DEV Community: Simmypeet

Optimizing Graph Traversal in Query Based Incremental Compiler

Simmypeet — Sun, 08 Mar 2026 12:33:55 +0000

Hi, this is my follow up post on the building query-based incremental compiler. This has been my rabbit hole for past few months.

I've been tackling one of the biggest challenges in my incremental compiler. It's about the huge graph traversal problem.

Previously, I've built a incremental compiler that's based on the Salsa model, which is the library that I believe rust-analyzer use.

Here I'll briefly explain how my previous incremental compiler algorithm works and what I believe Salsa model uses too.

1.) The central query database maintain a monotonically increasing version number. This could be just an increasing i32 or whatever. This represents the version that database is in. Every time a modification to the database's input is made (i.e., updating the source file), the global version number will be increased by one.

2.) Every time the query is computed and memoized to the database, It stores the result alongside with the current version number that database currently has. Technically, it stores two separate version numbers: version when it was computed and version when it was verified.

3.) Every time the query is made to the database, the db checks whether if the query has happened to be already memoized or not. If not, the database just run the query. If it's already memoized it follows the next step.

4.) The db checks the version when the query was last verified against the current version of the db. Imagine, if the database has been changed today but the query was last used yesterday, it means that the query potentially has stale result.

Based on this check, if the version mismatches (stale) it performs reparation. Otherwise, if the version matches (up-to-date), it directly returns the query result.

5.) When the query repairs itself, it also have to makes sure that its dependencies are also up-to-date (their dependencies' version number have to match with the current database's version). You'll notice that this is essentially a recursive call in the graph, traversing from the root node down to the leaf nodes.

The pseudocode algorithm looks something like this:

def query(db, node):
    # already up-to-date
    if db[node].last_verified == db.version:
        return db[node].result

    repair(db, node)

    return db[node].result

def repair(db, node):
    # already up-to-date
    if db[node].last_verified == db.version:
        return

    # IMPORTANT: we recursively repair unconditionally 
    for dep in db[node].dependencies:
        repair(db, dep)

    need_recompute = False

    for dep in db[node].dependencies:
        # it means that the dependency has changed since it was last used
        if db[dep].last_computed > db[node].last_verified:
            need_recompute = True

    # this means no further re-computation, mark as verified and return
    if not need_recompute:
        db[node].last_verified = db.version
        return

    old_fingerprint = db[node].fingerprint

    # assume it recomputes and set the result and fingerprint
    recompute(db, node)

    if db[node].fingerprint != old_fingerprint:
        db[node].last_computed = db.version

    db[node].last_verified = db.version

Here's the problem, even though this model can avoid O(n) re-computation to O(changes_made) re-computation (where n refers to the number of node in the graph). It stills have O(n) graph traversal even though you made small changes.

Here's an example:

Let's look at the above DAG (Directed Acyclic Graph), which currently is a 🌳, represents the program that the database maintain. Here, every queries are computed at version 0, hence the : v0 label attached to each node. For the brevity, we'll just show when it was last verified. In the actual implementation, it also contains when the query was computed as well, in this case, all of the queries are computed at version 0.

Let's say we make some change to the query D, making the database version increments to 1. Now, when we query for G again, it will check whether the query G's verification version matches to the database's version or not. Here, it mismatches, then the query G would have to be repaired, and in the process it also have to look at its own dependencies whether or not they have verification version match with the database version. Now you can imagine this recursive process, it would traverse through every node, and ended up traverse 7 nodes.

To Adapton Style

The previous style it's commonly called the pull-based or timestamp-based verification etc. Since I've encountered that said problems, I've been digging on the internet whether anyone has this problems and how they managed it. It seems like rust-analyzer team also acknowledged to this problem and they have came up with the durability system. I've also found "adapton" and its fine-grained dirty propagation system.

In Adapton, when ever the input changes, the modified node performs the dirty propagation on its incoming edge in the graph transitively. Here in Adapton, each edge in the graph also have dirty flag associated to it. When the dirty propagation occurs, it flips that said flags to true, signaling potential invalidation.

Let's say in previous DAG example:

When we modify query D, its incoming edge will be marked dirty and transitively propagates to the incoming edge of F, resulting in graph looking something like this.

Here's the above graph shows how the it would look like after dirty propagation.

The dirty propagation is active, it means that when the query node is modified, the dirty propagation happens immediately. This is what I believe why people often call this push model.

So great! how this dirty propagation help when we repair the query? The answer is unlike the previous model where the query has to recursively invoke reparation on all of its dependencies, this push model can selectively choose to recursively repair its dependencies that have dirty flag set to true.

This totally makes sense, because E doesn't depend on any query that were modified, whereas, F depends on D, which has been modified. Therefore, G skipping reparation on E is totally safe.

With this model, the only nodes that was traversed during reparation were G -> F -> D.

Therefore, making Adapton has two distinct phases:

Dirty Propagation: is active, happens immediately after the node is modified.
Repair: is lazy, happens when the user queries for a node that has dirty outgoing edges.

Now, I want to quickly discuss about the trade-offs between two models.

Laziness: Salsa is more lazy in the sense that when the query is modified, it just increments a version number on the DB. Unlike the Adapton, it has to traverse the graph backward and perform dirty propagation.
Memory Usage: In order for the Adapton dirty propagation to be able to traverse the graph backward efficiently, each node has to also maintain backward edges, resulting in more memory usage.
Graph Traversal: In the Adapton, the reparation phase usually needs less graph traversal than the Salsa model due to finer-grained dirty tracking.

Super Node: Where Dirty Propagation Falls Apart

When I've discovered Adapton, I though that my problem is solved. Before I'm going to implement my own version of incremental computation engine inspired by Adapton, I realized that the graph traversal problem would be a problem again even with the help of dirty propagation if my graph has a super node.

Let's me show you my current setup. I'm currently trying to build incremental compiler and currently my dependency graph looks something similar to this.

Here's at the bottom, we have "src A" and "src B" representing the source files that the compiler uses as inputs.

Then up on one layer, we have a huge query labelled as "symbol table" that aggregates all the symbols defined in each source file into one big HashMap<ID, Symbol>.

Then, we have each query like "A" and "B" that extracts a specific symbol information from the symbol table's HashMap<ID, Symbol>. These queries are essentially just a hash map look up on the "symbol table" to extract the information of the interested symbol.

Furthermore, we have some unnamed queries that depends on the "A", "B", and etc. representing some computation that further use symbol information like type checking.

Finally, the "start" node acts as a root that starts the whole compilation system.

Let's say I modify one single symbol in "src A" (a very little small change), the dirty propagation would kick in. The incoming edge of "src A" node is dirtied and then transitively propagates to all the incoming edges of "symbol table", which essentially all of the edges above the "symbol table'. Finally, we're left with dirty flag being set to true almost every where.

Here, I colored the edge with "red" marking them as dirty.

The problem is that the "symbol table" is a node that has so many incoming edges to it and the "symbol table" query is very coarse grained (very big).

Now, one could say that this is a problem of a poor dependency structure, and should've restructure the dependency to avoid this kind of problem, which is a very fair point.

Continue with this, I would say that the "symbol table" query is a super node and those "A", "B", and more are called projection queries.

The "super node" refers to a node that have lots of outgoing edges. Where as, projection query is a query that reads a small portion of its dependency. For example, the query "A" just extracts one symbol from "symbol table".

I'll call this problem "the over dirty propagation".

In fact, Adapton has a feature that is designed to combat with this issue specifically and it's called firewall.

With that, I take inspiration from Adapton and adapts into my engine. Here, I want introduce some algorithm inspired by Adapton's firewall that will combat with this issues.

Here, I'll introduce you to new two kinds of query that will be added. Normally, each query are "just a query", now we differentiate each query to "Normal" (default), "Firewall" (new), and "Projection" (new).

Firewall Query

We can mark a query as a "Firewall". The "Firewall" query has a main responsibility of stopping dirty propagation from crossing them.

Here's how it works, imagine the same compiler graph setup, if we modify the "src A", the incoming edge of "src A" would be dirtied and then propagate to all of the incoming edge of "symbol table".

However, if we mark the "symbol table" as firewall, the dirty propagation will stop there, meaning no incoming edges of the "symbol table" will be dirtied.

Here, the outgoing edge from "symbol table" to "src A" is dirtied, but none of the incoming edges of "symbol table" are dirtied at all because firewall stops dirty propagation from crossing it.

The Algorithm

Continuing from the previous graph with firewall example, let's say when we query "start" (at the top), it first sees that the "symbol table" has dirtied outgoing edge, therefore, it will attempt to repair the firewall first, which is "symbol table", before repairs query "start" itself.

What could happen is that, if the firewall "symbol table" is repaired, the result could either be the same or updated.

If the firewall "symbol table" is repaired with no changes, the firewall reparation is done. The reparation flow goes back to the "start" query. And since there're no dirty outgoing edges of "start" query, the "start" query itself is considered up-to-date, the result of "start" is reused, done!

In this happy path, where the firewall "symbol table" is recomputed and result stays the same. There's only one edge dirtied in total and only 3 nodes being traversed!

However, in the case of when the firewall "symbol table" is recomputed and result changes, then the dirty propagation will start at the "symbol table", which in this case, the dirty flag will eventually reach to the "start" query's outgoing edges.

The above image shows the steps up to when the firewall "symbol table" is recomputed and result changes.

The above image shows that after it detects result change, the dirty propagation starts at the firewall.

Finally, the dirty propagation is done then the firewall reparation is considered finished. The reparation is back to the "start" query where the "start" query will see that its outgoing edges are dirtied.

To summarize, we modify the reparation algorithm to first reparation the firewall that it depends on (directly on indirectly) before do the actual reparation work on the query node itself.

Note that in order for the "start" node to be able to detect that the firewall "symbol table" needs to be repaired first, it has to maintain additional edge that directly points to the firewall that it depends. This mean that every node in the graph will have additional edge that points to the firewall that it directly or indirectly depends on.

Projection Query

You can see that we haven't quite solved all the issues yet. In the previous example, when the firewall "symbol table" is repaired and the result changed, the dirty propagation still happens and lots of node are still dirty propagated, which means the graph traversal problem isn't quite solved yet.

In some cases, only some entries in the "symbol table" is actually changed.

For example, if we modified symbol "A" that is located in source file "src A". When we repair the firewall "symbol table", the entry table["A"] is only changed while entries like table["B"], table["C"], and more are still the same.

Wouldn't it be nice to only dirty propagate the incoming edge of "A" to "symbol table" like the following image?

Yes, we could achieve this finer-grained dirty propagation!

Here's the twist, what if when the firewall "symbol table" is repaired and the result changed, instead of dirty propagate at "symbol table" right away, we re-run those projection queries (like "A", "B", etc.).

And based on those re-runs on projection queries, whichever projection query's result changes, the dirty propagation start from that particular projection query instead of the firewall "symbol table".

Here the step-by-step explanation, let's use the same example: modifying symbol "A" located in "src A":

The steps are basically the same

All of the projection queries are re-run

Only A changed

Dirty propagate starts at A

Finally, we've achieved very fine-grained dirty propagation and thus can keep graph traversal very minimal during reparation phase.

Trade-offs

Let's talk about the trade-offs, nothing comes for free.

"Everything is a trade off"

Software Design and Architecture Prof.

Memory Usage: With this setup, every node has to maintain additional edges that directly point to the firewall that it depends (directly or indirectly). If not careful, the memory usage can grow to O(node * firewall).
Unnecessary Recomputation: Recall that when the firewall's result changed during reparation, it unconditionally re-executes the incoming projection queries.

However, these are very fair trade-offs considering that:

The number of firewall queries in system is very small, the memory overhead can be acceptable.
The projection queries that got re-executed unconditionally are very fast such as reading variable, array index, or hash map lookup.

Conclusion

We've explored a way to avoid a large graph traversal in query-based incremental compiler by using technique like dirty propagation, stopping dirty propagation at firewall query, and finer-grained dirty propagation through projection queries, which are heavily inspired by Adapton. We trade-off some increased memory usage and potentially some unnecessary recomputation for avoiding massive graph traversal.

These concept also can be extended further into something like: chain of firewalls, projection queries that depends on two firewall, and more.

I've also packaged this into a separate library called https://github.com/Simmypeet/qbice if anyone is interested 😉.

NOTE that I haven't taken some time to properly write documentation for it. Most documentations are AI generated, however, I've tried my best to check for its correctness as well.

Thank you for taking your time and interest reading this far 😘.

Rust 2.0: A Thought Experiment on Safe Specialization

Simmypeet — Sat, 10 Jan 2026 11:36:24 +0000

Specialization is a long-awaited feature in Rust that has never been stabilized. There have been many attempts to land this feature, but each comes with its own set of shortcomings and soundness holes.

In this blog post, I want to share an idea for impl specialization that has been floating around in my mind. We will walk through the trade-offs and try to explain exactly why specialization is such a challenging feature to add to the language.

Why Specialization?

One of the most compelling use cases for specialization is optimization. A concrete example is cloning a Vec<T>.

In general, cloning a Vec<T> works by iterating through each element and calling .clone() on it.

With specialization, we could write an extra, specialized case where T: Copy. When the compiler knows that T implements Copy, the Vec<T> implementation can optimize the cloning process by skipping the loop and using memcpy to bulk-copy the underlying memory buffer.

Primer: What's So Unsound About Specialization

The main specialization feature today hasn't been stabilized for many years
because it has some nuances with lifetimes. Mainly, it can lead to memory-safety
violations like use-after-free. I'll show you an example of such unsoundness
and then I'll explain why min_specialization has come to the rescue and
explores some alternatives.

We'll start of with this trait and two implementations:

#![feature(specialization)]

pub trait ItsABomb { fn boom(&mut self); }

impl<T> ItsABomb for T {
    default fn boom(&mut self) {
        println!("All is safe!");
    }
}

impl<T> ItsABomb for (T, T) {
    fn boom(&mut self) {
        std::mem::swap(&mut self.0, &mut self.1);
    }
}

Here's the example, simple enough. We have a trait ItsABomb with two
implementations.

The first general implementation works for all types T.
The second specialized implementation works for tuples of the form (T, T).

Here's the interesting part: the second implementation sees a tuple of
two identical types so it swaps the two elements in place.

Now, let's see how this can lead to unsoundness:

fn call_a_bomb<U>(bomb: &mut U) {
    bomb.boom();
}

fn create_a_bomb() -> &'static str {
    let local = "I'm a local string".to_string();

    let local_str = local.as_str();
    let static_str = "I'm a static string";

    // you can imagine both are of type (&'local str, &'static str)
    let mut pair = (local_str, static_str);

    // this calls the specialized impl that swaps the two elements
    call_a_bomb(&mut pair);

    // the second element becomes a "I'm a local string" now!
    println!("After boom: {}", pair.1);

    pair.1 // returning a reference to local data with no problem
}

fn main() {
    let leaked = create_a_bomb();

    // use-after-free occurs here!
    println!("Leaked string: {}", leaked);
}

Let's try put it all together and sees what happens here:

After boom: I'm a local string
Leaked string: #�'���+�

As of today (Jan 2025), the code compiles with flying colors and runs without
warnings (only saying that specialization is unsound, which it is :D), but
surely we hit a use-after-free at runtime!

If you have a chance to run this code, try it out yourself!, you'll see that the
it prints garbage for the leaked string.

What's Going On Here?

Let's break down what happened step by step:

create_a_bomb function create a tuple of two references: one to a local string and another to a static string.
You could imagine the type of pair is (&'local str, &'static str).
create_a_bomb calls call_a_bomb, passing a mutable reference to pair.
Inside call_a_bomb, the specialized implementation of ItsABomb is invoked, which swaps the two elements of the tuple.
After the swap, pair.1 now points to the local string.
However, create_a_bomb doesn't know that the swap has occurred. It still sees that pair.1 has a type of &'static str.
create_a_bomb returns pair.1, which is now a reference to the local string

What Should Have Been Done?

Here's the kicker, if you try to add a bound to call_a_bomb like this:

fn call_a_bomb<U: ItsABomb>(bomb: &mut U) {
    bomb.boom();
}

And compile with the exact same code, the compiler will refuse to compile it:

error[E0515]: cannot return value referencing local variable `local`
  --> src/main.rs:38:5
   |
26 |     let local_str = local.as_str();
   |                     ----- `local` is borrowed here
...
38 |     pair.1 // returning a reference to local data with no problem
   |     ^^^^^^ returns a value referencing data owned by the current function

The compiler now correctly rejects the code. Why does a simple bound fix the
issue?

The reason is that by adding the bound U: ItsABomb, we force the compiler to
resolve the impl for U at the call site (inside create_a_bomb), not
inside call_a_bomb.

Inside create_a_bomb, the compiler can see more complete picture of the types
involved, including the lifetimes.

Here's why this prevents the unsoundness:

When create_a_bomb calls call_a_bomb, it sees that there's an obligation to find an impl for ItsABomb for the type (&'local str, &'static str).
The type-checker with complete knowledge of the lifetimes involved, sees that the type (&'local str, &'static str) is a tuple of two different lifetimes.
The type-checker however picks the (T, T) implementation, but with additional constraint.
- Some might confuse how can (T, T) match (&'local str, &'static str) since 'local and 'static are different lifetimes. The answer is that generally when two types are being unified, the compiler is allowed to ignore the differences in lifetimes, but it generates additional constraints related to lifetimes to be solved later.
In this case, type-checker makes two types equal, it coerces (shrinks) the 'static lifetime to 'local, resulting in the type (&'local str, &'local str).
Now, when create_a_bomb tries to return pair.1, the compiler correctly identifies that pair.1 has type &'local str, preventing the use-after-free.

Applying the same logic to our original unsound example, here's why the compiler
didn't catch the issue:

Inside call_a_bomb, when we call bomb.bomb(), the compiler tries to check that "are there any impl for ItsABomb for type U?"
However, at this point, the compiler has no knowledge of what U is but it sees that there is a general implementation impl<T> ItsABomb for T.
The compiler eagerly concludes that, "Yes! There's an implementation for U!" It might not exactly know which one, but it knows that there's at least one.
The compiler type-checks call_a_bomb without any further complains.
This time, when create_a_bomb calls call_a_bomb, the compiler has no obligation to resolve the impl for ItsABomb for type (&'local str, &'static str).
Under incomplete knowledge, type-checker doesn't do anything between 'local and 'static lifetimes, treating them as completely separate.
The type-checker allows create_a_bomb to return pair.1 as &'static str, leading to the use-after-free.
At monomorphization time, when everything is concrete (no more generics), the specialized implementation is preferred, leading to generating the code that swaps the two elements.

The Problem

The root cause of the unsoundness is that the type-checker doesn't see the
complete picture when resolving the impl for a generic type parameter.

As we've pointed out, in the call_a_bomb<U> function, the compiler has no
knowledge of what U is but it sees that there is a general implementation
impl<T> ItsABomb for T so it type-checks call_a_bomb without any further
obligations.

When create_a_bomb calls call_a_bomb, the type-checker sees that this
function can be called with any type U and without any further obligations to
the caller. But in reality, the fact that it solves to the specialized (T, T)
implementation it already introduces additional constraints on the lifetimes
that the type-checker is unaware of.

How Could We Fix This?

At this point, we have shown an example of unsound specialization and explained
one of the possible fixes (adding a bound to defer the resolution to the caller).

The Rust team has acknowledged this unsoundness and this is one of the reasons
why the current specialization feature is not stabilized and advocates for
using min_specialization instead. If we were to use min_specialization, the
above compiler correctly rejects the code but for a different reason.

In the previous example that we added a bound to call_a_bomb, the compiler
rejects the code because it sees that we're about to return a local reference
as a 'static reference.

But under min_specialization, even without adding the bound, the compiler
rejects the code under the reason that the specialized implementation uses
generic parameter T twice, which could potentially introduce constraints that
the type-checker might miss.

In my proposed design for specialization, I'd like to take the idea of "making
the resolution transparent to the caller" (like how we added a bound to
call_a_bomb) and make it a required part of the specialization system.

Specialization with Deferred Binding

We introduce a new rule: The compiler is only allowed to resolve an impl when the types are "Grounded".

The term "grounded" refers to a property of a particular type. A type is said to be grounded if there aren't any generic parameters in it.

Vec<i32> is Grounded (Fixed structure).
Vec<T> is Not Grounded (T can be anything).

This property is important because if a type is not grounded (like Vec<U>), its structure is volatile, it could change into a specialized form in the future.

After applying this new rule, the previous call_a_bomb code example would produce an error:

fn call_a_bomb<U>(bomb: &mut U) {
    // Error! `U` is not grounded here!
    // It would produce error like:
    // `U: ItsABomb` cannot be satisfied
    bomb.boom();
}

Even though there's an implementation impl<T> ItsABomb for T, the compiler
refuses to resolve it because U is not grounded.

So what the solution is similar to what we did before: we add a bound to defer
the resolution to the caller!

fn call_a_bomb<U: ItsABomb>(bomb: &mut U) {
    // Error! `U` is not grounded here!
    // It would produce error like:
    // `U: ItsABomb` cannot be satisfied
    bomb.boom();
}

Conceptually, call_a_bomb is now saying: "Dear caller, please find the impl
for ItsABomb for type U and provide it to me."

Now, when create_a_bomb calls call_a_bomb, the compiler can resolve the
impl for (&'local str, &'static str) because this type is grounded.

Note: Under this rule, lifetime parameters are ignored when determining groundedness.

fn call_a_bomb<U: ItsABomb>(bomb: &mut U) { ... }

fn create_a_bomb() -> &'static str {
    // ...

    let mut pair = (local_str, static_str);

    // the type-checker resolves the `impl` here!
    call_a_bomb(&mut pair);

    // ...
}

When create_a_bomb gets to resolve the impl, it sees that it will use
the specialized (T, T) implementation and generates the additional constraints
on lifetimes (shrinking 'static to 'local), preventing the use-after-free.

The Chain of Delegation

Now we could also extend the chain of obligations further down the stack like so:

pub fn call_a_bomb_deep<U: ItsABomb>(bomb: &mut U) {
    bomb.boom();
}

pub fn call_a_bomb<U: ItsABomb>(bomb: &mut U) {
    call_a_bomb_deep::<U>(bomb);
}

fn create_a_bomb() -> &'static str {
    // ...

    let mut pair = (local_str, static_str);

    // the type-checker resolves the `impl` here!
    call_a_bomb(&mut pair);

    // ...
}

See, whenever the type-checker couldn't solve the impl because the type is not grounded, it forces the caller to provide the implementation instead. And this
chain continues until we reach a grounded type.

The Problem: Delegation Hell

With the Groundedness rule, we achieve sound specialization. However, it creates headaches in generic-heavy codebases.

Consider the standard library type Arc<T>. In Rust today, Arc<T> implements Clone regardless of what T is. Cloning an Arc is just incrementing an atomic counter; it doesn't require anything from T.

// crate: std
pub struct Arc<T> { ... }

// Here, NO bounds on T!
impl<T> Clone for Arc<T> {
    // Just increment atomic counter
}

// crate: app
fn clone_some_arcs<T>(arc: &Arc<T>) {
    let cloned = arc.clone();
}

This is perfectly fine code. However, with the new Groundedness rule, this code would not compile.

Why? Because Arc<T> inside clone_some_arcs<T> is not a grounded type. The compiler refuses to resolve the impl.

Even though we know that Arc's cloning logic is universal and won't change, the compiler is forced to be paranoid. It thinks: "I cannot bind to the standard implementation yet. What if, later down the line, there's a specialized implementation for Arc<i32>?"

Under the rule, we have no choice but to add where Arc<T>: Clone to the function. In a generic codebase, this pollution spreads everywhere:

fn this_is_such_a_pain<T, U>(a: &Arc<T>) {
    // 🤓 Compiler: "Nuh uh! You can't do that ..."
    let a = a.clone();

    // 🤓 Compiler: "Nuh uh! Actually there might be a specialized Option..."
    let b = Option::<U>::default();
}

To fix this, we have to state the obvious in the bounds:

fn this_is_such_a_pain<T, U>(a: &Arc<T>)
where
    Arc<T>: Clone,      // Isn't that obvious?
    Option<U>: Default, // Really?
    SomeInternalStruct<T, U>: Clone, // Now I'm leaking internal details, ugh!
{ ... }

Introduce `final impl`

We need a way to tell the compiler: "Relax, this impl is the FINAL and DEFINITIVE one. There will never be a more specialized version. Pick this one immediately."

Introducing the final impl.

The final impl is a way to mitigate the "paranoid compiler." It has two properties:

The Power: The compiler is allowed to bind this impl eagerly, even if the types are not grounded. This is exactly how Rust behaves today.
The Restriction: A final impl cannot be overridden. No one is allowed to write a more specific implementation that overlaps with it.

This solves the ergonomic issues. By declaring final impl, the compiler knows specialization is impossible, so eager binding is safe.

// crate: std
pub struct Arc<T> { ... }

// impl #1
// This `impl` can't be overridden!
final impl<T> Clone for Arc<T> {
    // ...
}

// crate: app
fn clone_some_arcs<T>(arc: &Arc<T>) {
    // Compiler is safe to bind to `impl #1` eagerly!
    // 1. Compiler sees `Arc<T>` is not grounded.
    // 2. But, it sees `final impl`.
    // 3. It knows this will never change.
    let cloned = arc.clone();
}

This creates two clear camps:

Regular impl: Specializable, but requires Grounded checks (deferred resolution).
final impl: Rigid, but allows eager resolution, improving ergonomics for structural types.

Some Further Crazy Ideas: Ranking

I want to throw out another wild idea to solve the final challenge of trait resolution: Ambiguity.

Consider a trait Log that is implemented for types that are Display, but falls back to Debug if Display isn't available.

// Impl #1: The 'preferred' one
impl<T: Display> Log for T {
    fn log(&self) { println!("{}", self); }
}

// Impl #2: The 'fallback' one
impl<T: Debug> Log for T {
    fn log(&self) { println!("{:?}", self); }
}

If a type implements both Display and Debug, the compiler has to guess. Since neither type is "more specialized" than the other, this is an ambiguity error.

What if we could assign an explicit ranking (where lower is higher priority) to the implementations?

// Rank 1 (High Priority)
#[rank(1)]
impl<T: Display> Log for T { ... }

// Rank 2 (Low Priority)
#[rank(2)]
impl<T: Debug> Log for T { ... }

This would only be allowed for regular impls, acting as a tie-breaker when type specificity is equal.

The revised resolution flow looks something like this:

def pick_regular_impl(available_impls, type, env):
    result_impl = None

    for candidate in available_impls:
        if not candidate.unify_with(type):
            continue

        if not candidate.is_bound_satisfied(env):
            continue

        # First valid match found? Keep it.
        if result_impl is None:
            result_impl = candidate
            continue

        # Compare specificity first
        order = candidate.order(result_impl)

        if order == Order.MoreSpecialized:
             result_impl = candidate

        # If equally specialized, use rank as a tie-breaker
        elif order == Order.Equal:
            if candidate.rank < result_impl.rank:
                 result_impl = candidate
            elif candidate.rank == result_impl.rank:
                raise AmbiguousImplError()

    return result_impl

That's it! Is this sound? I'm not sure 🤣. But it looks promising.

Reflection: How This Fits into Rust Today

All of the ideas discussed here would be breaking changes if applied to the language defaults.

However, the concept might not be that "alien" to the current state of Rust. In Rust today, trait implementation behaves exactly like the final impl proposed in this post (eager, non-overlapping).

We could imagine a path where we add a new keyword:

Keep impl as is: eager binding, not specializable.
Make default impl specializable, requiring groundedness checks.

However, it is still difficult to retrofit this feature into the standard library.

For example, if we were to enable Vec<T> cloning specialization, we would change the current impl to a default impl:

default impl<T: Clone> Clone for Vec<T> {
    // general cloning
}

impl Clone for Vec<u8> {
    // optimized memcpy version
}

Any time we call clone on a generic vector, we would have to add an explicit bound like where Vec<T>: Clone instead of just where T: Clone.

What's the catch?

In Rust today, the following code is valid because there's an implementation impl<T: Clone> Clone for Vec<T>.

fn clone_vec<T>(a: &Vec<T>)
where T: Clone
{
    let cloned = a.clone();
}

Under our new rules, because the implementation is no longer allowed to bind eagerly, the compiler isn't allowed to use the lazy impl for Vec<T> because Vec<T> is not grounded.

To fix this, we would have to rewrite the function signature:

fn clone_vec<T>(a: &Vec<T>)
where Vec<T>: Clone // CHANGED! Bound is on the container, not the content.
{
    let cloned = a.clone();
}

This means that simply enabling specialization for Vec would break every single function in the Rust ecosystem that clones a generic vector!

The Ugly

We've discussed all the good parts of this new specialization system, but what
are the downsides?

I think one of the biggest downsides is that it makes generic programming more
verbose and most importantly, it potentially leaks implementation details.

Taking from the previous clone_vec example, you can imagine that cloning
vector is something internal to the API of a library. However, with this new
specialization system, the library author is forced to expose the fact that
cloning a vector is done internally and forced to write where Vec<T>: Clone in
the public API instead of just where T: Clone.

The final impl does help in some cases, but it doesn't work when the trait
we use is specializable itself.

Bonus: Lifetimes

In this section I want to talk a bit about lifetimes and how I imagine whole system interacts with each other.

Generally, in Rust compiler, the lifetimes are only relevant during type-checking and borrow-checking, after that, the compiler erases all the lifetimes, the compiler sees &'a i32 and &'static i32 as the exact same thing: a pointer to an integer. This means that, up to the monomorphization stage, the compiler doesn't see any lifetimes in the function body.

Therefore, to make sure that during the monomorphization phase the compiler can still correct resolve the correct impl while having none knowledges related to lifetimes. We must ensure that the impl selection can't depend on the lifetime.

First, we treat lifetimes as irrelevant to type specificity and groundedness.

trait Test {}

// I want this impl to be the general case
default impl<'a, T> Test for &'a T {}

// I want this impl to be the specialized case
impl<'a, T> Test for &'static T {}

In this code example, we would treat them as ambiguous implementation. Both &'a T and &'static T are considered to have the same specificity.

Here's an another example:

trait Fizz { fn fizz(self); }

default impl<T: 'static> Fizz for &'static T { ... }

pub fn use_test<'a>(a: &'a i32) {
    // immediately resolves to the above impl with additional
    // `'a: 'static` bound. `'a` isn't considered in groundedness checking
    a.fizz();
}

Second: this system always consider different lifetimes equal.

Consider following this example:

trait Fizz { fn fizz(self); }

// the general impl
default impl<T> Fizz for T { fn fizz(self) { println("general"); }

// the specialized impl
impl<T> Fizz for (T, T) { fn fizz(self) { println("specialized"); }

fn use_fizz_weirdly<'a>(param: (&'a i32, &'static i32)) {
    // what should this be resolved to?
    param.fizz();
}

Under this system, I propose that it should be the specialized implementation even though the 'a and 'static lifetimes are different.

Surprisingly we treat &'a i32 and &'static i32 as equal! but with a twist: it generates further constraints.

In this case, it would consider to shrink the 'static lifetime instead because it's covariant.

In conclusion, these restrictions make the specialization related to lifetimes entirely impossible, however, this make the system sound in presence of lifetimes.

Building a Query-Based Incremental Compilation Engine in Rust

Simmypeet — Tue, 23 Sep 2025 17:08:19 +0000

Building an incremental compiler is a challenging task, and there are many possible architectures to go with. One of the recently popular architectures I've seen is the "Query-Based Architecture". This is the architecture that I believe the Rust compiler and LSP use.

In this blog, I'll share my experience of writing a query-based incremental compilation engine in Rust. I'll show my approach and implementation of this architecture.

Note that this is part of the implementation for my custom programming language, called "Pernix". The source code can be found at this GitHub link.

From Traditional Pipeline Compiler

This will briefly introduce the concept of "Query-Based Architecture". There are lots of great articles online explaining how it works, but in this section, we'll briefly go through how this approach works.

The most intuitive way to architect a compiler is a pipeline-based one. It easily maps well to each of the compilation phases. For example, the pipeline will be from lexing, parsing, type-checking, IR generation, to code generation. Each stage output is the input for the next step and is done sequentially. For instance, the token stream from lexing will be the input for the parser in the next step.

Typically, the whole compiler operates in each stage at a time. For example, the compiler has to build the whole one big symbol table artifact first before it can proceed to the type-checking or IR generation.

To Query-Based Compiler

In this architecture, every compiler knowledge is represented as a query and each query is very fine-grained; in contrast with the traditional pipeline, each step is very coarse-grained.

To illustrate the coarse vs fine-grain, in query-based architecture, we typically have a query like "the return type of function X", whereas the pipeline would be "build the whole one big symbol table" and then access the function X defined in that table and return its return type.

The above image shows how coarse-grained each step in the pipeline is; it has to build the whole symbol table even though we might only need some of the information.

Whereas, in query-based architecture, each of information is represented as a very fine-grained query, it's possible to query for only specific information without having to deal with other irrelevant information.

Query Dependency Graph

It's common that to compute one query, it requires other queries in the process.

The above diagram shows how one query can depend on another query. For example, if the compiler wants to know the return type of function "X", the query that computes the return type runs, and that particular query requires the abstract syntax tree of the function "X" in the process.

In this query-based architecture, another crucial information for incremental invalidation is the dependency graph. The dependency graph is represented as a "Directed Acyclic Graph" (DAG) showing what depends on what. When the incremental compiler starts, it will use this dependency graph to determine what queries can be reused and what needs to be recomputed.

In this blog, we'll not dive deep into the invalidation algorithm. This great article from Medium explains the algorithms in detail.

Implementing the Query Engine

In this section, we'll dive into how I implement the query-based architecture. I'll assume that you have a basic idea of how the algorithm works. If not, I strongly suggest this great article Salsa Algorithm Explained.

In my compiler, everything is done through the central Engine. It's a mediator for executing a query. For example, if I need to know the return type of a particular function.

fn do_something(engine: &Engine, function_id: SymbolID) {
    let return_ty = engine.query(ReturnType(functino_id));
    // ...
}

In my implementation, there are three main parts: the Key trait, the Executor trait, and the Engine.

The `Key` trait

The Key trait is defined simply as follows:

pub trait Key {
    type Output
}

That's it, this trait is used to define what the query input is and what the output is. The type that implements the Key itself is the input, and the associated type Key::Output is the output type.

Note that this trait doesn't specify how the query's done, we'll discuss how the query computes later.

For the previous example, the query that defines the return type of a particular function symbol would look like this.

pub struct ReturnTypeKey(SymbolID);

impl Key for ReturnTypeKey {
    type Output = Type;
}

The `Executor` trait

Next, the Executor trait defines how the query is implemented. It's defined similar to this:

pub trait Executor<K: Key> {
    pub fn execute(
        &self,
        key: &K,
        engine: &Engine
    ) -> Result<K::Output, Error>;
}

The Executor trait accepts a generic parameter K: Key -- a query that this executor implements. This Executor trait is similar to the "implementation", "definition" of the query, whereas the Key trait is similar to "interface", "declaration", "contract" for the query.

Note that the executor function accepts an engine where you can query for another dependencies required.

For example, to implement the Executor<ReturnTypeKey> it might look something similar to this:

pub struct ReturnTypeExecutor;

impl Executor<ReturnTypeKey> for ReturnTypeExecutor {
    pub fn execute(
        &self,
        key: &ReturnTypeKey,
        engine: &Engine,
    ) -> Result<Type, Error> {
        // this query depends on the AST of this function
        let fn_ast = engine.query(FunctionAstKey(key.0)).await?;

        Ok(process_type_ast(fn_ast.return_type_ast))
    }
}

The `Engine` object

Finally, the Engine is where everything is tied up together. This answers the question of "How the Key trait and Executor work together?".

pub struct Engine { ... }

impl Engine {
    pub fn query<K: Key>(&self, key: &K) -> Result<K::Output, Error> { ... }

    pub fn register_executor<K: Key, E: Executor<K>>(&self, key: &K, executor: E) { ... }
}

When the compiler starts, the Engine is created and every Key that will be executed is registered with the appropriate Executor.

When the query is invoked, the executor registered will be retrieved and executed.

Type Erasure in Engine

In order to store an arbitrary type of executors, we use some dynamic dispatch, dyn Any, and fn pointers trick to achieve runtime type erasure. It might look similar to something like this.

fn execute_fn<E: Executor<K>, K: Key>(
    dyn_executor: &dyn Any,
    dyn_key: &dyn Any,
    dyn_result: &mut dyn Any,
) {
    let executor =
        dyn_executor.downcast_ref::<E>().expect("Executor type mismatch");

    let key = dyn_key.downcast_ref::<K>().expect("Key type mismatch");

    let result = dyn_result
        .downcast_mut::<Option<Result<K::Output, Error>>>()
        .expect("Result type mismatch");

    *result = Some(executor.execute(key));
}

pub struct Registration {
    executor_fn: fn(&dyn Any, &dyn Any, &mut dyn Any),
    executor_dyn: Box<dyn Any + Send + Sync>,
}

pub struct Registry {
    executors: HashMap<TypeId, Registration>,
}

impl Registry {
    pub fn register<E: Executor<K> + 'static, K: Key + 'static>(&mut self) {
        let executor = E::new();

        self.executors.insert(TypeId::of::<K>(), Registration {
            executor_fn: execute_fn::<E, K>,
            executor_dyn: Box::new(executor),
        });
    }
}

As shown above, it heavily uses dyn Any and downcasting in order to achieve executor registration and retrieval. Every executor is boxed and turned into a Box<dyn Any>, and the executor's fn pointer is stored alongside for further execution.

To compute a query, the engine will retrieve the Registration using the TypeId of the query and use the executor_fn to compute.

pub struct Engine {
    registry: Registry,
    query_states: HashMap<BoxedKey, QueryResult>,
    version: Version,
}

impl Engine {
    pub fn query<K: Key>(&self, key: &K) -> Result<K::Output, Error> {
        let registration =
            self.registry.executors.get(&TypeId::of::<K>()).ok_or_else(
                || Error::msg("No executor for the given key type"),
            )?;

        let mut result: Option<Result<K::Output, Error>> = None;

        (registration.executor_fn)(
            &*registration.executor_dyn,
            key,
            &mut result,
        );

        let result = result.expect("Executor did not set the result")

        self.query_states.insert(
            key.boxed(), 
            QueryResult::Computed(result, self.version)
        );

        result
    }
}

The above code snippets should give you the simple idea of how to implement the Engine for the incremental compiler. There are some concepts that I've not shown in the above code snippets.

Supporting Infrastructure

These three main components discussed are the heart of the incremental compilation. However, these are not all; there are several components needed in order to build a fully functional incremental compiler.

Versioning and Dependency Tracking

The Engine maintains a version counter that will be incremented each time the compiler runs. The first run of the compiler sets the version to 0, and the next run increments it to 1, and so on.

Every time the query is computed, the Engine saves the result of the query along with this three information: "when it was last updated/created", "when it was last verified", "the unique fingerprint", and "what are the dependencies".

pub struct QueryResult {
    pub query_result: DynResult,
    pub last_updated: VersionNumber,
    pub last_verified: VersionNumber, 
    pub fingerprint: Hash128,
    pub dependencies: Vec<DynQuery>
}

pub struct Engine {
    ...
    query_states: HashMap<DynQuery, QueryResult>
    ...
}

These are the crucial information needed for determining what queries need to be recomputed. I'll briefly explain each of these fields.

last_updated and last_verified are used to determine whether the query is "stale" or not by comparing them with the current Engine's global version counter.
fingerprint is a 128-bit hash used to determine whether or not the query result computed each time has changed.
dependencies is used when the query is "stale" and has to verify whether or not its dependencies have updated.

To track the dependencies of each query, every time the executor is retrieved and executed, the Engine can maintain something like current_executing_queries stack. Soon, when the executor depends on other queries via engine.query(QueryKey) interface, the engine can observe that there's a dependency between queries and therefore, can build a dependency list based on that.

impl Engine {
    pub fn query<K: Key>(&self, key: &K) -> Result<K::Output, Error> {
        let source = self.get_currently_executing_query();
        let source_query_state = self.query_states.get(source);

        source_query_state.add_dependency(key);

        // ....
    }
}

Cyclic Tracking

Cyclic Queries are not allowed in this implementation; the Engine has to maintain some sort of "Query Call Stack" to detect the cyclic. The default behavior when detecting the cyclic is up to the implementation. In my implementation, when a cyclic dependency is detected, the Engine returns Err(CyclicDependency) and the error is propagated up through the query call stack.

Fingerprinting

As mentioned earlier, after the query result is computed, the Engine calculates the 128-bit hash to compare the equality of the query results between each version.

For instance, the query was computed at version 1 and had a fingerprint of "0xABC". When the query was invalidated and recomputed at version 3, and the fingerprint turns out to be "0xXYZ". As a result, the fingerprint between two version mismatches. The Engine now has to update the last_updated to 3 and fingerprint to "0xXYZ".

In my implementation, the fingerprint mechanism is done via a StableHash trait similar to what std::hash::Hash and what the "rustc" compiler internally uses for its fingerprinting.

The StableHash has a similar interface to std::hash::Hash except that it produces a 128-bit hash, works on HashMap and HashSet, and is consistent between each run.

Note that you might need an extra proc-macro has to be written to generate a StableHash implementation for each type automatically.

Persistence

In order to reuse the result for the next compilation run, the query results and all of their metadata need to be saved to disk. I've tried to serialize and deserialize one big HashMap before, and it results in very poor performance. In the later iteration, I ended up using the Key-Value store database for saving and retrieving query results from disk. This has several advantages:

The compiler doesn't have to deserialize one big Engine at startup, requiring a very long time to deserialize all the data. Each query can be retrieved from the KV database at a time.
The process of saving the query result can be sent to the background thread. The background thread can serialize and save the query to the KV database without blocking the main compiler sequence.

Multithreading Synchronization

To take advantage of this architecture to its fullest potential, you need to implement the Engine that allows the queries to be invoked from multiple threads. This is no easy task; I've encountered lots of problems while trying to implement multithreading support for it.

Lock Contention: The Engine has to have as few locks as possible. dashmap crate is an excellent choice for a concurrent map compared to RwLock<HashMap> counterparts. It's also a good idea to separate the fast path and slow path in the query. To illustrate, the Engine always obtains the read (shared) lock to the dashmap first to determine whether or not the query has been computed (the fast path). Subsequently, if the query hasn't yet been computed or is staled, the write (unique) lock is obtain in order to save result (the slow path).
Unique Execution: Imagine a scenario where there are queries A and B executed on different threads, and both of them require query C. The Engine must only allow one thread to execute query C and has to block all other threads until query C is computed.

Suppose the Thread Green (from query A) got to compute the query C.

The Thread Blue (from query B) has to wait.

Thread Pool Starvation: I initially used rayon as a thread pool. However, the scenarios described earlier, where there are some blocking/locking in the Engine, are a big performance killer in the thread pool. Even worse, it could result in a very difficult-to-debug deadlock. Due to this reason, I decided to go with async. Using async allows the thread to yield its execution when it's waiting for another thread to finish computing the query. This not only solves the thread pool starvation problem, but also increases the throughput of the Engine.

Pros and Cons

"Everything is a trade off"
- Software Design and Architecture Prof.

Pros

Ease of Testing: The Engine resembles the DI container that you might've seen in popular web frameworks. It's very easy to implement a unit test by swapping out the executor for the mock ones in order to achieve isolation.
Easy Parallelization: Due to the nature of "input-output" with minimal mutable state, it's easy to create multiple threads to query specific information (once your Engine is implemented to support multithreading).
On Demand: Since each of the queries is fine-grained, only the needed queries are run without having to invoke the whole compiler pipeline.

Cons

Infrastructure Setup: This requires an effort to set up a query engine before you implement any other compiler-specific logic. Though there are lots of library that implements this for you.
Boilerplate: This implementation can suffer from requiring lots of boilerplate: having to define a query key, executor, and then register the executor to the engine. However, the macro can help with these issues, but it comes at a cost of less readable code.
Memory Consumption: The Engine has to keep track of the query dependencies and states, which use lots of memory. In a large source file, the number of queries in the program can easily go to hundreds of thousands and up to millions.

Conclusion

We've explored the basic components of building the incremental query engine. There are still lots of details that have not been covered, but this should have given you a basic idea to build your own query engine.

You can see the exact implementation of my query engine in my GitHub Repository with the in-depth Architecture Doc for my specific implementation.

Crafting a Compiler in Rust: Syntactic Analysis

Simmypeet — Sat, 10 Dec 2022 22:25:35 +0000

In this post, I will introduce you to the basics of Syntactic Analysis. Moreover, we'll write a basic parser that takes the token stream and converts it into Abstract Syntax Trees.

Update on the Lexer

Before going into writing the parser, let me inform you about changes I've made to the Lexer🌟.

Now, the Lexer supports two more literal constant categories: Floating and Boolean.
The literal suffix is now available. For example, in the code let number = 0i64, the 0i64 has a literal suffix being i64 and a literal value of 0.

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum LiteralConstantType<'a> {
    Integer {
        value: &'a str,
        literal_suffix: Option<&'a str>,
    },
    Float {
        value: &'a str,
        literal_suffix: Option<&'a str>,
    },
    Boolean(bool),
}

/// Enumeration containing all patterns of token
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum TokenKind<'a> {
    Identifier,
    Space,
    Comment,
    Keyword(Keyword),
    LiteralConstant(LiteralConstantType<'a>),
    Punctuator(char),
    EndOfFile,
}

Full code changes to the pernix_lexer module is available.

Syntactic Analysis Basics

As mentioned in the introduction, The Syntactic Analysis continues from the Lexical Analysis phase. But what does it do?

It takes a token stream produced in the earlier phase into a meaningful data structure called Abstract Syntax Tree (AST). Additionally, this is the phase where all the syntactic errors are caught.

The Abstract Syntax Tree

The Abstract Syntax Tree is a tree representation of the code fed to the compiler. It contains only the crucial information of the code and extracts away the syntactic detail of the language.

Take the following code snippets as an example:

function add(a, b) {
    return a + b;
}

def add(a, b):
    return a + b

There's JavaScript and Python code above. Both functions from both languages behave precisely the same. If both code snippets are parsed, it will produce an AST similar to this:

In JSON representation

{
  "function": {
    "parameters": [
      "a",
      "b"
    ],
    "statements": [
      {
        "type": "ReturnStatement",
        "expression": {
          "type": "BinaryOperatorExpression",
          "left": {
            "type": "VariableExpression",
            "variable": "a"
          },
          "operator": "+",
          "right": {
            "type": "VariableExpression",
            "variable": "b"
          }
        }
      }
    ]
  }
}

The AST produced contains all the crucial information about the function.

Its parameter names and count.
The statement inside the function body; contains only one return statement, which returns an expression of a + b.

Even though Javascript and Python have different syntaxes, the AST produced by both languages here would be similar or identical since AST doesn't consider the language's syntax detail. That's why it's called Abstract Syntax Tree.

The Goal

Before diving into writing the parser, it's necessary to scope the feature of the parser. What features will be included? What does the code that will be parsed look like?

Therefore, I made a reference snippet of code to guide us when writing the parser:

using Simmypeet.Math;

namespace Simmypeet {
    namespace Math {
        int32 Add(int32 a, int32 b) {
            return a + b;
        }

        int32 Subtract(int32 a, int32 b) {
            return a + b;
        }
    }

    int32 Fibonacci(int32 n) {
        if (n == 0) {
            return 0;
        }
        else if (n == 1) {
            return 1;
        } 
        else {
            return Add(Fibonacci(n - 1) + Fibonacci(n - 2));
        }
    }
}

The code above is similar to C#, which is😁. It also tells us a lot about what features we have to implement.

If-else statement
Namespace
Using declaration (bringing the namespace scope)
Function call
Arithmetic operation
Comparison
Function declaration

The ultimate goal is to implement a parser that correctly parses the above code. Now, it's time to write some code and get our hands dirty!

The `pernix_parser` Crate

Let's start by creating a new crate named pernix_parser.

cargo new --lib compiler/pernix_parser

[workspace]
members = [
    "compiler/pernix_project",
    "compiler/pernix_lexer",
    "compiler/pernix_parser",
]

Before going into implementing the actual parser, it's necessary to write all sorts of Abstract Syntax Tree data structures first.

The `abstract_syntax_tree` Module

We'll create a new module called abstract_syntax_tree in the pernix_parser crate. This module holds all data structures relating to the Abstract Syntax Tree.

When producing an AST, it would be beneficial to include the source code position the parser parsed to make an AST. So, in the later phase, when errors occur, the error message can consist of the position in the source code that produces the errors.

Therefore, in pernix_parser/abstract_syntax_tree.rs, we'll write a wrapper struct consisting of two fields: the abstract syntax tree value and its position range.

/// A wrapper around a value that also contains the position of the value in the
/// source code
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct PositiionWrapper<T> {
    pub position: Range<SourcePosition>,
    pub value: T,
}

Next, let's write an enum that holds all the values of binary operators.

/// List of all available binary operators
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum BinaryOperator {
    Add,
    Subtract,
    Asterisk,
    Slash,
    Percent,
    LessThan,
    GreaterThan,
    LessThanEqual,
    GreaterThanEqual,
    Equal,
    NotEqual,
    And,
    Or,
}

Next, write an enum that contains all the values of unary operators.

/// List of all available unary operators
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum UnaryOperator {
    Plus,
    Minus,
    LogicalNot,
}

Next, include another enum with all the ways to refer to a type.

/// An enumeration containing all kinds of types referenced in the program
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Type {
    Identifier(String),
    Array {
        element_type: Box<Type>,
        size: usize,
    },
}

For example, a code with int32[5], an array of five int32s, would produce an Type enum in the code similar to this:

Type::Array {
    element_type: Box::new(Type::Identifier("int32".to_string)),
    size: 5
}

Next, let's create a submodule inside the abstract_syntax_tree module called expression. This submodule contains all the code related to Expresison Abstract Syntax Tree.

Expression refers to a code in the program that can be evaluated and yields a value. For example, in the x = 4 + 3 statement, the 4 + 3 is an expression.

Now, let's write an enum containing all the forms of an expression.

/// Enumeration containing all possible expressions
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Expression<'a> {
    /// Represents an expression of the form `left operator right`
    BinaryExpression {
        left: Box<PositiionWrapper<Expression<'a>>>,
        operator: PositiionWrapper<BinaryOperator>,
        right: Box<PositiionWrapper<Expression<'a>>>,
    },

    /// Represents an expression of the form `operator operand`
    UnaryExpression {
        operator: PositiionWrapper<UnaryOperator>,
        operand: Box<PositiionWrapper<Expression<'a>>>,
    },

    /// Represents an expression of the form `literal`
    LiteralExpression(LiteralConstantType<'a>),

    /// Represents an expression of the form `identifier`
    IdentifierExpression {
        identifier: PositiionWrapper<String>,
    },

    /// Represents an expression of the form `function_name(arguments)`
    FunctionCallExpression {
        function_name: PositiionWrapper<String>,
        arguments: Vec<PositiionWrapper<Expression<'a>>>,
    },
}

The BinaryExpression variant consists of two operand expressions separated by one binary operator, such as 4 + 5.
The UnaryExpression variant consists of an operand expression and a unary operator, for example, !true.
The LiteralExpression is straightforward; the expression yielded from the hardcoded value.
The IdentifierExpression refers to a reference to a variable.
The FunctionCallExpression refers to a call to a specific function by name and by providing arguments.

Next, let's write all the variants of the statement.

/// Enumeration containing all kinds of statements
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Statement<'a> {
    /// Represents a statement of the form `return expression;`
    ReturnStatement {
        expression: PositiionWrapper<Expression<'a>>,
    },

    /// Represents a statement of the form `expression;`
    ExpressionStatement {
        expression: PositiionWrapper<Expression<'a>>,
    },

    /// Represents a statement of the form `let identifier = expression;`
    VariableDeclarationStatement {
        identifier: PositiionWrapper<String>,
        expression: PositiionWrapper<Expression<'a>>,
    },

    /// Represents an if statement of the form `if (condition) then_statement
    /// else else_statement`
    IfStatement {
        condition: PositiionWrapper<Expression<'a>>,
        then_statement: Vec<PositiionWrapper<Statement<'a>>>,
        else_statement: Option<Vec<PositiionWrapper<Statement<'a>>>>,
    },
}

Statement is a fragment of code that carries out a specific action in the program.

The ReturnStatement variant represents a statement that returns a value from a function.
The ExpressionStatement variant represents a statement that evaluates an expression.
The VariableDeclarationStatement variant represents a statement that declares a new variable.
The IfStatement variant represents a statement that executes a block of code if a condition is true. It can also execute a different block of code if the condition is false.

Next, let's create a new submodule inside the abstract_syntax_tree module called declaration. This module holds all the AST code related to all the declarations that you would define in a program, such as namespace declarations, functions, and classes.

/// A declaration is a statement that declares a new name in the current scope.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Declaration<'a> {
    /// Represents a namespace declaration of the form `namespace namespace_name { declarations* }`
    NamespaceDeclaration {
        namespace_name: PositiionWrapper<String>,
        declarations: Vec<PositiionWrapper<Declaration<'a>>>,
    },

    /// Represents a function declaration of the form `type function_name(parameters) { statements* }`
    FunctionDeclaration {
        function_name: PositiionWrapper<String>,
        parameters: Vec<PositiionWrapper<String>>,
        return_type: PositiionWrapper<Type>,
        body: Vec<PositiionWrapper<Statement<'a>>>,
    },

    /// Represents a namespace using statement of the form `using namespace_name;`
    UsingStatement{
        namespace_name: PositiionWrapper<String>,
    },
}

The NamespaceDeclaration variant represents a declaration that declares a new namespace and contains other declarations inside it.
The FunctionDeclaration variant represents a declaration that declares a new function and contains a list of statements inside it.
The UsingDeclaration variant represents a declaration that imports a namespace into the current scope.

The `error` Module

Now, it's time to implement an error module. This module will contain all the error types that we will use in the parser.

/// Enumeration containing all possible contexts that the error can occur in.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Context {
    Program,
    Statement,
    Expression,
    Namespace,
}

/// Enumeration containing all possible errors that can occur during parsing.
#[derive(Debug, Clone)]
pub enum Error<'a> {
    LexicalError(pernix_lexer::error::Error<'a>),
    KeywordExpected {
        expected_keyword: Keyword,
        found_token: Token<'a>,
        source_reference: &'a SourceCode,
    },
    IdentifierExpected {
        found_token: Token<'a>,
        source_reference: &'a SourceCode,
    },
    PunctuatorExpected {
        expected_punctuator: char,
        found_token: Token<'a>,
        source_reference: &'a SourceCode,
    },
    UnexpectedToken {
        context: Context,
        found_token: Token<'a>,
        source_reference: &'a SourceCode,
    },
}

The Context enumeration contains all the possible contexts in which the error can occur. For example, if the error occurs in the Program context, it means that the error occurred in the top level of the program.
The Error enumeration contains all the possible errors that can occur during parsing. The LexicalError variant is used to wrap the error that occurred during the lexical analysis. The other variants are used to represent the errors that occurred during the parsing.

Writing The Parser

The parser is a state machine that behaves similarly to the lexer. It turns the token stream into a meaningful AST data structure. The parser that we will write is a combination of Recursive Descent Parsing and Operator-Precedence Parsing.

/// Represents a struct that parases the given token stream into abstract syntax
/// trees
pub struct Parser<'a> {
    // The lexer that is used to generate the token stream
    lexer: Lexer<'a>,
    // the accumulated tokens that have been tokenized by the lexer so far
    accumulated_tokens: Vec<Token<'a>>,
    // the accumulated errors that have been found during parsing so far
    accumulated_errors: Vec<Error<'a>>,
    // The current position in the source code
    current_position: usize,
    // Flag that indicates whether the parser should produce errors into the
    // list or not
    produce_errors: bool,
}

In the following sections, I'll explain the fields of the Parser struct.

The lexer field is used to generate the token stream. It's a struct that we've already implemented in the previous post.
The accumulated_tokens field is used to store the tokens that have been tokenized by the lexer so far. The parser will use this field to get the token already tokenized by the lexer.
The accumulated_errors field stores the errors found during parsing.
The current_position field stores the current token stream index.
The produce_errors field indicates whether the parser should produce errors into the list or not. This field prevents the parser from producing errors when recovering from an error.

Let's create a new constructor for the Parser struct.

impl<'a> Parser<'a> {
    /// Creates a new parser instance from the given source code
    pub fn new(source_code: &'a SourceCode) -> Self {
        let mut lexer = Lexer::new(source_code);
        let mut accumulated_errors = Vec::new();

        // get the first token
        let accumulated_tokens = vec![{
            let token_return;
            loop {
                match lexer.lex() {
                    Ok(token) => {
                        token_return = token;
                        break;
                    }
                    Err(err) => {
                        accumulated_errors.push(Error::LexicalError(err));
                    }
                }
            }
            token_return
        }];

        Self {
            lexer,
            accumulated_tokens,
            accumulated_errors,
            current_position: 0,
            produce_errors: true,
        }
    }
}

The function creates a new Lexer instance from the source code. First, it gets the first token from the lexer and stores it in the accumulated_tokens field. Then, it creates a new Parser instance and returns it.

Now, let's implement the next function. This function will return the current token and move the current_position field to the next token. If the current_position field is equal to the length of the accumulated_tokens field, it means that the parser has reached the end of the token stream. In this case, the function will get the next token from the lexer and store it in the accumulated_tokens field. Moreover, if the lexer encounters an error, the function will store the error in the accumulated_errors field.

impl<'a> Parser<'a> {
    // Gets the current token stream and moves the current position forward
    pub(crate) fn next(&mut self) -> &Token<'a> {
        // need to generate more tokens
        if self.current_position == self.accumulated_tokens.len() - 1 {
            let new_token;
            loop {
                match self.lexer.lex() {
                    Ok(token) => {
                        new_token = token;
                        break;
                    }
                    Err(err) => {
                        self.accumulated_errors.push(Error::LexicalError(err));
                    }
                }
            }

            // append the new token to the accumulated tokens
            self.accumulated_tokens.push(new_token);
        }
        // panic if the current position is greater than or equal the length
        else if self.current_position >= self.accumulated_tokens.len() {
            panic!("current position is greater than or equal the length of the accumulated tokens");
        }

        // increment the current position
        self.current_position += 1;

        &self.accumulated_tokens[self.current_position - 1]
    }
}

Now, let's implement the peek function. This function will simply index the
accumulated_tokens field with the current_position field. It will not
move the position forward.

impl<'a> Parser<'a> {
    // Gets the current token without moving the current position forward
    fn peek(&self) -> &Token<'a> {
        &self.accumulated_tokens[self.current_position]
    }

    // Gets the token back by one position without moving the current position
    fn peek_back(&self) -> &Token<'a> {
        &self.accumulated_tokens[self.current_position - 1]
    }
}

Before going into writing the parsing function, let's discuss insignificant tokens. In the previous post, we implemented the lexer that can tokenize the comments and whitespaces into tokens. However, in most cases, the syntax doesn't care about these whitespaces and comments. For example, the following code is valid in the language.

let x =   5;          // extra spaces? it's okay!
let x=5;              // no spaces? it's okay too!
let x = /*hello?*/ 5; // comment in the middle? that's fine!

However, in some cases, it can be crucial. For example, the only difference between the comparison operators == and two assignment operators = is the space between them. In the following code, the first line will assign the value of 5 to the variable x; the second line will compare the value of x with 5; the rest is invalid.

x = 5;            // yes
x == 5;           // yeah
x = = 5;          // ???
x =/*hello?*/= 5; // what?

Therefore, we need to implement a function that can skip insignificant tokens. The function will be called move_to_significant and implemented as follows.

impl<'a> Parser<'a> {
    /// Moves the current position to the next significant token
    pub(crate) fn move_to_significant(&mut self) {
        while !self.peek().is_significant_token() {
            self.next();
        }
    }
}

And on top of that, implement the function that moves to the next significant token, returns it, and moves the position forward.

impl<'a> Parser<'a> {
    // Moves the current position to the next significant token and emits it
    pub(crate) fn next_significant(&mut self) -> &Token<'a> {
        self.move_to_significant();
        self.next()
    }
}

And if you are wondering how the is_significant_token is implemented, it is as follows.

impl<'a> Token<'a> {
    /// Returns a boolean indicating whether this [`Token`] is a significant.
    /// Insignificant tokens are spaces and comments.
    pub fn is_significant_token(&self) -> bool {
        match self.token_kind() {
            TokenKind::Space | TokenKind::Comment => false,
            _ => true,
        }
    }
}

Next, let's implement the function that appends an error to the accumulated_errors field if the produce_errors field is true.

impl<'a> Token<'a> {
    // Appends the given error to the list of accumulated errors if the
    // `produce_errors` flag is set to true. Moreover, it also rolls the parser
    // position back to the `rollback_position`.
    #[must_use]
    pub fn append_error<T>(&mut self, error: Error<'a>) -> Option<T> {
        if self.produce_errors {
            self.accumulated_errors.push(error);
        }

        None
    }
}

Now that we've got the basic functions, let's implement the parsing function.

Parsing The Qualified Name

Let's start with something simple. Let's implement the function that parses the qualified name. The qualified name is the scope's name, such as Simmypeet.Compiler.Parser. It follows the pattern of an identifier followed by a dot, followed by another identifier, and so on.

pub fn parse_qualified_name(&mut self) -> Option<PositiionWrapper<String>> {
    self.move_to_significant();
    let starting_position = self.peek().position_range().start;

    // the string to return
    let mut string = String::new();

    // expect the first identifier
    if let TokenKind::Identifier = self.next().token_kind() {
        string.push_str(self.peek_back().lexeme());
    } else {
        return self.append_error(Error::IdentifierExpected {
            found_token: self.peek_back().clone(),
            source_reference: self.source_code(),
        });
    }

    // found additional scopes
    while matches!(self.peek().token_kind(), TokenKind::Punctuator('.')) {
        // eat the dot
        self.next();

        string.push('.');

        // expect the next identifier
        if let TokenKind::Identifier = self.next().token_kind() {
            string.push_str(self.peek_back().lexeme());
        } else {
            return self.append_error(Error::IdentifierExpected {
                found_token: self.peek_back().clone(),
                source_reference: self.source_code(),
            });
        }
    }

    Some(PositiionWrapper {
        position: starting_position..self.peek_back().position_range().end,
        value: string,
    })
}

The function first moves the position to the next significant token, as sometimes the parser's position is not at the significant token. Then, it records the starting position of the qualified name. This pattern will be used in the rest of the parsing functions.

It then expects the first identifier and stores it in the string variable. If the first token is not an identifier, it records an error and returns None.

Finally, it checks if a dot follows the identifier. If it is, it eats the dot, eats more identifiers, and pushes them to the string variable. It then checks again if the next token is a dot. If it is, it repeats the process. If it is not, it returns the string variable.

Parsing The Using Statement

Next, let's implement the function that parses the using statement. The statement uses the qualified name we've implemented in the previous section. The parser will expect the using keyword, the qualified name, and a semicolon.

/// Parses the current token stream as a using_statement
///
/// Using_Statement:
///   `using` Qualified_Name `;`
pub fn parse_using_statement(
    &mut self,
) -> Option<PositiionWrapper<Declaration<'a>>> {
    // move to the first significant token
    self.move_to_significant();
    let starting_position = self.peek().position_range().start;

    // expect the `using` keyword
    if !matches!(
        self.next().token_kind(),
        TokenKind::Keyword(Keyword::Using)
    ) {
        return self.append_error(Error::KeywordExpected {
            expected_keyword: Keyword::Using,
            found_token: self.peek_back().clone(),
            source_reference: self.source_code(),
        });
    }

    let qualified_name = self.parse_qualified_name()?;

    // expect the semicolon
    if !matches!(
        self.next_significant().token_kind(),
        TokenKind::Punctuator(';')
    ) {
        return self.append_error(Error::PunctuatorExpected {
            expected_punctuator: ';',
            found_token: self.peek_back().clone(),
            source_reference: self.source_code(),
        });
    }

    Some(PositiionWrapper {
        position: starting_position..self.peek_back().position_range().end,
        value: Declaration::UsingStatement {
            namespace_name: qualified_name,
        },
    })
}

Parsing The Namespace Declaration

This one is a bit more complicated. Before we start, let's look at our error recovery strategy. In a naive approach, we can stop parsing if the parser encounters an error. However, this is not a good idea, as it discards the rest of the possible valid tokens. Instead, we can use the error recovery strategy to continue parsing the rest of the tokens after the error.

We'll use the Panic Mode Error Recovery strategy in our cases. In this strategy, after the parser encounters an error, it will look for the next valid token and continue working from there, discarding the invalid tokens. This strategy is the most used error recovery strategy, as it is simple to implement and effective.

Let's put us in the perspective of the parser. Consider the following code:

mod simmypeet {
    use something;
    use something_else;

    1234 420 // Oops! it should not be here

    mod name {}
}

As you can see, there're number literals in the middle of the module declaration. When the parser encounters the number literals, it will record an error saying something like "unexpected token, number literal is not expected here". Then, it will look for the next valid token, which is the mod keyword. Our parser will not simply continue parsing from the 1234 token then to encounter another 420 token and record another error. Instead, it will skip the 1234 and 420 tokens, and continue parsing from the next mod name declaration.

Now that we've got the error recovery strategy, let's implement the namespace declaration parsing function. The parser will expect the namespace keyword, followed by the qualified identifier, followed by the opening curly brace.

/// Parses the current token stream as a namespace declaration
///
/// Namespace_Declaration:
///    `namespace` Qualified_Name `{` Declaration* `}`
pub fn parse_namespace_declaration(
    &mut self,
) -> Option<PositiionWrapper<Declaration<'a>>> {
    // move to the first significant token
    self.move_to_significant();
    let starting_position = self.peek().position_range().start;

    // expect the `namespace` keyword
    if !matches!(
        self.next().token_kind(),
        TokenKind::Keyword(Keyword::Namespace)
    ) {
        return self.append_error(Error::KeywordExpected {
            expected_keyword: Keyword::Namespace,
            found_token: self.peek_back().clone(),
            source_reference: self.source_code(),
        });
    }

    let namespace_name = self.parse_qualified_name()?;

    // expect the opening curly bracket
    if !matches!(
        self.next_significant().token_kind(),
        TokenKind::Punctuator('{')
    ) {
        return self.append_error(Error::PunctuatorExpected {
            expected_punctuator: '{',
            found_token: self.peek_back().clone(),
            source_reference: self.source_code(),
        });
    }

    /* More to come ... */
}

Next, we'll instantiate a new Vec to store the declarations inside the namespace. Then, we'll start a loop that will parse the declarations inside the namespace. The loop is terminated when the parser encounters the closing curly brace or reaches the end of the file.

/// Parses the current token stream as a namespace declaration
///
/// Namespace_Declaration:
///    `namespace` Qualified_Name `{` Declaration* `}`
pub fn parse_namespace_declaration(
    &mut self,
) -> Option<PositiionWrapper<Declaration<'a>>> {
    /* From the previous code ... */

    // loop through all the declarations
    let mut declarations = Vec::new();

    // move to the next significant token
    self.move_to_significant();

    // loop through all the declarations until closing curly bracket or
    // EOF is found
    while !matches!(
        self.peek().token_kind(),
        TokenKind::Punctuator('}') | TokenKind::EndOfFile
    ) {
        let declaration = match self.peek().token_kind() {
            TokenKind::Keyword(Keyword::Namespace) => {
                self.parse_namespace_declaration()
            }
            TokenKind::Keyword(Keyword::Using) => {
                self.parse_using_statement()
            }
            _ => self.append_error(Error::UnexpectedToken {
                context: Context::Namespace,
                found_token: self.peek().clone(),
                source_reference: self.source_code(),
            }),
        };

        if let Some(declaration) = declaration {
            declarations.push(declaration);
        } else {
            // skip to the next available declaration all delimeter
            self.skip_to(|token| {
                matches!(
                    token.token_kind(),
                    TokenKind::Keyword(Keyword::Namespace)
                        | TokenKind::Keyword(Keyword::Using)
                        | TokenKind::Punctuator('}')
                )
            });
        }

        // move to the next significant token
        self.move_to_significant();
    }

    /* More to come ... */
}

You might have noticed that we're using the skip_to method to skip to the subsequent available declaration or the closing curly brace. This method is a helper method that will bypass the tokens until the predicate returns true. In our case, we're skipping the tokens until we encounter the namespace, using, or } tokens.

Finally, we'll expect the closing curly brace and return the namespace declaration.

/// Parses the current token stream as a namespace declaration
///
/// Namespace_Declaration:
///    `namespace` Qualified_Name `{` Declaration* `}`
pub fn parse_namespace_declaration(
    &mut self,
) -> Option<PositiionWrapper<Declaration<'a>>> {
    /* From the previous code ... */

    // expect the closing curly bracket
    if !matches!(
        self.next_significant().token_kind(),
        TokenKind::Punctuator('}')
    ) {
        return self.append_error(Error::PunctuatorExpected {
            expected_punctuator: '}',
            found_token: self.peek_back().clone(),
            source_reference: self.source_code(),
        });
    }

    Some(PositiionWrapper {
        position: starting_position..self.peek_back().position_range().end,
        value: Declaration::NamespaceDeclaration {
            namespace_name,
            declarations,
        },
    })
}

Parsing The Program

Finally, we'll write the parse_program method that will parse the entire program. Luckily, the program is just a list of declarations, so we'll just loop through all the declarations and parse them similarly to how we parsed the namespace declaration.

/// Parses all token stream as a program
///
/// Program:
///  Declaration*
pub fn parse_program(&mut self) -> Option<Program<'a>> {
    let mut program = Program {
        declarations: Vec::new(),
    };

    // move to the next significant token
    self.move_to_significant();

    while !matches!(self.peek().token_kind(), TokenKind::EndOfFile) {
        let declaration = match self.peek().token_kind() {
            TokenKind::Keyword(Keyword::Namespace) => {
                self.parse_namespace_declaration()
            }
            TokenKind::Keyword(Keyword::Using) => {
                self.parse_using_statement()
            }
            _ => self.append_error(Error::UnexpectedToken {
                context: Context::Program,
                found_token: self.peek().clone(),
                source_reference: self.source_code(),
            }),
        };

        if let Some(declaration) = declaration {
            program.declarations.push(declaration);
        } else {
            // skip to the next available declaration all delimeter
            self.skip_to(|token| {
                matches!(
                    token.token_kind(),
                    TokenKind::Keyword(Keyword::Namespace)
                        | TokenKind::Keyword(Keyword::Using)
                )
            });
        }

        // move to the next significant token
        self.move_to_significant();
    }

    Some(program)
}

Summary

Phew!!😮‍💨😮‍💨 We've created a simple language parser that can understand the basic program structures. However, we're still going; in the next post, we'll continue writing the parser, which will parse the function declarations.

As always, you can find the source code for this post on GitHub

Feel free to comment if you have any thoughts, questions, feedbacks, or suggestions. I will be happy to read them 😊.

Crafting a Compiler in Rust: Lexical Analysis

Simmypeet — Thu, 08 Dec 2022 22:56:19 +0000

Let's create a project for the compiler. It'll be named pernix-lang. Inside the folder pernix-lang, the Cargo Workspace project locates here. I'll separate each different compiler phase into an individually distinct library crate.

The Pernix Project Crate

Before going into writing the compiler, let's create a crate called pernix_project.

cargo new --lib compiler/pernix_project

Add the newly created crate path in the Cargo.toml workspace file.

[workspace]
members = [
    "compiler/pernix_project",
]

The workspace should look something like this:

├── Cargo.toml
├── compiler/pernix_project
│   ├── Cargo.toml
│   └── src
│       └── src.rs

This crate contains all the code related to the language's project
such as source files, directories, targets, and libraries.

Let's write code for the pernix_project crate. I'll create a new module inside the crate named source_code. This module contains the SourceCode and SourcePosition structs; these structs involve source file inputs.

The SourceCode struct manages the content of the source file. It provides utility functions such as inspecting the source file's content by the line number.
The SourcePosition consists of two fields: line and column numbers.

Full Code Listing of source_code.rs

/// Represents a source code
pub struct SourceCode {
    source_code: String,
    source_name: String,
    new_line_ranges: Vec<Range<usize>>,
}

/// Represents a particular position in the source code, consisting of column
/// and line
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct SourcePosition {
    pub line: usize,
    pub column: usize,
}

Here's the snippet of the code of the SourceCode struct in action.

#[test]
fn test_line() {
    let source_code = SourceCode::new(
        "Hello, world!\n".to_string()
            + "My Name Is Pernix\n"
            + "I am a programming language\n"
            + "I am written in Rust\n"
            + "\n",
        "test".to_string(),
    );

    assert_eq!(source_code.line(1).unwrap(), "Hello, world!");
    assert_eq!(source_code.line(2).unwrap(), "My Name Is Pernix");
    assert_eq!(source_code.line(3).unwrap(), "I am a programming language");
    assert_eq!(source_code.line(4).unwrap(), "I am written in Rust");
    assert_eq!(source_code.line(5).unwrap(), "");
}

The Pernix Lexer Crate

Before doing the actual code, let's discuss more in-depth Lexical Analysis. Generally speaking, Lexical Analysis is the phase where the source code is fed to a lexer or scanner and converted into a stream of tokens. When working with a lexer, you will likely stumble across these terms: lexeme and token.

The lexeme is a term used to describe a sequence of characters matched by a well-defined pattern or rule.
The token is a term used to describe a syntactic category that constitutes the lexeme.

For example, the following code would produce a token stream like this:

int main() {
    return 0;
}

TokenKind	Lexeme
IDENTIFIER	int
IDENTIFIER	main
PUNCTUATOR	(
PUNCTUATOR	)
PUNCTUATOR	{
KEYWORD	return
LITERAL	0
PUNCTUATOR	;
PUNCTUATOR	}

Now that we've understood the basics of the Lexical Analysis phase, Let's create a library crate that contains the lexer for the compiler, pernix_lexer.

cargo new --lib compiler/pernix_lexer

[workspace]
members = [
    "compiler/pernix_project",
    "compiler/pernix_lexer",
]

Let's create a new module in this crate named token. This module contains the code related to the lexical token.

Now, let's write an enum with all token-kind values.

/// Enumeration containing all patterns of token
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum TokenKind {
    Identifier,
    Space,
    Comment,
    Keyword(Keyword),
    LiteralConstant,
    Punctuator(char),
    EndOfFile,
}

There're seven kinds of tokens defined here; Let's discuss each of them one by one.

An Identifier is a string of characters used to give a name to a particular symbol or declaration.
A Space represents a string of whitespaces defined in the source file, including whitespaces.
A Comment represents a text in the source file that doesn't alter the program's behavior but is meant to be an annotation for the programmer.
A Keyword is a string, similar to an identifier, but the language reserves since it often has a special meaning that commands particular program behavior.
A Literal Constant is any hard-coded value in the source file, including numbers, boolean-value, and strings.
A Punctuator is a token with syntactic and semantic meaning to the compiler, but the exact significance depends on the context.
A EndOfFile signifies the end of the token stream.

Now let's write a Token struct, the data structure that the lexer will produce.

/// Represents a single token word; containing type of the token and its lexeme
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Token<'a> {
    token_kind: TokenKind,
    position_range: Range<SourcePosition>,
    lexeme: &'a str,

This struct has only three fields. It contains the kind of token, a string representing the lexeme, and a position in the source file that makes up this token.

Error Handling

Having a sophisticated error-handling system is crucial when writing a compiler. It should include helpful information for the user and report a useful message.

Let's create a new module called error. This module contains code related to the error-handling system.

Next, create an enum called Error, containing all possible Lexical Error types.

/// An enumeration containing all lexical errors
pub enum Error<'a> {
    InvalidCharacter {
        position: SourcePosition,
        character: char,
        source_refernece: &'a SourceCode,
    },
    UnterminatedMultilineComment {
        multiline_comment_position: SourcePosition,
        source_refernece: &'a SourceCode,
    },
}

Each enum variant stores all necessary information about the error that can use to report the error message.

Next, implement an associated function that prints out the error message based on the stored information.

Full Code Listing of error.rs

impl<'a> Error<'a> {
    /// Prints the error message to the standard output
    pub fn print_error(&self) { ... }
}

The ellipses here signify that the code is lengthy and will not be included here. However, the complete code listing is provided at the beginning as a link to the GitHub repository.

Writing the Lexer

Now, back to writing the lexer. I will write the code of the lexer in the lib.rs file. The Lexer struct consumes the characters and omits one token at a time -- kind of like an iterator.

Psuedo code of using the lexer:

let mut lexer = Lexer::new(&source_code);
let first_token = lexer.lex();
let second_token = lexer.lex();

Let's write a Lexer struct.

/// Represents a lexer in lexical analysis which transforms source code into a
/// token stream
pub struct Lexer<'a> {
    source_code: &'a SourceCode,
    chars: Peekable<CharIndices<'a>>,
    current_position: SourcePosition,
}

It contains a reference to the input source code, an iterator using Peekable<CharIndices>, and a variable for tracking the current lexing position.

Before writing the code for lexing, we need a helper function that eats one character at a time; keeps tracking its current source code position; and returns the character value and the UTF-8 byte position, which is used for slicing the source code for constructing the lexeme.

impl<'a> Lexer<'a> {
    // returns the current character and the its byte index , and moves to the
    // next character
    fn next(&mut self) -> Option<(usize, char)> {
        let next = self.chars.next();

        // increment to the next position
        match next {
            Some(char) => {
                if char.1 == '\n' {
                    self.current_position.line += 1;
                    self.current_position.column = 1;
                } else {
                    self.current_position.column += 1;
                }
            }
            _ => {}
        }
        next
    }
}

Next, we need a hash table that stores every reserved keyword in the language. I'll use the lazy_static crate from crates.io for this case.

lazy_static! {
    static ref KEYWORD: HashMap<&'static str, Keyword> = {
        let mut map = HashMap::new();
        map.insert("return", Keyword::Return);
        map
    };
}

After that, we got everything required for writing the lex function. As discussed earlier, it moves the characters forward and returns the token.

Full Code Listing of lib.rs

impl<'a> Lexer<'a> {
    /// Lexes the current word; returns the corresponding token and moves to
    /// the next token.
    pub fn lex(&mut self) -> Result<Token<'a>, Error<'a>> { ... }
}

The actual implementation is lengthy, but I'll briefly explain how the function is implemented.

First, the function eats the first character by calling the next function and moves to the next character. If it returns None, the lex function exits immediately and returns the EndOfFile token. Otherwise, it proceeds. Next, from the given first character, the function now has a clue of what kind of token will be. The character is then matched against these following if-else branches to determine their token kind.

Python is used here, as the psuedo-code for brevity and conciseness.

If the first character is whitespace, the function eats all the next consecutive whitespaces if there are any. The token is categorized as TokenKind::Space.

if first_char.is_whitespace():   
    while self.peek().is_whitespace():
        self.next()
    return SPACE

If the first character is a forward slash, the function checks whether or not the next character is a forward slash too; if it is the comment is found, the lexer skips all the characters following after until the new line is located, the token is classified as TokenKind::Comment. Otherwise, the lexer typed the single forward slash as TokenKind::Punctuator.

else if first_char == '/':
    if self.peek() == '/':
        while self.peek() != '\n' || self.peek() != END_OF_FILE:
            self.next()
        # eat the '\n'
        self.next()
        return COMMENT
    else
        return PUNCTUATOR

If the first character is an alphabet or underscore, the function eats all the next alphabet or underscore. Next, the function checks whether the given string that has just been eaten is in the keyword hash table. If it is, the token is TokenKind::Keyword; otherwise, it is TokenKind::Identifier.

else if first_char.is_alphabet_or_underscore():
    string = first_char
    while self.peek().is_alphabet_or_underscore():
        string += self.next()

    if string in keyword_table:
        return KEYWORD
    else
        return IDENTIFIER

This one is the simplest; if the first character is punctuation, simply categorize the token as TokenKind::Punctuator.
If the first character is a numeric digit, the function eats all the next numeric digits -- works similarly to the identifier. The token is classified as TokenKind::LiteralConstant.

else if first_char.is_digit():
    string = first_char
    while self.peek().is_digit():
        string += self.next()

    return LITERAL_CONSTANT

Finally, the last else branch returns the Err variant signifying an invalid character is found.

// this character can't be categorized under any token kinds
else {
    return Err(Error::InvalidCharacter {
        position: first_position,
        character: first_char,
        source_refernece: self.source_code,
    });
}

Summary

That's it; we've essentially created a simple lexer in Rust, which can tokenize the source code into a stream of tokens. You can find all the code listings in the GitHub repository.

Crafting a Compiler in Rust: Introduction

Simmypeet — Thu, 08 Dec 2022 15:40:16 +0000

Has anyone wondered? How does the code that we've written turn into a program or application? The simple explanation is that there's a program designed specifically to translate high-level code into machine code that computers can understand and execute. This program is called a compiler.

Hi, In this dev-blog series, I'm writing and documenting the process of creating a compiler for my programming language, Pernix. This series will go through to the point where the compiler is self-hosted, meaning it's possible to develop a compiler for my programming language using my programming language and compiler. This series will not be a line-by-line tutorial but will show what each component in the compiler does and how they interact.

About my Programming Language and Compiler

The programming language is called Pernix. It is a Latin word; that means agile, quick, and swift. The language is statically-typed and compiled and has a syntax similar to C. I'll implement the compiler in Rust programming language with the help of LLVM.

Compiler Basics

Before writing a compiler, let's understand some basics of it. Generally speaking, the compiler is separated into the front-end and back-end. The front-end part involves converting the source code into an intermediate representation and checking all sorts of errors in the program. The back-end then performs the translation from the intermediate representation produced by the front-end into machine code.

Typically, each operating system and CPU have its own instruction sets, meaning that the compiler has to handle the differences between them.
Fortunately, LLVM will do the most heavy-lifting jobs in the back-end part. Therefore, I'll focus more on developing the front-end part.

Compiler Front-End Overview

Again, the compiler front end can also be broken down into several parts:
Lexical Analysis, Syntactic Analysis, and Semantic Analysis.

Lexical Analysis involves breaking the source code into manageable tokens/words.
Syntactic Analysis performs the grammar check of the language and turns a token stream from the previous phase into the abstract syntax tree (AST).
Semantic Analysis performs additional checks that the Syntactic Analysis phase can't, such as type-checking and symbols look-up. As the previous can only validate the grammatical structure of the program.

I'll go into more detail about each phase in their separate blog post of them.

DEV Community: Simmypeet

Optimizing Graph Traversal in Query Based Incremental Compiler

To Adapton Style

Super Node: Where Dirty Propagation Falls Apart

Firewall Query

The Algorithm

Projection Query

Trade-offs

Conclusion

Rust 2.0: A Thought Experiment on Safe Specialization

Why Specialization?

Primer: What's So Unsound About Specialization

What's Going On Here?

What Should Have Been Done?

The Problem

How Could We Fix This?

Specialization with Deferred Binding

The Chain of Delegation

The Problem: Delegation Hell

Introduce final impl

Some Further Crazy Ideas: Ranking

Reflection: How This Fits into Rust Today

The Ugly

Bonus: Lifetimes

Building a Query-Based Incremental Compilation Engine in Rust

From Traditional Pipeline Compiler

To Query-Based Compiler

Query Dependency Graph

Implementing the Query Engine

The Key trait

The Executor trait

The Engine object

Type Erasure in Engine

Supporting Infrastructure

Versioning and Dependency Tracking

Cyclic Tracking

Fingerprinting

Persistence

Multithreading Synchronization

Pros and Cons

Pros

Cons

Conclusion

Crafting a Compiler in Rust: Syntactic Analysis

Update on the Lexer

Syntactic Analysis Basics

The Abstract Syntax Tree

The Goal

The pernix_parser Crate

The abstract_syntax_tree Module

The error Module

Writing The Parser

Parsing The Qualified Name

Parsing The Using Statement

Parsing The Namespace Declaration

Parsing The Program

Summary

Crafting a Compiler in Rust: Lexical Analysis

The Pernix Project Crate

The Pernix Lexer Crate

Error Handling

Writing the Lexer

Summary

Crafting a Compiler in Rust: Introduction

About my Programming Language and Compiler

Compiler Basics

Compiler Front-End Overview

Introduce `final impl`

The `Key` trait

The `Executor` trait

The `Engine` object

The `pernix_parser` Crate

The `abstract_syntax_tree` Module

The `error` Module