value_rep.go

// Copyright 2015 The Vanadium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package vdl

// This file contains the non-trivial "rep" types, which are the representation
// of values of certain types.

// repBytes represents []byte and [N]byte values.  We special-case these kinds
// of types to easily support the Value.Bytes() and Value.CopyBytes() methods,
// which makes usage more convenient for the user.  This is also a more
// efficient representation.
type repBytes []byte

// allZeroBytes is a buffer containing all 0 bytes.  It's used for fast filling
// of 0 bytes after resizing.
var allZeroBytes = make(repBytes, 1024)

func zeroRepBytes(len int) *repBytes {
	if len == 0 {
		return new(repBytes)
	}
	rep := make(repBytes, len)
	return &rep
}

func copyRepBytes(rep *repBytes) *repBytes {
	if *rep == nil {
		return new(repBytes)
	}
	cp := make(repBytes, len(*rep))
	copy(cp, *rep)
	return &cp
}

func (rep *repBytes) AllBytesZero() bool {
	for _, b := range *rep {
		if b != 0 {
			return false
		}
	}
	return true
}

// Resize resizes rep to size n, ignoring existing bytes.
func (rep *repBytes) Resize(n int) {
	if n <= cap(*rep) {
		*rep = (*rep)[:n]
	} else {
		*rep = make(repBytes, n)
	}
}

// AssignLen resizes rep to size n, ensuring existing bytes are transferred, and
// all bytes beyond the original length are initialized to zero.
func (rep *repBytes) AssignLen(n int) {
	if n <= cap(*rep) {
		// Increase rep length, and fill rep[oldlen:n] with zero bytes.
		oldlen := len(*rep)
		*rep = (*rep)[:n]
		for ix := oldlen; ix < n; {
			ix += copy((*rep)[ix:], allZeroBytes)
		}
	} else {
		oldrep := *rep
		*rep = make(repBytes, n)
		copy(*rep, oldrep)
	}
}

// repMap represents set and map values.  There are two underlying
// representations depending on the key type.  We decide which one to use based
// on the type of the map key, and never change representations thereafter.
//   fast: Use a real Go map to associate keys with a kvPair
//   slow: Just a slice of kvPairs.
//
// Fast has the same O(1) amortized complexity as regular Go maps for insert and
// lookup, while slow is O(N).  Since fast uses a real Go map, it only works for
// maps whose key type is allowed in a real Go map; e.g. structs are implemented
// as a slice of fields, but slices aren't allowed as Go map keys, so that must
// use slow.
//
// TODO(toddw): Slow is really slow; e.g. Equal is quadratic.  Speed this up.
type repMap struct {
	fastIndex map[interface{}]kvPair // maps with scalar keys use the fast rep
	slowIndex []kvPair               // everything else uses the slow rep
}

type kvPair struct {
	key, val *Value
}

func copyKVPair(kv kvPair) kvPair {
	return kvPair{CopyValue(kv.key), CopyValue(kv.val)}
}

func (kv kvPair) String() string {
	s := stringRep(kv.key.t, kv.key.rep)
	if kv.val != nil {
		s += ": " + stringRep(kv.val.t, kv.val.rep)
	}
	return s
}

func useFastIndex(key *Type) bool {
	// TODO(toddw): Structs with exactly 1 simple field may also use fast.
	switch key.kind {
	case Bool, Byte, Uint16, Uint32, Uint64, Int8, Int16, Int32, Int64, Float32, Float64, String, Enum:
		return true
	}
	if key.IsBytes() {
		return true
	}
	return false
}

// fastKeyRep returns a representation of key that may be used in a regular Go
// map.  It's only called on keys where useFastIndex returns true.
func fastKeyRep(key *Value) interface{} {
	switch {
	case key.Kind() == Float32:
		// Float32 is represented as float64 in vdl.Value, but we must convert to
		// float32 to ensure map lookups work with the correct precision.  Otherwise
		// a single float32 may be reprsesented as different keys.
		return float32(key.rep.(float64))
	case key.t.IsBytes():
		// Convert []byte into a string so that it can be used as a map key.
		return string(key.Bytes())
	}
	return key.rep
}

func zeroRepMap(key *Type) *repMap {
	rep := &repMap{}
	if useFastIndex(key) {
		rep.fastIndex = make(map[interface{}]kvPair)
	}
	return rep
}

func copyRepMap(rep *repMap) *repMap {
	cp := &repMap{}
	if rep.fastIndex != nil {
		cp.fastIndex = make(map[interface{}]kvPair, len(rep.fastIndex))
		for keyrep, kv := range rep.fastIndex {
			cp.fastIndex[keyrep] = copyKVPair(kv)
		}
	} else {
		if len(rep.slowIndex) > 0 {
			cp.slowIndex = make([]kvPair, len(rep.slowIndex))
			for index, kv := range rep.slowIndex {
				cp.slowIndex[index] = copyKVPair(kv)
			}
		}
	}
	return cp
}

func equalRepMap(a, b *repMap) bool {
	if a.Len() != b.Len() {
		return false
	}
	if a.fastIndex != nil {
		for _, akv := range a.fastIndex {
			if !b.hasKV(akv) {
				return false
			}
		}
	} else {
		for _, akv := range a.slowIndex {
			if !b.hasKV(akv) {
				return false
			}
		}
	}
	return true
}

func (rep *repMap) hasKV(kv kvPair) bool {
	val, ok := rep.Index(kv.key)
	if !ok {
		return false
	}
	return EqualValue(kv.val, val)
}

func (rep *repMap) Len() int {
	if rep.fastIndex != nil {
		return len(rep.fastIndex)
	} else {
		return len(rep.slowIndex)
	}
}

func (rep *repMap) String() string {
	s := "{"
	if rep.fastIndex != nil {
		first := true
		for _, kv := range rep.fastIndex {
			if !first {
				s += ", "
			}
			s += kv.String()
			first = false
		}
	} else {
		for index, kv := range rep.slowIndex {
			if index > 0 {
				s += ", "
			}
			s += kv.String()
		}
	}
	return s + "}"
}

func (rep *repMap) Keys() []*Value {
	len := rep.Len()
	if len == 0 {
		return nil
	}
	keys := make([]*Value, len)
	if rep.fastIndex != nil {
		index := 0
		for _, kv := range rep.fastIndex {
			keys[index] = CopyValue(kv.key)
			index++
		}
	} else {
		for index, kv := range rep.slowIndex {
			keys[index] = CopyValue(kv.key)
		}
	}
	return keys
}

func (rep *repMap) Index(key *Value) (*Value, bool) {
	if rep.fastIndex != nil {
		if kv, ok := rep.fastIndex[fastKeyRep(key)]; ok {
			return kv.val, true
		}
	} else {
		for _, kv := range rep.slowIndex {
			if EqualValue(kv.key, key) {
				return kv.val, true
			}
		}
	}
	return nil, false
}

func (rep *repMap) Assign(key, elem *Value) {
	if rep.fastIndex != nil {
		rep.fastIndex[fastKeyRep(key)] = kvPair{key, elem}
	} else {
		for ix := 0; ix < len(rep.slowIndex); ix++ {
			if EqualValue(rep.slowIndex[ix].key, key) {
				rep.slowIndex[ix].val = elem
				return
			}
		}
		// The key doesn't exist in the slow index; append it.
		rep.slowIndex = append(rep.slowIndex, kvPair{key, elem})
	}
}

func (rep *repMap) Delete(key *Value) {
	if rep.fastIndex != nil {
		delete(rep.fastIndex, fastKeyRep(key))
	} else {
		for ix := 0; ix < len(rep.slowIndex); ix++ {
			if EqualValue(rep.slowIndex[ix].key, key) {
				// Delete entry ix by moving last entry into ix and shrinking by 1.
				last := len(rep.slowIndex) - 1
				rep.slowIndex[ix] = rep.slowIndex[last]
				rep.slowIndex = rep.slowIndex[:last]
				return
			}
		}
	}
}

// repSequence represents the elements of a list and array, and the fields of a
// struct.  Each value is lazily initialized; the semantics dictate that nil is
// indistinguishable from zero values.
//
// Arrays and structs are initialized to their fixed-length, while lists are
// initialized to nil.
type repSequence []*Value

func zeroRepSequence(len int) *repSequence {
	if len == 0 {
		return new(repSequence)
	}
	rep := make(repSequence, len)
	return &rep
}

func copyRepSequence(rep *repSequence) *repSequence {
	if *rep == nil {
		return new(repSequence)
	}
	cp := make(repSequence, len(*rep))
	for index, val := range *rep {
		cp[index] = CopyValue(val)
	}
	return &cp
}

func equalRepSequence(a, b *repSequence) bool {
	if len(*a) != len(*b) {
		return false
	}
	for index, aval := range *a {
		// Handle cases where we're using nil to represent zero values.
		switch bval := (*b)[index]; {
		case aval == nil && bval != nil:
			if !bval.IsZero() {
				return false
			}
		case aval != nil && bval == nil:
			if !aval.IsZero() {
				return false
			}
		case !EqualValue(aval, bval):
			return false
		}
	}
	return true
}

func (rep *repSequence) AllValuesZero() bool {
	for _, val := range *rep {
		if val != nil && !val.IsZero() {
			return false
		}
	}
	return true
}

func (rep *repSequence) String(t *Type) string {
	s := "{"
	for index, val := range *rep {
		if index > 0 {
			s += ", "
		}
		valtype := t.elem
		if t.Kind() == Struct {
			valtype = t.fields[index].Type
			s += t.fields[index].Name
			s += ": "
		}
		if val == nil {
			s += stringRep(valtype, zeroRep(valtype))
		} else {
			s += stringRep(val.t, val.rep)
		}
	}
	return s + "}"
}

// AssignLen resizes rep to size n, ensuring existing values are transferred,
// and all values beyond the original length are initialized to nil.
func (rep *repSequence) AssignLen(n int) {
	if n <= cap(*rep) {
		// Increase rep length, and fill rep[oldlen:n] with nil values.
		oldlen := len(*rep)
		*rep = (*rep)[:n]
		for ix := oldlen; ix < n; ix++ {
			(*rep)[ix] = nil
		}
	} else {
		oldrep := *rep
		*rep = make(repSequence, n)
		copy(*rep, oldrep)
	}
}

func (rep *repSequence) Index(t *Type, index int) *Value {
	if oldval := (*rep)[index]; oldval != nil {
		return oldval
	}
	// Lazy initialization; create the new value upon first access.
	newval := ZeroValue(t)
	(*rep)[index] = newval
	return newval
}

// repUnion represents a Union value, which includes the field index of its
// type, and the underlying elem.
type repUnion struct {
	index int
	value *Value
}

func equalRepUnion(a, b *repUnion) bool {
	return a.index == b.index && EqualValue(a.value, b.value)
}

func (rep *repUnion) String(t *Type) string {
	v := rep.value
	return "{" + t.fields[rep.index].Name + ": " + stringRep(v.t, v.rep) + "}"
}