정규식으로 위키 언어를 어디까지 만들 수 있을까?

정규식도 생각보다 오래 버텨줬습니다

처음 위키 문법을 만들 때는 별도의 파서가 필요하다고 생각하지 않았습니다.

제목 기호를 <h2>로 바꾸고, [[문서]]를 링크로 바꾸고, 굵은 글씨 기호를 <strong>으로 바꾸면 얼추 위키처럼 보였습니다. 새로운 문법이 필요할 때마다 정규식 하나를 추가하면 됐고, 결과도 바로 화면에서 확인할 수 있었습니다.

원문
  ↓ RegExp 1-pass
중간 문자열
  ↓ RegExp 2-pass
HTML

나무마크 호환성을 높이면서 정규식은 점점 복잡해졌습니다. 먼저 긴 문법을 찾아 임시 값으로 바꿔두고, 짧은 문법을 처리한 뒤 다시 되돌리는 식으로 1-pass, 2-pass도 나눴습니다. 중첩된 구간은 미리 찾아 스택에 넣고, 닫는 기호가 나올 때마다 깊이를 세는 방식도 시도했습니다.

솔직히 여기까지도 꽤 재밌었습니다. 복잡한 정규식 하나가 원하는 문서를 정확히 바꿔주면 퍼즐을 푼 느낌이 들었거든요.

문제는 문법 하나를 잘 처리하는 것과, 여러 문법이 동시에 등장하는 문서를 이해하는 것은 전혀 다른 일이었다는 점입니다.

{{{ {{{0}}} }}}를 만나고 생각이 달라졌습니다

위키 문법은 기호만 보고 판단할 수 없는 경우가 많습니다.

코드 블록 안의 [[문서]]는 링크가 아니어야 합니다. 링크에 화면에 표시할 문자열에는 스타일 문법을 허용할 수 있지만, 링크 대상에도 같은 규칙을 적용하면 안 됩니다. 표 안에서는 |와 줄바꿈의 의미가 달라지고, 인용문이나 목록 안에서는 다시 블록 문법을 읽어야 합니다.

그리고 나무마크에는 다음처럼 같은 기호가 여러 번 중첩되는 문법도 있습니다.

{{{ {{{0}}} }}}

정규식으로 시작과 끝을 찾는 것만으로는 어느 닫는 괄호가 어느 시작 괄호와 짝인지 알기 어렵습니다. 앞 단계에서 치환한 문자열을 뒤 단계가 다시 문법으로 읽거나, 이미 이스케이프한 문자열을 한 번 더 이스케이프하는 문제도 생겼습니다.

무엇보다 정규식을 적용하는 순서 자체가 문법 사양이 되어버렸습니다. 문법 하나를 추가했는데 전혀 관계없는 링크나 표가 깨지는 일이 생겼고, 왜 그런지 설명하려면 전체 치환 순서를 다시 따라가야 했습니다.

이쯤 되니 더 복잡한 정규식을 쓰는 것으로는 해결되지 않겠다는 생각이 들었습니다.

문단별로 나눠서 병렬로 돌려보기도 했습니다

정규식 방식의 다음 시도는 문서를 문단 단위로 나누는 것이었습니다.

위키 문법은 많은 경우 줄이나 문단의 시작에서 블록이 나뉩니다. 그렇다면 큰 문서를 문단별로 잘라 각각 렌더링하고, Rayon으로 병렬 처리하면 속도와 구조를 함께 잡을 수 있지 않을까 생각했습니다.

실제로 문단별 병렬 파서도 만들어봤습니다. 독립된 문단만 놓고 보면 꽤 잘 동작했습니다.

하지만 모든 문법이 문단 안에서 끝나지는 않았습니다. 여러 줄을 차지하는 표와 접기 문법, 앞 문단의 상태가 뒤에 영향을 주는 입력, 아직 닫히지 않은 블록은 문단 경계를 단순히 끊기 어렵게 만들었습니다.

문단 단위로 병렬화하기 전에 먼저 “어디까지가 독립된 문법 단위인가”를 정확히 알아야 했습니다. 결국 파서가 해야 할 일을 파서보다 먼저 추측해서 나누고 있던 셈입니다.

ANTLR4와 EBNF로 문법을 명시하는 방식도 시도해봤습니다. 문법을 파일로 분리하고 생성된 파서가 구조를 읽게 하는 접근은 훨씬 정돈되어 보였습니다.

다만 제가 만들고 싶었던 위키 언어는 완성된 소스 코드만 읽는 컴파일러와 조금 달랐습니다. 사용자가 괄호를 절반만 입력한 순간에도 앞부분은 계속 분석해야 했고, 기존 나무마크의 애매한 입력도 가능한 범위까지 받아들여야 했습니다. 문법마다 세밀한 복구와 문맥 제어를 넣기에는 제가 원하는 방식과 잘 맞지 않았습니다.

여러 번 돌아간 끝에 가장 손에 맞았던 것이 Winnow를 이용한 combinator parser였습니다.

작은 파서를 직접 조합하는 방식이 잘 맞았습니다

조합 파서는 링크, 스타일, 표, 목록처럼 작은 파서를 함수로 만들고 이를 조합해 더 큰 문법을 읽습니다.

이 방식이 좋았던 이유는 단순히 Rust 코드로 작성할 수 있어서가 아니었습니다. 어느 지점까지 입력을 되돌릴지, 언제부터 해당 문법으로 확정할지, 중첩된 파서에 어떤 상태를 넘길지를 제가 직접 정할 수 있었습니다.

SevenMark의 ParseContext에는 현재 어느 종류의 문법을 읽고 있는지 나타내는 BlockMode가 있습니다.

FullDocument
NestedDocument
InlineContent

문서 전체를 읽을 때는 제목이나 목록 같은 블록 문법을 허용합니다. 인용문이나 목록 항목 안에서는 NestedDocument로 다시 문서를 읽습니다. 링크의 표시 문자열처럼 블록이 들어가면 안 되는 곳에서는 InlineContent만 허용합니다.

ParseGuard도 함께 사용합니다. 이미 굵은 글씨 안에 들어와 있다면 같은 문법을 또 열어도 되는지, 링크 대상 안에서 다시 링크를 시작해도 되는지를 파서 상태로 확인합니다.

이제 **를 만났다고 무조건 굵은 글씨로 바꾸지 않습니다.

지금 읽고 있는 위치에서 굵은 글씨를 시작해도 되는가?

를 먼저 판단합니다. 제가 원했던 context-aware parser가 이 구조에서야 제대로 보이기 시작했습니다.

HTML보다 AST를 먼저 만들었습니다

정규식 시절에는 파싱과 렌더링이 같은 작업이었습니다. 링크를 찾는 순간 <a> 태그를 만들었고, 제목을 찾는 순간 <h2>로 바꿨습니다.

SevenMark에서는 이 둘을 나눴습니다.

원문
  ↓
AST
  ├─ HTML 렌더러
  ├─ 포매터
  ├─ 문서 참조 분석기
  └─ LSP

링크는 대상과 표시 내용을 가진 노드가 됩니다. 제목은 단계와 내부 내용을 가진 노드가 되고, 표는 행과 셀로 나뉩니다. 미디어 문법도 파일 이름과 표시 옵션을 문자열 하나가 아니라 구조로 보관합니다.

AST가 생기니 같은 문서를 여러 목적으로 읽을 수 있었습니다.

렌더러는 HTML을 만들고, 문서 분석기는 링크와 include, 파일 참조만 뽑습니다. 포매터는 같은 의미를 표준 문법으로 다시 쓰고, LSP는 각 노드의 위치를 이용해 색상과 오류를 표시합니다.

HTML 디자인을 바꾸는 일이 파서 우선순위를 흔들지 않게 된 것도 좋았습니다. 이전에는 출력 문자열과 문법 인식이 너무 가까이 붙어 있었거든요.

작성 중인 문서는 틀린 문서가 아니었습니다

에디터에 파서를 붙이면서 또 하나를 배웠습니다.

서버 렌더러는 저장이 끝난 문서를 주로 받습니다. 에디터는 사용자가 [[문까지만 입력한 순간의 문서도 받습니다. 닫는 ]]가 아직 없는 것은 사용자가 틀린 문서를 저장했다는 뜻이 아니라, 그냥 작성 중이라는 뜻입니다.

마지막 문법 하나가 닫히지 않았다고 앞에서 정상적으로 읽은 제목과 링크까지 모두 버리면 문법 강조와 자동완성이 계속 깜빡입니다.

SevenMark는 가능한 곳까지 AST를 만들고, 남은 입력은 위치를 가진 ErrorElement로 보존합니다. 다른 해석이 가능한 구간에서는 입력을 되돌리고, 이미 고유한 시작 기호를 확인한 뒤의 오류는 해당 문법의 오류로 남깁니다.

파서 후보가 실패했을 때 상태도 함께 되돌려야 했습니다. 초기에 각주 번호나 제목 번호를 파싱 중에 바로 증가시켰더니, 실제로는 실패한 후보가 번호를 소비하는 일이 있었습니다.

지금은 AST를 모두 만든 뒤 별도 단계에서 번호를 부여합니다.

파싱 후보 탐색
      ↓
확정된 AST
      ↓
제목·각주 번호 부여

문법을 발견하는 일과 문서 전체 순서를 정하는 일을 나눈 것입니다.

중첩은 기능이면서 공격 입력이기도 했습니다

중첩 문법을 자유롭게 지원하면 재귀 깊이도 사용자가 정할 수 있습니다.

인용문 안에 목록을 넣고, 목록 안에 접기 문법을 넣고, 그 안에 다시 인용문을 계속 넣을 수 있습니다. 문법상 올바르다는 이유로 무한히 허용하면 작은 입력으로 스택과 CPU를 소모할 수 있습니다.

ParseContext는 재귀 깊이를 추적하며 기본 최대 깊이는 16입니다. 한도를 넘으면 프로세스가 panic하거나 스택 오버플로로 종료되지 않고, 처리 가능한 파서 오류를 반환합니다.

서버에서는 이것만 믿지 않습니다. 요청 본문 크기와 제한 시간, 동시에 실행할 파싱 작업 수를 별도로 제한합니다.

한 문서가 얼마나 깊어질 수 있는지와, 여러 문서가 동시에 들어왔을 때 서버가 얼마나 버틸 수 있는지는 다른 문제이기 때문입니다.

포매터를 붙이자 애매한 부분이 전부 들켰습니다

렌더러만 있을 때는 화면이 그럴듯하게 나오면 파서가 잘 만들어졌다고 생각하기 쉽습니다.

포매터를 만들고 나니 훨씬 까다로운 조건이 생겼습니다.

parse(format(parse(source)))

이 과정을 거쳐도 같은 의미가 남아야 하고, 여러 번 포맷해도 결과가 계속 달라져서는 안 됩니다.

이 테스트는 AST에서 정보를 너무 일찍 버린 곳을 잘 찾아냈습니다. 생략한 기본값과 사용자가 직접 적은 값이 같은 노드로 합쳐졌는데 다시 어느 형태로 써야 할지 정하지 않은 경우가 대표적이었습니다. 네임스페이스 별칭이나 미디어 옵션을 파서와 포매터가 서로 다르게 해석하는 문제도 드러났습니다.

여러 도구가 공통으로 알아야 하는 규칙은 sevenmark_spec으로 분리했습니다. 어떤 대상이 어떤 옵션을 지원하는지, 어느 표현을 표준 형태로 볼지는 렌더러 하나의 편의로 정할 일이 아니었습니다.

이제는 작은 언어 하나가 되었습니다

SevenMark는 지금 AST, 문법 사양, 파서, 변환 단계, HTML 렌더러, 포매터, LSP와 WASM 모듈로 나뉘어 있습니다.

처음부터 이 구조를 그려놓고 시작한 것은 아닙니다. 정규식으로 만들었다가, 문단별로 나눠봤다가, 문법 생성기도 시도했다가, 결국 조합 파서로 돌아왔습니다. 포매터와 LSP를 붙일 때마다 AST도 다시 바꿨습니다.

Rust는 이 과정에서 꽤 도움이 됐습니다. 노드 하나를 추가하면 렌더러와 포매터, LSP에서 빠진 처리가 컴파일 오류로 드러났고, 같은 코드를 WebAssembly로 빌드해 브라우저에도 올릴 수 있었습니다.

물론 Rust가 문법을 대신 설계해주지는 않습니다. 잘못 만든 AST도 아주 타입 안전하게 잘못될 수 있습니다. 결국 무엇을 하나의 노드로 볼지, 애매한 입력을 어디까지 허용할지는 직접 결정해야 했습니다.

그래도 정규식 치환으로 시작했던 코드가 이제는 렌더러와 포매터, 언어 서버가 함께 쓰는 DSL이 되었습니다.

초반 Sevenwiki를 만들며 가장 즐거웠던 작업을 하나 꼽으라면 아마 이 과정일 것 같습니다. 다음 글에서는 이 AST를 에디터에 붙이면서 생겼던, 생각보다 훨씬 골치 아팠던 위치 계산 이야기를 해보겠습니다.