Unable to Resolve Methods on User-Defined Types

[sylwiabr]

@sylwiabr commented on Fri Apr 09 2021

What did you do?

opened project:

from Standard.Base import all
import Standard.Base.Math

type Shape
    type Circle r
    type Square a

    surface = case this of
        Circle r -> Math.pi * r ^ 2
        Square a -> a ^ 2

main =
    c = Circle 12
    f = c.surface

then added a node Square 2 and another one connected with itsurface

What did you expect to see?

both surfaces calculated

What did you see instead?

Enso Version

Frontend: Version: 1.0.0 Build: 9b1e455 Electron: 11.1.1 Chrome: 87.0.4280.88

Backend: Enso Project Manager Version: 0.2.10 Built with: scala-2.13.5 for GraalVM 21.0.0.2 Built from: enso-0.2.10 @ cd1ad23d392cb7d6380c27f676dd8448f7df8827 Built on: Mac OS X (amd64)

Additional notes

I can change value on node with Circle but if I put another surface method connected to it it is returning the same error

[4e6]

The method resolution fails when the value of an atom, i.e. Circle 12 is obtained from the cache and not evaluated. Apparently, evaluation changes the runtime state affecting the method resolution on other nodes.

[4e6]

Update. AtomConstructor when evaluated, registers its methods in the scope. The fix would be to generate methods defined on atoms during the IrToTruffle compilation step.

[4e6]

Update 2 Cached Atom carries its own scope. Scope stores methods in a hashmap with an AtomConstructor key. The lookup fails to find an AtomConstructor because the map contains an atom constructor from the previous compilation (the lookup is reference-based)

[iamrecursion]

This is my analysis of the problem from when I was looking into it in May.

Investigation

• When a module is replaced, EnsureCompiledJob is responsible for recompiling it. EnsureCompiledJob::ensureCompiledModule and EnsureCompiledJob::ensureCompiledScope both call into EnsureCompiledJob::compile which executes Module::compileScope directly. ensureCompiledModule calls it twice due to the need to ensure there's an IR for cache invalidation, but this isn't directly related to the problem.
• Module::compileScope will compile the module if it isn't AFTER_CODEGEN, calling Module::compile.
• Module::compile will call ModuleScope::reset, which involves clearing out all the registrations, including the methods. It also sets the module's compilation stage back to INITIAL.
• This then executes compiler::run on the Module.

Interestingly enough, the module handle appears to be the same at every point in the above chain, so far. The issue, however, occurs in the next phase as the compiler performs stub generation (which involves regenerating atom constructors anew).

• Compiler::run executes RuntimeStubsGenerator::generate, which creates a new AtomConstructor for each atom in the module. These are then registered using ModuleScope::registerConstructor.
• These new AtomConstructor instances are distinctly not the same ones as those associated with cached atoms, which means that at method lookup time we fetch the old AtomConstructor and try to look up methods for it in the scope, which no longer exist.
• We get to runtime and the methods are defined on the new AtomConstructor instances. This means that the method map for the provided key is empty, and we can't resolve methods on it.
• We find no methods and the method lookup fails.

Potential Solutions

The following are potential solutions to the issue that may not necessarily work.

AtomConstructor Replacement in the Cache

An initial thought of mine was that we could replace the scopes for relevant atoms in the cache, but this has two main issues:

1. All cache entries are stored as opaque Objects. Whilst we can do a pattern match and replacement if the entry is an Atom, we then run into the second issue.
2. Types that have their scopes invalidated may occur inside other scopes, meaning that the replacement process would have to traverse potentially the entire cached object graph. This would be far too expensive to perform.

AtomConstructor Reuse

The ideal solution would be to reuse the existing AtomConstructor instances rather than generating them anew. From a first glance this has a few problems:

• If the type definition is deleted then we have no way of retaining the constructor information in the module, and hence cannot dispatch methods on cached values.
• Even if we re-use the constructor for the same type, the type can undergo edits such as addition or removal of fields that would invalidate the constructor. While this isn't an issue for method dispatch (as we only care about the existence of a value with a certain constructor), the method definitions themselves may be changed and rely on the new structure of the atom. Hence calling the method can lead to a runtime error that (as far as the user is concerned) is spurious.
• We still need a way to invalidate the cache reliably when doing it. This may, unfortunately, be as simple as clearing the entire cache when a type is changed.

Perhaps, if there was a way to retain information on which AtomConstructors were alive this would be better, but that would involve deep analysis of the cache, which is likely too expensive to perform in general.

Wholesale Cache Eviction

Unfortunately the only truly semantically correct solution may be to clear the cache when any module imported into the current module is changed in a way that changes the types it defines. This is a very heavyweight solution, however, and I would much prefer to find something more reliable. Fundamentally, however, we run into the following issues with any partial solution:

• Reusing or updating constructor registrations is only valid for as long as the type definition itself doesn't change. If the name changes, the number of fields change, etc, the best we can do is start over.
• Addition of a method could be handled without evicting cache entries, but would be non-trivial to do so.
• Trying to work out which cache entries need to be cleared on changes to a type is intractable. Even if we had perfectly granular type information about Enso, we can never have the same information about interop values. This means that once we hand off an Enso value of type Foo to a different language and a value containing that gets cached, we will never know to evict it if Foo changes.

This means that the only semantically correct full solution is one that does the following:

• Tracks changes to types in the graph of modules imported into the module(s) where caching is enabled.
• Changes that can be updated in place (such as additions, modifications, and removals of methods) should be updated in place, reusing AtomConstructor instances for registration where possible.
• When a change is made that is not able to be updated in place, we have to evict the entire cache to ensure that the language is semantically correct.

I'm not sure we can even do better in the future.

• If we extend dataflow analysis to perform whole-program analysis we can track where a given type is used. Having information as to where a given type is used allows us to globally invalidate its usage sites except through dynamic dispatch.
• As dynamic dispatch is pervasive in Enso, we can't globally determine which CallTarget will be executed for a given method invocation. This means that we can never conclusively and coherently invalidate the correct cache entries. Due to circular imports, a method may create a value of the type that later needs to be invalidated without us ever knowing.
• Though, in the far future, a type checker and whole-program analyses would allow us to determine the possible set of CallTargets in Enso code that could be hit during a given resolution, we can't do anything when it comes to polyglot. A polyglot call could add or remove a method from an object which means we can't properly validate any type returned from polyglot.