Skip to content

Instantly share code, notes, and snippets.

@jimmyfrasche
Last active August 22, 2017 00:07
Show Gist options
  • Save jimmyfrasche/d60e1bea282dfd50ae47d48e986fdcc1 to your computer and use it in GitHub Desktop.
Save jimmyfrasche/d60e1bea282dfd50ae47d48e986fdcc1 to your computer and use it in GitHub Desktop.
sketch of optimizing value-combiner
package reflectutil
import (
"reflect"
"strconv"
"strings"
)
//Combine(s, t), where s is of type S and t is of type T, returns a combined value
//with a type roughly equivalent to
// struct {
// S // set to s
// T // set to t
// }
//except that in the case of an ambiguous method selector the method
//on T is always chosen.
func Combine(s, t interface{}) interface{} {
sv := normalize(s)
tv := normalize(t)
//NB this factory could be cached on the reflect.Type of s and t (not sv and tv)
factory := build(sv.Type(), tv.Type())
v := factory.Combine(sv, tv)
return v.Interface()
}
//normalize ensures our code need only consider two cases
func normalize(w interface{}) reflect.Value {
//wrap w in a struct of one field
//so our code only has to worry about struct fields
wrapped := struct {
f interface{}
}{f: w}
v := reflect.ValueOf(wrapped)
//but if v was created by an earlier call to combine,
//unwrap it so we only ever have
//a previously created struct or a wrapped struct.
if f := v.Field(0); isMarked(f) {
return f
}
return v
}
//mark is field 0 in every type we create
//and cannot be any field of a type we do not create.
type mark struct{}
var marked = reflect.TypeOf(mark{})
func isMarked(v reflect.Value) bool {
return v.Kind() == reflect.Struct && v.NumField() > 0 && v.Field(0).Type() == marked
}
//build computes the method set of the new type,
//uses that to create a compact struct to hold only the necessary fields,
//and returns a factory for creating instances of this type.
func build(s, t reflect.Type) *factory {
var ms []method
//collect all methods on the fields of s and t
ms = collect(ms, s)
ms = collect(ms, t)
//we want a method lower in the list to supersede one above it
//so we reverse it then go through and throw out any we've seen before,
//then we reverse it again because we need it in the original order later
//so that we create the fields in the correct order
//
//note that it's possible to entirely remove a field if none of its methods
//contribute to the final object so we don't need to store a reference to it.
//Further, if all fields of s or t are removed, then that type is removed entirely.
//It will always remove the marker struct we use to see if we constructed a type.
ms = reversed(ms)
ms = dedup(ms)
ms = reversed(ms)
//get the length of the longest method name in ms
max := maxName(ms)
//the way we built ms we can list the same field many times,
//par it down to the unique entries
fields := uniqueFields(ms)
//map the field indices we have to the field index in the struct we build
fieldLookup := buildLookupTable(fields)
//generate the fields and use them to build the actual type
reflectFields := makeFields(fields, max)
Type := makeType(reflectFields, ms, fieldLookup)
//create a table for our factory to use to look up fields
//when creating values of our new type
on := map[reflect.Type]int{
s: 0,
t: 1,
}
table := buildFieldLookup(on, fields, fieldLookup)
return &factory{
Type: Type,
Fields: table,
}
}
type method struct {
Type reflect.Type //s or t
Field int //field in s or t that we're defined on
Method reflect.Method //the actual method
}
//collect the methods of t into a container that will let us
//do all future computations easily
func collect(ms []method, t reflect.Type) []method {
//we either have a t with one field
//or a t with 2+ fields where the first has no methods
for i := 0; i < t.NumField(); i++ {
f := t.Field(i).Type
for j := 0; i < f.NumMethod(); j++ {
ms = append(ms, method{
Type: t, //this is the type that contains the field
Field: i,
Method: f.Method(j),
})
}
}
return ms
}
//reversed returns a new copy of the slice in reverse order
func reversed(ms []method) []method {
var acc []method
for i := len(ms) - 1; i >= 0; i-- {
acc = append(acc, ms[i])
}
return acc
}
//dedup returns a copy of the slice containing only unique methods.
//It may remove fields or types entirely.
func dedup(ms []method) []method {
var acc []method
seen := map[name]bool{}
for _, m := range ms {
nm := name{
Name: m.Method.Name,
PkgPath: m.Method.PkgPath,
}
if seen[nm] {
continue
}
seen[nm] = true
acc = append(acc, m)
}
return acc
}
type name struct {
Name, PkgPath string
}
//maxName finds the longest method name
//so we can generate field names at least one longer
//to avoid collisions.
func maxName(ms []method) (max int) {
for _, m := range ms {
if L := len(m.Method.Name); L > max {
max = L
}
}
return max
}
type field struct {
Type reflect.Type //s or t
Field int //index in s or t
}
//uniqueFields projects ms to a list of unique (type, fieldIndex) pairs
func uniqueFields(ms []method) (fs []field) {
seen := map[field]bool{}
for _, m := range ms {
f := field{
Type: m.Type,
Field: m.Field,
}
if seen[f] {
continue
}
seen[f] = true
fs = append(fs, f)
}
return fs
}
//makeFields generates the required field definitions
func makeFields(fs []field, max int) []reflect.StructField {
acc := []reflect.StructField{ //the marker field
{
Name: fieldName(0, max),
Type: marked,
},
}
for i, f := range fs {
//by construction we don't need to worry about embedded fields or struct tags
acc = append(acc, reflect.StructField{
Name: fieldName(i+1, max), //+1 to account for marker field
Type: f.Type,
})
}
return acc
}
//fieldName creates a name guaranteed not to collide with any unexported methods
//or other fields created by this function.
func fieldName(fieldNum, maxName int) string {
number := strconv.FormatInt(int64(fieldNum), 36)
name := strings.Repeat(number, len(number)/maxName)
return "F" + name
}
//buildLookupTable creates a map from the (Type, Field index)
//to the field in the struct
func buildLookupTable(fs []field) map[field]int {
lu := map[field]int{}
for i, f := range fs {
lu[f] = i + 1 //account for marker field
}
return lu
}
func makeType(fs []reflect.StructField, ms []method, lu map[field]int) reflect.Type {
s := reflect.StructOf(fs)
t, b := reflect_NewTypeOf(s)
for _, m := range ms {
f := lu[field{ //field in t to access
Type: m.Type,
Field: m.Field,
}]
b.AddMethod(proxyMethod(t, f, m.Method))
}
b.Seal()
return t
}
//reflect_NewTypeOf is a proxy for the proposed reflect.NewTypeOf,
//allowing this to be compiled if not run.
//
//The returned type is "unsealed": it can be used as normal but values cannot be created
//until it is sealed.
//Creating a value of 'new' will panic until the type is sealed.
//
//The returned builder allows methods to be added.
//After all methods have been added calling Seal with seal the type 'new',
//allowing values of that type to be created.
func reflect_NewTypeOf(t reflect.Type) (new reflect.Type, builder interface {
//AddMethod adds a method to the type 'new'.
//
//This panics if it follows a call to Seal.
AddMethod(reflect.Method)
//Seal must be called to signal that no new methods will be added to the type 'new'.
Seal()
}) {
return
}
//proxyMethod creates a method that forwards to the correct method of one of our fields.
func proxyMethod(onto reflect.Type, rcvr int, m reflect.Method) reflect.Method {
in := make([]reflect.Type, m.Type.NumIn())
in[0] = onto //Realistically we should always recieve on a pointer to our type since the size is unbounded
for i := m.Type.NumIn() - 1; i >= 1; i-- {
in[i] = m.Type.In(i)
}
out := make([]reflect.Type, m.Type.NumOut())
for i := 0; i < m.Type.NumOut(); i++ {
out[i] = m.Type.Out(i)
}
typ := reflect.FuncOf(in, out, m.Type.IsVariadic())
fn := reflect.MakeFunc(typ, func(args []reflect.Value) []reflect.Value {
r := args[0].Field(rcvr)
args = append([]reflect.Value{r}, args[1:]...)
if m.Type.IsVariadic() {
return r.CallSlice(args[1:])
} else {
return r.Call(args[1:])
}
})
return reflect.Method{
Name: m.Name,
PkgPath: m.PkgPath,
Type: typ,
Func: fn,
}
}
func buildFieldLookup(on map[reflect.Type]int, fs []field, lu map[field]int) []fieldLookup {
var fl []fieldLookup
for _, f := range fs {
fl = append(fl, fieldLookup{
on: on[f.Type],
old: f.Field,
new: lu[f],
})
}
return fl
}
type fieldLookup struct {
on, old, new int
}
type factory struct {
Type reflect.Type
Fields []fieldLookup
}
//Combine creates an f.Type from s and t.
func (f *factory) Combine(s, t reflect.Value) reflect.Value {
on := []reflect.Value{s, t}
z := reflect.New(f.Type)
for _, f := range f.Fields {
v := on[f.on].Field(f.old)
z.Elem().Field(f.new).Set(v)
}
return z
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment