Andrew's git / gitweb.git / grep.c
?
grep.con commit Merge git://git.kernel.org/pub/scm/gitk/gitk (d4f6bc8)
   1#include "cache.h"
   2#include "grep.h"
   3#include "xdiff-interface.h"
   4
   5void append_header_grep_pattern(struct grep_opt *opt, enum grep_header_field field, const char *pat)
   6{
   7        struct grep_pat *p = xcalloc(1, sizeof(*p));
   8        p->pattern = pat;
   9        p->origin = "header";
  10        p->no = 0;
  11        p->token = GREP_PATTERN_HEAD;
  12        p->field = field;
  13        *opt->pattern_tail = p;
  14        opt->pattern_tail = &p->next;
  15        p->next = NULL;
  16}
  17
  18void append_grep_pattern(struct grep_opt *opt, const char *pat,
  19                         const char *origin, int no, enum grep_pat_token t)
  20{
  21        struct grep_pat *p = xcalloc(1, sizeof(*p));
  22        p->pattern = pat;
  23        p->origin = origin;
  24        p->no = no;
  25        p->token = t;
  26        *opt->pattern_tail = p;
  27        opt->pattern_tail = &p->next;
  28        p->next = NULL;
  29}
  30
  31static int is_fixed(const char *s)
  32{
  33        while (*s && !is_regex_special(*s))
  34                s++;
  35        return !*s;
  36}
  37
  38static void compile_regexp(struct grep_pat *p, struct grep_opt *opt)
  39{
  40        int err;
  41
  42        p->word_regexp = opt->word_regexp;
  43
  44        if (opt->fixed || is_fixed(p->pattern))
  45                p->fixed = 1;
  46        if (opt->regflags & REG_ICASE)
  47                p->fixed = 0;
  48        if (p->fixed)
  49                return;
  50
  51        err = regcomp(&p->regexp, p->pattern, opt->regflags);
  52        if (err) {
  53                char errbuf[1024];
  54                char where[1024];
  55                if (p->no)
  56                        sprintf(where, "In '%s' at %d, ",
  57                                p->origin, p->no);
  58                else if (p->origin)
  59                        sprintf(where, "%s, ", p->origin);
  60                else
  61                        where[0] = 0;
  62                regerror(err, &p->regexp, errbuf, 1024);
  63                regfree(&p->regexp);
  64                die("%s'%s': %s", where, p->pattern, errbuf);
  65        }
  66}
  67
  68static struct grep_expr *compile_pattern_or(struct grep_pat **);
  69static struct grep_expr *compile_pattern_atom(struct grep_pat **list)
  70{
  71        struct grep_pat *p;
  72        struct grep_expr *x;
  73
  74        p = *list;
  75        if (!p)
  76                return NULL;
  77        switch (p->token) {
  78        case GREP_PATTERN: /* atom */
  79        case GREP_PATTERN_HEAD:
  80        case GREP_PATTERN_BODY:
  81                x = xcalloc(1, sizeof (struct grep_expr));
  82                x->node = GREP_NODE_ATOM;
  83                x->u.atom = p;
  84                *list = p->next;
  85                return x;
  86        case GREP_OPEN_PAREN:
  87                *list = p->next;
  88                x = compile_pattern_or(list);
  89                if (!*list || (*list)->token != GREP_CLOSE_PAREN)
  90                        die("unmatched parenthesis");
  91                *list = (*list)->next;
  92                return x;
  93        default:
  94                return NULL;
  95        }
  96}
  97
  98static struct grep_expr *compile_pattern_not(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_NOT:
 108                if (!p->next)
 109                        die("--not not followed by pattern expression");
 110                *list = p->next;
 111                x = xcalloc(1, sizeof (struct grep_expr));
 112                x->node = GREP_NODE_NOT;
 113                x->u.unary = compile_pattern_not(list);
 114                if (!x->u.unary)
 115                        die("--not followed by non pattern expression");
 116                return x;
 117        default:
 118                return compile_pattern_atom(list);
 119        }
 120}
 121
 122static struct grep_expr *compile_pattern_and(struct grep_pat **list)
 123{
 124        struct grep_pat *p;
 125        struct grep_expr *x, *y, *z;
 126
 127        x = compile_pattern_not(list);
 128        p = *list;
 129        if (p && p->token == GREP_AND) {
 130                if (!p->next)
 131                        die("--and not followed by pattern expression");
 132                *list = p->next;
 133                y = compile_pattern_and(list);
 134                if (!y)
 135                        die("--and not followed by pattern expression");
 136                z = xcalloc(1, sizeof (struct grep_expr));
 137                z->node = GREP_NODE_AND;
 138                z->u.binary.left = x;
 139                z->u.binary.right = y;
 140                return z;
 141        }
 142        return x;
 143}
 144
 145static struct grep_expr *compile_pattern_or(struct grep_pat **list)
 146{
 147        struct grep_pat *p;
 148        struct grep_expr *x, *y, *z;
 149
 150        x = compile_pattern_and(list);
 151        p = *list;
 152        if (x && p && p->token != GREP_CLOSE_PAREN) {
 153                y = compile_pattern_or(list);
 154                if (!y)
 155                        die("not a pattern expression %s", p->pattern);
 156                z = xcalloc(1, sizeof (struct grep_expr));
 157                z->node = GREP_NODE_OR;
 158                z->u.binary.left = x;
 159                z->u.binary.right = y;
 160                return z;
 161        }
 162        return x;
 163}
 164
 165static struct grep_expr *compile_pattern_expr(struct grep_pat **list)
 166{
 167        return compile_pattern_or(list);
 168}
 169
 170void compile_grep_patterns(struct grep_opt *opt)
 171{
 172        struct grep_pat *p;
 173
 174        if (opt->all_match)
 175                opt->extended = 1;
 176
 177        for (p = opt->pattern_list; p; p = p->next) {
 178                switch (p->token) {
 179                case GREP_PATTERN: /* atom */
 180                case GREP_PATTERN_HEAD:
 181                case GREP_PATTERN_BODY:
 182                        compile_regexp(p, opt);
 183                        break;
 184                default:
 185                        opt->extended = 1;
 186                        break;
 187                }
 188        }
 189
 190        if (!opt->extended)
 191                return;
 192
 193        /* Then bundle them up in an expression.
 194         * A classic recursive descent parser would do.
 195         */
 196        p = opt->pattern_list;
 197        if (p)
 198                opt->pattern_expression = compile_pattern_expr(&p);
 199        if (p)
 200                die("incomplete pattern expression: %s", p->pattern);
 201}
 202
 203static void free_pattern_expr(struct grep_expr *x)
 204{
 205        switch (x->node) {
 206        case GREP_NODE_ATOM:
 207                break;
 208        case GREP_NODE_NOT:
 209                free_pattern_expr(x->u.unary);
 210                break;
 211        case GREP_NODE_AND:
 212        case GREP_NODE_OR:
 213                free_pattern_expr(x->u.binary.left);
 214                free_pattern_expr(x->u.binary.right);
 215                break;
 216        }
 217        free(x);
 218}
 219
 220void free_grep_patterns(struct grep_opt *opt)
 221{
 222        struct grep_pat *p, *n;
 223
 224        for (p = opt->pattern_list; p; p = n) {
 225                n = p->next;
 226                switch (p->token) {
 227                case GREP_PATTERN: /* atom */
 228                case GREP_PATTERN_HEAD:
 229                case GREP_PATTERN_BODY:
 230                        regfree(&p->regexp);
 231                        break;
 232                default:
 233                        break;
 234                }
 235                free(p);
 236        }
 237
 238        if (!opt->extended)
 239                return;
 240        free_pattern_expr(opt->pattern_expression);
 241}
 242
 243static char *end_of_line(char *cp, unsigned long *left)
 244{
 245        unsigned long l = *left;
 246        while (l && *cp != '\n') {
 247                l--;
 248                cp++;
 249        }
 250        *left = l;
 251        return cp;
 252}
 253
 254static int word_char(char ch)
 255{
 256        return isalnum(ch) || ch == '_';
 257}
 258
 259static void show_name(struct grep_opt *opt, const char *name)
 260{
 261        printf("%s%c", name, opt->null_following_name ? '\0' : '\n');
 262}
 263
 264static int fixmatch(const char *pattern, char *line, regmatch_t *match)
 265{
 266        char *hit = strstr(line, pattern);
 267        if (!hit) {
 268                match->rm_so = match->rm_eo = -1;
 269                return REG_NOMATCH;
 270        }
 271        else {
 272                match->rm_so = hit - line;
 273                match->rm_eo = match->rm_so + strlen(pattern);
 274                return 0;
 275        }
 276}
 277
 278static int strip_timestamp(char *bol, char **eol_p)
 279{
 280        char *eol = *eol_p;
 281        int ch;
 282
 283        while (bol < --eol) {
 284                if (*eol != '>')
 285                        continue;
 286                *eol_p = ++eol;
 287                ch = *eol;
 288                *eol = '\0';
 289                return ch;
 290        }
 291        return 0;
 292}
 293
 294static struct {
 295        const char *field;
 296        size_t len;
 297} header_field[] = {
 298        { "author ", 7 },
 299        { "committer ", 10 },
 300};
 301
 302static int match_one_pattern(struct grep_pat *p, char *bol, char *eol,
 303                             enum grep_context ctx,
 304                             regmatch_t *pmatch, int eflags)
 305{
 306        int hit = 0;
 307        int saved_ch = 0;
 308        const char *start = bol;
 309
 310        if ((p->token != GREP_PATTERN) &&
 311            ((p->token == GREP_PATTERN_HEAD) != (ctx == GREP_CONTEXT_HEAD)))
 312                return 0;
 313
 314        if (p->token == GREP_PATTERN_HEAD) {
 315                const char *field;
 316                size_t len;
 317                assert(p->field < ARRAY_SIZE(header_field));
 318                field = header_field[p->field].field;
 319                len = header_field[p->field].len;
 320                if (strncmp(bol, field, len))
 321                        return 0;
 322                bol += len;
 323                saved_ch = strip_timestamp(bol, &eol);
 324        }
 325
 326 again:
 327        if (p->fixed)
 328                hit = !fixmatch(p->pattern, bol, pmatch);
 329        else
 330                hit = !regexec(&p->regexp, bol, 1, pmatch, eflags);
 331
 332        if (hit && p->word_regexp) {
 333                if ((pmatch[0].rm_so < 0) ||
 334                    (eol - bol) < pmatch[0].rm_so ||
 335                    (pmatch[0].rm_eo < 0) ||
 336                    (eol - bol) < pmatch[0].rm_eo)
 337                        die("regexp returned nonsense");
 338
 339                /* Match beginning must be either beginning of the
 340                 * line, or at word boundary (i.e. the last char must
 341                 * not be a word char).  Similarly, match end must be
 342                 * either end of the line, or at word boundary
 343                 * (i.e. the next char must not be a word char).
 344                 */
 345                if ( ((pmatch[0].rm_so == 0) ||
 346                      !word_char(bol[pmatch[0].rm_so-1])) &&
 347                     ((pmatch[0].rm_eo == (eol-bol)) ||
 348                      !word_char(bol[pmatch[0].rm_eo])) )
 349                        ;
 350                else
 351                        hit = 0;
 352
 353                /* Words consist of at least one character. */
 354                if (pmatch->rm_so == pmatch->rm_eo)
 355                        hit = 0;
 356
 357                if (!hit && pmatch[0].rm_so + bol + 1 < eol) {
 358                        /* There could be more than one match on the
 359                         * line, and the first match might not be
 360                         * strict word match.  But later ones could be!
 361                         * Forward to the next possible start, i.e. the
 362                         * next position following a non-word char.
 363                         */
 364                        bol = pmatch[0].rm_so + bol + 1;
 365                        while (word_char(bol[-1]) && bol < eol)
 366                                bol++;
 367                        eflags |= REG_NOTBOL;
 368                        if (bol < eol)
 369                                goto again;
 370                }
 371        }
 372        if (p->token == GREP_PATTERN_HEAD && saved_ch)
 373                *eol = saved_ch;
 374        if (hit) {
 375                pmatch[0].rm_so += bol - start;
 376                pmatch[0].rm_eo += bol - start;
 377        }
 378        return hit;
 379}
 380
 381static int match_expr_eval(struct grep_expr *x, char *bol, char *eol,
 382                           enum grep_context ctx, int collect_hits)
 383{
 384        int h = 0;
 385        regmatch_t match;
 386
 387        if (!x)
 388                die("Not a valid grep expression");
 389        switch (x->node) {
 390        case GREP_NODE_ATOM:
 391                h = match_one_pattern(x->u.atom, bol, eol, ctx, &match, 0);
 392                break;
 393        case GREP_NODE_NOT:
 394                h = !match_expr_eval(x->u.unary, bol, eol, ctx, 0);
 395                break;
 396        case GREP_NODE_AND:
 397                if (!match_expr_eval(x->u.binary.left, bol, eol, ctx, 0))
 398                        return 0;
 399                h = match_expr_eval(x->u.binary.right, bol, eol, ctx, 0);
 400                break;
 401        case GREP_NODE_OR:
 402                if (!collect_hits)
 403                        return (match_expr_eval(x->u.binary.left,
 404                                                bol, eol, ctx, 0) ||
 405                                match_expr_eval(x->u.binary.right,
 406                                                bol, eol, ctx, 0));
 407                h = match_expr_eval(x->u.binary.left, bol, eol, ctx, 0);
 408                x->u.binary.left->hit |= h;
 409                h |= match_expr_eval(x->u.binary.right, bol, eol, ctx, 1);
 410                break;
 411        default:
 412                die("Unexpected node type (internal error) %d", x->node);
 413        }
 414        if (collect_hits)
 415                x->hit |= h;
 416        return h;
 417}
 418
 419static int match_expr(struct grep_opt *opt, char *bol, char *eol,
 420                      enum grep_context ctx, int collect_hits)
 421{
 422        struct grep_expr *x = opt->pattern_expression;
 423        return match_expr_eval(x, bol, eol, ctx, collect_hits);
 424}
 425
 426static int match_line(struct grep_opt *opt, char *bol, char *eol,
 427                      enum grep_context ctx, int collect_hits)
 428{
 429        struct grep_pat *p;
 430        regmatch_t match;
 431
 432        if (opt->extended)
 433                return match_expr(opt, bol, eol, ctx, collect_hits);
 434
 435        /* we do not call with collect_hits without being extended */
 436        for (p = opt->pattern_list; p; p = p->next) {
 437                if (match_one_pattern(p, bol, eol, ctx, &match, 0))
 438                        return 1;
 439        }
 440        return 0;
 441}
 442
 443static int match_next_pattern(struct grep_pat *p, char *bol, char *eol,
 444                              enum grep_context ctx,
 445                              regmatch_t *pmatch, int eflags)
 446{
 447        regmatch_t match;
 448
 449        if (!match_one_pattern(p, bol, eol, ctx, &match, eflags))
 450                return 0;
 451        if (match.rm_so < 0 || match.rm_eo < 0)
 452                return 0;
 453        if (pmatch->rm_so >= 0 && pmatch->rm_eo >= 0) {
 454                if (match.rm_so > pmatch->rm_so)
 455                        return 1;
 456                if (match.rm_so == pmatch->rm_so && match.rm_eo < pmatch->rm_eo)
 457                        return 1;
 458        }
 459        pmatch->rm_so = match.rm_so;
 460        pmatch->rm_eo = match.rm_eo;
 461        return 1;
 462}
 463
 464static int next_match(struct grep_opt *opt, char *bol, char *eol,
 465                      enum grep_context ctx, regmatch_t *pmatch, int eflags)
 466{
 467        struct grep_pat *p;
 468        int hit = 0;
 469
 470        pmatch->rm_so = pmatch->rm_eo = -1;
 471        if (bol < eol) {
 472                for (p = opt->pattern_list; p; p = p->next) {
 473                        switch (p->token) {
 474                        case GREP_PATTERN: /* atom */
 475                        case GREP_PATTERN_HEAD:
 476                        case GREP_PATTERN_BODY:
 477                                hit |= match_next_pattern(p, bol, eol, ctx,
 478                                                          pmatch, eflags);
 479                                break;
 480                        default:
 481                                break;
 482                        }
 483                }
 484        }
 485        return hit;
 486}
 487
 488static void show_line(struct grep_opt *opt, char *bol, char *eol,
 489                      const char *name, unsigned lno, char sign)
 490{
 491        int rest = eol - bol;
 492
 493        if (opt->null_following_name)
 494                sign = '\0';
 495        if (opt->pathname)
 496                printf("%s%c", name, sign);
 497        if (opt->linenum)
 498                printf("%d%c", lno, sign);
 499        if (opt->color) {
 500                regmatch_t match;
 501                enum grep_context ctx = GREP_CONTEXT_BODY;
 502                int ch = *eol;
 503                int eflags = 0;
 504
 505                *eol = '\0';
 506                while (next_match(opt, bol, eol, ctx, &match, eflags)) {
 507                        if (match.rm_so == match.rm_eo)
 508                                break;
 509                        printf("%.*s%s%.*s%s",
 510                               (int)match.rm_so, bol,
 511                               opt->color_match,
 512                               (int)(match.rm_eo - match.rm_so), bol + match.rm_so,
 513                               GIT_COLOR_RESET);
 514                        bol += match.rm_eo;
 515                        rest -= match.rm_eo;
 516                        eflags = REG_NOTBOL;
 517                }
 518                *eol = ch;
 519        }
 520        printf("%.*s\n", rest, bol);
 521}
 522
 523static int grep_buffer_1(struct grep_opt *opt, const char *name,
 524                         char *buf, unsigned long size, int collect_hits)
 525{
 526        char *bol = buf;
 527        unsigned long left = size;
 528        unsigned lno = 1;
 529        struct pre_context_line {
 530                char *bol;
 531                char *eol;
 532        } *prev = NULL, *pcl;
 533        unsigned last_hit = 0;
 534        unsigned last_shown = 0;
 535        int binary_match_only = 0;
 536        const char *hunk_mark = "";
 537        unsigned count = 0;
 538        enum grep_context ctx = GREP_CONTEXT_HEAD;
 539
 540        if (buffer_is_binary(buf, size)) {
 541                switch (opt->binary) {
 542                case GREP_BINARY_DEFAULT:
 543                        binary_match_only = 1;
 544                        break;
 545                case GREP_BINARY_NOMATCH:
 546                        return 0; /* Assume unmatch */
 547                        break;
 548                default:
 549                        break;
 550                }
 551        }
 552
 553        if (opt->pre_context)
 554                prev = xcalloc(opt->pre_context, sizeof(*prev));
 555        if (opt->pre_context || opt->post_context)
 556                hunk_mark = "--\n";
 557
 558        while (left) {
 559                char *eol, ch;
 560                int hit;
 561
 562                eol = end_of_line(bol, &left);
 563                ch = *eol;
 564                *eol = 0;
 565
 566                if ((ctx == GREP_CONTEXT_HEAD) && (eol == bol))
 567                        ctx = GREP_CONTEXT_BODY;
 568
 569                hit = match_line(opt, bol, eol, ctx, collect_hits);
 570                *eol = ch;
 571
 572                if (collect_hits)
 573                        goto next_line;
 574
 575                /* "grep -v -e foo -e bla" should list lines
 576                 * that do not have either, so inversion should
 577                 * be done outside.
 578                 */
 579                if (opt->invert)
 580                        hit = !hit;
 581                if (opt->unmatch_name_only) {
 582                        if (hit)
 583                                return 0;
 584                        goto next_line;
 585                }
 586                if (hit) {
 587                        count++;
 588                        if (opt->status_only)
 589                                return 1;
 590                        if (binary_match_only) {
 591                                printf("Binary file %s matches\n", name);
 592                                return 1;
 593                        }
 594                        if (opt->name_only) {
 595                                show_name(opt, name);
 596                                return 1;
 597                        }
 598                        /* Hit at this line.  If we haven't shown the
 599                         * pre-context lines, we would need to show them.
 600                         * When asked to do "count", this still show
 601                         * the context which is nonsense, but the user
 602                         * deserves to get that ;-).
 603                         */
 604                        if (opt->pre_context) {
 605                                unsigned from;
 606                                if (opt->pre_context < lno)
 607                                        from = lno - opt->pre_context;
 608                                else
 609                                        from = 1;
 610                                if (from <= last_shown)
 611                                        from = last_shown + 1;
 612                                if (last_shown && from != last_shown + 1)
 613                                        fputs(hunk_mark, stdout);
 614                                while (from < lno) {
 615                                        pcl = &prev[lno-from-1];
 616                                        show_line(opt, pcl->bol, pcl->eol,
 617                                                  name, from, '-');
 618                                        from++;
 619                                }
 620                                last_shown = lno-1;
 621                        }
 622                        if (last_shown && lno != last_shown + 1)
 623                                fputs(hunk_mark, stdout);
 624                        if (!opt->count)
 625                                show_line(opt, bol, eol, name, lno, ':');
 626                        last_shown = last_hit = lno;
 627                }
 628                else if (last_hit &&
 629                         lno <= last_hit + opt->post_context) {
 630                        /* If the last hit is within the post context,
 631                         * we need to show this line.
 632                         */
 633                        if (last_shown && lno != last_shown + 1)
 634                                fputs(hunk_mark, stdout);
 635                        show_line(opt, bol, eol, name, lno, '-');
 636                        last_shown = lno;
 637                }
 638                if (opt->pre_context) {
 639                        memmove(prev+1, prev,
 640                                (opt->pre_context-1) * sizeof(*prev));
 641                        prev->bol = bol;
 642                        prev->eol = eol;
 643                }
 644
 645        next_line:
 646                bol = eol + 1;
 647                if (!left)
 648                        break;
 649                left--;
 650                lno++;
 651        }
 652
 653        free(prev);
 654        if (collect_hits)
 655                return 0;
 656
 657        if (opt->status_only)
 658                return 0;
 659        if (opt->unmatch_name_only) {
 660                /* We did not see any hit, so we want to show this */
 661                show_name(opt, name);
 662                return 1;
 663        }
 664
 665        /* NEEDSWORK:
 666         * The real "grep -c foo *.c" gives many "bar.c:0" lines,
 667         * which feels mostly useless but sometimes useful.  Maybe
 668         * make it another option?  For now suppress them.
 669         */
 670        if (opt->count && count)
 671                printf("%s%c%u\n", name,
 672                       opt->null_following_name ? '\0' : ':', count);
 673        return !!last_hit;
 674}
 675
 676static void clr_hit_marker(struct grep_expr *x)
 677{
 678        /* All-hit markers are meaningful only at the very top level
 679         * OR node.
 680         */
 681        while (1) {
 682                x->hit = 0;
 683                if (x->node != GREP_NODE_OR)
 684                        return;
 685                x->u.binary.left->hit = 0;
 686                x = x->u.binary.right;
 687        }
 688}
 689
 690static int chk_hit_marker(struct grep_expr *x)
 691{
 692        /* Top level nodes have hit markers.  See if they all are hits */
 693        while (1) {
 694                if (x->node != GREP_NODE_OR)
 695                        return x->hit;
 696                if (!x->u.binary.left->hit)
 697                        return 0;
 698                x = x->u.binary.right;
 699        }
 700}
 701
 702int grep_buffer(struct grep_opt *opt, const char *name, char *buf, unsigned long size)
 703{
 704        /*
 705         * we do not have to do the two-pass grep when we do not check
 706         * buffer-wide "all-match".
 707         */
 708        if (!opt->all_match)
 709                return grep_buffer_1(opt, name, buf, size, 0);
 710
 711        /* Otherwise the toplevel "or" terms hit a bit differently.
 712         * We first clear hit markers from them.
 713         */
 714        clr_hit_marker(opt->pattern_expression);
 715        grep_buffer_1(opt, name, buf, size, 1);
 716
 717        if (!chk_hit_marker(opt->pattern_expression))
 718                return 0;
 719
 720        return grep_buffer_1(opt, name, buf, size, 0);
 721}