tests/test-c-strcasestr.c

   1 /* Test of case-insensitive searching in a string.
   2    Copyright (C) 2007-2024 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 case from Yves Bastide.
 242      <https://www.openwall.com/lists/musl/2014/04/18/2>  */
 243   {
 244     const char input[] = "playing PLAY play PLAY always";
 245     const char *result = c_strcasestr (input, "play PLAY play");
 246     ASSERT (result == input + 8);
 247   }
 248
 249   /* Test long needles.  */
 250   {
 251     size_t m = 1024;
 252     char *haystack = (char *) malloc (2 * m + 1);
 253     char *needle = (char *) malloc (m + 1);
 254     if (haystack != NULL && needle != NULL)
 255       {
 256         const char *p;
 257         haystack[0] = 'x';
 258         memset (haystack + 1, ' ', m - 1);
 259         memset (haystack + m, 'x', m);
 260         haystack[2 * m] = '\0';
 261         memset (needle, 'X', m);
 262         needle[m] = '\0';
 263         p = c_strcasestr (haystack, needle);
 264         ASSERT (p);
 265         ASSERT (p - haystack == m);
 266       }
 267     free (needle);
 268     free (haystack);
 269   }
 270
 271   return test_exit_status;
 272 }