@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

``bash


pnpm

pnpm add @pattern-algebra/core

npm

npm install @pattern-algebra/core

yarn

yarn add @pattern-algebra/core
`

Quick Start

`typescript
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

$3

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

`typescript
'*.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

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

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

`typescript
'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
`

$3

- [abc] - Matches any character in the set

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

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

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

- [!abc] - Matches any character NOT in the set
`typescript
'[!.]*.ts' // matches files not starting with a dot
`

$3

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

`typescript
'*.{js,ts}' // matches: index.js, helper.ts

'src/{lib,test}/*' // matches: src/lib/, src/test/*
`

$3

- !pattern - Negates a pattern (typically used in arrays of patterns)
`typescript
const pattern = parsePattern('!node_modules/**')
`

API Reference

$3

#### parsePattern(source: string): PathPattern

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

`typescript
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.

`typescript
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.

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

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

#### expandBraces(source: string): string[]

Expands brace patterns into multiple patterns.

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

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

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

$3

#### compilePattern(ast: PathPattern): CompiledPattern

Compiles a parsed pattern into an efficient matching automaton.

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

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

$3

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

Matches a file path against a compiled pattern.

`typescript
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.

$3

#### 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.

`typescript
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.

`typescript
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.

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

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

#### segmentsToPath(segments: string[]): string

Joins segments into a path.

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

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

$3

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

Creates a pattern matching paths that match BOTH input patterns.

`typescript
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.

`typescript
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.

`typescript
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.

`typescript
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
`

$3

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

Determines the relationship between two patterns.

`typescript
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.

`typescript
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.

`typescript
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.

`typescript
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.

`typescript
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

$3

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

`typescript
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
`

$3

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

`typescript
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

$3

`typescript
// 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)
`

$3

`typescript
// 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)
}
`

$3

`typescript
// 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

$3

- 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