001/*
002 * Copyright (c) 2006-2012 Nuxeo SA (http://nuxeo.com/) and others.
003 *
004 * All rights reserved. This program and the accompanying materials
005 * are made available under the terms of the Eclipse Public License v1.0
006 * which accompanies this distribution, and is available at
007 * http://www.eclipse.org/legal/epl-v10.html
008 *
009 * Contributors:
010 *     IBM Corporation - initial API and implementation
011 */
012package org.nuxeo.common.utils;
013
014import java.io.Serializable;
015
016/**
017 * Contains code from Eclipse org.eclipse.core.runtime.Path class
018 *
019 * @author <a href="mailto:bs@nuxeo.com">Bogdan Stefanescu</a>
020 */
021public class Path implements Serializable {
022
023    private static final long serialVersionUID = -5420562131803786641L;
024
025    private static final int HAS_LEADING = 1;
026
027    private static final int HAS_TRAILING = 2;
028
029    private static final int ALL_SEPARATORS = HAS_LEADING | HAS_TRAILING;
030
031    private static final int USED_BITS = 2;
032
033    private static final String[] NO_SEGMENTS = new String[0];
034
035    /**
036     * Path separator character constant "/" used in paths.
037     */
038    private static final char SEPARATOR = '/';
039
040    /** Constant empty string value. */
041    private static final String EMPTY_STRING = ""; //$NON-NLS-1$
042
043    /** Constant value containing the empty path with no device. */
044    private static final Path EMPTY = new Path(EMPTY_STRING);
045
046    //
047    private static final int HASH_MASK = ~HAS_TRAILING;
048
049    /** Constant root path string (<code>"/"</code>). */
050    private static final String ROOT_STRING = "/"; //$NON-NLS-1$
051
052    /** Constant value containing the root path with no device. */
053    private static final Path ROOT = new Path(ROOT_STRING);
054
055    private String[] segments;
056
057    private int separators;
058
059    /**
060     * Constructs a new path from the given string path.
061     * <p>
062     * The string path must represent a valid file system path on the local file system.
063     * <p>
064     * The path is canonicalized and double slashes are removed except at the beginning. (to handle UNC paths). All
065     * forward slashes ('/') are treated as segment delimiters, and any segment and device delimiters for the local file
066     * system are also respected (such as colon (':') and backslash ('\') on some file systems).
067     *
068     * @param fullPath the string path
069     * @see #isValidPath(String)
070     */
071    public Path(String fullPath) {
072        initialize(fullPath);
073    }
074
075    /**
076     * Optimized constructor - no validations on segments are done.
077     *
078     * @param segments
079     * @param separators
080     */
081    private Path(String[] segments, int separators) {
082        // no segment validations are done for performance reasons
083        this.segments = segments;
084        // hash code is cached in all but the bottom three bits of the separators field
085        this.separators = (computeHashCode() << USED_BITS) | (separators & ALL_SEPARATORS);
086    }
087
088    /**
089     * Creates a path object from an absolute and canonical path.
090     * <p>
091     * This method does not check the given path - it assumes the path has a valid format of the form "/a/b/c" without
092     * duplicate slashes or dots.
093     *
094     * @return the path
095     */
096    public static Path createFromAbsolutePath(String path) {
097        assert path != null;
098        final int len = computeSegmentCount(path);
099        if (path.length() < 2) {
100            return ROOT;
101        }
102        String[] segments = new String[len];
103        int k = 0;
104        int j = 1;
105        int i = path.indexOf(SEPARATOR, j);
106        while (i > 0) {
107            segments[k++] = path.substring(j, i);
108            j = i + 1;
109            i = path.indexOf(SEPARATOR, j);
110        }
111        segments[k] = path.substring(j);
112        return new Path(segments, HAS_LEADING);
113    }
114
115    public static Path createFromSegments(String[] segments) {
116        if (segments.length == 0) {
117            return ROOT;
118        }
119        return new Path(segments, HAS_LEADING);
120    }
121
122    public Path addFileExtension(String extension) {
123        if (isRoot() || isEmpty() || hasTrailingSeparator()) {
124            return this;
125        }
126        int len = segments.length;
127        String[] newSegments = new String[len];
128        System.arraycopy(segments, 0, newSegments, 0, len - 1);
129        newSegments[len - 1] = segments[len - 1] + '.' + extension;
130        return new Path(newSegments, separators);
131    }
132
133    public Path addTrailingSeparator() {
134        if (hasTrailingSeparator() || isRoot()) {
135            return this;
136        }
137        if (isEmpty()) {
138            return new Path(segments, HAS_LEADING);
139        }
140        return new Path(segments, separators | HAS_TRAILING);
141    }
142
143    // XXX: confusing, one may think that this modifies the path
144    // being appended to (like Python's list.append()).
145    public Path append(Path tail) {
146        // optimize some easy cases
147        if (tail == null || tail.segmentCount() == 0) {
148            return this;
149        }
150        if (isEmpty()) {
151            return tail.makeRelative();
152        }
153        if (isRoot()) {
154            return tail.makeAbsolute();
155        }
156
157        // concatenate the two segment arrays
158        int myLen = segments.length;
159        int tailLen = tail.segmentCount();
160        String[] newSegments = new String[myLen + tailLen];
161        System.arraycopy(segments, 0, newSegments, 0, myLen);
162        for (int i = 0; i < tailLen; i++) {
163            newSegments[myLen + i] = tail.segment(i);
164        }
165        // use my leading separators and the tail's trailing separator
166        Path result = new Path(newSegments, (separators & HAS_LEADING)
167                | (tail.hasTrailingSeparator() ? HAS_TRAILING : 0));
168        String tailFirstSegment = newSegments[myLen];
169        if (tailFirstSegment.equals("..") || tailFirstSegment.equals(".")) { //$NON-NLS-1$ //$NON-NLS-2$
170            result.canonicalize();
171        }
172        return result;
173    }
174
175    // XXX: same remark
176    public Path append(String tail) {
177        // optimize addition of a single segment
178        if (tail.indexOf(SEPARATOR) == -1) {
179            int tailLength = tail.length();
180            if (tailLength < 3) {
181                // some special cases
182                if (tailLength == 0 || ".".equals(tail)) { //$NON-NLS-1$
183                    return this;
184                }
185                if ("..".equals(tail)) {
186                    return removeLastSegments(1);
187                }
188            }
189            // just add the segment
190            int myLen = segments.length;
191            String[] newSegments = new String[myLen + 1];
192            System.arraycopy(segments, 0, newSegments, 0, myLen);
193            newSegments[myLen] = tail;
194            return new Path(newSegments, separators & ~HAS_TRAILING);
195        }
196        // go with easy implementation
197        return append(new Path(tail));
198    }
199
200    /**
201     * Destructively converts this path to its canonical form.
202     * <p>
203     * In its canonical form, a path does not have any "." segments, and parent references ("..") are collapsed where
204     * possible.
205     *
206     * @return true if the path was modified, and false otherwise.
207     */
208    private boolean canonicalize() {
209        // look for segments that need canonicalizing
210        for (int i = 0, max = segments.length; i < max; i++) {
211            String segment = segments[i];
212            if (segment.charAt(0) == '.' && (segment.equals("..") || segment.equals("."))) { //$NON-NLS-1$ //$NON-NLS-2$
213                // path needs to be canonicalized
214                collapseParentReferences();
215                // paths of length 0 have no trailing separator
216                if (segments.length == 0) {
217                    separators &= HAS_LEADING;
218                }
219                // recompute hash because canonicalize affects hash
220                separators = (separators & ALL_SEPARATORS) | (computeHashCode() << USED_BITS);
221                return true;
222            }
223        }
224        return false;
225    }
226
227    /**
228     * Destructively removes all occurrences of ".." segments from this path.
229     */
230    private void collapseParentReferences() {
231        int segmentCount = segments.length;
232        String[] stack = new String[segmentCount];
233        int stackPointer = 0;
234        for (int i = 0; i < segmentCount; i++) {
235            String segment = segments[i];
236            if (segment.equals("..")) { //$NON-NLS-1$
237                if (stackPointer == 0) {
238                    // if the stack is empty we are going out of our scope
239                    // so we need to accumulate segments. But only if the original
240                    // path is relative. If it is absolute then we can't go any higher than
241                    // root so simply toss the .. references.
242                    if (!isAbsolute()) {
243                        stack[stackPointer++] = segment; // stack push
244                    }
245                } else {
246                    // if the top is '..' then we are accumulating segments so don't pop
247                    if ("..".equals(stack[stackPointer - 1])) { //$NON-NLS-1$
248                        stack[stackPointer++] = ".."; //$NON-NLS-1$
249                    } else {
250                        stackPointer--;
251                        // stack pop
252                    }
253                }
254                // collapse current references
255            } else if (!segment.equals(".") || (i == 0 && !isAbsolute())) {
256                stack[stackPointer++] = segment; // stack push
257            }
258        }
259        // if the number of segments hasn't changed, then no modification needed
260        if (stackPointer == segmentCount) {
261            return;
262        }
263        // build the new segment array backwards by popping the stack
264        String[] newSegments = new String[stackPointer];
265        System.arraycopy(stack, 0, newSegments, 0, stackPointer);
266        segments = newSegments;
267    }
268
269    /**
270     * Removes duplicate slashes from the given path.
271     */
272    private static String collapseSlashes(String path) {
273        int length = path.length();
274        // if the path is only 0 or 1 chars long then it could not possibly have illegal
275        // duplicate slashes.
276        if (length < 2) {
277            return path;
278        }
279        // check for an occurrence of // in the path. Start at index 1 to ensure we skip leading UNC //
280        // If there are no // then there is nothing to collapse so just return.
281        if (path.indexOf("//", 1) == -1) {
282            return path;
283        }
284        // We found an occurrence of // in the path so do the slow collapse.
285        char[] result = new char[path.length()];
286        int count = 0;
287        boolean hasPrevious = false;
288        char[] characters = path.toCharArray();
289        for (char c : characters) {
290            if (c == SEPARATOR) {
291                if (!hasPrevious) {
292                    hasPrevious = true;
293                    result[count] = c;
294                    count++;
295                } // else skip double slashes
296            } else {
297                hasPrevious = false;
298                result[count] = c;
299                count++;
300            }
301        }
302        return new String(result, 0, count);
303    }
304
305    private int computeHashCode() {
306        int hash = 17;
307        int segmentCount = segments.length;
308        for (int i = 0; i < segmentCount; i++) {
309            // this function tends to given a fairly even distribution
310            hash = hash * 37 + segments[i].hashCode();
311        }
312        return hash;
313    }
314
315    private int computeLength() {
316        int length = 0;
317        if ((separators & HAS_LEADING) != 0) {
318            length++;
319        }
320        // add the segment lengths
321        int max = segments.length;
322        if (max > 0) {
323            for (int i = 0; i < max; i++) {
324                length += segments[i].length();
325            }
326            // add the separator lengths
327            length += max - 1;
328        }
329        if ((separators & HAS_TRAILING) != 0) {
330            length++;
331        }
332        return length;
333    }
334
335    private static int computeSegmentCount(String path) {
336        int len = path.length();
337        if (len == 0 || (len == 1 && path.charAt(0) == SEPARATOR)) {
338            return 0;
339        }
340        int count = 1;
341        int prev = -1;
342        int i;
343        while ((i = path.indexOf(SEPARATOR, prev + 1)) != -1) {
344            if (i != prev + 1 && i != len) {
345                ++count;
346            }
347            prev = i;
348        }
349        if (path.charAt(len - 1) == SEPARATOR) {
350            --count;
351        }
352        return count;
353    }
354
355    /**
356     * Computes the segment array for the given canonicalized path.
357     */
358    private static String[] computeSegments(String path) {
359        // performance sensitive --- avoid creating garbage
360        int segmentCount = computeSegmentCount(path);
361        if (segmentCount == 0) {
362            return NO_SEGMENTS;
363        }
364        String[] newSegments = new String[segmentCount];
365        int len = path.length();
366        // check for initial slash
367        int firstPosition = (path.charAt(0) == SEPARATOR) ? 1 : 0;
368        // check for UNC
369        if (firstPosition == 1 && len > 1 && (path.charAt(1) == SEPARATOR)) {
370            firstPosition = 2;
371        }
372        int lastPosition = (path.charAt(len - 1) != SEPARATOR) ? len - 1 : len - 2;
373        // for non-empty paths, the number of segments is
374        // the number of slashes plus 1, ignoring any leading
375        // and trailing slashes
376        int next = firstPosition;
377        for (int i = 0; i < segmentCount; i++) {
378            int start = next;
379            int end = path.indexOf(SEPARATOR, next);
380            if (end == -1) {
381                newSegments[i] = path.substring(start, lastPosition + 1);
382            } else {
383                newSegments[i] = path.substring(start, end);
384            }
385            next = end + 1;
386        }
387        return newSegments;
388    }
389
390    @Override
391    public boolean equals(Object obj) {
392        if (this == obj) {
393            return true;
394        }
395        if (!(obj instanceof Path)) {
396            return false;
397        }
398        Path target = (Path) obj;
399        // check leading separators and hash code
400        if ((separators & HASH_MASK) != (target.separators & HASH_MASK)) {
401            return false;
402        }
403        String[] targetSegments = target.segments;
404        int i = segments.length;
405        // check segment count
406        if (i != targetSegments.length) {
407            return false;
408        }
409        // check segments in reverse order - later segments more likely to differ
410        while (--i >= 0) {
411            if (!segments[i].equals(targetSegments[i])) {
412                return false;
413            }
414        }
415        return true;
416    }
417
418    @Override
419    public int hashCode() {
420        return separators & HASH_MASK;
421    }
422
423    public String getFileExtension() {
424        if (hasTrailingSeparator()) {
425            return null;
426        }
427        String lastSegment = lastSegment();
428        if (lastSegment == null) {
429            return null;
430        }
431        int index = lastSegment.lastIndexOf('.');
432        if (index == -1) {
433            return null;
434        }
435        return lastSegment.substring(index + 1);
436    }
437
438    public boolean hasTrailingSeparator() {
439        return (separators & HAS_TRAILING) != 0;
440    }
441
442    /**
443     * Initializes the current path with the given string.
444     */
445    private Path initialize(String path) {
446        assert path != null;
447
448        path = collapseSlashes(path);
449        int len = path.length();
450
451        // compute the separators array
452        if (len < 2) {
453            if (len == 1 && path.charAt(0) == SEPARATOR) {
454                separators = HAS_LEADING;
455            } else {
456                separators = 0;
457            }
458        } else {
459            boolean hasLeading = path.charAt(0) == SEPARATOR;
460            boolean hasTrailing = path.charAt(len - 1) == SEPARATOR;
461            separators = hasLeading ? HAS_LEADING : 0;
462            if (hasTrailing) {
463                separators |= HAS_TRAILING;
464            }
465        }
466        // compute segments and ensure canonical form
467        segments = computeSegments(path);
468        if (!canonicalize()) {
469            // compute hash now because canonicalize didn't need to do it
470            separators = (separators & ALL_SEPARATORS) | (computeHashCode() << USED_BITS);
471        }
472        return this;
473    }
474
475    public boolean isAbsolute() {
476        // it's absolute if it has a leading separator
477        return (separators & HAS_LEADING) != 0;
478    }
479
480    public boolean isEmpty() {
481        // true if no segments and no leading prefix
482        return segments.length == 0 && ((separators & ALL_SEPARATORS) != HAS_LEADING);
483    }
484
485    public boolean isPrefixOf(Path anotherPath) {
486        if (isEmpty() || (isRoot() && anotherPath.isAbsolute())) {
487            return true;
488        }
489        int len = segments.length;
490        if (len > anotherPath.segmentCount()) {
491            return false;
492        }
493        for (int i = 0; i < len; i++) {
494            if (!segments[i].equals(anotherPath.segment(i))) {
495                return false;
496            }
497        }
498        return true;
499    }
500
501    public boolean isRoot() {
502        // must have no segments, a leading separator, and not be a UNC path.
503        return this == ROOT || (segments.length == 0 && ((separators & ALL_SEPARATORS) == HAS_LEADING));
504    }
505
506    public static boolean isValidPath(String path) {
507        Path test = new Path(path);
508        for (int i = 0, max = test.segmentCount(); i < max; i++) {
509            if (!isValidSegment(test.segment(i))) {
510                return false;
511            }
512        }
513        return true;
514    }
515
516    private static boolean isValidSegment(String segment) {
517        int size = segment.length();
518        if (size == 0) {
519            return false;
520        }
521        for (int i = 0; i < size; i++) {
522            char c = segment.charAt(i);
523            if (c == '/') {
524                return false;
525            }
526        }
527        return true;
528    }
529
530    public String lastSegment() {
531        int len = segments.length;
532        return len == 0 ? null : segments[len - 1];
533    }
534
535    public Path makeAbsolute() {
536        if (isAbsolute()) {
537            return this;
538        }
539        Path result = new Path(segments, separators | HAS_LEADING);
540        // may need canonicalizing if it has leading ".." or "." segments
541        if (result.segmentCount() > 0) {
542            String first = result.segment(0);
543            if (first.equals("..") || first.equals(".")) { //$NON-NLS-1$ //$NON-NLS-2$
544                result.canonicalize();
545            }
546        }
547        return result;
548    }
549
550    public Path makeRelative() {
551        if (!isAbsolute()) {
552            return this;
553        }
554        return new Path(segments, separators & HAS_TRAILING);
555    }
556
557    public int matchingFirstSegments(Path anotherPath) {
558        assert anotherPath != null;
559        int anotherPathLen = anotherPath.segmentCount();
560        int max = Math.min(segments.length, anotherPathLen);
561        int count = 0;
562        for (int i = 0; i < max; i++) {
563            if (!segments[i].equals(anotherPath.segment(i))) {
564                return count;
565            }
566            count++;
567        }
568        return count;
569    }
570
571    public Path removeFileExtension() {
572        String extension = getFileExtension();
573        if (extension == null || extension.equals("")) { //$NON-NLS-1$
574            return this;
575        }
576        String lastSegment = lastSegment();
577        int index = lastSegment.lastIndexOf(extension) - 1;
578        return removeLastSegments(1).append(lastSegment.substring(0, index));
579    }
580
581    public Path removeFirstSegments(int count) {
582        if (count == 0) {
583            return this;
584        }
585        if (count >= segments.length) {
586            return new Path(NO_SEGMENTS, 0);
587        }
588        assert count > 0;
589        int newSize = segments.length - count;
590        String[] newSegments = new String[newSize];
591        System.arraycopy(segments, count, newSegments, 0, newSize);
592
593        // result is always a relative path
594        return new Path(newSegments, separators & HAS_TRAILING);
595    }
596
597    public Path removeLastSegments(final int count) {
598        if (count == 0) {
599            return this;
600        }
601        if (count >= segments.length) {
602            // result will have no trailing separator
603            return new Path(NO_SEGMENTS, separators & HAS_LEADING);
604        }
605        assert count > 0;
606        final int newSize = segments.length - count;
607        final String[] newSegments = new String[newSize];
608        System.arraycopy(segments, 0, newSegments, 0, newSize);
609        return new Path(newSegments, separators);
610    }
611
612    public Path removeTrailingSeparator() {
613        if (!hasTrailingSeparator()) {
614            return this;
615        }
616        return new Path(segments, separators & HAS_LEADING);
617    }
618
619    public String segment(int index) {
620        if (index >= segments.length) {
621            return null;
622        }
623        return segments[index];
624    }
625
626    public int segmentCount() {
627        return segments.length;
628    }
629
630    public String[] segments() {
631        final String[] segmentCopy = new String[segments.length];
632        System.arraycopy(segments, 0, segmentCopy, 0, segments.length);
633        return segmentCopy;
634    }
635
636    @Override
637    public String toString() {
638        final int resultSize = computeLength();
639        if (resultSize <= 0) {
640            return EMPTY_STRING;
641        }
642        char[] result = new char[resultSize];
643        int offset = 0;
644        if ((separators & HAS_LEADING) != 0) {
645            result[offset++] = SEPARATOR;
646        }
647        final int len = segments.length - 1;
648        if (len >= 0) {
649            // append all but the last segment, with separators
650            for (int i = 0; i < len; i++) {
651                final int size = segments[i].length();
652                segments[i].getChars(0, size, result, offset);
653                offset += size;
654                result[offset++] = SEPARATOR;
655            }
656            // append the last segment
657            final int size = segments[len].length();
658            segments[len].getChars(0, size, result, offset);
659            offset += size;
660        }
661        if ((separators & HAS_TRAILING) != 0) {
662            result[offset] = SEPARATOR;
663        }
664        return new String(result);
665    }
666
667    public Path uptoSegment(final int count) {
668        if (count == 0) {
669            return new Path(NO_SEGMENTS, separators & HAS_LEADING);
670        }
671        if (count >= segments.length) {
672            return this;
673        }
674        assert count > 0; // Invalid parameter to Path.uptoSegment
675        final String[] newSegments = new String[count];
676        System.arraycopy(segments, 0, newSegments, 0, count);
677        return new Path(newSegments, separators);
678    }
679
680    /**
681     * Gets the name of the icon file so that it can be displayed as alt text.
682     */
683    public static String getFileNameFromPath(String iconPath) {
684        String iconName;
685        // String fileSeparator = System.getProperty("file.separator");
686
687        // temporary not working with the file separator, only with /
688        int firstCharOfIconName = iconPath.lastIndexOf(SEPARATOR);
689        int lastCharOfIconName = iconPath.lastIndexOf(".");
690        if (firstCharOfIconName == -1) {
691            iconName = iconPath;
692        } else {
693            iconName = iconPath.substring(firstCharOfIconName, lastCharOfIconName);
694        }
695        return iconName;
696    }
697
698}