Approaches to hashing CUE values

[lorrrrrrrenzo]

Hello,

I am doing some work around lattice caching and record-keeping, and the ability to generate reproducible hash values for a given CUE value would go a long way towards easing both efforts. My initial research suggests the use of hashstructure, used by Terraform extensively, with cue.Value or ast.Expr objects as a good initial approach.

What are some considerations that I should keep in mind as I begin this investigation, especially concerning hash stability (acknowledging that CUE has not yet reached v1)? I also have hopes that such a function could be added to the CUE Go package in the future, but that's a future conversation.

Thanks!

[lorrrrrrrenzo]

I need to put this through more thorough testing, but the following code is an initial approach that appears to work well enough. At its core is a conversion of a cue.Value into an ast.Node through its Syntax() method, which is then passed into hashstructure.Hash().

package cue_hasher

import (
	"hash/fnv"
	"strconv"

	"cuelang.org/go/cue"
	"github.com/mitchellh/hashstructure/v2"
)

var cueSyntaxOptions = []cue.Option{
	cue.All(),
	cue.Concrete(false),
	cue.DisallowCycles(false),
	cue.Docs(true),
	cue.Hidden(true), // https://github.com/cue-lang/cue/issues/3771
	cue.Raw(),
}

var hashStructureOptions = &hashstructure.HashOptions{
	IgnoreZeroValue: false,
	Hasher:          fnv.New64a(), // not strictly needed -- default is fnv.New64()
}

func Hash(val cue.Value) (string, error) {
	return HashString(val)
}

func HashString(val cue.Value) (string, error) {
	valHash, err := HashUint(val)
	if err != nil {
		return "", err
	}
	return strconv.FormatUint(valHash, 16), nil
}

func HashUint(val cue.Value) (uint64, error) {
	syn := val.Syntax(cueSyntaxOptions...)

	valHash, err := hashstructure.Hash(syn, hashstructure.FormatV2, hashStructureOptions)
	if err != nil {
		return 0, err
	}
	return valHash, nil
}

[infogulch]

You may need to think about canonicalization. i.e. equivalent structures that happen to be ordered differently. This will affect the hash, but the object is the same, somewhat defeating the point of using hashes. I think there has been discussion in this repo about this property under the name topological sorting (?), but I'm not sure what the status is.

[lorrrrrrrenzo]

Thanks for the tip about topological sorting. I was able to find this discussion from a few years ago asking for something similar, and found the toposort package.

toposort and its in-project dependencies (most notably adt.*) are all in internal packages, suggesting that a short-term solution will require manipulating the AST in a ast.Node. In the long term I can see the case for adding a func TopoSort() Option for cue.Syntax(), though that is obviously up for discussion.