I’ve begun to dwelve in the fantastic realm of, what I believe are, accessibility issues for access types. I do not understand at all the following messages:
list.adb:24:18: error: non-local pointer cannot point to local object
list.adb:26:18: error: non-local pointer cannot point to local object
list.adb:53:31: error: actual for “X” must be a variable
gnatmake: “list.adb” compilation error
As far as I can see, every subprogram and type are on the same level, and nothing has been marked constant or limited. So I don’t get it. Can someone explain it in simple terms ?
Also, it doesn’t seem to make a difference whether not I add “aliased” in the profile of the formal parameters I take an 'Access from. Which makes me wonder what it even does ?
Warning: in my version, the List_type type is limited, but only on his public view. It doesn’t change anything when I de-limit it.
Thank you.
pragma Ada_2022; pragma Extensions_Allowed (All);
with Ada.Unchecked_Deallocation;
generic
type Item_Type is private;
package List is
type Item_Record;
type Item_Access is access Item_Record;
type Item_Record is
record
Item : Item_Type;
Next : Item_Access;
Pred : Item_Access;
end record;
type List_Type is record
First : Item_Access;
Last : Item_Access;
Count : Natural := 0;
end record;
type List_Access is access all List_type;
type List_Iterator is
record
List : List_Access;
Current : Item_Access;
end record;
function First (List : in out List_Type) return List_Iterator;
function Last (List : in out List_Type) return List_Iterator;
procedure Delete (Iterator : List_Iterator);
procedure Free is new Ada.Unchecked_Deallocation (Item_record, Item_access);
end List;
package body List is
function First (List : in out List_Type) return List_Iterator is
(List'Access, List.First); -- ### l.24 ###
function Last (List : in out List_Type) return List_Iterator is
(List'Access, List.Last); -- ### l.26 ###
procedure Delete (Iterator : List_Iterator) is
begin
raise Iterator_Error when Iterator.current = null;
if Iterator.Current.Pred = null then
Iterator.list.first := Iterator.Current.Next;
else
Iterator.Current.Pred.Next := Iterator.Current.Next;
end if;
Free (Iterator.Current); -- ### l.53 ###
end Delete;
end List;
Lines 24/26: You are taking the access of your List variable which is a parameter to the function which will almost certainly be at a deeper scope than the function you are defining (it has to be based on what you have so far). So taking the access of it and then passing that to a named access type of a higher access level means that the object can be destroyed before the type is finalized, leaving a dangling pointer (potentially, in the “general” sense). You can try “Unchecked_Access” but that means you are on the hook for ensuring safety there.
Line 53. Free takes an access object using “in out” so that it can set the access type to null after it is done. The variable you are passing in is from the parameter of “in” type which is considered constant from the subprogram’s perspective. If you make your Delete subprogram take an “in out” parameter then it should be ok there.
For the ‘non-local pointer’ issues, it could happen that the caller of First deletes the list concerned while the iterator is still extant. So that’d be a dangling pointer. But I haven’t thought deeply about this.
For the ‘must be a variable’ issue, Free (X) takes X as an in-out parameter, because it’s going to set it to null. Try
procedure Delete (Iterator : in out List_Iterator);
ok the L53 part I understand, it is corrected.
The first part however… too alien for my mind yet.
How would you solve this without unchecked_access ? The from the solution, I’ll manage to understand your explanation.
I’l have to think about a solution. In the meantime if you want to see how the problem can manifest, take the example below:
pragma Ada_2022; pragma Extensions_Allowed (All);
with Ada.Unchecked_Deallocation;
with Ada.Text_IO; use Ada.Text_IO;
procedure jdoodle is
generic
type Item_Type is private;
package List is
type Item_Record;
type Item_Access is access Item_Record;
type Item_Record is
record
Item : Item_Type;
Next : Item_Access;
Pred : Item_Access;
end record;
type List_Type is record
First : Item_Access;
Last : Item_Access;
Count : Natural := 0;
end record;
type List_Access is access all List_type;
type List_Iterator is
record
List : List_Access;
Current : Item_Access;
end record;
function First (List : aliased in out List_Type) return List_Iterator;
function Last (List : aliased in out List_Type) return List_Iterator;
procedure Delete (Iterator : in out List_Iterator);
procedure Free is new Ada.Unchecked_Deallocation (Item_record, Item_access);
Iterator_Error : exception;
end List;
package body List is
function First (List : aliased in out List_Type) return List_Iterator is
(List'Unchecked_Access, List.First); -- ### l.24 ###
function Last (List : aliased in out List_Type) return List_Iterator is
(List'Unchecked_Access, List.Last); -- ### l.26 ###
procedure Delete (Iterator : in out List_Iterator) is
begin
raise Iterator_Error when Iterator.current = null;
if Iterator.Current.Pred = null then
Iterator.list.first := Iterator.Current.Next;
else
Iterator.Current.Pred.Next := Iterator.Current.Next;
end if;
Free (Iterator.Current); -- ### l.53 ###
end Delete;
end List;
package P is new List(Integer);
Int_List : aliased P.List_Type;
Node : P.Item_Access := new P.Item_Record'(10, null, null);
Iterator : P.List_Iterator;
Bad_Actor : P.List_Iterator;
begin
Int_List.First := Node;
Int_List.Last := Node;
Int_List.Count := 1;
Iterator := P.First(Int_List);
Bad_Actor := Iterator;
Put_Line(Bad_Actor.Current.Item'Image);
P.Delete(Iterator);
Put_Line(Bad_Actor.Current.Item'Image);
end;
You can see here that the call to the Image attribute in the Put_Line call references now deleted memory with no exception caught or compiler warning. This can be very dangerous.
See right above your question. I put out an example. I transformed 'Access to 'Unchecked_Access to bypass the Ada rule that caused your compiler error.
I didn’t intend to suggest it was a solution. I was showing why that error existed and why it wouldn’t let you assign that pointer normally by turning off the check. You wanted to know why the error existed and asked for an example to demonstrate why it was a problem…
For some reason I hadn’t noticed the full message. I see. And I just realized GNAT used Unrestricted_Access all over, and that you Jere wondered about it 6 years ago ahahah…
I’m currently updating a generic package that takes a container type as an input and creates an iterative type around it. I found quite a few instances of GNAT’s Unrestricted_Access which appear to be necessary because of the Iterate function’s container parameter of being mode “in” and the iterator needing a non constant access to it to supply tamper check semantics. […] but I don’t like relying on GNAT’s implementation defined attribute if I can help it.
Is that where this whole discussion about rust’s borrowing/ownership thing, to lock the number of variable that can access something, so as that the compiler can see nothing insecure is done without run-time checks ?
ps: I did notice my Insert was bricked, making for a exemple of dangling pointer…
Yeah it definitely is a really complex area of Ada. Not simple. For the Unrestricted_Access part, I later found two optional ways to get around it. If you are using a limited type, you can use what is called the “Rosen Technique” which is named after the guy who mostly cam up with it I believe. I’ll put a reference to that below. It allows a type to reference itself at the point of declaration (limited types only). If the type is not limited then I’ve used some tricks with System.Address_To_Access_Conversions to bypass the const-ness of the object, but this is unchecked programming (unlike the Rosen technique), so you have to really limit the scope of its use to really make use of it safely.
In terms of how to have safe iterator objects:
GNAT uses a “almost completely but not quite” way of doing it by inspecting memory and seeing if it matches what the code expects for the type. It basically does a lot of checks when you try to use/make a cursor or reference to make sure it is pointing to valid memory, but it is technically flawed in that if it is pointing to bad memory and the memory just happens to have all the correct values in it, it will be wrong. But the checks are pretty reliable in practice. You could take a look at how they check their cursors in Ada.Containers.Doubly_Linked_Lists ( gcc/gcc/ada/libgnat/a-cdlili.adb at c442a9b78bdbebdbcb4a8f91bc36961eb732fbdf · gcc-mirror/gcc · GitHub )
The only other way I have come up with making safe iterator objects is to used a reference counted access type to hold your element/node memory (internally, never exposed outside) and then ensure each cursor and “reference_type” object has a copy of that reference counted object so that the memory is never deleted until all references to it (cursors, containers, and reference_type objects). I feel this is safer than GNAT’s approach but it most likely less performant due to the extra reference counting stuff happening. I haven’t bench-marked it yet.
I had no idea the implementation of the standard libraries were so… unsightly, low-level ? Can’t help but thinking this is a bit hypocritical, though I get that it works best for practical purposes. I have issues with things good “in practice”, and not formally good, but iterators seem to be inherently either unsafe, or costly. A price to pay for their usefulness I suppose. Maybe the future will come with other solutions, like a dedicated hardware ship to do the counting and tracking.
Can I see your code, how you used the trick ?
ps: It seems to work only with access parameters, so an unnamed type, something we’re supposed to avoid ?
Ada 22 added a new feature to make safer (easier iteration): “Procedural Iterators” or “Loop bodies as anonymous procedure”. The name sounds more complex than it is. You think of the for loop you want. Say for example you want to loop through each Key, Value pair in a map, so Key_Type and Element_Type. You can create a procedure for your container API that looks like this:
procedure Iterate
(Self : Container;
Process : not null access procedure
(Key : Key_Type, Value : Element_Type))
with Allows_Exit;
procedure Iterate
(Self : Container;
Process : not null access procedure
(Key : Key_Type, Value : Element_Type))
is begin
-- loop over your container calling `Process` for
-- the key and element of each Cursor. You can use
-- hidden private cursor types that the user can't misuse
-- for this.
end Iterate;
Then after that your user can iterate over your container using the syntax:
for (Key, Value) of Some_Container_Object.Iterate(<>) loop
Put_Line(Key'Image & " => " & Element'Image);
end loop;
Which trick particular? I mentioned a couple. For some things I only have local “workspace” level stuff not online, but I might have something in one of my github repos depending on what it is.
implementing iterators/cursors using self-referencing limited objects, the rosen trick. The standard containers are too complicated, I can’t really copy what they did for my exercise, I wouldn’t understand a quarter of it.
Yes I know the procedural iterator, I didn’t see what it had special, but I see that it does hide more implementation details.
I have that as a local example. I’ll see if I can clean it up and post it somewhere online. It will be woefully incomplete as a container, just the iterator related parts. It’ll probably take me some time to prep it.
Ok, got something up you can look at. Keep in mind this is not meant to be an actual container. I genned up a contrived example to show how the Rosen technique plays into it. It is very bare bones and only has enough stuff to showcase that. Note this only works for limited containers. For normal containers that are not limited I’ve instead used System.Address_To_Access conversions to get around the const-ness. There is an analogous example for non limited containers if you do wish to see that.
Note that the cursors/ref types here are only meant for iteration. To make cursors / reference types that can be safely used for other means, you need to look at those 2 options I mentioned in my previous post. These examples are just to highlight how to work around constness and avoid Unrestricted_Access.
Rosen variable declaration in container:
One use of the Rosen technique when creating an iterator:
Many thanks. I could grok enough to change to references to access to List to reference to List.Rosen.self instead and it does circumvent the rules. But I wonder, isn’t it cheating ? I don’t understand why access parameters have those properties. If the type is limited, shouldn’t an access component, using a name type, behave the same, in the sense that it couldn’t be modified either ?
Seems like a loophole rather than a feature. Or a sort of conditonal limitedness.
I don’t think it is cheating necessarily. I believe the RM has rules for it. Also note that a limited type doesn’t mean it cannot be modified but it means it cannot be copied, so this doesn’t violate that. I may not understand what you mean though
No you’re right, I confused “no assignement” with “no copy”, but those are completely distinct concepts indeed. I forgot you can modify components, just not the whole object. Not much experience yet, I just happen to stumble or ownder about weird or corner cases above my station more often than I should.