Re: [Caml-list] Maximum non-constant constructors

[Eric Cooper <ecc@cmu.edu>]

On Thu, Mar 17, 2005 at 01:36:35PM +0100, Jean-Christophe Filliatre wrote:
> 
> Richard Jones writes:
>  > 
>  > Has anyone ever seen (in real life) a collision in the hash function
>  > which encodes polymorphic variants?  Just wondering ...  It seems like
>  > it could occur.
> 
> Yes it could occur, but there is a check a link time for such collisions.

Out of curiousity, I wrote a short program to enumerate possible
collisions.  (If you examine the hash_variant function in
typing/btype.ml, it's clear that any base-223 representation of a
multiple of 2^31 in which the "digits" are legal identifier characters
will hash to zero, and will therefore be an "invisible prefix".)

For example, for all strings XXX, the variants `XXX and `zyctRecXXX
collide.

Here's a small sampling of other invisible prefixes:

    CibPXd UMEDdm d1usNc hS1P1' jagJhn oZshTt Atmtemb CAoStes DHobutv
    PeoQMeo SQufoxX alzzdgn dRtEXEl eeAnNdc glMavfi stYKKKs vbasThr

My guess is that none of them are likely to be chosen by
humans, but might occur in program-generated code.

-- 
Eric Cooper             e c c @ c m u . e d u