UTF-8 エンコーディングのままでバッファ・ギャップ その2

前回のギャップ・バッファのギャップ移動を使って、 挿入・削除・置換を試してみます。挿入では、 現点にギャップを移動します。 ギャップのバイト数が挿入したい文字列のバイト数よりも大きくなるように適宜バッファを grow メソッドで長くします。 そして…

端末のスクロール機能を使った簡易版 refresh

xterm は ANSI 画面制御シーケンスに、 行削除 (\e[L) と行挿入 (\e[M) をもっています。 1 行だけでなくパラメータで行数を指定して、 複数の行を一度に削除したり挿入することもできます。 挿入するのは空行です。 さらに、 この 2 つを組み合わせることで…

EastAsianWidth 対応 wcwidth

Unicode Character Database の EastAsianWidth に対応する wcwidth です。 コード・ポイントに対する文字が、 端末上で必ず半角なら 1、 必ず全角なら 2 を返します。 フォントによって半角かもしれず、 全角かもしれないなら 3 を返します。文字幅情報は 2…

Terminfo 文字列ケーパビリティのパラメータ展開

Terminfo (5) ケーパビリティは、 様々な端末のエスケープ・シーケンスに柔軟に対応するために、 スタック計算機を組み込んであります。 それを使って、 パラメータを加工して、 望みの位置に望みの形式でパラメータを展開していきます。 そのスタック演算と…

AVL 木なロープもどきの改訂

4 年前に書いたロープに手を入れました。⇒ https://gist.github.com/tociyuki/10372481 avlrope.rb ⇒ AVL 木なロープもどき ⇒ Rope もどきの落ち穂拾い算法は同じです。 このロープの木は、 部分木に含まれている文字数による Weight 木になっていて、 木の…

ruby の SHARED String

Seeing double: how Ruby shares string values の内容に次の 4 点を追記しておきます。 リテラル文字列は SHARED です。 リテラル文字列へ束縛している String オブジェクトを破壊操作すると、 文字列実体であるバイト列を複製して書き込みます (copy-on-wr…

UTF-8 エンコーディングのままでバッファ・ギャップ

昨夜投稿したものの再投稿です。 更新しようとして操作ミスで削除してしまいました。ピュア Ruby で記述した Emacs 風のテキスト・エディタ Textbringer は、 Ruby の String オブジェクトをバッファ・ギャップにしています。 バッファ・ギャップの要点はギ…

Markdown ブロックの WikiWikiWeb 方式での書式変換 (その3)

先日の続きです。 葉ブロックの 2 行目以降の行では、 マーク・スタックを作らないため、 ブロック開始行用とは別に、 行頭の字下げを調べるメソッドを用意しています。 先日の setext ヘディングが開始行と同じレイアウトで下線行が字下げされているかどう…

Markdown ブロックの WikiWikiWeb 方式での書式変換 (その2)

WikiWikiWeb 方式で、 行単位でのマーク・スタックの変化から Markdown のブロック要素の入れ子構造の追跡を前回に試みました。 マーク・スタックを作るのは物理行単位とし、 すべての行でマーク・スタックを作っていたのですけど、 Markdown には空行とイン…

Onigmo の \G アンカーによる字句走査

ruby の組み込み正規表現オブジェクト Regexp には match メソッドが一つあるだけです。 このメソッドの第 1 引数に文字列を、 第 2 引数には検索開始位置を文字単位で指定します。 第 2 引数は省略可能でそのときはゼロを指定したことになります。 match メ…

StringScanner で戻り読みパターンが利用できない理由

添付ライブラリ strscan 0.7.0 ではパターンに戻り読みが使えません。 理由は簡単で、 次の引用箇所のように、 検索対象文字列に指定するアドレスに、 文字列先頭アドレス (S_PBEG マクロ) ではなくスキャン・ポインタに対応するアドレス (CURPTR マクロ) を…

Markdown ブロックの WikiWikiWeb 方式での書式変換

これまで書いた Markdown 書式変換器は、 John Gruber によるPerl によるリファレンス実装の入れ子認識法を参考にしていました。 そこでは、 ブロックを構成する一連の行の行頭マークを一つずつ削りながら下の行へと降りていき、 削り終えたら、 削り初めた…

再帰データ型宣言

プログラミング言語 Pascal の直系では、 ワン・パス・コンパイル対応のため、 定数・型・変数宣言を let* で、 手続き宣言を letrec* で処理する伝統があります。 ただし、 再帰データ型対応のため、 ポインタ型宣言だけが例外で、 POINTER TO IDENT のよう…

Wirth VM のアセンブラ改

Wirth VM はすべての命令の第一と第二オペランドに飛び先番地を記入します。 これまでは、 すべての命令にラベルを割り振ってみましたが、 行番号時代の BASIC のように、 どこが飛び先なのかわかりにくくなってしまっていました。 そこで、 これまで書いて…

左・右再帰と Wirth VM

一個以上の項目をコンマで区切った単純なリストを、 左再帰と右再帰のそれぞれで Yacc 風に記述してみましょう。 話を単純化するため、 item の FIRST 集合はコンマを含まず、 item の FOLLOW 集合と fold_left および foldright の FOLLOW 集合には重なりが…

型記述子ごとの Cheney Copying ゴミ集め (その 2)

C99

ペア・オブジェクトやベクタ・オブジェクトのようにヒープ空間に割り当てるオブジェクトの最小単位のことを LISP の慣例にならってセルと呼ぶことにします。 セルはゴミ集めの処理単位です。 コピー方式のゴミ集め Cheney Copy 算法では、 移動元 from 空間…

Oberon システムのゴミ集め

Oberon システムのゴミ集めは完全なマーク & 一括スイープ方式です。 ゴミ集めは協調型タスクとしてスケジュールされ、 ゴミ集め中に他のタスクのスタックは空なので、 全ロード済み MODULE のグローバル変数のポインタをルート・セットに選ぶだけで済んでい…

Oberon-07 のシンボル・ファイル

プログラミング言語 Oberon-07 は Modula 言語族に属し、 翻訳時環境の束縛対を永続化してシンボル・ファイルを作成する、 この言語族共通の機能を持ちます。 永続化の対象は、 翻訳単位である MODULE 宣言のトップ・レベルと、 そこから見える構造体フィー…

M. Adams 等の R6RS equal? の find 手続き

M. D. Adams, R. K. Dybvig, Efficient Nondestructive Equality Checking for Trees and Graphs, 2008 (以下、 ADAMS2008 と略す) の find 手続きについて。 結論は先送りで、 気になった点を備忘録として残しておきます。SRFI-85 で提案されて、 R6RS Sche…

Snapshot Isolation のおもちゃ・undo ログ MVCC 版

1ヶ月前に作ってみた「行持ち MVCC」では、 行ごとに並んでいる作業データの残骸を取り除くのにゴミ集めが必要になります。 一方、 同じ MVCC でも表単位での undo ログを利用すると、 ゴミ集めが不要になります。undo ログ方式もいくつか流儀があり、 ここ…

Packrat 解析器を Wirth VM で (その2)

以前の Ierusalimschy VM 用に作った Parsing Expression Grammar DSL の PEG モジュールを、 Packrat 化 Wirth VM でも利用できるようにします。 PEG モジュールは grammar モジュール関数のブロック中で、 Ruby の式を使って PEG を記述できるようにしてあ…

Packrat 解析器を Wirth VM で (その1)

感桁 PEG の字下げを扱える Packrat 解析器を作ってみようと試行錯誤しています。 まず、 以前、 Ierusalimschy VM で書いた Packrat 解析器を手直しすることを考えたのですが、 継続の取り回しが面倒で諦め、 その辺が単純化できる Wirth VM に乗り換えてみ…

Wirth VM の簡易アセンブリ

字下げ判定のための命令を Wirth VM に追加して動かしてみようと考えたのですが、 その前にアセンブリを作っておきます。 Wirth VM はすべての命令に成功時と失敗時の飛び先を記入するため、 飛び先をラベルで指定できないと修正が大変です。 さらに、 すべ…

Adams の字下げ文法による YAML 風構文 (その2)

絶対カラム位置で字下げを扱うようにすることで、 構文の生成規則が簡潔になる上、 変更しやすくなります。 昨日は YAML を尊重して、 ブロック・シーケンスで許している、 コンパクト形式と呼ばれている同一行でのブロック要素の入れ子をブロック・マッピン…

Adams の字下げ文法による YAML 風構文 (その 1)

YAML 1.2 の構文は、 下向き解析に属性文法を使って、 相続属性と合成属性で相対カラム幅を扱うことで、 字下げ情報を構文に落とし込んであります。 一方、 M. D. Adams Indentation-Sensitive Parsing for Parsec (2014) も、 下向き解析に属性文法で字下げ…

qp-trie

crit-bit 木は二分木です。 それの節で扱うビット数を増やして N 分木の基数木にすることが考えられます。 N 分木の基数木の節は一般に nil ばかりでほんの一部しか使わない疎な配列です。 そこで、 疎配列の実装の一つである P. Bagwell による array mappe…

Snapshot Isolation のおもちゃ・行持ち MVCC 版

前回のおもちゃはトランザクションごとに大域データを丸ごと局所データにコピーして隔離を実現しました。 今度のおもちゃは複数のバージョンをデータに混ぜる Multiversion concurrency control (MVCC) で隔離してみます。 バージョンの混ぜ方は様々で、 今…

AVL 木 その場書き換え版

赤黒木で左右の条件分岐を一つにまとめた方法を、 AVL 木でも試みてみます。 AVL 木は、 平衡因子が左右で反対称になっているため、 赤黒木ほど簡単に条件分岐を一つにまとめることができません。今回の AVL 木も、 親節への参照を持たない節を使います。 節…

赤黒木 その場書き換え版

赤黒木の平衡調整は、 綺麗に左右対称の記述になっています。 それを利用して、 crit-bit 木のように子への参照を 2 要素の配列にすることで、 左右の場合分けを一つにまとめることができます。 左をゼロの位置に、 右を 1 の位置に配置することにします。 …

crit-bit 木 (その2)

次のように、 crit-bit 木に含まれる最小値・最大値、 指定した値の一つ前・一つ後を求められるようにメソッドを追加します。 tree = Critbit::Tree.new ["xyz", "xyza", "xyze", "xy", "xya", "xye"].each {|k| tree.insert(k) } #=> ("xy" 17 (("xya" 21 "…