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