LLVM 24.0.0git
BitstreamReader.cpp
Go to the documentation of this file.
1//===- BitstreamReader.cpp - BitstreamReader implementation ---------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
10#include "llvm/ADT/StringRef.h"
11#include <cassert>
12#include <cstring>
13#include <optional>
14#include <string>
15
16using namespace llvm;
17
18//===----------------------------------------------------------------------===//
19// BitstreamCursor implementation
20//===----------------------------------------------------------------------===//
21//
22static Error error(const char *Message) {
23 return createStringError(std::errc::illegal_byte_sequence, Message);
24}
25
28 if (NumBits > sizeInBits() - std::min(BitNo, sizeInBits()))
29 return createStringError(std::errc::io_error,
30 "Unexpected end of file reading %u bits at bit "
31 "%" PRIu64 " of %" PRIu64,
32 NumBits, BitNo, sizeInBits());
33
34 // Copy the rest of the stream into a zero-padded buffer to read from.
35 uint8_t Buf[2 * sizeof(word_t)] = {};
36 size_t ByteNo = BitNo / 8;
37 std::memcpy(Buf, BitcodeBytes.data() + ByteNo,
38 std::min(sizeof(Buf), BitcodeBytes.size() - ByteNo));
39 word_t R =
41 support::unaligned>(Buf, BitNo % 8);
42 BitNo += NumBits;
43 return R & (~word_t(0) >> (BitsInWord - NumBits));
44}
45
46/// Having read the ENTER_SUBBLOCK abbrevid, enter the block.
47Error BitstreamCursor::EnterSubBlock(unsigned BlockID, unsigned *NumWordsP) {
48 // Save the current block's state on BlockScope.
49 BlockScope.push_back(Block(CurCodeSize));
50 BlockScope.back().PrevAbbrevs.swap(CurAbbrevs);
51
52 // Add the abbrevs specific to this block to the CurAbbrevs list.
53 if (BlockInfo) {
54 if (const BitstreamBlockInfo::BlockInfo *Info =
55 BlockInfo->getBlockInfo(BlockID)) {
56 llvm::append_range(CurAbbrevs, Info->Abbrevs);
57 }
58 }
59
60 // Get the codesize of this block.
62 if (!MaybeVBR)
63 return MaybeVBR.takeError();
64 CurCodeSize = MaybeVBR.get();
65
66 if (CurCodeSize > MaxChunkSize)
68 std::errc::illegal_byte_sequence,
69 "can't read more than %zu at a time, trying to read %u", +MaxChunkSize,
70 CurCodeSize);
71
74 if (!MaybeNum)
75 return MaybeNum.takeError();
76 word_t NumWords = MaybeNum.get();
77 if (NumWordsP)
78 *NumWordsP = NumWords;
79
80 if (CurCodeSize == 0)
82 std::errc::illegal_byte_sequence,
83 "can't enter sub-block: current code size is 0");
84 if (AtEndOfStream())
86 std::errc::illegal_byte_sequence,
87 "can't enter sub block: already at end of stream");
88
89 return Error::success();
90}
91
93 const BitCodeAbbrevOp &Op) {
94 assert(!Op.isLiteral() && "Not to be used with literals!");
95
96 // Decode the value as we are commanded.
97 switch (Op.getEncoding()) {
100 llvm_unreachable("Should not reach here");
102 assert((unsigned)Op.getEncodingData() <= Cursor.MaxChunkSize);
103 return Cursor.Read((unsigned)Op.getEncodingData());
105 assert((unsigned)Op.getEncodingData() <= Cursor.MaxChunkSize);
106 return Cursor.ReadVBR64((unsigned)Op.getEncodingData());
108 if (Expected<unsigned> Res = Cursor.Read(6))
109 return BitCodeAbbrevOp::DecodeChar6(Res.get());
110 else
111 return Res.takeError();
112 }
113 llvm_unreachable("invalid abbreviation encoding");
114}
115
116/// skipRecord - Read the current record and discard it.
118 // Skip unabbreviated records by reading past their entries.
119 if (AbbrevID == bitc::UNABBREV_RECORD) {
120 Expected<uint32_t> MaybeCode = ReadVBR(6);
121 if (!MaybeCode)
122 return MaybeCode.takeError();
123 unsigned Code = MaybeCode.get();
124 Expected<uint32_t> MaybeVBR = ReadVBR(6);
125 if (!MaybeVBR)
126 return MaybeVBR.takeError();
127 unsigned NumElts = MaybeVBR.get();
128 for (unsigned i = 0; i != NumElts; ++i)
129 if (Expected<uint64_t> Res = ReadVBR64(6))
130 ; // Skip!
131 else
132 return Res.takeError();
133 return Code;
134 }
135
136 Expected<const BitCodeAbbrev *> MaybeAbbv = getAbbrev(AbbrevID);
137 if (!MaybeAbbv)
138 return MaybeAbbv.takeError();
139
140 const BitCodeAbbrev *Abbv = MaybeAbbv.get();
141 const BitCodeAbbrevOp &CodeOp = Abbv->getOperandInfo(0);
142 unsigned Code;
143 if (CodeOp.isLiteral())
144 Code = CodeOp.getLiteralValue();
145 else {
146 if (CodeOp.getEncoding() == BitCodeAbbrevOp::Array ||
149 std::errc::illegal_byte_sequence,
150 "Abbreviation starts with an Array or a Blob");
151 Expected<uint64_t> MaybeCode = readAbbreviatedField(*this, CodeOp);
152 if (!MaybeCode)
153 return MaybeCode.takeError();
154 Code = MaybeCode.get();
155 }
156
157 for (unsigned i = 1, e = Abbv->getNumOperandInfos(); i < e; ++i) {
158 const BitCodeAbbrevOp &Op = Abbv->getOperandInfo(i);
159 if (Op.isLiteral())
160 continue;
161
162 if (Op.getEncoding() != BitCodeAbbrevOp::Array &&
163 Op.getEncoding() != BitCodeAbbrevOp::Blob) {
164 if (Expected<uint64_t> MaybeField = readAbbreviatedField(*this, Op))
165 continue;
166 else
167 return MaybeField.takeError();
168 }
169
170 if (Op.getEncoding() == BitCodeAbbrevOp::Array) {
171 // Array case. Read the number of elements as a vbr6.
172 Expected<uint32_t> MaybeNum = ReadVBR(6);
173 if (!MaybeNum)
174 return MaybeNum.takeError();
175 unsigned NumElts = MaybeNum.get();
176
177 // Get the element encoding.
178 assert(i+2 == e && "array op not second to last?");
179 const BitCodeAbbrevOp &EltEnc = Abbv->getOperandInfo(++i);
180
181 // Read all the elements.
182 // Decode the value as we are commanded.
183 switch (EltEnc.getEncoding()) {
184 default:
185 return error("Array element type can't be an Array or a Blob");
187 assert((unsigned)EltEnc.getEncodingData() <= MaxChunkSize);
188 if (Error Err =
189 JumpToBit(GetCurrentBitNo() + static_cast<uint64_t>(NumElts) *
190 EltEnc.getEncodingData()))
191 return Err;
192 break;
194 assert((unsigned)EltEnc.getEncodingData() <= MaxChunkSize);
195 for (; NumElts; --NumElts)
196 if (Expected<uint64_t> Res =
197 ReadVBR64((unsigned)EltEnc.getEncodingData()))
198 ; // Skip!
199 else
200 return Res.takeError();
201 break;
203 if (Error Err = JumpToBit(GetCurrentBitNo() + NumElts * 6))
204 return Err;
205 break;
206 }
207 continue;
208 }
209
210 assert(Op.getEncoding() == BitCodeAbbrevOp::Blob);
211 // Blob case. Read the number of bytes as a vbr6.
212 Expected<uint32_t> MaybeNum = ReadVBR(6);
213 if (!MaybeNum)
214 return MaybeNum.takeError();
215 unsigned NumElts = MaybeNum.get();
216 SkipToFourByteBoundary(); // 32-bit alignment
217
218 // Figure out where the end of this blob will be including tail padding.
219 const size_t NewEnd = GetCurrentBitNo() + alignTo(NumElts, 4) * 8;
220
221 // If this would read off the end of the bitcode file, just set the
222 // record to empty and return.
223 if (!canSkipToPos(NewEnd/8)) {
224 skipToEnd();
225 break;
226 }
227
228 // Skip over the blob.
229 if (Error Err = JumpToBit(NewEnd))
230 return Err;
231 }
232 return Code;
233}
234
237 StringRef *Blob) {
238 if (AbbrevID == bitc::UNABBREV_RECORD) {
239 Expected<uint32_t> MaybeCode = ReadVBR(6);
240 if (!MaybeCode)
241 return MaybeCode.takeError();
242 uint32_t Code = MaybeCode.get();
243 Expected<uint32_t> MaybeNumElts = ReadVBR(6);
244 if (!MaybeNumElts)
245 return error(
246 ("Failed to read size: " + toString(MaybeNumElts.takeError()))
247 .c_str());
248 uint32_t NumElts = MaybeNumElts.get();
249 if (!isSizePlausible(NumElts))
250 return error("Size is not plausible");
251 Vals.reserve(Vals.size() + NumElts);
252
253 for (unsigned i = 0; i != NumElts; ++i)
254 if (Expected<uint64_t> MaybeVal = ReadVBR64(6))
255 Vals.push_back(MaybeVal.get());
256 else
257 return MaybeVal.takeError();
258 return Code;
259 }
260
261 Expected<const BitCodeAbbrev *> MaybeAbbv = getAbbrev(AbbrevID);
262 if (!MaybeAbbv)
263 return MaybeAbbv.takeError();
264 const BitCodeAbbrev *Abbv = MaybeAbbv.get();
265
266 // Read the record code first.
267 assert(Abbv->getNumOperandInfos() != 0 && "no record code in abbreviation?");
268 const BitCodeAbbrevOp &CodeOp = Abbv->getOperandInfo(0);
269 unsigned Code;
270 if (CodeOp.isLiteral())
271 Code = CodeOp.getLiteralValue();
272 else {
273 if (CodeOp.getEncoding() == BitCodeAbbrevOp::Array ||
275 return error("Abbreviation starts with an Array or a Blob");
276 if (Expected<uint64_t> MaybeCode = readAbbreviatedField(*this, CodeOp))
277 Code = MaybeCode.get();
278 else
279 return MaybeCode.takeError();
280 }
281
282 for (unsigned i = 1, e = Abbv->getNumOperandInfos(); i != e; ++i) {
283 const BitCodeAbbrevOp &Op = Abbv->getOperandInfo(i);
284 if (Op.isLiteral()) {
285 Vals.push_back(Op.getLiteralValue());
286 continue;
287 }
288
289 if (Op.getEncoding() != BitCodeAbbrevOp::Array &&
290 Op.getEncoding() != BitCodeAbbrevOp::Blob) {
291 if (Expected<uint64_t> MaybeVal = readAbbreviatedField(*this, Op))
292 Vals.push_back(MaybeVal.get());
293 else
294 return MaybeVal.takeError();
295 continue;
296 }
297
298 if (Op.getEncoding() == BitCodeAbbrevOp::Array) {
299 // Array case. Read the number of elements as a vbr6.
300 Expected<uint32_t> MaybeNumElts = ReadVBR(6);
301 if (!MaybeNumElts)
302 return error(
303 ("Failed to read size: " + toString(MaybeNumElts.takeError()))
304 .c_str());
305 uint32_t NumElts = MaybeNumElts.get();
306 if (!isSizePlausible(NumElts))
307 return error("Size is not plausible");
308 Vals.reserve(Vals.size() + NumElts);
309
310 // Get the element encoding.
311 if (i + 2 != e)
312 return error("Array op not second to last");
313 const BitCodeAbbrevOp &EltEnc = Abbv->getOperandInfo(++i);
314 if (!EltEnc.isEncoding())
315 return error(
316 "Array element type has to be an encoding of a type");
317
318 // Read all the elements.
319 switch (EltEnc.getEncoding()) {
320 default:
321 return error("Array element type can't be an Array or a Blob");
323 for (; NumElts; --NumElts)
325 Read((unsigned)EltEnc.getEncodingData()))
326 Vals.push_back(MaybeVal.get());
327 else
328 return MaybeVal.takeError();
329 break;
331 for (; NumElts; --NumElts)
332 if (Expected<uint64_t> MaybeVal =
333 ReadVBR64((unsigned)EltEnc.getEncodingData()))
334 Vals.push_back(MaybeVal.get());
335 else
336 return MaybeVal.takeError();
337 break;
339 for (; NumElts; --NumElts)
341 Vals.push_back(BitCodeAbbrevOp::DecodeChar6(MaybeVal.get()));
342 else
343 return MaybeVal.takeError();
344 }
345 continue;
346 }
347
348 assert(Op.getEncoding() == BitCodeAbbrevOp::Blob);
349 // Blob case. Read the number of bytes as a vbr6.
350 Expected<uint32_t> MaybeNumElts = ReadVBR(6);
351 if (!MaybeNumElts)
352 return MaybeNumElts.takeError();
353 uint32_t NumElts = MaybeNumElts.get();
354 SkipToFourByteBoundary(); // 32-bit alignment
355
356 // Figure out where the end of this blob will be including tail padding.
357 size_t CurBitPos = GetCurrentBitNo();
358 const size_t NewEnd =
359 CurBitPos + static_cast<uint64_t>(alignTo(NumElts, 4)) * 8;
360
361 // Make sure the bitstream is large enough to contain the blob.
362 if (!canSkipToPos(NewEnd/8))
363 return error("Blob ends too soon");
364
365 // Otherwise, inform the streamer that we need these bytes in memory. Skip
366 // over tail padding first, in case jumping to NewEnd invalidates the Blob
367 // pointer.
368 if (Error Err = JumpToBit(NewEnd))
369 return Err;
370 const char *Ptr = (const char *)getPointerToBit(CurBitPos, NumElts);
371
372 // If we can return a reference to the data, do so to avoid copying it.
373 if (Blob) {
374 *Blob = StringRef(Ptr, NumElts);
375 } else {
376 // Otherwise, unpack into Vals with zero extension.
377 auto *UPtr = reinterpret_cast<const unsigned char *>(Ptr);
378 Vals.append(UPtr, UPtr + NumElts);
379 }
380 }
381
382 return Code;
383}
384
386 auto Abbv = std::make_shared<BitCodeAbbrev>();
387 Expected<uint32_t> MaybeNumOpInfo = ReadVBR(5);
388 if (!MaybeNumOpInfo)
389 return MaybeNumOpInfo.takeError();
390 unsigned NumOpInfo = MaybeNumOpInfo.get();
391 for (unsigned i = 0; i != NumOpInfo; ++i) {
392 Expected<word_t> MaybeIsLiteral = Read(1);
393 if (!MaybeIsLiteral)
394 return MaybeIsLiteral.takeError();
395 bool IsLiteral = MaybeIsLiteral.get();
396 if (IsLiteral) {
397 Expected<uint64_t> MaybeOp = ReadVBR64(8);
398 if (!MaybeOp)
399 return MaybeOp.takeError();
400 Abbv->Add(BitCodeAbbrevOp(MaybeOp.get()));
401 continue;
402 }
403
404 Expected<word_t> MaybeEncoding = Read(3);
405 if (!MaybeEncoding)
406 return MaybeEncoding.takeError();
407 if (!BitCodeAbbrevOp::isValidEncoding(MaybeEncoding.get()))
408 return error("Invalid encoding");
409
411 (BitCodeAbbrevOp::Encoding)MaybeEncoding.get();
413 Expected<uint64_t> MaybeData = ReadVBR64(5);
414 if (!MaybeData)
415 return MaybeData.takeError();
416 uint64_t Data = MaybeData.get();
417
418 // As a special case, handle fixed(0) (i.e., a fixed field with zero bits)
419 // and vbr(0) as a literal zero. This is decoded the same way, and avoids
420 // a slow path in Read() to have to handle reading zero bits.
421 if ((E == BitCodeAbbrevOp::Fixed || E == BitCodeAbbrevOp::VBR) &&
422 Data == 0) {
423 Abbv->Add(BitCodeAbbrevOp(0));
424 continue;
425 }
426
427 if ((E == BitCodeAbbrevOp::Fixed || E == BitCodeAbbrevOp::VBR) &&
429 return error("Fixed or VBR abbrev record with size > MaxChunkData");
430
431 Abbv->Add(BitCodeAbbrevOp(E, Data));
432 } else
433 Abbv->Add(BitCodeAbbrevOp(E));
434 }
435
436 if (Abbv->getNumOperandInfos() == 0)
437 return error("Abbrev record with no operands");
438 CurAbbrevs.push_back(std::move(Abbv));
439
440 return Error::success();
441}
442
444BitstreamCursor::ReadBlockInfoBlock(bool ReadBlockInfoNames) {
446 return Err;
447
448 BitstreamBlockInfo NewBlockInfo;
449
451 BitstreamBlockInfo::BlockInfo *CurBlockInfo = nullptr;
452
453 // Read all the records for this module.
454 while (true) {
455 Expected<BitstreamEntry> MaybeEntry =
457 if (!MaybeEntry)
458 return MaybeEntry.takeError();
459 BitstreamEntry Entry = MaybeEntry.get();
460
461 switch (Entry.Kind) {
462 case llvm::BitstreamEntry::SubBlock: // Handled for us already.
464 return std::nullopt;
466 return std::move(NewBlockInfo);
468 // The interesting case.
469 break;
470 }
471
472 // Read abbrev records, associate them with CurBID.
473 if (Entry.ID == bitc::DEFINE_ABBREV) {
474 if (!CurBlockInfo)
475 return std::nullopt;
476 if (Error Err = ReadAbbrevRecord())
477 return Err;
478
479 // ReadAbbrevRecord installs the abbrev in CurAbbrevs. Move it to the
480 // appropriate BlockInfo.
481 CurBlockInfo->Abbrevs.push_back(std::move(CurAbbrevs.back()));
482 CurAbbrevs.pop_back();
483 continue;
484 }
485
486 // Read a record.
487 Record.clear();
488 Expected<unsigned> MaybeBlockInfo = readRecord(Entry.ID, Record);
489 if (!MaybeBlockInfo)
490 return MaybeBlockInfo.takeError();
491 switch (MaybeBlockInfo.get()) {
492 default:
493 break; // Default behavior, ignore unknown content.
495 if (Record.size() < 1)
496 return std::nullopt;
497 CurBlockInfo = &NewBlockInfo.getOrCreateBlockInfo((unsigned)Record[0]);
498 break;
500 if (!CurBlockInfo)
501 return std::nullopt;
502 if (!ReadBlockInfoNames)
503 break; // Ignore name.
504 CurBlockInfo->Name = std::string(Record.begin(), Record.end());
505 break;
506 }
508 if (!CurBlockInfo)
509 return std::nullopt;
510 if (!ReadBlockInfoNames)
511 break; // Ignore name.
512 CurBlockInfo->RecordNames.emplace_back(
513 (unsigned)Record[0], std::string(Record.begin() + 1, Record.end()));
514 break;
515 }
516 }
517 }
518}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static Expected< uint64_t > readAbbreviatedField(BitstreamCursor &Cursor, const BitCodeAbbrevOp &Op)
#define error(X)
BitCodeAbbrevOp - This describes one or more operands in an abbreviation.
Definition BitCodes.h:34
uint64_t getLiteralValue() const
Definition BitCodes.h:64
static bool isValidEncoding(uint64_t E)
Definition BitCodes.h:52
bool hasEncodingData() const
Definition BitCodes.h:73
bool isLiteral() const
Definition BitCodes.h:60
bool isEncoding() const
Definition BitCodes.h:61
Encoding getEncoding() const
Definition BitCodes.h:67
static char DecodeChar6(unsigned V)
Definition BitCodes.h:98
uint64_t getEncodingData() const
Definition BitCodes.h:68
BitCodeAbbrev - This class represents an abbreviation record.
Definition BitCodes.h:109
unsigned getNumOperandInfos() const
Definition BitCodes.h:118
const BitCodeAbbrevOp & getOperandInfo(unsigned N) const
Definition BitCodes.h:121
This class maintains the abbreviations read from a block info block.
BlockInfo & getOrCreateBlockInfo(unsigned BlockID)
This represents a position within a bitcode file, implemented on top of a SimpleBitstreamCursor.
LLVM_ABI Error ReadAbbrevRecord()
uint64_t GetCurrentBitNo() const
Return the bit # of the bit we are reading.
Expected< uint64_t > ReadVBR64(const unsigned NumBits)
static const size_t MaxChunkSize
Expected< BitstreamEntry > advanceSkippingSubblocks(unsigned Flags=0)
This is a convenience function for clients that don't expect any subblocks.
Expected< const BitCodeAbbrev * > getAbbrev(unsigned AbbrevID)
Return the abbreviation for the specified AbbrevId.
LLVM_ABI Expected< unsigned > readRecord(unsigned AbbrevID, SmallVectorImpl< uint64_t > &Vals, StringRef *Blob=nullptr)
LLVM_ABI Error EnterSubBlock(unsigned BlockID, unsigned *NumWordsP=nullptr)
Having read the ENTER_SUBBLOCK abbrevid, and enter the block.
LLVM_ABI Expected< unsigned > skipRecord(unsigned AbbrevID)
Read the current record and discard it, returning the code for the record.
@ AF_DontAutoprocessAbbrevs
If this flag is used, abbrev entries are returned just like normal records.
void skipToEnd()
Skip to the end of the file.
LLVM_ABI Expected< std::optional< BitstreamBlockInfo > > ReadBlockInfoBlock(bool ReadBlockInfoNames=false)
Read and return a block info block from the bitstream.
Error JumpToBit(uint64_t NewBitNo)
Reset the stream to the specified bit number.
Expected< uint32_t > ReadVBR(const unsigned NumBits)
bool canSkipToPos(size_t pos) const
Lightweight error class with error context and mandatory checking.
Definition Error.h:159
static ErrorSuccess success()
Create a success value.
Definition Error.h:336
Tagged union holding either a T or a Error.
Definition Error.h:485
Error takeError()
Take ownership of the stored error.
Definition Error.h:612
reference get()
Returns a reference to the stored T value.
Definition Error.h:582
LLVM_ABI Expected< word_t > readSlow(unsigned NumBits)
Read NumBits bits that don't fit in a word load from the current byte, or are near the end of the str...
const uint8_t * getPointerToBit(uint64_t BitNo, uint64_t NumBytes)
Get a pointer into the bitstream at the specified bit offset.
size_t word_t
The type of the values returned by Read.
bool isSizePlausible(size_t Size) const
Check whether a reservation of Size elements is plausible.
uint64_t sizeInBits() const
Return the size of the stream in bits.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void reserve(size_type N)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Represent a constant reference to a string, i.e.
Definition StringRef.h:56
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ BLOCKINFO_CODE_BLOCKNAME
@ BLOCKINFO_CODE_SETRECORDNAME
@ BLOCKINFO_CODE_SETBID
@ BLOCKINFO_BLOCK_ID
BLOCKINFO_BLOCK is used to define metadata about blocks, for example, standard abbrevs that should be...
@ DEFINE_ABBREV
DEFINE_ABBREV - Defines an abbrev for the current block.
value_type readAtBitAlignment(const void *memory, uint64_t startBit)
Read a value of a particular endianness from memory, for a location that starts at the given bit offs...
Definition Endian.h:110
This is an optimization pass for GlobalISel generic memory operations.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition STLExtras.h:2229
Error createStringError(std::error_code EC, char const *Fmt, const Ts &... Vals)
Create formatted StringError object.
Definition Error.h:1321
constexpr uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition Alignment.h:149
DWARFExpression::Operation Op
std::string toString(const APInt &I, unsigned Radix, bool Signed, bool formatAsCLiteral=false, bool UpperCase=true, bool InsertSeparators=false)
This contains information emitted to BLOCKINFO_BLOCK blocks.
std::vector< std::pair< unsigned, std::string > > RecordNames
std::vector< std::shared_ptr< BitCodeAbbrev > > Abbrevs
When advancing through a bitstream cursor, each advance can discover a few different kinds of entries...