TBaseVirtualTree.GetLastVisibleNoInit code is incorrect and causes exponential slowdowns when traversing very large trees. (Suggested code changes attached) #725
Description
I've been using TreeView 4.5.4 with a Delphi 2007 project which I recently ported across to Delphi 10.2
In the process I installed the latest TreeView 6.7.0
I noticed that my TreeView control was very sluggish when moving up or down nodes using the arrow keys and there was also a lag when clicking on items far down the tree. This did not happen with the 4.5.4 version.
I've traced the problem to the TBaseVirtualTree.GetLastVisibleNoInit function:
6.7.0 looks like this:
function TBaseVirtualTree.GetLastVisibleNoInit(Node: PVirtualNode = nil;
ConsiderChildrenAbove: Boolean = True; IncludeFiltered: Boolean = False): PVirtualNode;
// Returns the very last visible node in the tree while optionally considering toChildrenAbove.
// No initialization is performed.
begin
Result := GetLastNoInit(Node, ConsiderChildrenAbove);
while Assigned(Result) and (Result <> Node) do
begin
if FullyVisible[Result] and
(IncludeFiltered or not IsEffectivelyFiltered[Result]) then
Break;
Result := GetPreviousNoInit(Result, ConsiderChildrenAbove);
end;
if (Result = Node) then // i.e. there is no visible node
Result := nil;
end;
The same function in 4.5.4 looks like this:
function TBaseVirtualTree.GetLastVisibleNoInit(Node: PVirtualNode = nil): PVirtualNode;
// Returns the very last visible node in the tree without initialization.
var
Next: PVirtualNode;
begin
Result := GetLastVisibleChildNoInit(Node);
while Assigned(Result) do
begin
// Test if there is a next last visible child. If not keep the node from the last run.
// Otherwise use the next last visible child.
Next := GetLastVisibleChildNoInit(Result);
if Next = nil then
Break;
Result := Next;
end;
end;
As you can see this version is calling the GetLastVisibleChildNoInit function instead of GetLastNoInit and GetPreviousNoInit
My suggested change is below:
function TBaseVirtualTree.GetLastVisibleNoInit(Node: PVirtualNode = nil;
ConsiderChildrenAbove: Boolean = True; IncludeFiltered: Boolean = False): PVirtualNode;
// Returns the very last visible node in the tree while optionally considering toChildrenAbove.
// No initialization is performed.
begin
Result := GetLastVisibleChildNoInit(Node, ConsiderChildrenAbove);
while Assigned(Result) and (Result <> Node) do
begin
if FullyVisible[Result] and
(IncludeFiltered or not IsEffectivelyFiltered[Result]) then
Break;
Result := GetLastVisibleChildNoInit(Result, ConsiderChildrenAbove);
end;
if (Result = Node) then // i.e. there is no visible node
Result := nil;
end;
Making this change resolved the sluggishness I was experiencing in my project.