正则表达式引擎的实现方式多样，不同方法在性能、内存消耗和实现复杂度上各有权衡。本文将介绍两种数学上等价但实际表现迥异的正则匹配方法：Brzozowski 导数方法和 Thompson 虚拟机方法。
这两种方法都基于相同的抽象语法树表示，为直接的性能对比提供了统一的基础。其核心思想在于：这些看似不同的方法实际上是用不同的计算策略来解决同一个问题——一个依靠代数变换，另一个则通过程序执行。
为了建立统一的基础，两种正则表达式引擎都采用相同的抽象语法树（AST）表示，用树形结构来描述正则表达式的基本构造：
enum Ast {
Chr(Char)
Seq(enum Ast {
Chr(Char)
Seq(Ast, Ast)
Rep(Ast, Int?)
Opt(Ast)
} derive(Show, ToJson, Hash, Eq)
enum Ast {
Chr(Char)
Seq(Ast, Ast)
Rep(Ast, Int?)
Opt(Ast)
} derive(Show, ToJson, Hash, Eq)
enum Ast {
Chr(Char)
Seq(Ast, Ast)
Rep(Ast, Int?)
Opt(Ast)
} derive(Show, ToJson, Hash, Eq)
enum Ast {
Chr(Char)
Seq(Ast, Ast)
Rep(Ast, Int?)
Opt(Ast)
} derive(Show, ToJson, Hash, Eq)
trait Show {
output(Self, &Logger) -> Unit
to_string(Self) -> String
}
Trait for types that can be converted to String
trait ToJson {
to_json(Self) -> Json
}
Trait for types that can be converted to Json
trait Hash {
hash_combine(Self, Hasher) -> Unit
hash(Self) -> Int
}
Trait for types that can be hashed
The hash method should return a hash value for the type, which is used in hash tables and other data structures.
The hash_combine method is used to combine the hash of the current value with another hash value,
typically used to hash composite types.
When two values are equal according to the Eq trait, they should produce the same hash value.
The hash method does not need to be implemented if hash_combine is implemented,
When implemented separately, hash does not need to produce a hash value that is consistent with hash_combine.
trait Eq {
equal(Self, Self) -> Bool
op_equal(Self, Self) -> Bool
not_equal(Self, Self) -> Bool
}
Trait for types whose elements can test for equality
此外，我们还提供了智能构造函数来简化正则表达式的构建：
fn enum Ast {
Chr(Char)
Seq(Ast, Ast)
Rep(Ast, Int?)
Opt(Ast)
} derive(Show, ToJson, Hash, Eq)
fn Ast::chr(chr : Char) -> Ast
enum Ast {
Chr(Char)
Seq(Ast, Ast)
Rep(Ast, Int?)
Opt(Ast)
} derive(Show, ToJson, Hash, Eq)
enum Ast {
Chr(Char)
Seq(Ast, Ast)
Rep(Ast, Int?)
Opt(Ast)
} derive(Show, ToJson, Hash, Eq)
fn Ast::seq(self : Ast, other : Ast) -> Ast
enum Ast {
Chr(Char)
Seq(Ast, Ast)
Rep(Ast, Int?)
Opt(Ast)
} derive(Show, ToJson, Hash, Eq)
enum Ast {
Chr(Char)
Seq(Ast, Ast)
Rep(Ast, Int?)
Opt(Ast)
} derive(Show, ToJson, Hash, Eq)
enum Ast {
Chr(Char)
Seq(Ast, Ast)
Rep(Ast, Int?)
Opt(Ast)
} derive(Show, ToJson, Hash, Eq)
enum Ast {
Chr(Char)
Seq(Ast, Ast)
Rep(Ast, Int?)
Opt(Ast)
} derive(Show, ToJson, Hash, Eq)
fn Ast::rep(self : Ast, n? : Int) -> Ast
enum Ast {
Chr(Char)
Seq(Ast, Ast)
Rep(Ast, Int?)
Opt(Ast)
} derive(Show, ToJson, Hash, Eq)
enum Ast {
Chr(Char)
Seq(Ast, Ast)
Rep(Ast, Int?)
Opt(Ast)
} derive(Show, ToJson, Hash, Eq)
enum Ast {
Chr(Char)
Seq(Ast, Ast)
Rep(Ast, Int?)
Opt(Ast)
} derive(Show, ToJson, Hash, Eq)
fn Ast::opt(self : Ast) -> Ast
enum Ast {
Chr(Char)
Seq(Ast, Ast)
Rep(Ast, Int?)
Opt(Ast)
} derive(Show, ToJson, Hash, Eq)
enum Ast {
Chr(Char)
Seq(Ast, Ast)
Rep(Ast, Int?)
Opt(Ast)
} derive(Show, ToJson, Hash, Eq)
AST 定义了四种基本的正则表达式操作：
Chr(Char) - 匹配单个字符字面量Seq(Ast, Ast) - 序列匹配，即一个模式紧跟另一个模式Rep(Ast, Int?) - 重复匹配，None 表示无限次重复，Some(n) 表示恰好重复 n 次Opt(Ast) - 可选匹配，相当于标准正则语法中的 pattern?
举个例子，正则表达式 (ab*)? 表示一个可选的序列（'a' 后跟零个或多个 'b'），可以这样构建：
Ast::chr('a').seq(Ast::chr('b').rep()).opt()
导数方法基于形式语言理论，通过代数变换来处理正则表达式。对于输入的每个字符，该方法计算正则表达式的"导数"，实质上是在问："消费掉这个字符后，还剩下什么需要匹配？"这样就得到了一个新的正则表达式，代表剩余的匹配模式。
为了明确表示导数和可空性，我们对基本的 Ast 类型进行了扩展：
enum Exp {
Nil
Eps
Chr(Char)
Alt(enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
trait Show {
output(Self, &Logger) -> Unit
to_string(Self) -> String
}
Trait for types that can be converted to String
trait Hash {
hash_combine(Self, Hasher) -> Unit
hash(Self) -> Int
}
Trait for types that can be hashed
The hash method should return a hash value for the type, which is used in hash tables and other data structures.
The hash_combine method is used to combine the hash of the current value with another hash value,
typically used to hash composite types.
When two values are equal according to the Eq trait, they should produce the same hash value.
The hash method does not need to be implemented if hash_combine is implemented,
When implemented separately, hash does not need to produce a hash value that is consistent with hash_combine.
trait Eq {
equal(Self, Self) -> Bool
op_equal(Self, Self) -> Bool
not_equal(Self, Self) -> Bool
}
Trait for types whose elements can test for equality
trait Compare : Eq {
compare(Self, Self) -> Int
op_lt(Self, Self) -> Bool
op_gt(Self, Self) -> Bool
op_le(Self, Self) -> Bool
op_ge(Self, Self) -> Bool
}
Trait for types whose elements are ordered
The return value of [compare] is:
- zero, if the two arguments are equal
- negative, if the first argument is smaller
- positive, if the first argument is greater
trait ToJson {
to_json(Self) -> Json
}
Trait for types that can be converted to Json
Exp 中各构造器的含义如下：
Nil - 表示不可能匹配的模式，即空集Eps - 匹配空字符串Chr(Char) - 匹配单个字符Alt(Exp, Exp) - 表示选择（或），在多个模式间进行选择Seq(Exp, Exp) - 表示连接，将两个模式依次连接Rep(Exp) - 表示重复，对模式进行零次或多次重复
通过 Exp::of_ast 函数，我们可以将 Ast 转换为表达能力更强的 Exp 格式：
fn enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
fn Exp::of_ast(ast : Ast) -> Exp
enum Ast {
Chr(Char)
Seq(Ast, Ast)
Rep(Ast, Int?)
Opt(Ast)
} derive(Show, ToJson, Hash, Eq)
enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
fn Exp::of_ast(ast : Ast) -> Exp
enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
fn Exp::of_ast(ast : Ast) -> Exp
enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
fn Exp::of_ast(ast : Ast) -> Exp
enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
fn Exp::of_ast(ast : Ast) -> Exp
enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
fn Exp::of_ast(ast : Ast) -> Exp
同样，我们也为 Exp 提供了智能构造函数来简化模式构建：
fn enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
fn Exp::seq(a : Exp, b : Exp) -> Exp
enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
不过，Alt 的智能构造函数特别重要——它保证构造出的 Exp 符合 Brzozowski 原论文中的"相似性"标准化要求。两个正则表达式如果能通过以下规则相互转换，就被认为是相似的：
A∣∅A∣BA∣(B∣C)→A→B∣A→(A∣B)∣C
因此，我们对 Alt 构造进行标准化，确保始终使用一致的结合律和选择顺序：
fn enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
fn Exp::alt(a : Exp, b : Exp) -> Exp
enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
fn Exp::alt(a : Exp, b : Exp) -> Exp
fn Exp::alt(a : Exp, b : Exp) -> Exp
(Exp, Exp) -> Bool
automatically derived
(x : Exp, y : Exp) -> Bool
nullable 函数用于判断一个模式是否能够在不消费任何输入的情况下成功匹配（即匹配空字符串）：
fn enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
fn Exp::nullable(self : Exp) -> Bool
enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
fn Exp::nullable(self : Exp) -> Bool
fn Exp::nullable(self : Exp) -> Bool
fn Exp::nullable(self : Exp) -> Bool
fn Exp::nullable(self : Exp) -> Bool
deriv 函数计算模式对于特定字符的导数，按照 Brzozowski 导数理论中定义的规则对模式进行变换。我们对规则进行了重新排列，使其与 deriv 函数的实现顺序保持一致：
Da∅DaϵDaaDabDa(P∣Q)Da(P⋅Q)Da(P∗)=∅=∅=ϵ=∅=(DaP)∣(DaQ)=(DaP⋅Q)∣(ν(P)⋅DaQ)=DaP⋅P∗ for (a=b)
fn enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
fn Exp::deriv(self : Exp, c : Char) -> Exp
enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
fn Eq::equal(self : Char, other : Char) -> Bool
Compares two characters for equality.
Parameters:
self : The first character to compare.other : The second character to compare.
Returns true if both characters represent the same Unicode code point,
false otherwise.
Example:
test {
let a = 'A'
let b = 'A'
let c = 'B'
inspect(a == b, content="true")
inspect(a == c, content="false")
}
fn Exp::deriv(self : Exp, c : Char) -> Exp
fn Exp::alt(a : Exp, b : Exp) -> Exp
fn Exp::deriv(self : Exp, c : Char) -> Exp
fn Exp::deriv(self : Exp, c : Char) -> Exp
fn Exp::nullable(self : Exp) -> Bool
fn Exp::seq(a : Exp, b : Exp) -> Exp
fn Exp::alt(a : Exp, b : Exp) -> Exp
fn Exp::deriv(self : Exp, c : Char) -> Exp
fn Exp::seq(a : Exp, b : Exp) -> Exp
fn Exp::deriv(self : Exp, c : Char) -> Exp
fn Exp::seq(a : Exp, b : Exp) -> Exp
为了简化实现，我们这里只进行严格匹配，也就是说模式必须匹配整个输入字符串。因此，只有在处理完所有输入字符后，我们才检查最终模式的可空性：
fn enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
fn Exp::matches(self : Exp, s : String) -> Bool
enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
fn String::view(self : String, start_offset? : Int, end_offset? : Int) -> StringView
Creates a View into a String.
Example
test {
let str = "Hello🤣🤣🤣"
let view1 = str.view()
inspect(view1, content="Hello🤣🤣🤣")
let start_offset = str.offset_of_nth_char(1).unwrap()
let end_offset = str.offset_of_nth_char(6).unwrap() // the second emoji
let view2 = str.view(start_offset~, end_offset~)
inspect(view2, content="ello🤣")
}
fn Exp::nullable(self : Exp) -> Bool
fn Exp::deriv(self : Exp, c : Char) -> Exp
虚拟机方法将正则表达式编译成简单虚拟机的字节码指令。这种方法把模式匹配问题转化为程序执行过程，虚拟机同时模拟非确定性有限自动机中所有可能的执行路径。
Ken Thompson 在 1968 年的经典论文中描述了一种将正则模式编译为 IBM 7094 机器代码的引擎。其关键思路是：通过维护多个执行线程来避免指数级回溯，这些线程同步地在输入中前进，每次处理一个字符，同时探索所有可能的匹配路径。
该虚拟机基于四种基本指令运行，它们分别对应 NFA 的不同操作：
enum Ops {
Done
Char(Char)
Jump(Int)
Fork(Int)
} derive(trait Show {
output(Self, &Logger) -> Unit
to_string(Self) -> String
}
Trait for types that can be converted to String
trait ToJson {
to_json(Self) -> Json
}
Trait for types that can be converted to Json
每条指令在 NFA 模拟中都有其特定作用：Done 标记匹配成功完成，对应 Thompson 原设计中的 match；Char(c) 消费输入字符 c 并跳转到下一条指令；Jump(addr) 无条件跳转至地址 addr，即 Thompson 的 jmp；Fork(addr) 创建两条执行路径——一条继续执行下一条指令，另一条跳转到 addr，对应 Thompson 的 split。
Fork 指令是处理模式非确定性的关键，比如选择和重复操作，这些情况下需要同时探索多条执行路径。这直接对应了 NFA 中的 ε-转换，即执行流可以在不消费输入的情况下发生分支。
我们定义了 Prg 类型，它封装了指令数组并提供便捷的方法来构建和操作字节码程序：
type Prg type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
enum Ops {
Done
Char(Char)
Jump(Int)
Fork(Int)
} derive(Show, ToJson)
trait Show {
output(Self, &Logger) -> Unit
to_string(Self) -> String
}
Trait for types that can be converted to String
trait ToJson {
to_json(Self) -> Json
}
Trait for types that can be converted to Json
type Prg Array[Ops] derive(Show, ToJson)
fn Prg::push(self : Prg, inst : Ops) -> Unit
type Prg Array[Ops] derive(Show, ToJson)
enum Ops {
Done
Char(Char)
Jump(Int)
Fork(Int)
} derive(Show, ToJson)
fn Prg::inner(self : Prg) -> Array[Ops]
Convert newtype to its underlying type, automatically derived.
fn[T] Array::push(self : Array[T], value : T) -> Unit
Adds an element to the end of the array.
If the array is at capacity, it will be reallocated.
Example
test {
let v = []
v.push(3)
}
type Prg Array[Ops] derive(Show, ToJson)
fn Prg::length(self : Prg) -> Int
type Prg Array[Ops] derive(Show, ToJson)
fn Prg::inner(self : Prg) -> Array[Ops]
Convert newtype to its underlying type, automatically derived.
fn[T] Array::length(self : Array[T]) -> Int
Returns the number of elements in the array.
Parameters:
array : The array whose length is to be determined.
Returns the number of elements in the array as an integer.
Example:
test {
let arr = [1, 2, 3]
inspect(arr.length(), content="3")
let empty : Array[Int] = []
inspect(empty.length(), content="0")
}
type Prg Array[Ops] derive(Show, ToJson)
fn Prg::op_set(self : Prg, index : Int, inst : Ops) -> Unit
type Prg Array[Ops] derive(Show, ToJson)
enum Ops {
Done
Char(Char)
Jump(Int)
Fork(Int)
} derive(Show, ToJson)
Array[Ops]
Sets the element at the specified index in the array to a new value. The
original value at that index is overwritten.
Parameters:
array : The array to modify.index : The position in the array where the value will be set.value : The new value to assign at the specified index.
Throws an error if index is negative or greater than or equal to the length
of the array.
Example:
test {
let arr = [1, 2, 3]
arr[1] = 42
inspect(arr, content="[1, 42, 3]")
}
fn Prg::inner(self : Prg) -> Array[Ops]
Convert newtype to its underlying type, automatically derived.
Array[Ops]
Sets the element at the specified index in the array to a new value. The
original value at that index is overwritten.
Parameters:
array : The array to modify.index : The position in the array where the value will be set.value : The new value to assign at the specified index.
Throws an error if index is negative or greater than or equal to the length
of the array.
Example:
test {
let arr = [1, 2, 3]
arr[1] = 42
inspect(arr, content="[1, 42, 3]")
}
fn[T] Array::op_set(self : Array[T], index : Int, value : T) -> Unit
Sets the element at the specified index in the array to a new value. The
original value at that index is overwritten.
Parameters:
array : The array to modify.index : The position in the array where the value will be set.value : The new value to assign at the specified index.
Throws an error if index is negative or greater than or equal to the length
of the array.
Example:
test {
let arr = [1, 2, 3]
arr[1] = 42
inspect(arr, content="[1, 42, 3]")
}
Prg::of_ast 函数采用标准的 NFA 构造技术，将 AST 模式转换为虚拟机指令：
-
Seq(a, b)：
code for a
code for b
-
Rep(a, None) (无界重复)：
Fork L1, L2
L1: code for a
Jump L1
L2:
-
Rep(a, Some(n)) (固定重复)：
code for a
code for a
... (n times) ...
-
Opt(a) (可选)：
Fork L1, L2
L1: code for a
L2:
需要注意的是，Fork 构造器只接受一个地址参数，这是因为我们总是希望在 Fork 指令后继续执行下一条指令。
fn type Prg Array[Ops] derive(Show, ToJson)
fn Prg::of_ast(ast : Ast) -> Prg
enum Ast {
Chr(Char)
Seq(Ast, Ast)
Rep(Ast, Int?)
Opt(Ast)
} derive(Show, ToJson, Hash, Eq)
type Prg Array[Ops] derive(Show, ToJson)
type Prg Array[Ops] derive(Show, ToJson)
enum Ast {
Chr(Char)
Seq(Ast, Ast)
Rep(Ast, Int?)
Opt(Ast)
} derive(Show, ToJson, Hash, Eq)
fn Prg::push(self : Prg, inst : Ops) -> Unit
fn Prg::length(self : Prg) -> Int
fn Prg::push(self : Prg, inst : Ops) -> Unit
fn Prg::push(self : Prg, inst : Ops) -> Unit
fn Prg::op_set(self : Prg, index : Int, inst : Ops) -> Unit
fn Prg::length(self : Prg) -> Int
fn Prg::length(self : Prg) -> Int
fn Prg::push(self : Prg, inst : Ops) -> Unit
fn Prg::op_set(self : Prg, index : Int, inst : Ops) -> Unit
fn Prg::length(self : Prg) -> Int
type Prg Array[Ops] derive(Show, ToJson)
fn Prg::push(self : Prg, inst : Ops) -> Unit
在 Rob Pike 的实现中，虚拟机会在输入字符串结束后再执行一轮来处理最终的接受状态。为了明确这个过程，我们的 matches 函数采用两阶段方法来实现核心的虚拟机执行循环：
阶段一：字符处理。对于每个输入字符，处理当前上下文中所有活跃的线程。如果 Char 指令匹配当前字符，就在下一个上下文中创建新线程。Jump 和 Fork 指令会立即在当前上下文中产生新线程。处理完所有线程后，交换上下文并继续处理下一个字符。
阶段二：最终接受判断。处理完所有输入后，检查剩余线程中是否有 Done 指令。同时处理那些不消费输入的 Jump/Fork 指令。如果有任何线程到达 Done 指令，就返回 true。
fn type Prg Array[Ops] derive(Show, ToJson)
fn Prg::matches(self : Prg, data : StringView) -> Bool
type Prg Array[Ops] derive(Show, ToJson)
struct Ctx {
deque: @deque.Deque[Int]
visit: FixedArray[Bool]
}
fn Ctx::new(length : Int) -> Ctx
fn[T] Array::length(self : Array[T]) -> Int
Returns the number of elements in the array.
Parameters:
array : The array whose length is to be determined.
Returns the number of elements in the array as an integer.
Example:
test {
let arr = [1, 2, 3]
inspect(arr.length(), content="3")
let empty : Array[Int] = []
inspect(empty.length(), content="0")
}
struct Ctx {
deque: @deque.Deque[Int]
visit: FixedArray[Bool]
}
fn Ctx::new(length : Int) -> Ctx
fn[T] Array::length(self : Array[T]) -> Int
Returns the number of elements in the array.
Parameters:
array : The array whose length is to be determined.
Returns the number of elements in the array as an integer.
Example:
test {
let arr = [1, 2, 3]
inspect(arr.length(), content="3")
let empty : Array[Int] = []
inspect(empty.length(), content="0")
}
fn Ctx::add(self : Ctx, pc : Int) -> Unit
fn Ctx::pop(self : Ctx) -> Int?
fn[T] Array::op_get(self : Array[T], index : Int) -> T
Retrieves an element from the array at the specified index.
Parameters:
array : The array to get the element from.index : The position in the array from which to retrieve the element.
Returns the element at the specified index.
Throws a panic if the index is negative or greater than or equal to the
length of the array.
Example:
test {
let arr = [1, 2, 3]
inspect(arr[1], content="2")
}
fn Eq::equal(self : Char, other : Char) -> Bool
Compares two characters for equality.
Parameters:
self : The first character to compare.other : The second character to compare.
Returns true if both characters represent the same Unicode code point,
false otherwise.
Example:
test {
let a = 'A'
let b = 'A'
let c = 'B'
inspect(a == b, content="true")
inspect(a == c, content="false")
}
fn Ctx::add(self : Ctx, pc : Int) -> Unit
fn Add::add(self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:
self : The first integer operand.other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
test {
inspect(42 + 1, content="43")
inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
}
fn Ctx::add(self : Ctx, pc : Int) -> Unit
fn Ctx::add(self : Ctx, pc : Int) -> Unit
fn Ctx::add(self : Ctx, pc : Int) -> Unit
fn Add::add(self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:
self : The first integer operand.other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
test {
inspect(42 + 1, content="43")
inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
}
fn Ctx::reset(self : Ctx) -> Unit
fn Ctx::pop(self : Ctx) -> Int?
fn[T] Array::op_get(self : Array[T], index : Int) -> T
Retrieves an element from the array at the specified index.
Parameters:
array : The array to get the element from.index : The position in the array from which to retrieve the element.
Returns the element at the specified index.
Throws a panic if the index is negative or greater than or equal to the
length of the array.
Example:
test {
let arr = [1, 2, 3]
inspect(arr[1], content="2")
}
fn Ctx::add(self : Ctx, pc : Int) -> Unit
fn Ctx::add(self : Ctx, pc : Int) -> Unit
fn Ctx::add(self : Ctx, pc : Int) -> Unit
fn Add::add(self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:
self : The first integer operand.other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
test {
inspect(42 + 1, content="43")
inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
}
在 Rob Pike 的原始博客中，他使用递归函数来处理 Fork 和 Jump 指令，以保证线程按优先级执行。而我们这里采用了类似栈的结构来管理所有执行线程，这样可以自然地维护线程优先级：
struct Ctx {
deque : #alias(T, deprecated="`T` is deprecated, use `Deque` instead")
type @deque.Deque[A]
A double-ended queue (deque) backed by a growable circular buffer.
This implementation follows the Rust VecDeque design: only head and len
are stored, with tail computed on demand as (head + len - 1) % cap.
Layout:
Wrapped case (head + len > cap):
buf: [4, 5, _, _, _, 1, 2, 3]
^ ^
(tail) head
head = 5, len = 5, tail = (5 + 5 - 1) % 8 = 1
Logical order: [1, 2, 3, 4, 5]
Contiguous case (head + len <= cap):
buf: [_, 1, 2, 3, 4, 5, _, _]
^ ^
head (tail)
head = 1, len = 5, tail = (1 + 5 - 1) % 8 = 5
Logical order: [1, 2, 3, 4, 5]
Empty case (len == 0):
buf: [_, _, _, _]
^
head (tail is undefined, not accessed)
Invariants:
0 <= len <= buf.length()0 <= head < buf.length()- Element at index
i is at buf[(head + i) % buf.length()]
- When
len > 0: front is buf[head], back is buf[(head + len - 1) % cap]
- When
len == 0: no valid element, head can be any valid index
struct Ctx {
deque: @deque.Deque[Int]
visit: FixedArray[Bool]
}
fn Ctx::new(length : Int) -> Ctx
struct Ctx {
deque: @deque.Deque[Int]
visit: FixedArray[Bool]
}
fn[A] @moonbitlang/core/deque.new(capacity? : Int) -> @deque.Deque[A]
Creates a new empty deque with an optional initial capacity.
Parameters:
capacity : The initial capacity of the deque. If not specified, defaults
to 0 and will be automatically adjusted as elements are added.
Returns a new empty deque of type T[A] where A is the type of elements
the deque will hold.
Example
test {
let dq : @deque.Deque[Int] = @deque.new()
inspect(dq.length(), content="0")
inspect(dq.capacity(), content="0")
let dq : @deque.Deque[Int] = @deque.new(capacity=10)
inspect(dq.length(), content="0")
inspect(dq.capacity(), content="10")
}
fn[T] FixedArray::make(len : Int, init : T) -> FixedArray[T]
Creates a new fixed-size array with the specified length, initializing all
elements with the given value.
Parameters:
length : The length of the array to create. Must be non-negative.initial_value : The value used to initialize all elements in the array.
Returns a new fixed-size array of type FixedArray[T] with length
elements, where each element is initialized to initial_value.
Throws a panic if length is negative.
Example:
test {
let arr = FixedArray::make(3, 42)
inspect(arr[0], content="42")
inspect(arr.length(), content="3")
}
WARNING: A common pitfall is creating with the same initial value, for example:
test {
let two_dimension_array = FixedArray::make(10, FixedArray::make(10, 0))
two_dimension_array[0][5] = 10
assert_eq(two_dimension_array[5][5], 10)
}
This is because all the cells reference to the same object (the FixedArray[Int] in this case).
One should use makei() instead which creates an object for each index.
struct Ctx {
deque: @deque.Deque[Int]
visit: FixedArray[Bool]
}
fn Ctx::add(self : Ctx, pc : Int) -> Unit
struct Ctx {
deque: @deque.Deque[Int]
visit: FixedArray[Bool]
}
fn[T] FixedArray::op_get(self : FixedArray[T], idx : Int) -> T
Retrieves an element at the specified index from a fixed-size array. This
function implements the array indexing operator [].
Parameters:
array : The fixed-size array to access.index : The position in the array from which to retrieve the element.
Returns the element at the specified index.
Panics if the index is out of bounds.
Example:
test {
let arr = FixedArray::make(3, 42)
inspect(arr[1], content="42")
}
fn[A] @deque.Deque::push_back(self : @deque.Deque[A], value : A) -> Unit
Adds an element to the back of the deque.
If the deque is at capacity, it will be reallocated.
Example
test {
let dv = @deque.from_array([1, 2, 3, 4, 5])
dv.push_back(6)
assert_eq(dv.back(), Some(6))
}
fn[T] FixedArray::op_set(self : FixedArray[T], idx : Int, val : T) -> Unit
Sets the value at the specified index in a fixed-size array.
Parameters:
array : The fixed-size array to be modified.index : The index at which to set the value. Must be non-negative and
less than the array's length.value : The value to be set at the specified index.
Throws a runtime error if the index is out of bounds (less than 0 or greater
than or equal to the array's length).
Example:
test {
let arr = FixedArray::make(3, 0)
arr.set(1, 42)
inspect(arr[1], content="42")
}
struct Ctx {
deque: @deque.Deque[Int]
visit: FixedArray[Bool]
}
fn Ctx::pop(self : Ctx) -> Int?
struct Ctx {
deque: @deque.Deque[Int]
visit: FixedArray[Bool]
}
fn[A] @deque.Deque::pop_back(self : @deque.Deque[A]) -> A?
Removes a back element from a deque and returns it, or None if it is empty.
Example
test {
let dv = @deque.from_array([1, 2, 3, 4, 5])
assert_eq(dv.pop_back(), Some(5))
}
fn[T] FixedArray::op_set(self : FixedArray[T], idx : Int, val : T) -> Unit
Sets the value at the specified index in a fixed-size array.
Parameters:
array : The fixed-size array to be modified.index : The index at which to set the value. Must be non-negative and
less than the array's length.value : The value to be set at the specified index.
Throws a runtime error if the index is out of bounds (less than 0 or greater
than or equal to the array's length).
Example:
test {
let arr = FixedArray::make(3, 0)
arr.set(1, 42)
inspect(arr[1], content="42")
}
struct Ctx {
deque: @deque.Deque[Int]
visit: FixedArray[Bool]
}
fn Ctx::reset(self : Ctx) -> Unit
struct Ctx {
deque: @deque.Deque[Int]
visit: FixedArray[Bool]
}
fn[A] @deque.Deque::clear(self : @deque.Deque[A]) -> Unit
Clears the deque, removing all values.
This method has no effect on the allocated capacity of the deque, only setting the length to 0.
Example
test {
let dv = @deque.from_array([1, 2, 3, 4, 5])
dv.clear()
inspect(dv.length(), content="0")
}
fn[T] FixedArray::fill(self : FixedArray[T], value : T, start? : Int, end? : Int) -> Unit
Fill the array with a given value.
This method fills all or part of a FixedArray with the given value.
Parameters
value: The value to fill the array withstart: The starting index (inclusive, default: 0)end: The ending index (exclusive, optional)
If end is not provided, fills from start to the end of the array.
If start equals end, no elements are modified.
Panics
- Panics if
start is negative or greater than or equal to the array length
- Panics if
end is provided and is less than start or greater than array length
- Does nothing if the array is empty
Example
test {
// Fill entire array
let fa : FixedArray[Int] = [0, 0, 0, 0, 0]
fa.fill(3)
inspect(fa, content="[3, 3, 3, 3, 3]")
// Fill from index 1 to 3 (exclusive)
let fa2 : FixedArray[Int] = [0, 0, 0, 0, 0]
fa2.fill(9, start=1, end=3)
inspect(fa2, content="[0, 9, 9, 0, 0]")
// Fill from index 2 to end
let fa3 : FixedArray[String] = ["a", "b", "c", "d"]
fa3.fill("x", start=2)
inspect(
fa3,
content=(
#|["a", "b", "x", "x"]
),
)
}
visit 数组用于过滤掉低优先级的重复线程。添加新线程时，我们 先通过 visit 数组检查该线程是否已存在于 deque 中。如果已存在就直接丢弃；否则加入 deque 并标记为已访问。这个机制对于处理像 (a?)* 这样可能无限扩展的模式很重要，能够有效避免无限循环或指数级的线程爆炸。
我们通过一个对很多正则表达式实现都构成挑战的病理性案例来比较这两种方法：
test (b : #alias(T)
type @bench.Bench
fn String::repeat(self : String, n : Int) -> String
Returns a new string with self repeated n times.
enum Ast {
Chr(Char)
Seq(Ast, Ast)
Rep(Ast, Int?)
Opt(Ast)
} derive(Show, ToJson, Hash, Eq)
fn Ast::chr(chr : Char) -> Ast
enum Ast {
Chr(Char)
Seq(Ast, Ast)
Rep(Ast, Int?)
Opt(Ast)
} derive(Show, ToJson, Hash, Eq)
fn Ast::opt(self : Ast) -> Ast
fn Ast::rep(self : Ast, n~ : Int) -> Ast
fn Ast::seq(self : Ast, other : Ast) -> Ast
fn Ast::rep(self : Ast, n~ : Int) -> Ast
enum Exp {
Nil
Eps
Chr(Char)
Alt(Exp, Exp)
Seq(Exp, Exp)
Rep(Exp)
} derive(Show, Hash, Eq, Compare, ToJson)
fn Exp::of_ast(ast : Ast) -> Exp
fn @bench.Bench::bench(self : @bench.Bench, name~ : String, f : () -> Unit, count? : UInt) -> Unit
Run a benchmark in batch mode
fn Exp::matches(self : Exp, s : String) -> Bool
fn[T] ignore(t : T) -> Unit
Evaluates an expression and discards its result. This is useful when you want
to execute an expression for its side effects but don't care about its return
value, or when you want to explicitly indicate that a value is intentionally
unused.
Parameters:
value : The value to be ignored. Can be of any type.
Example:
test {
let x = 42
ignore(x) // Explicitly ignore the value
let mut sum = 0
ignore([1, 2, 3].iter().each(x => sum = sum + x)) // Ignore the Unit return value of each()
}
type Prg Array[Ops] derive(Show, ToJson)
fn Prg::of_ast(ast : Ast) -> Prg
fn @bench.Bench::bench(self : @bench.Bench, name~ : String, f : () -> Unit, count? : UInt) -> Unit
Run a benchmark in batch mode
fn Prg::matches(self : Prg, data : StringView) -> Bool
fn[T] ignore(t : T) -> Unit
Evaluates an expression and discards its result. This is useful when you want
to execute an expression for its side effects but don't care about its return
value, or when you want to explicitly indicate that a value is intentionally
unused.
Parameters:
value : The value to be ignored. Can be of any type.
Example:
test {
let x = 42
ignore(x) // Explicitly ignore the value
let mut sum = 0
ignore([1, 2, 3].iter().each(x => sum = sum + x)) // Ignore the Unit return value of each()
}
模式 (a?){n}a{n} 是回溯引擎中典型的指数爆炸案例。这个模式有 n 种不同的方式来匹配 n 个 'a' 字符，在朴素的实现中会产生指数级的搜索空间。
name time (mean ± σ) range (min … max)
derive 41.78 µs ± 0.14 µs 41.61 µs … 42.13 µs in 10 × 2359 runs
thompson 12.79 µs ± 0.04 µs 12.74 µs … 12.84 µs in 10 × 7815 runs
从基准测试结果可以看出，在这种情况下虚拟机方法明显快于导数方法。导数方法需要频繁分配中间的正则表达式结构，带来了更高的开销和更慢的性能。相比之下，虚拟机执行的是一组固定的指令，一旦双端队列扩展到完整大小后，就很少需要分配新的结构了。
不过，导数方法在理论分析上更简洁。我们可以很容易地证明算法的终止性，因为需要计算的导数数量受到 AST 大小的限制，并且随着 deriv 函数的每次递归调用而严格递减。而虚拟机方法则不同，如果输入的 Prg 包含无限循环，程序可能永远不会终止，这就需要仔细处理线程优先级，以避免无限循环和线程数量的指数级增长。
