aggregator.go

Documentation: k8s.io/kube-openapi/pkg/aggregator

     1  /*
     2  Copyright 2017 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 aggregator
    18  
    19  import (
    20  	"fmt"
    21  	"reflect"
    22  	"sort"
    23  	"strings"
    24  
    25  	"k8s.io/kube-openapi/pkg/schemamutation"
    26  	"k8s.io/kube-openapi/pkg/util"
    27  	"k8s.io/kube-openapi/pkg/validation/spec"
    28  )
    29  
    30  const gvkKey = "x-kubernetes-group-version-kind"
    31  
    32  // usedDefinitionForSpec returns a map with all used definitions in the provided spec as keys and true as values.
    33  func usedDefinitionForSpec(root *spec.Swagger) map[string]bool {
    34  	usedDefinitions := map[string]bool{}
    35  	walkOnAllReferences(func(ref *spec.Ref) {
    36  		if refStr := ref.String(); refStr != "" && strings.HasPrefix(refStr, definitionPrefix) {
    37  			usedDefinitions[refStr[len(definitionPrefix):]] = true
    38  		}
    39  	}, root)
    40  	return usedDefinitions
    41  }
    42  
    43  // FilterSpecByPaths removes unnecessary paths and definitions used by those paths.
    44  // i.e. if a Path removed by this function, all definitions used by it and not used
    45  // anywhere else will also be removed.
    46  func FilterSpecByPaths(sp *spec.Swagger, keepPathPrefixes []string) {
    47  	*sp = *FilterSpecByPathsWithoutSideEffects(sp, keepPathPrefixes)
    48  }
    49  
    50  // FilterSpecByPathsWithoutSideEffects removes unnecessary paths and definitions used by those paths.
    51  // i.e. if a Path removed by this function, all definitions used by it and not used
    52  // anywhere else will also be removed.
    53  // It does not modify the input, but the output shares data structures with the input.
    54  func FilterSpecByPathsWithoutSideEffects(sp *spec.Swagger, keepPathPrefixes []string) *spec.Swagger {
    55  	if sp.Paths == nil {
    56  		return sp
    57  	}
    58  
    59  	// Walk all references to find all used definitions. This function
    60  	// want to only deal with unused definitions resulted from filtering paths.
    61  	// Thus a definition will be removed only if it has been used before but
    62  	// it is unused because of a path prune.
    63  	initialUsedDefinitions := usedDefinitionForSpec(sp)
    64  
    65  	// First remove unwanted paths
    66  	prefixes := util.NewTrie(keepPathPrefixes)
    67  	ret := *sp
    68  	ret.Paths = &spec.Paths{
    69  		VendorExtensible: sp.Paths.VendorExtensible,
    70  		Paths:            map[string]spec.PathItem{},
    71  	}
    72  	for path, pathItem := range sp.Paths.Paths {
    73  		if !prefixes.HasPrefix(path) {
    74  			continue
    75  		}
    76  		ret.Paths.Paths[path] = pathItem
    77  	}
    78  
    79  	// Walk all references to find all definition references.
    80  	usedDefinitions := usedDefinitionForSpec(&ret)
    81  
    82  	// Remove unused definitions
    83  	ret.Definitions = spec.Definitions{}
    84  	for k, v := range sp.Definitions {
    85  		if usedDefinitions[k] || !initialUsedDefinitions[k] {
    86  			ret.Definitions[k] = v
    87  		}
    88  	}
    89  
    90  	return &ret
    91  }
    92  
    93  // renameDefinitions renames definition references, without mutating the input.
    94  // The output might share data structures with the input.
    95  func renameDefinitions(s *spec.Swagger, renames map[string]string) *spec.Swagger {
    96  	refRenames := make(map[string]string, len(renames))
    97  	foundOne := false
    98  	for k, v := range renames {
    99  		refRenames[definitionPrefix+k] = definitionPrefix + v
   100  		if _, ok := s.Definitions[k]; ok {
   101  			foundOne = true
   102  		}
   103  	}
   104  
   105  	if !foundOne {
   106  		return s
   107  	}
   108  
   109  	ret := &spec.Swagger{}
   110  	*ret = *s
   111  
   112  	ret = schemamutation.ReplaceReferences(func(ref *spec.Ref) *spec.Ref {
   113  		refName := ref.String()
   114  		if newRef, found := refRenames[refName]; found {
   115  			ret := spec.MustCreateRef(newRef)
   116  			return &ret
   117  		}
   118  		return ref
   119  	}, ret)
   120  
   121  	renamedDefinitions := make(spec.Definitions, len(ret.Definitions))
   122  	for k, v := range ret.Definitions {
   123  		if newRef, found := renames[k]; found {
   124  			k = newRef
   125  		}
   126  		renamedDefinitions[k] = v
   127  	}
   128  	ret.Definitions = renamedDefinitions
   129  
   130  	return ret
   131  }
   132  
   133  // renameParameters renames parameter references, without mutating the input.
   134  // The output might share data structures with the input.
   135  func renameParameters(s *spec.Swagger, renames map[string]string) *spec.Swagger {
   136  	refRenames := make(map[string]string, len(renames))
   137  	foundOne := false
   138  	for k, v := range renames {
   139  		refRenames[parameterPrefix+k] = parameterPrefix + v
   140  		if _, ok := s.Parameters[k]; ok {
   141  			foundOne = true
   142  		}
   143  	}
   144  
   145  	if !foundOne {
   146  		return s
   147  	}
   148  
   149  	ret := &spec.Swagger{}
   150  	*ret = *s
   151  
   152  	ret = schemamutation.ReplaceReferences(func(ref *spec.Ref) *spec.Ref {
   153  		refName := ref.String()
   154  		if newRef, found := refRenames[refName]; found {
   155  			ret := spec.MustCreateRef(newRef)
   156  			return &ret
   157  		}
   158  		return ref
   159  	}, ret)
   160  
   161  	renamed := make(map[string]spec.Parameter, len(ret.Parameters))
   162  	for k, v := range ret.Parameters {
   163  		if newRef, found := renames[k]; found {
   164  			k = newRef
   165  		}
   166  		renamed[k] = v
   167  	}
   168  	ret.Parameters = renamed
   169  
   170  	return ret
   171  }
   172  
   173  // MergeSpecsIgnorePathConflictRenamingDefinitionsAndParameters is the same as
   174  // MergeSpecs except it will ignore any path conflicts by keeping the paths of
   175  // destination. It will rename definition and parameter conflicts.
   176  func MergeSpecsIgnorePathConflictRenamingDefinitionsAndParameters(dest, source *spec.Swagger) error {
   177  	return mergeSpecs(dest, source, true, true, true)
   178  }
   179  
   180  // MergeSpecsIgnorePathConflictDeprecated is the same as MergeSpecs except it will ignore any path
   181  // conflicts by keeping the paths of destination. It will rename definition and
   182  // parameter conflicts.
   183  func MergeSpecsIgnorePathConflictDeprecated(dest, source *spec.Swagger) error {
   184  	return mergeSpecs(dest, source, true, false, true)
   185  }
   186  
   187  // MergeSpecsFailOnDefinitionConflict is different from MergeSpecs as it fails if there is
   188  // a definition or parameter conflict.
   189  func MergeSpecsFailOnDefinitionConflict(dest, source *spec.Swagger) error {
   190  	return mergeSpecs(dest, source, false, false, false)
   191  }
   192  
   193  // MergeSpecs copies paths, definitions and parameters from source to dest, rename
   194  // definitions if needed. It will fail on path conflicts.
   195  //
   196  // The destination is mutated, the source is not.
   197  func MergeSpecs(dest, source *spec.Swagger) error {
   198  	return mergeSpecs(dest, source, true, true, false)
   199  }
   200  
   201  // mergeSpecs merges source into dest while resolving conflicts.
   202  // The source is not mutated.
   203  func mergeSpecs(dest, source *spec.Swagger, renameModelConflicts, renameParameterConflicts, ignorePathConflicts bool) (err error) {
   204  	// Paths may be empty, due to [ACL constraints](http://goo.gl/8us55a#securityFiltering).
   205  	if source.Paths == nil {
   206  		// When a source spec does not have any path, that means none of the definitions
   207  		// are used thus we should not do anything
   208  		return nil
   209  	}
   210  	if dest.Paths == nil {
   211  		dest.Paths = &spec.Paths{}
   212  	}
   213  	if ignorePathConflicts {
   214  		keepPaths := []string{}
   215  		hasConflictingPath := false
   216  		for k := range source.Paths.Paths {
   217  			if _, found := dest.Paths.Paths[k]; !found {
   218  				keepPaths = append(keepPaths, k)
   219  			} else {
   220  				hasConflictingPath = true
   221  			}
   222  		}
   223  		if len(keepPaths) == 0 {
   224  			// There is nothing to merge. All paths are conflicting.
   225  			return nil
   226  		}
   227  		if hasConflictingPath {
   228  			source = FilterSpecByPathsWithoutSideEffects(source, keepPaths)
   229  		}
   230  	}
   231  
   232  	// Check for model conflicts and rename to make definitions conflict-free (modulo different GVKs)
   233  	usedNames := map[string]bool{}
   234  	for k := range dest.Definitions {
   235  		usedNames[k] = true
   236  	}
   237  	renames := map[string]string{}
   238  DEFINITIONLOOP:
   239  	for k, v := range source.Definitions {
   240  		existing, found := dest.Definitions[k]
   241  		if !found || deepEqualDefinitionsModuloGVKs(&existing, &v) {
   242  			// skip for now, we copy them after the rename loop
   243  			continue
   244  		}
   245  
   246  		if !renameModelConflicts {
   247  			return fmt.Errorf("model name conflict in merging OpenAPI spec: %s", k)
   248  		}
   249  
   250  		// Reuse previously renamed model if one exists
   251  		var newName string
   252  		i := 1
   253  		for found {
   254  			i++
   255  			newName = fmt.Sprintf("%s_v%d", k, i)
   256  			existing, found = dest.Definitions[newName]
   257  			if found && deepEqualDefinitionsModuloGVKs(&existing, &v) {
   258  				renames[k] = newName
   259  				continue DEFINITIONLOOP
   260  			}
   261  		}
   262  
   263  		_, foundInSource := source.Definitions[newName]
   264  		for usedNames[newName] || foundInSource {
   265  			i++
   266  			newName = fmt.Sprintf("%s_v%d", k, i)
   267  			_, foundInSource = source.Definitions[newName]
   268  		}
   269  		renames[k] = newName
   270  		usedNames[newName] = true
   271  	}
   272  	source = renameDefinitions(source, renames)
   273  
   274  	// Check for parameter conflicts and rename to make parameters conflict-free
   275  	usedNames = map[string]bool{}
   276  	for k := range dest.Parameters {
   277  		usedNames[k] = true
   278  	}
   279  	renames = map[string]string{}
   280  PARAMETERLOOP:
   281  	for k, p := range source.Parameters {
   282  		existing, found := dest.Parameters[k]
   283  		if !found || reflect.DeepEqual(&existing, &p) {
   284  			// skip for now, we copy them after the rename loop
   285  			continue
   286  		}
   287  
   288  		if !renameParameterConflicts {
   289  			return fmt.Errorf("parameter name conflict in merging OpenAPI spec: %s", k)
   290  		}
   291  
   292  		// Reuse previously renamed parameter if one exists
   293  		var newName string
   294  		i := 1
   295  		for found {
   296  			i++
   297  			newName = fmt.Sprintf("%s_v%d", k, i)
   298  			existing, found = dest.Parameters[newName]
   299  			if found && reflect.DeepEqual(&existing, &p) {
   300  				renames[k] = newName
   301  				continue PARAMETERLOOP
   302  			}
   303  		}
   304  
   305  		_, foundInSource := source.Parameters[newName]
   306  		for usedNames[newName] || foundInSource {
   307  			i++
   308  			newName = fmt.Sprintf("%s_v%d", k, i)
   309  			_, foundInSource = source.Parameters[newName]
   310  		}
   311  		renames[k] = newName
   312  		usedNames[newName] = true
   313  	}
   314  	source = renameParameters(source, renames)
   315  
   316  	// Now without conflict (modulo different GVKs), copy definitions to dest
   317  	for k, v := range source.Definitions {
   318  		if existing, found := dest.Definitions[k]; !found {
   319  			if dest.Definitions == nil {
   320  				dest.Definitions = make(spec.Definitions, len(source.Definitions))
   321  			}
   322  			dest.Definitions[k] = v
   323  		} else if merged, changed, err := mergedGVKs(&existing, &v); err != nil {
   324  			return err
   325  		} else if changed {
   326  			existing.Extensions[gvkKey] = merged
   327  		}
   328  	}
   329  
   330  	// Now without conflict, copy parameters to dest
   331  	for k, v := range source.Parameters {
   332  		if _, found := dest.Parameters[k]; !found {
   333  			if dest.Parameters == nil {
   334  				dest.Parameters = make(map[string]spec.Parameter, len(source.Parameters))
   335  			}
   336  			dest.Parameters[k] = v
   337  		}
   338  	}
   339  
   340  	// Check for path conflicts
   341  	for k, v := range source.Paths.Paths {
   342  		if _, found := dest.Paths.Paths[k]; found {
   343  			return fmt.Errorf("unable to merge: duplicated path %s", k)
   344  		}
   345  		// PathItem may be empty, due to [ACL constraints](http://goo.gl/8us55a#securityFiltering).
   346  		if dest.Paths.Paths == nil {
   347  			dest.Paths.Paths = map[string]spec.PathItem{}
   348  		}
   349  		dest.Paths.Paths[k] = v
   350  	}
   351  
   352  	return nil
   353  }
   354  
   355  // deepEqualDefinitionsModuloGVKs compares s1 and s2, but ignores the x-kubernetes-group-version-kind extension.
   356  func deepEqualDefinitionsModuloGVKs(s1, s2 *spec.Schema) bool {
   357  	if s1 == nil {
   358  		return s2 == nil
   359  	} else if s2 == nil {
   360  		return false
   361  	}
   362  	if !reflect.DeepEqual(s1.Extensions, s2.Extensions) {
   363  		for k, v := range s1.Extensions {
   364  			if k == gvkKey {
   365  				continue
   366  			}
   367  			if !reflect.DeepEqual(v, s2.Extensions[k]) {
   368  				return false
   369  			}
   370  		}
   371  		len1 := len(s1.Extensions)
   372  		len2 := len(s2.Extensions)
   373  		if _, found := s1.Extensions[gvkKey]; found {
   374  			len1--
   375  		}
   376  		if _, found := s2.Extensions[gvkKey]; found {
   377  			len2--
   378  		}
   379  		if len1 != len2 {
   380  			return false
   381  		}
   382  
   383  		if s1.Extensions != nil {
   384  			shallowCopy := *s1
   385  			s1 = &shallowCopy
   386  			s1.Extensions = nil
   387  		}
   388  		if s2.Extensions != nil {
   389  			shallowCopy := *s2
   390  			s2 = &shallowCopy
   391  			s2.Extensions = nil
   392  		}
   393  	}
   394  
   395  	return reflect.DeepEqual(s1, s2)
   396  }
   397  
   398  // mergedGVKs merges the x-kubernetes-group-version-kind slices and returns the result, and whether
   399  // s1's x-kubernetes-group-version-kind slice was changed at all.
   400  func mergedGVKs(s1, s2 *spec.Schema) (interface{}, bool, error) {
   401  	gvk1, found1 := s1.Extensions[gvkKey]
   402  	gvk2, found2 := s2.Extensions[gvkKey]
   403  
   404  	if !found1 {
   405  		return gvk2, found2, nil
   406  	}
   407  	if !found2 {
   408  		return gvk1, false, nil
   409  	}
   410  
   411  	slice1, ok := gvk1.([]interface{})
   412  	if !ok {
   413  		return nil, false, fmt.Errorf("expected slice of GroupVersionKinds, got: %+v", slice1)
   414  	}
   415  	slice2, ok := gvk2.([]interface{})
   416  	if !ok {
   417  		return nil, false, fmt.Errorf("expected slice of GroupVersionKinds, got: %+v", slice2)
   418  	}
   419  
   420  	ret := make([]interface{}, len(slice1), len(slice1)+len(slice2))
   421  	keys := make([]string, 0, len(slice1)+len(slice2))
   422  	copy(ret, slice1)
   423  	seen := make(map[string]bool, len(slice1))
   424  	for _, x := range slice1 {
   425  		gvk, ok := x.(map[string]interface{})
   426  		if !ok {
   427  			return nil, false, fmt.Errorf(`expected {"group": <group>, "kind": <kind>, "version": <version>}, got: %#v`, x)
   428  		}
   429  		k := fmt.Sprintf("%s/%s.%s", gvk["group"], gvk["version"], gvk["kind"])
   430  		keys = append(keys, k)
   431  		seen[k] = true
   432  	}
   433  	changed := false
   434  	for _, x := range slice2 {
   435  		gvk, ok := x.(map[string]interface{})
   436  		if !ok {
   437  			return nil, false, fmt.Errorf(`expected {"group": <group>, "kind": <kind>, "version": <version>}, got: %#v`, x)
   438  		}
   439  		k := fmt.Sprintf("%s/%s.%s", gvk["group"], gvk["version"], gvk["kind"])
   440  		if seen[k] {
   441  			continue
   442  		}
   443  		ret = append(ret, x)
   444  		keys = append(keys, k)
   445  		changed = true
   446  	}
   447  
   448  	if changed {
   449  		sort.Sort(byKeys{ret, keys})
   450  	}
   451  
   452  	return ret, changed, nil
   453  }
   454  
   455  type byKeys struct {
   456  	values []interface{}
   457  	keys   []string
   458  }
   459  
   460  func (b byKeys) Len() int {
   461  	return len(b.values)
   462  }
   463  
   464  func (b byKeys) Less(i, j int) bool {
   465  	return b.keys[i] < b.keys[j]
   466  }
   467  
   468  func (b byKeys) Swap(i, j int) {
   469  	b.values[i], b.values[j] = b.values[j], b.values[i]
   470  	b.keys[i], b.keys[j] = b.keys[j], b.keys[i]
   471  }
   472
View as plain text