[question] dependency graph resolving process

[szy1840]

What is your question?

Hello, currently I'm using conan 1.45.0. I want to learn about the dependency graph resolving process in detail, to solve some weird version conflict error. For example, I notice that even though we use version ranges, in the generated package binary we get a conaninfo.txt which pin down it's dependency version(and RREV, pkgID). When I call conan install, conan will scan and select a version of the direct dependencies, and will it immediately look at the select version and try to find a package binary(BFS or DFS)? If in DFS order, will it refer to the conanfile.py of the package, or conaninfo.txt of the package binary? When will conan use the current recipe of a package in local cache, and when will conan decide to fetch another one from remote? When will it decide to build a package binary if -b=missing ? Thank you!

Have you read the CONTRIBUTING guide?

• [X] I've read the CONTRIBUTING guide

[memsharded]

Hi @szy1840

Thanks for your question.

The first important bit is that Conan 2.0 and Conan 1.X are very different versions, and the way the expand the dependency graph would be different.

Then, it is important to know that the process has 3 stages, sequential and decoupled:

• First compute the dependency graph of "versions". This doesn't take into account binaries at all, but just compute the dependency graph of conan recipes, resolving version ranges, revisions, etc.
• Only when the graph is finalized and complete, it will start looking for binaries, first computing which binaries exists, which needs to be built, etc.
• Finally it will execute the installation, downloading or building packages as necessary

This is done this way because it is impossible in C/C++ to know if a binary exists until you know its exact dependencies versions. Having a new version upstream might require a different binary. So until the full graph is computed, it is not possible to analyze binary existence.

More concepts:

• The conaninfo.txt represents the package_id. It is not used for dependency resolution at all, it is the result of the dependency resolution, then mapped to the package_id with the "modes", as explained above, the computation of binaries is decoupled from the graph resolution
• Conan expands the graph depth first
• The --build=missing is applied when no binary for the current settings/options/dependencies exists, instead of failing, it will mark such binary to be built from sources.

Please let me know if this clarifies the issue

[szy1840]

Thank you a lot for your answer. Let me try to describe the process when I call conan install and all the dependencies are written in version range style. Please point out if my understanding is wrong:

1. (In Conan 1.X) Starting with pkgA, it's first dependency is pkgB. Conan first check if there is pkgB's recipe in local cache, which matches the version range.
2. If yes, use current recipe; If not, conan search remotes to fetch one.
3. It use the recipe of pkgB to check pkgB's requirements and do a DFS resolving process like step1&2.
4. Finally, all dependencies are resolved and their recipe are all in local cache. Then Conan computes every needed package binary hash id, using the given settings, options and dependencies of the package. Conan check if these binaries are in local cache -> try fetch -> try build.

Questions:

• In step2, will Conan fetch the newest version in all remotes?
• What is the dependencies overriding rule? Acording to Conan doc 1.45.0, I think the rule is "down stream first". But, consider the situation that A requires B, B requires D, A requires D. In the above process, Conan will first resolve the dependencies of D(from B's requirement), but when it reaches A's second requirement, D, it seems that Conan have to do the resolving again if the selected D's version doesn't match A's requirement. This seems not very resonable.

[memsharded]

Good questions:

In step2, will Conan fetch the newest version in all remotes?

No, by default it will iterate the remotes until one satisfying version is found. This wouldn't be an issue if different remotes contain different packages. For the same package having different versions in different remotes, it will return the first valid one. If you want to really get the newest from every remote the --update argument is necessary. This is done because this is a slower operation, and then it is done as opt-in.

What is the dependencies overriding rule? Acording to Conan doc 1.45.0, I think the rule is "down stream first". But, consider the situation that A requires B, B requires D, A requires D. In the above process, Conan will first resolve the dependencies of D(from B's requirement), but when it reaches A's second requirement, D,

The general rule in Conan is that the "downstream", whatever is closer to the user, gets higher priority (Conan 1.X might have some exceptions to this rule, but Conan 2.0 made this rule more widely used).

For the case you are commenting, this is the typical half-diamond structure. The full diamond would be if A->C->D. When you have A->B->D/1, and A->D/2, the dependency A->D/2 is propagated upstream to the graph, so when the dependency B->D is resolved the first time, it is already overwritten by D/2, and resolved to D/2. That is Conan 1.X has implicit overriding by default.

Conan 2.0 made this a conflict error, and A must explicitly define if D/2 is either an override or a forced dependency. If it doesn't specify it, Conan 2.0 will say it is a conflict error and needs to be resolved (typically, by adding the force or override). In any case, resolving again the same dependency subtree is never done, we have considered the possibility a few times, but given the amount of computation and backtracking that might be necessary seems unfeasible in reasonable times.

[szy1840]

Thank you for answering.

When you have A->B->D/1, and A->D/2, the dependency A->D/2 is propagated upstream to the graph, so when the dependency B->D is resolved the first time, it is already overwritten by D/2, and resolved to D/2.

I'm confused with the expression "propagated upstream to the graph", it seems to me that it's impossible for Conan to know A->D since Conan do the resolving in depth first order(if A->D is in the second line). And, in the full diamond situation(A->C->D/2), will D/1, from A->B->D/1, get overridden(downstream-level equal situation)?

[memsharded]

Conan does not "resolve" the A->D/2 dependency first. But it takes the "definition" (requires in Conan terms), and propagate it upstream in the graph while expanding A->B->D.

The full diamond situation does not override by default, it is both a conflict in 1.X and 2.0. It needs explicit override from A to decide which one of the D versions is the one to be used.

[szy1840]

I read some source code of Conan 1.45.0 today, and I generally understand the process now. But I cannot understand the following logic in conan/model/requires.py/Requirements, method update():

req.ref = other_ref
# FIXME: We should compute the intersection of version_ranges
if req.version_range and not other_req.version_range:
    req.range_ref = other_req.range_ref  # Override

My current knowledge: In Requirement, self.ref will change to the resolved version after processed by RangeResolver, and self.range_ref will not change(still the version range expression style conan reference). It seems to me that the if condition means Conan will only update the version range of current requirement when the downstream requirement is written in fixed version style, and will not change if the downsteam requirement is in version range style. But it do update ref in both condition, which will lead to difference of ref and range_ref if the downstream requirement is of version range style, and:

@property
def is_resolved(self):
    """ returns True if the version_range reference has been already resolved to a
    concrete reference
    """
    return self.ref != self.range_ref

This means the version range is resolved. This really confuse me, can you help me understand the code logic here? Thanks a lot!

[memsharded]

That version range resolution doesn't try to really resolve it, but just to validate that it fits in the existing range:

        if require.is_resolved:
            ref = require.ref
            resolved_ref = self._resolve_version(version_range, [ref])
            if not resolved_ref:
                raise ConanException("Version range '%s' required by '%s' not valid for "
                                     "downstream requirement '%s'"
                                     % (version_range, base_conanref, str(ref)))
            else:
                self._result.append("Version range '%s' required by '%s' valid for "
                                    "downstream requirement '%s'"
                                    % (version_range, base_conanref, str(ref)))
            return

This is taking the resolved ref and checking against the version range, not taking the version range and finding a valid ref that satisfy it. So the override is happening, and this is just trying to add some validation, as the FIXME reads, the version range intersection is not being computed, it is just checked after the fact.

In any case, it is probably not worth checking this, now that Conan 2.0 is live, all of that 1.X code will not be changed in most cases, as the risk of breaking existing users is too high, so I'd recommend checking the behavior of 2.0. Thanks!