1

I have a slice of reflect.Type values that define the input type for a function and I want to cache the result using sync.Map.

I realize slices cannot be used as map keys in general so I have searched far and wide for a way to create unique keys from multiple reflect.Type values. Ideas include

  1. Using a concatenation of reflect.Type.String() for each subkey. The godoc explicitly says not to use it for equality so the keys would not be unique.
  2. Use a concatenation of fmt.Sprintf("%#v", subKey) - see here. I don't know whether these keys would be unique.
  3. Create a tree out of sync.Maps [a map of maps of maps... of depth len(slice)] where the lookup for a value involves traversing deeper in the tree of maps for each subkey. This seems slow and cumbersome but should work.
  4. Hardcode a limit on the number of keys and store it as an array whose size is the upper limit. This would work but the hardcoded limit is annoying when you need to exceed the limit.

A reference on why slices can't be used as keys indicates that how to define equality on slices may be unclear. In this case I want element-wise equality if and only if the slices have the same length.

It would be awesome to find a byte representation of reflect.Type similar to the solution to a similar problem here.

See also hashing-reflect-type.

Jonathan Hall
  • 75,165
  • 16
  • 143
  • 189
Brent
  • 113
  • 6
  • A tree approach looks good for me, but the question about `reflect.Type` bytes representation still looks reasonable. How about the `encoding/gob`, would it work here? – ei-grad Apr 22 '18 at 12:13
  • Why not use the string approach in [hashing-relfect-type](https://stackoverflow.com/questions/49634346/hashing-reflect-type/49634974#49634974)? The answer provides a unique string for a []reflect.Type. – Charlie Tumahai Apr 22 '18 at 13:46
  • @CeriseLimón - you're right. I can follow [hashing-reflect-type](https://stackoverflow.com/questions/49634346/hashing-reflect-type/49634974#49634974) to keep a map of unique ids for each `reflect.Type` and then combine those to make keys for my map whose keys are `[]reflect.Type`. I overlooked this when I read that answer. Feel free to make it an answer or I can! – Brent Apr 22 '18 at 18:14

1 Answers1

0

Following a suggestion in the comments I implemented a solution using the hashing-reflect-type solution, but for any slice of hashable types.

import (
    "reflect"
    "strconv"
    "strings"
    "sync"
)

// IdHashmap stores the next id as an int64 and a map pointing to the
// unique id for each hashable key
type IdHashmap struct {
    nextId  int64
    hashMap map[interface{}]string
    mutex   sync.Mutex
}

// LoadOrStore returns the existing value for the key if present. 
// Otherwise, it stores and returns the given value.
// The loaded result is true if the value was loaded, false if stored.
// The value is an a unique id for the object that was passed (or 
// object reference). It is a stringified int64
// representing the number of unique objects passed to this IdHashmap 
// before this object was first passed in
func (hm *IdHashmap) LoadOrStore(subKey interface{}) (hashmapId string) {
    if hm.hashMap == nil {
        hm.hashMap = make(map[interface{}]string)
    }
    // the entry for a given key is only ever written once but read many times
    if id, ok := hm.hashMap[subKey]; ok {
        return id
    }
    hm.mutex.Lock()
    // check for the possibility that someone else wrote a value for 
    // this subKey while this thread waited for the lock
    if id, ok := hm.hashMap[subKey]; ok {
        return id
    }
    id := strconv.FormatInt(hm.nextId, 10)
    hm.nextId++
    hm.hashMap[subKey] = id
    hm.mutex.Unlock()
    return id
}

// LoadOrStoreForSlice gets a unique id for a given slice of objects 
// by concatenating hashmapids of its elements
func (hm *IdHashmap) LoadOrStoreForSlice(keys interface{}) (hashmapId string) {
    if reflect.TypeOf(keys).Kind() == reflect.Slice {
        s := reflect.ValueOf(keys)

        ids := make([]string, s.Len())
        for i := 0; i < s.Len(); i++ {
            ids[i], _ = hm.LoadOrStore(s.Index(i))
        }
        return strings.Join(ids, ",")
    }
    // if not a slice try hashing directly in case the type is hashable
    id, _ := hm.LoadOrStore(keys)
    return id
}
Brent
  • 113
  • 6