Salsa의 작동 방식

이 장은 Niko Matsakis가 Salsa에 관한 이 영상에서 설명한 내용을 바탕으로 합니다. 더 자세히 알아보려면 역시 Niko Matsakis가 진행한 Salsa In More Depth를 시청해 보십시오.

2022년 11월 기준으로, Salsa는 (여러 가지 중에서도) rustc의 쿼리 시스템에서 영감을 받았지만 rustc에서 직접 사용되지는 않습니다. Salsa는 Rust 트레이트 시스템의 구현체인 [chalk]에서 _실제로_ 사용되고 있으며, Rust용 언어 서버 프로토콜의 공식 구현체인 [`rust-analyzer`]에서는 광범위하게 사용되지만, 이를 컴파일러에 통합하려는 중장기적인 구체적 계획은 없습니다.

Salsa란 무엇입니까?

Salsa는 점진적 재계산(incremental recomputation)을 위한 라이브러리입니다. 즉, 과거에 이미 수행된 계산을 재사용하여 이후 계산의 효율성을 높일 수 있게 해 줍니다.

Salsa의 목표는 다음과 같습니다:

• 이 기능을 자동화된 방식으로 제공하여, 과거 계산의 재사용이 라이브러리에 의해 자동으로 이루어지도록 합니다.
• 이를 “건전한(sound)”, 즉 “올바른” 방식으로 수행하여, 처음부터 계산한 것과 동일한 결과를 얻도록 합니다.

Salsa의 실제 모델은 훨씬 풍부하여, 다양한 종류의 입력과 여러 가지 다른 출력을 허용합니다. 예를 들어, Salsa를 IDE와 통합한다면 입력은 매니페스트(Cargo.toml, rust-toolchain.toml), 전체 소스 파일(foo.rs), 스니펫 등이 될 수 있습니다. 이러한 통합의 출력은 바이너리 실행 파일부터 린트, 타입(예를 들어 사용자가 특정 변수를 선택하고 그 타입을 확인하려는 경우), 자동 완성 등에 이르기까지 다양할 수 있습니다.

어떻게 작동합니까?

Salsa가 가장 먼저 해야 하는 일은 계산된 것이 아니라 입력으로 주어진 “기본 입력(base input)“을 식별하는 것입니다.

그다음 Salsa는 중간 단계의 “파생(derived)” 값도 식별해야 합니다. 파생 값은 라이브러리가 생성하는 것이지만, 각 파생 값마다 그 값을 계산하는 “순수(pure)” 함수가 존재합니다.

예를 들어, ast(x: Path) -> AST라는 함수가 있을 수 있습니다. 생성된 추상 구문 트리(AST)는 최종 값이 아니라, 라이브러리가 계산에 사용하는 중간 값입니다.

즉, 라이브러리로 계산을 수행하려고 하면 Salsa는 다양한 파생 값을 계산하고, 최종적으로 입력을 읽어 요청된 계산의 결과를 생성합니다.

계산 과정에서 Salsa는 어떤 입력에 접근했는지, 그리고 어떤 값이 파생되었는지를 추적합니다. 이 정보는 입력이 변경되었을 때 어떤 일이 일어날지, 즉 파생 값이 여전히 유효한지를 판단하는 데 사용됩니다.

그렇다고 해서 입력의 하류(downstream)에 있는 모든 계산을 반드시 검사한다는 뜻은 아니며, 그렇게 하면 비용이 많이 들 수 있습니다. Salsa는 변경되지 않은 계산을 찾을 때까지만 각 하류 계산을 검사하면 됩니다. 그 시점부터는 다른 파생 계산을 검사하지 않는데, 그 계산들은 변경될 필요가 없기 때문입니다.

이를 노드로 이루어진 그래프로 생각하면 이해하는 데 도움이 됩니다. 각 파생 값은 다른 값에 의존성을 가지며, 그 값들 자체도 기본 값이거나 파생 값일 수 있습니다. 기본 값에는 의존성이 없습니다.

I <- A <- C ...
          |
J <- B <--+

입력 I가 변경되면 파생 값 A가 변경될 수 있습니다. I, A, 또는 A나 I에서 파생된 어떤 값에도 의존하지 않는 파생 값 B는 변경 대상이 아닙니다. 따라서 Salsa는 과거에 B에 대해 수행한 계산을 다시 계산할 필요 없이 재사용할 수 있습니다.

계산이 조기에 종료될 수도 있습니다. 앞과 같은 그래프를 유지한 채, 입력 I는 어떤 식으로든 변경되었지만(입력 J는 변경되지 않았음) A를 다시 계산해 보니 A가 이전 계산과 달라지지 않았다고 가정해 봅시다. 이 경우 “조기 종료“가 일어납니다. C의 직접 입력인 A와 B가 모두 변경되지 않았으므로 C가 변경되어야 하는지 확인할 필요가 없기 때문입니다.

Salsa의 핵심 개념

쿼리

쿼리는 Salsa가 계산 과정에서 접근할 수 있는 어떤 값입니다. 각 쿼리는 여러 개의 키(0개부터 여러 개까지)를 가질 수 있으며, 함수와 마찬가지로 모든 쿼리에는 결과가 있습니다. 0-key 쿼리는 “입력” 쿼리라고 부릅니다.

데이터베이스

데이터베이스는 기본적으로 전체 계산의 컨텍스트이며, Salsa의 내부 상태, 각 쿼리의 모든 중간값, 그리고 계산에 필요할 수 있는 그 밖의 모든 것을 저장하기 위한 것입니다. 데이터베이스를 빌드하려면 먼저 라이브러리가 수행할 모든 쿼리를 알아야 하지만, 이 쿼리들이 같은 곳에 지정될 필요는 없습니다.

데이터베이스가 구성된 후에는 함수와 매우 비슷한 쿼리를 통해 데이터베이스에 접근할 수 있습니다. 각 쿼리의 결과는 데이터베이스에 저장되므로, 쿼리를 N번 호출하면 쿼리를 다시 계산하지 않고 N개의 복제된 결과를 반환합니다(재계산이 필요할 만큼 입력이 변경된 경우는 제외합니다).

각 입력 쿼리(0-key)마다 “set” 메서드가 생성되며, 사용자는 이를 통해 해당 쿼리의 출력을 변경하고 이전에 메모이제이션된 값이 무효화될 수 있도록 할 수 있습니다.

쿼리 그룹

쿼리 그룹은 하나의 단위로 함께 정의된 쿼리들의 집합입니다. 데이터베이스는 쿼리 그룹들을 결합하여 구성됩니다. 쿼리 그룹은 “Salsa 모듈“과 비슷합니다.

쿼리 그룹 안의 쿼리 집합은 단지 트레이트 안의 메서드 집합일 뿐입니다.

쿼리 그룹을 만들려면 특정 속성(#[salsa::query_group(...)])이 붙은 트레이트를 만들어야 합니다.

해당 속성에는 인자도 함께 제공해야 합니다. Salsa는 이 인자를 사용해 나중에 데이터베이스를 생성할 때 쓸 struct를 만듭니다.

입력 쿼리 그룹 예시:

/// This attribute will process this tree, produce this tree as output, and produce
/// a bunch of intermediate stuff that Salsa also uses. One of these things is a
/// "StorageStruct", whose name we have specified in the attribute.
///
/// This query group is a bunch of **input** queries, that do not rely on any
/// derived input.
#[salsa::query_group(InputsStorage)]
pub trait Inputs {
    /// This attribute (`#[salsa::input]`) indicates that this query is a base
    /// input, therefore `set_manifest` is going to be auto-generated
    #[salsa::input]
    fn manifest(&self) -> Manifest;

    #[salsa::input]
    fn source_text(&self, name: String) -> String;
}

파생 쿼리 그룹을 만들려면, 다음 예시와 같이 이 쿼리 그룹이 의존하는 다른 쿼리 그룹들을 슈퍼트레이트로 지정해야 합니다.

/// This query group is going to contain queries that depend on derived values.
/// A query group can access another query group's queries by specifying the
/// dependency as a supertrait. Query groups can be stacked as much as needed using
/// that pattern.
#[salsa::query_group(ParserStorage)]
pub trait Parser: Inputs {
    /// This query `ast` is not an input query, it's a derived query this means
    /// that a definition is necessary.
    fn ast(&self, name: String) -> String;
}

파생 쿼리를 만들 때는 해당 쿼리의 구현을 트레이트 바깥에 정의해야 합니다. 이 정의는 다른 키들 외에도 데이터베이스 매개변수를 impl Trait(또는 dyn Trait)로 받아야 하며, 여기서 트레이트는 해당 정의가 속한 쿼리 그룹입니다.

/// This is going to be the definition of the `ast` query in the `Parser` trait.
/// So, when the query `ast` is invoked, and it needs to be recomputed, Salsa is
/// going to call this function and it's going to give it the database as `impl
/// Parser`. The function doesn't need to be aware of all the queries of all the
/// query groups
fn ast(db: &impl Parser, name: String) -> String {
    //! Note, `impl Parser` is used here but `dyn Parser` works just as well
    /* code */
    ///By passing an `impl Parser`, this is allowed
    let source_text = db.input_file(name);
    /* do the actual parsing */
    return ast;
}

최종적으로 모든 쿼리 그룹을 정의한 후에는 struct를 선언하여 데이터베이스를 생성할 수 있습니다.

어떤 쿼리 그룹이 데이터베이스에 포함될지 지정하려면 attribute(#[salsa::database(...)])를 추가해야 합니다. 해당 attribute의 인자는 identifiers의 목록이며, 쿼리 그룹의 저장소를 지정합니다.

///This attribute specifies which query groups are going to be in the database
#[salsa::database(InputsStorage, ParserStorage)]
#[derive(Default)] //optional!
struct MyDatabase {
    ///You also need this one field
    runtime : salsa::Runtime<MyDatabase>,
}
///And this trait has to be implemented
impl salsa::Database for MyDatabase {
    fn salsa_runtime(&self) -> &salsa::Runtime<MyDatabase> {
        &self.runtime
    }
}

사용 예시:

fn main() {
    let db = MyDatabase::default();
    db.set_manifest(...);
    db.set_source_text(...);
    loop {
        db.ast(...); //will reuse results
        db.set_source_text(...);
    }
}