vdl/value_rep.go - release.go.v23 - Git at Google

 // 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) + "}"
 }
	// 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) + "}"
	}