diff options
Diffstat (limited to 'Src/Zle/compmatch.c')
| -rw-r--r-- | Src/Zle/compmatch.c | 1906 |
1 files changed, 1906 insertions, 0 deletions
diff --git a/Src/Zle/compmatch.c b/Src/Zle/compmatch.c new file mode 100644 index 000000000..32e0c3a68 --- /dev/null +++ b/Src/Zle/compmatch.c @@ -0,0 +1,1906 @@ +/* + * compmatch.c - the complete module, completion matching code + * + * This file is part of zsh, the Z shell. + * + * Copyright (c) 1999 Sven Wischnowsky + * All rights reserved. + * + * Permission is hereby granted, without written agreement and without + * license or royalty fees, to use, copy, modify, and distribute this + * software and to distribute modified versions of this software for any + * purpose, provided that the above copyright notice and the following + * two paragraphs appear in all copies of this software. + * + * In no event shall Sven Wischnowsky or the Zsh Development Group be liable + * to any party for direct, indirect, special, incidental, or consequential + * damages arising out of the use of this software and its documentation, + * even if Sven Wischnowsky and the Zsh Development Group have been advised of + * the possibility of such damage. + * + * Sven Wischnowsky and the Zsh Development Group specifically disclaim any + * warranties, including, but not limited to, the implied warranties of + * merchantability and fitness for a particular purpose. The software + * provided hereunder is on an "as is" basis, and Sven Wischnowsky and the + * Zsh Development Group have no obligation to provide maintenance, + * support, updates, enhancements, or modifications. + * + */ + +#include "complete.mdh" +#define GLOBAL_PROTOTYPES +#include "zle_tricky.pro" +#undef GLOBAL_PROTOTYPES +#include "compmatch.pro" + +/* Convenience macro for calling bslashquote() (formerly quotename()). */ + +#define quotename(s, e) bslashquote(s, e, instring) + +/* This compares two cpattern lists and returns non-zero if they are + * equal. */ + +/**/ +static int +cmp_cpatterns(Cpattern a, Cpattern b) +{ + while (a) { + if (a->equiv != b->equiv || memcmp(a->tab, b->tab, 256)) + return 0; + a = a->next; + b = b->next; + } + return 1; +} + +/* This compares two cmatchers and returns non-zero if they are equal. */ + +/**/ +static int +cmp_cmatchers(Cmatcher a, Cmatcher b) +{ + return (a == b || + (a->flags == b->flags && + a->llen == b->llen && a->wlen == b->wlen && + (!a->llen || cmp_cpatterns(a->line, b->line)) && + (a->wlen <= 0 || cmp_cpatterns(a->word, b->word)) && + (!(a->flags & CMF_LEFT) || + (a->lalen == b->lalen && + (!a->lalen || cmp_cpatterns(a->left, b->left)))) && + (!(a->flags & CMF_RIGHT) || + (a->ralen == b->ralen && + (!a->ralen || cmp_cpatterns(a->right, b->right)))))); +} + +/* Add the given matchers to the bmatcher list. */ + +/**/ +void +add_bmatchers(Cmatcher m) +{ + Cmlist old = bmatchers, *q = &bmatchers, n; + + for (; m; m = m->next) { + if ((!m->flags && m->wlen > 0 && m->llen > 0) || + (m->flags == CMF_RIGHT && m->wlen == -1 && !m->llen)) { + *q = n = (Cmlist) zhalloc(sizeof(struct cmlist)); + n->matcher = m; + q = &(n->next); + } + } + *q = old; +} + +/* This is called when the matchers in the mstack have changed to + * ensure that the bmatchers list contains no matchers not in mstack. */ + +/**/ +void +update_bmatchers(void) +{ + Cmlist p = bmatchers, q = NULL, ms; + Cmatcher mp; + int t; + + while (p) { + t = 0; + for (ms = mstack; ms && !t; ms = ms->next) + for (mp = ms->matcher; mp && !t; mp = mp->next) + t = cmp_cmatchers(mp, p->matcher); + + p = p->next; + if (!t) { + if (q) + q->next = p; + else + bmatchers = p; + } + } +} + +/* This returns a new Cline structure. */ + +/**/ +Cline +get_cline(char *l, int ll, char *w, int wl, char *o, int ol, int fl) +{ + Cline r; + + /* Prefer to take it from the buffer list (freecl), if there + * is none, allocate a new one. */ + + if ((r = freecl)) + freecl = r->next; + else + r = (Cline) zhalloc(sizeof(*r)); + + r->next = NULL; + r->line = l; r->llen = ll; + r->word = w; r->wlen = wl; + r->orig = o; r->olen = ol; + r->slen = 0; + r->flags = fl; + r->prefix = r->suffix = NULL; + return r; +} + +/* This frees a cline list. */ + +/**/ +void +free_cline(Cline l) +{ + Cline n; + + while (l) { + n = l->next; + l->next = freecl; + freecl = l; + free_cline(l->prefix); + free_cline(l->suffix); + l = n; + } +} + +/* Copy a cline list. */ + +/**/ +Cline +cp_cline(Cline l, int deep) +{ + Cline r = NULL, *p = &r, t, lp = NULL; + + while (l) { + if ((t = freecl)) + freecl = t->next; + else + t = (Cline) zhalloc(sizeof(*t)); + memcpy(t, l, sizeof(*t)); + if (deep) { + if (t->prefix) + t->prefix = cp_cline(t->prefix, 0); + if (t->suffix) + t->suffix = cp_cline(t->suffix, 0); + } + *p = lp = t; + p = &(t->next); + l = l->next; + } + *p = NULL; + + return r; +} + +/* Calculate the length of a cline and its sub-lists. */ + +/**/ +int +cline_sublen(Cline l) +{ + int len = ((l->flags & CLF_LINE) ? l->llen : l->wlen); + + if (l->olen && !((l->flags & CLF_SUF) ? l->suffix : l->prefix)) + len += l->olen; + else { + Cline p; + + for (p = l->prefix; p; p = p->next) + len += ((p->flags & CLF_LINE) ? p->llen : p->wlen); + for (p = l->suffix; p; p = p->next) + len += ((p->flags & CLF_LINE) ? p->llen : p->wlen); + } + return len; +} + +/* Set the lengths in the cline lists. */ + +/**/ +void +cline_setlens(Cline l, int both) +{ + while (l) { + l->max = cline_sublen(l); + if (both) + l->min = l->max; + l = l->next; + } +} + +/* This sets the CLF_MATCHED flag in the given clines. */ + +/**/ +void +cline_matched(Cline p) +{ + while (p) { + p->flags |= CLF_MATCHED; + cline_matched(p->prefix); + cline_matched(p->suffix); + + p = p->next; + } +} + +/* This reverts the order of the elements of the given cline list and + * returns a pointer to the new head. */ + +/**/ +Cline +revert_cline(Cline p) +{ + Cline r = NULL, n; + + while (p) { + n = p->next; + p->next = r; + r = p; + p = n; + } + return r; +} + +/* Global variables used during matching: a char-buffer for the string to + * use for the match, and two cline lists for the two levels we use. */ + +/**/ +char *matchbuf = NULL; +/**/ +int matchbuflen = 0, matchbufadded; + +/**/ +Cline matchparts, matchlastpart; +/**/ +Cline matchsubs, matchlastsub; + +/* This initialises the variables above. */ + +/**/ +static void +start_match(void) +{ + if (matchbuf) + *matchbuf = '\0'; + matchbufadded = 0; + matchparts = matchlastpart = matchsubs = matchlastsub = NULL; +} + +/* This aborts a matching, freeing the cline lists build. */ + +/**/ +static void +abort_match(void) +{ + free_cline(matchparts); + free_cline(matchsubs); + matchparts = matchsubs = NULL; +} + +/* This adds a new string in the static char buffer. The arguments are + * the matcher used (if any), the strings from the line and the word + * and the length of the string from the word. The last argument is + * non-zero if we are matching a suffix (where the given string has to + * be prepended to the contents of the buffer). */ + +/**/ +static void +add_match_str(Cmatcher m, char *l, char *w, int wl, int sfx) +{ + /* Get the string and length to insert: either from the line + * or from the match. */ + if (m && (m->flags & CMF_LINE)) { + wl = m->llen; w = l; + } + if (wl) { + /* Probably resize the buffer. */ + if (matchbuflen - matchbufadded <= wl) { + int blen = matchbuflen + wl + 20; + char *buf; + + buf = (char *) zalloc(blen); + memcpy(buf, matchbuf, matchbuflen); + zfree(matchbuf, matchbuflen); + matchbuf = buf; + matchbuflen = blen; + } + /* Insert the string. */ + if (sfx) { + memmove(matchbuf + wl, matchbuf, matchbufadded + 1); + memcpy(matchbuf, w, wl); + } else + memcpy(matchbuf + matchbufadded, w, wl); + matchbufadded += wl; + matchbuf[matchbufadded] = '\0'; + } +} + +/* This adds a cline for a word-part during matching. Arguments are the + * matcher used, pointers to the line and word strings for the anchor, + * a pointer to the original line string for the whole part, the string + * before (or after) the anchor that has not yet been added, the length + * of the line-string for that, and a flag saying if we are matching a + * suffix. */ + +/**/ +static void +add_match_part(Cmatcher m, char *l, char *w, int wl, + char *o, int ol, char *s, int sl, int osl, int sfx) +{ + Cline p, lp; + + /* If the anchors are equal, we keep only one. */ + + if (!strncmp(l, w, wl)) + l = NULL; + + /* Split the new part into parts and turn the last one into a + * `suffix' if we have a left anchor. */ + + p = bld_parts(s, sl, osl, &lp); + + p->flags &= ~CLF_NEW; + if (m && (m->flags & CMF_LEFT)) { + lp->flags |= CLF_SUF; + lp->suffix = lp->prefix; + lp->prefix = NULL; + } + /* cline lists for suffixes are sorted from back to front, so we have + * to revert the list we got. */ + if (sfx) + p = revert_cline(lp = p); + /* Now add the sub-clines we already had. */ + if (matchsubs) { + if (sfx) { + Cline q; + + if ((q = lp->prefix)) { + while (q->next) + q = q->next; + q->next = matchsubs; + } else + lp->prefix = matchsubs; + + matchlastsub->next = NULL; + } else { + matchlastsub->next = p->prefix; + p->prefix = matchsubs; + } + matchsubs = matchlastsub = NULL; + } + /* Store the arguments in the last part-cline. */ + lp->line = l; lp->llen = wl; + lp->word = w; lp->wlen = wl; + lp->orig = o; lp->olen = ol; + lp->flags &= ~CLF_NEW; + + /* Finally, put the new parts on the list. */ + if (matchlastpart) + matchlastpart->next = p; + else + matchparts = p; + matchlastpart = lp; +} + +/* This adds a new sub-cline. Arguments are the matcher and the strings from + * the line and the word. */ + +/**/ +static void +add_match_sub(Cmatcher m, char *l, int ll, char *w, int wl) +{ + int flags; + Cline n; + + /* Check if we are interested only in the string from the line. */ + if (m && (m->flags & CMF_LINE)) { + w = NULL; wl = 0; + flags = CLF_LINE; + } else + flags = 0; + + /* And add the cline. */ + if (wl || ll) { + n = get_cline(l, ll, w, wl, NULL, 0, flags); + if (matchlastsub) + matchlastsub->next = n; + else + matchsubs = n; + matchlastsub = n; + } +} + +/* This tests if the string from the line l matches the word w. In bp + * the offset for the brace is returned, in rwlp the length of the + * matched prefix or suffix, not including the stuff before or after + * the last anchor is given. When sfx is non-zero matching is done from + * the ends of the strings backward, if test is zero, the global variables + * above are used to build the string for the match and the cline. If + * part is non-zero, we are satisfied if only a part of the line-string + * is used (and return the length used). */ + +/**/ +int +match_str(char *l, char *w, Brinfo *bpp, int bc, int *rwlp, + int sfx, int test, int part) +{ + int ll = strlen(l), lw = strlen(w), oll = ll, olw = lw; + int il = 0, iw = 0, t, ind, add, he = 0, bpc, obc = bc; + VARARR(unsigned char, ea, ll + 1); + char *ow; + Cmlist ms; + Cmatcher mp, lm = NULL; + Brinfo bp = NULL; + + if (!test) { + start_match(); + bp = *bpp; + } + /* Adjust the pointers and get the values for subscripting and + * incrementing. */ + + if (sfx) { + l += ll; w += lw; + ind = -1; add = -1; + } else { + ind = 0; add = 1; + } + /* ow will always point to the beginning (or end) of that sub-string + * in w that wasn't put in the match-variables yet. */ + + ow = w; + + /* If the brace is at the beginning, we have to treat it now. */ + + if (!test && bp && bc >= bp->pos) { + bp->curpos = bc; + bp = bp->next; + } + while (ll && lw) { + /* First try the matchers. */ + for (mp = NULL, ms = mstack; !mp && ms; ms = ms->next) { + for (mp = ms->matcher; mp; mp = mp->next) { + t = 1; + if ((lm && lm == mp) || + ((oll == ll || olw == lw) && + (test == 1 || (test && !mp->left && !mp->right)) && + mp->wlen < 0)) + /* If we were called recursively, don't use `*' patterns + * at the beginning (avoiding infinite recursion). */ + continue; + + if (mp->wlen < 0) { + int both, loff, aoff, llen, alen, zoff, moff, ct, ict; + char *tp, savl = '\0', savw; + Cpattern ap; + + /* This is for `*' patterns, first initialise some + * local variables. */ + llen = mp->llen; + alen = (mp->flags & CMF_LEFT ? mp->lalen : mp->ralen); + + /* Give up if we don't have enough characters for the + * line-string and the anchor. */ + if (ll < llen + alen || lw < alen) + continue; + + if (mp->flags & CMF_LEFT) { + ap = mp->left; zoff = 0; moff = alen; + if (sfx) { + both = 0; loff = -llen; aoff = -(llen + alen); + } else { + both = 1; loff = alen; aoff = 0; + } + } else { + ap = mp->right; zoff = alen; moff = 0; + if (sfx) { + both = 1; loff = -(llen + alen); aoff = -alen; + } else { + both = 0; loff = 0; aoff = llen; + } + } + /* Try to match the line pattern and the anchor. */ + if (!pattern_match(mp->line, l + loff, NULL, NULL)) + continue; + if (ap) { + if (!pattern_match(ap, l + aoff, NULL, NULL) || + (both && (!pattern_match(ap, w + aoff, NULL, NULL) || + !match_parts(l + aoff, w + aoff, alen, + part)))) + continue; + } else if (!both || il || iw) + continue; + + /* Fine, now we call ourselves recursively to find the + * string matched by the `*'. */ + if (sfx) { + savl = l[-(llen + zoff)]; + l[-(llen + zoff)] = '\0'; + } + for (t = 0, tp = w, ct = 0, ict = lw - alen + 1; + ict; + tp += add, ct++, ict--) { + if ((both && + (!ap || !test || + !pattern_match(ap, tp + aoff, NULL, NULL))) || + (!both && + pattern_match(ap, tp - moff, NULL, NULL) && + match_parts(l + aoff , tp - moff, alen, part))) { + if (sfx) { + savw = tp[-zoff]; + tp[-zoff] = '\0'; + t = match_str(l - ll, w - lw, + NULL, 0, NULL, 1, 2, part); + tp[-zoff] = savw; + } else + t = match_str(l + llen + moff, tp + moff, + NULL, 0, NULL, 0, 1, part); + if (t || !both) + break; + } + } + ict = ct; + if (sfx) + l[-(llen + zoff)] = savl; + + /* Have we found a position in w where the rest of l + * matches? */ + if (!t) + continue; + + /* Yes, add the strings and clines if this is a + * top-level call. */ + if (!test && (!he || (llen + alen))) { + char *op, *lp, *map, *wap, *wmp; + int ol; + + if (sfx) { + op = w; ol = ow - w; lp = l - (llen + alen); + map = tp - alen; + if (mp->flags & CMF_LEFT) { + wap = tp - alen; wmp = tp; + } else { + wap = w - alen; wmp = tp - alen; + } + } else { + op = ow; ol = w - ow; lp = l; + map = ow; + if (mp->flags & CMF_LEFT) { + wap = w; wmp = w + alen; + } else { + wap = tp; wmp = ow; + } + } + /* If the matcher says that we are only interested + * in the line pattern, we just add that and the + * anchor and the string not added yet. Otherwise + * we add a new part. */ + if (mp->flags & CMF_LINE) { + add_match_str(NULL, NULL, op, ol, sfx); + add_match_str(NULL, NULL, lp, llen + alen, sfx); + add_match_sub(NULL, NULL, ol, op, ol); + add_match_sub(NULL, NULL, llen + alen, + lp, llen + alen); + } else if (sfx) { + add_match_str(NULL, NULL, + map, ct + ol + alen, sfx); + add_match_part(mp, l + aoff, wap, alen, + l + loff, llen, op, ol, ol, sfx); + add_match_sub(NULL, NULL, 0, wmp, ct); + } else { + add_match_str(NULL, NULL, + map, ct + ol + alen, sfx); + if (both) { + add_match_sub(NULL, NULL, ol, op, ol); + ol = -1; + } else + ct += ol; + add_match_part(mp, l + aoff, wap, alen, + l + loff, llen, wmp, ct, ol, sfx); + } + } + /* Now skip over the matched portion and the anchor. */ + llen += alen; alen += ict; + if (sfx) { + l -= llen; w -= alen; + } else { + l += llen; w += alen; + } + ll -= llen; il += llen; + lw -= alen; iw += alen; + bc += llen; + + if (!test) + while (bp && + bc >= (bpc = (useqbr ? bp->qpos : bp->pos))) { + bp->curpos = matchbufadded + bpc - bc + obc; + bp = bp->next; + } + ow = w; + + if (!llen && !alen) { + lm = mp; + if (he) + mp = NULL; + else + he = 1; + } else { + lm = NULL; he = 0; + } + break; + } else if (ll >= mp->llen && lw >= mp->wlen) { + /* Non-`*'-pattern. */ + char *tl, *tw; + int tll, tlw, til, tiw; + + /* We do this only if the line- and word-substrings + * are not equal. */ + if (!(mp->flags & (CMF_LEFT | CMF_RIGHT)) && + mp->llen == mp->wlen && + !(sfx ? strncmp(l - mp->llen, w - mp->wlen, mp->llen) : + strncmp(l, w, mp->llen))) + continue; + + /* Using local variables to make the following + * independent of whether we match a prefix or a + * suffix. */ + if (sfx) { + tl = l - mp->llen; tw = w - mp->wlen; + til = ll - mp->llen; tiw = lw - mp->wlen; + tll = il + mp->llen; tlw = iw + mp->wlen; + } else { + tl = l; tw = w; + til = il; tiw = iw; + tll = ll; tlw = lw; + } + if (mp->flags & CMF_LEFT) { + /* Try to match the left anchor, if any. */ + if (til < mp->lalen || tiw < mp->lalen) + continue; + else if (mp->left) + t = pattern_match(mp->left, tl - mp->lalen, + NULL, NULL) && + pattern_match(mp->left, tw - mp->lalen, + NULL, NULL); + else + t = (!sfx && !il && !iw); + } + if (mp->flags & CMF_RIGHT) { + /* Try to match the right anchor, if any. */ + if (tll < mp->llen + mp->ralen || + tlw < mp->wlen + mp->ralen) + continue; + else if (mp->left) + t = pattern_match(mp->right, + tl + mp->llen - mp->ralen, + NULL, NULL) && + pattern_match(mp->right, + tw + mp->wlen - mp->ralen, + NULL, NULL); + else + t = (sfx && !il && !iw); + } + /* Now try to match the line and word patterns. */ + if (!t || + !pattern_match(mp->line, tl, NULL, ea) || + !pattern_match(mp->word, tw, ea, NULL)) + continue; + + /* Probably add the matched strings. */ + if (!test) { + if (sfx) + add_match_str(NULL, NULL, w, ow - w, 0); + else + add_match_str(NULL, NULL, ow, w - ow, 0); + add_match_str(mp, tl, tw, mp->wlen, 0); + if (sfx) + add_match_sub(NULL, NULL, 0, w, ow - w); + else + add_match_sub(NULL, NULL, 0, ow, w - ow); + + add_match_sub(mp, tl, mp->llen, tw, mp->wlen); + } + if (sfx) { + l = tl; w = tw; + } else { + l += mp->llen; w += mp->wlen; + } + il += mp->llen; iw += mp->wlen; + ll -= mp->llen; lw -= mp->wlen; + bc += mp->llen; + + if (!test) + while (bp && + bc >= (bpc = (useqbr ? bp->qpos : bp->pos))) { + bp->curpos = matchbufadded + bpc - bc + obc; + bp = bp->next; + } + ow = w; + lm = NULL; + he = 0; + break; + } + } + } + if (mp) + continue; + + if (l[ind] == w[ind]) { + /* No matcher could be used, but the strings have the same + * character here, skip over it. */ + l += add; w += add; + il++; iw++; + ll--; lw--; + bc++; + if (!test) + while (bp && bc >= (useqbr ? bp->qpos : bp->pos)) { + bp->curpos = matchbufadded + (sfx ? (ow - w) : (w - ow)) + obc; + bp = bp->next; + } + lm = NULL; + he = 0; + } else { + /* No matcher and different characters: l does not match w. */ + if (test) + return 0; + + abort_match(); + + return -1; + } + } + /* If this is a recursive call, we just return if l matched w or not. */ + if (test) + return (part || !ll); + + /* In top-level calls, if ll is non-zero (unmatched portion in l), + * we have to free the collected clines. */ + if (!part && ll) { + abort_match(); + + return -1; + } + if (rwlp) + *rwlp = iw - (sfx ? ow - w : w - ow); + + /* If we matched a suffix, the anchors stored in the top-clines + * will be in the wrong clines: shifted by one. Adjust this. */ + if (sfx && matchparts) { + Cline t, tn, s; + + if (matchparts->prefix || matchparts->suffix) { + t = get_cline(NULL, 0, NULL, 0, NULL, 0, 0); + t->next = matchparts; + if (matchparts->prefix) + t->prefix = (Cline) 1; + else + t->suffix = (Cline) 1; + matchparts = t; + } + for (t = matchparts; (tn = t->next); t = tn) { + s = (tn->prefix ? tn->prefix : tn->suffix); + if (t->suffix) + t->suffix = s; + else + t->prefix = s; + } + t->prefix = t->suffix = NULL; + } + /* Finally, return the number of matched characters. */ + + *bpp = bp; + return (part ? il : iw); +} + +/* Wrapper for match_str(), only for a certain length and only doing + * the test. */ + +/**/ +static int +match_parts(char *l, char *w, int n, int part) +{ + char lsav = l[n], wsav = w[n]; + int ret; + + l[n] = w[n] = '\0'; + ret = match_str(l, w, NULL, 0, NULL, 0, 1, part); + l[n] = lsav; + w[n] = wsav; + + return ret; +} + +/* Check if the word w is matched by the strings in pfx and sfx (the prefix + * and the suffix from the line) or the pattern cp. In clp a cline list for + * w is returned. + * qu is non-zero if the words has to be quoted before processed any further. + * bpl and bsl are used to report the positions where the brace-strings in + * the prefix and the suffix have to be re-inserted if this match is inserted + * in the line. + * The return value is the string to use as a completion or NULL if the prefix + * and the suffix don't match the word w. */ + +/**/ +char * +comp_match(char *pfx, char *sfx, char *w, Patprog cp, Cline *clp, int qu, + Brinfo *bpl, int bcp, Brinfo *bsl, int bcs, int *exact) +{ + char *r = NULL; + + if (cp) { + /* We have a globcomplete-like pattern, just use that. */ + int wl; + + r = w; + if (!pattry(cp, r)) + return NULL; + + r = (qu ? quotename(r, NULL) : dupstring(r)); + if (qu == 2 && r[0] == '\\' && r[1] == '~') + chuck(r); + /* We still break it into parts here, trying to build a sensible + * cline list for these matches, too. */ + w = dupstring(w); + wl = strlen(w); + *clp = bld_parts(w, wl, wl, NULL); + *exact = 0; + } else { + Cline pli, plil; + int mpl, rpl, wl; + + w = (qu ? quotename(w, NULL) : dupstring(w)); + if (qu == 2 && w[0] == '\\' && w[1] == '~') + chuck(w); + + wl = strlen(w); + + /* Always try to match the prefix. */ + + useqbr = qu; + if ((mpl = match_str(pfx, w, bpl, bcp, &rpl, 0, 0, 0)) < 0) + return NULL; + + if (sfx && *sfx) { + int wpl = matchbufadded, msl, rsl; + VARARR(char, wpfx, wpl); + Cline mli, mlil; + + /* We also have a suffix to match, so first save the + * contents of the global matching variables. */ + memcpy(wpfx, matchbuf, wpl); + if (matchsubs) { + Cline tmp = get_cline(NULL, 0, NULL, 0, NULL, 0, 0); + + tmp->prefix = matchsubs; + if (matchlastpart) + matchlastpart->next = tmp; + else + matchparts = tmp; + } + pli = matchparts; + plil = matchlastpart; + + /* The try to match the suffix. */ + + if ((msl = match_str(sfx, w + mpl, bsl, bcs, &rsl, 1, 0, 0)) < 0) { + free_cline(pli); + + return NULL; + } + /* Matched, so add the string in the middle and the saved + * string for the prefix, and build a combined cline list + * for the prefix and the suffix. */ + if (matchsubs) { + Cline tmp = get_cline(NULL, 0, NULL, 0, NULL, 0, CLF_SUF); + + tmp->suffix = matchsubs; + if (matchlastpart) + matchlastpart->next = tmp; + else + matchparts = tmp; + } + add_match_str(NULL, NULL, w + rpl, wl - rpl - rsl, 1); + add_match_str(NULL, NULL, wpfx, wpl, 1); + + mli = bld_parts(w + rpl, wl - rpl - rsl, + (mpl - rpl) + (msl - rsl), &mlil); + mlil->flags |= CLF_MID; + mlil->slen = msl - rsl; + mlil->next = revert_cline(matchparts); + + if (plil) + plil->next = mli; + else + pli = mli; + } else { + /* Only a prefix, add the string and a part-cline for it. */ + add_match_str(NULL, NULL, w + rpl, wl - rpl, 0); + + add_match_part(NULL, NULL, NULL, 0, NULL, 0, w + rpl, wl - rpl, + mpl - rpl, 0); + pli = matchparts; + } + r = dupstring(matchbuf ? matchbuf : ""); + + *clp = pli; + + /* Test if the string built is equal to the one from the line. */ + if (sfx && *sfx) { + int pl = strlen(pfx); + + *exact = (!strncmp(pfx, w, pl) && !strcmp(sfx, w + pl)); + } else + *exact = !strcmp(pfx, w); + } + if (!qu) + hasunqu = 1; + + return r; +} + +/* Check if the given pattern matches the given string. * + * `in' and `out' are used for {...} classes. In `out' we store the * + * character number that was matched. In the word pattern this is * + * given in `in' so that we can easily test if we found the * + * corresponding character. */ + +/**/ +static int +pattern_match(Cpattern p, char *s, unsigned char *in, unsigned char *out) +{ + unsigned char c; + + while (p) { + c = *((unsigned char *) s); + + if (out) + *out = 0; + + if (p->equiv) { + if (in) { + c = p->tab[c]; + if ((*in && *in != c) || (!*in && !c)) + return 0; + } else if (out) { + if (!(*out = p->tab[c])) + return 0; + } else if (!p->tab[c]) + return 0; + + if (in && *in) + in++; + if (out) + out++; + } else if (!p->tab[c]) + return 0; + + s++; + p = p->next; + } + return 1; +} + +/* This splits the given string into a list of cline structs, separated + * at those places where one of the anchors of an `*' pattern was found. + * plen gives the number of characters on the line that matched this + * string. In lp we return a pointer to the last cline struct we build. */ + +/**/ +Cline +bld_parts(char *str, int len, int plen, Cline *lp) +{ + Cline ret = NULL, *q = &ret, n; + Cmlist ms; + Cmatcher mp; + int t, op = plen; + char *p = str; + + while (len) { + for (t = 0, ms = bmatchers; ms && !t; ms = ms->next) { + mp = ms->matcher; + if (mp->flags == CMF_RIGHT && mp->wlen == -1 && + !mp->llen && len >= mp->ralen && mp->ralen && + pattern_match(mp->right, str, NULL, NULL)) { + int olen = str - p, llen; + + /* We found an anchor, create a new cline. The NEW flag + * is set if the characters before the anchor were not + * on the line. */ + *q = n = get_cline(NULL, mp->ralen, str, mp->ralen, NULL, 0, + ((plen < 0) ? CLF_NEW : 0)); + + /* If there were any characters before the anchor, add + * them as a cline struct. */ + + if (p != str) { + llen = (op < 0 ? 0 : op); + + if (llen > olen) + llen = olen; + n->prefix = get_cline(NULL, llen, p, olen, NULL, 0, 0); + } + q = &(n->next); + str += mp->ralen; len -= mp->ralen; + plen -= mp->ralen; + op -= olen; + p = str; + t = 1; + } + } + if (!t) { + /* No anchor was found here, skip. */ + str++; len--; + plen--; + } + } + /* This is the cline struct for the remaining string at the end. */ + + *q = n = get_cline(NULL, 0, NULL, 0, NULL, 0, (plen < 0 ? CLF_NEW : 0)); + if (p != str) { + int olen = str - p, llen = (op < 0 ? 0 : op); + + if (llen > olen) + llen = olen; + n->prefix = get_cline(NULL, llen, p, olen, NULL, 0, 0); + } + n->next = NULL; + + if (lp) + *lp = n; + + return ret; +} + +/* This builds all the possible line patterns for the pattern pat in the + * buffer line. Initially line is the same as lp, but during recursive + * calls lp is incremented for storing successive characters. Whenever + * a full possible string is build, we test if this line matches the + * string given by wlen and word. The in argument contains the characters + * to use for the correspondence classes, it was filled by a call to + * pattern_match() in the calling function. + * The return value is the length of the string matched in the word, it + * is zero if we couldn't build a line that matches the word. */ + +/**/ +static int +bld_line(Cpattern pat, char *line, char *lp, + char *word, int wlen, unsigned char *in, int sfx) +{ + if (pat) { + /* Still working on the pattern. */ + + int i, l; + unsigned char c = 0; + + /* Get the number of the character for a correspondence class + * if it has a correxponding class. */ + if (pat->equiv) + if ((c = *in)) + in++; + + /* Walk through the table in the pattern and try the characters + * that may appear in the current position. */ + for (i = 0; i < 256; i++) + if ((pat->equiv && c) ? (c == pat->tab[i]) : pat->tab[i]) { + *lp = i; + /* We stored the character, now call ourselves to build + * the rest. */ + if ((l = bld_line(pat->next, line, lp + 1, word, wlen, + in, sfx))) + return l; + } + } else { + /* We reached the end, i.e. the line string is fully build, now + * see if it matches the given word. */ + + Cmlist ms; + Cmatcher mp; + int l = lp - line, t, rl = 0, ind, add; + VARARR(unsigned char, ea, l + 1); + + /* Quick test if the strings are exactly the same. */ + if (l == wlen && !strncmp(line, word, l)) + return l; + + if (sfx) { + line = lp; word += wlen; + ind = -1; add = -1; + } else { + ind = 0; add = 1; + } + /* We loop through the whole line string built. */ + while (l && wlen) { + if (word[ind] == line[ind]) { + /* The same character in both strings, skip over. */ + line += add; word += add; + l--; wlen--; rl++; + } else { + t = 0; + for (ms = bmatchers; ms && !t; ms = ms->next) { + mp = ms->matcher; + if (!mp->flags && mp->wlen <= wlen && mp->llen <= l && + pattern_match(mp->line, (sfx ? line - mp->llen : line), + NULL, ea) && + pattern_match(mp->word, (sfx ? word - mp->wlen : word), + ea, NULL)) { + /* Both the line and the word pattern matched, + * now skip over the matched portions. */ + if (sfx) { + line -= mp->llen; word -= mp->wlen; + } else { + line += mp->llen; word += mp->wlen; + } + l -= mp->llen; wlen -= mp->wlen; rl += mp->wlen; + t = 1; + } + } + if (!t) + /* Didn't match, give up. */ + return 0; + } + } + if (!l) + /* Unmatched portion in the line built, return matched length. */ + return rl; + } + return 0; +} + +/* This builds a string that may be put on the line that fully matches the + * given strings. The return value is NULL if no such string could be built + * or that string in local static memory, dup it. */ + +/**/ +static char * +join_strs(int la, char *sa, int lb, char *sb) +{ + static char *rs = NULL; + static int rl = 0; + + VARARR(unsigned char, ea, (la > lb ? la : lb) + 1); + Cmlist ms; + Cmatcher mp; + int t, bl, rr = rl; + char *rp = rs; + + while (la && lb) { + if (*sa != *sb) { + /* Different characters, try the matchers. */ + for (t = 0, ms = bmatchers; ms && !t; ms = ms->next) { + mp = ms->matcher; + if (!mp->flags && mp->wlen > 0 && mp->llen > 0 && + mp->wlen <= la && mp->wlen <= lb) { + /* The pattern has no anchors and the word + * pattern fits, try it. */ + if ((t = pattern_match(mp->word, sa, NULL, ea)) || + pattern_match(mp->word, sb, NULL, ea)) { + /* It matched one of the strings, t says which one. */ + VARARR(char, line, mp->llen + 1); + char **ap, **bp; + int *alp, *blp; + + if (t) { + ap = &sa; alp = &la; + bp = &sb; blp = &lb; + } else { + ap = &sb; alp = &lb; + bp = &sa; blp = &la; + } + /* Now try to build a string that matches the other + * string. */ + if ((bl = bld_line(mp->line, line, line, + *bp, *blp, ea, 0))) { + /* Found one, put it into the return string. */ + line[mp->llen] = '\0'; + if (rr <= mp->llen) { + char *or = rs; + + rs = realloc(rs, (rl += 20)); + rr += 20; + rp += rs - or; + } + memcpy(rp, line, mp->llen); + rp += mp->llen; rr -= mp->llen; + *ap += mp->wlen; *alp -= mp->wlen; + *bp += bl; *blp -= bl; + t = 1; + } else + t = 0; + } + } + } + if (!t) + break; + } else { + /* Same character, just take it. */ + if (rr <= 1) { + char *or = rs; + + rs = realloc(rs, (rl += 20)); + rr += 20; + rp += rs - or; + } + *rp++ = *sa; rr--; + sa++; sb++; + la--; lb--; + } + } + if (la || lb) + return NULL; + + *rp = '\0'; + + return rs; +} + +/* This compares the anchors stored in two top-level clines. */ + +/**/ +static int +cmp_anchors(Cline o, Cline n, int join) +{ + int line = 0; + char *j; + + /* First try the exact strings. */ + if ((!(o->flags & CLF_LINE) && o->wlen == n->wlen && + (!o->word || !strncmp(o->word, n->word, o->wlen))) || + (line = ((!o->line && !n->line && !o->wlen && !n->wlen) || + (o->llen == n->llen && o->line && n->line && + !strncmp(o->line, n->line, o->llen))))) { + if (line) { + o->flags |= CLF_LINE; + o->word = NULL; + n->wlen = 0; + } + return 1; + } + /* Didn't work, try to build a string matching both anchors. */ + if (join && !(o->flags & CLF_JOIN) && o->word && n->word && + (j = join_strs(o->wlen, o->word, n->wlen, n->word))) { + o->flags |= CLF_JOIN; + o->wlen = strlen(j); + o->word = dupstring(j); + + return 2; + } + return 0; +} + +/* Below is the code to join two cline lists. This struct is used to walk + * through a sub-list. */ + +typedef struct cmdata *Cmdata; + +struct cmdata { + Cline cl, pcl; + char *str, *astr; + int len, alen, olen, line; +}; + +/* This is used to ensure that a cmdata struct contains usable data. + * The return value is non-zero if we reached the end. */ + +static int +check_cmdata(Cmdata md, int sfx) +{ + /* We will use the str and len fields to contain the next sub-string + * in the list. If len is zero, we have to use the next cline. */ + if (!md->len) { + /* If there is none, we reached the end. */ + if (!md->cl) + return 1; + + /* Otherwise, get the string. Only the line-string or both. + * We also have to adjust the pointer if this is for a suffix. */ + if (md->cl->flags & CLF_LINE) { + md->line = 1; + md->len = md->cl->llen; + md->str = md->cl->line; + } else { + md->line = 0; + md->len = md->olen = md->cl->wlen; + if ((md->str = md->cl->word) && sfx) + md->str += md->len; + md->alen = md->cl->llen; + if ((md->astr = md->cl->line) && sfx) + md->astr += md->alen; + } + md->pcl = md->cl; + md->cl = md->cl->next; + } + return 0; +} + +/* This puts the not-yet-matched portion back into the last cline and + * returns that. */ + +static Cline +undo_cmdata(Cmdata md, int sfx) +{ + Cline r = md->pcl; + + if (md->line) { + r->word = NULL; + r->wlen = 0; + r->flags |= CLF_LINE; + r->llen = md->len; + r->line = md->str - (sfx ? md->len : 0); + } else if (md->len != md->olen) { + r->wlen = md->len; + r->word = md->str - (sfx ? md->len : 0); + } + return r; +} + +/* This tries to build a string matching a sub-string in a sub-cline + * that could not be matched otherwise. */ + +static Cline +join_sub(Cmdata md, char *str, int len, int *mlen, int sfx, int join) +{ + if (!check_cmdata(md, sfx)) { + char *ow = str, *nw = md->str; + int ol = len, nl = md->len; + Cmlist ms; + Cmatcher mp; + VARARR(unsigned char, ea, (ol > nl ? ol : nl) + 1); + int t; + + if (sfx) { + ow += ol; nw += nl; + } + for (t = 0, ms = bmatchers; ms && !t; ms = ms->next) { + mp = ms->matcher; + /* We use only those patterns that match a non-empty + * string in both the line and the word and that have + * no anchors. */ + if (!mp->flags && mp->wlen > 0 && mp->llen > 0) { + /* We first test, if the old string matches already the + * new one. */ + if (mp->llen <= ol && mp->wlen <= nl && + pattern_match(mp->line, ow - (sfx ? mp->llen : 0), + NULL, ea) && + pattern_match(mp->word, nw - (sfx ? mp->wlen : 0), + ea, NULL)) { + /* It did, update the contents of the cmdata struct + * and return a cline for the matched part. */ + if (sfx) + md->str -= mp->wlen; + else + md->str += mp->wlen; + md->len -= mp->wlen; + *mlen = mp->llen; + + return get_cline(NULL, 0, ow - (sfx ? mp->llen : 0), + mp->llen, NULL, 0, 0); + } + /* Otherwise we will try to build a string that matches + * both strings. But try the pattern only if the word- + * pattern matches one of the strings. */ + if (join && mp->wlen <= ol && mp->wlen <= nl && + ((t = pattern_match(mp->word, ow - (sfx ? mp->wlen : 0), + NULL, ea)) || + pattern_match(mp->word, nw - (sfx ? mp->wlen : 0), + NULL, ea))) { + VARARR(char, line, mp->llen + 1); + int bl; + + /* Then build all the possible lines and see + * if one of them matches the other string. */ + if ((bl = bld_line(mp->line, line, line, + (t ? nw : ow), (t ? nl : ol), + ea, sfx))) { + /* Yep, one of the lines matched the other + * string. */ + line[mp->llen] = '\0'; + + if (t) { + ol = mp->wlen; nl = bl; + } else { + ol = bl; nl = mp->wlen; + } + if (sfx) + md->str -= nl; + else + md->str += nl; + md->len -= nl; + *mlen = ol; + + return get_cline(NULL, 0, dupstring(line), mp->llen, + NULL, 0, CLF_JOIN); + } + } + } + } + } + return NULL; +} + +/* This is used to match a sub-string in a sub-cline. The length of the + * matched portion is returned. This tests only for exact equality. */ + +static int +sub_match(Cmdata md, char *str, int len, int sfx) +{ + int ret = 0, l, ind, add; + char *p, *q; + + if (sfx) { + str += len; + ind = -1; add = -1; + } else { + ind = 0; add = 1; + } + /* str and len describe the old string, in md we have the new one. */ + while (len) { + if (check_cmdata(md, sfx)) + return ret; + + for (l = 0, p = str, q = md->str; + l < len && l < md->len && p[ind] == q[ind]; + l++, p += add, q += add); + + if (l) { + /* There was a common prefix, use it. */ + md->len -= l; len -= l; + if (sfx) { + md->str -= l; str -= l; + } else { + md->str += l; str += l; + } + ret += l; + } else if (md->line || md->len != md->olen || !md->astr) + return ret; + else { + /* We still have the line string to try. */ + md->line = 1; + md->len = md->alen; + md->str = md->astr; + } + } + return ret; +} + +/* This is used to build a common prefix or suffix sub-list. If requested + * it returns the unmatched cline lists in orest and nrest. */ + +/**/ +static void +join_psfx(Cline ot, Cline nt, Cline *orest, Cline *nrest, int sfx) +{ + Cline p = NULL, o, n; + struct cmdata md, omd; + char **sstr = NULL; + int len, join = 0, line = 0, *slen = NULL; + + if (sfx) { + o = ot->suffix; n = nt->suffix; + } else { + o = ot->prefix; n = nt->prefix; + } + if (!o) { + if (orest) + *orest = NULL; + if (nrest) + *nrest = n; + + return; + } + if (!n) { + if (sfx) + ot->suffix = NULL; + else + ot->prefix = NULL; + + if (orest) + *orest = o; + else + free_cline(o); + if (nrest) + *nrest = NULL; + return; + } + md.cl = n; + md.len = 0; + + /* Walk through the old list. */ + while (o) { + join = 0; + memcpy(&omd, &md, sizeof(struct cmdata)); + + /* We first get the length of the prefix equal in both strings. */ + if (o->flags & CLF_LINE) { + if ((len = sub_match(&md, o->line, o->llen, sfx)) != o->llen) { + join = 1; line = 1; slen = &(o->llen); sstr = &(o->line); + } + } else if ((len = sub_match(&md, o->word, o->wlen, sfx)) != o->wlen) { + if (o->line) { + memcpy(&md, &omd, sizeof(struct cmdata)); + o->flags |= CLF_LINE | CLF_DIFF; + + continue; + } + join = 1; line = 0; slen = &(o->wlen); sstr = &(o->word); + } + if (join) { + /* There is a rest that is different in the two lists, + * we try to build a new cline matching both strings. */ + Cline joinl; + int jlen; + + if ((joinl = join_sub(&md, *sstr + len, *slen - len, + &jlen, sfx, !(o->flags & CLF_JOIN)))) { + /* We have one, insert it into the list. */ + joinl->flags |= CLF_DIFF; + if (len + jlen != *slen) { + Cline rest; + + rest = get_cline(NULL, 0, *sstr + (sfx ? 0 : len + jlen), + *slen - len - jlen, NULL, 0, 0); + + rest->next = o->next; + joinl->next = rest; + } else + joinl->next = o->next; + + if (len) { + if (sfx) + *sstr += *slen - len; + *slen = len; + o->next = joinl; + } else { + o->next = NULL; + free_cline(o); + if (p) + p->next = joinl; + else if (sfx) + ot->suffix = joinl; + else + ot->prefix = joinl; + } + o = joinl; + join = 0; + } + } + if (join) { + /* We couldn't build a cline for a common string, so we + * cut the list here. */ + if (len) { + Cline r; + + if (orest) { + if (line) + r = get_cline(o->line + len, *slen - len, + NULL, 0, NULL, 0, o->flags); + else + r = get_cline(NULL, 0, o->word + len, *slen - len, + NULL, 0, o->flags); + + r->next = o->next; + *orest = r; + + *slen = len; + o->next = NULL; + } else { + if (sfx) + *sstr += *slen - len; + *slen = len; + free_cline(o->next); + o->next = NULL; + } + } else { + if (p) + p->next = NULL; + else if (sfx) + ot->suffix = NULL; + else + ot->prefix = NULL; + + if (orest) + *orest = o; + else + free_cline(o); + } + if (!orest || !nrest) + ot->flags |= CLF_MISS; + + if (nrest) + *nrest = undo_cmdata(&md, sfx); + + return; + } + p = o; + o = o->next; + } + if (md.len || md.cl) + ot->flags |= CLF_MISS; + if (orest) + *orest = NULL; + if (nrest) + *nrest = undo_cmdata(&md, sfx); +} + +/* This builds the common prefix and suffix for a mid-cline -- the one + * describing the place where the prefix and the suffix meet. */ + +/**/ +static void +join_mid(Cline o, Cline n) +{ + if (o->flags & CLF_JOIN) { + /* The JOIN flag is set in the old cline struct if it was + * already joined with another one. In this case the suffix + * field contains the suffix from previous calls. */ + Cline nr; + + join_psfx(o, n, NULL, &nr, 0); + + n->suffix = revert_cline(nr); + + join_psfx(o, n, NULL, NULL, 1); + } else { + /* This is the first time for both structs, so the prefix field + * contains the whole sub-list. */ + Cline or, nr; + + o->flags |= CLF_JOIN; + + /* We let us give both rests and use them as the suffixes. */ + join_psfx(o, n, &or, &nr, 0); + + if (or) + or->llen = (o->slen > or->wlen ? or->wlen : o->slen); + o->suffix = revert_cline(or); + n->suffix = revert_cline(nr); + + join_psfx(o, n, NULL, NULL, 1); + } + n->suffix = NULL; +} + +/* This turns the sequence of anchor cline structs from b to e into a + * prefix sequence, puts it before the prefix of e and then tries to + * join that with the prefix of a. + * This is needed if some matches had a anchor match spec and others + * didn't. */ + +/**/ +static void +sub_join(Cline a, Cline b, Cline e, int anew) +{ + if (!e->suffix && a->prefix) { + Cline op = e->prefix, n = NULL, *p = &n, t, ca; + int min = 0, max = 0; + + for (; b != e; b = b->next) { + if ((*p = t = b->prefix)) { + while (t->next) + t = t->next; + p = &(t->next); + } + b->suffix = b->prefix = NULL; + b->flags &= ~CLF_SUF; + min += b->min; + max += b->max; + *p = b; + p = &(b->next); + } + *p = e->prefix; + ca = a->prefix; + + while (n != op) { + e->prefix = cp_cline(n, 0); + a->prefix = cp_cline(ca, 0); + + if (anew) { + join_psfx(e, a, NULL, NULL, 0); + if (e->prefix) { + e->min += min; + e->max += max; + break; + } + } else { + join_psfx(e, a, NULL, NULL, 0); + if (a->prefix) { + a->min += min; + a->max += max; + break; + } + } + min -= n->min; + max -= n->max; + + n = n->next; + } + } +} + +/* This simplifies the cline list given as the first argument so that + * it also matches the second list. */ + +/**/ +Cline +join_clines(Cline o, Cline n) +{ + cline_setlens(n, 1); + + /* First time called, just return the new list. On further invocations + * we will get it as the first argument. */ + if (!o) + return n; + else { + Cline oo = o, nn = n, po = NULL, pn = NULL; + + /* Walk through the lists. */ + while (o && n) { + /* If one of them describes a new part and the other one does + * not, synchronise them by searching an old part in the + * other list. */ + if ((o->flags & CLF_NEW) && !(n->flags & CLF_NEW)) { + Cline t, tn; + + for (t = o; (tn = t->next) && (tn->flags & CLF_NEW); t = tn); + if (tn && cmp_anchors(tn, n, 0)) { + sub_join(n, o, tn, 1); + + if (po) + po->next = tn; + else + oo = tn; + t->next = NULL; + free_cline(o); + o = tn; + o->flags |= CLF_MISS; + continue; + } + } + if (!(o->flags & CLF_NEW) && (n->flags & CLF_NEW)) { + Cline t, tn; + + for (t = n; (tn = t->next) && (tn->flags & CLF_NEW); t = tn); + if (tn && cmp_anchors(o, tn, 0)) { + sub_join(o, n, tn, 0); + + n = tn; + o->flags |= CLF_MISS; + continue; + } + } + /* Almost the same as above, but for the case that they + * describe different types of parts (prefix, suffix, or mid). */ + if ((o->flags & (CLF_SUF | CLF_MID)) != + (n->flags & (CLF_SUF | CLF_MID))) { + Cline t, tn; + + for (t = n; + (tn = t->next) && + (tn->flags & (CLF_SUF | CLF_MID)) != + (o->flags & (CLF_SUF | CLF_MID)); + t = tn); + if (tn && cmp_anchors(o, tn, 1)) { + sub_join(o, n, tn, 0); + + n = tn; + continue; + } + for (t = o; + (tn = t->next) && + (tn->flags & (CLF_SUF | CLF_MID)) != + (n->flags & (CLF_SUF | CLF_MID)); + t = tn); + if (tn && cmp_anchors(tn, n, 1)) { + sub_join(n, o, tn, 1); + if (po) + po->next = tn; + else + oo = tn; + t->next = NULL; + free_cline(o); + o = tn; + continue; + } + if (o->flags & CLF_MID) { + o->flags = (o->flags & ~CLF_MID) | (n->flags & CLF_SUF); + if (n->flags & CLF_SUF) { + free_cline(o->prefix); + o->prefix = NULL; + } else { + free_cline(o->suffix); + o->suffix = NULL; + } + } + break; + } + /* Now see if they have matching anchors. If not, cut the list. */ + if (!(o->flags & CLF_MID) && !cmp_anchors(o, n, 1)) { + Cline t, tn; + + for (t = n; (tn = t->next) && !cmp_anchors(o, tn, 1); t = tn); + + if (tn) { + sub_join(o, n, tn, 0); + + n = tn; + o->flags |= CLF_MISS; + continue; + } else { + for (t = o; (tn = t->next) && !cmp_anchors(n, tn, 1); + t = tn); + + if (tn) { + sub_join(n, o, tn, 1); + + if (po) + po->next = tn; + else + oo = tn; + o = tn; + o->flags |= CLF_MISS; + continue; + } else { + if (o->flags & CLF_SUF) + break; + + o->word = o->line = o->orig = NULL; + o->wlen = 0; + free_cline(o->next); + o->next = NULL; + o->flags |= CLF_MISS; + } + } + } + /* Ok, they are equal, now copy the information about the + * original string if needed, calculate minimum and maximum + * lengths, and join the sub-lists. */ + if (!o->orig && !o->olen) { + o->orig = n->orig; + o->olen = n->olen; + } + if (n->min < o->min) + o->min = n->min; + if (n->max > o->max) + o->max = n->max; + if (o->flags & CLF_MID) + join_mid(o, n); + else + join_psfx(o, n, NULL, NULL, (o->flags & CLF_SUF)); + + po = o; + o = o->next; + pn = n; + n = n->next; + } + /* Free the rest of the old list. */ + if (o) { + if (po) + po->next = NULL; + else + oo = NULL; + + free_cline(o); + } + free_cline(nn); + + return oo; + } +} + |