src/comm.c

   1 /* comm -- compare two sorted files line by line.
   2    Copyright (C) 1986-2015 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 "fadvise.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.  */
  45 static bool hard_LC_COLLATE;
  46
  47 /* If true, print lines that are found only in file 1. */
  48 static bool only_file_1;
  49
  50 /* If true, print lines that are found only in file 2. */
  51 static bool only_file_2;
  52
  53 /* If true, print lines that are found in both files. */
  54 static bool both;
  55
  56 /* If nonzero, we have seen at least one unpairable line. */
  57 static bool seen_unpairable;
  58
  59 /* If nonzero, we have warned about disorder in that file. */
  60 static bool issued_disorder_warning[2];
  61
  62 /* If nonzero, check that the input is correctly ordered. */
  63 static 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. */
  73 static 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.  */
  77 enum
  78 {
  79   CHECK_ORDER_OPTION = CHAR_MAX + 1,
  80   NOCHECK_ORDER_OPTION,
  81   OUTPUT_DELIMITER_OPTION
  82 };
  83
  84 static 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 \f
  95
  96 void
  97 usage (int status)
  98 {
  99   if (status != EXIT_SUCCESS)
 100     emit_try_help ();
 101   else
 102     {
 103       printf (_("\
 104 Usage: %s [OPTION]... FILE1 FILE2\n\
 105 "),
 106               program_name);
 107       fputs (_("\
 108 Compare sorted files FILE1 and FILE2 line by line.\n\
 109 "), stdout);
 110       fputs (_("\
 111 \n\
 112 When FILE1 or FILE2 (not both) is -, read standard input.\n\
 113 "), stdout);
 114       fputs (_("\
 115 \n\
 116 With no options, produce three-column output.  Column one contains\n\
 117 lines unique to FILE1, column two contains lines unique to FILE2,\n\
 118 and column three contains lines common to both files.\n\
 119 "), stdout);
 120       fputs (_("\
 121 \n\
 122   -1              suppress column 1 (lines unique to FILE1)\n\
 123   -2              suppress column 2 (lines unique to FILE2)\n\
 124   -3              suppress column 3 (lines that appear in both files)\n\
 125 "), stdout);
 126       fputs (_("\
 127 \n\
 128   --check-order     check that the input is correctly sorted, even\n\
 129                       if all input lines are pairable\n\
 130   --nocheck-order   do not check that the input is correctly sorted\n\
 131 "), stdout);
 132       fputs (_("\
 133   --output-delimiter=STR  separate columns with STR\n\
 134 "), stdout);
 135       fputs (HELP_OPTION_DESCRIPTION, stdout);
 136       fputs (VERSION_OPTION_DESCRIPTION, stdout);
 137       fputs (_("\
 138 \n\
 139 Note, comparisons honor the rules specified by 'LC_COLLATE'.\n\
 140 "), stdout);
 141       printf (_("\
 142 \n\
 143 Examples:\n\
 144   %s -12 file1 file2  Print only lines present in both file1 and file2.\n\
 145   %s -3 file1 file2  Print lines in file1 not in file2, and vice versa.\n\
 146 "),
 147               program_name, program_name);
 148       emit_ancillary_info (PROGRAM_NAME);
 149     }
 150   exit (status);
 151 }
 152
 153 /* Output the line in linebuffer LINE to stream STREAM
 154    provided the switches say it should be output.
 155    CLASS is 1 for a line found only in file 1,
 156    2 for a line only in file 2, 3 for a line in both. */
 157
 158 static void
 159 writeline (struct linebuffer const *line, FILE *stream, int class)
 160 {
 161   switch (class)
 162     {
 163     case 1:
 164       if (!only_file_1)
 165         return;
 166       break;
 167
 168     case 2:
 169       if (!only_file_2)
 170         return;
 171       /* Print a delimiter if we are printing lines from file 1.  */
 172       if (only_file_1)
 173         fputs (delimiter, stream);
 174       break;
 175
 176     case 3:
 177       if (!both)
 178         return;
 179       /* Print a delimiter if we are printing lines from file 1.  */
 180       if (only_file_1)
 181         fputs (delimiter, stream);
 182       /* Print a delimiter if we are printing lines from file 2.  */
 183       if (only_file_2)
 184         fputs (delimiter, stream);
 185       break;
 186     }
 187
 188   fwrite (line->buffer, sizeof (char), line->length, stream);
 189 }
 190
 191 /* Check that successive input lines PREV and CURRENT from input file
 192    WHATFILE are presented in order.
 193
 194    If the user specified --nocheck-order, the check is not made.
 195    If the user specified --check-order, the problem is fatal.
 196    Otherwise (the default), the message is simply a warning.
 197
 198    A message is printed at most once per input file.
 199
 200    This function was copied (nearly) verbatim from 'src/join.c'. */
 201
 202 static void
 203 check_order (struct linebuffer const *prev,
 204              struct linebuffer const *current,
 205              int whatfile)
 206 {
 207
 208   if (check_input_order != CHECK_ORDER_DISABLED
 209       && ((check_input_order == CHECK_ORDER_ENABLED) || seen_unpairable))
 210     {
 211       if (!issued_disorder_warning[whatfile - 1])
 212         {
 213           int order;
 214
 215           if (hard_LC_COLLATE)
 216             order = xmemcoll (prev->buffer, prev->length - 1,
 217                               current->buffer, current->length - 1);
 218           else
 219             order = memcmp2 (prev->buffer, prev->length - 1,
 220                              current->buffer, current->length - 1);
 221
 222           if (0 < order)
 223             {
 224               error ((check_input_order == CHECK_ORDER_ENABLED
 225                       ? EXIT_FAILURE : 0),
 226                      0, _("file %d is not in sorted order"), whatfile);
 227
 228               /* If we get to here, the message was just a warning, but we
 229                  want only to issue it once. */
 230               issued_disorder_warning[whatfile - 1] = true;
 231             }
 232         }
 233     }
 234 }
 235
 236 /* Compare INFILES[0] and INFILES[1].
 237    If either is "-", use the standard input for that file.
 238    Assume that each input file is sorted;
 239    merge them and output the result.  */
 240
 241 static void
 242 compare_files (char **infiles)
 243 {
 244   /* For each file, we have four linebuffers in lba. */
 245   struct linebuffer lba[2][4];
 246
 247   /* thisline[i] points to the linebuffer holding the next available line
 248      in file i, or is NULL if there are no lines left in that file.  */
 249   struct linebuffer *thisline[2];
 250
 251   /* all_line[i][alt[i][0]] also points to the linebuffer holding the
 252      current line in file i. We keep two buffers of history around so we
 253      can look two lines back when we get to the end of a file. */
 254   struct linebuffer *all_line[2][4];
 255
 256   /* This is used to rotate through the buffers for each input file. */
 257   int alt[2][3];
 258
 259   /* streams[i] holds the input stream for file i.  */
 260   FILE *streams[2];
 261
 262   int i, j;
 263
 264   /* Initialize the storage. */
 265   for (i = 0; i < 2; i++)
 266     {
 267       for (j = 0; j < 4; j++)
 268         {
 269           initbuffer (&lba[i][j]);
 270           all_line[i][j] = &lba[i][j];
 271         }
 272       alt[i][0] = 0;
 273       alt[i][1] = 0;
 274       alt[i][2] = 0;
 275       streams[i] = (STREQ (infiles[i], "-") ? stdin : fopen (infiles[i], "r"));
 276       if (!streams[i])
 277         error (EXIT_FAILURE, errno, "%s", infiles[i]);
 278
 279       fadvise (streams[i], FADVISE_SEQUENTIAL);
 280
 281       thisline[i] = readlinebuffer (all_line[i][alt[i][0]], streams[i]);
 282       if (ferror (streams[i]))
 283         error (EXIT_FAILURE, errno, "%s", infiles[i]);
 284     }
 285
 286   while (thisline[0] || thisline[1])
 287     {
 288       int order;
 289       bool fill_up[2] = { false, false };
 290
 291       /* Compare the next available lines of the two files.  */
 292
 293       if (!thisline[0])
 294         order = 1;
 295       else if (!thisline[1])
 296         order = -1;
 297       else
 298         {
 299           if (hard_LC_COLLATE)
 300             order = xmemcoll (thisline[0]->buffer, thisline[0]->length - 1,
 301                               thisline[1]->buffer, thisline[1]->length - 1);
 302           else
 303             {
 304               size_t len = min (thisline[0]->length, thisline[1]->length) - 1;
 305               order = memcmp (thisline[0]->buffer, thisline[1]->buffer, len);
 306               if (order == 0)
 307                 order = (thisline[0]->length < thisline[1]->length
 308                          ? -1
 309                          : thisline[0]->length != thisline[1]->length);
 310             }
 311         }
 312
 313       /* Output the line that is lesser. */
 314       if (order == 0)
 315         writeline (thisline[1], stdout, 3);
 316       else
 317         {
 318           seen_unpairable = true;
 319           if (order <= 0)
 320             writeline (thisline[0], stdout, 1);
 321           else
 322             writeline (thisline[1], stdout, 2);
 323         }
 324
 325       /* Step the file the line came from.
 326          If the files match, step both files.  */
 327       if (0 <= order)
 328         fill_up[1] = true;
 329       if (order <= 0)
 330         fill_up[0] = true;
 331
 332       for (i = 0; i < 2; i++)
 333         if (fill_up[i])
 334           {
 335             /* Rotate the buffers for this file. */
 336             alt[i][2] = alt[i][1];
 337             alt[i][1] = alt[i][0];
 338             alt[i][0] = (alt[i][0] + 1) & 0x03;
 339
 340             thisline[i] = readlinebuffer (all_line[i][alt[i][0]], streams[i]);
 341
 342             if (thisline[i])
 343               check_order (all_line[i][alt[i][1]], thisline[i], i + 1);
 344
 345             /* If this is the end of the file we may need to re-check
 346                the order of the previous two lines, since we might have
 347                discovered an unpairable match since we checked before. */
 348             else if (all_line[i][alt[i][2]]->buffer)
 349               check_order (all_line[i][alt[i][2]],
 350                            all_line[i][alt[i][1]], i + 1);
 351
 352             if (ferror (streams[i]))
 353               error (EXIT_FAILURE, errno, "%s", infiles[i]);
 354
 355             fill_up[i] = false;
 356           }
 357     }
 358
 359   for (i = 0; i < 2; i++)
 360     if (fclose (streams[i]) != 0)
 361       error (EXIT_FAILURE, errno, "%s", infiles[i]);
 362 }
 363
 364 int
 365 main (int argc, char **argv)
 366 {
 367   int c;
 368
 369   initialize_main (&argc, &argv);
 370   set_program_name (argv[0]);
 371   setlocale (LC_ALL, "");
 372   bindtextdomain (PACKAGE, LOCALEDIR);
 373   textdomain (PACKAGE);
 374   hard_LC_COLLATE = hard_locale (LC_COLLATE);
 375
 376   atexit (close_stdout);
 377
 378   only_file_1 = true;
 379   only_file_2 = true;
 380   both = true;
 381
 382   seen_unpairable = false;
 383   issued_disorder_warning[0] = issued_disorder_warning[1] = false;
 384   check_input_order = CHECK_ORDER_DEFAULT;
 385
 386   while ((c = getopt_long (argc, argv, "123", long_options, NULL)) != -1)
 387     switch (c)
 388       {
 389       case '1':
 390         only_file_1 = false;
 391         break;
 392
 393       case '2':
 394         only_file_2 = false;
 395         break;
 396
 397       case '3':
 398         both = false;
 399         break;
 400
 401       case NOCHECK_ORDER_OPTION:
 402         check_input_order = CHECK_ORDER_DISABLED;
 403         break;
 404
 405       case CHECK_ORDER_OPTION:
 406         check_input_order = CHECK_ORDER_ENABLED;
 407         break;
 408
 409       case OUTPUT_DELIMITER_OPTION:
 410         if (delimiter && !STREQ (delimiter, optarg))
 411           error (EXIT_FAILURE, 0, _("multiple delimiters specified"));
 412         delimiter = optarg;
 413         if (!*delimiter)
 414           {
 415             error (EXIT_FAILURE, 0, _("empty %s not allowed"),
 416                    quote ("--output-delimiter"));
 417           }
 418         break;
 419
 420       case_GETOPT_HELP_CHAR;
 421
 422       case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
 423
 424       default:
 425         usage (EXIT_FAILURE);
 426       }
 427
 428   if (argc - optind < 2)
 429     {
 430       if (argc <= optind)
 431         error (0, 0, _("missing operand"));
 432       else
 433         error (0, 0, _("missing operand after %s"), quote (argv[argc - 1]));
 434       usage (EXIT_FAILURE);
 435     }
 436
 437   if (2 < argc - optind)
 438     {
 439       error (0, 0, _("extra operand %s"), quote (argv[optind + 2]));
 440       usage (EXIT_FAILURE);
 441     }
 442
 443   /* The default delimiter is a TAB. */
 444   if (!delimiter)
 445     delimiter = "\t";
 446
 447   compare_files (argv + optind);
 448
 449   if (issued_disorder_warning[0] || issued_disorder_warning[1])
 450     return EXIT_FAILURE;
 451   else
 452     return EXIT_SUCCESS;
 453 }