/src/postgres/src/backend/regex/regprefix.c

Source
/*-------------------------------------------------------------------------
 *
 * regprefix.c
 *    Extract a common prefix, if any, from a compiled regex.
 *
 *
 * Portions Copyright (c) 2012-2026, PostgreSQL Global Development Group
 * Portions Copyright (c) 1998, 1999 Henry Spencer
 *
 * IDENTIFICATION
 *    src/backend/regex/regprefix.c
 *
 *-------------------------------------------------------------------------
 */

#include "regex/regguts.h"


/*
 * forward declarations
 */
static int  findprefix(struct cnfa *cnfa, struct colormap *cm,
             chr *string, size_t *slength);


/*
 * pg_regprefix - get common prefix for regular expression
 *
 * Returns one of:
 *  REG_NOMATCH: there is no common prefix of strings matching the regex
 *  REG_PREFIX: there is a common prefix of strings matching the regex
 *  REG_EXACT: all strings satisfying the regex must match the same string
 *  or a REG_XXX error code
 *
 * In the non-failure cases, *string is set to a palloc'd string containing
 * the common prefix or exact value, of length *slength (measured in chrs
 * not bytes!).
 *
 * This function does not analyze all complex cases (such as lookaround
 * constraints) exactly.  Therefore it is possible that some strings matching
 * the reported prefix or exact-match string do not satisfy the regex.  But
 * it should never be the case that a string satisfying the regex does not
 * match the reported prefix or exact-match string.
 */
int
pg_regprefix(regex_t *re,
       chr **string,
       size_t *slength)
{
  struct guts *g;
  struct cnfa *cnfa;
  int     st;

  /* sanity checks */
  if (string == NULL || slength == NULL)
    return REG_INVARG;
  *string = NULL;       /* initialize for failure cases */
  *slength = 0;
  if (re == NULL || re->re_magic != REMAGIC)
    return REG_INVARG;
  if (re->re_csize != sizeof(chr))
    return REG_MIXED;

  /* Initialize locale-dependent support */
  pg_set_regex_collation(re->re_collation);

  /* setup */
  g = (struct guts *) re->re_guts;
  if (g->info & REG_UIMPOSSIBLE)
    return REG_NOMATCH;

  /*
   * This implementation considers only the search NFA for the topmost regex
   * tree node.  Therefore, constraints such as backrefs are not fully
   * applied, which is allowed per the function's API spec.
   */
  assert(g->tree != NULL);
  cnfa = &g->tree->cnfa;

  /* matchall NFAs never have a fixed prefix */
  if (cnfa->flags & MATCHALL)
    return REG_NOMATCH;

  /*
   * Since a correct NFA should never contain any exit-free loops, it should
   * not be possible for our traversal to return to a previously visited NFA
   * state.  Hence we need at most nstates chrs in the output string.
   */
  *string = (chr *) MALLOC(cnfa->nstates * sizeof(chr));
  if (*string == NULL)
    return REG_ESPACE;

  /* do it */
  st = findprefix(cnfa, &g->cmap, *string, slength);

  assert(*slength <= cnfa->nstates);

  /* clean up */
  if (st != REG_PREFIX && st != REG_EXACT)
  {
    FREE(*string);
    *string = NULL;
    *slength = 0;
  }

  return st;
}

/*
 * findprefix - extract common prefix from cNFA
 *
 * Results are returned into the preallocated chr array string[], with
 * *slength (which must be preset to zero) incremented for each chr.
 */
static int            /* regprefix return code */
findprefix(struct cnfa *cnfa,
       struct colormap *cm,
       chr *string,
       size_t *slength)
{
  int     st;
  int     nextst;
  color   thiscolor;
  chr     c;
  struct carc *ca;

  /*
   * The "pre" state must have only BOS/BOL outarcs, else pattern isn't
   * anchored left.  If we have both BOS and BOL, they must go to the same
   * next state.
   */
  st = cnfa->pre;
  nextst = -1;
  for (ca = cnfa->states[st]; ca->co != COLORLESS; ca++)
  {
    if (ca->co == cnfa->bos[0] || ca->co == cnfa->bos[1])
    {
      if (nextst == -1)
        nextst = ca->to;
      else if (nextst != ca->to)
        return REG_NOMATCH;
    }
    else
      return REG_NOMATCH;
  }
  if (nextst == -1)
    return REG_NOMATCH;

  /*
   * Scan through successive states, stopping as soon as we find one with
   * more than one acceptable transition character (either multiple colors
   * on out-arcs, or a color with more than one member chr).
   *
   * We could find a state with multiple out-arcs that are all labeled with
   * the same singleton color; this comes from patterns like "^ab(cde|cxy)".
   * In that case we add the chr "c" to the output string but then exit the
   * loop with nextst == -1.  This leaves a little bit on the table: if the
   * pattern is like "^ab(cde|cdy)", we won't notice that "d" could be added
   * to the prefix.  But chasing multiple parallel state chains doesn't seem
   * worth the trouble.
   */
  do
  {
    st = nextst;
    nextst = -1;
    thiscolor = COLORLESS;
    for (ca = cnfa->states[st]; ca->co != COLORLESS; ca++)
    {
      /* We can ignore BOS/BOL arcs */
      if (ca->co == cnfa->bos[0] || ca->co == cnfa->bos[1])
        continue;

      /*
       * ... but EOS/EOL arcs terminate the search, as do RAINBOW arcs
       * and LACONs
       */
      if (ca->co == cnfa->eos[0] || ca->co == cnfa->eos[1] ||
        ca->co == RAINBOW || ca->co >= cnfa->ncolors)
      {
        thiscolor = COLORLESS;
        break;
      }
      if (thiscolor == COLORLESS)
      {
        /* First plain outarc */
        thiscolor = ca->co;
        nextst = ca->to;
      }
      else if (thiscolor == ca->co)
      {
        /* Another plain outarc for same color */
        nextst = -1;
      }
      else
      {
        /* More than one plain outarc color terminates the search */
        thiscolor = COLORLESS;
        break;
      }
    }
    /* Done if we didn't find exactly one color on plain outarcs */
    if (thiscolor == COLORLESS)
      break;
    /* The color must be a singleton */
    if (cm->cd[thiscolor].nschrs != 1)
      break;
    /* Must not have any high-color-map entries */
    if (cm->cd[thiscolor].nuchrs != 0)
      break;

    /*
     * Identify the color's sole member chr and add it to the prefix
     * string.  In general the colormap data structure doesn't provide a
     * way to find color member chrs, except by trying GETCOLOR() on each
     * possible chr value, which won't do at all.  However, for the cases
     * we care about it should be sufficient to test the "firstchr" value,
     * that is the first chr ever added to the color.  There are cases
     * where this might no longer be a member of the color (so we do need
     * to test), but none of them are likely to arise for a character that
     * is a member of a common prefix.  If we do hit such a corner case,
     * we just fall out without adding anything to the prefix string.
     */
    c = cm->cd[thiscolor].firstchr;
    if (GETCOLOR(cm, c) != thiscolor)
      break;

    string[(*slength)++] = c;

    /* Advance to next state, but only if we have a unique next state */
  } while (nextst != -1);

  /*
   * If we ended at a state that only has EOS/EOL outarcs leading to the
   * "post" state, then we have an exact-match string.  Note this is true
   * even if the string is of zero length.
   */
  nextst = -1;
  for (ca = cnfa->states[st]; ca->co != COLORLESS; ca++)
  {
    if (ca->co == cnfa->eos[0] || ca->co == cnfa->eos[1])
    {
      if (nextst == -1)
        nextst = ca->to;
      else if (nextst != ca->to)
      {
        nextst = -1;
        break;
      }
    }
    else
    {
      nextst = -1;
      break;
    }
  }
  if (nextst == cnfa->post)
    return REG_EXACT;

  /*
   * Otherwise, if we were unable to identify any prefix characters, say
   * NOMATCH --- the pattern is anchored left, but doesn't specify any
   * particular first character.
   */
  if (*slength > 0)
    return REG_PREFIX;

  return REG_NOMATCH;
}

Coverage Report

Created: 2026-10-16 06:48

Line	Count	Source
1		/*-------------------------------------------------------------------------
2		*
3		* regprefix.c
4		* Extract a common prefix, if any, from a compiled regex.
5		*
6		*
7		* Portions Copyright (c) 2012-2026, PostgreSQL Global Development Group
8		* Portions Copyright (c) 1998, 1999 Henry Spencer
9		*
10		* IDENTIFICATION
11		* src/backend/regex/regprefix.c
12		*
13		*-------------------------------------------------------------------------
14		*/
15
16		#include "regex/regguts.h"
17
18
19		/*
20		* forward declarations
21		*/
22		static int findprefix(struct cnfa cnfa, struct colormap cm,
23		chr string, size_t slength);
24
25
26		/*
27		* pg_regprefix - get common prefix for regular expression
28		*
29		* Returns one of:
30		* REG_NOMATCH: there is no common prefix of strings matching the regex
31		* REG_PREFIX: there is a common prefix of strings matching the regex
32		* REG_EXACT: all strings satisfying the regex must match the same string
33		* or a REG_XXX error code
34		*
35		* In the non-failure cases, *string is set to a palloc'd string containing
36		* the common prefix or exact value, of length *slength (measured in chrs
37		* not bytes!).
38		*
39		* This function does not analyze all complex cases (such as lookaround
40		* constraints) exactly. Therefore it is possible that some strings matching
41		* the reported prefix or exact-match string do not satisfy the regex. But
42		* it should never be the case that a string satisfying the regex does not
43		* match the reported prefix or exact-match string.
44		*/
45		int
46		pg_regprefix(regex_t *re,
47		chr **string,
48		size_t *slength)
49	0	{
50	0	struct guts *g;
51	0	struct cnfa *cnfa;
52	0	int st;
53
54		/* sanity checks */
55	0	if (string == NULL \|\| slength == NULL)
56	0	return REG_INVARG;
57	0	string = NULL; / initialize for failure cases */
58	0	*slength = 0;
59	0	if (re == NULL \|\| re->re_magic != REMAGIC)
60	0	return REG_INVARG;
61	0	if (re->re_csize != sizeof(chr))
62	0	return REG_MIXED;
63
64		/* Initialize locale-dependent support */
65	0	pg_set_regex_collation(re->re_collation);
66
67		/* setup */
68	0	g = (struct guts *) re->re_guts;
69	0	if (g->info & REG_UIMPOSSIBLE)
70	0	return REG_NOMATCH;
71
72		/*
73		* This implementation considers only the search NFA for the topmost regex
74		* tree node. Therefore, constraints such as backrefs are not fully
75		* applied, which is allowed per the function's API spec.
76		*/
77	0	assert(g->tree != NULL);
78	0	cnfa = &g->tree->cnfa;
79
80		/* matchall NFAs never have a fixed prefix */
81	0	if (cnfa->flags & MATCHALL)
82	0	return REG_NOMATCH;
83
84		/*
85		* Since a correct NFA should never contain any exit-free loops, it should
86		* not be possible for our traversal to return to a previously visited NFA
87		* state. Hence we need at most nstates chrs in the output string.
88		*/
89	0	string = (chr ) MALLOC(cnfa->nstates * sizeof(chr));
90	0	if (*string == NULL)
91	0	return REG_ESPACE;
92
93		/* do it */
94	0	st = findprefix(cnfa, &g->cmap, *string, slength);
95
96	0	assert(*slength <= cnfa->nstates);
97
98		/* clean up */
99	0	if (st != REG_PREFIX && st != REG_EXACT)
100	0	{
101	0	FREE(*string);
102	0	*string = NULL;
103	0	*slength = 0;
104	0	}
105
106	0	return st;
107	0	}
108
109		/*
110		* findprefix - extract common prefix from cNFA
111		*
112		* Results are returned into the preallocated chr array string[], with
113		* *slength (which must be preset to zero) incremented for each chr.
114		*/
115		static int /* regprefix return code */
116		findprefix(struct cnfa *cnfa,
117		struct colormap *cm,
118		chr *string,
119		size_t *slength)
120	0	{
121	0	int st;
122	0	int nextst;
123	0	color thiscolor;
124	0	chr c;
125	0	struct carc *ca;
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		*/
132	0	st = cnfa->pre;
133	0	nextst = -1;
134	0	for (ca = cnfa->states[st]; ca->co != COLORLESS; ca++)
135	0	{
136	0	if (ca->co == cnfa->bos[0] \|\| ca->co == cnfa->bos[1])
137	0	{
138	0	if (nextst == -1)
139	0	nextst = ca->to;
140	0	else if (nextst != ca->to)
141	0	return REG_NOMATCH;
142	0	}
143	0	else
144	0	return REG_NOMATCH;
145	0	}
146	0	if (nextst == -1)
147	0	return REG_NOMATCH;
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	0	do
163	0	{
164	0	st = nextst;
165	0	nextst = -1;
166	0	thiscolor = COLORLESS;
167	0	for (ca = cnfa->states[st]; ca->co != COLORLESS; ca++)
168	0	{
169		/* We can ignore BOS/BOL arcs */
170	0	if (ca->co == cnfa->bos[0] \|\| ca->co == cnfa->bos[1])
171	0	continue;
172
173		/*
174		* ... but EOS/EOL arcs terminate the search, as do RAINBOW arcs
175		* and LACONs
176		*/
177	0	if (ca->co == cnfa->eos[0] \|\| ca->co == cnfa->eos[1] \|\|
178	0	ca->co == RAINBOW \|\| ca->co >= cnfa->ncolors)
179	0	{
180	0	thiscolor = COLORLESS;
181	0	break;
182	0	}
183	0	if (thiscolor == COLORLESS)
184	0	{
185		/* First plain outarc */
186	0	thiscolor = ca->co;
187	0	nextst = ca->to;
188	0	}
189	0	else if (thiscolor == ca->co)
190	0	{
191		/* Another plain outarc for same color */
192	0	nextst = -1;
193	0	}
194	0	else
195	0	{
196		/* More than one plain outarc color terminates the search */
197	0	thiscolor = COLORLESS;
198	0	break;
199	0	}
200	0	}
201		/* Done if we didn't find exactly one color on plain outarcs */
202	0	if (thiscolor == COLORLESS)
203	0	break;
204		/* The color must be a singleton */
205	0	if (cm->cd[thiscolor].nschrs != 1)
206	0	break;
207		/* Must not have any high-color-map entries */
208	0	if (cm->cd[thiscolor].nuchrs != 0)
209	0	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		*/
223	0	c = cm->cd[thiscolor].firstchr;
224	0	if (GETCOLOR(cm, c) != thiscolor)
225	0	break;
226
227	0	string[(*slength)++] = c;
228
229		/* Advance to next state, but only if we have a unique next state */
230	0	} 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	0	nextst = -1;
238	0	for (ca = cnfa->states[st]; ca->co != COLORLESS; ca++)
239	0	{
240	0	if (ca->co == cnfa->eos[0] \|\| ca->co == cnfa->eos[1])
241	0	{
242	0	if (nextst == -1)
243	0	nextst = ca->to;
244	0	else if (nextst != ca->to)
245	0	{
246	0	nextst = -1;
247	0	break;
248	0	}
249	0	}
250	0	else
251	0	{
252	0	nextst = -1;
253	0	break;
254	0	}
255	0	}
256	0	if (nextst == cnfa->post)
257	0	return REG_EXACT;
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	0	if (*slength > 0)
265	0	return REG_PREFIX;
266
267	0	return REG_NOMATCH;
268	0	}