1/*-
2 * Copyright (c) 1991, 1993, 1994
3 *	The Regents of the University of California.  All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * Steve Hayman of the Computer Science Department, Indiana University,
7 * Michiro Hikida and David Goodenough.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 * 1. Redistributions of source code must retain the above copyright
13 *    notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 *    notice, this list of conditions and the following disclaimer in the
16 *    documentation and/or other materials provided with the distribution.
17 * 4. Neither the name of the University nor the names of its contributors
18 *    may be used to endorse or promote products derived from this software
19 *    without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * SUCH DAMAGE.
32 */
33
34#ifndef lint
35static const char copyright[] =
36"@(#) Copyright (c) 1991, 1993, 1994\n\
37	The Regents of the University of California.  All rights reserved.\n";
38#endif /* not lint */
39
40#ifndef lint
41#if 0
42static char sccsid[] = "@(#)join.c	8.6 (Berkeley) 5/4/95";
43#endif
44#endif /* not lint */
45#include <sys/cdefs.h>
46__FBSDID("$FreeBSD$");
47
48#include <sys/param.h>
49
50#include <err.h>
51#include <errno.h>
52#include <limits.h>
53#include <locale.h>
54#include <stdio.h>
55#include <stdlib.h>
56#include <string.h>
57#include <unistd.h>
58#include <wchar.h>
59
60/*
61 * There's a structure per input file which encapsulates the state of the
62 * file.  We repeatedly read lines from each file until we've read in all
63 * the consecutive lines from the file with a common join field.  Then we
64 * compare the set of lines with an equivalent set from the other file.
65 */
66typedef struct {
67	char *line;		/* line */
68	u_long linealloc;	/* line allocated count */
69	char **fields;		/* line field(s) */
70	u_long fieldcnt;	/* line field(s) count */
71	u_long fieldalloc;	/* line field(s) allocated count */
72} LINE;
73
74typedef struct {
75	FILE *fp;		/* file descriptor */
76	u_long joinf;		/* join field (-1, -2, -j) */
77	int unpair;		/* output unpairable lines (-a) */
78	u_long number;		/* 1 for file 1, 2 for file 2 */
79
80	LINE *set;		/* set of lines with same field */
81	int pushbool;		/* if pushback is set */
82	u_long pushback;	/* line on the stack */
83	u_long setcnt;		/* set count */
84	u_long setalloc;	/* set allocated count */
85} INPUT;
86static INPUT input1 = { NULL, 0, 0, 1, NULL, 0, 0, 0, 0 },
87    input2 = { NULL, 0, 0, 2, NULL, 0, 0, 0, 0 };
88
89typedef struct {
90	u_long	filenum;	/* file number */
91	u_long	fieldno;	/* field number */
92} OLIST;
93static OLIST *olist;		/* output field list */
94static u_long olistcnt;		/* output field list count */
95static u_long olistalloc;	/* output field allocated count */
96
97static int joinout = 1;		/* show lines with matched join fields (-v) */
98static int needsep;		/* need separator character */
99static int spans = 1;		/* span multiple delimiters (-t) */
100static char *empty;		/* empty field replacement string (-e) */
101static wchar_t default_tabchar[] = L" \t";
102static wchar_t *tabchar = default_tabchar; /* delimiter characters (-t) */
103
104static int  cmp(LINE *, u_long, LINE *, u_long);
105static void fieldarg(char *);
106static void joinlines(INPUT *, INPUT *);
107static int  mbscoll(const char *, const char *);
108static char *mbssep(char **, const wchar_t *);
109static void obsolete(char **);
110static void outfield(LINE *, u_long, int);
111static void outoneline(INPUT *, LINE *);
112static void outtwoline(INPUT *, LINE *, INPUT *, LINE *);
113static void slurp(INPUT *);
114static wchar_t *towcs(const char *);
115static void usage(void);
116
117int
118main(int argc, char *argv[])
119{
120	INPUT *F1, *F2;
121	int aflag, ch, cval, vflag;
122	char *end;
123
124	setlocale(LC_ALL, "");
125
126	F1 = &input1;
127	F2 = &input2;
128
129	aflag = vflag = 0;
130	obsolete(argv);
131	while ((ch = getopt(argc, argv, "\01a:e:j:1:2:o:t:v:")) != -1) {
132		switch (ch) {
133		case '\01':		/* See comment in obsolete(). */
134			aflag = 1;
135			F1->unpair = F2->unpair = 1;
136			break;
137		case '1':
138			if ((F1->joinf = strtol(optarg, &end, 10)) < 1)
139				errx(1, "-1 option field number less than 1");
140			if (*end)
141				errx(1, "illegal field number -- %s", optarg);
142			--F1->joinf;
143			break;
144		case '2':
145			if ((F2->joinf = strtol(optarg, &end, 10)) < 1)
146				errx(1, "-2 option field number less than 1");
147			if (*end)
148				errx(1, "illegal field number -- %s", optarg);
149			--F2->joinf;
150			break;
151		case 'a':
152			aflag = 1;
153			switch(strtol(optarg, &end, 10)) {
154			case 1:
155				F1->unpair = 1;
156				break;
157			case 2:
158				F2->unpair = 1;
159				break;
160			default:
161				errx(1, "-a option file number not 1 or 2");
162				break;
163			}
164			if (*end)
165				errx(1, "illegal file number -- %s", optarg);
166			break;
167		case 'e':
168			empty = optarg;
169			break;
170		case 'j':
171			if ((F1->joinf = F2->joinf =
172			    strtol(optarg, &end, 10)) < 1)
173				errx(1, "-j option field number less than 1");
174			if (*end)
175				errx(1, "illegal field number -- %s", optarg);
176			--F1->joinf;
177			--F2->joinf;
178			break;
179		case 'o':
180			fieldarg(optarg);
181			break;
182		case 't':
183			spans = 0;
184			if (mbrtowc(&tabchar[0], optarg, MB_LEN_MAX, NULL) !=
185			    strlen(optarg))
186				errx(1, "illegal tab character specification");
187			tabchar[1] = L'\0';
188			break;
189		case 'v':
190			vflag = 1;
191			joinout = 0;
192			switch (strtol(optarg, &end, 10)) {
193			case 1:
194				F1->unpair = 1;
195				break;
196			case 2:
197				F2->unpair = 1;
198				break;
199			default:
200				errx(1, "-v option file number not 1 or 2");
201				break;
202			}
203			if (*end)
204				errx(1, "illegal file number -- %s", optarg);
205			break;
206		case '?':
207		default:
208			usage();
209		}
210	}
211	argc -= optind;
212	argv += optind;
213
214	if (aflag && vflag)
215		errx(1, "the -a and -v options are mutually exclusive");
216
217	if (argc != 2)
218		usage();
219
220	/* Open the files; "-" means stdin. */
221	if (!strcmp(*argv, "-"))
222		F1->fp = stdin;
223	else if ((F1->fp = fopen(*argv, "r")) == NULL)
224		err(1, "%s", *argv);
225	++argv;
226	if (!strcmp(*argv, "-"))
227		F2->fp = stdin;
228	else if ((F2->fp = fopen(*argv, "r")) == NULL)
229		err(1, "%s", *argv);
230	if (F1->fp == stdin && F2->fp == stdin)
231		errx(1, "only one input file may be stdin");
232
233	slurp(F1);
234	slurp(F2);
235	while (F1->setcnt && F2->setcnt) {
236		cval = cmp(F1->set, F1->joinf, F2->set, F2->joinf);
237		if (cval == 0) {
238			/* Oh joy, oh rapture, oh beauty divine! */
239			if (joinout)
240				joinlines(F1, F2);
241			slurp(F1);
242			slurp(F2);
243		} else if (cval < 0) {
244			/* File 1 takes the lead... */
245			if (F1->unpair)
246				joinlines(F1, NULL);
247			slurp(F1);
248		} else {
249			/* File 2 takes the lead... */
250			if (F2->unpair)
251				joinlines(F2, NULL);
252			slurp(F2);
253		}
254	}
255
256	/*
257	 * Now that one of the files is used up, optionally output any
258	 * remaining lines from the other file.
259	 */
260	if (F1->unpair)
261		while (F1->setcnt) {
262			joinlines(F1, NULL);
263			slurp(F1);
264		}
265	if (F2->unpair)
266		while (F2->setcnt) {
267			joinlines(F2, NULL);
268			slurp(F2);
269		}
270	exit(0);
271}
272
273static void
274slurp(INPUT *F)
275{
276	LINE *lp, *lastlp, tmp;
277	size_t len;
278	int cnt;
279	char *bp, *fieldp;
280
281	/*
282	 * Read all of the lines from an input file that have the same
283	 * join field.
284	 */
285	F->setcnt = 0;
286	for (lastlp = NULL;; ++F->setcnt) {
287		/*
288		 * If we're out of space to hold line structures, allocate
289		 * more.  Initialize the structure so that we know that this
290		 * is new space.
291		 */
292		if (F->setcnt == F->setalloc) {
293			cnt = F->setalloc;
294			F->setalloc += 50;
295			if ((F->set = realloc(F->set,
296			    F->setalloc * sizeof(LINE))) == NULL)
297				err(1, NULL);
298			memset(F->set + cnt, 0, 50 * sizeof(LINE));
299
300			/* re-set lastlp in case it moved */
301			if (lastlp != NULL)
302				lastlp = &F->set[F->setcnt - 1];
303		}
304
305		/*
306		 * Get any pushed back line, else get the next line.  Allocate
307		 * space as necessary.  If taking the line from the stack swap
308		 * the two structures so that we don't lose space allocated to
309		 * either structure.  This could be avoided by doing another
310		 * level of indirection, but it's probably okay as is.
311		 */
312		lp = &F->set[F->setcnt];
313		if (F->setcnt)
314			lastlp = &F->set[F->setcnt - 1];
315		if (F->pushbool) {
316			tmp = F->set[F->setcnt];
317			F->set[F->setcnt] = F->set[F->pushback];
318			F->set[F->pushback] = tmp;
319			F->pushbool = 0;
320			continue;
321		}
322		if ((bp = fgetln(F->fp, &len)) == NULL)
323			return;
324		if (lp->linealloc <= len + 1) {
325			lp->linealloc += MAX(100, len + 1 - lp->linealloc);
326			if ((lp->line =
327			    realloc(lp->line, lp->linealloc)) == NULL)
328				err(1, NULL);
329		}
330		memmove(lp->line, bp, len);
331
332		/* Replace trailing newline, if it exists. */
333		if (bp[len - 1] == '\n')
334			lp->line[len - 1] = '\0';
335		else
336			lp->line[len] = '\0';
337		bp = lp->line;
338
339		/* Split the line into fields, allocate space as necessary. */
340		lp->fieldcnt = 0;
341		while ((fieldp = mbssep(&bp, tabchar)) != NULL) {
342			if (spans && *fieldp == '\0')
343				continue;
344			if (lp->fieldcnt == lp->fieldalloc) {
345				lp->fieldalloc += 50;
346				if ((lp->fields = realloc(lp->fields,
347				    lp->fieldalloc * sizeof(char *))) == NULL)
348					err(1, NULL);
349			}
350			lp->fields[lp->fieldcnt++] = fieldp;
351		}
352
353		/* See if the join field value has changed. */
354		if (lastlp != NULL && cmp(lp, F->joinf, lastlp, F->joinf)) {
355			F->pushbool = 1;
356			F->pushback = F->setcnt;
357			break;
358		}
359	}
360}
361
362static char *
363mbssep(char **stringp, const wchar_t *delim)
364{
365	char *s, *tok;
366	const wchar_t *spanp;
367	wchar_t c, sc;
368	size_t n;
369
370	if ((s = *stringp) == NULL)
371		return (NULL);
372	for (tok = s;;) {
373		n = mbrtowc(&c, s, MB_LEN_MAX, NULL);
374		if (n == (size_t)-1 || n == (size_t)-2)
375			errc(1, EILSEQ, NULL);	/* XXX */
376		s += n;
377		spanp = delim;
378		do {
379			if ((sc = *spanp++) == c) {
380				if (c == 0)
381					s = NULL;
382				else
383					s[-n] = '\0';
384				*stringp = s;
385				return (tok);
386			}
387		} while (sc != 0);
388	}
389}
390
391static int
392cmp(LINE *lp1, u_long fieldno1, LINE *lp2, u_long fieldno2)
393{
394	if (lp1->fieldcnt <= fieldno1)
395		return (lp2->fieldcnt <= fieldno2 ? 0 : 1);
396	if (lp2->fieldcnt <= fieldno2)
397		return (-1);
398	return (mbscoll(lp1->fields[fieldno1], lp2->fields[fieldno2]));
399}
400
401static int
402mbscoll(const char *s1, const char *s2)
403{
404	wchar_t *w1, *w2;
405	int ret;
406
407	if (MB_CUR_MAX == 1)
408		return (strcoll(s1, s2));
409	if ((w1 = towcs(s1)) == NULL || (w2 = towcs(s2)) == NULL)
410		err(1, NULL);	/* XXX */
411	ret = wcscoll(w1, w2);
412	free(w1);
413	free(w2);
414	return (ret);
415}
416
417static wchar_t *
418towcs(const char *s)
419{
420	wchar_t *wcs;
421	size_t n;
422
423	if ((n = mbsrtowcs(NULL, &s, 0, NULL)) == (size_t)-1)
424		return (NULL);
425	if ((wcs = malloc((n + 1) * sizeof(*wcs))) == NULL)
426		return (NULL);
427	mbsrtowcs(wcs, &s, n + 1, NULL);
428	return (wcs);
429}
430
431static void
432joinlines(INPUT *F1, INPUT *F2)
433{
434	u_long cnt1, cnt2;
435
436	/*
437	 * Output the results of a join comparison.  The output may be from
438	 * either file 1 or file 2 (in which case the first argument is the
439	 * file from which to output) or from both.
440	 */
441	if (F2 == NULL) {
442		for (cnt1 = 0; cnt1 < F1->setcnt; ++cnt1)
443			outoneline(F1, &F1->set[cnt1]);
444		return;
445	}
446	for (cnt1 = 0; cnt1 < F1->setcnt; ++cnt1)
447		for (cnt2 = 0; cnt2 < F2->setcnt; ++cnt2)
448			outtwoline(F1, &F1->set[cnt1], F2, &F2->set[cnt2]);
449}
450
451static void
452outoneline(INPUT *F, LINE *lp)
453{
454	u_long cnt;
455
456	/*
457	 * Output a single line from one of the files, according to the
458	 * join rules.  This happens when we are writing unmatched single
459	 * lines.  Output empty fields in the right places.
460	 */
461	if (olist)
462		for (cnt = 0; cnt < olistcnt; ++cnt) {
463			if (olist[cnt].filenum == (unsigned)F->number)
464				outfield(lp, olist[cnt].fieldno, 0);
465			else if (olist[cnt].filenum == 0)
466				outfield(lp, F->joinf, 0);
467			else
468				outfield(lp, 0, 1);
469		}
470	else
471		for (cnt = 0; cnt < lp->fieldcnt; ++cnt)
472			outfield(lp, cnt, 0);
473	(void)printf("\n");
474	if (ferror(stdout))
475		err(1, "stdout");
476	needsep = 0;
477}
478
479static void
480outtwoline(INPUT *F1, LINE *lp1, INPUT *F2, LINE *lp2)
481{
482	u_long cnt;
483
484	/* Output a pair of lines according to the join list (if any). */
485	if (olist)
486		for (cnt = 0; cnt < olistcnt; ++cnt)
487			if (olist[cnt].filenum == 0) {
488				if (lp1->fieldcnt >= F1->joinf)
489					outfield(lp1, F1->joinf, 0);
490				else
491					outfield(lp2, F2->joinf, 0);
492			} else if (olist[cnt].filenum == 1)
493				outfield(lp1, olist[cnt].fieldno, 0);
494			else /* if (olist[cnt].filenum == 2) */
495				outfield(lp2, olist[cnt].fieldno, 0);
496	else {
497		/*
498		 * Output the join field, then the remaining fields from F1
499		 * and F2.
500		 */
501		outfield(lp1, F1->joinf, 0);
502		for (cnt = 0; cnt < lp1->fieldcnt; ++cnt)
503			if (F1->joinf != cnt)
504				outfield(lp1, cnt, 0);
505		for (cnt = 0; cnt < lp2->fieldcnt; ++cnt)
506			if (F2->joinf != cnt)
507				outfield(lp2, cnt, 0);
508	}
509	(void)printf("\n");
510	if (ferror(stdout))
511		err(1, "stdout");
512	needsep = 0;
513}
514
515static void
516outfield(LINE *lp, u_long fieldno, int out_empty)
517{
518	if (needsep++)
519		(void)printf("%lc", (wint_t)*tabchar);
520	if (!ferror(stdout)) {
521		if (lp->fieldcnt <= fieldno || out_empty) {
522			if (empty != NULL)
523				(void)printf("%s", empty);
524		} else {
525			if (*lp->fields[fieldno] == '\0')
526				return;
527			(void)printf("%s", lp->fields[fieldno]);
528		}
529	}
530	if (ferror(stdout))
531		err(1, "stdout");
532}
533
534/*
535 * Convert an output list argument "2.1, 1.3, 2.4" into an array of output
536 * fields.
537 */
538static void
539fieldarg(char *option)
540{
541	u_long fieldno, filenum;
542	char *end, *token;
543
544	while ((token = strsep(&option, ", \t")) != NULL) {
545		if (*token == '\0')
546			continue;
547		if (token[0] == '0')
548			filenum = fieldno = 0;
549		else if ((token[0] == '1' || token[0] == '2') &&
550		    token[1] == '.') {
551			filenum = token[0] - '0';
552			fieldno = strtol(token + 2, &end, 10);
553			if (*end)
554				errx(1, "malformed -o option field");
555			if (fieldno == 0)
556				errx(1, "field numbers are 1 based");
557			--fieldno;
558		} else
559			errx(1, "malformed -o option field");
560		if (olistcnt == olistalloc) {
561			olistalloc += 50;
562			if ((olist = realloc(olist,
563			    olistalloc * sizeof(OLIST))) == NULL)
564				err(1, NULL);
565		}
566		olist[olistcnt].filenum = filenum;
567		olist[olistcnt].fieldno = fieldno;
568		++olistcnt;
569	}
570}
571
572static void
573obsolete(char **argv)
574{
575	size_t len;
576	char **p, *ap, *t;
577
578	while ((ap = *++argv) != NULL) {
579		/* Return if "--". */
580		if (ap[0] == '-' && ap[1] == '-')
581			return;
582		/* skip if not an option */
583		if (ap[0] != '-')
584			continue;
585		switch (ap[1]) {
586		case 'a':
587			/*
588			 * The original join allowed "-a", which meant the
589			 * same as -a1 plus -a2.  POSIX 1003.2, Draft 11.2
590			 * only specifies this as "-a 1" and "a -2", so we
591			 * have to use another option flag, one that is
592			 * unlikely to ever be used or accidentally entered
593			 * on the command line.  (Well, we could reallocate
594			 * the argv array, but that hardly seems worthwhile.)
595			 */
596			if (ap[2] == '\0' && (argv[1] == NULL ||
597			    (strcmp(argv[1], "1") != 0 &&
598			    strcmp(argv[1], "2") != 0))) {
599				ap[1] = '\01';
600				warnx("-a option used without an argument; "
601				    "reverting to historical behavior");
602			}
603			break;
604		case 'j':
605			/*
606			 * The original join allowed "-j[12] arg" and "-j arg".
607			 * Convert the former to "-[12] arg".  Don't convert
608			 * the latter since getopt(3) can handle it.
609			 */
610			switch(ap[2]) {
611			case '1':
612				if (ap[3] != '\0')
613					goto jbad;
614				ap[1] = '1';
615				ap[2] = '\0';
616				break;
617			case '2':
618				if (ap[3] != '\0')
619					goto jbad;
620				ap[1] = '2';
621				ap[2] = '\0';
622				break;
623			case '\0':
624				break;
625			default:
626jbad:				errx(1, "illegal option -- %s", ap);
627				usage();
628			}
629			break;
630		case 'o':
631			/*
632			 * The original join allowed "-o arg arg".
633			 * Convert to "-o arg -o arg".
634			 */
635			if (ap[2] != '\0')
636				break;
637			for (p = argv + 2; *p; ++p) {
638				if (p[0][0] == '0' || ((p[0][0] != '1' &&
639				    p[0][0] != '2') || p[0][1] != '.'))
640					break;
641				len = strlen(*p);
642				if (len - 2 != strspn(*p + 2, "0123456789"))
643					break;
644				if ((t = malloc(len + 3)) == NULL)
645					err(1, NULL);
646				t[0] = '-';
647				t[1] = 'o';
648				memmove(t + 2, *p, len + 1);
649				*p = t;
650			}
651			argv = p - 1;
652			break;
653		}
654	}
655}
656
657static void
658usage(void)
659{
660	(void)fprintf(stderr, "%s %s\n%s\n",
661	    "usage: join [-a fileno | -v fileno ] [-e string] [-1 field]",
662	    "[-2 field]",
663		"            [-o list] [-t char] file1 file2");
664	exit(1);
665}
666