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