windows でコマンドラインテキスト編集 - sed.js

# 要約

この記事では windows(cmd.exe) で使用できるストリームエディタ sed.js を紹介します。CUI でのテキスト処理は Unix like OS (以下 unix とする)では広く行われており、その利便性はよく知られています。ところが Windows では、GUI が重視されているため CUI でのテキスト処理は一般的とは言えず、標準の Windows ではそのような機能が一切提供されていません[^powershell]。そのような中で、技術者に支給される PC として、汎用性の観点から Windows が選択されることは多く、また支給された PC への任意のソフトウェアのインストールは原則として禁止されています。この問題を解決するために、Windows 標準の機能だけで作成・稼働可能なテキスト処理コマンド sed.js を作成しました。sed.js は、コマンドプロンプト上で sed.bat から呼び出されることで動作し、GNU sed とほぼ同等の機能を提供します。この記事では、一般的な sed の機能の確認と sed.js の実装の概要、一般に公開されている sed スクリプトを実行した結果について記述します。

[^powershell]: 一応 Powershell が存在しますが、使用感は Unix でのテキスト処理とは大きく異なり、利用目的も(多分)違います。

ソースは [github](https://github.com/asterisk9101/wincmd/blob/master/scripts/sed.js) で公開しています。sed.js の実行方法は[別の記事](http://qiita.com/asterisk9101/items/7da60f8c8859d6e4dffe)を参照してください。

# はじめに

[sed](https://ja.wikipedia.org/wiki/Sed_(%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF)) は、unix における代表的なテキスト処理コマンドです。sed は入力ストリーム(ファイル、またはパイプラインからの入力)を変換して出力するという、いわゆる[フィルター](https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%AB%E3%82%BF_(%E3%82%BD%E3%83%95%E3%83%88%E3%82%A6%E3%82%A7%E3%82%A2))として機能します。大きな特徴として、正規表現に対応しており様々な入力に対して柔軟な変換が可能である点が挙げられます。また sed スクリプトと呼ばれるスクリプト言語を使用することで、複雑な変換処理をスクリプト（ファイル）として保存することができます。

そのような利便性がある一方で、企業の技術者に支給される PC は windows が一般的であり、標準の状態では sed に類似するコマンドが存在しません[^edlin]。sed と同等の機能を提供するソフトウェアはいくつか存在する[^cygwin]ものの、一般的な企業では、支給された PC に任意のソフトウェアを導入することは禁止されています。このような現状に対して即効性があり、且つ有効な対処方法は知られていません[^unknown]。また、windows 7 以降の OS には、Powershell が標準のスクリプティング環境として搭載されていますが、以下のような点から sed の代替とするには適当ではありません。

[^edlin]: powershell を除くと、かつて EDLIN というコマンドが存在しましたが、64bit OS では利用できなくなりましたし、現在の OS で利用するにはいくつかの問題がありました。

[^cygwin]: cygwin, mingw など

[^unknown]: 教えてください。

- 汎用的なスクリプティング環境であるためテキスト処理の記述が冗長になりやすい。
- 既定ではファイルに保存したスクリプトを実行することができない。

そこで、windows における標準のスクリプティング環境である windows script host(cscript.exe) 上で動作するテキスト処理コマンドとして sed.js を作成しました。sed.js の実態はテキストファイルであるため、追加のソフトウェアをインストールすることなく作成から実行まで可能です。sed.js は GNU sed の機能を windows 上で再現することを目的として作成しており、unix 由来の ASCII テキストファイルと windows 上で作成したテキストファイルとを、同様に処理することができます[^charcode]。

[^charcode]: 文字コードは ASCII 互換でなければならない。マルチバイト UTF-8 は WSH で正常に読み取れない。

この記事では、テキスト処理ツールである sed を作成したことで分かったことと、sed.js の実装の詳細、sed スクリプトの実行検証、今後の課題などについて記述します。

# sed の特徴について

このセクションでは、一般的な sed の特徴について再確認します。

## sed の基本的な動作

sed は、入力ストリームから 1 行読み取ると、パターンスペースと呼ばれる領域に格納します。このとき改行は省略されます。そしてパターンスペースに格納された文字列は出力ストリームに流されます。このとき再び改行が付与されます。sed は入力ストリームが終端に達するまで、入力ストリームを読み取り、パターンスペースに格納し、パターンスペースを出力ストリームに流すサイクルを繰り返します。

## sed の命令

sed にはいくつかの命令を与えることができ、動作をコントロールすることができます。最もよく使われる命令は `s` です。`s` は、おそらく substitute(置換) の頭文字であり、パターンスペースに格納された文字列を置換します。その結果、出力される文字列は置換後の文字列になります。この命令は入力される全ての行に対して毎回適用されます。よく知られている命令を大別すると以下のような種類に分けることができます。

- 格納領域を操作するもの(h, H, g, G, x)
- パターンスペースの文字列を加工するもの(c, s, y, d, D)
- パターンスペースの入力と出力を行うもの(n, N, p, P)
- パターンスペースの文字列をファイルに出力するもの(w, W)
- その他の出力を行うもの(a, i, =, r, R)
- 命令をグループ化するもの({, })
- 命令の実行順序を制御するもの(b, t, T, q, Q)
- コメント(#)

前述の `s` など、いくつかの命令は引数をとることができ、命令に続けて `/regexp/replacement/` のように指定します。引数の構文は命令によって異なり、近年主流となっているプログラム言語と比較すると原始的な構文を持っています[^shutten]。

[^shutten]: 要出典

## アドレスの指定

ほとんどの命令は、アドレスと呼ばれる指定を行うことで、実行タイミング(命令を実行する行)を制御することができます。sed は行をパターンスペースに読み込むとアドレスを評価し、アドレスの示す条件が真であるときだけ命令を実行します。アドレスとしては数値を使って行番号を指定したり、正規表現にマッチする行を指定することもできます。また、数値と正規表現を組み合わせて範囲を指定したり、飛び飛びの行を指定することもできます。アドレスの構文は以下のようになります。

```bnf:syntax
<address>     := <number_addr>
              := <regexp_addr>
              := <step_addr>
              := <range_addr>
<number_addr> := [0-9]+
<regexp_addr> := '/' <string> '/'
<step_addr>   := <number_addr> '~' <number>
              := <regexp_addr> '~' <number>
<range_addr>  := <number_addr> ',' <number_addr>
              := <regex_addr> ',' <regex_addr>
              := <step_addr> ',' <number_addr>
              := etc.
```

この他に、ストリームの末尾を表す `$` や、否定を表す `!` があります。

## sed スクリプト

sed の命令は、スクリプトとして連続的に実行することができます。sed スクリプトは、以下のような文(statement)の集合で構成されます。

```bnf:sed_script
<statement>  := [<address>]<command>[<arguments>]
```
sed はテキストを行ごとに処理するため、そのスクリプトの構文は、どの行(address)に対して、どのような処理をするか(command, arguments) という形をとります。このうち`<address>` は省略可能で、省略すると入力された全ての行に対して `<command>` と `<arguments>` で指定された処理を施します。`<arguments>` は `<command>` に依って構文が変化し、場合によっては省略可能です。

## 命令のグループ化と制御命令

sed の命令には、複数の命令をグループ化するもの(`{`, `}`)と、命令の実行順序を制御するもの(`:`, `b`, `t`, `T`, ...)があります。これらの命令は、主にスクリプトを記述する際に利用されます。

グループ化された命令は、`{` に指定されたアドレスが真の場合にのみ実行されます。

命令の実行順序を制御する命令は、いわゆる `goto` であり、`:` で示されるラベルの箇所へ命令の実行位置を移します。この遷移に制限は無く、グループ化された命令の中から抜け出すことも、逆にグループ化された命令の中に入り込むことも可能です。

以下のスクリプトは、本来であれば入力の 10 行目だけが出力される(p命令)はずが、全ての行で label へ制御が移される(b命令)ため、全ての行が出力されます。

```sed
b label
10 {
   : label
   p
}
```

# 実装の概要

このセクションでは sed.js をどのように実装したかについて記述します。

sed.js は、一般的なスクリプト言語処理系と同様に、スクリプトを解釈して命令列を構築するコンパイラと、命令列を実行する仮想マシンから構成されます。

## コンパイラ

コンパイラは、与えられた sed スクリプトを解釈して命令列を構築します。通常、コンパイラは字句解析部と構文解析部に分かれます。しかし sed スクリプトは原始的な構文を持つため、構文を決定する前に字句を分割することが困難でした。そのためコンパイラは字句解析と構文解析を同時に行う関数として実装しました[^compiler]。これを `parser` 関数とします。`parser` 関数の簡略化した実装は以下のようになります。

[^compiler]: これによって文法の変更があった場合に、コンパイラの変更も大きくなるリスクが生じます。しかし sed は既に完成されているため問題はないと思われます。

```js:sed.js
var text = sed_script;
var at = 0;
var ch = text.charAt(at);

function statements() {
    var head, stat;
    head = statement();
    stat = head;
    while(/* statが生成される限り継続する */){
        stat.next = statement();
        stat = stat.next;
    }
    return head;
}
function statement() {
    var addr = address();
    var cmd = command();
    return new Statement(addr, cmd);
}
function address() {
    var addr;
    switch(ch) {
    case "/":       addr = new RegexAddr(/*正規表現をパースした文字列*/); break;
    case /* 0-9 */: addr = new NumberAddr(/*数値をパースした文字列*/); break;
    ...
    default: /* アドレス指定なし */ break;
    }
    return addr;
}
function command() {
    var cmd, name, args = [];
    name = ch; // sed コマンドの命令は 1 文字で表現される
    switch(name) {
    case /* コマンド */:
        args.push(/* name に応じた引数のパース */)
        break;
    ...
    default: error();
    }
    return new Command(name, args);
}
```

冒頭の変数 text, at, ch は、`parser` 関数全体で共有されており、それぞれ sed スクリプト全体を表す文字列、解析中の位置、解析中の1文字を格納します。続く 4 つの関数は引数なしで呼び出されていますが、解析位置を共有しているため sed スクリプト全体を順次解析していくことができます。

## 命令列のデータ構造

`parser` 関数は sed スクリプト全体を走査して命令列を構築します。命令列は連結リストとして実装し、連結リストの各要素は以下のようなデータ構造としました。

```text:連結リスト各要素のデータ構造
statement
|- next       ... 次の statement へのポインタ
|- address    ... address を表すオブジェクト
`- cmd        ... command を表すオブジェクト
   |- name    ... コマンド名を表す文字列
   `- args    ... arguments を表す配列
```

`address` オブジェクトには、いくつかの種類があります。それらは共通して、実行中の sed の状態(`sed_state`)を受け取り、`address` の表す条件に合致しているか判定する `match` メソッドを持ちます。後述する仮想マシンは `match` メソッドの判定に従って、`cmd` を実行するか決定します。

## 仮想マシン

sed 仮想マシン (命令評価器) は、コンパイラが生成した命令列を実行する部分です。仮想マシンは、簡単には以下のようなループを回すことによって、入力行ごとに命令列を実行します。

```js:sed.js
while(!stream.AtEndOfStream)
    read() // 入力行
    pc = stat_head; // 命令列（連結リスト）の最初の項目
    while(pc){
        if (match()) {
            exec();
        }
        next(); // 次の命令を読み出す関数
    }
    flush();
}
```

`pc` は、仮想マシンが次に実行する命令(statementオブジェクト)を保持します。仮想マシンは、まず `read()` によって新しい行をパターンスペースに読み込み、`pc` に最初の命令 `stat_head` をセットします。続いて `match()` によって `pc.addr` を評価し、結果が真の場合にだけ `exec()` を実行します。`exec()` は `pc.cmd.name` に応じて、適切な関数に `pc` を渡すディスパッチャーです。`exec()` は `pc` を書き換える場合があり、ラベルにジャンプする命令(b, t, T)は、`pc` の書き換えによって実現しています。

特殊な命令として `{` と `}` があります。この二つの命令に挟まれた命令はグループ化されます。グループ化された命令は、`{` に付属するアドレスにマッチしなければ実行されません。例えば、以下のような sed スクリプトでは、`i`, `p`, `a` 命令がグループ化されており、共通のアドレス(1,10)に従います。

```sed
1,10{
    i insert text
    p
    a append text
}
```

この機能を実現するために、仮想マシンは命令 `{` によって、次の命令 `pc.next` をスタックに積み上げて保存しておき、`pc.cmd.args[0]` を `pc` にセットします。仮想マシンは `pc.next` が `null` になるまで命令を実行し、最後にスタックから `pc.next` を取り出すことで元の命令列に戻ります。

# sed の動作検証

sed.js が実装できたことを確かめるために、[インターネットに公開されている sed スクリプト](http://quruli.ivory.ne.jp/document/sed_4.1.2/sed-ja_4.html)を使用して動作を検証しました。検証にあたって、スクリプトの修正する必要がありました。これは、sed.js の正規表現が、JScript の実装に依存するためです。主な修正点としては、以下の通りです。

- `()` を `\` でエスケープする必要がなくなった。
- 前方参照は '\' ではなく '$' を使用する必要がある。
- 改行コードは windows 標準の \r\n を使用した。

以下に、検証に使用したスクリプトを示します。以下の 3 つのスクリプトは期待通り動作し、sed.js に一般的な sed に相当する機能が正しく実装されていることが確かめられました。

## 行の中央揃え

以下のスクリプトは、文字列を幅 80 文字でセンタリングします。

```sed:centering.sed
# Put 80 spaces in the buffer
1 {
  x
  s/^$/          /
  s/^.*$/$&$&$&$&$&$&$&$&/
  x
}
# del leading and trailing spaces
y/	/ /
s/^ *//
s/ *$//
# add a newline and 80 spaces to end of line
G
# keep first 81 chars (80 + a newline)
s/^([\s\S]{81}).*$/$1/
# $2 matches half of the spaces, which are moved to the beginning
s/^(.*)\r\n(.*)\2/$2$1$2/
```

## 数字を増加させる

以下のスクリプトは、数値だけの行をインクリメントします。

```sed:increment.sed
/[^0-9]/ d

# replace all leading 9s by _ (any other character except digits, could
# be used)
:d

s/9(_*)$/_$1/; td

# incr last digit only.  The first line adds a most-significant
# digit of 1 if we have to add a digit.
#
# The tn commands are not necessary, but make the thing
# faster
s/^(_*)$/1$1/; tn
s/8(_*)$/9$1/; tn
s/7(_*)$/8$1/; tn
s/6(_*)$/7$1/; tn
s/5(_*)$/6$1/; tn
s/4(_*)$/5$1/; tn
s/3(_*)$/4$1/; tn
s/2(_*)$/3$1/; tn
s/1(_*)$/2$1/; tn
s/0(_*)$/1$1/; tn
:n
y/_/0/
```

## 行の文字を反転する

文字列を逆順に表示します。

```sed:reverse.sed
/../! b

# Reverse a line.  Begin embedding the line between two newlines
s/^.*$/\
$&\
/

# Move first character at the end.  The regexp matches until
# there are zero or one characters between the markers
tx
:x
s/(\r\n.)(.*)(.\r\n)/$3$2$1/
tx
# Remove the newline markers
s/\r\n//g
```

# おわりに

この記事では、一般的な sed の機能の確認と、sed.js の実装の紹介を行いました。また、 sed.js にて修正した既存の sed スクリプトを実行して動作を検証し、標準的な windows 環境で sed の機能が再現可能であることを示しました。
今後の課題として、いくつかの未実装命令(r, R, l)の実装と、非対応アドレス(n,~m など)の実装、正規表現の改修があります[^ato]。特に正規表現については、既存の sed スクリプトを流用する際の修正が多くなってしまったため、流用する際の修正が減るよう工夫したいと考えています。

[^ato]: あと、この記事が最後で息切れしているので文章力を鍛えたい