Tcl Source Code

Check-in [71a42e2a9c]
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 | core-8-5-branch
Files: files | file ages | folders
SHA1: 71a42e2a9c67b0eb6e5300b9b1c6fc8a01371dd8
User & Date: dgp 2013-03-06 20:28:10
Context
2013-03-06
21:54
Cleaner error handling in fixempties(). check-in: 8577d952c4 user: dgp tags: core-8-5-branch
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
19:56
merge 8.5 Closed-Leaf check-in: 5ea1084e1e user: dgp tags: bug-3606683-85
19:25
3604074,3606683 Rewrite of the fixempties() routine (and supporting routines) to completely eliminat... check-in: 8293cc6b1f user: dgp tags: core-8-4-branch
12:22
Add Eclipse .project too check-in: 7da71b436d user: jan.nijtmans tags: core-8-5-branch
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ChangeLog.








1
2
3
4
5
6
7






2013-02-27  Jan Nijtmans  <[email protected]>

	* generic/regcomp.c:	[Bug 3606139]: missing error check allows
	* tests/regexp.test:    regexp to crash Tcl. Thanks to Tom Lane
	for providing the test-case and the patch.

2013-02-26  Jan Nijtmans  <[email protected]>
>
>
>
>
>
>
>







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-27  Jan Nijtmans  <[email protected]>

	* generic/regcomp.c:	[Bug 3606139]: missing error check allows
	* tests/regexp.test:    regexp to crash Tcl. Thanks to Tom Lane
	for providing the test-case and the patch.

2013-02-26  Jan Nijtmans  <[email protected]>

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
...
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
....
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
....
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
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
    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
....
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
....
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
....
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
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
    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 *);
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 *);
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);
	    }