Disclaimer & Intro

This post has been made as my notes, even though I attempt to explain what I have built and how, I do not owe anyone any explanation. Do NOT expect anything.

My blog is my garden.

WARNING: No AI was used anywhere in this project. Not one token. Not for the code, not for debugging, not even for the commit messages. Just a 37-year-old paper, a Rust compiler, and free time that probably should have been spent sleeping.

A 1987 Paper and a Free Weekend

I came across Rob Pike's 1987 paper — Structural Regular Expressions — and could not put it down.

The core complaint Pike makes is one I have felt for years but never had language for: UNIX text tools are fundamentally weakened by their built-in concept of a line. grep, sed, awk — every single one of them thinks files are arrays of lines. That is the only model they know. And when the problem you are solving does not fit neatly into that model, you spend more code fighting the tool than solving the actual problem.

Pike's solution is elegant. Use regular expressions not just to select text but to describe the structure of it. An x/pattern/ command that extracts every match. A y/pattern/ that extracts the gaps between matches. Nesting these together — x/(.+\n)+/ g/%A.*Bimmler/ x/.*\n/ g/%T/p — and you have something that reads like a data pipeline, not a sequence of line-oriented hacks.

The paper is six pages. I read it twice on a Saturday morning. By Saturday afternoon I had started writing se.

What se Is

se is a structural text pipeline for Apple Silicon. It operates on views — (start, end) byte ranges over a memory-mapped file — rather than lines. Every command transforms a stream of views into a new stream. Edits are recorded out of band and stitched into the output at the end. The mapped file is never modified in place until you explicitly ask for -i.

I want to be clear about what this table means and what it does not. se wins on substitution and literal location because those hit the NEON path. It loses to grep on regex line-filtering because that is grep's home turf and grep has had decades of optimization for exactly that shape of problem. The numbers are honest.

The Commands

The language is a pipeline of commands separated by whitespace or ;. Here are the selectors:

• x/re/ — Extract: replace each view with sub-views matching re. This is Pike's core idea.
• y/re/ / z/re/ — Yank/split: replace each view with the gaps between matches of re. The complement of extract.
• g/re/ — Keep only views that contain a match of re.
• v/re/ — Drop views that contain a match of re.

And the actions:

• s/re/repl/ — Substitute. Supports g for global, i for case-insensitive.
• c/text/ — Change: overwrite each view with text. Out of band, no allocation per match.
• p — Print each view to stdout.
• = — Print start,end,length byte offsets for each view.
• N — Merge adjacent views into one spanning view.
• r/sep/ — Reduce: fold all views into one joined by sep.
• t { ... } — Branch if a substitution was made. Mirrors sed's t.
• m/re/ { ... } — Map: extract matches of re and run the block on each.
• { ... } — Group: run a sub-pipeline on each incoming view.
• /pattern/ { ... } — Awk binder: run the block on views matching pattern.

The composition is the point. A program that begins with / is automatically wrapped in a line extractor, so:

se '/error/ { p }' system.log

...works exactly like grep error system.log. And:

se 'x/.*\n/ g/error/ p' system.log

...is the same thing but explicit, which means you can build on it:

se 'x/[^\n]*error[^\n]*\n/ x/\[[^\]]+\]/ r/,/ p' system.log

Extract all error lines, extract the bracketed tag from each, join them with commas, print. That is not grep. That is not sed. That is something both tools separately cannot(unless you try VERY hard) do in one shot.

The Architecture

src/
  main.rs        — file mapping, pipeline driving, stitch + in-place write
  cli.rs         — clap argument definitions
  parser/        — program text → Pipeline
  core/
    types.rs     — ByteView, Mutation, Command trait, Pipeline, ExecutionContext
    mmap.rs      — mmap source, stdin ring-buffer, F_NOCACHE / madvise
  engine/
    regex.rs     — StructuralRegex: routes literals → SIMD, rest → regex-automata
    simd.rs      — NEON vceqq_u8 byte + substring scan, SWAR fallback
  commands/      — one type per command, implementing Command
  platform/
    macos.rs     — kqueue watch loop (EVFILT_VNODE / EVFILT_SIGNAL)

The Command trait is the central abstraction:

pub trait Command: Sync + Send {
    fn apply<'a>(
        &'a self,
        views: Box<dyn Iterator<Item = ByteView<'a>> + 'a>,
        ctx: &'a ExecutionContext,
    ) -> Box<dyn Iterator<Item = ByteView<'a>> + 'a>;

    fn rewrites(&self) -> bool { false }
}

Every command takes a lazy iterator of ByteViews and returns another lazy iterator of ByteViews. The pipeline is fused. Nothing is evaluated until you call .count() at the end to exhaust it. For a 1.47 GiB log file, x/.*\n/ over the whole thing never materialises all the lines in memory at once — it yields them on demand.

ByteView is just a &'a [u8] with some arithmetic helpers:

#[derive(Clone, Copy, Debug)]
pub struct ByteView<'a> {
    pub slice: &'a [u8],
}

Zero-copy. The view is a pointer into the mmap. No allocation happens when you extract or filter — you are just narrowing the window you look through.

Mutations work differently. When s/// or c// records an edit, it pushes a Mutation { start, end, replacement: Arc<[u8]> } into a Mutex<Vec<Mutation>> on the ExecutionContext. The Arc<[u8]> means recording one of 50 million substitutions is a refcount bump, not a heap allocation per match. At the end, stitch() walks the original slice, skips over mutated spans, and writes the replacements in order.

The SIMD Engine

The engine has two backends. Patterns that contain no regex metacharacters route to SimdLiteralMatcher. Everything else routes to regex-automata's meta engine.

const META: &[char] = &[
    '.', '*', '+', '?', '^', '$', '(', ')', '[', ']', '{', '}', '|', '\\',
];
let is_literal = !pattern.is_empty() && !pattern.chars().any(|c| META.contains(&c));

if is_literal && !flags.case_insensitive {
    return Ok(Self {
        backend: EngineBackend::Simd(Arc::new(SimdLiteralMatcher::new(pattern.as_bytes()))),
        pattern: pattern.to_owned(),
    });
}

The NEON scanner uses vceqq_u8 to compare 16 bytes at a time against the target byte, then vmaxvq_u8 to check if any lane fired:

while ptr.add(16) <= end {
    let chunk = vld1q_u8(ptr);
    let cmp = vceqq_u8(chunk, target);
    if vmaxvq_u8(cmp) != 0 {
        for i in 0..16 {
            if *ptr.add(i) == byte {
                return Some(ptr.add(i).offset_from(base) as usize);
            }
        }
    }
    ptr = ptr.add(16);
}

For multi-byte patterns, the NEON scanner finds candidates by scanning for the first byte, then verifies the rest with a bounds-safe starts_with. This is why literal substitution is ~10× faster than BSD sed — no regex engine involved, just a vectorised byte hunt.

On non-NEON targets there is a SWAR fallback using u64 XOR tricks. It also compiles and runs on Linux x86, just without the Apple Silicon speed advantage.

The I/O Layer

On macOS, se bypasses the unified buffer cache with F_NOCACHE on every mapped file, then hints the kernel with madvise(SEQUENTIAL | WILLNEED). This means every benchmark run re-reads the full file from disk rather than from the page cache — which is the honest way to measure. BSD sed and grep were reading from a warm cache in my benchmarks and se still won on substitution and literal location.

Stdin gets a 4 MiB anonymous mmap ring buffer. Under 4 MiB: zero copies, one mmap. Over 4 MiB: spills to a memfd tempfile, then maps that. Either way, se sees a &[u8] slice and doesn't know or care how it got there.

In-place edits (-i / -i=.bak) go through an atomic rename: write to a sibling tempfile in the same directory, then rename() over the original. Crash mid-write: original survives.

Watch mode (-w) uses kqueue with EVFILT_VNODE (NOTE_WRITE | NOTE_EXTEND | NOTE_DELETE) and EVFILT_SIGNAL (SIGINT). Editors that do replace-by-rename (which is most of them) trigger a NOTE_DELETE — se retries reopening the file for up to a second in 50ms increments to handle that correctly.

What Does Not Work

I said no AI and I meant it, which also means no hand-waving past the parts that are unfinished. Short version:

• Named capture groups in s/// replacement ($name / \1) are not implemented. The regex engine supports them but the substitution logic does not reference them yet. Literal replacement only.
• The parallel m/re/ { ... } was removed (I was working on this initially). Rayon workers sharing a buffered stdout lock deadlock when the block does p. Sequential and deterministic is the right default anyway; a correct parallel design would need each branch to own a private output buffer and merge in order. Maybe try to solve it later.
• argv[0] dispatch to emulate sed/awk/grep by symlink is not implemented but something I want to do.
• No miette source-span diagnostics. Errors come back as anyhow messages with a non-zero exit code. Clear, but not pretty.

The NEON paths and the kqueue watch loop need unsafe. Each unsafe block has a safety comment. #![forbid(unsafe_code)] is not applied crate-wide because that would be a lie, and I prefer my code honest.

The Build

Requires Rust 1.85+ (Edition 2024) and an Apple Silicon Mac. The other targets compile and run via SWAR fallbacks but the release profile is tuned for aarch64-apple-darwin:

[profile.release]
lto = "fat"
codegen-units = 1
panic = "abort"
opt-level = 3
strip = "debuginfo"

The Source Code is still not ready to be released!

To reproduce the benchmarks, we can run:

scripts/bench.sh 1

That generates a ~1 GiB synthetic log under $TMPDIR and times se, sed, grep, and awk against it. Five runs each, minimum wall-clock reported. The script is in the repo; read it before you trust the numbers.

A Few Examples Worth Noting

Global substitute, all occurrences — this is the ~10× case:

se "s/struct/class/g" source.cpp

grep but for lines with case-insensitive match:

se 'x/.*\n/ g/error/i p' system.log

Redact all quoted strings in a JSON config, keep a backup:

se -i=.bak 'x/"[^"]*"/ c/"***"/' config.json

Extract error lines, pull the bracketed process tag from each, join with commas:

se 'x/[^\n]*error[^\n]*\n/ x/\[[^\]]+\]/ r/,/ p' system.log

Byte offsets and lengths of every TODO in a Rust file:

se 'x/TODO/ =' main.rs

That last one — = — is straight from Pike. His paper talks about a structural diff that reports changed sentences instead of changed lines. se does not do that yet. But the byte offset output is the foundation you would need. The first stable release should also have that.

Conclusion

I built this in free time because the paper annoyed me in the best possible way. Pike was right in 1987. The line is still the wrong unit of abstraction for most text processing problems people actually have. sed and grep are still great at what they were designed for. For everything else you are either writing awk that fights itself or chaining twelve tools together and praying to the *nix ecosystem.

se is a structural tool. It is faster than sed on its home turf and slower than grep on its home turf. That is exactly how it should be - for now!!

Engineering is measurable. Measure it.

Jai Hind.

Wake up. Dig deeper.

#rust #development #research #security engineering #systems #linux #macos

curl -fsSL https://xer0x.in/blog/se-1/content.txt | openssl dgst -sha256 | grep -qi 3ad2154f0da631e5f6962e939f06c1e1703d7f6f6a8ddfa1fe0efe058afdfc6e && echo "signature ok" || echo "TAMPERED"

← Back to blog