How does compiler compile SwiftUI code?

Development Compiler
4

I guess there are three answers to this question, or maybe there are three separate questions.

Q1. Why did the compiler diagnose this error?

One of two things happened:

  1. If the expression references one or more overloaded names, we have to choose exactly one declaration from each overload set, in a way that's consistent with all other choices and the rest of the expression. This can take several attempts, so every time we choose an overload from an overload set, we increment a counter, which is reset to zero at the start of each expression. If the value of this counter exceeds one million, we diagnose an error.
  2. The expression checker uses a temporary memory allocation arena for scratch space while attempting different choices. This arena is reset for each expression. If the total size exceeds 512Mb, we diagnose an error.

(In the Swift 4 days, there was also a one minute wall-clock time limit. In 2017 it was increased to 10 minutes, and it should never be hit in practice because one of the other two limits should be hit first. On the main branch, it's gone entirely because reading the wall time was itself a pointless source of overhead.)

Q2. Why did my specific expression diagnose this error?

For any realistic concrete example, it's because "the solver isn't smart enough yet". If it could make some deduction earlier or attempt choices in a different order, it would be able to find a solution without having to consider so many choices. There's some on-going work to make it smarter ([ConstraintSystem] Return of the new disjunction favoring/selection algorithm by xedin · Pull Request #79461 · swiftlang/swift · GitHub). (Also there have been some smaller improvements recently on main as well, mostly to reduce the time spent consider each choice, so the solver explores the same search space faster.)

There are also known cases where an invalid expression produces this error, as you observed; this is because when generating diagnostics, we must attempt even more choices than we do otherwise (these are called "fixes"; for example, if a type doesn't conform to a protocol, we pretend that it does, and if that was the only problem, we diagnose the conformance failure, etc.)

Q3. Why do some expressions diagnose this error?

Because Swift type inference is NP-hard. Say you have a Boolean formula and you want to know if there is some set of input values that makes the formula evaluate to true:

func formula(x1: Bool, x2: Bool, x3: Bool) -> Bool {
  return (!x1 || x2 || x3) &&
         (!x1 || x2 || !x3) &&
         (!x2 || x3) &&
         (x1 || x2) &&
         (!x1 || !x2)
}

You can translate this into a type checking problem:

let fn = { x1, x2, x3 in
  (clause(not(x1), x2, x3),
   clause(not(x1), x2, not(x3)),
   clause(not(x2), x3, x3),
   clause(x1, x2, x2),
   clause(not(x1), not(x2), not(x2)))
}

// You just need a few types and overloads:
struct True {}
struct False {}

func not(_: True) -> False {}
func not(_: False) -> True {}

func clause(_: True, _: False, _: False) {}
func clause(_: False, _: True, _: False) {}
func clause(_: True, _: True, _: False) {}
func clause(_: False, _: False, _: True) {}
func clause(_: True, _: False, _: True) {}
func clause(_: False, _: True, _: True) {}
func clause(_: True, _: True, _: True) {}

Now, if our closure fn is well-typed, each one of its parameters x1, x2, and x3 will receive the type True or False, and these correspond to the input values that happen to make our original formula() return true.

Nobody has found a polynomial time algorithm that can determine if such an assignment exists for an arbitrary Boolean formula yet, which means that if you add enough variables and clauses to your formula, you might need to consider a very large number of choices before you can decide if the formula is satisfiable or not. So there will always be some expressions that cannot be solved in reasonable time. (But again, most of the "easy looking" expressions that produce this diagnostic are not truly intractable, and it's just a matter of implementation.)

20 Likes