Skip to content

WIP: Implement first parts of Inko's self-hosting compiler

Yorick Peterse requested to merge std-compiler into master

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

Merge request reports