use crate::{
articulation_points_4d, bridges_4d, earliest_arrival_path_4d, reachable_4d,
time_dependent_dijkstra_4d, GraphNode4D, GraphPath4D, SpatialRegion, TemporalDijkstraResult4D,
TemporalEdge, TemporalJourney4D, TemporalWindow, TraversalContext4D,
};
use glam::Vec3;
use serde_json::{json, Value};
use std::collections::BTreeMap;
pub type GeoCypherRow = BTreeMap<String, Value>;
#[derive(Debug, Clone, PartialEq)]
pub enum GeoCypherResult {
NodeIds(Vec<u64>),
Edges(Vec<(u64, u64)>),
Rows(Vec<GeoCypherRow>),
Path(GraphPath4D),
Journey(TemporalJourney4D),
Dijkstra(TemporalDijkstraResult4D),
Bottlenecks {
articulation_points: Vec<u64>,
bridges: Vec<(u64, u64)>,
},
Components(Vec<Vec<u64>>),
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct GeoCypherError {
pub message: String,
}
impl GeoCypherError {
fn new(message: impl Into<String>) -> Self {
Self {
message: message.into(),
}
}
}
impl std::fmt::Display for GeoCypherError {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str(&self.message)
}
}
impl std::error::Error for GeoCypherError {}
pub fn query_4d(nodes: &[GraphNode4D], query: &str) -> Result<GeoCypherResult, GeoCypherError> {
let normalized = normalize_query(query);
let upper = normalized.to_ascii_uppercase();
if upper.starts_with("MATCH ") {
return execute_match(nodes, &normalized);
}
if upper.starts_with("CALL DB.ROUTE.TEMPORAL") {
return execute_temporal_route(nodes, &normalized);
}
if upper.starts_with("CALL DB.IMPACT.RADIUS") {
return execute_impact_radius(nodes, &normalized);
}
if upper.starts_with("CALL DB.RESILIENCE.BOTTLENECKS") {
return execute_bottlenecks(nodes, &normalized);
}
if upper.starts_with("CALL DB.SIGNAL.PROPAGATE") {
return execute_signal_propagation(nodes, &normalized);
}
Err(GeoCypherError::new("unsupported 4D Cypher query"))
}
fn execute_bottlenecks(
nodes: &[GraphNode4D],
query: &str,
) -> Result<GeoCypherResult, GeoCypherError> {
let args = between(query, "(", ")")?;
let parts = split_top_level(args, ',');
if parts.len() != 2 {
return Err(GeoCypherError::new(
"db.resilience.bottlenecks expects spatial_sphere and time_window",
));
}
let spatial_region = parse_spatial_sphere(parts[0])?;
let time_window = parse_time_window(parts[1])?;
let ctx = TraversalContext4D {
time_window: Some(time_window),
spatial_region: Some(spatial_region),
..TraversalContext4D::default()
};
Ok(GeoCypherResult::Bottlenecks {
articulation_points: articulation_points_4d(nodes, &ctx),
bridges: bridges_4d(nodes, &ctx),
})
}
fn execute_signal_propagation(
nodes: &[GraphNode4D],
query: &str,
) -> Result<GeoCypherResult, GeoCypherError> {
let args = between(query, "(", ")")?;
let parts = split_top_level(args, ',');
if parts.len() < 2 {
return Err(GeoCypherError::new(
"db.signal.propagate expects start and departure",
));
}
let start_id = parse_u64(parts[0])?;
let departure = parse_named_u64(parts[1], "departure")?;
let spatial_region = if parts.len() >= 3 {
Some(parse_spatial_sphere(parts[2])?)
} else {
None
};
let result = time_dependent_dijkstra_4d(nodes, start_id, departure, spatial_region)
.ok_or_else(|| GeoCypherError::new("signal propagation start node is not usable"))?;
Ok(GeoCypherResult::Dijkstra(result))
}
fn execute_match(nodes: &[GraphNode4D], query: &str) -> Result<GeoCypherResult, GeoCypherError> {
let ctx = parse_context(query)?;
let return_items = parse_return_items(query)?;
if return_items
.iter()
.any(|item| matches!(item, ReturnItem::Property { .. }))
{
return project_match_rows(nodes, &ctx, &return_items).map(GeoCypherResult::Rows);
}
Ok(GeoCypherResult::Edges(active_edges(nodes, &ctx)))
}
fn execute_temporal_route(
nodes: &[GraphNode4D],
query: &str,
) -> Result<GeoCypherResult, GeoCypherError> {
let args = between(query, "(", ")")?;
let parts = split_top_level(args, ',');
if parts.len() < 3 {
return Err(GeoCypherError::new(
"db.route.temporal expects start, goal, and departure",
));
}
let start_id = parse_u64(parts[0])?;
let goal_id = parse_u64(parts[1])?;
let departure = parse_named_u64(parts[2], "departure")?;
let journey = earliest_arrival_path_4d(nodes, start_id, goal_id, departure, None)
.ok_or_else(|| GeoCypherError::new("no temporal route found"))?;
Ok(GeoCypherResult::Journey(journey))
}
fn execute_impact_radius(
nodes: &[GraphNode4D],
query: &str,
) -> Result<GeoCypherResult, GeoCypherError> {
let args = between(query, "(", ")")?;
let parts = split_top_level(args, ',');
if parts.len() != 3 {
return Err(GeoCypherError::new(
"db.impact.radius expects start, spatial_sphere, and time_window",
));
}
let start_id = parse_u64(parts[0])?;
let spatial_region = parse_spatial_sphere(parts[1])?;
let time_window = parse_time_window(parts[2])?;
let ctx = TraversalContext4D {
time_window: Some(time_window),
spatial_region: Some(spatial_region),
..TraversalContext4D::default()
};
Ok(GeoCypherResult::NodeIds(reachable_4d(
nodes, start_id, &ctx,
)))
}
fn active_edges(nodes: &[GraphNode4D], ctx: &TraversalContext4D) -> Vec<(u64, u64)> {
let node_map: std::collections::HashMap<u64, &GraphNode4D> =
nodes.iter().map(|node| (node.id, node)).collect();
let mut edges = Vec::new();
for node in nodes {
if !node_is_valid(node, ctx) {
continue;
}
for edge in &node.successors {
let Some(next) = node_map.get(&edge.dst).copied() else {
continue;
};
if edge_is_valid(*edge, ctx) && node_is_valid(next, ctx) {
edges.push((node.id, edge.dst));
}
}
}
edges.sort_unstable();
edges
}
fn project_match_rows(
nodes: &[GraphNode4D],
ctx: &TraversalContext4D,
return_items: &[ReturnItem],
) -> Result<Vec<GeoCypherRow>, GeoCypherError> {
let node_map: std::collections::HashMap<u64, &GraphNode4D> =
nodes.iter().map(|node| (node.id, node)).collect();
let mut rows = Vec::new();
for node in nodes {
if !node_is_valid(node, ctx) {
continue;
}
for edge in &node.successors {
let Some(next) = node_map.get(&edge.dst).copied() else {
continue;
};
if !edge_is_valid(*edge, ctx) || !node_is_valid(next, ctx) {
continue;
}
let mut row = GeoCypherRow::new();
for item in return_items {
match item {
ReturnItem::Alias(alias) => {
row.insert(alias.clone(), node_object(alias, node, next)?);
}
ReturnItem::Property { alias, property } => {
let source = match alias.as_str() {
"a" => node,
"b" => next,
_ => {
return Err(GeoCypherError::new(format!(
"unknown MATCH alias {alias}"
)));
}
};
row.insert(
format!("{alias}.{property}"),
property_value(source, property),
);
}
}
}
rows.push(row);
}
}
rows.sort_by(|left, right| format!("{left:?}").cmp(&format!("{right:?}")));
Ok(rows)
}
#[derive(Debug, Clone, PartialEq, Eq)]
enum ReturnItem {
Alias(String),
Property { alias: String, property: String },
}
fn parse_return_items(query: &str) -> Result<Vec<ReturnItem>, GeoCypherError> {
let upper = query.to_ascii_uppercase();
let Some(return_idx) = upper.find(" RETURN ") else {
return Ok(vec![
ReturnItem::Alias("a".to_string()),
ReturnItem::Alias("b".to_string()),
]);
};
let return_clause = &query[return_idx + " RETURN ".len()..];
let items = split_top_level(return_clause, ',')
.into_iter()
.map(parse_return_item)
.collect::<Result<Vec<_>, _>>()?;
if items.is_empty() {
return Err(GeoCypherError::new("RETURN clause is empty"));
}
Ok(items)
}
fn parse_return_item(input: &str) -> Result<ReturnItem, GeoCypherError> {
let item = input.trim();
if item.is_empty() {
return Err(GeoCypherError::new("empty RETURN item"));
}
if let Some((alias, property)) = item.split_once('.') {
return Ok(ReturnItem::Property {
alias: alias.trim().to_string(),
property: property.trim().to_string(),
});
}
Ok(ReturnItem::Alias(item.to_string()))
}
fn node_object(alias: &str, a: &GraphNode4D, b: &GraphNode4D) -> Result<Value, GeoCypherError> {
let node = match alias {
"a" => a,
"b" => b,
_ => return Err(GeoCypherError::new(format!("unknown MATCH alias {alias}"))),
};
Ok(json!({
"id": node.id,
"x": node.x,
"y": node.y,
"z": node.z,
"begin_ts": node.begin_ts,
"end_ts": node.end_ts,
"properties": node.properties,
}))
}
fn property_value(node: &GraphNode4D, property: &str) -> Value {
match property {
"id" => json!(node.id),
"x" => json!(node.x),
"y" => json!(node.y),
"z" => json!(node.z),
"begin_ts" => json!(node.begin_ts),
"end_ts" => json!(node.end_ts),
other => node.properties.get(other).cloned().unwrap_or(Value::Null),
}
}
fn parse_context(query: &str) -> Result<TraversalContext4D, GeoCypherError> {
let mut ctx = TraversalContext4D::default();
let upper = query.to_ascii_uppercase();
if !upper.contains(" WHERE ") {
return Ok(ctx);
}
if let Some(time_call) = extract_call(query, "time_window")? {
ctx.time_window = Some(parse_time_window(time_call)?);
}
if let Some(spatial_call) = extract_call(query, "spatial_sphere")? {
ctx.spatial_region = Some(parse_spatial_sphere(spatial_call)?);
}
Ok(ctx)
}
fn parse_time_window(input: &str) -> Result<TemporalWindow, GeoCypherError> {
let args = between(input, "(", ")")?;
let parts = split_top_level(args, ',');
if parts.len() != 2 {
return Err(GeoCypherError::new("time_window expects start and end"));
}
Ok(TemporalWindow {
start: parse_u64(parts[0])?,
end: parse_u64(parts[1])?,
})
}
fn parse_spatial_sphere(input: &str) -> Result<SpatialRegion, GeoCypherError> {
let args = between(input, "(", ")")?;
let parts = split_top_level(args, ',');
if parts.len() != 2 {
return Err(GeoCypherError::new(
"spatial_sphere expects [x,y,z] and radius",
));
}
let coords = parse_vec3(parts[0])?;
let radius = parts[1]
.trim()
.parse::<f32>()
.map_err(|_| GeoCypherError::new("invalid spatial_sphere radius"))?;
Ok(SpatialRegion::Sphere {
center: coords,
radius,
})
}
fn parse_vec3(input: &str) -> Result<Vec3, GeoCypherError> {
let trimmed = input.trim();
let inner = trimmed
.strip_prefix('[')
.and_then(|value| value.strip_suffix(']'))
.ok_or_else(|| GeoCypherError::new("expected [x,y,z] vector"))?;
let parts: Vec<_> = inner.split(',').map(str::trim).collect();
if parts.len() != 3 {
return Err(GeoCypherError::new("expected three vector coordinates"));
}
Ok(Vec3::new(
parse_f32(parts[0])?,
parse_f32(parts[1])?,
parse_f32(parts[2])?,
))
}
fn parse_f32(input: &str) -> Result<f32, GeoCypherError> {
input
.trim()
.parse::<f32>()
.map_err(|_| GeoCypherError::new("invalid float"))
}
fn parse_u64(input: &str) -> Result<u64, GeoCypherError> {
input
.trim()
.parse::<u64>()
.map_err(|_| GeoCypherError::new("invalid integer"))
}
fn parse_named_u64(input: &str, name: &str) -> Result<u64, GeoCypherError> {
let (key, value) = input
.split_once(':')
.ok_or_else(|| GeoCypherError::new("expected named argument"))?;
if !key.trim().eq_ignore_ascii_case(name) {
return Err(GeoCypherError::new(format!("expected {name} argument")));
}
parse_u64(value)
}
fn normalize_query(query: &str) -> String {
query.split_whitespace().collect::<Vec<_>>().join(" ")
}
fn between<'a>(input: &'a str, start: &str, end: &str) -> Result<&'a str, GeoCypherError> {
let start_idx = input
.find(start)
.ok_or_else(|| GeoCypherError::new("missing opening delimiter"))?
+ start.len();
let end_idx = input[start_idx..]
.rfind(end)
.ok_or_else(|| GeoCypherError::new("missing closing delimiter"))?
+ start_idx;
Ok(&input[start_idx..end_idx])
}
fn extract_call<'a>(query: &'a str, name: &str) -> Result<Option<&'a str>, GeoCypherError> {
let Some(start_idx) = query.to_ascii_lowercase().find(name) else {
return Ok(None);
};
let tail = &query[start_idx..];
let open = tail
.find('(')
.ok_or_else(|| GeoCypherError::new("missing function opening paren"))?;
let mut depth = 0usize;
for (idx, ch) in tail[open..].char_indices() {
match ch {
'(' => depth += 1,
')' => {
depth -= 1;
if depth == 0 {
return Ok(Some(&tail[..open + idx + 1]));
}
}
_ => {}
}
}
Err(GeoCypherError::new("unterminated function call"))
}
fn split_top_level(input: &str, delimiter: char) -> Vec<&str> {
let mut parts = Vec::new();
let mut start = 0usize;
let mut paren_depth = 0usize;
let mut bracket_depth = 0usize;
for (idx, ch) in input.char_indices() {
match ch {
'(' => paren_depth += 1,
')' => paren_depth = paren_depth.saturating_sub(1),
'[' => bracket_depth += 1,
']' => bracket_depth = bracket_depth.saturating_sub(1),
value if value == delimiter && paren_depth == 0 && bracket_depth == 0 => {
parts.push(input[start..idx].trim());
start = idx + ch.len_utf8();
}
_ => {}
}
}
parts.push(input[start..].trim());
parts
}
fn node_is_valid(node: &GraphNode4D, ctx: &TraversalContext4D) -> bool {
if let Some(window) = ctx.time_window {
if !window.overlaps(node.begin_ts, node.end_ts) {
return false;
}
}
match (&ctx.spatial_candidates, ctx.spatial_region) {
(Some(candidates), _) => {
if !candidates.contains(&node.id) {
return false;
}
}
(None, Some(region)) => {
if !region.contains(node.position()) {
return false;
}
}
(None, None) => {}
}
true
}
fn edge_is_valid(edge: TemporalEdge, ctx: &TraversalContext4D) -> bool {
ctx.time_window
.map(|window| window.overlaps(edge.begin_ts, edge.end_ts))
.unwrap_or(true)
}