This is a live mirror of the Perl 5 development currently hosted at https://github.com/perl/perl5
perl 3.0: (no announcement message available)
[perl5.git] / regcomp.h
CommitLineData
a687059c
LW
1/* $Header: regcomp.h,v 3.0 89/10/18 15:22:39 lwall Locked $
2 *
3 * $Log: regcomp.h,v $
4 * Revision 3.0 89/10/18 15:22:39 lwall
5 * 3.0 baseline
6 *
7 */
8
9/*
10 * The "internal use only" fields in regexp.h are present to pass info from
11 * compile to execute that permits the execute phase to run lots faster on
12 * simple cases. They are:
13 *
14 * regstart str that must begin a match; Nullch if none obvious
15 * reganch is the match anchored (at beginning-of-line only)?
16 * regmust string (pointer into program) that match must include, or NULL
17 * [regmust changed to STR* for bminstr()--law]
18 * regmlen length of regmust string
19 * [regmlen not used currently]
20 *
21 * Regstart and reganch permit very fast decisions on suitable starting points
22 * for a match, cutting down the work a lot. Regmust permits fast rejection
23 * of lines that cannot possibly match. The regmust tests are costly enough
24 * that regcomp() supplies a regmust only if the r.e. contains something
25 * potentially expensive (at present, the only such thing detected is * or +
26 * at the start of the r.e., which can involve a lot of backup). Regmlen is
27 * supplied because the test in regexec() needs it and regcomp() is computing
28 * it anyway.
29 * [regmust is now supplied always. The tests that use regmust have a
30 * heuristic that disables the test if it usually matches.]
31 *
32 * [In fact, we now use regmust in many cases to locate where the search
33 * starts in the string, so if regback is >= 0, the regmust search is never
34 * wasted effort. The regback variable says how many characters back from
35 * where regmust matched is the earliest possible start of the match.
36 * For instance, /[a-z].foo/ has a regmust of 'foo' and a regback of 2.]
37 */
38
39/*
40 * Structure for regexp "program". This is essentially a linear encoding
41 * of a nondeterministic finite-state machine (aka syntax charts or
42 * "railroad normal form" in parsing technology). Each node is an opcode
43 * plus a "next" pointer, possibly plus an operand. "Next" pointers of
44 * all nodes except BRANCH implement concatenation; a "next" pointer with
45 * a BRANCH on both ends of it is connecting two alternatives. (Here we
46 * have one of the subtle syntax dependencies: an individual BRANCH (as
47 * opposed to a collection of them) is never concatenated with anything
48 * because of operator precedence.) The operand of some types of node is
49 * a literal string; for others, it is a node leading into a sub-FSM. In
50 * particular, the operand of a BRANCH node is the first node of the branch.
51 * (NB this is *not* a tree structure: the tail of the branch connects
52 * to the thing following the set of BRANCHes.) The opcodes are:
53 */
54
55/* definition number opnd? meaning */
56#define END 0 /* no End of program. */
57#define BOL 1 /* no Match "" at beginning of line. */
58#define EOL 2 /* no Match "" at end of line. */
59#define ANY 3 /* no Match any one character. */
60#define ANYOF 4 /* str Match any character in this string. */
61#define ANYBUT 5 /* str Match any character not in this string. */
62#define BRANCH 6 /* node Match this alternative, or the next... */
63#define BACK 7 /* no Match "", "next" ptr points backward. */
64#define EXACTLY 8 /* str Match this string (preceded by length). */
65#define NOTHING 9 /* no Match empty string. */
66#define STAR 10 /* node Match this (simple) thing 0 or more times. */
67#define PLUS 11 /* node Match this (simple) thing 1 or more times. */
68#define ALNUM 12 /* no Match any alphanumeric character */
69#define NALNUM 13 /* no Match any non-alphanumeric character */
70#define BOUND 14 /* no Match "" at any word boundary */
71#define NBOUND 15 /* no Match "" at any word non-boundary */
72#define SPACE 16 /* no Match any whitespace character */
73#define NSPACE 17 /* no Match any non-whitespace character */
74#define DIGIT 18 /* no Match any numeric character */
75#define NDIGIT 19 /* no Match any non-numeric character */
76#define REF 20 /* no Match some already matched string */
77#define OPEN 30 /* no Mark this point in input as start of #n. */
78 /* OPEN+1 is number 1, etc. */
79#define CLOSE 40 /* no Analogous to OPEN. */
80/* CLOSE must be last one! see regmust finder */
81
82/*
83 * Opcode notes:
84 *
85 * BRANCH The set of branches constituting a single choice are hooked
86 * together with their "next" pointers, since precedence prevents
87 * anything being concatenated to any individual branch. The
88 * "next" pointer of the last BRANCH in a choice points to the
89 * thing following the whole choice. This is also where the
90 * final "next" pointer of each individual branch points; each
91 * branch starts with the operand node of a BRANCH node.
92 *
93 * BACK Normal "next" pointers all implicitly point forward; BACK
94 * exists to make loop structures possible.
95 *
96 * STAR,PLUS '?', and complex '*' and '+', are implemented as circular
97 * BRANCH structures using BACK. Simple cases (one character
98 * per match) are implemented with STAR and PLUS for speed
99 * and to minimize recursive plunges.
100 *
101 * OPEN,CLOSE ...are numbered at compile time.
102 */
103
104/* The following have no fixed length. */
105#ifndef DOINIT
106extern char varies[];
107#else
108char varies[] = {BRANCH,BACK,STAR,PLUS,
109 REF+1,REF+2,REF+3,REF+4,REF+5,REF+6,REF+7,REF+8,REF+9,0};
110#endif
111
112/* The following always have a length of 1. */
113#ifndef DOINIT
114extern char simple[];
115#else
116char simple[] = {ANY,ANYOF,ANYBUT,ALNUM,NALNUM,SPACE,NSPACE,DIGIT,NDIGIT,0};
117#endif
118
119EXT char regdummy;
120
121/*
122 * A node is one char of opcode followed by two chars of "next" pointer.
123 * "Next" pointers are stored as two 8-bit pieces, high order first. The
124 * value is a positive offset from the opcode of the node containing it.
125 * An operand, if any, simply follows the node. (Note that much of the
126 * code generation knows about this implicit relationship.)
127 *
128 * Using two bytes for the "next" pointer is vast overkill for most things,
129 * but allows patterns to get big without disasters.
130 *
131 * [If REGALIGN is defined, the "next" pointer is always aligned on an even
132 * boundary, and reads the offset directly as a short. Also, there is no
133 * special test to reverse the sign of BACK pointers since the offset is
134 * stored negative.]
135 */
136
137#ifndef gould
138#ifndef cray
139#define REGALIGN
140#endif
141#endif
142
143#define OP(p) (*(p))
144
145#ifndef lint
146#ifdef REGALIGN
147#define NEXT(p) (*(short*)(p+1))
148#else
149#define NEXT(p) (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
150#endif
151#else /* lint */
152#define NEXT(p) 0
153#endif /* lint */
154
155#define OPERAND(p) ((p) + 3)
156
157#ifdef REGALIGN
158#define NEXTOPER(p) ((p) + 4)
159#else
160#define NEXTOPER(p) ((p) + 3)
161#endif
162
163#define MAGIC 0234
164
165/*
166 * Utility definitions.
167 */
168#ifndef lint
169#ifndef CHARBITS
170#define UCHARAT(p) ((int)*(unsigned char *)(p))
171#else
172#define UCHARAT(p) ((int)*(p)&CHARBITS)
173#endif
174#else /* lint */
175#define UCHARAT(p) regdummy
176#endif /* lint */
177
178#define FAIL(m) fatal("/%s/: %s",regprecomp,m)
179
180char *regnext();
181#ifdef DEBUGGING
182void regdump();
183char *regprop();
184#endif
185