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
|
package merkletrie
import (
"fmt"
"io"
"gopkg.in/src-d/go-git.v4/utils/merkletrie/internal/frame"
"gopkg.in/src-d/go-git.v4/utils/merkletrie/noder"
)
// Iter is an iterator for merkletries (only the trie part of the
// merkletrie is relevant here, it does not use the Hasher interface).
//
// The iteration is performed in depth-first pre-order. Entries at each
// depth are traversed in (case-sensitive) alphabetical order.
//
// This is the kind of traversal you will expect when listing ordinary
// files and directories recursively, for example:
//
// Trie Traversal order
// ---- ---------------
// .
// / | \ c
// / | \ d/
// d c z ===> d/a
// / \ d/b
// b a z
//
//
// This iterator is somewhat especial as you can chose to skip whole
// "directories" when iterating:
//
// - The Step method will iterate normally.
//
// - the Next method will not descend deeper into the tree.
//
// For example, if the iterator is at `d/`, the Step method will return
// `d/a` while the Next would have returned `z` instead (skipping `d/`
// and its descendants). The name of the these two methods are based on
// the well known "next" and "step" operations, quite common in
// debuggers, like gdb.
//
// The paths returned by the iterator will be relative, if the iterator
// was created from a single node, or absolute, if the iterator was
// created from the path to the node (the path will be prefixed to all
// returned paths).
type Iter struct {
// Tells if the iteration has started.
hasStarted bool
// The top of this stack has the current node and its siblings. The
// rest of the stack keeps the ancestors of the current node and
// their corresponding siblings. The current element is always the
// top element of the top frame.
//
// When "step"ping into a node, its children are pushed as a new
// frame.
//
// When "next"ing pass a node, the current element is dropped by
// popping the top frame.
frameStack []*frame.Frame
// The base path used to turn the relative paths used internally by
// the iterator into absolute paths used by external applications.
// For relative iterator this will be nil.
base noder.Path
}
// NewIter returns a new relative iterator using the provider noder as
// its unnamed root. When iterating, all returned paths will be
// relative to node.
func NewIter(n noder.Noder) (*Iter, error) {
return newIter(n, nil)
}
// NewIterFromPath returns a new absolute iterator from the noder at the
// end of the path p. When iterating, all returned paths will be
// absolute, using the root of the path p as their root.
func NewIterFromPath(p noder.Path) (*Iter, error) {
return newIter(p, p) // Path implements Noder
}
func newIter(root noder.Noder, base noder.Path) (*Iter, error) {
ret := &Iter{
base: base,
}
frame, err := frame.New(root)
if err != nil {
return nil, err
}
ret.push(frame)
return ret, nil
}
func (iter *Iter) top() (*frame.Frame, bool) {
if len(iter.frameStack) == 0 {
return nil, false
}
top := len(iter.frameStack) - 1
return iter.frameStack[top], true
}
func (iter *Iter) push(f *frame.Frame) {
iter.frameStack = append(iter.frameStack, f)
}
const (
doDescend = true
dontDescend = false
)
// Next returns the path of the next node without descending deeper into
// the trie and nil. If there are no more entries in the trie it
// returns nil and io.EOF. In case of error, it will return nil and the
// error.
func (iter *Iter) Next() (noder.Path, error) {
return iter.advance(dontDescend)
}
// Step returns the path to the next node in the trie, descending deeper
// into it if needed, and nil. If there are no more nodes in the trie,
// it returns nil and io.EOF. In case of error, it will return nil and
// the error.
func (iter *Iter) Step() (noder.Path, error) {
return iter.advance(doDescend)
}
// Advances the iterator in the desired direction: descend or
// dontDescend.
//
// Returns the new current element and a nil error on success. If there
// are no more elements in the trie below the base, it returns nil, and
// io.EOF. Returns nil and an error in case of errors.
func (iter *Iter) advance(wantDescend bool) (noder.Path, error) {
current, err := iter.current()
if err != nil {
return nil, err
}
// The first time we just return the current node.
if !iter.hasStarted {
iter.hasStarted = true
return current, nil
}
// Advances means getting a next current node, either its first child or
// its next sibling, depending if we must descend or not.
numChildren, err := current.NumChildren()
if err != nil {
return nil, err
}
mustDescend := numChildren != 0 && wantDescend
if mustDescend {
// descend: add a new frame with the current's children.
frame, err := frame.New(current)
if err != nil {
return nil, err
}
iter.push(frame)
} else {
// don't descend: just drop the current node
iter.drop()
}
return iter.current()
}
// Returns the path to the current node, adding the base if there was
// one, and a nil error. If there were no noders left, it returns nil
// and io.EOF. If an error occurred, it returns nil and the error.
func (iter *Iter) current() (noder.Path, error) {
if topFrame, ok := iter.top(); !ok {
return nil, io.EOF
} else if _, ok := topFrame.First(); !ok {
return nil, io.EOF
}
ret := make(noder.Path, 0, len(iter.base)+len(iter.frameStack))
// concat the base...
ret = append(ret, iter.base...)
// ... and the current node and all its ancestors
for i, f := range iter.frameStack {
t, ok := f.First()
if !ok {
panic(fmt.Sprintf("frame %d is empty", i))
}
ret = append(ret, t)
}
return ret, nil
}
// removes the current node if any, and all the frames that become empty as a
// consecuence of this action.
func (iter *Iter) drop() {
frame, ok := iter.top()
if !ok {
return
}
frame.Drop()
// if the frame is empty, remove it and its parent, recursively
if frame.Len() == 0 {
top := len(iter.frameStack) - 1
iter.frameStack[top] = nil
iter.frameStack = iter.frameStack[:top]
iter.drop()
}
}
|
