Right node inaccessible after deleting parent

[jsandbrook]

Apologies if I'm stating that incorrectly. I don't have the best handle on the inner workings of this library.

When a covering node has 'right' and 'left' nodes, deleting it makes the right prefix inaccessible. It's fairly easy to reproduce. [1]

This specifically happens with version 0.10.0 installed explicitly without the C extension. With the C-extension, it works as expected [2].

[1] No c-extension

# Setup
>>> import radix._radix
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ImportError: No module named 'radix._radix'

>>> import radix
>>> radix.__version__
'0.10.0'
>>> rt = radix.Radix()
>>> rt.add('1.2.2.0/23')
<1.2.2.0/23>
>>> rt.add('1.2.2.0/24')
<1.2.2.0/24>
>>> rt.add('1.2.3.0/24')
<1.2.3.0/24>

# Check that the covering node has a right and left
>>> node = rt.search_exact('1.2.2.0/23')
>>> node.right
<1.2.3.0/24>
>>> node.left
<1.2.2.0/24>

# Delete the covering node
>>> rt.delete('1.2.2.0/23')

# The right node is no longer accessible despite still existing within nodes()
>>> rt.nodes()
[<1.2.2.0/24>, <1.2.3.0/24>]
>>> rt.search_exact('1.2.3.0/24')
>>> rt.delete('1.2.3.0/24')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/var/www/netarch-rest/ab-www/app/radix/radix.py", line 446, in delete
    raise KeyError('match not found')
KeyError: 'match not found'

[2] C-Extension exists this time

>>> import radix._radix
>>> rt = radix.Radix()
>>> rt.add('1.2.2.0/23')
<_radix.RadixNode object at 0x7fb361bda390>
>>> rt.add('1.2.2.0/24')
<_radix.RadixNode object at 0x7fb361bda420>
>>> rt.add('1.2.3.0/24')
<_radix.RadixNode object at 0x7fb361bda468>
>>> node = rt.search_exact('1.2.2.0/23')
>>> node.right
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: '_radix.RadixNode' object has no attribute 'right'
>>> node.left
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: '_radix.RadixNode' object has no attribute 'left'
>>> rt.delete(node.prefix)
>>> rt.search_exact('1.2.3.0/24')
<_radix.RadixNode object at 0x7fb361bda468>
>>> rt.delete('1.2.3.0/24')
>>>

[ljluestc]

import radix

class CustomRadix(radix.Radix):
    def delete(self, prefix):
        node = self.search_exact(prefix)
        if node is None:
            raise KeyError('match not found')
        
        # Check if the node to delete has children
        left_child = node.left
        right_child = node.right
        
        super().delete(prefix)
        
        if left_child:
            self._rehash_node(left_child)
        if right_child:
            self._rehash_node(right_child)

    def _rehash_node(self, node):
        # Re-add the node to fix the tree structure
        self.add(node.prefix)

# Example usage
if __name__ == "__main__":
    rt = CustomRadix()
    rt.add('1.2.2.0/23')
    rt.add('1.2.2.0/24')
    rt.add('1.2.3.0/24')

    print("Nodes before deletion:")
    for node in rt.nodes():
        print(node)

    # Delete the covering node
    rt.delete('1.2.2.0/23')

    print("\nNodes after deletion:")
    for node in rt.nodes():
        print(node)

    # Check if the right node is accessible
    right_node = rt.search_exact('1.2.3.0/24')
    print("\nRight node after deletion:")
    print(right_node)