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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
|
package image
import (
"context"
ociv1 "github.com/opencontainers/image-spec/specs-go/v1"
"github.com/pkg/errors"
)
// layerTree is an internal representation of local layers.
type layerTree struct {
// nodes is the actual layer tree with layer IDs being keys.
nodes map[string]*layerNode
// ociCache is a cache for Image.ID -> OCI Image. Translations are done
// on-demand.
ociCache map[string]*ociv1.Image
}
// node returns a layerNode for the specified layerID.
func (t *layerTree) node(layerID string) *layerNode {
node, exists := t.nodes[layerID]
if !exists {
node = &layerNode{}
t.nodes[layerID] = node
}
return node
}
// toOCI returns an OCI image for the specified image.
func (t *layerTree) toOCI(ctx context.Context, i *Image) (*ociv1.Image, error) {
var err error
oci, exists := t.ociCache[i.ID()]
if !exists {
oci, err = i.ociv1Image(ctx)
t.ociCache[i.ID()] = oci
}
return oci, err
}
// layerNode is a node in a layerTree. It's ID is the key in a layerTree.
type layerNode struct {
children []*layerNode
images []*Image
parent *layerNode
}
// layerTree extracts a layerTree from the layers in the local storage and
// relates them to the specified images.
func (ir *Runtime) layerTree() (*layerTree, error) {
layers, err := ir.store.Layers()
if err != nil {
return nil, err
}
images, err := ir.GetImages()
if err != nil {
return nil, err
}
tree := layerTree{
nodes: make(map[string]*layerNode),
ociCache: make(map[string]*ociv1.Image),
}
// First build a tree purely based on layer information.
for _, layer := range layers {
node := tree.node(layer.ID)
if layer.Parent == "" {
continue
}
parent := tree.node(layer.Parent)
node.parent = parent
parent.children = append(parent.children, node)
}
// Now assign the images to each (top) layer.
for i := range images {
img := images[i] // do not leak loop variable outside the scope
topLayer := img.TopLayer()
if topLayer == "" {
continue
}
node, exists := tree.nodes[topLayer]
if !exists {
return nil, errors.Errorf("top layer %s of image %s not found in layer tree", img.TopLayer(), img.ID())
}
node.images = append(node.images, img)
}
return &tree, nil
}
// children returns the image IDs of children . Child images are images
// with either the same top layer as parent or parent being the true parent
// layer. Furthermore, the history of the parent and child images must match
// with the parent having one history item less.
// If all is true, all images are returned. Otherwise, the first image is
// returned.
func (t *layerTree) children(ctx context.Context, parent *Image, all bool) ([]string, error) {
if parent.TopLayer() == "" {
return nil, nil
}
var children []string
parentNode, exists := t.nodes[parent.TopLayer()]
if !exists {
return nil, errors.Errorf("layer not found in layer tree: %q", parent.TopLayer())
}
parentID := parent.ID()
parentOCI, err := t.toOCI(ctx, parent)
if err != nil {
return nil, err
}
// checkParent returns true if child and parent are in such a relation.
checkParent := func(child *Image) (bool, error) {
if parentID == child.ID() {
return false, nil
}
childOCI, err := t.toOCI(ctx, child)
if err != nil {
return false, err
}
// History check.
return areParentAndChild(parentOCI, childOCI), nil
}
// addChildrenFrom adds child images of parent to children. Returns
// true if any image is a child of parent.
addChildrenFromNode := func(node *layerNode) (bool, error) {
foundChildren := false
for _, childImage := range node.images {
isChild, err := checkParent(childImage)
if err != nil {
return foundChildren, err
}
if isChild {
foundChildren = true
children = append(children, childImage.ID())
if all {
return foundChildren, nil
}
}
}
return foundChildren, nil
}
// First check images where parent's top layer is also the parent
// layer.
for _, childNode := range parentNode.children {
found, err := addChildrenFromNode(childNode)
if err != nil {
return nil, err
}
if found && all {
return children, nil
}
}
// Now check images with the same top layer.
if _, err := addChildrenFromNode(parentNode); err != nil {
return nil, err
}
return children, nil
}
// parent returns the parent image or nil if no parent image could be found.
func (t *layerTree) parent(ctx context.Context, child *Image) (*Image, error) {
if child.TopLayer() == "" {
return nil, nil
}
node, exists := t.nodes[child.TopLayer()]
if !exists {
return nil, errors.Errorf("layer not found in layer tree: %q", child.TopLayer())
}
childOCI, err := t.toOCI(ctx, child)
if err != nil {
return nil, err
}
// Check images from the parent node (i.e., parent layer) and images
// with the same layer (i.e., same top layer).
childID := child.ID()
images := node.images
if node.parent != nil {
images = append(images, node.parent.images...)
}
for _, parent := range images {
if parent.ID() == childID {
continue
}
parentOCI, err := t.toOCI(ctx, parent)
if err != nil {
return nil, err
}
// History check.
if areParentAndChild(parentOCI, childOCI) {
return parent, nil
}
}
return nil, nil
}
// hasChildrenAndParent returns true if the specified image has children and a
// parent.
func (t *layerTree) hasChildrenAndParent(ctx context.Context, i *Image) (bool, error) {
children, err := t.children(ctx, i, false)
if err != nil {
return false, err
}
if len(children) == 0 {
return false, nil
}
parent, err := t.parent(ctx, i)
return parent != nil, err
}
|
