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 }