天泣記

read_diff であるが、pipe でつないで diff を起動した後は、pipe からメモリに読み込んでいる。

diffutils-2.8.1/src/diff3.c:1220-1239

1220:   current_chunk_size = MAX (1, STAT_BLOCKSIZE (pipestat));
1221:   diff_result = xmalloc (current_chunk_size);
1222:   total = 0;
1223:
1224:   for (;;)
1225:     {
1226:       size_t bytes_to_read = current_chunk_size - total;
1227:       size_t bytes = block_read (fd, diff_result + total, bytes_to_read);
1228:       total += bytes;
1229:       if (bytes != bytes_to_read)
1230:         {
1231:           if (bytes == SIZE_MAX)
1232:             perror_with_exit (_("read failed"));
1233:           break;
1234:         }
1235:       if (PTRDIFF_MAX / 2 <= current_chunk_size)
1236:         xalloc_die ();
1237:       current_chunk_size *= 2;
1238:       diff_result = xrealloc (diff_result, current_chunk_size);
1239:     }

まぁ、pipe の block size になんの意味があるのかという疑問はあるが、ファイルを全部読み込めるまでバッファを倍々に増やしていくありがちなコードである。

#2 [diff3] process_diff の制御構造 [CODE blog]

process_diff では read_diff の結果をなめている。

diffutils-2.8.1/src/diff3.c:957-958,962-963,1042

957:   diff_limit = read_diff (filea, fileb, &diff_contents);
958:   scan_diff = diff_contents;

...

962:   while (scan_diff < diff_limit)
963:     {

...

1042:     }

#3 [diff3] process_diff の返り値 [CODE blog]

process_diff には return がひとつしかない。

diffutils-2.8.1/src/diff3.c:952,959,1046

952:   struct diff_block *block_list, **block_list_end, *bptr;

...

959:   block_list_end = &block_list;

...

1046:   return block_list;

その return は block_list を返しているが、block_list への言及は少ない。ってゆーか、一ヶ所で block_list へのポインタをとっているだけである。

block_list は struct diff_block へのポインタなので、block_list_end はポインタへのポインタということになる。

ポインタへのポインタで、list end という名前、とくれば、もう単方向リストを順に伸ばしていく感じが濃厚である。

struct diff_block を確認してみると、next フィールドが struct diff_block * なので、やはり単方向リストである。

diffutils-2.8.1/src/diff3.c:80-85

80: struct diff_block {
81:   lin ranges[2][2];             /* Ranges are inclusive */
82:   char **lines[2];              /* The actual lines (may contain nulls) */
83:   size_t *lengths[2];           /* Line lengths (including newlines, if any) */
84:   struct diff_block *next;
85: };

ちなみに、lin というのは ptrdiff_t らしい。行番号に ptrdiff_t をつかうのはなんでだろう?

diffutils-2.8.1/src/system.h:327

327: typedef ptrdiff_t lin;

リストに追加しているところは次のようなところになる。

diffutils-2.8.1/src/diff3.c:962-964,1040-1042

962:   while (scan_diff < diff_limit)
963:     {
964:       bptr = xmalloc (sizeof *bptr);

...

1040:       *block_list_end = bptr;
1041:       block_list_end = &bptr->next;
1042:     }

ループがひとまわりするたびにひとつ要素を付け加えている。

#4 [diff3] block_diff の読み込み [CODE blog]

あとはループの中身で bptr を埋めるのがわかれば、process_diff を理解した気になれる。

ただ、その前に、読み込む対象の例を見てみよう。

% cat f1
a
b
c
d
e
f
% cat f2
a
d
b
f
% diff --horizon-lines=100 -- f1 f2
2,3d1
< b
< c
5c3
< e
---
> b

この例からいくつかわかる。

・ 2,3d1 から
    □ f1 の 2-3行は f2 には無い、つまり削除 ([d]elete)
    □ f2 で対応する場所は 1行目の直後の行の間
・ 5c3 から
    □ f1 の 5行目が f2 の 3行目に変わる ([c]hange)
・ 行番号は 1-origin

struct diff_block を見直すと、ranges はふたつのファイル内での開始位置と終了位置を inclusive で示している、とある。さて、inclusive とすると、行がない場合、例でいえば削除後の位置とか、をどう表現するかが気になる。

diffutils-2.8.1/src/diff3.c:965-970,978-991,995,999,1007,1015,1017,1024,1032

965:       bptr->lines[0] = bptr->lines[1] = 0;
966:       bptr->lengths[0] = bptr->lengths[1] = 0;
967:
968:       dt = process_diff_control (&scan_diff, bptr);
969:       if (dt == ERROR || *scan_diff != '\n')
970:         {

...

978:         }
979:       scan_diff++;
980:
981:       /* Force appropriate ranges to be null, if necessary */
982:       switch (dt)
983:         {
984:         case ADD:
985:           bptr->ranges[0][0]++;
986:           break;
987:         case DELETE:
988:           bptr->ranges[1][0]++;
989:           break;
990:         case CHANGE:
991:           break;

...

995:         }

...

999:       if (dt != ADD)

...

1007:             scan_diff = scan_diff_line (scan_diff,

...

1015:       if (dt == CHANGE)

...

1017:           if (strncmp (scan_diff, "---\n", 4))

...

1024:       if (dt != DELETE)

...

1032:             scan_diff = scan_diff_line (scan_diff,

process_diff_control で 2,3d1 みたいな行を解釈し、979行目でその行末の改行を読み飛ばし、scan_diff_line で < b とかの行を読んでいるのであろう。

#5 [diff3] process_diff_control [CODE blog]

process_diff_control ではまず、SKIPWHITE と READNUM マクロを定義している。

diffutils-2.8.1/src/diff3.c:1065-1083

1065: static enum diff_type
1066: process_diff_control (char **string, struct diff_block *db)
1067: {
1068:   char *s = *string;
1069:   lin holdnum;
1070:   enum diff_type type;
1071:
1072: /* These macros are defined here because they can use variables
1073:    defined in this function.  Don't try this at home kids, we're
1074:    trained professionals!
1075:
1076:    Also note that SKIPWHITE only recognizes tabs and spaces, and
1077:    that READNUM can only read positive, integral numbers */
1078:
1079: #define SKIPWHITE(s)    { while (*s == ' ' || *s == '\t') s++; }
1080: #define READNUM(s, num) \
1081:         { unsigned char c = *s; if (!ISDIGIT (c)) return ERROR; holdnum = 0; \
1082:           do { holdnum = (c - '0' + holdnum * 10); }   \
1083:           while (ISDIGIT (c = *++s)); (num) = holdnum; }

うーむ。お子様お断り、ってコメントはどーなんですかねぇ。

まぁ、それはそれとして、SKIPWHITE は [ \t]* を読み飛ばし、 READNUM は [0-9]+ を読み飛ばすことがわかる。

diffutils-2.8.1/src/diff3.c:1085-1098

1085:   /* Read first set of digits */
1086:   SKIPWHITE (s);
1087:   READNUM (s, db->ranges[0][RANGE_START]);
1088:
1089:   /* Was that the only digit? */
1090:   SKIPWHITE (s);
1091:   if (*s == ',')
1092:     {
1093:       /* Get the next digit */
1094:       s++;
1095:       READNUM (s, db->ranges[0][RANGE_END]);
1096:     }
1097:   else
1098:     db->ranges[0][RANGE_END] = db->ranges[0][RANGE_START];

ふむ、ここまでで [ \t]*[0-9]+[ \t]*(,[0-9]+)? を読んでいる。数値は diff の結果の中の値がそのまま入り、数値がひとつしかない場合には、開始と終了両方がその値になる、というわけか。

diffutils-2.8.1/src/diff3.c:1100-1116

1100:   /* Get the letter */
1101:   SKIPWHITE (s);
1102:   switch (*s)
1103:     {
1104:     case 'a':
1105:       type = ADD;
1106:       break;
1107:     case 'c':
1108:       type = CHANGE;
1109:       break;
1110:     case 'd':
1111:       type = DELETE;
1112:       break;
1113:     default:
1114:       return ERROR;                     /* Bad format */
1115:     }
1116:   s++;                          /* Past letter */

ここでは [ \t]*[acd] を読んでいる。

diffutils-2.8.1/src/diff3.c:1118-1132

1118:   /* Read second set of digits */
1119:   SKIPWHITE (s);
1120:   READNUM (s, db->ranges[1][RANGE_START]);
1121:
1122:   /* Was that the only digit? */
1123:   SKIPWHITE (s);
1124:   if (*s == ',')
1125:     {
1126:       /* Get the next digit */
1127:       s++;
1128:       READNUM (s, db->ranges[1][RANGE_END]);
1129:       SKIPWHITE (s);            /* To move to end */
1130:     }
1131:   else
1132:     db->ranges[1][RANGE_END] = db->ranges[1][RANGE_START];

ここで読んでいるのは [ \t]*[0-9]+[ \t]*(,[0-9]+[ \t]*)? となる。

ぜんぶあわせると [ \t]*[0-9]+[ \t]*(,[0-9]+)?[ \t]*[acd][ \t]*[0-9]+[ \t]*(,[0-9]+[ \t]*)? となる。

diffutils-2.8.1/src/diff3.c:1134-1135

1134:   *string = s;
1135:   return type;

で、読み終わったらポインタを進める。進めた後は、まだ読んでいないところになるから、改行のところを指しているはずである。

#6 [diff3] process_diff_control から process_diff へ [CODE blog]

process_diff_control の呼び出しをもう一度見てみる。

diffutils-2.8.1/src/diff3.c:968-970,977-991,995

968:       dt = process_diff_control (&scan_diff, bptr);
969:       if (dt == ERROR || *scan_diff != '\n')
970:         {

...

977:           exit (EXIT_TROUBLE);
978:         }
979:       scan_diff++;
980:
981:       /* Force appropriate ranges to be null, if necessary */
982:       switch (dt)
983:         {
984:         case ADD:
985:           bptr->ranges[0][0]++;
986:           break;
987:         case DELETE:
988:           bptr->ranges[1][0]++;
989:           break;
990:         case CHANGE:
991:           break;

...

995:         }

やはり、まず読み飛ばしている改行は 2,3d1 とかの行の改行だった。

で、ADD や DELETE の場合は行番号をインクリメントしている。

ADD の場合は ranges[0][0]++ であるが、これは最初のファイルの開始行のインクリメントである。 ADD は最初のファイルになかったものが後のファイルに表れるというものだから、最初のファイルには対象となる行はない。そういうときに diff は (例には出さなかったが、DELETE のほうから類推できるように) 対象となる場所の直前の行番号が出てくる。なので、ranges[0][0] == range[0][1] で、そこにその行番号が入っている。で、インクリメントした結果、ranges[0][0] > ranges[0][1] で、開始行が終了行よりも大きくなる。

開始が終了よりも (ひとつ) 大きいのが空を意味するというのは、領域を inclusive で表現したときのやりかたである。まぁ、領域が空でないところから外挿するとそういう表現になるので、自然といえば自然なのではあるが、開始より終了が小さいというのは人間にとっては不自然気味である。個人的には対象とする状況においてよほどはっきりした利点がないかぎりは inclusive にはせず、終了をひとつ増やしておくことにしている。

inclusive に領域を表現する利点は、考えられなくはないのだが、diff3 で役に立つのはあるだろうか。あるとしたら範囲の扱いが開始方向と終了方向で対称になる、というあたりかな。

#7 [diff3] process_diff から scan_diff_line [CODE blog]

範囲を補整した後は、< b とかの行を読む。

まずは、dt != ADD という条件で元のファイルの内容である。 ADD のときは、元のファイルの領域は空なので、行はないはずである。

diffutils-2.8.1/src/diff3.c:997-1012

997:       /* Allocate space for the pointers for the lines from filea, and
998:          parcel them out among these pointers */
999:       if (dt != ADD)

1000:         {
1001:           lin numlines = D_NUMLINES (bptr, 0);
1002:           if (too_many_lines <= numlines)
1003:             xalloc_die ();
1004:           bptr->lines[0] = xmalloc (numlines * sizeof *bptr->lines[0]);
1005:           bptr->lengths[0] = xmalloc (numlines * sizeof *bptr->lengths[0]);
1006:           for (i = 0; i < numlines; i++)
1007:             scan_diff = scan_diff_line (scan_diff,
1008:                                         &(bptr->lines[0][i]),
1009:                                         &(bptr->lengths[0][i]),
1010:                                         diff_limit,
1011:                                         '<');
1012:         }

D_NUMLINES というのは以下のように定義されるマクロである。範囲を inclusive に定義したときの欠点のひとつが範囲の長さを求めるときに +1 しないといけないというところだが、ここではマクロに閉じ込めることによってその欠点に対処しているようだ。

diffutils-2.8.1/src/diff3.c:100-105

100: #define D_LOWLINE(diff, filenum)        \
101:   ((diff)->ranges[filenum][RANGE_START])
102: #define D_HIGHLINE(diff, filenum)       \
103:   ((diff)->ranges[filenum][RANGE_END])
104: #define D_NUMLINES(diff, filenum)       \
105:   (D_HIGHLINE (diff, filenum) - D_LOWLINE (diff, filenum) + 1)

too_many_lines というのはエラーチェックぽいのでとりあえず気にしないことにして、その次で行数だけの領域を確保している。

で、その次で行数だけ繰り返して scan_diff_line で行を読んでいる。

#8 [diff3] scan_diff_line [CODE blog]

scan_diff_line では、まず、leadingchar とスペースで行が始まっているかどうか検査している。さっきの呼出元では '>' を leadingchar として渡していたので、 "> " で始まっていることを検査していることになる。

diffutils-2.8.1/src/diff3.c:1286-1294

1286: static char *
1287: scan_diff_line (char *scan_ptr, char **set_start, size_t *set_length,
1288:                 char *limit, char leadingchar)
1289: {
1290:   char *line_ptr;
1291:
1292:   if (!(scan_ptr[0] == leadingchar
1293:         && scan_ptr[1] == ' '))
1294:     fatal ("invalid diff format; incorrect leading line chars");

次に、その "> " の次のところを *set_start に書き込んで呼出元に戻している。呼出元では &(bptr->lines[0][i]) だったから、最初のファイルの i番目の行の先頭である。

diffutils-2.8.1/src/diff3.c:1296

1296:   *set_start = line_ptr = scan_ptr + 2;

ふむ。そうすると、lines[0][i] は diff の結果全体を読み込んだ領域の途中を指すことになる。ということは、NUL terminate されてないよな、と思うと、そういえば引数の set_length や struct diff_block の lengths があって、ここではポインタと長さで文字列を扱っているわけだと考えられる。

その長さを求めるには行末を見つけないといけなくて、そのコードが次である。diffutils-2.8.1/src/diff3.c:1297-1298

1297:   while (*line_ptr++ != '\n')
1298:     continue;

これで行末が見つかった、と思うと、さにあらず。その次になんかコメントつきでいろいろ書いてある。

diffutils-2.8.1/src/diff3.c:1300-1321

1300:   /* Include newline if the original line ended in a newline,
1301:      or if an edit script is being generated.
1302:      Copy any missing newline message to stderr if an edit script is being
1303:      generated, because edit scripts cannot handle missing newlines.
1304:      Return the beginning of the next line.  */
1305:   *set_length = line_ptr - *set_start;
1306:   if (line_ptr < limit && *line_ptr == '\\')
1307:     {
1308:       if (edscript)
1309:         fprintf (stderr, "%s:", program_name);
1310:       else
1311:         --*set_length;
1312:       line_ptr++;
1313:       do
1314:         {
1315:           if (edscript)
1316:             putc (*line_ptr, stderr);
1317:         }
1318:       while (*line_ptr++ != '\n');
1319:     }
1320:
1321:   return line_ptr;

ふむ。最初に *set_length に書き込むのは想定の範囲内であるが、その次の if は何をしている? 行頭が \ だったとき?

あぁ、これはファイル終端が改行で終わってなかったときの話か。 diff の出力は行指向であるから、改行で終わっていない入力を与えられるとなかなか困る。行が改行で終わっているつもりで単に出力してしまうと、場合によっては出力が機械的に解釈できなくなってしまうことがあるからである。そういうとき、(GNU?) diff は改行を付け加えた後で、その改行は入力にはなかったということを示す印を次の行に出力する。その行が \ で始まるのである。たとえば、次のようなことになる。

% echo -n a > a
% echo -n b > b
% LANG=C diff a b
1c1
< a
\ No newline at end of file
---
> b
\ No newline at end of file

この \ があったら、というのが件の if であるとすると、 --*set_length で長さをひとつ短くして改行を抜き、 \ で始まった行を読み飛ばすというコードになっている。 edscript というのが気にならないでもないが、きっとこれは出力形式の都合で改行がない場合を扱えないのであろう。

あと、\ の 1文字だけじゃなくて No newline at end of file というメッセージまで含めて比較するほうがいいのではないかという気もするが、このメッセージは実は locale 依存なのでうまくないのであった。

% LANG=ja_JP.EUC-JP diff a b
1c1
< a
\ ファイル末尾に改行がありません
---
> b
\ ファイル末尾に改行がありません

#9 [diff3] 行末まで? [CODE blog]

そういえば、行末まで読む次のコードがあった。

diffutils-2.8.1/src/diff3.c:1297-1298

1297:   while (*line_ptr++ != '\n')
1298:     continue;

ここで、ファイル末尾のチェックをしていないのはいいのだろうか?

と、思い出してみると、read_diff に、ファイル末尾が \n でなかったらエラーというコードが入っていたのであった。

diffutils-2.8.1/src/diff3.c:1241-1242

1241:   if (total != 0 && diff_result[total-1] != '\n')
1242:     fatal ("invalid diff format; incomplete last line");

天泣記

2006-04-01 (Sat)

2006-04-02 (Sun)

2006-04-03 (Mon)

2006-04-06 (Thu)

2006-04-07 (Fri)

2006-04-08 (Sat)

2006-04-09 (Sun)

2006-04-10 (Mon)

2006-04-11 (Tue)

2006-04-12 (Wed)

2006-04-13 (Thu)

2006-04-18 (Tue)

2006-04-21 (Fri)

2006-04-22 (Sat)

2006-04-24 (Mon)

2006-04-25 (Tue)

2006-04-26 (Wed)

2006-04-27 (Thu)

2006-04-28 (Fri)

2006-04-30 (Sun)