[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH 5/8] dfa: change meaning of a state context
From: |
Paolo Bonzini |
Subject: |
[PATCH 5/8] dfa: change meaning of a state context |
Date: |
Fri, 20 Jan 2012 16:35:18 +0100 |
* src/dfa.c (MATCHES_NEWLINE_CONTEXT, MATCHES_LETTER_CONTEXT): Adjust.
(state_wanted_contexts): Remove second argument.
(state_index): Do not mask away CTX_NONE.
(dfaanalyze): Adjust call to state_index and state_wanted_contexts.
Compute full context for state 0.
(dfastate): Adjust calls to state_index and state_wanted_contexts.
Check whether there will be transitions with non-specific (that is,
wanted_context ^ CTX_ANY) context. If not do not generate a state for
non-specific context.
---
src/dfa.c | 63 ++++++++++++++++++++++++++++++++----------------------------
1 files changed, 34 insertions(+), 29 deletions(-)
diff --git a/src/dfa.c b/src/dfa.c
index f33a4c3..bc57e3f 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -93,11 +93,15 @@ static inline unsigned char to_uchar (char ch) { return ch;
}
/* Contexts tell us whether a character is a newline or a word constituent.
Word-constituent characters are those that satisfy iswalnum(), plus '_'.
+ Each character has a single CTX_* value; bitmasks of CTX_* values denote
+ a particular character class.
- A states also stores a context value, which is nonzero if its
- predecessors always matches a newline or a word constituent.
- The definition of a state's context is a bit unclear, but will be
- modified soon anyway. */
+ A state also stores a context value, which is a bitmask of CTX_* values.
+ A state's context represents a set of characters that the state's
+ predecessors must match. For example, a state whose context does not
+ include CTX_LETTER will never have transitions where the previous
+ character is a word constituent. A state whose context is CTX_ANY
+ might have transitions from any character. */
#define CTX_NONE 1
#define CTX_LETTER 2
@@ -121,15 +125,15 @@ static inline unsigned char to_uchar (char ch) { return
ch; }
bit 0 - neither previous nor current is word-constituent
The macro SUCCEEDS_IN_CONTEXT determines whether a given constraint
- succeeds in a particular context. Prev is the context value for
- the previous character, curr is the context value for the lookahead
- character. */
+ succeeds in a particular context. Prev is a bitmask of possible
+ context values for the previous character, curr is the bitmask of
+ possible context values for the lookahead character. */
#define MATCHES_NEWLINE_CONTEXT(constraint, prev, curr) \
((constraint) & \
- 1 << (((prev & CTX_NEWLINE) ? 2 : 0) + ((curr & CTX_NEWLINE) ? 1 : 0) + 4))
+ 1 << (((prev & ~CTX_NEWLINE) ? 0 : 2) + ((curr & ~CTX_NEWLINE) ? 0 : 1) +
4))
#define MATCHES_LETTER_CONTEXT(constraint, prev, curr) \
((constraint) & \
- 1 << (((prev & CTX_LETTER) ? 2 : 0) + ((curr & CTX_LETTER) ? 1 : 0)))
+ 1 << (((prev & ~CTX_LETTER) ? 0 : 2) + ((curr & ~CTX_LETTER) ? 0 : 1)))
#define SUCCEEDS_IN_CONTEXT(constraint, prev, curr) \
(MATCHES_NEWLINE_CONTEXT(constraint, prev, curr) \
&& MATCHES_LETTER_CONTEXT(constraint, prev, curr))
@@ -1976,7 +1980,6 @@ state_index (struct dfa *d, position_set const *s, int
context)
int constraint;
int i, j;
- context &= ~CTX_NONE;
for (i = 0; i < s->nelem; ++i)
hash ^= s->elems[i].index + s->elems[i].constraint;
@@ -2118,18 +2121,16 @@ charclass_context(charclass c)
return context;
}
-int state_wanted_contexts(position_set *s, int possible_contexts)
+int state_wanted_contexts(position_set *s)
{
int wanted_context = 0;
int j;
for (j = 0; j < s->nelem; ++j)
{
- if ((possible_contexts & CTX_NEWLINE)
- && PREV_NEWLINE_DEPENDENT(s->elems[j].constraint))
+ if (PREV_NEWLINE_DEPENDENT(s->elems[j].constraint))
wanted_context |= CTX_NEWLINE;
- if ((possible_contexts & CTX_LETTER)
- && PREV_LETTER_DEPENDENT(s->elems[j].constraint))
+ if (PREV_LETTER_DEPENDENT(s->elems[j].constraint))
wanted_context |= CTX_LETTER;
}
@@ -2394,8 +2395,11 @@ dfaanalyze (struct dfa *d, int searchflag)
d->sindex = 0;
MALLOC(d->states, d->salloc);
- wanted_context = state_wanted_contexts(&merged, CTX_NEWLINE);
- state_index(d, &merged, wanted_context);
+ wanted_context = state_wanted_contexts(&merged);
+ state_index(d, &merged,
+ (wanted_context & CTX_NEWLINE
+ ? CTX_NEWLINE
+ : wanted_context ^ CTX_ANY));
free(o_nullable);
free(o_nfirst);
@@ -2492,20 +2496,18 @@ dfastate (int s, struct dfa *d, int trans[])
if (pos.constraint != 0xFF)
{
if (! MATCHES_NEWLINE_CONTEXT(pos.constraint,
- d->states[s].context & CTX_NEWLINE,
- CTX_NEWLINE))
+ d->states[s].context, CTX_NEWLINE))
clrbit(eolbyte, matches);
if (! MATCHES_NEWLINE_CONTEXT(pos.constraint,
- d->states[s].context & CTX_NEWLINE, 0))
+ d->states[s].context, ~CTX_NEWLINE))
for (j = 0; j < CHARCLASS_INTS; ++j)
matches[j] &= newline[j];
if (! MATCHES_LETTER_CONTEXT(pos.constraint,
- d->states[s].context & CTX_LETTER,
- CTX_LETTER))
+ d->states[s].context, CTX_LETTER))
for (j = 0; j < CHARCLASS_INTS; ++j)
matches[j] &= ~letters[j];
if (! MATCHES_LETTER_CONTEXT(pos.constraint,
- d->states[s].context & CTX_LETTER, 0))
+ d->states[s].context, ~CTX_LETTER))
for (j = 0; j < CHARCLASS_INTS; ++j)
matches[j] &= letters[j];
@@ -2589,8 +2591,8 @@ dfastate (int s, struct dfa *d, int trans[])
{
/* Find the state(s) corresponding to the positions of state 0. */
copy(&d->states[0].elems, &follows);
- wanted_context = state_wanted_contexts(&follows, CTX_ANY);
- state = state_index(d, &follows, 0);
+ wanted_context = state_wanted_contexts(&follows);
+ state = state_index(d, &follows, wanted_context ^ CTX_ANY);
if (wanted_context & CTX_NEWLINE)
state_newline = state_index(d, &follows, CTX_NEWLINE);
else
@@ -2659,15 +2661,18 @@ dfastate (int s, struct dfa *d, int trans[])
/* Find out if the new state will want any context information. */
possible_contexts = charclass_context(labels[i]);
- wanted_context = state_wanted_contexts(&follows, possible_contexts);
+ wanted_context = state_wanted_contexts(&follows);
/* Find the state(s) corresponding to the union of the follows. */
- state = state_index(d, &follows, 0);
- if (wanted_context & CTX_NEWLINE)
+ if ((wanted_context & possible_contexts) != possible_contexts)
+ state = state_index(d, &follows, wanted_context ^ CTX_ANY);
+ else
+ state = -1;
+ if (wanted_context & possible_contexts & CTX_NEWLINE)
state_newline = state_index(d, &follows, CTX_NEWLINE);
else
state_newline = state;
- if (wanted_context & CTX_LETTER)
+ if (wanted_context & possible_contexts & CTX_LETTER)
state_letter = state_index(d, &follows, CTX_LETTER);
else
state_letter = state;
--
1.7.7.1
- [PATCH 0/8] fix problems with ^ and $ together with \< and \>, Paolo Bonzini, 2012/01/20
- [PATCH 7/8] dfa: fix constraint encoding, Paolo Bonzini, 2012/01/20
- [PATCH 8/8] dfa: merge calls to SUCCEEDS_IN_CONTEXT, Paolo Bonzini, 2012/01/20
- [PATCH 1/8] dfa: remove useless check, Paolo Bonzini, 2012/01/20
- [PATCH 2/8] dfa: introduce contexts for the values in d->success, Paolo Bonzini, 2012/01/20
- [PATCH 5/8] dfa: change meaning of a state context,
Paolo Bonzini <=
- [PATCH 3/8] dfa: change newline/letter to a single context value, Paolo Bonzini, 2012/01/20
- [PATCH 6/8] dfa: do not use MATCHES_*_CONTEXT directly, Paolo Bonzini, 2012/01/20
- [PATCH 4/8] dfa: refactor common context computations, Paolo Bonzini, 2012/01/20
- Re: [PATCH 0/8] fix problems with ^ and $ together with \< and \>, Paul Eggert, 2012/01/20