fdo#61256 - the Get.*Export methods also create and register styles
[LibreOffice.git] / dmake / percent.c
blob8ecac4ce764d48531bcc62807b8cfced94e7c7e7
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
13 -- WWW
14 -- http://dmake.wticorp.com/
16 -- COPYRIGHT
17 -- Copyright (c) 1996,1997 by WTI Corp. All rights reserved.
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.
23 -- LOG
24 -- Use cvs log to obtain detailed change logs.
27 #include "extern.h"
29 static DFAPTR _build_dfa ANSI((char *));
30 static char _shift_dfa ANSI((DFAPTR, char *));
33 #define NO_ACTION 0
34 #define START_PERCENT 1
35 #define END_PERCENT 2
36 #define ACCEPT 4
37 #define FAIL -1
39 static NFAPTR _nfa = NIL( NFA );
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;
49 register NFAPTR nfa;
50 int adv;
51 DFALINKPTR dfa_list = NIL(DFALINK);
53 DB_ENTER( "Match_dfa" );
54 DB_PRINT( "dfa", ("Matching %s", buf) );
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. */
61 do {
62 adv = FALSE;
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 );
69 /* Construct the list of matching DFA's */
70 if( nfa->status == (char) ACCEPT ) {
71 DFALINKPTR dl;
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;
78 if( dfa_list == NIL(DFALINK) )
79 dfa_list = dl;
80 else {
81 DFALINKPTR tdli = dfa_list;
82 DFALINKPTR tdlp = NIL(DFALINK);
84 for( ; tdli != NIL(DFALINK); tdli = tdli->dl_next ) {
85 if( dl->dl_state >= tdli->dl_state )
86 break;
87 tdlp = tdli;
90 if( tdli != NIL(DFALINK) ) {
91 tdli->dl_prev = dl;
92 dl->dl_next = tdli;
95 if( tdlp != NIL(DFALINK) ) {
96 tdlp->dl_next = dl;
97 dl->dl_prev = tdlp;
99 else
100 dfa_list = dl;
103 DB_PRINT( "dfa", ("Matched [%s]", dl->dl_meta->CE_NAME) );
107 buf++;
109 while ( adv );
111 for( nfa = _nfa; nfa != NIL( NFA ); nfa = nfa->next ) {
112 nfa->status = 0;
113 nfa->dfa->c_state = nfa->dfa->states;
116 DB_RETURN( dfa_list );
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. */
126 register NFAPTR nfa;
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 );
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;
142 NFAPTR nfa;
144 TALLOC(nfa, 1, NFA);
145 nfa->dfa = _build_dfa(name);
147 if( _nfa != NIL(NFA) ) nfa->next = _nfa;
149 _nfa = nfa;
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.
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.
166 char *name;
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;
175 nstates = strlen(name)+2;
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 );
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" );
188 sp->symbol = 0;
189 sp->action = START_PERCENT;
190 sp->no_match = sp->match = per_state = sp+1;
191 end_percent = TRUE;
193 else {
194 sp->symbol = *name;
195 sp->no_match = per_state;
197 if( *name == '\0' ) {
198 sp->action = ACCEPT;
199 sp->match = dfa->states;
201 else {
202 sp->action = NO_ACTION;
203 sp->match = sp+1;
206 if( end_percent ) {
207 sp->action |= END_PERCENT;
208 end_percent = FALSE;
212 sp++;
214 while( *name++ );
216 return(dfa);
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;
228 register STATEPTR sp = dfa->c_state;
229 char c = *data;
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++;
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;
247 else if( (dfa->c_state = sp->no_match) == NIL(STATE) || !c )
248 return((unsigned char) FAIL);
250 return(NO_ACTION);