Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!decwrl!pa.dec.com!src.dec.com!src.dec.com!muller
From: muller@src.dec.com (Eric Muller)
Newsgroups: comp.lang.modula3
Subject: Re: Typefinger printing in SRC M3
Message-ID: <1991Feb14.230044.20552@src.dec.com>
Date: 15 Feb 91 07:00:44 GMT
References: <9102111538.AA24105@yough.ucc.umass.edu>
Sender: news@src.dec.com (News)
Reply-To: muller@src.dec.com (Eric Muller)
Organization: DEC Systems Research Center
Lines: 36
Cc: broder@src.dec.com

In article <9102111538.AA24105@yough.ucc.umass.edu>, hudson@yough.ucc.umass.edu (Rick Hudson) writes:
>   My surface impression from scanning the sources is that works as
>   follows. Each type (scalar or constructed) has an operation to return
>   a textual type name. When fingerprinting a constructed type (esp. an
>   object/record) a string is constructed containing the recursive
>   enumeration of all scalar type names used in that constructed type.
>   This string is then treated as input to the "poly" function to compute
>   a 64-bit fingerprint.  
>   Is this reasonably accurate or am I way out in left field >>

This is accurate. In addition, you have to consider the case of opaque
types. The final phase of linking (practically, when the program
starts, but conceptually at link time) knows everything about the types and
computes a "full" fingerprint, based on the fingerprints of the
partial revelations.

For example, 

INTERFACE I;
TYPE T <: ROOT;
END I.

MODULE M;
TYPE U = T OBJECT a: INTEGER; END;
END M.

When compiling M, we generate a partial fingerprint for "OBJECT a:
INTEGER". A link time, this partial fingerprint is combined with the
fingerprint of type to the right of the "REVEAL T =" that must be
somewhere in the program.

As for the probability of collisions, it is extremely low. You can ask
Andrei Broder (broder@src.dec.com) if you want to know the fine points.

-- 
Eric.