Skip to main content

jmap_scene_server/
query.rs

1//! `/query` filter evaluation and ordering for `SceneAsset`, `SceneRegion`,
2//! `SceneObject` and `SceneAvatar` (draft-atwood-jmap-scene-00
3//! §`SceneAsset/query`, §`SceneRegion/query`, §`SceneObject/query`,
4//! §`SceneAvatar/query`).
5//!
6//! Pure functions a backend's `query_objects` can apply to its stored
7//! objects; the reference `MemoryBackend` uses them.
8
9use std::cmp::Ordering;
10
11use jmap_scene_types::{
12    Filter, Operator, SceneAssetComparator, SceneAssetFilter, SceneAssetSortProperty,
13    SceneAvatarComparator, SceneAvatarFilter, SceneAvatarSortProperty, SceneObjectComparator,
14    SceneObjectFilter, SceneObjectSortProperty, SceneRegionComparator, SceneRegionFilter,
15    SceneRegionSortProperty, WithinBounds, WithinRadius,
16};
17use jmap_scene_types::{Position, SceneAsset, SceneAvatar, SceneObject, SceneRegion};
18use jmap_types::Id;
19
20use crate::helpers::utc_key;
21
22/// RFC 8620 §5.5 filter algebra over `condition`. A filter operator this
23/// version does not know matches nothing.
24fn filter_matches<C>(filter: &Filter<C>, condition: &impl Fn(&C) -> bool) -> bool {
25    match filter {
26        Filter::Condition(cond) => condition(cond),
27        Filter::Operator(op) => {
28            let mut each = op.conditions.iter().map(|f| filter_matches(f, condition));
29            match op.operator {
30                Operator::And => each.all(|m| m),
31                Operator::Or => each.any(|m| m),
32                Operator::Not => !each.any(|m| m),
33                _ => false,
34            }
35        }
36        _ => false,
37    }
38}
39
40/// Case-insensitive substring match of `query` in `name`.
41fn name_contains(name: &str, query: &str) -> bool {
42    name.to_lowercase().contains(&query.to_lowercase())
43}
44
45/// `true` if `asset` matches `filter` (§`SceneAsset/query`): "All filter
46/// properties are combined with logical AND."
47///
48/// `mediaType` is an exact match, ignoring ASCII case (media type names
49/// are case-insensitive, RFC 6838 §4.2). `name` is a "Substring match on
50/// asset name", ignoring case as the draft's example does: the filter
51/// `"sculpture"` selects the asset named `"Sculpture: Convergence"`. An
52/// asset with a `null` name matches no `name` filter. `createdAfter` is
53/// inclusive ("at or after"), `createdBefore` exclusive ("before").
54pub fn asset_matches(filter: &SceneAssetFilter, asset: &SceneAsset) -> bool {
55    let created = utc_key(&asset.created_at);
56    filter_matches(filter, &|c| {
57        c.media_type
58            .as_ref()
59            .is_none_or(|t| t.eq_ignore_ascii_case(&asset.media_type))
60            && c.name
61                .as_ref()
62                .is_none_or(|q| asset.name.as_ref().is_some_and(|n| name_contains(n, q)))
63            && c.created_after
64                .as_ref()
65                .is_none_or(|b| created >= utc_key(b))
66            && c.created_before
67                .as_ref()
68                .is_none_or(|b| created < utc_key(b))
69    })
70}
71
72/// Order two assets by `sort` ("Sort properties: `createdAt`, `name`,
73/// `size`"; RFC 8620 §5.5: later comparators break ties of earlier ones),
74/// then by `id` so the order is total.
75///
76/// ponytail: `name` compares by Unicode code point and ignores the
77/// comparator's `collation`; the draft does not say where a `null` name
78/// sorts, so assets without one go last in either direction.
79pub fn compare_assets(a: &SceneAsset, b: &SceneAsset, sort: &[SceneAssetComparator]) -> Ordering {
80    sort.iter()
81        .map(|c| {
82            let directed = |ord: Ordering| if c.is_ascending { ord } else { ord.reverse() };
83            match c.property {
84                SceneAssetSortProperty::CreatedAt => {
85                    directed(utc_key(&a.created_at).cmp(utc_key(&b.created_at)))
86                }
87                SceneAssetSortProperty::Size => directed(a.size.cmp(&b.size)),
88                SceneAssetSortProperty::Name => match (&a.name, &b.name) {
89                    (Some(x), Some(y)) => directed(x.cmp(y)),
90                    (Some(_), None) => Ordering::Less,
91                    (None, Some(_)) => Ordering::Greater,
92                    (None, None) => Ordering::Equal,
93                },
94                _ => Ordering::Equal,
95            }
96        })
97        .find(|o| o.is_ne())
98        .unwrap_or_else(|| a.id.as_ref().cmp(b.id.as_ref()))
99}
100
101/// `true` if `region` matches `filter` (§`SceneRegion/query`): "All filter
102/// properties are combined with logical AND."
103///
104/// `name` is a "Substring match on region name", ignoring case as
105/// [`asset_matches`] does. `accessPolicy` and `viewHint` are exact
106/// matches; a region whose `viewHint` is `null` matches no `viewHint`
107/// filter. `hasSimulationUri` tests `simulationUri` for non-null,
108/// `hasActiveAvatars` tests "`activeAvatarCount > 0`". `createdAfter` is
109/// inclusive ("at or after"), `createdBefore` exclusive ("before").
110/// `worldStateEquals` compares top-level `worldState` keys with String,
111/// Number (by numeric value) and Boolean values.
112pub fn region_matches(filter: &SceneRegionFilter, region: &SceneRegion) -> bool {
113    let created = utc_key(&region.created_at);
114    filter_matches(filter, &|c| {
115        c.name
116            .as_ref()
117            .is_none_or(|q| name_contains(&region.name, q))
118            && c.access_policy
119                .as_ref()
120                .is_none_or(|p| *p == region.access_policy)
121            && c.view_hint
122                .as_ref()
123                .is_none_or(|h| region.view_hint.as_ref() == Some(h))
124            && c.has_simulation_uri
125                .is_none_or(|want| region.simulation_uri.is_some() == want)
126            && c.has_active_avatars
127                .is_none_or(|want| (region.active_avatar_count > 0) == want)
128            && c.created_after
129                .as_ref()
130                .is_none_or(|b| created >= utc_key(b))
131            && c.created_before
132                .as_ref()
133                .is_none_or(|b| created < utc_key(b))
134            && c.world_state_equals.as_ref().is_none_or(|want| {
135                world_state_equals(want, region.world_state.as_ref().and_then(Option::as_ref))
136            })
137    })
138}
139
140/// `worldStateEquals` (jmap-chat-spec 93f2258 §`SceneRegion/query`): `true`
141/// when `world_state` has every key of `want` "with an equal value: the
142/// same JSON type, and for Strings the same sequence of characters, for
143/// Numbers the same numeric value". An empty `want` matches every region,
144/// a `null` or absent `worldState` included.
145///
146/// Numbers compare exactly when both are integers, so `1` equals `1.0`
147/// and large integers are not rounded through `f64`. A `want` value that
148/// is not a String, Number or Boolean matches nothing; the handler has
149/// already refused it with `invalidArguments`.
150fn world_state_equals(
151    want: &serde_json::Map<String, serde_json::Value>,
152    world_state: Option<&serde_json::Map<String, serde_json::Value>>,
153) -> bool {
154    use serde_json::Value;
155    want.iter().all(|(key, w)| {
156        let Some(have) = world_state.and_then(|m| m.get(key)) else {
157            return false;
158        };
159        match (w, have) {
160            (Value::String(a), Value::String(b)) => a == b,
161            (Value::Bool(a), Value::Bool(b)) => a == b,
162            (Value::Number(a), Value::Number(b)) => match (a.as_i64(), b.as_i64()) {
163                (Some(x), Some(y)) => x == y,
164                _ => match (a.as_u64(), b.as_u64()) {
165                    (Some(x), Some(y)) => x == y,
166                    _ => a.as_f64().zip(b.as_f64()).is_some_and(|(x, y)| x == y),
167                },
168            },
169            _ => false,
170        }
171    })
172}
173
174/// Order two regions by `sort` ("Sort properties: `createdAt`, `name`,
175/// `activeAvatarCount`"; RFC 8620 §5.5: later comparators break ties of
176/// earlier ones), then by `id` so the order is total.
177///
178/// ponytail: `name` compares by Unicode code point and ignores the
179/// comparator's `collation`, as [`compare_assets`] does.
180pub fn compare_regions(
181    a: &SceneRegion,
182    b: &SceneRegion,
183    sort: &[SceneRegionComparator],
184) -> Ordering {
185    sort.iter()
186        .map(|c| {
187            let ord = match c.property {
188                SceneRegionSortProperty::CreatedAt => {
189                    utc_key(&a.created_at).cmp(utc_key(&b.created_at))
190                }
191                SceneRegionSortProperty::Name => a.name.cmp(&b.name),
192                SceneRegionSortProperty::ActiveAvatarCount => {
193                    a.active_avatar_count.cmp(&b.active_avatar_count)
194                }
195                _ => Ordering::Equal,
196            };
197            if c.is_ascending { ord } else { ord.reverse() }
198        })
199        .find(|o| o.is_ne())
200        .unwrap_or_else(|| a.id.as_ref().cmp(b.id.as_ref()))
201}
202
203/// The position of `object` in region-local coordinates.
204///
205/// "When non-null, `position`, `orientation`, and `scale` are relative to
206/// the parent's transform", while the spatial filters take region-local
207/// points. Each ancestor maps the point into its own parent's frame as
208/// `t + R(q) (s * p)` (glTF 2.0 TRS order: scale, then rotate, then
209/// translate). `parent_of` looks an ancestor up by id; the walk stops at a
210/// root, at an ancestor `parent_of` does not know, and at an id it has
211/// already visited, so a corrupt cycle cannot loop.
212pub fn region_local_position<'a>(
213    object: &'a SceneObject,
214    parent_of: impl Fn(&Id) -> Option<&'a SceneObject>,
215) -> Position {
216    let mut p = object.position;
217    let mut visited: Vec<&Id> = vec![&object.id];
218    let mut next = object.parent_id.as_ref();
219    while let Some(parent) = next.filter(|id| !visited.contains(id)).and_then(&parent_of) {
220        let scaled = [
221            p[0] * parent.scale[0],
222            p[1] * parent.scale[1],
223            p[2] * parent.scale[2],
224        ];
225        let r = rotate(parent.orientation, scaled);
226        p = [
227            parent.position[0] + r[0],
228            parent.position[1] + r[1],
229            parent.position[2] + r[2],
230        ];
231        visited.push(&parent.id);
232        next = parent.parent_id.as_ref();
233    }
234    p
235}
236
237/// Rotate `v` by the unit quaternion `[x, y, z, w]`:
238/// `v + 2w (u x v) + 2 u x (u x v)` with `u = [x, y, z]`.
239fn rotate(q: [f64; 4], v: Position) -> Position {
240    let cross = |a: Position, b: Position| {
241        [
242            a[1] * b[2] - a[2] * b[1],
243            a[2] * b[0] - a[0] * b[2],
244            a[0] * b[1] - a[1] * b[0],
245        ]
246    };
247    let u = [q[0], q[1], q[2]];
248    let uv = cross(u, v);
249    let uuv = cross(u, uv);
250    [
251        v[0] + 2.0 * (q[3] * uv[0] + uuv[0]),
252        v[1] + 2.0 * (q[3] * uv[1] + uuv[1]),
253        v[2] + 2.0 * (q[3] * uv[2] + uuv[2]),
254    ]
255}
256
257/// `true` if `object`, whose region-local position is `position` (see
258/// [`region_local_position`]), matches `filter` (§`SceneObject/query`):
259/// "All filter properties are combined with logical AND."
260///
261/// `name` is a case-insensitive substring match, as [`asset_matches`]
262/// does; an object with a `null` name matches no `name` filter.
263/// `visualType` is an exact match ignoring ASCII case (RFC 6838 §4.2).
264/// `parentId` `null` "returns only root-level objects". `withinRadius`
265/// and `withinBounds` include their boundary.
266pub fn object_matches(
267    filter: &SceneObjectFilter,
268    object: &SceneObject,
269    position: Position,
270) -> bool {
271    filter_matches(filter, &|c| {
272        c.region_id.as_ref().is_none_or(|r| *r == object.region_id)
273            && c.name
274                .as_ref()
275                .is_none_or(|q| object.name.as_ref().is_some_and(|n| name_contains(n, q)))
276            && c.visual_type.as_ref().is_none_or(|t| {
277                object
278                    .visual_type
279                    .as_ref()
280                    .is_some_and(|v| v.eq_ignore_ascii_case(t))
281            })
282            && c.owner_id
283                .as_ref()
284                .is_none_or(|o| object.owner_id.as_ref() == Some(o))
285            && c.interactable
286                .is_none_or(|want| object.interactable == want)
287            && c.visible.is_none_or(|want| object.visible == want)
288            && c.physics_mode
289                .as_ref()
290                .is_none_or(|m| *m == object.physics_mode)
291            && c.parent_id
292                .as_ref()
293                .is_none_or(|want| object.parent_id.as_ref() == want.as_ref())
294            && c.within_radius
295                .as_ref()
296                .is_none_or(|w| in_radius(w, position))
297            && c.within_bounds
298                .as_ref()
299                .is_none_or(|b| in_bounds(b, position))
300    })
301}
302
303/// `withinRadius`, boundary included.
304fn in_radius(w: &WithinRadius, p: Position) -> bool {
305    let d2: f64 = (0..3).map(|i| (p[i] - w.center[i]).powi(2)).sum();
306    d2 <= w.radius * w.radius
307}
308
309/// `withinBounds`, boundary included.
310fn in_bounds(b: &WithinBounds, p: Position) -> bool {
311    (0..3).all(|i| b.min[i] <= p[i] && p[i] <= b.max[i])
312}
313
314/// `true` if `avatar` matches `filter` (§`SceneAvatar/query`): "All filter
315/// properties are combined with logical AND."
316///
317/// `isActive` `true` selects "avatars with `leftAt == null`", `false`
318/// "avatars who have left". `withinRadius` and `withinBounds` test the
319/// avatar's "last known position", boundary included; an avatar has no
320/// parent, so its position is region-local.
321pub fn avatar_matches(filter: &SceneAvatarFilter, avatar: &SceneAvatar) -> bool {
322    filter_matches(filter, &|c| {
323        c.region_id.as_ref().is_none_or(|r| *r == avatar.region_id)
324            && c.user_id.as_ref().is_none_or(|u| *u == avatar.user_id)
325            && c.is_active
326                .is_none_or(|want| avatar.left_at.is_none() == want)
327            && c.within_radius
328                .as_ref()
329                .is_none_or(|w| in_radius(w, avatar.position))
330            && c.within_bounds
331                .as_ref()
332                .is_none_or(|b| in_bounds(b, avatar.position))
333    })
334}
335
336/// Order two avatars by `sort` ("Sort properties: `joinedAt`,
337/// `displayName`"; RFC 8620 §5.5: later comparators break ties of earlier
338/// ones), then by `id` so the order is total.
339///
340/// ponytail: `displayName` compares by Unicode code point and ignores the
341/// comparator's `collation`, as [`compare_assets`] does.
342pub fn compare_avatars(
343    a: &SceneAvatar,
344    b: &SceneAvatar,
345    sort: &[SceneAvatarComparator],
346) -> Ordering {
347    sort.iter()
348        .map(|c| {
349            let ord = match c.property {
350                SceneAvatarSortProperty::JoinedAt => {
351                    utc_key(&a.joined_at).cmp(utc_key(&b.joined_at))
352                }
353                SceneAvatarSortProperty::DisplayName => a.display_name.cmp(&b.display_name),
354                _ => Ordering::Equal,
355            };
356            if c.is_ascending { ord } else { ord.reverse() }
357        })
358        .find(|o| o.is_ne())
359        .unwrap_or_else(|| a.id.as_ref().cmp(b.id.as_ref()))
360}
361
362/// Order two objects by `sort` ("Sort properties: `createdAt`, `name`";
363/// RFC 8620 §5.5: later comparators break ties of earlier ones), then by
364/// `id` so the order is total.
365///
366/// ponytail: `name` compares by Unicode code point and ignores the
367/// comparator's `collation`; objects without a name go last in either
368/// direction, as [`compare_assets`] does.
369pub fn compare_objects(
370    a: &SceneObject,
371    b: &SceneObject,
372    sort: &[SceneObjectComparator],
373) -> Ordering {
374    sort.iter()
375        .map(|c| {
376            let directed = |ord: Ordering| if c.is_ascending { ord } else { ord.reverse() };
377            match c.property {
378                SceneObjectSortProperty::CreatedAt => {
379                    directed(utc_key(&a.created_at).cmp(utc_key(&b.created_at)))
380                }
381                SceneObjectSortProperty::Name => match (&a.name, &b.name) {
382                    (Some(x), Some(y)) => directed(x.cmp(y)),
383                    (Some(_), None) => Ordering::Less,
384                    (None, Some(_)) => Ordering::Greater,
385                    (None, None) => Ordering::Equal,
386                },
387                _ => Ordering::Equal,
388            }
389        })
390        .find(|o| o.is_ne())
391        .unwrap_or_else(|| a.id.as_ref().cmp(b.id.as_ref()))
392}