Borrow Checker

notJoon·2023년 7월 9일

언어 구현

목록 보기

2/2

개요

구현에 앞서 러스트에서 이 검사기의 역할과 이게 어떤 식으로 동작하는지 알아보겠습니다. 러스트에서 검사기는 메모리 안정성을 확보하는데 중요한 역할을 합니다. 이때 변수의 빌림 규칙(borrowing rule)을 강제로 적용하는데, 러스트에서의 규칙은 다음과 같습니다.

동시에 가변, 불변 참조를 가질 수 없음: 한 스코프 내부에서 어떤 변수가 가변 참조 되고 있는 동안에는 그 변수에 대한 불변 참조를 만들 수 없고, 반대의 경우도 마찬가지입니다.
한 번에 하나의 가변 참조만 존재할 수 있음: 어떤 변수에 대한 가변 참조가 존재하는 동안에는 그 변수를 동시에 다른 곳에서 참조하거나 수정하는 것을 방지하는 역할을 합니다.
불변 참조는 동시에 여러 개 존재할 수 있음: 가변 참조와 다르게 불변 참조는 해당 변수를 읽는 작업에서 사용합니다. 읽는 작업은 수정과 다르게 데이터의 변형이 일어나지 않기 때문에 한 스코프 내에서 여러 개의 불변 참조를 생성해도 문제가 없습니다. 어찌보면 RwLock과 비슷한 동작을 한다고 생각하면 됩니다.

이 검사기는 컴파일 시간에 프로그램을 분석해 이 규칙들을 지키는지 검사하는 역할을 합니다. 러스트의 검사기는 소유권 시스템과 라이프타임 개념을 사용해 빌림 규칙을 적용합니다.

참고로 소유권 시스템은 변수가 오직 하나의 소유자(owner)를 가지며, 소유자가 스코프를 벗어나면 변수가 메모리에서 해제되는 것을 보장하고, 라이프타임은 변수의 참조가 유효한 범위를 지정해 변수를 추적합니다.

논리 명제 표현식과 추론 규칙

들어가기에 앞서 코드를 읽기 쉽게 축약할 수 있는 논리 명제 표현식을 소개하겠습니다. 이 논리 표현식을 이용하면 복잡한 복합 명제를 단순하게 표현할 수 있습니다.

기본 연산자는 다음과 같습니다.

부정( $\neg$ ): 명제 P의 부정은 " $P$ 가 아님"을 의미
논리곱( $\land$ , and): 두 명제 $P$ 와 $Q$ 의 논리곱은 " $P$ 와 $Q$ 모두 참"
논리합( $\lor$ , or): 두 명제 $P$ 와 $Q$ 의 논리합은 "P 또는 $Q$ 중 적어도 하나는 참”
조건부( $\rightarrow$ ): 두 명제 $P$ 와 $Q$ 에 대한 $P \rightarrow Q$ 는 " $P$ 가 참이면 $Q$ 도 참"
동치( $\leftrightarrow$ ): 두 명제 $P$ 와 $Q$ 에 대한 $P \leftrightarrow Q$ 는 " $P$ 와 $Q$ 는 모두 참이거나, 모두 거짓"

추론 규칙은 아래의 표기법을 이용해 표기할 수 있습니다.

\frac{전제}{결론}

이 표기법은 주어진 전제에서 어떤 결과가 나오는지를 나타냅니다.

표기법에서 가로선 위의 내용은 "전제"를, 가로선 아래의 내용은 "결론"을 의미합니다. 즉, "전제가 참이면 결론도 참이다"라는 추론 규칙을 표현합니다.

예를 들어, modus ponens(전건 긍정, MP)을 이 표기법을 이용해 표현하면 다음과 같습니다.

\frac{P \space \space P \rightarrow Q}{Q}

이 추론 규칙은 " $P$ 가 참이고 $P$ 가 참일때 $Q$ 도 참이면, $Q$ 는 참이다"라는 논리적 추론을 나타냅니다.

이 명제 표현식과 추론 규칙을 적절히 사용한다면 복잡한 규칙도 간결하게 표현할 수 있습니다. 그래서 이후에 코드 설명에서 좀 길다 싶으면 이 표기법들을 이용할 것입니다.

Borrow System

이제 대여 검사기를 구현해보겠습니다. 러스트에는 이런 방식으로 구문을 분석하고 상태를 지정합니다.

borrow checker flowchart

단계를 나눈다면 코드 파싱(parsing)과 검사 단계로 나눌 수 있는데 파싱은 말 그대로 코드를 읽고 AST(추상 구문 트리)를 생성하는 단계입니다.

이후 검사기는 생성된 AST를 순회하면서 모든 변수와 그 참조 관계에 어떤 상태를 지정합니다. 이 상태는 참조 관계와 여부를 나타내며 각각 불변/가변 대여, 다중 대여, 대여 없음 4가지 경우로 나뉩니다. 이후 부여된 각 상태에 맞게 변수와 참조를 처리하면 끝입니다. 간단하죠?

하지만 여기서 작성한 검사기는 여러가지 복잡한 사정으로 인해 가변 참조는 다루지 않습니다. 그래서 나오는 모든 참조는 모두 불변 참조입니다. 더 간단하죠?

인스턴스 생성과 Borrow State

이제 검사기 구현을 해보겠습니다. 시작이 반이니 검사기 인스턴스와 BorrowState를 먼저 정의해야 합니다.

검사기의 구조는 변수의 borrow 정보를 저장할 공간과 스코프 정보만 저장하면 되기 때문에 저는 HashMap을 사용했습니다. 이렇게 하면 borrows는 스코프 단위로 각 변수와 표현식의 대여 관계를 저장하는 컨테이너의 역할을 합니다.

pub struct BorrowChecker<'a> {
    borrows: Vec<HashMap<&'a str, BorrowState>>,
}

해시 맵의 키와 값은 각각 변수 이름과 borrow 정보를 나타냅니다. 다음으로, 상태를 나타내는 BorrowState를 정의해보겠습니다.

#[derive(Debug, PartialEq)]
pub enum BorrowState {
    Uninitialized,
    Initialized,
    Borrowed,
    ImmutBorrowed,
}

위 그림과 다르게 4가지 상태로 정의했습니다. Uninitialized와 Initialized는 각각 변수가 현재 인식되었는지를 확인하는 플래그입니다. 그리고 Borrowed와 ImmutBorrowed는 borrow의 상태와 유형을 나타냅니다. 예를 들어, Borrowed 표시가 없으면 이는 참조되지 않은 일반 변수를 의미하며, ImmutBorrowed는 불변 참조를 나타내는 플래그입니다.

이제 기본 설정은 끝났으니 검사기의 인스턴스를 생성해보겠습니다. 이 인스턴스는 BorrowChecker::new 함수를 통해 생성됩니다.

impl BorrowChecker {
	pub fn new() -> Self {
			BorrowChecker {
            borrows: vec![HashMap::new()],
      }
	 }
}

Checking Statement

검사기는 생성된 AST를 순회하면서 변수의 borrow 유형을 검사하고 상태를 부여하고 각 상태에 맞는 메소드를 호출하는 방식으로 작동합니다.

check and chech_statement methods

상태를 할당하기 전에 먼저 참조(reference)와 관련된 AST를 보기전에 미리 짚고 넘어가야 되는 사항이 있습니다. Expression::Reference를 정의할 때 String이 아니라 Box<Expression>을 사용했어야 했다는 점입니다. 작성 당시 제작 목표는 최소한의 동작만을 하도록 하는 것이였고, 참조는 변수 이름만 처리하도록 하는게 목표였습니다. 그래서 이후 참조된 함수를 호출(ex. let a = &foo(a, &b))하는 것은 불가능하다는 점을 미리 알립니다.

// ast.rs

#[derive(Debug, PartialEq)]
pub enum Statement {
    VariableDecl {
        name: String,
        value: Option<Expression>,
        is_borrowed: bool,
    },

		// ...
}

#[derive(Debug, PartialEq)]
pub enum Expression {
    // ...
    Reference(String),
}

이후 생성된 AST는 BorrowChecker::check_statement와 BorrowChecker::check_variable_decl을 통해 처리됩니다. BorrowChecker::check_statement는 주어진 구문이 Statement::VariableDecl인지 확인하고, check_variable_decl 함수를 호출합니다. 이런 방식으로 Statement::VariableDecl을 처리할 수 있습니다.

type BorrowResult = Result<(), BorrowError>;

impl BorrowChecker {
	fn check_statement(&mut self, stmt: &'a Statement) -> BorrowResult {
	    match stmt {
	        Statement::VariableDecl { ... } => self.check_variable_decl(name, value, *is_borrowed),
	        _ => unimplemented!("나머지는 이후에 다룸."),
	    }
	 }

	fn check_variable_decl(
        &mut self,
        name: &'a str,
        value: &'a Option<Expression>,
        is_borrowed: bool,
    ) -> BorrowResult {
        match (is_borrowed, value) {
			// 1
            (true, Some(Expression::Reference(ref ident))) => {
                if let Some(state) = self.get_borrow(ident) {
                    match state {
                        BorrowState::Borrowed | BorrowState::Uninitialized => /* 에러 */
                        _ => {}
                    }
                    self.insert_borrow(name, BorrowState::ImmutBorrowed);

                    return Ok(());
                }

                Err(BorrowError::VariableNotDefined(ident.into()))
            }
			// 2
            (false, Some(expr)) => {
                self.check_expression(expr)?;
                self.insert_borrow(name, BorrowState::Initialized);

                Ok(())
            }
			// 3, 4
           (true, _) | (false, None) => /* 에러 처리 */
        }
    }
}

BorrowChecker::check_variable_decl 함수는 변수의 정보를 토대로 BorrowState를 결정합니다. 변수의 대여 여부와 값에 따라 패턴 매칭을 수행하고, 그 결과에 따라 상태를 지정합니다. 이 과정은 변수의 대여 상태를 추적하고 대여 규칙을 잘 지키고 있는지 확인하는 단계입니다.

패턴 매칭 부분에서 각각 어떤 역할을 하는지 간단히 살펴보겠습니다. 번호는 코드에 주석으로 매긴 조건 번호입니다.

변수가 참조되었고, 값이 참조되는 경우입니다. 이 경우 이미 대여된 변수에 대한 참조를 생성하려는지 확인합니다.
변수가 참조되지 않았지만, 값이 있는 경우를 나타냅니다. 일반 변수 선언을 나타내기 때문에 대여 상태를 Initialize로 설정합니다.
변수가 참조되었지만, 값은 참조되지 않은 케이스를 나타냅니다. 존재하지 않는 변수를 대여하려는 상황을 나타내기 때문에 에러를 반환합니다.
변수가 대여되지 않았고, 값도 없는 케이스입니다. 초기값 없이 변수를 선언하려는 시도를 나타내기 때문에 에러를 반환합니다.

명제를 추출하면 위 케이스들을 간결하게 표현할 수 있습니다. 해당 함수의 명제는 다음과 같습니다.

$P$ : stmt가 Statement::VariableDecl인 경우
$Q$ : is_borrowed가 true인 경우
$R$ : 어떤 변수 선언에서 value가 참조인 경우
$S$ : 선언된 변수의 상태가 BorrowState::Borrowed 또는 BorrowState::Uninitialized인 경우
$T$ : ident에 해당하는 state가 존재함.
$U$ : 변수의 값이 존재함.
$V$ : 변수가 대여되지 않음
$E$ : 에러

먼저, BorrowChecker::check_statement를 위 명제들로 표현해보겠습니다.

P \rightarrow CheckVariableDecl

이 표현식은 단순히 검사하고 있는 구문의 AST에 Statement::VariableDecl이 포함되어 있다면 특정 함수를 호출하라는 조건을 나타냅니다.

또한 패턴 매칭의 각 케이스는 아래와 같이 표현할 수 있습니다. 이 케이스들을 모두 check_variable_decl 함수 내부에서 동작하기 때문에 $P$ 가 항상 참인 경우에만 성립합니다. 그래서 표기의 단순화를 위해 $P$ 는 생략했습니다.

$Q \land R \land T \land \lnot S \rightarrow$ $ImmutBorrow$
$\lnot Q \land (\lnot R \land U )\rightarrow Initialized$
$Q \land \lnot R \rightarrow E$
$\neg U \land V \rightarrow E$

지금까지의 내용을 요약하면 다음과 같습니다

BorrowChecker는 AST를 순회하면서 변수의 대여 유형을 확인하고 상태를 부여하는 함
검사기는 check_statement와 check_variable_decl 함수를 통해 변수의 대여 유형과 상태를 부여함
check_statement는 Statement::VariableDecl인 구문을 확인
check_Variable_decl 함수는 변수의 정보를 기반으로 BorrowState를 결정

스코프 관리

그럼 대여의 범위는 어떻게 관리해야 할까요? 개발자가 직접 처리하는 방법도 있지만, RAII(Resouce Acquisition is Initialization)와 같이 스코프를 벗어나면 자동으로 해제하도록 하는게 더 편리하고 안전할 것 같아서, 여기서는 이 방법을 사용하겠습니다. 물론 러스트도 이 방법을 사용하기도 해서 그렇습니다.

RAII는 스코프의 진입 시점에 리소스를 할당하고, 스코프를 벗어나는 시점에서 자동으로 해제하는 방식입니다. 이를 구현하는BorrowChecker::allocate_scope 함수를 살펴보겠습니다.

BorrowChecker::allocate_scope 함수는 제네릭 함수로 FnOnce를 이용하여 각 값 마다 필요한 처리를 하고 개별 스코프에 처리된 값들을 할당합니다.

impl BorrowChecker {
	fn allocate_scope<F, T>(&mut self, action: F) -> T
    where
        F: FnOnce(&mut Self) -> T,
    {
		// 스코프 할당
        self.borrows.push(HashMap::new());

        // 각 스코프에서 구문에 맞는 처리를 함
        let result = action(self);

        // 스코프 해제
        self.borrows.pop();

        result
    }
}

이 함수는 새로운 스코프를 할당하고(push), 스코프 범위를 벗어나면 대여한 변수들을 해제(pop)합니다. 즉, RAII의 개념을 구현하고, 스코프의 범위에 따라 자동으로 할당과 해제를 관리합니다,

이 함수와 함께 사용하는 함수로는 check_function_def나 check 등, 어떤 스코프 범위를 지정해야 하는 구문을 처리하는 함수들이 있습니다(여기서 다루진않지만 if-else와 같은 조건문도 해당함). 이 함수들은 allocate_scope 함수를 통해 스코프를 관리합니다.

impl BorrowChecker {
	fn check_statement(&mut self, stmt: &'a Statement) -> BorrowResult {
      match stmt {
          Statement::FunctionDef { name, args, body } => {
              self.allocate_scope(|s| s.check_function_def(name, args, body))
          }
          Statement::Scope(stmts) => self.allocate_scope(|s| s.check(stmts)),
          _ => unimplemented!("지금은 일단 생략")
      }
	 }
}

call stack

이러한 방식은 stack discipline 방식을 반영합니다. 스택에는 각 구문(ex. 함수)에 대한 프레임이 있으며, 함수 호출과 반환, 블록 진입과 탈출 등 프로그램의 실행 흐름에 따라 메모리를 자동으로 관리합니다. 후입선출(LIFO) 구조를 가지고 있기 때문에 가장 마지막에 추가된 항목이 가장 먼저 제거되는 특성이 있습니다.

스택의 특성 덕분에 RAII를 사용할 수 있고, 이 RAII 덕분에 명시적으로 메모리를 관리할 필요 없이 자동으로 스코프를 관리할 수 있습니다.

변수 선언과 처리

BorrowChecker에서 변수를 관리하는 함수는 BorrowChecker::check_variable_decl와 BorrowChecker::check_borrowed_variable입니다. 여기서는 대여된 변수를 처리하는 것만 보겠습니다.

이전에 변수는 다음 AST를 통해 생성된다는걸 확인했었습니다.

#[derive(Debug, PartialEq)]
pub enum Statement {
    VariableDecl {
        name: String,
        value: Option<Expression>,
        is_borrowed: bool,
    },
    // ...
}

이후, 생성된 AST는 BorrowChecker::check_borrowed_variable로 전달됩니다. 이때 BorrowChecker::check 함수를 통해서 전달됩니다.

impl BorrowChecker {
	fn check_borrowed_variable(
        &mut self,
        name: &'a str,
        value: &'a Option<Expression>,
    ) -> BorrowResult {
        if let Some(Expression::Ident(ref ident)) = value {
            if let Some(state) = self.get_borrow(ident) {
                if state == &BorrowState::Borrowed {
                    return Err(/* 변수가 이미 대여된 상태라 다시 대여할 수 없음 */);
                }

                self.insert_borrow(name, BorrowState::ImmutBorrowed);
                return Ok(());
            }

            return Err(/* 변수 선언 안됨 */);
        }

        Err(BorrowError::InvalidBorrow(name.into()))
    }
}

이 함수는 검사해야할 변수식이 대여 규칙을 만족하고 있는지 검사합니다. 변수가 대여 상태(BorrowState::Borrowed)가 아닌 경우 self.insert_borrow 함수를 통해 변수와 상태를 등록하지만, 대여 상태인 변수가 들어오면 에러를 반환합니다.

표기를 단순화하기 위해 코드의 상황과 조건을 나누어 논리적 명제로 표현해보겠습니다. 주요 단계를 명제로 표현하면 다음과 같습니다.

$P$ : 값이 ident로 선언되어 있음
$Q$ : ident에 해당하는 state가 존재함
$R$ : state가 BorrowState::Borrowed임
$S$ : 통과
$E$ : 에러 반환. (에러 메시지는 여러 종류이지만 편의상 $E$ 로 통일)

이 명제들을 이용해 BorrowChecker::check_borrowed_variable를 표현하면 다음과 같고, 대여 규칙을 만족하는 경우는 한 가지입니다.

\frac{P \space \space \space Q \space \space \space \neg R}{S}

값이 선언되어 있고 상태가 있지만, 값이 이미 대여된 상태가 아닌 경우에만 유효합니다. 그 외 다른 조건들은 모든 대여 규칙을 만족하지 않습니다.

\frac{P \space \space \space Q \space \space \space R}{E} \space \space \space \frac{P \space \space \neg Q}{E} \space \space \space \frac{\neg P}{E}

함수 선언과 호출 처리

함수와 관련된 기능은 두 가지가 있습니다. 첫 번째는 함수를 선언하는 것이고, 두 번째는 함수를 호출하는 것입니다. 또한, 함수는 개별적인 스코프를 가지고 있습니다.

함수의 범위를 검사하는 것은 상대적으로 쉽습니다. BorrowChecker::check 함수는 AST를 재귀적으로 순회하면서 각 구문에 맞는 함수를 호출하고 있습니다. 따라서 함수 구문 처리 함수를 작성하고, 이를 check 함수에 추가하면 됩니다. 함수 구문 처리 함수는 함수 선언을 처리하는 메서드와 함수 호출을 처리하는 메서드로 구성됩니다.

먼저, 함수와 관련된 AST를 살펴보겠습니다.

#[derive(Debug, PartialEq)]
pub enum Statement {
    FunctionDef {
        name: String,
		// boolean은 함수가 대여됐는지 표시합니다.
        args: Option<Vec<(String, bool)>>,
        body: Vec<Statement>,
    },
    Return(Option<Expression>),
    Expr(Expression),
}

#[derive(Debug, PartialEq)]
pub enum Expression {
    // ...
    FunctionCall {
        name: Box<Expression>,
        args: Vec<Expression>,
    },
}

이 AST는 함수의 구문 구조를 나타냅니다. FunctionDef는 함수 정의를 나타냅니다. 특히 args의 튜플은 각 매개변수의 이름과 참조 여부를 나타냅니다. 예를들어, function foo(a, &b)가 있다면 [("a", false), ("b", true)]의 형태로 표시됩니다. Statement의 나머지 요소들인 Return은 함수의 반환값을 나타내고, Expr은 단일 표현식을 나타냅니다.

Expression은 표현식을 나타내고, FunctionCall은 함수 호출을 표현합니다. 호출할 함수의 이름과 전달할 인자 목록을 가지고 있습니다.

정의된 함수에 스코프를 할당하는 것과 함수 호출을 처리하는 것도 여타 구문 처리와 마찬가지로 BorrowChecker::check_statement를 통해 이루어집니다. 또한 함수는 내부에 여러 구문과 스코프를 가지고 있고, 또 어떤 함수는 반환 값을 가지고 있기 때문에 나머지 요소들도 추가해줘야 합니다.

impl BorrowChecker {
	fn check_statement(&mut self, stmt: &'a Statement) -> BorrowResult {
        match stmt {
            Statement::VariableDecl { ...} => self.check_variable_decl(...),
            Statement::FunctionDef { name, args, body } => {
                self.allocate_scope(|s| s.check_function_def(name, args, body))
            }
            Statement::FunctionCall { name, args } => self.check_function_call(name, args),
            Statement::Scope(stmts) => self.allocate_scope(...),
            Statement::Return(expr) => self.check_return(expr),
            Statement::Expr(expr) => self.check_expression(expr),
        }
    }
}

Statement::FunctionDef와 다르게 Statement::FunctionCall과 Statement::Return 그리고 Statement::Expr은 따로 스코프를 할당할 필요가 없기 때문에 그냥 호출을 하면 됩니다. 또한 단순히 AST에 해당 토큰이 있는지 확인을 하는 역할이 전부이기 때문에, 여기서는 Statement::FunctionDef만 다루도록 하겠습니다.

이 함수와 관련된 코드는 다음과 같습니다.

impl BorrowChecker {
	fn check_function_def(
        &mut self,
        _name: &'a str,
        args: &'a Option<Vec<(String, bool)>>,
        body: &'a [Statement],
    ) -> BorrowResult {
        self.borrows.push(HashMap::new());

		// 함수의 매개 변수 처리
        if let Some(args) = args {
            for (arg, is_borrowed) in args {
                self.insert_borrow(arg, BorrowState::Initialized);

                if *is_borrowed {
                    self.borrow_imm(arg)?;
                }
            }
        }

        // 함수 내부 구문 확인
        let result = self.check(body);

        // borrow 해제
        self.borrows.pop();

        result
    }

		fn borrow_imm(&mut self, name: &'a str) -> BorrowResult {
        let state = self.get_borrow(name);
        if state.is_none() || state == Some(&BorrowState::Initialized) {
            self.insert_borrow(name, BorrowState::ImmutBorrowed);
            return Ok(());
        }

        Err(BorrowError::CannotBorrowImmutable(name.into()))
    }
}

먼저 BorrowChecker::check_function_def 부터 보겠습니다. 이 함수는 정의된 함수를 확인하는 역할을 합니다. 먼저 새로운 스코프를 생성하고, 주어진 매개변수들을 스코프에 등록합니다. 등록된 매개변수는 borrowed된 상태인 경우 immutably borrowed로 설정합니다. 이후 함수의 본문(body)를 분석하고, 해당 범위에서의 빌림을 해제(pop)합니다.

function body handling

BorrowChecker::borrow_imm 함수는 주어진 이름의 변수를 불변하게 빌리는 작업을 합니다. 해당 변수가 아직 정의되지 않았거나 이미 초기화된 상태라면, 변수의 상태를 불변 대여로 변경하는 역할을 합니다. 러스트의 빌림 규칙을 적용하는 메서드라고 볼 수 있습니다.

요약하면 다음과 같습니다.

check_function_def() 함수는 함수의 매개변수를 처리할 때, 매개변수가 변경 가능 여부를 확인
변경 가능한 매개변수는 BorrowState::ImmutBorrowed 상태로 대여 됨
borrow_imm() 함수는 변수를 변경 불가능한 상태로 대여할 때, 해당 변수가 이전에 변경 가능한 상태로 대여되었는지 확인

결론

이렇게 빌림 규칙을 적용하는 코드를 작성해봤습니다. 물론 설계상의 오류도 있고 의도적으로 생략된 기능들도 있어서 완전히 러스트의 그것과 똑같이 동작한다고 할 순 없습니다. 하지만 코드 분석 시 어떻게 동작하고, 어떤 식으로 작동하는지 참고하는 용으로는 나쁘지 않은 것 같습니다. 당연히 개인적인 생각입니다.

만약 러스트 처럼 라이프타임(lifetime)을 추가한다면 대여 규칙을 적용한 것처럼 똑같이 라이프타임 규칙을 추가하면 됩니다. 라이프타임도 별반 다를 것 없이, 값을 넣기 위한 메모리를 할당 받고 있는 동안만 유효하고, 변수가 정의된 스코프 범위 내에서만 유효하다는 점에서 여기서 작성한 규칙과 딱히 다른 점이 없어 규현 자체는 무난할 것 같습니다. 나중에 시간이 되는대로 라이프타임 구현도 다루겠습니다.