/src/civetweb/src/match.inl

Source
/* Reimplementation of pattern matching */
/* This file is part of the CivetWeb web server.
 * See https://github.com/civetweb/civetweb/
 */


/* Initialize structure with 0 matches */
static void
match_context_reset(struct mg_match_context *mcx)
{
  mcx->num_matches = 0;
  memset(mcx->match, 0, sizeof(mcx->match));
}


/* Add a new match to the list of matches */
static void
match_context_push(const char *str, size_t len, struct mg_match_context *mcx)
{
  if (mcx->num_matches < MG_MATCH_CONTEXT_MAX_MATCHES) {
    mcx->match[mcx->num_matches].str = str;
    mcx->match[mcx->num_matches].len = len;
    mcx->num_matches++;
  }
}


static ptrdiff_t
mg_match_impl(const char *pat,
              size_t pat_len,
              const char *str,
              struct mg_match_context *mcx)
{
  /* Parse string */
  size_t i_pat = 0; /* Pattern index */
  size_t i_str = 0; /* Pattern index */

  int case_sensitive = ((mcx != NULL) ? mcx->case_sensitive : 0); /* 0 or 1 */

  while (i_pat < pat_len) {

    /* Pattern ? matches one character, except / and NULL character */
    if ((pat[i_pat] == '?') && (str[i_str] != '\0')
        && (str[i_str] != '/')) {
      size_t i_str_start = i_str;
      do {
        /* Advance as long as there are ? */
        i_pat++;
        i_str++;
      } while ((i_pat < pat_len) && (pat[i_pat] == '?')
               && (str[i_str] != '\0') && (str[i_str] != '/'));

      /* If we have a match context, add the substring we just found */
      if (mcx) {
        match_context_push(str + i_str_start, i_str - i_str_start, mcx);
      }

      /* Reached end of pattern ? */
      if (i_pat == pat_len) {
        return (ptrdiff_t)i_str;
      }
    }

    /* Pattern $ matches end of string */
    if (pat[i_pat] == '$') {
      return (str[i_str] == '\0') ? (ptrdiff_t)i_str : -1;
    }

    /* Pattern * or ** matches multiple characters */
    if (pat[i_pat] == '*') {
      size_t len; /* length matched by "*" or "**" */
      ptrdiff_t ret;

      i_pat++;
      if ((i_pat < pat_len) && (pat[i_pat] == '*')) {
        /* Pattern ** matches all */
        i_pat++;
        len = strlen(str + i_str);
      } else {
        /* Pattern * matches all except / character */
        len = strcspn(str + i_str, "/");
      }

      if (i_pat == pat_len) {
        /* End of pattern reached. Add all to match context. */
        if (mcx) {
          match_context_push(str + i_str, len, mcx);
        }
        return ((ptrdiff_t)(i_str + len));
      }

      /* This loop searches for the longest possible match */
      do {
        ret = mg_match_impl(pat + i_pat,
                            (pat_len - (size_t)i_pat),
                            str + i_str + len,
                            mcx);
      } while ((ret == -1) && (len-- > 0));

      /* If we have a match context, add the substring we just found */
      if (ret >= 0) {
        if (mcx) {
          match_context_push(str + i_str, len, mcx);
        }
        return ((ptrdiff_t)i_str + ret + (ptrdiff_t)len);
      }

      return -1;
    }


    /* Single character compare */
    if (case_sensitive) {
      if (pat[i_pat] != str[i_str]) {
        /* case sensitive compare: mismatch */
        return -1;
      }
    } else if (lowercase(&pat[i_pat]) != lowercase(&str[i_str])) {
      /* case insensitive compare: mismatch */
      return -1;
    }

    i_pat++;
    i_str++;
  }
  return (ptrdiff_t)i_str;
}


static ptrdiff_t
mg_match_alternatives(const char *pat,
                      size_t pat_len,
                      const char *str,
                      struct mg_match_context *mcx)
{
  const char *match_alternative = (const char *)memchr(pat, '|', pat_len);

  if (mcx != NULL) {
    match_context_reset(mcx);
  }

  while (match_alternative != NULL) {
    /* Split at | for alternative match */
    size_t left_size = (size_t)(match_alternative - pat);

    /* Try left string first */
    ptrdiff_t ret = mg_match_impl(pat, left_size, str, mcx);
    if (ret >= 0) {
      /* A 0-byte match is also valid */
      return ret;
    }

    /* Reset possible incomplete match data */
    if (mcx != NULL) {
      match_context_reset(mcx);
    }

    /* If no match: try right side */
    pat += left_size + 1;
    pat_len -= left_size + 1;
    match_alternative = (const char *)memchr(pat, '|', pat_len);
  }

  /* Handled all | operators. This is the final string. */
  return mg_match_impl(pat, pat_len, str, mcx);
}


static int
match_compare(const void *p1, const void *p2, void *user)
{
  const struct mg_match_element *e1 = (const struct mg_match_element *)p1;
  const struct mg_match_element *e2 = (const struct mg_match_element *)p2;

  /* unused */
  (void)user;

  if (e1->str > e2->str) {
    return +1;
  }
  if (e1->str < e2->str) {
    return -1;
  }
  return 0;
}


#if defined(MG_EXPERIMENTAL_INTERFACES)
CIVETWEB_API
#else
static
#endif
ptrdiff_t
mg_match(const char *pat, const char *str, struct mg_match_context *mcx)
{
  size_t pat_len = strlen(pat);
  ptrdiff_t ret = mg_match_alternatives(pat, pat_len, str, mcx);
  if (mcx != NULL) {
    if (ret < 0) {
      /* Remove possible incomplete data */
      match_context_reset(mcx);
    } else {
      /* Join "?*" to one pattern. */
      size_t i, j;

      /* Use difference of two array elements instead of sizeof, since
       * there may be some additional padding bytes. */
      size_t elmsize =
          (size_t)(&mcx->match[1]) - (size_t)(&mcx->match[0]);

      /* First sort the matches by address ("str" begin to end) */
      mg_sort(mcx->match, mcx->num_matches, elmsize, match_compare, NULL);

      /* Join consecutive matches */
      i = 1;
      while (i < mcx->num_matches) {
        if ((mcx->match[i - 1].str + mcx->match[i - 1].len)
            == mcx->match[i].str) {
          /* Two matches are consecutive. Join length. */
          mcx->match[i - 1].len += mcx->match[i].len;

          /* Shift all list elements. */
          for (j = i + 1; j < mcx->num_matches; j++) {
            mcx->match[j - 1].len = mcx->match[j].len;
            mcx->match[j - 1].str = mcx->match[j].str;
          }

          /* Remove/blank last list element. */
          mcx->num_matches--;
          mcx->match[mcx->num_matches].str = NULL;
          mcx->match[mcx->num_matches].len = 0;

        } else {
          i++;
        }
      }
    }
  }
  return ret;
}


static ptrdiff_t
match_prefix(const char *pattern, size_t pattern_len, const char *str)
{
  if (pattern == NULL) {
    return -1;
  }
  return mg_match_alternatives(pattern, pattern_len, str, NULL);
}


static ptrdiff_t
match_prefix_strlen(const char *pattern, const char *str)
{
  if (pattern == NULL) {
    return -1;
  }
  return mg_match_alternatives(pattern, strlen(pattern), str, NULL);
}

/* End of match.inl */

Coverage Report

Created: 2026-04-01 06:40

Line	Count	Source
1		/* Reimplementation of pattern matching */
2		/* This file is part of the CivetWeb web server.
3		* See https://github.com/civetweb/civetweb/
4		*/
5
6
7		/* Initialize structure with 0 matches */
8		static void
9		match_context_reset(struct mg_match_context *mcx)
10	0	{
11	0	mcx->num_matches = 0;
12	0	memset(mcx->match, 0, sizeof(mcx->match));
13	0	}
14
15
16		/* Add a new match to the list of matches */
17		static void
18		match_context_push(const char str, size_t len, struct mg_match_context mcx)
19	0	{
20	0	if (mcx->num_matches < MG_MATCH_CONTEXT_MAX_MATCHES) {
21	0	mcx->match[mcx->num_matches].str = str;
22	0	mcx->match[mcx->num_matches].len = len;
23	0	mcx->num_matches++;
24	0	}
25	0	}
26
27
28		static ptrdiff_t
29		mg_match_impl(const char *pat,
30		size_t pat_len,
31		const char *str,
32		struct mg_match_context *mcx)
33	0	{
34		/* Parse string */
35	0	size_t i_pat = 0; /* Pattern index */
36	0	size_t i_str = 0; /* Pattern index */
37
38	0	int case_sensitive = ((mcx != NULL) ? mcx->case_sensitive : 0); /* 0 or 1 */
39
40	0	while (i_pat < pat_len) {
41
42		/* Pattern ? matches one character, except / and NULL character */
43	0	if ((pat[i_pat] == '?') && (str[i_str] != '\0')
44	0	&& (str[i_str] != '/')) {
45	0	size_t i_str_start = i_str;
46	0	do {
47		/* Advance as long as there are ? */
48	0	i_pat++;
49	0	i_str++;
50	0	} while ((i_pat < pat_len) && (pat[i_pat] == '?')
51	0	&& (str[i_str] != '\0') && (str[i_str] != '/'));
52
53		/* If we have a match context, add the substring we just found */
54	0	if (mcx) {
55	0	match_context_push(str + i_str_start, i_str - i_str_start, mcx);
56	0	}
57
58		/* Reached end of pattern ? */
59	0	if (i_pat == pat_len) {
60	0	return (ptrdiff_t)i_str;
61	0	}
62	0	}
63
64		/* Pattern $ matches end of string */
65	0	if (pat[i_pat] == '$') {
66	0	return (str[i_str] == '\0') ? (ptrdiff_t)i_str : -1;
67	0	}
68
69		/* Pattern * or ** matches multiple characters */
70	0	if (pat[i_pat] == '*') {
71	0	size_t len; /* length matched by "" or "" /
72	0	ptrdiff_t ret;
73
74	0	i_pat++;
75	0	if ((i_pat < pat_len) && (pat[i_pat] == '*')) {
76		/* Pattern ** matches all */
77	0	i_pat++;
78	0	len = strlen(str + i_str);
79	0	} else {
80		/* Pattern * matches all except / character */
81	0	len = strcspn(str + i_str, "/");
82	0	}
83
84	0	if (i_pat == pat_len) {
85		/* End of pattern reached. Add all to match context. */
86	0	if (mcx) {
87	0	match_context_push(str + i_str, len, mcx);
88	0	}
89	0	return ((ptrdiff_t)(i_str + len));
90	0	}
91
92		/* This loop searches for the longest possible match */
93	0	do {
94	0	ret = mg_match_impl(pat + i_pat,
95	0	(pat_len - (size_t)i_pat),
96	0	str + i_str + len,
97	0	mcx);
98	0	} while ((ret == -1) && (len-- > 0));
99
100		/* If we have a match context, add the substring we just found */
101	0	if (ret >= 0) {
102	0	if (mcx) {
103	0	match_context_push(str + i_str, len, mcx);
104	0	}
105	0	return ((ptrdiff_t)i_str + ret + (ptrdiff_t)len);
106	0	}
107
108	0	return -1;
109	0	}
110
111
112		/* Single character compare */
113	0	if (case_sensitive) {
114	0	if (pat[i_pat] != str[i_str]) {
115		/* case sensitive compare: mismatch */
116	0	return -1;
117	0	}
118	0	} else if (lowercase(&pat[i_pat]) != lowercase(&str[i_str])) {
119		/* case insensitive compare: mismatch */
120	0	return -1;
121	0	}
122
123	0	i_pat++;
124	0	i_str++;
125	0	}
126	0	return (ptrdiff_t)i_str;
127	0	}
128
129
130		static ptrdiff_t
131		mg_match_alternatives(const char *pat,
132		size_t pat_len,
133		const char *str,
134		struct mg_match_context *mcx)
135	0	{
136	0	const char match_alternative = (const char )memchr(pat, '\|', pat_len);
137
138	0	if (mcx != NULL) {
139	0	match_context_reset(mcx);
140	0	}
141
142	0	while (match_alternative != NULL) {
143		/* Split at \| for alternative match */
144	0	size_t left_size = (size_t)(match_alternative - pat);
145
146		/* Try left string first */
147	0	ptrdiff_t ret = mg_match_impl(pat, left_size, str, mcx);
148	0	if (ret >= 0) {
149		/* A 0-byte match is also valid */
150	0	return ret;
151	0	}
152
153		/* Reset possible incomplete match data */
154	0	if (mcx != NULL) {
155	0	match_context_reset(mcx);
156	0	}
157
158		/* If no match: try right side */
159	0	pat += left_size + 1;
160	0	pat_len -= left_size + 1;
161	0	match_alternative = (const char *)memchr(pat, '\|', pat_len);
162	0	}
163
164		/* Handled all \| operators. This is the final string. */
165	0	return mg_match_impl(pat, pat_len, str, mcx);
166	0	}
167
168
169		static int
170		match_compare(const void p1, const void p2, void *user)
171	0	{
172	0	const struct mg_match_element e1 = (const struct mg_match_element )p1;
173	0	const struct mg_match_element e2 = (const struct mg_match_element )p2;
174	0
175	0	/* unused */
176	0	(void)user;
177	0
178	0	if (e1->str > e2->str) {
179	0	return +1;
180	0	}
181	0	if (e1->str < e2->str) {
182	0	return -1;
183	0	}
184	0	return 0;
185	0	}
186
187
188		#if defined(MG_EXPERIMENTAL_INTERFACES)
189		CIVETWEB_API
190		#else
191		static
192		#endif
193		ptrdiff_t
194		mg_match(const char pat, const char str, struct mg_match_context *mcx)
195	0	{
196	0	size_t pat_len = strlen(pat);
197	0	ptrdiff_t ret = mg_match_alternatives(pat, pat_len, str, mcx);
198	0	if (mcx != NULL) {
199	0	if (ret < 0) {
200	0	/* Remove possible incomplete data */
201	0	match_context_reset(mcx);
202	0	} else {
203	0	/* Join "?" to one pattern. /
204	0	size_t i, j;
205	0
206	0	/* Use difference of two array elements instead of sizeof, since
207	0	* there may be some additional padding bytes. */
208	0	size_t elmsize =
209	0	(size_t)(&mcx->match[1]) - (size_t)(&mcx->match[0]);
210	0
211	0	/* First sort the matches by address ("str" begin to end) */
212	0	mg_sort(mcx->match, mcx->num_matches, elmsize, match_compare, NULL);
213	0
214	0	/* Join consecutive matches */
215	0	i = 1;
216	0	while (i < mcx->num_matches) {
217	0	if ((mcx->match[i - 1].str + mcx->match[i - 1].len)
218	0	== mcx->match[i].str) {
219	0	/* Two matches are consecutive. Join length. */
220	0	mcx->match[i - 1].len += mcx->match[i].len;
221	0
222	0	/* Shift all list elements. */
223	0	for (j = i + 1; j < mcx->num_matches; j++) {
224	0	mcx->match[j - 1].len = mcx->match[j].len;
225	0	mcx->match[j - 1].str = mcx->match[j].str;
226	0	}
227	0
228	0	/* Remove/blank last list element. */
229	0	mcx->num_matches--;
230	0	mcx->match[mcx->num_matches].str = NULL;
231	0	mcx->match[mcx->num_matches].len = 0;
232	0
233	0	} else {
234	0	i++;
235	0	}
236	0	}
237	0	}
238	0	}
239	0	return ret;
240	0	}
241
242
243		static ptrdiff_t
244		match_prefix(const char pattern, size_t pattern_len, const char str)
245	0	{
246	0	if (pattern == NULL) {
247	0	return -1;
248	0	}
249	0	return mg_match_alternatives(pattern, pattern_len, str, NULL);
250	0	}
251
252
253		static ptrdiff_t
254		match_prefix_strlen(const char pattern, const char str)
255	0	{
256	0	if (pattern == NULL) {
257	0	return -1;
258	0	}
259	0	return mg_match_alternatives(pattern, strlen(pattern), str, NULL);
260	0	}
261
262		/* End of match.inl */