Bug Summary

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')

Annotated 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
29static DFAPTR _build_dfa ANSI((char *))(char *);
30static 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
39static NFAPTR _nfa = NIL( NFA )((NFA*)((void*)0));
40
41
42PUBLIC DFALINKPTR
43Match_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 ) */
47char *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
120PUBLIC void
121Check_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
135PUBLIC void
136Add_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. */
140char *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);
1
Calling '_build_dfa'
→
146
147 if( _nfa != NIL(NFA)((NFA*)((void*)0)) ) nfa->next = _nfa;
148
149 _nfa = nfa;
150}
151
152
153static 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*/
166char *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();};
2
←
Within the expansion of the macro 'TALLOC':
→
a
Value assigned to 'dfa'
b
Assuming pointer value is null
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
();};
3
←
Within the expansion of the macro 'TALLOC':
a
Access to field 'states' results in a dereference of a null pointer (loaded from variable 'dfa')
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
220static 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. */
225DFAPTR dfa;
226char *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}