builtin-grep.c

   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
  16 /*
  17  * git grep pathspecs are somewhat different from diff-tree pathspecs;
  18  * pathname wildcards are allowed.
  19  */
  20 static int pathspec_matches(const char **paths, const char *name)
  21 {
  22         int namelen, i;
  23         if (!paths || !*paths)
  24                 return 1;
  25         namelen = strlen(name);
  26         for (i = 0; paths[i]; i++) {
  27                 const char *match = paths[i];
  28                 int matchlen = strlen(match);
  29                 const char *slash, *cp;
  30
  31                 if ((matchlen <= namelen) &&
  32                     !strncmp(name, match, matchlen) &&
  33                     (match[matchlen-1] == '/' ||
  34                      name[matchlen] == '\0' || name[matchlen] == '/'))
  35                         return 1;
  36                 if (!fnmatch(match, name, 0))
  37                         return 1;
  38                 if (name[namelen-1] != '/')
  39                         continue;
  40
  41                 /* We are being asked if the name directory is worth
  42                  * descending into.
  43                  *
  44                  * Find the longest leading directory name that does
  45                  * not have metacharacter in the pathspec; the name
  46                  * we are looking at must overlap with that directory.
  47                  */
  48                 for (cp = match, slash = NULL; cp - match < matchlen; cp++) {
  49                         char ch = *cp;
  50                         if (ch == '/')
  51                                 slash = cp;
  52                         if (ch == '*' || ch == '[')
  53                                 break;
  54                 }
  55                 if (!slash)
  56                         slash = match; /* toplevel */
  57                 else
  58                         slash++;
  59                 if (namelen <= slash - match) {
  60                         /* Looking at "Documentation/" and
  61                          * the pattern says "Documentation/howto/", or
  62                          * "Documentation/diff*.txt".
  63                          */
  64                         if (!memcmp(match, name, namelen))
  65                                 return 1;
  66                 }
  67                 else {
  68                         /* Looking at "Documentation/howto/" and
  69                          * the pattern says "Documentation/h*".
  70                          */
  71                         if (!memcmp(match, name, slash - match))
  72                                 return 1;
  73                 }
  74         }
  75         return 0;
  76 }
  77
  78 struct grep_pat {
  79         struct grep_pat *next;
  80         const char *pattern;
  81         regex_t regexp;
  82 };
  83
  84 struct grep_opt {
  85         struct grep_pat *pattern_list;
  86         struct grep_pat **pattern_tail;
  87         regex_t regexp;
  88         unsigned linenum:1;
  89         unsigned invert:1;
  90         unsigned name_only:1;
  91         unsigned count:1;
  92         int regflags;
  93         unsigned pre_context;
  94         unsigned post_context;
  95 };
  96
  97 static void add_pattern(struct grep_opt *opt, const char *pat)
  98 {
  99         struct grep_pat *p = xcalloc(1, sizeof(*p));
 100         p->pattern = pat;
 101         *opt->pattern_tail = p;
 102         opt->pattern_tail = &p->next;
 103         p->next = NULL;
 104 }
 105
 106 static void compile_patterns(struct grep_opt *opt)
 107 {
 108         struct grep_pat *p;
 109         for (p = opt->pattern_list; p; p = p->next) {
 110                 int err = regcomp(&p->regexp, p->pattern, opt->regflags);
 111                 if (err) {
 112                         char errbuf[1024];
 113                         regerror(err, &p->regexp, errbuf, 1024);
 114                         regfree(&p->regexp);
 115                         die("'%s': %s", p->pattern, errbuf);
 116                 }
 117         }
 118 }
 119
 120 static char *end_of_line(char *cp, unsigned long *left)
 121 {
 122         unsigned long l = *left;
 123         while (l && *cp != '\n') {
 124                 l--;
 125                 cp++;
 126         }
 127         *left = l;
 128         return cp;
 129 }
 130
 131 static void show_line(struct grep_opt *opt, const char *bol, const char *eol,
 132                       const char *name, unsigned lno, char sign)
 133 {
 134         printf("%s%c", name, sign);
 135         if (opt->linenum)
 136                 printf("%d%c", lno, sign);
 137         printf("%.*s\n", (int)(eol-bol), bol);
 138 }
 139
 140 static int grep_buffer(struct grep_opt *opt, const char *name,
 141                        char *buf, unsigned long size)
 142 {
 143         char *bol = buf;
 144         unsigned long left = size;
 145         unsigned lno = 1;
 146         struct pre_context_line {
 147                 char *bol;
 148                 char *eol;
 149         } *prev = NULL, *pcl;
 150         unsigned last_hit = 0;
 151         unsigned last_shown = 0;
 152         const char *hunk_mark = "";
 153         unsigned count = 0;
 154
 155         if (opt->pre_context)
 156                 prev = xcalloc(opt->pre_context, sizeof(*prev));
 157         if (opt->pre_context || opt->post_context)
 158                 hunk_mark = "--\n";
 159
 160         while (left) {
 161                 regmatch_t pmatch[10];
 162                 char *eol, ch;
 163                 int hit = 0;
 164                 struct grep_pat *p;
 165
 166                 eol = end_of_line(bol, &left);
 167                 ch = *eol;
 168                 *eol = 0;
 169
 170                 for (p = opt->pattern_list; p; p = p->next) {
 171                         regex_t *exp = &p->regexp;
 172                         hit = !regexec(exp, bol, ARRAY_SIZE(pmatch),
 173                                        pmatch, 0);
 174                         if (hit)
 175                                 break;
 176                 }
 177                 /* "grep -v -e foo -e bla" should list lines
 178                  * that do not have either, so inversion should
 179                  * be done outside.
 180                  */
 181                 if (opt->invert)
 182                         hit = !hit;
 183                 if (hit) {
 184                         count++;
 185                         if (opt->name_only) {
 186                                 printf("%s\n", name);
 187                                 return 1;
 188                         }
 189                         /* Hit at this line.  If we haven't shown the
 190                          * pre-context lines, we would need to show them.
 191                          * When asked to do "count", this still show
 192                          * the context which is nonsense, but the user
 193                          * deserves to get that ;-).
 194                          */
 195                         if (opt->pre_context) {
 196                                 unsigned from;
 197                                 if (opt->pre_context < lno)
 198                                         from = lno - opt->pre_context;
 199                                 else
 200                                         from = 1;
 201                                 if (from <= last_shown)
 202                                         from = last_shown + 1;
 203                                 if (last_shown && from != last_shown + 1)
 204                                         printf(hunk_mark);
 205                                 while (from < lno) {
 206                                         pcl = &prev[lno-from-1];
 207                                         show_line(opt, pcl->bol, pcl->eol,
 208                                                   name, from, '-');
 209                                         from++;
 210                                 }
 211                                 last_shown = lno-1;
 212                         }
 213                         if (last_shown && lno != last_shown + 1)
 214                                 printf(hunk_mark);
 215                         if (!opt->count)
 216                                 show_line(opt, bol, eol, name, lno, ':');
 217                         last_shown = last_hit = lno;
 218                 }
 219                 else if (last_hit &&
 220                          lno <= last_hit + opt->post_context) {
 221                         /* If the last hit is within the post context,
 222                          * we need to show this line.
 223                          */
 224                         if (last_shown && lno != last_shown + 1)
 225                                 printf(hunk_mark);
 226                         show_line(opt, bol, eol, name, lno, '-');
 227                         last_shown = lno;
 228                 }
 229                 if (opt->pre_context) {
 230                         memmove(prev+1, prev,
 231                                 (opt->pre_context-1) * sizeof(*prev));
 232                         prev->bol = bol;
 233                         prev->eol = eol;
 234                 }
 235                 *eol = ch;
 236                 bol = eol + 1;
 237                 left--;
 238                 lno++;
 239         }
 240         /* NEEDSWORK:
 241          * The real "grep -c foo *.c" gives many "bar.c:0" lines,
 242          * which feels mostly useless but sometimes useful.  Maybe
 243          * make it another option?  For now suppress them.
 244          */
 245         if (opt->count && count)
 246                 printf("%s:%u\n", name, count);
 247         return !!last_hit;
 248 }
 249
 250 static int grep_sha1(struct grep_opt *opt, const unsigned char *sha1, const char *name)
 251 {
 252         unsigned long size;
 253         char *data;
 254         char type[20];
 255         int hit;
 256         data = read_sha1_file(sha1, type, &size);
 257         if (!data) {
 258                 error("'%s': unable to read %s", name, sha1_to_hex(sha1));
 259                 return 0;
 260         }
 261         hit = grep_buffer(opt, name, data, size);
 262         free(data);
 263         return hit;
 264 }
 265
 266 static int grep_file(struct grep_opt *opt, const char *filename)
 267 {
 268         struct stat st;
 269         int i;
 270         char *data;
 271         if (lstat(filename, &st) < 0) {
 272         err_ret:
 273                 if (errno != ENOENT)
 274                         error("'%s': %s", filename, strerror(errno));
 275                 return 0;
 276         }
 277         if (!st.st_size)
 278                 return 0; /* empty file -- no grep hit */
 279         if (!S_ISREG(st.st_mode))
 280                 return 0;
 281         i = open(filename, O_RDONLY);
 282         if (i < 0)
 283                 goto err_ret;
 284         data = xmalloc(st.st_size + 1);
 285         if (st.st_size != xread(i, data, st.st_size)) {
 286                 error("'%s': short read %s", filename, strerror(errno));
 287                 close(i);
 288                 free(data);
 289                 return 0;
 290         }
 291         close(i);
 292         i = grep_buffer(opt, filename, data, st.st_size);
 293         free(data);
 294         return i;
 295 }
 296
 297 static int grep_cache(struct grep_opt *opt, const char **paths, int cached)
 298 {
 299         int hit = 0;
 300         int nr;
 301         read_cache();
 302
 303         for (nr = 0; nr < active_nr; nr++) {
 304                 struct cache_entry *ce = active_cache[nr];
 305                 if (ce_stage(ce) || !S_ISREG(ntohl(ce->ce_mode)))
 306                         continue;
 307                 if (!pathspec_matches(paths, ce->name))
 308                         continue;
 309                 if (cached)
 310                         hit |= grep_sha1(opt, ce->sha1, ce->name);
 311                 else
 312                         hit |= grep_file(opt, ce->name);
 313         }
 314         return hit;
 315 }
 316
 317 static int grep_tree(struct grep_opt *opt, const char **paths,
 318                      struct tree_desc *tree,
 319                      const char *tree_name, const char *base)
 320 {
 321         unsigned mode;
 322         int len;
 323         int hit = 0;
 324         const char *path;
 325         const unsigned char *sha1;
 326         char *down;
 327         char *path_buf = xmalloc(PATH_MAX + strlen(tree_name) + 100);
 328
 329         if (tree_name[0]) {
 330                 int offset = sprintf(path_buf, "%s:", tree_name);
 331                 down = path_buf + offset;
 332                 strcat(down, base);
 333         }
 334         else {
 335                 down = path_buf;
 336                 strcpy(down, base);
 337         }
 338         len = strlen(path_buf);
 339
 340         while (tree->size) {
 341                 int pathlen;
 342                 sha1 = tree_entry_extract(tree, &path, &mode);
 343                 pathlen = strlen(path);
 344                 strcpy(path_buf + len, path);
 345
 346                 if (S_ISDIR(mode))
 347                         /* Match "abc/" against pathspec to
 348                          * decide if we want to descend into "abc"
 349                          * directory.
 350                          */
 351                         strcpy(path_buf + len + pathlen, "/");
 352
 353                 if (!pathspec_matches(paths, down))
 354                         ;
 355                 else if (S_ISREG(mode))
 356                         hit |= grep_sha1(opt, sha1, path_buf);
 357                 else if (S_ISDIR(mode)) {
 358                         char type[20];
 359                         struct tree_desc sub;
 360                         void *data;
 361                         data = read_sha1_file(sha1, type, &sub.size);
 362                         if (!data)
 363                                 die("unable to read tree (%s)",
 364                                     sha1_to_hex(sha1));
 365                         sub.buf = data;
 366                         hit |= grep_tree(opt, paths, &sub, tree_name, down);
 367                         free(data);
 368                 }
 369                 update_tree_entry(tree);
 370         }
 371         return hit;
 372 }
 373
 374 static int grep_object(struct grep_opt *opt, const char **paths,
 375                        struct object *obj, const char *name)
 376 {
 377         if (!strcmp(obj->type, blob_type))
 378                 return grep_sha1(opt, obj->sha1, name);
 379         if (!strcmp(obj->type, commit_type) ||
 380             !strcmp(obj->type, tree_type)) {
 381                 struct tree_desc tree;
 382                 void *data;
 383                 int hit;
 384                 data = read_object_with_reference(obj->sha1, tree_type,
 385                                                   &tree.size, NULL);
 386                 if (!data)
 387                         die("unable to read tree (%s)", sha1_to_hex(obj->sha1));
 388                 tree.buf = data;
 389                 hit = grep_tree(opt, paths, &tree, name, "");
 390                 free(data);
 391                 return hit;
 392         }
 393         die("unable to grep from object of type %s", obj->type);
 394 }
 395
 396 static const char builtin_grep_usage[] =
 397 "git-grep <option>* <rev>* [-e] <pattern> [<path>...]";
 398
 399 int cmd_grep(int argc, const char **argv, char **envp)
 400 {
 401         int hit = 0;
 402         int no_more_flags = 0;
 403         int seen_noncommit = 0;
 404         int cached = 0;
 405         struct grep_opt opt;
 406         struct object_list *list, **tail, *object_list = NULL;
 407         const char *prefix = setup_git_directory();
 408         const char **paths = NULL;
 409
 410         memset(&opt, 0, sizeof(opt));
 411         opt.pattern_tail = &opt.pattern_list;
 412         opt.regflags = REG_NEWLINE;
 413
 414         /*
 415          * No point using rev_info, really.
 416          */
 417         while (1 < argc) {
 418                 const char *arg = argv[1];
 419                 argc--; argv++;
 420                 if (!strcmp("--cached", arg)) {
 421                         cached = 1;
 422                         continue;
 423                 }
 424                 if (!strcmp("-i", arg) ||
 425                     !strcmp("--ignore-case", arg)) {
 426                         opt.regflags |= REG_ICASE;
 427                         continue;
 428                 }
 429                 if (!strcmp("-v", arg) ||
 430                     !strcmp("--invert-match", arg)) {
 431                         opt.invert = 1;
 432                         continue;
 433                 }
 434                 if (!strcmp("-E", arg) ||
 435                     !strcmp("--extended-regexp", arg)) {
 436                         opt.regflags |= REG_EXTENDED;
 437                         continue;
 438                 }
 439                 if (!strcmp("-G", arg) ||
 440                     !strcmp("--basic-regexp", arg)) {
 441                         opt.regflags &= ~REG_EXTENDED;
 442                         continue;
 443                 }
 444                 if (!strcmp("-n", arg)) {
 445                         opt.linenum = 1;
 446                         continue;
 447                 }
 448                 if (!strcmp("-H", arg)) {
 449                         /* We always show the pathname, so this
 450                          * is a noop.
 451                          */
 452                         continue;
 453                 }
 454                 if (!strcmp("-l", arg) ||
 455                     !strcmp("--files-with-matches", arg)) {
 456                         opt.name_only = 1;
 457                         continue;
 458                 }
 459                 if (!strcmp("-c", arg) ||
 460                     !strcmp("--count", arg)) {
 461                         opt.count = 1;
 462                         continue;
 463                 }
 464                 if (!strncmp("-A", arg, 2) ||
 465                     !strncmp("-B", arg, 2) ||
 466                     !strncmp("-C", arg, 2) ||
 467                     (arg[0] == '-' && '1' <= arg[1] && arg[1] <= '9')) {
 468                         unsigned num;
 469                         const char *scan;
 470                         switch (arg[1]) {
 471                         case 'A': case 'B': case 'C':
 472                                 if (!arg[2]) {
 473                                         if (argc <= 1)
 474                                                 usage(builtin_grep_usage);
 475                                         scan = *++argv;
 476                                         argc--;
 477                                 }
 478                                 else
 479                                         scan = arg + 2;
 480                                 break;
 481                         default:
 482                                 scan = arg + 1;
 483                                 break;
 484                         }
 485                         if (sscanf(scan, "%u", &num) != 1)
 486                                 usage(builtin_grep_usage);
 487                         switch (arg[1]) {
 488                         case 'A':
 489                                 opt.post_context = num;
 490                                 break;
 491                         default:
 492                         case 'C':
 493                                 opt.post_context = num;
 494                         case 'B':
 495                                 opt.pre_context = num;
 496                                 break;
 497                         }
 498                         continue;
 499                 }
 500                 if (!strcmp("-e", arg)) {
 501                         if (1 < argc) {
 502                                 add_pattern(&opt, argv[1]);
 503                                 argv++;
 504                                 argc--;
 505                                 continue;
 506                         }
 507                         usage(builtin_grep_usage);
 508                 }
 509                 if (!strcmp("--", arg)) {
 510                         no_more_flags = 1;
 511                         continue;
 512                 }
 513                 /* Either unrecognized option or a single pattern */
 514                 if (!no_more_flags && *arg == '-')
 515                         usage(builtin_grep_usage);
 516                 if (!opt.pattern_list) {
 517                         add_pattern(&opt, arg);
 518                         break;
 519                 }
 520                 else {
 521                         /* We are looking at the first path or rev;
 522                          * it is found at argv[0] after leaving the
 523                          * loop.
 524                          */
 525                         argc++; argv--;
 526                         break;
 527                 }
 528         }
 529         if (!opt.pattern_list)
 530                 die("no pattern given.");
 531         compile_patterns(&opt);
 532         tail = &object_list;
 533         while (1 < argc) {
 534                 struct object *object;
 535                 struct object_list *elem;
 536                 const char *arg = argv[1];
 537                 unsigned char sha1[20];
 538                 if (get_sha1(arg, sha1) < 0)
 539                         break;
 540                 object = parse_object(sha1);
 541                 if (!object)
 542                         die("bad object %s", arg);
 543                 elem = object_list_insert(object, tail);
 544                 elem->name = arg;
 545                 tail = &elem->next;
 546                 argc--; argv++;
 547         }
 548         if (1 < argc)
 549                 paths = get_pathspec(prefix, argv + 1);
 550         else if (prefix) {
 551                 paths = xcalloc(2, sizeof(const char *));
 552                 paths[0] = prefix;
 553                 paths[1] = NULL;
 554         }
 555
 556         if (!object_list)
 557                 return !grep_cache(&opt, paths, cached);
 558         /*
 559          * Do not walk "grep -e foo master next pu -- Documentation/"
 560          * but do walk "grep -e foo master..next -- Documentation/".
 561          * Ranged request mixed with a blob or tree object, like
 562          * "grep -e foo v1.0.0:Documentation/ master..next"
 563          * so detect that and complain.
 564          */
 565         for (list = object_list; list; list = list->next) {
 566                 struct object *real_obj;
 567                 real_obj = deref_tag(list->item, NULL, 0);
 568                 if (strcmp(real_obj->type, commit_type))
 569                         seen_noncommit = 1;
 570         }
 571         if (cached)
 572                 die("both --cached and revisions given.");
 573
 574         for (list = object_list; list; list = list->next) {
 575                 struct object *real_obj;
 576                 real_obj = deref_tag(list->item, NULL, 0);
 577                 if (grep_object(&opt, paths, real_obj, list->name))
 578                         hit = 1;
 579         }
 580         return !hit;
 581 }