Implement StaticType() for arrays and dictionaries

[SupunS]

Issue To Be Solved

getType() function on containers (arrays. dictionaries), returns no type information.
e.g:

var array : [Int] = [1, 3]

log(array.getType())

Actual output: Type()

Expected Output: Type([Int])

Solution

• Checker: Record static types for array expressions and dictionary expressions in elaboration
  @turbolent
  Add static types to array values and dictionary values #1034
• Interpreter:
  @turbolent
  Add static types to array values and dictionary values #1034
  • Add static type field to array values and dictionary values
  • Implement StaticType() for arrays and dictionaries
  • Add static type information when evaluation array expressions and dictionary expressions (use elaboration)
• Add function to walk value
  @turbolent
  Add walker for values #1037
• Encoding and decoding
  • This requires a storage format change
  • Add new encoder/decoder version
    @SupunS
    Add encoder/decoder v5 #1039
  • Store static types
    @SupunS
    Add encoding/decoding for array value static type #1035
  • Read static types
    @SupunS
    Add encoding/decoding dictionary static type info #1036
  • Ensure existing stored data can be decoded using the old decoder and re-encoding using the new encoder: Arrays and dictionaries are first deferred and need to be forced to be decoded, and the new decoding functions for deferred arrays and dictionaries need to delegate to the old deferred decoding functions. + Tests
    @SupunS
    Finish storage format changes #1042
    Add tests for decoding from old format and encoding in new format #1046
  • Storage migration. Infer static types from stored values, by walking decoded value object graph (see item "Add function to walk value" above)
    @turbolent
    • Similar to https://github.com/onflow/flow-go/blob/master/cmd/util/ledger/migrations/storage_v4.go
    • Handle deferred values
    • Migrate values even when type information is unavailable
    • Delete values that don't have type information
    • Generate report for deleted data
• Import and export
  • Add array type to imported array value and dictionary value
    @turbolent
    Add static types to array values and dictionary values #1034
  • Add static type to imported array values and dictionary values using target parameter type
    @turbolent
    Infer array and dictionary static types from expected type during import #1038
  • Infer type from the value when parameter/target type is not specific enough (e.g: target type has AnyStruct and the value is [3, 5, 2]). Could make use of: Find least common super-type #1025, by getting static type of each element -> convert to sema type -> find super type -> convert back to static type.
    @SupunS
    Short-term solution: Infer static-type from imported array/dictionary values #1052
    Long-term solution: Infer static type from the value itself for imported arrays/dictionaries #1049
• Dynamic types: Add static types to array values and dictionary values
  @turbolent
  Include and consider static types of arrays and dictionaries #1043
• Dynamic subtype check: Consider the array's / dictionary's static type.
  @turbolent
  Include and consider static types of arrays and dictionaries #1043
• Update ConformsToDynamicType: Consider dynamic array type's / dynamic dictionary type's static type
  @SupunS
  Seems redundant. Added tests: Add more tests for imported array/dictionary value type conformance #1045

Concerns

• Q: How do we maintain backward compatibility as discussed in Get the run-time type of an object #195?
  A: We will infer static types for existing stored data and migrate it

Related Issues

#748

[turbolent]

Thank you for creating this issue @SupunS. This was a known limitation of the initial implementation, see the discussion here: #195 (comment).

Container values currently don't have knowledge about their static type. This could be added, but is still missing in already stored values and could not easily be added for old values.
Still, I think we could add it for new values.

[turbolent]

Storage migration in flow-go is here: https://github.com/onflow/flow-go/compare/bastian/cadence-storage-v5

It can be run using e.g.:

go run ./cmd/util execution-state-extract --execution-state-dir devnet23 --output-dir devnet23-out

[SupunS]

Reopening because we still need to do the storage migration.

[SupunS]

Migration added: onflow/flow-go#1264