Pip: 2020 resolver: get_topological_weights AssertionError

[jahn]

What did you want to do?

pip install --use-feature 2020-resolver sphinx==1.8.5
pip install --use-feature 2020-resolver sphinx sphinxcontrib-bibtex

After installing sphinx 1.8.5, pip freeze gives this:

alabaster==0.7.12
Babel==2.8.0
certifi==2020.6.20
chardet==3.0.4
docutils==0.16
idna==2.10
imagesize==1.2.0
Jinja2==2.11.2
MarkupSafe==1.1.1
packaging==20.4
Pygments==2.7.1
pyparsing==2.4.7
pytz==2020.1
requests==2.24.0
six==1.15.0
snowballstemmer==2.0.0
Sphinx==1.8.5
sphinxcontrib-serializinghtml==1.1.4
sphinxcontrib-websupport==1.2.4
urllib3==1.25.11

Output

ERROR: Exception:
Traceback (most recent call last):
  File "/home/jahn/usr/src/pipmaster/src/pip/_internal/cli/base_command.py", line 222, in _main
    status = self.run(options, args)
  File "/home/jahn/usr/src/pipmaster/src/pip/_internal/cli/req_command.py", line 178, in wrapper
    return func(self, options, args)
  File "/home/jahn/usr/src/pipmaster/src/pip/_internal/commands/install.py", line 378, in run
    requirement_set
  File "/home/jahn/usr/src/pipmaster/src/pip/_internal/resolution/resolvelib/resolver.py", line 183, in get_installation_order
    weights = get_topological_weights(graph)
  File "/home/jahn/usr/src/pipmaster/src/pip/_internal/resolution/resolvelib/resolver.py", line 242, in get_topological_weights
    assert len(weights) == len(graph)
AssertionError

Additional information

Dependency tree (before error):

pipdeptree==1.0.0
  - pip [required: >=6.0.0, installed: 20.3.dev0]
Sphinx==1.8.5
  - alabaster [required: >=0.7,<0.8, installed: 0.7.12]
  - babel [required: >=1.3,!=2.0, installed: 2.8.0]
    - pytz [required: >=2015.7, installed: 2020.1]
  - docutils [required: >=0.11, installed: 0.16]
  - imagesize [required: Any, installed: 1.2.0]
  - Jinja2 [required: >=2.3, installed: 2.11.2]
    - MarkupSafe [required: >=0.23, installed: 1.1.1]
  - packaging [required: Any, installed: 20.4]
    - pyparsing [required: >=2.0.2, installed: 2.4.7]
    - six [required: Any, installed: 1.15.0]
  - Pygments [required: >=2.0, installed: 2.7.1]
  - requests [required: >=2.0.0, installed: 2.24.0]
    - certifi [required: >=2017.4.17, installed: 2020.6.20]
    - chardet [required: >=3.0.2,<4, installed: 3.0.4]
    - idna [required: >=2.5,<3, installed: 2.10]
    - urllib3 [required: >=1.21.1,<1.26,!=1.25.1,!=1.25.0, installed: 1.25.11]
  - setuptools [required: Any, installed: 41.6.0]
  - six [required: >=1.5, installed: 1.15.0]
  - snowballstemmer [required: >=1.1, installed: 2.0.0]
  - sphinxcontrib-websupport [required: Any, installed: 1.2.4]
    - sphinxcontrib-serializinghtml [required: Any, installed: 1.1.4]

When installing sphinx and sphixcontrib-bibtex, sphinx is set to upgrade to 3.2.1. The error only appears when sphinx is given on the command line. When only sphinxcontrib-bibtex is installed, it works fine and sphinx is upgraded. The error appears both in 20.2.4 and master.

This is the value of weights in get_topological_weights:

{'six': 5, '<Python from Requires-Python>': 5, 'latexcodec': 4, 'pyyaml': 4, 'pybtex': 3, 'setuptools': 3, 'oset': 2, 'docutils': 3, 'pybtex-docutils': 2, 'pyparsing': 4, 'packaging': 3, 'pygments': 3, 'alabaster': 3, 'sphinxcontrib-devhelp': 3, 'sphinxcontrib-jsmath': 3, 'sphinxcontrib-serializinghtml': 3, 'markupsafe': 4, 'jinja2': 3, 'snowballstemmer': 3, 'sphinxcontrib-applehelp': 3, 'sphinxcontrib-htmlhelp': 3, 'idna': 4, 'chardet': 4, 'urllib3': 4, 'certifi': 4, 'requests': 3, 'pytz': 4, 'babel': 3, 'imagesize': 3, 'sphinxcontrib-qthelp': 3, 'sphinx': 2, 'sphinxcontrib-bibtex': 1, None: 0}

This is graph:

<pip._vendor.resolvelib.structs.DirectedGraph object at 0x7f99ccef19d0>

This is graph._vertices:

{'<Python from Requires-Python>', 'oset', None, 'idna', 'sphinxcontrib-devhelp', 'sphinxcontrib-jsmath', 'urllib3', 'sphinxcontrib-htmlhelp', 'six', 'imagesize', 'pyyaml', 'snowballstemmer', 'certifi', 'sphinxcontrib-qthelp', 'markupsafe', 'docutils', 'packaging', 'sphinxcontrib-bibtex', 'sphinx', 'pytz', 'alabaster', 'pyparsing', 'jinja2', 'sphinxcontrib-applehelp', 'babel', 'pygments', 'pybtex-docutils', 'setuptools', 'sphinxcontrib-websupport', 'sphinxcontrib-serializinghtml', 'pybtex', 'requests', 'latexcodec', 'chardet'}

sphinxcontrib-websupport is missing from weights.

This is graph._forwards:

{None: {'sphinxcontrib-bibtex', 'sphinx'}, 'sphinx': {'docutils', 'packaging', '<Python from Requires-Python>', 'pygments', 'setuptools', 'alabaster', 'sphinxcontrib-devhelp', 'sphinxcontrib-jsmath', 'sphinxcontrib-serializinghtml', 'jinja2', 'snowballstemmer', 'sphinxcontrib-applehelp', 'sphinxcontrib-htmlhelp', 'requests', 'babel', 'imagesize', 'sphinxcontrib-qthelp'}, 'sphinxcontrib-bibtex': {'pybtex', 'oset', 'pybtex-docutils', 'sphinx'}, 'alabaster': set(), 'babel': {'pytz'}, 'six': set(), 'packaging': {'six', 'pyparsing'}, 'pybtex': {'six', 'latexcodec', 'pyyaml', '<Python from Requires-Python>'}, 'pybtex-docutils': {'six', 'docutils', 'pybtex', '<Python from Requires-Python>'}, 'latexcodec': {'six', '<Python from Requires-Python>'}, 'docutils': set(), 'jinja2': {'markupsafe'}, 'imagesize': set(), 'requests': {'idna', 'chardet', 'urllib3', 'certifi'}, 'setuptools': set(), 'oset': {'setuptools'}, 'snowballstemmer': set(), 'pygments': set(), 'sphinxcontrib-jsmath': {'<Python from Requires-Python>'}, 'sphinxcontrib-applehelp': {'<Python from Requires-Python>'}, 'sphinxcontrib-htmlhelp': {'<Python from Requires-Python>'}, 'sphinxcontrib-qthelp': {'<Python from Requires-Python>'}, 'sphinxcontrib-devhelp': {'<Python from Requires-Python>'}, 'sphinxcontrib-serializinghtml': set(), 'sphinxcontrib-websupport': {'sphinxcontrib-serializinghtml'}, '<Python from Requires-Python>': set(), 'pyyaml': {'<Python from Requires-Python>'}, 'pytz': set(), 'markupsafe': set(), 'urllib3': set(), 'certifi': set(), 'chardet': set(), 'idna': set(), 'pyparsing': set()}

This is graph._backwards:

{None: set(), 'sphinx': {'sphinxcontrib-bibtex', None}, 'sphinxcontrib-bibtex': {None}, 'alabaster': {'sphinx'}, 'babel': {'sphinx'}, 'six': {'pybtex', 'packaging', 'latexcodec', 'pybtex-docutils'}, 'packaging': {'sphinx'}, 'pybtex': {'sphinxcontrib-bibtex', 'pybtex-docutils'}, 'pybtex-docutils': {'sphinxcontrib-bibtex'}, 'latexcodec': {'pybtex'}, 'docutils': {'pybtex-docutils', 'sphinx'}, 'jinja2': {'sphinx'}, 'imagesize': {'sphinx'}, 'requests': {'sphinx'}, 'setuptools': {'oset', 'sphinx'}, 'oset': {'sphinxcontrib-bibtex'}, 'snowballstemmer': {'sphinx'}, 'pygments': {'sphinx'}, 'sphinxcontrib-jsmath': {'sphinx'}, 'sphinxcontrib-applehelp': {'sphinx'}, 'sphinxcontrib-htmlhelp': {'sphinx'}, 'sphinxcontrib-qthelp': {'sphinx'}, 'sphinxcontrib-devhelp': {'sphinx'}, 'sphinxcontrib-serializinghtml': {'sphinxcontrib-websupport', 'sphinx'}, 'sphinxcontrib-websupport': set(), '<Python from Requires-Python>': {'pybtex-docutils', 'sphinx', 'sphinxcontrib-devhelp', 'sphinxcontrib-jsmath', 'sphinxcontrib-applehelp', 'pybtex', 'sphinxcontrib-htmlhelp', 'latexcodec', 'pyyaml', 'sphinxcontrib-qthelp'}, 'pyyaml': {'pybtex'}, 'pytz': {'babel'}, 'markupsafe': {'jinja2'}, 'urllib3': {'requests'}, 'certifi': {'requests'}, 'chardet': {'requests'}, 'idna': {'requests'}, 'pyparsing': {'packaging'}}

[paulmueller]

This is causing my rtd builds to fail (https://readthedocs.org/projects/dclab/builds/12162768/). My workaround was to pin sphinx to sphinx<2 in requirements.txt. But this is hardly a good solution.

[pradyunsg]

Thanks @jahn for a detailed report here!

It has been super helpful to have the reproducer as well as useful debugging information for this issue.

---

Visualising the graph here, it looks like we're getting a malformed graph from resolvelib.

Graph on 20.2.3 (good):

Graph on 20.2.4 (naughty):

Notice how the node for "sphinxcontrib-websupport" has sneaked into this one? That's causing the failure here.

---

A quick dump of words to describe things:

• sphinx 1.8.5 depends on sphinxcontrib-websupport.
• the failing install command will try upgrade to a newer sphinx (which doesn't depend on sphinxcontrib-websupport)
  
  
  
  • the lack of --upgrade flag + a forced upgrade + the presence of a "dependency drop" are all needed here.
  
  
  • passing the --upgrade flag makes things work!
  
  
  • this is because the resolver ignores installed versions -> it'll never look at sphinx 1.8.5 -> it won't "see" the sphinxcontrib-websupport -> sphinxcontrib-serializinghtml dependency.
  
  
• the resolver generates the correct result during the resolution and figures out the right details. (yay! or as I said when I figured this out -- thank goodness.)
• during the result graph construction, it goes through all packages.
  
  
  
  • if the node's not in the graph, it adds the parent to the graph. (yes, it does a bunch more but this is what's relevant here)
  
  
  • this bit of logic adds the node that's going to be "orphan" (like sphinxcontrib-websupport here) since its "parent" (the older sphinx version) is no longer part of the result (and hence, the graph).
  
  
• during "figure out the install order", we're constructing a topological order from this graph, under the assumption that all nodes are accessible from the root node.
  
  
  
  • That assumption is embodied by the assertion here.
  
  
  • Since the assumption is falsified by the behavior in the previous bullet, the assertion fails even though we _technically_ have the correct install order (because it won't visit the sphinxcontrib-websupport node during that chunk of code -- only nodes accessible from the root node). :)
  
  

It seems to me that this issue arises because that we're adding nodes that have no "path to root" in the graph, by adding the parent unconditionally. IOW, this is a bug in resolvelib's _build_result function, which means we'd need to fix it there (/cc @uranusjr).

---

SOOOO. Possible choices to make here:

• Figure out a better approach to generating the graph in resolvelib without orphan nodes like this.
• Dropping the assertion, since we know that the topological ordering is working fine and not the cause of this issue. (I like this one -- least effort)
• Ignore this issue for 20.3 release, since it's a fairly esoteric edge case. :P

Things to do here:

1. pick one of the above. :P
2. figure out a minimal test case for this class of failures.
3. write a test in whichever package we're making the fix on, to ensure this does the right thing.
4. implement the change and get that into master.
5. there is no step 5.

---

# This was the blob of code that I used to generate the input to graphviz, for those graphs.
print('digraph G {')
print('  rankdir=LR;')

for node, others in graph._forwards.items():
    print(f'  "{node}";')

for node, others in graph._forwards.items():
    for to_node in others:
        print(f'  "{node}" -> "{to_node}";')

print('}')

/cc @pfmoore because I couldn't find a smooth excuse to mention you earlier than this line. :)

[pradyunsg]

I figured that we're only seeing the installed version of sphinx because of #8924 and because the user has specified sphinx directly. Sooo... dropping sphinx from the set of packages that the user requests would mean that the resolver won't see the already-installed version.

And, yes, that works. Yay!

pip install --use-feature 2020-resolver sphinx==1.8.5
pip install --use-feature 2020-resolver sphinxcontrib-bibtex

Now, it's almost 4am. I'mma sleep.

[pfmoore]

Nice analysis! I think dropping sphinx from the list of user-requested packages is a 100% acceptable workaround.

It would be nice to not have that node in the graph, but I don't feel that's a critical issue as we know it's not a genuine issue with the resolution or ordering. I'm not 100% clear whether that's possible solely in resolvelib or whether it would need some help from pip, but that's something we can work out.

Maybe change the assertion to a warning, so we don't completely lose the information that something odd is going on. And maybe if we can create a test to demonstrate the issue (make it xfail until we deal with it) that would also help us not to forget about it.

Brain dump over.

Oh, and @jahn can I add my thanks for a very well written, detailed and helpful issue report. It made it much easier to understand what's going on here.

[pradyunsg]

I'm not 100% clear whether that's possible solely in resolvelib or whether it would need some help from pip, but that's something we can work out.

This is definitely solvable purely on the resolvelib side -- we'd basically need to rework the graph construction slightly to do the right thing.

[uranusjr]

Can you check whether sphinxcontrib-websupport also end up in mapping? resolvelib already does cleanup on it, and I’d be very worried if the cleanup is not working. If not, pip should be able to work around this by changing the sanity check to

assert len(weights) == len(result.mapping) + 1  # Plus the santinel None node.

instead. I will find some time to also fix it on resolvelib’s side as well, assuming the mapping entries are correct.

[uranusjr]

Darn, I’m having a hard time trying to come up with an simplified example. It seems that a simple backtrack is not enough to cause the issue. This is what I was trying to use as a test case:

* tea-0 depends on kettle==0
* coffee-0 depends on kettle==0
* coffee-1 depends on kettle==1 and water==0
* water-0 depends on nothing
* kettle-0 does not depend on anything
* kettle-1 depends on non stove==0 which does not exist (causing a backtrack)

Now I instruct the resolver to resolve coffee before tea. This would induce backtracking because kettle-1 ultimately hits a dead end. water-0 was added for coffee-1, and I was expecting it to be left behind after backtracking—but it was not. The resolver correctly cleans it up after resolution, and the graph only contains coffee-0, tea-0, and kettle-0.

Not sure what I’m missing 😞

[pfmoore]

I thought a key point with the original example was that sphinxcontrib-websupport was already installed even though we were upgrading to a version of sphinx that didn't depend on it? Would that show up differently in the resolvelib data? It would mean that the older version of sphinx that depended on sphinx-webcontrib gets prioritised (and seen by the resolver) ahead of the later version that doesn't...

[uranusjr]

I persumed ordering is key as well, which is why I made the newer version of coffee depend on water, instead of the older. In the original case, and older version of sphinx being already installed means that the version is tried before the newer; in my made-up case, the newer kettle is tried first.

I also tried mimicking the already installed behaviour by swapping kettle versions:

* tea-0 depends on kettle==0
* coffee-0 depends on kettle==0
* coffee-1 depends on kettle==1 and water==0
* water-0 depends on nothing
* kettle-0 depends on non stove==0 which does not exist (causing a backtrack)
* kettle-1 does not depend on anything

and instruct the provider to put kettle-0 before kettle-1 (simulating version 0 being already installed). The behaviour is the same, water is not present in the final graph—which is expected, since the resolver does not have any logic regarding the actual version, only how the candidates are ordered; the candidate ordering does not change between my two test cases.

---

Here’s the test code I’m using, maybe it’s me implementing things wrong…

def test_result_cleanup():
    dependencies = {
        ("kettle", 0): [],
        ("kettle", 1): [("stove", {})],
        ("water", 0): [],
        ("tea", 0): [("kettle", {0})],
        ("coffee", 0): [("water", {0}), ("kettle", {1})],
        ("coffee", 1): [("kettle", {0})],
    }
    pref_vers = {"coffee": {0: 1}}  # Prefer coffee-0 over coffee-1.

    class Provider(AbstractProvider):
        def identify(self, dependency):
            return dependency[0]

        def get_preference(self, resolution, candidates, information):
            # Resolve coffee before tea. This will cause backtracking.
            if candidates[0][0] == "tea":
                return 1
            return 0

        def get_dependencies(self, candidate):
            return dependencies[candidate]

        def find_matches(self, requirements):
            if not requirements:
                return []
            name, versions = requirements.pop()
            versions = {
                version
                for version in versions
                if all(version in r[1] for r in requirements)
            }

            # Prefer coffee-0 over coffee-1.
            if name == "coffee":
                return sorted((name, v) for v in versions)

            return sorted(((name, v) for v in versions), reverse=True)

        def is_satisfied_by(self, requirement, candidate):
            return candidate[1] in requirement[1]

    resolver = Resolver(Provider(), BaseReporter())
    result = resolver.resolve([("coffee", {0, 1}), ("tea", {0})])
    assert "water" in result.graph, list(result.graph)
    # AssertionError: [None, 'kettle', 'tea', 'coffee']

[pfmoore]

Ah I see, sorry.

But in the actual example, sphinxcontrib-websupport 1.2.4 (the equivalent of your "stove") does exist, it's installed in the first run.

[pradyunsg]

pip should be able to work around this by changing the sanity check to

assert len(weights) == len(result.mapping) + 1  # Plus the santinel None node.

Yup -- this works. :)

[tomasaschan]

I just stumbled on this error; I see it's fixed already in 20.3 (and could confirm that it works for my use case in 20.3b1) - but while waiting for 20.3 to drop, what can I do to figure out what packages I need to lock/remove in my project as a workaround?

[uranusjr]

There is a 20.3b1 you can install.

[pradyunsg]

The package that is already installed in the environment that would be updated. For ReadTheDocs builds, that's gonna be Sphinx.

[tomasaschan]

@uranusjr Yes - I know (as stated, I've already tested that my use case works on 20.3b1); my point was that I might not be able to do this in the production environment, so I would like to know what I could do with my deps while waiting for a non-beta version.