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