src/comm.c

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