Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

cmd/compile: "in prove, detect loops with negative increments" breaks blackfriday tests #26116

Closed
heschi opened this issue Jun 28, 2018 · 4 comments
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. release-blocker
Milestone

Comments

@heschi
Copy link
Contributor

heschi commented Jun 28, 2018

CL 104041 (commit 6d379ad) breaks a test in blackfriday:

go test -v github.com/russross/blackfriday/ -run TestReference
=== RUN   TestReferenceOverride
--- PASS: TestReferenceOverride (0.02s)
=== RUN   TestReferenceLink
--- PASS: TestReferenceLink (0.04s)
=== RUN   TestReference
--- FAIL: TestReference (4.82s)
	ref_test.go:32: 
		panic while processing ["## Unordered\n\nAsterisks tight:\n\n*\tasterisk 1\n*\tasterisk 2\n*\tasterisk 3\n\n\nAsterisks loose:\n\n*\tasterisk 1\n\n*\tasterisk 2\n\n*\tasterisk 3\n\n* * "]: block input is missing terminating newline
=== RUN   TestReference_EXTENSION_NO_EMPTY_LINE_BEFORE_BLOCK
--- FAIL: TestReference_EXTENSION_NO_EMPTY_LINE_BEFORE_BLOCK (4.80s)
	ref_test.go:32: 
		panic while processing ["## Unordered\n\nAsterisks tight:\n\n*\tasterisk 1\n*\tasterisk 2\n*\tasterisk 3\n\n\nAsterisks loose:\n\n*\tasterisk 1\n\n*\tasterisk 2\n\n*\tasterisk 3\n\n* * "]: block input is missing terminating newline
FAIL
FAIL	github.com/russross/blackfriday	9.694s

I haven't looked at all at what exactly is happening, sorry.

CC @dr2chase @rasky @aclements

@heschi heschi added this to the Go1.11 milestone Jun 28, 2018
@heschi
Copy link
Contributor Author

heschi commented Jun 29, 2018

I dug into this. The bug comes while compiling this loop in listItem:
https://github.com/russross/blackfriday/blob/11635eb403ff09dbc3a6b5a007ab5ab09151c229/block.go#L1131-L1134

	for i > 0 && data[i-1] != '\n' {
		i++
	}

Note that the i > 0 clause is totally irrelevant -- i is increasing, not decreasing, and it doesn't start out negative. Removing that clause fixes the test.

I don't understand what precisely is going wrong in findIndVar, but somehow the extraneous clause must be convincing it that both the upper and lower boundaries are defined when clearly only the minimum is.

@ianlancetaylor ianlancetaylor added the NeedsFix The path to resolution is known, but the work has not been done. label Jun 29, 2018
@heschi
Copy link
Contributor Author

heschi commented Jul 2, 2018

I looked at this some more and I think I understand what's going on, but fixing it is way above my head. A self-contained repro:

package main

func main() {
	s := []int{0, 1, 2}
	i := 1
	for i > 0 && s[i] != 2 {
		i++
	}
	if i != 2 {
		panic("loop didn't run")
	}
}

I believe the problem is that we aren't checking that min and max move in the same direction as inc. Fixing this exact case, where the boundaries are constants, is easy; just check that the sign of inc is the same as the sign of max-min. But in the more common/important case, ranging over a slice, at least one of them will not be a constant. We need external information, maybe from the facts table, to check that. So maybe the fix is in prove, while calling addIndVarRestrictions?

Separately, while reading the code I noticed that we never set indVarMinExc. That almost has to be a bug.

@randall77
Copy link
Contributor

Certainly the induction variable conclusion is wrong (compile with -d=ssa/prove):

/usr/local/google/home/khr/gowork/issue26116.go:6:10: Induction variable: limits [1,0), increment 1 (v17)

The upper limit is wrong. It's treating i > 0 like it were i < 0. Somehow we have to ensure the comparison direction matches the increment direction.

@randall77 randall77 self-assigned this Jul 2, 2018
@gopherbot
Copy link

Change https://golang.org/cl/121940 mentions this issue: cmd/compile: ensure that loop condition is detected correctly

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. release-blocker
Projects
None yet
Development

No branches or pull requests

4 participants