aboutsummaryrefslogtreecommitdiff
path: root/src/wixext/UtilBinder.cs
diff options
context:
space:
mode:
Diffstat (limited to 'src/wixext/UtilBinder.cs')
-rw-r--r--src/wixext/UtilBinder.cs347
1 files changed, 347 insertions, 0 deletions
diff --git a/src/wixext/UtilBinder.cs b/src/wixext/UtilBinder.cs
new file mode 100644
index 00000000..ef80a876
--- /dev/null
+++ b/src/wixext/UtilBinder.cs
@@ -0,0 +1,347 @@
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
3namespace WixToolset.Extensions
4{
5#if TODO_BRINGBACK_FOR_BUNDLES
6 using System;
7 using System.Collections.Generic;
8 using System.Globalization;
9 using WixToolset.Data;
10 using WixToolset.Extensibility;
11
12 /// <summary>
13 /// The binder for the WiX Toolset Utility Extension.
14 /// </summary>
15 public sealed class UtilBinder : BinderExtension
16 {
17 // TODO: When WixSearch is supported in Product, etc, we may need to call
18 // ReorderWixSearch() from each of those initializers.
19
20 // TODO: A general-purpose "reorder this table given these constraints"
21 // mechanism may end up being helpful. This could be declaratively stated
22 // in the table definitions, or exposed from the core Wix.dll and called
23 // as-needed by any extensions.
24
25 /// <summary>
26 /// Called before bundle binding occurs.
27 /// </summary>
28 public override void Initialize(Output bundle)
29 {
30 if (OutputType.Bundle == bundle.Type)
31 {
32 this.ReorderWixSearch(bundle);
33 }
34 }
35
36 /// <summary>
37 /// Reorders Any WixSearch items.
38 /// </summary>
39 /// <param name="output">Output containing the tables to process.</param>
40 private void ReorderWixSearch(Output output)
41 {
42 Table wixSearchTable = output.Tables["WixSearch"];
43 if (null == wixSearchTable || wixSearchTable.Rows.Count == 0)
44 {
45 // nothing to do!
46 return;
47 }
48
49 RowDictionary rowDictionary = new RowDictionary();
50 foreach (Row row in wixSearchTable.Rows)
51 {
52 rowDictionary.AddRow(row);
53 }
54
55 Constraints constraints = new Constraints();
56 Table wixSearchRelationTable = output.Tables["WixSearchRelation"];
57 if (null != wixSearchRelationTable && wixSearchRelationTable.Rows.Count > 0)
58 {
59 // add relational info to our data...
60 foreach (Row row in wixSearchRelationTable.Rows)
61 {
62 constraints.AddConstraint((string)row[0], (string)row[1]);
63 }
64 }
65
66 this.FindCircularReference(constraints);
67
68 if (this.Core.EncounteredError)
69 {
70 return;
71 }
72
73 this.FlattenDependentReferences(constraints);
74
75 // Reorder by topographical sort (http://en.wikipedia.org/wiki/Topological_sorting)
76 // We use a variation of Kahn (1962) algorithm as described in
77 // Wikipedia, with the additional criteria that start nodes are sorted
78 // lexicographically at each step to ensure a deterministic ordering
79 // based on 'after' dependencies and ID.
80 TopologicalSort sorter = new TopologicalSort();
81 List <string> sortedIds = sorter.Sort(rowDictionary.Keys, constraints);
82
83 // Now, re-write the table with the searches in order...
84 wixSearchTable.Rows.Clear();
85 foreach (string id in sortedIds)
86 {
87 wixSearchTable.Rows.Add(rowDictionary[id]);
88 }
89 }
90
91 /// <summary>
92 /// A dictionary of Row items, indexed by their first column.
93 /// </summary>
94 private class RowDictionary : Dictionary<string, Row>
95 {
96 public void AddRow(Row row)
97 {
98 this.Add((string)row[0], row);
99 }
100
101 // TODO: Hide other Add methods?
102 }
103
104 /// <summary>
105 /// A dictionary of constraints, mapping an id to a list of ids.
106 /// </summary>
107 private class Constraints : Dictionary<string, List<string>>
108 {
109 public void AddConstraint(string id, string afterId)
110 {
111 if (!this.ContainsKey(id))
112 {
113 this.Add(id, new List<string>());
114 }
115
116 // TODO: Show warning if a constraint is seen twice?
117 if (!this[id].Contains(afterId))
118 {
119 this[id].Add(afterId);
120 }
121 }
122
123 // TODO: Hide other Add methods?
124 }
125
126 /// <summary>
127 /// Finds circular references in the constraints.
128 /// </summary>
129 /// <param name="constraints">Constraints to check.</param>
130 /// <remarks>This is not particularly performant, but it works.</remarks>
131 private void FindCircularReference(Constraints constraints)
132 {
133 foreach (string id in constraints.Keys)
134 {
135 List<string> seenIds = new List<string>();
136 string chain = null;
137 if (FindCircularReference(constraints, id, id, seenIds, out chain))
138 {
139 // We will show a separate message for every ID that's in
140 // the loop. We could bail after the first one, but then
141 // we wouldn't catch disjoint loops in a single run.
142 this.Core.OnMessage(UtilErrors.CircularSearchReference(chain));
143 }
144 }
145 }
146
147 /// <summary>
148 /// Recursive function that finds circular references in the constraints.
149 /// </summary>
150 /// <param name="constraints">Constraints to check.</param>
151 /// <param name="checkId">The identifier currently being looking for. (Fixed across a given run.)</param>
152 /// <param name="currentId">The idenifier curently being tested.</param>
153 /// <param name="seenIds">A list of identifiers seen, to ensure each identifier is only expanded once.</param>
154 /// <param name="chain">If a circular reference is found, will contain the chain of references.</param>
155 /// <returns>True if a circular reference is found, false otherwise.</returns>
156 private bool FindCircularReference(Constraints constraints, string checkId, string currentId, List<string> seenIds, out string chain)
157 {
158 chain = null;
159 List<string> afterList = null;
160 if (constraints.TryGetValue(currentId, out afterList))
161 {
162 foreach (string afterId in afterList)
163 {
164 if (afterId == checkId)
165 {
166 chain = String.Format(CultureInfo.InvariantCulture, "{0} -> {1}", currentId, afterId);
167 return true;
168 }
169
170 if (!seenIds.Contains(afterId))
171 {
172 seenIds.Add(afterId);
173 if (FindCircularReference(constraints, checkId, afterId, seenIds, out chain))
174 {
175 chain = String.Format(CultureInfo.InvariantCulture, "{0} -> {1}", currentId, chain);
176 return true;
177 }
178 }
179 }
180 }
181
182 return false;
183 }
184
185 /// <summary>
186 /// Flattens any dependency chains to simplify reordering.
187 /// </summary>
188 /// <param name="constraints"></param>
189 private void FlattenDependentReferences(Constraints constraints)
190 {
191 foreach (string id in constraints.Keys)
192 {
193 List<string> flattenedIds = new List<string>();
194 AddDependentReferences(constraints, id, flattenedIds);
195 List<string> constraintList = constraints[id];
196 foreach (string flattenedId in flattenedIds)
197 {
198 if (!constraintList.Contains(flattenedId))
199 {
200 constraintList.Add(flattenedId);
201 }
202 }
203 }
204 }
205
206 /// <summary>
207 /// Adds dependent references to a list.
208 /// </summary>
209 /// <param name="constraints"></param>
210 /// <param name="currentId"></param>
211 /// <param name="seenIds"></param>
212 private void AddDependentReferences(Constraints constraints, string currentId, List<string> seenIds)
213 {
214 List<string> afterList = null;
215 if (constraints.TryGetValue(currentId, out afterList))
216 {
217 foreach (string afterId in afterList)
218 {
219 if (!seenIds.Contains(afterId))
220 {
221 seenIds.Add(afterId);
222 AddDependentReferences(constraints, afterId, seenIds);
223 }
224 }
225 }
226 }
227
228 /// <summary>
229 /// Reorder by topological sort
230 /// </summary>
231 /// <remarks>
232 /// We use a variation of Kahn (1962) algorithm as described in
233 /// Wikipedia (http://en.wikipedia.org/wiki/Topological_sorting), with
234 /// the additional criteria that start nodes are sorted lexicographically
235 /// at each step to ensure a deterministic ordering based on 'after'
236 /// dependencies and ID.
237 /// </remarks>
238 private class TopologicalSort
239 {
240 private List<string> startIds = new List<string>();
241 private Constraints constraints;
242
243 /// <summary>
244 /// Reorder by topological sort
245 /// </summary>
246 /// <param name="allIds">The complete list of IDs.</param>
247 /// <param name="constraints">Constraints to use.</param>
248 /// <returns>The topologically sorted list of IDs.</returns>
249 internal List<string> Sort(IEnumerable<string> allIds, Constraints constraints)
250 {
251 this.startIds.Clear();
252 this.CopyConstraints(constraints);
253
254 this.FindInitialStartIds(allIds);
255
256 // We always create a new sortedId list, because we return it
257 // to the caller and don't know what its lifetime may be.
258 List<string> sortedIds = new List<string>();
259
260 while (this.startIds.Count > 0)
261 {
262 this.SortStartIds();
263
264 string currentId = this.startIds[0];
265 sortedIds.Add(currentId);
266 this.startIds.RemoveAt(0);
267
268 this.ResolveConstraint(currentId);
269 }
270
271 return sortedIds;
272 }
273
274 /// <summary>
275 /// Copies a Constraints set (to prevent modifying the incoming data).
276 /// </summary>
277 /// <param name="constraints">Constraints to copy.</param>
278 private void CopyConstraints(Constraints constraints)
279 {
280 this.constraints = new Constraints();
281 foreach (string id in constraints.Keys)
282 {
283 foreach (string afterId in constraints[id])
284 {
285 this.constraints.AddConstraint(id, afterId);
286 }
287 }
288 }
289
290 /// <summary>
291 /// Finds initial start IDs. (Those with no constraints.)
292 /// </summary>
293 /// <param name="allIds">The complete list of IDs.</param>
294 private void FindInitialStartIds(IEnumerable<string> allIds)
295 {
296 foreach (string id in allIds)
297 {
298 if (!this.constraints.ContainsKey(id))
299 {
300 this.startIds.Add(id);
301 }
302 }
303 }
304
305 /// <summary>
306 /// Sorts start IDs.
307 /// </summary>
308 private void SortStartIds()
309 {
310 this.startIds.Sort();
311 }
312
313 /// <summary>
314 /// Removes the resolved constraint and updates the list of startIds
315 /// with any now-valid (all constraints resolved) IDs.
316 /// </summary>
317 /// <param name="resolvedId">The ID to resolve from the set of constraints.</param>
318 private void ResolveConstraint(string resolvedId)
319 {
320 List<string> newStartIds = new List<string>();
321
322 foreach (string id in constraints.Keys)
323 {
324 if (this.constraints[id].Contains(resolvedId))
325 {
326 this.constraints[id].Remove(resolvedId);
327
328 // If we just removed the last constraint for this
329 // ID, it is now a valid start ID.
330 if (0 == this.constraints[id].Count)
331 {
332 newStartIds.Add(id);
333 }
334 }
335 }
336
337 foreach (string id in newStartIds)
338 {
339 this.constraints.Remove(id);
340 }
341
342 this.startIds.AddRange(newStartIds);
343 }
344 }
345 }
346#endif
347}