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 "quote.h"
  27 #include "stdio--.h"
  28 #include "memcmp2.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             order = memcmp2 (prev->buffer, prev->length - 1,
 204                              current->buffer, current->length - 1);
 205
 206           if (0 < order)
 207             {
 208               error ((check_input_order == CHECK_ORDER_ENABLED
 209                       ? EXIT_FAILURE : 0),
 210                      0, _("file %d is not in sorted order"), whatfile);
 211
 212               /* If we get to here, the message was just a warning, but we
 213                  want only to issue it once. */
 214               issued_disorder_warning[whatfile - 1] = true;
 215             }
 216         }
 217     }
 218 }
 219
 220 /* Compare INFILES[0] and INFILES[1].
 221    If either is "-", use the standard input for that file.
 222    Assume that each input file is sorted;
 223    merge them and output the result.  */
 224
 225 static void
 226 compare_files (char **infiles)
 227 {
 228   /* For each file, we have four linebuffers in lba. */
 229   struct linebuffer lba[2][4];
 230
 231   /* thisline[i] points to the linebuffer holding the next available line
 232      in file i, or is NULL if there are no lines left in that file.  */
 233   struct linebuffer *thisline[2];
 234
 235   /* all_line[i][alt[i][0]] also points to the linebuffer holding the
 236      current line in file i. We keep two buffers of history around so we
 237      can look two lines back when we get to the end of a file. */
 238   struct linebuffer *all_line[2][4];
 239
 240   /* This is used to rotate through the buffers for each input file. */
 241   int alt[2][3];
 242
 243   /* streams[i] holds the input stream for file i.  */
 244   FILE *streams[2];
 245
 246   int i, j;
 247
 248   /* Initialize the storage. */
 249   for (i = 0; i < 2; i++)
 250     {
 251       for (j = 0; j < 4; j++)
 252         {
 253           initbuffer (&lba[i][j]);
 254           all_line[i][j] = &lba[i][j];
 255         }
 256       alt[i][0] = 0;
 257       alt[i][1] = 0;
 258       alt[i][2] = 0;
 259       streams[i] = (STREQ (infiles[i], "-") ? stdin : fopen (infiles[i], "r"));
 260       if (!streams[i])
 261         error (EXIT_FAILURE, errno, "%s", infiles[i]);
 262
 263       thisline[i] = readlinebuffer (all_line[i][alt[i][0]], streams[i]);
 264       if (ferror (streams[i]))
 265         error (EXIT_FAILURE, errno, "%s", infiles[i]);
 266     }
 267
 268   while (thisline[0] || thisline[1])
 269     {
 270       int order;
 271       bool fill_up[2] = { false, false };
 272
 273       /* Compare the next available lines of the two files.  */
 274
 275       if (!thisline[0])
 276         order = 1;
 277       else if (!thisline[1])
 278         order = -1;
 279       else
 280         {
 281           if (hard_LC_COLLATE)
 282             order = xmemcoll (thisline[0]->buffer, thisline[0]->length - 1,
 283                               thisline[1]->buffer, thisline[1]->length - 1);
 284           else
 285             {
 286               size_t len = min (thisline[0]->length, thisline[1]->length) - 1;
 287               order = memcmp (thisline[0]->buffer, thisline[1]->buffer, len);
 288               if (order == 0)
 289                 order = (thisline[0]->length < thisline[1]->length
 290                          ? -1
 291                          : thisline[0]->length != thisline[1]->length);
 292             }
 293         }
 294
 295       /* Output the line that is lesser. */
 296       if (order == 0)
 297         writeline (thisline[1], stdout, 3);
 298       else
 299         {
 300           seen_unpairable = true;
 301           if (order <= 0)
 302             writeline (thisline[0], stdout, 1);
 303           else
 304             writeline (thisline[1], stdout, 2);
 305         }
 306
 307       /* Step the file the line came from.
 308          If the files match, step both files.  */
 309       if (0 <= order)
 310         fill_up[1] = true;
 311       if (order <= 0)
 312         fill_up[0] = true;
 313
 314       for (i = 0; i < 2; i++)
 315         if (fill_up[i])
 316           {
 317             /* Rotate the buffers for this file. */
 318             alt[i][2] = alt[i][1];
 319             alt[i][1] = alt[i][0];
 320             alt[i][0] = (alt[i][0] + 1) & 0x03;
 321
 322             thisline[i] = readlinebuffer (all_line[i][alt[i][0]], streams[i]);
 323
 324             if (thisline[i])
 325               check_order (all_line[i][alt[i][1]], thisline[i], i + 1);
 326
 327             /* If this is the end of the file we may need to re-check
 328                the order of the previous two lines, since we might have
 329                discovered an unpairable match since we checked before. */
 330             else if (all_line[i][alt[i][2]]->buffer)
 331               check_order (all_line[i][alt[i][2]],
 332                            all_line[i][alt[i][1]], i + 1);
 333
 334             if (ferror (streams[i]))
 335               error (EXIT_FAILURE, errno, "%s", infiles[i]);
 336
 337             fill_up[i] = false;
 338           }
 339     }
 340
 341   for (i = 0; i < 2; i++)
 342     if (fclose (streams[i]) != 0)
 343       error (EXIT_FAILURE, errno, "%s", infiles[i]);
 344 }
 345
 346 int
 347 main (int argc, char **argv)
 348 {
 349   int c;
 350
 351   initialize_main (&argc, &argv);
 352   set_program_name (argv[0]);
 353   setlocale (LC_ALL, "");
 354   bindtextdomain (PACKAGE, LOCALEDIR);
 355   textdomain (PACKAGE);
 356   hard_LC_COLLATE = hard_locale (LC_COLLATE);
 357
 358   atexit (close_stdout);
 359
 360   only_file_1 = true;
 361   only_file_2 = true;
 362   both = true;
 363
 364   seen_unpairable = false;
 365   issued_disorder_warning[0] = issued_disorder_warning[1] = false;
 366   check_input_order = CHECK_ORDER_DEFAULT;
 367
 368   while ((c = getopt_long (argc, argv, "123", long_options, NULL)) != -1)
 369     switch (c)
 370       {
 371       case '1':
 372         only_file_1 = false;
 373         break;
 374
 375       case '2':
 376         only_file_2 = false;
 377         break;
 378
 379       case '3':
 380         both = false;
 381         break;
 382
 383       case NOCHECK_ORDER_OPTION:
 384         check_input_order = CHECK_ORDER_DISABLED;
 385         break;
 386
 387       case CHECK_ORDER_OPTION:
 388         check_input_order = CHECK_ORDER_ENABLED;
 389         break;
 390
 391       case OUTPUT_DELIMITER_OPTION:
 392         if (delimiter && !STREQ (delimiter, optarg))
 393           error (EXIT_FAILURE, 0, _("multiple delimiters specified"));
 394         delimiter = optarg;
 395         if (!*delimiter)
 396           {
 397             error (EXIT_FAILURE, 0, _("empty %s not allowed"),
 398                    quote ("--output-delimiter"));
 399           }
 400         break;
 401
 402       case_GETOPT_HELP_CHAR;
 403
 404       case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
 405
 406       default:
 407         usage (EXIT_FAILURE);
 408       }
 409
 410   if (argc - optind < 2)
 411     {
 412       if (argc <= optind)
 413         error (0, 0, _("missing operand"));
 414       else
 415         error (0, 0, _("missing operand after %s"), quote (argv[argc - 1]));
 416       usage (EXIT_FAILURE);
 417     }
 418
 419   if (2 < argc - optind)
 420     {
 421       error (0, 0, _("extra operand %s"), quote (argv[optind + 2]));
 422       usage (EXIT_FAILURE);
 423     }
 424
 425   /* The default delimiter is a TAB. */
 426   if (!delimiter)
 427     delimiter = "\t";
 428
 429   compare_files (argv + optind);
 430
 431   if (issued_disorder_warning[0] || issued_disorder_warning[1])
 432     exit (EXIT_FAILURE);
 433   else
 434     exit (EXIT_SUCCESS);
 435 }