formal_ai/
links_query.rs

1//! LinksQL — a read-only, GraphQL-flavoured query language over the knowledge
2//! link store, plus a Links-Notation REST envelope (`lino-rest-api` style).
3//!
4//! Issue #347 / R6 asks, "ideally", for two Links-native interfaces alongside
5//! the OpenAI REST surface:
6//!
7//! 1. a [`lino-rest-api`](https://github.com/link-foundation/lino-rest-api)-style
8//!    layer that speaks **Links Notation** envelopes (not JSON), and
9//! 2. a universal **LinksQL** query language extending the idea behind
10//!    [`link-cli`](https://github.com/link-foundation/link-cli) with GraphQL-like
11//!    field selection.
12//!
13//! R7 constrains the *external* REST surface to OpenAI-compatible only, so this
14//! is an **internal/adjacent** Links-Notation channel: the query is a string, the
15//! request/response envelope is Links Notation, and the same projection JSON the
16//! `/v1/graph` endpoint already serves is offered for tooling that wants it.
17//!
18//! ## Grammar (read-only)
19//!
20//! ```text
21//! MATCH (a)                         RETURN a            # every node
22//! MATCH (a)-[:contains]->(b)        RETURN a, b         # edges of one role
23//! MATCH (a)-[r]->(b)                RETURN a, r, b      # every edge
24//! MATCH (a)-[r:response_link]->(b)  RETURN a, b
25//! MATCH (a) WHERE a.id = "rule_greeting"        RETURN a
26//! MATCH (a) WHERE a.label CONTAINS "rule"       RETURN a
27//! ```
28//!
29//! The evaluator runs against [`crate::engine::knowledge_graph`], so a LinksQL
30//! query is provably consistent with the engine: filtering all edges by a role
31//! returns exactly the `/v1/graph` edges of that role (see the tests).
32
33use serde::Serialize;
34
35use crate::engine::{knowledge_graph, GraphEdge, GraphNode, KnowledgeGraph};
36
37/// A parsed LinksQL query.
38#[derive(Debug, Clone, PartialEq, Eq)]
39pub struct LinksQuery {
40    pub source: NodePattern,
41    pub edge: Option<EdgePattern>,
42    pub target: Option<NodePattern>,
43    pub filters: Vec<Filter>,
44    pub returns: Vec<String>,
45}
46
47/// A node pattern such as `(a)`.
48#[derive(Debug, Clone, PartialEq, Eq)]
49pub struct NodePattern {
50    pub var: String,
51}
52
53/// An edge pattern such as `-[r:role]->`.
54#[derive(Debug, Clone, PartialEq, Eq)]
55pub struct EdgePattern {
56    pub var: Option<String>,
57    pub role: Option<String>,
58}
59
60/// A `WHERE` filter such as `a.id = "rule_greeting"`.
61#[derive(Debug, Clone, PartialEq, Eq)]
62pub struct Filter {
63    pub var: String,
64    pub field: Field,
65    pub op: FilterOp,
66    pub value: String,
67}
68
69/// The field a filter targets.
70#[derive(Debug, Clone, Copy, PartialEq, Eq)]
71pub enum Field {
72    Id,
73    Label,
74    Role,
75}
76
77/// The comparison a filter applies.
78#[derive(Debug, Clone, Copy, PartialEq, Eq)]
79pub enum FilterOp {
80    Eq,
81    Contains,
82}
83
84/// A parse or evaluation failure with a human-readable message.
85#[derive(Debug, Clone, PartialEq, Eq)]
86pub struct LinksQueryError {
87    pub message: String,
88}
89
90impl std::fmt::Display for LinksQueryError {
91    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
92        write!(formatter, "{}", self.message)
93    }
94}
95
96impl std::error::Error for LinksQueryError {}
97
98fn err(message: impl Into<String>) -> LinksQueryError {
99    LinksQueryError {
100        message: message.into(),
101    }
102}
103
104/// The nodes and edges a query selected, plus the originating query text.
105#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
106pub struct LinksQueryResult {
107    pub query: String,
108    pub nodes: Vec<GraphNode>,
109    pub edges: Vec<GraphEdge>,
110}
111
112impl LinksQueryResult {
113    /// Render the result as a Links-Notation envelope (the `lino-rest-api`
114    /// response shape). This is the preferred internal transport per R7.
115    #[must_use]
116    pub fn to_links_notation(&self) -> String {
117        let mut out = String::from("links_query_result\n");
118        out.push_str("  query \"");
119        out.push_str(&escape(&self.query));
120        out.push_str("\"\n");
121        for node in &self.nodes {
122            out.push_str("  node \"");
123            out.push_str(&escape(&node.id));
124            out.push_str("\"\n    label \"");
125            out.push_str(&escape(&node.label));
126            out.push_str("\"\n    links_notation \"");
127            out.push_str(&escape(&node.links_notation));
128            out.push_str("\"\n");
129        }
130        for edge in &self.edges {
131            out.push_str("  edge\n    from \"");
132            out.push_str(&escape(&edge.from));
133            out.push_str("\"\n    to \"");
134            out.push_str(&escape(&edge.to));
135            out.push_str("\"\n    role \"");
136            out.push_str(&escape(&edge.role));
137            out.push_str("\"\n");
138        }
139        out
140    }
141}
142
143impl KnowledgeGraph {
144    /// Render the graph as a `knowledge_graph` Links-Notation document — the
145    /// Links-native projection served from `/v1/links` (R6/R7). It carries the
146    /// same nodes and edges as the JSON `/v1/graph` view, only in Links
147    /// Notation, the project's preferred internal format.
148    #[must_use]
149    pub fn to_links_notation(&self) -> String {
150        let mut out = String::from("knowledge_graph\n");
151        for node in &self.nodes {
152            out.push_str("  node \"");
153            out.push_str(&escape(&node.id));
154            out.push_str("\"\n    label \"");
155            out.push_str(&escape(&node.label));
156            out.push_str("\"\n    links_notation \"");
157            out.push_str(&escape(&node.links_notation));
158            out.push_str("\"\n");
159        }
160        for edge in &self.edges {
161            out.push_str("  edge\n    from \"");
162            out.push_str(&escape(&edge.from));
163            out.push_str("\"\n    to \"");
164            out.push_str(&escape(&edge.to));
165            out.push_str("\"\n    role \"");
166            out.push_str(&escape(&edge.role));
167            out.push_str("\"\n");
168        }
169        out
170    }
171}
172
173fn escape(value: &str) -> String {
174    value.replace('\\', "\\\\").replace('"', "\\\"")
175}
176
177/// Parse and evaluate a LinksQL query against the engine's knowledge graph.
178///
179/// # Errors
180/// Returns [`LinksQueryError`] when the query cannot be parsed.
181pub fn run_links_query(query: &str) -> Result<LinksQueryResult, LinksQueryError> {
182    run_links_query_against(query, &knowledge_graph())
183}
184
185/// Evaluate a query against an explicit graph (used by tests and tooling).
186///
187/// # Errors
188/// Returns [`LinksQueryError`] when the query cannot be parsed.
189pub fn run_links_query_against(
190    query: &str,
191    graph: &KnowledgeGraph,
192) -> Result<LinksQueryResult, LinksQueryError> {
193    let parsed = parse_links_query(query)?;
194    Ok(evaluate(&parsed, query, graph))
195}
196
197/// Parse a LinksQL query string into a [`LinksQuery`].
198///
199/// # Errors
200/// Returns [`LinksQueryError`] when the `MATCH` / `RETURN` structure is invalid.
201pub fn parse_links_query(query: &str) -> Result<LinksQuery, LinksQueryError> {
202    let trimmed = query.trim();
203    let upper = trimmed.to_uppercase();
204    let match_start = upper
205        .find("MATCH")
206        .ok_or_else(|| err("query must contain a MATCH clause"))?;
207    let return_start = upper
208        .find("RETURN")
209        .ok_or_else(|| err("query must contain a RETURN clause"))?;
210    if return_start < match_start {
211        return Err(err("RETURN must follow MATCH"));
212    }
213
214    let after_match = &trimmed[match_start + "MATCH".len()..return_start];
215    let returns_text = &trimmed[return_start + "RETURN".len()..];
216
217    let (pattern_text, where_text) =
218        upper[match_start..return_start]
219            .find("WHERE")
220            .map_or((after_match, None), |relative| {
221                let absolute = match_start + relative;
222                (
223                    &trimmed[match_start + "MATCH".len()..absolute],
224                    Some(&trimmed[absolute + "WHERE".len()..return_start]),
225                )
226            });
227
228    let (source, edge, target) = parse_pattern(pattern_text.trim())?;
229    let filters = match where_text {
230        Some(text) => parse_filters(text.trim())?,
231        None => Vec::new(),
232    };
233    let returns = returns_text
234        .split(',')
235        .map(|item| {
236            item.trim()
237                .split('.')
238                .next()
239                .unwrap_or("")
240                .trim()
241                .to_owned()
242        })
243        .filter(|item| !item.is_empty())
244        .collect::<Vec<_>>();
245    if returns.is_empty() {
246        return Err(err("RETURN must name at least one variable"));
247    }
248
249    Ok(LinksQuery {
250        source,
251        edge,
252        target,
253        filters,
254        returns,
255    })
256}
257
258fn parse_pattern(
259    text: &str,
260) -> Result<(NodePattern, Option<EdgePattern>, Option<NodePattern>), LinksQueryError> {
261    let source_end = text
262        .find(')')
263        .ok_or_else(|| err("pattern must open with a node like (a)"))?;
264    let source = parse_node(&text[..=source_end])?;
265    let rest = text[source_end + 1..].trim();
266    if rest.is_empty() {
267        return Ok((source, None, None));
268    }
269
270    // Expect an edge `-[...]->` followed by a target node `(b)`.
271    let arrow = "->";
272    let arrow_pos = rest
273        .find(arrow)
274        .ok_or_else(|| err("edge pattern must end with ->"))?;
275    let edge_text = rest[..arrow_pos].trim();
276    let target_text = rest[arrow_pos + arrow.len()..].trim();
277    let edge = parse_edge(edge_text)?;
278    let target = parse_node(target_text)?;
279    Ok((source, Some(edge), Some(target)))
280}
281
282fn parse_node(text: &str) -> Result<NodePattern, LinksQueryError> {
283    let inner = text
284        .trim()
285        .strip_prefix('(')
286        .and_then(|value| value.strip_suffix(')'))
287        .ok_or_else(|| err(format!("invalid node pattern: {text}")))?;
288    let var = inner.split(':').next().unwrap_or("").trim().to_owned();
289    if var.is_empty() {
290        return Err(err("node pattern needs a variable name"));
291    }
292    Ok(NodePattern { var })
293}
294
295fn parse_edge(text: &str) -> Result<EdgePattern, LinksQueryError> {
296    let inner = text
297        .trim()
298        .strip_prefix('-')
299        .unwrap_or(text)
300        .trim()
301        .strip_prefix('[')
302        .and_then(|value| value.strip_suffix(']'))
303        .ok_or_else(|| err(format!("invalid edge pattern: {text}")))?;
304    let inner = inner.trim();
305    let (var_text, role_text) = if let Some((var, role)) = inner.split_once(':') {
306        (var.trim(), Some(role.trim()))
307    } else {
308        (inner, None)
309    };
310    let var = (!var_text.is_empty()).then(|| var_text.to_owned());
311    let role = role_text.and_then(|role| (!role.is_empty()).then(|| role.to_owned()));
312    Ok(EdgePattern { var, role })
313}
314
315fn parse_filters(text: &str) -> Result<Vec<Filter>, LinksQueryError> {
316    let mut filters = Vec::new();
317    for clause in split_filters(text) {
318        let clause = clause.trim();
319        if clause.is_empty() {
320            continue;
321        }
322        filters.push(parse_filter(clause)?);
323    }
324    Ok(filters)
325}
326
327fn split_filters(text: &str) -> Vec<String> {
328    // Split on AND / and, but never inside a quoted value.
329    let mut parts = Vec::new();
330    let mut current = String::new();
331    let mut in_quotes = false;
332    let chars: Vec<char> = text.chars().collect();
333    let mut index = 0;
334    while index < chars.len() {
335        let ch = chars[index];
336        if ch == '"' {
337            in_quotes = !in_quotes;
338            current.push(ch);
339            index += 1;
340            continue;
341        }
342        if !in_quotes {
343            let remaining: String = chars[index..].iter().collect();
344            let upper = remaining.to_uppercase();
345            if upper.starts_with("AND") && is_boundary(chars.get(index + 3).copied()) {
346                parts.push(std::mem::take(&mut current));
347                index += 3;
348                continue;
349            }
350        }
351        current.push(ch);
352        index += 1;
353    }
354    parts.push(current);
355    parts
356}
357
358fn is_boundary(ch: Option<char>) -> bool {
359    ch.is_none_or(char::is_whitespace)
360}
361
362fn parse_filter(clause: &str) -> Result<Filter, LinksQueryError> {
363    // Locate the operator outside of any quoted value, so a value such as
364    // `"contains"` is never mistaken for the CONTAINS operator and a `=` inside
365    // a quoted string never splits the clause.
366    let (op, split_at, op_len) = find_operator(clause)
367        .ok_or_else(|| err(format!("filter needs `=` or CONTAINS: {clause}")))?;
368    let lhs = clause[..split_at].trim();
369    let rhs = clause[split_at + op_len..].trim();
370
371    let (var, field_text) = lhs
372        .split_once('.')
373        .ok_or_else(|| err(format!("filter target must be `var.field`: {clause}")))?;
374    let field = match field_text.trim().to_lowercase().as_str() {
375        "id" => Field::Id,
376        "label" => Field::Label,
377        "role" => Field::Role,
378        other => return Err(err(format!("unknown field `{other}`"))),
379    };
380    let value = rhs.trim().trim_matches('"').to_owned();
381    Ok(Filter {
382        var: var.trim().to_owned(),
383        field,
384        op,
385        value,
386    })
387}
388
389/// Find the filter operator (`=` or `CONTAINS`) outside any quoted region.
390///
391/// Returns the operator, its byte offset, and its byte length. Scanning the
392/// unquoted spans only means a quoted value such as `"contains"` is never read
393/// as the CONTAINS keyword.
394fn find_operator(clause: &str) -> Option<(FilterOp, usize, usize)> {
395    let bytes = clause.as_bytes();
396    let upper = clause.to_uppercase();
397    let upper_bytes = upper.as_bytes();
398    let mut in_quotes = false;
399    let mut index = 0;
400    while index < bytes.len() {
401        let byte = bytes[index];
402        if byte == b'"' {
403            in_quotes = !in_quotes;
404            index += 1;
405            continue;
406        }
407        if !in_quotes {
408            if byte == b'=' {
409                return Some((FilterOp::Eq, index, 1));
410            }
411            if upper_bytes[index..].starts_with(b"CONTAINS") {
412                return Some((FilterOp::Contains, index, "CONTAINS".len()));
413            }
414        }
415        index += 1;
416    }
417    None
418}
419
420fn evaluate(query: &LinksQuery, source_text: &str, graph: &KnowledgeGraph) -> LinksQueryResult {
421    let mut result = LinksQueryResult {
422        query: source_text.trim().to_owned(),
423        nodes: Vec::new(),
424        edges: Vec::new(),
425    };
426
427    if query.edge.is_none() {
428        // Node-only query: filter all nodes by the filters that target the
429        // source variable.
430        for node in &graph.nodes {
431            if node_matches(node, &query.source.var, &query.filters) {
432                push_node(&mut result.nodes, node.clone());
433            }
434        }
435        return result;
436    }
437
438    let edge_pattern = query.edge.as_ref().expect("edge present");
439    let target = query.target.as_ref().expect("target present");
440    let want_source = query.returns.iter().any(|var| var == &query.source.var);
441    let want_target = query.returns.iter().any(|var| var == &target.var);
442
443    for edge in &graph.edges {
444        if let Some(role) = &edge_pattern.role {
445            if &edge.role != role {
446                continue;
447            }
448        }
449        let from_node = graph.nodes.iter().find(|node| node.id == edge.from);
450        let to_node = graph.nodes.iter().find(|node| node.id == edge.to);
451
452        if !node_filters_match(from_node, &query.source.var, &query.filters)
453            || !node_filters_match(to_node, &target.var, &query.filters)
454            || !edge_filters_match(edge, edge_pattern.var.as_deref(), &query.filters)
455        {
456            continue;
457        }
458
459        result.edges.push(edge.clone());
460        if want_source {
461            if let Some(node) = from_node {
462                push_node(&mut result.nodes, node.clone());
463            }
464        }
465        if want_target {
466            if let Some(node) = to_node {
467                push_node(&mut result.nodes, node.clone());
468            }
469        }
470    }
471    result
472}
473
474fn push_node(nodes: &mut Vec<GraphNode>, node: GraphNode) {
475    if !nodes.iter().any(|existing| existing.id == node.id) {
476        nodes.push(node);
477    }
478}
479
480fn node_matches(node: &GraphNode, var: &str, filters: &[Filter]) -> bool {
481    filters
482        .iter()
483        .filter(|filter| filter.var == var)
484        .all(|filter| apply_node_filter(node, filter))
485}
486
487fn node_filters_match(node: Option<&GraphNode>, var: &str, filters: &[Filter]) -> bool {
488    let relevant: Vec<&Filter> = filters
489        .iter()
490        .filter(|filter| filter.var == var && !matches!(filter.field, Field::Role))
491        .collect();
492    if relevant.is_empty() {
493        return true;
494    }
495    let Some(node) = node else {
496        return false;
497    };
498    relevant
499        .iter()
500        .all(|filter| apply_node_filter(node, filter))
501}
502
503fn edge_filters_match(edge: &GraphEdge, var: Option<&str>, filters: &[Filter]) -> bool {
504    let Some(var) = var else {
505        return !filters
506            .iter()
507            .any(|filter| matches!(filter.field, Field::Role) && filter.var != "__none__");
508    };
509    filters
510        .iter()
511        .filter(|filter| filter.var == var)
512        .all(|filter| match filter.op {
513            FilterOp::Eq => edge.role == filter.value,
514            FilterOp::Contains => edge.role.contains(&filter.value),
515        })
516}
517
518fn apply_node_filter(node: &GraphNode, filter: &Filter) -> bool {
519    let haystack = match filter.field {
520        Field::Id => &node.id,
521        Field::Label => &node.label,
522        Field::Role => return true,
523    };
524    match filter.op {
525        FilterOp::Eq => haystack == &filter.value,
526        FilterOp::Contains => haystack.contains(&filter.value),
527    }
528}
formal_ai/links_query.rs

formal_ai/
links_query.rs
