Repository: hylo-lang/hylo (swift)

Issue:
Fatal error: infinite recursion
Report a diagnostic instead please
```
public trait X {

  type Y: Regular
  fun f() -> Y


}

public trait Z: X {

  type Z: X

}

type A<B: Z> {

  typealias Z = B.Z
  typealias Y = Z.Y

  var c: Y

  fun f() -> Y { c.f() }

}
```

Yields:

/Users/dave/src/hylo/Sources/FrontEnd/TypeChecking/TypeChecker.swift:1820: Fatal error: infinite recursion

With HEAD at 3e6b3f8b

Pull request description:
Fixes #1409

Patch:
diff --git a/Sources/Core/Program.swift b/Sources/Core/Program.swift
index 4f11b59b4..ae5a8b9d4 100644
--- a/Sources/Core/Program.swift
+++ b/Sources/Core/Program.swift
@@ -156,6 +156,42 @@ extension Program {
     AnyDeclID(nodeToScope[s]!)?.isCallable ?? false
   }
 
+  /// Returns `d` and the parameters and explicit captures introduced in the same scope.
+  public func siblings(of d: ParameterDecl.ID) -> [AnyDeclID] {
+    parametersAndCaptures(inBodyOf: AnyDeclID(nodeToScope[d]!)!)
+  }
+
+  /// Returns the parameters and explicit captures introduced in the body of `d`.
+  private func parametersAndCaptures(inBodyOf d: AnyDeclID) -> [AnyDeclID] {
+    let cs: [BindingDecl.ID]
+    let ps: [ParameterDecl.ID]
+
+    switch d.kind {
+    case FunctionDecl.self:
+      let f = FunctionDecl.ID(d)!
+      (cs, ps) = (ast[f].explicitCaptures, ast[f].parameters)
+    case SubscriptDecl.self:
+      let f = SubscriptDecl.ID(d)!
+      (cs, ps) = (ast[f].explicitCaptures, ast[f].parameters)
+    case InitializerDecl.self:
+      (cs, ps) = ([], ast[InitializerDecl.ID(d)!].parameters)
+    case MethodDecl.self:
+      (cs, ps) = ([], ast[MethodDecl.ID(d)!].parameters)
+    case MethodImpl.self, SubscriptImpl.self:
+      return parametersAndCaptures(inBodyOf: AnyDeclID(nodeToScope[d]!)!)
+    default:
+      return []
+    }
+
+    var r = ps.map(AnyDeclID.init(_:))
+    for b in cs {
+      for (_, n) in ast.names(in: ast[b].pattern) {
+        r.append(AnyDeclID(ast[n].decl))
+      }
+    }
+    return r
+  }
+
   /// Returns `true` iff `d` is at module scope.
   public func isAtModuleScope<T: DeclID>(_ d: T) -> Bool {
     switch nodeToScope[d]!.kind {
diff --git a/Sources/FrontEnd/TypeChecking/TypeChecker+Diagnostics.swift b/Sources/FrontEnd/TypeChecking/TypeChecker+Diagnostics.swift
index 48b00a848..94227011f 100644
--- a/Sources/FrontEnd/TypeChecking/TypeChecker+Diagnostics.swift
+++ b/Sources/FrontEnd/TypeChecking/TypeChecker+Diagnostics.swift
@@ -378,6 +378,14 @@ extension Diagnostic {
       notes: ds.map { (d) in .note("'\(n.value)' declared here", at: ast[d].site) })
   }
 
+  static func error(recursiveDefinition d: AnyDeclID, in ast: AST) -> Diagnostic {
+    .error("definition recursively depends on itself", at: ast.siteForDiagnostics(about: d))
+  }
+
+  static func error(referenceToSibling e: NameExpr.ID, in ast: AST) -> Diagnostic {
+    .error("default value cannot refer to a sibling capture or parameter", at: ast[e].site)
+  }
+
   static func warning(needlessImport d: ImportDecl.ID, in ast: AST) -> Diagnostic {
     let s = ast[d].identifier
     return .warning("needless import: source file is part of '\(s.value)'", at: s.site)
diff --git a/Sources/FrontEnd/TypeChecking/TypeChecker.swift b/Sources/FrontEnd/TypeChecking/TypeChecker.swift
index 62fc37b0f..78cce4fb4 100644
--- a/Sources/FrontEnd/TypeChecking/TypeChecker.swift
+++ b/Sources/FrontEnd/TypeChecking/TypeChecker.swift
@@ -1015,6 +1015,13 @@ struct TypeChecker {
     if let e = program[d].defaultValue {
       guard let p = uncheckedType(of: d).errorFree else { return }
       _ = checkedType(of: e, asArgumentTo: ParameterType(p)!)
+
+      var w = RecursiveReferenceRecognizer(
+        targets: program.siblings(of: d), referredDecl: cache.local.referredDecl)
+      program.ast.walk(e, notifying: &w)
+      for r in w.recursiveReferences {
+        report(.error(referenceToSibling: r, in: program.ast))
+      }
     }
   }
 
@@ -2188,8 +2195,12 @@ struct TypeChecker {
   ) -> AnyType {
     // Check for infinite recursion.
     if let t = cache.uncheckedType[d] {
-      guard let u = t.computed else { fatalError("infinite recursion") }
-      return u
+      if let u = t.computed {
+        return u
+      } else {
+        report(.error(recursiveDefinition: AnyDeclID(d), in: program.ast))
+        return .error
+      }
     } else {
       cache.uncheckedType[d] = .inProgress
     }
@@ -4336,8 +4347,6 @@ struct TypeChecker {
       return resolveReceiverMetatype(in: ProductTypeDecl.ID(scopeOfUse)!)
     case TraitDecl.self:
       return resolveReceiverMetatype(in: TraitDecl.ID(scopeOfUse)!)
-    case TypeAliasDecl.self:
-      return resolveReceiverMetatype(in: TypeAliasDecl.ID(scopeOfUse)!)
     case ModuleDecl.self:
       return nil
     default:
@@ -6462,6 +6471,27 @@ struct TypeChecker {
 
 }
 
+/// An AST visitation callback that collects recursive references to specific declarations.
+private struct RecursiveReferenceRecognizer: ASTWalkObserver {
+
+  /// The declarations to consider while looking for cycles.
+  let targets: [AnyDeclID]
+
+  /// A map from name expression to its referred declaration.
+  let referredDecl: BindingMap
+
+  /// The recursive references that have been found.
+  var recursiveReferences: [NameExpr.ID] = []
+
+  mutating func willEnter(_ n: AnyNodeID, in ast: AST) -> Bool {
+    if let e = NameExpr.ID(n), let d = referredDecl[e]?.decl, targets.contains(d) {
+      recursiveReferences.append(e)
+    }
+    return true
+  }
+
+}
+
 extension Program {
 
   /// Returns a reference to `d` as a member of `parent`, specialized by `specialization`, exposed


Test patch:
diff --git a/Tests/HyloTests/TestCases/TypeChecking/RecursiveParameter.hylo b/Tests/HyloTests/TestCases/TypeChecking/RecursiveParameter.hylo
new file mode 100644
index 000000000..304fa3edc
--- /dev/null
+++ b/Tests/HyloTests/TestCases/TypeChecking/RecursiveParameter.hylo
@@ -0,0 +1,12 @@
+//- typeCheck expecting: failure
+
+//! @+3 diagnostic definition recursively depends on itself
+//! @+2 diagnostic undefined name 'x' in this scope
+//! @+1 diagnostic undefined name 'y' in this scope
+fun rec1(x: y, y: x) {}
+
+//! @+1 diagnostic default value cannot refer to a sibling capture or parameter
+fun rec2(x: Int = x, y: Int) {}
+
+//! @+1 diagnostic default value cannot refer to a sibling capture or parameter
+fun rec3[let x = 0](y: Int = x) {}