Best practices for fixing ordering effects in the Constraint System

I ran into SR-13216 the other day and have been investigating a fix recently. In terms of cause, it seems as though it basically comes down to the order in which we generate certain type variables.

Summary of issue and potential cause

The minimal reproducing I've been able to find is:

struct S {
    var x: String?
}

func foo(_: (inout S) -> Void) {}

func bar(_ kp: WritableKeyPath<S, String?>) {
    let value = ""
    foo { s in
        s[keyPath: kp] = value
        //return
    }
}

As written, this will emit a compiler error at the s[keyPath: kp] = value value line, complaining that the result of type String? should be unwrapped, which is clearly erroneous. Uncommenting the return resolves the issue.

From my investigation it appears that the issue comes down to whether the closure argument passed to foo is a single-expression closure or not. If so, then the s[keyPath: kp] = value line is solved as part of the entire call to foo. If not, then the call to foo is resolved first, and s[keyPath: kp] = value is solved as a separate expression.

In the case where the keyPath line is resolved separately, when we generate the constraints for the SubscriptExpr, the type of s has already been resolved to S, and member lookup generates the appropriate constraints for the keyPath subscript (namely, adding a potential binding for the argument to WritableKeyPath<S, String?>). Then, the constraint generation for the AssignExpr generates the potential bindings for the destination type based on value, resulting in potential bindings of (supertypes of) String. Since the keyPath argument type variable was generated first, we attempt the WritableKeyPath<S, String?> binding first, and the destination type is resolved to String.

On the other hand, if we're solving the single-expression closure as part of the call to foo, when we generate the constraints for the SubscriptExpr, the type of s hasn't been resolved yet and so member lookup can't look into S to find the keyPath subscript member. We then generate the constraints for the AssignExpr, which uses the (already resolved) type of value to set the potential bindings of the destination type of the AssignExpr to (supertypes of) String. Then, during simplification, the keyPath argument constraints and type variable are created with the potential binding to WritableKeyPath<S, String?>. Since the destination type variable was generated first, we attempt to bind it to String, which obviously fails since the keypath application produces a destination type of String?.

In short: when the closure body is a single expression, we attempt to bind the destination type variable for the AssignExpr to String before we attempt to bind the keyPath argument type variable to WritableKeyPath<S, String?>, resulting in the error. When the closure body is not a single expression, we attempt the WritableKeyPath<S, String?> binding before the destination type variable is bound to String, which ultimately finds a successful solution.

Can anyone provide advice about whether there's a 'standard' way to approach this sort of issue? It seems like any fix which wholesale changes the order in which certain resolutions happen in the type checker is off the table because of the potential side effects, but it also feels icky to just special-case this one situation—this doesn't appear to happen with normal subscript declarations, just keypath-based ones.

Would it be appropriate for enumerateDirectSupertypes to include the one-level-more-optional type (i.e., consider T? for a type T)? I think that would address this case, but I'm not clear if there's an existing reason for not considering T? as part of the binding step for "(supertypes of) T".

Or, if there's some completely different approach that would make sense here, I'm all ears...

I think this has already been fixed on master as I can't reproduce the error. I guess @LucianoPAlmeida fixed it in this PR: https://github.com/apple/swift/pull/32841

2 Likes

Nice! I was just a week or so behind master so didn't think this had been fixed, glad to see it was. Thank you @suyashsrijan.

No worries! In terms of fixing such problems in the future, I think @xedin or @hborla might have some advice.

3 Likes

Can anyone provide advice about whether there's a 'standard' way to approach this sort of issue?

There are definitely cases where it makes sense to delay work in the solver until something else happens first. I know it can feel icky to write special cases for certain language features, but you have to evaluate the semantics of those features to decide whether or not it warrants a special case.

For example, for single-expression closures, it doesn't make sense to even generate constraints for the closure body until the solver has a contextual type for the closure (or it decides that there is no contextual type available). Having that context can change the semantics of the code inside the body (e.g., is the closure a function builder?), which affects how constraints are generated in the body. (https://github.com/apple/swift/pull/28837)

If you look at the PR that Suyash linked for this issue, you'll see that the fix was to delay binding a key path application result type until the solver has the keypath type itself. Luciano's comment explains why this is important:

This ensures we try to bind the key path type first, which can allow us to discover additional bindings for the result type.

In both of these cases, work in the solver is delayed because the solver doesn't have enough information to continue (or it might have some, but not all of the necessary information to discover a certain type that will work). You'll see other places throughout CSSimplify that leave constraints unsolved before enough information is available. I think in cases like these, a good approach is to evaluate which information the solver needs in order to correctly solve a constraint, and delay solving until that information becomes available.

I know this is sort of vague advice, but I hope it helps!

5 Likes

Yeah that's super helpful, thank you @hborla!

1 Like
Terms of Service

Privacy Policy

Cookie Policy