Trace operator?

[jessegrosjean]

Is there any interest to add a trace operator? I have an implementation that's working pretty well. I'm wondering if I should clean it up and make a pull request.

I think it would be a good/better solution for these issues:

• Side effect operator #33
• Get range of parsed input #69

It works by adding a .trace(label:) operator. This operator returns upstream output, so you don't need to modify your model to make a trace. Instead trace data is stored in a thread local context. To make a trace and get the resulting context you will:

let (output, context) = try parser.parseWithTrace(input)

The trace is stored as a list of events:

public enum Event {
    case begin(depth: UInt16, label: String, index: Input.Index)
    case end(depth: UInt16, label: String, range: Range<Input.Index>, output: Any)
    case fail(depth: UInt16, label: String, error: Error)
}

The context stores the successful path, plus it also stores all the failed paths.

Compared to the above solutions:

1. Can print hierarchical trace, instead of just flat debug statements.
2. Can use events list to find highlighted keyword ranges. This is instead of having to include keyword ranges in your model, as withRange requires.

[jessegrosjean]

It's making for nice debug traces:

┃$a and $a  ENTER AndExpr
┃$a and $a    ENTER NotExpr
┃$a and $a      ENTER OneOf
┃$a and $a        ENTER ValueExpresion
┃$a and $a          ENTER AdditiveExpr
┃$a and $a            ENTER MultiplicativeExpr
┃$a and $a              ENTER OneOf
┃$a and $a                ENTER OneOf
$a┃ and $a                  MATCH Variable
$a┃ and $a                MATCH OneOf
$a┃ and $a              MATCH OneOf
$a┃ and $a            MATCH MultiplicativeExpr
$a┃ and $a          MATCH AdditiveExpr
$a┃ and $a        MATCH ValueExpresion
$a┃ and $a      MATCH OneOf
$a┃ and $a    MATCH NotExpr
$a and┃ $a    MATCH keyword.and
$a and ┃$a    ENTER AndExpr
$a and ┃$a      ENTER NotExpr
$a and ┃$a        ENTER OneOf
$a and ┃$a          ENTER ValueExpresion
$a and ┃$a            ENTER AdditiveExpr
$a and ┃$a              ENTER MultiplicativeExpr
$a and ┃$a                ENTER OneOf
$a and ┃$a                  ENTER OneOf
$a and $a┃                    MATCH Variable
$a and $a┃                  MATCH OneOf
$a and $a┃                MATCH OneOf
$a and $a┃              MATCH MultiplicativeExpr
$a and $a┃            MATCH AdditiveExpr
$a and $a┃          MATCH ValueExpresion
$a and $a┃        MATCH OneOf
$a and $a┃      MATCH NotExpr
$a and $a┃    MATCH AndExpr
$a and $a┃  MATCH AndExpr

[mackoj]

Yes please, I would love to something like this in the lib.

[jessegrosjean]

I don't have energy to go through back/forth/docs of pull request at moment, but happy to share what I have. Use code as you see fit, anyone is also welcome to turn into a pull request. Good luck, and I'm happy too answer any questions.

Here's how you can use (see highlight, trace):

struct MultiplicativeOpParser: ParserPrinter {
    var body: some ParserPrinter<Substring, MultiplicativeOp> {
        OneOf {
            " * ".map(.case(MultiplicativeOp.multiply)).highlight("keyword.mult")
            " / ".map(.case(MultiplicativeOp.divide)).highlight("keyword.div")
        }.trace("\(Self.self)")
    }
}

Here's how I'm using in my code:

do {
    let parser = OutlinePath.OutlinePathParser()
    let (output, traceContext) = try parser.parseWithTrace(path[...])
    
    self.expressionTraceContext = traceContext
    self.expressionTree = output
} catch let error as TraceError<String.SubSequence> {
    self.expressionTraceContext = error.traceContext
    self.parseError = error.original
    
    if 
        let (end, output) = error.traceContext.longestTopLevelMatch,
        let output = output as? OutlinePath.PrimaryExpression
    {
        self.parseErrorIndex = end
        self.expressionTree = output
    } else {
        self.parseErrorIndex = error.traceContext.input.startIndex
    }
} catch {
    fatalError()
}

• longestTopLevelMatch() get longest successful parse path along with output at that point. This way you can type 1 + 1 + and you will still have 1 + 1 successfully parsed and can generate 2 as the user is typing, even though the expression as a while is incorrect since they haven't typed final number.

import Parsing
import Foundation

public struct TraceError<Input>: Error where Input: Collection {
    public let original: Error
    public let traceContext: TraceContext<Input>
}

extension Parser where Input: Collection {

    @inlinable
    public func trace(_ label: String) -> Parsers.Trace<Input, Self> {
        .init(upstream: self, label: label, highlight: false)
    }

    @inlinable
    public func highlight(_ label: String) -> Parsers.Trace<Input, Self> {
        .init(upstream: self, label: label, highlight: true)
    }

    public func parseWithTrace<C: Collection>(_ input: C) rethrows -> (Output, TraceContext<C>) where Input == C {
        assert(TraceContext<C>.shared == nil)
        
        TraceContext<C>.shared = .init(input: input)
        
        var input = input
        let output: Output
        
        do {
            output = try Parse {
                self
                End<Input>()
            }.parse(&input)
        } catch {
            let error = TraceError<C>(original: error, traceContext: TraceContext<C>.shared!)
            TraceContext<C>.shared = nil
            throw error
        }
        
        let context = TraceContext<C>.shared!
        
        TraceContext<C>.shared = nil
        
        return (output, context)
    }
}

extension Parsers {
    public struct Trace<Input, Upstream: Parser>: Parser where Upstream.Input == Input, Input: Collection {
        @usableFromInline
        let upstream: Upstream

        @usableFromInline
        let label: String

        @usableFromInline
        let highlight: Bool

        @inlinable
        public init(upstream: Upstream, label: String, highlight: Bool) {
            self.upstream = upstream
            self.label = label
            self.highlight = highlight
        }
        
        @inlinable
        public func parse(_ input: inout Upstream.Input) rethrows -> Upstream.Output {
            guard let traceContext = TraceContext<Upstream.Input>.shared else {
                return try upstream.parse(&input)
            }
            
            let startIndex = input.startIndex

            do {
                traceContext.enter(label, highlight: highlight, index: startIndex)
                let output = try upstream.parse(&input)
                traceContext.match(label, highlight: highlight, range: startIndex..<input.startIndex, output: output)
                return output
            } catch {
                traceContext.error(label: label, highlight: highlight, index: startIndex, error: error)
                throw error
            }
        }
    }
}

extension Parsers.Trace: ParserPrinter where Upstream: ParserPrinter {
    @inlinable
    public func print(_ output: Upstream.Output, into input: inout Input) throws {
        try upstream.print(output, into: &input)
    }
}

public class TraceContext<Input> where Input: Collection {
    @inlinable
    static var shared: TraceContext<Input>? {
        get {
            Thread.current.threadDictionary["swift-parsing.trace"] as? TraceContext<Input>
        }
        set {
            if let newValue {
                Thread.current.threadDictionary["swift-parsing.trace"] = newValue
            } else {
                Thread.current.threadDictionary.removeObject(forKey: "swift-parsing.trace")
            }
        }
    }

    public struct Event: CustomDebugStringConvertible {
        public enum EventType {
            case enter
            case match(end: Input.Index, output: Any)
            case error(Error)
        }

        public let label: String
        public let highlight: Bool
        public let depth: UInt16
        public let index: Input.Index
        public let type: EventType
        
        @inlinable
        init(label: String, highlight: Bool, depth: UInt16, index: Input.Index, type: EventType) {
            self.label = label
            self.highlight = highlight
            self.depth = depth
            self.index = index
            self.type = type
        }
        
        public var debugDescription: String {
            switch self.type {
            case .enter:
                return "ENTER: \(label)"
            case .match:
                return "MATCH: \(label)"
            case .error:
                return "ERROR: \(label)"
            }
        }
    }

    public let input: Input

    @usableFromInline
    var events: [Event]

    @usableFromInline
    var depth: UInt16

    init(input: Input) {
        self.input = input
        events = []
        depth = 0
    }
        
    public var longestTopLevelMatch: (end: Input.Index, output: Any)? {
        events.compactMap { event -> (Input.Index, Any)? in
            if case .match(let end, let output) = event.type, event.depth == 0 {
                return (end, output)
            }
            return nil
        }.last
    }
    
    public func traceEvents(
        removePairs: Bool = true,
        removeBacktracking: Bool = true,
        removeHighlighting: Bool = true
    ) -> [Event] {
        var out: [Event] = []

        for event in events {
            if event.highlight && removeHighlighting {
                continue
            }
            
            switch event.type {
            case .enter:
                // Traced error paths are already removed in error case. This is neccessary
                // to remove errors that happen in untraced paths. For example you might have a OneOf
                // case that successfully matches a traced parser, but then fails on a following untraced parser.
                if removeBacktracking {
                    while let last = out.last, last.depth >= event.depth, last.index >= event.index {
                        _ = out.popLast()
                    }
                }
                out.append(event)
            case .match:
                // Compress results by remove enter if no other events between enter/match pair.
                if removePairs && out.last?.depth == event.depth {
                    out.removeLast()
                }
                out.append(event)
            case .error:
                if removeBacktracking {
                    while let last = out.last, last.depth > event.depth {
                        _ = out.popLast()
                    }
                    _ = out.popLast() // enter
                } else {
                    if removePairs && out.last?.depth == event.depth {
                        out.removeLast()
                    }
                    out.append(event)
                }
           }
        }
        
        return out
    }
    
    public func traceDescription(
        removePairs: Bool = true,
        removeBacktracking: Bool = true,
        removeHighlighting: Bool = true
    ) -> String {
        let events = traceEvents(
            removePairs: removePairs,
            removeBacktracking: removeBacktracking,
            removeHighlighting: removeHighlighting
        )

        var description = ""
        
        for event in events {
            let label = event.label
            let depth = event.depth
            let index = event.index
            
            switch event.type {
            case .enter:
                let indent = String(repeating: "  ", count: Int(depth + 1))
                let state = "\(input[..<index])┃\(input[index..<input.endIndex])"
                description += "\(state)\(indent)ENTER \(label)\n"
            case .match(let end, _):
                let indent = String(repeating: "  ", count: Int(depth + 1))
                let range = index..<end
                let state = "\(input[..<range.lowerBound])\(input[range])┃\(input[range.upperBound...])"
                description += "\(state)\(indent)MATCH \(label)\n"
            case .error:
                let indent = String(repeating: "  ", count: Int(depth + 1))
                let state = "\(input[..<index])┃\(input[index..<input.endIndex])"
                description += "\(state)\(indent)ERROR \(label)\n"
            }
        }
        
        return description
    }
    
    @inlinable
    func enter(_ label: String, highlight: Bool, index: Input.Index) {
        events.append(.init(label: label, highlight: highlight, depth: depth, index: index, type: .enter))
        depth += 1
    }
    
    @inlinable
    func match(_ label: String, highlight: Bool, range: Range<Input.Index>, output: Any) {
        depth -= 1
        events.append(.init(label: label, highlight: highlight, depth: depth, index: range.lowerBound, type: .match(end: range.upperBound, output: output)))
    }
    
    @inlinable
    func error(label: String, highlight: Bool, index: Input.Index, error: Error) {
        depth -= 1
        events.append(.init(label: label, highlight: highlight, depth: depth, index: index, type: .error(error)))
    }
    
}

[jessegrosjean]

Oh, and here's how I use to do syntax highlighting:

attributedString.beginEditing()
attributedString.setAttributes(defaultAttributes, range: NSMakeRange(0, attributedString.length))

if let trace = expressionTraceContext {
    for event in trace.traceEvents(removePairs: true, removeBacktracking: true, removeHighlighting: false) {
        if case .match(let endIndex, _) = event.type, event.highlight {
            let range = NSRange(event.index..<endIndex, in: trace.input)
            if event.label.starts(with: "keyword") {
                attributedString.addAttribute(.foregroundColor, value: NSColor.secondaryLabel, range: range)
            }
        }
    }
    
    if let parseErrorIndex {
        attributedString.addAttributes([
            .foregroundColor : NSColor.textColor,
            .backgroundColor : NSColor.systemRed.withAlphaComponent(0.2),
        ], range: NSRange(parseErrorIndex..., in: trace.input))
    }
}

attributedString.endEditing()

[mackoj]

Thanks