1 /* Test of case-insensitive searching in a string.
2 Copyright (C) 2007-2022 Free Software Foundation, Inc.
3
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <https://www.gnu.org/licenses/>. */
16
17 /* Written by Bruno Haible <bruno@clisp.org>, 2007. */
18
19 #include <config.h>
20
21 #include "c-strcasestr.h"
22
23 #include <stdlib.h>
24 #include <string.h>
25
26 #include "macros.h"
27
28 int
29 main ()
30 {
31 {
32 const char input[] = "foo";
33 const char *result = c_strcasestr (input, "");
34 ASSERT (result == input);
35 }
36
37 {
38 const char input[] = "foo";
39 const char *result = c_strcasestr (input, "O");
40 ASSERT (result == input + 1);
41 }
42
43 {
44 const char input[] = "ABC ABCDAB ABCDABCDABDE";
45 const char *result = c_strcasestr (input, "ABCDaBD");
46 ASSERT (result == input + 15);
47 }
48
49 {
50 const char input[] = "ABC ABCDAB ABCDABCDABDE";
51 const char *result = c_strcasestr (input, "ABCDaBE");
52 ASSERT (result == NULL);
53 }
54
55 {
56 const char input[] = "ABC ABCDAB ABCDABCDABDE";
57 const char *result = c_strcasestr (input, "ABCDaBCD");
58 ASSERT (result == input + 11);
59 }
60
61 /* Check that a long periodic needle does not cause false positives. */
62 {
63 const char input[] = "F_BD_CE_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD"
64 "_C3_88_20_EF_BF_BD_EF_BF_BD_EF_BF_BD"
65 "_C3_A7_20_EF_BF_BD";
66 const char need[] = "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD";
67 const char *result = c_strcasestr (input, need);
68 ASSERT (result == NULL);
69 }
70 {
71 const char input[] = "F_BD_CE_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD"
72 "_C3_88_20_EF_BF_BD_EF_BF_BD_EF_BF_BD"
73 "_C3_A7_20_EF_BF_BD_DA_B5_C2_A6_20"
74 "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD";
75 const char need[] = "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD";
76 const char *result = c_strcasestr (input, need);
77 ASSERT (result == input + 115);
78 }
79
80 /* Check that a very long haystack is handled quickly if the needle is
81 short and occurs near the beginning. */
82 {
83 size_t repeat = 10000;
84 size_t m = 1000000;
85 const char *needle =
86 "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
87 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaAaaaaaaAAAAaaaaaaa"
88 "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
89 char *haystack = (char *) malloc (m + 1);
90 if (haystack != NULL)
91 {
92 memset (haystack, 'A', m);
93 haystack[0] = 'B';
94 haystack[m] = '\0';
95
96 for (; repeat > 0; repeat--)
97 {
98 ASSERT (c_strcasestr (haystack, needle) == haystack + 1);
99 }
100
101 free (haystack);
102 }
103 }
104
105 /* Check that a very long needle is discarded quickly if the haystack is
106 short. */
107 {
108 size_t repeat = 10000;
109 size_t m = 1000000;
110 const char *haystack =
111 "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
112 "ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB";
113 char *needle = (char *) malloc (m + 1);
114 if (needle != NULL)
115 {
116 memset (needle, 'A', m);
117 needle[m] = '\0';
118
119 for (; repeat > 0; repeat--)
120 {
121 ASSERT (c_strcasestr (haystack, needle) == NULL);
122 }
123
124 free (needle);
125 }
126 }
127
128 /* Check that the asymptotic worst-case complexity is not quadratic. */
129 {
130 size_t m = 1000000;
131 char *haystack = (char *) malloc (2 * m + 2);
132 char *needle = (char *) malloc (m + 2);
133 if (haystack != NULL && needle != NULL)
134 {
135 const char *result;
136
137 memset (haystack, 'A', 2 * m);
138 haystack[2 * m] = 'B';
139 haystack[2 * m + 1] = '\0';
140
141 memset (needle, 'a', m);
142 needle[m] = 'B';
143 needle[m + 1] = '\0';
144
145 result = c_strcasestr (haystack, needle);
146 ASSERT (result == haystack + m);
147 }
148 free (needle);
149 free (haystack);
150 }
151
152 {
153 /* Ensure that with a barely periodic "short" needle, c_strcasestr's
154 search does not mistakenly skip just past the match point.
155 This use of c_strcasestr would mistakenly return NULL before
156 gnulib v0.0-4927. */
157 const char *haystack =
158 "\n"
159 "with_build_libsubdir\n"
160 "with_local_prefix\n"
161 "with_gxx_include_dir\n"
162 "with_cpp_install_dir\n"
163 "enable_generated_files_in_srcdir\n"
164 "with_gnu_ld\n"
165 "with_ld\n"
166 "with_demangler_in_ld\n"
167 "with_gnu_as\n"
168 "with_as\n"
169 "enable_largefile\n"
170 "enable_werror_always\n"
171 "enable_checking\n"
172 "enable_coverage\n"
173 "enable_gather_detailed_mem_stats\n"
174 "enable_build_with_cxx\n"
175 "with_stabs\n"
176 "enable_multilib\n"
177 "enable___cxa_atexit\n"
178 "enable_decimal_float\n"
179 "enable_fixed_point\n"
180 "enable_threads\n"
181 "enable_tls\n"
182 "enable_objc_gc\n"
183 "with_dwarf2\n"
184 "enable_shared\n"
185 "with_build_sysroot\n"
186 "with_sysroot\n"
187 "with_specs\n"
188 "with_pkgversion\n"
189 "with_bugurl\n"
190 "enable_languages\n"
191 "with_multilib_list\n";
192 const char *needle = "\n"
193 "with_GNU_ld\n";
194 const char* p = c_strcasestr (haystack, needle);
195 ASSERT (p - haystack == 114);
196 }
197
198 {
199 /* Same bug, shorter trigger. */
200 const char *haystack = "..wi.D.";
201 const char *needle = ".d.";
202 const char* p = c_strcasestr (haystack, needle);
203 ASSERT (p - haystack == 4);
204 }
205
206 {
207 /* Like the above, but trigger the flaw in two_way_long_needle
208 by using a needle of length LONG_NEEDLE_THRESHOLD (32) or greater.
209 Rather than trying to find the right alignment manually, I've
210 arbitrarily chosen the following needle and template for the
211 haystack, and ensure that for each placement of the needle in
212 that haystack, c_strcasestr finds it. */
213 const char *needle = "\nwith_gnu_ld-extend-to-len-32-b\n";
214 const char *h =
215 "\n"
216 "with_build_libsubdir\n"
217 "with_local_prefix\n"
218 "with_gxx_include_dir\n"
219 "with_cpp_install_dir\n"
220 "with_e_\n"
221 "..............................\n"
222 "with_FGHIJKLMNOPQRSTUVWXYZ\n"
223 "with_567890123456789\n"
224 "with_multilib_list\n";
225 size_t h_len = strlen (h);
226 char *haystack = malloc (h_len + 1);
227 size_t i;
228 ASSERT (haystack);
229 for (i = 0; i < h_len - strlen (needle); i++)
230 {
231 const char *p;
232 memcpy (haystack, h, h_len + 1);
233 memcpy (haystack + i, needle, strlen (needle) + 1);
234 p = c_strcasestr (haystack, needle);
235 ASSERT (p);
236 ASSERT (p - haystack == i);
237 }
238 free (haystack);
239 }
240
241 /* Test long needles. */
242 {
243 size_t m = 1024;
244 char *haystack = (char *) malloc (2 * m + 1);
245 char *needle = (char *) malloc (m + 1);
246 if (haystack != NULL && needle != NULL)
247 {
248 const char *p;
249 haystack[0] = 'x';
250 memset (haystack + 1, ' ', m - 1);
251 memset (haystack + m, 'x', m);
252 haystack[2 * m] = '\0';
253 memset (needle, 'X', m);
254 needle[m] = '\0';
255 p = c_strcasestr (haystack, needle);
256 ASSERT (p);
257 ASSERT (p - haystack == m);
258 }
259 free (needle);
260 free (haystack);
261 }
262
263 return 0;
264 }