src/comm.c

   1 /* comm -- compare two sorted files line by line.
   2    Copyright (C) 1986-2022 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    Exit the program when done.  */
 253
 254 static _Noreturn void
 255 compare_files (char **infiles)
 256 {
 257   /* For each file, we have four linebuffers in lba. */
 258   struct linebuffer lba[2][4];
 259
 260   /* thisline[i] points to the linebuffer holding the next available line
 261      in file i, or is NULL if there are no lines left in that file.  */
 262   struct linebuffer *thisline[2];
 263
 264   /* all_line[i][alt[i][0]] also points to the linebuffer holding the
 265      current line in file i. We keep two buffers of history around so we
 266      can look two lines back when we get to the end of a file. */
 267   struct linebuffer *all_line[2][4];
 268
 269   /* This is used to rotate through the buffers for each input file. */
 270   int alt[2][3];
 271
 272   /* streams[i] holds the input stream for file i.  */
 273   FILE *streams[2];
 274
 275   /* Counters for the summary.  */
 276   uintmax_t total[] = {0, 0, 0};
 277
 278   int i, j;
 279
 280   /* Initialize the storage. */
 281   for (i = 0; i < 2; i++)
 282     {
 283       for (j = 0; j < 4; j++)
 284         {
 285           initbuffer (&lba[i][j]);
 286           all_line[i][j] = &lba[i][j];
 287         }
 288       alt[i][0] = 0;
 289       alt[i][1] = 0;
 290       alt[i][2] = 0;
 291       streams[i] = (STREQ (infiles[i], "-") ? stdin : fopen (infiles[i], "r"));
 292       if (!streams[i])
 293         die (EXIT_FAILURE, errno, "%s", quotef (infiles[i]));
 294
 295       fadvise (streams[i], FADVISE_SEQUENTIAL);
 296
 297       thisline[i] = readlinebuffer_delim (all_line[i][alt[i][0]], streams[i],
 298                                           delim);
 299       if (ferror (streams[i]))
 300         die (EXIT_FAILURE, errno, "%s", quotef (infiles[i]));
 301     }
 302
 303   while (thisline[0] || thisline[1])
 304     {
 305       int order;
 306       bool fill_up[2] = { false, false };
 307
 308       /* Compare the next available lines of the two files.  */
 309
 310       if (!thisline[0])
 311         order = 1;
 312       else if (!thisline[1])
 313         order = -1;
 314       else
 315         {
 316           if (hard_LC_COLLATE)
 317             order = xmemcoll (thisline[0]->buffer, thisline[0]->length - 1,
 318                               thisline[1]->buffer, thisline[1]->length - 1);
 319           else
 320             {
 321               size_t len = min (thisline[0]->length, thisline[1]->length) - 1;
 322               order = memcmp (thisline[0]->buffer, thisline[1]->buffer, len);
 323               if (order == 0)
 324                 order = ((thisline[0]->length > thisline[1]->length)
 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   if (issued_disorder_warning[0] || issued_disorder_warning[1])
 406     die (EXIT_FAILURE, 0, _("input is not in sorted order"));
 407
 408   /* Exit here to pacify gcc -fsanitizer=leak.  */
 409   exit (EXIT_SUCCESS);
 410 }
 411
 412 int
 413 main (int argc, char **argv)
 414 {
 415   int c;
 416
 417   initialize_main (&argc, &argv);
 418   set_program_name (argv[0]);
 419   setlocale (LC_ALL, "");
 420   bindtextdomain (PACKAGE, LOCALEDIR);
 421   textdomain (PACKAGE);
 422   hard_LC_COLLATE = hard_locale (LC_COLLATE);
 423
 424   atexit (close_stdout);
 425
 426   only_file_1 = true;
 427   only_file_2 = true;
 428   both = true;
 429
 430   seen_unpairable = false;
 431   issued_disorder_warning[0] = issued_disorder_warning[1] = false;
 432   check_input_order = CHECK_ORDER_DEFAULT;
 433   total_option = false;
 434
 435   while ((c = getopt_long (argc, argv, "123z", long_options, NULL)) != -1)
 436     switch (c)
 437       {
 438       case '1':
 439         only_file_1 = false;
 440         break;
 441
 442       case '2':
 443         only_file_2 = false;
 444         break;
 445
 446       case '3':
 447         both = false;
 448         break;
 449
 450       case 'z':
 451         delim = '\0';
 452         break;
 453
 454       case NOCHECK_ORDER_OPTION:
 455         check_input_order = CHECK_ORDER_DISABLED;
 456         break;
 457
 458       case CHECK_ORDER_OPTION:
 459         check_input_order = CHECK_ORDER_ENABLED;
 460         break;
 461
 462       case OUTPUT_DELIMITER_OPTION:
 463         if (col_sep_len && !STREQ (col_sep, optarg))
 464           die (EXIT_FAILURE, 0, _("multiple output delimiters specified"));
 465         col_sep = optarg;
 466         col_sep_len = *optarg ? strlen (optarg) : 1;
 467         break;
 468
 469       case TOTAL_OPTION:
 470         total_option = true;
 471         break;
 472
 473       case_GETOPT_HELP_CHAR;
 474
 475       case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
 476
 477       default:
 478         usage (EXIT_FAILURE);
 479       }
 480
 481   if (! col_sep_len)
 482     col_sep_len = 1;
 483
 484   if (argc - optind < 2)
 485     {
 486       if (argc <= optind)
 487         error (0, 0, _("missing operand"));
 488       else
 489         error (0, 0, _("missing operand after %s"), quote (argv[argc - 1]));
 490       usage (EXIT_FAILURE);
 491     }
 492
 493   if (2 < argc - optind)
 494     {
 495       error (0, 0, _("extra operand %s"), quote (argv[optind + 2]));
 496       usage (EXIT_FAILURE);
 497     }
 498
 499   compare_files (argv + optind);
 500 }