userdiff style: declare patterns with consistent style
[git] / grep.c
1 #include "cache.h"
2 #include "config.h"
3 #include "grep.h"
4 #include "object-store.h"
5 #include "userdiff.h"
6 #include "xdiff-interface.h"
7 #include "diff.h"
8 #include "diffcore.h"
9 #include "commit.h"
10 #include "quote.h"
11 #include "help.h"
12
13 static int grep_source_load(struct grep_source *gs);
14 static int grep_source_is_binary(struct grep_source *gs,
15                                  struct index_state *istate);
16
17 static void std_output(struct grep_opt *opt, const void *buf, size_t size)
18 {
19         fwrite(buf, size, 1, stdout);
20 }
21
22 static struct grep_opt grep_defaults = {
23         .relative = 1,
24         .pathname = 1,
25         .max_depth = -1,
26         .pattern_type_option = GREP_PATTERN_TYPE_UNSPECIFIED,
27         .colors = {
28                 [GREP_COLOR_CONTEXT] = "",
29                 [GREP_COLOR_FILENAME] = "",
30                 [GREP_COLOR_FUNCTION] = "",
31                 [GREP_COLOR_LINENO] = "",
32                 [GREP_COLOR_COLUMNNO] = "",
33                 [GREP_COLOR_MATCH_CONTEXT] = GIT_COLOR_BOLD_RED,
34                 [GREP_COLOR_MATCH_SELECTED] = GIT_COLOR_BOLD_RED,
35                 [GREP_COLOR_SELECTED] = "",
36                 [GREP_COLOR_SEP] = GIT_COLOR_CYAN,
37         },
38         .only_matching = 0,
39         .color = -1,
40         .output = std_output,
41 };
42
43 static const char *color_grep_slots[] = {
44         [GREP_COLOR_CONTEXT]        = "context",
45         [GREP_COLOR_FILENAME]       = "filename",
46         [GREP_COLOR_FUNCTION]       = "function",
47         [GREP_COLOR_LINENO]         = "lineNumber",
48         [GREP_COLOR_COLUMNNO]       = "column",
49         [GREP_COLOR_MATCH_CONTEXT]  = "matchContext",
50         [GREP_COLOR_MATCH_SELECTED] = "matchSelected",
51         [GREP_COLOR_SELECTED]       = "selected",
52         [GREP_COLOR_SEP]            = "separator",
53 };
54
55 static int parse_pattern_type_arg(const char *opt, const char *arg)
56 {
57         if (!strcmp(arg, "default"))
58                 return GREP_PATTERN_TYPE_UNSPECIFIED;
59         else if (!strcmp(arg, "basic"))
60                 return GREP_PATTERN_TYPE_BRE;
61         else if (!strcmp(arg, "extended"))
62                 return GREP_PATTERN_TYPE_ERE;
63         else if (!strcmp(arg, "fixed"))
64                 return GREP_PATTERN_TYPE_FIXED;
65         else if (!strcmp(arg, "perl"))
66                 return GREP_PATTERN_TYPE_PCRE;
67         die("bad %s argument: %s", opt, arg);
68 }
69
70 define_list_config_array_extra(color_grep_slots, {"match"});
71
72 /*
73  * Read the configuration file once and store it in
74  * the grep_defaults template.
75  */
76 int grep_config(const char *var, const char *value, void *cb)
77 {
78         struct grep_opt *opt = &grep_defaults;
79         const char *slot;
80
81         if (userdiff_config(var, value) < 0)
82                 return -1;
83
84         /*
85          * The instance of grep_opt that we set up here is copied by
86          * grep_init() to be used by each individual invocation.
87          * When populating a new field of this structure here, be
88          * sure to think about ownership -- e.g., you might need to
89          * override the shallow copy in grep_init() with a deep copy.
90          */
91
92         if (!strcmp(var, "grep.extendedregexp")) {
93                 opt->extended_regexp_option = git_config_bool(var, value);
94                 return 0;
95         }
96
97         if (!strcmp(var, "grep.patterntype")) {
98                 opt->pattern_type_option = parse_pattern_type_arg(var, value);
99                 return 0;
100         }
101
102         if (!strcmp(var, "grep.linenumber")) {
103                 opt->linenum = git_config_bool(var, value);
104                 return 0;
105         }
106         if (!strcmp(var, "grep.column")) {
107                 opt->columnnum = git_config_bool(var, value);
108                 return 0;
109         }
110
111         if (!strcmp(var, "grep.fullname")) {
112                 opt->relative = !git_config_bool(var, value);
113                 return 0;
114         }
115
116         if (!strcmp(var, "color.grep"))
117                 opt->color = git_config_colorbool(var, value);
118         if (!strcmp(var, "color.grep.match")) {
119                 if (grep_config("color.grep.matchcontext", value, cb) < 0)
120                         return -1;
121                 if (grep_config("color.grep.matchselected", value, cb) < 0)
122                         return -1;
123         } else if (skip_prefix(var, "color.grep.", &slot)) {
124                 int i = LOOKUP_CONFIG(color_grep_slots, slot);
125                 char *color;
126
127                 if (i < 0)
128                         return -1;
129                 color = opt->colors[i];
130                 if (!value)
131                         return config_error_nonbool(var);
132                 return color_parse(value, color);
133         }
134         return 0;
135 }
136
137 /*
138  * Initialize one instance of grep_opt and copy the
139  * default values from the template we read the configuration
140  * information in an earlier call to git_config(grep_config).
141  */
142 void grep_init(struct grep_opt *opt, struct repository *repo, const char *prefix)
143 {
144         *opt = grep_defaults;
145
146         opt->repo = repo;
147         opt->prefix = prefix;
148         opt->prefix_length = (prefix && *prefix) ? strlen(prefix) : 0;
149         opt->pattern_tail = &opt->pattern_list;
150         opt->header_tail = &opt->header_list;
151 }
152
153 static void grep_set_pattern_type_option(enum grep_pattern_type pattern_type, struct grep_opt *opt)
154 {
155         /*
156          * When committing to the pattern type by setting the relevant
157          * fields in grep_opt it's generally not necessary to zero out
158          * the fields we're not choosing, since they won't have been
159          * set by anything. The extended_regexp_option field is the
160          * only exception to this.
161          *
162          * This is because in the process of parsing grep.patternType
163          * & grep.extendedRegexp we set opt->pattern_type_option and
164          * opt->extended_regexp_option, respectively. We then
165          * internally use opt->extended_regexp_option to see if we're
166          * compiling an ERE. It must be unset if that's not actually
167          * the case.
168          */
169         if (pattern_type != GREP_PATTERN_TYPE_ERE &&
170             opt->extended_regexp_option)
171                 opt->extended_regexp_option = 0;
172
173         switch (pattern_type) {
174         case GREP_PATTERN_TYPE_UNSPECIFIED:
175                 /* fall through */
176
177         case GREP_PATTERN_TYPE_BRE:
178                 break;
179
180         case GREP_PATTERN_TYPE_ERE:
181                 opt->extended_regexp_option = 1;
182                 break;
183
184         case GREP_PATTERN_TYPE_FIXED:
185                 opt->fixed = 1;
186                 break;
187
188         case GREP_PATTERN_TYPE_PCRE:
189                 opt->pcre2 = 1;
190                 break;
191         }
192 }
193
194 void grep_commit_pattern_type(enum grep_pattern_type pattern_type, struct grep_opt *opt)
195 {
196         if (pattern_type != GREP_PATTERN_TYPE_UNSPECIFIED)
197                 grep_set_pattern_type_option(pattern_type, opt);
198         else if (opt->pattern_type_option != GREP_PATTERN_TYPE_UNSPECIFIED)
199                 grep_set_pattern_type_option(opt->pattern_type_option, opt);
200         else if (opt->extended_regexp_option)
201                 /*
202                  * This branch *must* happen after setting from the
203                  * opt->pattern_type_option above, we don't want
204                  * grep.extendedRegexp to override grep.patternType!
205                  */
206                 grep_set_pattern_type_option(GREP_PATTERN_TYPE_ERE, opt);
207 }
208
209 static struct grep_pat *create_grep_pat(const char *pat, size_t patlen,
210                                         const char *origin, int no,
211                                         enum grep_pat_token t,
212                                         enum grep_header_field field)
213 {
214         struct grep_pat *p = xcalloc(1, sizeof(*p));
215         p->pattern = xmemdupz(pat, patlen);
216         p->patternlen = patlen;
217         p->origin = origin;
218         p->no = no;
219         p->token = t;
220         p->field = field;
221         return p;
222 }
223
224 static void do_append_grep_pat(struct grep_pat ***tail, struct grep_pat *p)
225 {
226         **tail = p;
227         *tail = &p->next;
228         p->next = NULL;
229
230         switch (p->token) {
231         case GREP_PATTERN: /* atom */
232         case GREP_PATTERN_HEAD:
233         case GREP_PATTERN_BODY:
234                 for (;;) {
235                         struct grep_pat *new_pat;
236                         size_t len = 0;
237                         char *cp = p->pattern + p->patternlen, *nl = NULL;
238                         while (++len <= p->patternlen) {
239                                 if (*(--cp) == '\n') {
240                                         nl = cp;
241                                         break;
242                                 }
243                         }
244                         if (!nl)
245                                 break;
246                         new_pat = create_grep_pat(nl + 1, len - 1, p->origin,
247                                                   p->no, p->token, p->field);
248                         new_pat->next = p->next;
249                         if (!p->next)
250                                 *tail = &new_pat->next;
251                         p->next = new_pat;
252                         *nl = '\0';
253                         p->patternlen -= len;
254                 }
255                 break;
256         default:
257                 break;
258         }
259 }
260
261 void append_header_grep_pattern(struct grep_opt *opt,
262                                 enum grep_header_field field, const char *pat)
263 {
264         struct grep_pat *p = create_grep_pat(pat, strlen(pat), "header", 0,
265                                              GREP_PATTERN_HEAD, field);
266         if (field == GREP_HEADER_REFLOG)
267                 opt->use_reflog_filter = 1;
268         do_append_grep_pat(&opt->header_tail, p);
269 }
270
271 void append_grep_pattern(struct grep_opt *opt, const char *pat,
272                          const char *origin, int no, enum grep_pat_token t)
273 {
274         append_grep_pat(opt, pat, strlen(pat), origin, no, t);
275 }
276
277 void append_grep_pat(struct grep_opt *opt, const char *pat, size_t patlen,
278                      const char *origin, int no, enum grep_pat_token t)
279 {
280         struct grep_pat *p = create_grep_pat(pat, patlen, origin, no, t, 0);
281         do_append_grep_pat(&opt->pattern_tail, p);
282 }
283
284 struct grep_opt *grep_opt_dup(const struct grep_opt *opt)
285 {
286         struct grep_pat *pat;
287         struct grep_opt *ret = xmalloc(sizeof(struct grep_opt));
288         *ret = *opt;
289
290         ret->pattern_list = NULL;
291         ret->pattern_tail = &ret->pattern_list;
292
293         for(pat = opt->pattern_list; pat != NULL; pat = pat->next)
294         {
295                 if(pat->token == GREP_PATTERN_HEAD)
296                         append_header_grep_pattern(ret, pat->field,
297                                                    pat->pattern);
298                 else
299                         append_grep_pat(ret, pat->pattern, pat->patternlen,
300                                         pat->origin, pat->no, pat->token);
301         }
302
303         return ret;
304 }
305
306 static NORETURN void compile_regexp_failed(const struct grep_pat *p,
307                 const char *error)
308 {
309         char where[1024];
310
311         if (p->no)
312                 xsnprintf(where, sizeof(where), "In '%s' at %d, ", p->origin, p->no);
313         else if (p->origin)
314                 xsnprintf(where, sizeof(where), "%s, ", p->origin);
315         else
316                 where[0] = 0;
317
318         die("%s'%s': %s", where, p->pattern, error);
319 }
320
321 static int is_fixed(const char *s, size_t len)
322 {
323         size_t i;
324
325         for (i = 0; i < len; i++) {
326                 if (is_regex_special(s[i]))
327                         return 0;
328         }
329
330         return 1;
331 }
332
333 #ifdef USE_LIBPCRE2
334 #define GREP_PCRE2_DEBUG_MALLOC 0
335
336 static void *pcre2_malloc(PCRE2_SIZE size, MAYBE_UNUSED void *memory_data)
337 {
338         void *pointer = malloc(size);
339 #if GREP_PCRE2_DEBUG_MALLOC
340         static int count = 1;
341         fprintf(stderr, "PCRE2:%p -> #%02d: alloc(%lu)\n", pointer, count++, size);
342 #endif
343         return pointer;
344 }
345
346 static void pcre2_free(void *pointer, MAYBE_UNUSED void *memory_data)
347 {
348 #if GREP_PCRE2_DEBUG_MALLOC
349         static int count = 1;
350         if (pointer)
351                 fprintf(stderr, "PCRE2:%p -> #%02d: free()\n", pointer, count++);
352 #endif
353         free(pointer);
354 }
355
356 static void compile_pcre2_pattern(struct grep_pat *p, const struct grep_opt *opt)
357 {
358         int error;
359         PCRE2_UCHAR errbuf[256];
360         PCRE2_SIZE erroffset;
361         int options = PCRE2_MULTILINE;
362         int jitret;
363         int patinforet;
364         size_t jitsizearg;
365
366         /*
367          * Call pcre2_general_context_create() before calling any
368          * other pcre2_*(). It sets up our malloc()/free() functions
369          * with which everything else is allocated.
370          */
371         p->pcre2_general_context = pcre2_general_context_create(
372                 pcre2_malloc, pcre2_free, NULL);
373         if (!p->pcre2_general_context)
374                 die("Couldn't allocate PCRE2 general context");
375
376         if (opt->ignore_case) {
377                 if (!opt->ignore_locale && has_non_ascii(p->pattern)) {
378                         p->pcre2_tables = pcre2_maketables(p->pcre2_general_context);
379                         p->pcre2_compile_context = pcre2_compile_context_create(p->pcre2_general_context);
380                         pcre2_set_character_tables(p->pcre2_compile_context,
381                                                         p->pcre2_tables);
382                 }
383                 options |= PCRE2_CASELESS;
384         }
385         if (!opt->ignore_locale && is_utf8_locale() && has_non_ascii(p->pattern) &&
386             !(!opt->ignore_case && (p->fixed || p->is_fixed)))
387                 options |= (PCRE2_UTF | PCRE2_MATCH_INVALID_UTF);
388
389 #ifdef GIT_PCRE2_VERSION_10_36_OR_HIGHER
390         /* Work around https://bugs.exim.org/show_bug.cgi?id=2642 fixed in 10.36 */
391         if (PCRE2_MATCH_INVALID_UTF && options & (PCRE2_UTF | PCRE2_CASELESS))
392                 options |= PCRE2_NO_START_OPTIMIZE;
393 #endif
394
395         p->pcre2_pattern = pcre2_compile((PCRE2_SPTR)p->pattern,
396                                          p->patternlen, options, &error, &erroffset,
397                                          p->pcre2_compile_context);
398
399         if (p->pcre2_pattern) {
400                 p->pcre2_match_data = pcre2_match_data_create_from_pattern(p->pcre2_pattern, p->pcre2_general_context);
401                 if (!p->pcre2_match_data)
402                         die("Couldn't allocate PCRE2 match data");
403         } else {
404                 pcre2_get_error_message(error, errbuf, sizeof(errbuf));
405                 compile_regexp_failed(p, (const char *)&errbuf);
406         }
407
408         pcre2_config(PCRE2_CONFIG_JIT, &p->pcre2_jit_on);
409         if (p->pcre2_jit_on) {
410                 jitret = pcre2_jit_compile(p->pcre2_pattern, PCRE2_JIT_COMPLETE);
411                 if (jitret)
412                         die("Couldn't JIT the PCRE2 pattern '%s', got '%d'\n", p->pattern, jitret);
413
414                 /*
415                  * The pcre2_config(PCRE2_CONFIG_JIT, ...) call just
416                  * tells us whether the library itself supports JIT,
417                  * but to see whether we're going to be actually using
418                  * JIT we need to extract PCRE2_INFO_JITSIZE from the
419                  * pattern *after* we do pcre2_jit_compile() above.
420                  *
421                  * This is because if the pattern contains the
422                  * (*NO_JIT) verb (see pcre2syntax(3))
423                  * pcre2_jit_compile() will exit early with 0. If we
424                  * then proceed to call pcre2_jit_match() further down
425                  * the line instead of pcre2_match() we'll either
426                  * segfault (pre PCRE 10.31) or run into a fatal error
427                  * (post PCRE2 10.31)
428                  */
429                 patinforet = pcre2_pattern_info(p->pcre2_pattern, PCRE2_INFO_JITSIZE, &jitsizearg);
430                 if (patinforet)
431                         BUG("pcre2_pattern_info() failed: %d", patinforet);
432                 if (jitsizearg == 0) {
433                         p->pcre2_jit_on = 0;
434                         return;
435                 }
436         }
437 }
438
439 static int pcre2match(struct grep_pat *p, const char *line, const char *eol,
440                 regmatch_t *match, int eflags)
441 {
442         int ret, flags = 0;
443         PCRE2_SIZE *ovector;
444         PCRE2_UCHAR errbuf[256];
445
446         if (eflags & REG_NOTBOL)
447                 flags |= PCRE2_NOTBOL;
448
449         if (p->pcre2_jit_on)
450                 ret = pcre2_jit_match(p->pcre2_pattern, (unsigned char *)line,
451                                       eol - line, 0, flags, p->pcre2_match_data,
452                                       NULL);
453         else
454                 ret = pcre2_match(p->pcre2_pattern, (unsigned char *)line,
455                                   eol - line, 0, flags, p->pcre2_match_data,
456                                   NULL);
457
458         if (ret < 0 && ret != PCRE2_ERROR_NOMATCH) {
459                 pcre2_get_error_message(ret, errbuf, sizeof(errbuf));
460                 die("%s failed with error code %d: %s",
461                     (p->pcre2_jit_on ? "pcre2_jit_match" : "pcre2_match"), ret,
462                     errbuf);
463         }
464         if (ret > 0) {
465                 ovector = pcre2_get_ovector_pointer(p->pcre2_match_data);
466                 ret = 0;
467                 match->rm_so = (int)ovector[0];
468                 match->rm_eo = (int)ovector[1];
469         }
470
471         return ret;
472 }
473
474 static void free_pcre2_pattern(struct grep_pat *p)
475 {
476         pcre2_compile_context_free(p->pcre2_compile_context);
477         pcre2_code_free(p->pcre2_pattern);
478         pcre2_match_data_free(p->pcre2_match_data);
479 #ifdef GIT_PCRE2_VERSION_10_34_OR_HIGHER
480         pcre2_maketables_free(p->pcre2_general_context, p->pcre2_tables);
481 #else
482         free((void *)p->pcre2_tables);
483 #endif
484         pcre2_general_context_free(p->pcre2_general_context);
485 }
486 #else /* !USE_LIBPCRE2 */
487 static void compile_pcre2_pattern(struct grep_pat *p, const struct grep_opt *opt)
488 {
489         die("cannot use Perl-compatible regexes when not compiled with USE_LIBPCRE");
490 }
491
492 static int pcre2match(struct grep_pat *p, const char *line, const char *eol,
493                 regmatch_t *match, int eflags)
494 {
495         return 1;
496 }
497
498 static void free_pcre2_pattern(struct grep_pat *p)
499 {
500 }
501
502 static void compile_fixed_regexp(struct grep_pat *p, struct grep_opt *opt)
503 {
504         struct strbuf sb = STRBUF_INIT;
505         int err;
506         int regflags = 0;
507
508         basic_regex_quote_buf(&sb, p->pattern);
509         if (opt->ignore_case)
510                 regflags |= REG_ICASE;
511         err = regcomp(&p->regexp, sb.buf, regflags);
512         strbuf_release(&sb);
513         if (err) {
514                 char errbuf[1024];
515                 regerror(err, &p->regexp, errbuf, sizeof(errbuf));
516                 compile_regexp_failed(p, errbuf);
517         }
518 }
519 #endif /* !USE_LIBPCRE2 */
520
521 static void compile_regexp(struct grep_pat *p, struct grep_opt *opt)
522 {
523         int err;
524         int regflags = REG_NEWLINE;
525
526         p->word_regexp = opt->word_regexp;
527         p->ignore_case = opt->ignore_case;
528         p->fixed = opt->fixed;
529
530         if (memchr(p->pattern, 0, p->patternlen) && !opt->pcre2)
531                 die(_("given pattern contains NULL byte (via -f <file>). This is only supported with -P under PCRE v2"));
532
533         p->is_fixed = is_fixed(p->pattern, p->patternlen);
534 #ifdef USE_LIBPCRE2
535        if (!p->fixed && !p->is_fixed) {
536                const char *no_jit = "(*NO_JIT)";
537                const int no_jit_len = strlen(no_jit);
538                if (starts_with(p->pattern, no_jit) &&
539                    is_fixed(p->pattern + no_jit_len,
540                             p->patternlen - no_jit_len))
541                        p->is_fixed = 1;
542        }
543 #endif
544         if (p->fixed || p->is_fixed) {
545 #ifdef USE_LIBPCRE2
546                 if (p->is_fixed) {
547                         compile_pcre2_pattern(p, opt);
548                 } else {
549                         /*
550                          * E.g. t7811-grep-open.sh relies on the
551                          * pattern being restored.
552                          */
553                         char *old_pattern = p->pattern;
554                         size_t old_patternlen = p->patternlen;
555                         struct strbuf sb = STRBUF_INIT;
556
557                         /*
558                          * There is the PCRE2_LITERAL flag, but it's
559                          * only in PCRE v2 10.30 and later. Needing to
560                          * ifdef our way around that and dealing with
561                          * it + PCRE2_MULTILINE being an error is more
562                          * complex than just quoting this ourselves.
563                         */
564                         strbuf_add(&sb, "\\Q", 2);
565                         strbuf_add(&sb, p->pattern, p->patternlen);
566                         strbuf_add(&sb, "\\E", 2);
567
568                         p->pattern = sb.buf;
569                         p->patternlen = sb.len;
570                         compile_pcre2_pattern(p, opt);
571                         p->pattern = old_pattern;
572                         p->patternlen = old_patternlen;
573                         strbuf_release(&sb);
574                 }
575 #else /* !USE_LIBPCRE2 */
576                 compile_fixed_regexp(p, opt);
577 #endif /* !USE_LIBPCRE2 */
578                 return;
579         }
580
581         if (opt->pcre2) {
582                 compile_pcre2_pattern(p, opt);
583                 return;
584         }
585
586         if (p->ignore_case)
587                 regflags |= REG_ICASE;
588         if (opt->extended_regexp_option)
589                 regflags |= REG_EXTENDED;
590         err = regcomp(&p->regexp, p->pattern, regflags);
591         if (err) {
592                 char errbuf[1024];
593                 regerror(err, &p->regexp, errbuf, 1024);
594                 compile_regexp_failed(p, errbuf);
595         }
596 }
597
598 static struct grep_expr *compile_pattern_or(struct grep_pat **);
599 static struct grep_expr *compile_pattern_atom(struct grep_pat **list)
600 {
601         struct grep_pat *p;
602         struct grep_expr *x;
603
604         p = *list;
605         if (!p)
606                 return NULL;
607         switch (p->token) {
608         case GREP_PATTERN: /* atom */
609         case GREP_PATTERN_HEAD:
610         case GREP_PATTERN_BODY:
611                 CALLOC_ARRAY(x, 1);
612                 x->node = GREP_NODE_ATOM;
613                 x->u.atom = p;
614                 *list = p->next;
615                 return x;
616         case GREP_OPEN_PAREN:
617                 *list = p->next;
618                 x = compile_pattern_or(list);
619                 if (!*list || (*list)->token != GREP_CLOSE_PAREN)
620                         die("unmatched parenthesis");
621                 *list = (*list)->next;
622                 return x;
623         default:
624                 return NULL;
625         }
626 }
627
628 static struct grep_expr *compile_pattern_not(struct grep_pat **list)
629 {
630         struct grep_pat *p;
631         struct grep_expr *x;
632
633         p = *list;
634         if (!p)
635                 return NULL;
636         switch (p->token) {
637         case GREP_NOT:
638                 if (!p->next)
639                         die("--not not followed by pattern expression");
640                 *list = p->next;
641                 CALLOC_ARRAY(x, 1);
642                 x->node = GREP_NODE_NOT;
643                 x->u.unary = compile_pattern_not(list);
644                 if (!x->u.unary)
645                         die("--not followed by non pattern expression");
646                 return x;
647         default:
648                 return compile_pattern_atom(list);
649         }
650 }
651
652 static struct grep_expr *compile_pattern_and(struct grep_pat **list)
653 {
654         struct grep_pat *p;
655         struct grep_expr *x, *y, *z;
656
657         x = compile_pattern_not(list);
658         p = *list;
659         if (p && p->token == GREP_AND) {
660                 if (!p->next)
661                         die("--and not followed by pattern expression");
662                 *list = p->next;
663                 y = compile_pattern_and(list);
664                 if (!y)
665                         die("--and not followed by pattern expression");
666                 CALLOC_ARRAY(z, 1);
667                 z->node = GREP_NODE_AND;
668                 z->u.binary.left = x;
669                 z->u.binary.right = y;
670                 return z;
671         }
672         return x;
673 }
674
675 static struct grep_expr *compile_pattern_or(struct grep_pat **list)
676 {
677         struct grep_pat *p;
678         struct grep_expr *x, *y, *z;
679
680         x = compile_pattern_and(list);
681         p = *list;
682         if (x && p && p->token != GREP_CLOSE_PAREN) {
683                 y = compile_pattern_or(list);
684                 if (!y)
685                         die("not a pattern expression %s", p->pattern);
686                 CALLOC_ARRAY(z, 1);
687                 z->node = GREP_NODE_OR;
688                 z->u.binary.left = x;
689                 z->u.binary.right = y;
690                 return z;
691         }
692         return x;
693 }
694
695 static struct grep_expr *compile_pattern_expr(struct grep_pat **list)
696 {
697         return compile_pattern_or(list);
698 }
699
700 static struct grep_expr *grep_true_expr(void)
701 {
702         struct grep_expr *z = xcalloc(1, sizeof(*z));
703         z->node = GREP_NODE_TRUE;
704         return z;
705 }
706
707 static struct grep_expr *grep_or_expr(struct grep_expr *left, struct grep_expr *right)
708 {
709         struct grep_expr *z = xcalloc(1, sizeof(*z));
710         z->node = GREP_NODE_OR;
711         z->u.binary.left = left;
712         z->u.binary.right = right;
713         return z;
714 }
715
716 static struct grep_expr *prep_header_patterns(struct grep_opt *opt)
717 {
718         struct grep_pat *p;
719         struct grep_expr *header_expr;
720         struct grep_expr *(header_group[GREP_HEADER_FIELD_MAX]);
721         enum grep_header_field fld;
722
723         if (!opt->header_list)
724                 return NULL;
725
726         for (p = opt->header_list; p; p = p->next) {
727                 if (p->token != GREP_PATTERN_HEAD)
728                         BUG("a non-header pattern in grep header list.");
729                 if (p->field < GREP_HEADER_FIELD_MIN ||
730                     GREP_HEADER_FIELD_MAX <= p->field)
731                         BUG("unknown header field %d", p->field);
732                 compile_regexp(p, opt);
733         }
734
735         for (fld = 0; fld < GREP_HEADER_FIELD_MAX; fld++)
736                 header_group[fld] = NULL;
737
738         for (p = opt->header_list; p; p = p->next) {
739                 struct grep_expr *h;
740                 struct grep_pat *pp = p;
741
742                 h = compile_pattern_atom(&pp);
743                 if (!h || pp != p->next)
744                         BUG("malformed header expr");
745                 if (!header_group[p->field]) {
746                         header_group[p->field] = h;
747                         continue;
748                 }
749                 header_group[p->field] = grep_or_expr(h, header_group[p->field]);
750         }
751
752         header_expr = NULL;
753
754         for (fld = 0; fld < GREP_HEADER_FIELD_MAX; fld++) {
755                 if (!header_group[fld])
756                         continue;
757                 if (!header_expr)
758                         header_expr = grep_true_expr();
759                 header_expr = grep_or_expr(header_group[fld], header_expr);
760         }
761         return header_expr;
762 }
763
764 static struct grep_expr *grep_splice_or(struct grep_expr *x, struct grep_expr *y)
765 {
766         struct grep_expr *z = x;
767
768         while (x) {
769                 assert(x->node == GREP_NODE_OR);
770                 if (x->u.binary.right &&
771                     x->u.binary.right->node == GREP_NODE_TRUE) {
772                         x->u.binary.right = y;
773                         break;
774                 }
775                 x = x->u.binary.right;
776         }
777         return z;
778 }
779
780 void compile_grep_patterns(struct grep_opt *opt)
781 {
782         struct grep_pat *p;
783         struct grep_expr *header_expr = prep_header_patterns(opt);
784
785         for (p = opt->pattern_list; p; p = p->next) {
786                 switch (p->token) {
787                 case GREP_PATTERN: /* atom */
788                 case GREP_PATTERN_HEAD:
789                 case GREP_PATTERN_BODY:
790                         compile_regexp(p, opt);
791                         break;
792                 default:
793                         opt->extended = 1;
794                         break;
795                 }
796         }
797
798         if (opt->all_match || header_expr)
799                 opt->extended = 1;
800         else if (!opt->extended)
801                 return;
802
803         p = opt->pattern_list;
804         if (p)
805                 opt->pattern_expression = compile_pattern_expr(&p);
806         if (p)
807                 die("incomplete pattern expression: %s", p->pattern);
808
809         if (!header_expr)
810                 return;
811
812         if (!opt->pattern_expression)
813                 opt->pattern_expression = header_expr;
814         else if (opt->all_match)
815                 opt->pattern_expression = grep_splice_or(header_expr,
816                                                          opt->pattern_expression);
817         else
818                 opt->pattern_expression = grep_or_expr(opt->pattern_expression,
819                                                        header_expr);
820         opt->all_match = 1;
821 }
822
823 static void free_pattern_expr(struct grep_expr *x)
824 {
825         switch (x->node) {
826         case GREP_NODE_TRUE:
827         case GREP_NODE_ATOM:
828                 break;
829         case GREP_NODE_NOT:
830                 free_pattern_expr(x->u.unary);
831                 break;
832         case GREP_NODE_AND:
833         case GREP_NODE_OR:
834                 free_pattern_expr(x->u.binary.left);
835                 free_pattern_expr(x->u.binary.right);
836                 break;
837         }
838         free(x);
839 }
840
841 void free_grep_patterns(struct grep_opt *opt)
842 {
843         struct grep_pat *p, *n;
844
845         for (p = opt->pattern_list; p; p = n) {
846                 n = p->next;
847                 switch (p->token) {
848                 case GREP_PATTERN: /* atom */
849                 case GREP_PATTERN_HEAD:
850                 case GREP_PATTERN_BODY:
851                         if (p->pcre2_pattern)
852                                 free_pcre2_pattern(p);
853                         else
854                                 regfree(&p->regexp);
855                         free(p->pattern);
856                         break;
857                 default:
858                         break;
859                 }
860                 free(p);
861         }
862
863         if (!opt->extended)
864                 return;
865         free_pattern_expr(opt->pattern_expression);
866 }
867
868 static char *end_of_line(char *cp, unsigned long *left)
869 {
870         unsigned long l = *left;
871         while (l && *cp != '\n') {
872                 l--;
873                 cp++;
874         }
875         *left = l;
876         return cp;
877 }
878
879 static int word_char(char ch)
880 {
881         return isalnum(ch) || ch == '_';
882 }
883
884 static void output_color(struct grep_opt *opt, const void *data, size_t size,
885                          const char *color)
886 {
887         if (want_color(opt->color) && color && color[0]) {
888                 opt->output(opt, color, strlen(color));
889                 opt->output(opt, data, size);
890                 opt->output(opt, GIT_COLOR_RESET, strlen(GIT_COLOR_RESET));
891         } else
892                 opt->output(opt, data, size);
893 }
894
895 static void output_sep(struct grep_opt *opt, char sign)
896 {
897         if (opt->null_following_name)
898                 opt->output(opt, "\0", 1);
899         else
900                 output_color(opt, &sign, 1, opt->colors[GREP_COLOR_SEP]);
901 }
902
903 static void show_name(struct grep_opt *opt, const char *name)
904 {
905         output_color(opt, name, strlen(name), opt->colors[GREP_COLOR_FILENAME]);
906         opt->output(opt, opt->null_following_name ? "\0" : "\n", 1);
907 }
908
909 static int patmatch(struct grep_pat *p, char *line, char *eol,
910                     regmatch_t *match, int eflags)
911 {
912         int hit;
913
914         if (p->pcre2_pattern)
915                 hit = !pcre2match(p, line, eol, match, eflags);
916         else
917                 hit = !regexec_buf(&p->regexp, line, eol - line, 1, match,
918                                    eflags);
919
920         return hit;
921 }
922
923 static int strip_timestamp(char *bol, char **eol_p)
924 {
925         char *eol = *eol_p;
926         int ch;
927
928         while (bol < --eol) {
929                 if (*eol != '>')
930                         continue;
931                 *eol_p = ++eol;
932                 ch = *eol;
933                 *eol = '\0';
934                 return ch;
935         }
936         return 0;
937 }
938
939 static struct {
940         const char *field;
941         size_t len;
942 } header_field[] = {
943         { "author ", 7 },
944         { "committer ", 10 },
945         { "reflog ", 7 },
946 };
947
948 static int match_one_pattern(struct grep_pat *p, char *bol, char *eol,
949                              enum grep_context ctx,
950                              regmatch_t *pmatch, int eflags)
951 {
952         int hit = 0;
953         int saved_ch = 0;
954         const char *start = bol;
955
956         if ((p->token != GREP_PATTERN) &&
957             ((p->token == GREP_PATTERN_HEAD) != (ctx == GREP_CONTEXT_HEAD)))
958                 return 0;
959
960         if (p->token == GREP_PATTERN_HEAD) {
961                 const char *field;
962                 size_t len;
963                 assert(p->field < ARRAY_SIZE(header_field));
964                 field = header_field[p->field].field;
965                 len = header_field[p->field].len;
966                 if (strncmp(bol, field, len))
967                         return 0;
968                 bol += len;
969                 switch (p->field) {
970                 case GREP_HEADER_AUTHOR:
971                 case GREP_HEADER_COMMITTER:
972                         saved_ch = strip_timestamp(bol, &eol);
973                         break;
974                 default:
975                         break;
976                 }
977         }
978
979  again:
980         hit = patmatch(p, bol, eol, pmatch, eflags);
981
982         if (hit && p->word_regexp) {
983                 if ((pmatch[0].rm_so < 0) ||
984                     (eol - bol) < pmatch[0].rm_so ||
985                     (pmatch[0].rm_eo < 0) ||
986                     (eol - bol) < pmatch[0].rm_eo)
987                         die("regexp returned nonsense");
988
989                 /* Match beginning must be either beginning of the
990                  * line, or at word boundary (i.e. the last char must
991                  * not be a word char).  Similarly, match end must be
992                  * either end of the line, or at word boundary
993                  * (i.e. the next char must not be a word char).
994                  */
995                 if ( ((pmatch[0].rm_so == 0) ||
996                       !word_char(bol[pmatch[0].rm_so-1])) &&
997                      ((pmatch[0].rm_eo == (eol-bol)) ||
998                       !word_char(bol[pmatch[0].rm_eo])) )
999                         ;
1000                 else
1001                         hit = 0;
1002
1003                 /* Words consist of at least one character. */
1004                 if (pmatch->rm_so == pmatch->rm_eo)
1005                         hit = 0;
1006
1007                 if (!hit && pmatch[0].rm_so + bol + 1 < eol) {
1008                         /* There could be more than one match on the
1009                          * line, and the first match might not be
1010                          * strict word match.  But later ones could be!
1011                          * Forward to the next possible start, i.e. the
1012                          * next position following a non-word char.
1013                          */
1014                         bol = pmatch[0].rm_so + bol + 1;
1015                         while (word_char(bol[-1]) && bol < eol)
1016                                 bol++;
1017                         eflags |= REG_NOTBOL;
1018                         if (bol < eol)
1019                                 goto again;
1020                 }
1021         }
1022         if (p->token == GREP_PATTERN_HEAD && saved_ch)
1023                 *eol = saved_ch;
1024         if (hit) {
1025                 pmatch[0].rm_so += bol - start;
1026                 pmatch[0].rm_eo += bol - start;
1027         }
1028         return hit;
1029 }
1030
1031 static int match_expr_eval(struct grep_opt *opt, struct grep_expr *x, char *bol,
1032                            char *eol, enum grep_context ctx, ssize_t *col,
1033                            ssize_t *icol, int collect_hits)
1034 {
1035         int h = 0;
1036
1037         if (!x)
1038                 die("Not a valid grep expression");
1039         switch (x->node) {
1040         case GREP_NODE_TRUE:
1041                 h = 1;
1042                 break;
1043         case GREP_NODE_ATOM:
1044                 {
1045                         regmatch_t tmp;
1046                         h = match_one_pattern(x->u.atom, bol, eol, ctx,
1047                                               &tmp, 0);
1048                         if (h && (*col < 0 || tmp.rm_so < *col))
1049                                 *col = tmp.rm_so;
1050                 }
1051                 break;
1052         case GREP_NODE_NOT:
1053                 /*
1054                  * Upon visiting a GREP_NODE_NOT, col and icol become swapped.
1055                  */
1056                 h = !match_expr_eval(opt, x->u.unary, bol, eol, ctx, icol, col,
1057                                      0);
1058                 break;
1059         case GREP_NODE_AND:
1060                 h = match_expr_eval(opt, x->u.binary.left, bol, eol, ctx, col,
1061                                     icol, 0);
1062                 if (h || opt->columnnum) {
1063                         /*
1064                          * Don't short-circuit AND when given --column, since a
1065                          * NOT earlier in the tree may turn this into an OR. In
1066                          * this case, see the below comment.
1067                          */
1068                         h &= match_expr_eval(opt, x->u.binary.right, bol, eol,
1069                                              ctx, col, icol, 0);
1070                 }
1071                 break;
1072         case GREP_NODE_OR:
1073                 if (!(collect_hits || opt->columnnum)) {
1074                         /*
1075                          * Don't short-circuit OR when given --column (or
1076                          * collecting hits) to ensure we don't skip a later
1077                          * child that would produce an earlier match.
1078                          */
1079                         return (match_expr_eval(opt, x->u.binary.left, bol, eol,
1080                                                 ctx, col, icol, 0) ||
1081                                 match_expr_eval(opt, x->u.binary.right, bol,
1082                                                 eol, ctx, col, icol, 0));
1083                 }
1084                 h = match_expr_eval(opt, x->u.binary.left, bol, eol, ctx, col,
1085                                     icol, 0);
1086                 if (collect_hits)
1087                         x->u.binary.left->hit |= h;
1088                 h |= match_expr_eval(opt, x->u.binary.right, bol, eol, ctx, col,
1089                                      icol, collect_hits);
1090                 break;
1091         default:
1092                 die("Unexpected node type (internal error) %d", x->node);
1093         }
1094         if (collect_hits)
1095                 x->hit |= h;
1096         return h;
1097 }
1098
1099 static int match_expr(struct grep_opt *opt, char *bol, char *eol,
1100                       enum grep_context ctx, ssize_t *col,
1101                       ssize_t *icol, int collect_hits)
1102 {
1103         struct grep_expr *x = opt->pattern_expression;
1104         return match_expr_eval(opt, x, bol, eol, ctx, col, icol, collect_hits);
1105 }
1106
1107 static int match_line(struct grep_opt *opt, char *bol, char *eol,
1108                       ssize_t *col, ssize_t *icol,
1109                       enum grep_context ctx, int collect_hits)
1110 {
1111         struct grep_pat *p;
1112         int hit = 0;
1113
1114         if (opt->extended)
1115                 return match_expr(opt, bol, eol, ctx, col, icol,
1116                                   collect_hits);
1117
1118         /* we do not call with collect_hits without being extended */
1119         for (p = opt->pattern_list; p; p = p->next) {
1120                 regmatch_t tmp;
1121                 if (match_one_pattern(p, bol, eol, ctx, &tmp, 0)) {
1122                         hit |= 1;
1123                         if (!opt->columnnum) {
1124                                 /*
1125                                  * Without --column, any single match on a line
1126                                  * is enough to know that it needs to be
1127                                  * printed. With --column, scan _all_ patterns
1128                                  * to find the earliest.
1129                                  */
1130                                 break;
1131                         }
1132                         if (*col < 0 || tmp.rm_so < *col)
1133                                 *col = tmp.rm_so;
1134                 }
1135         }
1136         return hit;
1137 }
1138
1139 static int match_next_pattern(struct grep_pat *p, char *bol, char *eol,
1140                               enum grep_context ctx,
1141                               regmatch_t *pmatch, int eflags)
1142 {
1143         regmatch_t match;
1144
1145         if (!match_one_pattern(p, bol, eol, ctx, &match, eflags))
1146                 return 0;
1147         if (match.rm_so < 0 || match.rm_eo < 0)
1148                 return 0;
1149         if (pmatch->rm_so >= 0 && pmatch->rm_eo >= 0) {
1150                 if (match.rm_so > pmatch->rm_so)
1151                         return 1;
1152                 if (match.rm_so == pmatch->rm_so && match.rm_eo < pmatch->rm_eo)
1153                         return 1;
1154         }
1155         pmatch->rm_so = match.rm_so;
1156         pmatch->rm_eo = match.rm_eo;
1157         return 1;
1158 }
1159
1160 static int next_match(struct grep_opt *opt, char *bol, char *eol,
1161                       enum grep_context ctx, regmatch_t *pmatch, int eflags)
1162 {
1163         struct grep_pat *p;
1164         int hit = 0;
1165
1166         pmatch->rm_so = pmatch->rm_eo = -1;
1167         if (bol < eol) {
1168                 for (p = opt->pattern_list; p; p = p->next) {
1169                         switch (p->token) {
1170                         case GREP_PATTERN: /* atom */
1171                         case GREP_PATTERN_HEAD:
1172                         case GREP_PATTERN_BODY:
1173                                 hit |= match_next_pattern(p, bol, eol, ctx,
1174                                                           pmatch, eflags);
1175                                 break;
1176                         default:
1177                                 break;
1178                         }
1179                 }
1180         }
1181         return hit;
1182 }
1183
1184 static void show_line_header(struct grep_opt *opt, const char *name,
1185                              unsigned lno, ssize_t cno, char sign)
1186 {
1187         if (opt->heading && opt->last_shown == 0) {
1188                 output_color(opt, name, strlen(name), opt->colors[GREP_COLOR_FILENAME]);
1189                 opt->output(opt, "\n", 1);
1190         }
1191         opt->last_shown = lno;
1192
1193         if (!opt->heading && opt->pathname) {
1194                 output_color(opt, name, strlen(name), opt->colors[GREP_COLOR_FILENAME]);
1195                 output_sep(opt, sign);
1196         }
1197         if (opt->linenum) {
1198                 char buf[32];
1199                 xsnprintf(buf, sizeof(buf), "%d", lno);
1200                 output_color(opt, buf, strlen(buf), opt->colors[GREP_COLOR_LINENO]);
1201                 output_sep(opt, sign);
1202         }
1203         /*
1204          * Treat 'cno' as the 1-indexed offset from the start of a non-context
1205          * line to its first match. Otherwise, 'cno' is 0 indicating that we are
1206          * being called with a context line.
1207          */
1208         if (opt->columnnum && cno) {
1209                 char buf[32];
1210                 xsnprintf(buf, sizeof(buf), "%"PRIuMAX, (uintmax_t)cno);
1211                 output_color(opt, buf, strlen(buf), opt->colors[GREP_COLOR_COLUMNNO]);
1212                 output_sep(opt, sign);
1213         }
1214 }
1215
1216 static void show_line(struct grep_opt *opt, char *bol, char *eol,
1217                       const char *name, unsigned lno, ssize_t cno, char sign)
1218 {
1219         int rest = eol - bol;
1220         const char *match_color = NULL;
1221         const char *line_color = NULL;
1222
1223         if (opt->file_break && opt->last_shown == 0) {
1224                 if (opt->show_hunk_mark)
1225                         opt->output(opt, "\n", 1);
1226         } else if (opt->pre_context || opt->post_context || opt->funcbody) {
1227                 if (opt->last_shown == 0) {
1228                         if (opt->show_hunk_mark) {
1229                                 output_color(opt, "--", 2, opt->colors[GREP_COLOR_SEP]);
1230                                 opt->output(opt, "\n", 1);
1231                         }
1232                 } else if (lno > opt->last_shown + 1) {
1233                         output_color(opt, "--", 2, opt->colors[GREP_COLOR_SEP]);
1234                         opt->output(opt, "\n", 1);
1235                 }
1236         }
1237         if (!opt->only_matching) {
1238                 /*
1239                  * In case the line we're being called with contains more than
1240                  * one match, leave printing each header to the loop below.
1241                  */
1242                 show_line_header(opt, name, lno, cno, sign);
1243         }
1244         if (opt->color || opt->only_matching) {
1245                 regmatch_t match;
1246                 enum grep_context ctx = GREP_CONTEXT_BODY;
1247                 int ch = *eol;
1248                 int eflags = 0;
1249
1250                 if (opt->color) {
1251                         if (sign == ':')
1252                                 match_color = opt->colors[GREP_COLOR_MATCH_SELECTED];
1253                         else
1254                                 match_color = opt->colors[GREP_COLOR_MATCH_CONTEXT];
1255                         if (sign == ':')
1256                                 line_color = opt->colors[GREP_COLOR_SELECTED];
1257                         else if (sign == '-')
1258                                 line_color = opt->colors[GREP_COLOR_CONTEXT];
1259                         else if (sign == '=')
1260                                 line_color = opt->colors[GREP_COLOR_FUNCTION];
1261                 }
1262                 *eol = '\0';
1263                 while (next_match(opt, bol, eol, ctx, &match, eflags)) {
1264                         if (match.rm_so == match.rm_eo)
1265                                 break;
1266
1267                         if (opt->only_matching)
1268                                 show_line_header(opt, name, lno, cno, sign);
1269                         else
1270                                 output_color(opt, bol, match.rm_so, line_color);
1271                         output_color(opt, bol + match.rm_so,
1272                                      match.rm_eo - match.rm_so, match_color);
1273                         if (opt->only_matching)
1274                                 opt->output(opt, "\n", 1);
1275                         bol += match.rm_eo;
1276                         cno += match.rm_eo;
1277                         rest -= match.rm_eo;
1278                         eflags = REG_NOTBOL;
1279                 }
1280                 *eol = ch;
1281         }
1282         if (!opt->only_matching) {
1283                 output_color(opt, bol, rest, line_color);
1284                 opt->output(opt, "\n", 1);
1285         }
1286 }
1287
1288 int grep_use_locks;
1289
1290 /*
1291  * This lock protects access to the gitattributes machinery, which is
1292  * not thread-safe.
1293  */
1294 pthread_mutex_t grep_attr_mutex;
1295
1296 static inline void grep_attr_lock(void)
1297 {
1298         if (grep_use_locks)
1299                 pthread_mutex_lock(&grep_attr_mutex);
1300 }
1301
1302 static inline void grep_attr_unlock(void)
1303 {
1304         if (grep_use_locks)
1305                 pthread_mutex_unlock(&grep_attr_mutex);
1306 }
1307
1308 static int match_funcname(struct grep_opt *opt, struct grep_source *gs, char *bol, char *eol)
1309 {
1310         xdemitconf_t *xecfg = opt->priv;
1311         if (xecfg && !xecfg->find_func) {
1312                 grep_source_load_driver(gs, opt->repo->index);
1313                 if (gs->driver->funcname.pattern) {
1314                         const struct userdiff_funcname *pe = &gs->driver->funcname;
1315                         xdiff_set_find_func(xecfg, pe->pattern, pe->cflags);
1316                 } else {
1317                         xecfg = opt->priv = NULL;
1318                 }
1319         }
1320
1321         if (xecfg) {
1322                 char buf[1];
1323                 return xecfg->find_func(bol, eol - bol, buf, 1,
1324                                         xecfg->find_func_priv) >= 0;
1325         }
1326
1327         if (bol == eol)
1328                 return 0;
1329         if (isalpha(*bol) || *bol == '_' || *bol == '$')
1330                 return 1;
1331         return 0;
1332 }
1333
1334 static void show_funcname_line(struct grep_opt *opt, struct grep_source *gs,
1335                                char *bol, unsigned lno)
1336 {
1337         while (bol > gs->buf) {
1338                 char *eol = --bol;
1339
1340                 while (bol > gs->buf && bol[-1] != '\n')
1341                         bol--;
1342                 lno--;
1343
1344                 if (lno <= opt->last_shown)
1345                         break;
1346
1347                 if (match_funcname(opt, gs, bol, eol)) {
1348                         show_line(opt, bol, eol, gs->name, lno, 0, '=');
1349                         break;
1350                 }
1351         }
1352 }
1353
1354 static int is_empty_line(const char *bol, const char *eol);
1355
1356 static void show_pre_context(struct grep_opt *opt, struct grep_source *gs,
1357                              char *bol, char *end, unsigned lno)
1358 {
1359         unsigned cur = lno, from = 1, funcname_lno = 0, orig_from;
1360         int funcname_needed = !!opt->funcname, comment_needed = 0;
1361
1362         if (opt->pre_context < lno)
1363                 from = lno - opt->pre_context;
1364         if (from <= opt->last_shown)
1365                 from = opt->last_shown + 1;
1366         orig_from = from;
1367         if (opt->funcbody) {
1368                 if (match_funcname(opt, gs, bol, end))
1369                         comment_needed = 1;
1370                 else
1371                         funcname_needed = 1;
1372                 from = opt->last_shown + 1;
1373         }
1374
1375         /* Rewind. */
1376         while (bol > gs->buf && cur > from) {
1377                 char *next_bol = bol;
1378                 char *eol = --bol;
1379
1380                 while (bol > gs->buf && bol[-1] != '\n')
1381                         bol--;
1382                 cur--;
1383                 if (comment_needed && (is_empty_line(bol, eol) ||
1384                                        match_funcname(opt, gs, bol, eol))) {
1385                         comment_needed = 0;
1386                         from = orig_from;
1387                         if (cur < from) {
1388                                 cur++;
1389                                 bol = next_bol;
1390                                 break;
1391                         }
1392                 }
1393                 if (funcname_needed && match_funcname(opt, gs, bol, eol)) {
1394                         funcname_lno = cur;
1395                         funcname_needed = 0;
1396                         if (opt->funcbody)
1397                                 comment_needed = 1;
1398                         else
1399                                 from = orig_from;
1400                 }
1401         }
1402
1403         /* We need to look even further back to find a function signature. */
1404         if (opt->funcname && funcname_needed)
1405                 show_funcname_line(opt, gs, bol, cur);
1406
1407         /* Back forward. */
1408         while (cur < lno) {
1409                 char *eol = bol, sign = (cur == funcname_lno) ? '=' : '-';
1410
1411                 while (*eol != '\n')
1412                         eol++;
1413                 show_line(opt, bol, eol, gs->name, cur, 0, sign);
1414                 bol = eol + 1;
1415                 cur++;
1416         }
1417 }
1418
1419 static int should_lookahead(struct grep_opt *opt)
1420 {
1421         struct grep_pat *p;
1422
1423         if (opt->extended)
1424                 return 0; /* punt for too complex stuff */
1425         if (opt->invert)
1426                 return 0;
1427         for (p = opt->pattern_list; p; p = p->next) {
1428                 if (p->token != GREP_PATTERN)
1429                         return 0; /* punt for "header only" and stuff */
1430         }
1431         return 1;
1432 }
1433
1434 static int look_ahead(struct grep_opt *opt,
1435                       unsigned long *left_p,
1436                       unsigned *lno_p,
1437                       char **bol_p)
1438 {
1439         unsigned lno = *lno_p;
1440         char *bol = *bol_p;
1441         struct grep_pat *p;
1442         char *sp, *last_bol;
1443         regoff_t earliest = -1;
1444
1445         for (p = opt->pattern_list; p; p = p->next) {
1446                 int hit;
1447                 regmatch_t m;
1448
1449                 hit = patmatch(p, bol, bol + *left_p, &m, 0);
1450                 if (!hit || m.rm_so < 0 || m.rm_eo < 0)
1451                         continue;
1452                 if (earliest < 0 || m.rm_so < earliest)
1453                         earliest = m.rm_so;
1454         }
1455
1456         if (earliest < 0) {
1457                 *bol_p = bol + *left_p;
1458                 *left_p = 0;
1459                 return 1;
1460         }
1461         for (sp = bol + earliest; bol < sp && sp[-1] != '\n'; sp--)
1462                 ; /* find the beginning of the line */
1463         last_bol = sp;
1464
1465         for (sp = bol; sp < last_bol; sp++) {
1466                 if (*sp == '\n')
1467                         lno++;
1468         }
1469         *left_p -= last_bol - bol;
1470         *bol_p = last_bol;
1471         *lno_p = lno;
1472         return 0;
1473 }
1474
1475 static int fill_textconv_grep(struct repository *r,
1476                               struct userdiff_driver *driver,
1477                               struct grep_source *gs)
1478 {
1479         struct diff_filespec *df;
1480         char *buf;
1481         size_t size;
1482
1483         if (!driver || !driver->textconv)
1484                 return grep_source_load(gs);
1485
1486         /*
1487          * The textconv interface is intimately tied to diff_filespecs, so we
1488          * have to pretend to be one. If we could unify the grep_source
1489          * and diff_filespec structs, this mess could just go away.
1490          */
1491         df = alloc_filespec(gs->path);
1492         switch (gs->type) {
1493         case GREP_SOURCE_OID:
1494                 fill_filespec(df, gs->identifier, 1, 0100644);
1495                 break;
1496         case GREP_SOURCE_FILE:
1497                 fill_filespec(df, &null_oid, 0, 0100644);
1498                 break;
1499         default:
1500                 BUG("attempt to textconv something without a path?");
1501         }
1502
1503         /*
1504          * fill_textconv is not remotely thread-safe; it modifies the global
1505          * diff tempfile structure, writes to the_repo's odb and might
1506          * internally call thread-unsafe functions such as the
1507          * prepare_packed_git() lazy-initializator. Because of the last two, we
1508          * must ensure mutual exclusion between this call and the object reading
1509          * API, thus we use obj_read_lock() here.
1510          *
1511          * TODO: allowing text conversion to run in parallel with object
1512          * reading operations might increase performance in the multithreaded
1513          * non-worktreee git-grep with --textconv.
1514          */
1515         obj_read_lock();
1516         size = fill_textconv(r, driver, df, &buf);
1517         obj_read_unlock();
1518         free_filespec(df);
1519
1520         /*
1521          * The normal fill_textconv usage by the diff machinery would just keep
1522          * the textconv'd buf separate from the diff_filespec. But much of the
1523          * grep code passes around a grep_source and assumes that its "buf"
1524          * pointer is the beginning of the thing we are searching. So let's
1525          * install our textconv'd version into the grep_source, taking care not
1526          * to leak any existing buffer.
1527          */
1528         grep_source_clear_data(gs);
1529         gs->buf = buf;
1530         gs->size = size;
1531
1532         return 0;
1533 }
1534
1535 static int is_empty_line(const char *bol, const char *eol)
1536 {
1537         while (bol < eol && isspace(*bol))
1538                 bol++;
1539         return bol == eol;
1540 }
1541
1542 static int grep_source_1(struct grep_opt *opt, struct grep_source *gs, int collect_hits)
1543 {
1544         char *bol;
1545         char *peek_bol = NULL;
1546         unsigned long left;
1547         unsigned lno = 1;
1548         unsigned last_hit = 0;
1549         int binary_match_only = 0;
1550         unsigned count = 0;
1551         int try_lookahead = 0;
1552         int show_function = 0;
1553         struct userdiff_driver *textconv = NULL;
1554         enum grep_context ctx = GREP_CONTEXT_HEAD;
1555         xdemitconf_t xecfg;
1556
1557         if (!opt->status_only && gs->name == NULL)
1558                 BUG("grep call which could print a name requires "
1559                     "grep_source.name be non-NULL");
1560
1561         if (!opt->output)
1562                 opt->output = std_output;
1563
1564         if (opt->pre_context || opt->post_context || opt->file_break ||
1565             opt->funcbody) {
1566                 /* Show hunk marks, except for the first file. */
1567                 if (opt->last_shown)
1568                         opt->show_hunk_mark = 1;
1569                 /*
1570                  * If we're using threads then we can't easily identify
1571                  * the first file.  Always put hunk marks in that case
1572                  * and skip the very first one later in work_done().
1573                  */
1574                 if (opt->output != std_output)
1575                         opt->show_hunk_mark = 1;
1576         }
1577         opt->last_shown = 0;
1578
1579         if (opt->allow_textconv) {
1580                 grep_source_load_driver(gs, opt->repo->index);
1581                 /*
1582                  * We might set up the shared textconv cache data here, which
1583                  * is not thread-safe. Also, get_oid_with_context() and
1584                  * parse_object() might be internally called. As they are not
1585                  * currently thread-safe and might be racy with object reading,
1586                  * obj_read_lock() must be called.
1587                  */
1588                 grep_attr_lock();
1589                 obj_read_lock();
1590                 textconv = userdiff_get_textconv(opt->repo, gs->driver);
1591                 obj_read_unlock();
1592                 grep_attr_unlock();
1593         }
1594
1595         /*
1596          * We know the result of a textconv is text, so we only have to care
1597          * about binary handling if we are not using it.
1598          */
1599         if (!textconv) {
1600                 switch (opt->binary) {
1601                 case GREP_BINARY_DEFAULT:
1602                         if (grep_source_is_binary(gs, opt->repo->index))
1603                                 binary_match_only = 1;
1604                         break;
1605                 case GREP_BINARY_NOMATCH:
1606                         if (grep_source_is_binary(gs, opt->repo->index))
1607                                 return 0; /* Assume unmatch */
1608                         break;
1609                 case GREP_BINARY_TEXT:
1610                         break;
1611                 default:
1612                         BUG("unknown binary handling mode");
1613                 }
1614         }
1615
1616         memset(&xecfg, 0, sizeof(xecfg));
1617         opt->priv = &xecfg;
1618
1619         try_lookahead = should_lookahead(opt);
1620
1621         if (fill_textconv_grep(opt->repo, textconv, gs) < 0)
1622                 return 0;
1623
1624         bol = gs->buf;
1625         left = gs->size;
1626         while (left) {
1627                 char *eol, ch;
1628                 int hit;
1629                 ssize_t cno;
1630                 ssize_t col = -1, icol = -1;
1631
1632                 /*
1633                  * look_ahead() skips quickly to the line that possibly
1634                  * has the next hit; don't call it if we need to do
1635                  * something more than just skipping the current line
1636                  * in response to an unmatch for the current line.  E.g.
1637                  * inside a post-context window, we will show the current
1638                  * line as a context around the previous hit when it
1639                  * doesn't hit.
1640                  */
1641                 if (try_lookahead
1642                     && !(last_hit
1643                          && (show_function ||
1644                              lno <= last_hit + opt->post_context))
1645                     && look_ahead(opt, &left, &lno, &bol))
1646                         break;
1647                 eol = end_of_line(bol, &left);
1648                 ch = *eol;
1649                 *eol = 0;
1650
1651                 if ((ctx == GREP_CONTEXT_HEAD) && (eol == bol))
1652                         ctx = GREP_CONTEXT_BODY;
1653
1654                 hit = match_line(opt, bol, eol, &col, &icol, ctx, collect_hits);
1655                 *eol = ch;
1656
1657                 if (collect_hits)
1658                         goto next_line;
1659
1660                 /* "grep -v -e foo -e bla" should list lines
1661                  * that do not have either, so inversion should
1662                  * be done outside.
1663                  */
1664                 if (opt->invert)
1665                         hit = !hit;
1666                 if (opt->unmatch_name_only) {
1667                         if (hit)
1668                                 return 0;
1669                         goto next_line;
1670                 }
1671                 if (hit) {
1672                         count++;
1673                         if (opt->status_only)
1674                                 return 1;
1675                         if (opt->name_only) {
1676                                 show_name(opt, gs->name);
1677                                 return 1;
1678                         }
1679                         if (opt->count)
1680                                 goto next_line;
1681                         if (binary_match_only) {
1682                                 opt->output(opt, "Binary file ", 12);
1683                                 output_color(opt, gs->name, strlen(gs->name),
1684                                              opt->colors[GREP_COLOR_FILENAME]);
1685                                 opt->output(opt, " matches\n", 9);
1686                                 return 1;
1687                         }
1688                         /* Hit at this line.  If we haven't shown the
1689                          * pre-context lines, we would need to show them.
1690                          */
1691                         if (opt->pre_context || opt->funcbody)
1692                                 show_pre_context(opt, gs, bol, eol, lno);
1693                         else if (opt->funcname)
1694                                 show_funcname_line(opt, gs, bol, lno);
1695                         cno = opt->invert ? icol : col;
1696                         if (cno < 0) {
1697                                 /*
1698                                  * A negative cno indicates that there was no
1699                                  * match on the line. We are thus inverted and
1700                                  * being asked to show all lines that _don't_
1701                                  * match a given expression. Therefore, set cno
1702                                  * to 0 to suggest the whole line matches.
1703                                  */
1704                                 cno = 0;
1705                         }
1706                         show_line(opt, bol, eol, gs->name, lno, cno + 1, ':');
1707                         last_hit = lno;
1708                         if (opt->funcbody)
1709                                 show_function = 1;
1710                         goto next_line;
1711                 }
1712                 if (show_function && (!peek_bol || peek_bol < bol)) {
1713                         unsigned long peek_left = left;
1714                         char *peek_eol = eol;
1715
1716                         /*
1717                          * Trailing empty lines are not interesting.
1718                          * Peek past them to see if they belong to the
1719                          * body of the current function.
1720                          */
1721                         peek_bol = bol;
1722                         while (is_empty_line(peek_bol, peek_eol)) {
1723                                 peek_bol = peek_eol + 1;
1724                                 peek_eol = end_of_line(peek_bol, &peek_left);
1725                         }
1726
1727                         if (match_funcname(opt, gs, peek_bol, peek_eol))
1728                                 show_function = 0;
1729                 }
1730                 if (show_function ||
1731                     (last_hit && lno <= last_hit + opt->post_context)) {
1732                         /* If the last hit is within the post context,
1733                          * we need to show this line.
1734                          */
1735                         show_line(opt, bol, eol, gs->name, lno, col + 1, '-');
1736                 }
1737
1738         next_line:
1739                 bol = eol + 1;
1740                 if (!left)
1741                         break;
1742                 left--;
1743                 lno++;
1744         }
1745
1746         if (collect_hits)
1747                 return 0;
1748
1749         if (opt->status_only)
1750                 return opt->unmatch_name_only;
1751         if (opt->unmatch_name_only) {
1752                 /* We did not see any hit, so we want to show this */
1753                 show_name(opt, gs->name);
1754                 return 1;
1755         }
1756
1757         xdiff_clear_find_func(&xecfg);
1758         opt->priv = NULL;
1759
1760         /* NEEDSWORK:
1761          * The real "grep -c foo *.c" gives many "bar.c:0" lines,
1762          * which feels mostly useless but sometimes useful.  Maybe
1763          * make it another option?  For now suppress them.
1764          */
1765         if (opt->count && count) {
1766                 char buf[32];
1767                 if (opt->pathname) {
1768                         output_color(opt, gs->name, strlen(gs->name),
1769                                      opt->colors[GREP_COLOR_FILENAME]);
1770                         output_sep(opt, ':');
1771                 }
1772                 xsnprintf(buf, sizeof(buf), "%u\n", count);
1773                 opt->output(opt, buf, strlen(buf));
1774                 return 1;
1775         }
1776         return !!last_hit;
1777 }
1778
1779 static void clr_hit_marker(struct grep_expr *x)
1780 {
1781         /* All-hit markers are meaningful only at the very top level
1782          * OR node.
1783          */
1784         while (1) {
1785                 x->hit = 0;
1786                 if (x->node != GREP_NODE_OR)
1787                         return;
1788                 x->u.binary.left->hit = 0;
1789                 x = x->u.binary.right;
1790         }
1791 }
1792
1793 static int chk_hit_marker(struct grep_expr *x)
1794 {
1795         /* Top level nodes have hit markers.  See if they all are hits */
1796         while (1) {
1797                 if (x->node != GREP_NODE_OR)
1798                         return x->hit;
1799                 if (!x->u.binary.left->hit)
1800                         return 0;
1801                 x = x->u.binary.right;
1802         }
1803 }
1804
1805 int grep_source(struct grep_opt *opt, struct grep_source *gs)
1806 {
1807         /*
1808          * we do not have to do the two-pass grep when we do not check
1809          * buffer-wide "all-match".
1810          */
1811         if (!opt->all_match)
1812                 return grep_source_1(opt, gs, 0);
1813
1814         /* Otherwise the toplevel "or" terms hit a bit differently.
1815          * We first clear hit markers from them.
1816          */
1817         clr_hit_marker(opt->pattern_expression);
1818         grep_source_1(opt, gs, 1);
1819
1820         if (!chk_hit_marker(opt->pattern_expression))
1821                 return 0;
1822
1823         return grep_source_1(opt, gs, 0);
1824 }
1825
1826 int grep_buffer(struct grep_opt *opt, char *buf, unsigned long size)
1827 {
1828         struct grep_source gs;
1829         int r;
1830
1831         grep_source_init(&gs, GREP_SOURCE_BUF, NULL, NULL, NULL);
1832         gs.buf = buf;
1833         gs.size = size;
1834
1835         r = grep_source(opt, &gs);
1836
1837         grep_source_clear(&gs);
1838         return r;
1839 }
1840
1841 void grep_source_init(struct grep_source *gs, enum grep_source_type type,
1842                       const char *name, const char *path,
1843                       const void *identifier)
1844 {
1845         gs->type = type;
1846         gs->name = xstrdup_or_null(name);
1847         gs->path = xstrdup_or_null(path);
1848         gs->buf = NULL;
1849         gs->size = 0;
1850         gs->driver = NULL;
1851
1852         switch (type) {
1853         case GREP_SOURCE_FILE:
1854                 gs->identifier = xstrdup(identifier);
1855                 break;
1856         case GREP_SOURCE_OID:
1857                 gs->identifier = oiddup(identifier);
1858                 break;
1859         case GREP_SOURCE_BUF:
1860                 gs->identifier = NULL;
1861                 break;
1862         }
1863 }
1864
1865 void grep_source_clear(struct grep_source *gs)
1866 {
1867         FREE_AND_NULL(gs->name);
1868         FREE_AND_NULL(gs->path);
1869         FREE_AND_NULL(gs->identifier);
1870         grep_source_clear_data(gs);
1871 }
1872
1873 void grep_source_clear_data(struct grep_source *gs)
1874 {
1875         switch (gs->type) {
1876         case GREP_SOURCE_FILE:
1877         case GREP_SOURCE_OID:
1878                 FREE_AND_NULL(gs->buf);
1879                 gs->size = 0;
1880                 break;
1881         case GREP_SOURCE_BUF:
1882                 /* leave user-provided buf intact */
1883                 break;
1884         }
1885 }
1886
1887 static int grep_source_load_oid(struct grep_source *gs)
1888 {
1889         enum object_type type;
1890
1891         gs->buf = read_object_file(gs->identifier, &type, &gs->size);
1892         if (!gs->buf)
1893                 return error(_("'%s': unable to read %s"),
1894                              gs->name,
1895                              oid_to_hex(gs->identifier));
1896         return 0;
1897 }
1898
1899 static int grep_source_load_file(struct grep_source *gs)
1900 {
1901         const char *filename = gs->identifier;
1902         struct stat st;
1903         char *data;
1904         size_t size;
1905         int i;
1906
1907         if (lstat(filename, &st) < 0) {
1908         err_ret:
1909                 if (errno != ENOENT)
1910                         error_errno(_("failed to stat '%s'"), filename);
1911                 return -1;
1912         }
1913         if (!S_ISREG(st.st_mode))
1914                 return -1;
1915         size = xsize_t(st.st_size);
1916         i = open(filename, O_RDONLY);
1917         if (i < 0)
1918                 goto err_ret;
1919         data = xmallocz(size);
1920         if (st.st_size != read_in_full(i, data, size)) {
1921                 error_errno(_("'%s': short read"), filename);
1922                 close(i);
1923                 free(data);
1924                 return -1;
1925         }
1926         close(i);
1927
1928         gs->buf = data;
1929         gs->size = size;
1930         return 0;
1931 }
1932
1933 static int grep_source_load(struct grep_source *gs)
1934 {
1935         if (gs->buf)
1936                 return 0;
1937
1938         switch (gs->type) {
1939         case GREP_SOURCE_FILE:
1940                 return grep_source_load_file(gs);
1941         case GREP_SOURCE_OID:
1942                 return grep_source_load_oid(gs);
1943         case GREP_SOURCE_BUF:
1944                 return gs->buf ? 0 : -1;
1945         }
1946         BUG("invalid grep_source type to load");
1947 }
1948
1949 void grep_source_load_driver(struct grep_source *gs,
1950                              struct index_state *istate)
1951 {
1952         if (gs->driver)
1953                 return;
1954
1955         grep_attr_lock();
1956         if (gs->path)
1957                 gs->driver = userdiff_find_by_path(istate, gs->path);
1958         if (!gs->driver)
1959                 gs->driver = userdiff_find_by_name("default");
1960         grep_attr_unlock();
1961 }
1962
1963 static int grep_source_is_binary(struct grep_source *gs,
1964                                  struct index_state *istate)
1965 {
1966         grep_source_load_driver(gs, istate);
1967         if (gs->driver->binary != -1)
1968                 return gs->driver->binary;
1969
1970         if (!grep_source_load(gs))
1971                 return buffer_is_binary(gs->buf, gs->size);
1972
1973         return 0;
1974 }