tree.go

Documentation: github.com/linkerd/linkerd2/pkg/tree

     1  package tree
     2  
     3  import (
     4  	"fmt"
     5  
     6  	"sigs.k8s.io/yaml"
     7  )
     8  
     9  // Tree is a structured representation of a string keyed tree document such as
    10  // yaml or json.
    11  type Tree map[string]interface{}
    12  
    13  // ToYAML returns a yaml serialization of the Tree.
    14  func (t Tree) ToYAML() (string, error) {
    15  	bytes, err := yaml.Marshal(t)
    16  	if err != nil {
    17  		return "", err
    18  	}
    19  	return string(bytes), nil
    20  }
    21  
    22  // String returns a yaml representation of the Tree or an error string if
    23  // serialization fails.
    24  func (t Tree) String() string {
    25  	s, err := t.ToYAML()
    26  	if err != nil {
    27  		return err.Error()
    28  	}
    29  	return s
    30  }
    31  
    32  // GetString returns the string value at the given path
    33  func (t Tree) GetString(path ...string) (string, error) {
    34  	if len(path) == 1 {
    35  		// check if exists
    36  		if val, ok := t[path[0]]; ok {
    37  			// check if string
    38  			if s, ok := val.(string); ok {
    39  				return s, nil
    40  			}
    41  			return "", fmt.Errorf("expected string at node %s but found a different type", path[0])
    42  		}
    43  		return "", fmt.Errorf("could not find node %s", path[0])
    44  	}
    45  
    46  	// check if exists
    47  	if val, ok := t[path[0]]; ok {
    48  		// Check if its a Tree
    49  		if valTree, ok := val.(Tree); ok {
    50  			return valTree.GetString(path[1:]...)
    51  		}
    52  		return "", fmt.Errorf("expected Tree at node %s but found a different type", path[0])
    53  	}
    54  	return "", fmt.Errorf("could not find node %s", path[0])
    55  }
    56  
    57  // Diff returns the subset of other where its values differ from t.
    58  func (t Tree) Diff(other Tree) (Tree, error) {
    59  	diff := make(Tree)
    60  	for k, v := range other {
    61  		tv, ok := t[k]
    62  		if ok {
    63  			tvt, tvIsTree := tv.(Tree)
    64  			vt, vIsTree := v.(Tree)
    65  			if tvIsTree && vIsTree {
    66  				subdiff, err := tvt.Diff(vt)
    67  				if err != nil {
    68  					return nil, err
    69  				}
    70  				diff[k] = subdiff
    71  			} else if !tvIsTree && !vIsTree {
    72  				if !equal(v, tv) {
    73  					diff[k] = v
    74  				}
    75  			} else {
    76  				diff[k] = v
    77  			}
    78  		} else {
    79  			diff[k] = v
    80  		}
    81  	}
    82  	diff.Prune()
    83  	return diff, nil
    84  }
    85  
    86  func equal(x interface{}, y interface{}) bool {
    87  	xt, xIsTree := x.(Tree)
    88  	yt, yIsTree := y.(Tree)
    89  	if xIsTree && yIsTree {
    90  		if len(xt) != len(yt) {
    91  			return false
    92  		}
    93  		for k := range xt {
    94  			if !equal(xt[k], yt[k]) {
    95  				return false
    96  			}
    97  		}
    98  		return true
    99  	}
   100  	if xIsTree || yIsTree {
   101  		return false
   102  	}
   103  	xs, xIsSlice := x.([]interface{})
   104  	ys, yIsSlice := x.([]interface{})
   105  	if xIsSlice && yIsSlice {
   106  		if len(xs) != len(ys) {
   107  			return false
   108  		}
   109  		for i := range xs {
   110  			if !equal(xs[i], ys[i]) {
   111  				return false
   112  			}
   113  		}
   114  		return true
   115  	}
   116  	if xIsSlice || yIsSlice {
   117  		return false
   118  	}
   119  	return x == y
   120  }
   121  
   122  // Prune removes all empty subtrees.  A subtree is considered empty if it does
   123  // not contain any leaf values.
   124  func (t Tree) Prune() {
   125  	for k, v := range t {
   126  		child, isTree := v.(Tree)
   127  		if isTree {
   128  			if child.Empty() {
   129  				delete(t, k)
   130  			} else {
   131  				child.Prune()
   132  			}
   133  		}
   134  	}
   135  }
   136  
   137  // Empty returns true iff the Tree contains no leaf values.
   138  func (t Tree) Empty() bool {
   139  	for _, v := range t {
   140  		child, isTree := v.(Tree)
   141  		if !isTree {
   142  			return false
   143  		}
   144  		if !child.Empty() {
   145  			return false
   146  		}
   147  	}
   148  	return true
   149  }
   150  
   151  // MarshalToTree marshals obj to yaml and then parses the resulting yaml as
   152  // a Tree.
   153  func MarshalToTree(obj interface{}) (Tree, error) {
   154  	bytes, err := yaml.Marshal(obj)
   155  	if err != nil {
   156  		return nil, err
   157  	}
   158  	return BytesToTree(bytes)
   159  }
   160  
   161  // BytesToTree converts given bytes into a tree by Unmarshaling
   162  func BytesToTree(bytes []byte) (Tree, error) {
   163  	tree := make(Tree)
   164  	err := yaml.Unmarshal(bytes, &tree)
   165  	if err != nil {
   166  		return nil, err
   167  	}
   168  	tree.coerceToTree()
   169  	return tree, nil
   170  }
   171  
   172  // Diff marshals two objects into their yaml representations and then performs
   173  // a diff on those Trees.  It returns a Tree which represents all of the fields
   174  // in y which differ from x.
   175  func Diff(x interface{}, y interface{}) (Tree, error) {
   176  	xTree, err := MarshalToTree(x)
   177  	if err != nil {
   178  		return nil, err
   179  	}
   180  	yTree, err := MarshalToTree(y)
   181  	if err != nil {
   182  		return nil, err
   183  	}
   184  	return xTree.Diff(yTree)
   185  }
   186  
   187  // coerceTreeValue accepts a value and returns a value where all child values
   188  // have been coerced to a Tree where such a coercion is possible
   189  func coerceTreeValue(v interface{}) interface{} {
   190  	if vt, ok := v.(Tree); ok {
   191  		vt.coerceToTree()
   192  	} else if vm, ok := v.(map[string]interface{}); ok {
   193  		tree := Tree(vm)
   194  		tree.coerceToTree()
   195  		return tree
   196  	} else if va, ok := v.([]interface{}); ok {
   197  		for i, v := range va {
   198  			va[i] = coerceTreeValue(v)
   199  		}
   200  	}
   201  	return v
   202  }
   203  
   204  // coerceToTree recursively casts all instances of map[string]interface{} into
   205  // Tree within this Tree.  When a tree document is unmarshaled, the subtrees
   206  // will typically be unmarshaled as map[string]interface{} values.  We cast
   207  // each of these into the Tree newtype so that the Tree type is used uniformly
   208  // throughout the tree. Will additionally recurse through arrays
   209  func (t Tree) coerceToTree() {
   210  	for k, v := range t {
   211  		t[k] = coerceTreeValue(v)
   212  	}
   213  }
   214
View as plain text