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