diff options
5 files changed, 178 insertions, 77 deletions
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<IModMetadata> modA = this.GetMetadataForDependencyTest("Mod A"); - Mock<IModMetadata> modB = this.GetMetadataForDependencyTest("Mod B", modA); - Mock<IModMetadata> modC = this.GetMetadataForDependencyTest("Mod C", modA, modB); + Mock<IModMetadata> modB = this.GetMetadataForDependencyTest("Mod B", dependencies: new[] { "Mod A" }); + Mock<IModMetadata> 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<IModMetadata> modA = this.GetMetadataForDependencyTest("Mod A"); - Mock<IModMetadata> modB = this.GetMetadataForDependencyTest("Mod B", modA); - Mock<IModMetadata> modC = this.GetMetadataForDependencyTest("Mod C", modB); - Mock<IModMetadata> modD = this.GetMetadataForDependencyTest("Mod D", modC); + Mock<IModMetadata> modB = this.GetMetadataForDependencyTest("Mod B", dependencies: new[] { "Mod A" }); + Mock<IModMetadata> modC = this.GetMetadataForDependencyTest("Mod C", dependencies: new[] { "Mod B" }); + Mock<IModMetadata> 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<IModMetadata> modA = this.GetMetadataForDependencyTest("Mod A"); - Mock<IModMetadata> modB = this.GetMetadataForDependencyTest("Mod B", modA); - Mock<IModMetadata> modC = this.GetMetadataForDependencyTest("Mod C", modB); - Mock<IModMetadata> modD = this.GetMetadataForDependencyTest("Mod D", modC); - Mock<IModMetadata> modE = this.GetMetadataForDependencyTest("Mod E", modB); - Mock<IModMetadata> modF = this.GetMetadataForDependencyTest("Mod F", modC, modE); + Mock<IModMetadata> modB = this.GetMetadataForDependencyTest("Mod B", dependencies: new[] { "Mod A" }); + Mock<IModMetadata> modC = this.GetMetadataForDependencyTest("Mod C", dependencies: new[] { "Mod B" }); + Mock<IModMetadata> modD = this.GetMetadataForDependencyTest("Mod D", dependencies: new[] { "Mod C" }); + Mock<IModMetadata> modE = this.GetMetadataForDependencyTest("Mod E", dependencies: new[] { "Mod B" }); + Mock<IModMetadata> 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<IModMetadata> modA = this.GetMetadataForDependencyTest("Mod A"); + Mock<IModMetadata> modB = this.GetMetadataForDependencyTest("Mod B", dependencies: new[] { "Mod A" }); + Mock<IModMetadata> modC = this.GetMetadataForDependencyTest("Mod C", dependencies: new[] { "Mod B", "Mod D" }, allowStatusChange: true); + Mock<IModMetadata> modD = this.GetMetadataForDependencyTest("Mod D", dependencies: new[] { "Mod E" }, allowStatusChange: true); + Mock<IModMetadata> 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<string>()), 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<string>()), 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<string>()), 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 /// <summary>Get a randomised basic manifest.</summary> /// <param name="uniqueID">The mod's name and unique ID.</param> /// <param name="dependencies">The dependencies this mod requires.</param> - private Mock<IModMetadata> GetMetadataForDependencyTest(string uniqueID, params Mock<IModMetadata>[] dependencies) + /// <param name="allowStatusChange">Whether the code being tested is allowed to change the mod status.</param> + private Mock<IModMetadata> GetMetadataForDependencyTest(string uniqueID, string[] dependencies = null, bool allowStatusChange = false) { Mock<IModMetadata> mod = new Mock<IModMetadata>(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<ModMetadataStatus>(), It.IsAny<string>())) + .Callback<ModMetadataStatus, string>((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 +{ + /// <summary>An exception which indicates that something went seriously wrong while loading mods, and SMAPI should abort outright.</summary> + public class InvalidModStateException : Exception + { + /// <summary>Construct an instance.</summary> + /// <param name="message">The error message.</param> + /// <param name="ex">The underlying exception, if any.</param> + 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 +{ + /// <summary>The status of a given mod in the dependency-sorting algorithm.</summary> + internal enum ModDependencyStatus + { + /// <summary>The mod hasn't been visited yet.</summary> + Queued, + + /// <summary>The mod is currently being analysed as part of a dependency chain.</summary> + Checking, + + /// <summary>The mod has already been sorted.</summary> + Sorted, + + /// <summary>The mod couldn't be sorted due to a metadata issue (e.g. missing dependencies).</summary> + 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 /// <param name="mods">The mods to process.</param> public IEnumerable<IModMetadata> ProcessDependencies(IEnumerable<IModMetadata> mods) { - var unsortedMods = mods.ToList(); + mods = mods.ToArray(); var sortedMods = new Stack<IModMetadata>(); - var visitedMods = new HashSet<IModMetadata>(); - var currentChain = new List<IModMetadata>(); - 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<IModMetadata>()); - return sortedMods.Reverse().ToArray(); + return sortedMods.Reverse(); } @@ -157,73 +144,118 @@ namespace StardewModdingAPI.Framework.ModLoading ** Private methods *********/ /// <summary>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.</summary> + /// <param name="mods">The full list of mods being validated.</param> /// <param name="mod">The mod whose dependencies to process.</param> - /// <param name="visited">The mods which have been visited.</param> + /// <param name="states">The dependency state for each mod.</param> /// <param name="sortedMods">The list in which to save mods sorted by dependency order.</param> /// <param name="currentChain">The current change of mod dependencies.</param> - /// <param name="unsortedMods">The mods remaining to sort.</param> - /// <returns>Returns whether the mod can be loaded.</returns> - private bool ProcessDependencies(IModMetadata mod, HashSet<IModMetadata> visited, Stack<IModMetadata> sortedMods, List<IModMetadata> currentChain, List<IModMetadata> unsortedMods) + /// <returns>Returns the mod dependency status.</returns> + private ModDependencyStatus ProcessDependencies(IModMetadata[] mods, IModMetadata mod, IDictionary<IModMetadata, ModDependencyStatus> states, Stack<IModMetadata> sortedMods, ICollection<IModMetadata> 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<IModMetadata>(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; + } } /// <summary>Get all mod folders in a root folder, passing through empty folders as needed.</summary> 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 @@ <Compile Include="Events\GameEvents.cs" /> <Compile Include="Events\GraphicsEvents.cs" /> <Compile Include="Framework\ModLoading\IModMetadata.cs" /> + <Compile Include="Framework\ModLoading\InvalidModStateException.cs" /> + <Compile Include="Framework\ModLoading\ModDependencyStatus.cs" /> <Compile Include="Framework\ModLoading\ModMetadataStatus.cs" /> <Compile Include="Framework\ModLoading\ModResolver.cs" /> <Compile Include="Framework\ModLoading\AssemblyDefinitionResolver.cs" /> |