doRemoveLeaf() incorrectly clears leaf data and breaks subgroup trees

Hello;

I've found something interesting related to this issue.

Given a Group entity and three Subgroups of this group, after its creation they have the following data:

PARENT

|ID|Depth|Left|Right|Tree|
|--|-----|----|-----|----|
|62|0    |1   |8    |62  | 

CHILD

|ID|Depth|Left|Right|Tree|
|--|-----|----|-----|----|
|63|1    |2   |3    |62  | 
|64|1    |4   |5    |62  | 
|65|1    |6   |7    |62  | 

The desired structure is as follows: one parent (62), three children on the same level (63, 64, 65)

As you can see, every child has the correct depth and tree values.

If you start eliminating them from 65 up to 63, everything's fine.

But if you start from the group with ID 63 the whole tree will break because the left and (especially) right values will change in a way that methods like getChildren, hasDescendant, etc... won't work anymore.

This seems to be related to this code on function doRemoveLeaf() on /src/Entity/SubgroupHandlerBase.php

    // If the left and right values are 2 and 3 respectively it means we're
    // removing the last child of a tree root. In this case, we unset the tree
    // altogether.
    if ($leaf->getLeft() === 2 && $leaf->getRight() === 3) {
      $root = $this->storage->load($leaf->getTree());
      $this->clearLeafData($root, TRUE);
    }

The code states that "If the left and right values are 2 and 3 respectively it means we're removing the last child", but this is false, at least with the previous data, since there are at least two siblings left (groups 64 and 65) and yet the clearLeafData method is called on the root. This is "wiping" the tree data even if we just deleted a single children that happened to be the first one to be created.

So, it seems to me that either the children's left and right data are wrong or the previous code is making a false assumtpion (that the user will delete the groups in the same order as they were created).

I've added a new patch/MR with an alternate solution that handles the origin of the malformed data.

For reference, those are the steps that I followed to solve the bug on a clean D9 install and my reasoning of the solution:

1- Create a group and four subgroups

Result:

The Group parent has the following values:

|ID|Depth|Left|Right|Tree|
|--|-----|----|-----|----|
|1 |0    |1   |10   |1  | 

The Childs have the following values.

|ID|Depth|Left|Right|Tree|
|--|-----|----|-----|----|
|2 |1    |2   |3    |1  | 
|3 |1    |4   |5    |1  | 
|4 |1    |6   |7    |1  | 
|5 |1    |8   |9    |1  | 

This behavior is correct and establishes a tree. Note that the parent's Right value equals to the last child's Right value + 1.

2- Remove the last child (ID 5)

Result:

The Group parent has the following values:

|ID|Depth|Left|Right|Tree|
|--|-----|----|-----|----|
|1 |0    |1   |8    |1  | 

The Childs have the following values.

|ID|Depth|Left|Right|Tree|
|--|-----|----|-----|----|
|2 |1    |2   |3    |1  | 
|3 |1    |4   |5    |1  | 
|4 |1    |6   |7    |1  | 

This behavior is correct and the parent's Right value has been updated to reflect the new last child's Right value + 1. Now, the parent "embraces" subgroups from 0 (left) to 8 (right).

3- Remove the first child (GID 2)

Result:

The Group parent has the following values:

|ID|Depth|Left|Right|Tree|
|--|-----|----|-----|----|
|1 |NULL |NULL|NULL |1  | 

The Childs have the following values.

|ID|Depth|Left|Right|Tree|
|--|-----|----|-----|----|
|3 |1    |4   |5    |1  | 
|4 |1    |6   |7    |1  | 

This behavior is wrong and is the source of the problem. The parent's tree data has been wiped so, from now on, all calls to handler methods like hasDescendants, isParent, etc... will fail.

As I said on the previous comment, the problem seems to be related with the detection of wether the removed Leaf of a tree is the last one. The code is relying on a comparison of ($leaf->getLeft() === 2 && $leaf->getRight() === 3) , which implies that the user won't start by deleting the first created child (in my example, GID 2).

The patch addresses this by changing to this comparison:

    $root = $this->storage->load($leaf->getTree());

    // If there are no more descendants left, it means we removed the last
    // child of a tree root. In this case, we unset the tree altogether.
    if ($root instanceof GroupInterface && !$this->hasDescendants($root)) {
      $this->clearLeafData($root, TRUE);
    }

I have checked that, when this code executes, the hasDescendants() method correctly returns TRUE or FALSE depending on the remaining groups (in this point, the deleted group is not included on hasDescendants() and won't throw a false positive).

This allows the user to delete subgroups in any order, but it also introduces the need of an additional query (so it has a performance impact) and I haven't tested on more complex trees, with more nesting levels.

Tests are failing, i will check them as soon as possible.

Updated the title to reflect the actual problem.

Yup, this is a bug and it only manifests itself when the leftmost child has no descendants. Otherwise, it would never have values 2 and 3. This is an oversight and needs to be fixed ASAP, good catch!

What needs to happen here is:

1. Rewrite the check to see if it is in fact the last leaf (i.e. depth 1 and no siblings)
2. Preferably put the above in the handler and properly test it
3. Write a change record that tells you how to fix or an update hook that does it for you

I'm hesitant about the update hook because if the original parent group was used again as a root, all hell breaks loose. So I'd rather put a code sample in a change record instead. Any suggestions would be welcome :)

Here's an idea. Should still be performant (because no entities loaded) and we still rely on left-2/right-3 values to save some processing power too.

Didn't use the fork because I didn't want to completely remove your work in a single commit and I can't quickly figure out how to have multiple forks for one issue. Needs tests for new method and to prove the broken scenario works now.

Think I figured the forks out, but doing patch just for now (so tests run during lunch).

This adds tests, and reverses the test for last child removal so the leftmost child is removed first and the rightmost (now leftmost) child second. This makes sure that a left-2/right-3 child does not trigger a tree destruction unless it's the last descendant of its root.

Forgot about stale entity properties in tests

Will tag a new release as this is important enough to warrant one.

Nice to see this solved!! My patch was mainly a workaround, but had no time to investigate a better solution. Many thanks!

I think this fix does not work anymore. I'm not sure why or how but we should check for a descendants count of 0, not 1. When I create 1 group with 2 subgroups and specifically delete the first subgroup. My tree gets broken because it triggers clearLeafData(). We only want this to trigger when there are no children in the root. Here is a new patch: