Skip to main content

karma_cigarette_spotting/
lib.rs

1//! Deterministic hotspot analysis for karma settlement ledgers.
2//!
3//! The Cocoshiga spotting principle is observational: preserve the source
4//! ledger, rank unresolved positions by absolute size, and report how much of
5//! the total imbalance the selected spots explain.
6//!
7//! ```
8//! use karma_cigarette_spotting::{CocoshigaSpot, KarmaLedger, SpotRole};
9//!
10//! let mut ledger = KarmaLedger::new();
11//! ledger.record("alice", "bob", 10, "support")?;
12//! ledger.record("carol", "bob", 5, "review")?;
13//!
14//! let report = CocoshigaSpot::analyze(&ledger)?;
15//! let hottest = report.hottest().unwrap();
16//! assert_eq!(hottest.party().as_str(), "bob");
17//! assert_eq!(hottest.role(), SpotRole::Payer);
18//! assert_eq!(hottest.units(), 15);
19//! # Ok::<(), karma_cigarette_spotting::SpotError>(())
20//! ```
21
22use std::error::Error;
23use std::fmt::{self, Display, Formatter};
24use std::num::NonZeroUsize;
25
26pub use karma_cigarette::{KarmaEntry, KarmaError, KarmaLedger, PartyId};
27
28/// Selects which unresolved positions appear in a spot report.
29#[derive(Clone, Copy, Debug, PartialEq, Eq)]
30pub struct SpotPolicy {
31    minimum_units: u128,
32    limit: Option<NonZeroUsize>,
33}
34
35impl SpotPolicy {
36    /// Creates a policy that includes every non-zero position.
37    pub const fn new() -> Self {
38        Self {
39            minimum_units: 1,
40            limit: None,
41        }
42    }
43
44    /// Hides positions whose absolute size is below this value.
45    ///
46    /// A value of zero includes every non-zero position, like the default
47    /// minimum of one.
48    pub const fn with_minimum_units(mut self, minimum_units: u128) -> Self {
49        self.minimum_units = minimum_units;
50        self
51    }
52
53    /// Restricts the report to its first `limit` spots.
54    pub fn with_limit(mut self, limit: usize) -> Result<Self, SpotError> {
55        self.limit = Some(NonZeroUsize::new(limit).ok_or(SpotError::ZeroLimit)?);
56        Ok(self)
57    }
58
59    /// Removes the result limit.
60    pub const fn without_limit(mut self) -> Self {
61        self.limit = None;
62        self
63    }
64
65    /// Minimum absolute units required for a spot.
66    pub const fn minimum_units(self) -> u128 {
67        self.minimum_units
68    }
69
70    /// Maximum number of spots, or `None` when unlimited.
71    pub const fn limit(self) -> Option<NonZeroUsize> {
72        self.limit
73    }
74}
75
76impl Default for SpotPolicy {
77    fn default() -> Self {
78        Self::new()
79    }
80}
81
82/// Which side of final settlement a spot occupies.
83#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
84pub enum SpotRole {
85    /// The party has a positive balance and should receive units.
86    Recipient,
87    /// The party has a negative balance and should pay units.
88    Payer,
89}
90
91/// One highlighted unresolved party position.
92#[derive(Clone, Debug, PartialEq, Eq)]
93pub struct KarmaSpot {
94    party: PartyId,
95    role: SpotRole,
96    units: u128,
97    share_basis_points: u16,
98}
99
100impl KarmaSpot {
101    /// Highlighted party.
102    pub fn party(&self) -> &PartyId {
103        &self.party
104    }
105
106    /// Whether the party should receive or pay.
107    pub const fn role(&self) -> SpotRole {
108        self.role
109    }
110
111    /// Absolute unresolved units for the party.
112    pub const fn units(&self) -> u128 {
113        self.units
114    }
115
116    /// Share of total absolute imbalance in basis points.
117    ///
118    /// One basis point is 0.01%. Values use integer truncation.
119    pub const fn share_basis_points(&self) -> u16 {
120        self.share_basis_points
121    }
122}
123
124/// Immutable result of spotting a ledger.
125#[derive(Clone, Debug, PartialEq, Eq)]
126pub struct SpotReport {
127    spots: Vec<KarmaSpot>,
128    settlement_units: u128,
129    total_absolute_units: u128,
130    coverage_basis_points: u16,
131    omitted_parties: usize,
132    conserved: bool,
133}
134
135impl SpotReport {
136    /// Selected spots in descending absolute size and stable party order.
137    pub fn spots(&self) -> &[KarmaSpot] {
138        &self.spots
139    }
140
141    /// The first and largest selected spot.
142    pub fn hottest(&self) -> Option<&KarmaSpot> {
143        self.spots.first()
144    }
145
146    /// Iterates over selected spots on one settlement side.
147    pub fn for_role(&self, role: SpotRole) -> impl Iterator<Item = &KarmaSpot> {
148        self.spots.iter().filter(move |spot| spot.role == role)
149    }
150
151    /// Total units that must cross from payers to recipients.
152    pub const fn settlement_units(&self) -> u128 {
153        self.settlement_units
154    }
155
156    /// Sum of the absolute values of all non-zero party balances.
157    ///
158    /// For a conserved ledger this is twice `settlement_units`.
159    pub const fn total_absolute_units(&self) -> u128 {
160        self.total_absolute_units
161    }
162
163    /// Portion of total absolute imbalance represented by selected spots.
164    pub const fn coverage_basis_points(&self) -> u16 {
165        self.coverage_basis_points
166    }
167
168    /// Non-zero party positions hidden by threshold or result limit.
169    pub const fn omitted_parties(&self) -> usize {
170        self.omitted_parties
171    }
172
173    /// Whether total receivables exactly equal total payables.
174    pub const fn is_conserved(&self) -> bool {
175        self.conserved
176    }
177}
178
179/// Implements the Cocoshiga hotspot analysis.
180#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
181pub struct CocoshigaSpot;
182
183impl CocoshigaSpot {
184    /// Analyzes every non-zero position with the default policy.
185    pub fn analyze(ledger: &KarmaLedger) -> Result<SpotReport, SpotError> {
186        Self::analyze_with(ledger, SpotPolicy::new())
187    }
188
189    /// Analyzes a ledger using an explicit selection policy.
190    pub fn analyze_with(ledger: &KarmaLedger, policy: SpotPolicy) -> Result<SpotReport, SpotError> {
191        let balances = ledger.balances().map_err(SpotError::Karma)?;
192        let mut recipients = 0u128;
193        let mut payers = 0u128;
194        let mut all_spots = Vec::new();
195
196        for (party, balance) in balances {
197            let (role, units) = if balance > 0 {
198                let units = balance as u128;
199                recipients = recipients.checked_add(units).ok_or(SpotError::Overflow)?;
200                (SpotRole::Recipient, units)
201            } else if balance < 0 {
202                let units = balance.unsigned_abs();
203                payers = payers.checked_add(units).ok_or(SpotError::Overflow)?;
204                (SpotRole::Payer, units)
205            } else {
206                continue;
207            };
208            all_spots.push((party, role, units));
209        }
210
211        let total_absolute_units = recipients.checked_add(payers).ok_or(SpotError::Overflow)?;
212        let conserved = recipients == payers;
213        if !conserved {
214            return Err(SpotError::Unbalanced);
215        }
216
217        all_spots.sort_by(|left, right| right.2.cmp(&left.2).then_with(|| left.0.cmp(&right.0)));
218        let nonzero_parties = all_spots.len();
219        all_spots.retain(|spot| spot.2 >= policy.minimum_units.max(1));
220        if let Some(limit) = policy.limit {
221            all_spots.truncate(limit.get());
222        }
223
224        let mut selected_units = 0u128;
225        let spots = all_spots
226            .into_iter()
227            .map(|(party, role, units)| {
228                selected_units = selected_units
229                    .checked_add(units)
230                    .ok_or(SpotError::Overflow)?;
231                Ok(KarmaSpot {
232                    party,
233                    role,
234                    units,
235                    share_basis_points: ratio_basis_points(units, total_absolute_units)?,
236                })
237            })
238            .collect::<Result<Vec<_>, SpotError>>()?;
239        let omitted_parties = nonzero_parties - spots.len();
240
241        Ok(SpotReport {
242            spots,
243            settlement_units: recipients,
244            total_absolute_units,
245            coverage_basis_points: ratio_basis_points(selected_units, total_absolute_units)?,
246            omitted_parties,
247            conserved,
248        })
249    }
250}
251
252fn ratio_basis_points(part: u128, whole: u128) -> Result<u16, SpotError> {
253    if whole == 0 {
254        return Ok(0);
255    }
256    let scaled = part.checked_mul(10_000).ok_or(SpotError::Overflow)? / whole;
257    u16::try_from(scaled).map_err(|_| SpotError::Overflow)
258}
259
260/// Failure returned while configuring or performing spot analysis.
261#[derive(Clone, Debug, PartialEq, Eq)]
262#[non_exhaustive]
263pub enum SpotError {
264    /// The source karma ledger could not compute its balances.
265    Karma(KarmaError),
266    /// A result limit of zero was requested.
267    ZeroLimit,
268    /// Checked analysis arithmetic overflowed.
269    Overflow,
270    /// Total receivables and payables did not match.
271    Unbalanced,
272}
273
274impl Display for SpotError {
275    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
276        match self {
277            Self::Karma(error) => write!(f, "karma error: {error}"),
278            Self::ZeroLimit => f.write_str("spot limit must be greater than zero"),
279            Self::Overflow => f.write_str("spot analysis arithmetic overflowed"),
280            Self::Unbalanced => f.write_str("karma balances are not conserved"),
281        }
282    }
283}
284
285impl Error for SpotError {
286    fn source(&self) -> Option<&(dyn Error + 'static)> {
287        match self {
288            Self::Karma(error) => Some(error),
289            Self::ZeroLimit | Self::Overflow | Self::Unbalanced => None,
290        }
291    }
292}
293
294impl From<KarmaError> for SpotError {
295    fn from(value: KarmaError) -> Self {
296        Self::Karma(value)
297    }
298}
299
300#[cfg(test)]
301mod tests {
302    use super::*;
303
304    fn sample_ledger() -> KarmaLedger {
305        let mut ledger = KarmaLedger::new();
306        ledger.record("alice", "bob", 10, "support").unwrap();
307        ledger.record("carol", "bob", 5, "review").unwrap();
308        ledger
309    }
310
311    #[test]
312    fn largest_position_is_spotted_first() {
313        let report = CocoshigaSpot::analyze(&sample_ledger()).unwrap();
314        let hottest = report.hottest().unwrap();
315
316        assert_eq!(hottest.party().as_str(), "bob");
317        assert_eq!(hottest.role(), SpotRole::Payer);
318        assert_eq!(hottest.units(), 15);
319        assert_eq!(hottest.share_basis_points(), 5_000);
320        assert_eq!(report.settlement_units(), 15);
321        assert_eq!(report.total_absolute_units(), 30);
322        assert_eq!(report.coverage_basis_points(), 10_000);
323        assert!(report.is_conserved());
324    }
325
326    #[test]
327    fn ties_are_resolved_by_party_identifier() {
328        let mut ledger = KarmaLedger::new();
329        ledger.record("zeta", "beta", 5, "").unwrap();
330        ledger.record("alpha", "yota", 5, "").unwrap();
331
332        let report = CocoshigaSpot::analyze(&ledger).unwrap();
333        let names: Vec<_> = report
334            .spots()
335            .iter()
336            .map(|spot| spot.party().as_str())
337            .collect();
338        assert_eq!(names, ["alpha", "beta", "yota", "zeta"]);
339    }
340
341    #[test]
342    fn threshold_and_limit_report_omissions_and_coverage() {
343        let mut ledger = sample_ledger();
344        ledger.record("dora", "erin", 1, "small").unwrap();
345        let policy = SpotPolicy::new()
346            .with_minimum_units(2)
347            .with_limit(2)
348            .unwrap();
349
350        let report = CocoshigaSpot::analyze_with(&ledger, policy).unwrap();
351        assert_eq!(report.spots().len(), 2);
352        assert_eq!(report.omitted_parties(), 3);
353        assert_eq!(report.coverage_basis_points(), 7_812);
354    }
355
356    #[test]
357    fn fully_netted_ledger_has_no_spots() {
358        let mut ledger = KarmaLedger::new();
359        ledger.record("alice", "bob", 4, "").unwrap();
360        ledger.record("bob", "alice", 4, "").unwrap();
361
362        let report = CocoshigaSpot::analyze(&ledger).unwrap();
363        assert!(report.spots().is_empty());
364        assert_eq!(report.settlement_units(), 0);
365        assert_eq!(report.coverage_basis_points(), 0);
366        assert!(report.is_conserved());
367    }
368
369    #[test]
370    fn zero_limit_is_rejected() {
371        assert_eq!(
372            SpotPolicy::new().with_limit(0).unwrap_err(),
373            SpotError::ZeroLimit
374        );
375    }
376
377    #[test]
378    fn analysis_does_not_mutate_the_ledger() {
379        let ledger = sample_ledger();
380        let before = ledger.clone();
381        CocoshigaSpot::analyze(&ledger).unwrap();
382        assert_eq!(ledger, before);
383    }
384}