dmake/percent.c

   1 /* RCS  $Id: percent.c,v 1.1.1.1 2000-09-22 15:33:25 hr Exp $
   2 --
   3 -- SYNOPSIS
   4 --      Handle building or %-rule meta-target nfa.
   5 --
   6 -- DESCRIPTION
   7 --      Builds the NFA used by dmake to match targets against %-meta
   8 --      rule constructs.  The NFA is built as a set of DFA's.
   9 --
  10 -- AUTHOR
  11 --      Dennis Vadura, dvadura@dmake.wticorp.com
  12 --
  13 -- WWW
  14 --      http://dmake.wticorp.com/
  15 --
  16 -- COPYRIGHT
  17 --      Copyright (c) 1996,1997 by WTI Corp.  All rights reserved.
  18 --
  19 --      This program is NOT free software; you can redistribute it and/or
  20 --      modify it under the terms of the Software License Agreement Provided
  21 --      in the file <distribution-root>/readme/license.txt.
  22 --
  23 -- LOG
  24 --      Use cvs log to obtain detailed change logs.
  25 */
  26
  27 #include "extern.h"
  28
  29 static DFAPTR _build_dfa ANSI((char *));
  30 static char   _shift_dfa ANSI((DFAPTR, char *));
  31
  32
  33 #define NO_ACTION       0
  34 #define START_PERCENT   1
  35 #define END_PERCENT     2
  36 #define ACCEPT          4
  37 #define FAIL           -1
  38
  39 static  NFAPTR _nfa = NIL( NFA );
  40
  41
  42 PUBLIC DFALINKPTR
  43 Match_dfa( buf )/*
  44 ==================
  45    This routines runs all DFA's in parrallel and selects the one that best
  46    matches the string.  If no match then it returns NIL( DFA ) */
  47 char *buf;
  48 {
  49    register NFAPTR nfa;
  50    int             adv;
  51    DFALINKPTR      dfa_list = NIL(DFALINK);
  52
  53    DB_ENTER( "Match_dfa" );
  54    DB_PRINT( "dfa", ("Matching %s", buf) );
  55
  56    /* Run each of the DFA's on the input string in parallel, we terminate
  57     * when all DFA's have either failed or ACCEPTED, if more than one DFA
  58     * accepts we build a list of all accepting DFA's sorted on states with
  59     * those matching in a higher numbered state heading the list. */
  60
  61    do {
  62       adv = FALSE;
  63
  64       for( nfa = _nfa; nfa != NIL( NFA ); nfa = nfa->next )
  65          if( nfa->status != (char) FAIL && nfa->status != (char) ACCEPT ) {
  66             adv++;
  67             nfa->status = _shift_dfa( nfa->dfa, buf );
  68
  69             /* Construct the list of matching DFA's */
  70             if( nfa->status == (char) ACCEPT ) {
  71                DFALINKPTR dl;
  72
  73                TALLOC( dl, 1, DFALINK );
  74                dl->dl_meta  = nfa->dfa->node;
  75                dl->dl_per   = DmSubStr( nfa->dfa->pstart, nfa->dfa->pend );
  76                dl->dl_state = nfa->dfa->states - nfa->dfa->c_state;
  77
  78                if( dfa_list == NIL(DFALINK) )
  79                   dfa_list = dl;
  80                else {
  81                   DFALINKPTR tdli = dfa_list;
  82                   DFALINKPTR tdlp = NIL(DFALINK);
  83
  84                   for( ; tdli != NIL(DFALINK); tdli = tdli->dl_next ) {
  85                      if( dl->dl_state >= tdli->dl_state )
  86                         break;
  87                      tdlp = tdli;
  88                   }
  89
  90                   if( tdli != NIL(DFALINK) ) {
  91                      tdli->dl_prev = dl;
  92                      dl->dl_next   = tdli;
  93                   }
  94
  95                   if( tdlp != NIL(DFALINK) ) {
  96                      tdlp->dl_next = dl;
  97                      dl->dl_prev   = tdlp;
  98                   }
  99                   else
 100                      dfa_list = dl;
 101                }
 102
 103                DB_PRINT( "dfa", ("Matched [%s]", dl->dl_meta->CE_NAME) );
 104             }
 105          }
 106
 107       buf++;
 108    }
 109    while ( adv );
 110
 111    for( nfa = _nfa; nfa != NIL( NFA ); nfa = nfa->next ) {
 112       nfa->status = 0;
 113       nfa->dfa->c_state = nfa->dfa->states;
 114    }
 115
 116    DB_RETURN( dfa_list );
 117 }
 118
 119
 120 PUBLIC void
 121 Check_circle_dfa()/*
 122 ====================
 123    This function is called to test for circularities in the DFA lists
 124    constructed from %-meta targets. */
 125 {
 126    register NFAPTR nfa;
 127
 128    for( nfa = _nfa; nfa != NIL(NFA); nfa = nfa->next )
 129       if( Test_circle( nfa->dfa->node, FALSE ) )
 130          Fatal( "Detected circular dependency in inference graph at [%s]",
 131                 nfa->dfa->node->CE_NAME );
 132 }
 133
 134
 135 PUBLIC void
 136 Add_nfa( name )/*
 137 =================
 138    Given name, build a DFA and add it to the NFA.  The NFA is maintained as
 139    a singly linked list of DFA's. */
 140 char *name;
 141 {
 142    NFAPTR nfa;
 143
 144    TALLOC(nfa, 1, NFA);
 145    nfa->dfa = _build_dfa(name);
 146
 147    if( _nfa != NIL(NFA) ) nfa->next = _nfa;
 148
 149    _nfa = nfa;
 150 }
 151
 152
 153 static DFAPTR
 154 _build_dfa( name )/*
 155 ====================
 156    Construct a dfa for the passed in cell name.  The routine returns a struct
 157    that represents a finite state machine that can recognize a regular
 158    expression with exactly one '%' sign in it.  The '%' symbol is used as a
 159    wildcard character that will match anything except the character that
 160    immediately follows it or NUL.
 161
 162    The Construction of DFA's is well known and can be found in Hopcroft and
 163    Ullman or any other book discussing formal language theory.
 164    A more practical treatise can be found in Compilers, Aho, Sethi and Ullman.
 165 */
 166 char *name;
 167 {
 168    DFAPTR   dfa;
 169    int      nstates;
 170    register STATEPTR sp;
 171    STATEPTR per_state = NIL(STATE);
 172    int      pcount=0;
 173    int      end_percent=FALSE;
 174
 175    nstates = strlen(name)+2;
 176
 177    /* Allocate a DFA node and the right number of states. */
 178    TALLOC(dfa, 1, DFA);
 179    TALLOC(sp=dfa->c_state=dfa->states, nstates, STATE);
 180    dfa->node = Def_cell( name );
 181
 182    /* Now construct the state table for the DFA */
 183    do {
 184       if( *name == '%' ) {
 185          if( pcount++ > 0 )
 186             Error( "Only one %% allowed within a %%-meta target" );
 187
 188          sp->symbol   = 0;
 189          sp->action   = START_PERCENT;
 190          sp->no_match = sp->match = per_state = sp+1;
 191          end_percent  = TRUE;
 192       }
 193       else {
 194          sp->symbol   = *name;
 195          sp->no_match = per_state;
 196
 197          if( *name == '\0' ) {
 198             sp->action = ACCEPT;
 199             sp->match  = dfa->states;
 200          }
 201          else {
 202             sp->action = NO_ACTION;
 203             sp->match  = sp+1;
 204          }
 205
 206          if( end_percent ) {
 207             sp->action |= END_PERCENT;
 208             end_percent = FALSE;
 209          }
 210       }
 211
 212       sp++;
 213    }
 214    while( *name++ );
 215
 216    return(dfa);
 217 }
 218
 219
 220 static char
 221 _shift_dfa( dfa, data )/*
 222 =========================
 223    Take a given dfa and advance it based on the current state, the shift
 224    action in that state, and the current data value. */
 225 DFAPTR dfa;
 226 char   *data;
 227 {
 228    register STATEPTR sp = dfa->c_state;
 229    char c = *data;
 230
 231    /* Check if it is a START_PERCENT action if so then we need to save
 232     * a pointer to the start of the string and advance to the next state. */
 233    if( sp->action & START_PERCENT ) {
 234       dfa->pstart = data;
 235       sp++;
 236    }
 237
 238    /* Now check if the current char matches the character expected in the
 239     * current state.  If it does then perform the specified action, otherwise
 240     * either shift it or fail.  We fail if the next state on no-match is
 241     * NIL. */
 242    if( sp->symbol == c ) {
 243       if( sp->action & END_PERCENT ) dfa->pend = data;
 244       if( sp->action & ACCEPT ) return(ACCEPT);
 245       dfa->c_state = sp->match;
 246    }
 247    else if( (dfa->c_state = sp->no_match) == NIL(STATE) || !c )
 248       return((unsigned char) FAIL);
 249
 250    return(NO_ACTION);
 251 }