Skip to main content

karma_cigarette/
lib.rs

1//! Deterministic karma accounting and net settlement.
2//!
3//! The crate models the **Cocoshiga principle**: record contributions, cancel
4//! reciprocal obligations, preserve every party's net position, and emit only
5//! the transfers still required for settlement.
6//!
7//! A contribution from a giver to a receiver makes the giver a creditor and
8//! the receiver a debtor by the recorded number of units.
9//!
10//! ```
11//! use karma_cigarette::{Cocoshiga, KarmaLedger};
12//!
13//! let mut ledger = KarmaLedger::new();
14//! ledger.record("aya", "ben", 8, "helped with a task")?;
15//! ledger.record("ben", "aya", 3, "returned the favor")?;
16//!
17//! let plan = Cocoshiga::settle(&ledger)?;
18//! assert_eq!(plan.transfers()[0].units(), 5);
19//! assert!(plan.is_conserved());
20//! # Ok::<(), karma_cigarette::KarmaError>(())
21//! ```
22
23use std::collections::BTreeMap;
24use std::error::Error;
25use std::fmt::{self, Display, Formatter};
26
27/// A stable, non-empty identifier for a party in a ledger.
28#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
29pub struct PartyId(String);
30
31impl PartyId {
32    /// Creates a validated party identifier.
33    pub fn new(value: impl Into<String>) -> Result<Self, KarmaError> {
34        let value = value.into();
35        if value.trim().is_empty() {
36            return Err(KarmaError::EmptyParty);
37        }
38        Ok(Self(value))
39    }
40
41    /// Returns the identifier as text.
42    pub fn as_str(&self) -> &str {
43        &self.0
44    }
45}
46
47impl Display for PartyId {
48    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
49        f.write_str(&self.0)
50    }
51}
52
53impl AsRef<str> for PartyId {
54    fn as_ref(&self) -> &str {
55        self.as_str()
56    }
57}
58
59/// One contribution recorded in a [`KarmaLedger`].
60#[derive(Clone, Debug, PartialEq, Eq)]
61pub struct KarmaEntry {
62    giver: PartyId,
63    receiver: PartyId,
64    units: u64,
65    memo: String,
66}
67
68impl KarmaEntry {
69    /// Creates and validates an entry.
70    pub fn new(
71        giver: impl Into<String>,
72        receiver: impl Into<String>,
73        units: u64,
74        memo: impl Into<String>,
75    ) -> Result<Self, KarmaError> {
76        let giver = PartyId::new(giver)?;
77        let receiver = PartyId::new(receiver)?;
78        if giver == receiver {
79            return Err(KarmaError::SameParty);
80        }
81        if units == 0 {
82            return Err(KarmaError::ZeroUnits);
83        }
84        Ok(Self {
85            giver,
86            receiver,
87            units,
88            memo: memo.into(),
89        })
90    }
91
92    /// The party that supplied the contribution.
93    pub fn giver(&self) -> &PartyId {
94        &self.giver
95    }
96
97    /// The party that received the contribution.
98    pub fn receiver(&self) -> &PartyId {
99        &self.receiver
100    }
101
102    /// The positive number of units transferred by the contribution.
103    pub fn units(&self) -> u64 {
104        self.units
105    }
106
107    /// Application-defined context attached to the entry.
108    pub fn memo(&self) -> &str {
109        &self.memo
110    }
111}
112
113/// An append-only collection of karma entries.
114#[derive(Clone, Debug, Default, PartialEq, Eq)]
115pub struct KarmaLedger {
116    entries: Vec<KarmaEntry>,
117}
118
119impl KarmaLedger {
120    /// Creates an empty ledger.
121    pub const fn new() -> Self {
122        Self {
123            entries: Vec::new(),
124        }
125    }
126
127    /// Records a validated contribution.
128    pub fn record(
129        &mut self,
130        giver: impl Into<String>,
131        receiver: impl Into<String>,
132        units: u64,
133        memo: impl Into<String>,
134    ) -> Result<&KarmaEntry, KarmaError> {
135        let entry = KarmaEntry::new(giver, receiver, units, memo)?;
136        self.entries.push(entry);
137        Ok(self
138            .entries
139            .last()
140            .expect("an entry was inserted immediately before access"))
141    }
142
143    /// Appends a previously validated entry.
144    pub fn push(&mut self, entry: KarmaEntry) -> &KarmaEntry {
145        self.entries.push(entry);
146        self.entries
147            .last()
148            .expect("an entry was inserted immediately before access")
149    }
150
151    /// Returns all entries in insertion order.
152    pub fn entries(&self) -> &[KarmaEntry] {
153        &self.entries
154    }
155
156    /// Returns whether no contributions have been recorded.
157    pub fn is_empty(&self) -> bool {
158        self.entries.is_empty()
159    }
160
161    /// Returns the number of recorded contributions.
162    pub fn len(&self) -> usize {
163        self.entries.len()
164    }
165
166    /// Computes each party's net position.
167    ///
168    /// Positive values are receivables and negative values are payables.
169    pub fn balances(&self) -> Result<BTreeMap<PartyId, i128>, KarmaError> {
170        let mut balances = BTreeMap::<PartyId, i128>::new();
171        for entry in &self.entries {
172            let units = i128::from(entry.units);
173            add_balance(&mut balances, &entry.giver, units)?;
174            add_balance(&mut balances, &entry.receiver, -units)?;
175        }
176        Ok(balances)
177    }
178
179    /// Returns one party's net position, or zero when the party is absent.
180    pub fn balance_of(&self, party: &str) -> Result<i128, KarmaError> {
181        Ok(self
182            .balances()?
183            .into_iter()
184            .find_map(|(id, balance)| (id.as_str() == party).then_some(balance))
185            .unwrap_or(0))
186    }
187}
188
189fn add_balance(
190    balances: &mut BTreeMap<PartyId, i128>,
191    party: &PartyId,
192    delta: i128,
193) -> Result<(), KarmaError> {
194    let current = balances.entry(party.clone()).or_default();
195    *current = current.checked_add(delta).ok_or(KarmaError::Overflow)?;
196    Ok(())
197}
198
199/// A payment required to satisfy a net karma position.
200#[derive(Clone, Debug, PartialEq, Eq)]
201pub struct SettlementTransfer {
202    from: PartyId,
203    to: PartyId,
204    units: u128,
205}
206
207impl SettlementTransfer {
208    /// Party that should pay.
209    pub fn from(&self) -> &PartyId {
210        &self.from
211    }
212
213    /// Party that should receive.
214    pub fn to(&self) -> &PartyId {
215        &self.to
216    }
217
218    /// Number of units to transfer.
219    pub fn units(&self) -> u128 {
220        self.units
221    }
222}
223
224/// A deterministic settlement plan produced from a ledger.
225#[derive(Clone, Debug, Default, PartialEq, Eq)]
226pub struct SettlementPlan {
227    transfers: Vec<SettlementTransfer>,
228    original_balances: BTreeMap<PartyId, i128>,
229}
230
231impl SettlementPlan {
232    /// Required transfers in deterministic party order.
233    pub fn transfers(&self) -> &[SettlementTransfer] {
234        &self.transfers
235    }
236
237    /// Sum of all units moved by the plan.
238    pub fn total_units(&self) -> u128 {
239        self.transfers.iter().map(SettlementTransfer::units).sum()
240    }
241
242    /// Returns whether applying the plan clears every original balance.
243    pub fn is_conserved(&self) -> bool {
244        let mut balances = self.original_balances.clone();
245        for transfer in &self.transfers {
246            let Ok(units) = i128::try_from(transfer.units) else {
247                return false;
248            };
249            let Some(from) = balances
250                .get(&transfer.from)
251                .and_then(|value| value.checked_add(units))
252            else {
253                return false;
254            };
255            let Some(to) = balances
256                .get(&transfer.to)
257                .and_then(|value| value.checked_sub(units))
258            else {
259                return false;
260            };
261            balances.insert(transfer.from.clone(), from);
262            balances.insert(transfer.to.clone(), to);
263        }
264        balances.values().all(|&balance| balance == 0)
265    }
266}
267
268/// Implements the Cocoshiga net-settlement principle.
269#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
270pub struct Cocoshiga;
271
272impl Cocoshiga {
273    /// Nets reciprocal and transitive obligations into a settlement plan.
274    ///
275    /// Parties are processed in lexicographic order, so identical ledgers
276    /// always yield identical plans.
277    pub fn settle(ledger: &KarmaLedger) -> Result<SettlementPlan, KarmaError> {
278        let balances = ledger.balances()?;
279        let sum = balances.values().try_fold(0i128, |total, &balance| {
280            total.checked_add(balance).ok_or(KarmaError::Overflow)
281        })?;
282        if sum != 0 {
283            return Err(KarmaError::Unbalanced);
284        }
285
286        let mut debtors: Vec<(PartyId, u128)> = balances
287            .iter()
288            .filter(|&(_, &balance)| balance < 0)
289            .map(|(party, &balance)| (party.clone(), balance.unsigned_abs()))
290            .collect();
291        let mut creditors: Vec<(PartyId, u128)> = balances
292            .iter()
293            .filter(|&(_, &balance)| balance > 0)
294            .map(|(party, &balance)| (party.clone(), balance as u128))
295            .collect();
296
297        let mut transfers = Vec::new();
298        let (mut debtor_index, mut creditor_index) = (0usize, 0usize);
299        while debtor_index < debtors.len() && creditor_index < creditors.len() {
300            let units = debtors[debtor_index].1.min(creditors[creditor_index].1);
301            transfers.push(SettlementTransfer {
302                from: debtors[debtor_index].0.clone(),
303                to: creditors[creditor_index].0.clone(),
304                units,
305            });
306            debtors[debtor_index].1 -= units;
307            creditors[creditor_index].1 -= units;
308            if debtors[debtor_index].1 == 0 {
309                debtor_index += 1;
310            }
311            if creditors[creditor_index].1 == 0 {
312                creditor_index += 1;
313            }
314        }
315
316        let plan = SettlementPlan {
317            transfers,
318            original_balances: balances,
319        };
320        if !plan.is_conserved() {
321            return Err(KarmaError::Unbalanced);
322        }
323        Ok(plan)
324    }
325}
326
327/// Validation and arithmetic failures returned by the crate.
328#[derive(Clone, Copy, Debug, PartialEq, Eq)]
329#[non_exhaustive]
330pub enum KarmaError {
331    /// A party identifier is empty or whitespace-only.
332    EmptyParty,
333    /// Giver and receiver are the same party.
334    SameParty,
335    /// An entry has no units.
336    ZeroUnits,
337    /// A checked arithmetic operation overflowed.
338    Overflow,
339    /// A settlement failed the conservation invariant.
340    Unbalanced,
341}
342
343impl Display for KarmaError {
344    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
345        f.write_str(match self {
346            Self::EmptyParty => "party identifiers cannot be empty",
347            Self::SameParty => "giver and receiver must be different parties",
348            Self::ZeroUnits => "karma units must be greater than zero",
349            Self::Overflow => "karma balance overflowed",
350            Self::Unbalanced => "settlement does not conserve all balances",
351        })
352    }
353}
354
355impl Error for KarmaError {}
356
357#[cfg(test)]
358mod tests {
359    use super::*;
360
361    #[test]
362    fn reciprocal_karma_is_netted() {
363        let mut ledger = KarmaLedger::new();
364        ledger.record("alice", "bob", 10, "lunch").unwrap();
365        ledger.record("bob", "alice", 4, "coffee").unwrap();
366
367        let plan = Cocoshiga::settle(&ledger).unwrap();
368        assert_eq!(
369            plan.transfers(),
370            &[SettlementTransfer {
371                from: PartyId::new("bob").unwrap(),
372                to: PartyId::new("alice").unwrap(),
373                units: 6,
374            }]
375        );
376        assert!(plan.is_conserved());
377    }
378
379    #[test]
380    fn transitive_karma_becomes_one_transfer() {
381        let mut ledger = KarmaLedger::new();
382        ledger.record("alice", "bob", 7, "").unwrap();
383        ledger.record("bob", "carol", 7, "").unwrap();
384
385        let plan = Cocoshiga::settle(&ledger).unwrap();
386        assert_eq!(plan.transfers().len(), 1);
387        assert_eq!(plan.transfers()[0].from().as_str(), "carol");
388        assert_eq!(plan.transfers()[0].to().as_str(), "alice");
389        assert_eq!(plan.transfers()[0].units(), 7);
390    }
391
392    #[test]
393    fn settlement_is_deterministic_and_conserved() {
394        let mut ledger = KarmaLedger::new();
395        ledger.record("d", "a", 8, "").unwrap();
396        ledger.record("c", "b", 5, "").unwrap();
397        ledger.record("a", "c", 2, "").unwrap();
398
399        let first = Cocoshiga::settle(&ledger).unwrap();
400        let second = Cocoshiga::settle(&ledger).unwrap();
401        assert_eq!(first, second);
402        assert!(first.is_conserved());
403    }
404
405    #[test]
406    fn invalid_entries_do_not_mutate_the_ledger() {
407        let mut ledger = KarmaLedger::new();
408        assert_eq!(
409            ledger.record("", "bob", 1, "").unwrap_err(),
410            KarmaError::EmptyParty
411        );
412        assert_eq!(
413            ledger.record("alice", "alice", 1, "").unwrap_err(),
414            KarmaError::SameParty
415        );
416        assert_eq!(
417            ledger.record("alice", "bob", 0, "").unwrap_err(),
418            KarmaError::ZeroUnits
419        );
420        assert!(ledger.is_empty());
421    }
422
423    #[test]
424    fn empty_ledger_has_an_empty_valid_plan() {
425        let plan = Cocoshiga::settle(&KarmaLedger::new()).unwrap();
426        assert!(plan.transfers().is_empty());
427        assert_eq!(plan.total_units(), 0);
428        assert!(plan.is_conserved());
429    }
430}