1/* See LICENSE file for copyright and license details. */
2
3#include <ctype.h>
4#include <stdint.h>
5#include <stdio.h>
6#include <stdlib.h>
7#include <string.h>
8
9#include "text.h"
10#include "utf.h"
11#include "util.h"
12
13enum {
14 INIT = 1,
15 GROW = 2,
16};
17
18enum {
19 EXPAND = 0,
20 RESET = 1,
21};
22
23enum {
24 FIELD_ERROR = -2,
25};
26
27struct field {
28 char *s;
29 size_t len;
30};
31
32struct jline {
33 struct line text;
34 size_t nf;
35 size_t maxf;
36 struct field *fields;
37};
38
39struct spec {
40 size_t fileno;
41 size_t fldno;
42};
43
44struct outlist {
45 size_t ns;
46 size_t maxs;
47 struct spec **specs;
48};
49
50struct span {
51 size_t nl;
52 size_t maxl;
53 struct jline **lines;
54};
55
56static char *sep = NULL;
57static char *replace = NULL;
58static const char defaultofs = ' ';
59static const int jfield = 1; /* POSIX default join field */
60static int unpairsa = 0, unpairsb = 0;
61static int oflag = 0;
62static int pairs = 1;
63static size_t seplen;
64static struct outlist output;
65
66static void
67usage(void)
68{
69 eprintf(
70 "usage: %s [-1 field] [-2 field] [-o list] [-e string] "
71 "[-a | -v fileno] [-t delim] file1 file2\n",
72 argv0
73 );
74}
75
76static void
77prfield(struct field *fp)
78{
79 if (fwrite(fp->s, 1, fp->len, stdout) != fp->len)
80 eprintf("fwrite:");
81}
82
83static void
84prsep(void)
85{
86 if (sep)
87 fwrite(sep, 1, seplen, stdout);
88 else
89 putchar(defaultofs);
90}
91
92static void
93swaplines(struct jline *la, struct jline *lb)
94{
95 struct jline tmp;
96
97 tmp = *la;
98 *la = *lb;
99 *lb = tmp;
100}
101
102static void
103prjoin(struct jline *la, struct jline *lb, size_t jfa, size_t jfb)
104{
105 struct spec *sp;
106 struct field *joinfield;
107 size_t i;
108
109 if (jfa >= la->nf || jfb >= lb->nf)
110 return;
111
112 joinfield = &la->fields[jfa];
113
114 if (oflag) {
115 for (i = 0; i < output.ns; i++) {
116 sp = output.specs[i];
117
118 if (sp->fileno == 1) {
119 if (sp->fldno < la->nf)
120 prfield(&la->fields[sp->fldno]);
121 else if (replace)
122 fputs(replace, stdout);
123 } else if (sp->fileno == 2) {
124 if (sp->fldno < lb->nf)
125 prfield(&lb->fields[sp->fldno]);
126 else if (replace)
127 fputs(replace, stdout);
128 } else if (sp->fileno == 0) {
129 prfield(joinfield);
130 }
131
132 if (i < output.ns - 1)
133 prsep();
134 }
135 } else {
136 prfield(joinfield);
137 prsep();
138
139 for (i = 0; i < la->nf; i++) {
140 if (i != jfa) {
141 prfield(&la->fields[i]);
142 prsep();
143 }
144 }
145 for (i = 0; i < lb->nf; i++) {
146 if (i != jfb) {
147 prfield(&lb->fields[i]);
148 if (i < lb->nf - 1)
149 prsep();
150 }
151 }
152 }
153 putchar('\n');
154}
155
156static void
157prline(struct jline *lp)
158{
159 if (fwrite(lp->text.data, 1, lp->text.len, stdout) != lp->text.len)
160 eprintf("fwrite:");
161 putchar('\n');
162}
163
164static int
165jlinecmp(struct jline *la, struct jline *lb, size_t jfa, size_t jfb)
166{
167 int status;
168
169 /* return FIELD_ERROR if both lines are short */
170 if (jfa >= la->nf) {
171 status = (jfb >= lb->nf) ? FIELD_ERROR : -1;
172 } else if (jfb >= lb->nf) {
173 status = 1;
174 } else {
175 status =
176 memcmp(la->fields[jfa].s, lb->fields[jfb].s, MAX(la->fields[jfa].len, lb->fields[jfb].len));
177 LIMIT(status, -1, 1);
178 }
179
180 return status;
181}
182
183static void
184addfield(struct jline *lp, char *sp, size_t len)
185{
186 if (lp->nf >= lp->maxf) {
187 lp->fields = ereallocarray(lp->fields, (GROW * lp->maxf), sizeof(struct field));
188 lp->maxf *= GROW;
189 }
190 lp->fields[lp->nf].s = sp;
191 lp->fields[lp->nf].len = len;
192 lp->nf++;
193}
194
195static void
196prspanjoin(struct span *spa, struct span *spb, size_t jfa, size_t jfb)
197{
198 size_t i, j;
199
200 for (i = 0; i < (spa->nl - 1); i++)
201 for (j = 0; j < (spb->nl - 1); j++)
202 prjoin(spa->lines[i], spb->lines[j], jfa, jfb);
203}
204
205static struct jline *
206makeline(char *s, size_t len)
207{
208 struct jline *lp;
209 char *tmp;
210 size_t i, end;
211
212 if (s[len - 1] == '\n')
213 s[--len] = '\0';
214
215 lp = ereallocarray(NULL, INIT, sizeof(struct jline));
216 lp->text.data = s;
217 lp->text.len = len;
218 lp->fields = ereallocarray(NULL, INIT, sizeof(struct field));
219 lp->nf = 0;
220 lp->maxf = INIT;
221
222 for (i = 0; i < lp->text.len && isblank(lp->text.data[i]); i++)
223 ;
224 while (i < lp->text.len) {
225 if (sep) {
226 if ((lp->text.len - i) < seplen
227 || !(tmp = memmem(lp->text.data + i, lp->text.len - i, sep, seplen))) {
228 goto eol;
229 }
230 end = tmp - lp->text.data;
231 addfield(lp, lp->text.data + i, end - i);
232 i = end + seplen;
233 } else {
234 for (end = i; !(isblank(lp->text.data[end])); end++) {
235 if (end + 1 == lp->text.len)
236 goto eol;
237 }
238 addfield(lp, lp->text.data + i, end - i);
239 for (i = end; isblank(lp->text.data[i]); i++)
240 ;
241 }
242 }
243eol:
244 addfield(lp, lp->text.data + i, lp->text.len - i);
245
246 return lp;
247}
248
249static int
250addtospan(struct span *sp, FILE *fp, int reset)
251{
252 char *newl = NULL;
253 ssize_t len;
254 size_t size = 0;
255
256 if ((len = getline(&newl, &size, fp)) < 0) {
257 if (ferror(fp))
258 eprintf("getline:");
259 else
260 return 0;
261 }
262
263 if (reset)
264 sp->nl = 0;
265
266 if (sp->nl >= sp->maxl) {
267 sp->lines = ereallocarray(sp->lines, (GROW * sp->maxl), sizeof(struct jline *));
268 sp->maxl *= GROW;
269 }
270
271 sp->lines[sp->nl] = makeline(newl, len);
272 sp->nl++;
273 return 1;
274}
275
276static void
277initspan(struct span *sp)
278{
279 sp->nl = 0;
280 sp->maxl = INIT;
281 sp->lines = ereallocarray(NULL, INIT, sizeof(struct jline *));
282}
283
284static void
285freespan(struct span *sp)
286{
287 size_t i;
288
289 for (i = 0; i < sp->nl; i++) {
290 free(sp->lines[i]->fields);
291 free(sp->lines[i]->text.data);
292 }
293 free(sp->lines);
294}
295
296static void
297initolist(struct outlist *olp)
298{
299 olp->ns = 0;
300 olp->maxs = 1;
301 olp->specs = ereallocarray(NULL, INIT, sizeof(struct spec *));
302}
303
304static void
305addspec(struct outlist *olp, struct spec *sp)
306{
307 if (olp->ns >= olp->maxs) {
308 olp->specs = ereallocarray(olp->specs, (GROW * olp->maxs), sizeof(struct spec *));
309 olp->maxs *= GROW;
310 }
311 olp->specs[olp->ns] = sp;
312 olp->ns++;
313}
314
315static struct spec *
316makespec(char *s)
317{
318 struct spec *sp;
319 int fileno;
320 size_t fldno;
321
322 if (!strcmp(s, "0")) { /* join field must be 0 and nothing else */
323 fileno = 0;
324 fldno = 0;
325 } else if ((s[0] == '1' || s[0] == '2') && s[1] == '.') {
326 fileno = s[0] - '0';
327 fldno =
328 estrtonum(&s[2], 1, MIN((unsigned long long)LLONG_MAX, (unsigned long long)SIZE_MAX)) - 1;
329 } else {
330 eprintf("%s: invalid format\n", s);
331 }
332
333 sp = ereallocarray(NULL, INIT, sizeof(struct spec));
334 sp->fileno = fileno;
335 sp->fldno = fldno;
336 return sp;
337}
338
339static void
340makeolist(struct outlist *olp, char *s)
341{
342 char *item, *sp;
343 sp = s;
344
345 while (sp) {
346 item = sp;
347 sp = strpbrk(sp, ", \t");
348 if (sp)
349 *sp++ = '\0';
350 addspec(olp, makespec(item));
351 }
352}
353
354static void
355freespecs(struct outlist *olp)
356{
357 size_t i;
358
359 for (i = 0; i < olp->ns; i++)
360 free(olp->specs[i]);
361}
362
363static void
364join(FILE *fa, FILE *fb, size_t jfa, size_t jfb)
365{
366 struct span spa, spb;
367 int cmp, eofa, eofb;
368
369 initspan(&spa);
370 initspan(&spb);
371 cmp = eofa = eofb = 0;
372
373 addtospan(&spa, fa, RESET);
374 addtospan(&spb, fb, RESET);
375
376 while (spa.nl && spb.nl) {
377 if ((cmp = jlinecmp(spa.lines[0], spb.lines[0], jfa, jfb)) < 0) {
378 if (unpairsa)
379 prline(spa.lines[0]);
380 if (!addtospan(&spa, fa, RESET)) {
381 if (unpairsb) { /* a is EOF'd; print the rest of
382 b */
383 do
384 prline(spb.lines[0]);
385 while (addtospan(&spb, fb, RESET));
386 }
387 eofa = eofb = 1;
388 } else {
389 continue;
390 }
391 } else if (cmp > 0) {
392 if (unpairsb)
393 prline(spb.lines[0]);
394 if (!addtospan(&spb, fb, RESET)) {
395 if (unpairsa) { /* b is EOF'd; print the rest of
396 a */
397 do
398 prline(spa.lines[0]);
399 while (addtospan(&spa, fa, RESET));
400 }
401 eofa = eofb = 1;
402 } else {
403 continue;
404 }
405 } else if (cmp == 0) {
406 /* read all consecutive matching lines from a */
407 do {
408 if (!addtospan(&spa, fa, EXPAND)) {
409 eofa = 1;
410 spa.nl++;
411 break;
412 }
413 } while (jlinecmp(spa.lines[spa.nl - 1], spb.lines[0], jfa, jfb) == 0);
414
415 /* read all consecutive matching lines from b */
416 do {
417 if (!addtospan(&spb, fb, EXPAND)) {
418 eofb = 1;
419 spb.nl++;
420 break;
421 }
422 } while (jlinecmp(spa.lines[0], spb.lines[spb.nl - 1], jfa, jfb) == 0);
423
424 if (pairs)
425 prspanjoin(&spa, &spb, jfa, jfb);
426
427 } else { /* FIELD_ERROR: both lines lacked join fields */
428 if (unpairsa)
429 prline(spa.lines[0]);
430 if (unpairsb)
431 prline(spb.lines[0]);
432 eofa = addtospan(&spa, fa, RESET) ? 0 : 1;
433 eofb = addtospan(&spb, fb, RESET) ? 0 : 1;
434 if (!eofa && !eofb)
435 continue;
436 }
437
438 if (eofa) {
439 spa.nl = 0;
440 } else {
441 swaplines(spa.lines[0], spa.lines[spa.nl - 1]); /* ugly */
442 spa.nl = 1;
443 }
444
445 if (eofb) {
446 spb.nl = 0;
447 } else {
448 swaplines(spb.lines[0], spb.lines[spb.nl - 1]); /* ugly */
449 spb.nl = 1;
450 }
451 }
452 freespan(&spa);
453 freespan(&spb);
454}
455
456// ?man join: join lines on common field
457// ?man join lines of two sorted files on a common field
458int
459main(int argc, char *argv[])
460{
461 size_t jf[2] = {
462 jfield,
463 jfield,
464 };
465 FILE *fp[2];
466 int ret = 0, n;
467 char *fno;
468
469 ARGBEGIN
470 {
471 // ?man -1:num: specify option flag
472 case '1':
473 jf[0] = estrtonum(
474 EARGF(usage()), 1, MIN((unsigned long long)LLONG_MAX, (unsigned long long)SIZE_MAX)
475 );
476 break;
477 // ?man -2:num: specify option flag
478 case '2':
479 jf[1] = estrtonum(
480 EARGF(usage()), 1, MIN((unsigned long long)LLONG_MAX, (unsigned long long)SIZE_MAX)
481 );
482 break;
483 // ?man -a:str: print or show all entries
484 case 'a':
485 fno = EARGF(usage());
486 if (strcmp(fno, "1") == 0)
487 unpairsa = 1;
488 else if (strcmp(fno, "2") == 0)
489 unpairsb = 1;
490 else
491 usage();
492 break;
493 // ?man -e:str: specify expression or pattern
494 case 'e':
495 replace = EARGF(usage());
496 break;
497 // ?man -o:str: specify output file
498 case 'o':
499 oflag = 1;
500 initolist(&output);
501 makeolist(&output, EARGF(usage()));
502 break;
503 // ?man -t:str: sort or specify timestamp
504 case 't':
505 sep = EARGF(usage());
506 break;
507 // ?man -v:str: verbose mode; show progress
508 case 'v':
509 pairs = 0;
510 fno = EARGF(usage());
511 if (strcmp(fno, "1") == 0)
512 unpairsa = 1;
513 else if (strcmp(fno, "2") == 0)
514 unpairsb = 1;
515 else
516 usage();
517 break;
518 default:
519 usage();
520 }
521 ARGEND
522
523 if (sep)
524 seplen = unescape(sep);
525
526 if (argc != 2)
527 usage();
528
529 for (n = 0; n < 2; n++) {
530 if (!strcmp(argv[n], "-")) {
531 argv[n] = "<stdin>";
532 fp[n] = stdin;
533 } else if (!(fp[n] = fopen(argv[n], "r"))) {
534 eprintf("fopen %s:", argv[n]);
535 }
536 }
537
538 jf[0]--;
539 jf[1]--;
540
541 join(fp[0], fp[1], jf[0], jf[1]);
542
543 if (oflag)
544 freespecs(&output);
545
546 if (fshut(fp[0], argv[0]) | (fp[0] != fp[1] && fshut(fp[1], argv[1])) | fshut(stdout, "<stdout>"))
547 ret = 2;
548
549 return ret;
550}
