// Copyright 2014 The Bazel Authors. All rights reserved. // // Licensed under the Apache License, Version 2.0 (the "License"); // you may not use this file except in compliance with the License. // You may obtain a copy of the License at // // http://www.apache.org/licenses/LICENSE-2.0 // // Unless required by applicable law or agreed to in writing, software // distributed under the License is distributed on an "AS IS" BASIS, // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. // See the License for the specific language governing permissions and // limitations under the License. package com.google.devtools.build.lib.vfs; import static com.google.common.collect.ImmutableSet.toImmutableSet; import com.google.common.base.Preconditions; import com.google.common.collect.ImmutableList; import com.google.common.collect.ImmutableSet; import com.google.common.collect.Iterables; import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable; import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe; import com.google.devtools.build.lib.skylarkinterface.SkylarkPrintable; import com.google.devtools.build.lib.skylarkinterface.SkylarkPrinter; import com.google.devtools.build.lib.util.OS; import com.google.devtools.build.lib.util.StringCanonicalizer; import java.io.File; import java.io.InvalidObjectException; import java.io.ObjectInputStream; import java.io.Serializable; import java.util.Arrays; import java.util.List; import java.util.Set; /** * This class represents an immutable filesystem path, which may be absolute or relative. The path * is maintained as a simple ordered list of path segment strings. * *
This class is independent from other VFS classes, especially anything requiring native code. * It is safe to use in places that need simple segmented string path functionality. * *
There is some limited support for Windows-style paths. Most importantly, drive identifiers in
* front of a path (c:/abc) are supported and such paths are correctly recognized as absolute, as
* are paths with backslash separators (C:\\foo\\bar). However, advanced Windows-style features like
* \\\\network\\paths and \\\\?\\unc\\paths are not supported.
*/
@Immutable
@javax.annotation.concurrent.Immutable
@ThreadSafe
public abstract class PathFragment
implements Comparable There will be exactly one {@link Helper} instance used to manipulate all the {@link
* PathFragment} instances (see {@link PathFragment#HELPER}). All of the various {@link Helper}
* and {@link PathFragment} implementations may assume this property.
*/
protected abstract static class Helper {
/**
* Returns whether the two given arrays of segments have the same length and should be
* considered have logically equal contents.
*/
protected final boolean segmentsEqual(String[] segments1, String[] segments2) {
return segments1.length == segments2.length
&& segmentsEqual(segments1.length, segments1, 0, segments2);
}
/**
* Returns whether the {@code length} segments in {@code segments1}, starting at {@code offset1}
* should be considered to be logically equal to the first {@code length} segments in {@code
* segments2}.
*/
abstract boolean segmentsEqual(int length, String[] segments1, int offset1, String[] segments2);
/** Returns the comparison result of two {@link PathFragment} instances. */
protected abstract int compare(PathFragment pathFragment1, PathFragment pathFragment2);
/** Returns a fresh {@link PathFragment} instance from the given path string. */
abstract PathFragment create(String path);
/**
* Returns a fresh {@link PathFragment} instance from the given information, taking ownership of
* {@code segments} and assuming the {@link String}s within have already been interned.
*/
abstract PathFragment createAlreadyInterned(
char driveLetter, boolean isAbsolute, String[] segments);
/** Returns whether {@code c} is a path separator. */
abstract boolean isSeparator(char c);
/** Returns the primary path separator. */
abstract char getPrimarySeparatorChar();
/** Return whether the given {@code path} contains a path separator. */
abstract boolean containsSeparatorChar(String path);
/**
* Splits the given {@code toSegment} into path segments, starting at the given {@code offset}.
*/
protected final String[] segment(String toSegment, int offset) {
int length = toSegment.length();
// We make two passes through the array of characters: count & alloc,
// because simply using ArrayList was a bottleneck showing up during profiling.
int seg = 0;
int start = offset;
for (int i = offset; i < length; i++) {
if (isSeparator(toSegment.charAt(i))) {
if (i > start) { // to skip repeated separators
seg++;
}
start = i + 1;
}
}
if (start < length) {
seg++;
}
String[] result = new String[seg];
seg = 0;
start = offset;
for (int i = offset; i < length; i++) {
if (isSeparator(toSegment.charAt(i))) {
if (i > start) { // to skip repeated separators
result[seg] = StringCanonicalizer.intern(toSegment.substring(start, i));
seg++;
}
start = i + 1;
}
}
if (start < length) {
result[seg] = StringCanonicalizer.intern(toSegment.substring(start, length));
}
return result;
}
}
/** Lower-level API. Create a PathFragment, interning segments. */
public static PathFragment create(char driveLetter, boolean isAbsolute, String[] segments) {
String[] internedSegments = new String[segments.length];
for (int i = 0; i < segments.length; i++) {
internedSegments[i] = StringCanonicalizer.intern(segments[i]);
}
return createAlreadyInterned(driveLetter, isAbsolute, internedSegments);
}
/** Same as {@link #create(char, boolean, String[])}, except for {@link List}s of segments. */
public static PathFragment create(char driveLetter, boolean isAbsolute, List Package-private because it does not perform a defensive copy of the segments array. Used
* here in PathFragment, and by Path.asFragment() and Path.relativeTo().
*/
static PathFragment createAlreadyInterned(
char driveLetter, boolean isAbsolute, String[] segments) {
return HELPER.createAlreadyInterned(driveLetter, isAbsolute, segments);
}
/** Returns whether the current {@code path} contains a path separator. */
static boolean containsSeparator(String path) {
return HELPER.containsSeparatorChar(path);
}
/**
* Construct a PathFragment from a sequence of other PathFragments. The new fragment will be
* absolute iff the first fragment was absolute.
*/
// TODO(bazel-team): Most usages of this method are wasteful from a garbage perspective. Refactor
// to something better.
public static PathFragment create(PathFragment first, PathFragment second, PathFragment... more) {
String[] segments = new String[sumLengths(first, second, more)];
int offset = 0;
offset += addSegmentsTo(segments, offset, first);
offset += addSegmentsTo(segments, offset, second);
for (PathFragment fragment : more) {
offset += addSegmentsTo(segments, offset, fragment);
}
boolean isAbsolute = first.isAbsolute();
char driveLetter = first.getDriveLetter();
return HELPER.createAlreadyInterned(driveLetter, isAbsolute, segments);
}
// Medium sized builds can easily hold millions of live PathFragments, so the per-instance size of
// PathFragment is a concern.
//
// We have two oop-sized fields (segments, path), and one 4-byte-sized one (hashCode).
//
// If Blaze is run on a jvm with -XX:+UseCompressedOops, each PathFragment instance is 24 bytes
// and so adding any additional field will increase the per-instance size to at least 32 bytes.
//
// If Blaze is run on a jvm with -XX:-UseCompressedOops, each PathFragment instance is 32 bytes
// and so adding any additional field will increase the per-instance size to at least 40 bytes.
//
// Therefore, do not add any additional fields unless you have considered the memory implications.
// The individual path components.
// Does *not* include the Windows drive letter.
protected final String[] segments;
// hashCode and path are lazily initialized but semantically immutable.
private int hashCode;
private String path;
protected PathFragment(String[] segments) {
this.segments = segments;
}
private static int addSegmentsTo(String[] segments, int offset, PathFragment fragment) {
int count = fragment.segmentCount();
System.arraycopy(fragment.segments, 0, segments, offset, count);
return count;
}
private static int sumLengths(PathFragment first, PathFragment second, PathFragment[] more) {
int total = first.segmentCount() + second.segmentCount();
for (PathFragment fragment : more) {
total += fragment.segmentCount();
}
return total;
}
protected Object writeReplace() {
return new PathFragmentSerializationProxy(toString());
}
protected void readObject(ObjectInputStream stream) throws InvalidObjectException {
throw new InvalidObjectException("Serialization is allowed only by proxy");
}
/**
* Returns the path string using '/' as the name-separator character. Returns "" if the path
* is both relative and empty.
*/
public String getPathString() {
// Double-checked locking works, even without volatile, because path is a String, according to:
// http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
if (path == null) {
synchronized (this) {
if (path == null) {
path = StringCanonicalizer.intern(joinSegments(HELPER.getPrimarySeparatorChar()));
}
}
}
return path;
}
/**
* Returns "." if the path fragment is both relative and empty, or {@link
* #getPathString} otherwise.
*/
// TODO(bazel-team): Change getPathString to do this - this behavior makes more sense.
public String getSafePathString() {
return (!isAbsolute() && (segmentCount() == 0)) ? "." : getPathString();
}
/**
* Returns the path string using '/' as the name-separator character, but do so in a way
* unambiguously recognizable as path. In other words, return "." for relative and empty paths,
* and prefix relative paths with one segment by "./".
*
* In this way, a shell will always interpret such a string as path (absolute or relative to
* the working directory) and not as command to be searched for in the search path.
*/
public String getCallablePathString() {
if (isAbsolute()) {
return getPathString();
} else if (segmentCount() == 0) {
return ".";
} else if (segmentCount() == 1) {
return "." + HELPER.getPrimarySeparatorChar() + getPathString();
} else {
return getPathString();
}
}
/**
* Returns a sequence consisting of the {@link #getSafePathString()} return of each item in
* {@code fragments}.
*/
public static Iterable If {@code otherFragment} is absolute, the current path will be ignored;
* otherwise, they will be concatenated. This is a purely syntactic operation,
* with no path normalization or I/O performed.
*/
public PathFragment getRelative(PathFragment otherFragment) {
if (otherFragment == EMPTY_FRAGMENT) {
return this;
}
if (otherFragment.isAbsolute()) {
char driveLetter = getDriveLetter();
return driveLetter == '\0' || otherFragment.getDriveLetter() != '\0'
? otherFragment
: createAlreadyInterned(driveLetter, true, otherFragment.segments);
} else {
return create(this, otherFragment);
}
}
/**
* Returns the path formed by appending the relative or absolute string
* {@code path} to this path.
*
* If the given path string is absolute, the current path will be ignored;
* otherwise, they will be concatenated. This is a purely syntactic operation,
* with no path normalization or I/O performed.
*/
public PathFragment getRelative(String path) {
return getRelative(create(path));
}
/**
* Returns the path formed by appending the single non-special segment "baseName" to this path.
*
* You should almost always use {@link #getRelative} instead, which has the same performance
* characteristics if the given name is a valid base name, and which also works for '.', '..', and
* strings containing '/'.
*
* @throws IllegalArgumentException if {@code baseName} is not a valid base name according to
* {@link #checkBaseName}
*/
public PathFragment getChild(String baseName) {
checkBaseName(baseName);
baseName = StringCanonicalizer.intern(baseName);
String[] newSegments = Arrays.copyOf(segments, segments.length + 1);
newSegments[newSegments.length - 1] = baseName;
return createAlreadyInterned(getDriveLetter(), isAbsolute(), newSegments);
}
/**
* Returns the last segment of this path, or "" for the empty fragment.
*/
public String getBaseName() {
return (segments.length == 0) ? "" : segments[segments.length - 1];
}
/**
* Returns the file extension of this path, excluding the period, or "" if there is no extension.
*/
public String getFileExtension() {
String baseName = getBaseName();
int lastIndex = baseName.lastIndexOf('.');
if (lastIndex != -1) {
return baseName.substring(lastIndex + 1);
}
return "";
}
/**
* Returns a relative path fragment to this path, relative to
* {@code ancestorDirectory}.
*
*
* For example, Note: This method DOES NOT normalize ".." and "." path segments.
*/
public PathFragment getParentDirectory() {
return segments.length == 0 ? null : subFragment(0, segments.length - 1);
}
/**
* Returns true iff {@code prefix}, considered as a list of path segments, is
* a prefix of {@code this}, and that they are both relative or both
* absolute.
*
* This is a reflexive, transitive, anti-symmetric relation (i.e. a partial
* order)
*/
public boolean startsWith(PathFragment prefix) {
if (isAbsolute() != prefix.isAbsolute()
|| this.segments.length < prefix.segments.length
|| (isAbsolute() && getDriveLetter() != prefix.getDriveLetter())) {
return false;
}
return HELPER.segmentsEqual(prefix.segments.length, segments, 0, prefix.segments);
}
/**
* Returns true iff {@code suffix}, considered as a list of path segments, is
* relative and a suffix of {@code this}, or both are absolute and equal.
*
* This is a reflexive, transitive, anti-symmetric relation (i.e. a partial
* order)
*/
public boolean endsWith(PathFragment suffix) {
if ((suffix.isAbsolute() && !suffix.equals(this))
|| this.segments.length < suffix.segments.length) {
return false;
}
int offset = this.segments.length - suffix.segments.length;
return HELPER.segmentsEqual(suffix.segments.length, segments, offset, suffix.segments);
}
private static String[] subarray(String[] array, int start, int length) {
String[] subarray = new String[length];
System.arraycopy(array, start, subarray, 0, length);
return subarray;
}
/**
* Returns a new path fragment that is a sub fragment of this one.
* The sub fragment begins at the specified True both for UNIX-style absolute paths ("/foo") and Windows-style ("C:/foo"). False for a
* Windows-style volume label ("C:") which is actually a relative path.
*/
public abstract boolean isAbsolute();
/**
* Returns the segments of this path fragment. This array should not be
* modified.
*/
String[] segments() {
return segments;
}
public ImmutableListx.relativeTo(z) == y
implies
* z.getRelative(y) == x
.
* "foo/bar/wiz".relativeTo("foo")
* returns "bar/wiz"
.
*/
public PathFragment relativeTo(PathFragment ancestorDirectory) {
String[] ancestorSegments = ancestorDirectory.segments();
int ancestorLength = ancestorSegments.length;
if (isAbsolute() != ancestorDirectory.isAbsolute() || segments.length < ancestorLength) {
throw new IllegalArgumentException("PathFragment " + this
+ " is not beneath " + ancestorDirectory);
}
if (!HELPER.segmentsEqual(ancestorLength, segments, 0, ancestorSegments)) {
throw new IllegalArgumentException(
"PathFragment " + this + " is not beneath " + ancestorDirectory);
}
int length = segments.length - ancestorLength;
String[] resultSegments = subarray(segments, ancestorLength, length);
return createAlreadyInterned('\0', false, resultSegments);
}
/**
* Returns a relative path fragment to this path, relative to {@code path}.
*/
public PathFragment relativeTo(String path) {
return relativeTo(create(path));
}
/**
* Returns a new PathFragment formed by appending {@code newName} to the
* parent directory. Null is returned iff this method is called on a
* PathFragment with zero segments. If {@code newName} designates an absolute path,
* the value of {@code this} will be ignored and a PathFragment corresponding to
* {@code newName} will be returned. This behavior is consistent with the behavior of
* {@link #getRelative(String)}.
*/
public PathFragment replaceName(String newName) {
return segments.length == 0 ? null : getParentDirectory().getRelative(newName);
}
/**
* Returns a path representing the parent directory of this path,
* or null iff this Path represents the root of the filesystem.
*
* beginIndex
segment
* and ends at the segment at index endIndex - 1
. Thus the number
* of segments in the new PathFragment is endIndex - beginIndex
.
*
* @param beginIndex the beginning index, inclusive.
* @param endIndex the ending index, exclusive.
* @return the specified sub fragment, never null.
* @exception IndexOutOfBoundsException if the
* beginIndex
is negative, or
* endIndex
is larger than the length of
* this String
object, or
* beginIndex
is larger than
* endIndex
.
*/
public PathFragment subFragment(int beginIndex, int endIndex) {
int count = segments.length;
if ((beginIndex < 0) || (beginIndex > endIndex) || (endIndex > count)) {
throw new IndexOutOfBoundsException(String.format("path: %s, beginIndex: %d endIndex: %d",
toString(), beginIndex, endIndex));
}
boolean isAbsolute = (beginIndex == 0) && isAbsolute();
return ((beginIndex == 0) && (endIndex == count))
? this
: createAlreadyInterned(
getDriveLetter(), isAbsolute, subarray(segments, beginIndex, endIndex - beginIndex));
}
/**
* Returns true iff the path represented by this object is absolute.
*
*