Shader cache index implementation (#2452)

12 files changed, 146 insertions, 137 deletions

diff --git a/source/compiler-core/slang-dxc-compiler.cpp b/source/compiler-core/slang-dxc-compiler.cpp
index 52933eaa7..06dfc74b0 100644
--- a/source/compiler-core/slang-dxc-compiler.cpp
+++ b/source/compiler-core/slang-dxc-compiler.cpp
@@ -14,7 +14,7 @@
 #include "../core/slang-semantic-version.h"
 #include "../core/slang-char-util.h"
 
-#include "../core/slang-digest.h"
+#include "../core/slang-digest-builder.h"
 
 #include "slang-include-system.h"
 #include "slang-source-loc.h"
diff --git a/source/compiler-core/slang-glslang-compiler.cpp b/source/compiler-core/slang-glslang-compiler.cpp
index 26cbf3292..6e11d9814 100644
--- a/source/compiler-core/slang-glslang-compiler.cpp
+++ b/source/compiler-core/slang-glslang-compiler.cpp
@@ -14,7 +14,7 @@
 #include "../core/slang-semantic-version.h"
 #include "../core/slang-char-util.h"
 
-#include "../core/slang-digest.h"
+#include "../core/slang-digest-builder.h"
 
 #include "slang-artifact-associated-impl.h"
 #include "slang-artifact-desc-util.h"
diff --git a/source/core/slang-digest.h b/source/core/slang-digest-builder.h
index 47c0cd8f7..47c0cd8f7 100644
--- a/source/core/slang-digest.h
+++ b/source/core/slang-digest-builder.h
diff --git a/source/core/slang-digest-util.cpp b/source/core/slang-digest-util.cpp
new file mode 100644
index 000000000..d235f2cf0
--- /dev/null
+++ b/source/core/slang-digest-util.cpp
@@ -0,0 +1,66 @@
+// string-digest-util.cpp
+#include "slang-digest-util.h"
+
+#include "../core/slang-basic.h"
+#include "../core/slang-digest-builder.h"
+#include "../core/slang-md5.h"
+#include "../core/slang-char-util.h"
+
+namespace Slang
+{
+
+/*static*/ Digest DigestUtil::computeDigestForStringSlice(UnownedStringSlice text)
+{
+    DigestBuilder builder;
+    builder.addToDigest(text);
+    return builder.finalize();
+}
+
+/*static*/ Digest DigestUtil::combine(const Digest& digestA, const Digest& digestB)
+{
+    DigestBuilder builder;
+    builder.addToDigest(digestA);
+    builder.addToDigest(digestB);
+    return builder.finalize();
+}
+
+/*static*/ String DigestUtil::toString(const Digest& digest)
+{
+    StringBuilder hashString;
+
+    uint8_t* uint8Hash = (uint8_t*)digest.values;
+
+    for (Index i = 0; i < 16; ++i)
+    {
+        auto hashSegmentString = String(uint8Hash[i], 16);
+
+        if (hashSegmentString.getLength() == 1)
+        {
+            hashString.append("0");
+        }
+        hashString.append(hashSegmentString.getBuffer());
+    }
+
+    return hashString;
+}
+
+/*static*/ Digest DigestUtil::fromString(UnownedStringSlice hashString)
+{
+    uint8_t uint8Hash[16];
+
+    // When the hash is converted to a String, ReverseInternalAscii is called
+    // at the very end. Since there is no way to get a char* for hashString to pass
+    // to ReverseInternalAscii to flip the string back, we instead loop starting from
+    // the end and work backwards towards the beginning.
+    for (Index i = 0; i < 16; i++)
+    {
+        uint8Hash[i] = (uint8_t)CharUtil::getHexDigitValue(hashString[i * 2]) * 16
+            + (uint8_t)CharUtil::getHexDigitValue(hashString[i * 2 + 1]);
+    }
+
+    Digest digest;
+    memcpy(digest.values, uint8Hash, 16);
+    return digest;
+}
+
+}
diff --git a/source/core/slang-digest-util.h b/source/core/slang-digest-util.h
new file mode 100644
index 000000000..1e272fd5e
--- /dev/null
+++ b/source/core/slang-digest-util.h
@@ -0,0 +1,43 @@
+// slang-digest-utils.h - Utility functions specifically designed to be used with slang::Digest
+#pragma once
+#include "../../slang.h"
+#include "slang-string.h"
+
+namespace Slang
+{
+    using slang::Digest;
+
+    struct DigestUtil
+    {
+        // Compute the digest for an UnownedStringSlice
+        static Digest computeDigestForStringSlice(UnownedStringSlice text);
+
+        // Combines the two provided digests.
+        static Digest combine(const Digest& digestA, const Digest& digestB);
+
+        // Returns the hash stored in digest as a String.
+        static String toString(const Digest& digest);
+
+        // Returns the hash represented by hashString as a Digest.
+        static Digest fromString(UnownedStringSlice hashString);
+    };
+
+    inline StringBuilder& operator<<(StringBuilder& sb, const Digest& d)
+    {
+        // Must cast to uint8_t* first in order to correctly account for
+        // endianness.
+        uint8_t* uint8Hash = (uint8_t*)d.values;
+
+        for (Index i = 0; i < 16; ++i)
+        {
+            int hashSegment = uint8Hash[i];
+            // Check if we need to append a leading zero.
+            if (hashSegment < 16)
+            {
+                sb << "0";
+            }
+            sb.append(hashSegment, 16);
+        }
+        return sb;
+    }
+}
diff --git a/source/core/slang-linked-list.h b/source/core/slang-linked-list.h
index 7c9987397..38da2ccce 100644
--- a/source/core/slang-linked-list.h
+++ b/source/core/slang-linked-list.h
@@ -243,6 +243,12 @@ public:
     {
         LinkedNode<T>* n = new LinkedNode<T>(this);
         n->Value = nData;
+        AddFirst(n);
+        count++;
+        return n;
+    };
+    void AddFirst(LinkedNode<T>* n)
+    {
         n->prev = 0;
         n->next = head;
         if (head)
@@ -250,24 +256,12 @@ public:
         head = n;
         if (!tail)
             tail = n;
-        count++;
-        return n;
-    };
-    void Delete(LinkedNode<T>* n, int Count = 1)
+    }
+    void RemoveFromList(LinkedNode<T>* n)
     {
-        LinkedNode<T>*n1, *n2 = 0, *tn;
+        LinkedNode<T>*n1, *n2 = 0;
         n1 = n->prev;
-        tn = n;
-        int numDeleted = 0;
-        for (int i = 0; i < Count; i++)
-        {
-            n2 = tn->next;
-            delete tn;
-            tn = n2;
-            numDeleted++;
-            if (tn == 0)
-                break;
-        }
+        n2 = n->next;
         if (n1)
             n1->next = n2;
         else
@@ -276,6 +270,24 @@ public:
             n2->prev = n1;
         else
             tail = n1;
+        n->prev = nullptr;
+        n->next = nullptr;
+    }
+    void Delete(LinkedNode<T>* n, int Count = 1)
+    {
+        LinkedNode<T>*cur, *next;
+        cur = n;
+        int numDeleted = 0;
+        for (int i = 0; i < Count; i++)
+        {
+            next = cur->next;
+            RemoveFromList(cur);
+            delete cur;
+            cur = next;
+            numDeleted++;
+            if (cur == 0)
+                break;
+        }
         count -= numDeleted;
     }
     void Clear()
diff --git a/source/slang/slang-ast-base.h b/source/slang/slang-ast-base.h
index 04788340a..dea02afbb 100644
--- a/source/slang/slang-ast-base.h
+++ b/source/slang/slang-ast-base.h
@@ -9,8 +9,6 @@
 
 #include "slang-serialize-reflection.h"
 
-#include "../core/slang-digest.h"
-
 // This file defines the primary base classes for the hierarchy of
 // AST nodes and related objects. For example, this is where the
 // basic `Decl`, `Stmt`, `Expr`, `type`, etc. definitions come from.
diff --git a/source/slang/slang-ast-val.h b/source/slang/slang-ast-val.h
index 49189f65c..5f72e58c8 100644
--- a/source/slang/slang-ast-val.h
+++ b/source/slang/slang-ast-val.h
@@ -3,7 +3,6 @@
 #pragma once
 
 #include "slang-ast-base.h"
-#include "../core/slang-digest.h"
 
 namespace Slang {
 
diff --git a/source/slang/slang-compiler.h b/source/slang/slang-compiler.h
index 016c8fefa..bd7cd4a18 100755
--- a/source/slang/slang-compiler.h
+++ b/source/slang/slang-compiler.h
@@ -3,7 +3,7 @@
 
 #include "../core/slang-basic.h"
 #include "../core/slang-shared-library.h"
-#include "../core/slang-digest.h"
+#include "../core/slang-digest-builder.h"
 
 #include "../compiler-core/slang-downstream-compiler.h"
 #include "../compiler-core/slang-downstream-compiler-util.h"
@@ -899,7 +899,7 @@ namespace Slang
             return Super::computeDependencyBasedHash(entryPointIndex, targetIndex, outHash);
         }
 
-        SLANG_NO_THROW void SLANG_MCALL computeASTBasedHash(slang::Digest* outHash)
+        SLANG_NO_THROW void SLANG_MCALL computeASTBasedHash(slang::Digest* outHash) SLANG_OVERRIDE
         {
             return Super::computeASTBasedHash(outHash);
         }
@@ -1126,7 +1126,7 @@ namespace Slang
             return Super::computeDependencyBasedHash(entryPointIndex, targetIndex, outHash);
         }
 
-        SLANG_NO_THROW void SLANG_MCALL computeASTBasedHash(slang::Digest* outHash)
+        SLANG_NO_THROW void SLANG_MCALL computeASTBasedHash(slang::Digest* outHash) SLANG_OVERRIDE
         {
             return Super::computeASTBasedHash(outHash);
         }
@@ -1322,7 +1322,7 @@ namespace Slang
             return Super::computeDependencyBasedHash(entryPointIndex, targetIndex, outHash);
         }
 
-        SLANG_NO_THROW void SLANG_MCALL computeASTBasedHash(slang::Digest* outHash)
+        SLANG_NO_THROW void SLANG_MCALL computeASTBasedHash(slang::Digest* outHash) SLANG_OVERRIDE
         {
             return Super::computeASTBasedHash(outHash);
         }
diff --git a/source/slang/slang-hash-utils.h b/source/slang/slang-hash-utils.h
deleted file mode 100644
index c354e43f0..000000000
--- a/source/slang/slang-hash-utils.h
+++ /dev/null
@@ -1,49 +0,0 @@
-// slang-hash-utils.h - Utility functions specifically designed to be used with slang::Digest
-#pragma once
-#include "../../slang.h"
-#include "../core/slang-basic.h"
-#include "../core/slang-md5.h"
-#include "../core/slang-digest.h"
-
-namespace Slang
-{
-    // Compute the hash for an UnownedStringSlice
-    inline slang::Digest computeHashForStringSlice(UnownedStringSlice text)
-    {
-        DigestBuilder builder;
-        builder.addToDigest(text);
-        return builder.finalize();
-    }
-
-    // Combines the two provided hashes.
-    inline slang::Digest combineHashes(const slang::Digest& hashA, const slang::Digest& hashB)
-    {
-        DigestBuilder builder;
-        builder.addToDigest(hashA);
-        builder.addToDigest(hashB);
-        return builder.finalize();
-    }
-
-    // Returns the stored hash in checksum as a String.
-    inline StringBuilder hashToString(const slang::Digest& hash)
-    {
-        StringBuilder filename;
-
-        uint8_t* uint8Hash = (uint8_t*)hash.values;
-
-        for (Index i = 0; i < 16; ++i)
-        {
-            auto hashSegmentString = String(uint8Hash[i], 16);
-
-            if (hashSegmentString.getLength() == 1)
-            {
-                filename.append("0");
-            }
-            filename.append(hashSegmentString.getBuffer());
-        }
-
-        return filename;
-    }
-
-    // TODO: fromString implementation?
-}
diff --git a/source/slang/slang-shader-cache-index.h b/source/slang/slang-shader-cache-index.h
deleted file mode 100644
index 530aacf11..000000000
--- a/source/slang/slang-shader-cache-index.h
+++ /dev/null
@@ -1,60 +0,0 @@
-#pragma once
-#include "../../slang.h"
-
-#include "../core/slang-string.h"
-#include "../core/slang-linked-list.h"
-#include "../core/slang-dictionary.h"
-
-namespace Slang
-{
-    class ShaderCacheIndex
-    {
-    public:
-        struct ShaderCacheEntry
-        {
-            slang::Digest dependencyBasedDigest;
-            slang::Digest astBasedDigest;
-        };
-
-        ShaderCacheIndex(SlangInt size)
-            : entryCountLimit(size)
-        {}
-
-        // Load a previous cache index saved to disk. If not found, create a new cache index
-        // and save it to disk as filename.
-        SlangResult loadCacheIndexFromFile(String filename);
-
-        // Fetch the cache entry corresponding to the provided key. If found, move the entry to
-        // the front of entries and return the entry. Else, return nullptr.
-        ShaderCacheEntry* findEntry(const slang::Digest& key);
-
-        // Add an entry to the cache with the provided key and contents hashes. If
-        // adding an entry causes the cache to exceed size limitations, this will also
-        // delete the least recently used entry.
-        void addEntry(const slang::Digest& dependencyDigest, const slang::Digest& astDigest);
-
-        // Update the contents hash for the specified entry in the cache and update the
-        // corresponding file on disk.
-        void updateEntry(const slang::Digest& dependencyDigest, const slang::Digest& astDigest);
-
-    private:
-        // Update the cache index on disk. This should be called any time an entry changes.
-        SlangResult saveCacheIndexToFile();
-
-        // Delete the last entry from entries and remove its key/value pair from keyToContents
-        // as well as remove the corresponding file on disk. This should only be used when the
-        // cache has reached the size limit specified by entryLimit to create space for a new entry.
-        void deleteEntry();
-
-        // Dictionary mapping each shader's key to its corresponding node (entry) in the list
-        // of entries.
-        Dictionary<slang::Digest, LinkedNode<ShaderCacheEntry>*> keyToEntry;
-
-        // Linked list containing the entries stored in the shader cache in order
-        // of most to least recently used.
-        LinkedList<ShaderCacheEntry> entries;
-
-        // The maximum number of cache entries allowed.
-        SlangInt entryCountLimit = -1;
-    }
-}
diff --git a/source/slang/slang.cpp b/source/slang/slang.cpp
index 3fb89c549..c7351d6a8 100644
--- a/source/slang/slang.cpp
+++ b/source/slang/slang.cpp
@@ -45,7 +45,7 @@
 #include "slang-check-impl.h"
 
 #include "../core/slang-md5.h"
-#include "slang-hash-utils.h"
+#include "../core/slang-digest-util.h"
 
 #include "../../slang-tag-version.h"
 
@@ -1692,8 +1692,8 @@ void TranslationUnitRequest::_addSourceFile(SourceFile* sourceFile)
         // for non-file-based dependencies later when shader files are being hashed for
         // the shader cache.
 
-        slang::Digest sourceHash = computeHashForStringSlice(sourceFile->getContent());
-        getModule()->addFilePathDependency(hashToString(sourceHash));
+        slang::Digest sourceHash = DigestUtil::computeDigestForStringSlice(sourceFile->getContent());
+        getModule()->addFilePathDependency(DigestUtil::toString(sourceHash));
     }
 }