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) --- .../ModLoading/InvalidModStateException.cs | 14 ++ .../Framework/ModLoading/ModDependencyStatus.cs | 18 +++ .../Framework/ModLoading/ModResolver.cs | 162 ++++++++++++--------- 3 files changed, 129 insertions(+), 65 deletions(-) create mode 100644 src/StardewModdingAPI/Framework/ModLoading/InvalidModStateException.cs create mode 100644 src/StardewModdingAPI/Framework/ModLoading/ModDependencyStatus.cs (limited to 'src/StardewModdingAPI/Framework/ModLoading') 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. -- cgit