src/comm.c

   1 /* comm -- compare two sorted files line by line.
   2    Copyright (C) 1986, 1990-1991, 1995-2005, 2008-2012 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 \f
  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 "fadvise.h"
  28 #include "hard-locale.h"
  29 #include "quote.h"
  30 #include "stdio--.h"
  31 #include "memcmp2.h"
  32 #include "xmemcoll.h"
  33
  34 /* The official name of this program (e.g., no `g' prefix).  */
  35 #define PROGRAM_NAME "comm"
  36
  37 #define AUTHORS \
  38   proper_name ("Richard M. Stallman"), \
  39   proper_name ("David MacKenzie")
  40
  41 /* Undefine, to avoid warning about redefinition on some systems.  */
  42 #undef min
  43 #define min(x, y) ((x) < (y) ? (x) : (y))
  44
  45 /* True if the LC_COLLATE locale is hard.  */
  46 static bool hard_LC_COLLATE;
  47
  48 /* If true, print lines that are found only in file 1. */
  49 static bool only_file_1;
  50
  51 /* If true, print lines that are found only in file 2. */
  52 static bool only_file_2;
  53
  54 /* If true, print lines that are found in both files. */
  55 static bool both;
  56
  57 /* If nonzero, we have seen at least one unpairable line. */
  58 static bool seen_unpairable;
  59
  60 /* If nonzero, we have warned about disorder in that file. */
  61 static bool issued_disorder_warning[2];
  62
  63 /* If nonzero, check that the input is correctly ordered. */
  64 static enum
  65   {
  66     CHECK_ORDER_DEFAULT,
  67     CHECK_ORDER_ENABLED,
  68     CHECK_ORDER_DISABLED
  69   } check_input_order;
  70
  71 /* Output columns will be delimited with this string, which may be set
  72    on the command-line with --output-delimiter=STR.  The default is a
  73    single TAB character. */
  74 static char const *delimiter;
  75
  76 /* For long options that have no equivalent short option, use a
  77    non-character as a pseudo short option, starting with CHAR_MAX + 1.  */
  78 enum
  79 {
  80   CHECK_ORDER_OPTION = CHAR_MAX + 1,
  81   NOCHECK_ORDER_OPTION,
  82   OUTPUT_DELIMITER_OPTION
  83 };
  84
  85 static struct option const long_options[] =
  86 {
  87   {"check-order", no_argument, NULL, CHECK_ORDER_OPTION},
  88   {"nocheck-order", no_argument, NULL, NOCHECK_ORDER_OPTION},
  89   {"output-delimiter", required_argument, NULL, OUTPUT_DELIMITER_OPTION},
  90   {GETOPT_HELP_OPTION_DECL},
  91   {GETOPT_VERSION_OPTION_DECL},
  92   {NULL, 0, NULL, 0}
  93 };
  94
  95 \f
  96
  97 void
  98 usage (int status)
  99 {
 100   if (status != EXIT_SUCCESS)
 101     emit_try_help ();
 102   else
 103     {
 104       printf (_("\
 105 Usage: %s [OPTION]... FILE1 FILE2\n\
 106 "),
 107               program_name);
 108       fputs (_("\
 109 Compare sorted files FILE1 and FILE2 line by line.\n\
 110 "), stdout);
 111       fputs (_("\
 112 \n\
 113 With no options, produce three-column output.  Column one contains\n\
 114 lines unique to FILE1, column two contains lines unique to FILE2,\n\
 115 and 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\
 136 Note, comparisons honor the rules specified by `LC_COLLATE'.\n\
 137 "), stdout);
 138       printf (_("\
 139 \n\
 140 Examples:\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
 155 static void
 156 writeline (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
 199 static void
 200 check_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
 238 static void
 239 compare_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       fadvise (streams[i], FADVISE_SEQUENTIAL);
 277
 278       thisline[i] = readlinebuffer (all_line[i][alt[i][0]], streams[i]);
 279       if (ferror (streams[i]))
 280         error (EXIT_FAILURE, errno, "%s", infiles[i]);
 281     }
 282
 283   while (thisline[0] || thisline[1])
 284     {
 285       int order;
 286       bool fill_up[2] = { false, false };
 287
 288       /* Compare the next available lines of the two files.  */
 289
 290       if (!thisline[0])
 291         order = 1;
 292       else if (!thisline[1])
 293         order = -1;
 294       else
 295         {
 296           if (hard_LC_COLLATE)
 297             order = xmemcoll (thisline[0]->buffer, thisline[0]->length - 1,
 298                               thisline[1]->buffer, thisline[1]->length - 1);
 299           else
 300             {
 301               size_t len = min (thisline[0]->length, thisline[1]->length) - 1;
 302               order = memcmp (thisline[0]->buffer, thisline[1]->buffer, len);
 303               if (order == 0)
 304                 order = (thisline[0]->length < thisline[1]->length
 305                          ? -1
 306                          : thisline[0]->length != thisline[1]->length);
 307             }
 308         }
 309
 310       /* Output the line that is lesser. */
 311       if (order == 0)
 312         writeline (thisline[1], stdout, 3);
 313       else
 314         {
 315           seen_unpairable = true;
 316           if (order <= 0)
 317             writeline (thisline[0], stdout, 1);
 318           else
 319             writeline (thisline[1], stdout, 2);
 320         }
 321
 322       /* Step the file the line came from.
 323          If the files match, step both files.  */
 324       if (0 <= order)
 325         fill_up[1] = true;
 326       if (order <= 0)
 327         fill_up[0] = true;
 328
 329       for (i = 0; i < 2; i++)
 330         if (fill_up[i])
 331           {
 332             /* Rotate the buffers for this file. */
 333             alt[i][2] = alt[i][1];
 334             alt[i][1] = alt[i][0];
 335             alt[i][0] = (alt[i][0] + 1) & 0x03;
 336
 337             thisline[i] = readlinebuffer (all_line[i][alt[i][0]], streams[i]);
 338
 339             if (thisline[i])
 340               check_order (all_line[i][alt[i][1]], thisline[i], i + 1);
 341
 342             /* If this is the end of the file we may need to re-check
 343                the order of the previous two lines, since we might have
 344                discovered an unpairable match since we checked before. */
 345             else if (all_line[i][alt[i][2]]->buffer)
 346               check_order (all_line[i][alt[i][2]],
 347                            all_line[i][alt[i][1]], i + 1);
 348
 349             if (ferror (streams[i]))
 350               error (EXIT_FAILURE, errno, "%s", infiles[i]);
 351
 352             fill_up[i] = false;
 353           }
 354     }
 355
 356   for (i = 0; i < 2; i++)
 357     if (fclose (streams[i]) != 0)
 358       error (EXIT_FAILURE, errno, "%s", infiles[i]);
 359 }
 360
 361 int
 362 main (int argc, char **argv)
 363 {
 364   int c;
 365
 366   initialize_main (&argc, &argv);
 367   set_program_name (argv[0]);
 368   setlocale (LC_ALL, "");
 369   bindtextdomain (PACKAGE, LOCALEDIR);
 370   textdomain (PACKAGE);
 371   hard_LC_COLLATE = hard_locale (LC_COLLATE);
 372
 373   atexit (close_stdout);
 374
 375   only_file_1 = true;
 376   only_file_2 = true;
 377   both = true;
 378
 379   seen_unpairable = false;
 380   issued_disorder_warning[0] = issued_disorder_warning[1] = false;
 381   check_input_order = CHECK_ORDER_DEFAULT;
 382
 383   while ((c = getopt_long (argc, argv, "123", long_options, NULL)) != -1)
 384     switch (c)
 385       {
 386       case '1':
 387         only_file_1 = false;
 388         break;
 389
 390       case '2':
 391         only_file_2 = false;
 392         break;
 393
 394       case '3':
 395         both = false;
 396         break;
 397
 398       case NOCHECK_ORDER_OPTION:
 399         check_input_order = CHECK_ORDER_DISABLED;
 400         break;
 401
 402       case CHECK_ORDER_OPTION:
 403         check_input_order = CHECK_ORDER_ENABLED;
 404         break;
 405
 406       case OUTPUT_DELIMITER_OPTION:
 407         if (delimiter && !STREQ (delimiter, optarg))
 408           error (EXIT_FAILURE, 0, _("multiple delimiters specified"));
 409         delimiter = optarg;
 410         if (!*delimiter)
 411           {
 412             error (EXIT_FAILURE, 0, _("empty %s not allowed"),
 413                    quote ("--output-delimiter"));
 414           }
 415         break;
 416
 417       case_GETOPT_HELP_CHAR;
 418
 419       case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
 420
 421       default:
 422         usage (EXIT_FAILURE);
 423       }
 424
 425   if (argc - optind < 2)
 426     {
 427       if (argc <= optind)
 428         error (0, 0, _("missing operand"));
 429       else
 430         error (0, 0, _("missing operand after %s"), quote (argv[argc - 1]));
 431       usage (EXIT_FAILURE);
 432     }
 433
 434   if (2 < argc - optind)
 435     {
 436       error (0, 0, _("extra operand %s"), quote (argv[optind + 2]));
 437       usage (EXIT_FAILURE);
 438     }
 439
 440   /* The default delimiter is a TAB. */
 441   if (!delimiter)
 442     delimiter = "\t";
 443
 444   compare_files (argv + optind);
 445
 446   if (issued_disorder_warning[0] || issued_disorder_warning[1])
 447     exit (EXIT_FAILURE);
 448   else
 449     exit (EXIT_SUCCESS);
 450 }