A minimal companion to "Bike: Outline Path Implementation"

OutlinePathTiny.swift

//  Example from https://www.hogbaysoftware.com/posts/bike-outline-path-implementation/
//  Demonstrates the same three-component design — AST, swift-parsing parser with trace, and evaluator

import Foundation
import Parsing

// MARK: - AST

struct Path: Equatable {
    let absolute: Bool
    let steps: [Step]
}

struct Step: Equatable {
    let text: String
}

// MARK: - Tree

final class Node {
    let text: String
    var children: [Node]
    init(_ text: String, _ children: [Node] = []) {
        self.text = text
        self.children = children
    }
}

// MARK: - Trace

/// Records labelled, ranged events emitted by traced parsers during a parse.
/// The same trace drives syntax highlighting and partial-AST error recovery
/// in the real OutlinePath implementation; here we just dump labels and
/// matched substrings as a stand-in for highlighting, plus surface the
/// longest top-level match for recovery.
final class TraceContext {
    enum EventType {
        case enter
        case match(endIndex: String.Index)
        case error(Swift.Error)
    }

    struct Event {
        let label: String
        let highlight: Bool
        let index: String.Index
        let type: EventType
    }

    let input: Substring
    private(set) var events: [Event] = []

    init(input: Substring) {
        self.input = input
    }

    // Thread-local current context. Set by `parse(_:)` for the duration of a
    // parse so traced parsers don't need to be threaded an explicit argument.
    private static let threadKey = "OutlinePathTiny.TraceContext"
    static var shared: TraceContext? {
        get { Thread.current.threadDictionary[threadKey] as? TraceContext }
        set { Thread.current.threadDictionary[threadKey] = newValue }
    }

    fileprivate func enter(_ label: String, highlight: Bool, at index: String.Index) {
        events.append(Event(label: label, highlight: highlight, index: index, type: .enter))
    }
    fileprivate func match(_ label: String, highlight: Bool, at index: String.Index, end: String.Index) {
        events.append(Event(label: label, highlight: highlight, index: index, type: .match(endIndex: end)))
    }
    fileprivate func error(_ label: String, highlight: Bool, at index: String.Index, error: Swift.Error) {
        events.append(Event(label: label, highlight: highlight, index: index, type: .error(error)))
    }

    /// End-index of the longest successful top-level (`label == "Path"`)
    /// match recorded during the parse. When the overall parse fails this is
    /// where the partial AST ends — enough information for a UI to anchor
    /// an error indicator at the byte where the parser gave up. Errors from
    /// transient backtracking (e.g. `Many` trying one more element than it
    /// can take) are ignored on purpose.
    var longestTopLevelMatchEnd: String.Index? {
        var best: String.Index?
        for event in events {
            if case .match(let end) = event.type, event.label == "Path" {
                best = best.map { Swift.max($0, end) } ?? end
            }
        }
        return best
    }
}

// MARK: - Trace combinator

extension Parser where Input == Substring {
    func trace(_ label: String) -> TracedParser<Self> {
        TracedParser(upstream: self, label: label, highlight: false)
    }
    func highlight(_ label: String) -> TracedParser<Self> {
        TracedParser(upstream: self, label: label, highlight: true)
    }
}

struct TracedParser<Upstream: Parser>: Parser where Upstream.Input == Substring {
    typealias Input = Substring
    typealias Output = Upstream.Output

    let upstream: Upstream
    let label: String
    let highlight: Bool

    func parse(_ input: inout Substring) rethrows -> Output {
        let start = input.startIndex
        let ctx = TraceContext.shared
        ctx?.enter(label, highlight: highlight, at: start)
        do {
            let output = try upstream.parse(&input)
            ctx?.match(label, highlight: highlight, at: start, end: input.startIndex)
            return output
        } catch {
            ctx?.error(label, highlight: highlight, at: start, error: error)
            throw error
        }
    }
}

extension TracedParser: ParserPrinter where Upstream: ParserPrinter {
    func print(_ output: Output, into input: inout Substring) throws {
        try upstream.print(output, into: &input)
    }
}

// MARK: - Parsers

struct PathParser: ParserPrinter {
    var body: some ParserPrinter<Substring, Path> {
        ParsePrint(.memberwise(Path.init)) {
            "/".highlight("step.separator").map { true }
            Many {
                StepParser()
            } separator: {
                "/".highlight("step.separator")
            }
        }
        .trace("Path")
    }
}

struct StepParser: ParserPrinter {
    var body: some ParserPrinter<Substring, Step> {
        ParsePrint(.memberwise(Step.init)) {
            Prefix(1..., while: { $0 != "/" })
                .map(.string)
                .highlight("step.text")
        }
        .trace("Step")
    }
}

// MARK: - Top-level parse

struct ParseResult {
    let path: Path?
    let traceContext: TraceContext
    let error: Swift.Error?
}

/// Parses a path string and returns the AST plus the trace recorded during
/// the parse. On error the AST is nil but the trace still contains every
/// label that successfully matched before the failure — that's the data a UI
/// would use to highlight the prefix and anchor an error indicator.
func parse(_ input: String) -> ParseResult {
    let ctx = TraceContext(input: input[...])
    TraceContext.shared = ctx
    defer { TraceContext.shared = nil }

    var remaining: Substring = input[...]
    do {
        let path = try Parse {
            PathParser()
            End<Substring>()
        }.parse(&remaining)
        return ParseResult(path: path, traceContext: ctx, error: nil)
    } catch {
        return ParseResult(path: nil, traceContext: ctx, error: error)
    }
}

// MARK: - Evaluator

/// Walks a path against a tree, returning all nodes the path matches. Each
/// step threads its result into the next. The match rule is exact text
/// equality; the real implementation supports type tests, predicates, axes,
/// and slices that this demo strips out.
func evaluate(_ path: Path, in tree: Node, current: Node? = nil) -> [Node] {
    var inputs: [Node] = path.absolute ? [tree] : [current ?? tree]
    for step in path.steps {
        var next: [Node] = []
        for input in inputs {
            for child in input.children where child.text == step.text {
                next.append(child)
            }
        }
        if next.isEmpty { return [] }
        inputs = next
    }
    return inputs
}

// MARK: - Demo

func runDemo() {
    let tree = Node("root", [
        Node("foo", [
            Node("bar"),
            Node("baz", [Node("qux")]),
        ]),
        Node("foo", [Node("bar")]),
    ])

    let queries = ["/foo/bar", "/foo/baz/qux", "/foo/missing", "/foo/"]

    for query in queries {
        print("Query: \(query)")
        let result = parse(query)

        print("  Trace (matched substrings):")
        for event in result.traceContext.events {
            guard case .match(let end) = event.type else { continue }
            let range = event.index..<end
            let text = result.traceContext.input[range]
            let tag = event.highlight ? "[highlight]" : "[trace]    "
            print("    \(tag) \(event.label): \"\(text)\"")
        }

        if let path = result.path {
            print("  AST: \(path)")
            print("  Matches:")
            for node in evaluate(path, in: tree) {
                print("    - \(node.text)")
            }
        } else if let error = result.error {
            print("  Error: \(error)")
            if let end = result.traceContext.longestTopLevelMatchEnd {
                let input = result.traceContext.input
                let prefix = input[..<end]
                let offset = input.distance(from: input.startIndex, to: end)
                print("  Recovery: longest top-level match ended at offset \(offset) (\"\(prefix)\")")
            }
        }
        print()
    }
}