sim_expr_tree_core/
namespace.rs

1use std::collections::{BTreeSet, HashMap};
2
3use crate::{
4    CellId, CellRecord, CodecPolicyPatch, DirId, DirRecord, EffectiveCodecPolicy,
5    GeneratedNameKind, NamespaceError, NamespaceName, NodeKind, RevisionTick, SourceRecord, Stamp,
6    TreeId,
7};
8
9/// Request record for creating an immutable durable cell.
10#[derive(Clone, Debug, PartialEq, Eq)]
11pub struct CellCreate {
12    /// Stable cell id.
13    pub id: CellId,
14    /// Reserved parent directory.
15    pub parent: DirId,
16    /// Reserved child name.
17    pub name: NamespaceName,
18    /// Cell node family.
19    pub kind: NodeKind,
20    /// Optional source provenance.
21    pub source: Option<SourceRecord>,
22    /// Local policy patch.
23    pub policy_patch: CodecPolicyPatch,
24}
25
26impl CellCreate {
27    /// Create a request with no source provenance and no local policy patch.
28    pub fn new(id: CellId, parent: DirId, name: NamespaceName, kind: NodeKind) -> Self {
29        Self {
30            id,
31            parent,
32            name,
33            kind,
34            source: None,
35            policy_patch: CodecPolicyPatch::empty(),
36        }
37    }
38
39    /// Attach source provenance.
40    pub fn with_source(mut self, source: SourceRecord) -> Self {
41        self.source = Some(source);
42        self
43    }
44
45    /// Attach a local policy patch.
46    pub fn with_policy_patch(mut self, policy_patch: CodecPolicyPatch) -> Self {
47        self.policy_patch = policy_patch;
48        self
49    }
50}
51
52/// An acquired serialized writer lane.
53#[derive(Clone, Copy, Debug, PartialEq, Eq)]
54pub struct WriterLane {
55    epoch: u64,
56}
57
58/// Durable finite namespace records for one expression tree.
59#[derive(Debug)]
60pub struct Namespace {
61    tree_id: TreeId,
62    root_dir: DirId,
63    dirs: HashMap<DirId, DirRecord>,
64    cells: HashMap<CellId, CellRecord>,
65    children: HashMap<(DirId, NamespaceName), NamespaceEntry>,
66    reservations: BTreeSet<(DirId, NamespaceName)>,
67    counters: HashMap<(DirId, GeneratedNameKind), u64>,
68    current: RevisionTick,
69    writer_epoch: u64,
70    writer_active: bool,
71}
72
73impl Namespace {
74    /// Create a namespace with one root directory record.
75    pub fn new(tree_id: TreeId, root_dir: DirId) -> Self {
76        let stamp = Stamp::new(RevisionTick::default(), None);
77        let root = DirRecord::root(root_dir.clone(), stamp);
78        Self {
79            tree_id,
80            root_dir: root_dir.clone(),
81            dirs: HashMap::from([(root_dir, root)]),
82            cells: HashMap::new(),
83            children: HashMap::new(),
84            reservations: BTreeSet::new(),
85            counters: HashMap::new(),
86            current: RevisionTick::default(),
87            writer_epoch: 0,
88            writer_active: false,
89        }
90    }
91
92    /// The namespace tree id.
93    pub fn tree_id(&self) -> &TreeId {
94        &self.tree_id
95    }
96
97    /// Root directory identity.
98    pub fn root_dir(&self) -> &DirId {
99        &self.root_dir
100    }
101
102    /// Acquire the single serialized writer lane.
103    pub fn acquire_writer(&mut self) -> Result<WriterLane, NamespaceError> {
104        if self.writer_active {
105            return Err(NamespaceError::WriterAlreadyActive);
106        }
107        self.writer_active = true;
108        self.writer_epoch += 1;
109        Ok(WriterLane {
110            epoch: self.writer_epoch,
111        })
112    }
113
114    /// Release a previously acquired writer lane.
115    pub fn release_writer(&mut self, lane: WriterLane) -> Result<(), NamespaceError> {
116        self.require_writer(lane)?;
117        self.writer_active = false;
118        Ok(())
119    }
120
121    /// Number of durable name reservations.
122    pub fn reservation_count(&self) -> usize {
123        self.reservations.len()
124    }
125
126    /// Number of generated-name counters.
127    pub fn counter_count(&self) -> usize {
128        self.counters.len()
129    }
130
131    /// Read a directory by id without allocating namespace state.
132    pub fn dir(&self, id: &DirId) -> Option<&DirRecord> {
133        self.dirs.get(id)
134    }
135
136    /// Read a cell by id without allocating namespace state.
137    pub fn cell(&self, id: &CellId) -> Option<&CellRecord> {
138        self.cells.get(id)
139    }
140
141    /// Read a named child without allocating namespace state.
142    pub fn child(&self, parent: &DirId, name: &NamespaceName) -> Option<NamespaceEntry> {
143        self.children.get(&(parent.clone(), name.clone())).cloned()
144    }
145
146    /// Lists a directory's named children in deterministic name order.
147    pub fn children(
148        &self,
149        parent: &DirId,
150    ) -> Result<Vec<(NamespaceName, NamespaceEntry)>, NamespaceError> {
151        self.ensure_parent(parent)?;
152        let mut children = self
153            .children
154            .iter()
155            .filter(|((entry_parent, _), _)| entry_parent == parent)
156            .map(|((_, name), entry)| (name.clone(), entry.clone()))
157            .collect::<Vec<_>>();
158        children.sort_by(|left, right| left.0.cmp(&right.0));
159        Ok(children)
160    }
161
162    /// Reserve an explicit child name before creating the durable node.
163    pub fn reserve_name(
164        &mut self,
165        lane: WriterLane,
166        parent: &DirId,
167        name: NamespaceName,
168    ) -> Result<NamespaceName, NamespaceError> {
169        self.require_writer(lane)?;
170        self.ensure_parent(parent)?;
171        self.ensure_available(parent, &name)?;
172        self.reservations.insert((parent.clone(), name.clone()));
173        Ok(name)
174    }
175
176    /// Reserve a generated child name before creating the durable node.
177    pub fn reserve_generated_name(
178        &mut self,
179        lane: WriterLane,
180        parent: &DirId,
181        kind: GeneratedNameKind,
182    ) -> Result<NamespaceName, NamespaceError> {
183        self.require_writer(lane)?;
184        self.ensure_parent(parent)?;
185        let key = (parent.clone(), kind);
186        let next_value = {
187            let next = self.counters.entry(key).or_insert(0);
188            *next += 1;
189            *next
190        };
191        let name = NamespaceName::new(format!("{}-{}", kind.prefix(), next_value))?;
192        if !self.is_available(parent, &name) {
193            return Err(NamespaceError::CounterCorruption {
194                parent: parent.clone(),
195                kind,
196                candidate: name,
197            });
198        }
199        self.reservations.insert((parent.clone(), name.clone()));
200        Ok(name)
201    }
202
203    /// Create a durable cell from a prior reservation.
204    pub fn create_cell(
205        &mut self,
206        lane: WriterLane,
207        request: CellCreate,
208    ) -> Result<(), NamespaceError> {
209        self.require_writer(lane)?;
210        self.consume_reservation(&request.parent, &request.name)?;
211        self.ensure_available(&request.parent, &request.name)?;
212        let stamp = self.next_stamp();
213        let record = CellRecord::new(
214            request.id.clone(),
215            request.parent.clone(),
216            request.name.clone(),
217            request.kind,
218            request.source,
219            request.policy_patch,
220            stamp,
221        );
222        self.children.insert(
223            (request.parent, request.name),
224            NamespaceEntry::Cell {
225                id: request.id.clone(),
226                kind: request.kind,
227            },
228        );
229        self.cells.insert(request.id, record);
230        Ok(())
231    }
232
233    /// Create a durable child directory from a prior reservation.
234    pub fn create_dir(
235        &mut self,
236        lane: WriterLane,
237        id: DirId,
238        parent: &DirId,
239        name: NamespaceName,
240        policy_patch: CodecPolicyPatch,
241    ) -> Result<(), NamespaceError> {
242        self.require_writer(lane)?;
243        self.consume_reservation(parent, &name)?;
244        self.ensure_available(parent, &name)?;
245        let stamp = self.next_stamp();
246        let record = DirRecord::child(
247            id.clone(),
248            parent.clone(),
249            name.clone(),
250            policy_patch,
251            stamp,
252        );
253        self.children.insert(
254            (parent.clone(), name),
255            NamespaceEntry::Dir { id: id.clone() },
256        );
257        self.dirs.insert(id, record);
258        Ok(())
259    }
260
261    /// Rename or move a cell while preserving immutable cell identity.
262    pub fn move_cell(
263        &mut self,
264        lane: WriterLane,
265        id: &CellId,
266        new_parent: &DirId,
267        new_name: NamespaceName,
268    ) -> Result<(), NamespaceError> {
269        self.require_writer(lane)?;
270        self.ensure_parent(new_parent)?;
271        let (old_parent, old_name, kind) = {
272            let record = self
273                .cells
274                .get(id)
275                .ok_or_else(|| NamespaceError::MissingCell(id.clone()))?;
276            (
277                record.parent().clone(),
278                record.name().clone(),
279                record.kind(),
280            )
281        };
282        if old_parent != *new_parent || old_name != new_name {
283            self.ensure_available(new_parent, &new_name)?;
284        }
285        self.children.remove(&(old_parent, old_name));
286        self.children.insert(
287            (new_parent.clone(), new_name.clone()),
288            NamespaceEntry::Cell {
289                id: id.clone(),
290                kind,
291            },
292        );
293        self.cells
294            .get_mut(id)
295            .expect("cell existence was checked above")
296            .rename(new_parent.clone(), new_name);
297        self.next_stamp();
298        Ok(())
299    }
300
301    /// Rename or move a directory while preserving immutable directory identity.
302    pub fn move_dir(
303        &mut self,
304        lane: WriterLane,
305        id: &DirId,
306        new_parent: &DirId,
307        new_name: NamespaceName,
308    ) -> Result<(), NamespaceError> {
309        self.require_writer(lane)?;
310        if id == &self.root_dir {
311            return Err(NamespaceError::RootDirCannotMove);
312        }
313        self.ensure_parent(new_parent)?;
314        if self.is_descendant(new_parent, id) {
315            return Err(NamespaceError::DirMoveCycle {
316                dir: id.clone(),
317                new_parent: new_parent.clone(),
318            });
319        }
320        let (old_parent, old_name) = {
321            let record = self
322                .dirs
323                .get(id)
324                .ok_or_else(|| NamespaceError::MissingDirRecord(id.clone()))?;
325            (
326                record
327                    .parent()
328                    .cloned()
329                    .expect("non-root dirs have parents"),
330                record.name().cloned().expect("non-root dirs have names"),
331            )
332        };
333        if old_parent != *new_parent || old_name != new_name {
334            self.ensure_available(new_parent, &new_name)?;
335        }
336        self.children.remove(&(old_parent, old_name));
337        self.children.insert(
338            (new_parent.clone(), new_name.clone()),
339            NamespaceEntry::Dir { id: id.clone() },
340        );
341        self.dirs
342            .get_mut(id)
343            .expect("dir existence was checked above")
344            .rename(new_parent.clone(), new_name);
345        self.next_stamp();
346        Ok(())
347    }
348
349    /// Replaces a cell's local codec-policy patch.
350    pub fn set_cell_policy(
351        &mut self,
352        lane: WriterLane,
353        id: &CellId,
354        policy_patch: CodecPolicyPatch,
355    ) -> Result<(), NamespaceError> {
356        self.require_writer(lane)?;
357        let cell = self
358            .cells
359            .get_mut(id)
360            .ok_or_else(|| NamespaceError::MissingCell(id.clone()))?;
361        cell.set_policy_patch(policy_patch);
362        self.next_stamp();
363        Ok(())
364    }
365
366    /// Replaces a directory's local codec-policy patch.
367    pub fn set_dir_policy(
368        &mut self,
369        lane: WriterLane,
370        id: &DirId,
371        policy_patch: CodecPolicyPatch,
372    ) -> Result<(), NamespaceError> {
373        self.require_writer(lane)?;
374        let dir = self
375            .dirs
376            .get_mut(id)
377            .ok_or_else(|| NamespaceError::MissingDirRecord(id.clone()))?;
378        dir.set_policy_patch(policy_patch);
379        self.next_stamp();
380        Ok(())
381    }
382
383    /// Deletes one cell while preserving its generated-name reservation history.
384    pub fn delete_cell(
385        &mut self,
386        lane: WriterLane,
387        id: &CellId,
388    ) -> Result<CellRecord, NamespaceError> {
389        self.require_writer(lane)?;
390        let record = self
391            .cells
392            .remove(id)
393            .ok_or_else(|| NamespaceError::MissingCell(id.clone()))?;
394        self.children
395            .remove(&(record.parent().clone(), record.name().clone()));
396        self.next_stamp();
397        Ok(record)
398    }
399
400    /// Deletes one empty non-root directory.
401    pub fn delete_dir(
402        &mut self,
403        lane: WriterLane,
404        id: &DirId,
405    ) -> Result<DirRecord, NamespaceError> {
406        self.require_writer(lane)?;
407        if id == &self.root_dir {
408            return Err(NamespaceError::RootDirCannotMove);
409        }
410        if self.children.keys().any(|(parent, _)| parent == id) {
411            return Err(NamespaceError::DirNotEmpty(id.clone()));
412        }
413        let record = self
414            .dirs
415            .remove(id)
416            .ok_or_else(|| NamespaceError::MissingDirRecord(id.clone()))?;
417        let parent = record
418            .parent()
419            .cloned()
420            .expect("non-root directory has a parent");
421        let name = record
422            .name()
423            .cloned()
424            .expect("non-root directory has a name");
425        self.children.remove(&(parent, name));
426        self.next_stamp();
427        Ok(record)
428    }
429
430    /// Resolve the inherited policy for a directory.
431    pub fn effective_dir_policy(&self, id: &DirId) -> Result<EffectiveCodecPolicy, NamespaceError> {
432        let mut lineage = Vec::new();
433        let mut cursor = id;
434        loop {
435            let dir = self
436                .dirs
437                .get(cursor)
438                .ok_or_else(|| NamespaceError::MissingDirRecord(cursor.clone()))?;
439            lineage.push(dir);
440            match dir.parent() {
441                Some(parent) => cursor = parent,
442                None => break,
443            }
444        }
445
446        let mut effective = EffectiveCodecPolicy::empty();
447        for dir in lineage.into_iter().rev() {
448            dir.policy_patch().apply_to(&mut effective);
449        }
450        Ok(effective)
451    }
452
453    /// Resolve the inherited policy for a cell, applying the cell patch last.
454    pub fn effective_cell_policy(
455        &self,
456        id: &CellId,
457    ) -> Result<EffectiveCodecPolicy, NamespaceError> {
458        let cell = self
459            .cells
460            .get(id)
461            .ok_or_else(|| NamespaceError::MissingCell(id.clone()))?;
462        let mut effective = self.effective_dir_policy(cell.parent())?;
463        cell.policy_patch().apply_to(&mut effective);
464        Ok(effective)
465    }
466
467    /// Test-only recovery hook for corrupt persisted counters.
468    #[cfg(test)]
469    pub(crate) fn set_counter_for_test(
470        &mut self,
471        parent: DirId,
472        kind: GeneratedNameKind,
473        value: u64,
474    ) {
475        self.counters.insert((parent, kind), value);
476    }
477
478    fn require_writer(&self, lane: WriterLane) -> Result<(), NamespaceError> {
479        if self.writer_active && lane.epoch == self.writer_epoch {
480            Ok(())
481        } else {
482            Err(NamespaceError::InvalidWriterLane)
483        }
484    }
485
486    fn ensure_parent(&self, parent: &DirId) -> Result<(), NamespaceError> {
487        if self.dirs.contains_key(parent) {
488            Ok(())
489        } else {
490            Err(NamespaceError::MissingDir(parent.clone()))
491        }
492    }
493
494    fn is_available(&self, parent: &DirId, name: &NamespaceName) -> bool {
495        !self.children.contains_key(&(parent.clone(), name.clone()))
496            && !self.reservations.contains(&(parent.clone(), name.clone()))
497    }
498
499    fn ensure_available(&self, parent: &DirId, name: &NamespaceName) -> Result<(), NamespaceError> {
500        if self.is_available(parent, name) {
501            Ok(())
502        } else {
503            Err(NamespaceError::NameCollision {
504                parent: parent.clone(),
505                name: name.clone(),
506            })
507        }
508    }
509
510    fn consume_reservation(
511        &mut self,
512        parent: &DirId,
513        name: &NamespaceName,
514    ) -> Result<(), NamespaceError> {
515        if self.reservations.remove(&(parent.clone(), name.clone())) {
516            Ok(())
517        } else {
518            Err(NamespaceError::MissingReservation {
519                parent: parent.clone(),
520                name: name.clone(),
521            })
522        }
523    }
524
525    fn next_stamp(&mut self) -> Stamp {
526        self.current = self.current.next_after();
527        Stamp::new(self.current, None)
528    }
529
530    fn is_descendant(&self, candidate: &DirId, ancestor: &DirId) -> bool {
531        let mut cursor = Some(candidate);
532        while let Some(id) = cursor {
533            if id == ancestor {
534                return true;
535            }
536            cursor = self.dirs.get(id).and_then(DirRecord::parent);
537        }
538        false
539    }
540}
541
542/// A named child entry in the finite namespace.
543#[derive(Clone, Debug, PartialEq, Eq)]
544pub enum NamespaceEntry {
545    /// Child directory.
546    Dir {
547        /// Directory identity.
548        id: DirId,
549    },
550    /// Child cell.
551    Cell {
552        /// Cell identity.
553        id: CellId,
554        /// Cell kind.
555        kind: NodeKind,
556    },
557}
558
559impl Namespace {
560    /// Convenience policy patch for tests and callers that need only a codec.
561    pub fn codec_patch(codec: impl Into<String>) -> CodecPolicyPatch {
562        CodecPolicyPatch::set_codec(codec)
563    }
564}
sim_expr_tree_core/namespace.rs

sim_expr_tree_core/
namespace.rs
