From 2d9aefebb0991b2e942241bf509eaa98f63b4963 Mon Sep 17 00:00:00 2001 From: Jesse Plamondon-Willard Date: Sun, 14 May 2017 21:19:27 -0400 Subject: rewrite dependency logic to resolve dependency loops by disabling the affected mods (#285) --- src/StardewModdingAPI.Tests/ModResolverTests.cs | 59 ++++++-- .../ModLoading/InvalidModStateException.cs | 14 ++ .../Framework/ModLoading/ModDependencyStatus.cs | 18 +++ .../Framework/ModLoading/ModResolver.cs | 162 ++++++++++++--------- src/StardewModdingAPI/StardewModdingAPI.csproj | 2 + 5 files changed, 178 insertions(+), 77 deletions(-) create mode 100644 src/StardewModdingAPI/Framework/ModLoading/InvalidModStateException.cs create mode 100644 src/StardewModdingAPI/Framework/ModLoading/ModDependencyStatus.cs (limited to 'src') diff --git a/src/StardewModdingAPI.Tests/ModResolverTests.cs b/src/StardewModdingAPI.Tests/ModResolverTests.cs index 285c5127..1142a264 100644 --- a/src/StardewModdingAPI.Tests/ModResolverTests.cs +++ b/src/StardewModdingAPI.Tests/ModResolverTests.cs @@ -252,8 +252,8 @@ namespace StardewModdingAPI.Tests // │ │ // └─ C ─┘ Mock modA = this.GetMetadataForDependencyTest("Mod A"); - Mock modB = this.GetMetadataForDependencyTest("Mod B", modA); - Mock modC = this.GetMetadataForDependencyTest("Mod C", modA, modB); + Mock modB = this.GetMetadataForDependencyTest("Mod B", dependencies: new[] { "Mod A" }); + Mock modC = this.GetMetadataForDependencyTest("Mod C", dependencies: new[] { "Mod A", "Mod B" }); // act IModMetadata[] mods = new ModResolver().ProcessDependencies(new[] { modC.Object, modA.Object, modB.Object }).ToArray(); @@ -271,9 +271,9 @@ namespace StardewModdingAPI.Tests // arrange // A ◀── B ◀── C ◀── D Mock modA = this.GetMetadataForDependencyTest("Mod A"); - Mock modB = this.GetMetadataForDependencyTest("Mod B", modA); - Mock modC = this.GetMetadataForDependencyTest("Mod C", modB); - Mock modD = this.GetMetadataForDependencyTest("Mod D", modC); + Mock modB = this.GetMetadataForDependencyTest("Mod B", dependencies: new[] { "Mod A" }); + Mock modC = this.GetMetadataForDependencyTest("Mod C", dependencies: new[] { "Mod B" }); + Mock modD = this.GetMetadataForDependencyTest("Mod D", dependencies: new[] { "Mod C" }); // act IModMetadata[] mods = new ModResolver().ProcessDependencies(new[] { modC.Object, modA.Object, modB.Object, modD.Object }).ToArray(); @@ -295,11 +295,11 @@ namespace StardewModdingAPI.Tests // │ │ // E ◀── F Mock modA = this.GetMetadataForDependencyTest("Mod A"); - Mock modB = this.GetMetadataForDependencyTest("Mod B", modA); - Mock modC = this.GetMetadataForDependencyTest("Mod C", modB); - Mock modD = this.GetMetadataForDependencyTest("Mod D", modC); - Mock modE = this.GetMetadataForDependencyTest("Mod E", modB); - Mock modF = this.GetMetadataForDependencyTest("Mod F", modC, modE); + Mock modB = this.GetMetadataForDependencyTest("Mod B", dependencies: new[] { "Mod A" }); + Mock modC = this.GetMetadataForDependencyTest("Mod C", dependencies: new[] { "Mod B" }); + Mock modD = this.GetMetadataForDependencyTest("Mod D", dependencies: new[] { "Mod C" }); + Mock modE = this.GetMetadataForDependencyTest("Mod E", dependencies: new[] { "Mod B" }); + Mock modF = this.GetMetadataForDependencyTest("Mod F", dependencies: new[] { "Mod C", "Mod E" }); // act IModMetadata[] mods = new ModResolver().ProcessDependencies(new[] { modC.Object, modA.Object, modB.Object, modD.Object, modF.Object, modE.Object }).ToArray(); @@ -314,6 +314,32 @@ namespace StardewModdingAPI.Tests Assert.AreSame(modF.Object, mods[5], "The load order is incorrect: mod F should be last since it needs mods E and C."); } + [Test(Description = "Assert that mods with circular dependency chains are skipped, but any other mods are loaded in the correct order.")] + public void ProcessDependencies_Skips_CircularDependentMods() + { + // arrange + // A ◀── B ◀── C ──▶ D + // ▲ │ + // │ ▼ + // └──── E + Mock modA = this.GetMetadataForDependencyTest("Mod A"); + Mock modB = this.GetMetadataForDependencyTest("Mod B", dependencies: new[] { "Mod A" }); + Mock modC = this.GetMetadataForDependencyTest("Mod C", dependencies: new[] { "Mod B", "Mod D" }, allowStatusChange: true); + Mock modD = this.GetMetadataForDependencyTest("Mod D", dependencies: new[] { "Mod E" }, allowStatusChange: true); + Mock modE = this.GetMetadataForDependencyTest("Mod E", dependencies: new[] { "Mod C" }, allowStatusChange: true); + + // act + IModMetadata[] mods = new ModResolver().ProcessDependencies(new[] { modC.Object, modA.Object, modB.Object, modD.Object, modE.Object }).ToArray(); + + // assert + Assert.AreEqual(5, mods.Length, 0, "Expected to get the same number of mods input."); + Assert.AreSame(modA.Object, mods[0], "The load order is incorrect: mod A should be first since it's needed by mod B."); + Assert.AreSame(modB.Object, mods[1], "The load order is incorrect: mod B should be second since it needs mod A."); + modC.Verify(p => p.SetStatus(ModMetadataStatus.Failed, It.IsAny()), Times.Once, "Mod C was expected to fail since it's part of a dependency loop."); + modD.Verify(p => p.SetStatus(ModMetadataStatus.Failed, It.IsAny()), Times.Once, "Mod D was expected to fail since it's part of a dependency loop."); + modE.Verify(p => p.SetStatus(ModMetadataStatus.Failed, It.IsAny()), Times.Once, "Mod E was expected to fail since it's part of a dependency loop."); + } + /********* ** Private methods @@ -338,18 +364,27 @@ namespace StardewModdingAPI.Tests /// Get a randomised basic manifest. /// The mod's name and unique ID. /// The dependencies this mod requires. - private Mock GetMetadataForDependencyTest(string uniqueID, params Mock[] dependencies) + /// Whether the code being tested is allowed to change the mod status. + private Mock GetMetadataForDependencyTest(string uniqueID, string[] dependencies = null, bool allowStatusChange = false) { Mock mod = new Mock(MockBehavior.Strict); mod.Setup(p => p.Status).Returns(ModMetadataStatus.Found); + mod.Setup(p => p.DisplayName).Returns(uniqueID); mod.Setup(p => p.Manifest).Returns( this.GetRandomManifest(manifest => { manifest.Name = uniqueID; manifest.UniqueID = uniqueID; - manifest.Dependencies = dependencies.Select(p => (IManifestDependency)new ManifestDependency(p.Object.Manifest.UniqueID)).ToArray(); + manifest.Dependencies = dependencies?.Select(dependencyID => (IManifestDependency)new ManifestDependency(dependencyID)).ToArray(); }) ); + if (allowStatusChange) + { + mod + .Setup(p => p.SetStatus(It.IsAny(), It.IsAny())) + .Callback((status, message) => Console.WriteLine($"<{uniqueID} changed status: [{status}] {message}")) + .Returns(mod.Object); + } return mod; } } diff --git a/src/StardewModdingAPI/Framework/ModLoading/InvalidModStateException.cs b/src/StardewModdingAPI/Framework/ModLoading/InvalidModStateException.cs new file mode 100644 index 00000000..ab11272a --- /dev/null +++ b/src/StardewModdingAPI/Framework/ModLoading/InvalidModStateException.cs @@ -0,0 +1,14 @@ +using System; + +namespace StardewModdingAPI.Framework.ModLoading +{ + /// An exception which indicates that something went seriously wrong while loading mods, and SMAPI should abort outright. + public class InvalidModStateException : Exception + { + /// Construct an instance. + /// The error message. + /// The underlying exception, if any. + public InvalidModStateException(string message, Exception ex = null) + : base(message, ex) { } + } +} diff --git a/src/StardewModdingAPI/Framework/ModLoading/ModDependencyStatus.cs b/src/StardewModdingAPI/Framework/ModLoading/ModDependencyStatus.cs new file mode 100644 index 00000000..0774b487 --- /dev/null +++ b/src/StardewModdingAPI/Framework/ModLoading/ModDependencyStatus.cs @@ -0,0 +1,18 @@ +namespace StardewModdingAPI.Framework.ModLoading +{ + /// The status of a given mod in the dependency-sorting algorithm. + internal enum ModDependencyStatus + { + /// The mod hasn't been visited yet. + Queued, + + /// The mod is currently being analysed as part of a dependency chain. + Checking, + + /// The mod has already been sorted. + Sorted, + + /// The mod couldn't be sorted due to a metadata issue (e.g. missing dependencies). + Failed + } +} diff --git a/src/StardewModdingAPI/Framework/ModLoading/ModResolver.cs b/src/StardewModdingAPI/Framework/ModLoading/ModResolver.cs index 8efe57d9..2b081edc 100644 --- a/src/StardewModdingAPI/Framework/ModLoading/ModResolver.cs +++ b/src/StardewModdingAPI/Framework/ModLoading/ModResolver.cs @@ -130,26 +130,13 @@ namespace StardewModdingAPI.Framework.ModLoading /// The mods to process. public IEnumerable ProcessDependencies(IEnumerable mods) { - var unsortedMods = mods.ToList(); + mods = mods.ToArray(); var sortedMods = new Stack(); - var visitedMods = new HashSet(); - var currentChain = new List(); - bool success = true; - - foreach (IModMetadata mod in unsortedMods) - { - if (mod.Status == ModMetadataStatus.Failed) - continue; - - success = this.ProcessDependencies(mod, visitedMods, sortedMods, currentChain, unsortedMods); - if (!success) - break; - } - - if (!success) - return new ModMetadata[0]; + var states = mods.ToDictionary(mod => mod, mod => ModDependencyStatus.Queued); + foreach (IModMetadata mod in mods) + this.ProcessDependencies(mods.ToArray(), mod, states, sortedMods, new List()); - return sortedMods.Reverse().ToArray(); + return sortedMods.Reverse(); } @@ -157,73 +144,118 @@ namespace StardewModdingAPI.Framework.ModLoading ** Private methods *********/ /// Sort a mod's dependencies by the order they should be loaded, and remove any mods that can't be loaded due to missing or conflicting dependencies. + /// The full list of mods being validated. /// The mod whose dependencies to process. - /// The mods which have been visited. + /// The dependency state for each mod. /// The list in which to save mods sorted by dependency order. /// The current change of mod dependencies. - /// The mods remaining to sort. - /// Returns whether the mod can be loaded. - private bool ProcessDependencies(IModMetadata mod, HashSet visited, Stack sortedMods, List currentChain, List unsortedMods) + /// Returns the mod dependency status. + private ModDependencyStatus ProcessDependencies(IModMetadata[] mods, IModMetadata mod, IDictionary states, Stack sortedMods, ICollection currentChain) { - // visit mod - if (visited.Contains(mod)) - return true; // already sorted - visited.Add(mod); + // check if already visited + switch (states[mod]) + { + // already sorted or failed + case ModDependencyStatus.Sorted: + case ModDependencyStatus.Failed: + return states[mod]; - // mod already failed - if (mod.Status == ModMetadataStatus.Failed) - return false; + // dependency loop + case ModDependencyStatus.Checking: + // This should never happen. The higher-level mod checks if the dependency is + // already being checked, so it can fail without visiting a mod twice. If this + // case is hit, that logic didn't catch the dependency loop for some reason. + throw new InvalidModStateException($"A dependency loop was not caught by the calling iteration ({string.Join(" => ", currentChain.Select(p => p.DisplayName))} => {mod.DisplayName}))."); - // process dependencies - bool success = true; - if (mod.Manifest.Dependencies != null && mod.Manifest.Dependencies.Any()) + // not visited yet, start processing + case ModDependencyStatus.Queued: + break; + + // sanity check + default: + throw new InvalidModStateException($"Unknown dependency status '{states[mod]}'."); + } + + // no dependencies, mark sorted + if (mod.Manifest.Dependencies == null || !mod.Manifest.Dependencies.Any()) { - // validate required dependencies are present + sortedMods.Push(mod); + return states[mod] = ModDependencyStatus.Sorted; + } + + // missing required dependencies, mark failed + { + string[] missingModIDs = + ( + from dependency in mod.Manifest.Dependencies + where mods.All(m => m.Manifest.UniqueID != dependency.UniqueID) + orderby dependency.UniqueID + select dependency.UniqueID + ) + .ToArray(); + if (missingModIDs.Any()) { - string missingMods = null; - foreach (IManifestDependency dependency in mod.Manifest.Dependencies) - { - if (!unsortedMods.Any(m => m.Manifest.UniqueID.Equals(dependency.UniqueID))) - missingMods += $"{dependency.UniqueID}, "; - } - if (missingMods != null) - { - mod.SetStatus(ModMetadataStatus.Failed, $"it requires mods which aren't installed ({missingMods.Substring(0, missingMods.Length - 2)})."); - return false; - } + sortedMods.Push(mod); + mod.SetStatus(ModMetadataStatus.Failed, $"it requires mods which aren't installed ({string.Join(", ", missingModIDs)})."); + return states[mod] = ModDependencyStatus.Failed; } + } - // get mods which should be loaded before this one + // process dependencies + { + states[mod] = ModDependencyStatus.Checking; + + // get mods to load first IModMetadata[] modsToLoadFirst = ( - from unsorted in unsortedMods - where mod.Manifest.Dependencies.Any(required => required.UniqueID == unsorted.Manifest.UniqueID) - select unsorted + from other in mods + where mod.Manifest.Dependencies.Any(required => required.UniqueID == other.Manifest.UniqueID) + select other ) .ToArray(); - // detect circular references - IModMetadata circularReferenceMod = currentChain.FirstOrDefault(modsToLoadFirst.Contains); - if (circularReferenceMod != null) - { - mod.SetStatus(ModMetadataStatus.Failed, $"its dependencies have a circular reference: {string.Join(" => ", currentChain.Select(p => p.DisplayName))} => {circularReferenceMod.DisplayName})."); - return false; - } - currentChain.Add(mod); - // recursively sort dependencies foreach (IModMetadata requiredMod in modsToLoadFirst) { - success = this.ProcessDependencies(requiredMod, visited, sortedMods, currentChain, unsortedMods); - if (!success) - break; + var subchain = new List(currentChain) { mod }; + + // detect dependency loop + if (states[requiredMod] == ModDependencyStatus.Checking) + { + sortedMods.Push(mod); + mod.SetStatus(ModMetadataStatus.Failed, $"its dependencies have a circular reference: {string.Join(" => ", subchain.Select(p => p.DisplayName))} => {requiredMod.DisplayName})."); + return states[mod] = ModDependencyStatus.Failed; + } + + // recursively process each dependency + var substatus = this.ProcessDependencies(mods, requiredMod, states, sortedMods, subchain); + switch (substatus) + { + // sorted successfully + case ModDependencyStatus.Sorted: + break; + + // failed, which means this mod can't be loaded either + case ModDependencyStatus.Failed: + sortedMods.Push(mod); + mod.SetStatus(ModMetadataStatus.Failed, $"it needs the '{requiredMod.DisplayName}' mod, which couldn't be loaded."); + return states[mod] = ModDependencyStatus.Failed; + + // unexpected status + case ModDependencyStatus.Queued: + case ModDependencyStatus.Checking: + throw new InvalidModStateException($"Something went wrong sorting dependencies: mod '{requiredMod.DisplayName}' unexpectedly stayed in the '{substatus}' status."); + + // sanity check + default: + throw new InvalidModStateException($"Unknown dependency status '{states[mod]}'."); + } } - } - // mark mod sorted - sortedMods.Push(mod); - currentChain.Remove(mod); - return success; + // all requirements sorted successfully + sortedMods.Push(mod); + return states[mod] = ModDependencyStatus.Sorted; + } } /// Get all mod folders in a root folder, passing through empty folders as needed. diff --git a/src/StardewModdingAPI/StardewModdingAPI.csproj b/src/StardewModdingAPI/StardewModdingAPI.csproj index a7362153..61b97baa 100644 --- a/src/StardewModdingAPI/StardewModdingAPI.csproj +++ b/src/StardewModdingAPI/StardewModdingAPI.csproj @@ -122,6 +122,8 @@ + + -- cgit