1use super::{BTreeMap, BTreeSet, Deserialize, GraphStoreError, GraphStoreResult, Serialize};
10
11use crate::age_names::{EDGE_DEFAULT_LABEL_NAME, VERTEX_DEFAULT_LABEL_NAME};
12
13pub const GRAPHID_LABEL_SHIFT: u32 = 48;
16
17pub const VERTEX_DEFAULT_LABEL_ID: u32 = 1;
19
20pub const EDGE_DEFAULT_LABEL_ID: u32 = 2;
22
23pub const FIRST_USER_LABEL_ID: u32 = 3;
25
26pub 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
43pub 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#[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#[must_use]
67pub fn graphid_sequence(id: u64) -> u64 {
68 id & ((1 << GRAPHID_LABEL_SHIFT) - 1)
69}
70
71#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
73pub enum LabelKind {
74 #[serde(rename = "v")]
76 Vertex,
77 #[serde(rename = "e")]
79 Edge,
80}
81
82impl LabelKind {
83 #[must_use]
85 pub fn as_char(self) -> char {
86 match self {
87 Self::Vertex => 'v',
88 Self::Edge => 'e',
89 }
90 }
91
92 #[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 #[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#[derive(Debug, Clone, PartialEq, Eq)]
120pub struct GraphLabelInfo {
121 pub name: String,
123 pub id: u32,
125 pub kind: LabelKind,
127 pub last_sequence: u64,
130}
131
132#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
136#[serde(default)]
137pub struct GraphLabelRegistry {
138 pub allocation_id: [u8; 16],
140 pub labels: BTreeMap<String, u32>,
144 pub kinds: BTreeMap<String, LabelKind>,
147 pub sequences: BTreeMap<u32, u64>,
149 pub dropped_label_ids: BTreeSet<u32>,
154 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 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 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 #[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 #[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 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 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 #[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 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 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 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}