src/comm.c

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