[SOLVED] Treeview, possible to late set Node.HasChildren (plus sign)?

[d7_2_laz]

For to keep the story short: i found that (in my use case) i could save A LOT of file-IO and, so, could achieve a tremendous performance benefit if i were able to set  ANode.HasChildren := true/false  especially within customtreeview OnGetImageIndex.

The one and only problem is, that, setting it here, doesn't make the setting appear immediately. It comes into effect when a node is clicked, or the container scrolled, or another control activated.

Presumably an ANode:Update (or treeview Invalidate or Refresh) comes into effect too late, at a later repaint.
The more the operation is embedded in BeginUpdate/EndUpdate seequences.

So, does anybody know if it's possible to enforce that for an particular node the painting (or removing)  of the belonging plus sign does happen?  (Best, without OwnerDraw)
Or is this idea too far away from the standards?

[d7_2_laz]

My finding ist, that, within treeview.inc, TCustomTreeView.DoPaint;,   the fetch of the imageindex simply is too late for that purpose.
Does any reason speaks against, to place it earlier?

HERE, just before Node.HasChildren is queried:

Code: Pascal  [Select][+][-]

1.   // Right here, before the HasExpandSign definition is done (below), where Node.HasChildren
2.   if (Images <> nil) then  begin
3.       if FSelectedNode <> Node then  begin
4.         GetImageIndex(Node);
5.       end;
6.   end;
7.  
8.   VertMid := NodeRect.Top + (NodeRect.Bottom - NodeRect.Top) div 2;
9.   HasExpandSign := ShowButtons and Node.HasChildren and ((tvoShowRoot in Options) or (Node.Parent <> nil));

Here it is too late, because the expand sign stuff had been already done:

Code: Pascal  [Select][+][-]

1.     // draw icon
2.     if (Images <> nil) then
3.     begin
4.       if FSelectedNode <> Node then
5.       begin
6.       //  Please fetch that earlier
7.       //    GetImageIndex(Node);
8.         ImgIndex := Node.ImageIndex
9.       end
10.  

Placing it earlier, weill give a chance that setting Node.HasChildren will have the desired effect.

That will give the double benefit that looping a large amount of folders for subfolders, one could save those IOs and use, for instance, SHGetFileInfoW needed for to retrieve Icons from the file system.
And, it would be done only for the items that are visible!

The speed benefit, ie. fhor the ShellTreeView, could be tremendous!

My test folder is C:\Windows\WinSxS. 
What do you think?

[d7_2_laz]

Hello Jamie, fully agree, it wouldn't be a good practice to do 50  Application.ProcessMessages for to update 50 visible tree nodes.
And, at least in my case, it had not worked.
But that is not needed, really.
if i only could convince the maintainer of the treeview.inc to do this little change
(-> to move the fetch of the imageindex some few lines above, just before Node.HasChildren is evaluated),
then there are much better possibilites ready to use.

Please do me a favour and try: in any Windows file explorer: open C:\Windows, navigate to the last node. Should be "WinSxS".
Expand this node (via click on the plus icon). See how long it takes ...
Why?
Only because for thousands of subfolders each individual subfolder is opened for to identify in a for-loop if itself contains subfolders, Simply for to decide: should the plus sign be set before the treenode or not.
Tons of IOs !!
What do you think of to get rid of that easily, and to speedup the treeview drastically (more than doubled).
So that the folder in speech now opens  *instantly**?
Because simply some flags need to be correctly interpreted at the right place that are already available in OnGetImageIndex for a file object  orienteded treeview.
But only if the change within treeview.inc will be done, sigh ...

Of course i did the change already on my system, but with the next Lazarus release it will be away
So i'm hoping much that the change (as described above) will go into the source, now allowing more possiblities.

My argument is:
for a treeview, the chances are high that it deals with file objects presented in the nodes.
OnGetImageIndex typically does file access for to retrieve the icons of those file objects.
Why not allow the possiblity of a reuse of this already existant information for to provide other relevant attriebutes That, otherwise, cost a lot of IOs? By a simple source line shift?

Might a maaintainer of the treeview.inc take a look at this, please?

[d7_2_laz]

For to be fair, for the ShellTreeView there are excellent examples from wp and GetMen (can be found in the thread about ShellTreeView and system icons), but they would require some minor modifications to take full advantage (should be integrated in 2.2, if i understood right).

However: was ShellTreeView as well as my own app (and most comparable others) are doing when expanding a node, is:
search for subfolders, and iterate each subfolder for to detect if this one contains subfolders.
I was never happy with that, therefore my test of alternatives to the time-consuming HasSubFolders routine.

I ended up with this result:  'Expanding took: 156 ms  for:  C:\Windows\WinSxS'.
16 ms for the Windows folder; 0ms for the C: drive ....

What does that cost?
- 2 lines of easy code within my app (ok, might be 5 lines for better readability), within OnGetImageIndex
- Preocondition: a very small change in treeview.inc for to let it work
  The change is described above: move the call of OnGetImageIndex just before the line referencing Node.HasChilden

What's about the correctness of the alternative approach?
Test: 20000 folders on my systems.  5 folders of them are differently interpreted than before. 
And those 5 are mostly rather stuff for a philosophical debate ("should $Recycle.Bin indicate to have subfodlers").
Correct are 99,98% ... not a world-class science. but should be fairly good enough for a daily-work tool.

Does this sound interesting enough for development to do the change in treeview.inc for to allow the app to take this benefit?

[d7_2_laz]

To add: this approach would be virtual in the sense, that, when expanding a node, it would not be necessary to gather the information "HasSubfolders" for all objects at once.
But only for those few ones, that initially become visible in the viewport / that are initially painted.

What do you mean?

[d7_2_laz]

If i understand right (not quite sure): it's similar to:  for to decide whether a child node just created should have a plus sign or not,  look into the directory that is represented by the child node's name for to see if it contains at at least _one element_, file or folder doesn't matter. Right?

That wouldn't be the way i'd like to go, because:
- the result might be wrong, because an 'IsDirectoryEmpty' (= contains at least one file or one folder) or an "HasSubfolders" (= contains at least one folder) is really not the same.
So there are too many cases where you'll indicate with a plus sign that is is expandable where in fact it does not contain folders and so, shouldn't indicate to be expandable.
- as you still need to dig phyically within each child node's directory, there is no real performance win.
- you need to do that for _each_  subfolder within the node that is just being in progress to be expanded.

Result of a test using the method "Node,HasChildren := directory_is_ not_empty":
Expanding took: 2671 ms  for:  C:\Windows\WinSx
If i don't decide by "is not empty". but by "contains definitely at least one folder":
the result had been 3204 ms. This is not a very big difference.

Tre result for the method i'd  prefer had been: 'Expanding took: 156 ms  for:  C:\Windows\WinSx'

So i would still vote for this really small change in treeview,inc allowing an alternative approach.
In ShellTreeView, OnGetImageIndex, the file icons are only retrieved when first painted.

Why not allow to do the same with the plus sign, simply by shiftig the call of OnGetImageIndex some lines above, without harm, but allowing so to do a little bit more with the plus indicator here too?
What's the problem to accept this proposal?

[JuhaManninen]

What's the problem to accept this proposal?

Please upload a patch here and I will take a look. A patch tells more than thousand words.

[d7_2_laz]

Hello Juha, thanks for the offer! I attach the original version as retrieved from sourceforge (lazarus-2.0.12-fpc-3.2.0-win64.exe) this march as well as the patched version below. You'll see the change easily via a diff.

The change itself is very trivial and for itself it doesn't do anything. It only gives the chance to make things possible, that otherwise won't directly reflect in the node's current paint (re-use of already existent API calls for to adapt HasChildren).

[JuhaManninen]

Hello Juha, thanks for the offer! I attach the original version as retrieved from sourceforge (lazarus-2.0.12-fpc-3.2.0-win64.exe) this march as well as the patched version below. You'll see the change easily via a diff.

Sorry but you should learn to create actual patch files. It is very easy:
 https://wiki.lazarus.freepascal.org/Creating_A_Patch
You can use either SVN or Git.
A patch file has many advantages. There is no dangar of reverting other recent changes. Looking at a patch is often enough to see if it is good or not.
The diff format + "patch" command are very handy tools.

[wp]

However: was ShellTreeView as well as my own app (and most comparable others) are doing when expanding a node, is:
search for subfolders, and iterate each subfolder for to detect if this one contains subfolders.

I don't think so: The TShellListView starts with "PopulateWithBaseFiles" which only iterates the files/folders in the root. Then, when I open the "C:\" node, it calls "PopulateTreeNodewithFiles" which searches the files at the current level (C:\) and creates a node for each one of them. In order to decide whether a node has Children it calls the local function HasSubDir which scans the folder level below (but not deeper). When a node is clicked to expand the method CanExand is called which populates the child level of the clicked node by calling PopulateTreeNodeWithFiles again. So, in my opinion this is exactly how it should be done. This is for trunk, I did not check the releases.

[d7_2_laz]

Hello wp, thanks for reply!
please don't misunderstand - i didn't say anything against shellcontrols, i did follow a similar file access approach myself and wouldn't vote for any changes here, the more is has to be thought cross-platform so far ever possible. It's fine and fast!

However, admittedly using only a single platform (windows), i thought about how to avoid something like this local function HasSubDir, which implies a lot of time expensive file iterations, needed only for to set NewNode.HasChildren. Special situation, special approach.
There are alternatives (one might choose them or not), but they would require i could set HasChildren within OnGetImageIndex, so that this becomes part of the node paint. Solvable by a little code change, that's all, therefore i dis ask.

The last months i got more familiar with Lazarus and love to work with it very much, digging sometimes into workarounds for specific situations.
But the development admin system, installing trunk or versioning systems. is not my cosmos and scope, i know my limits here.
What i can do is to explain the demand for a change as best as i can to the review by a developer, who knows the develop system and overall architecture best, and who might accept this demand or not.
In the case here it's a bit hard, because we're not speaking about a reproducable bug (absolutely not!), but about  a little bit more flexibility for a specific system.

The change itself is trivial: to move the line "GetImageIndex(Node);" some lines above, before HasExpandSign is set:

Code: Pascal  [Select][+][-]

1.  // Do this call here and not later, so that a modification of Node.HasChildren might come into effect for HasExpandSign assignment
2.   if (Images <> nil) then  begin
3.       if FSelectedNode <> Node then  begin
4.            GetImageIndex(Node);
5.       end;
6.   end;
7.  
8.   VertMid := NodeRect.Top + (NodeRect.Bottom - NodeRect.Top) div 2;
9.   HasExpandSign := ShowButtons and Node.HasChildren and ((tvoShowRoot in Options) or (Node.Parent <> nil));

[wp]

This change will disrupt the order of actions in DoPaintNode: draw background - draw tree lines - draw expand sign - draw state icon - draw icon - draw text - draw insert mark. It is an awfully complicated method already, and your change would make it even more confuse.

When somebody refactors this method he will wonder why the "draw icon" part is split into two parts - maybe he will bring it back in order, and your problem is back.

Your solution is a hack. Why don't you set HasChildren when the node is created?

[d7_2_laz]

Hello wp,
why not directly when the node is created?  Because for to decide about the "Haschildren" prpperty, typically here long during file iterations are needed.
I did a short test usingone of the demos from the thread "ShellTreeview and System Icons", Iterating a heavy populated folder like Windows}WinSxS" (18000 subfolders) it takes 2563 ms.
Replacing the call of "HasSubDir" testwise by a hard-coded value, it takes 141 ms! So most of the time is spent here, and so i thought, from time to time. could this be improved.

Probably it could be improved using another already existent system call, with a small loss of accuracy. Namely via SHGetFileInfoW as already placed within the OnGetImageIndex callback.
I renewed my test using the shell tree demo now:  result: 156 ms.
Does it make sense i prepare a modified version of the shell tree demo for you so that you can see yourself (A simple proof of concept only. nothing stable or finalized)

The functional accuracy, in my app, is 99,975 % (only 5 of 20000 system folders are found to be differently interpreted, eg. "$Recycle.Bin"). So i think it's a legimate question if it might be a usable option for an app ... maximal speed costing minimal quality loss. Not as standard behaviour (the more it is os-specific), but as an optional decision for certain use cases.

For now i spared out the specifc technique yet, because it would need some explanation and would surely give room for specific discussions; too much for here!

Of course this needed change in treeview.inc will disrupt the natural order of actions in DoPaintNode ... in so far, as the assignment of Node.ImageIndex will be shifted a bit above.
Admittedly, that does not look nice. But in fact, regarding variables or functional interference, i cannot see any real impact. You see one? I see it so, that  simply a variable assignment is done a bit earlier. After working with the change a couple of days, i did not encounter any side effects.

If it doesn't sound comfortable, i could imagine an alternative that is completely transparent to / separated from the normal flow (a kind of purely optional to use procedure, like FOnPreGetImageIndex or, maybe better: more generic, FOnCustomGetPreAssigns or whatsoever). One could use it on own risc alternatively to FOnGetImageIndex). Normally it would be an unused slot.

Does those ideas sound crazy?

[wp]

OK, let met put this in my own words: suppose I have the TShellTreeView, open the c:\Windows node - this is fast. One of the subnodes is c:\windows\winsxs. I click on the '+' in front of the winsxs folder - it takes 1.5 s on my system until this folder opens - this is long... Looking at the folder in the explorer I see that there are many directories in this folder (more than 15,000). For each of these sub-folders the ShellTreeView inserts a node, and after inserting the node it has to check whether the node has children. It checks whether the node is a directory (which almost certainly it is), scans through this directory until it finds another directory or file (if option NonFolders is true) - if yes the node would have children, otherwise not. Since there are many folders in winsxs this will take some time.

Your idea is to move the check for "HasChildren" into the painting cycle (DoPaintNode) because only the visible nodes are painted, and this can be at most only some dozens - so there only some dozens of directories to be checked (winxsx has 15.000...).

Sounds reasonable.

What I don't like why you want to abuse the OnGetImageIndex event for this? DoPaintNode is awfully long and a good candidate for refactoring. Therefore moving OnGetImageIndex some lines higher in the code probably will be reverted in the refactored version and you will have the same issue again.

Why not introduce a new event, OnHasChildren, which is called somewhere in the beginning of DoPaintNode?

This probably will overwrite an already assigned Node.HasChildren. How to protect this?

And Node.HasChildren is used at many locations in the CustomTreeView (DoCanExpand, InternalMove, DeleteChildren, GetInternalMarkAt). Since in your solution HasChildren is valid only after painting, what if an undrawn node is processed and its HasChildren is requested (e.g. expand c:\windows\winsxs when only c:\ is open -- this will not work...!)?

Maybe there should be a new TTreeNodeState tsValidHasChildren. Querying Node.HasChildren should check if the HasChildren option is valid; if not it should fire the OnHasChildren event. This would decouple HasChildren from the painting cycle. However, this will be a non-trivial change, and there will be some chance for errors...

[d7_2_laz]

Hello wp,
you got the idea, exactly! And the good news is: it does work fine (tested with shelltree demo too).

With the only specification: the idea behind is not to move the check for "HasChildren" into the painting cycle,
but to move it there, where the SHGetFileInfoW is already doing it's job (here: for getImageIndex);. With the
pleasant accompanying effect, that it's only for the node that come into the view (maybe 30 instad of 18000 at once).
And what we surely don't want is that SHGetFileInfoW (we know it's time intensive) should be called again twice, elsewhere.That won't speedup, but slow down the overall process noticeably and kill the desired effect.

About the abuse the OnGetImageIndex: fully agree! I don't like it either!
(unfortunately the expensive SHGetFileInfoW is already herein ...  and i want to reuse it's results).
So my preferred option would be, just as you proposed, a new event - that might be, purely optional, used or not.
A purely generic optional slot, transparent and nothing changing for existing apps.
Whatever it is named ....  so i thought about, in the alternative proposal, something like that:

Code: Pascal  [Select][+][-]

1. if FSelectedNode <> Node then  begin
2.     if Assigned(FOnCustomGetSettings) then    // but that requires a variable def. outside of treeview.inc (commctrls)
3.        FOnCustomGetSettings(Self, Node);
4. ...
5. ...
6. HasExpandSign := ShowButtons and Node.HasChildren and ((tvoShowRoot in Options) or (Node.Parent <> nil));

The only reason i didn't use that, had been that i tried to avoid to touch another file (commctrls.pp) for to place the definitions here.

Whatever this custom event is, it should meet the twofold requirements;
- can fetch the imageindex here as efficient as before (= only when needed).  Instead of using OnGetImageIndex of course
- can reuse SHGetFileInfoW for to fetch other attributes and allow to set (and later paint) HasChildren here.
  SHGetFileInfoW shouldn't be forced to be called elsewhere again (the need for multiple calls should be avoided)
So probably within PaintNode might stay the best place though.