Fix usage string to match that given in the man page
[git] / grep.c
1 #include "cache.h"
2 #include <regex.h>
3 #include "grep.h"
4
5 void append_grep_pattern(struct grep_opt *opt, const char *pat,
6                          const char *origin, int no, enum grep_pat_token t)
7 {
8         struct grep_pat *p = xcalloc(1, sizeof(*p));
9         p->pattern = pat;
10         p->origin = origin;
11         p->no = no;
12         p->token = t;
13         *opt->pattern_tail = p;
14         opt->pattern_tail = &p->next;
15         p->next = NULL;
16 }
17
18 static void compile_regexp(struct grep_pat *p, struct grep_opt *opt)
19 {
20         int err = regcomp(&p->regexp, p->pattern, opt->regflags);
21         if (err) {
22                 char errbuf[1024];
23                 char where[1024];
24                 if (p->no)
25                         sprintf(where, "In '%s' at %d, ",
26                                 p->origin, p->no);
27                 else if (p->origin)
28                         sprintf(where, "%s, ", p->origin);
29                 else
30                         where[0] = 0;
31                 regerror(err, &p->regexp, errbuf, 1024);
32                 regfree(&p->regexp);
33                 die("%s'%s': %s", where, p->pattern, errbuf);
34         }
35 }
36
37 static struct grep_expr *compile_pattern_expr(struct grep_pat **);
38 static struct grep_expr *compile_pattern_atom(struct grep_pat **list)
39 {
40         struct grep_pat *p;
41         struct grep_expr *x;
42
43         p = *list;
44         switch (p->token) {
45         case GREP_PATTERN: /* atom */
46         case GREP_PATTERN_HEAD:
47         case GREP_PATTERN_BODY:
48                 x = xcalloc(1, sizeof (struct grep_expr));
49                 x->node = GREP_NODE_ATOM;
50                 x->u.atom = p;
51                 *list = p->next;
52                 return x;
53         case GREP_OPEN_PAREN:
54                 *list = p->next;
55                 x = compile_pattern_expr(list);
56                 if (!x)
57                         return NULL;
58                 if (!*list || (*list)->token != GREP_CLOSE_PAREN)
59                         die("unmatched parenthesis");
60                 *list = (*list)->next;
61                 return x;
62         default:
63                 return NULL;
64         }
65 }
66
67 static struct grep_expr *compile_pattern_not(struct grep_pat **list)
68 {
69         struct grep_pat *p;
70         struct grep_expr *x;
71
72         p = *list;
73         switch (p->token) {
74         case GREP_NOT:
75                 if (!p->next)
76                         die("--not not followed by pattern expression");
77                 *list = p->next;
78                 x = xcalloc(1, sizeof (struct grep_expr));
79                 x->node = GREP_NODE_NOT;
80                 x->u.unary = compile_pattern_not(list);
81                 if (!x->u.unary)
82                         die("--not followed by non pattern expression");
83                 return x;
84         default:
85                 return compile_pattern_atom(list);
86         }
87 }
88
89 static struct grep_expr *compile_pattern_and(struct grep_pat **list)
90 {
91         struct grep_pat *p;
92         struct grep_expr *x, *y, *z;
93
94         x = compile_pattern_not(list);
95         p = *list;
96         if (p && p->token == GREP_AND) {
97                 if (!p->next)
98                         die("--and not followed by pattern expression");
99                 *list = p->next;
100                 y = compile_pattern_and(list);
101                 if (!y)
102                         die("--and not followed by pattern expression");
103                 z = xcalloc(1, sizeof (struct grep_expr));
104                 z->node = GREP_NODE_AND;
105                 z->u.binary.left = x;
106                 z->u.binary.right = y;
107                 return z;
108         }
109         return x;
110 }
111
112 static struct grep_expr *compile_pattern_or(struct grep_pat **list)
113 {
114         struct grep_pat *p;
115         struct grep_expr *x, *y, *z;
116
117         x = compile_pattern_and(list);
118         p = *list;
119         if (x && p && p->token != GREP_CLOSE_PAREN) {
120                 y = compile_pattern_or(list);
121                 if (!y)
122                         die("not a pattern expression %s", p->pattern);
123                 z = xcalloc(1, sizeof (struct grep_expr));
124                 z->node = GREP_NODE_OR;
125                 z->u.binary.left = x;
126                 z->u.binary.right = y;
127                 return z;
128         }
129         return x;
130 }
131
132 static struct grep_expr *compile_pattern_expr(struct grep_pat **list)
133 {
134         return compile_pattern_or(list);
135 }
136
137 void compile_grep_patterns(struct grep_opt *opt)
138 {
139         struct grep_pat *p;
140
141         for (p = opt->pattern_list; p; p = p->next) {
142                 switch (p->token) {
143                 case GREP_PATTERN: /* atom */
144                 case GREP_PATTERN_HEAD:
145                 case GREP_PATTERN_BODY:
146                         if (!opt->fixed)
147                                 compile_regexp(p, opt);
148                         break;
149                 default:
150                         opt->extended = 1;
151                         break;
152                 }
153         }
154
155         if (!opt->extended)
156                 return;
157
158         /* Then bundle them up in an expression.
159          * A classic recursive descent parser would do.
160          */
161         p = opt->pattern_list;
162         opt->pattern_expression = compile_pattern_expr(&p);
163         if (p)
164                 die("incomplete pattern expression: %s", p->pattern);
165 }
166
167 static void free_pattern_expr(struct grep_expr *x)
168 {
169         switch (x->node) {
170         case GREP_NODE_ATOM:
171                 break;
172         case GREP_NODE_NOT:
173                 free_pattern_expr(x->u.unary);
174                 break;
175         case GREP_NODE_AND:
176         case GREP_NODE_OR:
177                 free_pattern_expr(x->u.binary.left);
178                 free_pattern_expr(x->u.binary.right);
179                 break;
180         }
181         free(x);
182 }
183
184 void free_grep_patterns(struct grep_opt *opt)
185 {
186         struct grep_pat *p, *n;
187
188         for (p = opt->pattern_list; p; p = n) {
189                 n = p->next;
190                 switch (p->token) {
191                 case GREP_PATTERN: /* atom */
192                 case GREP_PATTERN_HEAD:
193                 case GREP_PATTERN_BODY:
194                         regfree(&p->regexp);
195                         break;
196                 default:
197                         break;
198                 }
199                 free(p);
200         }
201
202         if (!opt->extended)
203                 return;
204         free_pattern_expr(opt->pattern_expression);
205 }
206
207 static char *end_of_line(char *cp, unsigned long *left)
208 {
209         unsigned long l = *left;
210         while (l && *cp != '\n') {
211                 l--;
212                 cp++;
213         }
214         *left = l;
215         return cp;
216 }
217
218 static int word_char(char ch)
219 {
220         return isalnum(ch) || ch == '_';
221 }
222
223 static void show_line(struct grep_opt *opt, const char *bol, const char *eol,
224                       const char *name, unsigned lno, char sign)
225 {
226         if (opt->pathname)
227                 printf("%s%c", name, sign);
228         if (opt->linenum)
229                 printf("%d%c", lno, sign);
230         printf("%.*s\n", (int)(eol-bol), bol);
231 }
232
233 /*
234  * NEEDSWORK: share code with diff.c
235  */
236 #define FIRST_FEW_BYTES 8000
237 static int buffer_is_binary(const char *ptr, unsigned long size)
238 {
239         if (FIRST_FEW_BYTES < size)
240                 size = FIRST_FEW_BYTES;
241         return !!memchr(ptr, 0, size);
242 }
243
244 static int fixmatch(const char *pattern, char *line, regmatch_t *match)
245 {
246         char *hit = strstr(line, pattern);
247         if (!hit) {
248                 match->rm_so = match->rm_eo = -1;
249                 return REG_NOMATCH;
250         }
251         else {
252                 match->rm_so = hit - line;
253                 match->rm_eo = match->rm_so + strlen(pattern);
254                 return 0;
255         }
256 }
257
258 static int match_one_pattern(struct grep_opt *opt, struct grep_pat *p, char *bol, char *eol, enum grep_context ctx)
259 {
260         int hit = 0;
261         int at_true_bol = 1;
262         regmatch_t pmatch[10];
263
264         if ((p->token != GREP_PATTERN) &&
265             ((p->token == GREP_PATTERN_HEAD) != (ctx == GREP_CONTEXT_HEAD)))
266                 return 0;
267
268  again:
269         if (!opt->fixed) {
270                 regex_t *exp = &p->regexp;
271                 hit = !regexec(exp, bol, ARRAY_SIZE(pmatch),
272                                pmatch, 0);
273         }
274         else {
275                 hit = !fixmatch(p->pattern, bol, pmatch);
276         }
277
278         if (hit && opt->word_regexp) {
279                 if ((pmatch[0].rm_so < 0) ||
280                     (eol - bol) <= pmatch[0].rm_so ||
281                     (pmatch[0].rm_eo < 0) ||
282                     (eol - bol) < pmatch[0].rm_eo)
283                         die("regexp returned nonsense");
284
285                 /* Match beginning must be either beginning of the
286                  * line, or at word boundary (i.e. the last char must
287                  * not be a word char).  Similarly, match end must be
288                  * either end of the line, or at word boundary
289                  * (i.e. the next char must not be a word char).
290                  */
291                 if ( ((pmatch[0].rm_so == 0 && at_true_bol) ||
292                       !word_char(bol[pmatch[0].rm_so-1])) &&
293                      ((pmatch[0].rm_eo == (eol-bol)) ||
294                       !word_char(bol[pmatch[0].rm_eo])) )
295                         ;
296                 else
297                         hit = 0;
298
299                 if (!hit && pmatch[0].rm_so + bol + 1 < eol) {
300                         /* There could be more than one match on the
301                          * line, and the first match might not be
302                          * strict word match.  But later ones could be!
303                          */
304                         bol = pmatch[0].rm_so + bol + 1;
305                         at_true_bol = 0;
306                         goto again;
307                 }
308         }
309         return hit;
310 }
311
312 static int match_expr_eval(struct grep_opt *opt,
313                            struct grep_expr *x,
314                            char *bol, char *eol,
315                            enum grep_context ctx)
316 {
317         switch (x->node) {
318         case GREP_NODE_ATOM:
319                 return match_one_pattern(opt, x->u.atom, bol, eol, ctx);
320                 break;
321         case GREP_NODE_NOT:
322                 return !match_expr_eval(opt, x->u.unary, bol, eol, ctx);
323         case GREP_NODE_AND:
324                 return (match_expr_eval(opt, x->u.binary.left, bol, eol, ctx) &&
325                         match_expr_eval(opt, x->u.binary.right, bol, eol, ctx));
326         case GREP_NODE_OR:
327                 return (match_expr_eval(opt, x->u.binary.left, bol, eol, ctx) ||
328                         match_expr_eval(opt, x->u.binary.right, bol, eol, ctx));
329         }
330         die("Unexpected node type (internal error) %d\n", x->node);
331 }
332
333 static int match_expr(struct grep_opt *opt, char *bol, char *eol,
334                       enum grep_context ctx)
335 {
336         struct grep_expr *x = opt->pattern_expression;
337         return match_expr_eval(opt, x, bol, eol, ctx);
338 }
339
340 static int match_line(struct grep_opt *opt, char *bol, char *eol,
341                       enum grep_context ctx)
342 {
343         struct grep_pat *p;
344         if (opt->extended)
345                 return match_expr(opt, bol, eol, ctx);
346         for (p = opt->pattern_list; p; p = p->next) {
347                 if (match_one_pattern(opt, p, bol, eol, ctx))
348                         return 1;
349         }
350         return 0;
351 }
352
353 int grep_buffer(struct grep_opt *opt, const char *name, char *buf, unsigned long size)
354 {
355         char *bol = buf;
356         unsigned long left = size;
357         unsigned lno = 1;
358         struct pre_context_line {
359                 char *bol;
360                 char *eol;
361         } *prev = NULL, *pcl;
362         unsigned last_hit = 0;
363         unsigned last_shown = 0;
364         int binary_match_only = 0;
365         const char *hunk_mark = "";
366         unsigned count = 0;
367         enum grep_context ctx = GREP_CONTEXT_HEAD;
368
369         if (buffer_is_binary(buf, size)) {
370                 switch (opt->binary) {
371                 case GREP_BINARY_DEFAULT:
372                         binary_match_only = 1;
373                         break;
374                 case GREP_BINARY_NOMATCH:
375                         return 0; /* Assume unmatch */
376                         break;
377                 default:
378                         break;
379                 }
380         }
381
382         if (opt->pre_context)
383                 prev = xcalloc(opt->pre_context, sizeof(*prev));
384         if (opt->pre_context || opt->post_context)
385                 hunk_mark = "--\n";
386
387         while (left) {
388                 char *eol, ch;
389                 int hit = 0;
390
391                 eol = end_of_line(bol, &left);
392                 ch = *eol;
393                 *eol = 0;
394
395                 if ((ctx == GREP_CONTEXT_HEAD) && (eol == bol))
396                         ctx = GREP_CONTEXT_BODY;
397
398                 hit = match_line(opt, bol, eol, ctx);
399                 *eol = ch;
400
401                 /* "grep -v -e foo -e bla" should list lines
402                  * that do not have either, so inversion should
403                  * be done outside.
404                  */
405                 if (opt->invert)
406                         hit = !hit;
407                 if (opt->unmatch_name_only) {
408                         if (hit)
409                                 return 0;
410                         goto next_line;
411                 }
412                 if (hit) {
413                         count++;
414                         if (opt->status_only)
415                                 return 1;
416                         if (binary_match_only) {
417                                 printf("Binary file %s matches\n", name);
418                                 return 1;
419                         }
420                         if (opt->name_only) {
421                                 printf("%s\n", name);
422                                 return 1;
423                         }
424                         /* Hit at this line.  If we haven't shown the
425                          * pre-context lines, we would need to show them.
426                          * When asked to do "count", this still show
427                          * the context which is nonsense, but the user
428                          * deserves to get that ;-).
429                          */
430                         if (opt->pre_context) {
431                                 unsigned from;
432                                 if (opt->pre_context < lno)
433                                         from = lno - opt->pre_context;
434                                 else
435                                         from = 1;
436                                 if (from <= last_shown)
437                                         from = last_shown + 1;
438                                 if (last_shown && from != last_shown + 1)
439                                         printf(hunk_mark);
440                                 while (from < lno) {
441                                         pcl = &prev[lno-from-1];
442                                         show_line(opt, pcl->bol, pcl->eol,
443                                                   name, from, '-');
444                                         from++;
445                                 }
446                                 last_shown = lno-1;
447                         }
448                         if (last_shown && lno != last_shown + 1)
449                                 printf(hunk_mark);
450                         if (!opt->count)
451                                 show_line(opt, bol, eol, name, lno, ':');
452                         last_shown = last_hit = lno;
453                 }
454                 else if (last_hit &&
455                          lno <= last_hit + opt->post_context) {
456                         /* If the last hit is within the post context,
457                          * we need to show this line.
458                          */
459                         if (last_shown && lno != last_shown + 1)
460                                 printf(hunk_mark);
461                         show_line(opt, bol, eol, name, lno, '-');
462                         last_shown = lno;
463                 }
464                 if (opt->pre_context) {
465                         memmove(prev+1, prev,
466                                 (opt->pre_context-1) * sizeof(*prev));
467                         prev->bol = bol;
468                         prev->eol = eol;
469                 }
470
471         next_line:
472                 bol = eol + 1;
473                 if (!left)
474                         break;
475                 left--;
476                 lno++;
477         }
478
479         free(prev);
480
481         if (opt->status_only)
482                 return 0;
483         if (opt->unmatch_name_only) {
484                 /* We did not see any hit, so we want to show this */
485                 printf("%s\n", name);
486                 return 1;
487         }
488
489         /* NEEDSWORK:
490          * The real "grep -c foo *.c" gives many "bar.c:0" lines,
491          * which feels mostly useless but sometimes useful.  Maybe
492          * make it another option?  For now suppress them.
493          */
494         if (opt->count && count)
495                 printf("%s:%u\n", name, count);
496         return !!last_hit;
497 }
498