dmake/infer.c

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