GitLab

This is a draft.  There's a LOT of hard design choices which are not
yet completely settled here.

Corresponding updates to the ipld/specs repo will be coming soon:
these implementations match a very recursive concept of selectors.
(https://github.com/ipld/specs/pull/116 is roughly this.)

There's so many things to go over, here.

- selectors at all
- selectFields is kind of a special case of unions
- selectPath as a concept is gone; is a degenerate case of selectFields
- we've added some new methods to help narrow down search spaces
- we have serial selector spec parsers...!  (very hand-rolled.)
- the idea of always reporting candidates vs definite match parents
  is dropped for now; it requires a different algo with different
  performance characteristics, so, we'll do it as such -- later.
- we ended up with unions being *in*!  They're going to be used
  internally by a bunch of other things -- see comment blocks in
  the code about that (tl;dr recursives imply a need of unions).

More docs will be coming in future commits; this is just a checkpoint
of the progress.
Signed-off-by: Eric Myhre <hash@exultant.us>

And test.
Signed-off-by: Eric Myhre <hash@exultant.us>

Autocomplete on TraversalProgress was suggesting *way* too many things.
It's now reigned in.

Being able to say `tp.Ctx` is gone, but that's a small price to pay.
(And perhaps we should actually move the Context up to TP?  Wouldn't
seem unreasonable.  I think the main reason it's in TC right now is
to reduce the size of memory that's shuffled when TP is passed by value
down the stack, and it's unclear how consequential that's really
going to be in the big picture.  We can review this later.)
Signed-off-by: Eric Myhre <hash@exultant.us>

NodeBuilderChooser returned -- sorry.  There are some cases where it's
unavoidable.  (If we have schemas / typed nodes, we can do feature
detection on the node to see if it can recommend an appropriate
NodeBuilder for the far side of its link.  If we're fine using Node
implementations that have 'any' storage support, it's not an issue.
If we're using *bind* implementation Nodes -- which are constrained
by the Golang native type system, and yet not perfectly mapped onto
our own typed.Node constraint declarations -- then we need some way
to choose the NodeBuilder.  So.  NodeBuilderChooser.  Again: sorry.)

We can probably still expect the NodeBuilderChooser to be fixed
(probably returning one of the 'any' storage supporting Node impls)
in practice, since these traversal systems are generally for either
"low context" usage (e.g., dunno what the data is) or will be used
on typed/schema nodes, in which case we're again free of these issues.
And the default values will indeed do this, using our new helpful
default initialization for TraversalConfig.

TraversalConfig will now always be initialized to sensible default
values when using any of the traversal methods.  That means you can
always assume `tp.Ctx`, etc, are going to be set -- no nil checks
necssary -- even though they're optional to the caller.

Error messages from traversal.Focus are touched up a bit for both
consistency and clearer information.  There's more work to do here:
we want these to be full-on typed errors before we call it "done".
This work will probably begin soon, but be spread over quite a few
commits (we also need to go back up to the *main* ipld package and
make types for Node-level errors, and make sure tests exist to
standardize those errors across Node implementations as well).
Signed-off-by: Eric Myhre <hash@exultant.us>

We now have both MapIterator and ListIterator interfaces.
Both return key-value (or index-value) pairs, rather than just keys.

List iterators may seem a tad redundant: you just loop over the length,
right?  Well, sure.  But there's one place a list iterator shines:
selecting only a subset of elements.  And indeed, we'll be doing
exactly that in the traversal/selector package; therefore, we
definitely need list iterators.

We might want keys-only iterators again in the future, but at present,
I'm deferring that.  It's definitely true that we should have iterators
returning values as a core feature, since they're likely to be more
efficiently supportable than "random" access (especially when we get to
some Advanced Layout data systems), so we'll implement those first.

Additionally, note that MapIterator now returns a Node for the key.
This is to account for that fact that when using the schema system and
typed nodes, map keys can be more *specific* types.  Such nodes are
still required to be kind==ReprKind_String, but string might not be
their *preferred* native format (think: tuples with serialized to be
delimiter-separated strings); we need to account for that.
(MapBuilder.Insert method already takes a Node parameter for similar
reasons: so it can take *typed* nodes.  Node.TraverseField accepting
a plain string is the oddball out here, and should be rectified.)
Signed-off-by: Eric Myhre <hash@exultant.us>

Having a function called "Kind" return a "ReprKind" was inconsistent.

Also, we want to introduce a "Kind" method on `typed.Node` in the future.

No logical content to this change: you can safely refactor with sed.
Signed-off-by: Eric Myhre <hash@exultant.us>

Signed-off-by: Eric Myhre <hash@exultant.us>

Yes, this one has moved about a bunch now.  Hopefully this is the last time.
It's true and elegant that paths really only emerge as descriptions of traversal
progress; however, this misses a few other practicalities.
There are other kinds of traversal (other than the traversal package, whoa!) out
there: see the typesystem packages, which had grown a custom path implementation
simply for error reporting messages!
In general, we seem to want to have Path around for logging and errors, which
will make it increasingly desirable to have available in the root package when
we begin to clean up towards strongly typed errors.
And we also need Path for LinkContext -- and wherever that comes to rest, it
definitely need to not be an import cycle problem, which it *is* if Path is
in traversal and we wanted LinkContext to be *anywhere* else.
All of these point to moving Path back up to the root, and the errors concern
in particular cinches it.

Drop the Path.traverse method.  As has been noted in its comment for a while
now, that method wasn't useful for much, having been replaced by features
in the traversal package.

(Also drop the tests specific to the Path.traverse method.  We should write
more tests against the features now implemented by travesral.Focus... but at
this point, it'd be easier to start over.  The tests we're dropping are against
a different model of traversal (returns rather than visitors) and are also
built against the old hacky ipldfree mutable model which is deprecated and
soon to be dropped.)

Also, a small docs fix: drop description of this Path implementation as a
"merklepath" -- it is not.  These paths are all relative, and do not contain
an innate understanding of hashed object identifiers at their first segment.
Signed-off-by: Eric Myhre <hash@exultant.us>

Outline of Traverse* funcs; comment about link loaders in TraversalConfig; confession of working draft of Selector interface; fixed typo in AdvVisitFn return types.

Yes, that's lot of things heaped in one commit.

Yes, (unfortunately,) they're all related.  Almost the entirety of this
has to manifest *at once*, all seamlessly connected, for any part of
it to get off the ground.

Note how very much is handwaved in the comments about TraversalConfig
having linkloader tools of some kind.  There's a lot to unpack there.
Getting it to work well, and let users of the library supply functions
that customize the parts that are interesting to the user, while *not*
getting them hamstrung by a bunch of details about multicodecs and
multihashing (unless they want to!)... requires careful design work.
Signed-off-by: Eric Myhre <hash@exultant.us>

All traversal/transform/selector/path code to date got a rethink.

For the longest time, I was trying to keep all the traversal code in
the main root IPLD package, thinking/hoping that the number of relevant
functions would be minimal enough that this would be fine.

Somewhere around the time where I conceded that yes, we *do* need
separate methods for writable and readonly paths (it's true that
readonly is a degenerate case of writable -- but they have different
performance characteristics!), I gave up: the number of functions in
play is too high to heap alltogether in the root package namespace.

This leads to a number of other surprising results: namely, that
ipld.Path *isn't* -- it's actually traversal.Path!  We *don't use*
paths anywhere else except as guidance to some forms of traversal,
and logs and progress markers during traversal.  Huh!
Despite being initially surprising, I now regard this as a *good*
code smell.

ipld.Traversal as an interface and ipld.Path.Traverse are dropped.
These turned out to be the wrong level of abstraction:
it's both missing things, and not able to return enough things.
By the time we would fix both, it's not an abstraction anymore.

Path.Traverse didn't know how to use a link loader func -- and
that's correct; it shouldn't -- and it also didn't retain and
return a stack of Nodes it traversed -- which again, it shouldn't,
because in general that would be useless overkill and resource waste...
it's just that both these things are essential in some use cases.
So!  Cut that gordian knot.

The Focus/FocusTransform/Traverse/TraverseTransform methods will now
do all recursion work themselves, internally.  The transform family
will keep stacks of nodes encountered along the way, to aid in the
(presumably) coming tree re-build; the focus family won't.
All of these methods will be able to support link loading, though
implementation of that is still upcoming.

There's a few more fields in TraversalProgress, also preparing for when
we have automatic link loading and traversal: we'll want to be able
to inform the user's callbacks about load edges.  (I'm not a fan of the
term 'block' here, but running with it for the moment.)

TraversalConfig is expected to grow.  Namely, to include link
loaders... and subsequently, probably block writers, as well!  This is
a big subject, though.  It'll probably take several commits and
possibly more than one iteration over time to hammer out a good API.

One thing that's interesting to note that neither TraversalConfig nor
TraversalProgress will grow to contain certain things: for example,
a map of "seen" CIDs when doing link traversal.  Why?  Well, if you've
been mentally modelling things as a graph, this is surprising; surely
any graph traversal needs to remember a set of already-visited nodes.
The trick is... we're *not* doing a graph traversal -- not exactly!
Since our visitor gets a (Node,Path) *tuple*... it would be wrong to
memoize on anything other than the complete tuple; and the Path part
of the tuple means we're actually doing a *tree* walk rather than
a graph walk.  (And of course, since we're operating on DAGs,
termination guarantees are already a non-issue.)  Tada; no "seen" set.
Signed-off-by: Eric Myhre <hash@exultant.us>