1 /// HashGraph Event
2 module tagion.hashgraph.Round;
3 
4 //import std.stdio;
5 
6 import std.datetime; // Date, DateTime
7 import std.algorithm.iteration : cache, each, filter, fold, joiner, map, reduce;
8 import std.algorithm.searching;
9 import std.algorithm.searching : all, any, canFind, count, until;
10 import std.algorithm.sorting : sort;
11 import std.array : array;
12 import std.conv;
13 import std.format;
14 import std.range;
15 import std.range : enumerate, tee;
16 import std.range.primitives : isBidirectionalRange, isForwardRange, isInputRange, walkLength;
17 import std.stdio;
18 import std.traits : ReturnType, Unqual;
19 import std.traits;
20 import std.typecons;
21 import std.typecons : No;
22 import tagion.basic.Debug;
23 import tagion.basic.Types : Buffer;
24 import tagion.basic.basic : EnumText, basename, buf_idup, this_dot;
25 import tagion.crypto.Types : Pubkey;
26 import tagion.hashgraph.Event;
27 import tagion.hashgraph.HashGraph : HashGraph;
28 import tagion.hashgraph.HashGraphBasic : EvaPayload, EventBody, EventPackage, Tides, higher, isAllVotes, isMajority;
29 import tagion.hashgraphview.EventMonitorCallbacks;
30 import tagion.hibon.Document : Document;
31 import tagion.hibon.HiBON : HiBON;
32 import tagion.hibon.HiBONRecord;
33 import tagion.logger.Logger;
34 import tagion.utils.BitMask : BitMask;
35 import tagion.utils.Miscellaneous;
36 import tagion.utils.StdTime;
37 
38 /// Handles the round information for the events in the Hashgraph
39 @safe
40 class Round {
41     //    bool erased;
42     enum uint total_limit = 3;
43     enum int coin_round_limit = 10;
44     protected {
45         Round _previous;
46         Round _next;
47         bool _decided;
48     }
49     immutable long number;
50 
51     package Event[] _events;
52     public BitMask famous_mask;
53 
54     /**
55  * Compare the round number 
56  * Params:
57  *   rhs = round to be checked
58  * Returns: true if equal or less than
59  */
60     @nogc bool lessOrEqual(const Round rhs) pure const nothrow {
61         return (number - rhs.number) <= 0;
62     }
63 
64     /**
65      * Number of events in a round should be the same 
66      * as the number of nodes in the hashgraph
67      * Returns: number of nodes in the round 
68      */
69     @nogc const(uint) node_size() pure const nothrow {
70         return cast(uint) _events.length;
71     }
72 
73     /**
74      * Construct a round from the previous round
75      * Params:
76      *   previous = previous round
77      *   node_size = size of events in a round
78      */
79     private this(Round previous, const size_t node_size) pure nothrow {
80         if (previous) {
81             number = previous.number + 1;
82             previous._next = this;
83             _previous = previous;
84         }
85         else {
86             number = 0;
87         }
88         _events = new Event[node_size];
89     }
90 
91     /**
92      * All the events in the first ooccurrences of this round
93      * Returns: all events in a round
94      */
95     @nogc
96     const(Event[]) events() const pure nothrow {
97         return _events;
98     }
99 
100     /**
101      * Adds the even to round
102      * Params:
103      *   event = the event to be added
104      */
105     package void add(Event event) pure nothrow
106     in {
107         assert(_events[event.node_id] is null, "Event at node_id " ~ event.node_id.to!string ~ " should only be added once");
108     }
109     do {
110         _events[event.node_id] = event;
111         event._round = this;
112     }
113 
114     /**
115      * Check of the round has no events
116      * Returns: true of the round is empty
117      */
118     @nogc
119     bool empty() const pure nothrow {
120         return !_events.any!((e) => e !is null);
121     }
122 
123     /**
124      * Counts the number of events which has been set in this round
125      * Returns: number of events set
126      */
127     @nogc
128     size_t event_count() const pure nothrow {
129         return _events.count!((e) => e !is null);
130     }
131 
132     /**
133      * Remove the event from the round 
134      * Params:
135      *   event = event to be removed
136      */
137     @nogc
138     package void remove(const(Event) event) nothrow
139     in {
140         assert(event.isEva || _events[event.node_id] is event,
141                 "This event does not exist in round at the current node so it can not be remove from this round");
142         assert(event.isEva || !empty, "No events exists in this round");
143     }
144     do {
145         if (!event.isEva && _events[event.node_id]) {
146             _events[event.node_id] = null;
147         }
148     }
149 
150     /**
151      * Scrap all rounds and events from this round and downwards 
152      * Params:
153      *   hashgraph = the hashgraph owning the events/rounds
154      */
155     private void scrap(HashGraph hashgraph) @trusted
156     in {
157         assert(!_previous, "Round can not be scrapped due that a previous round still exists");
158     }
159     do {
160         uint count;
161         void scrap_events(Event e) {
162             if (e !is null) {
163                 count++;
164                 if (Event.callbacks) {
165                     Event.callbacks.remove(e);
166                 }
167                 scrap_events(e._mother);
168                 e.disconnect(hashgraph);
169                 e.destroy;
170             }
171         }
172 
173         foreach (node_id, e; _events) {
174             scrap_events(e);
175         }
176         if (_next) {
177             _next._previous = null;
178             _next = null;
179         }
180     }
181 
182     /**
183      * Check if the round has been decided
184      * Returns: true if the round has been decided
185      */
186     @nogc bool decided() const pure nothrow {
187         return _decided;
188     }
189 
190     const(Round) next() const pure nothrow {
191         return _next;
192     }
193 
194     /**
195      * Get the event a the node_id 
196      * Params:
197      *   node_id = node id number
198      * Returns: 
199      *   Event at the node_id
200      */
201     @nogc
202     inout(Event) event(const size_t node_id) pure inout {
203         return _events[node_id];
204     }
205 
206     /**
207      * Previous round from this round
208      * Returns: previous round
209      */
210     @nogc
211     package Round previous() pure nothrow {
212         return _previous;
213     }
214 
215     @nogc
216     const(Round) previous() const pure nothrow {
217         return _previous;
218     }
219 
220     /**
221  * Range from this round and down
222  * Returns: range of rounds 
223  */
224     @nogc
225     package Rounder.Range!false opSlice() pure nothrow {
226         return Rounder.Range!false(this);
227     }
228 
229     /// Ditto
230     @nogc
231     Rounder.Range!true opSlice() const pure nothrow {
232         return Rounder.Range!true(this);
233     }
234 
235     invariant {
236         assert(!_previous || (_previous.number + 1 is number));
237         assert(!_next || (_next.number - 1 is number));
238     }
239 
240     /**
241      * The rounder takes care of cleaning up old round 
242      * and keeps track of if an round has been decided or can be decided
243      */
244     struct Rounder {
245         Round last_round;
246         Round last_decided_round;
247         HashGraph hashgraph;
248         Round[] voting_round_per_node;
249 
250         @disable this();
251 
252         this(HashGraph hashgraph) pure nothrow {
253             this.hashgraph = hashgraph;
254             last_round = new Round(null, hashgraph.node_size);
255             voting_round_per_node = last_round.repeat(hashgraph.node_size).array;
256         }
257 
258         package void erase() {
259             void local_erase(Round r) @trusted {
260                 if (r !is null) {
261                     local_erase(r._previous);
262                     r.scrap(hashgraph);
263                     r.destroy;
264                 }
265             }
266 
267             Event.scrapping = true;
268             scope (exit) {
269                 Event.scrapping = false;
270             }
271             last_decided_round = null;
272             local_erase(last_round);
273         }
274 
275         //Cleans up old round and events if they are no-longer needed
276 
277         package
278         void dustman() {
279             void local_dustman(Round r) {
280                 if (r !is null) {
281                     local_dustman(r._previous);
282                     r.scrap(hashgraph);
283                 }
284             }
285 
286             Event.scrapping = true;
287             scope (exit) {
288                 Event.scrapping = false;
289             }
290             if (hashgraph.scrap_depth != 0) {
291                 int depth = hashgraph.scrap_depth;
292                 for (Round r = last_decided_round; r !is null; r = r._previous) {
293                     depth--;
294                     if (depth < 0) {
295                         local_dustman(r);
296                         break;
297                     }
298                 }
299             }
300         }
301 
302         /**
303   * Number of round epoch in the rounder queue
304   * Returns: size of the queue
305    */
306         @nogc
307         size_t length() const pure nothrow {
308             return this[].walkLength;
309         }
310 
311         /**
312      * Number of the same as hashgraph
313      * Returns: number of nodes
314      */
315         uint node_size() const pure nothrow
316         in {
317             assert(last_round, "Last round must be initialized before this function is called");
318         }
319         do {
320             return cast(uint)(last_round._events.length);
321 
322         }
323 
324         /**
325      * Sets the round for an event and creates an new round if needed
326      * Params:
327      *   e = event
328      */
329         void next_round(Event e) nothrow
330         in {
331             assert(last_round, "Base round must be created");
332             assert(last_decided_round, "Last decided round must exist");
333             assert(e, "Event must create before a round can be added");
334         }
335         out {
336             assert(e._round !is null);
337         }
338         do {
339             scope (exit) {
340                 e._round.add(e);
341             }
342             if (e._round && e._round._next) {
343                 e._round = e._round._next;
344             }
345             else {
346                 e._round = new Round(last_round, hashgraph.node_size);
347                 last_round = e._round;
348                 // if (Event.callbacks) {
349                 //     Event.callbacks.round_seen(e);
350                 // }
351             }
352         }
353 
354         bool isEventInLastDecidedRound(const(Event) event) const pure nothrow @nogc {
355             if (!last_decided_round) {
356                 return false;
357             }
358 
359             return last_decided_round.events
360                 .filter!((e) => e !is null)
361                 .map!(e => e.event_package.fingerprint)
362                 .canFind(event.event_package.fingerprint);
363         }
364 
365         /**
366      * Check of a round has been decided
367      * Params:
368      *   test_round = round to be tested
369      * Returns: 
370      */
371         @nogc
372         bool decided(const Round test_round) pure const nothrow {
373             bool _decided(const Round r) pure nothrow {
374                 if (r) {
375                     if (test_round is r) {
376                         return true;
377                     }
378                     return _decided(r._next);
379                 }
380                 return false;
381             }
382 
383             return _decided(last_decided_round);
384         }
385 
386         /**
387      * Calculates the number of rounds since the last decided round
388      * Returns: number of undecided roundes 
389      */
390         @nogc
391         long coin_round_distance() pure const nothrow {
392             return last_round.number - last_decided_round.number;
393         }
394 
395         /**
396      * Number of decided round in cached in memory
397      * Returns: Number of cached dicided rounds
398      */
399         @nogc
400         uint cached_decided_count() pure const nothrow {
401             uint _cached_decided_count(const Round r, const uint i = 0) pure nothrow {
402                 if (r) {
403                     return _cached_decided_count(r._previous, i + 1);
404                 }
405                 return i;
406             }
407 
408             return _cached_decided_count(last_round);
409         }
410 
411         /**
412      * Check the coin round limit
413      * Returns: true if the coin round has beed exceeded 
414      */
415         @nogc
416         bool check_decided_round_limit() pure const nothrow {
417             return cached_decided_count > total_limit;
418         }
419 
420         void check_decide_round() {
421             auto round_to_be_decided = last_decided_round._next;
422             if (!voting_round_per_node.all!(r => r.number > round_to_be_decided.number)) {
423                 return;
424             }
425             collect_received_round(round_to_be_decided, hashgraph);
426             round_to_be_decided._decided = true;
427             last_decided_round = round_to_be_decided;
428             // if (hashgraph._rounds.voting_round_per_node.all!(r => r.number > round_to_be_decided.number)
429             // {
430             //     check_decided_round(hashgraph);        
431             // } 
432         }
433 
434         /**
435      * Call to collect and order the epoch
436      * Params:
437      *   r = decided round to collect events to produce the epoch
438      *   hashgraph = hashgraph which ownes this rounds
439      */
440 
441         package void collect_received_round(Round r, HashGraph hashgraph) {
442 
443             auto famous_witnesses = r._events.filter!(e => e && r.famous_mask[e.node_id]);
444 
445             pragma(msg, "fixme(bbh) potential fault at boot of network if youngest_son_ancestor[x] = null");
446             auto famous_witness_youngest_son_ancestors = famous_witnesses.map!(e => e._youngest_son_ancestors).joiner;
447 
448             Event[] consensus_son_tide = r._events.find!(e => e !is null).front._youngest_son_ancestors.dup();
449 
450             foreach (son_ancestor; famous_witness_youngest_son_ancestors.filter!(e => e !is null)) {
451                 if (consensus_son_tide[son_ancestor.node_id] is null) {
452                     continue;
453                 }
454                 if (higher(consensus_son_tide[son_ancestor.node_id].order, son_ancestor.order)) {
455                     consensus_son_tide[son_ancestor.node_id] = son_ancestor;
456                 }
457             }
458 
459             version (EPOCH_FIX) {
460                 auto consensus_tide = consensus_son_tide
461                     .filter!(e => e !is null)
462                     .filter!(e =>
463                             !(e[].retro
464                                 .until!(e => !famous_witnesses.all!(w => w.sees(e)))
465                                 .empty)
466                 )
467                     .map!(e =>
468                             e[].retro
469                                 .until!(e => !famous_witnesses.all!(w => w.sees(e)))
470                                 .array.back
471                 );
472             }
473             else {
474                 auto consensus_tide = consensus_son_tide
475                     .filter!(e => e !is null)
476                     .map!(e =>
477                             e[].retro
478                                 .until!(e => !famous_witnesses.all!(w => w.sees(e)))
479                                 .array.back
480                 );
481 
482             }
483 
484             auto event_collection = consensus_tide
485                 .map!(e => e[].until!(e => e._round_received !is null))
486                 .joiner.array;
487 
488             event_collection.each!(e => e._round_received = r);
489 
490             hashgraph.epoch(event_collection, r);
491         }
492 
493         package void vote(HashGraph hashgraph, size_t vote_node_id) {
494             voting_round_per_node[vote_node_id] = voting_round_per_node[vote_node_id]._next;
495             Round current_round = voting_round_per_node[vote_node_id];
496             if (voting_round_per_node.all!(r => !higher(current_round.number, r.number))) {
497                 check_decide_round();
498             }
499 
500             while (current_round._next !is null) {
501                 current_round = current_round._next;
502                 foreach (e; current_round._events.filter!(e => e !is null)) {
503                     e.calc_vote(hashgraph, vote_node_id);
504                 }
505             }
506         }
507 
508         /**
509      * Range from this round and down
510      * Returns: range of rounds 
511      */
512         @nogc
513         package Range!false opSlice() pure nothrow {
514             return Range!false(last_round);
515         }
516 
517         /// Ditto
518         @nogc
519         Range!true opSlice() const pure nothrow {
520             return Range!true(last_round);
521         }
522 
523         /**
524      * Range of rounds 
525      */
526         @nogc
527         struct Range(bool CONST = true) {
528             private Round round;
529             this(const Round round) pure nothrow @trusted {
530                 this.round = cast(Round) round;
531             }
532 
533             pure nothrow {
534                 static if (CONST) {
535                     const(Round) front() const {
536                         return round;
537                     }
538                 }
539                 else {
540                     Round front() {
541                         return round;
542                     }
543                 }
544 
545                 alias back = front;
546 
547                 bool empty() const {
548                     return round is null;
549                 }
550 
551                 void popBack() {
552                     round = round._next;
553                 }
554 
555                 void popFront() {
556                     round = round._previous;
557                 }
558 
559                 Range save() {
560                     return Range(round);
561                 }
562 
563             }
564 
565         }
566 
567         static assert(isInputRange!(Range!true));
568         static assert(isForwardRange!(Range!true));
569         static assert(isBidirectionalRange!(Range!true));
570     }
571 
572 }