IR 정의하기: 다양한 “salsa struct”

IR 정의하기: 다양한 “salsa struct”

parser를 정의하기 전에, calc 프로그램에서 사용할 중간 표현(IR, intermediate representation)을 먼저 정의해야 합니다. 기본 구조에서는 Statement와 Expression 같은 “의사(pseudo)-Rust” 구조를 정의했는데, 이제 이를 실제로 정의해 보겠습니다.

“Salsa struct”

일반적인 Rust 타입 외에도, 우리는 다양한 Salsa struct를 사용합니다. Salsa struct는 다음 Salsa 애노테이션 중 하나로 주석 처리된(struct에 부착된) 구조체를 말합니다:

• #[salsa::input]: 계산의 “기본 입력(base inputs)”을 지정합니다.
• #[salsa::tracked]: 계산 과정에서 생성되는 중간 값을 지정합니다.
• #[salsa::interned]: 동등성 비교가 쉬운 작은 값을 지정합니다.

모든 Salsa struct는 자신의 필드 값을 Salsa 데이터베이스에 저장합니다. 이를 통해, 필드 값이 언제 바뀌었는지 추적하여 어떤 작업을 다시 실행해야 하는지 판단할 수 있습니다.

위 Salsa 속성 중 하나를 구조체에 붙이면, Salsa는 해당 구조체를 데이터베이스에 연결하기 위한 여러 코드를 자동 생성합니다.

입력(input) 구조체

먼저 입력(input) 을 정의합니다. 모든 Salsa 프로그램에는 나머지 계산을 구동하는 기본 입력들이 있습니다. 프로그램의 나머지 부분은 그 기본 입력들에 대한 어떤 결정적(deterministic) 함수여야 하며, 입력이 바뀌면 그 함수의 새로운 결과를 효율적으로 다시 계산할 수 있어야 합니다.

입력은 #[salsa::input] 애노테이션이 붙은 Rust 구조체로 정의합니다:

rust
#[salsa::input(debug)]
pub struct SourceProgram {
    #[returns(ref)]
    pub text: String,
}

우리 컴파일러에서는 입력이 하나뿐입니다. 문자열 필드 text를 가진 SourceProgram입니다.

데이터는 데이터베이스에 저장된다

겉보기에는 다른 Rust 구조체처럼 선언하지만, Salsa struct는 구현 방식이 꽤 다릅니다. 필드 값은 Salsa 데이터베이스에 저장되고, 구조체 인스턴스는 그 값을 참조만 합니다. 따라서 구조체 인스턴스는 (어떤 필드를 포함하든) Copy가 됩니다. 구조체 인스턴스를 만들고 필드에 접근하는 것은 new 같은 메서드와 getter/setter를 호출하는 방식으로 이뤄집니다.

#[salsa::input]의 경우, 구조체는 0이 아닌 정수인 salsa::Id를 담습니다. 따라서 생성되는 SourceProgram 구조체는 대략 다음처럼 생겼습니다:

rust
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct SourceProgram(salsa::Id);

또한 데이터베이스 안에 SourceProgram을 만들 수 있는 new 메서드도 생성됩니다. input의 경우에는 &db 참조와 각 필드 값이 필요합니다:

rust
let source = SourceProgram::new(&db, "print 11 + 11".to_string());

필드 값은 source.text(&db)로 읽을 수 있고, source.set_text(&mut db, "print 11 * 2".to_string())로 설정할 수 있습니다.

데이터베이스 리비전(revision)

함수가 데이터베이스에 대한 &mut 참조를 받는다면, 이는 개요에서 설명한 것처럼 프로그램의 증분화(incrementalized)된 부분 “바깥”에서만 호출할 수 있다는 뜻입니다. 입력 필드 값을 바꾸면 데이터베이스의 ‘리비전 카운터(revision counter)’가 증가하여, 이제 일부 입력이 달라졌음을 나타냅니다. 우리가 데이터베이스의 “리비전”을 말할 때는, 입력 값 변경 사이에 존재하는 데이터베이스 상태를 의미합니다.

파싱된 프로그램 표현하기

다음으로 tracked struct를 정의합니다. input이 계산의 시작 을 나타낸다면, tracked struct는 계산 중에 생성되는 중간 값을 나타냅니다.

이 경우 파서는 앞에서 본 SourceProgram을 입력으로 받아, 완전히 파싱된 프로그램을 표현하는 Program을 반환합니다:

rust
#[salsa::tracked(debug)]
pub struct Program<'db> {
    #[tracked]
    #[returns(ref)]
    pub statements: Vec<Statement<'db>>,
}

input과 마찬가지로, tracked struct의 필드도 데이터베이스에 저장됩니다. 하지만 input과 달리 이 필드들은 불변(immutable)입니다(“set”할 수 없음). 그리고 Salsa는 리비전 사이에서 이 필드들을 비교하여 값이 바뀌었는지 판단합니다. 예를 들어 입력을 파싱한 결과가 동일한 Program이라면(입력 변경이 단지 끝 공백(trailing whitespace) 정도였을 수도 있겠죠), 이후 계산 단계는 다시 실행할 필요가 없습니다. (tracked struct가 재사용(reuse)에서 어떤 역할을 하는지는 IR의 다음 부분들에서 더 다룹니다.)

필드가 불변이라는 점을 제외하면, tracked struct를 다루는 API는 input과 꽤 비슷합니다:

• new로 새 값을 생성할 수 있습니다. 예: Program::new(&db, some_statements)
• input과 동일하게 getter로 필드를 읽습니다(예: my_func.statements(db)로 statements 필드 읽기).
  • 여기서는 필드가 #[returns(ref)]로 태그되어 있으므로, getter는 벡터를 복제하지 않고 &Vec<Statement>를 반환합니다.

'db 라이프타임

input과 달리, tracked struct는 'db 라이프타임을 갖습니다. 이 라이프타임은 그것을 생성할 때 사용된 &db에 묶여 있으며, 구조체를 사용하는 동안에는 데이터베이스가 불변임을 보장합니다. 즉, salsa::Input의 값을 변경할 수 없습니다.

또한 'db 라이프타임 덕분에 tracked struct는( salsa::input 구조체에서 쓰는 숫자 id 대신) 포인터로 구현될 수 있습니다. 사용자 입장에서 크게 체감되는 차이는 없지만, tracked struct에서 필드에 접근하는—매우 흔한—연산을 최적화할 수 있게 됩니다.

함수 표현하기

각 함수를 표현하기 위해 tracked struct를 하나 더 사용합니다. Function 구조체는 파서가 사용자가 정의한 각 함수를 나타내기 위해 생성합니다:

rust
#[salsa::tracked(debug)]
pub struct Function<'db> {
    pub name: FunctionId<'db>,

    name_span: Span<'db>,

    #[tracked]
    #[returns(ref)]
    pub args: Vec<VariableId<'db>>,

    #[tracked]
    #[returns(ref)]
    pub body: Expression<'db>,
}

예를 들어 f라는 Function 인스턴스가 있다고 하면, 사용자가 f의 정의를 바꾸면서 f.body 필드가 바뀔 수 있습니다. 이는 f.body에 의존하던 코드 부분은 다시 실행해야 하지만, 다른 함수의 본문에만 의존하던 코드 부분은 다시 실행할 필요가 없음을 의미합니다.

필드가 불변이라는 점을 제외하면, tracked struct를 다루는 API는 input과 꽤 비슷합니다:

• new로 새 값을 생성할 수 있습니다. 예: Function::new(&db, some_name, some_args, some_body)
• input과 동일하게 getter로 필드를 읽습니다(예: my_func.args(db)로 args 필드 읽기).

id 필드

리비전 간 재사용을 더 잘 하기 위해, 특히 재정렬(reorder)이 발생할 때, 어떤 엔티티의 일부 필드를 #[id]로 표시할 수 있습니다. 보통 엔티티의 “이름”을 나타내는 필드에 사용합니다. 이는 두 리비전 R1과 R2에서 같은 이름을 가진 두 함수가 생성되었다면, 그들은 같은 엔티티를 가리킨다는 뜻이므로, 다른 필드들을 동등성 비교하여 무엇을 다시 실행할지 결정할 수 있습니다. #[id]는 최적화이며 정합성(correctness)에는 영향을 주지 않습니다. 자세한 내용은 레퍼런스의 알고리즘 페이지를 참고하세요.

인터닝(interned) 구조체

마지막 종류의 Salsa struct는 interned struct 입니다. input과 tracked struct처럼 interned struct의 데이터도 데이터베이스에 저장됩니다. 하지만 이들 구조체와 달리, 같은 데이터를 두 번 intern하면 같은 정수를 다시 받게 됩니다.

인터닝의 고전적인 사용처는 함수 이름과 변수 이름 같은 작은 문자열입니다. 이런 이름들을 String으로 들고 다니면 복제(clone)해야 해서 귀찮고 비효율적입니다. 또한 문자열 비교로 동등성을 판정하는 것도 비효율적입니다. 따라서 문자열을 저장하는 단일 필드를 가진 FunctionId와 VariableId라는 두 interned struct를 정의합니다:

rust
#[salsa::interned(debug)]
pub struct VariableId<'db> {
    #[returns(ref)]
    pub text: String,
}

#[salsa::interned(debug)]
pub struct FunctionId<'db> {
    #[returns(ref)]
    pub text: String,
}

예를 들어 FunctionId::new(&db, "my_string".to_string())를 호출하면, 단순히 정수에 newtype을 씌운 FunctionId를 얻습니다. 그런데 동일한 new 호출을 다시 하면 같은 정수를 돌려받습니다:

rust
let f1 = FunctionId::new(&db, "my_string".to_string());
let f2 = FunctionId::new(&db, "my_string".to_string());
assert_eq!(f1, f2);

interned 값도 'db 라이프타임을 가진다

tracked struct처럼, interned 값도 salsa 리비전 사이에서 사용되지 못하도록 막는 'db 라이프타임을 가집니다. 또한 내부적으로 포인터를 사용해 구현할 수 있게 하여, 필드 접근을 효율적으로 만듭니다. interned 값은 단일 리비전 내에서는 일관됨이 보장됩니다. 리비전 간에는 값이 지워지거나, 재할당되거나, 재배치될 수 있습니다. 하지만 'db 라이프타임 때문에 interned 값이 사용 중일 때는 입력을 변경(즉 새로운 리비전 생성)할 수 없으므로, 일반적으로 사용자가 이를 관찰할 방법은 없습니다.

표현식과 문장

표현식과 문장에는 특별한 “Salsa struct”를 사용하지 않습니다:

rust
#[derive(Eq, PartialEq, Debug, Hash, salsa::Update)]
pub struct Statement<'db> {
    pub span: Span<'db>,

    pub data: StatementData<'db>,
}

impl<'db> Statement<'db> {
    pub fn new(span: Span<'db>, data: StatementData<'db>) -> Self {
        Statement { span, data }
    }
}

#[derive(Eq, PartialEq, Debug, Hash, salsa::Update)]
pub enum StatementData<'db> {
    /// `fn <name>(<args>) = <body>`를 정의
    Function(Function<'db>),
    /// `print <expr>`를 정의
    Print(Expression<'db>),
}

#[derive(Eq, PartialEq, Debug, Hash, salsa::Update)]
pub struct Expression<'db> {
    pub span: Span<'db>,

    pub data: ExpressionData<'db>,
}

impl<'db> Expression<'db> {
    pub fn new(span: Span<'db>, data: ExpressionData<'db>) -> Self {
        Expression { span, data }
    }
}

#[derive(Eq, PartialEq, Debug, Hash, salsa::Update)]
pub enum ExpressionData<'db> {
    Op(Box<Expression<'db>>, Op, Box<Expression<'db>>),
    Number(OrderedFloat<f64>),
    Variable(VariableId<'db>),
    Call(FunctionId<'db>, Vec<Expression<'db>>),
}

#[derive(Eq, PartialEq, Copy, Clone, Hash, Debug)]
pub enum Op {
    Add,
    Subtract,
    Multiply,
    Divide,
}

문장과 표현식이 tracked가 아니므로, 이는 함수 단위의 증분 재사용만 노린다는 뜻입니다. 즉 함수 본문 안에서 무엇이든 바뀌면, 함수 본문 전체를 더럽혀졌다고(dirty) 보고, 그것에 의존하던 모든 것을 다시 실행합니다. 보통은 이렇게 “적당히 거친(coarse)” 경계를 두는 것이 합리적입니다.

이 설정 방식의 한 가지 단점은, 각 구조체에 위치(position)를 인라인으로 넣었다는 점입니다.