1 ////////////////////////////////////////////////////////////////////////////////
2 //
3 // Copyright 2016 - 2021, Thomas Lauf, Paul Beckingham, Federico Hernandez.
4 //
5 // Permission is hereby granted, free of charge, to any person obtaining a copy
6 // of this software and associated documentation files (the "Software"), to deal
7 // in the Software without restriction, including without limitation the rights
8 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 // copies of the Software, and to permit persons to whom the Software is
10 // furnished to do so, subject to the following conditions:
11 //
12 // The above copyright notice and this permission notice shall be included
13 // in all copies or substantial portions of the Software.
14 //
15 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
16 // OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 // THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
21 // SOFTWARE.
22 //
23 // https://www.opensource.org/licenses/mit-license.php
24 //
25 ////////////////////////////////////////////////////////////////////////////////
26
27 #include <algorithm>
28 #include <cassert>
29
30 #include <cmake.h>
31 #include <shared.h>
32 #include <format.h>
33 #include <Datetime.h>
34 #include <Duration.h>
35 #include <timew.h>
36 #include <algorithm>
37 #include <iostream>
38 #include <IntervalFactory.h>
39
40 ////////////////////////////////////////////////////////////////////////////////
41 // Read rules and extract all holiday definitions. Create a Range for each
42 // one that spans from midnight to midnight.
getHolidays(const Rules & rules)43 std::vector <Range> getHolidays (const Rules& rules)
44 {
45 std::vector <Range> results;
46 for (auto& holiday : rules.all ("holidays."))
47 {
48 auto lastDot = holiday.rfind ('.');
49 if (lastDot != std::string::npos)
50 {
51 Range r;
52 Datetime d (holiday.substr (lastDot + 1), "Y_M_D");
53 r.start = d;
54 ++d;
55 r.end = d;
56 results.push_back (r);
57 }
58 }
59
60 debug (format ("Found {1} holidays", results.size ()));
61 return results;
62 }
63
64 ////////////////////////////////////////////////////////////////////////////////
65 // [1] Read holiday definitions from the rules, extract their dates and create
66 // a set of Range from them.
67 // [2] For 'exc day ...' exclusions, separate into daysOn and daysOff sets,
68 // based on whether the exclusion is additive.
69 // [3] Treat daysOff as additional holidays.
70 // [4] Subtract daysOn from the set of holidays.
71 // [5] Take all the 'exc <dayOfWeek> ...' exclusions and expand them into
72 // concrete ranges within the overall range, adding them to the results.
73 //
74 // The result is the complete set of untrackable time that lies within the
75 // input range. This will be a set of nights, weekends, holidays and lunchtimes.
getAllExclusions(const Rules & rules,const Range & range)76 std::vector <Range> getAllExclusions (
77 const Rules& rules,
78 const Range& range)
79 {
80 // Start with the set of all holidays, intersected with range.
81 std::vector <Range> results;
82 results = addRanges (range, results, getHolidays (rules));
83
84 // Load all exclusions from configuration.
85 std::vector <Exclusion> exclusions;
86 for (auto& name : rules.all ("exclusions."))
87 exclusions.push_back (Exclusion (lowerCase (name), rules.get (name)));
88 debug (format ("Found {1} exclusions", exclusions.size ()));
89
90 // Find exclusions 'exc day on <date>' and remove from holidays.
91 // Find exclusions 'exc day off <date>' and add to holidays.
92 std::vector <Range> daysOn;
93 std::vector <Range> daysOff;
94 for (auto& exclusion : exclusions)
95 {
96 if (exclusion.tokens ()[1] == "day")
97 {
98 if (exclusion.additive ())
99 for (auto& r : exclusion.ranges (range))
100 daysOn.push_back (r);
101 else
102 for (auto& r : exclusion.ranges (range))
103 daysOff.push_back (r);
104 }
105 }
106
107 // daysOff are combined with existing holidays.
108 results = addRanges (range, results, daysOff);
109 if (! daysOn.empty ())
110 debug (format ("Found {1} additional working days", daysOn.size ()));
111 if (! daysOff.empty ())
112 debug (format ("Found {1} additional non-working days", daysOff.size ()));
113
114 // daysOn are subtracted from the existing holidays.
115 results = subtractRanges (results, daysOn);
116
117 // Expand all exclusions that are not 'exc day ...' into excluded ranges that
118 // overlap with range.
119 std::vector <Range> exclusionRanges;
120 for (auto& exclusion : exclusions)
121 if (exclusion.tokens ()[1] != "day")
122 for (auto& r : exclusion.ranges (range))
123 exclusionRanges.push_back (r);
124
125 return merge (addRanges (range, results, exclusionRanges));
126 }
127
128 ////////////////////////////////////////////////////////////////////////////////
129 // Potentially expand the latest interval into a collection of synthetic
130 // intervals.
expandLatest(const Interval & latest,const Rules & rules)131 std::vector <Interval> expandLatest (const Interval& latest, const Rules& rules)
132 {
133 int current_id = 0;
134 std::vector <Interval> intervals;
135 // If the latest interval is open, check for synthetic intervals
136 if (latest.is_open ())
137 {
138 auto exclusions = getAllExclusions (rules, {latest.start, Datetime ()});
139 if (! exclusions.empty ())
140 {
141 std::vector <Interval> flattened = flatten (latest, exclusions);
142
143 // If flatten() converted the latest interval into a group of synthetic
144 // intervals, the number of returned intervals will be greater than 1,
145 // otherwise, it just returned the non-synthetic latest interval.
146 if (flattened.size () > 1)
147 {
148 std::reverse (flattened.begin (), flattened.end ());
149 for (auto interval : flattened)
150 {
151 interval.synthetic = true;
152 interval.id = ++current_id;
153 intervals.push_back (std::move (interval));
154 }
155 }
156 }
157 }
158
159 if (intervals.empty ())
160 {
161 intervals.push_back (latest);
162 intervals.back().id = 1;
163 }
164 return intervals;
165 }
166
167 ////////////////////////////////////////////////////////////////////////////////
168 // Convert what would be synthetic intervals into real intervals in the database
flattenDatabase(Database & database,const Rules & rules)169 void flattenDatabase (Database& database, const Rules& rules)
170 {
171 Interval latest = getLatestInterval (database);
172 std::vector <Interval> expanded = expandLatest (latest, rules);
173
174 if (expanded.size () > 1)
175 {
176 bool verbose = rules.getBoolean ("verbose");
177 database.deleteInterval (latest);
178 for (auto it = expanded.rbegin (); it != expanded.rend (); ++it)
179 {
180 it->synthetic = false;
181 database.addInterval (*it, verbose);
182 }
183 }
184 }
185
186 ////////////////////////////////////////////////////////////////////////////////
187 // Return collection of intervals (synthetic included) sorted by id
getIntervalsByIds(Database & database,const Rules & rules,const std::set<int> & ids)188 std::vector <Interval> getIntervalsByIds (
189 Database& database,
190 const Rules& rules,
191 const std::set <int>& ids)
192 {
193 std::vector <Interval> intervals;
194 intervals.reserve (ids.size ());
195
196 int current_id = 0;
197 auto id_it = ids.begin ();
198 auto id_end = ids.end ();
199
200 auto it = database.begin ();
201 auto end = database.end ();
202
203 // Because the latest recorded interval may be expanded into synthetic
204 // intervals, we'll handle it specially
205 if (it != end )
206 {
207 Interval latest = IntervalFactory::fromSerialization (*it);
208 ++it;
209
210 for (auto& interval : expandLatest (latest, rules))
211 {
212 ++current_id;
213
214 if (id_it == id_end)
215 {
216 break;
217 }
218
219 if (interval.id == *id_it)
220 {
221 intervals.push_back (interval);
222 ++id_it;
223 }
224 }
225 }
226
227 // We'll find remaining intervals from the normal recorded intervals
228 for ( ; (it != end) && (id_it != id_end); ++it)
229 {
230 ++current_id;
231
232 if (current_id == *id_it)
233 {
234 Interval interval = IntervalFactory::fromSerialization (*it);
235 interval.id = current_id;
236 intervals.push_back (interval);
237 ++id_it;
238 }
239 }
240
241 // We did not find all the ids we were looking for.
242 if (id_it != id_end)
243 {
244 throw format("ID '@{1}' does not correspond to any tracking.", *id_it);
245 }
246
247 return intervals;
248 }
249
250 ////////////////////////////////////////////////////////////////////////////////
subset(const Interval & filter,const std::vector<Interval> & intervals)251 std::vector <Interval> subset (
252 const Interval& filter,
253 const std::vector <Interval>& intervals)
254 {
255 std::vector <Interval> all;
256 for (auto& interval : intervals)
257 if (matchesFilter (interval, filter))
258 all.push_back (interval);
259
260 return all;
261 }
262
263 ////////////////////////////////////////////////////////////////////////////////
subset(const Range & range,const std::vector<Range> & ranges)264 std::vector <Range> subset (
265 const Range& range,
266 const std::vector <Range>& ranges)
267 {
268 std::vector <Range> all;
269 for (auto& r : ranges) {
270 if (range.intersects (r)) {
271 all.push_back (r);
272 }
273 }
274
275 return all;
276 }
277
278 ////////////////////////////////////////////////////////////////////////////////
subset(const Range & range,const std::vector<Interval> & intervals)279 std::vector <Interval> subset (
280 const Range& range,
281 const std::vector <Interval>& intervals)
282 {
283 std::vector <Interval> all;
284 for (auto& interval : intervals) {
285 if (range.intersects (interval))
286 {
287 all.push_back (interval);
288 }
289 }
290
291 return all;
292 }
293
294 ////////////////////////////////////////////////////////////////////////////////
flatten(const Interval & interval,const std::vector<Range> & exclusions)295 std::vector <Interval> flatten (
296 const Interval& interval,
297 const std::vector <Range>& exclusions)
298 {
299 std::vector <Interval> all;
300
301 std::vector <Range> enclosed;
302 for (auto& e : exclusions)
303 if (interval.encloses (e))
304 enclosed.push_back (e);
305
306 Datetime now;
307 for (auto& result : subtractRanges ({interval}, enclosed))
308 {
309 if (interval.is_open() && result.start > now)
310 {
311 break;
312 }
313
314 Interval chunk {interval};
315 chunk.setRange (result);
316
317 all.push_back (chunk);
318 }
319
320 return all;
321 }
322
323 ////////////////////////////////////////////////////////////////////////////////
324 // Simply merges a vector of ranges, without data loss.
rangeCompare(Range left,Range right)325 static bool rangeCompare (Range left, Range right)
326 {
327 return left.start < right.start;
328 }
329
merge(const std::vector<Range> & ranges)330 std::vector <Range> merge (
331 const std::vector <Range>& ranges)
332 {
333 // Short cut.
334 if (ranges.size () < 2)
335 return ranges;
336
337 std::vector <Range> sorted {ranges};
338 std::sort (sorted.begin (), sorted.end (), rangeCompare);
339
340 unsigned int cursor = 0;
341 int merges = 0;
342 for (unsigned int i = 0; i < sorted.size (); ++i)
343 {
344 if (cursor && sorted[cursor - 1].overlaps (sorted[i]))
345 {
346 sorted[cursor - 1] = sorted[cursor - 1].combine (sorted[i]);
347 ++merges;
348 }
349 else
350 {
351 sorted[cursor] = sorted[i];
352 ++cursor;
353 }
354 }
355
356 if (merges)
357 sorted.resize (ranges.size () - merges);
358
359 return sorted;
360 }
361
362 ////////////////////////////////////////////////////////////////////////////////
363 // Subset both ranges and additions by limits, and combine.
addRanges(const Range & limits,const std::vector<Range> & ranges,const std::vector<Range> & additions)364 std::vector <Range> addRanges (
365 const Range& limits,
366 const std::vector <Range>& ranges,
367 const std::vector <Range>& additions)
368 {
369 std::vector <Range> results;
370
371 for (auto& range : ranges)
372 if (limits.overlaps (range))
373 results.push_back (range);
374
375 for (auto& addition : additions)
376 if (limits.overlaps (addition))
377 results.push_back (addition);
378
379 return results;
380 }
381
382 ////////////////////////////////////////////////////////////////////////////////
383 // Subtract a set of Ranges from another set of Ranges, all within a defined range.
subtractRanges(const std::vector<Range> & ranges,const std::vector<Range> & subtractions)384 std::vector <Range> subtractRanges (
385 const std::vector <Range>& ranges,
386 const std::vector <Range>& subtractions)
387 {
388 std::vector <Range> results = ranges;
389 for (auto& s : subtractions)
390 {
391 std::vector <Range> split_results;
392 for (auto& range : results)
393 for (auto& split_range : range.subtract (s))
394 split_results.push_back (split_range);
395
396 results = split_results;
397 }
398
399 return results;
400 }
401
402 ////////////////////////////////////////////////////////////////////////////////
403 // An interval matches a filter range if the start/end overlaps
matchesRange(const Interval & interval,const Range & filter)404 bool matchesRange (const Interval& interval, const Range& filter)
405 {
406 return ((!filter.is_started() && !filter.is_ended()) || interval.intersects (filter));
407 }
408
409 ////////////////////////////////////////////////////////////////////////////////
410 // An interval matches a filter interval if the start/end overlaps, and all
411 // filter interval tags are found in the interval.
412 //
413 // [1] interval.end.toEpoch () == 0
414 // [2] interval.end > filter.start
415 // [3] filter.end.toEpoch () == 0
416 // [4] interval.start < filter.end
417 //
418 // Match: (1 || 2) && (3 || 4)
419
420 // filter closed [--------) 1 2 3 4 5 6 result
421 // --------------------------------------------------------------------------
422 // A [--------) . . 0 0 0 1 0 0 0
423 // B [--------) . 0 1 0 1 1 1 1
424 // C . [----) . 0 1 0 1 1 1 1
425 // D . [--------) 0 1 0 1 1 1 1
426 // E . . [--------) 0 1 0 0 1 0 0
427 // F [-------------) 0 1 0 1 1 1 1
428 // G [... . 1 0 0 1 1 1 1
429 // H . [... . 1 0 0 1 1 1 1
430 // I . . [... 1 0 0 0 1 0 0
431 //
432 //
433 //
434 // filter open [... 1 2 3 4 5 6 result
435 // --------------------------------------------------------------------------
436 // A [--------) . 0 0 1 0 0 1 0
437 // B [--------) 0 1 1 0 1 1 1
438 // C . [----) 0 1 1 0 1 1 1
439 // D . [--------) 0 1 1 0 1 1 1
440 // E . [--------) 0 1 1 0 1 1 1
441 // F [-------------) 0 1 1 0 1 1 1
442 // G [... 1 0 1 0 1 1 1
443 // H . [... 1 0 1 0 1 1 1
444 // I . [... 1 0 1 0 1 1 1
445 //
matchesFilter(const Interval & interval,const Interval & filter)446 bool matchesFilter (const Interval& interval, const Interval& filter)
447 {
448 if (matchesRange (interval, filter))
449 {
450 for (auto& tag : filter.tags ())
451 {
452 if (! interval.hasTag (tag))
453 {
454 return false;
455 }
456 }
457 return true;
458 }
459
460 return false;
461 }
462
463 ////////////////////////////////////////////////////////////////////////////////
464 // Take an interval and clip it to the range
clip(const Interval & interval,const Range & range)465 Interval clip (const Interval& interval, const Range& range)
466 {
467 if (! range.is_started () ||
468 range.total () == 0)
469 return interval;
470
471 Interval clipped {interval};
472 if (clipped.start.toEpoch () &&
473 clipped.start < range.start)
474 clipped.start = range.start;
475
476 if (clipped.end.toEpoch () &&
477 clipped.end > range.end)
478 clipped.end = range.end;
479
480 return clipped;
481 }
482
483 ////////////////////////////////////////////////////////////////////////////////
484 // Return collection of intervals that match the filter (synthetic intervals
485 // included) sorted by date
getTracked(Database & database,const Rules & rules,Interval & filter)486 std::vector <Interval> getTracked (
487 Database& database,
488 const Rules& rules,
489 Interval& filter)
490 {
491 int current_id = 0;
492 std::vector <Interval> intervals;
493
494 auto it = database.begin ();
495 auto end = database.end ();
496
497 // Because the latest recorded interval may be expanded into synthetic
498 // intervals, we'll handle it specially
499 if (it != end )
500 {
501 Interval latest = IntervalFactory::fromSerialization (*it);
502 ++it;
503
504 for (auto& interval : expandLatest (latest, rules))
505 {
506 ++current_id;
507 if (matchesFilter (interval, filter))
508 {
509 interval.id = current_id;
510 intervals.push_back (interval);
511 }
512 }
513 }
514
515 for (; it != end; ++it)
516 {
517 Interval interval = IntervalFactory::fromSerialization(*it);
518 interval.id = ++current_id;
519
520 if (matchesFilter (interval, filter))
521 {
522 intervals.push_back (std::move (interval));
523 }
524 else if ((interval.start < filter.start) && ! interval.intersects (filter))
525 {
526 // Since we are moving backwards in time, and the intervals are in sorted
527 // order, if the filter is after the interval, we know there will be no
528 // more matches
529 break;
530 }
531 }
532
533 debug (format ("Loaded {1} tracked intervals", intervals.size ()));
534
535 // By default intervals are sorted by id, but getTracked needs to return the
536 // intervals sorted by date, which are ids in reverse order.
537 std::reverse (intervals.begin (), intervals.end ());
538 return intervals;
539 }
540
541 ////////////////////////////////////////////////////////////////////////////////
542 // Untracked time is that which is not excluded, and not filled. Gaps.
getUntracked(Database & database,const Rules & rules,Interval & filter)543 std::vector <Range> getUntracked (
544 Database& database,
545 const Rules& rules,
546 Interval& filter)
547 {
548 bool found_match = false;
549 std::vector <Range> inclusion_ranges;
550 for (auto& line : database)
551 {
552 Interval i = IntervalFactory::fromSerialization (line);
553 if (matchesFilter (i, filter))
554 {
555 inclusion_ranges.push_back (i);
556 found_match = true;
557 }
558 else if (found_match)
559 {
560 // If we already had a match, and now we do not, since the database is in
561 // order from most recent to oldest inclusion, we can be sure that there
562 // will not be any further matches.
563 break;
564 }
565 }
566
567 auto available = subtractRanges ({filter}, getAllExclusions (rules, filter));
568 auto untracked = subtractRanges (available, inclusion_ranges);
569 debug (format ("Loaded {1} untracked ranges", untracked.size ()));
570 return untracked;
571 }
572
573 ////////////////////////////////////////////////////////////////////////////////
getLatestInterval(Database & database)574 Interval getLatestInterval (Database& database)
575 {
576 Interval i;
577 auto latestEntry = database.getLatestEntry ();
578 if (! latestEntry.empty ())
579 {
580 i = IntervalFactory::fromSerialization (latestEntry);
581 i.id = 1;
582 }
583
584 return i;
585 }
586
587 ////////////////////////////////////////////////////////////////////////////////
getFullDay(const Datetime & day)588 Range getFullDay (const Datetime& day)
589 {
590 int y;
591 int m;
592 int d;
593 day.toYMD (y, m, d);
594 return Range (Datetime (y, m, d, 0, 0, 0),
595 Datetime (y, m, d, 24, 0, 0));
596 }
597
598 ////////////////////////////////////////////////////////////////////////////////
599