Generally use NULL instead of explicitly casting 0 to some pointer type (part2).
[dragonfly.git] / usr.bin / lex / nfa.c
1 /* nfa - NFA construction routines */
2
3 /*-
4  * Copyright (c) 1990 The Regents of the University of California.
5  * All rights reserved.
6  *
7  * This code is derived from software contributed to Berkeley by
8  * Vern Paxson.
9  * 
10  * The United States Government has rights in this work pursuant
11  * to contract no. DE-AC03-76SF00098 between the United States
12  * Department of Energy and the University of California.
13  *
14  * Redistribution and use in source and binary forms are permitted provided
15  * that: (1) source distributions retain this entire copyright notice and
16  * comment, and (2) distributions including binaries display the following
17  * acknowledgement:  ``This product includes software developed by the
18  * University of California, Berkeley and its contributors'' in the
19  * documentation or other materials provided with the distribution and in
20  * all advertising materials mentioning features or use of this software.
21  * Neither the name of the University nor the names of its contributors may
22  * be used to endorse or promote products derived from this software without
23  * specific prior written permission.
24  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
25  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
26  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
27  */
28
29 /* $Header: /home/daffy/u0/vern/flex/RCS/nfa.c,v 2.17 95/03/04 16:11:42 vern Exp $ */
30 /* $FreeBSD: src/usr.bin/lex/nfa.c,v 1.5 1999/10/27 07:56:46 obrien Exp $ */
31 /* $DragonFly: src/usr.bin/lex/nfa.c,v 1.4 2005/08/04 17:31:22 drhodus Exp $ */
32
33 #include "flexdef.h"
34
35
36 /* declare functions that have forward references */
37
38 int dupmachine PROTO((int));
39 void mkxtion PROTO((int, int));
40
41
42 /* add_accept - add an accepting state to a machine
43  *
44  * accepting_number becomes mach's accepting number.
45  */
46
47 void add_accept(int mach, int accepting_number)
48         {
49         /* Hang the accepting number off an epsilon state.  if it is associated
50          * with a state that has a non-epsilon out-transition, then the state
51          * will accept BEFORE it makes that transition, i.e., one character
52          * too soon.
53          */
54
55         if ( transchar[finalst[mach]] == SYM_EPSILON )
56                 accptnum[finalst[mach]] = accepting_number;
57
58         else
59                 {
60                 int astate = mkstate( SYM_EPSILON );
61                 accptnum[astate] = accepting_number;
62                 (void) link_machines( mach, astate );
63                 }
64         }
65
66
67 /* copysingl - make a given number of copies of a singleton machine
68  *
69  * synopsis
70  *
71  *   newsng = copysingl( singl, num );
72  *
73  *     newsng - a new singleton composed of num copies of singl
74  *     singl  - a singleton machine
75  *     num    - the number of copies of singl to be present in newsng
76  */
77
78 int copysingl(int singl, int num)
79         {
80         int copy, i;
81
82         copy = mkstate( SYM_EPSILON );
83
84         for ( i = 1; i <= num; ++i )
85                 copy = link_machines( copy, dupmachine( singl ) );
86
87         return copy;
88         }
89
90
91 /* dumpnfa - debugging routine to write out an nfa */
92
93 void dumpnfa(int state1)
94         {
95         int sym, tsp1, tsp2, anum, ns;
96
97         fprintf( stderr,
98         _( "\n\n********** beginning dump of nfa with start state %d\n" ),
99                 state1 );
100
101         /* We probably should loop starting at firstst[state1] and going to
102          * lastst[state1], but they're not maintained properly when we "or"
103          * all of the rules together.  So we use our knowledge that the machine
104          * starts at state 1 and ends at lastnfa.
105          */
106
107         /* for ( ns = firstst[state1]; ns <= lastst[state1]; ++ns ) */
108         for ( ns = 1; ns <= lastnfa; ++ns )
109                 {
110                 fprintf( stderr, _( "state # %4d\t" ), ns );
111
112                 sym = transchar[ns];
113                 tsp1 = trans1[ns];
114                 tsp2 = trans2[ns];
115                 anum = accptnum[ns];
116
117                 fprintf( stderr, "%3d:  %4d, %4d", sym, tsp1, tsp2 );
118
119                 if ( anum != NIL )
120                         fprintf( stderr, "  [%d]", anum );
121
122                 fprintf( stderr, "\n" );
123                 }
124
125         fprintf( stderr, _( "********** end of dump\n" ) );
126         }
127
128
129 /* dupmachine - make a duplicate of a given machine
130  *
131  * synopsis
132  *
133  *   copy = dupmachine( mach );
134  *
135  *     copy - holds duplicate of mach
136  *     mach - machine to be duplicated
137  *
138  * note that the copy of mach is NOT an exact duplicate; rather, all the
139  * transition states values are adjusted so that the copy is self-contained,
140  * as the original should have been.
141  *
142  * also note that the original MUST be contiguous, with its low and high
143  * states accessible by the arrays firstst and lastst
144  */
145
146 int dupmachine(int mach)
147         {
148         int i, init, state_offset;
149         int state = 0;
150         int last = lastst[mach];
151
152         for ( i = firstst[mach]; i <= last; ++i )
153                 {
154                 state = mkstate( transchar[i] );
155
156                 if ( trans1[i] != NO_TRANSITION )
157                         {
158                         mkxtion( finalst[state], trans1[i] + state - i );
159
160                         if ( transchar[i] == SYM_EPSILON &&
161                              trans2[i] != NO_TRANSITION )
162                                 mkxtion( finalst[state],
163                                         trans2[i] + state - i );
164                         }
165
166                 accptnum[state] = accptnum[i];
167                 }
168
169         if ( state == 0 )
170                 flexfatal( _( "empty machine in dupmachine()" ) );
171
172         state_offset = state - i + 1;
173
174         init = mach + state_offset;
175         firstst[init] = firstst[mach] + state_offset;
176         finalst[init] = finalst[mach] + state_offset;
177         lastst[init] = lastst[mach] + state_offset;
178
179         return init;
180         }
181
182
183 /* finish_rule - finish up the processing for a rule
184  *
185  * An accepting number is added to the given machine.  If variable_trail_rule
186  * is true then the rule has trailing context and both the head and trail
187  * are variable size.  Otherwise if headcnt or trailcnt is non-zero then
188  * the machine recognizes a pattern with trailing context and headcnt is
189  * the number of characters in the matched part of the pattern, or zero
190  * if the matched part has variable length.  trailcnt is the number of
191  * trailing context characters in the pattern, or zero if the trailing
192  * context has variable length.
193  */
194
195 void finish_rule(int mach, int variable_trail_rule, int headcnt, int trailcnt)
196         {
197         char action_text[MAXLINE];
198
199         add_accept( mach, num_rules );
200
201         /* We did this in new_rule(), but it often gets the wrong
202          * number because we do it before we start parsing the current rule.
203          */
204         rule_linenum[num_rules] = linenum;
205
206         /* If this is a continued action, then the line-number has already
207          * been updated, giving us the wrong number.
208          */
209         if ( continued_action )
210                 --rule_linenum[num_rules];
211
212         sprintf( action_text, "case %d:\n", num_rules );
213         add_action( action_text );
214
215         if ( variable_trail_rule )
216                 {
217                 rule_type[num_rules] = RULE_VARIABLE;
218
219                 if ( performance_report > 0 )
220                         fprintf( stderr,
221                         _( "Variable trailing context rule at line %d\n" ),
222                                 rule_linenum[num_rules] );
223
224                 variable_trailing_context_rules = true;
225                 }
226
227         else
228                 {
229                 rule_type[num_rules] = RULE_NORMAL;
230
231                 if ( headcnt > 0 || trailcnt > 0 )
232                         {
233                         /* Do trailing context magic to not match the trailing
234                          * characters.
235                          */
236                         char *scanner_cp = "yy_c_buf_p = yy_cp";
237                         char *scanner_bp = "yy_bp";
238
239                         add_action(
240         "*yy_cp = yy_hold_char; /* undo effects of setting up yytext */\n" );
241
242                         if ( headcnt > 0 )
243                                 {
244                                 sprintf( action_text, "%s = %s + %d;\n",
245                                 scanner_cp, scanner_bp, headcnt );
246                                 add_action( action_text );
247                                 }
248
249                         else
250                                 {
251                                 sprintf( action_text, "%s -= %d;\n",
252                                         scanner_cp, trailcnt );
253                                 add_action( action_text );
254                                 }
255
256                         add_action(
257                         "YY_DO_BEFORE_ACTION; /* set up yytext again */\n" );
258                         }
259                 }
260
261         /* Okay, in the action code at this point yytext and yyleng have
262          * their proper final values for this rule, so here's the point
263          * to do any user action.  But don't do it for continued actions,
264          * as that'll result in multiple YY_RULE_SETUP's.
265          */
266         if ( ! continued_action )
267                 add_action( "YY_RULE_SETUP\n" );
268
269         line_directive_out( NULL, 1 );
270         }
271
272
273 /* link_machines - connect two machines together
274  *
275  * synopsis
276  *
277  *   new = link_machines( first, last );
278  *
279  *     new    - a machine constructed by connecting first to last
280  *     first  - the machine whose successor is to be last
281  *     last   - the machine whose predecessor is to be first
282  *
283  * note: this routine concatenates the machine first with the machine
284  *  last to produce a machine new which will pattern-match first first
285  *  and then last, and will fail if either of the sub-patterns fails.
286  *  FIRST is set to new by the operation.  last is unmolested.
287  */
288
289 int link_machines(int first, int last)
290         {
291         if ( first == NIL )
292                 return last;
293
294         else if ( last == NIL )
295                 return first;
296
297         else
298                 {
299                 mkxtion( finalst[first], last );
300                 finalst[first] = finalst[last];
301                 lastst[first] = MAX( lastst[first], lastst[last] );
302                 firstst[first] = MIN( firstst[first], firstst[last] );
303
304                 return first;
305                 }
306         }
307
308
309 /* mark_beginning_as_normal - mark each "beginning" state in a machine
310  *                            as being a "normal" (i.e., not trailing context-
311  *                            associated) states
312  *
313  * The "beginning" states are the epsilon closure of the first state
314  */
315
316 void mark_beginning_as_normal(int mach)
317         {
318         switch ( state_type[mach] )
319                 {
320                 case STATE_NORMAL:
321                         /* Oh, we've already visited here. */
322                         return;
323
324                 case STATE_TRAILING_CONTEXT:
325                         state_type[mach] = STATE_NORMAL;
326
327                         if ( transchar[mach] == SYM_EPSILON )
328                                 {
329                                 if ( trans1[mach] != NO_TRANSITION )
330                                         mark_beginning_as_normal(
331                                                 trans1[mach] );
332
333                                 if ( trans2[mach] != NO_TRANSITION )
334                                         mark_beginning_as_normal(
335                                                 trans2[mach] );
336                                 }
337                         break;
338
339                 default:
340                         flexerror(
341                         _( "bad state type in mark_beginning_as_normal()" ) );
342                         break;
343                 }
344         }
345
346
347 /* mkbranch - make a machine that branches to two machines
348  *
349  * synopsis
350  *
351  *   branch = mkbranch( first, second );
352  *
353  *     branch - a machine which matches either first's pattern or second's
354  *     first, second - machines whose patterns are to be or'ed (the | operator)
355  *
356  * Note that first and second are NEITHER destroyed by the operation.  Also,
357  * the resulting machine CANNOT be used with any other "mk" operation except
358  * more mkbranch's.  Compare with mkor()
359  */
360
361 int mkbranch(int first, int second)
362         {
363         int eps;
364
365         if ( first == NO_TRANSITION )
366                 return second;
367
368         else if ( second == NO_TRANSITION )
369                 return first;
370
371         eps = mkstate( SYM_EPSILON );
372
373         mkxtion( eps, first );
374         mkxtion( eps, second );
375
376         return eps;
377         }
378
379
380 /* mkclos - convert a machine into a closure
381  *
382  * synopsis
383  *   new = mkclos( state );
384  *
385  * new - a new state which matches the closure of "state"
386  */
387
388 int mkclos(int state)
389         {
390         return mkopt( mkposcl( state ) );
391         }
392
393
394 /* mkopt - make a machine optional
395  *
396  * synopsis
397  *
398  *   new = mkopt( mach );
399  *
400  *     new  - a machine which optionally matches whatever mach matched
401  *     mach - the machine to make optional
402  *
403  * notes:
404  *     1. mach must be the last machine created
405  *     2. mach is destroyed by the call
406  */
407
408 int mkopt(int mach)
409         {
410         int eps;
411
412         if ( ! SUPER_FREE_EPSILON(finalst[mach]) )
413                 {
414                 eps = mkstate( SYM_EPSILON );
415                 mach = link_machines( mach, eps );
416                 }
417
418         /* Can't skimp on the following if FREE_EPSILON(mach) is true because
419          * some state interior to "mach" might point back to the beginning
420          * for a closure.
421          */
422         eps = mkstate( SYM_EPSILON );
423         mach = link_machines( eps, mach );
424
425         mkxtion( mach, finalst[mach] );
426
427         return mach;
428         }
429
430
431 /* mkor - make a machine that matches either one of two machines
432  *
433  * synopsis
434  *
435  *   new = mkor( first, second );
436  *
437  *     new - a machine which matches either first's pattern or second's
438  *     first, second - machines whose patterns are to be or'ed (the | operator)
439  *
440  * note that first and second are both destroyed by the operation
441  * the code is rather convoluted because an attempt is made to minimize
442  * the number of epsilon states needed
443  */
444
445 int mkor(int first, int second)
446         {
447         int eps, orend;
448
449         if ( first == NIL )
450                 return second;
451
452         else if ( second == NIL )
453                 return first;
454
455         else
456                 {
457                 /* See comment in mkopt() about why we can't use the first
458                  * state of "first" or "second" if they satisfy "FREE_EPSILON".
459                  */
460                 eps = mkstate( SYM_EPSILON );
461
462                 first = link_machines( eps, first );
463
464                 mkxtion( first, second );
465
466                 if ( SUPER_FREE_EPSILON(finalst[first]) &&
467                      accptnum[finalst[first]] == NIL )
468                         {
469                         orend = finalst[first];
470                         mkxtion( finalst[second], orend );
471                         }
472
473                 else if ( SUPER_FREE_EPSILON(finalst[second]) &&
474                           accptnum[finalst[second]] == NIL )
475                         {
476                         orend = finalst[second];
477                         mkxtion( finalst[first], orend );
478                         }
479
480                 else
481                         {
482                         eps = mkstate( SYM_EPSILON );
483
484                         first = link_machines( first, eps );
485                         orend = finalst[first];
486
487                         mkxtion( finalst[second], orend );
488                         }
489                 }
490
491         finalst[first] = orend;
492         return first;
493         }
494
495
496 /* mkposcl - convert a machine into a positive closure
497  *
498  * synopsis
499  *   new = mkposcl( state );
500  *
501  *    new - a machine matching the positive closure of "state"
502  */
503
504 int mkposcl(int state)
505         {
506         int eps;
507
508         if ( SUPER_FREE_EPSILON(finalst[state]) )
509                 {
510                 mkxtion( finalst[state], state );
511                 return state;
512                 }
513
514         else
515                 {
516                 eps = mkstate( SYM_EPSILON );
517                 mkxtion( eps, state );
518                 return link_machines( state, eps );
519                 }
520         }
521
522
523 /* mkrep - make a replicated machine
524  *
525  * synopsis
526  *   new = mkrep( mach, lb, ub );
527  *
528  *    new - a machine that matches whatever "mach" matched from "lb"
529  *          number of times to "ub" number of times
530  *
531  * note
532  *   if "ub" is INFINITY then "new" matches "lb" or more occurrences of "mach"
533  */
534
535 int mkrep(int mach, int lb, int ub)
536         {
537         int base_mach, tail, copy, i;
538
539         base_mach = copysingl( mach, lb - 1 );
540
541         if ( ub == INFINITY )
542                 {
543                 copy = dupmachine( mach );
544                 mach = link_machines( mach,
545                 link_machines( base_mach, mkclos( copy ) ) );
546                 }
547
548         else
549                 {
550                 tail = mkstate( SYM_EPSILON );
551
552                 for ( i = lb; i < ub; ++i )
553                         {
554                         copy = dupmachine( mach );
555                         tail = mkopt( link_machines( copy, tail ) );
556                         }
557
558                 mach = link_machines( mach, link_machines( base_mach, tail ) );
559                 }
560
561         return mach;
562         }
563
564
565 /* mkstate - create a state with a transition on a given symbol
566  *
567  * synopsis
568  *
569  *   state = mkstate( sym );
570  *
571  *     state - a new state matching sym
572  *     sym   - the symbol the new state is to have an out-transition on
573  *
574  * note that this routine makes new states in ascending order through the
575  * state array (and increments LASTNFA accordingly).  The routine DUPMACHINE
576  * relies on machines being made in ascending order and that they are
577  * CONTIGUOUS.  Change it and you will have to rewrite DUPMACHINE (kludge
578  * that it admittedly is)
579  */
580
581 int mkstate(int sym)
582         {
583         if ( ++lastnfa >= current_mns )
584                 {
585                 if ( (current_mns += MNS_INCREMENT) >= MAXIMUM_MNS )
586                         lerrif(
587                 _( "input rules are too complicated (>= %d NFA states)" ),
588                                 current_mns );
589
590                 ++num_reallocs;
591
592                 firstst = reallocate_integer_array( firstst, current_mns );
593                 lastst = reallocate_integer_array( lastst, current_mns );
594                 finalst = reallocate_integer_array( finalst, current_mns );
595                 transchar = reallocate_integer_array( transchar, current_mns );
596                 trans1 = reallocate_integer_array( trans1, current_mns );
597                 trans2 = reallocate_integer_array( trans2, current_mns );
598                 accptnum = reallocate_integer_array( accptnum, current_mns );
599                 assoc_rule =
600                         reallocate_integer_array( assoc_rule, current_mns );
601                 state_type =
602                         reallocate_integer_array( state_type, current_mns );
603                 }
604
605         firstst[lastnfa] = lastnfa;
606         finalst[lastnfa] = lastnfa;
607         lastst[lastnfa] = lastnfa;
608         transchar[lastnfa] = sym;
609         trans1[lastnfa] = NO_TRANSITION;
610         trans2[lastnfa] = NO_TRANSITION;
611         accptnum[lastnfa] = NIL;
612         assoc_rule[lastnfa] = num_rules;
613         state_type[lastnfa] = current_state_type;
614
615         /* Fix up equivalence classes base on this transition.  Note that any
616          * character which has its own transition gets its own equivalence
617          * class.  Thus only characters which are only in character classes
618          * have a chance at being in the same equivalence class.  E.g. "a|b"
619          * puts 'a' and 'b' into two different equivalence classes.  "[ab]"
620          * puts them in the same equivalence class (barring other differences
621          * elsewhere in the input).
622          */
623
624         if ( sym < 0 )
625                 {
626                 /* We don't have to update the equivalence classes since
627                  * that was already done when the ccl was created for the
628                  * first time.
629                  */
630                 }
631
632         else if ( sym == SYM_EPSILON )
633                 ++numeps;
634
635         else
636                 {
637                 check_char( sym );
638
639                 if ( useecs )
640                         /* Map NUL's to csize. */
641                         mkechar( sym ? sym : csize, nextecm, ecgroup );
642                 }
643
644         return lastnfa;
645         }
646
647
648 /* mkxtion - make a transition from one state to another
649  *
650  * synopsis
651  *
652  *   mkxtion( statefrom, stateto );
653  *
654  *     statefrom - the state from which the transition is to be made
655  *     stateto   - the state to which the transition is to be made
656  */
657
658 void mkxtion(int statefrom, int stateto)
659         {
660         if ( trans1[statefrom] == NO_TRANSITION )
661                 trans1[statefrom] = stateto;
662
663         else if ( (transchar[statefrom] != SYM_EPSILON) ||
664                   (trans2[statefrom] != NO_TRANSITION) )
665                 flexfatal( _( "found too many transitions in mkxtion()" ) );
666
667         else
668                 { /* second out-transition for an epsilon state */
669                 ++eps2;
670                 trans2[statefrom] = stateto;
671                 }
672         }
673
674 /* new_rule - initialize for a new rule */
675
676 void new_rule(void)
677         {
678         if ( ++num_rules >= current_max_rules )
679                 {
680                 ++num_reallocs;
681                 current_max_rules += MAX_RULES_INCREMENT;
682                 rule_type = reallocate_integer_array( rule_type,
683                                                         current_max_rules );
684                 rule_linenum = reallocate_integer_array( rule_linenum,
685                                                         current_max_rules );
686                 rule_useful = reallocate_integer_array( rule_useful,
687                                                         current_max_rules );
688                 }
689
690         if ( num_rules > MAX_RULE )
691                 lerrif( _( "too many rules (> %d)!" ), MAX_RULE );
692
693         rule_linenum[num_rules] = linenum;
694         rule_useful[num_rules] = false;
695         }