Lobsters

A New Way to Think About Borrow Checking (In Reverse)

역방향으로 생각하는 새로운 대여 검사 방식

Valen의 대여 검사기는 함수 본문을 뒤에서 앞으로 훑으며 참조의 사용, 선언, 변경을 추적합니다. 글은 이 방식이 마지막 사용 지점을 찾고 반복문을 처리하는 데 편리하다고 설명하지만, 반복문 처리에는 별도 규칙이 필요하며 검사기의 기능도 아직 완성되지 않았습니다.

에디터 노트

역방향 검사의 설득력은 마지막 사용 지점을 별도 탐색 없이 찾는다는 설명과 반복문 예제에 있습니다. 특히 루프 안에서 참조를 다시 설정하는 경우와 그렇지 않은 경우를 구분하는 규칙을 제시해, 단순히 함수 문장 순서만 뒤집은 아이디어에 그치지 않습니다. 다만 저자도 MUTATE가 pending 목록을 확인하는 비용을 해결하지 않았고, 처리량을 측정해 비교하지 않았다고 밝힙니다. 따라서 속도는 현재 검증된 결과가 아니라 예상입니다. 댓글은 시간 대칭성에 관한 기존 아이디어와 구현에 대한 호응을 보태지만, 알고리즘의 성능이나 완전성을 검증하지는 않습니다.

AI 요약

Valen은 Rust처럼 공유 참조와 가변 참조를 배타적으로 제한하는 방식 대신, 메모리에 안전한 가변 별칭을 허용하는 언어입니다. 이 글은 Valen의 대여 검사기가 함수 본문을 역방향으로 검사하는 방법을 설명합니다. 컴파일 과정은 네 단계로 나뉩니다. 정적 타입 검사, 그룹화, 메모리 안전성 검사 등을 거치며, 네 번째 단계가 함수의 마지막 문장에서 시작해 위쪽으로 진행합니다. 글에서 말하는 그룹(group)은 참조가 가리키는 메모리 경로를 나타냅니다.

역방향 검사로 use-after-free 찾기

두 번째 단계에서는 변수의 타입을 정하고, 세 번째 단계에서는 참조가 가리키는 경로를 정적으로 그룹화합니다. 예를 들어 배열의 첫 원소를 가리키는 참조는 배열 전체가 아니라 해당 배열 경로에 속한 참조로 기록됩니다. 네 번째 단계는 이 정보를 사용해 use-after-free를 찾습니다.

검사기는 문장을 거꾸로 읽으며 USE, DECLARE, MUTATE 이벤트를 기록합니다. 뒤쪽에서 사용된 변수는 pending 목록에 넣습니다. 더 위쪽에서 그 변수가 선언되면 목록에서 제거하고, pending에 남은 참조가 가리키는 메모리 경로를 변경하는 MUTATE를 만나면 오류로 처리합니다. 예를 들어 배열 원소를 가리키는 buff를 만든 뒤 배열에 원소를 추가하고 buff를 다시 사용하면, 변경이 참조를 무효화하므로 오류가 됩니다. 반대로 배열을 먼저 변경한 뒤 참조를 만들면 이후 사용은 유효합니다.

마지막 사용과 반복문

역방향 검사는 변수의 마지막 사용을 찾기 편합니다. 정방향 검사에서는 사용이 마지막인지 알기 위해 뒤쪽 문장까지 찾아야 하지만, 역방향 검사에서는 변수를 처음 만나는 사용이 뒤에서 본 마지막 사용입니다. 글은 이를 참조 카운트 감소, 소멸자 호출, use-after-free 검사 같은 bookkeeping에 활용할 수 있다고 설명합니다.

반복문은 별도 처리가 필요합니다. 루프 안에서 배열을 변경한 뒤 참조를 다시 설정하는 경우, 역방향 검사는 루프 시작점에서 pending 참조가 반복 중 변경으로 무효화되는지 확인합니다. 참조가 루프 안에서 다시 설정되는, 즉 revived 목록에 들어 있는 경우에는 검사를 통과합니다. 다시 설정하지 않으면 이전 반복에서 무효화된 참조를 사용할 수 있으므로 유효하지 않습니다. 저자는 이 방식이 각 구문 노드를 정방향과 역방향으로 한 번씩 처리해 더 빠를 것으로 예상하지만, MUTATE가 pending 목록 전체를 확인하므로 아직 O(n)이라고 단정하지 않습니다. 확인을 빠르게 할 방법은 찾고 있다고 덧붙입니다.

구현 범위와 다음 단계

Valen의 검사기는 약 3,600줄이며 아직 완성되지 않았습니다. break와 continue 같은 제어 흐름 중단, 연관 그룹, 클로저를 지원해야 합니다. 현재 그룹 추론은 한 방향으로 진행하지만, 향후 rustc처럼 함수 전체의 정보를 풀어 참조의 수명을 추론하는 단계로 바꾸는 방안을 제시합니다. 그 경우에도 네 번째 단계의 역방향 검사는 유지할 수 있다고 설명합니다. 또한 타입이 지정된 AST 대신 제어 흐름 그래프를 검사하도록 리팩터링할 계획입니다.

Lobsters 반응

  • @Verdagon — 기존 기법을 새롭게 적용한 점이 마음에 듭니다. 모두 즐겁게 읽어주길 바랍니다.
  • @anordal — 대여 검사도 시간 대칭적이어야 한다는 생각을 저도 했습니다. C에 파괴적 이동 의미론을 추가하자는 제안서에서 이 아이디어를 썼습니다.
  • @gavinmorrow — 정말 흥미롭고 우아하게 느껴집니다. 반복문 예제가 특히 인상적이었고, 저는 아주 재미있게 읽었습니다.

원문: Verdagon / 번역·요약: Trawling

원문 보기 ↗토론 보기 ↗