canonical type equality constraint (#8445)

Fixes #8439

When checked, generic type equality constraints types are now in a
canonical order, allowing for a commutative type equality operator.

---------

Co-authored-by: Mukund Keshava <mkeshava@nvidia.com>

4 files changed, 114 insertions, 20 deletions

diff --git a/source/core/slang-list.h b/source/core/slang-list.h
index 597f1b9b6..db509d6ba 100644
--- a/source/core/slang-list.h
+++ b/source/core/slang-list.h
@@ -583,7 +583,7 @@ public:
     }
 
     template<typename T2>
-    Index binarySearch(const T2& obj)
+    Index binarySearch(const T2& obj) const
     {
         return binarySearch(
             obj,
diff --git a/source/slang/slang-check-decl.cpp b/source/slang/slang-check-decl.cpp
index d6b50e999..77a799f1c 100644
--- a/source/slang/slang-check-decl.cpp
+++ b/source/slang/slang-check-decl.cpp
@@ -365,9 +365,14 @@ struct SemanticsDeclHeaderVisitor : public SemanticsDeclVisitorBase,
 
     void visitGenericTypeConstraintDecl(GenericTypeConstraintDecl* decl);
 
+    void checkGenericTypeEqualityConstraintSubType(GenericTypeConstraintDecl* decl);
+
     void visitTypeCoercionConstraintDecl(TypeCoercionConstraintDecl* decl);
 
-    void validateGenericConstraintSubType(GenericTypeConstraintDecl* decl, TypeExp type);
+    bool validateGenericConstraintSubType(
+        GenericTypeConstraintDecl* decl,
+        TypeExp type,
+        DiagnosticSink* sink = nullptr);
 
     void checkForwardReferencesInGenericConstraint(GenericTypeConstraintDecl* decl);
 
@@ -3250,10 +3255,25 @@ bool isProperConstraineeType(Type* type)
     return true;
 }
 
-void SemanticsDeclHeaderVisitor::validateGenericConstraintSubType(
+bool SemanticsDeclHeaderVisitor::validateGenericConstraintSubType(
     GenericTypeConstraintDecl* decl,
-    TypeExp type)
+    TypeExp type,
+    DiagnosticSink* sink)
 {
+    auto diagnose = [&]()
+    {
+        if (sink)
+        {
+            if (decl->isEqualityConstraint)
+            {
+                sink->diagnose(type.exp, Diagnostics::invalidEqualityConstraintSubType, type);
+            }
+            else
+            {
+                sink->diagnose(type.exp, Diagnostics::invalidConstraintSubType, type);
+            }
+        }
+    };
     // Validate that the sub type of a constraint is in valid form.
     //
     if (auto subDeclRef = isDeclRefTypeOf<Decl>(type.type))
@@ -3261,7 +3281,7 @@ void SemanticsDeclHeaderVisitor::validateGenericConstraintSubType(
         if (subDeclRef.getDecl()->parentDecl == decl->parentDecl)
         {
             // OK, sub type is one of the generic parameter type.
-            return;
+            return true;
         }
         if (as<GenericDecl>(decl->parentDecl))
         {
@@ -3272,8 +3292,8 @@ void SemanticsDeclHeaderVisitor::validateGenericConstraintSubType(
             auto dependentGeneric = getShared()->getDependentGenericParent(subDeclRef);
             if (dependentGeneric.getDecl() != decl->parentDecl)
             {
-                getSink()->diagnose(type.exp, Diagnostics::invalidConstraintSubType, type);
-                return;
+                diagnose();
+                return false;
             }
         }
         else if (as<AssocTypeDecl>(decl->parentDecl))
@@ -3291,8 +3311,8 @@ void SemanticsDeclHeaderVisitor::validateGenericConstraintSubType(
             auto lookupDeclRef = as<LookupDeclRef>(subDeclRef.declRefBase);
             if (!lookupDeclRef)
             {
-                getSink()->diagnose(type.exp, Diagnostics::invalidConstraintSubType, type);
-                return;
+                diagnose();
+                return false;
             }
 
             // We allow `associatedtype T where This.T : ...`.
@@ -3301,24 +3321,25 @@ void SemanticsDeclHeaderVisitor::validateGenericConstraintSubType(
             //
             if (lookupDeclRef->getDecl()->parentDecl == decl->parentDecl ||
                 lookupDeclRef->getDecl() == decl->parentDecl)
-                return;
+                return true;
             auto baseType = as<Type>(lookupDeclRef->getLookupSource());
             if (!baseType)
             {
-                getSink()->diagnose(type.exp, Diagnostics::invalidConstraintSubType, type);
-                return;
+                diagnose();
+                return false;
             }
             type.type = baseType;
-            validateGenericConstraintSubType(decl, type);
+            return validateGenericConstraintSubType(decl, type, sink);
         }
     }
     if (!isProperConstraineeType(type.type))
     {
         // It is meaningless for certain types to be used in type constraints.
         // For example, `IFoo<T>` should not appear as the left-hand-side of a generic constraint.
-        getSink()->diagnose(type.exp, Diagnostics::invalidConstraintSubType, type);
-        return;
+        diagnose();
+        return false;
     }
+    return true;
 }
 
 // General utility function to collect all referenced declarations from a value
@@ -3443,9 +3464,9 @@ void SemanticsDeclHeaderVisitor::visitGenericTypeConstraintDecl(GenericTypeConst
         // Check for forward references in generic constraints after type translation
         checkForwardReferencesInGenericConstraint(decl);
 
-        validateGenericConstraintSubType(decl, decl->sub);
         if (decl->isEqualityConstraint)
         {
+            checkGenericTypeEqualityConstraintSubType(decl);
             if (!isProperConstraineeType(decl->sup) && !as<ErrorType>(decl->sup.type))
             {
                 getSink()->diagnose(
@@ -3456,6 +3477,7 @@ void SemanticsDeclHeaderVisitor::visitGenericTypeConstraintDecl(GenericTypeConst
         }
         else
         {
+            validateGenericConstraintSubType(decl, decl->sub, getSink());
             if (!isValidGenericConstraintType(decl->sup) && !as<ErrorType>(decl->sup.type))
             {
                 getSink()->diagnose(
@@ -3467,6 +3489,61 @@ void SemanticsDeclHeaderVisitor::visitGenericTypeConstraintDecl(GenericTypeConst
     }
 }
 
+ContainerDecl* findDeclsLowestCommonAncestor(Decl*& a, Decl*& b);
+int compareDecls(Decl* lhs, Decl* rhs);
+
+void SemanticsDeclHeaderVisitor::checkGenericTypeEqualityConstraintSubType(
+    GenericTypeConstraintDecl* decl)
+{
+    auto checkAndCompare = [&]() -> int
+    {
+        bool subOk = validateGenericConstraintSubType(decl, decl->sub);
+        bool supOk = validateGenericConstraintSubType(decl, decl->sup);
+
+        if (subOk != supOk) // Only one is qualified
+        {
+            return int(supOk) - int(subOk);
+        }
+        else if (!(subOk || supOk))
+        {
+            getSink()->diagnose(decl, Diagnostics::noValidEqualityConstraintSubType);
+            // Re-run the validation to emit the diagnostic this time
+            validateGenericConstraintSubType(decl, decl->sub, getSink());
+            validateGenericConstraintSubType(decl, decl->sup, getSink());
+            return -1;
+        }
+        // Both sub and sup are qualified
+        // For example:
+        // __generic <A : IA, B : IB>
+        // where A::T == B::T
+        // Sort them by declaration order in the generic (A > B)
+
+        Decl* subAncestor = as<DeclRefType>(decl->sub.type)->getDeclRef().getDecl();
+        Decl* supAncestor = as<DeclRefType>(decl->sup.type)->getDeclRef().getDecl();
+        auto ancestor = findDeclsLowestCommonAncestor(subAncestor, supAncestor);
+        if (!ancestor)
+        {
+            return compareDecls(subAncestor, supAncestor);
+        }
+
+        auto subIndex = ancestor->getMembers().binarySearch(subAncestor);
+        auto supIndex = ancestor->getMembers().binarySearch(supAncestor);
+
+        return int(supIndex - subIndex);
+    };
+
+    int cmp = checkAndCompare();
+    if (cmp > 0)
+    {
+        Swap(decl->sub, decl->sup);
+    }
+    else if (cmp == 0 && decl->sub != decl->sup)
+    {
+        // The comparison was not fully handled for this case.
+        getSink()->diagnose(decl, Diagnostics::failedEqualityConstraintCanonicalOrder);
+    }
+}
+
 void SemanticsDeclHeaderVisitor::visitGenericTypeParamDecl(GenericTypeParamDecl* decl)
 {
     // TODO: could probably push checking the default value
diff --git a/source/slang/slang-diagnostic-defs.h b/source/slang/slang-diagnostic-defs.h
index 0b7ce6cf0..b1bb22ef3 100644
--- a/source/slang/slang-diagnostic-defs.h
+++ b/source/slang/slang-diagnostic-defs.h
@@ -1691,6 +1691,22 @@ DIAGNOSTIC(
     Error,
     invalidEqualityConstraintSupType,
     "type '$0' is not a proper type to use in a generic equality constraint.")
+DIAGNOSTIC(
+    30405,
+    Error,
+    noValidEqualityConstraintSubType,
+    "generic equality constraint requires at least one operand to be dependant on the generic "
+    "declaration")
+DIAGNOSTIC(
+    30402,
+    Note,
+    invalidEqualityConstraintSubType,
+    "type '$0' cannot be constrained by a type equality")
+DIAGNOSTIC(
+    30407,
+    Warning,
+    failedEqualityConstraintCanonicalOrder,
+    "failed to resolve canonical order of generic equality constraint.")
 
 // 305xx: initializer lists
 DIAGNOSTIC(30500, Error, tooManyInitializers, "too many initializers (expected $0, got $1)")
diff --git a/source/slang/slang-parser.cpp b/source/slang/slang-parser.cpp
index 196b2efa8..eb1671aa7 100644
--- a/source/slang/slang-parser.cpp
+++ b/source/slang/slang-parser.cpp
@@ -1683,13 +1683,14 @@ static void maybeParseGenericConstraints(Parser* parser, ContainerDecl* genericP
         bool optional = AdvanceIf(parser, "optional", &whereToken);
 
         auto subType = parser->ParseTypeExp();
-        if (AdvanceIf(parser, TokenType::Colon))
+        Token constraintToken;
+        if (AdvanceIf(parser, TokenType::Colon, &constraintToken))
         {
             for (;;)
             {
                 auto constraint = parser->astBuilder->create<GenericTypeConstraintDecl>();
                 constraint->whereTokenLoc = whereToken.loc;
-                parser->FillPosition(constraint);
+                constraint->loc = constraintToken.loc;
                 constraint->sub = subType;
                 constraint->sup = parser->ParseTypeExp();
                 if (optional)
@@ -1703,12 +1704,12 @@ static void maybeParseGenericConstraints(Parser* parser, ContainerDecl* genericP
                     break;
             }
         }
-        else if (AdvanceIf(parser, TokenType::OpEql))
+        else if (AdvanceIf(parser, TokenType::OpEql, &constraintToken))
         {
             auto constraint = parser->astBuilder->create<GenericTypeConstraintDecl>();
             constraint->whereTokenLoc = whereToken.loc;
             constraint->isEqualityConstraint = true;
-            parser->FillPosition(constraint);
+            constraint->loc = constraintToken.loc;
             constraint->sub = subType;
             constraint->sup = parser->ParseTypeExp();
             if (optional)