code review 12552047: go.tools/go.types: retain ast.Node links on demand only (issue 12552047)

[g...@golang.org]

Reviewers: adonovan, r,

Message:
Hello adon...@google.com, r...@golang.org (cc:
golan...@googlegroups.com),

I'd like you to review this change to
https://code.google.com/p/go.tools


Description:
go.tools/go.types: retain ast.Node links on demand only

- support Info.Scopes mapping that maps ast.Nodes
to the respective *Scope
- remove old node link from *Scope
- added corresponding API test

Also: re-enable debug mode (the faster version was
only important for the go api tool, which has its
own version now).

Please review this at https://codereview.appspot.com/12552047/

Affected files:
M go/types/api.go
M go/types/api_test.go
M go/types/check.go
M go/types/resolver.go
M go/types/scope.go
M go/types/stmt.go
M go/types/typexpr.go

[r...@golang.org]

LGTM

https://codereview.appspot.com/12552047/

[g...@golang.org]

*** Submitted as
https://code.google.com/p/go/source/detail?r=15ba0a163203&repo=tools ***

go.tools/go.types: retain ast.Node links on demand only

- support Info.Scopes mapping that maps ast.Nodes
to the respective *Scope
- remove old node link from *Scope
- added corresponding API test

Also: re-enable debug mode (the faster version was
only important for the go api tool, which has its
own version now).

R=adonovan, r
CC=golang-dev
https://codereview.appspot.com/12552047


https://codereview.appspot.com/12552047/

[rocky.b...@gmail.com]

What changes (if any) need to be made in the ssa-interpreter need to
allow it access to the ast as it was before this change?

I see the Scopes field (map[ast.Node]*Scope) added now to types.Info and
field "node" removed from the Scopes type and some sort of make() needed
after types.Info is created, but ssa uses
importer.CreatePackageFromArgs.

https://codereview.appspot.com/12552047/

[Robert Griesemer]

No changes are needed I think. ssa didn't use that information in the first place.

- gri

[rocky.b...@gmail.com]

Yes, sure, the ssa interpreter doesn't use that information, but the
fork of it on github to support debugging does. And I've started
removing the lossy Pos information in that ssa interpreter by using
position information from the ast.

(Currently it is as a start and end position but eventually, I'll
probably add the single interval number/index I mentioned)

I think I recall you suggesting that one could use information from the
ast to get the more accurate range information rather than use the lossy
canonical form that is in the ssa interpreter. I had said okay, and then
you don't need that "canonical Pos" at all. But this assumes one has the
ast position information.

Later, Alan had said he thought he would eventually remove that
canonical Pos information, although that hasn't happened yet.

On 2013/08/10 00:57:49, gri wrote:
> No changes are needed I think. ssa didn't use that information in the
first
> place.
> - gri

> On Fri, Aug 9, 2013 at 5:53 PM, <mailto:rocky.b...@gmail.com>

wrote:

> > What changes (if any) need to be made in the ssa-interpreter need to
> > allow it access to the ast as it was before this change?
> >
> > I see the Scopes field (map[ast.Node]*Scope) added now to types.Info
and
> > field "node" removed from the Scopes type and some sort of make()
needed
> > after types.Info is created, but ssa uses

> > importer.**CreatePackageFromArgs.
> >
> >

https://codereview.appspot.**com/12552047/%3Chttps://codereview.appspot.com/12552047/>
> >



https://codereview.appspot.com/12552047/

[Robert Griesemer]

It's trivial to add the information if you need it. The importer allocates all maps in one place, and you just add a additional line for a Scopes map and copy the pattern used for the other maps.

The main difference is that now the information provided is from nodes to scopes, while before the information was from scopes to nodes. But it's trivially inverted if there is need for it.

I'll leave it to Alan to make the respective changes in importer - my primary goal at the moment is to get go/types completed. Alan will be back by the middle of next week, I believe.

- gri

On Fri, Aug 9, 2013 at 6:33 PM, <rocky.b...@gmail.com> wrote:

Yes, sure, the ssa interpreter doesn't use that information, but the
fork of it on github to support debugging does. And I've started
removing the lossy Pos information in that ssa interpreter by using
position information from the ast.

(Currently it is as a start and end position but eventually, I'll
probably add the single interval number/index I mentioned)

I think I recall you suggesting that one could use information from the
ast to get the more accurate range information rather than use the lossy
canonical form that is in the ssa interpreter. I had said okay, and then
you don't need that "canonical Pos" at all. But this assumes one has the
ast position information.

Later, Alan had said he thought he would eventually remove that
canonical Pos information, although that hasn't happened yet.

On 2013/08/10 00:57:49, gri wrote:

No changes are needed I think. ssa didn't use that information in the

first

place.
- gri

On Fri, Aug 9, 2013 at 5:53 PM, <mailto:rocky.bernstein@gmail.com>

[rocky.b...@gmail.com]

On 2013/08/10 04:18:02, gri wrote:
> It's trivial to add the information if you need it. The importer
allocates
> all maps in one place, and you just add a additional line for a Scopes
map
> and copy the pattern used for the other maps.

> The main difference is that now the information provided is from nodes
to
> scopes, while before the information was from scopes to nodes. But
it's
> trivially inverted if there is need for it.

> I'll leave it to Alan to make the respective changes in importer - my
> primary goal at the moment is to get go/types completed.

What is on the roadmap for getting go/types completed?

In the last month or so there have been a lot of changes such the
addition of scopes, which was much needed for things like writing a
debugger. When you had mentioned that this was going to change, I said
I'd wait for the changes before starting to fill out aspects around
handling scopes. When you said you thought everything was there
complete, although it was just a small matter of programming to add
whatever else was needed, I resumed.

In general understanding what's contemplated and what is likely to
change helps me or anyone else who is seriously trying to use this.

> Alan will be back
> by the middle of next week, I believe.

Ok. Thanks for the information. I won't try then to code around the
recent changes but instead will wait for importer to get revised.


> - gri




> On Fri, Aug 9, 2013 at 6:33 PM, <mailto:rocky.b...@gmail.com>

> <mailto:rocky.bernstein@gmail.**com<rocky.b...@gmail.com>

> >> >
> >>
> > wrote:
> >
> > > What changes (if any) need to be made in the ssa-interpreter need
to
> >> > allow it access to the ast as it was before this change?
> >> >
> >> > I see the Scopes field (map[ast.Node]*Scope) added now to
types.Info
> >>
> > and
> >
> >> > field "node" removed from the Scopes type and some sort of make()
> >>
> > needed
> >
> >> > after types.Info is created, but ssa uses

> >> > importer.****CreatePackageFromArgs.
> >> >
> >> >
> >>
> >
> > https://codereview.appspot.****com/12552047/%253Chttps://codere**
> > view.appspot.com/12552047/
<http://codereview.appspot.com/12552047/>>

[Robert Griesemer]

go/types is very close to functionally complete. There are known bugs (issue tracker, and TODOs in the code). But the code is now type-checking the entire standard-library in all os/arch configurations, and various other code.

What is still a bit in flux is the set of factory functions, exact naming, parameter lists, etc. - they have been added somewhat ad-hoc for clients (ssa) who needed to create their own types.

From an API perspective, I'd rather not have clients be able to mix their own things in because it's hard to enforce that they are properly set-up with all invariants preserved. For instance, at the moment its possible to muck with the Universe scope which is a no-no. I think this is one of the areas where we can still evolve the API and perhaps find better solutions. This is also an area where I don't want to tie things down too early. But in general, such changes should be not too hard on clients.

I might send out (or document in the code) the current status and what's missing, sometimes early next week. I will be offline for 4 weeks after that, but Alan will be able to chime in.

- gri

On Fri, Aug 9, 2013 at 6:33 PM, <mailto:rocky.bernstein@gmail.com>

<mailto:rocky.bernstein@gmail.**com<rocky.bernstein@gmail.com>

>> >
>>
> wrote:
>
>  > What changes (if any) need to be made in the ssa-interpreter need

[rocky.b...@gmail.com]

> On Fri, Aug 9, 2013 at 9:40 PM, <mailto:rocky.b...@gmail.com>

> <mailto:rocky.bernstein@gmail.**com<rocky.b...@gmail.com>

<mailto:rocky.bernstein@gmail.****com<rocky.bernstein@gmail.**com<rocky.b...@gmail.com>

> >> >
> >>
> >> >> >
> >> >>
> >> > wrote:
> >> >
> >> > > What changes (if any) need to be made in the ssa-interpreter
need
> >>
> > to
> >
> >> >> > allow it access to the ast as it was before this change?
> >> >> >
> >> >> > I see the Scopes field (map[ast.Node]*Scope) added now to
> >>
> > types.Info
> >
> >> >>
> >> > and
> >> >
> >> >> > field "node" removed from the Scopes type and some sort of
make()
> >> >>
> >> > needed
> >> >
> >> >> > after types.Info is created, but ssa uses

> >> >> > importer.******CreatePackageFromArgs.
> >> >> >
> >> >> >
> >> >>
> >> >
> >> >
https://codereview.appspot.******com/12552047/%25253Chttps://**codere**
> >> > view.appspot.com/12552047/
> >>
> >

<http://codereview.appspot.**com/12552047/%3Chttp://codereview.appspot.com/12552047/>

> > >>
> >
> > >
> >> >> >
> >> >>
> >> >
> >> >
> >> >
> >> >
> >>
> >
> > https://codereview.appspot.****com/12552047/%253Chttps://codere**
> > view.appspot.com/12552047/
<http://codereview.appspot.com/12552047/>>
> >
> >> >
> >>
> >
> >
> >
> >

https://codereview.appspot.**com/12552047/%3Chttps://codereview.appspot.com/12552047/>
> >

Thanks! This helps a lot. I' looking forward to a synopsis where things
stand next week.

https://codereview.appspot.com/12552047/

[Rocky Bernstein]

I've been looking again to look at the bugs and TODO's as you mentioned previously. As it is right now, it's not all that useful in a debugger or a go shell (short of abusing the Universal scope which we all agree is undesirable), because access to the checker is at a very coarse level -- the level of an entire program. Also, the type and value information inside the type checker don't seem to be accessible from the outside. Am I missing something? 

There is types.Check() which works with an entire program. Underneath that calls  checkExprOrType but that's not exposed from the outside. Nor is the checker object where type and value information about the ast object is saved. 

Inside a debugger stopped inside a go program, one has a current scope (say a type.Scope object). The programmer enters an expression and that's parsed and evaluated using current values and the scope. Similarly, in an interactive shell one also has a scope. Some interactive shells also have "workspaces" which allow one to switch scopes. 

Does the use cases of go/types encompass these scenarios? Also, if it is the case that the type information is not accessible after a check is done, I would imagine there some duplication inside the ssa-interpreter to handle the same sorts of issues. So again, I must be missing something. 

On Fri, Aug 9, 2013 at 9:40 PM, <mailto:rocky.bernstein@gmail.com>

<mailto:rocky.bernstein@gmail.**com<rocky.bernstein@gmail.com>

<mailto:rocky.bernstein@gmail.****com<rocky.bernstein@gmail.**com<rocky.bernstein@gmail.com>

[Robert Griesemer]

The Info struct can be populated with maps that provide you access to the type (and if constant, value) of every expression in the program. There are maps that permit mapping of all identifiers to their objects, and thus types, and corresponding scopes. I have pointed you at this structure before when explaining how to hook up the Scopes map.

So you're certainly not correct: There is very fine-grained information available about the entire program. Together with the AST it is possible to get all the type and value information that is needed to implement a back-end of a compiler. It was certainly possible for Alan to implement the ssa interpreter...

The type-checker's primary goal is to provide whole-program type information.

There's a whole set of problems that come with implementing a debugger or an interactive shell that has very little to do with type-checking, and it's not the goal of the type-checker to be a kitchen sink for all possible applications.

- gri

[Rocky Bernstein]

On Sun, Aug 11, 2013 at 12:34 AM, Robert Griesemer <g...@golang.org> wrote:

The Info struct can be populated with maps that provide you access to the type (and if constant, value) of every expression in the program. There are maps that permit mapping of all identifiers to their objects, and thus types, and corresponding scopes. I have pointed you at this structure before when explaining how to hook up the Scopes map.

So you're certainly not correct: There is very fine-grained information available about the entire program.

I think you misunderstood what I wrote. I didn't write there wasn't fine-grained information about the entire program from the checker.

I wrote that access to the checker was at the granularity of an entire program. Inside, the types checker uses an ast node and a scope. ast/parser is also able to take an expression string and parse that. But from outside go.tools/types, you can't pass in an ast expression and a scope hand have the checker work on that. 

Addressing this is looks like largely (if not entirely) a matter of allowing some of the internal routines be called from the outside, and allowing the checker data structure be accessible. 

Together with the AST it is possible to get all the type and value information that is needed to implement a back-end of a compiler. It was certainly possible for Alan to implement the ssa interpreter...

The type-checker's primary goal is to provide whole-program type information.

There's a whole set of problems that come with implementing a debugger or an interactive shell that has very little to do with type-checking, and it's not the goal of the type-checker to be a kitchen sink for all possible applications.

I think you are expanding this way outside of the scope of what I was suggesting: again, allow checking to work on expressions in addition to whole programs just as ast/parser currently allows.  

One can define away the problem by saying that is outside of the purview of this package. However look at it from the standpoint of an evaluator application that needs use that information. I can only think of 3 options:

1. Use the existing package in a Rube Goldberg way (and this invites messing with the Universal scope), 
2. Fork the code so that those routines are exposed
3. Abandon working on the problem altogether 

[Robert Griesemer]

go.types.Eval does exactly what you are asking for and has been there for a while now.

- gri

[Rocky Bernstein]

I had previously tried go.types.Eval, but it has a number of problems. 

The most serious one is how it gets the values for identifiers. Currently those values have to be recorded off of its kind of scope object. To populate or update that that every time a program stops is a bit prohibitive.  Recall that the ssa.interp doesn't need or use this kind of scope object in its normal operations. To be fair that;s because this kind of scope was fairly recently created. Instead, it has its own notion, or current environment of values. In fact, the ssa interpreter's notion of a "value" I think is is slightly different, although it might be fairly easy to convert it from interp.Value to exact.Value and and back.

A more friendlier design would allow one to give a call back to use to get the value of an identifier inside the appropriate routine under types.Eval -  check.ident() ? 

A second problem with type with types.Eval is how it handles errors. The object of type Config, set in types.EvalNode(), isn't exposed to the outside, so I don't see how to control configuration things which includes how to handle errors.  

The last problem I have had is having the checker evaluate 

testTypes[0].num given a "scope" created that contains this: 

type testEntry struct {

src string

   num int

}

var testTypes = []testEntry{ {"a", 1}, {"b", 2}}

But here, I'm using the version of types before the change to move around scope. I haven't been able to test this on the current tip, for reasons I don't understand. 

Leaving aside the above which might or might not be a simple bug, if the other main issues around types.Eval() were addressed, absolutely types.Eval() would be great to use. 

[Robert Griesemer]

Let me say it one more time:

The issues you have with a debugger or interpreter are overlapping with go/types but it's not the purpose of go/types to solve these problems. go/types is about statically type-checking programs. The fact that it can evaluate expressions is incidental: The Go type system requires that the values of constant expressions (as defined by the spec) be known at compile time since they impact the typing of a program. Therefore go/types evaluates constant expressions of basic types only. There is no internal representation of non-basic values and no plan to add that.

Therefore, providing a mechanism for types.Eval to get dynamic values for identifiers doesn't solve the issue you are facing, for exactly the above stated reasons: In general such values are not of basic types. Implementing such an interpreter is beyond go/types and exactly the kind of work you will have to put in in a debugger. What go/types will do for you is that it will tell you if such an expression is legal (from a type-point of view).

ssa/interp works exactly because it does this extra work. For a debugger, a simpler expression evaluator will be possible that mirrors some of the go/types internal structure, but that is simply because that structure is given by the structure of the AST.

Regarding the 2nd issue: You can change the configuration (e.g. the Error handler) at runtime if you wanted to change it midstream.

Finally, your last problem again is related to your first issue: It's not in the scope (pardon my pun) of go/types to evaluate arbitrary non-constant expressions. And what you have is not a constant expression.

Going forward, please refrain from replying to this thread or any mailing lists reserved for code review feedback. This is not a forum for design discussions. Use golang-nuts instead.

Thanks.

- gri

PS: For pending issues with go/types see https://code.google.com/p/go/issues/detail?id=6141 . I don't think any of these should block the implementation of a debugger.

[adon...@google.com]

LGTM


https://codereview.appspot.com/12552047/diff/2/go/types/api_test.go
File go/types/api_test.go (right):

https://codereview.appspot.com/12552047/diff/2/go/types/api_test.go#newcode89
go/types/api_test.go:89: func TestScopesInfo(t *testing.T) {
Nice test.

https://codereview.appspot.com/12552047/diff/2/go/types/api_test.go#newcode198
go/types/api_test.go:198: // look for matching scope description
Would it also be useful to test the scope tree topology, i.e. Parent()
links?

https://codereview.appspot.com/12552047/

[g...@golang.org]

https://codereview.appspot.com/12552047/diff/2/go/types/api_test.go
File go/types/api_test.go (right):

https://codereview.appspot.com/12552047/diff/2/go/types/api_test.go#newcode198
go/types/api_test.go:198: // look for matching scope description

On 2013/08/14 17:05:12, adonovan wrote:
> Would it also be useful to test the scope tree topology, i.e. Parent()
links?

Yes, but I left it out because I think it might be done elsewhere - in a
sanity-checking phase that runs through the data structures generated
after a type check.

https://codereview.appspot.com/12552047/