← Back to branch summary

~pythonregexp2.7/python/issue2636-01

« back to all changes in this revision

Viewing changes to Modules/_sre.c

  • Committer: Jeffrey C. "The TimeHorse" Jacobs
  • Date: 2008-06-04 19:22:10 UTC
  • Revision ID: darklord@timehorse.com-20080604192210-f2muwly10sm4inwp
As suggested, removed POSSESSIVE_UNTIL and put all the work in a very
simple POSSESSIVE_REPEAT handler; unfortunately, that still does not work
and the last version may still have some now-deleted code that probably
needs to come back in the next version, especially that comment about why
we need to jump to UNTIL straight from REPEAT to optimize zero-matches.

Show diffs side-by-side

added added

removed removed

Lines of Context:
Modules/_sre.c
775
775
#define JUMP_BRANCH          11
776
776
#define JUMP_ASSERT          12
777
777
#define JUMP_ASSERT_NOT      13
778
 
#define JUMP_POSS_UNTIL_1    14
779
 
#define JUMP_POSS_UNTIL_2    15
780
 
#define JUMP_ATOMIC_GROUP    16
 
778
#define JUMP_POSS_REPEAT     14
 
779
#define JUMP_ATOMIC_GROUP    15
781
780
 
782
781
#define DO_JUMP(jumpvalue, jumplabel, nextpattern) \
783
782
    DATA_ALLOC(SRE_MATCH_CONTEXT, nextctx); \
1377
1376
            RETURN_FAILURE;
1378
1377
 
1379
1378
        case SRE_OP_POSSESSIVE_REPEAT:
1380
 
            /* create repeat context.  all the hard work is done
1381
 
               by the UNTIL operator (POSSESSIVE_UNTIL) */
1382
 
            /* <POSSESSIVE_REPEAT> <skip> <1=min> <2=max> item
1383
 
               <POSSESSIVE_UNTIL> tail */
 
1379
            /* create possessive repeat contexts. */
 
1380
            /* <POSSESSIVE_REPEAT> <skip> <1=min> <2=max> <pattern>
 
1381
               <SUCCESS> tail */
1384
1382
            TRACE(("|%p|%p|POSSESSIVE_REPEAT %d %d\n", ctx->pattern,
1385
1383
                   ctx->ptr, ctx->pattern[1], ctx->pattern[2]));
1386
1384
 
1387
 
            /* install new repeat context */
1388
 
            ctx->u.rep = (SRE_REPEAT*) PyObject_MALLOC(sizeof(*ctx->u.rep));
1389
 
            if (!ctx->u.rep) {
1390
 
                PyErr_NoMemory();
1391
 
                RETURN_FAILURE;
 
1385
            /* Set the global Input pointer to this context's Input
 
1386
               pointer */
 
1387
            state->ptr = ctx->ptr;
 
1388
 
 
1389
            /* Initialize Count to 0 */
 
1390
            ctx->count = 0;
 
1391
 
 
1392
            /* Keep trying to parse the <pattern> sub-pattern until the
 
1393
               end is reached, creating a new context each time. */
 
1394
            while (ctx->count <= (int)ctx->pattern[2] ||
 
1395
                   (int)ctx->pattern[2] == 65535) {
 
1396
 
 
1397
                /* We have not reached the maximin matches, so try to
 
1398
                   match once more. */
 
1399
                DO_JUMP(JUMP_POSS_REPEAT, jump_poss_repeat,
 
1400
                        &ctx->pattern[3]);
 
1401
                RETURN_ON_ERROR(ret);
 
1402
 
 
1403
                /* Check to see if the last attempted match
 
1404
                   succeeded. */
 
1405
                if (ret) {
 
1406
                    /* Success, increment the count. */
 
1407
                    ctx->count++;
 
1408
                }
 
1409
                /* Last attempted match failed. */
 
1410
                else {
 
1411
                    /* Check for minimum required matches. */
 
1412
                    if (ctx->count < (int)ctx->pattern[1]) {
 
1413
                        RETURN_FAILURE;
 
1414
                    }
 
1415
                    else {
 
1416
                        /* We have sufficient matches, so exit loop. */
 
1417
                        break;
 
1418
                    }
 
1419
                }
1392
1420
            }
1393
 
            ctx->u.rep->count = -1;
1394
 
            ctx->u.rep->pattern = ctx->pattern;
1395
 
            ctx->u.rep->prev = state->repeat;
1396
 
            ctx->u.rep->last_ptr = NULL;
1397
 
            state->repeat = ctx->u.rep;
1398
 
 
1399
 
            state->ptr = ctx->ptr;
1400
 
 
1401
 
            /* Go to the Until Clause; we evaluate that first because
1402
 
               it is possible we may have a match count of 0 and so we
1403
 
               want to skip the evaluation of pattern until UNTIL has
1404
 
               set up a stack point where it can fail and just continue
1405
 
               onto the tail. */
1406
 
            ctx->pattern += ctx->pattern[0];
1407
 
            break;
1408
 
 
1409
 
            /* TODO move code to UNTIL handler */
1410
 
            printf("\nResult: %lu; Last Count: %lu @ %s with next op "
1411
 
                   "code: %d\n", ret, ctx->u.rep->count,
1412
 
                   (char *)state->ptr, ctx->pattern[ctx->pattern[0]+1]);
1413
 
            state->repeat = ctx->u.rep->prev;
1414
 
            PyObject_FREE(ctx->u.rep);
1415
1421
 
1416
1422
            /* Evaluate Tail */
1417
1423
            ctx->pattern += ctx->pattern[0] + 1;
1418
1424
            break;
1419
1425
 
1420
 
        case SRE_OP_POSSESSIVE_UNTIL:
1421
 
            /* maximizing repeat */
1422
 
            /* <REPEAT> <skip> <1=min> <2=max> item <POSSESSIVE_UNTIL>
1423
 
               tail */
1424
 
 
1425
 
            /* FIXME: we probably need to deal with zero-width
1426
 
               matches in here... */
1427
 
 
1428
 
            ctx->u.rep = state->repeat;
1429
 
            if (!ctx->u.rep) {
1430
 
                RETURN_ERROR(SRE_ERROR_STATE);
1431
 
            }
1432
 
 
1433
 
            state->ptr = ctx->ptr;
1434
 
 
1435
 
            ctx->count = ctx->u.rep->count+1;
1436
 
 
1437
 
            TRACE(("|%p|%p|POSSESSIVE_UNTIL %d\n", ctx->pattern,
1438
 
                   ctx->ptr, ctx->count));
1439
 
            printf("\nCount: %lu @ %s; %d needed, %d capacity\n",
1440
 
                   ctx->count, ctx->ptr, ctx->u.rep->pattern[1],
1441
 
                   ctx->u.rep->pattern[2]);
1442
 
            printf("Offset: %p; End: %p; Context: %p\n", state->ptr,
1443
 
                   ctx->u.rep->last_ptr, ctx->ptr);
1444
 
 
1445
 
            if (ctx->count < ctx->u.rep->pattern[1]) {
1446
 
                /* not enough matches */
1447
 
                ctx->u.rep->count = ctx->count;
1448
 
                DO_JUMP(JUMP_POSS_UNTIL_1, jump_poss_until_1,
1449
 
                        ctx->u.rep->pattern+3);
1450
 
                printf("Return: %lu @ count = %lu\n", ret, ctx->count);
1451
 
                if (ret) {
1452
 
                    RETURN_ON_ERROR(ret);
1453
 
                    RETURN_SUCCESS;
1454
 
                }
1455
 
                ctx->u.rep->count = ctx->count-1;
1456
 
                state->ptr = ctx->ptr;
1457
 
                RETURN_FAILURE;
1458
 
            }
1459
 
 
1460
 
            if ((ctx->count < ctx->u.rep->pattern[2] ||
1461
 
                 ctx->u.rep->pattern[2] == 65535) &&
1462
 
                state->ptr != ctx->u.rep->last_ptr) {
1463
 
                /* we may have enough matches, but if we can
1464
 
                   match another item, do so */
1465
 
                ctx->u.rep->count = ctx->count;
1466
 
                LASTMARK_SAVE();
1467
 
                MARK_PUSH(ctx->lastmark);
1468
 
                /* zero-width match protection */
1469
 
                DATA_PUSH(&ctx->u.rep->last_ptr);
1470
 
                ctx->u.rep->last_ptr = state->ptr;
1471
 
                DO_JUMP(JUMP_POSS_UNTIL_2, jump_poss_until_2,
1472
 
                        ctx->u.rep->pattern+3);
1473
 
                DATA_POP(&ctx->u.rep->last_ptr);
1474
 
                printf("Return: %lu @ count = %lu w/ %s\n", ret,
1475
 
                       ctx->count, ctx->ptr);
1476
 
                if (ret) {
1477
 
                    MARK_POP_DISCARD(ctx->lastmark);
1478
 
                    RETURN_ON_ERROR(ret);
1479
 
                    RETURN_SUCCESS;
1480
 
                }
1481
 
                MARK_POP(ctx->lastmark);
1482
 
                LASTMARK_RESTORE();
1483
 
                ctx->u.rep->count = ctx->count-1;
1484
 
                state->ptr = ctx->ptr;
1485
 
            }
1486
 
 
1487
 
            /* Maximum matches reached or No more matches to match, so
1488
 
               return success */
1489
 
            state->repeat = ctx->u.rep->prev;
1490
 
            RETURN_SUCCESS;
1491
 
 
1492
1426
        case SRE_OP_GROUPREF:
1493
1427
            /* match backreference */
1494
1428
            TRACE(("|%p|%p|GROUPREF %d\n", ctx->pattern,
1622
1556
        case JUMP_MIN_UNTIL_3:
1623
1557
            TRACE(("|%p|%p|JUMP_MIN_UNTIL_3\n", ctx->pattern, ctx->ptr));
1624
1558
            goto jump_min_until_3;
1625
 
        case JUMP_POSS_UNTIL_2:
1626
 
            TRACE(("|%p|%p|JUMP_POSS_UNTIL_2\n", ctx->pattern, ctx->ptr));
1627
 
            goto jump_poss_until_2;
1628
1559
        case JUMP_BRANCH:
1629
1560
            TRACE(("|%p|%p|JUMP_BRANCH\n", ctx->pattern, ctx->ptr));
1630
1561
            goto jump_branch;
1634
1565
        case JUMP_MIN_UNTIL_1:
1635
1566
            TRACE(("|%p|%p|JUMP_MIN_UNTIL_1\n", ctx->pattern, ctx->ptr));
1636
1567
            goto jump_min_until_1;
1637
 
        case JUMP_POSS_UNTIL_1:
1638
 
            TRACE(("|%p|%p|JUMP_POSS_UNTIL_1\n", ctx->pattern, ctx->ptr));
1639
 
            goto jump_poss_until_1;
 
1568
        case JUMP_POSS_REPEAT:
 
1569
            TRACE(("|%p|%p|JUMP_POSS_REPEAT\n", ctx->pattern, ctx->ptr));
 
1570
            goto jump_poss_repeat;
1640
1571
        case JUMP_REPEAT:
1641
1572
            TRACE(("|%p|%p|JUMP_REPEAT\n", ctx->pattern, ctx->ptr));
1642
1573
            goto jump_repeat;