Re: memmem issues

[Bruno Haible]

Eric Blake wrote:
> - It uses memcmp without depending on the memcmp module, making it needlessly 
> fail on some older platforms.

If memory serves me well, the platforms where memcmp was incorrect (comparing
signed instead of unsigned byte values) were SunOS 4 and possibly IRIX 4.
*Very* ancient.

That's the reason why so many modules use memcmp without requiring the module.

> - It passed up on using optimizations built into memchr when needle_len is 1. 
>  
> Is it okay with everyone that this patch relicenses memchr as LGPLv2+?

Yes.

> - test-memmem.c was flat-out broken (calling memmem with 3 instead of 4 
> arguments).  The reason it was never compiled was the lack of a memmem-tests 
> module.

Thanks for finding this!

> - There are platform-specific bugs in existing memmem implementations.  
> Cygwin, 
> for example, returns NULL instead of haystack for memmem(haystack,len,"",0).

Ouch.

> How best do I document platform bugs in non-standardized functions?

I would put such info as comments into lib/string.h.

> - The implementation was naively quadratic in the worst-case complexity.  ...
>   glibc still uses the naive implementation - should we file a bug with them
>   to fix it?

It's worth a try. When fnmatch turned out to be exponential and I reported it,
Jakub fixed it.

> Should we update memmem.m4 to reject known-quadratic implementations? 

I would say no, since memmem is rarely applied to memory regions larger than
a few hundred bytes. Make it optional, by creating a 'memmem-fast' module
that requires the O(n) implementation.

> +     precisely, when
> +       - the outer loop count is >= 10,
> +       - the average number of comparisons per outer loop is >= 5,
> +       - the total number of comparisons is >= m.

These comments are out of sync with the code.

> +          /* The first character matches.  */

Better write "byte" here, not "character", so that people remember i18n
issues.

> +      [AC_RUN_IFELSE([AC_LANG_PROGRAM([#include <string.h>],
> +         [return !memmem ("a", 1, NULL, 0);])],

<string.h> does not define NULL. Better write (void*)0 or "" instead of NULL.

> +TESTS += test-memmem
> +TESTS_ENVIRONMENT += EXEEXT='@EXEEXT@'
> +check_PROGRAMS += test-memmem

You can drop the TESTS_ENVIRONMENT line.

Bruno