AST Comparison API

[jubnzv]

We need an API that provides a way to compare any Tact AST:

• AstComparator:
  • Provide an API to check AST equivalence without renaming
• AstHasher: Write the hashing module that doesn't take names into account
• AstRenamer: Canonicalize binder names introducing something like de Bruijn indices
  • Rename elements
    • Top-level/contract/trait entries
    • Native functions: rename to match their original names.
    • Struct/message/contract fields
    • Function arguments
  • Handle dependencies
    • Build dependency graphs for the AST entries. This is required to rename and sort them properly. (TODO: create a separate module for this?)
    • Provide topological sort of the renamed entries. We have to write additional logic to handle mutually recursive function calls.
  • Rename uses of renamed elements in the source code
    • Struct/contract initializers
    • Function/method calls
    • Function arguments
    • Implemented traits in traits/contracts
    • Fields (it will be easier when introducing types in AST Tact frontend API: Improvements for tooling #314)
• AstSorter: Improve the sorting routines
  • Lexicographically sort top-level entries
  • Imports
  • Function/constant/trait/contract attributes
• Compare ASTs after partial evaluation

[anton-trunov]

Would be nice to have those bullet points in the OP configurable

[anton-trunov]

A couple more things regarding order-independence of things:

• the order of function parameters can be irrelevant (provided the same shuffling has been done at all the call sites as well)
• the order of fields in structs can be irrelevant.

But, the above two cases can result in different gas consumption! So we cannot really ignore order for the above two cases.