Rust로 SQL 렉서 만들기: `Vec<char>`를 `&str`로, `Ident(String)`을 Span으로 바꾼 이유
출처: Dev.to
나는 Rust로 데이터베이스 엔진을 처음부터 만들면서 최근에 렉서(lexer)를 완성했다.
렉서 자체는 가장 흥미로운 부분은 아니었다.
내가 더 가치 있게 느낀 것은 Rust와 컴파일러·데이터베이스 시스템이 일반적으로 구현되는 방식을 배우면서 설계가 어떻게 진화했는가 하는 점이다.
시작할 때 나는 입력을 Vec<char> 로 저장했다.
UTF‑8 경계에 신경 쓰지 않고 문자에 바로 접근할 수 있어 직관적이라고 생각했다.
또한 식별자를 다음과 같이 표현했다:
Ident(String)겉보기엔 전혀 문제가 없어 보였다.
각 식별자 토큰이 자체 텍스트를 가지고 있어 파서가 바로 사용할 수 있었다.
하지만 렉서가 커지면서 나는 스스로에게 간단한 질문을 던졌다:
이미 원본 SQL 쿼리 안에 식별자가 존재한다.
왜 또 다른 문자열을 할당하고 같은 데이터를 매 토큰마다 복사하고 있는 걸까?
예를 들어 다음과 같은 쿼리를 생각해 보자:
SELECT username, email FROM users;원본 텍스트에는 이미
username
email
users가 존재한다.
각 식별자마다 별도의 String 할당을 만든다면, 이미 존재하는 데이터를 중복 복사하는 셈이다.
또한 Rust 열거형(enum)의 중요한 특성을 알게 되었다.
열거형의 크기는 가장 큰 변형(variant)의 크기에 의해 결정된다.
변형이 추가 데이터를 담기 시작하면, 모든 토큰 인스턴스가 실제 필요보다 커진다.
그래서 나는 식별자 텍스트를 토큰 안에 직접 저장하는 대신, 토큰 종류만 저장하도록 바꾸었다:
Ident그리고 소스 위치 정보를 함께 저장했다:
Span {
start,
end,
line,
column,
}이제 토큰은 두 가지 질문에만 답한다:
- 이 토큰은 무엇인가?
- 어디서 왔는가?
파서가 실제 식별자 텍스트가 필요하면, 저장된 바이트 범위를 이용해 원본 SQL 문자열에서 직접 복구하면 된다.
Vec 대신 &str 사용
두 번째 설계 변경은
Vec<char>에서 벗어나
&str을 직접 다루도록 바꾼 것이다.
수명(lifetime)을 이용해 입력 전체를 또 다른 컬렉션에 복사하지 않고, 렉서가 빌린 소스 텍스트 위를 걸어다니게 만들었다.
그 결과:
- 중복된 입력 버퍼가 없음
- 메모리 사용량 감소
- 할당 수 감소
- 단일 진실의 원천(single source of truth) 확보
렉서는 SQL 문자열을 소유하지 않는다. 단지 빌려서 사용한다.
예시 쿼리:
SELECT name, age FROM users WHERE age > 18;렉서는 다음과 같은 토큰을 만든다:
Select @ line 1, col 1, bytes 0..6
Ident @ line 1, col 8, bytes 7..11
Comma @ line 1, col 12, bytes 11..12
Ident @ line 1, col 14, bytes 13..16
From @ line 1, col 18, bytes 17..21
Ident @ line 1, col 23, bytes 22..27
Where @ line 1, col 29, bytes 28..33
Ident @ line 1, col 35, bytes 34..37
Gt @ line 1, col 39, bytes 38..39
IntLit(18) @ line 1, col 41, bytes 40..42
Semicolon @ line 1, col 43, bytes 42..43
Eof @ line 1, col 44, bytes 43..43이 프로젝트를 시작한 이유는 데이터베이스가 내부적으로 어떻게 동작하는지 이해하고 싶었기 때문이다.
지금까지 나를 가장 놀라게 한 것은 SQL 자체가 아니라, 소유권, 빌림, 데이터 표현에 관한 몇 가지 사소해 보이는 설계 결정이 시스템의 메모리 특성을 크게 바꿔놓는다는 점이었다.
렉서는 이제 완성되었다.
다음 목표: 파서와 AST 구축.
컴파일러, 인터프리터, 데이터베이스, 혹은 파서를 만든 경험이 있다면, 여러분이 구현하면서 가장 크게 바뀐 설계 결정이 무엇이었는지 공유해 주세요.