1#include "cache.h"
2#include "grep.h"
3#include "userdiff.h"
4#include "xdiff-interface.h"
5
6static struct grep_pat *create_grep_pat(const char *pat, size_t patlen,
7 const char *origin, int no,
8 enum grep_pat_token t,
9 enum grep_header_field field)
10{
11 struct grep_pat *p = xcalloc(1, sizeof(*p));
12 p->pattern = xmemdupz(pat, patlen);
13 p->patternlen = patlen;
14 p->origin = origin;
15 p->no = no;
16 p->token = t;
17 p->field = field;
18 return p;
19}
20
21static void do_append_grep_pat(struct grep_pat ***tail, struct grep_pat *p)
22{
23 **tail = p;
24 *tail = &p->next;
25 p->next = NULL;
26
27 switch (p->token) {
28 case GREP_PATTERN: /* atom */
29 case GREP_PATTERN_HEAD:
30 case GREP_PATTERN_BODY:
31 for (;;) {
32 struct grep_pat *new_pat;
33 size_t len = 0;
34 char *cp = p->pattern + p->patternlen, *nl = NULL;
35 while (++len <= p->patternlen) {
36 if (*(--cp) == '\n') {
37 nl = cp;
38 break;
39 }
40 }
41 if (!nl)
42 break;
43 new_pat = create_grep_pat(nl + 1, len - 1, p->origin,
44 p->no, p->token, p->field);
45 new_pat->next = p->next;
46 if (!p->next)
47 *tail = &new_pat->next;
48 p->next = new_pat;
49 *nl = '\0';
50 p->patternlen -= len;
51 }
52 break;
53 default:
54 break;
55 }
56}
57
58void append_header_grep_pattern(struct grep_opt *opt,
59 enum grep_header_field field, const char *pat)
60{
61 struct grep_pat *p = create_grep_pat(pat, strlen(pat), "header", 0,
62 GREP_PATTERN_HEAD, field);
63 do_append_grep_pat(&opt->header_tail, p);
64}
65
66void append_grep_pattern(struct grep_opt *opt, const char *pat,
67 const char *origin, int no, enum grep_pat_token t)
68{
69 append_grep_pat(opt, pat, strlen(pat), origin, no, t);
70}
71
72void append_grep_pat(struct grep_opt *opt, const char *pat, size_t patlen,
73 const char *origin, int no, enum grep_pat_token t)
74{
75 struct grep_pat *p = create_grep_pat(pat, patlen, origin, no, t, 0);
76 do_append_grep_pat(&opt->pattern_tail, p);
77}
78
79struct grep_opt *grep_opt_dup(const struct grep_opt *opt)
80{
81 struct grep_pat *pat;
82 struct grep_opt *ret = xmalloc(sizeof(struct grep_opt));
83 *ret = *opt;
84
85 ret->pattern_list = NULL;
86 ret->pattern_tail = &ret->pattern_list;
87
88 for(pat = opt->pattern_list; pat != NULL; pat = pat->next)
89 {
90 if(pat->token == GREP_PATTERN_HEAD)
91 append_header_grep_pattern(ret, pat->field,
92 pat->pattern);
93 else
94 append_grep_pat(ret, pat->pattern, pat->patternlen,
95 pat->origin, pat->no, pat->token);
96 }
97
98 return ret;
99}
100
101static NORETURN void compile_regexp_failed(const struct grep_pat *p,
102 const char *error)
103{
104 char where[1024];
105
106 if (p->no)
107 sprintf(where, "In '%s' at %d, ", p->origin, p->no);
108 else if (p->origin)
109 sprintf(where, "%s, ", p->origin);
110 else
111 where[0] = 0;
112
113 die("%s'%s': %s", where, p->pattern, error);
114}
115
116#ifdef USE_LIBPCRE
117static void compile_pcre_regexp(struct grep_pat *p, const struct grep_opt *opt)
118{
119 const char *error;
120 int erroffset;
121 int options = PCRE_MULTILINE;
122
123 if (opt->ignore_case)
124 options |= PCRE_CASELESS;
125
126 p->pcre_regexp = pcre_compile(p->pattern, options, &error, &erroffset,
127 NULL);
128 if (!p->pcre_regexp)
129 compile_regexp_failed(p, error);
130
131 p->pcre_extra_info = pcre_study(p->pcre_regexp, 0, &error);
132 if (!p->pcre_extra_info && error)
133 die("%s", error);
134}
135
136static int pcrematch(struct grep_pat *p, const char *line, const char *eol,
137 regmatch_t *match, int eflags)
138{
139 int ovector[30], ret, flags = 0;
140
141 if (eflags & REG_NOTBOL)
142 flags |= PCRE_NOTBOL;
143
144 ret = pcre_exec(p->pcre_regexp, p->pcre_extra_info, line, eol - line,
145 0, flags, ovector, ARRAY_SIZE(ovector));
146 if (ret < 0 && ret != PCRE_ERROR_NOMATCH)
147 die("pcre_exec failed with error code %d", ret);
148 if (ret > 0) {
149 ret = 0;
150 match->rm_so = ovector[0];
151 match->rm_eo = ovector[1];
152 }
153
154 return ret;
155}
156
157static void free_pcre_regexp(struct grep_pat *p)
158{
159 pcre_free(p->pcre_regexp);
160 pcre_free(p->pcre_extra_info);
161}
162#else /* !USE_LIBPCRE */
163static void compile_pcre_regexp(struct grep_pat *p, const struct grep_opt *opt)
164{
165 die("cannot use Perl-compatible regexes when not compiled with USE_LIBPCRE");
166}
167
168static int pcrematch(struct grep_pat *p, const char *line, const char *eol,
169 regmatch_t *match, int eflags)
170{
171 return 1;
172}
173
174static void free_pcre_regexp(struct grep_pat *p)
175{
176}
177#endif /* !USE_LIBPCRE */
178
179static int is_fixed(const char *s, size_t len)
180{
181 size_t i;
182
183 /* regcomp cannot accept patterns with NULs so we
184 * consider any pattern containing a NUL fixed.
185 */
186 if (memchr(s, 0, len))
187 return 1;
188
189 for (i = 0; i < len; i++) {
190 if (is_regex_special(s[i]))
191 return 0;
192 }
193
194 return 1;
195}
196
197static void compile_regexp(struct grep_pat *p, struct grep_opt *opt)
198{
199 int err;
200
201 p->word_regexp = opt->word_regexp;
202 p->ignore_case = opt->ignore_case;
203
204 if (opt->fixed || is_fixed(p->pattern, p->patternlen))
205 p->fixed = 1;
206 else
207 p->fixed = 0;
208
209 if (p->fixed) {
210 if (opt->regflags & REG_ICASE || p->ignore_case)
211 p->kws = kwsalloc(tolower_trans_tbl);
212 else
213 p->kws = kwsalloc(NULL);
214 kwsincr(p->kws, p->pattern, p->patternlen);
215 kwsprep(p->kws);
216 return;
217 }
218
219 if (opt->pcre) {
220 compile_pcre_regexp(p, opt);
221 return;
222 }
223
224 err = regcomp(&p->regexp, p->pattern, opt->regflags);
225 if (err) {
226 char errbuf[1024];
227 regerror(err, &p->regexp, errbuf, 1024);
228 regfree(&p->regexp);
229 compile_regexp_failed(p, errbuf);
230 }
231}
232
233static struct grep_expr *compile_pattern_or(struct grep_pat **);
234static struct grep_expr *compile_pattern_atom(struct grep_pat **list)
235{
236 struct grep_pat *p;
237 struct grep_expr *x;
238
239 p = *list;
240 if (!p)
241 return NULL;
242 switch (p->token) {
243 case GREP_PATTERN: /* atom */
244 case GREP_PATTERN_HEAD:
245 case GREP_PATTERN_BODY:
246 x = xcalloc(1, sizeof (struct grep_expr));
247 x->node = GREP_NODE_ATOM;
248 x->u.atom = p;
249 *list = p->next;
250 return x;
251 case GREP_OPEN_PAREN:
252 *list = p->next;
253 x = compile_pattern_or(list);
254 if (!*list || (*list)->token != GREP_CLOSE_PAREN)
255 die("unmatched parenthesis");
256 *list = (*list)->next;
257 return x;
258 default:
259 return NULL;
260 }
261}
262
263static struct grep_expr *compile_pattern_not(struct grep_pat **list)
264{
265 struct grep_pat *p;
266 struct grep_expr *x;
267
268 p = *list;
269 if (!p)
270 return NULL;
271 switch (p->token) {
272 case GREP_NOT:
273 if (!p->next)
274 die("--not not followed by pattern expression");
275 *list = p->next;
276 x = xcalloc(1, sizeof (struct grep_expr));
277 x->node = GREP_NODE_NOT;
278 x->u.unary = compile_pattern_not(list);
279 if (!x->u.unary)
280 die("--not followed by non pattern expression");
281 return x;
282 default:
283 return compile_pattern_atom(list);
284 }
285}
286
287static struct grep_expr *compile_pattern_and(struct grep_pat **list)
288{
289 struct grep_pat *p;
290 struct grep_expr *x, *y, *z;
291
292 x = compile_pattern_not(list);
293 p = *list;
294 if (p && p->token == GREP_AND) {
295 if (!p->next)
296 die("--and not followed by pattern expression");
297 *list = p->next;
298 y = compile_pattern_and(list);
299 if (!y)
300 die("--and not followed by pattern expression");
301 z = xcalloc(1, sizeof (struct grep_expr));
302 z->node = GREP_NODE_AND;
303 z->u.binary.left = x;
304 z->u.binary.right = y;
305 return z;
306 }
307 return x;
308}
309
310static struct grep_expr *compile_pattern_or(struct grep_pat **list)
311{
312 struct grep_pat *p;
313 struct grep_expr *x, *y, *z;
314
315 x = compile_pattern_and(list);
316 p = *list;
317 if (x && p && p->token != GREP_CLOSE_PAREN) {
318 y = compile_pattern_or(list);
319 if (!y)
320 die("not a pattern expression %s", p->pattern);
321 z = xcalloc(1, sizeof (struct grep_expr));
322 z->node = GREP_NODE_OR;
323 z->u.binary.left = x;
324 z->u.binary.right = y;
325 return z;
326 }
327 return x;
328}
329
330static struct grep_expr *compile_pattern_expr(struct grep_pat **list)
331{
332 return compile_pattern_or(list);
333}
334
335static void indent(int in)
336{
337 while (in-- > 0)
338 fputc(' ', stderr);
339}
340
341static void dump_grep_pat(struct grep_pat *p)
342{
343 switch (p->token) {
344 case GREP_AND: fprintf(stderr, "*and*"); break;
345 case GREP_OPEN_PAREN: fprintf(stderr, "*(*"); break;
346 case GREP_CLOSE_PAREN: fprintf(stderr, "*)*"); break;
347 case GREP_NOT: fprintf(stderr, "*not*"); break;
348 case GREP_OR: fprintf(stderr, "*or*"); break;
349
350 case GREP_PATTERN: fprintf(stderr, "pattern"); break;
351 case GREP_PATTERN_HEAD: fprintf(stderr, "pattern_head"); break;
352 case GREP_PATTERN_BODY: fprintf(stderr, "pattern_body"); break;
353 }
354
355 switch (p->token) {
356 default: break;
357 case GREP_PATTERN_HEAD:
358 fprintf(stderr, "<head %d>", p->field); break;
359 case GREP_PATTERN_BODY:
360 fprintf(stderr, "<body>"); break;
361 }
362 switch (p->token) {
363 default: break;
364 case GREP_PATTERN_HEAD:
365 case GREP_PATTERN_BODY:
366 case GREP_PATTERN:
367 fprintf(stderr, "%.*s", (int)p->patternlen, p->pattern);
368 break;
369 }
370 fputc('\n', stderr);
371}
372
373static void dump_grep_expression_1(struct grep_expr *x, int in)
374{
375 indent(in);
376 switch (x->node) {
377 case GREP_NODE_TRUE:
378 fprintf(stderr, "true\n");
379 break;
380 case GREP_NODE_ATOM:
381 dump_grep_pat(x->u.atom);
382 break;
383 case GREP_NODE_NOT:
384 fprintf(stderr, "(not\n");
385 dump_grep_expression_1(x->u.unary, in+1);
386 indent(in);
387 fprintf(stderr, ")\n");
388 break;
389 case GREP_NODE_AND:
390 fprintf(stderr, "(and\n");
391 dump_grep_expression_1(x->u.binary.left, in+1);
392 dump_grep_expression_1(x->u.binary.right, in+1);
393 indent(in);
394 fprintf(stderr, ")\n");
395 break;
396 case GREP_NODE_OR:
397 fprintf(stderr, "(or\n");
398 dump_grep_expression_1(x->u.binary.left, in+1);
399 dump_grep_expression_1(x->u.binary.right, in+1);
400 indent(in);
401 fprintf(stderr, ")\n");
402 break;
403 }
404}
405
406void dump_grep_expression(struct grep_opt *opt)
407{
408 struct grep_expr *x = opt->pattern_expression;
409
410 if (opt->all_match)
411 fprintf(stderr, "[all-match]\n");
412 dump_grep_expression_1(x, 0);
413 fflush(NULL);
414}
415
416static struct grep_expr *grep_true_expr(void)
417{
418 struct grep_expr *z = xcalloc(1, sizeof(*z));
419 z->node = GREP_NODE_TRUE;
420 return z;
421}
422
423static struct grep_expr *grep_or_expr(struct grep_expr *left, struct grep_expr *right)
424{
425 struct grep_expr *z = xcalloc(1, sizeof(*z));
426 z->node = GREP_NODE_OR;
427 z->u.binary.left = left;
428 z->u.binary.right = right;
429 return z;
430}
431
432static struct grep_expr *prep_header_patterns(struct grep_opt *opt)
433{
434 struct grep_pat *p;
435 struct grep_expr *header_expr;
436 struct grep_expr *(header_group[GREP_HEADER_FIELD_MAX]);
437 enum grep_header_field fld;
438
439 if (!opt->header_list)
440 return NULL;
441
442 for (p = opt->header_list; p; p = p->next) {
443 if (p->token != GREP_PATTERN_HEAD)
444 die("bug: a non-header pattern in grep header list.");
445 if (p->field < 0 || GREP_HEADER_FIELD_MAX <= p->field)
446 die("bug: unknown header field %d", p->field);
447 compile_regexp(p, opt);
448 }
449
450 for (fld = 0; fld < GREP_HEADER_FIELD_MAX; fld++)
451 header_group[fld] = NULL;
452
453 for (p = opt->header_list; p; p = p->next) {
454 struct grep_expr *h;
455 struct grep_pat *pp = p;
456
457 h = compile_pattern_atom(&pp);
458 if (!h || pp != p->next)
459 die("bug: malformed header expr");
460 if (!header_group[p->field]) {
461 header_group[p->field] = h;
462 continue;
463 }
464 header_group[p->field] = grep_or_expr(h, header_group[p->field]);
465 }
466
467 header_expr = NULL;
468
469 for (fld = 0; fld < GREP_HEADER_FIELD_MAX; fld++) {
470 if (!header_group[fld])
471 continue;
472 if (!header_expr)
473 header_expr = grep_true_expr();
474 header_expr = grep_or_expr(header_group[fld], header_expr);
475 }
476 return header_expr;
477}
478
479static struct grep_expr *grep_splice_or(struct grep_expr *x, struct grep_expr *y)
480{
481 struct grep_expr *z = x;
482
483 while (x) {
484 assert(x->node == GREP_NODE_OR);
485 if (x->u.binary.right &&
486 x->u.binary.right->node == GREP_NODE_TRUE) {
487 x->u.binary.right = y;
488 break;
489 }
490 x = x->u.binary.right;
491 }
492 return z;
493}
494
495static void compile_grep_patterns_real(struct grep_opt *opt)
496{
497 struct grep_pat *p;
498 struct grep_expr *header_expr = prep_header_patterns(opt);
499
500 for (p = opt->pattern_list; p; p = p->next) {
501 switch (p->token) {
502 case GREP_PATTERN: /* atom */
503 case GREP_PATTERN_HEAD:
504 case GREP_PATTERN_BODY:
505 compile_regexp(p, opt);
506 break;
507 default:
508 opt->extended = 1;
509 break;
510 }
511 }
512
513 if (opt->all_match || header_expr)
514 opt->extended = 1;
515 else if (!opt->extended && !opt->debug)
516 return;
517
518 p = opt->pattern_list;
519 if (p)
520 opt->pattern_expression = compile_pattern_expr(&p);
521 if (p)
522 die("incomplete pattern expression: %s", p->pattern);
523
524 if (!header_expr)
525 return;
526
527 if (!opt->pattern_expression)
528 opt->pattern_expression = header_expr;
529 else if (opt->all_match)
530 opt->pattern_expression = grep_splice_or(header_expr,
531 opt->pattern_expression);
532 else
533 opt->pattern_expression = grep_or_expr(opt->pattern_expression,
534 header_expr);
535 opt->all_match = 1;
536}
537
538void compile_grep_patterns(struct grep_opt *opt)
539{
540 compile_grep_patterns_real(opt);
541 if (opt->debug)
542 dump_grep_expression(opt);
543}
544
545static void free_pattern_expr(struct grep_expr *x)
546{
547 switch (x->node) {
548 case GREP_NODE_TRUE:
549 case GREP_NODE_ATOM:
550 break;
551 case GREP_NODE_NOT:
552 free_pattern_expr(x->u.unary);
553 break;
554 case GREP_NODE_AND:
555 case GREP_NODE_OR:
556 free_pattern_expr(x->u.binary.left);
557 free_pattern_expr(x->u.binary.right);
558 break;
559 }
560 free(x);
561}
562
563void free_grep_patterns(struct grep_opt *opt)
564{
565 struct grep_pat *p, *n;
566
567 for (p = opt->pattern_list; p; p = n) {
568 n = p->next;
569 switch (p->token) {
570 case GREP_PATTERN: /* atom */
571 case GREP_PATTERN_HEAD:
572 case GREP_PATTERN_BODY:
573 if (p->kws)
574 kwsfree(p->kws);
575 else if (p->pcre_regexp)
576 free_pcre_regexp(p);
577 else
578 regfree(&p->regexp);
579 free(p->pattern);
580 break;
581 default:
582 break;
583 }
584 free(p);
585 }
586
587 if (!opt->extended)
588 return;
589 free_pattern_expr(opt->pattern_expression);
590}
591
592static char *end_of_line(char *cp, unsigned long *left)
593{
594 unsigned long l = *left;
595 while (l && *cp != '\n') {
596 l--;
597 cp++;
598 }
599 *left = l;
600 return cp;
601}
602
603static int word_char(char ch)
604{
605 return isalnum(ch) || ch == '_';
606}
607
608static void output_color(struct grep_opt *opt, const void *data, size_t size,
609 const char *color)
610{
611 if (want_color(opt->color) && color && color[0]) {
612 opt->output(opt, color, strlen(color));
613 opt->output(opt, data, size);
614 opt->output(opt, GIT_COLOR_RESET, strlen(GIT_COLOR_RESET));
615 } else
616 opt->output(opt, data, size);
617}
618
619static void output_sep(struct grep_opt *opt, char sign)
620{
621 if (opt->null_following_name)
622 opt->output(opt, "\0", 1);
623 else
624 output_color(opt, &sign, 1, opt->color_sep);
625}
626
627static void show_name(struct grep_opt *opt, const char *name)
628{
629 output_color(opt, name, strlen(name), opt->color_filename);
630 opt->output(opt, opt->null_following_name ? "\0" : "\n", 1);
631}
632
633static int fixmatch(struct grep_pat *p, char *line, char *eol,
634 regmatch_t *match)
635{
636 struct kwsmatch kwsm;
637 size_t offset = kwsexec(p->kws, line, eol - line, &kwsm);
638 if (offset == -1) {
639 match->rm_so = match->rm_eo = -1;
640 return REG_NOMATCH;
641 } else {
642 match->rm_so = offset;
643 match->rm_eo = match->rm_so + kwsm.size[0];
644 return 0;
645 }
646}
647
648static int regmatch(const regex_t *preg, char *line, char *eol,
649 regmatch_t *match, int eflags)
650{
651#ifdef REG_STARTEND
652 match->rm_so = 0;
653 match->rm_eo = eol - line;
654 eflags |= REG_STARTEND;
655#endif
656 return regexec(preg, line, 1, match, eflags);
657}
658
659static int patmatch(struct grep_pat *p, char *line, char *eol,
660 regmatch_t *match, int eflags)
661{
662 int hit;
663
664 if (p->fixed)
665 hit = !fixmatch(p, line, eol, match);
666 else if (p->pcre_regexp)
667 hit = !pcrematch(p, line, eol, match, eflags);
668 else
669 hit = !regmatch(&p->regexp, line, eol, match, eflags);
670
671 return hit;
672}
673
674static int strip_timestamp(char *bol, char **eol_p)
675{
676 char *eol = *eol_p;
677 int ch;
678
679 while (bol < --eol) {
680 if (*eol != '>')
681 continue;
682 *eol_p = ++eol;
683 ch = *eol;
684 *eol = '\0';
685 return ch;
686 }
687 return 0;
688}
689
690static struct {
691 const char *field;
692 size_t len;
693} header_field[] = {
694 { "author ", 7 },
695 { "committer ", 10 },
696};
697
698static int match_one_pattern(struct grep_pat *p, char *bol, char *eol,
699 enum grep_context ctx,
700 regmatch_t *pmatch, int eflags)
701{
702 int hit = 0;
703 int saved_ch = 0;
704 const char *start = bol;
705
706 if ((p->token != GREP_PATTERN) &&
707 ((p->token == GREP_PATTERN_HEAD) != (ctx == GREP_CONTEXT_HEAD)))
708 return 0;
709
710 if (p->token == GREP_PATTERN_HEAD) {
711 const char *field;
712 size_t len;
713 assert(p->field < ARRAY_SIZE(header_field));
714 field = header_field[p->field].field;
715 len = header_field[p->field].len;
716 if (strncmp(bol, field, len))
717 return 0;
718 bol += len;
719 saved_ch = strip_timestamp(bol, &eol);
720 }
721
722 again:
723 hit = patmatch(p, bol, eol, pmatch, eflags);
724
725 if (hit && p->word_regexp) {
726 if ((pmatch[0].rm_so < 0) ||
727 (eol - bol) < pmatch[0].rm_so ||
728 (pmatch[0].rm_eo < 0) ||
729 (eol - bol) < pmatch[0].rm_eo)
730 die("regexp returned nonsense");
731
732 /* Match beginning must be either beginning of the
733 * line, or at word boundary (i.e. the last char must
734 * not be a word char). Similarly, match end must be
735 * either end of the line, or at word boundary
736 * (i.e. the next char must not be a word char).
737 */
738 if ( ((pmatch[0].rm_so == 0) ||
739 !word_char(bol[pmatch[0].rm_so-1])) &&
740 ((pmatch[0].rm_eo == (eol-bol)) ||
741 !word_char(bol[pmatch[0].rm_eo])) )
742 ;
743 else
744 hit = 0;
745
746 /* Words consist of at least one character. */
747 if (pmatch->rm_so == pmatch->rm_eo)
748 hit = 0;
749
750 if (!hit && pmatch[0].rm_so + bol + 1 < eol) {
751 /* There could be more than one match on the
752 * line, and the first match might not be
753 * strict word match. But later ones could be!
754 * Forward to the next possible start, i.e. the
755 * next position following a non-word char.
756 */
757 bol = pmatch[0].rm_so + bol + 1;
758 while (word_char(bol[-1]) && bol < eol)
759 bol++;
760 eflags |= REG_NOTBOL;
761 if (bol < eol)
762 goto again;
763 }
764 }
765 if (p->token == GREP_PATTERN_HEAD && saved_ch)
766 *eol = saved_ch;
767 if (hit) {
768 pmatch[0].rm_so += bol - start;
769 pmatch[0].rm_eo += bol - start;
770 }
771 return hit;
772}
773
774static int match_expr_eval(struct grep_expr *x, char *bol, char *eol,
775 enum grep_context ctx, int collect_hits)
776{
777 int h = 0;
778 regmatch_t match;
779
780 if (!x)
781 die("Not a valid grep expression");
782 switch (x->node) {
783 case GREP_NODE_TRUE:
784 h = 1;
785 break;
786 case GREP_NODE_ATOM:
787 h = match_one_pattern(x->u.atom, bol, eol, ctx, &match, 0);
788 break;
789 case GREP_NODE_NOT:
790 h = !match_expr_eval(x->u.unary, bol, eol, ctx, 0);
791 break;
792 case GREP_NODE_AND:
793 if (!match_expr_eval(x->u.binary.left, bol, eol, ctx, 0))
794 return 0;
795 h = match_expr_eval(x->u.binary.right, bol, eol, ctx, 0);
796 break;
797 case GREP_NODE_OR:
798 if (!collect_hits)
799 return (match_expr_eval(x->u.binary.left,
800 bol, eol, ctx, 0) ||
801 match_expr_eval(x->u.binary.right,
802 bol, eol, ctx, 0));
803 h = match_expr_eval(x->u.binary.left, bol, eol, ctx, 0);
804 x->u.binary.left->hit |= h;
805 h |= match_expr_eval(x->u.binary.right, bol, eol, ctx, 1);
806 break;
807 default:
808 die("Unexpected node type (internal error) %d", x->node);
809 }
810 if (collect_hits)
811 x->hit |= h;
812 return h;
813}
814
815static int match_expr(struct grep_opt *opt, char *bol, char *eol,
816 enum grep_context ctx, int collect_hits)
817{
818 struct grep_expr *x = opt->pattern_expression;
819 return match_expr_eval(x, bol, eol, ctx, collect_hits);
820}
821
822static int match_line(struct grep_opt *opt, char *bol, char *eol,
823 enum grep_context ctx, int collect_hits)
824{
825 struct grep_pat *p;
826 regmatch_t match;
827
828 if (opt->extended)
829 return match_expr(opt, bol, eol, ctx, collect_hits);
830
831 /* we do not call with collect_hits without being extended */
832 for (p = opt->pattern_list; p; p = p->next) {
833 if (match_one_pattern(p, bol, eol, ctx, &match, 0))
834 return 1;
835 }
836 return 0;
837}
838
839static int match_next_pattern(struct grep_pat *p, char *bol, char *eol,
840 enum grep_context ctx,
841 regmatch_t *pmatch, int eflags)
842{
843 regmatch_t match;
844
845 if (!match_one_pattern(p, bol, eol, ctx, &match, eflags))
846 return 0;
847 if (match.rm_so < 0 || match.rm_eo < 0)
848 return 0;
849 if (pmatch->rm_so >= 0 && pmatch->rm_eo >= 0) {
850 if (match.rm_so > pmatch->rm_so)
851 return 1;
852 if (match.rm_so == pmatch->rm_so && match.rm_eo < pmatch->rm_eo)
853 return 1;
854 }
855 pmatch->rm_so = match.rm_so;
856 pmatch->rm_eo = match.rm_eo;
857 return 1;
858}
859
860static int next_match(struct grep_opt *opt, char *bol, char *eol,
861 enum grep_context ctx, regmatch_t *pmatch, int eflags)
862{
863 struct grep_pat *p;
864 int hit = 0;
865
866 pmatch->rm_so = pmatch->rm_eo = -1;
867 if (bol < eol) {
868 for (p = opt->pattern_list; p; p = p->next) {
869 switch (p->token) {
870 case GREP_PATTERN: /* atom */
871 case GREP_PATTERN_HEAD:
872 case GREP_PATTERN_BODY:
873 hit |= match_next_pattern(p, bol, eol, ctx,
874 pmatch, eflags);
875 break;
876 default:
877 break;
878 }
879 }
880 }
881 return hit;
882}
883
884static void show_line(struct grep_opt *opt, char *bol, char *eol,
885 const char *name, unsigned lno, char sign)
886{
887 int rest = eol - bol;
888 char *line_color = NULL;
889
890 if (opt->file_break && opt->last_shown == 0) {
891 if (opt->show_hunk_mark)
892 opt->output(opt, "\n", 1);
893 } else if (opt->pre_context || opt->post_context || opt->funcbody) {
894 if (opt->last_shown == 0) {
895 if (opt->show_hunk_mark) {
896 output_color(opt, "--", 2, opt->color_sep);
897 opt->output(opt, "\n", 1);
898 }
899 } else if (lno > opt->last_shown + 1) {
900 output_color(opt, "--", 2, opt->color_sep);
901 opt->output(opt, "\n", 1);
902 }
903 }
904 if (opt->heading && opt->last_shown == 0) {
905 output_color(opt, name, strlen(name), opt->color_filename);
906 opt->output(opt, "\n", 1);
907 }
908 opt->last_shown = lno;
909
910 if (!opt->heading && opt->pathname) {
911 output_color(opt, name, strlen(name), opt->color_filename);
912 output_sep(opt, sign);
913 }
914 if (opt->linenum) {
915 char buf[32];
916 snprintf(buf, sizeof(buf), "%d", lno);
917 output_color(opt, buf, strlen(buf), opt->color_lineno);
918 output_sep(opt, sign);
919 }
920 if (opt->color) {
921 regmatch_t match;
922 enum grep_context ctx = GREP_CONTEXT_BODY;
923 int ch = *eol;
924 int eflags = 0;
925
926 if (sign == ':')
927 line_color = opt->color_selected;
928 else if (sign == '-')
929 line_color = opt->color_context;
930 else if (sign == '=')
931 line_color = opt->color_function;
932 *eol = '\0';
933 while (next_match(opt, bol, eol, ctx, &match, eflags)) {
934 if (match.rm_so == match.rm_eo)
935 break;
936
937 output_color(opt, bol, match.rm_so, line_color);
938 output_color(opt, bol + match.rm_so,
939 match.rm_eo - match.rm_so,
940 opt->color_match);
941 bol += match.rm_eo;
942 rest -= match.rm_eo;
943 eflags = REG_NOTBOL;
944 }
945 *eol = ch;
946 }
947 output_color(opt, bol, rest, line_color);
948 opt->output(opt, "\n", 1);
949}
950
951#ifndef NO_PTHREADS
952int grep_use_locks;
953
954/*
955 * This lock protects access to the gitattributes machinery, which is
956 * not thread-safe.
957 */
958pthread_mutex_t grep_attr_mutex;
959
960static inline void grep_attr_lock(void)
961{
962 if (grep_use_locks)
963 pthread_mutex_lock(&grep_attr_mutex);
964}
965
966static inline void grep_attr_unlock(void)
967{
968 if (grep_use_locks)
969 pthread_mutex_unlock(&grep_attr_mutex);
970}
971
972/*
973 * Same as git_attr_mutex, but protecting the thread-unsafe object db access.
974 */
975pthread_mutex_t grep_read_mutex;
976
977#else
978#define grep_attr_lock()
979#define grep_attr_unlock()
980#endif
981
982static int match_funcname(struct grep_opt *opt, struct grep_source *gs, char *bol, char *eol)
983{
984 xdemitconf_t *xecfg = opt->priv;
985 if (xecfg && !xecfg->find_func) {
986 grep_source_load_driver(gs);
987 if (gs->driver->funcname.pattern) {
988 const struct userdiff_funcname *pe = &gs->driver->funcname;
989 xdiff_set_find_func(xecfg, pe->pattern, pe->cflags);
990 } else {
991 xecfg = opt->priv = NULL;
992 }
993 }
994
995 if (xecfg) {
996 char buf[1];
997 return xecfg->find_func(bol, eol - bol, buf, 1,
998 xecfg->find_func_priv) >= 0;
999 }
1000
1001 if (bol == eol)
1002 return 0;
1003 if (isalpha(*bol) || *bol == '_' || *bol == '$')
1004 return 1;
1005 return 0;
1006}
1007
1008static void show_funcname_line(struct grep_opt *opt, struct grep_source *gs,
1009 char *bol, unsigned lno)
1010{
1011 while (bol > gs->buf) {
1012 char *eol = --bol;
1013
1014 while (bol > gs->buf && bol[-1] != '\n')
1015 bol--;
1016 lno--;
1017
1018 if (lno <= opt->last_shown)
1019 break;
1020
1021 if (match_funcname(opt, gs, bol, eol)) {
1022 show_line(opt, bol, eol, gs->name, lno, '=');
1023 break;
1024 }
1025 }
1026}
1027
1028static void show_pre_context(struct grep_opt *opt, struct grep_source *gs,
1029 char *bol, char *end, unsigned lno)
1030{
1031 unsigned cur = lno, from = 1, funcname_lno = 0;
1032 int funcname_needed = !!opt->funcname;
1033
1034 if (opt->funcbody && !match_funcname(opt, gs, bol, end))
1035 funcname_needed = 2;
1036
1037 if (opt->pre_context < lno)
1038 from = lno - opt->pre_context;
1039 if (from <= opt->last_shown)
1040 from = opt->last_shown + 1;
1041
1042 /* Rewind. */
1043 while (bol > gs->buf &&
1044 cur > (funcname_needed == 2 ? opt->last_shown + 1 : from)) {
1045 char *eol = --bol;
1046
1047 while (bol > gs->buf && bol[-1] != '\n')
1048 bol--;
1049 cur--;
1050 if (funcname_needed && match_funcname(opt, gs, bol, eol)) {
1051 funcname_lno = cur;
1052 funcname_needed = 0;
1053 }
1054 }
1055
1056 /* We need to look even further back to find a function signature. */
1057 if (opt->funcname && funcname_needed)
1058 show_funcname_line(opt, gs, bol, cur);
1059
1060 /* Back forward. */
1061 while (cur < lno) {
1062 char *eol = bol, sign = (cur == funcname_lno) ? '=' : '-';
1063
1064 while (*eol != '\n')
1065 eol++;
1066 show_line(opt, bol, eol, gs->name, cur, sign);
1067 bol = eol + 1;
1068 cur++;
1069 }
1070}
1071
1072static int should_lookahead(struct grep_opt *opt)
1073{
1074 struct grep_pat *p;
1075
1076 if (opt->extended)
1077 return 0; /* punt for too complex stuff */
1078 if (opt->invert)
1079 return 0;
1080 for (p = opt->pattern_list; p; p = p->next) {
1081 if (p->token != GREP_PATTERN)
1082 return 0; /* punt for "header only" and stuff */
1083 }
1084 return 1;
1085}
1086
1087static int look_ahead(struct grep_opt *opt,
1088 unsigned long *left_p,
1089 unsigned *lno_p,
1090 char **bol_p)
1091{
1092 unsigned lno = *lno_p;
1093 char *bol = *bol_p;
1094 struct grep_pat *p;
1095 char *sp, *last_bol;
1096 regoff_t earliest = -1;
1097
1098 for (p = opt->pattern_list; p; p = p->next) {
1099 int hit;
1100 regmatch_t m;
1101
1102 hit = patmatch(p, bol, bol + *left_p, &m, 0);
1103 if (!hit || m.rm_so < 0 || m.rm_eo < 0)
1104 continue;
1105 if (earliest < 0 || m.rm_so < earliest)
1106 earliest = m.rm_so;
1107 }
1108
1109 if (earliest < 0) {
1110 *bol_p = bol + *left_p;
1111 *left_p = 0;
1112 return 1;
1113 }
1114 for (sp = bol + earliest; bol < sp && sp[-1] != '\n'; sp--)
1115 ; /* find the beginning of the line */
1116 last_bol = sp;
1117
1118 for (sp = bol; sp < last_bol; sp++) {
1119 if (*sp == '\n')
1120 lno++;
1121 }
1122 *left_p -= last_bol - bol;
1123 *bol_p = last_bol;
1124 *lno_p = lno;
1125 return 0;
1126}
1127
1128static void std_output(struct grep_opt *opt, const void *buf, size_t size)
1129{
1130 fwrite(buf, size, 1, stdout);
1131}
1132
1133static int grep_source_1(struct grep_opt *opt, struct grep_source *gs, int collect_hits)
1134{
1135 char *bol;
1136 unsigned long left;
1137 unsigned lno = 1;
1138 unsigned last_hit = 0;
1139 int binary_match_only = 0;
1140 unsigned count = 0;
1141 int try_lookahead = 0;
1142 int show_function = 0;
1143 enum grep_context ctx = GREP_CONTEXT_HEAD;
1144 xdemitconf_t xecfg;
1145
1146 if (!opt->output)
1147 opt->output = std_output;
1148
1149 if (opt->pre_context || opt->post_context || opt->file_break ||
1150 opt->funcbody) {
1151 /* Show hunk marks, except for the first file. */
1152 if (opt->last_shown)
1153 opt->show_hunk_mark = 1;
1154 /*
1155 * If we're using threads then we can't easily identify
1156 * the first file. Always put hunk marks in that case
1157 * and skip the very first one later in work_done().
1158 */
1159 if (opt->output != std_output)
1160 opt->show_hunk_mark = 1;
1161 }
1162 opt->last_shown = 0;
1163
1164 switch (opt->binary) {
1165 case GREP_BINARY_DEFAULT:
1166 if (grep_source_is_binary(gs))
1167 binary_match_only = 1;
1168 break;
1169 case GREP_BINARY_NOMATCH:
1170 if (grep_source_is_binary(gs))
1171 return 0; /* Assume unmatch */
1172 break;
1173 case GREP_BINARY_TEXT:
1174 break;
1175 default:
1176 die("bug: unknown binary handling mode");
1177 }
1178
1179 memset(&xecfg, 0, sizeof(xecfg));
1180 opt->priv = &xecfg;
1181
1182 try_lookahead = should_lookahead(opt);
1183
1184 if (grep_source_load(gs) < 0)
1185 return 0;
1186
1187 bol = gs->buf;
1188 left = gs->size;
1189 while (left) {
1190 char *eol, ch;
1191 int hit;
1192
1193 /*
1194 * look_ahead() skips quickly to the line that possibly
1195 * has the next hit; don't call it if we need to do
1196 * something more than just skipping the current line
1197 * in response to an unmatch for the current line. E.g.
1198 * inside a post-context window, we will show the current
1199 * line as a context around the previous hit when it
1200 * doesn't hit.
1201 */
1202 if (try_lookahead
1203 && !(last_hit
1204 && (show_function ||
1205 lno <= last_hit + opt->post_context))
1206 && look_ahead(opt, &left, &lno, &bol))
1207 break;
1208 eol = end_of_line(bol, &left);
1209 ch = *eol;
1210 *eol = 0;
1211
1212 if ((ctx == GREP_CONTEXT_HEAD) && (eol == bol))
1213 ctx = GREP_CONTEXT_BODY;
1214
1215 hit = match_line(opt, bol, eol, ctx, collect_hits);
1216 *eol = ch;
1217
1218 if (collect_hits)
1219 goto next_line;
1220
1221 /* "grep -v -e foo -e bla" should list lines
1222 * that do not have either, so inversion should
1223 * be done outside.
1224 */
1225 if (opt->invert)
1226 hit = !hit;
1227 if (opt->unmatch_name_only) {
1228 if (hit)
1229 return 0;
1230 goto next_line;
1231 }
1232 if (hit) {
1233 count++;
1234 if (opt->status_only)
1235 return 1;
1236 if (opt->name_only) {
1237 show_name(opt, gs->name);
1238 return 1;
1239 }
1240 if (opt->count)
1241 goto next_line;
1242 if (binary_match_only) {
1243 opt->output(opt, "Binary file ", 12);
1244 output_color(opt, gs->name, strlen(gs->name),
1245 opt->color_filename);
1246 opt->output(opt, " matches\n", 9);
1247 return 1;
1248 }
1249 /* Hit at this line. If we haven't shown the
1250 * pre-context lines, we would need to show them.
1251 */
1252 if (opt->pre_context || opt->funcbody)
1253 show_pre_context(opt, gs, bol, eol, lno);
1254 else if (opt->funcname)
1255 show_funcname_line(opt, gs, bol, lno);
1256 show_line(opt, bol, eol, gs->name, lno, ':');
1257 last_hit = lno;
1258 if (opt->funcbody)
1259 show_function = 1;
1260 goto next_line;
1261 }
1262 if (show_function && match_funcname(opt, gs, bol, eol))
1263 show_function = 0;
1264 if (show_function ||
1265 (last_hit && lno <= last_hit + opt->post_context)) {
1266 /* If the last hit is within the post context,
1267 * we need to show this line.
1268 */
1269 show_line(opt, bol, eol, gs->name, lno, '-');
1270 }
1271
1272 next_line:
1273 bol = eol + 1;
1274 if (!left)
1275 break;
1276 left--;
1277 lno++;
1278 }
1279
1280 if (collect_hits)
1281 return 0;
1282
1283 if (opt->status_only)
1284 return 0;
1285 if (opt->unmatch_name_only) {
1286 /* We did not see any hit, so we want to show this */
1287 show_name(opt, gs->name);
1288 return 1;
1289 }
1290
1291 xdiff_clear_find_func(&xecfg);
1292 opt->priv = NULL;
1293
1294 /* NEEDSWORK:
1295 * The real "grep -c foo *.c" gives many "bar.c:0" lines,
1296 * which feels mostly useless but sometimes useful. Maybe
1297 * make it another option? For now suppress them.
1298 */
1299 if (opt->count && count) {
1300 char buf[32];
1301 output_color(opt, gs->name, strlen(gs->name), opt->color_filename);
1302 output_sep(opt, ':');
1303 snprintf(buf, sizeof(buf), "%u\n", count);
1304 opt->output(opt, buf, strlen(buf));
1305 return 1;
1306 }
1307 return !!last_hit;
1308}
1309
1310static void clr_hit_marker(struct grep_expr *x)
1311{
1312 /* All-hit markers are meaningful only at the very top level
1313 * OR node.
1314 */
1315 while (1) {
1316 x->hit = 0;
1317 if (x->node != GREP_NODE_OR)
1318 return;
1319 x->u.binary.left->hit = 0;
1320 x = x->u.binary.right;
1321 }
1322}
1323
1324static int chk_hit_marker(struct grep_expr *x)
1325{
1326 /* Top level nodes have hit markers. See if they all are hits */
1327 while (1) {
1328 if (x->node != GREP_NODE_OR)
1329 return x->hit;
1330 if (!x->u.binary.left->hit)
1331 return 0;
1332 x = x->u.binary.right;
1333 }
1334}
1335
1336int grep_source(struct grep_opt *opt, struct grep_source *gs)
1337{
1338 /*
1339 * we do not have to do the two-pass grep when we do not check
1340 * buffer-wide "all-match".
1341 */
1342 if (!opt->all_match)
1343 return grep_source_1(opt, gs, 0);
1344
1345 /* Otherwise the toplevel "or" terms hit a bit differently.
1346 * We first clear hit markers from them.
1347 */
1348 clr_hit_marker(opt->pattern_expression);
1349 grep_source_1(opt, gs, 1);
1350
1351 if (!chk_hit_marker(opt->pattern_expression))
1352 return 0;
1353
1354 return grep_source_1(opt, gs, 0);
1355}
1356
1357int grep_buffer(struct grep_opt *opt, char *buf, unsigned long size)
1358{
1359 struct grep_source gs;
1360 int r;
1361
1362 grep_source_init(&gs, GREP_SOURCE_BUF, NULL, NULL);
1363 gs.buf = buf;
1364 gs.size = size;
1365
1366 r = grep_source(opt, &gs);
1367
1368 grep_source_clear(&gs);
1369 return r;
1370}
1371
1372void grep_source_init(struct grep_source *gs, enum grep_source_type type,
1373 const char *name, const void *identifier)
1374{
1375 gs->type = type;
1376 gs->name = name ? xstrdup(name) : NULL;
1377 gs->buf = NULL;
1378 gs->size = 0;
1379 gs->driver = NULL;
1380
1381 switch (type) {
1382 case GREP_SOURCE_FILE:
1383 gs->identifier = xstrdup(identifier);
1384 break;
1385 case GREP_SOURCE_SHA1:
1386 gs->identifier = xmalloc(20);
1387 memcpy(gs->identifier, identifier, 20);
1388 break;
1389 case GREP_SOURCE_BUF:
1390 gs->identifier = NULL;
1391 }
1392}
1393
1394void grep_source_clear(struct grep_source *gs)
1395{
1396 free(gs->name);
1397 gs->name = NULL;
1398 free(gs->identifier);
1399 gs->identifier = NULL;
1400 grep_source_clear_data(gs);
1401}
1402
1403void grep_source_clear_data(struct grep_source *gs)
1404{
1405 switch (gs->type) {
1406 case GREP_SOURCE_FILE:
1407 case GREP_SOURCE_SHA1:
1408 free(gs->buf);
1409 gs->buf = NULL;
1410 gs->size = 0;
1411 break;
1412 case GREP_SOURCE_BUF:
1413 /* leave user-provided buf intact */
1414 break;
1415 }
1416}
1417
1418static int grep_source_load_sha1(struct grep_source *gs)
1419{
1420 enum object_type type;
1421
1422 grep_read_lock();
1423 gs->buf = read_sha1_file(gs->identifier, &type, &gs->size);
1424 grep_read_unlock();
1425
1426 if (!gs->buf)
1427 return error(_("'%s': unable to read %s"),
1428 gs->name,
1429 sha1_to_hex(gs->identifier));
1430 return 0;
1431}
1432
1433static int grep_source_load_file(struct grep_source *gs)
1434{
1435 const char *filename = gs->identifier;
1436 struct stat st;
1437 char *data;
1438 size_t size;
1439 int i;
1440
1441 if (lstat(filename, &st) < 0) {
1442 err_ret:
1443 if (errno != ENOENT)
1444 error(_("'%s': %s"), filename, strerror(errno));
1445 return -1;
1446 }
1447 if (!S_ISREG(st.st_mode))
1448 return -1;
1449 size = xsize_t(st.st_size);
1450 i = open(filename, O_RDONLY);
1451 if (i < 0)
1452 goto err_ret;
1453 data = xmalloc(size + 1);
1454 if (st.st_size != read_in_full(i, data, size)) {
1455 error(_("'%s': short read %s"), filename, strerror(errno));
1456 close(i);
1457 free(data);
1458 return -1;
1459 }
1460 close(i);
1461 data[size] = 0;
1462
1463 gs->buf = data;
1464 gs->size = size;
1465 return 0;
1466}
1467
1468int grep_source_load(struct grep_source *gs)
1469{
1470 if (gs->buf)
1471 return 0;
1472
1473 switch (gs->type) {
1474 case GREP_SOURCE_FILE:
1475 return grep_source_load_file(gs);
1476 case GREP_SOURCE_SHA1:
1477 return grep_source_load_sha1(gs);
1478 case GREP_SOURCE_BUF:
1479 return gs->buf ? 0 : -1;
1480 }
1481 die("BUG: invalid grep_source type");
1482}
1483
1484void grep_source_load_driver(struct grep_source *gs)
1485{
1486 if (gs->driver)
1487 return;
1488
1489 grep_attr_lock();
1490 gs->driver = userdiff_find_by_path(gs->name);
1491 if (!gs->driver)
1492 gs->driver = userdiff_find_by_name("default");
1493 grep_attr_unlock();
1494}
1495
1496int grep_source_is_binary(struct grep_source *gs)
1497{
1498 grep_source_load_driver(gs);
1499 if (gs->driver->binary != -1)
1500 return gs->driver->binary;
1501
1502 if (!grep_source_load(gs))
1503 return buffer_is_binary(gs->buf, gs->size);
1504
1505 return 0;
1506}