URL: https://thunderseethe.dev/posts/desugar-base/

구체 구문과 추상 구문의 관계 디슈거링하기

이전에는 마지못해 일부 구문을 Concrete Syntax Tree(CST)로 파싱했다. 그 늪을 능숙하게 피해 나왔으니, 이제 다음 패스인 디슈거링(desugaring)으로 나아갈 수 있다. 디슈거링은 문법 설탕(syntax sugar)을 제거하고 CST를 Abstract Syntax Tree(AST)로 사상한다. CST에는 |나 = 같은 잡동사니가 잔뜩 남아 있다. 이런 것들은 처음 소스 파일에서 머리와 꼬리를 구분하기 위해 중요했고, 진단(diagnostics)을 보고할 때도 필요하겠지만, 컴파일러의 나머지 부분은 그런 시시한 일에는 별 관심이 없다. 디슈거링은 이런 모든 구문을 벗겨내고 중요한 것에만 집중하게 해 주어서, 이후 컴파일러 패스들의 인지 부하를 줄여 준다.

하지만… 정말 꼭 해야 하나? 꽤 귀찮아 보인다. 이후 패스들이 그냥 남는 구문을 처리하게 하면 안 될까? 보통은 “왜 안 되는지”를 설명하기 위한 도입처럼 들리지만, 사실 그냥… 해도 된다. 실제로 Swift가 정확히 그렇게 한다.

Swift는 CST를 파싱하고, 그들의 “AST”는 CST의 필드 중 의미적으로 중요한 부분의 부분집합일 뿐이다. 이는 완전히 타당한 전략이다. 어쩌면 _추천_할 수도 있다. 물론, 이후의 모든 컴파일러 패스를 이미 명시적인 AST를 기준으로 작성해 두지 않았다면 말이다. 하지만 누가 그런 짓을 하겠어, 하하. 걱정 마라. 별도의 AST를 써야 하는 진짜 이유도 있다.

우리 문법에는 let 표현식이 있지만, AST에는 그것이 전혀 없다. 문법 설탕은 CST와 AST를 분리하게 만드는 흔한 동기다. rust-analyzer를 보면 Swift와 비슷한 전략을 쓴다. 그들은 CST에서 의미적으로 흥미로운 것들을 다루기 위한 다양한 헬퍼를 노출한다. 그럼에도 불구하고, 그들은 HIR이라는 별도의 트리를 또 만든다.

Rust 역시 표면 구문(surface syntax)을 많이 디슈거링해 없앤다. 이런 변환을 수용하려면 새로운 트리를 생성해야 한다. 의미적으로 흥미로운 것들을 위한 메서드만 제공하는 것으로는 충분하지 않다. 트리의 구조 자체를 근본적으로 바꿔야 한다.

트리를 바꾸는 동안, 우리가 어디서 왔는지(원본 CST에서) 기억해야 한다. AST를 다시 CST에 매핑할 수 있어야 한다. 이는 에러 리포팅뿐 아니라 쿼리(query)에도 중요하다. 예를 들어 “정의로 이동(go to definition)”을 하려면, 커서가 가리키는 AST 노드를 결정한 뒤 그것을 사용해 해당 정의가 어디인지 찾아야 한다.

디슈거링은 새로운 AST 그리고 AST 노드에서 CST 노드로의 매핑을 만든다. 파싱과 마찬가지로 디슈거링도 탄력적(resilient)일 것이다. AST와 매핑과 함께 오류 목록도 생성한다.

대부분 디슈거링은 간단하다. CST를 순회하면서 의미 있는 조각들을 꺼내 새로 구성 중인 AST에 저장하면 된다. 편리하게도, 우리의 구문 노드들은 AST 노드에 직접 대응한다. 마치… 그렇게 설계한 것처럼.

let 표현식은 예외로, 좀 더 주의가 필요하다. AST로 직접 매핑할 수 없다. 노드들의 트리로 표현하고, 그것들을 다시 CST로 매핑해야 한다.

CST를 헤집고 다니기

파싱 동안에는 CST를 구축하는 데에만 관심이 있었고 CST를 어떻게 소비(consume)할지는 거의 고려하지 않았다. 디슈거링에서는 달라진다. 이제는 CST를 어떻게 순회할지뿐 아니라 CST를 어떻게 저장할지도 고민해야 한다. 출력 중 하나가 CST와 AST 간의 매핑임을 기억하자. 이런 매핑을 만들려면 특정 CST 노드를 참조할 수 있는 방법이 필요하다.

우리 CST는 rowan이 제공하며, 다행히 운이 좋다. rowan은 CST뿐 아니라 그것을 순회하는 방법도 제공한다. 순회는 SyntaxNode로 수행한다. 파싱 과정에서는 전혀 만나지 않았던 타입이다.

파싱된 GreenNode로부터 SyntaxNode를 구성할 수 있으며, 그 결과 여러 메서드를 사용할 수 있다. 우리가 가장 자주 사용할 메서드는 first_child_by_kind다. first_child_by_kind는 Fn(Syntax) -> bool를 받아, 해당 함수가 true를 반환하는 첫 번째 노드를 돌려준다. 이 술어(predicate)를 통해 트리에서 특정 종류의 노드(SyntaxKind::LetBinder, Sytnax::Expr 등)를 골라낼 수 있다.

중요한 점은 first_child_by_kind가 오직 syntax node만 반환한다는 것이다. 즉 토큰(token)—CST의 리프 노드—는 반환할 수 없다. 이는 rowan의 실수가 아니라 의도적인 설계다. 토큰을 찾고 싶다면 first_child_or_token_by_kind를 쓰면 된다.

SyntaxNode의 자식들을 헤집을 때 우리는 노드만 신경 쓴다. 토큰은 Whitespace나 Equal 같은 구문적 잡음일 뿐이고 AST를 만들 때는 무관하다. rowan은 이를 알고 곧장 핵심으로 갈 수 있게 해 준다.

이 때문에 파싱 중에 주목할 만한 Identifier 토큰을 노드로 감싸 두었다. FunBinder와 LetBinder는 (약간의 Whitespace를 제외하면) 항상 하나의 Identifier를 감싸지만, first_child_by_kind를 통해 그 식별자를 찾을 수 있게 된다.

성공을 위한 준비

다른 패스들과 마찬가지로, 디슈거링은 트리를 순회하는 재귀 메서드들의 집합이다. 우리가 순회하는 트리들이 워낙 많다 보니, 컴파일을 끝낼 때쯤이면 숲 전체를 훑은 셈일 것이다. 또한 다른 패스들과 마찬가지로, 재귀 메서드들 간에 공유하는 상태를 Desugar 구조체에 담는다:

rust
struct Desugar {
  node_id: u32,
  root: GreenNode,
  ast_to_cst: HashMap<NodeId, SyntaxNodeHandle>,
  errors: HashMap<SyntaxNodePtr<Lang>, DesugarError>,
}

Desugar는 Ast 노드들을 유일하게 식별할 책임이 있다. node_id는 AST 노드를 생성하면서 다음으로 사용할 수 있는 ID를 추적한다. lowering의 VarSupply처럼, 노드를 만들 때마다 이 카운터를 증가시킨다.

root는 파싱에서 나온 CST의 루트 노드다. 디슈거링이 지금 한창 순회하고 있는 바로 그 CST다. GreenNode는 복제 비용이 저렴하므로, 여기저기 두 사본이 떠다녀도 걱정할 필요가 없다.

ast_to_cst는 Ast 노드들을 그것을 생성한 CST 노드로 다시 매핑한다. 이 매핑은 에러 리포팅의 중심이 된다. AST 노드에서의 에러를 소스 파일의 스팬(span)으로 바꾸는 데 쓰이기 때문이다. 여기서 SyntaxNode가 아니라 SyntaxNodeHandle이라는 것을 저장한다는 점이 의아할 수 있다.

SyntaxNode는 내부적으로 포인터다. 성능에는 좋지만 장기 저장에는 좋지 않다. 포인터를 안전하게 저장하는 방법을 고민하는 대신, SyntaxNode가 가리키던 트리 내 위치로 돌아갈 수 있는 인덱스를 저장한다.

Note

이름이 암시하듯, 여기서 설명하는 것은 핸들 패턴(handle pattern)이다.

이는 &T 대신 (Vec<T>, usize)를 저장하는 것으로 생각할 수 있다. SyntaxNodeHandle을 열어 보면 이를 확인할 수 있다:

rust
struct SyntaxNodeHandle {
  root: GreenNode,
  ptr: SyntaxNodePtr<Lang>,
}

SyntaxNodePtr는 rowan에서 온다. 이름과 달리 정의를 보면 포인터가 없다:

rust
struct SyntaxNodePtr<L: Language> {
  // 우리에게는 Syntax
  kind: L::Kind,
  // 소스 텍스트 내 스팬
  range: TextRange,
}

노드의 스팬과 종류로부터 root 내에서 해당 노드를 찾아 필요할 때마다 SyntaxNode를 만들 수 있다. 순회 중에는 빠르므로 SyntaxNode로 작업하지만, 저장해야 할 때는 SyntaxNodeHandle로 변환한다. 다시 순회할 때는 핸들을 SyntaxNode로 되돌려 중단했던 지점에서 이어서 진행한다.

error 역시 오류가 발생한 위치를 가리키기 위해 SyntaxNode를 저장해야 한다. 오류에 대해서는 순회를 재개하는 데 크게 관심이 없으므로 SyntaxNodePtr를 저장하는 것으로 충분하다.

케이크에서 아이싱 걷어내기

상태를 정리했으니, 이제 진입점 desugar로 넘어가자:

rust
fn desugar(root: GreenNode) -> DesugarOut {
  todo!()
}

파싱으로부터 GreenNode를 받아 DesugarOut을 만든다:

rust
struct DesugarOut {
  ast: Ast<String>,
  ast_to_cst: HashMap<NodeId, SyntaxNodeHandle>,
  errors: HashMap<SyntaxNodePtr<Lang>, DesugarError>,
}

DesugarOut은 디슈거링에서 생성하는 세 가지를 담는다. 탄력성(resilience) 덕분에 우리는 어떤 형태로든 항상 출력들을 만들어 낸다. 본문은 짧다:

rust
fn desugar(root: GreenNode) -> DesugarOut {
  let mut desugar = Desugar::new(root.clone());
  let ast = desugar.desugar_program(SyntaxNode::new_root(root));
  DesugarOut {
    ast,
    ast_to_cst: desugar.ast_to_cst,
    errors: desugar.errors,
  }
}

Desugar를 만들고, 프로그램의 Ast를 디슈거링한 뒤, 출력들을 조립한다. 이보다 간단할 수는 없다.

프로그램부터 위에서 아래로

파싱에서 프로그램은 단지 하나의 표현식이었다. desugar_program에서도 여전히 그렇다:

rust
fn desugar_program(&mut self, cst: SyntaxNode<Lang>) -> Ast<String> {
  let Some(expr) = cst.first_child_by_kind(&|kind| kind == Syntax::Expr) else {
    // 파서가 누락된 노드에 대해 이미 에러를 냈다고 가정하고 여기서는 Hole을 반환한다.
    return self.hole(&cst, DesugarError::MissingSyntax(Syntax::Expr));
  };

  self.desugar_expr(expr)
}

CST에서 첫 번째 Expr 노드를 찾는다. 많아야 하나만 존재하므로 첫 번째가 항상 정답이다. 표현식을 찾지 못하면 프로그램이 유효하지 않다고 가정하고 hole을 반환한다. hole은 Hole AST 노드를 만들고 그것을 CST 노드에 매핑한다:

rust
fn hole(&mut self, node: &SyntaxNode<Lang>, kind: DesugarError) -> Ast<String> {
  let ptr = SyntaxNodePtr::new(node);
  self.errors.insert(ptr, kind);

  let id = self.next_id();
  self.insert_node(id, ptr);
  Ast::Hole(id, "_".to_string())
}

Hole은 우리의 탄력성 전략의 일부로, 이전에 타입 추론에서 보았다. 첫 번째로 잘못된 AST에서 실패하는 대신, 그것을 Hole로 취급하고 가능한 한 많은 AST를 복구하려 한다. Hole을 만들 때마다 무슨 일이 잘못됐는지 알 수 있도록 오류를 붙인다.

표현식 디슈거링

Expr를 찾으면 desugar_expr로 넘긴다:

rust
fn desugar_expr(
  &mut self, 
  expr: SyntaxNode<Lang>
) -> Ast<String> {
  todo!()
}

표현식 문법은 “0개 이상의 let 바인딩 + 하나의 애플리케이션(application)”이다:

• Expr
  • Let
    • …
  • Let
    • …
  • App
    • …

완벽한 세상이라면 이 레이아웃을 그대로 소비하고 즐겁게 지나가면 된다. 하지만 우리가 보고 있는 표현식이 잘못됐을 가능성도 고려해야 한다. 바인딩 목록을 유지하며 표현식의 자식 SyntaxNode들을 순회한다:

rust
let mut binds = vec![];
// Let 안에 등장하는 토큰은 공백뿐이며, 여기서는 기꺼이 건너뛴다.
for child in expr.children() {
  match child.kind() {
    Syntax::Let => match self.desugar_let(child.clone()) {
      Ok((var, arg)) => binds.push((var, arg, child)),
      Err(error) => {
        let hole = self.hole(&child, error);
        return self.build_locals(binds, hole);
      }
    },
    _ => {
      let body = self.desugar_app(child);
      return self.build_locals(binds, body);
    }
  }
}

이 루프는 세 가지 방식 중 하나로 끝난다:

1. desugar_let에서 에러가 발생한다
2. Let이 아닌 자식을 만난다
3. 자식 노드를 다 소진한다

첫 번째 종료는 let 바인딩이 유효하지 않았다는 뜻이며, 표현식의 나머지를 hole로 취급한다. 그래도 이미 모아 둔 바인딩들이 있을 수 있으므로, build_locals로 let 표현식을 만들 것이다.

두 번째 경우가 “해피 패스”다. Let이 아닌 구문을 보면 그것이 애플리케이션이라고 가정하고 desugar_app으로 넘긴 다음, 그 결과를 build_locals에 전달한다. 애플리케이션은 괄호로 감싼 표현식, 함수, 정수, 애플리케이션 등 무엇이든 될 수 있다. 여기서 그 모든 것을 검사할 필요는 없다. 잘못된 구문을 desugar_app에 넘기면, 그쪽이 hole을 돌려줄 것이다.

마지막으로 세 번째 경우는 루프가 끝까지 돈 것이다. Let 자식만 있고 본문이 없거나, 애초에 자식이 없는 경우다. 어느 쪽이든 동일하게 처리하며 hole을 만든다:

rust
let node = &expr.last_child().unwrap_or(expr);
self.hole(node, DesugarError::ExprMissingBody)

이 루프는 children이 syntax node만 순회한다는 점에 의존한다. let 바인딩 사이에는 Whitespace 토큰이 있을 수 있고(없어도 되긴 하지만), 그런 토큰이 보이면 와일드카드 케이스가 트리거되어 루프가 일찍 종료될 수 있다. 하지만 Whitespace는 토큰이므로 children은 이를 건너뛰어, 표현식의 마지막 애플리케이션에 도달하기 전까지는 Let 구문만 보게 된다고 가정할 수 있다.

let 바인딩 디슈거링

desugar_let은 완전한 let 표현식을 디슈거링하지 않는다. 이는 CST가 let 바인딩 let <var> = <expr>;만 인코딩하기 때문이다. 파싱에서 보았듯 Let 구문 노드는 다음 모양이다:

• Let
  • LetKw
  • LetBinder
    • …
  • Equal
  • Expr
    • …
  • Semicolon

그래서 desugar_let은 Ast를 만들어 내지 않는다. 그러기엔 필요한 구문이 부족하다. 대신 식별자와 그 정의로 이루어진 쌍을 만들고, desugar_expr이 그것들을 완전한 Ast로 바꾸도록 맡긴다. Let 노드의 자식들에서 이 쌍을 추출한다:

rust
fn desugar_let(
  &mut self, 
  bind: SyntaxNode<Lang>
) -> Result<(String, Ast<String>), DesugarError> {
  let mut children = bind.children();

  let binder = children
    .next()
    .filter(|var| var.kind() == Syntax::LetBinder)
    .and_then(|var| var.first_child_or_token_by_kind(&|kind| kind == Syntax::Identifier))
    .ok_or(DesugarError::LetMissingBinding)?;

  let ast = match children.next()
      .filter(|expr| expr.kind() == Syntax::Expr) {
    Some(expr) => self.desugar_expr(expr),
    None => self.hole(&bind, DesugarError::LetMissingExpr),
  };

  Ok((binder.to_string(), ast))
}

let 바인딩에는 노드가 두 개뿐이라고 가정한다(토큰이 몇 개인지는 신경 쓸 필요가 없다). 첫 번째는 식별자를 담고 있는 LetBinder다. LetBinder를 열어 내부의 Identifier 토큰을 드러낸 다음 텍스트를 가져온다. 바인딩이 누락되면 즉시 에러를 낸다.

다음은 let 바인딩의 정의이며, Expr여야 한다. 이를 desugar_expr에 넘기고 그 결과를 그대로 사용한다. 찾지 못하면 hole을 만들고 표현식이 빠졌음을 사용자에게 알린다. 다음으로 애플리케이션 디슈거링을… 사실…

대충 감이 오지?

디슈거링을 맛봤다. 이제부터는 여기서 충분히 외삽할 수 있을 거라 믿는다. 각 구문 조각마다 우리는:

1. CST에서 흥미로운 노드로 이동하고
2. 그 텍스트를 추출하고
3. AST에 넣는다

이 단계들 중 하나라도 실패하면, 만들고 있던 AST를 Hole로 바꾸되 가능한 한 작은 AST만 대체하려 한다. let의 정의를 hole로 바꾸는 편이 전체 let을 hole로 바꾸는 것보다 낫다. AST 노드를 만들 때마다 유일한 ID를 부여하고(머리를 쓰다듬어 주고), CST로의 매핑에 등록한 뒤 다음으로 보낸다. 모니터 해상도에 따라 “영광스러운 고해상도”로 전체 코드를 보고 싶다면 전체 코드를 확인하라. 위에서 이미 다룬 개념을 반복하는 대신, 다음으로 흥미로운 부분—let 표현식 디슈거링—으로 넘어가자.

문법 설탕 제거하기

build_locals는 어떤 의미에서 마법이 일어나는 곳이다. 다른 헬퍼들은 하나의 구문 구성 요소를 하나의 AST 구성 요소로 바꾼다. 하지만 여기서는 let 표현식을 여러 AST 노드로 바꾼다. 1:1 매핑이 깨졌으니 질문이 생긴다: 여러 AST 노드를 하나의 CST 노드로 어떻게 매핑할까?

let 표현식은 애플리케이션 안에 중첩된 함수로 변환된다. let x = 1; incr x를 쓸 때마다 (|x| incr x) 1로 쓸 수도 있다. 우리는 let 표현식을 Ast::Fun과 Ast::App으로 표현할 것이다.

그런데 Ast::Fun의 스팬은 무엇인가? 트리 변환은 파괴적(destructive)이다. 우리는 일부 정보를 잃었다.

소스에서 함수를 나타내는 연속적인 스팬이 없다. let ∣x = 1; incr x∣처럼 함수의 모든 요소를 포함하도록 감싸면 애플리케이션의 일부도 포함된다. 애플리케이션도 비슷한 곤란을 겪지만, let 전체 표현식을 스팬으로 본다고 손쉽게 넘길 수 있다.

함수의 “완벽한” 스팬을 고르는 대신, 스팬이 왜 필요한지 생각해 보자. 가장 중요한 용도는 진단 위치다. 그 다음은 사용자 상호작용을 위해 AST 노드를 식별하는 것이다. 예를 들어 let 변수의 타입을 알고 싶다면, 스팬으로부터 AST에서 어떤 함수 매개변수의 타입을 가져와야 하는지 알아낸다.

실제로 함수 전체에 대한 스팬은 많은 진단에서 필요하지 않다. 함수 본문에서 에러가 발생하면, 함수 본문 자체가 독립적인 스팬에 매핑되는 표현식이다.

함수 _전체_에 대한 스팬이 필요하지는 않다. 함수 매개변수에만 스팬을 부여하면, 함수 본문은 알아서 처리된다. 그러면 과제는 훨씬 간단해진다: let ∣x∣ = 1; incr x. 이렇게 해서 함수 매개변수에 스팬을 할당했다. 그리고 구현을 보면 실제로 우리가 정확히 그렇게 한다는 걸 알 수 있다:

rust
fn build_locals(
  &mut self,
  binds: Vec<(String, Ast<String>, SyntaxNode<Lang>)>,
  body: Ast<String>
) -> Ast<String> {
  binds.into_iter().rfold(body, |body, (var, arg, child)| {
    let app_id = self.next_id();
    let fun_id = self.next_id();
    if let Some(let_binder) =
      child.first_child_by_kind(&|kind| kind == Syntax::LetBinder) {
      self.insert_node(fun_id, SyntaxNodePtr::new(&let_binder));
    }
    self.insert_node(app_id, SyntaxNodePtr::new(&child));
    Ast::app(app_id, Ast::fun(fun_id, var, body), arg)
  })
}

let 디슈거링을 하면서 부차적인 작업도 하나 수행한다. 즉, let 바인딩들을 올바르게 중첩시키는 것이다. body는 가장 안쪽 let 바인딩의 본문 표현식이며, 이는 binds의 마지막 요소가 된다. binds를 역순으로 걷고, 이전 바인딩들을 바탕으로 새 let 표현식을 구성해 나가다가 첫 바인딩에 도달한다. 첫 바인딩이 가장 바깥 let 표현식이 되고, 그 본문에 나머지 모든 바인딩이 포함된다.

let이 실제로 어떻게 동작하는지 보자

디슈거링의 감을 잡기 위해 예제를 통해 살펴보자. 다음 구문에서 시작한다:

text
let one = |s||z| s z;
let add = |m||n||s||z| m s (n s z);
add one one

처치 인코딩 팬들은 채팅에 출석. 내게 묻는다면 덧셈을 하기엔 완벽히 좋은 방법이다. 더 많은 기능을 추가하려는 이유를 잘 모르겠다. 이 구문은 CST로 파싱되며, 여기서는 요약만 하자:

• Program
  • Expr
    • Let
      • LetBinder “one”
      • Expr …
    • Let
      • LetBinder “add”
      • Expr …
    • App
      • App
        • Var “add”
        • Var “one”
      • Var “one”

이 CST로부터 Ast를 디슈거링한다. 간결함을 위해 let 정의의 본문은 생략하겠다. 여기서는 let 표현식이 어떻게 변환되는지 감만 잡고 싶다:

rust
use Ast::*;
App(
  NodeId(25),
  Fun(
    NodeId(26),
    "one", 
    App(
      NodeId(23),
      Fun(
        NodeId(24),
        "add",
        App(
          NodeId(22),
          App(
            NodeId(20),
            Var(NodeId(18), "add"), 
            Var(NodeId(19), "one")),
          Var(NodeId(21), "one")
        )
      ),
      Fun(NodeId(17), "m", Fun(NodeId(16), "n", 
        Fun(NodeId(15), "s", Fun(NodeId(14), "z", ...))))
    )
  ),
  Fun(NodeId(4), "s",
    Fun(NodeId(3), "z", ...))
)

휴, 손으로 직접 쓰니 컴퓨터가 해 주는 일을 새삼 고맙게 느낀다. 이제 let은 문법 설탕이므로, 다음처럼 써도 동일한 Ast에 도달할 수 있다:

text
(|one| 
  (|add| add one one) 
  (|m||n||s||z| m s (n s z))
) (|s||z| s z)

검증은 여러분에게 맡기겠지만, 이는 같은 Ast로 변환된다. 나는 어느 쪽 문법을 더 쓰고 싶은지 알고 있다. 하지만 let 표현식이 _필요하지 않다_는 것을 보는 건 통찰이 있다.

Note

이는 우리가 타입 시스템을 설계하며 내린 선택 덕분에 가능한 일이다. Haskell에서는 let 바인딩이 함수 매개변수와 다른 타이핑을 허용하므로 이런 변환이 유효하지 않다. 우리는 let 표현식에 어떤 특별 취급도 하지 않기 때문에 디슈거링할 수 있다.

항상 그렇듯, 디슈거링 패스의 전체 코드는 making a language 저장소에서 찾을 수 있다. 디슈거 예제에서 한 가지가 계속 마음에 걸린다. 디슈거된 Ast는 변수에 String을 쓰지만, 타입 추론에서는 Var를 쓴다. 타입 추론에 Ast를 넘기기 전에 한 번 더 패스가 필요하다: 이름 해석(name resolution).