CVS difference for ai05s/ai05-0144-2.txt
--- ai05s/ai05-0144-2.txt 2010/02/25 01:22:32 1.4
+++ ai05s/ai05-0144-2.txt 2010/04/06 00:41:41 1.5
@@ -921,3 +921,277 @@
work for that benefit (that we should have had in Ada 95, IMHO).
****************************************************************
+
+From: Erhard Ploedereder
+Sent: Friday, February 26, 2010 10:41 AM
+
+Here is part I of my homework on aliasing. The following are details of a few
+aliasing situations, referring to files in big archives, which I can distribute
+at the meeting (gnat.tar has about 16 MB, the alias_pl.tar has 1 MB). I did not
+want to distribute the archives by e-mail.
+
+===================================
+
+in Gnat, version ca 1999,
+see archive gnat.tar
+
+file osint.adb :
+
+aliaspair: Osint.locate_File and NameT.name_Buffer aliases caused at lines 795,804,820
+calls on Locate_File alias effect in Locate_'File, writing to Name_buffer (line 760)
+alias origin in namet.ads, line 121
+
+---------------------
+
+file sem_ch4.adb :
+
+aliaspair: sem_ch4.analyse_membership_op.t.typ and
+ sem_ch4.analyse_membership_op.Try_one_interp.T1
+line 1617 bur note full assignment in line 1577
+
+aliaspair: sem_ch4.find_comparison_types.it.typ and
+sem_ch4.find_comparison_types.it.Try_one_interp.T1
+lines 3456 and assignment in line 3407
+also lines 3602 and 3543
+
+--------------------
+file par_ch4.adb
+
+aliaspair: scans.token_ptr and par.ch4.bad_range_attribute.loc aliases caused by
+calls of Bad-Range_attribute in lines 1468, 1556, 1992
+
+also relevant par-sync.adb (lines 163) and scans.ads (lines 326) see also scn.abd line 433
+
+
+=======================
+for the following 2 cases, see alias_pl.tar
+
+
+file: alias_pl/adabasis/Stubber/alias.txt
+
+aliaspair: Gettoken.get_token.token, gettoken.get_token.add_on.sT
+
+many calls on GetToken
+
+-----------------
+
+file: alias_pl/scannergenerator
+
+aliaspair: Str_Tree.Calculatons.Replace_Node.Node and Str_Tree.Calculatons.Replace_Node.New_Node
+aliases in many calls out of Str_Tree.Sem_checks
+
+****************************************************************
+
+From: Erhard Ploedereder
+Sent: Friday, February 26, 2010 10:46 AM
+
+Here is an unusual (non-)aliasing situation. Nasty, but possibly not relevant.
+
+===================== cut here ==================
+-- this code is a text-book implementation of deletion from a sorted binary
+-- search tree. As far as I know, the code was originally written by Niklaus
+-- Wirth in Pascal or Modula. The code here is a literal translation into
+-- Ada, plus English identifiers, and a slightly "de-nested" structure.
+
+-- It exhibits a rather nasty problem....
+
+-- At the marked place, the original code relied on VAR parameters being
+-- passed by reference. If aliasing occured, the code produced the "right"
+-- effect of a "noop", albeit in a very screwy way. Passing the parameters
+-- by value-result corrupts the tree into a cyclic structure, if the first
+-- parameter is the subTreeLeft component of the target of the second
+-- parameter.
+
+-- (The general correction is to not execute the 2 lines when --
+-- Subtree = Temp.SubtreeLeft)
+
+-- In the original code, Tree was an uplevel-addressed variable rather than
+-- a parameter.
+
+-- It would have been nice if some diagnostics had identified the
+-- aliasing situation. (It is not your run-of-the-mill aliasing situation,
+-- though.)
+
+procedure test_wirth is
+
+ type Node;
+ type NodePtr is access Node;
+
+ type Node is record
+ Content : ElementTyp;
+ SubtreeLeft, SubtreeRight : NodePtr;
+ end record;
+
+ procedure Remove (Subtree: in out NodePtr; Tree: in out NodePtr) is
+ Temp: NodePtr;
+ begin
+ if Subtree.SubtreeRight = null then
+ Temp := Tree;
+ Tree := Subtree;
+------------
+-- the following two lines malfunction badly, if Subtree is Tree.SubtreeLeft,
+-- that is, for a call Remove(Tree.SubtreeLeft, Tree)
+-- the original code relied on the fact that VAR parameters are passed
+-- by-ref; it then produces the right effects (a "noop" in a screwy way)
+-- to fix, simply execute these lines conditionally
+
+ Subtree := Subtree.SubtreeLeft;
+ Tree.SubtreeLeft := Temp.SubtreeLeft;
+------------
+ Tree.SubtreeRight := Temp.SubtreeRight;
+ Free(Temp);
+ else
+ Remove (Subtree.SubtreeRight, Tree);
+ end if;
+ end Remove;
+
+
+procedure Delete ( Key : in KeyTyp;
+ OK : out Boolean) is
+
+ procedure RecDelete (Tree: in out NodePtr) is
+ begin -- RecDelete
+ if Tree = null then
+ OK := False;
+ else
+ case StringComp (Key, Tree.Content.Key) is
+ when Before => RecDelete (Tree.SubtreeLeft);
+ when After => RecDelete (Tree.SubtreeRight);
+ when Equal =>
+ if (Tree.SubtreeLeft = null) or else
+ (Tree.SubtreeRight = null) then
+ declare
+ Temp: NodePtr := Tree;
+ begin
+ if Tree.SubtreeRight = null then
+ Tree := Tree.SubtreeLeft;
+ else
+ Tree := Tree.SubtreeRight;
+ end if;
+ Free(Temp);
+ end;
+ else
+ Remove (Tree.SubtreeLeft, Tree);
+ end if;
+ OK := True;
+ end case;
+ end if;
+ end RecDelete;
+
+ begin -- Delete
+ RecDelete (BigTree);
+ end Delete;
+begin
+ null;
+end test_wirth;
+
+****************************************************************
+
+From: Bob Duff
+Sent: Tuesday, March 2, 2010 7:39 PM
+
+> Here is part I of my homework on aliasing.
+
+What was your homework assignment?
+And what does the stuff below attempt to prove?
+
+I'm puzzled... I'm not sure what "aliaspair", "aliases caused",
+"alias effect", and "alias origin" mean, exactly.
+
+Name_Buffer is a (very) global variable. I have fixed at least one bug related
+to that fact! ;-)
+
+What tool is producing this information?
+
+*****************************************************************
+
+From: Erhard Ploedereder
+Sent: Wednesday, March 3, 2010 12:27 PM
+
+> What was your homework assignment?
+> And what does the stuff below attempt to prove?
+> I'm puzzled... I'm not sure what "aliaspair", "aliases caused",
+> "alias effect", and "alias origin" mean, exactly.
+
+I had a homework to dig out the results of a study that we did 10 years ago
+about aliasing in real Ada code.
+
+The tool used is an implementation of Cooper-Kennedy, with a better filter than
+they used on visibility.
+
+Aliaspairs are names that denote the same object AND, for this study, cause an
+aliasing effect, i.e., reading via one name and writing via the other.
+
+Aliases are caused whereever the second name starts its scope (origin).
+Sometimes they are caused by propagation.
+The premise, if I remember correctly, was that all "[in] out" parameters were
+seen as being at risk (this is not quite true). Still, the number of aliases
+caused by explicit names (CK does not deal in pointer aliasing) were about 1 in
+10.000 lines of code.
+
+The samples in the mail were situations that we could recover 10 years later.
+Without the .tar files, indeed mostly meaningless info, unless you can re-locate
+the situations in today's GNAT code.
+
+Question is: is it worth introducing the subsetted "no aliasing" check
+ - if the number of aliases is so small
+ - if the check might not even catch them
+
+For the later purpose, these samples were intended to help evaluate whether the
+checks would indeed catch them or how they could be amended to do so.
+
+*****************************************************************
+
+From: Bob Duff
+Sent: Wednesday, March 3, 2010 1:17 PM
+
+> I had a homework to dig out the results of a study that we did 10
+> years ago about aliasing in real Ada code.
+
+Thanks for the info. Interesting results (now that I understand what they
+mean).
+
+> Question is: is it worth introducing the subsetted "no aliasing" check
+> - if the number of aliases is so small
+> - if the check might not even catch them
+
+I don't know, but to me, the primary purpose of those checks is to keep Tucker
+happy -- always a worthy goal. ;-)
+
+*****************************************************************
+
+From: Tucker Taft
+Sent: Wednesday, March 3, 2010 1:24 PM
+
+The current proposed checks are of two kinds:
+
+ 1) Two by-copy [IN] OUT parameters of the same
+ call that denote the same object. That is
+ clearly weird since there is no defined
+ ordering for the copy-back for these.
+
+ 2) Two actual parameters that denote the same object
+ occuring within a single expression
+ or simple statement, where at least one
+ is an [IN] OUT parameter of a function
+ call, and it is not specified by the language
+ rules whether that function call
+ will occur before or after the evaluation
+ of the call with the other parameter.
+
+Because (2) necessarily involves an [IN] OUT parameter of a function call, there
+is no test on existing Ada code that can determine how often these will occur.
+
+Ed verified that (1) happens very rarely in current Ada code, so there is no
+danger of significant incompatibility from (1). You might argue that it is
+unneeded, but it is an inexpensive check, and it also applies to the new
+functions with [IN] OUT parameters, so it will help users avoid doing clearly
+meaningless things with those.
+
+My own belief is that (2) will occur with some regularly in code involving calls
+on functions with [IN] OUT parameters, so it is an important check to help
+preserve the overall safety level of Ada, as we add [IN] OUT parameters to
+functions. In my view, there is nothing more important than preserving the
+overall safety level of Ada going forward.
+
+*****************************************************************
Questions? Ask the ACAA Technical Agent