1package merkletrie 2 3import ( 4 "fmt" 5 "io" 6 7 "github.com/jesseduffield/go-git/v5/utils/merkletrie/internal/frame" 8 "github.com/jesseduffield/go-git/v5/utils/merkletrie/noder" 9) 10 11// Iter is an iterator for merkletries (only the trie part of the 12// merkletrie is relevant here, it does not use the Hasher interface). 13// 14// The iteration is performed in depth-first pre-order. Entries at each 15// depth are traversed in (case-sensitive) alphabetical order. 16// 17// This is the kind of traversal you will expect when listing ordinary 18// files and directories recursively, for example: 19// 20// Trie Traversal order 21// ---- --------------- 22// . 23// / | \ c 24// / | \ d/ 25// d c z ===> d/a 26// / \ d/b 27// b a z 28// 29// 30// This iterator is somewhat especial as you can chose to skip whole 31// "directories" when iterating: 32// 33// - The Step method will iterate normally. 34// 35// - the Next method will not descend deeper into the tree. 36// 37// For example, if the iterator is at `d/`, the Step method will return 38// `d/a` while the Next would have returned `z` instead (skipping `d/` 39// and its descendants). The name of the these two methods are based on 40// the well known "next" and "step" operations, quite common in 41// debuggers, like gdb. 42// 43// The paths returned by the iterator will be relative, if the iterator 44// was created from a single node, or absolute, if the iterator was 45// created from the path to the node (the path will be prefixed to all 46// returned paths). 47type Iter struct { 48 // Tells if the iteration has started. 49 hasStarted bool 50 // The top of this stack has the current node and its siblings. The 51 // rest of the stack keeps the ancestors of the current node and 52 // their corresponding siblings. The current element is always the 53 // top element of the top frame. 54 // 55 // When "step"ping into a node, its children are pushed as a new 56 // frame. 57 // 58 // When "next"ing pass a node, the current element is dropped by 59 // popping the top frame. 60 frameStack []*frame.Frame 61 // The base path used to turn the relative paths used internally by 62 // the iterator into absolute paths used by external applications. 63 // For relative iterator this will be nil. 64 base noder.Path 65} 66 67// NewIter returns a new relative iterator using the provider noder as 68// its unnamed root. When iterating, all returned paths will be 69// relative to node. 70func NewIter(n noder.Noder) (*Iter, error) { 71 return newIter(n, nil) 72} 73 74// NewIterFromPath returns a new absolute iterator from the noder at the 75// end of the path p. When iterating, all returned paths will be 76// absolute, using the root of the path p as their root. 77func NewIterFromPath(p noder.Path) (*Iter, error) { 78 return newIter(p, p) // Path implements Noder 79} 80 81func newIter(root noder.Noder, base noder.Path) (*Iter, error) { 82 ret := &Iter{ 83 base: base, 84 } 85 86 if root == nil { 87 return ret, nil 88 } 89 90 frame, err := frame.New(root) 91 if err != nil { 92 return nil, err 93 } 94 ret.push(frame) 95 96 return ret, nil 97} 98 99func (iter *Iter) top() (*frame.Frame, bool) { 100 if len(iter.frameStack) == 0 { 101 return nil, false 102 } 103 top := len(iter.frameStack) - 1 104 105 return iter.frameStack[top], true 106} 107 108func (iter *Iter) push(f *frame.Frame) { 109 iter.frameStack = append(iter.frameStack, f) 110} 111 112const ( 113 doDescend = true 114 dontDescend = false 115) 116 117// Next returns the path of the next node without descending deeper into 118// the trie and nil. If there are no more entries in the trie it 119// returns nil and io.EOF. In case of error, it will return nil and the 120// error. 121func (iter *Iter) Next() (noder.Path, error) { 122 return iter.advance(dontDescend) 123} 124 125// Step returns the path to the next node in the trie, descending deeper 126// into it if needed, and nil. If there are no more nodes in the trie, 127// it returns nil and io.EOF. In case of error, it will return nil and 128// the error. 129func (iter *Iter) Step() (noder.Path, error) { 130 return iter.advance(doDescend) 131} 132 133// Advances the iterator in the desired direction: descend or 134// dontDescend. 135// 136// Returns the new current element and a nil error on success. If there 137// are no more elements in the trie below the base, it returns nil, and 138// io.EOF. Returns nil and an error in case of errors. 139func (iter *Iter) advance(wantDescend bool) (noder.Path, error) { 140 current, err := iter.current() 141 if err != nil { 142 return nil, err 143 } 144 145 // The first time we just return the current node. 146 if !iter.hasStarted { 147 iter.hasStarted = true 148 return current, nil 149 } 150 151 // Advances means getting a next current node, either its first child or 152 // its next sibling, depending if we must descend or not. 153 numChildren, err := current.NumChildren() 154 if err != nil { 155 return nil, err 156 } 157 158 mustDescend := numChildren != 0 && wantDescend 159 if mustDescend { 160 // descend: add a new frame with the current's children. 161 frame, err := frame.New(current) 162 if err != nil { 163 return nil, err 164 } 165 iter.push(frame) 166 } else { 167 // don't descend: just drop the current node 168 iter.drop() 169 } 170 171 return iter.current() 172} 173 174// Returns the path to the current node, adding the base if there was 175// one, and a nil error. If there were no noders left, it returns nil 176// and io.EOF. If an error occurred, it returns nil and the error. 177func (iter *Iter) current() (noder.Path, error) { 178 if topFrame, ok := iter.top(); !ok { 179 return nil, io.EOF 180 } else if _, ok := topFrame.First(); !ok { 181 return nil, io.EOF 182 } 183 184 ret := make(noder.Path, 0, len(iter.base)+len(iter.frameStack)) 185 186 // concat the base... 187 ret = append(ret, iter.base...) 188 // ... and the current node and all its ancestors 189 for i, f := range iter.frameStack { 190 t, ok := f.First() 191 if !ok { 192 panic(fmt.Sprintf("frame %d is empty", i)) 193 } 194 ret = append(ret, t) 195 } 196 197 return ret, nil 198} 199 200// removes the current node if any, and all the frames that become empty as a 201// consequence of this action. 202func (iter *Iter) drop() { 203 frame, ok := iter.top() 204 if !ok { 205 return 206 } 207 208 frame.Drop() 209 // if the frame is empty, remove it and its parent, recursively 210 if frame.Len() == 0 { 211 top := len(iter.frameStack) - 1 212 iter.frameStack[top] = nil 213 iter.frameStack = iter.frameStack[:top] 214 iter.drop() 215 } 216} 217