Line data 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 (A_EPILOG | A_PRECIOUS | A_SILENT | A_SHELL | A_SETDIR |\
37 : A_SEQ | A_LIBRARY | A_IGNORE | A_PROLOG | A_SWAP |\
38 : A_PHONY | A_NOSTATE )
39 :
40 :
41 : /* Define local static functions */
42 : static DFALINKPTR dfa_subset ANSI((DFALINKPTR, DFASETPTR));
43 : static void free_dfas ANSI((DFALINKPTR));
44 : static int count_dots ANSI((char *));
45 : static char * buildname ANSI((char *, char *, char *));
46 : static void free_icells ANSI((void));
47 : static ICELLPTR union_iset ANSI((ICELLPTR, ICELLPTR));
48 : static ICELLPTR add_iset ANSI((ICELLPTR,ICELLPTR,CELLPTR,DFALINKPTR,
49 : CELLPTR,int,int,char *,char *, int));
50 : static ICELLPTR derive_prerequisites ANSI((ICELLPTR, ICELLPTR *));
51 : static char * dump_inf_chain ANSI((ICELLPTR, int, int));
52 :
53 : #ifdef DBUG
54 : static void _dump_dfa_stack ANSI((DFALINKPTR, DFASETPTR));
55 : static void _dump_iset ANSI(( char *, ICELLPTR ));
56 : #endif
57 :
58 :
59 : PUBLIC void
60 34255 : Infer_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. */
64 : CELLPTR cp;
65 : CELLPTR setdirroot;
66 : {
67 : ICELLPTR nomatch, match;
68 :
69 : DB_ENTER("Infer_recipe");
70 :
71 34255 : if( cp->ce_attr & A_NOINFER ) {DB_VOID_RETURN;}
72 :
73 : DB_PRINT("inf", ("Inferring rule for [%s]", cp->CE_NAME));
74 :
75 34255 : match = NIL(ICELL);
76 : {
77 : char *tmp;
78 102765 : nomatch = add_iset( NIL(ICELL), NIL(ICELL), NIL(CELL), NIL(DFALINK),
79 34255 : setdirroot, Prep+count_dots(cp->CE_NAME), 0,
80 34255 : tmp = DmStrDup(cp->CE_NAME), NIL(char),
81 34255 : cp->ce_time != (time_t)0L);
82 34255 : FREE(tmp);
83 : }
84 :
85 : /* Make sure we try whole heartedly to infer at least one suffix */
86 34255 : if( nomatch->ic_dmax == 0 ) ++nomatch->ic_dmax;
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 98011 : while( nomatch != NIL(ICELL) ) {
93 34255 : ICELLPTR new_nomatch = NIL(ICELL);
94 : ICELLPTR ic, pmatch, mmatch;
95 : CELLPTR prereq;
96 :
97 68510 : for( ic=nomatch; ic != NIL(ICELL); ic=ic->ic_next ) {
98 34255 : int ipush = FALSE;
99 :
100 34255 : if( ic->ic_dir ) ipush = Push_dir(ic->ic_dir, ic->ic_name, FALSE);
101 34255 : match = union_iset(match, derive_prerequisites(ic, &new_nomatch));
102 34255 : if( ipush ) Pop_dir(FALSE);
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 34255 : if( match == NIL(ICELL) ) {
119 29501 : nomatch = new_nomatch;
120 :
121 : /* Skip the rest and try one level deeper. */
122 29501 : 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 4754 : pmatch = mmatch = NIL(ICELL);
143 9508 : for(; match; match = ic ) {
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 4754 : ic = match->ic_next;
149 4754 : match->ic_next = NIL(ICELL);
150 :
151 4754 : if( match->ic_exists )
152 4754 : pmatch = union_iset(pmatch, match);
153 : else
154 0 : mmatch = union_iset(mmatch, match);
155 : }
156 :
157 : /* Prefer %-targets with existing prerequisites. */
158 4754 : if( pmatch )
159 4754 : match = pmatch;
160 : else
161 0 : 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 4754 : if( match->ic_next != NIL(ICELL) ) {
168 0 : int count = 1;
169 :
170 0 : Warning( "Ambiguous inference chains for target '%s'", cp->CE_NAME );
171 0 : for( ic=match; ic; ic=ic->ic_next )
172 0 : (void) dump_inf_chain(ic, TRUE, count++);
173 0 : 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 4754 : if( Verbose & V_INFER ) {
183 0 : char *tmp = dump_inf_chain(match, TRUE, FALSE);
184 0 : printf("%s: Inferring prerequistes and recipes using:\n%s: ... %s\n",
185 : Pname, Pname, tmp );
186 0 : FREE(tmp);
187 : }
188 :
189 4754 : pmatch = NIL(ICELL);
190 4754 : prereq = NIL(CELL);
191 :
192 : /* This loop treats the inferred targets last to first. */
193 19016 : while( match ) {
194 9508 : CELLPTR infcell=NIL(CELL);
195 :
196 : /* Compute the inferred prerequisite first. */
197 9508 : if( match->ic_name ) {
198 9376 : if( match->ic_meta )
199 4622 : infcell = Def_cell( match->ic_name );
200 : else
201 4754 : infcell = cp;
202 :
203 9376 : infcell->ce_flag |= F_TARGET;
204 :
205 9376 : if( infcell != cp ) {
206 4622 : infcell->ce_flag |= F_INFER|F_REMOVE;
207 : DB_PRINT("remove", ("Mark for deletion [%s]",
208 : infcell->CE_NAME));
209 : }
210 :
211 9376 : if( !match->ic_flag )
212 4754 : infcell->ce_attr |= A_NOINFER;
213 : }
214 :
215 : /* Add global prerequisites from previous rule if there are any and
216 : * the recipe. */
217 9508 : if( pmatch ) {
218 4754 : 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 4754 : infcell->ce_per = pmatch->ic_dfa->dl_per;
225 4754 : infcell->ce_attr |= (imeta->ce_attr & A_TRANSFER);
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 4754 : if( infcell->ce_attr & A_PHONY ){
232 2 : infcell->ce_time = 0L;
233 2 : infcell->ce_flag &= ~F_STAT;
234 : }
235 :
236 4754 : if( !(infcell->ce_flag & F_RULES) ) {
237 4754 : infcell->ce_flag |= (imeta->ce_flag&(F_SINGLE|F_GROUP))|F_RULES;
238 4754 : infcell->ce_recipe = imeta->ce_recipe;
239 : }
240 :
241 : /* Add any conditional macro definitions that may be associated
242 : * with the inferred cell. */
243 4754 : if (imeta->ce_cond != NIL(STRING)) {
244 : STRINGPTR sp,last;
245 :
246 0 : last = infcell->ce_cond;
247 0 : for(sp=imeta->ce_cond; sp; sp=sp->st_next) {
248 : STRINGPTR new;
249 0 : TALLOC(new, 1, STRING);
250 0 : new->st_string = DmStrDup(sp->st_string);
251 0 : if(last)
252 0 : last->st_next = new;
253 : else
254 0 : infcell->ce_cond = new;
255 0 : last = new;
256 : }
257 : }
258 :
259 4754 : pmatch->ic_dfa->dl_per = NIL(char);
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 4754 : if( imeta->ce_dir ) {
264 0 : 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 0 : 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 0 : infcell->ce_dir = DmStrDup(imeta->ce_dir);
283 : }
284 : }
285 :
286 4754 : for( lp=imeta->ce_indprq; lp != NIL(LINK); lp=lp->cl_next ) {
287 0 : char *name = lp->cl_prq->CE_NAME;
288 : CELLPTR tcp;
289 :
290 0 : name = buildname( cp->CE_NAME, name, infcell->ce_per );
291 0 : tcp = Def_cell( name );
292 0 : tcp->ce_flag |= F_REMOVE;
293 0 : Add_prerequisite( infcell, tcp, FALSE, FALSE );
294 :
295 0 : if( Verbose & V_INFER )
296 0 : printf( "%s: Inferred indirect prerequisite [%s]\n",
297 : Pname, name );
298 0 : FREE(name);
299 : }
300 : }
301 :
302 : /* Add the previous cell as the prerequisite */
303 9508 : if( prereq )
304 4622 : (Add_prerequisite(infcell,prereq,FALSE,FALSE))->cl_flag |=F_TARGET;
305 :
306 9508 : pmatch = match; /* Previous member in inference chain ... */
307 9508 : 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 9508 : match = match->ic_parent;
311 : }
312 :
313 : DB_PRINT("inf", ("Terminated due to a match"));
314 : break;
315 : }
316 :
317 : all_done:
318 34255 : free_icells();
319 :
320 34255 : DB_VOID_RETURN;
321 : }
322 :
323 :
324 : static ICELLPTR
325 34255 : derive_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. */
336 : ICELLPTR ic;
337 : ICELLPTR *nnmp;
338 : {
339 34255 : ICELLPTR match = NIL(ICELL);
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 34255 : 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 34255 : if( dfas == NIL(DFALINK) ) {
358 : DB_PRINT( "mem", ("%s:<- mem %ld",ic->ic_name, (long)coreleft()));
359 : DB_PRINT( "inf", ("<<< Exit, no dfas, cp = %04x", NIL(CELL)) );
360 29501 : DB_RETURN( NIL(ICELL) );
361 : }
362 :
363 : /* Save the dfas, we are going to use on the stack for this cell. */
364 4754 : 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 9514 : for( pdfa = dfas; pdfa != NIL(DFALINK); pdfa = pdfa->dl_next ) {
372 : LINK tl;
373 : LINKPTR edge;
374 : CELLPTR pmeta;
375 :
376 4760 : 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 4760 : if( pmeta->ce_flag & F_MULTI )
383 4760 : edge = pmeta->ce_prq;
384 : else {
385 0 : tl.cl_prq = pmeta;
386 0 : tl.cl_next = NIL(LINK);
387 0 : edge = &tl;
388 : }
389 :
390 : /* Now run through the list of prerequisite edge's for the %-meta. */
391 9574 : for( ; edge != NIL(LINK); edge = edge->cl_next ) {
392 4814 : 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 4814 : STRINGPTR ircp = 0; /* Inferred prerequisites recipe */
398 : char *idir; /* directory to CD to. */
399 4814 : int ipush = 0; /* flag for push on inferred prereq */
400 4814 : char *name = NIL(char); /* prerequisite name */
401 4814 : CELLPTR meta = edge->cl_prq;
402 : int trans;
403 : int noinf;
404 : int exists;
405 :
406 : /* Name of the prerequisite, can be empty. */
407 4814 : if( meta->ce_prq )
408 4682 : name = meta->ce_prq->cl_prq->CE_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 4814 : register char *s = (char *) &iprq;
418 4814 : register int n = sizeof(CELL);
419 4814 : while( n ) { *s++ = '\0'; n--; }
420 : }
421 :
422 4814 : nidirroot = idirroot = ic->ic_setdirroot;
423 4814 : iprq.ce_name = &iprqh;
424 :
425 4814 : if( name ) {
426 : /* Build the prerequisite name from the %-meta prerequisite given
427 : * for the %-meta rule. */
428 : int dmax_fix;
429 4682 : iprqh.ht_name = buildname( ic->ic_name, name, pdfa->dl_per );
430 4682 : if((dmax_fix = (count_dots(name)-count_dots(meta->CE_NAME))) < 0)
431 4604 : dmax_fix = 0;
432 :
433 9364 : if( !strcmp(ic->ic_name, iprqh.ht_name) ||
434 4682 : (count_dots(iprqh.ht_name) > ic->ic_dmax + dmax_fix) ) {
435 0 : FREE( iprqh.ht_name );
436 0 : 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 4682 : thp = Get_name( iprqh.ht_name, Defs, FALSE );
447 4682 : if(thp != NIL(HASH)) {
448 48 : iprq = *thp->CP_OWNR;
449 : /* Check if a recipe for this target exists. Targets with F_MULTI
450 : * set need each cell checked for existing recipes.
451 : */
452 48 : if( iprq.ce_flag & F_MULTI ) {
453 : /* Walk through all cells of this target. */
454 0 : LINKPTR mtcp = iprq.ce_prq;
455 0 : ircp = NIL(STRING);
456 0 : for( ; mtcp != NIL(LINK); 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 0 : if( mtcp->cl_prq->ce_recipe != NIL(STRING) ) {
461 0 : ircp = mtcp->cl_prq->ce_recipe;
462 0 : break;
463 : }
464 : }
465 : }
466 : else
467 48 : ircp = iprq.ce_recipe;
468 : }
469 : else
470 4634 : ircp = NIL(STRING);
471 : }
472 : else
473 132 : iprqh.ht_name = NIL(char);
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 4814 : if( iprq.ce_dir ) {
482 0 : if( (ipush = Push_dir(iprq.ce_dir, iprqh.ht_name, TRUE)) != 0 ) {
483 0 : nidirroot = thp->CP_OWNR;
484 0 : idir = Pwd;
485 : }
486 : else {
487 0 : if( iprqh.ht_name ) FREE( iprqh.ht_name );
488 0 : continue;
489 : }
490 : }
491 : else
492 4814 : idir = NIL(char);
493 :
494 :
495 : /* Stat the inferred prerequisite.
496 : */
497 4814 : if( name ) {
498 4682 : if( Verbose & V_INFER )
499 0 : 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 4682 : if( !(iprq.ce_flag & F_STAT) ) Stat_target(&iprq, FALSE, FALSE);
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 4814 : noinf = ((Glob_attr)&A_NOINFER);
514 4814 : if( meta->ce_prq )
515 4682 : noinf |= ((meta->ce_prq->cl_prq->ce_attr)&A_NOINFER);
516 4814 : trans = Transitive || !noinf;
517 :
518 : /* If no prereq is given treat it as if it is existing. */
519 4814 : exists = (iprq.ce_time != (time_t)0L) || (name == NIL(char));
520 :
521 4814 : if( exists || (ircp != NIL(STRING)) || !name ) {
522 4754 : match = add_iset( match, ic, meta, pdfa, idirroot, ic->ic_dmax,
523 4754 : trans, iprq.ce_name->ht_name, idir, exists );
524 : DB_PRINT("inf",("Added to MATCH %s",iprq.ce_name->ht_name));
525 : }
526 60 : else if( !noinf && match == NIL(ICELL) ) {
527 28 : *nnmp = add_iset( *nnmp, ic, meta, pdfa, nidirroot, ic->ic_dmax,
528 28 : 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 4814 : if( ipush ) Pop_dir(FALSE);
536 4814 : if( iprqh.ht_name ) FREE(iprqh.ht_name);
537 : }
538 : }
539 :
540 4754 : DB_RETURN(match);
541 : }
542 :
543 :
544 : static char *
545 4682 : buildname( tg, meta, per )/*
546 : ============================
547 : Replace '%' with per in meta. Expand the result and return it. */
548 : char *tg; /* Current target name. */
549 : char *meta;
550 : char *per;
551 : {
552 : char *name;
553 :
554 4682 : name = Apply_edit( meta, "%", per, FALSE, FALSE );
555 : /* Handle infered dynamic prerequisites. */
556 4682 : 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 0 : if( *DmStrPbrk( tg, "${}" ) != '\0' )
563 0 : Fatal("$@ [%s] not fully expanded!", tg);
564 0 : m_at = Def_macro( "@", DO_WINPATH(tg), M_MULTI|M_EXPANDED );
565 0 : tmp = Expand( name );
566 :
567 0 : if( m_at->ht_value != NIL(char) ) {
568 0 : FREE( m_at->ht_value );
569 0 : m_at->ht_value = NIL(char);
570 : }
571 :
572 : /* Free name if Apply_edit() did something. */
573 0 : if( name != meta ) FREE( name );
574 0 : name = tmp;
575 : }
576 4682 : else if( name == meta )
577 44 : name = DmStrDup( name );
578 :
579 4682 : return(name);
580 : }
581 :
582 :
583 : static DFALINKPTR
584 34255 : dfa_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. */
593 : DFALINKPTR pdfa;
594 : register 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 39009 : for(; pdfa != NIL(DFALINK) && stack != NIL(DFASET); stack = stack->df_next) {
605 4754 : int subset = TRUE;
606 :
607 9508 : for( element=stack->df_set; subset && element != NIL(DFALINK);
608 0 : element=element->dl_next ) {
609 : register DFALINKPTR subel;
610 :
611 0 : for( subel = pdfa;
612 0 : subel != NIL(DFALINK) && (subel->dl_meta != element->dl_meta);
613 0 : 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 0 : if( (subset = (subel != NIL(DFALINK))) != 0 )
619 0 : element->dl_member = subel;
620 : }
621 :
622 4754 : if( subset )
623 9508 : for( element=stack->df_set; element != NIL(DFALINK);
624 0 : element=element->dl_next ) {
625 0 : DFALINKPTR mem = element->dl_member;
626 0 : int npr = element->dl_prep + 1;
627 :
628 0 : if( npr > Prep )
629 0 : mem->dl_delete++;
630 : else
631 0 : mem->dl_prep = npr;
632 : }
633 : }
634 :
635 39015 : for( element = pdfa; element != NIL(DFALINK); element = nelement ) {
636 4760 : nelement = element->dl_next;
637 :
638 4760 : 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 0 : if( element == pdfa )
643 0 : pdfa = element->dl_next;
644 : else
645 0 : element->dl_prev->dl_next = element->dl_next;
646 :
647 0 : if( element->dl_next != NIL(DFALINK) )
648 0 : element->dl_next->dl_prev = element->dl_prev;
649 :
650 : DB_PRINT("inf", ("deleting dfa [%s]", element->dl_meta->CE_NAME));
651 0 : FREE( element->dl_per );
652 0 : FREE( element );
653 : }
654 : }
655 :
656 34255 : DB_RETURN( pdfa );
657 : }
658 :
659 :
660 :
661 : static void
662 39037 : free_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. */
666 : DFALINKPTR chain;
667 : {
668 : register DFALINKPTR tl;
669 :
670 : DB_ENTER( "free_dfas" );
671 :
672 43797 : for( tl=chain; tl != NIL(DFALINK); chain = tl ) {
673 4760 : tl = tl->dl_next;
674 :
675 : DB_PRINT( "inf", ("Freeing DFA [%s], %% = [%s]", chain->dl_meta->CE_NAME,
676 : chain->dl_per) );
677 :
678 4760 : if( chain->dl_per != NIL(char) ) FREE( chain->dl_per );
679 4760 : FREE( chain );
680 : }
681 :
682 39037 : DB_VOID_RETURN;
683 : }
684 :
685 :
686 : static int
687 48301 : count_dots( name )/*
688 : =====================*/
689 : char *name;
690 : {
691 : register char *p;
692 48301 : register int i = 0;
693 :
694 48301 : for( p = name; *p; p++ ) if(*p == '.') i++;
695 :
696 48301 : return( i );
697 : }
698 :
699 :
700 : static ICELLPTR _icells = NIL(ICELL);
701 : #ifdef DBUG
702 : static int _icell_cost = 0;
703 : #endif
704 :
705 : static ICELLPTR
706 39037 : add_iset( iset, parent, meta, dfa, setdirroot, dmax, noinf, name, dir, exists)
707 : ICELLPTR iset;
708 : ICELLPTR parent;
709 : CELLPTR meta;
710 : DFALINKPTR dfa;
711 : CELLPTR setdirroot;
712 : int dmax;
713 : int noinf;
714 : char *name;
715 : char *dir;
716 : int exists;
717 : {
718 : ICELLPTR icell;
719 :
720 : DB_ENTER("add_iset");
721 39037 : TALLOC(icell, 1, ICELL);
722 :
723 : DB_EXECUTE("inf", _icell_cost+=(sizeof(ICELL)+strlen(dir?dir:"")+strlen(name?name:"")+2););
724 :
725 39037 : icell->ic_meta = meta;
726 39037 : icell->ic_dfa = dfa;
727 39037 : icell->ic_setdirroot = setdirroot;
728 :
729 39037 : if( parent ) icell->ic_dfastack.df_next = &parent->ic_dfastack;
730 :
731 39037 : icell->ic_dmax = dmax;
732 39037 : icell->ic_dir = DmStrDup(dir);
733 39037 : icell->ic_name = DmStrDup(name);
734 39037 : icell->ic_parent = parent;
735 39037 : icell->ic_next = iset;
736 39037 : icell->ic_flag = noinf;
737 39037 : icell->ic_exists = exists;
738 :
739 39037 : icell->ic_link = _icells;
740 39037 : _icells = icell;
741 :
742 39037 : DB_RETURN(icell);
743 : }
744 :
745 :
746 : static void
747 34255 : free_icells()
748 : {
749 : register ICELLPTR ic;
750 :
751 : DB_ENTER("free_icells");
752 :
753 73292 : for( ; _icells; _icells = ic ) {
754 39037 : ic = _icells->ic_link;
755 :
756 39037 : free_dfas(_icells->ic_dfastack.df_set);
757 39037 : if( _icells->ic_dir ) FREE(_icells->ic_dir);
758 39037 : if( _icells->ic_name) FREE(_icells->ic_name);
759 39037 : FREE(_icells);
760 : }
761 :
762 : DB_PRINT("inf",("Used %d memory for icells",_icell_cost));
763 : DB_EXECUTE("inf", _icell_cost=0; );
764 :
765 34255 : DB_VOID_RETURN;
766 : }
767 :
768 :
769 : static ICELLPTR
770 39009 : union_iset( iset, uset )
771 : ICELLPTR iset;
772 : ICELLPTR uset;
773 : {
774 : register ICELLPTR ic;
775 :
776 39009 : if( iset == NIL(ICELL) ) return(uset);
777 :
778 0 : for( ic=iset; ic->ic_next != NIL(ICELL); ic=ic->ic_next );
779 0 : ic->ic_next = uset;
780 :
781 0 : return(iset);
782 : }
783 :
784 :
785 : static char *
786 0 : dump_inf_chain( ip, flag, print )/*
787 : ===================================
788 : Return string with infered prerequisites.
789 : flag == TRUE adds the top of the chain.
790 : print == TRUE prints to screen with number "print" and returns NULL. */
791 : ICELLPTR ip;
792 : int flag;
793 : int print;
794 : {
795 : char *tmp;
796 :
797 0 : if( ip == NIL(ICELL) ) return(NIL(char));
798 :
799 : /* ip->ic_parent is the target to be build after ip. */
800 0 : tmp = dump_inf_chain(ip->ic_parent, FALSE, FALSE);
801 :
802 0 : if( ip->ic_meta ) {
803 0 : tmp = DmStrJoin(tmp, "(", -1, TRUE);
804 0 : tmp = DmStrJoin(tmp, ip->ic_meta->CE_NAME, -1, TRUE);
805 :
806 0 : if( ip->ic_dir && !*ip->ic_dir ) {
807 0 : tmp = DmStrJoin(tmp, "[", -1, TRUE);
808 0 : if( strncmp(Makedir,ip->ic_dir, strlen(Makedir)) )
809 0 : tmp = DmStrJoin(tmp, ip->ic_dir, -1, TRUE);
810 : else
811 0 : tmp = DmStrJoin(tmp, ip->ic_dir+strlen(Makedir)+1, -1, TRUE);
812 0 : tmp = DmStrJoin(tmp, "]", -1, TRUE);
813 : }
814 0 : tmp = DmStrJoin(tmp, (ip->ic_name)?") -->":")", -1, TRUE);
815 : }
816 :
817 0 : if( ip->ic_name ) tmp = DmStrApp( tmp, ip->ic_name );
818 :
819 0 : if( flag && ip->ic_meta->ce_prq) {
820 0 : tmp = DmStrJoin(tmp, "(", -1, TRUE);
821 0 : tmp = DmStrJoin(tmp, ip->ic_meta->ce_prq->cl_prq->CE_NAME, -1, TRUE);
822 0 : tmp = DmStrJoin(tmp, ")", -1, TRUE);
823 : }
824 :
825 0 : if( print ) {
826 0 : fprintf( stderr, "%s: %2d. %s\n", Pname, print, tmp );
827 0 : FREE(tmp);
828 0 : tmp = NIL(char);
829 : }
830 :
831 0 : return(tmp);
832 : }
833 :
834 :
835 : #ifdef DBUG
836 : static void
837 : _dump_dfa_stack(dfas, dfa_stack)
838 : DFALINKPTR dfas;
839 : DFASETPTR dfa_stack;
840 : {
841 : register DFALINKPTR pdfa;
842 : char *tmp = NIL(char);
843 : DFASETPTR ds;
844 :
845 : for( pdfa = dfas; pdfa != NIL(DFALINK); pdfa = pdfa->dl_next )
846 : tmp = DmStrApp( tmp, pdfa->dl_meta->CE_NAME );
847 :
848 : tmp = DmStrApp( tmp, ":: {" );
849 : for( ds = dfa_stack; ds != NIL(DFASET); ds = ds->df_next ) {
850 : tmp = DmStrApp( tmp, "[" );
851 : for( pdfa = ds->df_set; pdfa != NIL(DFALINK); pdfa = pdfa->dl_next )
852 : tmp = DmStrApp( tmp, pdfa->dl_meta->CE_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);
859 : }
860 :
861 :
862 : static void
863 : _dump_iset( name, iset )
864 : char *name;
865 : ICELLPTR iset;
866 : {
867 : int cell = 0;
868 :
869 : printf( "**** ISET for %s\n", name );
870 : for( ; iset != NIL(ICELL); 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_NAME,
874 : iset->ic_meta->ce_prq ?
875 : iset->ic_meta->ce_prq->cl_prq->CE_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_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_NAME,
897 : iset->ic_parent->ic_meta->ce_prq ?
898 : iset->ic_parent->ic_meta->ce_prq->cl_prq->CE_NAME :
899 : "(nil)" );
900 : else
901 : printf( "(nil)\n" );
902 : else
903 : printf( "(nil)\n" );
904 : }
905 : printf( "==================================\n" );
906 : }
907 : #endif
|
