tanstaafl.dev

세계에서 제일 빠른 JSON 파서 만들기

2020-08-21

마켓 데이터 이야기로 블로그를 연 김에, 마켓 데이터 이야기를 더 해 보자. 요즘 나는 크립토 마켓 데이터를 들여다 보고 있는데, 대부분의 크립토 거래소들은 웹소켓을 통해 JSON으로 마켓 데이터를 배포하고 있다. 예를 들면 이렇게 생긴 메시지들이 온다.

{"table":"spot/depth_l2_tbt",
 "action":"update",
 "data":[{"instrument_id":"BTC-USDT",
          "asks":[["9633.9","0","0","0"]],
          "bids":[["9629.3","0.3","0","2"]],
          "timestamp":"2020-06-23T06:19:58.732Z",
          "checksum":-1890242265}]}

(빈칸과 줄바꿈은 가독성을 위해 내가 추가했다.) 이 메시지는 다음과 같은 정보를 나타낸다.

트레이딩 전략들은 이 JSON을 파싱해서 호가 목록을 업데이트한다. 내가 알기로 크립토 시장은 아직 미국 선물시장같이 속도 경쟁이 치열하지는 않지만, 기왕이면 빠른 게 좋으니까 어떻게 하면 이 JSON을 빠르게 파싱할 수 있을까 심심풀이 삼아 뚝딱거려 보았는데, 그 과정이 흥미로웠어서 이렇게 포스팅을 해본다.

기존의 가장 빠른 라이브러리

C++ JSON 파서를 찾아보면 그 중 가장 빠르다는 라이브러리는 simdjson이란 물건이다. 벤치마크에 따르면 이 라이브러리는 두 번째로 빠른 라이브러리(RapidJSON)보다 세 배 이상 빠르다. 어떻게 이렇게 빠르게 만들었는지에 대해서도 무려 논문으로 잘 설명해주고 있다. 얼핏 봐도 엄청나게 많은 노력이 들어간 라이브러리로 보인다. 그럼 이것보다 빨리 파싱을 할 수는 없을까? 당연히 할 수 있다. 내가 짠 300줄이 안 되는 파서는 내 사용례에 관해서는 simdjson보다 다섯 배 빠르다. 내 벤치마크에서 메시지 하나당 simdjson은 1.66마이크로초, 내 파서는 0.37마이크로초가 걸린다. 이 정도면 과장 좀 보태서 세계에서 제일 빠른 JSON 파서라고 해도 되지 않을까?

비결은 꼼수

어떻게 이게 가능할까? 당연히 수많은 꼼수를 썼기 때문이다. 이 파서는 "내 사용례"에서만 쓸 수 있다. simdjson은 모든 사람이 쓰는 일반용 라이브러리이기 때문에 해야 하는, 아니면 할 수 없는 수 많은 일들이 있다. simdjson은 입력이 정당한 UTF-8 인코딩인지도 확인해야 하고, 여는 괄호와 닫는 괄호가 매칭되지 않는 포매팅 에러들도 다 잡아내고 친절한 에러 메시지를 던져줘야 하고, 심지어는 실수 파싱도 1 ULP내로 정확하게 해야 한다.

난 사실 이런 것이 다 필요 없다. 덕분에 내 파서는:

그리고 내가 짠 파서를 내가 쓰기 때문에, 사용하는 코드에 더 많은 것을 요구할 수 있다. 예를 들면 파서에 주어진 문자열 버퍼가 마지막까지 해제되지 않고 남아 있어야 한다는 조건 등을 걸 수 있다. (이런 조건을 걸 수 있으면 입력 받은 문자열을 내부 상태로 복사해 올 필요가 없기 때문에 아주 유리하다.)

물론 이런 장점이 있다고 해도 simdjson 보다 빠르게 파싱하는 것은 충분히 어렵고 흥미로운 일이다.

최소한의 요구 조건에서 시작하기: 토크나이저

빠르게 동작하는 프로그램을 짜고 싶을 때 잊지 않아야 하는 금과옥조가 있다:

섣부른 최적화는 만악의 근원이다(Premature optimization is the root of all evil).

요는 어설프게 처음부터 빠른 프로그램을 짜려고 삽질하지 말고 잘 동작하는 프로그램을 짠 뒤 프로파일링을 통해 점진적으로 속도를 개선하라는 이야기다. 이것은 99%의 프로젝트에서 옳은 이야기다.

하지만 이 파서를 만들 때 나는 반대 방향으로 시작했다: 거의 모든 요구조건을 무시하고, 내가 필요로 하는 일만 가장 빠르게 할 수 있는 코드에서 시작한 것이다. 왜냐면, 나는 simdjson보다 빠른 코드가 아니라면 이 일을 할 이유가 없었기 때문이다. 할 수 있는 가장 무식하고 빠른 코드를 짰는데 이것부터가 simdjson 보다 느리다면 그냥 포기하는 게 나으니까.

위 코드를 읽어들이기 위해서 필요한 제일 단순한 파서는 무엇일까? 입력이 JSON이라는 것을 무시하고, " , { } [ ] 같은 경계 문자(delimiter)들을 다 지워버리고 남은 문자열을 공백으로 자르는 것이다! 이런 과정을 거치면 위 JSON 문서는 다음과 같이 변한다.

table spot/depth_l2_tbt
action update
data instrument_id BTC-USDT
asks 9633.9 0 0 0
bids 9629.3 0.3 0 2
timestamp 2020-06-23T06:19:58.732Z
checksum -1890242265

살아남은 각각의 문자열을 토큰(token)이라고 부르자. 이런 일을 하는 초간단 공포의 무식한 파서, 아니 토크나이저(tokenizer)를 짜 보았다.

struct JSONTokenizer {
  string_view next_token; // 이번 토큰
  const char *p;          // 다음 토큰을 찾기 시작할 위치
  const char *end;        // end of buffer

  JSONTokenizer(string_view s): p(s.data()), end(s.data() + s.size()) {
    pop(); // 첫 번째 토큰을 찾는다
  }

  // 토큰이 남았으면 true, 더 없으면 false
  operator bool() const { return p < end; }

  // 지금 맨 앞에 있는 토큰을 반환한다.
  string_view front() {
    assert(p < end);
    return next_token;
  }

  // 다음 토큰을 찾아서 next_token 에 저장한다.
  void pop() {
    // 1. 토큰 시작 위치 찾기: 경계 문자가 아닌 문자가 나올 때까지 p를 전진시킨다.
    while(p < end && (*p == '{' || *p == '[' || *p == '}' || *p == ']' ||
                      *p == ':' || *p == ' ' || *p == '\t' || *p == ',')) {
      ++p;
    }

    // 문자열 끝에 도달했으면 더 이상 토큰이 없다.
    if (p >= end) { return; }

    // 2. 해당 토큰의 끝을 찾는다. 그러려면 토큰이 어떤 종류인지 알아야 한다.
    // 여기서는 문자열과 숫자만 지원한다. (true / false / null 등은 일단 무시)
    if (*p == '"') { // 따옴표로 시작하면 문자열
      // TODO escaped quote 파싱하던지 말던지 할것

      char* q = p + 1;
      // 문자열 끝을 찾는다
      while(*q != '"') ++q;
      next_token = string_view(p + 1, q - p - 1);

      // q가 문자열을 닫는 따옴표이니, 다음 칸부터 시작해서 다음 토큰을 찾는다
      p = q + 1;
    }
    else {
      // 문자열 아니면 실수일 것이다
      assert(isdigit(*p) || *p == '-');
      char* q = p+1;
      while(isdigit(*q) || *q == '.' || *q == 'e' || *q == '+') ++q;
      *q = 0;
      next_token = string_view(p, q-p);
      p = q;
    }
  }
};

이렇게 쓸 수 있다.

JSONTokenizer tokenizer(json_string_view);
while(tokenizer) {
  cout << tokenizer.front() << "\n";
  tokenizer.pop();
}

어디 가서 보일 만한 코드는 아니라 대충 짰고, 정리도 대충 했다... 하지만 뒤에 나올 파서의 기초가 된다. 중요한 포인트는 다음과 같다.

(3번째 포인트는 특히 속도에 중요하다. 일반 사용자를 대상으로 한 JSON 라이브러리에서는 이런 것을 요구할 수 없다. 따라서 파싱 단계에서 모든 정보를 읽어들여 내부 상태로 복사하는 과정을 거쳐야 한다. 하지만 내가 만든 라이브러리를 내가 쓸 때는 이런 문제가 없다.)

이 코드엔 말도 안되게 많은 문제가 있지만, 이것만 이용해도 위 형태의 메시지들은 쉽게 파싱할 수 있다. 나는 데이터가 어떻게 생겼을지 알기 때문이다. 토큰들을 순회하면서 bid를 만나면 그 후로 나오는 숫자 4개씩을 묶어서 호가를 업데이트하고, timestamp를 만나면 그 다음 토큰은 시간일 것이다.

속도를 재 봤더니 simdjson 보다 훨씬 빠르다! 좋아 이제 이 속도만 유지하면서 기능을 추가하면 대성공이다.

리스트와 오브젝트 처리하기

일반적인 JSON 파서가 되려면 어떤 기능을 추가해야 할까? 방금 본 토크나이저에는 수많은 문제가 있지만, 그 중 치명적인 것은 다른 원소들을 포함하는 리스트나 오브젝트들을 무시한다는 것이다. 예를 들어 토크나이저는 다음 두 문서를 똑같이 파싱한다.

{"bid": [1.0], "ask": [2.0]}
[{"bid": 1.0, "ask": 2.0}]

물론 거래소에서 배포하는 마켓 데이터의 형식이 고정되어 있다면 이것으로도 충분할 수 있지만, 늘 존재하는 것이 아니라 optional한 필드가 있다거나 하면 문제가 된다. 예를 들면 다음 두 메시지를 구분할 수 없다.

[{"price": 100.0, "qty": 1, "optional_aggressor_id": 3}, {"price": 101.0, "qty": 2}]
[{"price": 100.0, "qty": 1}, {"optional_aggressor_id": 3, "price": 101.0, "qty": 2}]

이를 위해 코드를 다음과 같이 고치면 어떨까?

  1. 이들을 나타내는 경계 문자(오브젝트는 {}, 리스트는 [])들을 앞으로 무시하지 말고, 여는 괄호가 나오면 토큰 시작으로 간주한다.
  2. 여는 괄호와 매칭되는 닫는 괄호를 찾아 거기까지를 토큰 하나로 간주한다.

이렇게 하면 위의 예제들을 어떻게 파싱하게 될까? 첫 번째 문자인 [와 매칭되는 ]은 문자열 끝에 있다. 그러니 첫 번째 토큰은 주어진 문자열 전체가 된다. 그러니 이 토큰을 추가로 쪼개야 한다. 왼쪽 끝과 오른쪽 끝의 []을 떼어내고 이들을 다시 토큰들로 쪼개면 위 예제 중 첫 번째는 다음과 같이 쪼개진다.

{"price": 100.0, "qty": 1, "optional_aggressor_id": 3}
{"price": 101.0, "qty": 2}

여기서 첫 번째 토큰을 가져와 양쪽 끝의 {}를 떼어내고 다시 쪼개면 다음과 같다.

"price"
100.0
"qty"
1
"optional_aggressor_id"
3

이렇게 재귀적으로 토큰들을 쪼개면 우리가 원하는 결과를 얻을 수 있다. 여는 괄호와 매칭되는 닫는 괄호를 찾는 것은 다행히 아주 쉬운 문제다. [를 만났을 경우 ]를 만날 때까지 전진하면 되는데, [[1],[2]] 같은 경우를 처리하려면 전진하는 도중에 []를 몇 개나 만났는지를 세어야 한다. 전진하면서 [을 만날 때마다 카운터를 하나 늘리고, ]을 만날 때마다 카운터를 하나 줄인다. 카운터가 0일 때 만나는 ]이 닫는 괄호가 된다. 예를 들면 다음과 같은 코드를 쓸 수 있겠다.

// p에서 시작하는 리스트 혹은 오브젝트의 끝(닫는 괄호)을 찾는다.
const char* advance_to_end(const char* p) {
    char open = *p; // [ 혹은 {
    char close = open == '{' ? '}' : ']';
    int counter = 0;
    ++p;
    while(p < end && (*p != close || counter > 0)) {
        if (*p == open) ++counter;
        if (*p == close) --counter;
    }
    return p;
}

(진짜로 사용한 코드가 아니다. 귀찮아서 테스트는 안해봤다.)

싱글 패스 토크나이저

이렇게 재귀적으로 토큰을 찾고, 토큰 내부를 다시 쪼개면 문자열의 각 부분을 여러 번 순회하게 된다. 극단적으로 (실제로 마켓 데이터로 날아올 가능성은 거의 없겠지만) 다음과 같은 JSON 문자열을 생각해 보자.

[[[[[[[[[[[[[[[[[[[[1, 2, 3]]]]]]]]]]]]]]]]]]]]

첫 번째 토큰을 찾기 위해 문자열 끝까지 전진한 뒤, 여기서 왼쪽과 오른쪽 []을 벗겨내고, 여기서 첫 번째 토큰을 찾으면 다시 문자열 끝까지 전진한다. 이렇게 반복하면 가운데 있는 1, 2, 3 부분은 총 20번 스캔하게 된다. 어떻게 하면 이 삽질을 피할 수 있을까? 어차피 [] 내부도 우리가 토큰으로 쪼개야 할 문자열이란 사실을 기억하자. 이럴 때 처음과 끝을 지정해서 토큰별로 쪼개는 대신, "이 위치에서 시작하는 토큰을 한개 잘라낸다"는 연산으로 코드를 바꾸면 구현이 간편해진다. 예를 들어 다음의 문자열을 파싱할 때:

[{"price": 100.0, "qty": 1, "optional_aggressor_id": 3}, {"price": 101.0, "qty": 2}]

첫 번째 [에 대응되는 ]를 찾느라 시간을 허비하지 말고, 첫 번째 글자만 잘라내자. 남은 문자열에서 첫 번째 토큰을 떼어낸다. (이 경우 {"price": 100.0, "qty": 1, "optional_aggressor_id": 3}) 그리고 다음 토큰도 떼어내고 나면, 토큰의 첫 글자가 절대로 될 수 없는 ]가 나온다. 그러면 이것이 우리가 찾던 닫는 괄호다.

이럴 때 문자열을 "먹어치우는consumes" 파싱 함수를 만든다고 생각하면 구현이 자연스러워진다. 이 함수는 문자열의 맨 앞에서부터 시작해서 자신이 처리할 수 있는 만큼 먹어치우고 나머지를 반환한다. 이 경우, 토큰 한 개를 먹어치우되, 토큰이 없으면 닫는 괄호까지 먹어치우는 함수를 만들면 된다.

string_view json; // 입력받은 JSON 문자열

// json[ix..] 문자열을 토큰을 하나 찾거나 닫는 괄호를 만날 때까지 먹어치운다.
// 토큰을 찾았을 경우 true, 못 찾았을 경우 거짓을 반환한다.
// 이 때 ix는 먹어치우고 남은 문자열 첫 글자의 인덱스가 된다.
// (ix가 레퍼런스 타입이라 입력과 출력을 겸한다는 데 유의한다)
bool consume(int& ix) {
  // 공백이나 ',' ':' 같이 우리가 처리하지 않는 문자들을 먹어치운다
  while(ix < json.size() && ignored(json[ix])) ++ix; // (*1)

  // TODO 문자열의 끝까지 먹어치웠을 경우 에러 처리

  // 첫 글자를 이용해 어떤 원소인지 (혹은 리스트/오브젝트의  끝인지) 알아낸다
  bool found;
  switch(json[ix]) {

    case ']': // fallthrough
    case '}': // 닫는 괄호를 찾았다. 이 괄호도 먹어치우고 false를 반환한다.
      ++ix;
      found = false;
      break;

    case '[': // 리스트를 찾았다.
      // 리스트 원소들을 더 먹을 수 없을 때까지 (닫는 괄호가 나올 때까지) 먹어치운다.
      while(consume(ix));
      // consume() 마지막 호출에서 닫는 괄호도 이미 먹어치웠으므로, 끝
      found = true;
      break;

    case '{': // 오브젝트를 찾았다.
      ...

    case 't': // true를 찾았다.
      assert(/* 다음 4자가 "true" 인지 */);
      ix += 4;
      return true;

    case 'f': // false를 찾았다.
      ...

    case '"': // 문자열을 찾았다.

    ...
  }
  return found; // (*2)
}

이렇게 하고

int ix = 0;
consume(ix);

하면, 문자열에 JSON 원소가 하나밖에 없다는 전제 하에 ix는 문서 끝까지 이동하고, ix는 계속 늘기만 하지 줄지 않으므로 문자열의 길이만큼 딱 한 번 스캔이 이루어진다는 것을 알 수 있다.

DOM API 지원하기

consume()은 각 오브젝트나 리스트들을 잘 쪼개주긴 하는데, 쪼갠 결과를 아직 아무데에도 저장하지 않는다. 쪼갠 결과값들을 어떻게 저장해 둬야 나중에 편하고 빠르게 사용할 수 있을까?

일반적인 JSON 파서를 사용하면 파싱한 JSON 문서에 DOM (Document Object Model) API를 사용해서 접근할 수 있다. DOM은 JSON 문서에 포함된 각 "원소"(문자열, 숫자, 리스트, 오브젝트들. Element 라고 부르자)마다 이를 표현하는 Element 오브젝트를 만들어 준다. JSON 문자열을 파서에 집어넣으면 문서 전체를 나타내는 Element 오브젝트가 돌아오고, 문법마다 다르지만 여기에서 포함된 각 값들(리스트의 경우 원소들, 오브젝트의 경우 키/값 쌍)을 얻을 수 있다. 이런 형태의 API를 예로 들 수 있다.

// [{"price": 100.0, "qty": 1, "optional_aggressor_id": 3}, {"price": 101.0, "qty": 2}] 이 들어간다고 가정
Element doc = parser.parse(json_string);

// 리스트의 첫 번째 원소를 표현하는 Element 오브젝트를 반환
Element first_trade = doc[0];

// 이러면 3이 출력될 것이다
cout << first_trade["optional_aggressor_id"].to_number() << "\n";

// 이것은 false를 출력할 것이다
cout << doc[1].contains("optional_aggressor_id") << "\n";

우리도 이런 API를 구현해 보자. consume()이 한 번 실행될 때마다 우리는 토큰 하나를 찾아낸다. 따라서 consume()이 종료할 때마다 DOM 트리를 만들어서 해당 토큰에 대한 정보를 저장할 수 있다. 해당 토큰에 대한 정보는 원래 JSON 문자열 안에서 해당 토큰의 시작 인덱스와 끝 인덱스로 하자. 이것은 위 코드에서 (*1)이 종료한 뒤 ix의 값, (*2)에 도달했을 때 ix의 값을 각각 저장해 둬서 얻을 수 있다. 위 예제 JSON을 이런 트리로 표현하면 대충 이런 그림을 얻을 수 있다.

루트의 [0,84)은 이 노드가 JSON 문자열의 0번 문자에서 83번 문자까지를 포함하는 값을 표현한다는 뜻이다. (왜 84가 아니라 83인가? 이것은 [0,84)가 반닫힌구간(half-closed interval) 이라 그렇다.) 그 아래 [1,55)[57,83)은 각각 리스트의 첫 번째 원소와 두 번째 원소를 나타낸다. 아래에 적힌 각 문자의 인덱스와 이 트리와 대조해서 확인해보자.

0000000000111111111122222222223333333333444444444455555555556666666666777777777788888
0123456789012345678901234567890123456789012345678901234567890123456789012345678901234
[{"price": 100.0, "qty": 1, "optional_aggressor_id": 3}, {"price": 101.0, "qty": 2}]

파싱 단계에서는 이런 트리에 각 토큰의 위치만 기록해 두고, 특정 값을 진짜로 읽어오고 싶으면 원본 JSON 문자열에서 해당 오프셋 부분을 잘라온다. ("문자열을 해제하지 말고 계속 들고 있어라" 라는 요구를 해야 하는 일반 파서는 할 수 없는 일이다) doc[0]["price"] 값은 위 트리에서 [11,16) 노드로 연결된다. 그러면 JSON 문자열에서 해당 부분을 불러와서 sscanf(), istringstream 혹은 from_chars() 따위를 이용해 실수형으로 바꿔 주면 된다.

이 트리를 어떻게 저장할까? 이런 트리를 구현하는 정석은 각 노드를 별도의 객체로 구현하고, 이들을 포인터로 연결해 두는 것이다. C++로 하면 이런 식이겠다.

struct DOMElement {
  int begin; // 해당 값의 시작 위치
  int end;   // 해당 값의 끝 위치 (정확하게는 past-the-end 위치)

  // 리스트나 오브젝트의 경우, 여기에 포함된 토큰들을 표현하는 DOMElement로 가는 포인터
  vector<DOMElement*> children;
};

(내가 소스를 다 까본 것은 아니지만) 이것이 일반적인 JSON 파서에서 파싱 결과를 내부적으로 저장하는 방법이다. consume()이 하나 끝나고 새 토큰을 찾을 때마다 해당 토큰을 표현하는 DOMElement 인스턴스를 newmalloc을 통해서 할당하면 된다. "섣부른 최적화는 만악의 근원" 정신에 입각해서 나도 이런 코드를 짜면 어떨까? 망한다. 메모리 할당은 너무 느리다. 이래선 simdjson 보다 5배, 50배 느린 라이브러리들 꼴이 난다. 이 문제를 메모리 풀을 사용해 푸는 파서들도 있다. (RapidJSON 이 그렇다.) 하지만 메모리 할당을 아예 할 필요가 없다면(!) 이 문제를 풀 필요도 없다.

이 파서에서는 결과값을 트리가 아니라 문자열과 같은 크기의 1차원 배열에 저장한다. 이 배열은 프로그램 시작시에 한 번 생성해 두면 파싱 과정에서는 어떤 할당도 일어나지 않는다. 어떻게 저장하느냐?

이것이 좀 헷갈리니 좀더 명확히 정의하자. consume() 함수는 실행 과정에서 ix값을 계속 바꾸는데, 세 시점의 값이 중요하다. 각각 이름을 붙여 보면

  1. start = 함수가 처음 호출되었을 때 ix에 들어 있는 값
  2. begin = 토큰 시작을 찾았을 때 ix에 들어 있는 값 ((*1) 위치)
  3. end = 함수가 종료될 때 ix에 들어 있는 값

beginend는 실제 토큰 값을 찾아야 하니까 중요한 것을 알겠는데, start는 왜 중요할까? 저장해 둔 consume() 함수의 결과값을 찾아오기 위해 필요하다. 8번째 문자에서 시작하고 22번째 문자에서 끝나는 리스트가 있다고 하자. 이 리스트의 첫 번째 원소가 어디에서 시작할지는 알기 어렵다. [ 3,7,2] 처럼 [ 뒤에 빈칸이 있을 수도 있기 때문이다. 하지만 start는 항상 일정하다! 나는 첫 글자 [를 먹어치우고 consume()을 호출하기 때문에, start는 빈칸이 몇 개 있건간에 리스트의 첫 글자 바로 다음인 9로 일정하다.

따라서 start는 어떤 토큰을 찾은 consume() 결과를 저장하는 배열의 인덱스로 쓴다. 다시 말해

p[start] = (begin, end)

가 되는 벡터

vector<pair<int, int>> p;

를 만드는 것이다. 그러면 내가 가진 리스트가 8번째 문자에서 시작한다면 첫 번째 원소의 위치를 p[9]로 얻을 수 있다. 두 번째 원소의 시작 위치는 어떨까? p[9](9, 11)이었다고 하자. 두 번째 원소는 그럼 consume(11)이 찾았을 테니, p[11]을 참조하면 두 번째 원소의 위치를 찾을 수 있다.

이런 방식으로 순회할 수 있게 하면, DOMElement에는 end도 저장할 필요가 없다. start만 알면 p[]에서 해당 정보를 읽어 오면 되니까.

consume()의 전체 소스 코드

// Grossly unsafe and nonstandard, but fast JSON parser
struct JSONParser {
  string_view buf;

  // result of initial linear scan: p[ix] tell you the result of consume() function call when starting with buf[ix]
  vector<tuple<int, int>> p;

  JSONParser(int n): p(n) {}

  // starts from ix, consumes a value. returns false when it meets a closing delimiter or end of string.
  bool consume(int& ix) {
    int start = ix;
    int begin;
    while(isspace(buf[ix]) || buf[ix] == ':' || buf[ix] == ',') ++ix;
    assert(buf[ix] != '\0'); // buf did not prematurely end

    switch(buf[ix]) {
      case ']': // fall through
      case '}':
        ix++; // we still consume ending delimiters!
        begin = -1;
        break;
      case '"':
        begin = ix++;
        while(buf[ix] != '"') ++ix;
        ++ix; // consume the closing quote
        break;
      case '[':
        begin = ix++;
        while(consume(ix));
        // closing delimiter is already consumed
        break;
      case '{':
        begin = ix++;
        while(consume(ix)) { CHECK_F(consume(ix)); } // value always comes in pairs in objects
        // closing delimiter is already consumed
        break;
      case 't': // true
        begin = ix;
        CHECK_F(strncmp(&buf[ix], "true", 4) == 0);
        ix += 4;
        break;
      case 'f': // false
        begin = ix;
        CHECK_F(strncmp(&buf[ix], "false", 5) == 0);
        ix += 5;
        break;
      default:
        CHECK_F(isdigit(buf[ix]) || buf[ix] == '-', "invalid value %s", &buf[start]);
        begin = ix;
        while(isdigit(buf[ix]) || buf[ix] == 'e' || buf[ix] == 'E' || buf[ix] == '-' || buf[ix] == '+' || buf[ix] == '.') { ++ix; }
        break;
    }
    p[start] = make_tuple(ix, begin);
    return begin >= 0;
  }

  ..

  // 이하 DOM API, parse() 구현
};

빈칸 채우기

p 배열이 있으면 이제 위 예제와 거의 비슷한 DOM API를 구현할 수 있다. 하지만 이것은 이제 너무 귀찮으므로... 구독자를 위한 숙제로 남겨 둔다. :-) 리플이 많이 달리면 다시 포스팅하는 것으로... (쿨럭)

기타

처음으로