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 <limits>
12 #include <memory>
13 #include <optional>
14 #include <string>
15 #include <tuple>
16 #include <utility>
17 #include <variant>
18 #include <vector>
19 
20 #include <hilti/rt/any.h>
21 #include <hilti/rt/exception.h>
22 #include <hilti/rt/intrusive-ptr.h>
23 #include <hilti/rt/logging.h>
24 #include <hilti/rt/result.h>
25 #include <hilti/rt/safe-int.h>
26 #include <hilti/rt/types/bytes.h>
27 #include <hilti/rt/types/time.h>
28 #include <hilti/rt/types/vector.h>
29 #include <hilti/rt/util.h>
30 
31 namespace hilti::rt {
32 
33 class Stream;
34 
35 namespace stream {
36 class View;
37 class SafeConstIterator;
38 
39 namespace detail {
41 }
42 } // namespace stream
43 
44 namespace detail::adl {
45 std::string to_string(const Stream& x, adl::tag /*unused*/);
46 std::string to_string(const stream::View& x, adl::tag /*unused*/);
47 std::string to_string(const stream::SafeConstIterator& x, adl::tag /*unused*/);
48 std::string to_string(const stream::detail::UnsafeConstIterator& x, adl::tag /*unused*/);
49 } // namespace detail::adl
50 
51 namespace stream {
53 using Byte = uint8_t;
54 
56 using Offset = integer::safe<uint64_t>;
57 
59 using Size = integer::safe<uint64_t>;
60 
62 enum class Direction : int64_t { Forward, Backward };
63 
64 namespace detail {
65 
66 class Chain;
70 
71 // Represents a gap of length `size`.
72 struct Gap {
73  size_t size;
74 };
75 
88 class Chunk {
89 public:
90  static const int SmallBufferSize = 32;
91  using Array = std::pair<Size, std::array<Byte, SmallBufferSize>>;
92  using Vector = std::vector<Byte>;
93 
94  Chunk(Offset o, std::array<Byte, SmallBufferSize> d, Size n) : _offset(o), _data(std::make_pair(n, d)) {}
95  Chunk(Offset o, Vector&& d) : _offset(o), _data(std::move(d)) {}
96  Chunk(Offset o, const View& d);
97  Chunk(Offset o, const std::string& s);
98 
99  template<int N>
100  Chunk(Offset o, std::array<Byte, N> d) : Chunk(_fromArray(o, std::move(d))) {}
101  Chunk(Offset o, const char* d, Size n) : Chunk(_fromArray(o, d, n)) {}
102 
103  // Constructs a gap chunk which signifies empty data.
104  Chunk(Offset o, size_t len) : _offset(o), _data(Gap{len}) {}
105 
106  Chunk(const Chunk& other) : _offset(other._offset), _data(other._data) {}
107  Chunk(Chunk&& other) noexcept
108  : _offset(other._offset), _data(std::move(other._data)), _next(std::move(other._next)) {}
109 
110  Chunk& operator=(const Chunk& other) = delete;
111 
112  Chunk& operator=(Chunk&& other) noexcept {
113  _offset = other._offset;
114  _data = std::move(other._data);
115  _next = std::move(other._next);
116  _chain = other._chain;
117  return *this;
118  }
119 
120  ~Chunk() = default;
121 
122  Offset offset() const { return _offset; }
123  Offset endOffset() const { return _offset + size(); }
124  bool isGap() const { return std::holds_alternative<Gap>(_data); }
125  bool inRange(Offset offset) const { return offset >= _offset && offset < endOffset(); }
126 
127  const Byte* data() const {
128  if ( auto a = std::get_if<Array>(&_data) )
129  return a->second.data();
130  else if ( auto a = std::get_if<Vector>(&_data) ) {
131  return a->data();
132  }
133  else if ( std::holds_alternative<Gap>(_data) )
134  throw MissingData("data is missing");
135 
137  }
138 
139  const Byte* data(Offset offset) const {
140  assert(inRange(offset));
141  return data() + (offset - _offset).Ref();
142  }
143 
144  const Byte* endData() const {
145  if ( auto a = std::get_if<Array>(&_data) )
146  return a->second.data() + a->first.Ref();
147  else if ( auto a = std::get_if<Vector>(&_data) ) {
148  return a->data() + a->size();
149  }
150  else if ( std::holds_alternative<Gap>(_data) )
151  throw MissingData("data is missing");
152 
154  }
155 
156  Size size() const {
157  if ( auto a = std::get_if<Array>(&_data) )
158  return a->first;
159  else if ( auto a = std::get_if<Vector>(&_data) )
160  return a->size();
161  else if ( auto a = std::get_if<Gap>(&_data) )
162  return a->size;
163 
165  }
166 
167  bool isLast() const { return ! _next; }
168  const Chunk* next() const { return _next.get(); }
169 
170  auto last() const {
171  const Chunk* i = this;
172  while ( i && i->_next )
173  i = i->_next.get();
174  return i;
175  }
176 
177  auto last() {
178  Chunk* i = this;
179  while ( i && i->_next )
180  i = i->_next.get();
181  return i;
182  }
183 
184  void debugPrint(std::ostream& out) const;
185 
186 protected:
187  // All mutating functions are protected and are expected to be called
188  // only from chain so that it can track any changes.
189  friend class Chain;
190 
191  void trim(Offset o);
192 
193  // Update offset for current chunk and all others linked from it.
194  void setOffset(Offset o) {
195  auto c = this;
196  while ( c ) {
197  c->_offset = o;
198  o += c->size();
199  c = c->next();
200  }
201  }
202 
203  // Set chain for current chunk and all others linked from it.
204  void setChain(const Chain* chain) {
205  auto x = this;
206  while ( x ) {
207  x->_chain = chain;
208  x = x->_next.get();
209  }
210  }
211 
212  Chunk* next() { return _next.get(); }
213 
214  // Link in chunk as successor of current one. Updates offset/chain for
215  // the appended chunk and all its successors.
216  void setNext(std::unique_ptr<Chunk> next) {
217  assert(_chain);
218 
219  Offset offset = endOffset();
220  _next = std::move(next);
221 
222  auto c = _next.get();
223  while ( c ) {
224  c->_offset = offset;
225  c->_chain = _chain;
226  offset += c->size();
227  c = c->_next.get();
228  }
229  }
230 
231  void clearNext() { _next = nullptr; }
232 
233 private:
234  inline Chunk _fromArray(Offset o, const char* d, Size n) {
235  auto ud = reinterpret_cast<const Byte*>(d);
236 
237  if ( n <= Chunk::SmallBufferSize ) {
238  std::array<Byte, Chunk::SmallBufferSize> x{};
239  std::copy(ud, ud + n.Ref(), x.data());
240  return Chunk(o, x, n);
241  }
242 
243  return Chunk(o, Chunk::Vector(ud, ud + n.Ref()));
244  }
245 
246  Offset _offset = 0; // global offset of 1st byte
247  std::variant<Array, Vector, Gap> _data; // content of this chunk
248  const Chain* _chain = nullptr; // chain this chunk is part of, or null if not linked to a chain yet (non-owning;
249  // will stay valid at least as long as the current chunk does)
250  std::unique_ptr<Chunk> _next = nullptr; // next chunk in chain, or null if last
251 };
252 
260 public:
263  using Size = stream::Size;
264 
265  Chain() {}
266 
268  Chain(std::unique_ptr<Chunk> head) : _head(std::move(head)), _tail(_head->last()) { _head->setChain(this); }
269 
270  Chain(Chain&& other) = delete;
271  Chain(const Chain& other) = delete;
272  Chain& operator=(const Chain& other) = delete;
273  Chain& operator=(const Chain&& other) = delete;
274 
275  const Chunk* head() const { return _head.get(); }
276  const Chunk* tail() const { return _tail; }
277  Size size() const { return (endOffset() - offset()).Ref(); }
278  bool isFrozen() const { return _state == State::Frozen; }
279  bool isValid() const { return _state != State::Invalid; }
280  bool inRange(Offset o) const { return o >= offset() && o < endOffset(); }
281 
282  Offset offset() const { return _head_offset; }
283  Offset endOffset() const { return _tail ? _tail->endOffset() : _head_offset; }
284 
285  // Finds the chunk containing *offset*. Returns null if not found.
286  // *hint_prev* may point to a chunk chained in before the target chunk,
287  // allowing that to be found more quickly. If given, *hint_prev* must be
288  // pointing to a current chunk of the chain, but it's ok if it's
289  // non-helpful for finding the target (i.e., pointing to a later chunk).
290  const Chunk* findChunk(Offset offset, const Chunk* hint_prev = nullptr) const;
291  Chunk* findChunk(Offset offset, Chunk* hint_prev = nullptr);
292 
293  // Returns a pointer to the byte at a given offset. Returns null if
294  // offset is out of range. See find() for semantics of *hint_prev*.
295  const Byte* data(Offset offset, Chunk* hint_prev = nullptr) const;
296 
297  SafeConstIterator begin() const;
298  SafeConstIterator end() const;
299  SafeConstIterator at(Offset offset) const;
300  UnsafeConstIterator unsafeBegin() const;
301  UnsafeConstIterator unsafeEnd() const;
302 
303  // Returns a newly allocated chain with the same content.
304  ChainPtr deepCopy() const;
305 
307  void append(std::unique_ptr<Chunk> chunk);
308  void append(Chain&& other);
309 
310  void trim(Offset offset);
311  void trim(const SafeConstIterator& i);
312  void trim(const UnsafeConstIterator& i);
313 
314  // Turns the chain into invalidated state, whill releases all chunks and
315  // will let attempts to dereference any still existing iterators fail.
316  void invalidate() {
317  _state = State::Invalid;
318  _head.reset();
319  _head_offset = 0;
320  _tail = nullptr;
321  }
322 
323  // Turns the chain into a freshly initialized state.
324  void reset() {
325  _state = State::Mutable;
326  _head.reset();
327  _head_offset = 0;
328  _tail = nullptr;
329  }
330 
331  void freeze() {
332  if ( isValid() )
333  _state = State::Frozen;
334  }
335  void unfreeze() {
336  if ( isValid() )
337  _state = State::Mutable;
338  }
339 
340  // Returns the number of dynamic chunks allocated.
341  int numberOfChunks() const;
342 
343 private:
344  void _ensureValid() const {
345  if ( ! isValid() )
346  throw InvalidIterator("stream object no longer available");
347  }
348 
349  void _ensureMutable() const {
350  if ( isFrozen() )
351  throw Frozen("stream object can no longer be modified");
352  }
353 
354  enum class State {
355  Mutable, // content can be expanded an trimmed
356  Frozen, // content cannot be changed
357  Invalid, // parent stream object has been destroyed, all content is invalid
358  };
359 
360  // Current state of chain
361  State _state = State::Mutable;
362 
363  // First chunk, or null if chain is empty.
364  std::unique_ptr<Chunk> _head = nullptr;
365 
366  // Offset of the beginning of chain. If head is set, this offset will
367  // match that of head. If head is not set, it'll contain the most recent
368  // end offset of the main (that's zero initially, but may be non-zero
369  // after trimming off all chunks).
370  Offset _head_offset = 0;
371 
372  // Always pointing to last chunk reachable from *head*, or null if chain
373  // is empty; non-owning
374  Chunk* _tail = nullptr;
375 };
376 
377 } // namespace detail
378 
393 public:
394  using Byte = stream::Byte;
398  using Offset = stream::Offset;
399  using Size = stream::Size;
401 
403  SafeConstIterator() = default;
404 
406  explicit SafeConstIterator(const UnsafeConstIterator& i);
407 
409  Offset offset() const { return _offset; }
410 
412  bool isFrozen() const { return ! _chain || _chain->isFrozen(); }
413 
415  auto& operator++() {
416  _increment(1);
417  return *this;
418  }
419 
421  auto operator++(int) {
422  auto x = *this;
423  _increment(1);
424  return x;
425  }
426 
428  auto& operator+=(integer::safe<uint64_t> i) {
429  _increment(i);
430  return *this;
431  }
432 
434  auto& operator--() {
435  _decrement(1);
436  return *this;
437  }
438 
440  auto operator--(int) {
441  auto x = *this;
442  _decrement(1);
443  return x;
444  }
445 
447  auto& operator-=(integer::safe<uint64_t> i) {
448  _decrement(i);
449  return *this;
450  }
451 
453  auto operator*() const { return _dereference(); }
454 
456  auto operator+(integer::safe<uint64_t> i) const {
457  auto x = *this;
458  x._increment(i);
459  return x;
460  }
461 
463  auto operator-(integer::safe<uint64_t> i) const {
464  auto x = *this;
465  x._decrement(i);
466  return x;
467  }
468 
474  integer::safe<int64_t> operator-(const SafeConstIterator& other) const {
475  _ensureSameChain(other);
476  return static_cast<int64_t>(_offset) - static_cast<int64_t>(other._offset);
477  }
478 
484  bool operator==(const SafeConstIterator& other) const {
485  _ensureSameChain(other);
486  return (_offset == other._offset) || (isEnd() && other.isEnd());
487  }
488 
494  bool operator!=(const SafeConstIterator& other) const {
495  _ensureSameChain(other);
496  return ! (*this == other);
497  }
498 
500  bool operator<(const SafeConstIterator& other) const {
501  _ensureSameChain(other);
502  return offset() < other.offset();
503  }
504 
506  bool operator<=(const SafeConstIterator& other) const {
507  _ensureSameChain(other);
508  return offset() <= other.offset();
509  }
510 
512  bool operator>(const SafeConstIterator& other) const {
513  _ensureSameChain(other);
514  return offset() > other.offset();
515  }
516 
518  bool operator>=(const SafeConstIterator& other) const {
519  _ensureSameChain(other);
520  return offset() >= other.offset();
521  }
522 
524  explicit operator bool() const { return ! isUnset(); }
525 
526  std::ostream& operator<<(std::ostream& out) const {
527  out << to_string(*this);
528  return out;
529  }
530 
532  bool isUnset() const { return ! _chain; }
533 
538  bool isExpired() const {
539  if ( ! _chain )
540  return false;
541 
542  return ! _chain->isValid();
543  }
544 
549  bool isValid() const { return ! isUnset() && ! isExpired(); }
550 
556  bool isEnd() const {
557  if ( ! _chain )
558  return true;
559 
560  _ensureValidChain();
561  return _offset >= _chain->endOffset();
562  }
563 
568  void debugPrint(std::ostream& out) const;
569 
570 protected:
571  friend class hilti::rt::stream::View;
574 
575  // Returns the chunk only if it's a valid pointer, other null. See
576  // comment on `_chunk` validity below.
577  const Chunk* chunk() const { return _chain && _chain->isValid() && _chain->inRange(_offset) ? _chunk : nullptr; }
578  const Chain* chain() const { return _chain.get(); }
579 
580 private:
581  SafeConstIterator(ConstChainPtr chain, Offset offset, const Chunk* chunk)
582  : _chain(std::move(chain)), _offset(offset), _chunk(chunk) {
583  assert(! isUnset());
584  }
585 
586  void _ensureValidChain() const {
587  // This must have been checked at this point already.
588  assert(_chain);
589 
590  if ( ! _chain->isValid() )
591  throw InvalidIterator("stream object no longer available");
592  }
593 
594  void _ensureSameChain(const SafeConstIterator& other) const {
595  if ( ! (_chain && other._chain) )
596  // One is the default constructed end iterator; that's ok.
597  return;
598 
599  if ( ! other.isValid() )
600  throw InvalidIterator("stream object no longer available");
601 
602  if ( _chain != other._chain )
603  throw InvalidIterator("incompatible iterators");
604  }
605 
606  void _increment(integer::safe<uint64_t> n) {
607  if ( ! _chain )
608  throw InvalidIterator("unbound stream iterator");
609 
610  if ( ! n )
611  return;
612 
613  _offset += n;
614 
615  if ( ! (_chain && _chain->isValid()) )
616  return; // will be caught when dereferenced
617 
618  _chunk = _chain->findChunk(_offset, chunk());
619  // chunk will be null if we're pointing beyond the end.
620  }
621 
622  void _decrement(integer::safe<uint64_t> n) {
623  if ( ! _chain )
624  throw InvalidIterator("unbound stream iterator");
625 
626  if ( n > _offset )
627  throw InvalidIterator("attempt to move before beginning of stream");
628 
629  if ( ! n )
630  return;
631 
632  _offset -= n;
633 
634  if ( _chunk && _offset > _chunk->offset() )
635  return; // fast-path, chunk still valid
636 
637  if ( ! (_chain && _chain->isValid()) )
638  return; // will be caught when dereferenced
639 
640  _chunk = _chain->findChunk(_offset, _chunk);
641  // chunk will be null if we're pointing beyond the beginning.
642  }
643 
644  Byte _dereference() const {
645  if ( ! _chain )
646  throw InvalidIterator("unbound stream iterator");
647 
648  _ensureValidChain();
649 
650  if ( ! _chain->inRange(_offset) )
651  throw InvalidIterator("stream iterator outside of valid range");
652 
653  auto c = _chain->findChunk(_offset, chunk());
654  assert(c);
655 
656  if ( c->isGap() )
657  throw MissingData("data is missing");
658 
659  return *c->data(_offset);
660  }
661 
662  // Parent chain if bound, or null if not. The parent will stay around for
663  // at least as long as this iterator.
664  ConstChainPtr _chain = nullptr;
665 
666  // Global offset inside parent chain. This can be pointing to anywhere
667  // inside the stream's sequence space, including potentially being
668  // outside of the chain's valid range. It may always be accessed, even if
669  // the iterator is unbound, or the chain not valid anymore; it will then
670  // generally reflect the most recent value, which may or may not
671  // semantically make sense.
672  Offset _offset = 0;
673 
674  // A chunk from which *_offset* is reachable (i.e., the chunk either
675  // contains the offset, or we can get to the right chunk by following its
676  // successors). The chunk is null if our current offset is outside of the
677  // chains valid range.
678  //
679  // This chunk pointer is only valid for access if (1) *_chain* is set and
680  // valid; and (2) _offset is inside the chain's valid range. It will then
681  // point to a chunk from which _offset is *reachable*. (If these two are
682  // not satisfied, the chunk may be pointing into freed memory!)
683  const Chunk* _chunk = nullptr;
684 };
685 
686 inline std::ostream& operator<<(std::ostream& out, const SafeConstIterator& x) {
687  out << to_string(x);
688  return out;
689 }
690 
701 namespace detail {
702 
704 public:
705  using Byte = stream::Byte;
709  using Offset = stream::Offset;
710  using Size = stream::Size;
711 
713  UnsafeConstIterator() = default;
714 
716  explicit UnsafeConstIterator(const SafeConstIterator& i);
717 
719  Offset offset() const { return _offset; }
720 
722  bool isFrozen() const { return ! _chain || _chain->isFrozen(); }
723 
725  auto& operator++() {
726  _increment(1);
727  return *this;
728  }
729 
731  auto operator++(int) {
732  auto x = *this;
733  _increment(1);
734  return x;
735  }
736 
738  auto& operator--() {
739  _decrement(1);
740  return *this;
741  }
742 
744  auto operator--(int) {
745  auto x = *this;
746  _decrement(1);
747  return x;
748  }
749 
751  auto& operator-=(integer::safe<uint64_t> i) {
752  _decrement(i);
753  return *this;
754  }
755 
757  auto operator*() const { return _dereference(); }
758 
760  auto operator+(integer::safe<uint64_t> i) const {
761  auto x = *this;
762  x._increment(i);
763  return x;
764  }
765 
767  auto operator-(integer::safe<uint64_t> i) const {
768  auto x = *this;
769  x._decrement(i);
770  return x;
771  }
772 
778  integer::safe<int64_t> operator-(const UnsafeConstIterator& other) const {
779  return static_cast<int64_t>(_offset) - static_cast<int64_t>(other._offset);
780  }
781 
787  bool operator==(const UnsafeConstIterator& other) const {
788  return (_offset == other._offset) || (isEnd() && other.isEnd());
789  }
790 
796  bool operator!=(const UnsafeConstIterator& other) const { return ! (*this == other); }
797 
799  bool operator<(const UnsafeConstIterator& other) const { return offset() < other.offset(); }
800 
802  bool operator<=(const UnsafeConstIterator& other) const { return offset() <= other.offset(); }
803 
805  bool operator>(const UnsafeConstIterator& other) const { return offset() > other.offset(); }
806 
808  bool operator>=(const UnsafeConstIterator& other) const { return offset() >= other.offset(); }
809 
811  explicit operator bool() const { return ! isUnset(); }
812 
813  std::ostream& operator<<(std::ostream& out) const {
814  out << to_string(*this);
815  return out;
816  }
817 
819  bool isUnset() const { return ! _chain; }
820 
825  bool isExpired() const {
826  if ( ! _chain )
827  return false;
828 
829  return ! _chain->isValid();
830  }
831 
836  bool isValid() const { return ! isUnset() && ! isExpired(); }
837 
839  bool isEnd() const {
840  if ( ! _chain )
841  return true;
842 
843  return _offset >= _chain->endOffset();
844  }
845 
850  void debugPrint(std::ostream& out) const;
851 
852 protected:
853  friend class hilti::rt::stream::View;
856 
857  const Chunk* chunk() const { return _chunk; }
858  const Chain* chain() const { return _chain; }
859 
860 private:
861  UnsafeConstIterator(const ConstChainPtr& chain, Offset offset, const Chunk* chunk)
862  : _chain(chain.get()), _offset(offset), _chunk(chunk) {
863  assert(! isUnset());
864  }
865 
866  UnsafeConstIterator(const Chain* chain, Offset offset, const Chunk* chunk)
867  : _chain(chain), _offset(offset), _chunk(chunk) {
868  assert(! isUnset());
869  }
870 
871  void _increment(integer::safe<uint64_t> n) {
872  _offset += n;
873 
874  if ( _chunk && _offset < _chunk->endOffset() )
875  return; // fast-path, chunk still valid
876 
877  _chunk = _chain->findChunk(_offset, _chunk);
878  }
879 
880  void _decrement(integer::safe<uint64_t> n) {
881  _offset -= n;
882 
883  if ( _chunk && _offset > _chunk->offset() )
884  return; // fast-path, chunk still valid
885 
886  _chunk = _chain->findChunk(_offset, _chunk);
887  }
888 
889  Byte _dereference() const {
890  // TODO(bbannier): Ideally we would `assert(_chunk)` here so clang-tidy
891  // knows that `_chunk` is always not null. Unfortunately it looks like
892  // that fails to it pruning that CFG edge so we have to return instead
893  // here. This should be inconsequential to users as this function must
894  // not be called if the data is invalid.
895  if ( ! _chunk )
896  internalError("dereference of invalid iterator");
897 
898  auto* byte = _chunk->data(_offset);
899 
900  if ( ! byte )
901  throw MissingData("data is missing");
902 
903  return *byte;
904  }
905 
906  // Parent chain if bound, or null if not. This is a raw, non-owning
907  // pointer that assumes the parent chain will stick around as long as
908  // needed.
909  const Chain* _chain = nullptr;
910 
911  // Global offset inside parent chain. This can be pointing to anywhere
912  // inside the stream's sequence space, including potentially being
913  // outside of the chain's valid range.
914  Offset _offset = 0;
915 
916  // The chunk containing the current offset, or null if offset is out of
917  // bounds. This a raw, non-owning pointer that assumes the chunk will
918  // stick around as long as needed.
919  const Chunk* _chunk = nullptr;
920 };
921 
923  : _chain(i.chain()), _offset(i.offset()), _chunk(i.chain() ? i.chain()->findChunk(_offset, i.chunk()) : nullptr) {}
924 
925 inline std::ostream& operator<<(std::ostream& out, const UnsafeConstIterator& x) {
926  out << to_string(x);
927  return out;
928 }
929 
930 inline SafeConstIterator Chain::begin() const {
931  _ensureValid();
932  return {ConstChainPtr(intrusive_ptr::NewRef(), this), offset(), _head.get()};
933 }
934 
935 inline SafeConstIterator Chain::end() const {
936  _ensureValid();
937  return {ConstChainPtr(intrusive_ptr::NewRef(), this), endOffset(), _tail};
938 }
939 
940 inline SafeConstIterator Chain::at(Offset offset) const {
941  return {ConstChainPtr(intrusive_ptr::NewRef(), this), offset, findChunk(offset)};
942 }
943 
944 inline UnsafeConstIterator Chain::unsafeBegin() const {
945  _ensureValid();
946  return {ConstChainPtr(intrusive_ptr::NewRef(), this), offset(), _head.get()};
947 }
948 inline UnsafeConstIterator Chain::unsafeEnd() const {
949  _ensureValid();
950  return {ConstChainPtr(intrusive_ptr::NewRef(), this), endOffset(), _tail};
951 }
952 
953 inline void Chain::trim(const SafeConstIterator& i) {
954  if ( ! i.chain() ) {
955  // Unbound end operator, trim all content off.
956  trim(endOffset());
957  return;
958  }
959 
960  if ( i.chain() != this )
961  throw InvalidIterator("incompatible iterator");
962 
963  if ( ! i.isValid() )
964  throw InvalidIterator("stream object no longer available");
965 
966  trim(i.offset());
967 }
968 
969 inline void Chain::trim(const UnsafeConstIterator& i) { trim(i.offset()); }
970 
971 } // namespace detail
972 
974  : _chain(detail::ConstChainPtr(intrusive_ptr::NewRef(), i._chain)), _offset(i._offset), _chunk(i._chunk) {}
975 
983 class View {
984 public:
985  using Byte = stream::Byte;
989  using Offset = stream::Offset;
990  using Size = stream::Size;
992 
994  View() = default;
995 
997  virtual ~View();
998 
1000  explicit View(SafeConstIterator begin, SafeConstIterator end) : _begin(std::move(begin)), _end(std::move(end)) {
1001  _ensureValid();
1002 
1003  if ( ! _end->_chain )
1004  _end = _begin.chain()->end();
1005  else
1006  _ensureSameChain(*_end);
1007  }
1008 
1014  explicit View(SafeConstIterator begin) : _begin(std::move(begin)) {}
1015 
1020  Offset offset() const { return _begin.offset(); }
1021 
1026  std::optional<Offset> endOffset() const {
1027  if ( _end )
1028  return _end->offset();
1029  else
1030  return std::nullopt;
1031  }
1032 
1038  Size size() const;
1039 
1041  bool isEmpty() const { return size() == 0; }
1042 
1044  bool isFrozen() const { return _begin.isFrozen(); }
1045 
1051  bool isOpenEnded() const { return ! _end.has_value(); }
1052 
1059  SafeConstIterator find(Byte b) const {
1060  _ensureValid();
1061  return SafeConstIterator(find(b, UnsafeConstIterator()));
1062  }
1063 
1071  SafeConstIterator find(Byte b, const SafeConstIterator& n) const {
1072  _ensureValid();
1073  _ensureSameChain(n);
1074  return SafeConstIterator(find(b, UnsafeConstIterator(n)));
1075  }
1076 
1084  UnsafeConstIterator find(Byte b, UnsafeConstIterator n) const;
1085 
1095  std::tuple<bool, SafeConstIterator> find(const View& v) const {
1096  _ensureValid();
1097  auto x = find(v, UnsafeConstIterator());
1098  return std::make_tuple(std::get<0>(x), SafeConstIterator(std::get<1>(x)));
1099  }
1100 
1111  std::tuple<bool, SafeConstIterator> find(const View& v, const SafeConstIterator& n) const {
1112  _ensureValid();
1113  _ensureSameChain(n);
1114  auto x = find(v, UnsafeConstIterator(n));
1115  return std::make_tuple(std::get<0>(x), SafeConstIterator(std::get<1>(x)));
1116  }
1117 
1128  std::tuple<bool, UnsafeConstIterator> find(const View& v, UnsafeConstIterator n) const;
1129 
1140  std::tuple<bool, SafeConstIterator> find(const Bytes& v, Direction d = Direction::Forward) const {
1141  _ensureValid();
1142  auto i = (d == Direction::Forward ? unsafeBegin() : unsafeEnd());
1143  auto x = find(v, std::move(i), d);
1144  return std::make_tuple(std::get<0>(x), SafeConstIterator(std::get<1>(x)));
1145  }
1146 
1158  std::tuple<bool, SafeConstIterator> find(const Bytes& v, const SafeConstIterator& n,
1159  Direction d = Direction::Forward) const {
1160  _ensureValid();
1161  _ensureSameChain(n);
1162  auto x = find(v, UnsafeConstIterator(n), d);
1163  return std::make_tuple(std::get<0>(x), SafeConstIterator(std::get<1>(x)));
1164  }
1165 
1177  std::tuple<bool, UnsafeConstIterator> find(const Bytes& v, UnsafeConstIterator n,
1178  Direction d = Direction::Forward) const {
1179  if ( d == Direction::Forward )
1180  return _findForward(v, std::move(n));
1181  else
1182  return _findBackward(v, std::move(n));
1183  }
1184 
1192  _ensureSameChain(i);
1193  return View(std::move(i), _end);
1194  }
1195 
1201  View advance(integer::safe<uint64_t> i) const { return View(begin() + i, _end); }
1202 
1206  View advanceToNextData() const;
1207 
1215  _ensureSameChain(from);
1216  _ensureSameChain(to);
1217  return View(std::move(from), std::move(to));
1218  }
1219 
1227  _ensureSameChain(to);
1228  return View(begin(), std::move(to));
1229  }
1230 
1237  View sub(Offset from, Offset to) const { return View(begin() + from, begin() + to); }
1238 
1245  View sub(Offset to) const { return View(begin(), begin() + to); }
1246 
1248  SafeConstIterator at(Offset offset) const { return begin() + (offset - begin().offset()); }
1249 
1255  View trim(const SafeConstIterator& nbegin) const {
1256  _ensureSameChain(nbegin);
1257 
1258  if ( ! _end )
1259  return View(nbegin);
1260 
1261  if ( nbegin.offset() > _end->offset() )
1262  return View(*_end, *_end);
1263 
1264  return View(nbegin, *_end);
1265  }
1266 
1272  View limit(Offset incr) const { return View(begin(), begin() + incr); }
1273 
1281  View extract(Byte* dst, uint64_t n) const {
1282  _ensureValid();
1283 
1284  if ( n > size() )
1285  throw WouldBlock("end of stream view");
1286 
1287  auto p = unsafeBegin();
1288  for ( int i = 0; i < n; ++i )
1289  dst[i] = *p++;
1290 
1291  return View(SafeConstIterator(p), _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 
1572  Offset endOffset() const { return _chain->endOffset(); }
1573 
1580  View view(bool expanding = true) const { return expanding ? View(begin()) : View(begin(), end()); }
1581 
1582  bool operator==(const Bytes& other) const { return view() == other; }
1583  bool operator==(const Stream& other) const { return view() == other.view(); }
1584  bool operator==(const stream::View& other) const { return view() == other; }
1585  bool operator!=(const Bytes& other) const { return ! (*this == other); }
1586  bool operator!=(const Stream& other) const { return ! (*this == other); }
1587  bool operator!=(const stream::View& other) const { return ! (*this == other); }
1588 
1593  int numberOfChunks() const { return _chain->numberOfChunks(); }
1594 
1598  void debugPrint(std::ostream& out) const;
1599 
1603  static void debugPrint(std::ostream& out, const stream::detail::Chain* chain);
1604 
1605 private:
1606  Stream(Chunk&& ch) : _chain(make_intrusive<Chain>(std::make_unique<Chunk>(std::move(ch)))) {}
1607 
1608  ChainPtr _chain; // always non-null
1609 };
1610 
1611 template<>
1612 inline std::string detail::to_string_for_print<stream::View>(const stream::View& x) {
1613  return escapeBytes(x.dataForPrint(), true);
1614 }
1615 
1616 template<>
1617 inline std::string detail::to_string_for_print<Stream>(const Stream& x) {
1618  return to_string_for_print(x.view());
1619 }
1620 
1621 inline std::ostream& operator<<(std::ostream& out, const Stream& x) { return out << to_string_for_print(x); }
1622 
1623 namespace detail::adl {
1624 inline std::string to_string(const stream::View& x, adl::tag /*unused*/) {
1625  return fmt("b\"%s\"", hilti::rt::to_string_for_print(x));
1626 }
1627 
1628 inline std::string to_string(const Stream& x, adl::tag /*unused*/) { return hilti::rt::to_string(x.view()); }
1629 } // namespace detail::adl
1630 
1631 } // namespace hilti::rt
Chain(std::unique_ptr< Chunk > head)
Definition: stream.h:268
std::tuple< bool, SafeConstIterator > find(const Bytes &v, Direction d=Direction::Forward) const
Definition: stream.h:1140
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:1226
auto & operator+=(integer::safe< uint64_t > i)
Definition: stream.h:428
void trim(const SafeConstIterator &i)
Definition: stream.h:1542
View(SafeConstIterator begin)
Definition: stream.h:1014
bool operator>=(const UnsafeConstIterator &other) const
Definition: stream.h:808
auto operator*() const
Definition: stream.h:757
const detail::Chunk * _block
Definition: stream.h:1330
bool isUnset() const
Definition: stream.h:819
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:1177
bool operator>(const SafeConstIterator &other) const
Definition: stream.h:512
bool operator<=(const UnsafeConstIterator &other) const
Definition: stream.h:802
Definition: intrusive-ptr.h:26
Definition: any.h:7
std::optional< Offset > endOffset() const
Definition: stream.h:1026
Stream & operator=(const Stream &other)
Definition: stream.h:1489
Offset offset() const
Definition: stream.h:1020
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:751
Definition: optional.h:79
UnsafeConstIterator unsafeBegin() const
Definition: stream.h:1560
const Byte * start
Definition: stream.h:1325
Definition: stream.h:72
Definition: intrusive-ptr.h:29
integer::safe< int64_t > operator-(const SafeConstIterator &other) const
Definition: stream.h:474
Definition: stream.h:1324
auto operator--(int)
Definition: stream.h:744
bool operator==(const UnsafeConstIterator &other) const
Definition: stream.h:787
SafeConstIterator begin() const
Definition: stream.h:1554
Definition: bytes.h:158
bool startsWith(const std::string &s, const std::string &prefix)
Definition: util.h:201
bool isEmpty() const
Definition: stream.h:1041
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:1245
Definition: stream.h:259
View limit(Offset incr) const
Definition: stream.h:1272
bool is_first
Definition: stream.h:1328
bool isEmpty() const
Definition: stream.h:1508
bool operator<=(const SafeConstIterator &other) const
Definition: stream.h:506
auto & operator--()
Definition: stream.h:738
bool operator<(const SafeConstIterator &other) const
Definition: stream.h:500
bool operator!=(const SafeConstIterator &other) const
Definition: stream.h:494
auto operator++(int)
Definition: stream.h:731
SafeConstIterator find(Byte b, const SafeConstIterator &n) const
Definition: stream.h:1071
Definition: stream.h:983
auto & operator--()
Definition: stream.h:434
bool isEnd() const
Definition: stream.h:839
auto operator--(int)
Definition: stream.h:440
detail::UnsafeConstIterator unsafeEnd() const
Definition: stream.h:1312
bool isValid() const
Definition: stream.h:836
void unfreeze()
Definition: stream.h:1548
bool isExpired() const
Definition: stream.h:825
int numberOfChunks() const
Definition: stream.h:1593
Offset offset() const
Definition: stream.h:719
View advance(SafeConstIterator i) const
Definition: stream.h:1191
Stream(const stream::View &d)
Definition: stream.h:1450
bool isFrozen() const
Definition: stream.h:722
bool isExpired() const
Definition: stream.h:538
std::tuple< bool, SafeConstIterator > find(const View &v) const
Definition: stream.h:1095
Offset endOffset() const
Definition: stream.h:1572
bool isValid() const
Definition: stream.h:549
bool operator!=(const UnsafeConstIterator &other) const
Definition: stream.h:796
bool isUnset() const
Definition: stream.h:532
View sub(SafeConstIterator from, SafeConstIterator to) const
Definition: stream.h:1214
View advance(integer::safe< uint64_t > i) const
Definition: stream.h:1201
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:447
bool is_last
Definition: stream.h:1329
Definition: stream.h:1407
Definition: intrusive-ptr.h:70
Stream()
Definition: stream.h:1421
Stream(Stream &&other) noexcept
Definition: stream.h:1469
auto operator++(int)
Definition: stream.h:421
void debugPrint(std::ostream &out) const
Definition: stream.cc:592
Size size() const
Definition: stream.h:1505
bool isOpenEnded() const
Definition: stream.h:1051
bool isFrozen() const
Definition: stream.h:1551
bool isFrozen() const
Definition: stream.h:1044
bool operator==(const SafeConstIterator &other) const
Definition: stream.h:484
View extract(Byte *dst, uint64_t n) const
Definition: stream.h:1281
std::tuple< bool, SafeConstIterator > find(const View &v, const SafeConstIterator &n) const
Definition: stream.h:1111
auto operator*() const
Definition: stream.h:453
bool operator>=(const SafeConstIterator &other) const
Definition: stream.h:518
bool isEnd() const
Definition: stream.h:556
~Stream()
Definition: stream.h:1499
auto operator+(integer::safe< uint64_t > i) const
Definition: stream.h:456
View(SafeConstIterator begin, SafeConstIterator end)
Definition: stream.h:1000
auto operator+(integer::safe< uint64_t > i) const
Definition: stream.h:760
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:88
bool isFrozen() const
Definition: stream.h:412
SafeConstIterator find(Byte b) const
Definition: stream.h:1059
bool operator>(const UnsafeConstIterator &other) const
Definition: stream.h:805
auto operator-(integer::safe< uint64_t > i) const
Definition: stream.h:463
Definition: stream.h:392
void freeze()
Definition: stream.h:1545
bool operator<(const UnsafeConstIterator &other) const
Definition: stream.h:799
auto & operator++()
Definition: stream.h:725
View trim(const SafeConstIterator &nbegin) const
Definition: stream.h:1255
Stream(const Stream &other) noexcept
Definition: stream.h:1463
integer::safe< int64_t > operator-(const UnsafeConstIterator &other) const
Definition: stream.h:778
SafeConstIterator at(Offset offset) const
Definition: stream.h:1248
auto & operator++()
Definition: stream.h:415
std::string fmt(const char *fmt, const Args &... args)
Definition: fmt.h:13
View sub(Offset from, Offset to) const
Definition: stream.h:1237
std::tuple< bool, SafeConstIterator > find(const Bytes &v, const SafeConstIterator &n, Direction d=Direction::Forward) const
Definition: stream.h:1158
Offset offset() const
Definition: stream.h:409
View view(bool expanding=true) const
Definition: stream.h:1580
auto operator-(integer::safe< uint64_t > i) const
Definition: stream.h:767
uint64_t size
Definition: stream.h:1326