Interpreter falsely reports "Undeclared type" during import

[toinehartman]

Describe the bug

On typepal 0.15.3, importing analysis::typepal::Collector results in the interpreter reporting an undeclared type Use in analysis::typepal::StringSimilarity. The typechecker does not.

Use (from analysis::typepal::TModel) should be available:

• module analysis::typepal::StringSimilarity
• imports analysis::typepal::ConfigurableScopeGraph; (notably is in a cycle with analysis::typepal::StringSimilarity)
• extends analysis::typepal::ISolver
• extends analysis::typepal::AType
• extends anaysis::typepal::TModel which defines data Use

Importing analysis::typepal::StringSimilarity first and analysis::typepal::Collector after does not trigger the error.

To Reproduce

Steps to reproduce the behavior:

1. Install vsix
2. Open typepal on commit usethesource/typepal@241ba7e
3. Open analysis::typepal::Collector
4. Click inlay hint Import in new Rascal terminal

Expected behavior
No error.

Stack traces

Literally copy stacktraces from the console, or from the Eclipse Error log here.

Desktop (please complete the following information):
VSCode REPL
Path config:

[INFO] pom.xml: Rascal version is 0.41.0
[INFO] pom.xml: Project root is |file:///C:/Users/toine/swat/projects/Rascal/typepal/|
[INFO] pom.xml: Bin folder   is |file:///C:/Users/toine/swat/projects/Rascal/typepal/target/classes|
[INFO] pom.xml: Source module path is:
  - |std:///|
  - |file:///C:/Users/toine/swat/projects/Rascal/typepal/src|
  - |jar+file:///C:/Users/toine/.vscode/extensions/usethesource.rascalmpl-0.13.0-head3138/assets/jars/rascal-lsp.jar!/library|
[INFO] pom.xml: Library module (and classes) path is:
  - |file:///C:/Users/toine/.vscode/extensions/usethesource.rascalmpl-0.13.0-head3138/assets/jars/rascal.jar|
  - |mvn://junit--junit--4.13.1|
  - |mvn://org.hamcrest--hamcrest-core--1.3|
  - |file:///C:/Users/toine/.vscode/extensions/usethesource.rascalmpl-0.13.0-head3138/assets/jars/rascal-lsp.jar|

[jurgenvinju]

reproduced with:

1. cd typepal
2. mvn rascal:console or java -jar /Users/jurgenv/.m2/repository/org/rascalmpl/rascal/0.41.0/rascal-0.41.0.jar
3. import analysis::typepal::Collector;

[jurgenvinju]

Comparing the two (very) clear scenarios described by @toinehartman. Especially focusing on the import cycle that was observed. Sherlock Holmes is proud :-)

Starting with the second scenario which does not fail:

1. We start with importing StringSimilarity
2. which imports ConfigurableScopeGraph
3. which extends down to TModel which defines Use
4. and ConfigurableScopeGraph imports StringSimilarity, and that's fine.
5. ConfigurableScopeGraph ends up being fully initialized and extended
6. StringSimilarity pops back and we finish initializing it.

The StringSimilarity module has access to the contents of the ConfigurableScope module after everything has been extended into it (via bottom-up recursion of the import/extend graph), including the definition of Use. It then continues to declare its own local functions and types, and finds Use where it is supposed to be.

Continuing with the first scenario, we end up in the fail case (maybe) because:

1. Now ConfigurableScopeGraph is the first to be imported.
2. It imports StringSimilarity, probably before extending the other modules.
3. The import/extend stack is depth-first, so now StringSimilarity imports ConfigurableScopeGraph back again, but it is already on the import/extend stack so it is not processed again.
4. StringSimilarity proceeds initializing other stuff before ConfigurableScopeGraph has been fully extended. And this initialization code requires a definition of Use which is not there.

The unexpected part of this is that this specific fail scenario was catered for in the design of Import and Extend and the declaration of local types. If there are cyclic dependencies, then the code is supposed to try and define as many types as possible already (for example by declaring the data X type but not yet the constructors, and aliases unless they fail due to a cyclic dependency, etc.). After this initial round, and when all imports and extends have finished, the code revisits these declarations and now runs the full declaration (hopefully getting enough partial definitions from the other side to complete).

However; this looks more like a case of importing an incomplete module. The parent module ConfigurableScopeGraph is simply not complete yet while StringSimilarity is already initializing its contents for the second time. The two-stage initialization mechanism only includes the local definitions of both modules in the first stage, but not those of the extended modules. Hence it is incomplete in resolving cyclic dependencies which only arise from definitions buried under extend.

[jurgenvinju]

This happens before importing or extending anything:

rascal/src/org/rascalmpl/semantics/dynamic/Import.java

Line 474 in 9603cc7

declareTypesWhichDoNotNeedImportedModulesAlready(eval, env, top);

And then here via buildModule and loadModule higher up the call stack, everything is declared again:

rascal/src/org/rascalmpl/semantics/dynamic/Import.java

Line 357 in 9603cc7

module.interpret(eval);

[jurgenvinju]

• Note that @PaulKlint has added a number of data X; definitions in the top of the import/extend graph of the rascal checker and typepal to avoid similar UndeclaredType errors in the past. Also @PaulKlint changed the order of extend and import to avoid the broken behavior. This adds to the evidence that we are on the right track here.
• The recent changes in module load semantics have an effect on typical module load order, especially in the presence of static errors and import cycles. This explains why new instances of UndeclaredType can arise which were not present in the previous version of rascal. Changing the import/extend order in a module can have a similar effect. Note that the import and extend order is supposed to be semantically irrelevant.
• The subject Rascal code is notably not broken here. It really is the interpreter's initialization semantics in the presence of (correct) import cycles with extend in one or more of the cycle participants. The import cycle must not only exist, also at least one of the extended modules should contain a type definition that is used in a type definition of another module in the cycle.

[jurgenvinju]

Solution direction. Given the following assertions:

• extend is transitive, but not cyclic (erroneous cycles are detected early and stop further processing)
• import is not transitive, but may be cyclic
• an import of a module which is extending the current module (transitively or directly) is not allowed (is also detected early)
• the execution order of import and extend evaluation is left to the implementation of Rascal and offers no other guarentees than correct initialization in the presence of the above.

With this in mind, the following order of initialization solves the current problem:

1. when a module is being loaded, first process all extend declarations, depth-first in the extend graph. This process detects illegal cycles
2. after the extends are finished executing, all transitive definitions are present in the current module.
3. now we execute the early type declarations of stage 1 via declareTypesWhichDoNotNeedImportedModulesAlready
4. we can then do a depth-first loading of imported modules.
5. finally we can initialize the declarations of the module.

In short: extends first. It solves the scenario above since ConfigurableScopeGraph will be complete including the definition of Use before we even start to import the offending StringSimilarity. When that module needs the definitions imported via ConfigurableScopeGraph, Use will already be there. Even types introduced in ConfigurableScopeGraph will already be there due to step 3. Because import is not transitive, it does not matter that the imports of ConfigurableScopeGraph have not all finished yet; their types are not accessible anyway.

WDYT? The question is if this goes right by induction through the depth-first exploration of extend or not? After all, extended modules will also import stuff... This could go wrong if an import goes up the extend dependency stack, but exactly that case is dissallowed by the third assertion above. Let's think about this a bit.

It's interesting that this solution needs all the details of the exclusive semantics between import and extend {transitivity x cyclicity}^2