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

Inconsistent triggering behaviour in properties over arrays #840

Open
gottschali opened this issue Feb 5, 2025 · 0 comments
Open

Inconsistent triggering behaviour in properties over arrays #840

gottschali opened this issue Feb 5, 2025 · 0 comments

Comments

@gottschali
Copy link

The pure function isSorted returns true if and only an array is sorted ascendingly.
When I test it with all binary arrays of length 4, isSorted(a) or !isSorted(a) can be asserted, except for the following non-sorted arrays:

[4]int{0, 0, 1, 0}
[4]int{0, 1, 0, 1}
[4]int{1, 1, 0, 1}

I find this behaviour confusing: why can I assert that [4]int{1, 1, 1, 0} is not sorted but the assertion might fail for [4]int{0, 0, 1, 0}.

Program:

package main

const N = 4

ghost
pure
ensures sorted == forall i, j int :: {arr[i], arr[j]} 0 <= i && i < j && j < N ==> arr[i] <= arr[j]
decreases
func isSorted(arr [N]int) (sorted bool) {
	return aux(arr, 1) == N
}

ghost
pure
requires 0 < idx && idx <= N
requires forall i, j int :: {arr[i], arr[j]} 0 <= i && i < j && j < idx ==> arr[i] <= arr[j]
ensures 0 < k && k <= N
ensures k < N ==> arr[k-1] > arr[k]
ensures (k == N) ==> forall i, j int :: {arr[i], arr[j]} 0 <= i && i < j && j < N ==> arr[i] <= arr[j]
decreases N - idx
func aux(arr [N]int, idx int) (k int) {
	return idx == N ? N : (arr[idx-1] <= arr[idx] ? aux(arr, idx + 1) : idx)
}

func c0() {
	a := [4]int{0, 0, 0, 0}
	assert isSorted(a)
}

func c1() {
	a := [4]int{0, 0, 0, 1}
	assert isSorted(a)
}

func c2() {
	a := [4]int{0, 0, 1, 0}
	assert !isSorted(a) // might not hold
}
func c3() {
	a := [4]int{0, 0, 1, 1}
	assert isSorted(a)
}
func c4() {
	a := [4]int{0, 1, 0, 0}
	assert !isSorted(a)
}
func c5() {
	a := [4]int{0, 1, 0, 1}
	assert !isSorted(a) // might not hold
}
func c6() {
	a := [4]int{0, 1, 1, 0}
	assert !isSorted(a)
}
func c7() {
	a := [4]int{0, 1, 1, 1}
	assert isSorted(a)
}
func c8() {
	a := [4]int{1, 0, 0, 0}
	assert !isSorted(a)
}
func c9() {
	a := [4]int{1, 0, 0, 1}
	assert !isSorted(a)
}
func c10() {
	a := [4]int{1, 0, 1, 0}
	assert !isSorted(a)
}
func c11() {
	a := [4]int{1, 0, 1, 1}
	assert !isSorted(a)
}
func c12() {
	a := [4]int{1, 1, 0, 0}
	assert !isSorted(a)
}
func c13() {
	a := [4]int{1, 1, 0, 1}
	assert !isSorted(a) // might not hold
}
func c14() {
	a := [4]int{1, 1, 1, 0}
	assert !isSorted(a)
}
func c15() {
	a := [4]int{1, 1, 1, 1}
	assert isSorted(a)
}
@jcp19 jcp19 changed the title Possible inconsistency in the array encoding Inconsistent triggering behaviour in properties over arrays Feb 5, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant