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}