src/comm.c

   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 \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 "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     fprintf (stderr, _("Try `%s --help' for more information.\n"),
 101              program_name);
 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       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
 359 int
 360 main (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 }