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