001: /*
002: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
003: *
004: * Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
005: *
006: * The contents of this file are subject to the terms of either the GNU
007: * General Public License Version 2 only ("GPL") or the Common
008: * Development and Distribution License("CDDL") (collectively, the
009: * "License"). You may not use this file except in compliance with the
010: * License. You can obtain a copy of the License at
011: * http://www.netbeans.org/cddl-gplv2.html
012: * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
013: * specific language governing permissions and limitations under the
014: * License. When distributing the software, include this License Header
015: * Notice in each file and include the License file at
016: * nbbuild/licenses/CDDL-GPL-2-CP. Sun designates this
017: * particular file as subject to the "Classpath" exception as provided
018: * by Sun in the GPL Version 2 section of the License file that
019: * accompanied this code. If applicable, add the following below the
020: * License Header, with the fields enclosed by brackets [] replaced by
021: * your own identifying information:
022: * "Portions Copyrighted [year] [name of copyright owner]"
023: *
024: * Contributor(s):
025: *
026: * The Original Software is NetBeans. The Initial Developer of the Original
027: * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
028: * Microsystems, Inc. All Rights Reserved.
029: *
030: * If you wish your version of this file to be governed by only the CDDL
031: * or only the GPL Version 2, indicate your decision by adding
032: * "[Contributor] elects to include this software in this distribution
033: * under the [CDDL or GPL Version 2] license." If you do not indicate a
034: * single choice of license, a recipient has the option to distribute
035: * your version of this file under either the CDDL, the GPL Version 2 or
036: * to extend the choice of license to its licensees as provided above.
037: * However, if you add GPL Version 2 code and therefore, elected the GPL
038: * Version 2 license, then the option applies only if the new code is
039: * made subject to such option by the copyright holder.
040: */
041:
042: package org.netbeans.nbbuild;
043:
044: import java.io.File;
045: import java.io.IOException;
046: import java.io.PrintWriter;
047: import java.io.StringWriter;
048: import java.util.ArrayList;
049: import java.util.Collection;
050: import java.util.Collections;
051: import java.util.HashMap;
052: import java.util.HashSet;
053: import java.util.Iterator;
054: import java.util.LinkedList;
055: import java.util.List;
056: import java.util.Map;
057: import java.util.Set;
058: import java.util.Stack;
059: import java.util.TreeMap;
060: import org.apache.tools.ant.BuildException;
061: import org.apache.tools.ant.Project;
062: import org.apache.tools.ant.Task;
063: import org.apache.tools.ant.types.Path;
064: import org.w3c.dom.Document;
065: import org.w3c.dom.Element;
066: import org.xml.sax.InputSource;
067: import org.xml.sax.SAXException;
068:
069: /**
070: * Task to sort the list of modules in a suite by their declared build dependencies.
071: * @author Jesse Glick
072: */
073: public class SortSuiteModules extends Task {
074: private boolean sortTests;
075: private Path unsortedModules;
076:
077: /**
078: * Set a list of modules in the suite.
079: * Each entry should be a project base directory.
080: */
081: public void setUnsortedModules(Path unsortedModules) {
082: this .unsortedModules = unsortedModules;
083: }
084:
085: private String sortedModulesProperty;
086:
087: /**
088: * Set a property name in which to store a sorted path of module base directories.
089: */
090: public void setSortedModulesProperty(String sortedModulesProperty) {
091: this .sortedModulesProperty = sortedModulesProperty;
092: }
093:
094: /** Is enabled sorting test dependencies?
095: */
096: public boolean isSortTests() {
097: return sortTests;
098: }
099:
100: /** Enable or disable sorting test dependenciens. Default value is false.
101: */
102: public void setSortTests(boolean sortTests) {
103: this .sortTests = sortTests;
104: }
105:
106: public SortSuiteModules() {
107: }
108:
109: public @Override
110: void execute() throws BuildException {
111: if (unsortedModules == null) {
112: throw new BuildException("Must set unsortedModules");
113: }
114: if (sortedModulesProperty == null) {
115: throw new BuildException("Must set sortedModulesProperty");
116: }
117: Map<String, File> basedirsByCNB = new TreeMap<String, File>();
118: Map<String, List<String>> buildDeps = new HashMap<String, List<String>>();
119: for (String piece : unsortedModules.list()) {
120: File d = new File(piece);
121: File projectXml = new File(d, "nbproject"
122: + File.separatorChar + "project.xml");
123: if (!projectXml.isFile()) {
124: throw new BuildException("Cannot open " + projectXml,
125: getLocation());
126: }
127: Document doc;
128: try {
129: doc = XMLUtil.parse(new InputSource(projectXml.toURI()
130: .toString()), false, true, null, null);
131: } catch (IOException e) {
132: throw new BuildException("Error parsing " + projectXml
133: + ": " + e, e, getLocation());
134: } catch (SAXException e) {
135: throw new BuildException("Error parsing " + projectXml
136: + ": " + e, e, getLocation());
137: }
138: Element config = XMLUtil.findElement(doc
139: .getDocumentElement(), "configuration",
140: ParseProjectXml.PROJECT_NS);
141: if (config == null) {
142: throw new BuildException("Malformed project file "
143: + projectXml, getLocation());
144: }
145: Element data = ParseProjectXml.findNBMElement(config,
146: "data");
147: if (data == null) {
148: log("Skipping " + projectXml
149: + " as it does not look like a module project",
150: Project.MSG_WARN);
151: continue;
152: }
153: Element cnbEl = ParseProjectXml.findNBMElement(data,
154: "code-name-base");
155: if (cnbEl == null) {
156: throw new BuildException("Malformed project file "
157: + projectXml, getLocation());
158: }
159: String cnb = XMLUtil.findText(cnbEl);
160: basedirsByCNB.put(cnb, d);
161: List<String> deps = new LinkedList<String>();
162: Element depsEl = ParseProjectXml.findNBMElement(data,
163: "module-dependencies");
164: if (depsEl == null) {
165: throw new BuildException("Malformed project file "
166: + projectXml, getLocation());
167: }
168: for (Element dep : XMLUtil.findSubElements(depsEl)) {
169: if (ParseProjectXml.findNBMElement(dep,
170: "build-prerequisite") == null) {
171: continue;
172: }
173: Element cnbEl2 = ParseProjectXml.findNBMElement(dep,
174: "code-name-base");
175: if (cnbEl2 == null) {
176: throw new BuildException("Malformed project file "
177: + projectXml, getLocation());
178: }
179: String cnb2 = XMLUtil.findText(cnbEl2);
180: deps.add(cnb2);
181: }
182: buildDeps.put(cnb, deps);
183:
184: // create test dependencies
185: if (isSortTests()) {
186: Element testDepsEl = ParseProjectXml.findNBMElement(
187: data, "test-dependencies");
188: if (testDepsEl != null) {
189: // <test-type>
190: Iterator itTType = XMLUtil.findSubElements(
191: testDepsEl).iterator();
192: while (itTType.hasNext()) {
193: Iterator itt = XMLUtil.findSubElements(
194: (Element) itTType.next()).iterator();
195: while (itt.hasNext()) {
196: Element dep = (Element) itt.next();
197: if (ParseProjectXml.findNBMElement(dep,
198: "test") == null) {
199: continue;
200: }
201: Element cnbEl2 = ParseProjectXml
202: .findNBMElement(dep,
203: "code-name-base");
204: if (cnbEl2 == null) {
205: throw new BuildException(
206: "No cobase found for test-dependency");
207: }
208: String cnb2 = XMLUtil.findText(cnbEl2);
209: deps.add(cnb2);
210: }
211: }
212: }
213: }
214: }
215: for (List<String> deps : buildDeps.values()) {
216: deps.retainAll(basedirsByCNB.keySet());
217: }
218: Map<String, List<String>> reversedDeps = new HashMap<String, List<String>>();
219: for (Map.Entry<String, List<String>> entry : buildDeps
220: .entrySet()) {
221: for (String from : entry.getValue()) {
222: String to = entry.getKey();
223: List<String> tos = reversedDeps.get(from);
224: if (tos == null) {
225: reversedDeps.put(from,
226: tos = new ArrayList<String>());
227: }
228: tos.add(to);
229: }
230: }
231: List<String> cnbs;
232: try {
233: cnbs = topologicalSort(basedirsByCNB.keySet(), reversedDeps);
234: } catch (TopologicalSortException x) {
235: throw new BuildException(x.getMessage(), x, getLocation());
236: }
237: StringBuffer path = new StringBuffer();
238: for (String cnb : cnbs) {
239: assert basedirsByCNB.containsKey(cnb);
240: if (path.length() > 0) {
241: path.append(File.pathSeparatorChar);
242: }
243: path.append(basedirsByCNB.get(cnb).getAbsolutePath());
244: }
245: getProject().setNewProperty(sortedModulesProperty,
246: path.toString());
247: }
248:
249: // Stolen from org.openide.util.Utilities:
250: private static <T> List<T> topologicalSort(Collection<T> c,
251: Map<? super T, ? extends Collection<? extends T>> edges)
252: throws TopologicalSortException {
253: Map<T, Boolean> finished = new HashMap<T, Boolean>();
254: List<T> r = new ArrayList<T>(Math.max(c.size(), 1));
255: List<T> cRev = new ArrayList<T>(c);
256: Collections.reverse(cRev);
257:
258: Iterator<T> it = cRev.iterator();
259:
260: while (it.hasNext()) {
261: List<T> cycle = visit(it.next(), edges, finished, r);
262:
263: if (cycle != null) {
264: throw new TopologicalSortException(cRev, edges);
265: }
266: }
267:
268: Collections.reverse(r);
269: if (r.size() != c.size()) {
270: r.retainAll(c);
271: }
272:
273: return r;
274: }
275:
276: private static <T> List<T> visit(T node,
277: Map<? super T, ? extends Collection<? extends T>> edges,
278: Map<T, Boolean> finished, List<T> r) {
279: Boolean b = finished.get(node);
280:
281: //System.err.println("node=" + node + " color=" + b);
282: if (b != null) {
283: if (b.booleanValue()) {
284: return null;
285: }
286:
287: ArrayList<T> cycle = new ArrayList<T>();
288: cycle.add(node);
289: finished.put(node, null);
290:
291: return cycle;
292: }
293:
294: Collection<? extends T> e = edges.get(node);
295:
296: if (e != null) {
297: finished.put(node, Boolean.FALSE);
298:
299: Iterator<? extends T> it = e.iterator();
300:
301: while (it.hasNext()) {
302: List<T> cycle = visit(it.next(), edges, finished, r);
303:
304: if (cycle != null) {
305: if (cycle instanceof ArrayList) {
306: // if cycle instanceof ArrayList we are still in the
307: // cycle and we want to collect new members
308: if (Boolean.FALSE == finished.get(node)) {
309: // another member in the cycle
310: cycle.add(node);
311: } else {
312: // we have reached the head of the cycle
313: // do not add additional cycles anymore
314: Collections.reverse(cycle);
315:
316: // changing cycle to not be ArrayList
317: cycle = Collections.unmodifiableList(cycle);
318: }
319: }
320:
321: // mark this node as tested
322: finished.put(node, Boolean.TRUE);
323:
324: // and report an error
325: return cycle;
326: }
327: }
328: }
329:
330: finished.put(node, Boolean.TRUE);
331: r.add(node);
332:
333: return null;
334: }
335:
336: private static final class TopologicalSortException extends
337: Exception {
338: /** all vertexes */
339:
340: private Collection vertexes;
341:
342: /** map with edges */
343: private Map edges;
344:
345: /** result if called twice */
346: private Set[] result;
347:
348: /** counter to number the vertexes */
349: private int counter;
350:
351: /** vertexes sorted by increasing value of y */
352: private Stack<Vertex> dualGraph = new Stack<Vertex>();
353:
354: TopologicalSortException(Collection vertexes, Map edges) {
355: this .vertexes = vertexes;
356: this .edges = edges;
357: }
358:
359: /** Because the full sort was not possible, this methods
360: * returns the best possible substitute for it that is available.
361: *
362: * @return list of partially sorted objects, the list can be freely modified
363: */
364: public final List partialSort() {
365: Set[] all = topologicalSets();
366:
367: ArrayList<Object> res = new ArrayList<Object>(vertexes
368: .size());
369:
370: for (int i = 0; i < all.length; i++) {
371: for (Object e : all[i]) {
372: res.add(e);
373: }
374: }
375:
376: return res;
377: }
378:
379: /** The topological sort could not be finished as there
380: * are some objects that are mutually refering to each other.
381: * This methods finds such objects and partition them into
382: * separate sets. All objects in one set (transitively) refer to
383: * each other and thus prevent the sort from succeding. As
384: * there can be more of such "unsortable sets" an array
385: * of them is returned.
386: *
387: * @return array of sets that contain some of the original objects, result
388: * shall not be modified
389: */
390: public final Set[] unsortableSets() {
391: Set[] all = topologicalSets();
392:
393: ArrayList<Set> unsort = new ArrayList<Set>();
394:
395: for (int i = 0; i < all.length; i++) {
396: if ((all[i].size() > 1) || !(all[i] instanceof HashSet)) {
397: unsort.add(all[i]);
398: }
399: }
400:
401: return unsort.toArray(new Set[0]);
402: }
403:
404: @Override
405: public String getMessage() {
406: StringWriter w = new StringWriter();
407: PrintWriter pw = new PrintWriter(w);
408: printDebug(pw);
409: pw.close();
410: return w.toString();
411: }
412:
413: @Override
414: public String toString() {
415: String s = getClass().getName();
416: return s;
417: }
418:
419: private void printDebug(java.io.PrintWriter w) {
420: w.print("TopologicalSortException - Collection: "); // NOI18N
421: w.print(vertexes);
422: w.print(" with edges "); // NOI18N
423: w.print(edges);
424: w.println(" cannot be sorted"); // NOI18N
425:
426: Set[] bad = unsortableSets();
427:
428: for (int i = 0; i < bad.length; i++) {
429: w.print(" Conflict #"); // NOI18N
430: w.print(i);
431: w.print(": "); // NOI18N
432: w.println(bad[i]);
433: }
434: }
435:
436: /** Adds description why the graph cannot be sorted.
437: * @param w writer to write to
438: */
439: public @Override
440: final void printStackTrace(java.io.PrintWriter w) {
441: printDebug(w);
442: super .printStackTrace(w);
443: }
444:
445: /** Adds description why the graph cannot be sorted.
446: * @param s stream to write to
447: */
448: public @Override
449: final void printStackTrace(java.io.PrintStream s) {
450: java.io.PrintWriter w = new java.io.PrintWriter(s);
451: this .printStackTrace(w);
452: w.flush();
453: }
454:
455: /** As the full topological sort cannot be finished due to cycles
456: * in the graph this methods performs a partition topological sort.
457: * <P>
458: * First of all it identifies unsortable parts of the graph and
459: * partitions the graph into sets of original objects. Each set contains
460: * objects that are mutually unsortable (there is a cycle between them).
461: * Then the topological sort is performed again on those sets, this
462: * sort succeeds because the graph of sets is DAG (all problematic edges
463: * were only between objects now grouped inside the sets) and the
464: * result forms the return value of this method.
465: *
466: * @return array of sorted sets that contain the original objects, each
467: * object from the original collection is exactly in one set, result
468: * shall not be modified
469: */
470: public final Set[] topologicalSets() {
471: if (result != null) {
472: return result;
473: }
474:
475: HashMap<Object, Vertex> vertexInfo = new HashMap<Object, Vertex>();
476:
477: // computes value X and Y for each vertex
478: counter = 0;
479:
480: Iterator it = vertexes.iterator();
481:
482: while (it.hasNext()) {
483: constructDualGraph(counter, it.next(), vertexInfo);
484: }
485:
486: // now connect vertexes that cannot be sorted into own
487: // sets
488: // map from the original objects to
489: Map<Object, Set> objectsToSets = new HashMap<Object, Set>();
490:
491: ArrayList<Set> sets = new ArrayList<Set>();
492:
493: while (!dualGraph.isEmpty()) {
494: Vertex v = dualGraph.pop();
495:
496: if (!v.visited) {
497: Set<Object> set = new HashSet<Object>();
498: visitDualGraph(v, set);
499:
500: if ((set.size() == 1) && v.edgesFrom.contains(v)) {
501: // mark if there is a self reference and the
502: // set is only one element big, it means that there
503: // is a self cycle
504: //
505: // do not use HashSet but Collections.singleton
506: // to recognize such cycles
507: set = Collections.singleton(v.object);
508: }
509:
510: sets.add(set);
511:
512: // fill the objectsToSets mapping
513: it = set.iterator();
514:
515: while (it.hasNext()) {
516: objectsToSets.put(it.next(), set);
517: }
518: }
519: }
520:
521: // now topologically sort the sets
522: // 1. prepare the map
523: HashMap<Set, Collection<Set>> edgesBetweenSets = new HashMap<Set, Collection<Set>>();
524: it = edges.entrySet().iterator();
525:
526: while (it.hasNext()) {
527: Map.Entry entry = (Map.Entry) it.next();
528: Collection leadsTo = (Collection) entry.getValue();
529:
530: if ((leadsTo == null) || leadsTo.isEmpty()) {
531: continue;
532: }
533:
534: Set from = objectsToSets.get(entry.getKey());
535:
536: Collection<Set> setsTo = edgesBetweenSets.get(from);
537:
538: if (setsTo == null) {
539: setsTo = new ArrayList<Set>();
540: edgesBetweenSets.put(from, setsTo);
541: }
542:
543: Iterator convert = leadsTo.iterator();
544:
545: while (convert.hasNext()) {
546: Set to = objectsToSets.get(convert.next());
547:
548: if (from != to) {
549: // avoid self cycles
550: setsTo.add(to);
551: }
552: }
553: }
554:
555: // 2. do the sort
556: try {
557: List<Set> listResult = topologicalSort(sets,
558: edgesBetweenSets);
559: result = listResult.toArray(new Set[0]);
560: } catch (TopologicalSortException ex) {
561: throw new IllegalStateException("Cannot happen"); // NOI18N
562: }
563:
564: return result;
565: }
566:
567: /** Traverses the tree
568: * @param counter current value
569: * @param vertex current vertex
570: * @param vertexInfo the info
571: */
572: private Vertex constructDualGraph(int counter, Object vertex,
573: HashMap<Object, Vertex> vertexInfo) {
574: Vertex info = vertexInfo.get(vertex);
575:
576: if (info == null) {
577: info = new Vertex(vertex, counter++);
578: vertexInfo.put(vertex, info);
579: } else {
580: // already (being) processed
581: return info;
582: }
583:
584: // process children
585: Collection c = (Collection) edges.get(vertex);
586:
587: if (c != null) {
588: Iterator it = c.iterator();
589:
590: while (it.hasNext()) {
591: Vertex next = constructDualGraph(counter,
592: it.next(), vertexInfo);
593: next.edgesFrom.add(info);
594: }
595: }
596:
597: // leaving the vertex
598: info.y = counter++;
599:
600: dualGraph.push(info);
601:
602: return info;
603: }
604:
605: /** Visit dual graph. Decreasing value of Y gives the order.
606: * Number
607: *
608: * @param vertex vertex to start from
609: * @param visited list of all objects that we've been to
610: */
611: private void visitDualGraph(Vertex vertex,
612: Collection<Object> visited) {
613: if (vertex.visited) {
614: return;
615: }
616:
617: visited.add(vertex.object);
618: vertex.visited = true;
619:
620: Iterator it = vertex.edges();
621:
622: while (it.hasNext()) {
623: Vertex v = (Vertex) it.next();
624: visitDualGraph(v, visited);
625: }
626: }
627:
628: /** Represents info about a vertex in the graph. Vertexes are
629: * comparable by the value of Y, but only after the value is set,
630: * so the sort has to be done latelly.
631: */
632: private static final class Vertex implements Comparable<Vertex> {
633: /** the found object */
634:
635: public Object object;
636:
637: /** list of vertexes that point to this one */
638: public List<Vertex> edgesFrom = new ArrayList<Vertex>();
639:
640: /** the counter state when we entered the vertex */
641: public final int x;
642:
643: /** the counter when we exited the vertex */
644: public int y;
645:
646: /** already sorted, true if the edges has been sorted */
647: public boolean sorted;
648:
649: /** true if visited in dual graph */
650: public boolean visited;
651:
652: public Vertex(Object obj, int x) {
653: this .x = x;
654: this .object = obj;
655: }
656:
657: /** Iterator over edges
658: * @return iterator of Vertex items
659: */
660: public Iterator edges() {
661: if (!sorted) {
662: Collections.sort(edgesFrom);
663: sorted = true;
664: }
665:
666: return edgesFrom.iterator();
667: }
668:
669: /** Comparing based on value of Y.
670: *
671: * @param o the Object to be compared.
672: * @return a negative integer, zero, or a positive integer as this object
673: * is less than, equal to, or greater than the specified object.
674: */
675: public int compareTo(Vertex o) {
676: return o.y - y;
677: }
678: }
679:
680: }
681: }
|