Missing term in derivation tree

[zanieb]

Hey!

I'm sort of losing my mind digging around on this one, hopefully I'm missing something obvious.

I recently noticed this confusing error message, in which we say:

Because only the following versions of open3d are available:
    open3d==0.8.0.0
    open3d==0.9.0.0
    open3d==0.10.0.0
    open3d==0.10.0.1
    open3d==0.11.0
    open3d==0.11.1
    open3d==0.11.2
    open3d==0.12.0
    open3d==0.13.0
    open3d==0.14.1
    open3d==0.15.1
    open3d==0.15.2
    open3d==0.16.0
    open3d==0.16.1
    open3d==0.17.0
    open3d==0.18.0
and open3d<=0.15.2 has no wheels with a matching Python ABI tag, we can conclude that open3d<0.9.0.0 cannot be used.
And because open3d>=0.16.0 has no wheels with a matching platform tag and you require open3d, we can conclude that your requirements are unsatisfiable.

There are a few problems here, like, I'm transforming the derivation tree to collapse the "no wheels" incompatibilities and things get out of order so we make a conclusion about the usable versions before we have enumerated all the incompatibilities (tracking that in astral-sh/uv#9861)

But I want to focus on open3d<0.9.0.0, which doesn't make any sense here. If I display the complement of the range and turn of simplification based on the available versions, we get this instead:

Because only the following versions of open3d are available:
    open3d==0.8.0.0
    open3d==0.9.0.0
    open3d==0.10.0.0
    open3d==0.10.0.1
    open3d==0.11.0
    open3d==0.11.1
    open3d==0.11.2
    open3d==0.12.0
    open3d==0.13.0
    open3d==0.14.1
    open3d==0.15.1
    open3d==0.15.2
    open3d==0.16.0
    open3d==0.16.1
    open3d==0.17.0
    open3d==0.18.0
 and open3d<=0.15.2 has no wheels with a matching Python ABI tag, we can conclude that all of:
    open3d==0.9.0.0
    open3d==0.10.0.0
    open3d==0.10.0.1
    open3d==0.11.0
    open3d==0.11.1
    open3d==0.11.2
    open3d==0.12.0
    open3d==0.13.0
    open3d==0.14.1
    open3d==0.15.1
    open3d==0.15.2
    open3d==0.16.0
    open3d==0.16.1
    open3d==0.17.0
    open3d==0.18.0
cannot be used.
And because open3d>=0.16.0 has no wheels with a matching platform tag and you require open3d, we can conclude that your requirements are unsatisfiable.

Now we're in a place that makes way more sense. We enumerate all the available versions, then say open3d<=0.15.2 is incompatible and open3d>=0.16.0 is incompatible so all available versions are incompatible and there's no solution. There's one problem though:open3d==0.8.0.0 is missing from the conclusion.

I have this little utility to display the derivation tree for debug purposes:

#[allow(clippy::print_stderr)]
fn display_tree(
    error: &DerivationTree<PubGrubPackage, Range<Version>, UnavailableReason>,
    name: &str,
) {
    let mut lines = Vec::new();
    display_tree_inner(error, &mut lines, 0);
    lines.reverse();

    if std::env::var_os(EnvVars::UV_INTERNAL__SHOW_DERIVATION_TREE).is_some() {
        eprintln!("{name}\n{}", lines.join("\n"));
    } else {
        trace!("{name}\n{}", lines.join("\n"));
    }
}

fn display_tree_inner(
    error: &DerivationTree<PubGrubPackage, Range<Version>, UnavailableReason>,
    lines: &mut Vec<String>,
    depth: usize,
) {
    let prefix = "  ".repeat(depth).to_string();
    match error {
        DerivationTree::Derived(derived) => {
            display_tree_inner(&derived.cause1, lines, depth + 1);
            display_tree_inner(&derived.cause2, lines, depth + 1);
            for (package, term) in derived.terms.iter() {
                match term {
                    Term::Positive(versions) => {
                        lines.push(format!("{prefix}term {package}{versions}"));
                    }
                    Term::Negative(versions) => {
                        lines.push(format!("{prefix}term not {package}{versions}"));
                    }
                }
            }
        }
        DerivationTree::External(external) => match external {
            External::FromDependencyOf(package, version, dependency, dependency_version) => {
                lines.push(format!(
                    "{prefix}{package}{version} depends on {dependency}{dependency_version}"
                ));
            }
            External::Custom(package, versions, reason) => match reason {
                UnavailableReason::Package(_) => {
                    lines.push(format!("{prefix}{package} {reason}"));
                }
                UnavailableReason::Version(_) => {
                    lines.push(format!("{prefix}{package}{versions} {reason}"));
                }
            },
            External::NoVersions(package, versions) => {
                lines.push(format!("{prefix}no versions of {package}{versions}"));
            }
            External::NotRoot(package, versions) => {
                lines.push(format!("{prefix}not root {package}{versions}"));
            }
        },
    }
}

Which gives us

term root==0a0.dev0
  root==0a0.dev0 depends on open3d*
  term open3d*
    open3d==0.18.0 no wheels with a matching platform tag
    term open3d<0.18.0 | >0.18.0
      open3d==0.17.0 no wheels with a matching platform tag
      term open3d<0.17.0 | >0.17.0, <0.18.0 | >0.18.0
        open3d==0.16.1 no wheels with a matching platform tag
        term open3d<0.16.1 | >0.16.1, <0.17.0 | >0.17.0, <0.18.0 | >0.18.0
          open3d==0.16.0 no wheels with a matching platform tag
          term open3d<0.16.0 | >0.16.0, <0.16.1 | >0.16.1, <0.17.0 | >0.17.0, <0.18.0 | >0.18.0
            open3d==0.15.2 no wheels with a matching Python ABI tag
            term open3d<0.15.2 | >0.15.2, <0.16.0 | >0.16.0, <0.16.1 | >0.16.1, <0.17.0 | >0.17.0, <0.18.0 | >0.18.0
              open3d==0.15.1 no wheels with a matching Python ABI tag
              term open3d<0.15.1 | >0.15.1, <0.15.2 | >0.15.2, <0.16.0 | >0.16.0, <0.16.1 | >0.16.1, <0.17.0 | >0.17.0, <0.18.0 | >0.18.0
                open3d==0.14.1 no wheels with a matching Python ABI tag
                term open3d<0.14.1 | >0.14.1, <0.15.1 | >0.15.1, <0.15.2 | >0.15.2, <0.16.0 | >0.16.0, <0.16.1 | >0.16.1, <0.17.0 | >0.17.0, <0.18.0 | >0.18.0
                  open3d==0.13.0 no wheels with a matching Python ABI tag
                  term open3d<0.13.0 | >0.13.0, <0.14.1 | >0.14.1, <0.15.1 | >0.15.1, <0.15.2 | >0.15.2, <0.16.0 | >0.16.0, <0.16.1 | >0.16.1, <0.17.0 | >0.17.0, <0.18.0 | >0.18.0
                    open3d==0.12.0 no wheels with a matching Python ABI tag
                    term open3d<0.12.0 | >0.12.0, <0.13.0 | >0.13.0, <0.14.1 | >0.14.1, <0.15.1 | >0.15.1, <0.15.2 | >0.15.2, <0.16.0 | >0.16.0, <0.16.1 | >0.16.1, <0.17.0 | >0.17.0, <0.18.0 | >0.18.0
                      open3d==0.11.2 no wheels with a matching Python ABI tag
                      term open3d<0.11.2 | >0.11.2, <0.12.0 | >0.12.0, <0.13.0 | >0.13.0, <0.14.1 | >0.14.1, <0.15.1 | >0.15.1, <0.15.2 | >0.15.2, <0.16.0 | >0.16.0, <0.16.1 | >0.16.1, <0.17.0 | >0.17.0, <0.18.0 | >0.18.0
                        open3d==0.11.1 no wheels with a matching Python ABI tag
                        term open3d<0.11.1 | >0.11.1, <0.11.2 | >0.11.2, <0.12.0 | >0.12.0, <0.13.0 | >0.13.0, <0.14.1 | >0.14.1, <0.15.1 | >0.15.1, <0.15.2 | >0.15.2, <0.16.0 | >0.16.0, <0.16.1 | >0.16.1, <0.17.0 | >0.17.0, <0.18.0 | >0.18.0
                          open3d==0.11.0 no wheels with a matching Python ABI tag
                          term open3d<0.11.0 | >0.11.0, <0.11.1 | >0.11.1, <0.11.2 | >0.11.2, <0.12.0 | >0.12.0, <0.13.0 | >0.13.0, <0.14.1 | >0.14.1, <0.15.1 | >0.15.1, <0.15.2 | >0.15.2, <0.16.0 | >0.16.0, <0.16.1 | >0.16.1, <0.17.0 | >0.17.0, <0.18.0 | >0.18.0
                            open3d==0.10.0.1 no wheels with a matching Python ABI tag
                            term open3d<0.10.0.1 | >0.10.0.1, <0.11.0 | >0.11.0, <0.11.1 | >0.11.1, <0.11.2 | >0.11.2, <0.12.0 | >0.12.0, <0.13.0 | >0.13.0, <0.14.1 | >0.14.1, <0.15.1 | >0.15.1, <0.15.2 | >0.15.2, <0.16.0 | >0.16.0, <0.16.1 | >0.16.1, <0.17.0 | >0.17.0, <0.18.0 | >0.18.0
                              open3d==0.10.0.0 no wheels with a matching Python ABI tag
                              term open3d<0.10.0.0 | >0.10.0.0, <0.10.0.1 | >0.10.0.1, <0.11.0 | >0.11.0, <0.11.1 | >0.11.1, <0.11.2 | >0.11.2, <0.12.0 | >0.12.0, <0.13.0 | >0.13.0, <0.14.1 | >0.14.1, <0.15.1 | >0.15.1, <0.15.2 | >0.15.2, <0.16.0 | >0.16.0, <0.16.1 | >0.16.1, <0.17.0 | >0.17.0, <0.18.0 | >0.18.0
                                open3d==0.9.0.0 no wheels with a matching Python ABI tag
                                term open3d<0.9.0.0 | >0.9.0.0, <0.10.0.0 | >0.10.0.0, <0.10.0.1 | >0.10.0.1, <0.11.0 | >0.11.0, <0.11.1 | >0.11.1, <0.11.2 | >0.11.2, <0.12.0 | >0.12.0, <0.13.0 | >0.13.0, <0.14.1 | >0.14.1, <0.15.1 | >0.15.1, <0.15.2 | >0.15.2, <0.16.0 | >0.16.0, <0.16.1 | >0.16.1, <0.17.0 | >0.17.0, <0.18.0 | >0.18.0
                                  open3d==0.8.0.0 no wheels with a matching Python ABI tag
                                  no versions of open3d<0.8.0.0 | >0.8.0.0, <0.9.0.0 | >0.9.0.0, <0.10.0.0 | >0.10.0.0, <0.10.0.1 | >0.10.0.1, <0.11.0 | >0.11.0, <0.11.1 | >0.11.1, <0.11.2 | >0.11.2, <0.12.0 | >0.12.0, <0.13.0 | >0.13.0, <0.14.1 | >0.14.1, <0.15.1 | >0.15.1, <0.15.2 | >0.15.2, <0.16.0 | >0.16.0, <0.16.1 | >0.16.1, <0.17.0 | >0.17.0, <0.18.0 | >0.18.0

Notice we create the incompatibility open3d==0.8.0.0 no wheels with a matching Python ABI tag but it's never reflected in the terms — so it's missing from the conclusion.

I added a debug log for the term_intersection in the no_versions case in the resolver here and see

open3d<0.8.0.0 | >0.8.0.0, <0.9.0.0 | >0.9.0.0, <0.10.0.0 | >0.10.0.0, <0.10.0.1 | >0.10.0.1, <0.11.0 | >0.11.0, <0.11.1 | >0.11.1, <0.11.2 | >0.11.2, <0.12.0 | >0.12.0, <0.13.0 | >0.13.0, <0.14.1 | >0.14.1, <0.15.1 | >0.15.1, <0.15.2 | >0.15.2, <0.16.0 | >0.16.0, <0.16.1 | >0.16.1, <0.17.0 | >0.17.0, <0.18.0 | >0.18.0

So.. we do construct this term, it just doesn't make it into the tree? Is this expected? It seems incorrect? Does this reflect a bug in PubGrub or in our resolver implementation? I don't think it's possible to construct the correct error message without it.

You can reproduce this with

$ echo "open3d" | uv pip compile --no-cache --exclude-newer 2024-03-25T00:00:00Z --python-platform linux --python 3.10 -

For what it's worth, if I drop our transformation to merge incompatibilities you get

  × No solution found when resolving dependencies:
  ╰─▶ Because only the following versions of open3d are available:
          open3d==0.8.0.0
          open3d==0.9.0.0
          open3d==0.10.0.0
          open3d==0.10.0.1
          open3d==0.11.0
          open3d==0.11.1
          open3d==0.11.2
          open3d==0.12.0
          open3d==0.13.0
          open3d==0.14.1
          open3d==0.15.1
          open3d==0.15.2
          open3d==0.16.0
          open3d==0.16.1
          open3d==0.17.0
          open3d==0.18.0
      and open3d==0.8.0.0 has no wheels with a matching Python ABI tag, we can conclude that open3d<0.9.0.0 cannot be used.
      And because open3d==0.9.0.0 has no wheels with a matching Python ABI tag and open3d==0.10.0.0 has no wheels with a matching Python ABI tag, we can conclude that open3d<0.10.0.1 cannot be used.
      And because open3d==0.10.0.1 has no wheels with a matching Python ABI tag and open3d==0.11.0 has no wheels with a matching Python ABI tag, we can conclude that open3d<0.11.1 cannot be used.
      And because open3d==0.11.1 has no wheels with a matching Python ABI tag and open3d==0.11.2 has no wheels with a matching Python ABI tag, we can conclude that open3d<0.12.0 cannot be used.
      And because open3d==0.12.0 has no wheels with a matching Python ABI tag and open3d==0.13.0 has no wheels with a matching Python ABI tag, we can conclude that open3d<0.14.1 cannot be used.
      And because open3d==0.14.1 has no wheels with a matching Python ABI tag and open3d==0.15.1 has no wheels with a matching Python ABI tag, we can conclude that open3d<0.15.2 cannot be used.
      And because open3d==0.15.2 has no wheels with a matching Python ABI tag and open3d==0.16.0 has no wheels with a matching platform tag, we can conclude that open3d<0.16.1 cannot be used.
      And because open3d==0.16.1 has no wheels with a matching platform tag and open3d==0.17.0 has no wheels with a matching platform tag, we can conclude that open3d<0.18.0 cannot be used.
      And because open3d==0.18.0 has no wheels with a matching platform tag and you require open3d, we can conclude that your requirements are unsatisfiable.

Which handles the 0.8.0.0 conclusion with and open3d==0.8.0.0 has no wheels with a matching Python ABI tag, we can conclude that open3d<0.9.0.0 cannot be used.

The entire conclusion is quite logical, so perhaps we just need to revisit how were merging these. It's here for reference. That transformation may be entirely unsound and PubGrub is working as intended here.

[zanieb]

I fixed this by adjusting the terms during the collapse. I'm still not sure what I'm missing about how terms work :)

[Eh2406]

Sorry I did not respond sooner. I did a quick triage and decided that it needed my full attention, and never got around to it. Which is not fair to you. Some initial thoughts:

So.. we do construct this term, it just doesn't make it into the tree? Is this expected? It seems incorrect? Does this reflect a bug in PubGrub or in our resolver implementation?

It looks like that term is in the debugging tree.

                                  no versions of open3d<0.8.0.0 | >0.8.0.0, <0.9.0.0 | >0.9.0.0, <0.10.0.0 | >0.10.0.0, <0.10.0.1 | >0.10.0.1, <0.11.0 | >0.11.0, <0.11.1 | >0.11.1, <0.11.2 | >0.11.2, <0.12.0 | >0.12.0, <0.13.0 | >0.13.0, <0.14.1 | >0.14.1, <0.15.1 | >0.15.1, <0.15.2 | >0.15.2, <0.16.0 | >0.16.0, <0.16.1 | >0.16.1, <0.17.0 | >0.17.0, <0.18.0 | >0.18.0

Witch is the same as the term from your debug print.
It then combines it with open3d==0.8.0.0 no wheels with a matching Python ABI tag to give the:

                                term open3d<0.9.0.0 | >0.9.0.0, <0.10.0.0 | >0.10.0.0, <0.10.0.1 | >0.10.0.1, <0.11.0 | >0.11.0, <0.11.1 | >0.11.1, <0.11.2 | >0.11.2, <0.12.0 | >0.12.0, <0.13.0 | >0.13.0, <0.14.1 | >0.14.1, <0.15.1 | >0.15.1, <0.15.2 | >0.15.2, <0.16.0 | >0.16.0, <0.16.1 | >0.16.1, <0.17.0 | >0.17.0, <0.18.0 | >0.18.0

The entire conclusion is quite logical, so perhaps we just need to revisit how were merging these. It's here for reference. That transformation may be entirely unsound and PubGrub is working as intended here.

Maybe I'm missing something but "the PubGrub output make sense but my transformed output doesn't" strongly suggests the buggy is in the transformation. Not that I was able to spot what the problem is.

I'm still not sure what I'm missing about how terms work :)

I'm not sure either, but happy to keep digging with you until we both end up with a deeper understanding.