001: package Schmortopf.OutputManager;
002:
003: /**
004: * This class is used by the OutputManager right before
005: * it starts the compiler.
006: * It's task is to sort all files which are going to be compiled
007: * against the number of dependencies, so that that for each input file for the
008: * compiler, the number of dependent files to be compiled
009: * is smaller.
010: * This task has no well defined result state because of
011: * cyclic dependencies in Java.
012: */
013:
014: import java.awt.*;
015: import java.awt.event.*;
016: import javax.swing.*;
017: import javax.swing.plaf.metal.*;
018: import java.io.*;
019: import java.util.*;
020:
021: import Schmortopf.Main.ProjectDefinition.ProjectDefinition;
022: import Schmortopf.Main.ProjectDefinition.ProjectDefinitionEntry;
023: import Schmortopf.Utility.*;
024: import Schmortopf.Utility.themes.*;
025: import Schmortopf.Utility.ThreadEngine.*;
026: import Schmortopf.FileStructure.*;
027: import Schmortopf.FileStructure.Descriptions.*;
028:
029: import Schmortopf.JavaSourceEditor.*;
030: import Schmortopf.JavaSourceEditor.JEditorTextPane;
031: import Schmortopf.JavaSourceEditor.CodeCompletion.CodeCompletionUtilities;
032: import Shared.Logging.Log;
033:
034: public class FileDependencySorter {
035:
036: final ProjectDefinition projectDefinition;
037:
038: private FileDependencyDescription dependencyDescriptionAnchor = null;
039: // Contains all fsds together with package and class imports of the project only
040: // It is designed as doubly linked closed list, with a nonflying anchor
041: // which is the one above.
042: // Advantage of doubly linked list above array or Vector: During move operations
043: // one must not shift maaaaany elements for filling the gap or making room for
044: // the one to insert, as its not closely related to the location in the memory.
045:
046: private String[] projectFilePathNamesToBeCompiled;
047:
048: final String projectDirectory_path;
049:
050: /**
051: * Constructor
052: */
053: public FileDependencySorter(
054: final ProjectDefinition projectDefinition,
055: final String[] projectFilePathNamesToBeCompiled,
056: final FileStructureDescriptionManager fsdManager) {
057: if (EventQueue.isDispatchThread()) {
058: Log
059: .Warn("CAUTION: FileDependencySorter is called inside the EventDispatchThread.");
060: Log.Warn("CAUTION: which is a design error.");
061: }
062:
063: this .projectDefinition = projectDefinition;
064: this .projectFilePathNamesToBeCompiled = projectFilePathNamesToBeCompiled;
065:
066: final ProjectDefinitionEntry entry = this .projectDefinition
067: .getProjectDefinitionEntry(ProjectDefinition.ProjectDirectoryPath_Key);
068: this .projectDirectory_path = (String) entry.getValue();
069:
070: // Create the linked list : The anchor has a null fsd and isnt used for sorting,
071: // Its reference can be used for getting the list start any time, cause it never
072: // is moved.
073: this .dependencyDescriptionAnchor = new FileDependencyDescription(
074: null);
075: // points to itself :
076: this .dependencyDescriptionAnchor.next = this .dependencyDescriptionAnchor;
077: this .dependencyDescriptionAnchor.previous = this .dependencyDescriptionAnchor;
078:
079: // Get the FSD's, associated to all projectfiles to compile.
080: // Because the pathname is contained in all project fsd's, we can base the order
081: // process completely on this fsd array :
082: for (int i = 0; i < projectFilePathNamesToBeCompiled.length; i++) {
083: FileStructureDescription fsd = fsdManager
084: .getFileStructureDescriptionForProjectFileWithPath(projectFilePathNamesToBeCompiled[i]);
085: // If the fsd was not found, we get into little problems. But this CAN occure.
086: // In this case, we just CREATE a help fsd, in which we only fill the
087: // required pathname. Should be best possible, cause we then at least can
088: // operate on the fsd's.
089: if (fsd == null) {
090: fsd = new FileStructureDescription();
091: fsd.pathNameBuffer.setLength(0);
092: fsd.pathNameBuffer
093: .append(projectFilePathNamesToBeCompiled[i]);
094: Log.Info("FSD is NULL for "
095: + projectFilePathNamesToBeCompiled[i]);
096: }
097: // Create a new element, add it to the closed linked list
098: // at the end (right before the anchor) and close the list again :
099: FileDependencyDescription fdd = new FileDependencyDescription(
100: fsd);
101: FileDependencyDescription insertionElement = this .dependencyDescriptionAnchor.previous;
102: // insert both backward links :
103: insertionElement.next = fdd;
104: fdd.previous = insertionElement;
105: // insert both forward links :
106: fdd.next = this .dependencyDescriptionAnchor;
107: this .dependencyDescriptionAnchor.previous = fdd;
108: } // for i
109: } // Constructor
110:
111: /**
112: * This method orders the filePathNames array, so that
113: * ANY parentclass is at a lower index than ANY of its children.
114: *
115: * It MUST be called outside the EventDispatchThread, and it will
116: * deny its work and return with an error message, if called inside.
117: *
118: */
119: public String[] orderFilePathNamesAfterDependencies() {
120: // If we have less than 3 elements, we return immediately
121: // and return the original array:
122: if (this .projectFilePathNamesToBeCompiled.length < 3) {
123: return this .projectFilePathNamesToBeCompiled;
124: }
125: // We can operate exclusively on the dependencyDescription array.
126: long startTime = System.currentTimeMillis();
127: int loopCount = 0;
128: int numberOfZeroReferenceMoves = 0;
129: int numberOfExchangements = 0;
130: int numberOfLoopOverflows = 0;
131: FileDependencyDescription currentFDD = this .dependencyDescriptionAnchor.next; // the anchor itself doesnt carry data
132: // Make one cycle through the list :
133: while (currentFDD.next != this .dependencyDescriptionAnchor) {
134: // highestReferencedFDD : 3 cases:
135: // a) An FDD != current FDD is returned -> we have a forward reference and
136: // therefore we will move the current FDD right behind the returned FDD.
137: // Note : We only move an FDD a certain amount of times, because circular
138: // references are allowed and otherwise would leed to endless loops.
139: //
140: // b) The returned FDD NULL -> No forward references
141: // -> all ok, nothing to do.
142: //
143: // c) The returned FDD is the anchor: Means that the associated FSD doesn't
144: // reference ANY other project FSD. In this case, we just move the current
145: // FDD to the anchor position, so later the compiler first will go through
146: // files, which don't reference any other project file.
147: //
148: final FileDependencyDescription highestReferencedFDD = this
149: .getHighestReferencedFDD(currentFDD);
150: if (highestReferencedFDD == this .dependencyDescriptionAnchor) {
151: // == No project related references at all, so put it to the beginning,
152: // if we are not still at the beginning.
153: // Store its next FDD, before we loose it in the move method:
154: if ((currentFDD != this .dependencyDescriptionAnchor)
155: && (currentFDD != this .dependencyDescriptionAnchor.next)) {
156: final FileDependencyDescription nextStepFDD = currentFDD.next;
157: // move :
158: this .moveFDDTo(currentFDD,
159: this .dependencyDescriptionAnchor.next);
160: currentFDD.incNumberOfMoves();
161: numberOfZeroReferenceMoves++;
162: // Take over the follower :
163: currentFDD = nextStepFDD;
164: } else {
165: currentFDD = currentFDD.next;
166: }
167: } else if (highestReferencedFDD != null) // longest forward reference
168: { // so put the currentFDD right behind that one
169: // Store its next FDD, before we loose it in the move method:
170: final FileDependencyDescription nextStepFDD = currentFDD.next;
171: // move currentFDD :
172: this .moveFDDTo(currentFDD, highestReferencedFDD.next);
173: currentFDD.incNumberOfMoves();
174: numberOfExchangements++;
175: // Take over the follower :
176: currentFDD = nextStepFDD;
177: } else if (highestReferencedFDD == null) // no forward references
178: {
179: currentFDD = currentFDD.next;
180: }
181: // We skip entries, which were moved 10 times already,
182: // because circular references are allowed and would result in an endless
183: // loop here otherwise. We just move an entry 10 times max, which should
184: // give a good order without taking too long :
185: // So test, if the element, which has slipped to fsdIndex after the
186: // above move already has been moved 6 times or more :
187: if (currentFDD.getNumberOfMoves() > 5) {
188: // but dont cross the endloop criteria here :
189: if (currentFDD.next != this .dependencyDescriptionAnchor) {
190: currentFDD = currentFDD.next;
191: numberOfLoopOverflows++;
192: }
193: }
194: loopCount++;
195: if (loopCount % 48 == 0) {
196: try {
197: Thread.yield();
198: } catch (Exception e23876) {
199: }
200: // Temporary workaround: Break after 5 seconds :
201: if (System.currentTimeMillis() - startTime > 5000) {
202: Log.Warn("Stopped cause took too much time.");
203: break;
204: }
205: }
206: } // while
207:
208: // Go through the ordered list now :
209: String[] orderedFilePathNames = new String[projectFilePathNamesToBeCompiled.length];
210: FileDependencyDescription fdd = this .dependencyDescriptionAnchor.next; // The anchor itself doesnt carry data
211: for (int i = 0; i < projectFilePathNamesToBeCompiled.length; i++) {
212: orderedFilePathNames[i] = fdd.fsd.pathNameBuffer.toString();
213: fdd = fdd.next;
214: }
215:
216: //Log.Info(">numberOfZeroReferenceMoves = " + numberOfZeroReferenceMoves);
217: //Log.Info(">numberOfExchangements = " + numberOfExchangements);
218: //Log.Info(">numberOfLoopOverflows = " + numberOfLoopOverflows);
219:
220: //long elapsedTime = System.currentTimeMillis() - startTime;
221: //Log.Info("Elapsed time = " + elapsedTime + " [ms]");
222:
223: return orderedFilePathNames;
224: } // orderFilePathNamesAfterDependencies
225:
226: /**
227: * Moves sourceFDD to the location, where targetFDD has been.
228: * targetFDD will be the next element after sourceFDD in the linked list
229: * after this.
230: */
231: private void moveFDDTo(FileDependencyDescription sourceFDD,
232: FileDependencyDescription targetFDD) {
233: // get the sourceFDD out of the linked list :
234: FileDependencyDescription previousFDD = sourceFDD.previous;
235: FileDependencyDescription nextFDD = sourceFDD.next;
236: previousFDD.next = nextFDD;
237: nextFDD.previous = previousFDD;
238: // insert sourceFDD at the target location :
239: FileDependencyDescription previousTargetFDD = targetFDD.previous;
240: // backward links :
241: previousTargetFDD.next = sourceFDD;
242: sourceFDD.previous = previousTargetFDD;
243: // forward links :
244: sourceFDD.next = targetFDD;
245: targetFDD.previous = sourceFDD;
246: } // moveFDD
247:
248: private boolean IsInStringArray(String[] stringArray, String string) {
249: boolean isContained = false;
250: for (int i = 0; i < stringArray.length; i++) {
251: if (string.equals(stringArray[i])) {
252: isContained = true;
253: break;
254: }
255: }
256: return isContained;
257: }
258:
259: /**
260: * Go backwards through the list, until an element is found, which is referenced
261: * by the basisFDD, or the list was traversed completely (1 cycle).
262: * 3 cases :
263: * a) An FDD != basisFDD is returned -> we have a forward reference and
264: * therefore we will move the current FDD right behind the returned FDD.
265: * Note : We only move an FDD a certain amount of times, because circular
266: * references are allowed and otherwise would leed to endless loops.
267: *
268: * b) The returned FDD NULL -> No forward references -> all ok, nothing to do.
269: *
270: * c) The returned FDD is the anchor: Means that the associated FSD doesn't
271: * reference ANY other project FSD. In this case, we just move the current
272: * FDD to the anchor position, so later the compiler first will go through
273: * files, which don't reference any other project file.
274: *
275: * Note, that the anchor itself doesnt carry data and never is moved.
276: *
277: */
278: private FileDependencyDescription getHighestReferencedFDD(
279: final FileDependencyDescription basisFDD) {
280: Vector basisFSDReferences = basisFDD.fsd.referencedProjectFiles;
281: // If the basisFSD doesn't reference anything, we can return
282: // the anchor:
283: if (basisFSDReferences.size() == 0) {
284: return this .dependencyDescriptionAnchor;
285: }
286: // Otherwise scan:
287: FileDependencyDescription testFDD = this .dependencyDescriptionAnchor;
288: // Step 1 : Start at the end ( from the anchor backwards ) until either
289: // a referenced FDD or the basisFDD itseld is encountered :
290: FileDependencyDescription referencedFDD = null; // candidate for returning
291: while (true) {
292: testFDD = testFDD.previous;
293: if (testFDD == basisFDD) // no forward references were found
294: {
295: break; // return null
296: }
297: if (testFDD == this .dependencyDescriptionAnchor) // we ran down the complete list
298: {
299: referencedFDD = this .dependencyDescriptionAnchor; // return the anchor
300: break;
301: }
302: final FileStructureDescription testFSD = testFDD.fsd;
303: final String testFSDQualifier = testFSD.fullyQualifiedClassNameBuffer
304: .toString();
305: // See, if testFSD is referenced by the basisFSD:
306: for (int refIndex = 0; refIndex < basisFSDReferences.size(); refIndex++) {
307: final String this ReferenceQualifier = (String) basisFSDReferences
308: .elementAt(refIndex);
309: if (testFSDQualifier.equals(this ReferenceQualifier)) {
310: referencedFDD = testFDD; // found this highest forward reference
311: }
312: }
313: if (referencedFDD != null) {
314: break; // return the found forward reference
315: }
316: } // while
317: return referencedFDD;
318: } // getHighestReferencedFDD
319:
320: /**
321: * Nice To GC mode
322: */
323: public void disposeMemberAttributes() {
324: FileDependencyDescription fdd = this .dependencyDescriptionAnchor.next;
325: while (fdd != this .dependencyDescriptionAnchor) {
326: FileDependencyDescription nextFDD = fdd.next;
327: fdd.previous = null;
328: fdd.next = null;
329: fdd = nextFDD;
330: } // while
331: this .dependencyDescriptionAnchor.next = null;
332: this .dependencyDescriptionAnchor.previous = null;
333: this .dependencyDescriptionAnchor = null;
334: this .projectFilePathNamesToBeCompiled = null;
335: } //disposeTheLinkedList
336:
337: } // FileDependencySorter
|