gh-93065: Fix HAMT to iterate correctly over 7-level deep trees (GH-93066) (GH-93146)

Also while there, clarify a few things about why we reduce the hash to 32 bits.

Co-authored-by: Eli Libman <eli@hyro.ai>
Co-authored-by: Yury Selivanov <yury@edgedb.com>
Co-authored-by: Łukasz Langa <lukasz@langa.pl>

(cherry picked from commit c1f5c903a7e4ed27190488f4e33b00d3c3d952e5)

1 files changed, 35 insertions, 0 deletions

diff --git a/Lib/test/test_context.py b/Lib/test/test_context.py
index 2d8b63a..689e3d4 100644
--- a/Lib/test/test_context.py
+++ b/Lib/test/test_context.py
@@ -533,6 +533,41 @@ class HamtTest(unittest.TestCase):
         self.assertEqual(len(h4), 2)
         self.assertEqual(len(h5), 3)
 
+    def test_hamt_collision_3(self):
+        # Test that iteration works with the deepest tree possible.
+        # https://github.com/python/cpython/issues/93065
+
+        C = HashKey(0b10000000_00000000_00000000_00000000, 'C')
+        D = HashKey(0b10000000_00000000_00000000_00000000, 'D')
+
+        E = HashKey(0b00000000_00000000_00000000_00000000, 'E')
+
+        h = hamt()
+        h = h.set(C, 'C')
+        h = h.set(D, 'D')
+        h = h.set(E, 'E')
+
+        # BitmapNode(size=2 count=1 bitmap=0b1):
+        #   NULL:
+        #     BitmapNode(size=2 count=1 bitmap=0b1):
+        #       NULL:
+        #         BitmapNode(size=2 count=1 bitmap=0b1):
+        #           NULL:
+        #             BitmapNode(size=2 count=1 bitmap=0b1):
+        #               NULL:
+        #                 BitmapNode(size=2 count=1 bitmap=0b1):
+        #                   NULL:
+        #                     BitmapNode(size=2 count=1 bitmap=0b1):
+        #                       NULL:
+        #                         BitmapNode(size=4 count=2 bitmap=0b101):
+        #                           <Key name:E hash:0>: 'E'
+        #                           NULL:
+        #                             CollisionNode(size=4 id=0x107a24520):
+        #                               <Key name:C hash:2147483648>: 'C'
+        #                               <Key name:D hash:2147483648>: 'D'
+
+        self.assertEqual({k.name for k in h.keys()}, {'C', 'D', 'E'})
+
     def test_hamt_stress(self):
         COLLECTION_SIZE = 7000
         TEST_ITERS_EVERY = 647