Tcl Source Code

Check-in [6fd3ededf1]
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:Rework into Tcl 8.5+ coding style.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | bug-3606683-85
Files: files | file ages | folders
SHA1: 6fd3ededf14bf208882be4985a97aea6a9d94845
User & Date: dgp 2013-03-06 19:53:42
Context
2013-03-06
19:56
merge 8.5 Closed-Leaf check-in: 5ea1084e1e user: dgp tags: bug-3606683-85
19:53
Rework into Tcl 8.5+ coding style. check-in: 6fd3ededf1 user: dgp tags: bug-3606683-85
18:01
Indent reduction in fixempties() check-in: cc4f0aada0 user: dgp tags: bug-3606683-85
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to generic/regc_nfa.c.

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
...
538
539
540
541
542
543
544
545
546

547
548
549
550
551
552
553
....
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
....
1411
1412
1413
1414
1415
1416
1417
1418
1419

1420
1421
1422
1423
1424
1425
1426
....
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481


1482
1483
1484
1485
1486
1487
1488
}
 
/*
 - hasnonemptyout - Does state have a non-EMPTY out arc?
 ^ static int hasnonemptyout(struct state *);
 */
static int
hasnonemptyout(s)
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 *);
................................................................................
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.
................................................................................
    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;
	/* while we're at it, 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;
    }

    /*
     * Now remove all the EMPTY arcs, since we don't need them anymore.
     */
    for (s = nfa->states; s != NULL && !NISERR(); 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.
................................................................................
    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
................................................................................
     * 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;
    } else {
	copyins(nfa, from, to, 0);
	return;
    }


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






|
|

|

|
|
|
>
>
|







 







|

>







 







|

>







 







|
|
|
>



|

>


|

>
|

>




|
|



|

|

>


|

>
|

>




|
|
|


|
|
|
|
|
>
|
|
|
|


|
>

|
|
|
>

|

>









|

|


|

>




|
|
|
>



|

|
|
>
|

>







 







|

>







 







<
<
<

>
>







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
...
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
....
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
....
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
....
1491
1492
1493
1494
1495
1496
1497



1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
}
 
/*
 - 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 *);
................................................................................
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.
................................................................................
    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.
................................................................................
    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
................................................................................
     * 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