chore: docs

[rvagg]

inline docs so far, want to add a docs.go too, will probably work on a spec for ipld/specs too that it can link to

[rvagg]

Added doc.go with algorithm summary. More meat in here than the HAMT since we don't yet have a proper spec doc.

I thought about trying to pull in some ASCII art used in https://github.com/ipld/specs/blob/master/data-structures/vector.md but for sparse indexing but ran out of steam. Maybe that can be saved for a spec doc. Those are useful visualisations for what's going on here, you just have to imaging missing bits in the middle of the tree structures.

Ready for review.

@anorth @momack2 @mikeal @Stebalien

[rvagg]

ping @ZenGround0 this should probably go in

[ZenGround0]

@rvagg no rush but I'm ready to review this now once its rebased on the big changes now on master. Thanks for your patience on this one!

[rvagg]

I had to start this again because of the large changes since the original PR, so this is a force push of a new version of the docs for the current code.

@ZenGround0 @Stebalien @anorth feedback would be appreciated! I know it's a lot of text and that's not to many people's tastes in code. But currently we have no other documentation for this data structure so this is in lieu of a formal specification. I think we need a formal specification but that will have to come later and it should be able to use some of this documentation in forming it (doc.go is done with this end goal in mind). The main goal right now is to widen the audience of people who understand what on earth this thing is. Secondarily it's for people implementing this in other languages.

If it's too much to merge, that's fine too since the ideal exists of using this to form a spec doc one day, so it's not entirely lost work. But in that case there may be a mid-point of just-enough that's acceptable?

[anorth]

@rvagg can you merge or do you need me to?

[rvagg]

The comments about the "advisory" nature of the count seem unnecessary to me

Yeah, it's our framing difference coming to the fore here again; me with an IPLD lens viewing blocks as singular entities, part of a larger, perhaps not-so-trusted web of entities. You with the Filecoin lens of these blocks essentially being the same entity.

We had a discussion recently about DAG-PB, which stores the UnixFS data for IPFS and has a "size" field in it adjacent to each of the links that's supposed to tell you the cumulative size of all blocks in the graph from that link and it ends up with the same problem - you really can't trust it and it's essentially "advisory" so you shouldn't build code that relies on it for anything important.

In this case it's different, but is it completely different? Are each of the nodes that handle this data going to be validating the count by rebuilding the data structures themselves?

I'm happy to remove those comments or soften them somewhat. Maybe @Stebalien has thoughts here, he was involved in that DAG-PB discussion as well and is well equipped with both frames of viewing these things!

[rvagg]

Here's that DAG-PB discussion btw (I think it's quite interesting for context if anyone else wants to dip toes into this area of thought) https://github.com/ipld/specs/pull/234

@Stebalien in the diff here, ctrl-f and search for "advisory", there's a few places it exists, always re "count". I'd appreciate your thoughts on whether any such note is necessary here or if it could be shaped a bit better to be relevant.

[rvagg]

good feedback, have addressed them in b7339c7. "advisory" doesn't make an appearance anymore but I've tried to leave the original idea in there without calling it out as something special to be worried about

I'll leave it to you to merge if you're happy with it @anorth, there's a couple of fixups in there now so you'll probably want to squash

[anorth]

there's a couple of fixups in there now so you'll probably want to squash

I always want to squash! 😁