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 { Forward, Backward };
62 
63 namespace detail {
64 
65 class Chain;
69 
82 class Chunk {
83 public:
84  static const int SmallBufferSize = 32;
85  using Array = std::pair<Size, std::array<Byte, SmallBufferSize>>;
86  using Vector = std::vector<Byte>;
87 
88  Chunk(Offset o, std::array<Byte, SmallBufferSize>&& d, Size n)
89  : _offset(o), _data(std::make_pair(n, std::move(d))) {}
90  Chunk(Offset o, Vector&& d) : _offset(o), _data(std::move(d)) {}
91  Chunk(Offset o, const View& d);
92  Chunk(Offset o, const std::string& s);
93 
94  template<int N>
95  Chunk(Offset o, std::array<Byte, N> d) : Chunk(_fromArray(o, std::move(d))) {}
96  Chunk(Offset o, const char* d, Size n) : Chunk(_fromArray(o, d, n)) {}
97 
98  Chunk(const Chunk& other) : _offset(other._offset), _data(other._data) {}
99  Chunk(Chunk&& other) noexcept
100  : _offset(other._offset), _data(std::move(other._data)), _next(std::move(other._next)) {}
101 
102  Chunk& operator=(const Chunk& other) = delete;
103 
104  Chunk& operator=(Chunk&& other) noexcept {
105  _offset = other._offset;
106  _data = std::move(other._data);
107  _next = std::move(other._next);
108  _chain = std::move(other._chain);
109  return *this;
110  }
111 
112  ~Chunk() = default;
113 
114  Offset offset() const { return _offset; }
115  Offset endOffset() const { return _offset + size(); }
116  bool isCompact() const { return std::holds_alternative<Array>(_data); }
117  bool inRange(Offset offset) const { return offset >= _offset && offset < endOffset(); }
118 
119  const Byte* data() const {
120  if ( auto a = std::get_if<Array>(&_data) )
121  return a->second.data();
122  else {
123  auto& v = std::get<Vector>(_data);
124  return v.data();
125  }
126  }
127 
128  const Byte* data(Offset offset) const {
129  assert(inRange(offset));
130  return data() + (offset - _offset).Ref();
131  }
132 
133  const Byte* endData() const {
134  if ( auto a = std::get_if<Array>(&_data) )
135  return a->second.data() + a->first.Ref();
136  else {
137  auto& v = std::get<Vector>(_data);
138  return v.data() + v.size();
139  }
140  }
141 
142  Size size() const {
143  if ( auto a = std::get_if<Array>(&_data) )
144  return a->first;
145 
146  auto& v = std::get<Vector>(_data);
147  return v.size();
148  }
149 
150  bool isLast() const { return ! _next.get(); }
151  const Chunk* next() const { return _next.get(); }
152 
153  auto last() const {
154  const Chunk* i = this;
155  while ( i && i->_next )
156  i = i->_next.get();
157  return i;
158  }
159 
160  auto last() {
161  Chunk* i = this;
162  while ( i && i->_next )
163  i = i->_next.get();
164  return i;
165  }
166 
167  void debugPrint(std::ostream& out) const;
168 
169 protected:
170  // All mutating functions are protected and are expected to be called
171  // only from chain so that it can track any changes.
172  friend class Chain;
173 
174  void trim(Offset o);
175 
176  // Update offset for current chunk and all others linked from it.
177  void setOffset(Offset o) {
178  auto c = this;
179  while ( c ) {
180  c->_offset = o;
181  o += c->size();
182  c = c->next();
183  }
184  }
185 
186  // Set chain for current chunk and all others linked from it.
187  void setChain(const Chain* chain) {
188  auto x = this;
189  while ( x ) {
190  x->_chain = chain;
191  x = x->_next.get();
192  }
193  }
194 
195  Chunk* next() { return _next.get(); }
196 
197  // Link in chunk as successor of current one. Updates offset/chain for
198  // the appended chunk and all its successors.
199  void setNext(std::unique_ptr<Chunk> next) {
200  assert(_chain);
201 
202  Offset offset = endOffset();
203  _next = std::move(next);
204 
205  auto c = _next.get();
206  while ( c ) {
207  c->_offset = offset;
208  c->_chain = _chain;
209  offset += c->size();
210  c = c->_next.get();
211  }
212  }
213 
214  void clearNext() { _next = nullptr; }
215 
216 private:
217  inline Chunk _fromArray(Offset o, const char* d, Size n) {
218  auto ud = reinterpret_cast<const Byte*>(d);
219 
220  if ( n <= Chunk::SmallBufferSize ) {
221  std::array<Byte, Chunk::SmallBufferSize> x{};
222  std::copy(ud, ud + n.Ref(), x.data());
223  return Chunk(o, std::move(x), n);
224  }
225 
226  return Chunk(o, Chunk::Vector(ud, ud + n.Ref()));
227  }
228 
229  Offset _offset = 0; // global offset of 1st byte
230  std::variant<Array, Vector> _data; // content of this chunk
231  const Chain* _chain = nullptr; // chain this chunk is part of, or null if not linked to a chain yet (non-owning;
232  // will stay valid at least as long as the current chunk does)
233  std::unique_ptr<Chunk> _next = nullptr; // next chunk in chain, or null if last
234 };
235 
243 public:
246  using Size = stream::Size;
247 
248  Chain() {}
249 
251  Chain(std::unique_ptr<Chunk> head) : _head(std::move(head)), _tail(_head->last()) { _head->setChain(this); }
252 
253  Chain(Chain&& other) = delete;
254  Chain(const Chain& other) = delete;
255  Chain& operator=(const Chain& other) = delete;
256  Chain& operator=(const Chain&& other) = delete;
257 
258  const Chunk* head() const { return _head.get(); }
259  const Chunk* tail() const { return _tail; }
260  Size size() const { return (endOffset() - offset()).Ref(); }
261  bool isFrozen() const { return _state == State::Frozen; }
262  bool isValid() const { return _state != State::Invalid; }
263  bool inRange(Offset o) const { return o >= offset() && o < endOffset(); }
264 
265  Offset offset() const { return _head_offset; }
266  Offset endOffset() const { return _tail ? _tail->endOffset() : _head_offset; }
267 
268  // Finds the chunk containing *offset*. Returns null if not found.
269  // *hint_prev* may point to a chunk chained in before the target chunk,
270  // allowing that to be found more quickly. If given, *hint_prev* must be
271  // pointing to a current chunk of the chain, but it's ok if it's
272  // non-helpful for finding the target (i.e., pointing to a later chunk).
273  const Chunk* findChunk(Offset offset, const Chunk* hint_prev = nullptr) const;
274  Chunk* findChunk(Offset offset, Chunk* hint_prev = nullptr);
275 
276  // Returns a pointer to the byte at a given offset. Returns null if
277  // offset is out of range. See find() for semantics of *hint_prev*.
278  const Byte* data(Offset offset, Chunk* hint_prev = nullptr) const;
279 
280  SafeConstIterator begin() const;
281  SafeConstIterator end() const;
282  SafeConstIterator at(Offset offset) const;
283  UnsafeConstIterator unsafeBegin() const;
284  UnsafeConstIterator unsafeEnd() const;
285 
286  // Returns a newly allocated chain with the same content.
287  ChainPtr deepCopy() const;
288 
290  void append(std::unique_ptr<Chunk> chunk);
291  void append(Chain&& other);
292 
293  void trim(Offset offset);
294  void trim(const SafeConstIterator& i);
295  void trim(const UnsafeConstIterator& i);
296 
297  // Turns the chain into invalidated state, whill releases all chunks and
298  // will let attempts to dereference any still existing iterators fail.
299  void invalidate() {
300  _state = State::Invalid;
301  _head.reset();
302  _head_offset = 0;
303  _tail = nullptr;
304  }
305 
306  // Turns the chain into a freshly initialized state.
307  void reset() {
308  _state = State::Mutable;
309  _head.reset();
310  _head_offset = 0;
311  _tail = nullptr;
312  }
313 
314  void freeze() {
315  if ( isValid() )
316  _state = State::Frozen;
317  }
318  void unfreeze() {
319  if ( isValid() )
320  _state = State::Mutable;
321  }
322 
323  // Returns the number of dynamic chunks allocated.
324  int numberOfChunks() const;
325 
326 private:
327  void _ensureValid() const {
328  if ( ! isValid() )
329  throw InvalidIterator("stream object no longer available");
330  }
331 
332  void _ensureMutable() const {
333  if ( isFrozen() )
334  throw Frozen("stream object can no longer be modified");
335  }
336 
337  enum class State {
338  Mutable, // content can be expanded an trimmed
339  Frozen, // content cannot be changed
340  Invalid, // parent stream object has been destroyed, all content is invalid
341  };
342 
343  // Current state of chain
344  State _state = State::Mutable;
345 
346  // First chunk, or null if chain is empty.
347  std::unique_ptr<Chunk> _head = nullptr;
348 
349  // Offset of the beginning of chain. If head is set, this offset will
350  // match that of head. If head is not set, it'll contain the most recent
351  // end offset of the main (that's zero initially, but may be non-zero
352  // after trimming off all chunks).
353  Offset _head_offset = 0;
354 
355  // Always pointing to last chunk reachable from *head*, or null if chain
356  // is empty; non-owning
357  Chunk* _tail = nullptr;
358 };
359 
360 } // namespace detail
361 
376 public:
377  using Byte = stream::Byte;
381  using Offset = stream::Offset;
382  using Size = stream::Size;
384 
386  SafeConstIterator() = default;
387 
389  explicit SafeConstIterator(const UnsafeConstIterator& i);
390 
392  Offset offset() const { return _offset; }
393 
395  bool isFrozen() const { return ! _chain || _chain->isFrozen(); }
396 
398  auto& operator++() {
399  _increment(1);
400  return *this;
401  }
402 
404  auto operator++(int) {
405  auto x = *this;
406  _increment(1);
407  return x;
408  }
409 
411  auto& operator+=(integer::safe<uint64_t> i) {
412  _increment(i);
413  return *this;
414  }
415 
417  auto& operator--() {
418  _decrement(1);
419  return *this;
420  }
421 
423  auto operator--(int) {
424  auto x = *this;
425  _decrement(1);
426  return x;
427  }
428 
430  auto& operator-=(integer::safe<uint64_t> i) {
431  _decrement(i);
432  return *this;
433  }
434 
436  auto operator*() const { return _dereference(); }
437 
439  auto operator+(integer::safe<uint64_t> i) const {
440  auto x = *this;
441  x._increment(i);
442  return x;
443  }
444 
446  auto operator-(integer::safe<uint64_t> i) const {
447  auto x = *this;
448  x._decrement(i);
449  return x;
450  }
451 
457  integer::safe<int64_t> operator-(const SafeConstIterator& other) const {
458  _ensureSameChain(other);
459  return static_cast<int64_t>(_offset) - static_cast<int64_t>(other._offset);
460  }
461 
467  bool operator==(const SafeConstIterator& other) const {
468  _ensureSameChain(other);
469  return (_offset == other._offset) || (isEnd() && other.isEnd());
470  }
471 
477  bool operator!=(const SafeConstIterator& other) const {
478  _ensureSameChain(other);
479  return ! (*this == other);
480  }
481 
483  bool operator<(const SafeConstIterator& other) const {
484  _ensureSameChain(other);
485  return offset() < other.offset();
486  }
487 
489  bool operator<=(const SafeConstIterator& other) const {
490  _ensureSameChain(other);
491  return offset() <= other.offset();
492  }
493 
495  bool operator>(const SafeConstIterator& other) const {
496  _ensureSameChain(other);
497  return offset() > other.offset();
498  }
499 
501  bool operator>=(const SafeConstIterator& other) const {
502  _ensureSameChain(other);
503  return offset() >= other.offset();
504  }
505 
507  explicit operator bool() const { return ! isUnset(); }
508 
509  std::ostream& operator<<(std::ostream& out) const {
510  out << to_string(*this);
511  return out;
512  }
513 
515  bool isUnset() const { return ! _chain; }
516 
521  bool isExpired() const {
522  if ( ! _chain )
523  return false;
524 
525  return ! _chain->isValid();
526  }
527 
532  bool isValid() const { return ! isUnset() && ! isExpired(); }
533 
539  bool isEnd() const {
540  if ( ! _chain )
541  return true;
542 
543  _ensureValidChain();
544  return _offset >= _chain->endOffset();
545  }
546 
551  void debugPrint(std::ostream& out) const;
552 
553 protected:
554  friend class hilti::rt::stream::View;
557 
558  // Returns the chunk only if it's a valid pointer, other null. See
559  // comment on `_chunk` validity below.
560  const Chunk* chunk() const { return _chain && _chain->isValid() && _chain->inRange(_offset) ? _chunk : nullptr; }
561  const Chain* chain() const { return _chain.get(); }
562 
563 private:
564  SafeConstIterator(ConstChainPtr chain, Offset offset, const Chunk* chunk)
565  : _chain(chain), _offset(offset), _chunk(chunk) {
566  assert(! isUnset());
567  }
568 
569  void _ensureValidChain() const {
570  // This must have been checked at this point already.
571  assert(_chain);
572 
573  if ( ! _chain->isValid() )
574  throw InvalidIterator("stream object no longer available");
575  }
576 
577  void _ensureSameChain(const SafeConstIterator& other) const {
578  if ( ! (_chain && other._chain) )
579  // One is the default constructed end iterator; that's ok.
580  return;
581 
582  if ( ! other.isValid() )
583  throw InvalidIterator("stream object no longer available");
584 
585  if ( _chain != other._chain )
586  throw InvalidIterator("incompatible iterators");
587  }
588 
589  void _increment(integer::safe<uint64_t> n) {
590  if ( ! _chain )
591  throw InvalidIterator("unbound stream iterator");
592 
593  if ( ! n )
594  return;
595 
596  _offset += n;
597 
598  if ( ! (_chain && _chain->isValid()) )
599  return; // will be caught when dereferenced
600 
601  _chunk = _chain->findChunk(_offset, chunk());
602  // chunk will be null if we're pointing beyond the end.
603  }
604 
605  void _decrement(integer::safe<uint64_t> n) {
606  if ( ! _chain )
607  throw InvalidIterator("unbound stream iterator");
608 
609  if ( n > _offset )
610  throw InvalidIterator("attempt to move before beginning of stream");
611 
612  if ( ! n )
613  return;
614 
615  _offset -= n;
616 
617  if ( _chunk && _offset > _chunk->offset() )
618  return; // fast-path, chunk still valid
619 
620  if ( ! (_chain && _chain->isValid()) )
621  return; // will be caught when dereferenced
622 
623  _chunk = _chain->findChunk(_offset, _chunk);
624  // chunk will be null if we're pointing beyond the beginning.
625  }
626 
627  Byte _dereference() const {
628  if ( ! _chain )
629  throw InvalidIterator("unbound stream iterator");
630 
631  _ensureValidChain();
632 
633  if ( ! _chain->inRange(_offset) )
634  throw InvalidIterator("stream iterator outside of valid range");
635 
636  auto c = _chain->findChunk(_offset, chunk());
637  assert(c);
638  return *c->data(_offset);
639  }
640 
641  // Parent chain if bound, or null if not. The parent will stay around for
642  // at least as long as this iterator.
643  ConstChainPtr _chain = nullptr;
644 
645  // Global offset inside parent chain. This can be pointing to anywhere
646  // inside the stream's sequence space, including potentially being
647  // outside of the chain's valid range. It may always be accessed, even if
648  // the iterator is unbound, or the chain not valid anymore; it will then
649  // generally reflect the most recent value, which may or may not
650  // semantically make sense.
651  Offset _offset = 0;
652 
653  // A chunk from which *_offset* is reachable (i.e., the chunk either
654  // contains the offset, or we can get to the right chunk by following its
655  // successors). The chunk is null if our current offset is outside of the
656  // chains valid range.
657  //
658  // This chunk pointer is only valid for access if (1) *_chain* is set and
659  // valid; and (2) _offset is inside the chain's valid range. It will then
660  // point to a chunk from which _offset is *reachable*. (If these two are
661  // not satisified, the chunk may be pointing into freed memory!)
662  const Chunk* _chunk = nullptr;
663 };
664 
665 inline std::ostream& operator<<(std::ostream& out, const SafeConstIterator& x) {
666  out << to_string(x);
667  return out;
668 }
669 
680 namespace detail {
681 
683 public:
684  using Byte = stream::Byte;
688  using Offset = stream::Offset;
689  using Size = stream::Size;
690 
692  UnsafeConstIterator() = default;
693 
695  explicit UnsafeConstIterator(const SafeConstIterator& i);
696 
698  Offset offset() const { return _offset; }
699 
701  bool isFrozen() const { return ! _chain || _chain->isFrozen(); }
702 
704  auto& operator++() {
705  _increment(1);
706  return *this;
707  }
708 
710  auto operator++(int) {
711  auto x = *this;
712  _increment(1);
713  return x;
714  }
715 
717  auto& operator--() {
718  _decrement(1);
719  return *this;
720  }
721 
723  auto operator--(int) {
724  auto x = *this;
725  _decrement(1);
726  return x;
727  }
728 
730  auto& operator-=(integer::safe<uint64_t> i) {
731  _decrement(i);
732  return *this;
733  }
734 
736  auto operator*() const { return _dereference(); }
737 
739  auto operator+(integer::safe<uint64_t> i) const {
740  auto x = *this;
741  x._increment(i);
742  return x;
743  }
744 
746  auto operator-(integer::safe<uint64_t> i) const {
747  auto x = *this;
748  x._decrement(i);
749  return x;
750  }
751 
757  integer::safe<int64_t> operator-(const UnsafeConstIterator& other) const {
758  return static_cast<int64_t>(_offset) - static_cast<int64_t>(other._offset);
759  }
760 
766  bool operator==(const UnsafeConstIterator& other) const {
767  return (_offset == other._offset) || (isEnd() && other.isEnd());
768  }
769 
775  bool operator!=(const UnsafeConstIterator& other) const { return ! (*this == other); }
776 
778  bool operator<(const UnsafeConstIterator& other) const { return offset() < other.offset(); }
779 
781  bool operator<=(const UnsafeConstIterator& other) const { return offset() <= other.offset(); }
782 
784  bool operator>(const UnsafeConstIterator& other) const { return offset() > other.offset(); }
785 
787  bool operator>=(const UnsafeConstIterator& other) const { return offset() >= other.offset(); }
788 
790  explicit operator bool() const { return ! isUnset(); }
791 
792  std::ostream& operator<<(std::ostream& out) const {
793  out << to_string(*this);
794  return out;
795  }
796 
798  bool isUnset() const { return ! _chain; }
799 
804  bool isExpired() const {
805  if ( ! _chain )
806  return false;
807 
808  return ! _chain->isValid();
809  }
810 
815  bool isValid() const { return ! isUnset() && ! isExpired(); }
816 
818  bool isEnd() const {
819  if ( ! _chain )
820  return true;
821 
822  return _offset >= _chain->endOffset();
823  }
824 
829  void debugPrint(std::ostream& out) const;
830 
831 protected:
832  friend class hilti::rt::stream::View;
835 
836  const Chunk* chunk() const { return _chunk; }
837  const Chain* chain() const { return _chain; }
838 
839 private:
840  UnsafeConstIterator(ConstChainPtr chain, Offset offset, const Chunk* chunk)
841  : _chain(chain.get()), _offset(offset), _chunk(chunk) {
842  assert(! isUnset());
843  }
844 
845  UnsafeConstIterator(const Chain* chain, Offset offset, const Chunk* chunk)
846  : _chain(chain), _offset(offset), _chunk(chunk) {
847  assert(! isUnset());
848  }
849 
850  void _increment(integer::safe<uint64_t> n) {
851  _offset += n;
852 
853  if ( _chunk && _offset < _chunk->endOffset() )
854  return; // fast-path, chunk still valid
855 
856  _chunk = _chain->findChunk(_offset, _chunk);
857  }
858 
859  void _decrement(integer::safe<uint64_t> n) {
860  _offset -= n;
861 
862  if ( _chunk && _offset > _chunk->offset() )
863  return; // fast-path, chunk still valid
864 
865  _chunk = _chain->findChunk(_offset, _chunk);
866  }
867 
868  Byte _dereference() const {
869  // TODO(bbannier): Ideally we would `assert(_chunk)` here so clang-tidy
870  // knows that `_chunk` is always not null. Unfortunately it looks like
871  // that fails to it pruning that CFG edge so we have to return instead
872  // here. This should be inconsequential to users as this function must
873  // not be called if the data is invalid.
874  if ( ! _chunk )
875  internalError("dereference of invalid iterator");
876 
877  auto* byte = _chunk->data(_offset);
878 
879  return *byte;
880  }
881 
882  // Parent chain if bound, or null if not. This is a raw, non-owning
883  // pointer that assumes the parent chain will stick around as long as
884  // needed.
885  const Chain* _chain = nullptr;
886 
887  // Global offset inside parent chain. This can be pointing to anywhere
888  // inside the stream's sequence space, including potentially being
889  // outside of the chain's valid range.
890  Offset _offset = 0;
891 
892  // The chunk containing the current offset, or null if offset is out of
893  // bounds. This a raw, non-owning pointer that assumes the chunk will
894  // stick aroud as long as needed.
895  const Chunk* _chunk = nullptr;
896 };
897 
899  : _chain(i._chain.get()), _offset(i._offset), _chunk(i._chain ? i._chain->findChunk(_offset, i._chunk) : nullptr) {}
900 
901 inline std::ostream& operator<<(std::ostream& out, const UnsafeConstIterator& x) {
902  out << to_string(x);
903  return out;
904 }
905 
906 template<int N>
907 inline UnsafeConstIterator _extract(Byte* dst, const UnsafeConstIterator& i) {
908  *dst = *i;
909  return _extract<N - 1>(dst + 1, i + 1);
910 }
911 
912 template<>
913 inline UnsafeConstIterator _extract<0>(Byte* /* dst */, const UnsafeConstIterator& i) {
914  return i;
915 }
916 
917 template<int N>
918 inline UnsafeConstIterator extract(Byte* dst, const UnsafeConstIterator& i, const UnsafeConstIterator& end) {
919  if ( end.offset() - i.offset() < N )
920  throw WouldBlock("end of stream view");
921 
922  return _extract<N>(dst, i);
923 }
924 
925 inline SafeConstIterator Chain::begin() const {
926  _ensureValid();
927  return {ConstChainPtr(intrusive_ptr::NewRef(), this), offset(), _head.get()};
928 }
929 
930 inline SafeConstIterator Chain::end() const {
931  _ensureValid();
932  return {ConstChainPtr(intrusive_ptr::NewRef(), this), endOffset(), _tail};
933 }
934 
935 inline SafeConstIterator Chain::at(Offset offset) const {
936  return {ConstChainPtr(intrusive_ptr::NewRef(), this), offset, findChunk(offset)};
937 }
938 
939 inline UnsafeConstIterator Chain::unsafeBegin() const {
940  _ensureValid();
941  return {ConstChainPtr(intrusive_ptr::NewRef(), this), offset(), _head.get()};
942 }
943 inline UnsafeConstIterator Chain::unsafeEnd() const {
944  _ensureValid();
945  return {ConstChainPtr(intrusive_ptr::NewRef(), this), endOffset(), _tail};
946 }
947 
948 inline void Chain::trim(const SafeConstIterator& i) {
949  if ( ! i.chain() ) {
950  // Unbound end operator, trim all content off.
951  trim(endOffset());
952  return;
953  }
954 
955  if ( i.chain() != this )
956  throw InvalidIterator("incompatible iterator");
957 
958  if ( ! i.isValid() )
959  throw InvalidIterator("stream object no longer available");
960 
961  trim(i.offset());
962 }
963 
964 inline void Chain::trim(const UnsafeConstIterator& i) { trim(i.offset()); }
965 
966 } // namespace detail
967 
969  : _chain(detail::ConstChainPtr(intrusive_ptr::NewRef(), i._chain)), _offset(i._offset), _chunk(i._chunk) {}
970 
978 class View {
979 public:
980  using Byte = stream::Byte;
984  using Offset = stream::Offset;
985  using Size = stream::Size;
987 
989  View() = default;
990 
992  virtual ~View();
993 
995  explicit View(SafeConstIterator begin, SafeConstIterator end) : _begin(std::move(begin)), _end(std::move(end)) {
996  _ensureValid();
997 
998  if ( ! _end->_chain )
999  _end = _begin.chain()->end();
1000  else
1001  _ensureSameChain(*_end);
1002  }
1003 
1009  explicit View(SafeConstIterator begin) : _begin(std::move(begin)) {}
1010 
1015  Offset offset() const { return _begin.offset(); }
1016 
1022  Size size() const;
1023 
1025  bool isEmpty() const { return size() == 0; }
1026 
1028  bool isFrozen() const { return _begin.isFrozen(); }
1029 
1035  bool isOpenEnded() const { return ! _end.has_value(); }
1036 
1043  SafeConstIterator find(Byte b) const {
1044  _ensureValid();
1045  return SafeConstIterator(find(b, UnsafeConstIterator()));
1046  }
1047 
1055  SafeConstIterator find(Byte b, const SafeConstIterator& n) const {
1056  _ensureValid();
1057  _ensureSameChain(n);
1058  return SafeConstIterator(find(b, UnsafeConstIterator(n)));
1059  }
1060 
1068  UnsafeConstIterator find(Byte b, UnsafeConstIterator n) const;
1069 
1079  std::tuple<bool, SafeConstIterator> find(const View& v) const {
1080  _ensureValid();
1081  auto x = find(v, UnsafeConstIterator());
1082  return std::make_tuple(std::get<0>(x), SafeConstIterator(std::get<1>(x)));
1083  }
1084 
1095  std::tuple<bool, SafeConstIterator> find(const View& v, const SafeConstIterator& n) const {
1096  _ensureValid();
1097  _ensureSameChain(n);
1098  auto x = find(v, UnsafeConstIterator(n));
1099  return std::make_tuple(std::get<0>(x), SafeConstIterator(std::get<1>(x)));
1100  }
1101 
1112  std::tuple<bool, UnsafeConstIterator> find(const View& v, UnsafeConstIterator n) const;
1113 
1124  std::tuple<bool, SafeConstIterator> find(const Bytes& v, Direction d = Direction::Forward) const {
1125  _ensureValid();
1126  auto i = (d == Direction::Forward ? unsafeBegin() : unsafeEnd());
1127  auto x = find(v, std::move(i), d);
1128  return std::make_tuple(std::get<0>(x), SafeConstIterator(std::get<1>(x)));
1129  }
1130 
1142  std::tuple<bool, SafeConstIterator> find(const Bytes& v, const SafeConstIterator& n,
1143  Direction d = Direction::Forward) const {
1144  _ensureValid();
1145  _ensureSameChain(n);
1146  auto x = find(v, UnsafeConstIterator(n), d);
1147  return std::make_tuple(std::get<0>(x), SafeConstIterator(std::get<1>(x)));
1148  }
1149 
1161  std::tuple<bool, UnsafeConstIterator> find(const Bytes& v, UnsafeConstIterator n,
1162  Direction d = Direction::Forward) const {
1163  if ( d == Direction::Forward )
1164  return _findForward(v, std::move(n));
1165  else
1166  return _findBackward(v, std::move(n));
1167  }
1168 
1176  _ensureSameChain(i);
1177  return View(std::move(i), _end);
1178  }
1179 
1185  View advance(integer::safe<uint64_t> i) const { return View(begin() + i, _end); }
1186 
1194  _ensureSameChain(from);
1195  _ensureSameChain(to);
1196  return View(std::move(from), std::move(to));
1197  }
1198 
1206  _ensureSameChain(to);
1207  return View(begin(), std::move(to));
1208  }
1209 
1216  View sub(Offset from, Offset to) const { return View(begin() + from, begin() + to); }
1217 
1224  View sub(Offset to) const { return View(begin(), begin() + to); }
1225 
1227  SafeConstIterator at(Offset offset) const { return begin() + (offset - begin().offset()); }
1228 
1234  View trim(const SafeConstIterator& nbegin) const {
1235  _ensureSameChain(nbegin);
1236 
1237  if ( ! _end )
1238  return View(nbegin);
1239 
1240  if ( nbegin.offset() > _end->offset() )
1241  return View(*_end, *_end);
1242 
1243  return View(nbegin, *_end);
1244  }
1245 
1251  View limit(Offset incr) const { return View(begin(), begin() + incr); }
1252 
1260  template<int N>
1261  View extract(Byte (&dst)[N]) const {
1262  _ensureValid();
1263  return View(SafeConstIterator(detail::extract<N>(dst, unsafeBegin(), unsafeEnd())), _end);
1264  }
1265 
1272  void copyRaw(Byte* dst) const;
1273 
1275  Bytes data() const;
1276 
1279 
1282 
1284  const SafeConstIterator& begin() const { return _begin; }
1285 
1288  assert(_begin.chain());
1289  return _end ? *_end : _begin.chain()->end();
1290  }
1291 
1293  struct Block {
1294  const Byte* start;
1295  uint64_t size;
1296  uint64_t offset;
1297  bool is_first;
1298  bool is_last;
1300  };
1301 
1305  std::optional<Block> firstBlock() const;
1306 
1310  std::optional<Block> nextBlock(std::optional<Block> current) const;
1311 
1316  bool startsWith(const Bytes& b) const;
1317 
1318  bool operator==(const Bytes& other) const;
1319  bool operator==(const Stream& other) const;
1320  bool operator==(const View& other) const;
1321  bool operator!=(const Bytes& other) const { return ! (*this == other); }
1322  bool operator!=(const Stream& other) const { return ! (*this == other); }
1323  bool operator!=(const View& other) const { return ! (*this == other); }
1324 
1328  void debugPrint(std::ostream& out) const;
1329 
1330 private:
1331  View(SafeConstIterator begin, std::optional<SafeConstIterator> end)
1332  : _begin(std::move(begin)), _end(std::move(end)) {
1333  if ( _end )
1334  _ensureSameChain(*_end);
1335  }
1336 
1337  void _ensureSameChain(const SafeConstIterator& other) const {
1338  if ( _begin.chain() != other.chain() )
1339  throw InvalidIterator("incompatible iterator");
1340  }
1341 
1342  void _ensureValid() const {
1343  // if ( ! _begin.chain() )
1344  // throw InvalidIterator("view has invalid beginning");
1345 
1346  // if ( ! _begin.isValid() )
1347  // throw InvalidIterator("view has invalid beginning");
1348 
1349  if ( _end && ! _end->isValid() )
1350  throw InvalidIterator("view has invalid end");
1351  }
1352 
1353  // Common backend for backward searching.
1354  std::tuple<bool, UnsafeConstIterator> _findBackward(const Bytes& v, UnsafeConstIterator n) const;
1355 
1356  // Common backend for forward searching.
1357  std::tuple<bool, UnsafeConstIterator> _findForward(const Bytes& v, UnsafeConstIterator n) const;
1358 
1359  SafeConstIterator _begin;
1360  std::optional<SafeConstIterator> _end;
1361 };
1362 
1363 inline std::ostream& operator<<(std::ostream& out, const View& x) {
1364  out << escapeBytes(x.data().str());
1365  return out;
1366 }
1367 } // namespace stream
1368 
1379 class Stream {
1380 private:
1381  using Byte = stream::Byte;
1382  using Chain = stream::detail::Chain;
1384  using Chunk = stream::detail::Chunk;
1385  using Offset = stream::Offset;
1387  using Size = stream::Size;
1389  using View = stream::View;
1390 
1391 public:
1393  Stream() : _chain(make_intrusive<Chain>()) {}
1394 
1399  explicit Stream(std::vector<Byte> d) : Stream(Chunk(0, std::move(d))) {}
1400 
1405  explicit Stream(const Bytes& d);
1406 
1411  explicit Stream(const char* d) : Stream(Chunk(0, d, strlen(d))) {}
1412 
1414  Stream(const char* d, Size n) : Stream(Chunk(0, d, n)) {}
1415 
1420  Stream(const stream::View& d) : Stream(Chunk(0, d)) {}
1421 
1426  template<int N>
1427  Stream(std::vector<std::array<Byte, N>> d) : Stream(chunkFromArray(0, std::move(d))) {}
1428 
1433  Stream(const Stream& other) noexcept : _chain(other._chain->deepCopy()) {}
1434 
1439  Stream(Stream&& other) noexcept : _chain(std::move(other._chain)) { other._chain = make_intrusive<Chain>(); }
1440 
1445  Stream& operator=(Stream&& other) noexcept {
1446  if ( &other == this )
1447  return *this;
1448 
1449  _chain->invalidate();
1450  _chain = std::move(other._chain);
1451  other._chain = make_intrusive<Chain>();
1452  return *this;
1453  }
1454 
1459  Stream& operator=(const Stream& other) {
1460  if ( &other == this )
1461  return *this;
1462 
1463  _chain->invalidate();
1464  _chain = other._chain->deepCopy();
1465  return *this;
1466  }
1467 
1470  assert(_chain);
1471  _chain->invalidate();
1472  }
1473 
1475  Size size() const { return _chain->size(); }
1476 
1478  bool isEmpty() const { return _chain->size() == 0; }
1479 
1484  void append(const Bytes& data);
1485 
1490  void append(Bytes&& data);
1491 
1496  void append(std::unique_ptr<const Byte*> data);
1497 
1502  void append(const char* data, size_t len);
1503 
1512  void trim(const SafeConstIterator& i) { _chain->trim(i); }
1513 
1515  void freeze() { _chain->freeze(); }
1516 
1518  void unfreeze() { _chain->unfreeze(); }
1519 
1521  bool isFrozen() const { return _chain->isFrozen(); }
1522 
1524  SafeConstIterator begin() const { return _chain->begin(); }
1525 
1527  SafeConstIterator end() const { return _chain->end(); }
1528 
1530  UnsafeConstIterator unsafeBegin() const { return _chain->unsafeBegin(); }
1531 
1533  UnsafeConstIterator unsafeEnd() const { return _chain->unsafeEnd(); }
1534 
1539  SafeConstIterator at(Offset offset) const { return _chain->at(offset); }
1540 
1547  View view(bool expanding = true) const { return expanding ? View(begin()) : View(begin(), end()); }
1548 
1553  Bytes data() const;
1554 
1555  bool operator==(const Bytes& other) const { return view() == other; }
1556  bool operator==(const Stream& other) const { return view() == other.view(); }
1557  bool operator==(const stream::View& other) const { return view() == other; }
1558  bool operator!=(const Bytes& other) const { return ! (*this == other); }
1559  bool operator!=(const Stream& other) const { return ! (*this == other); }
1560  bool operator!=(const stream::View& other) const { return ! (*this == other); }
1561 
1566  int numberOfChunks() const { return _chain->numberOfChunks(); }
1567 
1571  void debugPrint(std::ostream& out) const;
1572 
1576  static void debugPrint(std::ostream& out, const stream::detail::Chain* chain);
1577 
1578 private:
1579  Stream(Chunk&& ch) : _chain(make_intrusive<Chain>(std::make_unique<Chunk>(std::move(ch)))) {}
1580 
1581  ChainPtr _chain; // always non-null
1582 };
1583 
1584 inline std::ostream& operator<<(std::ostream& out, const Stream& x) {
1585  out << escapeBytes(x.data().str());
1586  return out;
1587 }
1588 
1589 template<>
1590 inline std::string detail::to_string_for_print<Stream>(const Stream& x) {
1591  return escapeBytes(x.data().str(), true);
1592 }
1593 
1594 template<>
1595 inline std::string detail::to_string_for_print<stream::View>(const stream::View& x) {
1596  return escapeBytes(x.data().str(), true);
1597 }
1598 
1599 namespace detail::adl {
1600 inline std::string to_string(const Stream& x, adl::tag /*unused*/) {
1601  return fmt("b\"%s\"", escapeBytes(x.data().str(), true));
1602 }
1603 inline std::string to_string(const stream::View& x, adl::tag /*unused*/) {
1604  return fmt("b\"%s\"", escapeBytes(x.data().str(), true));
1605 }
1606 } // namespace detail::adl
1607 
1608 } // namespace hilti::rt
Chain(std::unique_ptr< Chunk > head)
Definition: stream.h:251
View extract(Byte(&dst)[N]) const
Definition: stream.h:1261
std::tuple< bool, SafeConstIterator > find(const Bytes &v, Direction d=Direction::Forward) const
Definition: stream.h:1124
std::string to_string(T &&x)
Definition: extension-points.h:26
Definition: exception.h:190
View sub(SafeConstIterator to) const
Definition: stream.h:1205
auto & operator+=(integer::safe< uint64_t > i)
Definition: stream.h:411
void trim(const SafeConstIterator &i)
Definition: stream.h:1512
View(SafeConstIterator begin)
Definition: stream.h:1009
bool operator>=(const UnsafeConstIterator &other) const
Definition: stream.h:787
auto operator*() const
Definition: stream.h:736
const detail::Chunk * _block
Definition: stream.h:1299
bool isUnset() const
Definition: stream.h:798
detail::UnsafeConstIterator unsafeBegin() const
Definition: stream.h:1278
SafeConstIterator end() const
Definition: stream.h:1527
SafeConstIterator at(Offset offset) const
Definition: stream.h:1539
Stream(const char *d)
Definition: stream.h:1411
Stream(const char *d, Size n)
Definition: stream.h:1414
std::tuple< bool, UnsafeConstIterator > find(const Bytes &v, UnsafeConstIterator n, Direction d=Direction::Forward) const
Definition: stream.h:1161
bool operator>(const SafeConstIterator &other) const
Definition: stream.h:495
bool operator<=(const UnsafeConstIterator &other) const
Definition: stream.h:781
Definition: intrusive-ptr.h:25
Definition: any.h:7
Bytes data() const
Definition: stream.cc:429
Stream & operator=(const Stream &other)
Definition: stream.h:1459
Offset offset() const
Definition: stream.h:1015
void internalError(const std::string &msg) __attribute__((noreturn))
Definition: logging.cc:18
uint64_t offset
Definition: stream.h:1296
auto & operator-=(integer::safe< uint64_t > i)
Definition: stream.h:730
Definition: optional.h:79
UnsafeConstIterator unsafeBegin() const
Definition: stream.h:1530
const Byte * start
Definition: stream.h:1294
Definition: intrusive-ptr.h:28
integer::safe< int64_t > operator-(const SafeConstIterator &other) const
Definition: stream.h:457
Definition: stream.h:1293
auto operator--(int)
Definition: stream.h:723
bool operator==(const UnsafeConstIterator &other) const
Definition: stream.h:766
SafeConstIterator begin() const
Definition: stream.h:1524
Definition: bytes.h:153
bool startsWith(const std::string &s, const std::string &prefix)
Definition: util.h:200
bool isEmpty() const
Definition: stream.h:1025
Stream & operator=(Stream &&other) noexcept
Definition: stream.h:1445
View sub(Offset to) const
Definition: stream.h:1224
Definition: stream.h:242
View limit(Offset incr) const
Definition: stream.h:1251
bool is_first
Definition: stream.h:1297
bool isEmpty() const
Definition: stream.h:1478
bool operator<=(const SafeConstIterator &other) const
Definition: stream.h:489
auto & operator--()
Definition: stream.h:717
bool operator<(const SafeConstIterator &other) const
Definition: stream.h:483
bool operator!=(const SafeConstIterator &other) const
Definition: stream.h:477
auto operator++(int)
Definition: stream.h:710
SafeConstIterator find(Byte b, const SafeConstIterator &n) const
Definition: stream.h:1055
Definition: stream.h:978
auto & operator--()
Definition: stream.h:417
bool isEnd() const
Definition: stream.h:818
auto operator--(int)
Definition: stream.h:423
detail::UnsafeConstIterator unsafeEnd() const
Definition: stream.h:1281
bool isValid() const
Definition: stream.h:815
void unfreeze()
Definition: stream.h:1518
bool isExpired() const
Definition: stream.h:804
int numberOfChunks() const
Definition: stream.h:1566
Offset offset() const
Definition: stream.h:698
View advance(SafeConstIterator i) const
Definition: stream.h:1175
Stream(const stream::View &d)
Definition: stream.h:1420
bool isFrozen() const
Definition: stream.h:701
bool isExpired() const
Definition: stream.h:521
std::tuple< bool, SafeConstIterator > find(const View &v) const
Definition: stream.h:1079
bool isValid() const
Definition: stream.h:532
bool operator!=(const UnsafeConstIterator &other) const
Definition: stream.h:775
bool isUnset() const
Definition: stream.h:515
View sub(SafeConstIterator from, SafeConstIterator to) const
Definition: stream.h:1193
View advance(integer::safe< uint64_t > i) const
Definition: stream.h:1185
Stream(std::vector< std::array< Byte, N >> d)
Definition: stream.h:1427
Stream(std::vector< Byte > d)
Definition: stream.h:1399
auto & operator-=(integer::safe< uint64_t > i)
Definition: stream.h:430
bool is_last
Definition: stream.h:1298
Definition: stream.h:1379
const std::string & str() const &
Definition: bytes.h:214
Definition: intrusive-ptr.h:69
Stream()
Definition: stream.h:1393
Stream(Stream &&other) noexcept
Definition: stream.h:1439
auto operator++(int)
Definition: stream.h:404
void debugPrint(std::ostream &out) const
Definition: stream.cc:489
Size size() const
Definition: stream.h:1475
bool isOpenEnded() const
Definition: stream.h:1035
bool isFrozen() const
Definition: stream.h:1521
bool isFrozen() const
Definition: stream.h:1028
bool operator==(const SafeConstIterator &other) const
Definition: stream.h:467
std::tuple< bool, SafeConstIterator > find(const View &v, const SafeConstIterator &n) const
Definition: stream.h:1095
auto operator*() const
Definition: stream.h:436
bool operator>=(const SafeConstIterator &other) const
Definition: stream.h:501
bool isEnd() const
Definition: stream.h:539
~Stream()
Definition: stream.h:1469
auto operator+(integer::safe< uint64_t > i) const
Definition: stream.h:439
View(SafeConstIterator begin, SafeConstIterator end)
Definition: stream.h:995
auto operator+(integer::safe< uint64_t > i) const
Definition: stream.h:739
UnsafeConstIterator unsafeEnd() const
Definition: stream.h:1533
SafeConstIterator end() const
Definition: stream.h:1287
std::string_view trim(std::string_view s, const std::string &chars) noexcept
Definition: util.h:112
const SafeConstIterator & begin() const
Definition: stream.h:1284
Definition: stream.h:82
bool isFrozen() const
Definition: stream.h:395
SafeConstIterator find(Byte b) const
Definition: stream.h:1043
bool operator>(const UnsafeConstIterator &other) const
Definition: stream.h:784
auto operator-(integer::safe< uint64_t > i) const
Definition: stream.h:446
Definition: stream.h:375
void freeze()
Definition: stream.h:1515
bool operator<(const UnsafeConstIterator &other) const
Definition: stream.h:778
Bytes data() const
Definition: stream.cc:425
auto & operator++()
Definition: stream.h:704
View trim(const SafeConstIterator &nbegin) const
Definition: stream.h:1234
Stream(const Stream &other) noexcept
Definition: stream.h:1433
integer::safe< int64_t > operator-(const UnsafeConstIterator &other) const
Definition: stream.h:757
SafeConstIterator at(Offset offset) const
Definition: stream.h:1227
auto & operator++()
Definition: stream.h:398
std::string fmt(const char *fmt, const Args &... args)
Definition: fmt.h:13
View sub(Offset from, Offset to) const
Definition: stream.h:1216
std::tuple< bool, SafeConstIterator > find(const Bytes &v, const SafeConstIterator &n, Direction d=Direction::Forward) const
Definition: stream.h:1142
Offset offset() const
Definition: stream.h:392
View view(bool expanding=true) const
Definition: stream.h:1547
auto operator-(integer::safe< uint64_t > i) const
Definition: stream.h:746
uint64_t size
Definition: stream.h:1295