Bug Summary

File:dmake/infer.c
Location:line 225, column 30
Description:Access to field 'ce_attr' results in a dereference of a null pointer (loaded from variable 'imeta')

Annotated Source Code

1/*
2--
3-- SYNOPSIS
4-- Infer how to make a target.
5--
6-- DESCRIPTION
7-- This file contains the code to infer a recipe, and possibly some new
8-- prerequisites for a target which dmake does not know how to make, or
9-- has no explicit recipe.
10--
11-- The inference fails if no path through the inference graph can be
12-- found by which we can make the target.
13--
14-- AUTHOR
15-- Dennis Vadura, dvadura@dmake.wticorp.com
16--
17-- WWW
18-- http://dmake.wticorp.com/
19--
20-- COPYRIGHT
21-- Copyright (c) 1996,1997 by WTI Corp. All rights reserved.
22--
23-- This program is NOT free software; you can redistribute it and/or
24-- modify it under the terms of the Software License Agreement Provided
25-- in the file <distribution-root>/readme/license.txt.
26--
27-- LOG
28-- Use cvs log to obtain detailed change logs.
29*/
30
31#include "extern.h"
32
33/* attributes that get transfered from the % start cell to the inferred
34 * cells. */
35
36#define A_TRANSFER(0x00008 | 0x00001 | 0x00002 | 0x00800 | 0x00400 | 0x00200 | 0x00004
| 0x00020 | 0x00010 | 0x01000 | 0x04000 | 0x08000 ) (A_EPILOG0x00008 | A_PRECIOUS0x00001 | A_SILENT0x00002 | A_SHELL0x00800 | A_SETDIR0x00400 |\
37 A_SEQ0x00200 | A_LIBRARY0x00004 | A_IGNORE0x00020 | A_PROLOG0x00010 | A_SWAP0x01000 |\
38 A_PHONY0x04000 | A_NOSTATE0x08000 )
39
40
41/* Define local static functions */
42static DFALINKPTR dfa_subset ANSI((DFALINKPTR, DFASETPTR))(DFALINKPTR, DFASETPTR);
43static void free_dfas ANSI((DFALINKPTR))(DFALINKPTR);
44static int count_dots ANSI((char *))(char *);
45static char * buildname ANSI((char *, char *, char *))(char *, char *, char *);
46static void free_icells ANSI((void))(void);
47static ICELLPTR union_iset ANSI((ICELLPTR, ICELLPTR))(ICELLPTR, ICELLPTR);
48static ICELLPTR add_iset ANSI((ICELLPTR,ICELLPTR,CELLPTR,DFALINKPTR,(ICELLPTR,ICELLPTR,CELLPTR,DFALINKPTR, CELLPTR,int,int,char *
,char *, int)
49 CELLPTR,int,int,char *,char *, int))(ICELLPTR,ICELLPTR,CELLPTR,DFALINKPTR, CELLPTR,int,int,char *
,char *, int);
50static ICELLPTR derive_prerequisites ANSI((ICELLPTR, ICELLPTR *))(ICELLPTR, ICELLPTR *);
51static char * dump_inf_chain ANSI((ICELLPTR, int, int))(ICELLPTR, int, int);
52
53#ifdef DBUG
54static void _dump_dfa_stack ANSI((DFALINKPTR, DFASETPTR))(DFALINKPTR, DFASETPTR);
55static void _dump_iset ANSI(( char *, ICELLPTR ))( char *, ICELLPTR );
56#endif
57
58
59PUBLIC void
60Infer_recipe( cp, setdirroot )/*
61================================
62 Perform a breadth-first search of the inference graph and return if
63 possible an inferred set of prerequisites for making the current target. */
64CELLPTR cp;
65CELLPTR setdirroot;
66{
67 ICELLPTR nomatch, match;
68
69 DB_ENTER("Infer_recipe");
70
71 if( cp->ce_attr & A_NOINFER0x00080 ) {DB_VOID_RETURNreturn;}
1
Taking false branch
→
72
73 DB_PRINT("inf", ("Inferring rule for [%s]", cp->CE_NAME));
74
75 match = NIL(ICELL)((ICELL*)((void*)0));
76 {
77 char *tmp;
78 nomatch = add_iset( NIL(ICELL)((ICELL*)((void*)0)), NIL(ICELL)((ICELL*)((void*)0)), NIL(CELL)((CELL*)((void*)0)), NIL(DFALINK)((DFALINK*)((void*)0)),
79 setdirroot, Prep+count_dots(cp->CE_NAMEce_name->ht_name), 0,
80 tmp = DmStrDup(cp->CE_NAMEce_name->ht_name), NIL(char)((char*)((void*)0)),
81 cp->ce_time != (time_t)0L);
82 FREE(tmp)free((char*)(tmp));
83 }
84
85 /* Make sure we try whole heartedly to infer at least one suffix */
86 if( nomatch->ic_dmax == 0 ) ++nomatch->ic_dmax;
2
←
Taking false branch
→
87
88 DB_EXECUTE( "inf", _dump_iset("nomatch",nomatch); );
89
90 /* If nomatch is non-empty there was no match with an existing
91 * prerrequisite, try to derive one. */
92 while( nomatch != NIL(ICELL)((ICELL*)((void*)0)) ) {
3
←
Loop condition is true. Entering loop body
→
93 ICELLPTR new_nomatch = NIL(ICELL)((ICELL*)((void*)0));
94 ICELLPTR ic, pmatch, mmatch;
95 CELLPTR prereq;
96
97 for( ic=nomatch; ic != NIL(ICELL)((ICELL*)((void*)0)); ic=ic->ic_next ) {
4
←
Loop condition is true. Entering loop body
→
7
←
Loop condition is false. Execution continues on line 118
→
98 int ipush = FALSE0;
99
100 if( ic->ic_dir ) ipush = Push_dir(ic->ic_dir, ic->ic_name, FALSE0);
5
←
Taking false branch
→
101 match = union_iset(match, derive_prerequisites(ic, &new_nomatch));
102 if( ipush ) Pop_dir(FALSE0);
6
←
Taking false branch
→
103 }
104
105 DB_EXECUTE( "inf", _dump_iset("match",match); );
106 DB_EXECUTE( "inf", _dump_iset("nomatch",new_nomatch); );
107
108 /* We have now deduced the two sets MATCH and NOMATCH. MATCH holds the
109 * set of edges that we encountered that matched. If this set is empty
110 * then we can apply transitive closure (if enabled) to the elements of
111 * NOMATCH to see if we can find some other method to make the target.
112 *
113 * If MATCH is non-empty, we have found a method for making the target.
114 * It is the shortest method for doing so (ie. uses fewest number of
115 * steps). If MATCH contains more than one element then we have a
116 * possible ambiguity.
117 */
118 if( match == NIL(ICELL)((ICELL*)((void*)0)) ) {
8
←
Taking false branch
→
119 nomatch = new_nomatch;
120
121 /* Skip the rest and try one level deeper. */
122 if( Transitive ) continue;
123
124 goto all_done;
125 }
126
127 /* Ok, we have a set of possible matches in MATCH, we should check the
128 * set for ambiguity. If more than one inference path exists of the
129 * same depth, then we may issue an ambiguous inference error message.
130 *
131 * The message is suppressed if MATCH contains two elements and one of
132 * them is the empty-prerequisite-rule. In this case we ignore the
133 * ambiguity and take the rule that infers the prerequisite.
134 *
135 * Also if there are any chains that rely on a non-existant prerequisite
136 * that may get made because it has a recipe then we prefer any that
137 * rely on existing final prerequisites over those that we have to make.
138 */
139
140 /* Split out those that have to be made from those that end in
141 * prerequisites that already exist. */
142 pmatch = mmatch = NIL(ICELL)((ICELL*)((void*)0));
143 for(; match; match = ic ) {
9
←
Loop condition is true. Entering loop body
→
11
←
Loop condition is false. Execution continues on line 158
→
144 /* This loop checks all possible matches. */
145 DB_PRINT("inf", ("Target [%s] : prerequisite [%s]",
146 match->ic_meta->CE_NAME, match->ic_name));
147
148 ic = match->ic_next;
149 match->ic_next = NIL(ICELL)((ICELL*)((void*)0));
150
151 if( match->ic_exists )
10
←
Taking false branch
→
152 pmatch = union_iset(pmatch, match);
153 else
154 mmatch = union_iset(mmatch, match);
155 }
156
157 /* Prefer %-targets with existing prerequisites. */
158 if( pmatch )
12
←
Taking false branch
→
159 match = pmatch;
160 else
161 match = mmatch;
162
163 /* Make sure it is unique. It would be easy to check
164 * match->ic_meta->ce_prq for existence and prefer no prerequisites
165 * over prerequisites that are present, but we are currently not
166 * doing it. */
167 if( match->ic_next != NIL(ICELL)((ICELL*)((void*)0)) ) {
13
←
Taking false branch
→
168 int count = 1;
169
170 Warning( "Ambiguous inference chains for target '%s'", cp->CE_NAMEce_name->ht_name );
171 for( ic=match; ic; ic=ic->ic_next )
172 (void) dump_inf_chain(ic, TRUE1, count++);
173 Warning( "First matching rule is chosen.");
174 }
175
176 /* MATCH now points at the derived prerequisite chain(s). We must now
177 * take cp, and construct the correct graph so that the make may
178 * proceed. */
179
180 /* The folowing shows only the first element, i.e. the last matching
181 * recipe that was found. */
182 if( Verbose & V_INFER0x08 ) {
14
←
Taking false branch
→
183 char *tmp = dump_inf_chain(match, TRUE1, FALSE0);
184 printf("%s: Inferring prerequistes and recipes using:\n%s: ... %s\n",
185 Pname, Pname, tmp );
186 FREE(tmp)free((char*)(tmp));
187 }
188
189 pmatch = NIL(ICELL)((ICELL*)((void*)0));
190 prereq = NIL(CELL)((CELL*)((void*)0));
191
192 /* This loop treats the inferred targets last to first. */
193 while( match ) {
15
←
Loop condition is true. Entering loop body
→
19
←
Loop condition is true. Entering loop body
→
31
←
Loop condition is true. Entering loop body
→
194 CELLPTR infcell=NIL(CELL)((CELL*)((void*)0));
195
196 /* Compute the inferred prerequisite first. */
197 if( match->ic_name ) {
16
←
Taking false branch
→
20
←
Taking true branch
→
32
←
Taking true branch
→
198 if( match->ic_meta )
21
←
Taking false branch
→
33
←
Taking false branch
→
199 infcell = Def_cell( match->ic_name );
200 else
201 infcell = cp;
202
203 infcell->ce_flag |= F_TARGET0x0008;
204
205 if( infcell != cp ) {
22
←
Taking false branch
→
34
←
Taking false branch
→
206 infcell->ce_flag |= F_INFER0x4000|F_REMOVE0x1000;
207 DB_PRINT("remove", ("Mark for deletion [%s]",
208 infcell->CE_NAME));
209 }
210
211 if( !match->ic_flag )
23
←
Taking false branch
→
35
←
Taking false branch
→
212 infcell->ce_attr |= A_NOINFER0x00080;
213 }
214
215 /* Add global prerequisites from previous rule if there are any and
216 * the recipe. */
217 if( pmatch ) {
17
←
Taking false branch
→
24
←
Taking true branch
→
36
←
Taking true branch
→
218 CELLPTR imeta = pmatch->ic_meta;
219 LINKPTR lp;
220
221 DB_PRINT("inf", ("%%-target [%s] - infered target [%s]\n",
222 imeta->CE_NAME, infcell->CE_NAME));
223
224 infcell->ce_per = pmatch->ic_dfa->dl_per;
225 infcell->ce_attr |= (imeta->ce_attr & A_TRANSFER(0x00008 | 0x00001 | 0x00002 | 0x00800 | 0x00400 | 0x00200 | 0x00004
| 0x00020 | 0x00010 | 0x01000 | 0x04000 | 0x08000 ));
37
←
Access to field 'ce_attr' results in a dereference of a null pointer (loaded from variable 'imeta')
226
227 /* The .PHONY mechanism relies on having phony targets not
228 * being STATed and having a zero time stamp. While inferring
229 * the this target it might have been created and stated
230 * therefore these values need to be reset. */
231 if( infcell->ce_attr & A_PHONY0x04000 ){
25
←
Taking false branch
→
232 infcell->ce_time = 0L;
233 infcell->ce_flag &= ~F_STAT0x0040;
234 }
235
236 if( !(infcell->ce_flag & F_RULES0x0010) ) {
26
←
Taking false branch
→
237 infcell->ce_flag |= (imeta->ce_flag&(F_SINGLE0x0004|F_GROUP0x0020))|F_RULES0x0010;
238 infcell->ce_recipe = imeta->ce_recipe;
239 }
240
241 /* Add any conditional macro definitions that may be associated
242 * with the inferred cell. */
243 if (imeta->ce_cond != NIL(STRING)((STRING*)((void*)0))) {
27
←
Taking false branch
→
244 STRINGPTR sp,last;
245
246 last = infcell->ce_cond;
247 for(sp=imeta->ce_cond; sp; sp=sp->st_next) {
248 STRINGPTR new;
249 TALLOC(new, 1, STRING)if ((new = (STRING*) calloc((unsigned int)(1), (size_t)sizeof
(STRING))) == (STRING*)0) {No_ram();};
250 new->st_string = DmStrDup(sp->st_string);
251 if(last)
252 last->st_next = new;
253 else
254 infcell->ce_cond = new;
255 last = new;
256 }
257 }
258
259 pmatch->ic_dfa->dl_per = NIL(char)((char*)((void*)0));
260
261 /* If infcell already had a .SETDIR directory set then modify it
262 * based on whether it was the original cell or some intermediary. */
263 if( imeta->ce_dir ) {
28
←
Taking false branch
→
264 if( infcell->ce_dir && infcell == cp ) {
265 /* cp->ce_dir was set and we have pushed the directory prior
266 * to calling this routine.
267 * We build a new path by appending imeta->ce_dir to the
268 * current directory of the original cell.
269 * We should therefore pop it and push the new concatenated
270 * directory required by the inference.
271 * This leaks memory as cp->ce_dir is not freed before
272 * setting the new the new infcell->ce_dir value but as
273 * the pointer could be a `A_POOL` member we accept this. */
274 infcell->ce_dir = DmStrDup(Build_path(infcell->ce_dir,
275 imeta->ce_dir));
276 }
277 else {
278 /* Inherit a copy of the .SETDIR value. Use a copy because
279 * the original could have been freed in the meantime
280 * in Make() by the FREE() before _pool_lookup(). This can
281 * also leak if infcell->ce_dir was set before. */
282 infcell->ce_dir = DmStrDup(imeta->ce_dir);
283 }
284 }
285
286 for( lp=imeta->ce_indprq; lp != NIL(LINK)((LINK*)((void*)0)); lp=lp->cl_next ) {
29
←
Loop condition is false. Execution continues on line 303
→
287 char *name = lp->cl_prq->CE_NAMEce_name->ht_name;
288 CELLPTR tcp;
289
290 name = buildname( cp->CE_NAMEce_name->ht_name, name, infcell->ce_per );
291 tcp = Def_cell( name );
292 tcp->ce_flag |= F_REMOVE0x1000;
293 Add_prerequisite( infcell, tcp, FALSE0, FALSE0 );
294
295 if( Verbose & V_INFER0x08 )
296 printf( "%s: Inferred indirect prerequisite [%s]\n",
297 Pname, name );
298 FREE(name)free((char*)(name));
299 }
300 }
301
302 /* Add the previous cell as the prerequisite */
303 if( prereq )
18
←
Taking false branch
→
30
←
Taking false branch
→
304 (Add_prerequisite(infcell,prereq,FALSE0,FALSE0))->cl_flag |=F_TARGET0x0008;
305
306 pmatch = match; /* Previous member in inference chain ... */
307 prereq = infcell; /* is a prerequisite to the next match. */
308 /* ip->ic_parent is the next target in the inference chain to be
309 * build. If it is empty we are done. */
310 match = match->ic_parent;
311 }
312
313 DB_PRINT("inf", ("Terminated due to a match"));
314 break;
315 }
316
317 all_done:
318 free_icells();
319
320 DB_VOID_RETURNreturn;
321}
322
323
324static ICELLPTR
325derive_prerequisites( ic, nnmp )/*
326===================================
327 Take a cell and derive a set of prerequisites from the cell. Categorize
328 them into those that MATCH (ie. those that we found in the file system),
329 and those that do not match NOMATCH that we may possibly have a look at
330 later. When we process the next level of the breadth-first search.
331
332 Once MATCH is non-empty we will stop inserting elements into NOMATCH
333 since we know that either MATCH is successful and unique or it will
334 issue an ambiguity error. We will never go on to look at elements
335 in NOMATCH after wards. */
336ICELLPTR ic;
337ICELLPTR *nnmp;
338{
339 ICELLPTR match = NIL(ICELL)((ICELL*)((void*)0));
340 DFALINKPTR pdfa;
341 DFALINKPTR dfas;
342
343 DB_ENTER("derive_prerequisites");
344
345 DB_PRINT("inf", ("for [%s]\n", ic->ic_name));
346
347 /* If none of the inference nodes match then forget about the inference.
348 * The user did not tell us how to make such a target. We also stop the
349 * Inference if the new set of DFA's is a proper subset of a previous
350 * subset and it's PREP counts exceed the value of Prep.
351 */
352 dfas = dfa_subset( Match_dfa(ic->ic_name), &ic->ic_dfastack );
353
354 DB_EXECUTE("inf", _dump_dfa_stack(dfas, &ic->ic_dfastack); );
355
356 /* Ok, we have nothing here to work with so return an empty cell. */
357 if( dfas == NIL(DFALINK)((DFALINK*)((void*)0)) ) {
358 DB_PRINT( "mem", ("%s:<- mem %ld",ic->ic_name, (long)coreleft()));
359 DB_PRINT( "inf", ("<<< Exit, no dfas, cp = %04x", NIL(CELL)) );
360 DB_RETURN( NIL(ICELL) )return (((ICELL*)((void*)0)));
361 }
362
363 /* Save the dfas, we are going to use on the stack for this cell. */
364 ic->ic_dfastack.df_set = dfas;
365
366 /* Run through the %-meta cells, build the prerequisite cells. For each
367 * %-meta go through it's list of edges and try to use each in turn to
368 * deduce a likely prerequisite. We perform a breadth-first search
369 * matching the first path that results in a unique method for making the
370 * target. */
371 for( pdfa = dfas; pdfa != NIL(DFALINK)((DFALINK*)((void*)0)); pdfa = pdfa->dl_next ) {
372 LINK tl;
373 LINKPTR edge;
374 CELLPTR pmeta;
375
376 pmeta = pdfa->dl_meta;
377 DB_PRINT( "inf", ("Using dfa: [%s]", pmeta->CE_NAME) );
378
379 /* If the %-meta is a singleton meta then deal with it differently from
380 * the case when it is a bunch of %-meta's found on the original entries
381 * prerequisite list. */
382 if( pmeta->ce_flag & F_MULTI0x0002 )
383 edge = pmeta->ce_prq;
384 else {
385 tl.cl_prq = pmeta;
386 tl.cl_next = NIL(LINK)((LINK*)((void*)0));
387 edge = &tl;
388 }
389
390 /* Now run through the list of prerequisite edge's for the %-meta. */
391 for( ; edge != NIL(LINK)((LINK*)((void*)0)); edge = edge->cl_next ) {
392 HASHPTR thp = 0; /* temporary hash table pointer */
393 HASH iprqh; /* hash cell for new prerequisite */
394 CELL iprq; /* inferred prerequisite to look for */
395 CELLPTR idirroot; /* Inferred prerequisite root */
396 CELLPTR nidirroot; /* Inferred prerequisite root */
397 STRINGPTR ircp = 0; /* Inferred prerequisites recipe */
398 char *idir; /* directory to CD to. */
399 int ipush = 0; /* flag for push on inferred prereq */
400 char *name = NIL(char)((char*)((void*)0)); /* prerequisite name */
401 CELLPTR meta = edge->cl_prq;
402 int trans;
403 int noinf;
404 int exists;
405
406 /* Name of the prerequisite, can be empty. */
407 if( meta->ce_prq )
408 name = meta->ce_prq->cl_prq->CE_NAMEce_name->ht_name;
409
410 DB_PRINT( "inf", ("Trying edge from [%s] to [%s] for [%s]",
411 meta->CE_NAME, name?name:"(nil)", ic->ic_name) );
412
413 /* Set the temp CELL used for building prerequisite candidates to
414 * all zero so that we don't have to keep initializing all the
415 * fields. */
416 {
417 register char *s = (char *) &iprq;
418 register int n = sizeof(CELL);
419 while( n ) { *s++ = '\0'; n--; }
420 }
421
422 nidirroot = idirroot = ic->ic_setdirroot;
423 iprq.ce_name = &iprqh;
424
425 if( name ) {
426 /* Build the prerequisite name from the %-meta prerequisite given
427 * for the %-meta rule. */
428 int dmax_fix;
429 iprqh.ht_name = buildname( ic->ic_name, name, pdfa->dl_per );
430 if((dmax_fix = (count_dots(name)-count_dots(meta->CE_NAMEce_name->ht_name))) < 0)
431 dmax_fix = 0;
432
433 if( !strcmp(ic->ic_name, iprqh.ht_name) ||
434 (count_dots(iprqh.ht_name) > ic->ic_dmax + dmax_fix) ) {
435 FREE( iprqh.ht_name )free((char*)(iprqh.ht_name));
436 continue;
437 }
438
439 DB_PRINT( "inf", ("Checking prerequisite [%s]", iprqh.ht_name) );
440
441 /* See if the prerequisite CELL has been previously defined. If
442 * it has, then make a copy of it into iprq, and use it to try
443 * the inference. We make the copy so that we don't modify the
444 * stat of the inferred cell if the inference fails.
445 */
446 thp = Get_name( iprqh.ht_name, Defs, FALSE0 );
447 if(thp != NIL(HASH)((HASH*)((void*)0))) {
448 iprq = *thp->CP_OWNRvar.val.ht.ht_owner;
449 /* Check if a recipe for this target exists. Targets with F_MULTI
450 * set need each cell checked for existing recipes.
451 */
452 if( iprq.ce_flag & F_MULTI0x0002 ) {
453 /* Walk through all cells of this target. */
454 LINKPTR mtcp = iprq.ce_prq;
455 ircp = NIL(STRING)((STRING*)((void*)0));
456 for( ; mtcp != NIL(LINK)((LINK*)((void*)0)); mtcp = mtcp->cl_next ) {
457 /* If a recipe is found stop searching and set ircp to that result.
458 * ircp is not used but only checked if it is set.
459 */
460 if( mtcp->cl_prq->ce_recipe != NIL(STRING)((STRING*)((void*)0)) ) {
461 ircp = mtcp->cl_prq->ce_recipe;
462 break;
463 }
464 }
465 }
466 else
467 ircp = iprq.ce_recipe;
468 }
469 else
470 ircp = NIL(STRING)((STRING*)((void*)0));
471 }
472 else
473 iprqh.ht_name = NIL(char)((char*)((void*)0));
474
475
476 /* If the %-meta has a .SETDIR set then we change to the new
477 * directory prior to performing the stat of the new prerequisite.
478 * If the change of directory fails then the rule is droped from
479 * further consideration.
480 */
481 if( iprq.ce_dir ) {
482 if( (ipush = Push_dir(iprq.ce_dir, iprqh.ht_name, TRUE1)) != 0 ) {
483 nidirroot = thp->CP_OWNRvar.val.ht.ht_owner;
484 idir = Pwd;
485 }
486 else {
487 if( iprqh.ht_name ) FREE( iprqh.ht_name )free((char*)(iprqh.ht_name));
488 continue;
489 }
490 }
491 else
492 idir = NIL(char)((char*)((void*)0));
493
494
495 /* Stat the inferred prerequisite.
496 */
497 if( name ) {
498 if( Verbose & V_INFER0x08 )
499 printf( "%s: Trying prerequisite [%s] for [%s]\n", Pname,
500 iprqh.ht_name, ic->ic_name );
501
502 /* irpq is a temporary target cell, a stat will not be remembered. */
503 if( !(iprq.ce_flag & F_STAT0x0040) ) Stat_target(&iprq, FALSE0, FALSE0);
504 }
505
506
507 /* If the STAT succeeded or if the prerequisite has a recipe for
508 * making it then it's a match and a candidate for getting infered.
509 * Otherwise it is not a match, and we cannot yet tell if it is
510 * going to be a successful path to follow, so we save it for
511 * later consideration.
512 */
513 noinf = ((Glob_attr)&A_NOINFER0x00080);
514 if( meta->ce_prq )
515 noinf |= ((meta->ce_prq->cl_prq->ce_attr)&A_NOINFER0x00080);
516 trans = Transitive || !noinf;
517
518 /* If no prereq is given treat it as if it is existing. */
519 exists = (iprq.ce_time != (time_t)0L) || (name == NIL(char)((char*)((void*)0)));
520
521 if( exists || (ircp != NIL(STRING)((STRING*)((void*)0))) || !name ) {
522 match = add_iset( match, ic, meta, pdfa, idirroot, ic->ic_dmax,
523 trans, iprq.ce_name->ht_name, idir, exists );
524 DB_PRINT("inf",("Added to MATCH %s",iprq.ce_name->ht_name));
525 }
526 else if( !noinf && match == NIL(ICELL)((ICELL*)((void*)0)) ) {
527 *nnmp = add_iset( *nnmp, ic, meta, pdfa, nidirroot, ic->ic_dmax,
528 trans, iprq.ce_name->ht_name, idir, exists );
529 DB_PRINT("inf",("Added to NOMATCH %s",iprq.ce_name->ht_name));
530 }
531
532 /* If we pushed a directory for the inferred prerequisite then
533 * pop it.
534 */
535 if( ipush ) Pop_dir(FALSE0);
536 if( iprqh.ht_name ) FREE(iprqh.ht_name)free((char*)(iprqh.ht_name));
537 }
538 }
539
540 DB_RETURN(match)return (match);
541}
542
543
544static char *
545buildname( tg, meta, per )/*
546============================
547 Replace '%' with per in meta. Expand the result and return it. */
548char *tg; /* Current target name. */
549char *meta;
550char *per;
551{
552 char *name;
553
554 name = Apply_edit( meta, "%", per, FALSE0, FALSE0 );
555 /* Handle infered dynamic prerequisites. */
556 if( strchr(name, '$') ) {
557 HASHPTR m_at;
558 char *tmp;
559
560 /* Set $@ so that a Expand() can use it and remove it afterwards. */
561 /* Is $@ already expanded? FIXME: Remove this check later. */
562 if( *DmStrPbrk( tg, "${}" ) != '\0' )
563 Fatal("$@ [%s] not fully expanded!", tg);
564 m_at = Def_macro( "@", DO_WINPATH(tg)tg, M_MULTI0x0004|M_EXPANDED0x0008 );
565 tmp = Expand( name );
566
567 if( m_at->ht_value != NIL(char)((char*)((void*)0)) ) {
568 FREE( m_at->ht_value )free((char*)(m_at->ht_value));
569 m_at->ht_value = NIL(char)((char*)((void*)0));
570 }
571
572 /* Free name if Apply_edit() did something. */
573 if( name != meta ) FREE( name )free((char*)(name));
574 name = tmp;
575 }
576 else if( name == meta )
577 name = DmStrDup( name );
578
579 return(name);
580}
581
582
583static DFALINKPTR
584dfa_subset( pdfa, stack )/*
585============================
586 This is the valid DFA subset computation. Whenever a CELL has a Match_dfa
587 subset computed this algorithm is run to see if any of the previously
588 computed sets on the DFA stack are proper subsets of the new set. If they
589 are, then any elements of the matching subset whose Prep counts exceed
590 the allowed maximum given by Prep are removed from the computed DFA set,
591 and hence from consideration, thereby cutting off the cycle in the
592 inference graph. */
593DFALINKPTR pdfa;
594register DFASETPTR stack;
595{
596 register DFALINKPTR element;
597 DFALINKPTR nelement;
598
599 DB_ENTER( "dfa_subset" );
600
601 DB_PRINT("inf",("Computing DFA subset, PREP = %d",Prep));
602 DB_EXECUTE("inf", _dump_dfa_stack(pdfa, stack); );
603
604 for(; pdfa != NIL(DFALINK)((DFALINK*)((void*)0)) && stack != NIL(DFASET)((DFASET*)((void*)0)); stack = stack->df_next) {
605 int subset = TRUE1;
606
607 for( element=stack->df_set; subset && element != NIL(DFALINK)((DFALINK*)((void*)0));
608 element=element->dl_next ) {
609 register DFALINKPTR subel;
610
611 for( subel = pdfa;
612 subel != NIL(DFALINK)((DFALINK*)((void*)0)) && (subel->dl_meta != element->dl_meta);
613 subel = subel->dl_next );
614
615 DB_PRINT("inf",("Looking for %s, (%s)",element->dl_meta->CE_NAME,
616 (subel != NIL(DFALINK))?"succ":"fail"));
617
618 if( (subset = (subel != NIL(DFALINK)((DFALINK*)((void*)0)))) != 0 )
619 element->dl_member = subel;
620 }
621
622 if( subset )
623 for( element=stack->df_set; element != NIL(DFALINK)((DFALINK*)((void*)0));
624 element=element->dl_next ) {
625 DFALINKPTR mem = element->dl_member;
626 int npr = element->dl_prep + 1;
627
628 if( npr > Prep )
629 mem->dl_delete++;
630 else
631 mem->dl_prep = npr;
632 }
633 }
634
635 for( element = pdfa; element != NIL(DFALINK)((DFALINK*)((void*)0)); element = nelement ) {
636 nelement = element->dl_next;
637
638 if( element->dl_delete ) {
639 /* A member of the subset has a PREP count equal to PREP, so
640 * it should not be considered further in the inference, hence
641 * we remove it from the doubly linked set list */
642 if( element == pdfa )
643 pdfa = element->dl_next;
644 else
645 element->dl_prev->dl_next = element->dl_next;
646
647 if( element->dl_next != NIL(DFALINK)((DFALINK*)((void*)0)) )
648 element->dl_next->dl_prev = element->dl_prev;
649
650 DB_PRINT("inf", ("deleting dfa [%s]", element->dl_meta->CE_NAME));
651 FREE( element->dl_per )free((char*)(element->dl_per));
652 FREE( element )free((char*)(element));
653 }
654 }
655
656 DB_RETURN( pdfa )return (pdfa);
657}
658
659
660
661static void
662free_dfas( chain )/*
663=====================
664 Free the list of DFA's constructed by Match_dfa, and linked together by
665 LINK cells. FREE the % value as well, as long as it isn't NIL. */
666DFALINKPTR chain;
667{
668 register DFALINKPTR tl;
669
670 DB_ENTER( "free_dfas" );
671
672 for( tl=chain; tl != NIL(DFALINK)((DFALINK*)((void*)0)); chain = tl ) {
673 tl = tl->dl_next;
674
675 DB_PRINT( "inf", ("Freeing DFA [%s], %% = [%s]", chain->dl_meta->CE_NAME,
676 chain->dl_per) );
677
678 if( chain->dl_per != NIL(char)((char*)((void*)0)) ) FREE( chain->dl_per )free((char*)(chain->dl_per));
679 FREE( chain )free((char*)(chain));
680 }
681
682 DB_VOID_RETURNreturn;
683}
684
685
686static int
687count_dots( name )/*
688=====================*/
689char *name;
690{
691 register char *p;
692 register int i = 0;
693
694 for( p = name; *p; p++ ) if(*p == '.') i++;
695
696 return( i );
697}
698
699
700static ICELLPTR _icells = NIL(ICELL)((ICELL*)((void*)0));
701#ifdef DBUG
702static int _icell_cost = 0;
703#endif
704
705static ICELLPTR
706add_iset( iset, parent, meta, dfa, setdirroot, dmax, noinf, name, dir, exists)
707ICELLPTR iset;
708ICELLPTR parent;
709CELLPTR meta;
710DFALINKPTR dfa;
711CELLPTR setdirroot;
712int dmax;
713int noinf;
714char *name;
715char *dir;
716int exists;
717{
718 ICELLPTR icell;
719
720 DB_ENTER("add_iset");
721 TALLOC(icell, 1, ICELL)if ((icell = (ICELL*) calloc((unsigned int)(1), (size_t)sizeof
(ICELL))) == (ICELL*)0) {No_ram();};
722
723 DB_EXECUTE("inf", _icell_cost+=(sizeof(ICELL)+strlen(dir?dir:"")+strlen(name?name:"")+2););
724
725 icell->ic_meta = meta;
726 icell->ic_dfa = dfa;
727 icell->ic_setdirroot = setdirroot;
728
729 if( parent ) icell->ic_dfastack.df_next = &parent->ic_dfastack;
730
731 icell->ic_dmax = dmax;
732 icell->ic_dir = DmStrDup(dir);
733 icell->ic_name = DmStrDup(name);
734 icell->ic_parent = parent;
735 icell->ic_next = iset;
736 icell->ic_flag = noinf;
737 icell->ic_exists = exists;
738
739 icell->ic_link = _icells;
740 _icells = icell;
741
742 DB_RETURN(icell)return (icell);
743}
744
745
746static void
747free_icells()
748{
749 register ICELLPTR ic;
750
751 DB_ENTER("free_icells");
752
753 for( ; _icells; _icells = ic ) {
754 ic = _icells->ic_link;
755
756 free_dfas(_icells->ic_dfastack.df_set);
757 if( _icells->ic_dir ) FREE(_icells->ic_dir)free((char*)(_icells->ic_dir));
758 if( _icells->ic_name) FREE(_icells->ic_name)free((char*)(_icells->ic_name));
759 FREE(_icells)free((char*)(_icells));
760 }
761
762 DB_PRINT("inf",("Used %d memory for icells",_icell_cost));
763 DB_EXECUTE("inf", _icell_cost=0; );
764
765 DB_VOID_RETURNreturn;
766}
767
768
769static ICELLPTR
770union_iset( iset, uset )
771ICELLPTR iset;
772ICELLPTR uset;
773{
774 register ICELLPTR ic;
775
776 if( iset == NIL(ICELL)((ICELL*)((void*)0)) ) return(uset);
777
778 for( ic=iset; ic->ic_next != NIL(ICELL)((ICELL*)((void*)0)); ic=ic->ic_next );
779 ic->ic_next = uset;
780
781 return(iset);
782}
783
784
785static char *
786dump_inf_chain( ip, flag, print )/*
787===================================
788Return string with infered prerequisites.
789flag == TRUE adds the top of the chain.
790print == TRUE prints to screen with number "print" and returns NULL. */
791ICELLPTR ip;
792int flag;
793int print;
794{
795 char *tmp;
796
797 if( ip == NIL(ICELL)((ICELL*)((void*)0)) ) return(NIL(char)((char*)((void*)0)));
798
799 /* ip->ic_parent is the target to be build after ip. */
800 tmp = dump_inf_chain(ip->ic_parent, FALSE0, FALSE0);
801
802 if( ip->ic_meta ) {
803 tmp = DmStrJoin(tmp, "(", -1, TRUE1);
804 tmp = DmStrJoin(tmp, ip->ic_meta->CE_NAMEce_name->ht_name, -1, TRUE1);
805
806 if( ip->ic_dir && !*ip->ic_dir ) {
807 tmp = DmStrJoin(tmp, "[", -1, TRUE1);
808 if( strncmp(Makedir,ip->ic_dir, strlen(Makedir)) )
809 tmp = DmStrJoin(tmp, ip->ic_dir, -1, TRUE1);
810 else
811 tmp = DmStrJoin(tmp, ip->ic_dir+strlen(Makedir)+1, -1, TRUE1);
812 tmp = DmStrJoin(tmp, "]", -1, TRUE1);
813 }
814 tmp = DmStrJoin(tmp, (ip->ic_name)?") -->":")", -1, TRUE1);
815 }
816
817 if( ip->ic_name ) tmp = DmStrApp( tmp, ip->ic_name );
818
819 if( flag && ip->ic_meta->ce_prq) {
820 tmp = DmStrJoin(tmp, "(", -1, TRUE1);
821 tmp = DmStrJoin(tmp, ip->ic_meta->ce_prq->cl_prq->CE_NAMEce_name->ht_name, -1, TRUE1);
822 tmp = DmStrJoin(tmp, ")", -1, TRUE1);
823 }
824
825 if( print ) {
826 fprintf( stderrstderr, "%s: %2d. %s\n", Pname, print, tmp );
827 FREE(tmp)free((char*)(tmp));
828 tmp = NIL(char)((char*)((void*)0));
829 }
830
831 return(tmp);
832}
833
834
835#ifdef DBUG
836static void
837_dump_dfa_stack(dfas, dfa_stack)
838DFALINKPTR dfas;
839DFASETPTR dfa_stack;
840{
841 register DFALINKPTR pdfa;
842 char *tmp = NIL(char)((char*)((void*)0));
843 DFASETPTR ds;
844
845 for( pdfa = dfas; pdfa != NIL(DFALINK)((DFALINK*)((void*)0)); pdfa = pdfa->dl_next )
846 tmp = DmStrApp( tmp, pdfa->dl_meta->CE_NAMEce_name->ht_name );
847
848 tmp = DmStrApp( tmp, ":: {" );
849 for( ds = dfa_stack; ds != NIL(DFASET)((DFASET*)((void*)0)); ds = ds->df_next ) {
850 tmp = DmStrApp( tmp, "[" );
851 for( pdfa = ds->df_set; pdfa != NIL(DFALINK)((DFALINK*)((void*)0)); pdfa = pdfa->dl_next )
852 tmp = DmStrApp( tmp, pdfa->dl_meta->CE_NAMEce_name->ht_name );
853 tmp = DmStrApp( tmp, "]" );
854 }
855 tmp = DmStrApp( tmp, "}" );
856
857 printf( "DFA set and stack contents:\n%s\n", tmp );
858 FREE(tmp)free((char*)(tmp));
859}
860
861
862static void
863_dump_iset( name, iset )
864char *name;
865ICELLPTR iset;
866{
867 int cell = 0;
868
869 printf( "**** ISET for %s\n", name );
870 for( ; iset != NIL(ICELL)((ICELL*)((void*)0)); iset = iset->ic_next ){
871 printf( "cell %d\n", cell++ );
872 if( iset->ic_meta )
873 printf( "edge: %s --> %s\n", iset->ic_meta->CE_NAMEce_name->ht_name,
874 iset->ic_meta->ce_prq ?
875 iset->ic_meta->ce_prq->cl_prq->CE_NAMEce_name->ht_name :
876 "(nil)" );
877 else
878 printf( "edge: (nil)\n" );
879
880 if( iset->ic_dfa )
881 printf( "dfa: %s\n", iset->ic_dfa->dl_meta->CE_NAMEce_name->ht_name );
882 else
883 printf( "dfa: (nil)\n" );
884
885 printf( "sdr: %p\n", iset->ic_setdirroot );
886 _dump_dfa_stack(iset->ic_dfastack.df_set, &iset->ic_dfastack);
887
888 printf( "dmax: %d\n", iset->ic_dmax );
889 printf( "name: %s\n", iset->ic_name );
890 printf( "dir: %s\n", iset->ic_dir?iset->ic_dir:"(nil)" );
891
892 printf( "parent: " );
893 if( iset->ic_parent )
894 if( iset->ic_parent->ic_meta )
895 printf( "%s --> %s\n",
896 iset->ic_parent->ic_meta->CE_NAMEce_name->ht_name,
897 iset->ic_parent->ic_meta->ce_prq ?
898 iset->ic_parent->ic_meta->ce_prq->cl_prq->CE_NAMEce_name->ht_name :
899 "(nil)" );
900 else
901 printf( "(nil)\n" );
902 else
903 printf( "(nil)\n" );
904 }
905 printf( "==================================\n" );
906}
907#endif