public inbox for gcc-cvs@sourceware.org
help / color / mirror / Atom feed
* [gcc r12-2145] [Ada] Incorrect iteration over hashed containers after multiple Inserts
@ 2021-07-08 13:36 Pierre-Marie de Rodat
0 siblings, 0 replies; only message in thread
From: Pierre-Marie de Rodat @ 2021-07-08 13:36 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:b927d936e339ddd47779b522b80552306ebb5604
commit r12-2145-gb927d936e339ddd47779b522b80552306ebb5604
Author: Ed Schonberg <schonberg@adacore.com>
Date: Fri May 21 15:51:13 2021 -0400
[Ada] Incorrect iteration over hashed containers after multiple Inserts
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:
---
gcc/ada/libgnat/a-cohama.adb | 14 ++++++++++++--
gcc/ada/libgnat/a-cohama.ads | 8 ++++++++
gcc/ada/libgnat/a-cohase.adb | 14 ++++++++++++--
gcc/ada/libgnat/a-cohase.ads | 9 +++++++++
4 files changed, 41 insertions(+), 4 deletions(-)
diff --git a/gcc/ada/libgnat/a-cohama.adb b/gcc/ada/libgnat/a-cohama.adb
index 26bdd552265..e6d6e4d4030 100644
--- 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
index a04cb3a34c6..3f172bd399a 100644
--- 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
index 31374f6b9d6..2342116043e 100644
--- 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
index f0763afbcfc..2356ba7f66a 100644
--- 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.
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2021-07-08 13:36 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-07-08 13:36 [gcc r12-2145] [Ada] Incorrect iteration over hashed containers after multiple Inserts Pierre-Marie de Rodat
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).