{"thread":{"id":"5592","subject":"[PATCH 1/3] builtin-grep: make pieces of it available as library.","startedAt":"2006-09-18T00:42:24Z","lastAt":"2006-09-18T00:42:24Z","messageCount":1,"participants":["Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"27099","messageId":"7vfyeqyphr.fsf@assigned-by-dhcp.cox.net","threadId":"5592","inReplyTo":null,"subject":"[PATCH 1/3] builtin-grep: make pieces of it available as library.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-18T00:42:24Z","receivedAt":"2006-09-18T00:42:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This makes three functions and associated option structures from\nbuiltin-grep available from other parts of the system.\n\n * options to drive built-in grep engine is stored in struct\n   grep_opt;\n\n * pattern strings and extended grep expressions are added to\n   struct grep_opt with append_grep_pattern();\n\n * when finished calling append_grep_pattern(), call\n   compile_grep_patterns() to prepare for execution;\n\n * call grep_buffer() to find matches in the in-core buffer.\n\nThis also adds an internal option \"status_only\" to grep_opt,\nwhich suppresses any output from grep_buffer().  Callers of the\nfunction as library can use it to check if there is a match\nwithout producing any output.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n Makefile       |    2 \n builtin-grep.c |  522 ++------------------------------------------------------\n grep.c         |  440 +++++++++++++++++++++++++++++++++++++++++++++++\n grep.h         |   71 ++++++++\n 4 files changed, 530 insertions(+), 505 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex b987450..b8e679e 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -252,7 +252,7 @@ LIB_OBJS = \\\n \tserver-info.o setup.o sha1_file.o sha1_name.o strbuf.o \\\n \ttag.o tree.o usage.o config.o environment.o ctype.o copy.o \\\n \tfetch-clone.o revision.o pager.o tree-walk.o xdiff-interface.o \\\n-\twrite_or_die.o trace.o \\\n+\twrite_or_die.o trace.o grep.o \\\n \talloc.o merge-file.o path-list.o help.o unpack-trees.o $(DIFF_OBJS)\n \n BUILTIN_OBJS = \\\ndiff --git a/builtin-grep.c b/builtin-grep.c\nindex ed87a55..6718788 100644\n--- a/builtin-grep.c\n+++ b/builtin-grep.c\n@@ -11,6 +11,7 @@ #include \"tag.h\"\n #include \"tree-walk.h\"\n #include \"builtin.h\"\n #include <regex.h>\n+#include \"grep.h\"\n #include <fnmatch.h>\n #include <sys/wait.h>\n \n@@ -82,498 +83,6 @@ static int pathspec_matches(const char *\n \treturn 0;\n }\n \n-enum grep_pat_token {\n-\tGREP_PATTERN,\n-\tGREP_AND,\n-\tGREP_OPEN_PAREN,\n-\tGREP_CLOSE_PAREN,\n-\tGREP_NOT,\n-\tGREP_OR,\n-};\n-\n-struct grep_pat {\n-\tstruct grep_pat *next;\n-\tconst char *origin;\n-\tint no;\n-\tenum grep_pat_token token;\n-\tconst char *pattern;\n-\tregex_t regexp;\n-};\n-\n-enum grep_expr_node {\n-\tGREP_NODE_ATOM,\n-\tGREP_NODE_NOT,\n-\tGREP_NODE_AND,\n-\tGREP_NODE_OR,\n-};\n-\n-struct grep_expr {\n-\tenum grep_expr_node node;\n-\tunion {\n-\t\tstruct grep_pat *atom;\n-\t\tstruct grep_expr *unary;\n-\t\tstruct {\n-\t\t\tstruct grep_expr *left;\n-\t\t\tstruct grep_expr *right;\n-\t\t} binary;\n-\t} u;\n-};\n-\n-struct grep_opt {\n-\tstruct grep_pat *pattern_list;\n-\tstruct grep_pat **pattern_tail;\n-\tstruct grep_expr *pattern_expression;\n-\tint prefix_length;\n-\tregex_t regexp;\n-\tunsigned linenum:1;\n-\tunsigned invert:1;\n-\tunsigned name_only:1;\n-\tunsigned unmatch_name_only:1;\n-\tunsigned count:1;\n-\tunsigned word_regexp:1;\n-\tunsigned fixed:1;\n-#define GREP_BINARY_DEFAULT\t0\n-#define GREP_BINARY_NOMATCH\t1\n-#define GREP_BINARY_TEXT\t2\n-\tunsigned binary:2;\n-\tunsigned extended:1;\n-\tunsigned relative:1;\n-\tunsigned pathname:1;\n-\tint regflags;\n-\tunsigned pre_context;\n-\tunsigned post_context;\n-};\n-\n-static void add_pattern(struct grep_opt *opt, const char *pat,\n-\t\t\tconst char *origin, int no, enum grep_pat_token t)\n-{\n-\tstruct grep_pat *p = xcalloc(1, sizeof(*p));\n-\tp->pattern = pat;\n-\tp->origin = origin;\n-\tp->no = no;\n-\tp->token = t;\n-\t*opt->pattern_tail = p;\n-\topt->pattern_tail = &p->next;\n-\tp->next = NULL;\n-}\n-\n-static void compile_regexp(struct grep_pat *p, struct grep_opt *opt)\n-{\n-\tint err = regcomp(&p->regexp, p->pattern, opt->regflags);\n-\tif (err) {\n-\t\tchar errbuf[1024];\n-\t\tchar where[1024];\n-\t\tif (p->no)\n-\t\t\tsprintf(where, \"In '%s' at %d, \",\n-\t\t\t\tp->origin, p->no);\n-\t\telse if (p->origin)\n-\t\t\tsprintf(where, \"%s, \", p->origin);\n-\t\telse\n-\t\t\twhere[0] = 0;\n-\t\tregerror(err, &p->regexp, errbuf, 1024);\n-\t\tregfree(&p->regexp);\n-\t\tdie(\"%s'%s': %s\", where, p->pattern, errbuf);\n-\t}\n-}\n-\n-static struct grep_expr *compile_pattern_expr(struct grep_pat **);\n-static struct grep_expr *compile_pattern_atom(struct grep_pat **list)\n-{\n-\tstruct grep_pat *p;\n-\tstruct grep_expr *x;\n-\n-\tp = *list;\n-\tswitch (p->token) {\n-\tcase GREP_PATTERN: /* atom */\n-\t\tx = xcalloc(1, sizeof (struct grep_expr));\n-\t\tx->node = GREP_NODE_ATOM;\n-\t\tx->u.atom = p;\n-\t\t*list = p->next;\n-\t\treturn x;\n-\tcase GREP_OPEN_PAREN:\n-\t\t*list = p->next;\n-\t\tx = compile_pattern_expr(list);\n-\t\tif (!x)\n-\t\t\treturn NULL;\n-\t\tif (!*list || (*list)->token != GREP_CLOSE_PAREN)\n-\t\t\tdie(\"unmatched parenthesis\");\n-\t\t*list = (*list)->next;\n-\t\treturn x;\n-\tdefault:\n-\t\treturn NULL;\n-\t}\n-}\n-\n-static struct grep_expr *compile_pattern_not(struct grep_pat **list)\n-{\n-\tstruct grep_pat *p;\n-\tstruct grep_expr *x;\n-\n-\tp = *list;\n-\tswitch (p->token) {\n-\tcase GREP_NOT:\n-\t\tif (!p->next)\n-\t\t\tdie(\"--not not followed by pattern expression\");\n-\t\t*list = p->next;\n-\t\tx = xcalloc(1, sizeof (struct grep_expr));\n-\t\tx->node = GREP_NODE_NOT;\n-\t\tx->u.unary = compile_pattern_not(list);\n-\t\tif (!x->u.unary)\n-\t\t\tdie(\"--not followed by non pattern expression\");\n-\t\treturn x;\n-\tdefault:\n-\t\treturn compile_pattern_atom(list);\n-\t}\n-}\n-\n-static struct grep_expr *compile_pattern_and(struct grep_pat **list)\n-{\n-\tstruct grep_pat *p;\n-\tstruct grep_expr *x, *y, *z;\n-\n-\tx = compile_pattern_not(list);\n-\tp = *list;\n-\tif (p && p->token == GREP_AND) {\n-\t\tif (!p->next)\n-\t\t\tdie(\"--and not followed by pattern expression\");\n-\t\t*list = p->next;\n-\t\ty = compile_pattern_and(list);\n-\t\tif (!y)\n-\t\t\tdie(\"--and not followed by pattern expression\");\n-\t\tz = xcalloc(1, sizeof (struct grep_expr));\n-\t\tz->node = GREP_NODE_AND;\n-\t\tz->u.binary.left = x;\n-\t\tz->u.binary.right = y;\n-\t\treturn z;\n-\t}\n-\treturn x;\n-}\n-\n-static struct grep_expr *compile_pattern_or(struct grep_pat **list)\n-{\n-\tstruct grep_pat *p;\n-\tstruct grep_expr *x, *y, *z;\n-\n-\tx = compile_pattern_and(list);\n-\tp = *list;\n-\tif (x && p && p->token != GREP_CLOSE_PAREN) {\n-\t\ty = compile_pattern_or(list);\n-\t\tif (!y)\n-\t\t\tdie(\"not a pattern expression %s\", p->pattern);\n-\t\tz = xcalloc(1, sizeof (struct grep_expr));\n-\t\tz->node = GREP_NODE_OR;\n-\t\tz->u.binary.left = x;\n-\t\tz->u.binary.right = y;\n-\t\treturn z;\n-\t}\n-\treturn x;\n-}\n-\n-static struct grep_expr *compile_pattern_expr(struct grep_pat **list)\n-{\n-\treturn compile_pattern_or(list);\n-}\n-\n-static void compile_patterns(struct grep_opt *opt)\n-{\n-\tstruct grep_pat *p;\n-\n-\t/* First compile regexps */\n-\tfor (p = opt->pattern_list; p; p = p->next) {\n-\t\tif (p->token == GREP_PATTERN)\n-\t\t\tcompile_regexp(p, opt);\n-\t\telse\n-\t\t\topt->extended = 1;\n-\t}\n-\n-\tif (!opt->extended)\n-\t\treturn;\n-\n-\t/* Then bundle them up in an expression.\n-\t * A classic recursive descent parser would do.\n-\t */\n-\tp = opt->pattern_list;\n-\topt->pattern_expression = compile_pattern_expr(&p);\n-\tif (p)\n-\t\tdie(\"incomplete pattern expression: %s\", p->pattern);\n-}\n-\n-static char *end_of_line(char *cp, unsigned long *left)\n-{\n-\tunsigned long l = *left;\n-\twhile (l && *cp != '\\n') {\n-\t\tl--;\n-\t\tcp++;\n-\t}\n-\t*left = l;\n-\treturn cp;\n-}\n-\n-static int word_char(char ch)\n-{\n-\treturn isalnum(ch) || ch == '_';\n-}\n-\n-static void show_line(struct grep_opt *opt, const char *bol, const char *eol,\n-\t\t      const char *name, unsigned lno, char sign)\n-{\n-\tif (opt->pathname)\n-\t\tprintf(\"%s%c\", name, sign);\n-\tif (opt->linenum)\n-\t\tprintf(\"%d%c\", lno, sign);\n-\tprintf(\"%.*s\\n\", (int)(eol-bol), bol);\n-}\n-\n-/*\n- * NEEDSWORK: share code with diff.c\n- */\n-#define FIRST_FEW_BYTES 8000\n-static int buffer_is_binary(const char *ptr, unsigned long size)\n-{\n-\tif (FIRST_FEW_BYTES < size)\n-\t\tsize = FIRST_FEW_BYTES;\n-\treturn !!memchr(ptr, 0, size);\n-}\n-\n-static int fixmatch(const char *pattern, char *line, regmatch_t *match)\n-{\n-\tchar *hit = strstr(line, pattern);\n-\tif (!hit) {\n-\t\tmatch->rm_so = match->rm_eo = -1;\n-\t\treturn REG_NOMATCH;\n-\t}\n-\telse {\n-\t\tmatch->rm_so = hit - line;\n-\t\tmatch->rm_eo = match->rm_so + strlen(pattern);\n-\t\treturn 0;\n-\t}\n-}\n-\n-static int match_one_pattern(struct grep_opt *opt, struct grep_pat *p, char *bol, char *eol)\n-{\n-\tint hit = 0;\n-\tint at_true_bol = 1;\n-\tregmatch_t pmatch[10];\n-\n- again:\n-\tif (!opt->fixed) {\n-\t\tregex_t *exp = &p->regexp;\n-\t\thit = !regexec(exp, bol, ARRAY_SIZE(pmatch),\n-\t\t\t       pmatch, 0);\n-\t}\n-\telse {\n-\t\thit = !fixmatch(p->pattern, bol, pmatch);\n-\t}\n-\n-\tif (hit && opt->word_regexp) {\n-\t\tif ((pmatch[0].rm_so < 0) ||\n-\t\t    (eol - bol) <= pmatch[0].rm_so ||\n-\t\t    (pmatch[0].rm_eo < 0) ||\n-\t\t    (eol - bol) < pmatch[0].rm_eo)\n-\t\t\tdie(\"regexp returned nonsense\");\n-\n-\t\t/* Match beginning must be either beginning of the\n-\t\t * line, or at word boundary (i.e. the last char must\n-\t\t * not be a word char).  Similarly, match end must be\n-\t\t * either end of the line, or at word boundary\n-\t\t * (i.e. the next char must not be a word char).\n-\t\t */\n-\t\tif ( ((pmatch[0].rm_so == 0 && at_true_bol) ||\n-\t\t      !word_char(bol[pmatch[0].rm_so-1])) &&\n-\t\t     ((pmatch[0].rm_eo == (eol-bol)) ||\n-\t\t      !word_char(bol[pmatch[0].rm_eo])) )\n-\t\t\t;\n-\t\telse\n-\t\t\thit = 0;\n-\n-\t\tif (!hit && pmatch[0].rm_so + bol + 1 < eol) {\n-\t\t\t/* There could be more than one match on the\n-\t\t\t * line, and the first match might not be\n-\t\t\t * strict word match.  But later ones could be!\n-\t\t\t */\n-\t\t\tbol = pmatch[0].rm_so + bol + 1;\n-\t\t\tat_true_bol = 0;\n-\t\t\tgoto again;\n-\t\t}\n-\t}\n-\treturn hit;\n-}\n-\n-static int match_expr_eval(struct grep_opt *opt,\n-\t\t\t   struct grep_expr *x,\n-\t\t\t   char *bol, char *eol)\n-{\n-\tswitch (x->node) {\n-\tcase GREP_NODE_ATOM:\n-\t\treturn match_one_pattern(opt, x->u.atom, bol, eol);\n-\t\tbreak;\n-\tcase GREP_NODE_NOT:\n-\t\treturn !match_expr_eval(opt, x->u.unary, bol, eol);\n-\tcase GREP_NODE_AND:\n-\t\treturn (match_expr_eval(opt, x->u.binary.left, bol, eol) &&\n-\t\t\tmatch_expr_eval(opt, x->u.binary.right, bol, eol));\n-\tcase GREP_NODE_OR:\n-\t\treturn (match_expr_eval(opt, x->u.binary.left, bol, eol) ||\n-\t\t\tmatch_expr_eval(opt, x->u.binary.right, bol, eol));\n-\t}\n-\tdie(\"Unexpected node type (internal error) %d\\n\", x->node);\n-}\n-\n-static int match_expr(struct grep_opt *opt, char *bol, char *eol)\n-{\n-\tstruct grep_expr *x = opt->pattern_expression;\n-\treturn match_expr_eval(opt, x, bol, eol);\n-}\n-\n-static int match_line(struct grep_opt *opt, char *bol, char *eol)\n-{\n-\tstruct grep_pat *p;\n-\tif (opt->extended)\n-\t\treturn match_expr(opt, bol, eol);\n-\tfor (p = opt->pattern_list; p; p = p->next) {\n-\t\tif (match_one_pattern(opt, p, bol, eol))\n-\t\t\treturn 1;\n-\t}\n-\treturn 0;\n-}\n-\n-static int grep_buffer(struct grep_opt *opt, const char *name,\n-\t\t       char *buf, unsigned long size)\n-{\n-\tchar *bol = buf;\n-\tunsigned long left = size;\n-\tunsigned lno = 1;\n-\tstruct pre_context_line {\n-\t\tchar *bol;\n-\t\tchar *eol;\n-\t} *prev = NULL, *pcl;\n-\tunsigned last_hit = 0;\n-\tunsigned last_shown = 0;\n-\tint binary_match_only = 0;\n-\tconst char *hunk_mark = \"\";\n-\tunsigned count = 0;\n-\n-\tif (buffer_is_binary(buf, size)) {\n-\t\tswitch (opt->binary) {\n-\t\tcase GREP_BINARY_DEFAULT:\n-\t\t\tbinary_match_only = 1;\n-\t\t\tbreak;\n-\t\tcase GREP_BINARY_NOMATCH:\n-\t\t\treturn 0; /* Assume unmatch */\n-\t\t\tbreak;\n-\t\tdefault:\n-\t\t\tbreak;\n-\t\t}\n-\t}\n-\n-\tif (opt->pre_context)\n-\t\tprev = xcalloc(opt->pre_context, sizeof(*prev));\n-\tif (opt->pre_context || opt->post_context)\n-\t\thunk_mark = \"--\\n\";\n-\n-\twhile (left) {\n-\t\tchar *eol, ch;\n-\t\tint hit = 0;\n-\n-\t\teol = end_of_line(bol, &left);\n-\t\tch = *eol;\n-\t\t*eol = 0;\n-\n-\t\thit = match_line(opt, bol, eol);\n-\n-\t\t/* \"grep -v -e foo -e bla\" should list lines\n-\t\t * that do not have either, so inversion should\n-\t\t * be done outside.\n-\t\t */\n-\t\tif (opt->invert)\n-\t\t\thit = !hit;\n-\t\tif (opt->unmatch_name_only) {\n-\t\t\tif (hit)\n-\t\t\t\treturn 0;\n-\t\t\tgoto next_line;\n-\t\t}\n-\t\tif (hit) {\n-\t\t\tcount++;\n-\t\t\tif (binary_match_only) {\n-\t\t\t\tprintf(\"Binary file %s matches\\n\", name);\n-\t\t\t\treturn 1;\n-\t\t\t}\n-\t\t\tif (opt->name_only) {\n-\t\t\t\tprintf(\"%s\\n\", name);\n-\t\t\t\treturn 1;\n-\t\t\t}\n-\t\t\t/* Hit at this line.  If we haven't shown the\n-\t\t\t * pre-context lines, we would need to show them.\n-\t\t\t * When asked to do \"count\", this still show\n-\t\t\t * the context which is nonsense, but the user\n-\t\t\t * deserves to get that ;-).\n-\t\t\t */\n-\t\t\tif (opt->pre_context) {\n-\t\t\t\tunsigned from;\n-\t\t\t\tif (opt->pre_context < lno)\n-\t\t\t\t\tfrom = lno - opt->pre_context;\n-\t\t\t\telse\n-\t\t\t\t\tfrom = 1;\n-\t\t\t\tif (from <= last_shown)\n-\t\t\t\t\tfrom = last_shown + 1;\n-\t\t\t\tif (last_shown && from != last_shown + 1)\n-\t\t\t\t\tprintf(hunk_mark);\n-\t\t\t\twhile (from < lno) {\n-\t\t\t\t\tpcl = &prev[lno-from-1];\n-\t\t\t\t\tshow_line(opt, pcl->bol, pcl->eol,\n-\t\t\t\t\t\t  name, from, '-');\n-\t\t\t\t\tfrom++;\n-\t\t\t\t}\n-\t\t\t\tlast_shown = lno-1;\n-\t\t\t}\n-\t\t\tif (last_shown && lno != last_shown + 1)\n-\t\t\t\tprintf(hunk_mark);\n-\t\t\tif (!opt->count)\n-\t\t\t\tshow_line(opt, bol, eol, name, lno, ':');\n-\t\t\tlast_shown = last_hit = lno;\n-\t\t}\n-\t\telse if (last_hit &&\n-\t\t\t lno <= last_hit + opt->post_context) {\n-\t\t\t/* If the last hit is within the post context,\n-\t\t\t * we need to show this line.\n-\t\t\t */\n-\t\t\tif (last_shown && lno != last_shown + 1)\n-\t\t\t\tprintf(hunk_mark);\n-\t\t\tshow_line(opt, bol, eol, name, lno, '-');\n-\t\t\tlast_shown = lno;\n-\t\t}\n-\t\tif (opt->pre_context) {\n-\t\t\tmemmove(prev+1, prev,\n-\t\t\t\t(opt->pre_context-1) * sizeof(*prev));\n-\t\t\tprev->bol = bol;\n-\t\t\tprev->eol = eol;\n-\t\t}\n-\n-\tnext_line:\n-\t\t*eol = ch;\n-\t\tbol = eol + 1;\n-\t\tif (!left)\n-\t\t\tbreak;\n-\t\tleft--;\n-\t\tlno++;\n-\t}\n-\n-\tif (opt->unmatch_name_only) {\n-\t\t/* We did not see any hit, so we want to show this */\n-\t\tprintf(\"%s\\n\", name);\n-\t\treturn 1;\n-\t}\n-\n-\t/* NEEDSWORK:\n-\t * The real \"grep -c foo *.c\" gives many \"bar.c:0\" lines,\n-\t * which feels mostly useless but sometimes useful.  Maybe\n-\t * make it another option?  For now suppress them.\n-\t */\n-\tif (opt->count && count)\n-\t\tprintf(\"%s:%u\\n\", name, count);\n-\treturn !!last_hit;\n-}\n-\n static int grep_sha1(struct grep_opt *opt, const unsigned char *sha1, const char *name, int tree_name_len)\n {\n \tunsigned long size;\n@@ -1055,8 +564,9 @@ int cmd_grep(int argc, const char **argv\n \t\t\t\t/* ignore empty line like grep does */\n \t\t\t\tif (!buf[0])\n \t\t\t\t\tcontinue;\n-\t\t\t\tadd_pattern(&opt, xstrdup(buf), argv[1], ++lno,\n-\t\t\t\t\t    GREP_PATTERN);\n+\t\t\t\tappend_grep_pattern(&opt, xstrdup(buf),\n+\t\t\t\t\t\t    argv[1], ++lno,\n+\t\t\t\t\t\t    GREP_PATTERN);\n \t\t\t}\n \t\t\tfclose(patterns);\n \t\t\targv++;\n@@ -1064,27 +574,32 @@ int cmd_grep(int argc, const char **argv\n \t\t\tcontinue;\n \t\t}\n \t\tif (!strcmp(\"--not\", arg)) {\n-\t\t\tadd_pattern(&opt, arg, \"command line\", 0, GREP_NOT);\n+\t\t\tappend_grep_pattern(&opt, arg, \"command line\", 0,\n+\t\t\t\t\t    GREP_NOT);\n \t\t\tcontinue;\n \t\t}\n \t\tif (!strcmp(\"--and\", arg)) {\n-\t\t\tadd_pattern(&opt, arg, \"command line\", 0, GREP_AND);\n+\t\t\tappend_grep_pattern(&opt, arg, \"command line\", 0,\n+\t\t\t\t\t    GREP_AND);\n \t\t\tcontinue;\n \t\t}\n \t\tif (!strcmp(\"--or\", arg))\n \t\t\tcontinue; /* no-op */\n \t\tif (!strcmp(\"(\", arg)) {\n-\t\t\tadd_pattern(&opt, arg, \"command line\", 0, GREP_OPEN_PAREN);\n+\t\t\tappend_grep_pattern(&opt, arg, \"command line\", 0,\n+\t\t\t\t\t    GREP_OPEN_PAREN);\n \t\t\tcontinue;\n \t\t}\n \t\tif (!strcmp(\")\", arg)) {\n-\t\t\tadd_pattern(&opt, arg, \"command line\", 0, GREP_CLOSE_PAREN);\n+\t\t\tappend_grep_pattern(&opt, arg, \"command line\", 0,\n+\t\t\t\t\t    GREP_CLOSE_PAREN);\n \t\t\tcontinue;\n \t\t}\n \t\tif (!strcmp(\"-e\", arg)) {\n \t\t\tif (1 < argc) {\n-\t\t\t\tadd_pattern(&opt, argv[1], \"-e option\", 0,\n-\t\t\t\t\t    GREP_PATTERN);\n+\t\t\t\tappend_grep_pattern(&opt, argv[1],\n+\t\t\t\t\t\t    \"-e option\", 0,\n+\t\t\t\t\t\t    GREP_PATTERN);\n \t\t\t\targv++;\n \t\t\t\targc--;\n \t\t\t\tcontinue;\n@@ -1106,8 +621,8 @@ int cmd_grep(int argc, const char **argv\n \n \t\t/* First unrecognized non-option token */\n \t\tif (!opt.pattern_list) {\n-\t\t\tadd_pattern(&opt, arg, \"command line\", 0,\n-\t\t\t\t    GREP_PATTERN);\n+\t\t\tappend_grep_pattern(&opt, arg, \"command line\", 0,\n+\t\t\t\t\t    GREP_PATTERN);\n \t\t\tbreak;\n \t\t}\n \t\telse {\n@@ -1124,8 +639,7 @@ int cmd_grep(int argc, const char **argv\n \t\tdie(\"no pattern given.\");\n \tif ((opt.regflags != REG_NEWLINE) && opt.fixed)\n \t\tdie(\"cannot mix --fixed-strings and regexp\");\n-\tif (!opt.fixed)\n-\t\tcompile_patterns(&opt);\n+\tcompile_grep_patterns(&opt);\n \n \t/* Check revs and then paths */\n \tfor (i = 1; i < argc; i++) {\ndiff --git a/grep.c b/grep.c\nnew file mode 100644\nindex 0000000..61db6e1\n--- /dev/null\n+++ b/grep.c\n@@ -0,0 +1,440 @@\n+#include \"cache.h\"\n+#include <regex.h>\n+#include \"grep.h\"\n+\n+void append_grep_pattern(struct grep_opt *opt, const char *pat,\n+\t\t\t const char *origin, int no, enum grep_pat_token t)\n+{\n+\tstruct grep_pat *p = xcalloc(1, sizeof(*p));\n+\tp->pattern = pat;\n+\tp->origin = origin;\n+\tp->no = no;\n+\tp->token = t;\n+\t*opt->pattern_tail = p;\n+\topt->pattern_tail = &p->next;\n+\tp->next = NULL;\n+}\n+\n+static void compile_regexp(struct grep_pat *p, struct grep_opt *opt)\n+{\n+\tint err = regcomp(&p->regexp, p->pattern, opt->regflags);\n+\tif (err) {\n+\t\tchar errbuf[1024];\n+\t\tchar where[1024];\n+\t\tif (p->no)\n+\t\t\tsprintf(where, \"In '%s' at %d, \",\n+\t\t\t\tp->origin, p->no);\n+\t\telse if (p->origin)\n+\t\t\tsprintf(where, \"%s, \", p->origin);\n+\t\telse\n+\t\t\twhere[0] = 0;\n+\t\tregerror(err, &p->regexp, errbuf, 1024);\n+\t\tregfree(&p->regexp);\n+\t\tdie(\"%s'%s': %s\", where, p->pattern, errbuf);\n+\t}\n+}\n+\n+static struct grep_expr *compile_pattern_expr(struct grep_pat **);\n+static struct grep_expr *compile_pattern_atom(struct grep_pat **list)\n+{\n+\tstruct grep_pat *p;\n+\tstruct grep_expr *x;\n+\n+\tp = *list;\n+\tswitch (p->token) {\n+\tcase GREP_PATTERN: /* atom */\n+\t\tx = xcalloc(1, sizeof (struct grep_expr));\n+\t\tx->node = GREP_NODE_ATOM;\n+\t\tx->u.atom = p;\n+\t\t*list = p->next;\n+\t\treturn x;\n+\tcase GREP_OPEN_PAREN:\n+\t\t*list = p->next;\n+\t\tx = compile_pattern_expr(list);\n+\t\tif (!x)\n+\t\t\treturn NULL;\n+\t\tif (!*list || (*list)->token != GREP_CLOSE_PAREN)\n+\t\t\tdie(\"unmatched parenthesis\");\n+\t\t*list = (*list)->next;\n+\t\treturn x;\n+\tdefault:\n+\t\treturn NULL;\n+\t}\n+}\n+\n+static struct grep_expr *compile_pattern_not(struct grep_pat **list)\n+{\n+\tstruct grep_pat *p;\n+\tstruct grep_expr *x;\n+\n+\tp = *list;\n+\tswitch (p->token) {\n+\tcase GREP_NOT:\n+\t\tif (!p->next)\n+\t\t\tdie(\"--not not followed by pattern expression\");\n+\t\t*list = p->next;\n+\t\tx = xcalloc(1, sizeof (struct grep_expr));\n+\t\tx->node = GREP_NODE_NOT;\n+\t\tx->u.unary = compile_pattern_not(list);\n+\t\tif (!x->u.unary)\n+\t\t\tdie(\"--not followed by non pattern expression\");\n+\t\treturn x;\n+\tdefault:\n+\t\treturn compile_pattern_atom(list);\n+\t}\n+}\n+\n+static struct grep_expr *compile_pattern_and(struct grep_pat **list)\n+{\n+\tstruct grep_pat *p;\n+\tstruct grep_expr *x, *y, *z;\n+\n+\tx = compile_pattern_not(list);\n+\tp = *list;\n+\tif (p && p->token == GREP_AND) {\n+\t\tif (!p->next)\n+\t\t\tdie(\"--and not followed by pattern expression\");\n+\t\t*list = p->next;\n+\t\ty = compile_pattern_and(list);\n+\t\tif (!y)\n+\t\t\tdie(\"--and not followed by pattern expression\");\n+\t\tz = xcalloc(1, sizeof (struct grep_expr));\n+\t\tz->node = GREP_NODE_AND;\n+\t\tz->u.binary.left = x;\n+\t\tz->u.binary.right = y;\n+\t\treturn z;\n+\t}\n+\treturn x;\n+}\n+\n+static struct grep_expr *compile_pattern_or(struct grep_pat **list)\n+{\n+\tstruct grep_pat *p;\n+\tstruct grep_expr *x, *y, *z;\n+\n+\tx = compile_pattern_and(list);\n+\tp = *list;\n+\tif (x && p && p->token != GREP_CLOSE_PAREN) {\n+\t\ty = compile_pattern_or(list);\n+\t\tif (!y)\n+\t\t\tdie(\"not a pattern expression %s\", p->pattern);\n+\t\tz = xcalloc(1, sizeof (struct grep_expr));\n+\t\tz->node = GREP_NODE_OR;\n+\t\tz->u.binary.left = x;\n+\t\tz->u.binary.right = y;\n+\t\treturn z;\n+\t}\n+\treturn x;\n+}\n+\n+static struct grep_expr *compile_pattern_expr(struct grep_pat **list)\n+{\n+\treturn compile_pattern_or(list);\n+}\n+\n+void compile_grep_patterns(struct grep_opt *opt)\n+{\n+\tstruct grep_pat *p;\n+\n+\tif (opt->fixed)\n+\t\treturn;\n+\n+\t/* First compile regexps */\n+\tfor (p = opt->pattern_list; p; p = p->next) {\n+\t\tif (p->token == GREP_PATTERN)\n+\t\t\tcompile_regexp(p, opt);\n+\t\telse\n+\t\t\topt->extended = 1;\n+\t}\n+\n+\tif (!opt->extended)\n+\t\treturn;\n+\n+\t/* Then bundle them up in an expression.\n+\t * A classic recursive descent parser would do.\n+\t */\n+\tp = opt->pattern_list;\n+\topt->pattern_expression = compile_pattern_expr(&p);\n+\tif (p)\n+\t\tdie(\"incomplete pattern expression: %s\", p->pattern);\n+}\n+\n+static char *end_of_line(char *cp, unsigned long *left)\n+{\n+\tunsigned long l = *left;\n+\twhile (l && *cp != '\\n') {\n+\t\tl--;\n+\t\tcp++;\n+\t}\n+\t*left = l;\n+\treturn cp;\n+}\n+\n+static int word_char(char ch)\n+{\n+\treturn isalnum(ch) || ch == '_';\n+}\n+\n+static void show_line(struct grep_opt *opt, const char *bol, const char *eol,\n+\t\t      const char *name, unsigned lno, char sign)\n+{\n+\tif (opt->pathname)\n+\t\tprintf(\"%s%c\", name, sign);\n+\tif (opt->linenum)\n+\t\tprintf(\"%d%c\", lno, sign);\n+\tprintf(\"%.*s\\n\", (int)(eol-bol), bol);\n+}\n+\n+/*\n+ * NEEDSWORK: share code with diff.c\n+ */\n+#define FIRST_FEW_BYTES 8000\n+static int buffer_is_binary(const char *ptr, unsigned long size)\n+{\n+\tif (FIRST_FEW_BYTES < size)\n+\t\tsize = FIRST_FEW_BYTES;\n+\treturn !!memchr(ptr, 0, size);\n+}\n+\n+static int fixmatch(const char *pattern, char *line, regmatch_t *match)\n+{\n+\tchar *hit = strstr(line, pattern);\n+\tif (!hit) {\n+\t\tmatch->rm_so = match->rm_eo = -1;\n+\t\treturn REG_NOMATCH;\n+\t}\n+\telse {\n+\t\tmatch->rm_so = hit - line;\n+\t\tmatch->rm_eo = match->rm_so + strlen(pattern);\n+\t\treturn 0;\n+\t}\n+}\n+\n+static int match_one_pattern(struct grep_opt *opt, struct grep_pat *p, char *bol, char *eol)\n+{\n+\tint hit = 0;\n+\tint at_true_bol = 1;\n+\tregmatch_t pmatch[10];\n+\n+ again:\n+\tif (!opt->fixed) {\n+\t\tregex_t *exp = &p->regexp;\n+\t\thit = !regexec(exp, bol, ARRAY_SIZE(pmatch),\n+\t\t\t       pmatch, 0);\n+\t}\n+\telse {\n+\t\thit = !fixmatch(p->pattern, bol, pmatch);\n+\t}\n+\n+\tif (hit && opt->word_regexp) {\n+\t\tif ((pmatch[0].rm_so < 0) ||\n+\t\t    (eol - bol) <= pmatch[0].rm_so ||\n+\t\t    (pmatch[0].rm_eo < 0) ||\n+\t\t    (eol - bol) < pmatch[0].rm_eo)\n+\t\t\tdie(\"regexp returned nonsense\");\n+\n+\t\t/* Match beginning must be either beginning of the\n+\t\t * line, or at word boundary (i.e. the last char must\n+\t\t * not be a word char).  Similarly, match end must be\n+\t\t * either end of the line, or at word boundary\n+\t\t * (i.e. the next char must not be a word char).\n+\t\t */\n+\t\tif ( ((pmatch[0].rm_so == 0 && at_true_bol) ||\n+\t\t      !word_char(bol[pmatch[0].rm_so-1])) &&\n+\t\t     ((pmatch[0].rm_eo == (eol-bol)) ||\n+\t\t      !word_char(bol[pmatch[0].rm_eo])) )\n+\t\t\t;\n+\t\telse\n+\t\t\thit = 0;\n+\n+\t\tif (!hit && pmatch[0].rm_so + bol + 1 < eol) {\n+\t\t\t/* There could be more than one match on the\n+\t\t\t * line, and the first match might not be\n+\t\t\t * strict word match.  But later ones could be!\n+\t\t\t */\n+\t\t\tbol = pmatch[0].rm_so + bol + 1;\n+\t\t\tat_true_bol = 0;\n+\t\t\tgoto again;\n+\t\t}\n+\t}\n+\treturn hit;\n+}\n+\n+static int match_expr_eval(struct grep_opt *opt,\n+\t\t\t   struct grep_expr *x,\n+\t\t\t   char *bol, char *eol)\n+{\n+\tswitch (x->node) {\n+\tcase GREP_NODE_ATOM:\n+\t\treturn match_one_pattern(opt, x->u.atom, bol, eol);\n+\t\tbreak;\n+\tcase GREP_NODE_NOT:\n+\t\treturn !match_expr_eval(opt, x->u.unary, bol, eol);\n+\tcase GREP_NODE_AND:\n+\t\treturn (match_expr_eval(opt, x->u.binary.left, bol, eol) &&\n+\t\t\tmatch_expr_eval(opt, x->u.binary.right, bol, eol));\n+\tcase GREP_NODE_OR:\n+\t\treturn (match_expr_eval(opt, x->u.binary.left, bol, eol) ||\n+\t\t\tmatch_expr_eval(opt, x->u.binary.right, bol, eol));\n+\t}\n+\tdie(\"Unexpected node type (internal error) %d\\n\", x->node);\n+}\n+\n+static int match_expr(struct grep_opt *opt, char *bol, char *eol)\n+{\n+\tstruct grep_expr *x = opt->pattern_expression;\n+\treturn match_expr_eval(opt, x, bol, eol);\n+}\n+\n+static int match_line(struct grep_opt *opt, char *bol, char *eol)\n+{\n+\tstruct grep_pat *p;\n+\tif (opt->extended)\n+\t\treturn match_expr(opt, bol, eol);\n+\tfor (p = opt->pattern_list; p; p = p->next) {\n+\t\tif (match_one_pattern(opt, p, bol, eol))\n+\t\t\treturn 1;\n+\t}\n+\treturn 0;\n+}\n+\n+int grep_buffer(struct grep_opt *opt, const char *name, char *buf, unsigned long size)\n+{\n+\tchar *bol = buf;\n+\tunsigned long left = size;\n+\tunsigned lno = 1;\n+\tstruct pre_context_line {\n+\t\tchar *bol;\n+\t\tchar *eol;\n+\t} *prev = NULL, *pcl;\n+\tunsigned last_hit = 0;\n+\tunsigned last_shown = 0;\n+\tint binary_match_only = 0;\n+\tconst char *hunk_mark = \"\";\n+\tunsigned count = 0;\n+\n+\tif (buffer_is_binary(buf, size)) {\n+\t\tswitch (opt->binary) {\n+\t\tcase GREP_BINARY_DEFAULT:\n+\t\t\tbinary_match_only = 1;\n+\t\t\tbreak;\n+\t\tcase GREP_BINARY_NOMATCH:\n+\t\t\treturn 0; /* Assume unmatch */\n+\t\t\tbreak;\n+\t\tdefault:\n+\t\t\tbreak;\n+\t\t}\n+\t}\n+\n+\tif (opt->pre_context)\n+\t\tprev = xcalloc(opt->pre_context, sizeof(*prev));\n+\tif (opt->pre_context || opt->post_context)\n+\t\thunk_mark = \"--\\n\";\n+\n+\twhile (left) {\n+\t\tchar *eol, ch;\n+\t\tint hit = 0;\n+\n+\t\teol = end_of_line(bol, &left);\n+\t\tch = *eol;\n+\t\t*eol = 0;\n+\n+\t\thit = match_line(opt, bol, eol);\n+\t\t*eol = ch;\n+\n+\t\t/* \"grep -v -e foo -e bla\" should list lines\n+\t\t * that do not have either, so inversion should\n+\t\t * be done outside.\n+\t\t */\n+\t\tif (opt->invert)\n+\t\t\thit = !hit;\n+\t\tif (opt->unmatch_name_only) {\n+\t\t\tif (hit)\n+\t\t\t\treturn 0;\n+\t\t\tgoto next_line;\n+\t\t}\n+\t\tif (hit) {\n+\t\t\tcount++;\n+\t\t\tif (opt->status_only)\n+\t\t\t\treturn 1;\n+\t\t\tif (binary_match_only) {\n+\t\t\t\tprintf(\"Binary file %s matches\\n\", name);\n+\t\t\t\treturn 1;\n+\t\t\t}\n+\t\t\tif (opt->name_only) {\n+\t\t\t\tprintf(\"%s\\n\", name);\n+\t\t\t\treturn 1;\n+\t\t\t}\n+\t\t\t/* Hit at this line.  If we haven't shown the\n+\t\t\t * pre-context lines, we would need to show them.\n+\t\t\t * When asked to do \"count\", this still show\n+\t\t\t * the context which is nonsense, but the user\n+\t\t\t * deserves to get that ;-).\n+\t\t\t */\n+\t\t\tif (opt->pre_context) {\n+\t\t\t\tunsigned from;\n+\t\t\t\tif (opt->pre_context < lno)\n+\t\t\t\t\tfrom = lno - opt->pre_context;\n+\t\t\t\telse\n+\t\t\t\t\tfrom = 1;\n+\t\t\t\tif (from <= last_shown)\n+\t\t\t\t\tfrom = last_shown + 1;\n+\t\t\t\tif (last_shown && from != last_shown + 1)\n+\t\t\t\t\tprintf(hunk_mark);\n+\t\t\t\twhile (from < lno) {\n+\t\t\t\t\tpcl = &prev[lno-from-1];\n+\t\t\t\t\tshow_line(opt, pcl->bol, pcl->eol,\n+\t\t\t\t\t\t  name, from, '-');\n+\t\t\t\t\tfrom++;\n+\t\t\t\t}\n+\t\t\t\tlast_shown = lno-1;\n+\t\t\t}\n+\t\t\tif (last_shown && lno != last_shown + 1)\n+\t\t\t\tprintf(hunk_mark);\n+\t\t\tif (!opt->count)\n+\t\t\t\tshow_line(opt, bol, eol, name, lno, ':');\n+\t\t\tlast_shown = last_hit = lno;\n+\t\t}\n+\t\telse if (last_hit &&\n+\t\t\t lno <= last_hit + opt->post_context) {\n+\t\t\t/* If the last hit is within the post context,\n+\t\t\t * we need to show this line.\n+\t\t\t */\n+\t\t\tif (last_shown && lno != last_shown + 1)\n+\t\t\t\tprintf(hunk_mark);\n+\t\t\tshow_line(opt, bol, eol, name, lno, '-');\n+\t\t\tlast_shown = lno;\n+\t\t}\n+\t\tif (opt->pre_context) {\n+\t\t\tmemmove(prev+1, prev,\n+\t\t\t\t(opt->pre_context-1) * sizeof(*prev));\n+\t\t\tprev->bol = bol;\n+\t\t\tprev->eol = eol;\n+\t\t}\n+\n+\tnext_line:\n+\t\tbol = eol + 1;\n+\t\tif (!left)\n+\t\t\tbreak;\n+\t\tleft--;\n+\t\tlno++;\n+\t}\n+\n+\tif (opt->status_only)\n+\t\treturn 0;\n+\tif (opt->unmatch_name_only) {\n+\t\t/* We did not see any hit, so we want to show this */\n+\t\tprintf(\"%s\\n\", name);\n+\t\treturn 1;\n+\t}\n+\n+\t/* NEEDSWORK:\n+\t * The real \"grep -c foo *.c\" gives many \"bar.c:0\" lines,\n+\t * which feels mostly useless but sometimes useful.  Maybe\n+\t * make it another option?  For now suppress them.\n+\t */\n+\tif (opt->count && count)\n+\t\tprintf(\"%s:%u\\n\", name, count);\n+\treturn !!last_hit;\n+}\n+\ndiff --git a/grep.h b/grep.h\nnew file mode 100644\nindex 0000000..80122b0\n--- /dev/null\n+++ b/grep.h\n@@ -0,0 +1,71 @@\n+#ifndef GREP_H\n+#define GREP_H\n+\n+enum grep_pat_token {\n+\tGREP_PATTERN,\n+\tGREP_AND,\n+\tGREP_OPEN_PAREN,\n+\tGREP_CLOSE_PAREN,\n+\tGREP_NOT,\n+\tGREP_OR,\n+};\n+\n+struct grep_pat {\n+\tstruct grep_pat *next;\n+\tconst char *origin;\n+\tint no;\n+\tenum grep_pat_token token;\n+\tconst char *pattern;\n+\tregex_t regexp;\n+};\n+\n+enum grep_expr_node {\n+\tGREP_NODE_ATOM,\n+\tGREP_NODE_NOT,\n+\tGREP_NODE_AND,\n+\tGREP_NODE_OR,\n+};\n+\n+struct grep_expr {\n+\tenum grep_expr_node node;\n+\tunion {\n+\t\tstruct grep_pat *atom;\n+\t\tstruct grep_expr *unary;\n+\t\tstruct {\n+\t\t\tstruct grep_expr *left;\n+\t\t\tstruct grep_expr *right;\n+\t\t} binary;\n+\t} u;\n+};\n+\n+struct grep_opt {\n+\tstruct grep_pat *pattern_list;\n+\tstruct grep_pat **pattern_tail;\n+\tstruct grep_expr *pattern_expression;\n+\tint prefix_length;\n+\tregex_t regexp;\n+\tunsigned linenum:1;\n+\tunsigned invert:1;\n+\tunsigned status_only:1;\n+\tunsigned name_only:1;\n+\tunsigned unmatch_name_only:1;\n+\tunsigned count:1;\n+\tunsigned word_regexp:1;\n+\tunsigned fixed:1;\n+#define GREP_BINARY_DEFAULT\t0\n+#define GREP_BINARY_NOMATCH\t1\n+#define GREP_BINARY_TEXT\t2\n+\tunsigned binary:2;\n+\tunsigned extended:1;\n+\tunsigned relative:1;\n+\tunsigned pathname:1;\n+\tint regflags;\n+\tunsigned pre_context;\n+\tunsigned post_context;\n+};\n+\n+extern void append_grep_pattern(struct grep_opt *opt, const char *pat, const char *origin, int no, enum grep_pat_token t);\n+extern void compile_grep_patterns(struct grep_opt *opt);\n+extern int grep_buffer(struct grep_opt *opt, const char *name, char *buf, unsigned long size);\n+\n+#endif\n-- \n1.4.2.1.g414e5\n"}]}