@pattern-algebra/core

A TypeScript library for path pattern algebra - parsing, compiling, matching, and performing set operations on glob patterns. Designed for policy systems, build tools, and any application that needs to reason about path patterns mathematically.

Features

• Pattern Parsing: Parse glob patterns with support for *, **, ?, [...], {a,b}, and negation
• Pattern Matching: Efficiently match file paths against compiled patterns
• Pattern Algebra: Perform set operations (intersection, union, complement, difference) on patterns
• Containment Checking: Determine if one pattern contains, overlaps with, or is disjoint from another
• Path Utilities: Normalize paths, extract segments, and perform common path operations
• Type-Safe: Written in TypeScript with comprehensive type definitions

Installation

# pnpm
pnpm add @pattern-algebra/core

# npm
npm install @pattern-algebra/core

# yarn
yarn add @pattern-algebra/core

Quick Start

import {
  parsePattern,
  compilePattern,
  matchPath,
  patternIntersect,
  patternUnion,
  checkContainment,
} from '@pattern-algebra/core'

// Parse and compile a pattern
const pattern = compilePattern(parsePattern('src/**/*.ts'))

// Match paths against the pattern
matchPath('/src/index.ts', pattern) // true
matchPath('/src/utils/helper.ts', pattern) // true
matchPath('/lib/index.ts', pattern) // false

// Combine patterns with set operations
const srcFiles = compilePattern(parsePattern('src/**'))
const tsFiles = compilePattern(parsePattern('**/*.ts'))

// Intersection: files matching BOTH patterns
const srcTsFiles = patternIntersect(srcFiles, tsFiles)
matchPath('/src/index.ts', srcTsFiles) // true
matchPath('/lib/index.ts', srcTsFiles) // false

// Union: files matching EITHER pattern
const combined = patternUnion(compilePattern(parsePattern('**/*.js')), compilePattern(parsePattern('**/*.ts')))
matchPath('/src/index.js', combined) // true
matchPath('/src/index.ts', combined) // true

// Check containment relationships
const result = checkContainment(compilePattern(parsePattern('src/index.ts')), compilePattern(parsePattern('src/*.ts')))
result.isSubset // true
result.relationship // 'subset'

Pattern Syntax

Basic Wildcards

• * - Matches any characters within a single path segment (does not cross /)

  '*.ts' // matches: index.ts, helper.ts
  // does NOT match: src/index.ts
  
  'test-*-spec.js' // matches: test-unit-spec.js, test-integration-spec.js

• ? - Matches exactly one character

  'file?.ts' // matches: file1.ts, fileA.ts
  // does NOT match: file10.ts

• ** - Globstar: matches zero or more path segments

  'src/**/*.ts' // matches: src/index.ts, src/lib/util/helper.ts
  
  '**/*.test.ts' // matches: foo.test.ts, src/bar.test.ts, a/b/c/baz.test.ts

Character Classes

• [abc] - Matches any character in the set

  '[aeiou]*.txt' // matches: apple.txt, index.txt

• [a-z] - Matches any character in the range

  'file[0-9].ts' // matches: file1.ts, file9.ts

• [!abc] - Matches any character NOT in the set

  '[!.]*.ts' // matches files not starting with a dot

Brace Expansion

• {a,b,c} - Matches any of the comma-separated alternatives

  '*.{js,ts}' // matches: index.js, helper.ts
  
  'src/{lib,test}/**' // matches: src/lib/*, src/test/*

Negation

• !pattern - Negates a pattern (typically used in arrays of patterns)

  const pattern = parsePattern('!node_modules/**')

API Reference

Parsing

parsePattern(source: string): PathPattern

Parses a pattern string into an Abstract Syntax Tree (AST).

import { parsePattern } from '@pattern-algebra/core'

const ast = parsePattern('src/**/*.ts')
// Returns AST representation of the pattern

validatePattern(source: string): PatternError[]

Validates a pattern and returns any errors found.

import { validatePattern } from '@pattern-algebra/core'

const errors = validatePattern('src/[invalid')
if (errors.length > 0) {
  console.error('Invalid pattern:', errors)
}

isValidPattern(source: string): boolean

Checks if a pattern is valid.

import { isValidPattern } from '@pattern-algebra/core'

if (isValidPattern('src/**/*.ts')) {
  // Pattern is valid
}

expandBraces(source: string): string[]

Expands brace patterns into multiple patterns.

import { expandBraces } from '@pattern-algebra/core'

expandBraces('*.{js,ts}')
// Returns: ['*.js', '*.ts']

expandBraces('src/{lib,test}/**')
// Returns: ['src/lib/**', 'src/test/**']

Compilation

compilePattern(ast: PathPattern): CompiledPattern

Compiles a parsed pattern into an efficient matching automaton.

import { parsePattern, compilePattern } from '@pattern-algebra/core'

const pattern = compilePattern(parsePattern('src/**/*.ts'))
// Pattern is now ready for matching

Matching

matchPath(path: string, pattern: CompiledPattern): boolean

Matches a file path against a compiled pattern.

import { parsePattern, compilePattern, matchPath } from '@pattern-algebra/core'

const pattern = compilePattern(parsePattern('src/**/*.ts'))

matchPath('/src/index.ts', pattern) // true
matchPath('/lib/index.ts', pattern) // false

Note: Paths should be normalized (use forward slashes, no leading ./). Use normalizePath() if needed.

Path Utilities

PathContext

The PathContext interface provides context for path resolution operations. It is used with normalizePath() to handle home directory expansion, relative path resolution, and project-relative paths.

import type { PathContext } from '@pattern-algebra/core'

const context: PathContext = {
  homeDir: '/home/user', // User's home directory (for ~ expansion)
  cwd: '/home/user/project', // Current working directory
  projectRoot: '/home/user/project', // Optional: project root for project-relative patterns
}

Properties:

• homeDir (required): The user's home directory, used to expand ~ in paths
• cwd (required): The current working directory, used to resolve relative paths
• projectRoot (optional): The project root directory for project-relative pattern resolution

normalizePath(path: string, context: PathContext): string

Normalizes a file path by resolving ~, ., and .. segments, converting backslashes to forward slashes, and handling relative paths.

import { normalizePath } from '@pattern-algebra/core'

const context = {
  homeDir: '/home/user',
  cwd: '/home/user/project',
}

normalizePath('./src/../lib/index.ts', context) // '/home/user/project/lib/index.ts'
normalizePath('src\\utils\\helper.ts', context) // '/home/user/project/src/utils/helper.ts'
normalizePath('~/Documents/file.txt', context) // '/home/user/Documents/file.txt'

pathToSegments(path: string): string[]

Splits a path into segments.

import { pathToSegments } from '@pattern-algebra/core'

pathToSegments('/src/lib/index.ts') // ['src', 'lib', 'index.ts']

segmentsToPath(segments: string[]): string

Joins segments into a path.

import { segmentsToPath } from '@pattern-algebra/core'

segmentsToPath(['src', 'lib', 'index.ts']) // 'src/lib/index.ts'

Pattern Algebra (Set Operations)

patternIntersect(a: CompiledPattern, b: CompiledPattern): CompiledPattern

Creates a pattern matching paths that match BOTH input patterns.

import { parsePattern, compilePattern, patternIntersect, matchPath } from '@pattern-algebra/core'

const srcFiles = compilePattern(parsePattern('src/**'))
const tsFiles = compilePattern(parsePattern('**/*.ts'))
const srcTsFiles = patternIntersect(srcFiles, tsFiles)

matchPath('/src/index.ts', srcTsFiles) // true (matches both)
matchPath('/lib/index.ts', srcTsFiles) // false (only matches tsFiles)
matchPath('/src/index.js', srcTsFiles) // false (only matches srcFiles)

patternUnion(a: CompiledPattern, b: CompiledPattern): CompiledPattern

Creates a pattern matching paths that match EITHER input pattern.

import { parsePattern, compilePattern, patternUnion, matchPath } from '@pattern-algebra/core'

const jsFiles = compilePattern(parsePattern('**/*.js'))
const tsFiles = compilePattern(parsePattern('**/*.ts'))
const scriptFiles = patternUnion(jsFiles, tsFiles)

matchPath('/src/index.js', scriptFiles) // true
matchPath('/src/index.ts', scriptFiles) // true
matchPath('/src/style.css', scriptFiles) // false

patternComplement(pattern: CompiledPattern): CompiledPattern

Creates a pattern matching paths that do NOT match the input pattern.

import { parsePattern, compilePattern, patternComplement, matchPath } from '@pattern-algebra/core'

const testFiles = compilePattern(parsePattern('**/*.test.ts'))
const nonTestFiles = patternComplement(testFiles)

matchPath('/src/index.ts', nonTestFiles) // true
matchPath('/src/index.test.ts', nonTestFiles) // false

Note: Complement patterns may have infinite representations. Use with care.

patternDifference(a: CompiledPattern, b: CompiledPattern): CompiledPattern

Creates a pattern matching paths that match pattern A but NOT pattern B.

import { parsePattern, compilePattern, patternDifference, matchPath } from '@pattern-algebra/core'

const allTs = compilePattern(parsePattern('**/*.ts'))
const testTs = compilePattern(parsePattern('**/*.test.ts'))
const nonTestTs = patternDifference(allTs, testTs)

matchPath('/src/index.ts', nonTestTs) // true
matchPath('/src/index.test.ts', nonTestTs) // false

Containment Checking

checkContainment(a: CompiledPattern, b: CompiledPattern): ContainmentResult

Determines the relationship between two patterns.

import { parsePattern, compilePattern, checkContainment } from '@pattern-algebra/core'

const specific = compilePattern(parsePattern('src/index.ts'))
const general = compilePattern(parsePattern('src/*.ts'))

const result = checkContainment(specific, general)

result.isSubset // true (every path matching specific also matches general)
result.isSuperset // false
result.isEqual // false
result.relationship // 'subset'

Possible relationships:

• 'equal' - Patterns match exactly the same set of paths
• 'subset' - Pattern A matches a subset of pattern B's paths
• 'superset' - Pattern A matches a superset of pattern B's paths
• 'overlap' - Patterns have some common paths but neither contains the other
• 'disjoint' - Patterns have no common paths

areEquivalent(a: CompiledPattern, b: CompiledPattern): boolean

Checks if two patterns match exactly the same set of paths.

import { parsePattern, compilePattern, areEquivalent } from '@pattern-algebra/core'

const p1 = compilePattern(parsePattern('src/**/*.ts'))
const p2 = compilePattern(parsePattern('src/**/*.ts'))

areEquivalent(p1, p2) // true

hasOverlap(a: CompiledPattern, b: CompiledPattern): boolean

Checks if two patterns have any common paths.

import { parsePattern, compilePattern, hasOverlap } from '@pattern-algebra/core'

const ts = compilePattern(parsePattern('**/*.ts'))
const js = compilePattern(parsePattern('**/*.js'))

hasOverlap(ts, js) // false (disjoint file extensions)

areDisjoint(a: CompiledPattern, b: CompiledPattern): boolean

Checks if two patterns have no common paths.

import { parsePattern, compilePattern, areDisjoint } from '@pattern-algebra/core'

const src = compilePattern(parsePattern('src/**'))
const lib = compilePattern(parsePattern('lib/**'))

areDisjoint(src, lib) // true (different directories)

analyzePatterns(patterns: CompiledPattern[]): PatternAnalysis

Analyzes multiple patterns to find overlaps, redundancies, and gaps.

import { parsePattern, compilePattern, analyzePatterns } from '@pattern-algebra/core'

const patterns = [
  compilePattern(parsePattern('src/**/*.ts')),
  compilePattern(parsePattern('src/**/*.js')),
  compilePattern(parsePattern('lib/**')),
]

const analysis = analyzePatterns(patterns)
// Returns detailed analysis of pattern relationships

Advanced Usage

Working with Automata

For advanced use cases, you can work directly with the underlying automaton operations:

import {
  parsePattern,
  compilePattern,
  buildAutomaton,
  determinize,
  intersect,
  union,
  complement,
  isEmpty,
  findWitness,
} from '@pattern-algebra/core'

const pattern = compilePattern(parsePattern('src/**/*.ts'))

// Build NFA (Non-deterministic Finite Automaton)
const nfa = buildAutomaton(pattern.ast)

// Convert to DFA for faster matching
const dfa = determinize(nfa)

// Check if a pattern matches nothing
const empty = compilePattern(parsePattern('*.{js,ts}'))
const intersection = intersect(empty.automaton, compilePattern(parsePattern('*.css')).automaton)
isEmpty(intersection) // true (no files can be both .js/.ts AND .css)

// Find a witness path (example matching path)
const witness = findWitness(pattern.automaton)
// Returns a path that matches the pattern, or null if none exists

Quick Reject Filters

Compiled patterns include quick-reject filters for fast path elimination:

import { compilePattern, parsePattern, applyQuickReject } from '@pattern-algebra/core'

const pattern = compilePattern(parsePattern('src/**/*.ts'))

// Quick check before full automaton matching
const path = '/lib/index.js'
if (applyQuickReject(path, pattern.quickReject)) {
  // Path rejected - definitely doesn't match
} else {
  // Path might match - use full matching
}

Quick reject checks:

• Minimum/maximum segment count
• Required file extensions
• Required prefixes/suffixes
• Required path segments

Use Cases

Policy Systems

// Define access control policies as patterns
const readPolicy = compilePattern(parsePattern('public/**'))
const writePolicy = compilePattern(parsePattern('public/{uploads,temp}/**'))

// Check if a path is allowed
function canRead(path: string): boolean {
  return matchPath(path, readPolicy)
}

function canWrite(path: string): boolean {
  return matchPath(path, writePolicy)
}

// Find overlapping permissions
const overlap = patternIntersect(readPolicy, writePolicy)

Build Systems

// Define source patterns
const sourceFiles = patternUnion(
  compilePattern(parsePattern('src/**/*.ts')),
  compilePattern(parsePattern('lib/**/*.ts')),
)

const testFiles = compilePattern(parsePattern('**/*.test.ts'))

// Production files = source files - test files
const prodFiles = patternDifference(sourceFiles, testFiles)

// Check which files to include in build
function shouldBuild(path: string): boolean {
  return matchPath(path, prodFiles)
}

Linter Configuration Analysis

// Check if .eslintignore patterns overlap with lint targets
const lintTargets = compilePattern(parsePattern('src/**/*.{js,ts}'))
const ignored = compilePattern(parsePattern('src/generated/**'))

const result = checkContainment(ignored, lintTargets)

if (result.relationship === 'subset') {
  console.log('Some lint targets are ignored')
} else if (result.relationship === 'disjoint') {
  console.log('No overlap between targets and ignored files')
}

How It Works

@pattern-algebra/core uses segment-level automata to efficiently represent and operate on path patterns:

1. Parsing: Patterns are parsed into an Abstract Syntax Tree (AST)
2. Compilation: The AST is compiled into a Non-deterministic Finite Automaton (NFA) that operates on path segments (not characters)
3. Matching: Paths are split into segments and matched against the NFA
4. Set Operations: Automata are combined using standard automaton operations (intersection, union, complement)
5. Containment: Patterns are determinized into DFAs and compared to determine subset/superset relationships

Performance Optimizations

• Lazy Determinization: DFAs are only constructed when needed for containment checking
• Quick Reject Filters: Fast pre-filtering eliminates non-matching paths without full automaton traversal
• Segment-Level Operations: Operating on path segments (not characters) reduces state space
• Epsilon Transition Elimination: NFA-to-DFA conversion eliminates epsilon transitions for faster matching

License

MIT

Contributing

Contributions are welcome! Please see the repository for guidelines.

Related Projects

• @pattern-algebra/cli - Command-line interface for pattern operations
• @pattern-algebra/policy - Policy evaluation engine built on @pattern-algebra/core