Partial block result builder fails to pick correct overload and generates compiler error

[JaapWijnen]

Description
Partial block result builder fails to pick correct overload and generates a compiler error Ambiguous use of 'parser(of:)'

Steps to reproduce
Paste the following code into a new project
(This issue is a reduction of trying to compile an example (final 4 lines of the code below) of the swift-parsing package)

//MARK: Parsers
@rethrows public protocol Parser<Input> {
    associatedtype Input
}

extension String: Parser {
    public typealias Input = Substring
}

extension Int {
    static func parser(
        of inputType: Substring.Type = Substring.self
    ) -> FromSubstringToUTF8<IntParser<Substring.UTF8View>> {
        FromSubstringToUTF8 { IntParser<Substring.UTF8View>() }
    }

    static func parser(
        of inputType: Substring.UTF8View.Type = Substring.UTF8View.self
    ) -> IntParser<Substring.UTF8View> {
        .init()
    }
}

struct FromSubstringToUTF8<P: Parser>: Parser where P.Input == Substring.UTF8View {
    typealias Input = Substring
    
    let parser: P
    
    init(@ParserBuilder _ build: () -> P) { self.parser = build() }
}

struct IntParser<Input: Collection>: Parser where Input.SubSequence == Input, Input.Element == UTF8.CodeUnit {
    public init() { }
}

//MARK: ParserBuilder
struct Parse<Parsers: Parser>: Parser {
    typealias Input = Parsers.Input

    let parsers: Parsers
        
    init(@ParserBuilder with build: () -> Parsers) { self.parsers = build() }
}

@resultBuilder
struct ParserBuilder {
    public static func buildPartialBlock<P: Parser>(first: P) -> P { first }

    public static func buildPartialBlock<P0, P1>(accumulated: P0, next: P1) -> SkipFirst<P0, P1> {
        .init(p0: accumulated, p1: next)
    }
}

struct SkipFirst<P0: Parser, P1: Parser>: Parser where P0.Input == P1.Input {
    typealias Input = P0.Input

    let p0: P0
    let p1: P1
}

//MARK: main
let first = ParserBuilder.buildPartialBlock(first: ",")
let second = ParserBuilder.buildPartialBlock(accumulated: first, next: Int.parser())

let parser = Parse {
    ","
    Int.parser() // Ambiguous use of 'parser(of:)'
}

Expected behavior
This compiles for toolchain 2023-01-02 but breaks from 2023-01-07.
Expected to compile and choose the correct overload (in this case static func parser(of inputType: Substring.Type = Substring.self))

Since the first parser passed to the resultBuilder closure is of type String therefore the Parser associated type Input is of type Substring. Therefore the compiler should be able to infer that the parser returned by Int.parser() should have an Input of Substring as well.

Calling the individual partialBuildBlock functions does compile
works:

let first = ParserBuilder.buildPartialBlock(first: ",")
let second = ParserBuilder.buildPartialBlock(accumulated: first, next: Int.parser())

fails:

let parser = Parse {
    ","
    Int.parser() // Ambiguous use of 'parser(of:)'
}

Environment

• Swift compiler version info Swift Development Snapshot 2023-01-09
• Xcode version info Xcode 13.4.1 Build version 13F100
• Deployment target: M1 running macOS 12.5

[JaapWijnen]

Ran using the 2023-01-06 snapshot as well and that fails to compile too.

[xedin]

@JaapWijnen We have changed implementation to be more strict about how the inference works (aligned with https://github.com/apple/swift-evolution/blob/main/proposals/0348-buildpartialblock.md) and as per proposal result builder is a source transform that works this way:

let parser = Parse {
    let __builder0 = ","
    let __builder1 = Int.parser()

    let __builder2 = ParserBuilder.buildPartialBlock(first: __builder0)
    let __builder3 = ParserBuilder.buildPartialBlock(accumulated: __builder2, next: __builder1)
    return __builder3
}

which means that buildPartialBlock cannot in any way affect type-checking behavior of Int.parser().

[xedin]

The fix here would be to use static func buildExpression<T: Parser>(_ expression: T) -> T { expression }

[JaapWijnen]

@xedin
Hm I'm not sure I 100% follow. In the process of creating a reproducer I might have minimised my example a bit too much to convey what I'm actually trying to do. Let me know if your answer still applies after my explanation in that case I'm missing how I would have to implement your suggested fix.
What is actually happening in my use case is that on the Parser protocol there's a function that takes an inout input, produces an output and in the process modifies that input. The modified input is then passed to the next parser (In this case the Int parser). Therefore there's this dependency that both parsers have the same Input associatedtype. This restriction in this example is implemented by the type constraints on the SkipFirst parser.
The first parser is a string and it's defined to have an Input of Substring therefore SkipFirst<String, X> is required to have an Input of Substring which in turn requires X (in this case an IntParser) would be required to have Substring as input.

To describe, the full call hierarchy would be as follows: (This writing might be obvious and/or I'm not sure what's the best way of communicating this is) I'll add an updated version of my code below as well.)

I'd expect the Parse { } call to return a parser of type:
Parse<SkipFirst<String, FromSubstringToUTF8<IntParser<Substring.UTF8View>>>>
we can call parse(&input) on that which just passes it on to SkipFirst since that contains a single parser
This in turn will call two parsers

• first p0.parse(&input) this runs removes the "," input and returns Void
• second p1.parse(&input) // FromSubstringToUTF8<IntParser<Substring.UTF8View>>

this second call in turn calls a parser that wraps a parser of a different input. Since the IntParser does not work for an input of SubString as it's requiring Input: Collection where where Input.SubSequence == Input, Input.Element == UTF8.CodeUnit
So this parser, FromSubstringToUTF8, transforms the input, calls parse(&transformedInput), modifying it and then transforms the modified input back to the original Input type and overwrites the input variable.
Finally propagating the returned value of the IntParser to the FromSubstringToUTF8 to the SkipFirst and finally returning the value.

I really hope this is helpful. Let me know if there's information missing/unclear or how I can help in any other way!

code:

struct ParsingError: Error { }

//MARK: Parsers
@rethrows public protocol Parser<Input, Output> {
    associatedtype Input
    associatedtype Output
    
    func parse(input: inout Input) throws -> Output
}

extension String: Parser {
    public typealias Input = Substring
    
    public func parse(input: inout Substring) throws {
        guard input.starts(with: self) else {
          throw ParsingError()
        }
        input.removeFirst(self.count)
    }
}

extension Int {
    static func parser(
        of inputType: Substring.Type = Substring.self
    ) -> FromSubstringToUTF8<IntParser<Substring.UTF8View>> {
        FromSubstringToUTF8 { IntParser<Substring.UTF8View>() }
    }

    static func parser(
        of inputType: Substring.UTF8View.Type = Substring.UTF8View.self
    ) -> IntParser<Substring.UTF8View> {
        .init()
    }
}

struct FromSubstringToUTF8<P: Parser>: Parser where P.Input == Substring.UTF8View {
    typealias Input = Substring
    
    let parser: P
    
    init(@ParserBuilder _ build: () -> P) { self.parser = build() }
    
    func parse(input: inout Substring) throws -> P.Output {
        var transformedInput = input.utf8
        let result = try parser.parse(input: &transformedInput)
        input = Substring(transformedInput)
        return result
    }
}

struct IntParser<Input: Collection>: Parser where Input.SubSequence == Input, Input.Element == UTF8.CodeUnit {
    public init() { }
    
    func parse(input: inout Input) throws -> Int {
        // some int parsing logic
        return 4
    }
}

//MARK: ParserBuilder
struct Parse<Parsers: Parser>: Parser {
    let parsers: Parsers
        
    init(@ParserBuilder with build: () -> Parsers) { self.parsers = build() }
    
    func parse(input: inout Parsers.Input) throws -> Parsers.Output {
        try parsers.parse(input: &input)
    }
}

@resultBuilder
struct ParserBuilder {
    public static func buildPartialBlock<P: Parser>(first: P) -> P { first }

    public static func buildPartialBlock<P0, P1>(accumulated: P0, next: P1) -> SkipFirst<P0, P1> {
        .init(p0: accumulated, p1: next)
    }
}

struct SkipFirst<P0: Parser, P1: Parser>: Parser where P0.Input == P1.Input {
    let p0: P0
    let p1: P1
    
    func parse(input: inout P0.Input) throws -> P1.Output {
        let _ = try p0.parse(input: &input)
        return try p1.parse(input: &input)
    }
}

//MARK: main
let first = ParserBuilder.buildPartialBlock(first: ",")
let second = ParserBuilder.buildPartialBlock(accumulated: first, next: Int.parser())

let parser = Parse {
    ","
    Int.parser() // Ambiguous use of 'parser(of:)'
}

var input = ",4"[...]
let result = try parser.parse(input: &input)
print(result) // 4

[xedin]

I understand what you mean, this kind of workflow is not what is going to be supported by result builder transform implementation going forward. The result builder transform semantics are such that each element in the body is type-checked independently from others and the resulting value is then passed to a final buildBlock or a series of buildPartialBlock calls and returned just like I outlined in my example, the old implementation failed to enforce the "solved independently" bit which caused all sorts of diagnostics and performance issues.

In your example there are two overloads of parser(of:) method, both have argument that accepts a default value which means that the type-checker won't be able to disambiguate between them without buildExpression or buildPartialBlock providing more context (via generic requirements) just like if you wrote _ = Int.parser() without using result builders.

[JaapWijnen]

@xedin So does this mean that code previously relying on this feature will fail to compile in a future release?
I've seen multiple uses of this in libraries that use resultBuilders to create sort of pipelines which might be an easier example than my above parser example.

// a pipeline has an input and output
let pipeline = Pipeline {
  Pipeline1() // input: A, output: B
  Pipeline2() // input: B, output: C
  Pipeline3() // input: C, output: D
}

These types Pipeline1, 2 and 3 are then no longer able to be defined using generics and type restrictions? Is that correct?
Or is there a fix for my example that I'm missing at the moment?

[xedin]

It’s not about generics or type restrictions, the problem is that implementation did not adhere to the proposed semantics and allowed invalid code to type-check, which would not longer be the same. There are ways to change the result builder itself to archive portion of what was allowed before but cross-element inference would not be supported.

[xedin]

Just to clarify you can still use buildParticalBlock to produce a chain you described A -> B -> C -> D but it would not operate on the original elements, the builder transform in your example is going to be:

var __builder0 = Pipeline1()
var __builder1 = Pipeline2() 
var __builder2 = Pipeline3()

var r0 = Pipeline.buildPartialBlock(first: __builder0)
var r1 = Pipeline.buildPartialBlock(accumulated: r0, next: __builder1)
var r2 = Pipeline.buildPartialBlock(accumulated: r1, next: __builder2)

return r2

not:

var r0 = Pipeline.buildPartialBlock(first: Pipeline1())
var r1 = Pipeline.buildPartialBlock(accumulated: r0, next: Pipeline2())
var r2 = Pipeline.buildPartialBlock(accumulated: r1, next: Pipeline3())

return r2

because that violates the code principle behind result builders - type-checking of Pipeline{1, 2, 3} initializers would be affected by buildPartialBlock.

If either Pipeline1, Pipeline2 or Pipeline3 initializers are ambiguous all you can do is to use buildExpression to provide additional context.

This is exactly how the transform is described in the proposal that I've mentioned.

[JaapWijnen]

Aha that is very helpful! What I then finally perhaps fail to understand is how to use buildExpression to add context could you elaborate a little bit on that?

[xedin]

Sure! static func buildExpression when declared is going to be called for every element, back to your previous example:

var __builder0 = Pipeline.buildExpression(Pipeline1())
var __builder1 = Pipeline.buildExpression(Pipeline2())
var __builder2 = Pipeline.buildExpression(Pipeline3())

var r0 = Pipeline.buildPartialBlock(first: __builder0)
var r1 = Pipeline.buildPartialBlock(accumulated: r0, next: __builder1)
var r2 = Pipeline.buildPartialBlock(accumulated: r1, next: __builder2)

return r2

So you could declare that method in Pipeline to have any kind of generic parameters and return type, for example:

static func buildExpression<T: SomeProtoocol>(_ expression: T) -> T { expression }

This would make sure that Pipeline{1, 2, 3} all conform to SomeProtocol.

[JaapWijnen]

Got it! Thanks @xedin. One final question in that case. Is there then a possibility to also restrict associated types of that protocol? As in I'd like for all types supplied to the result builder that A they conform to SomeProtocol and B that their associated types SomeType (contained in SomeProtocol) are equal? Or is that not possible?

I'm hoping to fully understand the problem in order to find a fix for this dependency we currently rely on, swift-parsing, is able to compile again on the newer toolchain.

[xedin]

Yes, you can place whatever generic requirements are necessary i.e. <T: SomeProtocol>(...) where T.SomeType == ..., T.SomeOtherMember : OtherProtocol etc.

[JaapWijnen]

Hmm I don't fully follow. I can't make the requirement for the following example:

protocol: SomeProtocol {
  associatedtype Input
  associatedtype Output
}

struct P1<Input>: SomeProtocol {
  typealias Output = Int
}
struct P2<Input>: SomeProtocol {
  typealias Output = String
}

//When using these in a result builder: 
let object = Builder {
  P1()
  P2()
}

Can I force the Input associated type to be the same for all entries given to the builder? I don't see how to do that with restrictions on buildExpression that seems to me to only put restrictions on the individual entries is that correct?