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
heschik opened this issue Jun 28, 2018 · 4 comments

Comments

Projects
None yet
4 participants
@heschik
Copy link
Contributor

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

@heschik heschik added this to the Go1.11 milestone Jun 28, 2018

@heschik

This comment has been minimized.

Copy link
Contributor Author

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.

@heschik

This comment has been minimized.

Copy link
Contributor Author

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

This comment has been minimized.

Copy link
Contributor

commented Jul 2, 2018

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

This comment has been minimized.

Copy link

commented Jul 2, 2018

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.