1/* See LICENSE file for copyright and license details. */
2
3#include "queue.h"
4#include "text.h"
5#include "utf.h"
6#include "util.h"
7
8#include <ctype.h>
9#include <stdio.h>
10#include <stdlib.h>
11#include <string.h>
12
13struct keydef {
14 int start_column;
15 int end_column;
16 int start_char;
17 int end_char;
18 int flags;
19 TAILQ_ENTRY(keydef) entry;
20};
21
22struct column {
23 struct line line;
24 size_t cap;
25};
26
27enum {
28 MOD_N = 1 << 0,
29 MOD_STARTB = 1 << 1,
30 MOD_ENDB = 1 << 2,
31 MOD_R = 1 << 3,
32 MOD_D = 1 << 4,
33 MOD_F = 1 << 5,
34 MOD_I = 1 << 6,
35};
36
37static TAILQ_HEAD(kdhead, keydef) kdhead = TAILQ_HEAD_INITIALIZER(kdhead);
38
39static int Cflag = 0, cflag = 0, uflag = 0;
40#if FEATURE_SORT_BIG
41static int zflag = 0;
42#endif
43#if FEATURE_SORT_STABLE
44static int sflag = 0;
45#endif
46static char *fieldsep = NULL;
47static size_t fieldseplen = 0;
48static struct column col1, col2;
49
50static void
51skipblank(struct line *a)
52{
53 while (a->len && (*(a->data) == ' ' || *(a->data) == '\t')) {
54 a->data++;
55 a->len--;
56 }
57}
58
59static void
60skipnonblank(struct line *a)
61{
62 while (a->len && (*(a->data) != '\n' && *(a->data) != ' ' && *(a->data) != '\t')) {
63 a->data++;
64 a->len--;
65 }
66}
67
68static void
69skipcolumn(struct line *a, int skip_to_next_col)
70{
71 char *s;
72
73 if (fieldsep) {
74 if ((s = memmem(a->data, a->len, fieldsep, fieldseplen))) {
75 if (skip_to_next_col)
76 s += fieldseplen;
77 a->len -= s - a->data;
78 a->data = s;
79 } else {
80 a->data += a->len - 1;
81 a->len = 1;
82 }
83 } else {
84 skipblank(a);
85 skipnonblank(a);
86 }
87}
88
89static void
90columns(struct line *line, const struct keydef *kd, struct column *col)
91{
92 Rune r;
93 struct line start, end;
94 size_t utflen, rlen;
95 int i;
96
97 start.data = line->data;
98 start.len = line->len;
99 for (i = 1; i < kd->start_column; i++)
100 skipcolumn(&start, 1);
101 if (kd->flags & MOD_STARTB)
102 skipblank(&start);
103 for (utflen = 0; start.len > 1 && utflen < (size_t)(kd->start_char - 1);) {
104 rlen = chartorune(&r, start.data);
105 start.data += rlen;
106 start.len -= rlen;
107 utflen++;
108 }
109
110 end.data = line->data;
111 end.len = line->len;
112 if (kd->end_column) {
113 for (i = 1; i < kd->end_column; i++)
114 skipcolumn(&end, 1);
115 if (kd->flags & MOD_ENDB)
116 skipblank(&end);
117 if (kd->end_char) {
118 for (utflen = 0; end.len > 1 && utflen < (size_t)kd->end_char;) {
119 rlen = chartorune(&r, end.data);
120 end.data += rlen;
121 end.len -= rlen;
122 utflen++;
123 }
124 } else {
125 skipcolumn(&end, 0);
126 }
127 } else {
128 end.data += end.len - 1;
129 end.len = 1;
130 }
131 col->line.len = MAX(0, end.data - start.data);
132 if (!(col->line.data) || col->cap < col->line.len + 1) {
133 free(col->line.data);
134 col->line.data = emalloc(col->line.len + 1);
135 col->cap = col->line.len + 1;
136 }
137 memcpy(col->line.data, start.data, col->line.len);
138 col->line.data[col->line.len] = '\0';
139}
140
141static int
142skipmodcmp(struct line *a, struct line *b, int flags)
143{
144 Rune r1, r2;
145 size_t offa = 0, offb = 0;
146
147 do {
148 offa += chartorune(&r1, a->data + offa);
149 offb += chartorune(&r2, b->data + offb);
150
151 if (flags & MOD_D && flags & MOD_I) {
152 while (offa < a->len && ((!isblankrune(r1) && !isalnumrune(r1)) || (!isprintrune(r1))))
153 offa += chartorune(&r1, a->data + offa);
154 while (offb < b->len && ((!isblankrune(r2) && !isalnumrune(r2)) || (!isprintrune(r2))))
155 offb += chartorune(&r2, b->data + offb);
156 } else if (flags & MOD_D) {
157 while (offa < a->len && !isblankrune(r1) && !isalnumrune(r1))
158 offa += chartorune(&r1, a->data + offa);
159 while (offb < b->len && !isblankrune(r2) && !isalnumrune(r2))
160 offb += chartorune(&r2, b->data + offb);
161 } else if (flags & MOD_I) {
162 while (offa < a->len && !isprintrune(r1))
163 offa += chartorune(&r1, a->data + offa);
164 while (offb < b->len && !isprintrune(r2))
165 offb += chartorune(&r2, b->data + offb);
166 }
167 if (flags & MOD_F) {
168 r1 = toupperrune(r1);
169 r2 = toupperrune(r2);
170 }
171 } while (r1 && r1 == r2);
172
173 return r1 - r2;
174}
175
176#if FEATURE_SORT_BIG
177static void
178getlines_z(FILE *fp, struct linebuf *b)
179{
180 char *line = NULL;
181 size_t size = 0, linelen = 0;
182 ssize_t len;
183
184 while ((len = getdelim(&line, &size, '\0', fp)) > 0) {
185 if (++b->nlines > b->capacity) {
186 b->capacity += 512;
187 b->lines = ereallocarray(b->lines, b->capacity, sizeof(*b->lines));
188 }
189 linelen = len;
190 b->lines[b->nlines - 1].data = memcpy(emalloc(linelen + 1), line, linelen + 1);
191 b->lines[b->nlines - 1].len = linelen;
192 }
193 free(line);
194 if (b->lines && b->nlines && linelen && b->lines[b->nlines - 1].data[linelen - 1] != '\0') {
195 b->lines[b->nlines - 1].data = erealloc(b->lines[b->nlines - 1].data, linelen + 2);
196 b->lines[b->nlines - 1].data[linelen] = '\0';
197 b->lines[b->nlines - 1].data[linelen + 1] = '\0';
198 b->lines[b->nlines - 1].len++;
199 }
200}
201#endif
202
203static int
204slinecmp(struct line *a, struct line *b)
205{
206 int res = 0;
207 double x, y;
208 struct keydef *kd;
209
210 TAILQ_FOREACH(kd, &kdhead, entry)
211 {
212 columns(a, kd, &col1);
213 columns(b, kd, &col2);
214
215 /* if -u is given, don't use default key definition
216 * unless it is the only one */
217 if (uflag && kd == TAILQ_LAST(&kdhead, kdhead)
218 && TAILQ_LAST(&kdhead, kdhead) != TAILQ_FIRST(&kdhead)) {
219 res = 0;
220 } else if (kd->flags & MOD_N) {
221 x = strtod(col1.line.data, NULL);
222 y = strtod(col2.line.data, NULL);
223 res = (x < y) ? -1 : (x > y);
224 } else if (kd->flags & (MOD_D | MOD_F | MOD_I)) {
225 res = skipmodcmp(&col1.line, &col2.line, kd->flags);
226 } else {
227 res = linecmp(&col1.line, &col2.line);
228 }
229
230 if (kd->flags & MOD_R)
231 res = -res;
232 if (res)
233 break;
234 }
235
236 return res;
237}
238
239#if FEATURE_SORT_STABLE
240struct sort_item {
241 struct line line;
242 size_t index;
243};
244
245static int
246slinecmp_stable(const struct sort_item *a, const struct sort_item *b)
247{
248 int res = slinecmp((struct line *)&a->line, (struct line *)&b->line);
249 if (res == 0)
250 return (a->index < b->index) ? -1 : 1;
251 return res;
252}
253#endif
254
255static int
256check(FILE *fp, const char *fname)
257{
258 static struct line prev, cur, tmp;
259 static size_t prevsize, cursize, tmpsize;
260 ssize_t len;
261 int delim = '\n';
262
263#if FEATURE_SORT_BIG
264 if (zflag)
265 delim = '\0';
266#endif
267
268 if (!prev.data) {
269 if ((len = getdelim(&prev.data, &prevsize, delim, fp)) < 0) {
270 if (feof(fp))
271 return 0;
272 eprintf("getdelim:");
273 }
274 prev.len = len;
275 }
276 while ((len = getdelim(&cur.data, &cursize, delim, fp)) > 0) {
277 cur.len = len;
278 if (uflag > slinecmp(&cur, &prev)) {
279 if (!Cflag) {
280 weprintf("disorder %s: ", fname);
281 fwrite(cur.data, 1, cur.len, stderr);
282 }
283 return 1;
284 }
285 tmp = cur;
286 tmpsize = cursize;
287 cur = prev;
288 cursize = prevsize;
289 prev = tmp;
290 prevsize = tmpsize;
291 }
292
293 return 0;
294}
295
296static int
297parse_flags(char **s, int *flags, int bflag)
298{
299 while (isalpha((int)**s)) {
300 switch (*((*s)++)) {
301 // ?man -b: specify block size or base directory
302 case 'b':
303 *flags |= bflag;
304 break;
305 // ?man -d: specify directory
306 case 'd':
307 *flags |= MOD_D;
308 break;
309 // ?man -f: force the operation
310 case 'f':
311 *flags |= MOD_F;
312 break;
313 // ?man -i: interactive mode or prompt for confirmation
314 case 'i':
315 *flags |= MOD_I;
316 break;
317 // ?man -n: print line numbers or counts
318 case 'n':
319 *flags |= MOD_N;
320 break;
321 // ?man -r: operate recursively
322 case 'r':
323 *flags |= MOD_R;
324 break;
325 default:
326 return -1;
327 }
328 }
329
330 return 0;
331}
332
333static void
334addkeydef(char *kdstr, int flags)
335{
336 struct keydef *kd;
337
338 kd = enmalloc(2, sizeof(*kd));
339
340 /* parse key definition kdstr with format
341 * start_column[.start_char][flags][,end_column[.end_char][flags]]
342 */
343 kd->start_column = 1;
344 kd->start_char = 1;
345 kd->end_column = 0; /* 0 means end of line */
346 kd->end_char = 0; /* 0 means end of column */
347 kd->flags = flags;
348
349 if ((kd->start_column = strtol(kdstr, &kdstr, 10)) < 1)
350 enprintf(2, "invalid start column in key definition\n");
351
352 if (*kdstr == '.') {
353 if ((kd->start_char = strtol(kdstr + 1, &kdstr, 10)) < 1)
354 enprintf(
355 2,
356 "invalid start character in key "
357 "definition\n"
358 );
359 }
360 if (parse_flags(&kdstr, &kd->flags, MOD_STARTB) < 0)
361 enprintf(2, "invalid start flags in key definition\n");
362
363 if (*kdstr == ',') {
364 if ((kd->end_column = strtol(kdstr + 1, &kdstr, 10)) < 0)
365 enprintf(2, "invalid end column in key definition\n");
366 if (*kdstr == '.') {
367 if ((kd->end_char = strtol(kdstr + 1, &kdstr, 10)) < 0)
368 enprintf(
369 2,
370 "invalid end character in key "
371 "definition\n"
372 );
373 }
374 if (parse_flags(&kdstr, &kd->flags, MOD_ENDB) < 0)
375 enprintf(2, "invalid end flags in key definition\n");
376 }
377
378 if (*kdstr != '\0')
379 enprintf(2, "invalid key definition\n");
380
381 TAILQ_INSERT_TAIL(&kdhead, kd, entry);
382}
383
384static void
385usage(void)
386{
387 enprintf(
388 2,
389 "usage: %s [-Cbcdfimnru"
390#if FEATURE_SORT_STABLE
391 "s"
392#endif
393#if FEATURE_SORT_BIG
394 "z"
395#endif
396 "] [-o outfile] [-t delim] [-k def]... [file ...]\n",
397 argv0
398 );
399}
400
401// ?man sort: sort lines
402// ?man arguments: -Cbcdfimnru
403// ?man sort or merge lines of text files
404int
405main(int argc, char *argv[])
406{
407 FILE *fp, *ofp = stdout;
408 struct linebuf linebuf = EMPTY_LINEBUF;
409 size_t i;
410 int global_flags = 0, ret = 0;
411 char *outfile = NULL;
412
413 ARGBEGIN
414 {
415 // ?man -C: specify option flag
416 case 'C':
417 Cflag = 1;
418 break;
419 // ?man -b: specify block size or base directory
420 case 'b':
421 global_flags |= MOD_STARTB | MOD_ENDB;
422 break;
423 // ?man -c: print count or perform stdout action
424 case 'c':
425 cflag = 1;
426 break;
427 // ?man -d: specify directory
428 case 'd':
429 global_flags |= MOD_D;
430 break;
431 // ?man -f: force the operation
432 case 'f':
433 global_flags |= MOD_F;
434 break;
435 // ?man -i: interactive mode or prompt for confirmation
436 case 'i':
437 global_flags |= MOD_I;
438 break;
439 // ?man -k:str: specify option flag
440 case 'k':
441 addkeydef(EARGF(usage()), global_flags);
442 break;
443 // ?man -m: specify mode or limit
444 case 'm':
445 /* more or less for free, but for performance-reasons,
446 * we should keep this flag in mind and maybe some later
447 * day implement it properly so we don't run out of memory
448 * while merging large sorted files.
449 */
450 break;
451 // ?man -n: print line numbers or counts
452 case 'n':
453 global_flags |= MOD_N;
454 break;
455 // ?man -o:file: specify output file
456 case 'o':
457 outfile = EARGF(usage());
458 break;
459 // ?man -r: operate recursively
460 case 'r':
461 global_flags |= MOD_R;
462 break;
463#if FEATURE_SORT_STABLE
464 // ?man -s: silent mode or print summary
465 case 's':
466 sflag = 1;
467 break;
468#endif
469 // ?man -t:str: sort or specify timestamp
470 case 't':
471 fieldsep = EARGF(usage());
472 if (!*fieldsep)
473 eprintf("empty delimiter\n");
474 fieldseplen = unescape(fieldsep);
475 break;
476 // ?man -u: unbuffered output
477 case 'u':
478 uflag = 1;
479 break;
480#if FEATURE_SORT_BIG
481 // ?man -z: specify option flag
482 case 'z':
483 zflag = 1;
484 break;
485#endif
486 default:
487 usage();
488 }
489 ARGEND
490
491 /* -b shall only apply to custom key definitions */
492 if (TAILQ_EMPTY(&kdhead) && global_flags)
493 addkeydef("1", global_flags & ~(MOD_STARTB | MOD_ENDB));
494 if (TAILQ_EMPTY(&kdhead) || (!Cflag && !cflag))
495 addkeydef("1", global_flags & MOD_R);
496
497 if (!argc) {
498 if (Cflag || cflag) {
499 if (check(stdin, "<stdin>") && !ret)
500 ret = 1;
501 } else {
502#if FEATURE_SORT_BIG
503 if (zflag)
504 getlines_z(stdin, &linebuf);
505 else
506#endif
507 getlines(stdin, &linebuf);
508 }
509 } else
510 for (; *argv; argc--, argv++) {
511 if (!strcmp(*argv, "-")) {
512 *argv = "<stdin>";
513 fp = stdin;
514 } else if (!(fp = fopen(*argv, "r"))) {
515 enprintf(2, "fopen %s:", *argv);
516 continue;
517 }
518 if (Cflag || cflag) {
519 if (check(fp, *argv) && !ret)
520 ret = 1;
521 } else {
522#if FEATURE_SORT_BIG
523 if (zflag)
524 getlines_z(fp, &linebuf);
525 else
526#endif
527 getlines(fp, &linebuf);
528 }
529 if (fp != stdin && fshut(fp, *argv))
530 ret = 2;
531 }
532
533 if (!Cflag && !cflag) {
534 if (outfile && !(ofp = fopen(outfile, "w")))
535 eprintf("fopen %s:", outfile);
536
537#if FEATURE_SORT_STABLE
538 if (sflag) {
539 struct sort_item *items = ecalloc(linebuf.nlines, sizeof(*items));
540 for (i = 0; i < linebuf.nlines; i++) {
541 items[i].line = linebuf.lines[i];
542 items[i].index = i;
543 }
544 qsort(
545 items,
546 linebuf.nlines,
547 sizeof(*items),
548 (int (*)(const void *, const void *))slinecmp_stable
549 );
550 for (i = 0; i < linebuf.nlines; i++) {
551 linebuf.lines[i] = items[i].line;
552 }
553 free(items);
554 } else {
555#endif
556 qsort(
557 linebuf.lines,
558 linebuf.nlines,
559 sizeof(*linebuf.lines),
560 (int (*)(const void *, const void *))slinecmp
561 );
562#if FEATURE_SORT_STABLE
563 }
564#endif
565
566 for (i = 0; i < linebuf.nlines; i++) {
567 if (!uflag || i == 0 || slinecmp(&linebuf.lines[i], &linebuf.lines[i - 1])) {
568 fwrite(linebuf.lines[i].data, 1, linebuf.lines[i].len, ofp);
569 }
570 }
571 }
572
573 if (fshut(stdin, "<stdin>") | fshut(stdout, "<stdout>") | fshut(stderr, "<stderr>"))
574 ret = 2;
575
576 return ret;
577}
