kjol/tools/tsgo/internal/vfs/vfsmatch/MATCHING_ALGORITHM.md

Glob Matching Algorithm Specification

This document is a formal algorithmic specification of the file-path glob matching logic. An implementation conforming to this specification must produce identical results for all inputs. All subroutine errors are propagated as errors of the calling routine unless stated otherwise.

---

1. Definitions

Path — A normalized, /-separated absolute file path (e.g., /project/src/index.ts).

Path component — A single segment between / delimiters (e.g., src, index.ts). The leading / produces the root component, which is the empty string "".

Spec — A user-provided glob string (e.g., src/**/*.ts), before compilation.

Base path — The absolute directory against which relative specs are resolved.

Usage mode — One of three modes that alter matching semantics:

• Files — Matches complete file paths.
• Directories — Matches directory prefixes for traversal pruning.
• Exclude — Matches paths to be excluded.

Component kind — One of:

• Literal — Contains no * or ? characters.
• Wildcard — Contains at least one * or ? character.
• DoubleAsterisk — The exact string **.

Character — A single Unicode scalar value (codepoint). See Section 9 for the precise character-boundary requirements that apply during segment matching.

Segment kind — One of:

• SegLiteral — An exact literal substring.
• SegStar — Matches zero or more characters excluding /.
• SegQuestion — Matches exactly one character excluding /.

Pattern — A compiled spec consisting of a component list, a usage mode, and a case-sensitivity flag.

---

2. Helper Predicates

IS_HIDDEN_PATH(component)

1. If the length of component is 0, return false.
2. If the first character of component is ".", return true.
3. Return false.

IS_PACKAGE_FOLDER(component)

1. If component equals "node_modules" (case-insensitive), return true.
2. If component equals "bower_components" (case-insensitive), return true.
3. If component equals "jspm_packages" (case-insensitive), return true.
4. Return false.

ENSURE_TRAILING_SLASH(s)

1. If the length of s is 0, return s.
2. If the last character of s is "/", return s.
3. Return s concatenated with "/".

STRINGS_EQUAL(a, b, caseSensitive)

1. If caseSensitive is true, return whether a and b are byte-for-byte identical.
2. Return whether a and b are equal under Unicode case folding.

IS_IMPLICIT_GLOB(component)

1. If component contains any of the characters ".", "*", or "?", return false.
2. Return true.

---

3. Spec Normalization

NORMALIZE_SPEC(spec, basePath)

1. Let components be the result of resolving spec against basePath into an ordered list of normalized path components. The first element is the absolute root prefix (e.g., "/home"). The resolution uses / as the path separator, resolves . and .. segments, and collapses consecutive separators.
2. If the last character of components[0] is "/", remove it.
3. Return components.

---

4. Segment Parsing

PARSE_SEGMENTS(string)

1. Let segments be an empty list.
2. Let start be 0.
3. For each index i from 0 to the length of string − 1:
   1. If string[i] is "*" or "?", then:
      1. If i > start, append a SegLiteral segment with value string[start..i] to segments.
      2. If string[i] is "*", append a SegStar segment to segments.
      3. Otherwise, append a SegQuestion segment to segments.
      4. Set start to i + 1.
4. If start < length of string, append a SegLiteral segment with value string[start..] to segments.
5. Return segments.

---

5. Pattern Compilation

COMPILE_PATTERN(spec, basePath, usage, caseSensitive)

1. Let components be the result of NORMALIZE_SPEC(spec, basePath).
2. If the last element of components is "**" and usage is not Exclude, return failure. (The pattern compiles to nothing.)
3. If IS_IMPLICIT_GLOB(last element of components) is true (note: this check is applied to the normalized component, not the raw spec string), then:
   1. Append "**" to components.
   2. Append "*" to components.
4. Let compiledComponents be an empty list.
5. For each part in components:
   1. If part is "**", append a DoubleAsterisk component to compiledComponents.
   2. Otherwise, if part contains no "*" or "?" characters, append a Literal component with value part to compiledComponents.
   3. Otherwise, append a Wildcard component with segments PARSE_SEGMENTS(part) to compiledComponents.
6. Return a pattern with component list compiledComponents, usage mode usage, and case-sensitivity flag caseSensitive.

---

6. Path Component Extraction

NEXT_PATH_COMPONENT(path, offset)

1. If offset ≥ length of path, return (none, offset, false).
2. If offset is 0 and path[0] is "/", return ("", 1, true).
3. While offset < length of path and path[offset] is "/", increment offset.
4. If offset ≥ length of path, return (none, offset, false).
5. Let start be offset.
6. While offset < length of path and path[offset] is not "/", increment offset.
7. Return (path[start..offset], offset, true).

---

7. Full-Path Matching

MATCH_PATH(pattern, path)

1. Return the result of MATCH_PATH_INNER(pattern, path, 0, 0, false).

MATCH_PATH_PREFIX(pattern, path)

1. Return the result of MATCH_PATH_INNER(pattern, path, 0, 0, true).

MATCH_PATH_INNER(pattern, path, pathOffset, compIdx, prefixOnly)

1. Let components be the component list of pattern.
2. Let usage be the usage mode of pattern.
3. Let caseSensitive be the case-sensitivity flag of pattern.
4. Loop:
   1. Let (part, nextOffset, ok) be the result of NEXT_PATH_COMPONENT(path, pathOffset).
   2. If ok is false, then:
      1. If prefixOnly is true, return true.
      2. Return the result of PATTERN_SATISFIED(components, compIdx).
   3. If compIdx ≥ length of components, then:
      1. If usage is Exclude and prefixOnly is false, return true.
      2. Return false.
   4. Let comp be components[compIdx].
   5. If the kind of comp is DoubleAsterisk, then:
      1. Let skipResult be the result of MATCH_PATH_INNER(pattern, path, pathOffset, compIdx + 1, prefixOnly).
      2. If skipResult is true, return true.
      3. If usage is not Exclude, then:
         1. If IS_HIDDEN_PATH(part) is true, return false.
         2. If IS_PACKAGE_FOLDER(part) is true, return false.
      4. Set pathOffset to nextOffset.
      5. Continue the loop.
   6. If the kind of comp is Literal, then:
      1. If STRINGS_EQUAL(comp.value, part, caseSensitive) is false, return false.
   7. If the kind of comp is Wildcard, then:
      1. If usage is not Exclude and IS_PACKAGE_FOLDER(part) is true, return false.
      2. If the result of MATCH_WILDCARD(pattern, comp.segments, part) is false, return false.
   8. Set pathOffset to nextOffset.
   9. Increment compIdx.

PATTERN_SATISFIED(components, compIdx)

1. For each index i from compIdx to length of components − 1:
   1. If the kind of components[i] is not DoubleAsterisk, return false.
2. Return true.

---

8. Wildcard Component Matching

MATCH_WILDCARD(pattern, segments, string)

1. Let usage be the usage mode of pattern.
2. Let caseSensitive be the case-sensitivity flag of pattern.
3. If usage is not Exclude, then:
   1. If the length of segments > 0, then:
      1. Let firstKind be the kind of segments[0].
      2. If (firstKind is SegStar or firstKind is SegQuestion) and IS_HIDDEN_PATH(string) is true, return false.
4. Let matched be the result of MATCH_SEGMENTS(segments, string, caseSensitive).
5. If matched is false, return false.
6. Let accepted be the result of SHOULD_ACCEPT_MIN_JS(pattern, segments, string).
7. Return accepted.

---

9. Segment Matching

In this section, all string positions refer to character (codepoint) boundaries. Implementations must advance by full codepoints, not by encoding units (e.g., not by individual bytes in UTF-8, nor by individual code units in UTF-16). "Increment sIdx" means advance sIdx past the next character (one codepoint). Likewise, "length of s" is the number of characters, and s[sIdx] is the character at position sIdx.

The original TypeScript implementation uses ECMAScript regexes without the u flag, which operate on UTF-16 code units; a conforming implementation may match on codepoints instead, as the difference is only observable for supplementary-plane characters (U+10000 and above) in filenames.

MATCH_SEGMENTS(segments, s, caseSensitive)

1. Let segIdx be 0.
2. Let sIdx be 0.
3. Let starSegIdx be −1.
4. Let starSIdx be 0.
5. While sIdx < length of s:
   1. If segIdx < length of segments, then:
      1. Let seg be segments[segIdx].
      2. If the kind of seg is SegLiteral, then:
         1. Let lit be the value of seg.
         2. If sIdx + length of lit ≤ length of s and STRINGS_EQUAL(lit, s[sIdx..sIdx+len(lit)], caseSensitive) is true, then:
            1. Set sIdx to sIdx + length of lit.
            2. Increment segIdx.
            3. Continue the loop.
      3. If the kind of seg is SegQuestion, then:
         1. If s[sIdx] is not "/", then:
            1. Increment sIdx.
            2. Increment segIdx.
            3. Continue the loop.
      4. If the kind of seg is SegStar, then:
         1. Set starSegIdx to segIdx.
         2. Set starSIdx to sIdx.
         3. Increment segIdx.
         4. Continue the loop.
   2. If starSegIdx ≥ 0 and starSIdx < length of s and s[starSIdx] is not "/", then:
      1. Increment starSIdx.
      2. Set sIdx to starSIdx.
      3. Set segIdx to starSegIdx + 1.
      4. Continue the loop.
   3. Return false.
6. While segIdx < length of segments and the kind of segments[segIdx] is SegStar:
   1. Increment segIdx.
7. Return segIdx ≥ length of segments.

---

10. .min.js Default Exclusion

SHOULD_ACCEPT_MIN_JS(pattern, segments, filename)

1. Let usage be the usage mode of pattern.
2. If usage is not Files, return true.
3. If the result of HAS_MIN_JS_SUFFIX(filename, pattern.caseSensitive) is false, return true.
4. If the result of PATTERN_MENTIONS_MIN_SUFFIX(segments, pattern.caseSensitive) is true, return true.
5. Return false.

HAS_MIN_JS_SUFFIX(filename, caseSensitive)

1. Let suffix be ".min.js".
2. If length of filename < length of suffix, return false.
3. Let tail be the last 7 characters of filename.
4. If caseSensitive is true, return whether tail equals ".min.js".
5. Return whether tail equals ".min.js" under Unicode case folding.

PATTERN_MENTIONS_MIN_SUFFIX(segments, caseSensitive)

1. For each seg in segments:
   1. If the kind of seg is not SegLiteral, continue.
   2. Let lit be the value of seg.
   3. If caseSensitive is false, let lit be the lowercase form of lit.
   4. If lit contains the substring ".min.js" or ".min.", return true.
2. Return false.

---

11. Composite Matchers

MATCH_FILE(path, includePatterns, excludePatterns, hadIncludes)

1. For each pattern in excludePatterns:
   1. If the result of MATCH_PATH(pattern, path) is true, return (0, false).
2. If length of includePatterns is 0, then:
   1. If hadIncludes is true, return (0, false).
   2. Return (0, true).
3. For each index i from 0 to length of includePatterns − 1:
   1. If the result of MATCH_PATH(includePatterns[i], path) is true, return (i, true).
4. Return (0, false).

MATCH_DIRECTORY(path, includePatterns, excludePatterns, hadIncludes)

1. For each pattern in excludePatterns:
   1. If the result of MATCH_PATH(pattern, path) is true, return false.
2. If length of includePatterns is 0, then:
   1. If hadIncludes is true, return false.
   2. Return true.
3. For each pattern in includePatterns:
   1. If the result of MATCH_PATH_PREFIX(pattern, path) is true, return true.
4. Return false.

MATCH_SPEC(patterns, path)

1. For each pattern in patterns:
   1. If the result of MATCH_PATH(pattern, path) is true, return true.
2. Return false.

MATCH_SPEC_INDEX(patterns, path)

1. For each index i from 0 to length of patterns − 1:
   1. If the result of MATCH_PATH(patterns[i], path) is true, return i.
2. Return −1.

---

12. Pattern Set Compilation

COMPILE_PATTERNS(specs, basePath, usage, caseSensitive)

1. Let patterns be an empty list.
2. For each spec in specs:
   1. Let result be the result of COMPILE_PATTERN(spec, basePath, usage, caseSensitive).
   2. If result is not failure, append result to patterns.
3. Return patterns.

COMPILE_FILE_MATCHER(includeSpecs, excludeSpecs, basePath, caseSensitive)

1. Let includePatterns be the result of COMPILE_PATTERNS(includeSpecs, basePath, Files, caseSensitive).
2. Let excludePatterns be the result of COMPILE_PATTERNS(excludeSpecs, basePath, Exclude, caseSensitive).
3. Let hadIncludes be whether length of includeSpecs > 0.
4. Return (includePatterns, excludePatterns, hadIncludes).

COMPILE_DIRECTORY_MATCHER(includeSpecs, excludeSpecs, basePath, caseSensitive)

1. Let includePatterns be the result of COMPILE_PATTERNS(includeSpecs, basePath, Directories, caseSensitive).
2. Let excludePatterns be the result of COMPILE_PATTERNS(excludeSpecs, basePath, Exclude, caseSensitive).
3. Let hadIncludes be whether length of includeSpecs > 0.
4. Return (includePatterns, excludePatterns, hadIncludes).

---

13. Base Path Computation

GET_BASE_PATHS(rootPath, includeSpecs, caseSensitive)

1. Let basePaths be a list containing rootPath.
2. If includeSpecs is empty, return basePaths.
3. Let includeBasePaths be an empty list.
4. For each spec in includeSpecs:
   1. Let absolute be the result of resolving spec to an absolute normalized path against rootPath.
   2. Let basePath be GET_INCLUDE_BASE_PATH(absolute).
   3. Append basePath to includeBasePaths.
5. Sort includeBasePaths using a string comparator that is case-insensitive if caseSensitive is false.
6. For each candidate in includeBasePaths:
   1. If no element of basePaths is a path-prefix of candidate (respecting caseSensitive), append candidate to basePaths.
7. Return basePaths.

GET_INCLUDE_BASE_PATH(absoluteSpec)

1. Let wildcardOffset be the index of the first "*" or "?" character in absoluteSpec.
2. If wildcardOffset < 0, then:
   1. If absoluteSpec has a file extension (contains "."), return the parent directory of absoluteSpec.
   2. Return absoluteSpec.
3. Return the substring of absoluteSpec up to and including the last "/" before wildcardOffset.

---

14. Directory Traversal

READ_DIRECTORY(host, currentDir, path, extensions, excludeSpecs, includeSpecs, caseSensitive, depth)

The host must provide the following operations:

• Realpath(path) — Resolves symlinks and returns the canonical absolute path.
• GetAccessibleEntries(path) — Returns the sorted lists of files and subdirectories in the directory at path.

1. Let path be the normalized form of path.
2. Let currentDir be the normalized form of currentDir.
3. Let absolutePath be the concatenation of currentDir, "/", and path (normalized).
4. Let (fileIncludes, fileExcludes, fileHadIncludes) be the result of COMPILE_FILE_MATCHER(includeSpecs, excludeSpecs, absolutePath, caseSensitive).
5. Let (dirIncludes, dirExcludes, dirHadIncludes) be the result of COMPILE_DIRECTORY_MATCHER(includeSpecs, excludeSpecs, absolutePath, caseSensitive).
6. Let resultBuckets be a list of empty lists, with length equal to max(length of fileIncludes, 1).
7. Let visited be an empty set of strings.
8. Let basePaths be the result of GET_BASE_PATHS(path, includeSpecs, caseSensitive).
9. For each basePath in basePaths:
   1. Let baseAbsolute be the concatenation of currentDir, "/", and basePath (normalized).
   2. Perform VISIT(host, basePath, baseAbsolute, depth, extensions, fileIncludes, fileExcludes, fileHadIncludes, dirIncludes, dirExcludes, dirHadIncludes, caseSensitive, visited, resultBuckets).
10. Return the concatenation of all lists in resultBuckets, in order.

VISIT(host, path, absolutePath, depth, extensions, fileIncludes, fileExcludes, fileHadIncludes, dirIncludes, dirExcludes, dirHadIncludes, caseSensitive, visited, resultBuckets)

1. Let realPath be the result of host.Realpath(absolutePath).
2. Let canonicalPath be the canonical form of realPath under the file system's case-sensitivity rules.
3. If visited contains canonicalPath, return.
4. Add canonicalPath to visited.
5. Let entries be the result of host.GetAccessibleEntries(absolutePath).
6. Let absPrefix be ENSURE_TRAILING_SLASH(absolutePath).
7. Let pathPrefix be ENSURE_TRAILING_SLASH(path).
8. For each file in entries.files:
   1. If extensions is non-empty and the file extension of file is not in extensions, continue.
   2. Let absFile be absPrefix concatenated with file.
   3. Let (index, matched) be the result of MATCH_FILE(absFile, fileIncludes, fileExcludes, fileHadIncludes).
   4. If matched is true, append pathPrefix concatenated with file to resultBuckets[index].
9. If depth is finite (i.e., not the sentinel value representing unlimited depth), then:
   1. Decrement depth.
   2. If depth is 0, return.
10. For each dir in entries.directories:
    1. Let absDir be absPrefix concatenated with dir.
    2. If the result of MATCH_DIRECTORY(absDir, dirIncludes, dirExcludes, dirHadIncludes) is false, continue.
    3. Perform VISIT(host, pathPrefix concatenated with dir, absDir, depth, extensions, fileIncludes, fileExcludes, fileHadIncludes, dirIncludes, dirExcludes, dirHadIncludes, caseSensitive, visited, resultBuckets).

---

15. Invariants

The following properties hold for all conforming implementations:

1. COMPILE_PATTERN returns failure for any include or directory spec whose last component is "**".
2. When the pattern is exhausted but path components remain, exclude patterns return true and all other patterns return false.
3. MATCH_SEGMENTS is guaranteed O(n·m) where n is the string length and m is the segment count.
4. The .min.js default exclusion applies only under Files usage mode and only to wildcard components.
5. Symlink cycles are detected through real-path canonicalization in VISIT and cause the directory to be skipped.
6. Excludes are always evaluated before includes in MATCH_FILE and MATCH_DIRECTORY.
7. For include patterns, wildcard components reject package folders; literal components do not.
8. For include patterns, ** does not descend into hidden paths or package folders.
9. For include patterns, a wildcard component whose first segment is SegStar or SegQuestion does not match hidden path components.