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").
110pub fn region_matches(filter: &SceneRegionFilter, region: &SceneRegion) -> bool {
111    let created = utc_key(&region.created_at);
112    filter_matches(filter, &|c| {
113        c.name
114            .as_ref()
115            .is_none_or(|q| name_contains(&region.name, q))
116            && c.access_policy
117                .as_ref()
118                .is_none_or(|p| *p == region.access_policy)
119            && c.view_hint
120                .as_ref()
121                .is_none_or(|h| region.view_hint.as_ref() == Some(h))
122            && c.has_simulation_uri
123                .is_none_or(|want| region.simulation_uri.is_some() == want)
124            && c.has_active_avatars
125                .is_none_or(|want| (region.active_avatar_count > 0) == want)
126            && c.created_after
127                .as_ref()
128                .is_none_or(|b| created >= utc_key(b))
129            && c.created_before
130                .as_ref()
131                .is_none_or(|b| created < utc_key(b))
132    })
133}
134
135/// Order two regions by `sort` ("Sort properties: `createdAt`, `name`,
136/// `activeAvatarCount`"; RFC 8620 §5.5: later comparators break ties of
137/// earlier ones), then by `id` so the order is total.
138///
139/// ponytail: `name` compares by Unicode code point and ignores the
140/// comparator's `collation`, as [`compare_assets`] does.
141pub fn compare_regions(
142    a: &SceneRegion,
143    b: &SceneRegion,
144    sort: &[SceneRegionComparator],
145) -> Ordering {
146    sort.iter()
147        .map(|c| {
148            let ord = match c.property {
149                SceneRegionSortProperty::CreatedAt => {
150                    utc_key(&a.created_at).cmp(utc_key(&b.created_at))
151                }
152                SceneRegionSortProperty::Name => a.name.cmp(&b.name),
153                SceneRegionSortProperty::ActiveAvatarCount => {
154                    a.active_avatar_count.cmp(&b.active_avatar_count)
155                }
156                _ => Ordering::Equal,
157            };
158            if c.is_ascending { ord } else { ord.reverse() }
159        })
160        .find(|o| o.is_ne())
161        .unwrap_or_else(|| a.id.as_ref().cmp(b.id.as_ref()))
162}
163
164/// The position of `object` in region-local coordinates.
165///
166/// "When non-null, `position`, `orientation`, and `scale` are relative to
167/// the parent's transform", while the spatial filters take region-local
168/// points. Each ancestor maps the point into its own parent's frame as
169/// `t + R(q) (s * p)` (glTF 2.0 TRS order: scale, then rotate, then
170/// translate). `parent_of` looks an ancestor up by id; the walk stops at a
171/// root, at an ancestor `parent_of` does not know, and at an id it has
172/// already visited, so a corrupt cycle cannot loop.
173pub fn region_local_position<'a>(
174    object: &'a SceneObject,
175    parent_of: impl Fn(&Id) -> Option<&'a SceneObject>,
176) -> Position {
177    let mut p = object.position;
178    let mut visited: Vec<&Id> = vec![&object.id];
179    let mut next = object.parent_id.as_ref();
180    while let Some(parent) = next.filter(|id| !visited.contains(id)).and_then(&parent_of) {
181        let scaled = [
182            p[0] * parent.scale[0],
183            p[1] * parent.scale[1],
184            p[2] * parent.scale[2],
185        ];
186        let r = rotate(parent.orientation, scaled);
187        p = [
188            parent.position[0] + r[0],
189            parent.position[1] + r[1],
190            parent.position[2] + r[2],
191        ];
192        visited.push(&parent.id);
193        next = parent.parent_id.as_ref();
194    }
195    p
196}
197
198/// Rotate `v` by the unit quaternion `[x, y, z, w]`:
199/// `v + 2w (u x v) + 2 u x (u x v)` with `u = [x, y, z]`.
200fn rotate(q: [f64; 4], v: Position) -> Position {
201    let cross = |a: Position, b: Position| {
202        [
203            a[1] * b[2] - a[2] * b[1],
204            a[2] * b[0] - a[0] * b[2],
205            a[0] * b[1] - a[1] * b[0],
206        ]
207    };
208    let u = [q[0], q[1], q[2]];
209    let uv = cross(u, v);
210    let uuv = cross(u, uv);
211    [
212        v[0] + 2.0 * (q[3] * uv[0] + uuv[0]),
213        v[1] + 2.0 * (q[3] * uv[1] + uuv[1]),
214        v[2] + 2.0 * (q[3] * uv[2] + uuv[2]),
215    ]
216}
217
218/// `true` if `object`, whose region-local position is `position` (see
219/// [`region_local_position`]), matches `filter` (§SceneObject/query):
220/// "All filter properties are combined with logical AND."
221///
222/// `name` is a case-insensitive substring match, as [`asset_matches`]
223/// does; an object with a `null` name matches no `name` filter.
224/// `visualType` is an exact match ignoring ASCII case (RFC 6838 §4.2).
225/// `parentId` `null` "returns only root-level objects". `withinRadius`
226/// and `withinBounds` include their boundary.
227pub fn object_matches(
228    filter: &SceneObjectFilter,
229    object: &SceneObject,
230    position: Position,
231) -> bool {
232    filter_matches(filter, &|c| {
233        c.region_id.as_ref().is_none_or(|r| *r == object.region_id)
234            && c.name
235                .as_ref()
236                .is_none_or(|q| object.name.as_ref().is_some_and(|n| name_contains(n, q)))
237            && c.visual_type.as_ref().is_none_or(|t| {
238                object
239                    .visual_type
240                    .as_ref()
241                    .is_some_and(|v| v.eq_ignore_ascii_case(t))
242            })
243            && c.owner_id
244                .as_ref()
245                .is_none_or(|o| object.owner_id.as_ref() == Some(o))
246            && c.interactable
247                .is_none_or(|want| object.interactable == want)
248            && c.visible.is_none_or(|want| object.visible == want)
249            && c.physics_mode
250                .as_ref()
251                .is_none_or(|m| *m == object.physics_mode)
252            && c.parent_id
253                .as_ref()
254                .is_none_or(|want| object.parent_id.as_ref() == want.as_ref())
255            && c.within_radius
256                .as_ref()
257                .is_none_or(|w| in_radius(w, position))
258            && c.within_bounds
259                .as_ref()
260                .is_none_or(|b| in_bounds(b, position))
261    })
262}
263
264/// `withinRadius`, boundary included.
265fn in_radius(w: &WithinRadius, p: Position) -> bool {
266    let d2: f64 = (0..3).map(|i| (p[i] - w.center[i]).powi(2)).sum();
267    d2 <= w.radius * w.radius
268}
269
270/// `withinBounds`, boundary included.
271fn in_bounds(b: &WithinBounds, p: Position) -> bool {
272    (0..3).all(|i| b.min[i] <= p[i] && p[i] <= b.max[i])
273}
274
275/// `true` if `avatar` matches `filter` (§SceneAvatar/query): "All filter
276/// properties are combined with logical AND."
277///
278/// `isActive` `true` selects "avatars with `leftAt == null`", `false`
279/// "avatars who have left". `withinRadius` and `withinBounds` test the
280/// avatar's "last known position", boundary included; an avatar has no
281/// parent, so its position is region-local.
282pub fn avatar_matches(filter: &SceneAvatarFilter, avatar: &SceneAvatar) -> bool {
283    filter_matches(filter, &|c| {
284        c.region_id.as_ref().is_none_or(|r| *r == avatar.region_id)
285            && c.user_id.as_ref().is_none_or(|u| *u == avatar.user_id)
286            && c.is_active
287                .is_none_or(|want| avatar.left_at.is_none() == want)
288            && c.within_radius
289                .as_ref()
290                .is_none_or(|w| in_radius(w, avatar.position))
291            && c.within_bounds
292                .as_ref()
293                .is_none_or(|b| in_bounds(b, avatar.position))
294    })
295}
296
297/// Order two avatars by `sort` ("Sort properties: `joinedAt`,
298/// `displayName`"; RFC 8620 §5.5: later comparators break ties of earlier
299/// ones), then by `id` so the order is total.
300///
301/// ponytail: `displayName` compares by Unicode code point and ignores the
302/// comparator's `collation`, as [`compare_assets`] does.
303pub fn compare_avatars(
304    a: &SceneAvatar,
305    b: &SceneAvatar,
306    sort: &[SceneAvatarComparator],
307) -> Ordering {
308    sort.iter()
309        .map(|c| {
310            let ord = match c.property {
311                SceneAvatarSortProperty::JoinedAt => {
312                    utc_key(&a.joined_at).cmp(utc_key(&b.joined_at))
313                }
314                SceneAvatarSortProperty::DisplayName => a.display_name.cmp(&b.display_name),
315                _ => Ordering::Equal,
316            };
317            if c.is_ascending { ord } else { ord.reverse() }
318        })
319        .find(|o| o.is_ne())
320        .unwrap_or_else(|| a.id.as_ref().cmp(b.id.as_ref()))
321}
322
323/// Order two objects by `sort` ("Sort properties: `createdAt`, `name`";
324/// RFC 8620 §5.5: later comparators break ties of earlier ones), then by
325/// `id` so the order is total.
326///
327/// ponytail: `name` compares by Unicode code point and ignores the
328/// comparator's `collation`; objects without a name go last in either
329/// direction, as [`compare_assets`] does.
330pub fn compare_objects(
331    a: &SceneObject,
332    b: &SceneObject,
333    sort: &[SceneObjectComparator],
334) -> Ordering {
335    sort.iter()
336        .map(|c| {
337            let directed = |ord: Ordering| if c.is_ascending { ord } else { ord.reverse() };
338            match c.property {
339                SceneObjectSortProperty::CreatedAt => {
340                    directed(utc_key(&a.created_at).cmp(utc_key(&b.created_at)))
341                }
342                SceneObjectSortProperty::Name => match (&a.name, &b.name) {
343                    (Some(x), Some(y)) => directed(x.cmp(y)),
344                    (Some(_), None) => Ordering::Less,
345                    (None, Some(_)) => Ordering::Greater,
346                    (None, None) => Ordering::Equal,
347                },
348                _ => Ordering::Equal,
349            }
350        })
351        .find(|o| o.is_ne())
352        .unwrap_or_else(|| a.id.as_ref().cmp(b.id.as_ref()))
353}