Bike: Outline Path Implementation

This post is for Swift developers interested in the implementation details of Bike’s outline paths. It’s inspired by Swift Blog Carnival: Tiny Languages.

Important Links:

What are Outline Paths?

Bike’s outline is a tree structure where each row has a type and associated attributes. Each row also has attributed text, composed of text runs with associated attributes.

Bike needs an efficient and expressive way to find/match rows and runs. Users want to find rows that contain text, tasks that aren’t done, etc. Stylesheets want to style rows/runs based on their type and attributes.

Outline paths enable these cases and more. For outline path syntax see the Bike User Guide; this post is about the design and implementation.

Explore Outline Paths (Tooling)

Download the Bike 2.0 Preview and then open the menu item:

Use the explorer to see how outline paths evaluate against the current outline, plus live syntax highlighting, parse tree, and parse trace.

Design and Implementation

There are three main components to the implementation: the Abstract Syntax Tree (AST), the parser, and the evaluator.

My implementation is, I think/hope/wonder, pretty standard. The most interesting bit is using a trace parser for syntax highlighting and error recovery.

Abstract Syntax Tree (AST)

The AST is a tree of Swift enums and structs that represent your tiny language’s grammar. In my implementation I also attach metadata to some AST structs, and that allows me to optimize the evaluator by pre-computing some information immediately after parsing.

public indirect enum PrimaryExpression: Equatable {
    case pathExpression(PathExpression)
    case valueExpression(ValueExpression)
}

public indirect enum PathExpression: Equatable {
    case union(PathExpression, PathExpression)
    case except(PathExpression, PathExpression)
    case intersect(PathExpression, PathExpression)
    case group(PathExpression)
    case path(Path)
}

public struct Path: Equatable {
    public let absolute: Bool
    public var steps: [Step]
    public var meta: Meta!
}

public struct Step: Equatable {
    public var axis: Axis?
    public var filter: Filter?
    public var slice: Slice?
    public var meta: Meta!
}

...

Parsing with swift-parsing

The parser is implemented using swift-parsing. It’s a printer-parser, so it can both parse text into an AST and print an AST back to text.

When using swift-parsing your parser is composed of many smaller parsers. A typical parser in Bike’s grammar looks like this:

struct PathExpressionUnionParser: ParserPrinter {
    var body: some ParserPrinter<Substring, PathExpression> {
        ParsePrint(.caseOptionalCombine(PathExpression.union)) {
            PathExpresionExceptParser()
            Optionally {
                Whitespace(1...)
                "union".highlight("keyword.op.set")
                Whitespace(1...)
                PathExpressionUnionParser()
            }
        }.trace("PathExpressionUnionParser")
    }
}

This is standard swift-parsing code with the addition of my own .trace("…") and .highlight("…") functions. Those functions each construct a Trace parser that emits events to a thread-local trace context.

The trace context accumulates events in parse order with byte ranges and the output produced. Once a parse finishes, the trace contains all the information I need for syntax highlighting and error recovery.

Evaluation

The evaluator walks the AST against the outline data to produce results. The core algorithm is to walk a Path’s steps from a starting row passing the result of each step into the next:

var inputs: ElementSet = .single(start)
for step in path.steps {
    inputs = evaluate(step, inputs: inputs)
    if inputs.isEmpty { return .empty }
}
return inputs

Evaluating a step is axis traversal, then type-test filter, then predicate filter, then slice.

Example Implementation

I’ve tried to keep my description high-level. The actual implementation is long with many details. Long, but pretty straightforward (once you get all the typing right) and easy to modify.

I’ve used Claude Code to extract a simplified implementation so that you can see how the pieces above fit together.