Annotation of embedaddon/pcre/HACKING, revision 1.1.1.4
1.1 misho 1: Technical Notes about PCRE
2: --------------------------
3:
4: These are very rough technical notes that record potentially useful information
5: about PCRE internals. For information about testing PCRE, see the pcretest
6: documentation and the comment at the head of the RunTest file.
7:
8:
9: Historical note 1
10: -----------------
11:
12: Many years ago I implemented some regular expression functions to an algorithm
13: suggested by Martin Richards. These were not Unix-like in form, and were quite
14: restricted in what they could do by comparison with Perl. The interesting part
15: about the algorithm was that the amount of space required to hold the compiled
16: form of an expression was known in advance. The code to apply an expression did
17: not operate by backtracking, as the original Henry Spencer code and current
18: Perl code does, but instead checked all possibilities simultaneously by keeping
19: a list of current states and checking all of them as it advanced through the
20: subject string. In the terminology of Jeffrey Friedl's book, it was a "DFA
21: algorithm", though it was not a traditional Finite State Machine (FSM). When
22: the pattern was all used up, all remaining states were possible matches, and
23: the one matching the longest subset of the subject string was chosen. This did
24: not necessarily maximize the individual wild portions of the pattern, as is
25: expected in Unix and Perl-style regular expressions.
26:
27:
28: Historical note 2
29: -----------------
30:
31: By contrast, the code originally written by Henry Spencer (which was
32: subsequently heavily modified for Perl) compiles the expression twice: once in
33: a dummy mode in order to find out how much store will be needed, and then for
34: real. (The Perl version probably doesn't do this any more; I'm talking about
35: the original library.) The execution function operates by backtracking and
36: maximizing (or, optionally, minimizing in Perl) the amount of the subject that
37: matches individual wild portions of the pattern. This is an "NFA algorithm" in
38: Friedl's terminology.
39:
40:
41: OK, here's the real stuff
42: -------------------------
43:
44: For the set of functions that form the "basic" PCRE library (which are
45: unrelated to those mentioned above), I tried at first to invent an algorithm
46: that used an amount of store bounded by a multiple of the number of characters
47: in the pattern, to save on compiling time. However, because of the greater
48: complexity in Perl regular expressions, I couldn't do this. In any case, a
49: first pass through the pattern is helpful for other reasons.
50:
51:
1.1.1.4 ! misho 52: Support for 16-bit and 32-bit data strings
! 53: -------------------------------------------
1.1.1.2 misho 54:
1.1.1.4 ! misho 55: From release 8.30, PCRE supports 16-bit as well as 8-bit data strings; and from
! 56: release 8.32, PCRE supports 32-bit data strings. The library can be compiled
! 57: in any combination of 8-bit, 16-bit or 32-bit modes, creating different
! 58: libraries. In the description that follows, the word "short" is
1.1.1.2 misho 59: used for a 16-bit data quantity, and the word "unit" is used for a quantity
1.1.1.4 ! misho 60: that is a byte in 8-bit mode, a short in 16-bit mode and a 32-bit unsigned
! 61: integer in 32-bit mode. However, so as not to over-complicate the text, the
! 62: names of PCRE functions are given in 8-bit form only.
1.1.1.2 misho 63:
64:
1.1 misho 65: Computing the memory requirement: how it was
66: --------------------------------------------
67:
68: Up to and including release 6.7, PCRE worked by running a very degenerate first
69: pass to calculate a maximum store size, and then a second pass to do the real
70: compile - which might use a bit less than the predicted amount of memory. The
71: idea was that this would turn out faster than the Henry Spencer code because
72: the first pass is degenerate and the second pass can just store stuff straight
73: into the vector, which it knows is big enough.
74:
75:
76: Computing the memory requirement: how it is
77: -------------------------------------------
78:
79: By the time I was working on a potential 6.8 release, the degenerate first pass
80: had become very complicated and hard to maintain. Indeed one of the early
81: things I did for 6.8 was to fix Yet Another Bug in the memory computation. Then
82: I had a flash of inspiration as to how I could run the real compile function in
83: a "fake" mode that enables it to compute how much memory it would need, while
84: actually only ever using a few hundred bytes of working memory, and without too
85: many tests of the mode that might slow it down. So I refactored the compiling
86: functions to work this way. This got rid of about 600 lines of source. It
87: should make future maintenance and development easier. As this was such a major
88: change, I never released 6.8, instead upping the number to 7.0 (other quite
89: major changes were also present in the 7.0 release).
90:
91: A side effect of this work was that the previous limit of 200 on the nesting
92: depth of parentheses was removed. However, there is a downside: pcre_compile()
93: runs more slowly than before (30% or more, depending on the pattern) because it
94: is doing a full analysis of the pattern. My hope was that this would not be a
95: big issue, and in the event, nobody has commented on it.
96:
97:
98: Traditional matching function
99: -----------------------------
100:
101: The "traditional", and original, matching function is called pcre_exec(), and
102: it implements an NFA algorithm, similar to the original Henry Spencer algorithm
103: and the way that Perl works. This is not surprising, since it is intended to be
104: as compatible with Perl as possible. This is the function most users of PCRE
105: will use most of the time. From release 8.20, if PCRE is compiled with
106: just-in-time (JIT) support, and studying a compiled pattern with JIT is
107: successful, the JIT code is run instead of the normal pcre_exec() code, but the
108: result is the same.
109:
110:
111: Supplementary matching function
112: -------------------------------
113:
114: From PCRE 6.0, there is also a supplementary matching function called
115: pcre_dfa_exec(). This implements a DFA matching algorithm that searches
116: simultaneously for all possible matches that start at one point in the subject
117: string. (Going back to my roots: see Historical Note 1 above.) This function
118: intreprets the same compiled pattern data as pcre_exec(); however, not all the
119: facilities are available, and those that are do not always work in quite the
120: same way. See the user documentation for details.
121:
122: The algorithm that is used for pcre_dfa_exec() is not a traditional FSM,
123: because it may have a number of states active at one time. More work would be
124: needed at compile time to produce a traditional FSM where only one state is
125: ever active at once. I believe some other regex matchers work this way.
126:
127:
128: Changeable options
129: ------------------
130:
131: The /i, /m, or /s options (PCRE_CASELESS, PCRE_MULTILINE, PCRE_DOTALL) may
132: change in the middle of patterns. From PCRE 8.13, their processing is handled
133: entirely at compile time by generating different opcodes for the different
134: settings. The runtime functions do not need to keep track of an options state
135: any more.
136:
137:
138: Format of compiled patterns
139: ---------------------------
140:
1.1.1.2 misho 141: The compiled form of a pattern is a vector of units (bytes in 8-bit mode, or
1.1.1.4 ! misho 142: shorts in 16-bit mode, 32-bit unsigned integers in 32-bit mode), containing
! 143: items of variable length. The first unit in an item contains an opcode, and
! 144: the length of the item is either implicit in the opcode or contained in the
! 145: data that follows it.
1.1.1.2 misho 146:
147: In many cases listed below, LINK_SIZE data values are specified for offsets
148: within the compiled pattern. LINK_SIZE always specifies a number of bytes. The
149: default value for LINK_SIZE is 2, but PCRE can be compiled to use 3-byte or
150: 4-byte values for these offsets, although this impairs the performance. (3-byte
151: LINK_SIZE values are available only in 8-bit mode.) Specifing a LINK_SIZE
152: larger than 2 is necessary only when patterns whose compiled length is greater
153: than 64K are going to be processed. In this description, we assume the "normal"
154: compilation options. Data values that are counts (e.g. for quantifiers) are
155: always just two bytes long (one short in 16-bit mode).
1.1 misho 156:
157: Opcodes with no following data
158: ------------------------------
159:
1.1.1.2 misho 160: These items are all just one unit long
1.1 misho 161:
162: OP_END end of pattern
163: OP_ANY match any one character other than newline
164: OP_ALLANY match any one character, including newline
165: OP_ANYBYTE match any single byte, even in UTF-8 mode
166: OP_SOD match start of data: \A
167: OP_SOM, start of match (subject + offset): \G
168: OP_SET_SOM, set start of match (\K)
169: OP_CIRC ^ (start of data)
170: OP_CIRCM ^ multiline mode (start of data or after newline)
171: OP_NOT_WORD_BOUNDARY \W
172: OP_WORD_BOUNDARY \w
173: OP_NOT_DIGIT \D
174: OP_DIGIT \d
175: OP_NOT_HSPACE \H
176: OP_HSPACE \h
177: OP_NOT_WHITESPACE \S
178: OP_WHITESPACE \s
179: OP_NOT_VSPACE \V
180: OP_VSPACE \v
181: OP_NOT_WORDCHAR \W
182: OP_WORDCHAR \w
183: OP_EODN match end of data or \n at end: \Z
184: OP_EOD match end of data: \z
185: OP_DOLL $ (end of data, or before final newline)
186: OP_DOLLM $ multiline mode (end of data or before newline)
187: OP_EXTUNI match an extended Unicode character
188: OP_ANYNL match any Unicode newline sequence
189:
190: OP_ACCEPT ) These are Perl 5.10's "backtracking control
191: OP_COMMIT ) verbs". If OP_ACCEPT is inside capturing
192: OP_FAIL ) parentheses, it may be preceded by one or more
193: OP_PRUNE ) OP_CLOSE, followed by a 2-byte number,
194: OP_SKIP ) indicating which parentheses must be closed.
195:
196:
197: Backtracking control verbs with (optional) data
198: -----------------------------------------------
199:
200: (*THEN) without an argument generates the opcode OP_THEN and no following data.
1.1.1.2 misho 201: OP_MARK is followed by the mark name, preceded by a one-unit length, and
1.1 misho 202: followed by a binary zero. For (*PRUNE), (*SKIP), and (*THEN) with arguments,
203: the opcodes OP_PRUNE_ARG, OP_SKIP_ARG, and OP_THEN_ARG are used, with the name
204: following in the same format.
205:
206:
207: Matching literal characters
208: ---------------------------
209:
210: The OP_CHAR opcode is followed by a single character that is to be matched
1.1.1.2 misho 211: casefully. For caseless matching, OP_CHARI is used. In UTF-8 or UTF-16 modes,
1.1.1.4 ! misho 212: the character may be more than one unit long. In UTF-32 mode, characters
! 213: are always exactly one unit long.
1.1 misho 214:
215:
216: Repeating single characters
217: ---------------------------
218:
1.1.1.2 misho 219: The common repeats (*, +, ?), when applied to a single character, use the
1.1 misho 220: following opcodes, which come in caseful and caseless versions:
221:
222: Caseful Caseless
223: OP_STAR OP_STARI
224: OP_MINSTAR OP_MINSTARI
225: OP_POSSTAR OP_POSSTARI
226: OP_PLUS OP_PLUSI
227: OP_MINPLUS OP_MINPLUSI
228: OP_POSPLUS OP_POSPLUSI
229: OP_QUERY OP_QUERYI
230: OP_MINQUERY OP_MINQUERYI
231: OP_POSQUERY OP_POSQUERYI
232:
1.1.1.2 misho 233: Each opcode is followed by the character that is to be repeated. In ASCII mode,
1.1.1.4 ! misho 234: these are two-unit items; in UTF-8 or UTF-16 modes, the length is variable; in
! 235: UTF-32 mode these are one-unit items.
1.1.1.2 misho 236: Those with "MIN" in their names are the minimizing versions. Those with "POS"
237: in their names are possessive versions. Other repeats make use of these
238: opcodes:
1.1 misho 239:
240: Caseful Caseless
241: OP_UPTO OP_UPTOI
242: OP_MINUPTO OP_MINUPTOI
243: OP_POSUPTO OP_POSUPTOI
244: OP_EXACT OP_EXACTI
245:
1.1.1.2 misho 246: Each of these is followed by a two-byte (one short) count (most significant
247: byte first in 8-bit mode) and then the repeated character. OP_UPTO matches from
248: 0 to the given number. A repeat with a non-zero minimum and a fixed maximum is
249: coded as an OP_EXACT followed by an OP_UPTO (or OP_MINUPTO or OPT_POSUPTO).
1.1 misho 250:
251:
252: Repeating character types
253: -------------------------
254:
255: Repeats of things like \d are done exactly as for single characters, except
256: that instead of a character, the opcode for the type is stored in the data
1.1.1.2 misho 257: unit. The opcodes are:
1.1 misho 258:
259: OP_TYPESTAR
260: OP_TYPEMINSTAR
261: OP_TYPEPOSSTAR
262: OP_TYPEPLUS
263: OP_TYPEMINPLUS
264: OP_TYPEPOSPLUS
265: OP_TYPEQUERY
266: OP_TYPEMINQUERY
267: OP_TYPEPOSQUERY
268: OP_TYPEUPTO
269: OP_TYPEMINUPTO
270: OP_TYPEPOSUPTO
271: OP_TYPEEXACT
272:
273:
274: Match by Unicode property
275: -------------------------
276:
277: OP_PROP and OP_NOTPROP are used for positive and negative matches of a
278: character by testing its Unicode property (the \p and \P escape sequences).
1.1.1.2 misho 279: Each is followed by two units that encode the desired property as a type and a
1.1 misho 280: value.
281:
1.1.1.2 misho 282: Repeats of these items use the OP_TYPESTAR etc. set of opcodes, followed by
283: three units: OP_PROP or OP_NOTPROP, and then the desired property type and
1.1 misho 284: value.
285:
286:
287: Character classes
288: -----------------
289:
1.1.1.2 misho 290: If there is only one character in the class, OP_CHAR or OP_CHARI is used for a
291: positive class, and OP_NOT or OP_NOTI for a negative one (that is, for
1.1.1.3 misho 292: something like [^a]).
1.1.1.2 misho 293:
294: Another set of 13 repeating opcodes (called OP_NOTSTAR etc.) are used for
295: repeated, negated, single-character classes. The normal single-character
296: opcodes (OP_STAR, etc.) are used for repeated positive single-character
297: classes.
1.1 misho 298:
299: When there is more than one character in a class and all the characters are
300: less than 256, OP_CLASS is used for a positive class, and OP_NCLASS for a
1.1.1.2 misho 301: negative one. In either case, the opcode is followed by a 32-byte (16-short)
302: bit map containing a 1 bit for every character that is acceptable. The bits are
303: counted from the least significant end of each unit. In caseless mode, bits for
304: both cases are set.
1.1 misho 305:
1.1.1.4 ! misho 306: The reason for having both OP_CLASS and OP_NCLASS is so that, in UTF-8/16/32 mode,
1.1.1.2 misho 307: subject characters with values greater than 255 can be handled correctly. For
1.1 misho 308: OP_CLASS they do not match, whereas for OP_NCLASS they do.
309:
1.1.1.2 misho 310: For classes containing characters with values greater than 255, OP_XCLASS is
311: used. It optionally uses a bit map (if any characters lie within it), followed
312: by a list of pairs (for a range) and single characters. In caseless mode, both
313: cases are explicitly listed. There is a flag character than indicates whether
314: it is a positive or a negative class.
1.1 misho 315:
316:
317: Back references
318: ---------------
319:
1.1.1.2 misho 320: OP_REF (caseful) or OP_REFI (caseless) is followed by two bytes (one short)
321: containing the reference number.
1.1 misho 322:
323:
324: Repeating character classes and back references
325: -----------------------------------------------
326:
327: Single-character classes are handled specially (see above). This section
328: applies to OP_CLASS and OP_REF[I]. In both cases, the repeat information
329: follows the base item. The matching code looks at the following opcode to see
330: if it is one of
331:
332: OP_CRSTAR
333: OP_CRMINSTAR
334: OP_CRPLUS
335: OP_CRMINPLUS
336: OP_CRQUERY
337: OP_CRMINQUERY
338: OP_CRRANGE
339: OP_CRMINRANGE
340:
1.1.1.2 misho 341: All but the last two are just single-unit items. The others are followed by
342: four bytes (two shorts) of data, comprising the minimum and maximum repeat
343: counts. There are no special possessive opcodes for these repeats; a possessive
344: repeat is compiled into an atomic group.
1.1 misho 345:
346:
347: Brackets and alternation
348: ------------------------
349:
350: A pair of non-capturing (round) brackets is wrapped round each expression at
351: compile time, so alternation always happens in the context of brackets.
352:
353: [Note for North Americans: "bracket" to some English speakers, including
1.1.1.2 misho 354: myself, can be round, square, curly, or pointy. Hence this usage rather than
355: "parentheses".]
1.1 misho 356:
357: Non-capturing brackets use the opcode OP_BRA. Originally PCRE was limited to 99
358: capturing brackets and it used a different opcode for each one. From release
359: 3.5, the limit was removed by putting the bracket number into the data for
360: higher-numbered brackets. From release 7.0 all capturing brackets are handled
361: this way, using the single opcode OP_CBRA.
362:
363: A bracket opcode is followed by LINK_SIZE bytes which give the offset to the
364: next alternative OP_ALT or, if there aren't any branches, to the matching
365: OP_KET opcode. Each OP_ALT is followed by LINK_SIZE bytes giving the offset to
366: the next one, or to the OP_KET opcode. For capturing brackets, the bracket
1.1.1.2 misho 367: number immediately follows the offset, always as a 2-byte (one short) item.
1.1 misho 368:
1.1.1.2 misho 369: OP_KET is used for subpatterns that do not repeat indefinitely, and
1.1 misho 370: OP_KETRMIN and OP_KETRMAX are used for indefinite repetitions, minimally or
371: maximally respectively (see below for possessive repetitions). All three are
372: followed by LINK_SIZE bytes giving (as a positive number) the offset back to
373: the matching bracket opcode.
374:
375: If a subpattern is quantified such that it is permitted to match zero times, it
376: is preceded by one of OP_BRAZERO, OP_BRAMINZERO, or OP_SKIPZERO. These are
1.1.1.2 misho 377: single-unit opcodes that tell the matcher that skipping the following
1.1 misho 378: subpattern entirely is a valid branch. In the case of the first two, not
379: skipping the pattern is also valid (greedy and non-greedy). The third is used
380: when a pattern has the quantifier {0,0}. It cannot be entirely discarded,
381: because it may be called as a subroutine from elsewhere in the regex.
382:
383: A subpattern with an indefinite maximum repetition is replicated in the
384: compiled data its minimum number of times (or once with OP_BRAZERO if the
385: minimum is zero), with the final copy terminating with OP_KETRMIN or OP_KETRMAX
386: as appropriate.
387:
388: A subpattern with a bounded maximum repetition is replicated in a nested
389: fashion up to the maximum number of times, with OP_BRAZERO or OP_BRAMINZERO
390: before each replication after the minimum, so that, for example, (abc){2,5} is
391: compiled as (abc)(abc)((abc)((abc)(abc)?)?)?, except that each bracketed group
392: has the same number.
393:
394: When a repeated subpattern has an unbounded upper limit, it is checked to see
395: whether it could match an empty string. If this is the case, the opcode in the
396: final replication is changed to OP_SBRA or OP_SCBRA. This tells the matcher
397: that it needs to check for matching an empty string when it hits OP_KETRMIN or
398: OP_KETRMAX, and if so, to break the loop.
399:
400: Possessive brackets
401: -------------------
402:
403: When a repeated group (capturing or non-capturing) is marked as possessive by
404: the "+" notation, e.g. (abc)++, different opcodes are used. Their names all
405: have POS on the end, e.g. OP_BRAPOS instead of OP_BRA and OP_SCPBRPOS instead
406: of OP_SCBRA. The end of such a group is marked by OP_KETRPOS. If the minimum
407: repetition is zero, the group is preceded by OP_BRAPOSZERO.
408:
409:
410: Assertions
411: ----------
412:
413: Forward assertions are just like other subpatterns, but starting with one of
414: the opcodes OP_ASSERT or OP_ASSERT_NOT. Backward assertions use the opcodes
415: OP_ASSERTBACK and OP_ASSERTBACK_NOT, and the first opcode inside the assertion
1.1.1.2 misho 416: is OP_REVERSE, followed by a two byte (one short) count of the number of
417: characters to move back the pointer in the subject string. In ASCII mode, the
418: count is a number of units, but in UTF-8/16 mode each character may occupy more
1.1.1.4 ! misho 419: than one unit; in UTF-32 mode each character occupies exactly one unit.
! 420: A separate count is present in each alternative of a lookbehind
1.1.1.2 misho 421: assertion, allowing them to have different fixed lengths.
1.1 misho 422:
423:
424: Once-only (atomic) subpatterns
425: ------------------------------
426:
427: These are also just like other subpatterns, but they start with the opcode
428: OP_ONCE. The check for matching an empty string in an unbounded repeat is
429: handled entirely at runtime, so there is just this one opcode.
430:
431:
432: Conditional subpatterns
433: -----------------------
434:
435: These are like other subpatterns, but they start with the opcode OP_COND, or
436: OP_SCOND for one that might match an empty string in an unbounded repeat. If
437: the condition is a back reference, this is stored at the start of the
1.1.1.2 misho 438: subpattern using the opcode OP_CREF followed by two bytes (one short)
439: containing the reference number. OP_NCREF is used instead if the reference was
440: generated by name (so that the runtime code knows to check for duplicate
441: names).
1.1 misho 442:
443: If the condition is "in recursion" (coded as "(?(R)"), or "in recursion of
444: group x" (coded as "(?(Rx)"), the group number is stored at the start of the
445: subpattern using the opcode OP_RREF or OP_NRREF (cf OP_NCREF), and a value of
1.1.1.2 misho 446: zero for "the whole pattern". For a DEFINE condition, just the single unit
1.1 misho 447: OP_DEF is used (it has no associated data). Otherwise, a conditional subpattern
448: always starts with one of the assertions.
449:
450:
451: Recursion
452: ---------
453:
454: Recursion either matches the current regex, or some subexpression. The opcode
455: OP_RECURSE is followed by an value which is the offset to the starting bracket
456: from the start of the whole pattern. From release 6.5, OP_RECURSE is
457: automatically wrapped inside OP_ONCE brackets (because otherwise some patterns
458: broke it). OP_RECURSE is also used for "subroutine" calls, even though they
459: are not strictly a recursion.
460:
461:
462: Callout
463: -------
464:
1.1.1.2 misho 465: OP_CALLOUT is followed by one unit of data that holds a callout number in the
1.1 misho 466: range 0 to 254 for manual callouts, or 255 for an automatic callout. In both
1.1.1.2 misho 467: cases there follows a two-byte (one short) value giving the offset in the
468: pattern to the start of the following item, and another two-byte (one short)
469: item giving the length of the next item.
1.1 misho 470:
471:
472: Philip Hazel
1.1.1.3 misho 473: February 2012
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to HACKING CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / pcre