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));
11 p->token = GREP_PATTERN_HEAD;
13 *opt->pattern_tail = p;
14 opt->pattern_tail = &p->next;
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));
26 *opt->pattern_tail = p;
27 opt->pattern_tail = &p->next;
31 static int is_fixed(const char *s)
33 while (*s && !is_regex_special(*s))
38 static void compile_regexp(struct grep_pat *p, struct grep_opt *opt)
42 p->word_regexp = opt->word_regexp;
44 if (opt->fixed || is_fixed(p->pattern))
46 if (opt->regflags & REG_ICASE)
51 err = regcomp(&p->regexp, p->pattern, opt->regflags);
56 sprintf(where, "In '%s' at %d, ",
59 sprintf(where, "%s, ", p->origin);
62 regerror(err, &p->regexp, errbuf, 1024);
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)
76 case GREP_PATTERN: /* atom */
77 case GREP_PATTERN_HEAD:
78 case GREP_PATTERN_BODY:
79 x = xcalloc(1, sizeof (struct grep_expr));
80 x->node = GREP_NODE_ATOM;
86 x = compile_pattern_or(list);
89 if (!*list || (*list)->token != GREP_CLOSE_PAREN)
90 die("unmatched parenthesis");
91 *list = (*list)->next;
98 static struct grep_expr *compile_pattern_not(struct grep_pat **list)
107 die("--not not followed by pattern expression");
109 x = xcalloc(1, sizeof (struct grep_expr));
110 x->node = GREP_NODE_NOT;
111 x->u.unary = compile_pattern_not(list);
113 die("--not followed by non pattern expression");
116 return compile_pattern_atom(list);
120 static struct grep_expr *compile_pattern_and(struct grep_pat **list)
123 struct grep_expr *x, *y, *z;
125 x = compile_pattern_not(list);
127 if (p && p->token == GREP_AND) {
129 die("--and not followed by pattern expression");
131 y = compile_pattern_and(list);
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;
143 static struct grep_expr *compile_pattern_or(struct grep_pat **list)
146 struct grep_expr *x, *y, *z;
148 x = compile_pattern_and(list);
150 if (x && p && p->token != GREP_CLOSE_PAREN) {
151 y = compile_pattern_or(list);
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;
163 static struct grep_expr *compile_pattern_expr(struct grep_pat **list)
165 return compile_pattern_or(list);
168 void compile_grep_patterns(struct grep_opt *opt)
175 for (p = opt->pattern_list; p; p = p->next) {
177 case GREP_PATTERN: /* atom */
178 case GREP_PATTERN_HEAD:
179 case GREP_PATTERN_BODY:
180 compile_regexp(p, opt);
191 /* Then bundle them up in an expression.
192 * A classic recursive descent parser would do.
194 p = opt->pattern_list;
195 opt->pattern_expression = compile_pattern_expr(&p);
197 die("incomplete pattern expression: %s", p->pattern);
200 static void free_pattern_expr(struct grep_expr *x)
206 free_pattern_expr(x->u.unary);
210 free_pattern_expr(x->u.binary.left);
211 free_pattern_expr(x->u.binary.right);
217 void free_grep_patterns(struct grep_opt *opt)
219 struct grep_pat *p, *n;
221 for (p = opt->pattern_list; p; p = n) {
224 case GREP_PATTERN: /* atom */
225 case GREP_PATTERN_HEAD:
226 case GREP_PATTERN_BODY:
237 free_pattern_expr(opt->pattern_expression);
240 static char *end_of_line(char *cp, unsigned long *left)
242 unsigned long l = *left;
243 while (l && *cp != '\n') {
251 static int word_char(char ch)
253 return isalnum(ch) || ch == '_';
256 static void show_name(struct grep_opt *opt, const char *name)
258 printf("%s%c", name, opt->null_following_name ? '\0' : '\n');
261 static int fixmatch(const char *pattern, char *line, regmatch_t *match)
263 char *hit = strstr(line, pattern);
265 match->rm_so = match->rm_eo = -1;
269 match->rm_so = hit - line;
270 match->rm_eo = match->rm_so + strlen(pattern);
275 static int strip_timestamp(char *bol, char **eol_p)
280 while (bol < --eol) {
296 { "committer ", 10 },
299 static int match_one_pattern(struct grep_pat *p, char *bol, char *eol,
300 enum grep_context ctx,
301 regmatch_t *pmatch, int eflags)
306 if ((p->token != GREP_PATTERN) &&
307 ((p->token == GREP_PATTERN_HEAD) != (ctx == GREP_CONTEXT_HEAD)))
310 if (p->token == GREP_PATTERN_HEAD) {
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))
319 saved_ch = strip_timestamp(bol, &eol);
324 hit = !fixmatch(p->pattern, bol, pmatch);
326 hit = !regexec(&p->regexp, bol, 1, pmatch, eflags);
328 if (hit && p->word_regexp) {
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");
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).
341 if ( ((pmatch[0].rm_so == 0) ||
342 !word_char(bol[pmatch[0].rm_so-1])) &&
343 ((pmatch[0].rm_eo == (eol-bol)) ||
344 !word_char(bol[pmatch[0].rm_eo])) )
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!
353 * Forward to the next possible start, i.e. the
354 * next position following a non-word char.
356 bol = pmatch[0].rm_so + bol + 1;
357 while (word_char(bol[-1]) && bol < eol)
363 if (p->token == GREP_PATTERN_HEAD && saved_ch)
368 static int match_expr_eval(struct grep_expr *x, char *bol, char *eol,
369 enum grep_context ctx, int collect_hits)
376 h = match_one_pattern(x->u.atom, bol, eol, ctx, &match, 0);
379 h = !match_expr_eval(x->u.unary, bol, eol, ctx, 0);
382 if (!match_expr_eval(x->u.binary.left, bol, eol, ctx, 0))
384 h = match_expr_eval(x->u.binary.right, bol, eol, ctx, 0);
388 return (match_expr_eval(x->u.binary.left,
390 match_expr_eval(x->u.binary.right,
392 h = match_expr_eval(x->u.binary.left, bol, eol, ctx, 0);
393 x->u.binary.left->hit |= h;
394 h |= match_expr_eval(x->u.binary.right, bol, eol, ctx, 1);
397 die("Unexpected node type (internal error) %d", x->node);
404 static int match_expr(struct grep_opt *opt, char *bol, char *eol,
405 enum grep_context ctx, int collect_hits)
407 struct grep_expr *x = opt->pattern_expression;
408 return match_expr_eval(x, bol, eol, ctx, collect_hits);
411 static int match_line(struct grep_opt *opt, char *bol, char *eol,
412 enum grep_context ctx, int collect_hits)
418 return match_expr(opt, bol, eol, ctx, collect_hits);
420 /* we do not call with collect_hits without being extended */
421 for (p = opt->pattern_list; p; p = p->next) {
422 if (match_one_pattern(p, bol, eol, ctx, &match, 0))
428 static int match_next_pattern(struct grep_pat *p, char *bol, char *eol,
429 enum grep_context ctx,
430 regmatch_t *pmatch, int eflags)
434 if (!match_one_pattern(p, bol, eol, ctx, &match, eflags))
436 if (match.rm_so < 0 || match.rm_eo < 0)
438 if (pmatch->rm_so >= 0 && pmatch->rm_eo >= 0) {
439 if (match.rm_so > pmatch->rm_so)
441 if (match.rm_so == pmatch->rm_so && match.rm_eo < pmatch->rm_eo)
444 pmatch->rm_so = match.rm_so;
445 pmatch->rm_eo = match.rm_eo;
449 static int next_match(struct grep_opt *opt, char *bol, char *eol,
450 enum grep_context ctx, regmatch_t *pmatch, int eflags)
455 pmatch->rm_so = pmatch->rm_eo = -1;
457 for (p = opt->pattern_list; p; p = p->next) {
459 case GREP_PATTERN: /* atom */
460 case GREP_PATTERN_HEAD:
461 case GREP_PATTERN_BODY:
462 hit |= match_next_pattern(p, bol, eol, ctx,
473 static void show_line(struct grep_opt *opt, char *bol, char *eol,
474 const char *name, unsigned lno, char sign)
476 int rest = eol - bol;
478 if (opt->null_following_name)
481 printf("%s%c", name, sign);
483 printf("%d%c", lno, sign);
486 enum grep_context ctx = GREP_CONTEXT_BODY;
491 while (next_match(opt, bol, eol, ctx, &match, eflags)) {
492 printf("%.*s%s%.*s%s",
493 (int)match.rm_so, bol,
495 (int)(match.rm_eo - match.rm_so), bol + match.rm_so,
503 printf("%.*s\n", rest, bol);
506 static int grep_buffer_1(struct grep_opt *opt, const char *name,
507 char *buf, unsigned long size, int collect_hits)
510 unsigned long left = size;
512 struct pre_context_line {
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 = "";
521 enum grep_context ctx = GREP_CONTEXT_HEAD;
523 if (buffer_is_binary(buf, size)) {
524 switch (opt->binary) {
525 case GREP_BINARY_DEFAULT:
526 binary_match_only = 1;
528 case GREP_BINARY_NOMATCH:
529 return 0; /* Assume unmatch */
536 if (opt->pre_context)
537 prev = xcalloc(opt->pre_context, sizeof(*prev));
538 if (opt->pre_context || opt->post_context)
545 eol = end_of_line(bol, &left);
549 if ((ctx == GREP_CONTEXT_HEAD) && (eol == bol))
550 ctx = GREP_CONTEXT_BODY;
552 hit = match_line(opt, bol, eol, ctx, collect_hits);
558 /* "grep -v -e foo -e bla" should list lines
559 * that do not have either, so inversion should
564 if (opt->unmatch_name_only) {
571 if (opt->status_only)
573 if (binary_match_only) {
574 printf("Binary file %s matches\n", name);
577 if (opt->name_only) {
578 show_name(opt, name);
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 ;-).
587 if (opt->pre_context) {
589 if (opt->pre_context < lno)
590 from = lno - opt->pre_context;
593 if (from <= last_shown)
594 from = last_shown + 1;
595 if (last_shown && from != last_shown + 1)
596 fputs(hunk_mark, stdout);
598 pcl = &prev[lno-from-1];
599 show_line(opt, pcl->bol, pcl->eol,
605 if (last_shown && lno != last_shown + 1)
606 fputs(hunk_mark, stdout);
608 show_line(opt, bol, eol, name, lno, ':');
609 last_shown = last_hit = lno;
612 lno <= last_hit + opt->post_context) {
613 /* If the last hit is within the post context,
614 * we need to show this line.
616 if (last_shown && lno != last_shown + 1)
617 fputs(hunk_mark, stdout);
618 show_line(opt, bol, eol, name, lno, '-');
621 if (opt->pre_context) {
622 memmove(prev+1, prev,
623 (opt->pre_context-1) * sizeof(*prev));
640 if (opt->status_only)
642 if (opt->unmatch_name_only) {
643 /* We did not see any hit, so we want to show this */
644 show_name(opt, name);
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.
653 if (opt->count && count)
654 printf("%s%c%u\n", name,
655 opt->null_following_name ? '\0' : ':', count);
659 static void clr_hit_marker(struct grep_expr *x)
661 /* All-hit markers are meaningful only at the very top level
666 if (x->node != GREP_NODE_OR)
668 x->u.binary.left->hit = 0;
669 x = x->u.binary.right;
673 static int chk_hit_marker(struct grep_expr *x)
675 /* Top level nodes have hit markers. See if they all are hits */
677 if (x->node != GREP_NODE_OR)
679 if (!x->u.binary.left->hit)
681 x = x->u.binary.right;
685 int grep_buffer(struct grep_opt *opt, const char *name, char *buf, unsigned long size)
688 * we do not have to do the two-pass grep when we do not check
689 * buffer-wide "all-match".
692 return grep_buffer_1(opt, name, buf, size, 0);
694 /* Otherwise the toplevel "or" terms hit a bit differently.
695 * We first clear hit markers from them.
697 clr_hit_marker(opt->pattern_expression);
698 grep_buffer_1(opt, name, buf, size, 1);
700 if (!chk_hit_marker(opt->pattern_expression))
703 return grep_buffer_1(opt, name, buf, size, 0);