49 #define HASH(bv, nw) (((nw) == 1) ? *(bv) : hash(bv, nw))
50 #define HIT(h,bv,ss,nw) ((ss)->hash == (h) && ((nw) == 1 || \
51 memcmp(VS(bv), VS((ss)->states), (nw)*sizeof(unsigned)) == 0))
56 #define NOPROGRESS 010
101 #define DOMALLOC ((struct smalldfa *)NULL)
126 #define VISERR(vv) ((vv)->err != 0)
127 #define ISERR() VISERR(v)
128 #define VERR(vv,e) ((vv)->err = ((vv)->err ? (vv)->err : (e)))
129 #define ERR(e) VERR(v, e)
130 #define NOERR() {if (ISERR()) return v->err;}
131 #define OFF(p) ((p) - v->start)
132 #define LOFF(p) ((long)OFF(p))
145 struct dfa *d,
struct dfa *s,
chr **coldp);
159 chr *start,
chr *stop,
int *hitstopp);
161 chr *max,
chr **coldp,
int *hitstopp);
163 struct sset **lastcss,
chr **lastcp);
170 static unsigned hash(
unsigned *uv,
int n);
195 struct vars *v = &var;
212 if (search_start >
len)
227 if (backref && nmatch <= v->g->nsub)
247 if (nmatch > v->
g->
nsub + 1)
248 nmatch = v->
g->
nsub + 1;
275 for (
i = 0;
i < n;
i++)
288 for (
i = 0;
i < n;
i++)
297 for (
i = 0;
i < n;
i++)
317 assert(nmatch <= v->nmatch);
334 for (
i = 0;
i < n;
i++)
345 for (
i = 0;
i < n;
i++)
440 &cold, (
int *) NULL);
465 for (begin = open; begin <=
close; begin++)
467 MDEBUG((
"\nfind trying at %ld\n",
LOFF(begin)));
470 (
chr **) NULL, &hitend);
478 if (hitend && cold == NULL)
567 assert(d != NULL && s != NULL);
587 for (begin = open; begin <=
close; begin++)
589 MDEBUG((
"\ncfind trying at %ld\n",
LOFF(begin)));
597 estop, (
chr **) NULL, &hitend);
599 end =
longest(v, d, begin, estop,
606 if (hitend && cold == NULL)
651 }
while (close < v->stop);
668 for (
i = n - 1;
i > 0;
i--)
687 if ((
size_t) n < v->nmatch)
710 if ((
size_t) n >= v->
nmatch)
855 mid =
longest(v, d, begin, end, (
int *) NULL);
859 MDEBUG((
"%d: tentative midpoint %ld\n", t->
id,
LOFF(mid)));
865 if (
longest(v, d2, mid, end, (
int *) NULL) == end)
874 MDEBUG((
"%d: successful\n", t->
id));
889 MDEBUG((
"%d: no midpoint\n", t->
id));
892 mid =
longest(v, d, begin, mid - 1, (
int *) NULL);
897 MDEBUG((
"%d: failed midpoint\n", t->
id));
936 mid =
shortest(v, d, begin, begin, end, (
chr **) NULL, (
int *) NULL);
940 MDEBUG((
"%d: tentative midpoint %ld\n", t->
id,
LOFF(mid)));
946 if (
longest(v, d2, mid, end, (
int *) NULL) == end)
955 MDEBUG((
"%d: successful\n", t->
id));
970 MDEBUG((
"%d: no midpoint\n", t->
id));
973 mid =
shortest(v, d, begin, mid + 1, end, (
chr **) NULL, (
int *) NULL);
978 MDEBUG((
"%d: failed midpoint\n", t->
id));
1012 assert((
size_t) n < v->nmatch);
1014 MDEBUG((
"%d: cbrdissect %d{%d-%d} %ld-%ld\n", t->
id, n, min, max,
1030 if (begin == end && min <= max)
1032 MDEBUG((
"%d: backref matched trivially\n", t->
id));
1042 MDEBUG((
"%d: backref matched trivially\n", t->
id));
1054 if (tlen % brlen != 0)
1056 numreps = tlen / brlen;
1057 if (numreps < min || (numreps > max && max !=
DUPINF))
1062 while (numreps-- > 0)
1064 if ((*v->
g->compare) (brstring, p, brlen) != 0)
1069 MDEBUG((
"%d: backref matched\n", t->
id));
1099 if (
longest(v, d, begin, end, (
int *) NULL) == end)
1101 MDEBUG((
"%d: caltdissect matched\n", t->
id));
1149 min_matches = t->
min;
1150 if (min_matches <= 0)
1162 max_matches = end - begin;
1164 max_matches = t->
max;
1165 if (max_matches < min_matches)
1166 max_matches = min_matches;
1167 endpts = (
chr **)
MALLOC((max_matches + 1) *
sizeof(
chr *));
1198 endpts[k] =
longest(v, d, endpts[k - 1], limit, (
int *) NULL);
1204 if (endpts[k] == NULL)
1210 MDEBUG((
"%d: working endpoint %d: %ld\n",
1211 t->
id, k,
LOFF(endpts[k])));
1217 if (endpts[k] != end)
1220 if (k >= max_matches)
1228 if (endpts[k] == endpts[k - 1] &&
1229 (k >= min_matches || min_matches - k < end - endpts[k]))
1243 if (k < min_matches)
1246 MDEBUG((
"%d: verifying %d..%d\n", t->
id, nverified + 1, k));
1248 for (
i = nverified + 1;
i <= k;
i++)
1268 MDEBUG((
"%d: successful\n", t->
id));
1284 chr *prev_end = endpts[k - 1];
1286 if (endpts[k] > prev_end)
1288 limit = endpts[k] - 1;
1289 if (limit > prev_end ||
1290 (k < min_matches && min_matches - k >= end - prev_end))
1308 if (t->
min == 0 && begin == end)
1310 MDEBUG((
"%d: allowing zero matches\n", t->
id));
1349 min_matches = t->
min;
1350 if (min_matches <= 0)
1354 MDEBUG((
"%d: allowing zero matches\n", t->
id));
1369 max_matches = end - begin;
1371 max_matches = t->
max;
1372 if (max_matches < min_matches)
1373 max_matches = min_matches;
1374 endpts = (
chr **)
MALLOC((max_matches + 1) *
sizeof(
chr *));
1405 if (limit == endpts[k - 1] &&
1407 (k >= min_matches || min_matches - k < end - limit))
1411 if (k >= max_matches)
1415 endpts[k] =
shortest(v, d, endpts[k - 1], limit, end,
1416 (
chr **) NULL, (
int *) NULL);
1422 if (endpts[k] == NULL)
1428 MDEBUG((
"%d: working endpoint %d: %ld\n",
1429 t->
id, k,
LOFF(endpts[k])));
1435 if (endpts[k] != end)
1438 if (k >= max_matches)
1446 limit = endpts[k - 1];
1456 if (k < min_matches)
1459 MDEBUG((
"%d: verifying %d..%d\n", t->
id, nverified + 1, k));
1461 for (
i = nverified + 1;
i <= k;
i++)
1481 MDEBUG((
"%d: successful\n", t->
id));
1496 if (endpts[k] < end)
1498 limit = endpts[k] + 1;
static void cleanup(void)
if(TABLE==NULL||TABLE_index==NULL)
static void const char fflush(stdout)
void pg_set_regex_collation(Oid collation)
static int find(struct vars *v, struct cnfa *cnfa, struct colormap *cm)
static int citerdissect(struct vars *v, struct subre *t, chr *begin, chr *end)
static void freedfa(struct dfa *d)
static struct sset * initialize(struct vars *v, struct dfa *d, chr *start)
static struct sset * getvacant(struct vars *v, struct dfa *d, chr *cp, chr *start)
static void zapallsubs(regmatch_t *p, size_t n)
static int lacon(struct vars *v, struct cnfa *pcnfa, chr *cp, color co)
static int ccondissect(struct vars *v, struct subre *t, chr *begin, chr *end)
static int cfind(struct vars *v, struct cnfa *cnfa, struct colormap *cm)
static int creviterdissect(struct vars *v, struct subre *t, chr *begin, chr *end)
static int cfindloop(struct vars *v, struct cnfa *cnfa, struct colormap *cm, struct dfa *d, struct dfa *s, chr **coldp)
static chr * longest(struct vars *v, struct dfa *d, chr *start, chr *stop, int *hitstopp)
static unsigned hash(unsigned *uv, int n)
static int cbrdissect(struct vars *v, struct subre *t, chr *begin, chr *end)
static struct dfa * getladfa(struct vars *v, int n)
static struct dfa * getsubdfa(struct vars *v, struct subre *t)
static int crevcondissect(struct vars *v, struct subre *t, chr *begin, chr *end)
static struct sset * pickss(struct vars *v, struct dfa *d, chr *cp, chr *start)
static struct dfa * newdfa(struct vars *v, struct cnfa *cnfa, struct colormap *cm, struct smalldfa *sml)
static int cdissect(struct vars *v, struct subre *t, chr *begin, chr *end)
static chr * lastcold(struct vars *v, struct dfa *d)
static void zaptreesubs(struct vars *v, struct subre *t)
static int caltdissect(struct vars *v, struct subre *t, chr *begin, chr *end)
static chr * dfa_backref(struct vars *v, struct dfa *d, chr *start, chr *min, chr *max, bool shortest)
static void subset(struct vars *v, struct subre *sub, chr *begin, chr *end)
static chr * shortest(struct vars *v, struct dfa *d, chr *start, chr *min, chr *max, chr **coldp, int *hitstopp)
int pg_regexec(regex_t *re, const chr *string, size_t len, size_t search_start, rm_detail_t *details, size_t nmatch, regmatch_t pmatch[], int flags)
static int matchuntil(struct vars *v, struct dfa *d, chr *probe, struct sset **lastcss, chr **lastcp)
static struct sset * miss(struct vars *v, struct dfa *d, struct sset *css, color co, chr *cp, chr *start)
#define STACK_TOO_DEEP(re)
#define CANCEL_REQUESTED(re)
unsigned statesarea[FEWSTATES *2+WORK]
struct arcp incarea[FEWSTATES *2 *FEWCOLORS]
struct sset * outsarea[FEWSTATES *2 *FEWCOLORS]
struct sset ssets[FEWSTATES *2]