usr.bin/grep/dfa.c

4    This program is free software; you can redistribute it and/or modify
9    This program is distributed in the hope that it will be useful,
168 /* Reallocate an array of type t if nalloc is too small for index. */
268 /* A pointer to the current dfa is kept here during parsing. */
305 /* Like setbit, but if case is folded, set both cases of a letter.  */
320    GNU Regex syntax bits is located here.  The poor, suffering
321    reader is referred to the GNU Regex documentation for the
332 static int hard_LC_COLLATE;	/* Nonzero if LC_COLLATE is hard.  */
353                                   is 0 if corresponding character is a
360 				   The length of this array is same as
362 				   inputstring[i] is a single-byte char,
364 				   And inputwcs[i] is the codepoint.  */
371    p points current lexptr, len is the remaining buffer length.  */
375   /* If last character is a part of a multibyte character,
381   /* If last character is a single byte character, or the
383      next character is a multibyte character or not.  */
388 	/* It is a multibyte character.
393 	   cur_mb_index is aleady 0.  */
395       /* Otherwise, cur_mb_len == 1, it is a singlebyte character.
396 	 cur_mb_index is aleady 0.  */
419    used only if the current locale is a multibyte environment.  */
502       wc1 = WEOF; /* mark wc1 is not initialized".  */
507 	 dfa is ever called. */
533 		    /* This is in any case an invalid class name.  */
615 	      /* In the case [x-], the - is an ordinary hyphen,
616 		 which is left in c1, the lookahead character. */
678    to predicate functions that determine whether a given character is in
699 /* Return non-zero if C is a `word-constituent' byte; zero otherwise.  */
732 	/* If this is a part of a multi-byte character, we must treat
875 	     {M,} - minimum count, maximum is infinity
1019 		 dfa is ever called. */
1042 		      /* In the case [x-], the - is an ordinary hyphen,
1043 			 which is left in c1, the lookahead character. */
1112 				   holding deferred productions.  This is
1136 	/* It may be unnecesssary, but it is safer to treat other
1168 /* The grammar understood by the parser is as follows.
1356 /* Main entry point for the parser.  S is a string to be parsed, len is the
1357    length of the string, so s can include NUL characters.  D is a pointer to
1438 /* Merge two sets of positions into a third.  The result is exactly as if
1477    the given preceding context, or create a new state if there is no such
1618    Nullable:  A node is nullable if it is at the root of a regexp that can
1621    * No other leaf is nullable.
1622    * A QMARK or STAR node is nullable.
1623    * A PLUS node is nullable if its argument is nullable.
1624    * A CAT node is nullable if both its arguments are nullable.
1625    * An OR node is nullable if either argument is nullable.
1627    Firstpos:  The firstpos of a node is the set of positions (nonempty leaves)
1631    * The firstpos of a nonempty leaf is that leaf itself.
1632    * The firstpos of a QMARK, STAR, or PLUS node is the firstpos of its
1634    * The firstpos of a CAT node is the firstpos of the left argument, union
1635      the firstpos of the right if the left argument is nullable.
1636    * The firstpos of an OR node is the union of firstpos of each argument.
1638    Lastpos:  The lastpos of a node is the set of positions that could
1642    * The lastpos of a nonempty leaf is that leaf itself.
1643    * The lastpos of a QMARK, STAR, or PLUS node is the lastpos of its
1645    * The lastpos of a CAT node is the lastpos of its right argument, union
1646      the lastpos of the left if the right argument is nullable.
1647    * The lastpos of an OR node is the union of the lastpos of each argument.
1649    Follow:  The follow of a position is the set of positions that could
1653    Later, if we find that a special symbol is in a follow set, we will
1656    * Every node in the firstpos of the argument of a STAR or PLUS node is in
1658    * Every node in the firstpos of the second argument of a CAT node is in
1662    analysis is conveniently done by a linear scan with the aid of a stack.
1720 	/* The empty set is nullable. */
1729 	/* Every element in the firstpos of the argument is in the follow
1743 	/* A QMARK or STAR node is automatically nullable. */
1749 	/* Every element in the firstpos of the second argument is in the
1762 	/* The firstpos of a CAT node is the firstpos of the first argument,
1763 	   union that of the second argument if the first is nullable. */
1770 	/* The lastpos of a CAT node is the lastpos of the second argument,
1771 	   union that of the first argument if the second is nullable. */
1784 	/* A CAT node is nullable if both arguments are nullable. */
1791 	/* The firstpos is the union of the firstpos of each argument. */
1795 	/* The lastpos is the union of the lastpos of each argument. */
1799 	/* An OR node is nullable if either argument is nullable. */
1805 	/* Anything else is a nonempty position.  (Note that special
1812 	/* This position is in its own firstpos and lastpos. */
1845   /* For each follow set that is the follow set of a real position, replace
1905    than one group).  Each group is labeled with a set of characters that
1908    of the its elements' follows.  This set is the set of positions of the
1916    The collection of groups is constructed by building an equivalence-class
1923    intersection with C.  If L - C is nonempty, create a new group labeled
1939   int matchesf;			/* True if matches is nonempty. */
1941   int intersectf;		/* True if intersect is nonempty. */
1943   int leftoversf;		/* True if leftovers is nonempty. */
2063 	  /* Put the position in the current group.  Note that there is no
2089   /* If we are a searching matcher, the default transition is to a state
2091      is to fail miserably. */
2126 	 This is a hideously inefficient loop.  Fix it someday. */
2134 	  /* If a token in follows.elems is not 1st byte of a multibyte
2142 	     For example, we assume <sb a> is a certain singlebyte
2143 	     character, <mb A> is a certain multibyte character, and the
2225    is a non-accepting state, then d->trans[state] points to its table.
2226    If it is an accepting state then d->fails[state] points to its table.
2227    If it has no table at all, then d->trans[state] is NULL.
2237      exist at once.  1024 is arbitrary.  The idea is that the frequently
2294   /* Newline is a sentinel.  */
2318 /* Initial state may encounter the byte which is not a singlebyte character
2319    nor 1st byte of a multibyte character.  But it is incorrect for initial
2373    This function is almost same as the state transition routin in dfaexec().
2374    But state transition is done just once, otherwise matching succeed or
2418    `pos' is the position of the period.  `index' is the index from the
2419    buf_begin, and it is the current position in the buffer.  */
2458    `pos' is the position of the bracket expression.  `index' is the index
2459    from the buf_begin, and it is the current position in the buffer.  */
2574    `index' is the index from the buf_begin, and it is the current position
2604    `match_lens' is the input. It can be NULL, but it can also be the output
2606    `mbclen' and `pps' are the output.  `mbclen' is the length of the
2607    character consumed, and `pps' is the set this function enumerate.  */
2633   /* Check (inputed)match_lens, and initialize if it is NULL.  */
2656    buffer.  This function is for some operator which can match with a multi-
2746    character after the match, or (size_t) -1 if none is found.  BEGIN points to
2747    the beginning of the buffer, and SIZE is the size of the buffer.  If SIZE
2748    is nonzero, BEGIN[SIZE - 1] must be a newline.  BACKREF points to a place
2961       /* This is a kludge. */
3054    Finding a "longest" sequence is beyond the scope here;
3064 	sequences that must constitute the match ("is")
3067    calculated "in" sequences as our answer.  The sequence we find is returned in
3068    d->must (where "d" is the single argument passed to "dfamust");
3069    the length of the sequence is returned in d->mustn.
3072    are shown below.  "p" is the operand of unary operators (and the left-hand
3073    operand of binary operators); "q" is the right-hand operand of binary
3078 	Type	left		right		is		in
3094 	CAT	(p->is==ZERO)?	(q->is==ZERO)?	(p->is!=ZERO &&	p->in plus
3095 		p->left :	q->right :	q->is!=ZERO) ?	q->in plus
3096 		p->is##q->left	p->right##q->is	p->is##q->is :	p->right##q->left
3099 	OR	longest common	longest common	(do p->is and	substrings common to
3100 		leading		trailing	q->is have same	p->in and q->in
3103 		and q->left	and q->right	p->is : NULL
3112    And. . .is it here or someplace that we might ponder "optimizations" such as
3128    or is the automaton you get from "psi|epsilon" (for example)
3132    (something like 'ab*' is probably unlikely; something like is
3133    'psi|epsilon' is likelier)? */
3331   char *is;
3337   mp->left[0] = mp->right[0] = mp->is[0] = '\0';
3368       mp[i].is = malloc(2);
3370 	  mp[i].right == NULL || mp[i].is == NULL)
3372       mp[i].left[0] = mp[i].right[0] = mp[i].is[0] = '\0';
3421 	    if (strcmp(lmp->is, rmp->is) != 0)
3422 	      lmp->is[0] = '\0';
3452 	  mp->is[0] = '\0';
3460 	  if (strcmp(result, musts[0].is) == 0)
3496 	    if (lmp->is[0] != '\0')
3504 	    if (rmp->is[0] == '\0')
3510 	    if (lmp->is[0] != '\0' && rmp->is[0] != '\0')
3512 		lmp->is = icatalloc(lmp->is, rmp->is);
3513 		if (lmp->is == NULL)
3517 	      lmp->is[0] = '\0';
3545 	      mp->is[0] = mp->left[0] = mp->right[0] = t;
3546 	      mp->is[1] = mp->left[1] = mp->right[1] = '\0';
3547 	      mp->in = enlist(mp->in, mp->is, (size_t)1);
3559       fprintf(stderr, "\n  is: \"%s\"\n", mp->is);
3582       ifree(mp[i].is);