[GSoC 2021] Tracking for typechecker’s type inference

moatom · 2021-03-18T04:12:41.460Z

Hello! My name is Tomoaki Kobayashi and I am an undergraduate student in Japan. I am interested in the project and started to read the related codes like TypeCheckConstraints, ConstraintSystem, and CSSolver a little bit.

@hborla @xedin
Do you have a typical example where a confusing type is inferred?
If we also consider type errors in that case, one of the cases which I guess is the mistaken use of foldr as foldl’s interface:

extension Array {
    func foldl<A>(f: ((A, Element) -> A), z:A) -> A {
        var z = z
        for x in self {
            z = f(z,x)
        }
        return z
    }

    func foldr<A>(f: ((Element, A) -> A), z:A) -> A {
        var z = z
        for x in self.reversed() {
            z = f(x,z)
        }
        return z
    }
}
let a = [1,2,3]
let b = [4,5,6]
print(a.foldr(f:{x,y in [y] + x}, z:b))
//                      ^    error: cannot convert value of type '[Any]' to expected argument type 'Int'

Now, my idea is to allow users to add an annotation to an expression of which they want to trace its typing like a.foldr(f:{(x, y:@trace-type) in [y] + x}, z:b). Then, if we are no need to handle type errors, what the tool should do there is really similar to what swift -frontend -typecheck -debug-constraints do: just displays only the actually adopted solution for the expression by omitting the dump of failed attempts of disjunction choices, bindings and so on in the above debugging command.

xedin · 2021-03-19T05:35:45.741Z

Hi, Tomoaki! Welcome to the project! I think confusing type in this context could be anything i.e. overload choice selected in a complex expression or type in a position that requires type-checker to use inference. That also includes error scenarios where developer expected one type but type inference selected a different one just like in your example. I think we are looking to make -debug-constraints output more user friendly for starters and then improve on that. Recently @Jumhyn added a PlaceholderType, it could be used to improve experience and suggest possible types e.g. a.foldr(f:{(x, y:_) in [y] + x}, z:b).

moatom · 2021-03-20T02:07:42.642Z

Thx!

PlaceholderType

https://github.com/apple/swift/pull/35589
Placeholder types
Partial type annotations

I confirmed the current situation. We need to touch the parser at first!

Jumhyn · 2021-03-20T02:27:17.057Z

FWIW, the parser changes were originally part of that PR and were reverted to ship the refactor without any user-facing change to the language. If you want to explore and experiment, the necessary changes for parsing placeholder types as ‘_’ should just be reverting this commit.

moatom · 2021-03-20T03:47:32.507Z

Hi @Jumhyn!

were reverted to ship the refactor

Oh, I really appreciate your advice! Now I am considering to explore the related codes and start to write the proposal.

moatom · 2021-03-20T06:37:08.748Z

I reverted the commit and faced the same types of many errors when compiling Swift:

.../swift/stdlib/public/core/Array.swift:371:5: error: cannot assign to immutable expression of type '_.Type'
    _ = _checkSubscript(index, wasNativeTypeChecked: true)
    ^
.../swift/stdlib/public/core/Array.swift:371:9: error: cannot assign value of type '_DependenceToken' to type '_.Type'
    _ = _checkSubscript(index, wasNativeTypeChecked: true)
        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
.../swift/stdlib/public/core/ArraySlice.swift:952:5: error: cannot assign to immutable expression of type '_.Type'
    _ = _buffer.beginCOWMutation()
    ^

Do you know how to avoid it?

Jumhyn · 2021-03-20T10:39:55.286Z

So, I’m not certain what the precise issue is, but as you can guess from the lines that are raising the errors it looks like we’re incorrectly treating a discard assignment expression as a placeholder type.

There’s code that tries to mark the “valid” discard assignment expressions (i.e., those that appear immediately on the left-hand side of an assignment), and when that PR was merged there were changes that made the system work with placeholder types. It looks like some changes since my have caused trouble with the old scheme, though.

Give this commit and this commit a peek for an idea of how I originally addressed the issue—hopefully it will only require some small changes to get it working again.

Jumhyn · 2021-03-31T13:56:44.185Z

Hey @moatom not sure if you've made progress on your own here, but I had a chance to look into this and the following diff (in addition to reverting the commit mentioned above) should fix things enough to get the stdlib compiling. There will be some errors in the tests since parsing _ as a type results in different error messages in some cases, but valid code should behave exactly the same!

diff --git a/lib/Sema/PreCheckExpr.cpp b/lib/Sema/PreCheckExpr.cpp
index ccf2a0089ad..1aa984ccd67 100644
--- a/lib/Sema/PreCheckExpr.cpp
+++ b/lib/Sema/PreCheckExpr.cpp
@@ -1523,11 +1523,17 @@ TypeExpr *PreCheckExpression::simplifyTypeExpr(Expr *E) {
     return simplifyNestedTypeExpr(UDE);
   }
 
-  // Fold '_' into a placeholder type.
+  // Fold '_' into a placeholder type if it hasn't been marked as a "correct"
+  // discard assignment expr (on the LHS of an assignment). If we're inside a
+  // SequenceExpr, skip this step since we might have a correct
+  // DiscardAssignmentExpr that hasn't been marked as correct yet. The whole
+  // tree will be rechecked once SequenceExpr folding completes, anyway.
   if (auto *DAE = dyn_cast<DiscardAssignmentExpr>(E)) {
-    auto *placeholderRepr =
-        new (getASTContext()) PlaceholderTypeRepr(DAE->getLoc());
-    return new (getASTContext()) TypeExpr(placeholderRepr);
+    if (!CorrectDiscardAssignmentExprs.count(DAE) && SequenceExprDepth == 0) {
+      auto *placeholderRepr =
+          new (getASTContext()) PlaceholderTypeRepr(DAE->getLoc());
+      return new (getASTContext()) TypeExpr(placeholderRepr);
+    }
   }
 
   // Fold T? into an optional type when T is a TypeExpr.

moatom · 2021-04-01T01:09:43.228Z

the following diff (in addition to reverting the commit mentioned above) should fix things enough to get the stdlib compiling.

Yes, thanks!
However, PlaceholderType doesn't work yet due to the allocation's failure at swift::PlaceholderType::get.

moatom · 2021-04-01T01:17:48.625Z

@hborla @xedin
If you are available, would you give feedback to my proposal? I've already shared it from the dashboard.

Jumhyn · 2021-04-04T21:13:30.274Z

Hey @moatom, I've tracked down the issue causing the crash in PlaceholderType::get, it should be fixed by this commit (not yet merged and probably won't be for a while, but feel free to cherry-pick if it helps you explore).

moatom · 2021-04-05T06:24:12.869Z

I saw your post (C++ lambda captures, references, and lifetimes question)!
I didn't reach that conclusion because I debugged the arena allocation itself😅
Thank you so much.

xedin · 2021-04-12T17:05:34.655Z

@moatom I have looked at your proposal (sorry it took me some time to do that). I think everything looks reasonable, one note - besides using PlaceholderType you might also think about how member references could be handled e.g. for expressions like test(.a.b) - it's interesting to know what type has been chosen for .a and for .b and for test. Also please note there are only a couple of days left, so please submit a final version of the proposal and we'll go from there.