Smirk (;-P / ;-) — Pure Native Resumable PCRE Engine in Haskell

Smirk is a 100% native Haskell Perl-Compatible Regular Expression (PCRE) engine. It provides high-assurance, pure functional regular expression matching, step-bounded ReDoS immunity, pausable/resumable continuations, sequence polymorphism, and first-class algebraic effect handlers without C dependencies, buffer allocations, or FFI overhead.

The Name & Emoticon Grounding

The library's name and symbol—Smirk (;-P / ;-))—express cheeky, playful defiance:

• In the security and system reliability world, regular expression engines are notorious for disastrous catastrophic backtracking—the dreaded ReDoS (Regular Expression Denial of Service) attack, where a pathological string like aaaaaaaaaaaaaaaaaaaaaaaaaaaaa! against (a+)+$ locks a CPU core in exponential \(\mathcal{O}(2^N)\) backtracking for hours or days.
• In mainstream Haskell, developers were traditionally forced to link against foreign C libraries (libpcre / libpcre2) via FFI bindings, compromising memory safety, complicating static linking and cross-compilation, and inviting segmentation faults on unbounded recursion.
• Smirk smirks at both traps: by executing bytecode over an explicit, heap-allocated Pike-style backtracking state machine under a strict Fuel / Step Budget, Smirk guarantees that execution never locks a runtime thread, never overflows the C call stack, and can pause, yield an intact continuation, and resume on demand.

Core Motivation & Architecture

The Problem with C FFI and Unbounded Backtracking

1. Foreign Function Interface (FFI) Vulnerabilities: Traditional Haskell bindings to C PCRE libraries introduce native build dependencies, cross-compilation obstacles, and potential memory leaks across C string marshalling boundaries.
2. Catastrophic Backtracking (ReDoS): When processing untrusted user input (e.g. web forms, query filters, search strings), standard regex engines can enter exponential search loops that freeze application threads.
3. Container Inflexibility: Most regex libraries force data into strict ByteString or Text, forcing expensive allocations when scanning [Char], finger-tree Seq Char, or Vector Char.
4. Effect Monolithic Coupling: Extensible effect users often find regex libraries tightly coupled to a single effect framework, pulling in heavy dependencies.

The Smirk Solution

smirk resolves these challenges through five architectural pillars:

1. 100% Pure Haskell Pike Virtual Machine: Patterns are compiled into linear bytecode vectors (Opcode), evaluated by a step-stepped virtual machine with an explicit heap-allocated backtracking stack.
2. Fuel-Bounded Execution & ReDoS Defense: Every instruction execution consumes 1 unit of Fuel (StepBudget !Int). If the budget is exhausted, the engine yields OutOfFuel along with a MatchContinuation.
3. Pausable & Resumable Continuations: Match evaluations can be paused, inspected, serialized, and resumed via resumeMatch with an replenished fuel budget.
4. Sequence Polymorphism: Through the RegexTarget abstraction, matching operates zero-copy across Text, ByteString, [Char], Seq Char, and Vector Char.
5. Decoupled 3-Package Architecture: The core engine is completely independent of effect libraries; dedicated packages provide zero-overhead bindings for effectful and polysemy.

Multi-Package Catalog

The repository is structured into four independent, modular Cabal packages:

Key Subsystems & Worked Examples

1. Basic PCRE Matching & Capture Groups

{-# LANGUAGE OverloadedStrings #-}

import Smirk

main :: IO ()
main = do
  case compileRegex "(?<protocol>https?)://(?<domain>[a-z.]+)" of
    Left err  -> putStrLn ("Compile error: " ++ show err)
    Right reg -> do
      case execMatch reg ("Visit https://haskell.org today!" :: Text) of
        Nothing  -> putStrLn "No match found"
        Just res -> do
          print (matchedSlice res)                -- "https://haskell.org"
          print (matchOffset res, matchLength res) -- (6, 19)
          print (namedGroups res)                 -- fromList [("domain","haskell.org"),("protocol","https")]

2. Compile-Time QuasiQuoters ([re|...|] & [ed|...|])

QuasiQuoters validate regex syntax and stream editor templates at compile time:

{-# LANGUAGE QuasiQuotes #-}

import Smirk

-- 1. Compile-time verified pattern:
let pattern = [re|\b[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\.[A-Z|a-z]{2,}\b|]

-- 2. Stream editor find-and-replace:
let editor = [ed|foo([0-9]+)///bar${1}|]
let replaced = applyEditor editor "foo42 and foo99"
-- replaced == "bar42 and bar99"

3. Step-Bounded Execution & ReDoS Defense

Defend against pathological catastrophic backtracking patterns by enforcing a step budget:

import Smirk

let pathological = compileRegex "(a+)+$"
let target = "aaaaaaaaaaaaaaaaaaaaaaaaaaaa!" :: Text

case pathological of
  Right reg ->
    -- Restrict execution to at most 10,000 VM instruction steps:
    case execMatchWithFuel reg target (StepBudget 10000) of
      Matched _        -> putStrLn "Matched"
      NoMatch          -> putStrLn "Did not match"
      OutOfFuel cont   -> do
        putStrLn "ReDoS detected! Step budget exceeded without locking CPU."
        -- Optionally resume later with additional fuel:
        case resumeMatch cont (StepBudget 5000) of
          OutOfFuel _ -> putStrLn "Still out of fuel; safely aborting."
          _           -> putStrLn "Finished."

4. Sequence Polymorphism across Haskell Containers

Match uniformly across different sequence representations without converting to Text:

import qualified Data.ByteString.Char8 as BS
import qualified Data.Sequence as Seq
import qualified Data.Vector as V
import Smirk

let reg = [re|[0-9]+|]

-- Strict ByteString:
testMatch reg (BS.pack "port 8080")       -- True

-- Standard String ([Char]):
testMatch reg "port 8080"                  -- True

-- Data.Sequence.Seq Char:
testMatch reg (Seq.fromList "port 8080")   -- True

-- Data.Vector.Vector Char:
testMatch reg (V.fromList "port 8080")     -- True

5. Effectful Integration (smirk-effectful)

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE QuasiQuotes #-}
{-# LANGUAGE TypeApplications #-}

import Effectful
import Smirk (re)
import Smirk.Effect.Effectful

lookupPort :: (RegexEngine :> es) => Text -> Eff es (Maybe Text)
lookupPort input = do
  mMatch <- matchRegex [re|port:([0-9]+)|] input
  pure (fmap matchedSlice mMatch)

6. Polysemy Integration (smirk-polysemy)

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE QuasiQuotes #-}
{-# LANGUAGE TypeApplications #-}

import Polysemy
import Smirk (re)
import Smirk.Effect.Polysemy

lookupPort :: (Member RegexEngine r) => Text -> Sem r (Maybe Text)
lookupPort input = do
  mMatch <- matchRegex [re|port:([0-9]+)|] input
  pure (fmap matchedSlice mMatch)

7. Native Filesystem Globbing ([glob|...|])

{-# LANGUAGE QuasiQuotes #-}

import Smirk

let g = [glob|src/**/*.{hs,lhs}|]
matchGlob g "src/Smirk/Core/AST.hs"   -- True
matchGlob g "test/Spec.hs"            -- False

Documentation Corpus & Reading Order

The technical documentation corpus is structured for progressive disclosure:

1. docs/INDEX.md — Comprehensive corpus inventory, audience reading paths, and package catalog.
2. docs/TUTORIAL.md — Detailed hands-on tutorial with worked examples across all 7 subsystems.
3. docs/NEWBIE_GUIDE.md — Fast symbol navigation table and 15-minute quickstart.
4. docs/MAINTAINER_GUIDE.md — Architectural invariants (I1–I8), verification gates, and triage runbooks.
5. docs/notes/SMIRK_DESIGN.md — Canonical design monograph detailing decisions D1–D10.
6. docs/notes/DOC_STRATEGY.md — Documentation strategy, precedence rule, and lifecycle.
7. docs/notes/COMMIT_ATTRIBUTION.md — Linux kernel RFC 2822 trailer format standards.
8. AGENTS.md — Advisory operational rules and navigation funnels for AI coding assistants.

Physical Verification Discipline

Before any commit or release, all 5 physical verification gates must pass cleanly:

./bin/smirk-verify

1. Gate 1: HLint Static Analysis: Zero hints allowed across all source packages (.hlint.yaml).
2. Gate 2: Full Cabal Test Suite: All test suites pass across all packages (cabal test all).
3. Gate 3: Tagref Cross-Reference Gate: Zero dangling references and zero duplicate tags (bin/smirk-tagref).
4. Gate 4: Markdown Link Integrity Gate: Every relative link and heading anchor resolves (bin/smirk-linkcheck).
5. Gate 5: CLOC Comment Density Gate: Comment density satisfies documentation thresholds (bin/smirk-cloc).

License & Attribution

• Licensed under the Apache License 2.0 (LICENSE).
• Copyright (c) 2026 Nadia Yvette Chambers.
• AI assistant contributions follow the RFC 2822 trailer format (Assisted-by:). See docs/notes/COMMIT_ATTRIBUTION.md.