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