LoginSignup
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@ktz_alias

自作したSQLiteオレオレパーザの仕様

Posted at

はじめに

4月の頭ごろにcrates.ioを眺めていたときlalrクレートに遭遇した。
見たら隠蔽しすぎない構造で、これ使ったらオレオレパーザが作れるんじゃね？
と思ったのがきっかけで、SQLiteのオレオレパーザ作りに手を染めてしまった。
SQLiteを選んだのは構文ルールがほどほどに単純で実用的そうだったから。

それからはや3ヶ月、右も左も分からない状態からスタートしたが、無事SQLiteの具象構文木(CST)を生成するオレオレパーザが動くところまできたので仕様をまとめてみた。

また、WASI Preview 2がブラウザでどの程度使えるのかの検証実験も兼ねている。
検証のため、SQLiteオレオレパーザのプレイグラウンドも作ってみた。

SQLite parser playground1

この記事が、これからパーザを作る人の参考になれば幸い・・・なのだけど、これ完全に怪文書の類だわ。

レポジトリ

Actionsもろくに整備していないため、他の人にはまともにビルドできない代物だけど参考までに。

パースルールの抽出

SQLiteのパーザは作者本人が作成したParser generatorであるLemon LALR(1) Parser Generatorによって生成されている。
このパーザの構文ルールはsrc/parser.yで定義されている。

この構文ルールはyaccやbisonに類似している。
このファイルを読んで構文ルールを自前で抽出してもいいのだけどメンドイ。
Lemonのメインソースであるtool/lemon.cを眺めたところ、この構文ルールを読む関数Parse関数がファイルスコープではなかったので、必要な型や関数をヘッダファイルとして抜き出し、bindgenでRustコードのバインディング定義を生成した。
定義情報にアクセスできれば、あとはどうとでもできるため、jsonとして抜き出しステートマシン構築の入力とした。

ステートマシンの構築

LALR(1)パーザは、その土台としてPush down automatonが鎮座している。
このステートマシンにソースコードから切り出されたトークン素片を順次渡していくことでパースを進めていく仕組みとなっている。

Rustで構文ルールを入力としてステートマシンに変換するクレートとしてlalrがある。
構造を隠蔽し過ぎず適度に生成結果にアクセスできる優れもの。
自前のSQLiteパーザでは、lalrクレートをフォークしたlalryを使用した。
lalryクレートではコンフリクト解消のための定義がトレイトとして切り出すよう変更されておりlalrクレートより扱いやすかったため。

lalrクレートとlalryクレートはいずれも、BtreeMapとして構文ルールの左辺値と右辺値を型つけしてマッピングしGrammar型に割り当て、
次いでGrammar::lalr1を呼ぶことでステートマシンに変換する。

生成されたステートマシンの各状態での遷移定義はBtreeMapベースとなっており、そのまま使うには性能が気になったため、phfクレートを使って静的に一発引きできるようソースコードとして展開させた。

スキャンルール

パーザはステートマシンの入力としてトークン素片（パーザ界隈ではlookaheadと呼ぶっぽい）が必要。
ソースコードからトークン素片を切り出すためのスキャナも必要である。

SQLiteにおいてスキャナはtokenize.cとして記述されておりルールを抜き出すことは困難そうだった。
そのため以下の視点で整理してスキャンルールをハンドメイドで抜き出しjsonとして作成した。

  • parser.yのキーワード終端記号2
  • tokenize.cでマッピングされる演算子の終端記号
  • tokenize.cでマッピングされる識別子やリテラルの終端記号

作成したjsonの定義を入力として

  • キーワードおよび演算子を文字列の前方一致で抽出
  • 識別子およびリテラルをregexクレートを介した正規表現による抽出

の2本立てでスキャンルールを作成した。
スキャンルールのルックアップも静的に一発引きするためphfを使ってソースコードとして展開した。

スキャナ

スキャナは基本ソースコードをスキャンルールに食わせてトークン素片を吐き出すだけだが、ここに一工夫加えた。

ひとつはトークン素片の前と後ろにコメントや空白・改行コードがあればトリビアとしてトークンに持たせている。
トリビアという考えはC#のパーザであるRoslynで知った。

型定義の前にドキュメントコメントを置くケースが多いため、コメントを前方のトリビア(leading-triviaと呼んでいる)として、
空白や改行コードを後方のトリビア(trailing-triviaと呼んでいる)として付与した。

空白や改行コードをtrailing-triviaとした理由は、構文木を使ってコード補完を実施するケースに都合が良くなるから。
例えば、SELECT と入力した場合、オフセット:6は空白(U+20)になるが、SELECTのtrailing-triviaとして修飾されているためSELECTの次の候補探索をスムーズに行うことができる。

トリビアに関する話は、以下の記事に詳しく書かれている。

この記事では

Triviaの設計において、あるTriviaを左右どちらのトークンに紐づけるかという点は注意が必要です。 ここではSwiftの設計を参考にします。 Swiftでは2つのルールに従ってTriviaの所属するノードを決定します。

トークンは自身のあとに続くTriviaを保持する。このとき改行文字は含まない。
1で所属の決まらないTriviaはその直後のトークンに所属する
(snip)
もうひとつはleading_triviaをみることで、そのトークンが行の最初のトークンかどうか判別できることです。

とあり、改行コードはtrailing-triviaではなくleading-triviaに持たせるのがベーターとある。
しかしSQLiteの構文ルールでは、空白や改行コードに関する終端記号がSPACEしかなく使い分けられないため諦めた。

・・・・んだけど、思い返すとtrailing-triviaとleading-triviaに別のスキャンルールを行わせつつ同一の終端記号SPACEを割り当てればいけるんじゃねということに今気づいたのでここは変更するかも。

もう一つの工夫点は、ソース最後の内容からトークン素片を切り出したあとに、終端記号EOFと名付けたトークンを吐き出すようにしている。
以下を実現するためにEOFトークンを構文木に組み込んでいる。

  • ソース末端のコメント、空白、改行コードの引き取り先
  • インクリメンタルパースの編集起点(anchorと呼んでいる)

またこれを実現するため、SQLiteのparser.yから構文ルールを抽出する際にEOFでルールが完結するよう修飾して出力している。

フルパーザ

ステートマシンとスキャナが揃えばパーザとしての必要最低限の部品が揃う。

ステートマシンでは、スキャナから受け取ったトークン素片を入力に状態遷移のアクションを行わせる。

遷移アクションの定義は以下

pub enum Transition {
    Shift { next_state: usize },
    Reduce{ pop_count: usize, lhs: u32 },
    Accept{ last_state: usize, lhs: u32 },
}

受け取ったアクションにより以下の処理を行う

  • Shift
    • 遷移先の状態番号next_stateをスタックに積む
    • スキャナを一つ進める
  • Reduce
    • pop_count文だけスタックから状態番号をポップ
    • スタック先頭に置かれた状態番号をチラ見し、GOTO遷移表をルックアップして取得した遷移先の状態番号をスタックに積む
  • Accept
    • 終了処理なので実行機としては特に何もしない

このパーザの目的は構文木を作ることであるが、ステートマシンの実行器でノード構築まで行うと色々とごっちゃになるのと、この後に書くエラー普及との接続をスムーズにするためステートマシンの状態遷移と構文木のノード構築を切り離している。

切り離しに際し、ステートマシンからの結果をイベントとして取りまとめて呼び出し元に返している。
イベントは以下のようにステートマシンの結果と1対1でマッピングするよう定義した。

pub enum ParseEvent {
    Shift { 
        kind: SyntaxKind, 
        /// transition before state
        current_state: usize, 
        /// transition after state
        next_state: usize, 
        /// edit state for incremental parsing
        edit_state: usize,
    },
    Reduce{ 
        kind: SyntaxKind, 
        /// transition before state
        current_state: usize, 
        /// transition after state
        next_state: usize, 
        /// count for popped from state stack
        pop_count: usize, 
        /// edit state for incremental parsing
        edit_state: usize,
    },
    Accept{ 
        kind: SyntaxKind, 
        /// final state
        last_state: usize,
        /// edit state for incremental parsing
        edit_state: usize,
    }
}

ステートマシンから受け取ったイベントを構文木構築器にそのまま渡して構文木を作る。
構築はステートマシン同様、以下のアクションを行なっている。

  • Shift
    • 終端ノードを作りスタックに積む
  • Reduce
    • pop_count分だけスタックから取り出し、取り出したノードを子ノードとし、左辺値で親ノードを作りスタックに積む
  • Accept
    • すべてのノードをスタックから取り出しルートノードを親として作成し呼び出し元に返す

LALR(1)のようなボトムアップ型の構文解析器では、構文木は以下のように再帰的な構造となる。

root
    stmt_list
        stmt_list
            stmt_list
            stmt
        stmt
    stmt

インクリメンタルパーザで編集範囲を特定する場合に横並びの方が都合良いため、以下のルールで追加のイベントを発行している。

  • 文の終端の記号に特別な意味を与え、追加でEmitイベントを発行する
    • SQLiteであればセミコロンが文の終端記号
  • 終端記号EOFが来たら、追加でEmitイベントとAcceptイベントを発行する

ParseEvent定義にEmitを追加している

pub enum ParseEvent {
    // (snip)
    Emit {
        kind: SyntaxKind, 
        /// edit state for incremental parsing
        edit_state: usize 
    }
}

構文木生成器がEmitイベントを受け取ると以下の処理を行う

  1. 前回Emit以降にスタックに積まれたノードをすべてポップ
  2. 取り出したノードを子ノードとし、ステートメントのノードを親としてノードを作りスタックに積む
  3. スタックにウォーターマークを設定し、次回のEmitに備える
  4. ステートマシンの実行器をリセットし仕切り直させる

これにより構文木構築器のスタックにはステートメントが直列に積まれ、Acceptイベント処理後は

root
    stmt
    stmt
    stmt
    stmt

のような構造になる。

構文木

構文木の作成にはrowanクレートを使用した。
rowanクレートはRust Analyzerの構文木構築のために作られたものである。
当初はrowanをフォークしたcstreeを検討していた。

cstreeがrowanと異なる点として

  • ノードに直接追加情報を持たせることができる
  • ソースから切り出されたトークン素片の文字を管理するInternCacheが公開されている

しかしcstreeのこれらの特徴は

  • リーフノードは追加情報が持てない
  • InternCacheを削除する仕組みまでは提供されていない
    • インクリメンタルパースで随時入力が変わるケースでは致命的

な理由からrowanを選択した。

ただしノードを特徴づけるメタデータとしての追加情報は付与したかったため、以下のように持たせた

  • rowanのSyntaxNodeはオフセット、長さ、種別で一意となるため、これをキーにメタデータをHashMapで管理
  • ノードは走査で渡り歩いていくため、HashMapをRcでラップしコピーのオーバーヘッドを最小限に

正確にはトリビアを持たない場合にTokenSetとTokenItemがキーとして重複してしまうため、エッジかノードかを示すフラグをもたせて一意性を確保している。

メタデータでは以下を保持させた

  • UTF-16エンコーディング単位でのオフセットと長さ
  • ノードのタイプ
  • エラー復旧のタイプ
  • ノードから辿れる最初のリーフノードがShiftした時の状態番号

ノードタイプとして以下を用意した

  • Node
    • 非終端ノード
  • TokenItem
    • トリビア修飾以外のメインのトークン
  • LeadingToken
    • トークン素片のleading-trivia
  • TrailingToken
    • トークン素片のtrailing-trivia
  • TokenSet
    • TokenItem, LeadingToken, TrailingTokenを子要素として持つ特別なノード
    • スキャナから切り出されるトークン素片と1対1の関係を保つ

メタデータが保持する状態番号について

ノードタイプTokenSetはShiftイベントを受けとって作成されるため、イベント作成時の状態をそのまま保持すればいい
一方ノードタイプNodeはReduceイベントを受けとって作成される。
子孫ノードとしてぶら下がるすべてのノードの構築が終わってしまっているためリーフノードがShiftした時の状態番号を特定できない。

ノード構築時にポップした子ノードの最初の要素から取ってきてもいいが、ここではステートマシン実行器で解決する方法を選んだ。
状態遷移のためのスタックとは別管理のスタックを用意し以下の処理を行っている。

  • Shift
    このスタックに現在の状態番号をそのまま積む
  • Reduce
    • pop_countが0の場合(ε遷移)、現在の状態番号をそのまま積む
      • ε遷移からは構文木のノードは作られないため、テキトーで構わないという判断
    • pop_count > 0の場合、pop_count - 1だけスタックからポップし、先頭の状態を取得
      • この先頭の状態がちょうど、最初のリーフノードがShiftした時の状態番号
  • Accept
    • 終了処理なのでとくになにもしない

エラー復旧

エディタからの入力途中でのパースは、ほぼほぼ失敗するものと見た方がいい。
コンパイラであればコンパイルエラーを出して処理を中断すればいいが、エディタのためのパーザではそうはいかず、なんかそれっぽい構文木を作ってやり過ごす必要がある。
それっぽい構文木をつくるためにはエラー復旧を行い、ステートマシンが回るよう復帰できるようにしなければならない。

エラー復旧のタイプとしては、Shift recovery, Delete recovery, Insert recoveryがDon’t Panic! Better, Fewer, Syntax Errors for LR
Parsersに記載されている。
この論文は、gmrtoolsのドキュメントを読んでいる時に知った。

今回のパーザでは、「次の入力で完全復帰することに全ベット！」を目標とし、Shift recoveryとDelete recoveryのみを行っている。
またANTLRでは完全復帰を目指してすべての復旧タイプを組み合わせて復帰できるまで何度も繰り返すが、どう見ても重くなる未来しか予測できないため以下の手抜き最適化を行っている。

  • Shift recoveryのみをステートマシンが復帰できるところまで実施
  • Shift recoveryで解決できなければDelete recoveryのみをステートマシンが復帰できるところまで実施
  • いずれでも復帰できなければ諦めて、エラー状態を示す構文木を作ってお茶を濁す

Shift recovery、Delete recoveryいずれもイベントを発行し、構文木構築器でノードとして組み込めるようにしている。

Shift recoveryの詳細

Shift recoveryでは、現在のトークン素片を受け入れるまで状態を任意に進めてエラー復旧を図る。
このパーザでは規定値として最大10層まで状態を進め、それを超えても解決できなければ諦める。

ところで、すべての状態を貪欲に巡った場合、構文ルールにもよるがカジュアルに数億パターン発生する。
エディタのためのパースでは多くとも猶予100msecくらいしかないため、すぐに処理が詰まる。

この状況を避けるため、以下の手抜き最適化と多様性の確保を行っている。

  • 遷移パターンをShift, ε遷移なReduce, ε遷移以外のReduceに分類
  • 各状態で分類ごとに10の遷移ルールを見つかった順にピックアップする
  • 目的のトークン素片が来た場合は常に採用する

これにより10層回しても多様性をそれとなく確保しつつ、1000パターンくらいまで絞ることができた。
見つかったパターンをはイベント列として発行する。
定義は以下

pub enum ParseEvent {
    // (snip)
    PatchShift { 
        kind: SyntaxKind, 
        /// transition before state
        current_state: usize, 
        /// transition after state
        next_state: usize, 
        /// edit state for incremental parsing
        edit_state: usize,
    },
    PatchReduce{ 
        kind: SyntaxKind, 
        /// transition before state
        current_state: usize, 
        /// transition after state
        next_state: usize, 
        /// count for popped from state stack
        pop_count: usize, 
        /// edit state for incremental parsing
        edit_state: usize,
    }
}

見てのとおりShiftイベントとReduceイベントと中身は全く同じ。

しかし、たとえ復旧パターンが見つかったとしても、そこからReduceに進めるかは運次第のため、少なくとも1回pop_count > 0のReduceが確実に起こるところまで進め、
そこまでのパスをイベント列として構築して発行している。

ここで前者のShiftまでの復旧をPatchフェーズ、後半のReduceまでの復旧をStitchフェーズと呼んで分けている。
Stitchフェーズでは、別途イベントは用意せず、通常の状態遷移同様ShiftイベントとReduceイベントを発行している。

Shift recoveryでは通常複数の復旧結果が得られる。
以下のルールで順位づけをして合否を決めている

  • より短いイベント列でPatchフェースを終えたパターンに、より高いスコアを与える
  • より長いイベント列でStitchフェースを終えたパターンに、より高いスコアを与える

Delete recoveryの詳細

Delete recoveryでは現在の状態を満たすトークン素片が来るまでスキャナを進め続けるエラー復旧手法。
しかしやりすぎると以降のトークンすべて削除してしまう恐れがあるので、規定値として3回の削除まで認め、それを超えても解決できなければ諦める。
削除したトークン素片は復旧イベントの一つとして発行している。
定義は以下

pub enum ParseEvent {
    // (snip)
    PatchDrop {
        kind: SyntaxKind, 
        /// transition before state
        current_state: usize, 
        /// transition after state
        next_state: usize, 
        /// edit state for incremental parsing
        edit_state: usize,
    }
}

また、Shift recovery同様、Stitch処理を行い、少なくとも1回pop_count > 0のReduceが確実に起こるところまで進めている。

インクリメンタルパーザ

エディタ向けのパーザとして毎回フルパースしていては負荷も高くやってられないため、差分の範囲に限定してパースすることでの省力化が必須。
しかし変更点の差分だけ再パースしても構文器としての整合性を保てるわけではないため、以下の措置を行い安定化を図っている。

  • 前回作成した構文木と編集範囲を示すEditScopeを受け取り、影響を受けるステートメントを決定する
  • 各ステートメントの範囲内で、編集前の範囲から左右1つ分TokenSetを広げ、その範囲を再パースの対象とする

EditScopeは編集前後の範囲を定義しているだけ。
WASI Preview 2でビルドしTypescriptから使うことを目的としているため、UTF-16を単位としている。
また編集前後で開始点は動かないため共有させている。

pub struct EditScope {
    /// editing start offset (UTF-16 char unit base)
    pub start_char_offset: usize,
    /// old editing length (UTF-16 char units)
    pub old_char_len: usize,
    /// new editing length (UTF-16 char units)
    pub new_char_len: usize,
}

ステートメント範囲の決定

編集は1ステートメントに限定されるとは限らない。

  • ステートメントを跨ぐようにコピペ
  • トリビアを残して削除

特に後者のトリビアに関しては前後のステートメントに引き取ってもらう必要があるため、ステートメントレベルで範囲を拡張する必要がある。

以下のアルゴリズムを採用した。

スキャナをステートメント単位で取り出せるようにする

  • ステートメントの終端記号(SQLiteならセミコロン)で区切るようプレスキャンする
  1. 範囲開始の基準点(anchorと呼んでいる)を決める
  • プランA: 開始位置は編集前後で変わらないため、開始位置より前のステートメントに対応するスキャナをとりだし、最末端のトークン素片と最末端のTokenSet一致するステートメントを探す
    • 判定は種別、ノード範囲、値の完全一致をもって行う
    • ステートメントの削除により残されたトリビアを押しつけられる可能性があるため、最大で2ステートメントまで探索範囲を広げる
    • 一つ前はトリビアの押しつけにより汚染されるが、そのさらに前はクリーンという判断
    • ソース最先端にprependされる場合、前方にクリーンなステートメントは存在しないため諦める
  • プランB: 範囲終点の右隣のステートメントに対して、対応するスキャナを取り出し、同様に最先端のトークン素片と最先端のTokenSet一致するステートメントを探す
  • プランC: EOFのみを含むステートメントをanchorとして採用する

プランBにおいて範囲終点は開始位置と異なり編集後に変更されるため安定的に使うことはできない。
そこで以下の方法で安定化を図っている。

  • 範囲以降のステートメントを最大3つピックアップし、各ステートメントについて完全一致した場合先頭のステートメントをanchorとして採用する
    • 判定はプランA同様、種別、ノード範囲、値の完全一致
  • 見つからない場合はピックアップから前2つを取り出し、スキャナの末端から順にトークン素片と比較して最長一致したステートメントをanchorとして採用する

後者はちょっとわかりにくいので補足を。
キャレットを移動しただけで範囲選択をしない場合、変更対象のステートメントがより前方かまたはより後方かを決定できない。
そのため防御的に後方のステートメントがanchor候補に入り込んでくる。
このケースでは最大3つのステートメントの完全一致は完遂しないが、その1つ後ろのステートメントはクリーンであることは確定的に明らか。
最長一致としているのはステートメントが必ずしも3つ揃うとは限らないため。

プランA、プランBでともにanchorを決定できない場合、プランCを採用する。
このケースはソース末端にトリビアを追加したり、末端のトリビアを残してソースを削除した場合に発生する。
anchorでかつ更新範囲の末端となる。

  1. ステートメントとスキャナを対応づける
  • プランAによりanchorが決定された場合、その次のステートメントとスキャナからスタートして対応づけを行う
  • プランBによりanchorが決定された場合、その一つ前のステートメントとスキャナからスタートして、前方に向けて逆向きに進めて対応づけを行う
  • プランCによりanchorが決定された場合、anchorのステートメントからスタートして、前方に向けて逆向きに進めて対応づけを行う

対応づけの型定義は以下の通りとなっており

pub struct EditHintSlots {
    pub events: Vec<SlotEvent>,
    pub replace_from: usize,
    pub replace_byte_range: Option<std::ops::Range<usize>>,
}

pub enum SlotEvent {
    Replacing{ node: SyntaxNode, scanner: StatementScanner },
    Deleting{ node: SyntaxNode },
    Inserting{ scanner: StatementScanner },
}
  • Replacing
    • ステートメントとスキャナが両方揃った場合
  • Deleting
    • スキャナが枯渇しステートメントが残った場合
  • Inserting
    • ステートメントが枯渇しスキャナが残った場合

というルールで関連付けを行っている。

ステートメント内の再パース範囲の決定

引き渡された範囲のみで再パースを行っても構文木が壊れるだけ。
そのため前回作成した構文木からステートメント内で前後1つ分のTokenSetをピックアップし、その範囲内で再パースを行う。

再パースに向けてReplacingのケースでは以下のアルゴリズムを採用した。

  1. 開始点のTokenSetの決定
  • 引き渡された範囲の開始点に位置するTokenSetを取得
  • その左隣のTokenSetを取得を取得
    • なければ最初に見つかったTokenSetを採用
    • 隣接ステートメントの場合も最初に見つかったTokenSetを採用
  1. 終点のTokenSetの決定
  • 引き渡された範囲の終点に位置するTokenSetを取得
  • その右隣のTokenSetを取得を取得
    • なければ最初に見つかったTokenSetを採用
    • 隣接ステートメントの場合も最初に見つかったTokenSetを採用
  1. 共通祖先(Leaqst Common Anscestor)の決定
  • 1, 2で見つかったそれぞれのTokenSetからrowanのSyntaxNode::anscestors()で祖先を列挙する
  • Iterator::rev()で逆順にしてIterator::zip()で繋ぎ合わせ、最長一致となるノードを採用する

  1. 共通祖先ノードのメタデータから取得した開始状態でステートマシン実行器を初期化する

  2. 共通祖先のノードが構築されるまでReduceアクションが発生するようステートマシンの実行器を回す。

  • 共通祖先のノード構築の確認のためスキャナは一つ多くトークン素片吐き出すようにし、そのトークン素片にマッチによりパースを打ち切る
  • ただし一つ多く取得したトークン素片がEOFでかつEOFのみを含むステートメントを再パースする場合ぶっ壊れるので特別扱いな処理をしている
  • Insertingは完全に新規のステートメントを作成するため、実質フルパースと同じ
  • Deletingは既存のステートメントを削除するだけなので何もしない

最後に再パースにより作成された新しいステートメント列をrowanのGreenNodeData::splice_children()で元のステートメント列と置換する。

さいごに

SQLiteなSQLのパースを行うところまではできているが、以下はまだ未実装。

  • マルチ編集
    • 今時のテキストエディタは複数行を同時編集できる
    • 結果複数行のEditScopeを同時に扱う必要がある
  • キャレット位置の次の補完候補のリストアップ
    • メタデータとして状態番号を保持しているため、遷移先のlookaheadを収集してくれば事足りる・・・のだが、文脈を持たせると便利かなと思って保留にしてる
    • 文脈とは、可能な限りReduceさせて非終端記号を決定すること
    • SQLを例として出すと、識別子(ID)だけよりかはFROMまで遡れればテーブル列挙となるし、SELECTまで遡れればカラム列挙が判定できるかも

また、プレイグラウンドを作ってみたので、よかったら触ってみてくださいませませ。

SQLite parser playground1

おまけ

ChatGPTと問答して、マルチ編集のおおまかな仕様決めに付き合ってもらった。
以下そのまとめ

マルチスコープ編集の仕様まとめ
1. 前提：EditScope列の前提とソート

    編集範囲は、すべて変更前のソースを基準とした EditScope 列として受け取る

    EditScope 列は以下のルールでソートする：

        offsetの降順（後方から前方へ）

        同一offsetは元の入力順の昇順（≒編集順）

    これにより、後ろから順に再パース・ツリー更新・Token再構築を行う戦略が可能

2. EditHintの構造と更新範囲決定
EditHint 構造：

struct EditHint {
    precedings: Vec<SyntaxNode>, // 編集範囲の前の最大2文
    statements: Vec<SyntaxNode>, // 編集範囲そのもの（statement単位）
    followings: Vec<SyntaxNode>, // 編集範囲の後の最大3文（Eof含む）
}

anchor決定戦略：

    範囲選択あり（statementsが存在）：

        precedings と followings の両方から anchor（未変更なノード）を探す

    範囲選択なし（挿入のみ）：

        precedings がなければ followings から anchor を探す

        すべて変化していても Eof statement が番兵として機能する

    SyntaxNode::index() によって、ツリー更新後も再取得可能にすることで、ノードの破壊に耐える

3. Token再構築（scanner入力）
スキャン対象の構築：

    precedings, statements から旧ツリーからトークン列を抽出

    followings については直前スコープで生成されたトークン列の一部を再利用

    上記を結合して、スキャン用の**差分ソース断片（String）**を構築

トークン構造：

    Token は leading_trivia, main_token, trailing_trivia を持つ

    各 Token は offset, len, kind, text を持つため、元のソース再構築が可能

    トークン列を用いて StatementScannerIterator によって statement に分解

4. 再パースとツリー更新

    得られた statements を、旧ツリーの該当範囲に対して splice で差し替える

    以降のスコープでは更新済みツリーをもとに、precedings などを再取得しない前提で処理継続

⚠️ 現時点での懸念点・未決定項目
❗ 1. EditHint構築時のノードの生存保証

    ツリー更新により SyntaxNode が無効化される可能性あり
    → 解決策：SyntaxNode::index() を EditHint に保持し、tree.get_node_by_index() で再取得

❗ 2. followingsからのanchor探索の偽陽性

    同一ステートメントが複数並ぶケース（例：SELECT 1; 連続）で、意図しないノードをanchorとして拾う可能性
    → 解決策：

        SyntaxNode::hash() で変更検出

        変更が現れるまで followings をスライディング探索

        最後は Eof による強制終了でbreak保証

❗ 3. Token再利用によるズレ・不整合

    followings に依存してToken列を再利用しているが、ツリー更新の影響を受けて整合性が崩れる可能性
    → 解決策：

        Token も offset と index ベースで持ち、必要に応じて再取得可にする

        Token の正しさを hash チェック or text 照合で確認する余地あり

❗ 4. 複数スコープが重なる場合の再構築順序の整合性

    編集の scope が隣接 or overlap していた場合の再パース範囲とsplice操作の副作用
    → 現在の offset降順 + scope単位splice によりほぼ問題なしと想定
    → ただし重なりが多い場合、最初から結合スコープにして1回で処理する手も検討余地あり（最適化）

✅ 総合的な評価と実装可否
項目	評価
設計の一貫性	✅ 高い
実装の見通し	✅ 明瞭（既存構造の再利用が可能）
拡張・保守性	✅ 高い（Hash戦略・Index参照など汎用性あり）
パフォーマンス懸念	⚠️ トークン列の連結・比較が頻発するため今後観測が必要

  1. リンクカードのタイトルがちゃんと表示されないので ↩ ↩2

  2. 実際にはparser.yからの構文ルールの抽出でついでに拾えるので手作業ではない ↩

0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?