Matt Diephouse

Entry 0: SR-7380, Ambiguous KeyPath

13 June 2018

My first bug fix! Yay!

Here’s the bug I fixed (with a lot of help):

7380.swift:1:16: error: type of expression is ambiguous without more context
"str"[keyPath: \.count]
               ^~~~~~~

That seems obviously broken. The value is a String literal. They KeyPath should obviously be String.count. So why doesn’t this work?

How do I debug this thing?

My first step was to figure out exactly how to debug the issue.

I started by reproducing the issue in the Xcode debugger. Since I’m so familiar with Xcode, this is where I wanted to start. Luckily, Swift supports building with Xcode: you just need to pass --xcode to the build script.

Having done that, I:

  1. Opened the generated Xcode project file from inside the build directory
  2. Manually created a scheme for the swift product
  3. Edited the scheme to:
    1. Change the Run > Options > Working Directory to the directory where I’m keeping my buggy .swift files.
    2. Edit the Run > Arguments to pass the file I’m trying to compile. I like to keep things simple by reusing the bug number. So I’m working with 7380.swift here.
  4. Ran the code and saw the output in the debugger.

Now I could set breakpoints in Xcode and hit them in LLDB.

I had to poke around a bit to set my first breakpoint. I knew that I'd likely be dealing with the type checker, and I knew that type checking was done in swiftSema, the library used for Swift’s semantic analysis.

I eventually stumbled on ConstraintSystem.solve, which seemed like a good place to start.

But I also had to figure out how to print anything meaningful to the debug console. I’ve been pretty spoiled in Objective-C and Swift, where you can override description and use po in the debugger to print out helpful descriptions of your objects.

In C++, I knew that you can use p to print out the address of an object and p *object to print out its memory contents, but that’s not a super helpful description.

While visiting a WWDC lab, I discovered that, within the constraint system at least, most objects have a dump() method you can call e object.dump() to print out a friendly description. Now I could debug.

Extra Logging

Swift includes documentation about debugging the compiler. It includes some helpful flags you can pass (inside the scheme’s Run > Arguments or on the command-line) to get some helpful diagnostics.

Since I knew that I’d be debugging the type-checker, I added -Xfrontend -debug-constraints. (swiftc is the actual compiler, which takes the -debug-constraints flag; -Xfrontend tells swift to pass the next flag through to swiftc.)

That yields a lot of helpful output that shows the type-checker’s search for a solution. But—as I found out later—it doesn’t show you everything. Stepping through with the debugger and dumping this is still very helpful.

Dumping the AST (Abstract Syntax Tree) is also very helpful.

What is type checking?

When you write a Swift program, the compiler puts it through a number of stages that transform some input into some output.

To start with, you have just a file. That’s what we typically work with day-to-day. It’s effectively a big string. The lexer lexes the input stream into a stream of tokens: it transforms if foo { blah() } into something like [Token](.if, .identifier(“foo”), .openBrace, .identifier(“blah”), .leftParen, .rightParen, .closeBrace).

The parser transforms a stream of tokens into an abstract syntax tree (AST). This adds semantics to the tokens, creating something with meaning. That gives something like [Expression](.if(.variable(“foo”), call("blah", []), nil).

But not all valid syntactically-valid Swift programs are semantically valid. e.g. ””[keyPath: \Int.description] is valid syntax, but has invalid semantics. In this example, the types don’t line up: "" is a String, but the KeyPath is on Int.

The type-checker (part of the Sema or Semantic Analysis library in Swift) takes an AST and (1) infers missing types and (2) validates all the types.

How does type checking work?

Type-checking uses a constraint solver to solve a system of unknowns. I’ve written about how constraint solvers work generally and open sourced Logician, a Swift constraint solver library. Those are probably worth checking out if this sounds interesting.

In case of the Swift type-checker, a number of type variables are created for unknown types. Then constraints are added between the types and type variables. Best guesses are made. Swift takes valid solutions, scores them, and chooses one. There’s a lot more detail in the Swift documentation.

Code-wise, type-checking is done expression-by-expression. The constraint system walks the AST with an ASTWalker, generating constraints for each node in the AST of that expression. Once the constraints are generated, the problem can be solved.

Solving works by simplifying constraints and trying out different possible values. If a string literal is used without an explicit type, e.g., then it’ll be constrained to types that are ExpressibleByStringLiteral. The type-checker might start by checking whether all the constraints are met with an actual String.

Once the expression has been type-checked, the AST is rewritten to add the type annotations.

The interesting bits are in a few files:

  • CSGen.cpp: Generates the constraints from the AST
  • CSSolver.cpp: Does the actual solving
  • CSSimplify.cpp: Breaks down constraints once more information is known
  • CSDiag.cpp: Diagnoses type-checking failure, producing warnings and errors
  • CSApply.cpp: Rewrites the AST by applying the solution
  • ConstraintSystem.cpp: The core object that tracks constraints and assignments

If you dump the ConstraintSystem, you’ll see something like this:

Score: 0 0 0 0 0 0 0 0 0 0 0
Type Variables:
  $T0 as String @ locator@0x119800400 [StringLiteral@7380.swift:1:1]
  $T1 subtype_of_existential bindings={} @ locator@0x119800490 [KeyPath@7380.swift:1:16]
  $T2 [lvalue allowed] fully_bound subtype_of_existential involves_type_vars bindings={} @ locator@0x119800490 [KeyPath@7380.swift:1:16]
  $T3 subtype_of_existential involves_type_vars bindings={} @ locator@0x119800490 [KeyPath@7380.swift:1:16]
  $T4 subtype_of_existential involves_type_vars bindings={} @ locator@0x119800490 [KeyPath@7380.swift:1:16]
  $T5 subtype_of_existential involves_type_vars bindings={} @ locator@0x1198006c0 [Subscript@7380.swift:1:6 -> subscript index]
  $T6 [lvalue allowed] subtype_of_existential bindings={} @ locator@0x1198006e0 [Subscript@7380.swift:1:6 -> subscript result]
  $T7 subtype_of_existential bindings={} @ locator@0x119800cf8 [Subscript@7380.swift:1:6 -> subscript member -> function argument]
  $T8 [lvalue allowed] subtype_of_existential involves_type_vars bindings={} @ locator@0x119800cf8 [Subscript@7380.swift:1:6 -> subscript member -> function argument]
  $T9 subtype_of_existential involves_type_vars bindings={} @ locator@0x119800cf8 [Subscript@7380.swift:1:6 -> subscript member -> function argument]

Active Constraints:

Inactive Constraints:
  @lvalue $T1[.count: value] == $T2 [[locator@0x119800510 [KeyPath@7380.swift:1:16 -> key path component #0]]];
  $T2 equal $T3 [[locator@0x119800490 [KeyPath@7380.swift:1:16]]];
  $T4 key path from $T1 -> $T3 [[locator@0x119800490 [KeyPath@7380.swift:1:16]]];
  (keyPath: $T4) arg tuple conv $T5 [[locator@0x1198006c0 [Subscript@7380.swift:1:6 -> subscript index]]];
  $T8 equal $T9 [[locator@0x119800750 [Subscript@7380.swift:1:6 -> subscript member]]];

Examining this is the best way to debug type checking.

What caused the bug?

Back to the bug I wanted to solve:

7380.swift:1:16: error: type of expression is ambiguous without more context
"str"[keyPath: \.count]
               ^~~~~~~

Since this is clearly not ambiguous, we must know something that the type-checker doesn’t.

The output of -debug-constraints starts with a dump of the AST:

(subscript_expr type='$T6' location=7380.swift:1:6 range=[7380.swift:1:1 - line:1:23] arg_labels=keyPath:
  (string_literal_expr type='$T0' location=7380.swift:1:1 range=[7380.swift:1:1 - line:1:1] encoding=utf8 value="str" builtin_initializer=**NULL** initializer=**NULL**)
  (tuple_expr type='(keyPath: $T4)' location=7380.swift:1:6 range=[7380.swift:1:6 - line:1:23] names=keyPath
    (keypath_expr type='$T4' location=7380.swift:1:16 range=[7380.swift:1:16 - line:1:18]
      (component=unresolved_property count type=<null>)
      <<null>>
      (unresolved_dot_expr type='<null>' field 'count' function_ref=unapplied
        (key_path_dot_expr implicit type='<null>')))))

There’s a subscript on a string literal that has an arguments tuple with a keyPath: label and a KeyPath expression inside with an unresolved dot expression. (Unresolved meaning that we don’t know what type it’s on.)

Next, -debug-constraints prints the initial ConstraintSystem:

Score: 0 0 0 0 0 0 0 0 0 0 0
Type Variables:
  $T0 literal=3 bindings={(subtypes of) (default from ExpressibleByStringLiteral) String} @ locator@0x7fa6da01aa00 [StringLiteral@7380.swift:1:1]
  $T1 subtype_of_existential bindings={} @ locator@0x7fa6da01aa90 [KeyPath@7380.swift:1:16]
  $T2 [lvalue allowed] fully_bound subtype_of_existential involves_type_vars bindings={} @ locator@0x7fa6da01aa90 [KeyPath@7380.swift:1:16]
  $T3 subtype_of_existential involves_type_vars bindings={} @ locator@0x7fa6da01aa90 [KeyPath@7380.swift:1:16]
  $T4 subtype_of_existential involves_type_vars bindings={} @ locator@0x7fa6da01aa90 [KeyPath@7380.swift:1:16]
  $T5 fully_bound subtype_of_existential involves_type_vars bindings={} @ locator@0x7fa6da01acc0 [Subscript@7380.swift:1:6 -> subscript index]
  $T6 [lvalue allowed] fully_bound subtype_of_existential involves_type_vars bindings={} @ locator@0x7fa6da01ace0 [Subscript@7380.swift:1:6 -> subscript result]

Active Constraints:

Inactive Constraints:
  $T0 literal conforms to ExpressibleByStringLiteral [[locator@0x7fa6da01aa00 [StringLiteral@7380.swift:1:1]]];
  @lvalue $T1[.count: value] == $T2 [[locator@0x7fa6da01ab10 [KeyPath@7380.swift:1:16 -> key path component #0]]];
  $T2 equal $T3 [[locator@0x7fa6da01aa90 [KeyPath@7380.swift:1:16]]];
  $T4 key path from $T1 -> $T3 [[locator@0x7fa6da01aa90 [KeyPath@7380.swift:1:16]]];
  $T0[.subscript: value] == ($T5) -> $T6 [[locator@0x7fa6da01ad50 [Subscript@7380.swift:1:6 -> subscript member]]];
  (keyPath: $T4) arg tuple conv $T5 [[locator@0x7fa6da01acc0 [Subscript@7380.swift:1:6 -> subscript index]]];

There are a bunch of type variables (unknown types). It’s worth trying to work through them on your own.

From here, we can see why Swift thinks the type of the KeyPath is ambiguous: $T0 (the type of the string literal) has no real connection to $T1 (the root type of the KeyPath). But note that this is just the initial constraints—additional constraints could be provided later that provide this connection.

At this point, Swift hasn’t determined that the subscript is a key path application—it could be any subscript. Subscripts can be overloaded, so an OverloadChoice will be created to try the different choices. This is a disjunction—a spot where Swift can try different solutions.

The rest of -debug-constraints shows Swift trying a few different subscript overloads and then trying to diagnose the type failure. You can set a breakpoint inside the overload choice, step through, and dump the ConstraintSystem to see its logic.

What was the fix?

Well I had quite a bit of help with this in WWDC labs at and try! Swift San Jose. 😅

But it eventually became clear that an additional constraint was needed to tie the type the subscript was operating on to the root type of the KeyPath. But (1) where should that happen and (2) how do you do it?

The right place seems to be inside ConstraintSystem::addKeyPathApplicationConstraint. This is called from within the subscript’s OverloadChoice, when the type checker is trying to solve it as a KeyPath application. That’s the outermost code (excluding the code inside the overload choice) that knows that we’re trying to use a KeyPath application.

That method is called with a ConstraintLocatorBuilder, which can build a ConstraintLocator. A ConstraintLocator locates the origin of a constraint within an expression. The builder, well, can build a locator. In this case, we didn’t need to build an actual locator, we just need to ask it for its parts.

That yields the origin of the key path application constraint, which in this case will be a subscript expression. By looking inside there, and conditionally casting the expressions that we find, we can look for nodes that match the AST we’re interested in.

If this is the case we’re interested in, we can use the KeyPath expression (representing \.count) to find the KeyPath constraint. Once we have that, it’s easy to add a new constraint between the type the subscript operates on and the root type of the KeyPath. With that additional information, Swift can resolve \.count correctly! Bug fixed!