Skip to main content

rete_core/sparql/
fedmerge.rs

1//! Solution modifiers over a federation (`rete federate`): each source answers
2//! the query on its own, so ORDER BY, OFFSET, LIMIT and aggregates have to be
3//! applied (or merged) once more over the sources' rows, which the caller holds
4//! as term tokens.
5//!
6//! [`FederationPlan::new`] reads the query's top-level modifiers off its
7//! algebra and **refuses** what the merged rows cannot support, naming why:
8//!
9//! * ORDER BY keys must be projected variables (the merge sees projected rows
10//!   only), not expressions;
11//! * an aggregate query is merged only when every projected column is a GROUP BY
12//!   variable or a plain `COUNT`, `SUM`, `MIN` or `MAX`; `AVG`, `SAMPLE`,
13//!   `GROUP_CONCAT`, `COUNT(DISTINCT …)`, HAVING and expressions over an
14//!   aggregate are refused. `MIN` and `MAX` merge exactly; `COUNT` and `SUM` add
15//!   the sources' totals, which counts a triple stored in two sources twice, so
16//!   they are merged only when the caller says the sources are `disjoint`;
17//! * a CONSTRUCT with OFFSET or LIMIT, or with an aggregate, is refused (its
18//!   LIMIT counts solutions, not triples).
19//!
20//! [`FederationPlan::source_query`] gives the text each source runs: the
21//! query itself, or with `LIMIT offset+limit` pushed down (an upper bound: the
22//! rows past it cannot be among the merged ones), or with its ORDER BY / LIMIT /
23//! OFFSET removed when the aggregate merge takes them over.
24//! [`FederationPlan::finish`] then folds the aggregates, sorts, and slices.
25
26use std::cmp::Ordering;
27use std::collections::BTreeMap;
28use std::sync::Arc;
29
30use spargebra::algebra::{
31    AggregateExpression, AggregateFunction, Expression, GraphPattern, OrderExpression,
32};
33use spargebra::Query;
34
35use super::lower::parse_query;
36use super::value::OrderKey;
37use super::SparqlError;
38use crate::bgp::Binding;
39
40const XSD: &str = "http://www.w3.org/2001/XMLSchema#";
41
42fn refuse(why: impl Into<String>) -> SparqlError {
43    SparqlError::Federation(why.into())
44}
45
46#[derive(Debug, Clone, Copy, PartialEq, Eq)]
47enum Fold {
48    Count,
49    Sum,
50    Min,
51    Max,
52}
53
54#[derive(Debug, Clone)]
55struct Grouping {
56    /// GROUP BY variables that are projected.
57    by: Vec<String>,
58    /// `(projected variable, how the sources' values combine)`.
59    cols: Vec<(String, Fold)>,
60}
61
62/// How to run one query over several sources and merge their rows: see the
63/// module docs.
64#[derive(Debug, Clone)]
65pub struct FederationPlan {
66    /// A SELECT (the only form the modifiers apply to).
67    select: bool,
68    offset: usize,
69    limit: Option<usize>,
70    /// ORDER BY keys: `(variable, descending)`.
71    order: Vec<(String, bool)>,
72    group: Option<Grouping>,
73}
74
75impl FederationPlan {
76    /// Plan `query`. `disjoint` says no triple is stored in two sources, which
77    /// lets `COUNT` and `SUM` be added up.
78    pub fn new(query: &str, disjoint: bool) -> Result<FederationPlan, SparqlError> {
79        let parsed = parse_query(query)?;
80        let (select, pattern) = match &parsed {
81            Query::Select { pattern, .. } => (true, pattern),
82            Query::Construct { pattern, .. } => (false, pattern),
83            // ASK and DESCRIBE have no modifiers to merge.
84            _ => {
85                return Ok(FederationPlan {
86                    select: false,
87                    offset: 0,
88                    limit: None,
89                    order: Vec::new(),
90                    group: None,
91                })
92            }
93        };
94
95        // Peel the top-level modifiers in the order spargebra nests them:
96        // Slice, Distinct/Reduced, Project, OrderBy, select expressions and
97        // HAVING, Group — each once and in that order, so a sub-SELECT's own
98        // modifiers are never mistaken for the query's.
99        let mut offset = 0;
100        let mut limit = None;
101        let mut project: Option<&[spargebra::term::Variable]> = None;
102        let mut order: Option<&[OrderExpression]> = None;
103        let mut extends: Vec<(&str, &Expression)> = Vec::new();
104        let mut having = false;
105        let mut group = None;
106        let mut stage = 0;
107        let mut p: &GraphPattern = pattern;
108        loop {
109            let (next, inner): (u8, &GraphPattern) = match p {
110                GraphPattern::Slice {
111                    inner,
112                    start,
113                    length,
114                } if stage < 1 => {
115                    offset = *start;
116                    limit = *length;
117                    (1, &**inner)
118                }
119                GraphPattern::Distinct { inner } | GraphPattern::Reduced { inner } if stage < 2 => {
120                    (2, &**inner)
121                }
122                GraphPattern::Project { inner, variables } if stage < 3 => {
123                    project = Some(variables);
124                    (3, &**inner)
125                }
126                GraphPattern::OrderBy { inner, expression } if stage < 4 => {
127                    order = Some(expression);
128                    (4, &**inner)
129                }
130                GraphPattern::Extend {
131                    inner,
132                    variable,
133                    expression,
134                } if stage <= 5 => {
135                    extends.push((variable.as_str(), expression));
136                    (5, &**inner)
137                }
138                GraphPattern::Filter { inner, .. } if stage <= 5 => {
139                    having = true;
140                    (5, &**inner)
141                }
142                GraphPattern::Group {
143                    variables,
144                    aggregates,
145                    ..
146                } if stage < 6 => {
147                    group = Some((variables, aggregates));
148                    break;
149                }
150                _ => break,
151            };
152            stage = next;
153            p = inner;
154        }
155
156        if !select {
157            if offset != 0 || limit.is_some() {
158                return Err(refuse(
159                    "a CONSTRUCT with OFFSET or LIMIT: they count solutions, and each source \
160                     would cut its own. Use a SELECT, or run the CONSTRUCT on one source",
161                ));
162            }
163            if group.is_some() {
164                return Err(refuse(
165                    "a CONSTRUCT over an aggregate is computed per source. Use a SELECT",
166                ));
167            }
168            return Ok(FederationPlan {
169                select: false,
170                offset: 0,
171                limit: None,
172                order: Vec::new(),
173                group: None,
174            });
175        }
176
177        let project: Vec<String> = project
178            .map(|v| v.iter().map(|v| v.as_str().to_string()).collect())
179            .unwrap_or_default();
180
181        let mut keys = Vec::new();
182        for o in order.unwrap_or(&[]) {
183            let (e, desc) = match o {
184                OrderExpression::Asc(e) => (e, false),
185                OrderExpression::Desc(e) => (e, true),
186            };
187            match e {
188                Expression::Variable(v) if project.iter().any(|p| p == v.as_str()) => {
189                    keys.push((v.as_str().to_string(), desc))
190                }
191                Expression::Variable(v) => {
192                    return Err(refuse(format!(
193                        "ORDER BY ?{}, which the query does not project: the merged rows hold \
194                         only the projected variables. Add it to the SELECT",
195                        v.as_str()
196                    )))
197                }
198                _ => {
199                    return Err(refuse(
200                        "ORDER BY an expression: the merge sorts the projected variables. Bind \
201                         the expression to a variable in the SELECT ((expr AS ?k)) and order by \
202                         that",
203                    ))
204                }
205            }
206        }
207
208        let grouping = match group {
209            None => None,
210            Some((by, aggregates)) => {
211                if having {
212                    return Err(refuse(
213                        "HAVING filters groups that are only partial in each source",
214                    ));
215                }
216                // `(COUNT(*) AS ?n)` is `?n = ?agg0` over the group's `?agg0`.
217                let alias = |name: &str| -> String {
218                    extends
219                        .iter()
220                        .find_map(|(v, e)| match e {
221                            Expression::Variable(a) if a.as_str() == name => Some((*v).to_string()),
222                            _ => None,
223                        })
224                        .unwrap_or_else(|| name.to_string())
225                };
226                if let Some((v, _)) = extends
227                    .iter()
228                    .find(|(_, e)| !matches!(e, Expression::Variable(a) if aggregates.iter().any(|(n, _)| n == a)))
229                {
230                    return Err(refuse(format!(
231                        "?{v} is an expression over a group or an aggregate. Select the \
232                         aggregate itself and compute the expression afterwards"
233                    )));
234                }
235                let mut cols = Vec::new();
236                for (name, agg) in aggregates {
237                    let out = alias(name.as_str());
238                    if !project.contains(&out) {
239                        continue; // computed but not selected (ORDER BY it is refused above)
240                    }
241                    let fold = match agg {
242                        AggregateExpression::CountSolutions { distinct: false } => Fold::Count,
243                        AggregateExpression::FunctionCall {
244                            name: AggregateFunction::Count,
245                            distinct: false,
246                            ..
247                        } => Fold::Count,
248                        AggregateExpression::FunctionCall {
249                            name: AggregateFunction::Sum,
250                            distinct: false,
251                            ..
252                        } => Fold::Sum,
253                        AggregateExpression::FunctionCall {
254                            name: AggregateFunction::Min,
255                            ..
256                        } => Fold::Min,
257                        AggregateExpression::FunctionCall {
258                            name: AggregateFunction::Max,
259                            ..
260                        } => Fold::Max,
261                        other => {
262                            let what = match other {
263                                AggregateExpression::CountSolutions { .. }
264                                | AggregateExpression::FunctionCall {
265                                    name: AggregateFunction::Count,
266                                    ..
267                                } => "COUNT(DISTINCT …)",
268                                AggregateExpression::FunctionCall {
269                                    name: AggregateFunction::Sum,
270                                    ..
271                                } => "SUM(DISTINCT …)",
272                                AggregateExpression::FunctionCall {
273                                    name: AggregateFunction::Avg,
274                                    ..
275                                } => "AVG",
276                                AggregateExpression::FunctionCall {
277                                    name: AggregateFunction::GroupConcat { .. },
278                                    ..
279                                } => "GROUP_CONCAT",
280                                AggregateExpression::FunctionCall {
281                                    name: AggregateFunction::Sample,
282                                    ..
283                                } => "SAMPLE",
284                                _ => "this aggregate",
285                            };
286                            return Err(refuse(format!(
287                                "{what} cannot be merged from per-source results. Only COUNT, \
288                                 SUM, MIN and MAX can; or query one source"
289                            )));
290                        }
291                    };
292                    if matches!(fold, Fold::Count | Fold::Sum) && !disjoint {
293                        return Err(refuse(
294                            "COUNT and SUM add each source's total, which counts a triple stored \
295                             in two sources twice. If the sources share no triples, say so with \
296                             --disjoint",
297                        ));
298                    }
299                    cols.push((out, fold));
300                }
301                let by_vars: Vec<String> = by.iter().map(|v| v.as_str().to_string()).collect();
302                for p in &project {
303                    if !by_vars.contains(p) && !cols.iter().any(|(c, _)| c == p) {
304                        return Err(refuse(format!(
305                            "?{p} is neither a GROUP BY variable nor an aggregate"
306                        )));
307                    }
308                }
309                Some(Grouping {
310                    by: by_vars
311                        .into_iter()
312                        .filter(|v| project.contains(v))
313                        .collect(),
314                    cols,
315                })
316            }
317        };
318
319        Ok(FederationPlan {
320            select: true,
321            offset,
322            limit,
323            order: keys,
324            group: grouping,
325        })
326    }
327
328    /// Whether equal rows from different sources are one row. An aggregate's
329    /// rows are not: two sources can each count 5.
330    pub fn dedup_rows(&self) -> bool {
331        self.group.is_none()
332    }
333
334    /// The query each source should run for the merge to give the right rows.
335    pub fn source_query(&self, query: &str) -> Result<String, SparqlError> {
336        if !self.select {
337            return Ok(query.to_string());
338        }
339        // What a source must not do itself: an OFFSET (the merge skips rows
340        // once, over all sources), and, for an aggregate, a LIMIT (it would cut
341        // the groups the merge adds up).
342        let cuts = self.offset > 0 || (self.limit.is_some() && self.group.is_some());
343        let unchanged = |why: &str| -> Result<String, SparqlError> {
344            if cuts {
345                Err(refuse(format!(
346                    "cannot take this query's {why} off the per-source queries to merge it"
347                )))
348            } else {
349                // Not understood well enough to rewrite, and a source's own
350                // LIMIT is only an upper bound: run as written, merge after.
351                Ok(query.to_string())
352            }
353        };
354        let Some(scan) = Scan::of(query) else {
355            return unchanged("OFFSET / LIMIT");
356        };
357        if self.group.is_some() {
358            // Each source returns its whole groups; the merge sorts and slices.
359            return Ok(scan.head(query).trim_end().to_string());
360        }
361        if self.limit.is_none() && self.offset == 0 {
362            return Ok(query.to_string());
363        }
364        let mut head = scan.head(query).trim_end().to_string();
365        let mut limit = String::new();
366        if let Some(l) = self.limit {
367            // Each source's first `offset + limit` rows (in the query's order)
368            // hold every row the merged result can need. Sources are merged as
369            // a set, so the cut must count distinct rows: DISTINCT per source.
370            let Some(at) = scan.select_end else {
371                return unchanged("OFFSET / LIMIT");
372            };
373            let rest = head[at..].trim_start();
374            if rest.len() >= 7 && rest[..7].eq_ignore_ascii_case("REDUCED") {
375                // REDUCED may keep duplicates, which would eat into the cut.
376                let from = at + (head[at..].len() - rest.len());
377                head.replace_range(from..from + 7, "DISTINCT");
378            } else if !(rest.len() >= 8 && rest[..8].eq_ignore_ascii_case("DISTINCT")) {
379                head.insert_str(at, " DISTINCT");
380            }
381            limit = format!(" LIMIT {}", self.offset.saturating_add(l));
382        }
383        let order = scan.order(query).trim();
384        let order = if order.is_empty() {
385            String::new()
386        } else {
387            format!(" {order}")
388        };
389        Ok(format!("{head}{order}{limit}"))
390    }
391
392    /// The merged rows: aggregates folded, ORDER BY, OFFSET and LIMIT applied.
393    pub fn finish(&self, rows: Vec<Binding>) -> Vec<Binding> {
394        if !self.select {
395            return rows;
396        }
397        let mut rows = match &self.group {
398            Some(g) => fold_groups(g, rows),
399            None => rows,
400        };
401        if !self.order.is_empty() {
402            let keyed: Vec<Vec<Option<OrderKey>>> = rows
403                .iter()
404                .map(|r| {
405                    self.order
406                        .iter()
407                        .map(|(v, _)| r.get(v).map(|t| OrderKey::new(Arc::from(t.as_str()))))
408                        .collect()
409                })
410                .collect();
411            let mut idx: Vec<usize> = (0..rows.len()).collect();
412            idx.sort_by(|&a, &b| {
413                for (k, (_, desc)) in self.order.iter().enumerate() {
414                    // Unbound sorts lowest (§15.1).
415                    let c = match (&keyed[a][k], &keyed[b][k]) {
416                        (None, None) => Ordering::Equal,
417                        (None, Some(_)) => Ordering::Less,
418                        (Some(_), None) => Ordering::Greater,
419                        (Some(x), Some(y)) => x.cmp(y),
420                    };
421                    let c = if *desc { c.reverse() } else { c };
422                    if c != Ordering::Equal {
423                        return c;
424                    }
425                }
426                Ordering::Equal
427            });
428            let mut taken: Vec<Option<Binding>> = rows.into_iter().map(Some).collect();
429            rows = idx.into_iter().filter_map(|i| taken[i].take()).collect();
430        }
431        let skip = self.offset.min(rows.len());
432        rows.drain(..skip);
433        if let Some(l) = self.limit {
434            rows.truncate(l);
435        }
436        rows
437    }
438}
439
440// --- aggregates ---------------------------------------------------------------
441
442fn fold_groups(g: &Grouping, rows: Vec<Binding>) -> Vec<Binding> {
443    let mut groups: BTreeMap<Vec<Option<String>>, Vec<Binding>> = BTreeMap::new();
444    for r in rows {
445        let key = g.by.iter().map(|v| r.get(v).cloned()).collect();
446        groups.entry(key).or_default().push(r);
447    }
448    // An aggregate without GROUP BY always has one group, even over no rows.
449    if groups.is_empty() && g.by.is_empty() {
450        groups.insert(Vec::new(), Vec::new());
451    }
452    groups
453        .into_iter()
454        .map(|(key, members)| {
455            let mut out = Binding::new();
456            for (v, val) in g.by.iter().zip(key) {
457                if let Some(val) = val {
458                    out.insert(v.clone(), val);
459                }
460            }
461            for (col, fold) in &g.cols {
462                let vals: Vec<Option<&str>> = members
463                    .iter()
464                    .map(|m| m.get(col).map(String::as_str))
465                    .collect();
466                if let Some(v) = fold_values(*fold, &vals) {
467                    out.insert(col.clone(), v);
468                }
469            }
470            out
471        })
472        .collect()
473}
474
475#[derive(Clone, Copy, PartialEq, PartialOrd)]
476enum Kind {
477    Integer,
478    Decimal,
479    Float,
480    Double,
481}
482
483/// A numeric token as `(kind, integer value, float value)`.
484fn number(tok: &str) -> Option<(Kind, i128, f64)> {
485    let (lex, dt) = match crate::terms::literal_parts(tok) {
486        Some((body, sfx)) => (
487            crate::terms::unescape_literal(body),
488            sfx.strip_prefix("^^<")?.strip_suffix('>')?.to_string(),
489        ),
490        None => (
491            tok.to_string(),
492            format!(
493                "{XSD}{}",
494                if tok.contains(['e', 'E']) {
495                    "double"
496                } else if tok.contains('.') {
497                    "decimal"
498                } else {
499                    "integer"
500                }
501            ),
502        ),
503    };
504    let kind = match dt.strip_prefix(XSD)? {
505        "integer" | "int" | "long" | "short" | "byte" | "nonNegativeInteger"
506        | "positiveInteger" | "nonPositiveInteger" | "negativeInteger" | "unsignedInt"
507        | "unsignedLong" | "unsignedShort" | "unsignedByte" => Kind::Integer,
508        "decimal" => Kind::Decimal,
509        "float" => Kind::Float,
510        "double" => Kind::Double,
511        _ => return None,
512    };
513    let lex = lex.trim();
514    let int = if kind == Kind::Integer {
515        lex.parse::<i128>().ok()?
516    } else {
517        0
518    };
519    let f = match kind {
520        Kind::Integer => int as f64,
521        _ => lex.parse::<f64>().ok()?,
522    };
523    Some((kind, int, f))
524}
525
526fn fold_values(fold: Fold, vals: &[Option<&str>]) -> Option<String> {
527    match fold {
528        Fold::Count | Fold::Sum => {
529            // An unbound total is an error in its source, and so in the sum.
530            let mut kind = Kind::Integer;
531            let mut int: Option<i128> = Some(0);
532            let mut float = 0.0f64;
533            for v in vals {
534                let (k, i, f) = number(v.as_deref()?)?;
535                if k > kind {
536                    kind = k;
537                }
538                int = int.and_then(|s| s.checked_add(i));
539                float += f;
540            }
541            Some(match kind {
542                Kind::Integer => crate::terms::make_literal(
543                    &int?.to_string(),
544                    None,
545                    Some(&format!("{XSD}integer")),
546                ),
547                Kind::Decimal => {
548                    // Shortest form past binary-float noise, as rete's own SUM.
549                    let cleaned: f64 = format!("{float:.14e}").parse().unwrap_or(float);
550                    crate::terms::make_literal(
551                        &cleaned.to_string(),
552                        None,
553                        Some(&format!("{XSD}decimal")),
554                    )
555                }
556                Kind::Float => crate::terms::make_literal(
557                    &format!("{float:E}"),
558                    None,
559                    Some(&format!("{XSD}float")),
560                ),
561                Kind::Double => crate::terms::make_literal(
562                    &format!("{float:E}"),
563                    None,
564                    Some(&format!("{XSD}double")),
565                ),
566            })
567        }
568        Fold::Min | Fold::Max => {
569            // A source whose group had no value leaves it unbound: skipped.
570            let mut best: Option<OrderKey> = None;
571            for v in vals.iter().flatten() {
572                let k = OrderKey::new(Arc::from(*v));
573                let take = match &best {
574                    None => true,
575                    Some(b) => match k.cmp(b) {
576                        Ordering::Less => fold == Fold::Min,
577                        Ordering::Greater => fold == Fold::Max,
578                        Ordering::Equal => false,
579                    },
580                };
581                if take {
582                    best = Some(k);
583                }
584            }
585            best.map(|k| k.token.to_string())
586        }
587    }
588}
589
590// --- the query text -------------------------------------------------------------
591
592/// Where the top-level `SELECT` keyword ends and the solution modifiers
593/// (`ORDER BY … LIMIT … OFFSET …`) start, found without parsing: the parsed
594/// algebra has no source positions. Only words at brace and parenthesis depth 0
595/// count, and strings, IRIs and comments are skipped, so a sub-SELECT's
596/// modifiers and a literal "LIMIT" are never mistaken for the query's.
597struct Scan {
598    /// Byte index just after the first top-level `SELECT`.
599    select_end: Option<usize>,
600    /// Start of the first top-level ORDER / LIMIT / OFFSET; `query.len()` if none.
601    modifiers: usize,
602    /// The ORDER BY clause's start and end (the first LIMIT / OFFSET after it).
603    order: Option<(usize, usize)>,
604}
605
606impl Scan {
607    fn of(q: &str) -> Option<Scan> {
608        let b = q.as_bytes();
609        let mut depth = 0i32;
610        let mut i = 0;
611        let mut select_end = None;
612        let mut order_start = None;
613        let mut limit_start = None;
614        let mut first_mod = None;
615        while i < b.len() {
616            match b[i] {
617                b'#' => {
618                    while i < b.len() && b[i] != b'\n' {
619                        i += 1;
620                    }
621                }
622                b'"' | b'\'' => {
623                    let quote = b[i];
624                    let long = b.get(i + 1) == Some(&quote) && b.get(i + 2) == Some(&quote);
625                    i += if long { 3 } else { 1 };
626                    loop {
627                        match b.get(i) {
628                            None => return None,
629                            Some(b'\\') => i += 2,
630                            Some(&c) if c == quote => {
631                                if !long {
632                                    i += 1;
633                                    break;
634                                }
635                                if b.get(i + 1) == Some(&quote) && b.get(i + 2) == Some(&quote) {
636                                    i += 3;
637                                    break;
638                                }
639                                i += 1;
640                            }
641                            Some(_) => i += 1,
642                        }
643                    }
644                }
645                b'<' => {
646                    // An IRI reference has no whitespace; `<` as an operator
647                    // is followed by one before any `>`.
648                    let mut j = i + 1;
649                    while j < b.len() && !b[j].is_ascii_whitespace() && b[j] != b'>' && b[j] != b'<'
650                    {
651                        j += 1;
652                    }
653                    i = if b.get(j) == Some(&b'>') {
654                        j + 1
655                    } else {
656                        i + 1
657                    };
658                }
659                b'{' | b'(' | b'[' => {
660                    depth += 1;
661                    i += 1;
662                }
663                b'}' | b')' | b']' => {
664                    depth -= 1;
665                    i += 1;
666                }
667                c if c.is_ascii_alphabetic() && depth == 0 => {
668                    let start = i;
669                    let prev_ok = start == 0
670                        || !(b[start - 1].is_ascii_alphanumeric()
671                            || matches!(
672                                b[start - 1],
673                                b'_' | b':' | b'?' | b'$' | b'-' | b'.' | b'@'
674                            ));
675                    while i < b.len()
676                        && (b[i].is_ascii_alphanumeric() || matches!(b[i], b'_' | b':' | b'-'))
677                    {
678                        i += 1;
679                    }
680                    if !prev_ok {
681                        continue;
682                    }
683                    let word = &q[start..i];
684                    if word.eq_ignore_ascii_case("SELECT") && select_end.is_none() {
685                        select_end = Some(i);
686                    } else if word.eq_ignore_ascii_case("ORDER") && order_start.is_none() {
687                        let rest = q[i..].trim_start();
688                        if rest.len() >= 2 && rest[..2].eq_ignore_ascii_case("BY") {
689                            order_start = Some(start);
690                            first_mod.get_or_insert(start);
691                        }
692                    } else if (word.eq_ignore_ascii_case("LIMIT")
693                        || word.eq_ignore_ascii_case("OFFSET"))
694                        && limit_start.is_none()
695                    {
696                        limit_start = Some(start);
697                        first_mod.get_or_insert(start);
698                    }
699                }
700                _ => i += 1,
701            }
702        }
703        if depth != 0 {
704            return None;
705        }
706        let modifiers = first_mod.unwrap_or(q.len());
707        // After the modifiers' start only ORDER BY …, then LIMIT n / OFFSET n.
708        if let Some(ls) = limit_start {
709            let mut toks = q[ls..].split_whitespace();
710            while let Some(kw) = toks.next() {
711                let n = toks.next()?;
712                if !(kw.eq_ignore_ascii_case("LIMIT") || kw.eq_ignore_ascii_case("OFFSET"))
713                    || n.parse::<u64>().is_err()
714                {
715                    return None;
716                }
717            }
718        }
719        Some(Scan {
720            select_end,
721            modifiers,
722            order: order_start.map(|s| (s, limit_start.unwrap_or(q.len()))),
723        })
724    }
725
726    /// The query up to its solution modifiers.
727    fn head<'a>(&self, q: &'a str) -> &'a str {
728        &q[..self.modifiers]
729    }
730
731    /// The ORDER BY clause, or `""`.
732    fn order<'a>(&self, q: &'a str) -> &'a str {
733        self.order.map_or("", |(s, e)| &q[s..e])
734    }
735}
736
737#[cfg(test)]
738mod tests {
739    use super::*;
740
741    fn row(pairs: &[(&str, &str)]) -> Binding {
742        pairs
743            .iter()
744            .map(|(k, v)| (k.to_string(), v.to_string()))
745            .collect()
746    }
747
748    fn int(n: i64) -> String {
749        format!("\"{n}\"^^<{XSD}integer>")
750    }
751
752    fn plan(q: &str) -> FederationPlan {
753        FederationPlan::new(q, true).unwrap()
754    }
755
756    fn why(q: &str, disjoint: bool) -> String {
757        FederationPlan::new(q, disjoint).unwrap_err().to_string()
758    }
759
760    #[test]
761    fn order_by_offset_and_limit_apply_to_the_merged_rows() {
762        let p = plan("SELECT ?x WHERE { ?x ?p ?o } ORDER BY DESC(?x) OFFSET 1 LIMIT 2");
763        let rows = ["<b>", "<d>", "<a>", "<c>"]
764            .iter()
765            .map(|x| row(&[("x", x)]))
766            .collect();
767        let got: Vec<String> = p.finish(rows).into_iter().map(|r| r["x"].clone()).collect();
768        assert_eq!(got, ["<c>", "<b>"]);
769    }
770
771    #[test]
772    fn unbound_sorts_first_and_numbers_by_value() {
773        let p = plan("SELECT ?n ?m WHERE { ?x ?p ?n OPTIONAL { ?x ?q ?m } } ORDER BY ?m ?n");
774        let rows = vec![
775            row(&[("n", &int(10)), ("m", &int(2))]),
776            row(&[("n", &int(9))]),
777            row(&[("n", &int(8)), ("m", &int(2))]),
778        ];
779        let got: Vec<String> = p.finish(rows).into_iter().map(|r| r["n"].clone()).collect();
780        assert_eq!(got, [int(9), int(8), int(10)]);
781    }
782
783    #[test]
784    fn order_by_must_use_projected_variables() {
785        let e = why("SELECT ?x WHERE { ?x ?p ?o } ORDER BY ?o", true);
786        assert!(e.contains("does not project"), "{e}");
787        let e = why("SELECT ?x WHERE { ?x ?p ?o } ORDER BY STR(?x)", true);
788        assert!(e.contains("an expression"), "{e}");
789        // `SELECT *` projects everything in scope.
790        plan("SELECT * WHERE { ?x ?p ?o } ORDER BY ?o");
791    }
792
793    #[test]
794    fn limit_is_pushed_down_as_an_upper_bound() {
795        let q = "PREFIX e: <http://e/>\nSELECT ?x WHERE { ?x e:p \"ORDER BY LIMIT 1\" } ORDER BY ?x LIMIT 5 OFFSET 2";
796        let p = plan(q);
797        assert_eq!(
798            p.source_query(q).unwrap(),
799            "PREFIX e: <http://e/>\nSELECT DISTINCT ?x WHERE { ?x e:p \"ORDER BY LIMIT 1\" } ORDER BY ?x LIMIT 7"
800        );
801        // Already DISTINCT; no ORDER BY.
802        let q = "select distinct ?x where { ?x ?p ?o } limit 3";
803        assert_eq!(
804            plan(q).source_query(q).unwrap(),
805            "select distinct ?x where { ?x ?p ?o } LIMIT 3"
806        );
807        // REDUCED becomes DISTINCT: it may keep duplicates, which eat into the cut.
808        let q = "SELECT REDUCED ?x WHERE { ?x ?p ?o } LIMIT 3";
809        assert_eq!(
810            plan(q).source_query(q).unwrap(),
811            "SELECT DISTINCT ?x WHERE { ?x ?p ?o } LIMIT 3"
812        );
813        // A sub-SELECT's LIMIT is not the query's: nothing to push.
814        let q = "SELECT ?x WHERE { { SELECT ?x WHERE { ?x ?p ?o } LIMIT 2 } }";
815        assert_eq!(plan(q).source_query(q).unwrap(), q);
816        // OFFSET alone is taken off: the merge skips the rows once.
817        let q = "SELECT ?x WHERE { ?x ?p ?o } ORDER BY ?x OFFSET 2";
818        assert_eq!(
819            plan(q).source_query(q).unwrap(),
820            "SELECT ?x WHERE { ?x ?p ?o } ORDER BY ?x"
821        );
822    }
823
824    #[test]
825    fn construct_modifiers_are_refused() {
826        let e = why("CONSTRUCT { ?s ?p ?o } WHERE { ?s ?p ?o } LIMIT 2", true);
827        assert!(e.contains("CONSTRUCT"), "{e}");
828        plan("CONSTRUCT { ?s ?p ?o } WHERE { ?s ?p ?o }");
829        plan("ASK { ?s ?p ?o }");
830    }
831
832    #[test]
833    fn count_and_sum_add_up_min_and_max_pick() {
834        let q = "SELECT ?g (COUNT(*) AS ?n) (SUM(?v) AS ?s) (MIN(?v) AS ?lo) (MAX(?v) AS ?hi) \
835                 WHERE { ?x ?g ?v } GROUP BY ?g ORDER BY DESC(?n) LIMIT 1";
836        let p = plan(q);
837        assert!(!p.dedup_rows());
838        assert_eq!(
839            p.source_query(q).unwrap(),
840            "SELECT ?g (COUNT(*) AS ?n) (SUM(?v) AS ?s) (MIN(?v) AS ?lo) (MAX(?v) AS ?hi) \
841             WHERE { ?x ?g ?v } GROUP BY ?g"
842        );
843        let mk = |g: &str, n: i64, s: &str, lo: i64, hi: i64| {
844            row(&[
845                ("g", g),
846                ("n", &int(n)),
847                ("s", s),
848                ("lo", &int(lo)),
849                ("hi", &int(hi)),
850            ])
851        };
852        let dec = |x: &str| format!("\"{x}\"^^<{XSD}decimal>");
853        let rows = vec![
854            mk("<a>", 2, &int(5), 1, 4),
855            mk("<b>", 1, &int(9), 9, 9),
856            mk("<a>", 2, &dec("0.5"), 0, 3),
857        ];
858        let got = p.finish(rows);
859        assert_eq!(got.len(), 1);
860        assert_eq!(got[0]["g"], "<a>");
861        assert_eq!(got[0]["n"], int(4));
862        assert_eq!(got[0]["s"], dec("5.5"));
863        assert_eq!(got[0]["lo"], int(0));
864        assert_eq!(got[0]["hi"], int(4));
865    }
866
867    #[test]
868    fn an_aggregate_without_group_by_is_one_row_even_over_nothing() {
869        let p = plan("SELECT (COUNT(*) AS ?n) WHERE { ?s ?p ?o }");
870        let got = p.finish(Vec::new());
871        assert_eq!(got.len(), 1);
872        assert_eq!(got[0]["n"], int(0));
873    }
874
875    #[test]
876    fn a_source_error_stays_an_error_in_the_sum() {
877        let p = plan("SELECT (SUM(?v) AS ?s) WHERE { ?s ?p ?v }");
878        let got = p.finish(vec![row(&[("s", &int(1))]), row(&[])]);
879        assert!(!got[0].contains_key("s"));
880    }
881
882    #[test]
883    fn aggregates_that_cannot_merge_are_refused() {
884        for (agg, name) in [
885            ("AVG(?v)", "AVG"),
886            ("SAMPLE(?v)", "SAMPLE"),
887            ("GROUP_CONCAT(?v)", "GROUP_CONCAT"),
888            ("COUNT(DISTINCT ?v)", "COUNT(DISTINCT"),
889        ] {
890            let e = why(&format!("SELECT ({agg} AS ?a) WHERE {{ ?s ?p ?v }}"), true);
891            assert!(e.contains(name), "{agg}: {e}");
892        }
893        let e = why(
894            "SELECT ?p (COUNT(*) AS ?n) WHERE { ?s ?p ?v } GROUP BY ?p HAVING (COUNT(*) > 1)",
895            true,
896        );
897        assert!(e.contains("HAVING"), "{e}");
898        let e = why("SELECT ((COUNT(*) + 1) AS ?n) WHERE { ?s ?p ?v }", true);
899        assert!(e.contains("expression"), "{e}");
900        let e = why("SELECT (COUNT(*) AS ?n) WHERE { ?s ?p ?v }", false);
901        assert!(e.contains("--disjoint"), "{e}");
902        // MIN and MAX are exact whether or not the sources overlap.
903        FederationPlan::new("SELECT (MAX(?v) AS ?m) WHERE { ?s ?p ?v }", false).unwrap();
904    }
905}