1 // Copyright 2016 Google LLC. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 // Package iterator provides support for standard Google API iterators. 6 // See https://github.com/GoogleCloudPlatform/gcloud-golang/wiki/Iterator-Guidelines. 7 package iterator 8 9 import ( 10 "errors" 11 "fmt" 12 "reflect" 13 ) 14 15 // Done is returned by an iterator's Next method when the iteration is 16 // complete; when there are no more items to return. 17 var Done = errors.New("no more items in iterator") 18 19 // We don't support mixed calls to Next and NextPage because they play 20 // with the paging state in incompatible ways. 21 var errMixed = errors.New("iterator: Next and NextPage called on same iterator") 22 23 // PageInfo contains information about an iterator's paging state. 24 type PageInfo struct { 25 // Token is the token used to retrieve the next page of items from the 26 // API. You may set Token immediately after creating an iterator to 27 // begin iteration at a particular point. If Token is the empty string, 28 // the iterator will begin with the first eligible item. 29 // 30 // The result of setting Token after the first call to Next is undefined. 31 // 32 // After the underlying API method is called to retrieve a page of items, 33 // Token is set to the next-page token in the response. 34 Token string 35 36 // MaxSize is the maximum number of items returned by a call to the API. 37 // Set MaxSize as a hint to optimize the buffering behavior of the iterator. 38 // If zero, the page size is determined by the underlying service. 39 // 40 // Use Pager to retrieve a page of a specific, exact size. 41 MaxSize int 42 43 // The error state of the iterator. Manipulated by PageInfo.next and Pager. 44 // This is a latch: it starts as nil, and once set should never change. 45 err error 46 47 // If true, no more calls to fetch should be made. Set to true when fetch 48 // returns an empty page token. The iterator is Done when this is true AND 49 // the buffer is empty. 50 atEnd bool 51 52 // Function that fetches a page from the underlying service. It should pass 53 // the pageSize and pageToken arguments to the service, fill the buffer 54 // with the results from the call, and return the next-page token returned 55 // by the service. The function must not remove any existing items from the 56 // buffer. If the underlying RPC takes an int32 page size, pageSize should 57 // be silently truncated. 58 fetch func(pageSize int, pageToken string) (nextPageToken string, err error) 59 60 // Function that returns the number of currently buffered items. 61 bufLen func() int 62 63 // Function that returns the buffer, after setting the buffer variable to nil. 64 takeBuf func() interface{} 65 66 // Set to true on first call to PageInfo.next or Pager.NextPage. Used to check 67 // for calls to both Next and NextPage with the same iterator. 68 nextCalled, nextPageCalled bool 69 } 70 71 // NewPageInfo exposes internals for iterator implementations. 72 // It is not a stable interface. 73 var NewPageInfo = newPageInfo 74 75 // newPageInfo creates and returns a PageInfo and a next func. If an iterator can 76 // support paging, its iterator-creating method should call this. Each time the 77 // iterator's Next is called, it should call the returned next fn to determine 78 // whether a next item exists, and if so it should pop an item from the buffer. 79 // 80 // The fetch, bufLen and takeBuf arguments provide access to the iterator's 81 // internal slice of buffered items. They behave as described in PageInfo, above. 82 // 83 // The return value is the PageInfo.next method bound to the returned PageInfo value. 84 // (Returning it avoids exporting PageInfo.next.) 85 // 86 // Note: the returned PageInfo and next fn do not remove items from the buffer. 87 // It is up to the iterator using these to remove items from the buffer: 88 // typically by performing a pop in its Next. If items are not removed from the 89 // buffer, memory may grow unbounded. 90 func newPageInfo(fetch func(int, string) (string, error), bufLen func() int, takeBuf func() interface{}) (pi *PageInfo, next func() error) { 91 pi = &PageInfo{ 92 fetch: fetch, 93 bufLen: bufLen, 94 takeBuf: takeBuf, 95 } 96 return pi, pi.next 97 } 98 99 // Remaining returns the number of items available before the iterator makes another API call. 100 func (pi *PageInfo) Remaining() int { return pi.bufLen() } 101 102 // next provides support for an iterator's Next function. An iterator's Next 103 // should return the error returned by next if non-nil; else it can assume 104 // there is at least one item in its buffer, and it should return that item and 105 // remove it from the buffer. 106 func (pi *PageInfo) next() error { 107 pi.nextCalled = true 108 if pi.err != nil { // Once we get an error, always return it. 109 // TODO(jba): fix so users can retry on transient errors? Probably not worth it. 110 return pi.err 111 } 112 if pi.nextPageCalled { 113 pi.err = errMixed 114 return pi.err 115 } 116 // Loop until we get some items or reach the end. 117 for pi.bufLen() == 0 && !pi.atEnd { 118 if err := pi.fill(pi.MaxSize); err != nil { 119 pi.err = err 120 return pi.err 121 } 122 if pi.Token == "" { 123 pi.atEnd = true 124 } 125 } 126 // Either the buffer is non-empty or pi.atEnd is true (or both). 127 if pi.bufLen() == 0 { 128 // The buffer is empty and pi.atEnd is true, i.e. the service has no 129 // more items. 130 pi.err = Done 131 } 132 return pi.err 133 } 134 135 // Call the service to fill the buffer, using size and pi.Token. Set pi.Token to the 136 // next-page token returned by the call. 137 // If fill returns a non-nil error, the buffer will be empty. 138 func (pi *PageInfo) fill(size int) error { 139 tok, err := pi.fetch(size, pi.Token) 140 if err != nil { 141 pi.takeBuf() // clear the buffer 142 return err 143 } 144 pi.Token = tok 145 return nil 146 } 147 148 // Pageable is implemented by iterators that support paging. 149 type Pageable interface { 150 // PageInfo returns paging information associated with the iterator. 151 PageInfo() *PageInfo 152 } 153 154 // Pager supports retrieving iterator items a page at a time. 155 type Pager struct { 156 pageInfo *PageInfo 157 pageSize int 158 } 159 160 // NewPager returns a pager that uses iter. Calls to its NextPage method will 161 // obtain exactly pageSize items, unless fewer remain. The pageToken argument 162 // indicates where to start the iteration. Pass the empty string to start at 163 // the beginning, or pass a token retrieved from a call to Pager.NextPage. 164 // 165 // If you use an iterator with a Pager, you must not call Next on the iterator. 166 func NewPager(iter Pageable, pageSize int, pageToken string) *Pager { 167 p := &Pager{ 168 pageInfo: iter.PageInfo(), 169 pageSize: pageSize, 170 } 171 p.pageInfo.Token = pageToken 172 if pageSize <= 0 { 173 p.pageInfo.err = errors.New("iterator: page size must be positive") 174 } 175 return p 176 } 177 178 // NextPage retrieves a sequence of items from the iterator and appends them 179 // to slicep, which must be a pointer to a slice of the iterator's item type. 180 // Exactly p.pageSize items will be appended, unless fewer remain. 181 // 182 // The first return value is the page token to use for the next page of items. 183 // If empty, there are no more pages. Aside from checking for the end of the 184 // iteration, the returned page token is only needed if the iteration is to be 185 // resumed a later time, in another context (possibly another process). 186 // 187 // The second return value is non-nil if an error occurred. It will never be 188 // the special iterator sentinel value Done. To recognize the end of the 189 // iteration, compare nextPageToken to the empty string. 190 // 191 // It is possible for NextPage to return a single zero-length page along with 192 // an empty page token when there are no more items in the iteration. 193 func (p *Pager) NextPage(slicep interface{}) (nextPageToken string, err error) { 194 p.pageInfo.nextPageCalled = true 195 if p.pageInfo.err != nil { 196 return "", p.pageInfo.err 197 } 198 if p.pageInfo.nextCalled { 199 p.pageInfo.err = errMixed 200 return "", p.pageInfo.err 201 } 202 if p.pageInfo.bufLen() > 0 { 203 return "", errors.New("must call NextPage with an empty buffer") 204 } 205 // The buffer must be empty here, so takeBuf is a no-op. We call it just to get 206 // the buffer's type. 207 wantSliceType := reflect.PtrTo(reflect.ValueOf(p.pageInfo.takeBuf()).Type()) 208 if slicep == nil { 209 return "", errors.New("nil passed to Pager.NextPage") 210 } 211 vslicep := reflect.ValueOf(slicep) 212 if vslicep.Type() != wantSliceType { 213 return "", fmt.Errorf("slicep should be of type %s, got %T", wantSliceType, slicep) 214 } 215 for p.pageInfo.bufLen() < p.pageSize { 216 if err := p.pageInfo.fill(p.pageSize - p.pageInfo.bufLen()); err != nil { 217 p.pageInfo.err = err 218 return "", p.pageInfo.err 219 } 220 if p.pageInfo.Token == "" { 221 break 222 } 223 } 224 e := vslicep.Elem() 225 e.Set(reflect.AppendSlice(e, reflect.ValueOf(p.pageInfo.takeBuf()))) 226 return p.pageInfo.Token, nil 227 } 228