Dealing with recursing types

[randomeizer]

So, in my parsing adventures I have finally come across a recursing parser situation. In my case, it was with the children definition in the XML spec.

There are two challenges in getting recursive parsing to work:

1. Compile time:
   • Type recursion. This is solved by circuit-breaking with type erasure, such as via AnyParser, etc.
   • Value recursion. This is solved by having your parser defined inside a function or computed property.
2. Runtime:
   • Infinite loop on parser creation. This is solved by having at least one parser in the loop created lazily. This can be achieved via the Lazy parser.

Here's a simple example of a recursing type:

enum ArithmeticExpression: Equatable {
    case value(Int)
    indirect case add(ArithmeticExpression, ArithmeticExpression)
}

And here's a parser which works.

extension ArithmeticExpression {
    static var parser: AnyParser<Substring, ArithmeticExpression> {
        OneOf {
            Int.parser().map(ArithmeticExpression.value)
            Lazy {
                "("
                Self.parser
                "+"
                Self.parser
                ")"
            }
            .map(ArithmeticExpression.add)
        }
        .eraseToAnyParser()
    }
}

It has Lazy around the recursing part of the parser, and erases at the top level.

Technically, only the recursing part needs to be type-erased though, so you could also do this:

extension ArithmeticExpression {
    static var parser: OneOf<Parsers.OneOf2<Parsers.Map<From<Conversions.SubstringToUTF8View, Parsers.IntParser<Substring.UTF8View, Int>>, ArithmeticExpression>, AnyParser<Substring, ArithmeticExpression>>> {
        OneOf {
            Int.parser().map(ArithmeticExpression.value)
            Lazy {
                "("
                Self.parser
                "+"
                Self.parser
                ")"
            }
            .map(ArithmeticExpression.add)
            .eraseToAnyParser()
        }
    }
}

You end up with a pretty gnarly type signature, but it only erases at the point where it is required to to allow correct recursion.

To make my own life simpler to remember all the steps required for recursion, I've created a RecursivelyParse parser, which both executes the wrapped parsers lazily, and erases the parsed types. It currently looks like this:

public struct RecursivelyParse<Input, Output>: Parser {
    @usableFromInline let doParse: (inout Input) throws -> Output

    @inlinable
    public init<P>(@ParserBuilder _ wrapped: @escaping () -> P)
    where P: Parser, P.Input == Input, P.Output == Output
    {
        var lazyParser: P?
        doParse = { input in
            guard let parser = lazyParser else {
                let parser = wrapped()
                lazyParser = parser
                return try parser.parse(&input)
            }
            return try parser.parse(&input)
        }
    }
    
    @inlinable
    public func parse(_ input: inout Input) throws -> Output {
        try doParse(&input)
    }
}

Because it's type-erasing, I had to also create a related RecursivelyParsePrint, which implements ParsePrint in a similar manner (is there any way to have a single type when type-erasing?)

This is used like this:

extension ArithmeticExpression {
    static var parser: OneOf<Parsers.OneOf2<Parsers.Map<From<Conversions.SubstringToUTF8View, Parsers.IntParser<Substring.UTF8View, Int>>, ArithmeticExpression>, RecursivelyParse<Substring, ArithmeticExpression>>> {
        OneOf {
            Int.parser().map(ArithmeticExpression.value)
            RecursivelyParse {
                Parse(ArithmeticExpression.add) {
                    "("
                    Self.parser
                    "+"
                    Self.parser
                    ")"
                }
            }
        }
    }
}

It now correctly protects both the type signature and the lazy loading, hopefully reducing errors on my part down the track. I haven't implemented it yet, but plan to also support 'mapping' directly in the RecursivelyParse type, so you could do this:

extension ArithmeticExpression {
    static var parser: OneOf<Parsers.OneOf2<Parsers.Map<From<Conversions.SubstringToUTF8View, Parsers.IntParser<Substring.UTF8View, Int>>, ArithmeticExpression>, RecursivelyParse<Substring, ArithmeticExpression>>> {
        OneOf {
            Int.parser().map(ArithmeticExpression.value)
            RecursivelyParse(ArithmeticExpression.add) {
                "("
                Self.parser
                "+"
                Self.parser
                ")"
            }
        }
    }
}

Which is a bit neater anyway. The Int.parser() is making up most of the noise in the signature at this point.

Is it worth having something like RecursivelyParse in the standard library?

Yes, you can homebrew it already using Lazy and AnyParser, but it's not necessarily obvious, and you can forget to use Lazy and still have it compile correctly. This makes your intention explicit.

[tgrapperon]

Good idea @randomeizer!
Parsing/printing trees is something very common, and this parser would probably find many uses.

I'm slightly concerned about the usability though. It "feels" a little odd. We have to acknowledge the recursivity, but the Recursively parser doesn't provide additional features besides the sugar, so we have to think about using it only when we are forced to do so by the compiler/runtime. I don't know if I'm clear, but in other words, this parser doesn't reflect an intent, but it provides a workaround to build and run the meaningful parsers it composes. Maybe Lazy steps a foot in this category, but I'm not seeing similar parsers in the library on the top of my head.

If I'd encounter the situation, I would personally probably try to Lazy the whole thing and eraseToAnyParser():

extension ArithmeticExpression {
  static var parser: AnyParser<Substring, ArithmeticExpression> {
    Lazy {

      OneOf {
        Int.parser().map(ArithmeticExpression.value)
        Parse(ArithmeticExpression.add) {
          "("
          Self.parser
          "+"
          Self.parser
          ")"
        }
      }

    }.eraseToAnyParser()
  }
}

This is only an idea, I don't know if it works.

If I would absolutely need to avoid erasure to AnyParser, I would define an ArithmeticExpressionParser to perform the same task in its parse function. It would then be mostly of aesthetical purposes I guess, as there is already some type erasure happening in the init of RecursivelyParse. Did you benchmark RecursivelyParse against explicit definitions?

But this is overall a very frequent use-case, so I'm definitely very interested to see where it goes!

[randomeizer]

I am finding myself using a lot of .map(.case(MyEnum.case)) statements in combination with OneOf, but I agree that it is used in other situations as well, such as allowing strings to be single- or double-quoted, etc.

You can also have recursion with class values (although not structs, as far as I can tell), so not sure if Indirect is too specific a name?

[tgrapperon]

so not sure if Indirect is too specific a name?

The inspiration comes from enumerations where its unique purpose is to mark recursive cases. Such cases are boxed, and other measures I'm not remembering are also taken to avoid infinite recursion, but it provides nothing on the user's side. It just allows the compiler to successfully build (and to be honest, I don't understand why it is not automatic yet).

That's mostly this parallel that made me think about Indirect, but there are probably other solutions.

[randomeizer]

Yeah, there is definitely some correlation.

[tgrapperon]

but it provides nothing on the user's side

As an aside, and while thinking about it, I imagined that we could use the boxing to build a @Box property wrapper around an indirect enum case:

@propertyWrapper
public enum BoxEnum<Value> {
  indirect case value(Value)
  public init(wrappedValue: Value) {
    self = .value(wrappedValue)
  }
  public var wrappedValue: Value {
    get {
      switch self {
      case .value(let value):
        return value
      }
    }
    set {
      self = .value(newValue)
    }
  }
}

The "standard" class counterpart is:

@propertyWrapper
public struct BoxClass<Value> {
  @usableFromInline
  final class Box {
    var value: Value
    init(_ value: Value) { self.value = value }
  }
  @usableFromInline
  let box: Box
  public init(wrappedValue: Value) {
    self.box = Box(wrappedValue)
  }
  public var wrappedValue: Value {
    get { box.value }
    set { box.value = newValue }
  }
}

I've benchmarked this with a 8kB value, and if it initializes almost twice faster with enum, it writes almost twice slower:

name               time       std        iterations
---------------------------------------------------
Box.Class - Create 362.000 ns ± 137.63 %    1000000
Box.Enum - Create  214.000 ns ± 207.59 %    1000000
Box.Class - Read   278.000 ns ± 179.89 %    1000000
Box.Enum - Read    267.000 ns ± 125.50 %    1000000
Box.Class - Set    191.000 ns ± 143.83 %    1000000
Box.Enum - Set     383.000 ns ±  87.83 %    1000000

I wonder if there is a way to improve this.

This is totally off-topic, but I think it's good to know. TCA can rapidly have stack-overflow issues as the State grows and boxing property wrappers can help. It would be interesting to check how many times these values can be created vs written in a standard TCA app.

[tgrapperon]

I also wonder if there are some neat tricks we can find in using an enum property wrapper (with or without indirect), especially if it projects self. Using one enum per arity, we can maybe tie some kind of exhaustivity to the values being wrapped for example.

[stephencelis]

There are two challenges in getting recursive parsing to work:

1. Compile time:

   • Type recursion. This is solved by circuit-breaking with type erasure, such as via AnyParser, etc.
   • Value recursion. This is solved by having your parser defined inside a function or computed property.

2. Runtime:

   • Infinite loop on parser creation. This is solved by having at least one parser in the loop created lazily. This can be achieved via the Lazy parser.

It's worth pointing out that swift-parsing already contains an example arithmetic parser in its benchmarks suite, which is recursive but does not require explicit type erasure via AnyParser or explicit laziness via Lazy:

https://github.com/pointfreeco/swift-parsing/blob/6c69cc7a39519ab48bda05ef806b98b2bedfd98c/Sources/swift-parsing-benchmark/Arithmetic.swift

Instead it implicitly defers laziness to a "value recursion" solution as you mention above. We believe that conforming your own types to parsers is probably the friendliest way to maintain a complex parser as it grows, especially when recursion is introduced.

It's also worth noting that in the future we'd love to adopt a more SwiftUI-like interface for parsers. Something like the following:

struct MyParser: Parser {
  var body: some Parser<Substring, Bool> {
    // @ParserBuilder syntax in here
  }
}

This would provide type-level recursion without the need for explicit erasure or laziness.

We're still a Swift version or two away from being able to support this, but potentially soon enough! 😄

[randomeizer]

I hadn't noticed your Arithmetic parser, although it can be simpler than my example because it's resolving everything down to a simple Double during the parsing process. In my case, I'm preserving the tree structure built by the parser, thus the need for type erasure.

Either way, it would be good to have some documentation with recommendations for tackling the topic. I doubt I will be the last to encounter it.

[stephencelis]

although it can be simpler than my example because it's resolving everything down to a simple Double during the parsing process. In my case, I'm preserving the tree structure built by the parser, thus the need for type erasure.

I think it should be equivalent, but do you have a reason to believe it is not?

The JSON parser, which parses into an indirect enum, can also be written in this way to avoid Lazy and AnyParser: https://github.com/pointfreeco/swift-parsing/blob/56b9f16967a75680c9e9acce5ea716c24dfd4d93/Sources/swift-parsing-benchmark/JSON.swift

[randomeizer]

Thinking about it, the custom Parser is essentially doing some type erasure. The issue I was bumping up against was using the basic parsers to compose into more complex ones, which is what produced the loop in the type signature. So yeah, writing a custom parser and performing the parsing work inside the parse method should generally work around the issue.