Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

2020 resolver: get_topological_weights AssertionError #9031

Closed
jahn opened this issue Oct 21, 2020 · 15 comments · Fixed by #9055
Closed

2020 resolver: get_topological_weights AssertionError #9031

jahn opened this issue Oct 21, 2020 · 15 comments · Fixed by #9055
Labels
kind: crash For situations where pip crashes type: bug A confirmed bug or unintended behavior
Milestone

Comments

@jahn
Copy link

jahn commented Oct 21, 2020

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'}}
@jahn jahn changed the title get_topological_weights AssertionError 2020 resolver: get_topological_weights AssertionError Oct 21, 2020
@pradyunsg pradyunsg added C: new resolver kind: crash For situations where pip crashes type: bug A confirmed bug or unintended behavior labels Oct 22, 2020
@paulmueller
Copy link

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 pradyunsg added the !release blocker Hold a release until this is resolved label Oct 22, 2020
@pradyunsg pradyunsg added this to the 20.3 milestone Oct 22, 2020
@pradyunsg
Copy link
Member

pradyunsg commented Oct 22, 2020

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):

Screenshot 2020-10-23 at 2 59 19 AM

Graph on 20.2.4 (naughty):

Screenshot 2020-10-23 at 2 59 51 AM

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
Copy link
Member

pradyunsg commented Oct 22, 2020

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
Copy link
Member

pfmoore commented Oct 23, 2020

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
Copy link
Member

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
Copy link
Member

uranusjr commented Oct 23, 2020

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
Copy link
Member

uranusjr commented Oct 23, 2020

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
Copy link
Member

pfmoore commented Oct 23, 2020

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
Copy link
Member

uranusjr commented Oct 24, 2020

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
Copy link
Member

pfmoore commented Oct 24, 2020

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.

mithro added a commit to f4pga/prjxray that referenced this issue Oct 24, 2020
tomschr added a commit to python-semver/python-semver that referenced this issue Oct 26, 2020
tomschr added a commit to python-semver/python-semver that referenced this issue Oct 26, 2020
@pradyunsg pradyunsg removed the !release blocker Hold a release until this is resolved label Oct 26, 2020
@pradyunsg
Copy link
Member

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. :)

hunterhector added a commit to asyml/forte that referenced this issue Oct 26, 2020
Get around the pip problem by removing sphinx explicitly:

See the issue here:
pypa/pip#9031

Sphinx will still be installed because the rtd-theme depends on it.
@tomasaschan
Copy link

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
Copy link
Member

uranusjr commented Nov 3, 2020

There is a 20.3b1 you can install.

@pradyunsg
Copy link
Member

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

@tomasaschan
Copy link

@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.

hoodmane pushed a commit to hoodmane/pyodide that referenced this issue Dec 16, 2020
pypa/pip#9031 is fixed so we can include sphinx in requirements.txt
Fixed Makefile so that it will use a virtual environment if one is active.
Added some simple directions for building docs.
hoodmane pushed a commit to hoodmane/pyodide that referenced this issue Dec 16, 2020
pypa/pip#9031 is fixed so we can include sphinx in requirements.txt
Fixed Makefile so that it will use a virtual environment if one is active.
Added some simple directions for building docs.
hoodmane pushed a commit to hoodmane/pyodide that referenced this issue Dec 16, 2020
pypa/pip#9031 is fixed so we can include sphinx in requirements.txt
Fixed Makefile so that it will use a virtual environment if one is active.
Added some simple directions for building docs.
@github-actions github-actions bot locked as resolved and limited conversation to collaborators Oct 7, 2021
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
kind: crash For situations where pip crashes type: bug A confirmed bug or unintended behavior
Projects
None yet
Development

Successfully merging a pull request may close this issue.

6 participants