/* RCS $Id: percent.c,v 1.1.1.1 2000-09-22 15:33:25 hr Exp $ -- -- SYNOPSIS -- Handle building or %-rule meta-target nfa. -- -- DESCRIPTION -- Builds the NFA used by dmake to match targets against %-meta -- rule constructs. The NFA is built as a set of DFA's. -- -- AUTHOR -- Dennis Vadura, dvadura@dmake.wticorp.com -- -- WWW -- http://dmake.wticorp.com/ -- -- COPYRIGHT -- Copyright (c) 1996,1997 by WTI Corp. All rights reserved. -- -- This program is NOT free software; you can redistribute it and/or -- modify it under the terms of the Software License Agreement Provided -- in the file /readme/license.txt. -- -- LOG -- Use cvs log to obtain detailed change logs. */ #include "extern.h" static DFAPTR _build_dfa ANSI((char *)); static char _shift_dfa ANSI((DFAPTR, char *)); #define NO_ACTION 0 #define START_PERCENT 1 #define END_PERCENT 2 #define ACCEPT 4 #define FAIL -1 static NFAPTR _nfa = NIL( NFA ); PUBLIC DFALINKPTR Match_dfa( buf )/* ================== This routines runs all DFA's in parrallel and selects the one that best matches the string. If no match then it returns NIL( DFA ) */ char *buf; { register NFAPTR nfa; int adv; DFALINKPTR dfa_list = NIL(DFALINK); DB_ENTER( "Match_dfa" ); DB_PRINT( "dfa", ("Matching %s", buf) ); /* Run each of the DFA's on the input string in parallel, we terminate * when all DFA's have either failed or ACCEPTED, if more than one DFA * accepts we build a list of all accepting DFA's sorted on states with * those matching in a higher numbered state heading the list. */ do { adv = FALSE; for( nfa = _nfa; nfa != NIL( NFA ); nfa = nfa->next ) if( nfa->status != (char) FAIL && nfa->status != (char) ACCEPT ) { adv++; nfa->status = _shift_dfa( nfa->dfa, buf ); /* Construct the list of matching DFA's */ if( nfa->status == (char) ACCEPT ) { DFALINKPTR dl; TALLOC( dl, 1, DFALINK ); dl->dl_meta = nfa->dfa->node; dl->dl_per = DmSubStr( nfa->dfa->pstart, nfa->dfa->pend ); dl->dl_state = nfa->dfa->states - nfa->dfa->c_state; if( dfa_list == NIL(DFALINK) ) dfa_list = dl; else { DFALINKPTR tdli = dfa_list; DFALINKPTR tdlp = NIL(DFALINK); for( ; tdli != NIL(DFALINK); tdli = tdli->dl_next ) { if( dl->dl_state >= tdli->dl_state ) break; tdlp = tdli; } if( tdli != NIL(DFALINK) ) { tdli->dl_prev = dl; dl->dl_next = tdli; } if( tdlp != NIL(DFALINK) ) { tdlp->dl_next = dl; dl->dl_prev = tdlp; } else dfa_list = dl; } DB_PRINT( "dfa", ("Matched [%s]", dl->dl_meta->CE_NAME) ); } } buf++; } while ( adv ); for( nfa = _nfa; nfa != NIL( NFA ); nfa = nfa->next ) { nfa->status = 0; nfa->dfa->c_state = nfa->dfa->states; } DB_RETURN( dfa_list ); } PUBLIC void Check_circle_dfa()/* ==================== This function is called to test for circularities in the DFA lists constructed from %-meta targets. */ { register NFAPTR nfa; for( nfa = _nfa; nfa != NIL(NFA); nfa = nfa->next ) if( Test_circle( nfa->dfa->node, FALSE ) ) Fatal( "Detected circular dependency in inference graph at [%s]", nfa->dfa->node->CE_NAME ); } PUBLIC void Add_nfa( name )/* ================= Given name, build a DFA and add it to the NFA. The NFA is maintained as a singly linked list of DFA's. */ char *name; { NFAPTR nfa; TALLOC(nfa, 1, NFA); nfa->dfa = _build_dfa(name); if( _nfa != NIL(NFA) ) nfa->next = _nfa; _nfa = nfa; } static DFAPTR _build_dfa( name )/* ==================== Construct a dfa for the passed in cell name. The routine returns a struct that represents a finite state machine that can recognize a regular expression with exactly one '%' sign in it. The '%' symbol is used as a wildcard character that will match anything except the character that immediately follows it or NUL. The Construction of DFA's is well known and can be found in Hopcroft and Ullman or any other book discussing formal language theory. A more practical treatise can be found in Compilers, Aho, Sethi and Ullman. */ char *name; { DFAPTR dfa; int nstates; register STATEPTR sp; STATEPTR per_state = NIL(STATE); int pcount=0; int end_percent=FALSE; nstates = strlen(name)+2; /* Allocate a DFA node and the right number of states. */ TALLOC(dfa, 1, DFA); TALLOC(sp=dfa->c_state=dfa->states, nstates, STATE); dfa->node = Def_cell( name ); /* Now construct the state table for the DFA */ do { if( *name == '%' ) { if( pcount++ > 0 ) Error( "Only one %% allowed within a %%-meta target" ); sp->symbol = 0; sp->action = START_PERCENT; sp->no_match = sp->match = per_state = sp+1; end_percent = TRUE; } else { sp->symbol = *name; sp->no_match = per_state; if( *name == '\0' ) { sp->action = ACCEPT; sp->match = dfa->states; } else { sp->action = NO_ACTION; sp->match = sp+1; } if( end_percent ) { sp->action |= END_PERCENT; end_percent = FALSE; } } sp++; } while( *name++ ); return(dfa); } static char _shift_dfa( dfa, data )/* ========================= Take a given dfa and advance it based on the current state, the shift action in that state, and the current data value. */ DFAPTR dfa; char *data; { register STATEPTR sp = dfa->c_state; char c = *data; /* Check if it is a START_PERCENT action if so then we need to save * a pointer to the start of the string and advance to the next state. */ if( sp->action & START_PERCENT ) { dfa->pstart = data; sp++; } /* Now check if the current char matches the character expected in the * current state. If it does then perform the specified action, otherwise * either shift it or fail. We fail if the next state on no-match is * NIL. */ if( sp->symbol == c ) { if( sp->action & END_PERCENT ) dfa->pend = data; if( sp->action & ACCEPT ) return(ACCEPT); dfa->c_state = sp->match; } else if( (dfa->c_state = sp->no_match) == NIL(STATE) || !c ) return((unsigned char) FAIL); return(NO_ACTION); }