sorter.go

Documentation: k8s.io/kubectl/pkg/cmd/get

     1  /*
     2  Copyright 2014 The Kubernetes Authors.
     3  
     4  Licensed under the Apache License, Version 2.0 (the "License");
     5  you may not use this file except in compliance with the License.
     6  You may obtain a copy of the License at
     7  
     8      http://www.apache.org/licenses/LICENSE-2.0
     9  
    10  Unless required by applicable law or agreed to in writing, software
    11  distributed under the License is distributed on an "AS IS" BASIS,
    12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13  See the License for the specific language governing permissions and
    14  limitations under the License.
    15  */
    16  
    17  package get
    18  
    19  import (
    20  	"fmt"
    21  	"io"
    22  	"reflect"
    23  	"sort"
    24  
    25  	"k8s.io/klog/v2"
    26  
    27  	corev1 "k8s.io/api/core/v1"
    28  	"k8s.io/apimachinery/pkg/api/meta"
    29  	"k8s.io/apimachinery/pkg/api/resource"
    30  	metav1 "k8s.io/apimachinery/pkg/apis/meta/v1"
    31  	"k8s.io/apimachinery/pkg/apis/meta/v1/unstructured"
    32  	"k8s.io/apimachinery/pkg/runtime"
    33  	"k8s.io/cli-runtime/pkg/printers"
    34  	"k8s.io/client-go/util/jsonpath"
    35  
    36  	"github.com/fvbommel/sortorder"
    37  )
    38  
    39  // SortingPrinter sorts list types before delegating to another printer.
    40  // Non-list types are simply passed through
    41  type SortingPrinter struct {
    42  	SortField string
    43  	Delegate  printers.ResourcePrinter
    44  	Decoder   runtime.Decoder
    45  }
    46  
    47  func (s *SortingPrinter) PrintObj(obj runtime.Object, out io.Writer) error {
    48  	if table, isTable := obj.(*metav1.Table); isTable && len(table.Rows) > 1 {
    49  		parsedField, err := RelaxedJSONPathExpression(s.SortField)
    50  		if err != nil {
    51  			parsedField = s.SortField
    52  		}
    53  
    54  		if sorter, err := NewTableSorter(table, parsedField); err != nil {
    55  			return err
    56  		} else if err := sorter.Sort(); err != nil {
    57  			return err
    58  		}
    59  		return s.Delegate.PrintObj(table, out)
    60  	}
    61  
    62  	if meta.IsListType(obj) {
    63  		if err := s.sortObj(obj); err != nil {
    64  			return err
    65  		}
    66  		return s.Delegate.PrintObj(obj, out)
    67  	}
    68  
    69  	return s.Delegate.PrintObj(obj, out)
    70  }
    71  
    72  func (s *SortingPrinter) sortObj(obj runtime.Object) error {
    73  	objs, err := meta.ExtractList(obj)
    74  	if err != nil {
    75  		return err
    76  	}
    77  	if len(objs) == 0 {
    78  		return nil
    79  	}
    80  
    81  	sorter, err := SortObjects(s.Decoder, objs, s.SortField)
    82  	if err != nil {
    83  		return err
    84  	}
    85  
    86  	switch list := obj.(type) {
    87  	case *corev1.List:
    88  		outputList := make([]runtime.RawExtension, len(objs))
    89  		for ix := range objs {
    90  			outputList[ix] = list.Items[sorter.OriginalPosition(ix)]
    91  		}
    92  		list.Items = outputList
    93  		return nil
    94  	}
    95  	return meta.SetList(obj, objs)
    96  }
    97  
    98  // SortObjects sorts the runtime.Object based on fieldInput and returns RuntimeSort that implements
    99  // the golang sort interface
   100  func SortObjects(decoder runtime.Decoder, objs []runtime.Object, fieldInput string) (*RuntimeSort, error) {
   101  	for ix := range objs {
   102  		item := objs[ix]
   103  		switch u := item.(type) {
   104  		case *runtime.Unknown:
   105  			var err error
   106  			// decode runtime.Unknown to runtime.Unstructured for sorting.
   107  			// we don't actually want the internal versions of known types.
   108  			if objs[ix], _, err = decoder.Decode(u.Raw, nil, &unstructured.Unstructured{}); err != nil {
   109  				return nil, err
   110  			}
   111  		}
   112  	}
   113  
   114  	field, err := RelaxedJSONPathExpression(fieldInput)
   115  	if err != nil {
   116  		return nil, err
   117  	}
   118  
   119  	parser := jsonpath.New("sorting").AllowMissingKeys(true)
   120  	if err := parser.Parse(field); err != nil {
   121  		return nil, err
   122  	}
   123  
   124  	// We don't do any model validation here, so we traverse all objects to be sorted
   125  	// and, if the field is valid to at least one of them, we consider it to be a
   126  	// valid field; otherwise error out.
   127  	// Note that this requires empty fields to be considered later, when sorting.
   128  	var fieldFoundOnce bool
   129  	for _, obj := range objs {
   130  		values, err := findJSONPathResults(parser, obj)
   131  		if err != nil {
   132  			return nil, err
   133  		}
   134  		if len(values) > 0 && len(values[0]) > 0 {
   135  			fieldFoundOnce = true
   136  			break
   137  		}
   138  	}
   139  	if !fieldFoundOnce {
   140  		return nil, fmt.Errorf("couldn't find any field with path %q in the list of objects", field)
   141  	}
   142  
   143  	sorter := NewRuntimeSort(field, objs)
   144  	sort.Sort(sorter)
   145  	return sorter, nil
   146  }
   147  
   148  // RuntimeSort is an implementation of the golang sort interface that knows how to sort
   149  // lists of runtime.Object
   150  type RuntimeSort struct {
   151  	field        string
   152  	objs         []runtime.Object
   153  	origPosition []int
   154  }
   155  
   156  // NewRuntimeSort creates a new RuntimeSort struct that implements golang sort interface
   157  func NewRuntimeSort(field string, objs []runtime.Object) *RuntimeSort {
   158  	sorter := &RuntimeSort{field: field, objs: objs, origPosition: make([]int, len(objs))}
   159  	for ix := range objs {
   160  		sorter.origPosition[ix] = ix
   161  	}
   162  	return sorter
   163  }
   164  
   165  func (r *RuntimeSort) Len() int {
   166  	return len(r.objs)
   167  }
   168  
   169  func (r *RuntimeSort) Swap(i, j int) {
   170  	r.objs[i], r.objs[j] = r.objs[j], r.objs[i]
   171  	r.origPosition[i], r.origPosition[j] = r.origPosition[j], r.origPosition[i]
   172  }
   173  
   174  func isLess(i, j reflect.Value) (bool, error) {
   175  	switch i.Kind() {
   176  	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
   177  		return i.Int() < j.Int(), nil
   178  	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64:
   179  		return i.Uint() < j.Uint(), nil
   180  	case reflect.Float32, reflect.Float64:
   181  		return i.Float() < j.Float(), nil
   182  	case reflect.String:
   183  		return sortorder.NaturalLess(i.String(), j.String()), nil
   184  	case reflect.Pointer:
   185  		return isLess(i.Elem(), j.Elem())
   186  	case reflect.Struct:
   187  		// sort metav1.Time
   188  		in := i.Interface()
   189  		if t, ok := in.(metav1.Time); ok {
   190  			time := j.Interface().(metav1.Time)
   191  			return t.Before(&time), nil
   192  		}
   193  		// sort resource.Quantity
   194  		if iQuantity, ok := in.(resource.Quantity); ok {
   195  			jQuantity := j.Interface().(resource.Quantity)
   196  			return iQuantity.Cmp(jQuantity) < 0, nil
   197  		}
   198  		// fallback to the fields comparison
   199  		for idx := 0; idx < i.NumField(); idx++ {
   200  			less, err := isLess(i.Field(idx), j.Field(idx))
   201  			if err != nil || !less {
   202  				return less, err
   203  			}
   204  		}
   205  		return true, nil
   206  	case reflect.Array, reflect.Slice:
   207  		// note: the length of i and j may be different
   208  		for idx := 0; idx < min(i.Len(), j.Len()); idx++ {
   209  			less, err := isLess(i.Index(idx), j.Index(idx))
   210  			if err != nil || !less {
   211  				return less, err
   212  			}
   213  		}
   214  		return true, nil
   215  	case reflect.Interface:
   216  		if i.IsNil() && j.IsNil() {
   217  			return false, nil
   218  		} else if i.IsNil() {
   219  			return true, nil
   220  		} else if j.IsNil() {
   221  			return false, nil
   222  		}
   223  		switch itype := i.Interface().(type) {
   224  		case uint8:
   225  			if jtype, ok := j.Interface().(uint8); ok {
   226  				return itype < jtype, nil
   227  			}
   228  		case uint16:
   229  			if jtype, ok := j.Interface().(uint16); ok {
   230  				return itype < jtype, nil
   231  			}
   232  		case uint32:
   233  			if jtype, ok := j.Interface().(uint32); ok {
   234  				return itype < jtype, nil
   235  			}
   236  		case uint64:
   237  			if jtype, ok := j.Interface().(uint64); ok {
   238  				return itype < jtype, nil
   239  			}
   240  		case int8:
   241  			if jtype, ok := j.Interface().(int8); ok {
   242  				return itype < jtype, nil
   243  			}
   244  		case int16:
   245  			if jtype, ok := j.Interface().(int16); ok {
   246  				return itype < jtype, nil
   247  			}
   248  		case int32:
   249  			if jtype, ok := j.Interface().(int32); ok {
   250  				return itype < jtype, nil
   251  			}
   252  		case int64:
   253  			if jtype, ok := j.Interface().(int64); ok {
   254  				return itype < jtype, nil
   255  			}
   256  		case uint:
   257  			if jtype, ok := j.Interface().(uint); ok {
   258  				return itype < jtype, nil
   259  			}
   260  		case int:
   261  			if jtype, ok := j.Interface().(int); ok {
   262  				return itype < jtype, nil
   263  			}
   264  		case float32:
   265  			if jtype, ok := j.Interface().(float32); ok {
   266  				return itype < jtype, nil
   267  			}
   268  		case float64:
   269  			if jtype, ok := j.Interface().(float64); ok {
   270  				return itype < jtype, nil
   271  			}
   272  		case string:
   273  			if jtype, ok := j.Interface().(string); ok {
   274  				// check if it's a Quantity
   275  				itypeQuantity, err := resource.ParseQuantity(itype)
   276  				if err != nil {
   277  					return sortorder.NaturalLess(itype, jtype), nil
   278  				}
   279  				jtypeQuantity, err := resource.ParseQuantity(jtype)
   280  				if err != nil {
   281  					return sortorder.NaturalLess(itype, jtype), nil
   282  				}
   283  				// Both strings are quantity
   284  				return itypeQuantity.Cmp(jtypeQuantity) < 0, nil
   285  			}
   286  		default:
   287  			return false, fmt.Errorf("unsortable type: %T", itype)
   288  		}
   289  		return false, fmt.Errorf("unsortable interface: %v", i.Kind())
   290  
   291  	default:
   292  		return false, fmt.Errorf("unsortable type: %v", i.Kind())
   293  	}
   294  }
   295  
   296  func (r *RuntimeSort) Less(i, j int) bool {
   297  	iObj := r.objs[i]
   298  	jObj := r.objs[j]
   299  
   300  	var iValues [][]reflect.Value
   301  	var jValues [][]reflect.Value
   302  	var err error
   303  
   304  	parser := jsonpath.New("sorting").AllowMissingKeys(true)
   305  	err = parser.Parse(r.field)
   306  	if err != nil {
   307  		panic(err)
   308  	}
   309  
   310  	iValues, err = findJSONPathResults(parser, iObj)
   311  	if err != nil {
   312  		klog.Fatalf("Failed to get i values for %#v using %s (%#v)", iObj, r.field, err)
   313  	}
   314  
   315  	jValues, err = findJSONPathResults(parser, jObj)
   316  	if err != nil {
   317  		klog.Fatalf("Failed to get j values for %#v using %s (%v)", jObj, r.field, err)
   318  	}
   319  
   320  	if len(iValues) == 0 || len(iValues[0]) == 0 {
   321  		return true
   322  	}
   323  	if len(jValues) == 0 || len(jValues[0]) == 0 {
   324  		return false
   325  	}
   326  	iField := iValues[0][0]
   327  	jField := jValues[0][0]
   328  
   329  	less, err := isLess(iField, jField)
   330  	if err != nil {
   331  		klog.Exitf("Field %s in %T is an unsortable type: %s, err: %v", r.field, iObj, iField.Kind().String(), err)
   332  	}
   333  	return less
   334  }
   335  
   336  // OriginalPosition returns the starting (original) position of a particular index.
   337  // e.g. If OriginalPosition(0) returns 5 than the
   338  // item currently at position 0 was at position 5 in the original unsorted array.
   339  func (r *RuntimeSort) OriginalPosition(ix int) int {
   340  	if ix < 0 || ix > len(r.origPosition) {
   341  		return -1
   342  	}
   343  	return r.origPosition[ix]
   344  }
   345  
   346  type TableSorter struct {
   347  	field      string
   348  	obj        *metav1.Table
   349  	parsedRows [][][]reflect.Value
   350  }
   351  
   352  func (t *TableSorter) Len() int {
   353  	return len(t.obj.Rows)
   354  }
   355  
   356  func (t *TableSorter) Swap(i, j int) {
   357  	t.obj.Rows[i], t.obj.Rows[j] = t.obj.Rows[j], t.obj.Rows[i]
   358  	t.parsedRows[i], t.parsedRows[j] = t.parsedRows[j], t.parsedRows[i]
   359  }
   360  
   361  func (t *TableSorter) Less(i, j int) bool {
   362  	iValues := t.parsedRows[i]
   363  	jValues := t.parsedRows[j]
   364  
   365  	if len(iValues) == 0 || len(iValues[0]) == 0 {
   366  		return true
   367  	}
   368  	if len(jValues) == 0 || len(jValues[0]) == 0 {
   369  		return false
   370  	}
   371  
   372  	iField := iValues[0][0]
   373  	jField := jValues[0][0]
   374  
   375  	less, err := isLess(iField, jField)
   376  	if err != nil {
   377  		klog.Exitf("Field %s in %T is an unsortable type: %s, err: %v", t.field, t.parsedRows, iField.Kind().String(), err)
   378  	}
   379  	return less
   380  }
   381  
   382  func (t *TableSorter) Sort() error {
   383  	sort.Sort(t)
   384  	return nil
   385  }
   386  
   387  func NewTableSorter(table *metav1.Table, field string) (*TableSorter, error) {
   388  	var parsedRows [][][]reflect.Value
   389  
   390  	parser := jsonpath.New("sorting").AllowMissingKeys(true)
   391  	err := parser.Parse(field)
   392  	if err != nil {
   393  		return nil, fmt.Errorf("sorting error: %v", err)
   394  	}
   395  
   396  	fieldFoundOnce := false
   397  	for i := range table.Rows {
   398  		parsedRow, err := findJSONPathResults(parser, table.Rows[i].Object.Object)
   399  		if err != nil {
   400  			return nil, fmt.Errorf("Failed to get values for %#v using %s (%#v)", parsedRow, field, err)
   401  		}
   402  		parsedRows = append(parsedRows, parsedRow)
   403  		if len(parsedRow) > 0 && len(parsedRow[0]) > 0 {
   404  			fieldFoundOnce = true
   405  		}
   406  	}
   407  
   408  	if len(table.Rows) > 0 && !fieldFoundOnce {
   409  		return nil, fmt.Errorf("couldn't find any field with path %q in the list of objects", field)
   410  	}
   411  
   412  	return &TableSorter{
   413  		obj:        table,
   414  		field:      field,
   415  		parsedRows: parsedRows,
   416  	}, nil
   417  }
   418  func findJSONPathResults(parser *jsonpath.JSONPath, from runtime.Object) ([][]reflect.Value, error) {
   419  	if unstructuredObj, ok := from.(*unstructured.Unstructured); ok {
   420  		return parser.FindResults(unstructuredObj.Object)
   421  	}
   422  	return parser.FindResults(reflect.ValueOf(from).Elem().Interface())
   423  }
   424
View as plain text