/[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

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