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