Ada 2005, access types, and local variable escape analysis

Question

So when playing with access types on an Ada compiler which turns out to be Ada 2005, I try the following classic example:

type Node is record
  next: access Node;
end record;

function reverselist(input: access Node) return access Node is
  result: access Node := null;
  this: access Node := input;
  next: access Node := null;
begin
  while this /= null loop
    next := this.next;
    this.next := result; -- [*]
    result := this;
    this := next;
  end loop;
  return result; -- [*]
end;

The two starred lines produce compilation errors because Ada 2005's analysis thinks I might be leaking a local pointer. (I know that Ada 2012 has better analysis and will accept this. However, I don't have an Ada 2012 compiler.)

Okay, so this can be easily solved by using a named pool access instead of the anonymous access Node; by using a pool access I tell the compiler that the pointers can't be referring to stack objects. That works fine.

However, then I tried using a named general access:

type Node;
type List is access Node;
type Node is record
    next: List;
end record;

function reverselist(input: List) return access Node is
   result: List := null;
   this: List := input;
   next: List := null;
begin
   while this /= null loop
      next := this.next;
      this.next := result;
      result := this;
      this := next;
   end loop;
   return result;
end;

General access types can point at stack objects as well as heap objects; so why doesn't the compiler reject the second example for the same reasons that it rejected the first?

(I was also slightly surprised that anonymous access integer variables seem to end up with general access semantics. Why don't I have to use access all integer for anonymous general accesses?)

Answer 1

Although in general a general access type can point at non-heap objects (both global and stack), there are rules that would prevent a List from pointing to the stack. In this case, since List is not declared inside any subprogram, it cannot be made to point to a stack variable:

function reverselist(input: List) return access Node is
   result: List := null;
   this: List := input;
   next: List := null;
   Dummy : aliased Node;
begin
   result := Dummy'Access;  -- a compile-time error would occur at this point
   while this /= null loop
      next := this.next;
      this.next := result;
      result := this;
      this := next;
   end loop;
   return result;
end;

Since the rules "ensure" that a List can never point to a stack variable, there's no need for the compiler to reject any of the other statements. (I put "ensure" in quotes because you could use 'Unchecked_Access to get around them, as well as Unchecked_Conversion or a number of other ways to get around the type system.)

If an access type is declared inside a subprogram, it can point to stack variables inside that subprogram. This is because no objects of that access type can be declared outside the subprogram and therefore it's not possible (barring unchecked tricks) for any object of this type to live after the subprogram is completed. It can also point to globals, or to heap objects. But it can't point to stack variables in a nested subprogram.

procedure Proc is
    type Node is ... 
    type Acc is access all Node;
    N1 : aliased Node;

    procedure Nested_Proc is
        N2 : aliased Node;
        X : Acc;
    begin
        X := N1'Access;   -- legal
        X := N2'Access;   -- illegal.  N2 is too deep for this access type.
    end;

So it's at the point where 'Access is used that the compiler makes sure that dangling references to no-longer-existing variables can't be created.

All this is governed by the accessibility rules, which are clearly spelled out in RM 3.10.2. (I'm kidding. 3.10.2 is very difficult to understand and tends to produce migraines and borderline insanity in those who try to read it.)

Edit: To follow up on your comment: Basically, I don't think the compiler is doing any sort of "robust analysis". Most of the rules are actually simpler than I made it sound. In Ada 2005, most access types, including most anonymous ones, have a "level" that depend on where the type is declared. If an access object's type is level L, it can't take an access value whose level is "deeper" (more nested) than L. Each anonymous access declares a new type, whose level usually depends on where it's declared. In your example that uses anonymous access types, the type of the next record field is library level since it's outside any procedure; the type of the result is deeper than that since it's inside a procedure. this.next := result is illegal because result, being deeper, could point to a stack variable, and this.next has a shallower level and thus this isn't allowed. For the named access type case, this.next := result is legal because result is just as shallow as the next field, and result wouldn't be allowed to point to a stack variable in the first place. In Ada 2012, I think it's different because the anonymous access objects have to keep track at runtime of the level of the thing they're point to. So this.next := result is legal, but (I think) will raise an exception at runtime if result points to a stack variable. In Ada 2012, these access objects will need some extra data to allow them to do this check; in Ada 2005, they could all be just simple pointers. (I could be wrong about some of the Ada 2012 changes.) But hopefully that isn't too complicated. The complications in 3.10.2 have to do with anonymous access parameters, anonymous access discriminants, and some other special cases that your example doesn't have anything to do with.

Answer 2

One solution is to restructure the code a bit; using an extended-return might do it for you:

type Node is record
  next: access Node;
end record;

function reverse_list(input: access Node) return access Node is
  this: access Node := input;
  next: access Node := null;
begin
  Return result: access Node := null do
    while this /= null loop
      next := this.next;
      this.next := result;
      result := this;
      this := next;
    end loop;
  end return;
end reverse_list;

While accessibility-checks can get frustrating, I have an overall good opinion of them: we do not want dangling pointers.