Spicy
stream.h
1 // Copyright (c) 2020-2021 by the Zeek Project. See LICENSE for details.
2 
3 #pragma once
4 
5 #include <algorithm>
6 #include <array>
7 #include <cassert>
8 #include <cinttypes>
9 #include <cstddef>
10 #include <cstring>
11 #include <memory>
12 #include <optional>
13 #include <string>
14 #include <tuple>
15 #include <utility>
16 #include <variant>
17 #include <vector>
18 
19 #include <hilti/rt/any.h>
20 #include <hilti/rt/exception.h>
21 #include <hilti/rt/intrusive-ptr.h>
22 #include <hilti/rt/logging.h>
23 #include <hilti/rt/result.h>
24 #include <hilti/rt/safe-int.h>
25 #include <hilti/rt/types/bytes.h>
26 #include <hilti/rt/types/time.h>
27 #include <hilti/rt/types/vector.h>
28 #include <hilti/rt/util.h>
29 
30 namespace hilti::rt {
31 
32 class Stream;
33 
34 namespace stream {
35 class View;
36 class SafeConstIterator;
37 
38 namespace detail {
40 }
41 } // namespace stream
42 
43 namespace detail::adl {
44 std::string to_string(const Stream& x, adl::tag /*unused*/);
45 std::string to_string(const stream::View& x, adl::tag /*unused*/);
46 std::string to_string(const stream::SafeConstIterator& x, adl::tag /*unused*/);
47 std::string to_string(const stream::detail::UnsafeConstIterator& x, adl::tag /*unused*/);
48 } // namespace detail::adl
49 
50 namespace stream {
52 using Byte = uint8_t;
53 
55 using Offset = integer::safe<uint64_t>;
56 
58 using Size = integer::safe<uint64_t>;
59 
61 enum class Direction : int64_t { Forward, Backward };
62 
63 namespace detail {
64 
65 class Chain;
69 
70 // Represents a gap of length `size`.
71 struct Gap {
72  size_t size;
73 };
74 
87 class Chunk {
88 public:
89  static const int SmallBufferSize = 32;
90  using Array = std::pair<Size, std::array<Byte, SmallBufferSize>>;
91  using Vector = std::vector<Byte>;
92 
93  Chunk(Offset o, std::array<Byte, SmallBufferSize> d, Size n) : _offset(o), _data(std::make_pair(n, d)) {}
94  Chunk(Offset o, Vector&& d) : _offset(o), _data(std::move(d)) {}
95  Chunk(Offset o, const View& d);
96  Chunk(Offset o, const std::string& s);
97 
98  template<int N>
99  Chunk(Offset o, std::array<Byte, N> d) : Chunk(_fromArray(o, std::move(d))) {}
100  Chunk(Offset o, const char* d, Size n) : Chunk(_fromArray(o, d, n)) {}
101 
102  // Constructs a gap chunk which signifies empty data.
103  Chunk(Offset o, size_t len) : _offset(o), _data(Gap{len}) {}
104 
105  Chunk(const Chunk& other) : _offset(other._offset), _data(other._data) {}
106  Chunk(Chunk&& other) noexcept
107  : _offset(other._offset), _data(std::move(other._data)), _next(std::move(other._next)) {}
108 
109  Chunk& operator=(const Chunk& other) = delete;
110 
111  Chunk& operator=(Chunk&& other) noexcept {
112  _offset = other._offset;
113  _data = std::move(other._data);
114  _next = std::move(other._next);
115  _chain = other._chain;
116  return *this;
117  }
118 
119  ~Chunk() = default;
120 
121  Offset offset() const { return _offset; }
122  Offset endOffset() const { return _offset + size(); }
123  bool isGap() const { return std::holds_alternative<Gap>(_data); }
124  bool inRange(Offset offset) const { return offset >= _offset && offset < endOffset(); }
125 
126  const Byte* data() const {
127  if ( auto a = std::get_if<Array>(&_data) )
128  return a->second.data();
129  else if ( auto a = std::get_if<Vector>(&_data) ) {
130  return a->data();
131  }
132  else if ( auto a = std::get_if<Gap>(&_data) )
133  throw MissingData("data is missing");
134 
136  }
137 
138  const Byte* data(Offset offset) const {
139  assert(inRange(offset));
140  return data() + (offset - _offset).Ref();
141  }
142 
143  const Byte* endData() const {
144  if ( auto a = std::get_if<Array>(&_data) )
145  return a->second.data() + a->first.Ref();
146  else if ( auto a = std::get_if<Vector>(&_data) ) {
147  return a->data() + a->size();
148  }
149  else if ( auto a = std::get_if<Gap>(&_data) )
150  throw MissingData("data is missing");
151 
153  }
154 
155  Size size() const {
156  if ( auto a = std::get_if<Array>(&_data) )
157  return a->first;
158  else if ( auto a = std::get_if<Vector>(&_data) )
159  return a->size();
160  else if ( auto a = std::get_if<Gap>(&_data) )
161  return a->size;
162 
164  }
165 
166  bool isLast() const { return ! _next; }
167  const Chunk* next() const { return _next.get(); }
168 
169  auto last() const {
170  const Chunk* i = this;
171  while ( i && i->_next )
172  i = i->_next.get();
173  return i;
174  }
175 
176  auto last() {
177  Chunk* i = this;
178  while ( i && i->_next )
179  i = i->_next.get();
180  return i;
181  }
182 
183  void debugPrint(std::ostream& out) const;
184 
185 protected:
186  // All mutating functions are protected and are expected to be called
187  // only from chain so that it can track any changes.
188  friend class Chain;
189 
190  void trim(Offset o);
191 
192  // Update offset for current chunk and all others linked from it.
193  void setOffset(Offset o) {
194  auto c = this;
195  while ( c ) {
196  c->_offset = o;
197  o += c->size();
198  c = c->next();
199  }
200  }
201 
202  // Set chain for current chunk and all others linked from it.
203  void setChain(const Chain* chain) {
204  auto x = this;
205  while ( x ) {
206  x->_chain = chain;
207  x = x->_next.get();
208  }
209  }
210 
211  Chunk* next() { return _next.get(); }
212 
213  // Link in chunk as successor of current one. Updates offset/chain for
214  // the appended chunk and all its successors.
215  void setNext(std::unique_ptr<Chunk> next) {
216  assert(_chain);
217 
218  Offset offset = endOffset();
219  _next = std::move(next);
220 
221  auto c = _next.get();
222  while ( c ) {
223  c->_offset = offset;
224  c->_chain = _chain;
225  offset += c->size();
226  c = c->_next.get();
227  }
228  }
229 
230  void clearNext() { _next = nullptr; }
231 
232 private:
233  inline Chunk _fromArray(Offset o, const char* d, Size n) {
234  auto ud = reinterpret_cast<const Byte*>(d);
235 
236  if ( n <= Chunk::SmallBufferSize ) {
237  std::array<Byte, Chunk::SmallBufferSize> x{};
238  std::copy(ud, ud + n.Ref(), x.data());
239  return Chunk(o, x, n);
240  }
241 
242  return Chunk(o, Chunk::Vector(ud, ud + n.Ref()));
243  }
244 
245  Offset _offset = 0; // global offset of 1st byte
246  std::variant<Array, Vector, Gap> _data; // content of this chunk
247  const Chain* _chain = nullptr; // chain this chunk is part of, or null if not linked to a chain yet (non-owning;
248  // will stay valid at least as long as the current chunk does)
249  std::unique_ptr<Chunk> _next = nullptr; // next chunk in chain, or null if last
250 };
251 
259 public:
262  using Size = stream::Size;
263 
264  Chain() {}
265 
267  Chain(std::unique_ptr<Chunk> head) : _head(std::move(head)), _tail(_head->last()) { _head->setChain(this); }
268 
269  Chain(Chain&& other) = delete;
270  Chain(const Chain& other) = delete;
271  Chain& operator=(const Chain& other) = delete;
272  Chain& operator=(const Chain&& other) = delete;
273 
274  const Chunk* head() const { return _head.get(); }
275  const Chunk* tail() const { return _tail; }
276  Size size() const { return (endOffset() - offset()).Ref(); }
277  bool isFrozen() const { return _state == State::Frozen; }
278  bool isValid() const { return _state != State::Invalid; }
279  bool inRange(Offset o) const { return o >= offset() && o < endOffset(); }
280 
281  Offset offset() const { return _head_offset; }
282  Offset endOffset() const { return _tail ? _tail->endOffset() : _head_offset; }
283 
284  // Finds the chunk containing *offset*. Returns null if not found.
285  // *hint_prev* may point to a chunk chained in before the target chunk,
286  // allowing that to be found more quickly. If given, *hint_prev* must be
287  // pointing to a current chunk of the chain, but it's ok if it's
288  // non-helpful for finding the target (i.e., pointing to a later chunk).
289  const Chunk* findChunk(Offset offset, const Chunk* hint_prev = nullptr) const;
290  Chunk* findChunk(Offset offset, Chunk* hint_prev = nullptr);
291 
292  // Returns a pointer to the byte at a given offset. Returns null if
293  // offset is out of range. See find() for semantics of *hint_prev*.
294  const Byte* data(Offset offset, Chunk* hint_prev = nullptr) const;
295 
296  SafeConstIterator begin() const;
297  SafeConstIterator end() const;
298  SafeConstIterator at(Offset offset) const;
299  UnsafeConstIterator unsafeBegin() const;
300  UnsafeConstIterator unsafeEnd() const;
301 
302  // Returns a newly allocated chain with the same content.
303  ChainPtr deepCopy() const;
304 
306  void append(std::unique_ptr<Chunk> chunk);
307  void append(Chain&& other);
308 
309  void trim(Offset offset);
310  void trim(const SafeConstIterator& i);
311  void trim(const UnsafeConstIterator& i);
312 
313  // Turns the chain into invalidated state, whill releases all chunks and
314  // will let attempts to dereference any still existing iterators fail.
315  void invalidate() {
316  _state = State::Invalid;
317  _head.reset();
318  _head_offset = 0;
319  _tail = nullptr;
320  }
321 
322  // Turns the chain into a freshly initialized state.
323  void reset() {
324  _state = State::Mutable;
325  _head.reset();
326  _head_offset = 0;
327  _tail = nullptr;
328  }
329 
330  void freeze() {
331  if ( isValid() )
332  _state = State::Frozen;
333  }
334  void unfreeze() {
335  if ( isValid() )
336  _state = State::Mutable;
337  }
338 
339  // Returns the number of dynamic chunks allocated.
340  int numberOfChunks() const;
341 
342 private:
343  void _ensureValid() const {
344  if ( ! isValid() )
345  throw InvalidIterator("stream object no longer available");
346  }
347 
348  void _ensureMutable() const {
349  if ( isFrozen() )
350  throw Frozen("stream object can no longer be modified");
351  }
352 
353  enum class State {
354  Mutable, // content can be expanded an trimmed
355  Frozen, // content cannot be changed
356  Invalid, // parent stream object has been destroyed, all content is invalid
357  };
358 
359  // Current state of chain
360  State _state = State::Mutable;
361 
362  // First chunk, or null if chain is empty.
363  std::unique_ptr<Chunk> _head = nullptr;
364 
365  // Offset of the beginning of chain. If head is set, this offset will
366  // match that of head. If head is not set, it'll contain the most recent
367  // end offset of the main (that's zero initially, but may be non-zero
368  // after trimming off all chunks).
369  Offset _head_offset = 0;
370 
371  // Always pointing to last chunk reachable from *head*, or null if chain
372  // is empty; non-owning
373  Chunk* _tail = nullptr;
374 };
375 
376 } // namespace detail
377 
392 public:
393  using Byte = stream::Byte;
397  using Offset = stream::Offset;
398  using Size = stream::Size;
400 
402  SafeConstIterator() = default;
403 
405  explicit SafeConstIterator(const UnsafeConstIterator& i);
406 
408  Offset offset() const { return _offset; }
409 
411  bool isFrozen() const { return ! _chain || _chain->isFrozen(); }
412 
414  auto& operator++() {
415  _increment(1);
416  return *this;
417  }
418 
420  const auto operator++(int) {
421  auto x = *this;
422  _increment(1);
423  return x;
424  }
425 
427  auto& operator+=(integer::safe<uint64_t> i) {
428  _increment(i);
429  return *this;
430  }
431 
433  auto& operator--() {
434  _decrement(1);
435  return *this;
436  }
437 
439  const auto operator--(int) {
440  auto x = *this;
441  _decrement(1);
442  return x;
443  }
444 
446  auto& operator-=(integer::safe<uint64_t> i) {
447  _decrement(i);
448  return *this;
449  }
450 
452  auto operator*() const { return _dereference(); }
453 
455  auto operator+(integer::safe<uint64_t> i) const {
456  auto x = *this;
457  x._increment(i);
458  return x;
459  }
460 
462  auto operator-(integer::safe<uint64_t> i) const {
463  auto x = *this;
464  x._decrement(i);
465  return x;
466  }
467 
473  integer::safe<int64_t> operator-(const SafeConstIterator& other) const {
474  _ensureSameChain(other);
475  return static_cast<int64_t>(_offset) - static_cast<int64_t>(other._offset);
476  }
477 
483  bool operator==(const SafeConstIterator& other) const {
484  _ensureSameChain(other);
485  return (_offset == other._offset) || (isEnd() && other.isEnd());
486  }
487 
493  bool operator!=(const SafeConstIterator& other) const {
494  _ensureSameChain(other);
495  return ! (*this == other);
496  }
497 
499  bool operator<(const SafeConstIterator& other) const {
500  _ensureSameChain(other);
501  return offset() < other.offset();
502  }
503 
505  bool operator<=(const SafeConstIterator& other) const {
506  _ensureSameChain(other);
507  return offset() <= other.offset();
508  }
509 
511  bool operator>(const SafeConstIterator& other) const {
512  _ensureSameChain(other);
513  return offset() > other.offset();
514  }
515 
517  bool operator>=(const SafeConstIterator& other) const {
518  _ensureSameChain(other);
519  return offset() >= other.offset();
520  }
521 
523  explicit operator bool() const { return ! isUnset(); }
524 
525  std::ostream& operator<<(std::ostream& out) const {
526  out << to_string(*this);
527  return out;
528  }
529 
531  bool isUnset() const { return ! _chain; }
532 
537  bool isExpired() const {
538  if ( ! _chain )
539  return false;
540 
541  return ! _chain->isValid();
542  }
543 
548  bool isValid() const { return ! isUnset() && ! isExpired(); }
549 
555  bool isEnd() const {
556  if ( ! _chain )
557  return true;
558 
559  _ensureValidChain();
560  return _offset >= _chain->endOffset();
561  }
562 
567  void debugPrint(std::ostream& out) const;
568 
569 protected:
570  friend class hilti::rt::stream::View;
573 
574  // Returns the chunk only if it's a valid pointer, other null. See
575  // comment on `_chunk` validity below.
576  const Chunk* chunk() const { return _chain && _chain->isValid() && _chain->inRange(_offset) ? _chunk : nullptr; }
577  const Chain* chain() const { return _chain.get(); }
578 
579 private:
580  SafeConstIterator(ConstChainPtr chain, Offset offset, const Chunk* chunk)
581  : _chain(std::move(chain)), _offset(offset), _chunk(chunk) {
582  assert(! isUnset());
583  }
584 
585  void _ensureValidChain() const {
586  // This must have been checked at this point already.
587  assert(_chain);
588 
589  if ( ! _chain->isValid() )
590  throw InvalidIterator("stream object no longer available");
591  }
592 
593  void _ensureSameChain(const SafeConstIterator& other) const {
594  if ( ! (_chain && other._chain) )
595  // One is the default constructed end iterator; that's ok.
596  return;
597 
598  if ( ! other.isValid() )
599  throw InvalidIterator("stream object no longer available");
600 
601  if ( _chain != other._chain )
602  throw InvalidIterator("incompatible iterators");
603  }
604 
605  void _increment(integer::safe<uint64_t> n) {
606  if ( ! _chain )
607  throw InvalidIterator("unbound stream iterator");
608 
609  if ( ! n )
610  return;
611 
612  _offset += n;
613 
614  if ( ! (_chain && _chain->isValid()) )
615  return; // will be caught when dereferenced
616 
617  _chunk = _chain->findChunk(_offset, chunk());
618  // chunk will be null if we're pointing beyond the end.
619  }
620 
621  void _decrement(integer::safe<uint64_t> n) {
622  if ( ! _chain )
623  throw InvalidIterator("unbound stream iterator");
624 
625  if ( n > _offset )
626  throw InvalidIterator("attempt to move before beginning of stream");
627 
628  if ( ! n )
629  return;
630 
631  _offset -= n;
632 
633  if ( _chunk && _offset > _chunk->offset() )
634  return; // fast-path, chunk still valid
635 
636  if ( ! (_chain && _chain->isValid()) )
637  return; // will be caught when dereferenced
638 
639  _chunk = _chain->findChunk(_offset, _chunk);
640  // chunk will be null if we're pointing beyond the beginning.
641  }
642 
643  Byte _dereference() const {
644  if ( ! _chain )
645  throw InvalidIterator("unbound stream iterator");
646 
647  _ensureValidChain();
648 
649  if ( ! _chain->inRange(_offset) )
650  throw InvalidIterator("stream iterator outside of valid range");
651 
652  auto c = _chain->findChunk(_offset, chunk());
653  assert(c);
654 
655  if ( c->isGap() )
656  throw MissingData("data is missing");
657 
658  return *c->data(_offset);
659  }
660 
661  // Parent chain if bound, or null if not. The parent will stay around for
662  // at least as long as this iterator.
663  ConstChainPtr _chain = nullptr;
664 
665  // Global offset inside parent chain. This can be pointing to anywhere
666  // inside the stream's sequence space, including potentially being
667  // outside of the chain's valid range. It may always be accessed, even if
668  // the iterator is unbound, or the chain not valid anymore; it will then
669  // generally reflect the most recent value, which may or may not
670  // semantically make sense.
671  Offset _offset = 0;
672 
673  // A chunk from which *_offset* is reachable (i.e., the chunk either
674  // contains the offset, or we can get to the right chunk by following its
675  // successors). The chunk is null if our current offset is outside of the
676  // chains valid range.
677  //
678  // This chunk pointer is only valid for access if (1) *_chain* is set and
679  // valid; and (2) _offset is inside the chain's valid range. It will then
680  // point to a chunk from which _offset is *reachable*. (If these two are
681  // not satisfied, the chunk may be pointing into freed memory!)
682  const Chunk* _chunk = nullptr;
683 };
684 
685 inline std::ostream& operator<<(std::ostream& out, const SafeConstIterator& x) {
686  out << to_string(x);
687  return out;
688 }
689 
700 namespace detail {
701 
703 public:
704  using Byte = stream::Byte;
708  using Offset = stream::Offset;
709  using Size = stream::Size;
710 
712  UnsafeConstIterator() = default;
713 
715  explicit UnsafeConstIterator(const SafeConstIterator& i);
716 
718  Offset offset() const { return _offset; }
719 
721  bool isFrozen() const { return ! _chain || _chain->isFrozen(); }
722 
724  auto& operator++() {
725  _increment(1);
726  return *this;
727  }
728 
730  const auto operator++(int) {
731  auto x = *this;
732  _increment(1);
733  return x;
734  }
735 
737  auto& operator--() {
738  _decrement(1);
739  return *this;
740  }
741 
743  const auto operator--(int) {
744  auto x = *this;
745  _decrement(1);
746  return x;
747  }
748 
750  auto& operator-=(integer::safe<uint64_t> i) {
751  _decrement(i);
752  return *this;
753  }
754 
756  auto operator*() const { return _dereference(); }
757 
759  auto operator+(integer::safe<uint64_t> i) const {
760  auto x = *this;
761  x._increment(i);
762  return x;
763  }
764 
766  auto operator-(integer::safe<uint64_t> i) const {
767  auto x = *this;
768  x._decrement(i);
769  return x;
770  }
771 
777  integer::safe<int64_t> operator-(const UnsafeConstIterator& other) const {
778  return static_cast<int64_t>(_offset) - static_cast<int64_t>(other._offset);
779  }
780 
786  bool operator==(const UnsafeConstIterator& other) const {
787  return (_offset == other._offset) || (isEnd() && other.isEnd());
788  }
789 
795  bool operator!=(const UnsafeConstIterator& other) const { return ! (*this == other); }
796 
798  bool operator<(const UnsafeConstIterator& other) const { return offset() < other.offset(); }
799 
801  bool operator<=(const UnsafeConstIterator& other) const { return offset() <= other.offset(); }
802 
804  bool operator>(const UnsafeConstIterator& other) const { return offset() > other.offset(); }
805 
807  bool operator>=(const UnsafeConstIterator& other) const { return offset() >= other.offset(); }
808 
810  explicit operator bool() const { return ! isUnset(); }
811 
812  std::ostream& operator<<(std::ostream& out) const {
813  out << to_string(*this);
814  return out;
815  }
816 
818  bool isUnset() const { return ! _chain; }
819 
824  bool isExpired() const {
825  if ( ! _chain )
826  return false;
827 
828  return ! _chain->isValid();
829  }
830 
835  bool isValid() const { return ! isUnset() && ! isExpired(); }
836 
838  bool isEnd() const {
839  if ( ! _chain )
840  return true;
841 
842  return _offset >= _chain->endOffset();
843  }
844 
849  void debugPrint(std::ostream& out) const;
850 
851 protected:
852  friend class hilti::rt::stream::View;
855 
856  const Chunk* chunk() const { return _chunk; }
857  const Chain* chain() const { return _chain; }
858 
859 private:
860  UnsafeConstIterator(const ConstChainPtr& chain, Offset offset, const Chunk* chunk)
861  : _chain(chain.get()), _offset(offset), _chunk(chunk) {
862  assert(! isUnset());
863  }
864 
865  UnsafeConstIterator(const Chain* chain, Offset offset, const Chunk* chunk)
866  : _chain(chain), _offset(offset), _chunk(chunk) {
867  assert(! isUnset());
868  }
869 
870  void _increment(integer::safe<uint64_t> n) {
871  _offset += n;
872 
873  if ( _chunk && _offset < _chunk->endOffset() )
874  return; // fast-path, chunk still valid
875 
876  _chunk = _chain->findChunk(_offset, _chunk);
877  }
878 
879  void _decrement(integer::safe<uint64_t> n) {
880  _offset -= n;
881 
882  if ( _chunk && _offset > _chunk->offset() )
883  return; // fast-path, chunk still valid
884 
885  _chunk = _chain->findChunk(_offset, _chunk);
886  }
887 
888  Byte _dereference() const {
889  // TODO(bbannier): Ideally we would `assert(_chunk)` here so clang-tidy
890  // knows that `_chunk` is always not null. Unfortunately it looks like
891  // that fails to it pruning that CFG edge so we have to return instead
892  // here. This should be inconsequential to users as this function must
893  // not be called if the data is invalid.
894  if ( ! _chunk )
895  internalError("dereference of invalid iterator");
896 
897  auto* byte = _chunk->data(_offset);
898 
899  if ( ! byte )
900  throw MissingData("data is missing");
901 
902  return *byte;
903  }
904 
905  // Parent chain if bound, or null if not. This is a raw, non-owning
906  // pointer that assumes the parent chain will stick around as long as
907  // needed.
908  const Chain* _chain = nullptr;
909 
910  // Global offset inside parent chain. This can be pointing to anywhere
911  // inside the stream's sequence space, including potentially being
912  // outside of the chain's valid range.
913  Offset _offset = 0;
914 
915  // The chunk containing the current offset, or null if offset is out of
916  // bounds. This a raw, non-owning pointer that assumes the chunk will
917  // stick around as long as needed.
918  const Chunk* _chunk = nullptr;
919 };
920 
922  : _chain(i.chain()), _offset(i.offset()), _chunk(i.chain() ? i.chain()->findChunk(_offset, i.chunk()) : nullptr) {}
923 
924 inline std::ostream& operator<<(std::ostream& out, const UnsafeConstIterator& x) {
925  out << to_string(x);
926  return out;
927 }
928 
929 template<int N>
930 inline UnsafeConstIterator _extract(Byte* dst, const UnsafeConstIterator& i) {
931  *dst = *i;
932  return _extract<N - 1>(dst + 1, i + 1);
933 }
934 
935 template<>
936 inline UnsafeConstIterator _extract<0>(Byte* /* dst */, const UnsafeConstIterator& i) {
937  return i;
938 }
939 
940 template<int N>
941 inline UnsafeConstIterator extract(Byte* dst, const UnsafeConstIterator& i, const UnsafeConstIterator& end) {
942  if ( end.offset() - i.offset() < N )
943  throw WouldBlock("end of stream view");
944 
945  return _extract<N>(dst, i);
946 }
947 
948 inline SafeConstIterator Chain::begin() const {
949  _ensureValid();
950  return {ConstChainPtr(intrusive_ptr::NewRef(), this), offset(), _head.get()};
951 }
952 
953 inline SafeConstIterator Chain::end() const {
954  _ensureValid();
955  return {ConstChainPtr(intrusive_ptr::NewRef(), this), endOffset(), _tail};
956 }
957 
958 inline SafeConstIterator Chain::at(Offset offset) const {
959  return {ConstChainPtr(intrusive_ptr::NewRef(), this), offset, findChunk(offset)};
960 }
961 
962 inline UnsafeConstIterator Chain::unsafeBegin() const {
963  _ensureValid();
964  return {ConstChainPtr(intrusive_ptr::NewRef(), this), offset(), _head.get()};
965 }
966 inline UnsafeConstIterator Chain::unsafeEnd() const {
967  _ensureValid();
968  return {ConstChainPtr(intrusive_ptr::NewRef(), this), endOffset(), _tail};
969 }
970 
971 inline void Chain::trim(const SafeConstIterator& i) {
972  if ( ! i.chain() ) {
973  // Unbound end operator, trim all content off.
974  trim(endOffset());
975  return;
976  }
977 
978  if ( i.chain() != this )
979  throw InvalidIterator("incompatible iterator");
980 
981  if ( ! i.isValid() )
982  throw InvalidIterator("stream object no longer available");
983 
984  trim(i.offset());
985 }
986 
987 inline void Chain::trim(const UnsafeConstIterator& i) { trim(i.offset()); }
988 
989 } // namespace detail
990 
992  : _chain(detail::ConstChainPtr(intrusive_ptr::NewRef(), i._chain)), _offset(i._offset), _chunk(i._chunk) {}
993 
1001 class View {
1002 public:
1003  using Byte = stream::Byte;
1004  using Chain = stream::detail::Chain;
1006  using Chunk = stream::detail::Chunk;
1007  using Offset = stream::Offset;
1008  using Size = stream::Size;
1010 
1012  View() = default;
1013 
1015  virtual ~View();
1016 
1018  explicit View(SafeConstIterator begin, SafeConstIterator end) : _begin(std::move(begin)), _end(std::move(end)) {
1019  _ensureValid();
1020 
1021  if ( ! _end->_chain )
1022  _end = _begin.chain()->end();
1023  else
1024  _ensureSameChain(*_end);
1025  }
1026 
1032  explicit View(SafeConstIterator begin) : _begin(std::move(begin)) {}
1033 
1038  Offset offset() const { return _begin.offset(); }
1039 
1045  Size size() const;
1046 
1048  bool isEmpty() const { return size() == 0; }
1049 
1051  bool isFrozen() const { return _begin.isFrozen(); }
1052 
1058  bool isOpenEnded() const { return ! _end.has_value(); }
1059 
1066  SafeConstIterator find(Byte b) const {
1067  _ensureValid();
1068  return SafeConstIterator(find(b, UnsafeConstIterator()));
1069  }
1070 
1078  SafeConstIterator find(Byte b, const SafeConstIterator& n) const {
1079  _ensureValid();
1080  _ensureSameChain(n);
1081  return SafeConstIterator(find(b, UnsafeConstIterator(n)));
1082  }
1083 
1091  UnsafeConstIterator find(Byte b, UnsafeConstIterator n) const;
1092 
1102  std::tuple<bool, SafeConstIterator> find(const View& v) const {
1103  _ensureValid();
1104  auto x = find(v, UnsafeConstIterator());
1105  return std::make_tuple(std::get<0>(x), SafeConstIterator(std::get<1>(x)));
1106  }
1107 
1118  std::tuple<bool, SafeConstIterator> find(const View& v, const SafeConstIterator& n) const {
1119  _ensureValid();
1120  _ensureSameChain(n);
1121  auto x = find(v, UnsafeConstIterator(n));
1122  return std::make_tuple(std::get<0>(x), SafeConstIterator(std::get<1>(x)));
1123  }
1124 
1135  std::tuple<bool, UnsafeConstIterator> find(const View& v, UnsafeConstIterator n) const;
1136 
1147  std::tuple<bool, SafeConstIterator> find(const Bytes& v, Direction d = Direction::Forward) const {
1148  _ensureValid();
1149  auto i = (d == Direction::Forward ? unsafeBegin() : unsafeEnd());
1150  auto x = find(v, std::move(i), d);
1151  return std::make_tuple(std::get<0>(x), SafeConstIterator(std::get<1>(x)));
1152  }
1153 
1165  std::tuple<bool, SafeConstIterator> find(const Bytes& v, const SafeConstIterator& n,
1166  Direction d = Direction::Forward) const {
1167  _ensureValid();
1168  _ensureSameChain(n);
1169  auto x = find(v, UnsafeConstIterator(n), d);
1170  return std::make_tuple(std::get<0>(x), SafeConstIterator(std::get<1>(x)));
1171  }
1172 
1184  std::tuple<bool, UnsafeConstIterator> find(const Bytes& v, UnsafeConstIterator n,
1185  Direction d = Direction::Forward) const {
1186  if ( d == Direction::Forward )
1187  return _findForward(v, std::move(n));
1188  else
1189  return _findBackward(v, std::move(n));
1190  }
1191 
1199  _ensureSameChain(i);
1200  return View(std::move(i), _end);
1201  }
1202 
1208  View advance(integer::safe<uint64_t> i) const { return View(begin() + i, _end); }
1209 
1213  View advanceToNextData() const;
1214 
1222  _ensureSameChain(from);
1223  _ensureSameChain(to);
1224  return View(std::move(from), std::move(to));
1225  }
1226 
1234  _ensureSameChain(to);
1235  return View(begin(), std::move(to));
1236  }
1237 
1244  View sub(Offset from, Offset to) const { return View(begin() + from, begin() + to); }
1245 
1252  View sub(Offset to) const { return View(begin(), begin() + to); }
1253 
1255  SafeConstIterator at(Offset offset) const { return begin() + (offset - begin().offset()); }
1256 
1262  View trim(const SafeConstIterator& nbegin) const {
1263  _ensureSameChain(nbegin);
1264 
1265  if ( ! _end )
1266  return View(nbegin);
1267 
1268  if ( nbegin.offset() > _end->offset() )
1269  return View(*_end, *_end);
1270 
1271  return View(nbegin, *_end);
1272  }
1273 
1279  View limit(Offset incr) const { return View(begin(), begin() + incr); }
1280 
1288  template<int N>
1289  View extract(Byte (&dst)[N]) const {
1290  _ensureValid();
1291  return View(SafeConstIterator(detail::extract<N>(dst, unsafeBegin(), unsafeEnd())), _end);
1292  }
1293 
1300  void copyRaw(Byte* dst) const;
1301 
1303  Bytes data() const;
1304 
1306  std::string dataForPrint() const;
1307 
1310 
1313 
1315  const SafeConstIterator& begin() const { return _begin; }
1316 
1319  assert(_begin.chain());
1320  return _end ? *_end : _begin.chain()->end();
1321  }
1322 
1324  struct Block {
1325  const Byte* start;
1326  uint64_t size;
1327  uint64_t offset;
1328  bool is_first;
1329  bool is_last;
1331  };
1332 
1336  std::optional<Block> firstBlock() const;
1337 
1341  std::optional<Block> nextBlock(std::optional<Block> current) const;
1342 
1347  bool startsWith(const Bytes& b) const;
1348 
1349  bool operator==(const Bytes& other) const;
1350  bool operator==(const Stream& other) const;
1351  bool operator==(const View& other) const;
1352  bool operator!=(const Bytes& other) const { return ! (*this == other); }
1353  bool operator!=(const Stream& other) const { return ! (*this == other); }
1354  bool operator!=(const View& other) const { return ! (*this == other); }
1355 
1359  void debugPrint(std::ostream& out) const;
1360 
1361 private:
1362  View(SafeConstIterator begin, std::optional<SafeConstIterator> end)
1363  : _begin(std::move(begin)), _end(std::move(end)) {
1364  if ( _end )
1365  _ensureSameChain(*_end);
1366  }
1367 
1368  void _ensureSameChain(const SafeConstIterator& other) const {
1369  if ( _begin.chain() != other.chain() )
1370  throw InvalidIterator("incompatible iterator");
1371  }
1372 
1373  void _ensureValid() const {
1374  // if ( ! _begin.chain() )
1375  // throw InvalidIterator("view has invalid beginning");
1376 
1377  // if ( ! _begin.isValid() )
1378  // throw InvalidIterator("view has invalid beginning");
1379 
1380  if ( _end && ! _end->isValid() )
1381  throw InvalidIterator("view has invalid end");
1382  }
1383 
1384  // Common backend for backward searching.
1385  std::tuple<bool, UnsafeConstIterator> _findBackward(const Bytes& needle, UnsafeConstIterator i) const;
1386 
1387  // Common backend for forward searching.
1388  std::tuple<bool, UnsafeConstIterator> _findForward(const Bytes& v, UnsafeConstIterator n) const;
1389 
1390  SafeConstIterator _begin;
1391  std::optional<SafeConstIterator> _end;
1392 };
1393 
1394 inline std::ostream& operator<<(std::ostream& out, const View& x) { return out << hilti::rt::to_string_for_print(x); }
1395 } // namespace stream
1396 
1407 class Stream {
1408 private:
1409  using Byte = stream::Byte;
1410  using Chain = stream::detail::Chain;
1412  using Chunk = stream::detail::Chunk;
1413  using Offset = stream::Offset;
1415  using Size = stream::Size;
1417  using View = stream::View;
1418 
1419 public:
1421  Stream() : _chain(make_intrusive<Chain>()) {}
1422 
1427  explicit Stream(std::vector<Byte> d) : Stream(Chunk(0, std::move(d))) {}
1428 
1433  explicit Stream(const Bytes& d);
1434 
1439  explicit Stream(const char* d) : Stream(Chunk(0, d, strlen(d))) {}
1440 
1445  Stream(const char* d, Size n);
1450  Stream(const stream::View& d) : Stream(Chunk(0, d)) {}
1451 
1456  template<int N>
1457  Stream(std::vector<std::array<Byte, N>> d) : Stream(chunkFromArray(0, std::move(d))) {}
1458 
1463  Stream(const Stream& other) noexcept : _chain(other._chain->deepCopy()) {}
1464 
1469  Stream(Stream&& other) noexcept : _chain(std::move(other._chain)) { other._chain = make_intrusive<Chain>(); }
1470 
1475  Stream& operator=(Stream&& other) noexcept {
1476  if ( &other == this )
1477  return *this;
1478 
1479  _chain->invalidate();
1480  _chain = std::move(other._chain);
1481  other._chain = make_intrusive<Chain>();
1482  return *this;
1483  }
1484 
1489  Stream& operator=(const Stream& other) {
1490  if ( &other == this )
1491  return *this;
1492 
1493  _chain->invalidate();
1494  _chain = other._chain->deepCopy();
1495  return *this;
1496  }
1497 
1500  assert(_chain);
1501  _chain->invalidate();
1502  }
1503 
1505  Size size() const { return _chain->size(); }
1506 
1508  bool isEmpty() const { return _chain->size() == 0; }
1509 
1514  void append(const Bytes& data);
1515 
1520  void append(Bytes&& data);
1521 
1526  void append(std::unique_ptr<const Byte*> data);
1527 
1532  void append(const char* data, size_t len);
1533 
1542  void trim(const SafeConstIterator& i) { _chain->trim(i); }
1543 
1545  void freeze() { _chain->freeze(); }
1546 
1548  void unfreeze() { _chain->unfreeze(); }
1549 
1551  bool isFrozen() const { return _chain->isFrozen(); }
1552 
1554  SafeConstIterator begin() const { return _chain->begin(); }
1555 
1557  SafeConstIterator end() const { return _chain->end(); }
1558 
1560  UnsafeConstIterator unsafeBegin() const { return _chain->unsafeBegin(); }
1561 
1563  UnsafeConstIterator unsafeEnd() const { return _chain->unsafeEnd(); }
1564 
1569  SafeConstIterator at(Offset offset) const { return _chain->at(offset); }
1570 
1577  View view(bool expanding = true) const { return expanding ? View(begin()) : View(begin(), end()); }
1578 
1579  bool operator==(const Bytes& other) const { return view() == other; }
1580  bool operator==(const Stream& other) const { return view() == other.view(); }
1581  bool operator==(const stream::View& other) const { return view() == other; }
1582  bool operator!=(const Bytes& other) const { return ! (*this == other); }
1583  bool operator!=(const Stream& other) const { return ! (*this == other); }
1584  bool operator!=(const stream::View& other) const { return ! (*this == other); }
1585 
1590  int numberOfChunks() const { return _chain->numberOfChunks(); }
1591 
1595  void debugPrint(std::ostream& out) const;
1596 
1600  static void debugPrint(std::ostream& out, const stream::detail::Chain* chain);
1601 
1602 private:
1603  Stream(Chunk&& ch) : _chain(make_intrusive<Chain>(std::make_unique<Chunk>(std::move(ch)))) {}
1604 
1605  ChainPtr _chain; // always non-null
1606 };
1607 
1608 template<>
1609 inline std::string detail::to_string_for_print<stream::View>(const stream::View& x) {
1610  return escapeBytes(x.dataForPrint(), true);
1611 }
1612 
1613 template<>
1614 inline std::string detail::to_string_for_print<Stream>(const Stream& x) {
1615  return to_string_for_print(x.view());
1616 }
1617 
1618 inline std::ostream& operator<<(std::ostream& out, const Stream& x) { return out << to_string_for_print(x); }
1619 
1620 namespace detail::adl {
1621 inline std::string to_string(const stream::View& x, adl::tag /*unused*/) {
1622  return fmt("b\"%s\"", hilti::rt::to_string_for_print(x));
1623 }
1624 
1625 inline std::string to_string(const Stream& x, adl::tag /*unused*/) { return hilti::rt::to_string(x.view()); }
1626 } // namespace detail::adl
1627 
1628 } // namespace hilti::rt
Chain(std::unique_ptr< Chunk > head)
Definition: stream.h:267
View extract(Byte(&dst)[N]) const
Definition: stream.h:1289
std::tuple< bool, SafeConstIterator > find(const Bytes &v, Direction d=Direction::Forward) const
Definition: stream.h:1147
std::string to_string(T &&x)
Definition: extension-points.h:26
std::string to_string_for_print(const T &x)
Definition: extension-points.h:45
Definition: exception.h:199
View sub(SafeConstIterator to) const
Definition: stream.h:1233
const auto operator--(int)
Definition: stream.h:743
auto & operator+=(integer::safe< uint64_t > i)
Definition: stream.h:427
void trim(const SafeConstIterator &i)
Definition: stream.h:1542
View(SafeConstIterator begin)
Definition: stream.h:1032
bool operator>=(const UnsafeConstIterator &other) const
Definition: stream.h:807
auto operator*() const
Definition: stream.h:756
const detail::Chunk * _block
Definition: stream.h:1330
bool isUnset() const
Definition: stream.h:818
detail::UnsafeConstIterator unsafeBegin() const
Definition: stream.h:1309
SafeConstIterator end() const
Definition: stream.h:1557
SafeConstIterator at(Offset offset) const
Definition: stream.h:1569
Stream(const char *d)
Definition: stream.h:1439
std::tuple< bool, UnsafeConstIterator > find(const Bytes &v, UnsafeConstIterator n, Direction d=Direction::Forward) const
Definition: stream.h:1184
bool operator>(const SafeConstIterator &other) const
Definition: stream.h:511
bool operator<=(const UnsafeConstIterator &other) const
Definition: stream.h:801
Definition: intrusive-ptr.h:25
Definition: any.h:7
const auto operator++(int)
Definition: stream.h:730
Stream & operator=(const Stream &other)
Definition: stream.h:1489
Offset offset() const
Definition: stream.h:1038
void internalError(const std::string &msg) __attribute__((noreturn))
Definition: logging.cc:17
uint64_t offset
Definition: stream.h:1327
auto & operator-=(integer::safe< uint64_t > i)
Definition: stream.h:750
Definition: optional.h:79
UnsafeConstIterator unsafeBegin() const
Definition: stream.h:1560
const Byte * start
Definition: stream.h:1325
Definition: stream.h:71
Definition: intrusive-ptr.h:28
integer::safe< int64_t > operator-(const SafeConstIterator &other) const
Definition: stream.h:473
Definition: stream.h:1324
bool operator==(const UnsafeConstIterator &other) const
Definition: stream.h:786
SafeConstIterator begin() const
Definition: stream.h:1554
const auto operator++(int)
Definition: stream.h:420
Definition: bytes.h:155
bool startsWith(const std::string &s, const std::string &prefix)
Definition: util.h:201
bool isEmpty() const
Definition: stream.h:1048
Stream & operator=(Stream &&other) noexcept
Definition: stream.h:1475
void cannot_be_reached() __attribute__((noreturn))
Definition: util.cc:52
View sub(Offset to) const
Definition: stream.h:1252
Definition: stream.h:258
View limit(Offset incr) const
Definition: stream.h:1279
bool is_first
Definition: stream.h:1328
bool isEmpty() const
Definition: stream.h:1508
bool operator<=(const SafeConstIterator &other) const
Definition: stream.h:505
auto & operator--()
Definition: stream.h:737
bool operator<(const SafeConstIterator &other) const
Definition: stream.h:499
bool operator!=(const SafeConstIterator &other) const
Definition: stream.h:493
SafeConstIterator find(Byte b, const SafeConstIterator &n) const
Definition: stream.h:1078
Definition: stream.h:1001
auto & operator--()
Definition: stream.h:433
bool isEnd() const
Definition: stream.h:838
detail::UnsafeConstIterator unsafeEnd() const
Definition: stream.h:1312
bool isValid() const
Definition: stream.h:835
void unfreeze()
Definition: stream.h:1548
bool isExpired() const
Definition: stream.h:824
int numberOfChunks() const
Definition: stream.h:1590
Offset offset() const
Definition: stream.h:718
View advance(SafeConstIterator i) const
Definition: stream.h:1198
Stream(const stream::View &d)
Definition: stream.h:1450
bool isFrozen() const
Definition: stream.h:721
bool isExpired() const
Definition: stream.h:537
std::tuple< bool, SafeConstIterator > find(const View &v) const
Definition: stream.h:1102
bool isValid() const
Definition: stream.h:548
bool operator!=(const UnsafeConstIterator &other) const
Definition: stream.h:795
bool isUnset() const
Definition: stream.h:531
View sub(SafeConstIterator from, SafeConstIterator to) const
Definition: stream.h:1221
View advance(integer::safe< uint64_t > i) const
Definition: stream.h:1208
Stream(std::vector< std::array< Byte, N >> d)
Definition: stream.h:1457
Stream(std::vector< Byte > d)
Definition: stream.h:1427
auto & operator-=(integer::safe< uint64_t > i)
Definition: stream.h:446
bool is_last
Definition: stream.h:1329
Definition: stream.h:1407
Definition: intrusive-ptr.h:69
Stream()
Definition: stream.h:1421
Stream(Stream &&other) noexcept
Definition: stream.h:1469
const auto operator--(int)
Definition: stream.h:439
void debugPrint(std::ostream &out) const
Definition: stream.cc:577
Size size() const
Definition: stream.h:1505
bool isOpenEnded() const
Definition: stream.h:1058
bool isFrozen() const
Definition: stream.h:1551
bool isFrozen() const
Definition: stream.h:1051
bool operator==(const SafeConstIterator &other) const
Definition: stream.h:483
std::tuple< bool, SafeConstIterator > find(const View &v, const SafeConstIterator &n) const
Definition: stream.h:1118
auto operator*() const
Definition: stream.h:452
bool operator>=(const SafeConstIterator &other) const
Definition: stream.h:517
bool isEnd() const
Definition: stream.h:555
~Stream()
Definition: stream.h:1499
auto operator+(integer::safe< uint64_t > i) const
Definition: stream.h:455
View(SafeConstIterator begin, SafeConstIterator end)
Definition: stream.h:1018
auto operator+(integer::safe< uint64_t > i) const
Definition: stream.h:759
UnsafeConstIterator unsafeEnd() const
Definition: stream.h:1563
SafeConstIterator end() const
Definition: stream.h:1318
std::string_view trim(std::string_view s, const std::string &chars) noexcept
Definition: util.h:113
const SafeConstIterator & begin() const
Definition: stream.h:1315
Definition: stream.h:87
bool isFrozen() const
Definition: stream.h:411
SafeConstIterator find(Byte b) const
Definition: stream.h:1066
bool operator>(const UnsafeConstIterator &other) const
Definition: stream.h:804
auto operator-(integer::safe< uint64_t > i) const
Definition: stream.h:462
Definition: stream.h:391
void freeze()
Definition: stream.h:1545
bool operator<(const UnsafeConstIterator &other) const
Definition: stream.h:798
auto & operator++()
Definition: stream.h:724
View trim(const SafeConstIterator &nbegin) const
Definition: stream.h:1262
Stream(const Stream &other) noexcept
Definition: stream.h:1463
integer::safe< int64_t > operator-(const UnsafeConstIterator &other) const
Definition: stream.h:777
SafeConstIterator at(Offset offset) const
Definition: stream.h:1255
auto & operator++()
Definition: stream.h:414
std::string fmt(const char *fmt, const Args &... args)
Definition: fmt.h:13
View sub(Offset from, Offset to) const
Definition: stream.h:1244
std::tuple< bool, SafeConstIterator > find(const Bytes &v, const SafeConstIterator &n, Direction d=Direction::Forward) const
Definition: stream.h:1165
Offset offset() const
Definition: stream.h:408
View view(bool expanding=true) const
Definition: stream.h:1577
auto operator-(integer::safe< uint64_t > i) const
Definition: stream.h:766
uint64_t size
Definition: stream.h:1326