Tcl Source Code

Check-in [4d7eba11ad]
Login
Bounty program for improvements to Tcl and certain Tcl packages.
Tcl 2019 Conference, Houston/TX, US, Nov 4-8
Send your abstracts to [email protected]
or submit via the online form by Sep 9.

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:3604074,3606683 Rewrite of the fixempties() routine (and supporting routines) to completely eliminate the infinite loop hazard. Thanks to Tom Lane for the much improved solution.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 4d7eba11ad2f9de4c5c41e7a1a29b96bf557af30
User & Date: dgp 2013-03-06 20:50:53
Context
2013-03-06
21:55
Cleaner error handling in fixempties(). check-in: c769b9bb91 user: dgp tags: trunk
20:54
merge trunk check-in: 54d0ba332e user: dgp tags: dgp-refactor
20:50
3604074,3606683 Rewrite of the fixempties() routine (and supporting routines) to completely eliminat... check-in: 4d7eba11ad user: dgp tags: trunk
20:28
3604074,3606683 Rewrite of the fixempties() routine (and supporting routines) to completely eliminat... check-in: 71a42e2a9c user: dgp tags: core-8-5-branch
20:25
merge trunk Closed-Leaf check-in: 83fa62555b user: dgp tags: bug-3606683
12:26
Tell fossil and Eclipse that the default eol-convention is LF. Tell fossil which files are binary a... check-in: da4c323ede user: jan.nijtmans tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ChangeLog.








1
2
3
4
5
6
7






2013-02-28  Don Porter  <[email protected]>

	* generic/tclLiteral.c:	Revise TclReleaseLiteral() to tolerate a
	NULL interp argument.

	* generic/tclCompile.c:	Update callers and revise mistaken comments.
	* generic/tclProc.c:
>
>
>
>
>
>
>







1
2
3
4
5
6
7
8
9
10
11
12
13
14
2013-03-06  Don Porter  <[email protected]>

	* generic/regc_nfa.c:	[Bugs 3604074,3606683] Rewrite of the
	* generic/regcomp.c:	fixempties() routine (and supporting
	routines) to completely eliminate the infinite loop hazard.
	Thanks to Tom Lane for the much improved solution.

2013-02-28  Don Porter  <[email protected]>

	* generic/tclLiteral.c:	Revise TclReleaseLiteral() to tolerate a
	NULL interp argument.

	* generic/tclCompile.c:	Update callers and revise mistaken comments.
	* generic/tclProc.c:

Changes to generic/regc_nfa.c.

491
492
493
494
495
496
497
























































498
499
500
501
502
503
504
...
555
556
557
558
559
560
561
562

563
564
565
566
567
568
569

570
571
572
573
574
575

576

577
578
579
580
581
582
583
...
594
595
596
597
598
599
600
601

602
603
604
605
606
607
608

609
610
611
612
613
614

615

616
617
618
619
620
621
622
...
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
....
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
....
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256

1257


1258
1259
1260
1261
1262
1263

1264



1265

1266






1267
1268
1269


1270






1271
1272




1273


1274

1275

1276
1277
1278
1279
1280















1281











1282












1283
1284
1285
1286
1287
1288

1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302









1303
1304
1305
1306
1307
1308

1309
1310
1311
1312
1313
1314
1315
1316
1317
1318








1319
1320

1321
1322
1323
1324
1325
1326
1327



1328
1329

1330
1331
1332

1333
1334
1335
1336
1337




1338





1339
1340


1341
1342





















1343
1344
1345
1346

1347
1348
1349
1350
1351
1352
1353
1354




1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
    victim->from = NULL;	/* precautions... */
    victim->to = NULL;
    victim->inchain = NULL;
    victim->outchain = NULL;
    victim->freechain = from->free;
    from->free = victim;
}
























































 
/*
 - findarc - find arc, if any, from given source with given type and color
 * If there is more than one such arc, the result is random.
 ^ static struct arc *findarc(struct state *, int, pcolor);
 */
static struct arc *
................................................................................
	freearc(nfa, a);
    }
    assert(oldState->nins == 0);
    assert(oldState->ins == NULL);
}
 
/*
 - copyins - copy all in arcs of a state to another state

 ^ static void copyins(struct nfa *, struct state *, struct state *);
 */
static void
copyins(
    struct nfa *nfa,
    struct state *oldState,
    struct state *newState)

{
    struct arc *a;

    assert(oldState != newState);

    for (a=oldState->ins ; a!=NULL ; a=a->inchain) {

	cparc(nfa, a, a->from, newState);

    }
}
 
/*
 - moveouts - move all out arcs of a state to another state
 ^ static void moveouts(struct nfa *, struct state *, struct state *);
 */
................................................................................
    while ((a = oldState->outs) != NULL) {
	cparc(nfa, a, newState, a->to);
	freearc(nfa, a);
    }
}
 
/*
 - copyouts - copy all out arcs of a state to another state

 ^ static void copyouts(struct nfa *, struct state *, struct state *);
 */
static void
copyouts(
    struct nfa *nfa,
    struct state *oldState,
    struct state *newState)

{
    struct arc *a;

    assert(oldState != newState);

    for (a=oldState->outs ; a!=NULL ; a=a->outchain) {

	cparc(nfa, a, newState, a->to);

    }
}
 
/*
 - cloneouts - copy out arcs of a state to another state pair, modifying type
 ^ static void cloneouts(struct nfa *, struct state *, struct state *,
 ^ 	struct state *, int);
................................................................................
     */

    if (from->nouts > 1) {
	s = newstate(nfa);
	if (NISERR()) {
	    return 0;
	}
	assert(to != from);	/* con is not an inarc */
	copyins(nfa, from, s);	/* duplicate inarcs */
	cparc(nfa, con, s, to);	/* move constraint arc */
	freearc(nfa, con);
	from = s;
	con = from->outs;
    }
    assert(from->nouts == 1);

    /*
................................................................................
     */

    if (to->nins > 1) {
	s = newstate(nfa);
	if (NISERR()) {
	    return 0;
	}
	copyouts(nfa, to, s);	/* duplicate outarcs */
	cparc(nfa, con, from, s);	/* move constraint */
	freearc(nfa, con);
	to = s;
	con = to->ins;
    }
    assert(to->nins == 1);

................................................................................
 */
static void
fixempties(
    struct nfa *nfa,
    FILE *f)			/* for debug output; NULL none */
{
    struct state *s;
    struct state *nexts;
    struct state *to;
    struct arc *a;
    struct arc *nexta;
    int progress;

    /*

     * Find and eliminate empties until there are no more.


     */

    do {
	progress = 0;
	for (s = nfa->states; s != NULL && !NISERR(); s = nexts) {
	    nexts = s->next;

	    for (a = s->outs; a != NULL && !NISERR(); a = a->outchain) {



		if (a->type == EMPTY) {








		    /*
		     *  Mark a for deletion; copy arcs to preserve graph
		     * connectivity after it is gone.


		     */







		    unempty(nfa, a);




		}


	    }



	    /*
	     * Now pass through and delete the marked arcs.  Doing all the
	     * deletion after all the marking prevents arc copying from
	     * resurrecting deleted arcs which can cause failure to converge.
	     * [Tcl Bug 3604074]















	     */
























	    for (a = s->outs; a != NULL; a = nexta) {
		nexta = a->outchain;
		if (a->from == NULL) {
		    progress = 1;
		    to = a->to;
		    a->from = s;

		    freearc(nfa, a);
		    if (to->nins == 0) {
			while ((a = to->outs)) {
			    freearc(nfa, a);
			}
			if (nexts == to) {
			    nexts = to->next;
			}
			freestate(nfa, to);
		    }
		    if (s->nouts == 0) {
			while ((a = s->ins)) {
			    freearc(nfa, a);
			}









			freestate(nfa, s);
		    }
		}
	    }
	}
	if (progress && f != NULL) {

	    dumpnfa(nfa, f);
	}
    } while (progress && !NISERR());
}
 
/*
 - unempty - optimize out an EMPTY arc, if possible
 * Actually, as it stands this function always succeeds, but the return value
 * is kept with an eye on possible future changes.
 ^ static int unempty(struct nfa *, struct arc *);








 */
static int			/* 0 couldn't, 1 could */

unempty(
    struct nfa *nfa,
    struct arc *a)
{
    struct state *from = a->from;
    struct state *to = a->to;




    assert(a->type == EMPTY);
    assert(from != nfa->pre && to != nfa->post);


    if (from == to) {		/* vacuous loop */
	freearc(nfa, a);

	return 1;
    }

    /*
     *  Mark arc for deletion.




     */






    a->from = NULL;



    if (from->nouts > to->nins) {





















	copyouts(nfa, to, from);
	return 1;
    }
    if (from->nouts < to->nins) {

	copyins(nfa, from, to);
	return 1;
    }

    /*
     * from->nouts == to->nins . decide on secondary issue:  copy fewest arcs
     */





    if (from->nins > to->nouts) {
	copyouts(nfa, to, from);
	return 1;
    }

    copyins(nfa, from, to);
    return 1;
}
 
/*
 - cleanup - clean up NFA after optimizations
 ^ static void cleanup(struct nfa *);
 */
static void






>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







|
>
|





|
>






>
|
>







 







|
>
|





|
>






>
|
>







 







|
|
|







 







|







 







|
|


<


>
|
>
>

<
<
<
|
|
>
|
>
>
>
|
>
|
>
>
>
>
>
>
|
<
<
>
>
|
>
>
>
>
>
>
|
<
>
>
>
>
|
>
>
|
>
|
>
|
<
<
<
<
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
>
>
>
>
>
>
>
>
>
>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
|
|
<
<
<
<
>
|
<
<
<
|
<
<
|
<
|
<
<
<
|
>
>
>
>
>
>
>
>
>
|
|
|
|
<
<
>
|
|
<



<
<
<
<
>
>
>
>
>
>
>
>

<
>
|
|
|

<
|

>
>
>
|
<
>
|
<
<
>
|
|
|
|
<
>
>
>
>
|
>
>
>
>
>
|
<
>
>

<
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
|

<
>
|
|



|
<
|
>
>
>
>

|
|


|
<







491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
...
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
...
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
....
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
....
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
....
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317

1318
1319
1320
1321
1322
1323
1324



1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341


1342
1343
1344
1345
1346
1347
1348
1349
1350
1351

1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363




1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405




1406
1407



1408


1409

1410



1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424


1425
1426
1427

1428
1429
1430




1431
1432
1433
1434
1435
1436
1437
1438
1439

1440
1441
1442
1443
1444

1445
1446
1447
1448
1449
1450

1451
1452


1453
1454
1455
1456
1457

1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468

1469
1470
1471

1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495

1496
1497
1498
1499
1500
1501
1502

1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513

1514
1515
1516
1517
1518
1519
1520
    victim->from = NULL;	/* precautions... */
    victim->to = NULL;
    victim->inchain = NULL;
    victim->outchain = NULL;
    victim->freechain = from->free;
    from->free = victim;
}
 
/*
 - hasnonemptyout - Does state have a non-EMPTY out arc?
 ^ static int hasnonemptyout(struct state *);
 */
static int
hasnonemptyout(
    struct state *s)
{
    struct arc *a;

    for (a = s->outs; a != NULL; a = a->outchain) {
	if (a->type != EMPTY) {
	    return 1;
	}
    }
    return 0;
}
 
/*
 - nonemptyouts - count non-EMPTY out arcs of a state
 ^ static int nonemptyouts(struct state *);
 */
static int
nonemptyouts(
    struct state *s)
{
    int n = 0;
    struct arc *a;

    for (a = s->outs; a != NULL; a = a->outchain) {
	if (a->type != EMPTY) {
	    n++;
	}
    }
    return n;
}
 
/*
 - nonemptyins - count non-EMPTY in arcs of a state
 ^ static int nonemptyins(struct state *);
 */
static int
nonemptyins(
    struct state *s)
{
    int n = 0;
    struct arc *a;

    for (a = s->ins; a != NULL; a = a->inchain) {
	if (a->type != EMPTY) {
	    n++;
	}
    }
    return n;
}
 
/*
 - findarc - find arc, if any, from given source with given type and color
 * If there is more than one such arc, the result is random.
 ^ static struct arc *findarc(struct state *, int, pcolor);
 */
static struct arc *
................................................................................
	freearc(nfa, a);
    }
    assert(oldState->nins == 0);
    assert(oldState->ins == NULL);
}
 
/*
 - copyins - copy in arcs of a state to another state
 * Either all arcs, or only non-empty ones as determined by all value.
 ^ static VOID copyins(struct nfa *, struct state *, struct state *, int);
 */
static void
copyins(
    struct nfa *nfa,
    struct state *oldState,
    struct state *newState,
    int all)
{
    struct arc *a;

    assert(oldState != newState);

    for (a=oldState->ins ; a!=NULL ; a=a->inchain) {
	if (all || a->type != EMPTY) {
	    cparc(nfa, a, a->from, newState);
	}
    }
}
 
/*
 - moveouts - move all out arcs of a state to another state
 ^ static void moveouts(struct nfa *, struct state *, struct state *);
 */
................................................................................
    while ((a = oldState->outs) != NULL) {
	cparc(nfa, a, newState, a->to);
	freearc(nfa, a);
    }
}
 
/*
 - copyouts - copy out arcs of a state to another state
 * Either all arcs, or only non-empty ones as determined by all value.
 ^ static VOID copyouts(struct nfa *, struct state *, struct state *, int);
 */
static void
copyouts(
    struct nfa *nfa,
    struct state *oldState,
    struct state *newState,
    int all)
{
    struct arc *a;

    assert(oldState != newState);

    for (a=oldState->outs ; a!=NULL ; a=a->outchain) {
	if (all || a->type != EMPTY) {
	    cparc(nfa, a, newState, a->to);
	}
    }
}
 
/*
 - cloneouts - copy out arcs of a state to another state pair, modifying type
 ^ static void cloneouts(struct nfa *, struct state *, struct state *,
 ^ 	struct state *, int);
................................................................................
     */

    if (from->nouts > 1) {
	s = newstate(nfa);
	if (NISERR()) {
	    return 0;
	}
	assert(to != from);		/* con is not an inarc */
	copyins(nfa, from, s, 1);	/* duplicate inarcs */
	cparc(nfa, con, s, to);		/* move constraint arc */
	freearc(nfa, con);
	from = s;
	con = from->outs;
    }
    assert(from->nouts == 1);

    /*
................................................................................
     */

    if (to->nins > 1) {
	s = newstate(nfa);
	if (NISERR()) {
	    return 0;
	}
	copyouts(nfa, to, s, 1);	/* duplicate outarcs */
	cparc(nfa, con, from, s);	/* move constraint */
	freearc(nfa, con);
	to = s;
	con = to->ins;
    }
    assert(to->nins == 1);

................................................................................
 */
static void
fixempties(
    struct nfa *nfa,
    FILE *f)			/* for debug output; NULL none */
{
    struct state *s;
    struct state *s2;
    struct state *nexts;
    struct arc *a;
    struct arc *nexta;


    /*
     * First, get rid of any states whose sole out-arc is an EMPTY,
     * since they're basically just aliases for their successor.  The
     * parsing algorithm creates enough of these that it's worth
     * special-casing this.
     */



    for (s = nfa->states; s != NULL && !NISERR(); s = nexts) {
	nexts = s->next;
	if (s->flag || s->nouts != 1) {
	    continue;
	}
	a = s->outs;
	assert(a != NULL && a->outchain == NULL);
	if (a->type != EMPTY) {
	    continue;
	}
	if (s != a->to) {
	    moveins(nfa, s, a->to);
	}
	dropstate(nfa, s);
    }

    /*


     * Similarly, get rid of any state with a single EMPTY in-arc, by
     * folding it into its predecessor.
     */
    for (s = nfa->states; s != NULL && !NISERR(); s = nexts) {
	nexts = s->next;
	/* Ensure tmp fields are clear for next step */
	assert(s->tmp = NULL);
	if (s->flag || s->nins != 1) {
	    continue;
	}

	a = s->ins;
	assert(a != NULL && a->inchain == NULL);
	if (a->type != EMPTY) {
	    continue;
	}
	if (s != a->from) {
	    moveouts(nfa, s, a->from);
	}
	dropstate(nfa, s);
    }

    /*




     * For each remaining NFA state, find all other states that are
     * reachable from it by a chain of one or more EMPTY arcs.  Then
     * generate new arcs that eliminate the need for each such chain.
     *
     * If we just do this straightforwardly, the algorithm gets slow in
     * complex graphs, because the same arcs get copied to all
     * intermediate states of an EMPTY chain, and then uselessly pushed
     * repeatedly to the chain's final state; we waste a lot of time in
     * newarc's duplicate checking.  To improve matters, we decree that
     * any state with only EMPTY out-arcs is "doomed" and will not be
     * part of the final NFA. That can be ensured by not adding any new
     * out-arcs to such a state. Having ensured that, we need not update
     * the state's in-arcs list either; all arcs that might have gotten
     * pushed forward to it will just get pushed directly to successor
     * states.  This eliminates most of the useless duplicate arcs.
     */
    for (s = nfa->states; s != NULL && !NISERR(); s = s->next) {
	for (s2 = emptyreachable(s, s); s2 != s && !NISERR();
		s2 = nexts) {
	    /*
	     * If s2 is doomed, we decide that (1) we will always push
	     * arcs forward to it, not pull them back to s; and (2) we
	     * can optimize away the push-forward, per comment above.
	     * So do nothing.
	     */
	    if (s2->flag || hasnonemptyout(s2)) {
		replaceempty(nfa, s, s2);
	    }

	    /* Reset the tmp fields as we walk back */
	    nexts = s2->tmp;
	    s2->tmp = NULL;
	}
	s->tmp = NULL;
    }

    /*
     * Remove all the EMPTY arcs, since we don't need them anymore.
     */
    for (s = nfa->states; s != NULL; s = s->next) {
	for (a = s->outs; a != NULL; a = nexta) {
	    nexta = a->outchain;




	    if (a->type == EMPTY) {
		freearc(nfa, a);



	    }


	}

    }




    /*
     * And remove any states that have become useless.  (This cleanup is
     * not very thorough, and would be even less so if we tried to
     * combine it with the previous step; but cleanup() will take care
     * of anything we miss.)
     */
    for (s = nfa->states; s != NULL && !NISERR(); s = nexts) {
	nexts = s->next;
	if ((s->nins == 0 || s->nouts == 0) && !s->flag) {
	    dropstate(nfa, s);
	}
    }



    if (f != NULL && !NISERR()) {
	dumpnfa(nfa, f);
    }

}
 
/*




 - emptyreachable - recursively find all states reachable from s by EMPTY arcs
 * The return value is the last such state found.  Its tmp field links back
 * to the next-to-last such state, and so on back to s, so that all these
 * states can be located without searching the whole NFA.
 * The maximum recursion depth here is equal to the length of the longest
 * loop-free chain of EMPTY arcs, which is surely no more than the size of
 * the NFA, and in practice will be a lot less than that.
 ^ static struct state *emptyreachable(struct state *, struct state *);
 */

static struct state *
emptyreachable(
    struct state *s,
    struct state *lastfound)
{

    struct arc *a;

    s->tmp = lastfound;
    lastfound = s;
    for (a = s->outs; a != NULL; a = a->outchain) {
	if (a->type == EMPTY && a->to->tmp == NULL) {

	    lastfound = emptyreachable(a->to, lastfound);
	}


    }
    return lastfound;
}
 
/*

 - replaceempty - replace an EMPTY arc chain with some non-empty arcs
 * The EMPTY arc(s) should be deleted later, but we can't do it here because
 * they may still be needed to identify other arc chains during fixempties().
 ^ static void replaceempty(struct nfa *, struct state *, struct state *);
 */
static void
replaceempty(
    struct nfa *nfa,
    struct state *from,
    struct state *to)
{

    int fromouts;
    int toins;


    assert(from != to);

    /*
     * Create replacement arcs that bypass the need for the EMPTY chain.  We
     * can do this either by pushing arcs forward (linking directly from
     * "from"'s predecessors to "to") or by pulling them back (linking
     * directly from "from" to "to"'s successors).  In general, we choose
     * whichever way creates greater fan-out or fan-in, so as to improve the
     * odds of reducing the other state to zero in-arcs or out-arcs and
     * thereby being able to delete it.  However, if "from" is doomed (has no
     * non-EMPTY out-arcs), we must keep it so, so always push forward in that
     * case.
     *
     * The fan-out/fan-in comparison should count only non-EMPTY arcs.  If
     * "from" is doomed, we can skip counting "to"'s arcs, since we want to
     * force taking the copynonemptyins path in that case.
     */
    fromouts = nonemptyouts(from);
    toins = (fromouts == 0) ? 1 : nonemptyins(to);

    if (fromouts > toins) {
	copyouts(nfa, to, from, 0);
	return;
    }

    if (fromouts < toins) {
	copyins(nfa, from, to, 0);
	return;
    }

    /*
     * fromouts == toins.  Decide on secondary issue: copy fewest arcs.

     *
     * Doesn't seem to be worth the trouble to exclude empties from these
     * comparisons; that takes extra time and doesn't seem to improve the
     * resulting graph much.
     */
    if (from->nins > to->nouts) {
	copyouts(nfa, to, from, 0);
	return;
    }

    copyins(nfa, from, to, 0);

}
 
/*
 - cleanup - clean up NFA after optimizations
 ^ static void cleanup(struct nfa *);
 */
static void

Changes to generic/regcomp.c.

117
118
119
120
121
122
123



124
125
126
127
128
129
130
131
132
133
134
135
136
...
140
141
142
143
144
145
146

147
148
149
150
151
152
153
154
...
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
static struct state *newfstate(struct nfa *, int flag);
static void dropstate(struct nfa *, struct state *);
static void freestate(struct nfa *, struct state *);
static void destroystate(struct nfa *, struct state *);
static void newarc(struct nfa *, int, pcolor, struct state *, struct state *);
static struct arc *allocarc(struct nfa *, struct state *);
static void freearc(struct nfa *, struct arc *);



static struct arc *findarc(struct state *, int, pcolor);
static void cparc(struct nfa *, struct arc *, struct state *, struct state *);
static void moveins(struct nfa *, struct state *, struct state *);
static void copyins(struct nfa *, struct state *, struct state *);
static void moveouts(struct nfa *, struct state *, struct state *);
static void copyouts(struct nfa *, struct state *, struct state *);
static void cloneouts(struct nfa *, struct state *, struct state *, struct state *, int);
static void delsub(struct nfa *, struct state *, struct state *);
static void deltraverse(struct nfa *, struct state *, struct state *);
static void dupnfa(struct nfa *, struct state *, struct state *, struct state *, struct state *);
static void duptraverse(struct nfa *, struct state *, struct state *, int);
static void cleartraverse(struct nfa *, struct state *);
static void specialcolors(struct nfa *);
................................................................................
static void pushfwd(struct nfa *, FILE *);
static int push(struct nfa *, struct arc *);
#define	INCOMPATIBLE	1	/* destroys arc */
#define	SATISFIED	2	/* constraint satisfied */
#define	COMPATIBLE	3	/* compatible but not satisfied yet */
static int combine(struct arc *, struct arc *);
static void fixempties(struct nfa *, FILE *);

static int unempty(struct nfa *, struct arc *);
static void cleanup(struct nfa *);
static void markreachable(struct nfa *, struct state *, struct state *, struct state *);
static void markcanreach(struct nfa *, struct state *, struct state *, struct state *);
static long analyze(struct nfa *);
static void compact(struct nfa *, struct cnfa *);
static void carcsort(struct carc *, struct carc *);
static void freecnfa(struct cnfa *);
................................................................................
    /*
     * Do the splits.
     */

    for (s=slist ; s!=NULL ; s=s2) {
	s2 = newstate(nfa);

	copyouts(nfa, s, s2);
	for (a=s->ins ; a!=NULL ; a=b) {
	    b = a->inchain;

	    if (a->from != pre) {
		cparc(nfa, a, a->from, s2);
		freearc(nfa, a);
	    }






>
>
>



|

|







 







>
|







 







|







117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
...
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
...
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
static struct state *newfstate(struct nfa *, int flag);
static void dropstate(struct nfa *, struct state *);
static void freestate(struct nfa *, struct state *);
static void destroystate(struct nfa *, struct state *);
static void newarc(struct nfa *, int, pcolor, struct state *, struct state *);
static struct arc *allocarc(struct nfa *, struct state *);
static void freearc(struct nfa *, struct arc *);
static int hasnonemptyout(struct state *);
static int nonemptyouts(struct state *);
static int nonemptyins(struct state *);
static struct arc *findarc(struct state *, int, pcolor);
static void cparc(struct nfa *, struct arc *, struct state *, struct state *);
static void moveins(struct nfa *, struct state *, struct state *);
static void copyins(struct nfa *, struct state *, struct state *, int);
static void moveouts(struct nfa *, struct state *, struct state *);
static void copyouts(struct nfa *, struct state *, struct state *, int);
static void cloneouts(struct nfa *, struct state *, struct state *, struct state *, int);
static void delsub(struct nfa *, struct state *, struct state *);
static void deltraverse(struct nfa *, struct state *, struct state *);
static void dupnfa(struct nfa *, struct state *, struct state *, struct state *, struct state *);
static void duptraverse(struct nfa *, struct state *, struct state *, int);
static void cleartraverse(struct nfa *, struct state *);
static void specialcolors(struct nfa *);
................................................................................
static void pushfwd(struct nfa *, FILE *);
static int push(struct nfa *, struct arc *);
#define	INCOMPATIBLE	1	/* destroys arc */
#define	SATISFIED	2	/* constraint satisfied */
#define	COMPATIBLE	3	/* compatible but not satisfied yet */
static int combine(struct arc *, struct arc *);
static void fixempties(struct nfa *, FILE *);
static struct state *emptyreachable(struct state *, struct state *);
static void replaceempty(struct nfa *, struct state *, struct state *);
static void cleanup(struct nfa *);
static void markreachable(struct nfa *, struct state *, struct state *, struct state *);
static void markcanreach(struct nfa *, struct state *, struct state *, struct state *);
static long analyze(struct nfa *);
static void compact(struct nfa *, struct cnfa *);
static void carcsort(struct carc *, struct carc *);
static void freecnfa(struct cnfa *);
................................................................................
    /*
     * Do the splits.
     */

    for (s=slist ; s!=NULL ; s=s2) {
	s2 = newstate(nfa);

	copyouts(nfa, s, s2, 1);
	for (a=s->ins ; a!=NULL ; a=b) {
	    b = a->inchain;

	    if (a->from != pre) {
		cparc(nfa, a, a->from, s2);
		freearc(nfa, a);
	    }