Skip to main content

uqa_graph/memory_store/
graphid.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! AGE graphid composition and per-graph label allocation state.
8
9use super::{BTreeMap, BTreeSet, Deserialize, GraphStoreError, GraphStoreResult, Serialize};
10
11use crate::age_names::{EDGE_DEFAULT_LABEL_NAME, VERTEX_DEFAULT_LABEL_NAME};
12
13/// Number of bits reserved for the per-label sequence inside an AGE
14/// `graphid`. The label id occupies the remaining high 16 bits.
15pub const GRAPHID_LABEL_SHIFT: u32 = 48;
16
17/// Reserved AGE label id for unlabeled vertices (`_ag_label_vertex`).
18pub const VERTEX_DEFAULT_LABEL_ID: u32 = 1;
19
20/// Reserved AGE label id for unlabeled edges (`_ag_label_edge`).
21pub const EDGE_DEFAULT_LABEL_ID: u32 = 2;
22
23/// First label id available to user labels.
24pub const FIRST_USER_LABEL_ID: u32 = 3;
25
26/// The largest label id whose AGE graphid remains representable as a signed
27/// 64-bit agtype integer.
28pub const MAX_GRAPHID_LABEL_ID: u32 = 32_767;
29
30pub(crate) const MAX_GRAPHID_SEQUENCE: u64 = (1_u64 << GRAPHID_LABEL_SHIFT) - 1;
31const MAX_EXACT_F64_INTEGER: u64 = 9_007_199_254_740_992;
32
33pub(crate) fn usize_to_f64_exact(value: usize, context: &str) -> GraphStoreResult<f64> {
34    if u64::try_from(value).is_ok_and(|value| value <= MAX_EXACT_F64_INTEGER) {
35        Ok(value as f64)
36    } else {
37        Err(GraphStoreError::InvalidMutation(format!(
38            "{context} {value} exceeds the exact f64 integer range"
39        )))
40    }
41}
42
43/// Compose an AGE `graphid` from a label id and per-label sequence.
44pub fn make_graphid(label_id: u32, sequence: u64) -> GraphStoreResult<u64> {
45    if label_id > MAX_GRAPHID_LABEL_ID {
46        return Err(GraphStoreError::IdExhausted(format!(
47            "label id {label_id} exceeds {MAX_GRAPHID_LABEL_ID}"
48        )));
49    }
50    if sequence == 0 || sequence > MAX_GRAPHID_SEQUENCE {
51        return Err(GraphStoreError::IdExhausted(format!(
52            "sequence {sequence} is outside 1..={MAX_GRAPHID_SEQUENCE}"
53        )));
54    }
55    Ok((u64::from(label_id) << GRAPHID_LABEL_SHIFT) | sequence)
56}
57
58/// Label id component of an AGE `graphid`.
59#[must_use]
60pub fn graphid_label_id(id: u64) -> u32 {
61    let bytes = id.to_be_bytes();
62    u32::from(u16::from_be_bytes([bytes[0], bytes[1]]))
63}
64
65/// Sequence component of an AGE `graphid`.
66#[must_use]
67pub fn graphid_sequence(id: u64) -> u64 {
68    id & ((1 << GRAPHID_LABEL_SHIFT) - 1)
69}
70
71/// AGE label kind: the `ag_label.kind` catalog value.
72#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
73pub enum LabelKind {
74    /// A vertex label (`ag_label.kind = 'v'`).
75    #[serde(rename = "v")]
76    Vertex,
77    /// An edge label (`ag_label.kind = 'e'`).
78    #[serde(rename = "e")]
79    Edge,
80}
81
82impl LabelKind {
83    /// The `ag_label.kind` character.
84    #[must_use]
85    pub fn as_char(self) -> char {
86        match self {
87            Self::Vertex => 'v',
88            Self::Edge => 'e',
89        }
90    }
91
92    /// The reserved label id used for unlabeled entities of this kind.
93    #[must_use]
94    pub fn default_label_id(self) -> u32 {
95        match self {
96            Self::Vertex => VERTEX_DEFAULT_LABEL_ID,
97            Self::Edge => EDGE_DEFAULT_LABEL_ID,
98        }
99    }
100
101    /// The reserved AGE default label name for this kind.
102    #[must_use]
103    pub fn default_label_name(self) -> &'static str {
104        match self {
105            Self::Vertex => VERTEX_DEFAULT_LABEL_NAME,
106            Self::Edge => EDGE_DEFAULT_LABEL_NAME,
107        }
108    }
109
110    fn entity_noun(self) -> &'static str {
111        match self {
112            Self::Vertex => "vertices",
113            Self::Edge => "edges",
114        }
115    }
116}
117
118/// One `ag_label` catalog entry of a graph.
119#[derive(Debug, Clone, PartialEq, Eq)]
120pub struct GraphLabelInfo {
121    /// Label name; the default labels use the reserved AGE names.
122    pub name: String,
123    /// AGE label id (the high 16 bits of every graphid under the label).
124    pub id: u32,
125    /// Vertex or edge label.
126    pub kind: LabelKind,
127    /// Last allocated per-label sequence value (0 when nothing was
128    /// allocated yet).
129    pub last_sequence: u64,
130}
131
132/// Per-graph AGE label registry: label name -> label id plus the
133/// per-label id sequences. Serializable so engines can persist it in
134/// catalog metadata and restore deterministic id allocation.
135#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
136#[serde(default)]
137pub struct GraphLabelRegistry {
138    /// Persistent allocation identity, preserved by rename. Zero denotes a legacy registry or an in-memory graph.
139    pub allocation_id: [u8; 16],
140    /// Label name -> AGE label id. Vertex and edge labels share the
141    /// namespace-wide counter; the reserved names for ids 1 / 2 are
142    /// not stored here (empty labels map onto them implicitly).
143    pub labels: BTreeMap<String, u32>,
144    /// Label name -> vertex or edge kind. Registries persisted before
145    /// kinds were recorded fill this map from the stored entities.
146    pub kinds: BTreeMap<String, LabelKind>,
147    /// Label id -> last allocated per-label sequence value.
148    pub sequences: BTreeMap<u32, u64>,
149    /// AGE label ids whose relations were removed through `drop_label`.
150    /// Tombstones are persisted because edge rows can outlive the vertex
151    /// label relations that owned their endpoints. Registries written before
152    /// this field existed deserialize as an empty set.
153    pub dropped_label_ids: BTreeSet<u32>,
154    /// Next label id handed to a previously unseen label.
155    pub next_label_id: u32,
156}
157
158impl Default for GraphLabelRegistry {
159    fn default() -> Self {
160        Self {
161            allocation_id: [0; 16],
162            labels: BTreeMap::new(),
163            kinds: BTreeMap::new(),
164            sequences: BTreeMap::new(),
165            dropped_label_ids: BTreeSet::new(),
166            next_label_id: FIRST_USER_LABEL_ID,
167        }
168    }
169}
170
171impl GraphLabelRegistry {
172    /// Resolve the label id for an entity of `kind`, allocating a new
173    /// user label on first use. Empty labels map onto the reserved
174    /// default label of the kind. Using a label registered for the
175    /// other kind fails exactly like AGE's `CREATE` transform.
176    pub(crate) fn label_id(&mut self, label: &str, kind: LabelKind) -> GraphStoreResult<u32> {
177        if label.is_empty() {
178            self.require_default_label(kind)?;
179            return Ok(kind.default_label_id());
180        }
181        // The reserved AGE names always denote the default labels, so they
182        // resolve to the reserved ids instead of allocating a user label.
183        for reserved in [LabelKind::Vertex, LabelKind::Edge] {
184            if label == reserved.default_label_name() {
185                Self::require_kind(label, reserved, kind)?;
186                self.require_default_label(reserved)?;
187                return Ok(reserved.default_label_id());
188            }
189        }
190        if let Some(existing) = self.kinds.get(label).copied() {
191            Self::require_kind(label, existing, kind)?;
192        }
193        if let Some(id) = self.labels.get(label) {
194            if *id > MAX_GRAPHID_LABEL_ID {
195                return Err(GraphStoreError::IdExhausted(format!(
196                    "persisted label id {id} exceeds {MAX_GRAPHID_LABEL_ID}"
197                )));
198            }
199            self.kinds.entry(label.to_string()).or_insert(kind);
200            return Ok(*id);
201        }
202        self.require_default_label(kind)?;
203        let id = self.allocate_label_id()?;
204        self.labels.insert(label.to_string(), id);
205        self.kinds.insert(label.to_string(), kind);
206        Ok(id)
207    }
208
209    fn require_default_label(&self, kind: LabelKind) -> GraphStoreResult<()> {
210        if self.dropped_label_ids.contains(&kind.default_label_id()) {
211            return Err(GraphStoreError::InvalidMutation(format!(
212                "default label {} does not exist",
213                kind.default_label_name()
214            )));
215        }
216        Ok(())
217    }
218
219    fn require_kind(
220        label: &str,
221        existing: LabelKind,
222        requested: LabelKind,
223    ) -> GraphStoreResult<()> {
224        if existing == requested {
225            return Ok(());
226        }
227        Err(GraphStoreError::InvalidMutation(format!(
228            "label {label} is for {}, not {}",
229            existing.entity_noun(),
230            requested.entity_noun()
231        )))
232    }
233
234    fn allocate_label_id(&mut self) -> GraphStoreResult<u32> {
235        let id = self.next_label_id;
236        if id > MAX_GRAPHID_LABEL_ID {
237            return Err(GraphStoreError::IdExhausted(format!(
238                "label id {id} exceeds {MAX_GRAPHID_LABEL_ID}"
239            )));
240        }
241        self.next_label_id = id
242            .checked_add(1)
243            .ok_or_else(|| GraphStoreError::IdExhausted("label id counter overflow".to_string()))?;
244        Ok(id)
245    }
246
247    /// Whether `label` names a registered user label or a reserved
248    /// default label.
249    #[must_use]
250    pub fn contains_label(&self, label: &str) -> bool {
251        if label == VERTEX_DEFAULT_LABEL_NAME {
252            return !self
253                .dropped_label_ids
254                .contains(&LabelKind::Vertex.default_label_id());
255        }
256        if label == EDGE_DEFAULT_LABEL_NAME {
257            return !self
258                .dropped_label_ids
259                .contains(&LabelKind::Edge.default_label_id());
260        }
261        self.labels.contains_key(label)
262    }
263
264    /// The kind of a registered or default label. A user label persisted
265    /// before kinds were recorded, and whose entities are all gone, reports
266    /// as a vertex label until its next use records the kind.
267    #[must_use]
268    pub fn label_kind(&self, label: &str) -> Option<LabelKind> {
269        if label == VERTEX_DEFAULT_LABEL_NAME {
270            return self.contains_label(label).then_some(LabelKind::Vertex);
271        }
272        if label == EDGE_DEFAULT_LABEL_NAME {
273            return self.contains_label(label).then_some(LabelKind::Edge);
274        }
275        if !self.labels.contains_key(label) {
276            return None;
277        }
278        Some(self.kinds.get(label).copied().unwrap_or(LabelKind::Vertex))
279    }
280
281    /// Register an empty user label ahead of any entity, as
282    /// `create_vlabel` / `create_elabel` do. Returns the new label id;
283    /// `None` when the name is already a label of this graph.
284    pub fn register_label(
285        &mut self,
286        label: &str,
287        kind: LabelKind,
288    ) -> GraphStoreResult<Option<u32>> {
289        if self.contains_label(label) {
290            return Ok(None);
291        }
292        self.require_default_label(kind)?;
293        if label == VERTEX_DEFAULT_LABEL_NAME || label == EDGE_DEFAULT_LABEL_NAME {
294            return Err(GraphStoreError::InvalidMutation(format!(
295                "default label {label} cannot be recreated without recreating the graph"
296            )));
297        }
298        let id = self.allocate_label_id()?;
299        self.labels.insert(label.to_string(), id);
300        self.kinds.insert(label.to_string(), kind);
301        Ok(Some(id))
302    }
303
304    /// Forget a label. Default labels leave a durable tombstone so the graph
305    /// can continue to exist without their AGE relations. Returns the
306    /// released label id, or `None` when the label is not registered.
307    pub fn remove_label(&mut self, label: &str) -> Option<u32> {
308        for kind in [LabelKind::Vertex, LabelKind::Edge] {
309            if label == kind.default_label_name() {
310                if !self.dropped_label_ids.insert(kind.default_label_id()) {
311                    return None;
312                }
313                self.sequences.remove(&kind.default_label_id());
314                return Some(kind.default_label_id());
315            }
316        }
317        let id = self.labels.remove(label)?;
318        self.kinds.remove(label);
319        self.sequences.remove(&id);
320        self.dropped_label_ids.insert(id);
321        Some(id)
322    }
323
324    /// Every present label of the graph in `ag_label` order: surviving
325    /// defaults first, then user labels by ascending label id.
326    #[must_use]
327    pub fn labels(&self) -> Vec<GraphLabelInfo> {
328        let mut out = Vec::new();
329        for kind in [LabelKind::Vertex, LabelKind::Edge] {
330            if !self.dropped_label_ids.contains(&kind.default_label_id()) {
331                out.push(GraphLabelInfo {
332                    name: kind.default_label_name().to_string(),
333                    id: kind.default_label_id(),
334                    kind,
335                    last_sequence: self
336                        .sequences
337                        .get(&kind.default_label_id())
338                        .copied()
339                        .unwrap_or(0),
340                });
341            }
342        }
343        let mut user: Vec<GraphLabelInfo> = self
344            .labels
345            .iter()
346            .map(|(name, id)| GraphLabelInfo {
347                name: name.clone(),
348                id: *id,
349                kind: self.label_kind(name).unwrap_or(LabelKind::Vertex),
350                last_sequence: self.sequences.get(id).copied().unwrap_or(0),
351            })
352            .collect();
353        user.sort_by_key(|label| label.id);
354        out.extend(user);
355        out
356    }
357
358    pub(crate) fn next_sequence(&mut self, label_id: u32) -> GraphStoreResult<u64> {
359        let current = self.sequences.get(&label_id).copied().unwrap_or(0);
360        let next = current.checked_add(1).ok_or_else(|| {
361            GraphStoreError::IdExhausted(format!(
362                "sequence counter overflow for label id {label_id}"
363            ))
364        })?;
365        if next > MAX_GRAPHID_SEQUENCE {
366            return Err(GraphStoreError::IdExhausted(format!(
367                "sequence {next} exceeds {MAX_GRAPHID_SEQUENCE} for label id {label_id}"
368            )));
369        }
370        self.sequences.insert(label_id, next);
371        Ok(next)
372    }
373
374    /// Fold an existing entity id into the allocation watermarks and report whether the registry changed.
375    pub(crate) fn observe(&mut self, label: &str, id: u64, kind: LabelKind) -> bool {
376        let label_id = graphid_label_id(id);
377        if label_id == 0 {
378            // Plain counter ids contain no AGE label allocation to retain.
379            return false;
380        }
381        let mut changed = false;
382        if !label.is_empty() && label_id >= FIRST_USER_LABEL_ID {
383            if let std::collections::btree_map::Entry::Vacant(entry) =
384                self.labels.entry(label.to_string())
385            {
386                entry.insert(label_id);
387                changed = true;
388            }
389            if let std::collections::btree_map::Entry::Vacant(entry) =
390                self.kinds.entry(label.to_string())
391            {
392                entry.insert(kind);
393                changed = true;
394            }
395        }
396        changed |= self.dropped_label_ids.remove(&label_id);
397        let seq = graphid_sequence(id);
398        match self.sequences.entry(label_id) {
399            std::collections::btree_map::Entry::Vacant(entry) => {
400                entry.insert(seq);
401                changed = true;
402            }
403            std::collections::btree_map::Entry::Occupied(mut entry) if seq > *entry.get() => {
404                entry.insert(seq);
405                changed = true;
406            }
407            std::collections::btree_map::Entry::Occupied(_) => {}
408        }
409        if label_id >= self.next_label_id {
410            self.next_label_id = label_id + 1;
411            changed = true;
412        }
413        changed
414    }
415
416    /// Merge another registry (e.g. persisted metadata) into this one,
417    /// keeping the larger sequence values and label id watermark.
418    pub fn merge(&mut self, other: &GraphLabelRegistry) {
419        for (label, id) in &other.labels {
420            self.labels.entry(label.clone()).or_insert(*id);
421        }
422        for (label, kind) in &other.kinds {
423            self.kinds.entry(label.clone()).or_insert(*kind);
424        }
425        for (label_id, seq) in &other.sequences {
426            let entry = self.sequences.entry(*label_id).or_insert(0);
427            if *seq > *entry {
428                *entry = *seq;
429            }
430        }
431        self.dropped_label_ids
432            .extend(other.dropped_label_ids.iter().copied());
433        if other.next_label_id > self.next_label_id {
434            self.next_label_id = other.next_label_id;
435        }
436    }
437}