forked from vmware-archive/kubecfg
-
Notifications
You must be signed in to change notification settings - Fork 0
/
sort.go
158 lines (136 loc) · 4.64 KB
/
sort.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
// Copyright 2017 The kubecfg authors
//
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package utils
import (
"sort"
log "github.com/sirupsen/logrus"
"k8s.io/apimachinery/pkg/apis/meta/v1/unstructured"
"k8s.io/apimachinery/pkg/runtime/schema"
"k8s.io/client-go/discovery"
"k8s.io/kube-openapi/pkg/util/proto"
)
var (
gkTpr = schema.GroupKind{Group: "extensions", Kind: "ThirdPartyResource"}
gkCrd = schema.GroupKind{Group: "apiextensions", Kind: "CustomResourceDefinition"}
)
// a podSpecVisitor traverses a schema tree and records whether the schema
// contains a PodSpec resource.
type podSpecVisitor bool
func (v *podSpecVisitor) VisitKind(k *proto.Kind) {
if k.GetPath().String() == "io.k8s.api.core.v1.PodSpec" {
*v = true
return
}
for _, f := range k.Fields {
f.Accept(v)
if *v == true {
return
}
}
}
func (v *podSpecVisitor) VisitReference(s proto.Reference) { s.SubSchema().Accept(v) }
func (v *podSpecVisitor) VisitArray(s *proto.Array) { s.SubType.Accept(v) }
func (v *podSpecVisitor) VisitMap(s *proto.Map) { s.SubType.Accept(v) }
func (v *podSpecVisitor) VisitPrimitive(p *proto.Primitive) {}
var podSpecCache = map[string]podSpecVisitor{}
func containsPodSpec(disco discovery.OpenAPISchemaInterface, gvk schema.GroupVersionKind) bool {
result, ok := podSpecCache[gvk.String()]
if ok {
return bool(result)
}
oapi, err := NewOpenAPISchemaFor(disco, gvk)
if err != nil {
log.Debugf("error fetching schema for %s: %v", gvk, err)
return false
}
oapi.schema.Accept(&result)
podSpecCache[gvk.String()] = result
return bool(result)
}
// Arbitrary numbers used to do a simple topological sort of resources.
func depTier(disco ServerResourcesOpenAPISchema, o schema.ObjectKind) (int, error) {
gvk := o.GroupVersionKind()
if gk := gvk.GroupKind(); gk == gkTpr || gk == gkCrd {
// Special case: these create other types
return 10, nil
}
rsrc, err := serverResourceForGroupVersionKind(disco, gvk)
if err != nil {
log.Debugf("unable to fetch resource for %s (%v), continuing", gvk, err)
return 50, nil
}
if !rsrc.Namespaced {
// Place global before namespaced
return 20, nil
} else if containsPodSpec(disco, gvk) {
// (Potentially) starts a pod, so place last
return 100, nil
} else {
// Everything else
return 50, nil
}
}
// A subset of discovery.DiscoveryInterface
type ServerResourcesOpenAPISchema interface {
discovery.ServerResourcesInterface
discovery.OpenAPISchemaInterface
}
// DependencyOrder is a `sort.Interface` that *best-effort* sorts the
// objects so that known dependencies appear earlier in the list. The
// idea is to prevent *some* of the "crash-restart" loops when
// creating inter-dependent resources.
func DependencyOrder(disco ServerResourcesOpenAPISchema, list []*unstructured.Unstructured) (sort.Interface, error) {
sortKeys := make([]int, len(list))
for i, item := range list {
var err error
sortKeys[i], err = depTier(disco, item.GetObjectKind())
if err != nil {
return nil, err
}
}
log.Debugf("sortKeys is %v", sortKeys)
return &mappedSort{sortKeys: sortKeys, items: list}, nil
}
type mappedSort struct {
sortKeys []int
items []*unstructured.Unstructured
}
func (l *mappedSort) Len() int { return len(l.items) }
func (l *mappedSort) Swap(i, j int) {
l.sortKeys[i], l.sortKeys[j] = l.sortKeys[j], l.sortKeys[i]
l.items[i], l.items[j] = l.items[j], l.items[i]
}
func (l *mappedSort) Less(i, j int) bool {
if l.sortKeys[i] != l.sortKeys[j] {
return l.sortKeys[i] < l.sortKeys[j]
}
// Fall back to alpha sort, to give persistent order
return AlphabeticalOrder(l.items).Less(i, j)
}
// AlphabeticalOrder is a `sort.Interface` that sorts the
// objects by namespace/name/kind alphabetical order
type AlphabeticalOrder []*unstructured.Unstructured
func (l AlphabeticalOrder) Len() int { return len(l) }
func (l AlphabeticalOrder) Swap(i, j int) { l[i], l[j] = l[j], l[i] }
func (l AlphabeticalOrder) Less(i, j int) bool {
a, b := l[i], l[j]
if a.GetNamespace() != b.GetNamespace() {
return a.GetNamespace() < b.GetNamespace()
}
if a.GetName() != b.GetName() {
return a.GetName() < b.GetName()
}
return a.GetKind() < b.GetKind()
}