Overview¶

Package deephash hashes a Go value recursively, in a predictable order,without looping. The hash is only valid within the lifetime of a program.Users should not store the hash on disk or send it over the network.The hash is sufficiently strong and unique such thatHash(&x) == Hash(&y) is an appropriate replacement for x == y.

The definition of equality is identical to reflect.DeepEqual except:

• Floating-point values are compared based on the raw bits,which means that NaNs (with the same bit pattern) are treated as equal.
• time.Time are compared based on whether they are the same instant in timeand also in the same zone offset. Monotonic measurements and zone namesare ignored as part of the hash.
• netip.Addr are compared based on a shallow comparison of the struct.

WARNING: This package, like most of the tailscale.com Go module,should be considered Tailscale-internal; we make no API promises.

Cycle detection¶

This package correctly handles cycles in the value graph,but in a way that is potentially pathological in some situations.

The algorithm for cycle detection operates bypushing a pointer onto a stack whenever deephash is visiting a pointer andpopping the pointer from the stack after deephash is leaving the pointer.Before visiting a new pointer, deephash checks whether it has already beenvisited on the pointer stack. If so, it hashes the index of the pointeron the stack and avoids visiting the pointer.

This algorithm is guaranteed to detect cycles, but may expand pointersmore often than a potential alternate algorithm that remembers all pointersever visited in a map. The current algorithm uses O(D) memory, where Dis the maximum depth of the recursion, while the alternate algorithmwould use O(P) memory where P is all pointers ever seen, which can be a lot,and most of which may have nothing to do with cycles.Also, the alternate algorithm has to deal with challenges of producingdeterministic results when pointers are visited in non-deterministic wayssuch as when iterating through a Go map. The stack-based algorithm avoidsthis challenge since the stack is always deterministic regardless ofnon-deterministic iteration order of Go maps.

To concretely see how this algorithm can be pathological,consider the following data structure:

var big *Item = ... // some large data structure that is slow to hashvar manyBig []*Itemfor i := range 1000 {manyBig = append(manyBig, &big)}deephash.Hash(manyBig)

Here, the manyBig data structure is not even cyclic.We have the same big *Item being stored multiple times in a []*Item.When deephash hashes []*Item, it hashes each individual *Itemnot realizing that it had just done the computation earlier.To avoid the pathological situation, Item should implementSelfHasher andmemoize attempts to hash itself.

Index¶

• func HasherForType[T any](opts ...Option) func(*T) Sum
• func Update[T any](last *Sum, v *T) (changed bool)
• type Hasher
• • func (h Hasher) HashBytes(b []byte)
  • func (h Hasher) HashString(s string)
  • func (h Hasher) HashSum(s Sum)
  • func (h Hasher) HashUint16(n uint16)
  • func (h Hasher) HashUint32(n uint32)
  • func (h Hasher) HashUint64(n uint64)
  • func (h Hasher) HashUint8(n uint8)
• type Option
• • func ExcludeFields[T any](fields ...string) Option
  • func IncludeFields[T any](fields ...string) Option
• type SelfHasher
• type Sum
• • func Hash[T any](v *T) Sum
• • func (s Sum) AppendTo(b []byte) []byte
  • func (s Sum) String() string

This section is empty.

This section is empty.