16장: 패턴 매칭 컴파일
새 파일
src/match_compile.rssrc/usefulness.rssrc/env.rs변경된 파일
src/core.rssrc/core_lint.rssrc/eval.rssrc/io_lower.rssrc/lib.rssrc/main.rs
동기
우리 인터프리터는 패턴을 위에서 아래로 차례대로 시도하므로 그 의미를 따라가기 쉽습니다. 네이티브 컴파일러는 이 과정을 태그를 검사하고, 필드를 읽어 오고, 분기하는 명령어로 바꾸어야 합니다. 각 패턴을 따로따로 번역할 수도 있지만, 그러면 같은 값을 몇 번이고 다시 검사하는 일이 잦을 것입니다.
대신 우리는 패턴들을 한꺼번에 살펴보겠습니다. 패턴들을 행렬에 놓고, 쓸모 있는 검사를 하나 고른 다음, 그 결과에 따라 남은 작업을 나누십시오. 이렇게 하면 결정 트리가 만들어집니다. 합류 지점(join point)을 쓰면 서로 다른 경로가 도달하는 코드를 공유할 수 있으며, 가드가 실패했을 때 넘어가는 다음 절도 여기에 포함됩니다.
또한 어떤 입력이 패턴들 사이로 빠져나가지는 않는지, 혹은 뒤쪽 절이 매칭할 수 있는 것을 앞쪽 절이 이미 모두 잡아 버리지는 않았는지도 따져 볼 수 있습니다. 이는 흐뭇한 연결 고리입니다. 값의 모양을 이해하면 패턴을 실행하는 데에도, 패턴 속 실수를 설명하는 데에도 도움이 됩니다.
현재의 언어
새로운 소스 구문은 없습니다. 이전 프로그램들은 패턴이 매칭된 뒤에 실패하는 가드를 포함하여 모두 같은 결과를 냅니다:
f (Just x) | x < 0 = 0
f (Just x) = x
f Nothing = 99
main = print (f (Just 42))
첫 번째 절은 Just 42를 알아보지만, 그 가드가 실패합니다. 실행은 두 번째 절을 시도하여 42를 반환해야 합니다. 패턴 매칭 실패를 보고하거나 Nothing 절로 건너뛰어서는 안 됩니다. 지역 where 바인딩은 자신이 속한 등식의 가드와 우변에서 계속 스코프 안에 있습니다.
이제 검사기는 match에 난 구멍을 보여 줄 수 있습니다. W0001에는 처리되지 않는 입력의 예가 포함되며, W0002는 앞선 절 때문에 도달할 수 없게 된 절을 짚어 줍니다. 이들은 경고이므로 프로그램은 여전히 실행할 수 있습니다. 런타임에 처리되지 않은 입력을 만나면 여전히 fun: pattern match failure at FILE:LINE:COL을 보고합니다.
이론
match를 행이 절이고 열이 검사 대상(scrutinee)인 행렬로 생각해 보십시오. 생성자 C에 대해 열을 특수화하면 C와 매치될 수 있는 행을 남기고, 그 생성자를 제거한 뒤, 그 필드들을 새 열로 삽입합니다. 기본 행렬(default matrix)은 선택된 패턴이 다른 어떤 값과도 매치될 수 있는 행을 유지합니다. 이것이 Maranget이 설명한 결정 트리 방식입니다 (Maranget 2008).
Fun은 첫 번째 행에서 반박 가능한 패턴을 담고 있는 첫 번째 열을 고릅니다. 이 단순한 휴리스틱은 결정적이며 추적하기 쉽습니다. 이것이 모든 행렬에 대해 검사 횟수를 최소화한다는 주장은 아닙니다. 와일드카드, 변수, as-패턴은 값을 검사하지 않습니다. 이들의 바인딩은 최종적으로 실행될 절 본문을 위해 기록됩니다. 생성자 패턴은 태그가 매치된 뒤에야 필드를 드러냅니다.
유한한 데이터 타입은 알려진 생성자 집합을 가집니다. 정수와 문자 리터럴에는 기본 경로가 필요합니다. 검사한 리터럴의 유한한 집합으로는 그 값의 정의역을 모두 덮을 수 없기 때문입니다. 문자열 패턴은 동등성 검사가 됩니다. Double 패턴도 기본 동등성을 사용하며, 이를 통해 양의 0과 음의 0이 같다는 점을 포함한 언어의 부동소수점 비교 동작을 그대로 유지합니다.
유용성(usefulness)은 후보 패턴 벡터가 앞선 커버링 행들이 매치하지 않는 값을 허용하는지를 묻습니다 (Maranget 2007). 유용하지 않은 소스 행은 중복입니다. 유용한 전체 와일드카드 후보는 누락된 경우의 증거(witness)를 제공합니다. 가드는 커버리지 판단을 복잡하게 만듭니다. 패턴이 매치되더라도 다음 절로 넘어갈 수 있기 때문입니다. 구현은 가드 중 하나가 문자 그대로 True일 때만 가드가 있는 행을 커버링 행으로 취급합니다. 임의의 불리언 식을 증명하려고 시도하지는 않습니다.
하나의 질문, 두 가지 검사
두 경고를 같은 질문으로 바꾸는 깔끔한 방법이 있습니다. 이 패턴은 앞선 패턴들이 놓친 무언가와 매치됩니까? Maranget은 이런 패턴을 유용하다고 부릅니다. 앞선 행들을 P, 후보 패턴 벡터를 q라 할 때, 이 질문을 U(P, q)로 쓰겠습니다. 증거(witness)란 P를 빠져나가면서 q와 매치되는 실제 형태입니다 (Maranget 2007).
도달 가능성을 검사할 때 P는 현재 절보다 앞선 덮는 행들을 담고, q는 그 절의 패턴 벡터입니다. 완전성을 따질 때는 P가 커버하는 모든 행을 담고, q는 전부 와일드카드로 이루어진 벡터입니다. 첫 번째 질의는 어떤 절이 새로운 경우를 하나라도 추가하는지 묻습니다. 두 번째 질의는 아직 빠진 것이 남아 있는지 묻습니다. 커버리지를 결정하는 것은 행들 전체입니다. 앞선 절 가운데 어느 하나도 어떤 절을 완전히 덮지 못하더라도 그 절은 도달 불가능할 수 있습니다.
Maybe Bool과 Bool, 두 인자를 받는 함수를 생각해 봅시다:
choose Nothing _ = 0
choose (Just True) _ = 1
choose (Just _) False = 2
우변은 무시하고 인자 열만 남겨 둡시다:
| 행 | 첫 번째 인자 | 두 번째 인자 |
|---|---|---|
| 1 | Nothing | _ |
| 2 | Just True | _ |
| 3 | Just _ | False |
(_, _)가 유용한지 물어봅시다. 첫 번째 열에 Maybe의 두 생성자가 모두 들어 있으므로, 생성자 집합의 각 구성원을 하나씩 살펴봅니다. Nothing으로 특수화하면 2행과 3행이 버려지고 두 번째 인자 자리에 와일드카드가 남습니다. 그 분기는 덮여 있습니다. Just로 특수화하면 1행이 버려지고 첫 번째 열이 그 생성자의 유일한 필드로 바뀝니다:
| 행 | Just 안의 값 | 두 번째 인자 |
|---|---|---|
| 2 | True | _ |
| 3 | _ | False |
True 분기는 2행이 덮습니다. False 분기에는 3행만 남으며, 이 행은 두 번째 인자가 False인 경우를 덮습니다. 덮이지 않은 두 번째 인자는 True입니다. 필드를 감싸 생성자를 다시 세우면 원래 인자 벡터에 대한 증인 (Just False, True)를 얻습니다. choose (Just False) True = 3을 추가하면 이 매치가 완전해집니다. 원래의 어떤 절도 혼자서는 모든 입력을 덮지 못했지만, 그 뒤에 오는 절은 모두 도달 불가능합니다.
특수화와 기본 행렬
usefulness.rs는 첫 번째 열에 대해 탐색을 구현합니다. 선택된 패턴과 생성자 집합이 다음 문제를 결정합니다:
- 생성자 후보.
C(p1, ..., pk)의 경우,C나 와일드카드로 시작하는 행을 남깁니다.C를 그 필드들로 바꿉니다. 와일드카드는k개의 와일드카드로 확장합니다. 다른 생성자로 시작하는 행은 버리고, 질의에도 같은 확장을 적용합니다. - 와일드카드 후보, 완전한 족. 열의 데이터 타입에 속한 생성자가 모두 나타나면 각 생성자에 대해 특수화합니다. 유용한 분기가 하나라도 있으면 그 분기가 증인을 제공합니다.
- 와일드카드 후보, 불완전한 족. 기본 행렬을 탐색합니다. 와일드카드로 시작하는 행만 남기고 그 첫 번째 열을 버립니다. 유용한 접미사 앞에는 빠진 생성자를 붙일 수 있습니다. 리터럴 도메인은 이 경로로 처리하며, 검사한 머리에 없는 리터럴을 하나 고릅니다.
열이 0개인 경우에는 빈 행렬과 빈 행을 구별합니다. 행이 없으면 남은 빈 벡터를 덮는 것이 없으므로 그 벡터는 유용합니다. 빈 행이 있으면 앞선 절이 이미 남은 모든 것과 매치되므로 유용하지 않습니다. 이 작은 기저 사례들 덕분에 탐색은 재귀 데이터 타입의 모든 값을 열거하지 않고도 중첩된 생성자를 처리할 수 있습니다.
알고리즘은 돌아오면서 벗겨 냈던 생성자를 각각 증인 필드를 감싸 다시 세웁니다. 그래서 Fun의 useful은 단순한 불리언이 아니라 선택적인 패턴 벡터를 반환합니다. 경고 드라이버는 빠진 구체적인 형태를 출력하고, 그 형태를 임시 커버리지 행렬에 추가한 뒤, 최대 세 개의 예시를 찾을 때까지 다시 탐색할 수 있습니다.
가드와 커버리지의 한계
가드가 있는 절은 앞선 절들이 이미 그 패턴을 덮고 있어서 도달 불가능할 수 있습니다. 그러나 가드가 실패할 수 있으므로, 대개 그 절 자체로는 커버리지를 확립하지 못합니다. Fun은 그 행을 앞선 커버리지와 대조해 검사한 뒤, 가드가 없거나 구문상 리터럴 True 가드를 가진 경우에만 커버리지에 추가합니다. 임의의 가드 표현식을 풀지는 않습니다. 따라서 보고된 빈틈은 이 보수적인 정책을 반영한 것일 수 있으며, 패턴이 유용하다고 해서 그 가드가 언젠가 성공한다는 것이 증명되지는 않습니다.
이 분석은 타입이 붙은 생성자 집합을 사용하며, 변수를 와일드카드로 취급합니다. as-패턴의 이름은 커버리지를 바꾸지 않습니다. 재귀적인 필드 타입에 값이 존재하는지(inhabited)는 증명하지 않습니다. 컴파일과 검사는 별개로 유지됩니다. 결정 트리는 이러한 경고와 관계없이 절의 순서와 가드 폴스루(fallthrough)를 보존해야 합니다.
결정 트리 공유하기
조인 포인트는 어떤 식에 국한된 컨티뉴에이션에 이름을 붙인 것입니다. 조인 포인트의 매개변수는 공유되는 본문에 필요한 값을 전달하며, 모든 점프는 완전히 적용된 꼬리 전달입니다. 일반 함수와 달리, 조인은 탈출하거나 값으로 전달될 수 없습니다. 이 구분은 이후 ANF에서 조인을 사용하는 방식을 미리 보여 줍니다 (Maurer et al. 2017).
구현
컴파일러의 내부 행은 남은 패턴과 최종 우변을 분리합니다. values는 현재 결정 경로를 따라 바인딩된 값을 기록합니다. target과 params는 공유되는 절 본문을 식별합니다.
#![allow(unused)]
fn main() {
use crate::{
core::{self, Alt, AltCon, Expr, Id, Pat, RowBody, Type},
names,
session::{Session, Stop},
source::Span,
};
use std::collections::BTreeMap;
struct Compiler<'a> {
sess: &'a mut Session,
constructors: Vec<core::ConDecl>,
truths: std::collections::BTreeSet<u32>,
}
impl Compiler<'_> {
fn fresh(&mut self, ty: Type) -> Id {
Id {
name: self.sess.fresh_id("$case"),
ty,
}
}
fn fields(&self, con: &crate::data::ConId, ty: &Type) -> Vec<Type> {
let c = &self.constructors[con.index as usize];
let args = match ty {
Type::Con(_, args) => args.as_slice(),
Type::Bool => &[],
_ => unreachable!("typed data scrutinee"),
};
c.fields
.iter()
.map(|t| crate::elaborate::instantiate(t, &c.parameters, args))
.collect()
}
fn boolean(
&mut self,
test: Expr,
yes: Expr,
no: Expr,
result: &Type,
) -> Expr {
let truth = self
.constructors
.iter()
.find(|c| c.id.name == "True")
.unwrap()
.id
.clone();
Expr::Case(
Box::new(test),
self.fresh(Type::Bool),
result.clone(),
vec![
Alt {
con: AltCon::Con(truth),
binders: vec![],
rhs: yes,
},
Alt {
con: AltCon::Default,
binders: vec![],
rhs: no,
},
],
)
}
fn group(&mut self, g: core::BindGroup) -> core::BindGroup {
core::BindGroup {
recursive: g.recursive,
binds: g
.binds
.into_iter()
.map(|mut b| {
b.rhs = Box::new(self.expr(*b.rhs));
b
})
.collect(),
}
}
fn expr(&mut self, e: Expr) -> Expr {
match e {
Expr::Match(m) => self.compile(m),
Expr::Lam(i, b) => Expr::Lam(i, Box::new(self.expr(*b))),
Expr::TyLam(v, b) => Expr::TyLam(v, Box::new(self.expr(*b))),
Expr::TyApp(b, t) => Expr::TyApp(Box::new(self.expr(*b)), t),
e @ Expr::App(..) => {
let mut work = vec![Some(e)];
let mut output = Vec::new();
while let Some(job) = work.pop() {
match job {
Some(Expr::App(a, b)) => {
work.push(None);
work.push(Some(*b));
work.push(Some(*a));
}
Some(e) => output.push(self.expr(e)),
None => {
let b = output.pop().unwrap();
let a = output.pop().unwrap();
output
.push(Expr::App(Box::new(a), Box::new(b)));
}
}
}
output.pop().unwrap()
}
Expr::Let(g, b) => {
Expr::Let(self.group(g), Box::new(self.expr(*b)))
}
Expr::Con(c, ts, args) => Expr::Con(
c,
ts,
args.into_iter().map(|e| self.expr(e)).collect(),
),
Expr::Prim(p, ts, args, s) => Expr::Prim(
p,
ts,
args.into_iter().map(|e| self.expr(e)).collect(),
s,
),
other => other,
}
}
fn compile(&mut self, m: core::Match) -> Expr {
crate::usefulness::warn(
self.sess,
&m,
&self.constructors,
&self.truths,
);
let mut rows = vec![];
let mut bodies = vec![];
for r in m.rows {
let mut params = vec![];
for p in &r.pats {
binders(p, &mut params)
}
let target = self.sess.fresh_id("$rhs");
rows.push(Row {
pats: r.pats,
values: BTreeMap::new(),
target: target.clone(),
params: params.clone(),
});
bodies.push((target, params, r.locals, r.body));
}
let mut definitions = vec![];
for (index, (target, params, locals, body)) in
bodies.into_iter().enumerate().rev()
{
let fail = self.sess.fresh_id("$fail");
let mut body = match body {
RowBody::Plain(e) => self.expr(*e),
RowBody::Guarded(gs) => {
let residual = self.tree(
m.scruts.clone(),
rows[index + 1..].to_vec(),
&m.result,
m.span,
);
definitions.push((fail.clone(), vec![], residual));
let mut fallback =
Expr::Jump(fail.clone(), vec![], m.result.clone());
for (g, e) in gs.into_iter().rev() {
let g = self.expr(g);
let e = self.expr(e);
fallback = self.boolean(g, e, fallback, &m.result)
}
fallback
}
};
for g in locals.into_iter().rev() {
body = Expr::Let(self.group(g), Box::new(body))
}
definitions.push((target, params, body));
}
let mut body = self.tree(m.scruts, rows, &m.result, m.span);
for (id, params, rhs) in definitions.into_iter().rev() {
body = Expr::Join(id, params, Box::new(rhs), Box::new(body))
}
body
}
fn tree(
&mut self,
scruts: Vec<Id>,
mut rows: Vec<Row>,
result: &Type,
span: Span,
) -> Expr {
if rows.is_empty() {
return Expr::PatternFail(span, result.clone());
}
// Bind variables/as-patterns without copying their unique Core binders.
for row in &mut rows {
for (p, s) in row.pats.iter_mut().zip(&scruts) {
loop {
match p.clone() {
Pat::Var(id) => {
row.values.insert(id.unique(), s.clone());
*p = Pat::Wild;
break;
}
Pat::As(id, inner) => {
row.values.insert(id.unique(), s.clone());
*p = *inner
}
_ => break,
}
}
}
}
let Some(column) =
rows[0].pats.iter().position(|p| !matches!(p, Pat::Wild))
else {
let row = &rows[0];
return Expr::Jump(
row.target.clone(),
row.params
.iter()
.map(|p| Expr::Var(row.values[&p.unique()].clone()))
.collect(),
result.clone(),
);
};
let scrut = scruts[column].clone();
let mut heads = vec![];
for row in &rows {
let head = match &row.pats[column] {
Pat::Con(c, _) => AltCon::Con(c.clone()),
Pat::Lit(l) => AltCon::Lit(l.clone()),
_ => continue,
};
if !heads.contains(&head) {
heads.push(head)
}
}
let mut alts = vec![];
for head in heads {
let fields = match &head {
AltCon::Con(c) => self.fields(c, &scrut.ty),
_ => vec![],
};
let params = fields
.into_iter()
.map(|t| self.fresh(t))
.collect::<Vec<_>>();
let mut specialized = vec![];
for mut row in rows.clone() {
let p = row.pats.remove(column);
let fields = match (&head, p) {
(_, Pat::Wild) => vec![Pat::Wild; params.len()],
(AltCon::Con(c), Pat::Con(d, ps)) if *c == d => ps,
(AltCon::Lit(a), Pat::Lit(b)) if *a == b => vec![],
_ => continue,
};
row.pats.splice(column..column, fields);
specialized.push(row)
}
let mut columns = scruts.clone();
columns.splice(column..=column, params.clone());
let rhs = self.tree(columns, specialized, result, span);
alts.push(Alt {
con: head,
binders: params,
rhs,
});
}
let mut defaults = vec![];
for mut row in rows {
if matches!(row.pats[column], Pat::Wild) {
row.pats.remove(column);
defaults.push(row)
}
}
let mut columns = scruts;
columns.remove(column);
let fallback = self.tree(columns, defaults, result, span);
if matches!(scrut.ty, Type::String | Type::Double) {
let mut body = fallback;
for alt in alts.into_iter().rev() {
let AltCon::Lit(l) = alt.con else {
unreachable!()
};
let primitive = if matches!(scrut.ty, Type::String) {
crate::primitives::Prim::StrEq
} else {
crate::primitives::Prim::DblEq
};
let test = Expr::Prim(
crate::ast::Op::Runtime(primitive),
vec![],
vec![Expr::Var(scrut.clone()), Expr::Lit(l)],
span,
);
body = self.boolean(test, alt.rhs, body, result);
}
body
} else {
alts.push(Alt {
con: AltCon::Default,
binders: vec![],
rhs: fallback,
});
Expr::Case(
Box::new(Expr::Var(scrut.clone())),
self.fresh(scrut.ty),
result.clone(),
alts,
)
}
}
}
fn binders(p: &Pat, out: &mut Vec<Id>) {
match p {
Pat::Var(i) => out.push(i.clone()),
Pat::As(i, p) => {
out.push(i.clone());
binders(p, out)
}
Pat::Con(_, ps) => {
for p in ps {
binders(p, out)
}
}
_ => {}
}
}
/// Compile every nested match; generated binders come from the shared unique supply.
pub fn compile(
sess: &mut Session,
mut program: core::Program,
) -> Result<core::Program, Stop> {
let mut compiler = Compiler {
sess,
constructors: program.constructors.clone(),
truths: program.groups.iter().flat_map(|g| &g.binds)
.filter(|b| matches!(&*b.rhs, Expr::Con(c, _, _) if c.name == "True"))
.map(|b| b.name.unique()).collect(),
};
program.groups = program
.groups
.into_iter()
.map(|g| compiler.group(g))
.collect();
compiler.sess.finish(program)
}
#[derive(Clone)]
struct Row {
pats: Vec<Pat>,
values: BTreeMap<u32, Id>,
target: names::Id,
params: Vec<Id>,
}
}테스트를 만들기 전에 Compiler::compile은 각 절에 매개변수화된 우변 조인을 할당합니다. 또한 그 절 다음에 오는 나머지 행렬을 실패 조인으로 컴파일합니다. 가드는 순서대로 실행됩니다. 모두 실패하면 점프를 통해 그 나머지 행렬로 들어갑니다. 따라서 여러 리프가 절 본문을 복사하지 않고도 하나의 절 본문에 도달할 수 있으며, 실패한 여러 가드가 하나의 폴백을 함께 사용할 수 있습니다.
생성자 분기는 검사 대상(scrutinee)의 실제 타입 인자로 필드를 바인딩해야 합니다. 보조 함수는 선언을 찾아 그 매개변수를 치환합니다:
#![allow(unused)]
fn main() {
fn fields(&self, con: &crate::data::ConId, ty: &Type) -> Vec<Type> {
let c = &self.constructors[con.index as usize];
let args = match ty {
Type::Con(_, args) => args.as_slice(),
Type::Bool => &[],
_ => unreachable!("typed data scrutinee"),
};
c.fields
.iter()
.map(|t| crate::elaborate::instantiate(t, &c.parameters, args))
.collect()
}
}예를 들어 Just를 Maybe Int에서 특수화하면 선언의 인스턴스화되지 않은 타입 변수가 아니라 Int를 바인딩합니다. 같은 규칙이 레코드 프로젝션에도 중요합니다: 레코드 프로젝션의 단일 생성자 매치는 이제 태그 분기와 일반 필드 바인더가 됩니다. Core 린트는 이렇게 인스턴스화된 타입을 독립적으로 검사합니다.
Compiler::tree는 행렬을 재귀적으로 처리합니다. 빈 행렬은 PatternFail이 됩니다. 반박 가능한 패턴이 없는 첫 행은 바인더에 대해 누적된 값을 넘기며 해당 절의 조인으로 점프합니다. 그렇지 않으면 선택된 열은 특수화된 하위 트리들과 기본 하위 트리를 갖춘 평평한 Case를 만들거나, 문자열 및 Double 리터럴의 경우 동등성 테스트를 만듭니다.
경고 패스는 원래의 중첩 패턴을 그 표현이 사라지기 전에 사용합니다. 이 패스의 특수화 헬퍼는 앞에서 따라가 본 행렬 연산입니다:
#![allow(unused)]
fn main() {
use crate::{
core::{ConDecl, Lit, Match, Pat, RowBody, Type},
diagnostics::{Diagnostic, ErrorCode, Severity},
session::Session,
};
fn peel(p: &Pat) -> &Pat {
if let Pat::As(_, p) = p { peel(p) } else { p }
}
fn wild(p: &Pat) -> bool {
matches!(peel(p), Pat::Wild | Pat::Var(_))
}
fn same(a: &Pat, b: &Pat) -> bool {
match (peel(a), peel(b)) {
(Pat::Con(a, _), Pat::Con(b, _)) => a == b,
(Pat::Lit(Lit::Double(a)), Pat::Lit(Lit::Double(b))) => {
f64::from_bits(*a) == f64::from_bits(*b)
}
(Pat::Lit(a), Pat::Lit(b)) => a == b,
_ => false,
}
}
fn fields(head: &Pat, ty: &Type, cons: &[ConDecl]) -> Vec<Type> {
match peel(head) {
Pat::Con(id, _) => {
let c = &cons[id.index as usize];
let args = match ty {
Type::Con(_, args) => args.as_slice(),
_ => &[],
};
c.fields
.iter()
.map(|t| {
crate::elaborate::instantiate(t, &c.parameters, args)
})
.collect()
}
_ => vec![],
}
}
fn family(ty: &Type, cons: &[ConDecl]) -> Vec<Pat> {
cons.iter()
.filter(|c| match (&c.result, ty) {
(Type::Bool, Type::Bool) => true,
(Type::Con(a, _), Type::Con(b, _)) => a == b,
_ => false,
})
.map(|c| Pat::Con(c.id.clone(), vec![Pat::Wild; c.fields.len()]))
.collect()
}
/// Return a witness matched by the query but not by any covering row.
pub fn useful(
matrix: &[Vec<Pat>],
query: &[Pat],
types: &[Type],
cons: &[ConDecl],
) -> Option<Vec<Pat>> {
if query.is_empty() {
return matrix.is_empty().then(Vec::new);
}
let q = peel(&query[0]);
if !wild(q) {
let mut ts = fields(q, &types[0], cons);
let n = ts.len();
ts.extend_from_slice(&types[1..]);
let mut qs = match q {
Pat::Con(_, ps) => ps.clone(),
_ => vec![],
};
qs.extend_from_slice(&query[1..]);
let mut witness =
useful(&specialize(matrix, q, n), &qs, &ts, cons)?;
let children = witness.drain(..n).collect();
let p = match q {
Pat::Con(c, _) => Pat::Con(c.clone(), children),
_ => q.clone(),
};
witness.insert(0, p);
return Some(witness);
}
let heads = matrix
.iter()
.filter(|r| !wild(&r[0]))
.map(|r| peel(&r[0]).clone())
.collect::<Vec<_>>();
let all = family(&types[0], cons);
if !all.is_empty()
&& all.iter().all(|h| heads.iter().any(|p| same(h, p)))
{
for head in all {
let mut ts = fields(&head, &types[0], cons);
let n = ts.len();
ts.extend_from_slice(&types[1..]);
let mut qs = vec![Pat::Wild; n];
qs.extend_from_slice(&query[1..]);
if let Some(mut w) =
useful(&specialize(matrix, &head, n), &qs, &ts, cons)
{
let children = w.drain(..n).collect();
let Pat::Con(c, _) = head else { unreachable!() };
w.insert(0, Pat::Con(c, children));
return Some(w);
}
}
None
} else {
let defaults = matrix
.iter()
.filter(|r| wild(&r[0]))
.map(|r| r[1..].to_vec())
.collect::<Vec<_>>();
let mut witness =
useful(&defaults, &query[1..], &types[1..], cons)?;
let missing = all
.into_iter()
.find(|h| !heads.iter().any(|p| same(h, p)))
.unwrap_or_else(|| {
for n in 0..=heads.len() {
let p = match types[0] {
Type::Int => Pat::Lit(Lit::Int(n as i64)),
Type::Char => Pat::Lit(Lit::Char(
char::from_u32(97 + n as u32).unwrap_or('\0'),
)),
Type::String => {
Pat::Lit(Lit::String("x".repeat(n)))
}
Type::Double => {
Pat::Lit(Lit::Double((n as f64).to_bits()))
}
_ => return Pat::Wild,
};
if !heads.iter().any(|h| same(&p, h)) {
return p;
}
}
unreachable!()
});
witness.insert(0, missing);
Some(witness)
}
}
fn covers(
body: &RowBody,
truths: &std::collections::BTreeSet<u32>,
) -> bool {
match body {
RowBody::Plain(_) => true,
RowBody::Guarded(gs) => gs.iter().any(|(g, _)| match g {
crate::core::Expr::Con(c, _, _) => c.name == "True",
crate::core::Expr::Global(id) => truths.contains(&id.unique()),
_ => false,
}),
}
}
/// Warnings do not alter the decision tree; unmatched execution still fails at runtime.
pub fn warn(
sess: &mut Session,
m: &Match,
cons: &[ConDecl],
truths: &std::collections::BTreeSet<u32>,
) {
let types = m.scruts.iter().map(|i| i.ty.clone()).collect::<Vec<_>>();
let mut matrix = vec![];
for (index, row) in m.rows.iter().enumerate() {
if useful(&matrix, &row.pats, &types, cons).is_none()
&& !(index > 0 && m.rows[index - 1].span == row.span)
{
let mut d = Diagnostic::error(
ErrorCode::Redundant,
"clause can never match",
row.span,
);
d.severity = Severity::Warning;
sess.emit(d);
}
if covers(&row.body, truths) {
matrix.push(row.pats.clone())
}
}
let mut missing = vec![];
for _ in 0..3 {
let Some(p) =
useful(&matrix, &vec![Pat::Wild; types.len()], &types, cons)
else {
break;
};
missing.push(
p.iter()
.map(ToString::to_string)
.collect::<Vec<_>>()
.join(" "),
);
matrix.push(p)
}
if !missing.is_empty() {
let mut d = Diagnostic::error(
ErrorCode::NonExhaustive,
"non-exhaustive pattern match",
m.span,
);
d.severity = Severity::Warning;
d.notes.push(format!("missing: {}", missing.join("; ")));
sess.emit(d)
}
}
fn specialize(
matrix: &[Vec<Pat>],
head: &Pat,
arity: usize,
) -> Vec<Vec<Pat>> {
matrix
.iter()
.filter_map(|row| {
let mut fields = if wild(&row[0]) {
vec![Pat::Wild; arity]
} else if same(&row[0], head) {
match peel(&row[0]) {
Pat::Con(_, ps) => ps.clone(),
_ => vec![],
}
} else {
return None;
};
fields.extend_from_slice(&row[1..]);
Some(fields)
})
.collect()
}
}useful은 행렬과 함께 후보 벡터와 열 타입을 지니고 다닙니다. 이 패스의 드라이버는 유용한 증인(witness)을 반복해서 요청하고 진단을 기록합니다:
#![allow(unused)]
fn main() {
use crate::{
core::{ConDecl, Lit, Match, Pat, RowBody, Type},
diagnostics::{Diagnostic, ErrorCode, Severity},
session::Session,
};
fn peel(p: &Pat) -> &Pat {
if let Pat::As(_, p) = p { peel(p) } else { p }
}
fn wild(p: &Pat) -> bool {
matches!(peel(p), Pat::Wild | Pat::Var(_))
}
fn same(a: &Pat, b: &Pat) -> bool {
match (peel(a), peel(b)) {
(Pat::Con(a, _), Pat::Con(b, _)) => a == b,
(Pat::Lit(Lit::Double(a)), Pat::Lit(Lit::Double(b))) => {
f64::from_bits(*a) == f64::from_bits(*b)
}
(Pat::Lit(a), Pat::Lit(b)) => a == b,
_ => false,
}
}
fn specialize(
matrix: &[Vec<Pat>],
head: &Pat,
arity: usize,
) -> Vec<Vec<Pat>> {
matrix
.iter()
.filter_map(|row| {
let mut fields = if wild(&row[0]) {
vec![Pat::Wild; arity]
} else if same(&row[0], head) {
match peel(&row[0]) {
Pat::Con(_, ps) => ps.clone(),
_ => vec![],
}
} else {
return None;
};
fields.extend_from_slice(&row[1..]);
Some(fields)
})
.collect()
}
fn fields(head: &Pat, ty: &Type, cons: &[ConDecl]) -> Vec<Type> {
match peel(head) {
Pat::Con(id, _) => {
let c = &cons[id.index as usize];
let args = match ty {
Type::Con(_, args) => args.as_slice(),
_ => &[],
};
c.fields
.iter()
.map(|t| {
crate::elaborate::instantiate(t, &c.parameters, args)
})
.collect()
}
_ => vec![],
}
}
fn family(ty: &Type, cons: &[ConDecl]) -> Vec<Pat> {
cons.iter()
.filter(|c| match (&c.result, ty) {
(Type::Bool, Type::Bool) => true,
(Type::Con(a, _), Type::Con(b, _)) => a == b,
_ => false,
})
.map(|c| Pat::Con(c.id.clone(), vec![Pat::Wild; c.fields.len()]))
.collect()
}
/// Return a witness matched by the query but not by any covering row.
pub fn useful(
matrix: &[Vec<Pat>],
query: &[Pat],
types: &[Type],
cons: &[ConDecl],
) -> Option<Vec<Pat>> {
if query.is_empty() {
return matrix.is_empty().then(Vec::new);
}
let q = peel(&query[0]);
if !wild(q) {
let mut ts = fields(q, &types[0], cons);
let n = ts.len();
ts.extend_from_slice(&types[1..]);
let mut qs = match q {
Pat::Con(_, ps) => ps.clone(),
_ => vec![],
};
qs.extend_from_slice(&query[1..]);
let mut witness =
useful(&specialize(matrix, q, n), &qs, &ts, cons)?;
let children = witness.drain(..n).collect();
let p = match q {
Pat::Con(c, _) => Pat::Con(c.clone(), children),
_ => q.clone(),
};
witness.insert(0, p);
return Some(witness);
}
let heads = matrix
.iter()
.filter(|r| !wild(&r[0]))
.map(|r| peel(&r[0]).clone())
.collect::<Vec<_>>();
let all = family(&types[0], cons);
if !all.is_empty()
&& all.iter().all(|h| heads.iter().any(|p| same(h, p)))
{
for head in all {
let mut ts = fields(&head, &types[0], cons);
let n = ts.len();
ts.extend_from_slice(&types[1..]);
let mut qs = vec![Pat::Wild; n];
qs.extend_from_slice(&query[1..]);
if let Some(mut w) =
useful(&specialize(matrix, &head, n), &qs, &ts, cons)
{
let children = w.drain(..n).collect();
let Pat::Con(c, _) = head else { unreachable!() };
w.insert(0, Pat::Con(c, children));
return Some(w);
}
}
None
} else {
let defaults = matrix
.iter()
.filter(|r| wild(&r[0]))
.map(|r| r[1..].to_vec())
.collect::<Vec<_>>();
let mut witness =
useful(&defaults, &query[1..], &types[1..], cons)?;
let missing = all
.into_iter()
.find(|h| !heads.iter().any(|p| same(h, p)))
.unwrap_or_else(|| {
for n in 0..=heads.len() {
let p = match types[0] {
Type::Int => Pat::Lit(Lit::Int(n as i64)),
Type::Char => Pat::Lit(Lit::Char(
char::from_u32(97 + n as u32).unwrap_or('\0'),
)),
Type::String => {
Pat::Lit(Lit::String("x".repeat(n)))
}
Type::Double => {
Pat::Lit(Lit::Double((n as f64).to_bits()))
}
_ => return Pat::Wild,
};
if !heads.iter().any(|h| same(&p, h)) {
return p;
}
}
unreachable!()
});
witness.insert(0, missing);
Some(witness)
}
}
fn covers(
body: &RowBody,
truths: &std::collections::BTreeSet<u32>,
) -> bool {
match body {
RowBody::Plain(_) => true,
RowBody::Guarded(gs) => gs.iter().any(|(g, _)| match g {
crate::core::Expr::Con(c, _, _) => c.name == "True",
crate::core::Expr::Global(id) => truths.contains(&id.unique()),
_ => false,
}),
}
}
/// Warnings do not alter the decision tree; unmatched execution still fails at runtime.
pub fn warn(
sess: &mut Session,
m: &Match,
cons: &[ConDecl],
truths: &std::collections::BTreeSet<u32>,
) {
let types = m.scruts.iter().map(|i| i.ty.clone()).collect::<Vec<_>>();
let mut matrix = vec![];
for (index, row) in m.rows.iter().enumerate() {
if useful(&matrix, &row.pats, &types, cons).is_none()
&& !(index > 0 && m.rows[index - 1].span == row.span)
{
let mut d = Diagnostic::error(
ErrorCode::Redundant,
"clause can never match",
row.span,
);
d.severity = Severity::Warning;
sess.emit(d);
}
if covers(&row.body, truths) {
matrix.push(row.pats.clone())
}
}
let mut missing = vec![];
for _ in 0..3 {
let Some(p) =
useful(&matrix, &vec![Pat::Wild; types.len()], &types, cons)
else {
break;
};
missing.push(
p.iter()
.map(ToString::to_string)
.collect::<Vec<_>>()
.join(" "),
);
matrix.push(p)
}
if !missing.is_empty() {
let mut d = Diagnostic::error(
ErrorCode::NonExhaustive,
"non-exhaustive pattern match",
m.span,
);
d.severity = Severity::Warning;
d.notes.push(format!("missing: {}", missing.join("; ")));
sess.emit(d)
}
}
}생성된 do-패턴 폴백 행은 원래 위치의 span을 공유합니다. 진단 패스는 이렇게 합성된 인접 행에 대한 중복 경고는 억제하되, 소스 절에 대한 경고는 유지합니다. 경고 분석이 런타임 분기를 선택하지는 않습니다. 경고에서 생긴 실수가 평가를 조용히 바꾸어서는 안 됩니다.
이제 Core 린트는 평탄한 대안의 모양, 생성자 필드 타입, 전역적으로 고유한 바인더, 그리고 조인 인자의 타입과 항수를 검사합니다. 점프는 자신의 조인에 대해 꼬리 위치에 있어야 합니다. 꼬리가 아닌 하위 표현식에 들어가면 사용 가능한 바깥쪽 조인이 비워집니다. 하위 표현식은 자신만의 지역 조인을 세울 수 있습니다. Core 인터프리터는 평가 프레임과 반환 프레임을 명시적인 벡터에 보관합니다. 소스의 호출은 Rust를 재귀적으로 호출하는 대신 현재 표현식과 환경을 바꿉니다. 점프는 프레임을 자신의 어휘적 조인까지 되감고 그 본문으로 제어를 넘깁니다. 클로저는 안정적인 인덱스를 통해 코드를 빌려 오므로, 함수를 호출해도 구문 트리를 복제하지 않습니다. 생성자와 환경의 해제에도 작업 목록을 사용하므로, 긴 리스트를 해제할 때 스택이 넘치지 않습니다. 테스트는 꼬리가 아닌 재귀와 리스트 회수를 256 KiB 호스트 스택에서 실행합니다.
저장된 환경들은 불변 균형 트리를 공유합니다. 스코프를 포착할 때는 Rc 하나만 복사하고, 바인딩을 추가할 때는 탐색 경로만 복사합니다. env.rs는 이 갱신을 작업 벡터로 구현합니다. 이렇게 하면 인터프리터가 컨티뉴에이션을 저장할 때마다 커져 가는 스코프 전체가 복사되는 일을 막을 수 있습니다. 재귀 클로저는 머신이 소유한 그룹을 인덱스로 참조하므로, 호출은 참조 카운트 순환을 만들지 않고 그룹을 재사용합니다.
실행해 보기
$ cd crates/ch16_match
$ cargo run -q -- run tests/programs/match/guard-fallback.fun --lint
42
$ cargo run -q -- dump --pass=types tests/programs/match/guard-fallback.fun
main : IO ()
변환 자체를 보려면 같은 파일을 --pass=core로 덤프한 다음 --pass=match로 덤프하십시오. 전자는 중첩된 Match를 그대로 유지합니다. 후자는 평평한 Case, 우변 조인, 가드 실패 점프를 드러냅니다. 덤프에는 Prelude가 포함되므로, 결정 트리를 하나씩 살펴보려면 tests/matches.rs에 있는 Prelude 없는 작은 사례들이 유용합니다.
우리는 컴파일 전과 후에 모두 매치를 실행해 보는 방식으로 변환을 검사합니다. 커버리지는 별도의 검사가 필요합니다. 작은 불리언 패턴에 대해서는 가능한 모든 입력을 열거하고, 그렇게 직접 얻은 답을 유용성 알고리즘의 결과와 비교할 수 있습니다. 이는 잘못된 런타임 분기와는 다른 종류의 실수를 잡아냅니다.
연습 문제
- 기초. 예제의 결정 트리를 그리고, 실패한 가드가 향하는 곳을 표시하십시오.
- 중급. 생성자 절 앞에 와일드카드 절을 추가하고, 검사기를 실행하기 전에 중복 절 경고를 예측해 보십시오.
- 중급. 첫 번째 행이 변수로 시작하고 두 번째 패턴이 생성자인 2열 행렬을 특수화하십시오.
- 고급. 실험용 사본에서 열 선택 휴리스틱을 바꾸십시오. 변경 전후의 전체 실행 코퍼스는 그대로 유지하면서 트리 크기를 비교하십시오.
- 심화. 꼬리 위치가 아닌 식에서 바깥쪽 조인으로 점프하는 잘못된 Core를 만들어 보고, 그 때문에 버려지게 될 컨티뉴에이션이 무엇인지 설명하십시오.
더 읽을거리
- 결정 트리와 열 선택 휴리스틱 (Maranget 2008).
- 유용성, 완전성, 중복성 (Maranget 2007).
- 컴파일러 중간 표현으로서의 조인 포인트 (Maurer et al. 2017).
- 소스 패턴과 가드의 의미론 (Simon Marlow 2010).
같은 행렬 연산을 독립적인 Rust 구현으로 다룬 자료는 Patternkit을 참고하십시오. Fun은 검사 알고리즘이 이 장에서 계속 드러나도록 구현을 장 안에 둡니다.