lonca_core/
keyed.rs

1//! Keyed directories (#261): directories whose files carry a key in their
2//! name that no other file there may have. Flyway's `V12__add_users.sql`,
3//! Django's `0012_add_users.py`, golang-migrate's `000012_add_users.up.sql`
4//! and numbered decision records are such files: two of them with one key
5//! conflict in meaning, and Git sees two unrelated paths.
6//!
7//! The policy names each directory and a pattern that reads the key from a
8//! file name (`[paths.keyed]` in `lonca.toml`). The pattern is a regular
9//! expression of the `regex` crate, which never backtracks: matching takes
10//! time linear in the name and gives the same answer everywhere. Its one
11//! capture group is the key.
12//!
13//! A key is reserved like a member's name: an `insert` lease on the
14//! directory's container, `dir#<dir>`, with the key in `names`.
15
16use std::collections::{BTreeMap, BTreeSet};
17
18use regex::{Regex, RegexBuilder};
19use serde::{Deserialize, Serialize};
20
21/// The name of a keyed directory's container: `db/migration#<dir>`.
22pub const DIR: &str = "<dir>";
23
24/// Asked for among the names of a lease on `dir#<dir>`, the daemon gives
25/// the next free number instead (see [`KeyedDirs::next_key`]); the log
26/// records the number.
27pub const NEXT: &str = "next";
28
29/// At most this many keyed directories in a policy.
30pub const MAX_DIRS: usize = 64;
31
32/// A pattern is at most this long.
33pub const MAX_PATTERN: usize = 200;
34
35/// A number key has at most this many digits, so every one is a `u64`.
36pub const MAX_DIGITS: usize = 18;
37
38/// A text key is at most this long.
39pub const MAX_TEXT: usize = 128;
40
41/// What the compiled automaton of one pattern may take, in bytes.
42const SIZE_LIMIT: usize = 1 << 20;
43
44/// How keys compare. `number`: `12` and `012` are one key, and a key is
45/// written in a lease without leading zeros. `text`: as written.
46#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Serialize, Deserialize)]
47#[serde(rename_all = "snake_case")]
48pub enum Compare {
49    #[default]
50    Number,
51    Text,
52}
53
54/// One keyed directory: its path (no trailing `/`) and how its files' names
55/// give their keys.
56#[derive(Clone, Debug)]
57pub struct KeyedDir {
58    pub dir: String,
59    pub compare: Compare,
60    pattern: Regex,
61}
62
63impl KeyedDir {
64    /// The key of the file `name` (a name, not a path), as a lease writes
65    /// it; `None` when the name does not match or what it gives is no key.
66    pub fn key_of(&self, name: &str) -> Option<String> {
67        let found = self.pattern.captures(name)?.get(1)?.as_str();
68        match self.compare {
69            Compare::Number => {
70                let digits = !found.is_empty() && found.bytes().all(|b| b.is_ascii_digit());
71                if !digits || found.len() > MAX_DIGITS {
72                    return None;
73                }
74                let trimmed = found.trim_start_matches('0');
75                Some(if trimmed.is_empty() { "0" } else { trimmed }.to_string())
76            }
77            Compare::Text => valid_text(found).then(|| found.to_string()),
78        }
79    }
80
81    /// `key` is a key of this directory as a lease must write it: for
82    /// numbers, digits without a leading zero.
83    pub fn valid_key(&self, key: &str) -> bool {
84        match self.compare {
85            Compare::Number => {
86                let digits = !key.is_empty() && key.bytes().all(|b| b.is_ascii_digit());
87                digits && key.len() <= MAX_DIGITS && (key == "0" || !key.starts_with('0'))
88            }
89            Compare::Text => valid_text(key),
90        }
91    }
92
93    /// The container whose `insert` leases reserve this directory's keys.
94    pub fn container(&self) -> String {
95        container(&self.dir)
96    }
97}
98
99/// `dir#<dir>`.
100pub fn container(dir: &str) -> String {
101    format!("{dir}#{DIR}")
102}
103
104/// What a text key may be: what a reserved name may be, and no `/`.
105fn valid_text(key: &str) -> bool {
106    let bad = |c: char| c.is_whitespace() || c.is_control() || "#.()[]<>~/\\".contains(c);
107    !key.is_empty() && key.len() <= MAX_TEXT && !key.contains(bad)
108}
109
110/// The keyed directories of a policy.
111#[derive(Clone, Debug, Default)]
112pub struct KeyedDirs {
113    dirs: BTreeMap<String, KeyedDir>,
114}
115
116impl KeyedDirs {
117    /// Compiles `(directory, pattern, compare)`. Refused: more than
118    /// [`MAX_DIRS`], a directory that is no plain relative path, a pattern
119    /// longer than [`MAX_PATTERN`], that does not compile within the size
120    /// limit, or that has other than exactly one capture group.
121    pub fn new<'a>(
122        entries: impl IntoIterator<Item = (&'a str, &'a str, Compare)>,
123    ) -> Result<Self, String> {
124        let mut dirs = BTreeMap::new();
125        for (dir, pattern, compare) in entries {
126            if !valid_dir(dir) {
127                return Err(format!("paths.keyed: `{dir}` is no directory path"));
128            }
129            if pattern.len() > MAX_PATTERN {
130                return Err(format!("paths.keyed.\"{dir}\": the pattern is too long"));
131            }
132            let compiled = RegexBuilder::new(pattern)
133                .size_limit(SIZE_LIMIT)
134                .dfa_size_limit(SIZE_LIMIT)
135                .build()
136                .map_err(|e| format!("paths.keyed.\"{dir}\": {e}"))?;
137            if compiled.captures_len() != 2 {
138                return Err(format!(
139                    "paths.keyed.\"{dir}\": the pattern needs one capture group, the key"
140                ));
141            }
142            let keyed = KeyedDir {
143                dir: dir.to_string(),
144                compare,
145                pattern: compiled,
146            };
147            dirs.insert(dir.to_string(), keyed);
148        }
149        if dirs.len() > MAX_DIRS {
150            return Err(format!("paths.keyed: more than {MAX_DIRS} directories"));
151        }
152        Ok(Self { dirs })
153    }
154
155    pub fn is_empty(&self) -> bool {
156        self.dirs.is_empty()
157    }
158
159    /// The keyed directory `dir`.
160    pub fn get(&self, dir: &str) -> Option<&KeyedDir> {
161        self.dirs.get(dir)
162    }
163
164    /// The keyed directory that holds `path` directly, and the file's name.
165    /// A file in a directory under it is not one of its files.
166    pub fn of<'p>(&self, path: &'p str) -> Option<(&KeyedDir, &'p str)> {
167        let (dir, name) = path.rsplit_once('/')?;
168        self.dirs.get(dir).map(|d| (d, name))
169    }
170
171    /// The keys, as `dir#key`, that two or more of `paths` have in one keyed
172    /// directory.
173    pub fn clashes<'p>(&self, paths: impl IntoIterator<Item = &'p str>) -> BTreeSet<String> {
174        let mut seen: BTreeMap<String, usize> = BTreeMap::new();
175        for path in paths {
176            if let Some((d, name)) = self.of(path)
177                && let Some(key) = d.key_of(name)
178            {
179                *seen.entry(format!("{}#{key}", d.dir)).or_default() += 1;
180            }
181        }
182        seen.into_iter()
183            .filter(|(_, n)| *n > 1)
184            .map(|(k, _)| k)
185            .collect()
186    }
187
188    /// The keys, as `dir#key`, of the files in `added` that another file of
189    /// `tree` (the paths of the tree they are in) has too.
190    pub fn taken<'p>(
191        &self,
192        added: &[String],
193        tree: impl IntoIterator<Item = &'p str> + Clone,
194    ) -> Vec<String> {
195        let mut out = BTreeSet::new();
196        for path in added {
197            let Some((d, name)) = self.of(path) else {
198                continue;
199            };
200            let Some(key) = d.key_of(name) else {
201                continue;
202            };
203            let same = |other: &str| {
204                other != path
205                    && self
206                        .of(other)
207                        .is_some_and(|(o, n)| o.dir == d.dir && o.key_of(n).as_ref() == Some(&key))
208            };
209            if tree.clone().into_iter().any(same) {
210                out.insert(format!("{}#{key}", d.dir));
211            }
212        }
213        out.into_iter().collect()
214    }
215
216    /// The number after the highest key that a file of `tree` has in `dir`
217    /// or that `reserved` holds; `1` when there is none. `None` for a text
218    /// directory, whose keys have no order, or one that is not keyed.
219    pub fn next_key<'p>(
220        &self,
221        dir: &str,
222        tree: impl IntoIterator<Item = &'p str>,
223        reserved: impl IntoIterator<Item = &'p str>,
224    ) -> Option<String> {
225        let d = self
226            .dirs
227            .get(dir)
228            .filter(|d| d.compare == Compare::Number)?;
229        let in_tree = tree.into_iter().filter_map(|p| {
230            let (o, name) = self.of(p)?;
231            (o.dir == d.dir).then(|| d.key_of(name)).flatten()
232        });
233        let held = reserved.into_iter().map(str::to_string);
234        let highest = in_tree
235            .chain(held)
236            .filter_map(|k| k.parse::<u64>().ok())
237            .max();
238        Some(highest.map_or(1, |h| h.saturating_add(1)).to_string())
239    }
240}
241
242/// A plain relative directory path: no empty, `.` or `..` part, no leading
243/// or trailing `/`, no `\`, `#` or control character.
244fn valid_dir(dir: &str) -> bool {
245    let bad = |c: char| c.is_control() || c == '\\' || c == '#';
246    !dir.is_empty()
247        && !dir.contains(bad)
248        && dir
249            .split('/')
250            .all(|part| !part.is_empty() && part != "." && part != "..")
251}
252
253#[cfg(test)]
254mod tests {
255    use super::*;
256
257    fn dirs() -> KeyedDirs {
258        KeyedDirs::new([
259            ("db/migration", r"^V(\d+)__", Compare::Number),
260            ("docs/adr", r"^([a-z]+)-", Compare::Text),
261        ])
262        .unwrap()
263    }
264
265    #[test]
266    fn a_key_comes_from_the_name_and_numbers_drop_leading_zeros() {
267        let k = dirs();
268        let m = k.get("db/migration").unwrap();
269        assert_eq!(m.key_of("V12__add_users.sql").as_deref(), Some("12"));
270        assert_eq!(m.key_of("V012__add_users.sql").as_deref(), Some("12"));
271        assert_eq!(m.key_of("V0__init.sql").as_deref(), Some("0"));
272        assert_eq!(m.key_of("V000__init.sql").as_deref(), Some("0"));
273        assert_eq!(m.key_of("README.md"), None);
274        assert_eq!(m.key_of("V__x.sql"), None);
275        assert_eq!(m.key_of(&format!("V{}__x.sql", "1".repeat(19))), None);
276        assert_eq!(
277            m.key_of(&format!("V{}__x.sql", "1".repeat(18))).as_deref(),
278            Some("111111111111111111")
279        );
280        let adr = k.get("docs/adr").unwrap();
281        assert_eq!(adr.key_of("cedar-policy.md").as_deref(), Some("cedar"));
282        assert_eq!(adr.key_of("0012-x.md"), None);
283    }
284
285    #[test]
286    fn a_number_key_that_is_no_digits_is_no_key() {
287        let k = KeyedDirs::new([("m", r"^(\w+)_", Compare::Number)]).unwrap();
288        let m = k.get("m").unwrap();
289        assert_eq!(m.key_of("abc_x.sql"), None);
290        assert_eq!(m.key_of("12_x.sql").as_deref(), Some("12"));
291    }
292
293    #[test]
294    fn a_lease_writes_a_number_without_leading_zeros() {
295        let k = dirs();
296        let m = k.get("db/migration").unwrap();
297        assert!(m.valid_key("12"));
298        assert!(m.valid_key("0"));
299        assert!(!m.valid_key("012"));
300        assert!(!m.valid_key("00"));
301        assert!(!m.valid_key(""));
302        assert!(!m.valid_key("1a"));
303        assert!(m.valid_key(&"9".repeat(18)));
304        assert!(!m.valid_key(&"9".repeat(19)));
305        let adr = k.get("docs/adr").unwrap();
306        assert!(adr.valid_key("cedar"));
307        assert!(adr.valid_key("012"));
308        assert!(!adr.valid_key("a/b"));
309        assert!(!adr.valid_key("a b"));
310        assert!(!adr.valid_key(""));
311        assert!(!adr.valid_key(&"a".repeat(129)));
312        assert!(adr.valid_key(&"a".repeat(128)));
313        assert_eq!(m.container(), "db/migration#<dir>");
314    }
315
316    #[test]
317    fn only_files_directly_in_the_directory_count() {
318        let k = dirs();
319        let (d, name) = k.of("db/migration/V1__a.sql").unwrap();
320        assert_eq!((d.dir.as_str(), name), ("db/migration", "V1__a.sql"));
321        assert!(k.of("db/migration/old/V1__a.sql").is_none());
322        assert!(k.of("db/V1__a.sql").is_none());
323        assert!(k.of("V1__a.sql").is_none());
324    }
325
326    #[test]
327    fn clashes_name_each_key_two_files_share() {
328        let k = dirs();
329        let paths = [
330            "db/migration/V12__a.sql",
331            "db/migration/V012__b.sql",
332            "db/migration/V13__c.sql",
333            "db/migration/README.md",
334            "db/migration/old/V13__d.sql",
335            "src/V13__e.sql",
336        ];
337        let c: Vec<String> = k.clashes(paths).into_iter().collect();
338        assert_eq!(c, ["db/migration#12"]);
339        assert!(k.clashes(["db/migration/V1__a.sql"]).is_empty());
340    }
341
342    #[test]
343    fn taken_is_an_added_key_another_file_has() {
344        let k = dirs();
345        let tree = [
346            "db/migration/V11__x.sql",
347            "db/migration/V12__a.sql",
348            "db/migration/V12__b.sql",
349            "db/migration/V13__c.sql",
350            "db/migration/old/V14__d.sql",
351            "docs/adr/cedar-a.md",
352        ];
353        let added = |p: &[&str]| p.iter().map(|s| s.to_string()).collect::<Vec<_>>();
354        assert_eq!(
355            k.taken(&added(&["db/migration/V12__b.sql"]), tree),
356            ["db/migration#12"]
357        );
358        assert!(
359            k.taken(&added(&["db/migration/V13__c.sql"]), tree)
360                .is_empty()
361        );
362        assert!(
363            k.taken(&added(&["db/migration/old/V14__d.sql"]), tree)
364                .is_empty()
365        );
366        assert!(k.taken(&added(&["src/a.rs"]), tree).is_empty());
367        assert!(k.taken(&added(&["db/migration/README"]), tree).is_empty());
368    }
369
370    #[test]
371    fn next_is_one_past_the_highest_in_trunk_or_reserved() {
372        let k = dirs();
373        let tree = [
374            "db/migration/V9__x.sql",
375            "db/migration/V10__y.sql",
376            "db/migration/old/V40__z.sql",
377            "db/V50__w.sql",
378        ];
379        assert_eq!(k.next_key("db/migration", tree, []).as_deref(), Some("11"));
380        assert_eq!(
381            k.next_key("db/migration", tree, ["12", "x"]).as_deref(),
382            Some("13")
383        );
384        assert_eq!(
385            k.next_key("db/migration", tree, ["3"]).as_deref(),
386            Some("11")
387        );
388        assert_eq!(k.next_key("db/migration", [], []).as_deref(), Some("1"));
389        assert_eq!(k.next_key("docs/adr", [], []), None);
390        assert_eq!(k.next_key("src", [], []), None);
391        let top = format!("db/migration/V{}__x.sql", u64::MAX);
392        assert_eq!(
393            k.next_key("db/migration", [top.as_str()], []),
394            Some("1".into())
395        );
396    }
397
398    #[test]
399    fn a_policy_that_can_not_be_read_is_refused() {
400        let one = |dir: &str, p: &str| KeyedDirs::new([(dir, p, Compare::Number)]).map(|_| ());
401        assert!(one("db/migration", r"^V(\d+)__").is_ok());
402        assert!(one("db/migration", r"^V\d+__").is_err(), "no group");
403        assert!(one("db/migration", r"^(V)(\d+)__").is_err(), "two groups");
404        assert!(one("db/migration", r"^V(\d+").is_err(), "does not compile");
405        assert!(one("db/migration", &"a".repeat(201)).is_err());
406        assert!(one("db/migration", &format!("({})", "a".repeat(198))).is_ok());
407        assert!(
408            one("db/migration", r"^(\w{1000}){1000}$").is_err(),
409            "too big"
410        );
411        for dir in [
412            "", "/db", "db/", "db//m", "./db", "db/../m", "db\\m", "db#m",
413        ] {
414            assert!(one(dir, r"^(\d+)").is_err(), "{dir:?}");
415        }
416        let many: Vec<String> = (0..=MAX_DIRS).map(|i| format!("d{i}")).collect();
417        let entries = many
418            .iter()
419            .map(|d| (d.as_str(), r"^(\d+)", Compare::Number));
420        assert!(KeyedDirs::new(entries).is_err());
421        let fits = many[..MAX_DIRS]
422            .iter()
423            .map(|d| (d.as_str(), r"^(\d+)", Compare::Number));
424        assert!(KeyedDirs::new(fits).is_ok());
425        assert!(KeyedDirs::default().is_empty());
426        assert!(!dirs().is_empty());
427    }
428}
lonca_core/keyed.rs

lonca_core/
keyed.rs
