commit 0e6108a744e461547540f4002fb22e56abcb76fe
parent be373f904cbbd83e309181b2ec1379926da40e01
Author: Florian Dold <dold@taler.net>
Date: Thu, 20 Aug 2026 19:06:43 +0200
wallet-core: make fee timeline pairing boundary-safe
Diffstat:
2 files changed, 151 insertions(+), 172 deletions(-)
diff --git a/packages/taler-wallet-core/src/denominations.test.ts b/packages/taler-wallet-core/src/denominations.test.ts
@@ -660,6 +660,105 @@ test("should add both to the same row", (t) => {
}
});
+test("should pair timelines that end at never", (t) => {
+ const group = Amounts.stringifyValue(VALUES[1]);
+ const forever = AbsoluteTime.never();
+ const pairs = createPairTimeline(
+ [
+ {
+ group,
+ from: ABS_TIME[1],
+ until: forever,
+ fee: VALUES[1],
+ },
+ ],
+ [
+ {
+ group,
+ from: ABS_TIME[1],
+ until: ABS_TIME[3],
+ fee: VALUES[2],
+ },
+ ],
+ );
+
+ expect(t, pairs).deep.equals([
+ {
+ group,
+ from: ABS_TIME[1],
+ until: ABS_TIME[3],
+ left: VALUES[1],
+ right: VALUES[2],
+ },
+ {
+ group,
+ from: ABS_TIME[3],
+ until: forever,
+ left: VALUES[1],
+ right: undefined,
+ },
+ ] as FeeDescriptionPair[]);
+});
+
+test("should use boundaries from the current group", (t) => {
+ const firstGroup = Amounts.stringifyValue(VALUES[1]);
+ const secondGroup = Amounts.stringifyValue(VALUES[2]);
+ const pairs = createPairTimeline(
+ [
+ {
+ group: firstGroup,
+ from: ABS_TIME[1],
+ until: ABS_TIME[2],
+ fee: VALUES[1],
+ },
+ {
+ group: secondGroup,
+ from: ABS_TIME[2],
+ until: ABS_TIME[5],
+ fee: VALUES[2],
+ },
+ ],
+ [
+ {
+ group: firstGroup,
+ from: ABS_TIME[1],
+ until: ABS_TIME[2],
+ fee: VALUES[1],
+ },
+ {
+ group: secondGroup,
+ from: ABS_TIME[3],
+ until: ABS_TIME[4],
+ fee: VALUES[3],
+ },
+ ],
+ );
+
+ expect(t, pairs.filter((pair) => pair.group === secondGroup)).deep.equals([
+ {
+ group: secondGroup,
+ from: ABS_TIME[2],
+ until: ABS_TIME[3],
+ left: VALUES[2],
+ right: undefined,
+ },
+ {
+ group: secondGroup,
+ from: ABS_TIME[3],
+ until: ABS_TIME[4],
+ left: VALUES[2],
+ right: VALUES[3],
+ },
+ {
+ group: secondGroup,
+ from: ABS_TIME[4],
+ until: ABS_TIME[5],
+ left: VALUES[2],
+ right: undefined,
+ },
+ ] as FeeDescriptionPair[]);
+});
+
test("should repeat the first and change the second", (t) => {
const left = [
{
diff --git a/packages/taler-wallet-core/src/denominations.ts b/packages/taler-wallet-core/src/denominations.ts
@@ -111,183 +111,63 @@ export function createPairTimeline(
left: FeeDescription[],
right: FeeDescription[],
): FeeDescriptionPair[] {
- //FIXME: we need to create a copy of the array because
- //this algorithm is using splice, remove splice and
- //remove this array duplication
- left = [...left];
- right = [...right];
-
- //both list empty, discarded
- if (left.length === 0 && right.length === 0) return [];
-
- const pairList: FeeDescriptionPair[] = [];
-
- let li = 0; //left list index
- let ri = 0; //right list index
-
- while (li < left.length && ri < right.length) {
- const currentGroup =
- Number.parseFloat(left[li].group) < Number.parseFloat(right[ri].group)
- ? left[li].group
- : right[ri].group;
- const lgs = li; //left group start index
- const rgs = ri; //right group start index
-
- let lgl = 0; //left group length (until next value)
- while (li + lgl < left.length && left[li + lgl].group === currentGroup) {
- lgl++;
+ const byGroup = (
+ entries: FeeDescription[],
+ ): Map<string, FeeDescription[]> => {
+ const result = new Map<string, FeeDescription[]>();
+ for (const entry of entries) {
+ const group = result.get(entry.group) ?? [];
+ group.push(entry);
+ result.set(entry.group, group);
}
- let rgl = 0; //right group length (until next value)
- while (ri + rgl < right.length && right[ri + rgl].group === currentGroup) {
- rgl++;
- }
- const leftGroupIsEmpty = lgl === 0;
- const rightGroupIsEmpty = rgl === 0;
- //check which start after, add gap so both list starts at the same time
- // one list may be empty
- const leftStartTime: AbsoluteTime = leftGroupIsEmpty
- ? AbsoluteTime.never()
- : left[li].from;
- const rightStartTime: AbsoluteTime = rightGroupIsEmpty
- ? AbsoluteTime.never()
- : right[ri].from;
-
- //first time cut is the smallest time
- let timeCut: AbsoluteTime = leftStartTime;
-
- if (AbsoluteTime.cmp(leftStartTime, rightStartTime) < 0) {
- const ends = rightGroupIsEmpty ? left[li + lgl - 1].until : right[0].from;
-
- right.splice(ri, 0, {
- from: leftStartTime,
- until: ends,
- group: left[li].group,
- });
- rgl++;
-
- timeCut = leftStartTime;
- }
- if (AbsoluteTime.cmp(leftStartTime, rightStartTime) > 0) {
- const ends = leftGroupIsEmpty ? right[ri + rgl - 1].until : left[0].from;
-
- left.splice(li, 0, {
- from: rightStartTime,
- until: ends,
- group: right[ri].group,
- });
- lgl++;
-
- timeCut = rightStartTime;
- }
-
- //check which ends sooner, add gap so both list ends at the same time
- // here both list are non empty
- const leftEndTime: AbsoluteTime = left[li + lgl - 1].until;
- const rightEndTime: AbsoluteTime = right[ri + rgl - 1].until;
-
- if (AbsoluteTime.cmp(leftEndTime, rightEndTime) > 0) {
- right.splice(ri + rgl, 0, {
- from: rightEndTime,
- until: leftEndTime,
- group: left[0].group,
- });
- rgl++;
- }
- if (AbsoluteTime.cmp(leftEndTime, rightEndTime) < 0) {
- left.splice(li + lgl, 0, {
- from: leftEndTime,
- until: rightEndTime,
- group: right[0].group,
- });
- lgl++;
- }
-
- //now both lists are non empty and (starts,ends) at the same time
- while (li < lgs + lgl && ri < rgs + rgl) {
- if (
- AbsoluteTime.cmp(left[li].from, timeCut) !== 0 &&
- AbsoluteTime.cmp(right[ri].from, timeCut) !== 0
- ) {
- // timeCut comes from the latest "until" (expiration from the previous)
- // and this value comes from the latest left or right
- // it should be the same as the "from" from one of the latest left or right
- // otherwise it means that there is missing a gap object in the middle
- // the list is not complete and the behavior is undefined
- throw Error(
- "one of the list is not completed: list[i].until !== list[i+1].from",
- );
- }
-
- pairList.push({
- left: left[li].fee,
- right: right[ri].fee,
- from: timeCut,
- until: AbsoluteTime.never(),
- group: currentGroup,
- });
+ return result;
+ };
+ const leftGroups = byGroup(left);
+ const rightGroups = byGroup(right);
+ const groups = [...new Set([...leftGroups.keys(), ...rightGroups.keys()])];
+ groups.sort((a, b) => {
+ const numeric = Number.parseFloat(a) - Number.parseFloat(b);
+ return Number.isNaN(numeric) || numeric === 0
+ ? a.localeCompare(b)
+ : numeric;
+ });
- if (left[li].until.t_ms === right[ri].until.t_ms) {
- timeCut = left[li].until;
- ri++;
- li++;
- } else if (left[li].until.t_ms < right[ri].until.t_ms) {
- timeCut = left[li].until;
- li++;
- } else if (left[li].until.t_ms > right[ri].until.t_ms) {
- timeCut = right[ri].until;
- ri++;
- }
- pairList[pairList.length - 1].until = timeCut;
-
- // if (
- // (li < left.length && left[li].group !== currentGroup) ||
- // (ri < right.length && right[ri].group !== currentGroup)
- // ) {
- // //value changed, should break
- // //this if will catch when both (left and right) change at the same time
- // //if just one side changed it will catch in the while condition
- // break;
- // }
- }
- }
- //one of the list left or right can still have elements
- if (li < left.length) {
- let timeCut =
- pairList.length > 0 &&
- pairList[pairList.length - 1].group === left[li].group
- ? pairList[pairList.length - 1].until
- : left[li].from;
- while (li < left.length) {
- pairList.push({
- left: left[li].fee,
- right: undefined,
- from: timeCut,
- until: left[li].until,
- group: left[li].group,
- });
- timeCut = left[li].until;
- li++;
- }
- }
- if (ri < right.length) {
- let timeCut =
- pairList.length > 0 &&
- pairList[pairList.length - 1].group === right[ri].group
- ? pairList[pairList.length - 1].until
- : right[ri].from;
- while (ri < right.length) {
- pairList.push({
- right: right[ri].fee,
- left: undefined,
- from: timeCut,
- until: right[ri].until,
- group: right[ri].group,
+ const feeAt = (
+ entries: FeeDescription[],
+ moment: AbsoluteTime,
+ ): AmountString | undefined =>
+ entries.find(
+ (entry) =>
+ AbsoluteTime.cmp(entry.from, moment) <= 0 &&
+ AbsoluteTime.cmp(moment, entry.until) < 0,
+ )?.fee;
+
+ const result: FeeDescriptionPair[] = [];
+ for (const group of groups) {
+ const leftEntries = leftGroups.get(group) ?? [];
+ const rightEntries = rightGroups.get(group) ?? [];
+ const boundaries = [...leftEntries, ...rightEntries].flatMap((entry) => [
+ entry.from,
+ entry.until,
+ ]);
+ boundaries.sort(AbsoluteTime.cmp);
+ const uniqueBoundaries = boundaries.filter(
+ (boundary, index) =>
+ index === 0 || AbsoluteTime.cmp(boundaries[index - 1], boundary) !== 0,
+ );
+ for (let i = 0; i + 1 < uniqueBoundaries.length; i++) {
+ const from = uniqueBoundaries[i];
+ const until = uniqueBoundaries[i + 1];
+ result.push({
+ group,
+ from,
+ until,
+ left: feeAt(leftEntries, from),
+ right: feeAt(rightEntries, from),
});
- timeCut = right[ri].until;
- ri++;
}
}
- return pairList;
+ return result;
}
/**
