1use std::cmp::Ordering;
9
10use radixdb_plugin::prelude::*;
11
12pub const PACKAGE_ID: [u8; 16] = [
13 0x8f, 0x45, 0x9a, 0x6d, 0x5c, 0x31, 0x4f, 0x5e, 0xa0, 0x3d, 0x41, 0x2c, 0x68, 0x1e, 0xf1, 0x20,
14];
15pub const PACKAGE_NAME: &str = "radixdb_spatial";
16pub const PACKAGE_VERSION: &str = "1.0.0";
17
18const MAX_POLYGON_POINTS: usize = 256;
19const POLYGON_MAX_BYTES: usize = 4 + MAX_POLYGON_POINTS * 16;
20const MAX_CANDIDATE_SPANS: usize = 1024;
21const MAX_COVER_DEPTH: u32 = 28;
22const MAX_COVER_NODES: usize = 100_000;
23
24#[radixdb_plugin(
25 id = "8f459a6d-5c31-4f5e-a03d-412c681ef120",
26 name = "radixdb_spatial",
27 version = "1.0.0"
28)]
29pub mod spatial {
30 use super::*;
31
32 #[derive(Debug, Default, Clone, Copy, RadixType)]
33 #[radix_type(
34 id = "point",
35 name = "point",
36 codec = 1,
37 semantic_revision = 1,
38 storage = "fixed",
39 max_bytes = 16,
40 equality = point_equal,
41 hash = point_hash,
42 ordering = point_compare
43 )]
44 pub struct Point {
45 #[radix_field(codec = "f64-le")]
46 pub x: f64,
47 #[radix_field(codec = "f64-le")]
48 pub y: f64,
49 }
50
51 #[derive(Debug, Default, Clone, Copy, RadixType)]
52 #[radix_type(
53 id = "box2d",
54 name = "box2d",
55 codec = 1,
56 semantic_revision = 1,
57 storage = "fixed",
58 max_bytes = 32,
59 equality = box_equal,
60 hash = box_hash,
61 ordering = box_compare
62 )]
63 pub struct Box2d {
64 #[radix_field(codec = "f64-le")]
65 pub min_x: f64,
66 #[radix_field(codec = "f64-le")]
67 pub min_y: f64,
68 #[radix_field(codec = "f64-le")]
69 pub max_x: f64,
70 #[radix_field(codec = "f64-le")]
71 pub max_y: f64,
72 }
73
74 #[derive(Debug, Default, Clone, RadixType)]
75 #[radix_type(
76 id = "polygon",
77 name = "polygon",
78 codec = 1,
79 semantic_revision = 1,
80 storage = "variable",
81 max_bytes = 4100,
82 equality = polygon_equal,
83 hash = polygon_hash,
84 ordering = polygon_compare,
85 manual = PolygonCodec
86 )]
87 pub struct Polygon {
88 pub points: Vec<Point>,
89 }
90
91 pub struct PolygonCodec;
92
93 impl ManualCodec<Polygon> for PolygonCodec {
94 fn encode(value: &Polygon, output: &mut CodecWriter) -> PluginResult<()> {
95 if value.points.len() > MAX_POLYGON_POINTS {
96 return Err(PluginError::limit_exceeded("polygon exceeds 256 vertices"));
97 }
98 output.write(&(value.points.len() as u32).to_le_bytes())?;
99 for point in &value.points {
100 output.write(&point.x.to_bits().to_le_bytes())?;
101 output.write(&point.y.to_bits().to_le_bytes())?;
102 }
103 Ok(())
104 }
105
106 fn decode(input: &mut CodecReader<'_>) -> PluginResult<Polygon> {
107 let count = u32::from_le_bytes(input.read(4)?.try_into().expect("fixed width"));
108 let count = usize::try_from(count)
109 .map_err(|_| PluginError::invalid_input("polygon vertex count overflow"))?;
110 if count > MAX_POLYGON_POINTS {
111 return Err(PluginError::limit_exceeded("polygon exceeds 256 vertices"));
112 }
113 let mut points = Vec::with_capacity(count);
114 for _ in 0..count {
115 let x = f64::from_bits(u64::from_le_bytes(
116 input.read(8)?.try_into().expect("fixed width"),
117 ));
118 let y = f64::from_bits(u64::from_le_bytes(
119 input.read(8)?.try_into().expect("fixed width"),
120 ));
121 points.push(Point { x, y });
122 }
123 Ok(Polygon { points })
124 }
125
126 fn corpus() -> Vec<Polygon> {
127 vec![
128 Polygon::default(),
129 Polygon {
130 points: vec![
131 Point { x: 0.0, y: 0.0 },
132 Point { x: 4.0, y: 0.0 },
133 Point { x: 0.0, y: 3.0 },
134 ],
135 },
136 Polygon {
137 points: vec![Point { x: -1.0, y: 1.0 }; MAX_POLYGON_POINTS],
138 },
139 ]
140 }
141 }
142
143 fn normalized(value: f64) -> f64 {
144 if value.is_nan() {
145 f64::from_bits(0x7ff8_0000_0000_0000)
146 } else if value == 0.0 {
147 0.0
148 } else {
149 value
150 }
151 }
152
153 fn point_equal(left: &Point, right: &Point) -> bool {
154 normalized(left.x).to_bits() == normalized(right.x).to_bits()
155 && normalized(left.y).to_bits() == normalized(right.y).to_bits()
156 }
157
158 fn point_hash(value: &Point, sink: &mut HashSink<'_>) -> PluginResult<()> {
159 sink.f64_bits(normalized(value.x))?;
160 sink.f64_bits(normalized(value.y))
161 }
162
163 fn point_compare(left: &Point, right: &Point) -> Ordering {
164 morton_bytes(*left).cmp(&morton_bytes(*right))
165 }
166
167 fn box_equal(left: &Box2d, right: &Box2d) -> bool {
168 box_components(left)
169 .into_iter()
170 .zip(box_components(right))
171 .all(|(left, right)| left.to_bits() == right.to_bits())
172 }
173
174 fn box_hash(value: &Box2d, sink: &mut HashSink<'_>) -> PluginResult<()> {
175 for component in box_components(value) {
176 sink.f64_bits(component)?;
177 }
178 Ok(())
179 }
180
181 fn box_compare(left: &Box2d, right: &Box2d) -> Ordering {
182 box_components(left)
183 .into_iter()
184 .map(f64::to_bits)
185 .cmp(box_components(right).into_iter().map(f64::to_bits))
186 }
187
188 fn box_components(value: &Box2d) -> [f64; 4] {
189 [
190 normalized(value.min_x),
191 normalized(value.min_y),
192 normalized(value.max_x),
193 normalized(value.max_y),
194 ]
195 }
196
197 fn polygon_equal(left: &Polygon, right: &Polygon) -> bool {
198 left.points.len() == right.points.len()
199 && left
200 .points
201 .iter()
202 .zip(&right.points)
203 .all(|(left, right)| point_equal(left, right))
204 }
205
206 fn polygon_hash(value: &Polygon, sink: &mut HashSink<'_>) -> PluginResult<()> {
207 let mut canonical = Vec::with_capacity(POLYGON_MAX_BYTES);
208 canonical.extend_from_slice(&(value.points.len() as u32).to_le_bytes());
209 for point in &value.points {
210 canonical.extend_from_slice(&normalized(point.x).to_bits().to_le_bytes());
211 canonical.extend_from_slice(&normalized(point.y).to_bits().to_le_bytes());
212 }
213 sink.bytes(&canonical)
214 }
215
216 fn polygon_compare(left: &Polygon, right: &Polygon) -> Ordering {
217 left.points
218 .iter()
219 .map(|point| morton_bytes(*point))
220 .cmp(right.points.iter().map(|point| morton_bytes(*point)))
221 }
222
223 fn finite_point(point: Point) -> PluginResult<Point> {
224 if point.x.is_finite() && point.y.is_finite() {
225 Ok(point)
226 } else {
227 Err(PluginError::domain("spatial coordinates must be finite"))
228 }
229 }
230
231 fn valid_box(value: Box2d) -> PluginResult<Box2d> {
232 if ![value.min_x, value.min_y, value.max_x, value.max_y]
233 .into_iter()
234 .all(f64::is_finite)
235 {
236 return Err(PluginError::domain("box coordinates must be finite"));
237 }
238 if value.min_x > value.max_x || value.min_y > value.max_y {
239 return Err(PluginError::domain("box minima must not exceed maxima"));
240 }
241 Ok(value)
242 }
243
244 #[radixdb_scalar(
245 id = "distance",
246 name = "st_distance",
247 semantic_revision = 1,
248 immutable,
249 strict,
250 parallel_safe,
251 cost = 4,
252 cancellation = "bounded",
253 max_output_bytes = 8
254 )]
255 pub fn distance(left: Point, right: Point) -> PluginResult<f64> {
256 let left = finite_point(left)?;
257 let right = finite_point(right)?;
258 Ok((left.x - right.x).hypot(left.y - right.y))
259 }
260
261 #[radixdb_batch(for_scalar = "distance", rows_per_cancel_check = 64)]
262 pub fn distance_batch(
263 left: ColumnView<'_, Point>,
264 right: ColumnView<'_, Point>,
265 output: &mut ColumnBuilder<'_, '_, f64>,
266 context: &CallContext<'_>,
267 ) -> PluginResult<()> {
268 for (row, (left, right)) in left.zip(right).enumerate() {
269 if row % 64 == 0 {
270 context.check_cancelled()?;
271 }
272 output.push(distance(left?, right?)?)?;
273 }
274 Ok(())
275 }
276
277 #[radixdb_scalar(
278 id = "contains",
279 name = "st_contains",
280 semantic_revision = 1,
281 immutable,
282 strict,
283 parallel_safe,
284 cost = 8,
285 cancellation = "bounded",
286 max_output_bytes = 1
287 )]
288 pub fn contains(polygon: Polygon, point: Point) -> PluginResult<bool> {
289 let point = finite_point(point)?;
290 for vertex in &polygon.points {
291 finite_point(*vertex)?;
292 }
293 Ok(polygon_contains(&polygon.points, point))
294 }
295
296 #[radixdb_batch(for_scalar = "contains", rows_per_cancel_check = 32)]
297 pub fn contains_batch(
298 polygons: ColumnView<'_, Polygon>,
299 points: ColumnView<'_, Point>,
300 output: &mut ColumnBuilder<'_, '_, bool>,
301 context: &CallContext<'_>,
302 ) -> PluginResult<()> {
303 for (row, (polygon, point)) in polygons.zip(points).enumerate() {
304 if row % 32 == 0 {
305 context.check_cancelled()?;
306 }
307 output.push(contains(polygon?, point?)?)?;
308 }
309 Ok(())
310 }
311
312 #[radixdb_scalar(
313 id = "intersects",
314 name = "st_intersects",
315 semantic_revision = 1,
316 immutable,
317 strict,
318 parallel_safe,
319 cost = 2,
320 cancellation = "bounded",
321 max_output_bytes = 1
322 )]
323 pub fn intersects(left: Box2d, right: Box2d) -> PluginResult<bool> {
324 let left = valid_box(left)?;
325 let right = valid_box(right)?;
326 Ok(left.min_x <= right.max_x
327 && left.max_x >= right.min_x
328 && left.min_y <= right.max_y
329 && left.max_y >= right.min_y)
330 }
331
332 #[radixdb_batch(for_scalar = "intersects", rows_per_cancel_check = 64)]
333 pub fn intersects_batch(
334 left: ColumnView<'_, Box2d>,
335 right: ColumnView<'_, Box2d>,
336 output: &mut ColumnBuilder<'_, '_, bool>,
337 context: &CallContext<'_>,
338 ) -> PluginResult<()> {
339 for (row, (left, right)) in left.zip(right).enumerate() {
340 if row % 64 == 0 {
341 context.check_cancelled()?;
342 }
343 output.push(intersects(left?, right?)?)?;
344 }
345 Ok(())
346 }
347
348 #[radixdb_scalar(
349 id = "within_box",
350 name = "st_within_box",
351 semantic_revision = 1,
352 immutable,
353 strict,
354 parallel_safe,
355 cost = 2,
356 cancellation = "bounded",
357 max_output_bytes = 1
358 )]
359 pub fn within_box(point: Point, bounds: Box2d) -> PluginResult<bool> {
360 let point = finite_point(point)?;
361 let bounds = valid_box(bounds)?;
362 Ok(point.x >= bounds.min_x
363 && point.x <= bounds.max_x
364 && point.y >= bounds.min_y
365 && point.y <= bounds.max_y)
366 }
367
368 #[radixdb_scalar(
369 id = "within_radius",
370 name = "st_dwithin",
371 semantic_revision = 1,
372 immutable,
373 strict,
374 parallel_safe,
375 cost = 5,
376 cancellation = "bounded",
377 max_output_bytes = 1
378 )]
379 pub fn within_radius(point: Point, center: Point, radius: f64) -> PluginResult<bool> {
380 if !radius.is_finite() || radius < 0.0 {
381 return Err(PluginError::domain(
382 "radius must be finite and non-negative",
383 ));
384 }
385 Ok(distance(point, center)? <= radius)
386 }
387
388 #[radixdb_scalar(
389 id = "point_lt",
390 name = "point_lt",
391 semantic_revision = 1,
392 immutable,
393 strict,
394 parallel_safe,
395 cost = 1,
396 cancellation = "bounded",
397 max_output_bytes = 1
398 )]
399 fn point_lt(left: Point, right: Point) -> PluginResult<bool> {
400 Ok(point_compare(&left, &right) == Ordering::Less)
401 }
402
403 #[radixdb_scalar(
404 id = "point_le",
405 name = "point_le",
406 semantic_revision = 1,
407 immutable,
408 strict,
409 parallel_safe,
410 cost = 1,
411 cancellation = "bounded",
412 max_output_bytes = 1
413 )]
414 fn point_le(left: Point, right: Point) -> PluginResult<bool> {
415 Ok(point_compare(&left, &right) != Ordering::Greater)
416 }
417
418 #[radixdb_scalar(
419 id = "point_eq",
420 name = "point_eq",
421 semantic_revision = 1,
422 immutable,
423 strict,
424 parallel_safe,
425 cost = 1,
426 cancellation = "bounded",
427 max_output_bytes = 1
428 )]
429 fn point_eq(left: Point, right: Point) -> PluginResult<bool> {
430 Ok(point_equal(&left, &right))
431 }
432
433 #[radixdb_scalar(
434 id = "point_ge",
435 name = "point_ge",
436 semantic_revision = 1,
437 immutable,
438 strict,
439 parallel_safe,
440 cost = 1,
441 cancellation = "bounded",
442 max_output_bytes = 1
443 )]
444 fn point_ge(left: Point, right: Point) -> PluginResult<bool> {
445 Ok(point_compare(&left, &right) != Ordering::Less)
446 }
447
448 #[radixdb_scalar(
449 id = "point_gt",
450 name = "point_gt",
451 semantic_revision = 1,
452 immutable,
453 strict,
454 parallel_safe,
455 cost = 1,
456 cancellation = "bounded",
457 max_output_bytes = 1
458 )]
459 fn point_gt(left: Point, right: Point) -> PluginResult<bool> {
460 Ok(point_compare(&left, &right) == Ordering::Greater)
461 }
462
463 #[radixdb_operator(
464 id = "point_lt_operator",
465 symbol = "<",
466 semantic_revision = 1,
467 function = "point_lt",
468 left = Point,
469 right = Point,
470 result = bool
471 )]
472 #[allow(dead_code)]
473 fn point_lt_operator() {}
474
475 #[radixdb_operator(
476 id = "point_le_operator",
477 symbol = "<=",
478 semantic_revision = 1,
479 function = "point_le",
480 left = Point,
481 right = Point,
482 result = bool
483 )]
484 #[allow(dead_code)]
485 fn point_le_operator() {}
486
487 #[radixdb_operator(
488 id = "point_eq_operator",
489 symbol = "=",
490 semantic_revision = 1,
491 function = "point_eq",
492 left = Point,
493 right = Point,
494 result = bool
495 )]
496 #[allow(dead_code)]
497 fn point_eq_operator() {}
498
499 #[radixdb_operator(
500 id = "point_ge_operator",
501 symbol = ">=",
502 semantic_revision = 1,
503 function = "point_ge",
504 left = Point,
505 right = Point,
506 result = bool
507 )]
508 #[allow(dead_code)]
509 fn point_ge_operator() {}
510
511 #[radixdb_operator(
512 id = "point_gt_operator",
513 symbol = ">",
514 semantic_revision = 1,
515 function = "point_gt",
516 left = Point,
517 right = Point,
518 result = bool
519 )]
520 #[allow(dead_code)]
521 fn point_gt_operator() {}
522
523 #[radixdb_operator_class(
524 id = "point_morton_btree",
525 semantic_revision = 1,
526 access_method = "btree",
527 input = Point,
528 key = BoundedBytes::<16>,
529 key_codec_revision = 1
530 )]
531 pub fn point_morton_key(point: Point) -> PluginResult<BoundedBytes<16>> {
532 BoundedBytes::new(morton_bytes(point).to_vec())
533 }
534
535 #[radixdb_planner_support(
536 id = "within_box_support",
537 name = "st_within_box_support",
538 semantic_revision = 1,
539 for_function = "within_box",
540 operator_class = "point_morton_btree",
541 always_recheck,
542 max_spans = 1024,
543 max_output_bytes = 49152
544 )]
545 fn within_box_support(
546 predicate: PredicateView<'_>,
547 output: &mut CandidatePlanBuilder<'_, '_>,
548 ) -> PluginResult<()> {
549 if predicate.indexed_argument()? != 0 || predicate.argument_count()? != 2 {
550 return Err(PluginError::invalid_input(
551 "st_within_box support requires indexed point argument 0",
552 ));
553 }
554 let bounds = predicate
555 .constant::<Box2d>(1)?
556 .ok_or_else(|| PluginError::domain("NULL box has no candidate range"))?;
557 publish_cover(valid_box(bounds)?, output)
558 }
559
560 #[radixdb_planner_support(
561 id = "within_radius_support",
562 name = "st_dwithin_support",
563 semantic_revision = 1,
564 for_function = "within_radius",
565 operator_class = "point_morton_btree",
566 always_recheck,
567 max_spans = 1024,
568 max_output_bytes = 49152
569 )]
570 fn within_radius_support(
571 predicate: PredicateView<'_>,
572 output: &mut CandidatePlanBuilder<'_, '_>,
573 ) -> PluginResult<()> {
574 if predicate.indexed_argument()? != 0 || predicate.argument_count()? != 3 {
575 return Err(PluginError::invalid_input(
576 "st_dwithin support requires indexed point argument 0",
577 ));
578 }
579 let center = predicate
580 .constant::<Point>(1)?
581 .ok_or_else(|| PluginError::domain("NULL center has no candidate range"))?;
582 let radius = predicate
583 .constant::<f64>(2)?
584 .ok_or_else(|| PluginError::domain("NULL radius has no candidate range"))?;
585 let center = finite_point(center)?;
586 if !radius.is_finite() || radius < 0.0 {
587 return Err(PluginError::domain(
588 "radius must be finite and non-negative",
589 ));
590 }
591 publish_cover(
592 Box2d {
593 min_x: center.x - radius,
594 min_y: center.y - radius,
595 max_x: center.x + radius,
596 max_y: center.y + radius,
597 },
598 output,
599 )
600 }
601
602 fn publish_cover(bounds: Box2d, output: &mut CandidatePlanBuilder<'_, '_>) -> PluginResult<()> {
603 let spans = candidate_spans(bounds)?;
604 output.set_estimate(1, spans.len() as u32)?;
608 for span in spans {
609 output.push_span(span)?;
610 }
611 Ok(())
612 }
613
614 pub fn candidate_spans(bounds: Box2d) -> PluginResult<Vec<CandidateSpan>> {
615 let bounds = valid_box(bounds)?;
616 let query = IntegerBox {
617 min_x: sortable_bits(bounds.min_x),
618 min_y: sortable_bits(bounds.min_y),
619 max_x: sortable_bits(bounds.max_x),
620 max_y: sortable_bits(bounds.max_y),
621 };
622 let mut remaining_nodes = MAX_COVER_NODES;
623 let mut spans = cover_node(0, 0, 0, query, &mut remaining_nodes);
624 spans.sort_by(|left, right| left.start.cmp(&right.start));
625 Ok(spans)
626 }
627
628 fn polygon_contains(points: &[Point], point: Point) -> bool {
629 if points.len() < 3 {
630 return false;
631 }
632 let mut inside = false;
633 let mut previous = points[points.len() - 1];
634 for ¤t in points {
635 if point_on_segment(previous, current, point) {
636 return true;
637 }
638 let crosses = (current.y > point.y) != (previous.y > point.y)
639 && point.x
640 < (previous.x - current.x) * (point.y - current.y) / (previous.y - current.y)
641 + current.x;
642 if crosses {
643 inside = !inside;
644 }
645 previous = current;
646 }
647 inside
648 }
649
650 fn point_on_segment(left: Point, right: Point, point: Point) -> bool {
651 let cross =
652 (point.y - left.y) * (right.x - left.x) - (point.x - left.x) * (right.y - left.y);
653 if cross.abs() > f64::EPSILON * 16.0 {
654 return false;
655 }
656 point.x >= left.x.min(right.x)
657 && point.x <= left.x.max(right.x)
658 && point.y >= left.y.min(right.y)
659 && point.y <= left.y.max(right.y)
660 }
661
662 fn sortable_bits(value: f64) -> u64 {
663 let bits = normalized(value).to_bits();
664 if bits & (1_u64 << 63) != 0 {
665 !bits
666 } else {
667 bits ^ (1_u64 << 63)
668 }
669 }
670
671 pub fn morton_bytes(point: Point) -> [u8; 16] {
672 let x = sortable_bits(point.x);
673 let y = sortable_bits(point.y);
674 let mut morton = 0_u128;
675 for bit in (0..64).rev() {
676 morton = (morton << 1) | u128::from((x >> bit) & 1);
677 morton = (morton << 1) | u128::from((y >> bit) & 1);
678 }
679 morton.to_be_bytes()
680 }
681
682 #[derive(Clone, Copy)]
683 struct IntegerBox {
684 min_x: u64,
685 min_y: u64,
686 max_x: u64,
687 max_y: u64,
688 }
689
690 fn cover_node(
691 depth: u32,
692 x_prefix: u64,
693 y_prefix: u64,
694 query: IntegerBox,
695 remaining_nodes: &mut usize,
696 ) -> Vec<CandidateSpan> {
697 if *remaining_nodes == 0 {
698 return vec![prefix_span(depth, x_prefix, y_prefix)];
699 }
700 *remaining_nodes -= 1;
701 let node = prefix_box(depth, x_prefix, y_prefix);
702 if !integer_boxes_intersect(node, query) {
703 return Vec::new();
704 }
705 if integer_box_contains(query, node) || depth == MAX_COVER_DEPTH {
706 return vec![prefix_span(depth, x_prefix, y_prefix)];
707 }
708
709 let mut children = Vec::new();
710 for x_bit in 0..=1 {
711 for y_bit in 0..=1 {
712 children.extend(cover_node(
713 depth + 1,
714 (x_prefix << 1) | x_bit,
715 (y_prefix << 1) | y_bit,
716 query,
717 remaining_nodes,
718 ));
719 if children.len() > MAX_CANDIDATE_SPANS {
720 return vec![prefix_span(depth, x_prefix, y_prefix)];
721 }
722 }
723 }
724 children
725 }
726
727 fn prefix_box(depth: u32, x_prefix: u64, y_prefix: u64) -> IntegerBox {
728 if depth == 0 {
729 return IntegerBox {
730 min_x: 0,
731 min_y: 0,
732 max_x: u64::MAX,
733 max_y: u64::MAX,
734 };
735 }
736 let suffix_bits = 64 - depth;
737 let suffix_mask = (1_u64 << suffix_bits) - 1;
738 IntegerBox {
739 min_x: x_prefix << suffix_bits,
740 min_y: y_prefix << suffix_bits,
741 max_x: (x_prefix << suffix_bits) | suffix_mask,
742 max_y: (y_prefix << suffix_bits) | suffix_mask,
743 }
744 }
745
746 fn integer_boxes_intersect(left: IntegerBox, right: IntegerBox) -> bool {
747 left.min_x <= right.max_x
748 && left.max_x >= right.min_x
749 && left.min_y <= right.max_y
750 && left.max_y >= right.min_y
751 }
752
753 fn integer_box_contains(outer: IntegerBox, inner: IntegerBox) -> bool {
754 outer.min_x <= inner.min_x
755 && outer.max_x >= inner.max_x
756 && outer.min_y <= inner.min_y
757 && outer.max_y >= inner.max_y
758 }
759
760 fn prefix_span(depth: u32, x_prefix: u64, y_prefix: u64) -> CandidateSpan {
761 let mut prefix = 0_u128;
762 for bit in (0..depth).rev() {
763 prefix = (prefix << 1) | u128::from((x_prefix >> bit) & 1);
764 prefix = (prefix << 1) | u128::from((y_prefix >> bit) & 1);
765 }
766 let suffix_bits = 128 - depth * 2;
767 let start = if suffix_bits == 128 {
768 0
769 } else {
770 prefix << suffix_bits
771 };
772 let end = if suffix_bits == 128 {
773 u128::MAX
774 } else {
775 start | ((1_u128 << suffix_bits) - 1)
776 };
777 CandidateSpan {
778 start: start.to_be_bytes().to_vec(),
779 end: end.to_be_bytes().to_vec(),
780 }
781 }
782}
783
784pub use spatial::{Box2d, Point, Polygon};
785
786pub fn descriptor() -> &'static radixdb_plugin::__private::abi::RadixPluginDescriptorV1 {
787 spatial::__radixdb_descriptor()
788}
789
790pub fn encode<T: RadixType>(value: &T) -> PluginResult<Vec<u8>> {
791 let mut output = CodecWriter::new(T::MAX_BYTES as usize);
792 value.encode(&mut output)?;
793 Ok(output.into_bytes())
794}
795
796#[cfg(test)]
797mod tests {
798 use super::*;
799
800 #[test]
801 fn descriptor_and_all_three_codecs_pass_public_sdk_gates() {
802 radixdb_plugin::testing::validate_descriptor_graph(descriptor()).unwrap();
803 assert_eq!(descriptor().type_count, 3);
804 assert_eq!(descriptor().planner_support_count, 2);
805 radixdb_plugin::testing::check_type::<Point>().unwrap();
806 radixdb_plugin::testing::check_type::<Box2d>().unwrap();
807 radixdb_plugin::testing::check_type::<Polygon>().unwrap();
808 }
809
810 #[test]
811 fn geometry_edge_cases_are_explicit() {
812 let triangle = Polygon {
813 points: vec![
814 Point { x: 0.0, y: 0.0 },
815 Point { x: 4.0, y: 0.0 },
816 Point { x: 0.0, y: 4.0 },
817 ],
818 };
819 assert!(spatial::contains(triangle.clone(), Point { x: 1.0, y: 1.0 }).unwrap());
820 assert!(spatial::contains(triangle.clone(), Point { x: 2.0, y: 0.0 }).unwrap());
821 assert!(!spatial::contains(triangle, Point { x: 4.0, y: 4.0 }).unwrap());
822 assert!(spatial::intersects(
823 Box2d {
824 min_x: 0.0,
825 min_y: 0.0,
826 max_x: 1.0,
827 max_y: 1.0,
828 },
829 Box2d {
830 min_x: 1.0,
831 min_y: 1.0,
832 max_x: 2.0,
833 max_y: 2.0,
834 },
835 )
836 .unwrap());
837 assert!(
838 spatial::distance(Point { x: 0.0, y: 0.0 }, Point { x: 3.0, y: 4.0 }).unwrap() == 5.0
839 );
840 assert!(spatial::distance(
841 Point {
842 x: f64::NAN,
843 y: 0.0,
844 },
845 Point::default(),
846 )
847 .is_err());
848 }
849
850 #[test]
851 fn morton_cover_has_no_false_negatives_and_is_bounded() {
852 let bounds = Box2d {
853 min_x: 1002.5,
854 min_y: 2001.25,
855 max_x: 1003.75,
856 max_y: 2008.5,
857 };
858 let spans = spatial::candidate_spans(bounds).unwrap();
859 assert!(!spans.is_empty());
860 assert!(spans.len() <= MAX_CANDIDATE_SPANS);
861 for x in 10025..=10037 {
862 for y in 20013..=20085 {
863 let point = Point {
864 x: f64::from(x) / 10.0,
865 y: f64::from(y) / 10.0,
866 };
867 let key = spatial::morton_bytes(point);
868 assert!(spans
869 .iter()
870 .any(|span| span.start.as_slice() <= key.as_slice()
871 && key.as_slice() <= span.end.as_slice()));
872 }
873 }
874 }
875
876 #[test]
877 fn deterministic_differential_cover_matches_exact_scan() {
878 let queries = [
879 Box2d {
880 min_x: -750.0,
881 min_y: -500.0,
882 max_x: -125.0,
883 max_y: 300.0,
884 },
885 Box2d {
886 min_x: -0.0,
887 min_y: -0.0,
888 max_x: 0.0,
889 max_y: 0.0,
890 },
891 Box2d {
892 min_x: 100.0,
893 min_y: 200.0,
894 max_x: 700.0,
895 max_y: 850.0,
896 },
897 ];
898 let mut state = 0x6a09_e667_f3bc_c909_u64;
899 let points = (0..65_536)
900 .map(|_| {
901 state = state
902 .wrapping_mul(6_364_136_223_846_793_005)
903 .wrapping_add(1_442_695_040_888_963_407);
904 let x = ((state >> 11) as f64 / ((1_u64 << 53) as f64)) * 2_000.0 - 1_000.0;
905 state = state
906 .wrapping_mul(6_364_136_223_846_793_005)
907 .wrapping_add(1_442_695_040_888_963_407);
908 let y = ((state >> 11) as f64 / ((1_u64 << 53) as f64)) * 2_000.0 - 1_000.0;
909 Point { x, y }
910 })
911 .chain([Point { x: -0.0, y: 0.0 }, Point { x: 0.0, y: -0.0 }])
912 .collect::<Vec<_>>();
913
914 for query in queries {
915 let spans = spatial::candidate_spans(query).unwrap();
916 for point in &points {
917 let exact = spatial::within_box(*point, query).unwrap();
918 let key = spatial::morton_bytes(*point);
919 let candidate = spans.iter().any(|span| {
920 span.start.as_slice() <= key.as_slice() && key.as_slice() <= span.end.as_slice()
921 });
922 assert!(!exact || candidate, "candidate cover lost point {point:?}");
923 }
924 }
925 }
926
927 #[test]
928 fn scalar_and_batch_results_match_for_all_primitives() {
929 use radixdb_plugin::testing::{invoke_batch, invoke_scalar, TestValue};
930
931 let point_rows = [
932 (Point { x: 0.0, y: 0.0 }, Point { x: 3.0, y: 4.0 }),
933 (Point { x: -2.0, y: 7.0 }, Point { x: 1.0, y: 3.0 }),
934 ];
935 let rows = point_rows
936 .iter()
937 .map(|(left, right)| {
938 Ok(vec![
939 TestValue::external(descriptor(), left)?,
940 TestValue::external(descriptor(), right)?,
941 ])
942 })
943 .collect::<PluginResult<Vec<_>>>()
944 .unwrap();
945 assert_batch_parity("distance", &rows);
946
947 let polygon = Polygon {
948 points: vec![
949 Point { x: 0.0, y: 0.0 },
950 Point { x: 4.0, y: 0.0 },
951 Point { x: 0.0, y: 4.0 },
952 ],
953 };
954 let rows = [Point { x: 1.0, y: 1.0 }, Point { x: 5.0, y: 5.0 }]
955 .iter()
956 .map(|point| {
957 Ok(vec![
958 TestValue::external(descriptor(), &polygon)?,
959 TestValue::external(descriptor(), point)?,
960 ])
961 })
962 .collect::<PluginResult<Vec<_>>>()
963 .unwrap();
964 assert_batch_parity("contains", &rows);
965
966 let boxes = [
967 Box2d {
968 min_x: 0.0,
969 min_y: 0.0,
970 max_x: 2.0,
971 max_y: 2.0,
972 },
973 Box2d {
974 min_x: 5.0,
975 min_y: 5.0,
976 max_x: 6.0,
977 max_y: 6.0,
978 },
979 ];
980 let probe = Box2d {
981 min_x: 1.0,
982 min_y: 1.0,
983 max_x: 3.0,
984 max_y: 3.0,
985 };
986 let rows = boxes
987 .iter()
988 .map(|bounds| {
989 Ok(vec![
990 TestValue::external(descriptor(), bounds)?,
991 TestValue::external(descriptor(), &probe)?,
992 ])
993 })
994 .collect::<PluginResult<Vec<_>>>()
995 .unwrap();
996 assert_batch_parity("intersects", &rows);
997
998 fn assert_batch_parity(name: &str, rows: &[Vec<TestValue>]) {
999 let batch = invoke_batch(descriptor(), name, rows, Default::default()).unwrap();
1000 assert!(batch.finished);
1001 for (index, arguments) in rows.iter().enumerate() {
1002 let scalar =
1003 invoke_scalar(descriptor(), name, arguments, Default::default()).unwrap();
1004 assert_eq!(scalar.outputs.as_slice(), &batch.outputs[index..=index]);
1005 }
1006 }
1007 }
1008
1009 #[test]
1010 fn authoring_crate_has_only_the_public_sdk_dependency() {
1011 let manifest = include_str!("../Cargo.toml");
1012 let dependencies = manifest
1013 .split("[dependencies]")
1014 .nth(1)
1015 .unwrap()
1016 .split('[')
1017 .next()
1018 .unwrap();
1019 assert_eq!(
1020 dependencies
1021 .lines()
1022 .filter(|line| !line.trim().is_empty())
1023 .count(),
1024 1
1025 );
1026 assert!(dependencies.contains("radixdb-plugin"));
1027 for forbidden in [
1028 "radixdb-storage",
1029 "radixdb-executor",
1030 "radixdb-catalog",
1031 "radixdb-core",
1032 "radixdb-plugin-host",
1033 "radixdb-plugin-abi",
1034 ] {
1035 assert!(!dependencies.contains(forbidden));
1036 }
1037 }
1038}