1 /* Test of searching in a string.
2 Copyright (C) 2007-2023 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-strstr.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_strstr (input, "");
34 ASSERT (result == input);
35 }
36
37 {
38 const char input[] = "foo";
39 const char *result = c_strstr (input, "o");
40 ASSERT (result == input + 1);
41 }
42
43 {
44 const char input[] = "ABC ABCDAB ABCDABCDABDE";
45 const char *result = c_strstr (input, "ABCDABD");
46 ASSERT (result == input + 15);
47 }
48
49 {
50 const char input[] = "ABC ABCDAB ABCDABCDABDE";
51 const char *result = c_strstr (input, "ABCDABE");
52 ASSERT (result == NULL);
53 }
54
55 /* Check that a very long haystack is handled quickly if the needle is
56 short and occurs near the beginning. */
57 {
58 size_t repeat = 10000;
59 size_t m = 1000000;
60 const char *needle =
61 "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
62 "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
63 char *haystack = (char *) malloc (m + 1);
64 if (haystack != NULL)
65 {
66 memset (haystack, 'A', m);
67 haystack[0] = 'B';
68 haystack[m] = '\0';
69
70 for (; repeat > 0; repeat--)
71 {
72 ASSERT (c_strstr (haystack, needle) == haystack + 1);
73 }
74
75 free (haystack);
76 }
77 }
78
79 /* Check that a very long needle is discarded quickly if the haystack is
80 short. */
81 {
82 size_t repeat = 10000;
83 size_t m = 1000000;
84 const char *haystack =
85 "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
86 "ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB";
87 char *needle = (char *) malloc (m + 1);
88 if (needle != NULL)
89 {
90 memset (needle, 'A', m);
91 needle[m] = '\0';
92
93 for (; repeat > 0; repeat--)
94 {
95 ASSERT (c_strstr (haystack, needle) == NULL);
96 }
97
98 free (needle);
99 }
100 }
101
102 /* Check that the asymptotic worst-case complexity is not quadratic. */
103 {
104 size_t m = 1000000;
105 char *haystack = (char *) malloc (2 * m + 2);
106 char *needle = (char *) malloc (m + 2);
107 if (haystack != NULL && needle != NULL)
108 {
109 const char *result;
110
111 memset (haystack, 'A', 2 * m);
112 haystack[2 * m] = 'B';
113 haystack[2 * m + 1] = '\0';
114
115 memset (needle, 'A', m);
116 needle[m] = 'B';
117 needle[m + 1] = '\0';
118
119 result = c_strstr (haystack, needle);
120 ASSERT (result == haystack + m);
121 }
122 free (needle);
123 free (haystack);
124 }
125
126 {
127 /* Ensure that with a barely periodic "short" needle, c_strstr's
128 search does not mistakenly skip just past the match point.
129 This use of c_strstr would mistakenly return NULL before
130 gnulib v0.0-4927. */
131 const char *haystack =
132 "\n"
133 "with_build_libsubdir\n"
134 "with_local_prefix\n"
135 "with_gxx_include_dir\n"
136 "with_cpp_install_dir\n"
137 "enable_generated_files_in_srcdir\n"
138 "with_gnu_ld\n"
139 "with_ld\n"
140 "with_demangler_in_ld\n"
141 "with_gnu_as\n"
142 "with_as\n"
143 "enable_largefile\n"
144 "enable_werror_always\n"
145 "enable_checking\n"
146 "enable_coverage\n"
147 "enable_gather_detailed_mem_stats\n"
148 "enable_build_with_cxx\n"
149 "with_stabs\n"
150 "enable_multilib\n"
151 "enable___cxa_atexit\n"
152 "enable_decimal_float\n"
153 "enable_fixed_point\n"
154 "enable_threads\n"
155 "enable_tls\n"
156 "enable_objc_gc\n"
157 "with_dwarf2\n"
158 "enable_shared\n"
159 "with_build_sysroot\n"
160 "with_sysroot\n"
161 "with_specs\n"
162 "with_pkgversion\n"
163 "with_bugurl\n"
164 "enable_languages\n"
165 "with_multilib_list\n";
166 const char *needle = "\n"
167 "with_gnu_ld\n";
168 const char* p = c_strstr (haystack, needle);
169 ASSERT (p - haystack == 114);
170 }
171
172 {
173 /* Same bug, shorter trigger. */
174 const char *haystack = "..wi.d.";
175 const char *needle = ".d.";
176 const char* p = c_strstr (haystack, needle);
177 ASSERT (p - haystack == 4);
178 }
179
180 {
181 /* Like the above, but trigger the flaw in two_way_long_needle
182 by using a needle of length LONG_NEEDLE_THRESHOLD (32) or greater.
183 Rather than trying to find the right alignment manually, I've
184 arbitrarily chosen the following needle and template for the
185 haystack, and ensure that for each placement of the needle in
186 that haystack, c_strstr finds it. */
187 const char *needle = "\nwith_gnu_ld-extend-to-len-32-b\n";
188 const char *h =
189 "\n"
190 "with_build_libsubdir\n"
191 "with_local_prefix\n"
192 "with_gxx_include_dir\n"
193 "with_cpp_install_dir\n"
194 "with_e_\n"
195 "..............................\n"
196 "with_FGHIJKLMNOPQRSTUVWXYZ\n"
197 "with_567890123456789\n"
198 "with_multilib_list\n";
199 size_t h_len = strlen (h);
200 char *haystack = malloc (h_len + 1);
201 size_t i;
202 ASSERT (haystack);
203 for (i = 0; i < h_len - strlen (needle); i++)
204 {
205 const char *p;
206 memcpy (haystack, h, h_len + 1);
207 memcpy (haystack + i, needle, strlen (needle) + 1);
208 p = c_strstr (haystack, needle);
209 ASSERT (p);
210 ASSERT (p - haystack == i);
211 }
212 free (haystack);
213 }
214
215 /* Test case from Yves Bastide.
216 <https://www.openwall.com/lists/musl/2014/04/18/2> */
217 {
218 const char input[] = "playing play play play always";
219 const char *result = c_strstr (input, "play play play");
220 ASSERT (result == input + 8);
221 }
222
223 /* Test long needles. */
224 {
225 size_t m = 1024;
226 char *haystack = (char *) malloc (2 * m + 1);
227 char *needle = (char *) malloc (m + 1);
228 if (haystack != NULL && needle != NULL)
229 {
230 const char *p;
231 haystack[0] = 'x';
232 memset (haystack + 1, ' ', m - 1);
233 memset (haystack + m, 'x', m);
234 haystack[2 * m] = '\0';
235 memset (needle, 'x', m);
236 needle[m] = '\0';
237 p = c_strstr (haystack, needle);
238 ASSERT (p);
239 ASSERT (p - haystack == m);
240 }
241 free (needle);
242 free (haystack);
243 }
244
245 return 0;
246 }