GitLab

This reverts commit 6e6625bd.

Discussed at
https://github.com/ipld/go-ipld-prime/pull/126#issuecomment-753003441

Long story short, the motivations of this rename are good,
but the new name also carries some connotations we're really not sure
about, and so we're going to undo this for now, and continue to think
about it in the future.

This should be more intuitive to Go programmers, since assignments are
generally trivial operations, but conversions imply that extra work
might be needed to adapt the value to fit in the recipient.

The entire change is just:

	sed -ri 's/AssignNode/ConvertFrom/g' **/*.go

Downstream users can very likely use the same line to fix their function
declarations and calls.

Fixes #95.

We only supported representing Int nodes as Go's "int" builtin type.
This is fine on 64-bit, but on 32-bit, it limited those node values to
just 32 bits. This is a problem in practice, because it's reasonable to
want more than 32 bits for integers.

Moreover, this meant that IPLD would change behavior if built for a
32-bit platform; it would not be able to decode large integers, for
example, when in fact that was just a software limitation that 64-bit
builds did not have.

To fix this problem, consistently use int64 for AsInt and AssignInt.

A lot more functions are part of this rewrite as well; mainly, those
revolving around collections and iterating. Some might never need more
than 32 bits in practice, but consistency and portability is preferred.
Moreover, many are interfaces, and we want IPLD interfaces to be
flexible, which will be important for ADLs.

Below are some GNU sed lines which can be used to quickly update
function signatures to use int64:

	sed -ri 's/(func.* AsInt.*)\<int\>/\1int64/g' **/*.go
	sed -ri 's/(func.* AssignInt.*)\<int\>/\1int64/g' **/*.go
	sed -ri 's/(func.* Length.*)\<int\>/\1int64/g' **/*.go
	sed -ri 's/(func.* LookupByIndex.*)\<int\>/\1int64/g' **/*.go
	sed -ri 's/(func.* Next.*)\<int\>/\1int64/g' **/*.go
	sed -ri 's/(func.* ValuePrototype.*)\<int\>/\1int64/g' **/*.go

Note that the function bodies, as well as the code that calls said
functions, may need to be manually updated with the integer type change.
That cannot be automated, because it's possible that an automated fix
would silently introduce potential overflows not being handled.

Some TODOs and FIXMEs for overflow checks are removed, since we remove
some now unnecessary int64->int conversions. On the other hand, the
older codecs based on refmt need to gain some overflow check TODOs,
since refmt uses ints. That is okay for now, since we'll phase out refmt
pretty soon.

While at it, update codectools to use int64 for token Length fields, so
that it properly supports full IPLD integers without machine-dependent
behavior and overflow checks. The budget integer is also updated to be
int64, since the lengths it uses are now int64.

Note that this refactor needed changes to the Go code generator as well
as some of the tests, for the purpose of updating all the code.

Finally, note that the code-generated iterator structs do not use int64
fields internally, even though they must return int64 numbers to
implement the interface. This is because they use the numeric fields to
count up to a small finite amount (such as the number of fields in a Go
struct), or up to the length of a map/slice. Neither of them can ever
outgrow "int".

Fixes #124.

This is a clear and simple solution to the problem.

(I think I may have gotten so optimistic about type systems for a while
that I forgot that returning nils is an option.  mmmm.)

The docs on NodeBuilder already even nodded towards this possibility,
so I've just further clarified that.

After staring at this method for a while, I begin to wonder if it even
is all that useful.  To use it sensibly on structs or unions (for any
purpose other than checking if something is *not* a field/member),
you have to figure out which keys you can ask it about... which...
means you'd need the type info, to be able to enumerate that!  At which
point you'd just be able to look at the type info, and wouldn't really
need to ask the builder about ValuePrototype in this way at all,
rendering the whole thing moot.

But removing it seems a little drastic, too.  And would leave questions
about how to do those inspections on untyped things.  So.  Despite the
nibbles of oddity around this, perhaps this is still the least-bad
design that can make these situations legible.

I can't quite claim tests passed on the *first* shot... but,
the first shot after mostly syntactical (rather than semantic) fixes?
Yeah, actually.  That was pretty fun.

Snuck in a bit of DRY'ing up.  The repetition in BeginMap methods
got to me, and was low hanging fruit, so I extract that from unions
and also backported it to structs.

Errors got some work in this commit, because it turns out I've
straightjacketed myself by not allowing "fmt.Errorf" due to imports.
There's a lot to do there, and I only tackled what was directly
critical to get this commit about unions across the finish line,
but there's a few remarks in comments about where to go next.

Some more comments about future work on the type info holder types
also appears; I'm starting to skid on those placeholders and their
issues more and more.  I really hope we can get to replace those
sooner than later.

And... also, yes, the idea of not having a "focus" state field in
assemblers really bit it, hard, as speculated in the previous
commit message.  I ended up using 'ca' in more switches than I
expected, simply because it's easier to use that than have the
conditonal templating branches that would be necessary to use the other
tagging mechanisms that do also have sufficient info.

One big fixme in the core interfaces for nodebuilders (wince):
the ValuePrototype method can error sometimes, and that hasn't been
accounted for.  Need to make a decision about what to do there.
It's not really an exercised path in practice, but it shouldn't
contain caltrops, regardless of how frequently used it is.
(This probably would've come up earlier, except there's a bunch of
stubs about ValuePrototype in other parts of codegen already; all of
them need backfill, but haven't yet made it to top of the todo heap.)

But despite all the fixmes accumulated, this does bring unions
to be a usable thing, and definitively proves out that the design
still works, even for what turns out to be one of the most complicated
parts of the schema system!  It's very, *very* exciting to add the
checkmarks to this part of the feature table -- it's one of the places
I most feared "unknown unknowns", now it's put to bed.  Woot!

Hopefully this increases clarity and eases comprehension.

Notes and discussion can be found at
https://github.com/ipld/go-ipld-prime/issues/54 (and also
I suppose in some of our weekly video chats, but I'd have
to go on quite a dig to find the relevant links and time).

Many many refernces to 'ns' are also updated to 'np',
making the line count in this diff pretty wild.

It needs this for dealing with the exciting details of...
well, you can read the comment.

This is a heck of an example of how the schema system, even though
we've been almost completely successful in isolating it in packages
and not letting it appear or be referenced in any of the core
interfaces and main dependencies... is still informing and shaping
a few key details of the central interfaces.

Future IPLD library implementers in other languages may want to take
note of this commit for the above reason: it's useful to make sure
you've also taken account of schema systems in your library design
at an early point.  Even if you don't intend to implement them before
doing a 1.0 of the core interfaces and Data Model essentials,
knowing what expressiveness will be needed will save you a lot of work.

Saying "Node" again in the middle is just purely redundant and doesn't
improve clarity in any meaningful way.  Begone with it.

This is a *lot* of changes.  It's the most significant change to date,
both in semantics and in character count, since the start of this repo.
It changes the most central interfaces, and significantly so.

But all tests pass.  And all benchmarks are *improved*.

The Node interface (the reading side) is mostly unchanged -- a lot of
consuming code will still compile and work just fine without changes --
but any other Node implementations out there might need some updating.

The NodeBuilder interface (the writing side) is *extremely* changed --
any implementations out there will *definitely* need change -- and most
consumers will too.  It's unavoidable with a semantic fix this big.
The performance improvements should make it worth your while, though.

If you want more background on how and why we got here, you've got
quite a few commits on the "research-admissions" branches to catch up
on reading.  But here's a rundown of the changes:

(Get a glass of water or something calming before reading...)

=== NodeAssembler introduced! ===

NodeAssembler is a new interface that describes most of the work of
creating and filling data into a new Node.

The NodeBuilder interface is still around, but changed in role.
A NodeBuilder is now always also a NodeAssembler; additionally, it can
return the final Node to you.

A NodeAssembler, unlike NodeBuilder, can **not** return a Node to you.
In this way, a NodeBuilder represents the ability to allocate memory.
A NodeAssembler often *does not*: it's just *filling in* memory.

This design overall is much more friendly to efficient operations:
in this model, we do allocations in bulk when a NodeBuilder is used,
and then NodeAssemblers are used thereafter to fill it in -- this
mental model is very friendly to amortizing memory allocations.
Previously, the NodeBuilder interface made such a pattern of use
somewhere between difficult and outright impossible, because it was
modeled around building small values, then creating a bigger value and
inserting the smaller ones into it.

This is the key change that cascaded into producing the entire other
set of changes which land in this commit.

The NodeBuilder methods for getting "child builders" are also gone
as a result of these changes.  The result feels a lot smoother.
(You can still ask for the NodeStyle for children of a recursive kind!
But you'll find that even though it's possible, it's rarely necessary.)

We see some direct improvements from this interface change already.
We'll see even more in the future: creating values when using codegen'd
implementations of Node was hugely encumbered by the old NodeBuilder
model; NodeAssembler *radically* raises the possible ceiling for
performance of codegen Node implementations.

=== NodeStyle introduced ===

NodeStyle is a new interface type that is used to carry information
about concrete node implementations.

You can always use a NodeStyle to get a NodeBuilder.

NodeStyle may also have additional features on it which can be detected
by interface checks.  (This isn't heavily used yet, but we imagine it
might become handy in the future.)

NodeStyle replaces NodeBuilder in many function arguments,
because often what we wanted was to communicate a selection of Node
implementation strategy, but not actually the start of construction;
the NodeStyle interface now allows us to *say that*.

NodeStyle typically cost nothing to pass around, whereas a NodeBuilder
generally requires an allocation to create and initialize.  This means
we can use NodeStyle more freely in many contexts.

=== node package paths changed ===

Node implementations are now in packages under the "node/*" directory.
Previously, they were under an "impl/*" directory.

The "impl/free" package is replaced by the the "node/basic" package!
The package name was "ipldfree"; it's now "basicnode".

=== basicnode is an improved runtime/anycontent Node implementation ===

The `basicnode` package works much the same as the `ipldfree` package
used to -- you can store any kind of data in it, and it just does as
best it can to represent and handle that, and it works without any
kind of type info nor needs of compile-time special support, etc --
while being just quietly *better at it*.

The resident memory size of most things has gone down.
(We're not using "fat unions" in the implementation anymore.)

The cost of iterating maps has gone down *dramatically*.
Iteration previously suffered from O(n) allocations due to
expensive `runtime.conv*` calls when yielding keys.
Iteration is now O(1) (!!) because we redesigned `basicnode` internals
to use "internal pointers" more heavily, and this avoids the costs
from `runtime.conv*`.
(We could've done this separately from the NodeAssembler change,
admittedly.  But both are the product of research into how impactful
clever use of "internal pointers" can be, and lots of code in the
neighborhood had to be rewritten for the NodeAssembler interface,
so, these diffs arrive as one.)

Error messages are more informative.

Many small operations should get a few nanoseconds faster.
(The implementation uses more concrete types and fewer switch
statements.  The difference probably isn't the most noticeable part of
all these changes, but it's there.)

--- basicnode constructor helpers do all return pointers ---

All the "New*" helper functions in the basicnode package return
interfaces which are filled by a pointer now.
This is change from how they worked previously when they were first
implemented in the "rsrch" package.

The experience of integrating basicnode with the tests in the traversal
package made it clear that having a mixture of pointer and non-pointer
values flying around will be irritating in practice.  And since it is
the case that when returning values from inside a larger structure,
we *must* end up returning a pointer, pointers are thus what we
standardize on.

(There was even some writeup in the HACKME file about how we *might*
encounter issues on this, and need to change to pointers-everywhere --
the "pointer-vs-value inhabitant consistency" heading.  Yep: we did.
And since this detail is now resolved, that doc section is dropped.)

This doesn't really make any difference to performance.
The old way would cause an alloc in those method via 'conv*' methods;
the new way just makes it more explicit and go through a different
runtime method at the bottom, but it's still the same number of
allocations for essentially the same reasons.  (I do wonder if at some
future point, the golang compiler might get cleverer about eliding
'conv*' calls, and then this change we make here might be unfortunate;
but that's certainly not true today, nor in the future at any proximity
that I can foresee.)

=== iterator getters return nil for wrong-kind ===

The Node.MapIterator and Node.ListIterator methods now return nil
if you call them on non-maps or non-lists.

Previously, they would return an iterator, but using it would just
constantly error.

I don't think anyone was honestly really checking those error thunks,
and they made a lot of boilerplate white noise in the implementations,
and the error is still entirely avoidable by checking the node kind
up-front (and this is strictly preferable anyway, since it's faster
than getting an error thunk, poking it to get the error, etc)...
so, in total, there seem like very few reasons these were useful:
the idea is thus dropped.

Docs in the Node interface reflect this.

=== node/mixins makes new Node implementations easier ===

The mixins package isn't usable directly, but if you're going to make
a new Node implementation, it should save you a lot of typing...
and also, boost consistency of basic error handling.

Codegen will look forward to using this.  (Codegen already had much of
these semantics internally, and so this package is sort of lifting that
back out to be more generally usable.  By making it live out here as
exported symbols in the core library, we should also reduce the sheer
character count of codegen output.)

=== 'typed.Node' is now 'schema.TypedNode' ===

A bunch of interfaces that were under the "impl/typed" path moved to
be in the "schema" package instead.  This probably makes sense to you
if you look at them and needs no further explanation.

(The reason it comes in this diff, though, is that it was forced:
adding better tests to the traversal package highlighted a bunch of
cyclic dependency issues that came from 'typed.Node' being in a
package that had concrete use of 'basicnode'.)

=== codecs ===

The 'encoding' package is now named 'codec'.

This name is shorter; it's more in line with vocabulary we use
elsewhere in the IPLD project (whereas 'encoding' was more of a nod
to the naming found in the golang standard library); and in my personal
opinion it does better at describing the both directions of the process
(whereas 'encoding' sounds like only the to-linear-bytes direction).

I just like it better.

=== unmarshal functions no longer return node ===

Unmarshal functions accept an NodeAssembler parameter (rather than
a NodeBuilder, as before, nor a NodeStyle, which might also make sense
in the new family of interfaces).

This means they no longer need to return a Node, either -- the caller
can decide where the unmarshalled data lands.  If the caller is using
a NodeBuilder, it means they can call Build on that to get the value.
(If it's a codegen NodeBuilder with More Information, the caller can
use any specialized functions to get the more informative pointers
without need for casting!)

Broadly speaking, this means users of unmarshal functions have more
control over how memory allocation comes into play.

We may want to add more helper functions to the various codec packages
which take a NodeStyle argument and do return a Node.  That's not in
this diff, though.  (Need to decide what pattern of naming these
various APIs would deserve, among other things.)

=== the fluent package ===

The fluent package changed significantly.

The readonly/Node side of it is dropped.  It didn't seem to get a ton
of exercise in practice; the 'traversal' package (and in the future,
perhaps also a 'cursor' package) addresses a lot of the same needs,
and what remains is also covered well these days by the 'must' package;
and the performance cost of fluent node wrappers as well as the
composability obstruction of them... is just too much to be worth it.

The few things that used fluent.Node for reading data now mostly use
the 'must' package instead (and look better for it, imo).

It's possible that some sort of fluent.Node will be rebuilt someday,
but it's not entirely clear to me what it should look like, and indeed
whether or not it's a good idea to have in the repo at all if the
performance of it is counterindicated in a majority of situations...
so, it's not part of today's update.

The writing/NodeBuilder/NodeAssembler fluent wrappers are continued.
It's similar to before (panics promptly on errors, and has a lot of
closures)... but also reflects all of the changes made in the migration
towards NodeAssembler: it doesn't return intermediate nodes, and
there's much less kerfuffle with getting child builders.
Overall, the fluent builders are now even more streamlined than before;
the closures need even fewer parameters; great success!

The fluent.NodeAssembler interface retains the "Create" terminology
around maps and lists, even though in the core interfaces,
the ipld.NodeAssembler interface now says "Begin" for maps and lists.
This is because the fluent.NodeAssembler approach, with its use of
closures, really does do the whole operation in one swoop.

(It's amusing to note that this change includes finally nuking some
fairly old "REVIEW" comment blocks from the old fluent package which
regarded the "knb" value and other such sadness around typed recursion.
Indeed, we've finally reviewed that: and the answer was indeed to do
something drastically different to make those recursions dance well.)

=== selectors ===

Selectors essentially didn't change as part of this diff.  Neat.

(They should get a lot faster when applied, because our node
implementations hit a lot less interface boxing in common operations!
But the selector code itself didn't need to change to get the gains.)

The 'selector/builder' helper package *did* change a bit.
The changes are mostly invisible to the user.
I do have some questions about the performance of the result; I've got
a sneaking suspicion there's now a bunch of improvements that might be
easier to get to now than they would've been previously.  But, this is
not my quest today.  Perhaps it will deserve some review in the future.

The 'selector/builder' package should be noted as having some
interesting error handling strategies.  Namely, it doesn't.
Any panics raised by the fluent package will just keep rising; there's
no place where they're converted to regular error value returns.
I'm not sure this is a good interface, but it's the way it was before
I started passing through, so that's the way it stays after this patch.

ExploreFieldsSpecBuilder.Delete disappears.  I hope no one misses it.
I don't think anyone will.  I suspect it was there only because the
ipld.MapBuilder interface had such a method and it seemed like a
reasonable conservative choice at the time to proxy it; now that the
method proxied is gone, though, so too shall go this.

=== traversal ===

Traversal is mostly the same, but a few pieces of config have new names.

`traversal.Config.LinkNodeBuilderChooser` is now
`traversal.Config.LinkTargetNodeStyleChooser`.
Still a mouthful; slightly more accurate; and reflects that it now
works in terms of NodeStyle, which gives us a little more finesse in
reasoning about where NodeBuilders are actually created, and thus
better control and insight into where allocations happen.

`traversal.NodeBuilderChooser` is now
`traversal.LinkTargetNodeStyleChooser` for the same reasons.

The actual type of the `LinkTargetNodeStyleChooser` now requires
returning a `NodeStyle`, in case all the naming hasn't made it obvious.

=== disappearing node packages ===

A couple of packages under 'impl/*' are just dropped.

This is no real loss.  The packages dropped were Node implementations
that simply weren't done.  Deleting them is an increase in honesty.

This doesn't mean something with the same intentions as those packages
won't come back; it's just not today.

--- runtime typed node wrapper disappeared ---

This one will come back.  It was just too much of a pain to carry
along in this diff.  Since it was also a fairly unfinished
proof-of-concept with no downstream users, it's easier to drop and
later reincarnate it than it is to carry it along now.

=== linking ===

Link.Load now takes a `NodeAssembler` parameter instead of a
`NodeBuilder`, and no longer returns a `Node`!

This should result in callers having a little more control over where
allocations may occur, letting them potentially reuse builders, etc.

This change should also make sense considering how codec.Unmarshal
now similarly takes a NodeAssembler argument and does not return
a Node value since its understood that the caller has some way to
access or gather the effects, and it's none of our business.

Something about the Link interface still feels a bit contorted.
Having to give the Load method a Loader that takes half the same
arguments all over again is definitely odd.  And it's tempting to take
a peek at fixing this, since the method is getting a signature change.
It's unclear what exactly to do about this, though, and probably
a consequential design decision space... so it shall not be reopened
today during this other large refactor.  Maybe soon.  Maybe.

=== the dag-json codec ===

The dag-json codec got harder to implement.  Rrgh.

Since we can't tell if something is going to become a Link until
*several tokens in*, dag-json is always a bit annoying to deal with.
Previously, however, dag-json could still start optimistically building
a map node, and then just... quietly drop it if we turn out to be
dealing with a link instead.  *That's no longer possible*: the process
of using NodeAssembler doesn't have a general purpose mechanism for
backtracking.

So.  Now the dag-json codec has to do even more custom work to buffer
tokens until it knows what to do with them.  Yey.

The upside is: of course, the result is actually faster, and does fewer
memory allocations, since it gathers enough information to decide what
it's doing before it begins to do it.
(This is a lovely example of the disciplined design of NodeAssembler's
interface forcing other code to be better behaved and disciplined!)

=== traversal is faster ===

The `BenchmarkSpec_Walk_MapNStrMap3StrInt/n=32` test has about doubled
in speed on the new `basicnode` implementation in comparison to the old
`ipldfree.Node` implementation.

This is derived primarily from the drop in costs of iteration on
`basicnode` compared to the old `ipldfree.Node` implementation.

Some back-of-the-envelope math on the allocation still left around
suggest it could double in speed again.  The next thing to target
would be allocations of paths, followed by iterator allocations.
Both are a tad trickier, though (see a recently merge-ignore'd
commit for notes on iterators; and paths... paths will be a doozy
because the path forward almost certainly involves path values
becoming invalid if retained beyond a scope, which is... unsafe),
so certainly need their own efforts and separate commits.

=== marshalling is faster ===

Marshalling is much faster on the new `basicnode` implementation in
comparison to the old `ipldfree.Node` implementation.
Same reasons as traversal.

Some fixes to marshalling which previously caused unnecessary
allocations of token objects during recursions have also been made.
These improve speed a bit (though it's not nearly as noticeable as the
boost provided by the Node implementation improvements to iteration).

=== size hints showed up all over the place ===

The appearance of size hint arguments to assembly of maps and lists
is of course inevitable from the new NodeAssembler interface.

It's particularly interesting to see how many of them showed up in
the selector and selectorbuilder packages as constants.

And super especially interesting how many of them are very small
constants.  44 zeros.  86 ones.  25 twos.  9 threes.  2 fours.
(Counted via variations of `grep -r 'Map(.*4, func' | wc -l`.)
It's quite a distribution, neh?  We should probably consider some
more optimizations specifically targeted to small maps.
(This is an unscientific sample, and shifted by what we chose to
focus on in testing, etc etc, but the general point stands.)

`-1` is used to indicate "no idea" for size.  There's a small fix
to the basicnode implementations to allow this.  A zero would work
just as well in practice, but using a negative number as a hint to
the human seems potentially useful.  It's a shame we can't make the
argument optional; oh well.

=== codegen ===

The codegen packages still all compile... but do nonsensical things,
for the moment: they've not been updated to emit NodeAssembler.

Since the output of codegen still isn't well rigged to test harnesses,
this breakage is silent.

The codegen packages will probably undergo a fairly tabula-rasa sweep
in the near future.  There's been a lot of lessons learned since the
start of the code currently there.  Updating to emit the NodeAssembler
interface will be such a large endeavor it probably represents a good
point to just do a fresh pass on the whole thing all at once.

--------

... and that's all!

Fun reading, eh?

Please do forgive the refactors necessary for all this.  Truly, the
performance improvements should make it all worth your while.

Previously it was in the 'impl/typed' package, next to the
runtime-wrapper implementation of the interface.  This was strange.

Not only should those two things be separated just on principle,
this was also causing more import cycle problems down the road:
for example, the traversal package needs to consider the *interface*
for a schema-typed node in order to gracefully handle some features...
and if this also brings in a *concrete* dependency on the
runtime-wrapper implementation of typed nodes, not only is that
incorrect bloat, it becomes a show stopper because (currently, at
least) that implementation also in turn transitively imports the
ipldfree package for some of its scalars.  Ouchouch.

So.  Now the interface lives over in the 'schema' package, with all
the other interfaces for that feature set.  Where it probably always
should have been.

('typed.Maybe' also became known as 'schema.Maybe', which... does not
roll off the tongue as nicely.  But this is a minor concern and we
might reconsider the naming and appearance of that thing later anyway.)

The readme hadn't seen an update for quite a long time, so it was just
overdue for it.  I think the comments about where to expect changes
at this point are practically accurate and now are also stated.

The Node interface, despite being so central to the entire system,
was missing a doc block on the type as a whole!  It now has one.
(I'd like to continue to iterate on this and have it do more linking
out to ipld docs for some of the more conceptual parts, but we've
got a lot of work to do on that content as well, so, for now just
doing it here is better than not having it.)
Signed-off-by: Eric Myhre <hash@exultant.us>

(At long last!  These child-builder methods are a step that was known
to be needed for some time now, but I've intentionally been pushing off
the implementation of it until we finally reached some *other* piece of
functionality that would depend on it and force the issue.  Finally,
that's happened: that issue is unmarshalling into natively-typed
codegenerated nodes, and that's now.  Woo!)

(Though the current focus of this is for natively-typed codegen'd nodes,
if we put further effort into reflective-bind node implementations,
they'll also lean heavily on these child-builder-getters for internally
tracking the correct `reflect.Type` to create new values of -- very
similar to what our schema-typed things are doing, just with the Golang
type system instead of our schema types.)

The child-builder getter methods more or less explain themselves.
They yield a new NodeBuilder that's correctly specialized for child
nodes in recursive structures.  This is necessary for both keys and
values in maps, and for values in lists.  For values in lists and maps,
getting the child-builder requires takes a parameter -- this is so
typed nodes (namely, structs; but some unions will also lean on this)
may have discriminated contents that differ per key or index.

The BuilderForValue functions are able to take primitive strings and
ints as parameters rather than Node, because all uses that have
discriminated results are places where complex keys are not acceptable.
Therefore primitives are fine, and preferred since it avoids boxing.

The 'free' node implementation is updated to include this feature,
as are codegenerated nodes.
(The runtime wrapper typed node implementations have partial support,
but stubbed methods where the path forward is clear but the
implementation effort nontrivial and not currently on-priority-path.)

Unmarshalling now uses these child-builder-getters to correctly handle
the passing down of constraints and typeinfo.  This addresses several
TODO's that have been in the unmarshalling code for aeons -- hooray!
(Somewhat remarkably, our solution here is much better than the one
proposed in those ancient TODO's -- we actually got this done *without*
direct abstraction-breaking examination for typed nodes.  Nice!)

Unmarshalling tests are also in this same diff.
There's even a wee little benchmark using a snippet of JSON as fixture.
This is the first time we see unmarshalling and marshalling end-to-end
connected with codegen'd nodes.  This is very exciting!

There's still some questions to be answered about the most correct
(and most performance-friendly) place to put error handling against
asks for a child NodeBuilder with an invalid key or index, which is
a very real invalid state that's reachable for typed nodes that are
structs.  Comments about that are inline in the diff.  We'll probably
have to come back to that soon, but I'm gonna let it stew on the
back burner for a bit.  Currently, panics are used, but this may not
be acceptable ergonomics.

---

It's somewhat effortful to even detail how many thoughts about
performance and the future optimization potentials go into this diff.
Some comments I had in the area of the child-builder specialization
functions included concerns on:

- where common-subexpression-elimination will and won't apply
- where inlining is possible vs facing function call stack shuffle overhead
- ... as well as how that affects common-subexpression-elimination
- ... as well as how that affects escape analysis and shifts to heap
- whether an isDiscriminated property will make any of these things better
- can BuilderForValue hang onto a builder, boxed into interface already, when appropriate?
- ... for the maps case, should amortize in a way comparable to isDiscriminated, yes?  verify.
- ... can we do that without the builder keeping another two words of memory just... around?  i don't think so.  question is if it pays for itself.
- question: do zero value no-fields structs get a bonus?  reading runtime/iface.go -- doesn't look like it.  but needs confirmation.
- ... revised statement: they do, it's just nonobvious.  iface.go doesn't have a specialization, but the mallocgc call hits a special path internally for zero, and then the typedmemmove call 'coincidentally' hits its "src == dst" short-circuit, thus also being fast.

... all in all, as many of these as possible of these concerns have
been considered and this design should be optimization-friendly;
some of them are bucketed into "we'll see", because we need to build
nontrivial programs to see how significant the needs are, as well as
to see how clever the compiler can get with what we've already done.

There are some possible alternative ways we might re-engineer the
builders in the future to make them more performance-friendly.
In particular, the fact that many builders carry a previous value
with them in anticipation of one of the 'Amend' calls -- which is
not necessarily going to be used! -- is a potential obstruction to
optimization, since it makes many structures go from zero to
more-than-zero size, and that hits significantly different paths
in the runtime with very different performance characteristics.
However, that is a bit much to change today; so the thought lives
here as a note for potential future work.

Adding a `BuilderForValueIsDiscriminated() bool` method later seems
still seems on the table, but since it wouldn't require substantial
restructurings or headaches, can be deferred until benchmarks show
us exactly how much it matters.
(A single `type ChildBuilders interface { Style() Complexity; ... }`
with some enum for `Compleixty` resembling
`SimpleList | SimpleMap | DiscriminatedMap | DiscriminatedList` might
also be a tempting way to go about this.)

---

An alternative design considered that deserves a quick note: we
could've added a `ChildBuilders()` method to the MapBuilder and
ListBuilder, and attached the further getter methods there.
This might still be viable, if we found that there are more methods
involved in the future and we want to group them: it *should* always
land on the zero-fields struct path, which means it can be done
without hitting an expensive malloc.  However, at present this doesn't
seem warranted: we don't have enough methods to make it feel important
(especially after the recognition that Node variants of methods aren't
needed in addition to the primitive args variants, described above).

---

Whew.

Lines of code in diff does not correlate to hours of thought required.

Glad to have this landing.  Even performance minutae aside,
there was a significant period of time where I was terrified that all
these abstractions were going to shatter magnificently when it came
time to do the final end-to-end unification of all this massive arc
of work.  But now it's done.  And it works.  Whew.

Next: more fleshing out of more types; perhaps more benchmarks; and
also it's time to do some more drafts of the native accessors and
builders.  Some of that already has been done in parallel in gists
while this diff was incubating, but it's time to commit it too.

Lacking these has been an oversight.

At the data model level, appending basically can't go wrong.
As a result, we got away this this oversight so far.

The grace period is over, now.

At the schema level, this is not true -- type constraints can certainly
cause some modification to end in errors!  For lists, inconsistent
types can cause errors; for struct-with-tuple-representation, we can
encounter length limits and even distinct constraints per index!
Signed-off-by: Eric Myhre <hash@exultant.us>

In thinking about how to make a 'bind' (aka, reflect and atlases) Node
implementation, some interesting stuff comes up: despite being all
one concrete Node implementation, it needs specialization (for the
reflect.Value bound inside, specifically); and 'bind' nodes don't
*necessarily* have a schema and a typed.Node associated with them,
so the existing comments about specializing using Type info don't
actually apply.  So!  What do?

These comments are a tad hypothetical (and have been on my uncommitted
working tree for a while, so hopefully they're not *too* stale; I just
want to get them in history somewhere rather than keep dancing my
patches around them)... but there's almost certainly something to
address somewhere in this area.

As detailed in comments a few commits ago, this is part of a big, big
roll towards keeping linking details far enough off to one side that
one can actually use most of the IPLD system without forming an
explicit compile-time dependency on any linking features (until, of
course, one uses the linking features).

This is a surprisingly small diff, because... well, because most of
the *interesting* features around linking simply weren't implemented
yet, and at this point everything that is has already been isolated
in the new cidlink and related encoding packages.
"CID" was *already* just a semantic placeholder that meant "eh, link".
Signed-off-by: Eric Myhre <hash@exultant.us>

This is the first commit going down a long and somewhat dizzying prerequisite tree:

- For graphsync (an out-of-repo consuming project) we need selectors
- For Selectors we need traversal implemented
- For Traversal implementations we need link loaders [‡]
- For link loading we need all deserialization implemented
- (and ideally, link creation is done at the same time, so we don't get surprised by any issues with the duals later)
- and it turns out for deserialization, we now have some incongruities with the earlier draft at MapBuilder...

So we're all the way at bugfixes in the core ipld.MapBuilder API.  Nice.

([‡] Some of those jumps are a little strained.  In particular, traversal doesn't
*in general* need link loaders, so we might choose a very different implementation
order (probably one that involves me having a lot less headaches)... *except*,
since our overall driver for implementation order choices right now is graphsync,
we particularly need traversals crossing block boundaries since we're
interested in making sure selectors do what graphsync needs.  Uuf.)

What's the MapBuilder design issue?  Well, not enough error returns, mostly.
We tried to put the fluent call-chaining API in the wrong place.

Why is this suddenly an issue now?  Well, it turns out that properly genericising
the deserialization needs to be able to report error states like invalid
repeated map keys promptly.

Wait, didn't we even *have* deserialization code before?  Yes, yes we did.
It's just that that draft was specialized to the ipldfree.Node implementation...
and so it doesn't hold up anymore when we need it to work in general traversal.

Okay, so.  That's the stack depth.

With all that in mind...

This diff adds more error return points to ipld.MapBuilder, and maintains the
fluent variant more closely matching the old behavior (including the
call-chaining style), and fixes tests that relied on this syntax.

Duplicate keys rejection is also in this commit.  I thought about splitting it
into further commits, but it's so small.  (We may actually need more work in
the future to enable Amend+(updating)Insert, but that's for later; perhaps
an Upsert method; whatever, I dunno, out of scope for thought at the moment.)

And then we'll carry on, one step at a time, from there.  Whew.

---

Sidebar: also dropping MapBuilder.InsertAll(map[Node]Node) from the interface.
I think this could be better implemented as a functional feature that works
over a MapBuilder than being a builtin, and we should prefer a trim MapBuilder.
And might as well drop it now rather than bother fixing it up just to remove later.

---

ipld.ListBuilder also updated to no longer do a call-chaining style API, while
fluent.ListBuilder continues to do so.  This is mainly for consistency;
we don't have the same potential for mid-build error conditions for lists
as we do with maps, but ipld.ListBuilder and ipld.MapBuilder should be similar.

---

Aaaaand one more!  NodeBuilder.{Create,Append}{Map,List}() have ALL been
updated to also return errors.  Previously, the append methods had an error
state if you used them when the NodeBuilder was bound to a predecessor node
of an unmatching type, but they just swallowed them into the builder and
regurgitated them (much) later; we're no longer doing this.  Additionally,
it's occurred to me that *typed* builders -- while not so much a thing, yet,
certainly a thing that's coming -- will even potentially error on CreateMap
and CreateList methods, according to their type constraints.  So, jump that now.

...

Yeah, basically a whole tangle of misplaced optimism about error paths in
NodeBuilder and its whole set of siblings has been torn through at once here.
Bandaid ripping sound.
Signed-off-by: Eric Myhre <hash@exultant.us>

We now have nice, immutable nodes... as soon as we deprecate and remove
the MutableNode stuff.

All the tests pass.

A few methods for bulk update are still stubbed... as is delete;
seealso the comment about that in the API file.

NodeBuilders needed replication in the fluent package as well.
This is perhaps a tad frustrating, as well as borderline surprising
(because "how can sheer memset have errors anyway?"), but the ability
for node building to reject invalid calls will become relevant when
typed.Node is in play and has to enforce type rules while still
supporting the generic methods.

The builder syntax for maps and lists is based on chaining.
This works... okay.  I'm not as satisfied with the visual effect of it
as I'd hoped.  There'll probably be more experiments in this area.
Things nest -- critical success; but the indentation level doesn't
quite match what we'd contemporarily consider natural flow.

But look at the diff between the mutableNode test specs and the new
immutable&fluent nodeBuilder test specs!  The old ones were nuts:
temp variables everywhere for construction, total visual disorder, etc.
The new NodeBuilder is much much better for composition, and doesn't
need named variables to save fragments during construction.
More refinement on map/list builders still seems possible, but it's
moving in the right direction.
Signed-off-by: Eric Myhre <hash@exultant.us>

Specifically in regards to typed nodes, which are the main consumers of
this that I imagine right now (though we may find others in the
future).

Typed nodes which are implemented by *native* concrete types (e.g.
presumably by codegen -- though we haven't implemented any of this yet)
will *especially* hit this detail: they'll return builders that produce
new instances of their own concrete native type!

And all of the build methods that actually produce a new Node now also
have the option to return an error.  This follows from the docs;
typed nodes actually can and will reject some attempts at invalidly-
typed creation!

We'll probably want fluent wrappers of NodeBuilder as well, as a result
of these error returns.  I'll defer that until it's forced.
Lazy/just-in-time evaluation of the programmer :P
Signed-off-by: Eric Myhre <hash@exultant.us>

This will replace, deprecate, annihilate, obviate, oblivate, and
generally nuke the MutableNode interface.  MutableNode was a bad, bad
idea and made many things terribly complicated.  Immutable interfaces
are shaping up much, much better and I'm excited to move NodeBuidler
forward.

I tried for some time to figure out a useful way to do a builder
pattern in the fluent package, which would work *upon* the MutableNode
interface... but all attempts to do that ended poorly with code that
was both messy internally and complex and error prone for callers.
I've given up all such attempts.

It also seems to be true that we should have NodeBuilder *instances*
which may be per Node.  This wasn't obvious at first, but I think it'll
let us carry a lot of important information in a low-fuss way, and it
solves a *lot* of problems that cropped up when trying to implement
larger scale generic transformation methods on Node graphs (namely, the
frequent need to be able to create a new Node in the middle of a
process; and handing down a factory method to each of those points was
horrifically verbose and caused complexity that was not essential).
(Unfortunately, I can't really point at examples of *how* bad this got,
because I've never committed any of those research spikes; fortunately,
no one else will now ever have to *see* that mess, since we've got
better solutions figured out.)

MutableNode will go away in the next handful of commits, but I wanted
to land the new one first in a smaller diff.  Removing MutableNode
may be a fair amount of messy work, because of how it's used in nearly
all of our test fixture setup to date!  Uffdah.

(Node will get a GetBuilder method (or something of similar intent but
better name) at the same time we get rid of MutableNode; I'm eliding
it from this commit for the same reasons about diff size avoidance.)
Signed-off-by: Eric Myhre <hash@exultant.us>