Skip to main content

oxilite_cypher/
exec.rs

1//! Execution of a Cypher statement as a sans-IO step machine.
2//!
3//! [`CypherJob`] asks its driver for three kinds of work: a SPARQL query (the SQL part of the
4//! statement, run by the store so sync backends keep the spareval fallback), plain SQL reads
5//! on term ids (materializing nodes and relationships, probing existing edges before
6//! writing), and one atomic write request. Drivers exist for the blocking store, the async
7//! store (D1) and a core-level [`oxilite_core::Job`] adapter used by the wasm engine.
8//!
9//! Writes are computed in Rust from the rows of the read: the statement's effect is a set of
10//! quads to delete and insert, applied as one atomic request (one D1 batch). New nodes get
11//! fresh IRIs minted in Rust, so no read-back is needed.
12//!
13// @lat: [[architecture#Property graph frontend]]
14
15use crate::ast::*;
16use crate::error::{CypherError, Result};
17use crate::eval::{eval, eval_pred, Acc, Env, Row};
18use crate::lower::{Bind, RelVars};
19use crate::plan::{Plan, TailOp};
20use crate::schema::Shapes;
21use crate::value::{GroupKey, Node, Params, Path, Relationship, Value, REIFIES};
22use crate::vocab::Vocabulary;
23use crate::{CypherOptions, MultiValue};
24use oxilite_core::encoding::{named_node_id, rdf_type_id, subject_id, triple_id};
25use oxilite_core::job::Job;
26use oxilite_core::query::QueryOutput;
27use oxilite_core::resolve::TermResolver;
28use oxilite_core::sql::col;
29use oxilite_core::writer::EncodedQuads;
30use oxilite_core::{Capabilities, Request, Response, Statement, Step};
31use oxrdf::vocab::rdf;
32use oxrdf::{GraphName, NamedNode, NamedOrBlankNode, Quad, Term, Triple, Variable};
33use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
34
35/// What a [`CypherJob`] needs next.
36#[derive(Debug)]
37#[allow(clippy::large_enum_variant)]
38pub enum CypherStep {
39    /// Evaluate this SPARQL query with these options and resume with [`StepInput::Output`].
40    Query(spargebra::Query, oxilite_core::QueryOptions),
41    /// Run this read request and resume with [`StepInput::Response`].
42    Sql(Request),
43    /// Run this atomic write request and resume with [`StepInput::Response`].
44    Write(Request),
45    Done(CypherResult),
46}
47
48/// The input resuming a [`CypherJob`].
49#[derive(Debug)]
50pub enum StepInput {
51    Output(QueryOutput),
52    Response(Response),
53}
54
55/// Counters of what a statement changed.
56#[derive(Debug, Clone, Default, PartialEq, Eq)]
57pub struct WriteStats {
58    pub nodes_created: u64,
59    pub nodes_deleted: u64,
60    pub relationships_created: u64,
61    pub relationships_deleted: u64,
62    pub properties_set: u64,
63    pub labels_added: u64,
64    pub labels_removed: u64,
65}
66
67impl WriteStats {
68    pub fn is_empty(&self) -> bool {
69        *self == Self::default()
70    }
71}
72
73/// The result of a Cypher statement.
74#[derive(Debug, Clone, PartialEq)]
75pub struct CypherResult {
76    pub columns: Vec<String>,
77    pub rows: Vec<Vec<Value>>,
78    pub stats: WriteStats,
79    /// A write changed ontology triples (the store must reload its reasoning facts).
80    pub schema_changed: bool,
81}
82
83impl CypherResult {
84    /// Rows as maps from column name to value.
85    pub fn records(&self) -> Vec<BTreeMap<String, Value>> {
86        self.rows
87            .iter()
88            .map(|r| {
89                self.columns
90                    .iter()
91                    .cloned()
92                    .zip(r.iter().cloned())
93                    .collect()
94            })
95            .collect()
96    }
97
98    /// The single value of a one-row, one-column result.
99    pub fn single(&self) -> Option<&Value> {
100        match (self.rows.as_slice(), self.columns.len()) {
101            ([row], 1) => row.first(),
102            _ => None,
103        }
104    }
105
106    pub fn to_json(&self) -> serde_json::Value {
107        serde_json::json!({
108            "columns": self.columns,
109            "rows": self.rows.iter().map(|r| r.iter().map(Value::to_json).collect::<Vec<_>>()).collect::<Vec<_>>(),
110            "stats": {
111                "nodesCreated": self.stats.nodes_created,
112                "nodesDeleted": self.stats.nodes_deleted,
113                "relationshipsCreated": self.stats.relationships_created,
114                "relationshipsDeleted": self.stats.relationships_deleted,
115                "propertiesSet": self.stats.properties_set,
116                "labelsAdded": self.stats.labels_added,
117                "labelsRemoved": self.stats.labels_removed,
118            },
119        })
120    }
121}
122
123// ----- SQL fetches on term ids -----
124
125const CHUNK: usize = 300;
126
127fn id_list(ids: &[i64]) -> String {
128    ids.iter()
129        .map(ToString::to_string)
130        .collect::<Vec<_>>()
131        .join(",")
132}
133
134fn spo_cols(caps: &Capabilities, t: &str) -> String {
135    ["s", "p", "o"]
136        .iter()
137        .map(|c| {
138            if caps.int64_as_text {
139                format!("CAST({t}.{c} AS TEXT)")
140            } else {
141                format!("{t}.{c}")
142            }
143        })
144        .collect::<Vec<_>>()
145        .join(", ")
146}
147
148enum FetchState {
149    Start,
150    Main,
151    Resolving,
152}
153
154/// Runs statements returning `(s, p, o)` id rows — optionally followed by the `terms`
155/// columns of `p` (lex) and `o` (lex, dt, lang, dir) — then decodes every id, looking up
156/// only what the rows did not carry.
157struct QuadFetch {
158    stmts: Vec<Statement>,
159    rows: Vec<[i64; 3]>,
160    known: HashMap<i64, Term>,
161    resolver: TermResolver,
162    caps: Capabilities,
163    state: FetchState,
164}
165
166impl QuadFetch {
167    fn new(stmts: Vec<Statement>, caps: &Capabilities) -> Self {
168        Self {
169            stmts,
170            rows: Vec::new(),
171            known: HashMap::new(),
172            resolver: TermResolver::default(),
173            caps: caps.clone(),
174            state: FetchState::Start,
175        }
176    }
177
178    fn with_known(mut self, known: HashMap<i64, Term>) -> Self {
179        self.known = known;
180        self
181    }
182
183    /// Also decodes these ids (see [`Self::decoded`]).
184    fn with_extra(mut self, ids: impl IntoIterator<Item = i64>) -> Self {
185        for id in ids {
186            self.want(id);
187        }
188        self
189    }
190
191    /// Every id decoded so far.
192    fn decoded(&self, ids: impl IntoIterator<Item = i64>) -> HashMap<i64, Term> {
193        ids.into_iter()
194            .filter_map(|id| self.get(id).ok().map(|t| (id, t)))
195            .collect()
196    }
197
198    fn get(&self, id: i64) -> oxilite_core::Result<Term> {
199        match self.known.get(&id) {
200            Some(t) => Ok(t.clone()),
201            None => self.resolver.get(id),
202        }
203    }
204
205    fn want(&mut self, id: i64) {
206        if let std::collections::hash_map::Entry::Vacant(e) = self.known.entry(id) {
207            match oxilite_core::encoding::decode_inline(id) {
208                Some(t) => {
209                    e.insert(t);
210                }
211                None => self.resolver.want(id),
212            }
213        }
214    }
215
216    fn next(&mut self) -> oxilite_core::Result<Step<Vec<[Term; 3]>>> {
217        if let Some(r) = self.resolver.request(&self.caps) {
218            return Ok(Step::Execute(r));
219        }
220        let mut out = Vec::with_capacity(self.rows.len());
221        for [s, p, o] in &self.rows {
222            out.push([self.get(*s)?, self.get(*p)?, self.get(*o)?]);
223        }
224        Ok(Step::Done(out))
225    }
226}
227
228/// `SELECT` list and joins returning the terms of `p` and `o` with a quad row.
229fn with_terms(caps: &Capabilities, t: &str) -> (String, String) {
230    (
231        format!(
232            "{}, tp.lex, tt.lex, tt.dt, tt.lang, tt.dir",
233            spo_cols(caps, t)
234        ),
235        format!(" LEFT JOIN terms tp ON tp.id = {t}.p LEFT JOIN terms tt ON tt.id = {t}.o"),
236    )
237}
238
239impl Job for QuadFetch {
240    type Output = Vec<[Term; 3]>;
241
242    fn step(&mut self, response: Option<Response>) -> oxilite_core::Result<Step<Self::Output>> {
243        match self.state {
244            FetchState::Start => {
245                if self.stmts.is_empty() {
246                    self.state = FetchState::Resolving;
247                    return self.next();
248                }
249                self.state = FetchState::Main;
250                Ok(Step::Execute(Request::read(std::mem::take(
251                    &mut self.stmts,
252                ))))
253            }
254            FetchState::Main => {
255                let response = response
256                    .ok_or_else(|| oxilite_core::Error::Other("missing response".into()))?;
257                for rs in response {
258                    for row in rs.rows {
259                        let get = |i| {
260                            col(&row, i)?
261                                .as_i64()
262                                .ok_or_else(|| oxilite_core::Error::corrupted("bad id"))
263                        };
264                        let ids = [get(0)?, get(1)?, get(2)?];
265                        if row.len() >= 8 {
266                            let text = |i: usize| row.get(i).and_then(|v| v.clone().into_string());
267                            if let Some(lex) = text(3) {
268                                if let Ok(t) = oxilite_core::encoding::decode_row(
269                                    ids[1], lex, None, None, None,
270                                ) {
271                                    self.known.insert(ids[1], t);
272                                }
273                            }
274                            if let Some(lex) = text(4) {
275                                let dir = row.get(7).and_then(|v| v.as_i64());
276                                if let Ok(t) = oxilite_core::encoding::decode_row(
277                                    ids[2],
278                                    lex,
279                                    text(5),
280                                    text(6),
281                                    dir,
282                                ) {
283                                    self.known.insert(ids[2], t);
284                                }
285                            }
286                        }
287                        for id in ids {
288                            self.want(id);
289                        }
290                        self.rows.push(ids);
291                    }
292                }
293                self.state = FetchState::Resolving;
294                self.next()
295            }
296            FetchState::Resolving => {
297                let response = response
298                    .ok_or_else(|| oxilite_core::Error::Other("missing response".into()))?;
299                self.resolver.absorb(response)?;
300                self.next()
301            }
302        }
303    }
304}
305
306// ----- graph state -----
307
308/// Labels and literal properties of a node or relationship (by reifier).
309#[derive(Debug, Clone, Default)]
310struct Entity {
311    labels: Vec<NamedNode>,
312    props: Vec<(NamedNode, Term)>,
313    deleted: bool,
314}
315
316#[derive(Debug, Clone)]
317struct RelCreate {
318    s: NamedOrBlankNode,
319    p: NamedNode,
320    o: NamedOrBlankNode,
321    rid: NamedOrBlankNode,
322    dropped: bool,
323}
324
325#[derive(Debug, Clone)]
326struct RelDelete {
327    triple: Triple,
328    rid: Option<NamedOrBlankNode>,
329}
330
331#[derive(Debug, Default)]
332struct GraphState {
333    nodes: HashMap<NamedOrBlankNode, Entity>,
334    rels: HashMap<NamedOrBlankNode, Entity>,
335    fetched: HashSet<i64>,
336    created_nodes: HashSet<NamedOrBlankNode>,
337    created_rels: Vec<RelCreate>,
338    provisional: HashSet<NamedOrBlankNode>,
339    /// Unreified relationships that got a reifier in this statement.
340    reified: HashMap<Triple, NamedOrBlankNode>,
341    /// Reifiers that turned out unnecessary (a single plain relationship was created).
342    dropped: HashSet<NamedOrBlankNode>,
343    node_deletes: Vec<(NamedOrBlankNode, bool)>,
344    rel_deletes: Vec<RelDelete>,
345    touched: BTreeSet<String>,
346    touched_nodes: Vec<NamedOrBlankNode>,
347    ops: HashMap<Quad, bool>,
348    order: Vec<Quad>,
349    merge_cache: HashMap<String, Vec<(String, Value)>>,
350    stats: WriteStats,
351    counter: u64,
352    seed: Option<String>,
353}
354
355impl GraphState {
356    fn set(&mut self, q: Quad, present: bool) {
357        if self.ops.insert(q.clone(), present).is_none() {
358            self.order.push(q);
359        }
360    }
361
362    fn touch(&mut self, n: &NamedOrBlankNode) {
363        if self.touched.insert(crate::value::subject_str(n)) {
364            self.touched_nodes.push(n.clone());
365        }
366    }
367}
368
369fn to_subject(t: &Term) -> Option<NamedOrBlankNode> {
370    match t {
371        Term::NamedNode(n) => Some(n.clone().into()),
372        Term::BlankNode(b) => Some(b.clone().into()),
373        _ => None,
374    }
375}
376
377fn subject_term(s: &NamedOrBlankNode) -> Term {
378    match s {
379        NamedOrBlankNode::NamedNode(n) => n.clone().into(),
380        NamedOrBlankNode::BlankNode(b) => b.clone().into(),
381    }
382}
383
384/// `rdfs:Resource`: the marker type of nodes created by Cypher.
385pub(crate) const RESOURCE: &str = "http://www.w3.org/2000/01/rdf-schema#Resource";
386
387fn reifies() -> NamedNode {
388    NamedNode::new_unchecked(REIFIES)
389}
390
391fn is_rel_triple(p: &NamedNode, o: &Term) -> bool {
392    p.as_ref() != rdf::TYPE
393        && p.as_str() != REIFIES
394        && matches!(o, Term::NamedNode(_) | Term::BlankNode(_))
395}
396
397// ----- the job -----
398
399#[derive(Debug, Clone, Copy, PartialEq, Eq)]
400enum State {
401    Start,
402    Shapes,
403    Main,
404    Comprehension,
405    Bfs,
406    Materialize,
407    Fixup1,
408    Fixup2,
409    Write,
410    Finished,
411}
412
413/// A Cypher statement being executed. See the module documentation.
414pub struct CypherJob {
415    plan: Plan,
416    params: Params,
417    vocab: Vocabulary,
418    opts: CypherOptions,
419    caps: Capabilities,
420    graph: GraphName,
421    state: State,
422    part: usize,
423    raw: Vec<HashMap<Variable, Term>>,
424    outputs: Vec<Vec<Value>>,
425    g: GraphState,
426    fetch: Option<QuadFetch>,
427    shapes: Option<std::sync::Arc<Shapes>>,
428    fix: FixData,
429    schema_changed: bool,
430    bfs: Option<Bfs>,
431    /// Paths found per shortest-path pattern: (from, to) ids → id sequences.
432    found: Vec<HashMap<(i64, i64), Vec<IdPath>>>,
433    decoded: HashMap<i64, Term>,
434    pending_extra: Vec<i64>,
435    /// Rows of the pattern-comprehension queries of the current part.
436    comp_raw: Vec<Vec<HashMap<Variable, Term>>>,
437}
438
439/// A path as ids: its nodes, and the `(s, p, o)` of each relationship.
440type IdPath = (Vec<i64>, Vec<[i64; 3]>);
441
442/// Breadth-first search state of one shortest-path pattern.
443struct Bfs {
444    spec: usize,
445    level: usize,
446    /// Per source: parents of every reached node (all parents at its level), the frontier and
447    /// the targets still to reach.
448    sources: BTreeMap<i64, BfsSource>,
449}
450
451#[derive(Default)]
452struct BfsSource {
453    parents: HashMap<i64, (usize, Vec<(i64, [i64; 3])>)>,
454    frontier: Vec<i64>,
455    targets: HashSet<i64>,
456    done: bool,
457}
458
459#[derive(Debug, Default)]
460struct FixData {
461    incident: Vec<[Term; 3]>,
462    existing: HashSet<Triple>,
463    reifier_quads: Vec<[Term; 3]>,
464}
465
466impl CypherJob {
467    pub(crate) fn new(plan: Plan, params: Params, opts: CypherOptions, caps: Capabilities) -> Self {
468        let vocab = opts.vocabulary.clone();
469        let graph = vocab.graph();
470        let shapes = opts.schema.clone();
471        Self {
472            plan,
473            params,
474            vocab,
475            opts,
476            caps,
477            graph,
478            state: State::Start,
479            part: 0,
480            raw: Vec::new(),
481            outputs: Vec::new(),
482            g: GraphState::default(),
483            fetch: None,
484            shapes,
485            fix: FixData::default(),
486            schema_changed: false,
487            bfs: None,
488            found: Vec::new(),
489            decoded: HashMap::new(),
490            pending_extra: Vec::new(),
491            comp_raw: Vec::new(),
492        }
493    }
494
495    /// The options of the SPARQL query of part `i`: the statement's, plus the value types
496    /// the schema gives its property variables.
497    pub fn query_options(&self, i: usize) -> oxilite_core::QueryOptions {
498        let mut o = self.opts.query.clone();
499        if let Some(p) = self.plan.parts.get(i) {
500            o.var_types
501                .extend(p.var_types.iter().map(|(k, v)| (k.clone(), *v)));
502        }
503        o
504    }
505
506    /// The SPARQL queries the statement runs (one per `UNION` member), with their options.
507    pub fn queries(&self) -> Vec<(&spargebra::Query, oxilite_core::QueryOptions)> {
508        self.plan
509            .parts
510            .iter()
511            .enumerate()
512            .flat_map(|(i, p)| {
513                p.query
514                    .iter()
515                    .map(move |q| (q, self.query_options(i)))
516                    .chain(
517                        p.comprehensions
518                            .iter()
519                            .map(|c| (&c.query, self.opts.query.clone())),
520                    )
521            })
522            .collect()
523    }
524
525    /// Planner notes (what runs in Rust and why, capped patterns…).
526    pub fn notes(&self) -> &[String] {
527        &self.plan.notes
528    }
529
530    /// Whether the statement writes.
531    pub fn writes(&self) -> bool {
532        self.plan.writes
533    }
534
535    /// A human-readable plan: SPARQL of each part and what runs in Rust.
536    pub fn explain(&self) -> String {
537        let mut out = String::new();
538        for n in &self.plan.notes {
539            out.push_str(&format!("-- {n}\n"));
540        }
541        for (i, p) in self.plan.parts.iter().enumerate() {
542            if self.plan.parts.len() > 1 {
543                out.push_str(&format!("-- UNION member {}\n", i + 1));
544            }
545            match &p.query {
546                Some(q) => out.push_str(&format!("-- SPARQL (compiled to SQL):\n{q}\n")),
547                None => out.push_str("-- no read\n"),
548            }
549            let tail: Vec<&str> = p
550                .tail
551                .iter()
552                .filter_map(|t| match t {
553                    TailOp::Clause(c) => Some(clause_name(c)),
554                    TailOp::Merge { .. } => Some("MERGE"),
555                    TailOp::Output(_) => None,
556                })
557                .collect();
558            if !tail.is_empty() {
559                out.push_str(&format!("-- evaluated in Rust: {}\n", tail.join(", ")));
560            }
561            for c in &p.comprehensions {
562                out.push_str(&format!(
563                    "-- pattern comprehension (SPARQL):\n{}\n",
564                    c.query
565                ));
566            }
567            if !p.shortest.is_empty() {
568                out.push_str(
569                    "-- shortest paths: breadth-first search, one SQL request per level\n",
570                );
571            }
572        }
573        out
574    }
575
576    /// Advances the job. The first call gets `None`.
577    pub fn step(&mut self, input: Option<StepInput>) -> Result<CypherStep> {
578        let functions = self.opts.functions.clone();
579        crate::eval::with_host(&functions, || self.step_inner(input))
580    }
581
582    fn step_inner(&mut self, input: Option<StepInput>) -> Result<CypherStep> {
583        match (self.state, input) {
584            (State::Start, _) => {
585                crate::temporal::reset_clock();
586                if self.plan.writes && self.opts.shapes && self.shapes.is_none() {
587                    self.state = State::Shapes;
588                    // One indexed read, not a SPARQL evaluation: on D1 that is the difference
589                    // between one round trip and a compiled query per writing statement.
590                    return Ok(CypherStep::Sql(crate::schema::schema_request(&self.caps)));
591                }
592                self.start_part()
593            }
594            (State::Shapes, Some(StepInput::Response(r))) => {
595                let index = oxilite_core::shapes::ShapeIndex::from_response(&r)
596                    .map_err(CypherError::Store)?;
597                self.shapes = Some(std::sync::Arc::new(Shapes::from_index(index)));
598                self.start_part()
599            }
600            (State::Main, Some(StepInput::Output(out))) => {
601                self.raw = solutions(out)?;
602                self.after_main()
603            }
604            (State::Comprehension, Some(StepInput::Output(out))) => {
605                self.comp_raw.push(solutions(out)?);
606                self.after_main()
607            }
608            (State::Materialize, Some(StepInput::Response(r))) => self.drive_fetch(Some(r)),
609            (State::Bfs, Some(StepInput::Response(r))) => self.bfs_step(r),
610            (State::Fixup1 | State::Fixup2, Some(StepInput::Response(r))) => {
611                self.drive_fetch(Some(r))
612            }
613            (State::Write, Some(StepInput::Response(_))) => self.finish(),
614            (s, _) => Err(CypherError::runtime(format!(
615                "Cypher job resumed with an unexpected input in state {s:?}"
616            ))),
617        }
618    }
619
620    fn start_part(&mut self) -> Result<CypherStep> {
621        if self.part >= self.plan.parts.len() {
622            return self.begin_fixup();
623        }
624        match &self.plan.parts[self.part].query {
625            Some(q) => {
626                self.state = State::Main;
627                Ok(CypherStep::Query(q.clone(), self.query_options(self.part)))
628            }
629            None => {
630                self.raw = vec![HashMap::new()];
631                self.after_main()
632            }
633        }
634    }
635
636    fn drive_fetch(&mut self, response: Option<Response>) -> Result<CypherStep> {
637        let step = self.fetch.as_mut().expect("active fetch").step(response)?;
638        match step {
639            Step::Execute(r) => Ok(CypherStep::Sql(r)),
640            Step::Done(quads) => {
641                let fetch = self.fetch.take().expect("active fetch");
642                let extra = std::mem::take(&mut self.pending_extra);
643                self.decoded.extend(fetch.decoded(extra));
644                match self.state {
645                    State::Materialize => {
646                        // Path nodes exist even without labels or properties.
647                        let ids: Vec<i64> = self
648                            .found
649                            .iter()
650                            .flat_map(|f| f.values().flatten().flat_map(|(ns, _)| ns.clone()))
651                            .collect();
652                        for id in ids {
653                            if let Some(s) = self.decoded.get(&id).and_then(to_subject) {
654                                self.g.nodes.entry(s).or_default();
655                            }
656                        }
657                        self.absorb_materialized(quads);
658                        self.run_part()
659                    }
660                    State::Fixup1 => {
661                        self.absorb_fixup1(quads);
662                        self.fixup2()
663                    }
664                    State::Fixup2 => {
665                        self.fix.reifier_quads = quads;
666                        self.apply_fixup()
667                    }
668                    _ => unreachable!("fetch in state {:?}", self.state),
669                }
670            }
671        }
672    }
673
674    fn start_fetch(&mut self, state: State, stmts: Vec<Statement>) -> Result<CypherStep> {
675        self.state = state;
676        self.fetch = Some(QuadFetch::new(stmts, &self.caps));
677        self.drive_fetch(None)
678    }
679
680    /// The quad table reads come from: the store, or the store at the statement's version
681    /// (`QueryOptions::as_of`, resolved by the store before the statement runs).
682    fn quads_src(&self) -> String {
683        match self.opts.query.as_of_tick {
684            Some(t) => oxilite_core::version::as_of_sql(&t.to_string()),
685            None => "quads".to_owned(),
686        }
687    }
688
689    fn graph_cond(&self, t: &str) -> String {
690        format!(
691            "{t}.g = {}",
692            oxilite_core::encoding::graph_id(self.graph.as_ref())
693        )
694    }
695
696    /// The graph condition of reads (materialization, shortest-path expansion): every graph
697    /// when the default graph is the union of all graphs, as in the main query. Writes and
698    /// their fix-ups stay in the default graph.
699    fn read_graph_cond(&self, t: &str) -> String {
700        if self.opts.query.union_default_graph {
701            "1".into()
702        } else {
703            self.graph_cond(t)
704        }
705    }
706
707    // ----- materialization -----
708
709    fn after_main(&mut self) -> Result<CypherStep> {
710        let part = &self.plan.parts[self.part];
711        if self.found.len() < part.shortest.len() {
712            return self.start_bfs();
713        }
714        if let Some(c) = part.comprehensions.get(self.comp_raw.len()) {
715            self.state = State::Comprehension;
716            let mut o = self.query_options(self.part);
717            o.var_types.clear();
718            return Ok(CypherStep::Query(c.query.clone(), o));
719        }
720        self.materialize()
721    }
722
723    // ----- shortest paths -----
724
725    fn start_bfs(&mut self) -> Result<CypherStep> {
726        let spec_i = self.found.len();
727        let spec = self.plan.parts[self.part].shortest[spec_i].clone();
728        let mut sources: BTreeMap<i64, BfsSource> = BTreeMap::new();
729        for row in &self.raw {
730            let (Some(f), Some(t)) = (
731                row.get(&spec.from).and_then(to_subject),
732                row.get(&spec.to).and_then(to_subject),
733            ) else {
734                continue;
735            };
736            let (f, t) = (subject_id(f.as_ref()), subject_id(t.as_ref()));
737            let src = sources.entry(f).or_default();
738            src.targets.insert(t);
739            if src.frontier.is_empty() {
740                src.frontier.push(f);
741                src.parents.insert(f, (0, Vec::new()));
742            }
743        }
744        let mut found: HashMap<(i64, i64), Vec<IdPath>> = HashMap::new();
745        if spec.min == 0 {
746            for (f, src) in &mut sources {
747                if src.targets.remove(f) {
748                    found.insert((*f, *f), vec![(vec![*f], Vec::new())]);
749                }
750                src.done = src.targets.is_empty();
751            }
752        }
753        self.found.push(found);
754        self.bfs = Some(Bfs {
755            spec: spec_i,
756            level: 0,
757            sources,
758        });
759        self.bfs_request()
760    }
761
762    fn bfs_request(&mut self) -> Result<CypherStep> {
763        let bfs = self.bfs.as_ref().expect("bfs");
764        let spec = &self.plan.parts[self.part].shortest[bfs.spec];
765        let frontier: BTreeSet<i64> = bfs
766            .sources
767            .values()
768            .filter(|s| !s.done)
769            .flat_map(|s| s.frontier.iter().copied())
770            .collect();
771        if frontier.is_empty() || bfs.level >= spec.max {
772            return self.finish_bfs();
773        }
774        let frontier: Vec<i64> = frontier.into_iter().collect();
775        let preds = if spec.types.is_empty() {
776            format!(
777                "(q.o >> 59) IN (1, 2) AND q.p NOT IN ({}, {})",
778                rdf_type_id(),
779                named_node_id(REIFIES)
780            )
781        } else {
782            format!(
783                "q.p IN ({})",
784                id_list(
785                    &spec
786                        .types
787                        .iter()
788                        .map(|t| named_node_id(t.as_str()))
789                        .collect::<Vec<_>>()
790                )
791            )
792        };
793        let cols = spo_cols(&self.caps, "q");
794        let g = self.read_graph_cond("q");
795        let src = self.quads_src();
796        let mut stmts = Vec::new();
797        for chunk in frontier.chunks(CHUNK) {
798            let l = id_list(chunk);
799            if spec.dir != Direction::Left {
800                stmts.push(Statement::new(format!(
801                    "SELECT {cols} FROM {src} q WHERE {g} AND q.s IN ({l}) AND {preds}"
802                )));
803            }
804            if spec.dir != Direction::Right {
805                stmts.push(Statement::new(format!(
806                    "SELECT {cols} FROM {src} q WHERE {g} AND q.o IN ({l}) AND {preds}"
807                )));
808            }
809        }
810        self.state = State::Bfs;
811        Ok(CypherStep::Sql(Request::read(stmts)))
812    }
813
814    fn bfs_step(&mut self, response: Response) -> Result<CypherStep> {
815        let spec = {
816            let bfs = self.bfs.as_ref().expect("bfs");
817            self.plan.parts[self.part].shortest[bfs.spec].clone()
818        };
819        // Adjacency of this level: node → (neighbour, edge).
820        let mut adj: HashMap<i64, Vec<(i64, [i64; 3])>> = HashMap::new();
821        for rs in response {
822            for row in rs.rows {
823                let get = |i| col(&row, i).ok().and_then(|v| v.as_i64());
824                let (Some(s), Some(p), Some(o)) = (get(0), get(1), get(2)) else {
825                    continue;
826                };
827                let e = [s, p, o];
828                if spec.dir != Direction::Left {
829                    adj.entry(s).or_default().push((o, e));
830                }
831                if spec.dir != Direction::Right && s != o {
832                    adj.entry(o).or_default().push((s, e));
833                }
834            }
835        }
836        let bfs = self.bfs.as_mut().expect("bfs");
837        bfs.level += 1;
838        let level = bfs.level;
839        let found = self.found.last_mut().expect("found");
840        for (src_id, src) in bfs.sources.iter_mut() {
841            if src.done {
842                continue;
843            }
844            let mut next = Vec::new();
845            for x in std::mem::take(&mut src.frontier) {
846                for (y, e) in adj.get(&x).cloned().unwrap_or_default() {
847                    // A trail never reuses a relationship: in a shortest path a node repeats
848                    // only if the path could be shorter, so reaching a node once suffices.
849                    match src.parents.get_mut(&y) {
850                        None => {
851                            src.parents.insert(y, (level, vec![(x, e)]));
852                            next.push(y);
853                        }
854                        Some((l, ps)) if *l == level && spec.all && !ps.contains(&(x, e)) => {
855                            ps.push((x, e));
856                        }
857                        _ => {}
858                    }
859                }
860            }
861            next.sort_unstable();
862            next.dedup();
863            let reached: Vec<i64> = src
864                .targets
865                .iter()
866                .copied()
867                .filter(|t| src.parents.get(t).is_some_and(|(l, _)| *l == level))
868                .collect();
869            for t in reached {
870                src.targets.remove(&t);
871                found.insert((*src_id, t), unfold(&src.parents, *src_id, t, spec.all));
872            }
873            src.frontier = next;
874            if src.targets.is_empty() {
875                src.done = true;
876            }
877        }
878        self.bfs_request()
879    }
880
881    fn finish_bfs(&mut self) -> Result<CypherStep> {
882        self.bfs = None;
883        self.after_main()
884    }
885
886    fn materialize(&mut self) -> Result<CypherStep> {
887        let part = &self.plan.parts[self.part];
888        // The main rows and the pattern-comprehension rows, with their bindings.
889        let mut sets: Vec<(&Vec<HashMap<Variable, Term>>, &crate::lower::Scope)> =
890            vec![(&self.raw, &part.scope)];
891        for (rows, c) in self.comp_raw.iter().zip(&part.comprehensions) {
892            sets.push((rows, &c.scope));
893        }
894        let mut nodes: BTreeSet<i64> = BTreeSet::new();
895        let mut rels: BTreeSet<i64> = BTreeSet::new();
896        let add = |t: Option<&Term>, set: &mut BTreeSet<i64>, fetched: &HashSet<i64>| {
897            if let Some(s) = t.and_then(to_subject) {
898                let id = subject_id(s.as_ref());
899                if !fetched.contains(&id) {
900                    set.insert(id);
901                }
902            }
903        };
904        for (row, scope) in sets
905            .iter()
906            .flat_map(|(rows, scope)| rows.iter().map(move |r| (r, *scope)))
907        {
908            for b in scope.values() {
909                match b {
910                    Bind::Node { var, .. } => add(row.get(var), &mut nodes, &self.g.fetched),
911                    Bind::Rel { r, .. } => add(row.get(&r.rid), &mut rels, &self.g.fetched),
912                    Bind::Path {
913                        nodes: ns,
914                        rels: rs,
915                        ..
916                    } => {
917                        for n in ns {
918                            add(row.get(n), &mut nodes, &self.g.fetched);
919                        }
920                        for r in rs {
921                            add(row.get(&r.rid), &mut rels, &self.g.fetched);
922                        }
923                    }
924                    Bind::RelList { rels: rs, .. } => {
925                        for r in rs {
926                            add(row.get(&r.rid), &mut rels, &self.g.fetched);
927                        }
928                    }
929                    _ => {}
930                }
931            }
932        }
933        let mut extra: BTreeSet<i64> = BTreeSet::new();
934        for found in &self.found {
935            for paths in found.values() {
936                for (ns, rs) in paths {
937                    for n in ns {
938                        if !self.g.fetched.contains(n) {
939                            nodes.insert(*n);
940                        }
941                        extra.insert(*n);
942                    }
943                    for [s, p, o] in rs {
944                        extra.extend([*s, *p, *o]);
945                    }
946                }
947            }
948        }
949        if nodes.is_empty() && rels.is_empty() && extra.is_empty() {
950            return self.run_part();
951        }
952        let type_id = rdf_type_id();
953        let reifies_id = named_node_id(REIFIES);
954        let mut stmts = Vec::new();
955        let (cols, joins) = with_terms(&self.caps, "q");
956        let g = self.read_graph_cond("q");
957        let src = self.quads_src();
958        let nodes: Vec<i64> = nodes.into_iter().collect();
959        let rels: Vec<i64> = rels.into_iter().collect();
960        // Labels and literal properties (objects that are not IRIs, blank nodes or triples).
961        for chunk in nodes.chunks(CHUNK) {
962            stmts.push(Statement::new(format!(
963                "SELECT {cols} FROM {src} q{joins} WHERE q.s IN ({}) AND {g} AND (q.p = {type_id} OR (q.o >> 59) NOT IN (1, 2, 9))",
964                id_list(chunk)
965            )));
966        }
967        for chunk in rels.chunks(CHUNK) {
968            stmts.push(Statement::new(format!(
969                "SELECT {cols} FROM {src} q{joins} WHERE q.s IN ({}) AND {g} AND q.p <> {reifies_id} AND (q.o >> 59) NOT IN (1, 2, 9)",
970                id_list(chunk)
971            )));
972        }
973        self.g
974            .fetched
975            .extend(nodes.iter().copied().chain(rels.iter().copied()));
976        // Entities without any label or property still exist; their terms are known.
977        let mut entities: Vec<(NamedOrBlankNode, bool)> = Vec::new();
978        for (row, scope) in sets
979            .iter()
980            .flat_map(|(rows, scope)| rows.iter().map(move |r| (r, *scope)))
981        {
982            for b in scope.values() {
983                for (var, is_rel) in entity_vars(b) {
984                    if let Some(s) = row.get(&var).and_then(to_subject) {
985                        entities.push((s, is_rel));
986                    }
987                }
988            }
989        }
990        let raw = std::mem::take(&mut self.raw);
991        let mut known = HashMap::new();
992        for (s, is_rel) in entities {
993            known.insert(subject_id(s.as_ref()), subject_term(&s));
994            let map = if is_rel {
995                &mut self.g.rels
996            } else {
997                &mut self.g.nodes
998            };
999            map.entry(s).or_default();
1000        }
1001        self.raw = raw;
1002        self.state = State::Materialize;
1003        self.pending_extra = extra.iter().copied().collect();
1004        self.fetch = Some(
1005            QuadFetch::new(stmts, &self.caps)
1006                .with_known(known)
1007                .with_extra(extra),
1008        );
1009        self.drive_fetch(None)
1010    }
1011
1012    fn absorb_materialized(&mut self, quads: Vec<[Term; 3]>) {
1013        for [s, p, o] in quads {
1014            let (Some(s), Term::NamedNode(p)) = (to_subject(&s), p) else {
1015                continue;
1016            };
1017            let is_rel = self.g.rels.contains_key(&s);
1018            let e = if is_rel {
1019                self.g.rels.entry(s).or_default()
1020            } else {
1021                self.g.nodes.entry(s).or_default()
1022            };
1023            if p.as_ref() == rdf::TYPE {
1024                if let Term::NamedNode(l) = o {
1025                    if l.as_str() != RESOURCE && !e.labels.contains(&l) {
1026                        e.labels.push(l);
1027                    }
1028                }
1029            } else if matches!(o, Term::Literal(_)) {
1030                // The same triple can come from several graphs (union default graph).
1031                if !e.props.iter().any(|(q, v)| *q == p && *v == o) {
1032                    e.props.push((p, o));
1033                }
1034            }
1035        }
1036    }
1037
1038    // ----- values -----
1039
1040    fn prop_values(
1041        &self,
1042        owner_labels: &[NamedNode],
1043        props: &[(NamedNode, Term)],
1044    ) -> Result<BTreeMap<String, Value>> {
1045        let mut grouped: BTreeMap<String, Vec<Value>> = BTreeMap::new();
1046        let mut preds: BTreeMap<String, NamedNode> = BTreeMap::new();
1047        for (p, o) in props {
1048            if let Term::Literal(l) = o {
1049                let name = self.vocab.name(p.as_str());
1050                preds.entry(name.clone()).or_insert_with(|| p.clone());
1051                grouped
1052                    .entry(name)
1053                    .or_default()
1054                    .push(Value::from_literal(l));
1055            }
1056        }
1057        let mut out = BTreeMap::new();
1058        for (k, mut vs) in grouped {
1059            let scalar = self
1060                .shapes
1061                .as_ref()
1062                .is_some_and(|s| s.is_scalar(owner_labels, &preds[&k]));
1063            let v = if vs.len() == 1 {
1064                vs.pop().expect("one")
1065            } else if scalar {
1066                vs.sort_by(|a, b| a.order(b));
1067                vs.into_iter().next().expect("some")
1068            } else {
1069                match self.opts.multi_value {
1070                    MultiValue::List => {
1071                        vs.sort_by(|a, b| a.order(b));
1072                        Value::List(vs)
1073                    }
1074                    MultiValue::First => {
1075                        vs.sort_by(|a, b| a.order(b));
1076                        vs.into_iter().next().expect("some")
1077                    }
1078                    MultiValue::Error => {
1079                        return Err(CypherError::runtime(format!(
1080                            "property `{k}` has {} values (multi_value = error)",
1081                            vs.len()
1082                        )))
1083                    }
1084                }
1085            };
1086            out.insert(k, v);
1087        }
1088        Ok(out)
1089    }
1090
1091    fn node_value(&self, id: &NamedOrBlankNode) -> Result<Value> {
1092        let e = self.g.nodes.get(id).cloned().unwrap_or_default();
1093        Ok(Value::Node(Node {
1094            id: id.clone(),
1095            labels: e
1096                .labels
1097                .iter()
1098                .map(|l| self.vocab.name(l.as_str()))
1099                .collect(),
1100            properties: self.prop_values(&e.labels, &e.props)?,
1101        }))
1102    }
1103
1104    fn rel_value(
1105        &self,
1106        start: NamedOrBlankNode,
1107        predicate: NamedNode,
1108        end: NamedOrBlankNode,
1109        reifier: Option<NamedOrBlankNode>,
1110    ) -> Result<Value> {
1111        let reifier = reifier.or_else(|| {
1112            self.g
1113                .reified
1114                .get(&Triple::new(
1115                    start.clone(),
1116                    predicate.clone(),
1117                    subject_term(&end),
1118                ))
1119                .cloned()
1120        });
1121        let reifier = reifier.filter(|r| !self.g.dropped.contains(r));
1122        let properties = match &reifier {
1123            Some(r) => {
1124                let e = self.g.rels.get(r).cloned().unwrap_or_default();
1125                self.prop_values(&[], &e.props)?
1126            }
1127            None => BTreeMap::new(),
1128        };
1129        Ok(Value::Relationship(Relationship {
1130            rel_type: self.vocab.name(predicate.as_str()),
1131            start,
1132            predicate,
1133            end,
1134            reifier,
1135            properties,
1136        }))
1137    }
1138
1139    /// Re-reads entity values from the current state (after writes).
1140    fn refresh(&self, v: &mut Value) -> Result<()> {
1141        match v {
1142            Value::Node(n) => *v = self.node_value(&n.id)?,
1143            Value::Relationship(r) => {
1144                *v = self.rel_value(
1145                    r.start.clone(),
1146                    r.predicate.clone(),
1147                    r.end.clone(),
1148                    r.reifier.clone(),
1149                )?
1150            }
1151            Value::Path(p) => {
1152                for n in &mut p.nodes {
1153                    if let Value::Node(x) = self.node_value(&n.id)? {
1154                        *n = x;
1155                    }
1156                }
1157                for r in &mut p.relationships {
1158                    if let Value::Relationship(x) = self.rel_value(
1159                        r.start.clone(),
1160                        r.predicate.clone(),
1161                        r.end.clone(),
1162                        r.reifier.clone(),
1163                    )? {
1164                        *r = x;
1165                    }
1166                }
1167            }
1168            Value::List(items) => {
1169                for i in items {
1170                    self.refresh(i)?;
1171                }
1172            }
1173            Value::Map(m) => {
1174                for i in m.values_mut() {
1175                    self.refresh(i)?;
1176                }
1177            }
1178            _ => {}
1179        }
1180        Ok(())
1181    }
1182
1183    fn refresh_rows(&self, rows: &mut [Row]) -> Result<()> {
1184        for r in rows {
1185            for v in r.values_mut() {
1186                self.refresh(v)?;
1187            }
1188        }
1189        Ok(())
1190    }
1191
1192    fn id_path_value(&self, ns: &[i64], rs: &[[i64; 3]]) -> Result<Value> {
1193        let term = |id: &i64| {
1194            self.decoded
1195                .get(id)
1196                .cloned()
1197                .ok_or_else(|| CypherError::runtime(format!("term {id} of a path was not decoded")))
1198        };
1199        let mut nodes = Vec::new();
1200        for n in ns {
1201            let s = to_subject(&term(n)?)
1202                .ok_or_else(|| CypherError::runtime("path node is not a resource"))?;
1203            if let Value::Node(x) = self.node_value(&s)? {
1204                nodes.push(x);
1205            }
1206        }
1207        let mut rels = Vec::new();
1208        for [s, p, o] in rs {
1209            let (Some(s), Term::NamedNode(p), Some(o)) =
1210                (to_subject(&term(s)?), term(p)?, to_subject(&term(o)?))
1211            else {
1212                return Err(CypherError::runtime("invalid path relationship"));
1213            };
1214            if let Value::Relationship(r) = self.rel_value(s, p, o, None)? {
1215                rels.push(r);
1216            }
1217        }
1218        Ok(Value::Path(Path {
1219            nodes,
1220            relationships: rels,
1221        }))
1222    }
1223
1224    fn rel_from_vars(&self, row: &HashMap<Variable, Term>, r: &RelVars) -> Result<Value> {
1225        let (Some(s), Some(Term::NamedNode(p)), Some(o)) = (
1226            row.get(&r.s).and_then(to_subject),
1227            row.get(&r.p).cloned(),
1228            row.get(&r.o).and_then(to_subject),
1229        ) else {
1230            return Ok(Value::Null);
1231        };
1232        let rid = row.get(&r.rid).and_then(to_subject);
1233        self.rel_value(s, p, o, rid)
1234    }
1235
1236    fn bind_value(&self, b: &Bind, row: &HashMap<Variable, Term>) -> Result<Value> {
1237        Ok(match b {
1238            Bind::Node { var, .. } => match row.get(var).and_then(to_subject) {
1239                Some(s) => self.node_value(&s)?,
1240                None => Value::Null,
1241            },
1242            Bind::Rel { r, .. } => self.rel_from_vars(row, r)?,
1243            Bind::Value { var, name, .. } => match row.get(var) {
1244                None => Value::Null,
1245                Some(Term::NamedNode(n)) if *name => Value::String(self.vocab.name(n.as_str())),
1246                Some(t) => Value::from_term(t),
1247            },
1248            Bind::Map { fields, .. } => Value::Map(
1249                fields
1250                    .iter()
1251                    .map(|(k, v)| (k.clone(), row.get(v).map_or(Value::Null, Value::from_term)))
1252                    .collect(),
1253            ),
1254            Bind::Path {
1255                len, nodes, rels, ..
1256            } => {
1257                let Some(n) = row.get(len).map(Value::from_term).and_then(|v| match v {
1258                    Value::Int(i) => Some(i as usize),
1259                    _ => None,
1260                }) else {
1261                    return Ok(Value::Null);
1262                };
1263                let mut ns = Vec::new();
1264                for v in nodes.iter().take(n + 1) {
1265                    match row.get(v).and_then(to_subject) {
1266                        Some(s) => {
1267                            if let Value::Node(x) = self.node_value(&s)? {
1268                                ns.push(x);
1269                            }
1270                        }
1271                        None => return Ok(Value::Null),
1272                    }
1273                }
1274                let mut rs = Vec::new();
1275                for r in rels.iter().take(n) {
1276                    match self.rel_from_vars(row, r)? {
1277                        Value::Relationship(x) => rs.push(x),
1278                        _ => return Ok(Value::Null),
1279                    }
1280                }
1281                Value::Path(Path {
1282                    nodes: ns,
1283                    relationships: rs,
1284                })
1285            }
1286            Bind::RelList { len, rels, .. } => {
1287                let Some(n) = row.get(len).map(Value::from_term).and_then(|v| match v {
1288                    Value::Int(i) => Some(i as usize),
1289                    _ => None,
1290                }) else {
1291                    return Ok(Value::Null);
1292                };
1293                let mut out = Vec::new();
1294                for r in rels.iter().take(n) {
1295                    out.push(self.rel_from_vars(row, r)?);
1296                }
1297                Value::List(out)
1298            }
1299        })
1300    }
1301
1302    // ----- running a part -----
1303
1304    fn run_part(&mut self) -> Result<CypherStep> {
1305        let part = self.plan.parts[self.part].clone();
1306        let raw = std::mem::take(&mut self.raw);
1307        let mut rows: Vec<Row> = Vec::with_capacity(raw.len());
1308        if let Some(proc_) = &part.procedure {
1309            for r in &raw {
1310                let mut row = Row::new();
1311                for (col, alias) in &proc_.yields {
1312                    let v = Variable::new_unchecked(format!("proc_{col}"));
1313                    let val = match r.get(&v) {
1314                        None => Value::Null,
1315                        Some(Term::NamedNode(n)) => Value::String(self.vocab.name(n.as_str())),
1316                        Some(t) => Value::from_term(t),
1317                    };
1318                    row.insert(alias.clone(), val);
1319                }
1320                rows.push(row);
1321            }
1322            if let Some(w) = &proc_.where_ {
1323                let params = self.params.clone();
1324                rows = rows
1325                    .into_iter()
1326                    .filter_map(|r| match eval_pred(w, &Env::new(&r, &params)) {
1327                        Ok(true) => Some(Ok(r)),
1328                        Ok(false) => None,
1329                        Err(e) => Some(Err(e)),
1330                    })
1331                    .collect::<Result<_>>()?;
1332            }
1333        } else {
1334            for r in &raw {
1335                let mut row = Row::new();
1336                for (name, b) in &part.scope {
1337                    row.insert(name.clone(), self.bind_value(b, r)?);
1338                }
1339                rows.push(row);
1340            }
1341        }
1342        // Pattern comprehensions: each row gets the list of its outer values' matches.
1343        let comp_raw = std::mem::take(&mut self.comp_raw);
1344        for (c, crows) in part.comprehensions.iter().zip(&comp_raw) {
1345            let mut lists: HashMap<Vec<Option<Term>>, BTreeMap<String, Vec<Value>>> =
1346                HashMap::new();
1347            for cr in crows {
1348                let mut env_row = Row::new();
1349                for (name, b) in &c.scope {
1350                    env_row.insert(name.clone(), self.bind_value(b, cr)?);
1351                }
1352                let env = Env::new(&env_row, &self.params);
1353                if let Some(f) = &c.filter {
1354                    if !eval_pred(f, &env)? {
1355                        continue;
1356                    }
1357                }
1358                let key: Vec<Option<Term>> = c.keys.iter().map(|k| cr.get(k).cloned()).collect();
1359                let free = c
1360                    .free
1361                    .iter()
1362                    .map(|v| {
1363                        cr.get(v)
1364                            .and_then(to_subject)
1365                            .map_or_else(String::new, |s| crate::value::subject_str(&s))
1366                    })
1367                    .collect::<Vec<_>>()
1368                    .join("|");
1369                lists
1370                    .entry(key)
1371                    .or_default()
1372                    .entry(free)
1373                    .or_default()
1374                    .push(eval(&c.map, &env)?);
1375            }
1376            for (row, r) in rows.iter_mut().zip(&raw) {
1377                let key: Vec<Option<Term>> = c.keys.iter().map(|k| r.get(k).cloned()).collect();
1378                let by_free = lists.get(&key).cloned().unwrap_or_default();
1379                let v = if c.free.is_empty() {
1380                    Value::List(by_free.into_values().next().unwrap_or_default())
1381                } else {
1382                    Value::Map(
1383                        by_free
1384                            .into_iter()
1385                            .map(|(k, l)| (k, Value::List(l)))
1386                            .collect(),
1387                    )
1388                };
1389                row.insert(c.name.clone(), v);
1390            }
1391        }
1392        for (si, spec) in part.shortest.iter().enumerate() {
1393            let mut out = Vec::new();
1394            for (row, r) in rows.into_iter().zip(&raw) {
1395                let (Some(f), Some(t)) = (
1396                    r.get(&spec.from).and_then(to_subject),
1397                    r.get(&spec.to).and_then(to_subject),
1398                ) else {
1399                    continue;
1400                };
1401                let key = (subject_id(f.as_ref()), subject_id(t.as_ref()));
1402                for (ns, rs) in self.found[si].get(&key).cloned().unwrap_or_default() {
1403                    let path = self.id_path_value(&ns, &rs)?;
1404                    let mut row2 = row.clone();
1405                    if let Some(rv) = &spec.rel {
1406                        if let Value::Path(p) = &path {
1407                            row2.insert(
1408                                rv.clone(),
1409                                Value::List(
1410                                    p.relationships
1411                                        .iter()
1412                                        .cloned()
1413                                        .map(Value::Relationship)
1414                                        .collect(),
1415                                ),
1416                            );
1417                        }
1418                    }
1419                    row2.insert(spec.path.clone(), path);
1420                    out.push(row2);
1421                }
1422            }
1423            // Keep rows aligned with raw rows for the next pattern.
1424            rows = out;
1425            if si + 1 < part.shortest.len() {
1426                return Err(CypherError::unsupported(
1427                    "several shortestPath() patterns in one MATCH",
1428                ));
1429            }
1430        }
1431        self.found.clear();
1432        let mut columns: Option<Vec<String>> = None;
1433        for op in &part.tail {
1434            match op {
1435                TailOp::Output(cols) => {
1436                    columns = Some(cols.clone());
1437                }
1438                TailOp::Clause(Clause::Return(p)) => {
1439                    self.refresh_rows(&mut rows)?;
1440                    let (r, cols) = self.project(rows, p)?;
1441                    rows = r;
1442                    columns = Some(cols);
1443                }
1444                TailOp::Clause(c) => {
1445                    self.refresh_rows(&mut rows)?;
1446                    rows = self.exec_clause(c, rows)?;
1447                }
1448                TailOp::Merge {
1449                    part: pp,
1450                    on_create,
1451                    on_match,
1452                    lookup,
1453                } => {
1454                    self.refresh_rows(&mut rows)?;
1455                    rows = self.merge(pp, on_create, on_match, lookup.as_deref(), rows)?;
1456                }
1457            }
1458        }
1459        if let Some(cols) = columns {
1460            for r in rows {
1461                let mut out = Vec::with_capacity(cols.len());
1462                for c in &cols {
1463                    out.push(r.get(c).cloned().unwrap_or(Value::Null));
1464                }
1465                self.outputs.push(out);
1466            }
1467        }
1468        self.part += 1;
1469        self.start_part()
1470    }
1471
1472    // ----- projections in Rust -----
1473
1474    fn project(&self, rows: Vec<Row>, p: &Projection) -> Result<(Vec<Row>, Vec<String>)> {
1475        let mut items: Vec<(String, Expr)> = Vec::new();
1476        if p.star {
1477            let mut names: BTreeSet<String> = BTreeSet::new();
1478            for r in &rows {
1479                names.extend(r.keys().filter(|k| !k.starts_with('\u{1}')).cloned());
1480            }
1481            for n in names {
1482                items.push((n.clone(), Expr::Var(n)));
1483            }
1484        }
1485        for it in &p.items {
1486            items.push((it.name(), it.expr.clone()));
1487        }
1488        let names: Vec<String> = items.iter().map(|(n, _)| n.clone()).collect();
1489        let params = &self.params;
1490        let aggregating = items.iter().any(|(_, e)| e.has_aggregate());
1491        // (projected row, env for ORDER BY)
1492        let mut out: Vec<(Row, Row)> = Vec::new();
1493        if aggregating {
1494            let mut aggs: Vec<AggSpec> = Vec::new();
1495            let rewritten: Vec<(String, Expr, bool)> = items
1496                .iter()
1497                .map(|(n, e)| {
1498                    if e.has_aggregate() {
1499                        (n.clone(), extract_aggregates(e, &mut aggs), true)
1500                    } else {
1501                        (n.clone(), e.clone(), false)
1502                    }
1503                })
1504                .collect();
1505            let mut groups: Vec<(Vec<GroupKey>, Row, Vec<Acc>, Vec<HashSet<GroupKey>>)> =
1506                Vec::new();
1507            let mut index: HashMap<Vec<GroupKey>, usize> = HashMap::new();
1508            for r in &rows {
1509                let env = Env::new(r, params);
1510                let mut key = Vec::new();
1511                let mut keyrow = Row::new();
1512                for (n, e, is_agg) in &rewritten {
1513                    if !*is_agg {
1514                        let v = eval(e, &env)?;
1515                        key.push(v.group_key());
1516                        keyrow.insert(n.clone(), v);
1517                    }
1518                }
1519                let gi = match index.get(&key) {
1520                    Some(i) => *i,
1521                    None => {
1522                        let accs = aggs
1523                            .iter()
1524                            .map(|a| Acc::new(&a.func))
1525                            .collect::<Result<Vec<_>>>()?;
1526                        groups.push((key.clone(), keyrow, accs, vec![HashSet::new(); aggs.len()]));
1527                        index.insert(key, groups.len() - 1);
1528                        groups.len() - 1
1529                    }
1530                };
1531                for (ai, a) in aggs.iter().enumerate() {
1532                    if let (Some(e), Acc::Percentile { p: pp, .. }) =
1533                        (&a.arg2, &mut groups[gi].2[ai])
1534                    {
1535                        if let Some(x) = eval(e, &env)?.as_f64() {
1536                            if !(0.0..=1.0).contains(&x) {
1537                                return Err(CypherError::runtime(
1538                                    "percentile must be between 0.0 and 1.0",
1539                                ));
1540                            }
1541                            *pp = x;
1542                        }
1543                    }
1544                    let v = match &a.arg {
1545                        None => Value::Bool(true),
1546                        Some(e) => eval(e, &env)?,
1547                    };
1548                    if a.distinct && !v.is_null() && !groups[gi].3[ai].insert(v.group_key()) {
1549                        continue;
1550                    }
1551                    groups[gi].2[ai].add(v)?;
1552                }
1553            }
1554            if groups.is_empty() && rewritten.iter().all(|(_, _, a)| *a) {
1555                let accs = aggs
1556                    .iter()
1557                    .map(|a| Acc::new(&a.func))
1558                    .collect::<Result<Vec<_>>>()?;
1559                groups.push((Vec::new(), Row::new(), accs, Vec::new()));
1560            }
1561            for (_, keyrow, accs, _) in groups {
1562                let mut env_row = keyrow.clone();
1563                for (a, acc) in aggs.iter().zip(accs) {
1564                    env_row.insert(a.placeholder.clone(), acc.finish());
1565                }
1566                let mut row = Row::new();
1567                for (n, e, is_agg) in &rewritten {
1568                    let v = if *is_agg {
1569                        eval(e, &Env::new(&env_row, params))?
1570                    } else {
1571                        keyrow.get(n).cloned().unwrap_or(Value::Null)
1572                    };
1573                    row.insert(n.clone(), v);
1574                }
1575                out.push((row.clone(), row));
1576            }
1577        } else {
1578            for r in &rows {
1579                let env = Env::new(r, params);
1580                let mut row = Row::new();
1581                for (n, e) in &items {
1582                    row.insert(n.clone(), eval(e, &env)?);
1583                }
1584                let mut order_env = r.clone();
1585                order_env.extend(row.clone());
1586                out.push((row, order_env));
1587            }
1588        }
1589        // WITH … WHERE over variables of the previous scope filters before DISTINCT/ORDER.
1590        let mut early_where = false;
1591        if let (Some(w), false, None, None) = (&p.where_, aggregating, &p.skip, &p.limit) {
1592            let mut old_refs = false;
1593            w.walk(&mut |x| {
1594                if let Expr::Var(v) = x {
1595                    if !names.contains(v) {
1596                        old_refs = true;
1597                    }
1598                }
1599            });
1600            if old_refs {
1601                let mut kept = Vec::new();
1602                for (r, env_row) in out {
1603                    if eval_pred(w, &Env::new(&env_row, params))? {
1604                        kept.push((r, env_row));
1605                    }
1606                }
1607                out = kept;
1608                early_where = true;
1609            }
1610        }
1611        if p.distinct {
1612            let mut seen = HashSet::new();
1613            out.retain(|(r, _)| {
1614                let key: Vec<GroupKey> = names
1615                    .iter()
1616                    .map(|n| r.get(n).map_or(GroupKey::Null, Value::group_key))
1617                    .collect();
1618                seen.insert(key)
1619            });
1620        }
1621        if !p.order.is_empty() {
1622            // Order keys read projected values for the projected expressions they contain.
1623            let targets: Vec<(Expr, Expr)> = items
1624                .iter()
1625                .map(|(n, ie)| (ie.clone(), Expr::Var(n.clone())))
1626                .collect();
1627            let order: Vec<Expr> = p
1628                .order
1629                .iter()
1630                .map(|(e, _)| e.replace_subexprs(&targets))
1631                .collect();
1632            let mut keyed: Vec<(Vec<Value>, Row)> = Vec::with_capacity(out.len());
1633            for (r, env_row) in out {
1634                let env = Env::new(&env_row, params);
1635                let mut k = Vec::new();
1636                for e in &order {
1637                    k.push(eval(e, &env)?);
1638                }
1639                keyed.push((k, r));
1640            }
1641            keyed.sort_by(|(a, _), (b, _)| {
1642                for (i, (_, asc)) in p.order.iter().enumerate() {
1643                    let o = a[i].order(&b[i]);
1644                    let o = if *asc { o } else { o.reverse() };
1645                    if o != std::cmp::Ordering::Equal {
1646                        return o;
1647                    }
1648                }
1649                std::cmp::Ordering::Equal
1650            });
1651            out = keyed.into_iter().map(|(_, r)| (r.clone(), r)).collect();
1652        }
1653        let empty = Row::new();
1654        let count = |e: &Option<Expr>| -> Result<Option<usize>> {
1655            match e {
1656                None => Ok(None),
1657                Some(e) => match eval(e, &Env::new(&empty, params))? {
1658                    Value::Int(i) if i >= 0 => Ok(Some(i as usize)),
1659                    _ => Err(CypherError::semantic(
1660                        "SKIP and LIMIT need a non-negative integer",
1661                    )),
1662                },
1663            }
1664        };
1665        let skip = count(&p.skip)?.unwrap_or(0);
1666        let limit = count(&p.limit)?;
1667        let mut rows: Vec<Row> = out.into_iter().map(|(r, _)| r).skip(skip).collect();
1668        if let Some(l) = limit {
1669            rows.truncate(l);
1670        }
1671        if let (Some(w), false) = (&p.where_, early_where) {
1672            let mut kept = Vec::new();
1673            for r in rows {
1674                if eval_pred(w, &Env::new(&r, params))? {
1675                    kept.push(r);
1676                }
1677            }
1678            rows = kept;
1679        }
1680        Ok((rows, names))
1681    }
1682
1683    // ----- clauses in Rust -----
1684
1685    fn exec_clause(&mut self, c: &Clause, rows: Vec<Row>) -> Result<Vec<Row>> {
1686        let params = self.params.clone();
1687        Ok(match c {
1688            Clause::With(p) => self.project(rows, p)?.0,
1689            Clause::Unwind { expr, alias } => {
1690                let mut out = Vec::new();
1691                for r in rows {
1692                    match eval(expr, &Env::new(&r, &params))? {
1693                        Value::Null => {}
1694                        Value::List(items) => {
1695                            for i in items {
1696                                let mut r2 = r.clone();
1697                                r2.insert(alias.clone(), i);
1698                                out.push(r2);
1699                            }
1700                        }
1701                        v => {
1702                            let mut r2 = r;
1703                            r2.insert(alias.clone(), v);
1704                            out.push(r2);
1705                        }
1706                    }
1707                }
1708                out
1709            }
1710            Clause::Create(parts) => {
1711                let mut out = Vec::with_capacity(rows.len());
1712                for mut r in rows {
1713                    for p in parts {
1714                        self.create_part(p, &mut r)?;
1715                    }
1716                    out.push(r);
1717                }
1718                out
1719            }
1720            Clause::Set(items) => {
1721                let mut out = Vec::with_capacity(rows.len());
1722                for mut r in rows {
1723                    for it in items {
1724                        self.set_item(it, &mut r)?;
1725                    }
1726                    out.push(r);
1727                }
1728                out
1729            }
1730            Clause::Remove(items) => {
1731                let mut out = Vec::with_capacity(rows.len());
1732                for mut r in rows {
1733                    for it in items {
1734                        self.remove_item(it, &mut r)?;
1735                    }
1736                    out.push(r);
1737                }
1738                out
1739            }
1740            Clause::Delete { detach, exprs } => {
1741                for r in &rows {
1742                    for e in exprs {
1743                        let v = eval(e, &Env::new(r, &params))?;
1744                        self.delete_value(v, *detach)?;
1745                    }
1746                }
1747                rows
1748            }
1749            other => {
1750                return Err(CypherError::unsupported(format!(
1751                    "{} in this position",
1752                    clause_name(other)
1753                )))
1754            }
1755        })
1756    }
1757
1758    fn mint(&mut self, prefix: &str) -> NamedOrBlankNode {
1759        self.g.counter += 1;
1760        let seed = self
1761            .g
1762            .seed
1763            .get_or_insert_with(|| oxrdf::BlankNode::default().as_str().to_string())
1764            .clone();
1765        NamedNode::new_unchecked(format!("{prefix}{seed}-{}", self.g.counter)).into()
1766    }
1767
1768    fn literal_props(&self, e: Option<&Expr>, row: &Row) -> Result<Vec<(NamedNode, Term)>> {
1769        let Some(e) = e else {
1770            return Ok(Vec::new());
1771        };
1772        let v = eval(e, &Env::new(row, &self.params))?;
1773        let Value::Map(m) = v else {
1774            return Err(CypherError::runtime("properties must be a map"));
1775        };
1776        let mut out = Vec::new();
1777        for (k, v) in m {
1778            if let Some(l) = v.to_literal()? {
1779                out.push((self.vocab.iri(&k), l.into()));
1780            }
1781        }
1782        Ok(out)
1783    }
1784
1785    fn create_node(&mut self, np: &NodePattern, row: &mut Row) -> Result<NamedOrBlankNode> {
1786        if let Some(name) = &np.var {
1787            match row.get(name) {
1788                Some(Value::Node(n)) => {
1789                    if !np.labels.is_empty() || np.props.is_some() {
1790                        return Err(CypherError::semantic(format!(
1791                            "node `{name}` is already bound: it cannot get labels or properties in CREATE"
1792                        )));
1793                    }
1794                    return Ok(n.id.clone());
1795                }
1796                Some(Value::Null) => {
1797                    return Err(CypherError::runtime(format!(
1798                        "cannot create a relationship with the null node `{name}`"
1799                    )))
1800                }
1801                Some(other) => {
1802                    return Err(CypherError::semantic(format!(
1803                        "`{name}` is a {}, not a node",
1804                        other.type_name()
1805                    )))
1806                }
1807                None => {}
1808            }
1809        }
1810        let id = self.mint(&self.vocab.node_prefix.clone());
1811        let props = self.literal_props(np.props.as_ref(), row)?;
1812        let labels: Vec<NamedNode> = np.labels.iter().map(|l| self.vocab.iri(l)).collect();
1813        if self.opts.node_marker {
1814            self.g.set(
1815                Quad::new(
1816                    id.clone(),
1817                    rdf::TYPE.into_owned(),
1818                    NamedNode::new_unchecked(RESOURCE),
1819                    self.graph.clone(),
1820                ),
1821                true,
1822            );
1823        }
1824        for l in &labels {
1825            self.g.set(
1826                Quad::new(
1827                    id.clone(),
1828                    rdf::TYPE.into_owned(),
1829                    l.clone(),
1830                    self.graph.clone(),
1831                ),
1832                true,
1833            );
1834        }
1835        for (p, o) in &props {
1836            self.g.set(
1837                Quad::new(id.clone(), p.clone(), o.clone(), self.graph.clone()),
1838                true,
1839            );
1840        }
1841        self.g.stats.nodes_created += 1;
1842        self.g.stats.labels_added += labels.len() as u64;
1843        self.g.stats.properties_set += props.len() as u64;
1844        self.g.nodes.insert(
1845            id.clone(),
1846            Entity {
1847                labels,
1848                props,
1849                deleted: false,
1850            },
1851        );
1852        self.g.created_nodes.insert(id.clone());
1853        self.g.touch(&id);
1854        if let Some(name) = &np.var {
1855            row.insert(name.clone(), self.node_value(&id)?);
1856        }
1857        Ok(id)
1858    }
1859
1860    fn create_part(&mut self, p: &PatternPart, row: &mut Row) -> Result<()> {
1861        let mut nodes = vec![self.create_node(&p.element.start, row)?];
1862        let mut rels = Vec::new();
1863        for (rel, np) in &p.element.chain {
1864            let end = self.create_node(np, row)?;
1865            let start = nodes.last().expect("start").clone();
1866            if rel.length.is_some() {
1867                return Err(CypherError::semantic(
1868                    "variable-length relationships cannot be created",
1869                ));
1870            }
1871            let [t] = rel.types.as_slice() else {
1872                return Err(CypherError::semantic(
1873                    "a created relationship needs exactly one type",
1874                ));
1875            };
1876            let (s, o) = match rel.dir {
1877                Direction::Right => (start, end.clone()),
1878                Direction::Left => (end.clone(), start),
1879                Direction::Both => {
1880                    return Err(CypherError::semantic(
1881                        "a created relationship needs a direction",
1882                    ))
1883                }
1884            };
1885            if let Some(name) = &rel.var {
1886                if row.contains_key(name) {
1887                    return Err(CypherError::semantic(format!(
1888                        "relationship `{name}` is already bound"
1889                    )));
1890                }
1891            }
1892            let pred = self.vocab.iri(t);
1893            let rid = self.mint(&self.vocab.relationship_prefix.clone());
1894            let props = self.literal_props(rel.props.as_ref(), row)?;
1895            self.g.stats.relationships_created += 1;
1896            self.g.stats.properties_set += props.len() as u64;
1897            self.g.rels.insert(
1898                rid.clone(),
1899                Entity {
1900                    labels: Vec::new(),
1901                    props,
1902                    deleted: false,
1903                },
1904            );
1905            self.g.provisional.insert(rid.clone());
1906            self.g.created_rels.push(RelCreate {
1907                s: s.clone(),
1908                p: pred.clone(),
1909                o: o.clone(),
1910                rid: rid.clone(),
1911                dropped: false,
1912            });
1913            let v = self.rel_value(s, pred, o, Some(rid))?;
1914            if let Some(name) = &rel.var {
1915                row.insert(name.clone(), v.clone());
1916            }
1917            if let Value::Relationship(r) = v {
1918                rels.push(r);
1919            }
1920            nodes.push(end);
1921        }
1922        if let Some(pv) = &p.var {
1923            let mut ns = Vec::new();
1924            for n in &nodes {
1925                if let Value::Node(x) = self.node_value(n)? {
1926                    ns.push(x);
1927                }
1928            }
1929            row.insert(
1930                pv.clone(),
1931                Value::Path(Path {
1932                    nodes: ns,
1933                    relationships: rels,
1934                }),
1935            );
1936        }
1937        Ok(())
1938    }
1939
1940    fn merge_key(&self, p: &PatternPart, row: &Row) -> Result<String> {
1941        let env = Env::new(row, &self.params);
1942        let node = |np: &NodePattern| -> Result<String> {
1943            if let Some(Value::Node(n)) = np.var.as_ref().and_then(|v| row.get(v)) {
1944                return Ok(format!("#{}", n.element_id()));
1945            }
1946            let mut labels = np.labels.clone();
1947            labels.sort();
1948            let props = match &np.props {
1949                Some(e) => eval(e, &env)?.to_string(),
1950                None => String::new(),
1951            };
1952            Ok(format!("({}{props})", labels.join(":")))
1953        };
1954        let mut key = node(&p.element.start)?;
1955        for (r, n) in &p.element.chain {
1956            let props = match &r.props {
1957                Some(e) => eval(e, &env)?.to_string(),
1958                None => String::new(),
1959            };
1960            key.push_str(&format!("-[{}{props}|{:?}]-", r.types.join("|"), r.dir));
1961            key.push_str(&node(n)?);
1962        }
1963        Ok(key)
1964    }
1965
1966    fn merge(
1967        &mut self,
1968        p: &PatternPart,
1969        on_create: &[SetItem],
1970        on_match: &[SetItem],
1971        lookup: Option<&str>,
1972        rows: Vec<Row>,
1973    ) -> Result<Vec<Row>> {
1974        let vars = crate::plan::pattern_vars(p);
1975        let mut out = Vec::with_capacity(rows.len());
1976        for mut r in rows {
1977            let mut matched = lookup.is_some_and(|m| r.remove(m) == Some(Value::Bool(true)));
1978            // Nodes deleted earlier in the statement no longer match.
1979            if matched
1980                && vars.iter().any(|v| {
1981                    matches!(r.get(v), Some(Value::Node(n)) if self.g.nodes.get(&n.id).is_some_and(|e| e.deleted))
1982                })
1983            {
1984                matched = false;
1985                for v in &vars {
1986                    r.remove(v);
1987                }
1988            }
1989            if matched {
1990                for it in on_match {
1991                    self.set_item(it, &mut r)?;
1992                }
1993                out.push(r);
1994                continue;
1995            }
1996            // New variables of the pattern are unbound when it did not match.
1997            for v in &vars {
1998                if r.get(v).is_some_and(Value::is_null) {
1999                    r.remove(v);
2000                }
2001            }
2002            let key = self.merge_key(p, &r)?;
2003            if let Some(bound) = self.g.merge_cache.get(&key).cloned() {
2004                for (k, v) in bound {
2005                    r.insert(k, v);
2006                }
2007                self.refresh_rows(std::slice::from_mut(&mut r))?;
2008                for it in on_match {
2009                    self.set_item(it, &mut r)?;
2010                }
2011                out.push(r);
2012                continue;
2013            }
2014            if p.element
2015                .chain
2016                .iter()
2017                .any(|(rel, _)| rel.dir == Direction::Both)
2018            {
2019                return Err(CypherError::unsupported(
2020                    "MERGE of an undirected relationship",
2021                ));
2022            }
2023            self.create_part(p, &mut r)?;
2024            for it in on_create {
2025                self.set_item(it, &mut r)?;
2026            }
2027            let bound: Vec<(String, Value)> = vars
2028                .iter()
2029                .filter_map(|v| r.get(v).map(|x| (v.clone(), x.clone())))
2030                .collect();
2031            self.g.merge_cache.insert(key, bound);
2032            out.push(r);
2033        }
2034        Ok(out)
2035    }
2036
2037    /// The entity map and subject that `SET`/`REMOVE` on `var` modify.
2038    fn target(&mut self, var: &str, row: &Row) -> Result<Option<(NamedOrBlankNode, bool)>> {
2039        match row.get(var) {
2040            None => Err(CypherError::semantic(format!(
2041                "variable `{var}` not defined"
2042            ))),
2043            Some(Value::Null) => Ok(None),
2044            Some(Value::Node(n)) => Ok(Some((n.id.clone(), false))),
2045            Some(Value::Relationship(r)) => {
2046                let rid = match r
2047                    .reifier
2048                    .clone()
2049                    .filter(|x| !self.g.dropped.contains(x))
2050                    .or_else(|| {
2051                        self.g
2052                            .reified
2053                            .get(&Triple::new(
2054                                r.start.clone(),
2055                                r.predicate.clone(),
2056                                subject_term(&r.end),
2057                            ))
2058                            .cloned()
2059                    }) {
2060                    Some(rid) => rid,
2061                    None => {
2062                        // Properties need a reifier.
2063                        let rid = self.mint(&self.vocab.relationship_prefix.clone());
2064                        let t =
2065                            Triple::new(r.start.clone(), r.predicate.clone(), subject_term(&r.end));
2066                        self.g.set(
2067                            Quad::new(
2068                                rid.clone(),
2069                                reifies(),
2070                                Term::Triple(Box::new(t.clone())),
2071                                self.graph.clone(),
2072                            ),
2073                            true,
2074                        );
2075                        self.g.reified.insert(t, rid.clone());
2076                        self.g.rels.insert(rid.clone(), Entity::default());
2077                        rid
2078                    }
2079                };
2080                Ok(Some((rid, true)))
2081            }
2082            Some(other) => Err(CypherError::runtime(format!(
2083                "cannot set properties on a {}",
2084                other.type_name()
2085            ))),
2086        }
2087    }
2088
2089    fn set_prop(
2090        &mut self,
2091        subject: &NamedOrBlankNode,
2092        is_rel: bool,
2093        key: &NamedNode,
2094        value: Option<Term>,
2095    ) {
2096        let provisional = self.g.provisional.contains(subject);
2097        let map = if is_rel {
2098            &mut self.g.rels
2099        } else {
2100            &mut self.g.nodes
2101        };
2102        let e = map.entry(subject.clone()).or_default();
2103        let old: Vec<Term> = e
2104            .props
2105            .iter()
2106            .filter(|(p, _)| p == key)
2107            .map(|(_, o)| o.clone())
2108            .collect();
2109        e.props.retain(|(p, _)| p != key);
2110        if let Some(v) = &value {
2111            e.props.push((key.clone(), v.clone()));
2112        }
2113        if !provisional {
2114            for o in old {
2115                self.g.set(
2116                    Quad::new(subject.clone(), key.clone(), o, self.graph.clone()),
2117                    false,
2118                );
2119            }
2120            if let Some(v) = value {
2121                self.g.set(
2122                    Quad::new(subject.clone(), key.clone(), v, self.graph.clone()),
2123                    true,
2124                );
2125            }
2126        }
2127        self.g.stats.properties_set += 1;
2128        if !is_rel {
2129            self.g.touch(subject);
2130        }
2131    }
2132
2133    fn set_item(&mut self, it: &SetItem, row: &mut Row) -> Result<()> {
2134        let params = self.params.clone();
2135        match it {
2136            SetItem::Property { var, key, value } => {
2137                let v = eval(value, &Env::new(row, &params))?;
2138                if let Some((s, is_rel)) = self.target(var, row)? {
2139                    let l = v.to_literal()?.map(Term::from);
2140                    self.set_prop(&s, is_rel, &self.vocab.iri(key), l);
2141                }
2142            }
2143            SetItem::Replace { var, value } | SetItem::Merge { var, value } => {
2144                let v = eval(value, &Env::new(row, &params))?;
2145                let m = match v {
2146                    Value::Map(m) => m,
2147                    Value::Node(n) => n.properties,
2148                    Value::Relationship(r) => r.properties,
2149                    Value::Null => BTreeMap::new(),
2150                    o => {
2151                        return Err(CypherError::runtime(format!(
2152                            "SET … = expects a map, got {}",
2153                            o.type_name()
2154                        )))
2155                    }
2156                };
2157                if let Some((s, is_rel)) = self.target(var, row)? {
2158                    if matches!(it, SetItem::Replace { .. }) {
2159                        let existing: Vec<NamedNode> = {
2160                            let map = if is_rel { &self.g.rels } else { &self.g.nodes };
2161                            map.get(&s)
2162                                .map(|e| e.props.iter().map(|(p, _)| p.clone()).collect())
2163                                .unwrap_or_default()
2164                        };
2165                        let mut done = BTreeSet::new();
2166                        for p in existing {
2167                            if done.insert(p.clone())
2168                                && !m.contains_key(&self.vocab.name(p.as_str()))
2169                            {
2170                                self.set_prop(&s, is_rel, &p, None);
2171                            }
2172                        }
2173                    }
2174                    for (k, v) in m {
2175                        let l = v.to_literal()?.map(Term::from);
2176                        self.set_prop(&s, is_rel, &self.vocab.iri(&k), l);
2177                    }
2178                }
2179            }
2180            SetItem::Labels { var, labels } => match row.get(var) {
2181                Some(Value::Node(n)) => {
2182                    let id = n.id.clone();
2183                    for l in labels {
2184                        let iri = self.vocab.iri(l);
2185                        let e = self.g.nodes.entry(id.clone()).or_default();
2186                        if !e.labels.contains(&iri) {
2187                            e.labels.push(iri.clone());
2188                            self.g.stats.labels_added += 1;
2189                        }
2190                        self.g.set(
2191                            Quad::new(id.clone(), rdf::TYPE.into_owned(), iri, self.graph.clone()),
2192                            true,
2193                        );
2194                    }
2195                    self.g.touch(&id);
2196                }
2197                Some(Value::Null) => {}
2198                _ => return Err(CypherError::semantic(format!("`{var}` is not a node"))),
2199            },
2200        }
2201        self.refresh_rows(std::slice::from_mut(row))
2202    }
2203
2204    fn remove_item(&mut self, it: &RemoveItem, row: &mut Row) -> Result<()> {
2205        match it {
2206            RemoveItem::Property { var, key } => {
2207                if let Some((s, is_rel)) = self.target(var, row)? {
2208                    self.set_prop(&s, is_rel, &self.vocab.iri(key), None);
2209                }
2210            }
2211            RemoveItem::Labels { var, labels } => match row.get(var) {
2212                Some(Value::Node(n)) => {
2213                    let id = n.id.clone();
2214                    for l in labels {
2215                        let iri = self.vocab.iri(l);
2216                        let e = self.g.nodes.entry(id.clone()).or_default();
2217                        if e.labels.contains(&iri) {
2218                            e.labels.retain(|x| *x != iri);
2219                            self.g.stats.labels_removed += 1;
2220                        }
2221                        self.g.set(
2222                            Quad::new(id.clone(), rdf::TYPE.into_owned(), iri, self.graph.clone()),
2223                            false,
2224                        );
2225                    }
2226                    self.g.touch(&id);
2227                }
2228                Some(Value::Null) => {}
2229                _ => return Err(CypherError::semantic(format!("`{var}` is not a node"))),
2230            },
2231        }
2232        self.refresh_rows(std::slice::from_mut(row))
2233    }
2234
2235    fn delete_value(&mut self, v: Value, detach: bool) -> Result<()> {
2236        match v {
2237            Value::Null => {}
2238            Value::Node(n) => {
2239                let e = self.g.nodes.entry(n.id.clone()).or_default();
2240                if !e.deleted {
2241                    e.deleted = true;
2242                    self.g.node_deletes.push((n.id, detach));
2243                }
2244            }
2245            Value::Relationship(r) => {
2246                if let Some(rid) = &r.reifier {
2247                    if self.g.provisional.contains(rid) {
2248                        for c in &mut self.g.created_rels {
2249                            if &c.rid == rid && !c.dropped {
2250                                c.dropped = true;
2251                                self.g.stats.relationships_deleted += 1;
2252                            }
2253                        }
2254                        return Ok(());
2255                    }
2256                }
2257                let triple =
2258                    Triple::new(r.start.clone(), r.predicate.clone(), subject_term(&r.end));
2259                let rid = r
2260                    .reifier
2261                    .clone()
2262                    .or_else(|| self.g.reified.get(&triple).cloned());
2263                if !self
2264                    .g
2265                    .rel_deletes
2266                    .iter()
2267                    .any(|d| d.triple == triple && d.rid == rid)
2268                {
2269                    self.g.rel_deletes.push(RelDelete { triple, rid });
2270                    self.g.stats.relationships_deleted += 1;
2271                }
2272            }
2273            Value::Path(p) => {
2274                for r in p.relationships {
2275                    self.delete_value(Value::Relationship(r), detach)?;
2276                }
2277                for n in p.nodes {
2278                    self.delete_value(Value::Node(n), detach)?;
2279                }
2280            }
2281            Value::List(items) => {
2282                for i in items {
2283                    self.delete_value(i, detach)?;
2284                }
2285            }
2286            other => {
2287                return Err(CypherError::runtime(format!(
2288                    "cannot delete a {}",
2289                    other.type_name()
2290                )))
2291            }
2292        }
2293        Ok(())
2294    }
2295
2296    // ----- fix-up and write -----
2297
2298    fn has_writes(&self) -> bool {
2299        !self.g.ops.is_empty()
2300            || !self.g.created_rels.is_empty()
2301            || !self.g.node_deletes.is_empty()
2302            || !self.g.rel_deletes.is_empty()
2303    }
2304
2305    fn begin_fixup(&mut self) -> Result<CypherStep> {
2306        if !self.has_writes() {
2307            return self.finish();
2308        }
2309        let cols = spo_cols(&self.caps, "q");
2310        let g = self.graph_cond("q");
2311        let mut stmts = Vec::new();
2312        let dels: Vec<i64> = self
2313            .g
2314            .node_deletes
2315            .iter()
2316            .filter(|(n, _)| !self.g.created_nodes.contains(n))
2317            .map(|(n, _)| subject_id(n.as_ref()))
2318            .collect();
2319        for chunk in dels.chunks(CHUNK) {
2320            let l = id_list(chunk);
2321            stmts.push(Statement::new(format!(
2322                "SELECT {cols} FROM quads q WHERE {g} AND (q.s IN ({l}) OR q.o IN ({l}))"
2323            )));
2324        }
2325        // Do the triples of created relationships already exist?
2326        let mut conds = Vec::new();
2327        for c in &self.g.created_rels {
2328            if c.dropped
2329                || self.g.created_nodes.contains(&c.s)
2330                || self.g.created_nodes.contains(&c.o)
2331            {
2332                continue;
2333            }
2334            conds.push(format!(
2335                "(q.s = {} AND q.p = {} AND q.o = {})",
2336                subject_id(c.s.as_ref()),
2337                named_node_id(c.p.as_str()),
2338                subject_id(c.o.as_ref())
2339            ));
2340        }
2341        conds.sort();
2342        conds.dedup();
2343        for chunk in conds.chunks(100) {
2344            stmts.push(Statement::new(format!(
2345                "SELECT {cols} FROM quads q WHERE {g} AND ({})",
2346                chunk.join(" OR ")
2347            )));
2348        }
2349        self.start_fetch(State::Fixup1, stmts)
2350    }
2351
2352    fn absorb_fixup1(&mut self, quads: Vec<[Term; 3]>) {
2353        let dels: HashSet<Term> = self
2354            .g
2355            .node_deletes
2356            .iter()
2357            .map(|(n, _)| subject_term(n))
2358            .collect();
2359        for q in quads {
2360            let [s, p, o] = &q;
2361            if dels.contains(s) || dels.contains(o) {
2362                self.fix.incident.push(q.clone());
2363            }
2364            if let (Some(s), Term::NamedNode(p)) = (to_subject(s), p) {
2365                self.fix
2366                    .existing
2367                    .insert(Triple::new(s, p.clone(), o.clone()));
2368            }
2369        }
2370    }
2371
2372    /// Relationship triples whose reifiers matter for the fix-up.
2373    fn fix_triples(&self) -> Vec<Triple> {
2374        let mut out: Vec<Triple> = Vec::new();
2375        for c in &self.g.created_rels {
2376            if !c.dropped {
2377                out.push(Triple::new(c.s.clone(), c.p.clone(), subject_term(&c.o)));
2378            }
2379        }
2380        for d in &self.g.rel_deletes {
2381            out.push(d.triple.clone());
2382        }
2383        for [s, p, o] in &self.fix.incident {
2384            if let (Some(s), Term::NamedNode(p)) = (to_subject(s), p) {
2385                if is_rel_triple(p, o) {
2386                    out.push(Triple::new(s, p.clone(), o.clone()));
2387                }
2388            }
2389        }
2390        out.sort_by_key(|t| t.to_string());
2391        out.dedup();
2392        out
2393    }
2394
2395    fn fixup2(&mut self) -> Result<CypherStep> {
2396        let tids: Vec<i64> = self
2397            .fix_triples()
2398            .iter()
2399            .map(|t| triple_id(t.as_ref()))
2400            .collect();
2401        let cols = spo_cols(&self.caps, "q");
2402        let reifies_id = named_node_id(REIFIES);
2403        let (gr, gq) = (self.graph_cond("r"), self.graph_cond("q"));
2404        let mut stmts = Vec::new();
2405        for chunk in tids.chunks(CHUNK) {
2406            // Every quad of every reifier of these triples.
2407            stmts.push(Statement::new(format!(
2408                "SELECT {cols} FROM quads r JOIN quads q ON q.s = r.s WHERE r.p = {reifies_id} AND r.o IN ({}) AND {gr} AND {gq}",
2409                id_list(chunk)
2410            )));
2411        }
2412        self.start_fetch(State::Fixup2, stmts)
2413    }
2414
2415    fn apply_fixup(&mut self) -> Result<CypherStep> {
2416        let graph = self.graph.clone();
2417        // Reifiers of each triple, and all their quads.
2418        let mut reifiers: HashMap<Triple, Vec<NamedOrBlankNode>> = HashMap::new();
2419        let mut rid_quads: HashMap<NamedOrBlankNode, Vec<Quad>> = HashMap::new();
2420        for [s, p, o] in std::mem::take(&mut self.fix.reifier_quads) {
2421            let (Some(s), Term::NamedNode(p)) = (to_subject(&s), p) else {
2422                continue;
2423            };
2424            if p.as_str() == REIFIES {
2425                if let Term::Triple(t) = &o {
2426                    let list = reifiers.entry((**t).clone()).or_default();
2427                    if !list.contains(&s) {
2428                        list.push(s.clone());
2429                    }
2430                }
2431            }
2432            rid_quads
2433                .entry(s.clone())
2434                .or_default()
2435                .push(Quad::new(s, p, o, graph.clone()));
2436        }
2437        // Deleted relationships.
2438        let mut deleted_rids: HashSet<NamedOrBlankNode> = HashSet::new();
2439        let mut touched_triples: Vec<Triple> = Vec::new();
2440        for d in self.g.rel_deletes.clone() {
2441            match &d.rid {
2442                Some(rid) => {
2443                    for q in rid_quads.get(rid).cloned().unwrap_or_default() {
2444                        self.g.set(q, false);
2445                    }
2446                    self.g.set(
2447                        Quad::new(
2448                            rid.clone(),
2449                            reifies(),
2450                            Term::Triple(Box::new(d.triple.clone())),
2451                            graph.clone(),
2452                        ),
2453                        false,
2454                    );
2455                    deleted_rids.insert(rid.clone());
2456                    touched_triples.push(d.triple.clone());
2457                }
2458                None => {
2459                    self.g.set(
2460                        Quad::new(
2461                            d.triple.subject.clone(),
2462                            d.triple.predicate.clone(),
2463                            d.triple.object.clone(),
2464                            graph.clone(),
2465                        ),
2466                        false,
2467                    );
2468                }
2469            }
2470        }
2471        // Deleted nodes.
2472        let deleted_nodes: HashSet<NamedOrBlankNode> =
2473            self.g.node_deletes.iter().map(|(n, _)| n.clone()).collect();
2474        let deleted_triples: HashSet<Triple> = self
2475            .g
2476            .rel_deletes
2477            .iter()
2478            .filter(|d| d.rid.is_none())
2479            .map(|d| d.triple.clone())
2480            .collect();
2481        for (n, detach) in self.g.node_deletes.clone() {
2482            let nt = subject_term(&n);
2483            // Relationships created in this statement.
2484            for c in &mut self.g.created_rels {
2485                if !c.dropped && (c.s == n || c.o == n) {
2486                    if !detach {
2487                        return Err(CypherError::runtime(format!(
2488                            "cannot delete node <{}>: it still has relationships (use DETACH DELETE)",
2489                            crate::value::subject_str(&n)
2490                        )));
2491                    }
2492                    c.dropped = true;
2493                }
2494            }
2495            if self.g.created_nodes.contains(&n) {
2496                let quads: Vec<Quad> = self
2497                    .g
2498                    .order
2499                    .iter()
2500                    .filter(|q| q.subject == n)
2501                    .cloned()
2502                    .collect();
2503                for q in quads {
2504                    self.g.set(q, false);
2505                }
2506                self.g.stats.nodes_deleted += 1;
2507                continue;
2508            }
2509            let incident: Vec<[Term; 3]> = self
2510                .fix
2511                .incident
2512                .iter()
2513                .filter(|[s, _, o]| *s == nt || *o == nt)
2514                .cloned()
2515                .collect();
2516            for [s, p, o] in &incident {
2517                let (Some(s), Term::NamedNode(p)) = (to_subject(s), p) else {
2518                    continue;
2519                };
2520                let rel = is_rel_triple(p, o)
2521                    || (*o == nt && p.as_ref() != rdf::TYPE && p.as_str() != REIFIES);
2522                let triple = Triple::new(s.clone(), p.clone(), o.clone());
2523                if rel {
2524                    let rids = reifiers.get(&triple).cloned().unwrap_or_default();
2525                    let already = deleted_triples.contains(&triple)
2526                        || (!rids.is_empty() && rids.iter().all(|r| deleted_rids.contains(r)))
2527                        || (to_subject(o).is_some_and(|x| deleted_nodes.contains(&x))
2528                            && s == n
2529                            && detach);
2530                    if !detach && !already {
2531                        return Err(CypherError::runtime(format!(
2532                            "cannot delete node <{}>: it still has relationships (use DETACH DELETE)",
2533                            crate::value::subject_str(&n)
2534                        )));
2535                    }
2536                    if !already && !deleted_triples.contains(&triple) {
2537                        self.g.stats.relationships_deleted += 1;
2538                    }
2539                    for rid in rids {
2540                        for q in rid_quads.get(&rid).cloned().unwrap_or_default() {
2541                            self.g.set(q, false);
2542                        }
2543                        deleted_rids.insert(rid);
2544                    }
2545                }
2546                self.g
2547                    .set(Quad::new(s, p.clone(), o.clone(), graph.clone()), false);
2548            }
2549            self.g.stats.nodes_deleted += 1;
2550        }
2551        // Asserted triples whose last reifier was deleted.
2552        for t in touched_triples {
2553            let remaining = reifiers
2554                .get(&t)
2555                .map(|r| r.iter().filter(|x| !deleted_rids.contains(x)).count())
2556                .unwrap_or(0);
2557            let recreated = self.g.created_rels.iter().any(|c| {
2558                !c.dropped
2559                    && c.s == t.subject
2560                    && c.p == t.predicate
2561                    && subject_term(&c.o) == t.object
2562            });
2563            if remaining == 0 && !recreated {
2564                self.g.set(
2565                    Quad::new(
2566                        t.subject.clone(),
2567                        t.predicate.clone(),
2568                        t.object.clone(),
2569                        graph.clone(),
2570                    ),
2571                    false,
2572                );
2573            }
2574        }
2575        // Created relationships: a single plain one is just a triple; otherwise every
2576        // relationship of the triple gets a reifier.
2577        let mut groups: Vec<(Triple, Vec<RelCreate>)> = Vec::new();
2578        for c in self.g.created_rels.clone() {
2579            if c.dropped {
2580                self.g.dropped.insert(c.rid.clone());
2581                continue;
2582            }
2583            let t = Triple::new(c.s.clone(), c.p.clone(), subject_term(&c.o));
2584            match groups.iter_mut().find(|(x, _)| *x == t) {
2585                Some((_, v)) => v.push(c),
2586                None => groups.push((t, vec![c])),
2587            }
2588        }
2589        for (t, cs) in groups {
2590            let deleted_now = self.g.ops.get(&Quad::new(
2591                t.subject.clone(),
2592                t.predicate.clone(),
2593                t.object.clone(),
2594                graph.clone(),
2595            )) == Some(&false);
2596            let exists = self.fix.existing.contains(&t) && !deleted_now;
2597            let existing_rids: Vec<NamedOrBlankNode> = reifiers
2598                .get(&t)
2599                .map(|r| {
2600                    r.iter()
2601                        .filter(|x| !deleted_rids.contains(x))
2602                        .cloned()
2603                        .collect()
2604                })
2605                .unwrap_or_default();
2606            let plain = !exists
2607                && cs.len() == 1
2608                && self
2609                    .g
2610                    .rels
2611                    .get(&cs[0].rid)
2612                    .is_none_or(|e| e.props.is_empty());
2613            self.g.set(
2614                Quad::new(
2615                    t.subject.clone(),
2616                    t.predicate.clone(),
2617                    t.object.clone(),
2618                    graph.clone(),
2619                ),
2620                true,
2621            );
2622            if plain {
2623                self.g.dropped.insert(cs[0].rid.clone());
2624                continue;
2625            }
2626            if exists && existing_rids.is_empty() && !self.g.reified.contains_key(&t) {
2627                // The relationship already stored becomes one of several: reify it too.
2628                let old = self.mint(&self.vocab.relationship_prefix.clone());
2629                self.g.set(
2630                    Quad::new(
2631                        old.clone(),
2632                        reifies(),
2633                        Term::Triple(Box::new(t.clone())),
2634                        graph.clone(),
2635                    ),
2636                    true,
2637                );
2638                self.g.reified.insert(t.clone(), old);
2639            }
2640            for c in cs {
2641                self.g.set(
2642                    Quad::new(
2643                        c.rid.clone(),
2644                        reifies(),
2645                        Term::Triple(Box::new(t.clone())),
2646                        graph.clone(),
2647                    ),
2648                    true,
2649                );
2650                let props = self
2651                    .g
2652                    .rels
2653                    .get(&c.rid)
2654                    .map(|e| e.props.clone())
2655                    .unwrap_or_default();
2656                for (p, o) in props {
2657                    self.g
2658                        .set(Quad::new(c.rid.clone(), p, o, graph.clone()), true);
2659                }
2660            }
2661        }
2662        // SHACL shapes of every node the statement created or changed.
2663        if let Some(shapes) = &self.shapes {
2664            for n in &self.g.touched_nodes {
2665                let e = self.g.nodes.get(n).cloned().unwrap_or_default();
2666                if e.deleted {
2667                    continue;
2668                }
2669                shapes.check(n, &e.labels, &e.props, &self.vocab)?;
2670            }
2671        }
2672        let deletes: Vec<Quad> = self
2673            .g
2674            .order
2675            .iter()
2676            .filter(|q| self.g.ops.get(*q) == Some(&false))
2677            .cloned()
2678            .collect();
2679        let inserts: Vec<Quad> = self
2680            .g
2681            .order
2682            .iter()
2683            .filter(|q| self.g.ops.get(*q) == Some(&true))
2684            .cloned()
2685            .collect();
2686        if deletes.is_empty() && inserts.is_empty() {
2687            return self.finish();
2688        }
2689        let schema = deletes
2690            .iter()
2691            .chain(&inserts)
2692            .any(|q| oxilite_core::reason::is_schema_quad(q.as_ref()));
2693        let mut stmts =
2694            EncodedQuads::new(deletes.iter().map(Quad::as_ref)).delete_statements(&self.caps);
2695        stmts.extend(
2696            EncodedQuads::new(inserts.iter().map(Quad::as_ref)).insert_statements(&self.caps),
2697        );
2698        stmts.extend(oxilite_core::ops::schema_refresh_for(
2699            deletes.iter().chain(&inserts).map(Quad::as_ref),
2700        ));
2701        self.schema_changed = schema;
2702        self.state = State::Write;
2703        Ok(CypherStep::Write(Request::atomic(stmts)))
2704    }
2705
2706    fn finish(&mut self) -> Result<CypherStep> {
2707        self.state = State::Finished;
2708        let mut rows = std::mem::take(&mut self.outputs);
2709        if !self.g.dropped.is_empty() || !self.g.reified.is_empty() {
2710            for r in &mut rows {
2711                for v in r.iter_mut() {
2712                    patch_reifiers(v, &self.g.dropped, &self.g.reified);
2713                }
2714            }
2715        }
2716        // UNION (without ALL) removes duplicates.
2717        if self.plan.parts.len() > 1 && self.plan.union_all.iter().any(|a| !*a) {
2718            let mut seen = HashSet::new();
2719            rows.retain(|r| seen.insert(r.iter().map(Value::group_key).collect::<Vec<_>>()));
2720        }
2721        Ok(CypherStep::Done(CypherResult {
2722            columns: self.plan.columns.clone(),
2723            rows,
2724            stats: std::mem::take(&mut self.g.stats),
2725            schema_changed: self.schema_changed,
2726        }))
2727    }
2728}
2729
2730fn solutions(out: QueryOutput) -> Result<Vec<HashMap<Variable, Term>>> {
2731    match out {
2732        QueryOutput::Solutions { variables, rows } => Ok(rows
2733            .into_iter()
2734            .map(|r| {
2735                variables
2736                    .iter()
2737                    .cloned()
2738                    .zip(r)
2739                    .filter_map(|(v, t)| t.map(|t| (v, t)))
2740                    .collect()
2741            })
2742            .collect()),
2743        _ => Err(CypherError::runtime("unexpected query output")),
2744    }
2745}
2746
2747fn patch_reifiers(
2748    v: &mut Value,
2749    dropped: &HashSet<NamedOrBlankNode>,
2750    reified: &HashMap<Triple, NamedOrBlankNode>,
2751) {
2752    match v {
2753        Value::Relationship(r) => {
2754            if r.reifier.as_ref().is_some_and(|x| dropped.contains(x)) {
2755                r.reifier = None;
2756            }
2757            if r.reifier.is_none() {
2758                r.reifier = reified
2759                    .get(&Triple::new(
2760                        r.start.clone(),
2761                        r.predicate.clone(),
2762                        subject_term(&r.end),
2763                    ))
2764                    .cloned();
2765            }
2766        }
2767        Value::Path(p) => {
2768            for r in &mut p.relationships {
2769                let mut x = Value::Relationship(r.clone());
2770                patch_reifiers(&mut x, dropped, reified);
2771                if let Value::Relationship(x) = x {
2772                    *r = x;
2773                }
2774            }
2775        }
2776        Value::List(items) => items
2777            .iter_mut()
2778            .for_each(|i| patch_reifiers(i, dropped, reified)),
2779        Value::Map(m) => m
2780            .values_mut()
2781            .for_each(|i| patch_reifiers(i, dropped, reified)),
2782        _ => {}
2783    }
2784}
2785
2786fn entity_vars(b: &Bind) -> Vec<(Variable, bool)> {
2787    match b {
2788        Bind::Node { var, .. } => vec![(var.clone(), false)],
2789        Bind::Rel { r, .. } => vec![(r.rid.clone(), true)],
2790        Bind::Path { nodes, rels, .. } => nodes
2791            .iter()
2792            .map(|n| (n.clone(), false))
2793            .chain(rels.iter().map(|r| (r.rid.clone(), true)))
2794            .collect(),
2795        Bind::RelList { rels, .. } => rels.iter().map(|r| (r.rid.clone(), true)).collect(),
2796        _ => Vec::new(),
2797    }
2798}
2799
2800/// All shortest paths (or the first) from `src` to `t`, following the recorded parents.
2801fn unfold(
2802    parents: &HashMap<i64, (usize, Vec<(i64, [i64; 3])>)>,
2803    src: i64,
2804    t: i64,
2805    all: bool,
2806) -> Vec<IdPath> {
2807    const MAX_PATHS: usize = 10_000;
2808    let mut out = Vec::new();
2809    // Depth-first over parent choices, building paths backwards.
2810    let mut stack: Vec<(i64, Vec<i64>, Vec<[i64; 3]>)> = vec![(t, vec![t], Vec::new())];
2811    while let Some((n, ns, rs)) = stack.pop() {
2812        if n == src && rs.len() == parents.get(&t).map_or(0, |(l, _)| *l) {
2813            let mut ns = ns;
2814            let mut rs = rs;
2815            ns.reverse();
2816            rs.reverse();
2817            out.push((ns, rs));
2818            if !all || out.len() >= MAX_PATHS {
2819                break;
2820            }
2821            continue;
2822        }
2823        let Some((_, ps)) = parents.get(&n) else {
2824            continue;
2825        };
2826        let choices: &[(i64, [i64; 3])] = if all { ps } else { &ps[..ps.len().min(1)] };
2827        for (p, e) in choices.iter().rev() {
2828            if rs.contains(e) {
2829                continue;
2830            }
2831            let mut ns2 = ns.clone();
2832            ns2.push(*p);
2833            let mut rs2 = rs.clone();
2834            rs2.push(*e);
2835            stack.push((*p, ns2, rs2));
2836        }
2837    }
2838    out
2839}
2840
2841struct AggSpec {
2842    placeholder: String,
2843    func: String,
2844    distinct: bool,
2845    arg: Option<Expr>,
2846    arg2: Option<Expr>,
2847}
2848
2849fn extract_aggregates(e: &Expr, aggs: &mut Vec<AggSpec>) -> Expr {
2850    match e {
2851        Expr::CountStar => {
2852            let placeholder = format!("\u{1}agg{}", aggs.len());
2853            aggs.push(AggSpec {
2854                placeholder: placeholder.clone(),
2855                func: "count".into(),
2856                distinct: false,
2857                arg: None,
2858                arg2: None,
2859            });
2860            Expr::Var(placeholder)
2861        }
2862        Expr::Func {
2863            name,
2864            distinct,
2865            args,
2866        } if is_aggregate(name) => {
2867            let placeholder = format!("\u{1}agg{}", aggs.len());
2868            aggs.push(AggSpec {
2869                placeholder: placeholder.clone(),
2870                func: name.clone(),
2871                distinct: *distinct,
2872                arg: args.first().cloned(),
2873                arg2: args.get(1).cloned(),
2874            });
2875            Expr::Var(placeholder)
2876        }
2877        Expr::Binary(op, a, b) => Expr::Binary(
2878            *op,
2879            Box::new(extract_aggregates(a, aggs)),
2880            Box::new(extract_aggregates(b, aggs)),
2881        ),
2882        Expr::Unary(op, a) => Expr::Unary(*op, Box::new(extract_aggregates(a, aggs))),
2883        Expr::Func {
2884            name,
2885            distinct,
2886            args,
2887        } => Expr::Func {
2888            name: name.clone(),
2889            distinct: *distinct,
2890            args: args.iter().map(|a| extract_aggregates(a, aggs)).collect(),
2891        },
2892        Expr::List(items) => {
2893            Expr::List(items.iter().map(|a| extract_aggregates(a, aggs)).collect())
2894        }
2895        // The list of a comprehension or quantifier may be an aggregate (not the body).
2896        Expr::ListComp {
2897            var,
2898            list,
2899            filter,
2900            map,
2901        } => Expr::ListComp {
2902            var: var.clone(),
2903            list: Box::new(extract_aggregates(list, aggs)),
2904            filter: filter.clone(),
2905            map: map.clone(),
2906        },
2907        Expr::Quantified { q, var, list, pred } => Expr::Quantified {
2908            q: *q,
2909            var: var.clone(),
2910            list: Box::new(extract_aggregates(list, aggs)),
2911            pred: pred.clone(),
2912        },
2913        Expr::Map(items) => Expr::Map(
2914            items
2915                .iter()
2916                .map(|(k, a)| (k.clone(), extract_aggregates(a, aggs)))
2917                .collect(),
2918        ),
2919        Expr::Index(a, b) => Expr::Index(
2920            Box::new(extract_aggregates(a, aggs)),
2921            Box::new(extract_aggregates(b, aggs)),
2922        ),
2923        Expr::Prop(a, k) => Expr::Prop(Box::new(extract_aggregates(a, aggs)), k.clone()),
2924        Expr::Case {
2925            operand,
2926            whens,
2927            else_,
2928        } => Expr::Case {
2929            operand: operand
2930                .as_ref()
2931                .map(|o| Box::new(extract_aggregates(o, aggs))),
2932            whens: whens
2933                .iter()
2934                .map(|(w, t)| (extract_aggregates(w, aggs), extract_aggregates(t, aggs)))
2935                .collect(),
2936            else_: else_
2937                .as_ref()
2938                .map(|o| Box::new(extract_aggregates(o, aggs))),
2939        },
2940        other => other.clone(),
2941    }
2942}
2943
2944pub(crate) fn clause_name(c: &Clause) -> &'static str {
2945    match c {
2946        Clause::Match { optional: true, .. } => "OPTIONAL MATCH",
2947        Clause::Match { .. } => "MATCH",
2948        Clause::Unwind { .. } => "UNWIND",
2949        Clause::With(_) => "WITH",
2950        Clause::Return(_) => "RETURN",
2951        Clause::Create(_) => "CREATE",
2952        Clause::Merge { .. } => "MERGE",
2953        Clause::Set(_) => "SET",
2954        Clause::Remove(_) => "REMOVE",
2955        Clause::Delete { detach: true, .. } => "DETACH DELETE",
2956        Clause::Delete { .. } => "DELETE",
2957        Clause::Call { .. } => "CALL",
2958    }
2959}