Line data Source code
1 : /* RCS $Id: percent.c,v 1.1.1.1 2000-09-22 15:33:25 hr Exp $
2 : --
3 : -- SYNOPSIS
4 : -- Handle building or %-rule meta-target nfa.
5 : --
6 : -- DESCRIPTION
7 : -- Builds the NFA used by dmake to match targets against %-meta
8 : -- rule constructs. The NFA is built as a set of DFA's.
9 : --
10 : -- AUTHOR
11 : -- Dennis Vadura, dvadura@dmake.wticorp.com
12 : --
13 : -- WWW
14 : -- http://dmake.wticorp.com/
15 : --
16 : -- COPYRIGHT
17 : -- Copyright (c) 1996,1997 by WTI Corp. All rights reserved.
18 : --
19 : -- This program is NOT free software; you can redistribute it and/or
20 : -- modify it under the terms of the Software License Agreement Provided
21 : -- in the file <distribution-root>/readme/license.txt.
22 : --
23 : -- LOG
24 : -- Use cvs log to obtain detailed change logs.
25 : */
26 :
27 : #include "extern.h"
28 :
29 : static DFAPTR _build_dfa ANSI((char *));
30 : static char _shift_dfa ANSI((DFAPTR, char *));
31 :
32 :
33 : #define NO_ACTION 0
34 : #define START_PERCENT 1
35 : #define END_PERCENT 2
36 : #define ACCEPT 4
37 : #define FAIL -1
38 :
39 : static NFAPTR _nfa = NIL( NFA );
40 :
41 :
42 : PUBLIC DFALINKPTR
43 34255 : Match_dfa( buf )/*
44 : ==================
45 : This routines runs all DFA's in parrallel and selects the one that best
46 : matches the string. If no match then it returns NIL( DFA ) */
47 : char *buf;
48 : {
49 : register NFAPTR nfa;
50 : int adv;
51 34255 : DFALINKPTR dfa_list = NIL(DFALINK);
52 :
53 : DB_ENTER( "Match_dfa" );
54 : DB_PRINT( "dfa", ("Matching %s", buf) );
55 :
56 : /* Run each of the DFA's on the input string in parallel, we terminate
57 : * when all DFA's have either failed or ACCEPTED, if more than one DFA
58 : * accepts we build a list of all accepting DFA's sorted on states with
59 : * those matching in a higher numbered state heading the list. */
60 :
61 : do {
62 1833714 : adv = FALSE;
63 :
64 46716212 : for( nfa = _nfa; nfa != NIL( NFA ); nfa = nfa->next )
65 44882498 : if( nfa->status != (char) FAIL && nfa->status != (char) ACCEPT ) {
66 24926580 : adv++;
67 24926580 : nfa->status = _shift_dfa( nfa->dfa, buf );
68 :
69 : /* Construct the list of matching DFA's */
70 24926580 : if( nfa->status == (char) ACCEPT ) {
71 : DFALINKPTR dl;
72 :
73 4760 : TALLOC( dl, 1, DFALINK );
74 4760 : dl->dl_meta = nfa->dfa->node;
75 4760 : dl->dl_per = DmSubStr( nfa->dfa->pstart, nfa->dfa->pend );
76 4760 : dl->dl_state = nfa->dfa->states - nfa->dfa->c_state;
77 :
78 4760 : if( dfa_list == NIL(DFALINK) )
79 4754 : dfa_list = dl;
80 : else {
81 6 : DFALINKPTR tdli = dfa_list;
82 6 : DFALINKPTR tdlp = NIL(DFALINK);
83 :
84 6 : for( ; tdli != NIL(DFALINK); tdli = tdli->dl_next ) {
85 6 : if( dl->dl_state >= tdli->dl_state )
86 6 : break;
87 0 : tdlp = tdli;
88 : }
89 :
90 6 : if( tdli != NIL(DFALINK) ) {
91 6 : tdli->dl_prev = dl;
92 6 : dl->dl_next = tdli;
93 : }
94 :
95 6 : if( tdlp != NIL(DFALINK) ) {
96 0 : tdlp->dl_next = dl;
97 0 : dl->dl_prev = tdlp;
98 : }
99 : else
100 6 : dfa_list = dl;
101 : }
102 :
103 : DB_PRINT( "dfa", ("Matched [%s]", dl->dl_meta->CE_NAME) );
104 : }
105 : }
106 :
107 1833714 : buf++;
108 : }
109 1833714 : while ( adv );
110 :
111 866015 : for( nfa = _nfa; nfa != NIL( NFA ); nfa = nfa->next ) {
112 831760 : nfa->status = 0;
113 831760 : nfa->dfa->c_state = nfa->dfa->states;
114 : }
115 :
116 34255 : DB_RETURN( dfa_list );
117 : }
118 :
119 :
120 : PUBLIC void
121 184 : Check_circle_dfa()/*
122 : ====================
123 : This function is called to test for circularities in the DFA lists
124 : constructed from %-meta targets. */
125 : {
126 : register NFAPTR nfa;
127 :
128 4856 : for( nfa = _nfa; nfa != NIL(NFA); nfa = nfa->next )
129 4672 : if( Test_circle( nfa->dfa->node, FALSE ) )
130 0 : Fatal( "Detected circular dependency in inference graph at [%s]",
131 0 : nfa->dfa->node->CE_NAME );
132 184 : }
133 :
134 :
135 : PUBLIC void
136 4672 : Add_nfa( name )/*
137 : =================
138 : Given name, build a DFA and add it to the NFA. The NFA is maintained as
139 : a singly linked list of DFA's. */
140 : char *name;
141 : {
142 : NFAPTR nfa;
143 :
144 4672 : TALLOC(nfa, 1, NFA);
145 4672 : nfa->dfa = _build_dfa(name);
146 :
147 4672 : if( _nfa != NIL(NFA) ) nfa->next = _nfa;
148 :
149 4672 : _nfa = nfa;
150 4672 : }
151 :
152 :
153 : static DFAPTR
154 4672 : _build_dfa( name )/*
155 : ====================
156 : Construct a dfa for the passed in cell name. The routine returns a struct
157 : that represents a finite state machine that can recognize a regular
158 : expression with exactly one '%' sign in it. The '%' symbol is used as a
159 : wildcard character that will match anything except the character that
160 : immediately follows it or NUL.
161 :
162 : The Construction of DFA's is well known and can be found in Hopcroft and
163 : Ullman or any other book discussing formal language theory.
164 : A more practical treatise can be found in Compilers, Aho, Sethi and Ullman.
165 : */
166 : char *name;
167 : {
168 : DFAPTR dfa;
169 : int nstates;
170 : register STATEPTR sp;
171 4672 : STATEPTR per_state = NIL(STATE);
172 4672 : int pcount=0;
173 4672 : int end_percent=FALSE;
174 :
175 4672 : nstates = strlen(name)+2;
176 :
177 : /* Allocate a DFA node and the right number of states. */
178 4672 : TALLOC(dfa, 1, DFA);
179 4672 : TALLOC(sp=dfa->c_state=dfa->states, nstates, STATE);
180 4672 : dfa->node = Def_cell( name );
181 :
182 : /* Now construct the state table for the DFA */
183 : do {
184 172218 : if( *name == '%' ) {
185 4672 : if( pcount++ > 0 )
186 0 : Error( "Only one %% allowed within a %%-meta target" );
187 :
188 4672 : sp->symbol = 0;
189 4672 : sp->action = START_PERCENT;
190 4672 : sp->no_match = sp->match = per_state = sp+1;
191 4672 : end_percent = TRUE;
192 : }
193 : else {
194 167546 : sp->symbol = *name;
195 167546 : sp->no_match = per_state;
196 :
197 167546 : if( *name == '\0' ) {
198 4672 : sp->action = ACCEPT;
199 4672 : sp->match = dfa->states;
200 : }
201 : else {
202 162874 : sp->action = NO_ACTION;
203 162874 : sp->match = sp+1;
204 : }
205 :
206 167546 : if( end_percent ) {
207 4672 : sp->action |= END_PERCENT;
208 4672 : end_percent = FALSE;
209 : }
210 : }
211 :
212 172218 : sp++;
213 : }
214 172218 : while( *name++ );
215 :
216 4672 : return(dfa);
217 : }
218 :
219 :
220 : static char
221 24926580 : _shift_dfa( dfa, data )/*
222 : =========================
223 : Take a given dfa and advance it based on the current state, the shift
224 : action in that state, and the current data value. */
225 : DFAPTR dfa;
226 : char *data;
227 : {
228 24926580 : register STATEPTR sp = dfa->c_state;
229 24926580 : char c = *data;
230 :
231 : /* Check if it is a START_PERCENT action if so then we need to save
232 : * a pointer to the start of the string and advance to the next state. */
233 24926580 : if( sp->action & START_PERCENT ) {
234 285546 : dfa->pstart = data;
235 285546 : sp++;
236 : }
237 :
238 : /* Now check if the current char matches the character expected in the
239 : * current state. If it does then perform the specified action, otherwise
240 : * either shift it or fail. We fail if the next state on no-match is
241 : * NIL. */
242 24926580 : if( sp->symbol == c ) {
243 14112478 : if( sp->action & END_PERCENT ) dfa->pend = data;
244 14112478 : if( sp->action & ACCEPT ) return(ACCEPT);
245 14107718 : dfa->c_state = sp->match;
246 : }
247 10814102 : else if( (dfa->c_state = sp->no_match) == NIL(STATE) || !c )
248 827000 : return((unsigned char) FAIL);
249 :
250 24094820 : return(NO_ACTION);
251 : }
|
