[cfe-dev] [RFC] cHash: Integration of AST hashing

Fri Dec 8 19:38:16 PST 2017

On Mon, Aug 7, 2017 at 1:05 AM, Christian Dietrich via cfe-dev <
cfe-dev at lists.llvm.org> wrote:

> Raphael Isemann <teemperor at gmail.com> writes:
>
> > That sounds like a really nice tool!
>
> I also really like the general principle of avoiding work that is
> redundant in the end. Let's save some polar bears! And some developers
> from serious injuries stemming from sword fights.
>
> > One problem I see is that we get yet another AST hashing
> > implementation in clang. I'm aware of at least four of them that I
> > personally work with:
> >
> > * The normal Stmt::Profile for Stmts
>
> This does indeed look structurally similar to our implementation for
> statements. However, types are only included as means of their pointers
> and, therefore, the hash is not stable over compilations. I wonder for
> which applications this is actually sufficient. And, does it really
> speed up things to badly?
>
> > * The ODR hashing for AST nodes in modules.
>
> This is also based on StmtProfilerWithoutPointers as far as I can
> tell[1]. And it is stable over invocations as it actually handles types.
> However, changing the order of declarations[1] will alter the hash. Also
> one thing we did in cHash is to use pseudrandom identifiers for
> different ast node types[3] to avoid some of the possible collisions. If
> you only add small integer values (getKind(), etc.) It is much easier to
> have a collision. Therefore, we add something like
>
> <UNIQUE-NODE-CLASS-ID> <FIELD1> <FIELD2> <FIELD3>
>
> to the hashing stream most of the time. Ideally, the text that goes into
> the hash should be usable to reconstruct an AST tree with the same
> structure; not neccessarily with the same information.
>
> I don't understand your need for pseudrandom identifiers.  If a specific
type of AST node (for instance, a Decl) is expected, then adding to the
stream the node kind (like from Decl::getKind()) is enough to avoid
collisions.  If any node can be expected, then first pass in an enum to
differentiate the different types (Decl, Stmt, Type, Attr, etc), then add
the node kind, and then continue on.  Stmt::Profile and ODRHash use this
method to avoid collisions.  I don't see any gain from using new
identifiers here.

> > * The ASTDiff also has one
>
> Ok, then I was unable to find it. Can you give me a pointer
>
> > * The CloneDetector with its StmtDataCollector which can be
> > specialized for hashing
> >
> > They all contain similar code and have similar goals. And they all
> > contain different kind of bugs. And that's just the implementations
> > that I'm aware of.
>
> So, when they all contain some kinds of quirks, we really should build
> a good test harness around a unified implementation. Since nobody wants
> to break the "give me a unique identifier" silently.
>
> > I would very much prefer if we don't add more redundant code here but
> > instead try to figure out if we can get all this code in a more
> > central place.
>
> I like that idea and I do not necessarily stick to our implementation.
>
> > Most of the use cases are just about
> >
> >> I have this node, please forward all interesting data into this
> >> stream so I can [store|hash|...] it and I [do|don't] care about
> >> having cross-TU stable data and maybe I want to treat special nodes
> >> in a different way
> >
> > so it's not necessarily a difficult problem to solve. If we find a
> > common baseline for this, we could make one visitor that people can
> > specialize their specific hashing needs on top.
>
> Your are right, it is not a difficult problem in the end. But when doing
> It for the whole AST there are some weird corner cases that should be
> handled correctly (recursive type definitions come to my mind)
>
> > I already started doing this for the Stmt hashing when I refactored
> > the StmtDataCollector. I set a common baseline that I could turn my
> > two hashing implementations back then into a single one and I'm aiming
> > at also replacing the Stmt::Profile implementations with it.
> >
> > Not sure if anyone started working on something similar for generic
> > AST nodes (which is probably a bit more complicated than the Stmts
> > which are relatively simple), but maybe we should see if we can get
> > some people together to work on that. Otherwise we will have a dozen
> > hashing implementations in a few years that no one can/will maintain.
>
> Bringing cHash to mainline is based on the wish that I don't want to
> maintain an AST hashing mechanism in parallel to the clang development.
> Therefore, I would love to help with that. We should collect some
> requirements that the different users of unique identifiers have. And
> perhaps we can make them all happy by introducing a few switches to a
> unified visitor.
>
> Some switches and requirements come directly to my mind:
>
> - Syntactical vs. Semantic: There should be a switch to include only
>   nodes that are actually syntacical children of the given node. Not
>   everybody wants to include the transitive hull over all referenced AST
>   nodes.
>
> - Multiple Hashes in one pass: With one pass over the AST I want to have
>   not only one top-level hash, but also hashes of some interesting nodes
>   (top-level definitions, type declarations, global variables). cHash
>   already caches hashes for some nodes in a map to speed things up.
>
> - Debug information: I want to turn on/off the inclusion of debugging
>   information (line numbers, file names, local identifier names).
>
> - Stable?: Should the hash be stable over compiler invocations? Or can
>   we take some shortcuts for types/declarations/things that are not
>   syntactially enclosed into the node.
>
> chris
> --
> Christian Dietrich, M.Sc. (Scientific Staff)
> Institute for Systems Engineering (Systems and Computerarchitecture)
> Leibniz Universität Hannover
> Appelstraße 4
> 30167 Hannover, Germany
>
> Tel:    +49 511 762-19737
> Fax:    +49 511 762-19733
> eMail:  dietrich at sra.uni-hannover.de
> WWW:    https://www.sra.uni-hannover.de
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20171208/62b651b6/attachment.html>