Andrew's git - gitweb.git/blob

870d10cf6969d8b78bb6a2d2ea5262c1ddef0f62
   1#include "cache.h"
   2#include "grep.h"
   3#include "userdiff.h"
   4#include "xdiff-interface.h"
   5
   6void append_header_grep_pattern(struct grep_opt *opt, enum grep_header_field field, const char *pat)
   7{
   8        struct grep_pat *p = xcalloc(1, sizeof(*p));
   9        p->pattern = pat;
  10        p->patternlen = strlen(pat);
  11        p->origin = "header";
  12        p->no = 0;
  13        p->token = GREP_PATTERN_HEAD;
  14        p->field = field;
  15        *opt->header_tail = p;
  16        opt->header_tail = &p->next;
  17        p->next = NULL;
  18}
  19
  20void append_grep_pattern(struct grep_opt *opt, const char *pat,
  21                         const char *origin, int no, enum grep_pat_token t)
  22{
  23        append_grep_pat(opt, pat, strlen(pat), origin, no, t);
  24}
  25
  26void append_grep_pat(struct grep_opt *opt, const char *pat, size_t patlen,
  27                     const char *origin, int no, enum grep_pat_token t)
  28{
  29        struct grep_pat *p = xcalloc(1, sizeof(*p));
  30        p->pattern = pat;
  31        p->patternlen = patlen;
  32        p->origin = origin;
  33        p->no = no;
  34        p->token = t;
  35        *opt->pattern_tail = p;
  36        opt->pattern_tail = &p->next;
  37        p->next = NULL;
  38}
  39
  40struct grep_opt *grep_opt_dup(const struct grep_opt *opt)
  41{
  42        struct grep_pat *pat;
  43        struct grep_opt *ret = xmalloc(sizeof(struct grep_opt));
  44        *ret = *opt;
  45
  46        ret->pattern_list = NULL;
  47        ret->pattern_tail = &ret->pattern_list;
  48
  49        for(pat = opt->pattern_list; pat != NULL; pat = pat->next)
  50        {
  51                if(pat->token == GREP_PATTERN_HEAD)
  52                        append_header_grep_pattern(ret, pat->field,
  53                                                   pat->pattern);
  54                else
  55                        append_grep_pat(ret, pat->pattern, pat->patternlen,
  56                                        pat->origin, pat->no, pat->token);
  57        }
  58
  59        return ret;
  60}
  61
  62static NORETURN void compile_regexp_failed(const struct grep_pat *p,
  63                const char *error)
  64{
  65        char where[1024];
  66
  67        if (p->no)
  68                sprintf(where, "In '%s' at %d, ", p->origin, p->no);
  69        else if (p->origin)
  70                sprintf(where, "%s, ", p->origin);
  71        else
  72                where[0] = 0;
  73
  74        die("%s'%s': %s", where, p->pattern, error);
  75}
  76
  77static void compile_regexp(struct grep_pat *p, struct grep_opt *opt)
  78{
  79        int err;
  80
  81        p->word_regexp = opt->word_regexp;
  82        p->ignore_case = opt->ignore_case;
  83        p->fixed = opt->fixed;
  84
  85        if (p->fixed)
  86                return;
  87
  88        err = regcomp(&p->regexp, p->pattern, opt->regflags);
  89        if (err) {
  90                char errbuf[1024];
  91                regerror(err, &p->regexp, errbuf, 1024);
  92                regfree(&p->regexp);
  93                compile_regexp_failed(p, errbuf);
  94        }
  95}
  96
  97static struct grep_expr *compile_pattern_or(struct grep_pat **);
  98static struct grep_expr *compile_pattern_atom(struct grep_pat **list)
  99{
 100        struct grep_pat *p;
 101        struct grep_expr *x;
 102
 103        p = *list;
 104        if (!p)
 105                return NULL;
 106        switch (p->token) {
 107        case GREP_PATTERN: /* atom */
 108        case GREP_PATTERN_HEAD:
 109        case GREP_PATTERN_BODY:
 110                x = xcalloc(1, sizeof (struct grep_expr));
 111                x->node = GREP_NODE_ATOM;
 112                x->u.atom = p;
 113                *list = p->next;
 114                return x;
 115        case GREP_OPEN_PAREN:
 116                *list = p->next;
 117                x = compile_pattern_or(list);
 118                if (!*list || (*list)->token != GREP_CLOSE_PAREN)
 119                        die("unmatched parenthesis");
 120                *list = (*list)->next;
 121                return x;
 122        default:
 123                return NULL;
 124        }
 125}
 126
 127static struct grep_expr *compile_pattern_not(struct grep_pat **list)
 128{
 129        struct grep_pat *p;
 130        struct grep_expr *x;
 131
 132        p = *list;
 133        if (!p)
 134                return NULL;
 135        switch (p->token) {
 136        case GREP_NOT:
 137                if (!p->next)
 138                        die("--not not followed by pattern expression");
 139                *list = p->next;
 140                x = xcalloc(1, sizeof (struct grep_expr));
 141                x->node = GREP_NODE_NOT;
 142                x->u.unary = compile_pattern_not(list);
 143                if (!x->u.unary)
 144                        die("--not followed by non pattern expression");
 145                return x;
 146        default:
 147                return compile_pattern_atom(list);
 148        }
 149}
 150
 151static struct grep_expr *compile_pattern_and(struct grep_pat **list)
 152{
 153        struct grep_pat *p;
 154        struct grep_expr *x, *y, *z;
 155
 156        x = compile_pattern_not(list);
 157        p = *list;
 158        if (p && p->token == GREP_AND) {
 159                if (!p->next)
 160                        die("--and not followed by pattern expression");
 161                *list = p->next;
 162                y = compile_pattern_and(list);
 163                if (!y)
 164                        die("--and not followed by pattern expression");
 165                z = xcalloc(1, sizeof (struct grep_expr));
 166                z->node = GREP_NODE_AND;
 167                z->u.binary.left = x;
 168                z->u.binary.right = y;
 169                return z;
 170        }
 171        return x;
 172}
 173
 174static struct grep_expr *compile_pattern_or(struct grep_pat **list)
 175{
 176        struct grep_pat *p;
 177        struct grep_expr *x, *y, *z;
 178
 179        x = compile_pattern_and(list);
 180        p = *list;
 181        if (x && p && p->token != GREP_CLOSE_PAREN) {
 182                y = compile_pattern_or(list);
 183                if (!y)
 184                        die("not a pattern expression %s", p->pattern);
 185                z = xcalloc(1, sizeof (struct grep_expr));
 186                z->node = GREP_NODE_OR;
 187                z->u.binary.left = x;
 188                z->u.binary.right = y;
 189                return z;
 190        }
 191        return x;
 192}
 193
 194static struct grep_expr *compile_pattern_expr(struct grep_pat **list)
 195{
 196        return compile_pattern_or(list);
 197}
 198
 199static struct grep_expr *grep_true_expr(void)
 200{
 201        struct grep_expr *z = xcalloc(1, sizeof(*z));
 202        z->node = GREP_NODE_TRUE;
 203        return z;
 204}
 205
 206static struct grep_expr *grep_or_expr(struct grep_expr *left, struct grep_expr *right)
 207{
 208        struct grep_expr *z = xcalloc(1, sizeof(*z));
 209        z->node = GREP_NODE_OR;
 210        z->u.binary.left = left;
 211        z->u.binary.right = right;
 212        return z;
 213}
 214
 215static struct grep_expr *prep_header_patterns(struct grep_opt *opt)
 216{
 217        struct grep_pat *p;
 218        struct grep_expr *header_expr;
 219        struct grep_expr *(header_group[GREP_HEADER_FIELD_MAX]);
 220        enum grep_header_field fld;
 221
 222        if (!opt->header_list)
 223                return NULL;
 224        p = opt->header_list;
 225        for (p = opt->header_list; p; p = p->next) {
 226                if (p->token != GREP_PATTERN_HEAD)
 227                        die("bug: a non-header pattern in grep header list.");
 228                if (p->field < 0 || GREP_HEADER_FIELD_MAX <= p->field)
 229                        die("bug: unknown header field %d", p->field);
 230                compile_regexp(p, opt);
 231        }
 232
 233        for (fld = 0; fld < GREP_HEADER_FIELD_MAX; fld++)
 234                header_group[fld] = NULL;
 235
 236        for (p = opt->header_list; p; p = p->next) {
 237                struct grep_expr *h;
 238                struct grep_pat *pp = p;
 239
 240                h = compile_pattern_atom(&pp);
 241                if (!h || pp != p->next)
 242                        die("bug: malformed header expr");
 243                if (!header_group[p->field]) {
 244                        header_group[p->field] = h;
 245                        continue;
 246                }
 247                header_group[p->field] = grep_or_expr(h, header_group[p->field]);
 248        }
 249
 250        header_expr = NULL;
 251
 252        for (fld = 0; fld < GREP_HEADER_FIELD_MAX; fld++) {
 253                if (!header_group[fld])
 254                        continue;
 255                if (!header_expr)
 256                        header_expr = grep_true_expr();
 257                header_expr = grep_or_expr(header_group[fld], header_expr);
 258        }
 259        return header_expr;
 260}
 261
 262void compile_grep_patterns(struct grep_opt *opt)
 263{
 264        struct grep_pat *p;
 265        struct grep_expr *header_expr = prep_header_patterns(opt);
 266
 267        for (p = opt->pattern_list; p; p = p->next) {
 268                switch (p->token) {
 269                case GREP_PATTERN: /* atom */
 270                case GREP_PATTERN_HEAD:
 271                case GREP_PATTERN_BODY:
 272                        compile_regexp(p, opt);
 273                        break;
 274                default:
 275                        opt->extended = 1;
 276                        break;
 277                }
 278        }
 279
 280        if (opt->all_match || header_expr)
 281                opt->extended = 1;
 282        else if (!opt->extended)
 283                return;
 284
 285        p = opt->pattern_list;
 286        if (p)
 287                opt->pattern_expression = compile_pattern_expr(&p);
 288        if (p)
 289                die("incomplete pattern expression: %s", p->pattern);
 290
 291        if (!header_expr)
 292                return;
 293
 294        if (!opt->pattern_expression)
 295                opt->pattern_expression = header_expr;
 296        else
 297                opt->pattern_expression = grep_or_expr(opt->pattern_expression,
 298                                                       header_expr);
 299        opt->all_match = 1;
 300}
 301
 302static void free_pattern_expr(struct grep_expr *x)
 303{
 304        switch (x->node) {
 305        case GREP_NODE_TRUE:
 306        case GREP_NODE_ATOM:
 307                break;
 308        case GREP_NODE_NOT:
 309                free_pattern_expr(x->u.unary);
 310                break;
 311        case GREP_NODE_AND:
 312        case GREP_NODE_OR:
 313                free_pattern_expr(x->u.binary.left);
 314                free_pattern_expr(x->u.binary.right);
 315                break;
 316        }
 317        free(x);
 318}
 319
 320void free_grep_patterns(struct grep_opt *opt)
 321{
 322        struct grep_pat *p, *n;
 323
 324        for (p = opt->pattern_list; p; p = n) {
 325                n = p->next;
 326                switch (p->token) {
 327                case GREP_PATTERN: /* atom */
 328                case GREP_PATTERN_HEAD:
 329                case GREP_PATTERN_BODY:
 330                        regfree(&p->regexp);
 331                        break;
 332                default:
 333                        break;
 334                }
 335                free(p);
 336        }
 337
 338        if (!opt->extended)
 339                return;
 340        free_pattern_expr(opt->pattern_expression);
 341}
 342
 343static char *end_of_line(char *cp, unsigned long *left)
 344{
 345        unsigned long l = *left;
 346        while (l && *cp != '\n') {
 347                l--;
 348                cp++;
 349        }
 350        *left = l;
 351        return cp;
 352}
 353
 354static int word_char(char ch)
 355{
 356        return isalnum(ch) || ch == '_';
 357}
 358
 359static void output_color(struct grep_opt *opt, const void *data, size_t size,
 360                         const char *color)
 361{
 362        if (opt->color && color && color[0]) {
 363                opt->output(opt, color, strlen(color));
 364                opt->output(opt, data, size);
 365                opt->output(opt, GIT_COLOR_RESET, strlen(GIT_COLOR_RESET));
 366        } else
 367                opt->output(opt, data, size);
 368}
 369
 370static void output_sep(struct grep_opt *opt, char sign)
 371{
 372        if (opt->null_following_name)
 373                opt->output(opt, "\0", 1);
 374        else
 375                output_color(opt, &sign, 1, opt->color_sep);
 376}
 377
 378static void show_name(struct grep_opt *opt, const char *name)
 379{
 380        output_color(opt, name, strlen(name), opt->color_filename);
 381        opt->output(opt, opt->null_following_name ? "\0" : "\n", 1);
 382}
 383
 384static int fixmatch(struct grep_pat *p, char *line, char *eol,
 385                    regmatch_t *match)
 386{
 387        char *hit;
 388
 389        if (p->ignore_case) {
 390                char *s = line;
 391                do {
 392                        hit = strcasestr(s, p->pattern);
 393                        if (hit)
 394                                break;
 395                        s += strlen(s) + 1;
 396                } while (s < eol);
 397        } else
 398                hit = memmem(line, eol - line, p->pattern, p->patternlen);
 399
 400        if (!hit) {
 401                match->rm_so = match->rm_eo = -1;
 402                return REG_NOMATCH;
 403        }
 404        else {
 405                match->rm_so = hit - line;
 406                match->rm_eo = match->rm_so + p->patternlen;
 407                return 0;
 408        }
 409}
 410
 411static int regmatch(const regex_t *preg, char *line, char *eol,
 412                    regmatch_t *match, int eflags)
 413{
 414#ifdef REG_STARTEND
 415        match->rm_so = 0;
 416        match->rm_eo = eol - line;
 417        eflags |= REG_STARTEND;
 418#endif
 419        return regexec(preg, line, 1, match, eflags);
 420}
 421
 422static int patmatch(struct grep_pat *p, char *line, char *eol,
 423                    regmatch_t *match, int eflags)
 424{
 425        int hit;
 426
 427        if (p->fixed)
 428                hit = !fixmatch(p, line, eol, match);
 429        else
 430                hit = !regmatch(&p->regexp, line, eol, match, eflags);
 431
 432        return hit;
 433}
 434
 435static int strip_timestamp(char *bol, char **eol_p)
 436{
 437        char *eol = *eol_p;
 438        int ch;
 439
 440        while (bol < --eol) {
 441                if (*eol != '>')
 442                        continue;
 443                *eol_p = ++eol;
 444                ch = *eol;
 445                *eol = '\0';
 446                return ch;
 447        }
 448        return 0;
 449}
 450
 451static struct {
 452        const char *field;
 453        size_t len;
 454} header_field[] = {
 455        { "author ", 7 },
 456        { "committer ", 10 },
 457};
 458
 459static int match_one_pattern(struct grep_pat *p, char *bol, char *eol,
 460                             enum grep_context ctx,
 461                             regmatch_t *pmatch, int eflags)
 462{
 463        int hit = 0;
 464        int saved_ch = 0;
 465        const char *start = bol;
 466
 467        if ((p->token != GREP_PATTERN) &&
 468            ((p->token == GREP_PATTERN_HEAD) != (ctx == GREP_CONTEXT_HEAD)))
 469                return 0;
 470
 471        if (p->token == GREP_PATTERN_HEAD) {
 472                const char *field;
 473                size_t len;
 474                assert(p->field < ARRAY_SIZE(header_field));
 475                field = header_field[p->field].field;
 476                len = header_field[p->field].len;
 477                if (strncmp(bol, field, len))
 478                        return 0;
 479                bol += len;
 480                saved_ch = strip_timestamp(bol, &eol);
 481        }
 482
 483 again:
 484        hit = patmatch(p, bol, eol, pmatch, eflags);
 485
 486        if (hit && p->word_regexp) {
 487                if ((pmatch[0].rm_so < 0) ||
 488                    (eol - bol) < pmatch[0].rm_so ||
 489                    (pmatch[0].rm_eo < 0) ||
 490                    (eol - bol) < pmatch[0].rm_eo)
 491                        die("regexp returned nonsense");
 492
 493                /* Match beginning must be either beginning of the
 494                 * line, or at word boundary (i.e. the last char must
 495                 * not be a word char).  Similarly, match end must be
 496                 * either end of the line, or at word boundary
 497                 * (i.e. the next char must not be a word char).
 498                 */
 499                if ( ((pmatch[0].rm_so == 0) ||
 500                      !word_char(bol[pmatch[0].rm_so-1])) &&
 501                     ((pmatch[0].rm_eo == (eol-bol)) ||
 502                      !word_char(bol[pmatch[0].rm_eo])) )
 503                        ;
 504                else
 505                        hit = 0;
 506
 507                /* Words consist of at least one character. */
 508                if (pmatch->rm_so == pmatch->rm_eo)
 509                        hit = 0;
 510
 511                if (!hit && pmatch[0].rm_so + bol + 1 < eol) {
 512                        /* There could be more than one match on the
 513                         * line, and the first match might not be
 514                         * strict word match.  But later ones could be!
 515                         * Forward to the next possible start, i.e. the
 516                         * next position following a non-word char.
 517                         */
 518                        bol = pmatch[0].rm_so + bol + 1;
 519                        while (word_char(bol[-1]) && bol < eol)
 520                                bol++;
 521                        eflags |= REG_NOTBOL;
 522                        if (bol < eol)
 523                                goto again;
 524                }
 525        }
 526        if (p->token == GREP_PATTERN_HEAD && saved_ch)
 527                *eol = saved_ch;
 528        if (hit) {
 529                pmatch[0].rm_so += bol - start;
 530                pmatch[0].rm_eo += bol - start;
 531        }
 532        return hit;
 533}
 534
 535static int match_expr_eval(struct grep_expr *x, char *bol, char *eol,
 536                           enum grep_context ctx, int collect_hits)
 537{
 538        int h = 0;
 539        regmatch_t match;
 540
 541        if (!x)
 542                die("Not a valid grep expression");
 543        switch (x->node) {
 544        case GREP_NODE_TRUE:
 545                h = 1;
 546                break;
 547        case GREP_NODE_ATOM:
 548                h = match_one_pattern(x->u.atom, bol, eol, ctx, &match, 0);
 549                break;
 550        case GREP_NODE_NOT:
 551                h = !match_expr_eval(x->u.unary, bol, eol, ctx, 0);
 552                break;
 553        case GREP_NODE_AND:
 554                if (!match_expr_eval(x->u.binary.left, bol, eol, ctx, 0))
 555                        return 0;
 556                h = match_expr_eval(x->u.binary.right, bol, eol, ctx, 0);
 557                break;
 558        case GREP_NODE_OR:
 559                if (!collect_hits)
 560                        return (match_expr_eval(x->u.binary.left,
 561                                                bol, eol, ctx, 0) ||
 562                                match_expr_eval(x->u.binary.right,
 563                                                bol, eol, ctx, 0));
 564                h = match_expr_eval(x->u.binary.left, bol, eol, ctx, 0);
 565                x->u.binary.left->hit |= h;
 566                h |= match_expr_eval(x->u.binary.right, bol, eol, ctx, 1);
 567                break;
 568        default:
 569                die("Unexpected node type (internal error) %d", x->node);
 570        }
 571        if (collect_hits)
 572                x->hit |= h;
 573        return h;
 574}
 575
 576static int match_expr(struct grep_opt *opt, char *bol, char *eol,
 577                      enum grep_context ctx, int collect_hits)
 578{
 579        struct grep_expr *x = opt->pattern_expression;
 580        return match_expr_eval(x, bol, eol, ctx, collect_hits);
 581}
 582
 583static int match_line(struct grep_opt *opt, char *bol, char *eol,
 584                      enum grep_context ctx, int collect_hits)
 585{
 586        struct grep_pat *p;
 587        regmatch_t match;
 588
 589        if (opt->extended)
 590                return match_expr(opt, bol, eol, ctx, collect_hits);
 591
 592        /* we do not call with collect_hits without being extended */
 593        for (p = opt->pattern_list; p; p = p->next) {
 594                if (match_one_pattern(p, bol, eol, ctx, &match, 0))
 595                        return 1;
 596        }
 597        return 0;
 598}
 599
 600static int match_next_pattern(struct grep_pat *p, char *bol, char *eol,
 601                              enum grep_context ctx,
 602                              regmatch_t *pmatch, int eflags)
 603{
 604        regmatch_t match;
 605
 606        if (!match_one_pattern(p, bol, eol, ctx, &match, eflags))
 607                return 0;
 608        if (match.rm_so < 0 || match.rm_eo < 0)
 609                return 0;
 610        if (pmatch->rm_so >= 0 && pmatch->rm_eo >= 0) {
 611                if (match.rm_so > pmatch->rm_so)
 612                        return 1;
 613                if (match.rm_so == pmatch->rm_so && match.rm_eo < pmatch->rm_eo)
 614                        return 1;
 615        }
 616        pmatch->rm_so = match.rm_so;
 617        pmatch->rm_eo = match.rm_eo;
 618        return 1;
 619}
 620
 621static int next_match(struct grep_opt *opt, char *bol, char *eol,
 622                      enum grep_context ctx, regmatch_t *pmatch, int eflags)
 623{
 624        struct grep_pat *p;
 625        int hit = 0;
 626
 627        pmatch->rm_so = pmatch->rm_eo = -1;
 628        if (bol < eol) {
 629                for (p = opt->pattern_list; p; p = p->next) {
 630                        switch (p->token) {
 631                        case GREP_PATTERN: /* atom */
 632                        case GREP_PATTERN_HEAD:
 633                        case GREP_PATTERN_BODY:
 634                                hit |= match_next_pattern(p, bol, eol, ctx,
 635                                                          pmatch, eflags);
 636                                break;
 637                        default:
 638                                break;
 639                        }
 640                }
 641        }
 642        return hit;
 643}
 644
 645static void show_line(struct grep_opt *opt, char *bol, char *eol,
 646                      const char *name, unsigned lno, char sign)
 647{
 648        int rest = eol - bol;
 649        char *line_color = NULL;
 650
 651        if (opt->pre_context || opt->post_context) {
 652                if (opt->last_shown == 0) {
 653                        if (opt->show_hunk_mark) {
 654                                output_color(opt, "--", 2, opt->color_sep);
 655                                opt->output(opt, "\n", 1);
 656                        }
 657                } else if (lno > opt->last_shown + 1) {
 658                        output_color(opt, "--", 2, opt->color_sep);
 659                        opt->output(opt, "\n", 1);
 660                }
 661        }
 662        opt->last_shown = lno;
 663
 664        if (opt->pathname) {
 665                output_color(opt, name, strlen(name), opt->color_filename);
 666                output_sep(opt, sign);
 667        }
 668        if (opt->linenum) {
 669                char buf[32];
 670                snprintf(buf, sizeof(buf), "%d", lno);
 671                output_color(opt, buf, strlen(buf), opt->color_lineno);
 672                output_sep(opt, sign);
 673        }
 674        if (opt->color) {
 675                regmatch_t match;
 676                enum grep_context ctx = GREP_CONTEXT_BODY;
 677                int ch = *eol;
 678                int eflags = 0;
 679
 680                if (sign == ':')
 681                        line_color = opt->color_selected;
 682                else if (sign == '-')
 683                        line_color = opt->color_context;
 684                else if (sign == '=')
 685                        line_color = opt->color_function;
 686                *eol = '\0';
 687                while (next_match(opt, bol, eol, ctx, &match, eflags)) {
 688                        if (match.rm_so == match.rm_eo)
 689                                break;
 690
 691                        output_color(opt, bol, match.rm_so, line_color);
 692                        output_color(opt, bol + match.rm_so,
 693                                     match.rm_eo - match.rm_so,
 694                                     opt->color_match);
 695                        bol += match.rm_eo;
 696                        rest -= match.rm_eo;
 697                        eflags = REG_NOTBOL;
 698                }
 699                *eol = ch;
 700        }
 701        output_color(opt, bol, rest, line_color);
 702        opt->output(opt, "\n", 1);
 703}
 704
 705static int match_funcname(struct grep_opt *opt, char *bol, char *eol)
 706{
 707        xdemitconf_t *xecfg = opt->priv;
 708        if (xecfg && xecfg->find_func) {
 709                char buf[1];
 710                return xecfg->find_func(bol, eol - bol, buf, 1,
 711                                        xecfg->find_func_priv) >= 0;
 712        }
 713
 714        if (bol == eol)
 715                return 0;
 716        if (isalpha(*bol) || *bol == '_' || *bol == '$')
 717                return 1;
 718        return 0;
 719}
 720
 721static void show_funcname_line(struct grep_opt *opt, const char *name,
 722                               char *buf, char *bol, unsigned lno)
 723{
 724        while (bol > buf) {
 725                char *eol = --bol;
 726
 727                while (bol > buf && bol[-1] != '\n')
 728                        bol--;
 729                lno--;
 730
 731                if (lno <= opt->last_shown)
 732                        break;
 733
 734                if (match_funcname(opt, bol, eol)) {
 735                        show_line(opt, bol, eol, name, lno, '=');
 736                        break;
 737                }
 738        }
 739}
 740
 741static void show_pre_context(struct grep_opt *opt, const char *name, char *buf,
 742                             char *bol, unsigned lno)
 743{
 744        unsigned cur = lno, from = 1, funcname_lno = 0;
 745        int funcname_needed = opt->funcname;
 746
 747        if (opt->pre_context < lno)
 748                from = lno - opt->pre_context;
 749        if (from <= opt->last_shown)
 750                from = opt->last_shown + 1;
 751
 752        /* Rewind. */
 753        while (bol > buf && cur > from) {
 754                char *eol = --bol;
 755
 756                while (bol > buf && bol[-1] != '\n')
 757                        bol--;
 758                cur--;
 759                if (funcname_needed && match_funcname(opt, bol, eol)) {
 760                        funcname_lno = cur;
 761                        funcname_needed = 0;
 762                }
 763        }
 764
 765        /* We need to look even further back to find a function signature. */
 766        if (opt->funcname && funcname_needed)
 767                show_funcname_line(opt, name, buf, bol, cur);
 768
 769        /* Back forward. */
 770        while (cur < lno) {
 771                char *eol = bol, sign = (cur == funcname_lno) ? '=' : '-';
 772
 773                while (*eol != '\n')
 774                        eol++;
 775                show_line(opt, bol, eol, name, cur, sign);
 776                bol = eol + 1;
 777                cur++;
 778        }
 779}
 780
 781static int should_lookahead(struct grep_opt *opt)
 782{
 783        struct grep_pat *p;
 784
 785        if (opt->extended)
 786                return 0; /* punt for too complex stuff */
 787        if (opt->invert)
 788                return 0;
 789        for (p = opt->pattern_list; p; p = p->next) {
 790                if (p->token != GREP_PATTERN)
 791                        return 0; /* punt for "header only" and stuff */
 792        }
 793        return 1;
 794}
 795
 796static int look_ahead(struct grep_opt *opt,
 797                      unsigned long *left_p,
 798                      unsigned *lno_p,
 799                      char **bol_p)
 800{
 801        unsigned lno = *lno_p;
 802        char *bol = *bol_p;
 803        struct grep_pat *p;
 804        char *sp, *last_bol;
 805        regoff_t earliest = -1;
 806
 807        for (p = opt->pattern_list; p; p = p->next) {
 808                int hit;
 809                regmatch_t m;
 810
 811                hit = patmatch(p, bol, bol + *left_p, &m, 0);
 812                if (!hit || m.rm_so < 0 || m.rm_eo < 0)
 813                        continue;
 814                if (earliest < 0 || m.rm_so < earliest)
 815                        earliest = m.rm_so;
 816        }
 817
 818        if (earliest < 0) {
 819                *bol_p = bol + *left_p;
 820                *left_p = 0;
 821                return 1;
 822        }
 823        for (sp = bol + earliest; bol < sp && sp[-1] != '\n'; sp--)
 824                ; /* find the beginning of the line */
 825        last_bol = sp;
 826
 827        for (sp = bol; sp < last_bol; sp++) {
 828                if (*sp == '\n')
 829                        lno++;
 830        }
 831        *left_p -= last_bol - bol;
 832        *bol_p = last_bol;
 833        *lno_p = lno;
 834        return 0;
 835}
 836
 837int grep_threads_ok(const struct grep_opt *opt)
 838{
 839        /* If this condition is true, then we may use the attribute
 840         * machinery in grep_buffer_1. The attribute code is not
 841         * thread safe, so we disable the use of threads.
 842         */
 843        if (opt->funcname && !opt->unmatch_name_only && !opt->status_only &&
 844            !opt->name_only)
 845                return 0;
 846
 847        return 1;
 848}
 849
 850static void std_output(struct grep_opt *opt, const void *buf, size_t size)
 851{
 852        fwrite(buf, size, 1, stdout);
 853}
 854
 855static int grep_buffer_1(struct grep_opt *opt, const char *name,
 856                         char *buf, unsigned long size, int collect_hits)
 857{
 858        char *bol = buf;
 859        unsigned long left = size;
 860        unsigned lno = 1;
 861        unsigned last_hit = 0;
 862        int binary_match_only = 0;
 863        unsigned count = 0;
 864        int try_lookahead = 0;
 865        enum grep_context ctx = GREP_CONTEXT_HEAD;
 866        xdemitconf_t xecfg;
 867
 868        if (!opt->output)
 869                opt->output = std_output;
 870
 871        if (opt->last_shown && (opt->pre_context || opt->post_context) &&
 872            opt->output == std_output)
 873                opt->show_hunk_mark = 1;
 874        opt->last_shown = 0;
 875
 876        switch (opt->binary) {
 877        case GREP_BINARY_DEFAULT:
 878                if (buffer_is_binary(buf, size))
 879                        binary_match_only = 1;
 880                break;
 881        case GREP_BINARY_NOMATCH:
 882                if (buffer_is_binary(buf, size))
 883                        return 0; /* Assume unmatch */
 884                break;
 885        case GREP_BINARY_TEXT:
 886                break;
 887        default:
 888                die("bug: unknown binary handling mode");
 889        }
 890
 891        memset(&xecfg, 0, sizeof(xecfg));
 892        if (opt->funcname && !opt->unmatch_name_only && !opt->status_only &&
 893            !opt->name_only && !binary_match_only && !collect_hits) {
 894                struct userdiff_driver *drv = userdiff_find_by_path(name);
 895                if (drv && drv->funcname.pattern) {
 896                        const struct userdiff_funcname *pe = &drv->funcname;
 897                        xdiff_set_find_func(&xecfg, pe->pattern, pe->cflags);
 898                        opt->priv = &xecfg;
 899                }
 900        }
 901        try_lookahead = should_lookahead(opt);
 902
 903        while (left) {
 904                char *eol, ch;
 905                int hit;
 906
 907                /*
 908                 * look_ahead() skips quickly to the line that possibly
 909                 * has the next hit; don't call it if we need to do
 910                 * something more than just skipping the current line
 911                 * in response to an unmatch for the current line.  E.g.
 912                 * inside a post-context window, we will show the current
 913                 * line as a context around the previous hit when it
 914                 * doesn't hit.
 915                 */
 916                if (try_lookahead
 917                    && !(last_hit
 918                         && lno <= last_hit + opt->post_context)
 919                    && look_ahead(opt, &left, &lno, &bol))
 920                        break;
 921                eol = end_of_line(bol, &left);
 922                ch = *eol;
 923                *eol = 0;
 924
 925                if ((ctx == GREP_CONTEXT_HEAD) && (eol == bol))
 926                        ctx = GREP_CONTEXT_BODY;
 927
 928                hit = match_line(opt, bol, eol, ctx, collect_hits);
 929                *eol = ch;
 930
 931                if (collect_hits)
 932                        goto next_line;
 933
 934                /* "grep -v -e foo -e bla" should list lines
 935                 * that do not have either, so inversion should
 936                 * be done outside.
 937                 */
 938                if (opt->invert)
 939                        hit = !hit;
 940                if (opt->unmatch_name_only) {
 941                        if (hit)
 942                                return 0;
 943                        goto next_line;
 944                }
 945                if (hit) {
 946                        count++;
 947                        if (opt->status_only)
 948                                return 1;
 949                        if (opt->name_only) {
 950                                show_name(opt, name);
 951                                return 1;
 952                        }
 953                        if (opt->count)
 954                                goto next_line;
 955                        if (binary_match_only) {
 956                                opt->output(opt, "Binary file ", 12);
 957                                output_color(opt, name, strlen(name),
 958                                             opt->color_filename);
 959                                opt->output(opt, " matches\n", 9);
 960                                return 1;
 961                        }
 962                        /* Hit at this line.  If we haven't shown the
 963                         * pre-context lines, we would need to show them.
 964                         */
 965                        if (opt->pre_context)
 966                                show_pre_context(opt, name, buf, bol, lno);
 967                        else if (opt->funcname)
 968                                show_funcname_line(opt, name, buf, bol, lno);
 969                        show_line(opt, bol, eol, name, lno, ':');
 970                        last_hit = lno;
 971                }
 972                else if (last_hit &&
 973                         lno <= last_hit + opt->post_context) {
 974                        /* If the last hit is within the post context,
 975                         * we need to show this line.
 976                         */
 977                        show_line(opt, bol, eol, name, lno, '-');
 978                }
 979
 980        next_line:
 981                bol = eol + 1;
 982                if (!left)
 983                        break;
 984                left--;
 985                lno++;
 986        }
 987
 988        if (collect_hits)
 989                return 0;
 990
 991        if (opt->status_only)
 992                return 0;
 993        if (opt->unmatch_name_only) {
 994                /* We did not see any hit, so we want to show this */
 995                show_name(opt, name);
 996                return 1;
 997        }
 998
 999        xdiff_clear_find_func(&xecfg);
1000        opt->priv = NULL;
1001
1002        /* NEEDSWORK:
1003         * The real "grep -c foo *.c" gives many "bar.c:0" lines,
1004         * which feels mostly useless but sometimes useful.  Maybe
1005         * make it another option?  For now suppress them.
1006         */
1007        if (opt->count && count) {
1008                char buf[32];
1009                output_color(opt, name, strlen(name), opt->color_filename);
1010                output_sep(opt, ':');
1011                snprintf(buf, sizeof(buf), "%u\n", count);
1012                opt->output(opt, buf, strlen(buf));
1013                return 1;
1014        }
1015        return !!last_hit;
1016}
1017
1018static void clr_hit_marker(struct grep_expr *x)
1019{
1020        /* All-hit markers are meaningful only at the very top level
1021         * OR node.
1022         */
1023        while (1) {
1024                x->hit = 0;
1025                if (x->node != GREP_NODE_OR)
1026                        return;
1027                x->u.binary.left->hit = 0;
1028                x = x->u.binary.right;
1029        }
1030}
1031
1032static int chk_hit_marker(struct grep_expr *x)
1033{
1034        /* Top level nodes have hit markers.  See if they all are hits */
1035        while (1) {
1036                if (x->node != GREP_NODE_OR)
1037                        return x->hit;
1038                if (!x->u.binary.left->hit)
1039                        return 0;
1040                x = x->u.binary.right;
1041        }
1042}
1043
1044int grep_buffer(struct grep_opt *opt, const char *name, char *buf, unsigned long size)
1045{
1046        /*
1047         * we do not have to do the two-pass grep when we do not check
1048         * buffer-wide "all-match".
1049         */
1050        if (!opt->all_match)
1051                return grep_buffer_1(opt, name, buf, size, 0);
1052
1053        /* Otherwise the toplevel "or" terms hit a bit differently.
1054         * We first clear hit markers from them.
1055         */
1056        clr_hit_marker(opt->pattern_expression);
1057        grep_buffer_1(opt, name, buf, size, 1);
1058
1059        if (!chk_hit_marker(opt->pattern_expression))
1060                return 0;
1061
1062        return grep_buffer_1(opt, name, buf, size, 0);
1063}