Elaboration circularity with generics

Elaboration circularity with generics

[Maciej Sobczak]

Consider:

--  p.ads:
package P is
   procedure Proc;
end P;

--  p.adb:
with P.Q;
package body P is
   package P_Int is new P.Q (T => Integer);

   procedure Proc is
   begin
      P_Int.Proc;
   end Proc;
end P;

--  p-q.ads:
generic
   type T is private;
package P.Q is
   procedure Proc;
end P.Q;

--  p-q.adb:
package body P.Q is
   procedure Proc is
   begin
      null;
   end Proc;
end P.Q;

--  test.adb:
with P;

procedure Test is
begin
   null;
end Test;

The idea is that P.Q is a child, helper unit for P and P.Q is used in
the body of P.
Ideally it should be a private child, but these cannot be generic
(why?).

Forget the Proc procedures, they do not contribute to the actual
problem, but where needed to have meaningful source units.
The problem above is:

$ gnatmake test
gcc -c test.adb
gcc -c p.adb
gcc -c p-q.adb
gnatbind -x test.ali
error: elaboration circularity detected
info:    "p (body)" must be elaborated before "p (body)"
info:       reason: implicit Elaborate_All in unit "p (body)"
info:       recompile "p (body)" with -gnatwl for full details
info:          "p (body)"
info:             must be elaborated along with its spec:
info:          "p (spec)"
info:             which is withed by:
info:          "p.q (spec)"
info:             which is withed by:
info:          "p (body)"

gnatmake: *** bind failed.

Why this circular dependency? It does not exist if P.Q is not generic.
My initial version of P.Q was a regular package and I have found this
problem after turning it into a generic package.

A simple workaround is to make P_Q instead of P.Q, but I would like
understand where the circularity comes from. The -gnatwl option says
that some Elaborate_All is introduced at the instantiation of P.Q, but
I see no reason for circularity there.

--
Maciej Sobczak * http://www.msobczak.com * http://www.inspirel.com

Re: Elaboration circularity with generics

[Martin Dowie]

Maciej Sobczak <see.my.homepage@gmail.com> wrote:
> Consider:
> 
> --  p.ads:
> package P is
>    procedure Proc;
> end P;
> 
> --  p.adb:
> with P.Q;
> package body P is
>    package P_Int is new P.Q (T => Integer);
> 
>    procedure Proc is
>    begin
>       P_Int.Proc;
>    end Proc;
> end P;
> 
> --  p-q.ads:
> generic
>    type T is private;
> package P.Q is
>    procedure Proc;
> end P.Q;
> 
> --  p-q.adb:
> package body P.Q is
>    procedure Proc is
>    begin
>       null;
>    end Proc;
> end P.Q;
> 
> --  test.adb:
> with P;
> 
> procedure Test is
> begin
>    null;
> end Test;
> 
> The idea is that P.Q is a child, helper unit for P and P.Q is used in
> the body of P.
> Ideally it should be a private child, but these cannot be generic
> (why?).
> 
> Forget the Proc procedures, they do not contribute to the actual
> problem, but where needed to have meaningful source units.
> The problem above is:
> 
> $ gnatmake test
> gcc -c test.adb
> gcc -c p.adb
> gcc -c p-q.adb
> gnatbind -x test.ali
> error: elaboration circularity detected
> info:    "p (body)" must be elaborated before "p (body)"
> info:       reason: implicit Elaborate_All in unit "p (body)"
> info:       recompile "p (body)" with -gnatwl for full details
> info:          "p (body)"
> info:             must be elaborated along with its spec:
> info:          "p (spec)"
> info:             which is withed by:
> info:          "p.q (spec)"
> info:             which is withed by:
> info:          "p (body)"
> 
> gnatmake: *** bind failed.
> 
> Why this circular dependency? It does not exist if P.Q is not generic.
> My initial version of P.Q was a regular package and I have found this
> problem after turning it into a generic package.
> 
> A simple workaround is to make P_Q instead of P.Q, but I would like
> understand where the circularity comes from. The -gnatwl option says
> that some Elaborate_All is introduced at the instantiation of P.Q, but
> I see no reason for circularity there.
> 
> --
> Maciej Sobczak * http://www.msobczak.com * http://www.inspirel.com

I think a better way is to make the instantiation another child, e.g.

package P.Q.Integers is new P.Q (Integer);
pragma Preelaborate (P.Q.Integers);

Then it is available to other packages that may need it too.


-- Martin
-- 
-- Sent from my iPad

Re: Elaboration circularity with generics

[AdaMagica]

A unit can only be instantiated if it is fully elaborated.
I guess GNAT chose the elaboration order P'Spec, P.Q'Spec, P'Body
(crash since P.Q'body is not elaborated).
This dependence is not present for nongeneric units.

Perhaps addition of pragma Elaborate_Body to P.Q helps.

Re: Elaboration circularity with generics

[AdaMagica]

On 14 Jan., 16:09, Maciej Sobczak <see.my.homep...@gmail.com> wrote:
> Ideally it should be a private child, but these cannot be generic
> (why?).

Of course it can:

private generic
package P.Q is
...

But such a private generic can only be instantiated within the
hierarchy of P (of course).

Re: Elaboration circularity with generics

[Georg Bauhaus]

Maciej Sobczak <see.my.homepage@gmail.com> wrote:
> The -gnatwl option says
> that some Elaborate_All is introduced at the instantiation of P.Q, but
> I see no reason for circularity there.

The circularity vanishes with -gnatE, and the warning message
changes, too. So I guess the circularity is a consequence of
GNAT's default, static elaboration order algorithm. IIRC, some,
though not all of this algorithm is explained in the manual
(else in the source text).

Re: Elaboration circularity with generics

[Simon Wright]

AdaMagica <christ-usch.grein@t-online.de> writes:

> A unit can only be instantiated if it is fully elaborated.
> I guess GNAT chose the elaboration order P'Spec, P.Q'Spec, P'Body
> (crash since P.Q'body is not elaborated).
> This dependence is not present for nongeneric units.
>
> Perhaps addition of pragma Elaborate_Body to P.Q helps.

   with P.Q;
   pragma Elaborate (P.Q);          <<<<<<< does the trick for me
   package body P is

I have to say that elaboration problems are often mindboggling (the best
I remember was when GNAT 3.09 reported an elaboration cycle of 157 where
there were only 156 units in the program).

Re: Elaboration circularity with generics

[AdaMagica]

On 14 Jan., 23:46, Simon Wright <si...@pushface.org> wrote:
> AdaMagica <christ-usch.gr...@t-online.de> writes:
> > A unit can only be instantiated if it is fully elaborated.
> > I guess GNAT chose the elaboration order P'Spec, P.Q'Spec, P'Body
> > (crash since P.Q'body is not elaborated).
> > This dependence is not present for nongeneric units.
>
> > Perhaps addition of pragma Elaborate_Body to P.Q helps.
>
>    with P.Q;
>    pragma Elaborate (P.Q);          <<<<<<< does the trick for me
>    package body P is

Of course this works, but in my opinion, Elaborate_Body is better
because it has to be applied just once to P.Q, whereas Elaborate has
to be applied on every unit withing P.Q.

As a general rule of thumb I think Elaborate_Body should be applied
whenever a unit provides functions that are used in the spec of other
units providing initial values or constants, such like:

package P is
  pragma Elaborate_Body;  -- prevents elaboration error when F is
called
  function F (...) return T;
end P;

with P;  -- no need for "pragma Elaborate (P);"
package Q is
  V: [constant] T := P.F (...);
end Q;

Re: Elaboration circularity with generics

[Maciej Sobczak]

On Jan 14, 11:01 pm, Georg Bauhaus <rm-host.bauh...@maps.arcor.de>
wrote:

> So I guess the circularity is a consequence of
> GNAT's default, static elaboration order algorithm.

Does it mean that the compiler can refuse legal code just because its
internal algorithm is biased?
As I understand, there is no language-related reason for the
circularity. That is, there is no ARM paragraph that would say that in
this particular program there will be a cyclic elaboration dependency
(otherwise I would appreciate some pointers).

In such a case I would consider it to be a compiler bug.

--
Maciej Sobczak * http://www.msobczak.com * http://www.inspirel.com

Re: Elaboration circularity with generics

[AdaMagica]

On 15 Jan., 18:15, Maciej Sobczak <see.my.homep...@gmail.com> wrote:
> In such a case I would consider it to be a compiler bug.

No, this isn't a bug. The elaboration order is not completely defined.
If the compiler cannot find a valid order, it may reject the program.
The programmer then has to help the compiler with pragmas.

A compiler is not required to try out all sorts of elaboration orders.
This is for simplifying the compiler. There are about O(n!) orders.

Re: Elaboration circularity with generics

[Robert A Duff]

Maciej Sobczak <see.my.homepage@gmail.com> writes:

> Does it mean that the compiler can refuse legal code just because its
> internal algorithm is biased?
> As I understand, there is no language-related reason for the
> circularity. That is, there is no ARM paragraph that would say that in
> this particular program there will be a cyclic elaboration dependency
> (otherwise I would appreciate some pointers).

By default, GNAT uses a static elaboration model.  This is a
non-standard mode -- it does not follow the rules in the Ada RM.
If you want the standard mode, you have to turn it on explicitly.

I suggest you read the section about elaboration in the gnat
docs -- it's rather long, but it should explain everything.

One advantage of the static elaboration model is that you
don't get any run-time elaboration checks.  Another is that
you don't need to put elaboration control pragmas all
over the place.  (On rare occassions, you might need one.)
But the static elaboration model is (necessarily) more
restrictive in that it will disallow certain cases that
are allowed by the standard (dynamic) model.

> In such a case I would consider it to be a compiler bug.

I don't see any compiler bug here.

I see some Ada language-design bugs, though.  ;-)

- Bob

Re: Elaboration circularity with generics

[Simon Wright]

AdaMagica <christ-usch.grein@t-online.de> writes:

> On 14 Jan., 23:46, Simon Wright <si...@pushface.org> wrote:
>> AdaMagica <christ-usch.gr...@t-online.de> writes:
>> > A unit can only be instantiated if it is fully elaborated.
>> > I guess GNAT chose the elaboration order P'Spec, P.Q'Spec, P'Body
>> > (crash since P.Q'body is not elaborated).
>> > This dependence is not present for nongeneric units.
>>
>> > Perhaps addition of pragma Elaborate_Body to P.Q helps.
>>
>>    with P.Q;
>>    pragma Elaborate (P.Q);          <<<<<<< does the trick for me
>>    package body P is
>
> Of course this works, but in my opinion, Elaborate_Body is better
> because it has to be applied just once to P.Q, whereas Elaborate has
> to be applied on every unit withing P.Q.
>
> As a general rule of thumb I think Elaborate_Body should be applied
> whenever a unit provides functions that are used in the spec of other
> units providing initial values or constants, such like:
>
> package P is
>   pragma Elaborate_Body;  -- prevents elaboration error when F is
> called
>   function F (...) return T;
> end P;
>
> with P;  -- no need for "pragma Elaborate (P);"
> package Q is
>   V: [constant] T := P.F (...);
> end Q;

That may be true in general, but *in this case* it does not solve the
problem;

   generic
      type T is private;
   package P.Q is
      pragma Elaborate_Body;
      procedure Proc;
   end P.Q;

then

   $ gnatmake test
   gcc -c test.adb
   gcc -c p.adb
   gcc -c p-q.adb
   gnatbind -x test.ali
   error: elaboration circularity detected
   info:    "p (body)" must be elaborated before "p (body)"
   info:       reason: implicit Elaborate_All in unit "p (body)"
   info:       recompile "p (body)" with -gnatwl for full details
   info:          "p (body)"
   info:             must be elaborated along with its spec:
   info:          "p (spec)"
   info:             which is withed by:
   info:          "p.q (spec)"
   info:             which is withed by:
   info:          "p (body)"

   gnatmake: *** bind failed.

-gnatE still succeeds (provided you remember to rebuild the world!)

Re: Elaboration circularity with generics

[Adam Beneschan]

On Jan 15, 9:43 am, AdaMagica <christ-usch.gr...@t-online.de> wrote:
> On 15 Jan., 18:15, Maciej Sobczak <see.my.homep...@gmail.com> wrote:
>
> > In such a case I would consider it to be a compiler bug.
>
> No, this isn't a bug. The elaboration order is not completely defined.
> If the compiler cannot find a valid order, it may reject the program.
> The programmer then has to help the compiler with pragmas.

I think some clarification may help.  There's a rule in 10.2(18) that
says "there shall be a total order of the library_items that obeys the
above rules".  This rule is simple enough that any compiler should be
able to follow it; so if there is a total order and a compiler cannot
find it, the compiler definitely has a bug.

However, the compiler is *not* required to try to find an elaboration
order that will guarantee that Program_Error is not raised at
runtime.  Technically, a program that follows the language rules but
is certain to fail as soon as it's run should not be rejected by the
compiler, since it's a legal Ada program.  But it's useful for
compilers to report errors in such cases.  This may make it "non-
standard" in some sense, but I wouldn't consider it a bug if the
behavior is documented and an option is provided to follow the
standard technically.

                            -- Adam

Re: Elaboration circularity with generics

[AdaMagica]

On 16 Jan., 16:09, Simon Wright <si...@pushface.org> wrote:
> AdaMagica <christ-usch.gr...@t-online.de> writes:
> > On 14 Jan., 23:46, Simon Wright <si...@pushface.org> wrote:
> >> AdaMagica <christ-usch.gr...@t-online.de> writes:
> >> > A unit can only be instantiated if it is fully elaborated.
> >> > I guess GNAT chose the elaboration order P'Spec, P.Q'Spec, P'Body
> >> > (crash since P.Q'body is not elaborated).
> >> > This dependence is not present for nongeneric units.
>
> >> > Perhaps addition of pragma Elaborate_Body to P.Q helps.
>
> >>    with P.Q;
> >>    pragma Elaborate (P.Q);          <<<<<<< does the trick for me
> >>    package body P is
>
> > Of course this works, but in my opinion, Elaborate_Body is better
> > because it has to be applied just once to P.Q, whereas Elaborate has
> > to be applied on every unit withing P.Q.
>
> > As a general rule of thumb I think Elaborate_Body should be applied
> > whenever a unit provides functions that are used in the spec of other
> > units providing initial values or constants, such like:
>
> > package P is
> >   pragma Elaborate_Body;  -- prevents elaboration error when F is
> > called
> >   function F (...) return T;
> > end P;
>
> > with P;  -- no need for "pragma Elaborate (P);"
> > package Q is
> >   V: [constant] T := P.F (...);
> > end Q;
>
> That may be true in general, but *in this case* it does not solve the
> problem;
>
>    generic
>       type T is private;
>    package P.Q is
>       pragma Elaborate_Body;
>       procedure Proc;
>    end P.Q;
>
> then
>
>    $ gnatmake test
>    gcc -c test.adb
>    gcc -c p.adb
>    gcc -c p-q.adb
>    gnatbind -x test.ali
>    error: elaboration circularity detected
>    info:    "p (body)" must be elaborated before "p (body)"
>    info:       reason: implicit Elaborate_All in unit "p (body)"
>    info:       recompile "p (body)" with -gnatwl for full details
>    info:          "p (body)"
>    info:             must be elaborated along with its spec:
>    info:          "p (spec)"
>    info:             which is withed by:
>    info:          "p.q (spec)"
>    info:             which is withed by:
>    info:          "p (body)"
>
>    gnatmake: *** bind failed.
>
> -gnatE still succeeds (provided you remember to rebuild the world!)

Ha, yes, because of the implicit Elaborate_All implied by the
nonstandard behaviour of GNAT (I didn't think of this connection).
Obviously with standard Ada behaviour (-gnatE), GNAT can find a good
order without the pragma (there is no Elaborate_All in this case).

But I think the rule of thumb should be followed nevertheless. (It's
only a rule of thumb because Elaborate_Body is sometimes impossible.)

Re: Elaboration circularity with generics

[Maciej Sobczak]

On Jan 16, 3:34 pm, Robert A Duff <bobd...@shell01.TheWorld.com>
wrote:

> > In such a case I would consider it to be a compiler bug.
>
> I don't see any compiler bug here.

What I'm concerned about is portability. If the compiler is allowed to
refuse my program even though there is no paragraph saying that my
program is illegal, then perhaps some other compiler will compile it
without any trouble. Which means that my program will not be portable,
even though it might not touch any implementation limits or other
similarly valid reasons.

--
Maciej Sobczak * http://www.msobczak.com * http://www.inspirel.com

Re: Elaboration circularity with generics

[Adam Beneschan]

On Jan 16, 1:29 pm, Maciej Sobczak <see.my.homep...@gmail.com> wrote:
> On Jan 16, 3:34 pm, Robert A Duff <bobd...@shell01.TheWorld.com>
> wrote:
>
> > > In such a case I would consider it to be a compiler bug.
>
> > I don't see any compiler bug here.
>
> What I'm concerned about is portability. If the compiler is allowed to
> refuse my program even though there is no paragraph saying that my
> program is illegal, then perhaps some other compiler will compile it
> without any trouble. Which means that my program will not be portable,
> even though it might not touch any implementation limits or other
> similarly valid reasons.

The problem is that without any additional Elaborate pragmas, a
compiler *could* compile the program, but it would be useless as it
would raise Program_Error right away.  Another compiler might build
the program and choose a different elaboration order that doesn't
raise Program_Error.  Neither of these compilers would be wrong, since
the language doesn't specify the exact elaboration order when there is
more than one that obeys the Elaborate pragmas and other language
rules.  So your program as written isn't portable at all; and even
though technically a compiler should accept the program, if you're
concerned about portability then you should be grateful that GNAT (in
its non-standard mode) rejected the program and alerted you to the
portability problem in your code.  I don't think you have a legitimate
complaint about GNAT here, at least not on portability grounds.

                             -- Adam

Re: Elaboration circularity with generics

[Robert A Duff]

Maciej Sobczak <see.my.homepage@gmail.com> writes:

> On Jan 16, 3:34�pm, Robert A Duff <bobd...@shell01.TheWorld.com>
> wrote:
>
>> > In such a case I would consider it to be a compiler bug.
>>
>> I don't see any compiler bug here.
>
> What I'm concerned about is portability.

A very legitimate concern!

>...If the compiler is allowed to
> refuse my program even though there is no paragraph saying that my
> program is illegal,...

That's not the problem.  If your program is legal (I didn't look
at it carefully), then all Ada compilers will accept it.  In particular,
GNAT will accept it in standard-conforming mode.  You didn't use the
standard-conforming mode.

The problem (a language problem) is that in standard-conforming mode,
different Ada compilers are allowed to choose different elaboration
orders.  One order might work, and another order might raise
Program_Error.

In order to write portable code, you have to sprinkle elaboration
control pragmas all over the place (mostly pragma Elaborate_All).
And doing that by hand is a super-human task.  That's a language
problem -- you can't blame any particular Ada compiler.

Note that GNAT has a switch that will tell you where to put
pragma Elaborate_All.

Again, I suggest reading the elaboration section of the
GNAT docs -- it explains all this stuff in great detail.

>... then perhaps some other compiler will compile it
> without any trouble. Which means that my program will not be portable,
> even though it might not touch any implementation limits or other
> similarly valid reasons.

- Bob