[SR-15588] Generic/overload type-checking slowness

[stephencelis]

Previous ID	SR-15588
Radar	None
Original Reporter	@stephencelis
Type	Improvement

Additional Detail from JIRA

Votes	0
Component/s	Compiler
Labels	Improvement
Assignee	None
Priority	Medium

md5: 55b28a544364316a0bf385d9e2b129c2

Issue Description:

I wanted to contribute the following code that uses generics, overloads, closures, and String initializers to produce a relatively short expression take 10 seconds or so to compile:

protocol Parser {
  associatedtype Input
  associatedtype Output
  func parse(_ input: inout Input) -> Output?
}

struct Prefix<Input>: Parser
where
  Input: Collection,
  Input.SubSequence == Input
{
  let predicate: (Input.Element) -> Bool
  func parse(_ input: inout Input) -> Input? {
    let output = input.prefix(while: predicate)
    input.removeFirst(output.count)
    return output
  }
}

extension Prefix where Input == Substring {
  init(predicate: @escaping (Character) -> Bool) {
    self.predicate = predicate
  }
}

struct Map<Upstream, Output>: Parser
where
  Upstream: Parser
{
  let upstream: Upstream
  let transform: (Upstream.Output) -> Output
  func parse(_ input: inout Upstream.Input) -> Output? {
    self.upstream.parse(&input).map(transform)
  }
}

extension Parser {
  func map<NewOutput>(
    _ transform: @escaping (Output) -> NewOutput
  ) -> Map<Self, NewOutput> {
    .init(upstream: self, transform: transform)
  }
}

struct Zip<A, B>: Parser where A: Parser, B: Parser, A.Input == B.Input {
  let a: A
  let b: B

  init(_ a: A, _ b: B) {
    self.a = a
    self.b = b
  }

  func parse(_ input: inout A.Input) -> (A.Output, B.Output)? {
    let original = input
    guard
      let a = self.a.parse(&input),
      let b = self.b.parse(&input)
    else {
      input = original
      return nil
    }
    return (a, b)
  }
}

func f() {
  // Expression took 9680ms to type-check
  _ = Zip(Prefix { $0 != "-" }, Prefix { $0 != "-" })
    .map { (String($0), String($1)) }

  // Expression took 12457ms to type-check
  _ = Zip(
    Prefix { $0 != "-" }.map(String.init),
    Prefix { $0 != "-" }.map(String.init)
  )
}

There are tricks one can employ to improve the compilation time by a lot:

• Explicitly specify a generic (in the Prefix type, for example)

• Explicitly define the types in the map closure

• Use string interpolation instead of a string initializer

Hopefully, though, improvements can be made to the type checker to get things building a bit more quickly.