Merge branch 'jc/maint-add-p-coalesce-fix' into maint
[git/dscho.git] / grep.c
bloba649f063cf28baa5b0ddce72d7d6e4d9fca6f360
1 #include "cache.h"
2 #include "grep.h"
3 #include "xdiff-interface.h"
5 void append_header_grep_pattern(struct grep_opt *opt, enum grep_header_field field, const char *pat)
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;
18 void append_grep_pattern(struct grep_opt *opt, const char *pat,
19 const char *origin, int no, enum grep_pat_token t)
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;
31 static int is_fixed(const char *s)
33 while (*s && !is_regex_special(*s))
34 s++;
35 return !*s;
38 static void compile_regexp(struct grep_pat *p, struct grep_opt *opt)
40 int err;
42 p->word_regexp = opt->word_regexp;
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;
51 err = regcomp(&p->regexp, p->pattern, opt->regflags);
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);
68 static struct grep_expr *compile_pattern_or(struct grep_pat **);
69 static struct grep_expr *compile_pattern_atom(struct grep_pat **list)
71 struct grep_pat *p;
72 struct grep_expr *x;
74 p = *list;
75 if (!p)
76 return NULL;
77 switch (p->token) {
78 case GREP_PATTERN: /* atom */
79 case GREP_PATTERN_HEAD:
80 case GREP_PATTERN_BODY:
81 x = xcalloc(1, sizeof (struct grep_expr));
82 x->node = GREP_NODE_ATOM;
83 x->u.atom = p;
84 *list = p->next;
85 return x;
86 case GREP_OPEN_PAREN:
87 *list = p->next;
88 x = compile_pattern_or(list);
89 if (!*list || (*list)->token != GREP_CLOSE_PAREN)
90 die("unmatched parenthesis");
91 *list = (*list)->next;
92 return x;
93 default:
94 return NULL;
98 static struct grep_expr *compile_pattern_not(struct grep_pat **list)
100 struct grep_pat *p;
101 struct grep_expr *x;
103 p = *list;
104 if (!p)
105 return NULL;
106 switch (p->token) {
107 case GREP_NOT:
108 if (!p->next)
109 die("--not not followed by pattern expression");
110 *list = p->next;
111 x = xcalloc(1, sizeof (struct grep_expr));
112 x->node = GREP_NODE_NOT;
113 x->u.unary = compile_pattern_not(list);
114 if (!x->u.unary)
115 die("--not followed by non pattern expression");
116 return x;
117 default:
118 return compile_pattern_atom(list);
122 static struct grep_expr *compile_pattern_and(struct grep_pat **list)
124 struct grep_pat *p;
125 struct grep_expr *x, *y, *z;
127 x = compile_pattern_not(list);
128 p = *list;
129 if (p && p->token == GREP_AND) {
130 if (!p->next)
131 die("--and not followed by pattern expression");
132 *list = p->next;
133 y = compile_pattern_and(list);
134 if (!y)
135 die("--and not followed by pattern expression");
136 z = xcalloc(1, sizeof (struct grep_expr));
137 z->node = GREP_NODE_AND;
138 z->u.binary.left = x;
139 z->u.binary.right = y;
140 return z;
142 return x;
145 static struct grep_expr *compile_pattern_or(struct grep_pat **list)
147 struct grep_pat *p;
148 struct grep_expr *x, *y, *z;
150 x = compile_pattern_and(list);
151 p = *list;
152 if (x && p && p->token != GREP_CLOSE_PAREN) {
153 y = compile_pattern_or(list);
154 if (!y)
155 die("not a pattern expression %s", p->pattern);
156 z = xcalloc(1, sizeof (struct grep_expr));
157 z->node = GREP_NODE_OR;
158 z->u.binary.left = x;
159 z->u.binary.right = y;
160 return z;
162 return x;
165 static struct grep_expr *compile_pattern_expr(struct grep_pat **list)
167 return compile_pattern_or(list);
170 void compile_grep_patterns(struct grep_opt *opt)
172 struct grep_pat *p;
174 if (opt->all_match)
175 opt->extended = 1;
177 for (p = opt->pattern_list; p; p = p->next) {
178 switch (p->token) {
179 case GREP_PATTERN: /* atom */
180 case GREP_PATTERN_HEAD:
181 case GREP_PATTERN_BODY:
182 compile_regexp(p, opt);
183 break;
184 default:
185 opt->extended = 1;
186 break;
190 if (!opt->extended)
191 return;
193 /* Then bundle them up in an expression.
194 * A classic recursive descent parser would do.
196 p = opt->pattern_list;
197 if (p)
198 opt->pattern_expression = compile_pattern_expr(&p);
199 if (p)
200 die("incomplete pattern expression: %s", p->pattern);
203 static void free_pattern_expr(struct grep_expr *x)
205 switch (x->node) {
206 case GREP_NODE_ATOM:
207 break;
208 case GREP_NODE_NOT:
209 free_pattern_expr(x->u.unary);
210 break;
211 case GREP_NODE_AND:
212 case GREP_NODE_OR:
213 free_pattern_expr(x->u.binary.left);
214 free_pattern_expr(x->u.binary.right);
215 break;
217 free(x);
220 void free_grep_patterns(struct grep_opt *opt)
222 struct grep_pat *p, *n;
224 for (p = opt->pattern_list; p; p = n) {
225 n = p->next;
226 switch (p->token) {
227 case GREP_PATTERN: /* atom */
228 case GREP_PATTERN_HEAD:
229 case GREP_PATTERN_BODY:
230 regfree(&p->regexp);
231 break;
232 default:
233 break;
235 free(p);
238 if (!opt->extended)
239 return;
240 free_pattern_expr(opt->pattern_expression);
243 static char *end_of_line(char *cp, unsigned long *left)
245 unsigned long l = *left;
246 while (l && *cp != '\n') {
247 l--;
248 cp++;
250 *left = l;
251 return cp;
254 static int word_char(char ch)
256 return isalnum(ch) || ch == '_';
259 static void show_name(struct grep_opt *opt, const char *name)
261 printf("%s%c", name, opt->null_following_name ? '\0' : '\n');
264 static int fixmatch(const char *pattern, char *line, regmatch_t *match)
266 char *hit = strstr(line, pattern);
267 if (!hit) {
268 match->rm_so = match->rm_eo = -1;
269 return REG_NOMATCH;
271 else {
272 match->rm_so = hit - line;
273 match->rm_eo = match->rm_so + strlen(pattern);
274 return 0;
278 static int strip_timestamp(char *bol, char **eol_p)
280 char *eol = *eol_p;
281 int ch;
283 while (bol < --eol) {
284 if (*eol != '>')
285 continue;
286 *eol_p = ++eol;
287 ch = *eol;
288 *eol = '\0';
289 return ch;
291 return 0;
294 static struct {
295 const char *field;
296 size_t len;
297 } header_field[] = {
298 { "author ", 7 },
299 { "committer ", 10 },
302 static int match_one_pattern(struct grep_pat *p, char *bol, char *eol,
303 enum grep_context ctx,
304 regmatch_t *pmatch, int eflags)
306 int hit = 0;
307 int saved_ch = 0;
308 const char *start = bol;
310 if ((p->token != GREP_PATTERN) &&
311 ((p->token == GREP_PATTERN_HEAD) != (ctx == GREP_CONTEXT_HEAD)))
312 return 0;
314 if (p->token == GREP_PATTERN_HEAD) {
315 const char *field;
316 size_t len;
317 assert(p->field < ARRAY_SIZE(header_field));
318 field = header_field[p->field].field;
319 len = header_field[p->field].len;
320 if (strncmp(bol, field, len))
321 return 0;
322 bol += len;
323 saved_ch = strip_timestamp(bol, &eol);
326 again:
327 if (p->fixed)
328 hit = !fixmatch(p->pattern, bol, pmatch);
329 else
330 hit = !regexec(&p->regexp, bol, 1, pmatch, eflags);
332 if (hit && p->word_regexp) {
333 if ((pmatch[0].rm_so < 0) ||
334 (eol - bol) <= pmatch[0].rm_so ||
335 (pmatch[0].rm_eo < 0) ||
336 (eol - bol) < pmatch[0].rm_eo)
337 die("regexp returned nonsense");
339 /* Match beginning must be either beginning of the
340 * line, or at word boundary (i.e. the last char must
341 * not be a word char). Similarly, match end must be
342 * either end of the line, or at word boundary
343 * (i.e. the next char must not be a word char).
345 if ( ((pmatch[0].rm_so == 0) ||
346 !word_char(bol[pmatch[0].rm_so-1])) &&
347 ((pmatch[0].rm_eo == (eol-bol)) ||
348 !word_char(bol[pmatch[0].rm_eo])) )
350 else
351 hit = 0;
353 if (!hit && pmatch[0].rm_so + bol + 1 < eol) {
354 /* There could be more than one match on the
355 * line, and the first match might not be
356 * strict word match. But later ones could be!
357 * Forward to the next possible start, i.e. the
358 * next position following a non-word char.
360 bol = pmatch[0].rm_so + bol + 1;
361 while (word_char(bol[-1]) && bol < eol)
362 bol++;
363 if (bol < eol)
364 goto again;
367 if (p->token == GREP_PATTERN_HEAD && saved_ch)
368 *eol = saved_ch;
369 if (hit) {
370 pmatch[0].rm_so += bol - start;
371 pmatch[0].rm_eo += bol - start;
373 return hit;
376 static int match_expr_eval(struct grep_expr *x, char *bol, char *eol,
377 enum grep_context ctx, int collect_hits)
379 int h = 0;
380 regmatch_t match;
382 if (!x)
383 die("Not a valid grep expression");
384 switch (x->node) {
385 case GREP_NODE_ATOM:
386 h = match_one_pattern(x->u.atom, bol, eol, ctx, &match, 0);
387 break;
388 case GREP_NODE_NOT:
389 h = !match_expr_eval(x->u.unary, bol, eol, ctx, 0);
390 break;
391 case GREP_NODE_AND:
392 if (!match_expr_eval(x->u.binary.left, bol, eol, ctx, 0))
393 return 0;
394 h = match_expr_eval(x->u.binary.right, bol, eol, ctx, 0);
395 break;
396 case GREP_NODE_OR:
397 if (!collect_hits)
398 return (match_expr_eval(x->u.binary.left,
399 bol, eol, ctx, 0) ||
400 match_expr_eval(x->u.binary.right,
401 bol, eol, ctx, 0));
402 h = match_expr_eval(x->u.binary.left, bol, eol, ctx, 0);
403 x->u.binary.left->hit |= h;
404 h |= match_expr_eval(x->u.binary.right, bol, eol, ctx, 1);
405 break;
406 default:
407 die("Unexpected node type (internal error) %d", x->node);
409 if (collect_hits)
410 x->hit |= h;
411 return h;
414 static int match_expr(struct grep_opt *opt, char *bol, char *eol,
415 enum grep_context ctx, int collect_hits)
417 struct grep_expr *x = opt->pattern_expression;
418 return match_expr_eval(x, bol, eol, ctx, collect_hits);
421 static int match_line(struct grep_opt *opt, char *bol, char *eol,
422 enum grep_context ctx, int collect_hits)
424 struct grep_pat *p;
425 regmatch_t match;
427 if (opt->extended)
428 return match_expr(opt, bol, eol, ctx, collect_hits);
430 /* we do not call with collect_hits without being extended */
431 for (p = opt->pattern_list; p; p = p->next) {
432 if (match_one_pattern(p, bol, eol, ctx, &match, 0))
433 return 1;
435 return 0;
438 static int match_next_pattern(struct grep_pat *p, char *bol, char *eol,
439 enum grep_context ctx,
440 regmatch_t *pmatch, int eflags)
442 regmatch_t match;
444 if (!match_one_pattern(p, bol, eol, ctx, &match, eflags))
445 return 0;
446 if (match.rm_so < 0 || match.rm_eo < 0)
447 return 0;
448 if (pmatch->rm_so >= 0 && pmatch->rm_eo >= 0) {
449 if (match.rm_so > pmatch->rm_so)
450 return 1;
451 if (match.rm_so == pmatch->rm_so && match.rm_eo < pmatch->rm_eo)
452 return 1;
454 pmatch->rm_so = match.rm_so;
455 pmatch->rm_eo = match.rm_eo;
456 return 1;
459 static int next_match(struct grep_opt *opt, char *bol, char *eol,
460 enum grep_context ctx, regmatch_t *pmatch, int eflags)
462 struct grep_pat *p;
463 int hit = 0;
465 pmatch->rm_so = pmatch->rm_eo = -1;
466 if (bol < eol) {
467 for (p = opt->pattern_list; p; p = p->next) {
468 switch (p->token) {
469 case GREP_PATTERN: /* atom */
470 case GREP_PATTERN_HEAD:
471 case GREP_PATTERN_BODY:
472 hit |= match_next_pattern(p, bol, eol, ctx,
473 pmatch, eflags);
474 break;
475 default:
476 break;
480 return hit;
483 static void show_line(struct grep_opt *opt, char *bol, char *eol,
484 const char *name, unsigned lno, char sign)
486 int rest = eol - bol;
488 if (opt->null_following_name)
489 sign = '\0';
490 if (opt->pathname)
491 printf("%s%c", name, sign);
492 if (opt->linenum)
493 printf("%d%c", lno, sign);
494 if (opt->color) {
495 regmatch_t match;
496 enum grep_context ctx = GREP_CONTEXT_BODY;
497 int ch = *eol;
498 int eflags = 0;
500 *eol = '\0';
501 while (next_match(opt, bol, eol, ctx, &match, eflags)) {
502 printf("%.*s%s%.*s%s",
503 (int)match.rm_so, bol,
504 opt->color_match,
505 (int)(match.rm_eo - match.rm_so), bol + match.rm_so,
506 GIT_COLOR_RESET);
507 bol += match.rm_eo;
508 rest -= match.rm_eo;
509 eflags = REG_NOTBOL;
511 *eol = ch;
513 printf("%.*s\n", rest, bol);
516 static int grep_buffer_1(struct grep_opt *opt, const char *name,
517 char *buf, unsigned long size, int collect_hits)
519 char *bol = buf;
520 unsigned long left = size;
521 unsigned lno = 1;
522 struct pre_context_line {
523 char *bol;
524 char *eol;
525 } *prev = NULL, *pcl;
526 unsigned last_hit = 0;
527 unsigned last_shown = 0;
528 int binary_match_only = 0;
529 const char *hunk_mark = "";
530 unsigned count = 0;
531 enum grep_context ctx = GREP_CONTEXT_HEAD;
533 if (buffer_is_binary(buf, size)) {
534 switch (opt->binary) {
535 case GREP_BINARY_DEFAULT:
536 binary_match_only = 1;
537 break;
538 case GREP_BINARY_NOMATCH:
539 return 0; /* Assume unmatch */
540 break;
541 default:
542 break;
546 if (opt->pre_context)
547 prev = xcalloc(opt->pre_context, sizeof(*prev));
548 if (opt->pre_context || opt->post_context)
549 hunk_mark = "--\n";
551 while (left) {
552 char *eol, ch;
553 int hit;
555 eol = end_of_line(bol, &left);
556 ch = *eol;
557 *eol = 0;
559 if ((ctx == GREP_CONTEXT_HEAD) && (eol == bol))
560 ctx = GREP_CONTEXT_BODY;
562 hit = match_line(opt, bol, eol, ctx, collect_hits);
563 *eol = ch;
565 if (collect_hits)
566 goto next_line;
568 /* "grep -v -e foo -e bla" should list lines
569 * that do not have either, so inversion should
570 * be done outside.
572 if (opt->invert)
573 hit = !hit;
574 if (opt->unmatch_name_only) {
575 if (hit)
576 return 0;
577 goto next_line;
579 if (hit) {
580 count++;
581 if (opt->status_only)
582 return 1;
583 if (binary_match_only) {
584 printf("Binary file %s matches\n", name);
585 return 1;
587 if (opt->name_only) {
588 show_name(opt, name);
589 return 1;
591 /* Hit at this line. If we haven't shown the
592 * pre-context lines, we would need to show them.
593 * When asked to do "count", this still show
594 * the context which is nonsense, but the user
595 * deserves to get that ;-).
597 if (opt->pre_context) {
598 unsigned from;
599 if (opt->pre_context < lno)
600 from = lno - opt->pre_context;
601 else
602 from = 1;
603 if (from <= last_shown)
604 from = last_shown + 1;
605 if (last_shown && from != last_shown + 1)
606 fputs(hunk_mark, stdout);
607 while (from < lno) {
608 pcl = &prev[lno-from-1];
609 show_line(opt, pcl->bol, pcl->eol,
610 name, from, '-');
611 from++;
613 last_shown = lno-1;
615 if (last_shown && lno != last_shown + 1)
616 fputs(hunk_mark, stdout);
617 if (!opt->count)
618 show_line(opt, bol, eol, name, lno, ':');
619 last_shown = last_hit = lno;
621 else if (last_hit &&
622 lno <= last_hit + opt->post_context) {
623 /* If the last hit is within the post context,
624 * we need to show this line.
626 if (last_shown && lno != last_shown + 1)
627 fputs(hunk_mark, stdout);
628 show_line(opt, bol, eol, name, lno, '-');
629 last_shown = lno;
631 if (opt->pre_context) {
632 memmove(prev+1, prev,
633 (opt->pre_context-1) * sizeof(*prev));
634 prev->bol = bol;
635 prev->eol = eol;
638 next_line:
639 bol = eol + 1;
640 if (!left)
641 break;
642 left--;
643 lno++;
646 free(prev);
647 if (collect_hits)
648 return 0;
650 if (opt->status_only)
651 return 0;
652 if (opt->unmatch_name_only) {
653 /* We did not see any hit, so we want to show this */
654 show_name(opt, name);
655 return 1;
658 /* NEEDSWORK:
659 * The real "grep -c foo *.c" gives many "bar.c:0" lines,
660 * which feels mostly useless but sometimes useful. Maybe
661 * make it another option? For now suppress them.
663 if (opt->count && count)
664 printf("%s%c%u\n", name,
665 opt->null_following_name ? '\0' : ':', count);
666 return !!last_hit;
669 static void clr_hit_marker(struct grep_expr *x)
671 /* All-hit markers are meaningful only at the very top level
672 * OR node.
674 while (1) {
675 x->hit = 0;
676 if (x->node != GREP_NODE_OR)
677 return;
678 x->u.binary.left->hit = 0;
679 x = x->u.binary.right;
683 static int chk_hit_marker(struct grep_expr *x)
685 /* Top level nodes have hit markers. See if they all are hits */
686 while (1) {
687 if (x->node != GREP_NODE_OR)
688 return x->hit;
689 if (!x->u.binary.left->hit)
690 return 0;
691 x = x->u.binary.right;
695 int grep_buffer(struct grep_opt *opt, const char *name, char *buf, unsigned long size)
698 * we do not have to do the two-pass grep when we do not check
699 * buffer-wide "all-match".
701 if (!opt->all_match)
702 return grep_buffer_1(opt, name, buf, size, 0);
704 /* Otherwise the toplevel "or" terms hit a bit differently.
705 * We first clear hit markers from them.
707 clr_hit_marker(opt->pattern_expression);
708 grep_buffer_1(opt, name, buf, size, 1);
710 if (!chk_hit_marker(opt->pattern_expression))
711 return 0;
713 return grep_buffer_1(opt, name, buf, size, 0);