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