개요 - Salsa

Salsa 프로그램을 구성하는 요소들을 간단히 소개합니다. 더 자세히 보고 싶다면, 전체 프로젝트를 처음부터 끝까지 만들어 보는 튜토리얼을 확인하세요.

Goal of Salsa

Salsa의 목표는 효율적인 증분 재계산(incremental recomputation) 을 지원하는 것입니다. 예를 들어 Salsa는 rust-analyzer에서 사용되며, 타이핑하는 동안 프로그램을 빠르게 다시 컴파일하는 데 도움을 줍니다.

Salsa 프로그램의 기본 아이디어는 다음과 같습니다:

rust
#![allow(unused)]
fn main() {
let mut input = ...;
loop {
    let output = your_program(&input);
    modify(&mut input);
}
}

처음에는 어떤 값을 가진 입력(input)으로 시작합니다. 프로그램을 호출해 결과를 얻습니다. 시간이 지난 뒤 입력을 수정하고 프로그램을 다시 호출합니다. 우리의 목표는 첫 번째 호출에서 얻은 결과 일부를 재사용하여 두 번째 호출을 더 빠르게 만드는 것입니다.

물론 실제로는 입력이 여러 개일 수 있고, “프로그램”은 그 입력들 위에 정의된 여러 메서드와 함수일 수 있습니다. 하지만 이 그림은 몇 가지 중요한 개념을 전달합니다:

• Salsa는 “증분 계산”(함수 your_program)을 입력을 정의하는 바깥쪽 루프(outer loop)로부터 분리합니다.
• Salsa는 your_program을 정의하기 위한 도구를 제공합니다.
• Salsa는 your_program이 입력들에 대한 순수하게 결정적인(deterministic) 함수라고 가정합니다. 그렇지 않으면 이 전체 설정은 의미가 없습니다.
• 입력의 변경(mutation)은 항상 your_program 밖에서, 이 마스터 루프의 일부로 일어납니다.

Database

프로그램을 실행할 때마다 Salsa는 각 계산(computation)의 값을 데이터베이스(database) 에 기억합니다. 입력이 바뀌면 이 데이터베이스를 조회하여 재사용할 수 있는 값을 찾습니다. 데이터베이스는 또한 인터닝(interning: 값을 정규화된(canonical) 형태로 만들어 복사해 다닐 수 있고, 동등성 비교를 저렴하게 할 수 있게 함)과 기타 편리한 Salsa 기능들을 구현하는 데도 사용됩니다.

Inputs

모든 Salsa 프로그램은 입력(input) 에서 시작합니다. 입력은 프로그램의 시작점을 정의하는 특수한 구조체입니다. 프로그램의 나머지 모든 것은 궁극적으로 이 입력들의 결정적인 함수입니다.

예를 들어 컴파일러에서는 디스크에 있는 파일의 내용을 정의하는 입력이 있을 수 있습니다:

rust
#![allow(unused)]
fn main() {
#[salsa::input]
pub struct ProgramFile {
    pub path: PathBuf,
    pub contents: String,
}
}

입력은 new 메서드로 생성합니다. 입력 필드 값들은 데이터베이스에 저장되므로, 데이터베이스에 대한 & 참조도 함께 넘깁니다:

rust
#![allow(unused)]
fn main() {
let file: ProgramFile = ProgramFile::new(
    &db,
    PathBuf::from("some_path.txt"),
    String::from("fn foo() { }"),
);
}

새 입력을 만드는 것은 데이터베이스의 기존 추적 데이터(tracked data)에 영향을 줄 수 없으므로, 가변 접근은 필요하지 않습니다.

Salsa structs are just integers

#[salsa::input] 매크로가 생성하는 ProgramFile 구조체는 실제로 데이터를 저장하지 않습니다. 단지 newtype으로 감싼 정수 id일 뿐입니다:

rust
#![allow(unused)]
fn main() {
// Generated by the `#[salsa::input]` macro:
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct ProgramFile(salsa::Id);
}

즉 ProgramFile을 갖고 있으면 어디든 쉽게 복사해서 들고 다닐 수 있습니다. 하지만 필드 값을 실제로 읽으려면 데이터베이스와 getter 메서드를 사용해야 합니다.

Reading fields and returns(ref)

입력의 필드 값은 getter 메서드로 접근할 수 있습니다. 이 작업은 필드를 읽기만 하므로 데이터베이스에 대한 & 참조만 필요합니다:

rust
#![allow(unused)]
fn main() {
let contents: String = file.contents(&db);
}

접근자를 호출하면 데이터베이스에서 값을 클론(clone)해 옵니다. 때로는 이것이 원치 않는 동작일 수 있으므로, #[returns(ref)]로 필드를 주석 처리하면 데이터베이스 내부 값을 참조로 반환하도록 할 수 있습니다:

rust
#![allow(unused)]
fn main() {
#[salsa::input]
pub struct ProgramFile {
    pub path: PathBuf,
    #[returns(ref)]
    pub contents: String,
}
}

이제 file.contents(&db)는 &String을 반환합니다.

전체 구조체에 접근하려면 data 메서드도 사용할 수 있습니다:

rust
#![allow(unused)]
fn main() {
file.data(&db)
}

Writing input fields

마지막으로 setter 메서드를 사용해 입력 필드 값을 수정할 수도 있습니다. 이는 입력을 변경하고, 그로부터 파생된 데이터를 무효화할 수 있으므로 setter는 데이터베이스에 대한 &mut 참조를 받습니다:

rust
#![allow(unused)]
fn main() {
file.set_contents(&mut db).to(String::from("fn foo() { /* add a comment */ }"));
}

setter 메서드 set_contents는 “빌더(builder)”를 반환한다는 점에 유의하세요. 이를 통해 내구성(durability) 같은 고급 개념과 기타 설정을 지정할 수 있습니다.

Tracked functions

입력을 정의했다면 다음으로 추적 함수(tracked function) 를 정의합니다:

rust
#![allow(unused)]
fn main() {
#[salsa::tracked]
fn parse_file(db: &dyn crate::Db, file: ProgramFile) -> Ast {
    let contents: &str = file.contents(db);
    ...
}
}

추적 함수를 호출하면, Salsa는 그 함수가 어떤 입력을 읽었는지(이 예에서는 file.contents(db))를 추적합니다. 또한 반환값(여기서는 Ast)을 메모이즈(memoize)합니다. 추적 함수를 두 번 호출하면 Salsa는 입력이 바뀌었는지 검사하고, 바뀌지 않았다면 메모이즈된 값을 반환할 수 있습니다. Salsa가 언제 추적 함수를 다시 실행해야 하는지 결정하는 알고리즘은 red-green 알고리즘이라 하며, “Salsa”라는 이름도 여기서 유래했습니다.

추적 함수는 특정한 구조를 따라야 합니다:

• 첫 번째 인자로 데이터베이스에 대한 & 참조를 받아야 합니다.
  • 이 참조는 &이므로, 추적 함수 실행 중에는 입력을 수정할 수 없습니다!
• 두 번째 인자로 “Salsa 구조체”를 받아야 합니다. 이 예에서는 입력 구조체이지만, 곧 다른 종류의 Salsa 구조체들도 설명합니다.
• 추가 인자를 더 받을 수 는 있지만, 받지 않는 것이 더 빠르고 더 좋습니다.

추적 함수는 클론 가능한 어떤 타입이든 반환할 수 있습니다. 값이 캐시될 때 데이터베이스에서 결과를 클론해 꺼내야 하므로 clone이 필요합니다. 또한 #[returns(ref)]로 주석 처리해 데이터베이스 내부 값을 참조로 반환하도록 할 수도 있습니다(예를 들어 parse_file이 그렇게 주석 처리되어 있다면 호출자는 &Ast를 받게 됩니다).

Tracked structs

추적 구조체(tracked struct) 는 계산 과정 중에 만들어지는 중간 구조체입니다. 입력과 마찬가지로 필드는 데이터베이스 안에 저장되고, 구조체 자체는 id를 감싼 것에 불과합니다. 하지만 입력과 달리, 추적 구조체는 추적 함수 내부에서만 생성할 수 있으며, 한 번 생성된 뒤에는(적어도 다음 리비전 전까지는) 필드가 절대 바뀌지 않습니다. 필드를 읽기 위한 getter는 제공되지만 setter는 없습니다. 예:

rust
#![allow(unused)]
fn main() {
#[salsa::tracked]
struct Ast<'db> {
    #[returns(ref)]
    top_level_items: Vec<Item>,
}
}

입력과 마찬가지로 새 값은 Ast::new를 호출해 생성합니다. 추적 구조체의 new 함수는 데이터베이스에 대한 & 참조만 필요합니다:

rust
#![allow(unused)]
fn main() {
#[salsa::tracked]
fn parse_file(db: &dyn crate::Db, file: ProgramFile) -> Ast {
    let contents: &str = file.contents(db);
    let parser = Parser::new(contents);
    let mut top_level_items = vec![];
    while let Some(item) = parser.parse_top_level_item() {
        top_level_items.push(item);
    }
    Ast::new(db, top_level_items) // <-- Ast 생성!
}
}

#[id] fields

입력이 바뀌어 추적 함수가 재실행될 때, 새 실행에서 생성된 추적 구조체들은 이전 실행에서 생성된 것들과 매칭되고, 각 필드 값이 비교됩니다. 필드 값이 바뀌지 않았다면 그 필드만 읽는 다른 추적 함수들은 재실행되지 않습니다.

기본적으로 추적 구조체는 생성된 “순서”로 매칭됩니다. 예를 들어 이전 실행에서 parse_file이 만든 첫 번째 Ast는 새 실행에서 parse_file이 만든 첫 번째 Ast와 매칭됩니다. 이 예에서는 parse_file이 Ast를 하나만 만들기 때문에 매우 잘 동작합니다. 하지만 어떤 경우에는 그렇지 않을 수 있습니다. 예를 들어 파일 안의 아이템들을 위한 추적 구조체가 있다고 가정해 봅시다:

rust
#![allow(unused)]
fn main() {
#[salsa::tracked]
struct Item {
    name: Word, // Word는 곧 정의합니다!
    ...
}
}

파서가 먼저 이름이 foo인 Item을 만들고, 나중에 이름이 bar인 두 번째 Item을 만든다고 합시다. 그 후 사용자가 입력을 바꿔 함수들의 순서를 바꿨습니다. 아이템 개수는 같지만 생성 순서가 뒤집혔기 때문에, 단순한 알고리즘은 이전 실행의 foo 구조체를 새 실행의 bar 구조체와 매칭해 버립니다. Salsa 입장에서는 foo가 bar로 이름이 바뀌고 bar가 foo로 이름이 바뀐 것처럼 보입니다. 결과는 여전히 올바르지만, 단지 재정렬된 것임을 알았다면 피할 수 있었던 재계산을 더 많이 하게 될 수 있습니다.

이를 해결하기 위해 추적 구조체의 필드를 #[id]로 표시할 수 있습니다. 그러면 이 필드들이 실행 간 구조체 인스턴스를 “매칭”하는 데 사용됩니다:

rust
#![allow(unused)]
fn main() {
#[salsa::tracked]
struct Item {
    #[id]
    name: Word, // Word는 곧 정의합니다!
    ...
}
}

Specify the result of tracked functions for particular structs

때로는 추적 함수를 정의하되, 특정 구조체에 대해서는 그 값을 특별히 지정하고 싶을 때가 있습니다. 예를 들어 어떤 함수의 표현(representation)을 계산하는 기본 방식은 AST를 읽는 것이지만, 언어에 내장(built-in) 함수들이 있어서 결과를 하드코딩하고 싶을 수 있습니다. 또는 추적 구조체를 생성한 뒤에 초기화되는 필드를 흉내 내는 데도 사용할 수 있습니다.

이런 용도를 위해, 추적 함수에는 specify 메서드를 사용할 수 있습니다. 이 메서드를 활성화하려면, 해당 함수에 specify 플래그를 추가하여 값이 때때로 외부에서 지정될 수 있음을 사용자에게 알립니다.

rust
#![allow(unused)]
fn main() {
#[salsa::tracked(specify)] // <-- specify 플래그 필요
fn representation(db: &dyn crate::Db, item: Item) -> Representation {
    // 기본적으로 사용자의 입력 AST를 읽음
    let ast = ast(db, item);
    // ...
}

fn create_builtin_item(db: &dyn crate::Db) -> Item {
    let i = Item::new(db, ...);
    let r = hardcoded_representation();
    representation::specify(db, i, r); // <-- 메서드 사용!
    i
}
}

값 지정(specifying)은 데이터베이스 인자를 제외하고 단 하나의 추적 구조체만 인자로 받는 추적 함수에 대해서만 가능합니다.

Interned structs

Salsa 구조체의 마지막 종류는 인터닝 구조체(interned struct) 입니다. 인터닝 구조체는 빠른 동등성 비교에 유용합니다. 문자열이나 기타 원시 값(primitive value)을 표현하는 데 흔히 사용됩니다.

예를 들어 대부분의 컴파일러는 사용자 식별자(identifier)를 나타내는 타입을 정의합니다:

rust
#![allow(unused)]
fn main() {
#[salsa::interned]
struct Word {
    #[returns(ref)]
    pub text: String,
}
}

입력/추적 구조체와 마찬가지로 Word 구조체 자체는 newtype 정수일 뿐이며, 실제 데이터는 데이터베이스에 저장됩니다.

입력/추적 구조체와 마찬가지로 new로 새 인터닝 구조체를 만들 수 있습니다:

rust
#![allow(unused)]
fn main() {
let w1 = Word::new(db, "foo".to_string());
let w2 = Word::new(db, "bar".to_string());
let w3 = Word::new(db, "foo".to_string());
}

같은 필드 값을 가진 인터닝 구조체를 두 번 만들면, 동일한 정수 id가 반환됨이 보장됩니다. 따라서 여기서는 assert_eq!(w1, w3)는 참이고 assert_ne!(w1, w2)는 참입니다.

인터닝 구조체의 필드는 word.text(db) 같은 getter로 접근할 수 있습니다. 이 getter는 #[returns(ref)] 주석을 존중합니다. 추적 구조체와 마찬가지로, 인터닝 구조체의 필드는 불변(immutable)입니다.

Accumulators

마지막 Salsa 개념은 누산기(accumulator) 입니다. 누산기는 함수의 주 반환값과는 별개로, 오류나 기타 “부수 채널(side channel)” 정보를 보고하는 방법입니다.

누산기를 만들려면 어떤 타입을 누산기 로 선언합니다:

rust
#![allow(unused)]
fn main() {
#[salsa::accumulator]
pub struct Diagnostics(String);
}

이는 String 같은 어떤 타입의 newtype이어야 합니다. 이제 추적 함수 실행 중에 값을 푸시할 수 있습니다:

rust
#![allow(unused)]
fn main() {
Diagnostics::push(db, "some_string".to_string())
}

그리고 나중에(실행 밖에서), 특정 추적 함수가 누적한 진단(diagnostics) 집합을 요청할 수 있습니다. 예를 들어 타입 체커가 있고, 타입 체크 중에 진단을 보고한다고 해봅시다:

rust
#![allow(unused)]
fn main() {
#[salsa::tracked]
fn type_check(db: &dyn Db, item: Item) {
    // ...
    Diagnostics::push(db, "some error message".to_string())
    // ...
}
}

그렇다면 이후에 연관된 accumulated 함수를 호출하여 푸시된 모든 String 값을 얻을 수 있습니다:

rust
#![allow(unused)]
fn main() {
let v: Vec<String> = type_check::accumulated::<Diagnostics>(db);
}