tests/test-c-strstr.c

   1 /* Test of 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-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 test_exit_status;
 246 }