Branch data Line data Source code
1 : : /********************************************************************
2 : : * gnc-autoclear.cpp -- Knapsack algorithm functions *
3 : : * *
4 : : * Copyright 2020 Cristian Klein <cristian@kleinlabs.eu> *
5 : : * Copyright 2021 Christopher Lam to clear same-amount splits *
6 : : * *
7 : : * This program is free software; you can redistribute it and/or *
8 : : * modify it under the terms of the GNU General Public License as *
9 : : * published by the Free Software Foundation; either version 2 of *
10 : : * the License, or (at your option) any later version. *
11 : : * *
12 : : * This program is distributed in the hope that it will be useful, *
13 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of *
14 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
15 : : * GNU General Public License for more details. *
16 : : * *
17 : : * You should have received a copy of the GNU General Public License*
18 : : * along with this program; if not, contact: *
19 : : * *
20 : : * Free Software Foundation Voice: +1-617-542-5942 *
21 : : * 51 Franklin Street, Fifth Floor Fax: +1-617-542-2652 *
22 : : * Boston, MA 02110-1301, USA gnu@gnu.org *
23 : : *******************************************************************/
24 : :
25 : : #include <config.h>
26 : :
27 : : #include <glib/gi18n.h>
28 : :
29 : : #include "Account.h"
30 : : #include "Account.hpp"
31 : : #include "Split.h"
32 : : #include "Transaction.h"
33 : : #include "gnc-autoclear.h"
34 : :
35 : : #include <optional>
36 : : #include <vector>
37 : : #include <numeric>
38 : : #include <algorithm>
39 : : #include <cstdint>
40 : : #include <chrono>
41 : : #include <stdexcept>
42 : : #include <cinttypes>
43 : : #include <charconv>
44 : : #include <cstring>
45 : :
46 : : #define log_module "gnc.autoclear"
47 : :
48 : : struct RuntimeMonitor
49 : : {
50 : : uint64_t m_counter = 0;
51 : : std::optional<double> m_seconds;
52 : : std::chrono::steady_clock::time_point m_start;
53 : 38 : RuntimeMonitor (double seconds) : m_start(std::chrono::steady_clock::now())
54 : : {
55 : 38 : if (seconds > 0) m_seconds = seconds;
56 : 38 : };
57 : 0 : double get_elapsed ()
58 : : {
59 : 0 : return std::chrono::duration_cast<std::chrono::duration<double>>(std::chrono::steady_clock::now() - m_start).count();
60 : : }
61 : 1280 : bool should_abort ()
62 : : {
63 : 1280 : if (!m_seconds.has_value()) return false;
64 : 0 : if (++m_counter % 100000 != 0) return false;
65 : 0 : return get_elapsed() > *m_seconds;
66 : : }
67 : : };
68 : :
69 : : struct SplitInfo
70 : : {
71 : : int64_t m_amount;
72 : : int64_t m_rem_pos;
73 : : int64_t m_rem_neg;
74 : : Split* m_split;
75 : : };
76 : :
77 : : using SplitInfoVec = std::vector<SplitInfo>;
78 : : using SplitVec = std::vector<Split*>;
79 : :
80 : : struct Solution
81 : : {
82 : : bool abort = false;
83 : : SplitVec splits;
84 : : };
85 : :
86 : : static const char*
87 : 0 : path_to_str(const SplitInfoVec& path)
88 : : {
89 : 0 : if (path.empty()) return "<empty>";
90 : :
91 : : static char buff[1000];
92 : 0 : char* p = buff;
93 : 0 : char* end = buff + sizeof(buff);
94 : 0 : for (const auto& split_info : path)
95 : : {
96 : 0 : if (p != buff)
97 : : {
98 : 0 : if (p < end) *p++ = '|';
99 : 0 : else return "<overflow>";
100 : : }
101 : 0 : auto res = std::to_chars (p, end, split_info.m_amount);
102 : 0 : if (res.ec == std::errc()) p = res.ptr;
103 : 0 : else return "<overflow>";
104 : : }
105 : 0 : p = std::min (end - 1, p);
106 : 0 : *p = '\0';
107 : 0 : return buff;
108 : : }
109 : :
110 : : static void
111 : 1580 : subset_sum (SplitInfoVec::const_iterator iter,
112 : : SplitInfoVec::const_iterator end,
113 : : SplitInfoVec& path, Solution& solution,
114 : : int64_t target, RuntimeMonitor& monitor)
115 : : {
116 : 1580 : DEBUG ("this=%" PRId64" target=%" PRId64 " rem_pos=%" PRId64
117 : : " rem_neg=%" PRId64 " path=%s",
118 : : iter == end ? 0 : iter->m_amount, target,
119 : : iter == end ? 0 : iter->m_rem_pos,
120 : : iter == end ? 0 : iter->m_rem_neg, path_to_str (path));
121 : :
122 : 1580 : if (target == 0)
123 : : {
124 : 30 : DEBUG ("SOLUTION FOUND: %s%s", path_to_str (path),
125 : : solution.splits.empty() ? "" : " ABORT: AMBIGUOUS");
126 : 30 : if (!solution.splits.empty())
127 : 6 : solution.abort = true;
128 : : else
129 : : {
130 : 24 : solution.splits.resize (path.size());
131 : 24 : std::transform (path.begin(), path.end(), solution.splits.begin(),
132 : 51 : [](SplitInfo& i){ return i.m_split; });
133 : 809 : return;
134 : : }
135 : : }
136 : :
137 : 1556 : if (solution.abort || iter == end)
138 : 276 : return;
139 : :
140 : 1280 : if (monitor.should_abort())
141 : : {
142 : 0 : DEBUG ("ABORT: timeout");
143 : 0 : solution.abort = true;
144 : 0 : return;
145 : : }
146 : :
147 : 1280 : if (target < iter->m_rem_neg || target > iter->m_rem_pos)
148 : : {
149 : 509 : DEBUG ("PRUNE target=%" PRId64 " rem_pos=%" PRId64" rem_neg=%" PRId64,
150 : : target, iter->m_rem_pos, iter->m_rem_neg);
151 : 509 : return;
152 : : }
153 : :
154 : 771 : auto next = std::next(iter);
155 : :
156 : : // 1st path: use current_num
157 : 771 : path.push_back (*iter);
158 : 771 : subset_sum (next, end, path, solution, target - iter->m_amount, monitor);
159 : 771 : path.pop_back ();
160 : :
161 : : // 2nd path: skip current_num
162 : 771 : subset_sum (next, end, path, solution, target, monitor);
163 : : }
164 : :
165 : : GList *
166 : 39 : gnc_account_get_autoclear_splits (Account *account, gnc_numeric toclear_value,
167 : : time64 end_date, GError **error,
168 : : double max_seconds)
169 : : {
170 : 39 : g_return_val_if_fail (account && error, nullptr);
171 : :
172 : 39 : auto scu{xaccAccountGetCommoditySCU (account)};
173 : 396 : auto numeric_to_int64 = [scu](gnc_numeric num) -> int64_t
174 : : {
175 : : return gnc_numeric_num
176 : 396 : (gnc_numeric_convert
177 : 396 : (num, scu, GNC_HOW_DENOM_EXACT | GNC_HOW_RND_NEVER));
178 : 39 : };
179 : :
180 : 39 : int64_t target{numeric_to_int64 (toclear_value)};
181 : 39 : SplitInfoVec splits;
182 : 396 : for (auto split : xaccAccountGetSplits (account))
183 : : {
184 : 357 : if (xaccTransGetDate (xaccSplitGetParent (split)) > end_date)
185 : 0 : break;
186 : 357 : int64_t amt{numeric_to_int64 (xaccSplitGetAmount (split))};
187 : 357 : if (xaccSplitGetReconcile (split) != NREC)
188 : 104 : target -= amt;
189 : 253 : else if (amt == 0)
190 : 3 : DEBUG ("skipping zero-amount split %p", split);
191 : : else
192 : 250 : splits.push_back ({amt, 0, 0, split});
193 : : }
194 : :
195 : 39 : static GQuark autoclear_quark = g_quark_from_static_string ("autoclear");
196 : 39 : if (target == 0)
197 : : {
198 : 1 : g_set_error (error, autoclear_quark, 1, "%s",
199 : : "Account is already at Auto-Clear Balance.");
200 : 1 : return nullptr;
201 : : }
202 : :
203 : : // sort splits in descending absolute amount
204 : 38 : std::sort (splits.begin(), splits.end(),
205 : 676 : [](const SplitInfo& a, const SplitInfo& b)
206 : : {
207 : 676 : int64_t aa = std::llabs(a.m_amount);
208 : 676 : int64_t bb = std::llabs(b.m_amount);
209 : 676 : return (aa == bb) ? a.m_amount > b.m_amount : aa > bb;
210 : : });
211 : :
212 : : // for each split, precompute sums of remaining pos or neg amounts
213 : 38 : int64_t rem_pos{0}, rem_neg{0};
214 : 38 : std::for_each (splits.rbegin(), splits.rend(),
215 : 236 : [&rem_pos, &rem_neg](SplitInfo& s)
216 : : {
217 : 236 : s.m_rem_pos = rem_pos += std::max<int64_t>(s.m_amount, 0);
218 : 236 : s.m_rem_neg = rem_neg += std::min<int64_t>(s.m_amount, 0);
219 : 236 : });
220 : :
221 : 38 : RuntimeMonitor monitor{max_seconds};
222 : 38 : Solution solution;
223 : 38 : SplitInfoVec path;
224 : 38 : path.reserve (splits.size());
225 : :
226 : 38 : subset_sum (splits.begin(), splits.end(), path, solution, target, monitor);
227 : :
228 : 38 : DEBUG ("finished subset_sum in %f seconds", monitor.get_elapsed());
229 : :
230 : 38 : if (solution.splits.empty() || solution.abort)
231 : : {
232 : 20 : g_set_error (error, autoclear_quark, 1, "%s",
233 : : "The selected amount cannot be cleared.");
234 : 20 : return nullptr;
235 : : }
236 : :
237 : : return std::accumulate
238 : 18 : (solution.splits.begin(), solution.splits.end(),
239 : 18 : static_cast<GList*>(nullptr), g_list_prepend);
240 : 39 : }
|
