1 unstable release
0.1.0 | Apr 1, 2021 |
---|
#971 in Asynchronous
54 downloads per month
Used in 7 crates
(via dialectic-macro)
125KB
1.5K
SLoC
Contains functionality for compiling the language of Dialectic's Session!
macro into an actual Rust type. This crate is considered an internal implementation detail and none of its API is subject to semantic versioning rules. The compilation process is done via transforming the syntax gradually across three representations:
syntax::Syntax
- the "surface-level" abstract syntax tree. This is what gets parsed from the tokenstream provided by the proc macro interface.cfg::Cfg
- a control flow graph representation, which is gradually transformed by semantics-preserving passes until it takes on a form more suitable for emitting to the target.target::Target
- the "target language" syntax tree, which directly maps to Dialectic session types.
Syntax
AST transformations
After parsing, the Syntax
AST only really undergoes one transformation, when it is converted to the control flow graph representation.
Conversion to CFG - Syntax::to_cfg
During this conversion, we resolve labels in the AST and ensure that all break
and continue
constructs refer to valid nodes and emit errors for malformed loop nodes and such. Also, please note this method is often referred to as Syntax::to_cfg
but the method is actually implemented on Spanned<Syntax>
.
Errors
This pass may emit several errors:
CompileError::UndeclaredLabel
- emitted when we find a reference to a label that's not in scopeCompileError::ShadowedLabel
- emitted when two loops in the same scope have the same labelCompileError::ContinueOutsideLoop
- emitted when we find aContinue
in an empty environmentCompileError::BreakOutsideLoop
- emitted when we find aBreak
in an empty environment
[Cfg
] transformations
The CFG undergoes only one really crucial explicit transform before undergoing flow analysis, error reporting, and then finally lowering to the Target
. The rough outline of CFG processing looks like this:
- Scope resolution and implicit continue insertion
- Control flow analysis
- Reachability analysis, using the control flow analysis output
- Dead code analysis - report unreachable code, which will never be emitted by the compiler
- Target generation, break elimination, and loop productivity analysis
Scope resolution - Cfg::resolve_scopes
The scope resolution pass is implemented in the Cfg::resolve_scopes
method. It traverses the CFG from a given root node, and converts "implicit" continuations to "explicit" continuations. Because implicit continues are another sort of "implicit" continuation represented by the absence of a continuation in the scope of a loop body, we also insert them here. There is a chance, however, that a machine-generated Continue
node of this sort will actually be unreachable code, which would trigger an error during dead code analysis; because of that, machine generated Continues
are marked with the machine_generated
field of CfgNode
, and dead code reporting is configured to ignore them.
After the scope resolution pass, there are three critical invariants we can use:
Ir::Choose
andIr::Offer
nodes will never have a continuation (theirnode.next
fields will always beNone
).Ir::Loop
nodes will always have a nonempty body (theOption<Index>
inside theIr::Loop
variant will always beSome(body)
).- Paths through the body of an
Ir::Loop
node will always terminate in anIr::Break
or anIr::Continue
.
Most other passes will make use these assumptions.
The scope resolution algorithm looks something like this:
fn resolve_scopes(implicit_scope, node) {
if the node is a Recv, Send, Type, Break, Continue, Call, Split, or Error {
// The implicit continuation of the callee of a Call node or arm of a Split node is always
// Done, because we want to to run it until Done rather than to continue afterwards, as the
// Call/Split node takes care of the continuation.
if the node is a Call(callee) {
resolve_scopes(None, callee);
}
if the node is a Split(tx, rx) {
resolve_scopes(None, tx);
resolve_scopes(None, rx);
}
// If this node has an explicit continuation, then we follow it and continue visiting! If it
// doesn't, then we assign the implicit continuation in its scope to become its new explicit
// continuation.
match node.next {
Some(next) => resolve_scopes(implicit_cont, next),
None => node.next = implicit_scope,
}
} else if the node is a Choose(choices) or Offer(choices) {
// Remove the continuation from the node if present; we inline it into all arms of the //
// Choose/Offer.
let cont = match node.next.take() {
// If we find an implicit continuation, then it's the new "top of the continuation
// scope" for this node's arms. In order to properly inline the outer scope's implicit
// continuation, we visit the new implicit continuation w/ the previous one in order to
// cause it to be inlined in the correct places as well.
Some(next) => {
resolve_scopes(implicit_cont, next);
Some(next)
}
// If this node doesn't have an implicit continuation, then there's no need to worry
// about inlining the outer scope's implicit continuation into it, as we can just inline
// the outer implicit continuation into every arm instead.
None => implicit_cont,
};
for choice in choices {
resolve_scopes(cont, choice);
}
// We never follow or reassign a Choose/Offer node's implicit continuation, because it's
// been inlined into all its arms already.
} else if the node is a Loop(body) {
// Inside a loop body, the absence of an explicit continuation doesn't imply following the
// implicit continuation held by the scope outside the loop (the continuation of the loop
// block) - instead, it implies continuing the loop! So to handle that, we visit the body of
// the loop with its implicit continuation set to a Continue node we generate, targeted at
// the loop node itself.
let continue0 = Continue(node);
continue0.machine_generated = true;
resolve_scopes(continue0, body);
}
}
// We begin w/ an empty implicit continuation (the Done continuation) and start traversing from the
// root.
resolve_scopes(None, root);
Errors
This pass never emits any errors.
Dead code reporting - Cfg::report_dead_code
The dead core reporting pass itself is responsible for running the flow analysis and reachability analysis. After these are run, it traverses the control flow graph from the root, looking for nodes which the flow analysis considers "impassable" (control flow does not proceed to their continuations) but which still have a continuation. This gives us the location of all the points in the program which consist of reachable code immediately adjacent to unreachable code, which is much nicer for the user to see errors of rather than errors for every unreachable node, of which there may be many in the same flow path.
The dead code reporting algorithm looks something like this:
fn report_dead_code(node) {
// We want to follow every child node except for the node's continuation. If we did follow the
// continuation, we would end up reporting every unreachable node instead of just the
// unreachable nodes on the boundary between reachable and unreachable code.
for child in all children of node {
report_dead_code(child);
}
if let Some(cont) = node.next {
if node is passable {
report_dead_code(cont);
} else if !cont.machine_generated && cont is not reachable {
emit unreachable code errors;
}
}
}
report_dead_code(node);
Errors
This pass emits two types of errors:
CompileError::FollowingCodeUnreachable
- emitted on a reachable node which has an unreachable continuationCompileError::UnreachableStatement
- emitted on an unreachable node that is the continuation of a reachable node
Lowering to target/target code generation - Cfg::generate_target
The code generation/lowering pass also performs loop productivity analysis. An unproductive loop is technically a valid surface language program but will cause the Rust typechecker as of Rust 1.51 to infinitely loop and generate an error which is very difficult for new users to decipher. To prevent this, we detect them and report them instead of compiling a technically valid session type which will not compile as valid Rust.
Loop productivity analysis is conducted during the target generation pass because it is a syntactic property of the target language itself.
For most nodes, generating the corresponding target code is trivial - Send
, Recv
, Call
, Split
, Choose
, and Offer
all map very directly to their Target
counterparts. The complex components are Loop
, Continue
, Type
, Break
, and Error
:
Continue
s must be converted from directly referencing their target to referencing the correct DeBruijn index of the target loop. For this purpose, we keep a loop environment as a stack which is pushed to when entering a loop node and popped when exiting. Calculating the DeBruijn index corresponding to a loop is done with a linear search on the loop environment looking for the position of the matching loop in the loop environment.Break
has no corresponding representation in theTarget
; instead, it lowered by substituting any reference to it with the continuation of the loop it references. The loop's continuation must also be placed into its own loop environment, because in theTarget
, continuations of a loop are simply parts of a loop which do not end in aContinue
. This actually makes codegen a little bit more convenient, but should still be noted.Loop
must push its index to the loop environment stack before generating its body, and then pop once its body is generated, in order to ensure the loop environment properly corresponds to the scope in the target AST.Type
in theTarget
has nowhere to put the continuation corresponding to its next pointer. In theTarget
, aType
is run until it isDone
. So there are two cases; if theType
's continuation isNone
(the "done" continuation) we can just emit the type directly as aTarget::Type
node; if it isSome
, we must emit aTarget::Then
which sequences theType
's continuation after it.Error
has no corresponding representation in theTarget
, and is substituted with its continuation during codegen. While they are allowed during codegen, a codegen pass which encounters anError
node will already have encountered at least one corresponding emittedCompileError
, and the resulting target AST will not be returned fromCfg::generate_target
.
The codegen algorithm looks something like this:
fn generate_target(loop_env, maybe_node) {
if maybe_node is None {
// If the node is empty, that's the "done" continuation.
return Done;
} else if maybe_node is Some(node) {
if node is NOT Loop, Continue, Break {
// Note that the current loop's target representation contains something which is not
// another Loop in between itself and its `Continue` if present.
loop_env.mark_productive();
}
if node is Recv, Send, Call, Split, Choose, or Offer {
// Recursively call generate_target on child nodes and convert to the directly
// corresponding Target.
return Target:: ...;
} else if node is Loop(body) {
loop_env.push(node);
let body = generate_target(loop_env, body);
loop_env.pop(node);
return Target::Loop(body);
} else if node is Continue(jump_target) {
let debruijn_index = loop_env.debruijn_index_of(jump_target);
// If we've hit a continue, we can know whether or not the corresponding loop is
// productive or not, and emit an error if not.
if !loop_env.productive_for_continue(debruijn_index) {
// Emit an error for the unproductive loop, and for the unproductive continue *if*
// it is not machine generated
...
}
return Target::Continue(debruijn_index);
} else if node is Break(jump_target) {
// For a break, return the result of generating the target form of its corresponding
// loop's continuation.
return generate_target(loop_env, jump_target.next);
} else if node is Type(ty) {
// If the continuation is "done", then we don't need to emit a Then.
if node.next is None {
return Target::Type(ty);
} else {
let cont = generate_target(loop_env, node.next);
return Target::Then(Target::Type(ty), );
}
} else if node is Error {
// Just keep going so we can collect more loop productivity errors.
return generate_target(loop_env, node.next);
}
}
}
Errors
This pass emits two types of errors:
CompileError::UnproductiveLoop
- emitted on a loop node which is found to be unproductiveCompileError::UnproductiveContinue
- emitted on a non-machine-generated continue node which causes a loop to be unproductive
Target
transformations
At current, the target AST does not undergo any kind of transform before it is converted very transparently to its destination format (whether that's to be displayed as a string or emitted as a Rust token tree.)
Dependencies
~2.3–3MB
~63K SLoC