netget/server/scim/
query.rs

1//! SCIM queries (RFC 7644 §3.4.2, §3.5.2, §3.9): attribute paths, the filter grammar with its
2//! evaluation, PATCH paths, sorting and attribute projection. Rust applies these to the
3//! resources the handler supplies, so the handler only has to own the data.
4use super::schema::{self, ResourceType};
5use anyhow::{bail, ensure, Context, Result};
6use serde_json::{json, Map, Value};
7use std::cmp::Ordering;
8
9pub const MAX_FILTER_BYTES: usize = 4096;
10const MAX_DEPTH: usize = 16;
11const MAX_NODES: usize = 128;
12
13/// `[URI ":"] ATTRNAME ["." subAttr]`.
14#[derive(Debug, Clone, PartialEq)]
15pub struct AttrPath {
16    pub urn: Option<String>,
17    pub attr: String,
18    pub sub: Option<String>,
19}
20
21fn name_ok(s: &str) -> bool {
22    let mut c = s.chars();
23    c.next()
24        .is_some_and(|f| f.is_ascii_alphabetic() || f == '$')
25        && c.all(|ch| ch.is_ascii_alphanumeric() || ch == '_' || ch == '-' || ch == '$')
26        && s.len() <= 128
27}
28
29impl AttrPath {
30    pub fn parse(s: &str) -> Result<Self> {
31        ensure!(
32            !s.is_empty() && s.len() <= 512,
33            "empty or overlong attribute path"
34        );
35        // A path that is itself a schema URN names that whole extension (RFC 7644 §3.5.2).
36        if s.contains(':') && schema::schema(s).is_some() {
37            return Ok(Self {
38                urn: Some(s.to_owned()),
39                attr: String::new(),
40                sub: None,
41            });
42        }
43        let (urn, rest) = match s.rfind(':') {
44            Some(i) => (Some(s[..i].to_owned()), &s[i + 1..]),
45            None => (None, s),
46        };
47        if let Some(u) = &urn {
48            ensure!(
49                u.to_ascii_lowercase().starts_with("urn:"),
50                "attribute path {s:?} has a prefix that is not a URN"
51            );
52        }
53        let (attr, sub) = match rest.split_once('.') {
54            Some((a, b)) => (a, Some(b)),
55            None => (rest, None),
56        };
57        ensure!(name_ok(attr), "invalid attribute name in {s:?}");
58        if let Some(b) = sub {
59            ensure!(name_ok(b), "invalid sub-attribute name in {s:?}");
60        }
61        Ok(Self {
62            urn,
63            attr: attr.to_owned(),
64            sub: sub.map(str::to_owned),
65        })
66    }
67
68    pub fn to_json(&self) -> Value {
69        let attr = (!self.attr.is_empty()).then_some(&self.attr);
70        json!({"schema": self.urn, "attribute": attr, "sub_attribute": self.sub})
71    }
72
73    fn definition(&self, rt: &ResourceType) -> Option<&'static Value> {
74        schema::attribute(rt, self.urn.as_deref(), &self.attr, self.sub.as_deref())
75    }
76
77    /// The object this path's attribute lives in: the resource, or its extension object.
78    fn container<'a>(&self, rt: &ResourceType, resource: &'a Value) -> Option<&'a Value> {
79        match &self.urn {
80            Some(u) if !u.eq_ignore_ascii_case(rt.schema) => schema::member(resource, u),
81            _ => Some(resource),
82        }
83    }
84}
85
86#[derive(Debug, Clone, PartialEq)]
87pub enum Filter {
88    Compare {
89        path: AttrPath,
90        op: String,
91        value: Value,
92    },
93    Present(AttrPath),
94    And(Box<Filter>, Box<Filter>),
95    Or(Box<Filter>, Box<Filter>),
96    Not(Box<Filter>),
97    /// `attr[filter]`: some element of the multi-valued `attr` matches `filter`, whose paths
98    /// name sub-attributes.
99    ValuePath {
100        path: AttrPath,
101        filter: Box<Filter>,
102    },
103}
104
105const COMPARE_OPS: &[&str] = &["eq", "ne", "co", "sw", "ew", "gt", "ge", "lt", "le"];
106
107#[derive(Debug, Clone, PartialEq)]
108enum Tok {
109    Word(String),
110    Str(String),
111    Open,
112    Close,
113    LBracket,
114    RBracket,
115}
116
117fn tokenize(s: &str) -> Result<Vec<Tok>> {
118    let mut out = Vec::new();
119    let b = s.as_bytes();
120    let mut i = 0;
121    while i < b.len() {
122        match b[i] {
123            b' ' | b'\t' | b'\n' | b'\r' => i += 1,
124            b'(' => {
125                out.push(Tok::Open);
126                i += 1
127            }
128            b')' => {
129                out.push(Tok::Close);
130                i += 1
131            }
132            b'[' => {
133                out.push(Tok::LBracket);
134                i += 1
135            }
136            b']' => {
137                out.push(Tok::RBracket);
138                i += 1
139            }
140            b'"' => {
141                let start = i;
142                i += 1;
143                while i < b.len() && b[i] != b'"' {
144                    if b[i] == b'\\' {
145                        i += 1;
146                    }
147                    i += 1;
148                }
149                ensure!(i < b.len(), "unterminated string in filter");
150                let lit: String = serde_json::from_str(&s[start..=i])
151                    .context("invalid string literal in filter")?;
152                out.push(Tok::Str(lit));
153                i += 1;
154            }
155            _ => {
156                let start = i;
157                while i < b.len() && !b" \t\n\r()[]\"".contains(&b[i]) {
158                    i += 1;
159                }
160                out.push(Tok::Word(s[start..i].to_owned()));
161            }
162        }
163        ensure!(out.len() <= 4 * MAX_NODES, "filter has too many tokens");
164    }
165    Ok(out)
166}
167
168struct Parser {
169    toks: Vec<Tok>,
170    pos: usize,
171    nodes: usize,
172}
173
174impl Parser {
175    fn peek(&self) -> Option<&Tok> {
176        self.toks.get(self.pos)
177    }
178    fn keyword(&self, k: &str) -> bool {
179        matches!(self.peek(), Some(Tok::Word(w)) if w.eq_ignore_ascii_case(k))
180    }
181    fn node(&mut self) -> Result<()> {
182        self.nodes += 1;
183        ensure!(self.nodes <= MAX_NODES, "filter has too many expressions");
184        Ok(())
185    }
186    fn or(&mut self, depth: usize, in_value_path: bool) -> Result<Filter> {
187        ensure!(depth <= MAX_DEPTH, "filter nests too deeply");
188        let mut left = self.and(depth, in_value_path)?;
189        while self.keyword("or") {
190            self.pos += 1;
191            self.node()?;
192            let right = self.and(depth, in_value_path)?;
193            left = Filter::Or(Box::new(left), Box::new(right));
194        }
195        Ok(left)
196    }
197    fn and(&mut self, depth: usize, in_value_path: bool) -> Result<Filter> {
198        let mut left = self.unary(depth, in_value_path)?;
199        while self.keyword("and") {
200            self.pos += 1;
201            self.node()?;
202            let right = self.unary(depth, in_value_path)?;
203            left = Filter::And(Box::new(left), Box::new(right));
204        }
205        Ok(left)
206    }
207    fn unary(&mut self, depth: usize, in_value_path: bool) -> Result<Filter> {
208        self.node()?;
209        if self.keyword("not") {
210            self.pos += 1;
211            ensure!(self.peek() == Some(&Tok::Open), "not must be followed by (");
212            self.pos += 1;
213            let inner = self.or(depth + 1, in_value_path)?;
214            ensure!(self.peek() == Some(&Tok::Close), "missing ) after not(");
215            self.pos += 1;
216            return Ok(Filter::Not(Box::new(inner)));
217        }
218        if self.peek() == Some(&Tok::Open) {
219            self.pos += 1;
220            let inner = self.or(depth + 1, in_value_path)?;
221            ensure!(self.peek() == Some(&Tok::Close), "missing )");
222            self.pos += 1;
223            return Ok(inner);
224        }
225        let Some(Tok::Word(w)) = self.peek().cloned() else {
226            bail!("expected an attribute path");
227        };
228        self.pos += 1;
229        let path = AttrPath::parse(&w)?;
230        if self.peek() == Some(&Tok::LBracket) {
231            ensure!(!in_value_path, "a value filter cannot contain another");
232            ensure!(
233                path.sub.is_none(),
234                "a value path names an attribute, not a sub-attribute"
235            );
236            self.pos += 1;
237            let inner = self.or(depth + 1, true)?;
238            ensure!(self.peek() == Some(&Tok::RBracket), "missing ]");
239            self.pos += 1;
240            return Ok(Filter::ValuePath {
241                path,
242                filter: Box::new(inner),
243            });
244        }
245        let Some(Tok::Word(op)) = self.peek().cloned() else {
246            bail!("expected an operator after {w}");
247        };
248        let op = op.to_ascii_lowercase();
249        self.pos += 1;
250        if op == "pr" {
251            return Ok(Filter::Present(path));
252        }
253        ensure!(COMPARE_OPS.contains(&op.as_str()), "unknown operator {op}");
254        let value = match self.peek().cloned() {
255            Some(Tok::Str(s)) => Value::String(s),
256            Some(Tok::Word(v)) => match v.as_str() {
257                "true" => Value::Bool(true),
258                "false" => Value::Bool(false),
259                "null" => Value::Null,
260                n => serde_json::from_str::<serde_json::Number>(n)
261                    .map(Value::Number)
262                    .map_err(|_| anyhow::anyhow!("{n} is not a valid comparison value"))?,
263            },
264            _ => bail!("expected a comparison value"),
265        };
266        self.pos += 1;
267        Ok(Filter::Compare { path, op, value })
268    }
269}
270
271pub fn parse_filter(s: &str) -> Result<Filter> {
272    ensure!(
273        s.len() <= MAX_FILTER_BYTES,
274        "filter over {MAX_FILTER_BYTES} bytes"
275    );
276    let mut p = Parser {
277        toks: tokenize(s)?,
278        pos: 0,
279        nodes: 0,
280    };
281    ensure!(!p.toks.is_empty(), "empty filter");
282    let f = p.or(0, false)?;
283    ensure!(p.pos == p.toks.len(), "unexpected text after the filter");
284    Ok(f)
285}
286
287impl Filter {
288    pub fn to_json(&self) -> Value {
289        match self {
290            Filter::Compare { path, op, value } => {
291                json!({"op": op, "path": path.to_json(), "value": value})
292            }
293            Filter::Present(path) => json!({"op": "pr", "path": path.to_json()}),
294            Filter::And(a, b) => json!({"and": [a.to_json(), b.to_json()]}),
295            Filter::Or(a, b) => json!({"or": [a.to_json(), b.to_json()]}),
296            Filter::Not(f) => json!({"not": f.to_json()}),
297            Filter::ValuePath { path, filter } => {
298                json!({"value_path": path.to_json(), "filter": filter.to_json()})
299            }
300        }
301    }
302}
303
304/// Where paths resolve: a resource of a type, or an element of a multi-valued complex
305/// attribute (inside `attr[...]`), whose sub-attribute definitions are `parent`.
306#[derive(Clone, Copy)]
307enum Scope<'a> {
308    Resource(&'a ResourceType),
309    Element(&'a ResourceType, &'a AttrPath),
310}
311
312fn values<'a>(scope: Scope, path: &AttrPath, obj: &'a Value) -> (Vec<&'a Value>, bool) {
313    let (base, def, inner_sub) = match scope {
314        Scope::Resource(rt) => (
315            path.container(rt, obj),
316            path.definition(rt),
317            path.sub.as_deref(),
318        ),
319        Scope::Element(rt, parent) => (
320            Some(obj),
321            schema::attribute(rt, parent.urn.as_deref(), &parent.attr, Some(&path.attr)),
322            None,
323        ),
324    };
325    let exact = schema::case_exact(def);
326    let Some(base) = base else {
327        return (vec![], exact);
328    };
329    if path.attr.is_empty() {
330        return (vec![base], exact);
331    }
332    let Some(v) = schema::member(base, &path.attr) else {
333        return (vec![], exact);
334    };
335    let mut out = Vec::new();
336    let mut push = |x: &'a Value| match (inner_sub, x) {
337        (Some(s), Value::Object(_)) => {
338            if let Some(y) = schema::member(x, s) {
339                out.push(y)
340            }
341        }
342        (Some(_), _) => {}
343        // A multi-valued complex attribute compared directly means its "value".
344        (None, Value::Object(_)) => {
345            if let Some(y) = schema::member(x, "value") {
346                out.push(y)
347            }
348        }
349        (None, _) => out.push(x),
350    };
351    match v {
352        Value::Array(items) => items.iter().for_each(&mut push),
353        other => push(other),
354    }
355    (out, exact)
356}
357
358fn text(v: &Value, exact: bool) -> Option<String> {
359    v.as_str().map(|s| {
360        if exact {
361            s.to_owned()
362        } else {
363            s.to_lowercase()
364        }
365    })
366}
367
368fn compare(op: &str, actual: &Value, expected: &Value, exact: bool) -> bool {
369    if let (Some(a), Some(e)) = (text(actual, exact), text(expected, exact)) {
370        return match op {
371            "eq" => a == e,
372            "ne" => a != e,
373            "co" => a.contains(&e),
374            "sw" => a.starts_with(&e),
375            "ew" => a.ends_with(&e),
376            "gt" => a > e,
377            "ge" => a >= e,
378            "lt" => a < e,
379            "le" => a <= e,
380            _ => false,
381        };
382    }
383    if let (Some(a), Some(e)) = (actual.as_f64(), expected.as_f64()) {
384        return match op {
385            "eq" => a == e,
386            "ne" => a != e,
387            "gt" => a > e,
388            "ge" => a >= e,
389            "lt" => a < e,
390            "le" => a <= e,
391            _ => false,
392        };
393    }
394    match op {
395        "eq" => actual == expected,
396        "ne" => actual != expected,
397        _ => false,
398    }
399}
400
401fn present(v: &Value) -> bool {
402    match v {
403        Value::Null => false,
404        Value::String(s) => !s.is_empty(),
405        Value::Array(a) => !a.is_empty(),
406        Value::Object(o) => !o.is_empty(),
407        _ => true,
408    }
409}
410
411fn eval_in(f: &Filter, scope: Scope, obj: &Value) -> bool {
412    match f {
413        Filter::And(a, b) => eval_in(a, scope, obj) && eval_in(b, scope, obj),
414        Filter::Or(a, b) => eval_in(a, scope, obj) || eval_in(b, scope, obj),
415        Filter::Not(x) => !eval_in(x, scope, obj),
416        Filter::Present(path) => values(scope, path, obj).0.into_iter().any(present),
417        Filter::Compare { path, op, value } => {
418            let (vals, exact) = values(scope, path, obj);
419            if vals.is_empty() {
420                return op == "ne" && !value.is_null() || (op == "eq" && value.is_null());
421            }
422            vals.into_iter().any(|v| compare(op, v, value, exact))
423        }
424        Filter::ValuePath { path, filter } => {
425            let Scope::Resource(rt) = scope else {
426                return false;
427            };
428            let Some(attr) = path
429                .container(rt, obj)
430                .and_then(|c| schema::member(c, &path.attr))
431            else {
432                return false;
433            };
434            let elements: Vec<&Value> = match attr {
435                Value::Array(a) => a.iter().collect(),
436                other => vec![other],
437            };
438            elements
439                .into_iter()
440                .any(|e| eval_in(filter, Scope::Element(rt, path), e))
441        }
442    }
443}
444
445pub fn matches(f: &Filter, rt: &ResourceType, resource: &Value) -> bool {
446    eval_in(f, Scope::Resource(rt), resource)
447}
448
449/// A PATCH path (RFC 7644 §3.5.2): an attribute path, or `attr[filter]` optionally followed
450/// by `.sub`.
451#[derive(Debug, Clone, PartialEq)]
452pub struct PatchPath {
453    pub path: AttrPath,
454    pub filter: Option<Filter>,
455    pub sub_after_filter: Option<String>,
456}
457
458impl PatchPath {
459    pub fn parse(s: &str) -> Result<Self> {
460        ensure!(
461            s.len() <= MAX_FILTER_BYTES,
462            "path over {MAX_FILTER_BYTES} bytes"
463        );
464        match s.find('[') {
465            None => Ok(Self {
466                path: AttrPath::parse(s)?,
467                filter: None,
468                sub_after_filter: None,
469            }),
470            Some(i) => {
471                let close = s.rfind(']').context("missing ] in path")?;
472                ensure!(close > i, "malformed value path");
473                let path = AttrPath::parse(&s[..i])?;
474                ensure!(
475                    path.sub.is_none(),
476                    "a value path names an attribute, not a sub-attribute"
477                );
478                let mut p = Parser {
479                    toks: tokenize(&s[i + 1..close])?,
480                    pos: 0,
481                    nodes: 0,
482                };
483                let filter = p.or(0, true)?;
484                ensure!(p.pos == p.toks.len(), "unexpected text in the value filter");
485                let rest = &s[close + 1..];
486                let sub = match rest.strip_prefix('.') {
487                    Some(sub) => {
488                        ensure!(name_ok(sub), "invalid sub-attribute after the value filter");
489                        Some(sub.to_owned())
490                    }
491                    None => {
492                        ensure!(rest.is_empty(), "unexpected text after the value filter");
493                        None
494                    }
495                };
496                Ok(Self {
497                    path,
498                    filter: Some(filter),
499                    sub_after_filter: sub,
500                })
501            }
502        }
503    }
504
505    pub fn to_json(&self) -> Value {
506        json!({"path": self.path.to_json(), "filter": self.filter.as_ref().map(Filter::to_json), "sub_attribute_after_filter": self.sub_after_filter})
507    }
508}
509
510/// Sort by `path` (first value of a multi-valued attribute; absent values last).
511pub fn sort(resources: &mut [Value], rt: &ResourceType, path: &AttrPath, descending: bool) {
512    let key = |r: &Value| -> Option<Value> {
513        let (vals, exact) = values(Scope::Resource(rt), path, r);
514        vals.into_iter().next().map(|v| match text(v, exact) {
515            Some(t) => Value::String(t),
516            None => v.clone(),
517        })
518    };
519    resources.sort_by(|a, b| {
520        let (ka, kb) = (key(a), key(b));
521        let ord = match (&ka, &kb) {
522            (None, None) => Ordering::Equal,
523            (None, _) => return Ordering::Greater,
524            (_, None) => return Ordering::Less,
525            (Some(x), Some(y)) => match (x, y) {
526                (Value::String(p), Value::String(q)) => p.cmp(q),
527                _ => x
528                    .as_f64()
529                    .partial_cmp(&y.as_f64())
530                    .unwrap_or(Ordering::Equal),
531            },
532        };
533        if descending {
534            ord.reverse()
535        } else {
536            ord
537        }
538    });
539}
540
541/// RFC 7644 §3.9: keep `always` attributes, drop `never` ones, then honour `attributes`
542/// (only these plus the always set) or `excludedAttributes`.
543pub fn project(
544    resource: &Value,
545    rt: &ResourceType,
546    attributes: &[AttrPath],
547    excluded: &[AttrPath],
548) -> Value {
549    let Value::Object(src) = resource else {
550        return resource.clone();
551    };
552    let mut out = src.clone();
553    for (urn, name) in schema::names_returned(rt, "never") {
554        remove(
555            &mut out,
556            rt,
557            &AttrPath {
558                urn: urn.map(str::to_owned),
559                attr: name,
560                sub: None,
561            },
562        );
563    }
564    let always: Vec<AttrPath> = schema::names_returned(rt, "always")
565        .into_iter()
566        .map(|(urn, name)| AttrPath {
567            urn: urn.map(str::to_owned),
568            attr: name,
569            sub: None,
570        })
571        .collect();
572    if !attributes.is_empty() {
573        let mut kept = Map::new();
574        for p in always.iter().chain(attributes) {
575            copy(&out, &mut kept, rt, p);
576        }
577        return Value::Object(kept);
578    }
579    for p in excluded {
580        if !always.iter().any(|a| {
581            a.attr.eq_ignore_ascii_case(&p.attr)
582                && p.sub.is_none()
583                && a.urn.is_none() == p.urn.is_none()
584        }) {
585            remove(&mut out, rt, p);
586        }
587    }
588    Value::Object(out)
589}
590
591fn is_extension(rt: &ResourceType, p: &AttrPath) -> Option<String> {
592    p.urn
593        .as_ref()
594        .filter(|u| !u.eq_ignore_ascii_case(rt.schema))
595        .cloned()
596}
597
598fn copy(src: &Map<String, Value>, dst: &mut Map<String, Value>, rt: &ResourceType, p: &AttrPath) {
599    let src_v = Value::Object(src.clone());
600    if let Some(ext) = is_extension(rt, p) {
601        let Some(key) = schema::member_key(&src_v, &ext) else {
602            return;
603        };
604        if p.attr.is_empty() {
605            dst.insert(key.clone(), src[&key].clone());
606            return;
607        }
608        let inner_src = src[&key].as_object().cloned().unwrap_or_default();
609        let entry = dst.entry(key).or_insert_with(|| json!({}));
610        if let Value::Object(inner_dst) = entry {
611            copy(
612                &inner_src,
613                inner_dst,
614                rt,
615                &AttrPath {
616                    urn: None,
617                    attr: p.attr.clone(),
618                    sub: p.sub.clone(),
619                },
620            );
621        }
622        return;
623    }
624    let Some(key) = schema::member_key(&src_v, &p.attr) else {
625        return;
626    };
627    let value = &src[&key];
628    match &p.sub {
629        None => {
630            dst.insert(key, value.clone());
631        }
632        Some(sub) => {
633            let pick = |o: &Value| -> Option<Value> {
634                let k = schema::member_key(o, sub)?;
635                let mut m = Map::new();
636                m.insert(k.clone(), o[&k].clone());
637                Some(Value::Object(m))
638            };
639            let picked = match value {
640                Value::Array(items) => Value::Array(items.iter().filter_map(pick).collect()),
641                Value::Object(_) => pick(value).unwrap_or_else(|| json!({})),
642                _ => return,
643            };
644            match (dst.get_mut(&key), picked) {
645                (Some(Value::Object(existing)), Value::Object(more)) => existing.extend(more),
646                (_, picked) => {
647                    dst.insert(key, picked);
648                }
649            }
650        }
651    }
652}
653
654fn remove(obj: &mut Map<String, Value>, rt: &ResourceType, p: &AttrPath) {
655    if let Some(ext) = is_extension(rt, p) {
656        let key = schema::member_key(&Value::Object(obj.clone()), &ext);
657        if p.attr.is_empty() {
658            if let Some(k) = key {
659                obj.remove(&k);
660            }
661            return;
662        }
663        if let Some(Value::Object(inner)) = key.and_then(|k| obj.get_mut(&k)) {
664            remove(
665                inner,
666                rt,
667                &AttrPath {
668                    urn: None,
669                    attr: p.attr.clone(),
670                    sub: p.sub.clone(),
671                },
672            );
673        }
674        return;
675    }
676    let Some(key) = schema::member_key(&Value::Object(obj.clone()), &p.attr) else {
677        return;
678    };
679    match &p.sub {
680        None => {
681            obj.remove(&key);
682        }
683        Some(sub) => {
684            let strip = |o: &mut Value| {
685                if let Some(k) = schema::member_key(o, sub) {
686                    o.as_object_mut().map(|m| m.remove(&k));
687                }
688            };
689            match obj.get_mut(&key) {
690                Some(Value::Array(items)) => items.iter_mut().for_each(strip),
691                Some(v @ Value::Object(_)) => strip(v),
692                _ => {}
693            }
694        }
695    }
696}
697
698pub fn parse_list(s: Option<&str>) -> Result<Vec<AttrPath>> {
699    match s.filter(|s| !s.trim().is_empty()) {
700        None => Ok(vec![]),
701        Some(s) => {
702            let parts: Vec<&str> = s.split(',').map(str::trim).collect();
703            ensure!(parts.len() <= 64, "at most 64 attribute names");
704            parts.into_iter().map(AttrPath::parse).collect()
705        }
706    }
707}
netget/server/scim/query.rs

netget/server/scim/
query.rs
