1 /* join - join lines of two files on a common field
2 Copyright (C) 91, 1995-2006, 2008 Free Software Foundation, Inc.
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.
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.
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/>.
17 Written by Mike Haertel, mike@gnu.ai.mit.edu. */
22 #include <sys/types.h>
27 #include "hard-locale.h"
28 #include "linebuffer.h"
29 #include "memcasecmp.h"
36 /* The official name of this program (e.g., no `g' prefix). */
37 #define PROGRAM_NAME "join"
39 #define AUTHORS "Mike Haertel"
41 #define join system_join
43 /* An element of the list identifying which fields to print for each
47 /* File number: 0, 1, or 2. 0 means use the join field.
48 1 means use the first file argument, 2 the second. */
51 /* Field index (zero-based), specified only when FILE is 1 or 2. */
57 /* A field of a line. */
60 char *beg; /* First character in field. */
61 size_t len; /* The length of the field. */
64 /* A line read from an input file. */
67 struct linebuffer buf; /* The line itself. */
68 size_t nfields; /* Number of elements in `fields'. */
69 size_t nfields_allocated; /* Number of elements allocated for `fields'. */
73 /* One or more consecutive lines read from a file that all have the
74 same join field value. */
77 size_t count; /* Elements used in `lines'. */
78 size_t alloc; /* Elements allocated in `lines'. */
82 /* The name this program was run with. */
85 /* The previous line read from each file. */
86 static struct line *prevline[2];
88 /* True if the LC_COLLATE locale is hard. */
89 static bool hard_LC_COLLATE;
91 /* If nonzero, print unpairable lines in file 1 or 2. */
92 static bool print_unpairables_1, print_unpairables_2;
94 /* If nonzero, print pairable lines. */
95 static bool print_pairables;
97 /* If nonzero, we have seen at least one unpairable line. */
98 static bool seen_unpairable;
100 /* If nonzero, we have warned about disorder in that file. */
101 static bool issued_disorder_warning[2];
103 /* Empty output field filler. */
104 static char const *empty_filler;
106 /* Field to join on; SIZE_MAX means they haven't been determined yet. */
107 static size_t join_field_1 = SIZE_MAX;
108 static size_t join_field_2 = SIZE_MAX;
110 /* List of fields to print. */
111 static struct outlist outlist_head;
113 /* Last element in `outlist', where a new element can be added. */
114 static struct outlist *outlist_end = &outlist_head;
116 /* Tab character separating fields. If negative, fields are separated
117 by any nonempty string of blanks, otherwise by exactly one
118 tab character whose value (when cast to unsigned char) equals TAB. */
121 /* If nonzero, check that the input is correctly ordered. */
131 CHECK_ORDER_OPTION = CHAR_MAX + 1,
136 static struct option const longopts[] =
138 {"ignore-case", no_argument, NULL, 'i'},
139 {"check-order", no_argument, NULL, CHECK_ORDER_OPTION},
140 {"nocheck-order", no_argument, NULL, NOCHECK_ORDER_OPTION},
141 {GETOPT_HELP_OPTION_DECL},
142 {GETOPT_VERSION_OPTION_DECL},
146 /* Used to print non-joining lines */
147 static struct line uni_blank;
149 /* If nonzero, ignore case when comparing join fields. */
150 static bool ignore_case;
153 static void checkorder (const struct line *, const struct line *, int);
158 if (status != EXIT_SUCCESS)
159 fprintf (stderr, _("Try `%s --help' for more information.\n"),
164 Usage: %s [OPTION]... FILE1 FILE2\n\
168 For each pair of input lines with identical join fields, write a line to\n\
169 standard output. The default join field is the first, delimited\n\
170 by whitespace. When FILE1 or FILE2 (not both) is -, read standard input.\n\
172 -a FILENUM print unpairable lines coming from file FILENUM, where\n\
173 FILENUM is 1 or 2, corresponding to FILE1 or FILE2\n\
174 -e EMPTY replace missing input fields with EMPTY\n\
177 -i, --ignore-case ignore differences in case when comparing fields\n\
178 -j FIELD equivalent to `-1 FIELD -2 FIELD'\n\
179 -o FORMAT obey FORMAT while constructing output line\n\
180 -t CHAR use CHAR as input and output field separator\n\
183 -v FILENUM like -a FILENUM, but suppress joined output lines\n\
184 -1 FIELD join on this FIELD of file 1\n\
185 -2 FIELD join on this FIELD of file 2\n\
186 --check-order check that the input is correctly sorted, even\n\
187 if all input lines are pairable\n\
188 --nocheck-order do not check that the input is correctly sorted\n\
190 fputs (HELP_OPTION_DESCRIPTION, stdout);
191 fputs (VERSION_OPTION_DESCRIPTION, stdout);
194 Unless -t CHAR is given, leading blanks separate fields and are ignored,\n\
195 else fields are separated by CHAR. Any FIELD is a field number counted\n\
196 from 1. FORMAT is one or more comma or blank separated specifications,\n\
197 each being `FILENUM.FIELD' or `0'. Default FORMAT outputs the join field,\n\
198 the remaining fields from FILE1, the remaining fields from FILE2, all\n\
199 separated by CHAR.\n\
201 Important: FILE1 and FILE2 must be sorted on the join fields.\n\
202 E.g., use `sort -k 1b,1' if `join' has no options.\n\
203 If the input is not sorted and some lines cannot be joined, a\n\
204 warning message will be given.\n\
206 emit_bug_reporting_address ();
211 /* Record a field in LINE, with location FIELD and size LEN. */
214 extract_field (struct line *line, char *field, size_t len)
216 if (line->nfields >= line->nfields_allocated)
218 line->fields = X2NREALLOC (line->fields, &line->nfields_allocated);
220 line->fields[line->nfields].beg = field;
221 line->fields[line->nfields].len = len;
225 /* Fill in the `fields' structure in LINE. */
228 xfields (struct line *line)
230 char *ptr = line->buf.buffer;
231 char const *lim = ptr + line->buf.length - 1;
239 for (; (sep = memchr (ptr, tab, lim - ptr)) != NULL; ptr = sep + 1)
240 extract_field (line, ptr, sep - ptr);
244 /* Skip leading blanks before the first field. */
245 while (isblank (to_uchar (*ptr)))
252 for (sep = ptr + 1; sep != lim && ! isblank (to_uchar (*sep)); sep++)
254 extract_field (line, ptr, sep - ptr);
257 for (ptr = sep + 1; ptr != lim && isblank (to_uchar (*ptr)); ptr++)
263 extract_field (line, ptr, lim - ptr);
267 dup_line (const struct line *old)
269 struct line *newline = xmalloc (sizeof *newline);
272 /* Duplicate the buffer. */
273 initbuffer (&newline->buf);
274 newline->buf.buffer = xmalloc (old->buf.size);
275 newline->buf.size = old->buf.size;
276 memcpy (newline->buf.buffer, old->buf.buffer, old->buf.length);
277 newline->buf.length = old->buf.length;
279 /* Duplicate the field positions. */
280 newline->fields = xnmalloc (old->nfields_allocated, sizeof *newline->fields);
281 newline->nfields = old->nfields;
282 newline->nfields_allocated = old->nfields_allocated;
284 for (i = 0; i < old->nfields; i++)
286 newline->fields[i].len = old->fields[i].len;
287 newline->fields[i].beg = newline->buf.buffer + (old->fields[i].beg
294 freeline (struct line *line)
297 free (line->buf.buffer);
298 line->buf.buffer = NULL;
301 /* Read a line from FP into LINE and split it into fields.
302 Return true if successful. */
305 get_line (FILE *fp, struct line *line, int which)
307 initbuffer (&line->buf);
309 if (! readlinebuffer (&line->buf, fp))
312 error (EXIT_FAILURE, errno, _("read error"));
313 free (line->buf.buffer);
314 line->buf.buffer = NULL;
318 line->nfields_allocated = 0;
323 if (prevline[which - 1])
325 checkorder (prevline[which - 1], line, which);
326 freeline (prevline[which - 1]);
327 free (prevline[which - 1]);
329 prevline[which - 1] = dup_line (line);
338 for (i = 0; i < ARRAY_CARDINALITY (prevline); i++)
341 freeline (prevline[i]);
348 initseq (struct seq *seq)
355 /* Read a line from FP and add it to SEQ. Return true if successful. */
358 getseq (FILE *fp, struct seq *seq, int whichfile)
360 if (seq->count == seq->alloc)
361 seq->lines = X2NREALLOC (seq->lines, &seq->alloc);
363 if (get_line (fp, &seq->lines[seq->count], whichfile))
371 /* Read a line from FP and add it to SEQ, as the first item if FIRST is
372 true, else as the next. */
374 advance_seq (FILE *fp, struct seq *seq, bool first, int whichfile)
378 freeline (&seq->lines[0]);
381 return getseq (fp, seq, whichfile);
385 delseq (struct seq *seq)
388 for (i = 0; i < seq->count; i++)
389 if (seq->lines[i].buf.buffer)
390 freeline (&seq->lines[i]);
394 /* Return <0 if the join field in LINE1 compares less than the one in LINE2;
395 >0 if it compares greater; 0 if it compares equal.
396 Report an error and exit if the comparison fails. */
399 keycmp (struct line const *line1, struct line const *line2)
401 /* Start of field to compare in each file. */
406 size_t len2; /* Length of fields to compare. */
409 if (join_field_1 < line1->nfields)
411 beg1 = line1->fields[join_field_1].beg;
412 len1 = line1->fields[join_field_1].len;
420 if (join_field_2 < line2->nfields)
422 beg2 = line2->fields[join_field_2].beg;
423 len2 = line2->fields[join_field_2].len;
432 return len2 == 0 ? 0 : -1;
438 /* FIXME: ignore_case does not work with NLS (in particular,
439 with multibyte chars). */
440 diff = memcasecmp (beg1, beg2, MIN (len1, len2));
445 return xmemcoll (beg1, len1, beg2, len2);
446 diff = memcmp (beg1, beg2, MIN (len1, len2));
451 return len1 < len2 ? -1 : len1 != len2;
456 /* Check that successive input lines PREV and CURRENT from input file
457 WHATFILE are presented in order, unless the user may be relying on
458 the GNU extension that input lines may be out of order if no input
459 lines are unpairable.
461 If the user specified --nocheck-order, the check is not made.
462 If the user specified --check-order, the problem is fatal.
463 Otherwise (the default), the message is simply a warning.
465 A message is printed at most once per input file. */
468 checkorder (const struct line *prev,
469 const struct line *current,
472 if (check_input_order != CHECK_ORDER_DISABLED
473 && ((check_input_order == CHECK_ORDER_ENABLED) || seen_unpairable))
475 if (!issued_disorder_warning[whatfile-1])
477 if (keycmp (prev, current) > 0)
479 error ((check_input_order == CHECK_ORDER_ENABLED ? 1 : 0),
480 0, _("File %d is not in sorted order"), whatfile);
482 /* If we get to here, the message was just a warning, but we
483 want only to issue it once. */
484 issued_disorder_warning[whatfile-1] = true;
492 /* Print field N of LINE if it exists and is nonempty, otherwise
493 `empty_filler' if it is nonempty. */
496 prfield (size_t n, struct line const *line)
500 if (n < line->nfields)
502 len = line->fields[n].len;
504 fwrite (line->fields[n].beg, 1, len, stdout);
505 else if (empty_filler)
506 fputs (empty_filler, stdout);
508 else if (empty_filler)
509 fputs (empty_filler, stdout);
512 /* Print the join of LINE1 and LINE2. */
515 prjoin (struct line const *line1, struct line const *line2)
517 const struct outlist *outlist;
518 char output_separator = tab < 0 ? ' ' : tab;
520 outlist = outlist_head.next;
523 const struct outlist *o;
529 struct line const *line;
533 if (line1 == &uni_blank)
536 field = join_field_2;
541 field = join_field_1;
546 line = (o->file == 1 ? line1 : line2);
549 prfield (field, line);
553 putchar (output_separator);
561 if (line1 == &uni_blank)
563 struct line const *t;
568 prfield (join_field_1, line1);
569 for (i = 0; i < join_field_1 && i < line1->nfields; ++i)
571 putchar (output_separator);
574 for (i = join_field_1 + 1; i < line1->nfields; ++i)
576 putchar (output_separator);
580 for (i = 0; i < join_field_2 && i < line2->nfields; ++i)
582 putchar (output_separator);
585 for (i = join_field_2 + 1; i < line2->nfields; ++i)
587 putchar (output_separator);
594 /* Print the join of the files in FP1 and FP2. */
597 join (FILE *fp1, FILE *fp2)
599 struct seq seq1, seq2;
602 bool eof1, eof2, checktail;
604 /* Read the first line of each file. */
606 getseq (fp1, &seq1, 1);
608 getseq (fp2, &seq2, 2);
610 while (seq1.count && seq2.count)
613 diff = keycmp (&seq1.lines[0], &seq2.lines[0]);
616 if (print_unpairables_1)
617 prjoin (&seq1.lines[0], &uni_blank);
618 advance_seq (fp1, &seq1, true, 1);
619 seen_unpairable = true;
624 if (print_unpairables_2)
625 prjoin (&uni_blank, &seq2.lines[0]);
626 advance_seq (fp2, &seq2, true, 2);
627 seen_unpairable = true;
631 /* Keep reading lines from file1 as long as they continue to
632 match the current line from file2. */
635 if (!advance_seq (fp1, &seq1, false, 1))
641 while (!keycmp (&seq1.lines[seq1.count - 1], &seq2.lines[0]));
643 /* Keep reading lines from file2 as long as they continue to
644 match the current line from file1. */
647 if (!advance_seq (fp2, &seq2, false, 2))
653 while (!keycmp (&seq1.lines[0], &seq2.lines[seq2.count - 1]));
657 for (i = 0; i < seq1.count - 1; ++i)
660 for (j = 0; j < seq2.count - 1; ++j)
661 prjoin (&seq1.lines[i], &seq2.lines[j]);
665 for (i = 0; i < seq1.count - 1; ++i)
666 freeline (&seq1.lines[i]);
669 seq1.lines[0] = seq1.lines[seq1.count - 1];
675 for (i = 0; i < seq2.count - 1; ++i)
676 freeline (&seq2.lines[i]);
679 seq2.lines[0] = seq2.lines[seq2.count - 1];
686 /* If the user did not specify --check-order, and the we read the
687 tail ends of both inputs to verify that they are in order. We
688 skip the rest of the tail once we have issued a warning for that
689 file, unless we actually need to print the unpairable lines. */
690 if (check_input_order != CHECK_ORDER_DISABLED
691 && !(issued_disorder_warning[0] && issued_disorder_warning[1]))
696 if ((print_unpairables_1 || checktail) && seq1.count)
698 if (print_unpairables_1)
699 prjoin (&seq1.lines[0], &uni_blank);
700 freeline (&seq1.lines[0]);
701 seen_unpairable = true;
702 while (get_line (fp1, &line, 1))
704 if (print_unpairables_1)
705 prjoin (&line, &uni_blank);
707 if (issued_disorder_warning[0] && !print_unpairables_1)
712 if ((print_unpairables_2 || checktail) && seq2.count)
714 if (print_unpairables_2)
715 prjoin (&uni_blank, &seq2.lines[0]);
716 freeline (&seq2.lines[0]);
717 seen_unpairable = true;
718 while (get_line (fp2, &line, 2))
720 if (print_unpairables_2)
721 prjoin (&uni_blank, &line);
723 if (issued_disorder_warning[1] && !print_unpairables_2)
732 /* Add a field spec for field FIELD of file FILE to `outlist'. */
735 add_field (int file, size_t field)
739 assert (file == 0 || file == 1 || file == 2);
740 assert (file != 0 || field == 0);
742 o = xmalloc (sizeof *o);
747 /* Add to the end of the list so the fields are in the right order. */
748 outlist_end->next = o;
752 /* Convert a string of decimal digits, STR (the 1-based join field number),
753 to an integral value. Upon successful conversion, return one less
754 (the zero-based field number). Silently convert too-large values
755 to SIZE_MAX - 1. Otherwise, if a value cannot be converted, give a
756 diagnostic and exit. */
759 string_to_join_field (char const *str)
762 unsigned long int val;
763 verify (SIZE_MAX <= ULONG_MAX);
765 strtol_error s_err = xstrtoul (str, NULL, 10, &val, "");
766 if (s_err == LONGINT_OVERFLOW || (s_err == LONGINT_OK && SIZE_MAX < val))
768 else if (s_err != LONGINT_OK || val == 0)
769 error (EXIT_FAILURE, 0, _("invalid field number: %s"), quote (str));
776 /* Convert a single field specifier string, S, to a *FILE_INDEX, *FIELD_INDEX
777 pair. In S, the field index string is 1-based; *FIELD_INDEX is zero-based.
778 If S is valid, return true. Otherwise, give a diagnostic and exit. */
781 decode_field_spec (const char *s, int *file_index, size_t *field_index)
783 /* The first character must be 0, 1, or 2. */
789 /* `0' must be all alone -- no `.FIELD'. */
790 error (EXIT_FAILURE, 0, _("invalid field specifier: %s"), quote (s));
799 error (EXIT_FAILURE, 0, _("invalid field specifier: %s"), quote (s));
800 *file_index = s[0] - '0';
801 *field_index = string_to_join_field (s + 2);
805 error (EXIT_FAILURE, 0,
806 _("invalid file number in field spec: %s"), quote (s));
808 /* Tell gcc -W -Wall that we can't get beyond this point.
809 This avoids a warning (otherwise legit) that the caller's copies
810 of *file_index and *field_index might be used uninitialized. */
817 /* Add the comma or blank separated field spec(s) in STR to `outlist'. */
820 add_field_list (char *str)
828 char const *spec_item = p;
830 p = strpbrk (p, ", \t");
833 decode_field_spec (spec_item, &file_index, &field_index);
834 add_field (file_index, field_index);
839 /* Set the join field *VAR to VAL, but report an error if *VAR is set
840 more than once to incompatible values. */
843 set_join_field (size_t *var, size_t val)
845 if (*var != SIZE_MAX && *var != val)
847 unsigned long int var1 = *var + 1;
848 unsigned long int val1 = val + 1;
849 error (EXIT_FAILURE, 0, _("incompatible join fields %lu, %lu"),
855 /* Status of command-line arguments. */
859 /* This argument must be an operand, i.e., one of the files to be
863 /* This might be the argument of the preceding -j1 or -j2 option,
864 or it might be an operand. */
868 /* This might be the argument of the preceding -o option, or it might be
873 /* Add NAME to the array of input file NAMES with operand statuses
874 OPERAND_STATUS; currently there are NFILES names in the list. */
877 add_file_name (char *name, char *names[2],
878 int operand_status[2], int joption_count[2], int *nfiles,
879 int *prev_optc_status, int *optc_status)
885 bool op0 = (operand_status[0] == MUST_BE_OPERAND);
886 char *arg = names[op0];
887 switch (operand_status[op0])
889 case MUST_BE_OPERAND:
890 error (0, 0, _("extra operand %s"), quote (name));
891 usage (EXIT_FAILURE);
893 case MIGHT_BE_J1_ARG:
895 set_join_field (&join_field_1, string_to_join_field (arg));
898 case MIGHT_BE_J2_ARG:
900 set_join_field (&join_field_2, string_to_join_field (arg));
904 add_field_list (arg);
909 operand_status[0] = operand_status[1];
915 operand_status[n] = *prev_optc_status;
918 if (*prev_optc_status == MIGHT_BE_O_ARG)
919 *optc_status = MIGHT_BE_O_ARG;
923 main (int argc, char **argv)
926 int prev_optc_status = MUST_BE_OPERAND;
927 int operand_status[2];
928 int joption_count[2] = { 0, 0 };
935 initialize_main (&argc, &argv);
936 program_name = argv[0];
937 setlocale (LC_ALL, "");
938 bindtextdomain (PACKAGE, LOCALEDIR);
939 textdomain (PACKAGE);
940 hard_LC_COLLATE = hard_locale (LC_COLLATE);
942 atexit (close_stdout);
943 atexit (free_prevline);
945 print_pairables = true;
946 seen_unpairable = false;
947 issued_disorder_warning[0] = issued_disorder_warning[1] = false;
948 check_input_order = CHECK_ORDER_DEFAULT;
950 while ((optc = getopt_long (argc, argv, "-a:e:i1:2:j:o:t:v:",
954 optc_status = MUST_BE_OPERAND;
959 print_pairables = false;
964 unsigned long int val;
965 if (xstrtoul (optarg, NULL, 10, &val, "") != LONGINT_OK
966 || (val != 1 && val != 2))
967 error (EXIT_FAILURE, 0,
968 _("invalid field number: %s"), quote (optarg));
970 print_unpairables_1 = true;
972 print_unpairables_2 = true;
977 if (empty_filler && ! STREQ (empty_filler, optarg))
978 error (EXIT_FAILURE, 0,
979 _("conflicting empty-field replacement strings"));
980 empty_filler = optarg;
988 set_join_field (&join_field_1, string_to_join_field (optarg));
992 set_join_field (&join_field_2, string_to_join_field (optarg));
996 if ((optarg[0] == '1' || optarg[0] == '2') && !optarg[1]
997 && optarg == argv[optind - 1] + 2)
999 /* The argument was either "-j1" or "-j2". */
1000 bool is_j2 = (optarg[0] == '2');
1001 joption_count[is_j2]++;
1002 optc_status = MIGHT_BE_J1_ARG + is_j2;
1006 set_join_field (&join_field_1, string_to_join_field (optarg));
1007 set_join_field (&join_field_2, join_field_1);
1012 add_field_list (optarg);
1013 optc_status = MIGHT_BE_O_ARG;
1018 unsigned char newtab = optarg[0];
1020 error (EXIT_FAILURE, 0, _("empty tab"));
1023 if (STREQ (optarg, "\\0"))
1026 error (EXIT_FAILURE, 0, _("multi-character tab %s"),
1029 if (0 <= tab && tab != newtab)
1030 error (EXIT_FAILURE, 0, _("incompatible tabs"));
1035 case NOCHECK_ORDER_OPTION:
1036 check_input_order = CHECK_ORDER_DISABLED;
1039 case CHECK_ORDER_OPTION:
1040 check_input_order = CHECK_ORDER_ENABLED;
1043 case 1: /* Non-option argument. */
1044 add_file_name (optarg, names, operand_status, joption_count,
1045 &nfiles, &prev_optc_status, &optc_status);
1048 case_GETOPT_HELP_CHAR;
1050 case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
1053 usage (EXIT_FAILURE);
1056 prev_optc_status = optc_status;
1059 /* Process any operands after "--". */
1060 prev_optc_status = MUST_BE_OPERAND;
1061 while (optind < argc)
1062 add_file_name (argv[optind++], names, operand_status, joption_count,
1063 &nfiles, &prev_optc_status, &optc_status);
1068 error (0, 0, _("missing operand"));
1070 error (0, 0, _("missing operand after %s"), quote (argv[argc - 1]));
1071 usage (EXIT_FAILURE);
1074 /* If "-j1" was specified and it turns out not to have had an argument,
1075 treat it as "-j 1". Likewise for -j2. */
1076 for (i = 0; i < 2; i++)
1077 if (joption_count[i] != 0)
1079 set_join_field (&join_field_1, i);
1080 set_join_field (&join_field_2, i);
1083 if (join_field_1 == SIZE_MAX)
1085 if (join_field_2 == SIZE_MAX)
1088 fp1 = STREQ (names[0], "-") ? stdin : fopen (names[0], "r");
1090 error (EXIT_FAILURE, errno, "%s", names[0]);
1091 fp2 = STREQ (names[1], "-") ? stdin : fopen (names[1], "r");
1093 error (EXIT_FAILURE, errno, "%s", names[1]);
1095 error (EXIT_FAILURE, errno, _("both files cannot be standard input"));
1098 if (fclose (fp1) != 0)
1099 error (EXIT_FAILURE, errno, "%s", names[0]);
1100 if (fclose (fp2) != 0)
1101 error (EXIT_FAILURE, errno, "%s", names[1]);
1103 if (issued_disorder_warning[0] || issued_disorder_warning[1])
1104 exit (EXIT_FAILURE);
1106 exit (EXIT_SUCCESS);