22.0: assert len(weights) == expected_node_count AssertionError

[elParaguayo]

Description

Hi there,

I'm one of the maintainers for Qtile (https://www.github.com/qtile/qtile).

I've noticed that our docs (hosted by ReadTheDocs) have begun failing to build.

The error message is:

ERROR: Exception:
Traceback (most recent call last):
  File "/home/docs/checkouts/readthedocs.org/user_builds/qtile/envs/3274/lib/python3.7/site-packages/pip/_internal/cli/base_command.py", line 165, in exc_logging_wrapper
    status = run_func(*args)
  File "/home/docs/checkouts/readthedocs.org/user_builds/qtile/envs/3274/lib/python3.7/site-packages/pip/_internal/cli/req_command.py", line 205, in wrapper
    return func(self, options, args)
  File "/home/docs/checkouts/readthedocs.org/user_builds/qtile/envs/3274/lib/python3.7/site-packages/pip/_internal/commands/install.py", line 389, in run
    to_install = resolver.get_installation_order(requirement_set)
  File "/home/docs/checkouts/readthedocs.org/user_builds/qtile/envs/3274/lib/python3.7/site-packages/pip/_internal/resolution/resolvelib/resolver.py", line 190, in get_installation_order
    expected_node_count=len(self._result.mapping) + 1,
  File "/home/docs/checkouts/readthedocs.org/user_builds/qtile/envs/3274/lib/python3.7/site-packages/pip/_internal/resolution/resolvelib/resolver.py", line 276, in get_topological_weights
    assert len(weights) == expected_node_count
AssertionError

The first failure (https://readthedocs.org/projects/qtile/builds/15928125/) was the first build following the release of 22.0.

The most recent failure (https://readthedocs.org/projects/qtile/builds/15931046/) also fails on 22.0.1.

Expected behavior

Documents should build successfully.

I'm not aware of any other changes that would have impacted the building of our docs.

pip version

22.0 and 22.0.1

Python version

3.7

OS

ReadTheDocs docker image - I think is Ubuntu 20.04

How to Reproduce

(Appreciate this isn't particularly helpful...)

1. Submit a PR for Qtile
2. Hook starts build of docs
3. Build fails

Note: I cannot recreate locally. However, given that the failures started with 22.0 I can only assume it's caused by that. Unfortunately, I don't know what the error message means.

Output

No response

Code of Conduct

• I agree to follow the PSF Code of Conduct.

[pradyunsg]

This is likely related to #10574.

/cc @mauritsvanrees in case they're interested!

[pradyunsg]

@elParaguayo Can you try creating a clean virtualenv, and running pip install -r doc/requirements.txt in it, on a compatible system, with that project? If you can confirm that's a reproducer, that'd be great! ^>^

[elParaguayo]

I tried that. I create a virtual environment with python 3.7, upgraded pip to latest and installed requirements. No error message.

I was hoping to get the same error locally.

[pradyunsg]

Hmmm... Maybe this needs running the pip install commands that RTD runs before those?

pip install --upgrade pip setuptools<58.3.0 
pip install --upgrade mock==1.0.1 pillow==5.4.1 alabaster>=0.7,<0.8,!=0.7.5 commonmark==0.8.1 recommonmark==0.5.0 sphinx<2 sphinx-rtd-theme<0.5 readthedocs-sphinx-ext<2.2 
pip install -r docs/requirements.txt

It might be that already-installed packages are implicated.

[boxed]

This started happening to me too.

[notatallshaw]

Hmmm... Maybe this needs running the pip install commands that RTD runs before those?

pip install --upgrade pip setuptools<58.3.0 
pip install --upgrade mock==1.0.1 pillow==5.4.1 alabaster>=0.7,<0.8,!=0.7.5 commonmark==0.8.1 recommonmark==0.5.0 sphinx<2 sphinx-rtd-theme<0.5 readthedocs-sphinx-ext<2.2 
pip install -r docs/requirements.txt

It might be that already-installed packages are implicated.

I am able to reproduce the error following these steps with a fresh virtual environment. Here are the steps specifically:

python3.10 -m venv .venv
source .venv/bin/activate
python -m pip install --upgrade pip "setuptools<58.3.0"
python -m pip install --upgrade mock==1.0.1 pillow==5.4.1 "alabaster>=0.7,<0.8,!=0.7.5" commonmark==0.8.1 recommonmark==0.5.0 "sphinx<2" "sphinx-rtd-theme<0.5" "readthedocs-sphinx-ext<2.2"
python -m pip install -r requirements.txt

And the requirements file looks like this:

setuptools_scm
sphinx
sphinx_rtd_theme
funcparserlib==1.0.0a0
sphinxcontrib-seqdiag
numpydoc
cairocffi >= 0.9.0
cffi >= 1.1.0
xcffib >= 0.10.1

I have not been able to reproduce it using a single install or using download.

I set a breakpoint where the asert statement is and I found:

(Pdb) expected_node_count
41
(Pdb) len(weights)
42
(Pdb) weights
{'snowballstemmer': 41, 'urllib3': 41, 'alabaster': 41, 'pytz': 41, 'six': 41, 'pyparsing': 41, 'imagesize': 41, '<Python from Requires-Python>': 41, 'pygments': 41, 'pillow': 41, 'charset-normalizer': 41, 'docutils': 41, 'certifi': 41, 'setuptools': 41, 'markupsafe': 41, 'sphinxcontrib-serializinghtml': 41, 'idna': 41, 'packaging': 24, 'funcparserlib': 24, 'sphinxcontrib-websupport': 24, 'webcolors': 24, 'pycparser': 24, 'sphinxcontrib-qthelp': 24, 'sphinxcontrib-htmlhelp': 24, 'babel': 24, 'sphinxcontrib-applehelp': 24, 'tomli': 24, 'requests': 24, 'sphinxcontrib-devhelp': 24, 'sphinxcontrib-jsmath': 24, 'jinja2': 24, 'cffi': 10, 'sphinx': 10, 'setuptools-scm': 10, 'blockdiag': 10, 'cairocffi': 6, 'sphinx-rtd-theme': 6, 'numpydoc': 6, 'seqdiag': 6, 'xcffib': 6, 'sphinxcontrib-seqdiag': 1, None: 0}

[mauritsvanrees]

I can't easily check the example, because installing Pillow fails due to missing zlib. I should have that installed, and I have various Pillow versions installed correctly, but I get this error more often.

The expected_node_count is defined as len(self._result.mapping) + 1. Can someone post which items are in self._result.mapping? If we see which one is missing from weights, this would help.

This one in weights looks suspicious: <Python from Requires-Python>.

BTW, if someone is looking for a workaround, you could try an extra option for pip install: --use-deprecated legacy-resolver. I don't know if it helps, but it may be worth a try.

[elParaguayo]

FYI - ReadTheDocs are pinning pip to 21.3.1 for now.

readthedocs/readthedocs.org#8864 (comment)

[notatallshaw]

The expected_node_count is defined as len(self._result.mapping) + 1. Can someone post which items are in self._result.mapping? If we see which one is missing from weights, this would help.

This was a fun little learning exercise with the debugger (I've removed the parts where I'm figuring out how to do this):

> /home/damian/nodebug/pip/src/pip/_internal/resolution/resolvelib/resolver.py(278)get_topological_weights()
-> assert weights[None] == 0
(Pdb) u
> /home/damian/nodebug/pip/src/pip/_internal/resolution/resolvelib/resolver.py(188)get_installation_order()
-> weights = get_topological_weights(
(Pdb) globals()['result_mapping'] = self._result.mapping
(Pdb) d
> /home/damian/nodebug/pip/src/pip/_internal/resolution/resolvelib/resolver.py(278)get_topological_weights()
-> assert weights[None] == 0
(Pdb) len(weights)
42
(Pdb) len(result_mapping)
40
(Pdb) weights - result_mapping.keys()
{'sphinxcontrib-websupport', None}

So "sphinxcontrib-websupport" is in the weights but not in the self._result.mapping.

[pradyunsg]

See #9031, which also involved sphinxcontrib-websupport.

[notatallshaw]

See #9031, which also involved sphinxcontrib-websupport.

That looks horrendous... And given the steps required to produce this error it's probably a very similar issue.

Perhaps the graph cleaning assumes you can't have nodes which are not descendants of the root node? Which appears like it can still be the case reading that issue?

[AllexVeldman]

For completeness, this is also raised when running pip install tox tox-gh probably due to tox-gh pinning tox to an alpha release (4.0.0a10), resulting in 2 versions of tox.

In previous releases of pip this would install the dependency defined by tox-gh.

Removing tox from the install command solves this instance.

[mauritsvanrees]

I confirm that this can be reproduced with the original instructions of issue #9031. Updated for pip 22:

pip install -U pip
pip install sphinx==1.8.5
pip install sphinx sphinxcontrib-bibtex

In this case, before calculating the topological weights:

(Pdb) len(graph)
34
(Pdb) len(self._result.mapping)
32
(Pdb) set(graph) - set(self._result.mapping)
{'sphinxcontrib-websupport', None}
(Pdb) len(req_set.requirements.keys())
14
(Pdb) req_set.requirements.keys()
odict_keys(['sphinxcontrib-bibtex', 'sphinx', 'docutils', 'importlib-metadata', 'pybtex', 'pybtex-docutils', 'sphinxcontrib-htmlhelp', 'sphinxcontrib-applehelp', 'sphinxcontrib-devhelp', 'sphinxcontrib-jsmath', 'sphinxcontrib-qthelp', 'latexcodec', 'pyyaml', 'zipp'])

Some ideas:

• Several values in self._result.mapping are instances of the class pip._internal.resolution.resolvelib.candidates.AlreadyInstalledCandidate. Can we ignore these? They are installed already, so they don't need to be installed anymore. But maybe these are older versions from packages that we want to upgrade, or reinstall? (If we cannot ignore them, then maybe already installed candidates should get the highest possible weight, but that won't solve the current issue.)
• get_topological_weights is only used to define the sort order of req_set.requirements.items(). As you can see in the short pdb session above, this only contains 14 keys. So the weights must exactly these 14, and we can ignore all others. That should simplify things.

When I try the last idea, it works for pip install sphinx sphinxcontrib-bibtex.
I can try a PR.

[pradyunsg]

Perhaps the graph cleaning assumes you can't have nodes which are not descendants of the root node? Which appears like it can still be the case reading that issue?

The graph cleaning "trims" nodes that don't have any edges "out" of them. This makes it so that the graph is only left with cycles by the time we recursive visit logic that is keeps track of paths and visits every possible path, which makes the whole thing a lot quicker.

That won't be affected by the root cause of this failure, which originates from resolvelib not spewing out the right keys in the mapping object. Anyway, this is an easy fix -- change the assertion to assume that the weighted graph will be the same length as the graph put into the topological sort. 🤷🏽

[mauritsvanrees]

This PR should fix it: #10867

[mauritsvanrees]

For completeness, this is also raised when running pip install tox tox-gh probably due to tox-gh pinning tox to an alpha release (4.0.0a10), resulting in 2 versions of tox.

In previous releases of pip this would install the dependency defined by tox-gh.

With pip 22.0.2, I also see this error. With my PR it works again, resulting in an install of tox 4.0.0a10.

[Secunseen]

So can anyone help me out with 22.0.3

[notatallshaw]

So can anyone help me out with 22.0.3

This issue is closed. If you have a new issue with the latest version of pip (currently 22.0.3) you should report that new issue.