grep: add support for coloring with external greps
[git/git.git] / grep.c
CommitLineData
83b5d2f5 1#include "cache.h"
83b5d2f5 2#include "grep.h"
6bfce93e 3#include "xdiff-interface.h"
83b5d2f5 4
a4d7d2c6
JH
5void append_header_grep_pattern(struct grep_opt *opt, enum grep_header_field field, const char *pat)
6{
7 struct grep_pat *p = xcalloc(1, sizeof(*p));
8 p->pattern = pat;
9 p->origin = "header";
10 p->no = 0;
11 p->token = GREP_PATTERN_HEAD;
12 p->field = field;
13 *opt->pattern_tail = p;
14 opt->pattern_tail = &p->next;
15 p->next = NULL;
16}
17
83b5d2f5
JH
18void append_grep_pattern(struct grep_opt *opt, const char *pat,
19 const char *origin, int no, enum grep_pat_token t)
20{
21 struct grep_pat *p = xcalloc(1, sizeof(*p));
22 p->pattern = pat;
23 p->origin = origin;
24 p->no = no;
25 p->token = t;
26 *opt->pattern_tail = p;
27 opt->pattern_tail = &p->next;
28 p->next = NULL;
29}
30
c822255c
RS
31static int is_fixed(const char *s)
32{
f9b7cce6 33 while (*s && !is_regex_special(*s))
c822255c
RS
34 s++;
35 return !*s;
36}
37
83b5d2f5
JH
38static void compile_regexp(struct grep_pat *p, struct grep_opt *opt)
39{
c822255c
RS
40 int err;
41
d7eb527d
RS
42 p->word_regexp = opt->word_regexp;
43
c822255c
RS
44 if (opt->fixed || is_fixed(p->pattern))
45 p->fixed = 1;
46 if (opt->regflags & REG_ICASE)
47 p->fixed = 0;
48 if (p->fixed)
49 return;
50
51 err = regcomp(&p->regexp, p->pattern, opt->regflags);
83b5d2f5
JH
52 if (err) {
53 char errbuf[1024];
54 char where[1024];
55 if (p->no)
56 sprintf(where, "In '%s' at %d, ",
57 p->origin, p->no);
58 else if (p->origin)
59 sprintf(where, "%s, ", p->origin);
60 else
61 where[0] = 0;
62 regerror(err, &p->regexp, errbuf, 1024);
63 regfree(&p->regexp);
64 die("%s'%s': %s", where, p->pattern, errbuf);
65 }
66}
67
0ab7befa 68static struct grep_expr *compile_pattern_or(struct grep_pat **);
83b5d2f5
JH
69static struct grep_expr *compile_pattern_atom(struct grep_pat **list)
70{
71 struct grep_pat *p;
72 struct grep_expr *x;
73
74 p = *list;
75 switch (p->token) {
76 case GREP_PATTERN: /* atom */
480c1ca6
JH
77 case GREP_PATTERN_HEAD:
78 case GREP_PATTERN_BODY:
83b5d2f5
JH
79 x = xcalloc(1, sizeof (struct grep_expr));
80 x->node = GREP_NODE_ATOM;
81 x->u.atom = p;
82 *list = p->next;
83 return x;
84 case GREP_OPEN_PAREN:
85 *list = p->next;
0ab7befa 86 x = compile_pattern_or(list);
83b5d2f5
JH
87 if (!x)
88 return NULL;
89 if (!*list || (*list)->token != GREP_CLOSE_PAREN)
90 die("unmatched parenthesis");
91 *list = (*list)->next;
92 return x;
93 default:
94 return NULL;
95 }
96}
97
98static struct grep_expr *compile_pattern_not(struct grep_pat **list)
99{
100 struct grep_pat *p;
101 struct grep_expr *x;
102
103 p = *list;
104 switch (p->token) {
105 case GREP_NOT:
106 if (!p->next)
107 die("--not not followed by pattern expression");
108 *list = p->next;
109 x = xcalloc(1, sizeof (struct grep_expr));
110 x->node = GREP_NODE_NOT;
111 x->u.unary = compile_pattern_not(list);
112 if (!x->u.unary)
113 die("--not followed by non pattern expression");
114 return x;
115 default:
116 return compile_pattern_atom(list);
117 }
118}
119
120static struct grep_expr *compile_pattern_and(struct grep_pat **list)
121{
122 struct grep_pat *p;
123 struct grep_expr *x, *y, *z;
124
125 x = compile_pattern_not(list);
126 p = *list;
127 if (p && p->token == GREP_AND) {
128 if (!p->next)
129 die("--and not followed by pattern expression");
130 *list = p->next;
131 y = compile_pattern_and(list);
132 if (!y)
133 die("--and not followed by pattern expression");
134 z = xcalloc(1, sizeof (struct grep_expr));
135 z->node = GREP_NODE_AND;
136 z->u.binary.left = x;
137 z->u.binary.right = y;
138 return z;
139 }
140 return x;
141}
142
143static struct grep_expr *compile_pattern_or(struct grep_pat **list)
144{
145 struct grep_pat *p;
146 struct grep_expr *x, *y, *z;
147
148 x = compile_pattern_and(list);
149 p = *list;
150 if (x && p && p->token != GREP_CLOSE_PAREN) {
151 y = compile_pattern_or(list);
152 if (!y)
153 die("not a pattern expression %s", p->pattern);
154 z = xcalloc(1, sizeof (struct grep_expr));
155 z->node = GREP_NODE_OR;
156 z->u.binary.left = x;
157 z->u.binary.right = y;
158 return z;
159 }
160 return x;
161}
162
163static struct grep_expr *compile_pattern_expr(struct grep_pat **list)
164{
165 return compile_pattern_or(list);
166}
167
168void compile_grep_patterns(struct grep_opt *opt)
169{
170 struct grep_pat *p;
171
0ab7befa
JH
172 if (opt->all_match)
173 opt->extended = 1;
174
83b5d2f5 175 for (p = opt->pattern_list; p; p = p->next) {
480c1ca6
JH
176 switch (p->token) {
177 case GREP_PATTERN: /* atom */
178 case GREP_PATTERN_HEAD:
179 case GREP_PATTERN_BODY:
c822255c 180 compile_regexp(p, opt);
480c1ca6
JH
181 break;
182 default:
83b5d2f5 183 opt->extended = 1;
480c1ca6
JH
184 break;
185 }
83b5d2f5
JH
186 }
187
188 if (!opt->extended)
189 return;
190
191 /* Then bundle them up in an expression.
192 * A classic recursive descent parser would do.
193 */
194 p = opt->pattern_list;
195 opt->pattern_expression = compile_pattern_expr(&p);
196 if (p)
197 die("incomplete pattern expression: %s", p->pattern);
198}
199
b48fb5b6
JH
200static void free_pattern_expr(struct grep_expr *x)
201{
202 switch (x->node) {
203 case GREP_NODE_ATOM:
204 break;
205 case GREP_NODE_NOT:
206 free_pattern_expr(x->u.unary);
207 break;
208 case GREP_NODE_AND:
209 case GREP_NODE_OR:
210 free_pattern_expr(x->u.binary.left);
211 free_pattern_expr(x->u.binary.right);
212 break;
213 }
214 free(x);
215}
216
217void free_grep_patterns(struct grep_opt *opt)
218{
219 struct grep_pat *p, *n;
220
221 for (p = opt->pattern_list; p; p = n) {
222 n = p->next;
223 switch (p->token) {
224 case GREP_PATTERN: /* atom */
225 case GREP_PATTERN_HEAD:
226 case GREP_PATTERN_BODY:
227 regfree(&p->regexp);
228 break;
229 default:
230 break;
231 }
232 free(p);
233 }
234
235 if (!opt->extended)
236 return;
237 free_pattern_expr(opt->pattern_expression);
238}
239
83b5d2f5
JH
240static char *end_of_line(char *cp, unsigned long *left)
241{
242 unsigned long l = *left;
243 while (l && *cp != '\n') {
244 l--;
245 cp++;
246 }
247 *left = l;
248 return cp;
249}
250
251static int word_char(char ch)
252{
253 return isalnum(ch) || ch == '_';
254}
255
83caecca
RZ
256static void show_name(struct grep_opt *opt, const char *name)
257{
258 printf("%s%c", name, opt->null_following_name ? '\0' : '\n');
259}
260
83b5d2f5
JH
261static int fixmatch(const char *pattern, char *line, regmatch_t *match)
262{
263 char *hit = strstr(line, pattern);
264 if (!hit) {
265 match->rm_so = match->rm_eo = -1;
266 return REG_NOMATCH;
267 }
268 else {
269 match->rm_so = hit - line;
270 match->rm_eo = match->rm_so + strlen(pattern);
271 return 0;
272 }
273}
274
a4d7d2c6
JH
275static int strip_timestamp(char *bol, char **eol_p)
276{
277 char *eol = *eol_p;
278 int ch;
279
280 while (bol < --eol) {
281 if (*eol != '>')
282 continue;
283 *eol_p = ++eol;
284 ch = *eol;
285 *eol = '\0';
286 return ch;
287 }
288 return 0;
289}
290
291static struct {
292 const char *field;
293 size_t len;
294} header_field[] = {
295 { "author ", 7 },
296 { "committer ", 10 },
297};
298
d7eb527d 299static int match_one_pattern(struct grep_pat *p, char *bol, char *eol,
79212772
RS
300 enum grep_context ctx,
301 regmatch_t *pmatch, int eflags)
83b5d2f5
JH
302{
303 int hit = 0;
a4d7d2c6 304 int saved_ch = 0;
83b5d2f5 305
480c1ca6
JH
306 if ((p->token != GREP_PATTERN) &&
307 ((p->token == GREP_PATTERN_HEAD) != (ctx == GREP_CONTEXT_HEAD)))
308 return 0;
309
a4d7d2c6
JH
310 if (p->token == GREP_PATTERN_HEAD) {
311 const char *field;
312 size_t len;
313 assert(p->field < ARRAY_SIZE(header_field));
314 field = header_field[p->field].field;
315 len = header_field[p->field].len;
316 if (strncmp(bol, field, len))
317 return 0;
318 bol += len;
319 saved_ch = strip_timestamp(bol, &eol);
320 }
321
83b5d2f5 322 again:
79212772 323 if (p->fixed)
83b5d2f5 324 hit = !fixmatch(p->pattern, bol, pmatch);
79212772
RS
325 else
326 hit = !regexec(&p->regexp, bol, 1, pmatch, eflags);
83b5d2f5 327
d7eb527d 328 if (hit && p->word_regexp) {
83b5d2f5
JH
329 if ((pmatch[0].rm_so < 0) ||
330 (eol - bol) <= pmatch[0].rm_so ||
331 (pmatch[0].rm_eo < 0) ||
332 (eol - bol) < pmatch[0].rm_eo)
333 die("regexp returned nonsense");
334
335 /* Match beginning must be either beginning of the
336 * line, or at word boundary (i.e. the last char must
337 * not be a word char). Similarly, match end must be
338 * either end of the line, or at word boundary
339 * (i.e. the next char must not be a word char).
340 */
fb62eb7f 341 if ( ((pmatch[0].rm_so == 0) ||
83b5d2f5
JH
342 !word_char(bol[pmatch[0].rm_so-1])) &&
343 ((pmatch[0].rm_eo == (eol-bol)) ||
344 !word_char(bol[pmatch[0].rm_eo])) )
345 ;
346 else
347 hit = 0;
348
349 if (!hit && pmatch[0].rm_so + bol + 1 < eol) {
350 /* There could be more than one match on the
351 * line, and the first match might not be
352 * strict word match. But later ones could be!
fb62eb7f
RS
353 * Forward to the next possible start, i.e. the
354 * next position following a non-word char.
83b5d2f5
JH
355 */
356 bol = pmatch[0].rm_so + bol + 1;
fb62eb7f
RS
357 while (word_char(bol[-1]) && bol < eol)
358 bol++;
359 if (bol < eol)
360 goto again;
83b5d2f5
JH
361 }
362 }
a4d7d2c6
JH
363 if (p->token == GREP_PATTERN_HEAD && saved_ch)
364 *eol = saved_ch;
83b5d2f5
JH
365 return hit;
366}
367
d7eb527d
RS
368static int match_expr_eval(struct grep_expr *x, char *bol, char *eol,
369 enum grep_context ctx, int collect_hits)
83b5d2f5 370{
0ab7befa 371 int h = 0;
79212772 372 regmatch_t match;
0ab7befa 373
83b5d2f5
JH
374 switch (x->node) {
375 case GREP_NODE_ATOM:
79212772 376 h = match_one_pattern(x->u.atom, bol, eol, ctx, &match, 0);
83b5d2f5
JH
377 break;
378 case GREP_NODE_NOT:
d7eb527d 379 h = !match_expr_eval(x->u.unary, bol, eol, ctx, 0);
0ab7befa 380 break;
83b5d2f5 381 case GREP_NODE_AND:
d7eb527d 382 if (!match_expr_eval(x->u.binary.left, bol, eol, ctx, 0))
252d560d 383 return 0;
d7eb527d 384 h = match_expr_eval(x->u.binary.right, bol, eol, ctx, 0);
0ab7befa 385 break;
83b5d2f5 386 case GREP_NODE_OR:
0ab7befa 387 if (!collect_hits)
d7eb527d 388 return (match_expr_eval(x->u.binary.left,
0ab7befa 389 bol, eol, ctx, 0) ||
d7eb527d 390 match_expr_eval(x->u.binary.right,
0ab7befa 391 bol, eol, ctx, 0));
d7eb527d 392 h = match_expr_eval(x->u.binary.left, bol, eol, ctx, 0);
0ab7befa 393 x->u.binary.left->hit |= h;
d7eb527d 394 h |= match_expr_eval(x->u.binary.right, bol, eol, ctx, 1);
0ab7befa
JH
395 break;
396 default:
d7530708 397 die("Unexpected node type (internal error) %d", x->node);
83b5d2f5 398 }
0ab7befa
JH
399 if (collect_hits)
400 x->hit |= h;
401 return h;
83b5d2f5
JH
402}
403
480c1ca6 404static int match_expr(struct grep_opt *opt, char *bol, char *eol,
0ab7befa 405 enum grep_context ctx, int collect_hits)
83b5d2f5
JH
406{
407 struct grep_expr *x = opt->pattern_expression;
d7eb527d 408 return match_expr_eval(x, bol, eol, ctx, collect_hits);
83b5d2f5
JH
409}
410
480c1ca6 411static int match_line(struct grep_opt *opt, char *bol, char *eol,
0ab7befa 412 enum grep_context ctx, int collect_hits)
83b5d2f5
JH
413{
414 struct grep_pat *p;
79212772
RS
415 regmatch_t match;
416
83b5d2f5 417 if (opt->extended)
0ab7befa
JH
418 return match_expr(opt, bol, eol, ctx, collect_hits);
419
420 /* we do not call with collect_hits without being extended */
83b5d2f5 421 for (p = opt->pattern_list; p; p = p->next) {
79212772 422 if (match_one_pattern(p, bol, eol, ctx, &match, 0))
83b5d2f5
JH
423 return 1;
424 }
425 return 0;
426}
427
7e8f59d5
RS
428static int match_next_pattern(struct grep_pat *p, char *bol, char *eol,
429 enum grep_context ctx,
430 regmatch_t *pmatch, int eflags)
431{
432 regmatch_t match;
433
434 if (!match_one_pattern(p, bol, eol, ctx, &match, eflags))
435 return 0;
436 if (match.rm_so < 0 || match.rm_eo < 0)
437 return 0;
438 if (pmatch->rm_so >= 0 && pmatch->rm_eo >= 0) {
439 if (match.rm_so > pmatch->rm_so)
440 return 1;
441 if (match.rm_so == pmatch->rm_so && match.rm_eo < pmatch->rm_eo)
442 return 1;
443 }
444 pmatch->rm_so = match.rm_so;
445 pmatch->rm_eo = match.rm_eo;
446 return 1;
447}
448
449static int next_match(struct grep_opt *opt, char *bol, char *eol,
450 enum grep_context ctx, regmatch_t *pmatch, int eflags)
451{
452 struct grep_pat *p;
453 int hit = 0;
454
455 pmatch->rm_so = pmatch->rm_eo = -1;
456 if (bol < eol) {
457 for (p = opt->pattern_list; p; p = p->next) {
458 switch (p->token) {
459 case GREP_PATTERN: /* atom */
460 case GREP_PATTERN_HEAD:
461 case GREP_PATTERN_BODY:
462 hit |= match_next_pattern(p, bol, eol, ctx,
463 pmatch, eflags);
464 break;
465 default:
466 break;
467 }
468 }
469 }
470 return hit;
471}
472
473static void show_line(struct grep_opt *opt, char *bol, char *eol,
474 const char *name, unsigned lno, char sign)
475{
476 int rest = eol - bol;
477
478 if (opt->null_following_name)
479 sign = '\0';
480 if (opt->pathname)
481 printf("%s%c", name, sign);
482 if (opt->linenum)
483 printf("%d%c", lno, sign);
484 if (opt->color) {
485 regmatch_t match;
486 enum grep_context ctx = GREP_CONTEXT_BODY;
487 int ch = *eol;
488 int eflags = 0;
489
490 *eol = '\0';
491 while (next_match(opt, bol, eol, ctx, &match, eflags)) {
492 printf("%.*s%s%.*s%s",
493 match.rm_so, bol,
494 opt->color_match,
495 match.rm_eo - match.rm_so, bol + match.rm_so,
496 GIT_COLOR_RESET);
497 bol += match.rm_eo;
498 rest -= match.rm_eo;
499 eflags = REG_NOTBOL;
500 }
501 *eol = ch;
502 }
503 printf("%.*s\n", rest, bol);
504}
505
0ab7befa
JH
506static int grep_buffer_1(struct grep_opt *opt, const char *name,
507 char *buf, unsigned long size, int collect_hits)
83b5d2f5
JH
508{
509 char *bol = buf;
510 unsigned long left = size;
511 unsigned lno = 1;
512 struct pre_context_line {
513 char *bol;
514 char *eol;
515 } *prev = NULL, *pcl;
516 unsigned last_hit = 0;
517 unsigned last_shown = 0;
518 int binary_match_only = 0;
519 const char *hunk_mark = "";
520 unsigned count = 0;
480c1ca6 521 enum grep_context ctx = GREP_CONTEXT_HEAD;
83b5d2f5
JH
522
523 if (buffer_is_binary(buf, size)) {
524 switch (opt->binary) {
525 case GREP_BINARY_DEFAULT:
526 binary_match_only = 1;
527 break;
528 case GREP_BINARY_NOMATCH:
529 return 0; /* Assume unmatch */
530 break;
531 default:
532 break;
533 }
534 }
535
536 if (opt->pre_context)
537 prev = xcalloc(opt->pre_context, sizeof(*prev));
538 if (opt->pre_context || opt->post_context)
539 hunk_mark = "--\n";
540
541 while (left) {
542 char *eol, ch;
0ab7befa 543 int hit;
83b5d2f5
JH
544
545 eol = end_of_line(bol, &left);
546 ch = *eol;
547 *eol = 0;
548
480c1ca6
JH
549 if ((ctx == GREP_CONTEXT_HEAD) && (eol == bol))
550 ctx = GREP_CONTEXT_BODY;
551
0ab7befa 552 hit = match_line(opt, bol, eol, ctx, collect_hits);
83b5d2f5
JH
553 *eol = ch;
554
0ab7befa
JH
555 if (collect_hits)
556 goto next_line;
557
83b5d2f5
JH
558 /* "grep -v -e foo -e bla" should list lines
559 * that do not have either, so inversion should
560 * be done outside.
561 */
562 if (opt->invert)
563 hit = !hit;
564 if (opt->unmatch_name_only) {
565 if (hit)
566 return 0;
567 goto next_line;
568 }
569 if (hit) {
570 count++;
571 if (opt->status_only)
572 return 1;
573 if (binary_match_only) {
574 printf("Binary file %s matches\n", name);
575 return 1;
576 }
577 if (opt->name_only) {
83caecca 578 show_name(opt, name);
83b5d2f5
JH
579 return 1;
580 }
581 /* Hit at this line. If we haven't shown the
582 * pre-context lines, we would need to show them.
583 * When asked to do "count", this still show
584 * the context which is nonsense, but the user
585 * deserves to get that ;-).
586 */
587 if (opt->pre_context) {
588 unsigned from;
589 if (opt->pre_context < lno)
590 from = lno - opt->pre_context;
591 else
592 from = 1;
593 if (from <= last_shown)
594 from = last_shown + 1;
595 if (last_shown && from != last_shown + 1)
9db56f71 596 fputs(hunk_mark, stdout);
83b5d2f5
JH
597 while (from < lno) {
598 pcl = &prev[lno-from-1];
599 show_line(opt, pcl->bol, pcl->eol,
600 name, from, '-');
601 from++;
602 }
603 last_shown = lno-1;
604 }
605 if (last_shown && lno != last_shown + 1)
9db56f71 606 fputs(hunk_mark, stdout);
83b5d2f5
JH
607 if (!opt->count)
608 show_line(opt, bol, eol, name, lno, ':');
609 last_shown = last_hit = lno;
610 }
611 else if (last_hit &&
612 lno <= last_hit + opt->post_context) {
613 /* If the last hit is within the post context,
614 * we need to show this line.
615 */
616 if (last_shown && lno != last_shown + 1)
9db56f71 617 fputs(hunk_mark, stdout);
83b5d2f5
JH
618 show_line(opt, bol, eol, name, lno, '-');
619 last_shown = lno;
620 }
621 if (opt->pre_context) {
622 memmove(prev+1, prev,
623 (opt->pre_context-1) * sizeof(*prev));
624 prev->bol = bol;
625 prev->eol = eol;
626 }
627
628 next_line:
629 bol = eol + 1;
630 if (!left)
631 break;
632 left--;
633 lno++;
634 }
635
b48fb5b6 636 free(prev);
0ab7befa
JH
637 if (collect_hits)
638 return 0;
b48fb5b6 639
83b5d2f5
JH
640 if (opt->status_only)
641 return 0;
642 if (opt->unmatch_name_only) {
643 /* We did not see any hit, so we want to show this */
83caecca 644 show_name(opt, name);
83b5d2f5
JH
645 return 1;
646 }
647
648 /* NEEDSWORK:
649 * The real "grep -c foo *.c" gives many "bar.c:0" lines,
650 * which feels mostly useless but sometimes useful. Maybe
651 * make it another option? For now suppress them.
652 */
653 if (opt->count && count)
83caecca
RZ
654 printf("%s%c%u\n", name,
655 opt->null_following_name ? '\0' : ':', count);
83b5d2f5
JH
656 return !!last_hit;
657}
658
0ab7befa
JH
659static void clr_hit_marker(struct grep_expr *x)
660{
661 /* All-hit markers are meaningful only at the very top level
662 * OR node.
663 */
664 while (1) {
665 x->hit = 0;
666 if (x->node != GREP_NODE_OR)
667 return;
668 x->u.binary.left->hit = 0;
669 x = x->u.binary.right;
670 }
671}
672
673static int chk_hit_marker(struct grep_expr *x)
674{
675 /* Top level nodes have hit markers. See if they all are hits */
676 while (1) {
677 if (x->node != GREP_NODE_OR)
678 return x->hit;
679 if (!x->u.binary.left->hit)
680 return 0;
681 x = x->u.binary.right;
682 }
683}
684
685int grep_buffer(struct grep_opt *opt, const char *name, char *buf, unsigned long size)
686{
687 /*
688 * we do not have to do the two-pass grep when we do not check
689 * buffer-wide "all-match".
690 */
691 if (!opt->all_match)
692 return grep_buffer_1(opt, name, buf, size, 0);
693
694 /* Otherwise the toplevel "or" terms hit a bit differently.
695 * We first clear hit markers from them.
696 */
697 clr_hit_marker(opt->pattern_expression);
698 grep_buffer_1(opt, name, buf, size, 1);
699
700 if (!chk_hit_marker(opt->pattern_expression))
701 return 0;
702
703 return grep_buffer_1(opt, name, buf, size, 0);
704}