Mercurial > vim

comparison src/regexp_nfa.c @ 6328:adfbffe1e642 v7.4.497

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
updated for version 7.4.497 Problem: With some regexp patterns the NFA engine uses many states and becomes very slow. To the user it looks like Vim freezes. Solution: When the number of states reaches a limit fall back to the old engine. (Christian Brabandt)
author Bram Moolenaar <bram@vim.org>
date Wed, 05 Nov 2014 14:27:36 +0100
parents 7f2472960aa1
children 2bb019eb60ca
comparison
equal deleted inserted replaced
6327:896d12bf73c1 6328:adfbffe1e642
5520 thislist = &list[flag]; 5520 thislist = &list[flag];
5521 nextlist = &list[flag ^= 1]; 5521 nextlist = &list[flag ^= 1];
5522 nextlist->n = 0; /* clear nextlist */ 5522 nextlist->n = 0; /* clear nextlist */
5523 nextlist->has_pim = FALSE; 5523 nextlist->has_pim = FALSE;
5524 ++nfa_listid; 5524 ++nfa_listid;
5525 if (prog->re_engine == AUTOMATIC_ENGINE && nfa_listid >= NFA_MAX_STATES)
5526 {
5527 /* too many states, retry with old engine */
5528 nfa_match = NFA_TOO_EXPENSIVE;
5529 goto theend;
5530 }
5531
5525 thislist->id = nfa_listid; 5532 thislist->id = nfa_listid;
5526 nextlist->id = nfa_listid + 1; 5533 nextlist->id = nfa_listid + 1;
5527 5534
5528 #ifdef ENABLE_LOG 5535 #ifdef ENABLE_LOG
5529 fprintf(log_fd, "------------------------------------------\n"); 5536 fprintf(log_fd, "------------------------------------------\n");
5702 * First try matching the invisible match, then what 5709 * First try matching the invisible match, then what
5703 * follows. 5710 * follows.
5704 */ 5711 */
5705 result = recursive_regmatch(t->state, NULL, prog, 5712 result = recursive_regmatch(t->state, NULL, prog,
5706 submatch, m, &listids); 5713 submatch, m, &listids);
5714 if (result == NFA_TOO_EXPENSIVE)
5715 {
5716 nfa_match = result;
5717 goto theend;
5718 }
5707 5719
5708 /* for \@! and \@<! it is a match when the result is 5720 /* for \@! and \@<! it is a match when the result is
5709 * FALSE */ 5721 * FALSE */
5710 if (result != (t->state->c == NFA_START_INVISIBLE_NEG 5722 if (result != (t->state->c == NFA_START_INVISIBLE_NEG
5711 || t->state->c == NFA_START_INVISIBLE_NEG_FIRST 5723 || t->state->c == NFA_START_INVISIBLE_NEG_FIRST
5815 #endif 5827 #endif
5816 5828
5817 /* First try matching the pattern. */ 5829 /* First try matching the pattern. */
5818 result = recursive_regmatch(t->state, NULL, prog, 5830 result = recursive_regmatch(t->state, NULL, prog,
5819 submatch, m, &listids); 5831 submatch, m, &listids);
5832 if (result == NFA_TOO_EXPENSIVE)
5833 {
5834 nfa_match = result;
5835 goto theend;
5836 }
5820 if (result) 5837 if (result)
5821 { 5838 {
5822 int bytelen; 5839 int bytelen;
5823 5840
5824 #ifdef ENABLE_LOG 5841 #ifdef ENABLE_LOG
6758 colnr_T col; 6775 colnr_T col;
6759 { 6776 {
6760 int i; 6777 int i;
6761 regsubs_T subs, m; 6778 regsubs_T subs, m;
6762 nfa_state_T *start = prog->start; 6779 nfa_state_T *start = prog->start;
6780 int result;
6763 #ifdef ENABLE_LOG 6781 #ifdef ENABLE_LOG
6764 FILE *f; 6782 FILE *f;
6765 #endif 6783 #endif
6766 6784
6767 reginput = regline + col; 6785 reginput = regline + col;
6789 #ifdef FEAT_SYN_HL 6807 #ifdef FEAT_SYN_HL
6790 clear_sub(&subs.synt); 6808 clear_sub(&subs.synt);
6791 clear_sub(&m.synt); 6809 clear_sub(&m.synt);
6792 #endif 6810 #endif
6793 6811
6794 if (nfa_regmatch(prog, start, &subs, &m) == FALSE) 6812 result = nfa_regmatch(prog, start, &subs, &m);
6813 if (result == FALSE)
6795 return 0; 6814 return 0;
6815 else if (result == NFA_TOO_EXPENSIVE)
6816 return result;
6796 6817
6797 cleanup_subexpr(); 6818 cleanup_subexpr();
6798 if (REG_MULTI) 6819 if (REG_MULTI)
6799 { 6820 {
6800 for (i = 0; i < subs.norm.in_use; i++) 6821 for (i = 0; i < subs.norm.in_use; i++)
6927 nfa_has_zend = prog->has_zend; 6948 nfa_has_zend = prog->has_zend;
6928 nfa_has_backref = prog->has_backref; 6949 nfa_has_backref = prog->has_backref;
6929 nfa_nsubexpr = prog->nsubexp; 6950 nfa_nsubexpr = prog->nsubexp;
6930 nfa_listid = 1; 6951 nfa_listid = 1;
6931 nfa_alt_listid = 2; 6952 nfa_alt_listid = 2;
6932 #ifdef DEBUG
6933 nfa_regengine.expr = prog->pattern; 6953 nfa_regengine.expr = prog->pattern;
6934 #endif
6935 6954
6936 if (prog->reganch && col > 0) 6955 if (prog->reganch && col > 0)
6937 return 0L; 6956 return 0L;
6938 6957
6939 need_clear_subexpr = TRUE; 6958 need_clear_subexpr = TRUE;
6977 prog->state[i].lastlist[1] = 0; 6996 prog->state[i].lastlist[1] = 0;
6978 } 6997 }
6979 6998
6980 retval = nfa_regtry(prog, col); 6999 retval = nfa_regtry(prog, col);
6981 7000
6982 #ifdef DEBUG
6983 nfa_regengine.expr = NULL; 7001 nfa_regengine.expr = NULL;
6984 #endif
6985 7002
6986 theend: 7003 theend:
6987 return retval; 7004 return retval;
6988 } 7005 }
6989 7006
7001 int *postfix; 7018 int *postfix;
7002 7019
7003 if (expr == NULL) 7020 if (expr == NULL)
7004 return NULL; 7021 return NULL;
7005 7022
7006 #ifdef DEBUG
7007 nfa_regengine.expr = expr; 7023 nfa_regengine.expr = expr;
7008 #endif
7009 7024
7010 init_class_tab(); 7025 init_class_tab();
7011 7026
7012 if (nfa_regcomp_start(expr, re_flags) == FAIL) 7027 if (nfa_regcomp_start(expr, re_flags) == FAIL)
7013 return NULL; 7028 return NULL;
7080 #endif 7095 #endif
7081 #ifdef FEAT_SYN_HL 7096 #ifdef FEAT_SYN_HL
7082 /* Remember whether this pattern has any \z specials in it. */ 7097 /* Remember whether this pattern has any \z specials in it. */
7083 prog->reghasz = re_has_z; 7098 prog->reghasz = re_has_z;
7084 #endif 7099 #endif
7085 #ifdef DEBUG
7086 prog->pattern = vim_strsave(expr); 7100 prog->pattern = vim_strsave(expr);
7087 nfa_regengine.expr = NULL; 7101 nfa_regengine.expr = NULL;
7088 #endif
7089 7102
7090 out: 7103 out:
7091 vim_free(post_start); 7104 vim_free(post_start);
7092 post_start = post_ptr = post_end = NULL; 7105 post_start = post_ptr = post_end = NULL;
7093 state_ptr = NULL; 7106 state_ptr = NULL;
7097 vim_free(prog); 7110 vim_free(prog);
7098 prog = NULL; 7111 prog = NULL;
7099 #ifdef ENABLE_LOG 7112 #ifdef ENABLE_LOG
7100 nfa_postfix_dump(expr, FAIL); 7113 nfa_postfix_dump(expr, FAIL);
7101 #endif 7114 #endif
7102 #ifdef DEBUG
7103 nfa_regengine.expr = NULL; 7115 nfa_regengine.expr = NULL;
7104 #endif
7105 goto out; 7116 goto out;
7106 } 7117 }
7107 7118
7108 /* 7119 /*
7109 * Free a compiled regexp program, returned by nfa_regcomp(). 7120 * Free a compiled regexp program, returned by nfa_regcomp().
7113 regprog_T *prog; 7124 regprog_T *prog;
7114 { 7125 {
7115 if (prog != NULL) 7126 if (prog != NULL)
7116 { 7127 {
7117 vim_free(((nfa_regprog_T *)prog)->match_text); 7128 vim_free(((nfa_regprog_T *)prog)->match_text);
7118 #ifdef DEBUG
7119 vim_free(((nfa_regprog_T *)prog)->pattern); 7129 vim_free(((nfa_regprog_T *)prog)->pattern);
7120 #endif
7121 vim_free(prog); 7130 vim_free(prog);
7122 } 7131 }
7123 } 7132 }
7124 7133
7125 /* 7134 /*