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

Jump to bottom

proposal: Go 2: define slice equality #23725

Closed
pciet opened this issue Feb 6, 2018 · 6 comments
Closed

proposal: Go 2: define slice equality #23725

pciet opened this issue Feb 6, 2018 · 6 comments
Labels
FrozenDueToAge LanguageChange Proposal v2 A language change or incompatible library change
Milestone
Proposal

Comments

@pciet
Copy link
Contributor

pciet commented Feb 6, 2018

Slices should have equality defined which would allow slice types to be used as map keys and in comparison with == and !=.

An implementation proposal is that slices are compared by nil versus non-nil, length and backing array pointer, and then by the rules for array if length is equal but different arrays are pointed.

Array values are comparable if values of the array element type are comparable. Two array values are equal if their corresponding elements are equal.

Additionally self-referencing types using a slice cannot be compared, and values of map key types using a slice are copied; map types with a slice key can only be keyed by slice value.

In my experience this would have been useful for a map keyed by a path of X,Y coordinates. With Go 1 in this case a pointer to a slice was used, which means consumers of the map can do comparisons between these paths but cannot access the map using new paths without possible duplicates.

The choice of comparison by slice header vs by slice value is arbitrary and debated:

The problem is that different programs need different things for slice equality. Some want pointer equality as you suggest. Some want element comparisons, as is done for array equality. Without an obvious semantics for the operation, the language omits it entirely.

The topic is discussed here: https://groups.google.com/forum/#!topic/golang-nuts/ajXzEM6lqJI

In the first part of this golang-nuts thread one person asks for by-header while four ask for by-value. I’m in the by-value camp and I think picking one is better than having neither.
@gopherbot gopherbot added this to the Proposal milestone Feb 6, 2018
@pciet
Copy link
Contributor Author

pciet commented Feb 6, 2018

Related to #21829

@ianlancetaylor ianlancetaylor added LanguageChange v2 A language change or incompatible library change labels Feb 6, 2018
@ianlancetaylor
Copy link
Contributor

Given the use case of maps, this is also related to #395.

@ianlancetaylor
Copy link
Contributor

Personally I find the introduction of a unique special case for the handling of slice values as map keys to be rather troubling.

@Merovius
Copy link
Contributor

Merovius commented Feb 6, 2018

Additionally self-referencing types using a slice cannot be compared

// rough equivalent implemented at https://play.golang.org/p/cQ1qR_yfGiX
type T []interface{}

t1, t2 := T{nil}, T{nil}
t1[0], t2[0] = t1, t2

Note, that the type is not self-referencing, but the value is. And note, that this isn't a problem with arrays, as they would get copied, whereas slices share the same backing array.

@rogpeppe
Copy link
Contributor

rogpeppe commented Feb 7, 2018

values of map key types using a slice are copied

This seems problematic to me. It means that an expression like m[k] = true where m is a map and k is an interface might allocate arbitrary amounts of memory, and it also means that invariants in the keys might be disrupted. For example, this code would panic:

type key struct {
	slice []int
	first *int
}
m := make(map[key]bool)
k := key{slice: []int{1, 2}}
k.first = &k.slice[0]
m[k] = true
for k, _ := range m {
	if k.first != &k.slice[0] {
		panic("first does not point to first element of slice")
	}
}

Additionally self-referencing types using a slice cannot be compared

I don't believe it's possible to statically determine if a type is potentially self-referencing, unless you prohibit all slice comparisons that are made through an interface, because interface members can always be self-referential. Consider this code, for example:

type key struct {
	elem interface{}
}
ks := make([]key, 1)
ks[0].elem = ks
fmt.Println(ks == ks)

@ianlancetaylor
Copy link
Contributor

It seems non-orthogonal to say that slices used as a map key are copied. It seems disastrous to not copy them.

As was stated above, some people prefer a different equality mechanism, so picking this one makes the language more confusing for some people.

@golang golang locked and limited conversation to collaborators Apr 17, 2019
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge LanguageChange Proposal v2 A language change or incompatible library change
Projects
None yet
Milestone
Proposal
Development

No branches or pull requests
5 participants
@rogpeppe @Merovius @ianlancetaylor @pciet @gopherbot