Long story short, Richard proposed moving to Zig while we're rewriting so much of the compiler
And we all seemed to agree
Ok cool
So next weekend, I'll have a PR ready for us to look over the IRs for a Zig compiler
Written in Zig in our existing repo
@Joshua Warner I was hoping we could talk about what we would want the parser to look like in a new Zig world. It's a good opportunity for us to implement a lot of the things we've talked about behind the scenes
We'll be all opening said PR in Zed and collaboratively shaping it how we think things should look, and then maybe starting to implement something pretty soon!
I'm busy this weekend vacationing out of town, but don't let my plans to set up these IRs next weekend stop people from doing something before I do for next weekend's meeting
For the parser and ast, I’d start by at least loosely following the design of the parser and ast for zig itself
Probably wouldn't be a bad choice :-)
Let's talk sometime in the next week if you have some time. Nothing formal, just over Zulip async
@Sam Mohr I think someone should set our intention and add a top-level directory for the Zig project
I'll do that ASAP, not sure when the "possible" part is
to Ayaz's point about debuggability and struct-of-arrays, as far as I can tell Zig's MultiArrayList
has the same ergonomics as a normal Rust Vec
except it's automatically struct-of-arrays behind the scenes
so the (very serious) debuggability/ergonomics downside we've had of doing SoA in Rust may just be a non-issue in Zig
also @Andrew Kelley mentioned to me, and said it was ok to share:
if your dev loop ever gets longer than like 1 second let me know, I bet we can keep it under that number
here's the llvm bitcode builder: https://github.com/ziglang/zig/blob/4de2b1ea65e6b54cedfe56268a8bf8e9446addb0/src/codegen/llvm/Builder.zig
https://github.com/ziglang/zig/blob/4de2b1ea65e6b54cedfe56268a8bf8e9446addb0/src/codegen/llvm.zig#L9
Also, with this rewrite, I assume we'll add in some of the platform changes. Specifically thinking it would be good to design from the beginning to assume that platforms pass in a gigantic struct of functions pointers. That struct would contain all effects and all roc_
special functions like for allocation. It would be used the entire call stack in roc. I think that will fix some linking problems and be very important for eventually wiring up a roc interpreter.
Not to mention finally fix our llvm c-abi woes. I wonder if we can share some code for c abi with zig instead of doing it manually.
Yeah Richard's cooking a whole plan for fixing llvm by cooperating with the zig guys.
Also, reminder to future llvm backend writer (maybe myself). Make sure to follow this to help make llvm happy: https://llvm.org/docs/Frontend/PerformanceTips.html
I'm definitely keen to scope out the platform related things we want to fix too. Like we can leave the shared memory stuff behind and just go straight to the new test provided by the host.
what is the issue with llvm?
Honestly the biggest annoyance with llvm is that it doesn't deal with calling conventions. Second biggest annoyance is that it expects the ir in a specific form to optimize well (like all allocas in the entry block)
That is at least thinking from the code gen side
Not a huge deal to do it manually, but would be nice to just share with the zig compiler since they have already had to solve some of these annoyances
We currently have a lot of c-abi calling convention bugs in our llvm backend
This is probably a dumb question - or will be construed as such - but is there a world where it's better and faster to compiler Roc to Zig?
Andrew shared this - https://github.com/ziglang/zig/blob/master/test/c_abi/cfuncs.c - it's not the actual implementation, but it's test cases written in Zig
Anthony Bullard said:
This is probably a dumb question - or will be construed as such - but is there a world where it's better and faster to compiler Roc to Zig?
it's definitely strictly slower, plus then we'd have to bundle an entire Zig compiler inside roc
:sweat_smile:
Well, I meant would there be a simplification to our compiler that would / could justify that dependency
compiling to C is more common, but yeah it's definitely slower
I don't think compiling to c is that much simpler than compiling to llvm
it would be from the ABI perspective specifically
but in other ways probably harder
Yep, that is the main gain. You don't have to implement c abi.
not sure if it would be a net win overall when you put the two together, not to mention what it would do to our build complexity :sweat_smile:
I thought with Zig there is higher-level constructs that would make a lot of things simpler
But just act like I never asked the question :rofl:
Roc primitives are pretty simple and we already can write builtins in zig instead of raw llvm, so don't think otherwise using zig is a big difference
Andrew said:
https://github.com/ziglang/zig/blob/4de2b1ea65e6b54cedfe56268a8bf8e9446addb0/src/codegen/llvm.zig#L5423-L5722
it lowers from Zig IR ("AIR") to LLVM IR in this logic. So the best thing this codebase has to offer is perhaps the opportunity to port that ParamTypeIterator abstraction, which handles many calling conventions in addition to the C one
see also this: https://github.com/ziglang/zig/blob/4de2b1ea65e6b54cedfe56268a8bf8e9446addb0/lib/std/Target.zig#L3326-L3391
Like we already have the ability to dish out to zig for anything complex that we don't want to write in raw llvm ir.
Yeah, I bet if we can use some of zigs backend for llvm as a library, it will solve the hardest parts of working with llvm. That will be awesome
yeah I feel like if we:
...we should end up with something that works as well as Zig's does, which is to say - very well! :smiley:
Yeah, like Joshua is saying, one advantage of Zig is that the Zig compiler is maybe approachable enough that if nothing else there could be some code sharing - or at least some patterns that we can pick up.
Andrew did add a caveat:
note that this isn't enough, you still have to follow certain undocumented rules about what LLVM types and attributes to use in parameters and return value
yeah plus Andrew is keen to help us out, so we're not just poking around Zig's code base in the dark with a flashlight
By "sharing" I mean mostly copy/paste/iterate
Richard Feldman said:
Andrew did add a caveat:
note that this isn't enough, you still have to follow certain undocumented rules about what LLVM types and attributes to use in parameters and return value
Yep, makes sense. But should ease some pain still.
Whoa, I was not expecting this, nice!!
I cannot believe how much has been changing in Roc land this last year :big_smile::star:
Tried translating an old tokenizer experiment from rust to zig: https://github.com/joshuawarner32/roc/blob/c80a3ba0e453abf495619a1abf8ed28c9e6ff909/zig/tokenize/src/main.zig
This reminds me. For zigs tokenizer, didn't they remove the tag. Instead they just load the offset and reparse the token (cause the token is essentially the tag). Not saying we need to do that, but reminded of the DOD talk on the new zig irs and such.
Other random cool technique. For chomping whitespace and trivial things, some sort of SWAR mask may enable easily going 8 bytes at a time for essentially the same cost.
For chomping whitespace and trivial things, some sort of SWAR mask may enable easily going 8 bytes at a time for essentially the same cost.
Roc actually already does this! (I wrote that part :P)
https://github.com/roc-lang/roc/blob/main/crates/compiler/parse/src/blankspace.rs#L263
Time and time again, it seems the Roc parser is just Joshua turtles all the way down
How do people feel about scoping in a bit more than just functions, values, and strings to start with? If we want to allow for dev parallelism, we want to give people tasks they don't require as much coordination with. I think once the compiler is working all the way through with just strings, adding subsequent features will happen where a single change affects the whole pipeline. Seems like we can push that off to start with by making the stages bigger silos for now
Currently, we need:
Maybe adding in if-else or records could be something else that's not overly complex?
Also, a naive but parallelism friendly single-Env replacement would be to get rid of Env as a concept and to save everything in a stage's IR for a given module. When compiling a module for stage N, we compile its dependencies first and pass their N+1 IRs as args for the module that depends on them. For example, if module Foo imports module Bar, then during type specialization, we'd type specialize Bar first, and then pass the TypeSpecIR for Bar as an arg to specialize_types(typecheck_ir_for_module: TypeCheckIR, type_spec_ir_per_dep_modules: Map<ModuleID, TypeSpecIR>)
It would be better to load in the relevant data into the main module's IR to avoid having to look in two places for deps, but we should be able to make that improvement later
I'm gonna run with that approach for the Zig skeleton unless someone has a better but still simple idea
it's probably about the same if we sketch things out but don't have all of them implemented end to end right away
I think the main thing is that we start with a simple skeleton and don't try to bring everything in at the outset :big_smile:
Agreed
just a small handful seems fine
Tangentially, does anyone have opinions on whether typechecking would look how it does today or would we do it structurally differently if we rewrote it (as is the plan). Somewhat an @Ayaz Hafiz question I presume. I think I know what the IR will look like for most stages, but typechecking is like the one hole in my mental model
i would say rewrite it if it makes it simpler for you
the important thing is not whether it's fine rn imo
it's can you build on top of it
i would maybe write a small unification-style typechecker in a toy language to build an intuition for how it works if you all don't have a solid one already, you can pluck a parser for some random language off the internet and write a checker for it
That's a good idea
I think the unification strategy makes sense to me (roughly), though writing an impl myself should help a good deal
The thing that feels messy to me is adding type constraints right now, and I'm wondering if there's a way to reduce the vibe of "hopefully we add all the right constraints"
It feels easy in the current system to miss or add too many constraints
And I don't know a good strategy to help with that besides maybe grouping behaviors like "constrain a function type" and "constraint a record" and pulling them into separate functions that take a struct for their args, meaning it's harder to misalign on what constraints to add?
Idk
maybe get rid of constraint gen
just unify when you need to
it's fine
Oh??
Do you know of a language that does that?
I'll just read their compiler
I’ll follow along with you Sam, unification is where I went off the rails with my language
brother
yes, plenty of languages keep constraints inline while typechecking
eg
fn infer(..) -> type_variable {
...
case
Apply(f, x) {
t_f_in_infer = make_var()
t_f_out_infer = make_var()
t_f_infer = make_var(TFn(t_f_in_infer, t_f_out_infer))
t_f = infer(f)
t_x = infer(x)
unify(t_f, t_f_infer)
unify(t_x, t_f_in_infer)
t_f_out_infer
Okay, cool
I'll mess with it
If unify(t_f, t_f_infer)
fails, emit an error about f
not being a function. If unify(t_x, t_f_in_infer)
fails, an error about the argument type being wrong
Makes sense!
one thing that took me awhile to understand is the "occurs check"
as I understand it (Ayaz, feel free to correct or elaborate on any of this!) the basic problem it's trying to solve is that if you have an infinitely recursive type, you don't want the type-checker to get stuck in an infinite loop hopping from one type to another trying to infer their types, but since they depend on each other, it just never terminates
so the "occurs check" is to say "hey, does this particular type variable occur anywhere in this other type?" (because if so, we have an infinite loop!)
so it just descends into that other type and tries to find any instances of the requested variable - as soon as it finds one, it returns
so the occurs check can't possibly get stuck in a loop
so there are certain places in unification where we're like "ok before proceeding, stop and do an occurs check to make sure that proceeding won't get stuck"
(and then bail out and report an error about it being an infinite type if we detect one)
I'm not sure if there are other use cases where it comes up, but my understanding is that this is its main job
also, there's the concept of rank
Folkert and I spent a lot of time figuring out how that one works in Elm's compiler, and what we concluded was:
it would be rad to actually understand for real how it's supposed to work :laughing:
there's also a thing called pools, and I have zero clue what they do
The explanation for ranks is linked here in the compiler: https://github.com/roc-lang/roc/blob/670d2550603b9bb29ab238b6ed6180778a5d107d/crates/compiler/solve/src/solve.rs#L78
http://okmij.org/ftp/ML/generalization.html#levels
I'll try to re-read it before next week
The rank tracks the number of let-bindings a variable is "under". Top-level definitions have rank 1. A let in a top-level definition gets rank 2, and so on.
This is a better explanation than mine from above: "The way it works is that it's for like...defs, and you sort of increase it when...decreasing def depth, or something? Well, but then with function arguments it's...well, and then pattern matching it's....anyway, it's definitely something."
yeah, so the tricky part is taking that general idea and figuring out exactly which situations need it, and then making sure to pair the incrmeents and decrements correctly (e.g. decrement the current rank the appropriate number of times when exiting a particular scope)
Yeah, wondering if there's a good way to encode it into our approach so we can't mess it up
Gonna take some brain power for that, probably
This is a let in the ML understanding, so every successive def is a new let (since in ML there is only expressions)
That’s why SML and OCaml use let x = … in
because the next let is a child expression
yeah we already convert to that representation
as in, we start with a flat list of defs but then convert them to nested during canonicalization
in other words:
a = 1
b = a + 1
c = b + 1
c + 1
...canonicalizes to the equivalent of:
a = 1
b = a + 1
c = b + 1
c + 1
I forget what the reason for this is - maybe because they each have their own scopes?
Not sure what the original reason was, but it does make the IR simpler. "either it's an expression, or a single def followed by an expression."
there's also a correctness aspect to it
I just know that no ML-derived type system really works without it
we originally didn't do this, and when we switched to it, it fixed bugs
yeah
I don't remember the exact reason though, this would have been like 2019 :sweat_smile:
that said, I don't think we actually need to rewrite the IR into that form if we don't want to
but we do need to pass the info to the type-checker as if it were in that form, if that makes sense
I think it has to do with a new var has to be scoped and it has a lifetime that has to then be resolved and rolled up into its parent
yeah like the "add this to the scope, increment the rank" and "remove it from the scope and decrement the rank" stuff needs to happen as if it were in that nested form, regardless of whether it is in the IR
Yes, I want to move parsing to be a simpler IR that’s flatter, but can will have to continue to do what it does today
amusingly, I think in the someday-future when we start doing adjacency nodes (not in this version of the compiler!) it might end up being the same haha
like there might not end up being a distinction at the IR level between nested and not-nested adjacent defs
Richard Feldman said:
as in, we start with a flat list of defs but then convert them to nested during canonicalization
I'm really surprised this makes any difference. Feels like you could just walk the dense list and derive all of the same information.
yeah that's what I mean about the canonical IR being decoupled from this, but the type checker needing to be told it's in the nested form even if it's not
speaking of general principles, we talked about this a bit on the call, but I definitely think we should put a stronger value on human-readable code in tests
Luke is in alignment with you there, and I think also Joshua. I'm confident we'll make that happen!
e.g. parsing tests consistently start with Roc code as inputs, and I think that should also be true of the other stages of the compiler
and as far as outputs go, transforming them into something more human-readable than raw IR nodes also seems like a good idea
and also fuzzing right out the gates :big_smile:
I think fuzzing would have caught a lot of those Rank mistakes earlier
and missing occurs
checks
Yes each IR should have a human readable representation that is divorced from the specific languages default formatting
Also, not sure how helpful this would be, but for mlir, it is useful to be able to write tests in terms of human readable ir and single pass transformations. That said, it doesn't always work to break down at that level. But can make IRs and passes a lot more debuggable if you can do tests like that easily.
a thought: I wonder if it would be helpful to start making an early API and test suite for editor commands
like even if we don't have the implementations right away, just having the pieces in there as part of the skeleton so we can think about which operations have which inputs and outputs
so that can inform how everything fits together
instead of trying to implement it after the fact on top of a process that was designed with only cli builds in mind
I’m assuming you are talking about the Roc Editor, not LSP Code Actions?
I think it's the same consideration regardless
Structural editing would be the difference, I think
(I wasn’t around when that was a live topic of discussion so I don’t know the first thing about the former)
Otherwise should be basically the same
like "the user has asked for this information and provided this input"
I don't think structural editing is as good an idea as I used to :sweat_smile:
but also I don't think it makes that much of a difference
incidentally, I know that Rust and C# were both designed to be editor-first compilers, but they're both unacceptably slow to me, so I'm not saying we should do what they did
just that we should keep these use cases in mind early
a good example of what I'm talking about:
so it would be good to make sure that once compilation is done, we can do all of that without it being a big pain :big_smile:
Yeah, that can be pretty agnostic. Good idea
batch compiler and language server compilers (query compilers) are totally different use cases. i wouldn't try to fit both in one
regarding list of statements vs expressions - they are isomorphic. just nested expressions are a lot easier in practice to work with. you can get the type of a whole expression at one node vs looking at the last item in the statement list
i wouldn't try to fit both in one
The roslyn C# compiler is built exactly like that, and it seems to have worked out reasonably well at least? Typescript too, I think?
Would be interesting to talk to someone on one of those teams to get their take
yes but have two different modes
Ayaz Hafiz said:
regarding list of statements vs expressions - they are isomorphic. just nested expressions are a lot easier in practice to work with. you can get the type of a whole expression at one node vs looking at the last item in the statement list
I wouldn’t try to use statements past parsing
regarding ranks - this is purely a performance optimization. it's not required. to build an intutition i think Mimram's Program=Proof is the best resource; see section 4.4.4 specifically starting at page 209. He explains the inference mechanism in the most succinct and understandable way i've seen. https://www.lix.polytechnique.fr/Labo/Samuel.Mimram/teaching/INF551/course.pdf
Just trying to minimize the size of the parse AST
And make it more fault tolerant for error reporting
Ayaz Hafiz said:
regarding ranks - this is purely a performance optimization. it's not required.
right, but if you have them and get them wrong, it seems to break correctness :sweat_smile:
yes because if you get it wrong you either over generalize or under generalize
the alternative is to generalize based on the kind of expression
Ayaz Hafiz said:
batch compiler and language server compilers (query compilers) are totally different use cases. i wouldn't try to fit both in one
do you think we should make two completely different compilers? :thinking:
occurs check - this is also not required in a language with infinite types, it is typically employed only to detect recursion and stop it. The current implementation uses it to insert "recursion points" that mark where the compiler should box a value at runtime. this is also unnecessary. Normal unification works just as well as long as you add a check to see that if you have already tried to unify two types A and B, if A and B are seen again, you short circuit the unification (hopefully it's clear why this is correct but i can explain if helpful). Then during code generation you determine the recursion point separately.
no, i would just start with the batch compiler use case. because programs are smaller queries are going to be fast even over the batch. then the query use case can be solved later
ahh right, I forgot about detecting recursion!
the "have we seen this already?" check sounds simpler in that we could just implement it once, as opposed to having to call occurs in a bunch of different places, right?
in principle you only need to run occurs after generalization so i dont think it makes a difference in terms of number of places it's called
but i would push it down until its actually needed
you mean in code gen?
yes
seems reasonable! :+1:
it'll be nice that we won't need to deal with optional record fields in the type checker
that will really simplify the record logic
oh yeah, we should remember to handle as
whenever we're doing pattern matches and imports and such
right now it's implemented pretty inconsistently :sweat_smile:
Do we have a strong direction around what patterns we will use to get around Zig's lack of interfaces? _I_ know plenty of ways to deal with it, but as I'm sitting here lookin at our current parsing code, we use a number of traits. The most obvious being Parser.
And I'd like to at least know that I'm going down a road that is going to be well-received by others here
Why is parser an interface and not just a concrete type with methods?
It's a pattern from FP languages for recursive descent
I'm actually thinking about explicitly NOT trying to copy that pattern
yeah
I don't think we need it
I have a structure for parsers (in procedural languages) that I'm pretty familiar with
I'm going to see how far it can take me
And then I'll present it
Also, as for uses of traits/interfaces in general. I think the zig equivalent of a trait is a comptime returned struct with different function implementations based on the concrete implementation. And interfaces are the same thing but runtime function pointers.
Can you show an example of what you are talking about? Because a Zig trait equivalent is very verbose usually
Unless you want to do some very tedious things in comptime and have all implementations live in one file
But a Zig wizard I am not
I think the recursive descent parser design Josh has in mind wouldn't want this anyway
Yeah, I guess for what I am thinking it requires central registration for traits, but they could still be implemented in various files.
Oh, looks like you can do it without central registration in zig: https://github.com/permutationlock/zimpl?tab=readme-ov-file#example
That said, I highly doubt we'll need this in the compiler. Almost everything is static concrete types or can be designed to be so.
Fixed some bugs in the tokenizer I pushed earlier: https://github.com/joshuawarner32/roc/blob/zig-tokenizer/zig/tokenize/src/main.zig
Now it:
Did you make it handle snake_case identifiers and import
statements in the header?
It does not currently handle snake case; I think those'll probably be tokenized incorrectly at present
Not hard to add tho
Yeah I did that on my local copy
There's not a whole lot it needs to do in order to handle import statements, with the one exception of making a token for the import
keyword (which needs to be done)
it looks like there's already enough here to try out zig's builtin fuzzing on! :smiley:
Indeed!
There is one minor syntax tweak I'd like to make, which I think was discussed elsewhere, and that's changing up the ext syntax from {a: Str}ext
to (IIRC?) {a: Str, ..ext}
- or something similar
that's it exactly! :100:
Sweet
@Joshua Warner What are your thoughts on the discussion above?
Awesome. The old syntax requires some bending over backwards that I'm going to happily rip out of the zig tokenizer.
Re: replacing the trait-laden system we have in Rust with a more straight-forward parser struct with just a ton of methods on it working on some sort of input/state struct?
Yeah, that's exactly my thinking.
Straight-forward recursive descent
Sweet. I'll continue exploring down this path then
Using your tokenizer output as input
Maybe we should have a branch on the main roc repo we can collaborate on?
Thank you for saving me a couple of hours of work with that!
Probably
Right now I don't have a ton of time so I'm just poking around - remembering how to write Zig, and exploring the design space
If you're interested in design space exploration, here's an old prototype I wrote: https://github.com/joshuawarner32/roc/blob/cypress/crates/compiler/cypress/src/parse.rs
Cool, I'll check it out
This is a design I've used (with some small tweaks) in parsers in Dart, Go, and Zig: https://gist.github.com/gamebox/947afc1fb18cae753be2d25a7ee777dd
Of course the AST-level methods would differ a lot
Yep, that looks like roughly the pattern I typically use.
btw Josh, check this out: https://github.com/ziglang/zig/pull/21257#issuecomment-2336865183
Your prototype above is pretty INTERESTING!
(on the thing I posted above) I'm not super gung-ho on that direction at the moment, and it's probably not a thing we want to try to quickly prototype with, but that is somewhat closer zig's parser, and also has some perf advantages. (IIRC, it was ~2x faster than the current roc parser, prior to any attempts at micro optimization) But harder to read/develop.
Yeah, it looks very DOD style
Seems like something Andrew K would enjoy
But micro-optimizing the parser perf doesn't make a ton of sense given how much compile time is usually devoted to it
_IF_ it makes the parser harder maintain or debug
It was like 30% win, 70% loss for debuggability
The fact that the parser state was easily serializable and inspectable at any point make it really easy to visualize what's going.
That's great. I'll try to read through it tonight when I have more time
But at the same time it's a very _weird_ pattern. The combination of the rigid linear layout of the AST, roc's somewhat weird grammar, and trying to do it "stackless" made it all a lot more headache than it really needed to be.
the thing I linked to makes it possible to do a really direct state machine style
where you're basically like "if I encounter this condition, GOTO this other place"
except instead of actual gotos, they're all labeled
Sorry Richard, I don't have any experience with that kind of parser (I'm a one-trick pony with RD), do you have an example to share?
(I can imagine a simple example, but at the scale of a full PL grammar it's hard)
Actually it reminds me of the grammar that's made by Nearly
it's what simdjson uses for the parsing step, except they use actual goto :laughing:
(I don't have a link handy and I'm on mobile)
Which is a tool I was forced into using for making the Formula language in our product (in JS)
I'll take a look at it
I think they do it for performance, but it seems like it would be super straightforward to read and understand
It's been a while since I read about simdjson
don't look at the lexer :laughing:
I think complicated state machines can be very hard to understand a non-linear flow
But I am open minded!
oh btw, I think we should restrict line lengths to u16 and total number of lines per file to u16
so regions can be more compact
Think of it as a while loop with a switch statement in it over the current state of the state machine. It really isn't anything special.
Just more optimized than that
I'm fine saying you can't have a line that's more than 65k lines long, and also that you can't have a .roc file that's more than 65k lines long
I guess we’ll cross the “Why can’t you compile my 80k LOC module” bridge when we get there
In some ways you could say we’ve made it if we do
oh that's easy: "Because .roc files aren't allowed to be that long. You have to split it up."
I'm so excited for when this rewrite leads to having proper debug info in the llvm backend
:thinking: I wonder how debugging in an interpreter backend could work
step debugging I mean
I don't think it could possibly be compatible with gdb/lldb unless I'm missing something
I think it would need to do its own thing
Richard Feldman said:
oh btw, I think we should restrict line lengths to u16 and total number of lines per file to u16
Maybe even u8 line lengths?
Probably need to look into pdb more. Probably has things to learn from
Never mind I guess that wouldn’t help because of alignment
yeah unless we did SoA regions or something :sweat_smile:
Did zig end up going with a raw u32 offset? Then they recalculated line and col info if it is needed? Not sure that is a better choice. It is more flexible though.
hm actually in Zig it might be pretty easy to do a packed struct of a u32 split into a u20 and u12
oh yeah I think they did
I wonder about that for editor tooling, but maybe it's fine?
like the find all references example
Cause you only need line and col for warnings and errors....I guess you also need it for expect and dbg messages...
Hmm, don't you need it for every node in llvm for debug info?
oh yeah probably
And yeah, I think something like U22, U12 sounds amazing. Like pick a reasonable line that allows for longer files at the cost of shorter lines
Using offset only is pretty typical
You can just pass the input to the reporter and have it calculate the line:col positions on the fly
My parser above does that
u32 split into a u20 and u12 would allow individual lines to be 4096 bytes and then each file could have up to 1M lines
Joshua Warner said:
Tried translating an old tokenizer experiment from rust to zig: https://github.com/joshuawarner32/roc/blob/c80a3ba0e453abf495619a1abf8ed28c9e6ff909/zig/tokenize/src/main.zig
saw this last night and made this: https://clbin.com/m5TF7
when you have 2+ ArrayList with the same length, that's a great case for MultiArrayList which is equivalent but will have only 1 length field for all of them, as well as manage exactly 1 allocation for all the arrays
Richard Feldman said:
so the (very serious) debuggability/ergonomics downside we've had of doing SoA in Rust may just be a non-issue in Zig
with the llvm backend it's still a pain in the ass to debug MultiArrayList, however, with our self-hosted backends (currently x86_64 only, aarch64 to follow next) we have custom dwarf + lldb fork that recognizes zig std lib types and makes debugging really nice. same thing goes for hash maps
this project may be interesting to watch long term since jacobly (author of above lldb fork as well as zig's x86_64 backend) has taken an interest in it
Anthony Bullard said:
You can just pass the input to the reporter and have it calculate the line:col positions on the fly
Yeah, would just require calculating all line and col offsets when generating debug info. So not sure it is that much of a gain.
I know this is a silly metric, but I hope with the new compiler rewrite I'll feel confident figuring out any part of the compiler. Currently, parser is manageable but pretty opaque to me. Some of type checking is fine, but a lot is hard to follow fully. Obviously don't really know where to start with our more complex type related passes. Then I can understand all the backends, but I think some of that is due to lots of exposure rather than them being clean or simple.
Brendan Hansknecht said:
Anthony Bullard said:
You can just pass the input to the reporter and have it calculate the line:col positions on the fly
Yeah, would just require calculating all line and col offsets when generating debug info. So not sure it is that much of a gain.
For a normal use case you are reporting multiple orders of magnitude fewer problems than you are parsing AST nodes
Richard Feldman said:
it looks like there's already enough here to try out zig's builtin fuzzing on! :smiley:
Fuzzing is very alpha right now, I recommend to join zig development if you want to play with it. I mean really alpha like I have a branch with everything rewritten that I haven't merged yet. I expect that to become beta quality during the 0.15.0 release cycle. I will say though having it integrated into the compiler tool chain and unit tests is going to be a killer feature. I even have a web UI where you can watch the fuzzer find new code paths in realtime
I’ve used it in three parser projects and it was still fast enough
Richard Feldman said:
I'm fine saying you can't have a line that's more than 65k lines long, and also that you can't have a .roc file that's more than 65k lines long
would you believe me if I told you we had a hand-written, hand-maintained file in the zig compiler codebase that uses 78% of this quota :grinning:
Andrew Kelley said:
Richard Feldman said:
it looks like there's already enough here to try out zig's builtin fuzzing on! :smiley:
Fuzzing is very alpha right now, I recommend to join zig development if you want to play with it. I mean really alpha like I have a branch with everything rewritten that I haven't merged yet. I expect that to become beta quality during the 0.15.0 release cycle. I will say though having it integrated into the compiler tool chain and unit tests is going to be a killer feature. I even have a web UI where you can watch the fuzzer find new code paths in realtime
I assume it is easy to plug zig into existing c++ fuzzers currently? Like libfuzzer and afl? Just need to compile zig with some extra llvm flags for coverage info, right?
Glad to see everyone hyped about this. I'm going to move this discussion into our compiler development channel to recover the contributor coord thread. :smiley:
292 messages were moved here from #contributing > contributor coordination meeting - Feb 2024 #2 by Luke Boswell.
Joshua Warner said:
Maybe we should have a branch on the main roc repo we can collaborate on?
I think this would be a good idea.
We discussed all the zig code should live under src/
, so I think just start with that structure is ok.
Also for the parser stage - tokenizer specifically.. I think it would live somewhere like
/src/check/parse/tokenize/...
based on the presentation we were organising verything according to it's function and nesting from the top-down, phases->stages->etc
One thing I'm really unsure about because I haven't researched it yet, is if we want or need to organise all of the zig modules into separate zig "packages" or if that is just unnecessary.
One of the goals is for it to be easy for tooling to reach in and use the code for multiple purposes.
Do we need to define these boundaries ahead of time and separate them into packages? or are zig modules easy to refer to, like rust crates?
I think we should use a separate folder but not a separate branch
better to just keep merging stuff into main
since we're not going to cause merge conflicts with any existing PRs anyway :big_smile:
To clarify this /src/check/parse/tokenize/...
, in my mind this is a structure like;
check
phaseparse
stagetokenize
functionI like to structure things based on their function or behaviour, for at least the top one or two levels. But I appreciate that this can be a controversial topic.
Yeah, trying to organize roughly based on pass ordering and IR sounds like a great idea. Should help avoid dependency messes.
Though tokenize may just be tokenize.zig
in this case. Only needs to be a folder if it is so complex that it needs many files
Brendan Hansknecht said:
Andrew Kelley said:
Richard Feldman said:
it looks like there's already enough here to try out zig's builtin fuzzing on! :smiley:
Fuzzing is very alpha right now, I recommend to join zig development if you want to play with it. I mean really alpha like I have a branch with everything rewritten that I haven't merged yet. I expect that to become beta quality during the 0.15.0 release cycle. I will say though having it integrated into the compiler tool chain and unit tests is going to be a killer feature. I even have a web UI where you can watch the fuzzer find new code paths in realtime
I assume it is easy to plug zig into existing c++ fuzzers currently? Like libfuzzer and afl? Just need to compile zig with some extra llvm flags for coverage info, right?
Yeah that all works, I recently tried out that use case and fixed a few codegen things to make it a smooth experience. I think Loris has a nice example somewhere, let me grab a link and make sure it still builds
Useful talks to watch if you want more context on DOD and how things are done in the zig compiler. Likely will help with thinking about how to model data structures in the new compiler:
Andrew Kelley Practical Data Oriented Design (DoD)
Data-Oriented Design Revisited: Type Safety in the Zig Compiler - Matthew Lugg
second talk especially has zig compiler ir specific designs and example code.
Richard Feldman said:
oh btw, I think we should restrict line lengths to u16 and total number of lines per file to u16
We currently use u32's to indicate positions in the syntax tree at least (and I _think_ elsewhere). Just byte index into the original string. That's both (1) the same size as 2 u16's, and (2) more flexible - i.e. you can have 17k lines just fine, so long as they're normal length lines.
I have definitely worked in projects with one or more files with 16k+ lines. While I don't want to encourage that, it's also a small enough limit that it doesn't feel worth it to enforce.
Seems really easy to go over 16k lines with codegen
re:
https://github.com/kristoff-it/zig-afl-kit/
if you give this a spin, I recommend to have a chat with Loris if you run into any issues. I didn't try using AFL yet other than reading the source code since I'm more interested in advancing the integrated fuzzing implementation
@Andrew Kelley Applied your suggestions - thanks!
FWIW, the reason for adding an extra entry to self.output.offsets
was essentially the same job an Eof token would be doing. In the parser that corresponded to this, having that there avoided some branches - but I didn't need the actual eof token itself, so I never added it. :man_shrugging: Went ahead and replaced that with a proper EndOfFile token.
Also added the import keyword, removed the NoSpace weirdness, and it now supports snake_case idents
ah yeah I figured it was something like that
Tokenizer PR here: https://github.com/roc-lang/roc/pull/7569
another thing you might have fun playing with is labeled switch continue. In the case that the value used is comptime known, it's a direct branch to the other case. This is a common optimization trick used by emulators for example. When we switched our tokenizer to use it, we observed a 13% perf improvement
Joshua Warner said:
Tokenizer PR here: https://github.com/roc-lang/roc/pull/7569
IT BEGINS
(btw, please please rip my zig code to shreds; this is a useful learning opportunity)
re: labeled switch continue
Ohhhh Richard posted that above, but I didn't get the connection initially. I'll check it out!
it's also just like really satisfying to use for some reason, idk if it's just me
Joshua Warner said:
(btw, please please rip my zig code to shreds; this is a useful learning opportunity)
ok, you got it :smile: I trust you to tell me if it becomes too much
I'll be curious to hear how the perf measures up old code vs new code, although I'm sure the tokenizer is insignificant compared to the rest of the pipeline
General request:
As we spin up this new compiler, can we try to add file and function doc comments to everything (or at least everything exposed). They can be super simple, but I think if we start from the core with a culture of documentation it will be very useful. I think we will be much much more likely to document the compiler flow if we are separate stages of the compiler into different files and we add a high level comment about the goal of each file and roughly what it is meant to do.
Beyond Rust compiler compilation speedup that is irrelevant with Zig's compilation speeds, I don't think there's a good reason to split our compiler into separate libraries. Folders seem sufficient. To that end, I don't think we should consolidate the IR into a single place, that moves the data types away from the logic that operates on them. I'm gonna put the IRs in their respective stage folders, probably in <phase>/<stage>/ir.zig
I agree with that
Totally agree
Fun random thing I just realized. Cause the interpreter will be written in zig, it will be able to just call the zig builtins without any sort of ffi complexities.
Yeah that was one of the big motivating factors Richard mentioned. :smiley:
How does one organize a large multi-file zig project?
Do you make intermediate libraries that reference other libs? Or is it better to do one big source tree that builds into a single exe?
On big source tree with direct file imports from what I have seen
I've starting putting a simple shell for the cli together... not sure if it's something we'll want to keep. But something to parse the cli args and build a binary from. Based pretty heavily off the zig compiler. -- mostly as a learning exercise, but I plan to make it a PR so we have something.
I'm not sure the exact standard, but I would assume something like:
build.zig
build.zig.zon
main.zig
<phase.zig>
<phase>/<stage>.zig
<phase>/<stage>/something.zig
Where zig files are only allowed to import from files at the same level or from a level deeper if the folder name matches the zig file name. That enables clean separation of various parts of the compiler with clear interfaces
And how does that work with tests? One test target from main.zig? Or multiple?
And if a <stage>
is small enough, or just getting started, it may just be in one file. In that case it would just be <phase>/<stage>.zig
and there would be no <phase>/<stage>/something.zig
I'm not sure the best way to do tests. One natural way (but may not scale well) is to put tests at the bottom of the file. That way I can just do zig test <phase>/<stage>.zig
to run all tests for a specific stage.
But it might be cleaner to make a separate test directory. Based on experience with rust, you want a reasonable number of test executables/targets. If you have too many, it wastes a crap ton of time linking them all. If you have too few, you have to compile way too much code for small changes.
cc @Andrew Kelley in case he has any good tips on zig project organization.
I have this right now:
Screenshot 2025-02-02 at 19.15.34.png
Having trouble importing the tokenizer from the parser:
check/parse/parse.zig:2:27: error: import of file outside module path: '../tokenizer/tokenizer.zig'
const tokenizer = @import("../tokenizer/tokenizer.zig");
^~~~~~~~~~~~~~~~~~~~~~~~~~~~
I think it should be:
check/parse.zig
check/tokenize.zig
If parse needs to be split over multiple files, it would be:
check/parse.zig
check/parse/subpart1.zig
check/parse/subpart2.zig
Ahhhhh cool
Being a beginner is fun :sweat_smile:
I'm definitely still a beginner in terms of expected zig project organization. Though I have worked on a few zig projects at this point, I have never touched anything large or dealt with best practices around organization
This is just some stuff I have gleamed from looking at the zig compiler itself, but I really have not studied it thoroughly
File names fall into two categories: types and namespaces. If the file (implicitly a struct) has top level fields, it should be named like any other struct with fields using
TitleCase
. Otherwise, it should usesnake_case
. Directory names should besnake_case
.
https://ziglang.org/documentation/0.13.0/#Names
Also, the pattern I described follows what the zig standard library does for reference
Also, the TitleCase
just for reference is used to define a type in a single file. For example, instead of defining Cursor
in tokenize.zig
you could instead put it in tokenize/Cursor.zig
. In this case, you would literally copy all of the lines within struct { ... }
as the contents of Cursor.zig
.
Anyway, for structure purpose, I think that we should put unit tests at the bottom of the relevant file. For our larger integration tests, we probably want them to be standalone executables that read the snapshots and what not.
Also, just to explain one more design point, if we have:
check/parse.zig
check/parse/ir.zig
check/canonicalize.zig
and canonicalize
needs access to parse/ir.zig
, it would do:
const parse = @import("parse.zig");
const ir = parse.ir;
and parse would need to export the ir for can to import
Here's my WIP for the cli https://github.com/roc-lang/roc/pull/7571
If others are ok with it, I'm heavily interested in working on the interpreter. Of course, it depends on getting everything wired through type checking before it can be worked on. I feel like it is the highest level thing that I can really help with (both initial implementation and eventual optimizations). I'm sure I'll need help finding the correct design around type info and such, but sounds like a fun project. (also, I'm sure more than one person can work on the interpreter if others are interested).
Hopefully will be able to start by working only with self contained examples that don't need platforms then can expand to passing in pointers for allocators and effects. Will be interesting eventually getting it working in wasm too.
Otherwise, hopefully I can help with reviews and some high level zig organizational stuff.
Luke Boswell said:
Here's my WIP for the cli https://github.com/roc-lang/roc/pull/7571
What order do we want to land things in. Someone has to put the base zig config and organization together. Currently both this and @Joshua Warner's PR both are setting up the zig build and what not.
I'm still cleaning mine up from the feedback. If Josh's merges first I can merge any updates and adapt it.
It sounds like your keen to start on things. Also feel free to push to my branch. I'm not precious about what I have so far... and probably wont be doing much for the next 18hrs
It sounds like your keen to start on things
I guess so, though not like I have that much time at the end of today.
Yeah, I'm so hyped about the zig stuff... I just want to work on this instead of my actual work. :sweat_smile:
Also, as a general note, I feel like for some things I might just make cleanup PRs for instead of adding PR comments. Just feel liking cleaning up some code will be easier to just show the changes that I think would be nice than add a ton of comments. On top of that, they aren't pressing, so I don't think they are worth tons of iteration on PRs for.
Sounds good. I like the feedback because I'm learning. But appreciate its a lot more work.
At a minimum, I'll make sure to add original authors as reviewers.
Yep, definitely better to just do cleanup PRs for now.
@Joshua Warner don't the build.zig ans build.zig.zon usually go in the folder outside of src?
I think we could just leave those in the root of the roc repo and they won't interfere with anything
Luke Boswell said:
Here's my WIP for the cli https://github.com/roc-lang/roc/pull/7571
Ok... I've fixed @Brendan Hansknecht's suggestions. I think we could just merge this and then we've got a basic structure to start working with.
Anyone available to review?
I approved you @Luke Boswell
Brendan Hansknecht said:
cc Andrew Kelley in case he has any good tips on zig project organization.
my main suggestion is to take advantage of namespace nesting, try to follow these namespace-related suggestions, and then once any given struct accumulates "too much" code inside of it, extract it to a separate file.
in my experience one generally ends up with weird/wrong organization when trying to guess ahead of time which files to put stuff in, but a nice organization arises when you prioritize the Fully Qualified Namespace Names having precise, accurate, non-redundant names
https://github.com/roc-lang/roc/pull/7573
zig build test
-- tests to run are specified in src/test.zig
Also .. I was surprised at first that just zig build test
didn't report anything unless there is a failure. So I also "install" the test binary so it can be run separately.
10:40:31 ~/Documents/GitHub/roc zig-cli $ zig build test
10:40:35 ~/Documents/GitHub/roc zig-cli $ zig build && ./zig-out/bin/test
All 4 tests passed.
I don't know if it's controversial... but for now you have to specify roc run
and the run
subcommand isn't optional. It just greatly simplifies the option parsing logic. I figure we could improve later if we still want that.
Didn't we want to remove roc run
? https://github.com/roc-lang/roc/issues/6637
Yes... well remove roc dev
and roc run
in favour of just roc
was the plan ... but now I think it makes sense just to have roc run
to simplify option parsing. So I've haven't added a roc dev
or anything so we're still aligned with that new Cli workflow
The options I'm parsing are based on that Issue and not the current implementation
--opt size
--opt none
etc
Okay, that's good. I think we shouldn't do roc run
even if it's simpler, though. Making roc script.roc
work is what makes shebangs work
I've ignored --backend dev
etc.. because it sounds like we will only have the llvm backend.
So roc run
would use the interpreter dev loop, and roc build
would use llvm.
Sam Mohr said:
Okay, that's good. I think we shouldn't do
roc run
even if it's simpler, though. Makingroc script.roc
work is what makes shebangs work
I agree.. I'll have another crack at it in a follow up PR.
It was just challenging because we still support parsing options before providing the path/to/app.roc
file to run, and we're not sure if we have invalid options or an invalid roc file path being passed. I'm sure there is a way to do it.
Made a PR to start figuring out fuzzing: https://github.com/roc-lang/roc/pull/7574
We discussed all the zig code should live under
src/
, so I think just start with that structure is ok.
Can we move src, build.zig and build.zig.zon to a new separate folder (zig or zigcompiler...)? That way I can put a flake.nix in that folder instead of adding a flake-zig.nix at the root level that also requires custom nix develop
flags to point to that flake etc.
We definitely shouldn't move src somewhere else because that will mean we have to move like a hundred files in 3 months back to the root
But I think just the build files would be okay
Doesn't zig expect the layout to be:
src
build.zig
Sam Mohr said:
We definitely shouldn't move src somewhere else because that will mean we have to move like a hundred files in 3 months back to the root
Do we plan to add ~hundred files to the root currently?
Seems like if we use git mv
to move the folder we can avoid most of the typical downsides
There will be many files in src/
Moving files isn't the real problem, it's moving files with 10 PRs against those files
I volunteer to update all those PRs. I'd really like a separate folder for the new compiler. We want to make tools like this platform that don't belong in src so they'll end up at the root level, that will lead to flake dependency issues. I would also need to add a bunch of exceptions for when the new compiler CI should run vs old compiler CI because there is no clean folder separation.
I don't feel that strongly about it. If you think its really worth this effort, then go for it
:+1: I'll leave some time for others to weigh in on the folder issue if they want to
It's just a folder move. People can update PRs for a folder move. Though I would probably rather move the rust compiler and leave the new zig compiler at root.
That'd be way better IMO
Anyone have opinions on how to handle allocation failures for lists during Roc compilation? I don't know what recovery mechanism there is, so it feels like we'd want to just fail compilation, since it can only mean out of memory. I don't think we should expose handling allocation failures because of this.
Not sure how to avoid threading this logic throughout the entire service without doing something like "if OOM, std.process.exit(1)", though that's probably acceptable with a reasonable error message.
I wrote this function and I'm calling it on allocation results:
fn exit_on_oom(alloc_result: std.mem.Allocator.Error!void) void {
alloc_result catch {
const oom_message =
\\I ran out of memory! I can't do anything to recover, so I'm exiting.
\\Try reducing memory usage on your machine and then running again.
;
std.debug.print(oom_message, .{});
std.process.exit(1);
};
}
I would make the function just be what goes in catch
So it read alloc(...) catch exit_on_oom
At the callsite
That reads better, yeah
Brendan Hansknecht said:
Made a PR to start figuring out fuzzing: https://github.com/roc-lang/roc/pull/7574
neat, did it work? i.e. does it build and link and basically function?
It's broken in nix, but otherwise yes.
I'm assuming that is an issue with our nix config though. Seems that afl clang is somehow pulling in a version of llvm from nix that is wrong or something along those lines.
gotcha. well, that's certainly something we can compete on with an integrated fuzzer :) I'm looking forward to picking that project back up after the release is cut
Oh, actually, might have one minor other bug. I think there are some wrong linker flags that lead it to "fail" on recompiled due to the linker printing to stderr. But it actually succeeds.
Andrew Kelley said:
gotcha. well, that's certainly something we can compete on with an integrated fuzzer :) I'm looking forward to picking that project back up after the release is cut
We will be very happy to switch over as it gets more robust.
I think that go did an amazing job with integrated fuzzing and I'm sure zig can do something at least as good.
Hey @Andrew Kelley other random but related question, would you advise that we follow zig master instead of specific stable versions?
I know a lot of zig projects seem to do that (though not sure how common it is nowadays and best practices). I would assume tracking master would get us things like faster compile times and integrated fuzzing sooner.
normally I would advise sticking to a release but we're like 2 weeks out from 0.14.0 so master branch is probably your best bet (the download page will show you the most recent master branch commit that passed all CI checks)
Brendan Hansknecht said:
We will be very happy to switch over as it gets more robust.
there's a fun demo video in this PR that gives you a little taste of what I'm cooking up: https://github.com/ziglang/zig/pull/20958
Very cool
I rebased https://github.com/roc-lang/roc/pull/7569 on top of the new top-level build organization and did some minimal integration work, mostly just useful for testing at this point. In particular, I dozig build run -- check crates/compiler/test_syntax/tests/snapshots/pass/
to verify that the tokenizer will run over our existing tests without spitting out errors.
@Sam Mohr I'm thinking we should avoid putting too much time into translating the rust to zig for roc/src/check/parse/ir.zig
specifically. It sounds like @Anthony Bullard has been working on this.
Yep, I'm basically entirely ignoring parse. The stuff in the draft PR was initial work that I don't plan to finish
Yep I’m working
Do you have your stuff pushed anywhere? I'd be interested in collaborating. Might have some time tonight.
I can push something later
It’s in a chaotic state now after our convo
np!
@Sam Mohr what is the state of landing the core structure you have been hacking on?
Luke and I are about to call, you're welcome to join. I think I could make a couple things a bit more consistent and then just push anyway, and we could keep cleaning up even after merging something into the main repo.
Choir got cancelled tonight so I've got lots of time for that today.
https://github.com/roc-lang/roc/pull/7580
I want to make the build/
IRs all follow a cleaned up structure, and then we can probably just push to prioritize visibility over finishedness
I like using Zed's realtime collab features. I can leave all kinds of mess behind in Sam's PR :sweat_smile:
Oh cool would love to join
I might be able to in about an hour or so if you are still on
Odds are good, just ping us
Hah well figured out why you didn't have my syntax.zig @Sam Mohr ; because I never committed it :man_facepalming:
And that's why we need CI!
Big shrug, we'll get there soon
@Sam Mohr I figured out the build flag, it isn't --verbose
, it is --summary all
. Prints out a summary of all the steps zig ran, if they were cached, and more clearly shows how many tests passed if they ran at all.
Thanks for the heads up
I found this interesting while creating the type-safe layer on top of the parser AST:
var store = try ast.NodeStore.initWithCapacity(allocator, estimated_node_count);
const expr_index: ast.NodeStore.ExprIndex = try store.addExpr(.{ .int = .{
.token = 1,
.region = .{ .start = 0, .end = 0 },
} });
_ = try store.addStatement(.{
.expr = .{
.expr = expr_index,
.region = .{ .start = 0, .end = 0 },
},
});
const blah: ast.NodeStore.StatementIndex = expr_index;
This compiles successfully, the definitions of each ExprIndex and StatementIndex:
pub const StatementIndex = struct { u32 };
pub const ExprIndex = struct { u32 };
They are what I thought were nominal types, but are treated as structural here. @Sam Mohr you might want to take note.
Changing the implementation of the index types to the following makes the types work fine:
pub const StatementIndex = struct { statement: u32 };
pub const ExprIndex = struct { expr: u32 };
I'll try the enum thing then. There are a few more options
I'm happy with what I got
I think just having a field name resolves it, you should check though.
Here is what usage of the type safe layer looks like:
var store = try ast.NodeStore.initWithCapacity(allocator, estimated_node_count);
const expr_index = try store.addExpr(.{ .int = .{
.token = 1,
.region = .{ .start = 0, .end = 0 },
} });
const statement_index = try store.addStatement(.{
.expr = .{
.expr = expr_index,
.region = .{ .start = 0, .end = 0 },
},
});
const file_index = try store.addFile(.{
.statements = &[_]ast.NodeStore.StatementIndex{statement_index},
.region = .{ .start = 0, .end = 0 },
});
const file = try store.getFile(file_index);
std.debug.print("File: {any}", .{file});
prints:
File: lib_ast.NodeStore.File{ .statements = { lib_ast.NodeStore.StatementIndex{ .statement = 1 } }, .region = lib_ast.Region{ .start = 0, .end = 0 } }
Yeah, I think the current recommended way in zig is an enum.
The old version was using tuples. (Not sure if those are nominal in zig). Now you switched to strict with unique keys.
Well an enum unifies things into one type of
We are using these to explicitly get different types of
They are basically typed “pointers”
But since they are offsets into an array they can be smaller and offer much better memory locality
Yeah, that is exactly what the zig compiler uses enums for now. Each one of your structs would become an unbounded nominal enum. Each enum would contain all values from 0 to the max u32.
const Parse.Id = enum(u32) { _ };
btw I wanted to note a general thing that @Andrew Kelley pointed out to me when we were talking about arenas:
a downside of using plain bump-allocated arenas for all memory allocation is that resizes basically never happen in-place
like if we push an element and it exceeds capacity, it's not really going to be able to grow in-place because something else will have almost always used the next slot in the arena, so it has to allocate a new array in the arena and copy the existing elements over
something to think about, at any rate!
Are there any data structures that give us in-place memory reuse for free, or is that something we'll have to cook ourselves?
I think we should do a single fixed allocation at boot
Like a single mmap at the beginning to create the backing memory for our allocator
I think it’s FixedBufferAllocator?
How does that fix the problem?
You don’t have to use an Arena
And worry about pointer invalidation on resize
Fixed buffer is an arena last I checked
Ok, but if it’s initialized with a fixed capacity it never resizes
Also, pointer invalidation isn't a problem cause we use indices. The only problem is the growth.
That’s what the fixed means
It isn't the buffer that is resizing. It is the array lists allocated within the buffer
Oh I totally misread Richard’s comment
My apologies
No worries
Also, mmap is still technically a valid solution. We could mmap enough space to store a max sized array list for every array (like one per IR). It would be a crazy huge mmap, but given the memory is virtual should be ok (though k think some system still complain if you make too big of an mmap)
I think if we init our array lists with a very pessimistic capacity we can avoid this (using some empirical heuristic)
Richard Feldman said:
btw I wanted to note a general thing that Andrew Kelley pointed out to me when we were talking about arenas:
a downside of using plain bump-allocated arenas for all memory allocation is that resizes basically never happen in-place
Did he mention what zig does?
TigerBeetle uses the technique you are talking about to run a high availability database
But they use a holistic coding style to make that work well
(In zig)
Did you meet Joran at SYCL @Brendan Hansknecht ?
9A8A65F4-4659-4C81-A8DB-0CC6CEAB2A71.jpg
From their style guide
So you would have in effect fixed arrays and just maintain stack allocated cursors on them
Really reduces the number of trys in your code!
How do we determine the size of said fixed array? What if we try to compile lots of big files? The question seems so obvious that I'm hesitant to ask it
I wouldn’t say that this is necessarily the right choice for a compiler
But just explaining the design space available
To Brendan’s point, I’d be interested in what Zigs own memory management strategy is
Because that one seems to work well with this DoD architecture we seem to be embracing
I know they make some assumptions, and use appendAssumingCapacity a lot from what I read
The only allocation error is OOM, which we can't/shouldn't do anything about. The current approach to minimize try
s is to std.process.exit(1)
on OOM, as is done for you in SafeList
: https://github.com/roc-lang/roc/blob/a3cff5aff7a1cf9584eac6926fba03257d48391f/src/collections/safe_list.zig#L43
You want me to catch every append and call exit?
(name pending, something like TypedIndexList
would be better)
Ok, I think those should both have an initWithCapacity constructor
Agreed
But yes, I think we should catch exit_on_oom
on every allocation
Ok I’d like to hear what others think
But it should be a very rare and extraordinary case regardless of
If we use these “initialize with a constant max size” for these lists, we could just use appendAssumeCapacity and get largely the same behavior
Sorry not constant, but fixed relative to some attribute of the file
Anthony Bullard said:
Did you meet Joran at SYCL Brendan Hansknecht ?
Yes
Anthony Bullard said:
TigerBeetle uses the technique you are talking about to run a high availability database
Not quite
Tiger beetle knows their exact limits and fills up those limits up front
That would be more equivalent to recognizing how much memory a machine has and the allocating it into N different arrays of the max size possible for each of the IRs.
Of course you could decide to use only 2 arrays and keep reusing the memory, but it is a static limit
I was talking about allocating a terrabyte (arbitrary big number) of memory for each array. Way more than the system has. Then keeping track of the current size. The allocation never actually grows, but every once and a while, it page faults to get the os to get more real memory.
Brendan Hansknecht said:
Did he mention what zig does?
a crap ton of ArrayList and AutoArrayHashMap
tokenizer - append tokens to a multi array list
parser - append nodes to a multi array list
zir - append instructions to a multi array list
air - append instructions to a multi array list
mir - append instructions to a multi array list
machine code - append bytes to an array list
intern pool - basically an array hash map
one factor to consider is portability - if your code uses these simple data structures rather than depending on the OS feature of mmap, then you can e.g. run your code in the browser
fun fact, when you're browsing zig's autodocs, you're actually downloading literally a tarball of unmodified zig std lib source code plus a wasm file, and nothing else, and then you're running the actual tokenizer and parser in wasm
Brendan Hansknecht said:
Yeah, I think the current recommended way in zig is an enum.
one nice outcome of using enums is that you can name special values. for instance the trick where you use max int to store "none":
pub const OptionalString = enum(u32) {
none = std.math.maxInt(u32),
_,
pub fn unwrap(i: OptionalString) ?String {
if (i == .none) return null;
return @enumFromInt(@intFromEnum(i));
}
pub fn slice(index: OptionalString, wasm: *const Wasm) ?[:0]const u8 {
return (index.unwrap() orelse return null).slice(wasm);
}
};
pub const String = enum(u32) {
_,
pub fn slice(index: String, wasm: *const Wasm) [:0]const u8 {
const start_slice = wasm.string_bytes.items[@intFromEnum(index)..];
return start_slice[0..mem.indexOfScalar(u8, start_slice, 0).? :0];
}
pub fn toOptional(i: String) OptionalString {
const result: OptionalString = @enumFromInt(@intFromEnum(i));
assert(result != .none);
return result;
}
};
maybe you reserve index 0 to mean empty string, and index 1 to be the string "roc", well you can just put that into the enum then
@Andrew Kelley what would you recommend in terms of allocators when it comes to MultiArrayLists that we're going to build up (potentially involving resizes) with unknown up-front length, but which use indices over pointers for everything, and which we want to serialize straight to disk later (and deserialize straight into an arena)?
an allocator that supports resizing, i.e. not an arena allocator
you can memcpy your array list data to disk independently of the allocator used
since Roc links libc, the libc allocator is going to be your best bet probably for the "gpa" use case, i.e. when you need resizing
lately I've come around to either naming my allocator parameter gpa
or arena
to indicate the intended usage pattern
gpa
- is that the kitchen sink, and arena
is a dedicated purpose built thing we care about storing?
idea is that with gpa
you need to avoid leaking by remembering to free, and with arena
you can fire and forget
trying to do storage serialization at the allocator layer is not something I've experimented with. if you go that route, have fun and I have no advice for you
@Andrew Kelley - I wanted to ask about zig ld
. Would that be reasonable for us to embed in the roc cli binary to use for linking our prebuilt platform hosts and our roc apps together?
Something like zig ld app.o libhost.a
that's actually not a command the compiler supports at the moment, but I think I understand what you're asking - you want to reuse the linker code (not LLD) right?
to understand the use case a bit more, my understanding is that you already depend on llvm libraries in the roc binary - what makes zig's linker code a more attractive option than embedding LLD inside the roc binary, having roc expose roc lld
and then making roc invoke itself as a subprocess?
I guess I'm wondering if there is a simpler way. I thought zig ld
was written in zig and so using that might be a better option than wrangling llvm's lld.
Another option I was thinking was having roc distribute a version of lld that we could download from a release and store in cache.
We have been talking about using a similar approach to Zig with producing llvm bc
so I guess I assumed that meant we didn't need llvm anymore. But I guess @Richard Feldman has mentioned he would like it all in one binary... so we'll still need clang
or something.
yeah we have a macho linker, an elf linker, and a wasm linker all written in zig, however, they do not yet have feature parity or performance parity with LLD
actually I haven't measured the wasm linker perf vs lld since I rewrote it, that might have changed
zig's linkers are also "surgical" if you will, they are designed to be tightly coupled with the frontend and to prioritize zig code updates rather than the use case of only linking objects together
This is for producing a final binary, so as long as the linker isn't too slow (or worse than llvm) it's probably ok. But I'm not sure.
I think the tight coupling aspect will make them not a great fit for directly code sharing with roc compiler
Ok, it sounds like we're back to plan A, embedding llvm things.
have a look yourself and see what you think: https://github.com/ziglang/zig/blob/master/src/link/Wasm.zig
Thank you, but I'm probably not familiar enough with zig or linking to be able to read that just yet. :sweat_smile:
it's certainly adaptable to your use case, but then we'd be maintaining two separate implementations. which, hey, maybe that's not so bad. porting code can be fun and fairly quick
but yeah I think embedding LLD is a more immediate solution to your problem, and does not come with too many downsides since you already depend on LLVM libraries
Would you recommend using a library, or downloading a binary and caching that to use?
^^ I hope that question makes sense...
for shipping a linker?
Yeah, for both compiling llvm bc
and also for linking the final executable
Andrew Kelley said:
to understand the use case a bit more, my understanding is that you already depend on llvm libraries in the roc binary - what makes zig's linker code a more attractive option than embedding LLD inside the roc binary, having roc expose
roc lld
and then making roc invoke itself as a subprocess?
if you do :point_up: instead, then you can ship only 1 binary (roc) that has those other abilities built in
this is what zig does today - basically you copy paste main.cpp from lld into your project and rename main
to lld_main
actually I don't think you have to do that since lld exposes library functions
we do it for clang tho
Ok, I'll checkout the zig code and follow that.
https://github.com/ziglang/zig/blob/b0ed602d5d9358128471588f00a073f2545809fa/src/main.zig#L301-L306
Andrew Kelley said:
tokenizer - append tokens to a multi array list
parser - append nodes to a multi array list
zir - append instructions to a multi array list
air - append instructions to a multi array list
mir - append instructions to a multi array list
machine code - append bytes to an array list
Just to clarify, these all use gpa in your case.
Arena is for temporary non list stuff that never needs to grow
right
Luke Boswell said:
Yeah, for both compiling llvm
bc
and also for linking the final executable
doesn't roc already support this via the llvm library APIs? specifically for compiling bitcode, not linking
I'm not sure how that works. We currently use the inkwell
crate and I assume that bundles in the llvm libraries. But maybe there is some other magic happening there.
Our tokenizer and parser are doing exactly this, and right now using the heap allocator but could easily switch to libc. I think if we upfront make some assumptions about needed capacity resizing won’t hit us too hard
Yep
Also, I would probably use gpa and an arena for now
Currently we don't link libc. And we can generally re-evaluate at any point
Easy to switch an allocator
you don't link libc, but you're planning to link llvm right? that means you will be linking libc
or do you have plans to keep llvm libraries out of the roc binary?
That's true
So I guess we could just go straight to the c sllocator
I thought we had main compiling. From what I can tell, most of it is just broken code with invalid imports and non-existant variables
lazy compilation made it not obvious
I'm working on stuff right now
I don't think it is lazy. It is just that nothing is imported by main.zig
or test.zig
. So they literally aren't in the tree at all
Yes, lazy compilation is imprecise
It's what you said
I'm not sure how best to fix the issue besides importing all modules in main followed by a _ = imported_module
for each of them
Of course, paired with fixing whatever broken imports and such
Yeah, that is a fine start (also, I think just importing the coordinate into main imports everything or nearly everything)
I'm gonna try to get my scope cleanup work done first for canonicalization, and then I can try to fix these issues, and then make a PR
Sounds good.
I think I'll wait for the tree to be working and then switch into doing some various minor changes and cleanups
You might as well wait, I've been touching a lot of minor stuff today
yeah, sounds good
Also, exceptionally minor PR to update the zig-afl-kit dependency: https://github.com/roc-lang/roc/pull/7584
It does seem that Zig does not perform full semantic analysis on dead code.
More work on minor details, started work on scope checking for canonicalization to make sure it fits with everything else, added "coordinate.zig" import to "main.zig" for typechecking: https://github.com/roc-lang/roc/pull/7585
Not complete, just a wash of code
Got everything I need to _blast_ through the parser and formatter on top of a type-safe NodeStore
If you want to see what it would look like to manually construct an AST (which we should almost never do)
any time you have something like &[_]T{...}
, you can shortcut with &.{...}
, as long as there is a result type on the LHS
Sweet! I don’t know why I didn’t try that
@Sam Mohr, not sure this is useful to you now, but we could add a step in CI to do find src -name "*.zig" | xargs -n1 zig ast-check
. It would ensure that all of the zig files that aren't in the tree are at least internally valid. That said, I would assume that pretty quickly everything will be in the tree, so this may not matter.
I have time right now, so just trying to figure out if I can do something useful.
I think it's fine right now. I think what would be helpful is seeing if you can skeleton out what the interpreter and/or the LLVM backend would need for inputs
I'm working on setting up the coordinate.zig file right now so that everything is actually glued together
I've at least putatively set up scope checking logic already for canonicalization (not plugged in), meaning I'm pretty confident we'll be okay with the new ModuleIdent approach (formerly Symbol) for referencing idents that Richard proposed
If you can skeleton out what the interpreter
I feel like that may be hard to do without a Can IR. I plan to start by having this as a tree walking interpreter that just directly walks Can (maybe 1 level removed from can to do some type checking first with the concrete input types)
LLVM backend
This I definitely should look into more. Need to figure out zigs library to build llvm bitcode and also statically linking to llvm in general (which might be pretty hard)
Once I finish the package stuff, I'll see if I can get the CanIR at least mostly correct
Another super minor PR: https://github.com/roc-lang/roc/pull/7588
but a bit bigger this time
Approved, auto-merge enabled
Your PR is also the first time I've seen a greentext in Roc's ecosystem, nice
Brendan Hansknecht said:
Sam Mohr, not sure this is useful to you now, but we could add a step in CI to do
find src -name "*.zig" | xargs -n1 zig ast-check
. It would ensure that all of the zig files that aren't in the tree are at least internally valid. That said, I would assume that pretty quickly everything will be in the tree, so this may not matter.
zig fmt src --check --ast-check
We should add that to CI once we get all our source cleaned up. Thanks!
To add --ast-check
. Fails currently, but I want to make sure we don't forget about it later: https://github.com/roc-lang/roc/pull/7589
Correctly get the github ci filter working: https://github.com/roc-lang/roc/pull/7591
new gpa! https://ziglang.org/devlog/2025/#2025-02-07
That's cool. Though isn't the libc allocator just b tier? Like the good allocators are like mimalloc and tcmalloc?
Not trying to downplay anything, huge for the zig default to at least match C (while also having options to detect for memory leaks and such). Just noting that there are a lot of allocators out there and I don't think libc has been state of the art for a long time.
Also, I'm really curious how it compares to the jdz zig allocator: https://github.com/joadnacer/jdz_allocator
Also, does this mean it is in in time for 0.14.0?
Brendan Hansknecht said:
Correctly get the github ci filter working: https://github.com/roc-lang/roc/pull/7591
Or not...try 2: https://github.com/roc-lang/roc/pull/7592
Yay! only zig ci running: https://github.com/roc-lang/roc/pull/7590
Also above PR just adds a script to enable reproing fuzzing failures.
Brendan Hansknecht said:
Yay! only zig ci running: https://github.com/roc-lang/roc/pull/7590
I was testing it too :) https://github.com/roc-lang/roc/pull/7593
Currently CI is now ~3 minutes....why is windows so much slower than all the rest of CI?
To be fair 1m21s was for downloading to our cache for the Windows Zig install
But still
To be fair 1m21s was for downloading to our cache for the Windows Zig install
So on rerun, this should be skipped? let me test
Ok, a bit better
btw if you don't mind using https://github.com/mlugg/setup-zig instead of goto-bus-stop (which is now unmaintained) it will use mirrors and proper caching. should be faster for you and less bandwidth for ziglang.org
Yeah, we can definitely switch over
PR to switch: https://github.com/roc-lang/roc/pull/7594
Ok, I have the first draft of the parser able to parse AND format the canonical Hello World. I need to rebase it on the current structure and then probably make a few more changes to harmonize it with the rest of the project
The rest of the parser should be able to go _VERY_ fast from here
Exciting. I'm definitely interested in helping get a fuzzer setup once it lands
I'll have a PR up by tomorrow evening
By that I mean, if no one does it first, I'll add a parser to formatter fuzzer following the current format after your PR lands
I made a lot of mistakes and did a few redesigns. I also feel like I type like molasses with Zig, guess I'm just getting used to the syntax (and cursing everytime I forget the .
in front of an anonymous struct)
I know the feeling
But I'm very happy with this current design, even if there are some tools (i.e., helpers) that need to be built to make the actual parsing code more quickly scannable - but I didn't want to abstract too early in the game.
A good policy
Also, I'm going to be upfront - this initial version will have in it a LOT of panics (where problems should be reported, and unimplemented code paths). I do not intend to commit the PR that way, but I wanted to talk about how to do problems effectively (and Malformed) before I replace them in the PR review.
any plans to do snapshot testing for the parser? I think sometimes people call them golden tests? basically just like debug print the ast to a file and compare against it on the next run
#compiler development > zig compiler - snapshot testing
@panic("TODO")
ftw
@Andrew Kelley This is the way
I'm going to put up my PR. But first, should I try linking it into main.zig at all (even in it's very partially implemented state, and even though there is no further analysis being done)?
Fire away please! https://github.com/roc-lang/roc/pull/7597
And yes, I'm going to be looking at:
If you don't link it to main, make sure it at least passes zig fmt --check --ast-check
Oh, just realized that the tree is valid now. Can we merge https://github.com/roc-lang/roc/pull/7589 to protect it more from future breaks?
Done
I was waiting to see if anyone wanted to claim the fun one... but it seems to be still open for the taking. :smiley:
I'd like to take responsibility for the type-checker.
Me and my mate Claude have some reading to do on HM type inference... but we have a nice implementation to follow.
Hell yes, please take the hard work
Wait.. you said type-checking was the easy one
Talk to @Lucas Rosa, he was also interested because of his experience
It's not bad once you understand what's happening
I'd recommend reading through the current solve
and unify
crates in the Rust code
@Luke Boswell go for it, you have my support, just remember that constraint solving part, it's important for the quality of error messages :)
I also have access to OG lang PhDs that we can ask questions to, like Kent from chez scheme, also I could ask philip wadler questions probably, not sure how responsive he is but I share a slack with him.
just ping me and I can pretty much jump online to pair program about it at any time. the basics of HM type inference are straight forward and well understood for decades. definitely make sure you review solve and unify, those are the main show for this. a little bit of can
reading wouldn't hurt either
Thank you.
I will be watching with keen interest Luke
And I can also tell you what NOT to do :rofl:
it's not unlike an interpreter, you walk the tree, assign type vars to things, primitives and annotations are like the terminal points from which everything resolves upwards from
the only things you might not see in intro material is the extensible records stuff (basically row polymorphism if I'm not messing up terms)
and the tags which are like ocaml polymorphic variants (assuming that hasn't changed)
I also recently did the exhaustive matrix check thingy for matches so that's still fresh in my head
My plan is to approach it from both sides at once... spend roughly 50% of my time learning the theory, and the other following the rust impl.
let me find you a paper for exhaustiveness, I'm pretty sure it's where elm got it's algo from, I lifted it from elm myself as well
I think this is it
https://www.cambridge.org/core/services/aop-cambridge-core/content/view/3165B75113781E2431E3856972940347/S0956796807006223a.pdf/warnings-for-pattern-matching.pdf
also available here in web form on some subdomain on inrias website
http://moscova.inria.fr/~maranget/papers/warn/index.html
here is the elm implementation, also a remarkable reference because the code is some of the cleanest haskell code I've ever seen
https://github.com/elm/compiler/blob/master/compiler/src/Nitpick/PatternMatches.hs
along with my very ugly rust port of the exact algo
https://github.com/aiken-lang/aiken/blob/main/crates/aiken-lang/src/tipo/exhaustive.rs
The existing Roc implementation works very well, I think we should basically try to transcribe it in Zig terms
It was also lifted from elm, so I assumed he would look at the roc impl but I wanted to link him more sources
of note, the "demanded" enum for records isn't necessary anymore due to optional record fields going away
ah cool, good to know
optional record fields going away
single tear. I'll miss default value function arguments
Yeah, what replaces that? Is there another way to do it?
I've used them extensively in plume for example
Terse builders
That thing i did for Weaver... let me grab a link
Ahk.. I remember now. The builder pattern
https://gist.github.com/smores56/dc7b37f73114df11d28cd6a148987dea#file-weaver-builders-roc
I noticed that yesterday, pipe is replaced with .
? not a bad idea at all
That's static dispatch
oh I see, I went back and actually paid attention to the proposal
There it is! Pass the value in front of the dot to that function as its first argument, and we're done. (If the Result module did not define a top-level mapErr, or if we couldn't have accessed it in this module because it wasn't exposed, we'd get a compile-time error.)
sorry, still catching up to the most recent design
"In this design, the API is literally all there is to consider—exactly as it should be!" - some chad probably
"[-2, 0, 2].map(.abs().sub(1))" omg this is insane, didn't realize this could look so clean
I still think default valued args are super useful, but optionals and builder patterns are okish alternatives.
Yeah, I guess the hypothesis we are testing is can we get away without them. One more language feature we don't need to think about -- i.e. simplifies roc
yep
random other notes I just thought of (or really, Loris reminded me of).
Debug assertions are our friends. Please feel free to add std.debug.assert
to your code. They will all be ripped out in the final release binaries, but they are great anchors for fuzzing and for testing in general.
https://github.com/kristoff-it/zig-lsp-kit
I figure most say this already, but just in case. this could be useful
Adding llvm feels so painful. RIP binary size (will be great when we add an interpreter only config).
Debug
840K -> 114M
ReleaseFast strip
72k -> 9M
This is all without actually using any llvm. This is simply linking to a c++ file and statically compiled llvm, not actually using anything yet.
A necessary cost, it seems
I really surprised that release fast with strip grows by so much when we literally don't use any of it. That said, it will grow by much more than that once we start using things.
but yeah, statically compiled release builds of llvm and lld together are 201MB. So if we reference absolutely everything our compiler would be that big.
Which is why zig is like 270MB in size (note, zig also packages clang which we won't)
It would be really nice to go the same route as zig and take LLVM out of the compiler binary. I know we want everything to be a single binary, but could we instead have some tooling in the cli which makes it easy to install LLVM or setup the right thing if it's not already available in the system.
Do you mean the same route as cargo
?
Just spitballing here -- I'm thinking it might be good to map out the intended use cases or some scenarios of people using roc and figure out when we think we need a fully statically linked thing that includes LLVM, and are there other ways we could make that seamless.
Yeah, theoretically we could emit a .bc
file or run the interpretter (super slim). Then we could orchestrate llvm to actually compile. On first run, would just download our llvm compiler to the cache.
That said, I think for most users, this just means instead of downloading llvm now, they download it in a few days when they make an optimized build
So not really that much of gain in my mind.
Just hidden on first compilation
It also means upgrading roc... may use the same LLVM compiler and switching between roc versions may not need to download it again -- just use the one we saved in the roc cache
Oh, yeah, that is fair.
less often that you need to update the llvm bundle potentially
Roc compiler without LLVM bundled might be a couple of MBs (maybe even smaller?)... so it would be almost free to have every version in the roc cache.
In fact, assuming we generate an old version of bitcode, you potentially could lazily update much later. Like just use llvm 18 for a few years then jump to llvm 22.
Unless there is a significant performance gain from upgrading to 22 (for example) which we can easily measure... then we may not even need to.
I have zero anything to base that on though
Long term this is definitely something we should explore.
I was thinking short-medium term... it would help us with the development process to be able to manage multiple versions seamlessly -- the roc cli upgrades and downgrades itself
I think simply generating bitcode files already will give us a lot of flexibility. Still will depend on a few c apis from llvm, but they are the much more stable high level apis.
What is the size impact if we only have LLD linked?
should be around 10MB
Maybe less
Seems like bundling LLVM as well will be easier to get right for now. Would we be okay with starting with that and then pulling LLVM out later?
I think we should prioritize features that get us a working compiler first, and a fast one later
But if it's gonna be a fun project to get this working, then by all means
Also, to begin with, for the interpreter path, we will still need llvm.
Cause we need to generate the shims
probably could manually generate those at some point if we want.
Could the shim be prebuilt?
hmm... possibly could be. I guess it is static to the platform. So the platform could provide an extra shim object file per platform.
Like roc serialises ResolveIR, the interpreter shim is prebuilt and parses that before it starts doing it's interpreter thing...
But I guess this doesn't work because it needs to know what shape to satisfy the platform hosts API.
It's worth trying.
Oh yeah.... that was the idea -- the platform provides a prebuilt interpreter
I remember we discussed that
Not a prebuilt interpretter, just a prebuilt shim object file
Hmm, though the platform doesn't know the file locations of the final app which is need for the shim to know what to load.
Cause the shim essentially needs to provide the intepretter with the app main.roc
path, the name of the entrypoint being called, a return pointer, and a list of argument pointers. The interpreter can then learn the types of each pointer by reading the roc source code.
Anyway, I plan to get the interpreter working with shim and such before starting the llvm backend. So that will give us more concrete ideas here.
For now, I am just adding the wiring for llvm, I will leave it commented out in the build script to avoid the giant binaries until we have an llvm backend.
we should consider having the llvm backend only in the build if you enable a flag
bc the majority of compiler development won't need it and will be faster without it
and then we could instead build in something which just panics every time you call it saying "this compiler wasn't built with llvm, please rebuild with that env var set to use this feature"
the majority of compiler development won't need it
I wonder how well we can work on backend passes without llvm
We just have to validate their output
We can do that for at least simple cases with unit testing/fuzzing
But yes, the LLVM codegen side will be trickier
I mean theoretically we will even be able to generate .bc files without llvm
So it really is just for the final exe
Oh, I thought by "I wonder how well" you were implying "I'm not confident we can do a good job"
I agree
I guess we can run all snapshot tests without llvm, so that is nice anchor.
like we can generate refcounting ir and lower ir.
Roc successfully cross compiling to all major targets with llvm (as static as possible): https://github.com/roc-lang/roc/actions/runs/13321631348/job/37207263318?pr=7603
yoooooooooooo
for what it's worth, zig built in ReleaseSmall mode without llvm is 12M
and I think it's interesting to note that includes a full x86 backend, C backend, llvm (bitcode) backend, wasm backend, riscv64 backend, elf linker, coff linker, wasm linker. the only thing it lacks compared to llvm is a few more targets and optimization passes
4 messages were moved from this topic to #compiler development > zig compiler - fuzzing by Brendan Hansknecht.
Does anyone have any recommendations for debug printing with zig?
I want to debug print in tests.. but only if the test fails
std.log.debug
and std.log.info
do not show up in zig test
output
did you set the log level?
pub const std_options = .{
.log_level = .debug,
};
Is that in the module I'm testing or the tests.zig
file?
I think once in test.zig
should work. It should be a global flag to my understanding
Otherwise, maybe just std.debug.print
after checking for failure?
I'm not really sure best practice here
Yeah, me either. I've been researching and trying different things. But haven't found a reasonable solution yet.
Basically... I have all these test scenarios for unification etc... and they can print out useful debug info for each step. I only want to see that for the tests that fail though.
Maybe I should be thinking about snapshots at this point instead though
Hey... I got something working. Builds a snapshot test file using debug prints.
Just in case you didn't already read this: https://kristoff.it/blog/dead-simple-snapshot-testing/
Would it be a bad idea to give a Type Variable a comptime optional "name" to help with debug printing?
I'd like to have pretty greek letters for my snapshots tests instead of having random integers everywhere
Why not convert integers to characters on print for the snapshot test?
Ooh, that's a nicer idea
I've almost got something working.. I might just keep going with this thought before trying that
I went ahead and rebased @Anthony Bullard 's parser PR and fixed some bugs: https://github.com/roc-lang/roc/pull/7609
(would like to get that landed soon so we can iterate on it)
I'm happy to approve to unblock after the tests are fixed
Very puzzled at the current failure
Is it possible that CI box has run out of disk space or something?
That is what it looks like, which is pretty confusing cause it is a GitHub runner. Should have a blank slate every time
We use our own runners, right?
Not here I don't think. I think this are vanilla GitHub runners
But maybe that is wrong
@Joshua Warner can you rebase on latest main and run again. I just merged something that changed test steps a bit. Not saying it will fix anything, but might give more info.
No change, looks like
Really confusing that cross compiling with -Dllvm
works, but somehow regular compiling does not....
I guess it could be related to -Dllvm
combined with -Dfuzz
for some reason.
Removing -Dllvm seems to work
Maybe it'd be better to remove -Dfuzz?
nah, -Dllvm
doesn't actually do anything useful currently
Still very puzzled as to what's going on
Could be out of disk space, but should have 14GB, so a bit surprising
llvm is only like 300MB or so
even if it gets duplicated for ever executable, it should be no where near 14GB
Also, why would it break on this PR specifically...hmm
Hmm; added a call to df -h
and of course now it works
You still don't have -Dllvm
Oh whoops
Probably not disk space:
/dev/root 72G 46G 26G 64% /
is it only failing on ubuntu-24.04?
Yep :/
Can we try ubuntu-22.04
just to see?
I have no immediate ideas, probably would need to pull up a linux machine and test.
It works on ubuntu-22.04 :shrug:
Send it and worry about it later.
Might be some weird GitHub CI bug
Luke Boswell said:
I want to debug print in tests.. but only if the test fails
oh yeah I've been meaning to make what you want be the default thing
tracking issue: https://github.com/ziglang/zig/issues/5738
A message was moved from this topic to #compiler development > zig compiler - builtins by Luke Boswell.
Good watch on some zig patterns like comptime interfaces. Discussed a handful of useful ideas: https://youtu.be/l_qY2p0OH9A?t=1920&si=gzHTwuGTYRWoDQlS
Implemented some functionality in the old formatter to support migrating to the new braces syntax: https://github.com/roc-lang/roc/pull/7619
There are almost certainly bugs hiding in the formatting here, since I'm not really doing any verification on it. I'd like to assert that the new parser parses all of these inputs (or we add more "NotSupported" errors as appropriate).
@Anthony Bullard that PR also contains *.migrated.roc files, which should hopefully serve as useful test inputs for the new parser.
I wanted to understand the plan to wire up the compiler stages. I've put together this simplified diagram that I think captures some of the key features - with the help of Sam.
Roc Compiler Stages - Environments.pdf
Some key points to summarise
I thought we don't have cyclic dependencies
So no module sets?
Though maybe type variables or static dispatch change this?
We didn't used to have them, but we'd like to see if we can make cyclic dependencies work
The reason is because you might have two custom types that depend on each other (we expect this for DB constructs) and they both need to define a to_str
Oh, interesting. Are there restrictions?
They can't do that in the same file
Currently, the plan is to have them give a warning about compilation speed if it's not necessary
And "necessary" means the modules have custom types that depend on each other
yeah, basically the idea is that if you have two nominal tag unions that are mutually recursive, and you also want them to have static dispatch (which could come up when modeling database tables, for example) that's currently impossible
so if we do this, then all the modules in the cycle basically get type-checked as one big unit
which is worse for both concurrency and caching granularity
so it's kind of a perf footgun unless you're specifically using it to resolve the thing that's currently impossible
e.g. if you're not careful, one wrong import
can accidentally make your entire project into one big cycle that can't be parallelized at all anymore
so the warning would be basically "you have a cycle involving modules that don't expose mutually recursive types, so you should break it up!"
that way you get equivalent perf to today
because the only cycles are between modules that have mutually recursive types, which is also true today (where you have to just literally put them in the same module instead)
as a bonus, it's also nice for "always report, never block"
in that if you find yourself in a spot where you import something and it causes a cycle, you aren't blocked - you can do that, and still run your program
and maybe confirm whether you want to keep that architecture before cleaning up the cycle later
What if you end up being unsure how to break up the cycle and want to just leave it be. Will you be stuck with roc reporting failures in CI?
That's the current plan. You can always remove it by putting the cycle in a single file, but even more, since the cycle will be immediately obvious on creation, this will be an annoyance that will be early to see in at least most cases
I'd rather we not allow cyclic imports to prevent this from even being an issue, but the aforementioned custom types scenario doesn't seem to have a better solution
Yeah, I just find it strange partially allowing it
Sounds painful potentially
btw can I get Roc compiler developers' opinions about this? https://github.com/ziglang/zig/pull/22137
do you prefer status quo names or the names proposed in this PR?
I think the old wording is definitely clearer. I don't have to guess at all. That said, you only have to learn once, so the new wording is fine overall.
I wish ensureReserved worked, I think it's nicer than reserveUnused. I guess appendReserved works.
Not familiar with the zig std, so I don't know if there are inconsistencies, but the original wording communicates intent better. To me, even appendAssumeCapacity
is more clean than appendReserved
, though not by much.
Thanks!
@Joshua Warner @Anthony Bullard
Could you please make a single unit test or something that produces a minimal parse.IR
.
Like are we at the point we're the IR could represents this?
module [name]
name = "Luke"
This would be really helpful for working on Can. We're just not sure how to work with the ParseIR rn.
Just the output -- hardcoded is ok if we don't have the parser implementation this far yet.
I'm trying to make something like this... but definitely not right
test "Example Can IR" {
// Imagine we received a parse.IR representing the following roc module
const source =
\\module [name]
\\
\\name = "Luke"
;
const parse_ir = parse.IR{
.source = source,
.tokens = parse.TokenizedBuffer.init(std.testing.allocator),
.store = parse.NodeStore.init(std.testing.allocator),
.errors = .{},
};
var can_ir = IR.init(std.testing.allocator);
// We called "canonicalize" and
canonicalize(&can_ir, &parse_ir, std.testing.allocator);
}
I think it'd be nice to have these fields added to the parse.IR
:
header: NodeStore.Header
statements: std.ArrayList(NodeStore.Statement)
Or something like those, as that would unblock canonicalization
For now, I'm just pretending those exist and using dummy values
something I always wished we had in the Rust code base was having every single test suite start with normal Roc source code as the input
I think to do that, we'd need test helpers for each step that build on the previous step's helper
I presume you're thinking of something like what @Agus Zubiaga started setting up for the test_compile
crate: https://github.com/roc-lang/roc/blob/26f9416929aa0cd52ca732fc533b4a94a690de04/crates/test_compile/src/help_constrain.rs#L29
Richard Feldman said:
something I always wished we had in the Rust code base was having every single test suite start with normal Roc source code as the input
I would like this.
Im currently just trying to get my head around the IRs in a really minimal sense. Not suggesting we make unit tests like this.
Richard Feldman said:
something I always wished we had in the Rust code base was having every single test suite start with normal Roc source code as the input
I think many tests can be that way, but it also can make things more brittle to changes higher up the stack. Also can make it harder to write some of the low level optimization steps.
That said..I think that is what the super snapshot test framework is for
I really think we need to get the base of snapshots working with parse and can. Then slowly work it down the stack
Brendan Hansknecht said:
Richard Feldman said:
something I always wished we had in the Rust code base was having every single test suite start with normal Roc source code as the input
I think many tests can be that way, but it also can make things more brittle to changes higher up the stack.
I agree, but I think it's worth it :big_smile:
like I spent a lot of time in tests trying to build IRs from scratch and then taking even more time to try to figure out if they were correct
also I know there were tests I wouldn't write just because setting up the IRs was too tricky, but starting from scratch it wouldn't have been
so I think the brittleness to upstream changes is worth it
@Sam Mohr the reason I'd like not to just directly have a header/statements is I want this to be able to directly parse individual expressions both for testing and for repl evaluation
Richard Feldman said:
like I spent a lot of time in tests trying to build IRs from scratch
Yeah, this is a fundamental problem
I assume if every ir can be printed and parsed, it will reduce this pain a lot
I'm not saying all tests should start from source code btw, but rather that each stage should have at least some tests that are that way
Yeah, I think we want a comprehensive library of snapshot tests and they should run through every single ir
and that means we're set up to do them, and can reach for that whenever we want
100%
For the immediate short term, while we figure out what is and isnt in each IR / Env -- I'm hoping we can make a couple of simple hardcoded examples fur the purpose of seeing what the IR actually looks like and how we might use it.
I'm just having trouble piecing everything together and getting familiar with the representations like SoA etc
Before we have spent much time on implementing things, we might pick up on fundamental design/arch issues, and it's easier to change course now.
Like are we allowing cyclic imports or not... that seems kind of helpful to have a rough plan for now. <-- just an example of a discussion that has spun out of recent efforts to build out the API
Richard Feldman said:
yeah, basically the idea is that if you have two nominal tag unions that are mutually recursive, and you also want them to have static dispatch (which could come up when modeling database tables, for example) that's currently impossible
so I thought about this some more, and I think it's better if we continue to disallow cyclic imports and recommend this workaround if anyone actually needs mutually recursive nominal types with static dispatch:
A
and B
) in the same module, let's call it AandB.roc
A.roc
and B.roc
modules, each of which imports AandB.roc
onlyA.roc
and B.roc
exposes a nominal type which wraps the appropriate mutually recursive type inside AandB.roc
, and exposes all the desired methods on thoseA.roc
and B.roc
can each provide a to_inner
function which returns the underlying nominal type from AandB
. Static dispatch won't be available on this structure, but that's okay because the wrapper does.the tradeoffs of this compared to allowing cyclic imports and doing a warning:
So if you want to be able to call some external use_special_method : a -> Str where a.special_method() -> Str
on A
or B
, you can't?
I'm not sure how bad that limitation is
Especially for the auto-genned methods like to_str
and encode
I probably should have chosen better names
Yeah, they're tripping me up :sweat_smile:
let's say A.roc
exposes ExternalA
and that's a wrapper around InternalA
from AandB.roc
so InternalA
is mutually recursive with InnerB
InternalA
and InternalB
are both in AandB.roc
and ExternalA
wraps InternalA
and imports AandB.roc
but that's it
so you can do static dispatch on ExternalA
(which just operates on its wrapped InternalA
for you)
and then you can call to_inner : ExternalA -> InternalA
if you want to pattern match on it
(or maybe some things would make ExternalA
opaque and not expose a to_inner
- that's fine too)
Yeah, okay, that's a fine limitation
so you can't dispatch directly on InnerA
but that's fine because you can static dispatch on the ExternalA
wrapper around it instead
yeah, it's definitely an ergonomic downside
but you can still do everything
As long as its only ergonomics
We force the same tradeoff elsewhere, e.g. unicode stuff
It's good that Roc is opinionated
yeah I mean if you have a bunch of these that are all mutually recursive, you could end up with some gigantic QueriesInner.roc
or whatever
but what I realized is that if we allow cyclic imports, the compiler still ends up effectively dealing with that file - except it's even more work for the compiler, because first it has to staple together several cyclically imported modules into one gigantic module
Roc is a high-level language because we want to do stuff for you automatically you'd do anyway, right?
so on the one hand, arguably the ergonomics are better for the programmer because the modules are smaller, but on the other hand, there's something I do appreciate about like "hey these things are all tangled together into one big chunk" not being hidden from the programmer
So I'm more convinced by the "make it awkward to force better organization" argument
well, it really comes down to whether there are use cases where a ton of mutually recursive types is actually the best way to write the code
Do we allow any recursion at all outside of custom unions?
I am somewhat skeptical that those use cases really exist, but I also don't think I've really explored the space of representing the outputs of database queries that involve joins, nested queries, etc. using Roc's type system
Sam Mohr said:
Do we allow any recursion at all outside of custom unions?
not anymore
What about Tree a : [Leaf a, Cons (List (Tree a))]
although we do want to allow it within lists
yeah we never supported that, but always should have :sweat_smile:
lol yep
same with sets and dictionaries
Anything list-backed, yep (or Zig-list backed, distinct from written in a Roc-native list)
we used to support it in structural tag unions, but decided to stop because of https://github.com/roc-lang/rfcs/pull/1
So then, I'm gonna finish up the coordinate.zig
work I was doing to implement this, but get rid of ModuleSet
and move towards sequential module ID assignment for post-cache work. Sound good?
This doesn't feel like we need a big discussion
sounds good!
awesome
I'm really glad we've gone this direction.
I still really think we should support this without requiring custom tags if possible:
Tree a : { data: a, children: List a }
Just recursion through list. Cause that covers dict and set as well
That seems to be what we are agreeing on above
Oh, you still wrapped it in a tag
Oh, good point
Hmm
I want it completely tag free
Should be fine
List always breaks recursions.
Yep
Luke Boswell said:
Joshua Warner Anthony Bullard
Could you please make a single unit test or something that produces a minimal
parse.IR
.Like are we at the point we're the IR could represents this?
module [name] name = "Luke"
This would be really helpful for working on Can. We're just not sure how to work with the ParseIR rn.
If you need this right now, I can add parsing a plain module header to my PR
Everything else should work
@Sam Mohr header and statements do exist. If you get a file, it has this shape:
pub const File = struct {
header: HeaderIdx,
statements: []const StatementIdx,
region: Region,
};
You just need to run ast.store.getFile()
to get it
Another passing note, I am at the point where I want to start lazily creating the Parse IR display format, because I think it'll be useful for debugging for me
So I get:
(file (app (main!) "pf" ".../platform.roc" ()) (
(import "Stdout" "pf")
(decl (ident "main!") (
(expr (apply (ident "line!" "Stdout") ((string "Hello, world!")))))))
Maybe with the region as a (START END)
sexpr after the tag.
@Anthony Bullard We were discussing this in #compiler development > zig compiler - IR serde . The relevant part of that topic is that all IRs would have a way to get turned into S-expression nodes, which then would be serializable to string. Similarly (but less relevant to you), we would have 1 S-expression parser that would take in a string and turn that into a node, which then could be translated into any of the IR-s. That way the pretty printing and parsing could be in 1 place.
Okay, we can start running with that for canonicalization. The remaining thing is alignment of Region
structs. Maybe we can just use the parse.IR.Region
(source) everywhere and expect that to update when necessary? @Anthony Bullard would you think that a bad idea?
I think it's actually worth trying to use a parser node id as a region
That's a single u32, which is nice
What if a region is for a function body?
Then use the node that corresponds specifically to the body :)
Okay, yeah
I think that could work
All we'd need to do is ensure that all diagnostics we'd want to show would be traceable to such a parser node
But for the same source code and the same Roc compiler version, that's free
I'd love to make an alias so that we aren't just passing around Parser.NodeStore.Idx
or whatever the actual thing is called
Not sure what to call it
maybe
pub const ParseRegion = struct {
node_id: Parser.NodeStore.Idx,
};
Joshua Warner said:
I think it's actually worth trying to use a parser node id as a region
Then for caching, we have to serialize both the parse and can ir?
My thinking is to not write that out, but rather re-generate it on demand if we ever need to emit errors for that file.
(I'm a little unsure of what this means about things like debug info, where resolving line:col info is in the hot path)
I kinda want to say we should not emit traditional debug info unless asked, and by default we should have some faster-to-generate thing.
I think it is reasonable to say that optimized llvm builds (which likely will be the default llvm builds) don't emit debug info or emit very limited debug info.
yeah the interpreter seems like it would reduce demand for debuginfo a lot
Of course need to be able to opt in for llvm optimized builds with full debug info
eventually yeah, but not a hard requirement for 0.1.0 I don't think
And I think dev llvm builds should have full debug info (but the interpreter will make those rarer)
Richard Feldman said:
eventually yeah, but not a hard requirement for 0.1.0 I don't think
It think I might try to add in full debug info on first build of the llvm backend. I think it is the kind of work that can be painful to add later.
awesome!
Sorry, why a single parser/writer for all IR display formats? I don't know how well those will work together....
But I'm happy to see it if it does!
My (perhaps unfounded) assumption is that there will be some useful commonality to extract there, but I could be wrong.
In particular I was thinking about things like pretty-printing the s-expr, which if you want to have a reasonably dense format that doesn't take up a bunch of vertical space, is non-trivial
I'm ambivalent as to whether that takes the form of a bunch of utilities that are used adhoc by different IRs, or a system where you convert the IR to/from some s-expr nodes which are then processed
I've made a zig library to help parse and generate S-expression. Just wanted to let people know that I've started on this. Haven't wired it up with any of our actual IR's yet.
@Norbert Hajagos and I will polish it later today and I'll make a PR to share it.
Here's a snippet of what I've got so far
/// Represents a token in an S-expression.
///
/// This type is comptime generic over two types: `T` for identifiers and `V` for values.
pub fn Token(comptime T: type, comptime V: type) type {
return union(enum) {
ident: T,
value: V,
lparen,
rparen,
};
}
Do we want to use an arg parsing library for the CLI or roll it ourselves? I remember hearing talk of wanting to use very few third party libraries.
roll it ourselves!
as I believe @Andrew Kelley has said, "just write a parser for cli args"
We currently have one I wrote that is super simple
https://github.com/roc-lang/roc/blob/7fc2a08e2811fed7207ab5035f680bbf697d232f/src/cli.zig#L54
Probably could do with some love though
Okay sweet. I'm going to take a look at wiring up the formatter in the CLI and wanted to confirm the approach
Thank you Isaac! I'd love to get that so I can start writing files straight-up and running the formatter on it
Some string tokenizing + parsing updates: https://github.com/roc-lang/roc/pull/7632
Type Annotation and Declaration parsing and formatting: https://github.com/roc-lang/roc/pull/7633
I got most of Type.Store
(new Subs
) working today. I’m gonna work on unifying primitives tomorrow!
haven't disappeared, have been reading almost every message. just letting people cook, lots of chefs already :D
honestly, the speed at which this is moving needs to be studied, extremely impressive. ya'll are making what seems like a gargantuan effort look like a weekend project
Definitely moving well, but still tons to do. That said, I do agree that it might be hard to fully parallelize to more folks right now. Mostly things at the top of the stack are moving right now.
yea it's all good, I'll sneak something in eventually, I'm not here for personal glory :D
I'm trying to update my SExpr PR so I can land what I have, and am running into some issues with memory leaks/issues in the formatting tests.
One somewhat related question... should the SafeMultiList hold onto the allocator? why do we do that?
pub fn SafeMultiList(comptime T: type) type {
return struct {
items: std.MultiArrayList(T),
allocator: std.mem.Allocator,
I'm looking at this error trace from a test and it points to the store.nodes.deinit()
as the source of the problem.
thread 415308 panic: integer overflow
/opt/homebrew/Cellar/zig/0.13.0/lib/zig/std/multi_array_list.zig:540:31: 0x103032c37 in capacityInBytes (test)
return elem_bytes * capacity;
^
/opt/homebrew/Cellar/zig/0.13.0/lib/zig/std/multi_array_list.zig:544:49: 0x103032c7b in allocatedBytes (test)
return self.bytes[0..capacityInBytes(self.capacity)];
^
/opt/homebrew/Cellar/zig/0.13.0/lib/zig/std/multi_array_list.zig:177:41: 0x10303122f in deinit (test)
gpa.free(self.allocatedBytes());
^
/Users/luke/Documents/GitHub/roc/src/collections/safe_list.zig:132:30: 0x102ff531b in deinit (test)
self.items.deinit(self.allocator);
^
/Users/luke/Documents/GitHub/roc/src/check/parse/IR.zig:475:27: 0x102fa3ea3 in deinit (test)
store.nodes.deinit();
My suspicion is that maybe we are passing it a different allocator somehow... and so it's trying to free memory that isn't there or something.
If anyone would like to take a look I pushed a commit for the above error https://github.com/roc-lang/roc/pull/7629/commits/6f641a7ee9a3e1c850643c44ef988774b62babc6
Luke Boswell said:
My suspicion is that maybe we are passing it a different allocator somehow... and so it's trying to free memory that isn't there or something.
The error is an overflow when calculating the capacity. That should be before any sort of allocator interactions. Probably would be good to print out the capacity and element size in bytes before that call to see what they are.
Luke Boswell said:
One somewhat related question... should the SafeMultiList hold onto the allocator? why do we do that?
pub fn SafeMultiList(comptime T: type) type { return struct { items: std.MultiArrayList(T), allocator: std.mem.Allocator,
MultiArrayList stores the allocator, so we should not need to.
One possibility is that we deallocate out of order and that leads to reading a garbage capacity from freed memory. That or the equivalent but via a stack allocation
I should be able to pull this later today and take a deeper look
If you could that would be helpful. I'm very lost staring at these errors in the zig stdlib
I feel like building the SExpr I'm bumping into issues that we're not aware of just because I'm wiring things up for the first time.
@Luke Boswell I think I have everything you need in PR comments
me trying to resist making SExpr-based jokes in this channel
Luke Boswell said:
I'm looking at this error trace from a test and it points to the
store.nodes.deinit()
as the source of the problem.thread 415308 panic: integer overflow /opt/homebrew/Cellar/zig/0.13.0/lib/zig/std/multi_array_list.zig:540:31: 0x103032c37 in capacityInBytes (test) return elem_bytes * capacity; ^
If this happens in debug mode, it's often because one of the operands is undefined. In zig, when you assign something to undefined (for example by freeing memory), the bytes are memset to 0xaa
. This has some nice properties, including the fact that if you multiply by an integer even as small as 2
you get overflow.
in other words, I would expect that stack trace if you called safe_list deinit() twice
fear not, for this is checked illegal behavior, which is deterministic and straightforward to debug
Yeah, was great for catching the double free. Just not the clearest error message
What are general thoughts on always using Unmanaged
datastructures?
Unmanaged just means that they do not store a pointer to an allocator. Instead the allocator must be passed in on for all functions that might allocate/deallocate.
Fundamentally, I don't think it is a big change. Just a minor api change. It likely isn't too important of a change, but avoids storing lots of extra copies of pointers to the allocator. Instead we just store one copy of the pointer to the allocator and pass it down the stack.
Seems to fit nicely with how we are designing datastructures.
@Brendan Hansknecht I think I've got all the coordinate
code set up in this PR, more or less: https://github.com/roc-lang/roc/pull/7625
question for you on code structure: I was trying to figure out how best to pass around ownership of the different stage IRs and I realized that they are all in (Multi)ArrayLists anyway, so I changed from having each IR get init
ed and returned to each IR being created in a MultiArrayList as undefined
and then their init
functions get a pointer to that undefined
IR that they init in-place (source and source). This seemed like a simple way to keep the reference depth to one, but maybe there's a better pattern. What do you think about this strategy? Am I not explaining this well enough?
I'm not sure I quite follow. What is the advantage of
items.appendAssumeCapacity(.{
.package_idx = can_irs.getPackageIdx(work_idx),
.module_idx = can_irs.getModuleIdx(work_idx),
.work = undefined,
});
init_work_with_env(&items.items(.work)[index], &can_irs.getWork(work_idx).env, gpa);
over (or whatever the equivalent would be):
items.appendAssumeCapacity(.{
.package_idx = can_irs.getPackageIdx(work_idx),
.module_idx = can_irs.getModuleIdx(work_idx),
.work = Work.init_with_env(&can_irs.getWork(work_idx).env, gpa),
});
Because the second one is pass by value, so more copying is happening
Your talking about the returned value from Work.init_with_env
which is being placed into the larger struct as the .work
field?
Yes
Not sure if that's a big cost, or if LLVM will optimize that away
I wouldn't worry about that. Should be optimized away by llvm. Also, should not be anywhere near the hot path.
large returned structs by default are turned into pointer args
Great, that was the most underlying question
Question re https://github.com/roc-lang/roc/pull/7664#discussion_r1980864364 @Anthony Bullard and @Joshua Warner
I was wanting to clarify, should I be slicing into the source bytes or getting this information from the interner?
Is the plan for the untagged union to go away eventually and everything will be interned?
I haven't really paid attention to the interning progress we've made, I know that I'm using IR.resolve in the formatter
The untagged union won’t go away - eg for things that we definitely don’t need to intern (braces, symbols, etc)
My intent is that strings/number/etc will all be interned
I assume if we have any sort of parse errors, we should not format the ast, right? We should print the parse errors and early exit.
I thought the plan was to do a best effort, and generate a compiler error.
Are you specifically talking about the cli formatter?
Yeah, cli specifically
Ahk, that makes sense then.
The only thing I can think of is maybe there is something like an LSP that would want different behaviour. But that's a different tool.
Eventually I want the formatter to format everything _but_ the part of the input that has the error (e.g. maybe the nearest outer statement/decl) - and then copy the source text from the input verbatum, for the section with the error - the only possible difference being indenting or dedenting the entire block of text, if appropriate.
... but for now I think we should just make the formatter bail out on parser OR tokenizer errors.
That makes sense and will be cool when it works
I think we need to keep the source input around throughout all sources that can report errors in the source
At some point we could manifest the errors if we need to.
Note to all, on latest main, the zig version is now 0.14.0
If you have an issue compiling after updating zig, you may need to delete some caches (.zig-cache
and/or ~/.cache/zig/
, maybe also zig-out
).
Missed this on my first read of the zig updates, but zig plans to make the Unmanaged
containers their default contianers. So in zig 0.15.0
std.ArrayList
will be what was previously std.ArrayListUnmanaged
. So I guess switching over to the unmanaged veriants makes even more sense.
Embracing "Unmanaged"-Style Containers
Just wanted to highlight something with our Parser diagnostics. See https://github.com/roc-lang/roc/pull/7672#discussion_r1986224249
I'm thinking we probably want the Parser problems to be pushed into the ModuleEnv so they outlive the parsing stage of the compiler, and later stages that see a malformed node can still reference those errors.
What do people think?
That was always the plan in my eyes, but I do remember the Problem.Parse variant being removed by someone else
So there may be a reason I don't know about why we don't want them in ModuleEnv
But I don't know it
Yeah, I suspect we just haven't ever got that far before. Now we've got more of the coordinate and other stages set up a bit, we can find and sort out these things.
Sounds good to me. Avoids manually managing the lifetime
I'm happy to attempt this change. Though I'll wait for when @Anthony Bullard is next online as he may have ideas or want to work on this.
Where did we land on ||
-- is that meant to be parsed as an or
or are we only accepting keyword?
I'm just working on an ambiguous fuzz failure and this is the current problem.
I'm pretty sure both ||
and &&
should parse and then format to or
and and
This is the fuzz issue
~~~META
description=fuzz crash
~~~SOURCE
||1
That parses the first time as a lambda, then formats as ||
(without the space) then the second time around it parses as an or
Here's the latest snapshot output for that... including the tokens
~~~META
description=fuzz crash
~~~SOURCE
||1
~~~FORMATTED
|| 1
~~~TOKENS
OpBar,OpBar,Int,EndOfFile
~~~PARSE
(file
(malformed 'missing_header')
(lambda
(args)
(int '1')))
One "fix" I found that works, was to format the lambda with no args with a space, e.g. | |
ah yeah, there is ambiguity now. Not sure the plan on that
Would it look terrible if it formatted as |_|
?
I think that would suggest an ignored arg
For the sake of moving past this crash, I think I'll format using a space for now. It's a hack but we can come back to it.
so the idea we settled on was that:
or
and and
&&
to and
, and in the situations where you wrote ||
and it can unambiguously detect that or
would have worked (but 0-arg lambda would not), then it can also rewrite that to or
for you. But there was at least one situation where either could work, and so in those situations we have to assume you meant lambda (which is why we have to go with or
as the keyword)Ok, that makes sense
We are _not_ parsing ||
or &&
any longer. With the 0.1.0-line compiler we are hard moving to or
and and
Richard Feldman said:
- as a matter of convenience, we always have the formatter rewrite
&&
toand
, and in the situations where you wrote||
and it can unambiguously detect thator
would have worked (but 0-arg lambda would not), then it can also rewrite that toor
for you. But there was at least one situation where either could work, and so in those situations we have to assume you meant lambda (which is why we have to go withor
as the keyword)
We can work to do this eventually, but I'm not going to focus on this now.
My biggest concern is landing my current PR, then finishing all header parsing, then figuring out and implementing where ...
in type annotations, and then making malformed work well (the current situation has a number of issues)
Anthony Bullard said:
We are _not_ parsing
||
or&&
any longer. With the 0.1.0-line compiler we are hard moving toor
andand
I don't think this is correct. I think the tokenizer unifies them.
So we likely need to delete support from the tokenizer if this is what we want.
If that is the case, then yes the tokenizer needs an update
I think || at least needs to be given its own special token (not unified with or
at that level)
We need context from the parser in order to distinguish cases where || would me or
from uses as a no-args closure
Parser could match on double single bar instead of doing it in the tokenizer.
Though not sure the tradeoffs there
Like if in an expression where it could see and
or or
, if the parser sees two ampersand or two bar tokens, it could consider them and/or
I don’t want two bars with white space in between to ever accidentally be treated as an pipe || or. So I think this definitely needs some kind of token representation that’s unique from that.
I see. Yeah, forgot about whitespace
Interesting reply to our roc post on switching to zig. Specifically about compile times:
https://x.com/zack_overflow/status/1899953945990357081?t=oaGhkuoKLPnMyAsvl_zUxg&s=19
I agree with your reply :big_smile:
I'll happily take "massive feedback loop improvements for large code bases are mid-development but haven't landed yet" over "there are no plans for massive feedback loop improvements at any point in the future"
Even worse, no possible plans, IMO
The WASM runtime for proc macros seems pretty promising
And parallelism was only recently introduced in nightly for pre-LLVM stages within the same crate
But Rust as a language isn't designed in a way that can be compiled quickly
This coming from one of Rust's biggest fanboys
I think y'all should be able to try out this workflow already (the thing the bun guy said they can't try out because of usingnamespace
).
has anyone tried it? can you report success or trouble with it?
note: specifically the "no-bin" thing (read the linked section to see how to set it up)
Does no-bin have to be a flag? Currently we have a check
build step, but zig seems to ignore it and still build everything.
might be a bit of an awkward build system API thing here to work around. it needs to pass -fno-bin
to the compiler, which I believe it does based on whether or not exe.getEmittedBin()
is called, which is called by installArtifact
I'm interested in addressing that, but more interested in seeing if you can get incremental compilation on errors only to work already
If I comment out all installArtifact calls and remove the test step we get super fast compiles.
If I only comment out installArtifact, but leave in the test step, some reason every other build is super fast (presumably a bug of some sort cause I change the file every time).
interesting. well you are welcome to file bugs against this functionality (codegen disabled). mlugg has been pretty diligent about fixing such bugs
Despite changing the same amount of code between every run, every other call full rebuilds the tests and takes 2 seconds.
with test step
that's a good bug report assuming that you've managed to make the zig test
command pass -fno-emit-bin
and assuming that gets fixed soon, that should be a ~25ms recompile cycle for you while working on a refactor. hope that gives you a sense of where things are headed :)
Is there any equivalent config to -fno-emit-bin
for addTest
followed by addRunArtifact
?
From a quick skim of the options, I don't see anything available there
mm I think addTest is equivalent to addExecutable. so if you don't try to run the test, I think it will pass -fno-emit-bin. you can verify the CLI commands with --verbose
btw another thing I'm doing in this release cycle is separating out the build runner process from the application's configure script (build.zig), so that you don't have to wait for the growing number of build system features to compile every time you change your build script. this is relevant as the fuzzer UI becomes more sophisticated
Hmm, so yeah, some reason every other save it rebuilds the test binary. And it is missing -fno-emit-bin
.
/Users/bren077s/vendor/zig-0.14.0/zig test -ODebug -Mroot=/Users/bren077s/Projects/roc/src/test.zig -lc --cache-dir /Users/bren077s/Projects/roc/.zig-cache --global-cache-dir /Users/bren077s/.cache/zig --name test --zig-lib-dir /Users/bren077s/vendor/zig-0.14.0/lib/ -fincremental --listen=-
That said, given I am not calling zig build test
, I am a bit surprised this is happening at all.
I guess just because the test
step exists which runs the test binary, anything that interacts with the test binary (even if it doesn't run the binary), will lead to the binary being generated. I made our check
step depend on addTest
, just to make sure all our tests compile.
I'm sure the build system API could be improved to make this better without you having to think so hard about it
Hmm, yeah, making 2 copies of the test step. One that is used for zig build test
and actually runs the test, and one that is used for zig build check
but never run fixes the issue.
I mean, once the "codegen doesn't work yet" caveat is lifted, for instance, this will Just Work
but anyway, I hope you will find these workarounds worth it for the 0.14.x release of zig - they sure helped me out a ton when working on big things
Anyway, thanks for the tip, definitely will clean up our build.zig to make incremental builds work.
np! report bugs :)
one day we'll find all our own bugs with fuzzing but that day has not yet arrived
I've just checked out the new incremental stuff @Brendan Hansknecht landed for roc's zig compiler and configured ZLS too.
It's very fast. :firebird: :racecar: :rocket:
(edit) it's hard to find the right emoji to really convey the feeling
The "official" emoji for fast Zig stuff is :zap: (:zap:
)
Thank you Loris :zap:
ZLS does support --watch so you should also be able to enjoy basically the best of both worlds (in editor diagnostics, fast feedback) if you have the correct setup https://github.com/zigtools/zls/pull/2096
forgot to add: :zap:
What's the next thing that ought to be worked on at this point?
There are a few candidates
Moving to a keyboard
There are a few paths for us to take to get to an MVP
The first stage we have been talking about was functions and strings
_nods_
There were a couple of "more difficult to do after" steps I thought important to implement, like blocks and imports
But those aren't necessary
So if we want to finish up with imports, then implementing the basics of import resolution would be a good next step
That's part of can? Or is that in a later phase?
That's the phase stage directly after canonicalization
resolve_imports.zig, presumably
yep
In particular, can wants to treat imported data as "probably" present, and imported from a module with the given name. resolve_imports.zig
would go through those imports (and also ingested files a la import "file.txt" as data : List(U8)
) and match them to files in the filesystem or create an error
So it'll need to trigger parsing (and can) for those other files, right?
What's the mechanism for that?
That has already been implemented in the coordinate.zig
foundational work
The coordinate.zig
file looks at all files (Roc and non-Roc) in all referenced packages
And registers them in a big list
Then resolve_imports.zig
would look in the *Package.Store
and see if it can find a file with the right name for the imported module
Is that the discoverModulesStartingFromEntry
thing?
I'd look at ModuleGraph.zig
for whoever implements this, because that already forms a dependency graph and sorts the modules in reverse dependency order for compilation of post-cache stages, AKA import resolution and beyond
Aha great
And remind me, are we guaranteed to have a DAG? Or might there be import cycles?
We are banning import cycles
If we find an import cycle, we exit early:
https://github.com/roc-lang/roc/blob/2dbbdf3e1f6b80f7fade826b27e6a4703dd24357/src/coordinate.zig#L111
So this is one potential task
I thought we needed import cycles for mutually recursive custom types.
We could just require that mutual recursion stays within one module, no?
Or are you saying you also want to allow functions of the same name on each type?
Well, what about Foo
and Bar
both having to_str
methods
Ah, fair
Yeah... we should be able to support those awkwardly without allowing people to write less performantly-compiling code
I'll link the message from Richard's brain blast on the subject
Yeah, I think in that one special case, we have to conseder those modules as a super unit essentially
Richard Feldman said:
Richard Feldman said:
yeah, basically the idea is that if you have two nominal tag unions that are mutually recursive, and you also want them to have static dispatch (which could come up when modeling database tables, for example) that's currently impossible
so I thought about this some more, and I think it's better if we continue to disallow cyclic imports and recommend this workaround if anyone actually needs mutually recursive nominal types with static dispatch:
- define the two mutually recursive nominal types (let's call them
A
andB
) in the same module, let's call itAandB.roc
- create separate
A.roc
andB.roc
modules, each of which importsAandB.roc
only- both
A.roc
andB.roc
exposes a nominal type which wraps the appropriate mutually recursive type insideAandB.roc
, and exposes all the desired methods on those- if the underlying nominal type needs to be exposed too (e.g. because the tags are needed for matching), then
A.roc
andB.roc
can each provide ato_inner
function which returns the underlying nominal type fromAandB
. Static dispatch won't be available on this structure, but that's okay because the wrapper does.
From earlier in this channel:
Interesting
ah yeah, forgot about that
This sorta creates a one-type-per-file requirement
So yeah, painful, but no recursion
This sorta creates a one-type-per-file requirement
Custom types do that in general. This is more a side effect.
Yaeh true
I guess what I was poking at is maybe static dispatch methods ought to be definable within a smaller scope than a whole module
Like if you could define types in submodules and re-export them from the parent (real file) module
like Rust's mod{}
blocks
Yeah, that has been mentioned a few times. I think it is currently in the lets wait and see in practice state
Yep yep, makes sense
Cause could be dealt with via submodules or via explicitly bound methods to an object.
So @Joshua Warner, in order of my estimation of importance, there's
Is there something in particular you want to hear about?
If you're interested in typechecking, I'd reach out to Agus and see if you can grab it from him, he seems very busy with work at the moment and hasn't been pushing to his PR since its creation.
But there are technically multiple people that are interested in working on it, so that one will happen eventually
I have fairly limited time, so whatever I pick up probably needs to be possible to put into some relatively bite-sized chunks
Looks like snapshots can't have multiple test files right now, and thus can't usefully hit code in resolve_imports
Actually it looks like snapshots don't currently cover anything after parsing (no canonicalization, for example)
Yes, that would be something helpful to figure out on its own, and working on one stage at a time (or part of a stage at a time) should be modular enough
I thinking of tackling these things next:
~~~SOURCE
you have ~~~SOURCE:foo.roc
and ~~~SOURCE:bar.roc
sections, and so on for any of the following sections which are per-module.Thoughts?
That would be great!
Last updated: Jul 06 2025 at 12:14 UTC