vdl/compatible.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

import (
	"fmt"
	"sync"
)

// Compatible returns true if types a and b are compatible with each other.
//
// Compatibility is checked before every value conversion; it is the first-pass
// filter that disallows certain conversions.  Values of incompatible types are
// never convertible, while values of compatible types might not be convertible.
// E.g. float32 and byte are compatible types, and float32(1.0) is convertible
// to/from byte(1), but float32(1.5) is not convertible to/from any byte value.
//
// The reason we have a type compatibility check is to disallow invalid
// conversions that are hard to catch while converting values.  E.g. conversions
// between values of []bool and []float32 are invalid, but this is hard to catch
// if both lists are empty.
//
// Compatibility is reversible and transitive, except for the special Any type.
// Here are the rules:
//   o Any is compatible with all types.
//   o Optional is ignored for all rules (e.g. ?int is treated as int).
//   o Bool is only compatible with Bool.
//   o TypeObject is only compatible with TypeObject.
//   o Numbers are mutually compatible.
//   o String and enum are mutually compatible.
//   o Array and list are compatible if their elem types are compatible.
//   o Sets are compatible if their key types are compatible.
//   o Maps are compatible if their key and elem types are compatible.
//   o Structs are compatible if all fields with the same name are compatible,
//     and at least one field has the same name, or one of the types has no
//     fields.
//   o Unions are compatible if all fields with the same name are compatible,
//     and at least one field has the same name.
//
// Recursive types are checked for compatibility up to the first occurrence of a
// cycle in either type.  This leaves open the possibility of "obvious" false
// positives where types are compatible but values are not; this is a tradeoff
// favoring a simpler implementation and better performance over exhaustive
// checking.  This seems fine in practice since type compatibility is weaker
// than value convertibility, and since recursive types are not common.
func Compatible(a, b *Type) bool {
	a, b = a.NonOptional(), b.NonOptional()
	if a == b {
		return true // fastpath for common case
	}
	key := compatKey(a, b)
	if compat, ok := compatCache.lookup(key); ok {
		return compat
	}
	// Concurrent updates may cause compatCache to be updated multiple times.
	// This race is benign; we always end up with the same result.
	compat := compat(a, b, make(map[*Type]bool), make(map[*Type]bool))
	compatCache.update(key, compat)
	return compat
}

// TODO(toddw): Change this to a fixed-size LRU cache, otherwise it can grow
// without bounds and exhaust our memory.
var compatCache = &compatRegistry{compat: make(map[[2]*Type]bool)}

// compatRegistry is a cache of positive and negative compat results.  It is
// used to improve the performance of compatibility checks.  The only instance
// is the compatCache global cache.
type compatRegistry struct {
	sync.Mutex
	compat map[[2]*Type]bool
}

// The compat cache key is just the two types, which are already hash-consed.
// We make a minor attempt to normalize the order.
func compatKey(a, b *Type) [2]*Type {
	if a.Kind() > b.Kind() ||
		(a.Kind() == Enum && b.Kind() == Enum && a.NumEnumLabel() > b.NumEnumLabel()) ||
		(a.Kind() == Struct && b.Kind() == Struct && a.NumField() > b.NumField()) ||
		(a.Kind() == Union && b.Kind() == Union && a.NumField() > b.NumField()) {
		a, b = b, a
	}
	return [2]*Type{a, b}
}

func (reg *compatRegistry) lookup(key [2]*Type) (bool, bool) {
	reg.Lock()
	compat, ok := reg.compat[key]
	reg.Unlock()
	return compat, ok
}

func (reg *compatRegistry) update(key [2]*Type, compat bool) {
	reg.Lock()
	reg.compat[key] = compat
	reg.Unlock()
}

// compat is a recursive helper that implements Compatible.
func compat(a, b *Type, seenA, seenB map[*Type]bool) bool {
	// Normalize and break cycles from recursive types.
	a, b = a.NonOptional(), b.NonOptional()
	if a == b || seenA[a] || seenB[b] {
		return true
	}
	seenA[a], seenB[b] = true, true
	// Handle Any
	if a.Kind() == Any || b.Kind() == Any {
		return true
	}
	// Handle simple scalars
	if ax, bx := a.Kind() == Bool, b.Kind() == Bool; ax || bx {
		return ax && bx
	}
	if ax, bx := ttIsStringEnum(a), ttIsStringEnum(b); ax || bx {
		return ax && bx
	}
	if ax, bx := a.Kind().IsNumber(), b.Kind().IsNumber(); ax || bx {
		return ax && bx
	}
	if ax, bx := a.Kind() == TypeObject, b.Kind() == TypeObject; ax || bx {
		return ax && bx
	}
	// Handle composites
	switch a.Kind() {
	case Array, List:
		switch b.Kind() {
		case Array, List:
			return compat(a.Elem(), b.Elem(), seenA, seenB)
		}
		return false
	case Set:
		switch b.Kind() {
		case Set:
			return compat(a.Key(), b.Key(), seenA, seenB)
		}
		return false
	case Map:
		switch b.Kind() {
		case Map:
			return compat(a.Key(), b.Key(), seenA, seenB) && compat(a.Elem(), b.Elem(), seenA, seenB)
		}
		return false
	case Struct:
		switch b.Kind() {
		case Struct:
			if ttIsEmptyStruct(a) || ttIsEmptyStruct(b) {
				return true // empty struct is compatible with all other structs
			}
			return compatFields(a, b, seenA, seenB)
		}
		return false
	case Union:
		switch b.Kind() {
		case Union:
			return compatFields(a, b, seenA, seenB)
		}
		return false
	default:
		panic(fmt.Errorf("vdl: Compatible unhandled types %q %q", a, b))
	}
}

func ttIsStringEnum(tt *Type) bool {
	return tt.Kind() == String || tt.Kind() == Enum
}

func ttIsEmptyStruct(tt *Type) bool {
	return tt.Kind() == Struct && tt.NumField() == 0
}

// REQUIRED: a and b are either Struct or Union
func compatFields(a, b *Type, seenA, seenB map[*Type]bool) bool {
	// All fields with the same name must be compatible, and at least one field
	// must match.
	if a.NumField() > b.NumField() {
		a, seenA, b, seenB = b, seenB, a, seenA
	}
	fieldMatch := false
	for ax := 0; ax < a.NumField(); ax++ {
		afield := a.Field(ax)
		bfield, bindex := b.FieldByName(afield.Name)
		if bindex < 0 {
			continue
		}
		if !compat(afield.Type, bfield.Type, seenA, seenB) {
			return false
		}
		fieldMatch = true
	}
	return fieldMatch
}