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 3089 : 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 2304 : 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 435 : 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 114 : 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 : }
|
