sedでのtailのシミュレート

# はじめに
## 背景
「ファイルのm行目～n行目を取得」といった目的には、head や tail が良く使われます。
が、テキスト加工の多機能ツールである sed でももちろんこなすことができます。
しかし、「ファイルの先頭n行」の head の代わりは、例えば10行分なら `sed -e 10q' で済むところ、「ファイルの末尾n行」の tail の代わりは意外と複雑です。
本記事では、この tail のシミュレートの方法と、sed に指定するコードの解説を行います。

## 環境
Ubuntu18.04 ( WSL1/Windows10 ) 上の GNU sed 4.4 で動作検証しています。
他のLinuxディストリビューションでも基本変わらないと思いますが、非GNUな sed のことは考えていないので、Mac 等で試す場合はご注意ください。

# 単純なtailのシミュレート
## 実現コード
では先に、実際に tail の動きを実現した sed のコードを示します。
以下、`tail -n 5` と同様に末尾5行のみを出力する場合の例です。

```shell-session:tail_-n_5のシミュレート
$ seq 100 | sed -n -e ':L' -e '${p;q}; N; 6,$D; bL'
96
97
98
99
100
```

このように、seq の出力の末尾5行 ( 96～100 ) のみにフィルタされて出力されていることが分かります。

なお、以降の解説の関係上 `-n` を付けていますが、無い方がコードは短くなります。

```shell-session:-n無しの別解
$ seq 100 | sed -e ':L' -e '$q; N; 6,$D; bL'
96
97
98
99
100
```

## sedの基本
sed の挙動を追うために、先に基本をおさらいしておきます。これは普通に sed の manページに載っていますし、[GNUのサイトのマニュアル](https://www.gnu.org/software/sed/manual/sed.html)を見ても良いです。

まず sed は、指定されたファイルを開いて、あるいは標準入力からデータを**パターンスペース**と呼ばれる内部領域に読み込んで行単位で処理しつつ、加工したデータを標準に出力するのが基本です。
その際、`-e` で指定したコマンド ( 複数可 ) で加工を行うのですが、全体としての動作は次のような疑似コードに従います。
なお、この動作は `-n` オプションの有無で変わります。

```txt:疑似コード
動作継続をonにする
入力スキップをoffにする
出力をoffにする
while 動作継続がon { # 無限ループ
  if -nオプション無し {
    出力をonにする
  }
  if 入力スキップがoff {
    if EOF {
      break # ループ脱出
    }
    パターンスペースに1行分の入力データを保存
  }
  入力スキップをoffにする
  { # コマンドブロック
    コマンドを順に処理し、それに応じてデータ加工・出力
  }
  コマンドブロック終了:
  if 出力がon {
    パターンスペースの内容を出力
  }
}
```

このループの各ステップを、sedでは**サイクル**と呼んでいます。

なお、プログラミング上ありがちな `while ( EOFでない ) { 処理 }` や `while ( データ入力成功 ) { 処理 }` というパターンになってないのは、途中で処理を終える `q` や、次回の入力をスキップする `D` といったコマンドがあるからです。

そして、`-e` で指定したコマンド群は、改行や `;` の区切り文字 ( 一部コマンドは `;` 区切り不可 ) で区切られ、個々のコマンドとして解釈されます。
※改行を混ぜたくない場合は、`-e コマンド1 -e コマンド2` と `-e` オプションを分ければ、改行区切りと同等の扱いになります。

個々のコマンドは、**アドレス**(省略可)、**コマンド本体**、**引数**(ない場合もある)の3要素で構成されます。
アドレスは、最後に入力した行が何行目かという行数条件や、入力データ ( パターンスペースの内容 ) が正規表現にマッチするかといった条件を指定できます。( 省略時は「無条件に処理」 )
例えば `5q1` というコマンドだと、アドレスが `5` ( 5行目のみ処理 )、コマンド本体が `q` ( 終了コードをセットし、動作継続をoffにし、コマンドブロックを抜ける )、引数が 1 ( `q`で指定する終了コード ) という構成になります。
なお、`アドレス{ コマンド本体; コマンド本体 }` のように、同一アドレスで複数コマンドをまとめるような構成も可能です。

ところで、アドレスでの行数条件は「先頭から何行目」という指定は可能ですが、「末尾から何行目」という指定はできません。末尾から、という意味でできるのは**最終行かどうか**だけです。
※「末尾から何行目」はデータを全て読み終わってからでないと判断できないため除外されているものと思われます。
これが、head のシミュレートと tail のシミュレートの難易度が違う原因となっています。

## コード解説
では、`tail -n 5` をシミュレートする `sed -n -e ':L' -e '${p;q}; N; 6,$D; bL'` についての解説です。

まずはコマンド部分を改行区切りにして並べなおしてみます。

```sed:改行区切りコード
#アドレス 本体 引数
         :    L
 $     {
         p
         q
       }
         N
6,$      D
         b    L
```

アドレスとして現れているのは、

* 最終行のみを指定する `$`
* 6行目～最終行の範囲を指定する `6,$`

コマンド本体としては、

* `p`  
  パターンスペースの内容を出力する
* `q`
  動作継続をoffにし、コマンドブロックを抜ける  
  ※結果として sed 全体の動作終了を引き起こす
* `N`  
  行を ( 基本の無限ループとは別に ) 入力し、パターンスペースに追記する
* `:`  
  ジャンプ先のラベル名を定義する ( 引数必須 )
* `b`  
  定義したラベルにジャンプ ( goto ) する  
  ※ラベル省略時はコマンドブロックを抜ける
* `D`  
  ( パターンスペースに複数行保存されている場合に ) 先頭行のみを削除する
  ※追加で、入力スキップon、出力offを行い、コマンドブロックを抜ける

とこれだけあります。
この中で、**gotoによりコマンドブロック内部でのループを可能にする`b`** や、**sed本体のループとは別に自前で入力を行う`N`**、**次サイクルでの読み込みを抑止する`D`**といった癖のあるコマンドを使っているのが難易度を上げている原因となっています。

では、本体の動作とコマンド部分を合わせた全体の動作を見てみます。

```txt:疑似コード(全体)
動作継続をonにする
入力スキップをoffにする
while 動作継続がon { # 無限ループ
  if 入力スキップがoff {
    if EOF {
      break # ループ脱出
    }
    パターンスペースに1行分の入力データを保存
  }
  入力スキップをoffにする
  { # コマンドブロック
     ラベルL:                           # :L
     if 最終行 {                        # ${ }
       パターンスペースの内容を出力        # p
       動作継続off、goto コマンドブロック終了 # q
     }
     1行読み込みパターンスペースに追加     # N
     if 6行目～最終行 {                  # 6,$
       パターンスペースの先頭行削除        # D
       入力スキップon
       goto コマンドブロック終了
     }
     goto ラベルL                       # bL
  }
  コマンドブロック終了:
}
```

…これだけ見てもまだ分かり難いかも知れません。
しかし、よくよく見て見ると 6行目～最終行であれば `D` による入力スキップonが入りますし、6行目以前でもラベルLを介したコマンドブロック内ループがありますので、**実は本体ループでの入力処理は1行目しか行われません**。

それを踏まえて処理内容を変形させると、次のようになります。

```txt:疑似コード(変形)
動作継続をonにする
while 動作継続がon { # 無限ループ
  if 読み込んだデータなし {
    パターンスペースに1行目の入力データを保存
  }
  while true { # コマンドブロック・ラベルLの無限ループ
     if 最終行 {
       パターンスペースの内容を出力
       動作継続をoffにする
       break   # コマンドブロックを抜ける
     }
     1行読み込みパターンスペースに追加
     if 6行目～最終行 {
       パターンスペースの先頭行削除
       break   # コマンドブロックを抜ける
     }
  }
}
```

このように、5行目まではひたすら行をパターンスペースにためる、6行目からは行追加と先頭行削除を行うことで、最新の5行を保持するという動作によって最後に「末尾5行を出力」という`tail -n 5`と同等の動作を実現していることが分かります。

# 応用:先頭N行と末尾M行を出力
## 概要
@suzuki-kei 氏の、[ファイルの先頭 N 行と末尾 M 行を取り出すワンライナー](/suzuki-kei/items/c136b27dd0db6b812124)でコメントした「sedのみで実現する方法」についても、応用ということで解説してみます。

コマンドは次の通りでした。

```shell-session:先頭10行出力後末尾3行を出力するsedコード
sed -n -e '1p;:L' -e '${p;q};h;n;2,10p;H;g;4,$D;bL'
```

よく見ると、上で解説した tail 実現コードと似たような部分があることが分かると思います。

## 追加要素
しかし、ここではまだ紹介していないコマンドが現れています。それを先に紹介します。

* `n`  
  `N`に似ているが、追加はせず、1行読み込んだ内容でパターンスペースを置き換える
* `h`  
  パターンスペースの内容でホールドスペースを置き換える
* `H`  
  パターンスペースの内容をホールドスペースに追加する
* `g`  
  ホールドスペースの内容でパターンスペースを置き換える

また、コマンドの動作の中に「ホールドスペース」という用語が現れました。
これは、加工を行うメインの領域であるパターンスペースとは別に、一時的にデータを保持できるもう1つの領域です。つまり、パターンスペースの内容を一時的にバックアップしておいて、後でパターンスペースに戻して利用するようなことが可能になり、動作の幅が大きく広がります。

## 解説
では、このコードの全体を見てみます。

```txt:疑似コード(全体)
動作継続をonにする
入力スキップをoffにする
while 動作継続がon { # 無限ループ
  if 入力スキップがoff {
    if EOF {
      break # ループ脱出
    }
    パターンスペースに1行分の入力データを保存
  }
  入力スキップをoffにする
  { # コマンドブロック
     if 1行目 {                         # 1
       パターンスペースの内容を出力        # p
     }
     ラベルL:                           # :L
     if 最終行 {                        # ${ }
       パターンスペースの内容を出力        # p
       動作継続off、goto コマンドブロック終了 # q
     }
     パターンスペースの内容でホールドスペース置き換え # h
     1行読み込みパターンスペース置き換え    # n
     if 2行目～10行目 {                  # 2,10
       パターンスペースの内容を出力        # p
     }
     パターンスペースの内容をホールドスペースに追加   # H
     ホールドスペースの内容でパターンスペース置き換え # g
     if 4行目～最終行 {                  # 4,$
       パターンスペースの先頭行削除        # D
       入力スキップon
       goto コマンドブロック終了
     }
     goto ラベルL                       # bL
  }
  コマンドブロック終了:
}
```

結局のところ、**本体ループで入力を行うのが1行目のみ**というところは変わっていません。
これを変形させてみます。

```txt:疑似コード(変形)
動作継続をonにする
while 動作継続がon { # 無限ループ
  if 読み込んだデータなし {
    パターンスペースに1行目の入力データを保存
    パターンスペースの内容を出力
  }
  while true { # コマンドブロック・ラベルLの無限ループ
     if 最終行 {
       パターンスペースの内容を出力
       動作継続をoffにする
       break   # コマンドブロックを抜ける
     }
     パターンスペースの内容でホールドスペース置き換え
     1行読み込みパターンスペース置き換え
     if 2行目～10行目 {
       パターンスペースの内容を出力
     }
     パターンスペースの内容をホールドスペースに追加
     ホールドスペースの内容でパターンスペース置き換え
     if 4行目～最終行 {
       パターンスペースの先頭行削除
       break   # コマンドブロックを抜ける
     }
  }
}
```

実は、単純に tail のシミュレートコードに、「1行目～10行目は都度出力」を追加しているだけなのですが、パターンスペースだけでは記憶領域が足りないので、ホールドスペースを都度利用している ( `N`で行追加する代わりに、`n`で読み込んだ後`H`でホールドスペース側で行追加 ) ということで、**よく読むとそんな複雑なことはしていない**ということが分かると思います。

# 終わりに
sedのマニュアルを眺めているだけだと動作がなかなか分かり難いかもしれませんが、一度全体の動作を追ってみると、sedで込み入った処理を行うのが楽になるのではないでしょうか。
ということで、tail をネタに解説してみました。是非実務含めたシェル芸にご活用ください。