ferrostar 0.51.0

//! Tools for deciding when the user has sufficiently deviated from a route.
//!
//! The types in this module are designed around route deviation detection as a single responsibility:
//!
//! While the most common use for this is triggering route recalculation,
//! the decision to reroute (or display an overlay on screen, or any other action) lies with higher levels.
//!
//! For example, on iOS and Android, the `FerrostarCore` class is in charge of deciding
//! when to kick off a new route request.
//! Similarly, you may observe this in your own UI layer and display an overlay under certain conditions.
//!
//! When architecting a Ferrostar core integration for a new platform,
//! we suggest enforcing a similar separation of concerns.

use crate::algorithms::deviation_from_line;
use crate::models::Route;
use crate::navigation_controller::models::TripState;
#[cfg(test)]
use crate::{models::UserLocation, navigation_controller::test_helpers::get_navigating_trip_state};
#[cfg(feature = "alloc")]
use alloc::sync::Arc;
use geo::Point;
use serde::{Deserialize, Serialize};
#[cfg(feature = "wasm-bindgen")]
use tsify::Tsify;

#[cfg(test)]
use {
    crate::{
        models::GeographicCoordinate,
        navigation_controller::test_helpers::{gen_dummy_route_step, gen_route_from_steps},
    },
    proptest::prelude::*,
};

#[cfg(all(test, feature = "std", not(feature = "web-time")))]
use std::time::SystemTime;

#[cfg(all(test, feature = "web-time"))]
use web_time::SystemTime;

/// Determines if the user has deviated from the expected route.
#[derive(Clone, Serialize, Deserialize)]
#[cfg_attr(feature = "uniffi", derive(uniffi::Enum))]
#[cfg_attr(feature = "wasm-bindgen", derive(Tsify))]
#[cfg_attr(feature = "wasm-bindgen", tsify(from_wasm_abi))]
pub enum RouteDeviationTracking {
    /// No checks will be done, and we assume the user is always following the route.
    None,
    /// Detects deviation from the route using a configurable static distance threshold from the route line.
    #[cfg_attr(feature = "wasm-bindgen", serde(rename_all = "camelCase"))]
    StaticThreshold {
        /// The minimum required horizontal accuracy of the user location, in meters.
        /// Values larger than this will not trigger route deviation warnings.
        minimum_horizontal_accuracy: u16,
        /// The maximum acceptable deviation from the route line, in meters.
        ///
        /// If the distance between the reported location and the expected route line
        /// is greater than this threshold, it will be flagged as an off route condition.
        max_acceptable_deviation: f64,
    },
    // TODO: Standard variants that account for mode of travel. For example, `DefaultFor(modeOfTravel: ModeOfTravel)` with sensible defaults for walking, driving, cycling, etc.
    /// An arbitrary user-defined implementation.
    /// You decide with your own [`RouteDeviationDetector`] implementation!
    #[serde(skip)]
    Custom {
        detector: Arc<dyn RouteDeviationDetector>,
    },
}

impl RouteDeviationTracking {
    #[must_use]
    pub(crate) fn check_route_deviation(
        &self,
        route: &Route,
        trip_state: &TripState,
    ) -> RouteDeviation {
        match self {
            RouteDeviationTracking::None => RouteDeviation::NoDeviation,
            RouteDeviationTracking::StaticThreshold {
                minimum_horizontal_accuracy,
                max_acceptable_deviation,
            } => match trip_state {
                TripState::Idle { .. } | TripState::Complete { .. } => RouteDeviation::NoDeviation,
                TripState::Navigating {
                    user_location,
                    remaining_steps,
                    ..
                } => {
                    // Short-circuit in case the GPS is going wild (e.g. in a tunnel or deep urban canyon).
                    if user_location.horizontal_accuracy > f64::from(*minimum_horizontal_accuracy) {
                        return RouteDeviation::NoDeviation;
                    }

                    let user_point = Point::from(*user_location);

                    // No steps remain, so... ;)
                    let Some(current_step) = remaining_steps.first() else {
                        return RouteDeviation::NoDeviation;
                    };

                    let current_step_distance =
                        deviation_from_line(&user_point, &current_step.get_linestring())
                            .unwrap_or(0.0);

                    // Check if the user is on the current step.
                    if current_step_distance <= *max_acceptable_deviation {
                        return RouteDeviation::NoDeviation;
                    }

                    // User is off the current step. Check if they're on any future step.
                    for step in remaining_steps.iter().skip(1) {
                        let distance = deviation_from_line(&user_point, &step.get_linestring())
                            .unwrap_or(f64::MAX);
                        if distance <= *max_acceptable_deviation {
                            return RouteDeviation::Deviation {
                                kind: DeviationKind::OffStepOnRoute {
                                    deviation_from_step_line: current_step_distance,
                                },
                            };
                        }
                    }

                    // Not within the distance threshold of *any* step, so we're off the route.
                    RouteDeviation::Deviation {
                        kind: DeviationKind::CompletelyOffRoute {
                            deviation_from_route_line: current_step_distance,
                        },
                    }
                }
            },
            RouteDeviationTracking::Custom { detector } => {
                detector.check_route_deviation(route.clone(), trip_state.clone())
            }
        }
    }
}

/// The kind of deviation from the expected route.
#[derive(Debug, Copy, Clone, PartialEq, Serialize, Deserialize)]
#[cfg_attr(feature = "uniffi", derive(uniffi::Enum))]
#[cfg_attr(feature = "wasm-bindgen", derive(Tsify))]
#[cfg_attr(feature = "wasm-bindgen", tsify(into_wasm_abi, from_wasm_abi))]
pub enum DeviationKind {
    /// The user is off the current step, but still on the route polyline (on a future step).
    ///
    /// This can happen when the user takes a shortcut, GPS noise places them on a future step,
    /// or the route self-intersects. Step advance conditions can use this to limit advancement.
    #[cfg_attr(feature = "wasm-bindgen", serde(rename_all = "camelCase"))]
    OffStepOnRoute {
        /// The deviation from the current step line, in meters.
        deviation_from_step_line: f64,
    },
    /// The user is off the expected route entirely
    /// (not within threshold of any remaining step,
    /// neither the current one nor any future one).
    #[cfg_attr(feature = "wasm-bindgen", serde(rename_all = "camelCase"))]
    CompletelyOffRoute {
        /// The deviation from the route line, in meters.
        deviation_from_route_line: f64,
    },
}

/// Status information that describes whether the user is proceeding according to the route or not.
///
/// Note that the name is intentionally a bit generic to allow for expansion of other states.
/// For example, we could conceivably add a "wrong way" status in the future.
#[derive(Debug, Copy, Clone, PartialEq, Serialize, Deserialize)]
#[cfg_attr(feature = "uniffi", derive(uniffi::Enum))]
#[cfg_attr(feature = "wasm-bindgen", derive(Tsify))]
#[cfg_attr(feature = "wasm-bindgen", tsify(into_wasm_abi, from_wasm_abi))]
pub enum RouteDeviation {
    /// The user is proceeding on course within the expected tolerances; everything is normal.
    NoDeviation,
    /// The user has deviated from the expected route.
    ///
    /// Check the [`DeviationKind`] to determine if the user is still on the route polyline
    /// (off the current step but on a future step) or off the route entirely.
    Deviation { kind: DeviationKind },
}

impl RouteDeviation {
    /// Whether the user is no longer on the current step's polyline.
    ///
    /// This can happen either because the user has moved onto a future step
    /// without triggering advance, or because they have left the route entirely.
    /// In other words: **any deviation from the current step**.
    #[must_use]
    pub fn is_deviated_from_current_step(&self) -> bool {
        matches!(self, RouteDeviation::Deviation { .. })
    }

    /// Whether the user has deviated from the route entirely.
    ///
    /// This is true when the user is not just deviated from the current step,
    /// but also from the route as a whole (they didn't just take a shortcut).
    #[must_use]
    pub fn is_completely_off_route(&self) -> bool {
        matches!(
            self,
            RouteDeviation::Deviation {
                kind: DeviationKind::CompletelyOffRoute { .. }
            }
        )
    }
}

/// A custom deviation detector (for extending the behavior of [`RouteDeviationTracking`]).
///
/// This allows for arbitrarily complex implementations when the provided ones are not enough.
/// For example, detecting that the user is proceeding the wrong direction by keeping a ring buffer
/// of recent locations, or perform local map matching.
#[cfg_attr(feature = "uniffi", uniffi::export(with_foreign))]
pub trait RouteDeviationDetector: Send + Sync {
    /// Determines whether the user is following the route correctly or not.
    ///
    /// NOTE: This function has a single responsibility.
    /// Side-effects like whether to recalculate a route are left to higher levels,
    /// and implementations should only be concerned with determining the facts.
    ///
    /// IMPORTANT: If you are short circuiting [`StepAdvanceCondition`]'s to allow
    /// skipping steps, you must always fall back to checking the deviation from the
    /// full route line.
    #[must_use]
    fn check_route_deviation(&self, route: Route, trip_state: TripState) -> RouteDeviation;
}

#[cfg(test)]
proptest! {
    /// Tests [`RouteDeviationTracking::None`] behavior,
    /// which never reports that the user is off route, even when they obviously are.
    #[test]
    fn no_deviation_tracking(
        x1: f64, y1: f64,
        x2: f64, y2: f64,
        x3: f64, y3: f64,
    ) {
        let tracking = RouteDeviationTracking::None;
        let current_route_step = gen_dummy_route_step(x1, y1, x2, y2);
        let route = gen_route_from_steps(vec![current_route_step.clone()]);

        // Set the user location to the start of the route step.
        // This is clearly on the route.
        let user_location_on_route = UserLocation {
            coordinates: GeographicCoordinate {
                lng: x1,
                lat: y1,
            },
            horizontal_accuracy: 0.0,
            course_over_ground: None,
            timestamp: SystemTime::now(),
            speed: None
        };
        let trip_state = get_navigating_trip_state(
            user_location_on_route.clone(),
            vec![current_route_step.clone()],
            vec![],
            RouteDeviation::NoDeviation
        );
        prop_assert_eq!(
            tracking.check_route_deviation(&route, &trip_state),
            RouteDeviation::NoDeviation
        );

        // Set the user location to a random value.
        // This may be well off route, but we don't care in this mode.
        let user_location_random = UserLocation {
            coordinates: GeographicCoordinate {
                lng: x3,
                lat: y3,
            },
            horizontal_accuracy: 0.0,
            course_over_ground: None,
            timestamp: SystemTime::now(),
            speed: None
        };
        let trip_state_random = get_navigating_trip_state(
            user_location_random.clone(),
            vec![current_route_step.clone()],
            vec![],
            RouteDeviation::NoDeviation
        );
        prop_assert_eq!(
            tracking.check_route_deviation(&route, &trip_state_random),
            RouteDeviation::NoDeviation
        );
    }

    /// Implements the same behavior as [`RouteDeviationTracking::None`]
    /// with user-supplied code.
    #[test]
    fn custom_no_deviation_mode(
        x1: f64, y1: f64,
        x2: f64, y2: f64,
        x3: f64, y3: f64,
    ) {
        struct NeverDetector {}

        impl RouteDeviationDetector for NeverDetector {
            fn check_route_deviation(
                &self,
                _route: Route,
                _trip_state: TripState,
            ) -> RouteDeviation {
                return RouteDeviation::NoDeviation
            }
        }

        let tracking = RouteDeviationTracking::Custom {
            detector: Arc::new(NeverDetector {})
        };
        let current_route_step = gen_dummy_route_step(x1, y1, x2, y2);
        let route = gen_route_from_steps(vec![current_route_step.clone()]);

        // Set the user location to the start of the route step.
        // This is clearly on the route.
        let user_location_on_route = UserLocation {
            coordinates: GeographicCoordinate {
                lng: x1,
                lat: y1,
            },
            horizontal_accuracy: 0.0,
            course_over_ground: None,
            timestamp: SystemTime::now(),
            speed: None
        };
        let trip_state_on_route = get_navigating_trip_state(
            user_location_on_route.clone(),
            vec![current_route_step.clone()],
            vec![],
            RouteDeviation::NoDeviation
        );
        prop_assert_eq!(
            tracking.check_route_deviation(&route, &trip_state_on_route),
            RouteDeviation::NoDeviation
        );

        // Set the user location to a random value.
        // This may be well off route, but we don't care in this mode.
        let user_location_random = UserLocation {
            coordinates: GeographicCoordinate {
                lng: x3,
                lat: y3,
            },
            horizontal_accuracy: 0.0,
            course_over_ground: None,
            timestamp: SystemTime::now(),
            speed: None
        };
        let trip_state_random = get_navigating_trip_state(
            user_location_random.clone(),
            vec![current_route_step.clone()],
            vec![],
            RouteDeviation::NoDeviation
        );
        prop_assert_eq!(
            tracking.check_route_deviation(&route, &trip_state_random),
            RouteDeviation::NoDeviation
        );
    }

    /// Custom behavior claiming that the user is always off the route.
    #[test]
    fn custom_always_off_route(
        x1: f64, y1: f64,
        x2: f64, y2: f64,
        x3: f64, y3: f64,
    ) {
        struct NeverDetector {}

        impl RouteDeviationDetector for NeverDetector {
            fn check_route_deviation(
                &self,
                _route: Route,
                _trip_state: TripState,
            ) -> RouteDeviation {
                RouteDeviation::Deviation {
                    kind: DeviationKind::CompletelyOffRoute {
                        deviation_from_route_line: 7.0,
                    },
                }
            }
        }

        let tracking = RouteDeviationTracking::Custom {
            detector: Arc::new(NeverDetector {})
        };
        let current_route_step = gen_dummy_route_step(x1, y1, x2, y2);
        let route = gen_route_from_steps(vec![current_route_step.clone()]);

        // Set the user location to the start of the route step.
        // This is clearly on the route.
        let user_location_on_route = UserLocation {
            coordinates: GeographicCoordinate {
                lng: x1,
                lat: y1,
            },
            horizontal_accuracy: 0.0,
            course_over_ground: None,
            timestamp: SystemTime::now(),
            speed: None
        };
        let trip_state_on_route = get_navigating_trip_state(
            user_location_on_route.clone(),
            vec![current_route_step.clone()],
            vec![],
            RouteDeviation::NoDeviation
        );
        prop_assert_eq!(
            tracking.check_route_deviation(&route, &trip_state_on_route),
            RouteDeviation::Deviation {
                kind: DeviationKind::CompletelyOffRoute {
                    deviation_from_route_line: 7.0,
                },
            }
        );

        // Set the user location to a random value.
        // This may be well off route, but we don't care in this mode.
        let user_location_random = UserLocation {
            coordinates: GeographicCoordinate {
                lng: x3,
                lat: y3,
            },
            horizontal_accuracy: 0.0,
            course_over_ground: None,
            timestamp: SystemTime::now(),
            speed: None
        };
        let trip_state_random = get_navigating_trip_state(
            user_location_random.clone(),
            vec![current_route_step.clone()],
            vec![],
            RouteDeviation::NoDeviation
        );
        prop_assert_eq!(
            tracking.check_route_deviation(&route, &trip_state_random),
            RouteDeviation::Deviation {
                kind: DeviationKind::CompletelyOffRoute {
                    deviation_from_route_line: 7.0,
                },
            }
        );
    }

    /// Tests [`RouteDeviationTracking::StaticThreshold`] behavior,
    /// using [`algorithms::deviation_from_line`](crate::algorithms::deviation_from_line)
    #[test]
    fn static_threshold_oracle_test(
        x1: f64, y1: f64,
        x2: f64, y2: f64,
        x3: f64, y3: f64,
        minimum_horizontal_accuracy: u16,
        horizontal_accuracy: f64,
        max_acceptable_deviation in 0f64..,
    ) {
        let tracking = RouteDeviationTracking::StaticThreshold {
            minimum_horizontal_accuracy,
            max_acceptable_deviation
        };
        let current_route_step = gen_dummy_route_step(x1, y1, x2, y2);
        let route = gen_route_from_steps(vec![current_route_step.clone()]);

        // Set the user location to the start of the route step.
        // This is clearly on the route.
        let user_location_on_route = UserLocation {
            coordinates: GeographicCoordinate {
                lng: x1,
                lat: y1,
            },
            horizontal_accuracy,
            course_over_ground: None,
            timestamp: SystemTime::now(),
            speed: None
        };
        let trip_state = get_navigating_trip_state(
            user_location_on_route.clone(),
            vec![current_route_step.clone()],
            vec![],
            RouteDeviation::NoDeviation
        );
        prop_assert_eq!(
            tracking.check_route_deviation(&route, &trip_state),
            RouteDeviation::NoDeviation
        );

        // Set the user location to a random value.
        // This may be well off route. Check the deviation_from_line helper
        // as an oracle.
        let coordinates = GeographicCoordinate {
            lng: x3,
            lat: y3,
        };
        let user_location_random = UserLocation {
            coordinates,
            horizontal_accuracy: 0.0,
            course_over_ground: None,
            timestamp: SystemTime::now(),
            speed: None
        };
        let trip_state_random = get_navigating_trip_state(
            user_location_random.clone(),
            vec![current_route_step.clone()],
            vec![],
            RouteDeviation::NoDeviation
        );
        let deviation = deviation_from_line(&Point::from(coordinates), &current_route_step.get_linestring());
        match tracking.check_route_deviation(&route, &trip_state_random) {
            RouteDeviation::NoDeviation => {
                if let Some(calculated) = deviation {
                    prop_assert!(calculated <= max_acceptable_deviation);
                }
            }
            RouteDeviation::Deviation { kind: DeviationKind::OffStepOnRoute { .. } } => {
                // Cannot happen with a single-step route, but handle for exhaustiveness.
                prop_assert!(false, "OffStep should not occur with a single-step route");
            }
            RouteDeviation::Deviation { kind: DeviationKind::CompletelyOffRoute { deviation_from_route_line } } => {
                prop_assert_eq!(
                    deviation_from_route_line,
                    deviation.unwrap()
                );
            }
        }
    }

    /// Tests [`RouteDeviationTracking::StaticThreshold`] behavior
    /// for values which are not accurate enough.
    #[test]
    fn static_threshold_ignores_inaccurate_location_updates(
        x1 in -180f64..=180f64, y1 in -90f64..=90f64,
        x2 in -180f64..=180f64, y2 in -90f64..=90f64,
        x3 in -180f64..=180f64, y3 in -90f64..=90f64,
        horizontal_accuracy in 1u16..,
        max_acceptable_deviation: f64,
    ) {
        let tracking = RouteDeviationTracking::StaticThreshold {
            minimum_horizontal_accuracy: horizontal_accuracy - 1,
            max_acceptable_deviation
        };
        let current_route_step = gen_dummy_route_step(x1, y1, x2, y2);
        let route = gen_route_from_steps(vec![current_route_step.clone()]);

        let coordinates = GeographicCoordinate {
            lng: x3,
            lat: y3,
        };
        let user_location_random = UserLocation {
            coordinates,
            horizontal_accuracy: horizontal_accuracy as f64,
            course_over_ground: None,
            timestamp: SystemTime::now(),
            speed: None
        };
        let trip_state_random = get_navigating_trip_state(
            user_location_random.clone(),
            vec![current_route_step.clone()],
            vec![],
            RouteDeviation::NoDeviation
        );
        prop_assert_eq!(
            tracking.check_route_deviation(&route, &trip_state_random),
            RouteDeviation::NoDeviation
        );
    }
}

#[cfg(test)]
mod off_step_tests {
    use super::*;
    use crate::models::GeographicCoordinate;
    use crate::navigation_controller::test_helpers::{gen_dummy_route_step, gen_route_from_steps};

    #[cfg(all(feature = "std", not(feature = "web-time")))]
    use std::time::SystemTime;

    #[cfg(feature = "web-time")]
    use web_time::SystemTime;

    fn make_location(lng: f64, lat: f64) -> UserLocation {
        UserLocation {
            coordinates: GeographicCoordinate { lng, lat },
            horizontal_accuracy: 5.0,
            course_over_ground: None,
            timestamp: SystemTime::now(),
            speed: None,
        }
    }

    #[test]
    fn test_off_step_detected_when_on_future_step() {
        // Route: Step 1 goes east, Step 2 goes north
        let step1 = gen_dummy_route_step(0.0, 0.0, 0.001, 0.0); // ~111m east
        let step2 = gen_dummy_route_step(0.001, 0.0, 0.001, 0.001); // ~111m north

        let route = gen_route_from_steps(vec![step1.clone(), step2.clone()]);
        let tracking = RouteDeviationTracking::StaticThreshold {
            minimum_horizontal_accuracy: 10,
            max_acceptable_deviation: 50.0,
        };

        // User is on step 2's geometry (far from step 1)
        let user_on_step2 = make_location(0.001, 0.0005);
        let trip_state = get_navigating_trip_state(
            user_on_step2,
            vec![step1.clone(), step2.clone()],
            vec![],
            RouteDeviation::NoDeviation,
        );

        let result = tracking.check_route_deviation(&route, &trip_state);
        assert!(
            matches!(
                result,
                RouteDeviation::Deviation {
                    kind: DeviationKind::OffStepOnRoute { .. }
                }
            ),
            "Should detect OffStep when user is on a future step, got: {result:?}"
        );
    }

    #[test]
    fn test_no_deviation_when_on_current_step() {
        let step1 = gen_dummy_route_step(0.0, 0.0, 0.001, 0.0);
        let step2 = gen_dummy_route_step(0.001, 0.0, 0.001, 0.001);

        let route = gen_route_from_steps(vec![step1.clone(), step2.clone()]);
        let tracking = RouteDeviationTracking::StaticThreshold {
            minimum_horizontal_accuracy: 10,
            max_acceptable_deviation: 50.0,
        };

        // User is on step 1's geometry
        let user_on_step1 = make_location(0.0005, 0.0);
        let trip_state = get_navigating_trip_state(
            user_on_step1,
            vec![step1, step2],
            vec![],
            RouteDeviation::NoDeviation,
        );

        let result = tracking.check_route_deviation(&route, &trip_state);
        assert_eq!(
            result,
            RouteDeviation::NoDeviation,
            "Should be NoDeviation when user is on current step"
        );
    }

    #[test]
    fn test_off_route_when_not_on_any_step() {
        let step1 = gen_dummy_route_step(0.0, 0.0, 0.001, 0.0);
        let step2 = gen_dummy_route_step(0.001, 0.0, 0.001, 0.001);

        let route = gen_route_from_steps(vec![step1.clone(), step2.clone()]);
        let tracking = RouteDeviationTracking::StaticThreshold {
            minimum_horizontal_accuracy: 10,
            max_acceptable_deviation: 50.0,
        };

        // User is far from both steps (~5.5km north)
        let user_off_route = make_location(0.0005, 0.05);
        let trip_state = get_navigating_trip_state(
            user_off_route,
            vec![step1, step2],
            vec![],
            RouteDeviation::NoDeviation,
        );

        let result = tracking.check_route_deviation(&route, &trip_state);
        assert!(
            matches!(
                result,
                RouteDeviation::Deviation {
                    kind: DeviationKind::CompletelyOffRoute { .. }
                }
            ),
            "Should be CompletelyOffRoute when user is not on any step, got: {result:?}"
        );
    }

    #[test]
    fn test_off_step_has_deviation_distance() {
        // Step 1 goes east, step 2 goes north — perpendicular
        let step1 = gen_dummy_route_step(0.0, 0.0, 0.001, 0.0); // ~111m east
        let step2 = gen_dummy_route_step(0.001, 0.0, 0.001, 0.002); // ~222m north

        let route = gen_route_from_steps(vec![step1.clone(), step2.clone()]);
        let tracking = RouteDeviationTracking::StaticThreshold {
            minimum_horizontal_accuracy: 10,
            max_acceptable_deviation: 50.0,
        };

        // User is clearly on step 2's geometry, far from step 1
        // (~111m north of step 1's end, on step 2's line)
        let user_on_step2 = make_location(0.001, 0.001);
        let trip_state = get_navigating_trip_state(
            user_on_step2,
            vec![step1, step2],
            vec![],
            RouteDeviation::NoDeviation,
        );

        let result = tracking.check_route_deviation(&route, &trip_state);
        match result {
            RouteDeviation::Deviation {
                kind:
                    DeviationKind::OffStepOnRoute {
                        deviation_from_step_line,
                    },
            } => {
                assert!(
                    deviation_from_step_line > 0.0,
                    "OffStep should have a positive deviation distance"
                );
            }
            _ => panic!("Expected OffStep, got: {result:?}"),
        }
    }
}