From 8985598eaaa04830f0496960a39f91650089ddca Mon Sep 17 00:00:00 2001 From: Alejandro R Mosteo Date: Wed, 30 Jun 2021 09:16:31 +0200 Subject: [PATCH] Fixed cycle detection (#764) --- src/alire/alire-releases.ads | 7 ++++ src/alire/alire-roots-editable.adb | 7 +++- src/alire/alire-roots.adb | 37 ++++++++++++------ testsuite/drivers/alr.py | 7 ++-- testsuite/tests/pin/circularity/test.py | 51 ++++++++++++++++++++++--- 5 files changed, 88 insertions(+), 21 deletions(-) diff --git a/src/alire/alire-releases.ads b/src/alire/alire-releases.ads index 5a4bd299..13088c9d 100644 --- a/src/alire/alire-releases.ads +++ b/src/alire/alire-releases.ads @@ -153,6 +153,13 @@ package Alire.Releases is -- If R.Flat_Dependencies contains Crate, that dependency will be returned, -- Empty otherwise. + function Depends_On (R : Release; + Crate : Crate_Name; + P : Alire.Properties.Vector := + Alire.Properties.No_Properties) + return Boolean + is (R.Dependency_On (Crate, P).Has_Element); + function Flat_Dependencies (R : Release; P : Alire.Properties.Vector := Alire.Properties.No_Properties) diff --git a/src/alire/alire-roots-editable.adb b/src/alire/alire-roots-editable.adb index 464fad49..99a8ee9d 100644 --- a/src/alire/alire-roots-editable.adb +++ b/src/alire/alire-roots-editable.adb @@ -251,7 +251,8 @@ package body Alire.Roots.Editable is -- check the Solution and not the top-level dependencies) requested -- to be pinned, we assume a top-level dependency on the crate would -- be wanted, and add it too. If this is not wanted, the user can - -- easily remove the dependency by hand afterwards. + -- easily remove the dependency by hand afterwards (or add it, if the + -- dependency is in the closure but not in the root crate). if not This.Solution.Depends_On (Crate) then This.Add_Dependency @@ -264,7 +265,9 @@ package body Alire.Roots.Editable is -- Remove any previous pin for this crate - This.Remove_Pin (Crate); + if Release (This.Edit).Pins.Contains (Crate) then + This.Remove_Pin (Crate); + end if; return Crate; end; diff --git a/src/alire/alire-roots.adb b/src/alire/alire-roots.adb index 6a12f55b..aa508fd8 100644 --- a/src/alire/alire-roots.adb +++ b/src/alire/alire-roots.adb @@ -291,14 +291,18 @@ package body Alire.Roots is Sol : Solutions.Solution := This.Solution; Pins_Dir : constant Any_Path := This.Pins_Dir; - Linkers : Containers.Crate_Name_Sets.Set; - -- We store here crates that contain link pins, to detect cycles + Linked : Containers.Crate_Name_Sets.Set; + -- And we use this to avoid re-processing the same link target -------------- -- Add_Pins -- -------------- - procedure Add_Pins (This : in out Roots.Root) is + procedure Add_Pins (This : in out Roots.Root; + Upstream : Containers.Crate_Name_Sets.Set) + -- Upstream contains crates that are in the linking path to this root; + -- hence attempting to link to an upstream means a cycle in the graph. + is --------------------- -- Add_Version_Pin -- @@ -334,13 +338,10 @@ package body Alire.Roots is use type User_Pins.Pin; begin - -- Store the requester of this link to be able to detect cycles, - -- and check that the requested link is not already in the list - -- of requesters (which would imply circularity). + -- If the target of this link is an upstream crate, we are + -- attempting to create a cycle. - Linkers.Include (This.Name); - - if Linkers.Contains (Crate) then + if Upstream.Contains (Crate) then Raise_Checked_Error ("Pin circularity detected when adding pin " & TTY.Name (This.Name) & " --> " & TTY.Name (Crate) @@ -374,9 +375,21 @@ package body Alire.Roots is & TTY.URL (Sol.State (Crate).Link.Image (User => True))); end if; + -- If the link target has already been seen, we do not need to + -- reprocess it + + if Linked.Contains (Crate) then + Trace.Debug ("Skipping adding of already added link target: " + & TTY.Name (Crate)); + return; + else + Linked.Insert (Crate); + end if; + -- We have a new target root to load declare + use Containers.Crate_Name_Sets; Target : constant Optional.Root := Optional.Detect_Root (Pin.Path); begin @@ -416,7 +429,8 @@ package body Alire.Roots is -- Add possible pins at the link target if Target.Is_Valid then - Add_Pins (Target.Value); + Add_Pins (Target.Value, + Upstream => Union (Upstream, To_Set (This.Name))); end if; end; @@ -480,7 +494,8 @@ package body Alire.Roots is -- Recursively add all pins from this workspace and other linked ones - Add_Pins (This); + Add_Pins (This, + Upstream => Containers.Crate_Name_Sets.To_Set (This.Name)); if Sol /= This.Solution then Solutions.Diffs.Between (This.Solution, Sol).Print diff --git a/testsuite/drivers/alr.py b/testsuite/drivers/alr.py index 25c3c604..f4da8204 100644 --- a/testsuite/drivers/alr.py +++ b/testsuite/drivers/alr.py @@ -217,7 +217,8 @@ def alr_touch_manifest(path="."): Make the lockfile older than the manifest, to ensure editions to the manifest are detected. """ - os.utime(os.path.join(path, "alire.lock"), (0, 0)) + if os.path.exists(alr_lockfile()): + os.utime(alr_lockfile(), (0, 0)) def delete_array_entry_from_manifest(array, crate, @@ -249,7 +250,7 @@ def delete_array_entry_from_manifest(array, crate, (f"Could not remove crate {crate} in lines:\n" + str(orig)) # Make the lockfile "older" (otherwise timestamp is identical) - os.utime(alr_lockfile(), (0, 0)) + alr_touch_manifest() def alr_unpin(crate, manual=True, fail_if_missing=True, update=True): @@ -303,7 +304,7 @@ def alr_pin(crate, version="", path="", url="", commit="", branch="", manifest.writelines(["\n[[pins]]\n", pin_line + "\n"]) # Make the lockfile "older" (otherwise timestamp is identical) - os.utime(alr_lockfile(), (0, 0)) + alr_touch_manifest() if update: return run_alr("pin") # so the changes in the manifest are applied diff --git a/testsuite/tests/pin/circularity/test.py b/testsuite/tests/pin/circularity/test.py index c1f1dc0d..c9462c18 100644 --- a/testsuite/tests/pin/circularity/test.py +++ b/testsuite/tests/pin/circularity/test.py @@ -2,7 +2,7 @@ Verify pin circularity detection """ -from drivers.alr import run_alr, alr_pin, alr_unpin, init_local_crate +from drivers.alr import run_alr, alr_pin, alr_unpin, alr_with, init_local_crate from drivers.asserts import assert_eq, assert_match from drivers.helpers import on_windows, dir_separator @@ -25,23 +25,64 @@ os.chdir("..") # back to top-level shutil.rmtree("xxx") # and restart from scratch # Prepare a cycle +init_local_crate("xxx", enter=False) init_local_crate("yyy", enter=False) init_local_crate("zzz") -alr_pin("yyy", path="../yyy", update=False) +alr_pin("xxx", path="../xxx", update=False) os.chdir("..") os.chdir("yyy") alr_pin("zzz", path="../zzz", update=False) os.chdir("..") -init_local_crate("xxx") +os.chdir("xxx") alr_pin("yyy", path="../yyy", update=False) -# At this point, xxx --> yyy --> zzz --> yyy +# At this point, xxx --> yyy --> zzz --> xxx p = run_alr("pin", complain_on_error=False) s = re.escape(dir_separator()) assert_match( ".*" - "ERROR: Pin circularity detected when adding pin zzz --> yyy:\n" + "ERROR: Pin circularity detected when adding pin zzz --> xxx:\n" f"ERROR: Last manifest in the cycle is .*{s}zzz{s}alire.toml\n", p.out) +# Verify that the buggy case that was reported does not happen again +# In this case, we have +# dep1 -> dep2 -> dep3 -> dep4; dep1 -> dep3; dep1 -> dep4; dep2 -> dep4 + +init_local_crate("dep4", enter=False) + +init_local_crate("dep3") +alr_with("dep4", path="../dep4") + +os.chdir("..") +init_local_crate("dep2") +alr_with("dep3", path="../dep3") +alr_with("dep4", path="../dep4") + +os.chdir("..") +init_local_crate("dep1") +alr_with("dep2", path="../dep2") +alr_with("dep3", path="../dep3") +alr_with("dep4", path="../dep4") + +p = run_alr("with", "--solve") +assert_eq("""\ +Dependencies (direct): + dep2* + dep3* + dep4* +Dependencies (solution): + dep2=0.0.0 (pinned) (origin: ../dep2) + dep3=0.0.0 (pinned) (origin: ../dep3) + dep4=0.0.0 (pinned) (origin: ../dep4) +Dependencies (graph): + dep1=0.0.0 --> dep2=0.0.0 (*) + dep1=0.0.0 --> dep3=0.0.0 (*) + dep1=0.0.0 --> dep4=0.0.0 (*) + dep2=0.0.0 --> dep3=0.0.0 (*) + dep2=0.0.0 --> dep4=0.0.0 (*) + dep3=0.0.0 --> dep4=0.0.0 (*) +""", + p.out) + print('SUCCESS') -- 2.39.5