Avoid conversion from `StaticType` to `sema.Type` during runtime sub-type checking

[SupunS]

Issue to be solved

In Interpreter.IsSubType(...) function, both the sub-type and the super-type gets converted from StaticType to sema.Type (see below). This adds an unnecessary overhead.

https://github.com/onflow/cadence/blob/b09231fe0216ecb024fbfc909f213bed53a2d3bb/interpreter/interpreter.go#L4066 https://github.com/onflow/cadence/blob/b09231fe0216ecb024fbfc909f213bed53a2d3bb/interpreter/interpreter.go#L4039

Suggested Solution

Having a separate sub-type checking implementation for runtime (static types) could eliminate this overhead. We could define the sub-typing rules in some declarative format, and then generate the two implementations from that, to make them consistent/in-sync.

[turbolent]

@SupunS Some notes from our discussion yesterday:

• Maybe require explicit ...Type names (e.g. DictionaryType), and don't allow the variant without the Type suffix (e.g. Dictionary) implicitly

Rules file / YAML

• YAML is great it worked well for the compiler/VM instructions DSL

• It allows comments compared to JSON. Not sure if we can parse the comments out of the YAML and generat comments in the generated Go code. If that is not possible, we could maybe store the comments as data in the YAML. E.g.

  - comment: |
    A Go comment
  

• It allows references, "anchors", via & and *. We could use them to break up the larger rules into easier to reason about sub-rules, then combine them to larger rules.

• It might be nice to add a schema for the format, so we can make sure the rules file is valid. Happy to pick this up.

Rollout

• Ideally we finish the code generator so we we can replace the subtyping in the sema package first
• To validate correctness / equivalency we can check:
  • Statically: run both on all contracts and transactions
  • Dynamically: keep existing subtyping code and add new subtyping code. Run both and compare, report if
• Afterwards we can extend it to also generate the subtyping code for static types in the interpreter package
  • Problem: Some information needed for the subtyping rules is not (yet) available in static types
  • First we could just fall back to converting to sema types
  • Later we could materialize the info in static types (maybe as bit flag), but that requires a state migration / spork

[SupunS]

Capturing some more suggestions came up during the PR review:

• [ ] Replace oneOf with or (https://github.com/onflow/cadence/pull/4262#discussion_r2457356952)
• [ ] Split YAML file with anchors (https://github.com/onflow/cadence/pull/4262#discussion_r2457375989)
• [x] Add comments to the YAML file
• [x] Improve error reporting by also printing the path to the location of the error (https://github.com/onflow/cadence/pull/4262#discussion_r2457484188)
• [x] Add more tests to the generated (https://github.com/onflow/cadence/pull/4262#discussion_r2457506158)
• [ ] Review the rules and the generated code for accuracy