1 /* uniq -- remove duplicate lines from a sorted file
2 Copyright (C) 1986-2023 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 M. Stallman and David MacKenzie. */
18
19 #include <config.h>
20
21 #include <getopt.h>
22 #include <sys/types.h>
23
24 #include "system.h"
25 #include "argmatch.h"
26 #include "linebuffer.h"
27 #include "fadvise.h"
28 #include "posixver.h"
29 #include "stdio--.h"
30 #include "xstrtol.h"
31 #include "memcasecmp.h"
32 #include "quote.h"
33
34 /* The official name of this program (e.g., no 'g' prefix). */
35 #define PROGRAM_NAME "uniq"
36
37 #define AUTHORS \
38 proper_name ("Richard M. Stallman"), \
39 proper_name ("David MacKenzie")
40
41 #define SWAP_LINES(A, B) \
42 do \
43 { \
44 struct linebuffer *_tmp; \
45 _tmp = (A); \
46 (A) = (B); \
47 (B) = _tmp; \
48 } \
49 while (0)
50
51 /* Number of fields to skip on each line when doing comparisons. */
52 static size_t skip_fields;
53
54 /* Number of chars to skip after skipping any fields. */
55 static size_t skip_chars;
56
57 /* Number of chars to compare. */
58 static size_t check_chars;
59
60 enum countmode
61 {
62 count_occurrences, /* -c Print count before output lines. */
63 count_none /* Default. Do not print counts. */
64 };
65
66 /* Whether and how to precede the output lines with a count of the number of
67 times they occurred in the input. */
68 static enum countmode countmode;
69
70 /* Which lines to output: unique lines, the first of a group of
71 repeated lines, and the second and subsequent of a group of
72 repeated lines. */
73 static bool output_unique;
74 static bool output_first_repeated;
75 static bool output_later_repeated;
76
77 /* If true, ignore case when comparing. */
78 static bool ignore_case;
79
80 enum delimit_method
81 {
82 /* No delimiters output. --all-repeated[=none] */
83 DM_NONE,
84
85 /* Delimiter precedes all groups. --all-repeated=prepend */
86 DM_PREPEND,
87
88 /* Delimit all groups. --all-repeated=separate */
89 DM_SEPARATE
90 };
91
92 static char const *const delimit_method_string[] =
93 {
94 "none", "prepend", "separate", nullptr
95 };
96
97 static enum delimit_method const delimit_method_map[] =
98 {
99 DM_NONE, DM_PREPEND, DM_SEPARATE
100 };
101
102 /* Select whether/how to delimit groups of duplicate lines. */
103 static enum delimit_method delimit_groups;
104
105 enum grouping_method
106 {
107 /* No grouping, when "--group" isn't used */
108 GM_NONE,
109
110 /* Delimiter precedes all groups. --group=prepend */
111 GM_PREPEND,
112
113 /* Delimiter follows all groups. --group=append */
114 GM_APPEND,
115
116 /* Delimiter between groups. --group[=separate] */
117 GM_SEPARATE,
118
119 /* Delimiter before and after each group. --group=both */
120 GM_BOTH
121 };
122
123 static char const *const grouping_method_string[] =
124 {
125 "prepend", "append", "separate", "both", nullptr
126 };
127
128 static enum grouping_method const grouping_method_map[] =
129 {
130 GM_PREPEND, GM_APPEND, GM_SEPARATE, GM_BOTH
131 };
132
133 static enum grouping_method grouping = GM_NONE;
134
135 enum
136 {
137 GROUP_OPTION = CHAR_MAX + 1
138 };
139
140 static struct option const longopts[] =
141 {
142 {"count", no_argument, nullptr, 'c'},
143 {"repeated", no_argument, nullptr, 'd'},
144 {"all-repeated", optional_argument, nullptr, 'D'},
145 {"group", optional_argument, nullptr, GROUP_OPTION},
146 {"ignore-case", no_argument, nullptr, 'i'},
147 {"unique", no_argument, nullptr, 'u'},
148 {"skip-fields", required_argument, nullptr, 'f'},
149 {"skip-chars", required_argument, nullptr, 's'},
150 {"check-chars", required_argument, nullptr, 'w'},
151 {"zero-terminated", no_argument, nullptr, 'z'},
152 {GETOPT_HELP_OPTION_DECL},
153 {GETOPT_VERSION_OPTION_DECL},
154 {nullptr, 0, nullptr, 0}
155 };
156
157 void
158 usage (int status)
159 {
160 if (status != EXIT_SUCCESS)
161 emit_try_help ();
162 else
163 {
164 printf (_("\
165 Usage: %s [OPTION]... [INPUT [OUTPUT]]\n\
166 "),
167 program_name);
168 fputs (_("\
169 Filter adjacent matching lines from INPUT (or standard input),\n\
170 writing to OUTPUT (or standard output).\n\
171 \n\
172 With no options, matching lines are merged to the first occurrence.\n\
173 "), stdout);
174
175 emit_mandatory_arg_note ();
176
177 fputs (_("\
178 -c, --count prefix lines by the number of occurrences\n\
179 -d, --repeated only print duplicate lines, one for each group\n\
180 "), stdout);
181 fputs (_("\
182 -D print all duplicate lines\n\
183 --all-repeated[=METHOD] like -D, but allow separating groups\n\
184 with an empty line;\n\
185 METHOD={none(default),prepend,separate}\n\
186 "), stdout);
187 fputs (_("\
188 -f, --skip-fields=N avoid comparing the first N fields\n\
189 "), stdout);
190 fputs (_("\
191 --group[=METHOD] show all items, separating groups with an empty line;\n\
192 METHOD={separate(default),prepend,append,both}\n\
193 "), stdout);
194 fputs (_("\
195 -i, --ignore-case ignore differences in case when comparing\n\
196 -s, --skip-chars=N avoid comparing the first N characters\n\
197 -u, --unique only print unique lines\n\
198 "), stdout);
199 fputs (_("\
200 -z, --zero-terminated line delimiter is NUL, not newline\n\
201 "), stdout);
202 fputs (_("\
203 -w, --check-chars=N compare no more than N characters in lines\n\
204 "), stdout);
205 fputs (HELP_OPTION_DESCRIPTION, stdout);
206 fputs (VERSION_OPTION_DESCRIPTION, stdout);
207 fputs (_("\
208 \n\
209 A field is a run of blanks (usually spaces and/or TABs), then non-blank\n\
210 characters. Fields are skipped before chars.\n\
211 "), stdout);
212 fputs (_("\
213 \n\
214 Note: 'uniq' does not detect repeated lines unless they are adjacent.\n\
215 You may want to sort the input first, or use 'sort -u' without 'uniq'.\n\
216 "), stdout);
217 emit_ancillary_info (PROGRAM_NAME);
218 }
219 exit (status);
220 }
221
222 static bool
223 strict_posix2 (void)
224 {
225 int posix_ver = posix2_version ();
226 return 200112 <= posix_ver && posix_ver < 200809;
227 }
228
229 /* Convert OPT to size_t, reporting an error using MSGID if OPT is
230 invalid. Silently convert too-large values to SIZE_MAX. */
231
232 static size_t
233 size_opt (char const *opt, char const *msgid)
234 {
235 uintmax_t size;
236
237 switch (xstrtoumax (opt, nullptr, 10, &size, ""))
238 {
239 case LONGINT_OK:
240 case LONGINT_OVERFLOW:
241 break;
242
243 default:
244 error (EXIT_FAILURE, 0, "%s: %s", opt, _(msgid));
245 }
246
247 return MIN (size, SIZE_MAX);
248 }
249
250 /* Given a linebuffer LINE,
251 return a pointer to the beginning of the line's field to be compared. */
252
253 ATTRIBUTE_PURE
254 static char *
255 find_field (struct linebuffer const *line)
256 {
257 size_t count;
258 char const *lp = line->buffer;
259 size_t size = line->length - 1;
260 size_t i = 0;
261
262 for (count = 0; count < skip_fields && i < size; count++)
263 {
264 while (i < size && field_sep (lp[i]))
265 i++;
266 while (i < size && !field_sep (lp[i]))
267 i++;
268 }
269
270 i += MIN (skip_chars, size - i);
271
272 return line->buffer + i;
273 }
274
275 /* Return false if two strings OLD and NEW match, true if not.
276 OLD and NEW point not to the beginnings of the lines
277 but rather to the beginnings of the fields to compare.
278 OLDLEN and NEWLEN are their lengths. */
279
280 static bool
281 different (char *old, char *new, size_t oldlen, size_t newlen)
282 {
283 if (check_chars < oldlen)
284 oldlen = check_chars;
285 if (check_chars < newlen)
286 newlen = check_chars;
287
288 if (ignore_case)
289 return oldlen != newlen || memcasecmp (old, new, oldlen);
290 else
291 return oldlen != newlen || memcmp (old, new, oldlen);
292 }
293
294 /* Output the line in linebuffer LINE to standard output
295 provided that the switches say it should be output.
296 MATCH is true if the line matches the previous line.
297 If requested, print the number of times it occurred, as well;
298 LINECOUNT + 1 is the number of times that the line occurred. */
299
300 static void
301 writeline (struct linebuffer const *line,
302 bool match, uintmax_t linecount)
303 {
304 if (! (linecount == 0 ? output_unique
305 : !match ? output_first_repeated
306 : output_later_repeated))
307 return;
308
309 if (countmode == count_occurrences)
310 printf ("%7" PRIuMAX " ", linecount + 1);
311
312 if (fwrite (line->buffer, sizeof (char), line->length, stdout)
313 != line->length)
314 write_error ();
315 }
316
317 /* Process input file INFILE with output to OUTFILE.
318 If either is "-", use the standard I/O stream for it instead. */
319
320 static void
321 check_file (char const *infile, char const *outfile, char delimiter)
322 {
323 struct linebuffer lb1, lb2;
324 struct linebuffer *thisline, *prevline;
325
326 if (! (STREQ (infile, "-") || freopen (infile, "r", stdin)))
327 error (EXIT_FAILURE, errno, "%s", quotef (infile));
328 if (! (STREQ (outfile, "-") || freopen (outfile, "w", stdout)))
329 error (EXIT_FAILURE, errno, "%s", quotef (outfile));
330
331 fadvise (stdin, FADVISE_SEQUENTIAL);
332
333 thisline = &lb1;
334 prevline = &lb2;
335
336 initbuffer (thisline);
337 initbuffer (prevline);
338
339 /* The duplication in the following 'if' and 'else' blocks is an
340 optimization to distinguish between when we can print input
341 lines immediately (1. & 2.) or not.
342
343 1. --group => all input lines are printed.
344 checking for unique/duplicated lines is used only for printing
345 group separators.
346
347 2. The default case in which none of these options has been specified:
348 --count, --repeated, --all-repeated, --unique
349 In the default case, this optimization lets uniq output each different
350 line right away, without waiting to see if the next one is different.
351
352 3. All other cases.
353 */
354 if (output_unique && output_first_repeated && countmode == count_none)
355 {
356 char *prevfield = nullptr;
357 size_t prevlen;
358 bool first_group_printed = false;
359
360 while (!feof (stdin))
361 {
362 char *thisfield;
363 size_t thislen;
364 bool new_group;
365
366 if (readlinebuffer_delim (thisline, stdin, delimiter) == 0)
367 break;
368
369 thisfield = find_field (thisline);
370 thislen = thisline->length - 1 - (thisfield - thisline->buffer);
371
372 new_group = (!prevfield
373 || different (thisfield, prevfield, thislen, prevlen));
374
375 if (new_group && grouping != GM_NONE
376 && (grouping == GM_PREPEND || grouping == GM_BOTH
377 || (first_group_printed && (grouping == GM_APPEND
378 || grouping == GM_SEPARATE))))
379 putchar (delimiter);
380
381 if (new_group || grouping != GM_NONE)
382 {
383 if (fwrite (thisline->buffer, sizeof (char), thisline->length,
384 stdout) != thisline->length)
385 write_error ();
386
387 SWAP_LINES (prevline, thisline);
388 prevfield = thisfield;
389 prevlen = thislen;
390 first_group_printed = true;
391 }
392 }
393 if ((grouping == GM_BOTH || grouping == GM_APPEND) && first_group_printed)
394 putchar (delimiter);
395 }
396 else
397 {
398 char *prevfield;
399 size_t prevlen;
400 uintmax_t match_count = 0;
401 bool first_delimiter = true;
402
403 if (readlinebuffer_delim (prevline, stdin, delimiter) == 0)
404 goto closefiles;
405 prevfield = find_field (prevline);
406 prevlen = prevline->length - 1 - (prevfield - prevline->buffer);
407
408 while (!feof (stdin))
409 {
410 bool match;
411 char *thisfield;
412 size_t thislen;
413 if (readlinebuffer_delim (thisline, stdin, delimiter) == 0)
414 {
415 if (ferror (stdin))
416 goto closefiles;
417 break;
418 }
419 thisfield = find_field (thisline);
420 thislen = thisline->length - 1 - (thisfield - thisline->buffer);
421 match = !different (thisfield, prevfield, thislen, prevlen);
422 match_count += match;
423
424 if (match_count == UINTMAX_MAX)
425 {
426 if (count_occurrences)
427 error (EXIT_FAILURE, 0, _("too many repeated lines"));
428 match_count--;
429 }
430
431 if (delimit_groups != DM_NONE)
432 {
433 if (!match)
434 {
435 if (match_count) /* a previous match */
436 first_delimiter = false; /* Only used when DM_SEPARATE */
437 }
438 else if (match_count == 1)
439 {
440 if ((delimit_groups == DM_PREPEND)
441 || (delimit_groups == DM_SEPARATE
442 && !first_delimiter))
443 putchar (delimiter);
444 }
445 }
446
447 if (!match || output_later_repeated)
448 {
449 writeline (prevline, match, match_count);
450 SWAP_LINES (prevline, thisline);
451 prevfield = thisfield;
452 prevlen = thislen;
453 if (!match)
454 match_count = 0;
455 }
456 }
457
458 writeline (prevline, false, match_count);
459 }
460
461 closefiles:
462 if (ferror (stdin) || fclose (stdin) != 0)
463 error (EXIT_FAILURE, errno, _("error reading %s"), quoteaf (infile));
464
465 /* stdout is handled via the atexit-invoked close_stdout function. */
466
467 free (lb1.buffer);
468 free (lb2.buffer);
469 }
470
471 enum Skip_field_option_type
472 {
473 SFO_NONE,
474 SFO_OBSOLETE,
475 SFO_NEW
476 };
477
478 int
479 main (int argc, char **argv)
480 {
481 int optc = 0;
482 bool posixly_correct = (getenv ("POSIXLY_CORRECT") != nullptr);
483 enum Skip_field_option_type skip_field_option_type = SFO_NONE;
484 unsigned int nfiles = 0;
485 char const *file[2];
486 char delimiter = '\n'; /* change with --zero-terminated, -z */
487 bool output_option_used = false; /* if true, one of -u/-d/-D/-c was used */
488
489 file[0] = file[1] = "-";
490 initialize_main (&argc, &argv);
491 set_program_name (argv[0]);
492 setlocale (LC_ALL, "");
493 bindtextdomain (PACKAGE, LOCALEDIR);
494 textdomain (PACKAGE);
495
496 atexit (close_stdout);
497
498 skip_chars = 0;
499 skip_fields = 0;
500 check_chars = SIZE_MAX;
501 output_unique = output_first_repeated = true;
502 output_later_repeated = false;
503 countmode = count_none;
504 delimit_groups = DM_NONE;
505
506 while (true)
507 {
508 /* Parse an operand with leading "+" as a file after "--" was
509 seen; or if pedantic and a file was seen; or if not
510 obsolete. */
511
512 if (optc == -1
513 || (posixly_correct && nfiles != 0)
514 || ((optc = getopt_long (argc, argv,
515 "-0123456789Dcdf:is:uw:z",
516 longopts, nullptr))
517 == -1))
518 {
519 if (argc <= optind)
520 break;
521 if (nfiles == 2)
522 {
523 error (0, 0, _("extra operand %s"), quote (argv[optind]));
524 usage (EXIT_FAILURE);
525 }
526 file[nfiles++] = argv[optind++];
527 }
528 else switch (optc)
529 {
530 case 1:
531 {
532 uintmax_t size;
533 if (optarg[0] == '+'
534 && ! strict_posix2 ()
535 && xstrtoumax (optarg, nullptr, 10, &size, "") == LONGINT_OK
536 && size <= SIZE_MAX)
537 skip_chars = size;
538 else if (nfiles == 2)
539 {
540 error (0, 0, _("extra operand %s"), quote (optarg));
541 usage (EXIT_FAILURE);
542 }
543 else
544 file[nfiles++] = optarg;
545 }
546 break;
547
548 case '0':
549 case '1':
550 case '2':
551 case '3':
552 case '4':
553 case '5':
554 case '6':
555 case '7':
556 case '8':
557 case '9':
558 {
559 if (skip_field_option_type == SFO_NEW)
560 skip_fields = 0;
561
562 if (!DECIMAL_DIGIT_ACCUMULATE (skip_fields, optc - '0', size_t))
563 skip_fields = SIZE_MAX;
564
565 skip_field_option_type = SFO_OBSOLETE;
566 }
567 break;
568
569 case 'c':
570 countmode = count_occurrences;
571 output_option_used = true;
572 break;
573
574 case 'd':
575 output_unique = false;
576 output_option_used = true;
577 break;
578
579 case 'D':
580 output_unique = false;
581 output_later_repeated = true;
582 if (optarg == nullptr)
583 delimit_groups = DM_NONE;
584 else
585 delimit_groups = XARGMATCH ("--all-repeated", optarg,
586 delimit_method_string,
587 delimit_method_map);
588 output_option_used = true;
589 break;
590
591 case GROUP_OPTION:
592 if (optarg == nullptr)
593 grouping = GM_SEPARATE;
594 else
595 grouping = XARGMATCH ("--group", optarg,
596 grouping_method_string,
597 grouping_method_map);
598 break;
599
600 case 'f':
601 skip_field_option_type = SFO_NEW;
602 skip_fields = size_opt (optarg,
603 N_("invalid number of fields to skip"));
604 break;
605
606 case 'i':
607 ignore_case = true;
608 break;
609
610 case 's':
611 skip_chars = size_opt (optarg,
612 N_("invalid number of bytes to skip"));
613 break;
614
615 case 'u':
616 output_first_repeated = false;
617 output_option_used = true;
618 break;
619
620 case 'w':
621 check_chars = size_opt (optarg,
622 N_("invalid number of bytes to compare"));
623 break;
624
625 case 'z':
626 delimiter = '\0';
627 break;
628
629 case_GETOPT_HELP_CHAR;
630
631 case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
632
633 default:
634 usage (EXIT_FAILURE);
635 }
636 }
637
638 /* Note we could allow --group with -D at least, and that would
639 avoid the need to specify a grouping method to --all-repeated.
640 It was thought best to avoid deprecating those parameters though
641 and keep --group separate to other options. */
642 if (grouping != GM_NONE && output_option_used)
643 {
644 error (0, 0, _("--group is mutually exclusive with -c/-d/-D/-u"));
645 usage (EXIT_FAILURE);
646 }
647
648 if (grouping != GM_NONE && countmode != count_none)
649 {
650 error (0, 0,
651 _("grouping and printing repeat counts is meaningless"));
652 usage (EXIT_FAILURE);
653 }
654
655 if (countmode == count_occurrences && output_later_repeated)
656 {
657 error (0, 0,
658 _("printing all duplicated lines and repeat counts is meaningless"));
659 usage (EXIT_FAILURE);
660 }
661
662 check_file (file[0], file[1], delimiter);
663
664 return EXIT_SUCCESS;
665 }