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(const Offset& o, std::array<Byte, SmallBufferSize> d, const Size& n)
95  : _offset(o), _data(std::make_pair(n, d)) {}
96  Chunk(const Offset& o, Vector&& d) : _offset(o), _data(std::move(d)) {}
97  Chunk(const Offset& o, const View& d);
98  Chunk(const Offset& o, const std::string& s);
99 
100  template<int N>
101  Chunk(Offset o, std::array<Byte, N> d) : Chunk(_fromArray(o, std::move(d))) {}
102  Chunk(const Offset& o, const char* d, const Size& n) : Chunk(_fromArray(o, d, n)) {}
103 
104  // Constructs a gap chunk which signifies empty data.
105  Chunk(const Offset& o, size_t len) : _offset(o), _data(Gap{len}) {}
106 
107  Chunk(const Chunk& other) : _offset(other._offset), _data(other._data) {}
108  Chunk(Chunk&& other) noexcept
109  : _offset(other._offset), _data(std::move(other._data)), _next(std::move(other._next)) {}
110 
111  Chunk& operator=(const Chunk& other) = delete;
112 
113  Chunk& operator=(Chunk&& other) noexcept {
114  _offset = other._offset;
115  _data = std::move(other._data);
116  _next = std::move(other._next);
117  _chain = other._chain;
118  return *this;
119  }
120 
121  ~Chunk() = default;
122 
123  Offset offset() const { return _offset; }
124  Offset endOffset() const { return _offset + size(); }
125  bool isGap() const { return std::holds_alternative<Gap>(_data); }
126  bool inRange(const Offset& offset) const { return offset >= _offset && offset < endOffset(); }
127 
128  const Byte* data() const {
129  if ( auto a = std::get_if<Array>(&_data) )
130  return a->second.data();
131  else if ( auto a = std::get_if<Vector>(&_data) ) {
132  return a->data();
133  }
134  else if ( std::holds_alternative<Gap>(_data) )
135  throw MissingData("data is missing");
136 
138  }
139 
140  const Byte* data(const Offset& offset) const {
141  assert(inRange(offset));
142  return data() + (offset - _offset).Ref();
143  }
144 
145  const Byte* endData() const {
146  if ( auto a = std::get_if<Array>(&_data) )
147  return a->second.data() + a->first.Ref();
148  else if ( auto a = std::get_if<Vector>(&_data) ) {
149  return a->data() + a->size();
150  }
151  else if ( std::holds_alternative<Gap>(_data) )
152  throw MissingData("data is missing");
153 
155  }
156 
157  Size size() const {
158  if ( auto a = std::get_if<Array>(&_data) )
159  return a->first;
160  else if ( auto a = std::get_if<Vector>(&_data) )
161  return a->size();
162  else if ( auto a = std::get_if<Gap>(&_data) )
163  return a->size;
164 
166  }
167 
168  bool isLast() const { return ! _next; }
169  const Chunk* next() const { return _next.get(); }
170 
171  auto last() const {
172  const Chunk* i = this;
173  while ( i && i->_next )
174  i = i->_next.get();
175  return i;
176  }
177 
178  auto last() {
179  Chunk* i = this;
180  while ( i && i->_next )
181  i = i->_next.get();
182  return i;
183  }
184 
185  void debugPrint(std::ostream& out) const;
186 
187 protected:
188  // All mutating functions are protected and are expected to be called
189  // only from chain so that it can track any changes.
190  friend class Chain;
191 
192  void trim(const Offset& o);
193 
194  // Update offset for current chunk and all others linked from it.
195  void setOffset(Offset o) {
196  auto c = this;
197  while ( c ) {
198  c->_offset = o;
199  o += c->size();
200  c = c->next();
201  }
202  }
203 
204  // Set chain for current chunk and all others linked from it.
205  void setChain(const Chain* chain) {
206  auto x = this;
207  while ( x ) {
208  x->_chain = chain;
209  x = x->_next.get();
210  }
211  }
212 
213  Chunk* next() { return _next.get(); }
214 
215  // Link in chunk as successor of current one. Updates offset/chain for
216  // the appended chunk and all its successors.
217  void setNext(std::unique_ptr<Chunk> next) {
218  assert(_chain);
219 
220  Offset offset = endOffset();
221  _next = std::move(next);
222 
223  auto c = _next.get();
224  while ( c ) {
225  c->_offset = offset;
226  c->_chain = _chain;
227  offset += c->size();
228  c = c->_next.get();
229  }
230  }
231 
232  void clearNext() { _next = nullptr; }
233 
234 private:
235  inline Chunk _fromArray(const Offset& o, const char* d, const Size& n) {
236  auto ud = reinterpret_cast<const Byte*>(d);
237 
238  if ( n <= Chunk::SmallBufferSize ) {
239  std::array<Byte, Chunk::SmallBufferSize> x{};
240  std::copy(ud, ud + n.Ref(), x.data());
241  return Chunk(o, x, n);
242  }
243 
244  return Chunk(o, Chunk::Vector(ud, ud + n.Ref()));
245  }
246 
247  Offset _offset = 0; // global offset of 1st byte
248  std::variant<Array, Vector, Gap> _data; // content of this chunk
249  const Chain* _chain = nullptr; // chain this chunk is part of, or null if not linked to a chain yet (non-owning;
250  // will stay valid at least as long as the current chunk does)
251  std::unique_ptr<Chunk> _next = nullptr; // next chunk in chain, or null if last
252 };
253 
261 public:
264  using Size = stream::Size;
265 
266  Chain() {}
267 
269  Chain(std::unique_ptr<Chunk> head) : _head(std::move(head)), _tail(_head->last()) { _head->setChain(this); }
270 
271  Chain(Chain&& other) = delete;
272  Chain(const Chain& other) = delete;
273  Chain& operator=(const Chain& other) = delete;
274  Chain& operator=(const Chain&& other) = delete;
275 
276  const Chunk* head() const { return _head.get(); }
277  const Chunk* tail() const { return _tail; }
278  Size size() const { return (endOffset() - offset()).Ref(); }
279  bool isFrozen() const { return _state == State::Frozen; }
280  bool isValid() const { return _state != State::Invalid; }
281  bool inRange(const Offset& o) const { return o >= offset() && o < endOffset(); }
282 
283  Offset offset() const { return _head_offset; }
284  Offset endOffset() const { return _tail ? _tail->endOffset() : _head_offset; }
285 
286  // Finds the chunk containing *offset*. Returns null if not found.
287  // *hint_prev* may point to a chunk chained in before the target chunk,
288  // allowing that to be found more quickly. If given, *hint_prev* must be
289  // pointing to a current chunk of the chain, but it's ok if it's
290  // non-helpful for finding the target (i.e., pointing to a later chunk).
291  const Chunk* findChunk(const Offset& offset, const Chunk* hint_prev = nullptr) const;
292  Chunk* findChunk(const Offset& offset, Chunk* hint_prev = nullptr);
293 
294  // Returns a pointer to the byte at a given offset. Returns null if
295  // offset is out of range. See find() for semantics of *hint_prev*.
296  const Byte* data(const Offset& offset, Chunk* hint_prev = nullptr) const;
297 
298  SafeConstIterator begin() const;
299  SafeConstIterator end() const;
300  SafeConstIterator at(const Offset& offset) const;
301  UnsafeConstIterator unsafeBegin() const;
302  UnsafeConstIterator unsafeEnd() const;
303 
304  // Returns a newly allocated chain with the same content.
305  ChainPtr deepCopy() const;
306 
308  void append(std::unique_ptr<Chunk> chunk);
309  void append(Chain&& other);
310 
311  void trim(const Offset& offset);
312  void trim(const SafeConstIterator& i);
313  void trim(const UnsafeConstIterator& i);
314 
315  // Turns the chain into invalidated state, whill releases all chunks and
316  // will let attempts to dereference any still existing iterators fail.
317  void invalidate() {
318  _state = State::Invalid;
319  _head.reset();
320  _head_offset = 0;
321  _tail = nullptr;
322  }
323 
324  // Turns the chain into a freshly initialized state.
325  void reset() {
326  _state = State::Mutable;
327  _head.reset();
328  _head_offset = 0;
329  _tail = nullptr;
330  }
331 
332  void freeze() {
333  if ( isValid() )
334  _state = State::Frozen;
335  }
336  void unfreeze() {
337  if ( isValid() )
338  _state = State::Mutable;
339  }
340 
341  // Returns the number of dynamic chunks allocated.
342  int numberOfChunks() const;
343 
344 private:
345  void _ensureValid() const {
346  if ( ! isValid() )
347  throw InvalidIterator("stream object no longer available");
348  }
349 
350  void _ensureMutable() const {
351  if ( isFrozen() )
352  throw Frozen("stream object can no longer be modified");
353  }
354 
355  enum class State {
356  Mutable, // content can be expanded an trimmed
357  Frozen, // content cannot be changed
358  Invalid, // parent stream object has been destroyed, all content is invalid
359  };
360 
361  // Current state of chain
362  State _state = State::Mutable;
363 
364  // First chunk, or null if chain is empty.
365  std::unique_ptr<Chunk> _head = nullptr;
366 
367  // Offset of the beginning of chain. If head is set, this offset will
368  // match that of head. If head is not set, it'll contain the most recent
369  // end offset of the main (that's zero initially, but may be non-zero
370  // after trimming off all chunks).
371  Offset _head_offset = 0;
372 
373  // Always pointing to last chunk reachable from *head*, or null if chain
374  // is empty; non-owning
375  Chunk* _tail = nullptr;
376 };
377 
378 } // namespace detail
379 
394 public:
395  using Byte = stream::Byte;
399  using Offset = stream::Offset;
400  using Size = stream::Size;
402 
404  SafeConstIterator() = default;
405 
407  explicit SafeConstIterator(const UnsafeConstIterator& i);
408 
410  Offset offset() const { return _offset; }
411 
413  bool isFrozen() const { return ! _chain || _chain->isFrozen(); }
414 
416  auto& operator++() {
417  _increment(1);
418  return *this;
419  }
420 
422  auto operator++(int) {
423  auto x = *this;
424  _increment(1);
425  return x;
426  }
427 
429  auto& operator+=(const integer::safe<uint64_t>& i) {
430  _increment(i);
431  return *this;
432  }
433 
435  auto& operator--() {
436  _decrement(1);
437  return *this;
438  }
439 
441  auto operator--(int) {
442  auto x = *this;
443  _decrement(1);
444  return x;
445  }
446 
448  auto& operator-=(const integer::safe<uint64_t>& i) {
449  _decrement(i);
450  return *this;
451  }
452 
454  auto operator*() const { return _dereference(); }
455 
457  auto operator+(const integer::safe<uint64_t>& i) const {
458  auto x = *this;
459  x._increment(i);
460  return x;
461  }
462 
464  auto operator-(const integer::safe<uint64_t>& i) const {
465  auto x = *this;
466  x._decrement(i);
467  return x;
468  }
469 
475  integer::safe<int64_t> operator-(const SafeConstIterator& other) const {
476  _ensureSameChain(other);
477  return static_cast<int64_t>(_offset) - static_cast<int64_t>(other._offset);
478  }
479 
485  bool operator==(const SafeConstIterator& other) const {
486  _ensureSameChain(other);
487  return (_offset == other._offset) || (isEnd() && other.isEnd());
488  }
489 
495  bool operator!=(const SafeConstIterator& other) const {
496  _ensureSameChain(other);
497  return ! (*this == other);
498  }
499 
501  bool operator<(const SafeConstIterator& other) const {
502  _ensureSameChain(other);
503  return offset() < other.offset();
504  }
505 
507  bool operator<=(const SafeConstIterator& other) const {
508  _ensureSameChain(other);
509  return offset() <= other.offset();
510  }
511 
513  bool operator>(const SafeConstIterator& other) const {
514  _ensureSameChain(other);
515  return offset() > other.offset();
516  }
517 
519  bool operator>=(const SafeConstIterator& other) const {
520  _ensureSameChain(other);
521  return offset() >= other.offset();
522  }
523 
525  explicit operator bool() const { return ! isUnset(); }
526 
527  std::ostream& operator<<(std::ostream& out) const {
528  out << to_string(*this);
529  return out;
530  }
531 
533  bool isUnset() const { return ! _chain; }
534 
539  bool isExpired() const {
540  if ( ! _chain )
541  return false;
542 
543  return ! _chain->isValid();
544  }
545 
550  bool isValid() const { return ! isUnset() && ! isExpired(); }
551 
557  bool isEnd() const {
558  if ( ! _chain )
559  return true;
560 
561  _ensureValidChain();
562  return _offset >= _chain->endOffset();
563  }
564 
569  void debugPrint(std::ostream& out) const;
570 
571 protected:
572  friend class hilti::rt::stream::View;
575 
576  // Returns the chunk only if it's a valid pointer, other null. See
577  // comment on `_chunk` validity below.
578  const Chunk* chunk() const { return _chain && _chain->isValid() && _chain->inRange(_offset) ? _chunk : nullptr; }
579  const Chain* chain() const { return _chain.get(); }
580 
581 private:
582  SafeConstIterator(ConstChainPtr chain, const Offset& offset, const Chunk* chunk)
583  : _chain(std::move(chain)), _offset(offset), _chunk(chunk) {
584  assert(! isUnset());
585  }
586 
587  void _ensureValidChain() const {
588  // This must have been checked at this point already.
589  assert(_chain);
590 
591  if ( ! _chain->isValid() )
592  throw InvalidIterator("stream object no longer available");
593  }
594 
595  void _ensureSameChain(const SafeConstIterator& other) const {
596  if ( ! (_chain && other._chain) )
597  // One is the default constructed end iterator; that's ok.
598  return;
599 
600  if ( ! other.isValid() )
601  throw InvalidIterator("stream object no longer available");
602 
603  if ( _chain != other._chain )
604  throw InvalidIterator("incompatible iterators");
605  }
606 
607  void _increment(const integer::safe<uint64_t>& n) {
608  if ( ! _chain )
609  throw InvalidIterator("unbound stream iterator");
610 
611  if ( ! n )
612  return;
613 
614  _offset += n;
615 
616  if ( ! (_chain && _chain->isValid()) )
617  return; // will be caught when dereferenced
618 
619  _chunk = _chain->findChunk(_offset, chunk());
620  // chunk will be null if we're pointing beyond the end.
621  }
622 
623  void _decrement(const integer::safe<uint64_t>& n) {
624  if ( ! _chain )
625  throw InvalidIterator("unbound stream iterator");
626 
627  if ( n > _offset )
628  throw InvalidIterator("attempt to move before beginning of stream");
629 
630  if ( ! n )
631  return;
632 
633  _offset -= n;
634 
635  if ( _chunk && _offset > _chunk->offset() )
636  return; // fast-path, chunk still valid
637 
638  if ( ! (_chain && _chain->isValid()) )
639  return; // will be caught when dereferenced
640 
641  _chunk = _chain->findChunk(_offset, _chunk);
642  // chunk will be null if we're pointing beyond the beginning.
643  }
644 
645  Byte _dereference() const {
646  if ( ! _chain )
647  throw InvalidIterator("unbound stream iterator");
648 
649  _ensureValidChain();
650 
651  if ( ! _chain->inRange(_offset) )
652  throw InvalidIterator("stream iterator outside of valid range");
653 
654  auto c = _chain->findChunk(_offset, chunk());
655  assert(c);
656 
657  if ( c->isGap() )
658  throw MissingData("data is missing");
659 
660  return *c->data(_offset);
661  }
662 
663  // Parent chain if bound, or null if not. The parent will stay around for
664  // at least as long as this iterator.
665  ConstChainPtr _chain = nullptr;
666 
667  // Global offset inside parent chain. This can be pointing to anywhere
668  // inside the stream's sequence space, including potentially being
669  // outside of the chain's valid range. It may always be accessed, even if
670  // the iterator is unbound, or the chain not valid anymore; it will then
671  // generally reflect the most recent value, which may or may not
672  // semantically make sense.
673  Offset _offset = 0;
674 
675  // A chunk from which *_offset* is reachable (i.e., the chunk either
676  // contains the offset, or we can get to the right chunk by following its
677  // successors). The chunk is null if our current offset is outside of the
678  // chains valid range.
679  //
680  // This chunk pointer is only valid for access if (1) *_chain* is set and
681  // valid; and (2) _offset is inside the chain's valid range. It will then
682  // point to a chunk from which _offset is *reachable*. (If these two are
683  // not satisfied, the chunk may be pointing into freed memory!)
684  const Chunk* _chunk = nullptr;
685 };
686 
687 inline std::ostream& operator<<(std::ostream& out, const SafeConstIterator& x) {
688  out << to_string(x);
689  return out;
690 }
691 
702 namespace detail {
703 
705 public:
706  using Byte = stream::Byte;
710  using Offset = stream::Offset;
711  using Size = stream::Size;
712 
714  UnsafeConstIterator() = default;
715 
717  explicit UnsafeConstIterator(const SafeConstIterator& i);
718 
720  Offset offset() const { return _offset; }
721 
723  bool isFrozen() const { return ! _chain || _chain->isFrozen(); }
724 
726  auto& operator++() {
727  _increment(1);
728  return *this;
729  }
730 
732  auto operator++(int) {
733  auto x = *this;
734  _increment(1);
735  return x;
736  }
737 
739  auto& operator--() {
740  _decrement(1);
741  return *this;
742  }
743 
745  auto operator--(int) {
746  auto x = *this;
747  _decrement(1);
748  return x;
749  }
750 
752  auto& operator-=(const integer::safe<uint64_t>& i) {
753  _decrement(i);
754  return *this;
755  }
756 
758  auto operator*() const { return _dereference(); }
759 
761  auto operator+(const integer::safe<uint64_t>& i) const {
762  auto x = *this;
763  x._increment(i);
764  return x;
765  }
766 
768  auto operator-(const integer::safe<uint64_t>& i) const {
769  auto x = *this;
770  x._decrement(i);
771  return x;
772  }
773 
779  integer::safe<int64_t> operator-(const UnsafeConstIterator& other) const {
780  return static_cast<int64_t>(_offset) - static_cast<int64_t>(other._offset);
781  }
782 
788  bool operator==(const UnsafeConstIterator& other) const {
789  return (_offset == other._offset) || (isEnd() && other.isEnd());
790  }
791 
797  bool operator!=(const UnsafeConstIterator& other) const { return ! (*this == other); }
798 
800  bool operator<(const UnsafeConstIterator& other) const { return offset() < other.offset(); }
801 
803  bool operator<=(const UnsafeConstIterator& other) const { return offset() <= other.offset(); }
804 
806  bool operator>(const UnsafeConstIterator& other) const { return offset() > other.offset(); }
807 
809  bool operator>=(const UnsafeConstIterator& other) const { return offset() >= other.offset(); }
810 
812  explicit operator bool() const { return ! isUnset(); }
813 
814  std::ostream& operator<<(std::ostream& out) const {
815  out << to_string(*this);
816  return out;
817  }
818 
820  bool isUnset() const { return ! _chain; }
821 
826  bool isExpired() const {
827  if ( ! _chain )
828  return false;
829 
830  return ! _chain->isValid();
831  }
832 
837  bool isValid() const { return ! isUnset() && ! isExpired(); }
838 
840  bool isEnd() const {
841  if ( ! _chain )
842  return true;
843 
844  return _offset >= _chain->endOffset();
845  }
846 
851  void debugPrint(std::ostream& out) const;
852 
853 protected:
854  friend class hilti::rt::stream::View;
857 
858  const Chunk* chunk() const { return _chunk; }
859  const Chain* chain() const { return _chain; }
860 
861 private:
862  UnsafeConstIterator(const ConstChainPtr& chain, const Offset& offset, const Chunk* chunk)
863  : _chain(chain.get()), _offset(offset), _chunk(chunk) {
864  assert(! isUnset());
865  }
866 
867  UnsafeConstIterator(const Chain* chain, const Offset& offset, const Chunk* chunk)
868  : _chain(chain), _offset(offset), _chunk(chunk) {
869  assert(! isUnset());
870  }
871 
872  void _increment(const integer::safe<uint64_t>& n) {
873  _offset += n;
874 
875  if ( _chunk && _offset < _chunk->endOffset() )
876  return; // fast-path, chunk still valid
877 
878  _chunk = _chain->findChunk(_offset, _chunk);
879  }
880 
881  void _decrement(const integer::safe<uint64_t>& n) {
882  _offset -= n;
883 
884  if ( _chunk && _offset > _chunk->offset() )
885  return; // fast-path, chunk still valid
886 
887  _chunk = _chain->findChunk(_offset, _chunk);
888  }
889 
890  Byte _dereference() const {
891  // TODO(bbannier): Ideally we would `assert(_chunk)` here so clang-tidy
892  // knows that `_chunk` is always not null. Unfortunately it looks like
893  // that fails to it pruning that CFG edge so we have to return instead
894  // here. This should be inconsequential to users as this function must
895  // not be called if the data is invalid.
896  if ( ! _chunk )
897  internalError("dereference of invalid iterator");
898 
899  auto* byte = _chunk->data(_offset);
900 
901  if ( ! byte )
902  throw MissingData("data is missing");
903 
904  return *byte;
905  }
906 
907  // Parent chain if bound, or null if not. This is a raw, non-owning
908  // pointer that assumes the parent chain will stick around as long as
909  // needed.
910  const Chain* _chain = nullptr;
911 
912  // Global offset inside parent chain. This can be pointing to anywhere
913  // inside the stream's sequence space, including potentially being
914  // outside of the chain's valid range.
915  Offset _offset = 0;
916 
917  // The chunk containing the current offset, or null if offset is out of
918  // bounds. This a raw, non-owning pointer that assumes the chunk will
919  // stick around as long as needed.
920  const Chunk* _chunk = nullptr;
921 };
922 
924  : _chain(i.chain()), _offset(i.offset()), _chunk(i.chain() ? i.chain()->findChunk(_offset, i.chunk()) : nullptr) {}
925 
926 inline std::ostream& operator<<(std::ostream& out, const UnsafeConstIterator& x) {
927  out << to_string(x);
928  return out;
929 }
930 
931 inline SafeConstIterator Chain::begin() const {
932  _ensureValid();
933  return {ConstChainPtr(intrusive_ptr::NewRef(), this), offset(), _head.get()};
934 }
935 
936 inline SafeConstIterator Chain::end() const {
937  _ensureValid();
938  return {ConstChainPtr(intrusive_ptr::NewRef(), this), endOffset(), _tail};
939 }
940 
941 inline SafeConstIterator Chain::at(const Offset& offset) const {
942  return {ConstChainPtr(intrusive_ptr::NewRef(), this), offset, findChunk(offset)};
943 }
944 
945 inline UnsafeConstIterator Chain::unsafeBegin() const {
946  _ensureValid();
947  return {ConstChainPtr(intrusive_ptr::NewRef(), this), offset(), _head.get()};
948 }
949 inline UnsafeConstIterator Chain::unsafeEnd() const {
950  _ensureValid();
951  return {ConstChainPtr(intrusive_ptr::NewRef(), this), endOffset(), _tail};
952 }
953 
954 inline void Chain::trim(const SafeConstIterator& i) {
955  if ( ! i.chain() ) {
956  // Unbound end operator, trim all content off.
957  trim(endOffset());
958  return;
959  }
960 
961  if ( i.chain() != this )
962  throw InvalidIterator("incompatible iterator");
963 
964  if ( ! i.isValid() )
965  throw InvalidIterator("stream object no longer available");
966 
967  trim(i.offset());
968 }
969 
970 inline void Chain::trim(const UnsafeConstIterator& i) { trim(i.offset()); }
971 
972 } // namespace detail
973 
975  : _chain(detail::ConstChainPtr(intrusive_ptr::NewRef(), i._chain)), _offset(i._offset), _chunk(i._chunk) {}
976 
984 class View {
985 public:
986  using Byte = stream::Byte;
990  using Offset = stream::Offset;
991  using Size = stream::Size;
993 
995  View() = default;
996 
998  virtual ~View();
999 
1001  explicit View(SafeConstIterator begin, SafeConstIterator end) : _begin(std::move(begin)), _end(std::move(end)) {
1002  _ensureValid();
1003 
1004  if ( ! _end->_chain )
1005  _end = _begin.chain()->end();
1006  else
1007  _ensureSameChain(*_end);
1008  }
1009 
1015  explicit View(SafeConstIterator begin) : _begin(std::move(begin)) {}
1016 
1021  Offset offset() const { return _begin.offset(); }
1022 
1027  std::optional<Offset> endOffset() const {
1028  if ( _end )
1029  return _end->offset();
1030  else
1031  return std::nullopt;
1032  }
1033 
1039  Size size() const;
1040 
1042  bool isEmpty() const { return size() == 0; }
1043 
1045  bool isFrozen() const { return _begin.isFrozen(); }
1046 
1052  bool isOpenEnded() const { return ! _end.has_value(); }
1053 
1060  SafeConstIterator find(Byte b) const {
1061  _ensureValid();
1062  return SafeConstIterator(find(b, UnsafeConstIterator()));
1063  }
1064 
1072  SafeConstIterator find(Byte b, const SafeConstIterator& n) const {
1073  _ensureValid();
1074  _ensureSameChain(n);
1075  return SafeConstIterator(find(b, UnsafeConstIterator(n)));
1076  }
1077 
1085  UnsafeConstIterator find(Byte b, UnsafeConstIterator n) const;
1086 
1096  std::tuple<bool, SafeConstIterator> find(const View& v) const {
1097  _ensureValid();
1098  auto x = find(v, UnsafeConstIterator());
1099  return std::make_tuple(std::get<0>(x), SafeConstIterator(std::get<1>(x)));
1100  }
1101 
1112  std::tuple<bool, SafeConstIterator> find(const View& v, const SafeConstIterator& n) const {
1113  _ensureValid();
1114  _ensureSameChain(n);
1115  auto x = find(v, UnsafeConstIterator(n));
1116  return std::make_tuple(std::get<0>(x), SafeConstIterator(std::get<1>(x)));
1117  }
1118 
1129  std::tuple<bool, UnsafeConstIterator> find(const View& v, UnsafeConstIterator n) const;
1130 
1141  std::tuple<bool, SafeConstIterator> find(const Bytes& v, Direction d = Direction::Forward) const {
1142  _ensureValid();
1143  auto i = (d == Direction::Forward ? unsafeBegin() : unsafeEnd());
1144  auto x = find(v, std::move(i), d);
1145  return std::make_tuple(std::get<0>(x), SafeConstIterator(std::get<1>(x)));
1146  }
1147 
1159  std::tuple<bool, SafeConstIterator> find(const Bytes& v, const SafeConstIterator& n,
1160  Direction d = Direction::Forward) const {
1161  _ensureValid();
1162  _ensureSameChain(n);
1163  auto x = find(v, UnsafeConstIterator(n), d);
1164  return std::make_tuple(std::get<0>(x), SafeConstIterator(std::get<1>(x)));
1165  }
1166 
1178  std::tuple<bool, UnsafeConstIterator> find(const Bytes& v, UnsafeConstIterator n,
1179  Direction d = Direction::Forward) const {
1180  if ( d == Direction::Forward )
1181  return _findForward(v, std::move(n));
1182  else
1183  return _findBackward(v, std::move(n));
1184  }
1185 
1193  _ensureSameChain(i);
1194  return View(std::move(i), _end);
1195  }
1196 
1202  View advance(const integer::safe<uint64_t>& i) const { return View(begin() + i, _end); }
1203 
1207  View advanceToNextData() const;
1208 
1216  _ensureSameChain(from);
1217  _ensureSameChain(to);
1218  return View(std::move(from), std::move(to));
1219  }
1220 
1228  _ensureSameChain(to);
1229  return View(begin(), std::move(to));
1230  }
1231 
1238  View sub(const Offset& from, const Offset& to) const { return View(begin() + from, begin() + to); }
1239 
1246  View sub(const Offset& to) const { return View(begin(), begin() + to); }
1247 
1249  SafeConstIterator at(const Offset& offset) const { return begin() + (offset - begin().offset()); }
1250 
1256  View trim(const SafeConstIterator& nbegin) const {
1257  _ensureSameChain(nbegin);
1258 
1259  if ( ! _end )
1260  return View(nbegin);
1261 
1262  if ( nbegin.offset() > _end->offset() )
1263  return View(*_end, *_end);
1264 
1265  return View(nbegin, *_end);
1266  }
1267 
1273  View limit(const Offset& incr) const { return View(begin(), begin() + incr); }
1274 
1282  View extract(Byte* dst, uint64_t n) const {
1283  _ensureValid();
1284 
1285  if ( n > size() )
1286  throw WouldBlock("end of stream view");
1287 
1288  auto p = unsafeBegin();
1289  for ( int i = 0; i < n; ++i )
1290  dst[i] = *p++;
1291 
1292  return View(SafeConstIterator(p), _end);
1293  }
1294 
1301  void copyRaw(Byte* dst) const;
1302 
1304  Bytes data() const;
1305 
1307  std::string dataForPrint() const;
1308 
1311 
1314 
1316  const SafeConstIterator& begin() const { return _begin; }
1317 
1320  assert(_begin.chain());
1321  return _end ? *_end : _begin.chain()->end();
1322  }
1323 
1325  struct Block {
1326  const Byte* start;
1327  uint64_t size;
1328  uint64_t offset;
1329  bool is_first;
1330  bool is_last;
1332  };
1333 
1337  std::optional<Block> firstBlock() const;
1338 
1342  std::optional<Block> nextBlock(std::optional<Block> current) const;
1343 
1348  bool startsWith(const Bytes& b) const;
1349 
1350  bool operator==(const Bytes& other) const;
1351  bool operator==(const Stream& other) const;
1352  bool operator==(const View& other) const;
1353  bool operator!=(const Bytes& other) const { return ! (*this == other); }
1354  bool operator!=(const Stream& other) const { return ! (*this == other); }
1355  bool operator!=(const View& other) const { return ! (*this == other); }
1356 
1360  void debugPrint(std::ostream& out) const;
1361 
1362 private:
1363  View(SafeConstIterator begin, std::optional<SafeConstIterator> end)
1364  : _begin(std::move(begin)), _end(std::move(end)) {
1365  if ( _end )
1366  _ensureSameChain(*_end);
1367  }
1368 
1369  void _ensureSameChain(const SafeConstIterator& other) const {
1370  if ( _begin.chain() != other.chain() )
1371  throw InvalidIterator("incompatible iterator");
1372  }
1373 
1374  void _ensureValid() const {
1375  // if ( ! _begin.chain() )
1376  // throw InvalidIterator("view has invalid beginning");
1377 
1378  // if ( ! _begin.isValid() )
1379  // throw InvalidIterator("view has invalid beginning");
1380 
1381  if ( _end && ! _end->isValid() )
1382  throw InvalidIterator("view has invalid end");
1383  }
1384 
1385  // Common backend for backward searching.
1386  std::tuple<bool, UnsafeConstIterator> _findBackward(const Bytes& needle, UnsafeConstIterator i) const;
1387 
1388  // Common backend for forward searching.
1389  std::tuple<bool, UnsafeConstIterator> _findForward(const Bytes& v, UnsafeConstIterator n) const;
1390 
1391  SafeConstIterator _begin;
1392  std::optional<SafeConstIterator> _end;
1393 };
1394 
1395 inline std::ostream& operator<<(std::ostream& out, const View& x) { return out << hilti::rt::to_string_for_print(x); }
1396 } // namespace stream
1397 
1408 class Stream {
1409 private:
1410  using Byte = stream::Byte;
1411  using Chain = stream::detail::Chain;
1413  using Chunk = stream::detail::Chunk;
1414  using Offset = stream::Offset;
1416  using Size = stream::Size;
1418  using View = stream::View;
1419 
1420 public:
1422  Stream() : _chain(make_intrusive<Chain>()) {}
1423 
1428  explicit Stream(std::vector<Byte> d) : Stream(Chunk(0, std::move(d))) {}
1429 
1434  explicit Stream(const Bytes& d);
1435 
1440  explicit Stream(const char* d) : Stream(Chunk(0, d, strlen(d))) {}
1441 
1446  Stream(const char* d, const Size& n);
1451  Stream(const stream::View& d) : Stream(Chunk(0, d)) {}
1452 
1457  template<int N>
1458  Stream(std::vector<std::array<Byte, N>> d) : Stream(chunkFromArray(0, std::move(d))) {}
1459 
1464  Stream(const Stream& other) : _chain(other._chain->deepCopy()) {}
1465 
1470  Stream(Stream&& other) noexcept : _chain(std::move(other._chain)) { other._chain = make_intrusive<Chain>(); }
1471 
1476  Stream& operator=(Stream&& other) noexcept {
1477  if ( &other == this )
1478  return *this;
1479 
1480  _chain->invalidate();
1481  _chain = std::move(other._chain);
1482  other._chain = make_intrusive<Chain>();
1483  return *this;
1484  }
1485 
1490  Stream& operator=(const Stream& other) {
1491  if ( &other == this )
1492  return *this;
1493 
1494  _chain->invalidate();
1495  _chain = other._chain->deepCopy();
1496  return *this;
1497  }
1498 
1501  assert(_chain);
1502  _chain->invalidate();
1503  }
1504 
1506  Size size() const { return _chain->size(); }
1507 
1509  bool isEmpty() const { return _chain->size() == 0; }
1510 
1515  void append(const Bytes& data);
1516 
1521  void append(Bytes&& data);
1522 
1527  void append(std::unique_ptr<const Byte*> data);
1528 
1533  void append(const char* data, size_t len);
1534 
1543  void trim(const SafeConstIterator& i) { _chain->trim(i); }
1544 
1546  void freeze() { _chain->freeze(); }
1547 
1549  void unfreeze() { _chain->unfreeze(); }
1550 
1552  bool isFrozen() const { return _chain->isFrozen(); }
1553 
1555  SafeConstIterator begin() const { return _chain->begin(); }
1556 
1558  SafeConstIterator end() const { return _chain->end(); }
1559 
1561  UnsafeConstIterator unsafeBegin() const { return _chain->unsafeBegin(); }
1562 
1564  UnsafeConstIterator unsafeEnd() const { return _chain->unsafeEnd(); }
1565 
1570  SafeConstIterator at(const Offset& offset) const { return _chain->at(offset); }
1571 
1573  Offset endOffset() const { return _chain->endOffset(); }
1574 
1581  View view(bool expanding = true) const { return expanding ? View(begin()) : View(begin(), end()); }
1582 
1583  bool operator==(const Bytes& other) const { return view() == other; }
1584  bool operator==(const Stream& other) const { return view() == other.view(); }
1585  bool operator==(const stream::View& other) const { return view() == other; }
1586  bool operator!=(const Bytes& other) const { return ! (*this == other); }
1587  bool operator!=(const Stream& other) const { return ! (*this == other); }
1588  bool operator!=(const stream::View& other) const { return ! (*this == other); }
1589 
1594  int numberOfChunks() const { return _chain->numberOfChunks(); }
1595 
1599  void debugPrint(std::ostream& out) const;
1600 
1604  static void debugPrint(std::ostream& out, const stream::detail::Chain* chain);
1605 
1606 private:
1607  Stream(Chunk&& ch) : _chain(make_intrusive<Chain>(std::make_unique<Chunk>(std::move(ch)))) {}
1608 
1609  ChainPtr _chain; // always non-null
1610 };
1611 
1612 template<>
1613 inline std::string detail::to_string_for_print<stream::View>(const stream::View& x) {
1614  return escapeBytes(x.dataForPrint(), true);
1615 }
1616 
1617 template<>
1618 inline std::string detail::to_string_for_print<Stream>(const Stream& x) {
1619  return to_string_for_print(x.view());
1620 }
1621 
1622 inline std::ostream& operator<<(std::ostream& out, const Stream& x) { return out << to_string_for_print(x); }
1623 
1624 namespace detail::adl {
1625 inline std::string to_string(const stream::View& x, adl::tag /*unused*/) {
1626  return fmt("b\"%s\"", hilti::rt::to_string_for_print(x));
1627 }
1628 
1629 inline std::string to_string(const Stream& x, adl::tag /*unused*/) { return hilti::rt::to_string(x.view()); }
1630 } // namespace detail::adl
1631 
1632 } // namespace hilti::rt
View sub(const Offset &to) const
Definition: stream.h:1246
Chain(std::unique_ptr< Chunk > head)
Definition: stream.h:269
std::tuple< bool, SafeConstIterator > find(const Bytes &v, Direction d=Direction::Forward) const
Definition: stream.h:1141
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:1227
void trim(const SafeConstIterator &i)
Definition: stream.h:1543
View(SafeConstIterator begin)
Definition: stream.h:1015
bool operator>=(const UnsafeConstIterator &other) const
Definition: stream.h:809
auto operator*() const
Definition: stream.h:758
const detail::Chunk * _block
Definition: stream.h:1331
bool isUnset() const
Definition: stream.h:820
detail::UnsafeConstIterator unsafeBegin() const
Definition: stream.h:1310
SafeConstIterator end() const
Definition: stream.h:1558
Stream(const char *d)
Definition: stream.h:1440
std::tuple< bool, UnsafeConstIterator > find(const Bytes &v, UnsafeConstIterator n, Direction d=Direction::Forward) const
Definition: stream.h:1178
bool operator>(const SafeConstIterator &other) const
Definition: stream.h:513
bool operator<=(const UnsafeConstIterator &other) const
Definition: stream.h:803
Definition: intrusive-ptr.h:25
Definition: any.h:7
std::optional< Offset > endOffset() const
Definition: stream.h:1027
View limit(const Offset &incr) const
Definition: stream.h:1273
SafeConstIterator at(const Offset &offset) const
Definition: stream.h:1249
Stream & operator=(const Stream &other)
Definition: stream.h:1490
Offset offset() const
Definition: stream.h:1021
void internalError(const std::string &msg) __attribute__((noreturn))
Definition: logging.cc:16
uint64_t offset
Definition: stream.h:1328
Definition: optional.h:79
UnsafeConstIterator unsafeBegin() const
Definition: stream.h:1561
const Byte * start
Definition: stream.h:1326
Definition: stream.h:72
auto operator+(const integer::safe< uint64_t > &i) const
Definition: stream.h:761
Definition: intrusive-ptr.h:28
auto operator-(const integer::safe< uint64_t > &i) const
Definition: stream.h:768
integer::safe< int64_t > operator-(const SafeConstIterator &other) const
Definition: stream.h:475
Definition: stream.h:1325
SafeConstIterator at(const Offset &offset) const
Definition: stream.h:1570
auto operator--(int)
Definition: stream.h:745
bool operator==(const UnsafeConstIterator &other) const
Definition: stream.h:788
SafeConstIterator begin() const
Definition: stream.h:1555
Definition: bytes.h:157
bool startsWith(const std::string &s, const std::string &prefix)
Definition: util.cc:380
bool isEmpty() const
Definition: stream.h:1042
Stream & operator=(Stream &&other) noexcept
Definition: stream.h:1476
void cannot_be_reached() __attribute__((noreturn))
Definition: util.cc:42
Definition: stream.h:260
bool is_first
Definition: stream.h:1329
auto & operator+=(const integer::safe< uint64_t > &i)
Definition: stream.h:429
bool isEmpty() const
Definition: stream.h:1509
bool operator<=(const SafeConstIterator &other) const
Definition: stream.h:507
auto & operator--()
Definition: stream.h:739
bool operator<(const SafeConstIterator &other) const
Definition: stream.h:501
bool operator!=(const SafeConstIterator &other) const
Definition: stream.h:495
auto operator++(int)
Definition: stream.h:732
SafeConstIterator find(Byte b, const SafeConstIterator &n) const
Definition: stream.h:1072
Definition: stream.h:984
auto & operator--()
Definition: stream.h:435
bool isEnd() const
Definition: stream.h:840
auto operator--(int)
Definition: stream.h:441
View advance(const integer::safe< uint64_t > &i) const
Definition: stream.h:1202
detail::UnsafeConstIterator unsafeEnd() const
Definition: stream.h:1313
bool isValid() const
Definition: stream.h:837
void unfreeze()
Definition: stream.h:1549
bool isExpired() const
Definition: stream.h:826
int numberOfChunks() const
Definition: stream.h:1594
Offset offset() const
Definition: stream.h:720
View advance(SafeConstIterator i) const
Definition: stream.h:1192
Stream(const stream::View &d)
Definition: stream.h:1451
bool isFrozen() const
Definition: stream.h:723
bool isExpired() const
Definition: stream.h:539
auto & operator-=(const integer::safe< uint64_t > &i)
Definition: stream.h:448
std::tuple< bool, SafeConstIterator > find(const View &v) const
Definition: stream.h:1096
Offset endOffset() const
Definition: stream.h:1573
bool isValid() const
Definition: stream.h:550
bool operator!=(const UnsafeConstIterator &other) const
Definition: stream.h:797
View sub(const Offset &from, const Offset &to) const
Definition: stream.h:1238
bool isUnset() const
Definition: stream.h:533
View sub(SafeConstIterator from, SafeConstIterator to) const
Definition: stream.h:1215
Stream(const Stream &other)
Definition: stream.h:1464
Stream(std::vector< std::array< Byte, N >> d)
Definition: stream.h:1458
Stream(std::vector< Byte > d)
Definition: stream.h:1428
bool is_last
Definition: stream.h:1330
Definition: stream.h:1408
auto operator-(const integer::safe< uint64_t > &i) const
Definition: stream.h:464
Definition: intrusive-ptr.h:69
Stream()
Definition: stream.h:1422
Stream(Stream &&other) noexcept
Definition: stream.h:1470
auto operator++(int)
Definition: stream.h:422
auto & operator-=(const integer::safe< uint64_t > &i)
Definition: stream.h:752
void debugPrint(std::ostream &out) const
Definition: stream.cc:592
Size size() const
Definition: stream.h:1506
bool isOpenEnded() const
Definition: stream.h:1052
bool isFrozen() const
Definition: stream.h:1552
bool isFrozen() const
Definition: stream.h:1045
bool operator==(const SafeConstIterator &other) const
Definition: stream.h:485
View extract(Byte *dst, uint64_t n) const
Definition: stream.h:1282
std::tuple< bool, SafeConstIterator > find(const View &v, const SafeConstIterator &n) const
Definition: stream.h:1112
auto operator*() const
Definition: stream.h:454
bool operator>=(const SafeConstIterator &other) const
Definition: stream.h:519
bool isEnd() const
Definition: stream.h:557
~Stream()
Definition: stream.h:1500
View(SafeConstIterator begin, SafeConstIterator end)
Definition: stream.h:1001
UnsafeConstIterator unsafeEnd() const
Definition: stream.h:1564
SafeConstIterator end() const
Definition: stream.h:1319
std::string_view trim(std::string_view s, const std::string &chars) noexcept
Definition: util.h:143
const SafeConstIterator & begin() const
Definition: stream.h:1316
auto operator+(const integer::safe< uint64_t > &i) const
Definition: stream.h:457
Definition: stream.h:88
bool isFrozen() const
Definition: stream.h:413
SafeConstIterator find(Byte b) const
Definition: stream.h:1060
bool operator>(const UnsafeConstIterator &other) const
Definition: stream.h:806
Definition: stream.h:393
void freeze()
Definition: stream.h:1546
bool operator<(const UnsafeConstIterator &other) const
Definition: stream.h:800
auto & operator++()
Definition: stream.h:726
View trim(const SafeConstIterator &nbegin) const
Definition: stream.h:1256
integer::safe< int64_t > operator-(const UnsafeConstIterator &other) const
Definition: stream.h:779
auto & operator++()
Definition: stream.h:416
std::string fmt(const char *fmt, const Args &... args)
Definition: fmt.h:13
std::tuple< bool, SafeConstIterator > find(const Bytes &v, const SafeConstIterator &n, Direction d=Direction::Forward) const
Definition: stream.h:1159
Offset offset() const
Definition: stream.h:410
View view(bool expanding=true) const
Definition: stream.h:1581
uint64_t size
Definition: stream.h:1327