File: | dmake/percent.c |
Location: | line 74, column 12 |
Description: | Access to field 'dl_meta' results in a dereference of a null pointer (loaded from variable 'dl') |
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 | } |