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 : : const char* abort = nullptr;
83 : : gint abort_id = Autoclear::ABORT_NONE;
84 : : SplitVec splits;
85 : : };
86 : :
87 : : static const char*
88 : 0 : path_to_str(const SplitInfoVec& path)
89 : : {
90 : 0 : if (path.empty()) return "<empty>";
91 : :
92 : : static char buff[1000];
93 : 0 : char* p = buff;
94 : 0 : char* end = buff + sizeof(buff);
95 : 0 : for (const auto& split_info : path)
96 : : {
97 : 0 : if (p != buff)
98 : : {
99 : 0 : if (p < end) *p++ = '|';
100 : 0 : else return "<overflow>";
101 : : }
102 : 0 : auto res = std::to_chars (p, end, split_info.m_amount);
103 : 0 : if (res.ec == std::errc()) p = res.ptr;
104 : 0 : else return "<overflow>";
105 : : }
106 : 0 : p = std::min (end - 1, p);
107 : 0 : *p = '\0';
108 : 0 : return buff;
109 : : }
110 : :
111 : : static void
112 : 1580 : subset_sum (SplitInfoVec::const_iterator iter,
113 : : SplitInfoVec::const_iterator end,
114 : : SplitInfoVec& path, Solution& solution,
115 : : int64_t target, RuntimeMonitor& monitor)
116 : : {
117 : 1580 : DEBUG ("this=%" PRId64" target=%" PRId64 " rem_pos=%" PRId64
118 : : " rem_neg=%" PRId64 " path=%s",
119 : : iter == end ? 0 : iter->m_amount, target,
120 : : iter == end ? 0 : iter->m_rem_pos,
121 : : iter == end ? 0 : iter->m_rem_neg, path_to_str (path));
122 : :
123 : 1580 : if (target == 0)
124 : : {
125 : 30 : DEBUG ("SOLUTION FOUND: %s%s", path_to_str (path),
126 : : solution.splits.empty() ? "" : " ABORT: AMBIGUOUS");
127 : 30 : if (!solution.splits.empty())
128 : : {
129 : 6 : solution.abort_id = Autoclear::ABORT_MULTI;
130 : 6 : solution.abort = N_("Cannot uniquely clear splits. Found multiple possibilities.");
131 : 809 : return;
132 : : }
133 : : else
134 : : {
135 : 24 : solution.splits.resize (path.size());
136 : 24 : std::transform (path.begin(), path.end(), solution.splits.begin(),
137 : 51 : [](SplitInfo& i){ return i.m_split; });
138 : 24 : return;
139 : : }
140 : : }
141 : :
142 : 1550 : if (solution.abort_id != Autoclear::ABORT_NONE || iter == end)
143 : 270 : return;
144 : :
145 : 1280 : if (monitor.should_abort())
146 : : {
147 : 0 : DEBUG ("ABORT: timeout");
148 : 0 : solution.abort_id = Autoclear::ABORT_TIMEOUT;
149 : 0 : solution.abort = N_("Auto-clear exceeds allocated time");
150 : 0 : return;
151 : : }
152 : :
153 : 1280 : if (target < iter->m_rem_neg || target > iter->m_rem_pos)
154 : : {
155 : 509 : DEBUG ("PRUNE target=%" PRId64 " rem_pos=%" PRId64" rem_neg=%" PRId64,
156 : : target, iter->m_rem_pos, iter->m_rem_neg);
157 : 509 : return;
158 : : }
159 : :
160 : 771 : auto next = std::next(iter);
161 : :
162 : : // 1st path: use current_num
163 : 771 : path.push_back (*iter);
164 : 771 : subset_sum (next, end, path, solution, target - iter->m_amount, monitor);
165 : 771 : path.pop_back ();
166 : :
167 : : // 2nd path: skip current_num
168 : 771 : subset_sum (next, end, path, solution, target, monitor);
169 : : }
170 : :
171 : : GList *
172 : 39 : gnc_account_get_autoclear_splits (Account *account, gnc_numeric toclear_value,
173 : : time64 end_date, GError **error,
174 : : double max_seconds)
175 : : {
176 : 39 : g_return_val_if_fail (account && error, nullptr);
177 : :
178 : 39 : auto scu{xaccAccountGetCommoditySCU (account)};
179 : 396 : auto numeric_to_int64 = [scu](gnc_numeric num) -> int64_t
180 : : {
181 : : return gnc_numeric_num
182 : 396 : (gnc_numeric_convert
183 : 396 : (num, scu, GNC_HOW_DENOM_EXACT | GNC_HOW_RND_NEVER));
184 : 39 : };
185 : :
186 : 39 : int64_t target{numeric_to_int64 (toclear_value)};
187 : 39 : SplitInfoVec splits;
188 : 396 : for (auto split : xaccAccountGetSplits (account))
189 : : {
190 : 357 : if (xaccTransGetDate (xaccSplitGetParent (split)) > end_date)
191 : 0 : break;
192 : 357 : int64_t amt{numeric_to_int64 (xaccSplitGetAmount (split))};
193 : 357 : if (xaccSplitGetReconcile (split) != NREC)
194 : 104 : target -= amt;
195 : 253 : else if (amt == 0)
196 : 3 : DEBUG ("skipping zero-amount split %p", split);
197 : : else
198 : 250 : splits.push_back ({amt, 0, 0, split});
199 : : }
200 : :
201 : 39 : static GQuark autoclear_quark = g_quark_from_static_string ("autoclear");
202 : 39 : if (target == 0)
203 : : {
204 : 1 : g_set_error (error, autoclear_quark, Autoclear::ABORT_NOP, "%s",
205 : : N_("Account is already at Auto-Clear Balance."));
206 : 1 : return nullptr;
207 : : }
208 : :
209 : : // sort splits in descending absolute amount
210 : 38 : std::sort (splits.begin(), splits.end(),
211 : 676 : [](const SplitInfo& a, const SplitInfo& b)
212 : : {
213 : 676 : int64_t aa = std::llabs(a.m_amount);
214 : 676 : int64_t bb = std::llabs(b.m_amount);
215 : 676 : return (aa == bb) ? a.m_amount > b.m_amount : aa > bb;
216 : : });
217 : :
218 : : // for each split, precompute sums of remaining pos or neg amounts
219 : 38 : int64_t rem_pos{0}, rem_neg{0};
220 : 38 : std::for_each (splits.rbegin(), splits.rend(),
221 : 236 : [&rem_pos, &rem_neg](SplitInfo& s)
222 : : {
223 : 236 : s.m_rem_pos = rem_pos += std::max<int64_t>(s.m_amount, 0);
224 : 236 : s.m_rem_neg = rem_neg += std::min<int64_t>(s.m_amount, 0);
225 : 236 : });
226 : :
227 : 38 : RuntimeMonitor monitor{max_seconds};
228 : 38 : Solution solution;
229 : 38 : SplitInfoVec path;
230 : 38 : path.reserve (splits.size());
231 : :
232 : 38 : subset_sum (splits.begin(), splits.end(), path, solution, target, monitor);
233 : :
234 : 38 : DEBUG ("finished subset_sum in %f seconds", monitor.get_elapsed());
235 : :
236 : 38 : if (solution.splits.empty())
237 : : {
238 : 14 : g_set_error (error, autoclear_quark, Autoclear::ABORT_UNREACHABLE, "%s",
239 : : N_("The selected amount cannot be cleared."));
240 : 14 : return nullptr;
241 : : }
242 : 24 : else if (solution.abort_id)
243 : : {
244 : 6 : g_set_error (error, autoclear_quark,
245 : : solution.abort_id, "%s", solution.abort);
246 : 6 : return nullptr;
247 : : }
248 : :
249 : : return std::accumulate
250 : 18 : (solution.splits.begin(), solution.splits.end(),
251 : 18 : static_cast<GList*>(nullptr), g_list_prepend);
252 : 39 : }
|
