refactor(tvix/castore): remove `name` from Nodes r/8504

Nodes only have names if they're contained inside a Directory, or if
they're a root node and have something else possibly giving them a name
externally.

This removes all `name` fields in the three different Nodes, and instead
maintains it inside a BTreeMap inside the Directory.

It also removes the NamedNode trait (they don't have a get_name()), as
well as Node::rename(self, name), and all [Partial]Ord implementations
for Node (as they don't have names to use for sorting).

The `nodes()`, `directories()`, `files()` iterators inside a `Directory`
now return a tuple of Name and Node, as does the RootNodesProvider.

The different {Directory,File,Symlink}Node struct constructors got
simpler, and the {Directory,File}Node ones became infallible - as
there's no more possibility to represent invalid state.

The proto structs stayed the same - there's now from_name_and_node and
into_name_and_node to convert back and forth between the two `Node`
structs.

Some further cleanups:

The error types for Node validation were renamed. Everything related to
names is now in the DirectoryError (not yet happy about the naming)

There's some leftover cleanups to do:
 - There should be a from_(sorted_)iter and into_iter in Directory, so
   we can construct and deconstruct in one go.
   That should also enable us to implement conversions from and to the
   proto representation that moves, rather than clones.

 - The BuildRequest and PathInfo structs are still proto-based, so we
   still do a bunch of conversions back and forth there (and have some
   ugly expect there). There's not much point for error handling here,
   this will be moved to stricter types in a followup CL.

Change-Id: I7369a8e3a426f44419c349077cb4fcab2044ebb6
Reviewed-on: https://cl.tvl.fyi/c/depot/+/12205
Tested-by: BuildkiteCI
Reviewed-by: yuka <yuka@yuka.dev>
Autosubmit: flokli <flokli@flokli.de>
Reviewed-by: benjaminedwardwebb <benjaminedwardwebb@gmail.com>
Reviewed-by: Connor Brewster <cbrewster@hey.com>

5 files changed, 125 insertions, 260 deletions

diff --git a/tvix/castore/src/nodes/directory.rs b/tvix/castore/src/nodes/directory.rs
index 1752681c89c3..d58b7822a434 100644
--- a/tvix/castore/src/nodes/directory.rs
+++ b/tvix/castore/src/nodes/directory.rs
@@ -1,23 +1,25 @@
-use crate::{
-    proto, B3Digest, DirectoryNode, FileNode, NamedNode, Node, SymlinkNode, ValidateDirectoryError,
-    ValidateNodeError,
-};
-
-/// A Directory can contain Directory, File or Symlink nodes.
-/// Each of these nodes have a name attribute, which is the basename in that
-/// directory and node type specific attributes.
-/// While a Node by itself may have any name, the names of Directory entries:
+use std::collections::BTreeMap;
+
+use crate::{errors::DirectoryError, proto, B3Digest, DirectoryNode, FileNode, Node, SymlinkNode};
+
+/// A Directory contains nodes, which can be Directory, File or Symlink nodes.
+/// It attached names to these nodes, which is the basename in that directory.
+/// These names:
 ///  - MUST not contain slashes or null bytes
 ///  - MUST not be '.' or '..'
 ///  - MUST be unique across all three lists
 #[derive(Default, Debug, Clone, PartialEq, Eq)]
 pub struct Directory {
-    nodes: Vec<Node>,
+    nodes: BTreeMap<bytes::Bytes, Node>,
 }
 
 impl Directory {
+    /// Constructs a new, empty Directory.
+    /// FUTUREWORK: provide a constructor from an interator of (sorted) names and nodes.
     pub fn new() -> Self {
-        Directory { nodes: vec![] }
+        Directory {
+            nodes: BTreeMap::new(),
+        }
     }
 
     /// The size of a directory is the number of all regular and symlink elements,
@@ -25,7 +27,7 @@ impl Directory {
     pub fn size(&self) -> u64 {
         // It's impossible to create a Directory where the size overflows, because we
         // check before every add() that the size won't overflow.
-        (self.nodes.len() as u64) + self.directories().map(|e| e.size()).sum::<u64>()
+        (self.nodes.len() as u64) + self.directories().map(|(_name, dn)| dn.size()).sum::<u64>()
     }
 
     /// Calculates the digest of a Directory, which is the blake3 hash of a
@@ -35,62 +37,66 @@ impl Directory {
     }
 
     /// Allows iterating over all nodes (directories, files and symlinks)
-    /// ordered by their name.
-    pub fn nodes(&self) -> impl Iterator<Item = &Node> + Send + Sync + '_ {
+    /// For each, it returns a tuple of its name and node.
+    /// The elements are sorted by their names.
+    pub fn nodes(&self) -> impl Iterator<Item = (&bytes::Bytes, &Node)> + Send + Sync + '_ {
         self.nodes.iter()
     }
 
-    /// Allows iterating over the FileNode entries of this directory
-    /// ordered by their name
-    pub fn files(&self) -> impl Iterator<Item = &FileNode> + Send + Sync + '_ {
-        self.nodes.iter().filter_map(|node| match node {
-            Node::File(n) => Some(n),
+    /// Allows iterating over the FileNode entries of this directory.
+    /// For each, it returns a tuple of its name and node.
+    /// The elements are sorted by their names.
+    pub fn files(&self) -> impl Iterator<Item = (&bytes::Bytes, &FileNode)> + Send + Sync + '_ {
+        self.nodes.iter().filter_map(|(name, node)| match node {
+            Node::File(n) => Some((name, n)),
             _ => None,
         })
     }
 
-    /// Allows iterating over the subdirectories of this directory
-    /// ordered by their name
-    pub fn directories(&self) -> impl Iterator<Item = &DirectoryNode> + Send + Sync + '_ {
-        self.nodes.iter().filter_map(|node| match node {
-            Node::Directory(n) => Some(n),
+    /// Allows iterating over the DirectoryNode entries (subdirectories) of this directory.
+    /// For each, it returns a tuple of its name and node.
+    /// The elements are sorted by their names.
+    pub fn directories(
+        &self,
+    ) -> impl Iterator<Item = (&bytes::Bytes, &DirectoryNode)> + Send + Sync + '_ {
+        self.nodes.iter().filter_map(|(name, node)| match node {
+            Node::Directory(n) => Some((name, n)),
             _ => None,
         })
     }
 
     /// Allows iterating over the SymlinkNode entries of this directory
-    /// ordered by their name
-    pub fn symlinks(&self) -> impl Iterator<Item = &SymlinkNode> + Send + Sync + '_ {
-        self.nodes.iter().filter_map(|node| match node {
-            Node::Symlink(n) => Some(n),
+    /// For each, it returns a tuple of its name and node.
+    /// The elements are sorted by their names.
+    pub fn symlinks(
+        &self,
+    ) -> impl Iterator<Item = (&bytes::Bytes, &SymlinkNode)> + Send + Sync + '_ {
+        self.nodes.iter().filter_map(|(name, node)| match node {
+            Node::Symlink(n) => Some((name, n)),
             _ => None,
         })
     }
 
     /// Checks a Node name for validity as a directory entry
     /// We disallow slashes, null bytes, '.', '..' and the empty string.
-    pub(crate) fn validate_node_name(name: &[u8]) -> Result<(), ValidateNodeError> {
-        if name.is_empty()
+    pub(crate) fn is_valid_name(name: &[u8]) -> bool {
+        !(name.is_empty()
             || name == b".."
             || name == b"."
             || name.contains(&0x00)
-            || name.contains(&b'/')
-        {
-            Err(ValidateNodeError::InvalidName(name.to_owned().into()))
-        } else {
-            Ok(())
-        }
+            || name.contains(&b'/'))
     }
 
-    /// Adds the specified [Node] to the [Directory], preserving sorted entries.
+    /// Adds the specified [Node] to the [Directory] with a given name.
     ///
     /// Inserting an element that already exists with the same name in the directory will yield an
     /// error.
-    /// Inserting an element will validate that its name fulfills the stricter requirements for
-    /// directory entries and yield an error if it is not.
-    pub fn add(&mut self, node: Node) -> Result<(), ValidateDirectoryError> {
-        Self::validate_node_name(node.get_name())
-            .map_err(|e| ValidateDirectoryError::InvalidNode(node.get_name().clone().into(), e))?;
+    /// Inserting an element will validate that its name fulfills the
+    /// requirements for directory entries and yield an error if it is not.
+    pub fn add(&mut self, name: bytes::Bytes, node: Node) -> Result<(), DirectoryError> {
+        if !Self::is_valid_name(&name) {
+            return Err(DirectoryError::InvalidName(name));
+        }
 
         // Check that the even after adding this new directory entry, the size calculation will not
         // overflow
@@ -104,24 +110,17 @@ impl Directory {
                 _ => 0,
             },
         ])
-        .ok_or(ValidateDirectoryError::SizeOverflow)?;
-
-        // This assumes the [Directory] is sorted, since we don't allow accessing the nodes list
-        // directly and all previous inserts should have been in-order
-        let pos = match self
-            .nodes
-            .binary_search_by_key(&node.get_name(), |n| n.get_name())
-        {
-            Err(pos) => pos, // There is no node with this name; good!
-            Ok(_) => {
-                return Err(ValidateDirectoryError::DuplicateName(
-                    node.get_name().to_vec(),
-                ))
-            }
-        };
+        .ok_or(DirectoryError::SizeOverflow)?;
 
-        self.nodes.insert(pos, node);
-        Ok(())
+        match self.nodes.entry(name) {
+            std::collections::btree_map::Entry::Vacant(e) => {
+                e.insert(node);
+                Ok(())
+            }
+            std::collections::btree_map::Entry::Occupied(occupied) => {
+                Err(DirectoryError::DuplicateName(occupied.key().to_vec()))
+            }
+        }
     }
 }
 
@@ -133,49 +132,58 @@ fn checked_sum(iter: impl IntoIterator<Item = u64>) -> Option<u64> {
 mod test {
     use super::{Directory, DirectoryNode, FileNode, Node, SymlinkNode};
     use crate::fixtures::DUMMY_DIGEST;
-    use crate::ValidateDirectoryError;
+    use crate::DirectoryError;
 
     #[test]
     fn add_nodes_to_directory() {
         let mut d = Directory::new();
 
-        d.add(Node::Directory(
-            DirectoryNode::new("b".into(), DUMMY_DIGEST.clone(), 1).unwrap(),
-        ))
+        d.add(
+            "b".into(),
+            Node::Directory(DirectoryNode::new(DUMMY_DIGEST.clone(), 1)),
+        )
         .unwrap();
-        d.add(Node::Directory(
-            DirectoryNode::new("a".into(), DUMMY_DIGEST.clone(), 1).unwrap(),
-        ))
+        d.add(
+            "a".into(),
+            Node::Directory(DirectoryNode::new(DUMMY_DIGEST.clone(), 1)),
+        )
         .unwrap();
-        d.add(Node::Directory(
-            DirectoryNode::new("z".into(), DUMMY_DIGEST.clone(), 1).unwrap(),
-        ))
+        d.add(
+            "z".into(),
+            Node::Directory(DirectoryNode::new(DUMMY_DIGEST.clone(), 1)),
+        )
         .unwrap();
 
-        d.add(Node::File(
-            FileNode::new("f".into(), DUMMY_DIGEST.clone(), 1, true).unwrap(),
-        ))
+        d.add(
+            "f".into(),
+            Node::File(FileNode::new(DUMMY_DIGEST.clone(), 1, true)),
+        )
         .unwrap();
-        d.add(Node::File(
-            FileNode::new("c".into(), DUMMY_DIGEST.clone(), 1, true).unwrap(),
-        ))
+        d.add(
+            "c".into(),
+            Node::File(FileNode::new(DUMMY_DIGEST.clone(), 1, true)),
+        )
         .unwrap();
-        d.add(Node::File(
-            FileNode::new("g".into(), DUMMY_DIGEST.clone(), 1, true).unwrap(),
-        ))
+        d.add(
+            "g".into(),
+            Node::File(FileNode::new(DUMMY_DIGEST.clone(), 1, true)),
+        )
         .unwrap();
 
-        d.add(Node::Symlink(
-            SymlinkNode::new("t".into(), "a".into()).unwrap(),
-        ))
+        d.add(
+            "t".into(),
+            Node::Symlink(SymlinkNode::new("a".into()).unwrap()),
+        )
         .unwrap();
-        d.add(Node::Symlink(
-            SymlinkNode::new("o".into(), "a".into()).unwrap(),
-        ))
+        d.add(
+            "o".into(),
+            Node::Symlink(SymlinkNode::new("a".into()).unwrap()),
+        )
         .unwrap();
-        d.add(Node::Symlink(
-            SymlinkNode::new("e".into(), "a".into()).unwrap(),
-        ))
+        d.add(
+            "e".into(),
+            Node::Symlink(SymlinkNode::new("a".into()).unwrap()),
+        )
         .unwrap();
 
         // Convert to proto struct and back to ensure we are not generating any invalid structures
@@ -188,10 +196,11 @@ mod test {
         let mut d = Directory::new();
 
         assert_eq!(
-            d.add(Node::Directory(
-                DirectoryNode::new("foo".into(), DUMMY_DIGEST.clone(), u64::MAX).unwrap(),
-            )),
-            Err(ValidateDirectoryError::SizeOverflow)
+            d.add(
+                "foo".into(),
+                Node::Directory(DirectoryNode::new(DUMMY_DIGEST.clone(), u64::MAX))
+            ),
+            Err(DirectoryError::SizeOverflow)
         );
     }
 
@@ -199,16 +208,18 @@ mod test {
     fn add_duplicate_node_to_directory() {
         let mut d = Directory::new();
 
-        d.add(Node::Directory(
-            DirectoryNode::new("a".into(), DUMMY_DIGEST.clone(), 1).unwrap(),
-        ))
+        d.add(
+            "a".into(),
+            Node::Directory(DirectoryNode::new(DUMMY_DIGEST.clone(), 1)),
+        )
         .unwrap();
         assert_eq!(
             format!(
                 "{}",
-                d.add(Node::File(
-                    FileNode::new("a".into(), DUMMY_DIGEST.clone(), 1, true).unwrap(),
-                ))
+                d.add(
+                    "a".into(),
+                    Node::File(FileNode::new(DUMMY_DIGEST.clone(), 1, true))
+                )
                 .expect_err("adding duplicate dir entry must fail")
             ),
             "\"a\" is a duplicate name"
@@ -220,13 +231,10 @@ mod test {
     async fn directory_reject_invalid_name() {
         let mut dir = Directory::new();
         assert!(
-            dir.add(Node::Symlink(
-                SymlinkNode::new(
-                    "".into(), // wrong! can not be added to directory
-                    "doesntmatter".into(),
-                )
-                .unwrap()
-            ))
+            dir.add(
+                "".into(), // wrong! can not be added to directory
+                Node::Symlink(SymlinkNode::new("doesntmatter".into(),).unwrap())
+            )
             .is_err(),
             "invalid symlink entry be rejected"
         );
diff --git a/tvix/castore/src/nodes/directory_node.rs b/tvix/castore/src/nodes/directory_node.rs
index afbae1695c63..e6e6312a7a0c 100644
--- a/tvix/castore/src/nodes/directory_node.rs
+++ b/tvix/castore/src/nodes/directory_node.rs
@@ -1,13 +1,11 @@
-use crate::{B3Digest, NamedNode, ValidateNodeError};
+use crate::B3Digest;
 
 /// A DirectoryNode is a pointer to a [Directory], by its [Directory::digest].
-/// It also gives it a `name` and `size`.
+/// It also records a`size`.
 /// Such a node is either an element in the [Directory] it itself is contained in,
 /// or a standalone root node./
 #[derive(Debug, Clone, PartialEq, Eq)]
 pub struct DirectoryNode {
-    /// The (base)name of the directory
-    name: bytes::Bytes,
     /// The blake3 hash of a Directory message, serialized in protobuf canonical form.
     digest: B3Digest,
     /// Number of child elements in the Directory referred to by `digest`.
@@ -23,8 +21,8 @@ pub struct DirectoryNode {
 }
 
 impl DirectoryNode {
-    pub fn new(name: bytes::Bytes, digest: B3Digest, size: u64) -> Result<Self, ValidateNodeError> {
-        Ok(Self { name, digest, size })
+    pub fn new(digest: B3Digest, size: u64) -> Self {
+        Self { digest, size }
     }
 
     pub fn digest(&self) -> &B3Digest {
@@ -34,31 +32,4 @@ impl DirectoryNode {
     pub fn size(&self) -> u64 {
         self.size
     }
-
-    pub fn rename(self, name: bytes::Bytes) -> Self {
-        Self { name, ..self }
-    }
-}
-
-impl PartialOrd for DirectoryNode {
-    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
-        Some(self.cmp(other))
-    }
-}
-
-impl Ord for DirectoryNode {
-    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
-        self.get_name().cmp(other.get_name())
-    }
-}
-
-impl NamedNode for &DirectoryNode {
-    fn get_name(&self) -> &bytes::Bytes {
-        &self.name
-    }
-}
-impl NamedNode for DirectoryNode {
-    fn get_name(&self) -> &bytes::Bytes {
-        &self.name
-    }
 }
diff --git a/tvix/castore/src/nodes/file_node.rs b/tvix/castore/src/nodes/file_node.rs
index 5dd677c17b49..73abe21e59b4 100644
--- a/tvix/castore/src/nodes/file_node.rs
+++ b/tvix/castore/src/nodes/file_node.rs
@@ -1,11 +1,8 @@
-use crate::{B3Digest, NamedNode, ValidateNodeError};
+use crate::B3Digest;
 
 /// A FileNode represents a regular or executable file in a Directory or at the root.
 #[derive(Debug, Clone, PartialEq, Eq)]
 pub struct FileNode {
-    /// The (base)name of the file
-    name: bytes::Bytes,
-
     /// The blake3 digest of the file contents
     digest: B3Digest,
 
@@ -17,18 +14,12 @@ pub struct FileNode {
 }
 
 impl FileNode {
-    pub fn new(
-        name: bytes::Bytes,
-        digest: B3Digest,
-        size: u64,
-        executable: bool,
-    ) -> Result<Self, ValidateNodeError> {
-        Ok(Self {
-            name,
+    pub fn new(digest: B3Digest, size: u64, executable: bool) -> Self {
+        Self {
             digest,
             size,
             executable,
-        })
+        }
     }
 
     pub fn digest(&self) -> &B3Digest {
@@ -42,31 +33,4 @@ impl FileNode {
     pub fn executable(&self) -> bool {
         self.executable
     }
-
-    pub fn rename(self, name: bytes::Bytes) -> Self {
-        Self { name, ..self }
-    }
-}
-
-impl PartialOrd for FileNode {
-    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
-        Some(self.cmp(other))
-    }
-}
-
-impl Ord for FileNode {
-    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
-        self.get_name().cmp(other.get_name())
-    }
-}
-
-impl NamedNode for &FileNode {
-    fn get_name(&self) -> &bytes::Bytes {
-        &self.name
-    }
-}
-impl NamedNode for FileNode {
-    fn get_name(&self) -> &bytes::Bytes {
-        &self.name
-    }
 }
diff --git a/tvix/castore/src/nodes/mod.rs b/tvix/castore/src/nodes/mod.rs
index bb8e14cf856e..47f39ae8f94a 100644
--- a/tvix/castore/src/nodes/mod.rs
+++ b/tvix/castore/src/nodes/mod.rs
@@ -4,66 +4,17 @@ mod directory_node;
 mod file_node;
 mod symlink_node;
 
-use bytes::Bytes;
 pub use directory::Directory;
 pub use directory_node::DirectoryNode;
 pub use file_node::FileNode;
 pub use symlink_node::SymlinkNode;
 
 /// A Node is either a [DirectoryNode], [FileNode] or [SymlinkNode].
-/// While a Node by itself may have any name, only those matching specific requirements
-/// can can be added as entries to a [Directory] (see the documentation on [Directory] for details).
+/// Nodes themselves don't have names, what gives them names is either them
+/// being inside a [Directory], or a root node with its own name attached to it.
 #[derive(Debug, Clone, PartialEq, Eq)]
 pub enum Node {
     Directory(DirectoryNode),
     File(FileNode),
     Symlink(SymlinkNode),
 }
-
-impl Node {
-    /// Returns the node with a new name.
-    pub fn rename(self, name: Bytes) -> Self {
-        match self {
-            Node::Directory(n) => Node::Directory(n.rename(name)),
-            Node::File(n) => Node::File(n.rename(name)),
-            Node::Symlink(n) => Node::Symlink(n.rename(name)),
-        }
-    }
-}
-
-impl PartialOrd for Node {
-    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
-        Some(self.cmp(other))
-    }
-}
-
-impl Ord for Node {
-    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
-        self.get_name().cmp(other.get_name())
-    }
-}
-
-/// NamedNode is implemented for [FileNode], [DirectoryNode] and [SymlinkNode]
-/// and [Node], so we can ask all of them for the name easily.
-pub trait NamedNode {
-    fn get_name(&self) -> &Bytes;
-}
-
-impl NamedNode for &Node {
-    fn get_name(&self) -> &Bytes {
-        match self {
-            Node::File(node_file) => node_file.get_name(),
-            Node::Directory(node_directory) => node_directory.get_name(),
-            Node::Symlink(node_symlink) => node_symlink.get_name(),
-        }
-    }
-}
-impl NamedNode for Node {
-    fn get_name(&self) -> &Bytes {
-        match self {
-            Node::File(node_file) => node_file.get_name(),
-            Node::Directory(node_directory) => node_directory.get_name(),
-            Node::Symlink(node_symlink) => node_symlink.get_name(),
-        }
-    }
-}
diff --git a/tvix/castore/src/nodes/symlink_node.rs b/tvix/castore/src/nodes/symlink_node.rs
index 2fac27231a85..6b9df96a5dd3 100644
--- a/tvix/castore/src/nodes/symlink_node.rs
+++ b/tvix/castore/src/nodes/symlink_node.rs
@@ -1,50 +1,21 @@
-use crate::{NamedNode, ValidateNodeError};
+use crate::ValidateNodeError;
 
 /// A SymlinkNode represents a symbolic link in a Directory or at the root.
 #[derive(Debug, Clone, PartialEq, Eq)]
 pub struct SymlinkNode {
-    /// The (base)name of the symlink
-    name: bytes::Bytes,
     /// The target of the symlink.
     target: bytes::Bytes,
 }
 
 impl SymlinkNode {
-    pub fn new(name: bytes::Bytes, target: bytes::Bytes) -> Result<Self, ValidateNodeError> {
+    pub fn new(target: bytes::Bytes) -> Result<Self, ValidateNodeError> {
         if target.is_empty() || target.contains(&b'\0') {
             return Err(ValidateNodeError::InvalidSymlinkTarget(target));
         }
-        Ok(Self { name, target })
+        Ok(Self { target })
     }
 
     pub fn target(&self) -> &bytes::Bytes {
         &self.target
     }
-
-    pub(crate) fn rename(self, name: bytes::Bytes) -> Self {
-        Self { name, ..self }
-    }
-}
-
-impl PartialOrd for SymlinkNode {
-    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
-        Some(self.cmp(other))
-    }
-}
-
-impl Ord for SymlinkNode {
-    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
-        self.get_name().cmp(other.get_name())
-    }
-}
-
-impl NamedNode for &SymlinkNode {
-    fn get_name(&self) -> &bytes::Bytes {
-        &self.name
-    }
-}
-impl NamedNode for SymlinkNode {
-    fn get_name(&self) -> &bytes::Bytes {
-        &self.name
-    }
 }