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