add a treevert widget

[dankamongmen]

As either its own widget or an extension to multiselect, we ought have a selection widget that allows items to be expanded. Think of your canonical linux/freebsd old-skool installer. I ought be able to select "editors" and have them all select/unselect, or expand "editors" and select from among them. "editors" ought then be collapsible.

Probably this is best done as an extension to multiselector, assuming we can do it with backwards compatibility.

[dankamongmen]

This should probably just be an extension of multiselectors, I am thinking?

Or perhaps we want arbitrary actions to be performable against each item -- think aptitude. Perhaps we want a more general widget altogether, one which allows items to be drawn arbitrarily, or some arbitrary number of drawing callbacks to be used...

[dankamongmen]

Yeah, I think we ultimately want a generalized multiselector, one where you can define multiple states (as opposed to just 2), specifying at a minimum the channels and state glyph. That gets us just about everything we need for a sweet APT clone.

[dankamongmen]

This is a necessary element for Project Aptotheosis, and is the major new work goal of 2.3.0.

[dankamongmen]

So the really fundamental difference here from the other selectors is that one option can affect other options, and one action can affect multiple options. so let's go ahead and make this fully general, which will probably involve some callbacks. i'm thinking:

• you've got some hierarchical structure, a DAG
• that hierarchy might change at runtime, options may come and go
  • i don't think we should be responsible for resorting their lists; such a change ought just result in a new selector
  • this implies creation of a selector of hundreds of thousands of entries must be fast
  • sometimes we'll want a change to the set of options, but not to lose our position/viewstate
• widget ought always draw the relevant options, and manage scrolling/searching
• hierarchies must admit collapse/expand operators
• other operators ought be implemented by client
  • means client must be able to access all subhierarchy quickly
  • means client must be able to change state of many options quickly
• options should be independently styled
  • this is difficult...each hierarchy is its own plane? each entry is its own plane?
  • maybe just provide an n-ary palette?
  • maybe tie this together with status? there are n statuses, and they each have an indicator and channels?

[dankamongmen]

I'm considering various Aptotheosis strategies, and how they might be implemented...

• what if we wanted to display full package(s) info inline? ala line 1 is package AA, line 2 is package AB, line 3 is package AC expanded to show full details below, line 20 is package AD similarly expanded, line 36 is package AE... how would we do this? we basically want to insert an arbitrary plane below any item in the tree, a plane that cannot be acted on (i.e. it is a distinct concept than the hierarchical "items")...that actually sounds quite a bit like a gapless ncreel, quite a bit. hrmm.
  • it kinda breaks down from reels in that we'd have to manage the expanding/collapsing -- ncreel is very single-level-oriented
• what if we wanted to display the first words of the package description on the right side of the line that its corresponding item occupies? ala line 1 is package AA, with the text "u AA 46KBi a poop knife, suitable for insertion into your digital anus to scrape out colon abortions" or something. how would we do this? we don't want to supply the text to the widget -- there could be a lot of it, and resizes complicate things -- but i don't think we want to have to track what's being displayed in the widget ourselves. perhaps a set of per-item callbacks, ala ncreel? not too bad, especially if we can reuse results until they go offscreen....
  • can we generalize this to multiple lines? if so, we seem to get the best of both worlds, though layout is then complicated...

[dankamongmen]

are groups wholly distinct from items? i.e. is it always "Group 1, containing Item 1 and Item 2" or can it be "Item 1, containing Item 2 and Item 3"? is there aliasing? i.e. can we have "Group 1, containing Item 1" and "Group 2, containing Item 1"?

[dankamongmen]

If we do the draw-via-callback outlined above, ought we leave all styling decisions to the callback? Hell, ought we leave all output decisions to the callback? Ought we extend that even to groups/headers?

are groups wholly distinct from items? i.e. is it always "Group 1, containing Item 1 and Item 2" or can it be "Item 1, containing Item 2 and Item 3"? is there aliasing? i.e. can we have "Group 1, containing Item 1" and "Group 2, containing Item 1"?

I think we ought allow aliasing, especially if all we're keeping is a void* to hand to a callback. I don't see problems emerging from it, unless we tried to make too-clever decisions on what all callbacks needed be invoked on a change (basically, if we allow aliasing, and a callback changes the display of an item, it ought be updated everywhere it's being shown).

regarding groups vs items...we're going to be supporting most of the actions one can take on an item on groups. i.e. in aptitude one can press '+' to install a package, or '+' to install all the packages of a group. so the callbacks are going to need to know how to handle this for groups already. that could be implemented via distribution, though... groups must support expand+collapse, whereas items do not need to...hrm. but that could just be implemented as e+c for the groups and a null action for the items en callback...hrmmm....would we ever want to stylize groups? i think maybe so.

so what is this widget really doing? and i think here we can truly take lessons from ncreel, as alluded to earlier. it's providing:

• a scrollable view on a large set of information -- it tracks what's visible and what's not, and supports moving up and down, and to a particular entry
• a hierarchy -- indentation, expanding and collapse of collections, recursive distribution of an action on children
• (optional) borders, headers, footers

the question becomes: do we also want it responsible for display (not shaping) of items/groups? allowing it to is convenient, but delegating it to the client code is much more flexible. it honestly answers most of our design questions thus far. and we could always of course provide a nctree_simple_callback(ncplane* displane, void* curry) that just ncplane_putstr_yx(displane, 0, 0, curry), and you pass a const char* text for all the curries, and then you needn't write any display code.

yessssssssssssssssssssssssssss.

so this answers both of our hypothetical scenaria above: you are passed an ncplane representing all available display space, crap into it, measure the crap, resize the ncplane as needed, move onto the next one, and give it a smaller area in which to crap. within that ncplane, draw whatever you'd like, however you'd like to. it's very much like ncreel, except with a general hierarchy (ncreel is a single level), no gaps, and probably no infinite scrolling (which has proven such a rich source of bugs in ncreel). honestly, this might be strictly more powerful than ncreel (which is somewhat worrying -- ncreel is the most or second-most complex code in Notcurses).

is it going to be fast enough? if we cache while visible, i'd certainly think so. but in the worst case, we're starting up with a full screen worth of items, none of them seen before. that's at most R callbacks on R rows, using at least R ncplanes. Yeah, we can handle that. one annoyance is that when we scroll, we're going to damage almost the entire screen, but that's already the case for ncreel etc. might be a good place to apply terminal-level delete-line and insert-line techniques, though that would require new infrastructure for tracking their validity...anyway, fuck it, we'll be fine.

gaze into your omphalos.

[dankamongmen]

so the final question: are groups distinct from items?

i think no. i think the structure we want to prep the nctree is:

struct treeitem {
  unsigned childrencount;
  struct treeitem* children;
  void* curry;
};

and nctree gets:

unsigned topcount;
struct treeitem* tops;

and that's it. each treeitem has a curry, and some non-negative number of treeitem children. a group has children. a leaf does not. an item may or may not, and the set of items is partitioned into groups and leaves. why? because the issue comes down to one of client-side callback diversity, and--again--responsibility for display. differentiating groups from items is primarily useful because a handler can be implied for groups, whether done by the widget or client. but such a differentiation can be accomplished via a sum type in the curry, if desired. it's an important nod to flexibility and, once again, we can use nctree_simple_callback() (see above) to relieve the client of writing any display code.

so, i think we have our design. =]

[dankamongmen]

Well, there's one last question: how do we indicate change to an item not instigated by a standard action?

A: the same way we do with ncreel: nctree_redraw(). the question becomes how this interacts with the proposed caching layer. i'm thinking perhaps we implement "caching" via retaining the ncplanes across redraws in the widget, and passing them unchanged to the callback. the callback can then do its own check for validity, and redraw only if necessary. this of course implies a full R callbacks each frame, but they're potentially cheap callbacks. it also eliminates the need for cache management on the client side; the widget can just drop frames as they become naturally unviewed. the only trick would be a need to either invalidate-caching-info from the widget layer (probably done by invoking the callback with a NULL ncplane) or passing a nonce with each callback (eliminating the need to do an explicit invalidation callback). yeah, i think that works, either way.

i think best would be: widget-side invalidate with callback on NULL, client-side invalidate by NULLing out tracking pointer.

[dankamongmen]

we finally have something that is something!

[dankamongmen]

I say let's close this up and start making more targeted bugs.