[go] go/types, types2: check for direct cycles as a separate phase
Mark Freeman (Gerrit)
Mark Freeman voted Commit-Queue+1![]( "Open in Gerrit")
| Commit-Queue | +1 |
Related details
- Robert Griesemer
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mark Freeman (Gerrit)
Mark Freeman uploaded new patchset![]( "Open in Gerrit")
- TryBots-Pass: LUCI-TryBot-Result+1 by Go LUCI
Related details
- Robert Griesemer
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mark Freeman (Gerrit)
Mark Freeman uploaded new patchset![]( "Open in Gerrit")
Related details
- Robert Griesemer
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mark Freeman (Gerrit)
Mark Freeman uploaded new patchset![]( "Open in Gerrit")
Related details
- Robert Griesemer
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Robert Griesemer (Gerrit)
Robert Griesemer added 3 comments![]( "Open in Gerrit")
c.objSeen = make(map[Object]int)Rather than storing objSeen - which appears to be used in this code only - in Checker, in this case I would pass it to directCycle explicitly.
Then it will also automatically disappear from the root set when you return from this function (no need to nil out the field).
// any order is fineFor reproduceability we probably need to go in a deterministic order.
We may have test cases that produce different results depending on order.
Or we may beed it for debuggability (in that case, we could enable the deterministic order when debug is enabled).
Related details
- Mark Freeman
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mark Freeman (Gerrit)
Mark Freeman added 2 comments![]( "Open in Gerrit")
c.objSeen = make(map[Object]int)Rather than storing objSeen - which appears to be used in this code only - in Checker, in this case I would pass it to directCycle explicitly.
Then it will also automatically disappear from the root set when you return from this function (no need to nil out the field).
Fair — I had meant for this to be an alternative to the `grey` color used in the main type checking pass. Recall that the value of the grey color is the index in the object path, which might be a bit clever.
Do you think it's worth replacing that?
Alternatively, we could also do grey color encoding here, but then most objects will go from grey back to white which seems odd.
// any order is fineFor reproduceability we probably need to go in a deterministic order.
We may have test cases that produce different results depending on order.
Or we may beed it for debuggability (in that case, we could enable the deterministic order when debug is enabled).
Agree, it seems a bit less subtle if we go in deterministic order. Although we do end up doing this sort in a few places, which might not be the best performance wise.
Related details
- Robert Griesemer
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Robert Griesemer (Gerrit)
Robert Griesemer added 2 comments![]( "Open in Gerrit")
c.objSeen = make(map[Object]int)Mark FreemanRather than storing objSeen - which appears to be used in this code only - in Checker, in this case I would pass it to directCycle explicitly.
Then it will also automatically disappear from the root set when you return from this function (no need to nil out the field).
Fair — I had meant for this to be an alternative to the `grey` color used in the main type checking pass. Recall that the value of the grey color is the index in the object path, which might be a bit clever.
Do you think it's worth replacing that?
Alternatively, we could also do grey color encoding here, but then most objects will go from grey back to white which seems odd.
I agree that the grey color scheme is subtle and the machinery spread. Would be nice to replace that. But is this code sufficient? Don't we need to run through all kinds of RHS expressions etc.? I am probably missing something (haven't had time to look it through in detail yet).
// any order is fineMark FreemanFor reproduceability we probably need to go in a deterministic order.
We may have test cases that produce different results depending on order.
Or we may beed it for debuggability (in that case, we could enable the deterministic order when debug is enabled).
Agree, it seems a bit less subtle if we go in deterministic order. Although we do end up doing this sort in a few places, which might not be the best performance wise.
Understood, but in the past we used map random iteration orders and we endep up fixing all of those for reproducability.
Related details
- Mark Freeman
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mark Freeman (Gerrit)
Mark Freeman uploaded new patchset![]( "Open in Gerrit")
Related details
- Mark Freeman
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mark Freeman (Gerrit)
Mark Freeman added 2 comments![]( "Open in Gerrit")
c.objSeen = make(map[Object]int)Mark FreemanRather than storing objSeen - which appears to be used in this code only - in Checker, in this case I would pass it to directCycle explicitly.
Then it will also automatically disappear from the root set when you return from this function (no need to nil out the field).
Robert GriesemerFair — I had meant for this to be an alternative to the `grey` color used in the main type checking pass. Recall that the value of the grey color is the index in the object path, which might be a bit clever.
Do you think it's worth replacing that?
Alternatively, we could also do grey color encoding here, but then most objects will go from grey back to white which seems odd.
I agree that the grey color scheme is subtle and the machinery spread. Would be nice to replace that. But is this code sufficient? Don't we need to run through all kinds of RHS expressions etc.? I am probably missing something (haven't had time to look it through in detail yet).
I believe the mechanism (a map) is sufficient to replicate the grey color encoding, but the code here does not eliminate use of grey color encoding. We would need to go through `decl.go` in a separate CL.
I'm just pointing out that by adding `Checker.objSeen` in this CL, it makes follow-up work (marginally) easier.
// any order is fineMark FreemanFor reproduceability we probably need to go in a deterministic order.
We may have test cases that produce different results depending on order.
Or we may beed it for debuggability (in that case, we could enable the deterministic order when debug is enabled).
Robert GriesemerAgree, it seems a bit less subtle if we go in deterministic order. Although we do end up doing this sort in a few places, which might not be the best performance wise.
Understood, but in the past we used map random iteration orders and we endep up fixing all of those for reproducability.
I'm in agreement, it seems like the right thing to do. I've extracted the relevant logic in CL 715480 so we don't have to redo it here.
Related details
- Robert Griesemer
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Robert Griesemer (Gerrit)
Robert Griesemer added 12 comments![]( "Open in Gerrit")
// While seemingly trivial, freedom from direct cycles guarantees that the typeJust say: Freedom from direct cycles guarantees that ...
c.objSeen = make(map[Object]int)Mark FreemanRather than storing objSeen - which appears to be used in this code only - in Checker, in this case I would pass it to directCycle explicitly.
Then it will also automatically disappear from the root set when you return from this function (no need to nil out the field).
Robert GriesemerFair — I had meant for this to be an alternative to the `grey` color used in the main type checking pass. Recall that the value of the grey color is the index in the object path, which might be a bit clever.
Do you think it's worth replacing that?
Alternatively, we could also do grey color encoding here, but then most objects will go from grey back to white which seems odd.
Mark FreemanI agree that the grey color scheme is subtle and the machinery spread. Would be nice to replace that. But is this code sufficient? Don't we need to run through all kinds of RHS expressions etc.? I am probably missing something (haven't had time to look it through in detail yet).
I believe the mechanism (a map) is sufficient to replicate the grey color encoding, but the code here does not eliminate use of grey color encoding. We would need to go through `decl.go` in a separate CL.
I'm just pointing out that by adding `Checker.objSeen` in this CL, it makes follow-up work (marginally) easier.
Acknowledged
defer (func() { c.objSeen = nil })()again: pass objSeen down to directCyle instead of storing in Checker?
// any order is fineMark FreemanFor reproduceability we probably need to go in a deterministic order.
We may have test cases that produce different results depending on order.
Or we may beed it for debuggability (in that case, we could enable the deterministic order when debug is enabled).
Robert GriesemerAgree, it seems a bit less subtle if we go in deterministic order. Although we do end up doing this sort in a few places, which might not be the best performance wise.
Mark FreemanUnderstood, but in the past we used map random iteration orders and we endep up fixing all of those for reproducability.
I'm in agreement, it seems like the right thing to do. I've extracted the relevant logic in CL 715480 so we don't have to redo it here.
Acknowledged
if t, ok := obj.(*TypeName); ok {the convention in the type checker (when we don't _need_ and ok) is to avoid it:
```
if tname, _ := obj.(*TypeName); tname != nil {
```
func (c *Checker) directCycle(t *TypeName) (err bool) {s/err/ok/ and swap the default: this way the default is "not ok", and we are also not using the name "err" typically used for a variable of error type in an unusual way.
return falseif you change the result to (ok bool), the error case can just be "return"
defer (func() { delete(c.objSeen, c.pop()) })()no need for ()'s around the func literal
if n, ok := c.objMap[t].tdecl.Type.(*syntax.Name); ok {s/ok/n != nil/
// direct cycles can only exist through package-level type namesthis comment seems a bit out of place
var ts []*Nameds/ts/path/
ts leaves one guessing. Path seems clearer.
Related details
- Mark Freeman
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mark Freeman (Gerrit)
Mark Freeman added 3 comments![]( "Open in Gerrit")
defer (func() { c.objSeen = nil })()again: pass objSeen down to directCyle instead of storing in Checker?
I'm planning to follow this with replacement of the `grey` color encoding with `objSeen`, in which case I think I need it at the `Checker` level, no?
Though I don't explicitly need it in this CL if we don't want it at the Checker level until then.
if t, ok := obj.(*TypeName); ok {the convention in the type checker (when we don't _need_ and ok) is to avoid it:
```
if tname, _ := obj.(*TypeName); tname != nil {
```
I'm not opposed to following the convention, but I am curious why this is the convention.
IMO, I just need whether the assertion succeeded (without a panic) and don't want to know the appropriate default value to compare with `tname`.
It also seemingly invites a shortening to `if tname :=` which panics.
// direct cycles can only exist through package-level type namesthis comment seems a bit out of place
It's meant to suggest "we don't need to check anything else" — otherwise it's easy to wonder whether we missed consideration of imports, types in the universe scope, etc.
Perhaps a more direct wording of that?
Related details
- Robert Griesemer
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Robert Griesemer (Gerrit)
Robert Griesemer added 2 comments![]( "Open in Gerrit")
defer (func() { c.objSeen = nil })()Mark Freemanagain: pass objSeen down to directCyle instead of storing in Checker?
I'm planning to follow this with replacement of the `grey` color encoding with `objSeen`, in which case I think I need it at the `Checker` level, no?
Though I don't explicitly need it in this CL if we don't want it at the Checker level until then.
Acknowledged
if t, ok := obj.(*TypeName); ok {Mark Freemanthe convention in the type checker (when we don't _need_ and ok) is to avoid it:
```
if tname, _ := obj.(*TypeName); tname != nil {
```
I'm not opposed to following the convention, but I am curious why this is the convention.
IMO, I just need whether the assertion succeeded (without a panic) and don't want to know the appropriate default value to compare with `tname`.
It also seemingly invites a shortening to `if tname :=` which panics.
With t, ok, you can have ok == true but t == nil, leading to a panic. With tname != nil we check both ok and tname != nil at the same time. Also, it removes a name (ok) from the scope.
Admittedly, tname != nil may hide an error elsewhere, when tname shouldn't be nil in the first place. But it seemed that not panicking was more important at some point.
Related details
- Mark Freeman
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mark Freeman (Gerrit)
Mark Freeman added 1 comment![]( "Open in Gerrit")
if t, ok := obj.(*TypeName); ok {Mark Freemanthe convention in the type checker (when we don't _need_ and ok) is to avoid it:
```
if tname, _ := obj.(*TypeName); tname != nil {
```
Robert GriesemerI'm not opposed to following the convention, but I am curious why this is the convention.
IMO, I just need whether the assertion succeeded (without a panic) and don't want to know the appropriate default value to compare with `tname`.
It also seemingly invites a shortening to `if tname :=` which panics.
With t, ok, you can have ok == true but t == nil, leading to a panic. With tname != nil we check both ok and tname != nil at the same time. Also, it removes a name (ok) from the scope.
Admittedly, tname != nil may hide an error elsewhere, when tname shouldn't be nil in the first place. But it seemed that not panicking was more important at some point.
Got it — I figured we didn't want to pollute the scope, but didn't know we were taking a cautious approach to nilness.
In this case, I don't expect `objLst` to hold `nil` and would like to panic if that invariant is violated (even if only in debug mode). IMO, making assumptions about those invariants clearer seems quite useful.
Related details
- Robert Griesemer
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mark Freeman (Gerrit)
Mark Freeman uploaded new patchset![]( "Open in Gerrit")
Related details
- Robert Griesemer
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mark Freeman (Gerrit)
Mark Freeman added 4 comments![]( "Open in Gerrit")
// While seemingly trivial, freedom from direct cycles guarantees that the typeJust say: Freedom from direct cycles guarantees that ...
Done
func (c *Checker) directCycle(t *TypeName) (err bool) {s/err/ok/ and swap the default: this way the default is "not ok", and we are also not using the name "err" typically used for a variable of error type in an unusual way.
Done
if you change the result to (ok bool), the error case can just be "return"
Let's avoid the naked return there, it's a bit tricky that the `ok` (whether the assertion succeeded) is being returned.
defer (func() { delete(c.objSeen, c.pop()) })()Mark Freemanno need for ()'s around the func literal
Done
Related details
- Robert Griesemer
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mark Freeman (Gerrit)
Mark Freeman uploaded new patchset![]( "Open in Gerrit")
Related details
- Robert Griesemer
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mark Freeman (Gerrit)
Mark Freeman added 1 comment![]( "Open in Gerrit")
s/ts/path/
ts leaves one guessing. Path seems clearer.
Done
Related details
- Robert Griesemer
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Robert Griesemer (Gerrit)
Robert Griesemer added 4 comments![]( "Open in Gerrit")
if t, ok := obj.(*TypeName); ok {Mark Freemanthe convention in the type checker (when we don't _need_ and ok) is to avoid it:
```
if tname, _ := obj.(*TypeName); tname != nil {
```
Robert GriesemerI'm not opposed to following the convention, but I am curious why this is the convention.
IMO, I just need whether the assertion succeeded (without a panic) and don't want to know the appropriate default value to compare with `tname`.
It also seemingly invites a shortening to `if tname :=` which panics.
Mark FreemanWith t, ok, you can have ok == true but t == nil, leading to a panic. With tname != nil we check both ok and tname != nil at the same time. Also, it removes a name (ok) from the scope.
Admittedly, tname != nil may hide an error elsewhere, when tname shouldn't be nil in the first place. But it seemed that not panicking was more important at some point.
Got it — I figured we didn't want to pollute the scope, but didn't know we were taking a cautious approach to nilness.
In this case, I don't expect `objLst` to hold `nil` and would like to panic if that invariant is violated (even if only in debug mode). IMO, making assumptions about those invariants clearer seems quite useful.
Acknowledged
if n, ok := c.objMap[t].tdecl.Type.(*syntax.Name); ok {Robert Griesemers/ok/n != nil/
Acknowledged
// direct cycles can only exist through package-level type namesMark Freemanthis comment seems a bit out of place
It's meant to suggest "we don't need to check anything else" — otherwise it's easy to wonder whether we missed consideration of imports, types in the universe scope, etc.
Perhaps a more direct wording of that?
Acknowledged
if i, ok := seen[t]; ok {I wonder if it would make sense to leave (some of) this in debug mode: we panic if there's a cycle. That might be useful in case we run into unexpected cycles (not that I can think of one at the moment).
I'd declare the seen variable, and in debug mode, allocate it eagerly (so you don't need lines 652-654), and then have a simple check:
```
if debug {
assert(!seen[t])
seen[t] = true
}
```
Related details
- Mark Freeman
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mark Freeman (Gerrit)
Mark Freeman uploaded new patchset![]( "Open in Gerrit")
Related details
- Mark Freeman
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mark Freeman (Gerrit)
Mark Freeman uploaded new patchset![]( "Open in Gerrit")
Related details
- Mark Freeman
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mark Freeman (Gerrit)
Mark Freeman uploaded new patchset![]( "Open in Gerrit")
Related details
- Mark Freeman
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Robert Griesemer (Gerrit)
Robert Griesemer added 8 comments![]( "Open in Gerrit")
Now that I spent some more time on this, I think this code needs more work.
Apologies for not noticing sooner.
objPath []Object // path of object dependencies during type-checking (for cycle reporting)not sure what changed on this line
check.directCycles(make(map[Object]int))I don't see a reason for passing this map in as an argument.
Why not allocate it locally, in directCycles?
func (c *Checker) directCycles(seen map[Object]int) {s/c/check/ for consistency with the rest of the code.
I don't object to renaming, but let's do it consistently across all files.
The consistency simply makes it easier to read the code.
// directCycle drives [Checker.directCycles] for a given type.This doc string is not super helpful, also, the name is not quite right.
Better to explain the result.
But see below.
// if we reach an already-reported type, don't report it again// If we reach a previously reported type, don't report it again.
(Note that we may not have reported anything before. Also, for comments that are proper sentences, please use capitalization and periods. For others its ok to keep it all lowercase without punctuation.)
return c.directCycle(t, seen)I think we should avoid the recursion here. There is really no need, it's basically a tail recursion. The primary benefit is that tracing would show the entire path, but it's nested, which is not great either.
Just have a loop. Then you also don't need to return a result, actually.
And the seen map is always empty at the end, so I wonder if we can be smarter about this whole thing.
Let's say we represent `type A B` as A -> B, and use . to mark a literal (end of path). We may have a situation like this:
A -> B -> C -> D -> E -> .
F -> C -> D -> E -> .
G -> H -> D -> E -> .
Even though we know that after starting with A there is no cycle, we iterate (recurse!) through much of the path again and again for B, C, etc. That's potentially quadratic. We only stop early if we find a black object, and we only find one if we have a cycle.
We should absolutely avoid repeated traversals. In normal programs it won't be an issue, but it would be easy to generate a bad program that would consume a lot of time to check.
This needs some more work.
// direct cycles can only exist through package-level type names,make a proper sentence, please
Related details
- Mark Freeman
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mark Freeman (Gerrit)
Mark Freeman uploaded new patchset![]( "Open in Gerrit")
Related details
- Mark Freeman
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mark Freeman (Gerrit)
Mark Freeman added 5 comments![]( "Open in Gerrit")
objPath []Object // path of object dependencies during type-checking (for cycle reporting)not sure what changed on this line
s/type inference/type-checking
I believe inference refers to something else
I don't see a reason for passing this map in as an argument.
Why not allocate it locally, in directCycles?
My mistake — I misread your comment on "passing it in to directCycle" as passing it to "directCycles" (note the "s"); have put that back.
func (c *Checker) directCycles(seen map[Object]int) {s/c/check/ for consistency with the rest of the code.
I don't object to renaming, but let's do it consistently across all files.
The consistency simply makes it easier to read the code.
Done
// if we reach an already-reported type, don't report it again// If we reach a previously reported type, don't report it again.
(Note that we may not have reported anything before. Also, for comments that are proper sentences, please use capitalization and periods. For others its ok to keep it all lowercase without punctuation.)
Done
// direct cycles can only exist through package-level type names,make a proper sentence, please
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mark Freeman (Gerrit)
Mark Freeman uploaded new patchset![]( "Open in Gerrit")
Related details
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mark Freeman (Gerrit)
Mark Freeman uploaded new patchset![]( "Open in Gerrit")
Related details
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mark Freeman (Gerrit)
Mark Freeman voted Commit-Queue+1![]( "Open in Gerrit")
| Commit-Queue | +1 |
Related details
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mark Freeman (Gerrit)
Mark Freeman uploaded new patchset![]( "Open in Gerrit")
- TryBots-Pass: LUCI-TryBot-Result+1 by Go LUCI
Related details
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mark Freeman (Gerrit)
Mark Freeman voted Commit-Queue+1![]( "Open in Gerrit")
| Commit-Queue | +1 |
Related details
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mark Freeman (Gerrit)
Mark Freeman added 1 comment![]( "Open in Gerrit")
return c.directCycle(t, seen)I think we should avoid the recursion here. There is really no need, it's basically a tail recursion. The primary benefit is that tracing would show the entire path, but it's nested, which is not great either.
Just have a loop. Then you also don't need to return a result, actually.
And the seen map is always empty at the end, so I wonder if we can be smarter about this whole thing.Let's say we represent `type A B` as A -> B, and use . to mark a literal (end of path). We may have a situation like this:
A -> B -> C -> D -> E -> .
F -> C -> D -> E -> .
G -> H -> D -> E -> .Even though we know that after starting with A there is no cycle, we iterate (recurse!) through much of the path again and again for B, C, etc. That's potentially quadratic. We only stop early if we find a black object, and we only find one if we have a cycle.
We should absolutely avoid repeated traversals. In normal programs it won't be an issue, but it would be easy to generate a bad program that would consume a lot of time to check.
This needs some more work.
Overall agree — I've changed this to an iterative approach that marks visited types using a `done` map. This should guard against the quadratic case. Unfortunately, tracing becomes a bit less obvious, but I don't think its critical to have.
Related details
- Robert Griesemer
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mark Freeman (Gerrit)
Mark Freeman voted Commit-Queue+1![]( "Open in Gerrit")
| Commit-Queue | +1 |
Related details
- Robert Griesemer
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Robert Griesemer (Gerrit)
Robert Griesemer added 4 comments![]( "Open in Gerrit")
Apologies for the delay. Some more feedback.
It seems ok, but there ought to be a simpler, easier to understand way to do this.
I haven't completely convinced myself that this is correct.
func (check *Checker) directCycle(t0 *TypeName, seen map[Object]int, done map[Object]bool) {s/t0/t/
You need a t1 below, but only briefly. Ok to use t, t1 (similar to say t, and t' as one might us in math); this keeps the primary identifier short.
// If no cycle has been found, keep walking.This comment is confusing in front of the next two lines. I'd put it on line 44 and then have an empty line.
And then, here, I'd explain what happens. It is super subtle because push/pop affects the objPath. And the defer clears from the seen map and object path if there's no cycle, but _after_ we mark the path as done.
if t1, ok := check.pkg.scope.Lookup(n.Value).(*TypeName); ok {This could use a comment explaining that we follow the RHS type whether it's an alias or not.
Also, I think if t0 is not a type, that tdecl.Type might be nil. I think you can probably have a test case for that.
Related details
- Mark Freeman
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mark Freeman (Gerrit)
Mark Freeman added 5 comments![]( "Open in Gerrit")
// directCycle drives [Checker.directCycles] for a given type.This doc string is not super helpful, also, the name is not quite right.
Better to explain the result.
But see below.
I don't think we can explain much without restating what's in `Checker.directCycles`. It might be best to leave this a bit terse and simply link to the other method with more exposition.
func (check *Checker) directCycle(t0 *TypeName, seen map[Object]int, done map[Object]bool) {s/t0/t/
You need a t1 below, but only briefly. Ok to use t, t1 (similar to say t, and t' as one might us in math); this keeps the primary identifier short.
Makes sense, done
// If no cycle has been found, keep walking.This comment is confusing in front of the next two lines. I'd put it on line 44 and then have an empty line.
And then, here, I'd explain what happens. It is super subtle because push/pop affects the objPath. And the defer clears from the seen map and object path if there's no cycle, but _after_ we mark the path as done.
Agree — `check.pop()` being deferred is crucial because we still need the object path when we go to mark the path as done. I've added a comment explaining this.
if t1, ok := check.pkg.scope.Lookup(n.Value).(*TypeName); ok {This could use a comment explaining that we follow the RHS type whether it's an alias or not.
Also, I think if t0 is not a type, that tdecl.Type might be nil. I think you can probably have a test case for that.
Added the comment.
By traversal, `t0` is a package-level type declared in the current package. I think it's an invariant that `tdecl.Type` is populated for type declarations, which `Checker.resolveBaseTypeName` also relies on.
If we want to explicitly enforce that invariant, maybe we check it upstream in debug mode. Here, it seems simplest to use the invariant.
if i, ok := seen[t]; ok {I wonder if it would make sense to leave (some of) this in debug mode: we panic if there's a cycle. That might be useful in case we run into unexpected cycles (not that I can think of one at the moment).
I'd declare the seen variable, and in debug mode, allocate it eagerly (so you don't need lines 652-654), and then have a simple check:
```
if debug {
assert(!seen[t])
seen[t] = true
}
```
Pardon my delay, I had to think about this one a bit. While it seems fine here, it could be tricky for more advanced cycles and defeat some of the complexity savings.
In any case, we would hang if such unexpected cycles slipped by and could rely on traces to observe where it's hanging.
Related details
- Robert Griesemer
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Robert Griesemer (Gerrit)
Robert Griesemer has uploaded the change for review![]( "Open in Gerrit")
Commit message
go/types, types2: check for direct cycles as a separate phase
Alternative to CL 714760. To be discussed.
Change diff
diff --git a/src/cmd/compile/internal/types2/check.go b/src/cmd/compile/internal/types2/check.go
index 8b27d9d..0716ee8 100644
--- a/src/cmd/compile/internal/types2/check.go
+++ b/src/cmd/compile/internal/types2/check.go
@@ -497,6 +497,9 @@
print("== sortObjects ==")
check.sortObjects()
+ print("== directCycles ==")
+ check.directCycles()
+
print("== packageObjects ==")
check.packageObjects()
diff --git a/src/cmd/compile/internal/types2/cycles.go b/src/cmd/compile/internal/types2/cycles.go
new file mode 100644
index 0000000..b76dcf3
--- /dev/null
+++ b/src/cmd/compile/internal/types2/cycles.go
@@ -0,0 +1,122 @@
+// Copyright 2025 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package types2
+
+import "cmd/compile/internal/syntax"
+
+// directCycles searches for direct cycles among package level type declarations.
+// See directCycle for details.
+func (check *Checker) directCycles() {
+ seen := make(map[*TypeName]bool)
+ for _, obj := range check.objList {
+ if tname, _ := obj.(*TypeName); tname != nil {
+ check.directCycle(tname, seen)
+ }
+ }
+}
+
+// directCycle checks if the declaration of the type given by tname is free of direct cycles.
+// A direct cycle exists if the path from tname's declaration's RHS leads from type name to
+// type name and eventually ends up on the path again, via regular or alias declarations; in
+// other words if there are no type literals (or basic types) on the path.
+// If a cycle is detected, a cycle error is reported and all types on the path are marked
+// as invalid.
+//
+// The seen map tracks which type names have been processed already. An entry can be in one
+// one of 3 states to represent a typical 3-state (white-grey-black) graph marking algorithm
+// for cycle detection:
+//
+// - entry doesn't exist: tname has not been seen before ("white")
+// - value is false : tname has been seen but is not done ("grey")
+// - value is true : tname has been seen and is done ("black")
+//
+// When directCycle returns, the seen entries for all type names on the path that starts
+// at tname are true ("black"), irrespective of whether there was a cycle or not.
+// This ensures that a type name is never iterated over multiple times during the search.
+func (check *Checker) directCycle(tname *TypeName, seen map[*TypeName]bool) {
+ if debug && check.conf.Trace {
+ check.trace(tname.Pos(), "-- path for %s", tname)
+ }
+
+ var path []*TypeName
+ for {
+ done, found := seen[tname]
+ if done {
+ // We have seen tname and it was done before ("black" type name).
+ break
+ }
+
+ if found {
+ // We have seen tname before but it is not done yet, so we must
+ // have a cycle ("grey" type name).
+ // TODO(gri) consider marking all types on the path as invalid
+ tname.setType(Typ[Invalid])
+ tname.setColor(black)
+
+ // Determine the start of the cycle on the path.
+ // This is the error case, so we don't care about the extra
+ // path traversal.
+ start := -1 // start of cycle
+ for i, tn := range path {
+ // Because the seen map contained no "grey" entries upon call of
+ // this function, the only grey entries that are in seen now are
+ // entries that were added during this iteration. This ensures
+ // that we're going to fine tname in the path somewhere.
+ if tname == tn {
+ start = i
+ break
+ }
+ }
+ assert(start >= 0)
+
+ // Convert cycle path into an object path.
+ var cycle []Object
+ for _, tname := range path[start:] {
+ cycle = append(cycle, tname)
+ }
+
+ check.cycleError(cycle, firstInSrc(cycle))
+ break
+ }
+
+ // The type name was never seen before ("white" type name).
+ // Mark it accordingly ("grey") and add it to the path.
+ seen[tname] = false
+ path = append(path, tname)
+
+ // tname is a type name, so it must have a corresponding type declaration and
+ // associated RHS type of that declaration.
+ // For direct cycle detection, we don't care about whether we have an alias or not.
+ // If the associated type is not a name, we're at the end of the path and we're done.
+ rhs, _ := check.objMap[tname].tdecl.Type.(*syntax.Name)
+ if rhs == nil {
+ break
+ }
+
+ // Determine the RHS type. If it's not found, we have an error but it will
+ // be reported later, and we can stop. If it's not a type name, we also
+ // cannot have a direct cycle and thus can stop.
+ tn, _ := check.pkg.scope.Lookup(rhs.Value).(*TypeName)
+ if tn == nil {
+ break
+ }
+
+ // Otherwise, continue with RHS.
+ tname = tn
+ }
+
+ // Mark all type names as done.
+ // This ensures that seen doesn't contain any seen but not done entries
+ // upon return from this function.
+ for _, tname := range path {
+ seen[tname] = true
+ }
+
+ if debug {
+ for _, done := range seen {
+ assert(done)
+ }
+ }
+}
diff --git a/src/cmd/compile/internal/types2/named.go b/src/cmd/compile/internal/types2/named.go
index cece304..b5c8ed1 100644
--- a/src/cmd/compile/internal/types2/named.go
+++ b/src/cmd/compile/internal/types2/named.go
@@ -613,13 +613,18 @@
// type set to T. Aliases are skipped because their underlying type is
// not memoized.
//
-// This method also checks for cycles among alias and named types, which will
-// yield no underlying type. If such a cycle is found, the underlying type is
-// set to Typ[Invalid] and a cycle is reported.
+// resolveUnderlying assumes that there are no direct cycles; if there were
+// any, they were broken (by setting the respective types to invalid) during
+// the directCycles check phase.
func (n *Named) resolveUnderlying() {
assert(n.stateHas(unpacked))
- var seen map[*Named]int // allocated lazily
+ var seen map[*Named]bool // for debugging only
+ if debug {
+ seen = make(map[*Named]bool)
+ }
+
+ var path []*Named
var u Type
for rhs := Type(n); u == nil; {
switch t := rhs.(type) {
@@ -630,17 +635,9 @@
rhs = unalias(t)
case *Named:
- if i, ok := seen[t]; ok {
- // compute cycle path
- path := make([]Object, len(seen))
- for t, j := range seen {
- path[j] = t.obj
- }
- path = path[i:]
- // only called during type checking, hence n.check != nil
- n.check.cycleError(path, firstInSrc(path))
- u = Typ[Invalid]
- break
+ if debug {
+ assert(!seen[t])
+ seen[t] = true
}
// don't recalculate the underlying
@@ -649,10 +646,10 @@
break
}
- if seen == nil {
- seen = make(map[*Named]int)
+ if debug {
+ seen[t] = true
}
- seen[t] = len(seen)
+ path = append(path, t)
t.unpack()
assert(t.rhs() != nil || t.allowNilRHS)
@@ -663,7 +660,7 @@
}
}
- for t := range seen {
+ for _, t := range path {
func() {
t.mu.Lock()
defer t.mu.Unlock()
diff --git a/src/go/types/check.go b/src/go/types/check.go
index d163012..44d3ae5 100644
--- a/src/go/types/check.go
+++ b/src/go/types/check.go
@@ -522,6 +522,9 @@
print("== sortObjects ==")
check.sortObjects()
+ print("== directCycles ==")
+ check.directCycles()
+
print("== packageObjects ==")
check.packageObjects()
diff --git a/src/go/types/cycles.go b/src/go/types/cycles.go
new file mode 100644
index 0000000..5445900
--- /dev/null
+++ b/src/go/types/cycles.go
@@ -0,0 +1,122 @@
+// Copyright 2025 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package types
+
+import "go/ast"
+
+// directCycles searches for direct cycles among package level type declarations.
+// See directCycle for details.
+func (check *Checker) directCycles() {
+ seen := make(map[*TypeName]bool)
+ for _, obj := range check.objList {
+ if tname, _ := obj.(*TypeName); tname != nil {
+ check.directCycle(tname, seen)
+ }
+ }
+}
+
+// directCycle checks if the declaration of the type given by tname is free of direct cycles.
+// A direct cycle exists if the path from tname's declaration's RHS leads from type name to
+// type name and eventually ends up on the path again, via regular or alias declarations; in
+// other words if there are no type literals (or basic types) on the path.
+// If a cycle is detected, a cycle error is reported and all types on the path are marked
+// as invalid.
+//
+// The seen map tracks which type names have been processed already. An entry can be in one
+// one of 3 states to represent a typical 3-state (white-grey-black) graph marking algorithm
+// for cycle detection:
+//
+// - entry doesn't exist: tname has not been seen before ("white")
+// - value is false : tname has been seen but is not done ("grey")
+// - value is true : tname has been seen and is done ("black")
+//
+// When directCycle returns, the seen entries for all type names on the path that starts
+// at tname are true ("black"), irrespective of whether there was a cycle or not.
+// This ensures that a type name is never iterated over multiple times during the search.
+func (check *Checker) directCycle(tname *TypeName, seen map[*TypeName]bool) {
+ if debug && check.conf._Trace {
+ check.trace(tname.Pos(), "-- path for %s", tname)
+ }
+
+ var path []*TypeName
+ for {
+ done, found := seen[tname]
+ if done {
+ // We have seen tname and it was done before ("black" type name).
+ break
+ }
+
+ if found {
+ // We have seen tname before but it is not done yet, so we must
+ // have a cycle ("grey" type name).
+ // TODO(gri) consider marking all types on the path as invalid
+ tname.setType(Typ[Invalid])
+ tname.setColor(black)
+
+ // Determine the start of the cycle on the path.
+ // This is the error case, so we don't care about the extra
+ // path traversal.
+ start := -1 // start of cycle
+ for i, tn := range path {
+ // Because the seen map contained no "grey" entries upon call of
+ // this function, the only grey entries that are in seen now are
+ // entries that were added during this iteration. This ensures
+ // that we're going to fine tname in the path somewhere.
+ if tname == tn {
+ start = i
+ break
+ }
+ }
+ assert(start >= 0)
+
+ // Convert cycle path into an object path.
+ var cycle []Object
+ for _, tname := range path[start:] {
+ cycle = append(cycle, tname)
+ }
+
+ check.cycleError(cycle, firstInSrc(cycle))
+ break
+ }
+
+ // The type name was never seen before ("white" type name).
+ // Mark it accordingly ("grey") and add it to the path.
+ seen[tname] = false
+ path = append(path, tname)
+
+ // tname is a type name, so it must have a corresponding type declaration and
+ // associated RHS type of that declaration.
+ // For direct cycle detection, we don't care about whether we have an alias or not.
+ // If the associated type is not a name, we're at the end of the path and we're done.
+ rhs, _ := check.objMap[tname].tdecl.Type.(*ast.Ident)
+ if rhs == nil {
+ break
+ }
+
+ // Determine the RHS type. If it's not found, we have an error but it will
+ // be reported later, and we can stop. If it's not a type name, we also
+ // cannot have a direct cycle and thus can stop.
+ tn, _ := check.pkg.scope.Lookup(rhs.Name).(*TypeName)
+ if tn == nil {
+ break
+ }
+
+ // Otherwise, continue with RHS.
+ tname = tn
+ }
+
+ // Mark all type names as done.
+ // This ensures that seen doesn't contain any seen but not done entries
+ // upon return from this function.
+ for _, tname := range path {
+ seen[tname] = true
+ }
+
+ if debug {
+ for _, done := range seen {
+ assert(done)
+ }
+ }
+}
diff --git a/src/go/types/named.go b/src/go/types/named.go
index 1f9e247..b106d7a 100644
--- a/src/go/types/named.go
+++ b/src/go/types/named.go
@@ -616,13 +616,18 @@
// type set to T. Aliases are skipped because their underlying type is
// not memoized.
//
-// This method also checks for cycles among alias and named types, which will
-// yield no underlying type. If such a cycle is found, the underlying type is
-// set to Typ[Invalid] and a cycle is reported.
+// resolveUnderlying assumes that there are no direct cycles; if there were
+// any, they were broken (by setting the respective types to invalid) during
+// the directCycles check phase.
func (n *Named) resolveUnderlying() {
assert(n.stateHas(unpacked))
- var seen map[*Named]int // allocated lazily
+ var seen map[*Named]bool // for debugging only
+ if debug {
+ seen = make(map[*Named]bool)
+ }
+
+ var path []*Named
var u Type
for rhs := Type(n); u == nil; {
switch t := rhs.(type) {
@@ -633,17 +638,9 @@
rhs = unalias(t)
case *Named:
- if i, ok := seen[t]; ok {
- // compute cycle path
- path := make([]Object, len(seen))
- for t, j := range seen {
- path[j] = t.obj
- }
- path = path[i:]
- // only called during type checking, hence n.check != nil
- n.check.cycleError(path, firstInSrc(path))
- u = Typ[Invalid]
- break
+ if debug {
+ assert(!seen[t])
+ seen[t] = true
}
// don't recalculate the underlying
@@ -652,10 +649,10 @@
break
}
- if seen == nil {
- seen = make(map[*Named]int)
+ if debug {
+ seen[t] = true
}
- seen[t] = len(seen)
+ path = append(path, t)
t.unpack()
assert(t.rhs() != nil || t.allowNilRHS)
@@ -666,7 +663,7 @@
}
}
- for t := range seen {
+ for _, t := range path {
func() {
t.mu.Lock()
defer t.mu.Unlock()
Change information
- M src/cmd/compile/internal/types2/check.go
- A src/cmd/compile/internal/types2/cycles.go
- M src/cmd/compile/internal/types2/named.go
- M src/go/types/check.go
- A src/go/types/cycles.go
- M src/go/types/named.go
Related details
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Robert Griesemer (Gerrit)
Robert Griesemer added 1 comment![]( "Open in Gerrit")
CL to be discussed. Please have a look.
Related details
- Mark Freeman
- Robert Griesemer
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Robert Griesemer (Gerrit)
Robert Griesemer voted![]( "Open in Gerrit")
| Commit-Queue | +1 |
| Hold | +1 |
Related details
- Mark Freeman
- Robert Griesemer
Code-Review
No-Holds
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mark Freeman (Gerrit)
Mark Freeman uploaded new patchset![]( "Open in Gerrit")
- TryBots-Pass: LUCI-TryBot-Result+1 by Go LUCI
Related details
- Robert Griesemer
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Robert Griesemer (Gerrit)
Robert Griesemer uploaded new patchset![]( "Open in Gerrit")
- Mark Freeman
- Robert Griesemer
Code-Review
No-Holds
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Robert Griesemer (Gerrit)
Robert Griesemer voted and added 1 comment![]( "Open in Gerrit")
Votes added by Robert Griesemer
| Auto-Submit | +1 |
| Code-Review | +1 |
| Commit-Queue | +1 |
| Hold | +0 |
1 comment
Related details
- Mark Freeman
- Robert Griesemer
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Robert Griesemer (Gerrit)
Robert Griesemer uploaded new patchset![]( "Open in Gerrit")
- TryBots-Pass: LUCI-TryBot-Result+1 by Go LUCI
Related details
- Mark Freeman
- Robert Griesemer
- Robert Griesemer
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Robert Griesemer (Gerrit)
Robert Griesemer voted![]( "Open in Gerrit")
| Auto-Submit | +1 |
| Code-Review | +1 |
| Commit-Queue | +1 |
Related details
- Mark Freeman
- Robert Griesemer
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Mark Freeman (Gerrit)
Mark Freeman added 29 comments![]( "Open in Gerrit")
Quite nice and easy to read — left a first round of minor comments.
if tname, _ := obj.(*TypeName); tname != nil {ditto
// directCycle checks if the declaration of the type given by tname is free of direct cycles.A type can only have at most 1 direct cycle.
Perhaps "given by tname contains a direct cycle"? (?)
// A direct cycle exists if the path from tname's declaration's RHS leads from type name to
// type name and eventually ends up on the path again, via regular or alias declarations; inAs an aside, I wonder if it would help to define some notion of reachability. If we had that, we could say something like:
"A direct cycle exists if a TypeName tn is reachable from tn by traversing only TypeNames".
// If a cycle is detected, a cycle error is reported and all types on the path are markedSeems this should use either a newline or start on the previous line, though I see this is done often in this CL.
// The pathIdx map tracks which type names have been processed already. An entry can be ins/already/ (?)
// one of 3 states as used in a typical 3-state (white-grey-black) graph marking algorithmwhite / grey / black (?)
// one of 3 states as used in a typical 3-state (white-grey-black) graph marking algorithms/one of 3/1 of 3
// - entry not found: tname has not been seen before ("white")If we define these shorthands, I think we should make more use of them below.
// at tname are set to a value < 0 ("black"), irrespective of whether there was a cycle or not.s/irrespective/regardless (?)
// at tname are set to a value < 0 ("black"), irrespective of whether there was a cycle or not.s/set to a value < 0 ("black")/marked black
Though see my other comment regarding marking only the back-edge.
// at tname are set to a value < 0 ("black"), irrespective of whether there was a cycle or not.s/or not/
// This ensures that a type name is never iterated over multiple times during the search.s/that a type name is never iterated over multiple times/a type name is traversed only once
if debug && check.conf.Trace {
check.trace(tname.Pos(), "-- path for %s", tname)
}Is this meant to print the path? I don't see how. Also, do we usually gate tracing by debug?
// We have seen tname and it was done before ("black" type name).
// (start can only be < 0 if it was found in the first place)Perhaps:
It's marked black, do not traverse again.
assert(found)This feels a bit odd — if `!found`, then `start` takes the default value for an int. The only way this would fail is if that map invariant changed.
// We have seen tname before but it is not done yet, so we must
// have a cycle ("grey" type name). start is the index where the
// cycle begins on the path.Perhaps:
// It's marked grey, so we have a cycle on the path beginning at start.
// Mark all types on the path as invalid and collect type names on cycle.It feels more correct to only handle the back-edge. Consider:
```
type B A
type A A
type C A
```
Since we go in source order, we'll process B first. This will mark both B and A invalid. When we visit C, we observe that A is done and break out _without marking C_.
I think either all of them should be marked as invalid or only the back-edge. This is a mix depending on whichever comes before the back-edge in source, which seems odd.
// The type name was never seen before ("white" type name).
// Mark it accordingly ("grey") and add it to the path.Perhaps:
// It's marked white; mark it grey and add it to the path.
// tname is a type name, so it must have a corresponding type declaration and
// associated RHS type of that declaration.Maybe we leave this away, I would consider these well-known invariants that might not need restatement (?)
if rhs == nil {s/rhs == nil/!ok
I understand this is convention; still, I would prefer not to potentially mask an error here since we are not expecting RHS to be `nil` unless `!ok`.
// Determine the RHS type. If it's not found, we have an error but it will
// be reported later, and we can stop. If it's not a type name, we also
// cannot have a direct cycle and thus can stop.It's not necessarily an error. For example, it could refer to something in the universe, but we know nothing in the universe can lead to a direct cycle.
// Otherwise, continue with RHS.s/RHS/the RHS.
tname = tnIf tname is used more frequently than tn, I think the more concise should go to the more frequently used (all else being equal).
Perhaps:
s/tname/tn
s/rhs/n
s/tn/rhs
Or alternatively:
s/tname/tn
s/tn/tn1
// Mark all type names as done.s/all type names/all traversed type names
s/as/
// This ensures that seen doesn't contain any seen but not done entriess/that seen doesn't contain any seen but not done entries/pathIdx contains no grey entries
// upon return from this function.s/return/returning
s/from this function/
Related details
- Robert Griesemer
- Robert Griesemer
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Robert Griesemer (Gerrit)
Robert Griesemer uploaded new patchset![]( "Open in Gerrit")
- TryBots-Pass: LUCI-TryBot-Result+1 by Go LUCI
Related details
- Robert Griesemer
- Robert Griesemer
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Robert Griesemer (Gerrit)
Robert Griesemer voted and added 28 comments![]( "Open in Gerrit")
Votes added by Robert Griesemer
| Auto-Submit | +1 |
| Code-Review | +1 |
| Commit-Queue | +1 |
28 comments
Thanks for the careful review. PTAL.
if tname, _ := obj.(*TypeName); tname != nil {Robert Griesemerditto
Done
// directCycle checks if the declaration of the type given by tname is free of direct cycles.A type can only have at most 1 direct cycle.
Perhaps "given by tname contains a direct cycle"? (?)
Done
// A direct cycle exists if the path from tname's declaration's RHS leads from type name to
// type name and eventually ends up on the path again, via regular or alias declarations; inAs an aside, I wonder if it would help to define some notion of reachability. If we had that, we could say something like:
"A direct cycle exists if a TypeName tn is reachable from tn by traversing only TypeNames".
Ok to introduce a notion of reachability. For now I think this is fine.
// If a cycle is detected, a cycle error is reported and all types on the path are markedSeems this should use either a newline or start on the previous line, though I see this is done often in this CL.
not sure what this refers to
// The pathIdx map tracks which type names have been processed already. An entry can be inRobert Griesemers/already/ (?)
Done
// one of 3 states as used in a typical 3-state (white-grey-black) graph marking algorithmwhite / grey / black (?)
Done
// one of 3 states as used in a typical 3-state (white-grey-black) graph marking algorithms/one of 3/1 of 3
Done
// at tname are set to a value < 0 ("black"), irrespective of whether there was a cycle or not.s/set to a value < 0 ("black")/marked black
Though see my other comment regarding marking only the back-edge.
Done
// at tname are set to a value < 0 ("black"), irrespective of whether there was a cycle or not.Robert Griesemers/or not/
Done
// at tname are set to a value < 0 ("black"), irrespective of whether there was a cycle or not.Robert Griesemers/irrespective/regardless (?)
Done
// This ensures that a type name is never iterated over multiple times during the search.s/that a type name is never iterated over multiple times/a type name is traversed only once
Done
if debug && check.conf.Trace {
check.trace(tname.Pos(), "-- path for %s", tname)
}Is this meant to print the path? I don't see how. Also, do we usually gate tracing by debug?
It's gated by debug because in normal tracing we don't want to see this level of detail. Changed the text.
// We have seen tname and it was done before ("black" type name).
// (start can only be < 0 if it was found in the first place)Perhaps:
It's marked black, do not traverse again.
Done
This feels a bit odd — if `!found`, then `start` takes the default value for an int. The only way this would fail is if that map invariant changed.
removed (was a leftover because I added the comment in parentheses)
// We have seen tname before but it is not done yet, so we must
// have a cycle ("grey" type name). start is the index where the
// cycle begins on the path.Perhaps:
// It's marked grey, so we have a cycle on the path beginning at start.
Done
// Mark all types on the path as invalid and collect type names on cycle.It feels more correct to only handle the back-edge. Consider:
```
type B A
type A A
type C A
```Since we go in source order, we'll process B first. This will mark both B and A invalid. When we visit C, we observe that A is done and break out _without marking C_.
I think either all of them should be marked as invalid or only the back-edge. This is a mix depending on whichever comes before the back-edge in source, which seems odd.
Excellent point.
Will mark the backedge (actually the start of the cycle) only.
// The type name was never seen before ("white" type name).
// Mark it accordingly ("grey") and add it to the path.Perhaps:
// It's marked white; mark it grey and add it to the path.
Done
// tname is a type name, so it must have a corresponding type declaration and
// associated RHS type of that declaration.Maybe we leave this away, I would consider these well-known invariants that might not need restatement (?)
Done
s/rhs == nil/!ok
I understand this is convention; still, I would prefer not to potentially mask an error here since we are not expecting RHS to be `nil` unless `!ok`.
Done
// Determine the RHS type. If it's not found, we have an error but it will
// be reported later, and we can stop. If it's not a type name, we also
// cannot have a direct cycle and thus can stop.It's not necessarily an error. For example, it could refer to something in the universe, but we know nothing in the universe can lead to a direct cycle.
adjusted (using check.lookup now, no need for a subtle optimization here)
// Otherwise, continue with RHS.Robert Griesemers/RHS/the RHS.
Done
If tname is used more frequently than tn, I think the more concise should go to the more frequently used (all else being equal).
Perhaps:
s/tname/tn
s/rhs/n
s/tn/rhsOr alternatively:
s/tname/tn
s/tn/tn1
tname is used widely elsewhere in the code. renamed tn to tname1.
s/all type names/all traversed type names
s/as/
Done
// This ensures that seen doesn't contain any seen but not done entriess/that seen doesn't contain any seen but not done entries/pathIdx contains no grey entries
Done
// upon return from this function.Robert Griesemers/return/returning
s/from this function/
Done
for _, index := range pathIdx {Robert Griesemers/index/idx
changed to i - this is debug code after all
Related details
- Mark Freeman
- Robert Griesemer
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |