Repository: bazelbuild/bazel
Issue: incompatible_windows_case_ignoring_glob: enables case-insensitive glob() on Windows
Labels: P2
area-Windows
incompatible-change
team-OSS

# Description

The `--[no]incompatible_windows_case_ignoring_glob` shall control whether `glob()` is case-sensitive (false) or case-ignoring (true) on Windows.

## Affected platforms

This flag only affects Windows. It is a no-op on other platforms.

## Semantics

- When disabled (default): `glob()`'s include and exclude patterns must match exactly the casing of files and directories on the filesystem. This is the same behavior on other platforms. E.g. `glob(["Foo/**"], exclude = ["Foo/Bar"])` will match exactly `Foo/**` and not `foO/**`, and will exclude exactly `Foo/Bar` but not `foO/baR`.

- When enabled: on Windows, `glob()` will ignore the casing in the include and exclude patterns. On other platforms, this is a no-op.

## Related issues

- https://github.com/bazelbuild/bazel/issues/8705
- https://github.com/bazelbuild/bazel/issues/8759

# Migration recipe

<!-- TODO: would be nice to provide a migration tool that evaluates the glob with both semantics and warns if there are differences. -->

# Rollout plan

Issue comments:
I'm having second thoughts about this idea.

In light of https://github.com/bazelbuild/bazel/issues/7627, namely that Windows will case-sensitivity on a per-directory basis, I'm starting to doubt the feasibility and usefulness of case-insensitive glob().

More, if glob remained case-sensitive, then Bazel would behave the same on Linux and Windows, and we wouldn't need to worry about the per-directory settings.

Pull request review comments:

Patch that resolved the issue:
diff --git a/src/main/java/com/google/devtools/build/lib/packages/GlobCache.java b/src/main/java/com/google/devtools/build/lib/packages/GlobCache.java
index 8d1bb74115d9dc..db58cfc813df11 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/GlobCache.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/GlobCache.java
@@ -255,7 +255,13 @@ public List<String> globUnsorted(
       }
       results.addAll(items);
     }
-    UnixGlob.removeExcludes(results, excludes);
+
+    // TODO(laszlocsomor): set `caseSensitive` from the value of
+    // `--incompatible_windows_case_insensitive_glob` or from FileSystem.isGlobCaseSensitive()
+    // See https://github.com/bazelbuild/bazel/issues/8767
+    final boolean caseSensitive = true;
+
+    UnixGlob.removeExcludes(results, excludes, caseSensitive);
     if (!allowEmpty && results.isEmpty()) {
       throw new BadGlobException(
           "all files in the glob have been excluded, but allow_empty is set to False.");
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/GlobFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/GlobFunction.java
index cabb54f6bd80bc..e40c76f11b43a7 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/GlobFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/GlobFunction.java
@@ -43,6 +43,10 @@
  */
 public final class GlobFunction implements SkyFunction {
 
+  // TODO(laszlocsomor): we might need to create another regexPatternCache for case-insensitive
+  // glob() mode to avoid reading wrong cache results when the user changes the
+  // --incompatible_windows_case_ignoring_glob flag value between builds.
+  // See https://github.com/bazelbuild/bazel/issues/8767.
   private final ConcurrentHashMap<String, Pattern> regexPatternCache = new ConcurrentHashMap<>();
 
   private final boolean alwaysUseDirListing;
@@ -152,6 +156,11 @@ public SkyValue compute(SkyKey skyKey, Environment env)
         }
       }
 
+      // TODO(laszlocsomor): set `caseSensitive` from the value of
+      // `--incompatible_windows_case_insensitive_glob` or from FileSystem.isGlobCaseSensitive()
+      // See https://github.com/bazelbuild/bazel/issues/8767
+      final boolean caseSensitive = true;
+
       // Now that we have the directory listing, we do three passes over it so as to maximize
       // skyframe batching:
       // (1) Process every dirent, keeping track of values we need to request if the dirent cannot
@@ -169,7 +178,7 @@ public SkyValue compute(SkyKey skyKey, Environment env)
       for (Dirent dirent : listingValue.getDirents()) {
         Dirent.Type direntType = dirent.getType();
         String fileName = dirent.getName();
-        if (!UnixGlob.matches(patternHead, fileName, regexPatternCache)) {
+        if (!UnixGlob.matches(patternHead, fileName, regexPatternCache, caseSensitive)) {
           continue;
         }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
index 23a6c77b9921ba..cfbe0062aa91e7 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
@@ -1011,7 +1011,13 @@ private List<String> resolve(Globber delegate)
         if (legacyIncludesToken != null) {
           matches.addAll(delegate.fetch(legacyIncludesToken));
         }
-        UnixGlob.removeExcludes(matches, excludes);
+
+        // TODO(laszlocsomor): set `caseSensitive` from the value of
+        // `--incompatible_windows_case_insensitive_glob` or from FileSystem.isGlobCaseSensitive()
+        // See https://github.com/bazelbuild/bazel/issues/8767
+        final boolean caseSensitive = true;
+
+        UnixGlob.removeExcludes(matches, excludes, caseSensitive);
         List<String> result = new ArrayList<>(matches);
         // Skyframe glob results are unsorted. And we used a LegacyGlobber that doesn't sort.
         // Therefore, we want to unconditionally sort here.
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/FileSystem.java b/src/main/java/com/google/devtools/build/lib/vfs/FileSystem.java
index abaa6b1b9d7f08..7f6b6e02898559 100644
--- a/src/main/java/com/google/devtools/build/lib/vfs/FileSystem.java
+++ b/src/main/java/com/google/devtools/build/lib/vfs/FileSystem.java
@@ -137,6 +137,22 @@ final Root getAbsoluteRoot() {
    */
   public abstract boolean isFilePathCaseSensitive();
 
+  /**
+   * Returns true if glob() is case-sensitive.
+   *
+   * <p>When glob() is case-sensitive, it will only match (or exclude) file "Foo" if the include (or
+   * exclude) pattern uses the same upper-case and lower-case letters.
+   *
+   * <p>When glob() is case-insensitive, it will match (or exclude) the file "Foo" even if the
+   * include (or exclude) pattern uses a different casing such as "foO".
+   */
+  // TODO(laszlocsomor): After `--incompatible_windows_case_insensitive_glob` is flipped to true,
+  // remove this method and all references to it and replace call sites with
+  // isFilePathCaseSensitive(). See https://github.com/bazelbuild/bazel/issues/8767
+  public boolean isGlobCaseSensitive() {
+    return true;
+  }
+
   /**
    * Returns the type of the file system path belongs to.
    *
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/UnixGlob.java b/src/main/java/com/google/devtools/build/lib/vfs/UnixGlob.java
index d9175a27eaace1..05a45c9fbb90be 100644
--- a/src/main/java/com/google/devtools/build/lib/vfs/UnixGlob.java
+++ b/src/main/java/com/google/devtools/build/lib/vfs/UnixGlob.java
@@ -15,6 +15,7 @@
 package com.google.devtools.build.lib.vfs;
 
 import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Ascii;
 import com.google.common.base.Joiner;
 import com.google.common.base.Preconditions;
 import com.google.common.base.Predicate;
@@ -155,9 +156,9 @@ public static String checkPatternForError(String pattern) {
     return null;
   }
 
-  /** Calls {@link #matches(String, String, Map) matches(pattern, str, null)} */
-  public static boolean matches(String pattern, String str) {
-    return matches(pattern, str, null);
+  /** Calls {@link #matches(String, String, Map) matches(pattern, str, null, boolean)} */
+  public static boolean matches(String pattern, String str, boolean caseSensitive) {
+    return matches(pattern, str, null, caseSensitive);
   }
 
   /**
@@ -169,7 +170,8 @@ public static boolean matches(String pattern, String str) {
    * @param patternCache a cache from patterns to compiled Pattern objects, or {@code null} to skip
    *     caching
    */
-  public static boolean matches(String pattern, String str, Map<String, Pattern> patternCache) {
+  public static boolean matches(String pattern, String str, Map<String, Pattern> patternCache,
+      boolean caseSensitive) {
     if (pattern.length() == 0 || str.length() == 0) {
       return false;
     }
@@ -191,20 +193,21 @@ public static boolean matches(String pattern, String str, Map<String, Pattern> p
 
     // Common case: *.xyz
     if (pattern.charAt(0) == '*' && pattern.lastIndexOf('*') == 0) {
-      return str.endsWith(pattern.substring(1));
+      return endsWithCase(str, pattern.substring(1), caseSensitive);
     }
     // Common case: xyz*
     int lastIndex = pattern.length() - 1;
     // The first clause of this if statement is unnecessary, but is an
     // optimization--charAt runs faster than indexOf.
     if (pattern.charAt(lastIndex) == '*' && pattern.indexOf('*') == lastIndex) {
-      return str.startsWith(pattern.substring(0, lastIndex));
+      return startsWithCase(str, pattern.substring(0, lastIndex), caseSensitive);
     }
 
     Pattern regex =
         patternCache == null
-            ? makePatternFromWildcard(pattern)
-            : patternCache.computeIfAbsent(pattern, p -> makePatternFromWildcard(p));
+            ? makePatternFromWildcard(pattern, caseSensitive)
+            : patternCache.computeIfAbsent(
+                pattern, p -> makePatternFromWildcard(p, caseSensitive));
     return regex.matcher(str).matches();
   }
 
@@ -214,7 +217,7 @@ public static boolean matches(String pattern, String str, Map<String, Pattern> p
    *
    * <p>e.g. "foo*bar?.java" -> "foo.*bar.\\.java"
    */
-  private static Pattern makePatternFromWildcard(String pattern) {
+  private static Pattern makePatternFromWildcard(String pattern, boolean caseSensitive) {
     StringBuilder regexp = new StringBuilder();
     for (int i = 0, len = pattern.length(); i < len; i++) {
       char c = pattern.charAt(i);
@@ -247,7 +250,14 @@ private static Pattern makePatternFromWildcard(String pattern) {
           regexp.append(c);
           break;
         default:
-          regexp.append(c);
+          if (caseSensitive || !isAlphaAscii(c)) {
+            regexp.append(c);
+          } else {
+            regexp.append('[')
+                  .append(Ascii.toUpperCase(c))
+                  .append(Ascii.toLowerCase(c))
+                  .append(']');
+          }
           break;
       }
     }
@@ -558,7 +568,6 @@ Future<List<Path>> globAsync(
       if (baseStat == null || patterns.isEmpty()) {
         return Futures.immediateFuture(Collections.<Path>emptyList());
       }
-
       List<String[]> splitPatterns = checkAndSplitPatterns(patterns);
 
       // We do a dumb loop, even though it will likely duplicate logical work (note that the
@@ -567,6 +576,7 @@ Future<List<Path>> globAsync(
       // glob [*/*.java, sub/*.java, */*.txt]).
       pendingOps.incrementAndGet();
       try {
+        final boolean caseSensitive = base.getFileSystem().isGlobCaseSensitive();
         for (String[] splitPattern : splitPatterns) {
           int numRecursivePatterns = 0;
           for (String pattern : splitPattern) {
@@ -575,8 +585,10 @@ Future<List<Path>> globAsync(
             }
           }
           GlobTaskContext context = numRecursivePatterns > 1
-              ? new RecursiveGlobTaskContext(splitPattern, excludeDirectories, dirPred, syscalls)
-              : new GlobTaskContext(splitPattern, excludeDirectories, dirPred, syscalls);
+              ? new RecursiveGlobTaskContext(splitPattern, excludeDirectories, caseSensitive,
+                                             dirPred, syscalls)
+              : new GlobTaskContext(splitPattern, excludeDirectories, caseSensitive, dirPred,
+                                    syscalls);
           context.queueGlob(base, baseStat.isDirectory(), 0);
         }
       } finally {
@@ -685,16 +697,19 @@ private void decrementAndCheckDone() {
     private class GlobTaskContext {
       private final String[] patternParts;
       private final boolean excludeDirectories;
+      private final boolean caseSensitive;
       private final Predicate<Path> dirPred;
       private final FilesystemCalls syscalls;
 
       GlobTaskContext(
           String[] patternParts,
           boolean excludeDirectories,
+          boolean caseSensitive,
           Predicate<Path> dirPred,
           FilesystemCalls syscalls) {
         this.patternParts = patternParts;
         this.excludeDirectories = excludeDirectories;
+        this.caseSensitive = caseSensitive;
         this.dirPred = dirPred;
         this.syscalls = syscalls;
       }
@@ -744,9 +759,10 @@ public int hashCode() {
       private RecursiveGlobTaskContext(
           String[] patternParts,
           boolean excludeDirectories,
+          boolean caseSensitive,
           Predicate<Path> dirPred,
           FilesystemCalls syscalls) {
-        super(patternParts, excludeDirectories, dirPred, syscalls);
+        super(patternParts, excludeDirectories, caseSensitive, dirPred, syscalls);
       }
 
       @Override
@@ -820,7 +836,7 @@ private void reallyGlob(Path base, boolean baseIsDir, int idx, GlobTaskContext c
           // The file is a special file (fifo, etc.). No need to even match against the pattern.
           continue;
         }
-        if (matches(pattern, dent.getName(), cache)) {
+        if (matches(pattern, dent.getName(), cache, context.caseSensitive)) {
           Path child = base.getChild(dent.getName());
 
           if (childType == Dirent.Type.SYMLINK) {
@@ -868,12 +884,17 @@ private void processFileOrDirectory(
    * Filters out exclude patterns from a Set of paths. Common cases such as wildcard-free patterns
    * or suffix patterns are special-cased to make this function efficient.
    */
-  public static void removeExcludes(Set<String> paths, Collection<String> excludes) {
+  public static void removeExcludes(Set<String> paths, Collection<String> excludes,
+      boolean caseSensitive) {
     ArrayList<String> complexPatterns = new ArrayList<>(excludes.size());
     Map<String, List<String>> starstarSlashStarHeadTailPairs = new HashMap<>();
     for (String exclude : excludes) {
       if (isWildcardFree(exclude)) {
-        paths.remove(exclude);
+        if (caseSensitive) {
+          paths.remove(exclude);
+        } else {
+          paths.removeIf(p -> Ascii.equalsIgnoreCase(p, exclude));
+        }
         continue;
       }
       int patternPos = exclude.indexOf("**/*");
@@ -890,9 +911,9 @@ public static void removeExcludes(Set<String> paths, Collection<String> excludes
     for (Map.Entry<String, List<String>> headTailPair : starstarSlashStarHeadTailPairs.entrySet()) {
       paths.removeIf(
           path -> {
-            if (path.startsWith(headTailPair.getKey())) {
+            if (startsWithCase(path, headTailPair.getKey(), caseSensitive)) {
               for (String tail : headTailPair.getValue()) {
-                if (path.endsWith(tail)) {
+                if (endsWithCase(path, tail, caseSensitive)) {
                   return true;
                 }
               }
@@ -909,7 +930,7 @@ public static void removeExcludes(Set<String> paths, Collection<String> excludes
         path -> {
           String[] segments = Iterables.toArray(Splitter.on('/').split(path), String.class);
           for (String[] splitPattern : splitPatterns) {
-            if (matchesPattern(splitPattern, segments, 0, 0, patternCache)) {
+            if (matchesPattern(splitPattern, segments, 0, 0, patternCache, caseSensitive)) {
               return true;
             }
           }
@@ -919,19 +940,21 @@ public static void removeExcludes(Set<String> paths, Collection<String> excludes
 
   /** Returns true if {@code pattern} matches {@code path} starting from the given segments. */
   private static boolean matchesPattern(
-      String[] pattern, String[] path, int i, int j, Map<String, Pattern> patternCache) {
+      String[] pattern, String[] path, int i, int j, Map<String, Pattern> patternCache,
+      boolean caseSensitive) {
     if (i == pattern.length) {
       return j == path.length;
     }
     if (pattern[i].equals("**")) {
-      return matchesPattern(pattern, path, i + 1, j, patternCache)
-          || (j < path.length && matchesPattern(pattern, path, i, j + 1, patternCache));
+      return matchesPattern(pattern, path, i + 1, j, patternCache, caseSensitive)
+          || (j < path.length &&
+              matchesPattern(pattern, path, i, j + 1, patternCache, caseSensitive));
     }
     if (j == path.length) {
       return false;
     }
-    if (matches(pattern[i], path[j], patternCache)) {
-      return matchesPattern(pattern, path, i + 1, j + 1, patternCache);
+    if (matches(pattern[i], path[j], patternCache, caseSensitive)) {
+      return matchesPattern(pattern, path, i + 1, j + 1, patternCache, caseSensitive);
     }
     return false;
   }
@@ -939,4 +962,28 @@ private static boolean matchesPattern(
   private static boolean isWildcardFree(String pattern) {
     return !pattern.contains("*") && !pattern.contains("?");
   }
+
+  @VisibleForTesting
+  static boolean startsWithCase(String s, String p, boolean caseSensitive) {
+    if (caseSensitive) {
+      return s.startsWith(p);
+    } else {
+      return s.length() >= p.length() && s.regionMatches(true, 0, p, 0, p.length());
+    }
+  }
+
+  @VisibleForTesting
+  static boolean endsWithCase(String s, String p, boolean caseSensitive) {
+    if (caseSensitive) {
+      return s.endsWith(p);
+    } else {
+      return s.length() >= p.length() &&
+             s.regionMatches(true, s.length() - p.length(), p, 0, p.length());
+    }
+  }
+
+  @VisibleForTesting
+  static boolean isAlphaAscii(char c) {
+    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/windows/WindowsFileSystem.java b/src/main/java/com/google/devtools/build/lib/windows/WindowsFileSystem.java
index 5b3669b8ed5a8c..abb7c63d5e196a 100644
--- a/src/main/java/com/google/devtools/build/lib/windows/WindowsFileSystem.java
+++ b/src/main/java/com/google/devtools/build/lib/windows/WindowsFileSystem.java
@@ -105,6 +105,13 @@ public boolean isFilePathCaseSensitive() {
     return false;
   }
 
+  @Override
+  public boolean isGlobCaseSensitive() {
+    // TODO(laszlocsomor): return the opposite of `--incompatible_windows_case_insensitive_glob`
+    // here. See https://github.com/bazelbuild/bazel/issues/8767
+    return true;
+  }
+
   @Override
   protected boolean fileIsSymbolicLink(File file) {
     try {


Test patch:
diff --git a/src/test/java/com/google/devtools/build/lib/BUILD b/src/test/java/com/google/devtools/build/lib/BUILD
index fbf4d421a713a4..8199ba1e9d8cf5 100644
--- a/src/test/java/com/google/devtools/build/lib/BUILD
+++ b/src/test/java/com/google/devtools/build/lib/BUILD
@@ -9,6 +9,7 @@ package(
 CROSS_PLATFORM_WINDOWS_TESTS = [
     "util/DependencySetWindowsTest.java",
     "vfs/PathFragmentWindowsTest.java",
+    "vfs/WindowsGlobTest.java",
     "vfs/WindowsPathTest.java",
 ]
 
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/GlobFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/GlobFunctionTest.java
index 3d85f630d0f619..e30cb903f557c6 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/GlobFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/GlobFunctionTest.java
@@ -544,7 +544,7 @@ public void testSpecialRegexCharacter() throws Exception {
 
   @Test
   public void testMatchesCallWithNoCache() {
-    assertThat(UnixGlob.matches("*a*b", "CaCb", null)).isTrue();
+    assertThat(UnixGlob.matches("*a*b", "CaCb", null, true)).isTrue();
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/vfs/GlobTest.java b/src/test/java/com/google/devtools/build/lib/vfs/GlobTest.java
index 7eb2a6672138fc..efa15f515a8db2 100644
--- a/src/test/java/com/google/devtools/build/lib/vfs/GlobTest.java
+++ b/src/test/java/com/google/devtools/build/lib/vfs/GlobTest.java
@@ -285,7 +285,7 @@ public void testSpecialRegexCharacter() throws Exception {
 
   @Test
   public void testMatchesCallWithNoCache() {
-    assertThat(UnixGlob.matches("*a*b", "CaCb", null)).isTrue();
+    assertThat(UnixGlob.matches("*a*b", "CaCb", null, true)).isTrue();
   }
 
   @Test
@@ -297,11 +297,11 @@ public void testMultiplePatterns() throws Exception {
   public void testMatcherMethodRecursiveBelowDir() throws Exception {
     FileSystemUtils.createEmptyFile(tmpPath.getRelative("foo/file"));
     String pattern = "foo/**/*";
-    assertThat(UnixGlob.matches(pattern, "foo/bar")).isTrue();
-    assertThat(UnixGlob.matches(pattern, "foo/bar/baz")).isTrue();
-    assertThat(UnixGlob.matches(pattern, "foo")).isFalse();
-    assertThat(UnixGlob.matches(pattern, "foob")).isFalse();
-    assertThat(UnixGlob.matches("**/foo", "foo")).isTrue();
+    assertThat(UnixGlob.matches(pattern, "foo/bar", true)).isTrue();
+    assertThat(UnixGlob.matches(pattern, "foo/bar/baz", true)).isTrue();
+    assertThat(UnixGlob.matches(pattern, "foo", true)).isFalse();
+    assertThat(UnixGlob.matches(pattern, "foob", true)).isFalse();
+    assertThat(UnixGlob.matches("**/foo", "foo", true)).isTrue();
   }
 
   @Test
@@ -440,7 +440,7 @@ public boolean apply(Path input) {
 
   private Collection<String> removeExcludes(ImmutableList<String> paths, String... excludes) {
     HashSet<String> pathSet = new HashSet<>(paths);
-    UnixGlob.removeExcludes(pathSet, ImmutableList.copyOf(excludes));
+    UnixGlob.removeExcludes(pathSet, ImmutableList.copyOf(excludes), true);
     return pathSet;
   }
 
diff --git a/src/test/java/com/google/devtools/build/lib/vfs/WindowsGlobTest.java b/src/test/java/com/google/devtools/build/lib/vfs/WindowsGlobTest.java
new file mode 100644
index 00000000000000..39bd33f877e608
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/vfs/WindowsGlobTest.java
@@ -0,0 +1,348 @@
+// Copyright 2019 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.truth.Truth.assertThat;
+import static com.google.common.truth.Truth.assertWithMessage;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.clock.BlazeClock;
+import com.google.devtools.build.lib.vfs.inmemoryfs.InMemoryFileSystem;
+import java.io.IOException;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.TreeMap;
+import java.util.concurrent.atomic.AtomicReference;
+import java.util.regex.Pattern;
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+/** Tests glob() on Windows (when glob is case-insensitive). */
+@RunWith(JUnit4.class)
+public class WindowsGlobTest {
+
+  private static void assertMatches(UnixGlob.FilesystemCalls fsCalls, Path root, String pattern,
+      String... expecteds) throws IOException {
+    AtomicReference<UnixGlob.FilesystemCalls> sysCalls = new AtomicReference<>(fsCalls);
+    assertThat(
+        Iterables.transform(
+            new UnixGlob.Builder(root)
+                .addPattern(pattern)
+                .setFilesystemCalls(sysCalls)
+                .setExcludeDirectories(true)
+                .glob(),
+            // Convert Paths to Strings, otherwise they'd be compared with the host system's Path
+            // comparison semantics.
+            a -> a.relativeTo(root).toString()))
+        .containsExactlyElementsIn(expecteds);
+  }
+
+  private static void assertExcludes(Collection<String> unfiltered, String exclusionPattern,
+                                     boolean caseSensitive, Collection<String> expected) {
+    Set<String> matched = new HashSet<>(unfiltered);
+    UnixGlob.removeExcludes(matched, ImmutableList.of(exclusionPattern), caseSensitive);
+    assertThat(matched).containsExactlyElementsIn(expected);
+  }
+
+  @Test
+  public void testMatches() throws Exception {
+    assertThat(UnixGlob.matches("Foo/**", "Foo/Bar/a.txt", null, true)).isTrue();
+    assertThat(UnixGlob.matches("Foo/**", "Foo/Bar/a.txt", null, false)).isTrue();
+
+    assertThat(UnixGlob.matches("foo/**", "Foo/Bar/a.txt", null, true)).isFalse();
+    assertThat(UnixGlob.matches("foo/**", "Foo/Bar/a.txt", null, false)).isTrue();
+
+    assertThat(UnixGlob.matches("F*o*o/**", "Foo/Bar/a.txt", null, true)).isTrue();
+    assertThat(UnixGlob.matches("F*o*o/**", "Foo/Bar/a.txt", null, false)).isTrue();
+
+    assertThat(UnixGlob.matches("f*o*o/**", "Foo/Bar/a.txt", null, true)).isFalse();
+    assertThat(UnixGlob.matches("f*o*o/**", "Foo/Bar/a.txt", null, false)).isTrue();
+
+    assertThat(UnixGlob.matches("Foo/**", "Foo/Bar/a.txt", null, true)).isTrue();
+    assertThat(UnixGlob.matches("Foo/**", "Foo/Bar/a.txt", null, false)).isTrue();
+  }
+
+  @Test
+  public void testExcludes() throws Exception {
+    assertExcludes(Arrays.asList("Foo/Bar/a.txt", "Foo/Bar/b.dat"), "Foo/**/*.dat", true,
+                   Arrays.asList("Foo/Bar/a.txt"));
+    assertExcludes(Arrays.asList("Foo/Bar/a.txt", "Foo/Bar/b.dat"), "Foo/**/*.dat", false,
+                   Arrays.asList("Foo/Bar/a.txt"));
+
+    assertExcludes(Arrays.asList("Foo/Bar/a.txt", "Foo/Bar/b.dat"), "foo/**/*.dat", true,
+                   Arrays.asList("Foo/Bar/a.txt", "Foo/Bar/b.dat"));
+    assertExcludes(Arrays.asList("Foo/Bar/a.txt", "Foo/Bar/b.dat"), "foo/**/*.dat", false,
+                   Arrays.asList("Foo/Bar/a.txt"));
+  }
+
+  private enum MockStat implements FileStatus {
+    FILE(true, false),
+    DIR(false, true),
+    UNKNOWN(false, false);
+
+    private final boolean isFile;
+    private final boolean isDir;
+
+    private MockStat(boolean isFile, boolean isDir) {
+      this.isFile = isFile;
+      this.isDir = isDir;
+    }
+
+    @Override public boolean isFile() { return isFile; }
+    @Override public boolean isDirectory() { return isDir; }
+    @Override public boolean isSymbolicLink() { return false; }
+    @Override public boolean isSpecialFile() { return false; }
+    @Override public long getSize() throws IOException { return 0; }
+
+    @Override
+    public long getLastModifiedTime() throws IOException {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public long getLastChangeTime() throws IOException {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public long getNodeId() throws IOException {
+      throw new UnsupportedOperationException();
+    }
+  }
+
+  private static FileSystem mockFs(boolean caseSensitive) throws IOException {
+    FileSystem fs = new InMemoryFileSystem(BlazeClock.instance()) {
+      @Override public boolean isFilePathCaseSensitive() { return caseSensitive; }
+      @Override public boolean isGlobCaseSensitive() { return isFilePathCaseSensitive(); }
+    };
+    fs.getPath("/globtmp/Foo/Bar").createDirectoryAndParents();
+    FileSystemUtils.writeContentAsLatin1(fs.getPath("/globtmp/Foo/Bar/a.txt"), "foo");
+    FileSystemUtils.writeContentAsLatin1(fs.getPath("/globtmp/Foo/Bar/b.dat"), "bar");
+    return fs;
+  }
+
+  private static Map<String, Collection<Dirent>> mockDirents(Path root) {
+    // Map keys must be Strings not Paths, lest they follow the host OS' case-sensitivity policy.
+    Map<String, Collection<Dirent>> d = root.getFileSystem().isGlobCaseSensitive()
+        ? new HashMap<>()
+        : new TreeMap<>((String x, String y) -> x.compareToIgnoreCase(y));
+    d.put(
+        root.getParentDirectory().toString(),
+        ImmutableList.of(new Dirent(root.getBaseName(), Dirent.Type.DIRECTORY)));
+    d.put(
+        root.toString(),
+        ImmutableList.of(new Dirent("Foo", Dirent.Type.DIRECTORY)));
+    d.put(
+        root.getRelative("Foo").toString(),
+        ImmutableList.of(new Dirent("Bar", Dirent.Type.DIRECTORY)));
+    d.put(
+        root.getRelative("Foo/Bar").toString(),
+        ImmutableList.of(
+            new Dirent("a.txt", Dirent.Type.FILE), new Dirent("b.dat", Dirent.Type.FILE)));
+    return d;
+  }
+
+  private static Map<String, FileStatus> mockStats(Path root) {
+    // Map keys must be Strings not Paths, lest they follow the host OS' case-sensitivity policy.
+    Map<String, FileStatus> d = root.getFileSystem().isGlobCaseSensitive()
+        ? new HashMap<>()
+        : new TreeMap<>((String x, String y) -> x.compareToIgnoreCase(y));
+    d.put(root.getParentDirectory().toString(), MockStat.DIR);
+    d.put(root.toString(), MockStat.DIR);
+    d.put(root.getRelative("Foo").toString(), MockStat.DIR);
+    d.put(root.getRelative("Foo/Bar").toString(), MockStat.DIR);
+    d.put(root.getRelative("Foo/Bar/a.txt").toString(), MockStat.FILE);
+    d.put(root.getRelative("Foo/Bar/b.dat").toString(), MockStat.FILE);
+    return d;
+  }
+
+  private static UnixGlob.FilesystemCalls mockFsCalls(Path root) {
+    return new UnixGlob.FilesystemCalls() {
+      // These maps use case-sensitive or case-insensitive key comparison depending on
+      // root.getFileSystem().isGlobCaseSensitive()
+      private final Map<String, Collection<Dirent>> dirents = mockDirents(root);
+      private final Map<String, FileStatus> stats = mockStats(root);
+
+      @Override
+      public Collection<Dirent> readdir(Path path) throws IOException {
+        String p = path.toString();
+        if (dirents.containsKey(p)) {
+          return dirents.get(p);
+        }
+        throw new IOException(p);
+      }
+
+      @Override
+      public FileStatus statIfFound(Path path, Symlinks symlinks) throws IOException {
+        String p = path.toString();
+        if (stats.containsKey(p)) {
+          return stats.get(p);
+        }
+        return MockStat.UNKNOWN;
+      }
+
+      @Override
+      public Dirent.Type getType(Path path, Symlinks symlinks) throws IOException {
+        String p = path.toString();
+        if (dirents.containsKey(p)) {
+          for (Dirent d : dirents.get(p)) {
+            if (d.getName().equals(path.getBaseName())) {
+              return d.getType();
+            }
+          }
+        }
+        throw new IOException(p);
+      }
+    };
+  }
+
+  @Test
+  public void testFoo() throws Exception {
+    FileSystem unixFs = mockFs(/* caseSensitive */ true);
+    FileSystem winFs = mockFs(/* caseSensitive */ false);
+
+    Path unixRoot = unixFs.getPath("/globtmp");
+    Path winRoot = winFs.getPath("/globtmp");
+
+    Path unixRoot2 = unixFs.getPath("/globTMP");
+    Path winRoot2 = winFs.getPath("/globTMP");
+
+    UnixGlob.FilesystemCalls unixFsCalls = mockFsCalls(unixRoot);
+    UnixGlob.FilesystemCalls winFsCalls = mockFsCalls(winRoot);
+
+    // Try a simple, non-recursive glob that matches no files. (Directories are exluded.)
+    assertMatches(unixFsCalls, unixRoot, "Foo/*");
+    assertMatches(winFsCalls, winRoot, "Foo/*");
+
+    // Try a simple, non-recursive glob that should match some files.
+    assertMatches(unixFsCalls, unixRoot, "Foo/*/*", "Foo/Bar/a.txt", "Foo/Bar/b.dat");
+    assertMatches(winFsCalls, winRoot, "Foo/*/*", "Foo/Bar/a.txt", "Foo/Bar/b.dat");
+
+    // Try a recursive glob.
+    assertMatches(unixFsCalls, unixRoot, "Foo/**", "Foo/Bar/a.txt", "Foo/Bar/b.dat");
+    assertMatches(winFsCalls, winRoot, "Foo/**", "Foo/Bar/a.txt", "Foo/Bar/b.dat");
+
+    // Try a recursive glob, but use incorrect casing in the pattern.
+    // The results retain the casing of the pattern ("foO") because the glob logic checks its
+    // existence with 'statIfFound', and uses the name from the pattern.
+    // The **-matched parts use the actual casing ("Bar") because the glob does a 'readdir' to get
+    // these.
+    assertMatches(unixFsCalls, unixRoot, "foO/**");
+    assertMatches(winFsCalls, winRoot, "foO/**", "foO/Bar/a.txt", "foO/Bar/b.dat");
+
+    // Try the same with another path component in the glob pattern. The casing of that pattern
+    // should be retained in the results.
+    assertMatches(unixFsCalls, unixRoot, "foO/baR/*");
+    assertMatches(winFsCalls, winRoot, "foO/baR/*", "foO/baR/a.txt", "foO/baR/b.dat");
+
+    // Even if the root's casing is incorrect, the case-insensitive glob should match it.
+    assertMatches(unixFsCalls, unixRoot2, "**");
+    assertMatches(winFsCalls, winRoot2, "**", "Foo/Bar/a.txt", "Foo/Bar/b.dat");
+
+    // Try again the "wrong" root with a "wrong" first component. The result should retain the
+    // casing.
+    assertMatches(unixFsCalls, unixRoot2, "foO/**");
+    assertMatches(winFsCalls, winRoot2, "foO/**", "foO/Bar/a.txt", "foO/Bar/b.dat");
+
+    // Try the same with more "wrong" path components in the pattern. The results should retain all
+    // the casing.
+    assertMatches(unixFsCalls, unixRoot2, "foO/baR/A.TXT");
+    assertMatches(winFsCalls, winRoot2, "foO/baR/A.TXT", "foO/baR/A.TXT");
+
+    // Try a so-called "complex" in the file name. The glob logic creates a regex for this, and
+    // matches that against the result of a 'readdir', so the result retains the filesystem casing. 
+    assertMatches(unixFsCalls, unixRoot, "foO/baR/**");
+    assertMatches(winFsCalls, winRoot, "foO/baR/**/*.TXT", "foO/baR/a.txt");
+
+    // Try the same for a directory component. Again, because the glob logic matches a regex against
+    // the results of a 'readdir', the result should use the filesystem casing, not the pattern
+    // casing.
+    assertMatches(unixFsCalls, unixRoot, "F*o*o/**", "Foo/Bar/a.txt", "Foo/Bar/b.dat");
+    assertMatches(winFsCalls, winRoot, "F*o*o/**", "Foo/Bar/a.txt", "Foo/Bar/b.dat");
+
+    // A "complex" first token with the wrong casing.
+    assertMatches(unixFsCalls, unixRoot, "f*o*O/**");
+    assertMatches(winFsCalls, winRoot, "f*o*O/**", "Foo/Bar/a.txt", "Foo/Bar/b.dat");
+
+    // A "complex" first pattern with the right casing, but wrongly-cased root.
+    assertMatches(unixFsCalls, unixRoot2, "F*o*o/**");
+    assertMatches(winFsCalls, winRoot2, "F*o*o/**", "Foo/Bar/a.txt", "Foo/Bar/b.dat");
+
+    // A "complex" first pattern with the wrong casing and wrongly-cased root.
+    assertMatches(unixFsCalls, unixRoot2, "f*o*O/**");
+    assertMatches(winFsCalls, winRoot2, "f*o*O/**", "Foo/Bar/a.txt", "Foo/Bar/b.dat");
+  }
+
+  @Test
+  public void testStartsWithCase() {
+    assertThat(UnixGlob.startsWithCase("", "", true)).isTrue();
+    assertThat(UnixGlob.startsWithCase("", "", false)).isTrue();
+
+    assertThat(UnixGlob.startsWithCase("Foo", "", true)).isTrue();
+    assertThat(UnixGlob.startsWithCase("Foo", "", false)).isTrue();
+
+    assertThat(UnixGlob.startsWithCase("", "Foo", true)).isFalse();
+    assertThat(UnixGlob.startsWithCase("", "Foo", false)).isFalse();
+
+    assertThat(UnixGlob.startsWithCase("Fo", "Foo", true)).isFalse();
+    assertThat(UnixGlob.startsWithCase("Fo", "Foo", false)).isFalse();
+
+    assertThat(UnixGlob.startsWithCase("Foo", "Foo", true)).isTrue();
+    assertThat(UnixGlob.startsWithCase("Foo", "Foo", false)).isTrue();
+
+    assertThat(UnixGlob.startsWithCase("Foox", "Foo", true)).isTrue();
+    assertThat(UnixGlob.startsWithCase("Foox", "Foo", false)).isTrue();
+
+    assertThat(UnixGlob.startsWithCase("xFoo", "Foo", true)).isFalse();
+    assertThat(UnixGlob.startsWithCase("xFoo", "Foo", false)).isFalse();
+
+    assertThat(UnixGlob.startsWithCase("Foox", "foO", true)).isFalse();
+    assertThat(UnixGlob.startsWithCase("Foox", "foO", false)).isTrue();
+  }
+
+  @Test
+  public void testEndsWithCase() {
+    assertThat(UnixGlob.endsWithCase("", "", true)).isTrue();
+    assertThat(UnixGlob.endsWithCase("", "", false)).isTrue();
+
+    assertThat(UnixGlob.endsWithCase("Foo", "", true)).isTrue();
+    assertThat(UnixGlob.endsWithCase("Foo", "", false)).isTrue();
+
+    assertThat(UnixGlob.endsWithCase("", "Foo", true)).isFalse();
+    assertThat(UnixGlob.endsWithCase("", "Foo", false)).isFalse();
+
+    assertThat(UnixGlob.endsWithCase("Fo", "Foo", true)).isFalse();
+    assertThat(UnixGlob.endsWithCase("Fo", "Foo", false)).isFalse();
+
+    assertThat(UnixGlob.endsWithCase("Foo", "Foo", true)).isTrue();
+    assertThat(UnixGlob.endsWithCase("Foo", "Foo", false)).isTrue();
+
+    assertThat(UnixGlob.endsWithCase("Foox", "Foo", true)).isFalse();
+    assertThat(UnixGlob.endsWithCase("Foox", "Foo", false)).isFalse();
+
+    assertThat(UnixGlob.endsWithCase("xFoo", "Foo", true)).isTrue();
+    assertThat(UnixGlob.endsWithCase("xFoo", "Foo", false)).isTrue();
+
+    assertThat(UnixGlob.endsWithCase("xFoo", "foO", true)).isFalse();
+    assertThat(UnixGlob.endsWithCase("xFoo", "foO", false)).isTrue();
+  }
+}