src/comm.c

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