maint/gnulib/tests/test-strstr.c

/* */
This source file includes following definitions.
main
   1 /*
   2  * Copyright (C) 2004, 2007-2021 Free Software Foundation, Inc.
   3  * Written by Bruno Haible and Eric Blake
   4  *
   5  * This program is free software: you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 3 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  17 
  18 #include <config.h>
  19 
  20 #include <string.h>
  21 
  22 #include "signature.h"
  23 SIGNATURE_CHECK (strstr, char *, (char const *, char const *));
  24 
  25 #include <signal.h>
  26 #include <stdlib.h>
  27 #include <unistd.h>
  28 
  29 #include "zerosize-ptr.h"
  30 #include "macros.h"
  31 
  32 int
  33 main (int argc, char *argv[])
     /*  */
  34 {
  35 #if HAVE_DECL_ALARM
  36   /* Declare failure if test takes too long, by using default abort
  37      caused by SIGALRM.  All known platforms that lack alarm also have
  38      a quadratic strstr, and the replacement strstr is known to not
  39      take too long.  */
  40   int alarm_value = 50;
  41   signal (SIGALRM, SIG_DFL);
  42   alarm (alarm_value);
  43 #endif
  44 
  45   {
  46     const char input[] = "foo";
  47     const char *result = strstr (input, "");
  48     ASSERT (result == input);
  49   }
  50 
  51   {
  52     const char input[] = "foo";
  53     const char *result = strstr (input, "o");
  54     ASSERT (result == input + 1);
  55   }
  56 
  57   {
  58     /* On some platforms, the memchr() functions reads past the first
  59        occurrence of the byte to be searched, leading to an out-of-bounds
  60        read access for strstr().
  61        See <https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=521737>.
  62        This is a bug in memchr(), see the Austin Group's clarification
  63        <https://www.opengroup.org/austin/docs/austin_454.txt>.  */
  64     const char *fix = "aBaaaaaaaaaaax";
  65     char *page_boundary = (char *) zerosize_ptr ();
  66     size_t len = strlen (fix) + 1;
  67     char *input = page_boundary ? page_boundary - len : malloc (len);
  68     const char *result;
  69 
  70     strcpy (input, fix);
  71     result = strstr (input, "B1x");
  72     ASSERT (result == NULL);
  73     if (!page_boundary)
  74       free (input);
  75   }
  76 
  77   {
  78     const char input[] = "ABC ABCDAB ABCDABCDABDE";
  79     const char *result = strstr (input, "ABCDABD");
  80     ASSERT (result == input + 15);
  81   }
  82 
  83   {
  84     const char input[] = "ABC ABCDAB ABCDABCDABDE";
  85     const char *result = strstr (input, "ABCDABE");
  86     ASSERT (result == NULL);
  87   }
  88 
  89   {
  90     const char input[] = "ABC ABCDAB ABCDABCDABDE";
  91     const char *result = strstr (input, "ABCDABCD");
  92     ASSERT (result == input + 11);
  93   }
  94 
  95   /* Check that a long periodic needle does not cause false positives.  */
  96   {
  97     const char input[] = "F_BD_CE_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD"
  98                          "_C3_88_20_EF_BF_BD_EF_BF_BD_EF_BF_BD"
  99                          "_C3_A7_20_EF_BF_BD";
 100     const char need[] = "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD";
 101     const char *result = strstr (input, need);
 102     ASSERT (result == NULL);
 103   }
 104   {
 105     const char input[] = "F_BD_CE_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD"
 106                          "_C3_88_20_EF_BF_BD_EF_BF_BD_EF_BF_BD"
 107                          "_C3_A7_20_EF_BF_BD_DA_B5_C2_A6_20"
 108                          "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD";
 109     const char need[] = "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD";
 110     const char *result = strstr (input, need);
 111     ASSERT (result == input + 115);
 112   }
 113 
 114   /* Check that a very long haystack is handled quickly if the needle is
 115      short and occurs near the beginning.  */
 116   {
 117     size_t repeat = 10000;
 118     size_t m = 1000000;
 119     const char *needle =
 120       "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
 121       "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
 122     char *haystack = (char *) malloc (m + 1);
 123     if (haystack != NULL)
 124       {
 125         memset (haystack, 'A', m);
 126         haystack[0] = 'B';
 127         haystack[m] = '\0';
 128 
 129         for (; repeat > 0; repeat--)
 130           {
 131             ASSERT (strstr (haystack, needle) == haystack + 1);
 132           }
 133 
 134         free (haystack);
 135       }
 136   }
 137 
 138   /* Check that a very long needle is discarded quickly if the haystack is
 139      short.  */
 140   {
 141     size_t repeat = 10000;
 142     size_t m = 1000000;
 143     const char *haystack =
 144       "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
 145       "ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB";
 146     char *needle = (char *) malloc (m + 1);
 147     if (needle != NULL)
 148       {
 149         memset (needle, 'A', m);
 150         needle[m] = '\0';
 151 
 152         for (; repeat > 0; repeat--)
 153           {
 154             ASSERT (strstr (haystack, needle) == NULL);
 155           }
 156 
 157         free (needle);
 158       }
 159   }
 160 
 161   /* Check that the asymptotic worst-case complexity is not quadratic.  */
 162   {
 163     size_t m = 1000000;
 164     char *haystack = (char *) malloc (2 * m + 2);
 165     char *needle = (char *) malloc (m + 2);
 166     if (haystack != NULL && needle != NULL)
 167       {
 168         const char *result;
 169 
 170         memset (haystack, 'A', 2 * m);
 171         haystack[2 * m] = 'B';
 172         haystack[2 * m + 1] = '\0';
 173 
 174         memset (needle, 'A', m);
 175         needle[m] = 'B';
 176         needle[m + 1] = '\0';
 177 
 178         result = strstr (haystack, needle);
 179         ASSERT (result == haystack + m);
 180       }
 181     free (needle);
 182     free (haystack);
 183   }
 184 
 185   /* Sublinear speed is only possible in memmem; strstr must examine
 186      every character of haystack to find its length.  */
 187 
 188 
 189   {
 190     /* Ensure that with a barely periodic "short" needle, strstr's
 191        search does not mistakenly skip just past the match point.
 192        This use of strstr would mistakenly return NULL before
 193        gnulib v0.0-4927.  */
 194     const char *haystack =
 195       "\n"
 196       "with_build_libsubdir\n"
 197       "with_local_prefix\n"
 198       "with_gxx_include_dir\n"
 199       "with_cpp_install_dir\n"
 200       "enable_generated_files_in_srcdir\n"
 201       "with_gnu_ld\n"
 202       "with_ld\n"
 203       "with_demangler_in_ld\n"
 204       "with_gnu_as\n"
 205       "with_as\n"
 206       "enable_largefile\n"
 207       "enable_werror_always\n"
 208       "enable_checking\n"
 209       "enable_coverage\n"
 210       "enable_gather_detailed_mem_stats\n"
 211       "enable_build_with_cxx\n"
 212       "with_stabs\n"
 213       "enable_multilib\n"
 214       "enable___cxa_atexit\n"
 215       "enable_decimal_float\n"
 216       "enable_fixed_point\n"
 217       "enable_threads\n"
 218       "enable_tls\n"
 219       "enable_objc_gc\n"
 220       "with_dwarf2\n"
 221       "enable_shared\n"
 222       "with_build_sysroot\n"
 223       "with_sysroot\n"
 224       "with_specs\n"
 225       "with_pkgversion\n"
 226       "with_bugurl\n"
 227       "enable_languages\n"
 228       "with_multilib_list\n";
 229     const char *needle = "\n"
 230       "with_gnu_ld\n";
 231     const char* p = strstr (haystack, needle);
 232     ASSERT (p - haystack == 114);
 233   }
 234 
 235   {
 236     /* Same bug, shorter trigger.  */
 237     const char *haystack = "..wi.d.";
 238     const char *needle = ".d.";
 239     const char* p = strstr (haystack, needle);
 240     ASSERT (p - haystack == 4);
 241   }
 242 
 243   {
 244     /* Like the above, but trigger the flaw in two_way_long_needle
 245        by using a needle of length LONG_NEEDLE_THRESHOLD (32) or greater.
 246        Rather than trying to find the right alignment manually, I've
 247        arbitrarily chosen the following needle and template for the
 248        haystack, and ensure that for each placement of the needle in
 249        that haystack, strstr finds it.  */
 250     const char *needle = "\nwith_gnu_ld-extend-to-len-32-b\n";
 251     const char *h =
 252       "\n"
 253       "with_build_libsubdir\n"
 254       "with_local_prefix\n"
 255       "with_gxx_include_dir\n"
 256       "with_cpp_install_dir\n"
 257       "with_e_\n"
 258       "..............................\n"
 259       "with_FGHIJKLMNOPQRSTUVWXYZ\n"
 260       "with_567890123456789\n"
 261       "with_multilib_list\n";
 262     size_t h_len = strlen (h);
 263     char *haystack = malloc (h_len + 1);
 264     size_t i;
 265     ASSERT (haystack);
 266     for (i = 0; i < h_len - strlen (needle); i++)
 267       {
 268         const char *p;
 269         memcpy (haystack, h, h_len + 1);
 270         memcpy (haystack + i, needle, strlen (needle) + 1);
 271         p = strstr (haystack, needle);
 272         ASSERT (p);
 273         ASSERT (p - haystack == i);
 274       }
 275     free (haystack);
 276   }
 277 
 278   /* Test long needles.  */
 279   {
 280     size_t m = 1024;
 281     char *haystack = (char *) malloc (2 * m + 1);
 282     char *needle = (char *) malloc (m + 1);
 283     if (haystack != NULL && needle != NULL)
 284       {
 285         const char *p;
 286         haystack[0] = 'x';
 287         memset (haystack + 1, ' ', m - 1);
 288         memset (haystack + m, 'x', m);
 289         haystack[2 * m] = '\0';
 290         memset (needle, 'x', m);
 291         needle[m] = '\0';
 292         p = strstr (haystack, needle);
 293         ASSERT (p);
 294         ASSERT (p - haystack == m);
 295       }
 296     free (needle);
 297     free (haystack);
 298   }
 299 
 300   return 0;
 301 }
/* */
root/maint/gnulib/tests/test-strstr.c

DEFINITIONS
