src/uniq.c

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