Repository: hylo-lang/hylo (swift)

Issue:
Monomorphization can't locate default implementations in generic context
This program causes the compiler to crash during monomorphization:

```
public type A: Deinitializable, Strideable {

  public var n: Int

  public memberwise init

  public typealias Stride = Int

  fun offset(to other: Self) -> Stride {
    other.n - self.n
  }

  fun advance(by offset: Stride) -> Self {
    A(n: n + offset)
  }

}

public fun main() {
  let a1 = A(n: 1)
  let a2 = A(n: 2)
  precondition(a1 == a1)
  precondition(a1 != a2) // <- Cause of the crash
  precondition(a1 < a2)
}
```

Replacing `a1 != a2` by `!(a1 == a2)` silences the problem.

Pull request:

Patch:
diff --git a/Sources/Core/AST/Decl/SynthesizedFunctionDecl.swift b/Sources/Core/AST/Decl/SynthesizedFunctionDecl.swift
index 49571bb08..a954a37a3 100644
--- a/Sources/Core/AST/Decl/SynthesizedFunctionDecl.swift
+++ b/Sources/Core/AST/Decl/SynthesizedFunctionDecl.swift
@@ -43,16 +43,20 @@ public struct SynthesizedFunctionDecl: Hashable {
   }
 
   /// The type of the declaration's receiver.
+  ///
+  /// - Requires: `self` is a synthethic implementation of a member function.
   public var receiver: AnyType {
-    // Synthesized are members, so their receiver is part of their captures.
     let r = type.captures[0].type
     return RemoteType(r)?.bareType ?? r
   }
 
   /// Returns the generic parameters of the declaration.
   public var genericParameters: [GenericParameterDecl.ID] {
-    guard !type.captures.isEmpty else { return [] }
-    guard let t = BoundGenericType(receiver) else { return [] }
+    guard
+      !type.captures.isEmpty,
+      let t = BoundGenericType(receiver)
+    else { return [] }
+
     return t.arguments.compactMap { (k, v) -> GenericParameterDecl.ID? in
       if case .type(let u) = v {
         return GenericTypeParameterType(u)?.decl == k ? k : nil
diff --git a/Sources/FrontEnd/Monotonic.swift b/Sources/FrontEnd/Monotonic.swift
index dd07dac5b..9a487421c 100644
--- a/Sources/FrontEnd/Monotonic.swift
+++ b/Sources/FrontEnd/Monotonic.swift
@@ -13,7 +13,9 @@ protocol Monotonic: Equatable {
 extension Monotonic where Self: Equatable {
 
   /// Asserts that `self == other`.
-  func updateMonotonically(_ other: Self) { assert(self == other) }
+  func updateMonotonically(_ other: Self) {
+    assert(self == other, "non-monotonic update of \(type(of: self))")
+  }
 
 }
 
diff --git a/Sources/FrontEnd/TypeChecking/TypeChecker.swift b/Sources/FrontEnd/TypeChecking/TypeChecker.swift
index 44bb29048..0589da3a0 100644
--- a/Sources/FrontEnd/TypeChecking/TypeChecker.swift
+++ b/Sources/FrontEnd/TypeChecking/TypeChecker.swift
@@ -344,18 +344,36 @@ struct TypeChecker {
       let d = AnyDeclID(s)!
       let e = possiblyPartiallyFormedEnvironment(of: d)!
       result.formUnion(e.conformedTraits(of: ^t))
-
-      // Note: `s` might be extending the type whose declaration introduced the generic environment
-      // that declared `t`.
-      if s.kind.value is TypeExtendingDecl.Type {
-        if let g = environment(introducedByDeclOf: uncheckedType(of: d)) {
-          result.formUnion(g.conformedTraits(of: ^t))
-        }
-      }
+      result.formUnion(conformedTraits(declaredByConstraintsOn: t, inScopeExtendedBy: d))
     }
     return result
   }
 
+  /// Returns the traits to which `t` is declared conforming in the scope extended by `d` iff `d`
+  /// is an extension.
+  private mutating func conformedTraits(
+    declaredByConstraintsOn t: AnyType, inScopeExtendedBy d: AnyDeclID
+  ) -> Set<TraitType> {
+    let extendedScope: AnyScopeID?
+
+    switch d.kind {
+    case ConformanceDecl.self:
+      extendedScope = scopeExtended(by: ConformanceDecl.ID(d)!)
+    case ExtensionDecl.self:
+      extendedScope = scopeExtended(by: ExtensionDecl.ID(d)!)
+    default:
+      return []
+    }
+
+    if let s = extendedScope {
+      return conformedTraits(of: t, in: s)
+    } else if let e = environment(introducedByDeclOf: uncheckedType(of: d)) {
+      return e.conformedTraits(of: t)
+    } else {
+      return []
+    }
+  }
+
   /// Returns `true` if `model` is declared conforming to `trait` or if its conformance can be
   /// synthesized in `scopeOfUse`.
   ///
@@ -3960,7 +3978,9 @@ struct TypeChecker {
       // when the associated type is rooted at a trait. Substitution of associated type should
       // rely on conformances rather than lookup.
       if let r = context?.type ?? resolveReceiverMetatype(in: scopeOfUse)?.instance {
-        specialization[program[t.decl].receiver] = .type(r)
+        for u in refinements(of: t).unordered.sorted(by: \.decl.rawValue) {
+          specialization[program[u.decl].receiver] = .type(r)
+        }
       }
     }
 
@@ -4145,8 +4165,7 @@ struct TypeChecker {
     }
   }
 
-  /// Returns the list of generic arguments passed to a symbol occurring in `scope` of use and
-  /// looked up in `context`.
+  /// Returns the generic arguments passed to symbols occurring in `d` and looked up in `context`.
   ///
   /// The arguments of `context` are returned if the latter isn't `nil`. Otherwise, the arguments
   /// captured in the scope introducing `d` are returned in the form of a table mapping accumulated
diff --git a/Sources/FrontEnd/TypedProgram.swift b/Sources/FrontEnd/TypedProgram.swift
index 7f84a72c2..2dd881ac4 100644
--- a/Sources/FrontEnd/TypedProgram.swift
+++ b/Sources/FrontEnd/TypedProgram.swift
@@ -410,11 +410,16 @@ public struct TypedProgram {
   private func impliedConformance(
     of model: AnyType, to concept: TraitType, exposedTo scopeOfUse: AnyScopeID
   ) -> Conformance? {
+    // No implied conformance unless `model` is a generic parameter or associated type.
+    if !(model.base is AssociatedTypeType) && !(model.base is GenericTypeParameterType) {
+      return nil
+    }
+
     var checker = TypeChecker(asContextFor: self)
     let bounds = checker.conformedTraits(
       declaredByConstraintsOn: model,
       exposedTo: scopeOfUse)
-    guard bounds.contains(concept) else { return nil }
+    if !bounds.contains(concept) { return nil }
 
     var implementations = Conformance.ImplementationMap()
     for requirement in ast.requirements(of: concept.decl) {
diff --git a/Sources/IR/Analysis/Module+Depolymorphize.swift b/Sources/IR/Analysis/Module+Depolymorphize.swift
index 79a2f0963..37e93d6cd 100644
--- a/Sources/IR/Analysis/Module+Depolymorphize.swift
+++ b/Sources/IR/Analysis/Module+Depolymorphize.swift
@@ -128,14 +128,6 @@ extension Module {
     _ f: Function.ID, in ir: IR.Program,
     for specialization: GenericArguments, in scopeOfUse: AnyScopeID
   ) -> Function.ID {
-    // TODO: Avoid monomorphizing non-generic entities (#
-    // let parameters = ir.base.liftedGenericParameters(of: f)
-    // if parameters.isEmpty {
-    //   return f
-    // }
-    // let specialization = GenericArguments(
-    //   uniqueKeysWithValues: parameters.map({ ($0, specialization[$0]!) }))
-
     let result = demandMonomorphizedDeclaration(of: f, in: ir, for: specialization, in: scopeOfUse)
     if self[result].entry != nil {
       return result
@@ -535,13 +527,13 @@ extension Module {
       return FunctionReference(to: f, in: self)
     }
 
-    /// Returns a monomorphized copy of `f` specialized by `a` for use in `scopeOfUse`.
+    /// Returns a monomorphized copy of `f` specialized by `z` for use in `scopeOfUse`.
     ///
     /// If `f` is a trait requirement, the result is a monomorphized version of that requirement's
     /// implementation, using `a` to identify the requirement's receiver. Otherwise, the result is
     /// a monomorphized copy of `f`.
-    func rewritten(_ f: Function.ID, specializedBy a: GenericArguments) -> Function.ID {
-      let p = program.specialize(a, for: specialization, in: scopeOfUse)
+    func rewritten(_ f: Function.ID, specializedBy z: GenericArguments) -> Function.ID {
+      let p = program.specialize(z, for: specialization, in: scopeOfUse)
       if let m = program.requirementDeclaring(memberReferredBy: f) {
         return monomorphize(requirement: m.decl, of: m.trait, in: ir, for: p, in: scopeOfUse)
       } else {
@@ -562,21 +554,35 @@ extension Module {
     }
   }
 
-  /// Returns a reference to the monomorphized form of `requirement` for `specialization` in
+  /// Returns a reference to the monomorphized form of `requirement` for specialization `z` in
   /// `scopeOfUse`, reading definitions from `ir`.
   private mutating func monomorphize(
     requirement: AnyDeclID, of trait: TraitType, in ir: IR.Program,
-    for specialization: GenericArguments, in scopeOfUse: AnyScopeID
+    for z: GenericArguments, in scopeOfUse: AnyScopeID
   ) -> Function.ID {
-    let model = specialization[program[trait.decl].receiver]!.asType!
-    let c = program.conformance(of: model, to: trait, exposedTo: scopeOfUse)!
+    let receiver = ir.base[trait.decl].receiver.id
+    let model = z[receiver]!.asType!
+
+    let c = ir.base.conformance(of: model, to: trait, exposedTo: scopeOfUse)!
+    let i = c.implementations[requirement]!
+    let d = demandDeclaration(lowering: i)
 
-    let lowered = demandDeclaration(lowering: c.implementations[requirement]!)
-    if self[lowered].genericParameters.isEmpty {
-      return lowered
+    // Nothing to do if the implementation isn't generic.
+    if self[d].genericParameters.isEmpty {
+      return d
+    }
+
+    // Otherwise, the generic arguments of the implementation are supplied by the conformance,
+    // except for the argument to the receiver parameter. This parameter may be associated with
+    // a trait other the one declaring the requirement if the implementation is in an extension.
+    var monomorphizationArguments = c.arguments
+    if case .concrete(let d) = i, let t = ir.base.traitDeclaring(d), t != trait {
+      monomorphizationArguments[ir.base[t.decl].receiver] = .type(model)
     } else {
-      return monomorphize(lowered, in: ir, for: specialization, in: scopeOfUse)
+      monomorphizationArguments[receiver] = .type(model)
     }
+
+    return monomorphize(d, in: ir, for: monomorphizationArguments, in: scopeOfUse)
   }
 
   /// Returns the IR function monomorphizing `f` for `specialization` in `scopeOfUse`.
@@ -584,11 +590,18 @@ extension Module {
     of f: Function.ID, in ir: IR.Program,
     for specialization: GenericArguments, in scopeOfUse: AnyScopeID
   ) -> Function.ID {
-    let result = Function.ID(monomorphized: f, for: specialization)
-    if functions[result] != nil { return result }
+    let sourceModule = ir.modules[ir.module(defining: f)]!
+    let source = sourceModule[f]
+
+    precondition(!source.genericParameters.isEmpty, "function is not generic")
+    precondition(
+      source.genericParameters.allSatisfy({ specialization[$0] != nil }),
+      "incomplete monomorphization arguments")
 
-    let m = ir.modules[ir.module(defining: f)]!
-    let source = m[f]
+    let result = Function.ID(monomorphized: f, for: specialization)
+    if functions[result] != nil {
+      return result
+    }
 
     let inputs = source.inputs.map { (p) in
       let t = monomorphize(p.type.bareType, for: specialization, in: scopeOfUse)


Test patch:
diff --git a/Tests/LibraryTests/TestCases/StrideableTests.hylo b/Tests/LibraryTests/TestCases/StrideableTests.hylo
index ce1b6ddd5..bf151cd69 100644
--- a/Tests/LibraryTests/TestCases/StrideableTests.hylo
+++ b/Tests/LibraryTests/TestCases/StrideableTests.hylo
@@ -22,6 +22,6 @@ public fun main() {
   let a1 = A(n: 1)
   let a2 = A(n: 2)
   precondition(a1 == a1)
-  precondition(!(a1 == a2))  // See #1269
+  precondition(a1 != a2)
   precondition(a1 < a2)
 }