/[dtapublic]/projs/trunk/shared_source/c_tcl_base_7_5_w_mods/regcomp.c
ViewVC logotype

Diff of /projs/trunk/shared_source/c_tcl_base_7_5_w_mods/regcomp.c

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 70 by dashley, Mon Oct 31 00:57:34 2016 UTC revision 71 by dashley, Sat Nov 5 11:07:06 2016 UTC
# Line 1  Line 1 
1  /* $Header$ */  /* $Header$ */
2  /*  /*
3   * re_*comp and friends - compile REs   * re_*comp and friends - compile REs
4   * This file #includes several others (see the bottom).   * This file #includes several others (see the bottom).
5   *   *
6   * Copyright (c) 1998, 1999 Henry Spencer.  All rights reserved.   * Copyright (c) 1998, 1999 Henry Spencer.  All rights reserved.
7   *   *
8   * Development of this software was funded, in part, by Cray Research Inc.,   * Development of this software was funded, in part, by Cray Research Inc.,
9   * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics   * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
10   * Corporation, none of whom are responsible for the results.  The author   * Corporation, none of whom are responsible for the results.  The author
11   * thanks all of them.   * thanks all of them.
12   *   *
13   * Redistribution and use in source and binary forms -- with or without   * Redistribution and use in source and binary forms -- with or without
14   * modification -- are permitted for any purpose, provided that   * modification -- are permitted for any purpose, provided that
15   * redistributions in source form retain this entire copyright notice and   * redistributions in source form retain this entire copyright notice and
16   * indicate the origin and nature of any modifications.   * indicate the origin and nature of any modifications.
17   *   *
18   * I'd appreciate being given credit for this package in the documentation   * I'd appreciate being given credit for this package in the documentation
19   * of software which uses it, but that is not a requirement.   * of software which uses it, but that is not a requirement.
20   *   *
21   * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,   * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
22   * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY   * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
23   * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL   * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
24   * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,   * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
25   * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,   * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
26   * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;   * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
27   * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,   * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
28   * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR   * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
29   * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF   * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
30   * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.   * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31   *   *
32   */   */
33    
34  #include "regguts.h"  #include "regguts.h"
35    
36  /*  /*
37   * forward declarations, up here so forward datatypes etc. are defined early   * forward declarations, up here so forward datatypes etc. are defined early
38   */   */
39  /* =====^!^===== begin forwards =====^!^===== */  /* =====^!^===== begin forwards =====^!^===== */
40  /* automatically gathered by fwd; do not hand-edit */  /* automatically gathered by fwd; do not hand-edit */
41  /* === regcomp.c === */  /* === regcomp.c === */
42  int compile _ANSI_ARGS_((regex_t *, CONST chr *, size_t, int));  int compile _ANSI_ARGS_((regex_t *, CONST chr *, size_t, int));
43  static VOID moresubs _ANSI_ARGS_((struct vars *, int));  static VOID moresubs _ANSI_ARGS_((struct vars *, int));
44  static int freev _ANSI_ARGS_((struct vars *, int));  static int freev _ANSI_ARGS_((struct vars *, int));
45  static VOID makesearch _ANSI_ARGS_((struct vars *, struct nfa *));  static VOID makesearch _ANSI_ARGS_((struct vars *, struct nfa *));
46  static struct subre *parse _ANSI_ARGS_((struct vars *, int, int, struct state *, struct state *));  static struct subre *parse _ANSI_ARGS_((struct vars *, int, int, struct state *, struct state *));
47  static struct subre *parsebranch _ANSI_ARGS_((struct vars *, int, int, struct state *, struct state *, int));  static struct subre *parsebranch _ANSI_ARGS_((struct vars *, int, int, struct state *, struct state *, int));
48  static VOID parseqatom _ANSI_ARGS_((struct vars *, int, int, struct state *, struct state *, struct subre *));  static VOID parseqatom _ANSI_ARGS_((struct vars *, int, int, struct state *, struct state *, struct subre *));
49  static VOID nonword _ANSI_ARGS_((struct vars *, int, struct state *, struct state *));  static VOID nonword _ANSI_ARGS_((struct vars *, int, struct state *, struct state *));
50  static VOID word _ANSI_ARGS_((struct vars *, int, struct state *, struct state *));  static VOID word _ANSI_ARGS_((struct vars *, int, struct state *, struct state *));
51  static int scannum _ANSI_ARGS_((struct vars *));  static int scannum _ANSI_ARGS_((struct vars *));
52  static VOID repeat _ANSI_ARGS_((struct vars *, struct state *, struct state *, int, int));  static VOID repeat _ANSI_ARGS_((struct vars *, struct state *, struct state *, int, int));
53  static VOID bracket _ANSI_ARGS_((struct vars *, struct state *, struct state *));  static VOID bracket _ANSI_ARGS_((struct vars *, struct state *, struct state *));
54  static VOID cbracket _ANSI_ARGS_((struct vars *, struct state *, struct state *));  static VOID cbracket _ANSI_ARGS_((struct vars *, struct state *, struct state *));
55  static VOID brackpart _ANSI_ARGS_((struct vars *, struct state *, struct state *));  static VOID brackpart _ANSI_ARGS_((struct vars *, struct state *, struct state *));
56  static chr *scanplain _ANSI_ARGS_((struct vars *));  static chr *scanplain _ANSI_ARGS_((struct vars *));
57  static VOID leaders _ANSI_ARGS_((struct vars *, struct cvec *));  static VOID leaders _ANSI_ARGS_((struct vars *, struct cvec *));
58  static VOID onechr _ANSI_ARGS_((struct vars *, pchr, struct state *, struct state *));  static VOID onechr _ANSI_ARGS_((struct vars *, pchr, struct state *, struct state *));
59  static VOID dovec _ANSI_ARGS_((struct vars *, struct cvec *, struct state *, struct state *));  static VOID dovec _ANSI_ARGS_((struct vars *, struct cvec *, struct state *, struct state *));
60  static celt nextleader _ANSI_ARGS_((struct vars *, pchr, pchr));  static celt nextleader _ANSI_ARGS_((struct vars *, pchr, pchr));
61  static VOID wordchrs _ANSI_ARGS_((struct vars *));  static VOID wordchrs _ANSI_ARGS_((struct vars *));
62  static struct subre *subre _ANSI_ARGS_((struct vars *, int, int, struct state *, struct state *));  static struct subre *subre _ANSI_ARGS_((struct vars *, int, int, struct state *, struct state *));
63  static VOID freesubre _ANSI_ARGS_((struct vars *, struct subre *));  static VOID freesubre _ANSI_ARGS_((struct vars *, struct subre *));
64  static VOID freesrnode _ANSI_ARGS_((struct vars *, struct subre *));  static VOID freesrnode _ANSI_ARGS_((struct vars *, struct subre *));
65  static VOID optst _ANSI_ARGS_((struct vars *, struct subre *));  static VOID optst _ANSI_ARGS_((struct vars *, struct subre *));
66  static int numst _ANSI_ARGS_((struct subre *, int));  static int numst _ANSI_ARGS_((struct subre *, int));
67  static VOID markst _ANSI_ARGS_((struct subre *));  static VOID markst _ANSI_ARGS_((struct subre *));
68  static VOID cleanst _ANSI_ARGS_((struct vars *));  static VOID cleanst _ANSI_ARGS_((struct vars *));
69  static long nfatree _ANSI_ARGS_((struct vars *, struct subre *, FILE *));  static long nfatree _ANSI_ARGS_((struct vars *, struct subre *, FILE *));
70  static long nfanode _ANSI_ARGS_((struct vars *, struct subre *, FILE *));  static long nfanode _ANSI_ARGS_((struct vars *, struct subre *, FILE *));
71  static int newlacon _ANSI_ARGS_((struct vars *, struct state *, struct state *, int));  static int newlacon _ANSI_ARGS_((struct vars *, struct state *, struct state *, int));
72  static VOID freelacons _ANSI_ARGS_((struct subre *, int));  static VOID freelacons _ANSI_ARGS_((struct subre *, int));
73  static VOID rfree _ANSI_ARGS_((regex_t *));  static VOID rfree _ANSI_ARGS_((regex_t *));
74  static VOID dump _ANSI_ARGS_((regex_t *, FILE *));  static VOID dump _ANSI_ARGS_((regex_t *, FILE *));
75  static VOID dumpst _ANSI_ARGS_((struct subre *, FILE *, int));  static VOID dumpst _ANSI_ARGS_((struct subre *, FILE *, int));
76  static VOID stdump _ANSI_ARGS_((struct subre *, FILE *, int));  static VOID stdump _ANSI_ARGS_((struct subre *, FILE *, int));
77  static char *stid _ANSI_ARGS_((struct subre *, char *, size_t));  static char *stid _ANSI_ARGS_((struct subre *, char *, size_t));
78  /* === regc_lex.c === */  /* === regc_lex.c === */
79  static VOID lexstart _ANSI_ARGS_((struct vars *));  static VOID lexstart _ANSI_ARGS_((struct vars *));
80  static VOID prefixes _ANSI_ARGS_((struct vars *));  static VOID prefixes _ANSI_ARGS_((struct vars *));
81  static VOID lexnest _ANSI_ARGS_((struct vars *, chr *, chr *));  static VOID lexnest _ANSI_ARGS_((struct vars *, chr *, chr *));
82  static VOID lexword _ANSI_ARGS_((struct vars *));  static VOID lexword _ANSI_ARGS_((struct vars *));
83  static int next _ANSI_ARGS_((struct vars *));  static int next _ANSI_ARGS_((struct vars *));
84  static int lexescape _ANSI_ARGS_((struct vars *));  static int lexescape _ANSI_ARGS_((struct vars *));
85  static chr lexdigits _ANSI_ARGS_((struct vars *, int, int, int));  static chr lexdigits _ANSI_ARGS_((struct vars *, int, int, int));
86  static int brenext _ANSI_ARGS_((struct vars *, pchr));  static int brenext _ANSI_ARGS_((struct vars *, pchr));
87  static VOID skip _ANSI_ARGS_((struct vars *));  static VOID skip _ANSI_ARGS_((struct vars *));
88  static chr newline _ANSI_ARGS_((NOPARMS));  static chr newline _ANSI_ARGS_((NOPARMS));
89  #ifdef REG_DEBUG  #ifdef REG_DEBUG
90  static chr *ch _ANSI_ARGS_((NOPARMS));  static chr *ch _ANSI_ARGS_((NOPARMS));
91  #endif  #endif
92  static chr chrnamed _ANSI_ARGS_((struct vars *, chr *, chr *, pchr));  static chr chrnamed _ANSI_ARGS_((struct vars *, chr *, chr *, pchr));
93  /* === regc_color.c === */  /* === regc_color.c === */
94  static VOID initcm _ANSI_ARGS_((struct vars *, struct colormap *));  static VOID initcm _ANSI_ARGS_((struct vars *, struct colormap *));
95  static VOID freecm _ANSI_ARGS_((struct colormap *));  static VOID freecm _ANSI_ARGS_((struct colormap *));
96  static VOID cmtreefree _ANSI_ARGS_((struct colormap *, union tree *, int));  static VOID cmtreefree _ANSI_ARGS_((struct colormap *, union tree *, int));
97  static color setcolor _ANSI_ARGS_((struct colormap *, pchr, pcolor));  static color setcolor _ANSI_ARGS_((struct colormap *, pchr, pcolor));
98  static color maxcolor _ANSI_ARGS_((struct colormap *));  static color maxcolor _ANSI_ARGS_((struct colormap *));
99  static color newcolor _ANSI_ARGS_((struct colormap *));  static color newcolor _ANSI_ARGS_((struct colormap *));
100  static VOID freecolor _ANSI_ARGS_((struct colormap *, pcolor));  static VOID freecolor _ANSI_ARGS_((struct colormap *, pcolor));
101  static color pseudocolor _ANSI_ARGS_((struct colormap *));  static color pseudocolor _ANSI_ARGS_((struct colormap *));
102  static color subcolor _ANSI_ARGS_((struct colormap *, pchr c));  static color subcolor _ANSI_ARGS_((struct colormap *, pchr c));
103  static color newsub _ANSI_ARGS_((struct colormap *, pcolor));  static color newsub _ANSI_ARGS_((struct colormap *, pcolor));
104  static VOID subrange _ANSI_ARGS_((struct vars *, pchr, pchr, struct state *, struct state *));  static VOID subrange _ANSI_ARGS_((struct vars *, pchr, pchr, struct state *, struct state *));
105  static VOID subblock _ANSI_ARGS_((struct vars *, pchr, struct state *, struct state *));  static VOID subblock _ANSI_ARGS_((struct vars *, pchr, struct state *, struct state *));
106  static VOID okcolors _ANSI_ARGS_((struct nfa *, struct colormap *));  static VOID okcolors _ANSI_ARGS_((struct nfa *, struct colormap *));
107  static VOID colorchain _ANSI_ARGS_((struct colormap *, struct arc *));  static VOID colorchain _ANSI_ARGS_((struct colormap *, struct arc *));
108  static VOID uncolorchain _ANSI_ARGS_((struct colormap *, struct arc *));  static VOID uncolorchain _ANSI_ARGS_((struct colormap *, struct arc *));
109  static int singleton _ANSI_ARGS_((struct colormap *, pchr c));  static int singleton _ANSI_ARGS_((struct colormap *, pchr c));
110  static VOID rainbow _ANSI_ARGS_((struct nfa *, struct colormap *, int, pcolor, struct state *, struct state *));  static VOID rainbow _ANSI_ARGS_((struct nfa *, struct colormap *, int, pcolor, struct state *, struct state *));
111  static VOID colorcomplement _ANSI_ARGS_((struct nfa *, struct colormap *, int, struct state *, struct state *, struct state *));  static VOID colorcomplement _ANSI_ARGS_((struct nfa *, struct colormap *, int, struct state *, struct state *, struct state *));
112  #ifdef REG_DEBUG  #ifdef REG_DEBUG
113  static VOID dumpcolors _ANSI_ARGS_((struct colormap *, FILE *));  static VOID dumpcolors _ANSI_ARGS_((struct colormap *, FILE *));
114  static VOID fillcheck _ANSI_ARGS_((struct colormap *, union tree *, int, FILE *));  static VOID fillcheck _ANSI_ARGS_((struct colormap *, union tree *, int, FILE *));
115  static VOID dumpchr _ANSI_ARGS_((pchr, FILE *));  static VOID dumpchr _ANSI_ARGS_((pchr, FILE *));
116  #endif  #endif
117  /* === regc_nfa.c === */  /* === regc_nfa.c === */
118  static struct nfa *newnfa _ANSI_ARGS_((struct vars *, struct colormap *, struct nfa *));  static struct nfa *newnfa _ANSI_ARGS_((struct vars *, struct colormap *, struct nfa *));
119  static VOID freenfa _ANSI_ARGS_((struct nfa *));  static VOID freenfa _ANSI_ARGS_((struct nfa *));
120  static struct state *newstate _ANSI_ARGS_((struct nfa *));  static struct state *newstate _ANSI_ARGS_((struct nfa *));
121  static struct state *newfstate _ANSI_ARGS_((struct nfa *, int flag));  static struct state *newfstate _ANSI_ARGS_((struct nfa *, int flag));
122  static VOID dropstate _ANSI_ARGS_((struct nfa *, struct state *));  static VOID dropstate _ANSI_ARGS_((struct nfa *, struct state *));
123  static VOID freestate _ANSI_ARGS_((struct nfa *, struct state *));  static VOID freestate _ANSI_ARGS_((struct nfa *, struct state *));
124  static VOID destroystate _ANSI_ARGS_((struct nfa *, struct state *));  static VOID destroystate _ANSI_ARGS_((struct nfa *, struct state *));
125  static VOID newarc _ANSI_ARGS_((struct nfa *, int, pcolor, struct state *, struct state *));  static VOID newarc _ANSI_ARGS_((struct nfa *, int, pcolor, struct state *, struct state *));
126  static struct arc *allocarc _ANSI_ARGS_((struct nfa *, struct state *));  static struct arc *allocarc _ANSI_ARGS_((struct nfa *, struct state *));
127  static VOID freearc _ANSI_ARGS_((struct nfa *, struct arc *));  static VOID freearc _ANSI_ARGS_((struct nfa *, struct arc *));
128  static struct arc *findarc _ANSI_ARGS_((struct state *, int, pcolor));  static struct arc *findarc _ANSI_ARGS_((struct state *, int, pcolor));
129  static VOID cparc _ANSI_ARGS_((struct nfa *, struct arc *, struct state *, struct state *));  static VOID cparc _ANSI_ARGS_((struct nfa *, struct arc *, struct state *, struct state *));
130  static VOID moveins _ANSI_ARGS_((struct nfa *, struct state *, struct state *));  static VOID moveins _ANSI_ARGS_((struct nfa *, struct state *, struct state *));
131  static VOID copyins _ANSI_ARGS_((struct nfa *, struct state *, struct state *));  static VOID copyins _ANSI_ARGS_((struct nfa *, struct state *, struct state *));
132  static VOID moveouts _ANSI_ARGS_((struct nfa *, struct state *, struct state *));  static VOID moveouts _ANSI_ARGS_((struct nfa *, struct state *, struct state *));
133  static VOID copyouts _ANSI_ARGS_((struct nfa *, struct state *, struct state *));  static VOID copyouts _ANSI_ARGS_((struct nfa *, struct state *, struct state *));
134  static VOID cloneouts _ANSI_ARGS_((struct nfa *, struct state *, struct state *, struct state *, int));  static VOID cloneouts _ANSI_ARGS_((struct nfa *, struct state *, struct state *, struct state *, int));
135  static VOID delsub _ANSI_ARGS_((struct nfa *, struct state *, struct state *));  static VOID delsub _ANSI_ARGS_((struct nfa *, struct state *, struct state *));
136  static VOID deltraverse _ANSI_ARGS_((struct nfa *, struct state *, struct state *));  static VOID deltraverse _ANSI_ARGS_((struct nfa *, struct state *, struct state *));
137  static VOID dupnfa _ANSI_ARGS_((struct nfa *, struct state *, struct state *, struct state *, struct state *));  static VOID dupnfa _ANSI_ARGS_((struct nfa *, struct state *, struct state *, struct state *, struct state *));
138  static VOID duptraverse _ANSI_ARGS_((struct nfa *, struct state *, struct state *));  static VOID duptraverse _ANSI_ARGS_((struct nfa *, struct state *, struct state *));
139  static VOID cleartraverse _ANSI_ARGS_((struct nfa *, struct state *));  static VOID cleartraverse _ANSI_ARGS_((struct nfa *, struct state *));
140  static VOID specialcolors _ANSI_ARGS_((struct nfa *));  static VOID specialcolors _ANSI_ARGS_((struct nfa *));
141  static long optimize _ANSI_ARGS_((struct nfa *, FILE *));  static long optimize _ANSI_ARGS_((struct nfa *, FILE *));
142  static VOID pullback _ANSI_ARGS_((struct nfa *, FILE *));  static VOID pullback _ANSI_ARGS_((struct nfa *, FILE *));
143  static int pull _ANSI_ARGS_((struct nfa *, struct arc *));  static int pull _ANSI_ARGS_((struct nfa *, struct arc *));
144  static VOID pushfwd _ANSI_ARGS_((struct nfa *, FILE *));  static VOID pushfwd _ANSI_ARGS_((struct nfa *, FILE *));
145  static int push _ANSI_ARGS_((struct nfa *, struct arc *));  static int push _ANSI_ARGS_((struct nfa *, struct arc *));
146  #define INCOMPATIBLE    1       /* destroys arc */  #define INCOMPATIBLE    1       /* destroys arc */
147  #define SATISFIED       2       /* constraint satisfied */  #define SATISFIED       2       /* constraint satisfied */
148  #define COMPATIBLE      3       /* compatible but not satisfied yet */  #define COMPATIBLE      3       /* compatible but not satisfied yet */
149  static int combine _ANSI_ARGS_((struct arc *, struct arc *));  static int combine _ANSI_ARGS_((struct arc *, struct arc *));
150  static VOID fixempties _ANSI_ARGS_((struct nfa *, FILE *));  static VOID fixempties _ANSI_ARGS_((struct nfa *, FILE *));
151  static int unempty _ANSI_ARGS_((struct nfa *, struct arc *));  static int unempty _ANSI_ARGS_((struct nfa *, struct arc *));
152  static VOID cleanup _ANSI_ARGS_((struct nfa *));  static VOID cleanup _ANSI_ARGS_((struct nfa *));
153  static VOID markreachable _ANSI_ARGS_((struct nfa *, struct state *, struct state *, struct state *));  static VOID markreachable _ANSI_ARGS_((struct nfa *, struct state *, struct state *, struct state *));
154  static VOID markcanreach _ANSI_ARGS_((struct nfa *, struct state *, struct state *, struct state *));  static VOID markcanreach _ANSI_ARGS_((struct nfa *, struct state *, struct state *, struct state *));
155  static long analyze _ANSI_ARGS_((struct nfa *));  static long analyze _ANSI_ARGS_((struct nfa *));
156  static VOID compact _ANSI_ARGS_((struct nfa *, struct cnfa *));  static VOID compact _ANSI_ARGS_((struct nfa *, struct cnfa *));
157  static VOID carcsort _ANSI_ARGS_((struct carc *, struct carc *));  static VOID carcsort _ANSI_ARGS_((struct carc *, struct carc *));
158  static VOID freecnfa _ANSI_ARGS_((struct cnfa *));  static VOID freecnfa _ANSI_ARGS_((struct cnfa *));
159  static VOID dumpnfa _ANSI_ARGS_((struct nfa *, FILE *));  static VOID dumpnfa _ANSI_ARGS_((struct nfa *, FILE *));
160  #ifdef REG_DEBUG  #ifdef REG_DEBUG
161  static VOID dumpstate _ANSI_ARGS_((struct state *, FILE *));  static VOID dumpstate _ANSI_ARGS_((struct state *, FILE *));
162  static VOID dumparcs _ANSI_ARGS_((struct state *, FILE *));  static VOID dumparcs _ANSI_ARGS_((struct state *, FILE *));
163  static int dumprarcs _ANSI_ARGS_((struct arc *, struct state *, FILE *, int));  static int dumprarcs _ANSI_ARGS_((struct arc *, struct state *, FILE *, int));
164  static VOID dumparc _ANSI_ARGS_((struct arc *, struct state *, FILE *));  static VOID dumparc _ANSI_ARGS_((struct arc *, struct state *, FILE *));
165  #endif  #endif
166  static VOID dumpcnfa _ANSI_ARGS_((struct cnfa *, FILE *));  static VOID dumpcnfa _ANSI_ARGS_((struct cnfa *, FILE *));
167  #ifdef REG_DEBUG  #ifdef REG_DEBUG
168  static VOID dumpcstate _ANSI_ARGS_((int, struct carc *, struct cnfa *, FILE *));  static VOID dumpcstate _ANSI_ARGS_((int, struct carc *, struct cnfa *, FILE *));
169  #endif  #endif
170  /* === regc_cvec.c === */  /* === regc_cvec.c === */
171  static struct cvec *newcvec _ANSI_ARGS_((int, int, int));  static struct cvec *newcvec _ANSI_ARGS_((int, int, int));
172  static struct cvec *clearcvec _ANSI_ARGS_((struct cvec *));  static struct cvec *clearcvec _ANSI_ARGS_((struct cvec *));
173  static VOID addchr _ANSI_ARGS_((struct cvec *, pchr));  static VOID addchr _ANSI_ARGS_((struct cvec *, pchr));
174  static VOID addrange _ANSI_ARGS_((struct cvec *, pchr, pchr));  static VOID addrange _ANSI_ARGS_((struct cvec *, pchr, pchr));
175  static VOID addmcce _ANSI_ARGS_((struct cvec *, chr *, chr *));  static VOID addmcce _ANSI_ARGS_((struct cvec *, chr *, chr *));
176  static int haschr _ANSI_ARGS_((struct cvec *, pchr));  static int haschr _ANSI_ARGS_((struct cvec *, pchr));
177  static struct cvec *getcvec _ANSI_ARGS_((struct vars *, int, int, int));  static struct cvec *getcvec _ANSI_ARGS_((struct vars *, int, int, int));
178  static VOID freecvec _ANSI_ARGS_((struct cvec *));  static VOID freecvec _ANSI_ARGS_((struct cvec *));
179  /* === regc_locale.c === */  /* === regc_locale.c === */
180  static int nmcces _ANSI_ARGS_((struct vars *));  static int nmcces _ANSI_ARGS_((struct vars *));
181  static int nleaders _ANSI_ARGS_((struct vars *));  static int nleaders _ANSI_ARGS_((struct vars *));
182  static struct cvec *allmcces _ANSI_ARGS_((struct vars *, struct cvec *));  static struct cvec *allmcces _ANSI_ARGS_((struct vars *, struct cvec *));
183  static celt element _ANSI_ARGS_((struct vars *, chr *, chr *));  static celt element _ANSI_ARGS_((struct vars *, chr *, chr *));
184  static struct cvec *range _ANSI_ARGS_((struct vars *, celt, celt, int));  static struct cvec *range _ANSI_ARGS_((struct vars *, celt, celt, int));
185  static int before _ANSI_ARGS_((celt, celt));  static int before _ANSI_ARGS_((celt, celt));
186  static struct cvec *eclass _ANSI_ARGS_((struct vars *, celt, int));  static struct cvec *eclass _ANSI_ARGS_((struct vars *, celt, int));
187  static struct cvec *cclass _ANSI_ARGS_((struct vars *, chr *, chr *, int));  static struct cvec *cclass _ANSI_ARGS_((struct vars *, chr *, chr *, int));
188  static struct cvec *allcases _ANSI_ARGS_((struct vars *, pchr));  static struct cvec *allcases _ANSI_ARGS_((struct vars *, pchr));
189  static int cmp _ANSI_ARGS_((CONST chr *, CONST chr *, size_t));  static int cmp _ANSI_ARGS_((CONST chr *, CONST chr *, size_t));
190  static int casecmp _ANSI_ARGS_((CONST chr *, CONST chr *, size_t));  static int casecmp _ANSI_ARGS_((CONST chr *, CONST chr *, size_t));
191  /* automatically gathered by fwd; do not hand-edit */  /* automatically gathered by fwd; do not hand-edit */
192  /* =====^!^===== end forwards =====^!^===== */  /* =====^!^===== end forwards =====^!^===== */
193    
194    
195    
196  /* internal variables, bundled for easy passing around */  /* internal variables, bundled for easy passing around */
197  struct vars {  struct vars {
198          regex_t *re;          regex_t *re;
199          chr *now;               /* scan pointer into string */          chr *now;               /* scan pointer into string */
200          chr *stop;              /* end of string */          chr *stop;              /* end of string */
201          chr *savenow;           /* saved now and stop for "subroutine call" */          chr *savenow;           /* saved now and stop for "subroutine call" */
202          chr *savestop;          chr *savestop;
203          int err;                /* error code (0 if none) */          int err;                /* error code (0 if none) */
204          int cflags;             /* copy of compile flags */          int cflags;             /* copy of compile flags */
205          int lasttype;           /* type of previous token */          int lasttype;           /* type of previous token */
206          int nexttype;           /* type of next token */          int nexttype;           /* type of next token */
207          chr nextvalue;          /* value (if any) of next token */          chr nextvalue;          /* value (if any) of next token */
208          int lexcon;             /* lexical context type (see lex.c) */          int lexcon;             /* lexical context type (see lex.c) */
209          int nsubexp;            /* subexpression count */          int nsubexp;            /* subexpression count */
210          struct subre **subs;    /* subRE pointer vector */          struct subre **subs;    /* subRE pointer vector */
211          size_t nsubs;           /* length of vector */          size_t nsubs;           /* length of vector */
212          struct subre *sub10[10];        /* initial vector, enough for most */          struct subre *sub10[10];        /* initial vector, enough for most */
213          struct nfa *nfa;        /* the NFA */          struct nfa *nfa;        /* the NFA */
214          struct colormap *cm;    /* character color map */          struct colormap *cm;    /* character color map */
215          color nlcolor;          /* color of newline */          color nlcolor;          /* color of newline */
216          struct state *wordchrs; /* state in nfa holding word-char outarcs */          struct state *wordchrs; /* state in nfa holding word-char outarcs */
217          struct subre *tree;     /* subexpression tree */          struct subre *tree;     /* subexpression tree */
218          struct subre *treechain;        /* all tree nodes allocated */          struct subre *treechain;        /* all tree nodes allocated */
219          struct subre *treefree;         /* any free tree nodes */          struct subre *treefree;         /* any free tree nodes */
220          int ntree;              /* number of tree nodes */          int ntree;              /* number of tree nodes */
221          struct cvec *cv;        /* interface cvec */          struct cvec *cv;        /* interface cvec */
222          struct cvec *cv2;       /* utility cvec */          struct cvec *cv2;       /* utility cvec */
223          struct cvec *mcces;     /* collating-element information */          struct cvec *mcces;     /* collating-element information */
224  #               define  ISCELEADER(v,c) (v->mcces != NULL && haschr(v->mcces, (c)))  #               define  ISCELEADER(v,c) (v->mcces != NULL && haschr(v->mcces, (c)))
225          struct state *mccepbegin;       /* in nfa, start of MCCE prototypes */          struct state *mccepbegin;       /* in nfa, start of MCCE prototypes */
226          struct state *mccepend; /* in nfa, end of MCCE prototypes */          struct state *mccepend; /* in nfa, end of MCCE prototypes */
227          struct subre *lacons;   /* lookahead-constraint vector */          struct subre *lacons;   /* lookahead-constraint vector */
228          int nlacons;            /* size of lacons */          int nlacons;            /* size of lacons */
229  };  };
230    
231  /* parsing macros; most know that `v' is the struct vars pointer */  /* parsing macros; most know that `v' is the struct vars pointer */
232  #define NEXT()  (next(v))               /* advance by one token */  #define NEXT()  (next(v))               /* advance by one token */
233  #define SEE(t)  (v->nexttype == (t))    /* is next token this? */  #define SEE(t)  (v->nexttype == (t))    /* is next token this? */
234  #define EAT(t)  (SEE(t) && next(v))     /* if next is this, swallow it */  #define EAT(t)  (SEE(t) && next(v))     /* if next is this, swallow it */
235  #define VISERR(vv)      ((vv)->err != 0)        /* have we seen an error yet? */  #define VISERR(vv)      ((vv)->err != 0)        /* have we seen an error yet? */
236  #define ISERR() VISERR(v)  #define ISERR() VISERR(v)
237  #define VERR(vv,e)      ((vv)->nexttype = EOS, ((vv)->err) ? (vv)->err :\  #define VERR(vv,e)      ((vv)->nexttype = EOS, ((vv)->err) ? (vv)->err :\
238                                                          ((vv)->err = (e)))                                                          ((vv)->err = (e)))
239  #define ERR(e)  VERR(v, e)              /* record an error */  #define ERR(e)  VERR(v, e)              /* record an error */
240  #define NOERR() {if (ISERR()) return;}  /* if error seen, return */  #define NOERR() {if (ISERR()) return;}  /* if error seen, return */
241  #define NOERRN()        {if (ISERR()) return NULL;}     /* NOERR with retval */  #define NOERRN()        {if (ISERR()) return NULL;}     /* NOERR with retval */
242  #define NOERRZ()        {if (ISERR()) return 0;}        /* NOERR with retval */  #define NOERRZ()        {if (ISERR()) return 0;}        /* NOERR with retval */
243  #define INSIST(c, e)    ((c) ? 0 : ERR(e))      /* if condition false, error */  #define INSIST(c, e)    ((c) ? 0 : ERR(e))      /* if condition false, error */
244  #define NOTE(b) (v->re->re_info |= (b))         /* note visible condition */  #define NOTE(b) (v->re->re_info |= (b))         /* note visible condition */
245  #define EMPTYARC(x, y)  newarc(v->nfa, EMPTY, 0, x, y)  #define EMPTYARC(x, y)  newarc(v->nfa, EMPTY, 0, x, y)
246    
247  /* token type codes, some also used as NFA arc types */  /* token type codes, some also used as NFA arc types */
248  #define EMPTY   'n'             /* no token present */  #define EMPTY   'n'             /* no token present */
249  #define EOS     'e'             /* end of string */  #define EOS     'e'             /* end of string */
250  #define PLAIN   'p'             /* ordinary character */  #define PLAIN   'p'             /* ordinary character */
251  #define DIGIT   'd'             /* digit (in bound) */  #define DIGIT   'd'             /* digit (in bound) */
252  #define BACKREF 'b'             /* back reference */  #define BACKREF 'b'             /* back reference */
253  #define COLLEL  'I'             /* start of [. */  #define COLLEL  'I'             /* start of [. */
254  #define ECLASS  'E'             /* start of [= */  #define ECLASS  'E'             /* start of [= */
255  #define CCLASS  'C'             /* start of [: */  #define CCLASS  'C'             /* start of [: */
256  #define END     'X'             /* end of [. [= [: */  #define END     'X'             /* end of [. [= [: */
257  #define RANGE   'R'             /* - within [] which might be range delim. */  #define RANGE   'R'             /* - within [] which might be range delim. */
258  #define LACON   'L'             /* lookahead constraint subRE */  #define LACON   'L'             /* lookahead constraint subRE */
259  #define AHEAD   'a'             /* color-lookahead arc */  #define AHEAD   'a'             /* color-lookahead arc */
260  #define BEHIND  'r'             /* color-lookbehind arc */  #define BEHIND  'r'             /* color-lookbehind arc */
261  #define WBDRY   'w'             /* word boundary constraint */  #define WBDRY   'w'             /* word boundary constraint */
262  #define NWBDRY  'W'             /* non-word-boundary constraint */  #define NWBDRY  'W'             /* non-word-boundary constraint */
263  #define SBEGIN  'A'             /* beginning of string (even if not BOL) */  #define SBEGIN  'A'             /* beginning of string (even if not BOL) */
264  #define SEND    'Z'             /* end of string (even if not EOL) */  #define SEND    'Z'             /* end of string (even if not EOL) */
265  #define PREFER  'P'             /* length preference */  #define PREFER  'P'             /* length preference */
266    
267  /* is an arc colored, and hence on a color chain? */  /* is an arc colored, and hence on a color chain? */
268  #define COLORED(a)      ((a)->type == PLAIN || (a)->type == AHEAD || \  #define COLORED(a)      ((a)->type == PLAIN || (a)->type == AHEAD || \
269                                                          (a)->type == BEHIND)                                                          (a)->type == BEHIND)
270    
271    
272    
273  /* static function list */  /* static function list */
274  static struct fns functions = {  static struct fns functions = {
275          rfree,                  /* regfree insides */          rfree,                  /* regfree insides */
276  };  };
277    
278    
279    
280  /*  /*
281   - compile - compile regular expression   - compile - compile regular expression
282   ^ int compile(regex_t *, CONST chr *, size_t, int);   ^ int compile(regex_t *, CONST chr *, size_t, int);
283   */   */
284  int  int
285  compile(re, string, len, flags)  compile(re, string, len, flags)
286  regex_t *re;  regex_t *re;
287  CONST chr *string;  CONST chr *string;
288  size_t len;  size_t len;
289  int flags;  int flags;
290  {  {
291          struct vars var;          struct vars var;
292          struct vars *v = &var;          struct vars *v = &var;
293          struct guts *g;          struct guts *g;
294          int i;          int i;
295          size_t j;          size_t j;
296          FILE *debug = (flags&REG_PROGRESS) ? stdout : (FILE *)NULL;          FILE *debug = (flags&REG_PROGRESS) ? stdout : (FILE *)NULL;
297  #       define  CNOERR()        { if (ISERR()) return freev(v, v->err); }  #       define  CNOERR()        { if (ISERR()) return freev(v, v->err); }
298    
299          /* sanity checks */          /* sanity checks */
300    
301          if (re == NULL || string == NULL)          if (re == NULL || string == NULL)
302                  return REG_INVARG;                  return REG_INVARG;
303          if ((flags&REG_QUOTE) &&          if ((flags&REG_QUOTE) &&
304                          (flags&(REG_ADVANCED|REG_EXPANDED|REG_NEWLINE)))                          (flags&(REG_ADVANCED|REG_EXPANDED|REG_NEWLINE)))
305                  return REG_INVARG;                  return REG_INVARG;
306          if (!(flags&REG_EXTENDED) && (flags&REG_ADVF))          if (!(flags&REG_EXTENDED) && (flags&REG_ADVF))
307                  return REG_INVARG;                  return REG_INVARG;
308    
309          /* initial setup (after which freev() is callable) */          /* initial setup (after which freev() is callable) */
310          v->re = re;          v->re = re;
311          v->now = (chr *)string;          v->now = (chr *)string;
312          v->stop = v->now + len;          v->stop = v->now + len;
313          v->savenow = v->savestop = NULL;          v->savenow = v->savestop = NULL;
314          v->err = 0;          v->err = 0;
315          v->cflags = flags;          v->cflags = flags;
316          v->nsubexp = 0;          v->nsubexp = 0;
317          v->subs = v->sub10;          v->subs = v->sub10;
318          v->nsubs = 10;          v->nsubs = 10;
319          for (j = 0; j < v->nsubs; j++)          for (j = 0; j < v->nsubs; j++)
320                  v->subs[j] = NULL;                  v->subs[j] = NULL;
321          v->nfa = NULL;          v->nfa = NULL;
322          v->cm = NULL;          v->cm = NULL;
323          v->nlcolor = COLORLESS;          v->nlcolor = COLORLESS;
324          v->wordchrs = NULL;          v->wordchrs = NULL;
325          v->tree = NULL;          v->tree = NULL;
326          v->treechain = NULL;          v->treechain = NULL;
327          v->treefree = NULL;          v->treefree = NULL;
328          v->cv = NULL;          v->cv = NULL;
329          v->cv2 = NULL;          v->cv2 = NULL;
330          v->mcces = NULL;          v->mcces = NULL;
331          v->lacons = NULL;          v->lacons = NULL;
332          v->nlacons = 0;          v->nlacons = 0;
333          re->re_magic = REMAGIC;          re->re_magic = REMAGIC;
334          re->re_info = 0;                /* bits get set during parse */          re->re_info = 0;                /* bits get set during parse */
335          re->re_csize = sizeof(chr);          re->re_csize = sizeof(chr);
336          re->re_guts = NULL;          re->re_guts = NULL;
337          re->re_fns = VS(&functions);          re->re_fns = VS(&functions);
338    
339          /* more complex setup, malloced things */          /* more complex setup, malloced things */
340          re->re_guts = VS(MALLOC(sizeof(struct guts)));          re->re_guts = VS(MALLOC(sizeof(struct guts)));
341          if (re->re_guts == NULL)          if (re->re_guts == NULL)
342                  return freev(v, REG_ESPACE);                  return freev(v, REG_ESPACE);
343          g = (struct guts *)re->re_guts;          g = (struct guts *)re->re_guts;
344          g->tree = NULL;          g->tree = NULL;
345          initcm(v, &g->cmap);          initcm(v, &g->cmap);
346          v->cm = &g->cmap;          v->cm = &g->cmap;
347          g->lacons = NULL;          g->lacons = NULL;
348          g->nlacons = 0;          g->nlacons = 0;
349          ZAPCNFA(g->search);          ZAPCNFA(g->search);
350          v->nfa = newnfa(v, v->cm, (struct nfa *)NULL);          v->nfa = newnfa(v, v->cm, (struct nfa *)NULL);
351          CNOERR();          CNOERR();
352          v->cv = newcvec(100, 20, 10);          v->cv = newcvec(100, 20, 10);
353          if (v->cv == NULL)          if (v->cv == NULL)
354                  return freev(v, REG_ESPACE);                  return freev(v, REG_ESPACE);
355          i = nmcces(v);          i = nmcces(v);
356          if (i > 0) {          if (i > 0) {
357                  v->mcces = newcvec(nleaders(v), 0, i);                  v->mcces = newcvec(nleaders(v), 0, i);
358                  CNOERR();                  CNOERR();
359                  v->mcces = allmcces(v, v->mcces);                  v->mcces = allmcces(v, v->mcces);
360                  leaders(v, v->mcces);                  leaders(v, v->mcces);
361                  addmcce(v->mcces, (chr *)NULL, (chr *)NULL);    /* dummy */                  addmcce(v->mcces, (chr *)NULL, (chr *)NULL);    /* dummy */
362          }          }
363          CNOERR();          CNOERR();
364    
365          /* parsing */          /* parsing */
366          lexstart(v);                    /* also handles prefixes */          lexstart(v);                    /* also handles prefixes */
367          if ((v->cflags&REG_NLSTOP) || (v->cflags&REG_NLANCH)) {          if ((v->cflags&REG_NLSTOP) || (v->cflags&REG_NLANCH)) {
368                  /* assign newline a unique color */                  /* assign newline a unique color */
369                  v->nlcolor = subcolor(v->cm, newline());                  v->nlcolor = subcolor(v->cm, newline());
370                  okcolors(v->nfa, v->cm);                  okcolors(v->nfa, v->cm);
371          }          }
372          CNOERR();          CNOERR();
373          v->tree = parse(v, EOS, PLAIN, v->nfa->init, v->nfa->final);          v->tree = parse(v, EOS, PLAIN, v->nfa->init, v->nfa->final);
374          assert(SEE(EOS));               /* even if error; ISERR() => SEE(EOS) */          assert(SEE(EOS));               /* even if error; ISERR() => SEE(EOS) */
375          CNOERR();          CNOERR();
376          assert(v->tree != NULL);          assert(v->tree != NULL);
377    
378          /* finish setup of nfa and its subre tree */          /* finish setup of nfa and its subre tree */
379          specialcolors(v->nfa);          specialcolors(v->nfa);
380          CNOERR();          CNOERR();
381          if (debug != NULL) {          if (debug != NULL) {
382                  fprintf(debug, "\n\n\n========= RAW ==========\n");                  fprintf(debug, "\n\n\n========= RAW ==========\n");
383                  dumpnfa(v->nfa, debug);                  dumpnfa(v->nfa, debug);
384                  dumpst(v->tree, debug, 1);                  dumpst(v->tree, debug, 1);
385          }          }
386          optst(v, v->tree);          optst(v, v->tree);
387          v->ntree = numst(v->tree, 1);          v->ntree = numst(v->tree, 1);
388          markst(v->tree);          markst(v->tree);
389          cleanst(v);          cleanst(v);
390          if (debug != NULL) {          if (debug != NULL) {
391                  fprintf(debug, "\n\n\n========= TREE FIXED ==========\n");                  fprintf(debug, "\n\n\n========= TREE FIXED ==========\n");
392                  dumpst(v->tree, debug, 1);                  dumpst(v->tree, debug, 1);
393          }          }
394    
395          /* build compacted NFAs for tree and lacons */          /* build compacted NFAs for tree and lacons */
396          re->re_info |= nfatree(v, v->tree, debug);          re->re_info |= nfatree(v, v->tree, debug);
397          CNOERR();          CNOERR();
398          assert(v->nlacons == 0 || v->lacons != NULL);          assert(v->nlacons == 0 || v->lacons != NULL);
399          for (i = 1; i < v->nlacons; i++) {          for (i = 1; i < v->nlacons; i++) {
400                  if (debug != NULL)                  if (debug != NULL)
401                          fprintf(debug, "\n\n\n========= LA%d ==========\n", i);                          fprintf(debug, "\n\n\n========= LA%d ==========\n", i);
402                  nfanode(v, &v->lacons[i], debug);                  nfanode(v, &v->lacons[i], debug);
403          }          }
404          CNOERR();          CNOERR();
405          if (v->tree->flags&SHORTER)          if (v->tree->flags&SHORTER)
406                  NOTE(REG_USHORTEST);                  NOTE(REG_USHORTEST);
407    
408          /* build compacted NFAs for tree, lacons, fast search */          /* build compacted NFAs for tree, lacons, fast search */
409          if (debug != NULL)          if (debug != NULL)
410                  fprintf(debug, "\n\n\n========= SEARCH ==========\n");                  fprintf(debug, "\n\n\n========= SEARCH ==========\n");
411          /* can sacrifice main NFA now, so use it as work area */          /* can sacrifice main NFA now, so use it as work area */
412          (DISCARD)optimize(v->nfa, debug);          (DISCARD)optimize(v->nfa, debug);
413          CNOERR();          CNOERR();
414          makesearch(v, v->nfa);          makesearch(v, v->nfa);
415          CNOERR();          CNOERR();
416          compact(v->nfa, &g->search);          compact(v->nfa, &g->search);
417          CNOERR();          CNOERR();
418    
419          /* looks okay, package it up */          /* looks okay, package it up */
420          re->re_nsub = v->nsubexp;          re->re_nsub = v->nsubexp;
421          v->re = NULL;                   /* freev no longer frees re */          v->re = NULL;                   /* freev no longer frees re */
422          g->magic = GUTSMAGIC;          g->magic = GUTSMAGIC;
423          g->cflags = v->cflags;          g->cflags = v->cflags;
424          g->info = re->re_info;          g->info = re->re_info;
425          g->nsub = re->re_nsub;          g->nsub = re->re_nsub;
426          g->tree = v->tree;          g->tree = v->tree;
427          v->tree = NULL;          v->tree = NULL;
428          g->ntree = v->ntree;          g->ntree = v->ntree;
429          g->compare = (v->cflags&REG_ICASE) ? casecmp : cmp;          g->compare = (v->cflags&REG_ICASE) ? casecmp : cmp;
430          g->lacons = v->lacons;          g->lacons = v->lacons;
431          v->lacons = NULL;          v->lacons = NULL;
432          g->nlacons = v->nlacons;          g->nlacons = v->nlacons;
433    
434          if (flags&REG_DUMP)          if (flags&REG_DUMP)
435                  dump(re, stdout);                  dump(re, stdout);
436    
437          assert(v->err == 0);          assert(v->err == 0);
438          return freev(v, 0);          return freev(v, 0);
439  }  }
440    
441  /*  /*
442   - moresubs - enlarge subRE vector   - moresubs - enlarge subRE vector
443   ^ static VOID moresubs(struct vars *, int);   ^ static VOID moresubs(struct vars *, int);
444   */   */
445  static VOID  static VOID
446  moresubs(v, wanted)  moresubs(v, wanted)
447  struct vars *v;  struct vars *v;
448  int wanted;                     /* want enough room for this one */  int wanted;                     /* want enough room for this one */
449  {  {
450          struct subre **p;          struct subre **p;
451          size_t n;          size_t n;
452    
453          assert(wanted > 0 && (size_t)wanted >= v->nsubs);          assert(wanted > 0 && (size_t)wanted >= v->nsubs);
454          n = (size_t)wanted * 3 / 2 + 1;          n = (size_t)wanted * 3 / 2 + 1;
455          if (v->subs == v->sub10) {          if (v->subs == v->sub10) {
456                  p = (struct subre **)MALLOC(n * sizeof(struct subre *));                  p = (struct subre **)MALLOC(n * sizeof(struct subre *));
457                  if (p != NULL)                  if (p != NULL)
458                          memcpy(VS(p), VS(v->subs),                          memcpy(VS(p), VS(v->subs),
459                                          v->nsubs * sizeof(struct subre *));                                          v->nsubs * sizeof(struct subre *));
460          } else          } else
461                  p = (struct subre **)REALLOC(v->subs, n*sizeof(struct subre *));                  p = (struct subre **)REALLOC(v->subs, n*sizeof(struct subre *));
462          if (p == NULL) {          if (p == NULL) {
463                  ERR(REG_ESPACE);                  ERR(REG_ESPACE);
464                  return;                  return;
465          }          }
466          v->subs = p;          v->subs = p;
467          for (p = &v->subs[v->nsubs]; v->nsubs < n; p++, v->nsubs++)          for (p = &v->subs[v->nsubs]; v->nsubs < n; p++, v->nsubs++)
468                  *p = NULL;                  *p = NULL;
469          assert(v->nsubs == n);          assert(v->nsubs == n);
470          assert((size_t)wanted < v->nsubs);          assert((size_t)wanted < v->nsubs);
471  }  }
472    
473  /*  /*
474   - freev - free vars struct's substructures where necessary   - freev - free vars struct's substructures where necessary
475   * Optionally does error-number setting, and always returns error code   * Optionally does error-number setting, and always returns error code
476   * (if any), to make error-handling code terser.   * (if any), to make error-handling code terser.
477   ^ static int freev(struct vars *, int);   ^ static int freev(struct vars *, int);
478   */   */
479  static int  static int
480  freev(v, err)  freev(v, err)
481  struct vars *v;  struct vars *v;
482  int err;  int err;
483  {  {
484          if (v->re != NULL)          if (v->re != NULL)
485                  rfree(v->re);                  rfree(v->re);
486          if (v->subs != v->sub10)          if (v->subs != v->sub10)
487                  FREE(v->subs);                  FREE(v->subs);
488          if (v->nfa != NULL)          if (v->nfa != NULL)
489                  freenfa(v->nfa);                  freenfa(v->nfa);
490          if (v->tree != NULL)          if (v->tree != NULL)
491                  freesubre(v, v->tree);                  freesubre(v, v->tree);
492          if (v->treechain != NULL)          if (v->treechain != NULL)
493                  cleanst(v);                  cleanst(v);
494          if (v->cv != NULL)          if (v->cv != NULL)
495                  freecvec(v->cv);                  freecvec(v->cv);
496          if (v->cv2 != NULL)          if (v->cv2 != NULL)
497                  freecvec(v->cv2);                  freecvec(v->cv2);
498          if (v->mcces != NULL)          if (v->mcces != NULL)
499                  freecvec(v->mcces);                  freecvec(v->mcces);
500          if (v->lacons != NULL)          if (v->lacons != NULL)
501                  freelacons(v->lacons, v->nlacons);                  freelacons(v->lacons, v->nlacons);
502          ERR(err);                       /* nop if err==0 */          ERR(err);                       /* nop if err==0 */
503    
504          return v->err;          return v->err;
505  }  }
506    
507  /*  /*
508   - makesearch - turn an NFA into a search NFA (implicit prepend of .*?)   - makesearch - turn an NFA into a search NFA (implicit prepend of .*?)
509   * NFA must have been optimize()d already.   * NFA must have been optimize()d already.
510   ^ static VOID makesearch(struct vars *, struct nfa *);   ^ static VOID makesearch(struct vars *, struct nfa *);
511   */   */
512  static VOID  static VOID
513  makesearch(v, nfa)  makesearch(v, nfa)
514  struct vars *v;  struct vars *v;
515  struct nfa *nfa;  struct nfa *nfa;
516  {  {
517          struct arc *a;          struct arc *a;
518          struct arc *b;          struct arc *b;
519          struct state *pre = nfa->pre;          struct state *pre = nfa->pre;
520          struct state *s;          struct state *s;
521          struct state *s2;          struct state *s2;
522          struct state *slist;          struct state *slist;
523    
524          /* no loops are needed if it's anchored */          /* no loops are needed if it's anchored */
525          for (a = pre->outs; a != NULL; a = a->outchain) {          for (a = pre->outs; a != NULL; a = a->outchain) {
526                  assert(a->type == PLAIN);                  assert(a->type == PLAIN);
527                  if (a->co != nfa->bos[0] && a->co != nfa->bos[1])                  if (a->co != nfa->bos[0] && a->co != nfa->bos[1])
528                          break;                          break;
529          }          }
530          if (a != NULL) {          if (a != NULL) {
531                  /* add implicit .* in front */                  /* add implicit .* in front */
532                  rainbow(nfa, v->cm, PLAIN, COLORLESS, pre, pre);                  rainbow(nfa, v->cm, PLAIN, COLORLESS, pre, pre);
533    
534                  /* and ^* and \A* too -- not always necessary, but harmless */                  /* and ^* and \A* too -- not always necessary, but harmless */
535                  newarc(nfa, PLAIN, nfa->bos[0], pre, pre);                  newarc(nfa, PLAIN, nfa->bos[0], pre, pre);
536                  newarc(nfa, PLAIN, nfa->bos[1], pre, pre);                  newarc(nfa, PLAIN, nfa->bos[1], pre, pre);
537          }          }
538    
539          /*          /*
540           * Now here's the subtle part.  Because many REs have no lookback           * Now here's the subtle part.  Because many REs have no lookback
541           * constraints, often knowing when you were in the pre state tells           * constraints, often knowing when you were in the pre state tells
542           * you little; it's the next state(s) that are informative.  But           * you little; it's the next state(s) that are informative.  But
543           * some of them may have other inarcs, i.e. it may be possible to           * some of them may have other inarcs, i.e. it may be possible to
544           * make actual progress and then return to one of them.  We must           * make actual progress and then return to one of them.  We must
545           * de-optimize such cases, splitting each such state into progress           * de-optimize such cases, splitting each such state into progress
546           * and no-progress states.           * and no-progress states.
547           */           */
548    
549          /* first, make a list of the states */          /* first, make a list of the states */
550          slist = NULL;          slist = NULL;
551          for (a = pre->outs; a != NULL; a = a->outchain) {          for (a = pre->outs; a != NULL; a = a->outchain) {
552                  s = a->to;                  s = a->to;
553                  for (b = s->ins; b != NULL; b = b->inchain)                  for (b = s->ins; b != NULL; b = b->inchain)
554                          if (b->from != pre)                          if (b->from != pre)
555                                  break;                                  break;
556                  if (b != NULL) {                /* must be split */                  if (b != NULL) {                /* must be split */
557                          s->tmp = slist;                          s->tmp = slist;
558                          slist = s;                          slist = s;
559                  }                  }
560          }          }
561    
562          /* do the splits */          /* do the splits */
563          for (s = slist; s != NULL; s = s2) {          for (s = slist; s != NULL; s = s2) {
564                  s2 = newstate(nfa);                  s2 = newstate(nfa);
565                  copyouts(nfa, s, s2);                  copyouts(nfa, s, s2);
566                  for (a = s->ins; a != NULL; a = b) {                  for (a = s->ins; a != NULL; a = b) {
567                          b = a->inchain;                          b = a->inchain;
568                          if (a->from != pre) {                          if (a->from != pre) {
569                                  cparc(nfa, a, a->from, s2);                                  cparc(nfa, a, a->from, s2);
570                                  freearc(nfa, a);                                  freearc(nfa, a);
571                          }                          }
572                  }                  }
573                  s2 = s->tmp;                  s2 = s->tmp;
574                  s->tmp = NULL;          /* clean up while we're at it */                  s->tmp = NULL;          /* clean up while we're at it */
575          }          }
576  }  }
577    
578  /*  /*
579   - parse - parse an RE   - parse - parse an RE
580   * This is actually just the top level, which parses a bunch of branches   * This is actually just the top level, which parses a bunch of branches
581   * tied together with '|'.  They appear in the tree as the left children   * tied together with '|'.  They appear in the tree as the left children
582   * of a chain of '|' subres.   * of a chain of '|' subres.
583   ^ static struct subre *parse(struct vars *, int, int, struct state *,   ^ static struct subre *parse(struct vars *, int, int, struct state *,
584   ^      struct state *);   ^      struct state *);
585   */   */
586  static struct subre *  static struct subre *
587  parse(v, stopper, type, init, final)  parse(v, stopper, type, init, final)
588  struct vars *v;  struct vars *v;
589  int stopper;                    /* EOS or ')' */  int stopper;                    /* EOS or ')' */
590  int type;                       /* LACON (lookahead subRE) or PLAIN */  int type;                       /* LACON (lookahead subRE) or PLAIN */
591  struct state *init;             /* initial state */  struct state *init;             /* initial state */
592  struct state *final;            /* final state */  struct state *final;            /* final state */
593  {  {
594          struct state *left;     /* scaffolding for branch */          struct state *left;     /* scaffolding for branch */
595          struct state *right;          struct state *right;
596          struct subre *branches; /* top level */          struct subre *branches; /* top level */
597          struct subre *branch;   /* current branch */          struct subre *branch;   /* current branch */
598          struct subre *t;        /* temporary */          struct subre *t;        /* temporary */
599          int firstbranch;        /* is this the first branch? */          int firstbranch;        /* is this the first branch? */
600    
601          assert(stopper == ')' || stopper == EOS);          assert(stopper == ')' || stopper == EOS);
602    
603          branches = subre(v, '|', LONGER, init, final);          branches = subre(v, '|', LONGER, init, final);
604          NOERRN();          NOERRN();
605          branch = branches;          branch = branches;
606          firstbranch = 1;          firstbranch = 1;
607          do {    /* a branch */          do {    /* a branch */
608                  if (!firstbranch) {                  if (!firstbranch) {
609                          /* need a place to hang it */                          /* need a place to hang it */
610                          branch->right = subre(v, '|', LONGER, init, final);                          branch->right = subre(v, '|', LONGER, init, final);
611                          NOERRN();                          NOERRN();
612                          branch = branch->right;                          branch = branch->right;
613                  }                  }
614                  firstbranch = 0;                  firstbranch = 0;
615                  left = newstate(v->nfa);                  left = newstate(v->nfa);
616                  right = newstate(v->nfa);                  right = newstate(v->nfa);
617                  NOERRN();                  NOERRN();
618                  EMPTYARC(init, left);                  EMPTYARC(init, left);
619                  EMPTYARC(right, final);                  EMPTYARC(right, final);
620                  NOERRN();                  NOERRN();
621                  branch->left = parsebranch(v, stopper, type, left, right, 0);                  branch->left = parsebranch(v, stopper, type, left, right, 0);
622                  NOERRN();                  NOERRN();
623                  branch->flags |= UP(branch->flags | branch->left->flags);                  branch->flags |= UP(branch->flags | branch->left->flags);
624                  if ((branch->flags &~ branches->flags) != 0)    /* new flags */                  if ((branch->flags &~ branches->flags) != 0)    /* new flags */
625                          for (t = branches; t != branch; t = t->right)                          for (t = branches; t != branch; t = t->right)
626                                  t->flags |= branch->flags;                                  t->flags |= branch->flags;
627          } while (EAT('|'));          } while (EAT('|'));
628          assert(SEE(stopper) || SEE(EOS));          assert(SEE(stopper) || SEE(EOS));
629    
630          if (!SEE(stopper)) {          if (!SEE(stopper)) {
631                  assert(stopper == ')' && SEE(EOS));                  assert(stopper == ')' && SEE(EOS));
632                  ERR(REG_EPAREN);                  ERR(REG_EPAREN);
633          }          }
634    
635          /* optimize out simple cases */          /* optimize out simple cases */
636          if (branch == branches) {       /* only one branch */          if (branch == branches) {       /* only one branch */
637                  assert(branch->right == NULL);                  assert(branch->right == NULL);
638                  t = branch->left;                  t = branch->left;
639                  branch->left = NULL;                  branch->left = NULL;
640                  freesubre(v, branches);                  freesubre(v, branches);
641                  branches = t;                  branches = t;
642          } else if (!MESSY(branches->flags)) {   /* no interesting innards */          } else if (!MESSY(branches->flags)) {   /* no interesting innards */
643                  freesubre(v, branches->left);                  freesubre(v, branches->left);
644                  branches->left = NULL;                  branches->left = NULL;
645                  freesubre(v, branches->right);                  freesubre(v, branches->right);
646                  branches->right = NULL;                  branches->right = NULL;
647                  branches->op = '=';                  branches->op = '=';
648          }          }
649    
650          return branches;          return branches;
651  }  }
652    
653  /*  /*
654   - parsebranch - parse one branch of an RE   - parsebranch - parse one branch of an RE
655   * This mostly manages concatenation, working closely with parseqatom().   * This mostly manages concatenation, working closely with parseqatom().
656   * Concatenated things are bundled up as much as possible, with separate   * Concatenated things are bundled up as much as possible, with separate
657   * ',' nodes introduced only when necessary due to substructure.   * ',' nodes introduced only when necessary due to substructure.
658   ^ static struct subre *parsebranch(struct vars *, int, int, struct state *,   ^ static struct subre *parsebranch(struct vars *, int, int, struct state *,
659   ^      struct state *, int);   ^      struct state *, int);
660   */   */
661  static struct subre *  static struct subre *
662  parsebranch(v, stopper, type, left, right, partial)  parsebranch(v, stopper, type, left, right, partial)
663  struct vars *v;  struct vars *v;
664  int stopper;                    /* EOS or ')' */  int stopper;                    /* EOS or ')' */
665  int type;                       /* LACON (lookahead subRE) or PLAIN */  int type;                       /* LACON (lookahead subRE) or PLAIN */
666  struct state *left;             /* leftmost state */  struct state *left;             /* leftmost state */
667  struct state *right;            /* rightmost state */  struct state *right;            /* rightmost state */
668  int partial;                    /* is this only part of a branch? */  int partial;                    /* is this only part of a branch? */
669  {  {
670          struct state *lp;       /* left end of current construct */          struct state *lp;       /* left end of current construct */
671          int seencontent;        /* is there anything in this branch yet? */          int seencontent;        /* is there anything in this branch yet? */
672          struct subre *t;          struct subre *t;
673    
674          lp = left;          lp = left;
675          seencontent = 0;          seencontent = 0;
676          t = subre(v, '=', 0, left, right);      /* op '=' is tentative */          t = subre(v, '=', 0, left, right);      /* op '=' is tentative */
677          NOERRN();          NOERRN();
678          while (!SEE('|') && !SEE(stopper) && !SEE(EOS)) {          while (!SEE('|') && !SEE(stopper) && !SEE(EOS)) {
679                  if (seencontent) {      /* implicit concat operator */                  if (seencontent) {      /* implicit concat operator */
680                          lp = newstate(v->nfa);                          lp = newstate(v->nfa);
681                          NOERRN();                          NOERRN();
682                          moveins(v->nfa, right, lp);                          moveins(v->nfa, right, lp);
683                  }                  }
684                  seencontent = 1;                  seencontent = 1;
685    
686                  /* NB, recursion in parseqatom() may swallow rest of branch */                  /* NB, recursion in parseqatom() may swallow rest of branch */
687                  parseqatom(v, stopper, type, lp, right, t);                  parseqatom(v, stopper, type, lp, right, t);
688          }          }
689    
690          if (!seencontent) {             /* empty branch */          if (!seencontent) {             /* empty branch */
691                  if (!partial)                  if (!partial)
692                          NOTE(REG_UUNSPEC);                          NOTE(REG_UUNSPEC);
693                  assert(lp == left);                  assert(lp == left);
694                  EMPTYARC(left, right);                  EMPTYARC(left, right);
695          }          }
696    
697          return t;          return t;
698  }  }
699    
700  /*  /*
701   - parseqatom - parse one quantified atom or constraint of an RE   - parseqatom - parse one quantified atom or constraint of an RE
702   * The bookkeeping near the end cooperates very closely with parsebranch();   * The bookkeeping near the end cooperates very closely with parsebranch();
703   * in particular, it contains a recursion that can involve parsing the rest   * in particular, it contains a recursion that can involve parsing the rest
704   * of the branch, making this function's name somewhat inaccurate.   * of the branch, making this function's name somewhat inaccurate.
705   ^ static VOID parseqatom(struct vars *, int, int, struct state *,   ^ static VOID parseqatom(struct vars *, int, int, struct state *,
706   ^      struct state *, struct subre *);   ^      struct state *, struct subre *);
707   */   */
708  static VOID  static VOID
709  parseqatom(v, stopper, type, lp, rp, top)  parseqatom(v, stopper, type, lp, rp, top)
710  struct vars *v;  struct vars *v;
711  int stopper;                    /* EOS or ')' */  int stopper;                    /* EOS or ')' */
712  int type;                       /* LACON (lookahead subRE) or PLAIN */  int type;                       /* LACON (lookahead subRE) or PLAIN */
713  struct state *lp;               /* left state to hang it on */  struct state *lp;               /* left state to hang it on */
714  struct state *rp;               /* right state to hang it on */  struct state *rp;               /* right state to hang it on */
715  struct subre *top;              /* subtree top */  struct subre *top;              /* subtree top */
716  {  {
717          struct state *s;        /* temporaries for new states */          struct state *s;        /* temporaries for new states */
718          struct state *s2;          struct state *s2;
719  #       define  ARCV(t, val)    newarc(v->nfa, t, val, lp, rp)  #       define  ARCV(t, val)    newarc(v->nfa, t, val, lp, rp)
720          int m, n;          int m, n;
721          struct subre *atom;     /* atom's subtree */          struct subre *atom;     /* atom's subtree */
722          struct subre *t;          struct subre *t;
723          int cap;                /* capturing parens? */          int cap;                /* capturing parens? */
724          int pos;                /* positive lookahead? */          int pos;                /* positive lookahead? */
725          int subno;              /* capturing-parens or backref number */          int subno;              /* capturing-parens or backref number */
726          int atomtype;          int atomtype;
727          int qprefer;            /* quantifier short/long preference */          int qprefer;            /* quantifier short/long preference */
728          int f;          int f;
729          struct subre **atomp;   /* where the pointer to atom is */          struct subre **atomp;   /* where the pointer to atom is */
730    
731          /* initial bookkeeping */          /* initial bookkeeping */
732          atom = NULL;          atom = NULL;
733          assert(lp->nouts == 0); /* must string new code */          assert(lp->nouts == 0); /* must string new code */
734          assert(rp->nins == 0);  /*  between lp and rp */          assert(rp->nins == 0);  /*  between lp and rp */
735          subno = 0;              /* just to shut lint up */          subno = 0;              /* just to shut lint up */
736    
737          /* an atom or constraint... */          /* an atom or constraint... */
738          atomtype = v->nexttype;          atomtype = v->nexttype;
739          switch (atomtype) {          switch (atomtype) {
740          /* first, constraints, which end by returning */          /* first, constraints, which end by returning */
741          case '^':          case '^':
742                  ARCV('^', 1);                  ARCV('^', 1);
743                  if (v->cflags&REG_NLANCH)                  if (v->cflags&REG_NLANCH)
744                          ARCV(BEHIND, v->nlcolor);                          ARCV(BEHIND, v->nlcolor);
745                  NEXT();                  NEXT();
746                  return;                  return;
747                  break;                  break;
748          case '$':          case '$':
749                  ARCV('$', 1);                  ARCV('$', 1);
750                  if (v->cflags&REG_NLANCH)                  if (v->cflags&REG_NLANCH)
751                          ARCV(AHEAD, v->nlcolor);                          ARCV(AHEAD, v->nlcolor);
752                  NEXT();                  NEXT();
753                  return;                  return;
754                  break;                  break;
755          case SBEGIN:          case SBEGIN:
756                  ARCV('^', 1);   /* BOL */                  ARCV('^', 1);   /* BOL */
757                  ARCV('^', 0);   /* or BOS */                  ARCV('^', 0);   /* or BOS */
758                  NEXT();                  NEXT();
759                  return;                  return;
760                  break;                  break;
761          case SEND:          case SEND:
762                  ARCV('$', 1);   /* EOL */                  ARCV('$', 1);   /* EOL */
763                  ARCV('$', 0);   /* or EOS */                  ARCV('$', 0);   /* or EOS */
764                  NEXT();                  NEXT();
765                  return;                  return;
766                  break;                  break;
767          case '<':          case '<':
768                  wordchrs(v);    /* does NEXT() */                  wordchrs(v);    /* does NEXT() */
769                  s = newstate(v->nfa);                  s = newstate(v->nfa);
770                  NOERR();                  NOERR();
771                  nonword(v, BEHIND, lp, s);                  nonword(v, BEHIND, lp, s);
772                  word(v, AHEAD, s, rp);                  word(v, AHEAD, s, rp);
773                  return;                  return;
774                  break;                  break;
775          case '>':          case '>':
776                  wordchrs(v);    /* does NEXT() */                  wordchrs(v);    /* does NEXT() */
777                  s = newstate(v->nfa);                  s = newstate(v->nfa);
778                  NOERR();                  NOERR();
779                  word(v, BEHIND, lp, s);                  word(v, BEHIND, lp, s);
780                  nonword(v, AHEAD, s, rp);                  nonword(v, AHEAD, s, rp);
781                  return;                  return;
782                  break;                  break;
783          case WBDRY:          case WBDRY:
784                  wordchrs(v);    /* does NEXT() */                  wordchrs(v);    /* does NEXT() */
785                  s = newstate(v->nfa);                  s = newstate(v->nfa);
786                  NOERR();                  NOERR();
787                  nonword(v, BEHIND, lp, s);                  nonword(v, BEHIND, lp, s);
788                  word(v, AHEAD, s, rp);                  word(v, AHEAD, s, rp);
789                  s = newstate(v->nfa);                  s = newstate(v->nfa);
790                  NOERR();                  NOERR();
791                  word(v, BEHIND, lp, s);                  word(v, BEHIND, lp, s);
792                  nonword(v, AHEAD, s, rp);                  nonword(v, AHEAD, s, rp);
793                  return;                  return;
794                  break;                  break;
795          case NWBDRY:          case NWBDRY:
796                  wordchrs(v);    /* does NEXT() */                  wordchrs(v);    /* does NEXT() */
797                  s = newstate(v->nfa);                  s = newstate(v->nfa);
798                  NOERR();                  NOERR();
799                  word(v, BEHIND, lp, s);                  word(v, BEHIND, lp, s);
800                  word(v, AHEAD, s, rp);                  word(v, AHEAD, s, rp);
801                  s = newstate(v->nfa);                  s = newstate(v->nfa);
802                  NOERR();                  NOERR();
803                  nonword(v, BEHIND, lp, s);                  nonword(v, BEHIND, lp, s);
804                  nonword(v, AHEAD, s, rp);                  nonword(v, AHEAD, s, rp);
805                  return;                  return;
806                  break;                  break;
807          case LACON:     /* lookahead constraint */          case LACON:     /* lookahead constraint */
808                  pos = v->nextvalue;                  pos = v->nextvalue;
809                  NEXT();                  NEXT();
810                  s = newstate(v->nfa);                  s = newstate(v->nfa);
811                  s2 = newstate(v->nfa);                  s2 = newstate(v->nfa);
812                  NOERR();                  NOERR();
813                  t = parse(v, ')', LACON, s, s2);                  t = parse(v, ')', LACON, s, s2);
814                  freesubre(v, t);        /* internal structure irrelevant */                  freesubre(v, t);        /* internal structure irrelevant */
815                  assert(SEE(')') || ISERR());                  assert(SEE(')') || ISERR());
816                  NEXT();                  NEXT();
817                  n = newlacon(v, s, s2, pos);                  n = newlacon(v, s, s2, pos);
818                  NOERR();                  NOERR();
819                  ARCV(LACON, n);                  ARCV(LACON, n);
820                  return;                  return;
821                  break;                  break;
822          /* then errors, to get them out of the way */          /* then errors, to get them out of the way */
823          case '*':          case '*':
824          case '+':          case '+':
825          case '?':          case '?':
826          case '{':          case '{':
827                  ERR(REG_BADRPT);                  ERR(REG_BADRPT);
828                  return;                  return;
829                  break;                  break;
830          default:          default:
831                  ERR(REG_ASSERT);                  ERR(REG_ASSERT);
832                  return;                  return;
833                  break;                  break;
834          /* then plain characters, and minor variants on that theme */          /* then plain characters, and minor variants on that theme */
835          case ')':               /* unbalanced paren */          case ')':               /* unbalanced paren */
836                  if ((v->cflags&REG_ADVANCED) != REG_EXTENDED) {                  if ((v->cflags&REG_ADVANCED) != REG_EXTENDED) {
837                          ERR(REG_EPAREN);                          ERR(REG_EPAREN);
838                          return;                          return;
839                  }                  }
840                  /* legal in EREs due to specification botch */                  /* legal in EREs due to specification botch */
841                  NOTE(REG_UPBOTCH);                  NOTE(REG_UPBOTCH);
842                  /* fallthrough into case PLAIN */                  /* fallthrough into case PLAIN */
843          case PLAIN:          case PLAIN:
844                  onechr(v, v->nextvalue, lp, rp);                  onechr(v, v->nextvalue, lp, rp);
845                  okcolors(v->nfa, v->cm);                  okcolors(v->nfa, v->cm);
846                  NOERR();                  NOERR();
847                  NEXT();                  NEXT();
848                  break;                  break;
849          case '[':          case '[':
850                  if (v->nextvalue == 1)                  if (v->nextvalue == 1)
851                          bracket(v, lp, rp);                          bracket(v, lp, rp);
852                  else                  else
853                          cbracket(v, lp, rp);                          cbracket(v, lp, rp);
854                  assert(SEE(']') || ISERR());                  assert(SEE(']') || ISERR());
855                  NEXT();                  NEXT();
856                  break;                  break;
857          case '.':          case '.':
858                  rainbow(v->nfa, v->cm, PLAIN,                  rainbow(v->nfa, v->cm, PLAIN,
859                                  (v->cflags&REG_NLSTOP) ? v->nlcolor : COLORLESS,                                  (v->cflags&REG_NLSTOP) ? v->nlcolor : COLORLESS,
860                                  lp, rp);                                  lp, rp);
861                  NEXT();                  NEXT();
862                  break;                  break;
863          /* and finally the ugly stuff */          /* and finally the ugly stuff */
864          case '(':       /* value flags as capturing or non */          case '(':       /* value flags as capturing or non */
865                  cap = (type == LACON) ? 0 : v->nextvalue;                  cap = (type == LACON) ? 0 : v->nextvalue;
866                  if (cap) {                  if (cap) {
867                          v->nsubexp++;                          v->nsubexp++;
868                          subno = v->nsubexp;                          subno = v->nsubexp;
869                          if ((size_t)subno >= v->nsubs)                          if ((size_t)subno >= v->nsubs)
870                                  moresubs(v, subno);                                  moresubs(v, subno);
871                          assert((size_t)subno < v->nsubs);                          assert((size_t)subno < v->nsubs);
872                  } else                  } else
873                          atomtype = PLAIN;       /* something that's not '(' */                          atomtype = PLAIN;       /* something that's not '(' */
874                  NEXT();                  NEXT();
875                  /* need new endpoints because tree will contain pointers */                  /* need new endpoints because tree will contain pointers */
876                  s = newstate(v->nfa);                  s = newstate(v->nfa);
877                  s2 = newstate(v->nfa);                  s2 = newstate(v->nfa);
878                  NOERR();                  NOERR();
879                  EMPTYARC(lp, s);                  EMPTYARC(lp, s);
880                  EMPTYARC(s2, rp);                  EMPTYARC(s2, rp);
881                  NOERR();                  NOERR();
882                  atom = parse(v, ')', PLAIN, s, s2);                  atom = parse(v, ')', PLAIN, s, s2);
883                  assert(SEE(')') || ISERR());                  assert(SEE(')') || ISERR());
884                  NEXT();                  NEXT();
885                  NOERR();                  NOERR();
886                  if (cap) {                  if (cap) {
887                          v->subs[subno] = atom;                          v->subs[subno] = atom;
888                          t = subre(v, '(', atom->flags|CAP, lp, rp);                          t = subre(v, '(', atom->flags|CAP, lp, rp);
889                          NOERR();                          NOERR();
890                          t->subno = subno;                          t->subno = subno;
891                          t->left = atom;                          t->left = atom;
892                          atom = t;                          atom = t;
893                  }                  }
894                  /* postpone everything else pending possible {0} */                  /* postpone everything else pending possible {0} */
895                  break;                  break;
896          case BACKREF:   /* the Feature From The Black Lagoon */          case BACKREF:   /* the Feature From The Black Lagoon */
897                  INSIST(type != LACON, REG_ESUBREG);                  INSIST(type != LACON, REG_ESUBREG);
898                  INSIST(v->nextvalue < v->nsubs, REG_ESUBREG);                  INSIST(v->nextvalue < v->nsubs, REG_ESUBREG);
899                  INSIST(v->subs[v->nextvalue] != NULL, REG_ESUBREG);                  INSIST(v->subs[v->nextvalue] != NULL, REG_ESUBREG);
900                  NOERR();                  NOERR();
901                  assert(v->nextvalue > 0);                  assert(v->nextvalue > 0);
902                  atom = subre(v, 'b', BACKR, lp, rp);                  atom = subre(v, 'b', BACKR, lp, rp);
903                  subno = v->nextvalue;                  subno = v->nextvalue;
904                  atom->subno = subno;                  atom->subno = subno;
905                  EMPTYARC(lp, rp);       /* temporarily, so there's something */                  EMPTYARC(lp, rp);       /* temporarily, so there's something */
906                  NEXT();                  NEXT();
907                  break;                  break;
908          }          }
909    
910          /* ...and an atom may be followed by a quantifier */          /* ...and an atom may be followed by a quantifier */
911          switch (v->nexttype) {          switch (v->nexttype) {
912          case '*':          case '*':
913                  m = 0;                  m = 0;
914                  n = INFINITY;                  n = INFINITY;
915                  qprefer = (v->nextvalue) ? LONGER : SHORTER;                  qprefer = (v->nextvalue) ? LONGER : SHORTER;
916                  NEXT();                  NEXT();
917                  break;                  break;
918          case '+':          case '+':
919                  m = 1;                  m = 1;
920                  n = INFINITY;                  n = INFINITY;
921                  qprefer = (v->nextvalue) ? LONGER : SHORTER;                  qprefer = (v->nextvalue) ? LONGER : SHORTER;
922                  NEXT();                  NEXT();
923                  break;                  break;
924          case '?':          case '?':
925                  m = 0;                  m = 0;
926                  n = 1;                  n = 1;
927                  qprefer = (v->nextvalue) ? LONGER : SHORTER;                  qprefer = (v->nextvalue) ? LONGER : SHORTER;
928                  NEXT();                  NEXT();
929                  break;                  break;
930          case '{':          case '{':
931                  NEXT();                  NEXT();
932                  m = scannum(v);                  m = scannum(v);
933                  if (EAT(',')) {                  if (EAT(',')) {
934                          if (SEE(DIGIT))                          if (SEE(DIGIT))
935                                  n = scannum(v);                                  n = scannum(v);
936                          else                          else
937                                  n = INFINITY;                                  n = INFINITY;
938                          if (m > n) {                          if (m > n) {
939                                  ERR(REG_BADBR);                                  ERR(REG_BADBR);
940                                  return;                                  return;
941                          }                          }
942                          /* {m,n} exercises preference, even if it's {m,m} */                          /* {m,n} exercises preference, even if it's {m,m} */
943                          qprefer = (v->nextvalue) ? LONGER : SHORTER;                          qprefer = (v->nextvalue) ? LONGER : SHORTER;
944                  } else {                  } else {
945                          n = m;                          n = m;
946                          /* {m} passes operand's preference through */                          /* {m} passes operand's preference through */
947                          qprefer = 0;                          qprefer = 0;
948                  }                  }
949                  if (!SEE('}')) {        /* catches errors too */                  if (!SEE('}')) {        /* catches errors too */
950                          ERR(REG_BADBR);                          ERR(REG_BADBR);
951                          return;                          return;
952                  }                  }
953                  NEXT();                  NEXT();
954                  break;                  break;
955          default:                /* no quantifier */          default:                /* no quantifier */
956                  m = n = 1;                  m = n = 1;
957                  qprefer = 0;                  qprefer = 0;
958                  break;                  break;
959          }          }
960    
961          /* annoying special case:  {0} or {0,0} cancels everything */          /* annoying special case:  {0} or {0,0} cancels everything */
962          if (m == 0 && n == 0) {          if (m == 0 && n == 0) {
963                  if (atom != NULL)                  if (atom != NULL)
964                          freesubre(v, atom);                          freesubre(v, atom);
965                  if (atomtype == '(')                  if (atomtype == '(')
966                          v->subs[subno] = NULL;                          v->subs[subno] = NULL;
967                  delsub(v->nfa, lp, rp);                  delsub(v->nfa, lp, rp);
968                  EMPTYARC(lp, rp);                  EMPTYARC(lp, rp);
969                  return;                  return;
970          }          }
971    
972          /* if not a messy case, avoid hard part */          /* if not a messy case, avoid hard part */
973          assert(!MESSY(top->flags));          assert(!MESSY(top->flags));
974          f = top->flags | qprefer | ((atom != NULL) ? atom->flags : 0);          f = top->flags | qprefer | ((atom != NULL) ? atom->flags : 0);
975          if (atomtype != '(' && atomtype != BACKREF && !MESSY(UP(f))) {          if (atomtype != '(' && atomtype != BACKREF && !MESSY(UP(f))) {
976                  if (!(m == 1 && n == 1))                  if (!(m == 1 && n == 1))
977                          repeat(v, lp, rp, m, n);                          repeat(v, lp, rp, m, n);
978                  if (atom != NULL)                  if (atom != NULL)
979                          freesubre(v, atom);                          freesubre(v, atom);
980                  top->flags = f;                  top->flags = f;
981                  return;                  return;
982          }          }
983    
984          /*          /*
985           * hard part:  something messy           * hard part:  something messy
986           * That is, capturing parens, back reference, short/long clash, or           * That is, capturing parens, back reference, short/long clash, or
987           * an atom with substructure containing one of those.           * an atom with substructure containing one of those.
988           */           */
989    
990          /* now we'll need a subre for the contents even if they're boring */          /* now we'll need a subre for the contents even if they're boring */
991          if (atom == NULL) {          if (atom == NULL) {
992                  atom = subre(v, '=', 0, lp, rp);                  atom = subre(v, '=', 0, lp, rp);
993                  NOERR();                  NOERR();
994          }          }
995    
996          /*          /*
997           * prepare a general-purpose state skeleton           * prepare a general-purpose state skeleton
998           *           *
999           *    ---> [s] ---prefix---> [begin] ---atom---> [end] ----rest---> [rp]           *    ---> [s] ---prefix---> [begin] ---atom---> [end] ----rest---> [rp]
1000           *   /                                            /           *   /                                            /
1001           * [lp] ----> [s2] ----bypass---------------------           * [lp] ----> [s2] ----bypass---------------------
1002           *           *
1003           * where bypass is an empty, and prefix is some repetitions of atom           * where bypass is an empty, and prefix is some repetitions of atom
1004           */           */
1005          s = newstate(v->nfa);           /* first, new endpoints for the atom */          s = newstate(v->nfa);           /* first, new endpoints for the atom */
1006          s2 = newstate(v->nfa);          s2 = newstate(v->nfa);
1007          NOERR();          NOERR();
1008          moveouts(v->nfa, lp, s);          moveouts(v->nfa, lp, s);
1009          moveins(v->nfa, rp, s2);          moveins(v->nfa, rp, s2);
1010          NOERR();          NOERR();
1011          atom->begin = s;          atom->begin = s;
1012          atom->end = s2;          atom->end = s2;
1013          s = newstate(v->nfa);           /* and spots for prefix and bypass */          s = newstate(v->nfa);           /* and spots for prefix and bypass */
1014          s2 = newstate(v->nfa);          s2 = newstate(v->nfa);
1015          NOERR();          NOERR();
1016          EMPTYARC(lp, s);          EMPTYARC(lp, s);
1017          EMPTYARC(lp, s2);          EMPTYARC(lp, s2);
1018          NOERR();          NOERR();
1019    
1020          /* break remaining subRE into x{...} and what follows */          /* break remaining subRE into x{...} and what follows */
1021          t = subre(v, '.', COMBINE(qprefer, atom->flags), lp, rp);          t = subre(v, '.', COMBINE(qprefer, atom->flags), lp, rp);
1022          t->left = atom;          t->left = atom;
1023          atomp = &t->left;          atomp = &t->left;
1024          /* here we should recurse... but we must postpone that to the end */          /* here we should recurse... but we must postpone that to the end */
1025    
1026          /* split top into prefix and remaining */          /* split top into prefix and remaining */
1027          assert(top->op == '=' && top->left == NULL && top->right == NULL);          assert(top->op == '=' && top->left == NULL && top->right == NULL);
1028          top->left = subre(v, '=', top->flags, top->begin, lp);          top->left = subre(v, '=', top->flags, top->begin, lp);
1029          top->op = '.';          top->op = '.';
1030          top->right = t;          top->right = t;
1031    
1032          /* if it's a backref, now is the time to replicate the subNFA */          /* if it's a backref, now is the time to replicate the subNFA */
1033          if (atomtype == BACKREF) {          if (atomtype == BACKREF) {
1034                  assert(atom->begin->nouts == 1);        /* just the EMPTY */                  assert(atom->begin->nouts == 1);        /* just the EMPTY */
1035                  delsub(v->nfa, atom->begin, atom->end);                  delsub(v->nfa, atom->begin, atom->end);
1036                  assert(v->subs[subno] != NULL);                  assert(v->subs[subno] != NULL);
1037                  /* and here's why the recursion got postponed:  it must */                  /* and here's why the recursion got postponed:  it must */
1038                  /* wait until the skeleton is filled in, because it may */                  /* wait until the skeleton is filled in, because it may */
1039                  /* hit a backref that wants to copy the filled-in skeleton */                  /* hit a backref that wants to copy the filled-in skeleton */
1040                  dupnfa(v->nfa, v->subs[subno]->begin, v->subs[subno]->end,                  dupnfa(v->nfa, v->subs[subno]->begin, v->subs[subno]->end,
1041                                                  atom->begin, atom->end);                                                  atom->begin, atom->end);
1042                  NOERR();                  NOERR();
1043          }          }
1044    
1045          /* it's quantifier time; first, turn x{0,...} into x{1,...}|empty */          /* it's quantifier time; first, turn x{0,...} into x{1,...}|empty */
1046          if (m == 0) {          if (m == 0) {
1047                  EMPTYARC(s2, atom->end);                /* the bypass */                  EMPTYARC(s2, atom->end);                /* the bypass */
1048                  assert(PREF(qprefer) != 0);                  assert(PREF(qprefer) != 0);
1049                  f = COMBINE(qprefer, atom->flags);                  f = COMBINE(qprefer, atom->flags);
1050                  t = subre(v, '|', f, lp, atom->end);                  t = subre(v, '|', f, lp, atom->end);
1051                  NOERR();                  NOERR();
1052                  t->left = atom;                  t->left = atom;
1053                  t->right = subre(v, '|', PREF(f), s2, atom->end);                  t->right = subre(v, '|', PREF(f), s2, atom->end);
1054                  NOERR();                  NOERR();
1055                  t->right->left = subre(v, '=', 0, s2, atom->end);                  t->right->left = subre(v, '=', 0, s2, atom->end);
1056                  NOERR();                  NOERR();
1057                  *atomp = t;                  *atomp = t;
1058                  atomp = &t->left;                  atomp = &t->left;
1059                  m = 1;                  m = 1;
1060          }          }
1061    
1062          /* deal with the rest of the quantifier */          /* deal with the rest of the quantifier */
1063          if (atomtype == BACKREF) {          if (atomtype == BACKREF) {
1064                  /* special case:  backrefs have internal quantifiers */                  /* special case:  backrefs have internal quantifiers */
1065                  EMPTYARC(s, atom->begin);       /* empty prefix */                  EMPTYARC(s, atom->begin);       /* empty prefix */
1066                  /* just stuff everything into atom */                  /* just stuff everything into atom */
1067                  repeat(v, atom->begin, atom->end, m, n);                  repeat(v, atom->begin, atom->end, m, n);
1068                  atom->min = (short)m;                  atom->min = (short)m;
1069                  atom->max = (short)n;                  atom->max = (short)n;
1070                  atom->flags |= COMBINE(qprefer, atom->flags);                  atom->flags |= COMBINE(qprefer, atom->flags);
1071          } else if (m == 1 && n == 1) {          } else if (m == 1 && n == 1) {
1072                  /* no/vacuous quantifier:  done */                  /* no/vacuous quantifier:  done */
1073                  EMPTYARC(s, atom->begin);       /* empty prefix */                  EMPTYARC(s, atom->begin);       /* empty prefix */
1074          } else {          } else {
1075                  /* turn x{m,n} into x{m-1,n-1}x, with capturing */                  /* turn x{m,n} into x{m-1,n-1}x, with capturing */
1076                  /*  parens in only second x */                  /*  parens in only second x */
1077                  dupnfa(v->nfa, atom->begin, atom->end, s, atom->begin);                  dupnfa(v->nfa, atom->begin, atom->end, s, atom->begin);
1078                  assert(m >= 1 && m != INFINITY && n >= 1);                  assert(m >= 1 && m != INFINITY && n >= 1);
1079                  repeat(v, s, atom->begin, m-1, (n == INFINITY) ? n : n-1);                  repeat(v, s, atom->begin, m-1, (n == INFINITY) ? n : n-1);
1080                  f = COMBINE(qprefer, atom->flags);                  f = COMBINE(qprefer, atom->flags);
1081                  t = subre(v, '.', f, s, atom->end);     /* prefix and atom */                  t = subre(v, '.', f, s, atom->end);     /* prefix and atom */
1082                  NOERR();                  NOERR();
1083                  t->left = subre(v, '=', PREF(f), s, atom->begin);                  t->left = subre(v, '=', PREF(f), s, atom->begin);
1084                  NOERR();                  NOERR();
1085                  t->right = atom;                  t->right = atom;
1086                  *atomp = t;                  *atomp = t;
1087          }          }
1088    
1089          /* and finally, look after that postponed recursion */          /* and finally, look after that postponed recursion */
1090          t = top->right;          t = top->right;
1091          if (!(SEE('|') || SEE(stopper) || SEE(EOS)))          if (!(SEE('|') || SEE(stopper) || SEE(EOS)))
1092                  t->right = parsebranch(v, stopper, type, atom->end, rp, 1);                  t->right = parsebranch(v, stopper, type, atom->end, rp, 1);
1093          else {          else {
1094                  EMPTYARC(atom->end, rp);                  EMPTYARC(atom->end, rp);
1095                  t->right = subre(v, '=', 0, atom->end, rp);                  t->right = subre(v, '=', 0, atom->end, rp);
1096          }          }
1097          assert(SEE('|') || SEE(stopper) || SEE(EOS));          assert(SEE('|') || SEE(stopper) || SEE(EOS));
1098          t->flags |= COMBINE(t->flags, t->right->flags);          t->flags |= COMBINE(t->flags, t->right->flags);
1099          top->flags |= COMBINE(top->flags, t->flags);          top->flags |= COMBINE(top->flags, t->flags);
1100  }  }
1101    
1102  /*  /*
1103   - nonword - generate arcs for non-word-character ahead or behind   - nonword - generate arcs for non-word-character ahead or behind
1104   ^ static VOID nonword(struct vars *, int, struct state *, struct state *);   ^ static VOID nonword(struct vars *, int, struct state *, struct state *);
1105   */   */
1106  static VOID  static VOID
1107  nonword(v, dir, lp, rp)  nonword(v, dir, lp, rp)
1108  struct vars *v;  struct vars *v;
1109  int dir;                        /* AHEAD or BEHIND */  int dir;                        /* AHEAD or BEHIND */
1110  struct state *lp;  struct state *lp;
1111  struct state *rp;  struct state *rp;
1112  {  {
1113          int anchor = (dir == AHEAD) ? '$' : '^';          int anchor = (dir == AHEAD) ? '$' : '^';
1114    
1115          assert(dir == AHEAD || dir == BEHIND);          assert(dir == AHEAD || dir == BEHIND);
1116          newarc(v->nfa, anchor, 1, lp, rp);          newarc(v->nfa, anchor, 1, lp, rp);
1117          newarc(v->nfa, anchor, 0, lp, rp);          newarc(v->nfa, anchor, 0, lp, rp);
1118          colorcomplement(v->nfa, v->cm, dir, v->wordchrs, lp, rp);          colorcomplement(v->nfa, v->cm, dir, v->wordchrs, lp, rp);
1119          /* (no need for special attention to \n) */          /* (no need for special attention to \n) */
1120  }  }
1121    
1122  /*  /*
1123   - word - generate arcs for word character ahead or behind   - word - generate arcs for word character ahead or behind
1124   ^ static VOID word(struct vars *, int, struct state *, struct state *);   ^ static VOID word(struct vars *, int, struct state *, struct state *);
1125   */   */
1126  static VOID  static VOID
1127  word(v, dir, lp, rp)  word(v, dir, lp, rp)
1128  struct vars *v;  struct vars *v;
1129  int dir;                        /* AHEAD or BEHIND */  int dir;                        /* AHEAD or BEHIND */
1130  struct state *lp;  struct state *lp;
1131  struct state *rp;  struct state *rp;
1132  {  {
1133          assert(dir == AHEAD || dir == BEHIND);          assert(dir == AHEAD || dir == BEHIND);
1134          cloneouts(v->nfa, v->wordchrs, lp, rp, dir);          cloneouts(v->nfa, v->wordchrs, lp, rp, dir);
1135          /* (no need for special attention to \n) */          /* (no need for special attention to \n) */
1136  }  }
1137    
1138  /*  /*
1139   - scannum - scan a number   - scannum - scan a number
1140   ^ static int scannum(struct vars *);   ^ static int scannum(struct vars *);
1141   */   */
1142  static int                      /* value, <= DUPMAX */  static int                      /* value, <= DUPMAX */
1143  scannum(v)  scannum(v)
1144  struct vars *v;  struct vars *v;
1145  {  {
1146          int n = 0;          int n = 0;
1147    
1148          while (SEE(DIGIT) && n < DUPMAX) {          while (SEE(DIGIT) && n < DUPMAX) {
1149                  n = n*10 + v->nextvalue;                  n = n*10 + v->nextvalue;
1150                  NEXT();                  NEXT();
1151          }          }
1152          if (SEE(DIGIT) || n > DUPMAX) {          if (SEE(DIGIT) || n > DUPMAX) {
1153                  ERR(REG_BADBR);                  ERR(REG_BADBR);
1154                  return 0;                  return 0;
1155          }          }
1156          return n;          return n;
1157  }  }
1158    
1159  /*  /*
1160   - repeat - replicate subNFA for quantifiers   - repeat - replicate subNFA for quantifiers
1161   * The duplication sequences used here are chosen carefully so that any   * The duplication sequences used here are chosen carefully so that any
1162   * pointers starting out pointing into the subexpression end up pointing into   * pointers starting out pointing into the subexpression end up pointing into
1163   * the last occurrence.  (Note that it may not be strung between the same   * the last occurrence.  (Note that it may not be strung between the same
1164   * left and right end states, however!)  This used to be important for the   * left and right end states, however!)  This used to be important for the
1165   * subRE tree, although the important bits are now handled by the in-line   * subRE tree, although the important bits are now handled by the in-line
1166   * code in parse(), and when this is called, it doesn't matter any more.   * code in parse(), and when this is called, it doesn't matter any more.
1167   ^ static VOID repeat(struct vars *, struct state *, struct state *, int, int);   ^ static VOID repeat(struct vars *, struct state *, struct state *, int, int);
1168   */   */
1169  static VOID  static VOID
1170  repeat(v, lp, rp, m, n)  repeat(v, lp, rp, m, n)
1171  struct vars *v;  struct vars *v;
1172  struct state *lp;  struct state *lp;
1173  struct state *rp;  struct state *rp;
1174  int m;  int m;
1175  int n;  int n;
1176  {  {
1177  #       define  SOME    2  #       define  SOME    2
1178  #       define  INF     3  #       define  INF     3
1179  #       define  PAIR(x, y)      ((x)*4 + (y))  #       define  PAIR(x, y)      ((x)*4 + (y))
1180  #       define  REDUCE(x)       ( ((x) == INFINITY) ? INF : (((x) > 1) ? SOME : (x)) )  #       define  REDUCE(x)       ( ((x) == INFINITY) ? INF : (((x) > 1) ? SOME : (x)) )
1181          CONST int rm = REDUCE(m);          CONST int rm = REDUCE(m);
1182          CONST int rn = REDUCE(n);          CONST int rn = REDUCE(n);
1183          struct state *s;          struct state *s;
1184          struct state *s2;          struct state *s2;
1185    
1186          switch (PAIR(rm, rn)) {          switch (PAIR(rm, rn)) {
1187          case PAIR(0, 0):                /* empty string */          case PAIR(0, 0):                /* empty string */
1188                  delsub(v->nfa, lp, rp);                  delsub(v->nfa, lp, rp);
1189                  EMPTYARC(lp, rp);                  EMPTYARC(lp, rp);
1190                  break;                  break;
1191          case PAIR(0, 1):                /* do as x| */          case PAIR(0, 1):                /* do as x| */
1192                  EMPTYARC(lp, rp);                  EMPTYARC(lp, rp);
1193                  break;                  break;
1194          case PAIR(0, SOME):             /* do as x{1,n}| */          case PAIR(0, SOME):             /* do as x{1,n}| */
1195                  repeat(v, lp, rp, 1, n);                  repeat(v, lp, rp, 1, n);
1196                  NOERR();                  NOERR();
1197                  EMPTYARC(lp, rp);                  EMPTYARC(lp, rp);
1198                  break;                  break;
1199          case PAIR(0, INF):              /* loop x around */          case PAIR(0, INF):              /* loop x around */
1200                  s = newstate(v->nfa);                  s = newstate(v->nfa);
1201                  NOERR();                  NOERR();
1202                  moveouts(v->nfa, lp, s);                  moveouts(v->nfa, lp, s);
1203                  moveins(v->nfa, rp, s);                  moveins(v->nfa, rp, s);
1204                  EMPTYARC(lp, s);                  EMPTYARC(lp, s);
1205                  EMPTYARC(s, rp);                  EMPTYARC(s, rp);
1206                  break;                  break;
1207          case PAIR(1, 1):                /* no action required */          case PAIR(1, 1):                /* no action required */
1208                  break;                  break;
1209          case PAIR(1, SOME):             /* do as x{0,n-1}x = (x{1,n-1}|)x */          case PAIR(1, SOME):             /* do as x{0,n-1}x = (x{1,n-1}|)x */
1210                  s = newstate(v->nfa);                  s = newstate(v->nfa);
1211                  NOERR();                  NOERR();
1212                  moveouts(v->nfa, lp, s);                  moveouts(v->nfa, lp, s);
1213                  dupnfa(v->nfa, s, rp, lp, s);                  dupnfa(v->nfa, s, rp, lp, s);
1214                  NOERR();                  NOERR();
1215                  repeat(v, lp, s, 1, n-1);                  repeat(v, lp, s, 1, n-1);
1216                  NOERR();                  NOERR();
1217                  EMPTYARC(lp, s);                  EMPTYARC(lp, s);
1218                  break;                  break;
1219          case PAIR(1, INF):              /* add loopback arc */          case PAIR(1, INF):              /* add loopback arc */
1220                  s = newstate(v->nfa);                  s = newstate(v->nfa);
1221                  s2 = newstate(v->nfa);                  s2 = newstate(v->nfa);
1222                  NOERR();                  NOERR();
1223                  moveouts(v->nfa, lp, s);                  moveouts(v->nfa, lp, s);
1224                  moveins(v->nfa, rp, s2);                  moveins(v->nfa, rp, s2);
1225                  EMPTYARC(lp, s);                  EMPTYARC(lp, s);
1226                  EMPTYARC(s2, rp);                  EMPTYARC(s2, rp);
1227                  EMPTYARC(s2, s);                  EMPTYARC(s2, s);
1228                  break;                  break;
1229          case PAIR(SOME, SOME):          /* do as x{m-1,n-1}x */          case PAIR(SOME, SOME):          /* do as x{m-1,n-1}x */
1230                  s = newstate(v->nfa);                  s = newstate(v->nfa);
1231                  NOERR();                  NOERR();
1232                  moveouts(v->nfa, lp, s);                  moveouts(v->nfa, lp, s);
1233                  dupnfa(v->nfa, s, rp, lp, s);                  dupnfa(v->nfa, s, rp, lp, s);
1234                  NOERR();                  NOERR();
1235                  repeat(v, lp, s, m-1, n-1);                  repeat(v, lp, s, m-1, n-1);
1236                  break;                  break;
1237          case PAIR(SOME, INF):           /* do as x{m-1,}x */          case PAIR(SOME, INF):           /* do as x{m-1,}x */
1238                  s = newstate(v->nfa);                  s = newstate(v->nfa);
1239                  NOERR();                  NOERR();
1240                  moveouts(v->nfa, lp, s);                  moveouts(v->nfa, lp, s);
1241                  dupnfa(v->nfa, s, rp, lp, s);                  dupnfa(v->nfa, s, rp, lp, s);
1242                  NOERR();                  NOERR();
1243                  repeat(v, lp, s, m-1, n);                  repeat(v, lp, s, m-1, n);
1244                  break;                  break;
1245          default:          default:
1246                  ERR(REG_ASSERT);                  ERR(REG_ASSERT);
1247                  break;                  break;
1248          }          }
1249  }  }
1250    
1251  /*  /*
1252   - bracket - handle non-complemented bracket expression   - bracket - handle non-complemented bracket expression
1253   * Also called from cbracket for complemented bracket expressions.   * Also called from cbracket for complemented bracket expressions.
1254   ^ static VOID bracket(struct vars *, struct state *, struct state *);   ^ static VOID bracket(struct vars *, struct state *, struct state *);
1255   */   */
1256  static VOID  static VOID
1257  bracket(v, lp, rp)  bracket(v, lp, rp)
1258  struct vars *v;  struct vars *v;
1259  struct state *lp;  struct state *lp;
1260  struct state *rp;  struct state *rp;
1261  {  {
1262          assert(SEE('['));          assert(SEE('['));
1263          NEXT();          NEXT();
1264          while (!SEE(']') && !SEE(EOS))          while (!SEE(']') && !SEE(EOS))
1265                  brackpart(v, lp, rp);                  brackpart(v, lp, rp);
1266          assert(SEE(']') || ISERR());          assert(SEE(']') || ISERR());
1267          okcolors(v->nfa, v->cm);          okcolors(v->nfa, v->cm);
1268  }  }
1269    
1270  /*  /*
1271   - cbracket - handle complemented bracket expression   - cbracket - handle complemented bracket expression
1272   * We do it by calling bracket() with dummy endpoints, and then complementing   * We do it by calling bracket() with dummy endpoints, and then complementing
1273   * the result.  The alternative would be to invoke rainbow(), and then delete   * the result.  The alternative would be to invoke rainbow(), and then delete
1274   * arcs as the b.e. is seen... but that gets messy.   * arcs as the b.e. is seen... but that gets messy.
1275   ^ static VOID cbracket(struct vars *, struct state *, struct state *);   ^ static VOID cbracket(struct vars *, struct state *, struct state *);
1276   */   */
1277  static VOID  static VOID
1278  cbracket(v, lp, rp)  cbracket(v, lp, rp)
1279  struct vars *v;  struct vars *v;
1280  struct state *lp;  struct state *lp;
1281  struct state *rp;  struct state *rp;
1282  {  {
1283          struct state *left = newstate(v->nfa);          struct state *left = newstate(v->nfa);
1284          struct state *right = newstate(v->nfa);          struct state *right = newstate(v->nfa);
1285          struct state *s;          struct state *s;
1286          struct arc *a;                  /* arc from lp */          struct arc *a;                  /* arc from lp */
1287          struct arc *ba;                 /* arc from left, from bracket() */          struct arc *ba;                 /* arc from left, from bracket() */
1288          struct arc *pa;                 /* MCCE-prototype arc */          struct arc *pa;                 /* MCCE-prototype arc */
1289          color co;          color co;
1290          chr *p;          chr *p;
1291          int i;          int i;
1292    
1293          NOERR();          NOERR();
1294          bracket(v, left, right);          bracket(v, left, right);
1295          if (v->cflags&REG_NLSTOP)          if (v->cflags&REG_NLSTOP)
1296                  newarc(v->nfa, PLAIN, v->nlcolor, left, right);                  newarc(v->nfa, PLAIN, v->nlcolor, left, right);
1297          NOERR();          NOERR();
1298    
1299          assert(lp->nouts == 0);         /* all outarcs will be ours */          assert(lp->nouts == 0);         /* all outarcs will be ours */
1300    
1301          /* easy part of complementing */          /* easy part of complementing */
1302          colorcomplement(v->nfa, v->cm, PLAIN, left, lp, rp);          colorcomplement(v->nfa, v->cm, PLAIN, left, lp, rp);
1303          NOERR();          NOERR();
1304          if (v->mcces == NULL) {         /* no MCCEs -- we're done */          if (v->mcces == NULL) {         /* no MCCEs -- we're done */
1305                  dropstate(v->nfa, left);                  dropstate(v->nfa, left);
1306                  assert(right->nins == 0);                  assert(right->nins == 0);
1307                  freestate(v->nfa, right);                  freestate(v->nfa, right);
1308                  return;                  return;
1309          }          }
1310    
1311          /* but complementing gets messy in the presence of MCCEs... */          /* but complementing gets messy in the presence of MCCEs... */
1312          NOTE(REG_ULOCALE);          NOTE(REG_ULOCALE);
1313          for (p = v->mcces->chrs, i = v->mcces->nchrs; i > 0; p++, i--) {          for (p = v->mcces->chrs, i = v->mcces->nchrs; i > 0; p++, i--) {
1314                  co = GETCOLOR(v->cm, *p);                  co = GETCOLOR(v->cm, *p);
1315                  a = findarc(lp, PLAIN, co);                  a = findarc(lp, PLAIN, co);
1316                  ba = findarc(left, PLAIN, co);                  ba = findarc(left, PLAIN, co);
1317                  if (ba == NULL) {                  if (ba == NULL) {
1318                          assert(a != NULL);                          assert(a != NULL);
1319                          freearc(v->nfa, a);                          freearc(v->nfa, a);
1320                  } else {                  } else {
1321                          assert(a == NULL);                          assert(a == NULL);
1322                  }                  }
1323                  s = newstate(v->nfa);                  s = newstate(v->nfa);
1324                  NOERR();                  NOERR();
1325                  newarc(v->nfa, PLAIN, co, lp, s);                  newarc(v->nfa, PLAIN, co, lp, s);
1326                  NOERR();                  NOERR();
1327                  pa = findarc(v->mccepbegin, PLAIN, co);                  pa = findarc(v->mccepbegin, PLAIN, co);
1328                  assert(pa != NULL);                  assert(pa != NULL);
1329                  if (ba == NULL) {       /* easy case, need all of them */                  if (ba == NULL) {       /* easy case, need all of them */
1330                          cloneouts(v->nfa, pa->to, s, rp, PLAIN);                          cloneouts(v->nfa, pa->to, s, rp, PLAIN);
1331                          newarc(v->nfa, '$', 1, s, rp);                          newarc(v->nfa, '$', 1, s, rp);
1332                          newarc(v->nfa, '$', 0, s, rp);                          newarc(v->nfa, '$', 0, s, rp);
1333                          colorcomplement(v->nfa, v->cm, AHEAD, pa->to, s, rp);                          colorcomplement(v->nfa, v->cm, AHEAD, pa->to, s, rp);
1334                  } else {                /* must be selective */                  } else {                /* must be selective */
1335                          if (findarc(ba->to, '$', 1) == NULL) {                          if (findarc(ba->to, '$', 1) == NULL) {
1336                                  newarc(v->nfa, '$', 1, s, rp);                                  newarc(v->nfa, '$', 1, s, rp);
1337                                  newarc(v->nfa, '$', 0, s, rp);                                  newarc(v->nfa, '$', 0, s, rp);
1338                                  colorcomplement(v->nfa, v->cm, AHEAD, pa->to,                                  colorcomplement(v->nfa, v->cm, AHEAD, pa->to,
1339                                                                           s, rp);                                                                           s, rp);
1340                          }                          }
1341                          for (pa = pa->to->outs; pa != NULL; pa = pa->outchain)                          for (pa = pa->to->outs; pa != NULL; pa = pa->outchain)
1342                                  if (findarc(ba->to, PLAIN, pa->co) == NULL)                                  if (findarc(ba->to, PLAIN, pa->co) == NULL)
1343                                          newarc(v->nfa, PLAIN, pa->co, s, rp);                                          newarc(v->nfa, PLAIN, pa->co, s, rp);
1344                          if (s->nouts == 0)      /* limit of selectivity: none */                          if (s->nouts == 0)      /* limit of selectivity: none */
1345                                  dropstate(v->nfa, s);   /* frees arc too */                                  dropstate(v->nfa, s);   /* frees arc too */
1346                  }                  }
1347                  NOERR();                  NOERR();
1348          }          }
1349    
1350          delsub(v->nfa, left, right);          delsub(v->nfa, left, right);
1351          assert(left->nouts == 0);          assert(left->nouts == 0);
1352          freestate(v->nfa, left);          freestate(v->nfa, left);
1353          assert(right->nins == 0);          assert(right->nins == 0);
1354          freestate(v->nfa, right);          freestate(v->nfa, right);
1355  }  }
1356                                                    
1357  /*  /*
1358   - brackpart - handle one item (or range) within a bracket expression   - brackpart - handle one item (or range) within a bracket expression
1359   ^ static VOID brackpart(struct vars *, struct state *, struct state *);   ^ static VOID brackpart(struct vars *, struct state *, struct state *);
1360   */   */
1361  static VOID  static VOID
1362  brackpart(v, lp, rp)  brackpart(v, lp, rp)
1363  struct vars *v;  struct vars *v;
1364  struct state *lp;  struct state *lp;
1365  struct state *rp;  struct state *rp;
1366  {  {
1367          celt startc;          celt startc;
1368          celt endc;          celt endc;
1369          struct cvec *cv;          struct cvec *cv;
1370          chr *startp;          chr *startp;
1371          chr *endp;          chr *endp;
1372          chr c[1];          chr c[1];
1373    
1374          /* parse something, get rid of special cases, take shortcuts */          /* parse something, get rid of special cases, take shortcuts */
1375          switch (v->nexttype) {          switch (v->nexttype) {
1376          case RANGE:                     /* a-b-c or other botch */          case RANGE:                     /* a-b-c or other botch */
1377                  ERR(REG_ERANGE);                  ERR(REG_ERANGE);
1378                  return;                  return;
1379                  break;                  break;
1380          case PLAIN:          case PLAIN:
1381                  c[0] = v->nextvalue;                  c[0] = v->nextvalue;
1382                  NEXT();                  NEXT();
1383                  /* shortcut for ordinary chr (not range, not MCCE leader) */                  /* shortcut for ordinary chr (not range, not MCCE leader) */
1384                  if (!SEE(RANGE) && !ISCELEADER(v, c[0])) {                  if (!SEE(RANGE) && !ISCELEADER(v, c[0])) {
1385                          onechr(v, c[0], lp, rp);                          onechr(v, c[0], lp, rp);
1386                          return;                          return;
1387                  }                  }
1388                  startc = element(v, c, c+1);                  startc = element(v, c, c+1);
1389                  NOERR();                  NOERR();
1390                  break;                  break;
1391          case COLLEL:          case COLLEL:
1392                  startp = v->now;                  startp = v->now;
1393                  endp = scanplain(v);                  endp = scanplain(v);
1394                  INSIST(startp < endp, REG_ECOLLATE);                  INSIST(startp < endp, REG_ECOLLATE);
1395                  NOERR();                  NOERR();
1396                  startc = element(v, startp, endp);                  startc = element(v, startp, endp);
1397                  NOERR();                  NOERR();
1398                  break;                  break;
1399          case ECLASS:          case ECLASS:
1400                  startp = v->now;                  startp = v->now;
1401                  endp = scanplain(v);                  endp = scanplain(v);
1402                  INSIST(startp < endp, REG_ECOLLATE);                  INSIST(startp < endp, REG_ECOLLATE);
1403                  NOERR();                  NOERR();
1404                  startc = element(v, startp, endp);                  startc = element(v, startp, endp);
1405                  NOERR();                  NOERR();
1406                  cv = eclass(v, startc, (v->cflags&REG_ICASE));                  cv = eclass(v, startc, (v->cflags&REG_ICASE));
1407                  NOERR();                  NOERR();
1408                  dovec(v, cv, lp, rp);                  dovec(v, cv, lp, rp);
1409                  return;                  return;
1410                  break;                  break;
1411          case CCLASS:          case CCLASS:
1412                  startp = v->now;                  startp = v->now;
1413                  endp = scanplain(v);                  endp = scanplain(v);
1414                  INSIST(startp < endp, REG_ECTYPE);                  INSIST(startp < endp, REG_ECTYPE);
1415                  NOERR();                  NOERR();
1416                  cv = cclass(v, startp, endp, (v->cflags&REG_ICASE));                  cv = cclass(v, startp, endp, (v->cflags&REG_ICASE));
1417                  NOERR();                  NOERR();
1418                  dovec(v, cv, lp, rp);                  dovec(v, cv, lp, rp);
1419                  return;                  return;
1420                  break;                  break;
1421          default:          default:
1422                  ERR(REG_ASSERT);                  ERR(REG_ASSERT);
1423                  return;                  return;
1424                  break;                  break;
1425          }          }
1426    
1427          if (SEE(RANGE)) {          if (SEE(RANGE)) {
1428                  NEXT();                  NEXT();
1429                  switch (v->nexttype) {                  switch (v->nexttype) {
1430                  case PLAIN:                  case PLAIN:
1431                  case RANGE:                  case RANGE:
1432                          c[0] = v->nextvalue;                          c[0] = v->nextvalue;
1433                          NEXT();                          NEXT();
1434                          endc = element(v, c, c+1);                          endc = element(v, c, c+1);
1435                          NOERR();                          NOERR();
1436                          break;                          break;
1437                  case COLLEL:                  case COLLEL:
1438                          startp = v->now;                          startp = v->now;
1439                          endp = scanplain(v);                          endp = scanplain(v);
1440                          INSIST(startp < endp, REG_ECOLLATE);                          INSIST(startp < endp, REG_ECOLLATE);
1441                          NOERR();                          NOERR();
1442                          endc = element(v, startp, endp);                          endc = element(v, startp, endp);
1443                          NOERR();                          NOERR();
1444                          break;                          break;
1445                  default:                  default:
1446                          ERR(REG_ERANGE);                          ERR(REG_ERANGE);
1447                          return;                          return;
1448                          break;                          break;
1449                  }                  }
1450          } else          } else
1451                  endc = startc;                  endc = startc;
1452    
1453          /*          /*
1454           * Ranges are unportable.  Actually, standard C does           * Ranges are unportable.  Actually, standard C does
1455           * guarantee that digits are contiguous, but making           * guarantee that digits are contiguous, but making
1456           * that an exception is just too complicated.           * that an exception is just too complicated.
1457           */           */
1458          if (startc != endc)          if (startc != endc)
1459                  NOTE(REG_UUNPORT);                  NOTE(REG_UUNPORT);
1460          cv = range(v, startc, endc, (v->cflags&REG_ICASE));          cv = range(v, startc, endc, (v->cflags&REG_ICASE));
1461          NOERR();          NOERR();
1462          dovec(v, cv, lp, rp);          dovec(v, cv, lp, rp);
1463  }  }
1464    
1465  /*  /*
1466   - scanplain - scan PLAIN contents of [. etc.   - scanplain - scan PLAIN contents of [. etc.
1467   * Certain bits of trickery in lex.c know that this code does not try   * Certain bits of trickery in lex.c know that this code does not try
1468   * to look past the final bracket of the [. etc.   * to look past the final bracket of the [. etc.
1469   ^ static chr *scanplain(struct vars *);   ^ static chr *scanplain(struct vars *);
1470   */   */
1471  static chr *                    /* just after end of sequence */  static chr *                    /* just after end of sequence */
1472  scanplain(v)  scanplain(v)
1473  struct vars *v;  struct vars *v;
1474  {  {
1475          chr *endp;          chr *endp;
1476    
1477          assert(SEE(COLLEL) || SEE(ECLASS) || SEE(CCLASS));          assert(SEE(COLLEL) || SEE(ECLASS) || SEE(CCLASS));
1478          NEXT();          NEXT();
1479    
1480          endp = v->now;          endp = v->now;
1481          while (SEE(PLAIN)) {          while (SEE(PLAIN)) {
1482                  endp = v->now;                  endp = v->now;
1483                  NEXT();                  NEXT();
1484          }          }
1485    
1486          assert(SEE(END) || ISERR());          assert(SEE(END) || ISERR());
1487          NEXT();          NEXT();
1488    
1489          return endp;          return endp;
1490  }  }
1491    
1492  /*  /*
1493   - leaders - process a cvec of collating elements to also include leaders   - leaders - process a cvec of collating elements to also include leaders
1494   * Also gives all characters involved their own colors, which is almost   * Also gives all characters involved their own colors, which is almost
1495   * certainly necessary, and sets up little disconnected subNFA.   * certainly necessary, and sets up little disconnected subNFA.
1496   ^ static VOID leaders(struct vars *, struct cvec *);   ^ static VOID leaders(struct vars *, struct cvec *);
1497   */   */
1498  static VOID  static VOID
1499  leaders(v, cv)  leaders(v, cv)
1500  struct vars *v;  struct vars *v;
1501  struct cvec *cv;  struct cvec *cv;
1502  {  {
1503          int mcce;          int mcce;
1504          chr *p;          chr *p;
1505          chr leader;          chr leader;
1506          struct state *s;          struct state *s;
1507          struct arc *a;          struct arc *a;
1508    
1509          v->mccepbegin = newstate(v->nfa);          v->mccepbegin = newstate(v->nfa);
1510          v->mccepend = newstate(v->nfa);          v->mccepend = newstate(v->nfa);
1511          NOERR();          NOERR();
1512    
1513          for (mcce = 0; mcce < cv->nmcces; mcce++) {          for (mcce = 0; mcce < cv->nmcces; mcce++) {
1514                  p = cv->mcces[mcce];                  p = cv->mcces[mcce];
1515                  leader = *p;                  leader = *p;
1516                  if (!haschr(cv, leader)) {                  if (!haschr(cv, leader)) {
1517                          addchr(cv, leader);                          addchr(cv, leader);
1518                          s = newstate(v->nfa);                          s = newstate(v->nfa);
1519                          newarc(v->nfa, PLAIN, subcolor(v->cm, leader),                          newarc(v->nfa, PLAIN, subcolor(v->cm, leader),
1520                                                          v->mccepbegin, s);                                                          v->mccepbegin, s);
1521                          okcolors(v->nfa, v->cm);                          okcolors(v->nfa, v->cm);
1522                  } else {                  } else {
1523                          a = findarc(v->mccepbegin, PLAIN,                          a = findarc(v->mccepbegin, PLAIN,
1524                                                  GETCOLOR(v->cm, leader));                                                  GETCOLOR(v->cm, leader));
1525                          assert(a != NULL);                          assert(a != NULL);
1526                          s = a->to;                          s = a->to;
1527                          assert(s != v->mccepend);                          assert(s != v->mccepend);
1528                  }                  }
1529                  p++;                  p++;
1530                  assert(*p != 0 && *(p+1) == 0); /* only 2-char MCCEs for now */                  assert(*p != 0 && *(p+1) == 0); /* only 2-char MCCEs for now */
1531                  newarc(v->nfa, PLAIN, subcolor(v->cm, *p), s, v->mccepend);                  newarc(v->nfa, PLAIN, subcolor(v->cm, *p), s, v->mccepend);
1532                  okcolors(v->nfa, v->cm);                  okcolors(v->nfa, v->cm);
1533          }          }
1534  }  }
1535    
1536  /*  /*
1537   - onechr - fill in arcs for a plain character, and possible case complements   - onechr - fill in arcs for a plain character, and possible case complements
1538   * This is mostly a shortcut for efficient handling of the common case.   * This is mostly a shortcut for efficient handling of the common case.
1539   ^ static VOID onechr(struct vars *, pchr, struct state *, struct state *);   ^ static VOID onechr(struct vars *, pchr, struct state *, struct state *);
1540   */   */
1541  static VOID  static VOID
1542  onechr(v, c, lp, rp)  onechr(v, c, lp, rp)
1543  struct vars *v;  struct vars *v;
1544  pchr c;  pchr c;
1545  struct state *lp;  struct state *lp;
1546  struct state *rp;  struct state *rp;
1547  {  {
1548          if (!(v->cflags&REG_ICASE)) {          if (!(v->cflags&REG_ICASE)) {
1549                  newarc(v->nfa, PLAIN, subcolor(v->cm, c), lp, rp);                  newarc(v->nfa, PLAIN, subcolor(v->cm, c), lp, rp);
1550                  return;                  return;
1551          }          }
1552    
1553          /* rats, need general case anyway... */          /* rats, need general case anyway... */
1554          dovec(v, allcases(v, c), lp, rp);          dovec(v, allcases(v, c), lp, rp);
1555  }  }
1556    
1557  /*  /*
1558   - dovec - fill in arcs for each element of a cvec   - dovec - fill in arcs for each element of a cvec
1559   * This one has to handle the messy cases, like MCCEs and MCCE leaders.   * This one has to handle the messy cases, like MCCEs and MCCE leaders.
1560   ^ static VOID dovec(struct vars *, struct cvec *, struct state *,   ^ static VOID dovec(struct vars *, struct cvec *, struct state *,
1561   ^      struct state *);   ^      struct state *);
1562   */   */
1563  static VOID  static VOID
1564  dovec(v, cv, lp, rp)  dovec(v, cv, lp, rp)
1565  struct vars *v;  struct vars *v;
1566  struct cvec *cv;  struct cvec *cv;
1567  struct state *lp;  struct state *lp;
1568  struct state *rp;  struct state *rp;
1569  {  {
1570          chr ch, from, to;          chr ch, from, to;
1571          celt ce;          celt ce;
1572          chr *p;          chr *p;
1573          int i;          int i;
1574          color co;          color co;
1575          struct cvec *leads;          struct cvec *leads;
1576          struct arc *a;          struct arc *a;
1577          struct arc *pa;         /* arc in prototype */          struct arc *pa;         /* arc in prototype */
1578          struct state *s;          struct state *s;
1579          struct state *ps;       /* state in prototype */          struct state *ps;       /* state in prototype */
1580    
1581          /* need a place to store leaders, if any */          /* need a place to store leaders, if any */
1582          if (nmcces(v) > 0) {          if (nmcces(v) > 0) {
1583                  assert(v->mcces != NULL);                  assert(v->mcces != NULL);
1584                  if (v->cv2 == NULL || v->cv2->nchrs < v->mcces->nchrs) {                  if (v->cv2 == NULL || v->cv2->nchrs < v->mcces->nchrs) {
1585                          if (v->cv2 != NULL)                          if (v->cv2 != NULL)
1586                                  free(v->cv2);                                  free(v->cv2);
1587                          v->cv2 = newcvec(v->mcces->nchrs, 0, v->mcces->nmcces);                          v->cv2 = newcvec(v->mcces->nchrs, 0, v->mcces->nmcces);
1588                          NOERR();                          NOERR();
1589                          leads = v->cv2;                          leads = v->cv2;
1590                  } else                  } else
1591                          leads = clearcvec(v->cv2);                          leads = clearcvec(v->cv2);
1592          } else          } else
1593                  leads = NULL;                  leads = NULL;
1594    
1595          /* first, get the ordinary characters out of the way */          /* first, get the ordinary characters out of the way */
1596          for (p = cv->chrs, i = cv->nchrs; i > 0; p++, i--) {          for (p = cv->chrs, i = cv->nchrs; i > 0; p++, i--) {
1597                  ch = *p;                  ch = *p;
1598                  if (!ISCELEADER(v, ch))                  if (!ISCELEADER(v, ch))
1599                          newarc(v->nfa, PLAIN, subcolor(v->cm, ch), lp, rp);                          newarc(v->nfa, PLAIN, subcolor(v->cm, ch), lp, rp);
1600                  else {                  else {
1601                          assert(singleton(v->cm, ch));                          assert(singleton(v->cm, ch));
1602                          assert(leads != NULL);                          assert(leads != NULL);
1603                          if (!haschr(leads, ch))                          if (!haschr(leads, ch))
1604                                  addchr(leads, ch);                                  addchr(leads, ch);
1605                  }                  }
1606          }          }
1607    
1608          /* and the ranges */          /* and the ranges */
1609          for (p = cv->ranges, i = cv->nranges; i > 0; p += 2, i--) {          for (p = cv->ranges, i = cv->nranges; i > 0; p += 2, i--) {
1610                  from = *p;                  from = *p;
1611                  to = *(p+1);                  to = *(p+1);
1612                  while (from <= to && (ce = nextleader(v, from, to)) != NOCELT) {                  while (from <= to && (ce = nextleader(v, from, to)) != NOCELT) {
1613                          if (from < ce)                          if (from < ce)
1614                                  subrange(v, from, ce - 1, lp, rp);                                  subrange(v, from, ce - 1, lp, rp);
1615                          assert(singleton(v->cm, ce));                          assert(singleton(v->cm, ce));
1616                          assert(leads != NULL);                          assert(leads != NULL);
1617                          if (!haschr(leads, ce))                          if (!haschr(leads, ce))
1618                                  addchr(leads, ce);                                  addchr(leads, ce);
1619                          from = ce + 1;                          from = ce + 1;
1620                  }                  }
1621                  if (from <= to)                  if (from <= to)
1622                          subrange(v, from, to, lp, rp);                          subrange(v, from, to, lp, rp);
1623          }          }
1624    
1625          if ((leads == NULL || leads->nchrs == 0) && cv->nmcces == 0)          if ((leads == NULL || leads->nchrs == 0) && cv->nmcces == 0)
1626                  return;                  return;
1627    
1628          /* deal with the MCCE leaders */          /* deal with the MCCE leaders */
1629          NOTE(REG_ULOCALE);          NOTE(REG_ULOCALE);
1630          for (p = leads->chrs, i = leads->nchrs; i > 0; p++, i--) {          for (p = leads->chrs, i = leads->nchrs; i > 0; p++, i--) {
1631                  co = GETCOLOR(v->cm, *p);                  co = GETCOLOR(v->cm, *p);
1632                  a = findarc(lp, PLAIN, co);                  a = findarc(lp, PLAIN, co);
1633                  if (a != NULL)                  if (a != NULL)
1634                          s = a->to;                          s = a->to;
1635                  else {                  else {
1636                          s = newstate(v->nfa);                          s = newstate(v->nfa);
1637                          NOERR();                          NOERR();
1638                          newarc(v->nfa, PLAIN, co, lp, s);                          newarc(v->nfa, PLAIN, co, lp, s);
1639                          NOERR();                          NOERR();
1640                  }                  }
1641                  pa = findarc(v->mccepbegin, PLAIN, co);                  pa = findarc(v->mccepbegin, PLAIN, co);
1642                  assert(pa != NULL);                  assert(pa != NULL);
1643                  ps = pa->to;                  ps = pa->to;
1644                  newarc(v->nfa, '$', 1, s, rp);                  newarc(v->nfa, '$', 1, s, rp);
1645                  newarc(v->nfa, '$', 0, s, rp);                  newarc(v->nfa, '$', 0, s, rp);
1646                  colorcomplement(v->nfa, v->cm, AHEAD, ps, s, rp);                  colorcomplement(v->nfa, v->cm, AHEAD, ps, s, rp);
1647                  NOERR();                  NOERR();
1648          }          }
1649    
1650          /* and the MCCEs */          /* and the MCCEs */
1651          for (i = 0; i < cv->nmcces; i++) {          for (i = 0; i < cv->nmcces; i++) {
1652                  p = cv->mcces[i];                  p = cv->mcces[i];
1653                  assert(singleton(v->cm, *p));                  assert(singleton(v->cm, *p));
1654                  if (!singleton(v->cm, *p)) {                  if (!singleton(v->cm, *p)) {
1655                          ERR(REG_ASSERT);                          ERR(REG_ASSERT);
1656                          return;                          return;
1657                  }                  }
1658                  ch = *p++;                  ch = *p++;
1659                  co = GETCOLOR(v->cm, ch);                  co = GETCOLOR(v->cm, ch);
1660                  a = findarc(lp, PLAIN, co);                  a = findarc(lp, PLAIN, co);
1661                  if (a != NULL)                  if (a != NULL)
1662                          s = a->to;                          s = a->to;
1663                  else {                  else {
1664                          s = newstate(v->nfa);                          s = newstate(v->nfa);
1665                          NOERR();                          NOERR();
1666                          newarc(v->nfa, PLAIN, co, lp, s);                          newarc(v->nfa, PLAIN, co, lp, s);
1667                          NOERR();                          NOERR();
1668                  }                  }
1669                  assert(*p != 0);        /* at least two chars */                  assert(*p != 0);        /* at least two chars */
1670                  assert(singleton(v->cm, *p));                  assert(singleton(v->cm, *p));
1671                  ch = *p++;                  ch = *p++;
1672                  co = GETCOLOR(v->cm, ch);                  co = GETCOLOR(v->cm, ch);
1673                  assert(*p == 0);        /* and only two, for now */                  assert(*p == 0);        /* and only two, for now */
1674                  newarc(v->nfa, PLAIN, co, s, rp);                  newarc(v->nfa, PLAIN, co, s, rp);
1675                  NOERR();                  NOERR();
1676          }          }
1677  }  }
1678    
1679  /*  /*
1680   - nextleader - find next MCCE leader within range   - nextleader - find next MCCE leader within range
1681   ^ static celt nextleader(struct vars *, pchr, pchr);   ^ static celt nextleader(struct vars *, pchr, pchr);
1682   */   */
1683  static celt                     /* NOCELT means none */  static celt                     /* NOCELT means none */
1684  nextleader(v, from, to)  nextleader(v, from, to)
1685  struct vars *v;  struct vars *v;
1686  pchr from;  pchr from;
1687  pchr to;  pchr to;
1688  {  {
1689          int i;          int i;
1690          chr *p;          chr *p;
1691          chr ch;          chr ch;
1692          celt it = NOCELT;          celt it = NOCELT;
1693    
1694          if (v->mcces == NULL)          if (v->mcces == NULL)
1695                  return it;                  return it;
1696    
1697          for (i = v->mcces->nchrs, p = v->mcces->chrs; i > 0; i--, p++) {          for (i = v->mcces->nchrs, p = v->mcces->chrs; i > 0; i--, p++) {
1698                  ch = *p;                  ch = *p;
1699                  if (from <= ch && ch <= to)                  if (from <= ch && ch <= to)
1700                          if (it == NOCELT || ch < it)                          if (it == NOCELT || ch < it)
1701                                  it = ch;                                  it = ch;
1702          }          }
1703          return it;          return it;
1704  }  }
1705    
1706  /*  /*
1707   - wordchrs - set up word-chr list for word-boundary stuff, if needed   - wordchrs - set up word-chr list for word-boundary stuff, if needed
1708   * The list is kept as a bunch of arcs between two dummy states; it's   * The list is kept as a bunch of arcs between two dummy states; it's
1709   * disposed of by the unreachable-states sweep in NFA optimization.   * disposed of by the unreachable-states sweep in NFA optimization.
1710   * Does NEXT().  Must not be called from any unusual lexical context.   * Does NEXT().  Must not be called from any unusual lexical context.
1711   * This should be reconciled with the \w etc. handling in lex.c, and   * This should be reconciled with the \w etc. handling in lex.c, and
1712   * should be cleaned up to reduce dependencies on input scanning.   * should be cleaned up to reduce dependencies on input scanning.
1713   ^ static VOID wordchrs(struct vars *);   ^ static VOID wordchrs(struct vars *);
1714   */   */
1715  static VOID  static VOID
1716  wordchrs(v)  wordchrs(v)
1717  struct vars *v;  struct vars *v;
1718  {  {
1719          struct state *left;          struct state *left;
1720          struct state *right;          struct state *right;
1721    
1722          if (v->wordchrs != NULL) {          if (v->wordchrs != NULL) {
1723                  NEXT();         /* for consistency */                  NEXT();         /* for consistency */
1724                  return;                  return;
1725          }          }
1726    
1727          left = newstate(v->nfa);          left = newstate(v->nfa);
1728          right = newstate(v->nfa);          right = newstate(v->nfa);
1729          NOERR();          NOERR();
1730          /* fine point:  implemented with [::], and lexer will set REG_ULOCALE */          /* fine point:  implemented with [::], and lexer will set REG_ULOCALE */
1731          lexword(v);          lexword(v);
1732          NEXT();          NEXT();
1733          assert(v->savenow != NULL && SEE('['));          assert(v->savenow != NULL && SEE('['));
1734          bracket(v, left, right);          bracket(v, left, right);
1735          assert((v->savenow != NULL && SEE(']')) || ISERR());          assert((v->savenow != NULL && SEE(']')) || ISERR());
1736          NEXT();          NEXT();
1737          NOERR();          NOERR();
1738          v->wordchrs = left;          v->wordchrs = left;
1739  }  }
1740    
1741  /*  /*
1742   - subre - allocate a subre   - subre - allocate a subre
1743   ^ static struct subre *subre(struct vars *, int, int, struct state *,   ^ static struct subre *subre(struct vars *, int, int, struct state *,
1744   ^      struct state *);   ^      struct state *);
1745   */   */
1746  static struct subre *  static struct subre *
1747  subre(v, op, flags, begin, end)  subre(v, op, flags, begin, end)
1748  struct vars *v;  struct vars *v;
1749  int op;  int op;
1750  int flags;  int flags;
1751  struct state *begin;  struct state *begin;
1752  struct state *end;  struct state *end;
1753  {  {
1754          struct subre *ret;          struct subre *ret;
1755    
1756          ret = v->treefree;          ret = v->treefree;
1757          if (ret != NULL)          if (ret != NULL)
1758                  v->treefree = ret->left;                  v->treefree = ret->left;
1759          else {          else {
1760                  ret = (struct subre *)MALLOC(sizeof(struct subre));                  ret = (struct subre *)MALLOC(sizeof(struct subre));
1761                  if (ret == NULL) {                  if (ret == NULL) {
1762                          ERR(REG_ESPACE);                          ERR(REG_ESPACE);
1763                          return NULL;                          return NULL;
1764                  }                  }
1765                  ret->chain = v->treechain;                  ret->chain = v->treechain;
1766                  v->treechain = ret;                  v->treechain = ret;
1767          }          }
1768    
1769          assert(strchr("|.b(=", op) != NULL);          assert(strchr("|.b(=", op) != NULL);
1770    
1771          ret->op = op;          ret->op = op;
1772          ret->flags = flags;          ret->flags = flags;
1773          ret->retry = 0;          ret->retry = 0;
1774          ret->subno = 0;          ret->subno = 0;
1775          ret->min = ret->max = 1;          ret->min = ret->max = 1;
1776          ret->left = NULL;          ret->left = NULL;
1777          ret->right = NULL;          ret->right = NULL;
1778          ret->begin = begin;          ret->begin = begin;
1779          ret->end = end;          ret->end = end;
1780          ZAPCNFA(ret->cnfa);          ZAPCNFA(ret->cnfa);
1781    
1782          return ret;          return ret;
1783  }  }
1784    
1785  /*  /*
1786   - freesubre - free a subRE subtree   - freesubre - free a subRE subtree
1787   ^ static VOID freesubre(struct vars *, struct subre *);   ^ static VOID freesubre(struct vars *, struct subre *);
1788   */   */
1789  static VOID  static VOID
1790  freesubre(v, sr)  freesubre(v, sr)
1791  struct vars *v;                 /* might be NULL */  struct vars *v;                 /* might be NULL */
1792  struct subre *sr;  struct subre *sr;
1793  {  {
1794          if (sr == NULL)          if (sr == NULL)
1795                  return;                  return;
1796    
1797          if (sr->left != NULL)          if (sr->left != NULL)
1798                  freesubre(v, sr->left);                  freesubre(v, sr->left);
1799          if (sr->right != NULL)          if (sr->right != NULL)
1800                  freesubre(v, sr->right);                  freesubre(v, sr->right);
1801    
1802          freesrnode(v, sr);          freesrnode(v, sr);
1803  }  }
1804    
1805  /*  /*
1806   - freesrnode - free one node in a subRE subtree   - freesrnode - free one node in a subRE subtree
1807   ^ static VOID freesrnode(struct vars *, struct subre *);   ^ static VOID freesrnode(struct vars *, struct subre *);
1808   */   */
1809  static VOID  static VOID
1810  freesrnode(v, sr)  freesrnode(v, sr)
1811  struct vars *v;                 /* might be NULL */  struct vars *v;                 /* might be NULL */
1812  struct subre *sr;  struct subre *sr;
1813  {  {
1814          if (sr == NULL)          if (sr == NULL)
1815                  return;                  return;
1816    
1817          if (!NULLCNFA(sr->cnfa))          if (!NULLCNFA(sr->cnfa))
1818                  freecnfa(&sr->cnfa);                  freecnfa(&sr->cnfa);
1819          sr->flags = 0;          sr->flags = 0;
1820    
1821          if (v != NULL) {          if (v != NULL) {
1822                  sr->left = v->treefree;                  sr->left = v->treefree;
1823                  v->treefree = sr;                  v->treefree = sr;
1824          } else          } else
1825                  FREE(sr);                  FREE(sr);
1826  }  }
1827    
1828  /*  /*
1829   - optst - optimize a subRE subtree   - optst - optimize a subRE subtree
1830   ^ static VOID optst(struct vars *, struct subre *);   ^ static VOID optst(struct vars *, struct subre *);
1831   */   */
1832  static VOID  static VOID
1833  optst(v, t)  optst(v, t)
1834  struct vars *v;  struct vars *v;
1835  struct subre *t;  struct subre *t;
1836  {  {
1837          if (t == NULL)          if (t == NULL)
1838                  return;                  return;
1839    
1840          /* recurse through children */          /* recurse through children */
1841          if (t->left != NULL)          if (t->left != NULL)
1842                  optst(v, t->left);                  optst(v, t->left);
1843          if (t->right != NULL)          if (t->right != NULL)
1844                  optst(v, t->right);                  optst(v, t->right);
1845  }  }
1846    
1847  /*  /*
1848   - numst - number tree nodes (assigning retry indexes)   - numst - number tree nodes (assigning retry indexes)
1849   ^ static int numst(struct subre *, int);   ^ static int numst(struct subre *, int);
1850   */   */
1851  static int                      /* next number */  static int                      /* next number */
1852  numst(t, start)  numst(t, start)
1853  struct subre *t;  struct subre *t;
1854  int start;                      /* starting point for subtree numbers */  int start;                      /* starting point for subtree numbers */
1855  {  {
1856          int i;          int i;
1857    
1858          assert(t != NULL);          assert(t != NULL);
1859    
1860          i = start;          i = start;
1861          t->retry = (short)i++;          t->retry = (short)i++;
1862          if (t->left != NULL)          if (t->left != NULL)
1863                  i = numst(t->left, i);                  i = numst(t->left, i);
1864          if (t->right != NULL)          if (t->right != NULL)
1865                  i = numst(t->right, i);                  i = numst(t->right, i);
1866          return i;          return i;
1867  }  }
1868    
1869  /*  /*
1870   - markst - mark tree nodes as INUSE   - markst - mark tree nodes as INUSE
1871   ^ static VOID markst(struct subre *);   ^ static VOID markst(struct subre *);
1872   */   */
1873  static VOID  static VOID
1874  markst(t)  markst(t)
1875  struct subre *t;  struct subre *t;
1876  {  {
1877          assert(t != NULL);          assert(t != NULL);
1878    
1879          t->flags |= INUSE;          t->flags |= INUSE;
1880          if (t->left != NULL)          if (t->left != NULL)
1881                  markst(t->left);                  markst(t->left);
1882          if (t->right != NULL)          if (t->right != NULL)
1883                  markst(t->right);                  markst(t->right);
1884  }  }
1885    
1886  /*  /*
1887   - cleanst - free any tree nodes not marked INUSE   - cleanst - free any tree nodes not marked INUSE
1888   ^ static VOID cleanst(struct vars *);   ^ static VOID cleanst(struct vars *);
1889   */   */
1890  static VOID  static VOID
1891  cleanst(v)  cleanst(v)
1892  struct vars *v;  struct vars *v;
1893  {  {
1894          struct subre *t;          struct subre *t;
1895          struct subre *next;          struct subre *next;
1896    
1897          for (t = v->treechain; t != NULL; t = next) {          for (t = v->treechain; t != NULL; t = next) {
1898                  next = t->chain;                  next = t->chain;
1899                  if (!(t->flags&INUSE))                  if (!(t->flags&INUSE))
1900                          FREE(t);                          FREE(t);
1901          }          }
1902          v->treechain = NULL;          v->treechain = NULL;
1903          v->treefree = NULL;             /* just on general principles */          v->treefree = NULL;             /* just on general principles */
1904  }  }
1905    
1906  /*  /*
1907   - nfatree - turn a subRE subtree into a tree of compacted NFAs   - nfatree - turn a subRE subtree into a tree of compacted NFAs
1908   ^ static long nfatree(struct vars *, struct subre *, FILE *);   ^ static long nfatree(struct vars *, struct subre *, FILE *);
1909   */   */
1910  static long                     /* optimize results from top node */  static long                     /* optimize results from top node */
1911  nfatree(v, t, f)  nfatree(v, t, f)
1912  struct vars *v;  struct vars *v;
1913  struct subre *t;  struct subre *t;
1914  FILE *f;                        /* for debug output */  FILE *f;                        /* for debug output */
1915  {  {
1916          assert(t != NULL && t->begin != NULL);          assert(t != NULL && t->begin != NULL);
1917    
1918          if (t->left != NULL)          if (t->left != NULL)
1919                  (DISCARD)nfatree(v, t->left, f);                  (DISCARD)nfatree(v, t->left, f);
1920          if (t->right != NULL)          if (t->right != NULL)
1921                  (DISCARD)nfatree(v, t->right, f);                  (DISCARD)nfatree(v, t->right, f);
1922    
1923          return nfanode(v, t, f);          return nfanode(v, t, f);
1924  }  }
1925    
1926  /*  /*
1927   - nfanode - do one NFA for nfatree   - nfanode - do one NFA for nfatree
1928   ^ static long nfanode(struct vars *, struct subre *, FILE *);   ^ static long nfanode(struct vars *, struct subre *, FILE *);
1929   */   */
1930  static long                     /* optimize results */  static long                     /* optimize results */
1931  nfanode(v, t, f)  nfanode(v, t, f)
1932  struct vars *v;  struct vars *v;
1933  struct subre *t;  struct subre *t;
1934  FILE *f;                        /* for debug output */  FILE *f;                        /* for debug output */
1935  {  {
1936          struct nfa *nfa;          struct nfa *nfa;
1937          long ret = 0;          long ret = 0;
1938          char idbuf[50];          char idbuf[50];
1939    
1940          assert(t->begin != NULL);          assert(t->begin != NULL);
1941    
1942          if (f != NULL)          if (f != NULL)
1943                  fprintf(f, "\n\n\n========= TREE NODE %s ==========\n",                  fprintf(f, "\n\n\n========= TREE NODE %s ==========\n",
1944                                                  stid(t, idbuf, sizeof(idbuf)));                                                  stid(t, idbuf, sizeof(idbuf)));
1945          nfa = newnfa(v, v->cm, v->nfa);          nfa = newnfa(v, v->cm, v->nfa);
1946          NOERRZ();          NOERRZ();
1947          dupnfa(nfa, t->begin, t->end, nfa->init, nfa->final);          dupnfa(nfa, t->begin, t->end, nfa->init, nfa->final);
1948          if (!ISERR()) {          if (!ISERR()) {
1949                  specialcolors(nfa);                  specialcolors(nfa);
1950                  ret = optimize(nfa, f);                  ret = optimize(nfa, f);
1951          }          }
1952          if (!ISERR())          if (!ISERR())
1953                  compact(nfa, &t->cnfa);                  compact(nfa, &t->cnfa);
1954    
1955          freenfa(nfa);          freenfa(nfa);
1956          return ret;          return ret;
1957  }  }
1958    
1959  /*  /*
1960   - newlacon - allocate a lookahead-constraint subRE   - newlacon - allocate a lookahead-constraint subRE
1961   ^ static int newlacon(struct vars *, struct state *, struct state *, int);   ^ static int newlacon(struct vars *, struct state *, struct state *, int);
1962   */   */
1963  static int                      /* lacon number */  static int                      /* lacon number */
1964  newlacon(v, begin, end, pos)  newlacon(v, begin, end, pos)
1965  struct vars *v;  struct vars *v;
1966  struct state *begin;  struct state *begin;
1967  struct state *end;  struct state *end;
1968  int pos;  int pos;
1969  {  {
1970          int n;          int n;
1971          struct subre *sub;          struct subre *sub;
1972    
1973          if (v->nlacons == 0) {          if (v->nlacons == 0) {
1974                  v->lacons = (struct subre *)MALLOC(2 * sizeof(struct subre));                  v->lacons = (struct subre *)MALLOC(2 * sizeof(struct subre));
1975                  n = 1;          /* skip 0th */                  n = 1;          /* skip 0th */
1976                  v->nlacons = 2;                  v->nlacons = 2;
1977          } else {          } else {
1978                  v->lacons = (struct subre *)REALLOC(v->lacons,                  v->lacons = (struct subre *)REALLOC(v->lacons,
1979                                          (v->nlacons+1)*sizeof(struct subre));                                          (v->nlacons+1)*sizeof(struct subre));
1980                  n = v->nlacons++;                  n = v->nlacons++;
1981          }          }
1982          if (v->lacons == NULL) {          if (v->lacons == NULL) {
1983                  ERR(REG_ESPACE);                  ERR(REG_ESPACE);
1984                  return 0;                  return 0;
1985          }          }
1986          sub = &v->lacons[n];          sub = &v->lacons[n];
1987          sub->begin = begin;          sub->begin = begin;
1988          sub->end = end;          sub->end = end;
1989          sub->subno = pos;          sub->subno = pos;
1990          ZAPCNFA(sub->cnfa);          ZAPCNFA(sub->cnfa);
1991          return n;          return n;
1992  }  }
1993    
1994  /*  /*
1995   - freelacons - free lookahead-constraint subRE vector   - freelacons - free lookahead-constraint subRE vector
1996   ^ static VOID freelacons(struct subre *, int);   ^ static VOID freelacons(struct subre *, int);
1997   */   */
1998  static VOID  static VOID
1999  freelacons(subs, n)  freelacons(subs, n)
2000  struct subre *subs;  struct subre *subs;
2001  int n;  int n;
2002  {  {
2003          struct subre *sub;          struct subre *sub;
2004          int i;          int i;
2005    
2006          assert(n > 0);          assert(n > 0);
2007          for (sub = subs + 1, i = n - 1; i > 0; sub++, i--)      /* no 0th */          for (sub = subs + 1, i = n - 1; i > 0; sub++, i--)      /* no 0th */
2008                  if (!NULLCNFA(sub->cnfa))                  if (!NULLCNFA(sub->cnfa))
2009                          freecnfa(&sub->cnfa);                          freecnfa(&sub->cnfa);
2010          FREE(subs);          FREE(subs);
2011  }  }
2012    
2013  /*  /*
2014   - rfree - free a whole RE (insides of regfree)   - rfree - free a whole RE (insides of regfree)
2015   ^ static VOID rfree(regex_t *);   ^ static VOID rfree(regex_t *);
2016   */   */
2017  static VOID  static VOID
2018  rfree(re)  rfree(re)
2019  regex_t *re;  regex_t *re;
2020  {  {
2021          struct guts *g;          struct guts *g;
2022    
2023          if (re == NULL || re->re_magic != REMAGIC)          if (re == NULL || re->re_magic != REMAGIC)
2024                  return;                  return;
2025    
2026          re->re_magic = 0;       /* invalidate RE */          re->re_magic = 0;       /* invalidate RE */
2027          g = (struct guts *)re->re_guts;          g = (struct guts *)re->re_guts;
2028          re->re_guts = NULL;          re->re_guts = NULL;
2029          re->re_fns = NULL;          re->re_fns = NULL;
2030          g->magic = 0;          g->magic = 0;
2031          freecm(&g->cmap);          freecm(&g->cmap);
2032          if (g->tree != NULL)          if (g->tree != NULL)
2033                  freesubre((struct vars *)NULL, g->tree);                  freesubre((struct vars *)NULL, g->tree);
2034          if (g->lacons != NULL)          if (g->lacons != NULL)
2035                  freelacons(g->lacons, g->nlacons);                  freelacons(g->lacons, g->nlacons);
2036          if (!NULLCNFA(g->search))          if (!NULLCNFA(g->search))
2037                  freecnfa(&g->search);                  freecnfa(&g->search);
2038          FREE(g);          FREE(g);
2039  }  }
2040    
2041  /*  /*
2042   - dump - dump an RE in human-readable form   - dump - dump an RE in human-readable form
2043   ^ static VOID dump(regex_t *, FILE *);   ^ static VOID dump(regex_t *, FILE *);
2044   */   */
2045  static VOID  static VOID
2046  dump(re, f)  dump(re, f)
2047  regex_t *re;  regex_t *re;
2048  FILE *f;  FILE *f;
2049  {  {
2050  #ifdef REG_DEBUG  #ifdef REG_DEBUG
2051          struct guts *g;          struct guts *g;
2052          int i;          int i;
2053    
2054          if (re->re_magic != REMAGIC)          if (re->re_magic != REMAGIC)
2055                  fprintf(f, "bad magic number (0x%x not 0x%x)\n", re->re_magic,                  fprintf(f, "bad magic number (0x%x not 0x%x)\n", re->re_magic,
2056                                                                  REMAGIC);                                                                  REMAGIC);
2057          if (re->re_guts == NULL) {          if (re->re_guts == NULL) {
2058                  fprintf(f, "NULL guts!!!\n");                  fprintf(f, "NULL guts!!!\n");
2059                  return;                  return;
2060          }          }
2061          g = (struct guts *)re->re_guts;          g = (struct guts *)re->re_guts;
2062          if (g->magic != GUTSMAGIC)          if (g->magic != GUTSMAGIC)
2063                  fprintf(f, "bad guts magic number (0x%x not 0x%x)\n", g->magic,                  fprintf(f, "bad guts magic number (0x%x not 0x%x)\n", g->magic,
2064                                                                  GUTSMAGIC);                                                                  GUTSMAGIC);
2065    
2066          fprintf(f, "\n\n\n========= DUMP ==========\n");          fprintf(f, "\n\n\n========= DUMP ==========\n");
2067          fprintf(f, "nsub %d, info 0%lo, csize %d, ntree %d\n",          fprintf(f, "nsub %d, info 0%lo, csize %d, ntree %d\n",
2068                  re->re_nsub, re->re_info, re->re_csize, g->ntree);                  re->re_nsub, re->re_info, re->re_csize, g->ntree);
2069    
2070          dumpcolors(&g->cmap, f);          dumpcolors(&g->cmap, f);
2071          if (!NULLCNFA(g->search)) {          if (!NULLCNFA(g->search)) {
2072                  printf("\nsearch:\n");                  printf("\nsearch:\n");
2073                  dumpcnfa(&g->search, f);                  dumpcnfa(&g->search, f);
2074          }          }
2075          for (i = 1; i < g->nlacons; i++) {          for (i = 1; i < g->nlacons; i++) {
2076                  fprintf(f, "\nla%d (%s):\n", i,                  fprintf(f, "\nla%d (%s):\n", i,
2077                                  (g->lacons[i].subno) ? "positive" : "negative");                                  (g->lacons[i].subno) ? "positive" : "negative");
2078                  dumpcnfa(&g->lacons[i].cnfa, f);                  dumpcnfa(&g->lacons[i].cnfa, f);
2079          }          }
2080          fprintf(f, "\n");          fprintf(f, "\n");
2081          dumpst(g->tree, f, 0);          dumpst(g->tree, f, 0);
2082  #endif  #endif
2083  }  }
2084    
2085  /*  /*
2086   - dumpst - dump a subRE tree   - dumpst - dump a subRE tree
2087   ^ static VOID dumpst(struct subre *, FILE *, int);   ^ static VOID dumpst(struct subre *, FILE *, int);
2088   */   */
2089  static VOID  static VOID
2090  dumpst(t, f, nfapresent)  dumpst(t, f, nfapresent)
2091  struct subre *t;  struct subre *t;
2092  FILE *f;  FILE *f;
2093  int nfapresent;                 /* is the original NFA still around? */  int nfapresent;                 /* is the original NFA still around? */
2094  {  {
2095          if (t == NULL)          if (t == NULL)
2096                  fprintf(f, "null tree\n");                  fprintf(f, "null tree\n");
2097          else          else
2098                  stdump(t, f, nfapresent);                  stdump(t, f, nfapresent);
2099          fflush(f);          fflush(f);
2100  }  }
2101    
2102  /*  /*
2103   - stdump - recursive guts of dumpst   - stdump - recursive guts of dumpst
2104   ^ static VOID stdump(struct subre *, FILE *, int);   ^ static VOID stdump(struct subre *, FILE *, int);
2105   */   */
2106  static VOID  static VOID
2107  stdump(t, f, nfapresent)  stdump(t, f, nfapresent)
2108  struct subre *t;  struct subre *t;
2109  FILE *f;  FILE *f;
2110  int nfapresent;                 /* is the original NFA still around? */  int nfapresent;                 /* is the original NFA still around? */
2111  {  {
2112          char idbuf[50];          char idbuf[50];
2113    
2114          fprintf(f, "%s. `%c'", stid(t, idbuf, sizeof(idbuf)), t->op);          fprintf(f, "%s. `%c'", stid(t, idbuf, sizeof(idbuf)), t->op);
2115          if (t->flags&LONGER)          if (t->flags&LONGER)
2116                  fprintf(f, " longest");                  fprintf(f, " longest");
2117          if (t->flags&SHORTER)          if (t->flags&SHORTER)
2118                  fprintf(f, " shortest");                  fprintf(f, " shortest");
2119          if (t->flags&MIXED)          if (t->flags&MIXED)
2120                  fprintf(f, " hasmixed");                  fprintf(f, " hasmixed");
2121          if (t->flags&CAP)          if (t->flags&CAP)
2122                  fprintf(f, " hascapture");                  fprintf(f, " hascapture");
2123          if (t->flags&BACKR)          if (t->flags&BACKR)
2124                  fprintf(f, " hasbackref");                  fprintf(f, " hasbackref");
2125          if (!(t->flags&INUSE))          if (!(t->flags&INUSE))
2126                  fprintf(f, " UNUSED");                  fprintf(f, " UNUSED");
2127          if (t->subno != 0)          if (t->subno != 0)
2128                  fprintf(f, " (#%d)", t->subno);                  fprintf(f, " (#%d)", t->subno);
2129          if (t->min != 1 || t->max != 1) {          if (t->min != 1 || t->max != 1) {
2130                  fprintf(f, " {%d,", t->min);                  fprintf(f, " {%d,", t->min);
2131                  if (t->max != INFINITY)                  if (t->max != INFINITY)
2132                          fprintf(f, "%d", t->max);                          fprintf(f, "%d", t->max);
2133                  fprintf(f, "}");                  fprintf(f, "}");
2134          }          }
2135          if (nfapresent)          if (nfapresent)
2136                  fprintf(f, " %ld-%ld", (long)t->begin->no, (long)t->end->no);                  fprintf(f, " %ld-%ld", (long)t->begin->no, (long)t->end->no);
2137          if (t->left != NULL)          if (t->left != NULL)
2138                  fprintf(f, " L:%s", stid(t->left, idbuf, sizeof(idbuf)));                  fprintf(f, " L:%s", stid(t->left, idbuf, sizeof(idbuf)));
2139          if (t->right != NULL)          if (t->right != NULL)
2140                  fprintf(f, " R:%s", stid(t->right, idbuf, sizeof(idbuf)));                  fprintf(f, " R:%s", stid(t->right, idbuf, sizeof(idbuf)));
2141          if (!NULLCNFA(t->cnfa)) {          if (!NULLCNFA(t->cnfa)) {
2142                  fprintf(f, "\n");                  fprintf(f, "\n");
2143                  dumpcnfa(&t->cnfa, f);                  dumpcnfa(&t->cnfa, f);
2144                  fprintf(f, "\n");                  fprintf(f, "\n");
2145          }          }
2146          if (t->left != NULL)          if (t->left != NULL)
2147                  stdump(t->left, f, nfapresent);                  stdump(t->left, f, nfapresent);
2148          if (t->right != NULL)          if (t->right != NULL)
2149                  stdump(t->right, f, nfapresent);                  stdump(t->right, f, nfapresent);
2150  }  }
2151    
2152  /*  /*
2153   - stid - identify a subtree node for dumping   - stid - identify a subtree node for dumping
2154   ^ static char *stid(struct subre *, char *, size_t);   ^ static char *stid(struct subre *, char *, size_t);
2155   */   */
2156  static char *                   /* points to buf or constant string */  static char *                   /* points to buf or constant string */
2157  stid(t, buf, bufsize)  stid(t, buf, bufsize)
2158  struct subre *t;  struct subre *t;
2159  char *buf;  char *buf;
2160  size_t bufsize;  size_t bufsize;
2161  {  {
2162          /* big enough for hex int or decimal t->retry? */          /* big enough for hex int or decimal t->retry? */
2163          if (bufsize < sizeof(int)*2 + 3 || bufsize < sizeof(t->retry)*3 + 1)          if (bufsize < sizeof(int)*2 + 3 || bufsize < sizeof(t->retry)*3 + 1)
2164                  return "unable";                  return "unable";
2165          if (t->retry != 0)          if (t->retry != 0)
2166                  sprintf(buf, "%d", t->retry);                  sprintf(buf, "%d", t->retry);
2167          else          else
2168                  sprintf(buf, "0x%x", (int)t);   /* may lose bits, that's okay */                  sprintf(buf, "0x%x", (int)t);   /* may lose bits, that's okay */
2169          return buf;          return buf;
2170  }  }
2171    
2172  #include "regc_lex.c"  #include "regc_lex.c"
2173  #include "regc_color.c"  #include "regc_color.c"
2174  #include "regc_nfa.c"  #include "regc_nfa.c"
2175  #include "regc_cvec.c"  #include "regc_cvec.c"
2176  #include "regc_locale.c"  #include "regc_locale.c"
2177    
2178  /* End of regcomp.c */  /* End of regcomp.c */

Legend:
Removed from v.70  
changed lines
  Added in v.71

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25