← Back to branch summary

~pythonregexp2.7/python/issue2636-09-01+10

« back to all changes in this revision

Viewing changes to Modules/_sre.c

  • Committer: Jeffrey C. "The TimeHorse" Jacobs
  • Date: 2008-09-22 21:39:45 UTC
  • mfrom: (39055.1.33 Regexp-2.7)
  • Revision ID: darklord@timehorse.com-20080922213945-23717m5eiqpamcyn
Merged in changes from the Single-Loop Engine branch.

Show diffs side-by-side

added added

removed removed

Lines of Context:
Modules/_sre.c
4801
4801
    offsetof(PatternObject, weakreflist),    /* tp_weaklistoffset */
4802
4802
};
4803
4803
 
 
4804
static int _validate(PatternObject *self); /* Forward */
 
4805
 
4804
4806
static PyObject *
4805
4807
_compile(PyObject* self_, PyObject* args)
4806
4808
{
4860
4862
 
4861
4863
    self->weakreflist = NULL;
4862
4864
 
 
4865
    if (!_validate(self)) {
 
4866
        Py_DECREF(self);
 
4867
        return NULL;
 
4868
    }
 
4869
 
4863
4870
    return (PyObject*) self;
4864
4871
}
4865
4872
 
4866
4873
/* -------------------------------------------------------------------- */
 
4874
/* Code validation */
 
4875
 
 
4876
/* To learn more about this code, have a look at the _compile() function in
 
4877
   Lib/sre_compile.py.  The validation functions below checks the code array
 
4878
   for conformance with the code patterns generated there.
 
4879
 
 
4880
   The nice thing about the generated code is that it is position-independent:
 
4881
   all jumps are relative jumps forward.  Also, jumps don't cross each other:
 
4882
   the target of a later jump is always earlier than the target of an earlier
 
4883
   jump.  IOW, this is okay:
 
4884
 
 
4885
   J---------J-------T--------T
 
4886
    \         \_____/        /
 
4887
     \______________________/
 
4888
 
 
4889
   but this is not:
 
4890
 
 
4891
   J---------J-------T--------T
 
4892
    \_________\_____/        /
 
4893
               \____________/
 
4894
 
 
4895
   It also helps that SRE_CODE is always an unsigned type, either 2 bytes or 4
 
4896
   bytes wide (the latter if Python is compiled for "wide" unicode support).
 
4897
*/
 
4898
 
 
4899
/* Defining this one enables tracing of the validator */
 
4900
#undef VVERBOSE
 
4901
 
 
4902
/* Trace macro for the validator */
 
4903
#if defined(VVERBOSE)
 
4904
#define VTRACE(v) printf v
 
4905
#else
 
4906
#define VTRACE(v)
 
4907
#endif
 
4908
 
 
4909
/* Report failure */
 
4910
#define FAIL do { VTRACE(("FAIL: %d\n", __LINE__)); return 0; } while (0)
 
4911
 
 
4912
/* Extract opcode, argument, or skip count from code array */
 
4913
#define GET_OP                                          \
 
4914
    do {                                                \
 
4915
        VTRACE(("%p: ", code));                         \
 
4916
        if (code >= end) FAIL;                          \
 
4917
        op = *code++;                                   \
 
4918
        VTRACE(("%lu (op)\n", (unsigned long)op));      \
 
4919
    } while (0)
 
4920
#define GET_ARG                                         \
 
4921
    do {                                                \
 
4922
        VTRACE(("%p= ", code));                         \
 
4923
        if (code >= end) FAIL;                          \
 
4924
        arg = *code++;                                  \
 
4925
        VTRACE(("%lu (arg)\n", (unsigned long)arg));    \
 
4926
    } while (0)
 
4927
#define GET_SKIP_ADJ(adj)                               \
 
4928
    do {                                                \
 
4929
        VTRACE(("%p= ", code));                         \
 
4930
        if (code >= end) FAIL;                          \
 
4931
        skip = *code;                                   \
 
4932
        VTRACE(("%lu (skip to %p)\n",                   \
 
4933
               (unsigned long)skip, code+skip));        \
 
4934
        if (code+skip-adj < code || code+skip-adj > end)\
 
4935
            FAIL;                                       \
 
4936
        code++;                                         \
 
4937
    } while (0)
 
4938
#define GET_SKIP GET_SKIP_ADJ(0)
 
4939
 
 
4940
static int
 
4941
_validate_charset(SRE_CODE *code, SRE_CODE *end)
 
4942
{
 
4943
    /* Some variables are manipulated by the macros above */
 
4944
    SRE_CODE op;
 
4945
    SRE_CODE arg;
 
4946
    SRE_CODE offset;
 
4947
    int i;
 
4948
 
 
4949
    while (code < end) {
 
4950
        GET_OP;
 
4951
        switch (op) {
 
4952
 
 
4953
        case SRE_OP_NEGATE:
 
4954
            break;
 
4955
 
 
4956
        case SRE_OP_LITERAL:
 
4957
            GET_ARG;
 
4958
            break;
 
4959
 
 
4960
        case SRE_OP_RANGE:
 
4961
            GET_ARG;
 
4962
            GET_ARG;
 
4963
            break;
 
4964
 
 
4965
        case SRE_OP_CHARSET:
 
4966
            offset = 32/sizeof(SRE_CODE); /* 32-byte bitmap */
 
4967
            if (code+offset < code || code+offset > end)
 
4968
                FAIL;
 
4969
            code += offset;
 
4970
            break;
 
4971
 
 
4972
        case SRE_OP_BIGCHARSET:
 
4973
            GET_ARG; /* Number of blocks */
 
4974
            offset = 256/sizeof(SRE_CODE); /* 256-byte table */
 
4975
            if (code+offset < code || code+offset > end)
 
4976
                FAIL;
 
4977
            /* Make sure that each byte points to a valid block */
 
4978
            for (i = 0; i < 256; i++) {
 
4979
                if (((unsigned char *)code)[i] >= arg)
 
4980
                    FAIL;
 
4981
            }
 
4982
            code += offset;
 
4983
            offset = arg * 32/sizeof(SRE_CODE); /* 32-byte bitmap times arg */
 
4984
            if (code+offset < code || code+offset > end)
 
4985
                FAIL;
 
4986
            code += offset;
 
4987
            break;
 
4988
 
 
4989
        case SRE_OP_CATEGORY:
 
4990
            GET_ARG;
 
4991
            switch (arg) {
 
4992
            case SRE_CATEGORY_DIGIT:
 
4993
            case SRE_CATEGORY_NOT_DIGIT:
 
4994
            case SRE_CATEGORY_SPACE:
 
4995
            case SRE_CATEGORY_NOT_SPACE:
 
4996
            case SRE_CATEGORY_WORD:
 
4997
            case SRE_CATEGORY_NOT_WORD:
 
4998
            case SRE_CATEGORY_LINEBREAK:
 
4999
            case SRE_CATEGORY_NOT_LINEBREAK:
 
5000
            case SRE_CATEGORY_LOC_WORD:
 
5001
            case SRE_CATEGORY_LOC_NOT_WORD:
 
5002
            case SRE_CATEGORY_UNI_DIGIT:
 
5003
            case SRE_CATEGORY_UNI_NOT_DIGIT:
 
5004
            case SRE_CATEGORY_UNI_SPACE:
 
5005
            case SRE_CATEGORY_UNI_NOT_SPACE:
 
5006
            case SRE_CATEGORY_UNI_WORD:
 
5007
            case SRE_CATEGORY_UNI_NOT_WORD:
 
5008
            case SRE_CATEGORY_UNI_LINEBREAK:
 
5009
            case SRE_CATEGORY_UNI_NOT_LINEBREAK:
 
5010
                break;
 
5011
            default:
 
5012
                FAIL;
 
5013
            }
 
5014
            break;
 
5015
 
 
5016
        default:
 
5017
            FAIL;
 
5018
 
 
5019
        }
 
5020
    }
 
5021
 
 
5022
    return 1;
 
5023
}
 
5024
 
 
5025
static int
 
5026
_validate_inner(SRE_CODE *code, SRE_CODE *end, Py_ssize_t groups)
 
5027
{
 
5028
    /* Some variables are manipulated by the macros above */
 
5029
    SRE_CODE op;
 
5030
    SRE_CODE arg;
 
5031
    SRE_CODE skip;
 
5032
 
 
5033
    VTRACE(("code=%p, end=%p\n", code, end));
 
5034
 
 
5035
    if (code > end)
 
5036
        FAIL;
 
5037
 
 
5038
    while (code < end) {
 
5039
        GET_OP;
 
5040
        switch (op) {
 
5041
 
 
5042
        case SRE_OP_MARK:
 
5043
            /* We don't check whether marks are properly nested; the
 
5044
               sre_match() code is robust even if they don't, and the worst
 
5045
               you can get is nonsensical match results. */
 
5046
            GET_ARG;
 
5047
            if (arg > 2*groups+1) {
 
5048
                VTRACE(("arg=%d, groups=%d\n", (int)arg, (int)groups));
 
5049
                FAIL;
 
5050
            }
 
5051
            break;
 
5052
 
 
5053
        case SRE_OP_LITERAL:
 
5054
        case SRE_OP_NOT_LITERAL:
 
5055
        case SRE_OP_LITERAL_IGNORE:
 
5056
        case SRE_OP_NOT_LITERAL_IGNORE:
 
5057
            GET_ARG;
 
5058
            /* The arg is just a character, nothing to check */
 
5059
            break;
 
5060
 
 
5061
        case SRE_OP_SUCCESS:
 
5062
        case SRE_OP_FAILURE:
 
5063
            /* Nothing to check; these normally end the matching process */
 
5064
            break;
 
5065
 
 
5066
        case SRE_OP_AT:
 
5067
            GET_ARG;
 
5068
            switch (arg) {
 
5069
            case SRE_AT_BEGINNING:
 
5070
            case SRE_AT_BEGINNING_STRING:
 
5071
            case SRE_AT_BEGINNING_LINE:
 
5072
            case SRE_AT_END:
 
5073
            case SRE_AT_END_LINE:
 
5074
            case SRE_AT_END_STRING:
 
5075
            case SRE_AT_BOUNDARY:
 
5076
            case SRE_AT_NON_BOUNDARY:
 
5077
            case SRE_AT_LOC_BOUNDARY:
 
5078
            case SRE_AT_LOC_NON_BOUNDARY:
 
5079
            case SRE_AT_UNI_BOUNDARY:
 
5080
            case SRE_AT_UNI_NON_BOUNDARY:
 
5081
                break;
 
5082
            default:
 
5083
                FAIL;
 
5084
            }
 
5085
            break;
 
5086
 
 
5087
        case SRE_OP_ANY:
 
5088
        case SRE_OP_ANY_ALL:
 
5089
            /* These have no operands */
 
5090
            break;
 
5091
 
 
5092
        case SRE_OP_IN:
 
5093
        case SRE_OP_IN_IGNORE:
 
5094
            GET_SKIP;
 
5095
            /* Stop 1 before the end; we check the FAILURE below */
 
5096
            if (!_validate_charset(code, code+skip-2))
 
5097
                FAIL;
 
5098
            if (code[skip-2] != SRE_OP_FAILURE)
 
5099
                FAIL;
 
5100
            code += skip-1;
 
5101
            break;
 
5102
 
 
5103
        case SRE_OP_INFO:
 
5104
            {
 
5105
                /* A minimal info field is
 
5106
                   <INFO> <1=skip> <2=flags> <3=min> <4=max>;
 
5107
                   If SRE_INFO_PREFIX or SRE_INFO_CHARSET is in the flags,
 
5108
                   more follows. */
 
5109
                SRE_CODE flags, min, max, i;
 
5110
                SRE_CODE *newcode;
 
5111
                GET_SKIP;
 
5112
                newcode = code+skip-1;
 
5113
                GET_ARG; flags = arg;
 
5114
                GET_ARG; min = arg;
 
5115
                GET_ARG; max = arg;
 
5116
                /* Check that only valid flags are present */
 
5117
                if ((flags & ~(SRE_INFO_PREFIX |
 
5118
                               SRE_INFO_LITERAL |
 
5119
                               SRE_INFO_CHARSET)) != 0)
 
5120
                    FAIL;
 
5121
                /* PREFIX and CHARSET are mutually exclusive */
 
5122
                if ((flags & SRE_INFO_PREFIX) &&
 
5123
                    (flags & SRE_INFO_CHARSET))
 
5124
                    FAIL;
 
5125
                /* LITERAL implies PREFIX */
 
5126
                if ((flags & SRE_INFO_LITERAL) &&
 
5127
                    !(flags & SRE_INFO_PREFIX))
 
5128
                    FAIL;
 
5129
                /* Validate the prefix */
 
5130
                if (flags & SRE_INFO_PREFIX) {
 
5131
                    SRE_CODE prefix_len, prefix_skip;
 
5132
                    GET_ARG; prefix_len = arg;
 
5133
                    GET_ARG; prefix_skip = arg;
 
5134
                    /* Here comes the prefix string */
 
5135
                    if (code+prefix_len < code || code+prefix_len > newcode)
 
5136
                        FAIL;
 
5137
                    code += prefix_len;
 
5138
                    /* And here comes the overlap table */
 
5139
                    if (code+prefix_len < code || code+prefix_len > newcode)
 
5140
                        FAIL;
 
5141
                    /* Each overlap value should be < prefix_len */
 
5142
                    for (i = 0; i < prefix_len; i++) {
 
5143
                        if (code[i] >= prefix_len)
 
5144
                            FAIL;
 
5145
                    }
 
5146
                    code += prefix_len;
 
5147
                }
 
5148
                /* Validate the charset */
 
5149
                if (flags & SRE_INFO_CHARSET) {
 
5150
                    if (!_validate_charset(code, newcode-1))
 
5151
                        FAIL;
 
5152
                    if (newcode[-1] != SRE_OP_FAILURE)
 
5153
                        FAIL;
 
5154
                    code = newcode;
 
5155
                }
 
5156
                else if (code != newcode) {
 
5157
                  VTRACE(("code=%p, newcode=%p\n", code, newcode));
 
5158
                    FAIL;
 
5159
                }
 
5160
            }
 
5161
            break;
 
5162
 
 
5163
        case SRE_OP_BRANCH:
 
5164
            {
 
5165
                SRE_CODE *target = NULL;
 
5166
                for (;;) {
 
5167
                    GET_SKIP;
 
5168
                    if (skip == 0)
 
5169
                        break;
 
5170
                    /* Stop 2 before the end; we check the JUMP below */
 
5171
                    if (!_validate_inner(code, code+skip-3, groups))
 
5172
                        FAIL;
 
5173
                    code += skip-3;
 
5174
                    /* Check that it ends with a JUMP, and that each JUMP
 
5175
                       has the same target */
 
5176
                    GET_OP;
 
5177
                    if (op != SRE_OP_JUMP)
 
5178
                        FAIL;
 
5179
                    GET_SKIP;
 
5180
                    if (target == NULL)
 
5181
                        target = code+skip-1;
 
5182
                    else if (code+skip-1 != target)
 
5183
                        FAIL;
 
5184
                }
 
5185
            }
 
5186
            break;
 
5187
 
 
5188
        case SRE_OP_REPEAT_ONE:
 
5189
        case SRE_OP_MIN_REPEAT_ONE:
 
5190
            {
 
5191
                SRE_CODE min, max;
 
5192
                GET_SKIP;
 
5193
                GET_ARG; min = arg;
 
5194
                GET_ARG; max = arg;
 
5195
                if (min > max)
 
5196
                    FAIL;
 
5197
#ifdef Py_UNICODE_WIDE
 
5198
                if (max > 65535)
 
5199
                    FAIL;
 
5200
#endif
 
5201
                if (!_validate_inner(code, code+skip-4, groups))
 
5202
                    FAIL;
 
5203
                code += skip-4;
 
5204
                GET_OP;
 
5205
                if (op != SRE_OP_SUCCESS)
 
5206
                    FAIL;
 
5207
            }
 
5208
            break;
 
5209
 
 
5210
        case SRE_OP_REPEAT:
 
5211
            {
 
5212
                SRE_CODE min, max;
 
5213
                GET_SKIP;
 
5214
                GET_ARG; min = arg;
 
5215
                GET_ARG; max = arg;
 
5216
                if (min > max)
 
5217
                    FAIL;
 
5218
#ifdef Py_UNICODE_WIDE
 
5219
                if (max > 65535)
 
5220
                    FAIL;
 
5221
#endif
 
5222
                if (!_validate_inner(code, code+skip-3, groups))
 
5223
                    FAIL;
 
5224
                code += skip-3;
 
5225
                GET_OP;
 
5226
                if (op != SRE_OP_MAX_UNTIL && op != SRE_OP_MIN_UNTIL)
 
5227
                    FAIL;
 
5228
            }
 
5229
            break;
 
5230
 
 
5231
        case SRE_OP_GROUPREF:
 
5232
        case SRE_OP_GROUPREF_IGNORE:
 
5233
            GET_ARG;
 
5234
            if (arg >= groups)
 
5235
                FAIL;
 
5236
            break;
 
5237
 
 
5238
        case SRE_OP_GROUPREF_EXISTS:
 
5239
            /* The regex syntax for this is: '(?(group)then|else)', where
 
5240
               'group' is either an integer group number or a group name,
 
5241
               'then' and 'else' are sub-regexes, and 'else' is optional. */
 
5242
            GET_ARG;
 
5243
            if (arg >= groups)
 
5244
                FAIL;
 
5245
            GET_SKIP_ADJ(1);
 
5246
            code--; /* The skip is relative to the first arg! */
 
5247
            /* There are two possibilities here: if there is both a 'then'
 
5248
               part and an 'else' part, the generated code looks like:
 
5249
 
 
5250
               GROUPREF_EXISTS
 
5251
               <group>
 
5252
               <skipyes>
 
5253
               ...then part...
 
5254
               JUMP
 
5255
               <skipno>
 
5256
               (<skipyes> jumps here)
 
5257
               ...else part...
 
5258
               (<skipno> jumps here)
 
5259
 
 
5260
               If there is only a 'then' part, it looks like:
 
5261
 
 
5262
               GROUPREF_EXISTS
 
5263
               <group>
 
5264
               <skip>
 
5265
               ...then part...
 
5266
               (<skip> jumps here)
 
5267
 
 
5268
               There is no direct way to decide which it is, and we don't want
 
5269
               to allow arbitrary jumps anywhere in the code; so we just look
 
5270
               for a JUMP opcode preceding our skip target.
 
5271
            */
 
5272
            if (skip >= 3 && code+skip-3 >= code &&
 
5273
                code[skip-3] == SRE_OP_JUMP)
 
5274
            {
 
5275
                VTRACE(("both then and else parts present\n"));
 
5276
                if (!_validate_inner(code+1, code+skip-3, groups))
 
5277
                    FAIL;
 
5278
                code += skip-2; /* Position after JUMP, at <skipno> */
 
5279
                GET_SKIP;
 
5280
                if (!_validate_inner(code, code+skip-1, groups))
 
5281
                    FAIL;
 
5282
                code += skip-1;
 
5283
            }
 
5284
            else {
 
5285
                VTRACE(("only a then part present\n"));
 
5286
                if (!_validate_inner(code+1, code+skip-1, groups))
 
5287
                    FAIL;
 
5288
                code += skip-1;
 
5289
            }
 
5290
            break;
 
5291
 
 
5292
        case SRE_OP_ASSERT:
 
5293
        case SRE_OP_ASSERT_NOT:
 
5294
            GET_SKIP;
 
5295
            GET_ARG; /* 0 for lookahead, width for lookbehind */
 
5296
            code--; /* Back up over arg to simplify math below */
 
5297
            if (arg & 0x80000000)
 
5298
                FAIL; /* Width too large */
 
5299
            /* Stop 1 before the end; we check the SUCCESS below */
 
5300
            if (!_validate_inner(code+1, code+skip-2, groups))
 
5301
                FAIL;
 
5302
            code += skip-2;
 
5303
            GET_OP;
 
5304
            if (op != SRE_OP_SUCCESS)
 
5305
                FAIL;
 
5306
            break;
 
5307
 
 
5308
        default:
 
5309
            FAIL;
 
5310
 
 
5311
        }
 
5312
    }
 
5313
 
 
5314
    VTRACE(("okay\n"));
 
5315
    return 1;
 
5316
}
 
5317
 
 
5318
static int
 
5319
_validate_outer(SRE_CODE *code, SRE_CODE *end, Py_ssize_t groups)
 
5320
{
 
5321
    if (groups < 0 || groups > 100 || code >= end || end[-1] != SRE_OP_SUCCESS)
 
5322
        FAIL;
 
5323
    if (groups == 0)  /* fix for simplejson */
 
5324
        groups = 100; /* 100 groups should always be safe */
 
5325
    return _validate_inner(code, end-1, groups);
 
5326
}
 
5327
 
 
5328
static int
 
5329
_validate(PatternObject *self)
 
5330
{
 
5331
    if (!_validate_outer(self->code, self->code+self->codesize, self->groups))
 
5332
    {
 
5333
        PyErr_SetString(PyExc_RuntimeError, "invalid SRE code");
 
5334
        return 0;
 
5335
    }
 
5336
    else
 
5337
        VTRACE(("Success!\n"));
 
5338
    return 1;
 
5339
}
 
5340
 
 
5341
/* -------------------------------------------------------------------- */
4867
5342
/* match methods */
4868
5343
 
4869
5344
static void