File: | dmake/percent.c |
Location: | line 179, column 4 |
Description: | Access to field 'states' results in a dereference of a null pointer (loaded from variable 'dfa') |
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 *))(char *); | |||||
30 | static char _shift_dfa ANSI((DFAPTR, char *))(DFAPTR, char *); | |||||
31 | ||||||
32 | ||||||
33 | #define NO_ACTION0 0 | |||||
34 | #define START_PERCENT1 1 | |||||
35 | #define END_PERCENT2 2 | |||||
36 | #define ACCEPT4 4 | |||||
37 | #define FAIL-1 -1 | |||||
38 | ||||||
39 | static NFAPTR _nfa = NIL( NFA )((NFA*)((void*)0)); | |||||
40 | ||||||
41 | ||||||
42 | PUBLIC DFALINKPTR | |||||
43 | 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 | DFALINKPTR dfa_list = NIL(DFALINK)((DFALINK*)((void*)0)); | |||||
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 | adv = FALSE0; | |||||
63 | ||||||
64 | for( nfa = _nfa; nfa != NIL( NFA )((NFA*)((void*)0)); nfa = nfa->next ) | |||||
65 | if( nfa->status != (char) FAIL-1 && nfa->status != (char) ACCEPT4 ) { | |||||
66 | adv++; | |||||
67 | nfa->status = _shift_dfa( nfa->dfa, buf ); | |||||
68 | ||||||
69 | /* Construct the list of matching DFA's */ | |||||
70 | if( nfa->status == (char) ACCEPT4 ) { | |||||
71 | DFALINKPTR dl; | |||||
72 | ||||||
73 | TALLOC( dl, 1, DFALINK )if ((dl = (DFALINK*) calloc((unsigned int)(1), (size_t)sizeof (DFALINK))) == (DFALINK*)0) {No_ram();}; | |||||
74 | dl->dl_meta = nfa->dfa->node; | |||||
75 | dl->dl_per = DmSubStr( nfa->dfa->pstart, nfa->dfa->pend ); | |||||
76 | dl->dl_state = nfa->dfa->states - nfa->dfa->c_state; | |||||
77 | ||||||
78 | if( dfa_list == NIL(DFALINK)((DFALINK*)((void*)0)) ) | |||||
79 | dfa_list = dl; | |||||
80 | else { | |||||
81 | DFALINKPTR tdli = dfa_list; | |||||
82 | DFALINKPTR tdlp = NIL(DFALINK)((DFALINK*)((void*)0)); | |||||
83 | ||||||
84 | for( ; tdli != NIL(DFALINK)((DFALINK*)((void*)0)); tdli = tdli->dl_next ) { | |||||
85 | if( dl->dl_state >= tdli->dl_state ) | |||||
86 | break; | |||||
87 | tdlp = tdli; | |||||
88 | } | |||||
89 | ||||||
90 | if( tdli != NIL(DFALINK)((DFALINK*)((void*)0)) ) { | |||||
91 | tdli->dl_prev = dl; | |||||
92 | dl->dl_next = tdli; | |||||
93 | } | |||||
94 | ||||||
95 | if( tdlp != NIL(DFALINK)((DFALINK*)((void*)0)) ) { | |||||
96 | tdlp->dl_next = dl; | |||||
97 | dl->dl_prev = tdlp; | |||||
98 | } | |||||
99 | else | |||||
100 | dfa_list = dl; | |||||
101 | } | |||||
102 | ||||||
103 | DB_PRINT( "dfa", ("Matched [%s]", dl->dl_meta->CE_NAME) ); | |||||
104 | } | |||||
105 | } | |||||
106 | ||||||
107 | buf++; | |||||
108 | } | |||||
109 | while ( adv ); | |||||
110 | ||||||
111 | for( nfa = _nfa; nfa != NIL( NFA )((NFA*)((void*)0)); nfa = nfa->next ) { | |||||
112 | nfa->status = 0; | |||||
113 | nfa->dfa->c_state = nfa->dfa->states; | |||||
114 | } | |||||
115 | ||||||
116 | DB_RETURN( dfa_list )return (dfa_list); | |||||
117 | } | |||||
118 | ||||||
119 | ||||||
120 | PUBLIC void | |||||
121 | 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 | for( nfa = _nfa; nfa != NIL(NFA)((NFA*)((void*)0)); nfa = nfa->next ) | |||||
129 | if( Test_circle( nfa->dfa->node, FALSE0 ) ) | |||||
130 | Fatal( "Detected circular dependency in inference graph at [%s]", | |||||
131 | nfa->dfa->node->CE_NAMEce_name->ht_name ); | |||||
132 | } | |||||
133 | ||||||
134 | ||||||
135 | PUBLIC void | |||||
136 | 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 | TALLOC(nfa, 1, NFA)if ((nfa = (NFA*) calloc((unsigned int)(1), (size_t)sizeof(NFA ))) == (NFA*)0) {No_ram();}; | |||||
145 | nfa->dfa = _build_dfa(name); | |||||
| ||||||
146 | ||||||
147 | if( _nfa != NIL(NFA)((NFA*)((void*)0)) ) nfa->next = _nfa; | |||||
148 | ||||||
149 | _nfa = nfa; | |||||
150 | } | |||||
151 | ||||||
152 | ||||||
153 | static DFAPTR | |||||
154 | _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 | STATEPTR per_state = NIL(STATE)((STATE*)((void*)0)); | |||||
172 | int pcount=0; | |||||
173 | int end_percent=FALSE0; | |||||
174 | ||||||
175 | nstates = strlen(name)+2; | |||||
176 | ||||||
177 | /* Allocate a DFA node and the right number of states. */ | |||||
178 | TALLOC(dfa, 1, DFA)if ((dfa = (DFA*) calloc((unsigned int)(1), (size_t)sizeof(DFA ))) == (DFA*)0) {No_ram();}; | |||||
179 | TALLOC(sp=dfa->c_state=dfa->states, nstates, STATE)if ((sp=dfa->c_state=dfa->states = (STATE*) calloc((unsigned int)(nstates), (size_t)sizeof(STATE))) == (STATE*)0) {No_ram ();}; | |||||
| ||||||
180 | dfa->node = Def_cell( name ); | |||||
181 | ||||||
182 | /* Now construct the state table for the DFA */ | |||||
183 | do { | |||||
184 | if( *name == '%' ) { | |||||
185 | if( pcount++ > 0 ) | |||||
186 | Error( "Only one %% allowed within a %%-meta target" ); | |||||
187 | ||||||
188 | sp->symbol = 0; | |||||
189 | sp->action = START_PERCENT1; | |||||
190 | sp->no_match = sp->match = per_state = sp+1; | |||||
191 | end_percent = TRUE1; | |||||
192 | } | |||||
193 | else { | |||||
194 | sp->symbol = *name; | |||||
195 | sp->no_match = per_state; | |||||
196 | ||||||
197 | if( *name == '\0' ) { | |||||
198 | sp->action = ACCEPT4; | |||||
199 | sp->match = dfa->states; | |||||
200 | } | |||||
201 | else { | |||||
202 | sp->action = NO_ACTION0; | |||||
203 | sp->match = sp+1; | |||||
204 | } | |||||
205 | ||||||
206 | if( end_percent ) { | |||||
207 | sp->action |= END_PERCENT2; | |||||
208 | end_percent = FALSE0; | |||||
209 | } | |||||
210 | } | |||||
211 | ||||||
212 | sp++; | |||||
213 | } | |||||
214 | while( *name++ ); | |||||
215 | ||||||
216 | return(dfa); | |||||
217 | } | |||||
218 | ||||||
219 | ||||||
220 | static char | |||||
221 | _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 | register STATEPTR sp = dfa->c_state; | |||||
229 | 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 | if( sp->action & START_PERCENT1 ) { | |||||
234 | dfa->pstart = data; | |||||
235 | 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 | if( sp->symbol == c ) { | |||||
243 | if( sp->action & END_PERCENT2 ) dfa->pend = data; | |||||
244 | if( sp->action & ACCEPT4 ) return(ACCEPT4); | |||||
245 | dfa->c_state = sp->match; | |||||
246 | } | |||||
247 | else if( (dfa->c_state = sp->no_match) == NIL(STATE)((STATE*)((void*)0)) || !c ) | |||||
248 | return((unsigned char) FAIL-1); | |||||
249 | ||||||
250 | return(NO_ACTION0); | |||||
251 | } |