Patchwork [Ada] No tampering check for empty container

login
register
mail settings
Submitter Arnaud Charlet
Date April 25, 2013, 10:24 a.m.
Message ID <20130425102427.GA4995@adacore.com>
Download mbox | patch
Permalink /patch/239465/
State New
Headers show

Comments

Arnaud Charlet - April 25, 2013, 10:24 a.m.
AI05-0022 requires that tampering checks be performed in order to detect
manipulation of the container via generic actual subprograms. (In the case of
the ordered maps, that would occur through generic operators "<" for Key_Type
and "=" for Element_Type.)

However, for an empty container, no such check is strictly required, as we
obtain the result without having to invoke any generic formal subprograms
(because there are no elements). To ensure that there is no unnecessary
manipulation of container state, we handle an empty container as a special
case, and return a result immediately, without performing a tampering check.

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

2013-04-25  Matthew Heaney  <heaney@adacore.com>

	* a-rbtgbo.adb, a-crbtgo.adb (Generic_Equal): do not test for
	tampering when container empty.
	* a-crbtgk.adb (Ceiling, Find, Floor): ditto.
	(Generic_Conditional_Insert, Generic_Conditional_Insert_With_Hint):
	ditto.

Patch

Index: a-crbtgk.adb
===================================================================
--- a-crbtgk.adb	(revision 198221)
+++ a-crbtgk.adb	(working copy)
@@ -45,6 +45,13 @@ 
       X : Node_Access;
 
    begin
+      --  If the container is empty, return a result immediately, so that we do
+      --  not manipulate the tamper bits unnecessarily.
+
+      if Tree.Root = null then
+         return null;
+      end if;
+
       --  Per AI05-0022, the container implementation is required to detect
       --  element tampering by a generic actual subprogram.
 
@@ -87,6 +94,13 @@ 
       Result : Node_Access;
 
    begin
+      --  If the container is empty, return a result immediately, so that we do
+      --  not manipulate the tamper bits unnecessarily.
+
+      if Tree.Root = null then
+         return null;
+      end if;
+
       --  Per AI05-0022, the container implementation is required to detect
       --  element tampering by a generic actual subprogram.
 
@@ -137,6 +151,13 @@ 
       X : Node_Access;
 
    begin
+      --  If the container is empty, return a result immediately, so that we do
+      --  not manipulate the tamper bits unnecessarily.
+
+      if Tree.Root = null then
+         return null;
+      end if;
+
       --  Per AI05-0022, the container implementation is required to detect
       --  element tampering by a generic actual subprogram.
 
@@ -198,6 +219,15 @@ 
       --  its previous neighbor, in order for the conditional insertion to
       --  succeed.
 
+      --  Handle insertion into an empty container as a special case, so that
+      --  we do not manipulate the tamper bits unnecessarily.
+
+      if Tree.Root = null then
+         Insert_Post (Tree, null, True, Node);
+         Inserted := True;
+         return;
+      end if;
+
       --  We search the tree to find the nearest neighbor of Key, which is
       --  either the smallest node greater than Key (Inserted is True), or the
       --  largest node less or equivalent to Key (Inserted is False).
@@ -227,9 +257,9 @@ 
 
       if Inserted then
 
-         --  Either Tree is empty, or Key is less than Y. If Y is the first
-         --  node in the tree, then there are no other nodes that we need to
-         --  search for, and we insert a new node into the tree.
+         --  Key is less than Y. If Y is the first node in the tree, then there
+         --  are no other nodes that we need to search for, and we insert a new
+         --  node into the tree.
 
          if Y = Tree.First then
             Insert_Post (Tree, Y, True, Node);
@@ -316,18 +346,26 @@ 
       --  is not a search and the only comparisons that occur are with
       --  the hint and its neighbor.
 
-      --  If Position is null, this is interpreted to mean that Key is
-      --  large relative to the nodes in the tree. If the tree is empty,
-      --  or Key is greater than the last node in the tree, then we're
-      --  done; otherwise the hint was "wrong" and we must search.
+      --  Handle insertion into an empty container as a special case, so that
+      --  we do not manipulate the tamper bits unnecessarily.
 
+      if Tree.Root = null then
+         Insert_Post (Tree, null, True, Node);
+         Inserted := True;
+         return;
+      end if;
+
+      --  If Position is null, this is interpreted to mean that Key is large
+      --  relative to the nodes in the tree. If Key is greater than the last
+      --  node in the tree, then we're done; otherwise the hint was "wrong" and
+      --  we must search.
+
       if Position = null then  -- largest
          begin
             B := B + 1;
             L := L + 1;
 
-            Compare :=
-              Tree.Last = null or else Is_Greater_Key_Node (Key, Tree.Last);
+            Compare := Is_Greater_Key_Node (Key, Tree.Last);
 
             L := L - 1;
             B := B - 1;
Index: a-crbtgo.adb
===================================================================
--- a-crbtgo.adb	(revision 198221)
+++ a-crbtgo.adb	(working copy)
@@ -646,6 +646,13 @@ 
          return False;
       end if;
 
+      --  If the containers are empty, return a result immediately, so as to
+      --  not manipulate the tamper bits unnecessarily.
+
+      if Left.Length = 0 then
+         return True;
+      end if;
+
       --  Per AI05-0022, the container implementation is required to detect
       --  element tampering by a generic actual subprogram.
 
Index: a-rbtgbo.adb
===================================================================
--- a-rbtgbo.adb	(revision 198221)
+++ a-rbtgbo.adb	(working copy)
@@ -626,6 +626,13 @@ 
          return False;
       end if;
 
+      --  If the containers are empty, return a result immediately, so as to
+      --  not manipulate the tamper bits unnecessarily.
+
+      if Left.Length = 0 then
+         return True;
+      end if;
+
       --  Per AI05-0022, the container implementation is required to detect
       --  element tampering by a generic actual subprogram.