From aac13242c1e2bb6d1870e1284795bd3ca370984c Mon Sep 17 00:00:00 2001 From: nharmata Date: Mon, 24 Apr 2017 17:41:23 +0200 Subject: Make PathFragment an abstract class. There are now four concrete implementations: RelativeUnixPathFragment, AbsoluteUnixPathFragment, RelativeWindowsPathFragment, AbsoluteWindowsPathFragment. Goals: -Reduce memory usage of PathFragment on non-Windows platforms while maintaining existing semantics. -Make a few simple performance improvements along the way. -Add TODOs for a few more simple performance improvements. -Open the way for reducing code complexity of PathFragment. All of the Windows-specific stuff ought not complicate the code so much. Non goals: -Make the entire codebase as pretty as possible wrt PathFragment & Windows. -Make PathFragment usage more sane in general (e.g. change semantics to ban coexistence of Windows and Unix PathFragments). -Optimize PathFragment as much as possible wrt memory or even in any other dimensions (e.g. gc churn, cpu). To elaborate, the primary motivation is per-instance memory usage of PathFragment on Unix platforms: Before this change ------------------ +UseCompressedOops --> 32 bytes per instance -UseCompressedOops --> 40 bytes per instance After this change ------------------ +UseCompressedOops --> 24 bytes per instance -UseCompressedOops --> 32 bytes per instance Since Bazel can retain lots of PathFragments, the memory savings of this CL are fairly large. RELNOTES: None PiperOrigin-RevId: 154052905 --- .../devtools/build/lib/syntax/EvalUtils.java | 2 +- .../com/google/devtools/build/lib/vfs/Path.java | 8 +- .../devtools/build/lib/vfs/PathFragment.java | 460 +++++++++------------ .../devtools/build/lib/vfs/UnixPathFragment.java | 220 ++++++++++ .../build/lib/vfs/WindowsPathFragment.java | 252 +++++++++++ 5 files changed, 666 insertions(+), 276 deletions(-) create mode 100644 src/main/java/com/google/devtools/build/lib/vfs/UnixPathFragment.java create mode 100644 src/main/java/com/google/devtools/build/lib/vfs/WindowsPathFragment.java (limited to 'src/main/java/com/google/devtools/build/lib') diff --git a/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java b/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java index 75b9a6b91e..34ab3f3fd1 100644 --- a/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java +++ b/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java @@ -152,7 +152,7 @@ public final class EvalUtils { || SkylarkInterfaceUtils.getSkylarkModule(c) != null || ImmutableMap.class.isAssignableFrom(c) // will be converted to SkylarkDict || NestedSet.class.isAssignableFrom(c) // will be converted to SkylarkNestedSet - || c.equals(PathFragment.class); // other known class + || PathFragment.class.isAssignableFrom(c); // other known class } // TODO(bazel-team): move the following few type-related functions to SkylarkType diff --git a/src/main/java/com/google/devtools/build/lib/vfs/Path.java b/src/main/java/com/google/devtools/build/lib/vfs/Path.java index ac8b756696..bf8c612d66 100644 --- a/src/main/java/com/google/devtools/build/lib/vfs/Path.java +++ b/src/main/java/com/google/devtools/build/lib/vfs/Path.java @@ -724,9 +724,7 @@ public class Path implements Comparable, Serializable { return this; } else if (path.equals("..")) { return isTopLevelDirectory() ? this : parent; - } else if (path.indexOf('/') != -1) { - return getRelative(PathFragment.create(path)); - } else if (path.indexOf(PathFragment.EXTRA_SEPARATOR_CHAR) != -1) { + } else if (PathFragment.containsSeparator(path)) { return getRelative(PathFragment.create(path)); } else { return getCachedChildPath(path); @@ -745,7 +743,7 @@ public class Path implements Comparable, Serializable { /** Returns an absolute PathFragment representing this path. */ public PathFragment asFragment() { - return PathFragment.createNoClone('\0', true, getSegments()); + return PathFragment.createAlreadyInterned('\0', true, getSegments()); } /** @@ -777,7 +775,7 @@ public class Path implements Comparable, Serializable { currentPath = currentPath.getParentDirectory(); } if (ancestorPath.equals(currentPath)) { - return PathFragment.createNoClone('\0', false, resultSegments); + return PathFragment.createAlreadyInterned('\0', false, resultSegments); } } } diff --git a/src/main/java/com/google/devtools/build/lib/vfs/PathFragment.java b/src/main/java/com/google/devtools/build/lib/vfs/PathFragment.java index e08a6d4465..41e45b1944 100644 --- a/src/main/java/com/google/devtools/build/lib/vfs/PathFragment.java +++ b/src/main/java/com/google/devtools/build/lib/vfs/PathFragment.java @@ -14,7 +14,6 @@ package com.google.devtools.build.lib.vfs; import com.google.common.base.Function; -import com.google.common.base.Joiner; import com.google.common.base.Predicate; import com.google.common.collect.ImmutableList; import com.google.common.collect.ImmutableSet; @@ -33,26 +32,26 @@ import java.util.List; import java.util.Set; /** - * This class represents an immutable UNIX filesystem path, which may be absolute or relative. The - * path is maintained as a simple ordered list of path segment strings. + * 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 + *

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 @ThreadSafe -public final class PathFragment implements Comparable, Serializable { +@Immutable +@ThreadSafe +public abstract class PathFragment implements Comparable, Serializable { + private static final Helper HELPER = + OS.getCurrent() == OS.WINDOWS ? WindowsPathFragment.HELPER : UnixPathFragment.HELPER; - public static final int INVALID_SEGMENT = -1; - - public static final char SEPARATOR_CHAR = '/'; + public static final char SEPARATOR_CHAR = HELPER.getPrimarySeparatorChar(); - public static final char EXTRA_SEPARATOR_CHAR = - (OS.getCurrent() == OS.WINDOWS) ? '\\' : '/'; + public static final int INVALID_SEGMENT = -1; public static final String ROOT_DIR = "/"; @@ -83,13 +82,96 @@ public final class PathFragment implements Comparable, Serializabl } }; + /** + * A helper object for manipulating the various internal {@link PathFragment} implementations. + * + *

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 createNoClone(driveLetter, isAbsolute, internedSegments); + return createAlreadyInterned(driveLetter, isAbsolute, internedSegments); } /** Same as {@link #create(char, boolean, String[])}, except for {@link List}s of segments. */ @@ -98,7 +180,7 @@ public final class PathFragment implements Comparable, Serializabl for (int i = 0; i < segments.size(); i++) { internedSegments[i] = StringCanonicalizer.intern(segments.get(i)); } - return createNoClone(driveLetter, isAbsolute, internedSegments); + return createAlreadyInterned(driveLetter, isAbsolute, internedSegments); } /** @@ -106,112 +188,80 @@ public final class PathFragment implements Comparable, Serializabl * relative UNIX path. Does not support Windows-style Files. */ public static PathFragment create(File path) { - return new PathFragment(path); + return HELPER.create(path.getPath()); } /** * Construct a PathFragment from a string, which is an absolute or relative UNIX or Windows path. */ public static PathFragment create(String path) { - return new PathFragment(path); + return HELPER.create(path); } /** - * Constructs a PathFragment, taking ownership of segments. Package-private, - * because it does not perform a defensive clone of the segments array. Used + * Constructs a PathFragment, taking ownership of {@code segments} and assuming the {@link + * String}s within have already been interned. + * + *

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 createNoClone( + static PathFragment createAlreadyInterned( char driveLetter, boolean isAbsolute, String[] segments) { - return new PathFragment(driveLetter, isAbsolute, 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. + * 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) { - return new PathFragment(first, second, more); - } - - // We have 3 word-sized fields (segments, hashCode and path), and 2 - // byte-sized ones, which fits in 16 bytes. Object sizes are rounded - // to 16 bytes. Medium sized builds can easily hold millions of - // live PathFragments, so do not add further fields on a whim. + 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. - private final String[] segments; - - // 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. - private final boolean isAbsolute; - - // Upper case Windows drive letter, or '\0' if none or unknown. - private final char driveLetter; + protected final String[] segments; // hashCode and path are lazily initialized but semantically immutable. private int hashCode; private String path; - private PathFragment(String path) { - this.driveLetter = - (OS.getCurrent() == OS.WINDOWS - && path.length() >= 2 - && path.charAt(1) == ':' - && Character.isLetter(path.charAt(0))) - ? Character.toUpperCase(path.charAt(0)) - : '\0'; - - if (driveLetter != '\0') { - path = path.substring(2); - // TODO(bazel-team): Decide what to do about non-absolute paths with a volume name, e.g. C:x. - } - this.isAbsolute = path.length() > 0 && isSeparator(path.charAt(0)); - this.segments = segment(path, isAbsolute ? 1 : 0); - } - - private static boolean isSeparator(char c) { - return c == SEPARATOR_CHAR || c == EXTRA_SEPARATOR_CHAR; - } - - private PathFragment(File path) { - this(path.getPath()); - } - - private PathFragment(char driveLetter, boolean isAbsolute, String[] segments) { - driveLetter = Character.toUpperCase(driveLetter); - if (OS.getCurrent() == OS.WINDOWS - && segments.length > 0 - && segments[0].length() == 2 - && Character.toUpperCase(segments[0].charAt(0)) == driveLetter - && segments[0].charAt(1) == ':') { - throw new IllegalStateException( - String.format( - "the drive letter should not be a path segment; drive='%c', segments=[%s]", - driveLetter, Joiner.on(", ").join(segments))); - } - this.driveLetter = driveLetter; - this.isAbsolute = isAbsolute; + protected PathFragment(String[] segments) { this.segments = segments; } - private PathFragment(PathFragment first, PathFragment second, PathFragment... more) { - // TODO(bazel-team): The handling of absolute path fragments in this constructor is unexpected. - this.segments = new String[sumLengths(first, second, more)]; - int offset = 0; - offset += addSegments(offset, first); - offset += addSegments(offset, second); - for (PathFragment fragment : more) { - offset += addSegments(offset, fragment); - } - this.isAbsolute = first.isAbsolute; - this.driveLetter = first.driveLetter; - } - - private int addSegments(int offset, PathFragment fragment) { + private static int addSegmentsTo(String[] segments, int offset, PathFragment fragment) { int count = fragment.segmentCount(); - System.arraycopy(fragment.segments, 0, this.segments, offset, count); + System.arraycopy(fragment.segments, 0, segments, offset, count); return count; } @@ -223,60 +273,11 @@ public final class PathFragment implements Comparable, Serializabl return total; } - /** - * Segments the string passed in as argument and returns an array of strings. - * The split is performed along occurrences of (sequences of) the slash - * character. - * - * @param toSegment the string to segment - * @param offset how many characters from the start of the string to ignore. - */ - private static String[] segment(String toSegment, int offset) { - int length = toSegment.length(); - - // Handle "/" and "" quickly. - if (length == offset) { - return new String[0]; - } - - // 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; - } - - private Object writeReplace() { + protected Object writeReplace() { return new PathFragmentSerializationProxy(toString()); } - private void readObject(ObjectInputStream stream) throws InvalidObjectException { + protected void readObject(ObjectInputStream stream) throws InvalidObjectException { throw new InvalidObjectException("Serialization is allowed only by proxy"); } @@ -290,7 +291,7 @@ public final class PathFragment implements Comparable, Serializabl if (path == null) { synchronized (this) { if (path == null) { - path = StringCanonicalizer.intern(joinSegments(SEPARATOR_CHAR)); + path = StringCanonicalizer.intern(joinSegments(HELPER.getPrimarySeparatorChar())); } } } @@ -303,7 +304,7 @@ public final class PathFragment implements Comparable, Serializabl */ // TODO(bazel-team): Change getPathString to do this - this behavior makes more sense. public String getSafePathString() { - return (!isAbsolute && (segmentCount() == 0)) ? "." : getPathString(); + return (!isAbsolute() && (segmentCount() == 0)) ? "." : getPathString(); } /** @@ -315,12 +316,12 @@ public final class PathFragment implements Comparable, Serializabl * the working directory) and not as command to be searched for in the search path. */ public String getCallablePathString() { - if (isAbsolute) { + if (isAbsolute()) { return getPathString(); } else if (segmentCount() == 0) { return "."; } else if (segmentCount() == 1) { - return "." + SEPARATOR_CHAR + getPathString(); + return "." + HELPER.getPrimarySeparatorChar() + getPathString(); } else { return getPathString(); } @@ -363,7 +364,7 @@ public final class PathFragment implements Comparable, Serializabl } private String joinSegments(char separatorChar) { - if (segments.length == 0 && isAbsolute) { + if (segments.length == 0 && isAbsolute()) { return windowsVolume() + ROOT_DIR; } @@ -372,17 +373,17 @@ public final class PathFragment implements Comparable, Serializabl // we do not have to expand the capacity of the StringBuilder. // Heuristically, this estimate is right for about 99% of the time. int estimateSize = - ((driveLetter != '\0') ? 2 : 0) - + ((segments.length == 0) ? 0 : (segments.length + 1) * 20); + ((getDriveLetter() != '\0') ? 2 : 0) + + ((segments.length == 0) ? 0 : (segments.length + 1) * 20); StringBuilder result = new StringBuilder(estimateSize); - if (isAbsolute) { + if (isAbsolute()) { // Only print the Windows volume label if the PathFragment is absolute. Do not print relative // Windows paths like "C:foo/bar", it would break all kinds of things, e.g. glob(). result.append(windowsVolume()); } boolean initialSegment = true; for (String segment : segments) { - if (!initialSegment || isAbsolute) { + if (!initialSegment || isAbsolute()) { result.append(separatorChar); } initialSegment = false; @@ -437,7 +438,8 @@ public final class PathFragment implements Comparable, Serializabl return this; } - return createNoClone(driveLetter, isAbsolute, subarray(scratchSegments, 0, segmentCount)); + return HELPER.createAlreadyInterned( + getDriveLetter(), isAbsolute(), subarray(scratchSegments, 0, segmentCount)); } /** @@ -454,9 +456,10 @@ public final class PathFragment implements Comparable, Serializabl } if (otherFragment.isAbsolute()) { - return this.driveLetter == '\0' || otherFragment.driveLetter != '\0' + char driveLetter = getDriveLetter(); + return driveLetter == '\0' || otherFragment.getDriveLetter() != '\0' ? otherFragment - : createNoClone(this.driveLetter, true, otherFragment.segments); + : createAlreadyInterned(driveLetter, true, otherFragment.segments); } else { return create(this, otherFragment); } @@ -490,7 +493,7 @@ public final class PathFragment implements Comparable, Serializabl baseName = StringCanonicalizer.intern(baseName); String[] newSegments = Arrays.copyOf(segments, segments.length + 1); newSegments[newSegments.length - 1] = baseName; - return createNoClone(driveLetter, isAbsolute, newSegments); + return createAlreadyInterned(getDriveLetter(), isAbsolute(), newSegments); } /** @@ -528,20 +531,19 @@ public final class PathFragment implements Comparable, Serializabl String[] ancestorSegments = ancestorDirectory.segments(); int ancestorLength = ancestorSegments.length; - if (isAbsolute != ancestorDirectory.isAbsolute() - || segments.length < ancestorLength) { + if (isAbsolute() != ancestorDirectory.isAbsolute() || segments.length < ancestorLength) { throw new IllegalArgumentException("PathFragment " + this + " is not beneath " + ancestorDirectory); } - if (!segmentsEqual(ancestorLength, segments, 0, ancestorSegments)) { + 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 createNoClone('\0', false, resultSegments); + return createAlreadyInterned('\0', false, resultSegments); } /** @@ -582,12 +584,12 @@ public final class PathFragment implements Comparable, Serializabl * order) */ public boolean startsWith(PathFragment prefix) { - if (this.isAbsolute != prefix.isAbsolute + if (isAbsolute() != prefix.isAbsolute() || this.segments.length < prefix.segments.length - || (isAbsolute && this.driveLetter != prefix.driveLetter)) { + || (isAbsolute() && getDriveLetter() != prefix.getDriveLetter())) { return false; } - return segmentsEqual(prefix.segments.length, segments, 0, prefix.segments); + return HELPER.segmentsEqual(prefix.segments.length, segments, 0, prefix.segments); } /** @@ -598,12 +600,12 @@ public final class PathFragment implements Comparable, Serializabl * order) */ public boolean endsWith(PathFragment suffix) { - if ((suffix.isAbsolute && !suffix.equals(this)) || - this.segments.length < suffix.segments.length) { + if ((suffix.isAbsolute() && !suffix.equals(this)) + || this.segments.length < suffix.segments.length) { return false; } int offset = this.segments.length - suffix.segments.length; - return segmentsEqual(suffix.segments.length, segments, offset, suffix.segments); + return HELPER.segmentsEqual(suffix.segments.length, segments, offset, suffix.segments); } private static String[] subarray(String[] array, int start, int length) { @@ -634,21 +636,20 @@ public final class PathFragment implements Comparable, Serializabl throw new IndexOutOfBoundsException(String.format("path: %s, beginIndex: %d endIndex: %d", toString(), beginIndex, endIndex)); } - boolean isAbsolute = (beginIndex == 0) && this.isAbsolute; + boolean isAbsolute = (beginIndex == 0) && isAbsolute(); return ((beginIndex == 0) && (endIndex == count)) ? this - : createNoClone( - driveLetter, - isAbsolute, - subarray(segments, beginIndex, endIndex - beginIndex)); + : createAlreadyInterned( + getDriveLetter(), isAbsolute, subarray(segments, beginIndex, endIndex - beginIndex)); } /** * Returns true iff the path represented by this object is absolute. + * + *

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 boolean isAbsolute() { - return isAbsolute; - } + public abstract boolean isAbsolute(); /** * Returns the segments of this path fragment. This array should not be @@ -662,14 +663,12 @@ public final class PathFragment implements Comparable, Serializabl return ImmutableList.copyOf(segments); } - public String windowsVolume() { - return (driveLetter != '\0') ? driveLetter + ":" : ""; - } + public abstract String windowsVolume(); /** Return the drive letter or '\0' if not applicable. */ - public char getDriveLetter() { - return driveLetter; - } + // TODO(bazel-team): This doesn't need to pollute the PathFragment interface (ditto for + // windowsVolume). + public abstract char getDriveLetter(); /** * Returns the number of segments in this path. @@ -716,16 +715,12 @@ public final class PathFragment implements Comparable, Serializabl * same segments and drive letter. */ public PathFragment toRelative() { - Preconditions.checkArgument(isAbsolute); - return createNoClone(driveLetter, false, segments); - } - - private boolean isEmpty() { - return !isAbsolute && segments.length == 0; + Preconditions.checkArgument(isAbsolute()); + return HELPER.createAlreadyInterned(getDriveLetter(), false, segments); } @Override - public int hashCode() { + public final int hashCode() { // We use the hash code caching strategy employed by java.lang.String. There are three subtle // things going on here: // @@ -737,104 +732,29 @@ public final class PathFragment implements Comparable, Serializabl // first one to compute and cache the hash code. // // (3) Moreover, since 'hashCode' is non-volatile, the cached hash code value written from one - // thread may not be visible by another. + // thread may not be visible by another. Note that we don't need to worry about multiple + // inefficient reads of 'hashCode' on the same thread since it's non-volatile. // // All three of these issues are benign from a correctness perspective; in the end we have no // overhead from synchronization, at the cost of potentially computing the hash code more than // once. - int h = hashCode; - boolean isWindows = OS.getCurrent() == OS.WINDOWS; - if (h == 0) { - h = Boolean.valueOf(isAbsolute).hashCode(); - for (String segment : segments) { - int segmentHash = isWindows ? segment.toLowerCase().hashCode() : segment.hashCode(); - h = h * 31 + segmentHash; - } - if (!isEmpty()) { - h = h * 31 + Character.valueOf(driveLetter).hashCode(); - } - hashCode = h; + if (hashCode == 0) { + hashCode = computeHashCode(); } - return h; + return hashCode; } - @Override - public boolean equals(Object other) { - if (this == other) { - return true; - } - if (!(other instanceof PathFragment)) { - return false; - } - PathFragment otherPath = (PathFragment) other; - if (isEmpty() && otherPath.isEmpty()) { - return true; - } else { - return isAbsolute == otherPath.isAbsolute - && driveLetter == otherPath.driveLetter - && segments.length == otherPath.segments.length - && segmentsEqual(segments.length, segments, 0, otherPath.segments); - } - } + protected abstract int computeHashCode(); - private static boolean segmentsEqual( - int length, String[] segments1, int offset1, String[] segments2) { - if ((segments1.length - offset1) < length || segments2.length < length) { - return false; - } - boolean isWindows = OS.getCurrent() == OS.WINDOWS; - for (int i = 0; i < length; ++i) { - String seg1 = segments1[i + offset1]; - String seg2 = segments2[i]; - if ((seg1 == null) != (seg2 == null)) { - return false; - } - if (seg1 == null) { - continue; - } - if (isWindows) { - seg1 = seg1.toLowerCase(); - seg2 = seg2.toLowerCase(); - } - if (!seg1.equals(seg2)) { - return false; - } - } - return true; - } + @Override + public abstract boolean equals(Object other); /** * Compares two PathFragments using the lexicographical order. */ @Override public int compareTo(PathFragment p2) { - if (isAbsolute != p2.isAbsolute) { - return isAbsolute ? -1 : 1; - } - int cmp = Character.compare(driveLetter, p2.driveLetter); - if (cmp != 0) { - return cmp; - } - PathFragment p1 = this; - String[] segments1 = p1.segments; - String[] segments2 = p2.segments; - int len1 = segments1.length; - int len2 = segments2.length; - int n = Math.min(len1, len2); - boolean isWindows = OS.getCurrent() == OS.WINDOWS; - for (int i = 0; i < n; i++) { - String seg1 = segments1[i]; - String seg2 = segments2[i]; - if (isWindows) { - seg1 = seg1.toLowerCase(); - seg2 = seg2.toLowerCase(); - } - cmp = seg1.compareTo(seg2); - if (cmp != 0) { - return cmp; - } - } - return len1 - len2; + return HELPER.compare(this, p2); } @Override diff --git a/src/main/java/com/google/devtools/build/lib/vfs/UnixPathFragment.java b/src/main/java/com/google/devtools/build/lib/vfs/UnixPathFragment.java new file mode 100644 index 0000000000..d83386affb --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/vfs/UnixPathFragment.java @@ -0,0 +1,220 @@ +// Copyright 2017 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 com.google.devtools.build.lib.util.Preconditions; +import java.io.InvalidObjectException; +import java.io.ObjectInputStream; + +/** + * Abstract base class for {@link PathFragment} instances that will be allocated when Blaze is run + * on a non-Windows platform. + */ +abstract class UnixPathFragment extends PathFragment { + static final Helper HELPER = new Helper(); + /** + * We have two concrete subclasses with zero per-instance additional memory overhead. Do not add + * any fields. See the comment on memory use in PathFragment for details on the current + * per-instance memory usage. + */ + + protected UnixPathFragment(String[] segments) { + super(segments); + } + + @Override + protected int computeHashCode() { + int h = 0; + for (String segment : segments) { + int segmentHash = segment.hashCode(); + h = h * 31 + segmentHash; + } + return h; + } + + @Override + public String windowsVolume() { + return ""; + } + + @Override + public char getDriveLetter() { + return '\0'; + } + + private static class Helper extends PathFragment.Helper { + private static final char SEPARATOR_CHAR = '/'; + + @Override + PathFragment create(String path) { + boolean isAbsolute = path.length() > 0 && isSeparator(path.charAt(0)); + return isAbsolute + ? new AbsoluteUnixPathFragment(segment(path, 1)) + : new RelativeUnixPathFragment(segment(path, 0)); + } + + @Override + PathFragment createAlreadyInterned(char driveLetter, boolean isAbsolute, String[] segments) { + Preconditions.checkState(driveLetter == '\0', driveLetter); + return isAbsolute + ? new AbsoluteUnixPathFragment(segments) + : new RelativeUnixPathFragment(segments); + } + + @Override + char getPrimarySeparatorChar() { + return SEPARATOR_CHAR; + } + + @Override + boolean isSeparator(char c) { + return c == SEPARATOR_CHAR; + } + + @Override + boolean containsSeparatorChar(String path) { + return path.indexOf(SEPARATOR_CHAR) != -1; + } + + @Override + boolean segmentsEqual(int length, String[] segments1, int offset1, String[] segments2) { + if ((segments1.length - offset1) < length || segments2.length < length) { + return false; + } + for (int i = 0; i < length; ++i) { + String seg1 = segments1[i + offset1]; + String seg2 = segments2[i]; + if ((seg1 == null) != (seg2 == null)) { + return false; + } + if (seg1 == null) { + continue; + } + if (!seg1.equals(seg2)) { + return false; + } + } + return true; + } + + @Override + protected int compare(PathFragment pathFragment1, PathFragment pathFragment2) { + if (pathFragment1.isAbsolute() != pathFragment2.isAbsolute()) { + return pathFragment1.isAbsolute() ? -1 : 1; + } + String[] segments1 = pathFragment1.segments(); + String[] segments2 = pathFragment2.segments(); + int len1 = segments1.length; + int len2 = segments2.length; + int n = Math.min(len1, len2); + for (int i = 0; i < n; i++) { + String seg1 = segments1[i]; + String seg2 = segments2[i]; + int cmp = seg1.compareTo(seg2); + if (cmp != 0) { + return cmp; + } + } + return len1 - len2; + } + } + + private static final class AbsoluteUnixPathFragment extends UnixPathFragment { + private AbsoluteUnixPathFragment(String[] segments) { + super(segments); + } + + @Override + public boolean isAbsolute() { + return true; + } + + @Override + protected int computeHashCode() { + int h = Boolean.TRUE.hashCode(); + h = h * 31 + super.computeHashCode(); + return h; + } + + @Override + public boolean equals(Object other) { + if (!(other instanceof AbsoluteUnixPathFragment)) { + return false; + } + if (this == other) { + return true; + } + AbsoluteUnixPathFragment otherAbsoluteUnixPathFragment = (AbsoluteUnixPathFragment) other; + return HELPER.segmentsEqual(this.segments, otherAbsoluteUnixPathFragment.segments); + } + + // Java serialization looks for the presence of this method in the concrete class. It is not + // inherited from the parent class. + @Override + protected Object writeReplace() { + return super.writeReplace(); + } + + // Java serialization looks for the presence of this method in the concrete class. It is not + // inherited from the parent class. + @Override + protected void readObject(ObjectInputStream stream) throws InvalidObjectException { + super.readObject(stream); + } + } + + private static final class RelativeUnixPathFragment extends UnixPathFragment { + private RelativeUnixPathFragment(String[] segments) { + super(segments); + } + + @Override + public boolean isAbsolute() { + return false; + } + + @Override + protected int computeHashCode() { + int h = Boolean.FALSE.hashCode(); + h = h * 31 + super.computeHashCode(); + return h; + } + + @Override + public boolean equals(Object other) { + if (!(other instanceof RelativeUnixPathFragment)) { + return false; + } + if (this == other) { + return true; + } + RelativeUnixPathFragment otherRelativeUnixPathFragment = (RelativeUnixPathFragment) other; + return HELPER.segmentsEqual(this.segments, otherRelativeUnixPathFragment.segments); + } + + // Java serialization looks for the presence of this method in the concrete class. It is not + // inherited from the parent class. + @Override + protected Object writeReplace() { + return super.writeReplace(); + } + + // Java serialization looks for the presence of this method in the concrete class. It is not + // inherited from the parent class. + @Override + protected void readObject(ObjectInputStream stream) throws InvalidObjectException { + super.readObject(stream); + } + } +} diff --git a/src/main/java/com/google/devtools/build/lib/vfs/WindowsPathFragment.java b/src/main/java/com/google/devtools/build/lib/vfs/WindowsPathFragment.java new file mode 100644 index 0000000000..4f94535acf --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/vfs/WindowsPathFragment.java @@ -0,0 +1,252 @@ +// Copyright 2017 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 java.io.InvalidObjectException; +import java.io.ObjectInputStream; + +/** + * Abstract base class for {@link PathFragment} instances that will be allocated when Blaze is run + * on a Windows platform. + */ +abstract class WindowsPathFragment extends PathFragment { + static final Helper HELPER = new Helper(); + + protected final char driveLetter; + + protected WindowsPathFragment(char driveLetter, String[] segments) { + super(segments); + this.driveLetter = driveLetter; + } + + @Override + public String windowsVolume() { + return (driveLetter != '\0') ? driveLetter + ":" : ""; + } + + @Override + public char getDriveLetter() { + return driveLetter; + } + + @Override + protected int computeHashCode() { + int h = 0; + for (String segment : segments) { + int segmentHash = segment.toLowerCase().hashCode(); + h = h * 31 + segmentHash; + } + return h; + } + + private static class Helper extends PathFragment.Helper { + private static final char SEPARATOR_CHAR = '/'; + // TODO(laszlocsomor): Lots of internal PathFragment operations, e.g. getPathString, use the + // primary separator char and do not use this. + private static final char EXTRA_SEPARATOR_CHAR = '\\'; + + @Override + PathFragment create(String path) { + // TODO(laszlocsomor): Character#isLetter returns true for some non ASCII characters. + char driveLetter = + path.length() >= 2 && path.charAt(1) == ':' && Character.isLetter(path.charAt(0)) + ? Character.toUpperCase(path.charAt(0)) + : '\0'; + if (driveLetter != '\0') { + path = path.substring(2); + // TODO(bazel-team): Decide what to do about non-absolute paths with a volume name, e.g. + // C:x. + } + boolean isAbsolute = path.length() > 0 && isSeparator(path.charAt(0)); + return isAbsolute + ? new AbsoluteWindowsPathFragment(driveLetter, segment(path, 1)) + : new RelativeWindowsPathFragment(driveLetter, segment(path, 0)); + } + + @Override + PathFragment createAlreadyInterned(char driveLetter, boolean isAbsolute, String[] segments) { + return isAbsolute + ? new AbsoluteWindowsPathFragment(driveLetter, segments) + : new RelativeWindowsPathFragment(driveLetter, segments); + } + + @Override + char getPrimarySeparatorChar() { + return SEPARATOR_CHAR; + } + + @Override + boolean isSeparator(char c) { + return c == SEPARATOR_CHAR || c == EXTRA_SEPARATOR_CHAR; + } + + @Override + boolean containsSeparatorChar(String path) { + // TODO(laszlocsomor): This is inefficient. + return path.indexOf(SEPARATOR_CHAR) != -1 || path.indexOf(EXTRA_SEPARATOR_CHAR) != -1; + } + + @Override + boolean segmentsEqual(int length, String[] segments1, int offset1, String[] segments2) { + if ((segments1.length - offset1) < length || segments2.length < length) { + return false; + } + for (int i = 0; i < length; ++i) { + String seg1 = segments1[i + offset1]; + String seg2 = segments2[i]; + if ((seg1 == null) != (seg2 == null)) { + return false; + } + if (seg1 == null) { + continue; + } + // TODO(laszlocsomor): The calls to String#toLowerCase are inefficient and potentially + // repeated too. Also, why not use String#equalsIgnoreCase. + seg1 = seg1.toLowerCase(); + seg2 = seg2.toLowerCase(); + if (!seg1.equals(seg2)) { + return false; + } + } + return true; + } + + @Override + protected int compare(PathFragment pathFragment1, PathFragment pathFragment2) { + if (pathFragment1.isAbsolute() != pathFragment2.isAbsolute()) { + return pathFragment1.isAbsolute() ? -1 : 1; + } + int cmp = Character.compare(pathFragment1.getDriveLetter(), pathFragment2.getDriveLetter()); + if (cmp != 0) { + return cmp; + } + String[] segments1 = pathFragment1.segments(); + String[] segments2 = pathFragment2.segments(); + int len1 = segments1.length; + int len2 = segments2.length; + int n = Math.min(len1, len2); + for (int i = 0; i < n; i++) { + String seg1 = segments1[i].toLowerCase(); + String seg2 = segments2[i].toLowerCase(); + cmp = seg1.compareTo(seg2); + if (cmp != 0) { + return cmp; + } + } + return len1 - len2; + } + } + + private static final class AbsoluteWindowsPathFragment extends WindowsPathFragment { + private AbsoluteWindowsPathFragment(char driveLetter, String[] segments) { + super(driveLetter, segments); + } + + @Override + public boolean isAbsolute() { + return true; + } + + @Override + protected int computeHashCode() { + int h = Boolean.TRUE.hashCode(); + h = h * 31 + super.computeHashCode(); + h = h * 31 + Character.valueOf(getDriveLetter()).hashCode(); + return h; + } + + @Override + public boolean equals(Object other) { + if (!(other instanceof AbsoluteWindowsPathFragment)) { + return false; + } + if (this == other) { + return true; + } + AbsoluteWindowsPathFragment otherAbsoluteWindowsPathFragment = + (AbsoluteWindowsPathFragment) other; + return this.driveLetter == otherAbsoluteWindowsPathFragment.driveLetter + && HELPER.segmentsEqual(this.segments, otherAbsoluteWindowsPathFragment.segments); + } + + // Java serialization looks for the presence of this method in the concrete class. It is not + // inherited from the parent class. + @Override + protected Object writeReplace() { + return super.writeReplace(); + } + + // Java serialization looks for the presence of this method in the concrete class. It is not + // inherited from the parent class. + @Override + protected void readObject(ObjectInputStream stream) throws InvalidObjectException { + super.readObject(stream); + } + } + + private static final class RelativeWindowsPathFragment extends WindowsPathFragment { + private RelativeWindowsPathFragment(char driveLetter, String[] segments) { + super(driveLetter, segments); + } + + @Override + public boolean isAbsolute() { + return false; + } + + @Override + protected int computeHashCode() { + int h = Boolean.FALSE.hashCode(); + h = h * 31 + super.computeHashCode(); + if (!isEmpty()) { + h = h * 31 + Character.valueOf(getDriveLetter()).hashCode(); + } + return h; + } + + @Override + public boolean equals(Object other) { + if (!(other instanceof RelativeWindowsPathFragment)) { + return false; + } + if (this == other) { + return true; + } + RelativeWindowsPathFragment otherRelativeWindowsPathFragment = + (RelativeWindowsPathFragment) other; + return isEmpty() && otherRelativeWindowsPathFragment.isEmpty() + ? true + : this.driveLetter == otherRelativeWindowsPathFragment.driveLetter + && HELPER.segmentsEqual(this.segments, otherRelativeWindowsPathFragment.segments); + } + + private boolean isEmpty() { + return segmentCount() == 0; + } + + // Java serialization looks for the presence of this method in the concrete class. It is not + // inherited from the parent class. + @Override + protected Object writeReplace() { + return super.writeReplace(); + } + + // Java serialization looks for the presence of this method in the concrete class. It is not + // inherited from the parent class. + @Override + protected void readObject(ObjectInputStream stream) throws InvalidObjectException { + super.readObject(stream); + } + } +} -- cgit v1.2.3