Unique identifier for each node in the IR

[AttilaMihaly]

A common requirement that comes up in various discussions is the ability to associate extra information to various nodes in the IR. While the IR itself allows us to assign extra attributes to each type and value nodes it is not always desirable to add all information directly in the IR. An alternative approach is to have a unique identifier for each node and use that to associate arbitrary information to each node in external dictionaries.

Types and values defined on a module level have a trivial unique identifier (the fully-qualified name) but nodes on the right-hand side cannot be directly addressed by default. A simple solution to the problem is to address nodes using an integer index following a well-defined traversal of the expression tree. In fact we already implemented the functionality for values here.

Based on the above it would be relatively easy to com up with a standard and implementation to get a unique identifier for any node in the IR. This can then be used to associate and look up arbitrary information related to the IR. Example uses would be:

• Fine-grained documentation.
• Links to source documents such as regulatory documentation.
• Associating source location to each node in the IR.
• Adding type information to each value.

[DamianReeves]

This sounds great and very useful. I can imagine particularly the module level unique Ids as a good place to store hashes to help in identifying what parts of models have changed in an easy manner.

[AttilaMihaly]

My latest thought on this is that for identifying specific nodes in a value or type expression tree a single index might not be efficient. While it is space efficient it makes it difficult to assign IDs to nodes and also finding nodes by ID. We could use a sequence of integers instead which describe the path to get to the specific node. Every node in expression trees already has a predictable ordering for its children so this should be easy to implement in both directions.

[AttilaMihaly]

For example, given this code:

a + b

Which translates to this Morphir IR (with some simplification):

Apply
    (Apply 
        (Reference "add")
        (Variable "a")
    )
    (Variable "b")

The id for each node would be the following:

• add: [ 0, 0 ]
• a: [ 0, 1 ]
• b: [ 1 ]