Andrew's git / gitweb.git / grep.c
?
grep.con commit Merge branch 'maint-1.6.1' into maint-1.6.2 (c503467)
   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        if (opt->fixed || is_fixed(p->pattern))
  43                p->fixed = 1;
  44        if (opt->regflags & REG_ICASE)
  45                p->fixed = 0;
  46        if (p->fixed)
  47                return;
  48
  49        err = regcomp(&p->regexp, p->pattern, opt->regflags);
  50        if (err) {
  51                char errbuf[1024];
  52                char where[1024];
  53                if (p->no)
  54                        sprintf(where, "In '%s' at %d, ",
  55                                p->origin, p->no);
  56                else if (p->origin)
  57                        sprintf(where, "%s, ", p->origin);
  58                else
  59                        where[0] = 0;
  60                regerror(err, &p->regexp, errbuf, 1024);
  61                regfree(&p->regexp);
  62                die("%s'%s': %s", where, p->pattern, errbuf);
  63        }
  64}
  65
  66static struct grep_expr *compile_pattern_or(struct grep_pat **);
  67static struct grep_expr *compile_pattern_atom(struct grep_pat **list)
  68{
  69        struct grep_pat *p;
  70        struct grep_expr *x;
  71
  72        p = *list;
  73        if (!p)
  74                return NULL;
  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 (!*list || (*list)->token != GREP_CLOSE_PAREN)
  88                        die("unmatched parenthesis");
  89                *list = (*list)->next;
  90                return x;
  91        default:
  92                return NULL;
  93        }
  94}
  95
  96static struct grep_expr *compile_pattern_not(struct grep_pat **list)
  97{
  98        struct grep_pat *p;
  99        struct grep_expr *x;
 100
 101        p = *list;
 102        if (!p)
 103                return NULL;
 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        opt->pattern_expression = compile_pattern_expr(&p);
 196        if (p)
 197                die("incomplete pattern expression: %s", p->pattern);
 198}
 199
 200static void free_pattern_expr(struct grep_expr *x)
 201{
 202        switch (x->node) {
 203        case GREP_NODE_ATOM:
 204                break;
 205        case GREP_NODE_NOT:
 206                free_pattern_expr(x->u.unary);
 207                break;
 208        case GREP_NODE_AND:
 209        case GREP_NODE_OR:
 210                free_pattern_expr(x->u.binary.left);
 211                free_pattern_expr(x->u.binary.right);
 212                break;
 213        }
 214        free(x);
 215}
 216
 217void free_grep_patterns(struct grep_opt *opt)
 218{
 219        struct grep_pat *p, *n;
 220
 221        for (p = opt->pattern_list; p; p = n) {
 222                n = p->next;
 223                switch (p->token) {
 224                case GREP_PATTERN: /* atom */
 225                case GREP_PATTERN_HEAD:
 226                case GREP_PATTERN_BODY:
 227                        regfree(&p->regexp);
 228                        break;
 229                default:
 230                        break;
 231                }
 232                free(p);
 233        }
 234
 235        if (!opt->extended)
 236                return;
 237        free_pattern_expr(opt->pattern_expression);
 238}
 239
 240static char *end_of_line(char *cp, unsigned long *left)
 241{
 242        unsigned long l = *left;
 243        while (l && *cp != '\n') {
 244                l--;
 245                cp++;
 246        }
 247        *left = l;
 248        return cp;
 249}
 250
 251static int word_char(char ch)
 252{
 253        return isalnum(ch) || ch == '_';
 254}
 255
 256static void show_line(struct grep_opt *opt, const char *bol, const char *eol,
 257                      const char *name, unsigned lno, char sign)
 258{
 259        if (opt->null_following_name)
 260                sign = '\0';
 261        if (opt->pathname)
 262                printf("%s%c", name, sign);
 263        if (opt->linenum)
 264                printf("%d%c", lno, sign);
 265        printf("%.*s\n", (int)(eol-bol), bol);
 266}
 267
 268static void show_name(struct grep_opt *opt, const char *name)
 269{
 270        printf("%s%c", name, opt->null_following_name ? '\0' : '\n');
 271}
 272
 273static int fixmatch(const char *pattern, char *line, regmatch_t *match)
 274{
 275        char *hit = strstr(line, pattern);
 276        if (!hit) {
 277                match->rm_so = match->rm_eo = -1;
 278                return REG_NOMATCH;
 279        }
 280        else {
 281                match->rm_so = hit - line;
 282                match->rm_eo = match->rm_so + strlen(pattern);
 283                return 0;
 284        }
 285}
 286
 287static int strip_timestamp(char *bol, char **eol_p)
 288{
 289        char *eol = *eol_p;
 290        int ch;
 291
 292        while (bol < --eol) {
 293                if (*eol != '>')
 294                        continue;
 295                *eol_p = ++eol;
 296                ch = *eol;
 297                *eol = '\0';
 298                return ch;
 299        }
 300        return 0;
 301}
 302
 303static struct {
 304        const char *field;
 305        size_t len;
 306} header_field[] = {
 307        { "author ", 7 },
 308        { "committer ", 10 },
 309};
 310
 311static int match_one_pattern(struct grep_opt *opt, struct grep_pat *p, char *bol, char *eol, enum grep_context ctx)
 312{
 313        int hit = 0;
 314        int saved_ch = 0;
 315        regmatch_t pmatch[10];
 316
 317        if ((p->token != GREP_PATTERN) &&
 318            ((p->token == GREP_PATTERN_HEAD) != (ctx == GREP_CONTEXT_HEAD)))
 319                return 0;
 320
 321        if (p->token == GREP_PATTERN_HEAD) {
 322                const char *field;
 323                size_t len;
 324                assert(p->field < ARRAY_SIZE(header_field));
 325                field = header_field[p->field].field;
 326                len = header_field[p->field].len;
 327                if (strncmp(bol, field, len))
 328                        return 0;
 329                bol += len;
 330                saved_ch = strip_timestamp(bol, &eol);
 331        }
 332
 333 again:
 334        if (!p->fixed) {
 335                regex_t *exp = &p->regexp;
 336                hit = !regexec(exp, bol, ARRAY_SIZE(pmatch),
 337                               pmatch, 0);
 338        }
 339        else {
 340                hit = !fixmatch(p->pattern, bol, pmatch);
 341        }
 342
 343        if (hit && opt->word_regexp) {
 344                if ((pmatch[0].rm_so < 0) ||
 345                    (eol - bol) <= pmatch[0].rm_so ||
 346                    (pmatch[0].rm_eo < 0) ||
 347                    (eol - bol) < pmatch[0].rm_eo)
 348                        die("regexp returned nonsense");
 349
 350                /* Match beginning must be either beginning of the
 351                 * line, or at word boundary (i.e. the last char must
 352                 * not be a word char).  Similarly, match end must be
 353                 * either end of the line, or at word boundary
 354                 * (i.e. the next char must not be a word char).
 355                 */
 356                if ( ((pmatch[0].rm_so == 0) ||
 357                      !word_char(bol[pmatch[0].rm_so-1])) &&
 358                     ((pmatch[0].rm_eo == (eol-bol)) ||
 359                      !word_char(bol[pmatch[0].rm_eo])) )
 360                        ;
 361                else
 362                        hit = 0;
 363
 364                if (!hit && pmatch[0].rm_so + bol + 1 < eol) {
 365                        /* There could be more than one match on the
 366                         * line, and the first match might not be
 367                         * strict word match.  But later ones could be!
 368                         * Forward to the next possible start, i.e. the
 369                         * next position following a non-word char.
 370                         */
 371                        bol = pmatch[0].rm_so + bol + 1;
 372                        while (word_char(bol[-1]) && bol < eol)
 373                                bol++;
 374                        if (bol < eol)
 375                                goto again;
 376                }
 377        }
 378        if (p->token == GREP_PATTERN_HEAD && saved_ch)
 379                *eol = saved_ch;
 380        return hit;
 381}
 382
 383static int match_expr_eval(struct grep_opt *o,
 384                           struct grep_expr *x,
 385                           char *bol, char *eol,
 386                           enum grep_context ctx,
 387                           int collect_hits)
 388{
 389        int h = 0;
 390
 391        if (!x)
 392                die("Not a valid grep expression");
 393        switch (x->node) {
 394        case GREP_NODE_ATOM:
 395                h = match_one_pattern(o, x->u.atom, bol, eol, ctx);
 396                break;
 397        case GREP_NODE_NOT:
 398                h = !match_expr_eval(o, x->u.unary, bol, eol, ctx, 0);
 399                break;
 400        case GREP_NODE_AND:
 401                if (!collect_hits)
 402                        return (match_expr_eval(o, x->u.binary.left,
 403                                                bol, eol, ctx, 0) &&
 404                                match_expr_eval(o, x->u.binary.right,
 405                                                bol, eol, ctx, 0));
 406                h = match_expr_eval(o, x->u.binary.left, bol, eol, ctx, 0);
 407                h &= match_expr_eval(o, x->u.binary.right, bol, eol, ctx, 0);
 408                break;
 409        case GREP_NODE_OR:
 410                if (!collect_hits)
 411                        return (match_expr_eval(o, x->u.binary.left,
 412                                                bol, eol, ctx, 0) ||
 413                                match_expr_eval(o, x->u.binary.right,
 414                                                bol, eol, ctx, 0));
 415                h = match_expr_eval(o, x->u.binary.left, bol, eol, ctx, 0);
 416                x->u.binary.left->hit |= h;
 417                h |= match_expr_eval(o, x->u.binary.right, bol, eol, ctx, 1);
 418                break;
 419        default:
 420                die("Unexpected node type (internal error) %d", x->node);
 421        }
 422        if (collect_hits)
 423                x->hit |= h;
 424        return h;
 425}
 426
 427static int match_expr(struct grep_opt *opt, char *bol, char *eol,
 428                      enum grep_context ctx, int collect_hits)
 429{
 430        struct grep_expr *x = opt->pattern_expression;
 431        return match_expr_eval(opt, x, bol, eol, ctx, collect_hits);
 432}
 433
 434static int match_line(struct grep_opt *opt, char *bol, char *eol,
 435                      enum grep_context ctx, int collect_hits)
 436{
 437        struct grep_pat *p;
 438        if (opt->extended)
 439                return match_expr(opt, bol, eol, ctx, collect_hits);
 440
 441        /* we do not call with collect_hits without being extended */
 442        for (p = opt->pattern_list; p; p = p->next) {
 443                if (match_one_pattern(opt, p, bol, eol, ctx))
 444                        return 1;
 445        }
 446        return 0;
 447}
 448
 449static int grep_buffer_1(struct grep_opt *opt, const char *name,
 450                         char *buf, unsigned long size, int collect_hits)
 451{
 452        char *bol = buf;
 453        unsigned long left = size;
 454        unsigned lno = 1;
 455        struct pre_context_line {
 456                char *bol;
 457                char *eol;
 458        } *prev = NULL, *pcl;
 459        unsigned last_hit = 0;
 460        unsigned last_shown = 0;
 461        int binary_match_only = 0;
 462        const char *hunk_mark = "";
 463        unsigned count = 0;
 464        enum grep_context ctx = GREP_CONTEXT_HEAD;
 465
 466        if (buffer_is_binary(buf, size)) {
 467                switch (opt->binary) {
 468                case GREP_BINARY_DEFAULT:
 469                        binary_match_only = 1;
 470                        break;
 471                case GREP_BINARY_NOMATCH:
 472                        return 0; /* Assume unmatch */
 473                        break;
 474                default:
 475                        break;
 476                }
 477        }
 478
 479        if (opt->pre_context)
 480                prev = xcalloc(opt->pre_context, sizeof(*prev));
 481        if (opt->pre_context || opt->post_context)
 482                hunk_mark = "--\n";
 483
 484        while (left) {
 485                char *eol, ch;
 486                int hit;
 487
 488                eol = end_of_line(bol, &left);
 489                ch = *eol;
 490                *eol = 0;
 491
 492                if ((ctx == GREP_CONTEXT_HEAD) && (eol == bol))
 493                        ctx = GREP_CONTEXT_BODY;
 494
 495                hit = match_line(opt, bol, eol, ctx, collect_hits);
 496                *eol = ch;
 497
 498                if (collect_hits)
 499                        goto next_line;
 500
 501                /* "grep -v -e foo -e bla" should list lines
 502                 * that do not have either, so inversion should
 503                 * be done outside.
 504                 */
 505                if (opt->invert)
 506                        hit = !hit;
 507                if (opt->unmatch_name_only) {
 508                        if (hit)
 509                                return 0;
 510                        goto next_line;
 511                }
 512                if (hit) {
 513                        count++;
 514                        if (opt->status_only)
 515                                return 1;
 516                        if (binary_match_only) {
 517                                printf("Binary file %s matches\n", name);
 518                                return 1;
 519                        }
 520                        if (opt->name_only) {
 521                                show_name(opt, name);
 522                                return 1;
 523                        }
 524                        /* Hit at this line.  If we haven't shown the
 525                         * pre-context lines, we would need to show them.
 526                         * When asked to do "count", this still show
 527                         * the context which is nonsense, but the user
 528                         * deserves to get that ;-).
 529                         */
 530                        if (opt->pre_context) {
 531                                unsigned from;
 532                                if (opt->pre_context < lno)
 533                                        from = lno - opt->pre_context;
 534                                else
 535                                        from = 1;
 536                                if (from <= last_shown)
 537                                        from = last_shown + 1;
 538                                if (last_shown && from != last_shown + 1)
 539                                        fputs(hunk_mark, stdout);
 540                                while (from < lno) {
 541                                        pcl = &prev[lno-from-1];
 542                                        show_line(opt, pcl->bol, pcl->eol,
 543                                                  name, from, '-');
 544                                        from++;
 545                                }
 546                                last_shown = lno-1;
 547                        }
 548                        if (last_shown && lno != last_shown + 1)
 549                                fputs(hunk_mark, stdout);
 550                        if (!opt->count)
 551                                show_line(opt, bol, eol, name, lno, ':');
 552                        last_shown = last_hit = lno;
 553                }
 554                else if (last_hit &&
 555                         lno <= last_hit + opt->post_context) {
 556                        /* If the last hit is within the post context,
 557                         * we need to show this line.
 558                         */
 559                        if (last_shown && lno != last_shown + 1)
 560                                fputs(hunk_mark, stdout);
 561                        show_line(opt, bol, eol, name, lno, '-');
 562                        last_shown = lno;
 563                }
 564                if (opt->pre_context) {
 565                        memmove(prev+1, prev,
 566                                (opt->pre_context-1) * sizeof(*prev));
 567                        prev->bol = bol;
 568                        prev->eol = eol;
 569                }
 570
 571        next_line:
 572                bol = eol + 1;
 573                if (!left)
 574                        break;
 575                left--;
 576                lno++;
 577        }
 578
 579        free(prev);
 580        if (collect_hits)
 581                return 0;
 582
 583        if (opt->status_only)
 584                return 0;
 585        if (opt->unmatch_name_only) {
 586                /* We did not see any hit, so we want to show this */
 587                show_name(opt, name);
 588                return 1;
 589        }
 590
 591        /* NEEDSWORK:
 592         * The real "grep -c foo *.c" gives many "bar.c:0" lines,
 593         * which feels mostly useless but sometimes useful.  Maybe
 594         * make it another option?  For now suppress them.
 595         */
 596        if (opt->count && count)
 597                printf("%s%c%u\n", name,
 598                       opt->null_following_name ? '\0' : ':', count);
 599        return !!last_hit;
 600}
 601
 602static void clr_hit_marker(struct grep_expr *x)
 603{
 604        /* All-hit markers are meaningful only at the very top level
 605         * OR node.
 606         */
 607        while (1) {
 608                x->hit = 0;
 609                if (x->node != GREP_NODE_OR)
 610                        return;
 611                x->u.binary.left->hit = 0;
 612                x = x->u.binary.right;
 613        }
 614}
 615
 616static int chk_hit_marker(struct grep_expr *x)
 617{
 618        /* Top level nodes have hit markers.  See if they all are hits */
 619        while (1) {
 620                if (x->node != GREP_NODE_OR)
 621                        return x->hit;
 622                if (!x->u.binary.left->hit)
 623                        return 0;
 624                x = x->u.binary.right;
 625        }
 626}
 627
 628int grep_buffer(struct grep_opt *opt, const char *name, char *buf, unsigned long size)
 629{
 630        /*
 631         * we do not have to do the two-pass grep when we do not check
 632         * buffer-wide "all-match".
 633         */
 634        if (!opt->all_match)
 635                return grep_buffer_1(opt, name, buf, size, 0);
 636
 637        /* Otherwise the toplevel "or" terms hit a bit differently.
 638         * We first clear hit markers from them.
 639         */
 640        clr_hit_marker(opt->pattern_expression);
 641        grep_buffer_1(opt, name, buf, size, 1);
 642
 643        if (!chk_hit_marker(opt->pattern_expression))
 644                return 0;
 645
 646        return grep_buffer_1(opt, name, buf, size, 0);
 647}