1 /* grep.c - show lines matching regular expressions
2 *
3 * Copyright 2013 CE Strake <strake888 at gmail.com>
4 *
5 * See http://pubs.opengroup.org/onlinepubs/9699919799/utilities/grep.html
6 *
7 * Posix doesn't even specify -r: too many deviations to document.
8 * TODO: -i is only ascii case insensitive, not unicode.
9
10 USE_GREP(NEWTOY(grep, "(line-buffered)(color):;(exclude-dir)*S(exclude)*M(include)*ZzEFHIab(byte-offset)h(no-filename)ino(only-matching)rRsvwc(count)L(files-without-match)l(files-with-matches)q(quiet)(silent)e*f*C#B#A#m#x[!wx][!EF]", TOYFLAG_BIN|TOYFLAG_ARGFAIL(2)|TOYFLAG_LINEBUF|TOYFLAG_AUTOCONF))
11 USE_EGREP(OLDTOY(egrep, grep, TOYFLAG_BIN|TOYFLAG_ARGFAIL(2)|TOYFLAG_LINEBUF|TOYFLAG_AUTOCONF))
12 USE_FGREP(OLDTOY(fgrep, grep, TOYFLAG_BIN|TOYFLAG_ARGFAIL(2)|TOYFLAG_LINEBUF|TOYFLAG_AUTOCONF))
13
14 config GREP
15 bool "grep"
16 default y
17 help
18 usage: grep [-abcEFHhIiLlnoqrsvwxZz] [-ABC NUM] [-m MAX] [-e REGEX]... [-MS PATTERN]... [-f REGFILE]... [FILE]...
19
20 Show lines matching regular expressions. If no -e, first argument is
21 regular expression to match. With no files (or "-" filename) read stdin.
22 Returns 0 if matched, 1 if no match found, 2 for command errors.
23
24 -e Regex(es) to match. -f File(s) of regexes to match (1 per line).
25
26 file search:
27 -r Recurse into subdirs -R Recurse following symlinks
28 -M Match files (--include) -S Skip files (--exclude)
29 -I Ignore binary files --exclude-dir=PATTERN Skip directories
30
31 match type:
32 -A Show NUM lines after -B Show NUM lines before match
33 -C NUM lines context (A+B) -E extended regex syntax
34 -F fixed (literal match) -a always text (not binary)
35 -i case insensitive -m match MAX many lines
36 -v invert match -w whole word (implies -E)
37 -x whole line -z input NUL terminated
38
39 display modes: (default: matched line)
40 -L filenames with no match -Z output is NUL terminated
41 -c count of matching lines -l filenames with a match
42 -o only matching part -q quiet (errors only)
43 -s silent (no error msg)
44
45 output prefix (default: filename if checking more than 1 file)
46 -H force filename -b byte offset of match
47 -h hide filename -n line number of match
48
49 config EGREP
50 bool
51 default y
52 depends on GREP
53
54 config FGREP
55 bool
56 default y
57 depends on GREP
58 */
59
60 #define FOR_grep
61 #include "toys.h"
62
63 GLOBALS(
64 long m, A, B, C;
65 struct arg_list *f, *e, *M, *S, *exclude_dir;
66 char *color;
67
68 char *purple, *cyan, *red, *green, *grey;
69 struct double_list *reg;
70 int found, tried, delim;
71 struct arg_list **fixed;
72 )
73
74 struct reg {
75 struct reg *next, *prev;
76 int rc;
77 regex_t r;
78 regmatch_t m;
79 };
80
numdash(long num,char dash)81 static void numdash(long num, char dash)
82 {
83 printf("%s%ld%s%c", TT.green, num, TT.cyan, dash);
84 }
85
86 // Emit line with various potential prefixes and delimiter
outline(char * line,char dash,char * name,long lcount,long bcount,unsigned trim)87 static void outline(char *line, char dash, char *name, long lcount, long bcount,
88 unsigned trim)
89 {
90 if (!trim && FLAG(o)) return;
91 if (name && FLAG(H)) printf("%s%s%s%c", TT.purple, name, TT.cyan, dash);
92 if (FLAG(c)) xprintf("%s%ld%c", TT.grey, lcount, TT.delim);
93 else if (lcount && FLAG(n)) numdash(lcount, dash);
94 if (bcount && FLAG(b)) numdash(bcount-1, dash);
95 if (line) {
96 if (FLAG(color)) xputsn(FLAG(o) ? TT.red : TT.grey);
97 // support embedded NUL bytes in output
98 xputsl(line, trim);
99 xputc(TT.delim);
100 }
101 }
102
matchw(char * line,char * start,long so,long eo)103 static int matchw(char *line, char *start, long so, long eo)
104 {
105 if (FLAG(w)) {
106 if (so+(start-line)) if (isalnum(start[so-1]) || start[so-1]=='_') return 0;
107 if (isalnum(start[eo]) || start[eo]=='_') return 0;
108 }
109
110 return 1;
111 }
112
113 // Show matches in one file
do_grep(int fd,char * name)114 static void do_grep(int fd, char *name)
115 {
116 long lcount = 0, mcount = 0, offset = 0, after = 0, before = 0, new = 1;
117 struct double_list *dlb = 0;
118 char *bars = 0;
119 FILE *file;
120 int bin = 0;
121
122 if (!FLAG(r)) TT.tried++;
123 if (!fd) name = "(standard input)";
124
125 // Only run binary file check on lseekable files.
126 if (!FLAG(a) && !lseek(fd, 0, SEEK_CUR)) {
127 char buf[256];
128 int len, i = 0;
129 unsigned wc;
130
131 // If the first 256 bytes don't parse as utf8, call it binary.
132 if (0<(len = read(fd, buf, 256))) {
133 lseek(fd, -len, SEEK_CUR);
134 while (i<len) {
135 bin = utf8towc(&wc, buf+i, len-i);
136 if (bin == -2) i = len;
137 if (bin<1) break;
138 i += bin;
139 }
140 bin = i!=len;
141 }
142 if (bin && FLAG(I)) return;
143 }
144
145 if (!(file = fdopen(fd, "r"))) return perror_msg_raw(name);
146
147 // Loop through lines of input
148 for (;;) {
149 char *line = 0, *start, *ss, *pp;
150 struct reg *shoe;
151 size_t ulen;
152 long len;
153 int matched = 0, rc = 1, move = 0, ii;
154
155 // get next line, check and trim delimiter
156 lcount++;
157 errno = 0;
158 ulen = len = getdelim(&line, &ulen, TT.delim, file);
159 if (len == -1 && errno) perror_msg_raw(name);
160 if (len<1) break;
161 if (line[ulen-1] == TT.delim) line[--ulen] = 0;
162
163 // Prepare for next line
164 start = line;
165 for (shoe = (void *)TT.reg; shoe; shoe = shoe->next) shoe->rc = 0;
166
167 // Loop to handle multiple matches in same line
168 if (new) do {
169 regmatch_t *mm = (void *)toybuf;
170 struct arg_list *seek;
171
172 mm->rm_so = mm->rm_eo = 0;
173 rc = 1;
174
175 // Handle "fixed" (literal) matches (if any)
176 if (TT.e) for (ss = start; ss-line<=ulen; ss++) {
177 ii = FLAG(i) ? toupper(*ss) : *ss;
178 for (seek = TT.fixed[ii]; seek; seek = seek->next) {
179 if (*(pp = seek->arg)=='^' && !FLAG(F)) {
180 if (ss!=start) continue;
181 pp++;
182 }
183 for (ii = 0; pp[ii] && ss[ii]; ii++) {
184 if (!FLAG(F)) {
185 if (pp[ii]=='.') continue;
186 if (pp[ii]=='\\' && pp[ii+1]) pp++;
187 else if (pp[ii]=='$' && !pp[ii+1]) break;
188 }
189 if (FLAG(i)) {
190 if (toupper(pp[ii])!=toupper(ss[ii])) break;
191 } else if (pp[ii]!=ss[ii]) break;
192 }
193 if (pp[ii] && (pp[ii]!='$' || pp[ii+1] || ss[ii])) continue;
194 mm->rm_eo = (mm->rm_so = ss-start)+ii;
195 if (!matchw(line, start, mm->rm_so, mm->rm_eo)) continue;
196 rc = 0;
197
198 goto got;
199 }
200 if (FLAG(x)) break;
201 }
202
203 got:
204 // Handle regex matches (if any)
205 for (shoe = (void *)TT.reg; shoe; shoe = shoe->next) {
206 // Do we need to re-check this regex?
207 if (!shoe->rc) {
208 shoe->m.rm_so -= move;
209 shoe->m.rm_eo -= move;
210 if (!matched || shoe->m.rm_so<0)
211 shoe->rc = regexec0(&shoe->r, start, ulen-(start-line), 1,
212 &shoe->m, start==line ? 0 : REG_NOTBOL);
213 }
214
215 if (!matchw(line, start, shoe->m.rm_so, shoe->m.rm_eo)) continue;
216 // If we got a match, is it a _better_ match?
217 if (!shoe->rc && (rc || shoe->m.rm_so < mm->rm_so ||
218 (shoe->m.rm_so == mm->rm_so && shoe->m.rm_eo >= mm->rm_eo)))
219 {
220 mm = &shoe->m;
221 rc = 0;
222 }
223 }
224
225 if (!rc && FLAG(o) && !mm->rm_eo && ulen>start-line) {
226 move = 1;
227 continue;
228 }
229
230 if (!rc && FLAG(x) && (mm->rm_so || ulen-(start-line)!=mm->rm_eo)) rc = 1;
231
232 if (FLAG(v)) {
233 if (FLAG(o)) {
234 if (rc) mm->rm_eo = ulen-(start-line);
235 else if (!mm->rm_so) {
236 move = mm->rm_eo;
237 continue;
238 } else mm->rm_eo = mm->rm_so;
239 } else {
240 if (!rc) break;
241 mm->rm_eo = ulen-(start-line);
242 }
243 mm->rm_so = 0;
244 } else if (rc) break;
245
246 // At least one line we didn't print since match while -ABC active
247 if (bars) {
248 xputs(bars);
249 bars = 0;
250 }
251 matched++;
252 TT.found = 1;
253
254 // Are we NOT showing the matching text?
255 if (FLAG(q)) {
256 toys.exitval = 0;
257 xexit();
258 }
259 if (FLAG(L) || FLAG(l)) {
260 if (FLAG(l)) xprintf("%s%c", name, '\n'*!FLAG(Z));
261 free(line);
262 fclose(file);
263 return;
264 }
265
266 if (!FLAG(c)) {
267 long bcount = 1 + offset + (start-line) + (FLAG(o) ? mm->rm_so : 0);
268
269 if (bin) printf("Binary file %s matches\n", name);
270 else if (FLAG(o))
271 outline(start+mm->rm_so, ':', name, lcount, bcount,
272 mm->rm_eo-mm->rm_so);
273 else {
274 while (dlb) {
275 struct double_list *dl = dlist_pop(&dlb);
276 unsigned *uu = (void *)(dl->data+(strlen(dl->data)|3)+1);
277
278 outline(dl->data, '-', name, lcount-before, uu[0]+1, uu[1]);
279 free(dl->data);
280 free(dl);
281 before--;
282 }
283
284 if (matched==1)
285 outline(FLAG(color) ? 0 : line, ':', name, lcount, bcount, ulen);
286 if (FLAG(color)) {
287 xputsn(TT.grey);
288 if (mm->rm_so) xputsl(start, mm->rm_so);
289 xputsn(TT.red);
290 xputsl(start+mm->rm_so, mm->rm_eo-mm->rm_so);
291 }
292
293 if (TT.A) after = TT.A+1;
294 }
295 }
296
297 if (mm->rm_so == (move = mm->rm_eo)) break;
298 } while (*(start += move));
299 offset += len;
300
301 if (matched) {
302 // Finish off pending line color fragment.
303 if (FLAG(color) && !FLAG(o)) {
304 xputsn(TT.grey);
305 if (ulen > start-line) xputsl(start, ulen-(start-line));
306 xputc(TT.delim);
307 }
308 mcount++;
309 } else {
310 int discard = (after || TT.B);
311
312 if (after && --after) {
313 outline(line, '-', name, lcount, 0, ulen);
314 discard = 0;
315 }
316 if (discard && TT.B) {
317 unsigned *uu, ul = (ulen|3)+1;
318
319 line = xrealloc(line, ul+8);
320 uu = (void *)(line+ul);
321 uu[0] = offset-len;
322 uu[1] = ulen;
323 dlist_add(&dlb, line);
324 line = 0;
325 if (++before>TT.B) {
326 struct double_list *dl;
327
328 dl = dlist_pop(&dlb);
329 free(dl->data);
330 free(dl);
331 before--;
332 } else discard = 0;
333 }
334 // If we discarded a line while displaying context, show bars before next
335 // line (but don't show them now in case that was last match in file)
336 if (discard && mcount) bars = "--";
337 }
338 free(line);
339
340 if (FLAG(m) && mcount >= TT.m) {
341 if (!after) break;
342 new = 0;
343 }
344 }
345
346 if (FLAG(L)) xprintf("%s%c", name, TT.delim);
347 else if (FLAG(c)) outline(0, ':', name, mcount, 0, 1);
348
349 // loopfiles will also close the fd, but this frees an (opaque) struct.
350 fclose(file);
351 llist_traverse(dlb, llist_free_double);
352 }
353
lensort(struct arg_list ** a,struct arg_list ** b)354 static int lensort(struct arg_list **a, struct arg_list **b)
355 {
356 long la = strlen((*a)->arg), lb = strlen((*b)->arg);
357
358 if (la<lb) return -1;
359 if (la>lb) return 1;
360
361 return 0;
362 }
363
parse_regex(void)364 static void parse_regex(void)
365 {
366 struct arg_list *al, *new, *list = NULL, **last;
367 char *s, *ss, *special = "\\.^$[()|*+?{";
368 int len, ii, key;
369
370 // Add all -f lines to -e list. (Yes, this is leaking allocation context for
371 // exit to free. Not supporting nofork for this command any time soon.)
372 al = TT.f ? TT.f : TT.e;
373 while (al) {
374 if (TT.f) {
375 if (!*(s = xreadfile(al->arg, 0, 0))) {
376 free(s);
377 s = 0;
378 } else if (*(ss = s+strlen(s)-1)=='\n') *ss = 0;
379 } else s = al->arg;
380
381 // Advance, when we run out of -f switch to -e.
382 al = al->next;
383 if (!al && TT.f) {
384 TT.f = 0;
385 al = TT.e;
386 }
387 if (!s) continue;
388
389 // NOTE: even with -z, -f is still \n delimited. Blank line = match all
390 // Split lines at \n, add individual lines to new list.
391 do {
392 if ((ss = strchr(s, '\n'))) *(ss++) = 0;
393 new = xmalloc(sizeof(struct arg_list));
394 new->next = list;
395 new->arg = s;
396 list = new;
397 s = ss;
398 } while (s);
399 }
400 TT.e = list;
401
402 // Convert to regex where appropriate
403 for (last = &TT.e; *last;) {
404 // Can we use the fast path?
405 s = (*last)->arg;
406 if ('.'!=*s && !FLAG(F) && strcmp(s, "^$")) for (; *s; s++) {
407 if (*s=='\\') {
408 if (!s[1] || !strchr(special, *++s)) break;
409 if (!FLAG(E) && *s=='(') break;
410 } else if (*s>127 || strchr(special+4, *s)) break;
411 }
412
413 // Leave entry in fast path (literal-ish match) or move to slow path (regex)
414 if (!*s || FLAG(F)) last = &((*last)->next);
415 else {
416 struct reg *shoe;
417
418 dlist_add_nomalloc(&TT.reg, (void *)(shoe = xmalloc(sizeof(struct reg))));
419 xregcomp(&shoe->r, (*last)->arg, REG_EXTENDED*FLAG(E)|REG_ICASE*FLAG(i));
420 al = *last;
421 *last = (*last)->next;
422 free(al);
423 }
424 }
425 dlist_terminate(TT.reg);
426
427 // Sort fast path patterns into buckets by first character
428 for (al = TT.e; al; al = new) {
429 new = al->next;
430 if (FLAG(F)) key = 0;
431 else {
432 key = '^'==*al->arg;
433 if ('\\'==al->arg[key]) key++;
434 else if ('$'==al->arg[key] && !al->arg[key+1]) key++;
435 }
436 key = al->arg[key];
437 if (FLAG(i)) key = toupper(key);
438 al->next = TT.fixed[key];
439 TT.fixed[key] = al;
440 }
441
442 // Sort each fast path pattern set by length so first hit is longest match
443 // Zero length matches aren't sorted, instead appended to every list.
444 if (TT.e) for (key = 1; key<256; key++) {
445 if (!TT.fixed[key]) {
446 TT.fixed[key] = *TT.fixed;
447 continue;
448 }
449 for (len = 0, al = TT.fixed[key]; al; al = al->next) len++;
450 last = xmalloc(len*sizeof(void *));
451 for (len = 0, al = TT.fixed[key]; al; al = al->next) last[len++] = al;
452 qsort(last, len, sizeof(void *), (void *)lensort);
453 for (ii = 0; ii<len; ii++) last[ii]->next = ii ? last[ii-1] : *TT.fixed;
454 TT.fixed[key] = last[len-1];
455 free(last);
456 }
457 }
458
do_grep_r(struct dirtree * new)459 static int do_grep_r(struct dirtree *new)
460 {
461 struct arg_list *al;
462 char *name;
463
464 if (!new->parent) TT.tried++;
465 if (!dirtree_notdotdot(new)) return 0;
466 if (S_ISDIR(new->st.st_mode)) {
467 for (al = TT.exclude_dir; al; al = al->next)
468 if (!fnmatch(al->arg, new->name, 0)) return 0;
469 return DIRTREE_RECURSE|DIRTREE_SYMFOLLOW*FLAG(R);
470 }
471 if (TT.S || TT.M) {
472 for (al = TT.S; al; al = al->next)
473 if (!fnmatch(al->arg, new->name, 0)) return 0;
474
475 if (TT.M) {
476 for (al = TT.M; al; al = al->next)
477 if (!fnmatch(al->arg, new->name, 0)) break;
478
479 if (!al) return 0;
480 }
481 }
482
483 // "grep -r onefile" doesn't show filenames, but "grep -r onedir" should.
484 if (new->parent && !FLAG(h)) toys.optflags |= FLAG_H;
485
486 name = dirtree_path(new, 0);
487 do_grep(openat(dirtree_parentfd(new), new->name, O_NONBLOCK|O_NOCTTY), name);
488 free(name);
489
490 return 0;
491 }
492
grep_main(void)493 void grep_main(void)
494 {
495 char **ss = toys.optargs;
496
497 TT.fixed = xzalloc(256*sizeof(*TT.fixed));
498
499 if (FLAG(color) && (!TT.color || !strcmp(TT.color, "auto")) && !isatty(1))
500 toys.optflags &= ~FLAG_color;
501
502 if (FLAG(color)) {
503 TT.purple = "\e[35m";
504 TT.cyan = "\e[36m";
505 TT.red = "\e[1;31m";
506 TT.green = "\e[32m";
507 TT.grey = "\e[m";
508 } else TT.purple = TT.cyan = TT.red = TT.green = TT.grey = "";
509
510 if (FLAG(R)) toys.optflags |= FLAG_r;
511
512 // Grep exits with 2 for errors
513 toys.exitval = 2;
514
515 if (!TT.A) TT.A = TT.C;
516 if (!TT.B) TT.B = TT.C;
517
518 TT.delim = '\n' * !FLAG(z);
519
520 // Handle egrep and fgrep
521 if (*toys.which->name == 'e') toys.optflags |= FLAG_E;
522 if (*toys.which->name == 'f') toys.optflags |= FLAG_F;
523
524 if (!TT.e && !TT.f) {
525 if (!*ss) error_exit("no REGEX");
526 TT.e = xzalloc(sizeof(struct arg_list));
527 TT.e->arg = *(ss++);
528 toys.optc--;
529 }
530
531 parse_regex();
532
533 if (!FLAG(h) && toys.optc>1) toys.optflags |= FLAG_H;
534
535 if (FLAG(s)) {
536 close(2);
537 xopen_stdio("/dev/null", O_RDWR);
538 }
539
540 if (FLAG(r)) {
541 // Iterate through -r arguments. Use "." as default if none provided.
542 for (ss = *ss ? ss : (char *[]){".", 0}; *ss; ss++) {
543 if (!strcmp(*ss, "-")) do_grep(0, *ss);
544 else dirtree_read(*ss, do_grep_r);
545 }
546 } else loopfiles_rw(ss, O_RDONLY|WARN_ONLY, 0, do_grep);
547 if (TT.tried >= toys.optc || (FLAG(q)&&TT.found)) toys.exitval = !TT.found;
548 }
549