1/************************************************* 2* Perl-Compatible Regular Expressions * 3*************************************************/ 4 5/* 6This is a library of functions to support regular expressions whose syntax 7and semantics are as close as possible to those of the Perl 5 language. See 8the file Tech.Notes for some information on the internals. 9 10Written by: Philip Hazel <ph10@cam.ac.uk> 11 12 Copyright (c) 1997-2004 University of Cambridge 13 14----------------------------------------------------------------------------- 15Redistribution and use in source and binary forms, with or without 16modification, are permitted provided that the following conditions are met: 17 18 * Redistributions of source code must retain the above copyright notice, 19 this list of conditions and the following disclaimer. 20 21 * Redistributions in binary form must reproduce the above copyright 22 notice, this list of conditions and the following disclaimer in the 23 documentation and/or other materials provided with the distribution. 24 25 * Neither the name of the University of Cambridge nor the names of its 26 contributors may be used to endorse or promote products derived from 27 this software without specific prior written permission. 28 29THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 30AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 31IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 32ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 33LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 34CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 35SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 36INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 37CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 38ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 39POSSIBILITY OF SUCH DAMAGE. 40----------------------------------------------------------------------------- 41*/ 42 43 44/* Include the internals header, which itself includes Standard C headers plus 45the external pcre header. */ 46 47#include "internal.h" 48 49 50 51/************************************************* 52* Set a bit and maybe its alternate case * 53*************************************************/ 54 55/* Given a character, set its bit in the table, and also the bit for the other 56version of a letter if we are caseless. 57 58Arguments: 59 start_bits points to the bit map 60 c is the character 61 caseless the caseless flag 62 cd the block with char table pointers 63 64Returns: nothing 65*/ 66 67static void 68set_bit(uschar *start_bits, unsigned int c, BOOL caseless, compile_data *cd) 69{ 70start_bits[c/8] |= (1 << (c&7)); 71if (caseless && (cd->ctypes[c] & ctype_letter) != 0) 72 start_bits[cd->fcc[c]/8] |= (1 << (cd->fcc[c]&7)); 73} 74 75 76 77/************************************************* 78* Create bitmap of starting chars * 79*************************************************/ 80 81/* This function scans a compiled unanchored expression and attempts to build a 82bitmap of the set of initial characters. If it can't, it returns FALSE. As time 83goes by, we may be able to get more clever at doing this. 84 85Arguments: 86 code points to an expression 87 start_bits points to a 32-byte table, initialized to 0 88 caseless the current state of the caseless flag 89 utf8 TRUE if in UTF-8 mode 90 cd the block with char table pointers 91 92Returns: TRUE if table built, FALSE otherwise 93*/ 94 95static BOOL 96set_start_bits(const uschar *code, uschar *start_bits, BOOL caseless, 97 BOOL utf8, compile_data *cd) 98{ 99register int c; 100 101/* This next statement and the later reference to dummy are here in order to 102trick the optimizer of the IBM C compiler for OS/2 into generating correct 103code. Apparently IBM isn't going to fix the problem, and we would rather not 104disable optimization (in this module it actually makes a big difference, and 105the pcre module can use all the optimization it can get). */ 106 107volatile int dummy; 108 109do 110 { 111 const uschar *tcode = code + 1 + LINK_SIZE; 112 BOOL try_next = TRUE; 113 114 while (try_next) 115 { 116 /* If a branch starts with a bracket or a positive lookahead assertion, 117 recurse to set bits from within them. That's all for this branch. */ 118 119 if ((int)*tcode >= OP_BRA || *tcode == OP_ASSERT) 120 { 121 if (!set_start_bits(tcode, start_bits, caseless, utf8, cd)) 122 return FALSE; 123 try_next = FALSE; 124 } 125 126 else switch(*tcode) 127 { 128 default: 129 return FALSE; 130 131 /* Skip over callout */ 132 133 case OP_CALLOUT: 134 tcode += 2 + 2*LINK_SIZE; 135 break; 136 137 /* Skip over extended extraction bracket number */ 138 139 case OP_BRANUMBER: 140 tcode += 3; 141 break; 142 143 /* Skip over lookbehind and negative lookahead assertions */ 144 145 case OP_ASSERT_NOT: 146 case OP_ASSERTBACK: 147 case OP_ASSERTBACK_NOT: 148 do tcode += GET(tcode, 1); while (*tcode == OP_ALT); 149 tcode += 1+LINK_SIZE; 150 break; 151 152 /* Skip over an option setting, changing the caseless flag */ 153 154 case OP_OPT: 155 caseless = (tcode[1] & PCRE_CASELESS) != 0; 156 tcode += 2; 157 break; 158 159 /* BRAZERO does the bracket, but carries on. */ 160 161 case OP_BRAZERO: 162 case OP_BRAMINZERO: 163 if (!set_start_bits(++tcode, start_bits, caseless, utf8, cd)) 164 return FALSE; 165 dummy = 1; 166 do tcode += GET(tcode,1); while (*tcode == OP_ALT); 167 tcode += 1+LINK_SIZE; 168 break; 169 170 /* Single-char * or ? sets the bit and tries the next item */ 171 172 case OP_STAR: 173 case OP_MINSTAR: 174 case OP_QUERY: 175 case OP_MINQUERY: 176 set_bit(start_bits, tcode[1], caseless, cd); 177 tcode += 2; 178#ifdef SUPPORT_UTF8 179 if (utf8) while ((*tcode & 0xc0) == 0x80) tcode++; 180#endif 181 break; 182 183 /* Single-char upto sets the bit and tries the next */ 184 185 case OP_UPTO: 186 case OP_MINUPTO: 187 set_bit(start_bits, tcode[3], caseless, cd); 188 tcode += 4; 189#ifdef SUPPORT_UTF8 190 if (utf8) while ((*tcode & 0xc0) == 0x80) tcode++; 191#endif 192 break; 193 194 /* At least one single char sets the bit and stops */ 195 196 case OP_EXACT: /* Fall through */ 197 tcode += 2; 198 199 case OP_CHAR: 200 case OP_CHARNC: 201 case OP_PLUS: 202 case OP_MINPLUS: 203 set_bit(start_bits, tcode[1], caseless, cd); 204 try_next = FALSE; 205 break; 206 207 /* Single character type sets the bits and stops */ 208 209 case OP_NOT_DIGIT: 210 for (c = 0; c < 32; c++) 211 start_bits[c] |= ~cd->cbits[c+cbit_digit]; 212 try_next = FALSE; 213 break; 214 215 case OP_DIGIT: 216 for (c = 0; c < 32; c++) 217 start_bits[c] |= cd->cbits[c+cbit_digit]; 218 try_next = FALSE; 219 break; 220 221 case OP_NOT_WHITESPACE: 222 for (c = 0; c < 32; c++) 223 start_bits[c] |= ~cd->cbits[c+cbit_space]; 224 try_next = FALSE; 225 break; 226 227 case OP_WHITESPACE: 228 for (c = 0; c < 32; c++) 229 start_bits[c] |= cd->cbits[c+cbit_space]; 230 try_next = FALSE; 231 break; 232 233 case OP_NOT_WORDCHAR: 234 for (c = 0; c < 32; c++) 235 start_bits[c] |= ~cd->cbits[c+cbit_word]; 236 try_next = FALSE; 237 break; 238 239 case OP_WORDCHAR: 240 for (c = 0; c < 32; c++) 241 start_bits[c] |= cd->cbits[c+cbit_word]; 242 try_next = FALSE; 243 break; 244 245 /* One or more character type fudges the pointer and restarts, knowing 246 it will hit a single character type and stop there. */ 247 248 case OP_TYPEPLUS: 249 case OP_TYPEMINPLUS: 250 tcode++; 251 break; 252 253 case OP_TYPEEXACT: 254 tcode += 3; 255 break; 256 257 /* Zero or more repeats of character types set the bits and then 258 try again. */ 259 260 case OP_TYPEUPTO: 261 case OP_TYPEMINUPTO: 262 tcode += 2; /* Fall through */ 263 264 case OP_TYPESTAR: 265 case OP_TYPEMINSTAR: 266 case OP_TYPEQUERY: 267 case OP_TYPEMINQUERY: 268 switch(tcode[1]) 269 { 270 case OP_ANY: 271 return FALSE; 272 273 case OP_NOT_DIGIT: 274 for (c = 0; c < 32; c++) 275 start_bits[c] |= ~cd->cbits[c+cbit_digit]; 276 break; 277 278 case OP_DIGIT: 279 for (c = 0; c < 32; c++) 280 start_bits[c] |= cd->cbits[c+cbit_digit]; 281 break; 282 283 case OP_NOT_WHITESPACE: 284 for (c = 0; c < 32; c++) 285 start_bits[c] |= ~cd->cbits[c+cbit_space]; 286 break; 287 288 case OP_WHITESPACE: 289 for (c = 0; c < 32; c++) 290 start_bits[c] |= cd->cbits[c+cbit_space]; 291 break; 292 293 case OP_NOT_WORDCHAR: 294 for (c = 0; c < 32; c++) 295 start_bits[c] |= ~cd->cbits[c+cbit_word]; 296 break; 297 298 case OP_WORDCHAR: 299 for (c = 0; c < 32; c++) 300 start_bits[c] |= cd->cbits[c+cbit_word]; 301 break; 302 } 303 304 tcode += 2; 305 break; 306 307 /* Character class where all the information is in a bit map: set the 308 bits and either carry on or not, according to the repeat count. If it was 309 a negative class, and we are operating with UTF-8 characters, any byte 310 with a value >= 0xc4 is a potentially valid starter because it starts a 311 character with a value > 255. */ 312 313 case OP_NCLASS: 314 if (utf8) 315 { 316 start_bits[24] |= 0xf0; /* Bits for 0xc4 - 0xc8 */ 317 memset(start_bits+25, 0xff, 7); /* Bits for 0xc9 - 0xff */ 318 } 319 /* Fall through */ 320 321 case OP_CLASS: 322 { 323 tcode++; 324 325 /* In UTF-8 mode, the bits in a bit map correspond to character 326 values, not to byte values. However, the bit map we are constructing is 327 for byte values. So we have to do a conversion for characters whose 328 value is > 127. In fact, there are only two possible starting bytes for 329 characters in the range 128 - 255. */ 330 331 if (utf8) 332 { 333 for (c = 0; c < 16; c++) start_bits[c] |= tcode[c]; 334 for (c = 128; c < 256; c++) 335 { 336 if ((tcode[c/8] && (1 << (c&7))) != 0) 337 { 338 int d = (c >> 6) | 0xc0; /* Set bit for this starter */ 339 start_bits[d/8] |= (1 << (d&7)); /* and then skip on to the */ 340 c = (c & 0xc0) + 0x40 - 1; /* next relevant character. */ 341 } 342 } 343 } 344 345 /* In non-UTF-8 mode, the two bit maps are completely compatible. */ 346 347 else 348 { 349 for (c = 0; c < 32; c++) start_bits[c] |= tcode[c]; 350 } 351 352 /* Advance past the bit map, and act on what follows */ 353 354 tcode += 32; 355 switch (*tcode) 356 { 357 case OP_CRSTAR: 358 case OP_CRMINSTAR: 359 case OP_CRQUERY: 360 case OP_CRMINQUERY: 361 tcode++; 362 break; 363 364 case OP_CRRANGE: 365 case OP_CRMINRANGE: 366 if (((tcode[1] << 8) + tcode[2]) == 0) tcode += 5; 367 else try_next = FALSE; 368 break; 369 370 default: 371 try_next = FALSE; 372 break; 373 } 374 } 375 break; /* End of bitmap class handling */ 376 377 } /* End of switch */ 378 } /* End of try_next loop */ 379 380 code += GET(code, 1); /* Advance to next branch */ 381 } 382while (*code == OP_ALT); 383return TRUE; 384} 385 386 387 388/************************************************* 389* Study a compiled expression * 390*************************************************/ 391 392/* This function is handed a compiled expression that it must study to produce 393information that will speed up the matching. It returns a pcre_extra block 394which then gets handed back to pcre_exec(). 395 396Arguments: 397 re points to the compiled expression 398 options contains option bits 399 errorptr points to where to place error messages; 400 set NULL unless error 401 402Returns: pointer to a pcre_extra block, with study_data filled in and the 403 appropriate flag set; 404 NULL on error or if no optimization possible 405*/ 406 407EXPORT pcre_extra * 408pcre_study(const pcre *external_re, int options, const char **errorptr) 409{ 410uschar start_bits[32]; 411pcre_extra *extra; 412pcre_study_data *study; 413const uschar *tables; 414const real_pcre *re = (const real_pcre *)external_re; 415uschar *code = (uschar *)re + re->name_table_offset + 416 (re->name_count * re->name_entry_size); 417compile_data compile_block; 418 419*errorptr = NULL; 420 421if (re == NULL || re->magic_number != MAGIC_NUMBER) 422 { 423 *errorptr = "argument is not a compiled regular expression"; 424 return NULL; 425 } 426 427if ((options & ~PUBLIC_STUDY_OPTIONS) != 0) 428 { 429 *errorptr = "unknown or incorrect option bit(s) set"; 430 return NULL; 431 } 432 433/* For an anchored pattern, or an unanchored pattern that has a first char, or 434a multiline pattern that matches only at "line starts", no further processing 435at present. */ 436 437if ((re->options & (PCRE_ANCHORED|PCRE_FIRSTSET|PCRE_STARTLINE)) != 0) 438 return NULL; 439 440/* Set the character tables in the block that is passed around */ 441 442tables = re->tables; 443if (tables == NULL) 444 (void)pcre_fullinfo(external_re, NULL, PCRE_INFO_DEFAULT_TABLES, (void*)&tables); 445 446compile_block.lcc = tables + lcc_offset; 447compile_block.fcc = tables + fcc_offset; 448compile_block.cbits = tables + cbits_offset; 449compile_block.ctypes = tables + ctypes_offset; 450 451/* See if we can find a fixed set of initial characters for the pattern. */ 452 453memset(start_bits, 0, 32 * sizeof(uschar)); 454if (!set_start_bits(code, start_bits, (re->options & PCRE_CASELESS) != 0, 455 (re->options & PCRE_UTF8) != 0, &compile_block)) return NULL; 456 457/* Get a pcre_extra block and a pcre_study_data block. The study data is put in 458the latter, which is pointed to by the former, which may also get additional 459data set later by the calling program. At the moment, the size of 460pcre_study_data is fixed. We nevertheless save it in a field for returning via 461the pcre_fullinfo() function so that if it becomes variable in the future, we 462don't have to change that code. */ 463 464extra = (pcre_extra *)(pcre_malloc) 465 (sizeof(pcre_extra) + sizeof(pcre_study_data)); 466 467if (extra == NULL) 468 { 469 *errorptr = "failed to get memory"; 470 return NULL; 471 } 472 473study = (pcre_study_data *)((char *)extra + sizeof(pcre_extra)); 474extra->flags = PCRE_EXTRA_STUDY_DATA; 475extra->study_data = study; 476 477study->size = sizeof(pcre_study_data); 478study->options = PCRE_STUDY_MAPPED; 479memcpy(study->start_bits, start_bits, sizeof(start_bits)); 480 481return extra; 482} 483 484/* End of study.c */ 485