datrs / flat-tree Goto Github PK

I noticed that uncle was implemented, which isn't part of the js api. Is that used somewhere?

I skipped over implementing the offset stuff in the iterator. https://github.com/mafintosh/flat-tree/blob/master/index.js - we should reimplement that so we get access to the is_left and is_right methods, required for hypercore.

I decided to look at the generated assembly for the left_child function (inlining everything it calls):

example::left_child:
  push rbp
  mov rbp, rsp
  xor eax, eax
  test dil, 1
  jne .LBB0_2
  mov rdx, rdi
  pop rbp
  ret
.LBB0_2:
  mov rdx, rdi
  mov rcx, rdx
.LBB0_3:
  shr rcx
  add rax, 1
  test dl, 2
  mov rdx, rcx
  jne .LBB0_3
  test rax, rax
  je .LBB0_5
  lea ecx, [rax + 1]
  shr rdi, cl
  add rdi, rdi
  lea rdx, [rax - 1]
  mov ecx, eax
  shl rdi, cl
  mov esi, 1
  mov ecx, edx
  shl rsi, cl
  mov eax, 1
  add rsi, -1
  or rdi, rsi
  mov rdx, rdi
  pop rbp
  ret
.LBB0_5:
  mov eax, 1
  mov rdx, rdi
  pop rbp
  ret

By rewriting it to store each level in its entirety consecutively (level 1, then 2, then 3, etc), I got this (since then changed, will update later, but wasn't much longer):

example::left_child:
  push rbp
  mov rbp, rsp
  lea rax, [rdi + rdi]
  add rax, -1
  pop rbp
  ret

I understand that the algorithm is taken from the JS project, but I still think that this algorithm is quite slow...

It seems to me that the data referred to as index is not really an index. At least it's not the node index when building the merkle-tree. It's a bit confusing when the nodes are stored in a flat data structure (e.g., a list).

When building the merkle-tree, there is an inherent ordering which is the order in which each hash is computed (using this order requires the least amount of memory to build the merkle-tree):

1. first data block is received, its hash is computed (A)
2. second data block is received, its hash is computed (B)
3. hash of (AB) is computed (C)
4. third data block is received, hashes computed (D)
5. fourth data block is received, hashes computed (E)
6. hash of (DE) is computed (F)
7. hash of (CF) is computed (G)
   ...

The index for the above hashes in the flat-tree are the following:

• A: 0
• B: 2
• C: 1
• D: 4
• E: 6
• F: 5
• G: 3

Maybe there is a reason for using index to refer to these nodes, but I could not find one. So, if there is no specific reason for this name, I propose to use id or maybe position instead.

I have an index, lets say index = 44 and I want the offset, so I call offset(44). Does it even make sense to call offset_with_depth(44, 4)?

I suspect these functions are there because rust doesn't have default values for function parameters, which is the same thing for functions in c.

Maybe all xyz_with_depth() should be local only?

Same goes for .sibling(), .parent() etc

More concretely, does a calling lib ever pass in depth explicitly?

When compiling hypercore I get the following error:

error[E0554]: #![feature] may not be used on the stable release channel
 --> /Users/bryce/.cargo/registry/src/github.com-1ecc6299db9ec823/flat-tree-3.3.0/src/lib.rs:2:1
  |
2 | #![feature(external_doc)]
  | ^^^^^^^^^^^^^^^^^^^^^^^^^

cargo --version
cargo 1.28.0 (96a2c7d16 2018-07-13)

I'm not very familiar with Rust, is it implied that I should not be using the stable release channel?

I get the following output

error[E0308]: mismatched types
    --> /home/lms/.cargo/registry/src/github.com-1ecc6299db9ec823/clippy_lints-0.0.194/src/loops.rs:1801:48
     |
1801 |         ty::TyArray(_, n) => (0..=32).contains(n.val.to_raw_bits().expect("array length")),
     |                                                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
     |                                                |
     |                                                expected reference, found u128
     |                                                help: consider borrowing here: `&n.val.to_raw_bits().expect("array length")`
     |
     = note: expected type `&_`
                found type `u128`

error[E0308]: mismatched types
   --> /home/lms/.cargo/registry/src/github.com-1ecc6299db9ec823/clippy_lints-0.0.194/src/regex.rs:213:56
    |
213 |                         str_span(expr.span, *e.span(), offset),
    |                                                        ^^^^^^ expected usize, found u16

error[E0308]: mismatched types
   --> /home/lms/.cargo/registry/src/github.com-1ecc6299db9ec823/clippy_lints-0.0.194/src/regex.rs:221:56
    |
221 |                         str_span(expr.span, *e.span(), offset),
    |                                                        ^^^^^^ expected usize, found u16

error: aborting due to 3 previous errors

For more information about this error, try `rustc --explain E0308`.
error: Could not compile `clippy_lints`.

I made rustup update earlier today, not sure if it has anything to do with that

The following isn't working right now:

flat_tree::children(9) == (8, 10)

Instead it's returning (2, 4)

Some cases to consider:

• calling .prev() on the iterator while at the left nodes
• calling left-child / right-child of a leaf node
• calling left-span / right-span of a leaf node

I'm thinking we should perhaps return the Option type more often in both FlatTree and the Iterator structs.

Iterators / indexes / lengths are all usize. Accepting usize only makes the API a lot better to use.

The other repositories use Apache-2.0.

cc @yoshuawuyts

Having an iterator exposed would make it easier to walk flat-tree. With stuff like Seek we can also skip forward / backward. Provides parity with mafintosh/flat-tree.

Ref

• https://doc.rust-lang.org/std/iter/trait.Iterator.html

We can probably drop the API header, but also bring it closer in line with the rest of the repos.

If it turns out that left_child_with_depth and right_child_with_depth can be private, there's a few things we could change after that

1. If they aren't used internally (which I suspect they aren't), then we could merge them, so body of left_child_with_depth is moved to left_child (and similarly for right_child)
2. The depth == 0 check is no longer needed, since this only happens for even indices

So

pub fn left_child_with_depth(i: usize, depth: usize) -> Option<usize> {
  if is_even(i) {
    None
  } else if depth == 0 {
    Some(i)
  } else {
    Some(index(
      depth - 1,
      offset_with_depth(i, depth) << 1,
    ))
  }
}

pub fn left_child(i: usize) -> Option<usize> {
  left_child_with_depth(i, depth(i))
}

Could be

pub fn left_child(i: usize) -> Option<usize> {
  if is_even(i) {
    None
  } else {
    let d = depth(i)
    Some(index(
      d - 1,
      offset_with_depth(i, d) << 1,
    ))
  }
}

and make friends on https://github.com/datrs 🎉