top-down type inference, implements rfc 149

[metagn]

refs https://github.com/nim-lang/RFCs/issues/149, closes https://github.com/nim-lang/RFCs/issues/36

Name copied from Haxe manual

Proof of concept for adding top-down type inference on top of the validating style inference used by fitNode. (I think this is called "bidirectional typing"). Each expression can opt-in to this and define their own behaviors.

• [x] assignments
• [x] let/var/const type annotations
• [x] blocks/statement lists
• [x] if/case/try branches
• [x] if/while conditions
• [x] set literal elements
• [x] array literal elements
• [x] seq literal elements (unfortunately requires @ to not be overloaded)
• [x] tuple elements
• [x] object constructors
• [x] table constructor
• [x] proc body inference based on return type
• [x] string literal (cstrings)
• [x] nil literal
• [x] generalized overload specification
• [x] surface level range types
• [ ] document
• lambda/do signature inference? https://forum.nim-lang.org/t/9191
• better refactor for expectedType?

notes

• fitNode already has errors, so new errors/enforcing expectedType are probably not needed
• type conversions are left alone. a new magic like infer(x: untyped, T: type): T is possible, but might be excessive
• performance should be considered
• keeping this as compatible as possible is best, but if needed, it can be made conditional by turning all expectedType = ... into expectedType = cond(...) where cond(...) is nil or the given argument based on the condition
• current incompatibilities:
  • a sequtils test breaks (AFAICT some kind of #14844 is unlocked so probably not my fault), sequtils is changed to make the test work

This would be most useful potentially for routine arguments, but I don't think it would be simple to do. I have thought of a couple ways:

1. Query all overloads, filter all the ones that fit the call (param count, named arguments etc), then get the common type of each argument, and use that for the expected types. The disadvantages with this are that varargs/untyped would completely disable some arguments, and generally these common types will not give too much information. This will also not be great for performance.
2. Gradually type arguments in a row (except untyped arguments) until only 1 overload remains. For example if there are overloads that are like (A, X, Y), (B, X, Y), (C, X, Y), you sem the first argument (not accounting for named arguments) and get A, then only the overload of (A, X, Y) remains, so you know to use X and Y for the remaining arguments. This has the advantage of working with method-style signatures much better. It might also be bad for performance.

I can't get started on these easily so they are out of scope for me.

[Araq]

Awesome and bounty-worthy!

[Varriount]

Just out of curiosity (I have practically no experience working with the compiler), why use an extra parameter over adding a new field to PContext?

[metagn]

If it could be refactored to that, I would do it, but I am not too confident about it. It would be really hard to keep track of (you would need to think about it for every sem call). For example sometimes you expect bool for if conditions then another type for their branches. Sometimes you are supposed to leave the type empty, like in statement lists until the last statement.

I guess also for now I want the behavior of having nil by default instead of propagating the type. For example if there was a expectType(typ): sem() wrapper, you would have to call expectType(nil): sem() to opt expressions out of it.

[metagn]

Forgot to comment this is ready for review, it just might be a little painful to do so.

[github-actions[bot]]

Thanks for your hard work on this PR! The lines below are statistics of the Nim compiler built from 0014b9c48e883d3c04995b9e83bb0f8468a16df6

Hint: mm: orc; threads: on; opt: speed; options: -d:release 163798 lines; 13.113s; 841.578MiB peakmem