tiers.gno

  1// Package tiers prices one amount against a graduated schedule: cut the
  2// amount at caller-declared breakpoints, charge each slice at its own rate,
  3// and sum.
  4//
  5// This is the arithmetic behind a progressive fee, a marginal tax bracket, a
  6// volume discount and a tiered royalty. Nothing here reads the chain, holds
  7// state, or knows what the amount is a quantity of, so a realm can price a
  8// whole schedule without a node.
  9//
 10//	s, _ := New([]int64{1000, 5000}, []int64{100, 250, 500})
 11//	parts, err := s.SliceAt(7000)     // [1000 4000 2000] -- the partition
 12//	col, err := s.ChargeByTier(7000)  // [10 100 100]      -- the line items
 13//	fee, err := s.Charge(7000)        // 210               -- their sum
 14//
 15// The three steps are separable on purpose, in the shape [p/aging] uses: the
 16// partition is what a reader checks against the schedule, the per-tier column
 17// is the line items, and [Schedule.Charge] is the one number that goes in a
 18// ledger. Charge is *defined* as the sum of the column, so the two cannot
 19// disagree.
 20//
 21// # Marginal, and never a cliff
 22//
 23// Each slice of the amount is charged at the rate for the tier it falls in.
 24// The whole amount is never charged at the top tier's rate. Those are
 25// different numbers, and the difference is not a rounding matter: the cliff
 26// form has a discontinuity at every edge, where earning one more unit can
 27// cost more than one unit.
 28//
 29// With edges `{100}` and rates `{0, 5000}`, the cliff form charges 0 at 99 and
 30// 50 at 100 — one extra unit costs fifty. The graduated form charges 0 at 100
 31// and 0 at 101, because only the one unit above the edge is priced at 50%.
 32//
 33// What this package guarantees, at every amount and for every valid schedule:
 34//
 35//	Charge(n) <= Charge(n+1) <= Charge(n) + 1
 36//
 37// The left inequality is monotonicity; the right is the no-cliff property.
 38// Adding one unit to the amount grows exactly one slice by one, and
 39// `floor((x+1)r/RateScale) - floor(x·r/RateScale)` is 0 or 1 whenever
 40// `r <= RateScale`. [TestChargeHasNoCliffAtAnyEdge] asserts it at and around
 41// every edge of every schedule it builds, and [TestCliffFormulaViolatesIt]
 42// pins the counterexample so that a later "simplification" to the cliff form
 43// fails the suite instead of silently changing every published number.
 44//
 45// A third consequence of the same bound: `Charge(n) <= n`. A graduated
 46// schedule can never charge more than the amount it is pricing, which is what
 47// makes the rate cap in [New] an arithmetic fact and not only hygiene.
 48//
 49// # The amount is a length, and the half-open convention is load-bearing
 50//
 51// Think of the amount as the interval `[0, amount)`. Tier i covers the
 52// half-open range `[edges[i-1], edges[i])`, with tier 0 starting at 0 and the
 53// last tier unbounded above. That makes the tiers exhaustive and disjoint over
 54// every non-negative amount, with no breakpoint shared by two tiers. A slice
 55// is the overlap of `[0, amount)` with a tier's range, so the slices always
 56// sum to exactly the amount — [Schedule.SliceAt]'s cross-foot.
 57//
 58// The unit running from x to x+1 is priced at the tier containing **x**. So
 59// [Schedule.TierOf] and [Schedule.MarginalRate] answer a question about the
 60// *next* unit, not the last one:
 61//
 62//	MarginalRate(n) is the rate the (n+1)'th unit will attract.
 63//
 64// At an edge the two readings differ, and that difference is the off-by-one
 65// this package is most exposed to. With edges `{30}`, `MarginalRate(30)` is
 66// the *upper* tier's rate: the amount 30 exactly fills tier 0, and the next
 67// unit is the first one above the edge. The other reading — "the rate the last
 68// unit was charged at" — would answer with the lower tier, and is not offered,
 69// because it is undefined at amount 0.
 70//
 71// [p/aging] shipped an off-by-one of exactly this kind in its own discovery
 72// record (its doc, "The degenerate two-bucket case"), so the convention is
 73// stated here and pinned by [TestMarginalRateAtAnEdgeIsTheUpperTier] rather
 74// than left to a reader to reconstruct. [Schedule.TierRange] exists for the
 75// same reason: reconstructing a half-open range from [Schedule.Edges] is where
 76// the mistake lives.
 77//
 78// # Why the floor is taken per slice
 79//
 80//	Charge = Σ floor(sliceᵢ × rateᵢ / RateScale)
 81//
 82// not one floor taken at the end of an exact rational total. Those are
 83// different numbers, and which one a package shipped is invisible in any test
 84// that happens to use round rates.
 85//
 86// Per-slice is chosen because [Schedule.ChargeByTier] is the line-item column
 87// a reader sees next to the slices, and line items that do not add up to the
 88// stated total are a bookkeeping defect regardless of which total is "more
 89// accurate". The same discipline, and the same rationale, as [p/aging]'s
 90// per-bucket floor and [p/depreciation]'s `Charge`-from-`CarryingAt`.
 91//
 92// [TestFloorIsPerSliceNotAtTheEnd] pins a case where the two disagree.
 93//
 94// # Monotone in the amount — and why, unlike [p/aging], it really is
 95//
 96// [p/aging] published the analogous claim as settled and the code falsified
 97// it: its provision can **fall** as time advances, by up to one unit per
 98// bucket, because mass *moves between* buckets as an obligation ages and each
 99// bucket re-floors. Its doc records the counterexample and the attained bound.
100//
101// Here the claim holds, and the reason is structural rather than fortunate:
102// increasing the amount only ever **adds mass at the top**. Every lower slice
103// is already full, so its subtotal is literally the same number and no floored
104// subtotal can shrink. Nothing moves between slices.
105//
106// That is an argument, so it is also measured: [TestChargeIsMonotone] sweeps
107// random schedules across contiguous amounts and asserts a strictly
108// non-decreasing charge. The discovery record for this package committed to
109// amending itself rather than quietly editing if the sweep found a drop; the
110// sweep found none, and the figure it ran is in the test rather than restated
111// here.
112//
113// # Why the rates need NOT be monotone, which is the opposite of [p/aging]
114//
115// [New] accepts rates in any order. A rising schedule is a progressive fee; a
116// falling one is a volume discount, which is the same arithmetic read from the
117// other end and is a first-class use of this package, not a tolerated
118// degenerate case.
119//
120// [p/aging] refuses a falling schedule, and the contrast is worth stating
121// because copying that check here would be the plausible mistake. It needs the
122// ordering for two reasons, neither of which transfers: a falling loss rate is
123// a domain error (an older receivable is not more collectible), and without the
124// ordering its exact-rational monotonicity fails as well, since an obligation
125// crossing into a cheaper bucket *reduces* the total. In this package nothing
126// crosses into anything. The monotonicity above needs only `rate >= 0`.
127//
128// So a transposed rate array is a silent authoring error here in a way it is
129// not in [p/aging], and this package cannot detect it. That is recorded in
130// "What this package does not claim" rather than papered over with a check
131// that would also forbid every discount schedule.
132//
133// # The per-slice multiply goes through 128 bits
134//
135// `slice × rate` overflows an int64 for large amounts — a slice near maxInt64
136// at any rate above 1 basis point — so the product is taken in 128 bits with
137// `bits.Mul64` and divided with `bits.Div64`.
138//
139// The discipline is ADOPTED, not derived, and the source is [p/curve], read in
140// full before this was written. Its guard carries the argument in its own
141// comment: without the `hi < m` check, `bits.Div64` violates its own
142// precondition and over-issues. See DISCOVERY.md § 3 and § 4, which attribute
143// it.
144//
145// Here that precondition is *provable*: rates are capped at RateScale, so
146// `slice × rate < 2^63 × 10^4 < 2^77` and `hi < 2^13 = 8192 < 10000 = m`.
147// **It is checked anyway**, and so is the quotient's fit in an int64, which is
148// provable from the same cap. A proof that rests on the rate cap is a proof
149// that expires silently the day someone raises the cap, and CLAUDE.md § 7a's
150// whole subject is checks that stop asking their question.
151//
152// Every guard in `chargeSlice` is therefore unreachable through the exported
153// API, which makes them untestable through it. They are not left unexercised:
154// `chargeSlice` is unexported and the suite calls it directly —
155// [TestChargeSliceGuardsAPreconditionTheAPICannotReach] — so each guard has a
156// test that fails when it is removed.
157//
158// No count is given here, deliberately. This paragraph said "Both guards" when
159// it meant the two OVERFLOW guards specifically, and when the rate-sign guard
160// was added the obvious repair — "three" — was wrong twice over: the function
161// holds four guards, and two of the four are preconditions rather than overflow
162// checks, so any single number here answers an ambiguous question. CLAUDE.md
163// § 4a's rule applies — prefer deleting a restated number over updating it —
164// and the sabotage harness counts them by construction anyway.
165//
166// An alternative was considered and
167// rejected: binding the amount to `maxInt64/RateScale` so a plain int64
168// multiply could not wrap. That bound is safe for any µGNOT quantity and is
169// refused for exactly that reason — justifying it needs a unit, and this
170// package declares it has none. See DISCOVERY.md § 4.
171//
172// The rate-sign guard was added after an adversarial audit, and the
173// reason it was missing is worth more than the fix. The paragraph above proves
174// the precondition from the rate *cap*, and a cap is an upper bound: writing it
175// out established `rate <= RateScale` and said nothing about the other end,
176// while the `slice < 0` guard sitting one line away made the function look as
177// though both of its signed inputs had been considered. Measured, before the
178// fix: `chargeSlice(1, -1)` returned `(1844674407370955, nil)` — a positive
179// charge, a nil error, and both overflow guards cleanly passed, because
180// `uint64(-1)` has a zero high word when multiplied by 1.
181//
182// What made it survive review is the near miss: `chargeSlice(maxInt64, -1)`
183// *is* caught, by `hi >= m`, so the negative-rate family is half-covered by an
184// existing check and a spot probe at the interesting end of int64 reports an
185// error exactly as it should. The hole is at the *small* end, where nothing
186// about the value looks extreme. A guard that catches the dramatic case and
187// misses the mundane one reads, from the outside, like a guard that works.
188//
189// # What bounds the work
190//
191// Tier lookup is a linear scan over the edges, cheaper than a binary search at
192// these sizes and the shape an auditor can check by reading. [MaxTiers] is 16,
193// so there are at most 15 edges. One [Schedule.Charge] performs at most 16
194// 128-bit multiplications and divisions over a 16-entry partition, and every
195// exported method re-runs `check`, costing at most 50 further comparisons.
196//
197// That 50 is `2 + 2 + (MaxTiers-2) + 2×MaxTiers`, and the decomposition is
198// pinned by [TestConstantsAreTheDocumentedValues] rather than left as a
199// number in prose beside a constant nobody checked. This project has shipped
200// that defect more than once.
201//
202// Those are the figures, not an assertion that they are affordable. A realm
203// pricing many amounts in one transaction, or doing it inside a `Render`, must
204// size them against the gas it has. This package bounds the work; it does not
205// price it.
206//
207// # The one-tier schedule, and what it subsumes
208//
209// Empty edges are legitimate: `New(nil, []int64{250})` is a flat 2.5% on the
210// whole amount, with one tier and no breakpoint. It is the degenerate case of
211// the same formula rather than a special path.
212//
213// That schedule reproduces [p/nt/grc721/royalty]'s arithmetic — `salePrice *
214// Bps / FeeDenominator` against the same 10000 denominator — with one
215// difference in the implementation and none in the result for the amounts that
216// package can take. Royalty multiplies before dividing in plain int64, so it is
217// implicitly bounded at about `maxInt64/10000 ≈ 9.2e14`; this package's
218// 128-bit path has no such bound. [TestOneTierSchedule] pins the agreement
219// over the range where both are defined.
220//
221// [p/aging] is refused as a comparison in the other direction: it bins a *set*
222// of items by each item's age, where this slices *one* amount by magnitude. A
223// bin is not a slice, and the measurable consequence is the monotonicity
224// section above. See DISCOVERY.md § 3.
225//
226// # What this package does not claim
227//
228//   - **No novelty for the formula.** A graduated rate schedule is textbook
229//     arithmetic and three independent mul-div helpers already exist in the
230//     ecosystem. What was not found in the searched sources is this shape:
231//     a partition of one amount into magnitude slices at caller-declared
232//     edges, each priced at its own rate. See DISCOVERY.md § 1 and § 3, which
233//     also record a functionally exact mul-div primitive that was found,
234//     classified reusable, and deliberately not imported.
235//   - **No unit, deliberately.** The amount, the edges and the slices are
236//     int64 in whatever unit the caller keeps consistently. A rate is
237//     dimensionless. This is the stronger half of [p/aging]'s rule, and here
238//     it costs nothing because there is no time axis to pick a convention for.
239//   - **Nothing about money.** A charge is a number in a report. This package
240//     never sees a coin, and a realm using it must not infer custody or a
241//     transfer from it.
242//   - **No opinion on where the edges and rates come from.** Picking them is
243//     the whole of a fee policy and none of it is here. They are validated for
244//     shape and range, never for plausibility — and, unlike [p/aging], not for
245//     ordering either. A transposed rate array is accepted.
246//   - **No schedule identity, and no versioning.** A [Schedule] is a value
247//     with no name and no effective date. A realm that changes its fees must
248//     keep its own record of which schedule priced which charge, because
249//     nothing here can tell two schedules apart or say when one took effect.
250//   - **Not a rounding policy.** The floor is the only rounding this package
251//     performs and it is not configurable. A caller needing round-half-up, or
252//     needing the exact rational, must compute it from [Schedule.SliceAt] and
253//     the rates, both of which are exported for that purpose.
254//
255// [p/aging]: /p/g1ut6uspuh73e02yauxpmyt8g3wwddaq8utagvm3/aging
256// [p/depreciation]: /p/g1ut6uspuh73e02yauxpmyt8g3wwddaq8utagvm3/depreciation
257// [p/curve]: /p/g1ecsuj0q572jr0dhu29q9njtnmw03hyu7tyyvv6/curve/v0
258// [p/nt/grc721/royalty]: /p/nt/grc721/royalty/v0
259package tiers
260
261import (
262	"errors"
263	"math/bits"
264)
265
266// RateScale is the denominator every rate is expressed against, so a rate is
267// in basis points: 0 is 0%, 250 is 2.5%, 10000 is 100%.
268//
269// It is a constant rather than a per-schedule field on purpose, the same
270// decision and the same reason as [p/aging]'s: a schedule carrying its own
271// denominator lets two schedules in one realm be priced on different scales,
272// and the first symptom of that is a charge wrong by a factor of a hundred
273// with every individual number looking reasonable.
274//
275// The value is taken from the corpus rather than invented.
276// [p/nt/grc721/royalty] declares it as the EIP-2981 basis-point denominator
277// and `guildhall/trust/v0` independently ships the same ceiling; see
278// DISCOVERY.md § 4.
279const RateScale int64 = 10000
280
281// MaxTiers bounds the number of tiers, and so bounds the edge scan in
282// [Schedule.TierOf] and the loops in [Schedule.SliceAt] and
283// [Schedule.ChargeByTier]. 16 is past the point where a tier is meaningful: a
284// conventional fee schedule uses three or four.
285//
286// The minimum is 1, not 2, and that is the deliberate difference from
287// [p/aging]'s MaxBuckets. A one-tier schedule has no edges and applies one
288// rate to the whole amount, which is a flat fee — degenerate, but the same
289// formula, and useful enough to be the subject of its own section in the
290// package doc. [p/aging] refuses its own one-bucket case because a flat loss
291// rate is not an aging schedule at all; a flat fee *is* a rate schedule.
292//
293// What the bound costs: a caller needing more than 16 tiers must compose two
294// schedules, and the composition is **not** a 32-tier schedule. The second
295// would restart its partition at 0, so every slice and every floor would be
296// taken against the wrong origin. Composing graduated schedules is not
297// supported and cannot be faked by addition.
298const MaxTiers = 16
299
300var (
301	// ErrBadTierCount is returned when a schedule would have fewer than 1 or
302	// more than MaxTiers tiers. The tier count is len(edges)+1, so this is a
303	// statement about the edge slice: it must hold between 0 and MaxTiers-1
304	// entries. A nil or empty edge slice is legitimate and does NOT land
305	// here — it is the one-tier flat schedule.
306	ErrBadTierCount = errors.New("tiers: tier count must be in [1, MaxTiers]")
307
308	// ErrBadEdges is returned when the edges are not positive and strictly
309	// increasing.
310	//
311	// Equal adjacent edges would define an empty tier, which is not an error
312	// in arithmetic but is always an authoring mistake: it silently reduces
313	// the schedule's resolution while every tier still reports.
314	//
315	// Positive and not merely non-negative, for the same reason one step
316	// earlier. A first edge of 0 makes tier 0 the half-open range [0,0),
317	// occupiable by nothing, for every amount, forever — while NumTiers still
318	// reports it and its rate still prints. That is [p/aging]'s finding Y2,
319	// which shipped as `< 0` and was corrected before deployment; the check
320	// here reaches the first edge from the outset because of it.
321	ErrBadEdges = errors.New("tiers: edges must be positive and strictly increasing")
322
323	// ErrBadRateCount is returned when len(rates) != len(edges)+1. The
324	// off-by-one here is the most likely way to build a wrong schedule that
325	// still looks right, so it is named apart from ErrBadRate: a reader
326	// seeing this error knows to count, not to look at values.
327	ErrBadRateCount = errors.New("tiers: need exactly one rate per tier, which is len(edges)+1")
328
329	// ErrBadRate is returned when a rate is negative or exceeds RateScale.
330	//
331	// The cap is arithmetic as well as hygiene. `rate <= RateScale` is what
332	// makes `Charge(n) <= n`, what makes the no-cliff bound
333	// `Charge(n+1) <= Charge(n)+1` hold, and what proves the 128-bit
334	// precondition in chargeSlice. A rate above 100% would charge more than
335	// the amount; a negative rate would charge a refund and would break the
336	// monotonicity the package doc claims.
337	//
338	// The rates are NOT required to be ordered. See the package doc: a
339	// falling schedule is a volume discount, and refusing it would be copying
340	// a check from [p/aging] whose two reasons do not transfer.
341	ErrBadRate = errors.New("tiers: each rate must be in [0, RateScale]")
342
343	// ErrBadAmount is returned for a negative amount, and by the per-tier
344	// accessors for a negative slice.
345	//
346	// Zero is legitimate, unlike [p/aging]'s obligation amount: an amount of
347	// zero partitions into all-zero slices and charges 0, which is the right
348	// answer and not a caller bug. A realm pricing an empty cart should not
349	// have to special-case it.
350	ErrBadAmount = errors.New("tiers: amount must not be negative")
351
352	// ErrBadTierIndex is returned by the per-tier accessors for an index
353	// outside [0, NumTiers).
354	ErrBadTierIndex = errors.New("tiers: tier index out of range")
355
356	// ErrOverflow is returned when the arithmetic would wrap.
357	//
358	// Through the exported API it is unreachable, and that is a claim with a
359	// proof rather than an absence of evidence: the slices sum to the amount
360	// and so each is at most maxInt64; every rate is at most RateScale; the
361	// product is taken in 128 bits; and the quotient is at most the slice. The
362	// guards in chargeSlice are kept anyway, because the proof rests entirely
363	// on the rate cap and would expire silently if the cap were raised. See
364	// the package doc, and TestChargeSliceGuardsAPreconditionTheAPICannotReach
365	// for the direct unexported calls that do reach them.
366	ErrOverflow = errors.New("tiers: int64 overflow")
367)
368
369// maxInt64 is written as a literal rather than as `int64(1)<<63 - 1`, which
370// does not compile: the shift is evaluated in the already-typed int64 and
371// overflows before the subtraction brings it back. The same note is in
372// [p/aging] and [p/depreciation]; it is repeated because it is the same shape
373// as the arithmetic this package exists to get right.
374const maxInt64 int64 = 9223372036854775807
375
376// Schedule is a graduated rate schedule: the amount breakpoints and the rate
377// charged on each resulting slice.
378//
379// Its fields are unexported and the accessors copy, following [p/aging] and
380// for the same reason: a schedule holding slices is not safely copyable, and a
381// caller that kept the slice it passed to [New] could mutate the edges after
382// validation so that every subsequent call priced against a schedule that
383// never passed `check`. Construct with [New].
384type Schedule struct {
385	// edges holds the tier breakpoints, strictly increasing and positive.
386	// Tier i is the half-open amount range [edges[i-1], edges[i]), with tier
387	// 0 starting at 0 and the last tier unbounded above. It may be empty,
388	// which is the one-tier flat schedule.
389	edges []int64
390
391	// rates holds one rate per tier in units of RateScale, each in
392	// [0, RateScale] and in any order. len(rates) == len(edges)+1.
393	rates []int64
394}
395
396// New validates and returns a schedule. The edges are the amount breakpoints,
397// positive and strictly increasing; the rates are one per tier, so one more
398// than there are edges, each in [0, RateScale].
399//
400//	New([]int64{1000, 5000}, []int64{100, 250, 500})
401//
402// reads as: 1% on the first 1000, 2.5% on the next 4000, 5% on everything
403// above 5000.
404//
405// Empty edges are legitimate and give the one-tier flat schedule:
406// `New(nil, []int64{250})` charges 2.5% of the whole amount. A first edge of 0
407// is [ErrBadEdges] — it would define an empty tier 0.
408//
409// The rates are deliberately not required to be ordered; a falling schedule is
410// a volume discount. See the package doc on why [p/aging] refuses what this
411// accepts.
412//
413// Both slices are copied, so the caller may reuse or mutate its own.
414func New(edges, rates []int64) (Schedule, error) {
415	e := make([]int64, len(edges))
416	copy(e, edges)
417	r := make([]int64, len(rates))
418	copy(r, rates)
419	s := Schedule{edges: e, rates: r}
420	if err := s.check(); err != nil {
421		return Schedule{}, err
422	}
423	return s, nil
424}
425
426// check validates every field and establishes the precondition that lets
427// chargeSlice divide without a guard per term.
428//
429// Every exported method that can return an error calls it rather than trusting
430// its receiver, so the zero Schedule fails everywhere instead of pricing
431// against nil slices.
432//
433// That qualifier is a correction. This said "Every exported method calls it",
434// which is false: [Schedule.Edges] and [Schedule.Rates] do not, and cannot
435// usefully — they return a slice and no error, so there is nothing for a failed
436// check to become. An audit caught the overstatement, and the honest version of
437// the invariant names where the protection actually lives:
438//
439//   - `edges` and `rates` are unexported, so no importer can build a Schedule
440//     that did not come from [New].
441//   - [New] rejects by returning `Schedule{}`, not the half-built `s`, so a
442//     refused schedule carries no edges or rates to hand back. Measured: a
443//     schedule New refused answers `Edges() == []`, `len 0`.
444//
445// So the two unchecked accessors are safe by CONSTRUCTION rather than by
446// validation, and the distinction matters because the two fail differently. A
447// check that is absent fails when someone adds a path around it; a field that
448// is unexported fails only if someone exports it. Within this package the
449// construction argument does not hold at all, and that is measurable rather
450// than hypothetical: a hostile in-package struct literal answers
451// `Edges() == [-5 -1]` while `Valid() == false`. Nothing is wrong with that
452// today -- the package's own code never builds one -- but it is the state a
453// future `New` variant that returned `s` beside its error would leak, and
454// Edges/Rates are precisely the two methods that would not notice.
455//
456// Note
457// what that costs here that it does not cost [p/aging]: the zero Schedule has
458// no edges, which is a *legal* edge slice in this package, so it is the rate
459// count that rejects it — `len(nil) != 0+1`. [ErrBadRateCount] is therefore
460// the zero value's error, and TestZeroScheduleIsInvalid asserts exactly that
461// rather than only that some error came back.
462//
463// The cost is at most 50 comparisons per call; see the package doc on bounds.
464func (s Schedule) check() error {
465	if len(s.edges) > MaxTiers-1 {
466		return ErrBadTierCount
467	}
468	if len(s.rates) != len(s.edges)+1 {
469		return ErrBadRateCount
470	}
471	// `<= 0` and not `< 0`, reaching the FIRST edge and not only the adjacent
472	// pairs. Tier 0 is the half-open range [0, edges[0]), so an edges[0] of 0
473	// makes it [0,0) — occupiable by nothing, forever — while NumTiers still
474	// counts it and MarginalRate still returns its rate. That is precisely the
475	// condition the loop below refuses between adjacent edges, and the first
476	// edge is the one place the rule would not reach if it were written as a
477	// pairwise loop alone. It is [p/aging]'s audit finding Y2, which is why it
478	// is a separate statement with its own sabotage case.
479	if len(s.edges) > 0 && s.edges[0] <= 0 {
480		return ErrBadEdges
481	}
482	for i := 1; i < len(s.edges); i++ {
483		if s.edges[i] <= s.edges[i-1] {
484			return ErrBadEdges
485		}
486	}
487	for _, rate := range s.rates {
488		if rate < 0 || rate > RateScale {
489			return ErrBadRate
490		}
491	}
492	return nil
493}
494
495// Valid reports whether the schedule is well-formed. A zero Schedule is not.
496func (s Schedule) Valid() bool { return s.check() == nil }
497
498// NumTiers is the number of tiers, which is one more than the number of edges.
499// It returns 0 for an invalid schedule, including the zero value, so a caller
500// that skipped [Schedule.Valid] gets a number that reads as wrong rather than
501// one that reads as a legitimate one-tier schedule.
502//
503// That distinction is sharper here than in [p/aging], where 0 could not be
504// confused with anything: a one-tier schedule is valid in this package, so if
505// NumTiers returned 1 for the zero value a caller could not tell the flat
506// schedule from the broken one.
507func (s Schedule) NumTiers() int {
508	if s.check() != nil {
509		return 0
510	}
511	return len(s.edges) + 1
512}
513
514// Edges returns a copy of the tier breakpoints. It is empty for a one-tier
515// schedule.
516func (s Schedule) Edges() []int64 {
517	out := make([]int64, len(s.edges))
518	copy(out, s.edges)
519	return out
520}
521
522// Rates returns a copy of the per-tier rates, in units of [RateScale].
523func (s Schedule) Rates() []int64 {
524	out := make([]int64, len(s.rates))
525	copy(out, s.rates)
526	return out
527}
528
529// TierRange returns the half-open amount range of tier i as [lo, hi),
530// together with whether it is unbounded above — which is true for the last
531// tier and only the last tier, where hi is meaningless.
532//
533// It exists so that a caller rendering line items does not have to
534// reconstruct the half-open convention from [Schedule.Edges]. That
535// reconstruction is where an off-by-one lives, and [p/aging] shipped one of
536// those in its own discovery record; see the package doc.
537func (s Schedule) TierRange(i int) (lo, hi int64, unbounded bool, err error) {
538	if err := s.check(); err != nil {
539		return 0, 0, false, err
540	}
541	if i < 0 || i > len(s.edges) {
542		return 0, 0, false, ErrBadTierIndex
543	}
544	if i > 0 {
545		lo = s.edges[i-1]
546	}
547	if i == len(s.edges) {
548		return lo, 0, true, nil
549	}
550	return lo, s.edges[i], false, nil
551}
552
553// TierOf returns the index of the tier that the NEXT unit of the amount falls
554// in: 0 for the lowest, NumTiers-1 for the unbounded top.
555//
556// The partition is half-open, [lo, hi), which is what makes it exhaustive and
557// disjoint over every non-negative amount with no breakpoint shared by two
558// tiers. An amount equal to an edge is in the **upper** tier, so with edge
559// 1000, `TierOf(1000)` is 1: the amount 1000 exactly fills tier 0 and the next
560// unit is the first one above the breakpoint.
561//
562// Read it as a question about the next unit, never about the last one. See the
563// package doc, which states the convention and names the off-by-one it avoids.
564func (s Schedule) TierOf(amount int64) (int, error) {
565	if err := s.check(); err != nil {
566		return 0, err
567	}
568	if amount < 0 {
569		return 0, ErrBadAmount
570	}
571	for i, edge := range s.edges {
572		if amount < edge {
573			return i, nil
574		}
575	}
576	return len(s.edges), nil
577}
578
579// MarginalRate returns the rate the next unit of the amount will attract, in
580// units of [RateScale]: the rate of [Schedule.TierOf]'s tier.
581//
582// It is not the average rate and not the rate the last unit was charged at.
583// `MarginalRate(n)` prices unit n+1, so at an edge it returns the upper tier's
584// rate; the package doc gives the reason the other reading is not offered.
585//
586// The effective rate on the whole amount is `Charge(n) × RateScale / n`, which
587// is the caller's arithmetic: it needs a rounding decision this package does
588// not make, and it is undefined at n = 0.
589func (s Schedule) MarginalRate(amount int64) (int64, error) {
590	i, err := s.TierOf(amount)
591	if err != nil {
592		return 0, err
593	}
594	return s.rates[i], nil
595}
596
597// SliceAt partitions an amount across the tiers and returns the slice in each,
598// lowest first.
599//
600// The slices sum to exactly the amount — no remainder, no dust, by
601// construction rather than by a correction step — because a slice is the
602// overlap of `[0, amount)` with the tier's half-open range and the ranges
603// partition `[0, ∞)`. [TestSliceAtCrossFoots] asserts the sum, and the package
604// doc explains why that assertion alone is weak: moving mass between adjacent
605// slices preserves it. Each edge comparison therefore has its own sabotage
606// case, in tools/test_tiers_sabotage.sh.
607//
608// An amount of 0 returns all-zero slices and no error. Tiers above the amount
609// are 0, which is why the result always has [Schedule.NumTiers] entries rather
610// than being truncated at the last non-empty tier: a caller rendering line
611// items against [Schedule.Rates] indexes both by tier.
612func (s Schedule) SliceAt(amount int64) ([]int64, error) {
613	if err := s.check(); err != nil {
614		return nil, err
615	}
616	if amount < 0 {
617		return nil, ErrBadAmount
618	}
619	out := make([]int64, len(s.edges)+1)
620	for i := 0; i <= len(s.edges); i++ {
621		var lo int64
622		if i > 0 {
623			lo = s.edges[i-1]
624		}
625		// The edges increase, so once the amount fails to reach this tier's
626		// floor it reaches no higher tier either. The remaining entries stay
627		// at their zero value, which is the correct answer and not an
628		// omission.
629		if amount <= lo {
630			break
631		}
632		top := amount
633		if i < len(s.edges) && s.edges[i] < amount {
634			top = s.edges[i]
635		}
636		// No overflow is possible in either subtraction: lo is non-negative
637		// and strictly below top in both branches, so the difference is a
638		// positive int64.
639		out[i] = top - lo
640	}
641	return out, nil
642}
643
644// ChargeByTier returns the charge on each slice of an amount, lowest first:
645// the line-item column.
646//
647// Each entry is `floor(sliceᵢ × rateᵢ / RateScale)`, the floor taken per slice
648// so that this column sums to exactly what [Schedule.Charge] reports. See the
649// package doc for what that choice costs.
650//
651// Unlike [p/aging]'s ProvisionByBucket, this takes the amount rather than a
652// caller-built report, so there is no cross-foot to validate and no way to
653// price a partition that came from a different schedule. [p/aging] exports its
654// Report so that a realm can accumulate buckets across calls, and pays for it
655// with four validation branches and a documented hazard. Nothing here needs
656// accumulation — one amount is one amount — so the opportunity is removed
657// instead of guarded.
658func (s Schedule) ChargeByTier(amount int64) ([]int64, error) {
659	parts, err := s.SliceAt(amount)
660	if err != nil {
661		return nil, err
662	}
663	out := make([]int64, len(parts))
664	for i, slice := range parts {
665		c, err := chargeSlice(slice, s.rates[i])
666		if err != nil {
667			return nil, err
668		}
669		out[i] = c
670	}
671	return out, nil
672}
673
674// Charge returns the total charge on an amount: one number for a ledger.
675//
676// It is defined as the sum of [Schedule.ChargeByTier], so the single figure
677// and the line items can never disagree — the same discipline [p/aging] uses
678// for Provision and [p/depreciation] for Charge.
679//
680// The sum cannot overflow: each term is at most its slice, because every rate
681// is at most RateScale, and the slices sum to the amount. That also gives
682// `Charge(n) <= n`, stated in the package doc.
683func (s Schedule) Charge(amount int64) (int64, error) {
684	parts, err := s.ChargeByTier(amount)
685	if err != nil {
686		return 0, err
687	}
688	var sum int64
689	for _, p := range parts {
690		sum += p
691	}
692	return sum, nil
693}
694
695// chargeSlice returns floor(slice × rate / RateScale) with the product taken
696// in 128 bits.
697//
698// It is unexported and it is called directly by the suite, which is the only
699// way any guard below can be reached: every one of them is provably unreachable
700// from a validated Schedule, and every one is kept. See the package doc, "The
701// per-slice multiply goes through 128 bits", for the proof, the attribution to
702// [p/curve], and why a proof resting on the rate cap is not treated as a
703// licence to delete the check.
704//
705// "either guard … both" stood here until the Y1 fix added a fourth guard, and
706// it was not caught by the sweep that fixed the other counts because a
707// single-line grep does not match prose a comment wrap has split. Both of those
708// failure modes are recorded in AUDIT.md § 5 item 1.
709//
710// Both signed inputs must be non-negative, and the callers establish each from
711// a different place: `slice` from the partition [Schedule.SliceAt] builds, and
712// `rate` from `check`, which rejects `rate < 0` before any Schedule exists.
713// Naming only `slice` here is how the missing `rate < 0` guard went unnoticed
714// — the doc described half the contract and the code enforced exactly as much
715// as the doc described.
716func chargeSlice(slice, rate int64) (int64, error) {
717	if slice < 0 {
718		return 0, ErrBadAmount
719	}
720	// Not symmetric with the guard above, and deliberately so: a negative slice
721	// is a broken partition (ErrBadAmount), while a negative rate is a broken
722	// schedule (ErrBadRate) — the error names which precondition failed, and
723	// each is the error `check` would have returned for the same input.
724	//
725	// What it must precede is the DIVISION, not the conversion -- stated
726	// precisely because the loose version of this sentence is the defect being
727	// repaired. `uint64(rate)` is a value conversion and cannot fail, so a guard
728	// sitting between it and `hi >= m` would behave identically; placing it
729	// first is for the reader, not for correctness. What would be wrong is
730	// placing it after the division, because `uint64(-1)` multiplied by a small
731	// slice has a high word of zero, sails past `hi >= m`, and divides to a
732	// large positive charge. Measured before this guard existed:
733	// `chargeSlice(1, -1) = (1844674407370955, nil)`.
734	if rate < 0 {
735		return 0, ErrBadRate
736	}
737	m := uint64(RateScale)
738	hi, lo := bits.Mul64(uint64(slice), uint64(rate))
739	// bits.Div64 PANICS when its precondition hi < y is violated, so this is
740	// not a politeness check: without it a wrapping input would abort the
741	// transaction instead of returning an error, and the caller could not tell
742	// an overflow from any other panic. The same argument [p/curve] makes in
743	// its own comment.
744	if hi >= m {
745		return 0, ErrOverflow
746	}
747	q, _ := bits.Div64(hi, lo, m)
748	// And the quotient must fit. Provable from rate <= RateScale, which gives
749	// q <= slice <= maxInt64 — and checked for the same reason as above. The
750	// two guards are not redundant: this one is reachable with a rate in
751	// (RateScale, 2×RateScale), where the product's high word stays below m
752	// but the quotient exceeds maxInt64.
753	if q > uint64(maxInt64) {
754		return 0, ErrOverflow
755	}
756	return int64(q), nil
757}