A prototype Set implementation using the second round of Go Generics proposal with contracts

generic_set.go

// Package set is an adaptation of an existing Set implementation I wrote (that
// originally used interface{} as its underlying type) to the current Go 2
// Generics proposal at the time of this writing:
//     https://go.googlesource.com/proposal/+/4a54a00950b56dd0096482d0edae46969d7432a6/design/go2draft-contracts.md
//
// This adaptation retains the existing feature that a set can be of any type,
// without that type needing to be extended with any additional methods, as long
// as the caller can provide a separate Rules type that provides the necessary
// additional operations. Generics allows the compiler to check the requirement
// that only sets with the same rules can be used together, which was previously
// enforced only at runtime with panics.
//
// One difference compared to the old implementation is that the compiler cannot
// verify that two sets used together have the same Rules _value_, only that
// their type is the same. In practice Rules types tend to be empty types or
// types parameterized only by a type, in which case generics allows even the
// ones parameterized by a type (previously using reflection) to be presented
// as a zero-length type which therefore only has one possible value.
//
// However, toward the end of the file is a predefined Rules for comparable
// types that still requires a hash function to be provided; that example shows
// a limitation of this reliance on type checking for rules: the compiler cannot
// verify that two values of that type have the same value for the hash function,
// and would thus allow two sets of the same comparable type to be used together
// even if their hashing functions are not equal. That's not a failing of the
// generics design, but does illustrate that this separate rules mechanism
// may be better implemented as a generic interface type, rather than as a
// generic type parameter, and retain the existing runtime checks instead.
package set

import (
	"fmt"
)

// Set is an implementation of the concept of a set: a collection where all
// values are conceptually either in or out of the set, but the members are
// not ordered.
//
// This type primarily exists to be the internal type of sets in cty, but
// it is considered to be at the same level of abstraction as Go's built in
// slice and map collection types, and so should make no cty-specific
// assumptions.
//
// Set operations are not thread safe. It is the caller's responsibility to
// provide mutex guarantees where necessary.
//
// Set operations are not optimized to minimize memory pressure. Mutating
// a set will generally create garbage and so should perhaps be avoided in
// tight loops where memory pressure is a concern.
type Set(type Element, Rules Elements) struct {
	vals  map[int][]Element
	rules Rules
}

// Elements describes the relationship between a set's elements type and its
// rules type.
contract Elements(type Element, Rules) {
	Rules Hash(Element) int
	Rules Equivalent(Element, Element) bool
}

// NewSet returns an empty set with the membership rules given.
func NewSet(type Element, Rules Elements)(rules Rules, initial []Element) Set(Element, Rules) {
	s := Set(Element, Rules){
		vals:  map[int][]Element{},
		rules: rules,
	}

	for _, v := range initial {
		s.Add(v)
	}

	return s
}

// Add inserts the given value into the receiving Set.
//
// This mutates the set in-place. This operation is not thread-safe.
func (s Set(Element, Rules)) Add(val Element) {
	hv := s.rules.Hash(val)
	if _, ok := s.vals[hv]; !ok {
		s.vals[hv] = make([]Element, 0, 1)
	}
	bucket := s.vals[hv]

	// See if an equivalent value is already present
	for _, ev := range bucket {
		if s.rules.Equivalent(val, ev) {
			return
		}
	}

	s.vals[hv] = append(bucket, val)
}

// Remove deletes the given value from the receiving set, if indeed it was
// there in the first place. If the value is not present, this is a no-op.
func (s Set(Element, Rules)) Remove(val Element) {
	hv := s.rules.Hash(val)
	bucket, ok := s.vals[hv]
	if !ok {
		return
	}

	for i, ev := range bucket {
		if s.rules.Equivalent(val, ev) {
			newBucket := make([]Element, 0, len(bucket)-1)
			newBucket = append(newBucket, bucket[:i]...)
			newBucket = append(newBucket, bucket[i+1:]...)
			if len(newBucket) > 0 {
				s.vals[hv] = newBucket
			} else {
				delete(s.vals, hv)
			}
			return
		}
	}
}

// Has returns true if the given value is in the receiving set, or false if
// it is not.
func (s Set(Element, Rules)) Has(val Element) bool {
	hv := s.rules.Hash(val)
	bucket, ok := s.vals[hv]
	if !ok {
		return false
	}

	for _, ev := range bucket {
		if s.rules.Equivalent(val, ev) {
			return true
		}
	}
	return false
}

// Copy performs a shallow copy of the receiving set, returning a new set
// with the same rules and elements.
func (s Set(Element, Rules)) Copy() Set(Element, Rules) {
	ret := NewSet(s.rules, ([]Element)(nil))
	for k, v := range s.vals {
		ret.vals[k] = v
	}
	return ret
}

// Values returns a slice of all the values in the set in an undefined order.
func (s Set(Element, Rules)) Values() []Element {
	var ret []Element
	// Sort the bucketIds to ensure that we always produce the same result
	// for a given set content, even though that order is undefined.
	bucketIDs := make([]int, 0, len(s.vals))
	for id := range s.vals {
		bucketIDs = append(bucketIDs, id)
	}
	sort.Ints(bucketIDs)

	for _, bucketID := range bucketIDs {
		ret = append(ret, s.vals[bucketID]...)
	}

	return ret
}


// Length returns the number of values in the set.
func (s Set(Element, Rules)) Length() int {
	var count int
	for _, bucket := range s.vals {
		count = count + len(bucket)
	}
	return count
}

// Union returns a new set that contains all of the members of both the
// receiving set and the given set.
func (s1 Set(Element, Rules)) Union(s2 Set(Element, Rules)) Set(Element, Rules) {
	// This is not a particularly efficient implementation, but the point
	// here is just the API, not the implementation. (The original implementation
	// this derived from had an iterator interface that this was built on,
	// but I did not adapt _that_ to the generics proposal.
	rs := NewSet(s1.rules, s1.Values())
	for _, v := s2.Values() {
		rs.Add(v)
	}
	return rs
}

// Original implementation also had Intersection, Subtract, and SymmetricDifference,
// but all follow the same pattern of accepting another set of the same element
// type and rules type and returning a new set with the same type arguments.

// comparableRules is a Rules type that can be used with any comparable type
// as long as a suitable hashing function can be provided for it.
type comparableRules(type Element comparable) func (Element) int

func (r comparableRules(Element)) Hash(v Element) int {
	return r(v)
}

func (r comparableRules(Element)) Equivalent(a, b Element) bool {
	return a == b
}

// NewSetComparable is a convenience wrapper around NewSet that works with any
// Go type that supports the == operator if the caller can define a suitable
// hashing function for it.
func NewSetComparable(type Element comparable)(hash func (Element) int, initial []Element) Set(Element, comparableRules) {
	// This one is interesting in that it's an exported function that is
	// returning a type parameterized by an unexported type. Not sure from the
	// proposal as currently written whether that's valid?
	rules := comparableRules(hash)
	return NewSet(rules, initial)
}

contract WithEqual(type T) {
	T Equal(T) bool
}

// equalMethodRules is a Rules type that can be used with any type that
// has an Equal method.
//
// Because the contracts mechanism does not provide a way to call for a type
// that is comparable _or_ has an equals method, we must define this separately.
type equalMethodRules(type Element WithEqual) func (Element) int

func (r equalMethodRules(Element)) Hash(v Element) int {
	return r(v)
}

func (r equalMethodRules(Element)) Equivalent(a, b Element) bool {
	return a.Equal(b)
}

// NewSetWithEqual is a convenience wrapper around NewSet that works with any
// Go type that has a method Equals, if the caller can define a suitable
// hashing function for it.
func NewSetWithEqual(type Element WithEqual)(hash func (Element) int, initial []Element) Set(Element, equalMethodRules) {
	// This one is interesting in that it's an exported function that is
	// returning a type parameterized by an unexported type. Not sure from the
	// proposal as currently written whether that's valid?
	rules := equalMethodRules(hash)
	return NewSet(rules, initial)
}