AST nodes should be uniquely identifiable

[viper-admin]

Created by @mschwerhoff on 2018-08-26 09:52
Last updated on 2019-04-30 09:31

Any kind of multi-phase operations on ASTs is difficult to get right because there is no good way of unambiguously identifying AST nodes: AST nodes have no unique ID, and positional information and all other other meta-data is optional.

Consider, for example, the following expression:

b ? e : (b ? e : e)

If an algorithm records, in a first phase, that the second e isn't reachable or that the second b can only evaluate to false, then there isn't a convenient and reliable way of identifying these nodes in a second phase, e.g. during a subsequent expression simplification: built-in AST equality does not discriminate the different instances of b and e, positional information might be missing, and reference equality isn't a good choice either since our AST transformers routinely duplicate nodes.

It would therefore be great if we had a way of reliably identifying AST nodes.

See Silicon issue #261 and Silver issue #94 .

[viper-admin]

@mschwerhoff on 2018-08-26 09:53:

• changed kind from proposal to enhancement

[viper-admin]

@alexanderjsummers commented on 2018-09-13 11:28

Summarising what I said yesterday, I'd be in favour of being able to differentiate "coincidences" in the AST notion of equality, such as occurrences of two separately-declared variables being considered equal. However, I would not be in favour of building a notion of identity into the nodes themselves; I think this would be sensitive to how the AST is created and transformed.

[viper-admin]

@fabiopakk commented on 2019-04-10 09:16

This is related with #231.

[viper-admin]

@fabiopakk commented on 2019-04-30 09:31

Also related with #94.