WIP: Implement first parts of Inko's self-hosting compiler
This implements the first bits and pieces of Inko's self-hosting compiler. This includes types for configuring the compiler, parsing modules and their dependencies, type-checking them, and some language changes such as support for pattern matching.
Originally the goal of this MR was to implement all of the self-hosting compiler, and merge when completed. Given this will likely take quite some time, and I want to release the existing changes (most notably pattern matching), I changed the focus of this MR on just type-checking. Once that works well enough, we'll merge this MR and implement the rest of the compiler in separate MRs.
old TODO
A rough TODO/outline of the compiler steps to implement:
1. [x] Given the name of a file to compile, determine the module name
* This is the path of the module, relative to the search directories
* Filesystem separators are replaced with `::`
* Lowercased
* `runtime/src/std/compiler/parser` becomes `std::compiler::parser`
1. [x] Create a compiler module object
1. [x] Parse the source into an AST
1. [x] Desugar the AST.
* [x] Add new/init to objects
* [x] Desugar `try!` properly
1. [x] Pass for inserting implicit imports
1. [x] Pass for hoisting imports to the start of a module
1. [x] Process all dependencies first, in parallel.
* Continue when all succeed
* Abort if one or more fail
* Detect circular imports
1. [ ] Type inference and type checking
* Error for symbols already imported
* Types start off as Unknown and are inferred into Any or a concrete type
* Never (Void before) indicates something never returns or throws
* Disallow (when type checking) arguments of required methods to have default values
* Error when method argument types are not specified
* Error when closure arguments can't be inferred
1. [ ] Perform AST optimisations
* [ ] Turn `Boolean.if` into `_INKOC.if({ ... }, { ... })`
* [ ] Turn `Boolean.if_true` into `_INKOC.if({ ... }, { Nil })`
* [ ] Turn `Boolean.if_false` into `_INKOC.if({ Nil }, { ... })`
* [ ] Turn `Block.loop` into `_INKOC.while({ True }, { ... })`
* [ ] Turn `Block.while_true` into `_INKOC.while({ ... }, { ... })`
* [ ] Turn `Block.while_false` into `_INKOC.while({ ... == False }, { ... })`
* [ ] Replace keyword arguments, pad missing arguments with `_INKOC.undefined`
1. [ ] Convert AST into MIR
* Register based CFG
* No SSA for now
* Uses basic blocks
* Rename locals defined in `_INKOC.if` and `_INKOC.while`
* Make sure to keep track of the original names for errors
* This is needed to "flatten" the closure
* [ ] Convert `_INKOC.if` into a set of gotos
* [ ] Convert `_INKOC.while` into a goto
1. [ ] Inlining
* [ ] Inline methods that just return an attribute
* This will optimise getter methods
* [ ] Inline methods that just set an attribute
* This will optimise setter methods
* [ ] Inline methods that just contain a single `_INKOC.X` instruction
* This removes the overhead of some core methods such as == and equal?
* This automatically optimises Integer.+, Float./, etc.
* More inlining can be added in the future
1. [ ] Optimise MIR
* [ ] Constant propagation
* [ ] Constant folding
* [ ] Optimise arithmetic identities
* [ ] Strength reduction (`2 * X` -> `X + X`)
* [ ] Remove unused assignments (this probably requires SSA)
* [ ] Remove unreachable code
* [ ] Move literal loading out of loops
* [ ] Optimise `Nil.unknown_message` so the method doesn't get called, as doing so creates an unused array for the arguments
1. [ ] Make sure that `_INKOC.get_attribute(X, 'Y')` results in the compiler knowing the type of `X::Y`, but only if the attribute name is a string literal (not e.g. a variable).
1. [ ] Detect if all attributes are assigned when creating a new object, without assuming the initialiser method is always called `init`. See https://gitlab.com/inko-lang/inko/-/issues/195
1. [ ] Methods without a return type should have it inferred to Nil, and have a `return` inserted at the end. This should not mess up tail recursive methods, thus this probably can't be done prior to type checking.
Edited by Yorick Peterse