001: /*******************************************************************************
002: * Copyright (c) 2000, 2003 IBM Corporation and others.
003: * All rights reserved. This program and the accompanying materials
004: * are made available under the terms of the Common Public License v1.0
005: * which accompanies this distribution, and is available at
006: * http://www.eclipse.org/legal/cpl-v10.html
007: *
008: * Contributors:
009: * IBM Corporation - initial API and implementation
010: *******************************************************************************/package org.enhydra.shark.xpdl;
011:
012: import java.io.File;
013:
014: /**
015: * Paths are always maintained in canonicalized form. That is, parent
016: * references (i.e., <code>../../</code>) and duplicate separators are
017: * resolved. For example,
018: * <pre> new Path("/a/b").append("../foo/bar")</pre>
019: * will yield the path
020: * <pre> /a/foo/bar</pre>
021: * <p>
022: * This class is not intended to be subclassed by clients but
023: * may be instantiated.
024: * </p>
025: */
026: public class Path {
027: /**
028: * Path separator character constant "/" used in paths.
029: */
030: public static final char SEPARATOR = '/';
031:
032: /**
033: * Device separator character constant ":" used in paths.
034: */
035: public static final char DEVICE_SEPARATOR = ':';
036:
037: /** The path segments */
038: private String[] segments;
039:
040: /** The device id string. May be null if there is no device. */
041: private String device = null;
042:
043: /** flags indicating separators (has leading, is UNC, has trailing) */
044: private int separators;
045:
046: /** masks for separator values */
047: private static final int HAS_LEADING = 1;
048: private static final int IS_UNC = 2;
049: private static final int HAS_TRAILING = 4;
050: private static final int ALL_SEPARATORS = HAS_LEADING | IS_UNC
051: | HAS_TRAILING;
052:
053: // /** Mask for all bits that are involved in the hashcode */
054: // private static final int HASH_MASK = ~HAS_TRAILING;
055:
056: /** Constant value indicating no segments */
057: private static final String[] NO_SEGMENTS = new String[0];
058:
059: /** Constant root path string (<code>"/"</code>). */
060: private static final String ROOT_STRING = "/"; //$NON-NLS-1$
061:
062: /** Constant value containing the root path with no device. */
063: public static final Path ROOT = new Path(ROOT_STRING);
064:
065: /** Constant empty string value. */
066: private static final String EMPTY_STRING = ""; //$NON-NLS-1$
067:
068: /** Constant value containing the empty path with no device. */
069: public static final Path EMPTY = new Path(EMPTY_STRING);
070:
071: //Private implementation note: the segments and separators
072: //arrays are never modified, so that they can be shared between
073: //path instances
074: private Path(String device, String[] segments, int _separators) {
075: // no segment validations are done for performance reasons
076: this .segments = segments;
077: this .device = device;
078: //hashcode is cached in all but the bottom three bits of the separators field
079: this .separators = (computeHashCode() << 3)
080: | (_separators & ALL_SEPARATORS);
081: }
082:
083: /**
084: * Constructs a new path from the given string path.
085: * The given string path must be valid.
086: * The path is canonicalized and double slashes are removed
087: * except at the beginning. (to handle UNC paths) All backslashes ('\')
088: * are replaced with forward slashes. ('/')
089: *
090: * @param fullPath the string path
091: */
092: public Path(String fullPath) {
093: // no segment validations are done for performance reasons
094: initialize(null, fullPath);
095: }
096:
097: /**
098: * Constructs a new path from the given device id and string path.
099: * The given string path must be valid.
100: * The path is canonicalized and double slashes are removed except
101: * at the beginning (to handle UNC paths). All backslashes ('\')
102: * are replaced with forward slashes. ('/')
103: *
104: * @param device the device id
105: * @param path the string path
106: * @see #setDevice
107: */
108: public Path(String device, String path) {
109: // no segment validations are done for performance reasons
110: initialize(device, path);
111: }
112:
113: /**
114: * Destructively converts this path to its canonical form.
115: * <p>
116: * In its canonical form, a path does not have any
117: * "." segments, and parent references ("..") are collapsed
118: * where possible.
119: * </p>
120: * @return true if the path was modified, and false otherwise.
121: */
122: private boolean canonicalize() {
123: //look for segments that need canonicalizing
124: for (int i = 0, max = segments.length; i < max; i++) {
125: String segment = segments[i];
126: if (segment.charAt(0) == '.'
127: && (segment.equals("..") || segment.equals("."))) { //$NON-NLS-1$ //$NON-NLS-2$
128: //path needs to be canonicalized
129: collapseParentReferences();
130: //paths of length 0 have no trailing separator
131: if (segments.length == 0)
132: separators &= (HAS_LEADING | IS_UNC);
133: //recompute hash because canonicalize affects hash
134: separators = (separators & ALL_SEPARATORS)
135: | (computeHashCode() << 3);
136: return true;
137: }
138: }
139: return false;
140: }
141:
142: /**
143: * Destructively removes all occurrences of ".." segments from this path.
144: */
145: private void collapseParentReferences() {
146: int segmentCount = segments.length;
147: String[] stack = new String[segmentCount];
148: int stackPointer = 0;
149: for (int i = 0; i < segmentCount; i++) {
150: String segment = segments[i];
151: if (segment.equals("..")) { //$NON-NLS-1$
152: if (stackPointer == 0) {
153: // if the stack is empty we are going out of our scope
154: // so we need to accumulate segments. But only if the original
155: // path is relative. If it is absolute then we can't go any higher than
156: // root so simply toss the .. references.
157: if (!isAbsolute())
158: stack[stackPointer++] = segment;//stack push
159: } else {
160: // if the top is '..' then we are accumulating segments so don't pop
161: if ("..".equals(stack[stackPointer - 1])) //$NON-NLS-1$
162: stack[stackPointer++] = ".."; //$NON-NLS-1$
163: else
164: stackPointer--;//stack pop
165: }
166: //collapse current references
167: } else if (!segment.equals(".") || (i == 0 && !isAbsolute())) //$NON-NLS-1$
168: stack[stackPointer++] = segment;//stack push
169: }
170: //if the number of segments hasn't changed, then no modification needed
171: if (stackPointer == segmentCount)
172: return;
173: //build the new segment array backwards by popping the stack
174: String[] newSegments = new String[stackPointer];
175: System.arraycopy(stack, 0, newSegments, 0, stackPointer);
176: this .segments = newSegments;
177: }
178:
179: /**
180: * Removes duplicate slashes from the given path, with the exception
181: * of leading double slash which represents a UNC path.
182: */
183: private String collapseSlashes(String path) {
184: int length = path.length();
185: // if the path is only 0, 1 or 2 chars long then it could not possibly have illegal
186: // duplicate slashes.
187: if (length < 3)
188: return path;
189: // check for an occurence of // in the path. Start at index 1 to ensure we skip leading UNC //
190: // If there are no // then there is nothing to collapse so just return.
191: if (path.indexOf("//", 1) == -1) //$NON-NLS-1$
192: return path;
193: // We found an occurence of // in the path so do the slow collapse.
194: char[] result = new char[path.length()];
195: int count = 0;
196: boolean hasPrevious = false;
197: char[] characters = path.toCharArray();
198: for (int index = 0; index < characters.length; index++) {
199: char c = characters[index];
200: if (c == SEPARATOR) {
201: if (hasPrevious) {
202: // skip double slashes, except for beginning of UNC.
203: // note that a UNC path can't have a device.
204: if (device == null && index == 1) {
205: result[count] = c;
206: count++;
207: }
208: } else {
209: hasPrevious = true;
210: result[count] = c;
211: count++;
212: }
213: } else {
214: hasPrevious = false;
215: result[count] = c;
216: count++;
217: }
218: }
219: return new String(result, 0, count);
220: }
221:
222: /*
223: * Computes the hash code for this object.
224: */
225: private int computeHashCode() {
226: int hash = device == null ? 17 : device.hashCode();
227: int segmentCount = segments.length;
228: for (int i = 0; i < segmentCount; i++) {
229: //this function tends to given a fairly even distribution
230: hash = hash * 37 + segments[i].hashCode();
231: }
232: return hash;
233: }
234:
235: /*
236: * Returns the size of the string that will be created by toString or toOSString.
237: */
238: private int computeLength() {
239: int length = 0;
240: if (device != null)
241: length += device.length();
242: if ((separators & HAS_LEADING) != 0)
243: length++;
244: if ((separators & IS_UNC) != 0)
245: length++;
246: //add the segment lengths
247: int max = segments.length;
248: if (max > 0) {
249: for (int i = 0; i < max; i++) {
250: length += segments[i].length();
251: }
252: //add the separator lengths
253: length += max - 1;
254: }
255: if ((separators & HAS_TRAILING) != 0)
256: length++;
257: return length;
258: }
259:
260: /*
261: * Returns the number of segments in the given path
262: */
263: private int computeSegmentCount(String path) {
264: int len = path.length();
265: if (len == 0 || (len == 1 && path.charAt(0) == SEPARATOR)) {
266: return 0;
267: }
268: int count = 1;
269: int prev = -1;
270: int i;
271: while ((i = path.indexOf(SEPARATOR, prev + 1)) != -1) {
272: if (i != prev + 1 && i != len) {
273: ++count;
274: }
275: prev = i;
276: }
277: if (path.charAt(len - 1) == SEPARATOR) {
278: --count;
279: }
280: return count;
281: }
282:
283: /**
284: * Computes the segment array for the given canonicalized path.
285: */
286: private String[] computeSegments(String path) {
287: // performance sensitive --- avoid creating garbage
288: int segmentCount = computeSegmentCount(path);
289: if (segmentCount == 0)
290: return NO_SEGMENTS;
291: String[] newSegments = new String[segmentCount];
292: int len = path.length();
293: // check for initial slash
294: int firstPosition = (path.charAt(0) == SEPARATOR) ? 1 : 0;
295: // check for UNC
296: if (firstPosition == 1 && len > 1
297: && (path.charAt(1) == SEPARATOR))
298: firstPosition = 2;
299: int lastPosition = (path.charAt(len - 1) != SEPARATOR) ? len - 1
300: : len - 2;
301: // for non-empty paths, the number of segments is
302: // the number of slashes plus 1, ignoring any leading
303: // and trailing slashes
304: int next = firstPosition;
305: for (int i = 0; i < segmentCount; i++) {
306: int start = next;
307: int end = path.indexOf(SEPARATOR, next);
308: if (end == -1) {
309: newSegments[i] = path
310: .substring(start, lastPosition + 1);
311: } else {
312: newSegments[i] = path.substring(start, end);
313: }
314: next = end + 1;
315: }
316: return newSegments;
317: }
318:
319: /*
320: * Initialize the current path with the given string.
321: */
322: private void initialize(String pDevice, String fullPath) {
323: if (fullPath == null)
324: throw new RuntimeException();
325: this .device = pDevice;
326:
327: //indexOf is much faster than replace
328: String path = fullPath.indexOf('\\') == -1 ? fullPath
329: : fullPath.replace('\\', SEPARATOR);
330:
331: int i = path.indexOf(DEVICE_SEPARATOR);
332: if (i != -1) {
333: // if the specified device is null then set it to
334: // be whatever is defined in the path string
335: if (pDevice == null)
336: this .device = path.substring(0, i + 1);
337: path = path.substring(i + 1, path.length());
338: }
339: path = collapseSlashes(path);
340: int len = path.length();
341:
342: //compute the separators array
343: if (len < 2) {
344: if (len == 1 && path.charAt(0) == SEPARATOR) {
345: this .separators = HAS_LEADING;
346: } else {
347: this .separators = 0;
348: }
349: } else {
350: boolean hasLeading = path.charAt(0) == SEPARATOR;
351: boolean isUNC = hasLeading && path.charAt(1) == SEPARATOR;
352: //UNC path of length two has no trailing separator
353: boolean hasTrailing = !(isUNC && len == 2)
354: && path.charAt(len - 1) == SEPARATOR;
355: separators = hasLeading ? HAS_LEADING : 0;
356: if (isUNC)
357: separators |= IS_UNC;
358: if (hasTrailing)
359: separators |= HAS_TRAILING;
360: }
361: //compute segments and ensure canonical form
362: segments = computeSegments(path);
363: if (!canonicalize()) {
364: //compute hash now because canonicalize didn't need to do it
365: separators = (separators & ALL_SEPARATORS)
366: | (computeHashCode() << 3);
367: }
368: }
369:
370: public boolean isAbsolute() {
371: //it's absolute if it has a leading separator
372: return (separators & HAS_LEADING) != 0;
373: }
374:
375: public int matchingFirstSegments(Path anotherPath) {
376: if (anotherPath == null)
377: throw new RuntimeException();
378: int anotherPathLen = anotherPath.segmentCount();
379: int max = Math.min(segments.length, anotherPathLen);
380: int count = 0;
381: for (int i = 0; i < max; i++) {
382: if (!segments[i].equals(anotherPath.segment(i))) {
383: return count;
384: }
385: count++;
386: }
387: return count;
388: }
389:
390: public String segment(int index) {
391: if (index >= segments.length)
392: return null;
393: return segments[index];
394: }
395:
396: public int segmentCount() {
397: return segments.length;
398: }
399:
400: public String[] segments() {
401: String[] segmentCopy = new String[segments.length];
402: System.arraycopy(segments, 0, segmentCopy, 0, segments.length);
403: return segmentCopy;
404: }
405:
406: public Path setDevice(String value) {
407: if (value != null) {
408: //Assert.isTrue(value.indexOf(Path.DEVICE_SEPARATOR) == (value.length() - 1), "Last character should be the device separator"); //$NON-NLS-1$
409: if (value.indexOf(Path.DEVICE_SEPARATOR) != (value.length() - 1))
410: throw new RuntimeException(
411: "Last character should be the device separator");
412: }
413: //return the reciever if the device is the same
414: if (value == device || (value != null && value.equals(device)))
415: return this ;
416:
417: return new Path(value, segments, separators);
418: }
419:
420: public String toOSString() {
421: //Note that this method is identical to toString except
422: //it uses the OS file separator instead of the path separator
423: int resultSize = computeLength();
424: if (resultSize <= 0)
425: return EMPTY_STRING;
426: char FILE_SEPARATOR = File.separatorChar;
427: char[] result = new char[resultSize];
428: int offset = 0;
429: if (device != null) {
430: int size = device.length();
431: device.getChars(0, size, result, offset);
432: offset += size;
433: }
434: if ((separators & HAS_LEADING) != 0)
435: result[offset++] = FILE_SEPARATOR;
436: if ((separators & IS_UNC) != 0)
437: result[offset++] = FILE_SEPARATOR;
438: int len = segments.length - 1;
439: if (len >= 0) {
440: //append all but the last segment, with separators
441: for (int i = 0; i < len; i++) {
442: int size = segments[i].length();
443: segments[i].getChars(0, size, result, offset);
444: offset += size;
445: result[offset++] = FILE_SEPARATOR;
446: }
447: //append the last segment
448: int size = segments[len].length();
449: segments[len].getChars(0, size, result, offset);
450: offset += size;
451: }
452: if ((separators & HAS_TRAILING) != 0)
453: result[offset++] = FILE_SEPARATOR;
454: return new String(result);
455: }
456:
457: public static String getRelativePath(Path fullPath, Path fBasePath) {
458: if (fBasePath == null || !hasSameDevice(fullPath, fBasePath)) {
459: return fullPath.toOSString();
460: }
461: int matchingSegments = fBasePath
462: .matchingFirstSegments(fullPath);
463: StringBuffer res = new StringBuffer();
464: int backSegments = fBasePath.segmentCount() - matchingSegments;
465: while (backSegments > 0) {
466: res.append(".."); //$NON-NLS-1$
467: res.append(File.separatorChar);
468: backSegments--;
469: }
470: int segCount = fullPath.segmentCount();
471: for (int i = matchingSegments; i < segCount; i++) {
472: if (i > matchingSegments) {
473: res.append(File.separatorChar);
474: }
475: res.append(fullPath.segment(i));
476: }
477: return res.toString();
478: }
479:
480: private static boolean hasSameDevice(Path p1, Path p2) {
481: String dev = p1.device;
482: if (dev == null) {
483: return p2.device == null;
484: }
485: return dev.equals(p2.device);
486: }
487:
488: }
|