0
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@mitsu389(mitsu 389)

sed の内部設計

0
Posted at

目次

1. 本記事の目的
2. ファイルの解説
3. 処理の流れ

 3.1. 最も大雑把な説明
 3.2. 少し丁寧な説明

  3.2.1. sed_cmd
  3.2.2. union x
  3.2.3. vector
  3.2.4. 改めて、少し丁寧な説明

 3.3. より詳細な説明

  3.3.1. compile.c
   3.3.1.1. 入力元の管理
   3.3.1.2. 文字単位の読み取り
   3.3.1.3. compile_program()
   3.3.1.4. next_cmd_entry()
   3.3.1.5. compile_address()
   3.3.1.6. ! の処理
   3.3.1.7. コマンドごとの解析

  3.3.2. execute.c
   3.3.2.1. process_files()
   3.3.2.2. read_pattern_space()
   3.3.2.3. execute_program()
   3.3.2.4. match_address_p()

4. 最後に

1. 本記事の目的

stream editor である sed は、フレキシブルなテキスト編集に重宝します。Qiita でもコマンドやオプションを整理して解説する記事や備忘録が多く見受けられ、エンジニアを中心に広く受け入れられていることがわかります。

しかし、内部でどのような処理を行っているかを解説する記事は、寡聞にして知りません。sed のソースコードは、GitHub で公開されていて、誰でも読むことができます。

この記事では、大雑把ではありますが sed の内部設計を見てみることにします。目的は以下のようになっています。

  1. 人のソースコードを読む練習
  2. 仕様を内部から知る練習

さて、前置きはここまでにして、実際に見てみましょう。

警告
筆者は初学者です。この記事には勘違いや語弊のある表現が含まれている可能性があることをご了承ください。あくまでも、大雑把な理解を目的としています。
また、この記事の執筆には、部分的に AI を使用しています。

2. ファイルの解説

sed のソースコードファイルをここで簡単に解説しておきます。この中で特に重要なのは、sed.c、compile.c、execute.c、sed.h です。今回の解説で、mbcs.c や debug.c などのサポートモジュールは出てきません。

ファイル 分類 主な役割
sed.c 入口・全体制御 main 関数を持つ GNU sed の入口。 コマンドライン引数、オプション、スクリプト指定、入力ファイル処理の開始を担当する。
compile.c コンパイル処理 sed スクリプトを読み取り、アドレス、コマンド、オペランドを解析して、 内部表現へ変換する。
execute.c 実行処理 コンパイル済み sed プログラムを入力ストリームに対して実行する。 pattern space / hold space の操作や各コマンドの実行処理を担当する。
sed.h 共有定義 GNU sed 内部で共有される構造体、列挙型、関数宣言などを定義する。 struct vector や struct sed_cmd などが特に重要。
regexp.c 正規表現処理 正規表現のコンパイルとマッチ処理を担当する。 正規表現アドレスや s コマンドの検索パターンで使われる。
mbcs.c マルチバイト文字処理 UTF-8 など、1文字が複数バイトで表される環境への対応を担当する。 文字境界やマルチバイト文字の判定に関係する。
debug.c デバッグ表示 --debug オプション用の表示処理を担当する。 コンパイル済み sed プログラムを人間が読める形で出力する。
utils.c 補助関数 ファイル操作、バッファ操作、エラー処理などの共通処理を提供する。 入出力やメモリ管理を追うときに参照する。
utils.h 補助関数の宣言 utils.c で定義される補助関数や終了コードなどを宣言する。
local.mk ビルド設定 sed 本体を構成するソースファイルやヘッダファイルを列挙する Makefile 断片。

3. 処理の流れ

3.1. 最も大雑把な説明

sed が実行されると、まずsed.c の main 関数に入ります。その後、 compile.c でスクリプトのパースが行われます。パースが成功すると、execute.c がコマンドを実行し、処理を終了します。

3.2. 少し丁寧な説明

処理をもう少し具体的に見ていく上で、個人的に重要だと思う構造体をいくつか見ておきましょう。どちらも sed.h で定義されています。

3.2.1. sed_cmd

この構造体は、スクリプト中の 1 コマンドを保持するためにあります。

sed_cmd のソースコード
sed.h
struct sed_cmd {
  struct addr *a1;	/* save space: usually is NULL */
  struct addr *a2;

  /* See description the enum, above.  */
  enum addr_state range_state;

  /* Non-zero if command is to be applied to non-matches. */
  char addr_bang;

  /* The actual command character. */
  char cmd;

  /* auxiliary data for various commands */
  union {
    /* This structure is used for a, i, and c commands. */
    struct text_buf cmd_txt;

    /* This is used for the l, q and Q commands. */
    intmax_t int_arg;

    /* This is used for the {}, b, and t commands. */
    idx_t jump_index;

    /* This is used for the r command. */
    struct readcmd readcmd;

    /* This is used for the hairy s command. */
    struct subst *cmd_subst;

    /* This is used for the w command. */
    struct output *outf;

    /* This is used for the R command.
       (despite the struct name, it is used for both in and out files). */
    struct output *inf;

    /* This is used for the y command. */
    unsigned char *translate;
    char **translatemb;

    /* This is used for the ':' command (debug only).  */
    char* label_name;
  } x;
};
メンバ 意味
a1 第1アドレス。アドレス指定がない場合は NULL になり得る。
a2 第2アドレス。1,3p のような範囲指定で使われる。
range_state 2アドレス範囲が現在有効かどうかを表す状態。
addr_bang コマンドを一致しない行にも適用する場合に、0 以外。つまり、'!' フラグ。
cmd 実際の sed コマンド文字。たとえば 'p', 'd', 's' など。
union x コマンド固有データ。コマンドごとに異なる追加的な情報を保持するための共用体。
補足情報（union x は下記詳述）

struct addr *a1, *a2

sed.h
struct addr {
  enum addr_types addr_type;
  intmax_t addr_number;
  intmax_t addr_step;
  struct regex *addr_regex;
};

enum addr_state range_state

sed.h
enum addr_state {
  RANGE_INACTIVE,	/* never been active */
  RANGE_ACTIVE,		/* between first and second address */
  RANGE_CLOSED		/* like RANGE_INACTIVE, but range has ended once */
};

enum addr_types

sed.h
enum addr_types {
  ADDR_IS_NULL,		/* null address */
  ADDR_IS_REGEX,	/* a.addr_regex is valid */
  ADDR_IS_NUM,		/* a.addr_number is valid */
  ADDR_IS_NUM_MOD,	/* a.addr_number is valid, addr_step is modulo */
  ADDR_IS_STEP,		/* address is +N (only valid for addr2) */
  ADDR_IS_STEP_MOD,	/* address is ~N (only valid for addr2) */
  ADDR_IS_LAST		/* address is $ */
};

3.2.2. union x

union x のソースコード
sed.h
union {
    /* This structure is used for a, i, and c commands. */
    struct text_buf cmd_txt;

    /* This is used for the l, q and Q commands. */
    intmax_t int_arg;

    /* This is used for the {}, b, and t commands. */
    idx_t jump_index;

    /* This is used for the r command. */
    struct readcmd readcmd;

    /* This is used for the hairy s command. */
    struct subst *cmd_subst;

    /* This is used for the w command. */
    struct output *outf;

    /* This is used for the R command.
       (despite the struct name, it is used for both in and out files). */
    struct output *inf;

    /* This is used for the y command. */
    unsigned char *translate;
    char **translatemb;

    /* This is used for the ':' command (debug only).  */
    char* label_name;
} x;
メンバ 主に対応するコマンド 役割
cmd_txt a, i, c 追加・挿入・変更するテキストを保持する。
int_arg l, q, Q 数値引数を保持する。
jump_index {}, b, t ジャンプ先のコマンド位置を保持する。
readcmd r 読み込み対象ファイルなどの情報を保持する。
cmd_subst s 置換コマンドの正規表現、置換文字列、フラグなどを保持する。
outf w 書き込み先ファイルの情報を保持する。
inf R 読み込み用ファイルの情報を保持する。
translate y 1バイト文字用の変換表を保持する。
translatemb y マルチバイト文字用の変換情報を保持する。
label_name : ラベル名を保持する。デバッグ表示で使われる。

3.2.3. vector

この構造体は、struct sed_cmd の動的配列です。

sed.h
struct vector {
  struct sed_cmd *v;	/* a dynamically allocated array */
  idx_t v_allocated;	/* ... number of slots allocated */
  idx_t v_length;	/* ... number of slots in use */
};
メンバ 役割
sed_cmd *v コマンド配列の先頭
v_allocated 確保済みのスロット数
v_length 実際に使用中のコマンド数

この構造体を図示すると、こういうことです。

struct vector
  ├── v[0] = struct sed_cmd
  ├── v[1] = struct sed_cmd
  ├── v[2] = struct sed_cmd
  └── ...
なぜ、v_allocated と v_length は分かれているのか なぜ、`v_allocated` と `v_length` は分かれているのでしょうか。それは、コマンドの個数だけ `sed_cmd` を確保しているわけではないためです。 領域の確保は、`compile.c` の `next_cmd_entry()` で行われています。
compile.c
static struct sed_cmd *
next_cmd_entry (struct vector *v)
{
  struct sed_cmd *cmd;

  if (v->v_length == v->v_allocated)
    v->v = xpalloc (v->v, &v->v_allocated, 1, -1, sizeof *v->v);

  cmd = v->v + v->v_length;
  cmd->a1 = NULL;
  cmd->a2 = NULL;
  cmd->range_state = RANGE_INACTIVE;
  cmd->addr_bang = false;
  cmd->cmd = '\0';	/* something invalid, to catch bugs early */

  return cmd;
}

xpalloc によって、確保される領域は、sed_cmd 1 つ分だけとは限らないため、v_allocated と v_length は一致しないケースがあるのです。

3.2.4. 改めて、少し丁寧な説明

さて、ここまで説明すると、3.1. 最も大雑把な説明に少し付け加えることができます。

compile.c で行っていることは、コマンドを一つずつ sed_cmd に格納し、それを vector に動的配列で保存することです。保存されたものは、execute.c に引き継がれ、実行されることになります。

3.3. より詳細な説明

では、ここまでの前提がわかったうえで、compile.c と execute.c の流れを追います。

3.3.1. compile.c

compile.c の主要な処理を以下に示します。

  1. sed スクリプトを読み込む
  2. アドレスを解析する
  3. コマンド文字を読む
  4. コマンドごとのオペランドを解析する
  5. struct sed_cmd に格納する
  6. ラベルやブロックのジャンプ先を後で解決する
  7. コンパイル済みプログラムを完成させる

特に重要な処理だけ、以下で解説します。

3.3.1.1. 入力元の管理

main 関数から compile.c にスクリプトを渡すときの入り口は 2 つに分かれています。compile_string() と compile_file() です。それぞれ、-e と -f に対応しています。
内部では、入力元を struct prog_info で管理しています。

compile.c
struct prog_info {
  const unsigned char *base;
  const unsigned char *cur;
  const unsigned char *end;
  FILE *file;
};

3.3.1.2. 文字単位の読み取り

compile.c に渡されたスクリプトは、文字単位で読み取られます。そのための関数が、いたるところで使用されることになります。
主要な関数は、以下のものです。

関数 役割
inchar() 次の1文字を読む
savchar() 1文字を戻す
in_nonblank() 空白を飛ばして次の文字を読む
read_end_of_cmd() コマンド末尾を確認する
in_integer() 数値を読む

3.3.1.3. compile_program()

compile.c の中心はこの関数です。
プログラム、または { ... } の中のサブプログラムを読み込み、コンパイル結果を vector に保存する関数です。かなり長い関数なので、ここで全体を見せることはしません。この関数がやっていることを単純化すると、以下のようになります。

while (まだ sed スクリプトが残っている) {
    空白やセミコロンを飛ばす
    次の sed_cmd のスロットを用意する
    アドレスを読む
    ! を読む
    コマンド文字を読む
    コマンドごとの引数を読む
    vector->v_length を増やす
}

3.3.1.4. next_cmd_entry()

次に追加する struct sed_cmd のスロットを返す関数です。v_length と v_allocated が一致したとき、つまり既に確保したスロットがコマンドで埋まった時、xpalloc() によって、領域が確保されます。

compile.c
next_cmd_entry (struct vector *v)
{
  struct sed_cmd *cmd;

  if (v->v_length == v->v_allocated)
    v->v = xpalloc (v->v, &v->v_allocated, 1, -1, sizeof *v->v);

  cmd = v->v + v->v_length;
  cmd->a1 = NULL;
  cmd->a2 = NULL;
  cmd->range_state = RANGE_INACTIVE;
  cmd->addr_bang = false;
  cmd->cmd = '\0';	/* something invalid, to catch bugs early */

  return cmd;
}

3.3.1.5. compile_address()

アドレス部分を処理します。入力がアドレスらしければ struct addr に保存して true を返し、アドレスでなければ何も読まずに false を返します。
以下のアドレスに対応します。

アドレス 内部的な扱い
/regex/ 正規表現アドレス
\cregexc 任意区切り文字の正規表現アドレス
数字 行番号アドレス
$ 最終行アドレス
first~step GNU 拡張の周期指定
+N, ~N 2番目のアドレス側で使う GNU 拡張

3.3.1.6. ! の処理

アドレスに一致しない行でコマンドを実行するために、struct sed_cmd の addr_bang のフラグを有効化する必要があります。

3.3.1.7. コマンドごとの解析

compile_program() の一番大きな部分です。switch (ch) によって、コマンドごとの解析処理に分岐します。。長いので、先頭部分だけ載せます。

compile.c
switch (ch)
{
    case '#':
        if (cur_cmd->a1)
          bad_prog ("comments don't accept any addresses");
        ch = inchar ();
        if (ch=='n' && first_script && cur_input.line < 2)
          if (   (prog.base && prog.cur==2+prog.base)
              || (prog.file && !prog.base && 2==ftell (prog.file)))
            no_default_output = true;
        while (ch != EOF && ch != '\n')
          ch = inchar ();
        continue;	/* restart the for (;;) loop */

    case 'v':
        /* This is an extension.  Programs needing GNU sed might start
        * with a 'v' command so that other seds will stop.
        * We compare the version and ignore POSIXLY_CORRECT.
        */
        {
        char *version = read_label ();
        char const *compared_version;
        compared_version = (*version == '\0') ? "4.0" : version;
        if (strverscmp (compared_version, PACKAGE_VERSION) > 0)
            bad_prog ("expected newer version of sed");

        free (version);
        posixicity = POSIXLY_EXTENDED;
        }
        continue;
...
}

3.3.2. execute.c

execute.c は、入力を読み、変換し、出力する部分を担当しています。

このファイル内で重要な構造体があります。
以下の struct line は、パターンスペースやホールドスペースのための構造体です。

execute.c
struct line {
    char *text;
    char *active;
    idx_t length;
    idx_t alloc;
    bool chomped;
    mbstate_t mbstate;
};

3.3.2.1. process_files()

main 関数からの入り口は、process_files() です。これは、コンパイル済み sed プログラムを、入力ファイル群に適用する関数です。

process_files() のソースコード
execute.c
/* Apply the compiled script to all the named files. */
int
process_files (struct vector *the_program, char **argv)
{
  static char dash[] = "-";
  static char *stdin_argv[2] = { dash, NULL };
  struct input input;
  int status;

  line_init (&line, NULL, INITIAL_BUFFER_SIZE);
  line_init (&hold, NULL, 0);
  line_init (&buffer, NULL, 0);

  input.reset_at_next_file = true;
  if (argv && *argv)
    input.file_list = argv;
  else if (in_place_extension)
    panic (_("no input files"));
  else
    input.file_list = stdin_argv;

  input.bad_count = 0;
  input.line_number = 0;
  input.read_fn = read_always_fail;
  input.fp = NULL;

  status = EXIT_SUCCESS;
  while (read_pattern_space (&input, the_program, false))
    {
      if (debug)
        {
          debug_print_input (&input);
          debug_print_line (&line);
        }

      status = execute_program (the_program, &input);
      if (status == -1)
        status = EXIT_SUCCESS;
      else
        break;
    }
  closedown (&input);

#ifdef lint
  /* We're about to exit, so these free()s are redundant.
     But if we're running under a memory-leak detecting
     implementation of malloc(), we want to explicitly
     deallocate in order to avoid extraneous noise from
     the allocator. */
  release_append_queue ();
  free (buffer.text);
  free (hold.text);
  free (line.text);
  free (s_accum.text);
#endif /* lint */

  if (input.bad_count)
    status = EXIT_BAD_INPUT;

  return status;
}

この関数は、read_pattern_space() で入力を読み、そのたびに execute_program() を呼ぶ構造になっています。

3.3.2.2. read_pattern_space()

この関数が、次の入力行を pattern space に読みます。
通常は、一行読むごとに pattern space をリセットして次の行を読みます。一方、N コマンドでは append = true となって通常とは異なる動作になります。
また、a, r, R の遅延出力もここで行います。

read_pattern_space() のソースコード
execute.c
static bool
read_pattern_space (struct input *input, struct vector *the_program, int append)
{
  if (append_head) /* redundant test to optimize for common case */
    dump_append_queue ();
  replaced = false;
  if (!append)
    line.length = 0;
  line.chomped = true;  /* default, until proved otherwise */

  while ( ! (*input->read_fn)(input) )
    {
      closedown (input);

      if (!*input->file_list)
        return false;

      if (input->reset_at_next_file)
        {
          input->line_number = 0;
          hold.length = 0;
          reset_addresses (the_program);
          rewind_read_files ();

          /* If doing in-place editing, we will never append the
             new-line to this file; but if the output goes to stdout,
             we might still have to output the missing new-line.  */
          if (in_place_extension)
            output_file.missing_newline = false;

          input->reset_at_next_file = separate_files;
        }

      open_next_file (*input->file_list++, input);
    }

  ++input->line_number;

  /* Do not allow a line number equal to INTMAX_MAX, as that represents
     overflow in address specs.  */
  if (input->line_number == INTMAX_MAX)
    bad_prog ("line number overflow");

  return true;
}

3.3.2.3. execute_program()

コマンドを実行します。一番大事かもしれません。
内部的には、大きな switch 文です。コマンドによって処理が分岐し、それぞれ実行されます。

各コマンドの出力は、以下の部分で判断されています。

execute.c
if (!no_default_output)
    output_line(line.active, line.length, line.chomped, &output_file);
a コマンド

少し特殊なのは、a コマンドです。
'a' コマンドは、キューに積むことで一時的に退避しています。

execute.c
case 'a':
{
    struct append_queue *aq = next_append_slot();
    aq->text = cur_cmd->x.cmd_txt.text;
    aq->textlen = cur_cmd->x.cmd_txt.text_length;
}
break;

その後、read_pattern_space() の以下の処理で出力されます。

execute.c
  if (append_head) /* redundant test to optimize for common case */
    dump_append_queue ();

3.3.2.4. match_address_p()

アドレス一致のための関数です。
内部的には、enum addr_types で定義されたアドレスタイプによって処理を分岐しています。

sed.h
enum addr_types {
  ADDR_IS_NULL,		/* null address */
  ADDR_IS_REGEX,	/* a.addr_regex is valid */
  ADDR_IS_NUM,		/* a.addr_number is valid */
  ADDR_IS_NUM_MOD,	/* a.addr_number is valid, addr_step is modulo */
  ADDR_IS_STEP,		/* address is +N (only valid for addr2) */
  ADDR_IS_STEP_MOD,	/* address is ~N (only valid for addr2) */
  ADDR_IS_LAST		/* address is $ */
};

4. 最後に

今回の記事では、ソースコード全体の内、かなり内容を絞っています。私のような初学者が読むには重いコードですが、ここまでの前提知識があるとかなり読みやすくなると思います。

0
2
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?