| 1 | // Copyright (c) .NET Foundation and contributors. All rights reserved. Licensed under the Microsoft Reciprocal License. See LICENSE.TXT file in the project root for full license information. |
| 2 | |
| 3 | namespace WixToolset.Core.Burn.Bundles |
| 4 | { |
| 5 | using System; |
| 6 | using System.Collections.Generic; |
| 7 | using System.Globalization; |
| 8 | using System.Linq; |
| 9 | using WixToolset.Data; |
| 10 | using WixToolset.Data.Burn; |
| 11 | using WixToolset.Data.Symbols; |
| 12 | using WixToolset.Extensibility.Services; |
| 13 | |
| 14 | internal class OrderSearchesCommand |
| 15 | { |
| 16 | public OrderSearchesCommand(IMessaging messaging, IntermediateSection section) |
| 17 | { |
| 18 | this.Messaging = messaging; |
| 19 | this.Section = section; |
| 20 | } |
| 21 | |
| 22 | private IMessaging Messaging { get; } |
| 23 | |
| 24 | private IntermediateSection Section { get; } |
| 25 | |
| 26 | public IDictionary<string, IEnumerable<IntermediateSymbol>> ExtensionSearchSymbolsByExtensionId { get; private set; } |
| 27 | |
| 28 | public IEnumerable<ISearchFacade> OrderedSearchFacades { get; private set; } |
| 29 | |
| 30 | public void Execute() |
| 31 | { |
| 32 | this.ExtensionSearchSymbolsByExtensionId = new Dictionary<string, IEnumerable<IntermediateSymbol>>(); |
| 33 | this.OrderedSearchFacades = Array.Empty<ISearchFacade>(); |
| 34 | |
| 35 | var searchSymbols = this.Section.Symbols.OfType<WixSearchSymbol>().ToDictionary(t => t.Id.Id); |
| 36 | if (searchSymbols.Count == 0) |
| 37 | { |
| 38 | // Nothing to do! |
| 39 | return; |
| 40 | } |
| 41 | |
| 42 | var constraints = new Constraints(); |
| 43 | |
| 44 | // Add relational info to our data... |
| 45 | foreach (var searchRelationSymbol in this.Section.Symbols.OfType<WixSearchRelationSymbol>()) |
| 46 | { |
| 47 | constraints.AddConstraint(searchRelationSymbol.Id.Id, searchRelationSymbol.ParentSearchRef); |
| 48 | } |
| 49 | |
| 50 | this.FindCircularReference(constraints); |
| 51 | |
| 52 | if (this.Messaging.EncounteredError) |
| 53 | { |
| 54 | return; |
| 55 | } |
| 56 | |
| 57 | this.FlattenDependentReferences(constraints); |
| 58 | |
| 59 | // Reorder by topographical sort (https://en.wikipedia.org/wiki/Topological_sorting) |
| 60 | // We use a variation of Kahn (1962) algorithm as described in |
| 61 | // Wikipedia, with the additional criteria that start nodes are sorted |
| 62 | // lexicographically at each step to ensure a deterministic ordering |
| 63 | // based on 'after' dependencies and ID. |
| 64 | var sorter = new TopologicalSort(); |
| 65 | var sortedIds = sorter.Sort(searchSymbols.Keys, constraints); |
| 66 | |
| 67 | // Now, create the search facades with the searches in order... |
| 68 | (var orderedSearchFacades, var extensionSearchSymbolsByExtensionId) = this.OrderSearches(sortedIds, searchSymbols); |
| 69 | |
| 70 | this.OrderedSearchFacades = orderedSearchFacades; |
| 71 | this.ExtensionSearchSymbolsByExtensionId = extensionSearchSymbolsByExtensionId; |
| 72 | } |
| 73 | |
| 74 | /// <summary> |
| 75 | /// A dictionary of constraints, mapping an id to a list of ids. |
| 76 | /// </summary> |
| 77 | private class Constraints : Dictionary<string, List<string>> |
| 78 | { |
| 79 | public void AddConstraint(string id, string afterId) |
| 80 | { |
| 81 | if (!this.ContainsKey(id)) |
| 82 | { |
| 83 | this.Add(id, new List<string>()); |
| 84 | } |
| 85 | |
| 86 | // TODO: Show warning if a constraint is seen twice? |
| 87 | if (!this[id].Contains(afterId)) |
| 88 | { |
| 89 | this[id].Add(afterId); |
| 90 | } |
| 91 | } |
| 92 | |
| 93 | // TODO: Hide other Add methods? |
| 94 | } |
| 95 | |
| 96 | /// <summary> |
| 97 | /// Finds circular references in the constraints. |
| 98 | /// </summary> |
| 99 | /// <param name="constraints">Constraints to check.</param> |
| 100 | /// <remarks>This is not particularly performant, but it works.</remarks> |
| 101 | private void FindCircularReference(Constraints constraints) |
| 102 | { |
| 103 | foreach (var id in constraints.Keys) |
| 104 | { |
| 105 | var seenIds = new List<string>(); |
| 106 | |
| 107 | if (this.FindCircularReference(constraints, id, id, seenIds, out var chain)) |
| 108 | { |
| 109 | // We will show a separate message for every ID that's in |
| 110 | // the loop. We could bail after the first one, but then |
| 111 | // we wouldn't catch disjoint loops in a single run. |
| 112 | this.Messaging.Write(ErrorMessages.CircularSearchReference(chain)); |
| 113 | } |
| 114 | } |
| 115 | } |
| 116 | |
| 117 | /// <summary> |
| 118 | /// Recursive function that finds circular references in the constraints. |
| 119 | /// </summary> |
| 120 | /// <param name="constraints">Constraints to check.</param> |
| 121 | /// <param name="checkId">The identifier currently being looking for. (Fixed across a given run.)</param> |
| 122 | /// <param name="currentId">The idenifier curently being tested.</param> |
| 123 | /// <param name="seenIds">A list of identifiers seen, to ensure each identifier is only expanded once.</param> |
| 124 | /// <param name="chain">If a circular reference is found, will contain the chain of references.</param> |
| 125 | /// <returns>True if a circular reference is found, false otherwise.</returns> |
| 126 | private bool FindCircularReference(Constraints constraints, string checkId, string currentId, List<string> seenIds, out string chain) |
| 127 | { |
| 128 | chain = null; |
| 129 | if (constraints.TryGetValue(currentId, out var afterList)) |
| 130 | { |
| 131 | foreach (string afterId in afterList) |
| 132 | { |
| 133 | if (afterId == checkId) |
| 134 | { |
| 135 | chain = String.Format(CultureInfo.InvariantCulture, "{0} -> {1}", currentId, afterId); |
| 136 | return true; |
| 137 | } |
| 138 | |
| 139 | if (!seenIds.Contains(afterId)) |
| 140 | { |
| 141 | seenIds.Add(afterId); |
| 142 | if (this.FindCircularReference(constraints, checkId, afterId, seenIds, out chain)) |
| 143 | { |
| 144 | chain = String.Format(CultureInfo.InvariantCulture, "{0} -> {1}", currentId, chain); |
| 145 | return true; |
| 146 | } |
| 147 | } |
| 148 | } |
| 149 | } |
| 150 | |
| 151 | return false; |
| 152 | } |
| 153 | |
| 154 | /// <summary> |
| 155 | /// Flattens any dependency chains to simplify reordering. |
| 156 | /// </summary> |
| 157 | /// <param name="constraints"></param> |
| 158 | private void FlattenDependentReferences(Constraints constraints) |
| 159 | { |
| 160 | foreach (string id in constraints.Keys) |
| 161 | { |
| 162 | var flattenedIds = new List<string>(); |
| 163 | this.AddDependentReferences(constraints, id, flattenedIds); |
| 164 | var constraintList = constraints[id]; |
| 165 | foreach (var flattenedId in flattenedIds) |
| 166 | { |
| 167 | if (!constraintList.Contains(flattenedId)) |
| 168 | { |
| 169 | constraintList.Add(flattenedId); |
| 170 | } |
| 171 | } |
| 172 | } |
| 173 | } |
| 174 | |
| 175 | /// <summary> |
| 176 | /// Adds dependent references to a list. |
| 177 | /// </summary> |
| 178 | /// <param name="constraints"></param> |
| 179 | /// <param name="currentId"></param> |
| 180 | /// <param name="seenIds"></param> |
| 181 | private void AddDependentReferences(Constraints constraints, string currentId, List<string> seenIds) |
| 182 | { |
| 183 | if (constraints.TryGetValue(currentId, out var afterList)) |
| 184 | { |
| 185 | foreach (var afterId in afterList) |
| 186 | { |
| 187 | if (!seenIds.Contains(afterId)) |
| 188 | { |
| 189 | seenIds.Add(afterId); |
| 190 | this.AddDependentReferences(constraints, afterId, seenIds); |
| 191 | } |
| 192 | } |
| 193 | } |
| 194 | } |
| 195 | |
| 196 | /// <summary> |
| 197 | /// Reorder by topological sort |
| 198 | /// </summary> |
| 199 | /// <remarks> |
| 200 | /// We use a variation of Kahn (1962) algorithm as described in |
| 201 | /// Wikipedia (https://en.wikipedia.org/wiki/Topological_sorting), with |
| 202 | /// the additional criteria that start nodes are sorted lexicographically |
| 203 | /// at each step to ensure a deterministic ordering based on 'after' |
| 204 | /// dependencies and ID. |
| 205 | /// </remarks> |
| 206 | private class TopologicalSort |
| 207 | { |
| 208 | private readonly List<string> startIds = new List<string>(); |
| 209 | private Constraints constraints; |
| 210 | |
| 211 | /// <summary> |
| 212 | /// Reorder by topological sort |
| 213 | /// </summary> |
| 214 | /// <param name="allIds">The complete list of IDs.</param> |
| 215 | /// <param name="constraints">Constraints to use.</param> |
| 216 | /// <returns>The topologically sorted list of IDs.</returns> |
| 217 | internal List<string> Sort(IEnumerable<string> allIds, Constraints constraints) |
| 218 | { |
| 219 | this.startIds.Clear(); |
| 220 | this.CopyConstraints(constraints); |
| 221 | |
| 222 | this.FindInitialStartIds(allIds); |
| 223 | |
| 224 | // We always create a new sortedId list, because we return it |
| 225 | // to the caller and don't know what its lifetime may be. |
| 226 | var sortedIds = new List<string>(); |
| 227 | |
| 228 | while (this.startIds.Count > 0) |
| 229 | { |
| 230 | this.SortStartIds(); |
| 231 | |
| 232 | var currentId = this.startIds[0]; |
| 233 | sortedIds.Add(currentId); |
| 234 | this.startIds.RemoveAt(0); |
| 235 | |
| 236 | this.ResolveConstraint(currentId); |
| 237 | } |
| 238 | |
| 239 | return sortedIds; |
| 240 | } |
| 241 | |
| 242 | /// <summary> |
| 243 | /// Copies a Constraints set (to prevent modifying the incoming data). |
| 244 | /// </summary> |
| 245 | /// <param name="constraints">Constraints to copy.</param> |
| 246 | private void CopyConstraints(Constraints constraints) |
| 247 | { |
| 248 | this.constraints = new Constraints(); |
| 249 | foreach (var id in constraints.Keys) |
| 250 | { |
| 251 | foreach (var afterId in constraints[id]) |
| 252 | { |
| 253 | this.constraints.AddConstraint(id, afterId); |
| 254 | } |
| 255 | } |
| 256 | } |
| 257 | |
| 258 | /// <summary> |
| 259 | /// Finds initial start IDs. (Those with no constraints.) |
| 260 | /// </summary> |
| 261 | /// <param name="allIds">The complete list of IDs.</param> |
| 262 | private void FindInitialStartIds(IEnumerable<string> allIds) |
| 263 | { |
| 264 | foreach (var id in allIds) |
| 265 | { |
| 266 | if (!this.constraints.ContainsKey(id)) |
| 267 | { |
| 268 | this.startIds.Add(id); |
| 269 | } |
| 270 | } |
| 271 | } |
| 272 | |
| 273 | /// <summary> |
| 274 | /// Sorts start IDs. |
| 275 | /// </summary> |
| 276 | private void SortStartIds() |
| 277 | { |
| 278 | this.startIds.Sort(); |
| 279 | } |
| 280 | |
| 281 | /// <summary> |
| 282 | /// Removes the resolved constraint and updates the list of startIds |
| 283 | /// with any now-valid (all constraints resolved) IDs. |
| 284 | /// </summary> |
| 285 | /// <param name="resolvedId">The ID to resolve from the set of constraints.</param> |
| 286 | private void ResolveConstraint(string resolvedId) |
| 287 | { |
| 288 | var newStartIds = new List<string>(); |
| 289 | |
| 290 | foreach (var id in this.constraints.Keys) |
| 291 | { |
| 292 | if (this.constraints[id].Contains(resolvedId)) |
| 293 | { |
| 294 | this.constraints[id].Remove(resolvedId); |
| 295 | |
| 296 | // If we just removed the last constraint for this |
| 297 | // ID, it is now a valid start ID. |
| 298 | if (this.constraints[id].Count == 0) |
| 299 | { |
| 300 | newStartIds.Add(id); |
| 301 | } |
| 302 | } |
| 303 | } |
| 304 | |
| 305 | foreach (var id in newStartIds) |
| 306 | { |
| 307 | this.constraints.Remove(id); |
| 308 | } |
| 309 | |
| 310 | this.startIds.AddRange(newStartIds); |
| 311 | } |
| 312 | } |
| 313 | |
| 314 | private (IEnumerable<ISearchFacade>, Dictionary<string, IEnumerable<IntermediateSymbol>>) OrderSearches(IEnumerable<string> sortedIds, Dictionary<string, WixSearchSymbol> searchSymbolDictionary) |
| 315 | { |
| 316 | var orderedSearchFacades = new List<ISearchFacade>(); |
| 317 | var extensionSearchSymbolsByExtensionId = new Dictionary<string, List<IntermediateSymbol>>(); |
| 318 | |
| 319 | // TODO: Although the WixSearch tables are defined in the Util extension, |
| 320 | // the Bundle Binder has to know all about them. We hope to revisit all |
| 321 | // of this in the 4.0 timeframe. |
| 322 | var legacySearchesById = this.Section.Symbols |
| 323 | .Where(t => t.Definition.Type == SymbolDefinitionType.WixComponentSearch || |
| 324 | t.Definition.Type == SymbolDefinitionType.WixFileSearch || |
| 325 | t.Definition.Type == SymbolDefinitionType.WixProductSearch || |
| 326 | t.Definition.Type == SymbolDefinitionType.WixRegistrySearch) |
| 327 | .ToDictionary(t => t.Id.Id); |
| 328 | var setVariablesById = this.Section.Symbols |
| 329 | .OfType<WixSetVariableSymbol>() |
| 330 | .ToDictionary(t => t.Id.Id); |
| 331 | var extensionSearchesById = this.Section.Symbols |
| 332 | .Where(t => t.Definition.HasTag(BurnConstants.BootstrapperExtensionSearchSymbolDefinitionTag)) |
| 333 | .ToDictionary(t => t.Id.Id); |
| 334 | |
| 335 | foreach (var searchId in sortedIds) |
| 336 | { |
| 337 | var searchSymbol = searchSymbolDictionary[searchId]; |
| 338 | |
| 339 | if (legacySearchesById.TryGetValue(searchId, out var specificSearchSymbol)) |
| 340 | { |
| 341 | orderedSearchFacades.Add(new LegacySearchFacade(searchSymbol, specificSearchSymbol)); |
| 342 | } |
| 343 | else if (setVariablesById.TryGetValue(searchId, out var setVariableSymbol)) |
| 344 | { |
| 345 | orderedSearchFacades.Add(new SetVariableSearchFacade(searchSymbol, setVariableSymbol)); |
| 346 | } |
| 347 | else if (extensionSearchesById.TryGetValue(searchId, out var extensionSearchSymbol)) |
| 348 | { |
| 349 | orderedSearchFacades.Add(new ExtensionSearchFacade(searchSymbol)); |
| 350 | |
| 351 | if (!extensionSearchSymbolsByExtensionId.TryGetValue(searchSymbol.BootstrapperExtensionRef, out var extensionSearchSymbols)) |
| 352 | { |
| 353 | extensionSearchSymbols = new List<IntermediateSymbol>(); |
| 354 | extensionSearchSymbolsByExtensionId[searchSymbol.BootstrapperExtensionRef] = extensionSearchSymbols; |
| 355 | } |
| 356 | extensionSearchSymbols.Add(extensionSearchSymbol); |
| 357 | } |
| 358 | else |
| 359 | { |
| 360 | this.Messaging.Write(ErrorMessages.MissingBundleSearch(searchSymbol.SourceLineNumbers, searchId)); |
| 361 | } |
| 362 | } |
| 363 | |
| 364 | return (orderedSearchFacades, extensionSearchSymbolsByExtensionId.ToDictionary(kvp => kvp.Key, kvp => (IEnumerable<IntermediateSymbol>)kvp.Value)); |
| 365 | } |
| 366 | } |
| 367 | } |