Win32: fix detection of empty directories in is_dir_empty
[git/dscho.git] / grep.c
blobedc7776677ed201dbe117c207a680e1f832737e3
1 #include "cache.h"
2 #include "grep.h"
3 #include "userdiff.h"
4 #include "xdiff-interface.h"
6 static int grep_source_load(struct grep_source *gs);
7 static int grep_source_is_binary(struct grep_source *gs);
10 static struct grep_pat *create_grep_pat(const char *pat, size_t patlen,
11 const char *origin, int no,
12 enum grep_pat_token t,
13 enum grep_header_field field)
15 struct grep_pat *p = xcalloc(1, sizeof(*p));
16 p->pattern = xmemdupz(pat, patlen);
17 p->patternlen = patlen;
18 p->origin = origin;
19 p->no = no;
20 p->token = t;
21 p->field = field;
22 return p;
25 static void do_append_grep_pat(struct grep_pat ***tail, struct grep_pat *p)
27 **tail = p;
28 *tail = &p->next;
29 p->next = NULL;
31 switch (p->token) {
32 case GREP_PATTERN: /* atom */
33 case GREP_PATTERN_HEAD:
34 case GREP_PATTERN_BODY:
35 for (;;) {
36 struct grep_pat *new_pat;
37 size_t len = 0;
38 char *cp = p->pattern + p->patternlen, *nl = NULL;
39 while (++len <= p->patternlen) {
40 if (*(--cp) == '\n') {
41 nl = cp;
42 break;
45 if (!nl)
46 break;
47 new_pat = create_grep_pat(nl + 1, len - 1, p->origin,
48 p->no, p->token, p->field);
49 new_pat->next = p->next;
50 if (!p->next)
51 *tail = &new_pat->next;
52 p->next = new_pat;
53 *nl = '\0';
54 p->patternlen -= len;
56 break;
57 default:
58 break;
62 void append_header_grep_pattern(struct grep_opt *opt,
63 enum grep_header_field field, const char *pat)
65 struct grep_pat *p = create_grep_pat(pat, strlen(pat), "header", 0,
66 GREP_PATTERN_HEAD, field);
67 if (field == GREP_HEADER_REFLOG)
68 opt->use_reflog_filter = 1;
69 do_append_grep_pat(&opt->header_tail, p);
72 void append_grep_pattern(struct grep_opt *opt, const char *pat,
73 const char *origin, int no, enum grep_pat_token t)
75 append_grep_pat(opt, pat, strlen(pat), origin, no, t);
78 void append_grep_pat(struct grep_opt *opt, const char *pat, size_t patlen,
79 const char *origin, int no, enum grep_pat_token t)
81 struct grep_pat *p = create_grep_pat(pat, patlen, origin, no, t, 0);
82 do_append_grep_pat(&opt->pattern_tail, p);
85 struct grep_opt *grep_opt_dup(const struct grep_opt *opt)
87 struct grep_pat *pat;
88 struct grep_opt *ret = xmalloc(sizeof(struct grep_opt));
89 *ret = *opt;
91 ret->pattern_list = NULL;
92 ret->pattern_tail = &ret->pattern_list;
94 for(pat = opt->pattern_list; pat != NULL; pat = pat->next)
96 if(pat->token == GREP_PATTERN_HEAD)
97 append_header_grep_pattern(ret, pat->field,
98 pat->pattern);
99 else
100 append_grep_pat(ret, pat->pattern, pat->patternlen,
101 pat->origin, pat->no, pat->token);
104 return ret;
107 static NORETURN void compile_regexp_failed(const struct grep_pat *p,
108 const char *error)
110 char where[1024];
112 if (p->no)
113 sprintf(where, "In '%s' at %d, ", p->origin, p->no);
114 else if (p->origin)
115 sprintf(where, "%s, ", p->origin);
116 else
117 where[0] = 0;
119 die("%s'%s': %s", where, p->pattern, error);
122 #ifdef USE_LIBPCRE
123 static void compile_pcre_regexp(struct grep_pat *p, const struct grep_opt *opt)
125 const char *error;
126 int erroffset;
127 int options = PCRE_MULTILINE;
129 if (opt->ignore_case)
130 options |= PCRE_CASELESS;
132 p->pcre_regexp = pcre_compile(p->pattern, options, &error, &erroffset,
133 NULL);
134 if (!p->pcre_regexp)
135 compile_regexp_failed(p, error);
137 p->pcre_extra_info = pcre_study(p->pcre_regexp, 0, &error);
138 if (!p->pcre_extra_info && error)
139 die("%s", error);
142 static int pcrematch(struct grep_pat *p, const char *line, const char *eol,
143 regmatch_t *match, int eflags)
145 int ovector[30], ret, flags = 0;
147 if (eflags & REG_NOTBOL)
148 flags |= PCRE_NOTBOL;
150 ret = pcre_exec(p->pcre_regexp, p->pcre_extra_info, line, eol - line,
151 0, flags, ovector, ARRAY_SIZE(ovector));
152 if (ret < 0 && ret != PCRE_ERROR_NOMATCH)
153 die("pcre_exec failed with error code %d", ret);
154 if (ret > 0) {
155 ret = 0;
156 match->rm_so = ovector[0];
157 match->rm_eo = ovector[1];
160 return ret;
163 static void free_pcre_regexp(struct grep_pat *p)
165 pcre_free(p->pcre_regexp);
166 pcre_free(p->pcre_extra_info);
168 #else /* !USE_LIBPCRE */
169 static void compile_pcre_regexp(struct grep_pat *p, const struct grep_opt *opt)
171 die("cannot use Perl-compatible regexes when not compiled with USE_LIBPCRE");
174 static int pcrematch(struct grep_pat *p, const char *line, const char *eol,
175 regmatch_t *match, int eflags)
177 return 1;
180 static void free_pcre_regexp(struct grep_pat *p)
183 #endif /* !USE_LIBPCRE */
185 static int is_fixed(const char *s, size_t len)
187 size_t i;
189 /* regcomp cannot accept patterns with NULs so we
190 * consider any pattern containing a NUL fixed.
192 if (memchr(s, 0, len))
193 return 1;
195 for (i = 0; i < len; i++) {
196 if (is_regex_special(s[i]))
197 return 0;
200 return 1;
203 static void compile_regexp(struct grep_pat *p, struct grep_opt *opt)
205 int err;
207 p->word_regexp = opt->word_regexp;
208 p->ignore_case = opt->ignore_case;
210 if (opt->fixed || is_fixed(p->pattern, p->patternlen))
211 p->fixed = 1;
212 else
213 p->fixed = 0;
215 if (p->fixed) {
216 if (opt->regflags & REG_ICASE || p->ignore_case)
217 p->kws = kwsalloc(tolower_trans_tbl);
218 else
219 p->kws = kwsalloc(NULL);
220 kwsincr(p->kws, p->pattern, p->patternlen);
221 kwsprep(p->kws);
222 return;
225 if (opt->pcre) {
226 compile_pcre_regexp(p, opt);
227 return;
230 err = regcomp(&p->regexp, p->pattern, opt->regflags);
231 if (err) {
232 char errbuf[1024];
233 regerror(err, &p->regexp, errbuf, 1024);
234 regfree(&p->regexp);
235 compile_regexp_failed(p, errbuf);
239 static struct grep_expr *compile_pattern_or(struct grep_pat **);
240 static struct grep_expr *compile_pattern_atom(struct grep_pat **list)
242 struct grep_pat *p;
243 struct grep_expr *x;
245 p = *list;
246 if (!p)
247 return NULL;
248 switch (p->token) {
249 case GREP_PATTERN: /* atom */
250 case GREP_PATTERN_HEAD:
251 case GREP_PATTERN_BODY:
252 x = xcalloc(1, sizeof (struct grep_expr));
253 x->node = GREP_NODE_ATOM;
254 x->u.atom = p;
255 *list = p->next;
256 return x;
257 case GREP_OPEN_PAREN:
258 *list = p->next;
259 x = compile_pattern_or(list);
260 if (!*list || (*list)->token != GREP_CLOSE_PAREN)
261 die("unmatched parenthesis");
262 *list = (*list)->next;
263 return x;
264 default:
265 return NULL;
269 static struct grep_expr *compile_pattern_not(struct grep_pat **list)
271 struct grep_pat *p;
272 struct grep_expr *x;
274 p = *list;
275 if (!p)
276 return NULL;
277 switch (p->token) {
278 case GREP_NOT:
279 if (!p->next)
280 die("--not not followed by pattern expression");
281 *list = p->next;
282 x = xcalloc(1, sizeof (struct grep_expr));
283 x->node = GREP_NODE_NOT;
284 x->u.unary = compile_pattern_not(list);
285 if (!x->u.unary)
286 die("--not followed by non pattern expression");
287 return x;
288 default:
289 return compile_pattern_atom(list);
293 static struct grep_expr *compile_pattern_and(struct grep_pat **list)
295 struct grep_pat *p;
296 struct grep_expr *x, *y, *z;
298 x = compile_pattern_not(list);
299 p = *list;
300 if (p && p->token == GREP_AND) {
301 if (!p->next)
302 die("--and not followed by pattern expression");
303 *list = p->next;
304 y = compile_pattern_and(list);
305 if (!y)
306 die("--and not followed by pattern expression");
307 z = xcalloc(1, sizeof (struct grep_expr));
308 z->node = GREP_NODE_AND;
309 z->u.binary.left = x;
310 z->u.binary.right = y;
311 return z;
313 return x;
316 static struct grep_expr *compile_pattern_or(struct grep_pat **list)
318 struct grep_pat *p;
319 struct grep_expr *x, *y, *z;
321 x = compile_pattern_and(list);
322 p = *list;
323 if (x && p && p->token != GREP_CLOSE_PAREN) {
324 y = compile_pattern_or(list);
325 if (!y)
326 die("not a pattern expression %s", p->pattern);
327 z = xcalloc(1, sizeof (struct grep_expr));
328 z->node = GREP_NODE_OR;
329 z->u.binary.left = x;
330 z->u.binary.right = y;
331 return z;
333 return x;
336 static struct grep_expr *compile_pattern_expr(struct grep_pat **list)
338 return compile_pattern_or(list);
341 static void indent(int in)
343 while (in-- > 0)
344 fputc(' ', stderr);
347 static void dump_grep_pat(struct grep_pat *p)
349 switch (p->token) {
350 case GREP_AND: fprintf(stderr, "*and*"); break;
351 case GREP_OPEN_PAREN: fprintf(stderr, "*(*"); break;
352 case GREP_CLOSE_PAREN: fprintf(stderr, "*)*"); break;
353 case GREP_NOT: fprintf(stderr, "*not*"); break;
354 case GREP_OR: fprintf(stderr, "*or*"); break;
356 case GREP_PATTERN: fprintf(stderr, "pattern"); break;
357 case GREP_PATTERN_HEAD: fprintf(stderr, "pattern_head"); break;
358 case GREP_PATTERN_BODY: fprintf(stderr, "pattern_body"); break;
361 switch (p->token) {
362 default: break;
363 case GREP_PATTERN_HEAD:
364 fprintf(stderr, "<head %d>", p->field); break;
365 case GREP_PATTERN_BODY:
366 fprintf(stderr, "<body>"); break;
368 switch (p->token) {
369 default: break;
370 case GREP_PATTERN_HEAD:
371 case GREP_PATTERN_BODY:
372 case GREP_PATTERN:
373 fprintf(stderr, "%.*s", (int)p->patternlen, p->pattern);
374 break;
376 fputc('\n', stderr);
379 static void dump_grep_expression_1(struct grep_expr *x, int in)
381 indent(in);
382 switch (x->node) {
383 case GREP_NODE_TRUE:
384 fprintf(stderr, "true\n");
385 break;
386 case GREP_NODE_ATOM:
387 dump_grep_pat(x->u.atom);
388 break;
389 case GREP_NODE_NOT:
390 fprintf(stderr, "(not\n");
391 dump_grep_expression_1(x->u.unary, in+1);
392 indent(in);
393 fprintf(stderr, ")\n");
394 break;
395 case GREP_NODE_AND:
396 fprintf(stderr, "(and\n");
397 dump_grep_expression_1(x->u.binary.left, in+1);
398 dump_grep_expression_1(x->u.binary.right, in+1);
399 indent(in);
400 fprintf(stderr, ")\n");
401 break;
402 case GREP_NODE_OR:
403 fprintf(stderr, "(or\n");
404 dump_grep_expression_1(x->u.binary.left, in+1);
405 dump_grep_expression_1(x->u.binary.right, in+1);
406 indent(in);
407 fprintf(stderr, ")\n");
408 break;
412 static void dump_grep_expression(struct grep_opt *opt)
414 struct grep_expr *x = opt->pattern_expression;
416 if (opt->all_match)
417 fprintf(stderr, "[all-match]\n");
418 dump_grep_expression_1(x, 0);
419 fflush(NULL);
422 static struct grep_expr *grep_true_expr(void)
424 struct grep_expr *z = xcalloc(1, sizeof(*z));
425 z->node = GREP_NODE_TRUE;
426 return z;
429 static struct grep_expr *grep_or_expr(struct grep_expr *left, struct grep_expr *right)
431 struct grep_expr *z = xcalloc(1, sizeof(*z));
432 z->node = GREP_NODE_OR;
433 z->u.binary.left = left;
434 z->u.binary.right = right;
435 return z;
438 static struct grep_expr *prep_header_patterns(struct grep_opt *opt)
440 struct grep_pat *p;
441 struct grep_expr *header_expr;
442 struct grep_expr *(header_group[GREP_HEADER_FIELD_MAX]);
443 enum grep_header_field fld;
445 if (!opt->header_list)
446 return NULL;
448 for (p = opt->header_list; p; p = p->next) {
449 if (p->token != GREP_PATTERN_HEAD)
450 die("bug: a non-header pattern in grep header list.");
451 if (p->field < 0 || GREP_HEADER_FIELD_MAX <= p->field)
452 die("bug: unknown header field %d", p->field);
453 compile_regexp(p, opt);
456 for (fld = 0; fld < GREP_HEADER_FIELD_MAX; fld++)
457 header_group[fld] = NULL;
459 for (p = opt->header_list; p; p = p->next) {
460 struct grep_expr *h;
461 struct grep_pat *pp = p;
463 h = compile_pattern_atom(&pp);
464 if (!h || pp != p->next)
465 die("bug: malformed header expr");
466 if (!header_group[p->field]) {
467 header_group[p->field] = h;
468 continue;
470 header_group[p->field] = grep_or_expr(h, header_group[p->field]);
473 header_expr = NULL;
475 for (fld = 0; fld < GREP_HEADER_FIELD_MAX; fld++) {
476 if (!header_group[fld])
477 continue;
478 if (!header_expr)
479 header_expr = grep_true_expr();
480 header_expr = grep_or_expr(header_group[fld], header_expr);
482 return header_expr;
485 static struct grep_expr *grep_splice_or(struct grep_expr *x, struct grep_expr *y)
487 struct grep_expr *z = x;
489 while (x) {
490 assert(x->node == GREP_NODE_OR);
491 if (x->u.binary.right &&
492 x->u.binary.right->node == GREP_NODE_TRUE) {
493 x->u.binary.right = y;
494 break;
496 x = x->u.binary.right;
498 return z;
501 static void compile_grep_patterns_real(struct grep_opt *opt)
503 struct grep_pat *p;
504 struct grep_expr *header_expr = prep_header_patterns(opt);
506 for (p = opt->pattern_list; p; p = p->next) {
507 switch (p->token) {
508 case GREP_PATTERN: /* atom */
509 case GREP_PATTERN_HEAD:
510 case GREP_PATTERN_BODY:
511 compile_regexp(p, opt);
512 break;
513 default:
514 opt->extended = 1;
515 break;
519 if (opt->all_match || header_expr)
520 opt->extended = 1;
521 else if (!opt->extended && !opt->debug)
522 return;
524 p = opt->pattern_list;
525 if (p)
526 opt->pattern_expression = compile_pattern_expr(&p);
527 if (p)
528 die("incomplete pattern expression: %s", p->pattern);
530 if (!header_expr)
531 return;
533 if (!opt->pattern_expression)
534 opt->pattern_expression = header_expr;
535 else if (opt->all_match)
536 opt->pattern_expression = grep_splice_or(header_expr,
537 opt->pattern_expression);
538 else
539 opt->pattern_expression = grep_or_expr(opt->pattern_expression,
540 header_expr);
541 opt->all_match = 1;
544 void compile_grep_patterns(struct grep_opt *opt)
546 compile_grep_patterns_real(opt);
547 if (opt->debug)
548 dump_grep_expression(opt);
551 static void free_pattern_expr(struct grep_expr *x)
553 switch (x->node) {
554 case GREP_NODE_TRUE:
555 case GREP_NODE_ATOM:
556 break;
557 case GREP_NODE_NOT:
558 free_pattern_expr(x->u.unary);
559 break;
560 case GREP_NODE_AND:
561 case GREP_NODE_OR:
562 free_pattern_expr(x->u.binary.left);
563 free_pattern_expr(x->u.binary.right);
564 break;
566 free(x);
569 void free_grep_patterns(struct grep_opt *opt)
571 struct grep_pat *p, *n;
573 for (p = opt->pattern_list; p; p = n) {
574 n = p->next;
575 switch (p->token) {
576 case GREP_PATTERN: /* atom */
577 case GREP_PATTERN_HEAD:
578 case GREP_PATTERN_BODY:
579 if (p->kws)
580 kwsfree(p->kws);
581 else if (p->pcre_regexp)
582 free_pcre_regexp(p);
583 else
584 regfree(&p->regexp);
585 free(p->pattern);
586 break;
587 default:
588 break;
590 free(p);
593 if (!opt->extended)
594 return;
595 free_pattern_expr(opt->pattern_expression);
598 static char *end_of_line(char *cp, unsigned long *left)
600 unsigned long l = *left;
601 while (l && *cp != '\n') {
602 l--;
603 cp++;
605 *left = l;
606 return cp;
609 static int word_char(char ch)
611 return isalnum(ch) || ch == '_';
614 static void output_color(struct grep_opt *opt, const void *data, size_t size,
615 const char *color)
617 if (want_color(opt->color) && color && color[0]) {
618 opt->output(opt, color, strlen(color));
619 opt->output(opt, data, size);
620 opt->output(opt, GIT_COLOR_RESET, strlen(GIT_COLOR_RESET));
621 } else
622 opt->output(opt, data, size);
625 static void output_sep(struct grep_opt *opt, char sign)
627 if (opt->null_following_name)
628 opt->output(opt, "\0", 1);
629 else
630 output_color(opt, &sign, 1, opt->color_sep);
633 static void show_name(struct grep_opt *opt, const char *name)
635 output_color(opt, name, strlen(name), opt->color_filename);
636 opt->output(opt, opt->null_following_name ? "\0" : "\n", 1);
639 static int fixmatch(struct grep_pat *p, char *line, char *eol,
640 regmatch_t *match)
642 struct kwsmatch kwsm;
643 size_t offset = kwsexec(p->kws, line, eol - line, &kwsm);
644 if (offset == -1) {
645 match->rm_so = match->rm_eo = -1;
646 return REG_NOMATCH;
647 } else {
648 match->rm_so = offset;
649 match->rm_eo = match->rm_so + kwsm.size[0];
650 return 0;
654 static int regmatch(const regex_t *preg, char *line, char *eol,
655 regmatch_t *match, int eflags)
657 #ifdef REG_STARTEND
658 match->rm_so = 0;
659 match->rm_eo = eol - line;
660 eflags |= REG_STARTEND;
661 #endif
662 return regexec(preg, line, 1, match, eflags);
665 static int patmatch(struct grep_pat *p, char *line, char *eol,
666 regmatch_t *match, int eflags)
668 int hit;
670 if (p->fixed)
671 hit = !fixmatch(p, line, eol, match);
672 else if (p->pcre_regexp)
673 hit = !pcrematch(p, line, eol, match, eflags);
674 else
675 hit = !regmatch(&p->regexp, line, eol, match, eflags);
677 return hit;
680 static int strip_timestamp(char *bol, char **eol_p)
682 char *eol = *eol_p;
683 int ch;
685 while (bol < --eol) {
686 if (*eol != '>')
687 continue;
688 *eol_p = ++eol;
689 ch = *eol;
690 *eol = '\0';
691 return ch;
693 return 0;
696 static struct {
697 const char *field;
698 size_t len;
699 } header_field[] = {
700 { "author ", 7 },
701 { "committer ", 10 },
702 { "reflog ", 7 },
705 static int match_one_pattern(struct grep_pat *p, char *bol, char *eol,
706 enum grep_context ctx,
707 regmatch_t *pmatch, int eflags)
709 int hit = 0;
710 int saved_ch = 0;
711 const char *start = bol;
713 if ((p->token != GREP_PATTERN) &&
714 ((p->token == GREP_PATTERN_HEAD) != (ctx == GREP_CONTEXT_HEAD)))
715 return 0;
717 if (p->token == GREP_PATTERN_HEAD) {
718 const char *field;
719 size_t len;
720 assert(p->field < ARRAY_SIZE(header_field));
721 field = header_field[p->field].field;
722 len = header_field[p->field].len;
723 if (strncmp(bol, field, len))
724 return 0;
725 bol += len;
726 switch (p->field) {
727 case GREP_HEADER_AUTHOR:
728 case GREP_HEADER_COMMITTER:
729 saved_ch = strip_timestamp(bol, &eol);
730 break;
731 default:
732 break;
736 again:
737 hit = patmatch(p, bol, eol, pmatch, eflags);
739 if (hit && p->word_regexp) {
740 if ((pmatch[0].rm_so < 0) ||
741 (eol - bol) < pmatch[0].rm_so ||
742 (pmatch[0].rm_eo < 0) ||
743 (eol - bol) < pmatch[0].rm_eo)
744 die("regexp returned nonsense");
746 /* Match beginning must be either beginning of the
747 * line, or at word boundary (i.e. the last char must
748 * not be a word char). Similarly, match end must be
749 * either end of the line, or at word boundary
750 * (i.e. the next char must not be a word char).
752 if ( ((pmatch[0].rm_so == 0) ||
753 !word_char(bol[pmatch[0].rm_so-1])) &&
754 ((pmatch[0].rm_eo == (eol-bol)) ||
755 !word_char(bol[pmatch[0].rm_eo])) )
757 else
758 hit = 0;
760 /* Words consist of at least one character. */
761 if (pmatch->rm_so == pmatch->rm_eo)
762 hit = 0;
764 if (!hit && pmatch[0].rm_so + bol + 1 < eol) {
765 /* There could be more than one match on the
766 * line, and the first match might not be
767 * strict word match. But later ones could be!
768 * Forward to the next possible start, i.e. the
769 * next position following a non-word char.
771 bol = pmatch[0].rm_so + bol + 1;
772 while (word_char(bol[-1]) && bol < eol)
773 bol++;
774 eflags |= REG_NOTBOL;
775 if (bol < eol)
776 goto again;
779 if (p->token == GREP_PATTERN_HEAD && saved_ch)
780 *eol = saved_ch;
781 if (hit) {
782 pmatch[0].rm_so += bol - start;
783 pmatch[0].rm_eo += bol - start;
785 return hit;
788 static int match_expr_eval(struct grep_expr *x, char *bol, char *eol,
789 enum grep_context ctx, int collect_hits)
791 int h = 0;
792 regmatch_t match;
794 if (!x)
795 die("Not a valid grep expression");
796 switch (x->node) {
797 case GREP_NODE_TRUE:
798 h = 1;
799 break;
800 case GREP_NODE_ATOM:
801 h = match_one_pattern(x->u.atom, bol, eol, ctx, &match, 0);
802 break;
803 case GREP_NODE_NOT:
804 h = !match_expr_eval(x->u.unary, bol, eol, ctx, 0);
805 break;
806 case GREP_NODE_AND:
807 if (!match_expr_eval(x->u.binary.left, bol, eol, ctx, 0))
808 return 0;
809 h = match_expr_eval(x->u.binary.right, bol, eol, ctx, 0);
810 break;
811 case GREP_NODE_OR:
812 if (!collect_hits)
813 return (match_expr_eval(x->u.binary.left,
814 bol, eol, ctx, 0) ||
815 match_expr_eval(x->u.binary.right,
816 bol, eol, ctx, 0));
817 h = match_expr_eval(x->u.binary.left, bol, eol, ctx, 0);
818 x->u.binary.left->hit |= h;
819 h |= match_expr_eval(x->u.binary.right, bol, eol, ctx, 1);
820 break;
821 default:
822 die("Unexpected node type (internal error) %d", x->node);
824 if (collect_hits)
825 x->hit |= h;
826 return h;
829 static int match_expr(struct grep_opt *opt, char *bol, char *eol,
830 enum grep_context ctx, int collect_hits)
832 struct grep_expr *x = opt->pattern_expression;
833 return match_expr_eval(x, bol, eol, ctx, collect_hits);
836 static int match_line(struct grep_opt *opt, char *bol, char *eol,
837 enum grep_context ctx, int collect_hits)
839 struct grep_pat *p;
840 regmatch_t match;
842 if (opt->extended)
843 return match_expr(opt, bol, eol, ctx, collect_hits);
845 /* we do not call with collect_hits without being extended */
846 for (p = opt->pattern_list; p; p = p->next) {
847 if (match_one_pattern(p, bol, eol, ctx, &match, 0))
848 return 1;
850 return 0;
853 static int match_next_pattern(struct grep_pat *p, char *bol, char *eol,
854 enum grep_context ctx,
855 regmatch_t *pmatch, int eflags)
857 regmatch_t match;
859 if (!match_one_pattern(p, bol, eol, ctx, &match, eflags))
860 return 0;
861 if (match.rm_so < 0 || match.rm_eo < 0)
862 return 0;
863 if (pmatch->rm_so >= 0 && pmatch->rm_eo >= 0) {
864 if (match.rm_so > pmatch->rm_so)
865 return 1;
866 if (match.rm_so == pmatch->rm_so && match.rm_eo < pmatch->rm_eo)
867 return 1;
869 pmatch->rm_so = match.rm_so;
870 pmatch->rm_eo = match.rm_eo;
871 return 1;
874 static int next_match(struct grep_opt *opt, char *bol, char *eol,
875 enum grep_context ctx, regmatch_t *pmatch, int eflags)
877 struct grep_pat *p;
878 int hit = 0;
880 pmatch->rm_so = pmatch->rm_eo = -1;
881 if (bol < eol) {
882 for (p = opt->pattern_list; p; p = p->next) {
883 switch (p->token) {
884 case GREP_PATTERN: /* atom */
885 case GREP_PATTERN_HEAD:
886 case GREP_PATTERN_BODY:
887 hit |= match_next_pattern(p, bol, eol, ctx,
888 pmatch, eflags);
889 break;
890 default:
891 break;
895 return hit;
898 static void show_line(struct grep_opt *opt, char *bol, char *eol,
899 const char *name, unsigned lno, char sign)
901 int rest = eol - bol;
902 char *line_color = NULL;
904 if (opt->file_break && opt->last_shown == 0) {
905 if (opt->show_hunk_mark)
906 opt->output(opt, "\n", 1);
907 } else if (opt->pre_context || opt->post_context || opt->funcbody) {
908 if (opt->last_shown == 0) {
909 if (opt->show_hunk_mark) {
910 output_color(opt, "--", 2, opt->color_sep);
911 opt->output(opt, "\n", 1);
913 } else if (lno > opt->last_shown + 1) {
914 output_color(opt, "--", 2, opt->color_sep);
915 opt->output(opt, "\n", 1);
918 if (opt->heading && opt->last_shown == 0) {
919 output_color(opt, name, strlen(name), opt->color_filename);
920 opt->output(opt, "\n", 1);
922 opt->last_shown = lno;
924 if (!opt->heading && opt->pathname) {
925 output_color(opt, name, strlen(name), opt->color_filename);
926 output_sep(opt, sign);
928 if (opt->linenum) {
929 char buf[32];
930 snprintf(buf, sizeof(buf), "%d", lno);
931 output_color(opt, buf, strlen(buf), opt->color_lineno);
932 output_sep(opt, sign);
934 if (opt->color) {
935 regmatch_t match;
936 enum grep_context ctx = GREP_CONTEXT_BODY;
937 int ch = *eol;
938 int eflags = 0;
940 if (sign == ':')
941 line_color = opt->color_selected;
942 else if (sign == '-')
943 line_color = opt->color_context;
944 else if (sign == '=')
945 line_color = opt->color_function;
946 *eol = '\0';
947 while (next_match(opt, bol, eol, ctx, &match, eflags)) {
948 if (match.rm_so == match.rm_eo)
949 break;
951 output_color(opt, bol, match.rm_so, line_color);
952 output_color(opt, bol + match.rm_so,
953 match.rm_eo - match.rm_so,
954 opt->color_match);
955 bol += match.rm_eo;
956 rest -= match.rm_eo;
957 eflags = REG_NOTBOL;
959 *eol = ch;
961 output_color(opt, bol, rest, line_color);
962 opt->output(opt, "\n", 1);
965 #ifndef NO_PTHREADS
966 int grep_use_locks;
969 * This lock protects access to the gitattributes machinery, which is
970 * not thread-safe.
972 pthread_mutex_t grep_attr_mutex;
974 static inline void grep_attr_lock(void)
976 if (grep_use_locks)
977 pthread_mutex_lock(&grep_attr_mutex);
980 static inline void grep_attr_unlock(void)
982 if (grep_use_locks)
983 pthread_mutex_unlock(&grep_attr_mutex);
987 * Same as git_attr_mutex, but protecting the thread-unsafe object db access.
989 pthread_mutex_t grep_read_mutex;
991 #else
992 #define grep_attr_lock()
993 #define grep_attr_unlock()
994 #endif
996 static int match_funcname(struct grep_opt *opt, struct grep_source *gs, char *bol, char *eol)
998 xdemitconf_t *xecfg = opt->priv;
999 if (xecfg && !xecfg->find_func) {
1000 grep_source_load_driver(gs);
1001 if (gs->driver->funcname.pattern) {
1002 const struct userdiff_funcname *pe = &gs->driver->funcname;
1003 xdiff_set_find_func(xecfg, pe->pattern, pe->cflags);
1004 } else {
1005 xecfg = opt->priv = NULL;
1009 if (xecfg) {
1010 char buf[1];
1011 return xecfg->find_func(bol, eol - bol, buf, 1,
1012 xecfg->find_func_priv) >= 0;
1015 if (bol == eol)
1016 return 0;
1017 if (isalpha(*bol) || *bol == '_' || *bol == '$')
1018 return 1;
1019 return 0;
1022 static void show_funcname_line(struct grep_opt *opt, struct grep_source *gs,
1023 char *bol, unsigned lno)
1025 while (bol > gs->buf) {
1026 char *eol = --bol;
1028 while (bol > gs->buf && bol[-1] != '\n')
1029 bol--;
1030 lno--;
1032 if (lno <= opt->last_shown)
1033 break;
1035 if (match_funcname(opt, gs, bol, eol)) {
1036 show_line(opt, bol, eol, gs->name, lno, '=');
1037 break;
1042 static void show_pre_context(struct grep_opt *opt, struct grep_source *gs,
1043 char *bol, char *end, unsigned lno)
1045 unsigned cur = lno, from = 1, funcname_lno = 0;
1046 int funcname_needed = !!opt->funcname;
1048 if (opt->funcbody && !match_funcname(opt, gs, bol, end))
1049 funcname_needed = 2;
1051 if (opt->pre_context < lno)
1052 from = lno - opt->pre_context;
1053 if (from <= opt->last_shown)
1054 from = opt->last_shown + 1;
1056 /* Rewind. */
1057 while (bol > gs->buf &&
1058 cur > (funcname_needed == 2 ? opt->last_shown + 1 : from)) {
1059 char *eol = --bol;
1061 while (bol > gs->buf && bol[-1] != '\n')
1062 bol--;
1063 cur--;
1064 if (funcname_needed && match_funcname(opt, gs, bol, eol)) {
1065 funcname_lno = cur;
1066 funcname_needed = 0;
1070 /* We need to look even further back to find a function signature. */
1071 if (opt->funcname && funcname_needed)
1072 show_funcname_line(opt, gs, bol, cur);
1074 /* Back forward. */
1075 while (cur < lno) {
1076 char *eol = bol, sign = (cur == funcname_lno) ? '=' : '-';
1078 while (*eol != '\n')
1079 eol++;
1080 show_line(opt, bol, eol, gs->name, cur, sign);
1081 bol = eol + 1;
1082 cur++;
1086 static int should_lookahead(struct grep_opt *opt)
1088 struct grep_pat *p;
1090 if (opt->extended)
1091 return 0; /* punt for too complex stuff */
1092 if (opt->invert)
1093 return 0;
1094 for (p = opt->pattern_list; p; p = p->next) {
1095 if (p->token != GREP_PATTERN)
1096 return 0; /* punt for "header only" and stuff */
1098 return 1;
1101 static int look_ahead(struct grep_opt *opt,
1102 unsigned long *left_p,
1103 unsigned *lno_p,
1104 char **bol_p)
1106 unsigned lno = *lno_p;
1107 char *bol = *bol_p;
1108 struct grep_pat *p;
1109 char *sp, *last_bol;
1110 regoff_t earliest = -1;
1112 for (p = opt->pattern_list; p; p = p->next) {
1113 int hit;
1114 regmatch_t m;
1116 hit = patmatch(p, bol, bol + *left_p, &m, 0);
1117 if (!hit || m.rm_so < 0 || m.rm_eo < 0)
1118 continue;
1119 if (earliest < 0 || m.rm_so < earliest)
1120 earliest = m.rm_so;
1123 if (earliest < 0) {
1124 *bol_p = bol + *left_p;
1125 *left_p = 0;
1126 return 1;
1128 for (sp = bol + earliest; bol < sp && sp[-1] != '\n'; sp--)
1129 ; /* find the beginning of the line */
1130 last_bol = sp;
1132 for (sp = bol; sp < last_bol; sp++) {
1133 if (*sp == '\n')
1134 lno++;
1136 *left_p -= last_bol - bol;
1137 *bol_p = last_bol;
1138 *lno_p = lno;
1139 return 0;
1142 static void std_output(struct grep_opt *opt, const void *buf, size_t size)
1144 fwrite(buf, size, 1, stdout);
1147 static int grep_source_1(struct grep_opt *opt, struct grep_source *gs, int collect_hits)
1149 char *bol;
1150 unsigned long left;
1151 unsigned lno = 1;
1152 unsigned last_hit = 0;
1153 int binary_match_only = 0;
1154 unsigned count = 0;
1155 int try_lookahead = 0;
1156 int show_function = 0;
1157 enum grep_context ctx = GREP_CONTEXT_HEAD;
1158 xdemitconf_t xecfg;
1160 if (!opt->output)
1161 opt->output = std_output;
1163 if (opt->pre_context || opt->post_context || opt->file_break ||
1164 opt->funcbody) {
1165 /* Show hunk marks, except for the first file. */
1166 if (opt->last_shown)
1167 opt->show_hunk_mark = 1;
1169 * If we're using threads then we can't easily identify
1170 * the first file. Always put hunk marks in that case
1171 * and skip the very first one later in work_done().
1173 if (opt->output != std_output)
1174 opt->show_hunk_mark = 1;
1176 opt->last_shown = 0;
1178 switch (opt->binary) {
1179 case GREP_BINARY_DEFAULT:
1180 if (grep_source_is_binary(gs))
1181 binary_match_only = 1;
1182 break;
1183 case GREP_BINARY_NOMATCH:
1184 if (grep_source_is_binary(gs))
1185 return 0; /* Assume unmatch */
1186 break;
1187 case GREP_BINARY_TEXT:
1188 break;
1189 default:
1190 die("bug: unknown binary handling mode");
1193 memset(&xecfg, 0, sizeof(xecfg));
1194 opt->priv = &xecfg;
1196 try_lookahead = should_lookahead(opt);
1198 if (grep_source_load(gs) < 0)
1199 return 0;
1201 bol = gs->buf;
1202 left = gs->size;
1203 while (left) {
1204 char *eol, ch;
1205 int hit;
1208 * look_ahead() skips quickly to the line that possibly
1209 * has the next hit; don't call it if we need to do
1210 * something more than just skipping the current line
1211 * in response to an unmatch for the current line. E.g.
1212 * inside a post-context window, we will show the current
1213 * line as a context around the previous hit when it
1214 * doesn't hit.
1216 if (try_lookahead
1217 && !(last_hit
1218 && (show_function ||
1219 lno <= last_hit + opt->post_context))
1220 && look_ahead(opt, &left, &lno, &bol))
1221 break;
1222 eol = end_of_line(bol, &left);
1223 ch = *eol;
1224 *eol = 0;
1226 if ((ctx == GREP_CONTEXT_HEAD) && (eol == bol))
1227 ctx = GREP_CONTEXT_BODY;
1229 hit = match_line(opt, bol, eol, ctx, collect_hits);
1230 *eol = ch;
1232 if (collect_hits)
1233 goto next_line;
1235 /* "grep -v -e foo -e bla" should list lines
1236 * that do not have either, so inversion should
1237 * be done outside.
1239 if (opt->invert)
1240 hit = !hit;
1241 if (opt->unmatch_name_only) {
1242 if (hit)
1243 return 0;
1244 goto next_line;
1246 if (hit) {
1247 count++;
1248 if (opt->status_only)
1249 return 1;
1250 if (opt->name_only) {
1251 show_name(opt, gs->name);
1252 return 1;
1254 if (opt->count)
1255 goto next_line;
1256 if (binary_match_only) {
1257 opt->output(opt, "Binary file ", 12);
1258 output_color(opt, gs->name, strlen(gs->name),
1259 opt->color_filename);
1260 opt->output(opt, " matches\n", 9);
1261 return 1;
1263 /* Hit at this line. If we haven't shown the
1264 * pre-context lines, we would need to show them.
1266 if (opt->pre_context || opt->funcbody)
1267 show_pre_context(opt, gs, bol, eol, lno);
1268 else if (opt->funcname)
1269 show_funcname_line(opt, gs, bol, lno);
1270 show_line(opt, bol, eol, gs->name, lno, ':');
1271 last_hit = lno;
1272 if (opt->funcbody)
1273 show_function = 1;
1274 goto next_line;
1276 if (show_function && match_funcname(opt, gs, bol, eol))
1277 show_function = 0;
1278 if (show_function ||
1279 (last_hit && lno <= last_hit + opt->post_context)) {
1280 /* If the last hit is within the post context,
1281 * we need to show this line.
1283 show_line(opt, bol, eol, gs->name, lno, '-');
1286 next_line:
1287 bol = eol + 1;
1288 if (!left)
1289 break;
1290 left--;
1291 lno++;
1294 if (collect_hits)
1295 return 0;
1297 if (opt->status_only)
1298 return 0;
1299 if (opt->unmatch_name_only) {
1300 /* We did not see any hit, so we want to show this */
1301 show_name(opt, gs->name);
1302 return 1;
1305 xdiff_clear_find_func(&xecfg);
1306 opt->priv = NULL;
1308 /* NEEDSWORK:
1309 * The real "grep -c foo *.c" gives many "bar.c:0" lines,
1310 * which feels mostly useless but sometimes useful. Maybe
1311 * make it another option? For now suppress them.
1313 if (opt->count && count) {
1314 char buf[32];
1315 output_color(opt, gs->name, strlen(gs->name), opt->color_filename);
1316 output_sep(opt, ':');
1317 snprintf(buf, sizeof(buf), "%u\n", count);
1318 opt->output(opt, buf, strlen(buf));
1319 return 1;
1321 return !!last_hit;
1324 static void clr_hit_marker(struct grep_expr *x)
1326 /* All-hit markers are meaningful only at the very top level
1327 * OR node.
1329 while (1) {
1330 x->hit = 0;
1331 if (x->node != GREP_NODE_OR)
1332 return;
1333 x->u.binary.left->hit = 0;
1334 x = x->u.binary.right;
1338 static int chk_hit_marker(struct grep_expr *x)
1340 /* Top level nodes have hit markers. See if they all are hits */
1341 while (1) {
1342 if (x->node != GREP_NODE_OR)
1343 return x->hit;
1344 if (!x->u.binary.left->hit)
1345 return 0;
1346 x = x->u.binary.right;
1350 int grep_source(struct grep_opt *opt, struct grep_source *gs)
1353 * we do not have to do the two-pass grep when we do not check
1354 * buffer-wide "all-match".
1356 if (!opt->all_match)
1357 return grep_source_1(opt, gs, 0);
1359 /* Otherwise the toplevel "or" terms hit a bit differently.
1360 * We first clear hit markers from them.
1362 clr_hit_marker(opt->pattern_expression);
1363 grep_source_1(opt, gs, 1);
1365 if (!chk_hit_marker(opt->pattern_expression))
1366 return 0;
1368 return grep_source_1(opt, gs, 0);
1371 int grep_buffer(struct grep_opt *opt, char *buf, unsigned long size)
1373 struct grep_source gs;
1374 int r;
1376 grep_source_init(&gs, GREP_SOURCE_BUF, NULL, NULL);
1377 gs.buf = buf;
1378 gs.size = size;
1380 r = grep_source(opt, &gs);
1382 grep_source_clear(&gs);
1383 return r;
1386 void grep_source_init(struct grep_source *gs, enum grep_source_type type,
1387 const char *name, const void *identifier)
1389 gs->type = type;
1390 gs->name = name ? xstrdup(name) : NULL;
1391 gs->buf = NULL;
1392 gs->size = 0;
1393 gs->driver = NULL;
1395 switch (type) {
1396 case GREP_SOURCE_FILE:
1397 gs->identifier = xstrdup(identifier);
1398 break;
1399 case GREP_SOURCE_SHA1:
1400 gs->identifier = xmalloc(20);
1401 memcpy(gs->identifier, identifier, 20);
1402 break;
1403 case GREP_SOURCE_BUF:
1404 gs->identifier = NULL;
1408 void grep_source_clear(struct grep_source *gs)
1410 free(gs->name);
1411 gs->name = NULL;
1412 free(gs->identifier);
1413 gs->identifier = NULL;
1414 grep_source_clear_data(gs);
1417 void grep_source_clear_data(struct grep_source *gs)
1419 switch (gs->type) {
1420 case GREP_SOURCE_FILE:
1421 case GREP_SOURCE_SHA1:
1422 free(gs->buf);
1423 gs->buf = NULL;
1424 gs->size = 0;
1425 break;
1426 case GREP_SOURCE_BUF:
1427 /* leave user-provided buf intact */
1428 break;
1432 static int grep_source_load_sha1(struct grep_source *gs)
1434 enum object_type type;
1436 grep_read_lock();
1437 gs->buf = read_sha1_file(gs->identifier, &type, &gs->size);
1438 grep_read_unlock();
1440 if (!gs->buf)
1441 return error(_("'%s': unable to read %s"),
1442 gs->name,
1443 sha1_to_hex(gs->identifier));
1444 return 0;
1447 static int grep_source_load_file(struct grep_source *gs)
1449 const char *filename = gs->identifier;
1450 struct stat st;
1451 char *data;
1452 size_t size;
1453 int i;
1455 if (lstat(filename, &st) < 0) {
1456 err_ret:
1457 if (errno != ENOENT)
1458 error(_("'%s': %s"), filename, strerror(errno));
1459 return -1;
1461 if (!S_ISREG(st.st_mode))
1462 return -1;
1463 size = xsize_t(st.st_size);
1464 i = open(filename, O_RDONLY);
1465 if (i < 0)
1466 goto err_ret;
1467 data = xmalloc(size + 1);
1468 if (st.st_size != read_in_full(i, data, size)) {
1469 error(_("'%s': short read %s"), filename, strerror(errno));
1470 close(i);
1471 free(data);
1472 return -1;
1474 close(i);
1475 data[size] = 0;
1477 gs->buf = data;
1478 gs->size = size;
1479 return 0;
1482 static int grep_source_load(struct grep_source *gs)
1484 if (gs->buf)
1485 return 0;
1487 switch (gs->type) {
1488 case GREP_SOURCE_FILE:
1489 return grep_source_load_file(gs);
1490 case GREP_SOURCE_SHA1:
1491 return grep_source_load_sha1(gs);
1492 case GREP_SOURCE_BUF:
1493 return gs->buf ? 0 : -1;
1495 die("BUG: invalid grep_source type");
1498 void grep_source_load_driver(struct grep_source *gs)
1500 if (gs->driver)
1501 return;
1503 grep_attr_lock();
1504 gs->driver = userdiff_find_by_path(gs->name);
1505 if (!gs->driver)
1506 gs->driver = userdiff_find_by_name("default");
1507 grep_attr_unlock();
1510 static int grep_source_is_binary(struct grep_source *gs)
1512 grep_source_load_driver(gs);
1513 if (gs->driver->binary != -1)
1514 return gs->driver->binary;
1516 if (!grep_source_load(gs))
1517 return buffer_is_binary(gs->buf, gs->size);
1519 return 0;