tools/src/cts/query/tree.go - dawn - Git at Google

 // Copyright 2022 The Dawn & Tint Authors
 //
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are met:
 //
 // 1. Redistributions of source code must retain the above copyright notice, this
 //    list of conditions and the following disclaimer.
 //
 // 2. Redistributions in binary form must reproduce the above copyright notice,
 //    this list of conditions and the following disclaimer in the documentation
 //    and/or other materials provided with the distribution.
 //
 // 3. Neither the name of the copyright holder nor the names of its
 //    contributors may be used to endorse or promote products derived from
 //    this software without specific prior written permission.
 //
 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 // DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 // OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 package query

 import (
 	"errors"
 	"fmt"
 	"io"
 	"sort"
 )

 // Tree holds a tree structure of Query to generic Data type.
 // Each separate suite, file, test of the query produces a separate tree node.
 // All cases of the query produce a single leaf tree node.
 type Tree[Data any] struct {
 	TreeNode[Data]
 }

 // TreeNode is a single node in the Tree
 type TreeNode[Data any] struct {
 	// The full query of the node
 	Query Query
 	// The data associated with this node. nil is used to represent no-data.
 	Data *Data
 	// Children of the node. Keyed by query.Target and name.
 	Children TreeNodeChildren[Data]
 }

 // TreeNodeChildKey is the key used by TreeNode for the Children map
 type TreeNodeChildKey struct {
 	// The child name. This is the string between `:` and `,` delimiters.
 	// Note: that all test cases are held by a single TreeNode.
 	Name string
 	// The target type of the child. Examples:
 	//  Query           |  Target of 'child'
 	// -----------------+--------------------
 	// parent:child     | Files
 	// parent:x,child   | Files
 	// parent:x:child   | Test
 	// parent:x:y,child | Test
 	// parent:x:y:child | Cases
 	//
 	// It's possible to have a directory and '.spec.ts' share the same name,
 	// hence why we include the Target as part of the child key.
 	Target Target
 }

 // TreeNodeChildren is a map of TreeNodeChildKey to TreeNode pointer.
 // Data is the data type held by a TreeNode.
 type TreeNodeChildren[Data any] map[TreeNodeChildKey]*TreeNode[Data]

 // sortedChildKeys returns all the sorted children keys.
 func (n *TreeNode[Data]) sortedChildKeys() []TreeNodeChildKey {
 	keys := make([]TreeNodeChildKey, 0, len(n.Children))
 	for key := range n.Children {
 		keys = append(keys, key)
 	}
 	sort.Slice(keys, func(i, j int) bool {
 		a, b := keys[i], keys[j]
 		switch {
 		case a.Name < b.Name:
 			return true
 		case a.Name > b.Name:
 			return false
 		case a.Target < b.Target:
 			return true
 		case a.Target > b.Target:
 			return false
 		}
 		return false
 	})
 	return keys
 }

 // traverse performs a depth-first-search of the tree calling f for each visited
 // node, starting with n, then visiting each of children in sorted order
 // (pre-order traversal).
 func (n *TreeNode[Data]) traverse(f func(n *TreeNode[Data]) error) error {
 	if err := f(n); err != nil {
 		return err
 	}
 	for _, key := range n.sortedChildKeys() {
 		if err := n.Children[key].traverse(f); err != nil {
 			return err
 		}
 	}
 	return nil
 }

 // Merger is a function used to merge the children nodes of a tree.
 // Merger is called with the Data of each child node. If the function returns a
 // non-nil Data pointer, then this is used as the merged result. If the function
 // returns nil, then the node will not be merged.
 type Merger[Data any] func([]Data) *Data

 // merge collapses tree nodes based on child node data, using the function f.
 // merge operates on the leaf nodes first, working its way towards the root of
 // the tree.
 // Returns the merged target data for this node, or nil if the node is not a
 // leaf and its children has non-uniform data.
 func (n *TreeNode[Data]) merge(f Merger[Data]) *Data {
 	// If the node is a leaf, then simply return the node's data.
 	if len(n.Children) == 0 {
 		return n.Data
 	}

 	// Build a map of child target to merged child data.
 	// A nil for the value indicates that one or more children could not merge.
 	mergedChildren := map[Target][]Data{}
 	for key, child := range n.Children {
 		// Call merge() on the child. Even if we cannot merge this node, we want
 		// to do this for all children so they can merge their sub-graphs.
 		childData := child.merge(f)

 		if childData == nil {
 			// If merge() returned nil, then the data could not be merged.
 			// Mark the entire target as unmergeable.
 			mergedChildren[key.Target] = nil
 			continue
 		}

 		// Fetch the merge list for this child's target.
 		list, found := mergedChildren[key.Target]
 		if !found {
 			// First child with the given target?
 			mergedChildren[key.Target] = []Data{*childData}
 			continue
 		}
 		if list != nil {
 			mergedChildren[key.Target] = append(list, *childData)
 		}
 	}

 	merge := func(in []Data) *Data {
 		switch len(in) {
 		case 0:
 			return nil // nothing to merge.
 		case 1:
 			return &in[0] // merge of a single item results in that item
 		default:
 			return f(in)
 		}
 	}

 	// Might it possible to merge this node?
 	maybeMergeable := true

 	// The merged data, per target
 	mergedTargets := map[Target]Data{}

 	// Attempt to merge each of the target's data
 	for target, list := range mergedChildren {
 		if list != nil { // nil == unmergeable target
 			if data := merge(list); data != nil {
 				// Merge success!
 				mergedTargets[target] = *data
 				continue
 			}
 		}
 		maybeMergeable = false // Merge of this node is not possible
 	}

 	// Remove all children that have been merged
 	for key := range n.Children {
 		if _, merged := mergedTargets[key.Target]; merged {
 			delete(n.Children, key)
 		}
 	}

 	// Add wildcards for merged targets
 	for target, data := range mergedTargets {
 		data := data // Don't take address of iterator
 		n.getOrCreateChild(TreeNodeChildKey{"*", target}).Data = &data
 	}

 	// If any of the targets are unmergeable, then we cannot merge the node itself.
 	if !maybeMergeable {
 		return nil
 	}

 	// All targets were merged. Attempt to merge each of the targets.
 	data := make([]Data, 0, len(mergedTargets))
 	for _, d := range mergedTargets {
 		data = append(data, d)
 	}
 	return merge(data)
 }

 // print writes a textual representation of this node and its children to w.
 // prefix is used as the line prefix for each node, which is appended with
 // whitespace for each child node.
 func (n *TreeNode[Data]) print(w io.Writer, prefix string) {
 	fmt.Fprintf(w, "%v{\n", prefix)
 	fmt.Fprintf(w, "%v  query: '%v'\n", prefix, n.Query)
 	fmt.Fprintf(w, "%v  data:  '%v'\n", prefix, n.Data)
 	for _, key := range n.sortedChildKeys() {
 		n.Children[key].print(w, prefix+"  ")
 	}
 	fmt.Fprintf(w, "%v}\n", prefix)
 }

 // Format implements the io.Formatter interface.
 // See https://pkg.go.dev/fmt#Formatter
 func (n *TreeNode[Data]) Format(f fmt.State, verb rune) {
 	n.print(f, "")
 }

 // getOrCreateChild returns the child with the given key if it exists,
 // otherwise the child node is created and added to n and is returned.
 func (n *TreeNode[Data]) getOrCreateChild(key TreeNodeChildKey) *TreeNode[Data] {
 	if n.Children == nil {
 		child := &TreeNode[Data]{Query: n.Query.Append(key.Target, key.Name)}
 		n.Children = TreeNodeChildren[Data]{key: child}
 		return child
 	}
 	if child, ok := n.Children[key]; ok {
 		return child
 	}
 	child := &TreeNode[Data]{Query: n.Query.Append(key.Target, key.Name)}
 	n.Children[key] = child
 	return child
 }

 // QueryData is a pair of a Query and a generic Data type.
 // Used by NewTree for constructing a tree with entries.
 type QueryData[Data any] struct {
 	Query Query
 	Data  Data
 }

 // NewTree returns a new Tree populated with the given entries.
 // If entries returns duplicate queries, then ErrDuplicateData will be returned.
 func NewTree[Data any](entries ...QueryData[Data]) (Tree[Data], error) {
 	out := Tree[Data]{}
 	for _, qd := range entries {
 		if err := out.Add(qd.Query, qd.Data); err != nil {
 			return Tree[Data]{}, err
 		}
 	}
 	return out, nil
 }

 // Add adds a new data to the tree.
 // Returns ErrDuplicateData if the tree already contains a data for the given node at query
 func (t *Tree[Data]) Add(q Query, d Data) error {
 	node := &t.TreeNode
 	q.Walk(func(q Query, t Target, n string) error {
 		node = node.getOrCreateChild(TreeNodeChildKey{n, t})
 		return nil
 	})
 	if node.Data != nil {
 		return ErrDuplicateData{node.Query}
 	}
 	node.Data = &d
 	return nil
 }

 // Split adds a new data to the tree, clearing any ancestor node's data.
 // Returns ErrDuplicateData if the tree already contains a data for the given node at query
 func (t *Tree[Data]) Split(q Query, d Data) error {
 	node := &t.TreeNode
 	q.Walk(func(q Query, t Target, n string) error {
 		delete(node.Children, TreeNodeChildKey{Name: "*", Target: t})
 		node.Data = nil
 		node = node.getOrCreateChild(TreeNodeChildKey{n, t})
 		return nil
 	})
 	if node.Data != nil {
 		return ErrDuplicateData{node.Query}
 	}
 	node.Data = &d
 	return nil
 }

 // GetOrCreate returns existing, or adds a new data to the tree.
 func (t *Tree[Data]) GetOrCreate(q Query, create func() Data) *Data {
 	node := &t.TreeNode
 	q.Walk(func(q Query, t Target, n string) error {
 		node = node.getOrCreateChild(TreeNodeChildKey{n, t})
 		return nil
 	})
 	if node.Data == nil {
 		data := create()
 		node.Data = &data
 	}
 	return node.Data
 }

 // errStop is an error used to stop traversal of Query.Walk
 var errStop = errors.New("stop")

 // Get returns the closest existing tree node for the given query
 func (t *Tree[Data]) Get(q Query) *TreeNode[Data] {
 	node := &t.TreeNode
 	q.Walk(func(q Query, t Target, n string) error {
 		if n := node.Children[TreeNodeChildKey{n, t}]; n != nil {
 			node = n
 			return nil
 		}
 		return errStop
 	})
 	if node.Query == q {
 		return node
 	}
 	return nil
 }

 // Reduce reduces the tree using the Merger function f.
 // If the Merger function returns a non-nil Data value, then this will be used
 // to replace the non-leaf node with a new leaf node holding the returned Data.
 // This process recurses up to the tree root.
 func (t *Tree[Data]) Reduce(f Merger[Data]) {
 	for _, root := range t.TreeNode.Children {
 		root.merge(f)
 	}
 }

 // ReduceUnder reduces the sub-tree under the given query using the Merger
 // function f.
 // If the Merger function returns a non-nil Data value, then this will be used
 // to replace the non-leaf node with a new leaf node holding the returned Data.
 // This process recurses up to the node pointed at by the query to.
 func (t *Tree[Data]) ReduceUnder(to Query, f Merger[Data]) error {
 	node := &t.TreeNode
 	return to.Walk(func(q Query, t Target, n string) error {
 		if n == "*" {
 			node.merge(f)
 			return nil
 		}
 		child, ok := node.Children[TreeNodeChildKey{n, t}]
 		if !ok {
 			return ErrNoDataForQuery{q}
 		}
 		node = child
 		if q == to {
 			node.merge(f)
 		}
 		return nil
 	})
 }

 // glob calls f for every node under the given query.
 func (t *Tree[Data]) glob(fq Query, f func(f *TreeNode[Data]) error) error {
 	node := &t.TreeNode
 	return fq.Walk(func(q Query, t Target, n string) error {
 		if n == "*" {
 			// Wildcard reached.
 			// Glob the parent, but restrict to the wildcard target type.
 			for _, key := range node.sortedChildKeys() {
 				child := node.Children[key]
 				if child.Query.Target() == t {
 					if err := child.traverse(f); err != nil {
 						return err
 					}
 				}
 			}
 			return nil
 		}
 		switch t {
 		case Suite, Files, Tests:
 			child, ok := node.Children[TreeNodeChildKey{n, t}]
 			if !ok {
 				return ErrNoDataForQuery{q}
 			}
 			node = child
 		case Cases:
 			for _, key := range node.sortedChildKeys() {
 				child := node.Children[key]
 				if child.Query.Contains(fq) {
 					if err := f(child); err != nil {
 						return err
 					}
 				}
 			}
 			return nil
 		}
 		if q == fq {
 			return node.traverse(f)
 		}
 		return nil
 	})
 }

 // Replace replaces the sub-tree matching the query 'what' with the Data 'with'
 func (t *Tree[Data]) Replace(what Query, with Data) error {
 	node := &t.TreeNode
 	return what.Walk(func(q Query, t Target, n string) error {
 		childKey := TreeNodeChildKey{n, t}
 		if q == what {
 			for key, child := range node.Children {
 				// Use Query.Contains() to handle matching of Cases
 				// (which are not split into tree nodes)
 				if q.Contains(child.Query) {
 					delete(node.Children, key)
 				}
 			}
 			node = node.getOrCreateChild(childKey)
 			node.Data = &with
 		} else {
 			child, ok := node.Children[childKey]
 			if !ok {
 				return ErrNoDataForQuery{q}
 			}
 			node = child
 		}
 		return nil
 	})
 }

 // List returns the tree nodes flattened as a list of QueryData
 func (t *Tree[Data]) List() []QueryData[Data] {
 	out := []QueryData[Data]{}
 	t.traverse(func(n *TreeNode[Data]) error {
 		if n.Data != nil {
 			out = append(out, QueryData[Data]{n.Query, *n.Data})
 		}
 		return nil
 	})
 	return out
 }

 // Glob returns a list of QueryData's for every node that is under the given
 // query, which holds data.
 // Glob handles wildcards as well as non-wildcard queries:
 //   - A non-wildcard query will match the node itself, along with every node
 //     under the query. For example: 'a:b' will match every File and Test
 //     node under 'a:b', including 'a:b' itself.
 //   - A wildcard Query will include every node under the parent node with the
 //     matching Query target. For example: 'a:b:*' will match every Test
 //     node (excluding File nodes) under 'a:b', 'a:b' will not be included.
 func (t *Tree[Data]) Glob(q Query) ([]QueryData[Data], error) {
 	out := []QueryData[Data]{}
 	err := t.glob(q, func(n *TreeNode[Data]) error {
 		if n.Data != nil {
 			out = append(out, QueryData[Data]{n.Query, *n.Data})
 		}
 		return nil
 	})
 	if err != nil {
 		return nil, err
 	}
 	return out, nil
 }
	// Copyright 2022 The Dawn & Tint Authors
	//
	// Redistribution and use in source and binary forms, with or without
	// modification, are permitted provided that the following conditions are met:
	//
	// 1. Redistributions of source code must retain the above copyright notice, this
	// list of conditions and the following disclaimer.
	//
	// 2. Redistributions in binary form must reproduce the above copyright notice,
	// this list of conditions and the following disclaimer in the documentation
	// and/or other materials provided with the distribution.
	//
	// 3. Neither the name of the copyright holder nor the names of its
	// contributors may be used to endorse or promote products derived from
	// this software without specific prior written permission.
	//
	// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
	// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
	// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
	// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
	// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
	// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
	// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
	// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

	package query

	import (
	"errors"
	"fmt"
	"io"
	"sort"
	)

	// Tree holds a tree structure of Query to generic Data type.
	// Each separate suite, file, test of the query produces a separate tree node.
	// All cases of the query produce a single leaf tree node.
	type Tree[Data any] struct {
	TreeNode[Data]
	}

	// TreeNode is a single node in the Tree
	type TreeNode[Data any] struct {
	// The full query of the node
	Query Query
	// The data associated with this node. nil is used to represent no-data.
	Data *Data
	// Children of the node. Keyed by query.Target and name.
	Children TreeNodeChildren[Data]
	}

	// TreeNodeChildKey is the key used by TreeNode for the Children map
	type TreeNodeChildKey struct {
	// The child name. This is the string between `:` and `,` delimiters.
	// Note: that all test cases are held by a single TreeNode.
	Name string
	// The target type of the child. Examples:
	// Query \| Target of 'child'
	// -----------------+--------------------
	// parent:child \| Files
	// parent:x,child \| Files
	// parent:x:child \| Test
	// parent:x:y,child \| Test
	// parent:x:y:child \| Cases
	//
	// It's possible to have a directory and '.spec.ts' share the same name,
	// hence why we include the Target as part of the child key.
	Target Target
	}

	// TreeNodeChildren is a map of TreeNodeChildKey to TreeNode pointer.
	// Data is the data type held by a TreeNode.
	type TreeNodeChildren[Data any] map[TreeNodeChildKey]*TreeNode[Data]

	// sortedChildKeys returns all the sorted children keys.
	func (n *TreeNode[Data]) sortedChildKeys() []TreeNodeChildKey {
	keys := make([]TreeNodeChildKey, 0, len(n.Children))
	for key := range n.Children {
	keys = append(keys, key)
	}
	sort.Slice(keys, func(i, j int) bool {
	a, b := keys[i], keys[j]
	switch {
	case a.Name < b.Name:
	return true
	case a.Name > b.Name:
	return false
	case a.Target < b.Target:
	return true
	case a.Target > b.Target:
	return false
	}
	return false
	})
	return keys
	}

	// traverse performs a depth-first-search of the tree calling f for each visited
	// node, starting with n, then visiting each of children in sorted order
	// (pre-order traversal).
	func (n TreeNode[Data]) traverse(f func(n TreeNode[Data]) error) error {
	if err := f(n); err != nil {
	return err
	}
	for _, key := range n.sortedChildKeys() {
	if err := n.Children[key].traverse(f); err != nil {
	return err
	}
	}
	return nil
	}

	// Merger is a function used to merge the children nodes of a tree.
	// Merger is called with the Data of each child node. If the function returns a
	// non-nil Data pointer, then this is used as the merged result. If the function
	// returns nil, then the node will not be merged.
	type Merger[Data any] func([]Data) *Data

	// merge collapses tree nodes based on child node data, using the function f.
	// merge operates on the leaf nodes first, working its way towards the root of
	// the tree.
	// Returns the merged target data for this node, or nil if the node is not a
	// leaf and its children has non-uniform data.
	func (n TreeNode[Data]) merge(f Merger[Data]) Data {
	// If the node is a leaf, then simply return the node's data.
	if len(n.Children) == 0 {
	return n.Data
	}

	// Build a map of child target to merged child data.
	// A nil for the value indicates that one or more children could not merge.
	mergedChildren := map[Target][]Data{}
	for key, child := range n.Children {
	// Call merge() on the child. Even if we cannot merge this node, we want
	// to do this for all children so they can merge their sub-graphs.
	childData := child.merge(f)

	if childData == nil {
	// If merge() returned nil, then the data could not be merged.
	// Mark the entire target as unmergeable.
	mergedChildren[key.Target] = nil
	continue
	}

	// Fetch the merge list for this child's target.
	list, found := mergedChildren[key.Target]
	if !found {
	// First child with the given target?
	mergedChildren[key.Target] = []Data{*childData}
	continue
	}
	if list != nil {
	mergedChildren[key.Target] = append(list, *childData)
	}
	}

	merge := func(in []Data) *Data {
	switch len(in) {
	case 0:
	return nil // nothing to merge.
	case 1:
	return &in[0] // merge of a single item results in that item
	default:
	return f(in)
	}
	}

	// Might it possible to merge this node?
	maybeMergeable := true

	// The merged data, per target
	mergedTargets := map[Target]Data{}

	// Attempt to merge each of the target's data
	for target, list := range mergedChildren {
	if list != nil { // nil == unmergeable target
	if data := merge(list); data != nil {
	// Merge success!
	mergedTargets[target] = *data
	continue
	}
	}
	maybeMergeable = false // Merge of this node is not possible
	}

	// Remove all children that have been merged
	for key := range n.Children {
	if _, merged := mergedTargets[key.Target]; merged {
	delete(n.Children, key)
	}
	}

	// Add wildcards for merged targets
	for target, data := range mergedTargets {
	data := data // Don't take address of iterator
	n.getOrCreateChild(TreeNodeChildKey{"*", target}).Data = &data
	}

	// If any of the targets are unmergeable, then we cannot merge the node itself.
	if !maybeMergeable {
	return nil
	}

	// All targets were merged. Attempt to merge each of the targets.
	data := make([]Data, 0, len(mergedTargets))
	for _, d := range mergedTargets {
	data = append(data, d)
	}
	return merge(data)
	}

	// print writes a textual representation of this node and its children to w.
	// prefix is used as the line prefix for each node, which is appended with
	// whitespace for each child node.
	func (n *TreeNode[Data]) print(w io.Writer, prefix string) {
	fmt.Fprintf(w, "%v{\n", prefix)
	fmt.Fprintf(w, "%v query: '%v'\n", prefix, n.Query)
	fmt.Fprintf(w, "%v data: '%v'\n", prefix, n.Data)
	for _, key := range n.sortedChildKeys() {
	n.Children[key].print(w, prefix+" ")
	}
	fmt.Fprintf(w, "%v}\n", prefix)
	}

	// Format implements the io.Formatter interface.
	// See https://pkg.go.dev/fmt#Formatter
	func (n *TreeNode[Data]) Format(f fmt.State, verb rune) {
	n.print(f, "")
	}

	// getOrCreateChild returns the child with the given key if it exists,
	// otherwise the child node is created and added to n and is returned.
	func (n TreeNode[Data]) getOrCreateChild(key TreeNodeChildKey) TreeNode[Data] {
	if n.Children == nil {
	child := &TreeNode[Data]{Query: n.Query.Append(key.Target, key.Name)}
	n.Children = TreeNodeChildren[Data]{key: child}
	return child
	}
	if child, ok := n.Children[key]; ok {
	return child
	}
	child := &TreeNode[Data]{Query: n.Query.Append(key.Target, key.Name)}
	n.Children[key] = child
	return child
	}

	// QueryData is a pair of a Query and a generic Data type.
	// Used by NewTree for constructing a tree with entries.
	type QueryData[Data any] struct {
	Query Query
	Data Data
	}

	// NewTree returns a new Tree populated with the given entries.
	// If entries returns duplicate queries, then ErrDuplicateData will be returned.
	func NewTree[Data any](entries ...QueryData[Data]) (Tree[Data], error) {
	out := Tree[Data]{}
	for _, qd := range entries {
	if err := out.Add(qd.Query, qd.Data); err != nil {
	return Tree[Data]{}, err
	}
	}
	return out, nil
	}

	// Add adds a new data to the tree.
	// Returns ErrDuplicateData if the tree already contains a data for the given node at query
	func (t *Tree[Data]) Add(q Query, d Data) error {
	node := &t.TreeNode
	q.Walk(func(q Query, t Target, n string) error {
	node = node.getOrCreateChild(TreeNodeChildKey{n, t})
	return nil
	})
	if node.Data != nil {
	return ErrDuplicateData{node.Query}
	}
	node.Data = &d
	return nil
	}

	// Split adds a new data to the tree, clearing any ancestor node's data.
	// Returns ErrDuplicateData if the tree already contains a data for the given node at query
	func (t *Tree[Data]) Split(q Query, d Data) error {
	node := &t.TreeNode
	q.Walk(func(q Query, t Target, n string) error {
	delete(node.Children, TreeNodeChildKey{Name: "*", Target: t})
	node.Data = nil
	node = node.getOrCreateChild(TreeNodeChildKey{n, t})
	return nil
	})
	if node.Data != nil {
	return ErrDuplicateData{node.Query}
	}
	node.Data = &d
	return nil
	}

	// GetOrCreate returns existing, or adds a new data to the tree.
	func (t Tree[Data]) GetOrCreate(q Query, create func() Data) Data {
	node := &t.TreeNode
	q.Walk(func(q Query, t Target, n string) error {
	node = node.getOrCreateChild(TreeNodeChildKey{n, t})
	return nil
	})
	if node.Data == nil {
	data := create()
	node.Data = &data
	}
	return node.Data
	}

	// errStop is an error used to stop traversal of Query.Walk
	var errStop = errors.New("stop")

	// Get returns the closest existing tree node for the given query
	func (t Tree[Data]) Get(q Query) TreeNode[Data] {
	node := &t.TreeNode
	q.Walk(func(q Query, t Target, n string) error {
	if n := node.Children[TreeNodeChildKey{n, t}]; n != nil {
	node = n
	return nil
	}
	return errStop
	})
	if node.Query == q {
	return node
	}
	return nil
	}

	// Reduce reduces the tree using the Merger function f.
	// If the Merger function returns a non-nil Data value, then this will be used
	// to replace the non-leaf node with a new leaf node holding the returned Data.
	// This process recurses up to the tree root.
	func (t *Tree[Data]) Reduce(f Merger[Data]) {
	for _, root := range t.TreeNode.Children {
	root.merge(f)
	}
	}

	// ReduceUnder reduces the sub-tree under the given query using the Merger
	// function f.
	// If the Merger function returns a non-nil Data value, then this will be used
	// to replace the non-leaf node with a new leaf node holding the returned Data.
	// This process recurses up to the node pointed at by the query to.
	func (t *Tree[Data]) ReduceUnder(to Query, f Merger[Data]) error {
	node := &t.TreeNode
	return to.Walk(func(q Query, t Target, n string) error {
	if n == "*" {
	node.merge(f)
	return nil
	}
	child, ok := node.Children[TreeNodeChildKey{n, t}]
	if !ok {
	return ErrNoDataForQuery{q}
	}
	node = child
	if q == to {
	node.merge(f)
	}
	return nil
	})
	}

	// glob calls f for every node under the given query.
	func (t Tree[Data]) glob(fq Query, f func(f TreeNode[Data]) error) error {
	node := &t.TreeNode
	return fq.Walk(func(q Query, t Target, n string) error {
	if n == "*" {
	// Wildcard reached.
	// Glob the parent, but restrict to the wildcard target type.
	for _, key := range node.sortedChildKeys() {
	child := node.Children[key]
	if child.Query.Target() == t {
	if err := child.traverse(f); err != nil {
	return err
	}
	}
	}
	return nil
	}
	switch t {
	case Suite, Files, Tests:
	child, ok := node.Children[TreeNodeChildKey{n, t}]
	if !ok {
	return ErrNoDataForQuery{q}
	}
	node = child
	case Cases:
	for _, key := range node.sortedChildKeys() {
	child := node.Children[key]
	if child.Query.Contains(fq) {
	if err := f(child); err != nil {
	return err
	}
	}
	}
	return nil
	}
	if q == fq {
	return node.traverse(f)
	}
	return nil
	})
	}

	// Replace replaces the sub-tree matching the query 'what' with the Data 'with'
	func (t *Tree[Data]) Replace(what Query, with Data) error {
	node := &t.TreeNode
	return what.Walk(func(q Query, t Target, n string) error {
	childKey := TreeNodeChildKey{n, t}
	if q == what {
	for key, child := range node.Children {
	// Use Query.Contains() to handle matching of Cases
	// (which are not split into tree nodes)
	if q.Contains(child.Query) {
	delete(node.Children, key)
	}
	}
	node = node.getOrCreateChild(childKey)
	node.Data = &with
	} else {
	child, ok := node.Children[childKey]
	if !ok {
	return ErrNoDataForQuery{q}
	}
	node = child
	}
	return nil
	})
	}

	// List returns the tree nodes flattened as a list of QueryData
	func (t *Tree[Data]) List() []QueryData[Data] {
	out := []QueryData[Data]{}
	t.traverse(func(n *TreeNode[Data]) error {
	if n.Data != nil {
	out = append(out, QueryData[Data]{n.Query, *n.Data})
	}
	return nil
	})
	return out
	}

	// Glob returns a list of QueryData's for every node that is under the given
	// query, which holds data.
	// Glob handles wildcards as well as non-wildcard queries:
	// - A non-wildcard query will match the node itself, along with every node
	// under the query. For example: 'a:b' will match every File and Test
	// node under 'a:b', including 'a:b' itself.
	// - A wildcard Query will include every node under the parent node with the
	// matching Query target. For example: 'a:b:*' will match every Test
	// node (excluding File nodes) under 'a:b', 'a:b' will not be included.
	func (t *Tree[Data]) Glob(q Query) ([]QueryData[Data], error) {
	out := []QueryData[Data]{}
	err := t.glob(q, func(n *TreeNode[Data]) error {
	if n.Data != nil {
	out = append(out, QueryData[Data]{n.Query, *n.Data})
	}
	return nil
	})
	if err != nil {
	return nil, err
	}
	return out, nil
	}