GitLab

If you've been following along for a while now, you don't need to see
the benchmarks to know what's coming.  The long story short is:
allocations are the root of all evil, and we got rid of some, and now
things are significantly faster.

Here's the numbers:

basicnode (just for a baseline to compare to):

```
BenchmarkMapStrInt_3n_AssembleStandard-8         1988986               588 ns/op             520 B/op          8 allocs/op
BenchmarkMapStrInt_3n_AssembleEntry-8            2158921               559 ns/op             520 B/op          8 allocs/op
BenchmarkMapStrInt_3n_Iteration-8               19679841                67.0 ns/op            16 B/op          1 allocs/op
BenchmarkSpec_Marshal_Map3StrInt-8               1377094               870 ns/op             544 B/op          7 allocs/op
BenchmarkSpec_Marshal_Map3StrInt_CodecNull-8     4560031               278 ns/op             176 B/op          3 allocs/op
BenchmarkSpec_Unmarshal_Map3StrInt-8              368763              3239 ns/op            1608 B/op         32 allocs/op
```

realgen, previously, using fcb:

```
BenchmarkMapStrInt_3n_AssembleStandard-8         4293072               278 ns/op             208 B/op          5 allocs/op
BenchmarkMapStrInt_3n_AssembleEntry-8            4643892               259 ns/op             208 B/op          5 allocs/op
BenchmarkMapStrInt_3n_Iteration-8               20307603                59.9 ns/op            16 B/op          1 allocs/op
BenchmarkSpec_Marshal_Map3StrInt-8               1346115               913 ns/op             544 B/op          7 allocs/op
BenchmarkSpec_Marshal_Map3StrInt_CodecNull-8     4606304               256 ns/op             176 B/op          3 allocs/op
BenchmarkSpec_Unmarshal_Map3StrInt-8              425662              2793 ns/op            1160 B/op         27 allocs/op
```

realgen, new, improved:

```
BenchmarkMapStrInt_3n_AssembleStandard-8         6138765               183 ns/op             129 B/op          3 allocs/op
BenchmarkMapStrInt_3n_AssembleEntry-8            7276795               176 ns/op             129 B/op          3 allocs/op
BenchmarkMapStrInt_3n_Iteration-8               19593212                67.2 ns/op            16 B/op          1 allocs/op
BenchmarkSpec_Marshal_Map3StrInt-8               1309916               912 ns/op             544 B/op          7 allocs/op
BenchmarkSpec_Marshal_Map3StrInt_CodecNull-8     4579935               257 ns/op             176 B/op          3 allocs/op
BenchmarkSpec_Unmarshal_Map3StrInt-8              465195              2599 ns/op            1080 B/op         25 allocs/op
```

So!  About 150% improvement on assembly between gen with fcb and our new-improved no-callback system.

And about 321% improvement in total now for codegen structs over the basicnode map.

That's the kind of ratio I was looking for :)

As with all of these measurements: these will also get much bigger on bigger corpuses.
Some of the improvements here are O(n) -> O(1), and some apply even more heartily in deeper trees, etc.
But it's telling that even on very small corpuses, the impact is already huge.

Results: mixed.

The good news:

The codegen works.

We were able to wire it to the standard benchmarks (!  great success).

It is flat out faster than any other implementation to date.

The not-so-good news:

It's not _as_ fast as I wanted >:(

The strategy of using a callback ("fcb") for transmitting 'finished'
signals from child assemblers to their parents causes an allocation.

That single source of allocations turns out to be one of the most
dominant things on the pprof of the benchmark.  (And it would
absolutely be even worse if 'N' was larger than '3' -- an alloc here
shifts us from an O(1) to O(n) on fields.)

So.  Good to know!  Having end to end benchmarks is VERY exciting.

And we're going to have to go back to the drawing board on that
part involving a callback.

This diff is pretty fun.  It's our first alternative representation,
and it all works out nicely (no internal syntactical complications
encountered or any other unexpected unpleasantness).

It's also our first representation that involves potentially recursive
destructuring work over a scalar!  So, you can see the new 'construct'
method conventions appearing to handle that.  Works out neatly.
This kind of recursive destructuring happens all within the span of
processing one "token" so to speak, so naturally it can work without
any stateful machinery.

Some utility functions are added to the mixins package.
(It's sort of betraying in the name of the package, but, well,
it's an extremely expedient choice.  See comments about import
management.  tl;dr: consistency makes things easier.)

Tests for a recursive case of this will be coming soon, but requires
addressing some other design flaws with the AdjunctConfig maps.
(StructField is... not a good key.  It's not always hashable... such
as when the StructField.Type field is inhabited by TypeStruct.)
Easy enough to fix, just not going to cram it into this commit.

The way null and the 'fcb' are handled here differs from previous
generators: here, we *always* have an 'fcb', and just make a special
one for the root builder.  This is... well, it works.  It was an
attempt to simplify things and generate fewer method overrides, and
it did.  However, I'm not going to dwell on this too long, because...

The 'fcb' system is not working out well overall for other reasons:
it's causing costly allocations.  (Taking a function pointer from
a method requires at least two words: one for the function pointer
and one for the value to apply it on.  That means an allocation.)
So a serious rewrite of anything involing the 'fcb' strategy is needed.

And that is going to be a little tricky.  The 'fcb' idea was itself
a trying-slightly-too-hard-to-be-clever attempt to avoid an alternative
solution that involves generating additional types per distinct child
value slot (and I'm still unwilling to pursue that one -- it suggests
far too many types).  The next best idea I have now seems to involve a
lot of pointers into other assembler's state machines; this will surely
be a bit touchy.  But no worse than any of the rest of all this, I
suppose: it's *all* "a bit touchy".  Buckle up for fun diffs ahead.)

So, considering these 'fcb' notes, this feels a bit mixed...
"Two steps forward, one step back", so to speak.  Still: progress!
And it's very exciting that we got through several new categories of
behavior without hitting any other new roadbumps.

The label used to advance over absent optionals is a compile-time error
if not referenced, so we have to branch generation for that.

I'll want this momentarily for doing Generate from other packages.
(I might not actually commit anything relating to this for a while,
but secretly, I'm playing with it.)

Correct a half-dozen laxnesses in path handling while at it.

Output is fairly fabulous.  Really happy with this.

Diff size is nice.  Took the opportunity to do some cleanups and the
net result is 193 insertions and 351 deletions counted by line.

Most importantly, though: running 'go test .' in the gengo package
actually generates, compiles, and tests **everything**.

The test file inside the "_test" dir that you previously had to jankily
run manually is gone.  Hooray!

And already, we've got three distinct packages being generated and
tested.  (Try 'diff _test/stroct*/tStroct.go'.  It's neat.)

The time overhead is acceptable so far.  The total time is up to 0.9sec
on my current machine.  Not as bad as feared.

Overall: nice.  I think this reduces the test friction to a point that
will significantly enable further progress.

'go test' just really wasn't designed for this.  There's no first class
API-driven way to interact with it at all.  Even the 'go test -json'
capabilities, despite being built-in, appear to be strap-ons rather
than logically central consistent abstractions.

Where things can be parsed at all (and in general, they can't -- not
without significant potential for ambiguity slipping in from some
angle or another), trying to output them again in a normalized form
is seriously tricky business: a great deal of re-buffering is required.
(This diff doesn't have it: I started off far too optimistic about the
simplicity of the whole thing, and am putting it down rather than
continue.  I get the feeling I could tumble down the rabbit hole quite
some time and still only ever be *approaching* correctness
asymptotically -- never actually *getting* there.)

In addition, all the problems enumerated in the previous commit
('-v' needs to be passed down; '-run' is more or less impossible; and
all the sadness about closures and more helper files split across whole
package boundaries just for maximum distraction) are still here.

Yeah... let's... let's put this one back in the box.
I'm going to merge-ignore this and keep the plugin approach instead.
As much as I *really* don't want gcc as a test dep, all this stuff...
this seems worse.  (And maybe, someday, Go can be improved so plugins
don't have the gcc dep.  I'm going to hope for that.)

In the parent commit, we tried using plugins.  Turns out there's one
big, big drawback to plugins.  Building one invokes 'gcc'.
Works; as long as you... have gcc, and don't mind that having that as
a dependency that you now have to track and potentially worry about.
I don't consider that minor.

So, okay.  What's using 'go test' child invocations look like?

Well, bad.  It looks... bad.

The output is a mess.  Every child process starts its output as if its
a top level thing.  Why this happens is perfectly understandable and
hard to be mad at, but nonetheless the result is maddeningly illegible.
Cleaning this up might be possible, but will require some additional
effort to be invested.

There's some more irritating problems than that, though.
Notice the entirely new package that's sprouted.

Not being able to use closures in the test assertions is unfortunate.

Having to put the test assertions in *entirely different files* than
their setup... now that's really painful.

(And yeah, sure, we can move the setup out to another package, too.
It's not pleasing, though.  Then what of the test is actually in the
package it's testing?  The entrypoint?  So then, I'd end up editting
the test setup and assertions in one package (but running tests on
that package would actually no-op; syke!) and then have to switch to
the other package to actually run it?  There's no angle this can be
sliced that results in any sort of _nice_.)

Flags like '-v' aren't inherited now, either.  Hooray.
We could try to hack that in, I suppose.  Detect '-test.v' arg.
But it's just another thing that needs patching up to be shipshape.

Speaking of which, '-run' arg isn't even *remotely* manageable
without massive effort.  The thing can contain regexps, for goodness
sake -- how can we possibly semantically modify those for passdown?

I'm not sure where to go with this.  Depending on gcc in tests is
undesirable.  But all these other effects from trying to use 'go test'
this way seem even *more* undesirable.

Using golang's plugin feature, we can... well, *do* this.

To date, testing codegen has involved running the "test" in the gen
package to get it to emit code; and then switching to the emitted
package and _manually_ running the tests there.

Now, running `go test` in the gen package is sufficient to do
*everything*: both the generation, and the result compiling,
and we can even write tests against the interfaces and run those,
all in one step.

There's also lots of stuff that becomes possible now that we can easily
generate multiple separate packages with various codegen outputs:

- Overall: everything is granular.  We can test selections of things,
  rather than needing to have everything fall into place at once.
- Generally more organized results.
- We can more easily inspect the size of generated code.
- We can more easily inspect the size of the compiled result of gen!
  (Okay, not really.  I'm seeing a '.so' file that's 4MB is coming out
  from 200sloc of "String".  I don't think that's exactly informative.
  Some constant factor is thoroughly obscuring the data of interest.
  Nice idea in theory though, and maybe we'll get there later.)
- We can diff the generated type for variations in adjunct config!
  (Probably not something that will end up tested, but neat to be able
  to do during dev.)

Doing this with go plugins seemed like the neatest way to do this.
It's certainly not the only way, though.  And in particular, I will
confess that this will probably make developing from a windows host
pretty painful: go plugins aren't supported on windows.  Mind,
this doesn't mean you can't *use* codegen or its results on windows.
It just means the tests won't work.  So, someone doing development
_on the codegen itself_ would have to wait for the CI server to run
the tests on their behalf.  Hopefully this is survivable.

(There's also a fun wee wiggle in that loading a plugin has the
requirement that it be built with the same "runtime".  The definition
of "runtime" here happens to include whether or not things have been
built in "race" mode.  So, the '-race' flag disappears from our CI
config file in this diff; otherwise, CI will get the (rather confusing)
error "plugin was built with a different version of package runtime".
This isn't really worrying to ditch, though.  I'm... not even sure why
the '-race' was in our CI script in the first place.  Must've arrived
via cargo cult; we don't _have_ any concurrency in this library.)

An alternative way to go about all this would be to have the tests for
gen invoke `go test` (rather than `go build` in plugin mode) on each of
the generated packages.  It strikes me as similar but worse.
We still have to invoke the go tools from inside the test;
we'd have *more* work to do to either copy tests into the gen'd package
or else generate calls back to the parent package for test functions
(which still have to be written against interfaces, so that they can
compile even when the gen isn't done, as it indeed isn't when you
freshly check out the repo -- exact same as with the plugin approach);
and in exchange for the extra work, we get markedly worse output
('go test' doesn't nest nicely, afaict), and we can't separate the
compiling of the generated code from the evaluation of tests on it,
and we'd have no possibility of passing information via closures should
we wish to develop table-driven tests where this would be useful.
tl;dr: Highest cost, uglier, and worse.

No matter which way we go about this, there *is* a speed trade-off.
Invoking the compiler per package adds at least a half second of time
for each package, in practice.  Worth it, though.

And on the off chance that this plugin approach does burn later,
and we do want to switch to child process 'go test' invocations...
the good news is: we shouldn't actually have to rewrite very much.
The everything-starts-from-NodeStyle-and-tests-against-Node work is
exactly the same for making the plugin approach work, and will
trivially pivot to working fine in for child 'go test' approaches,
should we find it necessary to do so in the future.  So!  With our
butts covered: a plugin'ing we shall go!

Some of the code here still needs cleanup; this is a proof of concept
checkpointing commit.  (The real thing probably won't have such
function names as "TestFancier".)  But, we do get to see here:
plugins work; more than one in the process works; and they work even
when the same type names are in the generated packages.  All good.

Some touches to ImplicitValue came along for the ride, but aren't
exercised yet.

Tests are getting unwieldy.  I think something must be done about
this before proceding much further or it's going to start resulting
in increasingly significant velocity loss.

Still have a lot of uncertainty to resolve around nullable and optional
in general.  But writing that up elsewhere -- trying to treat it from
the spec angle without getting the implementation too mixed up in it.

I was particularly worried about trailing optionals.  Happily,
they appear to work fine.

Representation iterators and smooth stopping included.

Starting to wonder how best to organize these tests to continue.
333 lines already?  Questionable scalability.

I started doing double-duty in tests to keep the volume down:
the block for nullables tests both 'nullable' and 'nullable optional';
and the optionals similarly.  Will make failures require more careful
reading to discern, but probably a fine trade.

I'm almost a little staggered.  We've got structures with maybes
both using pointers and not, and everything seems fine.

A few fixes were necessary, but they were mostly "d'oh" grade.
(The finishCallback logic is a bit hairy, but appears correct now.)

More cases for more variations in presence coming up next.

Sanity check level: gen result compiles.

Next: time to target tests at all this jazz that actually exercise
and run the generated code.

Easier than previous commit message seemed to think.

Since we already have finishCallback functions in play in any scene
where maybes can also be in play, we can just make those responsible
for copying out a pointer from the child assembler to the parent value.
That makes the child assembler able to create a new value late in
its lifecycle and still expect it can land in a proper home.

Tests needed badly; this is *oodles* of edge cases.
Unrelated fix needed first.  (Might make that elsewhere and rebase
this to include that, to reduce the carnage ever so slightly.)

Fix many issues with maybes; adjunct config for if maybe is implemented using a pointer; attempt the finishCallback system for reusable child assemblers.

This... almost appears to be on a dang nice track.

Except one fairly critical thing.  It doesn't work correctly if your
maybe IS implemented as containing a pointer.

Because that pointer starts life as nil in the parent structure.

And that's hard to fix.

We can't have a pointer to a pointer in the assembler;
that'd cause the type bifructation we've been trying to avoid.
(We can give up and do that of course; it would be correct.
Just... more code and larger final assembly size.
And if we did this, a lot of this diff would be rewritten.)

We could have the parent structure allocate a blank of the field,
and put a pointer to it in the maybe and also in the child assembler.
Except... this is a wasted allocation if it turns out to be null.

Rock and hard place detected in a paired configuration.
Might have to back out of this approach entirely.  Not sure.

We'll see how this works out.

Lots of tasty bitshuffling in this commit.

Remaining: creating, embedding, and returning child value assemblers.
This might involve a full type per field: doing so would be direct,
have pretty excellent verbosity in debugging symbols,
and pointers back to parent suffer no interface indirection;
overall, it's probably going to have the fastest results.
However, it would also mean: we can't save resident memory size if we
have more than one field in a struct that has the same type;
and we we can't avoid increasing binary size if the same types are used
as fields in several places.
Going to pause to think about this for a while.

This cleans up a lot of stuff and reduces the amount of boilerplate
content that's just generating monomorphizing error method stubs.

The nodeGenerator mixins now also use the node mixins.  I don't know
why I failed to do that from the start; I certainly meant to.
It results in shorter generated code, and the compiler turns it into
identical assembly.

(That line kind of says a lot about why this project is tricky, doesn't it.)

Compiles and runs; but the results don't.
Some small issues; some big issues.  Just needed a checkpoint.

It's feeling like it's time to deal with breaking down the assembler
generators in the same way we did for all the node components, which
is going to be kind of a big shakeup.

I *think* the notes on Maybes are now oscillating increasingly closely
around a consistent centroid.  But getting here has been a one heck of
a noodle-scratcher.

In research: I found that there are more low-cost ways to switch which
methods are available to call on a value than I thought.  Also, these
techniques work even for methods of the same name.  This is going to
improve some code in NodeAssemblers significantly -- there are several
situations where this will let us reuse existing pieces of memory
instead of needing to allocate new ones; even the basicnode package
now already needs updates to improve this.  It's also going to make
returning representation nodes from our typed nodes *significantly*
easier and and lower in performance costs.  (Before finding methodsets
are in fact so feasible, I was afraid this was going to require our
typed nodes to embed yet another small struct with a pointer back to
themselves so we can have amortized availability of value that contains
the representation's logic for the Node interface... which while it
certainly would've worked, would've definitely made me sigh deeply.)
Quite exciting for several reasons; only wish I'd noticed this earlier.

Also in research: I found a novel way to make it (I believe) impossible
to create zero values of a type, whilst also making a symbol available
for it in other packages, so that we can do type assertions, etc,
with that symbol.  This is neat.  We're gonna use this to make sure
that types in your schema package can never be created without passing
through any validation logic that the user applies.

In codegen: lots of files disappear.  I'm doing a tabula rasa workflow.
(A bunch of the old files stick around in my working directory, and
are being... "inspirational"... but everything is getting whitelisted
before any of it ports over to the new commits.  This is an effective
way to force myself to do things like naming consistency re-checks
across the board.  And there's *very* little that's getting zero change
since the changes to pointer strategy and assembler interface are so
sweeping, so... there's very little reason *not* to tabula rasa.)

Strings are reimplemented already.  *With* representations.

Most of the codegen interfaces stay roughly the same so far.
I've exported more things this time around.

Lots of "mixins" based on lessons learned in the prior joust.
(Also a bunch of those kind-based rejections look *much* nicer now,
since we also made those standard across the other node packages.)

Some parts of the symbol munging still up in the air a bit.
I think I'm going to go for getting all the infrastructure in place
for allowing symbol-rename adjunct configuration this time.
(I doubt I'll wire it all the way up to real usable configuration yet,
but it'll be nice to get as many of the interventions as possible into
topologically the right places to minimize future effort required.)

There's a HACKME_wip.md file which contains some other notes on
priorities/goals/lessoned-learned-now-being-applied in this rewrite
which may contain some information about what's changing at a higher
level than trying to track the diffs.  (But, caveat: I'm not really
writing it for an audience; more my own tracking.  So, it comes with
no guarantee it will make sense or be useful.)

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.

This is the last part of the cleanup and cyclic import fix started
in the previous commit.

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.)

rename EmitTypedLinkNodeMethodReferencedLinkBuilder to EmitTypedLinkNodeMethodReferencedNodeBuilder