Support nested generic types (e.g. L<T<S>>)

fixes #325

This commit includes following changes:

1. Including a default DeclaredSubtypeWitness argument when creating a default GenericSubstitution for a DeclRefType, so that the witness argument can be successfully replaced with an actual witness table after specialization. (check,cpp)

2. Not emitting full mangled name for struct field members. Since the declref of the member access instruction do not include necessary generic substitutions for its parent generic parameters, so the mangled names of the declaration site and use site mismatches. Instead we just emit the original name for struct fields. (emit.cpp)

3. Allow IRWitnessTable to represent a generic witness table for generic structs. Adds necessary fields to IRWitnessTable for generic specialization. For now, the user field of the IRUse is not used and is nullptr. (ir-inst.h)

4. Make IRProxyVal use an IRUse instead of an IRValue*, so that an IRValue referenced by IRProxyVal (as a substitution argument) can be managed by the def-use chain for easy replacement. This is used for specializing witness tables. (ir.cpp, ir.h)

5. Add a `String dumpIRFunc(IRFunc*)` function for debugging.

6. Add name mangling for generic / specialized witness tables (mangle.cpp)

7. improved natvis file for inspecting witness tables.

8. Add specialization of witness tables:
   1) `findWitnessTable` will simply return the specialize IRInst for a generic witness table.
   2) make `cloneSubstitutionArg` call `cloneValue` to clone the argument instead of calling `context->maybeCloneValue`, so we can make use of the cloned value lookup machanism to directly return the specialized witness table (which is done when we process the `specialize` instruction on the generic witness table before process the decl ref).
  3) bug fix: the argument in ir.cpp:3338 should be `newArg` instead of `arg`.
  4) add `specializeWitnessTable` function to specailize a generic witness table. It clones the witness table, and recursively calls `getSpecailizedFunc` for the witness table entries.
  5) make `specailizeGenerics` function also handle the case when an operand of the `specialize` instruction is a witness table. We will call `specializeWitnessTable` here and replace the `specialize` instruction with the specialized witness table. The replacement mechanism based on IR def-use chain works here because we have already make IRProxyVal a part of the def-use chain.

9. Add two more test cases for nested generics with constraints. (generic-list.slang and generic-struct-with-constraint.slang)

1 files changed, 139 insertions, 38 deletions

diff --git a/source/slang/ir.cpp b/source/slang/ir.cpp
index cd36e8d47..e0f703cbd 100644
--- a/source/slang/ir.cpp
+++ b/source/slang/ir.cpp
@@ -60,7 +60,8 @@ namespace Slang
         // clear out the old value
         if (usedVal)
         {
-            *prevLink = nextUse;
+            if (prevLink)
+                *prevLink = nextUse;
         }
 
         init(user, usedVal);
@@ -934,6 +935,19 @@ namespace Slang
         return entry;
     }
 
+    IRWitnessTable * IRBuilder::lookupWitnessTable(String mangledName)
+    {
+        IRWitnessTable * result;
+        if (sharedBuilder->witnessTableMap.TryGetValue(mangledName, result))
+            return result;
+        return nullptr;
+    }
+
+
+    void IRBuilder::registerWitnessTable(IRWitnessTable * table)
+    {
+        sharedBuilder->witnessTableMap[table->mangledName] = table;
+    }
 
     IRBlock* IRBuilder::createBlock()
     {
@@ -1396,7 +1410,7 @@ namespace Slang
     struct IRDumpContext
     {
         StringBuilder* builder;
-        int     indent;
+        int     indent = 0;
 
         UInt                        idCounter = 1;
         Dictionary<IRValue*, UInt>  mapValueToID;
@@ -1588,7 +1602,7 @@ namespace Slang
         }
         else if (auto proxyVal = dynamic_cast<IRProxyVal*>(val))
         {
-            dumpOperand(context, proxyVal->inst);
+            dumpOperand(context, proxyVal->inst.usedValue);
         }
         else
         {
@@ -2095,6 +2109,17 @@ namespace Slang
         dump(context, "}\n");
     }
 
+
+    String dumpIRFunc(IRFunc* func)
+    {
+        IRDumpContext dumpContext;
+        StringBuilder sbDump;
+        dumpContext.builder = &sbDump;
+        dumpIRFunc(&dumpContext, func);
+        auto strFunc = sbDump.ToString();
+        return strFunc;
+    }
+
     void dumpIRGlobalVar(
         IRDumpContext*  context,
         IRGlobalVar*    var)
@@ -3199,7 +3224,6 @@ namespace Slang
         case kIROp_Func:
         case kIROp_witness_table:
             return cloneGlobalValue(this, (IRGlobalValue*) originalValue);
-
         case kIROp_boolConst:
             {
                 IRConstant* c = (IRConstant*)originalValue;
@@ -3246,7 +3270,7 @@ namespace Slang
                                 {
                                     auto proxyVal = witness.Value.As<IRProxyVal>();
                                     SLANG_ASSERT(proxyVal);
-                                    return proxyVal->inst;
+                                    return proxyVal->inst.usedValue;
                                 }
                             }
                         }
@@ -3270,16 +3294,20 @@ namespace Slang
         }
     }
 
+    IRValue* cloneValue(
+        IRSpecContextBase*  context,
+        IRValue*        originalValue);
+
     RefPtr<Val> cloneSubstitutionArg(
         IRSpecContext*  context,
         Val*            val)
     {
         if (auto proxyVal = dynamic_cast<IRProxyVal*>(val))
         {
-            auto newIRVal = context->maybeCloneValue(proxyVal->inst);
+            auto newIRVal = cloneValue(context, proxyVal->inst.usedValue);
 
             RefPtr<IRProxyVal> newProxyVal = new IRProxyVal();
-            newProxyVal->inst = newIRVal;
+            newProxyVal->inst.init(nullptr, newIRVal);
             return newProxyVal;
         }
         else if (auto type = dynamic_cast<Type*>(val))
@@ -3307,7 +3335,7 @@ namespace Slang
             for (auto arg : genSubst->args)
             {
                 auto newArg = cloneSubstitutionArg(context, arg);
-                newSubst->args.Add(arg);
+                newSubst->args.Add(newArg);
             }
             return newSubst;
         }
@@ -3436,7 +3464,7 @@ namespace Slang
     }
 
     IRWitnessTable* cloneWitnessTableImpl(
-        IRSpecContext*  context,
+        IRSpecContextBase*  context,
         IRWitnessTable* originalTable,
         IROriginalValuesForClone const& originalValues)
     {
@@ -3445,7 +3473,9 @@ namespace Slang
 
         auto mangledName = originalTable->mangledName;
         clonedTable->mangledName = mangledName;
-
+        clonedTable->genericDecl = originalTable->genericDecl;
+        clonedTable->subTypeDeclRef = originalTable->subTypeDeclRef;
+        clonedTable->supTypeDeclRef = originalTable->supTypeDeclRef;
         cloneDecorations(context, clonedTable, originalTable);
 
         // Clone the entries in the witness table as well
@@ -3463,7 +3493,7 @@ namespace Slang
     }
 
     IRWitnessTable* cloneWitnessTableWithoutRegistering(
-        IRSpecContext*  context,
+        IRSpecContextBase*  context,
         IRWitnessTable* originalTable)
     {
         return cloneWitnessTableImpl(context, originalTable, IROriginalValuesForClone());
@@ -4008,7 +4038,7 @@ namespace Slang
                         SLANG_ASSERT(table);
                         table = cloneWitnessTableWithoutRegistering(context, (IRWitnessTable*)(table));
                         IRProxyVal * tableVal = new IRProxyVal();
-                        tableVal->inst = table;
+                        tableVal->inst.init(nullptr, table);
                         paramSubst->witnessTables.Add(KeyValuePair<RefPtr<Type>, RefPtr<Val>>(subtypeWitness->sup, tableVal));
                     }
                 }
@@ -4228,7 +4258,7 @@ namespace Slang
             // the pointed-to value and not the proxy type-level `Val`
             // instead.
 
-            return context->maybeCloneValue(proxyVal->inst);
+            return context->maybeCloneValue(proxyVal->inst.usedValue);
         }
         else
         {
@@ -4394,6 +4424,69 @@ namespace Slang
         return newSubst;
     }
 
+    IRFunc* getSpecializedFunc(
+        IRSharedGenericSpecContext* sharedContext,
+        IRFunc*                     genericFunc,
+        DeclRef<Decl>               specDeclRef);
+
+    IRWitnessTable* specializeWitnessTable(IRSharedGenericSpecContext * sharedContext, IRWitnessTable* originalTable, DeclRef<Decl> specDeclRef)
+    {
+        // First, we want to see if an existing specialization
+        // has already been made. To do that we will need to
+        // compute the mangled name of the specialized function,
+        // so that we can look for existing declarations.
+        String specMangledName;
+        String specializedMangledName = getMangledNameForConformanceWitness(specDeclRef.Substitute(originalTable->subTypeDeclRef),
+            specDeclRef.Substitute(originalTable->supTypeDeclRef));
+
+        // TODO: This is a terrible linear search, and we should
+        // avoid it by building a dictionary ahead of time,
+        // as is being done for the `IRSpecContext` used above.
+        // We can probalby use the same basic context, actually.
+        auto module = originalTable->parentModule;
+        for (auto gv = module->getFirstGlobalValue(); gv; gv = gv->getNextValue())
+        {
+            if (gv->mangledName == specMangledName)
+                return (IRWitnessTable*)gv;
+        }
+
+        RefPtr<Substitutions> newSubst = cloneSubstitutionsForSpecialization(
+            sharedContext,
+            specDeclRef.substitutions,
+            originalTable->genericDecl);
+
+        IRGenericSpecContext context;
+        context.shared = sharedContext;
+        context.builder = &sharedContext->builderStorage;
+        context.subst = newSubst;
+
+        // TODO: other initialization is needed here...
+
+        auto specTable = cloneWitnessTableWithoutRegistering(&context, originalTable);
+
+        // Set up the clone to recognize that it is no longer generic
+        specTable->mangledName = specMangledName;
+        specTable->genericDecl = nullptr;
+        
+        // Specialization of witness tables should trigger cascading specializations 
+        // of involved functions.
+        for (auto entry : specTable->entries)
+        {
+            if (entry->satisfyingVal.usedValue->op == kIROp_Func)
+            {
+                IRFunc* func = (IRFunc*)entry->satisfyingVal.usedValue;
+                if (func->genericDecl)
+                    entry->satisfyingVal.set(getSpecializedFunc(sharedContext, func, specDeclRef));
+            }
+            
+        }
+        // We also need to make sure that we register this specialized
+        // function under its mangled name, so that later lookup
+        // steps will find it.
+        insertGlobalValueSymbol(sharedContext, specTable);
+
+        return specTable;
+    }
 
     IRFunc* getSpecializedFunc(
         IRSharedGenericSpecContext* sharedContext,
@@ -4415,9 +4508,9 @@ namespace Slang
         // as is being done for the `IRSpecContext` used above.
         // We can probalby use the same basic context, actually.
         auto module = genericFunc->parentModule;
-        for(auto gv = module->getFirstGlobalValue(); gv; gv = gv->getNextValue())
+        for (auto gv = module->getFirstGlobalValue(); gv; gv = gv->getNextValue())
         {
-            if(gv->mangledName == specMangledName)
+            if (gv->mangledName == specMangledName)
                 return (IRFunc*) gv;
         }
 
@@ -4564,7 +4657,7 @@ namespace Slang
             // specialization to perform.
             auto func = workList[count-1];
             workList.RemoveAt(count-1);
-
+            
             // We are going to go ahead and walk through
             // all the instructions in this function,
             // and look for `specialize` operations.
@@ -4596,32 +4689,40 @@ namespace Slang
                             // specialization here and now.
                             IRSpecialize* specInst = (IRSpecialize*) ii;
 
-                            // We need to check that the value being specialized is
-                            // a generic function.
-                            auto genericVal = specInst->genericVal.usedValue;
-                            if(genericVal->op != kIROp_Func)
-                                continue;
-                            auto genericFunc = (IRFunc*) genericVal;
-                            if(!genericFunc->genericDecl)
-                                continue;
-
                             // Now we extract the specialized decl-ref that will
                             // tell us how to specialize things.
-                            auto specDeclRefVal = (IRDeclRef*) specInst->specDeclRefVal.usedValue;
+                            auto specDeclRefVal = (IRDeclRef*)specInst->specDeclRefVal.usedValue;
                             auto specDeclRef = specDeclRefVal->declRef;
 
-                            // Okay, we have a candidate for specialization here.
-                            //
-                            // We will first find or construct a specialized version
-                            // of the callee funciton/
-                            auto specFunc = getSpecializedFunc(sharedContext, genericFunc, specDeclRef);
-                            //
-                            // Then we will replace the use sites for the `specialize`
-                            // instruction with uses of the specialized function.
-                            //
-                            specInst->replaceUsesWith(specFunc);
-
-                            specInst->removeAndDeallocate();
+                            // We need to specialize functions and witness tables
+                            auto genericVal = specInst->genericVal.usedValue;
+                            if (genericVal->op == kIROp_Func)
+                            {
+                                auto genericFunc = (IRFunc*)genericVal;
+                                if (!genericFunc->genericDecl)
+                                    continue;
+
+                                // Okay, we have a candidate for specialization here.
+                                //
+                                // We will first find or construct a specialized version
+                                // of the callee funciton/
+                                auto specFunc = getSpecializedFunc(sharedContext, genericFunc, specDeclRef);
+                                //
+                                // Then we will replace the use sites for the `specialize`
+                                // instruction with uses of the specialized function.
+                                //
+                                specInst->replaceUsesWith(specFunc);
+
+                                specInst->removeAndDeallocate();
+                            }
+                            else if (genericVal->op == kIROp_witness_table)
+                            {
+                                // specialize a witness table
+                                auto originalTable = (IRWitnessTable*)genericVal;
+                                auto specWitnessTable = specializeWitnessTable(sharedContext, originalTable, specDeclRef); 
+                                specInst->replaceUsesWith(specWitnessTable);
+                                specInst->removeAndDeallocate();
+                            }
                         }
                         break;