diff options
Diffstat (limited to 'src/regexp_nfa.c')
-rw-r--r-- | src/regexp_nfa.c | 305 |
1 files changed, 119 insertions, 186 deletions
diff --git a/src/regexp_nfa.c b/src/regexp_nfa.c index 96d6a01a90..75deff1b3e 100644 --- a/src/regexp_nfa.c +++ b/src/regexp_nfa.c @@ -5,6 +5,8 @@ * This file is included in "regexp.c". */ +#include "misc2.h" + /* * Logging of NFA engine. * @@ -327,9 +329,11 @@ static int failure_chance __ARGS((nfa_state_T *state, int depth)); * Initialize internal variables before NFA compilation. * Return OK on success, FAIL otherwise. */ -static int nfa_regcomp_start(expr, re_flags) -char_u *expr; -int re_flags; /* see vim_regcomp() */ +static int +nfa_regcomp_start ( + char_u *expr, + int re_flags /* see vim_regcomp() */ +) { size_t postfix_size; int nstate_max; @@ -364,9 +368,7 @@ int re_flags; /* see vim_regcomp() */ * Figure out if the NFA state list starts with an anchor, must match at start * of the line. */ -static int nfa_get_reganch(start, depth) -nfa_state_T *start; -int depth; +static int nfa_get_reganch(nfa_state_T *start, int depth) { nfa_state_T *p = start; @@ -423,9 +425,7 @@ int depth; * Figure out if the NFA state list starts with a character which must match * at start of the match. */ -static int nfa_get_regstart(start, depth) -nfa_state_T *start; -int depth; +static int nfa_get_regstart(nfa_state_T *start, int depth) { nfa_state_T *p = start; @@ -504,8 +504,7 @@ int depth; * else. If so return a string in allocated memory with what must match after * regstart. Otherwise return NULL. */ -static char_u * nfa_get_match_text(start) -nfa_state_T *start; +static char_u *nfa_get_match_text(nfa_state_T *start) { nfa_state_T *p = start; int len = 0; @@ -543,7 +542,7 @@ nfa_state_T *start; * Allocate more space for post_start. Called when * running above the estimated number of states. */ -static int realloc_post_list() { +static int realloc_post_list(void) { int nstate_max = (int)(post_end - post_start); int new_max = nstate_max + 1000; int *new_start; @@ -571,10 +570,7 @@ static int realloc_post_list() { * Keep in mind that 'ignorecase' applies at execution time, thus [a-z] may * need to be interpreted as [a-zA-Z]. */ -static int nfa_recognize_char_class(start, end, extra_newl) -char_u *start; -char_u *end; -int extra_newl; +static int nfa_recognize_char_class(char_u *start, char_u *end, int extra_newl) { # define CLASS_not 0x80 # define CLASS_af 0x40 @@ -696,8 +692,7 @@ int extra_newl; * * NOTE! When changing this function, also update reg_equi_class() */ -static int nfa_emit_equi_class(c) -int c; +static int nfa_emit_equi_class(int c) { #define EMIT2(c) EMIT(c); EMIT(NFA_CONCAT); # define EMITMBC(c) EMIT(c); EMIT(NFA_CONCAT); @@ -1061,7 +1056,7 @@ int c; * or \%( pattern \) * or \z( pattern \) */ -static int nfa_regatom() { +static int nfa_regatom(void) { int c; int charclass; int equiclass; @@ -1740,7 +1735,7 @@ nfa_do_multibyte: * piece ::= atom * or atom multi */ -static int nfa_regpiece() { +static int nfa_regpiece(void) { int i; int op; int ret; @@ -1931,7 +1926,7 @@ static int nfa_regpiece() { * or piece piece piece * etc. */ -static int nfa_regconcat() { +static int nfa_regconcat(void) { int cont = TRUE; int first = TRUE; @@ -2003,7 +1998,7 @@ static int nfa_regconcat() { * or concat \& concat \& concat * etc. */ -static int nfa_regbranch() { +static int nfa_regbranch(void) { int ch; int old_post_pos; @@ -2047,8 +2042,10 @@ static int nfa_regbranch() { * or branch \| branch \| branch * etc. */ -static int nfa_reg(paren) -int paren; /* REG_NOPAREN, REG_PAREN, REG_NPAREN or REG_ZPAREN */ +static int +nfa_reg ( + int paren /* REG_NOPAREN, REG_PAREN, REG_NPAREN or REG_ZPAREN */ +) { int parno = 0; @@ -2101,8 +2098,7 @@ int paren; /* REG_NOPAREN, REG_PAREN, REG_NPAREN or REG_ZPAREN */ #ifdef REGEXP_DEBUG static char_u code[50]; -static void nfa_set_code(c) -int c; +static void nfa_set_code(int c) { int addnl = FALSE; @@ -2330,9 +2326,7 @@ static FILE *log_fd; /* * Print the postfix notation of the current regexp. */ -static void nfa_postfix_dump(expr, retval) -char_u *expr; -int retval; +static void nfa_postfix_dump(char_u *expr, int retval) { int *p; FILE *f; @@ -2360,9 +2354,7 @@ int retval; /* * Print the NFA starting with a root node "state". */ -static void nfa_print_state(debugf, state) -FILE *debugf; -nfa_state_T *state; +static void nfa_print_state(FILE *debugf, nfa_state_T *state) { garray_T indent; @@ -2372,10 +2364,7 @@ nfa_state_T *state; ga_clear(&indent); } -static void nfa_print_state2(debugf, state, indent) -FILE *debugf; -nfa_state_T *state; -garray_T *indent; +static void nfa_print_state2(FILE *debugf, nfa_state_T *state, garray_T *indent) { char_u *p; @@ -2433,8 +2422,7 @@ garray_T *indent; /* * Print the NFA state machine. */ -static void nfa_dump(prog) -nfa_regprog_T *prog; +static void nfa_dump(nfa_regprog_T *prog) { FILE *debugf = fopen(NFA_REGEXP_DUMP_LOG, "a"); @@ -2459,7 +2447,7 @@ nfa_regprog_T *prog; * Parse r.e. @expr and convert it into postfix form. * Return the postfix string on success, NULL otherwise. */ -static int * re2post() { +static int *re2post(void) { if (nfa_reg(REG_NOPAREN) == FAIL) return NULL; EMIT(NFA_MOPEN); @@ -2480,10 +2468,7 @@ static nfa_state_T *state_ptr; /* points to nfa_prog->state */ /* * Allocate and initialize nfa_state_T. */ -static nfa_state_T * alloc_state(c, out, out1) -int c; -nfa_state_T *out; -nfa_state_T *out1; +static nfa_state_T *alloc_state(int c, nfa_state_T *out, nfa_state_T *out1) { nfa_state_T *s; @@ -2536,9 +2521,7 @@ static Frag_T st_pop __ARGS((Frag_T **p, Frag_T *stack)); /* * Initialize a Frag_T struct and return it. */ -static Frag_T frag(start, out) -nfa_state_T *start; -Ptrlist *out; +static Frag_T frag(nfa_state_T *start, Ptrlist *out) { Frag_T n; @@ -2550,8 +2533,7 @@ Ptrlist *out; /* * Create singleton list containing just outp. */ -static Ptrlist * list1(outp) -nfa_state_T **outp; +static Ptrlist *list1(nfa_state_T **outp) { Ptrlist *l; @@ -2563,9 +2545,7 @@ nfa_state_T **outp; /* * Patch the list of states at out to point to start. */ -static void patch(l, s) -Ptrlist *l; -nfa_state_T *s; +static void patch(Ptrlist *l, nfa_state_T *s) { Ptrlist *next; @@ -2579,9 +2559,7 @@ nfa_state_T *s; /* * Join the two lists l1 and l2, returning the combination. */ -static Ptrlist * append(l1, l2) -Ptrlist *l1; -Ptrlist *l2; +static Ptrlist *append(Ptrlist *l1, Ptrlist *l2) { Ptrlist *oldl1; @@ -2597,10 +2575,7 @@ Ptrlist *l2; */ static Frag_T empty; -static void st_error(postfix, end, p) -int *postfix UNUSED; -int *end UNUSED; -int *p UNUSED; +static void st_error(int *postfix, int *end, int *p) { #ifdef NFA_REGEXP_ERROR_LOG FILE *df; @@ -2643,10 +2618,7 @@ int *p UNUSED; /* * Push an item onto the stack. */ -static void st_push(s, p, stack_end) -Frag_T s; -Frag_T **p; -Frag_T *stack_end; +static void st_push(Frag_T s, Frag_T **p, Frag_T *stack_end) { Frag_T *stackp = *p; @@ -2659,9 +2631,7 @@ Frag_T *stack_end; /* * Pop an item from the stack. */ -static Frag_T st_pop(p, stack) -Frag_T **p; -Frag_T *stack; +static Frag_T st_pop(Frag_T **p, Frag_T *stack) { Frag_T *stackp; @@ -2676,9 +2646,7 @@ Frag_T *stack; * Estimate the maximum byte length of anything matching "state". * When unknown or unlimited return -1. */ -static int nfa_max_width(startstate, depth) -nfa_state_T *startstate; -int depth; +static int nfa_max_width(nfa_state_T *startstate, int depth) { int l, r; nfa_state_T *state = startstate; @@ -2888,10 +2856,7 @@ int depth; * Convert a postfix form into its equivalent NFA. * Return the NFA start state on success, NULL otherwise. */ -static nfa_state_T * post2nfa(postfix, end, nfa_calc_size) -int *postfix; -int *end; -int nfa_calc_size; +static nfa_state_T *post2nfa(int *postfix, int *end, int nfa_calc_size) { int *p; int mopen; @@ -3375,8 +3340,7 @@ theend: /* * After building the NFA program, inspect it to add optimization hints. */ -static void nfa_postprocess(prog) -nfa_regprog_T *prog; +static void nfa_postprocess(nfa_regprog_T *prog) { int i; int c; @@ -3489,16 +3453,14 @@ static void log_subsexpr __ARGS((regsubs_T *subs)); static void log_subexpr __ARGS((regsub_T *sub)); static char *pim_info __ARGS((nfa_pim_T *pim)); -static void log_subsexpr(subs) -regsubs_T *subs; +static void log_subsexpr(regsubs_T *subs) { log_subexpr(&subs->norm); if (nfa_has_zsubexpr) log_subexpr(&subs->synt); } -static void log_subexpr(sub) -regsub_T *sub; +static void log_subexpr(regsub_T *sub) { int j; @@ -3521,8 +3483,7 @@ regsub_T *sub; } } -static char * pim_info(pim) -nfa_pim_T *pim; +static char *pim_info(nfa_pim_T *pim) { static char buf[30]; @@ -3563,9 +3524,7 @@ static void addstate_here __ARGS((nfa_list_T *l, nfa_state_T *state, /* * Copy postponed invisible match info from "from" to "to". */ -static void copy_pim(to, from) -nfa_pim_T *to; -nfa_pim_T *from; +static void copy_pim(nfa_pim_T *to, nfa_pim_T *from) { to->result = from->result; to->state = from->state; @@ -3575,8 +3534,7 @@ nfa_pim_T *from; to->end = from->end; } -static void clear_sub(sub) -regsub_T *sub; +static void clear_sub(regsub_T *sub) { if (REG_MULTI) /* Use 0xff to set lnum to -1 */ @@ -3590,9 +3548,7 @@ regsub_T *sub; /* * Copy the submatches from "from" to "to". */ -static void copy_sub(to, from) -regsub_T *to; -regsub_T *from; +static void copy_sub(regsub_T *to, regsub_T *from) { to->in_use = from->in_use; if (from->in_use > 0) { @@ -3611,9 +3567,7 @@ regsub_T *from; /* * Like copy_sub() but exclude the main match. */ -static void copy_sub_off(to, from) -regsub_T *to; -regsub_T *from; +static void copy_sub_off(regsub_T *to, regsub_T *from) { if (to->in_use < from->in_use) to->in_use = from->in_use; @@ -3633,9 +3587,7 @@ regsub_T *from; /* * Like copy_sub() but only do the end of the main match if \ze is present. */ -static void copy_ze_off(to, from) -regsub_T *to; -regsub_T *from; +static void copy_ze_off(regsub_T *to, regsub_T *from) { if (nfa_has_zend) { if (REG_MULTI) { @@ -3651,9 +3603,7 @@ regsub_T *from; /* * Return TRUE if "sub1" and "sub2" have the same start positions. */ -static int sub_equal(sub1, sub2) -regsub_T *sub1; -regsub_T *sub2; +static int sub_equal(regsub_T *sub1, regsub_T *sub2) { int i; int todo; @@ -3723,11 +3673,13 @@ static void report_state(char *action, * Return TRUE if the same state is already in list "l" with the same * positions as "subs". */ -static int has_state_with_pos(l, state, subs, pim) -nfa_list_T *l; /* runtime state list */ -nfa_state_T *state; /* state to update */ -regsubs_T *subs; /* pointers to subexpressions */ -nfa_pim_T *pim; /* postponed match or NULL */ +static int +has_state_with_pos ( + nfa_list_T *l, /* runtime state list */ + nfa_state_T *state, /* state to update */ + regsubs_T *subs, /* pointers to subexpressions */ + nfa_pim_T *pim /* postponed match or NULL */ +) { nfa_thread_T *thread; int i; @@ -3748,9 +3700,7 @@ nfa_pim_T *pim; /* postponed match or NULL */ * Return TRUE if "one" and "two" are equal. That includes when both are not * set. */ -static int pim_equal(one, two) -nfa_pim_T *one; -nfa_pim_T *two; +static int pim_equal(nfa_pim_T *one, nfa_pim_T *two) { int one_unused = (one == NULL || one->result == NFA_PIM_UNUSED); int two_unused = (two == NULL || two->result == NFA_PIM_UNUSED); @@ -3774,9 +3724,7 @@ nfa_pim_T *two; /* * Return TRUE if "state" leads to a NFA_MATCH without advancing the input. */ -static int match_follows(startstate, depth) -nfa_state_T *startstate; -int depth; +static int match_follows(nfa_state_T *startstate, int depth) { nfa_state_T *state = startstate; @@ -3865,10 +3813,12 @@ int depth; /* * Return TRUE if "state" is already in list "l". */ -static int state_in_list(l, state, subs) -nfa_list_T *l; /* runtime state list */ -nfa_state_T *state; /* state to update */ -regsubs_T *subs; /* pointers to subexpressions */ +static int +state_in_list ( + nfa_list_T *l, /* runtime state list */ + nfa_state_T *state, /* state to update */ + regsubs_T *subs /* pointers to subexpressions */ +) { if (state->lastlist[nfa_ll_index] == l->id) { if (!nfa_has_backref || has_state_with_pos(l, state, subs, NULL)) @@ -3882,12 +3832,14 @@ regsubs_T *subs; /* pointers to subexpressions */ * Returns "subs_arg", possibly copied into temp_subs. */ -static regsubs_T * addstate(l, state, subs_arg, pim, off) -nfa_list_T *l; /* runtime state list */ -nfa_state_T *state; /* state to update */ -regsubs_T *subs_arg; /* pointers to subexpressions */ -nfa_pim_T *pim; /* postponed look-behind match */ -int off; /* byte offset, when -1 go to next line */ +static regsubs_T * +addstate ( + nfa_list_T *l, /* runtime state list */ + nfa_state_T *state, /* state to update */ + regsubs_T *subs_arg, /* pointers to subexpressions */ + nfa_pim_T *pim, /* postponed look-behind match */ + int off /* byte offset, when -1 go to next line */ +) { int subidx; nfa_thread_T *thread; @@ -4226,12 +4178,14 @@ skip_add: * This makes sure the order of states to be tried does not change, which * matters for alternatives. */ -static void addstate_here(l, state, subs, pim, ip) -nfa_list_T *l; /* runtime state list */ -nfa_state_T *state; /* state to update */ -regsubs_T *subs; /* pointers to subexpressions */ -nfa_pim_T *pim; /* postponed look-behind match */ -int *ip; +static void +addstate_here ( + nfa_list_T *l, /* runtime state list */ + nfa_state_T *state, /* state to update */ + regsubs_T *subs, /* pointers to subexpressions */ + nfa_pim_T *pim, /* postponed look-behind match */ + int *ip +) { int tlen = l->n; int count; @@ -4290,9 +4244,7 @@ int *ip; /* * Check character class "class" against current character c. */ -static int check_char_class(class, c) -int class; -int c; +static int check_char_class(int class, int c) { switch (class) { case NFA_CLASS_ALNUM: @@ -4372,10 +4324,12 @@ int c; * Check for a match with subexpression "subidx". * Return TRUE if it matches. */ -static int match_backref(sub, subidx, bytelen) -regsub_T *sub; /* pointers to subexpressions */ -int subidx; -int *bytelen; /* out: length of match in bytes */ +static int +match_backref ( + regsub_T *sub, /* pointers to subexpressions */ + int subidx, + int *bytelen /* out: length of match in bytes */ +) { int len; @@ -4428,9 +4382,11 @@ static int match_zref __ARGS((int subidx, int *bytelen)); * Check for a match with \z subexpression "subidx". * Return TRUE if it matches. */ -static int match_zref(subidx, bytelen) -int subidx; -int *bytelen; /* out: length of match in bytes */ +static int +match_zref ( + int subidx, + int *bytelen /* out: length of match in bytes */ +) { int len; @@ -4454,9 +4410,7 @@ int *bytelen; /* out: length of match in bytes */ * Also reset the IDs to zero. * Only used for the recursive value lastlist[1]. */ -static void nfa_save_listids(prog, list) -nfa_regprog_T *prog; -int *list; +static void nfa_save_listids(nfa_regprog_T *prog, int *list) { int i; nfa_state_T *p; @@ -4473,9 +4427,7 @@ int *list; /* * Restore list IDs from "list" to all NFA states. */ -static void nfa_restore_listids(prog, list) -nfa_regprog_T *prog; -int *list; +static void nfa_restore_listids(nfa_regprog_T *prog, int *list) { int i; nfa_state_T *p; @@ -4487,10 +4439,7 @@ int *list; } } -static int nfa_re_num_cmp(val, op, pos) -long_u val; -int op; -long_u pos; +static int nfa_re_num_cmp(long_u val, int op, long_u pos) { if (op == 1) return pos > val; if (op == 2) return pos < val; @@ -4510,13 +4459,7 @@ static int nfa_regmatch __ARGS((nfa_regprog_T *prog, nfa_state_T *start, * "pim" is NULL or contains info about a Postponed Invisible Match (start * position). */ -static int recursive_regmatch(state, pim, prog, submatch, m, listids) -nfa_state_T *state; -nfa_pim_T *pim; -nfa_regprog_T *prog; -regsubs_T *submatch; -regsubs_T *m; -int **listids; +static int recursive_regmatch(nfa_state_T *state, nfa_pim_T *pim, nfa_regprog_T *prog, regsubs_T *submatch, regsubs_T *m, int **listids) { int save_reginput_col = (int)(reginput - regline); int save_reglnum = reglnum; @@ -4666,9 +4609,7 @@ static long find_match_text __ARGS((colnr_T startcol, int regstart, * NFA_ANY: 1 * specific character: 99 */ -static int failure_chance(state, depth) -nfa_state_T *state; -int depth; +static int failure_chance(nfa_state_T *state, int depth) { int c = state->c; int l, r; @@ -4821,9 +4762,7 @@ int depth; /* * Skip until the char "c" we know a match must start with. */ -static int skip_to_start(c, colp) -int c; -colnr_T *colp; +static int skip_to_start(int c, colnr_T *colp) { char_u *s; @@ -4845,10 +4784,7 @@ colnr_T *colp; * Called after skip_to_start() has found regstart. * Returns zero for no match, 1 for a match. */ -static long find_match_text(startcol, regstart, match_text) -colnr_T startcol; -int regstart; -char_u *match_text; +static long find_match_text(colnr_T startcol, int regstart, char_u *match_text) { colnr_T col = startcol; int c1, c2; @@ -4904,11 +4840,7 @@ char_u *match_text; * When there is a match "submatch" contains the positions. * Note: Caller must ensure that: start != NULL. */ -static int nfa_regmatch(prog, start, submatch, m) -nfa_regprog_T *prog; -nfa_state_T *start; -regsubs_T *submatch; -regsubs_T *m; +static int nfa_regmatch(nfa_regprog_T *prog, nfa_state_T *start, regsubs_T *submatch, regsubs_T *m) { int result; int size = 0; @@ -6116,9 +6048,7 @@ theend: * Try match of "prog" with at regline["col"]. * Returns 0 for failure, number of lines contained in the match otherwise. */ -static long nfa_regtry(prog, col) -nfa_regprog_T *prog; -colnr_T col; +static long nfa_regtry(nfa_regprog_T *prog, colnr_T col) { int i; regsubs_T subs, m; @@ -6221,9 +6151,11 @@ colnr_T col; * * Returns 0 for failure, number of lines contained in the match otherwise. */ -static long nfa_regexec_both(line, startcol) -char_u *line; -colnr_T startcol; /* column to start looking for match */ +static long +nfa_regexec_both ( + char_u *line, + colnr_T startcol /* column to start looking for match */ +) { nfa_regprog_T *prog; long retval = 0L; @@ -6319,9 +6251,7 @@ theend: * Compile a regular expression into internal code for the NFA matcher. * Returns the program in allocated space. Returns NULL for an error. */ -static regprog_T * nfa_regcomp(expr, re_flags) -char_u *expr; -int re_flags; +static regprog_T *nfa_regcomp(char_u *expr, int re_flags) { nfa_regprog_T *prog = NULL; size_t prog_size; @@ -6435,8 +6365,7 @@ fail: /* * Free a compiled regexp program, returned by nfa_regcomp(). */ -static void nfa_regfree(prog) -regprog_T *prog; +static void nfa_regfree(regprog_T *prog) { if (prog != NULL) { vim_free(((nfa_regprog_T *)prog)->match_text); @@ -6454,10 +6383,12 @@ regprog_T *prog; * * Return TRUE if there is a match, FALSE if not. */ -static int nfa_regexec(rmp, line, col) -regmatch_T *rmp; -char_u *line; /* string to match against */ -colnr_T col; /* column to start looking for match */ +static int +nfa_regexec ( + regmatch_T *rmp, + char_u *line, /* string to match against */ + colnr_T col /* column to start looking for match */ +) { reg_match = rmp; reg_mmatch = NULL; @@ -6479,10 +6410,12 @@ static int nfa_regexec_nl __ARGS((regmatch_T *rmp, char_u *line, colnr_T col)); /* * Like nfa_regexec(), but consider a "\n" in "line" to be a line break. */ -static int nfa_regexec_nl(rmp, line, col) -regmatch_T *rmp; -char_u *line; /* string to match against */ -colnr_T col; /* column to start looking for match */ +static int +nfa_regexec_nl ( + regmatch_T *rmp, + char_u *line, /* string to match against */ + colnr_T col /* column to start looking for match */ +) { reg_match = rmp; reg_mmatch = NULL; @@ -6529,7 +6462,7 @@ win_T *win; /* window in which to search or NULL */ buf_T *buf; /* buffer in which to search */ linenr_T lnum; /* nr of line to start looking for match */ colnr_T col; /* column to start looking for match */ -proftime_T *tm UNUSED; /* timeout limit or NULL */ +proftime_T *tm; /* timeout limit or NULL */ { reg_match = NULL; reg_mmatch = rmp; |