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