<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Mon, Dec 11, 2017 at 5:14 AM, Christian Dietrich <span dir="ltr"><<a href="mailto:dietrich@sra.uni-hannover.de" target="_blank">dietrich@sra.uni-hannover.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span>Richard Trieu <<a href="mailto:rtrieu@google.com" target="_blank">rtrieu@google.com</a>> writes:<br>
<br>
> I don't understand your need for pseudrandom identifiers.  If a specific<br>
> type of AST node (for instance, a Decl) is expected, then adding to the<br>
> stream the node kind (like from Decl::getKind()) is enough to avoid<br>
> collisions.  If any node can be expected, then first pass in an enum to<br>
> differentiate the different types (Decl, Stmt, Type, Attr, etc), then add<br>
> the node kind, and then continue on.  Stmt::Profile and ODRHash use this<br>
> method to avoid collisions.  I don't see any gain from using new<br>
> identifiers here.<br>
<br>
</span>Ok, so let's explain a little bit my idea here: Of course, including the<br>
Decl::getKind() also distinguishes node types from each other. However,<br>
these values come from enums and are, therefore, small integers. Small<br>
integers (SI) occur very often in an AST. So, if a sequence of addData()<br>
operations produces the same sequence of SIs because node types are not<br>
distinguishable from SI that occur in the AST, we get a collision[1].<br>
<br></blockquote><div>How does the result of Decl::getKind() being a small integer allows any chance of collision?  I'll admit that arbitrary sub-sequences of different hash streams can be equal, but we shouldn't be hashing sub-sequences.</div><div><br></div><div>Decl</div><div><Decl::getKind()></div><div><br></div><div>Decl with two fields</div><div><Decl::getKind()> <Field 1> < Field 2></div><div><br></div><div>Decl with one sub-Decl</div><div><Decl::getKind()> <Stream of sub-decl></div><div><br></div><div>Decl with arbitrary number of sub-Decl's</div><div><Decl::getKind()> <Number of sub-Decl's> <Stream of sub-decl 1> ... <Stream of sub-decl N></div><div> </div><div>The result of Decl::getKind() will basically specify the format of the hash stream.  I think better controlling of the input stream is a better way of avoiding collisions then using magic numbers as identifiers.</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
We could see the same sequence for different ASTs, if an AST node has a<br>
variable number of children/references. Especially when using the<br>
RecursiveASTVisitor, which reduces the implementation burden of such a<br>
hashing method enormously[2], I'm not 100% sure, that I find all node<br>
types with a variable number of children/references.<br></blockquote><div><br></div><div>Adding the number of children before visiting each child would avoid a collision.</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Introducing 32 Bit of random as an node-type identifier makes the<br>
propability for such a constructive collision much smaller. So it is a<br>
better-safe-than-sorry approach at this point. I also think the enum in<br>
CHashVisitor.h is very very ugly.<br>
<br>
chris<br>
<br>
[1] Sure, we use hashing, so there is always the possibility of hash<br>
    collisions, but we should at least avoid to feed the hash algorithm<br>
    the same sequence for different AST trees.<br>
<br>
[2] By porting[3] CHash to the RecursiveASTVisitor saved about 1200<br>
    lines of code.<br>
<br>
[3] More like throwing away, and building from scratch by using<br>
    fragments of the original code.<br>
<div class="m_-6527040356401607366m_-1099486331382686505HOEnZb"><div class="m_-6527040356401607366m_-1099486331382686505h5">--<br>
Christian Dietrich, M.Sc. (Scientific Staff)<br>
Institute for Systems Engineering (Systems and Computerarchitecture)<br>
Leibniz Universität Hannover<br>
Appelstraße 4<br>
30167 Hannover, Germany<br>
<br>
Tel:    <a href="tel:%2B49%20511%20762-19737" value="+4951176219737" target="_blank">+49 511 762-19737</a><br>
Fax:    <a href="tel:%2B49%20511%20762-19733" value="+4951176219733" target="_blank">+49 511 762-19733</a><br>
eMail:  <a href="mailto:dietrich@sra.uni-hannover.de" target="_blank">dietrich@sra.uni-hanno<wbr>ver.de</a><br>
WWW:    <a href="https://www.sra.uni-hannover.de" rel="noreferrer" target="_blank">https://www.sra.uni-ha<wbr>nnover.de</a><br>
</div></div></blockquote></div><br></div></div>