ハクソク

世界を動かす技術を、日本語で。

HNに表示: Tree-sitterをGoに移植しました

89日前原文(github.com)

概要

gotreesitter は、CGoやCツールチェーン不要の 純粋なGo実装 のtree-sitterランタイム。 既存のtree-sitter文法を 再コンパイルなし で利用可能。 CGoバインディングよりも 全てのワークロードで高速、特にインクリメンタル編集で90倍のパフォーマンス。 クロスコンパイルやCI環境 での導入が容易。 205言語 に対応、エディタ・解析ツール開発に最適。

gotreesitter：Pure-Go Tree-sitterランタイムの特徴

  • CGo不要、Cツールチェーン不要、WASM対応
    • go get とビルドのみで利用可能、全プラットフォーム・全ターゲットサポート
    • クロスコンパイルが容易（例：GOOS=wasip1, GOARCH=arm64など）
  • tree-sitter互換のパーステーブル形式 を実装
    • 既存の文法ファイルを 再コンパイルなし でそのまま利用可能
  • CGoバインディングより圧倒的に高速
    • インクリメンタル編集で 約90倍高速
    • ノー編集時の再パースは 14,000倍高速
    • C実装の呼び出しオーバーヘッドを完全排除
  • CIやローカル開発環境がシンプル
    • Cツールチェーン不要、gcc未導入ユーザーでも go install が失敗しない
    • レースディテクタやファジング、カバレッジツールとの相性向上

クイックスタート

  • インポート例
    • import ( "fmt" "github.com/odvcencio/gotreesitter" "github.com/odvcencio/gotreesitter/grammars" )
  • 基本的な使い方
    • 文法取得： lang := grammars.GoLanguage()
    • パーサ生成： parser := gotreesitter.NewParser(lang)
    • パース： tree := parser.Parse(src)
    • インクリメンタル編集： tree2 := parser.ParseIncremental(newSrc, tree)
  • ファイル名から文法自動選択
    • grammars.DetectLanguage("main.go") で自動判定

クエリ・シンタックスハイライト・タグ抽出

  • S式クエリ言語 対応（predicates・カーソルストリーム含む）
  • シンタックスハイライト
    • NewHighlighter と Highlight でハイライト範囲抽出
  • シンボルタグ抽出
    • NewTagger と Tag で定義・参照位置抽出
  • 全ての主要なtree-sitterクエリ機能をサポート
    • #eq? #match? #any-of? #not-eq? #lua-match? #has-ancestor? など

インクリメンタル編集

  • 変更領域のみ再パース
    • 未変更部分はサブツリーを 自動再利用 しパフォーマンス向上
    • 1バイト編集時の再パースが 1.38μs（CGoは124μs）

パース品質管理

  • Qualityフィールド でパース信頼度を表示
    • full：完全サポート（外部スキャナ含む）
    • partial：一部サポート（外部スキャナ未実装）
    • none：未サポート

ベンチマーク

  • CGoバインディングとの比較
    • フルパース： 約1.5倍高速
    • インクリメンタル編集： 約90倍高速
    • ノー編集再パース： 約14,000倍高速
  • メモリ使用量 や アロケーション数 も最適化

対応言語と文法

  • 205言語 に対応
    • 204言語はfullサポート、1言語（norg）はpartialサポート
    • 195 DFA、9 token_source、111言語はGo製外部スキャナ実装
  • 言語セットのカスタマイズ
    • ビルドタグと環境変数で組み込み・外部文法の切り替え、キャッシュ制御
    • GOTREESITTER_GRAMMAR_SET でランタイム登録言語を制限可能

アーキテクチャ

  • パーサ ：テーブル駆動LR(1)、GLRサポート
  • インクリメンタル再利用 ：カーソルベース、未変更領域のスキップ
  • アリーナアロケータ ：GC負荷軽減
  • DFAレキサ ：文法テーブルから自動生成
  • 外部スキャナVM ：バイトコード解釈
  • クエリエンジン ：S式パターンマッチング
  • ハイライタ／タグ抽出 ：クエリベース

テスト・品質保証

  • 全205文法のスモークテスト
  • 20言語のゴールデンテスト
  • ハイライト・クエリ・パーサの単体/統合テスト
  • ファジング による堅牢性検証
  • go test ./... -race でレース検出対応

今後のロードマップ

  • クエリエンジンの互換性強化
  • dfa-partial言語の外部スキャナ追加
  • Parse()のエラー返却対応
  • C tree-sitterとの自動パリティテスト
  • ファジングの多言語展開

gotreesitterを活用したプロジェクト例

  • TUIエディタ向けツール群 ：https://github.com/odvcencio/gts-suite
  • 次世代バージョン管理システム Got ：https://github.com/odvcencio/got
  • 今後はGotHubという統合プロジェクトも計画中

gotreesitter は、レガシーアーキテクチャを含むあらゆるGoアプリケーションに 高速かつ簡易にtree-sitterのパワーを導入 できるソリューション。 エディタや言語サーバ、コード解析ツール開発者に特におすすめ。

Hackerたちの意見

これはBazelコミュニティにとって本当に素晴らしいですね。GazelleがGoで書かれているのに、tree-sitterに依存してGazelle言語拡張を作るにはCGOを使わなきゃいけないんです。これでCGOの依存をなくして、純粋なGoにできるかもしれません。何人かに見てもらうように連絡しました。

└

メッセージありがとう！本当に感謝してる。まさに君みたいな人のためにこれを作ったんだ。改めてありがとう！

└

これがgopackagesdriverバックエンドをサポートしてくれるといいな。

gotってOpenBSDのGotと混同されないかな？ https://gameoftrees.org/index.html

└

うわー！自分がちょっと賢すぎると思ってたけど、太陽の下に新しいものはないって考えるべきだったね。今、名前の提案を受け付けてるよ！

└

大多数の人が聞いたこともないものに、どうして混乱するのか理解できない。名前はメインストリームじゃないプロジェクトに気を使う必要ないと思う。

それはすごく興味深いね。私も似たようなプロジェクトに取り組んでるよ。https://replicated.wiki/blog/partII.html ただ、私はCRDTマージを使ってるんだ。3方向のメタデータなしのマージは、例えばgit+mergirafに対してほんの少しの改善しか提供しないから。gotがgitに対してどんな主な改善をもたらすと思う？

└

基本的に、gotは同じファイルの同時編集のために設計された構造的なVCSなんだ。これを実現するために、gotreesitterやgts-suiteの抽象化を使っていて、以下のことができるようになってる：- エンティティを意識したdiff - 行単位ではなく関数単位で - 構造的なブレイム - エンティティの生涯にわたる帰属解決 - 構造からのsemver - 何が破壊的変更で、何がマイナー、パッチかを知っているからバンプを推奨できる - エンティティの履歴 - エンティティが独立して追跡されるから、ファイルの名前変更や移動がエンティティの履歴に影響しない。gotreesitterが言語を解析できないときは、3方向のテキストマージがフォールバックとして行われる。構造的なマージが可能にするのは、同じエンティティに対して矛盾する変更がない限り、コンフリクトが発生しないことなんだ。

カスタムCレキサーの移植が、これを実現するための大きな問題の一部だったみたいだね。

└

うん、基本的にエンジニアリングの努力の約70%は、外部スキャナーの移植と元の(C) tree-sitterとの整合性を確保するのに使われたよ。

クロードがポート用のツリーシッターを試みたみたい。もっといいタイトルにした方がいいね。

└

で、どうだったの？

└

OPがクレードを使うことって関係あるの？

└

僕はリビジョン管理システムのプロジェクトに取り組んでるんだけど、マージはCRDTなんだ。2月22日にサーバーが侵入された（クライアントには暗号化されてないソースは置いてなかったし、サーバーログインはYubiKeyだけだったけど、それでも100%の保証はない）。その日はTelegramチャンネルに侵入を報告したよ。設計ドキュメントはここにあるよ https://replicated.wiki/blog/partII.html。粗いASTのためにツリーシッターを使ったんだけど、サーバーからいくつかの重要な部分が欠けてた。問題が起きると思ってたからね（東アジアでいろいろ冒険したし、悪いメイドや他の様々な事件もあったから）。最初に「Goのツリーシッター」ってタイトルを見たときはすごく嬉しかった。いくつかの問題が解決できそうだと思ったんだけど、全体像を見たら…

└

タイトルを見ただけで、私も最初にそう思ったよ。

これすごい！こんなの探してたから、作ってくれてありがとう！Goベースのフォージでシンタックスハイライトが必要なところ（GiteaやForgejoとか）にはめっちゃ役立つと思う。僕は厳格なno-cgoの要件があるから、Git+JJフォージのプロジェクトで使うかもしれないよ。https://gitncoffee.com

└

ありがたい言葉をありがとう！すごくクールなプロジェクトだね！君が何か役立つものを見つけられて本当に嬉しいよ。

TreeCursorsやtree-sitter-generateの相当するものはある？クエリやウォークが適さないケースが少なくともいくつかあるんだ。それに、文法をその場で再生成してコンパイルできるのがめちゃくちゃ助かることもある。少なくとも僕のユースケースでは、これだと使えないな。それと、これって何なの？ > partial [..] missing external scanner なんで一部の文法（htmlとか）で不正確な出力を保証するパースモードがあって、それを「90倍速い」ベンチマークの数字として使うの？

└

90倍の数字はCGOバウンドのツリーシッターと比較するためのGoソースに基づいてるよ。君のユースケースは僕が設計したものじゃないけど、確かにREADMEには近すぎるセクションがあるかも。今のところ欠けてる外部スキャナーはnorgだけだよ。君のユースケースを知ったから、何とか解決策を考えられるかもしれない。

私もtree-sitterのRustリライトを持ってるけど、エンドユーザーにはあまり役に立たない気がするな… https://github.com/HerringtonDarkholme/tree-sitter

これとLSPの関係を誰か説明してくれない？たとえば、Helixではこれを使っていろんな言語サーバーの代わりにできるの？

└

Tree-sitterは特定の言語のASTを生成するためのツールに過ぎない。一方、LSPはもっと多機能だよ（フォーマット、診断、プロジェクト全体の定義へのジャンプ、インレイヒント、ホバー時のドキュメント表示など）。その仕様を見ればわかるけど、互いに置き換えることはできないよ。[0]: https://microsoft.github.io/language-server-protocol/specifi...

これはすごく興味深いけど、リライトアプローチが長期的なメンテナンスやTree Sitterからの変更のポーティングにどう影響するか気になるな。WASM対応について触れてたけど、公式のTree SitterのWASMビルドをwazero（純粋なGoのWASMランタイム）と一緒に使うことを考えた？長期的にはアップストリームと同期を保つのに役立つかもしれないし、ちょっと遅くなるかもしれないけど、セキュリティやGCの面でもいい利点があるよ。