1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
//! Secondary-label API for [`DirGraph`] — the choke point every label
//! mutation and read routes through.
//!
//! Split out of `dir_graph/mod.rs` to keep that file under its line ceiling,
//! and because labels are a genuinely separable concern: they are the one
//! piece of node state that does **not** live in the storage backend.
//! `NodeData` carries no labels at all; `DirGraph::secondary_label_index` is
//! the canonical store.
//!
//! That placement is why this module exists as a choke point rather than as
//! plain field access. Sitting above storage means no `GraphWrite` call can
//! describe a label change, so anything that needs to observe one has to be
//! notified here explicitly — statement rollback (the undo journal) and
//! durability (the WAL capture wrapper) both hook these two mutators. A label
//! write that bypassed them would be invisible to both: silently
//! unrollbackable and silently lost on crash recovery.
use petgraph::graph::NodeIndex;
use crate::graph::schema::{DirGraph, InternedKey};
impl DirGraph {
/// Capture a node's pre-edit state for change data capture, **before** a
/// label edit lands.
///
/// This is the label half of the side-channel rule: the capture wrapper
/// sits below storage and cannot see the label index at all, and
/// `note_recorded_node_labels` fires *after* the bucket edit — so a
/// before-image read from there would report the post-edit label set under
/// the name `before`. Reading here, ahead of the edit, is the only place
/// the old set still exists.
///
/// Two cases, and the second is why this is not just "capture if absent":
///
/// - The node has no image yet (this label edit is its first touch in the
/// commit): capture the whole entity, labels included.
/// - The node was first touched by a *property* write, whose image could
/// not see labels: backfill just the labels. They are still the
/// commit-start set, because this is the commit's first label edit on
/// the node — a later one finds `labels` already filled and leaves it.
fn capture_label_before_image(&mut self, idx: NodeIndex) {
if !self.graph.captures_before_images() {
return;
}
let labels = self.secondary_label_names(idx);
if !self.graph.needs_node_before_image(idx) {
self.graph.backfill_node_before_labels(idx, labels);
return;
}
use crate::graph::storage::GraphRead;
let Some(image) =
self.graph
.node_view(idx)
.map(|view| crate::graph::storage::recording::BeforeImage {
title: view.title().into_owned(),
properties: view.property_pairs(),
labels: Some(labels),
})
else {
return;
};
self.graph.note_node_before_image(idx, image);
}
/// Add a secondary label to a node. Choke-point API for label
/// mutations — every mutation site routes through here so the
/// `secondary_label_index` stays canonical across all three
/// backends. NodeData itself never carries extra labels; the
/// inverted index is the single source of truth.
///
/// Returns `true` if the label was added, `false` if it was already
/// present (idempotent) or equal to the primary type.
pub fn add_node_label(&mut self, idx: NodeIndex, label: InternedKey) -> bool {
use crate::graph::storage::GraphRead;
let primary = match GraphRead::node_type_of(&self.graph, idx) {
Some(k) => k,
None => return false,
};
if primary == label {
return false;
}
let bucket_was_new = !self.secondary_label_index.contains_key(&label);
if self
.secondary_label_index
.get(&label)
.is_some_and(|bucket| bucket.contains(&idx))
{
// Idempotent: the node already carries the label, so nothing is
// written and nothing may be captured.
return false;
}
// Before the edit, and only now that one is certain: the label set
// this write is about to change is what a `before` image must report.
self.capture_label_before_image(idx);
self.secondary_label_index
.entry(label)
.or_default()
.push(idx);
self.has_secondary_labels = true;
// Statement-rollback capture: the label index lives above storage, so
// the backend's `GraphWrite` seam cannot see this edit.
if let Some(journal) = self.graph.undo_journal_mut() {
journal.note_bucket_appended(
crate::graph::storage::undo::BucketId::SecondaryLabel(label),
idx,
bucket_was_new,
);
}
// WAL capture, for the same reason: no `GraphWrite` call describes a
// label change, so a durable graph would otherwise lose it on replay.
self.graph.note_recorded_node_labels(idx);
true
}
/// Remove a secondary label from a node. Choke-point API for label
/// mutations.
///
/// Returns `Ok(true)` if removed, `Ok(false)` if the node never had
/// the label, `Err(...)` if `label` is the primary type (use
/// `SET n.type = ...` to retype instead).
pub fn remove_node_label(
&mut self,
idx: NodeIndex,
label: InternedKey,
) -> Result<bool, String> {
use crate::graph::storage::GraphRead;
let Some(primary) = GraphRead::node_type_of(&self.graph, idx) else {
return Ok(false);
};
if primary == label {
return Err(
"Cannot remove a node's primary label via REMOVE n:Label; use \
SET n.type = 'NewType' to retype."
.to_string(),
);
}
let Some(bucket) = self.secondary_label_index.get(&label) else {
return Ok(false);
};
// Positional removal rather than `retain`: `add_node_label` rejects
// duplicates, so there is at most one match, and the position is what
// statement rollback needs to restore the bucket's original order.
let position = bucket.iter().position(|&i| i == idx);
if position.is_some() {
// Before the edit, and only when there is one to make: a REMOVE of
// a label the node never had changes nothing, so it must capture
// nothing — an image offered here would claim a first touch for a
// write that is not going to happen.
self.capture_label_before_image(idx);
}
let bucket = self
.secondary_label_index
.get_mut(&label)
.expect("bucket present, just read above");
if let Some(pos) = position {
bucket.remove(pos);
}
if position.is_some() && bucket.is_empty() {
self.secondary_label_index.remove(&label);
}
if self.secondary_label_index.is_empty() {
self.has_secondary_labels = false;
}
if let Some(pos) = position {
if let Some(journal) = self.graph.undo_journal_mut() {
journal.note_bucket_removed(
crate::graph::storage::undo::BucketId::SecondaryLabel(label),
idx,
pos,
);
}
// WAL capture — see `add_node_label`. The op carries the whole
// remaining set, so a removal replays as correctly as an add.
self.graph.note_recorded_node_labels(idx);
}
Ok(position.is_some())
}
/// Return a node's labels as `[primary, ...extras]`. Returns an
/// empty Vec if the node is missing. Consumers that only need the
/// primary type should keep using `GraphRead::node_type_of` (one
/// InternedKey lookup, no allocation).
///
/// Reads secondaries from `secondary_label_index` (the canonical
/// source maintained by the choke-point API), which is an inverted
/// index — it has no record of the order the labels were declared in.
/// Secondaries are therefore returned **sorted by label name**, with the
/// primary type first.
///
/// Sorting is not cosmetic: iterating the index directly leaked
/// `HashMap` iteration order into `labels(n)`, so two graphs holding
/// identical data disagreed about the order of a node's labels (each
/// `HashMap` seeds its own `RandomState`). That made results
/// irreproducible across processes and across two instances of the same
/// graph. Name order is stable everywhere and needs no extra state.
///
/// Single-label graphs short-circuit on `has_secondary_labels` and never
/// reach the sort.
pub fn node_labels(&self, idx: NodeIndex) -> Vec<InternedKey> {
use crate::graph::storage::GraphRead;
let Some(primary) = GraphRead::node_type_of(&self.graph, idx) else {
return Vec::new();
};
let extras = self.secondary_labels(idx);
let mut labels = Vec::with_capacity(extras.len() + 1);
labels.push(primary);
labels.extend(extras);
labels
}
/// A node's **secondary** labels alone, sorted by label name — the
/// ordering half of [`node_labels`](Self::node_labels), factored out so
/// the primary-first-then-name-sorted guarantee has exactly one
/// implementation. Empty when the node has none (or does not exist).
pub fn secondary_labels(&self, idx: NodeIndex) -> Vec<InternedKey> {
if !self.has_secondary_labels {
return Vec::new();
}
let mut extras: Vec<InternedKey> = self
.secondary_label_index
.iter()
.filter(|(_, bucket)| bucket.contains(&idx))
.map(|(&key, _)| key)
.collect();
extras.sort_unstable_by(|a, b| self.interner.resolve(*a).cmp(self.interner.resolve(*b)));
extras
}
/// [`secondary_labels`](Self::secondary_labels) resolved to owned
/// names. This is what the WAL persists — a log outlives the interner
/// that produced its keys, so labels cross the durability boundary as
/// strings, in the same order the live graph reports them.
pub fn secondary_label_names(&self, idx: NodeIndex) -> Vec<String> {
self.secondary_labels(idx)
.into_iter()
.map(|key| self.interner.resolve(key).to_string())
.collect()
}
/// All nodes carrying `label` as EITHER their primary type or a
/// secondary label — the canonical "candidates for `MATCH (n:label)`"
/// set. This is the single source of truth that every label-based
/// candidate-selection site should route through, mirroring
/// `PatternExecutor::find_matching_nodes`'s `needs_secondary_path`.
///
/// Single-label fast path: when no node anywhere carries a secondary
/// label, this returns exactly `type_indices[label].to_vec()` — byte
/// for byte what every primary-only call site produced before
/// multi-label existed, so single-label performance is unchanged.
///
/// The choke-point API (`add_node_label`) forbids a node holding the
/// same key as both primary and secondary, so the union is
/// duplicate-free.
pub fn nodes_with_label(&self, label: &str) -> Vec<NodeIndex> {
let mut out = self
.type_indices
.get(label)
.map(|v| v.to_vec())
.unwrap_or_default();
if self.has_secondary_labels {
if let Some(secondary) = self
.secondary_label_index
.get(&InternedKey::from_str(label))
{
out.extend(secondary.iter().copied());
}
}
out
}
/// True if `idx` carries `key` as its primary type or a secondary
/// label. Membership test companion to `nodes_with_label` for sites
/// that filter an existing candidate set rather than enumerate one.
pub fn node_has_label(&self, idx: NodeIndex, key: InternedKey) -> bool {
use crate::graph::storage::GraphRead;
if GraphRead::node_type_of(&self.graph, idx) == Some(key) {
return true;
}
self.has_secondary_labels
&& self
.secondary_label_index
.get(&key)
.is_some_and(|bucket| bucket.contains(&idx))
}
}