← Back to branch summary

~ubuntu-branches/debian/sid/glib2.0/sid

« back to all changes in this revision

Viewing changes to glib/pcre/pcre_dfa_exec.c

  • Committer: Package Import Robot
  • Author(s): Martin Pitt
  • Date: 2013-05-08 06:25:57 UTC
  • mfrom: (1.27.14) (3.1.181 experimental)
  • Revision ID: package-import@ubuntu.com-20130508062557-i7gbku66mls70gi2
Tags: 2.36.1-2
Merge experimental branch, upload to unstable.

Show diffs side-by-side

added added

removed removed

Lines of Context:
glib/pcre/pcre_dfa_exec.c
38
38
-----------------------------------------------------------------------------
39
39
*/
40
40
 
41
 
 
42
41
/* This module contains the external function pcre_dfa_exec(), which is an
43
42
alternative matching function that uses a sort of DFA algorithm (not a true
44
 
FSM). This is NOT Perl- compatible, but it has advantages in certain
 
43
FSM). This is NOT Perl-compatible, but it has advantages in certain
45
44
applications. */
46
45
 
47
46
 
282
281
  int data;                       /* Some use extra data */
283
282
} stateblock;
284
283
 
285
 
#define INTS_PER_STATEBLOCK  (sizeof(stateblock)/sizeof(int))
 
284
#define INTS_PER_STATEBLOCK  (int)(sizeof(stateblock)/sizeof(int))
286
285
 
287
286
 
288
287
#ifdef PCRE_DEBUG
382
381
    next_new_state->count  = (y); \
383
382
    next_new_state->data   = (z); \
384
383
    next_new_state++; \
385
 
    DPRINTF(("%.*sADD_NEW_DATA(%d,%d,%d)\n", rlevel*2-2, SP, (x), (y), (z))); \
 
384
    DPRINTF(("%.*sADD_NEW_DATA(%d,%d,%d) line %d\n", rlevel*2-2, SP, \
 
385
      (x), (y), (z), __LINE__)); \
386
386
    } \
387
387
  else return PCRE_ERROR_DFA_WSSIZE
388
388
 
424
424
BOOL utf = FALSE;
425
425
#endif
426
426
 
 
427
BOOL reset_could_continue = FALSE;
 
428
 
427
429
rlevel++;
428
430
offsetcount &= (-2);
429
431
 
571
573
  int clen, dlen;
572
574
  unsigned int c, d;
573
575
  int forced_fail = 0;
574
 
  BOOL could_continue = FALSE;
 
576
  BOOL partial_newline = FALSE;
 
577
  BOOL could_continue = reset_could_continue;
 
578
  reset_could_continue = FALSE;
575
579
 
576
580
  /* Make the new state list into the active state list and empty the
577
581
  new state list. */
607
611
 
608
612
  if (ptr < end_subject)
609
613
    {
610
 
    clen = 1;        /* Number of bytes in the character */
 
614
    clen = 1;        /* Number of data items in the character */
611
615
#ifdef SUPPORT_UTF
612
616
    if (utf) { GETCHARLEN(c, ptr, clen); } else
613
617
#endif  /* SUPPORT_UTF */
641
645
 
642
646
    /* A negative offset is a special case meaning "hold off going to this
643
647
    (negated) state until the number of characters in the data field have
644
 
    been skipped". */
 
648
    been skipped". If the could_continue flag was passed over from a previous
 
649
    state, arrange for it to passed on. */
645
650
 
646
651
    if (state_offset < 0)
647
652
      {
650
655
        DPRINTF(("%.*sSkipping this character\n", rlevel*2-2, SP));
651
656
        ADD_NEW_DATA(state_offset, current_state->count,
652
657
          current_state->data - 1);
 
658
        if (could_continue) reset_could_continue = TRUE;
653
659
        continue;
654
660
        }
655
661
      else
689
695
    permitted.
690
696
 
691
697
    We also use this mechanism for opcodes such as OP_TYPEPLUS that take an
692
 
    argument that is not a data character - but is always one byte long. We
693
 
    have to take special action to deal with  \P, \p, \H, \h, \V, \v and \X in
694
 
    this case. To keep the other cases fast, convert these ones to new opcodes.
695
 
    */
 
698
    argument that is not a data character - but is always one byte long because
 
699
    the values are small. We have to take special action to deal with  \P, \p,
 
700
    \H, \h, \V, \v and \X in this case. To keep the other cases fast, convert
 
701
    these ones to new opcodes. */
696
702
 
697
703
    if (coptable[codevalue] > 0)
698
704
      {
783
789
            offsets[0] = (int)(current_subject - start_subject);
784
790
            offsets[1] = (int)(ptr - start_subject);
785
791
            DPRINTF(("%.*sSet matched string = \"%.*s\"\n", rlevel*2-2, SP,
786
 
              offsets[1] - offsets[0], current_subject));
 
792
              offsets[1] - offsets[0], (char *)current_subject));
787
793
            }
788
794
          if ((md->moptions & PCRE_DFA_SHORTEST) != 0)
789
795
            {
888
894
      /*-----------------------------------------------------------------*/
889
895
      case OP_ANY:
890
896
      if (clen > 0 && !IS_NEWLINE(ptr))
891
 
        { ADD_NEW(state_offset + 1, 0); }
 
897
        {
 
898
        if (ptr + 1 >= md->end_subject &&
 
899
            (md->moptions & (PCRE_PARTIAL_HARD)) != 0 &&
 
900
            NLBLOCK->nltype == NLTYPE_FIXED &&
 
901
            NLBLOCK->nllen == 2 &&
 
902
            c == NLBLOCK->nl[0])
 
903
          {
 
904
          could_continue = partial_newline = TRUE;
 
905
          }
 
906
        else
 
907
          {
 
908
          ADD_NEW(state_offset + 1, 0);
 
909
          }
 
910
        }
892
911
      break;
893
912
 
894
913
      /*-----------------------------------------------------------------*/
916
935
               (ptr == end_subject - md->nllen)
917
936
            ))
918
937
          { ADD_ACTIVE(state_offset + 1, 0); }
 
938
        else if (ptr + 1 >= md->end_subject &&
 
939
                 (md->moptions & (PCRE_PARTIAL_HARD|PCRE_PARTIAL_SOFT)) != 0 &&
 
940
                 NLBLOCK->nltype == NLTYPE_FIXED &&
 
941
                 NLBLOCK->nllen == 2 &&
 
942
                 c == NLBLOCK->nl[0])
 
943
          {
 
944
          if ((md->moptions & PCRE_PARTIAL_HARD) != 0)
 
945
            {
 
946
            reset_could_continue = TRUE;
 
947
            ADD_NEW_DATA(-(state_offset + 1), 0, 1);
 
948
            }
 
949
          else could_continue = partial_newline = TRUE;
 
950
          }
919
951
        }
920
952
      break;
921
953
 
928
960
        else if (clen == 0 ||
929
961
            ((md->poptions & PCRE_DOLLAR_ENDONLY) == 0 && IS_NEWLINE(ptr)))
930
962
          { ADD_ACTIVE(state_offset + 1, 0); }
 
963
        else if (ptr + 1 >= md->end_subject &&
 
964
                 (md->moptions & (PCRE_PARTIAL_HARD|PCRE_PARTIAL_SOFT)) != 0 &&
 
965
                 NLBLOCK->nltype == NLTYPE_FIXED &&
 
966
                 NLBLOCK->nllen == 2 &&
 
967
                 c == NLBLOCK->nl[0])
 
968
          {
 
969
          if ((md->moptions & PCRE_PARTIAL_HARD) != 0)
 
970
            {
 
971
            reset_could_continue = TRUE;
 
972
            ADD_NEW_DATA(-(state_offset + 1), 0, 1);
 
973
            }
 
974
          else could_continue = partial_newline = TRUE;
 
975
          }
931
976
        }
932
977
      else if (IS_NEWLINE(ptr))
933
978
        { ADD_ACTIVE(state_offset + 1, 0); }
1090
1135
      if (count > 0) { ADD_ACTIVE(state_offset + 2, 0); }
1091
1136
      if (clen > 0)
1092
1137
        {
1093
 
        if ((c >= 256 && d != OP_DIGIT && d != OP_WHITESPACE && d != OP_WORDCHAR) ||
 
1138
        if (d == OP_ANY && ptr + 1 >= md->end_subject &&
 
1139
            (md->moptions & (PCRE_PARTIAL_HARD)) != 0 &&
 
1140
            NLBLOCK->nltype == NLTYPE_FIXED &&
 
1141
            NLBLOCK->nllen == 2 &&
 
1142
            c == NLBLOCK->nl[0])
 
1143
          {
 
1144
          could_continue = partial_newline = TRUE;
 
1145
          }
 
1146
        else if ((c >= 256 && d != OP_DIGIT && d != OP_WHITESPACE && d != OP_WORDCHAR) ||
1094
1147
            (c < 256 &&
1095
1148
              (d != OP_ANY || !IS_NEWLINE(ptr)) &&
1096
1149
              ((ctypes[c] & toptable1[d]) ^ toptable2[d]) != 0))
1113
1166
      ADD_ACTIVE(state_offset + 2, 0);
1114
1167
      if (clen > 0)
1115
1168
        {
1116
 
        if ((c >= 256 && d != OP_DIGIT && d != OP_WHITESPACE && d != OP_WORDCHAR) ||
 
1169
        if (d == OP_ANY && ptr + 1 >= md->end_subject &&
 
1170
            (md->moptions & (PCRE_PARTIAL_HARD)) != 0 &&
 
1171
            NLBLOCK->nltype == NLTYPE_FIXED &&
 
1172
            NLBLOCK->nllen == 2 &&
 
1173
            c == NLBLOCK->nl[0])
 
1174
          {
 
1175
          could_continue = partial_newline = TRUE;
 
1176
          }
 
1177
        else if ((c >= 256 && d != OP_DIGIT && d != OP_WHITESPACE && d != OP_WORDCHAR) ||
1117
1178
            (c < 256 &&
1118
1179
              (d != OP_ANY || !IS_NEWLINE(ptr)) &&
1119
1180
              ((ctypes[c] & toptable1[d]) ^ toptable2[d]) != 0))
1135
1196
      ADD_ACTIVE(state_offset + 2, 0);
1136
1197
      if (clen > 0)
1137
1198
        {
1138
 
        if ((c >= 256 && d != OP_DIGIT && d != OP_WHITESPACE && d != OP_WORDCHAR) ||
 
1199
        if (d == OP_ANY && ptr + 1 >= md->end_subject &&
 
1200
            (md->moptions & (PCRE_PARTIAL_HARD)) != 0 &&
 
1201
            NLBLOCK->nltype == NLTYPE_FIXED &&
 
1202
            NLBLOCK->nllen == 2 &&
 
1203
            c == NLBLOCK->nl[0])
 
1204
          {
 
1205
          could_continue = partial_newline = TRUE;
 
1206
          }
 
1207
        else if ((c >= 256 && d != OP_DIGIT && d != OP_WHITESPACE && d != OP_WORDCHAR) ||
1139
1208
            (c < 256 &&
1140
1209
              (d != OP_ANY || !IS_NEWLINE(ptr)) &&
1141
1210
              ((ctypes[c] & toptable1[d]) ^ toptable2[d]) != 0))
1155
1224
      count = current_state->count;  /* Number already matched */
1156
1225
      if (clen > 0)
1157
1226
        {
1158
 
        if ((c >= 256 && d != OP_DIGIT && d != OP_WHITESPACE && d != OP_WORDCHAR) ||
 
1227
        if (d == OP_ANY && ptr + 1 >= md->end_subject &&
 
1228
            (md->moptions & (PCRE_PARTIAL_HARD)) != 0 &&
 
1229
            NLBLOCK->nltype == NLTYPE_FIXED &&
 
1230
            NLBLOCK->nllen == 2 &&
 
1231
            c == NLBLOCK->nl[0])
 
1232
          {
 
1233
          could_continue = partial_newline = TRUE;
 
1234
          }
 
1235
        else if ((c >= 256 && d != OP_DIGIT && d != OP_WHITESPACE && d != OP_WORDCHAR) ||
1159
1236
            (c < 256 &&
1160
1237
              (d != OP_ANY || !IS_NEWLINE(ptr)) &&
1161
1238
              ((ctypes[c] & toptable1[d]) ^ toptable2[d]) != 0))
1176
1253
      count = current_state->count;  /* Number already matched */
1177
1254
      if (clen > 0)
1178
1255
        {
1179
 
        if ((c >= 256 && d != OP_DIGIT && d != OP_WHITESPACE && d != OP_WORDCHAR) ||
 
1256
        if (d == OP_ANY && ptr + 1 >= md->end_subject &&
 
1257
            (md->moptions & (PCRE_PARTIAL_HARD)) != 0 &&
 
1258
            NLBLOCK->nltype == NLTYPE_FIXED &&
 
1259
            NLBLOCK->nllen == 2 &&
 
1260
            c == NLBLOCK->nl[0])
 
1261
          {
 
1262
          could_continue = partial_newline = TRUE;
 
1263
          }
 
1264
        else if ((c >= 256 && d != OP_DIGIT && d != OP_WHITESPACE && d != OP_WORDCHAR) ||
1180
1265
            (c < 256 &&
1181
1266
              (d != OP_ANY || !IS_NEWLINE(ptr)) &&
1182
1267
              ((ctypes[c] & toptable1[d]) ^ toptable2[d]) != 0))
1824
1909
          ncount++;
1825
1910
          nptr += ndlen;
1826
1911
          }
 
1912
        if (nptr >= end_subject && (md->moptions & PCRE_PARTIAL_HARD) != 0)
 
1913
            reset_could_continue = TRUE;
1827
1914
        if (++count >= GET2(code, 1))
1828
1915
          { ADD_NEW_DATA(-(state_offset + 2 + IMM2_SIZE), 0, ncount); }
1829
1916
        else
2037
2124
          ncount++;
2038
2125
          nptr += nclen;
2039
2126
          }
 
2127
        if (nptr >= end_subject && (md->moptions & PCRE_PARTIAL_HARD) != 0)
 
2128
            reset_could_continue = TRUE;
2040
2129
        ADD_NEW_DATA(-(state_offset + 1), 0, ncount);
2041
2130
        }
2042
2131
      break;
2062
2151
        break;
2063
2152
 
2064
2153
        case 0x000d:
2065
 
        if (ptr + 1 < end_subject && ptr[1] == 0x0a)
 
2154
        if (ptr + 1 >= end_subject)
 
2155
          {
 
2156
          ADD_NEW(state_offset + 1, 0);
 
2157
          if ((md->moptions & PCRE_PARTIAL_HARD) != 0)
 
2158
            reset_could_continue = TRUE;
 
2159
          }
 
2160
        else if (ptr[1] == 0x0a)
2066
2161
          {
2067
2162
          ADD_NEW_DATA(-(state_offset + 1), 0, 1);
2068
2163
          }
2171
2266
      break;
2172
2267
 
2173
2268
      /*-----------------------------------------------------------------*/
2174
 
      /* Match a negated single character casefully. This is only used for
2175
 
      one-byte characters, that is, we know that d < 256. The character we are
2176
 
      checking (c) can be multibyte. */
 
2269
      /* Match a negated single character casefully. */
2177
2270
 
2178
2271
      case OP_NOT:
2179
2272
      if (clen > 0 && c != d) { ADD_NEW(state_offset + dlen + 1, 0); }
2180
2273
      break;
2181
2274
 
2182
2275
      /*-----------------------------------------------------------------*/
2183
 
      /* Match a negated single character caselessly. This is only used for
2184
 
      one-byte characters, that is, we know that d < 256. The character we are
2185
 
      checking (c) can be multibyte. */
 
2276
      /* Match a negated single character caselessly. */
2186
2277
 
2187
2278
      case OP_NOTI:
2188
 
      if (clen > 0 && c != d && c != fcc[d])
2189
 
        { ADD_NEW(state_offset + dlen + 1, 0); }
 
2279
      if (clen > 0)
 
2280
        {
 
2281
        unsigned int otherd;
 
2282
#ifdef SUPPORT_UTF
 
2283
        if (utf && d >= 128)
 
2284
          {
 
2285
#ifdef SUPPORT_UCP
 
2286
          otherd = UCD_OTHERCASE(d);
 
2287
#endif  /* SUPPORT_UCP */
 
2288
          }
 
2289
        else
 
2290
#endif  /* SUPPORT_UTF */
 
2291
        otherd = TABLE_GET(d, fcc, d);
 
2292
        if (c != d && c != otherd)
 
2293
          { ADD_NEW(state_offset + dlen + 1, 0); }
 
2294
        }
2190
2295
      break;
2191
2296
 
2192
2297
      /*-----------------------------------------------------------------*/
2692
2797
            {
2693
2798
            int charcount = local_offsets[rc+1] - local_offsets[rc];
2694
2799
#ifdef SUPPORT_UTF
2695
 
            const pcre_uchar *p = start_subject + local_offsets[rc];
2696
 
            const pcre_uchar *pp = start_subject + local_offsets[rc+1];
2697
 
            while (p < pp) if (NOT_FIRSTCHAR(*p++)) charcount--;
 
2800
            if (utf)
 
2801
              {
 
2802
              const pcre_uchar *p = start_subject + local_offsets[rc];
 
2803
              const pcre_uchar *pp = start_subject + local_offsets[rc+1];
 
2804
              while (p < pp) if (NOT_FIRSTCHAR(*p++)) charcount--;
 
2805
              }
2698
2806
#endif
2699
2807
            if (charcount > 0)
2700
2808
              {
2793
2901
            const pcre_uchar *pp = local_ptr;
2794
2902
            charcount = (int)(pp - p);
2795
2903
#ifdef SUPPORT_UTF
2796
 
            while (p < pp) if (NOT_FIRSTCHAR(*p++)) charcount--;
 
2904
            if (utf) while (p < pp) if (NOT_FIRSTCHAR(*p++)) charcount--;
2797
2905
#endif
2798
2906
            ADD_NEW_DATA(-next_state_offset, 0, (charcount - 1));
2799
2907
            }
2875
2983
          else
2876
2984
            {
2877
2985
#ifdef SUPPORT_UTF
2878
 
            const pcre_uchar *p = start_subject + local_offsets[0];
2879
 
            const pcre_uchar *pp = start_subject + local_offsets[1];
2880
 
            while (p < pp) if (NOT_FIRSTCHAR(*p++)) charcount--;
 
2986
            if (utf)
 
2987
              {
 
2988
              const pcre_uchar *p = start_subject + local_offsets[0];
 
2989
              const pcre_uchar *pp = start_subject + local_offsets[1];
 
2990
              while (p < pp) if (NOT_FIRSTCHAR(*p++)) charcount--;
 
2991
              }
2881
2992
#endif
2882
2993
            ADD_NEW_DATA(-next_state_offset, 0, (charcount - 1));
2883
2994
            if (repeat_state_offset >= 0)
2946
3057
  if (new_count <= 0)
2947
3058
    {
2948
3059
    if (rlevel == 1 &&                               /* Top level, and */
2949
 
        could_continue &&                            /* Some could go on */
 
3060
        could_continue &&                            /* Some could go on, and */
2950
3061
        forced_fail != workspace[1] &&               /* Not all forced fail & */
2951
3062
        (                                            /* either... */
2952
3063
        (md->moptions & PCRE_PARTIAL_HARD) != 0      /* Hard partial */
2954
3065
        ((md->moptions & PCRE_PARTIAL_SOFT) != 0 &&  /* Soft partial and */
2955
3066
         match_count < 0)                            /* no matches */
2956
3067
        ) &&                                         /* And... */
2957
 
        ptr >= end_subject &&                  /* Reached end of subject */
2958
 
        ptr > md->start_used_ptr)              /* Inspected non-empty string */
 
3068
        (
 
3069
        partial_newline ||                           /* Either partial NL */
 
3070
          (                                          /* or ... */
 
3071
          ptr >= end_subject &&                /* End of subject and */
 
3072
          ptr > md->start_used_ptr)            /* Inspected non-empty string */
 
3073
          )
 
3074
        )
2959
3075
      {
2960
3076
      if (offsetcount >= 2)
2961
3077
        {
3052
3168
if (wscount < 20) return PCRE_ERROR_DFA_WSSIZE;
3053
3169
if (start_offset < 0 || start_offset > length) return PCRE_ERROR_BADOFFSET;
3054
3170
 
3055
 
/* We need to find the pointer to any study data before we test for byte
3056
 
flipping, so we scan the extra_data block first. This may set two fields in the
3057
 
match block, so we must initialize them beforehand. However, the other fields
3058
 
in the match block must not be set until after the byte flipping. */
 
3171
/* Check that the first field in the block is the magic number. If it is not,
 
3172
return with PCRE_ERROR_BADMAGIC. However, if the magic number is equal to
 
3173
REVERSED_MAGIC_NUMBER we return with PCRE_ERROR_BADENDIANNESS, which
 
3174
means that the pattern is likely compiled with different endianness. */
 
3175
 
 
3176
if (re->magic_number != MAGIC_NUMBER)
 
3177
  return re->magic_number == REVERSED_MAGIC_NUMBER?
 
3178
    PCRE_ERROR_BADENDIANNESS:PCRE_ERROR_BADMAGIC;
 
3179
if ((re->flags & PCRE_MODE) == 0) return PCRE_ERROR_BADMODE;
 
3180
 
 
3181
/* If restarting after a partial match, do some sanity checks on the contents
 
3182
of the workspace. */
 
3183
 
 
3184
if ((options & PCRE_DFA_RESTART) != 0)
 
3185
  {
 
3186
  if ((workspace[0] & (-2)) != 0 || workspace[1] < 1 ||
 
3187
    workspace[1] > (wscount - 2)/INTS_PER_STATEBLOCK)
 
3188
      return PCRE_ERROR_DFA_BADRESTART;
 
3189
  }
 
3190
 
 
3191
/* Set up study, callout, and table data */
3059
3192
 
3060
3193
md->tables = re->tables;
3061
3194
md->callout_data = NULL;
3074
3207
    md->tables = extra_data->tables;
3075
3208
  }
3076
3209
 
3077
 
/* Check that the first field in the block is the magic number. If it is not,
3078
 
return with PCRE_ERROR_BADMAGIC. However, if the magic number is equal to
3079
 
REVERSED_MAGIC_NUMBER we return with PCRE_ERROR_BADENDIANNESS, which
3080
 
means that the pattern is likely compiled with different endianness. */
3081
 
 
3082
 
if (re->magic_number != MAGIC_NUMBER)
3083
 
  return re->magic_number == REVERSED_MAGIC_NUMBER?
3084
 
    PCRE_ERROR_BADENDIANNESS:PCRE_ERROR_BADMAGIC;
3085
 
if ((re->flags & PCRE_MODE) == 0) return PCRE_ERROR_BADMODE;
3086
 
 
3087
3210
/* Set some local values */
3088
3211
 
3089
3212
current_subject = (const pcre_uchar *)subject + start_offset;