diff mbox series

[Ada] Incorrect iteration over hashed containers after multiple Inserts

Message ID 20210708135001.GA2465563@adacore.com
State New
Headers show
Series [Ada] Incorrect iteration over hashed containers after multiple Inserts | expand

Commit Message

Pierre-Marie de Rodat July 8, 2021, 1:50 p.m. UTC 
Cursors for Hashed maps and hashed sets include a component that speeds
up iteration over these containers. However, in the presence of multiple
insertions into the corresponding hash-tables, this component may become
unreliable when a cursor obtained before an iteration is compared with a
cursor denoting the same element but obtained during a loop over the
container. To prevent these anomalies, we introduce an explicit equality
operator for the corresponding Cursor types, which ignores the
additional component. This patch assumes that the mention of
"predefined" equality in the sections of the RM that discuss these
cursors is in fact an over specification.

Tested on x86_64-pc-linux-gnu, committed on trunk

gcc/ada/

	* libgnat/a-cohama.ads: Introduce an equality operator over
	cursors.
	* libgnat/a-cohase.ads: Ditto.
	* libgnat/a-cohama.adb: Add body for "=" over cursors.
	(Insert): Do not set the Position component of the cursor that
	denotes the inserted element.
	* libgnat/a-cohase.adb: Ditto.
diff mbox series

Patch

diff --git a/gcc/ada/libgnat/a-cohama.adb b/gcc/ada/libgnat/a-cohama.adb
--- a/gcc/ada/libgnat/a-cohama.adb
+++ b/gcc/ada/libgnat/a-cohama.adb
@@ -116,6 +116,13 @@  is
    -- "=" --
    ---------
 
+   function "=" (Left, Right : Cursor) return Boolean is
+   begin
+      return
+       Left.Container = Right.Container
+         and then Left.Node = Right.Node;
+   end "=";
+
    function "=" (Left, Right : Map) return Boolean is
    begin
       return Is_Equal (Left.HT, Right.HT);
@@ -636,7 +643,11 @@  is
       end if;
 
       Position.Container := Container'Unrestricted_Access;
-      Position.Position := HT_Ops.Index (HT, Position.Node);
+
+      --  Note that we do not set the Position component of the cursor,
+      --  because it may become incorrect on subsequent insertions/deletions
+      --  from the container. This will lose some optimizations but prevents
+      --  anomalies when the underlying hash-table is expanded or shrunk.
    end Insert;
 
    procedure Insert
@@ -679,7 +690,6 @@  is
       end if;
 
       Position.Container := Container'Unrestricted_Access;
-      Position.Position := HT_Ops.Index (HT, Position.Node);
    end Insert;
 
    procedure Insert


diff --git a/gcc/ada/libgnat/a-cohama.ads b/gcc/ada/libgnat/a-cohama.ads
--- a/gcc/ada/libgnat/a-cohama.ads
+++ b/gcc/ada/libgnat/a-cohama.ads
@@ -110,6 +110,14 @@  is
    type Cursor is private;
    pragma Preelaborable_Initialization (Cursor);
 
+   function "=" (Left, Right : Cursor) return Boolean;
+   --  The representation of cursors includes a component used to optimize
+   --  iteration over maps. This component may become unreliable after
+   --  multiple map insertions, and must be excluded from cursor equality,
+   --  so we need to provide an explicit definition for it, instead of
+   --  using predefined equality (as implied by a questionable comment
+   --  in the RM).
+
    Empty_Map : constant Map;
    --  Map objects declared without an initialization expression are
    --  initialized to the value Empty_Map.


diff --git a/gcc/ada/libgnat/a-cohase.adb b/gcc/ada/libgnat/a-cohase.adb
--- a/gcc/ada/libgnat/a-cohase.adb
+++ b/gcc/ada/libgnat/a-cohase.adb
@@ -145,6 +145,13 @@  is
    -- "=" --
    ---------
 
+   function "=" (Left, Right : Cursor) return Boolean is
+   begin
+      return
+       Left.Container = Right.Container
+         and then Left.Node = Right.Node;
+   end "=";
+
    function "=" (Left, Right : Set) return Boolean is
    begin
       return Is_Equal (Left.HT, Right.HT);
@@ -763,11 +770,14 @@  is
       Position  : out Cursor;
       Inserted  : out Boolean)
    is
-      HT : Hash_Table_Type renames Container'Unrestricted_Access.HT;
    begin
       Insert (Container.HT, New_Item, Position.Node, Inserted);
       Position.Container := Container'Unchecked_Access;
-      Position.Position := HT_Ops.Index (HT, Position.Node);
+
+      --  Note that we do not set the Position component of the cursor,
+      --  because it may become incorrect on subsequent insertions/deletions
+      --  from the container. This will lose some optimizations but prevents
+      --  anomalies when the underlying hash-table is expanded or shrunk.
    end Insert;
 
    procedure Insert


diff --git a/gcc/ada/libgnat/a-cohase.ads b/gcc/ada/libgnat/a-cohase.ads
--- a/gcc/ada/libgnat/a-cohase.ads
+++ b/gcc/ada/libgnat/a-cohase.ads
@@ -69,6 +69,15 @@  is
    type Cursor is private;
    pragma Preelaborable_Initialization (Cursor);
 
+   function "=" (Left, Right : Cursor) return Boolean;
+   --  The representation of cursors includes a component used to optimize
+   --  iteration over sets. This component may become unreliable after
+   --  multiple set insertions, and must be excluded from cursor equality,
+   --  so we need to provide an explicit definition for it, instead of
+   --  using predefined equality (as implied by a questionable comment
+   --  in the RM). This is also the case for hashed maps, and affects the
+   --  use of Insert primitives in hashed structures.
+
    Empty_Set : constant Set;
    --  Set objects declared without an initialization expression are
    --  initialized to the value Empty_Set.