1 /// Handles the lower level operation of DART database 2 module tagion.dart.DARTFile; 3 @safe: 4 private { 5 import core.thread : Fiber; 6 import std.algorithm.comparison : equal; 7 import std.algorithm.iteration : each, filter; 8 import std.algorithm.searching : all, count, maxElement; 9 import std.algorithm.sorting : sort; 10 import std.array; 11 import std.conv : to; 12 import std.exception : assumeWontThrow; 13 import std.format; 14 import std.range; 15 import std.range.primitives : ElementType, isInputRange; 16 import std.stdio : File; 17 import std.traits; 18 import std.typecons : Flag, No, Yes; 19 import std.typecons; 20 import tagion.basic.Debug : __write; 21 import tagion.basic.Types : Buffer, isBufferType, isTypedef, mut; 22 import tagion.basic.basic : EnumText, assumeTrusted, isinit; 23 import tagion.crypto.SecureInterfaceNet : HashNet, SecureNet; 24 import tagion.crypto.Types : Fingerprint; 25 import tagion.dart.BlockFile; 26 import tagion.dart.DARTBasic; 27 import tagion.dart.DARTException : DARTException; 28 import tagion.dart.Recorder; 29 import tagion.hibon.Document : Document; 30 import tagion.hibon.HiBON : HiBON; 31 import tagion.hibon.HiBONRecord : GetLabel, exclude, record_filter = filter, label, recordType; 32 33 //import tagion.basic.basic; 34 // import std.stdio : writefln, writeln; 35 import tagion.basic.tagionexceptions : Check; 36 import tagion.dart.DARTRim; 37 import tagion.dart.RimKeyRange : rimKeyRange; 38 import tagion.hibon.HiBONRecord; 39 import std.bitmanip; 40 } 41 42 /++ 43 + Gets the rim key from a buffer 44 + 45 + Returns; 46 + fingerprint[rim] 47 +/ 48 ubyte rim_key(F)(F rim_keys, const uint rim) pure if (isBufferType!F) { 49 if (rim >= rim_keys.length) { 50 debug __write("%(%02X%) rim=%d", rim_keys, rim); 51 } 52 return rim_keys[rim]; 53 } 54 55 enum SECTOR_MAX_SIZE = 1 << (ushort.sizeof * 8); 56 57 import std.algorithm; 58 59 alias check = Check!DARTException; 60 enum KEY_SPAN = ubyte.max + 1; 61 62 /++ 63 + DART File system 64 + Distribute Achive of Random Transction 65 + This class handels the CRUD Database 66 + 67 + The archive is hashed and store in structure similar to merkle trees datastruct. 68 + Which here is called at sparsed merkle tree the sparse merkle is section in to rims 69 + in hierarchy which is where each rim contains a sub-tree called Branches. If a rim 70 + Doens't branche out it contais a Leave which contains a Archive 71 + 72 +/ 73 class DARTFile { 74 75 version (FLAT_DART) { 76 enum default_flat = Yes.flat; 77 } 78 else { 79 enum default_flat = No.flat; 80 } 81 import tagion.dart.BlockFile : Index; 82 83 immutable(string) filename; 84 const Flag!"flat" flat; 85 protected RecordFactory manufactor; 86 87 protected { 88 BlockFile blockfile; 89 Fingerprint _fingerprint; 90 } 91 92 protected enum _params = [ 93 "dart_indices", 94 "bullseye", 95 ]; 96 97 mixin(EnumText!("Params", _params)); 98 99 enum flat_marker = "flat"; 100 enum MIN_BLOCK_SIZE = 0x80; 101 static create(string filename, const HashNet net, const uint block_size = MIN_BLOCK_SIZE, const uint max_size = 0x80_000, const Flag!"flat" flat = default_flat) 102 in { 103 assert(block_size >= MIN_BLOCK_SIZE, 104 format("Block size is too small for %s, %d must be langer than %d", filename, block_size, MIN_BLOCK_SIZE)); 105 } 106 do { 107 auto id_name = net.multihash; 108 if (flat) { 109 id_name ~= ":" ~ flat_marker; 110 } 111 BlockFile.create(filename, id_name, block_size, DARTFile.stringof, max_size); 112 } 113 /++ 114 + A file set by filename should be create by the BlockFile 115 + before it can be used as a DARTFile 116 117 + Params: 118 + net = Is the network object is for Hashing etc.. 119 + filename = File name of the dart which much be created via the BlockFile.create method 120 121 + Examples: 122 --- 123 enum BLOCK_SIZE=0x80; // Block size use in the BlockFile 124 enum filename="some_filename.DART"; 125 auto net= new SomeNet; 126 auto blockfile=BlockFile.create(filename, "Some description text", BLOCK_SIZE); 127 // Open the DART File 128 auto dartfile=new DARTFile(net, filename); 129 --- 130 +/ 131 this(const HashNet net, string filename, const Flag!"read_only" read_only = No.read_only) { 132 blockfile = BlockFile(filename, read_only); 133 this.manufactor = RecordFactory(net); 134 this.filename = filename; 135 136 137 138 .check(blockfile.headerBlock.checkLabel(DARTFile.stringof), 139 format("Wrong label %s expected %s for %s", 140 blockfile.headerBlock.Label, 141 DARTFile.stringof, filename)); 142 143 Flag!"flat" checkId() { 144 if (blockfile.headerBlock.checkId(net.multihash)) { 145 return No.flat; 146 } 147 148 if (blockfile.headerBlock.checkId(net.multihash ~ ":" ~ flat_marker)) { 149 return Yes.flat; 150 } 151 152 .check(false, 153 format("Wrong hash type %s expected %s for %s", 154 net.multihash, blockfile.headerBlock.Id, filename)); 155 156 assert(0); 157 } 158 flat=checkId; 159 if (blockfile.root_index) { 160 const data = blockfile.load(blockfile.root_index); 161 const doc = Document(data); 162 auto branches = Branches(doc); 163 _fingerprint = branches.fingerprint(this); 164 } 165 } 166 167 /** 168 * Close the DARTFile 169 */ 170 void close() @trusted { 171 blockfile.close; 172 blockfile.destroy; 173 blockfile = null; 174 } 175 176 /* 177 * The Merkle root of the DARTFile 178 * Returns: the `bullseye` of the DARTFile 179 */ 180 Fingerprint fingerprint() pure const nothrow { 181 return _fingerprint; 182 } 183 184 /// Ditto for fingerprint 185 alias bullseye = fingerprint; 186 187 /** 188 * Creates a recorder factor 189 * Returns: 190 * recorder 191 */ 192 RecordFactory.Recorder recorder() nothrow { 193 return manufactor.recorder; 194 } 195 196 /** 197 * Creates a recorder from a document using the RecorderFactory used by the DART 198 * Params: 199 * doc = list of archives in document format 200 * Returns: 201 * a recorder of the document 202 */ 203 RecordFactory.Recorder recorder(const(Document) doc) { 204 return manufactor.recorder(doc); 205 } 206 207 /** 208 * Ditto 209 * Params: 210 * archives = Archive data which contails an ordred list of archives 211 * Returns: 212 * recorder of the list of archives 213 */ 214 RecordFactory.Recorder recorder(RecordFactory.Recorder.Archives archives) nothrow { 215 return manufactor.recorder(archives); 216 } 217 218 struct Leave { 219 import tagion.hibon.HiBONRecord; 220 221 Index index; 222 Buffer fingerprint; 223 DARTIndex dart_index; 224 bool empty() pure const nothrow { 225 return (index is Index.init) && (fingerprint is null); 226 } 227 228 mixin HiBONRecord!(q{ 229 this(const Index index, const(Fingerprint) fingerprint, const(DARTIndex) dart_index) { 230 this.index = index; 231 this.fingerprint = cast(Buffer)fingerprint; 232 this.dart_index = dart_index; 233 234 } 235 }); 236 } 237 238 /** 239 * Data struct which contains the branches in sub-tree 240 */ 241 @recordType("$@B") struct Branches { 242 import std.stdio; 243 import tagion.hibon.HiBONJSON; 244 245 @exclude protected Fingerprint merkleroot; /// The sparsed Merkle root hash of the branches 246 @label("$prints") @optional @(record_filter.Initialized) protected Fingerprint[] _fingerprints; /// Array of all the Leaves hashes 247 @label("$darts") @(record_filter.Initialized) protected DARTIndex[] _dart_indices; /// Array of all the Leaves hashes 248 @label("$idx") @optional @(record_filter.Initialized) protected Index[] _indices; /// Array of index pointer to BlockFile 249 @exclude private bool done; 250 enum fingerprintsName = GetLabel!(_fingerprints).name; 251 enum dart_indicesName = GetLabel!(_dart_indices).name; 252 enum indicesName = GetLabel!(_indices).name; 253 this(Document doc) { 254 255 256 257 .check(isRecord(doc), format("Document is not a %s", ThisType.stringof)); 258 if (doc.hasMember(indicesName)) { 259 _indices = new Index[KEY_SPAN]; 260 foreach (e; doc[indicesName].get!Document[]) { 261 _indices[e.index] = e.get!Index; 262 } 263 } 264 if (doc.hasMember(fingerprintsName)) { 265 _fingerprints = new Fingerprint[KEY_SPAN]; 266 foreach (e; doc[fingerprintsName].get!Document) { 267 _fingerprints[e.index] = e.get!(Buffer).idup; 268 } 269 } 270 if (doc.hasMember(dart_indicesName)) { 271 _dart_indices = new DARTIndex[KEY_SPAN]; 272 foreach (e; doc[dart_indicesName].get!Document) { 273 _dart_indices[e.index] = e.get!(Buffer).idup; 274 } 275 } 276 } 277 278 auto keys() { 279 return _fingerprints.enumerate 280 .filter!(f => !f.value.empty) 281 .map!(f => f.index); 282 } 283 284 protected DARTIndex get_dart_index(const size_t key) pure nothrow { 285 if (_dart_indices) { 286 return _dart_indices[key]; 287 } 288 return DARTIndex.init; 289 } 290 291 auto opSlice() { 292 return keys.map!(key => Leave(indices[key], fingerprints[key], get_dart_index(key))); 293 } 294 295 DARTIndexRange dart_indices() const pure nothrow @nogc { 296 return DARTIndexRange(this); 297 } 298 299 struct DARTIndexRange { 300 const(Branches) owner; 301 private size_t _key; 302 pure nothrow @nogc { 303 this(const(Branches) owner) { 304 this.owner = owner; 305 } 306 307 DARTIndex opIndex(const size_t key) const { 308 return owner.dart_index(key); 309 } 310 311 bool empty() const { 312 return _key >= owner._dart_indices.length; 313 } 314 315 DARTIndex front() const { 316 return owner.dart_index(_key); 317 } 318 319 void popFront() { 320 while (_key < owner._dart_indices.length) { 321 _key++; 322 if (!owner._dart_indices.isinit) { 323 break; 324 } 325 326 } 327 } 328 } 329 } 330 /* 331 * Check if the Branches has storage indices 332 * Returns: true if the branch has BlockFile indices 333 */ 334 @nogc 335 bool hasIndices() const pure nothrow { 336 return _indices.length !is 0; 337 } 338 339 /** 340 * Params: 341 * key = key index of the branch 342 * Returns: 343 * The fingerprint at key 344 */ 345 Fingerprint fingerprint(const size_t key) pure const nothrow @nogc 346 in { 347 assert(key < KEY_SPAN); 348 } 349 do { 350 if (_fingerprints) { 351 return _fingerprints[key]; 352 } 353 return Fingerprint.init; 354 } 355 356 DARTIndex dart_index(const size_t key) pure const nothrow @nogc { 357 if (!_dart_indices.empty && !_dart_indices[key].isinit) { 358 return _dart_indices[key]; 359 } 360 return DARTIndex(cast(Buffer) fingerprint(key)); 361 } 362 /** 363 * Returns: 364 * All the fingerprints to the sub branches and archives 365 */ 366 @property 367 const(Fingerprint[]) fingerprints() pure const nothrow { 368 return _fingerprints; 369 } 370 371 /** 372 * Returns: 373 * All the blockfile pointers to the sub branches and archives 374 */ 375 @property 376 const(Index[]) indices() pure const nothrow { 377 return _indices; 378 } 379 380 /** 381 * Returns: 382 * The number of index pointer which points to Leave or Branches 383 * in the blockfile 384 */ 385 uint count() pure const { 386 return cast(uint) _indices.count!("a != b")(0); 387 } 388 389 /** 390 * Creates a HiBON from a the branches 391 * Params: 392 * exclude_indices = If this flag is `true` then indices is not generated 393 * Returns: HiBON of the branches 394 */ 395 HiBON toHiBON(const bool exclude_indices = false) const 396 in { 397 assert(merkleroot.isinit, "Fingerprint must be calcuted before toHiBON is called"); 398 } 399 do { 400 auto hibon = new HiBON; 401 auto hibon_fingerprints = new HiBON; 402 if (!exclude_indices) { 403 auto hibon_indices = new HiBON; 404 bool indices_set; 405 foreach (key, index; _indices) { 406 if (index !is Index.init) { 407 hibon_indices[key] = index; 408 409 410 411 .check(!_fingerprints[key].isinit, 412 format("Fingerprint key=%02X at index=%d is not defined", key, index)); 413 indices_set = true; 414 } 415 } 416 if (indices_set) { 417 hibon[indicesName] = hibon_indices; 418 } 419 } 420 foreach (key, print; _fingerprints) { 421 if (!print.isinit) { 422 hibon_fingerprints[key] = print; 423 } 424 } 425 if (_dart_indices) { 426 auto hibon_dart_indices = new HiBON; 427 foreach (key, dart_index; _dart_indices) { 428 if (!dart_index.isinit && fingerprints[key] != dart_index) { 429 430 hibon_dart_indices[key] = dart_index; 431 } 432 433 } 434 if (hibon_dart_indices.length) { 435 hibon[dart_indicesName] = hibon_dart_indices; 436 } 437 } 438 hibon[fingerprintsName] = hibon_fingerprints; 439 hibon[TYPENAME] = type_name; 440 return hibon; 441 } 442 443 /* 444 * Convert the Branches to a Document 445 * Returns: document 446 */ 447 const(Document) toDoc() const { 448 return Document(toHiBON); 449 } 450 451 import tagion.hibon.HiBONJSON : JSONString; 452 453 mixin JSONString; 454 455 import tagion.hibon.HiBONRecord : HiBONRecordType; 456 457 mixin HiBONRecordType; 458 459 /** 460 * Get the index number of Leave at the leave number key 461 * 462 * Params: 463 * key = Leave number of the branches 464 * 465 */ 466 Index index(const uint key) pure const { 467 if (empty) { 468 return Index.init; 469 } 470 else { 471 return _indices[key]; 472 } 473 } 474 475 /** 476 * Set the branch at leave-number key the leave 477 * 478 * Params: 479 * leave = Which contains the archive data 480 * key = leave number 481 */ 482 void opIndexAssign(const Leave leave, const uint key) { 483 if (_indices is null) { 484 _indices = new Index[KEY_SPAN]; 485 } 486 if (_fingerprints.isinit) { 487 _fingerprints = new Fingerprint[KEY_SPAN]; 488 } 489 if (!leave.dart_index.isinit) { 490 if (_dart_indices.isinit) { 491 _dart_indices = new DARTIndex[KEY_SPAN]; 492 493 } 494 _dart_indices[key] = leave.dart_index.mut; 495 496 } 497 _indices[key] = Index(leave.index); 498 _fingerprints[key] = leave.fingerprint; 499 } 500 501 /** 502 * Get the leave at key in the branches 503 * Params: 504 * key = leave-number 505 * Returns: 506 * The leave located at the leave-number key 507 * 508 */ 509 Leave opIndex(const uint key) { 510 if (empty) { 511 return Leave.init; 512 } 513 return Leave(_indices[key], _fingerprints[key], get_dart_index(key)); 514 } 515 516 /** 517 * Check if the branches has indices 518 * Returns: true if no indices 519 */ 520 bool empty() pure const { 521 if (_indices !is null) { 522 import std.algorithm.searching : any; 523 524 return !_indices.any!("a != 0"); 525 } 526 return true; 527 } 528 529 /** 530 * Merkle root of the branches 531 * Returns: fingerprint 532 */ 533 private Fingerprint fingerprint( 534 DARTFile dartfile) { 535 if (merkleroot.isinit) { 536 merkleroot = Fingerprint(sparsed_merkletree(dartfile.manufactor.net, _fingerprints, dartfile.flat)); 537 } 538 return merkleroot; 539 } 540 541 /** 542 * Dumps the branches information 543 */ 544 void dump() const { 545 import std.stdio; 546 547 foreach (key, index; _indices) { 548 if (index !is Index.init) { 549 writefln("branches[%02X]=%(%02x%)", key, _fingerprints[key]); 550 } 551 } 552 553 } 554 /** 555 * 556 * Returns: true if there is only one fingerprint left else false 557 */ 558 bool isSingle() pure const nothrow @nogc { 559 import std.range : take, walkLength; 560 561 return _fingerprints 562 .filter!(f => !f.isinit) 563 .take(2) 564 .walkLength == 1; 565 } 566 } 567 568 /** 569 * Reads the data at branch key 570 * Params: 571 * b = branches to read from 572 * key = key in the branch to read from 573 * Returns: the data a key 574 */ 575 Document load(ref const(Branches) b, const uint key) { 576 if ((key < KEY_SPAN) && (b.indices)) { 577 immutable index = b.indices[key]; 578 if (index !is Index.init) { 579 return blockfile.load(index); 580 } 581 } 582 return Document.init; 583 } 584 585 class RimWalkerFiber : Fiber { 586 immutable(Buffer) rim_paths; 587 protected Document doc; 588 protected bool _finished; 589 /** 590 * Sector for the walker 591 * Returns: the sector of the rim 592 */ 593 ushort sector() const pure nothrow 594 in { 595 assert(rim_paths.length >= ubyte.sizeof, assumeWontThrow(format( 596 "rim_paths is too short %d >= %d", rim_paths 597 .length, ubyte 598 .sizeof))); 599 } 600 do { 601 if (rim_paths.length == ubyte.sizeof) { 602 return ushort(rim_paths[0] << 8); 603 } 604 return bigEndianToNative!ushort(rim_paths[0 .. ushort.sizeof]); 605 } 606 /** 607 * Creates a walker from the DART path 608 * Params: 609 * rim_paths = rim selected path 610 */ 611 this(const(Buffer) rim_paths) @trusted 612 in { 613 assert(rim_paths.length >= ubyte.sizeof, format( 614 "Size of rim_paths should have a size of %d or more", ubyte 615 .sizeof)); 616 } 617 do { 618 this.rim_paths = rim_paths; 619 super(&run); 620 popFront; 621 } 622 623 final private void run() { 624 void traverse( 625 immutable Index index, 626 immutable uint rim = 0) @safe { 627 if (index !is Index.init) { 628 doc = this.outer.blockfile.load(index); 629 assert(!doc.empty, "Loaded document should not be empty"); 630 //const doc = Document(data); 631 if (rim < rim_paths.length) { 632 if (Branches.isRecord(doc)) { 633 const branches = Branches(doc); 634 // This branches 635 immutable key = rim_key(rim_paths, rim); 636 immutable next_index = branches.indices[key]; 637 traverse(next_index, rim + 1); 638 } 639 } 640 else { 641 if (Branches.isRecord(doc)) { 642 const branches = Branches(doc); 643 foreach (next_index; branches.indices) { 644 traverse(next_index, rim + 1); 645 } 646 } 647 else { 648 assumeTrusted!yield; 649 } 650 } 651 } 652 } 653 654 traverse(this.outer.blockfile.masterBlock.root_index); 655 _finished = true; 656 } 657 658 /* 659 * Move to next data element in the range 660 */ 661 @trusted 662 final void popFront() { 663 call; 664 } 665 666 /** 667 * Range empty 668 * Returns: true if empty 669 */ 670 final bool empty() const pure nothrow { 671 return _finished; 672 } 673 674 /** 675 * Front for the range 676 * Returns: the data at the range position 677 */ 678 final const(Document) front() const pure nothrow { 679 return doc; 680 } 681 } 682 683 /** 684 * A range which traverse the branches below the rim_paths 685 * The range build as a Fiber. 686 * 687 * Params: 688 * rim_paths = Set the starting rim_paths 689 * 690 * Returns: 691 * A range on DARTFile as a Fiber 692 */ 693 RimWalkerFiber rimWalkerRange(immutable(Buffer) rim_paths) { 694 return new RimWalkerFiber(rim_paths); 695 } 696 697 /** 698 * Create indet string a rim_level 699 * Params: 700 * rim = 701 * Returns: 702 */ 703 string indent(const uint rim_level) { 704 string local_indent(const uint rim_level, string indent_str = null) { 705 if (rim_level > 0) { 706 return local_indent(rim_level - 1, indent_str ~ indent_tab); 707 } 708 return indent_str; 709 } 710 711 return local_indent(rim_level); 712 } 713 714 pragma(msg, "fixme(alex); Remove loadAll function"); 715 HiBON loadAll(Archive.Type type = Archive.Type.ADD) { 716 auto recorder = manufactor.recorder; 717 void local_load( 718 const Index branch_index, 719 const ubyte rim_key = 0, 720 const uint rim = 0) @safe { 721 if (branch_index !is Index.init) { 722 immutable data = blockfile.load(branch_index); 723 const doc = Document(data); 724 if (Branches.isRecord(doc)) { 725 const branches = Branches(doc); 726 if (branches.indices.length) { 727 foreach (key, index; branches._indices) { 728 local_load(index, cast(ubyte) key, rim + 1); 729 } 730 } 731 } 732 recorder.insert(doc, type); 733 } 734 } 735 736 local_load(blockfile.masterBlock.root_index); 737 auto result = new HiBON; 738 uint i; 739 foreach (a; recorder[]) { 740 result[i] = a.toDoc; 741 i++; 742 } 743 return result; 744 } 745 746 /** 747 * Loads all the archives in the list of fingerprints 748 * 749 * Params: 750 * fingerprints = range of fingerprints 751 * type = types of archives 752 * Returns: 753 * recorder of the read archives 754 */ 755 RecordFactory.Recorder loads(Range)( 756 Range dart_indices, 757 Archive.Type type = Archive.Type.REMOVE) if (isInputRange!Range && is(ElementType!Range : const(DARTIndex))) { 758 759 import std.algorithm.comparison : min; 760 761 auto result = recorder; 762 void traverse_dart( 763 const Index branch_index, 764 DARTIndex[] ordered_dart_indices, 765 immutable uint rim = 0) @safe { 766 if ((ordered_dart_indices) && (branch_index !is Index.init)) { 767 immutable data = blockfile.load(branch_index); 768 const doc = Document(data); 769 if (Branches.isRecord(doc)) { 770 const branches = Branches(doc); 771 auto selected_dart_indices = ordered_dart_indices; 772 foreach (rim_key, index; branches._indices) { 773 uint pos; 774 while ((pos < selected_dart_indices.length) && 775 (rim_key is selected_dart_indices[pos].rim_key(rim))) { 776 pos++; 777 } 778 if (pos > 0) { 779 traverse_dart(index, selected_dart_indices[0 .. pos], rim + 1); 780 selected_dart_indices = selected_dart_indices[pos .. $]; 781 } 782 } 783 } 784 else { 785 // Loads the Archives into the archives 786 787 auto archive = new Archive(manufactor.net, doc, type); 788 if (ordered_dart_indices[0] == archive.dart_index) { 789 result.insert(archive); 790 } 791 792 } 793 } 794 } 795 796 auto sorted_dart_indices = dart_indices 797 .filter!(a => a.length !is 0) 798 .map!(a => DARTIndex(cast(Buffer) a)) 799 .array 800 .dup; 801 sorted_dart_indices.sort; 802 traverse_dart(blockfile.masterBlock.root_index, sorted_dart_indices); 803 return result; 804 } 805 806 DARTIndex[] checkload(Range)(Range dart_indices) if (isInputRange!Range && isBufferType!(ElementType!Range)) { 807 import std.algorithm : canFind; 808 809 auto result = loads(dart_indices)[] 810 .map!(a => a.dart_index); 811 812 auto not_found = dart_indices 813 .filter!(f => !canFind(result, f)) 814 .map!(f => cast(DARTIndex) f) 815 .array; 816 817 return not_found; 818 } 819 820 enum RIMS_IN_SECTOR = 2; 821 822 /// Wrapper function for the modify function. 823 Fingerprint modify(const(RecordFactory.Recorder) modifyrecords, const Flag!"undo" undo = No.undo) { 824 if (undo) { 825 return modify!(Yes.undo)(modifyrecords); 826 } 827 else { 828 return modify!(No.undo)(modifyrecords); 829 830 } 831 } 832 833 import core.demangle; 834 import std.traits; 835 836 pragma(msg, "modify ", mangle!(FunctionTypeOf!(DARTFile.modify!(No.undo)))("modify")); 837 /** 838 * $(SMALL_TABLE 839 * Sample of the DART Map 840 * | |key[0]|key[1]|key[2]|key[3]|key[4]| 841 * | rim | 00 | 01 | 02 | 03 | 04 | .... 842 * |------|------|------|------|------|------|----- 843 * | | 20 | A3 | 33 | B1 | 17 | -> arcive fingerprint=20_A3_33_B1_17.... 844 * | | ** | ** | ** | ** | 42 | -> arcive fingerprint=20_A3_33_B1_42.... 845 * | | ** | ** | 57 | B1 | 17 | -> arcive fingerprint=20_A3_57_B1_17.... 846 * | | ** | ** | ** | ** | 42 | -> arcive fingerprint=20_A3_57_B1_42.... 847 * | | ** | ** | C2 | | | -> arcive fingerprint=20_A3_C3.... 848 * | | ** | ** | CA | 48 | | -> arcive fingerprint=20_A3_CA_48.... 849 * | | ** | ** | ** | 68 | | -> arcive fingerprint=20_A3_CA_48.... 850 * ) 851 * $(B Sector=[key[0],key[1]]) <br> 852 * ### Note ** means the same value as above 853 * The first two rims is set the sector and the following is rims 854 * represents the key index into the Branches incices 855 * The modifyrecords contains the archives which is going to be added or deleted 856 * The type of archive tells which actions are going to be performed by the modifier 857 * If the function executes succesfully then the DART is updated or else it does not affect the DART 858 * The function returns the bullseye of the dart 859 */ 860 Fingerprint modify(Flag!"undo" undo)(const(RecordFactory.Recorder) modifyrecords) 861 in (blockfile.cache_empty, format("IN: THE CACHE MUST BE EMPTY WHEN PERFORMING NEW MODIFY len=%s", blockfile 862 .cache_len)) 863 do { 864 /** 865 * Inner function for the modify function. 866 * Note that this function is recursive and called from itself. 867 * Can be broken up into 3 sections. The first is for going through the branches 868 * In the sectors. Next section is for going through branches deeper than the sectors. 869 * The last section is responsible for acutally doing the work with the archives. 870 * Params: 871 * range = RimKeyRange to traverse with. 872 * branch_index = The branch index to modify. 873 * Returns: 874 */ 875 .check(!blockfile.read_only, format("Can not call a %s on a read-only DART", __FUNCTION__)); 876 Leave traverse_dart(Range)(Range range, const Index branch_index) @safe if (isInputRange!Range) 877 out { 878 assert(range.empty, "Must have been through the whole range and therefore empty on return"); 879 } 880 do { 881 // if the range is empty that means that nothing is located in it now. 882 if (range.empty) { 883 return Leave.init; 884 } 885 886 /// First section for going through the Branches in the sectors. 887 Index erase_block_index; 888 scope (success) { 889 blockfile.dispose(erase_block_index); 890 } 891 Branches branches; 892 if (range.rim < RIMS_IN_SECTOR) { 893 if (branch_index !is Index.init) { 894 branches = blockfile.load!Branches(branch_index); 895 .check(branches.hasIndices, 896 "DART failure within the sector rims the DART should contain a branch"); 897 } 898 899 while (!range.empty) { 900 auto sub_range = range.nextRim; 901 immutable rim_key = sub_range.front.dart_index.rim_key(sub_range.rim); 902 branches[rim_key] = traverse_dart(sub_range, branches.index(rim_key)); 903 } 904 erase_block_index = Index(branch_index); 905 906 if (branches.empty) { 907 return Leave.init; 908 } 909 910 return Leave(blockfile.save(branches).index, 911 branches.fingerprint(this), DARTIndex.init); 912 913 } 914 // Section for going through branches that are not in the sectors. 915 else { 916 if (branch_index !is Index.init) { 917 const doc = blockfile.cacheLoad(branch_index); 918 if (Branches.isRecord(doc)) { 919 branches = Branches(doc); 920 while (!range.empty) { 921 auto sub_range = range.nextRim; 922 immutable rim_key = sub_range.front.dart_index.rim_key(sub_range.rim); 923 branches[rim_key] = traverse_dart(sub_range, branches.index(rim_key)); 924 } 925 // if the range is empty then we return a null leave. 926 if (branches.empty) { 927 return Leave.init; 928 } 929 930 if (branches.isSingle && range.rim >= RIMS_IN_SECTOR) { 931 const single_leave = branches[].front; 932 const buf = cacheLoad(single_leave.index); 933 const single_doc = Document(buf); 934 935 if (!Branches.isRecord(single_doc)) { 936 return single_leave; 937 } 938 939 } 940 return Leave(blockfile.save(branches).index, branches.fingerprint(this), DARTIndex.init); 941 } 942 else { 943 // This is a standalone archive ("single"). 944 // DART does not store a branch this means that it contains a leave. 945 // Leave means and archive 946 // The new Archives is constructed to include the archive which is already in the DART 947 auto current_archive = recorder.archive(doc, Archive.Type.ADD); 948 scope (success) { 949 // The archive is erased and it will be added again to the DART 950 // if it not removed by and action in the record 951 blockfile.dispose(branch_index); 952 953 } 954 auto sub_range = range.save.filter!(a => a.dart_index == current_archive.dart_index); 955 956 if (sub_range.empty) { 957 range.add(current_archive); 958 } 959 960 } 961 } 962 // If there is only one archive left, it means we have traversed to the bottom of the tree 963 // Therefore we must return the leave if it is an ADD. 964 if (range.oneLeft) { 965 scope (exit) { 966 range.popFront; 967 } 968 if (range.type == Archive.Type.ADD) { 969 return Leave( 970 blockfile.save(range.front.store).index, 971 range.front.fingerprint, range.front.dart_index); 972 } 973 return Leave.init; 974 } 975 /// More than one archive is present. Meaning we have to traverse 976 /// Deeper into the tree. 977 while (!range.empty) { 978 const rim_key = range.front.dart_index.rim_key(range.rim + 1); 979 980 const leave = traverse_dart(range.nextRim, Index.init); 981 branches[rim_key] = leave; 982 } 983 /// If the branch is empty we return a NULL leave. 984 if (branches.empty) { 985 return Leave.init; 986 } 987 // If the branch isSingle then we have to move the branch / archives located in it upwards. 988 if (branches.isSingle) { 989 const single_leave = branches[].front; 990 const buf = cacheLoad(single_leave.index); 991 const single_doc = Document(buf); 992 993 if (!Branches.isRecord(single_doc)) { 994 return single_leave; 995 } 996 997 } 998 return Leave( 999 blockfile.save(branches).index, 1000 branches.fingerprint(this), DARTIndex.init); 1001 } 1002 1003 } 1004 1005 /// If our records is empty we return the previous fingerprint 1006 if (modifyrecords.empty) { 1007 return _fingerprint; 1008 } 1009 1010 // This check ensures us that we never have multiple add and deletes on the 1011 // same archive in the same recorder. 1012 .check(modifyrecords.length <= 1 || 1013 !modifyrecords[] 1014 .slide(2) 1015 .map!(a => a.front.dart_index == a.dropOne.front.dart_index) 1016 .any, 1017 "cannot have multiple operations on same dart-index in one modify"); 1018 1019 auto range = rimKeyRange!undo(modifyrecords); 1020 auto new_root = traverse_dart(range, blockfile.masterBlock.root_index); 1021 1022 scope (success) { 1023 // On success the new root_index is set and the DART is updated 1024 _fingerprint = new_root.fingerprint; 1025 if ((new_root.fingerprint is null) || (new_root.index is Index.init)) { 1026 // All data has been delete so a new blockfile is created 1027 blockfile.close; 1028 blockfile = BlockFile.reset(filename); 1029 } 1030 else { 1031 blockfile.root_index = new_root.index; 1032 blockfile.store; 1033 // blockfile.block_chains.clear; 1034 } 1035 } 1036 scope (failure) { 1037 // On failure drop the BlockFile and reopen it 1038 blockfile.close; 1039 blockfile = BlockFile(filename); 1040 } 1041 return Fingerprint(new_root.fingerprint); 1042 } 1043 1044 /** 1045 * Loads the branches from the DART at rim_path 1046 * Params: 1047 * rim_path = rim path select the branches 1048 * Returns: 1049 * the branches a the rim_path 1050 */ 1051 Branches branches(const(ubyte[]) rim_path, scope Index* branch_index = null) { 1052 Branches search(const(ubyte[]) rim_path, const Index index, const uint rim = 0) { 1053 const doc = blockfile.load(index); 1054 if (Branches.isRecord(doc)) { 1055 Branches branches = Branches(doc); 1056 if (rim < rim_path.length) { 1057 immutable rim_key = rim_path.rim_key(rim); 1058 immutable sub_index = branches._indices[rim_key]; 1059 if (sub_index !is Index.init) { 1060 return search(rim_path, sub_index, rim + 1); 1061 } 1062 } 1063 else { 1064 if (branch_index !is null) { 1065 *branch_index = Index(index); 1066 1067 } 1068 return branches; 1069 } 1070 } 1071 return Branches.init; 1072 } 1073 1074 if (blockfile.masterBlock.root_index is Index.init) { 1075 return Branches.init; 1076 } 1077 return search(rim_path, blockfile.masterBlock.root_index); 1078 } 1079 1080 enum indent_tab = "| .. "; 1081 /** 1082 * Dumps the dart as rim-path 1083 * Params: 1084 * full = true for full DART 1085 */ 1086 void dump( 1087 const SectorRange sectors = SectorRange.init, 1088 const Flag!"full" full = No.full, 1089 const uint depth = 0 1090 ) { 1091 import std.stdio; 1092 1093 writefln("EYE: %(%02X%)", _fingerprint); 1094 const from_rim = sectors.from_sector.nativeToBigEndian; 1095 const to_rim = sectors.to_sector.nativeToBigEndian; 1096 1097 void local_dump(const Index branch_index, 1098 const ubyte rim_key = 0, 1099 const uint rim = 0, 1100 Buffer rim_path = null, 1101 string indent = null) @safe { 1102 if (!branch_index.isinit && 1103 ((depth == 0) || (rim <= depth))) { 1104 immutable data = blockfile.load(branch_index); 1105 const doc = Document(data); 1106 if (Branches.isRecord(doc)) { 1107 auto branches = Branches(doc); 1108 string _indent; 1109 if (rim > 0) { 1110 rim_path ~= rim_key; 1111 if (!sectors.inRange(Rims(rim_path))) { 1112 return; 1113 } 1114 writefln("%s| %02X [%d]", indent, rim_key, branch_index); 1115 _indent = indent ~ indent_tab; 1116 } 1117 foreach (key, index; branches._indices) { 1118 local_dump(index, cast(ubyte) key, rim + 1, rim_path, _indent); 1119 } 1120 } 1121 else { 1122 immutable dart_index = manufactor.net.dartIndex(doc); 1123 auto lastRing = full ? dart_index.length : rim + 1; 1124 const hash_marker = doc.hasHashKey ? " #" : ""; 1125 writefln("%s%(%02x%) [%d]%s", 1126 indent, dart_index[0 .. lastRing], branch_index, hash_marker); 1127 } 1128 } 1129 } 1130 1131 Index index = blockfile.masterBlock.root_index; 1132 if (!sectors.isinit) { 1133 Buffer start_path = Rims(sectors.from_sector).path; 1134 local_dump(index, start_path[0], 0, null); 1135 return; 1136 } 1137 1138 local_dump(index); 1139 } 1140 1141 alias TraverseCallback = bool delegate( 1142 const(Document) doc, 1143 const Index branch_index, 1144 const uint rim, 1145 Buffer rim_path); 1146 1147 void traverse( 1148 const TraverseCallback dg, 1149 const SectorRange sectors = SectorRange.init, 1150 const uint depth = 0, 1151 const bool branches = true) { 1152 void local_traverse( 1153 const Index branch_index, 1154 const ubyte rim_key = 0, 1155 const uint rim = 0, 1156 Buffer rim_path = null) @safe { 1157 if (!branch_index.isinit && 1158 ((depth == 0) || (rim <= depth))) { 1159 immutable data = blockfile.load(branch_index); 1160 const doc = Document(data); 1161 if (dg(doc, branch_index, rim, rim_path)) { 1162 return; 1163 } 1164 if (Branches.isRecord(doc)) { 1165 auto branches = Branches(doc); 1166 if (rim > 0) { 1167 rim_path ~= rim_key; 1168 if (!sectors.inRange(Rims(rim_path))) { 1169 return; 1170 } 1171 } 1172 foreach (key, index; branches._indices) { 1173 local_traverse(index, cast(ubyte) key, rim + 1, rim_path); 1174 } 1175 } 1176 } 1177 } 1178 1179 Index index = blockfile.masterBlock.root_index; 1180 if (!sectors.isinit) { 1181 Buffer start_path = Rims(sectors.from_sector).path; 1182 local_traverse(index, start_path[0], 0, null); 1183 return; 1184 } 1185 1186 local_traverse(index); 1187 } 1188 1189 package Document cacheLoad(const Index index) { 1190 return Document(blockfile.cacheLoad(index)); 1191 } 1192 1193 HiBON search(Buffer[] owners, const(SecureNet) net) { 1194 import std.algorithm : canFind; 1195 import tagion.script.common; 1196 1197 TagionBill[] bills; 1198 1199 void local_load( 1200 const Index branch_index, 1201 const ubyte rim_key = 0, 1202 const uint rim = 0) @safe { 1203 if (branch_index !is Index.init) { 1204 const doc = blockfile.load(branch_index); 1205 if (Branches.isRecord(doc)) { 1206 const branches = Branches(doc); 1207 if (branches.indices.length) { 1208 foreach (key, index; branches._indices) { 1209 local_load(index, cast(ubyte) key, rim + 1); 1210 } 1211 } 1212 } 1213 if (TagionBill.isRecord(doc)) { 1214 auto bill = TagionBill(doc); 1215 if (owners.canFind(bill.owner)) { 1216 bills ~= bill; 1217 } 1218 } 1219 } 1220 } 1221 1222 local_load(blockfile.masterBlock.root_index); 1223 HiBON params = new HiBON; 1224 foreach (i, bill; bills) { 1225 params[i] = bill.toHiBON; 1226 } 1227 return params; 1228 1229 } 1230 1231 version (unittest) { 1232 1233 static { 1234 bool check(const(RecordFactory.Recorder) A, const(RecordFactory.Recorder) B) { 1235 return equal!(q{a.dart_index == b.dart_index})(A.archives[], B.archives[]); 1236 } 1237 1238 Fingerprint write(DARTFile dart, const(ulong[]) table, out RecordFactory.Recorder rec) { 1239 rec = records(dart.manufactor, table); 1240 return dart.modify(rec); 1241 } 1242 1243 DARTIndex[] dart_indices(RecordFactory.Recorder recorder) { 1244 DARTIndex[] results; 1245 foreach (a; recorder.archives) { 1246 results ~= a.dart_index; 1247 } 1248 return results; 1249 1250 } 1251 1252 bool validate(DARTFile dart, const(ulong[]) table, out RecordFactory 1253 .Recorder recorder) { 1254 write(dart, table, recorder); 1255 auto _dart_indices = dart_indices(recorder); 1256 auto find_recorder = dart.loads(_dart_indices); 1257 return check(recorder, find_recorder); 1258 } 1259 1260 RecordFactory.Recorder records(RecordFactory factory, const(ulong[]) table) { 1261 auto rec = factory.recorder; 1262 foreach (t; table) { 1263 const doc = DARTFakeNet.fake_doc(t); 1264 rec.add(doc); 1265 } 1266 return rec; 1267 } 1268 1269 RecordFactory.Recorder recordsRemove(RecordFactory factory, const(ulong[]) table) { 1270 auto rec = factory.recorder; 1271 foreach (t; table) { 1272 const doc = DARTFakeNet.fake_doc(t); 1273 rec.remove(doc); 1274 } 1275 return rec; 1276 } 1277 1278 } 1279 1280 } 1281 1282 } 1283 1284 version (unittest) { 1285 import tagion.dart.DARTFakeNet; 1286 import tagion.dart.RimKeyRange; 1287 import std.internal.math.biguintx86; 1288 } 1289 /// 1290 unittest { 1291 import std.algorithm.sorting : sort; 1292 1293 import std.stdio : writefln; // import tagion.basic.basic; 1294 import std.bitmanip : BitArray; 1295 import std.typecons; 1296 import tagion.basic.basic : forceRemove; 1297 import tagion.hibon.HiBONJSON : toPretty; 1298 import tagion.utils.Miscellaneous : cutHex; 1299 import tagion.utils.Random; 1300 1301 auto net = new DARTFakeNet; 1302 auto manufactor = RecordFactory(net); 1303 1304 immutable(ulong[]) table = [ 1305 // RIM 2 test (rim=2) 1306 0x20_21_10_30_40_50_80_90, 1307 0x20_21_11_30_40_50_80_90, 1308 0x20_21_12_30_40_50_80_90, 1309 0x20_21_0a_30_40_50_80_90, // Insert before in rim 2 1310 1311 // Rim 3 test (rim=3) 1312 0x20_21_20_30_40_50_80_90, 1313 0x20_21_20_31_40_50_80_90, 1314 0x20_21_20_34_40_50_80_90, 1315 0x20_21_20_20_40_50_80_90, // Insert before the first in rim 3 1316 1317 0x20_21_20_32_40_50_80_90, // Insert just the last archive in the bucket in rim 3 1318 1319 // Rim 3 test (rim=3) 1320 0x20_21_22_30_40_50_80_90, 1321 0x20_21_22_31_40_50_80_90, 1322 0x20_21_22_34_40_50_80_90, 1323 0x20_21_22_20_40_50_80_90, // Insert before the first in rim 3 1324 0x20_21_22_36_40_50_80_90, // Insert after the first in rim 3 1325 1326 0x20_21_22_32_40_50_80_90, // Insert between in rim 3 1327 1328 // Add in first rim again 1329 0x20_21_11_33_40_50_80_90, 1330 0x20_21_20_32_30_40_50_80, 1331 1332 0x20_21_20_32_31_40_50_80, // rim 4 test 1333 0x20_21_20_32_34_40_50_80, 1334 0x20_21_20_32_20_40_50_80, // Insert before the first in rim 4 1335 1336 0x20_21_20_32_32_40_50_80, // Insert just the last archive in the bucket in rim 4 1337 1338 ]; 1339 1340 immutable filename = fileId!DARTFile.fullpath; 1341 immutable filename_A = fileId!DARTFile("A").fullpath; 1342 immutable filename_B = fileId!DARTFile("B").fullpath; 1343 1344 { // Test the fake hash on Archive 1345 auto doc_in = DARTFakeNet.fake_doc(table[0]); 1346 auto a_in = new Archive(net, doc_in, Archive.Type.ADD); 1347 1348 // Test recorder 1349 auto recorder = manufactor.recorder; 1350 recorder.insert(a_in); 1351 auto recorder_doc_out = recorder.toDoc; 1352 auto recorder_out = manufactor.recorder(recorder_doc_out); 1353 auto recorder_archive = recorder_out.archives[].front; 1354 assert(recorder_archive.dart_index == a_in.dart_index); 1355 1356 } 1357 1358 { // Test RimKeyRange 1359 auto recorder = manufactor.recorder; 1360 1361 auto test_tabel = table[0 .. 8].dup; 1362 foreach (t; test_tabel) { 1363 const doc = DARTFakeNet.fake_doc(t); 1364 recorder.add(doc); 1365 } 1366 1367 test_tabel.sort; 1368 1369 uint i; 1370 foreach (a; recorder.archives) { 1371 assert(a.filed.data == net.fake_doc(test_tabel[i]).data); 1372 i++; 1373 } 1374 1375 immutable rim = 3; 1376 { 1377 auto root_range = rimKeyRange(recorder); 1378 auto rim_range = root_range.selectRim(3); 1379 1380 i = 0; 1381 immutable key = rim_range.front.dart_index.rim_key(rim); 1382 foreach (a; rim_range) { 1383 while (net.dartIndex(DARTFakeNet.fake_doc(test_tabel[i])).rim_key(rim) !is key) { 1384 i++; 1385 } 1386 i++; 1387 } 1388 } 1389 } 1390 1391 { // Rim 2 test 1392 filename.forceRemove; 1393 DARTFile.create(filename, net); 1394 auto dart = new DARTFile(net, filename); 1395 RecordFactory.Recorder recorder; 1396 assert(DARTFile.validate(dart, table[0 .. 4], recorder)); 1397 } 1398 1399 { // Rim 3 test 1400 filename.forceRemove; 1401 1402 DARTFile.create(filename, net); 1403 auto dart = new DARTFile(net, filename); 1404 RecordFactory.Recorder recorder; 1405 //=Recorder(net); 1406 assert(DARTFile.validate(dart, table[4 .. 9], recorder)); 1407 // dart.dump; 1408 } 1409 1410 { // Rim 4 test 1411 filename.forceRemove; 1412 DARTFile.create(filename, net); 1413 auto dart = new DARTFile(net, filename); 1414 RecordFactory.Recorder recorder; 1415 1416 assert(DARTFile.validate(dart, table[17 .. $], recorder)); 1417 // dart.dump; 1418 } 1419 1420 { // Rim 2 & 3 1421 filename.forceRemove; 1422 DARTFile.create(filename, net); 1423 auto dart = new DARTFile(net, filename); 1424 RecordFactory.Recorder recorder; 1425 1426 assert(DARTFile.validate(dart, table[0 .. 9], recorder)); 1427 // dart.dump; 1428 } 1429 1430 { // Rim 2 & 3 & 4 1431 filename.forceRemove; 1432 DARTFile.create(filename, net); 1433 auto dart = new DARTFile(net, filename); 1434 RecordFactory.Recorder recorder; 1435 1436 assert(DARTFile.validate(dart, table[0 .. 9] ~ table[17 .. $], recorder)); 1437 // dart.dump; 1438 } 1439 1440 { // Rim all 1441 filename.forceRemove; 1442 DARTFile.create(filename, net); 1443 auto dart = new DARTFile(net, filename); 1444 RecordFactory.Recorder recorder; 1445 1446 assert(DARTFile.validate(dart, table, recorder)); 1447 // dart.dump; 1448 } 1449 1450 { // Remove two archives and check the bulleye 1451 immutable file_A = fileId!DARTFile("XA").fullpath; 1452 immutable file_B = fileId!DARTFile("XB").fullpath; 1453 1454 DARTFile.create(file_A, net); 1455 DARTFile.create(file_B, net); 1456 1457 RecordFactory.Recorder recorder_A; 1458 RecordFactory.Recorder recorder_B; 1459 auto dart_A = new DARTFile(net, file_A); 1460 auto dart_B = new DARTFile(net, file_B); 1461 // 1462 DARTFile.write(dart_A, table, recorder_A); 1463 // table 8 and 9 is left out 1464 auto bulleye_B = DARTFile.write(dart_B, table[0 .. 8] ~ table[10 .. $], recorder_B); 1465 1466 //dart_A.dump; 1467 //dart_B.dump; 1468 auto remove_recorder = DARTFile.recordsRemove(manufactor, table[8 .. 10]); 1469 1470 auto bulleye_A = dart_A.modify(remove_recorder); 1471 //dart_A.dump; 1472 assert(bulleye_A == bulleye_B); 1473 } 1474 1475 { // Random remove and the bulleye is check 1476 auto rand = Random!ulong(1234_5678_9012_345UL); 1477 enum N = 1000; 1478 auto random_table = new ulong[N]; 1479 foreach (ref r; random_table) { 1480 r = rand.value(0xABBA_1234_5678_0000UL, 0xABBA_1234_FFFF_0000UL); 1481 } 1482 DARTFile.create(filename_A, net); 1483 DARTFile.create(filename_B, net); 1484 RecordFactory.Recorder recorder_A; 1485 RecordFactory.Recorder recorder_B; 1486 auto dart_A = new DARTFile(net, filename_A); 1487 auto dart_B = new DARTFile(net, filename_B); 1488 // 1489 1490 auto bulleye_A = DARTFile.write(dart_A, random_table, recorder_A); 1491 auto bulleye_B = DARTFile.write(dart_B, random_table[0 .. N - 100], recorder_B); 1492 auto remove_recorder = DARTFile.recordsRemove(manufactor, random_table[N - 100 .. N]); 1493 1494 bulleye_A = dart_A.modify(remove_recorder); 1495 // dart_A.dump; 1496 1497 // The bull eye of the two DART must be the same 1498 assert(bulleye_A == bulleye_B); 1499 } 1500 { // DARTFile.write on to an existing DART and the bulleye is check 1501 // This test is based on the next random test. Where an error was found. Do not delete. 1502 const from_random_table = [ 1503 0xABBA_1234_DF92_7BA7UL, // add first time 1504 0xABBA_1234_62BD_7814UL, // add first time 1505 0xABBA_1234_DFA5_2B29UL, 1506 ]; 1507 filename_A.forceRemove; 1508 filename_B.forceRemove; 1509 DARTFile.create(filename_A, net); 1510 DARTFile.create(filename_B, net); 1511 RecordFactory.Recorder recorder_A; 1512 RecordFactory.Recorder recorder_B; 1513 auto dart_A = new DARTFile(net, filename_A); 1514 auto dart_B = new DARTFile(net, filename_B); 1515 // 1516 1517 DARTFile.write(dart_A, from_random_table[0 .. 2], recorder_A); 1518 // writeln("0->2"); 1519 // dart_A.dump; 1520 auto bulleye_A = DARTFile.write(dart_A, from_random_table[2 .. 3], recorder_A); 1521 // writeln("4->5"); 1522 // dart_A.dump; 1523 //assert(0); 1524 auto bulleye_B = DARTFile.write(dart_B, from_random_table, recorder_B); 1525 // writeln("DART B: 0->2 & 4->5"); 1526 // dart_B.dump; 1527 1528 // The bull eye of the two DART must be the same 1529 assert(bulleye_A == bulleye_B); 1530 } 1531 1532 { // Random DARTFile.write on to an existing DART and the bulleye is check 1533 auto rand = Random!ulong(1234_5678_9012_345UL); 1534 enum N = 100; 1535 auto random_table = new ulong[N]; 1536 foreach (ref r; random_table) { 1537 r = rand.value(0xABBA_1234_5678_0000UL, 0xABBA_1234_FFFF_0000UL); 1538 } 1539 filename_A.forceRemove; 1540 filename_B.forceRemove; 1541 DARTFile.create(filename_A, net); 1542 DARTFile.create(filename_B, net); 1543 RecordFactory.Recorder recorder_A; 1544 RecordFactory.Recorder recorder_B; 1545 auto dart_A = new DARTFile(net, filename_A); 1546 auto dart_B = new DARTFile(net, filename_B); 1547 // 1548 1549 DARTFile.write(dart_A, random_table[0 .. 29], recorder_A); 1550 // dart_A.dump; 1551 auto bulleye_A = DARTFile.write(dart_A, random_table[34 .. 100], recorder_A); 1552 // dart_A.dump; 1553 //assert(0); 1554 auto bulleye_B = DARTFile.write(dart_B, random_table[0 .. 29] ~ random_table[34 .. 100], recorder_B); 1555 // dart_B.dump; 1556 1557 // The bullseye of the two DART must be the same 1558 assert(bulleye_A == bulleye_B); 1559 } 1560 1561 { // Random remove and the bullseye is checked 1562 auto rand = Random!ulong(1234_5678_9012_345UL); 1563 enum N = 1000; 1564 auto random_table = new ulong[N]; 1565 foreach (ref r; random_table) { 1566 r = rand.value(0xABBA_1234_5678_0000UL, 0xABBA_1234_FFFF_0000UL); 1567 } 1568 filename_A.forceRemove; 1569 filename_B.forceRemove; 1570 DARTFile.create(filename_A, net); 1571 DARTFile.create(filename_B, net); 1572 RecordFactory.Recorder recorder_A; 1573 RecordFactory.Recorder recorder_B; 1574 auto dart_A = new DARTFile(net, filename_A); 1575 auto dart_B = new DARTFile(net, filename_B); 1576 // 1577 1578 auto bulleye_A = DARTFile.write(dart_A, random_table, recorder_A); 1579 auto bulleye_B = DARTFile.write(dart_B, random_table[0 .. N - 100], recorder_B); 1580 auto remove_recorder = DARTFile.recordsRemove(manufactor, random_table[N - 100 .. N]); 1581 bulleye_A = dart_A.modify(remove_recorder); 1582 // dart_A.dump; 1583 // The bull eye of the two DART must be the same 1584 assert(bulleye_A == bulleye_B); 1585 } 1586 1587 { // Random DARTFile.write and then bullseye is checked 1588 auto rand = Random!ulong(1234_5678_9012_345UL); 1589 enum N = 1000; 1590 auto random_table = new ulong[N]; 1591 foreach (ref r; random_table) { 1592 r = rand.value(0xABBA_1234_5678_0000UL, 0xABBA_1234_FFFF_0000UL); 1593 } 1594 filename_A.forceRemove; 1595 filename_B.forceRemove; 1596 DARTFile.create(filename_A, net); 1597 DARTFile.create(filename_B, net); 1598 RecordFactory.Recorder recorder_A; 1599 RecordFactory.Recorder recorder_B; 1600 auto dart_A = new DARTFile(net, filename_A); 1601 auto dart_B = new DARTFile(net, filename_B); 1602 1603 DARTFile.write(dart_A, random_table[0 .. 333], recorder_A); 1604 DARTFile.write(dart_B, random_table[0 .. 777], recorder_B); 1605 auto bulleye_A = DARTFile.write(dart_A, random_table[333 .. $], recorder_A); 1606 auto bulleye_B = DARTFile.write(dart_B, random_table[777 .. $], recorder_B); 1607 1608 // The bull eye of the two DART must be the same 1609 assert(bulleye_A == bulleye_B); 1610 } 1611 1612 { // Try to remove a nonexisting archive 1613 auto rand = Random!ulong(1234_5678_9012_345UL); 1614 enum N = 50; 1615 auto random_table = new ulong[N]; 1616 foreach (ref r; random_table) { 1617 r = rand.value(0xABBA_1234_5678_0000UL, 0xABBA_1234_FFFF_0000UL); 1618 } 1619 filename_A.forceRemove; 1620 filename_B.forceRemove; 1621 DARTFile.create(filename_A, net); 1622 DARTFile.create(filename_B, net); 1623 1624 auto dart_A = new DARTFile(net, filename_A); 1625 auto dart_B = new DARTFile(net, filename_B); 1626 RecordFactory.Recorder recorder_A; 1627 RecordFactory.Recorder recorder_B; 1628 1629 DARTFile.write(dart_A, random_table, recorder_A); 1630 DARTFile.write(dart_B, random_table, recorder_B); 1631 assert(dart_A.fingerprint == dart_B.fingerprint); 1632 1633 auto recorder = dart_A.recorder; 1634 const archive_1 = new Archive(net, net.fake_doc(0xABB7_1111_1111_0000UL), Archive 1635 .Type.NONE); 1636 recorder.remove(archive_1.dart_index); 1637 const archive_2 = new Archive(net, net.fake_doc(0xABB7_1112_1111_0000UL), Archive 1638 .Type.NONE); 1639 recorder.remove(archive_2.dart_index); 1640 dart_B.modify(recorder); 1641 // dart_B.dump; 1642 // dart_A.dump; 1643 assert(dart_A.fingerprint == dart_B.fingerprint); 1644 1645 // Check fingerprint on load 1646 auto read_dart_A = new DARTFile(net, filename_A); 1647 assert(dart_A.fingerprint == read_dart_A.fingerprint); 1648 } 1649 1650 { // Large random test 1651 auto rand = Random!ulong(1234_5678_9012_345UL); 1652 enum N = 1000; 1653 auto random_table = new ulong[N]; 1654 foreach (ref r; random_table) { 1655 r = rand.value(0xABBA_1234_5678_0000UL, 0xABBA_1234_FFFF_0000UL); 1656 } 1657 filename_A.forceRemove; 1658 filename_B.forceRemove; 1659 DARTFile.create(filename_A, net); 1660 DARTFile.create(filename_B, net); 1661 // Recorder recorder_B; 1662 auto dart_A = new DARTFile(net, filename_A); 1663 auto dart_B = new DARTFile(net, filename_B); 1664 1665 BitArray saved_archives; 1666 (() @trusted { saved_archives.length = N; })(); 1667 auto rand_index = Random!uint(1234); 1668 enum ITERATIONS = 7; 1669 enum SELECT_ITER = 35; 1670 (() @trusted { 1671 foreach (i; 0 .. ITERATIONS) { 1672 auto recorder = dart_A.recorder; 1673 BitArray check_archives; 1674 BitArray added_archives; 1675 BitArray removed_archives; 1676 check_archives.length = N; 1677 added_archives.length = N; 1678 removed_archives.length = N; 1679 foreach (j; 0 .. SELECT_ITER) { 1680 immutable index = rand_index.value(N); 1681 if (!check_archives[index]) { 1682 const doc = net.fake_doc(random_table[index]); 1683 if (saved_archives[index]) { 1684 recorder.remove(doc); 1685 removed_archives[index] = true; 1686 } 1687 else { 1688 recorder.add(doc); 1689 added_archives[index] = true; 1690 } 1691 check_archives[index] = true; 1692 } 1693 } 1694 // dart_A.blockfile.dump; 1695 //recorder.dump; 1696 dart_A.modify(recorder); 1697 saved_archives |= added_archives; 1698 saved_archives &= ~removed_archives; 1699 // dart_A.dump; 1700 } 1701 auto recorder_B = dart_B.recorder; 1702 1703 saved_archives.bitsSet.each!( 1704 n => recorder_B.add(net.fake_doc(random_table[n]))); 1705 dart_B.modify(recorder_B); 1706 // dart_B.dump; 1707 assert(dart_A.fingerprint == dart_B.fingerprint); 1708 })(); 1709 } 1710 1711 { 1712 // The bug we want to find 1713 // EYE: abb913ab11ef1234000000000000000000000000000000000000000000000000 1714 // | AB [17] 1715 // | .. | B9 [16] 1716 // | .. | .. | 13 [15] 1717 // | .. | .. | .. | AB [14] 1718 // | .. | .. | .. | .. abb913ab11ef1234000000000000000000000000000000000000000000000000 [7] 1719 // As it can be seen the branch has not snapped back to the first rim. The database should instead look like 1720 // this: 1721 // | AB [17] 1722 // | .. | .. abb913ab11ef1234000000000000000000000000000000000000000000000000 [7] 1723 1724 import std.algorithm : map; 1725 import std.format; 1726 import std.range : empty; 1727 1728 size_t numberOfArchives(DARTFile.Branches branches, DARTFile db) { 1729 return branches.indices 1730 .filter!(i => i !is Index.init) 1731 .map!(i => DARTFile.Branches.isRecord(db.cacheLoad(i))) 1732 .walkLength; 1733 1734 } 1735 1736 { 1737 filename_A.forceRemove; 1738 DARTFile.create(filename_A, net); 1739 auto dart_A = new DARTFile(net, filename_A); 1740 1741 const ulong[] deep_table = [ 1742 0xABB9_13ab_11ef_0923, 1743 0xABB9_13ab_11ef_1234, 1744 ]; 1745 1746 auto docs = deep_table.map!(a => DARTFakeNet.fake_doc(a)); 1747 auto recorder = dart_A.recorder(); 1748 foreach (doc; docs) { 1749 recorder.add(doc); 1750 } 1751 auto remove_dart_index = DARTIndex(recorder[].front.dart_index); 1752 // writefln("%s", remove_dart_index); 1753 1754 dart_A.modify(recorder); 1755 // dart_A.dump(); 1756 1757 auto remove_recorder = dart_A.recorder(); 1758 remove_recorder.remove(remove_dart_index); 1759 dart_A.modify(remove_recorder); 1760 // dart_A.dump(); 1761 1762 auto branches = dart_A.branches([0xAB, 0xB9]); 1763 1764 assert(numberOfArchives(branches, dart_A) == 1, "Branch not snapped back to rim 2"); 1765 1766 } 1767 1768 { 1769 filename_A.forceRemove; 1770 DARTFile.create(filename_A, net); 1771 auto dart_A = new DARTFile(net, filename_A); 1772 const ulong[] deep_table = [ 1773 0xABB9_13ab_11ef_0923, 1774 0xABB9_13ab_11ef_1234, 1775 ]; 1776 1777 auto docs = deep_table.map!(a => DARTFakeNet.fake_doc(a)); 1778 auto recorder = dart_A.recorder(); 1779 foreach (doc; docs) { 1780 recorder.add(doc); 1781 } 1782 dart_A.modify(recorder); 1783 // dart_A.dump(); 1784 auto dart_indices = recorder[].map!(a => cast(immutable) DARTIndex(a.dart_index)).array; 1785 1786 auto empty_load = dart_A.checkload(dart_indices); 1787 assert(empty_load.length == 0); 1788 // test.map!(f => f.toPretty).writeln; 1789 const ulong[] not_in_dart = [ 1790 0xABB9_13ab_11ef_0929, 1791 0xABB9_13ab_11ef_1239, 1792 1793 ]; 1794 auto not_in_dart_fingerprints = not_in_dart 1795 .map!(a => DARTFakeNet.fake_doc(a)) 1796 .map!(a => net.dartIndex(a)); 1797 1798 auto full_load = dart_A.checkload(not_in_dart_fingerprints); 1799 assert(not_in_dart_fingerprints.length == full_load.length); 1800 1801 const ulong[] half_in_dart = [ 1802 0xABB9_13ab_11ef_0923, 1803 0xABB9_13ab_11ef_1239, 1804 ]; 1805 auto half_in_dart_fingerprints = half_in_dart 1806 .map!(a => DARTFakeNet.fake_doc(a)) 1807 .map!(a => net.dartIndex(a)) 1808 .array; 1809 1810 auto half_load = dart_A.checkload(half_in_dart_fingerprints); 1811 assert(half_load.length == 1); 1812 1813 assert(half_load[0] == half_in_dart_fingerprints[1]); 1814 1815 } 1816 1817 { 1818 // this test is just a support to see how the real result should be of the previous test. 1819 filename_A.forceRemove; 1820 DARTFile.create(filename_A, net); 1821 auto dart_A = new DARTFile(net, filename_A); 1822 1823 const ulong archive = 0xABB9_13ab_11ef_0234; 1824 1825 auto doc = DARTFakeNet.fake_doc(archive); 1826 auto recorder = dart_A.recorder(); 1827 1828 recorder.add(doc); 1829 1830 auto fingerprint = recorder[].front.fingerprint; 1831 dart_A.modify(recorder); 1832 1833 // dart_A.dump(); 1834 assert(dart_A.bullseye == fingerprint); 1835 1836 auto branches = dart_A.branches([0xAB, 0xB9]); 1837 1838 assert(numberOfArchives(branches, dart_A) == 1, "Branch not snapped back to rim 2"); 1839 } 1840 { 1841 // middle branch test. 1842 // we start by creating the following archive structure. 1843 // EYE: 88aed312de6a292c4f3c80267b9272b32e39af749ceef8723e66c91c1872e056 1844 // | AB [9] 1845 // | .. | B9 [8] 1846 // | .. | .. | 13 [7] 1847 // | .. | .. | .. | AB [6] 1848 // | .. | .. | .. | .. | 11 [4] 1849 // | .. | .. | .. | .. | .. | EF [3] 1850 // | .. | .. | .. | .. | .. | .. abb913ab11ef0923 [1] 1851 // | .. | .. | .. | .. | .. | .. abb913ab11ef1234 [2] 1852 // | .. | .. | .. | .. abb913ab1213 [5] 1853 1854 // now we remove one of the archives located in EF [3]. Then we should get the following. 1855 // EYE: 9428892e35b550187e8ff0a0d612bbd94029dbf6d7780cf29b66a8d5f8d10f58 1856 // | AB [15] 1857 // | .. | B9 [14] 1858 // | .. | .. | 13 [13] 1859 // | .. | .. | .. | AB [12] 1860 // | .. | .. | .. | .. abb913ab11ef [2] 1861 // | .. | .. | .. | .. abb913ab1213 [5] 1862 filename_A.forceRemove; 1863 1864 DARTFile.create(filename_A, net); 1865 auto dart_A = new DARTFile(net, filename_A); 1866 1867 const ulong[] deep_table = [ 1868 0xABB9_13ab_11ef_0923, 1869 0xABB9_13ab_11ef_1234, 1870 0xABB9_13ab_1213_5678, 1871 ]; 1872 1873 auto docs = deep_table.map!(a => DARTFakeNet.fake_doc(a)); 1874 auto recorder = dart_A.recorder(); 1875 foreach (doc; docs) { 1876 recorder.add(doc); 1877 } 1878 auto remove_dart_index = recorder[].front.dart_index; 1879 dart_A.modify(recorder); 1880 // dart_A.dump(); 1881 1882 auto remove_recorder = dart_A.recorder(); 1883 remove_recorder.remove(remove_dart_index); 1884 dart_A.modify(remove_recorder); 1885 1886 ubyte[] rim_path = [0xAB, 0xB9, 0x13, 0xab]; 1887 auto branches = dart_A.branches(rim_path); 1888 1889 assert(numberOfArchives(branches, dart_A) == 2, "Branch not snapped back"); 1890 1891 // dart_A.dump(); 1892 } 1893 1894 { 1895 // ADD ADD REMOVE 1896 // we start by creating the following archive structure. 1897 // | AB [9] 1898 // | .. | B9 [8] 1899 // | .. | .. | 13 [7] 1900 // | .. | .. | .. | AB [6] 1901 // | .. | .. | .. | .. | 11 [4] 1902 // | .. | .. | .. | .. | .. | EF [3] 1903 // | .. | .. | .. | .. | .. | .. abb913ab11ef0923 [1] 1904 // | .. | .. | .. | .. | .. | .. abb913ab11ef1234 [2] 1905 1906 // now we remove one of the archives located in EF [3]. And add another archive afterwards in the same recorder. 1907 // EYE: f32ee782a2576cdb57cc36c9e64409f36aa7747dd6c4ff1df8166b268b6ee0b1 1908 // | AB [17] 1909 // | .. | B9 [16] 1910 // | .. | .. | 13 [15] 1911 // | .. | .. | .. | AB [14] 1912 // | .. | .. | .. | .. | 11 [13] 1913 // | .. | .. | .. | .. | .. | EF [12] 1914 // | .. | .. | .. | .. | .. | .. abb913ab11ef1234 [2] 1915 // | .. | .. | .. | .. | .. | .. abb913ab11ef2078 [11] 1916 filename_A.forceRemove; 1917 1918 DARTFile.create(filename_A, net); 1919 // writefln("dartfilename=%s", filename_A); 1920 auto dart_A = new DARTFile(net, filename_A); 1921 1922 const ulong[] deep_table = [ 1923 0xABB9_13ab_11ef_0923, 1924 0xABB9_13ab_11ef_1234, 1925 0xABB9_13ab_11ef_2078, 1926 ]; 1927 1928 auto docs = deep_table.map!(a => DARTFakeNet.fake_doc(a)).array; 1929 auto recorder = dart_A.recorder(); 1930 1931 assert(docs.length == 3); 1932 recorder.add(docs[0]); 1933 recorder.add(docs[1]); 1934 auto remove_dart_index = recorder[].front.dart_index; 1935 1936 dart_A.modify(recorder); 1937 // dart_A.dump(); 1938 1939 auto next_recorder = dart_A.recorder(); 1940 next_recorder.remove(remove_dart_index); 1941 next_recorder.add(docs[2]); 1942 // next_recorder[].each!q{a.dump}; 1943 dart_A.modify(next_recorder); 1944 // dart_A.dump(); 1945 1946 ubyte[] rim_path = [0xAB, 0xB9, 0x13, 0xab, 0x11, 0xef]; 1947 auto branches = dart_A.branches(rim_path); 1948 1949 assert(numberOfArchives(branches, dart_A) == 2, "Should contain two archives"); 1950 1951 } 1952 1953 { 1954 // Double snap back. Add 2 x 2 archives and remove one in each so both branches should snap back. 1955 // EYE: 13c0d1bdc484c65f84968f8bcd1eb873520cfda16c070fdac4f5eb54f1fa54d9 1956 // | AB [11] 1957 // | .. | B9 [10] 1958 // | .. | .. | 13 [9] 1959 // | .. | .. | .. | AB [8] 1960 // | .. | .. | .. | .. | 11 [4] 1961 // | .. | .. | .. | .. | .. | EF [3] 1962 // | .. | .. | .. | .. | .. | .. abb913ab11ef0923 [1] 1963 // | .. | .. | .. | .. | .. | .. abb913ab11ef1234 [2] 1964 // | .. | .. | .. | .. | 12 [7] 1965 // | .. | .. | .. | .. | .. abb913ab121356 [5] 1966 // | .. | .. | .. | .. | .. abb913ab121412 [6] 1967 // Then the db should look like this: 1968 // EYE: a8db386daf51e78165021eae66ef072815d52bfcdd776e59f065a742e680ffb0 1969 // | AB [17] 1970 // | .. | B9 [16] 1971 // | .. | .. | 13 [15] 1972 // | .. | .. | .. | AB [14] 1973 // | .. | .. | .. | .. abb913ab11ef [2] 1974 // | .. | .. | .. | .. abb913ab1214 [6] 1975 filename_A.forceRemove; 1976 1977 DARTFile.create(filename_A, net); 1978 auto dart_A = new DARTFile(net, filename_A); 1979 1980 const ulong[] deep_table = [ 1981 0xABB9_13ab_11ef_0923, 1982 0xABB9_13ab_11ef_1234, 1983 0xABB9_13ab_1213_5678, 1984 0xABB9_13ab_1214_1234, 1985 ]; 1986 1987 auto docs = deep_table.map!(a => DARTFakeNet.fake_doc(a)); 1988 auto recorder = dart_A.recorder(); 1989 foreach (doc; docs) { 1990 recorder.add(doc); 1991 } 1992 1993 auto dart_indices = recorder[].map!(r => r.dart_index).array; 1994 assert(dart_indices.length == 4); 1995 dart_A.modify(recorder); 1996 // dart_A.dump(); 1997 1998 auto remove_recorder = dart_A.recorder(); 1999 remove_recorder.remove(dart_indices[0]); 2000 remove_recorder.remove(dart_indices[2]); 2001 dart_A.modify(remove_recorder); 2002 // dart_A.dump(); 2003 2004 ubyte[] rim_path = [0xAB, 0xB9, 0x13, 0xab]; 2005 auto branches = dart_A.branches(rim_path); 2006 2007 assert(numberOfArchives(branches, dart_A) == 2, "Should contain two archives"); 2008 } 2009 2010 { 2011 // we start with the following structure. 2012 // EYE: 96443dfcd4959c2698f1553976e18d7a7ab99b9c914967d9e0e6cd7bb3db5852 2013 // | AB [13] 2014 // | .. | B9 [12] 2015 // | .. | .. | 13 [11] 2016 // | .. | .. | .. abb9130b11 [1] 2017 // | .. | .. | .. | AB [10] 2018 // | .. | .. | .. | .. abb913ab11ef [2] 2019 // | .. | .. | .. | .. | 12 [9] 2020 // | .. | .. | .. | .. | .. abb913ab12de56 [3] 2021 // | .. | .. | .. | .. | .. | EF [8] 2022 // | .. | .. | .. | .. | .. | .. abb913ab12ef1354 [4] 2023 // | .. | .. | .. | .. | .. | .. | 56 [7] 2024 // | .. | .. | .. | .. | .. | .. | .. abb913ab12ef565600 [5] 2025 // | .. | .. | .. | .. | .. | .. | .. abb913ab12ef567800 [6] 2026 // EYE: a3f372ca07524db275e0bd8445af237c7827e97c7cb9d50d585b6798f0da3be0 2027 // then we remove the last one. we should get this. 2028 // | AB [21] 2029 // | .. | B9 [20] 2030 // | .. | .. | 13 [19] 2031 // | .. | .. | .. abb9130b11 [1] 2032 // | .. | .. | .. | AB [18] 2033 // | .. | .. | .. | .. abb913ab11ef [2] 2034 // | .. | .. | .. | .. | 12 [17] 2035 // | .. | .. | .. | .. | .. abb913ab12de56 [3] 2036 // | .. | .. | .. | .. | .. | EF [16] 2037 // | .. | .. | .. | .. | .. | .. abb913ab12ef1354 [4] 2038 // | .. | .. | .. | .. | .. | .. abb913ab12ef5656 [5] 2039 filename_A.forceRemove; 2040 2041 DARTFile.create(filename_A, net); 2042 auto dart_A = new DARTFile(net, filename_A); 2043 2044 const ulong[] deep_table = [ 2045 0xABB9_13ab_11ef_0923, 2046 0xABB9_130b_11ef_1234, 2047 0xABB9_13ab_12ef_5678, 2048 0xABB9_13ab_12ef_1354, 2049 0xABB9_13ab_12ef_5656, 2050 0xABB9_13ab_12de_5678, 2051 ]; 2052 2053 auto docs = deep_table.map!(a => DARTFakeNet.fake_doc(a)); 2054 auto recorder = dart_A.recorder(); 2055 foreach (doc; docs) { 2056 recorder.add(doc); 2057 } 2058 auto dart_indices = recorder[].map!(r => r.dart_index).array; 2059 dart_A.modify(recorder); 2060 // dart_A.dump(); 2061 2062 auto remove_recorder = dart_A.recorder(); 2063 remove_recorder.remove(dart_indices[$ - 1]); 2064 2065 dart_A.modify(remove_recorder); 2066 // dart_A.dump(); 2067 2068 ubyte[] rim_path = [0xAB, 0xB9, 0x13, 0xab, 0x12, 0xef]; 2069 2070 auto branches = dart_A.branches(rim_path); 2071 assert(numberOfArchives(branches, dart_A) == 2, "Should contain two archives after remove"); 2072 2073 } 2074 2075 { 2076 // we start with the following structure. 2077 // EYE: 96443dfcd4959c2698f1553976e18d7a7ab99b9c914967d9e0e6cd7bb3db5852 2078 // | AB [13] 2079 // | .. | B9 [12] 2080 // | .. | .. | 13 [11] 2081 // | .. | .. | .. abb9130b11 [1] 2082 // | .. | .. | .. | AB [10] 2083 // | .. | .. | .. | .. abb913ab11ef [2] 2084 // | .. | .. | .. | .. | 12 [9] 2085 // | .. | .. | .. | .. | .. abb913ab12de56 [3] 2086 // | .. | .. | .. | .. | .. | EF [8] 2087 // | .. | .. | .. | .. | .. | .. abb913ab12ef1354 [4] 2088 // | .. | .. | .. | .. | .. | .. | 56 [7] 2089 // | .. | .. | .. | .. | .. | .. | .. abb913ab12ef565600 [5] 2090 // | .. | .. | .. | .. | .. | .. | .. abb913ab12ef567800 [6] 2091 // now we remove the middle branch located at EF. 2092 filename_A.forceRemove; 2093 2094 DARTFile.create(filename_A, net); 2095 auto dart_A = new DARTFile(net, filename_A); 2096 2097 const ulong[] deep_table = [ 2098 0xABB9_13ab_11ef_0923, 2099 0xABB9_130b_11ef_1234, 2100 0xABB9_13ab_12ef_5678, 2101 0xABB9_13ab_12ef_1354, 2102 0xABB9_13ab_12ef_5656, 2103 0xABB9_13ab_12de_5678, 2104 ]; 2105 2106 auto docs = deep_table.map!(a => DARTFakeNet.fake_doc(a)); 2107 auto recorder = dart_A.recorder(); 2108 foreach (doc; docs) { 2109 recorder.add(doc); 2110 } 2111 auto dart_indices = recorder[].map!(r => r.dart_index).array; 2112 dart_A.modify(recorder); 2113 // dart_A.dump(); 2114 2115 auto remove_recorder = dart_A.recorder(); 2116 remove_recorder.remove(dart_indices[4]); 2117 2118 dart_A.modify(remove_recorder); 2119 // dart_A.dump(); 2120 2121 ubyte[] rim_path = [0xAB, 0xB9, 0x13, 0xab, 0x12, 0xef]; 2122 2123 auto branches = dart_A.branches(rim_path); 2124 // writefln("XXX %s", numberOfArchives(branches, dart_A)); 2125 assert(numberOfArchives(branches, dart_A) == 2, "Should contain two archives after remove"); 2126 2127 } 2128 2129 { 2130 filename_A.forceRemove; 2131 2132 DARTFile.create(filename_A, net); 2133 auto dart_A = new DARTFile(net, filename_A); 2134 2135 const ulong[] deep_table = [ 2136 0xABB9_13ab_11ef_0923, 2137 0xABB9_130b_11ef_1234, 2138 0xABB9_13ab_12ef_5678, 2139 0xABB9_13ab_12ef_1354, 2140 0xABB9_13ab_12ef_5656, 2141 0xABB9_13ab_12de_5678, 2142 ]; 2143 2144 auto docs = deep_table.map!(a => DARTFakeNet.fake_doc(a)); 2145 auto recorder = dart_A.recorder(); 2146 foreach (doc; docs) { 2147 recorder.add(doc); 2148 } 2149 auto dart_indices = recorder[].map!(r => r.dart_index).array; 2150 dart_A.modify(recorder); 2151 // dart_A.dump(); 2152 2153 auto remove_recorder = dart_A.recorder(); 2154 remove_recorder.remove(dart_indices[4]); 2155 remove_recorder.remove(dart_indices[3]); 2156 2157 dart_A.modify(remove_recorder); 2158 // dart_A.dump(); 2159 2160 ubyte[] rim_path = [0xAB, 0xB9, 0x13, 0xab, 0x12]; 2161 2162 auto branches = dart_A.branches(rim_path); 2163 // writefln("XXX %s", numberOfArchives(branches, dart_A)); 2164 assert(numberOfArchives(branches, dart_A) == 2, "Should contain two archives after remove"); 2165 2166 } 2167 2168 { 2169 filename_A.forceRemove; 2170 2171 DARTFile.create(filename_A, net); 2172 auto dart_A = new DARTFile(net, filename_A); 2173 2174 const ulong[] deep_table = [ 2175 0xABB9_13ab_11ef_0923, 2176 0xABB9_130b_3456_1234, 2177 0xABB9_13ab_11ef_1234, 2178 ]; 2179 2180 auto docs = deep_table.map!(a => DARTFakeNet.fake_doc(a)); 2181 auto recorder = dart_A.recorder(); 2182 foreach (doc; docs) { 2183 recorder.add(doc); 2184 } 2185 auto dart_indices = recorder[].map!(r => r.dart_index).array; 2186 dart_A.modify(recorder); 2187 // dart_A.dump(); 2188 2189 auto remove_recorder = dart_A.recorder(); 2190 remove_recorder.remove(dart_indices[1]); 2191 remove_recorder.remove(dart_indices[2]); 2192 2193 dart_A.modify(remove_recorder); 2194 // dart_A.dump(); 2195 2196 ubyte[] rim_path = [0xAB, 0xB9]; 2197 2198 auto branches = dart_A.branches(rim_path); 2199 // // writefln("XXX %s", numberOfArchives(branches, dart_A)); 2200 assert(numberOfArchives(branches, dart_A) == 1, "Should contain one archives after remove"); 2201 2202 } 2203 { 2204 filename_A.forceRemove; 2205 2206 DARTFile.create(filename_A, net); 2207 auto dart_A = new DARTFile(net, filename_A); 2208 2209 const ulong[] deep_table = [ 2210 0xABB9_130b_11ef_0923, 2211 0xABB9_13ab_3456_1234, 2212 0xABB9_130b_11ef_1234, 2213 ]; 2214 2215 auto docs = deep_table.map!(a => DARTFakeNet.fake_doc(a)); 2216 auto recorder = dart_A.recorder(); 2217 foreach (doc; docs) { 2218 recorder.add(doc); 2219 } 2220 auto dart_indices = recorder[].map!(r => r.dart_index).array; 2221 dart_A.modify(recorder); 2222 // dart_A.dump(); 2223 2224 auto remove_recorder = dart_A.recorder(); 2225 remove_recorder.remove(dart_indices[0]); 2226 remove_recorder.remove(dart_indices[1]); 2227 2228 dart_A.modify(remove_recorder); 2229 // dart_A.dump(); 2230 2231 ubyte[] rim_path = [0xAB, 0xB9]; 2232 2233 auto branches = dart_A.branches(rim_path); 2234 // // writefln("XXX %s", numberOfArchives(branches, dart_A)); 2235 assert(numberOfArchives(branches, dart_A) == 1, "Should contain one archives after remove"); 2236 2237 } 2238 2239 { 2240 // add two of the same archives and remove it. The bullseye should be null. 2241 filename_A.forceRemove; 2242 2243 // writefln("two same archives"); 2244 DARTFile.create(filename_A, net); 2245 auto dart_A = new DARTFile(net, filename_A); 2246 2247 const ulong[] deep_table = [ 2248 0xABB9_130b_11ef_0923, 2249 0xABB9_130b_11ef_0923, 2250 ]; 2251 2252 auto docs = deep_table.map!(a => DARTFakeNet.fake_doc(a)); 2253 auto recorder = dart_A.recorder(); 2254 foreach (doc; docs) { 2255 recorder.add(doc); 2256 } 2257 auto remove_dart_index = DARTIndex(recorder[].front.dart_index); 2258 // writefln("%s", remove_dart_index); 2259 2260 dart_A.modify(recorder); 2261 // dart_A.dump(); 2262 2263 auto dart_blockfile = BlockFile(filename_A); 2264 // dart_blockfile.dump; 2265 dart_blockfile.close; 2266 2267 auto remove_recorder = dart_A.recorder(); 2268 remove_recorder.remove(remove_dart_index); 2269 dart_A.modify(remove_recorder); 2270 // writefln("after remove"); 2271 // dart_A.dump(); 2272 2273 dart_blockfile = BlockFile(filename_A); 2274 // dart_blockfile.dump; 2275 dart_blockfile.close; 2276 2277 assert(dart_A.bullseye == null); 2278 2279 } 2280 2281 { // add the same archive in different modifies. Should only contain one archive afterwards. 2282 // Test was created due to error were if the same archive was added it would remove the 2283 // archive in the database. 2284 filename_A.forceRemove; 2285 2286 DARTFile.create(filename_A, net); 2287 auto dart_A = new DARTFile(net, filename_A); 2288 2289 auto doc = DARTFakeNet.fake_doc(0xABB9_130b_11ef_0923); 2290 auto recorder = dart_A.recorder(); 2291 recorder.add(doc); 2292 dart_A.modify(recorder); 2293 assert(dart_A.bullseye == recorder[].front.fingerprint); 2294 dart_A.modify(recorder); 2295 2296 assert(dart_A.bullseye == recorder[].front.fingerprint); 2297 } 2298 2299 { 2300 filename_A.forceRemove; 2301 2302 DARTFile.create(filename_A, net); 2303 auto dart_A = new DARTFile(net, filename_A); 2304 2305 const ulong[] deep_table = [ 2306 0xABB9_130b_11ef_0923, 2307 0xAB10_130b_11ef_0923, 2308 ]; 2309 2310 auto docs = deep_table.map!(a => DARTFakeNet.fake_doc(a)); 2311 auto recorder = dart_A.recorder(); 2312 foreach (doc; docs) { 2313 recorder.add(doc); 2314 } 2315 auto remove_dart_index = DARTIndex(recorder[].front.dart_index); 2316 2317 dart_A.modify(recorder); 2318 // dart_A.dump(); 2319 2320 auto dart_blockfile = BlockFile(filename_A); 2321 // dart_blockfile.dump; 2322 dart_blockfile.close; 2323 2324 auto remove_recorder = dart_A.recorder(); 2325 remove_recorder.remove(remove_dart_index); 2326 dart_A.modify(remove_recorder); 2327 // writefln("after remove"); 2328 // dart_A.dump(); 2329 2330 dart_blockfile = BlockFile(filename_A); 2331 // dart_blockfile.dump; 2332 dart_blockfile.close; 2333 2334 ubyte[] rim_path = [0xAB]; 2335 2336 auto branches = dart_A.branches(rim_path); 2337 assert(numberOfArchives(branches, dart_A) == 1, "Should contain one archives after remove"); 2338 2339 } 2340 { 2341 filename_A.forceRemove; 2342 2343 DARTFile.create(filename_A, net); 2344 auto dart_A = new DARTFile(net, filename_A); 2345 dart_A.close; 2346 auto blockfile = BlockFile(filename_A); 2347 // blockfile.dump; 2348 blockfile.close; 2349 2350 dart_A = new DARTFile(net, filename_A); 2351 assert(dart_A.bullseye == null); 2352 2353 } 2354 { // name record unittests 2355 @recordType("name") 2356 static struct NameRecord { 2357 @label("#name") string name; 2358 string data; 2359 2360 mixin HiBONRecord!(q{ 2361 this(const string name, const string data) { 2362 this.name = name; 2363 this.data = data; 2364 } 2365 }); 2366 } 2367 2368 { 2369 filename_A.forceRemove; 2370 2371 DARTFile.create(filename_A, net); 2372 auto dart_A = new DARTFile(net, filename_A); 2373 2374 auto recorder = dart_A.recorder(); 2375 2376 auto name_record = NameRecord("jens", "10"); 2377 2378 recorder.add(name_record); 2379 2380 dart_A.modify(recorder); 2381 2382 auto dart_index = recorder[].front.dart_index; 2383 2384 auto read_recorder = dart_A.loads([dart_index]); 2385 2386 auto read_name_record = NameRecord(read_recorder[].front.filed); 2387 // writefln(read_name_record.toPretty); 2388 // dart_A.dump; 2389 // auto blockfile = BlockFile(filename_A); 2390 // blockfile.dump; 2391 // blockfile.close; 2392 assert(read_name_record == name_record, "should be the same after reading"); 2393 2394 // we try to insert a namerecord with the same name. 2395 // This should overwrite the namerecord in the database. 2396 // We insert a long string in order to see if we are not using the same 2397 // index afterwards. 2398 2399 auto new_recorder = dart_A.recorder(); 2400 2401 auto new_name = NameRecord("jens", 'x'.repeat(200).array); 2402 new_recorder.add(new_name); 2403 dart_A.modify(new_recorder); 2404 auto new_dart_index = new_recorder[].front.dart_index; 2405 2406 auto new_read_recorder = dart_A.loads([new_dart_index]); 2407 auto new_read_name = NameRecord(new_read_recorder[].front.filed); 2408 // writefln(new_read_name.toPretty); 2409 // dart_A.dump; 2410 // auto new_blockfile = BlockFile(filename_A); 2411 // new_blockfile.dump; 2412 // new_blockfile.close; 2413 assert(new_read_name == new_name, 2414 "Should not be updated, since the previous name record was not removed"); 2415 2416 } 2417 { 2418 // Namerecord. add the name to the DART 2419 // Then perform a manual REMOVE ADD with a different add data in the same recorder 2420 // should throw an exception since we cannot have multiple adds 2421 // and removes in same recorder 2422 import std.exception : assertThrown; 2423 2424 filename_B.forceRemove; 2425 2426 DARTFile.create(filename_B, net); 2427 auto dart_A = new DARTFile(net, filename_B); 2428 2429 auto recorder = dart_A.recorder(); 2430 2431 auto name_record = NameRecord("hugo", "10"); 2432 2433 recorder.add(name_record); 2434 2435 dart_A.modify(recorder); 2436 auto dart_index = recorder[].front.dart_index; 2437 auto read_recorder = dart_A.loads([dart_index]); 2438 auto read_name_record = NameRecord(read_recorder[].front.filed); 2439 assert(read_name_record == name_record, "should be the same after reading"); 2440 2441 auto new_recorder = dart_A.recorder(); 2442 auto new_name_record = NameRecord("hugo", 'x'.repeat(200).array); 2443 new_recorder.remove(name_record); 2444 new_recorder.add(new_name_record); 2445 // new_recorder.each!q{a.dump}; 2446 auto rim_key_range = rimKeyRange(new_recorder); 2447 // writefln("rim key dump"); 2448 // rim_key_range.each!q{a.dump}; 2449 assertThrown!DARTException(dart_A.modify(new_recorder)); 2450 2451 } 2452 2453 } 2454 2455 { // undo test 2456 filename_A.forceRemove; 2457 2458 DARTFile.create(filename_A, net); 2459 auto dart_A = new DARTFile(net, filename_A); 2460 RecordFactory.Recorder recorder; 2461 2462 auto doc = DARTFakeNet.fake_doc(0xABB9_130b_11ef_0923); 2463 recorder = dart_A.recorder(); 2464 recorder.add(doc); 2465 dart_A.modify(recorder); 2466 2467 const bullseye = dart_A.bullseye; 2468 // dart_A.dump; 2469 auto new_doc = DARTFakeNet.fake_doc(0x2345_130b_1234_1234); 2470 recorder = dart_A.recorder(); 2471 recorder.add(new_doc); 2472 dart_A.modify(recorder); 2473 const new_bullseye = dart_A.bullseye; 2474 dart_A.modify(recorder, Yes.undo); 2475 assert(dart_A.bullseye != new_bullseye, 2476 "Should not be the same as the new bullseye after undo"); 2477 assert(dart_A.bullseye == bullseye, "should have been reverted to previoius bullseye"); 2478 } 2479 2480 } 2481 2482 { // undo test both with remove and adds 2483 filename_A.forceRemove; 2484 2485 DARTFile.create(filename_A, net); 2486 auto dart_A = new DARTFile(net, filename_A); 2487 RecordFactory.Recorder recorder; 2488 2489 const ulong[] datas = [ 2490 0xABB9_130b_11ef_0923, 2491 0x1234_5678_9120_1234, 2492 0xABCD_1234_0000_0000, 2493 ]; 2494 auto docs = datas.map!(a => DARTFakeNet.fake_doc(a)); 2495 2496 recorder = dart_A.recorder(); 2497 2498 foreach (doc; docs) { 2499 recorder.add(doc); 2500 } 2501 2502 dart_A.modify(recorder); 2503 2504 const bullseye = dart_A.bullseye; 2505 const dart_indices = recorder[].map!(a => a.dart_index).array; 2506 2507 auto new_doc = DARTFakeNet.fake_doc(0x2345_130b_1234_1234); 2508 recorder = dart_A.recorder(); 2509 recorder.add(new_doc); 2510 foreach (dart_index; dart_indices) { 2511 recorder.remove(dart_index); 2512 } 2513 dart_A.modify(recorder); 2514 const new_bullseye = dart_A.bullseye; 2515 dart_A.modify(recorder, Yes.undo); 2516 assert(dart_A.bullseye != new_bullseye, "Should not be the same as the new bullseye after undo"); 2517 assert(dart_A.bullseye == bullseye, "should have been reverted to previoius bullseye"); 2518 2519 } 2520 2521 { 2522 pragma(msg, "fixme(cbr): This unittest does not see to be relavant to DARTFile maybe this should be moved"); 2523 // At least it should not be dependent on tagion.script 2524 // Just make a d Document with $Y owner key 2525 filename_A.forceRemove; 2526 DARTFile.create(filename_A, net); 2527 auto dart_A = new DARTFile(net, filename_A); 2528 import tagion.crypto.Types; 2529 import tagion.script.TagionCurrency; 2530 import tagion.script.common; 2531 import tagion.utils.StdTime; 2532 2533 RecordFactory.Recorder recorder_A; 2534 2535 TagionBill[] bills; 2536 2537 Pubkey pkey1 = Pubkey([1, 2, 3, 4]); 2538 Pubkey pkey2 = Pubkey([2, 3, 4, 5]); 2539 2540 bills ~= TagionBill(100.TGN, currentTime, pkey1, Buffer.init); 2541 bills ~= TagionBill(100.TGN, currentTime, pkey2, Buffer.init); 2542 2543 recorder_A = dart_A.recorder; 2544 2545 recorder_A.insert(bills, Archive.Type.ADD); 2546 dart_A.modify(recorder_A); 2547 2548 // dart_A.dump; 2549 import tagion.crypto.SecureInterfaceNet; 2550 import tagion.crypto.SecureNet; 2551 2552 SecureNet _net = new StdSecureNet(); 2553 import tagion.crypto.SecureNet : StdSecureNet; 2554 2555 _net.generateKeyPair("wowo"); 2556 auto h = dart_A.search([pkey1, pkey2].map!(b => cast(Buffer) b).array, (() @trusted => cast(immutable) _net)()); 2557 } 2558 2559 { // Check the #name archives 2560 filename_A.forceRemove; 2561 DARTFile.create(filename_A, net); 2562 auto dart_A = new DARTFile(net, filename_A); 2563 static struct HashDoc { 2564 @label("#name") string name; 2565 int number; 2566 mixin HiBONRecord!(q{ 2567 this(string name, int n) { 2568 this.name=name; 2569 number=n; 2570 } 2571 }); 2572 } 2573 2574 auto recorder_add = dart_A.recorder; 2575 const hashdoc = HashDoc("hugo", 42); 2576 recorder_add.add(hashdoc); 2577 assert(recorder_add[].front.dart_index != recorder_add[].front.fingerprint, 2578 "The dart_index and the fingerprint of a archive should not be the same for a # archive"); 2579 auto bullseye = dart_A.modify(recorder_add); 2580 // dart_A.dump; 2581 // writefln("bullseye =%(%02x%)", bullseye); 2582 // writefln("fingerprint=%(%02x%)", recorder_add[].front.fingerprint); 2583 assert(bullseye == recorder_add[].front.fingerprint, 2584 "The bullseye for a DART with a single #key archive should be the same as the fingerprint of the archive"); 2585 const hashdoc_change = HashDoc("hugo", 17); 2586 auto recorder_B = dart_A.recorder; 2587 recorder_B.remove(hashdoc_change); 2588 // dart_A.dump; 2589 bullseye = dart_A.modify(recorder_B); 2590 auto recorder_change = dart_A.recorder; 2591 recorder_change.add(hashdoc_change); 2592 bullseye = dart_A.modify(recorder_change); 2593 // dart_A.dump; 2594 // writefln("bullseye =%(%02x%)", bullseye); 2595 // writefln("dart_index =%(%02x%)", recorder_change[].front.dart_index); 2596 // writefln("fingerprint=%(%02x%)", recorder_change[].front.fingerprint); 2597 assert(recorder_add[].front.dart_index == recorder_change[].front.dart_index); 2598 assert(bullseye == recorder_change[].front.fingerprint, 2599 "The bullseye for a DART with a single #key archive should be the same as the fingerprint of the archive"); 2600 { // read the dart_index from the dart and check the dart_index 2601 auto load_recorder = dart_A.loads(recorder_change[].map!(a => a.dart_index)); 2602 //writefln("load_recorder=%(%02x%)", load_recorder[].front.dart_index); 2603 assert(equal( 2604 load_recorder[].map!(a => a.dart_index), 2605 recorder_change[].map!(a => a.dart_index))); 2606 } 2607 // writefln("filename_A %s", filename_A); 2608 const hashdoc_extra = HashDoc("boerge", 42); 2609 auto recorder_C = dart_A.recorder; 2610 recorder_C.add(hashdoc_extra); 2611 bullseye = dart_A.modify(recorder_C); 2612 dart_A.close; 2613 { 2614 auto dart_reload = new DARTFile(net, filename_A); 2615 auto reload_recorder = dart_reload.loads(recorder_change[].map!(a => a.dart_index)); 2616 //writefln("reload_recorder=%(%02x%)", reload_recorder[].front.dart_index); 2617 // dart_reload.dump; 2618 assert(equal(recorder_change[].map!(a => a.filed), reload_recorder[].map!(a => a.filed))); 2619 } 2620 2621 } 2622 2623 }