120{
121 int st;
122 int nextst;
126
127 /*
128 * The "pre" state must have only BOS/BOL outarcs, else pattern isn't
129 * anchored left. If we have both BOS and BOL, they must go to the same
130 * next state.
131 */
133 nextst = -1;
135 {
137 {
138 if (nextst == -1)
140 else if (nextst != ca->
to)
142 }
143 else
145 }
146 if (nextst == -1)
148
149 /*
150 * Scan through successive states, stopping as soon as we find one with
151 * more than one acceptable transition character (either multiple colors
152 * on out-arcs, or a color with more than one member chr).
153 *
154 * We could find a state with multiple out-arcs that are all labeled with
155 * the same singleton color; this comes from patterns like "^ab(cde|cxy)".
156 * In that case we add the chr "c" to the output string but then exit the
157 * loop with nextst == -1. This leaves a little bit on the table: if the
158 * pattern is like "^ab(cde|cdy)", we won't notice that "d" could be added
159 * to the prefix. But chasing multiple parallel state chains doesn't seem
160 * worth the trouble.
161 */
162 do
163 {
164 st = nextst;
165 nextst = -1;
168 {
169 /* We can ignore BOS/BOL arcs */
171 continue;
172
173 /*
174 * ... but EOS/EOL arcs terminate the search, as do RAINBOW arcs
175 * and LACONs
176 */
179 {
181 break;
182 }
184 {
185 /* First plain outarc */
188 }
189 else if (thiscolor == ca->
co)
190 {
191 /* Another plain outarc for same color */
192 nextst = -1;
193 }
194 else
195 {
196 /* More than one plain outarc color terminates the search */
198 break;
199 }
200 }
201 /* Done if we didn't find exactly one color on plain outarcs */
203 break;
204 /* The color must be a singleton */
206 break;
207 /* Must not have any high-color-map entries */
209 break;
210
211 /*
212 * Identify the color's sole member chr and add it to the prefix
213 * string. In general the colormap data structure doesn't provide a
214 * way to find color member chrs, except by trying GETCOLOR() on each
215 * possible chr value, which won't do at all. However, for the cases
216 * we care about it should be sufficient to test the "firstchr" value,
217 * that is the first chr ever added to the color. There are cases
218 * where this might no longer be a member of the color (so we do need
219 * to test), but none of them are likely to arise for a character that
220 * is a member of a common prefix. If we do hit such a corner case,
221 * we just fall out without adding anything to the prefix string.
222 */
225 break;
226
227 string[(*slength)++] =
c;
228
229 /* Advance to next state, but only if we have a unique next state */
230 } while (nextst != -1);
231
232 /*
233 * If we ended at a state that only has EOS/EOL outarcs leading to the
234 * "post" state, then we have an exact-match string. Note this is true
235 * even if the string is of zero length.
236 */
237 nextst = -1;
239 {
241 {
242 if (nextst == -1)
244 else if (nextst != ca->
to)
245 {
246 nextst = -1;
247 break;
248 }
249 }
250 else
251 {
252 nextst = -1;
253 break;
254 }
255 }
258
259 /*
260 * Otherwise, if we were unable to identify any prefix characters, say
261 * NOMATCH --- the pattern is anchored left, but doesn't specify any
262 * particular first character.
263 */
264 if (*slength > 0)
266
268}