1/* comm -- compare two sorted files line by line.
2   Copyright (C) 1986, 1990-1991, 1995-2005, 2008-2010 Free Software
3   Foundation, Inc.
4
5   This program is free software: you can redistribute it and/or modify
6   it under the terms of the GNU General Public License as published by
7   the Free Software Foundation, either version 3 of the License, or
8   (at your option) any later version.
9
10   This program is distributed in the hope that it will be useful,
11   but WITHOUT ANY WARRANTY; without even the implied warranty of
12   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13   GNU General Public License for more details.
14
15   You should have received a copy of the GNU General Public License
16   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
17
18/* Written by Richard Stallman and David MacKenzie. */
19
20#include <config.h>
21
22#include <getopt.h>
23#include <sys/types.h>
24#include "system.h"
25#include "linebuffer.h"
26#include "error.h"
27#include "hard-locale.h"
28#include "quote.h"
29#include "stdio--.h"
30#include "memcmp2.h"
31#include "xmemcoll.h"
32
33/* The official name of this program (e.g., no `g' prefix).  */
34#define PROGRAM_NAME "comm"
35
36#define AUTHORS \
37  proper_name ("Richard M. Stallman"), \
38  proper_name ("David MacKenzie")
39
40/* Undefine, to avoid warning about redefinition on some systems.  */
41#undef min
42#define min(x, y) ((x) < (y) ? (x) : (y))
43
44/* True if the LC_COLLATE locale is hard.  */
45static bool hard_LC_COLLATE;
46
47/* If true, print lines that are found only in file 1. */
48static bool only_file_1;
49
50/* If true, print lines that are found only in file 2. */
51static bool only_file_2;
52
53/* If true, print lines that are found in both files. */
54static bool both;
55
56/* If nonzero, we have seen at least one unpairable line. */
57static bool seen_unpairable;
58
59/* If nonzero, we have warned about disorder in that file. */
60static bool issued_disorder_warning[2];
61
62/* If nonzero, check that the input is correctly ordered. */
63static enum
64  {
65    CHECK_ORDER_DEFAULT,
66    CHECK_ORDER_ENABLED,
67    CHECK_ORDER_DISABLED
68  } check_input_order;
69
70/* Output columns will be delimited with this string, which may be set
71   on the command-line with --output-delimiter=STR.  The default is a
72   single TAB character. */
73static char const *delimiter;
74
75/* For long options that have no equivalent short option, use a
76   non-character as a pseudo short option, starting with CHAR_MAX + 1.  */
77enum
78{
79  CHECK_ORDER_OPTION = CHAR_MAX + 1,
80  NOCHECK_ORDER_OPTION,
81  OUTPUT_DELIMITER_OPTION
82};
83
84static struct option const long_options[] =
85{
86  {"check-order", no_argument, NULL, CHECK_ORDER_OPTION},
87  {"nocheck-order", no_argument, NULL, NOCHECK_ORDER_OPTION},
88  {"output-delimiter", required_argument, NULL, OUTPUT_DELIMITER_OPTION},
89  {GETOPT_HELP_OPTION_DECL},
90  {GETOPT_VERSION_OPTION_DECL},
91  {NULL, 0, NULL, 0}
92};
93
94
95
96void
97usage (int status)
98{
99  if (status != EXIT_SUCCESS)
100    fprintf (stderr, _("Try `%s --help' for more information.\n"),
101             program_name);
102  else
103    {
104      printf (_("\
105Usage: %s [OPTION]... FILE1 FILE2\n\
106"),
107              program_name);
108      fputs (_("\
109Compare sorted files FILE1 and FILE2 line by line.\n\
110"), stdout);
111      fputs (_("\
112\n\
113With no options, produce three-column output.  Column one contains\n\
114lines unique to FILE1, column two contains lines unique to FILE2,\n\
115and column three contains lines common to both files.\n\
116"), stdout);
117      fputs (_("\
118\n\
119  -1              suppress column 1 (lines unique to FILE1)\n\
120  -2              suppress column 2 (lines unique to FILE2)\n\
121  -3              suppress column 3 (lines that appear in both files)\n\
122"), stdout);
123      fputs (_("\
124\n\
125  --check-order     check that the input is correctly sorted, even\n\
126                      if all input lines are pairable\n\
127  --nocheck-order   do not check that the input is correctly sorted\n\
128"), stdout);
129      fputs (_("\
130  --output-delimiter=STR  separate columns with STR\n\
131"), stdout);
132      fputs (HELP_OPTION_DESCRIPTION, stdout);
133      fputs (VERSION_OPTION_DESCRIPTION, stdout);
134      fputs (_("\
135\n\
136Note, comparisons honor the rules specified by `LC_COLLATE'.\n\
137"), stdout);
138      printf (_("\
139\n\
140Examples:\n\
141  %s -12 file1 file2  Print only lines present in both file1 and file2.\n\
142  %s -3  file1 file2  Print lines in file1 not in file2, and vice versa.\n\
143"),
144              program_name, program_name);
145      emit_ancillary_info ();
146    }
147  exit (status);
148}
149
150/* Output the line in linebuffer LINE to stream STREAM
151   provided the switches say it should be output.
152   CLASS is 1 for a line found only in file 1,
153   2 for a line only in file 2, 3 for a line in both. */
154
155static void
156writeline (struct linebuffer const *line, FILE *stream, int class)
157{
158  switch (class)
159    {
160    case 1:
161      if (!only_file_1)
162        return;
163      break;
164
165    case 2:
166      if (!only_file_2)
167        return;
168      /* Print a delimiter if we are printing lines from file 1.  */
169      if (only_file_1)
170        fputs (delimiter, stream);
171      break;
172
173    case 3:
174      if (!both)
175        return;
176      /* Print a delimiter if we are printing lines from file 1.  */
177      if (only_file_1)
178        fputs (delimiter, stream);
179      /* Print a delimiter if we are printing lines from file 2.  */
180      if (only_file_2)
181        fputs (delimiter, stream);
182      break;
183    }
184
185  fwrite (line->buffer, sizeof (char), line->length, stream);
186}
187
188/* Check that successive input lines PREV and CURRENT from input file
189   WHATFILE are presented in order.
190
191   If the user specified --nocheck-order, the check is not made.
192   If the user specified --check-order, the problem is fatal.
193   Otherwise (the default), the message is simply a warning.
194
195   A message is printed at most once per input file.
196
197   This funtion was copied (nearly) verbatim from `src/join.c'. */
198
199static void
200check_order (struct linebuffer const *prev,
201             struct linebuffer const *current,
202             int whatfile)
203{
204
205  if (check_input_order != CHECK_ORDER_DISABLED
206      && ((check_input_order == CHECK_ORDER_ENABLED) || seen_unpairable))
207    {
208      if (!issued_disorder_warning[whatfile - 1])
209        {
210          int order;
211
212          if (hard_LC_COLLATE)
213            order = xmemcoll (prev->buffer, prev->length - 1,
214                              current->buffer, current->length - 1);
215          else
216            order = memcmp2 (prev->buffer, prev->length - 1,
217                             current->buffer, current->length - 1);
218
219          if (0 < order)
220            {
221              error ((check_input_order == CHECK_ORDER_ENABLED
222                      ? EXIT_FAILURE : 0),
223                     0, _("file %d is not in sorted order"), whatfile);
224
225              /* If we get to here, the message was just a warning, but we
226                 want only to issue it once. */
227              issued_disorder_warning[whatfile - 1] = true;
228            }
229        }
230    }
231}
232
233/* Compare INFILES[0] and INFILES[1].
234   If either is "-", use the standard input for that file.
235   Assume that each input file is sorted;
236   merge them and output the result.  */
237
238static void
239compare_files (char **infiles)
240{
241  /* For each file, we have four linebuffers in lba. */
242  struct linebuffer lba[2][4];
243
244  /* thisline[i] points to the linebuffer holding the next available line
245     in file i, or is NULL if there are no lines left in that file.  */
246  struct linebuffer *thisline[2];
247
248  /* all_line[i][alt[i][0]] also points to the linebuffer holding the
249     current line in file i. We keep two buffers of history around so we
250     can look two lines back when we get to the end of a file. */
251  struct linebuffer *all_line[2][4];
252
253  /* This is used to rotate through the buffers for each input file. */
254  int alt[2][3];
255
256  /* streams[i] holds the input stream for file i.  */
257  FILE *streams[2];
258
259  int i, j;
260
261  /* Initialize the storage. */
262  for (i = 0; i < 2; i++)
263    {
264      for (j = 0; j < 4; j++)
265        {
266          initbuffer (&lba[i][j]);
267          all_line[i][j] = &lba[i][j];
268        }
269      alt[i][0] = 0;
270      alt[i][1] = 0;
271      alt[i][2] = 0;
272      streams[i] = (STREQ (infiles[i], "-") ? stdin : fopen (infiles[i], "r"));
273      if (!streams[i])
274        error (EXIT_FAILURE, errno, "%s", infiles[i]);
275
276      thisline[i] = readlinebuffer (all_line[i][alt[i][0]], streams[i]);
277      if (ferror (streams[i]))
278        error (EXIT_FAILURE, errno, "%s", infiles[i]);
279    }
280
281  while (thisline[0] || thisline[1])
282    {
283      int order;
284      bool fill_up[2] = { false, false };
285
286      /* Compare the next available lines of the two files.  */
287
288      if (!thisline[0])
289        order = 1;
290      else if (!thisline[1])
291        order = -1;
292      else
293        {
294          if (hard_LC_COLLATE)
295            order = xmemcoll (thisline[0]->buffer, thisline[0]->length - 1,
296                              thisline[1]->buffer, thisline[1]->length - 1);
297          else
298            {
299              size_t len = min (thisline[0]->length, thisline[1]->length) - 1;
300              order = memcmp (thisline[0]->buffer, thisline[1]->buffer, len);
301              if (order == 0)
302                order = (thisline[0]->length < thisline[1]->length
303                         ? -1
304                         : thisline[0]->length != thisline[1]->length);
305            }
306        }
307
308      /* Output the line that is lesser. */
309      if (order == 0)
310        writeline (thisline[1], stdout, 3);
311      else
312        {
313          seen_unpairable = true;
314          if (order <= 0)
315            writeline (thisline[0], stdout, 1);
316          else
317            writeline (thisline[1], stdout, 2);
318        }
319
320      /* Step the file the line came from.
321         If the files match, step both files.  */
322      if (0 <= order)
323        fill_up[1] = true;
324      if (order <= 0)
325        fill_up[0] = true;
326
327      for (i = 0; i < 2; i++)
328        if (fill_up[i])
329          {
330            /* Rotate the buffers for this file. */
331            alt[i][2] = alt[i][1];
332            alt[i][1] = alt[i][0];
333            alt[i][0] = (alt[i][0] + 1) & 0x03;
334
335            thisline[i] = readlinebuffer (all_line[i][alt[i][0]], streams[i]);
336
337            if (thisline[i])
338              check_order (all_line[i][alt[i][1]], thisline[i], i + 1);
339
340            /* If this is the end of the file we may need to re-check
341               the order of the previous two lines, since we might have
342               discovered an unpairable match since we checked before. */
343            else if (all_line[i][alt[i][2]]->buffer)
344              check_order (all_line[i][alt[i][2]],
345                           all_line[i][alt[i][1]], i + 1);
346
347            if (ferror (streams[i]))
348              error (EXIT_FAILURE, errno, "%s", infiles[i]);
349
350            fill_up[i] = false;
351          }
352    }
353
354  for (i = 0; i < 2; i++)
355    if (fclose (streams[i]) != 0)
356      error (EXIT_FAILURE, errno, "%s", infiles[i]);
357}
358
359int
360main (int argc, char **argv)
361{
362  int c;
363
364  initialize_main (&argc, &argv);
365  set_program_name (argv[0]);
366  setlocale (LC_ALL, "");
367  bindtextdomain (PACKAGE, LOCALEDIR);
368  textdomain (PACKAGE);
369  hard_LC_COLLATE = hard_locale (LC_COLLATE);
370
371  atexit (close_stdout);
372
373  only_file_1 = true;
374  only_file_2 = true;
375  both = true;
376
377  seen_unpairable = false;
378  issued_disorder_warning[0] = issued_disorder_warning[1] = false;
379  check_input_order = CHECK_ORDER_DEFAULT;
380
381  while ((c = getopt_long (argc, argv, "123", long_options, NULL)) != -1)
382    switch (c)
383      {
384      case '1':
385        only_file_1 = false;
386        break;
387
388      case '2':
389        only_file_2 = false;
390        break;
391
392      case '3':
393        both = false;
394        break;
395
396      case NOCHECK_ORDER_OPTION:
397        check_input_order = CHECK_ORDER_DISABLED;
398        break;
399
400      case CHECK_ORDER_OPTION:
401        check_input_order = CHECK_ORDER_ENABLED;
402        break;
403
404      case OUTPUT_DELIMITER_OPTION:
405        if (delimiter && !STREQ (delimiter, optarg))
406          error (EXIT_FAILURE, 0, _("multiple delimiters specified"));
407        delimiter = optarg;
408        if (!*delimiter)
409          {
410            error (EXIT_FAILURE, 0, _("empty %s not allowed"),
411                   quote ("--output-delimiter"));
412          }
413        break;
414
415      case_GETOPT_HELP_CHAR;
416
417      case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
418
419      default:
420        usage (EXIT_FAILURE);
421      }
422
423  if (argc - optind < 2)
424    {
425      if (argc <= optind)
426        error (0, 0, _("missing operand"));
427      else
428        error (0, 0, _("missing operand after %s"), quote (argv[argc - 1]));
429      usage (EXIT_FAILURE);
430    }
431
432  if (2 < argc - optind)
433    {
434      error (0, 0, _("extra operand %s"), quote (argv[optind + 2]));
435      usage (EXIT_FAILURE);
436    }
437
438  /* The default delimiter is a TAB. */
439  if (!delimiter)
440    delimiter = "\t";
441
442  compare_files (argv + optind);
443
444  if (issued_disorder_warning[0] || issued_disorder_warning[1])
445    exit (EXIT_FAILURE);
446  else
447    exit (EXIT_SUCCESS);
448}
449