/src/postgres/src/backend/regex/regexport.c

Source
/*-------------------------------------------------------------------------
 *
 * regexport.c
 *    Functions for exporting info about a regex's NFA
 *
 * In this implementation, the NFA defines a necessary but not sufficient
 * condition for a string to match the regex: that is, there can be strings
 * that match the NFA but don't match the full regex, but not vice versa.
 * Thus, for example, it is okay for the functions below to treat lookaround
 * constraints as no-ops, since they merely constrain the string some more.
 *
 * Notice that these functions return info into caller-provided arrays
 * rather than doing their own malloc's.  This simplifies the APIs by
 * eliminating a class of error conditions, and in the case of colors
 * allows the caller to decide how big is too big to bother with.
 *
 *
 * Portions Copyright (c) 2013-2026, PostgreSQL Global Development Group
 * Portions Copyright (c) 1998, 1999 Henry Spencer
 *
 * IDENTIFICATION
 *    src/backend/regex/regexport.c
 *
 *-------------------------------------------------------------------------
 */

#include "regex/regguts.h"

#include "regex/regexport.h"


/*
 * Get total number of NFA states.
 */
int
pg_reg_getnumstates(const regex_t *regex)
{
  struct cnfa *cnfa;

  assert(regex != NULL && regex->re_magic == REMAGIC);
  cnfa = &((struct guts *) regex->re_guts)->search;

  return cnfa->nstates;
}

/*
 * Get initial state of NFA.
 */
int
pg_reg_getinitialstate(const regex_t *regex)
{
  struct cnfa *cnfa;

  assert(regex != NULL && regex->re_magic == REMAGIC);
  cnfa = &((struct guts *) regex->re_guts)->search;

  return cnfa->pre;
}

/*
 * Get final state of NFA.
 */
int
pg_reg_getfinalstate(const regex_t *regex)
{
  struct cnfa *cnfa;

  assert(regex != NULL && regex->re_magic == REMAGIC);
  cnfa = &((struct guts *) regex->re_guts)->search;

  return cnfa->post;
}

/*
 * pg_reg_getnumoutarcs() and pg_reg_getoutarcs() mask the existence of LACON
 * arcs from the caller, treating any LACON as being automatically satisfied.
 * Since the output representation does not support arcs that consume no
 * character when traversed, we have to recursively traverse LACON arcs here,
 * and report whatever normal arcs are reachable by traversing LACON arcs.
 * Note that this wouldn't work if it were possible to reach the final state
 * via LACON traversal, but the regex library never builds NFAs that have
 * LACON arcs leading directly to the final state.  (This is because the
 * regex executor is designed to consume one character beyond the nominal
 * match end --- possibly an EOS indicator --- so there is always a set of
 * ordinary arcs leading to the final state.)
 *
 * traverse_lacons is a recursive subroutine used by both exported functions
 * to count and then emit the reachable regular arcs.  *arcs_count is
 * incremented by the number of reachable arcs, and as many as will fit in
 * arcs_len (possibly 0) are emitted into arcs[].
 */
static void
traverse_lacons(struct cnfa *cnfa, int st,
        int *arcs_count,
        regex_arc_t *arcs, int arcs_len)
{
  struct carc *ca;

  /*
   * Since this function recurses, it could theoretically be driven to stack
   * overflow.  In practice, this is mostly useful to backstop against a
   * failure of the regex compiler to remove a loop of LACON arcs.
   */
  check_stack_depth();

  for (ca = cnfa->states[st]; ca->co != COLORLESS; ca++)
  {
    if (ca->co < cnfa->ncolors)
    {
      /* Ordinary arc, so count and possibly emit it */
      int     ndx = (*arcs_count)++;

      if (ndx < arcs_len)
      {
        arcs[ndx].co = ca->co;
        arcs[ndx].to = ca->to;
      }
    }
    else
    {
      /* LACON arc --- assume it's satisfied and recurse... */
      /* ... but first, assert it doesn't lead directly to post state */
      Assert(ca->to != cnfa->post);

      traverse_lacons(cnfa, ca->to, arcs_count, arcs, arcs_len);
    }
  }
}

/*
 * Get number of outgoing NFA arcs of state number "st".
 */
int
pg_reg_getnumoutarcs(const regex_t *regex, int st)
{
  struct cnfa *cnfa;
  int     arcs_count;

  assert(regex != NULL && regex->re_magic == REMAGIC);
  cnfa = &((struct guts *) regex->re_guts)->search;

  if (st < 0 || st >= cnfa->nstates)
    return 0;
  arcs_count = 0;
  traverse_lacons(cnfa, st, &arcs_count, NULL, 0);
  return arcs_count;
}

/*
 * Write array of outgoing NFA arcs of state number "st" into arcs[],
 * whose length arcs_len must be at least as long as indicated by
 * pg_reg_getnumoutarcs(), else not all arcs will be returned.
 */
void
pg_reg_getoutarcs(const regex_t *regex, int st,
          regex_arc_t *arcs, int arcs_len)
{
  struct cnfa *cnfa;
  int     arcs_count;

  assert(regex != NULL && regex->re_magic == REMAGIC);
  cnfa = &((struct guts *) regex->re_guts)->search;

  if (st < 0 || st >= cnfa->nstates || arcs_len <= 0)
    return;
  arcs_count = 0;
  traverse_lacons(cnfa, st, &arcs_count, arcs, arcs_len);
}

/*
 * Get total number of colors.
 */
int
pg_reg_getnumcolors(const regex_t *regex)
{
  struct colormap *cm;

  assert(regex != NULL && regex->re_magic == REMAGIC);
  cm = &((struct guts *) regex->re_guts)->cmap;

  return cm->max + 1;
}

/*
 * Check if color is beginning of line/string.
 *
 * (We might at some point need to offer more refined handling of pseudocolors,
 * but this will do for now.)
 */
int
pg_reg_colorisbegin(const regex_t *regex, int co)
{
  struct cnfa *cnfa;

  assert(regex != NULL && regex->re_magic == REMAGIC);
  cnfa = &((struct guts *) regex->re_guts)->search;

  if (co == cnfa->bos[0] || co == cnfa->bos[1])
    return true;
  else
    return false;
}

/*
 * Check if color is end of line/string.
 */
int
pg_reg_colorisend(const regex_t *regex, int co)
{
  struct cnfa *cnfa;

  assert(regex != NULL && regex->re_magic == REMAGIC);
  cnfa = &((struct guts *) regex->re_guts)->search;

  if (co == cnfa->eos[0] || co == cnfa->eos[1])
    return true;
  else
    return false;
}

/*
 * Get number of member chrs of color number "co".
 *
 * Note: we return -1 if the color number is invalid, or if it is a special
 * color (WHITE, RAINBOW, or a pseudocolor), or if the number of members is
 * uncertain.
 * Callers should not try to extract the members if -1 is returned.
 */
int
pg_reg_getnumcharacters(const regex_t *regex, int co)
{
  struct colormap *cm;

  assert(regex != NULL && regex->re_magic == REMAGIC);
  cm = &((struct guts *) regex->re_guts)->cmap;

  if (co <= 0 || co > cm->max) /* <= 0 rejects WHITE and RAINBOW */
    return -1;
  if (cm->cd[co].flags & PSEUDO) /* also pseudocolors (BOS etc) */
    return -1;

  /*
   * If the color appears anywhere in the high colormap, treat its number of
   * members as uncertain.  In principle we could determine all the specific
   * chrs corresponding to each such entry, but it would be expensive
   * (particularly if character class tests are required) and it doesn't
   * seem worth it.
   */
  if (cm->cd[co].nuchrs != 0)
    return -1;

  /* OK, return the known number of member chrs */
  return cm->cd[co].nschrs;
}

/*
 * Write array of member chrs of color number "co" into chars[],
 * whose length chars_len must be at least as long as indicated by
 * pg_reg_getnumcharacters(), else not all chars will be returned.
 *
 * Fetching the members of WHITE, RAINBOW, or a pseudocolor is not supported.
 *
 * Caution: this is a relatively expensive operation.
 */
void
pg_reg_getcharacters(const regex_t *regex, int co,
           pg_wchar *chars, int chars_len)
{
  struct colormap *cm;
  chr     c;

  assert(regex != NULL && regex->re_magic == REMAGIC);
  cm = &((struct guts *) regex->re_guts)->cmap;

  if (co <= 0 || co > cm->max || chars_len <= 0)
    return;
  if (cm->cd[co].flags & PSEUDO)
    return;

  /*
   * We need only examine the low character map; there should not be any
   * matching entries in the high map.
   */
  for (c = CHR_MIN; c <= MAX_SIMPLE_CHR; c++)
  {
    if (cm->locolormap[c - CHR_MIN] == co)
    {
      *chars++ = c;
      if (--chars_len == 0)
        break;
    }
  }
}

Coverage Report

Created: 2026-11-09 07:20

Line	Count	Source
1		/*-------------------------------------------------------------------------
2		*
3		* regexport.c
4		* Functions for exporting info about a regex's NFA
5		*
6		* In this implementation, the NFA defines a necessary but not sufficient
7		* condition for a string to match the regex: that is, there can be strings
8		* that match the NFA but don't match the full regex, but not vice versa.
9		* Thus, for example, it is okay for the functions below to treat lookaround
10		* constraints as no-ops, since they merely constrain the string some more.
11		*
12		* Notice that these functions return info into caller-provided arrays
13		* rather than doing their own malloc's. This simplifies the APIs by
14		* eliminating a class of error conditions, and in the case of colors
15		* allows the caller to decide how big is too big to bother with.
16		*
17		*
18		* Portions Copyright (c) 2013-2026, PostgreSQL Global Development Group
19		* Portions Copyright (c) 1998, 1999 Henry Spencer
20		*
21		* IDENTIFICATION
22		* src/backend/regex/regexport.c
23		*
24		*-------------------------------------------------------------------------
25		*/
26
27		#include "regex/regguts.h"
28
29		#include "regex/regexport.h"
30
31
32		/*
33		* Get total number of NFA states.
34		*/
35		int
36		pg_reg_getnumstates(const regex_t *regex)
37	0	{
38	0	struct cnfa *cnfa;
39
40	0	assert(regex != NULL && regex->re_magic == REMAGIC);
41	0	cnfa = &((struct guts *) regex->re_guts)->search;
42
43	0	return cnfa->nstates;
44	0	}
45
46		/*
47		* Get initial state of NFA.
48		*/
49		int
50		pg_reg_getinitialstate(const regex_t *regex)
51	0	{
52	0	struct cnfa *cnfa;
53
54	0	assert(regex != NULL && regex->re_magic == REMAGIC);
55	0	cnfa = &((struct guts *) regex->re_guts)->search;
56
57	0	return cnfa->pre;
58	0	}
59
60		/*
61		* Get final state of NFA.
62		*/
63		int
64		pg_reg_getfinalstate(const regex_t *regex)
65	0	{
66	0	struct cnfa *cnfa;
67
68	0	assert(regex != NULL && regex->re_magic == REMAGIC);
69	0	cnfa = &((struct guts *) regex->re_guts)->search;
70
71	0	return cnfa->post;
72	0	}
73
74		/*
75		* pg_reg_getnumoutarcs() and pg_reg_getoutarcs() mask the existence of LACON
76		* arcs from the caller, treating any LACON as being automatically satisfied.
77		* Since the output representation does not support arcs that consume no
78		* character when traversed, we have to recursively traverse LACON arcs here,
79		* and report whatever normal arcs are reachable by traversing LACON arcs.
80		* Note that this wouldn't work if it were possible to reach the final state
81		* via LACON traversal, but the regex library never builds NFAs that have
82		* LACON arcs leading directly to the final state. (This is because the
83		* regex executor is designed to consume one character beyond the nominal
84		* match end --- possibly an EOS indicator --- so there is always a set of
85		* ordinary arcs leading to the final state.)
86		*
87		* traverse_lacons is a recursive subroutine used by both exported functions
88		* to count and then emit the reachable regular arcs. *arcs_count is
89		* incremented by the number of reachable arcs, and as many as will fit in
90		* arcs_len (possibly 0) are emitted into arcs[].
91		*/
92		static void
93		traverse_lacons(struct cnfa *cnfa, int st,
94		int *arcs_count,
95		regex_arc_t *arcs, int arcs_len)
96	0	{
97	0	struct carc *ca;
98
99		/*
100		* Since this function recurses, it could theoretically be driven to stack
101		* overflow. In practice, this is mostly useful to backstop against a
102		* failure of the regex compiler to remove a loop of LACON arcs.
103		*/
104	0	check_stack_depth();
105
106	0	for (ca = cnfa->states[st]; ca->co != COLORLESS; ca++)
107	0	{
108	0	if (ca->co < cnfa->ncolors)
109	0	{
110		/* Ordinary arc, so count and possibly emit it */
111	0	int ndx = (*arcs_count)++;
112
113	0	if (ndx < arcs_len)
114	0	{
115	0	arcs[ndx].co = ca->co;
116	0	arcs[ndx].to = ca->to;
117	0	}
118	0	}
119	0	else
120	0	{
121		/* LACON arc --- assume it's satisfied and recurse... */
122		/* ... but first, assert it doesn't lead directly to post state */
123	0	Assert(ca->to != cnfa->post);
124
125	0	traverse_lacons(cnfa, ca->to, arcs_count, arcs, arcs_len);
126	0	}
127	0	}
128	0	}
129
130		/*
131		* Get number of outgoing NFA arcs of state number "st".
132		*/
133		int
134		pg_reg_getnumoutarcs(const regex_t *regex, int st)
135	0	{
136	0	struct cnfa *cnfa;
137	0	int arcs_count;
138
139	0	assert(regex != NULL && regex->re_magic == REMAGIC);
140	0	cnfa = &((struct guts *) regex->re_guts)->search;
141
142	0	if (st < 0 \|\| st >= cnfa->nstates)
143	0	return 0;
144	0	arcs_count = 0;
145	0	traverse_lacons(cnfa, st, &arcs_count, NULL, 0);
146	0	return arcs_count;
147	0	}
148
149		/*
150		* Write array of outgoing NFA arcs of state number "st" into arcs[],
151		* whose length arcs_len must be at least as long as indicated by
152		* pg_reg_getnumoutarcs(), else not all arcs will be returned.
153		*/
154		void
155		pg_reg_getoutarcs(const regex_t *regex, int st,
156		regex_arc_t *arcs, int arcs_len)
157	0	{
158	0	struct cnfa *cnfa;
159	0	int arcs_count;
160
161	0	assert(regex != NULL && regex->re_magic == REMAGIC);
162	0	cnfa = &((struct guts *) regex->re_guts)->search;
163
164	0	if (st < 0 \|\| st >= cnfa->nstates \|\| arcs_len <= 0)
165	0	return;
166	0	arcs_count = 0;
167	0	traverse_lacons(cnfa, st, &arcs_count, arcs, arcs_len);
168	0	}
169
170		/*
171		* Get total number of colors.
172		*/
173		int
174		pg_reg_getnumcolors(const regex_t *regex)
175	0	{
176	0	struct colormap *cm;
177
178	0	assert(regex != NULL && regex->re_magic == REMAGIC);
179	0	cm = &((struct guts *) regex->re_guts)->cmap;
180
181	0	return cm->max + 1;
182	0	}
183
184		/*
185		* Check if color is beginning of line/string.
186		*
187		* (We might at some point need to offer more refined handling of pseudocolors,
188		* but this will do for now.)
189		*/
190		int
191		pg_reg_colorisbegin(const regex_t *regex, int co)
192	0	{
193	0	struct cnfa *cnfa;
194
195	0	assert(regex != NULL && regex->re_magic == REMAGIC);
196	0	cnfa = &((struct guts *) regex->re_guts)->search;
197
198	0	if (co == cnfa->bos[0] \|\| co == cnfa->bos[1])
199	0	return true;
200	0	else
201	0	return false;
202	0	}
203
204		/*
205		* Check if color is end of line/string.
206		*/
207		int
208		pg_reg_colorisend(const regex_t *regex, int co)
209	0	{
210	0	struct cnfa *cnfa;
211
212	0	assert(regex != NULL && regex->re_magic == REMAGIC);
213	0	cnfa = &((struct guts *) regex->re_guts)->search;
214
215	0	if (co == cnfa->eos[0] \|\| co == cnfa->eos[1])
216	0	return true;
217	0	else
218	0	return false;
219	0	}
220
221		/*
222		* Get number of member chrs of color number "co".
223		*
224		* Note: we return -1 if the color number is invalid, or if it is a special
225		* color (WHITE, RAINBOW, or a pseudocolor), or if the number of members is
226		* uncertain.
227		* Callers should not try to extract the members if -1 is returned.
228		*/
229		int
230		pg_reg_getnumcharacters(const regex_t *regex, int co)
231	0	{
232	0	struct colormap *cm;
233
234	0	assert(regex != NULL && regex->re_magic == REMAGIC);
235	0	cm = &((struct guts *) regex->re_guts)->cmap;
236
237	0	if (co <= 0 \|\| co > cm->max) /* <= 0 rejects WHITE and RAINBOW */
238	0	return -1;
239	0	if (cm->cd[co].flags & PSEUDO) /* also pseudocolors (BOS etc) */
240	0	return -1;
241
242		/*
243		* If the color appears anywhere in the high colormap, treat its number of
244		* members as uncertain. In principle we could determine all the specific
245		* chrs corresponding to each such entry, but it would be expensive
246		* (particularly if character class tests are required) and it doesn't
247		* seem worth it.
248		*/
249	0	if (cm->cd[co].nuchrs != 0)
250	0	return -1;
251
252		/* OK, return the known number of member chrs */
253	0	return cm->cd[co].nschrs;
254	0	}
255
256		/*
257		* Write array of member chrs of color number "co" into chars[],
258		* whose length chars_len must be at least as long as indicated by
259		* pg_reg_getnumcharacters(), else not all chars will be returned.
260		*
261		* Fetching the members of WHITE, RAINBOW, or a pseudocolor is not supported.
262		*
263		* Caution: this is a relatively expensive operation.
264		*/
265		void
266		pg_reg_getcharacters(const regex_t *regex, int co,
267		pg_wchar *chars, int chars_len)
268	0	{
269	0	struct colormap *cm;
270	0	chr c;
271
272	0	assert(regex != NULL && regex->re_magic == REMAGIC);
273	0	cm = &((struct guts *) regex->re_guts)->cmap;
274
275	0	if (co <= 0 \|\| co > cm->max \|\| chars_len <= 0)
276	0	return;
277	0	if (cm->cd[co].flags & PSEUDO)
278	0	return;
279
280		/*
281		* We need only examine the low character map; there should not be any
282		* matching entries in the high map.
283		*/
284	0	for (c = CHR_MIN; c <= MAX_SIMPLE_CHR; c++)
285	0	{
286	0	if (cm->locolormap[c - CHR_MIN] == co)
287	0	{
288	0	*chars++ = c;
289	0	if (--chars_len == 0)
290	0	break;
291	0	}
292	0	}
293	0	}