CyberShadow / DustMite / 74
0%
master: 95%

LAST BUILD BRANCH: next
DEFAULT BRANCH: master
Ran
Jobs 1
Files 2
Run time 1s
Badge
Embed ▾
README BADGES
x

If you need to use a raster PNG badge, change the '.svg' to '.png' in the link

Markdown

Textile

RDoc

HTML

Rst
74

push

travis-ci

CyberShadow 
Overhaul tree representation and edit algorithms

Instead of predicting the result of applying a reduction using a tree
+ reduction object, redesign the tree data structure so that it's
possible to create cheap COW copies and simply apply the reductions as
tree edits.

This is achieved by introducing the concept of addresses (different
from the existing size_t[] one, which should be replaced with the new
one). An address is a linked list of indexes, starting from the leaf,
and ending with the index at the top-level root node. (They are cached
in a global tree to save memory.) Pointers to non-child entities are
thus now replaced by addresses, which continue to be valid even when
the tree is copied.

To ensure addresses remain valid even after the tree is edited, all
edits are performed in such a way that all nodes (which are still in
the tree) continue to remain reachable through their original address,
even after being moved around. This is achieved using tombstones with
redirects (an address going through a redirect transparently resolves
to the new address, like a symbolic link). Children are added strictly
by appending to the existing child list, which guarantees that their
new addresses were formally unoccupied.

With the ability to safely create cheap writable copies of the entire
tree, and invalidate cached information in only those nodes which have
changed, this commit paves the way for optimizations such as saving
trees for lookahead tasks in worker threads, partial rehashing, and
sub-O(n) reduction testing.

Note: there is a regression in the strat-careful test. The affected
code looks as follows:

import a, b, c, d, e;

After this commit, DustMite first removes the "d," tokens:

import a, b, c, d, e;
                ^^

To remove the "e" import, DustMite would also have to remove the comma
following "c". However, there is nothing linking "e" to "c"'s comma.

The reason for the regression itself is most likely a random
fluctuation due to the ... (continued)

1355 of 1548 relevant lines covered (87.53%)

100731.1 hits per line

Jobs
ID Job ID Ran Files Coverage
1 74.1 0
87.53
 Travis Job 74.1
Source Files on build 74
Detailed source file information is not available for this build.