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