programming/projects/muscript

repo
my UnrealScript compiler
part of the Stitchkit project, which aims to build a set of Hat in Time modding tools that are a joy to use
- the name “MuScript” is actually a reference to Mustache Girl
architecture
- MuScript uses a query-based architecture similar to rustc
  - the classic pass-based compiler architecture has the compiler drive itself by first parsing all files, then analyzing them, then emitting bytecode - in passes
  - a query-based architecture works by driving the compiler by asking it questions
    the most interesting question to us all being “do you know the bytecode of this package?”
    which then triggers another question “do you know the classes in this package?”
    which then triggers another question “do you know the contents (variables, functions, structs, enums, states, …) of those classes?”
    which then triggers another question “do you know all the variables in class ComfortZone?”
    which then triggers another question “do you know the ID of the type Int?”
    “yeah, it’s 4.”
    “there’s this variable HuggingQuota with ID 427.”
    which then triggers another question “do you know all the functions in class ComfortZone?”
    which then triggers another question “do you know the bytecode of function Hug?”
    which then triggers another question “do you know the ID of the class Person?”
    “yes indeed, this class exists and has ID 42.”
    which then triggers another question “do you know the bytecode of this function?”
    …you get the idea.
    “alright, here’s the bytecode for Hug.”
    “that’s all.”
ideas to try out
- I jot down various silly ideas for MuScript in the future here
- parallelization with an event loop
  - the thing with a pass-based architecture is that with enough locking, it may be easy to parallelize.
    I can imagine parallelization existing on many levels here.
    if you have a language like Zig where every line can be tokenized independently, you can spawn a task per line.
    you could analyze all the type declarations in parallel. though with dependencies it gets hairy.
    you could analyze the contents of classes in parallel.
    thing is, this stuff gets pretty hairy when you get to think about dependencies between all these different stages.
    hence why we haven’t seen very many compilers that would adopt this architecture; most of them just sort of do their thing on one thread, and expect to parallelize by spawning more processes of cc or rustc or what have you.
  - where with a pass-based architecture the problem is dependencies between independent stages you’re trying to parallelize, with a query-based architecture like MuScript’s it gets even harder, because the entire compiler is effectively a dependency _{_hell} machine.
    one query depends on 10 subqueries, which all depend on their own subqueries, and so on and so forth.
    but there’s technically nothing holding us back from executing certain queries in parallel.
    in fact, imagine if we executed all queries in parallel.
  - enter: the async event loop compiler
    there is a central event loop that distributes tasks to be done to multiple threads
    every query function is async
    meaning it suspends execution of the current function, writes back “need to compute the type ID of Person because that’s not yet available” into a concurrent set (very important that it’s a set) - let’s call this set the “TODO set”
    on the next iteration, the event loop spawns a task for each element of the TODO set, and the tasks compute all the questions asked
    because we’re using a set, the computation is never duplicated; remember that if an answer has already been memoized, it does not spawn a task and instead returns the answer immediately
    though this may be hard to do with Rust because, as far as I know, there is no way to suspend a function conditionally? (needs research.)
    once there are no more tasks in the queue, we’re done compiling
- parsing less
  - I measured the compiler’s performance yesterday and most time is actually spent on parsing, out of all things
    going along with the philosophy of be lazy, we should probably be parsing less things then
  - I don’t think we need to parse method bodies if we’re not emitting IR
    basically, out of this code: unrealscript function Hug(Hat_Player OtherPlayer) { PlayAnimation('Hugging'); // or something, idk UE3 } parse only this: unrealscript function Hug(Hat_Player OtherPlayer) { /* token blob: PlayAnimation ( 'Hugging' ) ; */ } omitting the entire method body and treating it as an opaque blob of tokens until we need to emit IR
  - I don’t think we need to parse the entire class if we only care about its superclass
    basically, out of this code: unrealscript class lqGoatBoy extends Hat_Player;
    
    defaultproperties { Model = SkeletalMesh’lqFluffyZone.SkGoatBoy’; // etc } only parse the following: class lqGoatBoy extends HatPlayer;
    
    /* parser stops here, rest of text is ignored until needed */ and then only parse the rest if any class items are requested
    real case: getting the superclasses of Hat_Player takes a really long time because it’s big (Hat_Player.uc itself is around 8000 lines of code, and it has many superclasses which are also pretty big)
ideas I tried out
- lexing first
  - something that MuScript did not use to do is have a separate tokenization stage
    this is because UnrealScript has some fairly idiosyncratic syntax which requires us to treat some things in braces {} as strings, such as cpptext
    cpptext { // this has to be parsed as C++ code, which has some differing lexing rules template <typename T> void Hug(T& Whomst) { DoHug(T::StaticClass(), &Whomst); } }
    but C++ is similar enough to UnrealScript that we are able to get away with lexing it using the main UnrealScript lexer
    we even lex variable metadata var int Something <ToolTip=bah>; using the lexer, storing invalid characters and errors as some InvalidCharacter token kind or something
    and that’s without emitting diagnostics - let the parser handle those instead
    one place where the current approach of the lexer eagerly emitting diagnostics fails is the case of <ToolTip=3D location>, where 3D is parsed as a number literal with an invalid suffix and thus errors out
  - implementing this taught me one important lesson: context switching is expensive
    having the lexer as a separate pass made the parsing 2x faster, speeding up the compiler pretty much two-fold (because that’s where the compiler was spending most of its time)
    my suspicion as to why this was slow is that the code for parsing, preprocessing, and reading tokens was scattered across memory - also with lots of branches that needed to be checked for each token requested by the parser
    I think also having token data in one contiguous block of memory also helped, though isn’t as efficient as it could be yet.
    the current data structure as of writing this is rust struct Token { kind: TokenKind, source_range: Range<usize>, }
    
    struct TokenArena { tokens: Vec<Token>, } (with some irrelevant things omitted - things like source files are not relevant for token streams themselves)
    I don’t know if I’ll ever optimize this to be even more efficient than it already is, but source ranges are mostly irrelevant to the high level task of matching tokens, so maybe arranging the storage like rust struct Tokens { kinds: Vec<TokenKind>, source_ranges: Vec<Range<usize>>, } could help
    another thing that could help is changing the usize source ranges to u32, but I don’t love the idea because it’ll make it even harder to support large files - not that we necessarily will ever support them, but it’s something to consider
insanium
- section for incredibly wack ideas that will never work but fill my inner bit twiddle magician with joy
- also see Stitchkit’s insanium

architecture

ideas to try out

ideas I tried out

insanium