Andrew's git / gitweb.git / builtin-grep.c
?
builtin-grep.con commit Build on Debian GNU/kFreeBSD (ca7a741)
   1/*
   2 * Builtin "git grep"
   3 *
   4 * Copyright (c) 2006 Junio C Hamano
   5 */
   6#include "cache.h"
   7#include "blob.h"
   8#include "tree.h"
   9#include "commit.h"
  10#include "tag.h"
  11#include "tree-walk.h"
  12#include "builtin.h"
  13#include <regex.h>
  14#include <fnmatch.h>
  15#include <sys/wait.h>
  16
  17/*
  18 * git grep pathspecs are somewhat different from diff-tree pathspecs;
  19 * pathname wildcards are allowed.
  20 */
  21static int pathspec_matches(const char **paths, const char *name)
  22{
  23        int namelen, i;
  24        if (!paths || !*paths)
  25                return 1;
  26        namelen = strlen(name);
  27        for (i = 0; paths[i]; i++) {
  28                const char *match = paths[i];
  29                int matchlen = strlen(match);
  30                const char *cp, *meta;
  31
  32                if (!matchlen ||
  33                    ((matchlen <= namelen) &&
  34                     !strncmp(name, match, matchlen) &&
  35                     (match[matchlen-1] == '/' ||
  36                      name[matchlen] == '\0' || name[matchlen] == '/')))
  37                        return 1;
  38                if (!fnmatch(match, name, 0))
  39                        return 1;
  40                if (name[namelen-1] != '/')
  41                        continue;
  42
  43                /* We are being asked if the directory ("name") is worth
  44                 * descending into.
  45                 *
  46                 * Find the longest leading directory name that does
  47                 * not have metacharacter in the pathspec; the name
  48                 * we are looking at must overlap with that directory.
  49                 */
  50                for (cp = match, meta = NULL; cp - match < matchlen; cp++) {
  51                        char ch = *cp;
  52                        if (ch == '*' || ch == '[' || ch == '?') {
  53                                meta = cp;
  54                                break;
  55                        }
  56                }
  57                if (!meta)
  58                        meta = cp; /* fully literal */
  59
  60                if (namelen <= meta - match) {
  61                        /* Looking at "Documentation/" and
  62                         * the pattern says "Documentation/howto/", or
  63                         * "Documentation/diff*.txt".  The name we
  64                         * have should match prefix.
  65                         */
  66                        if (!memcmp(match, name, namelen))
  67                                return 1;
  68                        continue;
  69                }
  70
  71                if (meta - match < namelen) {
  72                        /* Looking at "Documentation/howto/" and
  73                         * the pattern says "Documentation/h*";
  74                         * match up to "Do.../h"; this avoids descending
  75                         * into "Documentation/technical/".
  76                         */
  77                        if (!memcmp(match, name, meta - match))
  78                                return 1;
  79                        continue;
  80                }
  81        }
  82        return 0;
  83}
  84
  85enum grep_pat_token {
  86        GREP_PATTERN,
  87        GREP_AND,
  88        GREP_OPEN_PAREN,
  89        GREP_CLOSE_PAREN,
  90        GREP_NOT,
  91        GREP_OR,
  92};
  93
  94struct grep_pat {
  95        struct grep_pat *next;
  96        const char *origin;
  97        int no;
  98        enum grep_pat_token token;
  99        const char *pattern;
 100        regex_t regexp;
 101};
 102
 103enum grep_expr_node {
 104        GREP_NODE_ATOM,
 105        GREP_NODE_NOT,
 106        GREP_NODE_AND,
 107        GREP_NODE_OR,
 108};
 109
 110struct grep_expr {
 111        enum grep_expr_node node;
 112        union {
 113                struct grep_pat *atom;
 114                struct grep_expr *unary;
 115                struct {
 116                        struct grep_expr *left;
 117                        struct grep_expr *right;
 118                } binary;
 119        } u;
 120};
 121
 122struct grep_opt {
 123        struct grep_pat *pattern_list;
 124        struct grep_pat **pattern_tail;
 125        struct grep_expr *pattern_expression;
 126        regex_t regexp;
 127        unsigned linenum:1;
 128        unsigned invert:1;
 129        unsigned name_only:1;
 130        unsigned unmatch_name_only:1;
 131        unsigned count:1;
 132        unsigned word_regexp:1;
 133        unsigned fixed:1;
 134#define GREP_BINARY_DEFAULT     0
 135#define GREP_BINARY_NOMATCH     1
 136#define GREP_BINARY_TEXT        2
 137        unsigned binary:2;
 138        unsigned extended:1;
 139        int regflags;
 140        unsigned pre_context;
 141        unsigned post_context;
 142};
 143
 144static void add_pattern(struct grep_opt *opt, const char *pat,
 145                        const char *origin, int no, enum grep_pat_token t)
 146{
 147        struct grep_pat *p = xcalloc(1, sizeof(*p));
 148        p->pattern = pat;
 149        p->origin = origin;
 150        p->no = no;
 151        p->token = t;
 152        *opt->pattern_tail = p;
 153        opt->pattern_tail = &p->next;
 154        p->next = NULL;
 155}
 156
 157static void compile_regexp(struct grep_pat *p, struct grep_opt *opt)
 158{
 159        int err = regcomp(&p->regexp, p->pattern, opt->regflags);
 160        if (err) {
 161                char errbuf[1024];
 162                char where[1024];
 163                if (p->no)
 164                        sprintf(where, "In '%s' at %d, ",
 165                                p->origin, p->no);
 166                else if (p->origin)
 167                        sprintf(where, "%s, ", p->origin);
 168                else
 169                        where[0] = 0;
 170                regerror(err, &p->regexp, errbuf, 1024);
 171                regfree(&p->regexp);
 172                die("%s'%s': %s", where, p->pattern, errbuf);
 173        }
 174}
 175
 176#if DEBUG
 177static inline void indent(int in)
 178{
 179        int i;
 180        for (i = 0; i < in; i++) putchar(' ');
 181}
 182
 183static void dump_pattern_exp(struct grep_expr *x, int in)
 184{
 185        switch (x->node) {
 186        case GREP_NODE_ATOM:
 187                indent(in);
 188                puts(x->u.atom->pattern);
 189                break;
 190        case GREP_NODE_NOT:
 191                indent(in);
 192                puts("--not");
 193                dump_pattern_exp(x->u.unary, in+1);
 194                break;
 195        case GREP_NODE_AND:
 196                dump_pattern_exp(x->u.binary.left, in+1);
 197                indent(in);
 198                puts("--and");
 199                dump_pattern_exp(x->u.binary.right, in+1);
 200                break;
 201        case GREP_NODE_OR:
 202                dump_pattern_exp(x->u.binary.left, in+1);
 203                indent(in);
 204                puts("--or");
 205                dump_pattern_exp(x->u.binary.right, in+1);
 206                break;
 207        }
 208}
 209
 210static void looking_at(const char *msg, struct grep_pat **list)
 211{
 212        struct grep_pat *p = *list;
 213        fprintf(stderr, "%s: looking at ", msg);
 214        if (!p)
 215                fprintf(stderr, "empty\n");
 216        else
 217                fprintf(stderr, "<%s>\n", p->pattern);
 218}
 219#else
 220#define looking_at(a,b) do {} while(0)
 221#endif
 222
 223static struct grep_expr *compile_pattern_expr(struct grep_pat **);
 224static struct grep_expr *compile_pattern_atom(struct grep_pat **list)
 225{
 226        struct grep_pat *p;
 227        struct grep_expr *x;
 228
 229        looking_at("atom", list);
 230
 231        p = *list;
 232        switch (p->token) {
 233        case GREP_PATTERN: /* atom */
 234                x = xcalloc(1, sizeof (struct grep_expr));
 235                x->node = GREP_NODE_ATOM;
 236                x->u.atom = p;
 237                *list = p->next;
 238                return x;
 239        case GREP_OPEN_PAREN:
 240                *list = p->next;
 241                x = compile_pattern_expr(list);
 242                if (!x)
 243                        return NULL;
 244                if (!*list || (*list)->token != GREP_CLOSE_PAREN)
 245                        die("unmatched parenthesis");
 246                *list = (*list)->next;
 247                return x;
 248        default:
 249                return NULL;
 250        }
 251}
 252
 253static struct grep_expr *compile_pattern_not(struct grep_pat **list)
 254{
 255        struct grep_pat *p;
 256        struct grep_expr *x;
 257
 258        looking_at("not", list);
 259
 260        p = *list;
 261        switch (p->token) {
 262        case GREP_NOT:
 263                if (!p->next)
 264                        die("--not not followed by pattern expression");
 265                *list = p->next;
 266                x = xcalloc(1, sizeof (struct grep_expr));
 267                x->node = GREP_NODE_NOT;
 268                x->u.unary = compile_pattern_not(list);
 269                if (!x->u.unary)
 270                        die("--not followed by non pattern expression");
 271                return x;
 272        default:
 273                return compile_pattern_atom(list);
 274        }
 275}
 276
 277static struct grep_expr *compile_pattern_and(struct grep_pat **list)
 278{
 279        struct grep_pat *p;
 280        struct grep_expr *x, *y, *z;
 281
 282        looking_at("and", list);
 283
 284        x = compile_pattern_not(list);
 285        p = *list;
 286        if (p && p->token == GREP_AND) {
 287                if (!p->next)
 288                        die("--and not followed by pattern expression");
 289                *list = p->next;
 290                y = compile_pattern_and(list);
 291                if (!y)
 292                        die("--and not followed by pattern expression");
 293                z = xcalloc(1, sizeof (struct grep_expr));
 294                z->node = GREP_NODE_AND;
 295                z->u.binary.left = x;
 296                z->u.binary.right = y;
 297                return z;
 298        }
 299        return x;
 300}
 301
 302static struct grep_expr *compile_pattern_or(struct grep_pat **list)
 303{
 304        struct grep_pat *p;
 305        struct grep_expr *x, *y, *z;
 306
 307        looking_at("or", list);
 308
 309        x = compile_pattern_and(list);
 310        p = *list;
 311        if (x && p && p->token != GREP_CLOSE_PAREN) {
 312                y = compile_pattern_or(list);
 313                if (!y)
 314                        die("not a pattern expression %s", p->pattern);
 315                z = xcalloc(1, sizeof (struct grep_expr));
 316                z->node = GREP_NODE_OR;
 317                z->u.binary.left = x;
 318                z->u.binary.right = y;
 319                return z;
 320        }
 321        return x;
 322}
 323
 324static struct grep_expr *compile_pattern_expr(struct grep_pat **list)
 325{
 326        looking_at("expr", list);
 327
 328        return compile_pattern_or(list);
 329}
 330
 331static void compile_patterns(struct grep_opt *opt)
 332{
 333        struct grep_pat *p;
 334
 335        /* First compile regexps */
 336        for (p = opt->pattern_list; p; p = p->next) {
 337                if (p->token == GREP_PATTERN)
 338                        compile_regexp(p, opt);
 339                else
 340                        opt->extended = 1;
 341        }
 342
 343        if (!opt->extended)
 344                return;
 345
 346        /* Then bundle them up in an expression.
 347         * A classic recursive descent parser would do.
 348         */
 349        p = opt->pattern_list;
 350        opt->pattern_expression = compile_pattern_expr(&p);
 351#if DEBUG
 352        dump_pattern_exp(opt->pattern_expression, 0);
 353#endif
 354        if (p)
 355                die("incomplete pattern expression: %s", p->pattern);
 356}
 357
 358static char *end_of_line(char *cp, unsigned long *left)
 359{
 360        unsigned long l = *left;
 361        while (l && *cp != '\n') {
 362                l--;
 363                cp++;
 364        }
 365        *left = l;
 366        return cp;
 367}
 368
 369static int word_char(char ch)
 370{
 371        return isalnum(ch) || ch == '_';
 372}
 373
 374static void show_line(struct grep_opt *opt, const char *bol, const char *eol,
 375                      const char *name, unsigned lno, char sign)
 376{
 377        printf("%s%c", name, sign);
 378        if (opt->linenum)
 379                printf("%d%c", lno, sign);
 380        printf("%.*s\n", (int)(eol-bol), bol);
 381}
 382
 383/*
 384 * NEEDSWORK: share code with diff.c
 385 */
 386#define FIRST_FEW_BYTES 8000
 387static int buffer_is_binary(const char *ptr, unsigned long size)
 388{
 389        if (FIRST_FEW_BYTES < size)
 390                size = FIRST_FEW_BYTES;
 391        if (memchr(ptr, 0, size))
 392                return 1;
 393        return 0;
 394}
 395
 396static int fixmatch(const char *pattern, char *line, regmatch_t *match)
 397{
 398        char *hit = strstr(line, pattern);
 399        if (!hit) {
 400                match->rm_so = match->rm_eo = -1;
 401                return REG_NOMATCH;
 402        }
 403        else {
 404                match->rm_so = hit - line;
 405                match->rm_eo = match->rm_so + strlen(pattern);
 406                return 0;
 407        }
 408}
 409
 410static int match_one_pattern(struct grep_opt *opt, struct grep_pat *p, char *bol, char *eol)
 411{
 412        int hit = 0;
 413        regmatch_t pmatch[10];
 414
 415        if (!opt->fixed) {
 416                regex_t *exp = &p->regexp;
 417                hit = !regexec(exp, bol, ARRAY_SIZE(pmatch),
 418                               pmatch, 0);
 419        }
 420        else {
 421                hit = !fixmatch(p->pattern, bol, pmatch);
 422        }
 423
 424        if (hit && opt->word_regexp) {
 425                /* Match beginning must be either
 426                 * beginning of the line, or at word
 427                 * boundary (i.e. the last char must
 428                 * not be alnum or underscore).
 429                 */
 430                if ((pmatch[0].rm_so < 0) ||
 431                    (eol - bol) <= pmatch[0].rm_so ||
 432                    (pmatch[0].rm_eo < 0) ||
 433                    (eol - bol) < pmatch[0].rm_eo)
 434                        die("regexp returned nonsense");
 435                if (pmatch[0].rm_so != 0 &&
 436                    word_char(bol[pmatch[0].rm_so-1]))
 437                        hit = 0;
 438                if (pmatch[0].rm_eo != (eol-bol) &&
 439                    word_char(bol[pmatch[0].rm_eo]))
 440                        hit = 0;
 441        }
 442        return hit;
 443}
 444
 445static int match_expr_eval(struct grep_opt *opt,
 446                           struct grep_expr *x,
 447                           char *bol, char *eol)
 448{
 449        switch (x->node) {
 450        case GREP_NODE_ATOM:
 451                return match_one_pattern(opt, x->u.atom, bol, eol);
 452                break;
 453        case GREP_NODE_NOT:
 454                return !match_expr_eval(opt, x->u.unary, bol, eol);
 455        case GREP_NODE_AND:
 456                return (match_expr_eval(opt, x->u.binary.left, bol, eol) &&
 457                        match_expr_eval(opt, x->u.binary.right, bol, eol));
 458        case GREP_NODE_OR:
 459                return (match_expr_eval(opt, x->u.binary.left, bol, eol) ||
 460                        match_expr_eval(opt, x->u.binary.right, bol, eol));
 461        }
 462        die("Unexpected node type (internal error) %d\n", x->node);
 463}
 464
 465static int match_expr(struct grep_opt *opt, char *bol, char *eol)
 466{
 467        struct grep_expr *x = opt->pattern_expression;
 468        return match_expr_eval(opt, x, bol, eol);
 469}
 470
 471static int match_line(struct grep_opt *opt, char *bol, char *eol)
 472{
 473        struct grep_pat *p;
 474        if (opt->extended)
 475                return match_expr(opt, bol, eol);
 476        for (p = opt->pattern_list; p; p = p->next) {
 477                if (match_one_pattern(opt, p, bol, eol))
 478                        return 1;
 479        }
 480        return 0;
 481}
 482
 483static int grep_buffer(struct grep_opt *opt, const char *name,
 484                       char *buf, unsigned long size)
 485{
 486        char *bol = buf;
 487        unsigned long left = size;
 488        unsigned lno = 1;
 489        struct pre_context_line {
 490                char *bol;
 491                char *eol;
 492        } *prev = NULL, *pcl;
 493        unsigned last_hit = 0;
 494        unsigned last_shown = 0;
 495        int binary_match_only = 0;
 496        const char *hunk_mark = "";
 497        unsigned count = 0;
 498
 499        if (buffer_is_binary(buf, size)) {
 500                switch (opt->binary) {
 501                case GREP_BINARY_DEFAULT:
 502                        binary_match_only = 1;
 503                        break;
 504                case GREP_BINARY_NOMATCH:
 505                        return 0; /* Assume unmatch */
 506                        break;
 507                default:
 508                        break;
 509                }
 510        }
 511
 512        if (opt->pre_context)
 513                prev = xcalloc(opt->pre_context, sizeof(*prev));
 514        if (opt->pre_context || opt->post_context)
 515                hunk_mark = "--\n";
 516
 517        while (left) {
 518                char *eol, ch;
 519                int hit = 0;
 520
 521                eol = end_of_line(bol, &left);
 522                ch = *eol;
 523                *eol = 0;
 524
 525                hit = match_line(opt, bol, eol);
 526
 527                /* "grep -v -e foo -e bla" should list lines
 528                 * that do not have either, so inversion should
 529                 * be done outside.
 530                 */
 531                if (opt->invert)
 532                        hit = !hit;
 533                if (opt->unmatch_name_only) {
 534                        if (hit)
 535                                return 0;
 536                        goto next_line;
 537                }
 538                if (hit) {
 539                        count++;
 540                        if (binary_match_only) {
 541                                printf("Binary file %s matches\n", name);
 542                                return 1;
 543                        }
 544                        if (opt->name_only) {
 545                                printf("%s\n", name);
 546                                return 1;
 547                        }
 548                        /* Hit at this line.  If we haven't shown the
 549                         * pre-context lines, we would need to show them.
 550                         * When asked to do "count", this still show
 551                         * the context which is nonsense, but the user
 552                         * deserves to get that ;-).
 553                         */
 554                        if (opt->pre_context) {
 555                                unsigned from;
 556                                if (opt->pre_context < lno)
 557                                        from = lno - opt->pre_context;
 558                                else
 559                                        from = 1;
 560                                if (from <= last_shown)
 561                                        from = last_shown + 1;
 562                                if (last_shown && from != last_shown + 1)
 563                                        printf(hunk_mark);
 564                                while (from < lno) {
 565                                        pcl = &prev[lno-from-1];
 566                                        show_line(opt, pcl->bol, pcl->eol,
 567                                                  name, from, '-');
 568                                        from++;
 569                                }
 570                                last_shown = lno-1;
 571                        }
 572                        if (last_shown && lno != last_shown + 1)
 573                                printf(hunk_mark);
 574                        if (!opt->count)
 575                                show_line(opt, bol, eol, name, lno, ':');
 576                        last_shown = last_hit = lno;
 577                }
 578                else if (last_hit &&
 579                         lno <= last_hit + opt->post_context) {
 580                        /* If the last hit is within the post context,
 581                         * we need to show this line.
 582                         */
 583                        if (last_shown && lno != last_shown + 1)
 584                                printf(hunk_mark);
 585                        show_line(opt, bol, eol, name, lno, '-');
 586                        last_shown = lno;
 587                }
 588                if (opt->pre_context) {
 589                        memmove(prev+1, prev,
 590                                (opt->pre_context-1) * sizeof(*prev));
 591                        prev->bol = bol;
 592                        prev->eol = eol;
 593                }
 594
 595        next_line:
 596                *eol = ch;
 597                bol = eol + 1;
 598                if (!left)
 599                        break;
 600                left--;
 601                lno++;
 602        }
 603
 604        if (opt->unmatch_name_only) {
 605                /* We did not see any hit, so we want to show this */
 606                printf("%s\n", name);
 607                return 1;
 608        }
 609
 610        /* NEEDSWORK:
 611         * The real "grep -c foo *.c" gives many "bar.c:0" lines,
 612         * which feels mostly useless but sometimes useful.  Maybe
 613         * make it another option?  For now suppress them.
 614         */
 615        if (opt->count && count)
 616                printf("%s:%u\n", name, count);
 617        return !!last_hit;
 618}
 619
 620static int grep_sha1(struct grep_opt *opt, const unsigned char *sha1, const char *name)
 621{
 622        unsigned long size;
 623        char *data;
 624        char type[20];
 625        int hit;
 626        data = read_sha1_file(sha1, type, &size);
 627        if (!data) {
 628                error("'%s': unable to read %s", name, sha1_to_hex(sha1));
 629                return 0;
 630        }
 631        hit = grep_buffer(opt, name, data, size);
 632        free(data);
 633        return hit;
 634}
 635
 636static int grep_file(struct grep_opt *opt, const char *filename)
 637{
 638        struct stat st;
 639        int i;
 640        char *data;
 641        if (lstat(filename, &st) < 0) {
 642        err_ret:
 643                if (errno != ENOENT)
 644                        error("'%s': %s", filename, strerror(errno));
 645                return 0;
 646        }
 647        if (!st.st_size)
 648                return 0; /* empty file -- no grep hit */
 649        if (!S_ISREG(st.st_mode))
 650                return 0;
 651        i = open(filename, O_RDONLY);
 652        if (i < 0)
 653                goto err_ret;
 654        data = xmalloc(st.st_size + 1);
 655        if (st.st_size != xread(i, data, st.st_size)) {
 656                error("'%s': short read %s", filename, strerror(errno));
 657                close(i);
 658                free(data);
 659                return 0;
 660        }
 661        close(i);
 662        i = grep_buffer(opt, filename, data, st.st_size);
 663        free(data);
 664        return i;
 665}
 666
 667static int exec_grep(int argc, const char **argv)
 668{
 669        pid_t pid;
 670        int status;
 671
 672        argv[argc] = NULL;
 673        pid = fork();
 674        if (pid < 0)
 675                return pid;
 676        if (!pid) {
 677                execvp("grep", (char **) argv);
 678                exit(255);
 679        }
 680        while (waitpid(pid, &status, 0) < 0) {
 681                if (errno == EINTR)
 682                        continue;
 683                return -1;
 684        }
 685        if (WIFEXITED(status)) {
 686                if (!WEXITSTATUS(status))
 687                        return 1;
 688                return 0;
 689        }
 690        return -1;
 691}
 692
 693#define MAXARGS 1000
 694#define ARGBUF 4096
 695#define push_arg(a) do { \
 696        if (nr < MAXARGS) argv[nr++] = (a); \
 697        else die("maximum number of args exceeded"); \
 698        } while (0)
 699
 700static int external_grep(struct grep_opt *opt, const char **paths, int cached)
 701{
 702        int i, nr, argc, hit, len, status;
 703        const char *argv[MAXARGS+1];
 704        char randarg[ARGBUF];
 705        char *argptr = randarg;
 706        struct grep_pat *p;
 707
 708        if (opt->extended)
 709                return -1;
 710        len = nr = 0;
 711        push_arg("grep");
 712        if (opt->fixed)
 713                push_arg("-F");
 714        if (opt->linenum)
 715                push_arg("-n");
 716        if (opt->regflags & REG_EXTENDED)
 717                push_arg("-E");
 718        if (opt->regflags & REG_ICASE)
 719                push_arg("-i");
 720        if (opt->word_regexp)
 721                push_arg("-w");
 722        if (opt->name_only)
 723                push_arg("-l");
 724        if (opt->unmatch_name_only)
 725                push_arg("-L");
 726        if (opt->count)
 727                push_arg("-c");
 728        if (opt->post_context || opt->pre_context) {
 729                if (opt->post_context != opt->pre_context) {
 730                        if (opt->pre_context) {
 731                                push_arg("-B");
 732                                len += snprintf(argptr, sizeof(randarg)-len,
 733                                                "%u", opt->pre_context);
 734                                if (sizeof(randarg) <= len)
 735                                        die("maximum length of args exceeded");
 736                                push_arg(argptr);
 737                                argptr += len;
 738                        }
 739                        if (opt->post_context) {
 740                                push_arg("-A");
 741                                len += snprintf(argptr, sizeof(randarg)-len,
 742                                                "%u", opt->post_context);
 743                                if (sizeof(randarg) <= len)
 744                                        die("maximum length of args exceeded");
 745                                push_arg(argptr);
 746                                argptr += len;
 747                        }
 748                }
 749                else {
 750                        push_arg("-C");
 751                        len += snprintf(argptr, sizeof(randarg)-len,
 752                                        "%u", opt->post_context);
 753                        if (sizeof(randarg) <= len)
 754                                die("maximum length of args exceeded");
 755                        push_arg(argptr);
 756                        argptr += len;
 757                }
 758        }
 759        for (p = opt->pattern_list; p; p = p->next) {
 760                push_arg("-e");
 761                push_arg(p->pattern);
 762        }
 763
 764        /*
 765         * To make sure we get the header printed out when we want it,
 766         * add /dev/null to the paths to grep.  This is unnecessary
 767         * (and wrong) with "-l" or "-L", which always print out the
 768         * name anyway.
 769         *
 770         * GNU grep has "-H", but this is portable.
 771         */
 772        if (!opt->name_only && !opt->unmatch_name_only)
 773                push_arg("/dev/null");
 774
 775        hit = 0;
 776        argc = nr;
 777        for (i = 0; i < active_nr; i++) {
 778                struct cache_entry *ce = active_cache[i];
 779                char *name;
 780                if (ce_stage(ce) || !S_ISREG(ntohl(ce->ce_mode)))
 781                        continue;
 782                if (!pathspec_matches(paths, ce->name))
 783                        continue;
 784                name = ce->name;
 785                if (name[0] == '-') {
 786                        int len = ce_namelen(ce);
 787                        name = xmalloc(len + 3);
 788                        memcpy(name, "./", 2);
 789                        memcpy(name + 2, ce->name, len + 1);
 790                }
 791                argv[argc++] = name;
 792                if (argc < MAXARGS)
 793                        continue;
 794                status = exec_grep(argc, argv);
 795                if (0 < status)
 796                        hit = 1;
 797                argc = nr;
 798        }
 799        if (argc > nr) {
 800                status = exec_grep(argc, argv);
 801                if (0 < status)
 802                        hit = 1;
 803        }
 804        return hit;
 805}
 806
 807static int grep_cache(struct grep_opt *opt, const char **paths, int cached)
 808{
 809        int hit = 0;
 810        int nr;
 811        read_cache();
 812
 813#ifdef __unix__
 814        /*
 815         * Use the external "grep" command for the case where
 816         * we grep through the checked-out files. It tends to
 817         * be a lot more optimized
 818         */
 819        if (!cached) {
 820                hit = external_grep(opt, paths, cached);
 821                if (hit >= 0)
 822                        return hit;
 823        }
 824#endif
 825
 826        for (nr = 0; nr < active_nr; nr++) {
 827                struct cache_entry *ce = active_cache[nr];
 828                if (ce_stage(ce) || !S_ISREG(ntohl(ce->ce_mode)))
 829                        continue;
 830                if (!pathspec_matches(paths, ce->name))
 831                        continue;
 832                if (cached)
 833                        hit |= grep_sha1(opt, ce->sha1, ce->name);
 834                else
 835                        hit |= grep_file(opt, ce->name);
 836        }
 837        return hit;
 838}
 839
 840static int grep_tree(struct grep_opt *opt, const char **paths,
 841                     struct tree_desc *tree,
 842                     const char *tree_name, const char *base)
 843{
 844        int len;
 845        int hit = 0;
 846        struct name_entry entry;
 847        char *down;
 848        char *path_buf = xmalloc(PATH_MAX + strlen(tree_name) + 100);
 849
 850        if (tree_name[0]) {
 851                int offset = sprintf(path_buf, "%s:", tree_name);
 852                down = path_buf + offset;
 853                strcat(down, base);
 854        }
 855        else {
 856                down = path_buf;
 857                strcpy(down, base);
 858        }
 859        len = strlen(path_buf);
 860
 861        while (tree_entry(tree, &entry)) {
 862                strcpy(path_buf + len, entry.path);
 863
 864                if (S_ISDIR(entry.mode))
 865                        /* Match "abc/" against pathspec to
 866                         * decide if we want to descend into "abc"
 867                         * directory.
 868                         */
 869                        strcpy(path_buf + len + entry.pathlen, "/");
 870
 871                if (!pathspec_matches(paths, down))
 872                        ;
 873                else if (S_ISREG(entry.mode))
 874                        hit |= grep_sha1(opt, entry.sha1, path_buf);
 875                else if (S_ISDIR(entry.mode)) {
 876                        char type[20];
 877                        struct tree_desc sub;
 878                        void *data;
 879                        data = read_sha1_file(entry.sha1, type, &sub.size);
 880                        if (!data)
 881                                die("unable to read tree (%s)",
 882                                    sha1_to_hex(entry.sha1));
 883                        sub.buf = data;
 884                        hit |= grep_tree(opt, paths, &sub, tree_name, down);
 885                        free(data);
 886                }
 887        }
 888        return hit;
 889}
 890
 891static int grep_object(struct grep_opt *opt, const char **paths,
 892                       struct object *obj, const char *name)
 893{
 894        if (obj->type == OBJ_BLOB)
 895                return grep_sha1(opt, obj->sha1, name);
 896        if (obj->type == OBJ_COMMIT || obj->type == OBJ_TREE) {
 897                struct tree_desc tree;
 898                void *data;
 899                int hit;
 900                data = read_object_with_reference(obj->sha1, tree_type,
 901                                                  &tree.size, NULL);
 902                if (!data)
 903                        die("unable to read tree (%s)", sha1_to_hex(obj->sha1));
 904                tree.buf = data;
 905                hit = grep_tree(opt, paths, &tree, name, "");
 906                free(data);
 907                return hit;
 908        }
 909        die("unable to grep from object of type %s", typename(obj->type));
 910}
 911
 912static const char builtin_grep_usage[] =
 913"git-grep <option>* <rev>* [-e] <pattern> [<path>...]";
 914
 915static const char emsg_invalid_context_len[] =
 916"%s: invalid context length argument";
 917static const char emsg_missing_context_len[] =
 918"missing context length argument";
 919static const char emsg_missing_argument[] =
 920"option requires an argument -%s";
 921
 922int cmd_grep(int argc, const char **argv, const char *prefix)
 923{
 924        int hit = 0;
 925        int cached = 0;
 926        int seen_dashdash = 0;
 927        struct grep_opt opt;
 928        struct object_array list = { 0, 0, NULL };
 929        const char **paths = NULL;
 930        int i;
 931
 932        memset(&opt, 0, sizeof(opt));
 933        opt.pattern_tail = &opt.pattern_list;
 934        opt.regflags = REG_NEWLINE;
 935
 936        /*
 937         * If there is no -- then the paths must exist in the working
 938         * tree.  If there is no explicit pattern specified with -e or
 939         * -f, we take the first unrecognized non option to be the
 940         * pattern, but then what follows it must be zero or more
 941         * valid refs up to the -- (if exists), and then existing
 942         * paths.  If there is an explicit pattern, then the first
 943         * unrecognized non option is the beginning of the refs list
 944         * that continues up to the -- (if exists), and then paths.
 945         */
 946
 947        while (1 < argc) {
 948                const char *arg = argv[1];
 949                argc--; argv++;
 950                if (!strcmp("--cached", arg)) {
 951                        cached = 1;
 952                        continue;
 953                }
 954                if (!strcmp("-a", arg) ||
 955                    !strcmp("--text", arg)) {
 956                        opt.binary = GREP_BINARY_TEXT;
 957                        continue;
 958                }
 959                if (!strcmp("-i", arg) ||
 960                    !strcmp("--ignore-case", arg)) {
 961                        opt.regflags |= REG_ICASE;
 962                        continue;
 963                }
 964                if (!strcmp("-I", arg)) {
 965                        opt.binary = GREP_BINARY_NOMATCH;
 966                        continue;
 967                }
 968                if (!strcmp("-v", arg) ||
 969                    !strcmp("--invert-match", arg)) {
 970                        opt.invert = 1;
 971                        continue;
 972                }
 973                if (!strcmp("-E", arg) ||
 974                    !strcmp("--extended-regexp", arg)) {
 975                        opt.regflags |= REG_EXTENDED;
 976                        continue;
 977                }
 978                if (!strcmp("-F", arg) ||
 979                    !strcmp("--fixed-strings", arg)) {
 980                        opt.fixed = 1;
 981                        continue;
 982                }
 983                if (!strcmp("-G", arg) ||
 984                    !strcmp("--basic-regexp", arg)) {
 985                        opt.regflags &= ~REG_EXTENDED;
 986                        continue;
 987                }
 988                if (!strcmp("-n", arg)) {
 989                        opt.linenum = 1;
 990                        continue;
 991                }
 992                if (!strcmp("-H", arg)) {
 993                        /* We always show the pathname, so this
 994                         * is a noop.
 995                         */
 996                        continue;
 997                }
 998                if (!strcmp("-l", arg) ||
 999                    !strcmp("--files-with-matches", arg)) {
1000                        opt.name_only = 1;
1001                        continue;
1002                }
1003                if (!strcmp("-L", arg) ||
1004                    !strcmp("--files-without-match", arg)) {
1005                        opt.unmatch_name_only = 1;
1006                        continue;
1007                }
1008                if (!strcmp("-c", arg) ||
1009                    !strcmp("--count", arg)) {
1010                        opt.count = 1;
1011                        continue;
1012                }
1013                if (!strcmp("-w", arg) ||
1014                    !strcmp("--word-regexp", arg)) {
1015                        opt.word_regexp = 1;
1016                        continue;
1017                }
1018                if (!strncmp("-A", arg, 2) ||
1019                    !strncmp("-B", arg, 2) ||
1020                    !strncmp("-C", arg, 2) ||
1021                    (arg[0] == '-' && '1' <= arg[1] && arg[1] <= '9')) {
1022                        unsigned num;
1023                        const char *scan;
1024                        switch (arg[1]) {
1025                        case 'A': case 'B': case 'C':
1026                                if (!arg[2]) {
1027                                        if (argc <= 1)
1028                                                die(emsg_missing_context_len);
1029                                        scan = *++argv;
1030                                        argc--;
1031                                }
1032                                else
1033                                        scan = arg + 2;
1034                                break;
1035                        default:
1036                                scan = arg + 1;
1037                                break;
1038                        }
1039                        if (sscanf(scan, "%u", &num) != 1)
1040                                die(emsg_invalid_context_len, scan);
1041                        switch (arg[1]) {
1042                        case 'A':
1043                                opt.post_context = num;
1044                                break;
1045                        default:
1046                        case 'C':
1047                                opt.post_context = num;
1048                        case 'B':
1049                                opt.pre_context = num;
1050                                break;
1051                        }
1052                        continue;
1053                }
1054                if (!strcmp("-f", arg)) {
1055                        FILE *patterns;
1056                        int lno = 0;
1057                        char buf[1024];
1058                        if (argc <= 1)
1059                                die(emsg_missing_argument, arg);
1060                        patterns = fopen(argv[1], "r");
1061                        if (!patterns)
1062                                die("'%s': %s", argv[1], strerror(errno));
1063                        while (fgets(buf, sizeof(buf), patterns)) {
1064                                int len = strlen(buf);
1065                                if (buf[len-1] == '\n')
1066                                        buf[len-1] = 0;
1067                                /* ignore empty line like grep does */
1068                                if (!buf[0])
1069                                        continue;
1070                                add_pattern(&opt, strdup(buf), argv[1], ++lno,
1071                                            GREP_PATTERN);
1072                        }
1073                        fclose(patterns);
1074                        argv++;
1075                        argc--;
1076                        continue;
1077                }
1078                if (!strcmp("--not", arg)) {
1079                        add_pattern(&opt, arg, "command line", 0, GREP_NOT);
1080                        continue;
1081                }
1082                if (!strcmp("--and", arg)) {
1083                        add_pattern(&opt, arg, "command line", 0, GREP_AND);
1084                        continue;
1085                }
1086                if (!strcmp("--or", arg))
1087                        continue; /* no-op */
1088                if (!strcmp("(", arg)) {
1089                        add_pattern(&opt, arg, "command line", 0, GREP_OPEN_PAREN);
1090                        continue;
1091                }
1092                if (!strcmp(")", arg)) {
1093                        add_pattern(&opt, arg, "command line", 0, GREP_CLOSE_PAREN);
1094                        continue;
1095                }
1096                if (!strcmp("-e", arg)) {
1097                        if (1 < argc) {
1098                                add_pattern(&opt, argv[1], "-e option", 0,
1099                                            GREP_PATTERN);
1100                                argv++;
1101                                argc--;
1102                                continue;
1103                        }
1104                        die(emsg_missing_argument, arg);
1105                }
1106                if (!strcmp("--", arg)) {
1107                        /* later processing wants to have this at argv[1] */
1108                        argv--;
1109                        argc++;
1110                        break;
1111                }
1112                if (*arg == '-')
1113                        usage(builtin_grep_usage);
1114
1115                /* First unrecognized non-option token */
1116                if (!opt.pattern_list) {
1117                        add_pattern(&opt, arg, "command line", 0,
1118                                    GREP_PATTERN);
1119                        break;
1120                }
1121                else {
1122                        /* We are looking at the first path or rev;
1123                         * it is found at argv[1] after leaving the
1124                         * loop.
1125                         */
1126                        argc++; argv--;
1127                        break;
1128                }
1129        }
1130
1131        if (!opt.pattern_list)
1132                die("no pattern given.");
1133        if ((opt.regflags != REG_NEWLINE) && opt.fixed)
1134                die("cannot mix --fixed-strings and regexp");
1135        if (!opt.fixed)
1136                compile_patterns(&opt);
1137
1138        /* Check revs and then paths */
1139        for (i = 1; i < argc; i++) {
1140                const char *arg = argv[i];
1141                unsigned char sha1[20];
1142                /* Is it a rev? */
1143                if (!get_sha1(arg, sha1)) {
1144                        struct object *object = parse_object(sha1);
1145                        if (!object)
1146                                die("bad object %s", arg);
1147                        add_object_array(object, arg, &list);
1148                        continue;
1149                }
1150                if (!strcmp(arg, "--")) {
1151                        i++;
1152                        seen_dashdash = 1;
1153                }
1154                break;
1155        }
1156
1157        /* The rest are paths */
1158        if (!seen_dashdash) {
1159                int j;
1160                for (j = i; j < argc; j++)
1161                        verify_filename(prefix, argv[j]);
1162        }
1163
1164        if (i < argc)
1165                paths = get_pathspec(prefix, argv + i);
1166        else if (prefix) {
1167                paths = xcalloc(2, sizeof(const char *));
1168                paths[0] = prefix;
1169                paths[1] = NULL;
1170        }
1171
1172        if (!list.nr)
1173                return !grep_cache(&opt, paths, cached);
1174
1175        if (cached)
1176                die("both --cached and trees are given.");
1177
1178        for (i = 0; i < list.nr; i++) {
1179                struct object *real_obj;
1180                real_obj = deref_tag(list.objects[i].item, NULL, 0);
1181                if (grep_object(&opt, paths, real_obj, list.objects[i].name))
1182                        hit = 1;
1183        }
1184        return !hit;
1185}