[flang] Handle forward references to modules

[klausler]

Summary

When a USE of a module precedes its definition in the same source
file, ensure that the module is processed by name resolution before
the USE statement. This prevents the risk of the USE statement using
an obsolete module file that is later overwritten during the same
compilation.

flang/docs/Extensions.md

* In the definition of the `ASSOCIATED` intrinsic function (16.9.16), its optional
   left-hand side for a pointer assignment statement -- in particular, it
   cannot be `NULL()`, but also it is required to be modifiable.
   As there is  no good reason to disallow (say) an `INTENT(IN)` pointer here,
   or even `NULL()` as a well-defined case that is always `.FALSE.`,
   this compiler doesn't require the `POINTER=` argument to be a valid
   left-hand side for a pointer assignment statement, and we emit a
   portability warning when it is not.
 
+* F18 allows a `USE` statement to reference a module that is defined later
+  in the same compilation unit, so long as mutual dependencies do not form
+  a cycle.
+  This feature forestalls any risk of such a `USE` statement reading an
+  obsolete module file from a previous compilation and then overwriting
+  that file later.
+
 ## De Facto Standard Features
 
 * `EXTENDS_TYPE_OF()` returns `.TRUE.` if both of its arguments have the
   same type, a case that is technically implementation-defined.

flang/lib/Semantics/resolve-names.cpp

public:
 
   Scope &topScope() const { return topScope_; }
 
   // Default action for a parse tree node is to visit children.
   template <typename T> bool Pre(const T &) { return true; }
   template <typename T> void Post(const T &) {}
 
   bool Pre(const parser::SpecificationPart &);
+  bool Pre(const parser::Program &);
   void Post(const parser::Program &);
   bool Pre(const parser::ImplicitStmt &);
   void Post(const parser::PointerObject &);
   void Post(const parser::AllocateObject &);
   bool Pre(const parser::PointerAssignmentStmt &);
   void Post(const parser::Designator &);
   void Post(const parser::SubstringInquiry &);
   template <typename A, typename B>
bool ResolveNamesVisitor::Pre(const parser::ProgramUnit &x) {
   ResolveSpecificationParts(root);
   FinishSpecificationParts(root);
   ResolveExecutionParts(root);
   ResolveAccParts(context(), x);
   ResolveOmpParts(context(), x);
   return false;
 }
 
+template <typename A> std::set<SourceName> GetUses(const A &x) {
+  std::set<SourceName> uses;
+  if constexpr (!std::is_same_v<A, parser::CompilerDirective>) {
+    const auto &spec{std::get<parser::SpecificationPart>(x.t)};
+    const auto &unitUses{std::get<
+        std::list<parser::Statement<common::Indirection<parser::UseStmt>>>>(
+        spec.t)};
+    for (const auto &u : unitUses) {
+      uses.insert(u.statement.value().moduleName.source);
+    }
+  }
+  return uses;
+}
+
+bool ResolveNamesVisitor::Pre(const parser::Program &x) {
+  std::map<SourceName, const parser::ProgramUnit *> modules;
+  std::set<SourceName> uses;
+  bool disordered{false};
+  for (const auto &progUnit : x.v) {
+    if (const auto *indMod{
+            std::get_if<common::Indirection<parser::Module>>(&progUnit.u)}) {
+      const parser::Module &mod{indMod->value()};
+      const auto &moduleStmt{
+          std::get<parser::Statement<parser::ModuleStmt>>(mod.t)};
+      const SourceName &name{moduleStmt.statement.v.source};
+      if (auto iter{modules.find(name)}; iter != modules.end()) {
+        Say(name,
+            "Module '%s' appears multiple times in a compilation unit"_err_en_US)
+            .Attach(iter->first, "First definition of module"_en_US);
+        return true;
+      }
+      modules.emplace(name, &progUnit);
+      if (auto iter{uses.find(name)}; iter != uses.end()) {
+        Say(name,
+            "A USE statement referencing module '%s' appears earlier in this compilation unit"_port_en_US)
+            .Attach(*iter, "First USE of module"_en_US);
+        disordered = true;
+      }
+    }
+    for (SourceName used : common::visit(
+             [](const auto &indUnit) { return GetUses(indUnit.value()); },
+             progUnit.u)) {
+      uses.insert(used);
+    }
+  }
+  if (!disordered) {
+    return true;
+  }
+  // Process modules in topological order
+  std::vector<const parser::ProgramUnit *> moduleOrder;
+  while (!modules.empty()) {
+    bool ok;
+    for (const auto &pair : modules) {
+      const SourceName &name{pair.first};
+      const parser::ProgramUnit &progUnit{*pair.second};
+      const parser::Module &m{
+          std::get<common::Indirection<parser::Module>>(progUnit.u).value()};
+      ok = true;
+      for (const SourceName &use : GetUses(m)) {
+        if (modules.find(use) != modules.end()) {
+          ok = false;
+          break;
+        }
+      }
+      if (ok) {
+        moduleOrder.push_back(&progUnit);
+        modules.erase(name);
+        break;
+      }
+    }
+    if (!ok) {
+      parser::Message *msg{nullptr};
+      for (const auto &pair : modules) {
+        if (msg) {
+          msg->Attach(pair.first, "Module in a cycle"_en_US);
+        } else {
+          msg = &Say(pair.first,
+              "Some modules in this compilation unit form one or more cycles of dependence"_err_en_US);
+        }
+      }
+      return false;
+    }
+  }
+  // Modules can be ordered.  Process them first, and then all of the other
+  // program units.
+  for (const parser::ProgramUnit *progUnit : moduleOrder) {
+    Walk(*progUnit);
+  }
+  for (const auto &progUnit : x.v) {
+    if (!std::get_if<common::Indirection<parser::Module>>(&progUnit.u)) {
+      Walk(progUnit);
+    }
+  }
+  return false;
+}
+
 // References to procedures need to record that their symbols are known
 // to be procedures, so that they don't get converted to objects by default.
 class ExecutionPartSkimmer {
 public:
   explicit ExecutionPartSkimmer(ResolveNamesVisitor &resolver)
       : resolver_{resolver} {}
 
   void Walk(const parser::ExecutionPart *exec) {

flang/test/Semantics/modfile53.f90

+! RUN: %python %S/test_modfile.py %s %flang_fc1
+! Ensure that a module can be forward-referenced within a compilation unit.
+module m1
+  use m2
+end
+
+module m2
+  use m3
+end
+
+module m3
+  integer n
+end
+
+!Expect: m1.mod
+!module m1
+!use m2,only:n
+!end
+
+!Expect: m2.mod
+!module m2
+!use m3,only:n
+!end
+
+!Expect: m3.mod
+!module m3
+!integer(4)::n
+!end

flang/test/Semantics/modfile54.f90

+! RUN: %python %S/test_errors.py %s %flang_fc1
+!ERROR: Some modules in this compilation unit form one or more cycles of dependence
+module m1
+  use m2
+end
+
+!PORTABILITY: A USE statement referencing module 'm2' appears earlier in this compilation unit
+module m2
+  use m3
+end
+
+!PORTABILITY: A USE statement referencing module 'm3' appears earlier in this compilation unit
+module m3
+  use m1
+end