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