AK+Kernel: Specialize Trie for NNOP<KString> and use it in UnveilNode

This let's us avoid the infallible String allocations.

6 files changed, 31 insertions, 13 deletions

diff --git a/AK/Trie.h b/AK/Trie.h
index 8c60e2f724..0160ed1883 100644
--- a/AK/Trie.h
+++ b/AK/Trie.h
@@ -81,9 +81,13 @@ public:
     {
         auto it = m_children.find(value);
         if (it == m_children.end()) {
-            auto node = TRY(adopt_nonnull_own_or_enomem(new (nothrow) Trie(value, move(metadata))));
+            OwnPtr<Trie> node;
+            if constexpr (requires { { value->try_clone() } -> SpecializationOf<ErrorOr>; })
+                node = TRY(adopt_nonnull_own_or_enomem(new (nothrow) Trie(TRY(value->try_clone()), move(metadata))));
+            else
+                node = TRY(adopt_nonnull_own_or_enomem(new (nothrow) Trie(value, move(metadata))));
             auto& node_ref = *node;
-            TRY(m_children.try_set(move(value), move(node)));
+            TRY(m_children.try_set(move(value), node.release_nonnull()));
             return &static_cast<BaseType&>(node_ref);
         }
 
@@ -105,8 +109,12 @@ public:
             else
                 return provide_missing_metadata(forward<Ts>(args)...);
         };
-        for (; it != end; ++it)
-            last_root_node = static_cast<Trie*>(TRY(last_root_node->ensure_child(*it, TRY(invoke_provide_missing_metadata(static_cast<BaseType&>(*last_root_node), it)))));
+        for (; it != end; ++it) {
+            if constexpr (requires { { ValueType::ElementType::try_create(*it) } -> SpecializationOf<ErrorOr>; })
+                last_root_node = static_cast<Trie*>(TRY(last_root_node->ensure_child(TRY(ValueType::ElementType::try_create(*it)), TRY(invoke_provide_missing_metadata(static_cast<BaseType&>(*last_root_node), it)))));
+            else
+                last_root_node = static_cast<Trie*>(TRY(last_root_node->ensure_child(*it, TRY(invoke_provide_missing_metadata(static_cast<BaseType&>(*last_root_node), it)))));
+        }
         last_root_node->set_metadata(move(metadata));
         return static_cast<BaseType*>(last_root_node);
     }
@@ -115,8 +123,12 @@ public:
     ErrorOr<BaseType*> insert(It& it, const It& end) requires(IsNullPointer<MetadataType>)
     {
         Trie* last_root_node = &traverse_until_last_accessible_node(it, end);
-        for (; it != end; ++it)
-            last_root_node = static_cast<Trie*>(TRY(last_root_node->ensure_child(*it, {})));
+        for (; it != end; ++it) {
+            if constexpr (requires { { ValueType::ElementType::try_create(*it) } -> SpecializationOf<ErrorOr>; })
+                last_root_node = static_cast<Trie*>(TRY(last_root_node->ensure_child(TRY(ValueType::ElementType::try_create(*it)), {})));
+            else
+                last_root_node = static_cast<Trie*>(TRY(last_root_node->ensure_child(*it, {})));
+        }
         return static_cast<BaseType*>(last_root_node);
     }
 
@@ -174,6 +186,14 @@ public:
     [[nodiscard]] bool is_empty() const { return m_children.is_empty(); }
     void clear() { m_children.clear(); }
 
+    ErrorOr<BaseType> deep_copy() requires(requires(ValueType value) { { value->try_clone() } -> SpecializationOf<ErrorOr>; })
+    {
+        Trie root(TRY(m_value->try_clone()), TRY(copy_metadata(m_metadata)));
+        for (auto& it : m_children)
+            TRY(root.m_children.try_set(TRY(it.key->try_clone()), TRY(adopt_nonnull_own_or_enomem(new (nothrow) Trie(TRY(it.value->deep_copy()))))));
+        return static_cast<BaseType&&>(move(root));
+    }
+
     ErrorOr<BaseType> deep_copy()
     {
         Trie root(m_value, TRY(copy_metadata(m_metadata)));
diff --git a/Kernel/FileSystem/Inode.h b/Kernel/FileSystem/Inode.h
index 2056da0bf4..d5d06b8a02 100644
--- a/Kernel/FileSystem/Inode.h
+++ b/Kernel/FileSystem/Inode.h
@@ -11,7 +11,6 @@
 #include <AK/Function.h>
 #include <AK/HashTable.h>
 #include <AK/IntrusiveList.h>
-#include <AK/String.h>
 #include <AK/WeakPtr.h>
 #include <Kernel/FileSystem/FIFO.h>
 #include <Kernel/FileSystem/FileSystem.h>
diff --git a/Kernel/FileSystem/InodeWatcher.h b/Kernel/FileSystem/InodeWatcher.h
index 39d80652ab..a003d58b90 100644
--- a/Kernel/FileSystem/InodeWatcher.h
+++ b/Kernel/FileSystem/InodeWatcher.h
@@ -12,7 +12,6 @@
 #include <AK/CircularQueue.h>
 #include <AK/HashMap.h>
 #include <AK/NonnullOwnPtr.h>
-#include <AK/String.h>
 #include <Kernel/API/InodeWatcherEvent.h>
 #include <Kernel/FileSystem/File.h>
 #include <Kernel/Forward.h>
diff --git a/Kernel/FileSystem/UnveilNode.h b/Kernel/FileSystem/UnveilNode.h
index 76d3ec63bb..69d4179239 100644
--- a/Kernel/FileSystem/UnveilNode.h
+++ b/Kernel/FileSystem/UnveilNode.h
@@ -6,8 +6,8 @@
 
 #pragma once
 
-#include <AK/String.h>
 #include <AK/Trie.h>
+#include <Kernel/KString.h>
 
 namespace Kernel {
 
@@ -49,8 +49,8 @@ struct UnveilMetadata {
     }
 };
 
-struct UnveilNode final : public Trie<String, UnveilMetadata, Traits<String>, UnveilNode> {
-    using Trie<String, UnveilMetadata, Traits<String>, UnveilNode>::Trie;
+struct UnveilNode final : public Trie<NonnullOwnPtr<KString>, UnveilMetadata, Traits<NonnullOwnPtr<KString>>, UnveilNode> {
+    using Trie<NonnullOwnPtr<KString>, UnveilMetadata, Traits<NonnullOwnPtr<KString>>, UnveilNode>::Trie;
 
     bool was_explicitly_unveiled() const { return this->metadata_value().explicitly_unveiled; }
     UnveilAccess permissions() const { return this->metadata_value().permissions; }
diff --git a/Kernel/Process.cpp b/Kernel/Process.cpp
index fb30fea499..851d5df5bb 100644
--- a/Kernel/Process.cpp
+++ b/Kernel/Process.cpp
@@ -218,7 +218,8 @@ void Process::unprotect_data()
 ErrorOr<NonnullRefPtr<Process>> Process::try_create(RefPtr<Thread>& first_thread, NonnullOwnPtr<KString> name, UserID uid, GroupID gid, ProcessID ppid, bool is_kernel_process, RefPtr<Custody> cwd, RefPtr<Custody> executable, TTY* tty, Process* fork_parent)
 {
     auto space = TRY(Memory::AddressSpace::try_create(fork_parent ? &fork_parent->address_space() : nullptr));
-    auto process = TRY(adopt_nonnull_ref_or_enomem(new (nothrow) Process(move(name), uid, gid, ppid, is_kernel_process, move(cwd), move(executable), tty, UnveilNode { "/"sv, UnveilMetadata(TRY(KString::try_create("/"sv))) })));
+    auto unveil_tree = UnveilNode { TRY(KString::try_create("/"sv)), UnveilMetadata(TRY(KString::try_create("/"sv))) };
+    auto process = TRY(adopt_nonnull_ref_or_enomem(new (nothrow) Process(move(name), uid, gid, ppid, is_kernel_process, move(cwd), move(executable), tty, move(unveil_tree))));
     TRY(process->attach_resources(move(space), first_thread, fork_parent));
     return process;
 }
diff --git a/Kernel/Process.h b/Kernel/Process.h
index 1c62102dba..092df9f8af 100644
--- a/Kernel/Process.h
+++ b/Kernel/Process.h
@@ -12,7 +12,6 @@
 #include <AK/IntrusiveListRelaxedConst.h>
 #include <AK/NonnullRefPtrVector.h>
 #include <AK/OwnPtr.h>
-#include <AK/String.h>
 #include <AK/Userspace.h>
 #include <AK/Variant.h>
 #include <AK/WeakPtr.h>