1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 package org.eclipse.jetty.start.graph;
20
21 import java.io.FileNotFoundException;
22 import java.io.IOException;
23 import java.util.ArrayList;
24 import java.util.Arrays;
25 import java.util.Collection;
26 import java.util.Collections;
27 import java.util.HashMap;
28 import java.util.HashSet;
29 import java.util.Iterator;
30 import java.util.LinkedHashMap;
31 import java.util.List;
32 import java.util.Map;
33 import java.util.Set;
34 import java.util.Stack;
35
36 import org.eclipse.jetty.start.Props;
37 import org.eclipse.jetty.start.StartLog;
38 import org.eclipse.jetty.start.Utils;
39
40
41
42
43
44 public abstract class Graph<T extends Node<T>> implements Iterable<T>
45 {
46 private String selectionTerm = "select";
47 private String nodeTerm = "node";
48 private Map<String, T> nodes = new LinkedHashMap<>();
49 private int maxDepth = -1;
50
51 protected Set<String> asNameSet(Set<T> nodeSet)
52 {
53 Set<String> ret = new HashSet<>();
54 for (T node : nodeSet)
55 {
56 ret.add(node.getName());
57 }
58 return ret;
59 }
60
61 private void assertNoCycle(T node, Stack<String> refs)
62 {
63 for (T parent : node.getParentEdges())
64 {
65 if (refs.contains(parent.getName()))
66 {
67
68 StringBuilder err = new StringBuilder();
69 err.append("A cyclic reference in the ");
70 err.append(this.getClass().getSimpleName());
71 err.append(" has been detected: ");
72 for (int i = 0; i < refs.size(); i++)
73 {
74 if (i > 0)
75 {
76 err.append(" -> ");
77 }
78 err.append(refs.get(i));
79 }
80 err.append(" -> ").append(parent.getName());
81 throw new IllegalStateException(err.toString());
82 }
83
84 refs.push(parent.getName());
85 assertNoCycle(parent,refs);
86 refs.pop();
87 }
88 }
89
90 private void bfsCalculateDepth(final T node, final int depthNow)
91 {
92 int depth = depthNow + 1;
93
94
95 for (T child : node.getChildEdges())
96 {
97 child.setDepth(Math.max(depth,child.getDepth()));
98 this.maxDepth = Math.max(this.maxDepth,child.getDepth());
99 }
100
101
102 for (T child : node.getChildEdges())
103 {
104 bfsCalculateDepth(child,depth);
105 }
106 }
107
108 public void buildGraph() throws FileNotFoundException, IOException
109 {
110
111
112 List<T> nodeList = new ArrayList<>(nodes.values());
113 for (T node : nodeList)
114 {
115 for (String parentName : node.getParentNames())
116 {
117 T parent = get(parentName);
118
119 if (parent == null)
120 {
121 parent = resolveNode(parentName);
122 }
123
124 if (parent == null)
125 {
126 if (Props.hasPropertyKey(parentName))
127 {
128 StartLog.debug("Module property not expandable (yet) [%s]",parentName);
129 }
130 else
131 {
132 StartLog.warn("Module not found [%s]",parentName);
133 }
134 }
135 else
136 {
137 node.addParentEdge(parent);
138 parent.addChildEdge(node);
139 }
140 }
141
142 for (String optionalParentName : node.getOptionalParentNames())
143 {
144 T optional = get(optionalParentName);
145 if (optional == null)
146 {
147 StartLog.debug("Optional module not found [%s]",optionalParentName);
148 }
149 else if (optional.isSelected())
150 {
151 node.addParentEdge(optional);
152 optional.addChildEdge(node);
153 }
154 }
155 }
156
157
158 Stack<String> refs = new Stack<>();
159 for (T module : nodes.values())
160 {
161 refs.push(module.getName());
162 assertNoCycle(module,refs);
163 refs.pop();
164 }
165
166
167 for (T module : nodes.values())
168 {
169 if (module.getParentEdges().isEmpty())
170 {
171 bfsCalculateDepth(module,0);
172 }
173 }
174 }
175
176 public boolean containsNode(String name)
177 {
178 return nodes.containsKey(name);
179 }
180
181 public int count()
182 {
183 return nodes.size();
184 }
185
186 public void dumpSelectedTree()
187 {
188 List<T> ordered = new ArrayList<>();
189 ordered.addAll(nodes.values());
190 Collections.sort(ordered,new NodeDepthComparator());
191
192 List<T> active = getSelected();
193
194 for (T module : ordered)
195 {
196 if (active.contains(module))
197 {
198
199 String indent = toIndent(module.getDepth());
200 boolean transitive = module.matches(OnlyTransitivePredicate.INSTANCE);
201 System.out.printf("%s + %s: %s [%s]%n",indent,toCap(nodeTerm),module.getName(),transitive?"transitive":"selected");
202 }
203 }
204 }
205
206 public void dumpSelected()
207 {
208 List<T> ordered = new ArrayList<>();
209 ordered.addAll(nodes.values());
210 Collections.sort(ordered,new NodeDepthComparator());
211
212 List<T> active = getSelected();
213
214 for (T module : ordered)
215 {
216 if (active.contains(module))
217 {
218
219 boolean transitive = module.matches(OnlyTransitivePredicate.INSTANCE);
220 System.out.printf(" %3d) %-15s ",module.getDepth() + 1,module.getName());
221 if (transitive)
222 {
223 System.out.println("<transitive> ");
224 }
225 else
226 {
227 List<String> criterias = new ArrayList<>();
228 for (Selection selection : module.getSelections())
229 {
230 if (selection.isExplicit())
231 {
232 criterias.add(selection.getCriteria());
233 }
234 }
235 Collections.sort(criterias);
236 System.out.println(Utils.join(criterias,", "));
237 }
238 }
239 }
240 }
241
242 protected void findChildren(T module, Set<T> ret)
243 {
244 ret.add(module);
245 for (T child : module.getChildEdges())
246 {
247 ret.add(child);
248 }
249 }
250
251 protected void findParents(T module, Map<String, T> ret)
252 {
253 ret.put(module.getName(),module);
254 for (T parent : module.getParentEdges())
255 {
256 ret.put(parent.getName(),parent);
257 findParents(parent,ret);
258 }
259 }
260
261 public T get(String name)
262 {
263 return nodes.get(name);
264 }
265
266
267
268
269
270 public List<T> getSelected()
271 {
272 return getMatching(new AnySelectionPredicate());
273 }
274
275
276
277
278
279
280
281
282 public List<T> getMatching(Predicate predicate)
283 {
284 List<T> selected = new ArrayList<T>();
285
286 for (T node : nodes.values())
287 {
288 if (predicate.match(node))
289 {
290 selected.add(node);
291 }
292 }
293
294 Collections.sort(selected,new NodeDepthComparator());
295 return selected;
296 }
297
298 public int getMaxDepth()
299 {
300 return maxDepth;
301 }
302
303 public Set<T> getModulesAtDepth(int depth)
304 {
305 Set<T> ret = new HashSet<>();
306 for (T node : nodes.values())
307 {
308 if (node.getDepth() == depth)
309 {
310 ret.add(node);
311 }
312 }
313 return ret;
314 }
315
316 public Collection<String> getNodeNames()
317 {
318 return nodes.keySet();
319 }
320
321 public Collection<T> getNodes()
322 {
323 return nodes.values();
324 }
325
326 public String getNodeTerm()
327 {
328 return nodeTerm;
329 }
330
331 public String getSelectionTerm()
332 {
333 return selectionTerm;
334 }
335
336 @Override
337 public Iterator<T> iterator()
338 {
339 return nodes.values().iterator();
340 }
341
342 public abstract void onNodeSelected(T node);
343
344 public T register(T node)
345 {
346 StartLog.debug("Registering Node: [%s] %s",node.getName(),node);
347 nodes.put(node.getName(),node);
348 return node;
349 }
350
351 public Set<String> resolveChildNodesOf(String nodeName)
352 {
353 Set<T> ret = new HashSet<>();
354 T module = get(nodeName);
355 findChildren(module,ret);
356 return asNameSet(ret);
357 }
358
359
360
361
362
363
364
365
366 public abstract T resolveNode(String name);
367
368 public Set<String> resolveParentModulesOf(String nodeName)
369 {
370 Map<String, T> ret = new HashMap<>();
371 T node = get(nodeName);
372 findParents(node,ret);
373 return ret.keySet();
374 }
375
376 public int selectNode(Predicate nodePredicate, Selection selection)
377 {
378 int count = 0;
379 List<T> matches = getMatching(nodePredicate);
380 if (matches.isEmpty())
381 {
382 StringBuilder err = new StringBuilder();
383 err.append("WARNING: Cannot ").append(selectionTerm);
384 err.append(" requested ").append(nodeTerm);
385 err.append("s. ").append(nodePredicate);
386 err.append(" returned no matches.");
387 StartLog.warn(err.toString());
388 return count;
389 }
390
391
392 for (T node : matches)
393 {
394 count += selectNode(node,selection);
395 }
396
397 return count;
398 }
399
400 public int selectNode(String name, Selection selection)
401 {
402 int count = 0;
403 T node = get(name);
404 if (node == null)
405 {
406 StringBuilder err = new StringBuilder();
407 err.append("Cannot ").append(selectionTerm);
408 err.append(" requested ").append(nodeTerm);
409 err.append(" [").append(name).append("]: not a valid ");
410 err.append(nodeTerm).append(" name.");
411 StartLog.warn(err.toString());
412 return count;
413 }
414
415 count += selectNode(node,selection);
416
417 return count;
418 }
419
420 private int selectNode(T node, Selection selection)
421 {
422 int count = 0;
423
424 if (node.getSelections().contains(selection))
425 {
426
427 return count;
428 }
429
430 StartLog.debug("%s %s: %s (via %s)",toCap(selectionTerm),nodeTerm,node.getName(),selection);
431
432 boolean newlySelected = node.getSelections().isEmpty();
433
434
435 node.addSelection(selection);
436 if (newlySelected)
437 {
438 onNodeSelected(node);
439 }
440 count++;
441
442
443 Selection transitive = selection.asTransitive();
444 List<String> parentNames = new ArrayList<>();
445 parentNames.addAll(node.getParentNames());
446
447 count += selectNodes(parentNames,transitive);
448
449 return count;
450 }
451
452 public int selectNodes(Collection<String> names, Selection selection)
453 {
454 StartLog.debug("%s [%s] (via %s)",toCap(selectionTerm),Utils.join(names,", "),selection);
455
456 int count = 0;
457
458 for (String name : names)
459 {
460 T node = get(name);
461
462 if (node == null)
463 {
464 StartLog.debug("resolving node [%s]",name);
465 node = resolveNode(name);
466 }
467
468 if (node == null)
469 {
470 throw new GraphException("Missing referenced dependency: " + name);
471 }
472
473 count += selectNode(node.getName(),selection);
474 }
475
476 return count;
477 }
478
479 public void setNodeTerm(String nodeTerm)
480 {
481 this.nodeTerm = nodeTerm;
482 }
483
484 public void setSelectionTerm(String selectionTerm)
485 {
486 this.selectionTerm = selectionTerm;
487 }
488
489 private String toCap(String str)
490 {
491 StringBuilder cap = new StringBuilder();
492 cap.append(Character.toUpperCase(str.charAt(0)));
493 cap.append(str.substring(1));
494 return cap.toString();
495 }
496
497 private String toIndent(int depth)
498 {
499 char indent[] = new char[depth * 2];
500 Arrays.fill(indent,' ');
501 return new String(indent);
502 }
503 }