一休.com Advent Calendar 2025 の25日目の記事です。 一休.com レストランの開発を担当している恩田 @takashi_onda です。 最近はあまり聞かれることのないダイナミックスコープの話をしてみたいと思います。 はじめに 現代のプログラミング言語ではレキシカルスコープがあまりに当たり前になってしまっていて、ダイナミックスコープという概念自体を聞いたことがない、という人も多いのではないかと思います。 プログラミング言語の歴史を学ぶ際に少し触れられている程度で、実際、手元の『コンピュータプログラミングの概念・技法・モデル』を繙いてみても、900ページ近い大著にもかかわらずダイナミックスコープについての言及は1ページにも満たないほどです。 このようにダイナミックスコープは歴史の中で消えていった概念のように見えます。ですが、用語としては廃れた一方で、今日でも似た仕組み自体が実は再発明されています。使い方に注意は必要ですが、うまくはまると既存コードへの侵襲を最小に抑えながら文脈を伝播させる手段として、今も有効な選択肢だからではないでしょうか。 本稿では、ダイナミックスコープの歴史を振り返りながら、なぜ今も形を変えてその考え方が引き継がれているのか、文脈伝播の観点から見直してみたいと思います。 レキシカルスコープとダイナミックスコープ まずは定義の確認からはじめたいと思います。 現代のプログラミング言語において、私たちが当たり前のように享受しているのがレキシカルスコープ（静的スコープ）です。 const x = 'Global' ; function printX ( suffix ) { const prefix = 'value is ' console . log ( ` ${ prefix }${ x }${ suffix } ` ) ; } function withLocalX () { const x = 'Local' ; printX ( '!' ) ; } withLocalX () ; // -> 'value is Global!' printX ( '?' ) // -> 'value is Global?' ここで、 printX に現れる変数に注目して、用語 1 をふたつ紹介します。 束縛変数（bound variable）: 関数の引数（ suffix ）や内部での宣言（ prefix ）によって、その場で意味が確定する変数を指します。 自由変数（free variable）: 関数の中で宣言も引数定義もされていない変数を指します。この例では x がそれにあたります。 レキシカルスコープとダイナミックスコープの違いは、この自由変数をどう解決するかにあります。 レキシカルスコープのルールはシンプルです。自由変数の意味は関数が定義された場所によって静的に決まる、というものです。上の例では printX が定義された場所の外側にある値 'Global' が参照されます。呼び出し元である withLocalX の内部に同名の変数があっても、それは無視されます。 この性質により、私たちはコードの構造から変数の由来を一意に辿ることができるという恩恵に与っています。 ごくごく自然に感じられると思います。 さて、今回取り上げるダイナミックスコープ（動的スコープ）を見てみましょう。ダイナミックスコープは、自由変数の解決をコード上の位置ではなく、実行時の呼び出しスタックに委ねます。 Perl の local 宣言 2 を例に見てみましょう。 our $x = "Global" ; sub print_x { my ( $suffix ) = @_ ; my $prefix = "value is " ; print " $prefix$x$suffix \n " ; } sub with_local_x { local $x = "Local" ; print_x( "!" ); } with_local_x(); # -> "value is Local!" print_x( "?" ); # -> "value is Global?" print_x が呼ばれる際、その自由変数 $x の値は自分を呼び出している実行時のコールスタックの状態で決定されます。 with_local_x の中で $x が一時的に変更されているため print_x はその値 "Local" を出力します。そして with_local_x の実行が終われば、その一時的な束縛が解除され $x の値はふたたび "Global" が参照されるようになります。 ダイナミックスコープの歴史 現代の感覚では、ダイナミックスコープは予測不能で不確実なものに見えると思います。では、なぜこのような仕組みが生まれ、利用されてきたのでしょうか。その経緯を振り返ってみたいと思います。 副産物としての誕生 ダイナミックスコープの起源は、1950年代後半の初期の Lisp に遡ります。 初期の Lisp においてダイナミックスコープは、意図的に設計された機能というよりは、素朴な実装の帰結でした。当時のインタプリタにおいて変数の値を解決するもっとも単純な方法は、実行時のシンボルテーブル（A-list と呼ばれる連想リスト）をスタックの根元に向かって順に検索することでした。関数を定義時の環境と一緒に保持するという発想（後にクロージャと呼ばれるもの）はまだなく、この素直な実装が、結果としてダイナミックスコープを生み出しました。 John McCarthy は後に、ダイナミックスコープを、意図した仕様ではなく単なる実装上のバグであり、いずれ修正されるだろうと考えていたと回想しています 3 。 引数バケツリレーの回避策としての受容 しかし、この偶然の挙動は実用上の利便性をもたらしました。 プログラムが複雑化し、関数の呼び出し階層が深くなると、末端の処理で必要になる設定値やフラグを、すべての中間関数に引数として渡し続ける必要が出てきます。いわゆるバケツリレー問題ですね。 ダイナミックスコープを利用すれば、呼び出し元で変数を一時的に束縛するだけで、中間層のコードを一切変更することなく、深い階層にある関数に情報を伝播させることができました。 Scheme によるレキシカルスコープの確立 この状況に変化をもたらしたのが、1970年代に登場した Scheme です。 Gerald Jay Sussman と Guy L. Steele Jr. は、ラムダ計算の理論を忠実に実装する過程で、関数が定義された時点の環境を保持するレキシカルスコープを導入しました。これにより、関数の挙動が呼び出し元に依存するという不確実性が排除され、数学的な一貫性とモジュールとしての独立性が確保されました。 これ以降、プログラミング言語のメインストリームはレキシカルスコープへと収束していき、ダイナミックスコープは扱いの難しいかつての仕組みとして、多くの言語から姿を消していくことになります。 Emacs Lisp における意図的な選択 Scheme がレキシカルスコープによって数学的に整合したモデルを確立していった一方で、Emacs Lisp は長らくダイナミックスコープをデフォルトとして採用し続けました 4 。 当時の計算資源の制約といった実装上の理由もあったようですが、結果としてこの選択は、実行時に振る舞いを拡張・上書き可能なエディタ、というより環境であった Emacs の目指すところと噛み合っていたように思います。 エディタの拡張においては、既存のコマンドやその内部実装に手を入れることなく、ある処理の文脈だけを少し変更したい、という要求が頻繁に現れます。Emacs Lisp では、こうした要求をダイナミックスコープによって自然に満たすことができました。 よく知られている例が、検索時の大文字・小文字の区別を制御する case-fold-search という変数です。この変数を let によって一時的に束縛するだけで、その内部で呼ばれる標準の検索コマンド群の挙動をまとめて変更できます。 ( defun my-case-sensitive-search ( keyword ) ( let (( case-fold-search nil )) ( search-forward keyword ))) 文脈伝播（Context Propagation） プログラミング言語全体に立ち返れば、前述の通り主流となったのはレキシカルスコープでした。関数の振る舞いが呼び出し元の状態に依存する性質は、大規模化・複雑化するソフトウェア開発において、扱いが難しかったためです。 レキシカルスコープがコードの予測可能性をもたらした一方で、アプリケーション開発には別の課題が残されました。文脈の伝播（Context Propagation）です。 Webアプリケーションを例にとれば、認証情報やトレーシングIDなどの情報は、処理の開始から終了まで、あらゆる階層の関数で参照したくなる横断的な関心事 5 です。レキシカルスコープでナイーブに実装すると、すべての関数にバケツリレーで渡さなければならず、中間層は不要な責務を負うことになります。 この明示的な記述の煩雑さを避けるため、言語仕様の外側でダイナミックスコープ的な挙動を実現する仕組みが実用化されてきました。Java における ThreadLocal がその代表例です。言語レベルでは静的なスコープによる安全性を選びつつも、ランタイムで暗黙的に文脈を引き継ぐ機構が初期から用意されていました。 ここからしばらく、現代のプログラミング言語で文脈伝播がどう実現されているかを見ていきたいと思います。 各節の細部を追わなくても、明示的に渡すアプローチと暗黙的に伝播させるアプローチがそれぞれ存在する、という雰囲気だけ掴んでもらえれば十分です。 Go の context パッケージ まずは明示的に文脈を渡す例として Go を見てみます。Go では context.Context を関数の第一引数として渡す規約が確立されており、キャンセル処理やタイムアウト、リクエストスコープの値を伝播させます。 func HandleRequest(w http.ResponseWriter, r *http.Request) { ctx := r.Context() traceId := generateTraceID() ctx = context.WithValue(ctx, traceIdKey, traceId) result, err := processOrder(ctx, orderId) // ... } func processOrder(ctx context.Context, orderId string ) (*Order, error ) { // 中間層も ctx を受け取り、下位に渡す return repository.FindOrder(ctx, orderId) } func (r *Repository) FindOrder(ctx context.Context, orderId string ) (*Order, error ) { traceId := ctx.Value(traceIdKey).( string ) r.logger.Info( "finding order" , "traceId" , traceId, "orderId" , orderId) // ... } 文脈が引数として明示されるため、関数シグネチャを見ればその関数が文脈を必要とすることが分かります。 しかし、 context.WithValue で渡される値については事情が異なります。 ctx に何が入っているかはシグネチャからは分からず、実行時に ctx.Value(key) で取り出すまで不明です。つまり、 context.Context という引数は明示的に渡されていますが、その中身へのアクセスはキーによる動的な参照になっています。 では、型によってこの暗黙性を解消する方法はあるのでしょうか。 Reader Monad 関数型プログラミングの世界では、この課題に対する手法として Reader Monad が知られています。 Reader Monad の本質は単純です。環境 R を受け取って値 A を返す関数 R => A を、合成可能な形で扱えるようにしたものです。Scala で書いてみましょう。 case class Reader[R, A](run: R => A) { def map[B](f: A => B): Reader[R, B] = Reader(r => f(run(r))) def flatMap[B](f: A => Reader[R, B]): Reader[R, B] = Reader(r => f(run(r)).run(r)) } これで環境に依存する計算を合成可能な形で表現できます。さきほどの例を Reader Monad で実装します。 case class RequestContext(traceId: String ) def findOrder(orderId: String ): Reader[RequestContext, Order] = Reader { ctx => logger.info(s "finding order: traceId=${ctx.traceId}, orderId=$orderId" ) repository.find(orderId) } def processOrder(orderId: String ): Reader[RequestContext, Result] = for { order <- findOrder(orderId) result <- validateAndProcess(order) } yield result def handleRequest(orderId: String ): Reader[RequestContext, Response] = for { result <- processOrder(orderId) } yield Response(result) // 実行時に環境を注入 val ctx = RequestContext(traceId = "abc-123" ) val response = handleRequest( "order-789" ).run(ctx) 関数のシグネチャに注目してください。 Reader[RequestContext, Order] という戻り値の型を見るだけで、この関数が RequestContext を必要とすることが分かります。必要な文脈が型レベルで明示されています。 また、for 内包表記により、環境の受け渡しを省略できます。 processOrder は findOrder を呼び出していますが、 ctx を渡すコードはどこにもありません。Reader の flatMap が環境を伝播してくれるからです。 この手法により、文脈の明示性と記述の簡潔さを両立できます。 Scala の context parameter このような書き方はよく使われるため、Scala では性質の近い機能が言語レベルでサポートされています。 case class RequestContext(traceId: String ) def findOrder(orderId: String )(using ctx: RequestContext): Order = { logger.info(s "finding order: traceId=${ctx.traceId}, orderId=$orderId" ) repository.find(orderId) } def processOrder(orderId: String )(using ctx: RequestContext): Result = { val order = findOrder(orderId) // ctx は暗黙的に渡される validateAndProcess(order) } def handleRequest(orderId: String )(using ctx: RequestContext): Response = { val result = processOrder(orderId) // ctx は暗黙的に渡される Response(result) } // 呼び出し側で given を定義 given ctx: RequestContext = RequestContext(traceId = "abc-123" ) val response = handleRequest( "order-789" ) // ctx は暗黙的に解決される using キーワードにより、コンパイラがスコープ内から適切な値を探して自動的に引数を補完します。中間層での明示的な受け渡しが不要でありながら、シグネチャには文脈が明示されています。 これは、レキシカルスコープの型安全性を維持しつつ、ダイナミックスコープが解決していたバケツリレー問題に対処する言語レベルの解答と言えます。 ただし、中間層の関数も (using ctx: RequestContext) をシグネチャに持つ必要があり、文脈の存在自体は伝播経路上のすべての関数に現れます。 ThreadLocal / AsyncLocalStorage ここまで見てきたのは、いずれも文脈を明示的に表現する手法でした。次に、暗黙的に文脈を伝播させる仕組みを見ていきます。 Java の ThreadLocal は JDK 1.2（1998年）で導入されました。ThreadLocal は、スレッドごとに独立した値を保持する仕組みです。 Webアプリケーションでは、1つのリクエストが1つのスレッドで処理される実行モデルが一般的でした。このモデルにおいて、リクエストスコープの情報（認証情報やトランザクションなど）を、引数で渡すことなく処理の流れ全体で共有する用途で ThreadLocal は広く使われてきました。 先ほどと同じ例を Java で書いてみましょう。 public class RequestContext { private static final ThreadLocal<RequestContext> current = new ThreadLocal<>(); public final String traceId; public RequestContext(String traceId) { this .traceId = traceId; } public static RequestContext current() { return current.get(); } public static <T> T runWith(RequestContext ctx, Supplier<T> block) { RequestContext previous = current.get(); current.set(ctx); try { return block.get(); } finally { current.set(previous); } } } public Order findOrder(String orderId) { var ctx = RequestContext.current(); logger.info( "finding order: traceId=" + ctx.traceId + ", orderId=" + orderId); return repository.find(orderId); } public Result processOrder(String orderId) { var order = findOrder(orderId); return validateAndProcess(order); } public Response handleRequest(String orderId) { var result = processOrder(orderId); return new Response(result); } // エントリーポイント var ctx = new RequestContext( "abc-123" ); var response = RequestContext.runWith(ctx, () -> handleRequest( "order-789" )); findOrder も processOrder も引数に文脈を持っていません。 RequestContext.current() を呼び出すだけで、呼び出し元で設定された値を取得できます。そして runWith のブロックを抜ければ、以前の値に戻ります。Perl の local が実現していた振る舞いと同じですね。 現在では非同期・並行処理が一般的になり、それらに対応した Java の ScopedValue（JDK 21〜、プレビュー）や、Node.js の AsyncLocalStorage が同様の機能を提供しています。これらは値のネストと復元が API に組み込まれており、ダイナミックスコープがコールスタックを遡って値を解決する仕組みにより近いものになっています。 React Context ここで少し視点を変えて、フロントエンドに目を向けてみましょう。 関数呼び出しの連鎖がコールスタックを形成するように、React ではコンポーネントの親子関係がツリー構造を形成します。そしてここでも、同じバケツリレー問題が現れます。 React では、親から子へデータを渡す際に props を使います。しかし、深くネストしたコンポーネントに値を届けるには、途中のすべてのコンポーネントが props を受け取って下に渡す必要があります。いわゆる props drilling です。 中間層のコンポーネントが自身では使わない props に依存することは、コンポーネントの再利用性を損ない、不要な再レンダリングの原因にもなります。React Context を使えば、Context で囲んだ範囲内のどの深さのコンポーネントからでも、中間層を経由せずに値を取得できます。 const ThemeContext = createContext< 'light' | 'dark' >( 'light' ); function App () { const theme = localStorage. getItem ( 'theme' ) ?? 'light' ; return ( < ThemeContext value = { theme } > < Header /> < Main /> < Footer /> </ ThemeContext > ); } function Main () { // Main は theme を知らない return < Sidebar /> ; } function Sidebar () { const theme = use(ThemeContext); // 中間層を飛び越えて取得 return < div className = { theme } > ... </ div > ; } Context のネストによって値を上書きでき、そのスコープを抜ければ外側の値に戻る。コンポーネントツリーという軸は異なりますが、これもダイナミックスコープの再発見と言えそうです。 侵襲を抑える ここまで見てきた通り、文脈伝播には万能の解決策がありません。 明示的に引数で渡せば、依存関係は明確になりコードの追跡も容易です。しかし、中間層が自身では使わない引数を知らなければならないという問題が残ります。暗黙的な伝播を使えば中間層の負担は消えますが、今度は依存関係が見えにくくなります。 このトレードオフに対して、別の軸から考えてみたいと思います。既存コードへの侵襲を抑える、という制約を置いた場合、ダイナミックスコープ的な振る舞いはどのように評価できるでしょうか。 現実のコードベースは往々にして理想通りにはなっていません。テストや文脈伝播の仕組みは必要だとわかっていても、スケジュールや優先度の都合で後回しにしたまま、コードが蓄積されてしまうことは起こりがちです。そこに手を入れるとき、引数で明示的に渡したり Reader Monad を導入するのが正攻法ですが、中間層をすべて修正するコストが見合わないこともあります。 以下では、ダイナミックスコープ的な仕組みの利用が、妥協ではあっても有効な選択肢になった例を具体的に見ていきます。いずれも呼び出し元の文脈に応じて値を差し替えたいという要求であり、これはまさにダイナミックスコープが解決していた問題です。実際に遭遇したケースを簡素化して紹介します。 あとからテストダブル たとえば、外部 API を直接呼び出している関数があり、テストを書きたいとします。理想的には依存性注入で差し替えられる設計になっているべきですが、現実にはそうなっていないコードも多いでしょう。 このとき、API クライアントを AsyncLocalStorage 経由で参照するように変更すれば、テスト時だけテストダブルを差し込むことができます。中間層の関数シグネチャを変更する必要はありません。 具体例を見てみましょう。 // 本番用の取得関数をデフォルト値として設定 const fetchCategoriesContext = new AsyncLocalStorage< ( ids : CategoryId []) => Promise < Category []> >( { defaultValue : defaultFetchCategories } ) function getFetchCategories () { const fetchCategories = fetchCategoriesContext.getStore() if (!fetchCategories) { throw new Error ( 'unreachable: defaultValue is set' ) } return fetchCategories } この getFetchCategories を利用してカテゴリを取得する関数を定義します。 export async function getCategory ( id : CategoryId ): Promise < Category | undefined > { const fetchCategories = getFetchCategories() const categories = await fetchCategories( [ id ] ) return categories[ 0 ] } テスト時にはテストダブルを差し込む関数を用意します。 /** * テスト時に fetchCategories を差し替えて実行する */ export async function withTestFetchCategories < T >( fetchCategories : ( ids : CategoryId []) => Promise < Category []> , body : () => T | Promise < T > ): Promise < T > { return fetchCategoriesContext.run(fetchCategories, body) } テストコードでは、 withTestFetchCategories のスコープ内でテスト対象を呼び出します。 getCategory を利用しているコードも、同じスコープ内で実行すればテストダブルが注入されます。 test ( 'カテゴリを取得できる' , async () => { const stubFetch = async ( ids : CategoryId []) => [ { id : ids[ 0 ], name : 'テストカテゴリ' } ] await withTestFetchCategories(stubFetch, async () => { const result = await getCategory( 'cat-1' ) expect (result?. name ).toBe( 'テストカテゴリ' ) } ) } ) あとからキャッシュ 先ほどのカテゴリデータの例の続きです。ひとつのリクエストを処理する中で getCategory が何度も呼ばれていることがわかりました。毎回バックエンドから取得せずに済むようにキャッシュを導入しましょう。 DataLoader を使えばキャッシュできますが、グローバルにキャッシュすると更新の反映やメモリ管理が複雑になります。そこでリクエスト単位でインスタンスを作ることにしました。具体的には、DataLoader をリクエストスコープで保持するために AsyncLocalStorage をもうひとつ追加します。 type CategoryDataLoader = DataLoader < CategoryId , Category | undefined > const categoryDataLoaderContext = new AsyncLocalStorage< CategoryDataLoader >() /** リクエスト単位で DataLoader を保持する */ export async function withCategoryDataLoader < T >( request : Request , body : () => T | Promise < T > ): Promise < T > { const loader = createCategoryDataLoader(request) return categoryDataLoaderContext.run(loader, body) } function createCategoryDataLoader ( request : Request ): CategoryDataLoader { const fetchCategories = getFetchCategories() return new DataLoader< CategoryId , Category | undefined >( async ( ids ) => fetchCategories(ids, request), { cache : true } ) } getCategory は DataLoader 経由で取得するように書き換えます。 function getCategoryDataLoader (): CategoryDataLoader { const loader = categoryDataLoaderContext.getStore() if (!loader) { throw new Error ( 'No categoryDataLoader in context' ) } return loader } // 利用側は DataLoader の存在を意識しない export async function getCategory ( id : CategoryId ): Promise < Category | undefined > { return getCategoryDataLoader().load(id) } リクエストを受けるエントリーポイントで withCategoryDataLoader を適用します。 export async function loader ( { request } : Route.LoaderArgs ) { return await withCategoryDataLoader(request, async () => { // この中で getCategory を呼び出す処理 } ) } これで、中間層の関数が DataLoader を引き回す必要はなく、リクエスト単位のキャッシュが有効になります。 あとから文脈伝播 実は上の例では、キャッシュだけでなく文脈伝播も実現しています。 fetchCategories の実装を見てみましょう。 async function defaultFetchCategories ( ids : readonly CategoryId [] , request : Request ): Promise <( Category | undefined )[]> { const response = await fetch (BACKEND_API, { method : 'POST' , headers : { 'Content-Type' : 'application/json' , 'X-Forwarded-For' : request. headers . get ( 'X-Forwarded-For' ) ?? '' , 'Cookie' : request. headers . get ( 'Cookie' ) ?? '' , } , body : JSON . stringify ( { ids } ), } ) return response.json() } withCategoryDataLoader に渡された request が DataLoader の生成時にキャプチャされ、バックエンドへのリクエスト時に cookie や X-Forwarded-For ヘッダを引き継いでいます。 getCategory を呼び出す側は、この伝播の仕組みを意識する必要がありません。 必要になったときに、コードの変更を最小に保ちながら、段階的に導入できる点がこのアプローチの利点です。 一方で、エントリーポイントで withCategoryDataLoader の適用を忘れると実行時エラーになる、という脆さがあります。依存関係が型に現れないため、コンパイル時には検出できません。これはダイナミックスコープ的な仕組みに共通する課題であり、トレードオフとしての慎重な検討が必要です。 おわりに React Context を説明していたときに、ダイナミックスコープの話をしたことがありました。それがこの記事のきっかけです。 歴史をたどりながら今の技術の位置づけを見直してみるのも、ときにはおもしろいものです。本稿からその一端でも感じていただければ幸いです。 一休では、技術を深く理解しながら、よりよいシステムをともに作っていくエンジニアを募集しています。 www.ikyu.co.jp まずはカジュアル面談からお気軽にご応募ください！ job.persona-ats.com ラムダ計算においては、ラムダ抽象 λx. M の本体 M に現れる変数のうち、λx によって束縛されているものを束縛変数、それ以外を自由変数と呼びます。 ↩ 古い Lisp の例を考えていたのですが Perl でも local で書けることを同僚が教えてくれました。 ↩ John McCarthy, History of Lisp (1978). "In modern terminology, lexical scoping was wanted, and dynamic scoping was obtained. I must confess that I regarded this difficulty as just a bug and expressed confidence that Steve Russell would soon fix it." ↩ 現在の Emacs Lisp ではレキシカルスコープを選択することが可能です。 ↩ 横断的関心事（cross-cutting concern）といえば2000年代に注目された AOP（Aspect Oriented Programming, アスペクト指向プログラミング）ですが、その主要なユースケースのひとつに文脈伝播の自動化がありました。ログ出力やトランザクションのコンテキストなどは、ThreadLocal 等の操作を裏側で隠蔽する典型的な例でした。 ↩

こんにちは。RevCommでフロントエンドエンジニアしているnobkzと申します。 はじめに 普段みなさんは、どのようなエディタをお使いでしょうか？私は普段から色んなエディタを使っていて、また色んなテキストエディタの実装を見ています。そこで、今回は、テキストエディタに関して重要な、テキストバッファの実装について見ていきましょう。 テキストバッファとは? そもそもテキストエディタとは何でしょうか？それは、テキストの情報を保持して、ユーザーの指示により内容を表示編集するプログラムです。 テキストバッファとは、　テキストエディタのテキストそのものを保持している場所であり、さまざまな機能が要求されます。 テキストバッファで特に重要な機能といえば、文字参照、挿入、削除です。 つまり、このcharAtやinsert、eraseの効率が重要になってきます。そのため、テキストバッファはこの効率のために、エディタごとに工夫したデータ構造をとっています。今回はそのようなテキストバッファのデータ構造を見ていきましょう。 テキストバッファのデータ構造 インターフェース 今回の記事では、TypeScriptで実装を紹介していきます。まず、簡単にテキストバッファを操作するためのインターフェースを定義してみましょう。今回は、TypeScriptを利用します。 type charAt < Buffer > = ( buffer : Buffer , pos : number ) => string ; type insert < Buffer > = ( buffer : Buffer , pos : number , char : string ) => Buffer ; type erase < Buffer > = ( buffer : Buffer , pos : number ) => Buffer ; 簡単なデータ構造によるテキストバッファ テキストバッファのデータ構造としてまず、簡単なデータ構造である配列やリストについて紹介して検討していきましょう。 配列をBufferにする まず、簡単にテキストを保持するデータ構造といえば、文字列型でしょう。文字列型は、言語によりますが基本的には文字の配列となっていることが多いでしょう。ここで配列とは、 文字の配列で、実際にTextBufferを実装してみます。JSには、さまざまな配列のメソッドが存在しますが、あえて配列のメソッドを使わず、わかりやすさのため配列の添字によるアクセス、代入によって実装してみます。 まずはデータ型の定義からですね。 type ArrayTextBuffer = { data : string [] , length : number ; capacity : number ; } ひとまず、stringの配列としてますが、1文字の配列だと考えてください。ここで、lengthはテキストの長さ、capacityは配列が確保している長さです。上記の図の例でいえば、lengthは7, capacityは10となります。 次に、charAtの実装をしてみましょう const arrayCharAt: charAt < ArrayTextBuffer > = ( buffer , pos ) => buffer.data[pos]; 文字参照は添字によって直接アクセスでき配列のサイズに依存しないので、計算量は となります。 次に、挿入と削除を実装してみましょう。以下のようになります。 const arrayInsert: insert < ArrayTextBuffer > = ( buffer , pos , char ) => { if (buffer. length === buffer.capacity) { buffer.capacity *= 2 ; const newData = new Array (buffer.capacity); buffer.data. forEach (( c , i ) => { newData[i] = c } ); buffer.data = newData; } for ( let i = buffer. length - 1 ; i >= pos ; i--) { buffer.data[i+ 1 ] = buffer.data[i]; } buffer.data[pos] = char; buffer. length ++; return buffer; } const arrayErase: erase < ArrayTextBuffer > = ( buffer , pos ) => { for ( let i = pos ; i < buffer. length; i++) { buffer.data[i] = buffer.data[i+ 1 ]; } buffer. length --; return buffer; } ; このように、挿入される場所から後の文字を1文字ずらして、文字を代入したり、削除は単純に1文字逆にずらして、実装します。このようにサイズが大きくなると、ずらす量も線形に増えて、計算量は、 となります。挿入においては、capacityとlengthが一致すると、バッファが満杯になっているので、バッファを2倍にしていることがわかると思います。 上記により配列をテキストバッファにすると、 文字参照は 挿入、削除は となり、小さなテキストだとこの実装で十分ですが、大きなテキストデータの挿入削除は非効率です。ただし、末尾に挿入や削除は になります。これが、後々Gab Bufferや、Piece Treeといったデータ構造に重要になってきます。 双方向リストをテキストバッファにしてみる 双方向リストをテキストバッファにしてみましょう。 データ型の定義は以下の通りになります。 type ListTextBuffer = { char : string , prev ?: ListTextBuffer , next ?: ListTextBuffer } | null ; // nullで空を表現 まず文字参照の実装をしてみましょう。実際には添え字の範囲外のエラーなどを出すべきですが、今回は簡単な実装に留めています。 const getNode = ( buffer : ListTextBuffer , pos : number ) => { let node = buffer; for ( let i = 0 ; i < pos ; i++) { node = node?. next ?? null ; } return node; } const listCharAt : charAt < ListTextBuffer > = ( buffer : ListTextBuffer , pos : number ) => { return getNode(buffer, pos)?.char || "" ; } 文字参照は、先頭から順番に参照を得ないといけないため、配列とは対照的に計算量は となります。 次に挿入と削除を実装しましょう。 const listInsert: insert < ListTextBuffer > = ( buffer : ListTextBuffer , pos : number , char : string ) => { const next = getNode(buffer, pos); const prev = next?.prev; const node : ListTextBuffer = { char , next , prev } ; if (next) { next.prev = node; } if (prev) { prev. next = node; } return buffer; } const listErase: erase < ListTextBuffer > = (buffer: ListTextBuffer, pos: number => { const targetNode = getNode(buffer, pos); const prev = targetNode?.prev; const next = targetNode?. next ; if (prev) { prev. next = next; } next.prev = prev; return buffer; } getNodeが現状の実装だと、 ですが、一旦それを無視してください。すると単につなぎかえるだけなので計算量が となります。 局所参照性 ところで、テキストエディタには局所参照性があります。局所参照性とは、メモリなどのリソースのアクセスが使用した部分の周辺が繰り返しアクセスされやすいという性質です。カーソル周りで編集がたくさんされやすいと考えればわかりやすいでしょう。テキストエディタの場合は、通常99%はシーケンシャルな参照 *1 らしいです。このような性質を前提としてテキストエディタは、データ構造を最適化して処理速度の向上が可能になります。 配列とリストの評価 さて、上記の getNode() の実装は簡単な実装に留めていましたが、実際にやるのであれば、このキャッシュしておくなどして、処理速度を効率化させて行くでしょう。 ここで、配列とリストについて評価をしていくと、配列はシンプルですが挿入や削除が です。一方でリストは文字参照が です。どちらも一長一短があります。局所参照性を考えると若干リストの方が良さそうに思えますが、他にも、実際のところ、1文字につきポインタが2つ必要になったりするのでメモリ使用量が増えたりなどの問題があります。 このような配列やリストの実装をベースとして他のバッファがこのようなパフォーマンスがどのように改善されていくか？みていきましょう。 行をリストで管理する 元々も、配列自体が挿入削除が となることわかります。このようになる原因はそもそも、テキスト全体一つの配列に詰め込んだからです。そうすると、テキスト全体を一つの配列ではなく区切って小さい単位に分けていこうとなるのは自然な発想となります。Software Tools *2 では、テキストエディタのバッファのデータ構造として、行単位で分けて、管理していました。 データ構造の定義は以下の通りになります。 type LineTextBuffer = { text : ArrayTextBuffer , prev ?: LineTextBuffer , next ?: LineTextBuffer } | null ; さて、文字参照、挿入削除。実装自体は省略します。(ぜひやってみてください）。文字参照は、Lが行数として、最初は となりますが、連続で同じ行をアクセスする場合は参照したい行が確定しているため となります。また、対象行の文字数をlと置くと、挿入削除は、最初は 、同じ行を編集するなら となります。配列やリストの管理を比較するとより、高速になったことがわかると思います。 こように行をリストで管理するのは、テキストエディタを実装としてよくみられます。VSCodeの最初の実装はこのような行単位管理による実装でした。ただし現在では後述するPieceTreeによって実装されます Gap Buffer 行単位でリスト管理する方法がある一方で、より局所参照の最適化を図ったデータ構造があります。それは、Gap Bufferです。Gap Bufferはemacsのテキストのデータ構造として利用されています。Gapバッファは、配列にGapつまり隙間があるデータ構造です。下の図のようはデータ構造になります。 データ構造を定義するなら以下のようになります。 type GapBuffer = { data : ArrayTextBuffer , capacity : number , gapStart : number , gapSize : number } まず文字参照をみていきましょう。 const gapBufferChartAt : charAt < GapBuffer > = ( buffer , pos ) => { if (pos < buffer.gapStart) { return buffer.data[pos]; } else { return buffer.data[pos+buffer.gapSize]; } } 文字参照は、gapStartの手前であれば、そのままposで参照し、超えていればgapSize+posで参照します。計算量は となります。 次に挿入や削除を実装してみましょう。動作のイメージは以下の通りです。 実装は以下のようになります。 const gapBufferInsert: insert < GapBuffer > = ( buffer , pos , char ) => { if (buffer.gapSize === 0 ) { buffer.gapStart = buffer.capacity; buffer.gapSize = buffer.capacity; buffer.capacity *= 2 ; const newData = new Array (buffer.capacity); buffer.data. forEach (( c , i ) => { newData[i] = c } ); buffer.data = newData; } while (pos !== buffer.gapStart) { const tmp = buffer.data[buffer.gapStart + buffer.gapSize - 1 ]; buffer.data[buffer.gapStart + buffer.gapSize - 1 ] = buffer.data[buffer.gapStart - 1 ]; buffer.data[buffer.gapStart - 1 ] = tmp; buffer.gapStart--; } buffer.data[pos] = char; buffer.gapSize--; buffer.gapStart++; return buffer; } const gapBufferErase: erase < GapBuffer > = ( buffer , pos ) => { while (pos !== buffer.gapStart) { const tmp = buffer.data[buffer.gapStart + buffer.gapSize - 1 ]; buffer.data[buffer.gapStart + buffer.gapSize - 1 ] = buffer.data[buffer.gapStart - 1 ]; buffer.data[buffer.gapStart - 1 ] = tmp; buffer.gapStart--; } buffer.gapSize++; buffer.gapStart--; return buffer; } さて、挿入は、gapSizeが0であれば、バッファが満杯なので、capacityを2倍にしていることがわかります。ArrayTextBufferの時と一緒ですね。そして、ギャップの最初の位置が一致するまで、ギャップをずらしています。削除の場合も、削除する位置にずらしています。ただし削除する場合は、配列からデータを消さずに、gapの位置だけずらして、文字参照から見えなくしているんですね。後述するデータ構造も、削除は実はデータ自体は保持されていますが、見えなくして削除しているデータ構造になっていることが多いです。さて、計算量について考えてみましょう。もしgapが一番後ろにあって、先頭に文字を挿入するならば、ほとんと配列と同様の操作となり になりますが、一方で、連続してテキストを編集するならば、ギャップをずらす必要がないため、 です。 gap bufferは非常に優秀なデータ構造で、これはテキストエディタの局所参照性を最大限に最適化したものと言えるでしょう。 PieceTable PieceTableは現在のVSCodeで利用されているPiece tree *3 の元となったデータ構造です。Pieceとは、断片という意味です。Piece Tableとは断片の表という意味ですが、ちょっと意味がわからないですよね。簡単に言えばPiece Tableとは、テキストの断片、つまり区間を表にしたデータ構造です。先ほどの行単位の管理のイメージを持つ人もいるとは思いますが、何が違うかと言えば、 編集区間 を表にしたと考えればわかりやすいかもしれません。 簡単にイメージしてみましょう。まず2つの配列バッファがあります。オリジナルバッファと、追記用のバッファです。オリジナルバッファは読み取り専用で、編集元のデータとなります。読み取り専用なので、このバッファ自体は変化しません。そして、追記用のバッファが、末尾に追加するだけのデータバッファで、編集でどんどん追記して大きくなっていきます。その2つのバッファとは別に、それぞれのテキストの区間を表す表があります。この区間の表は、順番があり、実際のテキストの順になるように作られています。 イメージとしては以下の通りです。 このイメージだと「吾輩はねLISPがすきである」という文章になります。オリジナルバッファの3番目の「猫」は表にないので、文章には入ってないことに注意してください。 さてデータ型を定義してみましょう。 type PieceTable = { originalData : ArrayTextBuffer , additionalData : ArrayTextBuffer , table : Piece [] } // startとendは閉区間にする type Piece = { bufferType : "original" | "additional" , start : number , end : number } さて文字参照を実装してみましょう。 const pieceTableCharAt : charAt < PieceTable > = ( buffer , pos ) => { const { offset , piece } = localPiece(buffer, pos); // pieceが見つからなかったらひとまず空文字を返しておく if (piece == null ) { return "" ; } return piece.bufferType == "original" ? arrayCharAt(buffer.originalData, piece.start + offset) : arrayCharAt(buffer.additinonalData, piece.start + offset); } // 閉区間なので長さは差分を取って+1 const pieceLen = ( p : Piece ) => p.end - p.start + 1 ; // 位置から、その位置を含むPieceとoffsetを取得する const localPiece = ( buffer : PieceTable , pos : number , ): { piece : Piece | null ; pieceIndex : number ; offset : number } => { if (pos < 0 ) return { piece : null , pieceIndex : - 1 , offset : 0 } ; let rem = pos; for ( let i = 0 ; i < buffer.table. length; i++) { const piece = buffer.table[i]; const len = pieceLen(piece); if (rem < len) return { piece , pieceIndex : i, offset : rem } ; rem -= len; } //　空テーブルの時など return { piece : null , pieceIndex : - 1 , offset : 0 } ; } ; Pieceの区間の処理をしないといけない分複雑になりましたね。さて、計算量はPieceの数に依存するので、Piecesの数を単純にPと置いて となります。ただし、この実装には含んでいませんが、部分を連続で参照する場合、発見したPieceを再活用できるため になります。 挿入削除を実装してみましょう。まず挿入のイメージですが以下になります。 つまり、編集したいPieceを発見して、分割して、その間に新しいPieceを挿入するということです。実装してみましょう。 const pieceTableInsert: insert < PieceTable > = ( buffer , pos , char ) => { // 追加バッファ末尾に1文字追加 const addPos = buffer.additionalData. length ; // 追加開始位置 arrayInsert(buffer.additionalData, addPos, char); const newPiece: Piece = { bufferType : "additional" , start : addPos, end : addPos } ; const { offset , piece , pieceIndex } = localPiece(buffer, pos); if (offset === 0 ) { // piece の先頭に挿入 = その前に newPiece を入れる buffer.table. splice (pieceIndex, 0 , newPiece); return buffer; } // pieceが見つからなかったらひとまず何もしないでおく if (piece == null ) { return buffer; } // piece を split して間に newPiece を挿入 // piece: [start .. end] (closed) // left: [start .. start+offset-1] // right: [start+offset .. end] const left: Piece = { bufferType : piece.bufferType, start : piece.start, end : piece.start + offset - 1 , } ; const right: Piece = { bufferType : piece.bufferType, start : piece.start + offset, end : piece.end, } ; buffer.table. splice (pieceIndex, 1 , left, newPiece, right); return buffer; } このように挿入の場合は、addtionalBufferに追加して、Pieceを分割して、新しいPieceを挿入すれば良いわけです。削除の場合は実装しませんが、こちらもPieceを発見して、分割、そして、Pieceのstartやendの位置を単にずらせばいいのですよね。Pieceが発見されてない場合は、 ですが、Pieceが発見されていて、newPieceに連続で編集する場合は、追記バッファの末尾の追加と、newPieceのendを増やせばいいだけになるので になります。削除も同様です。(削除は実装しないのでチャレンジしてみてください。） 上記の実装は簡単な実装であり、本来であれば、Pieceを合併したりする処理があるのですが、長くなるので割愛します。 Piece Tree さてVSCodeでは、Pieceの管理を、連続的な表ではなく、赤黒木で持つようにしました。その理由として、上記のPiece Tableの課題点として、編集が増えれば増えるほど、Pieceの数が増大し、探索がボトルネックになってきます。そこで、VSCodeでは、連続したTableとして持つのではなく、赤黒木としてPieceを持つようにしました。これがPiece Treeです。そのおかげで、文字参照の計算量は となりました。 Piece Treeの実装の方はやりません。（チャレンジしてみてもいいでしょう） 追記型の利点 Piece TableやPiece Treeは、このような性能のみならず、追記型であるがゆえに、編集履歴の管理にも強いと言う側面があります。なぜなら、バッファの追記のみで構成されるため、履歴管理には基本的には、Pieceの変更だけ追えば良いからです。 Rope さて、最近私はZed *4 を利用しています。Zedは共同編集やAIエディタなどを想定して、複数のユーザーから参照されると言う要件がでてきます。そのため、テキストバッファにRopeを採用しています。 RopeはPiece Treeと同様に大きな文字列を小さな断片に分け、それを木構造で保持するデータ構造です。Ropeは末端の葉は、文字の断片を表しますが、葉以外のノードは左部分木の文字数を示しています。イメージで言うと以下の通りです。 データ構造としては以下のようになります。今回、葉の設計がPiece Treeと同様の設計にしています。（一般的には、stringとして持つことが多いです。） type RopeNode = { kind : "node" ; weight : number ; left : RopeNode | RopeLeaf ; right : RopeNode | RopeLeaf ; } ; type RopeLeaf = { kind : "leaf" ; bufferType : "original" | "additional" ; start : number ; // closed end : number ; // closed } ; type RopeBuffer = { original : ArrayTextBuffer ; additional : ArrayTextBuffer ; root : ( RopeNode | RopeLeaf ) | null ; } ; 文字参照について簡単に実装してみましょう。動作イメージは以下の通りになります。 つまり、ノードと比較して、小さいなら左、大きいなら、右に進み、右に進むときに、調べる文字数を引けばいいのですね。 // 型ガード const isLeaf = ( x : RopeNode | RopeLeaf ): x is RopeLeaf => x.kind === "leaf" ; const leafLen = ( leaf : RopeLeaf ) => leaf.end - leaf.start + 1 ; const ropeCharAt: charAt < RopeBuffer > = ( buf , pos ) => { if (buf.root == null ) return "" ; if (pos < 0 ) return "" ; let node: RopeNode | RopeLeaf = buf.root; let i = pos; while ( true ) { if (isLeaf(node)) { if (i >= leafLen(node)) return "" ; const idx = node.start + i; return node.bufferType === "original" ? arrayCharAt(buf.original, idx) : arrayCharAt(buf.additional, idx); } // node は RopeNode に 좁まってる if (i < node.weight) { node = node.left; } else { i -= node.weight; node = node.right; } } } ; 木はバランスしている前提ならば、文字参照は高さに比例して （L は leaf 数）になります。 次に挿入や削除を見ていきましょう。Ropeの木の挿入と削除は、基本は split（分割） と concat（連結） の2つに落とし込めます。 split(tree, pos) : pos で木を左右の Rope に分割する concat(left, right) : 2つの Rope を連結する（新しいノードを作る） これができると、挿入は (L, R) = split(tree, pos) 追加バッファ末尾に char を追加し、それを指す leaf を作る tree' = concat(concat(L, newLeaf), R) 削除は (A, B) = split(tree, pos) (trash, C) = split(B, 1) （先頭 1 文字を落とす） tree' = concat(A, C) で表現できます。なので、今回はconcatとsplitのみ実装してみます。 const len = (t: (RopeNode | RopeLeaf) | null ): number => { if (t == null ) return 0 ; if (isLeaf(t)) return leafLen(t); return t.weight + len(t.right); } ; const concat = ( a: (RopeNode | RopeLeaf) | null , b: (RopeNode | RopeLeaf) | null , ): (RopeNode | RopeLeaf) | null => { if (a == null ) return b; if (b == null ) return a; return { kind : "node" , weight : len(a), left : a, right : b } ; } ; // split(t, pos) => [0..pos-1], [pos..end] const split = ( t: (RopeNode | RopeLeaf) | null , pos: number, ): [ (RopeNode | RopeLeaf) | null , (RopeNode | RopeLeaf) | null ] => { if (t == null ) return [ null , null ] ; if (pos <= 0 ) return [ null , t ] ; const tlen = len(t); if (pos >= tlen) return [ t, null ] ; if (isLeaf(t)) { const leftLen = pos; const leftLeaf: RopeLeaf = { kind : "leaf" , bufferType : t.bufferType, start : t.start, end : t.start + leftLen - 1 , } ; const rightLeaf: RopeLeaf = { kind : "leaf" , bufferType : t.bufferType, start : t.start + leftLen, end : t.end, } ; return [ leftLeaf, rightLeaf ] ; } if (pos < t.weight) { const [ l , r ] = split(t.left, pos); return [ l, concat(r, t.right) ] ; } else { const [ l , r ] = split(t.right, pos - t.weight); return [ concat(t.left, l), r ] ; } } ; これで挿入や削除は以下のように実装できます。 const ropeInsert: insert < RopeBuffer > = ( buf , pos , char ) => { // 追加バッファ末尾に 1 文字追加 const addPos = buf.additional. length ; arrayInsert(buf.additional, addPos, char); const newLeaf: RopeLeaf = { 　　... 略 } ; const [ L , R ] = split(buf.tree, pos); return { tree : concat(concat(L, newLeaf), R) } ; } ; const ropeErase: erase < RopeBuffer > = ( buf , pos ) => { const [ A , B ] = split(buf.tree, pos); const [ , C ] = split(B, 1 ); // 先頭 1 文字を捨てる return { tree : concat(A,C) } ; } ; 注意点として、今回は二分木の平衡を考慮していない実装です。実際にはそれなりに複雑になります。 木がバランスしている前提なら、こちらの計算量も、 となります。今回の実装には含まれていませんが、同じLeafに連続で編集する限り実装によりますが計算量は末端の葉のサイズをlと置いて となります。 Ropeと共同編集の容易性 さて、Ropeは、PieceTreeやGap Bufferと比較すると若干性能が悪いように見えます。しかしながら、Ropeは性能よりも共同編集に主眼を置いています。上記のデータ構造は、挿入も削除もよくみてみると、元の木のデータ構造を直接編集していません。concatは単に元ある木の結合ですし、splitも単に分割するだけで、直接木のに変更を加えていません。そして、削除や挿入はこのconcatやsplitを組み合わせて元にある木から、新しい木を構築しているだけなのです。 挿入と削除のイメージは以下になります。 つまり、Ropeは更新のたびに全体をコピーせず、変更が必要な部分だけを新しく作り、残りは共有するデータ構造になります。つまり、元のテキストを保持したまま、変更後のテキストを構築することができ、また、並行編集などを考えると、並行して複数のバージョンが持ちやすく、その結果、共同編集などの機能に強いデータ構造になっています。 さらに、Piece Tableと同様に履歴操作にも強いデータ構造になっていることがわかるかと思います。 まとめ 本記事では、テキストエディタの内部で使われるテキストバッファのデータ構造を、文字参照（charAt）・挿入（insert）・削除（erase）という観点で見てきました。 配列: charAt は常に O(1)。ただし insert/erase は後ろをずらすので O(N)。 速い参照の代償として編集が重い。 リスト: insert/erase は繋ぎ替え自体は O(1) だが、位置まで行く探索が O(N)。 編集は軽く“できる”が、そもそも目的地に辿り着くのが遅い。 行単位管理: 「全文字を1本に持つ」せいで O(N) になるなら、分割して局所化する。 → 参照・編集が “行数 + 行内” に落ち、現実の編集（同じ行を触り続ける）で効く。 Gap Buffer: 局所参照性（カーソル近傍を連続編集）を前提に、“そこだけO(1)” を作る。ギャップ移動は最悪 O(N) だが、連続編集は実質 O(1)。 Piece Table / Piece Tree: 文字列本体を動かさず、編集を“参照の断片（Piece）”として表現する。Piece が増えると探索が効くので、表（配列）→ 木（赤黒木）で O(P) → O(log P) にする（VSCode）。 Rope: 断片＋木で、split/concat に編集を還元する。変更は「必要な経路だけ作り直し、残りは共有」になり、履歴・複数ビュー・並行操作に自然に強い。 さまざまなテキストエディタのテキストバッファのデータ構造についてみていきました。普段、使っているエディタがどのような実装になっているかあまり気にしたことない方もたくさんいらっしゃるかもしれませんが、このようにさまざまなデータ構造の工夫がありとても面白いものとなっています。 また、ここまで書いてきましたが、テキストエディタの実装の話題ままだまだたくさんあり、たとえば、改行の管理や、カーソルの移動や、範囲選択、スクロール、折り返し、検索、共同編集などさまざまなことについてまだまだ深掘りできるところがあります。是非とも普段お使いのエディタについて探索してはいかがでしょうか？ *1 : https://www.cs.unm.edu/~crowley/papers/sds.pdf *2 : P.J. Kernighan, Brian W. Plauger Software Tools 1976 Addison-Wesley Professional 020103669X *3 : https://code.visualstudio.com/blogs/2018/03/23/text-buffer-reimplementation *4 : https://zed.dev/

これは株式会社LabBase テックカレンダー Advent Calendar 2025 12日目の記事です。 概要 学生時代から、論文などの議論の精読に対して、「絶対誰かがもう論理的な整合性を確かめたことあるんだろうな〜」と思い、その度に論理的な整合性の再確認に対してめんどくささを感じてきました。 本稿では形式意味論と定理証明支援系を利用して、あらゆる議論を形式化することで、これを打破することを目論みます。 もし自然言語が「コンパイル」できたら？ プログラミング言語では、コードを書くと同時にコンパイラや静的解析ツールが働き、文法ミスや型の不整合、論理的な破綻を検出してくれます。