From 23542bd10f4e58fdbd879599dc3f66b1f9265b77 Mon Sep 17 00:00:00 2001 From: Alejandro R Mosteo Date: Wed, 18 Aug 2021 12:59:22 +0200 Subject: [PATCH] Releases providing the same 3rd crate no longer implicitly conflict (#780) * Crates that "provides" the same no longer conflict This allows having several compilers in the same crate * Remove assumptions derived from implicit conflicts * Speed-ups in solver for the gnat dependency * doc/toolchains.md: Update to reflect current status * Typo --- doc/toolchains.md | 122 ++++---- src/alire/alire-conditional_trees.ads | 7 +- src/alire/alire-index.adb | 6 +- src/alire/alire-index.ads | 2 +- src/alire/alire-releases-containers.adb | 32 +-- src/alire/alire-releases-containers.ads | 10 +- src/alire/alire-releases.ads | 4 +- src/alire/alire-roots-editable.adb | 2 +- src/alire/alire-solutions.adb | 91 +++--- src/alire/alire-solutions.ads | 53 ++-- src/alire/alire-solver.adb | 266 +++++++++--------- src/alr/alr-commands-search.adb | 1 + src/alr/alr-commands-show.adb | 2 +- .../solver/equivalences-conflict/test.py | 1 + .../solver/equivalences-conflict/test.yaml | 0 .../cr/crate_virt_1/crate_virt_1-2.0.0.toml | 10 + .../crate_virt_2-1.0.0.toml} | 2 +- testsuite/tests/pin/missing-version/test.py | 6 +- .../tests/solver/provides-no-conflict/test.py | 30 ++ .../solver/provides-no-conflict/test.yaml | 4 + 20 files changed, 358 insertions(+), 293 deletions(-) rename testsuite/{tests => disabled}/solver/equivalences-conflict/test.py (91%) rename testsuite/{tests => disabled}/solver/equivalences-conflict/test.yaml (100%) create mode 100644 testsuite/fixtures/toolchain_index/cr/crate_virt_1/crate_virt_1-2.0.0.toml rename testsuite/fixtures/toolchain_index/cr/{crate_clash/crate_clash-1.0.0.toml => crate_virt_2/crate_virt_2-1.0.0.toml} (94%) create mode 100644 testsuite/tests/solver/provides-no-conflict/test.py create mode 100644 testsuite/tests/solver/provides-no-conflict/test.yaml diff --git a/doc/toolchains.md b/doc/toolchains.md index 124e5347..a392ccf1 100644 --- a/doc/toolchains.md +++ b/doc/toolchains.md @@ -2,34 +2,60 @@ Toolchains are comprised by a GNAT compiler and a `gprbuild` project file processor. Alire strives to simplify the availability of GNAT releases, which -are packaged to be retrieved and used with ease. Still, the compiler preferred -by the user might not be appropriate for some crates, which may cause subtle -interactions that this section explains. - -Some crates may require particular GNAT compilers (for example for -cross-compilation). Note that, independently of the compiler finally made -available by `alr` in the environment, the crate project file still must define -an appropriate `Target` attribute for the desired compiler. At the moment, Alire -does not examine project file contents to identify necessary compilers, and -relies only on regular `depends-on` dependencies. - -There are two sides to toolchain use by `alr`. On the one hand, a solution may -or may not have dependencies on GNAT compilers. On the other hand, the user may -or may have not selected a default toolchain for use via `alr toolchain ---select`. The interaction between these two features is explained next. - -Before going into the details, there are two kind of dependencies on GNAT -compilers: generic dependencies on the `gnat` crate, which apply to every -compiler, and dependencies on a precise native or cross-compiler, e.g., -`gnat_native` or `gnat_riscv_elf`. +are packaged to be retrieved and used with ease. + +The user can now select a preferred compiler via `alr toolchain --select`. +Releases may still override this selection (for example to use a +cross-compiler). + +There are two kind of dependencies on GNAT compilers: generic dependencies on +the `gnat` crate, which apply to every compiler, and dependencies on a precise +native or cross-compiler. + +The native compiler for each platform is always `gnat_native`, whereas +cross-compilers follow the naming convention `gnat_` (e.g., +`gnat_riscv_elf`). Alire will only offer to install valid cross-compilers for +the host platform. ## Identifying available compilers -Available compilers can be listed with `alr search --full --external-detect -gnat_`. They will also be shown by the selection assistant, `alr toolchain ---select`. +Compilers available for download can be listed with `alr search --full +--external-detect gnat_`. They will also be shown by the selection assistant, +`alr toolchain --select`. + +Running `alr toolchain` without arguments will show the installed compilers and +the preferred compiler, if any. + +## Manual compiler installation + +Besides selecting a default compiler with `alr toolchain --select`, the user +may install other compilers via `alt toolchain --install`. Installed but +unselected compilers will not be used, though, unless a crate explicitly +requests them via dependencies. + +Compilers can be removed with `alr toolchain --uninstall`. -## Specifying dependencies on GNAT compilers +## Automatic compiler installation + +If a crate requires a target-specific compiler via its dependencies, `alr` will +attempt to use first a matching installed compiler. Otherwise, a matching +compiler will be automatically downloaded. + +Generic dependencies on `gnat` will never cause a compiler download. + +## Automatic compiler selection by Alire + +When a build is launched, or `alr printenv` is run to obtain a build environment, +`alr` will use the available compilers as follows: + +1. Any target-specific compiler needed due to dependencies will be +selected. +1. Otherwise, if the user has defined a preferred compiler, it will be +selected. +1. If no preferred compiler has been defined, Alire will rely on the existing +user environment. + +## Specifying dependencies on GNAT compilers for crate publishing From the point of view of a user preparing a release for publication, these are the considerations to bear in mind: @@ -38,43 +64,17 @@ are the considerations to bear in mind: - Use dependencies on `gnat` to specify known compiler version restrictions. - Use dependencies on a precise gnat cross-compiler (e.g., `gnat_riscv_elf`) when your crate is purposely only available for such a target. -- There is no reason to specify a dependency on the native compiler +- It is normally not necessary to specify a dependency on the native compiler (`gnat_native`) as that would unnecessarily limit the availability of a library crate that might be useful to dependent cross-target crates. +- It may be useful to depend on `gnat_native` in cases where a crate builds a + tool to be used always in the host platform, for example to be used in some + action during the build process. + +## Note about cross-compilation -## Interactions with a selected toolchain - -From the point of view of a user wanting to compile some release, there will be -an interaction between the solution dependency on compilers and a selected -default compiler. - -The simplest and most usual scenario for native compilation is as follows: - -- Solution without dependencies on `gnat`: - - If a default compiler has been configured: the compiler will be included in the - PATH provided by `alr printenv` and used for the build. - - No compiler has been configured: `alr` will attempt to use whatever toolchain is - available in the user's environment prior to running `alr`. - - Note that compilers deployed with `alr toolchain --install` but not - selected as the default will not be used in this case. - -For crates with dependencies on GNAT compilers, the following two cases simultaneously apply: - -- Solution with generic dependencies on `gnat`: The solver will provide a - concrete GNAT to satisfy this dependency, applying the following - prioritization: - 1. A target-specific compiler that is already a dependency. - 1. The default compiler, if it has been defined. - 1. A native compiler that is already deployed. - 1. A cross-compiler that is already deployed. - 1. A native compiler from the index, that will be deployed with the rest of dependencies. - 1. A cross-compiler from the index, that will be deployed with the rest of dependencies. - -- Solution with dependencies on a target-specific GNAT (`gnat_native`, `gnat_ricv_elf`, - etc.): The `alr` solver will provide one compiler in the environment, applying the - following prioritization: - 1. A matching compiler that is already deployed, explicitly via `alr - toolchain --select`/`alr toolchain --install`, or implicitly during a previous - solving. - 1. A compiler that satisfies the dependency available in the catalog, - which will be deployed as part of regular dependency retrieval. +Independently of the compiler made available by `alr` in the environment, the +crate project file still must define an appropriate `Target` attribute for the +desired compiler. At the moment, Alire does not examine project file contents +to identify necessary compilers, and relies only on regular `depends-on` +dependencies. diff --git a/src/alire/alire-conditional_trees.ads b/src/alire/alire-conditional_trees.ads index d39aae26..ec66ad4f 100644 --- a/src/alire/alire-conditional_trees.ads +++ b/src/alire/alire-conditional_trees.ads @@ -93,7 +93,8 @@ package Alire.Conditional_Trees with Preelaborate is -- used to store conditional/dynamic properties and dependencies. -- Iteration is only over direct children, when the tree is AND/OR vector. - function Root (This : Tree) return Node'Class; + function Root (This : Tree) return Node'Class + with Pre => not This.Is_Empty; function Is_Iterable (This : Tree) return Boolean; -- Iterators visit only immediate values (leaves or vectors). Thus, this @@ -349,7 +350,7 @@ private function To_YAML (V : Leaf_Node) return String; function Is_Value (This : Tree) return Boolean is - (This.Root in Leaf_Node); + (not This.Is_Empty and then This.Root in Leaf_Node); function Value (This : Tree) return Values is (Leaf_Node (This.Root).Value.Element); @@ -449,7 +450,7 @@ private function TO_YAML (V : Vector_Node) return String; function Is_Vector (This : Tree) return Boolean is - (This.Root in Vector_Node); + (not This.Is_Empty and then This.Root in Vector_Node); -- Delayed implementation to avoid freezing: diff --git a/src/alire/alire-index.adb b/src/alire/alire-index.adb index d933a2b1..58e28d51 100644 --- a/src/alire/alire-index.adb +++ b/src/alire/alire-index.adb @@ -257,7 +257,7 @@ package body Alire.Index is function Releases_Satisfying (Dep : Dependencies.Dependency; Env : Properties.Vector; Use_Equivalences : Boolean := True; - Available : Boolean := True) + Available_Only : Boolean := True) return Releases.Containers.Release_Set is Result : Releases.Containers.Release_Set; @@ -268,7 +268,7 @@ package body Alire.Index is if Exists (Dep.Crate) then for Release of Crate (Dep.Crate).Releases loop if Release.Satisfies (Dep) - and then (not Available or else Release.Is_Available (Env)) + and then (not Available_Only or else Release.Is_Available (Env)) then Result.Insert (Release); end if; @@ -280,7 +280,7 @@ package body Alire.Index is if Use_Equivalences and then Aliases.Contains (Dep.Crate) then for Release of Aliases (Dep.Crate) loop if Release.Satisfies (Dep) - and then (not Available or else Release.Is_Available (Env)) + and then (not Available_Only or else Release.Is_Available (Env)) then Result.Include (Release); end if; diff --git a/src/alire/alire-index.ads b/src/alire/alire-index.ads index 2165515c..4d7a49a7 100644 --- a/src/alire/alire-index.ads +++ b/src/alire/alire-index.ads @@ -94,7 +94,7 @@ package Alire.Index is function Releases_Satisfying (Dep : Dependencies.Dependency; Env : Properties.Vector; Use_Equivalences : Boolean := True; - Available : Boolean := True) + Available_Only : Boolean := True) return Releases.Containers.Release_Set; -- Return all releases in the catalog able to provide this dependency, -- also optionally considering their "provides" equivalences, and also diff --git a/src/alire/alire-releases-containers.adb b/src/alire/alire-releases-containers.adb index cd94736d..4354b572 100644 --- a/src/alire/alire-releases-containers.adb +++ b/src/alire/alire-releases-containers.adb @@ -15,28 +15,24 @@ package body Alire.Releases.Containers is or else (for some Rel of This => Rel.Provides (Crate))); - ----------------------- - -- Element_Providing -- - ----------------------- + ------------------------ + -- Elements_Providing -- + ------------------------ - function Element_Providing (This : Release_Map; - Crate : Crate_Name) - return Releases.Release + function Elements_Providing (This : Release_Map'Class; + Crate : Crate_Name) + return Release_Set is + Result : Release_Set; begin - if This.Contains (Crate) then - return This (Crate); - else - for Rel of This loop - if Rel.Provides (Crate) then - return Rel; - end if; - end loop; - end if; + for Rel of This loop + if Rel.Provides (Crate) then + Result.Include (Rel); + end if; + end loop; - raise Constraint_Error with Errors.Set - ("Requested crate not in map: " & Crate.As_String); - end Element_Providing; + return Result; + end Elements_Providing; ------------ -- Insert -- diff --git a/src/alire/alire-releases-containers.ads b/src/alire/alire-releases-containers.ads index cac8ca5d..f3041cec 100644 --- a/src/alire/alire-releases-containers.ads +++ b/src/alire/alire-releases-containers.ads @@ -70,12 +70,12 @@ package Alire.Releases.Containers is function Contains_Or_Provides (This : Release_Map; Crate : Crate_Name) return Boolean; - -- Say if either the crate is a direct member, or provided by one of the - -- stored releases. + -- Say if either the crate is a direct member, or provided by one or more + -- of the stored releases. - function Element_Providing (This : Release_Map; - Crate : Crate_Name) - return Releases.Release + function Elements_Providing (This : Release_Map'Class; + Crate : Crate_Name) + return Release_Set with Pre => This.Contains_Or_Provides (Crate); -- Returns the release that is or provides Crate diff --git a/src/alire/alire-releases.ads b/src/alire/alire-releases.ads index 40134b89..a9148144 100644 --- a/src/alire/alire-releases.ads +++ b/src/alire/alire-releases.ads @@ -126,7 +126,7 @@ package Alire.Releases is function Forbidden (R : Release; P : Alire.Properties.Vector) - return Conditional.Dependencies; + return Conditional.Forbidden_Dependencies; -- Get platform-specific forbidden dependencies function Notes (R : Release) return Description_String; @@ -441,7 +441,7 @@ private function Forbidden (R : Release; P : Alire.Properties.Vector) - return Conditional.Dependencies + return Conditional.Forbidden_Dependencies is (R.Forbidden.Evaluate (P)); function Properties (R : Release) return Conditional.Properties diff --git a/src/alire/alire-roots-editable.adb b/src/alire/alire-roots-editable.adb index 78da98bd..9187716e 100644 --- a/src/alire/alire-roots-editable.adb +++ b/src/alire/alire-roots-editable.adb @@ -140,7 +140,7 @@ package body Alire.Roots.Editable is Alire.Manifest.Append (Crate_File (This.Edit), Dep); This.Reload_Manifest; - This.Edit.Set (This.Solution.Depending_On (Dep)); + This.Edit.Set (This.Solution.Missing (Dep)); end; end Add_Dependency; diff --git a/src/alire/alire-solutions.adb b/src/alire/alire-solutions.adb index f82ed3b0..e6ddc45f 100644 --- a/src/alire/alire-solutions.adb +++ b/src/alire/alire-solutions.adb @@ -102,7 +102,8 @@ package body Alire.Solutions is function Depends_On_Specific_GNAT (This : Solution) return Boolean is (This.Releases.Contains_Or_Provides (GNAT_Crate) and then - This.Releases.Element_Providing (GNAT_Crate).Name /= GNAT_Crate); + (for some Rel of This.Releases.Elements_Providing (GNAT_Crate) => + Rel.Name /= GNAT_Crate)); ---------------------------- -- Empty_Invalid_Solution -- @@ -436,14 +437,21 @@ package body Alire.Solutions is Result := Result.Depending_On (Release.To_Dependency.Value); end if; - -- Mark dependency solved and store its release - - Result.Dependencies := - Result.Dependencies.Including - (Result.State (Dep_Name) - .Solving (Release.Whenever (Env), - Shared => Shared)); - -- TODO: remove this Whenever once dynamic expr can be exported + -- Mark dependency solved and store its release. We double check here + -- that the release actually is adequate for the dependency. + + if Release.Satisfies (Result.State (Dep_Name).As_Dependency) then + Result.Dependencies := + Result.Dependencies.Including + (Result.State (Dep_Name).Solving + (Release.Whenever (Env), + Shared => Shared)); + -- TODO: remove this Whenever once dynamic expr can be exported + elsif Result.State (Dep_Name).Is_Hinted then + Result := Result.Hinting (Result.State (Dep_Name).As_Dependency); + else + Result := Result.Missing (Result.State (Dep_Name).As_Dependency); + end if; -- In addition, mark as solved other deps satisfied via provides @@ -487,10 +495,13 @@ package body Alire.Solutions is for Rel of This.Releases loop if Than.Contains_Release (Rel.Name) then - if Than.Release_Providing (Rel.Name).Version < Rel.Version then + if Than.Releases_Providing (Rel.Name) + .First_Element.Version < Rel.Version + then return Better; elsif - Rel.Version < Than.Release_Providing (Rel.Name).Version + Rel.Version < Than.Releases_Providing (Rel.Name) + .First_Element.Version then return Worse; end if; @@ -1087,50 +1098,60 @@ package body Alire.Solutions is end return; end Releases; - -------------------------- - -- Dependency_Providing -- - -------------------------- + ---------------------------- + -- Dependencies_Providing -- + ---------------------------- - function Dependency_Providing (This : Solution; - Crate : Crate_Name) - return States.State + function Dependencies_Providing (This : Solution; + Crate : Crate_Name) + return State_Map is + Result : State_Map; begin for Dep of This.Dependencies loop if Dep.Has_Release and then Dep.Release.Provides (Crate) then - return Dep; + Result.Insert (Dep.Crate, Dep); end if; end loop; - raise Program_Error with "Should not be reached due to preconditions"; - end Dependency_Providing; + return Result; + end Dependencies_Providing; - ----------------------- - -- Release_Providing -- - ----------------------- + ------------------------ + -- Releases_Providing -- + ------------------------ - function Release_Providing (This : Solution; + function Releases_Providing (This : Solution; Crate : Crate_Name) - return Alire.Releases.Release - is (This.Dependency_Providing (Crate).Release); + return Alire.Releases.Containers.Release_Set + is + Result : Alire.Releases.Containers.Release_Set; + begin + for State of This.Dependencies_Providing (Crate) loop + Result.Include (State.Release); + end loop; - ----------------------- - -- Release_Providing -- - ----------------------- + return Result; + end Releases_Providing; + + ------------------------ + -- Releases_Providing -- + ------------------------ - function Release_Providing (This : Solution; - Release : Alire.Releases.Release) - return Alire.Releases.Release + function Releases_Providing (This : Solution; + Release : Alire.Releases.Release) + return Alire.Releases.Containers.Release_Set is + Result : Alire.Releases.Containers.Release_Set; begin for Rel of This.Releases loop if Rel.Provides (Release) then - return Rel; + Result.Include (Rel); end if; end loop; - raise Program_Error with "Should not be reached due to precondition"; - end Release_Providing; + return Result; + end Releases_Providing; --------- -- Set -- diff --git a/src/alire/alire-solutions.ads b/src/alire/alire-solutions.ads index ddb32573..c28158c3 100644 --- a/src/alire/alire-solutions.ads +++ b/src/alire/alire-solutions.ads @@ -80,7 +80,7 @@ package Alire.Solutions is Dep : Dependencies.Dependency) return Solution; -- Add or merge a dependency without changing its state. For a new - -- dependency, it will be marked as Missing and with Unknown transitivity. + -- dependency, it will be marked as Pending and with Unknown transitivity. function Hinting (This : Solution; Dep : Dependencies.Dependency) @@ -96,17 +96,17 @@ package Alire.Solutions is Shared : Boolean := False) return Solution with Pre => - (Add_Dependency and then not This.Provides (Release)) - xor + Add_Dependency xor (For_Dependency.Has_Element and then - This.All_Dependencies.Contains (For_Dependency.Value)); + This.All_Dependencies.Contains (For_Dependency.Value)); -- Add a release to the solution, marking its dependency as solved. Takes - -- care of adding forbidden dependencies and ensuring the Release does not - -- conflict with current solution (which would result in a Checked_Error). - -- Since from the release we can't know the actual complete dependency the - -- release is fulfilling, by default we don't create its dependency (it - -- must exist previously). Only in particular cases where we want to add - -- a dependency matching the release Add_Dependency should be true. + -- care of adding forbidden dependencies and ensuring the Release does + -- not conflict with the current solution (the Solver must check this, + -- so Program_Error otherwise). Since from the release we can't know + -- the actual complete dependency the release is fulfilling, by default + -- we don't create its dependency (it must exist previously). Only in + -- particular cases where we want to add a dependency matching the + -- release Add_Dependency should be true. function Resetting (This : Solution; Crate : Crate_Name) @@ -244,24 +244,21 @@ package Alire.Solutions is -- Check whether the solution already contains or provides a release -- equivalent to Release. - function Dependency_Providing (This : Solution; - Crate : Crate_Name) - return States.State - with Pre => This.Releases.Contains_Or_Provides (Crate); - -- Return the dependency containing the release that provides Crate - - function Release_Providing (This : Solution; - Crate : Crate_Name) - return Alire.Releases.Release - with Pre => This.Contains_Release (Crate); - - function Release_Providing (This : Solution; - Release : Alire.Releases.Release) - return Alire.Releases.Release - with Pre => This.Provides (Release); - -- Return the release already in the solution that prevents Release from - -- entering the solution, as they both provide the same crate according - -- to This.Provides + function Dependencies_Providing (This : Solution; + Crate : Crate_Name) + return State_Map; + -- Return the dependency containing the release that provides Crate (may be + -- empty). + + function Releases_Providing (This : Solution; + Crate : Crate_Name) + return Alire.Releases.Containers.Release_Set; + + function Releases_Providing (This : Solution; + Release : Alire.Releases.Release) + return Alire.Releases.Containers.Release_Set; + -- Return releases already in the solution that are equivalent to Release + -- (may be empty). function Hints (This : Solution) return Dependency_Map; -- Return undetected externals in the solution diff --git a/src/alire/alire-solver.adb b/src/alire/alire-solver.adb index 6fbff35a..3bc2638e 100644 --- a/src/alire/alire-solver.adb +++ b/src/alire/alire-solver.adb @@ -22,6 +22,7 @@ package body Alire.Solver is package Semver renames Semantic_Versioning; package TTY renames Utils.TTY; + use all type Dependencies.States.Fulfillments; use all type Dependencies.States.Transitivities; package Solution_Sets is new Ada.Containers.Indefinite_Ordered_Sets @@ -106,8 +107,8 @@ package body Alire.Solver is use Alire.Conditional.For_Dependencies; - Unavailable_Crates : Containers.Crate_Name_Sets.Set; - Unavailable_Deps : Utils.String_Sets.Set; + Unavailable_Crates : Containers.Crate_Name_Sets.Set; + Unavailable_Direct_Deps : Utils.String_Sets.Set; -- Some dependencies may be unavailable because the crate does not -- exist, the requested releases do not exist, or the intersection of -- versions is empty. In this case, we can prematurely end the search @@ -117,6 +118,10 @@ package body Alire.Solver is -- introduced by the user), or otherwise it does make sense to explore -- alternate solutions that may not require the impossible dependencies. + Unavailable_All_Deps : Utils.String_Sets.Set; + -- Still, we can keep track of indirect unsolvable deps to speed-up the + -- search by not reattempting branches that contain such a dependency. + -- On the solver internal operation: the solver recursively tries all -- possible dependency combinations, in depth-first order. This means -- that, for a given dependency, all satisfying releases are attempted @@ -228,6 +233,8 @@ package body Alire.Solver is return Conditional.No_Dependencies; end Specific_GNAT; + Result : Boolean := False; + begin -- The following checks are not guaranteed to find the proper @@ -242,19 +249,20 @@ package body Alire.Solver is if Solution.Depends_On_Specific_GNAT then -- There is already a precise gnat_xxx in the solution, that - -- we must reuse. + -- we can reuse. + + Result := + (for some Prev of Solution.Releases_Providing (GNAT_Crate) + => Prev.Name = R.Name); Trace.Debug - ("SOLVER: gnat PASS " & Boolean' - (Solution.Releases - .Element_Providing (GNAT_Crate).Name = R.Name)'Image + ("SOLVER: gnat PASS " & Result'Image & " for " & R.Milestone.TTY_Image & " due to compiler already in solution: " - & Solution.Releases.Element_Providing - (GNAT_Crate).Milestone.TTY_Image); + & Solution.Releases.Elements_Providing + (GNAT_Crate).Image_One_Line); - return Solution - .Releases.Element_Providing (GNAT_Crate).Name = R.Name; + return Result; elsif not Specific_GNAT (Remaining).Is_Empty then @@ -314,9 +322,11 @@ package body Alire.Solver is -- Check -- ----------- - procedure Check (R : Release; Is_Shared : Boolean) is + procedure Check (R : Release; + Is_Shared : Boolean; + Is_Reused : Boolean) + is use all type Origins.Kinds; - use type Release; begin -- Special compiler checks are hardcoded when the dependency is @@ -324,92 +334,19 @@ package body Alire.Solver is -- is used, unless we are forced by other dependencies to do -- something else - if R.Provides (GNAT_Crate) and then not Check_Compiler (R) then + if Dep.Crate = GNAT_Crate and then + R.Provides (GNAT_Crate) and then + not Check_Compiler (R) + then -- Reason already logged by Check_Compiler return; end if; - -- We first check that the release matches the dependency we - -- are attempting to resolve, in which case we check whether - -- it is a valid candidate by taking into account the following - -- cases: - - -- A possibility is that the dependency was already frozen - -- previously (it was a dependency of an earlierly frozen - -- release). If the frozen version also satisfied the - -- current dependency, we may continue along this branch, - -- with this dependency out of the picture. - - if Solution.Provides (R) - then - - if R /= Solution.Release_Providing (R) then - - -- This may occur when e.g., we have a system compiler in - -- the solution, which does not have provides and hence - -- cannot be detected before this point. In this case we - -- cannot add a release that also provides something - -- in the solution, so we have to discard this branch. - - Trace.Debug - ("SOLVER: discarding tree because of " & - "conflicting FROZEN release: " & - Solution.Release_Providing (R).Milestone.TTY_Image & - " already provides same crate as target release: " & - R.Milestone.TTY_Image & " for dependency " & - Dep.Image & " in tree " & - Tree'(Expanded - and Target - and Remaining).Image_One_Line); - - return; - - end if; - - -- Now we may continue knowing that R is the same release - -- already in the solution for another dependency. - - if R.Satisfies (Dep) then - - Trace.Debug - ("SOLVER: reusing FROZEN release: " & - R.Milestone.Image & " to satisfy " & - Dep.Image & " in tree " & - Tree'(Expanded - and Target - and Remaining).Image_One_Line); - - -- Continue along this tree; no need to add dependencies - -- as the release was already added previously. - - Expand (Expanded => Expanded, - Target => Remaining, - Remaining => Empty, - Solution => Solution.Including - (R, Props, - For_Dependency => - Optional.Crate_Names.Unit (Dep.Crate), - Shared => - Is_Shared or else - R.Origin.Kind = Binary_Archive)); - - else - Trace.Debug - ("SOLVER: discarding tree because of " & - "conflicting FROZEN release: " & - R.Milestone.Image & " does not satisfy " & - Dep.Image & " in tree " & - Tree'(Expanded - and Target - and Remaining).Image_One_Line); - end if; - -- If the candidate release is forbidden by a previously -- resolved dependency, the candidate release is -- incompatible and we may stop search along this branch. - elsif Solution.Forbids (R, Props) - then + if Solution.Forbids (R, Props) then Trace.Debug ("SOLVER: discarding tree because of" & " FORBIDDEN release: " & @@ -433,6 +370,20 @@ package body Alire.Solver is and Target and Remaining).Image_One_Line); + -- Even if the release is OK for the dependency, we + -- agregated dependencies for the crate in the solution + -- can be another matter, so we recheck again. + + elsif not R.Satisfies (Solution.Dependency (Dep.Crate)) then + Trace.Debug + ("SOLVER: discarding search branch because " + & R.Milestone.Image & " FAILS to fulfill dep-in-solution " + & Solution.Dependency (Dep.Crate).TTY_Image + & " when the search tree was " + & Tree'(Expanded + and Target + and Remaining).Image_One_Line); + -- Or it may be that, even being a valid version, it's not for -- this environment. @@ -446,35 +397,46 @@ package body Alire.Solver is and Target and Remaining).Image_One_Line); - -- If we reached here, the release fulfills the dependency and - -- it's a first time seen, so we add it to the solution. + -- If we reached here, the release fulfills the dependency, so + -- we add it to the solution. It might still be a release that + -- fulfilled a previous dependency, so we take care of that + -- when adding its dependencies. else - Trace.Debug - ("SOLVER: dependency FROZEN: " & R.Milestone.Image & - " to satisfy " & Dep.TTY_Image & - (if Is_Shared then " with INSTALLED" else "") & - (if not R.Provides.Is_Empty - then " also providing " & R.Provides.Image_One_Line - else "") & - " adding" & - R.Dependencies (Props).Leaf_Count'Img & - " dependencies to tree " & - Tree'(Expanded - and Target - and Remaining - and R.Dependencies (Props)).Image_One_Line); + declare + -- We only need to add dependencies if it is the first + -- time we see this release. + New_Deps : constant Conditional.Platform_Dependencies := + (if Is_Reused + then Conditional.No_Dependencies + else R.Dependencies (Props)); + begin + Trace.Debug + ("SOLVER: dependency FROZEN: " & R.Milestone.Image & + " to satisfy " & Dep.TTY_Image & + (if Is_Reused then " with REUSED" else "") & + (if Is_Shared then " with INSTALLED" else "") & + (if not R.Provides.Is_Empty + then " also providing " & R.Provides.Image_One_Line + else "") & + " adding" & New_Deps.Leaf_Count'Img & + " dependencies to tree " & + Tree'(Expanded + and Target + and Remaining + and New_Deps).Image_One_Line); - Expand (Expanded => Expanded and R.To_Dependency, - Target => Remaining and R.Dependencies (Props), - Remaining => Empty, - Solution => Solution.Including - (R, Props, - For_Dependency => - Optional.Crate_Names.Unit (Dep.Crate), - Shared => - Is_Shared or else - R.Origin.Kind = Binary_Archive)); + Expand (Expanded => Expanded and R.To_Dependency, + Target => Remaining, + Remaining => New_Deps, + Solution => Solution.Including + (R, Props, + For_Dependency => + Optional.Crate_Names.Unit (Dep.Crate), + Shared => + Is_Shared or else + R.Origin.Kind = Binary_Archive)); + end; end if; end Check; @@ -488,7 +450,7 @@ package body Alire.Solver is begin if Options.Completeness > All_Complete or else Unavailable_Crates.Contains (Dep.Crate) or else - Unavailable_Deps.Contains (Dep.Image) + Unavailable_Direct_Deps.Contains (Dep.Image) then Trace.Debug @@ -580,7 +542,7 @@ package body Alire.Solver is Trace.Debug ("SOLVER short-cutting due to version pin" & " with valid release in index"); - Check (Release, Is_Shared => False); + Check (Release, Is_Shared => False, Is_Reused => False); end loop; -- There may be no satisfying releases, or even so the @@ -635,7 +597,7 @@ package body Alire.Solver is for R of reverse Installed.Satisfying (Dep) loop Satisfiable := True; - Check (R, Is_Shared => True); + Check (R, Is_Shared => True, Is_Reused => False); end loop; -- We may want still check without taking into account @@ -650,6 +612,8 @@ package body Alire.Solver is end Check_Shared; + use type Alire.Dependencies.Dependency; + begin if Pins.Depends_On (Dep.Crate) and then @@ -675,8 +639,10 @@ package body Alire.Solver is Solution => Solution.Linking (Dep.Crate, Pins.State (Dep.Crate).Link)); + return; + end if; - elsif Solution.Releases.Contains_Or_Provides (Dep.Crate) then + if not Solution.Dependencies_Providing (Dep.Crate).Is_Empty then -- Cut search once a crate is frozen, by checking the -- compatibility of the already frozen release. This will @@ -684,14 +650,20 @@ package body Alire.Solver is -- Dep, if possible, or discarding the search branch early. Trace.Debug - ("SOLVER: re-checking EXISTING release " - & Solution.Releases.Element_Providing (Dep.Crate) - .Milestone.TTY_Image + ("SOLVER: re-checking EXISTING releases " + & Solution.Releases_Providing (Dep.Crate).Image_One_Line & " for DIFFERENT dep " & Dep.TTY_Image); - Check (Solution.Releases.Element_Providing (Dep.Crate), - Is_Shared => - Solution.Dependency_Providing (Dep.Crate).Is_Shared); + for In_Sol of Solution.Dependencies_Providing (Dep.Crate) loop + if In_Sol.Has_Release then + Check (In_Sol.Release, + Is_Shared => + In_Sol.Is_Shared, + Is_Reused => True); + end if; + end loop; + + return; end if; @@ -735,7 +707,9 @@ package body Alire.Solver is -- thing from the start, which we can use to enable a partial -- solution without exploring the whole solution space: - if not Unavailable_Deps.Contains (Dep.Image) then + if not Unavailable_Direct_Deps.Contains (Dep.Image) and then + not Unavailable_All_Deps.Contains (Dep.Image) + then -- Don't bother checking what we known to not be available. -- We still want to go through to external hinting. declare @@ -744,8 +718,17 @@ package body Alire.Solver is procedure Consider (R : Release) is begin - Satisfiable := Satisfiable or else R.Satisfies (Dep); - Check (R, Is_Shared => False); + -- A GNAT release may still satisfy the dependency + -- but be not a valid candidate if uninstalled and + -- the dependency is on generic GNAT, so explicitly + -- consider this case: + + Satisfiable := Satisfiable or else + (R.Satisfies (Dep) and then + (Dep.Crate /= GNAT_Crate or else + Installed.Contains (R))); + + Check (R, Is_Shared => False, Is_Reused => False); end Consider; begin Trace.Debug ("SOLVER: considering" @@ -771,6 +754,17 @@ package body Alire.Solver is Check_Hinted; + -- If the dependency cannot be satisfied, add it to our damned + -- list for speed-up. + + if not Satisfiable and then + not Unavailable_All_Deps.Contains (Dep.Image) + then + Trace.Debug ("SOLVER: marking as unsatisfiable: " + & Dep.TTY_Image); + Unavailable_All_Deps.Include (Dep.Image); + end if; + -- There may be a less bad solution if we leave this crate out. if not Satisfiable or else Options.Completeness = All_Incomplete @@ -845,7 +839,6 @@ package body Alire.Solver is -- may force exploring all the combos of the rest of crates just -- because it doesn't exist. function Contains_All_Satisfiable return Boolean is - use all type Dependencies.States.Fulfillments; begin for Crate of Solution.Crates loop if Solution.State (Crate).Fulfilment in Missed | Hinted @@ -854,7 +847,7 @@ package body Alire.Solver is not Unavailable_Crates.Contains (Crate) -- Because it does not exist at all, so "complete" and then - not Unavailable_Deps.Contains + not Unavailable_Direct_Deps.Contains (Solution.Dependency (Crate).Image) -- Because no release fulfills it, so "complete" then @@ -892,6 +885,11 @@ package body Alire.Solver is end Store_Finished; begin + Trace.Debug ("SOLVER: EXPAND"); + Trace.Debug ("Frozen: " & Expanded.Image_One_Line); + Trace.Debug ("Target: " & Target.Image_One_Line); + Trace.Debug ("Remain: " & Remaining.Image_One_Line); + if Target.Is_Empty then -- This is a completed search branch, be the solution complete or @@ -911,6 +909,7 @@ package body Alire.Solver is Target => Remaining, Remaining => Empty, Solution => Solution); + return; end if; end if; @@ -962,12 +961,15 @@ package body Alire.Solver is Index.Detect_Externals (Dep.Value.Crate, Props); end if; + -- Regular unavailable releases + if Index.Releases_Satisfying (Dep.Value, Props).Is_Empty then - Unavailable_Deps.Include (Dep.Value.Image); + Unavailable_Direct_Deps.Include (Dep.Value.Image); Trace.Debug ("Direct dependency has no fulfilling releases: " & TTY.Name (Dep.Value.Image)); end if; + end loop; else Trace.Debug ("Alternate dependencies in tree, " diff --git a/src/alr/alr-commands-search.adb b/src/alr/alr-commands-search.adb index d6c45124..976ac3bd 100644 --- a/src/alr/alr-commands-search.adb +++ b/src/alr/alr-commands-search.adb @@ -37,6 +37,7 @@ package body Alr.Commands.Search is procedure List_Release (R : Alire.Releases.Release) is package Solver renames Alire.Solver; begin + Trace.Debug ("Listing release: " & R.Milestone.TTY_Image); if (Cmd.Prop.all = "" or else R.Property_Contains (Cmd.Prop.all) diff --git a/src/alr/alr-commands-show.adb b/src/alr/alr-commands-show.adb index ea47f238..a4dc3449 100644 --- a/src/alr/alr-commands-show.adb +++ b/src/alr/alr-commands-show.adb @@ -49,7 +49,7 @@ package body Alr.Commands.Show is (Name, Versions), Platform.Properties, Use_Equivalences => False, - Available => False)); + Available_Only => False)); Rel : constant Alire.Releases.Release := (if Candidates.Is_Empty diff --git a/testsuite/tests/solver/equivalences-conflict/test.py b/testsuite/disabled/solver/equivalences-conflict/test.py similarity index 91% rename from testsuite/tests/solver/equivalences-conflict/test.py rename to testsuite/disabled/solver/equivalences-conflict/test.py index bd8acb9e..9d51bc1c 100644 --- a/testsuite/tests/solver/equivalences-conflict/test.py +++ b/testsuite/disabled/solver/equivalences-conflict/test.py @@ -1,5 +1,6 @@ """ Test that two crates providing the same third crate are incompatible +DISABLED because this is no longer conflicting. To be revisited when "forbids" """ import subprocess diff --git a/testsuite/tests/solver/equivalences-conflict/test.yaml b/testsuite/disabled/solver/equivalences-conflict/test.yaml similarity index 100% rename from testsuite/tests/solver/equivalences-conflict/test.yaml rename to testsuite/disabled/solver/equivalences-conflict/test.yaml diff --git a/testsuite/fixtures/toolchain_index/cr/crate_virt_1/crate_virt_1-2.0.0.toml b/testsuite/fixtures/toolchain_index/cr/crate_virt_1/crate_virt_1-2.0.0.toml new file mode 100644 index 00000000..0bc89426 --- /dev/null +++ b/testsuite/fixtures/toolchain_index/cr/crate_virt_1/crate_virt_1-2.0.0.toml @@ -0,0 +1,10 @@ +description = "A crate that supplies another crate" +name = "crate_virt_1" +version = "2.0.0" +maintainers = ["alejandro@mosteo.com"] +maintainers-logins = ["mylogin"] +provides = ["crate_virtual=1.0", "crate_lone=1.0"] + +[origin] +url = "file:../../../crates/libhello_1.0.0.tgz" +hashes = ["sha512:99fa3a55540d0655c87605b54af732f76a8a363015f183b06e98aa91e54c0e69397872718c5c16f436dd6de0fba506dc50c66d34a0e5c61fb63cb01fa22f35ac"] diff --git a/testsuite/fixtures/toolchain_index/cr/crate_clash/crate_clash-1.0.0.toml b/testsuite/fixtures/toolchain_index/cr/crate_virt_2/crate_virt_2-1.0.0.toml similarity index 94% rename from testsuite/fixtures/toolchain_index/cr/crate_clash/crate_clash-1.0.0.toml rename to testsuite/fixtures/toolchain_index/cr/crate_virt_2/crate_virt_2-1.0.0.toml index 6463f7d3..1a704077 100644 --- a/testsuite/fixtures/toolchain_index/cr/crate_clash/crate_clash-1.0.0.toml +++ b/testsuite/fixtures/toolchain_index/cr/crate_virt_2/crate_virt_2-1.0.0.toml @@ -1,5 +1,5 @@ description = "A crate that supplies another crate" -name = "crate_clash" +name = "crate_virt_2" version = "1.0.0" maintainers = ["alejandro@mosteo.com"] maintainers-logins = ["mylogin"] diff --git a/testsuite/tests/pin/missing-version/test.py b/testsuite/tests/pin/missing-version/test.py index 137eb9b4..cca3d027 100644 --- a/testsuite/tests/pin/missing-version/test.py +++ b/testsuite/tests/pin/missing-version/test.py @@ -34,10 +34,12 @@ assert_match('.*Dependencies \(solution\):\n' # xxx=0.0.0 -> hello=5 (missing) alr_pin('hello', version='5') -# Check solution is as expected +# Check solution is as expected. Depending on the solver options and +# optimizations, this may show as hello=5.0.0 or hello(=5.0.0&>0), hence the +# permissive regex p = run_alr('with', '--solve') assert_match('.*Dependencies \(external\):\n' - ' hello\(=5\.0\.0\).*', + ' hello.*=5\.0\.0.*', p.out, flags=re.S) diff --git a/testsuite/tests/solver/provides-no-conflict/test.py b/testsuite/tests/solver/provides-no-conflict/test.py new file mode 100644 index 00000000..0c37f185 --- /dev/null +++ b/testsuite/tests/solver/provides-no-conflict/test.py @@ -0,0 +1,30 @@ +""" +Test that two crates providing the same third crate are compatible +""" + +import subprocess +import os + +from drivers.alr import run_alr, init_local_crate, alr_with +from drivers.asserts import assert_eq, assert_match, match_solution +from re import escape as e + +# This test relies on two crates in the index: +# crate_virt_1=2.0 also provides crate_virtual=1.0 +# crate_virt_2=1.0 also provides crate_virtual=1.0 + +# Verify that these crates provide the same virtual release +p = run_alr("show", "crate_virt_1") +assert_match(".*Provides: crate_virtual=1.0.0.*", p.out) +p = run_alr("show", "crate_virt_2") +assert_match(".*Provides: crate_virtual=1.0.0.*", p.out) + +init_local_crate("xxx") +alr_with("crate_virt_1") +alr_with("crate_virt_2") + +# Both crates must appear in the solution +match_solution("crate_virt_1=2.0.0 (origin: filesystem)", escape=True) +match_solution("crate_virt_2=1.0.0 (origin: filesystem)", escape=True) + +print('SUCCESS') diff --git a/testsuite/tests/solver/provides-no-conflict/test.yaml b/testsuite/tests/solver/provides-no-conflict/test.yaml new file mode 100644 index 00000000..8185c03b --- /dev/null +++ b/testsuite/tests/solver/provides-no-conflict/test.yaml @@ -0,0 +1,4 @@ +driver: python-script +indexes: + toolchain_index: + in_fixtures: true -- 2.39.5