#会话 #语法树 #类型 # #异步 #AST #异步通道

辩证编译器

辩证crate的会话类型宏编译器

1个不稳定版本

0.1.0 2021年4月1日

异步 中排名第 971

Download history 20/week @ 2024-03-11 17/week @ 2024-03-18 33/week @ 2024-03-25 61/week @ 2024-04-01 9/week @ 2024-04-08 13/week @ 2024-04-15 23/week @ 2024-04-22 13/week @ 2024-04-29 19/week @ 2024-05-06 16/week @ 2024-05-13 22/week @ 2024-05-20 8/week @ 2024-05-27 13/week @ 2024-06-03 15/week @ 2024-06-10 9/week @ 2024-06-17 17/week @ 2024-06-24

每月下载量 54
7 个crate中使用(通过 dialectic-macro

MIT 许可证

125KB
1.5K SLoC

Rust license: MIT crates.io docs.rs documentation

包含将辩证宏语言的 Session! 编译成实际Rust类型的函数。此crate被视为内部实现细节,其API不受语义版本控制规则约束。编译过程通过逐步转换三个表示形式来完成。

  • syntax::Syntax - "表面层"抽象语法树。这是从proc宏接口提供的标记流中解析出来的。
  • cfg::Cfg - 控制流程图表示,通过语义保留的转换逐渐转换,直到它采用更适合输出的形式。
  • target::Target - "目标语言"语法树,它直接映射到辩证会话类型。

Syntax AST转换

解析后,Syntax AST实际上只经过一次转换,当它转换为控制流程图表示时。

转换为CFG - Syntax::to_cfg

在这个转换过程中,我们在AST中解析标签,并确保所有breakcontinue构造都指向有效的节点,并对不规则的循环节点等问题发出错误。请注意,此方法通常被称为Syntax::to_cfg,但实际上该方法是在Spanned<Syntax>上实现的。

错误

这个遍历可能会产生几个错误

[Cfg] 转换

CFG在经过流分析、错误报告以及最终降低到Target之前,只经历了一次真正关键的显式转换。CFG处理的粗略概述如下

  • 作用域解析和隐式继续插入
  • 控制流分析
  • 可达性分析,使用控制流分析输出
  • 死代码分析 - 报告不可达代码,这些代码永远不会由编译器发出
  • 目标生成,break消除和循环效率分析

作用域解析 - Cfg::resolve_scopes

作用域解析遍历在Cfg::resolve_scopes方法中实现。它从给定的根节点遍历CFG,并将“隐式”继续转换为“显式”继续。由于隐式继续是另一种由循环体作用域中缺少继续表示的“隐式”继续,因此我们也在这里插入它们。然而,这种类型的机器生成的Continue节点实际上可能是不可达代码,这将在死代码分析期间触发错误;因此,机器生成的Continues被标记为CfgNodemachine_generated字段,死代码报告被配置为忽略它们。

在作用域解析遍历之后,我们可以使用三个关键的不变量

大多数其他流程都将利用这些假设。

作用域解析算法看起来像这样

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);

错误

此流程永远不会发出任何错误。

死代码报告 - Cfg::report_dead_code

死代码报告流程本身负责运行流分析可达性分析。在这些分析运行后,它从根节点遍历控制流图,寻找流分析认为“无法通过”的节点(控制流程不会继续到它们的后续节点),但它们仍然有后续节点。这为我们提供了所有包含可到达代码紧邻不可到达代码的程序点的位置,这对用户来说比看到每个不可到达节点(可能有很多相同的流程路径中的节点)的错误更容易。

死代码报告算法看起来像这样

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);

错误

此流程发出两种类型的错误

降低到目标/目标代码生成 - Cfg::generate_target

代码生成/降低流程还执行循环生产率分析。一个无生产力的循环在技术上是一个有效的表面语言程序,但将导致 Rust 1.51 版本的 Rust 类型检查器无限循环并生成一个错误,这对于新用户来说很难理解。为了防止这种情况,我们检测它们并报告它们,而不是编译一个技术上有效的会话类型,该类型不会作为有效的 Rust 编译。

循环生产率分析在目标生成流程中进行,因为它是对目标语言本身的句法属性的分析。

对于大多数节点,生成相应的目标代码非常简单 - SendRecvCallSplitChooseOffer 都非常直接地映射到它们的 Target 对应项。复杂组件包括 LoopContinueTypeBreakError

  • Continue 需要从直接引用其目标转换为引用目标循环的正确 DeBruijn 索引。为此,我们保持一个循环环境作为栈,在进入循环节点时将其推入,在退出时将其弹出。计算循环对应的 DeBruijn 索引是通过在循环环境中进行线性搜索来完成的,以查找匹配循环在循环环境中的位置。
  • BreakTarget 中没有对应的表示;相反,它在代码生成时通过用它引用的循环的延续来替换任何对其的引用来降低。循环的延续也必须放入其自己的循环环境,因为在 Target 中,循环的延续只是循环的一部分,不以 Continue 结束。这实际上使代码生成变得稍微方便一些,但仍然应该注意。
  • Loop 在生成其主体之前必须将其索引推入循环环境栈,然后在主体生成后将其弹出,以确保循环环境正确对应于目标 AST 中的范围。
  • Target 中的 Type 没有地方放置与它的下一个指针对应的延续。在 Target 中,一个 Type 会运行直到它完成。所以有两种情况;如果 Type 的延续是 None(“完成”延续),我们就可以直接将类型作为一个 Target::Type 节点发出;如果它是 Some,我们必须发出一个 Target::Then,它将 Type 的延续序列在其之后。
  • ErrorTarget 中没有对应的表示,在代码生成时用其延续替换。虽然在代码生成过程中允许它们存在,但遇到 Error 节点的代码生成过程已经遇到了至少一个相应的发出的 CompileError,并且生成的目标 AST 不会从 Cfg::generate_target 返回。

代码生成算法看起来是这样的

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);
        }
    }
}

错误

此流程发出两种类型的错误

Target 转换

目前,目标抽象语法树(AST)在转换为目的地格式(无论是作为字符串显示还是作为Rust令牌树发出)之前不进行任何类型的转换。

依赖项

~2.3–3MB
~63K SLoC