[PATCH pve-cluster 02/12] rust: notify: add path templates with placeholder capture

[Hannes Laimer <h.laimer@proxmox.com>]

A template such as nodes/{node}/qemu-server/{vmid}.conf matches memdb
paths and captures the parts its placeholders stand for. A component
holds at most one placeholder, and a placeholder may take the rest of
the path only as the whole last component. With these limits a match
takes a single pass over the path without backtracking.

Signed-off-by: Hannes Laimer <h.laimer@proxmox.com>
---
 src/rust/pmxcfs-notify/Cargo.toml      |   3 +
 src/rust/pmxcfs-notify/src/lib.rs      |  14 ++
 src/rust/pmxcfs-notify/src/template.rs | 285 +++++++++++++++++++++++++
 3 files changed, 302 insertions(+)
 create mode 100644 src/rust/pmxcfs-notify/src/template.rs

diff --git a/src/rust/pmxcfs-notify/Cargo.toml b/src/rust/pmxcfs-notify/Cargo.toml
index 3de30b5..5a49c75 100644
--- a/src/rust/pmxcfs-notify/Cargo.toml
+++ b/src/rust/pmxcfs-notify/Cargo.toml
@@ -9,3 +9,6 @@ homepage.workspace = true
 rust-version.workspace = true
 
 [dependencies]
+anyhow.workspace = true
+serde.workspace = true
+serde_json.workspace = true
diff --git a/src/rust/pmxcfs-notify/src/lib.rs b/src/rust/pmxcfs-notify/src/lib.rs
index 8b13789..889fe50 100644
--- a/src/rust/pmxcfs-notify/src/lib.rs
+++ b/src/rust/pmxcfs-notify/src/lib.rs
@@ -1 +1,15 @@
+//! Change notification socket for pmxcfs.
+//!
+//! A template is a memdb path whose components may each hold one `{name}` placeholder for all or
+//! part of that component. The last component may instead be `{name...}` for the rest of the path.
+//! `nodes/{node}/qemu-server/{vmid}.conf` captures node and vmid, and `{path...}` matches every
+//! path.
 
+#![allow(dead_code)]
+
+mod template;
+
+/// Events and templates name memdb paths without a leading slash.
+pub(crate) fn normalize_path(path: &str) -> &str {
+    path.trim_start_matches('/')
+}
diff --git a/src/rust/pmxcfs-notify/src/template.rs b/src/rust/pmxcfs-notify/src/template.rs
new file mode 100644
index 0000000..e8feb8c
--- /dev/null
+++ b/src/rust/pmxcfs-notify/src/template.rs
@@ -0,0 +1,285 @@
+use std::collections::BTreeMap;
+use std::str::FromStr;
+
+use anyhow::{Error, bail};
+use serde::Deserialize;
+
+use crate::normalize_path;
+
+pub(crate) type Captures<'a> = BTreeMap<&'a str, &'a str>;
+
+#[derive(Debug, PartialEq, Eq)]
+enum Component {
+    Literal(String),
+    Param {
+        prefix: String,
+        name: String,
+        suffix: String,
+    },
+    Rest(String),
+}
+
+// One placeholder per component and the spanning form only at the end let a match run in a single
+// pass over the path without backtracking. It runs for every event, template and connection.
+#[derive(Debug, PartialEq, Eq, Deserialize)]
+#[serde(try_from = "String")]
+pub(crate) struct Template {
+    components: Vec<Component>,
+}
+
+fn valid_name(name: &str) -> bool {
+    let mut chars = name.chars();
+    chars
+        .next()
+        .is_some_and(|c| c.is_ascii_alphabetic() || c == '_')
+        && chars.all(|c| c.is_ascii_alphanumeric() || c == '_')
+}
+
+impl FromStr for Template {
+    type Err = Error;
+
+    fn from_str(text: &str) -> Result<Self, Error> {
+        let text = normalize_path(text);
+        if text.is_empty() {
+            bail!("empty template");
+        }
+        let parts: Vec<&str> = text.split('/').collect();
+        let last = parts.len() - 1;
+        let mut components = Vec::with_capacity(parts.len());
+        let mut names: Vec<&str> = Vec::new();
+        for (index, part) in parts.into_iter().enumerate() {
+            if part.is_empty() {
+                bail!("empty path component");
+            }
+            let Some((prefix, rest)) = part.split_once('{') else {
+                if part.contains('}') {
+                    bail!("malformed placeholder in '{part}'");
+                }
+                components.push(Component::Literal(part.to_owned()));
+                continue;
+            };
+            let Some((body, suffix)) = rest.split_once('}') else {
+                bail!("unterminated placeholder in '{part}'");
+            };
+            if suffix.contains('{') {
+                bail!("only one placeholder per component in '{part}'");
+            }
+            if prefix.contains('}') || body.contains('{') || suffix.contains('}') {
+                bail!("malformed placeholder in '{part}'");
+            }
+            let (name, spans) = match body.strip_suffix("...") {
+                Some(name) => (name, true),
+                None => (body, false),
+            };
+            if !valid_name(name) {
+                bail!("invalid placeholder name '{name}'");
+            }
+            if names.contains(&name) {
+                bail!("placeholder '{name}' used twice");
+            }
+            names.push(name);
+            if spans {
+                if index != last || !prefix.is_empty() || !suffix.is_empty() {
+                    bail!("'{{{name}...}}' must be the whole last component");
+                }
+                components.push(Component::Rest(name.to_owned()));
+            } else {
+                components.push(Component::Param {
+                    prefix: prefix.to_owned(),
+                    name: name.to_owned(),
+                    suffix: suffix.to_owned(),
+                });
+            }
+        }
+        Ok(Self { components })
+    }
+}
+
+impl TryFrom<String> for Template {
+    type Error = Error;
+
+    fn try_from(text: String) -> Result<Self, Error> {
+        text.parse()
+    }
+}
+
+impl Template {
+    pub(crate) fn matches<'a>(&'a self, path: &'a str) -> Option<Captures<'a>> {
+        let mut captures = Captures::new();
+        let mut rest = path;
+        let last = self.components.len() - 1;
+        for (index, component) in self.components.iter().enumerate() {
+            if let Component::Rest(name) = component {
+                if rest.is_empty() {
+                    return None;
+                }
+                captures.insert(name.as_str(), rest);
+                return Some(captures);
+            }
+            let (head, tail) = match rest.split_once('/') {
+                Some((head, tail)) => (head, Some(tail)),
+                None => (rest, None),
+            };
+            match component {
+                Component::Literal(literal) if head == literal.as_str() => {}
+                Component::Param {
+                    prefix,
+                    name,
+                    suffix,
+                } => {
+                    let value = head
+                        .strip_prefix(prefix.as_str())?
+                        .strip_suffix(suffix.as_str())?;
+                    if value.is_empty() {
+                        return None;
+                    }
+                    captures.insert(name.as_str(), value);
+                }
+                _ => return None,
+            }
+            match (tail, index == last) {
+                (None, true) => return Some(captures),
+                (Some(tail), false) => rest = tail,
+                _ => return None,
+            }
+        }
+        unreachable!("the last component returns")
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    fn parse(text: &str) -> Result<Template, Error> {
+        text.parse()
+    }
+
+    fn captures<'a>(pairs: &[(&'a str, &'a str)]) -> Captures<'a> {
+        pairs.iter().copied().collect()
+    }
+
+    #[test]
+    fn parses_templates() {
+        let literal = |text: &str| Component::Literal(text.to_owned());
+        let param = |prefix: &str, name: &str, suffix: &str| Component::Param {
+            prefix: prefix.to_owned(),
+            name: name.to_owned(),
+            suffix: suffix.to_owned(),
+        };
+        assert_eq!(
+            parse("/datacenter.cfg").unwrap(),
+            Template {
+                components: vec![literal("datacenter.cfg")]
+            }
+        );
+        assert_eq!(
+            parse("nodes/{node}/qemu-server/{vmid}.conf").unwrap(),
+            Template {
+                components: vec![
+                    literal("nodes"),
+                    param("", "node", ""),
+                    literal("qemu-server"),
+                    param("", "vmid", ".conf"),
+                ]
+            }
+        );
+        assert_eq!(
+            parse("{path...}").unwrap(),
+            Template {
+                components: vec![Component::Rest("path".to_owned())]
+            }
+        );
+        assert_eq!(
+            parse("priv/lock/{path...}").unwrap(),
+            Template {
+                components: vec![
+                    literal("priv"),
+                    literal("lock"),
+                    Component::Rest("path".to_owned())
+                ]
+            }
+        );
+    }
+
+    #[test]
+    fn rejects_bad_templates() {
+        for (text, message) in [
+            ("", "empty template"),
+            ("/", "empty template"),
+            ("a//b", "empty path component"),
+            ("a/", "empty path component"),
+            ("{a}{b}", "only one placeholder per component"),
+            ("{a", "unterminated placeholder"),
+            ("a}", "malformed placeholder"),
+            ("{a}}", "malformed placeholder"),
+            ("{a{b}", "malformed placeholder"),
+            ("{}", "invalid placeholder name ''"),
+            ("{1a}", "invalid placeholder name '1a'"),
+            ("{a-b}", "invalid placeholder name 'a-b'"),
+            ("a/{x}/{x}", "placeholder 'x' used twice"),
+            ("{a...}/b", "must be the whole last component"),
+            ("x{a...}", "must be the whole last component"),
+            ("{a...}.conf", "must be the whole last component"),
+        ] {
+            let err = parse(text).unwrap_err().to_string();
+            assert!(err.contains(message), "{text:?}: {err}");
+        }
+    }
+
+    #[test]
+    fn deserializes_from_a_string() {
+        let template: Template = serde_json::from_str("\"/nodes/{node}/host.fw\"").unwrap();
+        assert_eq!(template, parse("nodes/{node}/host.fw").unwrap());
+        let err = serde_json::from_str::<Template>("\"{a}{b}\"").unwrap_err();
+        assert!(
+            err.to_string()
+                .starts_with("only one placeholder per component in '{a}{b}'"),
+            "{err}"
+        );
+        assert!(serde_json::from_str::<Template>("1").is_err());
+    }
+
+    #[test]
+    fn matches_paths() {
+        let guest = parse("nodes/{node}/qemu-server/{vmid}.conf").unwrap();
+        assert_eq!(
+            guest.matches("nodes/n1/qemu-server/100.conf"),
+            Some(captures(&[("node", "n1"), ("vmid", "100")]))
+        );
+        assert_eq!(guest.matches("nodes/n1/qemu-server/100.conf.tmp.1"), None);
+        assert_eq!(guest.matches("nodes/n1/qemu-server/.conf"), None);
+        assert_eq!(guest.matches("nodes/n1/lxc/100.conf"), None);
+        assert_eq!(guest.matches("nodes/n1/qemu-server"), None);
+        assert_eq!(guest.matches("nodes/n1/qemu-server/100.conf/x"), None);
+        assert_eq!(guest.matches("nodes//qemu-server/100.conf"), None);
+        assert_eq!(guest.matches(""), None);
+
+        let host = parse("nodes/{node}/host-{id}.cfg").unwrap();
+        assert_eq!(
+            host.matches("nodes/n1/host-7.cfg"),
+            Some(captures(&[("node", "n1"), ("id", "7")]))
+        );
+        assert_eq!(host.matches("nodes/n1/host-.cfg"), None);
+        assert_eq!(host.matches("nodes/n1/host-7.cfgx"), None);
+
+        let exact = parse("datacenter.cfg").unwrap();
+        assert_eq!(exact.matches("datacenter.cfg"), Some(captures(&[])));
+        assert_eq!(exact.matches("datacenter.cfg/x"), None);
+        assert_eq!(exact.matches("xdatacenter.cfg"), None);
+
+        let all = parse("{path...}").unwrap();
+        assert_eq!(all.matches("a"), Some(captures(&[("path", "a")])));
+        assert_eq!(all.matches("a/b/c"), Some(captures(&[("path", "a/b/c")])));
+        assert_eq!(all.matches(""), None);
+
+        let locks = parse("priv/lock/{path...}").unwrap();
+        assert_eq!(
+            locks.matches("priv/lock/file-storage_cfg/a"),
+            Some(captures(&[("path", "file-storage_cfg/a")]))
+        );
+        assert_eq!(locks.matches("priv/lock"), None);
+        assert_eq!(locks.matches("priv/lock/"), None);
+        assert_eq!(locks.matches("priv/locks/a"), None);
+    }
+}
-- 
2.47.3