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