tree.go

Documentation: sigs.k8s.io/kustomize/kyaml/kio

     1  // Copyright 2019 The Kubernetes Authors.
     2  // SPDX-License-Identifier: Apache-2.0
     3  
     4  package kio
     5  
     6  import (
     7  	"fmt"
     8  	"io"
     9  	"os"
    10  	"path/filepath"
    11  	"sort"
    12  	"strings"
    13  
    14  	"github.com/xlab/treeprint"
    15  	"sigs.k8s.io/kustomize/kyaml/kio/kioutil"
    16  	"sigs.k8s.io/kustomize/kyaml/yaml"
    17  )
    18  
    19  type TreeStructure string
    20  
    21  const (
    22  	// TreeStructurePackage configures TreeWriter to generate the tree structure off of the
    23  	// Resources packages.
    24  	TreeStructurePackage TreeStructure = "directory"
    25  
    26  	// TreeStructureOwners configures TreeWriter to generate the tree structure off of the
    27  	// Resource owners.
    28  	TreeStructureGraph TreeStructure = "owners"
    29  )
    30  
    31  var GraphStructures = []string{string(TreeStructureGraph), string(TreeStructurePackage)}
    32  
    33  // TreeWriter prints the package structured as a tree.
    34  // TODO(pwittrock): test this package better.  it is lower-risk since it is only
    35  //   used for printing rather than updating or editing.
    36  type TreeWriter struct {
    37  	Writer          io.Writer
    38  	Root            string
    39  	Fields          []TreeWriterField
    40  	Structure       TreeStructure
    41  	OpenAPIFileName string
    42  }
    43  
    44  // TreeWriterField configures a Resource field to be included in the tree
    45  type TreeWriterField struct {
    46  	yaml.PathMatcher
    47  	Name    string
    48  	SubName string
    49  }
    50  
    51  func (p TreeWriter) packageStructure(nodes []*yaml.RNode) error {
    52  	for i := range nodes {
    53  		if err := kioutil.CopyLegacyAnnotations(nodes[i]); err != nil {
    54  			return err
    55  		}
    56  	}
    57  	indexByPackage := p.index(nodes)
    58  
    59  	// create the new tree
    60  	tree := treeprint.New()
    61  	tree.SetValue(p.Root)
    62  
    63  	// add each package to the tree
    64  	treeIndex := map[string]treeprint.Tree{}
    65  	keys := p.sort(indexByPackage)
    66  	for _, pkg := range keys {
    67  		// create a branch for this package -- search for the parent package and create
    68  		// the branch under it -- requires that the keys are sorted
    69  		branch := tree
    70  		for parent, subTree := range treeIndex {
    71  			if strings.HasPrefix(pkg, parent) {
    72  				// found a package whose path is a prefix to our own, use this
    73  				// package if a closer one isn't found
    74  				branch = subTree
    75  				// don't break, continue searching for more closely related ancestors
    76  			}
    77  		}
    78  
    79  		// create a new branch for the package
    80  		createOk := pkg != "." // special edge case logic for tree on current working dir
    81  		if createOk {
    82  			branch = branch.AddBranch(branchName(p.Root, pkg, p.OpenAPIFileName))
    83  		}
    84  
    85  		// cache the branch for this package
    86  		treeIndex[pkg] = branch
    87  
    88  		// print each resource in the package
    89  		for i := range indexByPackage[pkg] {
    90  			var err error
    91  			if _, err = p.doResource(indexByPackage[pkg][i], "", branch); err != nil {
    92  				return err
    93  			}
    94  		}
    95  	}
    96  
    97  	_, err := io.WriteString(p.Writer, tree.String())
    98  	return err
    99  }
   100  
   101  // branchName takes the root directory and relative path to the directory
   102  // and returns the branch name
   103  func branchName(root, dirRelPath, openAPIFileName string) string {
   104  	name := filepath.Base(dirRelPath)
   105  	_, err := os.Stat(filepath.Join(root, dirRelPath, openAPIFileName))
   106  	if !os.IsNotExist(err) {
   107  		// add Pkg: prefix indicating that it is a separate package as it has
   108  		// openAPIFile
   109  		return fmt.Sprintf("Pkg: %s", name)
   110  	}
   111  	return name
   112  }
   113  
   114  // Write writes the ascii tree to p.Writer
   115  func (p TreeWriter) Write(nodes []*yaml.RNode) error {
   116  	switch p.Structure {
   117  	case TreeStructurePackage:
   118  		return p.packageStructure(nodes)
   119  	case TreeStructureGraph:
   120  		return p.graphStructure(nodes)
   121  	}
   122  
   123  	// If any resource has an owner reference, default to the graph structure. Otherwise, use package structure.
   124  	for _, node := range nodes {
   125  		if owners, _ := node.Pipe(yaml.Lookup("metadata", "ownerReferences")); owners != nil {
   126  			return p.graphStructure(nodes)
   127  		}
   128  	}
   129  	return p.packageStructure(nodes)
   130  }
   131  
   132  // node wraps a tree node, and any children nodes
   133  type node struct {
   134  	p TreeWriter
   135  	*yaml.RNode
   136  	children []*node
   137  }
   138  
   139  func (a node) Len() int      { return len(a.children) }
   140  func (a node) Swap(i, j int) { a.children[i], a.children[j] = a.children[j], a.children[i] }
   141  func (a node) Less(i, j int) bool {
   142  	return compareNodes(a.children[i].RNode, a.children[j].RNode)
   143  }
   144  
   145  // Tree adds this node to the root
   146  func (a node) Tree(root treeprint.Tree) error {
   147  	sort.Sort(a)
   148  	branch := root
   149  	var err error
   150  
   151  	// generate a node for the Resource
   152  	if a.RNode != nil {
   153  		branch, err = a.p.doResource(a.RNode, "Resource", root)
   154  		if err != nil {
   155  			return err
   156  		}
   157  	}
   158  
   159  	// attach children to the branch
   160  	for _, n := range a.children {
   161  		if err := n.Tree(branch); err != nil {
   162  			return err
   163  		}
   164  	}
   165  	return nil
   166  }
   167  
   168  // graphStructure writes the tree using owners for structure
   169  func (p TreeWriter) graphStructure(nodes []*yaml.RNode) error {
   170  	resourceToOwner := map[string]*node{}
   171  	root := &node{}
   172  	// index each of the nodes by their owner
   173  	for _, n := range nodes {
   174  		ownerVal, err := ownerToString(n)
   175  		if err != nil {
   176  			return err
   177  		}
   178  		var owner *node
   179  		if ownerVal == "" {
   180  			// no owner -- attach to the root
   181  			owner = root
   182  		} else {
   183  			// owner found -- attach to the owner
   184  			var found bool
   185  			owner, found = resourceToOwner[ownerVal]
   186  			if !found {
   187  				// initialize the owner if not found
   188  				resourceToOwner[ownerVal] = &node{p: p}
   189  				owner = resourceToOwner[ownerVal]
   190  			}
   191  		}
   192  
   193  		nodeVal, err := nodeToString(n)
   194  		if err != nil {
   195  			return err
   196  		}
   197  		val, found := resourceToOwner[nodeVal]
   198  		if !found {
   199  			// initialize the node if not found -- may have already been initialized if it
   200  			// is the owner of another node
   201  			resourceToOwner[nodeVal] = &node{p: p}
   202  			val = resourceToOwner[nodeVal]
   203  		}
   204  		val.RNode = n
   205  		owner.children = append(owner.children, val)
   206  	}
   207  
   208  	for k, v := range resourceToOwner {
   209  		if v.RNode == nil {
   210  			return fmt.Errorf(
   211  				"owner '%s' not found in input, but found as an owner of input objects", k)
   212  		}
   213  	}
   214  
   215  	// print the tree
   216  	tree := treeprint.New()
   217  	if err := root.Tree(tree); err != nil {
   218  		return err
   219  	}
   220  
   221  	_, err := io.WriteString(p.Writer, tree.String())
   222  	return err
   223  }
   224  
   225  // nodeToString generates a string to identify the node -- matches ownerToString format
   226  func nodeToString(node *yaml.RNode) (string, error) {
   227  	meta, err := node.GetMeta()
   228  	if err != nil {
   229  		return "", err
   230  	}
   231  
   232  	return fmt.Sprintf("%s %s/%s", meta.Kind, meta.Namespace, meta.Name), nil
   233  }
   234  
   235  // ownerToString generate a string to identify the owner -- matches nodeToString format
   236  func ownerToString(node *yaml.RNode) (string, error) {
   237  	meta, err := node.GetMeta()
   238  	if err != nil {
   239  		return "", err
   240  	}
   241  	namespace := meta.Namespace
   242  
   243  	owners, err := node.Pipe(yaml.Lookup("metadata", "ownerReferences"))
   244  	if err != nil {
   245  		return "", err
   246  	}
   247  	if owners == nil {
   248  		return "", nil
   249  	}
   250  
   251  	elements, err := owners.Elements()
   252  	if err != nil {
   253  		return "", err
   254  	}
   255  	if len(elements) == 0 {
   256  		return "", err
   257  	}
   258  	owner := elements[0]
   259  	var kind, name string
   260  
   261  	if value := owner.Field("kind"); !value.IsNilOrEmpty() {
   262  		kind = value.Value.YNode().Value
   263  	}
   264  	if value := owner.Field("name"); !value.IsNilOrEmpty() {
   265  		name = value.Value.YNode().Value
   266  	}
   267  
   268  	return fmt.Sprintf("%s %s/%s", kind, namespace, name), nil
   269  }
   270  
   271  // index indexes the Resources by their package
   272  func (p TreeWriter) index(nodes []*yaml.RNode) map[string][]*yaml.RNode {
   273  	// index the ResourceNodes by package
   274  	indexByPackage := map[string][]*yaml.RNode{}
   275  	for i := range nodes {
   276  		meta, err := nodes[i].GetMeta()
   277  		if err != nil || meta.Kind == "" {
   278  			// not a resource
   279  			continue
   280  		}
   281  		pkg := filepath.Dir(meta.Annotations[kioutil.PathAnnotation])
   282  		indexByPackage[pkg] = append(indexByPackage[pkg], nodes[i])
   283  	}
   284  	return indexByPackage
   285  }
   286  
   287  func compareNodes(i, j *yaml.RNode) bool {
   288  	metai, _ := i.GetMeta()
   289  	metaj, _ := j.GetMeta()
   290  	pi := metai.Annotations[kioutil.PathAnnotation]
   291  	pj := metaj.Annotations[kioutil.PathAnnotation]
   292  
   293  	// compare file names
   294  	if filepath.Base(pi) != filepath.Base(pj) {
   295  		return filepath.Base(pi) < filepath.Base(pj)
   296  	}
   297  
   298  	// compare namespace
   299  	if metai.Namespace != metaj.Namespace {
   300  		return metai.Namespace < metaj.Namespace
   301  	}
   302  
   303  	// compare name
   304  	if metai.Name != metaj.Name {
   305  		return metai.Name < metaj.Name
   306  	}
   307  
   308  	// compare kind
   309  	if metai.Kind != metaj.Kind {
   310  		return metai.Kind < metaj.Kind
   311  	}
   312  
   313  	// compare apiVersion
   314  	if metai.APIVersion != metaj.APIVersion {
   315  		return metai.APIVersion < metaj.APIVersion
   316  	}
   317  	return true
   318  }
   319  
   320  // sort sorts the Resources in the index in display order and returns the ordered
   321  // keys for the index
   322  //
   323  // Packages are sorted by package name
   324  // Resources within a package are sorted by: [filename, namespace, name, kind, apiVersion]
   325  func (p TreeWriter) sort(indexByPackage map[string][]*yaml.RNode) []string {
   326  	var keys []string
   327  	for k := range indexByPackage {
   328  		pkgNodes := indexByPackage[k]
   329  		sort.Slice(pkgNodes, func(i, j int) bool { return compareNodes(pkgNodes[i], pkgNodes[j]) })
   330  		keys = append(keys, k)
   331  	}
   332  
   333  	// return the package names sorted lexicographically
   334  	sort.Strings(keys)
   335  	return keys
   336  }
   337  
   338  func (p TreeWriter) doResource(leaf *yaml.RNode, metaString string, branch treeprint.Tree) (treeprint.Tree, error) {
   339  	meta, _ := leaf.GetMeta()
   340  	if metaString == "" {
   341  		path := meta.Annotations[kioutil.PathAnnotation]
   342  		path = filepath.Base(path)
   343  		metaString = path
   344  	}
   345  
   346  	value := fmt.Sprintf("%s %s", meta.Kind, meta.Name)
   347  	if len(meta.Namespace) > 0 {
   348  		value = fmt.Sprintf("%s %s/%s", meta.Kind, meta.Namespace, meta.Name)
   349  	}
   350  
   351  	fields, err := p.getFields(leaf)
   352  	if err != nil {
   353  		return nil, err
   354  	}
   355  
   356  	n := branch.AddMetaBranch(metaString, value)
   357  	for i := range fields {
   358  		field := fields[i]
   359  
   360  		// do leaf node
   361  		if len(field.matchingElementsAndFields) == 0 {
   362  			n.AddNode(fmt.Sprintf("%s: %s", field.name, field.value))
   363  			continue
   364  		}
   365  
   366  		// do nested nodes
   367  		b := n.AddBranch(field.name)
   368  		for j := range field.matchingElementsAndFields {
   369  			elem := field.matchingElementsAndFields[j]
   370  			b := b.AddBranch(elem.name)
   371  			for k := range elem.matchingElementsAndFields {
   372  				field := elem.matchingElementsAndFields[k]
   373  				b.AddNode(fmt.Sprintf("%s: %s", field.name, field.value))
   374  			}
   375  		}
   376  	}
   377  
   378  	return n, nil
   379  }
   380  
   381  // getFields looks up p.Fields from leaf and structures them into treeFields.
   382  // TODO(pwittrock): simplify this function
   383  func (p TreeWriter) getFields(leaf *yaml.RNode) (treeFields, error) {
   384  	fieldsByName := map[string]*treeField{}
   385  
   386  	// index nested and non-nested fields
   387  	for i := range p.Fields {
   388  		f := p.Fields[i]
   389  		seq, err := leaf.Pipe(&f)
   390  		if err != nil {
   391  			return nil, err
   392  		}
   393  		if seq == nil {
   394  			continue
   395  		}
   396  
   397  		if fieldsByName[f.Name] == nil {
   398  			fieldsByName[f.Name] = &treeField{name: f.Name}
   399  		}
   400  
   401  		// non-nested field -- add directly to the treeFields list
   402  		if f.SubName == "" {
   403  			// non-nested field -- only 1 element
   404  			val, err := yaml.String(seq.Content()[0], yaml.Trim, yaml.Flow)
   405  			if err != nil {
   406  				return nil, err
   407  			}
   408  			fieldsByName[f.Name].value = val
   409  			continue
   410  		}
   411  
   412  		// nested-field -- create a parent elem, and index by the 'match' value
   413  		if fieldsByName[f.Name].subFieldByMatch == nil {
   414  			fieldsByName[f.Name].subFieldByMatch = map[string]treeFields{}
   415  		}
   416  		index := fieldsByName[f.Name].subFieldByMatch
   417  		for j := range seq.Content() {
   418  			elem := seq.Content()[j]
   419  			matches := f.Matches[elem]
   420  			str, err := yaml.String(elem, yaml.Trim, yaml.Flow)
   421  			if err != nil {
   422  				return nil, err
   423  			}
   424  
   425  			// map the field by the name of the element
   426  			// index the subfields by the matching element so we can put all the fields for the
   427  			// same element under the same branch
   428  			matchKey := strings.Join(matches, "/")
   429  			index[matchKey] = append(index[matchKey], &treeField{name: f.SubName, value: str})
   430  		}
   431  	}
   432  
   433  	// iterate over collection of all queried fields in the Resource
   434  	for _, field := range fieldsByName {
   435  		// iterate over collection of elements under the field -- indexed by element name
   436  		for match, subFields := range field.subFieldByMatch {
   437  			// create a new element for this collection of fields
   438  			// note: we will convert name to an index later, but keep the match for sorting
   439  			elem := &treeField{name: match}
   440  			field.matchingElementsAndFields = append(field.matchingElementsAndFields, elem)
   441  
   442  			// iterate over collection of queried fields for the element
   443  			for i := range subFields {
   444  				// add to the list of fields for this element
   445  				elem.matchingElementsAndFields = append(elem.matchingElementsAndFields, subFields[i])
   446  			}
   447  		}
   448  		// clear this cached data
   449  		field.subFieldByMatch = nil
   450  	}
   451  
   452  	// put the fields in a list so they are ordered
   453  	fieldList := treeFields{}
   454  	for _, v := range fieldsByName {
   455  		fieldList = append(fieldList, v)
   456  	}
   457  
   458  	// sort the fields
   459  	sort.Sort(fieldList)
   460  	for i := range fieldList {
   461  		field := fieldList[i]
   462  		// sort the elements under this field
   463  		sort.Sort(field.matchingElementsAndFields)
   464  
   465  		for i := range field.matchingElementsAndFields {
   466  			element := field.matchingElementsAndFields[i]
   467  			// sort the elements under a list field by their name
   468  			sort.Sort(element.matchingElementsAndFields)
   469  			// set the name of the element to its index
   470  			element.name = fmt.Sprintf("%d", i)
   471  		}
   472  	}
   473  
   474  	return fieldList, nil
   475  }
   476  
   477  // treeField wraps a field node
   478  type treeField struct {
   479  	// name is the name of the node
   480  	name string
   481  
   482  	// value is the value of the node -- may be empty
   483  	value string
   484  
   485  	// matchingElementsAndFields is a slice of fields that go under this as a branch
   486  	matchingElementsAndFields treeFields
   487  
   488  	// subFieldByMatch caches matchingElementsAndFields indexed by the name of the matching elem
   489  	subFieldByMatch map[string]treeFields
   490  }
   491  
   492  // treeFields wraps a slice of treeField so they can be sorted
   493  type treeFields []*treeField
   494  
   495  func (nodes treeFields) Len() int { return len(nodes) }
   496  
   497  func (nodes treeFields) Less(i, j int) bool {
   498  	iIndex, iFound := yaml.FieldOrder[nodes[i].name]
   499  	jIndex, jFound := yaml.FieldOrder[nodes[j].name]
   500  	if iFound && jFound {
   501  		return iIndex < jIndex
   502  	}
   503  	if iFound {
   504  		return true
   505  	}
   506  	if jFound {
   507  		return false
   508  	}
   509  
   510  	if nodes[i].name != nodes[j].name {
   511  		return nodes[i].name < nodes[j].name
   512  	}
   513  	if nodes[i].value != nodes[j].value {
   514  		return nodes[i].value < nodes[j].value
   515  	}
   516  	return false
   517  }
   518  
   519  func (nodes treeFields) Swap(i, j int) { nodes[i], nodes[j] = nodes[j], nodes[i] }
   520
View as plain text