From bf435c69fd70f5140eddd99fe02d3dcdae75473a Mon Sep 17 00:00:00 2001 From: Sean Hall Date: Fri, 27 Mar 2020 15:49:39 +1000 Subject: Order WixSearches in Core. --- .../Bundles/OrderSearchesCommand.cs | 303 ++++++++++++++++++++- src/test/Example.Extension/Data/example.wir | Bin 535 -> 0 bytes .../TestData/SetVariable/Simple.wxs | 2 +- 3 files changed, 295 insertions(+), 10 deletions(-) delete mode 100644 src/test/Example.Extension/Data/example.wir (limited to 'src') diff --git a/src/WixToolset.Core.Burn/Bundles/OrderSearchesCommand.cs b/src/WixToolset.Core.Burn/Bundles/OrderSearchesCommand.cs index 3f720115..874258bf 100644 --- a/src/WixToolset.Core.Burn/Bundles/OrderSearchesCommand.cs +++ b/src/WixToolset.Core.Burn/Bundles/OrderSearchesCommand.cs @@ -2,7 +2,9 @@ namespace WixToolset.Core.Burn.Bundles { + using System; using System.Collections.Generic; + using System.Globalization; using System.Linq; using WixToolset.Data; using WixToolset.Data.Burn; @@ -26,6 +28,292 @@ namespace WixToolset.Core.Burn.Bundles public IList OrderedSearchFacades { get; private set; } public void Execute() + { + this.ExtensionSearchTuplesByExtensionId = new Dictionary>(); + this.OrderedSearchFacades = new List(); + + var searchRelationTuples = this.Section.Tuples.OfType().ToList(); + var searchTuples = this.Section.Tuples.OfType().ToList(); + if (searchTuples.Count == 0) + { + // nothing to do! + return; + } + + var tupleDictionary = searchTuples.ToDictionary(t => t.Id.Id); + + var constraints = new Constraints(); + if (searchRelationTuples.Count > 0) + { + // add relational info to our data... + foreach (var searchRelationTuple in searchRelationTuples) + { + constraints.AddConstraint(searchRelationTuple.Id.Id, searchRelationTuple.ParentSearchRef); + } + } + + this.FindCircularReference(constraints); + + if (this.Messaging.EncounteredError) + { + return; + } + + this.FlattenDependentReferences(constraints); + + // Reorder by topographical sort (http://en.wikipedia.org/wiki/Topological_sorting) + // We use a variation of Kahn (1962) algorithm as described in + // Wikipedia, with the additional criteria that start nodes are sorted + // lexicographically at each step to ensure a deterministic ordering + // based on 'after' dependencies and ID. + var sorter = new TopologicalSort(); + var sortedIds = sorter.Sort(tupleDictionary.Keys, constraints); + + // Now, create the search facades with the searches in order... + this.OrderSearches(sortedIds, tupleDictionary); + } + + /// + /// A dictionary of constraints, mapping an id to a list of ids. + /// + private class Constraints : Dictionary> + { + public void AddConstraint(string id, string afterId) + { + if (!this.ContainsKey(id)) + { + this.Add(id, new List()); + } + + // TODO: Show warning if a constraint is seen twice? + if (!this[id].Contains(afterId)) + { + this[id].Add(afterId); + } + } + + // TODO: Hide other Add methods? + } + + /// + /// Finds circular references in the constraints. + /// + /// Constraints to check. + /// This is not particularly performant, but it works. + private void FindCircularReference(Constraints constraints) + { + foreach (string id in constraints.Keys) + { + var seenIds = new List(); + string chain = null; + if (this.FindCircularReference(constraints, id, id, seenIds, out chain)) + { + // We will show a separate message for every ID that's in + // the loop. We could bail after the first one, but then + // we wouldn't catch disjoint loops in a single run. + this.Messaging.Write(ErrorMessages.CircularSearchReference(chain)); + } + } + } + + /// + /// Recursive function that finds circular references in the constraints. + /// + /// Constraints to check. + /// The identifier currently being looking for. (Fixed across a given run.) + /// The idenifier curently being tested. + /// A list of identifiers seen, to ensure each identifier is only expanded once. + /// If a circular reference is found, will contain the chain of references. + /// True if a circular reference is found, false otherwise. + private bool FindCircularReference(Constraints constraints, string checkId, string currentId, List seenIds, out string chain) + { + chain = null; + if (constraints.TryGetValue(currentId, out var afterList)) + { + foreach (string afterId in afterList) + { + if (afterId == checkId) + { + chain = String.Format(CultureInfo.InvariantCulture, "{0} -> {1}", currentId, afterId); + return true; + } + + if (!seenIds.Contains(afterId)) + { + seenIds.Add(afterId); + if (this.FindCircularReference(constraints, checkId, afterId, seenIds, out chain)) + { + chain = String.Format(CultureInfo.InvariantCulture, "{0} -> {1}", currentId, chain); + return true; + } + } + } + } + + return false; + } + + /// + /// Flattens any dependency chains to simplify reordering. + /// + /// + private void FlattenDependentReferences(Constraints constraints) + { + foreach (string id in constraints.Keys) + { + var flattenedIds = new List(); + this.AddDependentReferences(constraints, id, flattenedIds); + var constraintList = constraints[id]; + foreach (var flattenedId in flattenedIds) + { + if (!constraintList.Contains(flattenedId)) + { + constraintList.Add(flattenedId); + } + } + } + } + + /// + /// Adds dependent references to a list. + /// + /// + /// + /// + private void AddDependentReferences(Constraints constraints, string currentId, List seenIds) + { + if (constraints.TryGetValue(currentId, out var afterList)) + { + foreach (var afterId in afterList) + { + if (!seenIds.Contains(afterId)) + { + seenIds.Add(afterId); + this.AddDependentReferences(constraints, afterId, seenIds); + } + } + } + } + + /// + /// Reorder by topological sort + /// + /// + /// We use a variation of Kahn (1962) algorithm as described in + /// Wikipedia (http://en.wikipedia.org/wiki/Topological_sorting), with + /// the additional criteria that start nodes are sorted lexicographically + /// at each step to ensure a deterministic ordering based on 'after' + /// dependencies and ID. + /// + private class TopologicalSort + { + private readonly List startIds = new List(); + private Constraints constraints; + + /// + /// Reorder by topological sort + /// + /// The complete list of IDs. + /// Constraints to use. + /// The topologically sorted list of IDs. + internal List Sort(IEnumerable allIds, Constraints constraints) + { + this.startIds.Clear(); + this.CopyConstraints(constraints); + + this.FindInitialStartIds(allIds); + + // We always create a new sortedId list, because we return it + // to the caller and don't know what its lifetime may be. + var sortedIds = new List(); + + while (this.startIds.Count > 0) + { + this.SortStartIds(); + + var currentId = this.startIds[0]; + sortedIds.Add(currentId); + this.startIds.RemoveAt(0); + + this.ResolveConstraint(currentId); + } + + return sortedIds; + } + + /// + /// Copies a Constraints set (to prevent modifying the incoming data). + /// + /// Constraints to copy. + private void CopyConstraints(Constraints constraints) + { + this.constraints = new Constraints(); + foreach (var id in constraints.Keys) + { + foreach (var afterId in constraints[id]) + { + this.constraints.AddConstraint(id, afterId); + } + } + } + + /// + /// Finds initial start IDs. (Those with no constraints.) + /// + /// The complete list of IDs. + private void FindInitialStartIds(IEnumerable allIds) + { + foreach (var id in allIds) + { + if (!this.constraints.ContainsKey(id)) + { + this.startIds.Add(id); + } + } + } + + /// + /// Sorts start IDs. + /// + private void SortStartIds() + { + this.startIds.Sort(); + } + + /// + /// Removes the resolved constraint and updates the list of startIds + /// with any now-valid (all constraints resolved) IDs. + /// + /// The ID to resolve from the set of constraints. + private void ResolveConstraint(string resolvedId) + { + var newStartIds = new List(); + + foreach (var id in this.constraints.Keys) + { + if (this.constraints[id].Contains(resolvedId)) + { + this.constraints[id].Remove(resolvedId); + + // If we just removed the last constraint for this + // ID, it is now a valid start ID. + if (this.constraints[id].Count == 0) + { + newStartIds.Add(id); + } + } + } + + foreach (var id in newStartIds) + { + this.constraints.Remove(id); + } + + this.startIds.AddRange(newStartIds); + } + } + + private void OrderSearches(List sortedIds, Dictionary searchTupleDictionary) { // TODO: Although the WixSearch tables are defined in the Util extension, // the Bundle Binder has to know all about them. We hope to revisit all @@ -42,22 +330,19 @@ namespace WixToolset.Core.Burn.Bundles var extensionSearchesById = this.Section.Tuples .Where(t => t.Definition.HasTag(BurnConstants.BundleExtensionSearchTupleDefinitionTag)) .ToDictionary(t => t.Id.Id); - var searchTuples = this.Section.Tuples.OfType().ToList(); - - this.ExtensionSearchTuplesByExtensionId = new Dictionary>(); - this.OrderedSearchFacades = new List(legacySearchesById.Keys.Count + setVariablesById.Keys.Count + extensionSearchesById.Keys.Count); - foreach (var searchTuple in searchTuples) + foreach (var searchId in sortedIds) { - if (legacySearchesById.TryGetValue(searchTuple.Id.Id, out var specificSearchTuple)) + var searchTuple = searchTupleDictionary[searchId]; + if (legacySearchesById.TryGetValue(searchId, out var specificSearchTuple)) { this.OrderedSearchFacades.Add(new LegacySearchFacade(searchTuple, specificSearchTuple)); } - else if (setVariablesById.TryGetValue(searchTuple.Id.Id, out var setVariableTuple)) + else if (setVariablesById.TryGetValue(searchId, out var setVariableTuple)) { this.OrderedSearchFacades.Add(new SetVariableSearchFacade(searchTuple, setVariableTuple)); } - else if (extensionSearchesById.TryGetValue(searchTuple.Id.Id, out var extensionSearchTuple)) + else if (extensionSearchesById.TryGetValue(searchId, out var extensionSearchTuple)) { this.OrderedSearchFacades.Add(new ExtensionSearchFacade(searchTuple)); @@ -70,7 +355,7 @@ namespace WixToolset.Core.Burn.Bundles } else { - this.Messaging.Write(ErrorMessages.MissingBundleSearch(searchTuple.SourceLineNumbers, searchTuple.Id.Id)); + this.Messaging.Write(ErrorMessages.MissingBundleSearch(searchTuple.SourceLineNumbers, searchId)); } } } diff --git a/src/test/Example.Extension/Data/example.wir b/src/test/Example.Extension/Data/example.wir deleted file mode 100644 index d1ee8b90..00000000 Binary files a/src/test/Example.Extension/Data/example.wir and /dev/null differ diff --git a/src/test/WixToolsetTest.CoreIntegration/TestData/SetVariable/Simple.wxs b/src/test/WixToolsetTest.CoreIntegration/TestData/SetVariable/Simple.wxs index 96c92e54..7e8f2e99 100644 --- a/src/test/WixToolsetTest.CoreIntegration/TestData/SetVariable/Simple.wxs +++ b/src/test/WixToolsetTest.CoreIntegration/TestData/SetVariable/Simple.wxs @@ -9,7 +9,7 @@ + - -- cgit v1.2.3-55-g6feb