Expandable tree example

[pzcfg]

trafficstars

This adds a storybook example of an expandable nested tree by implementing a custom cell renderer, shifting text based on depth, and filtering out the children of collapsed items.

https://user-images.githubusercontent.com/94077014/171967390-19d2047f-70e7-4dff-b818-4a73d146324d.mp4

[jassmith]

Holy hell you did it, the mad lad pulled it off. Totally want to put that tree cell renderer into the core cells package. Bravo.

[pzcfg]

This also adds a sort of proposal for adding an onCellClicked function to the custom cell renders. I feel like that makes sense for handling custom logic such as the toggle on these cells, however it also requires some sort of callback to allow effects to state where the <DataEditor> is used. That's currently pretty hand-wavy with an (...args: any[]) => any function, but maybe other people have suggestions for how to handle this elegantly/cleanly.

[jassmith]

Just want to follow up I am still planning to polish and merge this. Just need to find the time.

[engrpatel21]

hey just wondering if this would be planned for 5.0. i am currenty using @pzcfg solution to get what i need accomplished.

[vilkinsons]

@jassmith Would be keen to help get this over the line if there are specific outstanding todos you're tracking! This is awesome.

[jassmith]

Okay the checklist for this is

• [ ] Move the source work into the source package
• [ ] Move the cell in to the cells package
• [ ] Utilize existing rendering calls instead of recreating basic text rendering.

Nice to haves

• [ ] Move informative hover effects

[pzcfg]

I took at stab at the above in two branches in my fork:

• tree-in-situ-onCellClicked adds onCellClicked directly in the example story, but this requires managing the depth and collapsing manually, which seems like it should be co-located with the tree rendering
• tree-CustomRenderer-onCellClicked adds an optional onCellClicked to CellRenderer which attempts to keep the logic with the renderer, but the actual implementation is pretty clunky at the moment.

Let me know if you want to pursue some from of onCellClicked colocation, or leave that either as a helper function or for the end user to implement as they desire.

[jassmith]

Hey @pzcfg sorry for the delay I've been out of country. I will be home this weekend and dig into this then.

[hyusetiawan]

@jassmith were you able to check out this PR?

[jassmith]

Yeah I've looked at it. Im just busy and this is a big scope increase. I could really use help polishing this up.

[rickarubio]

This is an awesome feature, thank you @pzcfg!

What do you think about also being able to do row group headers?

Here is an example of what I mean: (http://mleibman.github.io/SlickGrid/examples/example-grouping)

I have been looking for an alternative to this slickgrid functionality (the ability to have collapsible rows and nested row group headers). I think @pzcfg expandable tree code is pretty close.

Is that something that there would be interest in getting merged in as well (collapsible row group headers)? @jassmith

[jassmith]

functionally collapsible row group headers is just this + row spans which already exist.

[rickarubio]

functionally collapsible row group headers is just this + row spans which already exist.

Ah, I see it now: https://glideapps.github.io/glide-data-grid/?path=/story/glide-data-grid-dataeditor-demos--span-cell

I had been searching for a different term to figure out if row headers functionality existed. Thank you!

~~Is there any way to span a cell to take up all columns in a row regardless of the spanned cell's data types? For example if there is an image column in the middle of the grid, but you want to span a cell across an entire row to act as a row header with just text as the row header title.~~

~~Is that currently possible or any idea how / where I could start poking around to make it possible?~~

Edit: I'm not sure what this note in the storybook example meant or was warning against:

All cells within a span must return consistent data for defined behavior.

I see now that spanning across an entire row works regardless of various cell data types by doing something like

if (row === 3) {
  return {
    kind: GridCellKind.Text,
    allowOverlay: false,
    data: "This is a very long row grouping header now ...............................................................................etc",
    span: [0, cols.length-1],
    displayData: "This is a very long row grouping header now ........................................................................etc",
  }
}

[jassmith]

That note is pretty straightforward in concept but maybe not clear. If, for example, you have all of row 0 spanned into one giant cell, it is still acceptable for GDG to call getCellContent([2, 0]) or getCellContent([4,0]). In both of those cases it is expected that you will return a consistent result. The reasons for this are simply that since your spans are not required to be declared up front, and we only request cells based on the visible window, we don't actually know if the span cell we are about to request is already part of a span.

[rickarubio]

Makes sense, thanks!

If there's anything I (or anyone else following this thread) can do to help @pzcfg's feature get merged in, please let us know.

I'd be more than happy to help in any way I can.

[jassmith]

Rebase, clean it up, provide a code review :)

[jassmith]

Move the story to the correct location now

[rickarubio]

Move the story to the correct location now

Looks like @pzcfg has handled this in both these forks, the new cell type is called tree-cell and the new story is located in packages/cells/src/cell.stories.tsx along with existing custom cell stories.

1. https://github.com/glideapps/glide-data-grid/compare/main...pzcfg:glide-data-grid:tree-in-situ-onCellClicked
2. https://github.com/glideapps/glide-data-grid/compare/main...pzcfg:glide-data-grid:tree-CustomRenderer-onCellClicked

https://github.com/glideapps/glide-data-grid/pull/358#issuecomment-1278420073

Where to put onCellClicked seems to be needing some direction/decision.

[jassmith]

There is now an onClick event in the BaseCellRenderer interface which should suffice for what is being done here.

[pzcfg]

I can take a look at writing this with the new onClick event soon-ish.

In your case @rickarubio, if you don't need the nested levels (just one top level of collapsable rows) this implementation is probably overkill. You can create the header rows and toggle an array of collapsed states, then omit the children of the ones collapsed.

[rickarubio]

Awesome, thanks @pzcfg! Actually, nested row groups (with row group headers via cell spans for each group at each level) is exactly what I'm looking for 😁

I'm definitely interested in seeing this feature through! Let me know if I can help in any way, I'll follow the updates and review the code (though I am not super familiar with this library codebase yet).

[pzcfg]

Okay rebased this and switched over to using onClick, etc. but ran into some design issues I could use suggestions for.

Right now this is mutating the collapsed property directly on the TreeNode and then forcing the flattened tree to be rebuilt using setRoot({...root}) which isn't ideal. I was looking into making the cell return a new version of the node, but I think it would require adding a unique id field, or returning both the new and existing nodes so object equality can be used to find which node needs replacing. Any preferences on how to approach this?

Additionally, do you think TreeNode should have its own data (or otherwise-named) field to hold data for other columns you may want to render, or use something like an id field to look that information up elsewhere?

I'm also wondering if it would be better to have a more comprehensive set of tree manipulation methods or make TreeNode an object that can handle things like reparenting, inserting/removing children, etc. I didn't really see any existing tree libraries online that I liked but figured I'd hold off for suggestions before building my own.

---

Side note: how would you feel about adding immer as a dependency? While exploring the return-new-cell approach I found myself doing some overly complicated nested spreads like

return {
  ...cell,
  data: {
    ...cell.data,
    node: {
      ...cell.data.node,
      node: !node.collapsed
    }
  }
}

and immer's produce() would simplify this to

return produce(cell, draft => { draft.data.node.collapsed = !draft.data.node.collapsed })

[rickarubio]

Hey @pzcfg I'm wondering if you're noticing extremely large memory use when using larger numbers for the tree renderer.

For example, running the "100 Million Rows" demo in the glide storybook uses around 55-60MB of the JS Heap.

However, if I run the Expandable Tree demo, and I loop around 10,000 times in createSampleTree() to 10,000x the sample data:

export function createSampleTree(): TreeNode {
    const root = createNode("Root", "Root Item");
    root.collapsed = false;

    for (let i = 1; i <= 10_000; i++) {
      names.forEach(nameX => {

root node has 60,000 children (A), each of those children (A) has 6 children (B), each of those children (B) has 6 children (C).

60,000 * 6 = 360,000 * 6 = 2,160,000 children (C)

2,160,000 children (C) + 360,000 children (B) + 60,000 children (A) + root node = 2,580,001 elements in total in the expandable tree data grid demo.

However, looking at heap size usage with 2.58M tree node elements, the heap size is drastically higher than the 100M rows example.

JS Heap size seems to hover around 443MB when not doing anything (assuming all levels have collapsed = false to show them in an expanded state)

However, as soon as you attempt to collapse/expand a node, for example the root node, you will see heap size usage shoot up to 800MB - 1700MB. There is also about a half-second lag between clicking on a node to collapse/expand it when you're at 2.58M elements.

If you try go another power of 10 higher to do 25.8M elements, then the browser tab will crash since it exceeds the 4GB heap-size memory per tab limit of chrome.

Any idea why this is using such high amount of memory? Is it just because we are storing objects (the tree nodes) instead of strings (as in the 100M rows demo?). Or is there some optimization that is missing?

[pzcfg]

Woah! To be honest I haven't looked into profiling it at all.

It sounds like maybe the old tree or flattened list isn't getting freed when the new one is created? Not quite sure how best to diagnose that. Even with ~2.5M nodes though that memory usage sounds incredibly high.

I also think that if you're planning to use it for something with as many items as that, that you'll need a smarter tree flattening system that doesn't walk the whole thing and push() onto an array each time. Maybe something that caches flattened subtrees and and includes/excludes those depending on what's collapsed, but I imagine that could have its own memory issues, and is likely overkill for most cases.

[rickarubio]

@pzcfg Thanks for pointing me in the right direction. I switched over to testing out the latest version of your branch, and I can get the ~25M nodes to load with heap size around 3.3GB - 3.9GB (100,000x loop over createSampleTree() :

However, collapsing/uncollapsing a node (I tested the root node) will cause an out of memory crash:

It does seem that flattenTree is the culprit, it is called when setting up the initial rows for the grid via const rows = useCollapsingTreeRows(root); and again when collapsing/expanding tree nodes. Expanding/collapsing tree nodes is also when the spike in memory is observed.

I'll keep poking around here and see if I can find any way to improve the memory usage. Being able to display a large number of rows for tree cells would be nice, especially since 100M rows (Silly Numbers storybook example) seems to work so well.

[pzcfg]

I switched over to testing out the latest version of your branch, and I can get the ~25M nodes to load with heap size around 3.3GB - 3.9GB

Aah I didn't realize you were on the latest branch. Probably the most impactful memory change from previous versions was this

- const [root, setRoot] = React.useState(createSampleTree());
+ const [root, setRoot] = React.useState(() => createSampleTree());

In the previous version createSampleTree() gets called on every render and simply discarded after the initial state setup. Using the function means it only gets called once to get the starting state.

again when collapsing/expanding tree nodes. Expanding/collapsing tree nodes is also when the spike in memory is observed

I'm guessing this is because during that time two flattened trees exist until the garbage collector realizes the old one is no longer referenced.

In terms of improving performance, I'm thinking that if you keep track of the counts of the recursive children, you may be able to .splice() these in and out of the flattened array instead of recreating it each time, but you'd either still have to recalculate the whole subtree when re-expanding, or hold onto that at each level of the tree, which would probably have its own performance issues.

I'm also not sure if there would be any benefits to giving all of the nodes and id and track/access the children using that instead of deeply nested nodes. And if it would be beneficial to eliminate the recursive tree walking for deep trees.

[pzcfg]

However, collapsing/uncollapsing a node (I tested the root node) will cause an out of memory crash

I'm particularly surprised that this happens at the root node, but it did make me take another look at flattenTree(), and there's no reason to be looping over the children if the node is collapsed. Not sure why I wrote it that way…but I think this would improve that at least slightly.

  const _visit = (node: TreeNode, depth: number = 0) => {
    node.depth = depth;
    flattened.push(node);
-   node.children.forEach(child => { if (!(node.collapsed === true)) _visit(child, depth + 1) });
+   if (node.collapsed === true) return
+   node.children.forEach(child => { _visit(child, depth + 1) });
  };

[pzcfg]

Well that change certainly improves the root collapsing performance 😅 but the rest no so much 😬

[KyDenZ]

Do you have any updates on this feature? This is a great feature!

[pzcfg]

I haven't had a chance to dig into this more recently. In the short term you're probably best off including this as a custom cell and effect you use in combination with the grid as it is.