grep.c

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