[OOP] SELECT TYPE with CLASS IS

[Janus Weil]

Hi all,

> here is an early shot at CLASS IS. As announced before, my
> implementation uses the library function "is_extension_of" that I
> introduced with the EXTENDS_TYPE_OF patch and translates the CLASS IS
> cases into a chain of IF/ELSE IF statements (you can have a look at
> the dump for the attached test case to see an example of the code it
> generates). The patch is not quite complete yet, since CLASS IS cases
> are not being sorted if they're in the wrong order. But apart from
> this, most things should work already. In particular the following
> cases:
>
>  * SELECT TYPE statements with only one CLASS IS branch
>  * those cases where the CLASS IS labels are not extensions of each other, or
>  * cases where the CLASS IS labels are sorted in the right way
> manually (i.e. extensions before their parents)
>
> If anyone wants to try it out or have a look at the patch, that would
> be great (the patch has to be applied to the fortran-dev branch, btw).
> I'll try to get the sorting right soon.

the attached version of the patch adds the sorting, and should be able
to produce the right runtime-behavior for any combination of CLASS IS
blocks.

My first thought regarding the sorting of the CLASS IS cases was to
simply go through the list and for any given pair determine if one
type is an extension of the other. However, this naive plan has some
problems:
1) For each pair, you have to do two operations: Check if A is an
extension of B. If not, check if B is an extension of A. This check
would involve stepping through the inheritance tree (which can be
quite large in extreme cases).
2) In this way, you can not find a unique order of the blocks, since
some of the types may not be related at all.

It just occurred to me a few hours ago that there is a much more
elegant and efficient way to do the sorting. For this, I took the
attr.extension bitfield that Paul introduced when he implemented type
extensions, and expanded it by a few bits, so that it not only
determines if the type if an extension of another, but instead
contains a number which describes the "extension level" of the type.
That is, if you draw an inheritance tree based on a certain base
class, the "extension level" is simply the level at which a certain
type is located (the basetype having extension=0, its direct
descendants having extension=1, etc).

This is a natural generalization of the extension field, since
extension=0 still means the type is no extension, while extension>0
means it is. So all the present code which checks the extension field
still works. For now I chose to make the field 8 bits wide, so that
inheritance trees with up to 255 levels are possible (the actual
number of types in the tree can be much larger), which I think is hard
to exceed with any reasonable application (am I being too naive
here?).

But most importantly, this "extension level" provides a natural
ordering scheme: Highest extension levels must always come first in
the CLASS IS chain, which guarantees that descendants come before
their parents. For equal extension levels, ordering does not matter.
And that's it!

Then I just made sure to correctly set the 'extension' field, when
constructing a derived type, and implemented a simple bubble-sort on
the singly-linked list of CLASS IS blocks, based on the 'extension'
field.

I successfully checked the patch for regressions. Do you guys have any
comments or suggestions, or is it okay if I commit to fortran-dev?
(Will write a ChangeLog and dejagnuify my test case soonish.)

Cheers,
Janus
-------------- next part --------------
A non-text attachment was scrubbed...
Name: class_is_sort.diff
Type: text/x-diff
Size: 16121 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/fortran/attachments/20091111/ca1a2d58/attachment.bin>