ASTとCRDT — 文字列編集から構造編集へ

ソフトウェアの世界では、ここ10年くらいでかなり大きな変化が起きている。

昔は、`document.txt` を編集するという発想だった。今は、構造化されたデータを操作するという発想に変わってきている。

この変化の中心にあるのが、AST（Abstract Syntax Tree）とCRDT（Conflict-free Replicated Data Type）である。

これらは単なる実装テクニックではなく、「人間が複雑な情報をどう扱うか」の根本を変え始めている。

第1章 ASTとは何か

ASTは、Abstract Syntax Tree の略で、日本語では「抽象構文木」と呼ばれる。

名前は難しいが、本質は単純である。

### ASTとは

ASTとは、コードを意味の構造として表現したもの。

例えば、次のようなコードがある。

```js

1 + 2 * 3

人間はこれを次のように理解する。

1 + (2 * 3)

コンピュータも同じで、内部では次のような木構造に変換する。

+

/ \

1   *

/ \

2   3

これがASTである。

つまりASTは、文字列を意味構造へ変換する仕組みだ。

なぜASTが必要なのか

もしコードを単なる文字列として扱うと、かなり困る。

例えば、次のコードを考える。

if (age > 18) {

login()

}

IDEは、どこがif文で、どこが条件で、どこが関数呼び出しかを理解したい。でも文字列だけでは難しい。

ASTにすると、概念的には次のようになる。

IfStatement

├─ Condition

│  └─ age > 18

└─ Body

└─ login()

すると、補完、リファクタリング、型推論、エラー表示、AI編集が可能になる。

ASTはGUI編集の基盤でもある

ここがかなり重要。

ノーコードツールは「コードを書かない」ように見える。でも実際には、「ASTを別UIで編集している」と考えられる。

例えばWeWebで、ボタンを置く、色を変える、APIを接続する、とする。

内部では概念的に次のような構造ができる。

{

"type": "Button",

"props": {

"color": "red"

},

"events": {

"click": "fetchData"

}

}

つまり、次のようなコードを書いているのと本質的には同じ。

\

だから、Figma、Notion、WeWeb、Bubble、Webflowは全部、GUIによるAST編集システムとして理解できる。

ASTの本当の価値

ASTの価値は、部分的に理解できることにある。

文字列だと、全体を読む必要がある。でもASTだと、このノードだけ変更できる。

これはReactのVirtual DOMにも近い。

Reactは、前の木と新しい木の差分を計算する。ASTも同じである。

だから最近のシステムは、全文再計算から差分更新へ移行している。

第2章 Incremental Parsing

ASTの進化版として重要なのが、incremental parsingである。

昔のエディタは、1文字変更するたびに全文解析していた。巨大ファイルだと遅い。

今は、変更箇所周辺だけ再解析する。

例えば、次のコードがある。

const x = 1

これを次のように変える。

const y = 1

このとき、const、=、1 は変わっていない。だから再利用する。

これによって、VSCode、TypeScript、Rust Analyzer、Cursorなどが高速に動く。

第3章 CRDTとは何か

ここからがさらに面白い。

CRDTは、Conflict-free Replicated Data Type の略である。

本質は、複数人が同時編集しても壊れないデータ構造である。

例えばGoogle Docsで、君が Hello を書いている時、別の人が World を書いても壊れない。

普通に考えるとこれは難しい。なぜなら、「最後に保存した方が勝つ」だと片方の変更が消えるからである。

昔の解法：ロック

昔は、誰かが編集中なら、他人は編集不可にする方式だった。

いわゆるExcel共有地獄である。

でも現代アプリでは、全員同時編集が前提になる。そこでCRDTが必要になる。

CRDTの基本アイデア

CRDTでは、文字列を直接編集しない。

代わりに、操作を記録する。

例えば、Hello に ! を追加する。

普通は次のように全体保存する。

Hello!

CRDTでは、次のような操作として扱う。

{

"op": "insert",

"after": 5,

"char": "!"

}

つまり、documentからoperation logへ発想転換している。

なぜこれが強いのか

operationベースにすると、undoできる、replayできる、mergeしやすい、offline編集可能になる。

Gitもかなり近い思想である。

CRDTの核心

CRDTでは各要素に固有IDを持たせる。

例えば次のように扱う。

H(1)

e(2)

l(3)

l(4)

o(5)

そこに次の操作を追加する。

insert after 5: !

すると、操作順序を維持でき、分散mergeが可能になり、conflictを回避しやすくなる。

Operational Transformとの違い

Google Docs初期は、OT（Operational Transform）を使っていた。

OTは、操作同士を変換する方式である。かなり複雑だ。

CRDTは、データ構造側を工夫する。最近はCRDT寄りの実装が増えている。

第4章 Figmaが革命的だった理由

Figmaは、ブラウザ、Photoshop級UI、リアルタイム共同編集を同時に実現した。

これはかなり異常である。

内部では、巨大なシーングラフを持っている。

例えば、概念的には次のような構造になる。

Page

└─ Frame

├─ Text

└─ Rectangle

変更時は、次のような操作だけを送る。

move node 182

resize frame 44

change color 91

つまり、全文同期から操作同期になっている。

これが軽さの本質である。

第5章 ASTとCRDTは繋がっている

ここが一番重要。

ASTとCRDTは別技術に見える。でも本質は同じである。

共通点は、文字列を直接扱わないこと。

昔は document.txt を直接編集していた。

今は、構造化ノードと操作ログを扱う。

つまり、編集とは文字列変更ではなく、構造操作へ変わっている。

第6章 AI時代との関係

これはAIと極めて相性がいい。

LLMは、全文生成より構造差分生成の方が安全である。

例えばCursorも最近は、AST diff、semantic edit、partial rewrite寄りになっている。

なぜなら、壊れにくい、merge可能、部分修正可能、意図を保持しやすいからである。

第7章 今後起きること

今後はさらに、テキストから構造化データへ、構造化データから操作ログへ、そしてAI編集可能状態へ進む。

つまり未来のソフトウェアは、ファイルを編集せず、構造を編集し、操作を保存し、AIが部分変更するようになる。

だからASTやCRDTは単なる技術ではなく、情報そのものの扱い方の変化である。

ASTとCRDTの第二世代 — AI時代の共有構造編集

前回、ASTとCRDTについて説明した。

本質は、文字列編集から構造編集への移行だった。

しかし今、この流れはさらに大きく進化している。

それが第二世代である。

第一世代では、IDE高速化、リアルタイム共同編集、部分更新、ブラウザアプリ化が主目的だった。

しかし第二世代では、目的そのものが変わる。

第一世代の目的

第一世代AST/CRDTの目的は、人間が快適に編集することだった。

例えば、VSCode、Google Docs、Figma、Notion。

ここで重要だったのは、低遅延、差分更新、multiplayer、partial recomputeである。

つまり、高速な編集UIを作ることが目的だった。

第二世代で起きた変化

AIによって状況が変わった。

今は、人間だけが編集者ではない。AIも編集主体になる。

すると問題が変わる。

昔は、どう速く編集するかが重要だった。

今は、どう壊さず編集するかが重要になる。

ここでAST/CRDTが急激に重要になった。

なぜAIは全文生成と相性が悪いのか

初期のLLMは、全文を書き直すスタイルだった。

例えば「この関数async化して」と言うと、AIは巨大ファイル全体を再生成していた。

これはかなり危険である。

なぜなら、merge conflict、意図消失、formatting崩壊、無関係変更、hallucinationが起きるからだ。

つまり、文字列生成AIには限界があった。

第二世代AIは構造を編集する

そこで最近のAI IDEは、全文生成から構造差分生成へ移行している。

例えば、次の関数がある。

function fetchUser() {

return api.get("/user")

}

これをasync化する。

第一世代AIは、ファイル全体を再生成する。

第二世代AIは、FunctionDeclaration nodeを変更する。

つまり、AST-aware editingである。

Semantic Editing

ここで重要なのが、semantic editingである。

これは、文字列変更ではなく意味変更を扱う。

例えば、rename variable。

普通の編集だと文字列置換になる。

でもsemantic editingでは、symbol rename operationになる。

つまり、scope理解、import更新、type保持、reference追跡が可能になる。

CursorやJetBrains系がここに向かっている。

CRDTも第二世代に入っている

CRDTも進化している。

昔のCRDTは、文字列同期が中心だった。Google Docs的世界である。

しかし現代アプリは、構造化データを扱う。

例えばNotionは次のような構造を持つ。

Page

├─ Heading

├─ Todo

└─ Database

Figmaは次のような構造を持つ。

Canvas

├─ Frame

├─ Text

└─ Component

これは単なるテキストではない。

そこでTree CRDTが重要になる。

Tree CRDTとは何か

普通のCRDTは、文字列位置を同期する。

Tree CRDTは、ノード構造を同期する。

つまり、insert character ではなく、move node、delete subtree、change property を扱う。

これが、Notion、Figma、Excalidraw、tldraw、Museなどで重要になる。

第二世代の本質

ここがかなり重要。

第二世代では、documentという概念自体が弱くなる。

代わりに現れるのは、persistent shared stateである。

つまり、「ファイルを開く」ではなく、「共有状態に接続する」。

Notionがファイルっぽくないのはこれである。

Operation Log が中心になる

第二世代では、現在状態より操作履歴が重要になる。

例えば、次のような操作である。

move node 182

change color node 44

rename symbol fetchUser -> getUser

これが本質的データになる。

つまり、編集は状態変更ではなく、operation streamになる。

Local-first software

第二世代を語る上で重要なのが、local-firstである。

これはInk & Switchが強く提唱した。

思想は、クラウド従属をやめること。

つまり、offline動作、local保存、後で同期、cloudは補助という考え方である。

この時CRDTが極めて重要になる。

なぜなら、後からmergeできるからだ。

Figma以降の多くのアプリは、single source of truthをserverに置かなくなっている。

第二世代とAIの融合

ここからさらに重要。

AIはoperation生成と非常に相性がいい。

つまり未来のAIは、全文を書くのではなく、構造差分を提案する。

例えば、extract component、normalize schema、refactor subtree のような操作である。

これは、mergeしやすい、review可能、undo可能、collaborativeである。

つまりAIも共同編集者になる。

ASTとCRDTが融合し始めている

これが今起きている最も大きな変化。

昔は、ASTはcompiler技術で、CRDTはmultiplayer技術だった。

今は、AI editing、shared state、semantic operationsによって融合し始めている。

つまり、構造、操作、意味、同期を統合した世界である。

最終的に何が起きるのか

最終的には、ファイル編集という概念がかなり弱くなる。

代わりに、persistent collaborative semantic graphのようなものになる。

つまり未来のソフトウェアは、文字列ではなく構造、保存ではなく同期、編集ではなくoperation、単独作業ではなく共有状態、人間専用ではなくAI共同編集へ向かう。

ASTとCRDTの第二世代とは、AIと人間が共有構造を共同編集するための基盤への進化である。