composer: hangs at `Resolving dependencies through SAT`

My composer.json:

{
    "require": {
        "laravel/lumen-framework": "5.2.*",
        "illuminate/session": "5.2.*",
        "illuminate/cookie": "5.2.*",
        "baryshev/tree-route": "2.0.*",
        "qiniu/php-sdk": "7.0.*",
        "endroid/qrcode": "1.7.*",
        "geoip2/geoip2": "^2.5",
        "hashids/hashids": "^2.0",
        "elasticsearch/elasticsearch": "^5.2",
        "fguillot/json-rpc": "1.2.*",
        "nikic/php-parser": "^2.0",
        "symfony/yaml": "^3.0",
        "michelf/php-markdown": "^1.7",
        "guzzlehttp/guzzle": "^6.2",
        "phpunit/phpunit": "^5.7",
        "friendsofphp/php-cs-fixer": "^2.10"
    }
}

Output of composer diagnose:

Checking composer.json: WARNING
No license specified, it is recommended to do so. For closed-source software you may use "proprietary" as license.
Checking platform settings: OK
Checking git settings: OK
Checking http connectivity to packagist: OK
Checking https connectivity to packagist: OK
Checking github.com rate limit: OK
Checking disk free space: OK
Checking pubkeys:
Tags Public Key Fingerprint: 57815BA2 7E54DC31 7ECC7CC5 573090D0  87719BA6 8F3BB723 4E5D42D0 84A14642
Dev Public Key Fingerprint: 4AC45767 E5EC2265 2F0C1167 CBBB8A2B  0C708369 153E328C AD90147D AFE50952
OK
Checking composer version: OK
Composer version: 1.6.2
PHP version: 7.1.11
PHP binary path: /usr/local/Cellar/php71/7.1.11_22/bin/php

When I run this command:

composer update -vvv

I get the following output:

Reading ./composer.json
Loading config file /Users/kimkit/.composer/config.json
Loading config file /Users/kimkit/.composer/auth.json
Loading config file ./composer.json
Checked CA file /usr/local/etc/openssl/cert.pem: valid
Executing command (/Users/kimkit/workspace/composer_hangs): git branch --no-color --no-abbrev -v
Executing command (/Users/kimkit/workspace/composer_hangs): git describe --exact-match --tags
Executing command (/Users/kimkit/workspace/composer_hangs): git log --pretty="%H" -n1 HEAD
Executing command (/Users/kimkit/workspace/composer_hangs): hg branch
Executing command (/Users/kimkit/workspace/composer_hangs): fossil branch list
Executing command (/Users/kimkit/workspace/composer_hangs): fossil tag list
Executing command (/Users/kimkit/workspace/composer_hangs): svn info --xml
Failed to initialize global composer: Composer could not find the config file: /Users/kimkit/.composer/composer.json
To initialize a project, please create a composer.json file as described in the https://getcomposer.org/ "Getting Started" section
Running 1.6.2 (2018-01-05 15:28:41) with PHP 7.1.11 on Darwin / 15.6.0
Loading composer repositories with package information
Downloading https://packagist.phpcomposer.com/packages.json
Writing /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/packages.json into cache
Updating dependencies (including require-dev)
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/p-provider-2013.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/p-provider-2014.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/p-provider-2015.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/p-provider-2016.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/p-provider-2017.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/p-provider-2017-04.json from cache
Downloading https://packagist.phpcomposer.com/p/provider-2017-07%24454d48e9263af7a06f7162ca9e8ec557784901c23f1bf2a10ff665a1dc7c2b56.json
Writing /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/p-provider-2017-07.json into cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/p-provider-2017-10.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/p-provider-2018-01.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/p-provider-archived.json from cache
Downloading https://packagist.phpcomposer.com/p/provider-latest%2478049d5f787d00c052969d5c5e926e1570c74df7d78f4dc0414c5a77571c1533.json
Writing /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/p-provider-latest.json into cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-laravel$lumen-framework.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-illuminate$auth.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-illuminate$broadcasting.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-illuminate$bus.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-illuminate$cache.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-illuminate$config.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-illuminate$container.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-illuminate$contracts.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-illuminate$database.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-illuminate$encryption.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-illuminate$events.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-illuminate$filesystem.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-illuminate$hashing.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-illuminate$http.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-illuminate$pagination.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-illuminate$pipeline.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-illuminate$queue.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-illuminate$support.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-illuminate$translation.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-illuminate$validation.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-monolog$monolog.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-mtdowling$cron-expression.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-nikic$fast-route.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-paragonie$random-compat.json from cache
Downloading https://packagist.phpcomposer.com/p/symfony/http-foundation%2436a98d954f7e1011ab64efb97dc934d307408d35f79a083efb49abfd5f7acb7d.json
Writing /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-symfony$http-foundation.json into cache
Downloading https://packagist.phpcomposer.com/p/symfony/http-kernel%249d0d233e4a15e927774d2dd8c132065151f278bbee1f459794ec11cb070a062b.json
Writing /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-symfony$http-kernel.json into cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-nesbot$carbon.json from cache
Downloading https://packagist.phpcomposer.com/p/symfony/finder%244d55b21d8af1e5a54fee0563fd6c057704a6b2449ce8c788c4b9cf99adde5953.json
Writing /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-symfony$finder.json into cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-illuminate$session.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-illuminate$console.json from cache
Downloading https://packagist.phpcomposer.com/p/symfony/process%24c7c0de15f68257319c32b78c52d27e927faafa7d2765448e8fa08b1fbc5dad65.json
Writing /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-symfony$process.json into cache
Downloading https://packagist.phpcomposer.com/p/symfony/debug%24ab4f1b62eef51b3cdc448b7d14931ed2bd0e44d7cb7fc4ccf5d7a88fe05a6d25.json
Writing /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-symfony$debug.json into cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-doctrine$inflector.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-symfony$translation.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-psr$log.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-symfony$polyfill-php54.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-symfony$polyfill-php55.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-symfony$polyfill-mbstring.json from cache
Downloading https://packagist.phpcomposer.com/p/symfony/event-dispatcher%249a70a600b97fa31e9bf2b0aea2ae3546b5254c4a25e75c6a14f2fa0c1cc7e4e7.json
Writing /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-symfony$event-dispatcher.json into cache
Downloading https://packagist.phpcomposer.com/p/symfony/console%2472610f1a5e928f5ed0ecd6163a24ebbac5f5996e3d871f7a5e7ff62a96c1ba96.json
Writing /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-symfony$console.json into cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-ircmaxell$password-compat.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-symfony$polyfill-php70.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-illuminate$view.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-symfony$polyfill-php56.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-symfony$polyfill-util.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-illuminate$cookie.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-baryshev$tree-route.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-qiniu$php-sdk.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-squizlabs$php-codesniffer.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-endroid$qrcode.json from cache
Downloading https://packagist.phpcomposer.com/p/symfony/options-resolver%2460c8a1553e7b59c1559b26e1cf71ec1bd9f5300905cb7bccc26be85d94d55890.json
Writing /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-symfony$options-resolver.json into cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-geoip2$geoip2.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-maxmind-db$reader.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-maxmind$web-service-common.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-composer$ca-bundle.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-hashids$hashids.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-elasticsearch$elasticsearch.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-guzzlehttp$ringphp.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-guzzlehttp$streams.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-react$promise.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-fguillot$json-rpc.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-nikic$php-parser.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-symfony$yaml.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-michelf$php-markdown.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-guzzlehttp$guzzle.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-guzzlehttp$psr7.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-guzzlehttp$promises.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-psr$http-message.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-phpunit$phpunit.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-myclabs$deep-copy.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-phpspec$prophecy.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-phpunit$php-code-coverage.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-phpunit$php-file-iterator.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-phpunit$php-text-template.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-phpunit$php-timer.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-phpunit$phpunit-mock-objects.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-sebastian$comparator.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-sebastian$diff.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-sebastian$environment.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-sebastian$exporter.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-sebastian$global-state.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-sebastian$object-enumerator.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-sebastian$resource-operations.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-sebastian$version.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-phpdocumentor$reflection-docblock.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-doctrine$instantiator.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-sebastian$recursion-context.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-phpunit$php-token-stream.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-sebastian$code-unit-reverse-lookup.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-dflydev$markdown.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-phpdocumentor$reflection-common.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-phpdocumentor$type-resolver.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-webmozart$assert.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-friendsofphp$php-cs-fixer.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-composer$semver.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-doctrine$annotations.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-gecko-packages$gecko-php-unit.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-php-cs-fixer$diff.json from cache
Downloading https://packagist.phpcomposer.com/p/symfony/filesystem%24726a98202b11f420ffb48ba6e5cadda47243114a9d24277ec8d71c2e8317d85f.json
Writing /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-symfony$filesystem.json into cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-symfony$polyfill-php72.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-symfony$stopwatch.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-doctrine$lexer.json from cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-tightenco$collect.json from cache
Downloading https://packagist.phpcomposer.com/p/symfony/config%24f2be59972223e0ecb946b034c586631e2e690adde3d61d2f0890101bab118f9a.json
Writing /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-symfony$config.json into cache
Reading /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-twig$twig.json from cache
Downloading https://packagist.phpcomposer.com/p/symfony/dependency-injection%24e9e53dff253d1184e7bed2edf20a122b484fe8c45fede4be74fd982f57049516.json
Writing /Users/kimkit/.composer/cache/repo/https---packagist.phpcomposer.com/provider-symfony$dependency-injection.json into cache
Resolving dependencies through SAT

If I chanage friendsofphp/php-cs-fixer to ^1.13, It’s OK. I check runSat method, dump the $rulesCount, it equals to 99268, in the below for loop, it always continue, but $n takes many time to reach the $rulesCount value, so It hangs. I’m not sure it’s a bug, please check this problem.

About this issue

Original URL
State: closed
Created 6 years ago
Reactions: 11
Comments: 38 (21 by maintainers)

Most upvoted comments

It also should be noted that this problem is, because of the quote above, not Composer specific. apt, yum and npm use similar algorithms and have similar issues. For apt and yum the reason you don’t notice them is that they’re C++ and that system dependencies tend to be much more rigidly versioned than open source PHP libraries.

Also PHP just sucks at memory management for tasks like this. Composer in C++ would likely be 10 to literally 10000 times faster for the SAT process.

npm circumvents the core issue by not having the concept of ‘namespacing’ in its language, so it can just install multiple versions of the same package, which it does, hence why it’s usually faster than Composer. In PHP (and Java, and C++, and C#, and…) you simply cannot install 2 versions of symfony/yaml as they’d kill namespacing.

curry684 on Jul 3, 2018

The problem is with recursive dependencies. Your root packages are pretty much fixed, but the “second level dependencies” may vary immensely. For example a constraint on phing/phing:^2.0 already has 21 valid versions right now. All of them may or may not have different dependencies. Specifically all versions below 2.16 do not depend on symfony/yaml at all, being 19 of them.

phing/phing:2.6.1 depends directly on symfony/yaml: ^3.1 || ^4.0. So composer require fkooman/config will start by evaluating whether any existing root requirements violate the new package, and determine the right version to include based on that. That’s less than a hundred evaluations to find out it can’t.

Adding the dependency to composer.json and hitting update does not confer that prior knowledge about “who is the new guy”. Composer just has to work its way through all your 50 dependencies, with their 25 version, each with their 10 own dependencies, with 25 versions, each with their 5 own dependencies, with 25 versions. That’s millions of solutions to evaluate before it could stumble upon the two rules that not only flat out contradict, but are also not circumventable by dropping a package version, for example if you included phing/phing:^2.15 it could just drop to 2.15.2 and still be compatible with fkooman/config.

The best way to keep dependency resolution quick is to keep your constraints tight but Semver. It’s frequently faster to evaluate a caret constraint than a fixed constraint because it makes for faster drops closer to the root package. The tighter the constraints the more it has to try 4 levels deep to make it work, and that means exponentially tons more solutions to evaluate.

In other words: Composer is generally happier with root constraints that give it 1000 valid solutions out of a million possible ones, than 10 valid solutions out of half a million. SAT is designed to keep going until it times out (which Composer doesn’t out of principle) or a valid solution is found. Even if means evaluating 999.999 before the last one works. And with the average medium-sized project, there are tens of millions possible solutions.

Also refer to https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Algorithms_for_solving_SAT:

Since the SAT problem is NP-complete, only algorithms with exponential worst-case complexity are known for it.

curry684 on Jul 3, 2018

JL2014 on May 23, 2019

For anyone lurking: I attempted a more granular version control (specifying ~3.5 rather than ~3.0) and it worked immediately. My specific issue at least seemed to be the version specified, though I’m still unsure why.

CmdrSharp on Apr 5, 2018