code review 4313064: gc: correctly handle fields of pointer type to recursiv...

gc: correctly handle fields of pointer type to recursive forward references

Previously, whether declaring a type which copied the structure of a type it was referenced in via a pointer field would work depended on whether you declared it before or after the type it copied, e.g. type T2 T1; type T1 struct { F *T2 } would work, however type T1 struct { F *T2 }; type T2 T1 wouldn't.

Fixes issue 667.

[lstoakes, 2011-03-31 23:01:02]

Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://go.googlecode.com/hg/

[lstoakes, 2011-03-31 23:36:38]

Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),

Please take another look.

[lstoakes, 2011-04-01 00:57:18]

Ack, we've got a problem when dealing with struct fields, delaying the
walkdef() prevents us from being able to complete the field
generation, e.g.

	if(n->type == T) {
					*t0 = T;
					return t0;
				}

kills us when the type isn't set.

Still, this patch covers most cases; I've had to get pretty contrived
to get this to be a problem, e.g.:-

type Foo struct {
	F3 *Blah	
	F1 *Bar
	F2 *Boo
}

type Bar Baz
type Baz Blah
type Blah Boo
type Boo Argh
type Argh Foo

I will keep on working to fix this also.

On 1 April 2011 00:36,  <lstoakes@gmail.com> wrote:
> Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),
>
> Please take another look.
>
>
> http://codereview.appspot.com/4313064/
>



-- 
Lorenzo Stoakes
http://www.codegrunt.co.uk

[lstoakes, 2011-04-01 01:03:44]

Ok, so a closer look reveals this is actually a problem with the patch
in general - the struct is not getting typechecked correctly at all,
as the following demonstrates:-

package main

type Foo struct {
	Next *Bar
}
type Bar Foo

func main() {
	_ = &Foo{&Bar{}}
	
}

error: 'too many values in struct initializer'

But rearranging the code so type Bar Foo comes first fixes this.

Let me fix this...!

On 1 April 2011 01:56, Lorenzo Stoakes <lstoakes@gmail.com> wrote:
> Ack, we've got a problem when dealing with struct fields, delaying the
> walkdef() prevents us from being able to complete the field
> generation, e.g.
>
>        if(n->type == T) {
>                                        *t0 = T;
>                                        return t0;
>                                }
>
> kills us when the type isn't set.
>
> Still, this patch covers most cases; I've had to get pretty contrived
> to get this to be a problem, e.g.:-
>
> type Foo struct {
>        F3 *Blah
>        F1 *Bar
>        F2 *Boo
> }
>
> type Bar Baz
> type Baz Blah
> type Blah Boo
> type Boo Argh
> type Argh Foo
>
> I will keep on working to fix this also.
>
> On 1 April 2011 00:36,  <lstoakes@gmail.com> wrote:
>> Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),
>>
>> Please take another look.
>>
>>
>> http://codereview.appspot.com/4313064/
>>
>
>
>
> --
> Lorenzo Stoakes
> http://www.codegrunt.co.uk
>



-- 
Lorenzo Stoakes
http://www.codegrunt.co.uk

[lstoakes, 2011-04-03 01:06:13]

Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),

Please take another look.

[lstoakes, 2011-04-03 01:11:45]

Ok - I have now fixed the previous issues. Before I was deferring the
walkdef() until after all top-level types had been constructed,
however that just leads to problems because things rely on the
typechecking having actually been done by that point, in particular
stotype(). Instead, I 'defer' copying type information for fields of
pointer type pointing to a type which has a TFORW type somewhere in
its ntype tree until after all top-level types have been constructed.
In fact, we are not technically deferring this, but rather letting
these types stay at TFORW, until they are eventually corrected
afterwards.

I have also updated the fixedbug .go file to something which actually
checks properly whether you can construct the resultant types, as well
as covering every edge-case type I came across. Everything looks good,
and the patch is working and fixes issue 667.

If I'm not clear please forgive me, 2am here in the UK and been a
manic rush to get this one fixed properly :)

Cheers,

Lorenzo

On 3 April 2011 02:06,  <lstoakes@gmail.com> wrote:
> Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),
>
> Please take another look.
>
>
> http://codereview.appspot.com/4313064/
>



-- 
Lorenzo Stoakes
http://www.codegrunt.co.uk

[rsc, 2011-04-07 16:56:34]

http://codereview.appspot.com/4313064/diff/12001/src/cmd/gc/typecheck.c
File src/cmd/gc/typecheck.c (right):

http://codereview.appspot.com/4313064/diff/12001/src/cmd/gc/typecheck.c#newco...
src/cmd/gc/typecheck.c:35: static uchar	isind;
delete

http://codereview.appspot.com/4313064/diff/12001/src/cmd/gc/typecheck.c#newco...
src/cmd/gc/typecheck.c:145: if(isind && n->op == OTYPE && (ft =
walkforwtype(n->ntype)))
s/isind/(top&Eindir)/

http://codereview.appspot.com/4313064/diff/12001/src/cmd/gc/walk.c
File src/cmd/gc/walk.c (right):

http://codereview.appspot.com/4313064/diff/12001/src/cmd/gc/walk.c#newcode2405
src/cmd/gc/walk.c:2405: walkforwtype(Node *n) {
brace on new line please

also please make this not recursive.

Type*
walkforwtype(Node *n)
{
    for(;;) {
        if(n == N)
            return T;
        if(n->type && n->type->etype == TFORW)
            return n->type;
        switch(n->op) {
        default:
            return T;
        case OTYPE:
            n = n->ntype;
            break;
        case ONONAME:
            n = n->sym->def;
            break;
        }
    }
}

also rename to getforwtype and move to typecheck.c
where it is used and can be static.

[lstoakes, 2011-04-07 18:18:25]

I am out of country for a couple more days, so will be a slight delay
before getting these done :)

On Thursday, 7 April 2011,  <rsc@golang.org> wrote:

>>http://codereview.appspot.com/4313064/diff/12001/src/cmd/gc/typecheck.c#newcode145
> src/cmd/gc/typecheck.c:145: if(isind && n->op == OTYPE && (ft =
> walkforwtype(n->ntype)))
> s/isind/(top&Eindir)/
>
>

I thought the same; however this doesn't work when you nest anonymous
strict declarations in a type, as by the time the typechecker has got
to this point the Eindir has disappeared. I could however modify the
CL to 'remember' the Eindir and pass it through, I didn't do this
previously as I worried it could imply the struct was declared as a
pointer type.

Am happy to attempt this and re-submit to show you what I mean once I
have access to a computer again in a couple of days :)

I agree with all the other comments and will fix then also.

-- 
Lorenzo Stoakes
http://www.codegrunt.co.uk

[lstoakes, 2011-04-07 18:19:05]

Strict = struct. Using phone with autocorrect...

On Thursday, 7 April 2011, Lorenzo Stoakes <lstoakes@gmail.com> wrote:
> I am out of country for a couple more days, so will be a slight delay
> before getting these done :)
>
> On Thursday, 7 April 2011,  <rsc@golang.org> wrote:
>
>>>http://codereview.appspot.com/4313064/diff/12001/src/cmd/gc/typecheck.c#newcode145
>> src/cmd/gc/typecheck.c:145: if(isind && n->op == OTYPE && (ft =
>> walkforwtype(n->ntype)))
>> s/isind/(top&Eindir)/
>>
>>
>
> I thought the same; however this doesn't work when you nest anonymous
> strict declarations in a type, as by the time the typechecker has got
> to this point the Eindir has disappeared. I could however modify the
> CL to 'remember' the Eindir and pass it through, I didn't do this
> previously as I worried it could imply the struct was declared as a
> pointer type.
>
> Am happy to attempt this and re-submit to show you what I mean once I
> have access to a computer again in a couple of days :)
>
> I agree with all the other comments and will fix then also.
>
> --
> Lorenzo Stoakes
> http://www.codegrunt.co.uk
>

-- 
Lorenzo Stoakes
http://www.codegrunt.co.uk

[lstoakes, 2011-04-10 16:05:07]

Hello rsc (cc: golang-dev@googlegroups.com),

Please take another look.

[lstoakes, 2011-04-11 10:59:05]

Ah, actually - I need to make a few more changes to get issue 1672 as
well as 667 (1672 was merged into 667). One sec.

On 10 April 2011 17:05,  <lstoakes@gmail.com> wrote:
> Hello rsc (cc: golang-dev@googlegroups.com),
>
> Please take another look.
>
>
> http://codereview.appspot.com/4313064/
>



-- 
Lorenzo Stoakes
http://www.codegrunt.co.uk

[lstoakes, 2011-04-11 11:37:54]

Hello rsc (cc: golang-dev@googlegroups.com),

Please take another look.

[lstoakes, 2011-04-11 11:44:43]

All fixed up.

We are now sometimes passing around the current 'top' value in
typecheck(), amending it as we go, and sometimes simply making nested
calls to typecheck with a brand new top argument which seems quite
inconsistent. However, if you do start going down the road of making
sure any nested call to typecheck() contains all previous top bit
flags regressions occur, also doing so seems really rather out of the
scope of this CL.

I think it's fine to go ahead with this approach for now, and perhaps
fix the inconsistency in a separate CL. All tests pass under this CL,
incidentally.

On 11 April 2011 12:37,  <lstoakes@gmail.com> wrote:
> Hello rsc (cc: golang-dev@googlegroups.com),
>
> Please take another look.
>
>
> http://codereview.appspot.com/4313064/
>



-- 
Lorenzo Stoakes
http://www.codegrunt.co.uk

[lstoakes, 2011-04-14 12:08:17]

Let me know if there is anything else you need on this; note that I
also added cycle detection to the getforwtype() function to avoid
infinite loops if, somehow, n->ntype cycles.

On 11 April 2011 12:44, Lorenzo Stoakes <lstoakes@gmail.com> wrote:
> All fixed up.
>
> We are now sometimes passing around the current 'top' value in
> typecheck(), amending it as we go, and sometimes simply making nested
> calls to typecheck with a brand new top argument which seems quite
> inconsistent. However, if you do start going down the road of making
> sure any nested call to typecheck() contains all previous top bit
> flags regressions occur, also doing so seems really rather out of the
> scope of this CL.
>
> I think it's fine to go ahead with this approach for now, and perhaps
> fix the inconsistency in a separate CL. All tests pass under this CL,
> incidentally.
>
> On 11 April 2011 12:37,  <lstoakes@gmail.com> wrote:
>> Hello rsc (cc: golang-dev@googlegroups.com),
>>
>> Please take another look.
>>
>>
>> http://codereview.appspot.com/4313064/
>>
>
>
>
> --
> Lorenzo Stoakes
> http://www.codegrunt.co.uk
>



-- 
Lorenzo Stoakes
http://www.codegrunt.co.uk

[lstoakes, 2011-04-19 17:13:57]

Hello rsc (cc: golang-dev@googlegroups.com),

Please take another look.

[lstoakes, 2011-04-25 15:09:29]

Hi,

Wondered whether there was any update on this patch? I don't mean to
be impatient, and forgive me if it is simply a matter of other, higher
priority tasks taking precedence, but just wanted to know where we
were with it. I am happy to make any changes necessary to get it in
:-)

Lorenzo

On 19 April 2011 18:13,  <lstoakes@gmail.com> wrote:
> Hello rsc (cc: golang-dev@googlegroups.com),
>
> Please take another look.
>
>
> http://codereview.appspot.com/4313064/
>



-- 
Lorenzo Stoakes
http://www.codegrunt.co.uk

[rsc, 2011-04-25 15:43:56]

it's on a long but shrinking list

[lstoakes, 2011-04-25 16:10:25]

On 25 April 2011 16:43, Russ Cox <rsc@golang.org> wrote:
> it's on a long but shrinking list
>

Ok, cool, thanks, apologies for sounding a little impatient, but just
wanted to make sure it was still alive :-)

Cheers, Lorenzo


-- 
Lorenzo Stoakes
http://www.codegrunt.co.uk

[rsc, 2011-04-25 20:53:26]

http://codereview.appspot.com/4313064/diff/38001/src/cmd/gc/walk.c
File src/cmd/gc/walk.c (right):

http://codereview.appspot.com/4313064/diff/38001/src/cmd/gc/walk.c#newcode134
src/cmd/gc/walk.c:134: deferredtypecopy = list(deferredtypecopy, n);
parallel lists always cause bugs.  use one list.
also there are going to be many of these.
it's worth using code similar to what's in gc/align.c
for checkwidth to maintain the list.

http://codereview.appspot.com/4313064/diff/38001/src/cmd/gc/walk.c#newcode142
src/cmd/gc/walk.c:142: resumetypecopy()
s/()/(void)/

http://codereview.appspot.com/4313064/diff/38001/src/cmd/gc/walk.c#newcode158
src/cmd/gc/walk.c:158: copytype(Node *n, Type *t)
shouldn't be static; please call from typedcl2 too

http://codereview.appspot.com/4313064/diff/38001/src/cmd/gc/walk.c#newcode240
src/cmd/gc/walk.c:240: walkdef(Node *n, int top)
I don't understand why top is being threaded through all of this.
Isn't it still correct to just do the copy this way all the time?
It seems like that would be less code.

http://codereview.appspot.com/4313064/diff/38001/test/fixedbugs/bug328.go
File test/fixedbugs/bug328.go (right):

http://codereview.appspot.com/4313064/diff/38001/test/fixedbugs/bug328.go#new...
test/fixedbugs/bug328.go:9: <<<<<<< local
oops  :-)

[lstoakes, 2011-04-26 16:07:24]

Hello rsc (cc: golang-dev@googlegroups.com),

Please take another look.

[rsc, 2011-04-26 16:10:42]

http://codereview.appspot.com/4313064/diff/38001/src/cmd/gc/walk.c
File src/cmd/gc/walk.c (right):

http://codereview.appspot.com/4313064/diff/38001/src/cmd/gc/walk.c#newcode240
src/cmd/gc/walk.c:240: walkdef(Node *n, int top)
On 2011/04/25 20:53:26, rsc wrote:
> I don't understand why top is being threaded through all of this.
> Isn't it still correct to just do the copy this way all the time?
> It seems like that would be less code.

still applies

[lstoakes, 2011-04-26 16:10:57]

On 25 April 2011 21:53,  <rsc@golang.org> wrote:
>
> http://codereview.appspot.com/4313064/diff/38001/src/cmd/gc/walk.c
> File src/cmd/gc/walk.c (right):
>
> http://codereview.appspot.com/4313064/diff/38001/src/cmd/gc/walk.c#newcode134
> src/cmd/gc/walk.c:134: deferredtypecopy = list(deferredtypecopy, n);
> parallel lists always cause bugs.  use one list.
> also there are going to be many of these.
> it's worth using code similar to what's in gc/align.c
> for checkwidth to maintain the list.

Done.

>
> http://codereview.appspot.com/4313064/diff/38001/src/cmd/gc/walk.c#newcode142
> src/cmd/gc/walk.c:142: resumetypecopy()
> s/()/(void)/

Done.

>
> http://codereview.appspot.com/4313064/diff/38001/src/cmd/gc/walk.c#newcode158
> src/cmd/gc/walk.c:158: copytype(Node *n, Type *t)
> shouldn't be static; please call from typedcl2 too

Done.

>
> http://codereview.appspot.com/4313064/diff/38001/src/cmd/gc/walk.c#newcode240
> src/cmd/gc/walk.c:240: walkdef(Node *n, int top)
> I don't understand why top is being threaded through all of this.
> Isn't it still correct to just do the copy this way all the time?
> It seems like that would be less code.

Unfortunately not checking whether we're ultimately 'coming from' a
pointer type somewhere in the tree breaks recursive type checking for
cases like:-

type T T

and:-

type T1 T2
type T2 T3
type T3 T1

So we have to keep this check in place. This manifests as regressions
in fixed bugs 224 and 256 (as they contain 'type T T' or equivalent)

An aside:- I found a bug in the cycle checker (which this triggers) in
getforwtype which is now fixed.

>
> http://codereview.appspot.com/4313064/diff/38001/test/fixedbugs/bug328.go
> File test/fixedbugs/bug328.go (right):
>
>
http://codereview.appspot.com/4313064/diff/38001/test/fixedbugs/bug328.go#new...
> test/fixedbugs/bug328.go:9: <<<<<<< local
> oops  :-)

*ahem* fixed :-)

-- 
Lorenzo Stoakes
http://www.codegrunt.co.uk

[lstoakes, 2011-04-26 16:11:32]

On 26 April 2011 17:10,  <rsc@golang.org> wrote:

> still applies

Too quick for me :-)

See above note.


-- 
Lorenzo Stoakes
http://www.codegrunt.co.uk

[lstoakes, 2011-04-26 16:12:30]

On 26 April 2011 17:11, Lorenzo Stoakes <lstoakes@gmail.com> wrote:

> See above note.

However, there might be a nicer way of doing this without threading
'top' through everything. I am happy to investigate further.

-- 
Lorenzo Stoakes
http://www.codegrunt.co.uk

[lstoakes, 2011-04-26 16:24:47]

On 26 April 2011 17:12, Lorenzo Stoakes <lstoakes@gmail.com> wrote:

> However, there might be a nicer way of doing this without threading
> 'top' through everything. I am happy to investigate further.

Aha! I can simply have the cycle detector return T rather than fire a
fatal error should a cycle be detected.

I am removing the threading as we speak... :)

-- 
Lorenzo Stoakes
http://www.codegrunt.co.uk

[lstoakes, 2011-04-26 16:57:39]

Hello rsc (cc: golang-dev@googlegroups.com),

Please take another look.

[rsc, 2011-04-28 03:58:24]

LGTM

[rsc, 2011-04-28 04:13:52]

*** Submitted as http://code.google.com/p/go/source/detail?r=3c73bb78da9a ***

gc: correctly handle fields of pointer type to recursive forward references

Previously, whether declaring a type which copied the structure of a type it was
referenced in via a pointer field would work depended on whether you declared it
before or after the type it copied, e.g. type T2 T1; type T1 struct { F *T2 }
would work, however type T1 struct { F *T2 }; type T2 T1 wouldn't.

Fixes issue 667.

R=rsc
CC=golang-dev
http://codereview.appspot.com/4313064

Committer: Russ Cox <rsc@golang.org>