1use 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#[derive(Debug)]
37#[allow(clippy::large_enum_variant)]
38pub enum CypherStep {
39 Query(spargebra::Query, oxilite_core::QueryOptions),
41 Sql(Request),
43 Write(Request),
45 Done(CypherResult),
46}
47
48#[derive(Debug)]
50pub enum StepInput {
51 Output(QueryOutput),
52 Response(Response),
53}
54
55#[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#[derive(Debug, Clone, PartialEq)]
75pub struct CypherResult {
76 pub columns: Vec<String>,
77 pub rows: Vec<Vec<Value>>,
78 pub stats: WriteStats,
79 pub schema_changed: bool,
81}
82
83impl CypherResult {
84 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 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
123const 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
154struct 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 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 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
228fn 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#[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 reified: HashMap<Triple, NamedOrBlankNode>,
341 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
384pub(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#[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
413pub 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 found: Vec<HashMap<(i64, i64), Vec<IdPath>>>,
433 decoded: HashMap<i64, Term>,
434 pending_extra: Vec<i64>,
435 comp_raw: Vec<Vec<HashMap<Variable, Term>>>,
437}
438
439type IdPath = (Vec<i64>, Vec<[i64; 3]>);
441
442struct Bfs {
444 spec: usize,
445 level: usize,
446 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 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 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 pub fn notes(&self) -> &[String] {
527 &self.plan.notes
528 }
529
530 pub fn writes(&self) -> bool {
532 self.plan.writes
533 }
534
535 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 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 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 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 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 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 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 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 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 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 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 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 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 if !e.props.iter().any(|(q, v)| *q == p && *v == o) {
1032 e.props.push((p, o));
1033 }
1034 }
1035 }
1036 }
1037
1038 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 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 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, ¶ms)) {
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 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 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 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 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 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 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 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, ¶ms))? {
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, ¶ms))?;
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 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 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 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 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, ¶ms))?;
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, ¶ms))?;
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 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 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 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 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 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 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 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 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 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 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 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 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 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
2800fn 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 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 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}