KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > eclipse > core > internal > dependencies > DependencySystem


1 /*******************************************************************************
2  * Copyright (c) 2003, 2004 IBM Corporation and others.
3  * All rights reserved. This program and the accompanying materials
4  * are made available under the terms of the Common Public License v1.0
5  * which accompanies this distribution, and is available at
6  * http://www.eclipse.org/legal/cpl-v10.html
7  *
8  * Contributors:
9  * IBM Corporation - initial API and implementation
10  *******************************************************************************/
11 package org.eclipse.core.internal.dependencies;
12
13 import java.util.*;
14
15 public class DependencySystem {
16     public class CyclicSystemException extends Exception JavaDoc {
17         private Object JavaDoc[][] cycles;
18
19         public CyclicSystemException(Object JavaDoc[][] cycles) {
20             this.cycles = cycles;
21         }
22
23         public Object JavaDoc[][] getCycles() {
24             return cycles;
25         }
26
27         public String JavaDoc getMessage() {
28             StringBuffer JavaDoc result = new StringBuffer JavaDoc();
29             for (int i = 0; i < cycles.length; i++) {
30                 result.append("{"); //$NON-NLS-1$
31 for (int j = 0; j < cycles[i].length; j++) {
32                     result.append(((ElementSet) cycles[i][j]).getId());
33                     result.append(","); //$NON-NLS-1$
34 }
35                 result.deleteCharAt(result.length() - 1);
36                 result.append("},"); //$NON-NLS-1$
37 }
38             if (result.length() > 0)
39                 result.deleteCharAt(result.length() - 1);
40             return result.toString();
41         }
42     }
43
44     public final static int SATISFACTION = 0;
45     public final static int SELECTION = 1;
46     public final static int RESOLUTION = 2;
47     public final static int UP_TO_DATE = Integer.MAX_VALUE;
48
49     private long elementCount;
50     private int mark;
51
52     private ResolutionDelta lastDelta = new ResolutionDelta();
53     private ResolutionDelta delta = new ResolutionDelta();
54     private Comparator comparator;
55
56     // id-accessible element sets collection
57 private Map elementSets = new HashMap();
58     // the policy to be used in the selection stage
59 private ISelectionPolicy selectionPolicy;
60     // should we print debug messages?
61 private boolean debug;
62
63     /**
64      * Uses a user-provided comparator for comparing versions.
65      */
66     public DependencySystem(Comparator comparator, ISelectionPolicy selectionPolicy, boolean debug) {
67         this.comparator = comparator;
68         this.selectionPolicy = selectionPolicy;
69         this.debug = debug;
70     }
71
72     public DependencySystem(Comparator comparator, ISelectionPolicy selectionPolicy) {
73         this(comparator, selectionPolicy, false);
74     }
75
76     public ElementSet getElementSet(Object JavaDoc id) {
77         ElementSet elementSet = (ElementSet) this.elementSets.get(id);
78         // create an element set for the given id if one does not exist yet
79 if (elementSet == null)
80             this.elementSets.put(id, elementSet = new ElementSet(id, this));
81         return elementSet;
82     }
83
84     public Collection discoverRoots() {
85         Collection roots = new LinkedList();
86         for (Iterator elementSetsIter = elementSets.values().iterator(); elementSetsIter.hasNext();) {
87             ElementSet elementSet = (ElementSet) elementSetsIter.next();
88             if (elementSet.isRoot())
89                 roots.add(elementSet);
90         }
91         return roots;
92     }
93
94     /**
95      * Determines which versions of each element set are resolved.
96      */
97     public ResolutionDelta resolve() throws CyclicSystemException {
98         Collection roots = discoverRoots();
99         // traverse from roots to leaves - returns leaves
100 Collection satisfied = visit(roots, new SatisfactionVisitor(SATISFACTION));
101         // traverse from leaves to roots - returns roots
102 Collection selected = visit(satisfied, new SelectionVisitor(SELECTION, this.selectionPolicy));
103         // traverse from roots to leaves - returns leaves (result is ignored)
104 visit(selected, new ResolutionVisitor(RESOLUTION));
105         this.lastDelta = this.delta;
106         this.delta = new ResolutionDelta();
107         pruneEmptySets();
108         return this.lastDelta;
109     }
110
111     // clean up any dangling element sets that were removed and are not required by anybody
112 private void pruneEmptySets() {
113         for (Iterator elementSetsIter = elementSets.values().iterator(); elementSetsIter.hasNext();) {
114             ElementSet elementSet = (ElementSet) elementSetsIter.next();
115             if (elementSet.getElementCount() == 0 && elementSet.getRequiringCount() == 0)
116                 elementSetsIter.remove();
117         }
118     }
119
120     /**
121      * Traverses a graph starting from the given element sets.
122      * Returns a set containing all leaf element sets that satisfied the visitor.
123      */
124     public Collection visit(Collection elementSets, IElementSetVisitor visitor) throws CyclicSystemException {
125         int visitCounter = 0;
126         int mark = getNewMark(visitor.getOrder());
127         if (elementSets.isEmpty())
128             return Collections.EMPTY_SET;
129         Collection leaves = new LinkedList();
130         while (!elementSets.isEmpty()) {
131             Collection nextLevel = new LinkedList();
132             // first visit all element sets in the given set
133 for (Iterator elementSetsIter = elementSets.iterator(); elementSetsIter.hasNext();) {
134                 ElementSet elementSet = (ElementSet) elementSetsIter.next();
135                 // skip if already visited
136 if (mark == elementSet.getVisitedMark())
137                     continue;
138
139                 // last time was visited it has been changed, need to recompute
140 // only a change in a previous phase causes the next phase to need to recompute
141 if (elementSet.getVisitedMark() == elementSet.getChangedMark() && visitor.getOrder() > getVisitorOrder(elementSet.getChangedMark()))
142                     elementSet.markNeedingUpdate(visitor.getOrder());
143                 boolean shouldVisit = true;
144                 for (Iterator ancestorIter = visitor.getAncestors(elementSet).iterator(); ancestorIter.hasNext();) {
145                     ElementSet ancestorNode = (ElementSet) ancestorIter.next();
146                     if (ancestorNode.getVisitedMark() != mark) {
147                         // one ancestor element set has not been visited yet - bail out
148 shouldVisit = false;
149                         break;
150                     }
151                     if (ancestorNode.getChangedMark() == mark)
152                         // ancestor has changed - we need to recompute
153 elementSet.markNeedingUpdate(visitor.getOrder());
154                 }
155                 if (!shouldVisit)
156                     continue;
157
158                 elementSet.setVisitedMark(mark);
159                 // only update if necessary
160 if (elementSet.isNeedingUpdate(visitor.getOrder()))
161                     visitor.update(elementSet);
162
163                 visitCounter++;
164
165                 if (visitor.getDescendants(elementSet).isEmpty())
166                     leaves.add(elementSet);
167                 else
168                     nextLevel.addAll(visitor.getDescendants(elementSet));
169             }
170             elementSets = nextLevel;
171         }
172         // if visited more nodes than exist in the graph, a cycle has been found
173 // XXX: is this condition enough for detecting a cycle?
174 if (visitCounter != this.elementSets.size())
175             throw new CyclicSystemException(getCycles());
176         return leaves;
177     }
178
179     // temporary hack (using ComputeNodeOrder) to find out what the cycles are
180 public Object JavaDoc[][] getCycles() {
181         // find cycles
182 ElementSet[] nodes = (ElementSet[]) elementSets.values().toArray(new ElementSet[elementSets.size()]);
183         ArrayList dependencies = new ArrayList();
184         for (int i = 0; i < nodes.length; i++)
185             for (Iterator required = nodes[i].getRequired().iterator(); required.hasNext();)
186                 dependencies.add(new Object JavaDoc[] {nodes[i], required.next()});
187         return ComputeNodeOrder.computeNodeOrder(nodes, (Object JavaDoc[][]) dependencies.toArray(new Object JavaDoc[dependencies.size()][]));
188     }
189
190     private int getVisitorOrder(int mark) {
191         return mark & 0xFF;
192     }
193
194     private int getNewMark(int order) {
195         mark = mark % 0xFF + 1;
196         return (mark << 8) + (order & 0xFF);
197     }
198
199     public void addElements(Element[] elementsToAdd) {
200         for (int i = 0; i < elementsToAdd.length; i++)
201             addElement(elementsToAdd[i]);
202     }
203
204     public void addElement(Element element) {
205         this.getElementSet(element.getId()).addElement(element);
206         this.elementCount++;
207     }
208
209     public void removeElements(Element[] elementsToRemove) {
210         for (int i = 0; i < elementsToRemove.length; i++)
211             removeElement(elementsToRemove[i]);
212     }
213
214     public void removeElement(Object JavaDoc id, Object JavaDoc versionId) {
215         ElementSet elementSet = (ElementSet) elementSets.get(id);
216         if (elementSet == null)
217             return;
218         elementSet.removeElement(versionId);
219     }
220
221     public void removeElement(Element element) {
222         ElementSet elementSet = (ElementSet) elementSets.get(element.getId());
223         if (elementSet == null)
224             return;
225         elementSet.removeElement(element);
226     }
227
228     public long getElementCount() {
229         return elementCount;
230     }
231
232     public Map getNodes() {
233         return this.elementSets;
234     }
235
236     // returns all resolved elements ordered by pre-requisites
237 public List getResolved() {
238         int mark = getNewMark(RESOLUTION);
239         Collection elementSets = discoverRoots();
240         if (elementSets.isEmpty())
241             return Collections.EMPTY_LIST;
242         final List resolved = new LinkedList();
243         while (!elementSets.isEmpty()) {
244             Collection nextLevel = new LinkedList();
245             for (Iterator elementSetsIter = elementSets.iterator(); elementSetsIter.hasNext();) {
246                 ElementSet elementSet = (ElementSet) elementSetsIter.next();
247                 // skip if already visited
248 if (mark == elementSet.getVisitedMark())
249                     continue;
250                 Collection resolvedInSet = elementSet.getResolved();
251                 // ignore node (and requiring nodes) if none of its elements are resolved
252 if (resolvedInSet.isEmpty())
253                     continue;
254                 boolean shouldVisit = true;
255                 for (Iterator ancestorIter = elementSet.getRequired().iterator(); ancestorIter.hasNext();) {
256                     ElementSet ancestorNode = (ElementSet) ancestorIter.next();
257                     if (ancestorNode.getVisitedMark() != mark) {
258                         // one ancestor element set has not been visited yet - bail out
259 shouldVisit = false;
260                         break;
261                     }
262                 }
263                 if (!shouldVisit)
264                     continue;
265                 elementSet.setVisitedMark(mark);
266                 resolved.addAll(resolvedInSet);
267                 nextLevel.addAll(elementSet.getRequiring());
268             }
269             elementSets = nextLevel;
270         }
271         return resolved;
272     }
273
274     public String JavaDoc toString() {
275         StringBuffer JavaDoc result = new StringBuffer JavaDoc();
276         for (Iterator elementSetsIter = elementSets.values().iterator(); elementSetsIter.hasNext();) {
277             ElementSet elementSet = (ElementSet) elementSetsIter.next();
278             for (Iterator elementsIter = elementSet.getAvailable().iterator(); elementsIter.hasNext();) {
279                 Element element = (Element) elementsIter.next();
280                 result.append(element + ": " + Arrays.asList(element.getDependencies())); //$NON-NLS-1$
281 result.append(',');
282             }
283             result.deleteCharAt(result.length() - 1);
284             result.append('\n');
285         }
286         return result.toString();
287     }
288
289     void recordElementStatusChanged(Element element, int kind) {
290         this.delta.recordChange(element, kind);
291     }
292
293     void recordDependencyChanged(Collection oldResolved, Collection newResolved) {
294         for (Iterator oldResolvedIter = oldResolved.iterator(); oldResolvedIter.hasNext();) {
295             Element element = (Element) oldResolvedIter.next();
296             if (!newResolved.contains(element))
297                 this.delta.recordChange(element, ElementChange.UNRESOLVED);
298         }
299         for (Iterator newResolvedIter = newResolved.iterator(); newResolvedIter.hasNext();) {
300             Element element = (Element) newResolvedIter.next();
301             if (!oldResolved.contains(element))
302                 this.delta.recordChange(element, ElementChange.RESOLVED);
303         }
304     }
305
306     public Element getElement(Object JavaDoc id, Object JavaDoc versionId) {
307         ElementSet elementSet = (ElementSet) elementSets.get(id);
308         if (elementSet == null)
309             return null;
310         return elementSet.getElement(versionId);
311     }
312
313     // factory method
314 public Element createElement(Object JavaDoc id, Object JavaDoc versionId, Dependency[] dependencies, boolean singleton, Object JavaDoc userObject) {
315         return new Element(id, versionId, dependencies, singleton, userObject);
316     }
317
318     // factory method
319 public Dependency createDependency(Object JavaDoc requiredObjectId, IMatchRule satisfactionRule, boolean optional, Object JavaDoc userObject) {
320         return new Dependency(requiredObjectId, satisfactionRule, optional, userObject);
321     }
322
323     // global access to system version comparator
324 public int compare(Object JavaDoc obj1, Object JavaDoc obj2) {
325         return comparator.compare(obj1, obj2);
326     }
327
328     /**
329      * Returns the delta for the last resolution operation (<code>null</code> if never
330      * resolved or if last resolved with delta production disabled).
331      */
332
333     public ResolutionDelta getLastDelta() {
334         return lastDelta;
335     }
336
337     boolean inDebugMode() {
338         return debug;
339     }
340
341     public Collection getRequiringElements(Element required) {
342         ElementSet containing = getElementSet(required.getId());
343         return containing.getRequiringElements(required.getVersionId());
344     }
345
346     /**
347      * Forces a set of elements to be unresolved. All dependencies the elements may
348      * have as resolved are also unresolved. Also, any elements currently depending on
349      * the given elements will NOT be automatically unresolved. No delta is generated.
350      * These changes are only temporary, and do not affect the outcome of the next
351      * resolution (besides the generated delta).
352      */
353     public void unresolve(Element[] elements) {
354         int mark = getNewMark(RESOLUTION);
355         for (int i = 0; i < elements.length; i++) {
356             ElementSet set = getElementSet(elements[i].getId());
357             if (set == null)
358                 return;
359             set.unresolve(elements[i], mark);
360         }
361     }
362 }
Popular Tags