Skip to main content

hopr_transport/path/
planner.rs

1use std::{collections::HashSet, sync::Arc, time::Duration};
2
3use futures::{StreamExt as _, TryStreamExt, stream::FuturesUnordered};
4#[cfg(all(feature = "telemetry", not(test)))]
5use hopr_api::types::internal::path::Path;
6use hopr_api::{
7    OffchainPublicKey,
8    chain::{ChainKeyOperations, ChainPathResolver, ChainReadChannelOperations},
9    types::{
10        crypto::crypto_traits::Randomizable,
11        internal::{errors::PathError, prelude::*},
12        primitive::traits::ToHex,
13    },
14};
15use hopr_crypto_packet::prelude::*;
16use hopr_protocol_hopr::{FoundSurb, SurbStore};
17use parking_lot::Mutex;
18use tracing::Instrument;
19use validator::{Validate, ValidationError};
20
21use super::{
22    errors::{PathPlannerError, Result},
23    traits::{BackgroundPathCacheRefreshable, PathSelector, PathWithMetrics},
24};
25use crate::observer::{PathDirection, TransportEvent, TransportObserver};
26
27#[cfg(all(feature = "telemetry", not(test)))]
28lazy_static::lazy_static! {
29    static ref METRIC_PATH_LENGTH: hopr_api::types::telemetry::SimpleHistogram = hopr_api::types::telemetry::SimpleHistogram::new(
30        "hopr_path_length",
31        "Distribution of number of hops of sent messages",
32        vec![0.0, 1.0, 2.0, 3.0, 4.0]
33    ).unwrap();
34}
35
36/// Rejects a temper exponent outside `(0, 1]`.
37///
38/// `w^γ` is only a flattening of the weights for `γ ∈ (0, 1]`.
39///
40/// `γ > 1` would sharpen instead — concentrating harder than raw path value, the opposite of the
41/// knob's purpose — and `γ <= 0` inverts or annihilates the ordering, sending traffic *preferentially*
42/// to the worst relays. Both are almost certainly typos, so refuse them rather than silently
43/// degrade every return path the node builds.
44fn validate_weight_temper(temper: f64) -> std::result::Result<(), ValidationError> {
45    if temper > 0.0 && temper <= 1.0 {
46        return Ok(());
47    }
48    let mut err = ValidationError::new("weight_temper_out_of_range");
49    err.message = Some(
50        format!(
51            "return_path_weight_temper ({temper}) must be in (0, 1]: 1.0 samples by raw path value, smaller values \
52             flatten towards uniform"
53        )
54        .into(),
55    );
56    Err(err)
57}
58
59/// Configuration for [`PathPlanner`]'s internal path cache.
60#[derive(Debug, Clone, Copy, PartialEq, smart_default::SmartDefault, Validate)]
61#[cfg_attr(
62    feature = "serde",
63    derive(serde::Serialize, serde::Deserialize),
64    serde(default, deny_unknown_fields)
65)]
66#[validate(schema(function = "validate_refresh_within_ttl", skip_on_field_errors = false))]
67pub struct PathPlannerConfig {
68    /// Maximum number of `(source, destination, options)` entries in the path cache.
69    #[default = 10_000]
70    pub max_cache_capacity: u64,
71    /// Time-to-live for a cached path list.  When an entry expires the next
72    /// [`PathPlanner::resolve_routing`] call transparently recomputes it (lazy refresh).
73    ///
74    /// Candidate weights are computed once, when the entry is filled, and frozen in the
75    /// [`hopr_utils::statistics::WeightedCollection`] -- so this bounds how stale the *weights* a
76    /// live session draws from can be, not merely how stale the candidate set is. At the previous
77    /// 60 s a relay that stopped delivering kept its full share of return-path draws for a minute
78    /// after the graph had already scored it down.
79    #[default(Duration::from_secs(10))]
80    #[cfg_attr(feature = "serde", serde(with = "humantime_serde"))]
81    pub cache_ttl: Duration,
82    /// Period between proactive background cache-refresh sweeps.
83    ///
84    /// Held at half the TTL so a steady-state session is normally served from an entry that was
85    /// re-weighted rather than one that expired under it.
86    #[default(Duration::from_secs(5))]
87    #[cfg_attr(feature = "serde", serde(with = "humantime_serde"))]
88    #[validate(custom(function = "validate_refresh_period"))]
89    pub refresh_period: Duration,
90    /// Maximum number of candidate paths the selector may return per query.
91    /// All returned candidates are validated and cached.
92    /// Must be at least 1: a zero limit leaves the selector unable to return any multi-hop path.
93    #[default = 50]
94    #[validate(range(min = 1))]
95    pub max_cached_paths: usize,
96    /// Penalty multiplier for edges lacking probe-based quality observations.
97    /// Applied during path cost evaluation to down-weight unprobed edges.
98    /// Must be finite and in `0.0..=1.0`.
99    #[default = 0.5]
100    #[validate(custom(function = "validate_unit_interval"))]
101    pub edge_penalty: f64,
102    /// Minimum acceptable message acknowledgment rate for path selection.
103    /// Edges with an ack rate below this threshold are excluded from candidate paths.
104    /// Must be finite and in `0.0..=1.0`.
105    #[default = 0.1]
106    #[validate(custom(function = "validate_unit_interval"))]
107    pub min_ack_rate: f64,
108    /// Candidate count below which no latency-based pruning occurs.
109    ///
110    /// When fewer paths than this value are found, the selector returns all of them
111    /// unchanged (`min(found_count, floor)` semantics — the floor is never a minimum
112    /// to fabricate).  Set to 0 to disable pruning entirely.
113    #[default = 8]
114    pub min_paths_anonymity_floor: usize,
115    /// Total path latency at which the latency factor in the composite weight equals 0.5.
116    /// Higher values make the weight less sensitive to latency differences.
117    #[default(Duration::from_millis(100))]
118    #[cfg_attr(feature = "serde", serde(with = "humantime_serde"))]
119    pub latency_halflife: Duration,
120    /// Reference channel balance used to scale the capacity factor in the composite weight.
121    /// `capacity_factor` saturates at 1.0 near this value.
122    /// Defaults to 10_000_000 (~10 MiB in wxHOPR tokens).
123    #[default = 10_000_000]
124    pub capacity_reference: u128,
125    /// Exponent applied to path weights before sampling, flattening the distribution. Despite the
126    /// name it applies to forward draws as well as to return draws (the name is kept for
127    /// configuration compatibility).
128    ///
129    /// Paths are drawn weighted-random by path value, which concentrates a session's SURBs, and its
130    /// forward packets, on the few highest-valued relays — losing one then costs far more than the
131    /// reliable-mode loss tolerance, and a forward path that collapses on one relayer goes dark
132    /// with it. Raising each weight to `γ ∈ (0, 1]` compresses the spread between good and bad
133    /// candidates without changing their order: `w' = w^γ`.
134    ///
135    /// `1.0` samples by raw path value (most traffic on the best relays, largest blast radius when
136    /// one dies). Values approaching `0.0` tend to a uniform draw (smallest blast radius, most
137    /// traffic on poor relays). With weights `(0.4, 0.3, 0.2, 0.1)`, `γ = 0.5` moves the busiest
138    /// relay's share from 40% to 33% and the ratio between busiest and least-busy from 4.0 to 2.0.
139    ///
140    /// Defaults to 0.5.
141    #[validate(custom(function = "validate_weight_temper"))]
142    #[default = 0.5]
143    pub return_path_weight_temper: f64,
144    /// Fraction of path draws, forward and return, made uniformly at random instead of by weight
145    /// (the name is kept for configuration compatibility).
146    ///
147    /// Weights come from observations, and observations only exist for paths that get selected — a
148    /// closed loop in which a path that falls out of favour stops being measured, so its score can
149    /// never recover and it is never chosen again. Spending a small share of draws uniformly keeps
150    /// the plausible candidates under observation, which is what lets a recovered one climb back.
151    ///
152    /// Plausible means a tempered weight of at least a tenth of the best candidate's. That leaves out
153    /// a relayer on probation and an edge probes measured dead, and also a healthy path slow or thin
154    /// enough to weigh less than a tenth. An exploring return draw takes one of those only within a
155    /// node-wide allowance of one a second, while an ordinary return draw keeps it at its tempered
156    /// weight: a reply through a relayer on probation is what revives it. A forward draw, exploring or
157    /// not, never takes one, as a forward packet probes nothing.
158    ///
159    /// Costs throughput in proportion: this share of draws, forward and return, deliberately ignores
160    /// which plausible candidate looks best. Candidates have already passed the selector's gates
161    /// (open channels, `min_ack_rate`, and so on) before reaching here, so an exploratory draw never
162    /// takes a route the cost function rejected. `0.0` disables it. Defaults to 0.1.
163    #[validate(custom(function = "validate_unit_interval"))]
164    #[default = 0.1]
165    pub return_path_exploration: f64,
166    /// Upper bound on a loopback probe's round-trip time considered plausible.
167    /// Measurements above this cap (clock skew, stale telemetry) are discarded
168    /// instead of poisoning the latency EMA with an absurd value.
169    #[default(Duration::from_secs(30))]
170    #[cfg_attr(feature = "serde", serde(with = "humantime_serde"))]
171    pub max_plausible_loopback_rtt: Duration,
172    /// Loops over an edge from which the share that returned, not a single returned loop, decides whether
173    /// its relay delivers (handed to the graph through `ChannelGraph::with_starvation`). Below it, one returned loop
174    /// keeps the relay and none starves it. Few loops cross an edge in a sparse network, so this stays small.
175    #[default = 3]
176    #[validate(range(min = 1))]
177    pub min_loopbacks_for_rate: u32,
178    /// Share of loops over an edge that must return, once there are `min_loopbacks_for_rate` of them, for
179    /// its relay to stay routable. A relay dropping what it should forward still returns the odd loop, so
180    /// this is never zero. In `(0.0, 1.0]`.
181    #[default = 0.1]
182    #[validate(custom(function = "validate_loopback_return_rate"))]
183    pub min_loopback_return_rate: f64,
184}
185
186/// Shortest accepted `refresh_period`. A zero period makes the sweep loop rebuild every cached
187/// multi-hop path back to back, keeping the selector and resolver continuously busy.
188const MIN_REFRESH_PERIOD: Duration = Duration::from_secs(1);
189
190fn validate_refresh_period(period: &Duration) -> std::result::Result<(), ValidationError> {
191    if *period >= MIN_REFRESH_PERIOD {
192        return Ok(());
193    }
194    let mut err = ValidationError::new("refresh_period_too_short");
195    err.message = Some(format!("refresh_period ({period:?}) must be at least {MIN_REFRESH_PERIOD:?}").into());
196    Err(err)
197}
198
199/// A sweep that runs less often than entries expire never reaches them: the sweep walks live entries
200/// only, so an expired one is refilled on demand, and a refill that finds no paths is `PathNotFound`
201/// where a refreshed entry would have kept its previous weights.
202fn validate_refresh_within_ttl(cfg: &PathPlannerConfig) -> std::result::Result<(), ValidationError> {
203    if cfg.refresh_period < cfg.cache_ttl {
204        return Ok(());
205    }
206    let mut err = ValidationError::new("refresh_period_not_below_cache_ttl");
207    err.message = Some(
208        format!(
209            "refresh_period ({:?}) must be shorter than cache_ttl ({:?})",
210            cfg.refresh_period, cfg.cache_ttl
211        )
212        .into(),
213    );
214    Err(err)
215}
216
217/// A share of loops that must return, in `(0.0, 1.0]`: zero is met by any relay returning the odd loop, which
218/// is what a dropping relay does, so it would never starve one.
219fn validate_loopback_return_rate(value: f64) -> std::result::Result<(), ValidationError> {
220    if value.is_finite() && value > 0.0 && value <= 1.0 {
221        Ok(())
222    } else {
223        Err(ValidationError::new("value must be finite and in (0.0, 1.0]"))
224    }
225}
226
227fn validate_unit_interval(value: f64) -> std::result::Result<(), ValidationError> {
228    if value.is_finite() && (0.0..=1.0).contains(&value) {
229        Ok(())
230    } else {
231        Err(ValidationError::new("value must be finite and in 0.0..=1.0"))
232    }
233}
234
235/// Parameters that shape how per-path aggregates modulate the `WeightedCollection` weight.
236#[derive(Debug, Clone, Copy)]
237struct WeightingParams {
238    latency_halflife: Duration,
239    capacity_reference: u128,
240    return_path_weight_temper: f64,
241    return_path_exploration: f64,
242}
243
244/// Continuous, monotonically decreasing latency factor, bounded in (0, 1].
245///
246/// Returns 1.0 for zero latency and 0.5 when `latency == halflife`.
247fn latency_factor(latency: Duration, halflife: Duration) -> f64 {
248    let ms = latency.as_millis() as f64;
249    let h = halflife.as_millis().max(1) as f64;
250    1.0 / (1.0 + ms / h)
251}
252
253/// Continuous, monotonically increasing capacity factor, bounded in (0.05, 1.0].
254///
255/// Uses a log scale because channel balances span many orders of magnitude.
256/// Saturates at 1.0 near `reference`.
257fn capacity_factor(c: u128, reference: u128) -> f64 {
258    let log = (c as f64).max(1.0).log10();
259    let ref_log = (reference as f64).max(10.0).log10();
260    (log / ref_log).clamp(0.05, 1.0)
261}
262
263/// Composite selection weight for a candidate path.
264///
265/// Refines `pwc.cost` (the `EdgeValueFn` output) with latency and capacity factors
266/// derived from the per-path aggregates.  Factors are neutral (1.0) when the
267/// corresponding aggregate is unavailable to avoid penalising unprobed paths.
268/// For 0-hop routes (`hops == 0`) the capacity factor is always 1.0 — direct
269/// `me -> dest` packets use no payment channel, so `fundable_tickets_floor = None` is expected.
270fn composite_weight(pwc: &PathWithMetrics, hops: usize, params: WeightingParams) -> f64 {
271    let lat = pwc
272        .total_latency_ms
273        .map(|ms| latency_factor(Duration::from_millis(ms as u64), params.latency_halflife))
274        .unwrap_or(1.0);
275    let cap = if hops == 0 {
276        1.0
277    } else {
278        pwc.fundable_tickets_floor
279            .map(|c| capacity_factor(c, params.capacity_reference))
280            .unwrap_or(1.0)
281    };
282    pwc.cost * lat * cap
283}
284
285/// The weight a candidate is drawn by, as the walk valued it, tempered to spread the draws over
286/// relayers (see [`PathPlannerConfig::return_path_weight_temper`]), relayer health included.
287///
288/// Forward and return paths alike: an untempered forward draw put most of a session's packets on
289/// its single best path, and with the candidate prune diversifying first relayers only, on one
290/// middle relayer, whose death then took the whole forward direction with it (see
291/// `selector::MIDDLE_HOP_SHARE`).
292fn selection_weight(pwc: &PathWithMetrics, hops: usize, params: WeightingParams) -> f64 {
293    temper_weights(&[composite_weight(pwc, hops, params)], params.return_path_weight_temper)[0]
294}
295
296/// Picks an index into `weights` with probability proportional to the weight; `None` if all are
297/// non-positive.
298///
299/// Mirrors `WeightedCollection::pick_index`, which cannot be reused because the callers below
300/// select over *subsets* of a single collection.
301fn pick_weighted_index(weights: &[f64]) -> Option<usize> {
302    let total: f64 = weights.iter().map(|w| w.max(0.0)).sum();
303    if total <= 0.0 {
304        return None;
305    }
306
307    // Path selection is privacy-relevant, so draw from the CSPRNG rather than a thread RNG.
308    let r = hopr_api::types::crypto_random::random_float_in_range(0.0..total);
309    let mut cumulative = 0.0;
310    for (i, w) in weights.iter().enumerate() {
311        cumulative += w.max(0.0);
312        if r < cumulative {
313            return Some(i);
314        }
315    }
316
317    // Floating-point edge case: fall back to the last positive-weight entry.
318    weights.iter().rposition(|w| *w > 0.0)
319}
320
321/// Whether this draw should explore — ignore the weights and pick uniformly among the plausible
322/// candidates (see [`pick_exploring_index`]).
323///
324/// Weights are derived from observations, and observations only exist for paths that were selected.
325/// Left alone that is a closed loop: a path that falls out of favour stops being measured, so its
326/// score can never recover and it is never chosen again. Spending a small share of draws uniformly
327/// keeps the plausible candidates under observation, which is what lets one that has recovered climb
328/// back. An exploring draw takes a candidate below [`PLAUSIBLE_WEIGHT_FRACTION`] only as a return draw
329/// the [`ProbeBudget`] grants.
330fn should_explore(exploration: f64) -> bool {
331    exploration > 0.0 && hopr_api::types::crypto_random::random_float_in_range(0.0..1.0) < exploration
332}
333
334/// Picks a uniformly random index over `len` entries.
335fn pick_uniform_index(len: usize) -> Option<usize> {
336    (len > 0).then(|| (hopr_api::types::crypto_random::random_float_in_range(0.0..len as f64) as usize).min(len - 1))
337}
338
339/// The fraction of the best candidate's (tempered) weight below which a candidate is one the cost
340/// function all but rejects.
341///
342/// A relayer on probation is published at a health of a thousandth and an edge probes measured dead
343/// is floored at a billionth: tempered, they sit at about 3 % and 0.003 % of a healthy candidate. A
344/// stalled relayer still delivering at a hundredth of its health is at 10 %, and stays explorable.
345///
346/// Those figures are for the default `return_path_weight_temper` of 0.5. A weight tempered by `t`
347/// puts a relayer on probation at `0.001^t` of a healthy one, so a temper of 1/3 or less lifts it to
348/// this fraction or above: exploration then counts it as plausible, forward draws among them, and
349/// the probe budget no longer holds it back. Whoever lowers the temper that far trades this gate for
350/// the wider spread.
351const PLAUSIBLE_WEIGHT_FRACTION: f64 = 0.1;
352
353/// How often an exploring return draw may pick a candidate below [`PLAUSIBLE_WEIGHT_FRACTION`],
354/// node-wide.
355///
356/// That draw is the probe a relayer on probation is revived by, so it cannot be ruled out, but every
357/// one through a relayer that is really gone is a SURB lost at the counterparty — its PIX share with
358/// it — and each one is written off and replaced. Uniform exploration made a tenth of all draws such
359/// a probe whenever one candidate was implausible: 26 per second at production dimensions, and with
360/// them a few percent of the counterparty's stock dead, enough for a single lost control message to
361/// close a PIX Session. One a second is enough to notice a revival.
362const IMPLAUSIBLE_PROBE_INTERVAL: Duration = Duration::from_secs(1);
363
364/// The node-wide allowance of [`IMPLAUSIBLE_PROBE_INTERVAL`].
365#[derive(Debug)]
366struct ProbeBudget {
367    epoch: std::time::Instant,
368    /// Milliseconds since `epoch` of the last probe granted, plus one so that `0` is "none yet".
369    last_ms_plus_one: std::sync::atomic::AtomicU64,
370}
371
372impl Default for ProbeBudget {
373    fn default() -> Self {
374        Self {
375            epoch: std::time::Instant::now(),
376            last_ms_plus_one: std::sync::atomic::AtomicU64::new(0),
377        }
378    }
379}
380
381impl ProbeBudget {
382    /// Grants a probe if none was granted within [`IMPLAUSIBLE_PROBE_INTERVAL`].
383    fn take(&self) -> bool {
384        let now = u64::try_from(self.epoch.elapsed().as_millis())
385            .unwrap_or(u64::MAX - 1)
386            .saturating_add(1);
387        let interval = u64::try_from(IMPLAUSIBLE_PROBE_INTERVAL.as_millis()).unwrap_or(u64::MAX);
388        self.last_ms_plus_one
389            .fetch_update(
390                std::sync::atomic::Ordering::Relaxed,
391                std::sync::atomic::Ordering::Relaxed,
392                |last| (last == 0 || now.saturating_sub(last) >= interval).then_some(now),
393            )
394            .is_ok()
395    }
396}
397
398/// An exploring draw: uniform over the candidates whose weight is at least
399/// [`PLAUSIBLE_WEIGHT_FRACTION`] of the best, and over the others only when `allow_implausible`
400/// grants it (it is asked only when the draw lands on one).
401///
402/// Uniform over the plausible ones whatever is granted: a draw that lands on an implausible candidate
403/// it may not take is redrawn among the plausible ones.
404fn pick_exploring_index(weights: &[f64], allow_implausible: impl FnOnce() -> bool) -> Option<usize> {
405    let best = weights.iter().copied().fold(0.0, f64::max);
406    if best <= 0.0 {
407        return None;
408    }
409    let floor = best * PLAUSIBLE_WEIGHT_FRACTION;
410    let drawn = pick_uniform_index(weights.len())?;
411    if weights[drawn] >= floor || allow_implausible() {
412        return Some(drawn);
413    }
414    let plausible: Vec<usize> = (0..weights.len()).filter(|&i| weights[i] >= floor).collect();
415    pick_uniform_index(plausible.len()).map(|i| plausible[i])
416}
417
418/// Zeroes every weight below [`PLAUSIBLE_WEIGHT_FRACTION`] of the best, so that a weighted draw over
419/// `weights` never lands on a candidate the weights all but reject.
420///
421/// For ordinary forward draws. A return draw keeps such a candidate at its tempered weight, because a
422/// reply through it is what can end a relayer's probation. A forward packet probes nothing, so on such
423/// a candidate all it can do is be lost.
424fn gate_implausible(weights: &mut [f64]) {
425    let floor = weights.iter().copied().fold(0.0, f64::max) * PLAUSIBLE_WEIGHT_FRACTION;
426    for weight in weights.iter_mut().filter(|weight| **weight < floor) {
427        *weight = 0.0;
428    }
429}
430
431/// Flattens `weights` by raising each to `temper`, compressing the spread between good and bad
432/// candidates without reordering them.
433///
434/// `x^γ` is monotone for `γ > 0`, so the best candidate stays the best — only the *ratio* between
435/// them shrinks, which is what bounds how much of a session rides on any single relayer. Weights
436/// are clamped at zero first: a negative weight would make `powf` return NaN and poison the draw.
437fn temper_weights(weights: &[f64], temper: f64) -> Vec<f64> {
438    weights.iter().map(|w| w.max(0.0).powf(temper)).collect()
439}
440
441/// What a rebuild observed about return-path relayer diversity for its key.
442///
443/// Returned by [`PathBuilder::rebuild`] rather than acted on inside it, so the caller applies the
444/// transition to the shared tracker only once the rebuilt path actually reaches the cache. A
445/// background refresh whose stale path is rejected by `put_if_unchanged` must not move the tracker
446/// or log a recovery (issue #8502).
447struct DiversityObservation {
448    key: PlannerCacheKey,
449    collapsed: bool,
450    distinct_relayers: usize,
451    candidates: usize,
452}
453
454/// Records a diversity transition and logs it once: a WARN when a key first collapses to a single
455/// relayer, an INFO when it first recovers. Idempotent across repeated rebuilds of the same state,
456/// so the WARN fires on the transition, not on every rebuild.
457fn apply_diversity_transition(
458    collapsed_diversity: &Mutex<HashSet<PlannerCacheKey>>,
459    src_key: &OffchainPublicKey,
460    kind: &str,
461    obs: &DiversityObservation,
462) {
463    let mut collapsed = collapsed_diversity.lock();
464    if obs.collapsed {
465        if collapsed.insert(obs.key) {
466            tracing::warn!(
467                src = %src_key,
468                kind,
469                distinct_relayers = obs.distinct_relayers,
470                candidates = obs.candidates,
471                "return-path relayer diversity collapsed to a single relayer",
472            );
473        }
474    } else if collapsed.remove(&obs.key) {
475        tracing::info!(
476            src = %src_key,
477            kind,
478            distinct_relayers = obs.distinct_relayers,
479            candidates = obs.candidates,
480            "return-path relayer diversity recovered for this destination",
481        );
482    }
483}
484
485type RebuiltPaths = (CandidateSet, Option<DiversityObservation>);
486
487/// What a cache entry is rebuilt from, shared by the planner and its background sweep.
488#[derive(Clone)]
489struct PathBuilder<R, S> {
490    resolver: R,
491    selector: S,
492    weighting: WeightingParams,
493    me: OffchainPublicKey,
494    /// Keys currently in the collapsed return-path diversity state, so the WARN fires once on the
495    /// transition into it (and an INFO once on recovery) rather than on every rebuild (#8502).
496    collapsed_diversity: Arc<Mutex<HashSet<PlannerCacheKey>>>,
497}
498
499impl<R, S> PathBuilder<R, S>
500where
501    R: ChainKeyOperations + ChainReadChannelOperations + Send + Sync,
502    S: PathSelector,
503{
504    /// Rebuilds the weighted candidate collection for one `(source, destination, hops)` triple from
505    /// whatever the graph currently says.
506    ///
507    /// Shared by the lazy cache fill, the background sweep and the on-demand recompute, so all three
508    /// necessarily agree: a divergence here would make a session's weights depend on which of the three
509    /// happened to run last.
510    ///
511    /// `Ok(None)` means the selector offered nothing, or nothing survived validation. Callers decide
512    /// what that means — a fill turns it into `PathNotFound`, a refresh drops the existing entry.
513    /// `Err` is reserved for a selector that actually failed.
514    #[tracing::instrument(name = "planner.rebuild_candidates", level = "trace", skip_all)]
515    async fn rebuild(
516        &self,
517        src_key: OffchainPublicKey,
518        dest_key: OffchainPublicKey,
519        hops: usize,
520        kind: &'static str,
521    ) -> Result<Option<RebuiltPaths>> {
522        let (resolver, weighting, me) = (&self.resolver, self.weighting, self.me);
523        // Dead relayers are pruned by the traversal itself, and stalled ones cost less there: the SURB
524        // telemetry records their health in the graph.
525        let candidates = self.selector.select_path(src_key, dest_key, hops)?;
526        let discovered = candidates.len();
527
528        let chain_resolver = ChainPathResolver::from(resolver);
529        let mut valid_paths: Vec<(ValidatedPath, f64)> = Vec::with_capacity(candidates.len());
530        let mut path_metrics: Vec<PathWithMetrics> = Vec::with_capacity(candidates.len());
531        for pwc in candidates {
532            // Cloned, not taken: `distinct_first_relayers` below needs the path intact (#8502).
533            let node_ids: Vec<NodeId> = pwc.path.iter().cloned().map(NodeId::Offchain).collect::<Vec<_>>();
534            match ValidatedPath::new(NodeId::Offchain(src_key), node_ids, &chain_resolver).await {
535                Ok(vp) => {
536                    // Return paths are planned from the destination back to us.
537                    valid_paths.push((vp, selection_weight(&pwc, hops, weighting)));
538                    path_metrics.push(pwc);
539                }
540                Err(e) => tracing::debug!(kind, error = %e, "path candidate failed validation"),
541            }
542        }
543
544        // A return path that resolves to a single first relayer puts every SURB of the destination
545        // behind it. Checked after validation: only the survivors reflect what a session can draw.
546        let diversity = (src_key != me && hops > 0 && !path_metrics.is_empty()).then(|| {
547            let distinct_relayers = super::selector::distinct_first_relayers(&path_metrics);
548            DiversityObservation {
549                key: (src_key, dest_key, hops as u32),
550                collapsed: distinct_relayers <= 1,
551                distinct_relayers,
552                candidates: path_metrics.len(),
553            }
554        });
555
556        tracing::debug!(
557            discovered,
558            validated = valid_paths.len(),
559            rejected = discovered - valid_paths.len(),
560            outcome = if discovered == 0 {
561                "no paths discovered"
562            } else if valid_paths.is_empty() {
563                "no valid paths"
564            } else {
565                "completed"
566            },
567            "candidate validation"
568        );
569        if valid_paths.is_empty() {
570            return Ok(None);
571        }
572
573        let (set_id, weighted) = identify_candidates(hopr_utils::statistics::WeightedCollection::new(valid_paths));
574        let total_wt = weighted.total_weight();
575        // Cache rebuilds are the useful DEBUG boundary; per-draw details remain at TRACE.
576        if tracing::enabled!(tracing::Level::DEBUG) {
577            const MAX_LOGGED_CANDIDATES: usize = 8;
578            let candidates = weighted
579                .iter()
580                .take(MAX_LOGGED_CANDIDATES)
581                .map(|(path, weight)| (path.to_string(), *weight))
582                .collect::<Vec<_>>();
583            tracing::debug!(
584                kind,
585                source = %src_key,
586                destination = %dest_key,
587                hops,
588                total_weight = total_wt,
589                candidate_count = weighted.len(),
590                omitted = weighted.len().saturating_sub(MAX_LOGGED_CANDIDATES),
591                ?candidates,
592                "rebuilt weighted path collection",
593            );
594        }
595        // Return draws spend `exploration` of their picks uniformly, so log what a draw actually does.
596        let exploration = if dest_key == me {
597            weighting.return_path_exploration
598        } else {
599            0.0
600        };
601        let candidates = weighted.iter().count() as f64;
602        for (index, ((vp, w), pwm)) in weighted.iter().zip(path_metrics.iter()).enumerate() {
603            tracing::trace!(
604                kind,
605                set_id,
606                index,
607                destination = %dest_key,
608                hops,
609                path = %vp,
610                cost = pwm.cost,
611                selection_weight = w,
612                sampling_probability = if total_wt > 0.0 {
613                    (1.0 - exploration) * w.max(0.0) / total_wt + exploration / candidates
614                } else {
615                    0.0
616                },
617                total_latency_ms = ?pwm.total_latency_ms,
618                min_probe_success_rate = ?pwm.min_probe_success_rate,
619                min_ack_rate = ?pwm.min_ack_rate,
620                fundable_tickets_floor = ?pwm.fundable_tickets_floor,
621                "weighted candidate path",
622            );
623        }
624        Ok(Some(((set_id, weighted), diversity)))
625    }
626
627    fn apply_diversity(&self, kind: &str, diversity: Option<DiversityObservation>) {
628        if let Some(obs) = diversity {
629            apply_diversity_transition(&self.collapsed_diversity, &obs.key.0, kind, &obs);
630        }
631    }
632}
633
634/// Smallest change in a candidate's share of the draws that counts as traffic having moved.
635///
636/// Weights are recomputed from live observations, so they jitter constantly without meaning
637/// anything. One percentage point of a candidate's share is well below the shift a relayer going
638/// silent produces (measured: 33% to near zero) and well above the noise of an idle graph.
639const MIN_SHARE_SHIFT: f64 = 0.01;
640
641/// Each candidate's share of the total weight, keyed by the route it takes.
642fn shares_by_route(paths: &hopr_utils::statistics::WeightedCollection<ValidatedPath>) -> Vec<(String, f64)> {
643    let total: f64 = paths.iter().map(|(_, w)| w.max(0.0)).sum();
644    paths
645        .iter()
646        .map(|(vp, w)| {
647            let share = if total > 0.0 { w.max(0.0) / total } else { 0.0 };
648            (vp.to_string(), share)
649        })
650        .collect()
651}
652
653/// Whether re-weighting would send a materially different share of the draws somewhere else.
654///
655/// Shares rather than raw weights, because the draw normalises over the collection: every weight
656/// halving changes nothing about where traffic goes. Callers use this to decide whether a re-plan
657/// achieved anything, and a re-plan that moved nothing is a reason *not* to act on it -- so
658/// answering "yes" by default would defeat the check it exists for.
659fn weights_moved(
660    before: &hopr_utils::statistics::WeightedCollection<ValidatedPath>,
661    after: &hopr_utils::statistics::WeightedCollection<ValidatedPath>,
662) -> bool {
663    let (before, after) = (shares_by_route(before), shares_by_route(after));
664    if before.len() != after.len() {
665        return true;
666    }
667    before.iter().any(|(route, was)| {
668        // A route that vanished has lost its whole share, which is the largest move there is.
669        after
670            .iter()
671            .find(|(other, _)| other == route)
672            .is_none_or(|(_, now)| (now - was).abs() >= MIN_SHARE_SHIFT)
673    })
674}
675
676/// Cache key for the path planner: `(source, destination, hops)`.
677///
678/// Only the `Hops` variant of [`RoutingOptions`] is cached (explicit intermediate
679/// paths bypass the cache), so the key stores the hop count as a plain `u32`.
680///
681/// Keyed on resolved offchain keys rather than [`NodeId`], because a `NodeId` naming a node by its
682/// chain address is never equal to one naming the same node by its packet key. Callers hold
683/// whichever form their layer happens to use -- Sessions carry chain addresses, the SURB telemetry
684/// reports packet keys -- so a raw-`NodeId` key silently stores the same route twice. Resolving
685/// first makes lookup and insertion agree by construction.
686type PlannerCacheKey = (OffchainPublicKey, OffchainPublicKey, u32);
687/// A dictionary key paired with the immutable collection it identifies. IDs do not order cache
688/// updates: pointer equality below remains the authority for rejecting stale refreshes.
689type CandidateSet = (u64, hopr_utils::statistics::WeightedCollection<ValidatedPath>);
690type PlannerCacheValue = Arc<CandidateSet>;
691
692/// Gives every rebuilt collection a new process-local ID before any dictionary records are emitted.
693/// All production rebuilds and test-created replacements use this constructor; cache hits reuse the
694/// pair through its Arc. The counter is shared across planners to keep their logs unambiguous.
695fn identify_candidates(paths: hopr_utils::statistics::WeightedCollection<ValidatedPath>) -> CandidateSet {
696    static NEXT_ID: std::sync::atomic::AtomicU64 = std::sync::atomic::AtomicU64::new(1);
697    (NEXT_ID.fetch_add(1, std::sync::atomic::Ordering::Relaxed), paths)
698}
699
700/// Writes `value` under `key` only if `swept` is still the entry cached there, returning whether it
701/// was.
702///
703/// The background refresh reads an entry, rebuilds it from the graph across awaits, then writes. A
704/// [`PathPlanner::recompute_paths_from`] that ran in between built from newer SURB evidence, so the
705/// refresh's older selection must not land on top of it. The check and the write are one
706/// `and_compute_with`, which moka serialises against every other compute call on the key, and the
707/// recompute writes through one too — a plain insert would otherwise slip between this read and write.
708/// A key that went vacant meanwhile is left to the next fill.
709async fn put_if_unchanged(
710    cache: &moka::future::Cache<PlannerCacheKey, PlannerCacheValue>,
711    key: PlannerCacheKey,
712    swept: &PlannerCacheValue,
713    value: PlannerCacheValue,
714) -> bool {
715    let written = cache
716        .entry(key)
717        .and_compute_with(|current| {
718            futures::future::ready(match current {
719                Some(current) if Arc::ptr_eq(current.value(), swept) => moka::ops::compute::Op::Put(value),
720                _ => moka::ops::compute::Op::Nop,
721            })
722        })
723        .await;
724    if let moka::ops::compute::CompResult::ReplacedWith(entry) = written {
725        tracing::debug!(
726            source = %key.0,
727            destination = %key.1,
728            hops = key.2,
729            candidates = entry.value().1.len(),
730            set_id = entry.value().0,
731            kind = "background-refresh",
732            "candidate set installed"
733        );
734        true
735    } else {
736        false
737    }
738}
739
740async fn drop_if_unchanged(
741    cache: &moka::future::Cache<PlannerCacheKey, PlannerCacheValue>,
742    key: PlannerCacheKey,
743    swept: &PlannerCacheValue,
744) {
745    cache
746        .entry(key)
747        .and_compute_with(|current| {
748            futures::future::ready(match current {
749                Some(current) if Arc::ptr_eq(current.value(), swept) => moka::ops::compute::Op::Remove,
750                _ => moka::ops::compute::Op::Nop,
751            })
752        })
753        .await;
754}
755
756impl<R, S> PathBuilder<R, S>
757where
758    R: ChainKeyOperations + ChainReadChannelOperations + Send + Sync,
759    S: PathSelector,
760{
761    /// Rebuilds every cached multi-hop entry from the current graph, one pass of the background sweep.
762    async fn sweep(&self, cache: &moka::future::Cache<PlannerCacheKey, PlannerCacheValue>) {
763        for (key, swept) in cache.iter() {
764            let (src_key, dest_key, hops_u32) = *key.as_ref();
765            if hops_u32 == 0 {
766                continue;
767            }
768
769            let rebuilt = self
770                .rebuild(src_key, dest_key, hops_u32 as usize, "background-refresh")
771                .await;
772            // Only if this is still the entry the sweep read: a `recompute_paths_from` that ran
773            // during the rebuild built from newer evidence, and its route must not be overwritten.
774            match rebuilt {
775                Ok(Some((weighted, diversity))) => {
776                    // A rejected stale refresh must not move the diversity tracker (#8502).
777                    if put_if_unchanged(cache, (src_key, dest_key, hops_u32), &swept, Arc::new(weighted)).await {
778                        self.apply_diversity("background-refresh", diversity);
779                    }
780                }
781                // No route left, e.g. every candidate runs through a dead relayer: serving the old one
782                // would keep drawing it.
783                Ok(None) | Err(PathPlannerError::Path(PathError::PathNotFound(..))) => {
784                    drop_if_unchanged(cache, (src_key, dest_key, hops_u32), &swept).await
785                }
786                Err(error) => tracing::debug!(%error, "background refresh failed, keeping the cached paths"),
787            }
788        }
789    }
790}
791
792/// Path planner that resolves [`DestinationRouting`] to [`ResolvedTransportRouting`].
793///
794/// The planner delegates path *discovery* to any [`PathSelector`] implementation and
795/// owns the `moka` cache of fully-validated [`ValidatedPath`] objects paired with
796/// their traversal cost, keyed by `(source: NodeId, destination: NodeId, hops: u32)`.
797///
798/// On a cache miss the planner calls the selector, validates every candidate against
799/// the chain resolver, and stores an `Arc<WeightedCollection<ValidatedPath>>` in the
800/// cache. On a cache hit a candidate is picked via weighted random selection (higher
801/// cost = higher quality = higher probability).
802///
803/// A background sweep (`background_refresh`) can be spawned to
804/// proactively re-warm the cache for all previously-seen keys.
805#[derive(Clone)]
806pub struct PathPlanner<Surb, R, S> {
807    me: OffchainPublicKey,
808    pub surb_store: Surb,
809    paths: Arc<PathBuilder<R, S>>,
810    cache: moka::future::Cache<PlannerCacheKey, PlannerCacheValue>,
811    refresh_period: Duration,
812    /// See [`IMPLAUSIBLE_PROBE_INTERVAL`]; shared by every clone of the planner.
813    probe_budget: Arc<ProbeBudget>,
814    observer: Option<TransportObserver>,
815}
816
817impl<Surb, R, S> PathPlanner<Surb, R, S>
818where
819    Surb: SurbStore + Send + Sync + 'static,
820    R: ChainKeyOperations + ChainReadChannelOperations + Send + Sync + 'static,
821    S: PathSelector + Send + Sync + 'static,
822{
823    /// Create a new path planner.
824    ///
825    /// `me` is this node's [`OffchainPublicKey`]; it is used as the source in path queries.
826    pub fn new(me: OffchainPublicKey, surb_store: Surb, resolver: R, selector: S, config: PathPlannerConfig) -> Self {
827        // Bound the diversity tracker to the live cache: when a key's cached paths are evicted by
828        // capacity or expire by TTL, drop its collapsed-state record too, so the set cannot grow
829        // without bound as distinct `(source, destination, hops)` keys churn. A `Replaced` eviction
830        // (a recompute or refresh installing a newer value for the same key) leaves the key live, so
831        // its record must stay. Cleanup is silent -- it is not a diversity recovery, so no INFO.
832        let collapsed_diversity: Arc<Mutex<HashSet<PlannerCacheKey>>> = Arc::new(Mutex::new(HashSet::new()));
833        let tracker_for_eviction = collapsed_diversity.clone();
834        let cache = moka::future::Cache::builder()
835            .max_capacity(config.max_cache_capacity)
836            .time_to_live(config.cache_ttl)
837            .eviction_listener(move |key: Arc<PlannerCacheKey>, _value, cause| {
838                if cause != moka::notification::RemovalCause::Replaced {
839                    tracker_for_eviction.lock().remove(key.as_ref());
840                }
841            })
842            .build();
843
844        Self {
845            me,
846            surb_store,
847            paths: Arc::new(PathBuilder {
848                resolver,
849                selector,
850                weighting: WeightingParams {
851                    latency_halflife: config.latency_halflife,
852                    capacity_reference: config.capacity_reference,
853                    return_path_weight_temper: config.return_path_weight_temper,
854                    return_path_exploration: config.return_path_exploration,
855                },
856                me,
857                collapsed_diversity,
858            }),
859            cache,
860            refresh_period: config.refresh_period,
861            probe_budget: Arc::default(),
862            observer: None,
863        }
864    }
865
866    /// Report path resolves to `observer`. Attach it before the planner is shared.
867    pub fn with_observer(mut self, observer: TransportObserver) -> Self {
868        self.observer = Some(observer);
869        self
870    }
871
872    /// Configure the owned selector without changing existing planner clones.
873    pub(crate) fn configure_selector(&mut self, configure: impl FnOnce(&mut S))
874    where
875        R: Clone,
876        S: Clone,
877    {
878        configure(&mut Arc::make_mut(&mut self.paths).selector);
879    }
880
881    /// Report an outcome using canonical peer identity, retaining unresolved chain addresses.
882    fn record_resolution(&self, source: NodeId, destination: NodeId, succeeded: bool) {
883        if let Some(observer) = &self.observer {
884            let (direction, peer) = if source == NodeId::Offchain(self.me) {
885                (PathDirection::Forward, destination)
886            } else {
887                (PathDirection::Return, source)
888            };
889            let peer = match peer {
890                NodeId::Chain(address) => self
891                    .paths
892                    .resolver
893                    .chain_key_to_packet_key(&address)
894                    .ok()
895                    .flatten()
896                    .map(NodeId::Offchain)
897                    .unwrap_or(peer),
898                _ => peer,
899            };
900            observer(TransportEvent::PathResolved {
901                direction,
902                destination: peer,
903                succeeded,
904            });
905        }
906    }
907
908    /// Test-only count of `(src, dest, hops)` keys currently flagged as having collapsed
909    /// return-path relayer diversity, used to assert the WARN fires on the transition only.
910    #[cfg(test)]
911    fn collapsed_diversity_len(&self) -> usize {
912        self.paths.collapsed_diversity.lock().len()
913    }
914
915    /// Resolve a [`NodeId`] to an [`OffchainPublicKey`].
916    async fn resolve_node_id_to_offchain_key(&self, node_id: &NodeId) -> Result<OffchainPublicKey> {
917        match node_id {
918            NodeId::Offchain(key) => Ok(*key),
919            NodeId::Chain(addr) => {
920                let resolver = ChainPathResolver::from(&self.paths.resolver);
921                resolver
922                    .resolve_transport_address(addr)
923                    .await
924                    .map_err(|e| PathPlannerError::Other(anyhow::anyhow!("{e}")))?
925                    .ok_or_else(|| {
926                        PathPlannerError::Other(anyhow::anyhow!("no offchain key found for chain address {addr}"))
927                    })
928            }
929        }
930    }
931
932    /// Report the result of each forward resolution, including cache hits and failures.
933    #[tracing::instrument(name = "planner.resolve_path", level = "trace", skip_all)]
934    async fn resolve_path(
935        &self,
936        source: NodeId,
937        destination: NodeId,
938        options: RoutingOptions,
939    ) -> Result<ValidatedPath> {
940        let result = self.resolve_path_inner(source, destination, options).await;
941        self.record_resolution(source, destination, result.is_ok());
942        result
943    }
944
945    /// Resolve cached or newly selected paths while retaining validation and cache semantics.
946    async fn resolve_path_inner(
947        &self,
948        source: NodeId,
949        destination: NodeId,
950        options: RoutingOptions,
951    ) -> Result<ValidatedPath> {
952        let path = match options {
953            RoutingOptions::IntermediatePath(explicit_path) => {
954                tracing::trace!(
955                    direction = "loopback",
956                    ?source,
957                    ?destination,
958                    ?explicit_path,
959                    "resolving intermediate path"
960                );
961                let resolver = ChainPathResolver::from(&self.paths.resolver);
962                ValidatedPath::new(
963                    source,
964                    explicit_path
965                        .into_iter()
966                        .chain(std::iter::once(destination))
967                        .collect::<Vec<_>>(),
968                    &resolver,
969                )
970                .await?
971            }
972
973            RoutingOptions::Hops(hops) if u32::from(hops) == 0 => {
974                tracing::trace!(hops = 0, "resolving zero-hop direct path");
975                let resolver = ChainPathResolver::from(&self.paths.resolver);
976                ValidatedPath::new(source, vec![destination], &resolver).await?
977            }
978
979            RoutingOptions::Hops(hops) => {
980                let hops_usize: usize = hops.into();
981                let paths = self.cached_paths(source, destination, hops).await?;
982
983                // Format from the `NodeId`s rather than re-resolving them: `cached_paths` has
984                // already done that, and for `NodeId::Chain` each resolution is a resolver lookup.
985                //
986                // Explored like a return draw (see `return_path_exploration`): weights exist only for
987                // paths that get drawn, so without it a forward candidate that fell out of favour is
988                // never measured again, and the stream settles on one path.
989                //
990                // Over plausible candidates only, exploring or not: a forward packet through a relayer
991                // on probation, or over an edge probes measured dead, is data lost, PIX shares and
992                // SURBs with it, and it probes nothing (a probation ends on a reply through the
993                // relayer, which only a return path carries). Tempered, a relayer on probation keeps
994                // about 3 % of a healthy one's weight, so the ordinary draw is gated too.
995                let mut weights = paths.1.iter().map(|(_, weight)| *weight).collect::<Vec<_>>();
996                let drawn = if should_explore(self.paths.weighting.return_path_exploration) {
997                    pick_exploring_index(&weights, || false)
998                } else {
999                    gate_implausible(&mut weights);
1000                    pick_weighted_index(&weights)
1001                }
1002                .and_then(|i| {
1003                    tracing::trace!(set_id = paths.0, index = i, direction = "forward", "candidate selected");
1004                    paths.1.iter().nth(i)
1005                })
1006                .map(|(vp, _)| vp.clone());
1007                drawn.ok_or_else(|| {
1008                    PathPlannerError::Path(PathError::PathNotFound(
1009                        hops_usize,
1010                        source.to_string(),
1011                        destination.to_string(),
1012                    ))
1013                })?
1014            }
1015        };
1016
1017        #[cfg(all(feature = "telemetry", not(test)))]
1018        {
1019            hopr_api::types::telemetry::SimpleHistogram::observe(&METRIC_PATH_LENGTH, (path.num_hops() - 1) as f64);
1020        }
1021
1022        tracing::trace!(%path, "validated resolved path");
1023        Ok(path)
1024    }
1025
1026    /// Cached weighted collection of validated `hops`-hop paths from `source` to `destination`,
1027    /// computed on a miss.
1028    ///
1029    /// Single-path callers draw with `pick_one`; batch callers (see
1030    /// [`PathPlanner::resolve_diverse_return_paths`]) work over the collection directly, paying one
1031    /// cache lookup instead of one per path.
1032    #[tracing::instrument(name = "planner.cached_paths", level = "trace", skip_all)]
1033    async fn cached_paths(
1034        &self,
1035        source: NodeId,
1036        destination: NodeId,
1037        hops: hopr_api::types::primitive::bounded::BoundedSize<{ RoutingOptions::MAX_INTERMEDIATE_HOPS }>,
1038    ) -> Result<PlannerCacheValue> {
1039        let hops_usize: usize = hops.into();
1040        tracing::trace!(hops = hops_usize, "resolving path via planner cache");
1041
1042        let src_key = self.resolve_node_id_to_offchain_key(&source).await?;
1043        let dest_key = self.resolve_node_id_to_offchain_key(&destination).await?;
1044
1045        let cache_key: PlannerCacheKey = (src_key, dest_key, u32::from(hops));
1046
1047        let paths = self.paths.clone();
1048
1049        self.cache
1050            .try_get_with(cache_key, async move {
1051                tracing::trace!(hops = hops_usize, "path cache miss, querying selector");
1052                let (weighted, diversity) =
1053                    paths
1054                        .rebuild(src_key, dest_key, hops_usize, "fill")
1055                        .await?
1056                        .ok_or_else(|| {
1057                            PathPlannerError::Path(PathError::PathNotFound(
1058                                hops_usize,
1059                                src_key.to_hex(),
1060                                dest_key.to_hex(),
1061                            ))
1062                        })?;
1063                // A fill always becomes the cache entry, so its transition can be applied here.
1064                paths.apply_diversity("fill", diversity);
1065                Ok(Arc::new(weighted))
1066            })
1067            .await
1068            .map_err(PathPlannerError::CacheError)
1069    }
1070
1071    /// Runs one background sweep now: called when relayer health in the graph changes, so cached
1072    /// paths follow it at once instead of up to [`PathPlannerConfig::refresh_period`] later.
1073    pub(crate) async fn refresh_cached_paths(&self) {
1074        self.paths.sweep(&self.cache).await
1075    }
1076
1077    /// Rebuilds every cached entry whose paths originate at `source`, replacing each in place.
1078    ///
1079    /// Return paths are cached under `(counterparty, me, hops)`, so this is how a caller that has
1080    /// just learned a counterparty's return traffic went silent forces those weights to be rebuilt
1081    /// from the current graph, instead of waiting up to
1082    /// [`PathPlannerConfig::refresh_period`] for the background sweep to reach them.
1083    ///
1084    /// Entries are replaced, never dropped: one that rebuilds to nothing keeps serving what it
1085    /// already holds. Dropping them was measured to collapse a healthy session from 100 % to
1086    /// 0.14 %, because a live session draws its next return path from this very entry.
1087    ///
1088    /// Returns how many entries came back with a materially different **share** of the draws --
1089    /// not how many were rebuilt. Callers use this to decide whether the re-plan achieved anything
1090    /// worth acting on, and on a healthy graph a rebuild always succeeds, so counting rebuilds
1091    /// would answer "something moved" every time.
1092    #[tracing::instrument(name = "planner.recompute_paths", level = "trace", skip_all)]
1093    pub async fn recompute_paths_from(&self, source: &OffchainPublicKey) -> usize {
1094        // 0-hop entries name a direct route with nothing to re-weight, exactly as in the sweep.
1095        let keys = self
1096            .cache
1097            .iter()
1098            .map(|(key, _)| *key.as_ref())
1099            .filter(|(src, _, hops)| src == source && *hops > 0)
1100            .collect::<Vec<PlannerCacheKey>>();
1101
1102        let mut moved = 0usize;
1103        for (src_key, dest_key, hops) in keys {
1104            if let Ok(Some((weighted, diversity))) =
1105                self.paths.rebuild(src_key, dest_key, hops as usize, "recompute").await
1106            {
1107                let key = (src_key, dest_key, hops);
1108                // A fresh entry counts as moved -- there was no previous distribution to compare
1109                // against, so nothing here can say the traffic stayed put.
1110                let mut shifted = true;
1111                // Through `and_compute_with`, like the background refresh's `put_if_unchanged`: moka
1112                // serialises only compute calls on a key, so a plain insert here could land between
1113                // the refresh's read and write and be overwritten by the older entry it rebuilt.
1114                let installed = self
1115                    .cache
1116                    .entry(key)
1117                    .and_compute_with(|previous| {
1118                        if let Some(previous) = previous {
1119                            shifted = weights_moved(&previous.value().1, &weighted.1);
1120                        }
1121                        futures::future::ready(moka::ops::compute::Op::Put(Arc::new(weighted)))
1122                    })
1123                    .await;
1124                if let moka::ops::compute::CompResult::Inserted(entry)
1125                | moka::ops::compute::CompResult::ReplacedWith(entry) = installed
1126                {
1127                    tracing::debug!(
1128                        source = %src_key,
1129                        destination = %dest_key,
1130                        hops,
1131                        candidates = entry.value().1.len(),
1132                        set_id = entry.value().0,
1133                        kind = "recompute",
1134                        "candidate set installed"
1135                    );
1136                }
1137                // The recompute always installs, so its diversity transition always applies.
1138                self.paths.apply_diversity("recompute", diversity);
1139                if shifted {
1140                    moved += 1;
1141                }
1142            }
1143        }
1144
1145        tracing::debug!(%source, moved, "recomputed cached paths originating at peer");
1146        moved
1147    }
1148
1149    /// Resolves `count` return paths from `destination` back to this node, drawn weighted-random
1150    /// over [`PathPlannerConfig::return_path_weight_temper`]-flattened path values.
1151    ///
1152    /// Tempering is what bounds the blast radius of losing one relay: raw path values concentrate a
1153    /// session's SURBs on the few best candidates, so the flatter the effective distribution, the
1154    /// smaller any single relay's share of the return stream.
1155    ///
1156    /// Draws are independent — deliberately. Spreading a *batch* over K distinct relayers was tried
1157    /// and cannot work: a batch is the SURBs that fit in one packet (`HoprPacket::PAYLOAD_SIZE /
1158    /// HoprSurb::SIZE`, a handful at most), so K was capped by it whatever the configuration said,
1159    /// while each packet re-drew independently regardless. Tempering has no such ceiling.
1160    ///
1161    /// Neither spreads anything the candidates do not offer: the selector searches each first
1162    /// relayer's paths separately (`compute_paths_spread`), so a pool names every first relayer
1163    /// the graph allows rather than the one or two a single depth-first search reached first.
1164    ///
1165    /// Only `Hops` routing has alternatives to draw over — an explicit path resolves to itself, so
1166    /// those fall back to plain repeated resolution.
1167    #[tracing::instrument(name = "planner.resolve_diverse_return_paths", level = "trace", skip_all)]
1168    async fn resolve_diverse_return_paths(
1169        &self,
1170        destination: NodeId,
1171        options: RoutingOptions,
1172        count: usize,
1173    ) -> Result<Vec<ValidatedPath>> {
1174        let result = self
1175            .resolve_diverse_return_paths_inner(destination, options, count)
1176            .await;
1177        if count > 0 {
1178            self.record_resolution(destination, NodeId::Offchain(self.me), result.is_ok());
1179        }
1180        result
1181    }
1182
1183    /// Draw return paths from cached or rebuilt candidates while preserving path diversity.
1184    async fn resolve_diverse_return_paths_inner(
1185        &self,
1186        destination: NodeId,
1187        options: RoutingOptions,
1188        count: usize,
1189    ) -> Result<Vec<ValidatedPath>> {
1190        // No return paths requested (e.g. the message fills the payload, leaving no room for
1191        // SURBs). Resolve nothing — querying the planner here would turn "none wanted" into a
1192        // `PathNotFound` error.
1193        if count == 0 {
1194            return Ok(Vec::new());
1195        }
1196
1197        let me = NodeId::Offchain(self.me);
1198
1199        let hops = match options {
1200            RoutingOptions::Hops(hops) if u32::from(hops) > 0 => hops,
1201            // A fixed path or a direct return has no alternatives to weight over.
1202            other => {
1203                return (0..count)
1204                    .map(|_| self.resolve_path_inner(destination, me, other.clone()))
1205                    .collect::<FuturesUnordered<_>>()
1206                    .try_collect::<Vec<_>>()
1207                    .await;
1208            }
1209        };
1210
1211        let candidates = self.cached_paths(destination, me, hops).await?;
1212        let items: Vec<&(ValidatedPath, f64)> = candidates.1.iter().collect();
1213        let weights = items.iter().map(|(_, w)| *w).collect::<Vec<_>>();
1214
1215        if weights.iter().all(|w| *w <= 0.0) {
1216            return Err(PathPlannerError::Path(PathError::PathNotFound(
1217                hops.into(),
1218                destination.to_string(),
1219                me.to_string(),
1220            )));
1221        }
1222
1223        // Distinct first relayers in the candidate pool: the return-relayer diversity actually
1224        // available for this destination. A value of 1 is the corroboration blind spot (a dead
1225        // relayer cannot be told from a quiet peer) — the same condition `PathBuilder::rebuild` WARNs
1226        // on. This draw runs per-packet, so both sets below are built only when TRACE is actually
1227        // recorded -- not on every call.
1228        let log_relayer_diversity = tracing::enabled!(tracing::Level::TRACE);
1229        let candidate_relayers = log_relayer_diversity.then(|| {
1230            items
1231                .iter()
1232                .filter_map(|item| item.0.first())
1233                .collect::<std::collections::HashSet<_>>()
1234        });
1235
1236        tracing::trace!(
1237            %destination,
1238            count,
1239            candidates = items.len(),
1240            distinct_relayers = candidate_relayers.as_ref().map_or(0, |r| r.len()),
1241            temper = self.paths.weighting.return_path_weight_temper,
1242            exploration = self.paths.weighting.return_path_exploration,
1243            "drawing return paths from tempered weights"
1244        );
1245
1246        // An exploring draw may land on a candidate the weights all but reject only within the
1247        // node-wide probe allowance: see `IMPLAUSIBLE_PROBE_INTERVAL`.
1248        let drawn = (0..count)
1249            .filter_map(|_| {
1250                if should_explore(self.paths.weighting.return_path_exploration) {
1251                    pick_exploring_index(&weights, || self.probe_budget.take())
1252                } else {
1253                    pick_weighted_index(&weights)
1254                }
1255                .map(|i| {
1256                    tracing::trace!(
1257                        set_id = candidates.0,
1258                        index = i,
1259                        direction = "return",
1260                        "candidate selected"
1261                    );
1262                    items[i].0.clone()
1263                })
1264            })
1265            .collect::<Vec<_>>();
1266
1267        // How many distinct relayers the actual SURBs went to. Fewer than the candidate pool means
1268        // the weighting concentrated the stream — expected — but a persistent 1 here while
1269        // `candidates` > 1 says the draw itself is starving the siblings the detector relies on.
1270        let drawn_relayers = log_relayer_diversity.then(|| {
1271            drawn
1272                .iter()
1273                .filter_map(|vp| vp.first())
1274                .collect::<std::collections::HashSet<_>>()
1275        });
1276        tracing::trace!(
1277            %destination,
1278            drawn = drawn.len(),
1279            distinct_relayers = drawn_relayers.as_ref().map_or(0, |r| r.len()),
1280            of_candidates = candidate_relayers.as_ref().map_or(0, |r| r.len()),
1281            "drew return paths"
1282        );
1283
1284        Ok(drawn)
1285    }
1286
1287    /// Resolve a [`DestinationRouting`] to a [`ResolvedTransportRouting`].
1288    ///
1289    /// Returns the resolved routing and, for `Return` variants, the number of remaining SURBs.
1290    #[tracing::instrument(name = "planner.resolve_routing", level = "trace", skip_all)]
1291    pub async fn resolve_routing(
1292        &self,
1293        size_hint: usize,
1294        max_surbs: usize,
1295        routing: DestinationRouting,
1296    ) -> Result<(ResolvedTransportRouting<HoprSurb>, Option<usize>, Option<u8>)> {
1297        match routing {
1298            DestinationRouting::Forward {
1299                destination,
1300                pseudonym,
1301                forward_options,
1302                return_options,
1303            } => {
1304                tracing::trace!(direction = "forward", %destination, "resolving forward path");
1305
1306                let forward_path = self
1307                    .resolve_path(NodeId::Offchain(self.me), *destination, forward_options)
1308                    .await?;
1309                tracing::trace!(direction = "forward", %destination, path = %forward_path, "resolved path");
1310
1311                let resolved_pseudonym = pseudonym.unwrap_or_else(HoprPseudonym::random);
1312
1313                // Capture the SURB-batch generation here — with the return-path plan, not at encode
1314                // time — because the replying side supersedes SURBs by generation, so a batch's
1315                // generation must match the plan it was minted for.
1316                //
1317                // Crucially, read it *before* resolving the return paths, not after. The flush loop
1318                // recomputes paths and only *then* bumps the generation (`recompute_paths_from` then
1319                // `bump_generation` in `HoprTransport`'s SURB-flush task), so a bump racing this
1320                // resolution has, by the time it happens, already moved the planner to the new route.
1321                // Reading first therefore makes any residual mislabel *under*-label — a fresh route
1322                // stamped with the previous generation, which the peer merely appends and then clears
1323                // on the next batch (a few wasted SURBs) — and never *over*-label — a stale route
1324                // stamped with the newer generation, which would make the peer drop live SURBs and
1325                // hand out dead ones. Reading after the resolve is what would allow the harmful
1326                // over-label (choose old route, bump, read new generation), so the order matters and a
1327                // lock on the per-packet hot path is not needed.
1328                let (return_paths, generation) = if let Some(return_options) = return_options {
1329                    let generation = self.surb_store.current_generation(&resolved_pseudonym);
1330
1331                    let num_possible_surbs = HoprPacket::max_surbs_with_message(size_hint).min(max_surbs);
1332                    tracing::trace!(
1333                        %destination,
1334                        %num_possible_surbs,
1335                        data_len = size_hint,
1336                        max_surbs,
1337                        "resolving packet return paths"
1338                    );
1339
1340                    let return_paths: Vec<_> = self
1341                        .resolve_diverse_return_paths(*destination, return_options, num_possible_surbs)
1342                        .await?
1343                        .into_iter()
1344                        .enumerate()
1345                        .inspect(|(i, rp)| {
1346                            tracing::trace!(direction = "return", %destination, index = i, path = %rp, "resolved return path");
1347                        })
1348                        .map(|(_, rp)| rp)
1349                        .collect();
1350
1351                    // Only stamp a generation if return paths (hence SURBs) were actually produced.
1352                    let generation = (!return_paths.is_empty()).then_some(generation);
1353                    (return_paths, generation)
1354                } else {
1355                    (vec![], None)
1356                };
1357
1358                tracing::trace!(%destination, num_surbs = return_paths.len(), data_len = size_hint, "resolved packet");
1359
1360                Ok((
1361                    ResolvedTransportRouting::Forward {
1362                        pseudonym: resolved_pseudonym,
1363                        forward_path,
1364                        return_paths,
1365                    },
1366                    None,
1367                    generation,
1368                ))
1369            }
1370
1371            DestinationRouting::Return(matcher) => {
1372                let FoundSurb {
1373                    sender_id,
1374                    surb,
1375                    remaining,
1376                } = self
1377                    .surb_store
1378                    .find_surb(matcher)
1379                    .ok_or_else(|| PathPlannerError::Surb(format!("no surb for pseudonym {}", matcher.pseudonym())))?;
1380                Ok((ResolvedTransportRouting::Return(sender_id, surb), Some(remaining), None))
1381            }
1382        }
1383    }
1384}
1385
1386impl<Surb, R, S> BackgroundPathCacheRefreshable for PathPlanner<Surb, R, S>
1387where
1388    Surb: SurbStore + Send + Sync + 'static,
1389    R: ChainKeyOperations + ChainReadChannelOperations + Send + Sync + 'static,
1390    S: PathSelector + Send + Sync + 'static,
1391{
1392    /// Returns a future that runs the background path-cache refresh loop.
1393    ///
1394    /// The returned future iterates over all keys currently in the planner's cache
1395    /// and recomputes their paths on a configurable schedule, so that steady-state
1396    /// traffic is always served from cache.
1397    fn run_background_refresh(&self) -> impl std::future::Future<Output = ()> + Send + 'static {
1398        // Clone only the fields we need — avoids requiring R: Clone + S: Clone.
1399        let cache = self.cache.clone();
1400        let paths = self.paths.clone();
1401        let refresh_period = self.refresh_period;
1402
1403        // run at a non-zero interval
1404        futures_time::stream::interval(futures_time::time::Duration::from_millis(
1405            refresh_period.as_millis() as u64 + 1u64,
1406        ))
1407        .for_each(move |_| {
1408            let cache = cache.clone();
1409            let paths = paths.clone();
1410            async move { paths.sweep(&cache).await }
1411        })
1412        .instrument(tracing::debug_span!(parent: None, "planner.background_refresh"))
1413    }
1414}
1415
1416#[cfg(test)]
1417mod tests {
1418    use std::str::FromStr;
1419
1420    use anyhow::Context;
1421    use bimap::BiMap;
1422    use futures::stream::{self, BoxStream};
1423    use hex_literal::hex;
1424    use hopr_api::{
1425        chain::{ChainKeyOperations, ChainReadChannelOperations, ChannelSelector, HoprKeyIdent},
1426        graph::{NetworkGraphWrite, traits::EdgeObservableWrite},
1427        types::{
1428            crypto::prelude::{Keypair, OffchainKeypair},
1429            internal::channels::{ChannelEntry, ChannelStatus, generate_channel_id},
1430            primitive::prelude::*,
1431        },
1432    };
1433    use hopr_network_graph::ChannelGraph;
1434
1435    use super::*;
1436    use crate::path::selector::HoprGraphPathSelector;
1437
1438    #[derive(Debug)]
1439    struct TestError(String);
1440
1441    impl std::fmt::Display for TestError {
1442        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
1443            f.write_str(&self.0)
1444        }
1445    }
1446
1447    impl std::error::Error for TestError {}
1448
1449    const SECRET_ME: [u8; 32] = hex!("60741b83b99e36aa0c1331578156e16b8e21166d01834abb6c64b103f885734d");
1450    const SECRET_A: [u8; 32] = hex!("71bf1f42ebbfcd89c3e197a3fd7cda79b92499e509b6fefa0fe44d02821d146a");
1451    const SECRET_DEST: [u8; 32] = hex!("c24bd833704dd2abdae3933fcc9962c2ac404f84132224c474147382d4db2299");
1452    /// A second relayer, so a return fixture can offer a real alternative to the one that dies.
1453    const SECRET_B: [u8; 32] = hex!("3d5f2c8a91b4e07d6a3c1f8e2b95d40c7e6a1938f2c5b8d04e7a1c396b2f8d05");
1454
1455    fn pubkey(secret: &[u8; 32]) -> OffchainPublicKey {
1456        *OffchainKeypair::from_secret(secret).expect("valid secret").public()
1457    }
1458
1459    #[derive(Clone)]
1460    struct Mapper {
1461        map: Arc<BiMap<OffchainPublicKey, HoprKeyIdent>>,
1462    }
1463
1464    impl KeyIdMapping<HoprKeyIdent, OffchainPublicKey> for Mapper {
1465        fn map_key_to_id(&self, key: &OffchainPublicKey) -> Option<HoprKeyIdent> {
1466            self.map.get_by_left(key).copied()
1467        }
1468
1469        fn map_id_to_public(&self, id: &HoprKeyIdent) -> Option<OffchainPublicKey> {
1470            self.map.get_by_right(id).copied()
1471        }
1472
1473        fn map_keys_to_ids(&self, keys: &[OffchainPublicKey]) -> Vec<Option<HoprKeyIdent>> {
1474            keys.iter().map(|key| self.map_key_to_id(key)).collect()
1475        }
1476
1477        fn map_ids_to_keys(&self, ids: &[HoprKeyIdent]) -> Vec<Option<OffchainPublicKey>> {
1478            ids.iter().map(|id| self.map_id_to_public(id)).collect()
1479        }
1480    }
1481
1482    struct TestChainApi {
1483        me: Address,
1484        key_addr_map: BiMap<OffchainPublicKey, Address>,
1485        channels: Vec<ChannelEntry>,
1486        id_mapper: Mapper,
1487    }
1488
1489    impl TestChainApi {
1490        fn new(me_key: OffchainPublicKey, me_addr: Address, peers: Vec<(OffchainPublicKey, Address)>) -> Self {
1491            let mut key_addr_map = BiMap::new();
1492            let mut key_id_map: BiMap<OffchainPublicKey, HoprKeyIdent> = BiMap::new();
1493            key_addr_map.insert(me_key, me_addr);
1494            key_id_map.insert(me_key, 0u32.into());
1495            for (i, (k, a)) in peers.iter().enumerate() {
1496                key_addr_map.insert(*k, *a);
1497                key_id_map.insert(*k, ((i + 1) as u32).into());
1498            }
1499            Self {
1500                me: me_addr,
1501                key_addr_map,
1502                channels: vec![],
1503                id_mapper: Mapper {
1504                    map: Arc::new(key_id_map),
1505                },
1506            }
1507        }
1508
1509        fn with_open_channel(mut self, src: Address, dst: Address) -> Self {
1510            self.channels.push(
1511                ChannelEntry::builder()
1512                    .between(src, dst)
1513                    .amount(100)
1514                    .ticket_index(1)
1515                    .status(ChannelStatus::Open)
1516                    .epoch(1)
1517                    .build()
1518                    .unwrap(),
1519            );
1520            self
1521        }
1522    }
1523
1524    impl ChainKeyOperations for TestChainApi {
1525        type Error = TestError;
1526        type Mapper = Mapper;
1527
1528        fn chain_key_to_packet_key(
1529            &self,
1530            chain: &Address,
1531        ) -> std::result::Result<Option<OffchainPublicKey>, TestError> {
1532            Ok(self.key_addr_map.get_by_right(chain).copied())
1533        }
1534
1535        fn packet_key_to_chain_key(
1536            &self,
1537            packet: &OffchainPublicKey,
1538        ) -> std::result::Result<Option<Address>, TestError> {
1539            Ok(self.key_addr_map.get_by_left(packet).copied())
1540        }
1541
1542        fn key_id_mapper_ref(&self) -> &Self::Mapper {
1543            &self.id_mapper
1544        }
1545    }
1546
1547    impl ChainReadChannelOperations for TestChainApi {
1548        type Error = TestError;
1549
1550        fn me(&self) -> &Address {
1551            &self.me
1552        }
1553
1554        fn channel_by_id(&self, channel_id: &ChannelId) -> std::result::Result<Option<ChannelEntry>, TestError> {
1555            Ok(self
1556                .channels
1557                .iter()
1558                .find(|c| generate_channel_id(&c.source, &c.destination) == *channel_id)
1559                .cloned())
1560        }
1561
1562        fn stream_channels<'a>(
1563            &'a self,
1564            _selector: ChannelSelector,
1565        ) -> std::result::Result<BoxStream<'a, ChannelEntry>, TestError> {
1566            Ok(Box::pin(stream::iter(self.channels.clone())))
1567        }
1568    }
1569
1570    #[test]
1571    fn the_loopback_verdict_should_default_to_three_loops_and_a_tenth() {
1572        let cfg = PathPlannerConfig::default();
1573        assert_eq!(cfg.min_loopbacks_for_rate, 3);
1574        assert_eq!(cfg.min_loopback_return_rate, 0.1);
1575        assert!(cfg.validate().is_ok());
1576    }
1577
1578    #[test]
1579    fn a_loopback_verdict_that_could_never_starve_a_relay_should_be_invalid() {
1580        // A rate of zero is met by any relay returning the odd loop, which is what a dropping relay does.
1581        for rate in [0.0, -0.1, 1.5, f64::NAN, f64::INFINITY] {
1582            let cfg = PathPlannerConfig {
1583                min_loopback_return_rate: rate,
1584                ..Default::default()
1585            };
1586            assert!(cfg.validate().is_err(), "a return rate of {rate} must be rejected");
1587        }
1588        let cfg = PathPlannerConfig {
1589            min_loopbacks_for_rate: 0,
1590            ..Default::default()
1591        };
1592        assert!(
1593            cfg.validate().is_err(),
1594            "judging by the rate from zero loops must be rejected"
1595        );
1596        let cfg = PathPlannerConfig {
1597            min_loopback_return_rate: 1.0,
1598            ..Default::default()
1599        };
1600        assert!(cfg.validate().is_ok(), "a relay may be asked to return every loop");
1601    }
1602
1603    #[test]
1604    fn exploration_should_be_off_at_zero_and_certain_at_one() {
1605        // The two endpoints are what callers actually configure, and a mistake at either end is
1606        // silent: 0.0 that still explores wastes throughput, 1.0 that never does starves the
1607        // observations the weights are built from.
1608        assert!((0..200).all(|_| !should_explore(0.0)));
1609        assert!((0..200).all(|_| should_explore(1.0)));
1610    }
1611
1612    #[test]
1613    fn exploration_rate_should_be_near_the_configured_fraction() {
1614        let explored = (0..10_000).filter(|_| should_explore(0.1)).count();
1615        // Loose bounds: this is a CSPRNG draw, so the test is guarding the wiring, not the
1616        // generator's uniformity.
1617        assert!(
1618            (700..1_300).contains(&explored),
1619            "expected roughly 1000 of 10000 draws to explore, got {explored}"
1620        );
1621    }
1622
1623    #[test]
1624    fn uniform_index_should_stay_in_range_and_reach_every_candidate() {
1625        assert_eq!(None, pick_uniform_index(0), "nothing to pick from");
1626
1627        let mut seen = std::collections::HashSet::new();
1628        for _ in 0..1_000 {
1629            let i = pick_uniform_index(4).expect("non-empty");
1630            assert!(i < 4, "index {i} out of range");
1631            seen.insert(i);
1632        }
1633        assert_eq!(4, seen.len(), "every candidate must be reachable");
1634    }
1635
1636    #[test]
1637    fn exploration_should_reach_a_candidate_that_weighting_would_never_pick() {
1638        // The point of the knob: a path whose weight has collapsed still gets traffic occasionally,
1639        // which is the only way it can ever be re-measured and recover.
1640        let weights = [1.0, 0.0];
1641        assert!(
1642            (0..200).all(|_| pick_weighted_index(&weights) == Some(0)),
1643            "a zero weight is never drawn by weight"
1644        );
1645        assert!(
1646            (0..1_000).any(|_| pick_uniform_index(weights.len()) == Some(1)),
1647            "an exploratory draw must be able to reach it"
1648        );
1649    }
1650
1651    #[test]
1652    fn a_zero_candidate_limit_should_fail_validation() {
1653        let cfg = PathPlannerConfig {
1654            max_cached_paths: 0,
1655            ..Default::default()
1656        };
1657        assert!(cfg.validate().is_err());
1658        assert!(PathPlannerConfig::default().validate().is_ok());
1659    }
1660
1661    #[test]
1662    fn a_refresh_period_below_the_minimum_should_fail_validation() {
1663        for period in [Duration::ZERO, MIN_REFRESH_PERIOD - Duration::from_millis(1)] {
1664            let cfg = PathPlannerConfig {
1665                refresh_period: period,
1666                ..Default::default()
1667            };
1668            assert!(cfg.validate().is_err(), "{period:?} must be rejected");
1669        }
1670        let cfg = PathPlannerConfig {
1671            refresh_period: MIN_REFRESH_PERIOD,
1672            ..Default::default()
1673        };
1674        assert!(cfg.validate().is_ok());
1675    }
1676
1677    #[test]
1678    fn a_refresh_period_not_shorter_than_the_cache_ttl_should_fail_validation() {
1679        let cfg = |cache_ttl, refresh_period| PathPlannerConfig {
1680            cache_ttl,
1681            refresh_period,
1682            ..Default::default()
1683        };
1684        assert!(cfg(Duration::from_secs(1), Duration::from_secs(5)).validate().is_err());
1685        assert!(
1686            cfg(Duration::from_secs(5), Duration::from_secs(5)).validate().is_err(),
1687            "an entry must not expire at the moment the sweep reaches it"
1688        );
1689        assert!(cfg(Duration::from_secs(10), Duration::from_secs(5)).validate().is_ok());
1690    }
1691
1692    /// Cached candidate weights are frozen at fill time, so the TTL bounds how stale the numbers a
1693    /// live session draws from can be -- not just how stale the candidate set is.
1694    #[test]
1695    fn the_path_cache_should_expire_faster_than_a_session_can_be_lost() {
1696        let cfg = PathPlannerConfig::default();
1697
1698        // The SURB round-trip window slices at 5s. A TTL far above that lets a relay keep its full
1699        // share of return-path draws long after the graph has scored it down -- measured as a
1700        // session that stayed degraded for minutes after the evidence was in.
1701        assert!(
1702            cfg.cache_ttl <= Duration::from_secs(15),
1703            "path cache TTL {:?} outlives the evidence that should displace it",
1704            cfg.cache_ttl
1705        );
1706        assert!(
1707            cfg.refresh_period < cfg.cache_ttl,
1708            "the background sweep ({:?}) must re-weight entries before they expire ({:?})",
1709            cfg.refresh_period,
1710            cfg.cache_ttl
1711        );
1712    }
1713
1714    #[test]
1715    fn config_should_reject_a_weight_temper_outside_the_unit_range() {
1716        assert!(PathPlannerConfig::default().validate().is_ok());
1717
1718        // 1.0 is the raw path value — the sharpest permitted, and the pre-tempering behaviour.
1719        assert!(
1720            PathPlannerConfig {
1721                return_path_weight_temper: 1.0,
1722                ..PathPlannerConfig::default()
1723            }
1724            .validate()
1725            .is_ok()
1726        );
1727
1728        // Above 1.0 sharpens instead of flattening, concentrating harder than raw path value.
1729        let sharpening = PathPlannerConfig {
1730            return_path_weight_temper: 1.5,
1731            ..PathPlannerConfig::default()
1732        };
1733        // Assert on the rendered message, which is what an operator actually sees.
1734        let err = sharpening
1735            .validate()
1736            .expect_err("a sharpening exponent must be rejected");
1737        assert!(err.to_string().contains("must be in (0, 1]"), "{err}");
1738
1739        // Zero annihilates the ordering: every candidate would weigh exactly 1.
1740        assert!(
1741            PathPlannerConfig {
1742                return_path_weight_temper: 0.0,
1743                ..PathPlannerConfig::default()
1744            }
1745            .validate()
1746            .is_err()
1747        );
1748    }
1749
1750    #[test]
1751    fn temper_should_compress_the_weight_spread_without_reordering() {
1752        let raw = [0.4, 0.3, 0.2, 0.1];
1753
1754        let untouched = temper_weights(&raw, 1.0);
1755        assert_eq!(raw.to_vec(), untouched, "temper 1.0 must be the identity");
1756
1757        let flattened = temper_weights(&raw, 0.5);
1758        // Order preserved…
1759        assert!(flattened.windows(2).all(|w| w[0] > w[1]), "{flattened:?}");
1760        // …but the best-to-worst ratio shrinks from 4.0 towards 1.0, which is what bounds how much
1761        // of a session rides on the single best relayer.
1762        let raw_ratio = raw[0] / raw[3];
1763        let tempered_ratio = flattened[0] / flattened[3];
1764        assert!(
1765            tempered_ratio < raw_ratio,
1766            "{tempered_ratio} should be below {raw_ratio}"
1767        );
1768        assert!((tempered_ratio - 2.0).abs() < 1e-9, "{tempered_ratio}");
1769    }
1770
1771    #[test]
1772    fn temper_should_clamp_negative_weights_instead_of_producing_nan() {
1773        // `powf` on a negative base with a fractional exponent is NaN, which would poison the
1774        // cumulative sum in `pick_weighted_index` and make selection return nothing.
1775        let out = temper_weights(&[-1.0, 0.0, 4.0], 0.5);
1776        assert!(out.iter().all(|w| w.is_finite()), "{out:?}");
1777        assert_eq!(vec![0.0, 0.0, 2.0], out);
1778    }
1779
1780    #[test]
1781    fn pick_weighted_index_should_reject_a_non_positive_total() {
1782        assert_eq!(None, pick_weighted_index(&[]));
1783        assert_eq!(None, pick_weighted_index(&[0.0, 0.0]));
1784        assert_eq!(Some(1), pick_weighted_index(&[0.0, 1.0]));
1785    }
1786
1787    // ── address fixtures ──────────────────────────────────────────────────────
1788    fn me_addr() -> Address {
1789        Address::from_str("0x1000d5786d9e6799b3297da1ad55605b91e2c882").expect("valid addr")
1790    }
1791    fn a_addr() -> Address {
1792        Address::from_str("0x200060ddced1e33c9647a71f4fc2cf4ed33e4a9d").expect("valid addr")
1793    }
1794    fn dest_addr() -> Address {
1795        Address::from_str("0x30004105095c8c10f804109b4d1199a9ac40ed46").expect("valid addr")
1796    }
1797    fn b_addr() -> Address {
1798        Address::from_str("0x40001a7ec3d5b28f9047c6b1e83d5a2f9c71b0e4").expect("valid addr")
1799    }
1800
1801    // ── graph helpers ──────────────────────────────────────────────────────────
1802    fn mark_edge_full(graph: &ChannelGraph, src: &OffchainPublicKey, dst: &OffchainPublicKey) {
1803        use hopr_api::graph::traits::EdgeWeightType;
1804        graph.upsert_edge(src, dst, |obs| {
1805            obs.record(EdgeWeightType::Connected(true));
1806            obs.record(EdgeWeightType::Immediate(Ok(std::time::Duration::from_millis(50))));
1807            obs.record(EdgeWeightType::Intermediate(Ok(std::time::Duration::from_millis(50))));
1808            obs.record(EdgeWeightType::Balance(Some(hopr_api::graph::traits::Balance::from(
1809                1000u64,
1810            ))));
1811        });
1812    }
1813
1814    fn small_config() -> PathPlannerConfig {
1815        PathPlannerConfig {
1816            max_cache_capacity: 100,
1817            cache_ttl: std::time::Duration::from_secs(60),
1818            refresh_period: std::time::Duration::from_secs(60),
1819            max_cached_paths: 2,
1820            ..PathPlannerConfig::default()
1821        }
1822    }
1823
1824    // ── test: zero-hop path ───────────────────────────────────────────────────
1825
1826    /// A Session names its destination by chain address; the SURB telemetry names it by packet key.
1827    ///
1828    /// Regression: the cache used to be keyed on the `NodeId` as handed in, and
1829    /// `NodeId::Chain(addr) != NodeId::Offchain(key)` even for the same node -- so the two layers
1830    /// stored and looked up the same route under different keys without either noticing.
1831    #[tokio::test]
1832    async fn a_return_path_should_cache_under_one_key_whichever_form_names_the_node() {
1833        let me = pubkey(&SECRET_ME);
1834        let a = pubkey(&SECRET_A);
1835        let dest = pubkey(&SECRET_DEST);
1836
1837        let graph = ChannelGraph::new(me);
1838        graph.add_node(a);
1839        graph.add_node(dest);
1840        // A return path runs from the destination back to us.
1841        graph.add_edge(&dest, &a).unwrap();
1842        graph.add_edge(&a, &me).unwrap();
1843        mark_edge_full(&graph, &dest, &a);
1844        mark_edge_full(&graph, &a, &me);
1845
1846        let cfg = small_config();
1847        let selector = HoprGraphPathSelector::new(
1848            me,
1849            graph,
1850            cfg.max_cached_paths,
1851            cfg.edge_penalty,
1852            cfg.min_ack_rate,
1853            cfg.min_paths_anonymity_floor,
1854        );
1855        let chain_api = TestChainApi::new(me, me_addr(), vec![(a, a_addr()), (dest, dest_addr())])
1856            .with_open_channel(dest_addr(), a_addr())
1857            .with_open_channel(a_addr(), me_addr());
1858        let surb_store = hopr_protocol_hopr::MemorySurbStore::default();
1859        let planner = PathPlanner::new(me, surb_store, chain_api, selector, small_config());
1860
1861        // Populated the way a Session does it: by chain address.
1862        let _ = planner
1863            .resolve_diverse_return_paths(
1864                NodeId::Chain(dest_addr()),
1865                RoutingOptions::Hops(1.try_into().expect("valid 1")),
1866                1,
1867            )
1868            .await
1869            .expect("return path resolution should succeed");
1870
1871        let cache_key: PlannerCacheKey = (dest, me, 1);
1872        assert!(
1873            planner.cache.get(&cache_key).await.is_some(),
1874            "the return path should be cached after resolution"
1875        );
1876
1877        // Asking again the way the SURB telemetry names the node -- by packet key -- must land on
1878        // that same entry rather than resolving and caching a second copy.
1879        planner.cache.run_pending_tasks().await;
1880        assert_eq!(planner.cache.entry_count(), 1, "one resolution, one entry");
1881
1882        let _ = planner
1883            .resolve_diverse_return_paths(
1884                NodeId::Offchain(dest),
1885                RoutingOptions::Hops(1.try_into().expect("valid 1")),
1886                1,
1887            )
1888            .await
1889            .expect("return path resolution should succeed");
1890
1891        planner.cache.run_pending_tasks().await;
1892        assert_eq!(
1893            planner.cache.entry_count(),
1894            1,
1895            "naming the destination by packet key must hit the entry cached from its chain address"
1896        );
1897    }
1898
1899    #[tokio::test]
1900    async fn zero_hop_path_should_bypass_selector() {
1901        let me = pubkey(&SECRET_ME);
1902        let dest = pubkey(&SECRET_DEST);
1903
1904        // Build empty graph (no edges) — selector would fail if called.
1905        let graph = ChannelGraph::new(me);
1906        let cfg = small_config();
1907        let selector = HoprGraphPathSelector::new(
1908            me,
1909            graph,
1910            cfg.max_cached_paths,
1911            cfg.edge_penalty,
1912            cfg.min_ack_rate,
1913            cfg.min_paths_anonymity_floor,
1914        );
1915
1916        let chain_api = TestChainApi::new(me, me_addr(), vec![(dest, dest_addr())]);
1917        let surb_store = hopr_protocol_hopr::MemorySurbStore::default();
1918
1919        let planner = PathPlanner::new(me, surb_store, chain_api, selector, small_config());
1920
1921        let routing = DestinationRouting::Forward {
1922            destination: Box::new(NodeId::Offchain(dest)),
1923            pseudonym: None,
1924            forward_options: RoutingOptions::Hops(0.try_into().expect("valid 0")),
1925            return_options: None,
1926        };
1927
1928        let result = planner.resolve_routing(100, 0, routing).await;
1929        assert!(result.is_ok(), "zero-hop should succeed: {:?}", result.err());
1930
1931        let (resolved, rem, _) = result.unwrap();
1932        assert!(rem.is_none());
1933        if let ResolvedTransportRouting::Forward { forward_path, .. } = resolved {
1934            assert_eq!(
1935                forward_path.num_hops(),
1936                1,
1937                "zero-hop = 1 node in path (just destination)"
1938            );
1939        } else {
1940            panic!("expected Forward routing");
1941        }
1942    }
1943
1944    // ── test: one-hop path via graph selector ─────────────────────────────────
1945
1946    #[tokio::test]
1947    async fn one_hop_path_should_use_selector() {
1948        let me = pubkey(&SECRET_ME);
1949        let a = pubkey(&SECRET_A);
1950        let dest = pubkey(&SECRET_DEST);
1951
1952        let graph = ChannelGraph::new(me);
1953        graph.add_node(a);
1954        graph.add_node(dest);
1955        graph.add_edge(&me, &a).unwrap();
1956        graph.add_edge(&a, &dest).unwrap();
1957        mark_edge_full(&graph, &me, &a);
1958        mark_edge_full(&graph, &a, &dest);
1959
1960        let cfg = small_config();
1961        let selector = HoprGraphPathSelector::new(
1962            me,
1963            graph,
1964            cfg.max_cached_paths,
1965            cfg.edge_penalty,
1966            cfg.min_ack_rate,
1967            cfg.min_paths_anonymity_floor,
1968        );
1969
1970        let chain_api = TestChainApi::new(me, me_addr(), vec![(a, a_addr()), (dest, dest_addr())])
1971            .with_open_channel(me_addr(), a_addr())
1972            .with_open_channel(a_addr(), dest_addr());
1973
1974        let surb_store = hopr_protocol_hopr::MemorySurbStore::default();
1975        let planner = PathPlanner::new(me, surb_store, chain_api, selector, small_config());
1976
1977        let routing = DestinationRouting::Forward {
1978            destination: Box::new(NodeId::Offchain(dest)),
1979            pseudonym: None,
1980            forward_options: RoutingOptions::Hops(1.try_into().expect("valid 1")),
1981            return_options: None,
1982        };
1983
1984        let result = planner.resolve_routing(100, 0, routing).await;
1985        assert!(result.is_ok(), "1-hop routing should succeed: {:?}", result.err());
1986
1987        let (resolved, ..) = result.unwrap();
1988        if let ResolvedTransportRouting::Forward { forward_path, .. } = resolved {
1989            assert_eq!(
1990                forward_path.num_hops(),
1991                2,
1992                "1 intermediate hop means path has 2 nodes [a, dest]"
1993            );
1994        } else {
1995            panic!("expected Forward routing");
1996        }
1997    }
1998
1999    #[tokio::test]
2000    async fn explicit_intermediate_path_should_bypass_selector() {
2001        let me = pubkey(&SECRET_ME);
2002        let a = pubkey(&SECRET_A);
2003        let dest = pubkey(&SECRET_DEST);
2004
2005        // Empty graph — selector would fail; explicit path should not use it.
2006        let graph = ChannelGraph::new(me);
2007        let cfg = small_config();
2008        let selector = HoprGraphPathSelector::new(
2009            me,
2010            graph,
2011            cfg.max_cached_paths,
2012            cfg.edge_penalty,
2013            cfg.min_ack_rate,
2014            cfg.min_paths_anonymity_floor,
2015        );
2016
2017        let chain_api = TestChainApi::new(me, me_addr(), vec![(a, a_addr()), (dest, dest_addr())])
2018            .with_open_channel(me_addr(), a_addr())
2019            .with_open_channel(a_addr(), dest_addr());
2020
2021        let surb_store = hopr_protocol_hopr::MemorySurbStore::default();
2022        let planner = PathPlanner::new(me, surb_store, chain_api, selector, small_config());
2023
2024        use hopr_api::types::primitive::prelude::BoundedVec;
2025        let intermediate_path = BoundedVec::try_from(vec![NodeId::Offchain(a)]).expect("valid");
2026
2027        let routing = DestinationRouting::Forward {
2028            destination: Box::new(NodeId::Offchain(dest)),
2029            pseudonym: None,
2030            forward_options: RoutingOptions::IntermediatePath(intermediate_path),
2031            return_options: None,
2032        };
2033
2034        let result = planner.resolve_routing(100, 0, routing).await;
2035        assert!(result.is_ok(), "explicit path should succeed: {:?}", result.err());
2036
2037        let (resolved, ..) = result.unwrap();
2038        if let ResolvedTransportRouting::Forward { forward_path, .. } = resolved {
2039            assert_eq!(forward_path.num_hops(), 2, "one intermediate + destination = 2 hops");
2040        } else {
2041            panic!("expected Forward routing");
2042        }
2043    }
2044
2045    #[tokio::test]
2046    async fn return_routing_without_surb_should_return_error() {
2047        let me = pubkey(&SECRET_ME);
2048        let graph = ChannelGraph::new(me);
2049        let cfg = small_config();
2050        let selector = HoprGraphPathSelector::new(
2051            me,
2052            graph,
2053            cfg.max_cached_paths,
2054            cfg.edge_penalty,
2055            cfg.min_ack_rate,
2056            cfg.min_paths_anonymity_floor,
2057        );
2058        let chain_api = TestChainApi::new(me, me_addr(), vec![]);
2059        let surb_store = hopr_protocol_hopr::MemorySurbStore::default();
2060
2061        let planner = PathPlanner::new(me, surb_store, chain_api, selector, small_config());
2062
2063        use hopr_api::types::internal::routing::SurbMatcher;
2064        let matcher = SurbMatcher::Pseudonym(HoprPseudonym::random());
2065        let routing = DestinationRouting::Return(matcher);
2066
2067        let result = planner.resolve_routing(0, 0, routing).await;
2068        assert!(result.is_err(), "should fail when no SURB exists");
2069        assert!(
2070            matches!(result.unwrap_err(), PathPlannerError::Surb(_)),
2071            "error should be Surb variant"
2072        );
2073    }
2074
2075    // ── test: cache integration ───────────────────────────────────────────────
2076
2077    /// Builds a planner over `me -> a -> dest` with both channels open.
2078    fn diversity_planner(
2079        cfg: PathPlannerConfig,
2080    ) -> PathPlanner<hopr_protocol_hopr::MemorySurbStore, TestChainApi, HoprGraphPathSelector<ChannelGraph>> {
2081        let (me, a, dest) = (pubkey(&SECRET_ME), pubkey(&SECRET_A), pubkey(&SECRET_DEST));
2082
2083        let graph = ChannelGraph::new(me);
2084        graph.add_node(a);
2085        graph.add_node(dest);
2086        graph.add_edge(&me, &a).unwrap();
2087        graph.add_edge(&a, &dest).unwrap();
2088        graph.add_edge(&dest, &a).unwrap();
2089        graph.add_edge(&a, &me).unwrap();
2090        for (from, to) in [(me, a), (a, dest), (dest, a), (a, me)] {
2091            mark_edge_full(&graph, &from, &to);
2092        }
2093
2094        let selector = HoprGraphPathSelector::new(
2095            me,
2096            graph,
2097            cfg.max_cached_paths,
2098            cfg.edge_penalty,
2099            cfg.min_ack_rate,
2100            cfg.min_paths_anonymity_floor,
2101        );
2102        let chain_api = TestChainApi::new(me, me_addr(), vec![(a, a_addr()), (dest, dest_addr())])
2103            .with_open_channel(me_addr(), a_addr())
2104            .with_open_channel(a_addr(), dest_addr())
2105            .with_open_channel(dest_addr(), a_addr())
2106            .with_open_channel(a_addr(), me_addr());
2107
2108        PathPlanner::new(
2109            me,
2110            hopr_protocol_hopr::MemorySurbStore::default(),
2111            chain_api,
2112            selector,
2113            cfg,
2114        )
2115    }
2116
2117    #[tokio::test]
2118    async fn resolve_diverse_return_paths_should_return_empty_without_querying_when_none_requested() {
2119        let planner = diversity_planner(small_config());
2120        let dest = NodeId::Offchain(pubkey(&SECRET_DEST));
2121        let hops = RoutingOptions::Hops(1.try_into().expect("valid 1"));
2122
2123        // `max_surbs_with_message` returns 0 when the message fills the payload. That must yield an
2124        // empty result, not a `PathNotFound` — and must not populate the cache.
2125        let paths = planner
2126            .resolve_diverse_return_paths(dest, hops, 0)
2127            .await
2128            .expect("zero return paths is not an error");
2129        assert!(paths.is_empty());
2130
2131        // Keyed on resolved offchain keys, so the test names the nodes the same way.
2132        let dest_key = match dest {
2133            NodeId::Offchain(k) => k,
2134            NodeId::Chain(_) => unreachable!("the fixture names the destination by its packet key"),
2135        };
2136        let cache_key: PlannerCacheKey = (dest_key, pubkey(&SECRET_ME), 1);
2137        assert!(
2138            planner.cache.get(&cache_key).await.is_none(),
2139            "nothing requested must not query the planner"
2140        );
2141    }
2142
2143    #[tokio::test]
2144    async fn resolve_diverse_return_paths_should_return_count_paths_at_any_temper() {
2145        // Tempering changes *which* candidates are favoured, never how many paths come back — the
2146        // caller has already sized the batch to the SURBs that fit in its packet.
2147        for temper in [1.0, 0.5, 0.05] {
2148            let planner = diversity_planner(PathPlannerConfig {
2149                return_path_weight_temper: temper,
2150                ..small_config()
2151            });
2152            let dest = NodeId::Offchain(pubkey(&SECRET_DEST));
2153            let hops = RoutingOptions::Hops(1.try_into().expect("valid 1"));
2154
2155            let paths = planner
2156                .resolve_diverse_return_paths(dest, hops, 3)
2157                .await
2158                .expect("weighted resolution should succeed");
2159            assert_eq!(3, paths.len(), "temper={temper} must still return `count` paths");
2160        }
2161    }
2162
2163    #[tokio::test]
2164    async fn resolve_diverse_return_paths_should_fall_back_for_routing_without_alternatives() {
2165        let planner = diversity_planner(small_config());
2166        let dest = NodeId::Offchain(pubkey(&SECRET_DEST));
2167
2168        // A direct return has no relayer to spread over.
2169        let direct = planner
2170            .resolve_diverse_return_paths(dest, RoutingOptions::Hops(0.try_into().expect("valid 0")), 2)
2171            .await
2172            .expect("zero-hop return should resolve");
2173        assert_eq!(2, direct.len());
2174
2175        // An explicit path resolves to itself.
2176        let explicit = planner
2177            .resolve_diverse_return_paths(
2178                dest,
2179                RoutingOptions::IntermediatePath(vec![NodeId::Offchain(pubkey(&SECRET_A))].try_into().expect("valid")),
2180                2,
2181            )
2182            .await
2183            .expect("explicit return path should resolve");
2184        assert_eq!(2, explicit.len());
2185    }
2186
2187    #[tokio::test]
2188    async fn resolve_diverse_return_paths_should_return_the_requested_count() {
2189        let planner = diversity_planner(small_config());
2190        let dest = NodeId::Offchain(pubkey(&SECRET_DEST));
2191        let hops = RoutingOptions::Hops(1.try_into().expect("valid 1"));
2192
2193        // Fewer paths than the configured diversity: capped to `count`, still exactly `count` paths.
2194        for count in [1usize, 2, 5] {
2195            let paths = planner
2196                .resolve_diverse_return_paths(dest, hops.clone(), count)
2197                .await
2198                .expect("should resolve");
2199            assert_eq!(count, paths.len(), "count={count}");
2200        }
2201    }
2202
2203    #[tokio::test]
2204    async fn planner_cache_miss_should_populate_cache() {
2205        let me = pubkey(&SECRET_ME);
2206        let a = pubkey(&SECRET_A);
2207        let dest = pubkey(&SECRET_DEST);
2208
2209        let graph = ChannelGraph::new(me);
2210        graph.add_node(a);
2211        graph.add_node(dest);
2212        graph.add_edge(&me, &a).unwrap();
2213        graph.add_edge(&a, &dest).unwrap();
2214        mark_edge_full(&graph, &me, &a);
2215        mark_edge_full(&graph, &a, &dest);
2216
2217        let cfg = small_config();
2218        let selector = HoprGraphPathSelector::new(
2219            me,
2220            graph,
2221            cfg.max_cached_paths,
2222            cfg.edge_penalty,
2223            cfg.min_ack_rate,
2224            cfg.min_paths_anonymity_floor,
2225        );
2226        let chain_api = TestChainApi::new(me, me_addr(), vec![(a, a_addr()), (dest, dest_addr())])
2227            .with_open_channel(me_addr(), a_addr())
2228            .with_open_channel(a_addr(), dest_addr());
2229        let surb_store = hopr_protocol_hopr::MemorySurbStore::default();
2230        let planner = PathPlanner::new(me, surb_store, chain_api, selector, small_config());
2231
2232        let cache_key: PlannerCacheKey = (me, dest, 1);
2233
2234        assert!(
2235            planner.cache.get(&cache_key).await.is_none(),
2236            "cache should be empty before first call"
2237        );
2238
2239        let routing = DestinationRouting::Forward {
2240            destination: Box::new(NodeId::Offchain(dest)),
2241            pseudonym: None,
2242            forward_options: RoutingOptions::Hops(1.try_into().expect("valid 1")),
2243            return_options: None,
2244        };
2245        planner.resolve_routing(100, 0, routing).await.expect("should succeed");
2246
2247        let cached = planner.cache.get(&cache_key).await;
2248        assert!(cached.is_some(), "cache should be populated after first call");
2249        let paths = cached.unwrap();
2250        assert!(!paths.1.is_empty(), "cached paths must be non-empty");
2251        let (first_path, first_cost) = paths.1.iter().next().expect("at least one cached path");
2252        assert_eq!(first_path.num_hops(), 2, "path should have 2 hops [a, dest]");
2253        assert!(*first_cost > 0.0, "cost should be positive");
2254    }
2255
2256    #[tokio::test]
2257    async fn planner_cache_hit_should_return_valid_path() {
2258        let me = pubkey(&SECRET_ME);
2259        let a = pubkey(&SECRET_A);
2260        let dest = pubkey(&SECRET_DEST);
2261
2262        let graph = ChannelGraph::new(me);
2263        graph.add_node(a);
2264        graph.add_node(dest);
2265        graph.add_edge(&me, &a).unwrap();
2266        graph.add_edge(&a, &dest).unwrap();
2267        mark_edge_full(&graph, &me, &a);
2268        mark_edge_full(&graph, &a, &dest);
2269
2270        let cfg = small_config();
2271        let selector = HoprGraphPathSelector::new(
2272            me,
2273            graph,
2274            cfg.max_cached_paths,
2275            cfg.edge_penalty,
2276            cfg.min_ack_rate,
2277            cfg.min_paths_anonymity_floor,
2278        );
2279        let chain_api = TestChainApi::new(me, me_addr(), vec![(a, a_addr()), (dest, dest_addr())])
2280            .with_open_channel(me_addr(), a_addr())
2281            .with_open_channel(a_addr(), dest_addr());
2282        let surb_store = hopr_protocol_hopr::MemorySurbStore::default();
2283        let planner = PathPlanner::new(me, surb_store, chain_api, selector, small_config());
2284
2285        let make_routing = || DestinationRouting::Forward {
2286            destination: Box::new(NodeId::Offchain(dest)),
2287            pseudonym: None,
2288            forward_options: RoutingOptions::Hops(1.try_into().expect("valid 1")),
2289            return_options: None,
2290        };
2291
2292        let (r1, ..) = planner.resolve_routing(100, 0, make_routing()).await.expect("call 1");
2293        let (r2, ..) = planner.resolve_routing(100, 0, make_routing()).await.expect("call 2");
2294
2295        let hops1 = if let ResolvedTransportRouting::Forward { forward_path, .. } = r1 {
2296            forward_path.num_hops()
2297        } else {
2298            panic!("expected Forward");
2299        };
2300        let hops2 = if let ResolvedTransportRouting::Forward { forward_path, .. } = r2 {
2301            forward_path.num_hops()
2302        } else {
2303            panic!("expected Forward");
2304        };
2305        assert_eq!(hops1, 2);
2306        assert_eq!(hops2, 2);
2307    }
2308
2309    /// `resolve_routing` must capture the sending-side SURB generation for the packet's pseudonym at
2310    /// resolution time (adjacent to choosing the return paths), so the batch is later stamped with
2311    /// the generation of the plan it was minted for rather than one re-read at encode time.
2312    #[tokio::test]
2313    async fn resolve_routing_should_capture_the_current_surb_generation() {
2314        let me = pubkey(&SECRET_ME);
2315        let a = pubkey(&SECRET_A);
2316        let dest = pubkey(&SECRET_DEST);
2317
2318        let graph = ChannelGraph::new(me);
2319        graph.add_node(a);
2320        graph.add_node(dest);
2321        // Forward path me -> a -> dest, and a return path dest -> a -> me.
2322        graph.add_edge(&me, &a).unwrap();
2323        graph.add_edge(&a, &dest).unwrap();
2324        graph.add_edge(&dest, &a).unwrap();
2325        graph.add_edge(&a, &me).unwrap();
2326        mark_edge_full(&graph, &me, &a);
2327        mark_edge_full(&graph, &a, &dest);
2328        mark_edge_full(&graph, &dest, &a);
2329        mark_edge_full(&graph, &a, &me);
2330
2331        let cfg = small_config();
2332        let selector = HoprGraphPathSelector::new(
2333            me,
2334            graph,
2335            cfg.max_cached_paths,
2336            cfg.edge_penalty,
2337            cfg.min_ack_rate,
2338            cfg.min_paths_anonymity_floor,
2339        );
2340        let chain_api = TestChainApi::new(me, me_addr(), vec![(a, a_addr()), (dest, dest_addr())])
2341            .with_open_channel(me_addr(), a_addr())
2342            .with_open_channel(a_addr(), dest_addr())
2343            .with_open_channel(dest_addr(), a_addr())
2344            .with_open_channel(a_addr(), me_addr());
2345        let surb_store = hopr_protocol_hopr::MemorySurbStore::default();
2346        let planner = PathPlanner::new(me, surb_store, chain_api, selector, small_config());
2347
2348        let pseudonym = HoprPseudonym::random();
2349        // Advance the sending-side generation, as return-path re-plans would.
2350        planner.surb_store.bump_generation(&pseudonym);
2351        let expected = planner.surb_store.bump_generation(&pseudonym);
2352
2353        let routing = DestinationRouting::Forward {
2354            destination: Box::new(NodeId::Offchain(dest)),
2355            pseudonym: Some(pseudonym),
2356            forward_options: RoutingOptions::Hops(1.try_into().expect("valid 1")),
2357            return_options: Some(RoutingOptions::Hops(1.try_into().expect("valid 1"))),
2358        };
2359
2360        let (_resolved, _rem, generation) = planner
2361            .resolve_routing(100, 1, routing)
2362            .await
2363            .expect("resolution should succeed");
2364
2365        assert_eq!(
2366            generation,
2367            Some(expected),
2368            "resolve_routing must capture the store's current generation for the pseudonym"
2369        );
2370    }
2371
2372    #[tokio::test]
2373    async fn background_refresh_should_produce_a_future() {
2374        let me = pubkey(&SECRET_ME);
2375        let graph = ChannelGraph::new(me);
2376        let cfg = small_config();
2377        let selector = HoprGraphPathSelector::new(
2378            me,
2379            graph,
2380            cfg.max_cached_paths,
2381            cfg.edge_penalty,
2382            cfg.min_ack_rate,
2383            cfg.min_paths_anonymity_floor,
2384        );
2385        let chain_api = TestChainApi::new(me, me_addr(), vec![]);
2386        let surb_store = hopr_protocol_hopr::MemorySurbStore::default();
2387
2388        let planner = PathPlanner::new(me, surb_store, chain_api, selector, small_config());
2389        // Just ensure it compiles and produces a future.
2390        let _future = planner.run_background_refresh();
2391    }
2392
2393    // ── recomputing one cache entry in place ──────────────────────────────────
2394
2395    type TestPlanner =
2396        PathPlanner<hopr_protocol_hopr::MemorySurbStore, TestChainApi, HoprGraphPathSelector<ChannelGraph>>;
2397
2398    /// Return-path fixture with two interchangeable relayers: `dest -> {A, B} -> me`.
2399    ///
2400    /// Both start fully observed and identically good, so any later divergence in their share of
2401    /// the return draws is attributable to what the test recorded and not to the fixture.
2402    ///
2403    /// The graph is returned alongside the planner because it is the handle a test needs to move
2404    /// the evidence *under* an already-populated cache -- which is the whole point of the primitive
2405    /// under test.
2406    fn two_relayer_return_planner() -> (TestPlanner, ChannelGraph) {
2407        two_relayer_return_planner_with_floor(small_config().min_paths_anonymity_floor)
2408    }
2409
2410    /// A `me <- {a,b} <- dest` return topology with the given anonymity floor, so a test can watch
2411    /// the cap collapse the two relayers to one (or, at floor 0, keep both).
2412    fn two_relayer_return_planner_with_floor(floor: usize) -> (TestPlanner, ChannelGraph) {
2413        let me = pubkey(&SECRET_ME);
2414        let a = pubkey(&SECRET_A);
2415        let b = pubkey(&SECRET_B);
2416        let dest = pubkey(&SECRET_DEST);
2417
2418        let graph = ChannelGraph::new(me);
2419        for node in [a, b, dest] {
2420            graph.add_node(node);
2421        }
2422        for (src, dst) in [(dest, a), (a, me), (dest, b), (b, me)] {
2423            graph.add_edge(&src, &dst).expect("edge should be addable");
2424            // These return edges have SURB delivery evidence but no returning loopbacks.
2425            // Graph 0.12 trusts successful loops over delayed SURBs, so recording loops here
2426            // would prevent the recompute tests from modelling a delivery-rate collapse.
2427            graph.upsert_edge(&src, &dst, |obs| {
2428                use hopr_api::graph::traits::EdgeWeightType;
2429                obs.record(EdgeWeightType::Connected(true));
2430                obs.record(EdgeWeightType::Immediate(Ok(Duration::from_millis(50))));
2431                obs.record(EdgeWeightType::Balance(Some(1000u64.into())));
2432                obs.record(EdgeWeightType::SurbRoundTrips {
2433                    expected: 1_000,
2434                    observed: 1_000,
2435                });
2436            });
2437        }
2438
2439        let cfg = PathPlannerConfig {
2440            min_paths_anonymity_floor: floor,
2441            ..small_config()
2442        };
2443        let selector = HoprGraphPathSelector::new(
2444            me,
2445            graph.clone(),
2446            cfg.max_cached_paths,
2447            cfg.edge_penalty,
2448            cfg.min_ack_rate,
2449            cfg.min_paths_anonymity_floor,
2450        );
2451        let chain_api = TestChainApi::new(me, me_addr(), vec![(a, a_addr()), (b, b_addr()), (dest, dest_addr())])
2452            .with_open_channel(dest_addr(), a_addr())
2453            .with_open_channel(a_addr(), me_addr())
2454            .with_open_channel(dest_addr(), b_addr())
2455            .with_open_channel(b_addr(), me_addr());
2456
2457        let planner = PathPlanner::new(
2458            me,
2459            hopr_protocol_hopr::MemorySurbStore::default(),
2460            chain_api,
2461            selector,
2462            cfg,
2463        );
2464        (planner, graph)
2465    }
2466
2467    /// The mirror of [`two_relayer_return_planner`]: a `me -> {a,b} -> dest` forward topology.
2468    fn two_relayer_forward_planner() -> (TestPlanner, ChannelGraph) {
2469        let me = pubkey(&SECRET_ME);
2470        let a = pubkey(&SECRET_A);
2471        let b = pubkey(&SECRET_B);
2472        let dest = pubkey(&SECRET_DEST);
2473
2474        let graph = ChannelGraph::new(me);
2475        for node in [a, b, dest] {
2476            graph.add_node(node);
2477        }
2478        for (src, dst) in [(me, a), (a, dest), (me, b), (b, dest)] {
2479            graph.add_edge(&src, &dst).expect("edge should be addable");
2480            mark_edge_full(&graph, &src, &dst);
2481        }
2482
2483        let cfg = small_config();
2484        let selector = HoprGraphPathSelector::new(
2485            me,
2486            graph.clone(),
2487            cfg.max_cached_paths,
2488            cfg.edge_penalty,
2489            cfg.min_ack_rate,
2490            cfg.min_paths_anonymity_floor,
2491        );
2492        let chain_api = TestChainApi::new(me, me_addr(), vec![(a, a_addr()), (b, b_addr()), (dest, dest_addr())])
2493            .with_open_channel(me_addr(), a_addr())
2494            .with_open_channel(a_addr(), dest_addr())
2495            .with_open_channel(me_addr(), b_addr())
2496            .with_open_channel(b_addr(), dest_addr());
2497
2498        let planner = PathPlanner::new(
2499            me,
2500            hopr_protocol_hopr::MemorySurbStore::default(),
2501            chain_api,
2502            selector,
2503            cfg,
2504        );
2505        (planner, graph)
2506    }
2507
2508    /// Same `me <- {a,b} <- dest` return topology as [`two_relayer_return_planner_with_floor`], but
2509    /// `unresolvable` is left out of the chain resolver's key-to-address map -- present in the graph,
2510    /// so the selector still offers it as a candidate relayer, but `ValidatedPath::new` cannot map it
2511    /// to a chain address and drops every path through it. Floor 0, so pruning does not also remove
2512    /// it before validation gets the chance to.
2513    fn two_relayer_return_planner_with_unresolvable_relayer(
2514        unresolvable: OffchainPublicKey,
2515    ) -> (TestPlanner, ChannelGraph) {
2516        let me = pubkey(&SECRET_ME);
2517        let a = pubkey(&SECRET_A);
2518        let b = pubkey(&SECRET_B);
2519        let dest = pubkey(&SECRET_DEST);
2520
2521        let graph = ChannelGraph::new(me);
2522        for node in [a, b, dest] {
2523            graph.add_node(node);
2524        }
2525        for (src, dst) in [(dest, a), (a, me), (dest, b), (b, me)] {
2526            graph.add_edge(&src, &dst).expect("edge should be addable");
2527            mark_edge_full(&graph, &src, &dst);
2528        }
2529
2530        let cfg = PathPlannerConfig {
2531            min_paths_anonymity_floor: 0,
2532            ..small_config()
2533        };
2534        let selector = HoprGraphPathSelector::new(
2535            me,
2536            graph.clone(),
2537            cfg.max_cached_paths,
2538            cfg.edge_penalty,
2539            cfg.min_ack_rate,
2540            cfg.min_paths_anonymity_floor,
2541        );
2542        let resolvable_peers = [(a, a_addr()), (b, b_addr()), (dest, dest_addr())]
2543            .into_iter()
2544            .filter(|(key, _)| *key != unresolvable)
2545            .collect::<Vec<_>>();
2546        let chain_api = TestChainApi::new(me, me_addr(), resolvable_peers)
2547            .with_open_channel(dest_addr(), a_addr())
2548            .with_open_channel(a_addr(), me_addr())
2549            .with_open_channel(dest_addr(), b_addr())
2550            .with_open_channel(b_addr(), me_addr());
2551
2552        let planner = PathPlanner::new(
2553            me,
2554            hopr_protocol_hopr::MemorySurbStore::default(),
2555            chain_api,
2556            selector,
2557            cfg,
2558        );
2559        (planner, graph)
2560    }
2561
2562    /// Populates the return-path cache the way a Session does and hands back the cached entry.
2563    async fn fill_return_cache(planner: &TestPlanner) -> PlannerCacheValue {
2564        planner
2565            .resolve_diverse_return_paths(
2566                NodeId::Offchain(pubkey(&SECRET_DEST)),
2567                RoutingOptions::Hops(1.try_into().expect("valid 1")),
2568                1,
2569            )
2570            .await
2571            .expect("return path resolution should succeed");
2572        planner
2573            .cache
2574            .get(&(pubkey(&SECRET_DEST), pubkey(&SECRET_ME), 1))
2575            .await
2576            .expect("the return path should be cached after resolution")
2577    }
2578
2579    /// The diversity-collapse WARN must fire on the transition into the collapsed state, not on
2580    /// every rebuild while it persists (issue #8502): the collapsed-key set records the key on the
2581    /// first rebuild and a repeated rebuild of the same still-collapsed key does not re-record it, so
2582    /// the WARN is gated to the one transition.
2583    ///
2584    /// The inverse `remove` that clears the key on recovery (re-arming the WARN) is not driven here:
2585    /// the selector's candidate set is fixed for a given planner, so a live collapse->recovery
2586    /// transition on one key cannot be produced through this harness.
2587    #[tokio::test]
2588    async fn diversity_collapse_is_recorded_once_not_per_rebuild() {
2589        let dest = pubkey(&SECRET_DEST);
2590
2591        // Floor 1 caps the two relayers onto one, so the return path's diversity collapses.
2592        let (collapsed, _g) = two_relayer_return_planner_with_floor(1);
2593        fill_return_cache(&collapsed).await;
2594        assert_eq!(
2595            collapsed.collapsed_diversity_len(),
2596            1,
2597            "the first rebuild of a collapsed return path must record it"
2598        );
2599        // A repeated rebuild of the same still-collapsed key must not re-record it: the set is
2600        // unchanged, so the WARN is gated to the single transition.
2601        collapsed.recompute_paths_from(&dest).await;
2602        assert_eq!(
2603            collapsed.collapsed_diversity_len(),
2604            1,
2605            "a repeated rebuild of a still-collapsed key must not re-record it"
2606        );
2607    }
2608
2609    /// A return path that keeps every relayer must not record a collapse at all, so the WARN gate
2610    /// only trips on a real single-relayer collapse (issue #8502).
2611    #[tokio::test]
2612    async fn diverse_return_path_records_no_collapse() {
2613        let (diverse, _g) = two_relayer_return_planner_with_floor(0);
2614        let paths = fill_return_cache(&diverse).await;
2615        assert_eq!(
2616            2,
2617            candidate_set(&paths).len(),
2618            "vacuity guard: both relayers must survive"
2619        );
2620        assert_eq!(
2621            diverse.collapsed_diversity_len(),
2622            0,
2623            "a diverse return path must not record a collapse"
2624        );
2625    }
2626
2627    /// The collapsed-key tracker is bounded by the cache: when a key's cache entry leaves, its
2628    /// record is dropped too, so the set cannot grow without bound as keys churn (issue #8502). The
2629    /// cleanup is silent (it is not a diversity recovery).
2630    #[tokio::test]
2631    async fn evicting_a_cache_entry_drops_its_diversity_record() {
2632        let (me, dest) = (pubkey(&SECRET_ME), pubkey(&SECRET_DEST));
2633        let (planner, _g) = two_relayer_return_planner_with_floor(1);
2634        fill_return_cache(&planner).await;
2635        assert_eq!(planner.collapsed_diversity_len(), 1, "the collapsed key is recorded");
2636
2637        // Explicitly evict the entry, then drain moka's maintenance so the eviction listener runs.
2638        planner.cache.invalidate(&(dest, me, 1)).await;
2639        planner.cache.run_pending_tasks().await;
2640        assert_eq!(
2641            planner.collapsed_diversity_len(),
2642            0,
2643            "evicting the cache entry must drop its collapsed-state record"
2644        );
2645    }
2646
2647    /// A background refresh must not overwrite a route a `recompute_paths_from` installed from newer
2648    /// evidence while the sweep was rebuilding (raised on hoprnet#8486). The sweep reads an entry,
2649    /// rebuilds across awaits, then writes; a recompute that lands in between would otherwise be
2650    /// clobbered by the sweep's older selection, putting new-generation SURBs back on the route the
2651    /// recompute had just moved away from.
2652    #[tokio::test]
2653    async fn a_background_refresh_must_not_overwrite_a_recomputed_route() -> anyhow::Result<()> {
2654        let (planner, _graph) = two_relayer_return_planner();
2655        let key = (pubkey(&SECRET_DEST), pubkey(&SECRET_ME), 1);
2656
2657        // The sweep reads the entry it is about to rebuild from.
2658        let swept = fill_return_cache(&planner).await;
2659
2660        // A recompute from newer evidence installs a different entry at the same key.
2661        planner.recompute_paths_from(&pubkey(&SECRET_DEST)).await;
2662        let recomputed = planner
2663            .cache
2664            .get(&key)
2665            .await
2666            .context("the recompute should cache a route")?;
2667        assert!(
2668            !Arc::ptr_eq(&swept, &recomputed),
2669            "precondition: the recompute installed a new entry"
2670        );
2671
2672        // The sweep now writes its (older) rebuild. It must not land on the recomputed route.
2673        let wrote = put_if_unchanged(&planner.cache, key, &swept, swept.clone()).await;
2674        assert!(!wrote, "the sweep must not write over the entry the recompute replaced");
2675
2676        let current = planner.cache.get(&key).await.context("the entry is still cached")?;
2677        assert!(
2678            Arc::ptr_eq(&current, &recomputed),
2679            "the recomputed route is the one still served"
2680        );
2681        Ok(())
2682    }
2683
2684    /// The counterpart of the test above: while the entry the sweep read is still the one cached,
2685    /// its rebuild must land. Without this, a `put_if_unchanged` that never wrote would pass too.
2686    #[tokio::test]
2687    async fn a_background_refresh_should_replace_an_unchanged_entry() -> anyhow::Result<()> {
2688        let (planner, _graph) = two_relayer_return_planner();
2689        let key = (pubkey(&SECRET_DEST), pubkey(&SECRET_ME), 1);
2690        fill_return_cache(&planner).await;
2691
2692        // Read the entry the way the sweep does, from the cache iterator.
2693        let (_, swept) = planner
2694            .cache
2695            .iter()
2696            .find(|(k, _)| **k == key)
2697            .context("the filled entry should be iterable")?;
2698        let rebuilt = Arc::new(identify_candidates(hopr_utils::statistics::WeightedCollection::new(
2699            swept.1.iter().cloned().collect(),
2700        )));
2701
2702        let wrote = put_if_unchanged(&planner.cache, key, &swept, rebuilt.clone()).await;
2703        assert!(wrote, "the rebuild of an unchanged entry must be written");
2704
2705        let current = planner.cache.get(&key).await.context("the entry is still cached")?;
2706        assert!(
2707            Arc::ptr_eq(&current, &rebuilt),
2708            "the rebuilt route is the one now served"
2709        );
2710        Ok(())
2711    }
2712
2713    /// A neighbour that disconnects must stop being drawn as soon as the cache is refreshed, not
2714    /// up to a refresh period later.
2715    #[tokio::test]
2716    async fn refreshing_after_a_disconnect_should_drop_the_lost_relayer() -> anyhow::Result<()> {
2717        use hopr_api::graph::traits::EdgeWeightType;
2718
2719        let (planner, graph) = two_relayer_return_planner();
2720        let (me, b, dest) = (pubkey(&SECRET_ME), pubkey(&SECRET_B), pubkey(&SECRET_DEST));
2721
2722        let before = fill_return_cache(&planner).await;
2723        assert!(
2724            share_of(&before, &b) > 0.0,
2725            "vacuity guard: B must be a candidate first"
2726        );
2727
2728        for (src, dst) in [(me, b), (b, me)] {
2729            graph.upsert_edge(&src, &dst, |obs| obs.record(EdgeWeightType::Connected(false)));
2730        }
2731        planner.refresh_cached_paths().await;
2732
2733        let after = planner
2734            .cache
2735            .get(&(dest, me, 1))
2736            .await
2737            .context("the entry is still cached")?;
2738        assert_eq!(0.0, share_of(&after, &b), "the disconnected relayer must not be drawn");
2739        assert!(
2740            share_of(&after, &pubkey(&SECRET_A)) > 0.0,
2741            "the connected relayer must remain"
2742        );
2743        Ok(())
2744    }
2745
2746    /// A relayer judged dead is pruned by the traversal itself, in any position, instead of
2747    /// lingering at a floored but drawable weight.
2748    #[tokio::test]
2749    async fn a_relayer_judged_dead_should_leave_the_cached_paths() -> anyhow::Result<()> {
2750        use hopr_api::graph::NetworkGraphUpdate;
2751
2752        let (planner, graph) = two_relayer_return_planner();
2753        let (me, a, b, dest) = (
2754            pubkey(&SECRET_ME),
2755            pubkey(&SECRET_A),
2756            pubkey(&SECRET_B),
2757            pubkey(&SECRET_DEST),
2758        );
2759
2760        let before = fill_return_cache(&planner).await;
2761        assert!(
2762            share_of(&before, &b) > 0.0,
2763            "vacuity guard: B must be a candidate first"
2764        );
2765
2766        graph.record_node_health(&b, 0.0);
2767        planner.refresh_cached_paths().await;
2768
2769        let after = planner
2770            .cache
2771            .get(&(dest, me, 1))
2772            .await
2773            .context("the entry is still cached")?;
2774        assert_eq!(0.0, share_of(&after, &b), "the dead relayer must not be drawn");
2775        assert!(share_of(&after, &a) > 0.0, "the live relayer must remain");
2776        Ok(())
2777    }
2778
2779    #[tokio::test]
2780    async fn an_entry_left_without_a_route_should_leave_the_cache() -> anyhow::Result<()> {
2781        use hopr_api::graph::NetworkGraphUpdate;
2782
2783        let (planner, graph) = two_relayer_return_planner();
2784        let (me, dest) = (pubkey(&SECRET_ME), pubkey(&SECRET_DEST));
2785
2786        fill_return_cache(&planner).await;
2787        graph.record_node_health(&pubkey(&SECRET_A), 0.0);
2788        graph.record_node_health(&pubkey(&SECRET_B), 0.0);
2789        planner.refresh_cached_paths().await;
2790
2791        assert!(
2792            planner.cache.get(&(dest, me, 1)).await.is_none(),
2793            "no route must be served from an entry through dead relayers"
2794        );
2795        Ok(())
2796    }
2797
2798    /// Health is part of the walked value, so the return temper flattens it like any other quality;
2799    /// `HoprProtocolConfig::relayer_health_weight` sets how hard it bites.
2800    #[tokio::test]
2801    async fn a_stalled_relayer_should_have_its_share_cut_by_its_health() -> anyhow::Result<()> {
2802        use hopr_api::graph::NetworkGraphUpdate;
2803
2804        let (planner, graph) = two_relayer_return_planner();
2805        let (a, b) = (pubkey(&SECRET_A), pubkey(&SECRET_B));
2806        graph.record_node_health(&b, 1.0 / 16.0);
2807        planner.refresh_cached_paths().await;
2808
2809        let paths = planner
2810            .resolve_diverse_return_paths(
2811                NodeId::Offchain(pubkey(&SECRET_DEST)),
2812                RoutingOptions::Hops(1.try_into()?),
2813                4000,
2814            )
2815            .await?;
2816        let via_b = paths.iter().filter(|vp| vp.first() == Some(&b)).count();
2817        assert_eq!(4000, paths.len());
2818        // Untouched it would carry about half; a sixteenth of the health, tempered, leaves about a quarter.
2819        assert!(
2820            via_b < 1300,
2821            "the stalled relayer's share must shrink, got {via_b} of 4000"
2822        );
2823        assert!(
2824            via_b > 0,
2825            "a stalled relayer must stay drawable, or it can never prove recovery"
2826        );
2827        assert!(
2828            paths.iter().any(|vp| vp.first() == Some(&a)),
2829            "the healthy relayer must keep carrying the return stream"
2830        );
2831        Ok(())
2832    }
2833
2834    /// A forward draw explores like a return draw: the weaker relayer keeps a floor of the forward
2835    /// packets, so it stays measured and a session does not settle on one path. The health here is
2836    /// a sixteenth; tempered that is a quarter of the weight, and exploration adds a twentieth.
2837    #[tokio::test]
2838    async fn forward_draws_should_be_tempered_and_explored() -> anyhow::Result<()> {
2839        use hopr_api::graph::NetworkGraphUpdate;
2840
2841        let (planner, graph) = two_relayer_forward_planner();
2842        let (me, a, b, dest) = (
2843            pubkey(&SECRET_ME),
2844            pubkey(&SECRET_A),
2845            pubkey(&SECRET_B),
2846            pubkey(&SECRET_DEST),
2847        );
2848        graph.record_node_health(&b, 1.0 / 16.0);
2849        planner.refresh_cached_paths().await;
2850
2851        let mut via_b = 0;
2852        for _ in 0..4000 {
2853            let path = planner
2854                .resolve_path(
2855                    NodeId::Offchain(me),
2856                    NodeId::Offchain(dest),
2857                    RoutingOptions::Hops(1.try_into()?),
2858                )
2859                .await?;
2860            if path.first() == Some(&b) {
2861                via_b += 1;
2862            } else {
2863                assert_eq!(Some(&a), path.first(), "a forward path leaves through A or B");
2864            }
2865        }
2866        // Untempered and unexplored the weaker relayer would get about a seventeenth (~235); a
2867        // sixteenth of the health tempered to a quarter gives it about a fifth, plus the exploration.
2868        assert!(
2869            (500..1500).contains(&via_b),
2870            "the weaker relayer keeps a tempered share of the forward draws, got {via_b} of 4000"
2871        );
2872        Ok(())
2873    }
2874
2875    /// A forward draw never goes through a relayer the weights all but reject, such as one on
2876    /// probation, exploring or not. Ungated, its tempered weight alone drew it a few percent of the
2877    /// time, and uniform exploration added half of every tenth draw.
2878    #[tokio::test]
2879    async fn forward_draws_should_never_go_through_a_relayer_on_probation() -> anyhow::Result<()> {
2880        use hopr_api::graph::NetworkGraphUpdate;
2881
2882        let (planner, graph) = two_relayer_forward_planner();
2883        let (me, b, dest) = (pubkey(&SECRET_ME), pubkey(&SECRET_B), pubkey(&SECRET_DEST));
2884        graph.record_node_health(&b, 1e-3);
2885        planner.refresh_cached_paths().await;
2886
2887        let mut via_b = 0;
2888        for _ in 0..4000 {
2889            let path = planner
2890                .resolve_path(
2891                    NodeId::Offchain(me),
2892                    NodeId::Offchain(dest),
2893                    RoutingOptions::Hops(1.try_into()?),
2894                )
2895                .await?;
2896            if path.first() == Some(&b) {
2897                via_b += 1;
2898            }
2899        }
2900        // Ungated, the tempered weight alone drew about 0.9 x 4000 x sqrt(1e-3) / (1 + sqrt(1e-3)) ~ 110,
2901        // and uniform exploration over both candidates about 310.
2902        assert_eq!(
2903            0, via_b,
2904            "a relayer on probation draws no forward packet, got {via_b} of 4000"
2905        );
2906        Ok(())
2907    }
2908
2909    #[test]
2910    fn gating_should_zero_only_the_implausible_weights() {
2911        let mut weights = [1.0, 0.8, 0.1, 0.03, 0.0];
2912        gate_implausible(&mut weights);
2913        assert_eq!(
2914            [1.0, 0.8, 0.1, 0.0, 0.0],
2915            weights,
2916            "a tenth of the best stays plausible, anything less is zeroed"
2917        );
2918        assert!(
2919            (0..2000).filter_map(|_| pick_weighted_index(&weights)).all(|i| i < 3),
2920            "a weighted draw over the gated weights never lands on an implausible candidate"
2921        );
2922
2923        let mut nothing = [0.0, 0.0];
2924        gate_implausible(&mut nothing);
2925        assert_eq!(None, pick_weighted_index(&nothing), "nothing to draw from");
2926    }
2927
2928    #[test]
2929    fn exploring_draws_should_skip_implausible_candidates_unless_granted() {
2930        let weights = [1.0, 0.8, 0.01];
2931        let denied = (0..2000)
2932            .filter_map(|_| pick_exploring_index(&weights, || false))
2933            .collect::<Vec<_>>();
2934        assert!(
2935            denied.iter().all(|&i| i != 2),
2936            "never the implausible one without a grant"
2937        );
2938        let first = denied.iter().filter(|&&i| i == 0).count();
2939        assert!(
2940            (800..1200).contains(&first),
2941            "uniform over the plausible two, got {first} of 2000 for the first"
2942        );
2943
2944        let granted = (0..3000)
2945            .filter_map(|_| pick_exploring_index(&weights, || true))
2946            .filter(|&i| i == 2)
2947            .count();
2948        assert!(
2949            (800..1200).contains(&granted),
2950            "uniform over all three when granted, got {granted}"
2951        );
2952
2953        assert_eq!(None, pick_exploring_index(&[0.0, 0.0], || true), "nothing to draw from");
2954    }
2955
2956    #[test]
2957    fn the_probe_budget_should_grant_one_probe_per_interval() {
2958        let budget = ProbeBudget::default();
2959        assert!(budget.take(), "the first probe is granted");
2960        assert!((0..100).all(|_| !budget.take()), "none more within the interval");
2961    }
2962
2963    /// From races to the draw: a relayer losing its races by seconds is judged, recorded in the graph,
2964    /// and the re-plan that follows cuts its share of the cached return paths.
2965    #[tokio::test]
2966    async fn a_relayer_losing_its_races_should_have_its_share_cut() -> anyhow::Result<()> {
2967        use crate::protocol::surb_telemetry::{SurbRoundTripRegistry, refresh_relayer_health};
2968
2969        let (planner, graph) = two_relayer_return_planner();
2970        let (a, b) = (pubkey(&SECRET_A), pubkey(&SECRET_B));
2971        let before = share_of(&fill_return_cache(&planner).await, &b);
2972
2973        let registry = SurbRoundTripRegistry::default();
2974        let health = registry.relayer_health();
2975        let leg = |relayer| {
2976            let mut leg = [None; crate::protocol::surb_telemetry::PATH_ID_SLOTS];
2977            leg[0] = Some(relayer);
2978            leg
2979        };
2980        for seed in 0..10u8 {
2981            health.record_race(
2982                &leg(b),
2983                [seed; 8],
2984                &leg(a),
2985                Duration::from_millis(200),
2986                Duration::from_secs(3),
2987            );
2988        }
2989        refresh_relayer_health(&registry, &graph, 4, 1.0, || planner.refresh_cached_paths()).await;
2990
2991        let after = share_of(&fill_return_cache(&planner).await, &b);
2992        assert!(
2993            after < before / 2.0,
2994            "the late relayer's share must fall, from {before} to {after}"
2995        );
2996        assert!(share_of(&fill_return_cache(&planner).await, &a) > 0.5);
2997        Ok(())
2998    }
2999
3000    /// Share of the collection's total weight held by candidates whose first hop is `relayer`.
3001    ///
3002    /// This -- not the raw weight -- is what decides how much of a session's return stream rides on
3003    /// one relay, because the draw normalises over the collection.
3004    fn share_of(paths: &PlannerCacheValue, relayer: &OffchainPublicKey) -> f64 {
3005        let total: f64 = paths.1.iter().map(|(_, w)| *w).sum();
3006        let held: f64 = paths
3007            .1
3008            .iter()
3009            .filter(|(vp, _)| vp.first() == Some(relayer))
3010            .map(|(_, w)| *w)
3011            .sum();
3012        if total > 0.0 { held / total } else { 0.0 }
3013    }
3014
3015    /// The candidate paths as stable strings, weights discarded.
3016    fn candidate_set(paths: &PlannerCacheValue) -> std::collections::BTreeSet<String> {
3017        paths.1.iter().map(|(vp, _)| vp.to_string()).collect()
3018    }
3019
3020    /// Records failed loopbacks on the edge, so the graph's starvation rule reads its relay as dead.
3021    ///
3022    /// hopr-network-graph 0.12.0 keeps an edge at its loopback rate while the loops over it still
3023    /// come back, and that rate floors the SURB traffic rate (hoprnet/hoprnet#8650). A relay that
3024    /// drops SURBs and answers loops is deliberately no longer starved, so a test that wants a
3025    /// relay the planner must re-weight has to kill its loops as well.
3026    ///
3027    /// [`mark_edge_full`] records one returned intermediate loop per edge, so the rate is 100 %.
3028    /// The default starvation threshold is a 10 % return rate once three loops count, so the
3029    /// twelve failures below take the rate to 1/13, under it. They have to be intermediate
3030    /// measurements: only those feed the loopback window, an immediate one feeds the link average.
3031    fn record_failed_loops(graph: &ChannelGraph, src: &OffchainPublicKey, dst: &OffchainPublicKey) {
3032        use hopr_api::graph::traits::EdgeWeightType;
3033        graph.upsert_edge(src, dst, |obs| {
3034            for _ in 0..12 {
3035                obs.record(EdgeWeightType::Intermediate(Err(())));
3036            }
3037        });
3038    }
3039
3040    /// Records `rounds` SURB round-trips on the edge, of which `observed` per round came back.
3041    fn record_surbs(
3042        graph: &ChannelGraph,
3043        src: &OffchainPublicKey,
3044        dst: &OffchainPublicKey,
3045        expected: u64,
3046        observed: u64,
3047    ) {
3048        use hopr_api::graph::traits::EdgeWeightType;
3049        graph.upsert_edge(src, dst, |obs| {
3050            obs.record(EdgeWeightType::SurbRoundTrips { expected, observed });
3051        });
3052    }
3053
3054    /// A relay that stops delivering must lose its share of the return draws *without* the
3055    /// candidate set changing underneath the live session.
3056    ///
3057    /// Both halves matter and they pull against each other: dropping the candidates is what
3058    /// collapsed a healthy session from 100 % to 0.14 % in the cluster, while leaving the weights
3059    /// alone is what kept minting SURBs onto a dead relay for a full refresh period.
3060    #[tokio::test]
3061    async fn recomputing_an_entry_should_reweight_the_candidates_without_changing_the_set() {
3062        let (planner, graph) = two_relayer_return_planner();
3063        let (me, b, dest) = (pubkey(&SECRET_ME), pubkey(&SECRET_B), pubkey(&SECRET_DEST));
3064
3065        let before = fill_return_cache(&planner).await;
3066        let set_before = candidate_set(&before);
3067        let share_before = share_of(&before, &b);
3068
3069        assert_eq!(
3070            set_before.len(),
3071            2,
3072            "the fixture must offer both relayers as candidates"
3073        );
3074        assert!(
3075            share_before > 0.2,
3076            "vacuity guard: B must hold a material share before the collapse, held {share_before}"
3077        );
3078
3079        // A delivers, B stops. Same interval, so the contrast is in the evidence and not in time.
3080        record_surbs(&graph, &dest, &pubkey(&SECRET_A), 1_000, 1_000);
3081        record_surbs(&graph, &dest, &b, 1_000, 1_000);
3082        record_surbs(&graph, &dest, &b, 4_000, 0);
3083        // B's loops stop with its SURBs: a graph that floors the traffic rate at the loopback rate
3084        // keeps a relay whose loops still come back (hopr-network-graph 0.12.0).
3085        record_failed_loops(&graph, &dest, &b);
3086
3087        let replaced = planner.recompute_paths_from(&dest).await;
3088        assert_eq!(
3089            replaced, 1,
3090            "exactly the one cached return entry should have been rebuilt"
3091        );
3092
3093        let after = planner
3094            .cache
3095            .get(&(dest, me, 1))
3096            .await
3097            .expect("the entry must still exist after a recompute");
3098
3099        assert_eq!(
3100            candidate_set(&after),
3101            set_before,
3102            "a recompute must re-weight the candidates, never replace the set"
3103        );
3104
3105        let share_after = share_of(&after, &b);
3106        assert!(
3107            share_after < share_before,
3108            "the relay that stopped delivering must lose share: {share_before} -> {share_after}"
3109        );
3110    }
3111
3112    /// A recompute that finds nothing must leave the previous candidates in place.
3113    ///
3114    /// This is the property that separates recomputation from invalidation. A live session draws
3115    /// its next return path from this entry, so an empty result has to mean "no better information"
3116    /// rather than "no route".
3117    #[tokio::test]
3118    async fn recomputing_an_entry_should_keep_the_old_candidates_when_it_finds_none() {
3119        let (planner, graph) = two_relayer_return_planner();
3120        let (me, dest) = (pubkey(&SECRET_ME), pubkey(&SECRET_DEST));
3121
3122        let before = fill_return_cache(&planner).await;
3123        let set_before = candidate_set(&before);
3124
3125        // Total blackout: every route out of the destination disappears from the graph, so the
3126        // selector can no longer offer any candidate at all.
3127        for relay in [pubkey(&SECRET_A), pubkey(&SECRET_B)] {
3128            graph.remove_edge(&dest, &relay);
3129        }
3130
3131        let replaced = planner.recompute_paths_from(&dest).await;
3132        assert_eq!(replaced, 0, "a recompute that finds nothing must replace nothing");
3133
3134        let after = planner
3135            .cache
3136            .get(&(dest, me, 1))
3137            .await
3138            .expect("an entry must never be dropped by a recompute that found nothing");
3139        assert_eq!(
3140            candidate_set(&after),
3141            set_before,
3142            "the previous candidates must survive a fruitless recompute"
3143        );
3144    }
3145
3146    /// A recompute is addressed at one counterparty, so it must not sweep the whole cache.
3147    ///
3148    /// Rebuilding every entry on every detection would put the cost of one dead relay onto every
3149    /// other session the node is carrying.
3150    /// A recompute that lands on the same weights has moved no traffic, and the caller uses that
3151    /// answer to decide whether refilling is worth anything.
3152    ///
3153    /// Reporting the number of entries *rebuilt* instead would say "moved" every time, since a
3154    /// rebuild always succeeds on a healthy graph -- and refilling behind a re-plan that changed
3155    /// nothing just mints more SURBs onto the same route.
3156    #[tokio::test]
3157    async fn a_recompute_that_lands_on_the_same_weights_should_report_nothing_moved() {
3158        let (planner, graph) = two_relayer_return_planner();
3159        let dest = pubkey(&SECRET_DEST);
3160
3161        let _ = fill_return_cache(&planner).await;
3162
3163        assert_eq!(
3164            planner.recompute_paths_from(&dest).await,
3165            0,
3166            "nothing about the graph changed, so no traffic can have moved"
3167        );
3168
3169        // Vacuity guard: the same call must report movement once the evidence actually shifts.
3170        // B has to deliver first -- the rate is read against a peak, so a relayer that never had
3171        // one has no rate to fall from and the collapse would be invisible.
3172        record_surbs(&graph, &dest, &pubkey(&SECRET_A), 1_000, 1_000);
3173        record_surbs(&graph, &dest, &pubkey(&SECRET_B), 1_000, 1_000);
3174        record_surbs(&graph, &dest, &pubkey(&SECRET_B), 4_000, 0);
3175        record_failed_loops(&graph, &dest, &pubkey(&SECRET_B));
3176        assert_eq!(
3177            planner.recompute_paths_from(&dest).await,
3178            1,
3179            "a collapse on one relayer must register as moved"
3180        );
3181    }
3182
3183    /// End-to-end proof of the fix: a disabled cap keeps every return relayer, a cap of one
3184    /// collapses the stream onto a single relayer. The latter is the blind spot the degradation
3185    /// detector cannot escape, and the shape of the 2026-08-28 outage; the former is what the
3186    /// edge-client `latency_path_planner_config` now requests (`min_paths_anonymity_floor = 0`).
3187    #[tokio::test]
3188    async fn floor_zero_keeps_every_return_relayer_but_a_cap_of_one_collapses_it() {
3189        let (a, b) = (pubkey(&SECRET_A), pubkey(&SECRET_B));
3190
3191        let (uncapped, _g) = two_relayer_return_planner_with_floor(0);
3192        let paths = fill_return_cache(&uncapped).await;
3193        assert_eq!(2, candidate_set(&paths).len(), "floor 0 keeps both return relayers");
3194        assert!(
3195            share_of(&paths, &a) > 0.0,
3196            "relayer a carries part of the return stream"
3197        );
3198        assert!(
3199            share_of(&paths, &b) > 0.0,
3200            "relayer b carries part of the return stream"
3201        );
3202
3203        let (capped, _g) = two_relayer_return_planner_with_floor(1);
3204        let paths = fill_return_cache(&capped).await;
3205        assert_eq!(1, candidate_set(&paths).len(), "floor 1 collapses to a single relayer");
3206    }
3207
3208    /// Regression for the diversity check firing on the wrong set: the selector's raw candidates
3209    /// see both relayers, but chain validation rejects every path through `b` (its key never
3210    /// resolves to a chain address), so what a session can actually draw from has collapsed to `a`
3211    /// alone. A diversity check computed on the selector's pre-validation output would have missed
3212    /// this entirely -- it must be computed on the validated survivors, which is what
3213    /// `PathBuilder::rebuild` now does.
3214    #[tokio::test]
3215    async fn validation_rejecting_one_relayer_should_collapse_diversity_even_though_the_selector_saw_two() {
3216        let (a, b) = (pubkey(&SECRET_A), pubkey(&SECRET_B));
3217
3218        let (planner, _g) = two_relayer_return_planner_with_unresolvable_relayer(b);
3219        let paths = fill_return_cache(&planner).await;
3220
3221        assert_eq!(
3222            1,
3223            candidate_set(&paths).len(),
3224            "only the relayer that resolves on-chain should survive validation"
3225        );
3226        assert!(
3227            share_of(&paths, &a) > 0.0,
3228            "the resolvable relayer must carry the whole return stream"
3229        );
3230        assert_eq!(
3231            0.0,
3232            share_of(&paths, &b),
3233            "the unresolvable relayer must not appear among the validated candidates"
3234        );
3235    }
3236
3237    #[tokio::test]
3238    async fn recomputing_should_rebuild_only_the_entries_originating_at_that_peer() {
3239        let (planner, graph) = two_relayer_return_planner();
3240        let (me, a, dest) = (pubkey(&SECRET_ME), pubkey(&SECRET_A), pubkey(&SECRET_DEST));
3241
3242        let _ = fill_return_cache(&planner).await;
3243        // Something has to actually move, or the count below would be zero for the wrong reason.
3244        record_surbs(&graph, &dest, &a, 1_000, 1_000);
3245        record_surbs(&graph, &dest, &pubkey(&SECRET_B), 1_000, 1_000);
3246        record_surbs(&graph, &dest, &pubkey(&SECRET_B), 4_000, 0);
3247        record_failed_loops(&graph, &dest, &pubkey(&SECRET_B));
3248        // A second entry in the other direction, which no `dest` recompute may touch.
3249        let _ = planner
3250            .cached_paths(
3251                NodeId::Offchain(me),
3252                NodeId::Offchain(a),
3253                1.try_into().expect("valid 1"),
3254            )
3255            .await;
3256
3257        assert_eq!(
3258            planner.recompute_paths_from(&dest).await,
3259            1,
3260            "only the entry whose paths start at the named peer should be re-weighted"
3261        );
3262        assert_eq!(
3263            planner.recompute_paths_from(&pubkey(&SECRET_B)).await,
3264            0,
3265            "a peer with no cached entries of its own must rebuild nothing"
3266        );
3267    }
3268
3269    #[tokio::test]
3270    #[serial_test::serial(routing_logs)]
3271    async fn installation_events_should_report_only_committed_cache_updates() -> anyhow::Result<()> {
3272        use tracing::instrument::WithSubscriber;
3273
3274        let (planner, _) = two_relayer_return_planner();
3275        let key = (pubkey(&SECRET_DEST), pubkey(&SECRET_ME), 1);
3276        let logs = crate::tests::support::Logs::default();
3277        async {
3278            let hops = 1.try_into()?;
3279            let paths = futures::future::try_join_all(
3280                (0..8).map(|_| planner.cached_paths(NodeId::Offchain(key.0), NodeId::Offchain(key.1), hops)),
3281            )
3282            .await?;
3283            assert!(paths.iter().all(|path| Arc::ptr_eq(path, &paths[0])));
3284            assert!(logs.records("candidate set installed").is_empty());
3285            let hit = planner
3286                .cached_paths(NodeId::Offchain(key.0), NodeId::Offchain(key.1), 1.try_into()?)
3287                .await?;
3288            assert!(Arc::ptr_eq(&hit, &paths[0]));
3289            assert_eq!(
3290                logs.records("candidate set installed").len(),
3291                0,
3292                "hits must not report an installation"
3293            );
3294
3295            planner.recompute_paths_from(&key.0).await;
3296            let replacement = planner.cache.get(&key).await.context("recomputed entry")?;
3297            assert!(!put_if_unchanged(&planner.cache, key, &paths[0], paths[0].clone()).await);
3298            assert_eq!(
3299                logs.records("candidate set installed").len(),
3300                1,
3301                "a stale refresh must not report an installation"
3302            );
3303            let rebuilt = Arc::new(identify_candidates(hopr_utils::statistics::WeightedCollection::new(
3304                replacement.1.iter().cloned().collect(),
3305            )));
3306            assert!(put_if_unchanged(&planner.cache, key, &replacement, rebuilt).await);
3307            let events = logs.records("candidate set installed");
3308            assert_eq!(
3309                events
3310                    .iter()
3311                    .map(|event| event.fields["kind"].as_str())
3312                    .collect::<Vec<_>>(),
3313                ["recompute", "background-refresh"]
3314            );
3315            for event in events {
3316                assert!(event.fields.contains_key("source"));
3317                assert!(event.fields.contains_key("destination"));
3318                assert_eq!(event.fields["hops"], "1");
3319                assert_eq!(event.fields["candidates"], replacement.1.len().to_string());
3320            }
3321            anyhow::Ok(())
3322        }
3323        .with_subscriber(logs.subscriber(tracing::Level::DEBUG))
3324        .await
3325    }
3326
3327    /// Run with `--profile release` too, to detect compile-time ceilings on TRACE diagnostics.
3328    #[rstest::rstest]
3329    #[case(tracing::Level::DEBUG, false)]
3330    #[case(tracing::Level::TRACE, true)]
3331    #[tokio::test]
3332    #[serial_test::serial(routing_logs)]
3333    async fn return_candidates_and_draw_details_should_require_trace_logging(
3334        #[case] level: tracing::Level,
3335        #[case] expect_details: bool,
3336    ) -> anyhow::Result<()> {
3337        use tracing::instrument::WithSubscriber;
3338
3339        let (planner, _) = two_relayer_return_planner();
3340        // Keep callsite interest responsive to scoped subscribers used by concurrent tests.
3341        let _other_dispatch = tracing::Dispatch::new(tracing::subscriber::NoSubscriber::default());
3342        let logs = crate::tests::support::Logs::default();
3343        let drawn = planner
3344            .resolve_diverse_return_paths(
3345                NodeId::Offchain(pubkey(&SECRET_DEST)),
3346                RoutingOptions::Hops(1.try_into()?),
3347                2,
3348            )
3349            .with_subscriber(logs.subscriber(level))
3350            .await?;
3351        assert_eq!(drawn.len(), 2);
3352        assert_eq!(
3353            logs.records("candidate validation").len(),
3354            1,
3355            "keep rebuild summaries at DEBUG"
3356        );
3357        let before = logs.records("drawing return paths from tempered weights");
3358        let after = logs.records("drew return paths");
3359        let candidates = logs.records("weighted candidate path");
3360        if expect_details {
3361            assert_eq!(candidates.len(), 2, "TRACE must retain the candidate dictionary");
3362            assert_eq!(before.len(), 1);
3363            assert_eq!(after.len(), 1);
3364            assert_eq!(before[0].fields["count"], "2");
3365            assert_eq!(before[0].fields["candidates"], "2");
3366            assert_eq!(before[0].fields["distinct_relayers"], "2");
3367            assert!(before[0].fields.contains_key("temper"));
3368            assert!(before[0].fields.contains_key("exploration"));
3369            let distinct = drawn
3370                .iter()
3371                .filter_map(|path| path.first())
3372                .collect::<std::collections::HashSet<_>>()
3373                .len();
3374            assert_eq!(after[0].fields["drawn"], "2");
3375            assert_eq!(after[0].fields["of_candidates"], "2");
3376            assert_eq!(after[0].fields["distinct_relayers"], distinct.to_string());
3377        } else {
3378            assert!(candidates.is_empty(), "per-candidate weights must not appear at DEBUG");
3379            assert!(before.is_empty(), "per-packet draw details must not appear at DEBUG");
3380            assert!(after.is_empty(), "per-packet draw results must not appear at DEBUG");
3381        }
3382        Ok(())
3383    }
3384
3385    /// Cached snapshots keep their dictionary identity; replacements and other planners get new IDs.
3386    /// Every logged draw must reference the dictionary entry for the path actually returned.
3387    // Expand the proc macro before `test`: the pinned nightly otherwise crashes while
3388    // tokenizing the compiler-generated test entrypoint attribute.
3389    #[serial_test::serial(routing_logs)]
3390    #[test]
3391    fn candidate_dictionary_should_correlate_cached_snapshots_and_actual_draws() -> anyhow::Result<()> {
3392        let (planner, _) = two_relayer_return_planner();
3393        let (forward_planner, _) = two_relayer_forward_planner();
3394        // Keep multiple dispatchers registered: tracing-core's single-dispatcher fast path can
3395        // cache a callsite as disabled when another test first uses it without a scoped subscriber.
3396        let _other_dispatch = tracing::Dispatch::new(tracing::subscriber::NoSubscriber::default());
3397        let logs = crate::tests::support::Logs::default();
3398        let runtime = tokio::runtime::Builder::new_current_thread().enable_all().build()?;
3399        let subscriber = logs.subscriber(tracing::Level::TRACE);
3400        let selected = tracing::subscriber::with_default(subscriber, || {
3401            runtime.block_on(async {
3402                let source = NodeId::Offchain(pubkey(&SECRET_DEST));
3403                let destination = NodeId::Offchain(pubkey(&SECRET_ME));
3404                let first = planner.cached_paths(source, destination, 1.try_into()?).await?;
3405                let dictionary_size = logs.records("weighted candidate path").len();
3406                let hit = planner.cached_paths(source, destination, 1.try_into()?).await?;
3407                assert!(Arc::ptr_eq(&first, &hit));
3408                assert_eq!(logs.records("weighted candidate path").len(), dictionary_size);
3409                let mut selected = planner
3410                    .resolve_diverse_return_paths(source, RoutingOptions::Hops(1.try_into()?), 2)
3411                    .await?
3412                    .iter()
3413                    .map(ToString::to_string)
3414                    .collect::<Vec<_>>();
3415                planner.recompute_paths_from(&pubkey(&SECRET_DEST)).await;
3416                let replacement = planner.cached_paths(source, destination, 1.try_into()?).await?;
3417                assert!(!Arc::ptr_eq(&first, &replacement));
3418                selected.extend(
3419                    planner
3420                        .resolve_diverse_return_paths(source, RoutingOptions::Hops(1.try_into()?), 2)
3421                        .await?
3422                        .iter()
3423                        .map(ToString::to_string),
3424                );
3425                for _ in 0..2 {
3426                    selected.push(
3427                        forward_planner
3428                            .resolve_path(destination, source, RoutingOptions::Hops(1.try_into()?))
3429                            .await?
3430                            .to_string(),
3431                    );
3432                }
3433                anyhow::Ok(selected)
3434            })
3435        })?;
3436        let dictionary = logs.records("weighted candidate path");
3437        let draws = logs.records("candidate selected");
3438        assert_eq!(selected.len(), 6, "fixture must return the requested paths");
3439        assert_eq!(
3440            draws.len(),
3441            6,
3442            "each actual draw must have a dictionary reference: {}",
3443            logs.output()
3444        );
3445        for (draw, selected) in draws.iter().zip(selected) {
3446            let entry = dictionary
3447                .iter()
3448                .find(|entry| {
3449                    entry.fields["set_id"] == draw.fields["set_id"] && entry.fields["index"] == draw.fields["index"]
3450                })
3451                .context("draw must reference a recorded dictionary entry")?;
3452            assert_eq!(entry.fields["path"], selected);
3453        }
3454        let ids: std::collections::HashSet<_> = dictionary.iter().map(|entry| entry.fields["set_id"].clone()).collect();
3455        assert_eq!(
3456            ids.len(),
3457            3,
3458            "initial, replacement and other planner snapshots must be distinct"
3459        );
3460        assert_eq!(draws[0].fields["set_id"], draws[1].fields["set_id"]);
3461        assert_ne!(draws[1].fields["set_id"], draws[2].fields["set_id"]);
3462        assert_eq!(draws[4].fields["set_id"], draws[5].fields["set_id"]);
3463        Ok(())
3464    }
3465
3466    // ── composite weight helpers ──────────────────────────────────────────────
3467
3468    #[tokio::test]
3469    #[serial_test::serial(routing_logs)]
3470    async fn routing_children_should_inherit_the_session_without_repeating_its_fields() -> anyhow::Result<()> {
3471        use tracing::{Instrument, instrument::WithSubscriber};
3472
3473        let (planner, _) = two_relayer_return_planner();
3474        let logs = crate::tests::support::Logs::default();
3475        async {
3476            let session = tracing::debug_span!("session", session_id = 123);
3477            async {
3478                planner
3479                    .resolve_path(
3480                        NodeId::Offchain(pubkey(&SECRET_DEST)),
3481                        NodeId::Offchain(pubkey(&SECRET_ME)),
3482                        RoutingOptions::Hops(1.try_into()?),
3483                    )
3484                    .await?;
3485                anyhow::Ok(())
3486            }
3487            .instrument(session)
3488            .await
3489        }
3490        .with_subscriber(logs.subscriber(tracing::Level::TRACE))
3491        .await?;
3492
3493        let records = logs.records("graph traversal completed");
3494        assert!(!records.is_empty(), "routing must perform a graph traversal");
3495        // The selector can run multiple traversals while spreading candidates across relayers.
3496        // Check the context of every query instead of assuming one particular search strategy.
3497        for record in &records {
3498            let (traversal, parents) = record.ancestry.split_last().context("missing graph traversal span")?;
3499            assert!(matches!(*traversal, "graph.simple_paths" | "graph.simple_paths_from"));
3500            assert_eq!(
3501                parents,
3502                [
3503                    "session",
3504                    "planner.resolve_path",
3505                    "planner.cached_paths",
3506                    "planner.rebuild_candidates",
3507                    "selector.select_paths"
3508                ]
3509            );
3510            assert!(!record.fields.contains_key("session_id"));
3511        }
3512        let output = logs.output();
3513        let line = output
3514            .lines()
3515            .find(|line| line.contains("graph traversal completed"))
3516            .context("missing formatted graph record")?;
3517        assert!(line.contains("session_id=123"), "{line}");
3518        let selector_fields = line
3519            .split_once("selector.select_paths{")
3520            .and_then(|(_, fields)| fields.split_once('}'))
3521            .map(|(fields, _)| fields)
3522            .context("missing formatted selector span fields")?;
3523        assert!(
3524            selector_fields.split_whitespace().any(|field| field == "hops=1"),
3525            "selector span must record the requested hop count: {line}"
3526        );
3527        Ok(())
3528    }
3529
3530    #[tokio::test]
3531    #[serial_test::serial(routing_logs)]
3532    async fn filtered_routing_spans_should_not_modify_the_caller() -> anyhow::Result<()> {
3533        use tracing::{Instrument, instrument::WithSubscriber};
3534
3535        let (planner, _) = two_relayer_return_planner();
3536        let logs = crate::tests::support::Logs::default();
3537        async {
3538            async {
3539                planner
3540                    .resolve_path(
3541                        NodeId::Offchain(pubkey(&SECRET_DEST)),
3542                        NodeId::Offchain(pubkey(&SECRET_ME)),
3543                        RoutingOptions::Hops(1.try_into()?),
3544                    )
3545                    .await?;
3546                tracing::trace!("caller fields retained");
3547                anyhow::Ok(())
3548            }
3549            .instrument(tracing::debug_span!("caller", direction = "caller-direction"))
3550            .await
3551        }
3552        .with_subscriber(logs.subscriber_disabling_spans(
3553            tracing::Level::TRACE,
3554            &["planner.cached_paths", "selector.select_paths"],
3555        ))
3556        .await?;
3557        let output = logs.output();
3558        let line = output
3559            .lines()
3560            .find(|line| line.contains("caller fields retained"))
3561            .context("missing caller record")?;
3562        assert!(line.contains("direction=\"caller-direction\""), "{line}");
3563        Ok(())
3564    }
3565
3566    fn default_weighting() -> WeightingParams {
3567        WeightingParams {
3568            latency_halflife: Duration::from_millis(100),
3569            capacity_reference: 10_000_000,
3570            return_path_weight_temper: 1.0,
3571            return_path_exploration: 0.0,
3572        }
3573    }
3574
3575    fn make_pwm(cost: f64, latency_ms: Option<u32>, fundable_tickets_floor: Option<u128>) -> PathWithMetrics {
3576        PathWithMetrics {
3577            path: vec![],
3578            cost,
3579            total_latency_ms: latency_ms,
3580            min_probe_success_rate: None,
3581            min_ack_rate: None,
3582            fundable_tickets_floor,
3583        }
3584    }
3585
3586    #[test]
3587    fn latency_factor_is_monotonic_decreasing() {
3588        let halflife = Duration::from_millis(100);
3589        let f0 = latency_factor(Duration::ZERO, halflife);
3590        let f100 = latency_factor(Duration::from_millis(100), halflife);
3591        let f200 = latency_factor(Duration::from_millis(200), halflife);
3592        assert!(
3593            f0 > f100 && f100 > f200,
3594            "must be strictly decreasing: {f0} > {f100} > {f200}"
3595        );
3596        assert!(
3597            (f100 - 0.5).abs() < 1e-9,
3598            "at halflife factor should be 0.5, got {f100}"
3599        );
3600        assert!(f0 <= 1.0, "factor must never exceed 1.0, got {f0}");
3601    }
3602
3603    #[test]
3604    fn capacity_factor_is_monotonic_increasing() {
3605        let reference = 10_000_000u128;
3606        let f_low = capacity_factor(100, reference);
3607        let f_mid = capacity_factor(1_000_000, reference);
3608        let f_ref = capacity_factor(reference, reference);
3609        assert!(
3610            f_low < f_mid && f_mid <= f_ref,
3611            "must be non-decreasing: {f_low} < {f_mid} <= {f_ref}"
3612        );
3613        assert!(f_ref <= 1.0, "factor must not exceed 1.0 at reference, got {f_ref}");
3614        assert!(f_low >= 0.05, "minimum clamp is 0.05, got {f_low}");
3615    }
3616
3617    #[test]
3618    fn composite_weight_for_0_hop_skips_capacity_factor() {
3619        let params = default_weighting();
3620        let pwm = make_pwm(0.6, Some(100), None);
3621        let w = composite_weight(&pwm, 0, params);
3622        let expected = 0.6 * latency_factor(Duration::from_millis(100), params.latency_halflife);
3623        assert!(
3624            (w - expected).abs() < 1e-9,
3625            "0-hop weight should ignore capacity: {w} != {expected}"
3626        );
3627        assert!(w > 0.0, "0-hop weight must be positive");
3628    }
3629
3630    #[test]
3631    fn composite_weight_with_all_aggregates_is_below_cost() {
3632        let params = default_weighting();
3633        let pwm = make_pwm(0.8, Some(150), Some(5_000_000));
3634        let w = composite_weight(&pwm, 1, params);
3635        assert!(
3636            w < pwm.cost,
3637            "composite must be below raw cost when factors < 1.0: {w} >= {}",
3638            pwm.cost
3639        );
3640        assert!(w > 0.0, "composite weight must be positive");
3641    }
3642
3643    #[test]
3644    fn composite_weight_missing_capacity_on_multi_hop_neutral() {
3645        let params = default_weighting();
3646        let pwm_with = make_pwm(0.7, Some(80), Some(8_000_000));
3647        let pwm_without = make_pwm(0.7, Some(80), None);
3648        let w_with = composite_weight(&pwm_with, 2, params);
3649        let w_without = composite_weight(&pwm_without, 2, params);
3650        // Missing capacity is neutral (1.0), so without-capacity weight equals cost * lat only.
3651        let expected_without = 0.7 * latency_factor(Duration::from_millis(80), params.latency_halflife);
3652        assert!((w_without - expected_without).abs() < 1e-9);
3653        // With capacity the factor adds further reduction (capacity_factor < 1.0 here).
3654        assert!(w_with <= w_without, "known capacity should not increase the weight");
3655    }
3656    #[tokio::test]
3657    /// Verify canonical peer identities and the unresolved chain-address fallback in observer events.
3658    async fn observer_canonicalizes_chain_addresses_and_retains_unresolvable_destinations() -> anyhow::Result<()> {
3659        let events = Arc::new(parking_lot::Mutex::new(Vec::new()));
3660        let (planner, _) = two_relayer_return_planner();
3661        let planner = planner.with_observer(Arc::new({
3662            let events = events.clone();
3663            move |event| events.lock().push(event)
3664        }));
3665        let me = NodeId::Offchain(planner.me);
3666        planner
3667            .resolve_path(me, NodeId::Chain(dest_addr()), RoutingOptions::Hops(0.try_into()?))
3668            .await?;
3669        planner
3670            .resolve_path(NodeId::Chain(dest_addr()), me, RoutingOptions::Hops(1.try_into()?))
3671            .await?;
3672        let unknown = NodeId::Chain(Address::from([99; 20]));
3673        assert!(
3674            planner
3675                .resolve_path(me, unknown, RoutingOptions::Hops(1.try_into()?))
3676                .await
3677                .is_err()
3678        );
3679        let events = events.lock();
3680        assert_eq!(events.len(), 3);
3681        assert!(matches!(&events[0], TransportEvent::PathResolved {
3682            direction: PathDirection::Forward, destination, succeeded: true,
3683        } if *destination == NodeId::Offchain(pubkey(&SECRET_DEST))));
3684        assert!(matches!(&events[1], TransportEvent::PathResolved {
3685            direction: PathDirection::Return, destination, succeeded: true,
3686        } if *destination == NodeId::Offchain(pubkey(&SECRET_DEST))));
3687        assert!(matches!(&events[2], TransportEvent::PathResolved {
3688            direction: PathDirection::Forward, destination, succeeded: false,
3689        } if *destination == unknown));
3690        Ok(())
3691    }
3692
3693    #[tokio::test]
3694    /// Report cached return batches and failed resolves without counting them as graph searches.
3695    async fn observer_sees_cached_return_batches_and_resolution_failures() -> anyhow::Result<()> {
3696        let events = Arc::new(parking_lot::Mutex::new(Vec::new()));
3697        let (planner, _) = two_relayer_return_planner();
3698        let planner = planner.with_observer(Arc::new({
3699            let events = events.clone();
3700            move |event| events.lock().push(event)
3701        }));
3702        let source = NodeId::Offchain(pubkey(&SECRET_DEST));
3703        for _ in 0..2 {
3704            planner
3705                .resolve_diverse_return_paths(source, RoutingOptions::Hops(1.try_into()?), 2)
3706                .await?;
3707        }
3708        assert!(
3709            planner
3710                .resolve_path(
3711                    NodeId::Offchain(planner.me),
3712                    NodeId::Offchain(pubkey(&[99; 32])),
3713                    RoutingOptions::Hops(1.try_into()?)
3714                )
3715                .await
3716                .is_err()
3717        );
3718        let resolved: Vec<_> = events
3719            .lock()
3720            .iter()
3721            .filter_map(|event| match event {
3722                TransportEvent::PathResolved {
3723                    direction,
3724                    destination,
3725                    succeeded,
3726                } => Some((*direction, *destination, *succeeded)),
3727                _ => None,
3728            })
3729            .collect();
3730        assert_eq!(
3731            2,
3732            resolved
3733                .iter()
3734                .filter(|r| **r == (PathDirection::Return, source, true))
3735                .count(),
3736            "each cached return batch is one resolve"
3737        );
3738        assert_eq!(1, resolved.iter().filter(|(_, _, succeeded)| !succeeded).count());
3739        assert_eq!(3, resolved.len(), "the planner reports resolves only, no searches");
3740        Ok(())
3741    }
3742}