public inbox for gcc-cvs@sourceware.org help / color / mirror / Atom feed
From: Pierre-Marie de Rodat <pmderodat@gcc.gnu.org> To: gcc-cvs@gcc.gnu.org Subject: [gcc r12-2145] [Ada] Incorrect iteration over hashed containers after multiple Inserts Date: Thu, 8 Jul 2021 13:36:18 +0000 (GMT) [thread overview] Message-ID: <20210708133618.D521F398B842@sourceware.org> (raw) 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.
reply other threads:[~2021-07-08 13:36 UTC|newest] Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20210708133618.D521F398B842@sourceware.org \ --to=pmderodat@gcc.gnu.org \ --cc=gcc-cvs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
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).