src/comm.c

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