iOS/Pods/Realm/include/core/realm/sync/changeset.hpp

   1 /*************************************************************************
   2  *
   3  * REALM CONFIDENTIAL
   4  * __________________
   5  *
   6  *  [2011] - [2017] Realm Inc
   7  *  All Rights Reserved.
   8  *
   9  * NOTICE:  All information contained herein is, and remains
  10  * the property of Realm Incorporated and its suppliers,
  11  * if any.  The intellectual and technical concepts contained
  12  * herein are proprietary to Realm Incorporated
  13  * and its suppliers and may be covered by U.S. and Foreign Patents,
  14  * patents in process, and are protected by trade secret or copyright law.
  15  * Dissemination of this information or reproduction of this material
  16  * is strictly forbidden unless prior written permission is obtained
  17  * from Realm Incorporated.
  18  *
  19  **************************************************************************/
  20
  21 #ifndef REALM_SYNC_CHANGESET_HPP
  22 #define REALM_SYNC_CHANGESET_HPP
  23
  24 #include <realm/sync/instructions.hpp>
  25 #include <realm/util/optional.hpp>
  26
  27 #include <type_traits>
  28
  29 namespace realm {
  30 namespace sync {
  31
  32 using InternStrings = std::unordered_map<uint32_t, StringBufferRange>;
  33
  34 struct BadChangesetError : std::exception {
  35     const char* message;
  36     BadChangesetError() : BadChangesetError("Bad bad changeset") {}
  37     BadChangesetError(const char* msg) : message(msg) {}
  38     const char* what() const noexcept override
  39     {
  40         return message;
  41     }
  42 };
  43
  44 struct Changeset {
  45     struct Range;
  46     using timestamp_type = uint_fast64_t;
  47     using file_ident_type = uint_fast64_t;
  48     using version_type = uint_fast64_t; // FIXME: Get from `History`.
  49
  50     Changeset();
  51     struct share_buffers_tag {};
  52     Changeset(const Changeset&, share_buffers_tag);
  53     Changeset(Changeset&&) = default;
  54     Changeset& operator=(Changeset&&) = default;
  55     Changeset(const Changeset&) = delete;
  56     Changeset& operator=(const Changeset&) = delete;
  57
  58     InternString intern_string(StringData); // Slow!
  59     StringData string_data() const noexcept;
  60
  61     util::StringBuffer& string_buffer() noexcept;
  62     const util::StringBuffer& string_buffer() const noexcept;
  63     const InternStrings& interned_strings() const noexcept;
  64     InternStrings& interned_strings() noexcept;
  65
  66     StringBufferRange get_intern_string(InternString) const noexcept;
  67     util::Optional<StringBufferRange> try_get_intern_string(InternString) const noexcept;
  68     util::Optional<StringData> try_get_string(StringBufferRange) const noexcept;
  69     StringData get_string(StringBufferRange) const noexcept;
  70     StringData get_string(InternString) const noexcept;
  71     StringBufferRange append_string(StringData);
  72
  73     // Interface to imitate std::vector:
  74     template <bool is_const> struct IteratorImpl;
  75     using iterator = IteratorImpl<false>;
  76     using const_iterator = IteratorImpl<true>;
  77     using value_type = Instruction;
  78     iterator begin() noexcept;
  79     iterator end() noexcept;
  80     const_iterator begin() const noexcept;
  81     const_iterator end() const noexcept;
  82     const_iterator cbegin() const noexcept;
  83     const_iterator cend() const noexcept;
  84     bool empty() const noexcept;
  85
  86     /// Size of the Changeset, not counting tombstones.
  87     ///
  88     /// FIXME: This is an O(n) operation.
  89     size_t size() const noexcept;
  90
  91     void clear() noexcept;
  92
  93     //@{
  94     /// Insert instructions, invalidating all iterators.
  95     iterator insert(iterator pos, Instruction);
  96     template <class InputIt>
  97     iterator insert(iterator pos, InputIt begin, InputIt end);
  98     //@}
  99
 100     /// Erase an instruction, invalidating all iterators.
 101     iterator erase(iterator);
 102
 103     /// Insert an instruction at the end, invalidating all iterators.
 104     void push_back(Instruction);
 105
 106     //@{
 107     /// Insert instructions at \a position without invalidating other
 108     /// iterators.
 109     ///
 110     /// Only iterators created before any call to `insert_stable()` may be
 111     /// considered stable across calls to `insert_stable()`. In addition,
 112     /// "iterator stability" has a very specific meaning here: Other copies of
 113     /// \a position in the program will point to the newly inserted elements
 114     /// after calling `insert_stable()`, rather than point to the value at the
 115     /// position prior to insertion. This is different from, say, a tree
 116     /// structure, where iterator stability signifies the property that
 117     /// iterators keep pointing to the same element after insertion before or
 118     /// after that position.
 119     ///
 120     /// For the purpose of supporting `ChangesetIndex`, and the OT merge
 121     /// algorithm, these semantics are acceptable, since prepended instructions
 122     /// can never create new object or table references.
 123     iterator insert_stable(iterator position, Instruction);
 124     template <class InputIt>
 125     iterator insert_stable(iterator position, InputIt begin, InputIt end);
 126     //@}
 127
 128     /// Erase instruction at \a position without invalidating other iterators.
 129     /// If erasing the object would invalidate other iterators, it is turned
 130     /// into a tombstone instead, and subsequent derefencing of the iterator
 131     /// will return `nullptr`. An iterator pointing to a tombstone remains valid
 132     /// and can be incremented.
 133     ///
 134     /// Only iterators created before any call to `insert_stable()` may be
 135     /// considered stable across calls to `erase_stable()`. If other copies of
 136     /// \a position exist in the program, they will either point to the
 137     /// subsequent element if that element was previously inserted with
 138     /// `insert_stable()`, or otherwise it will be turned into a tombstone.
 139     iterator erase_stable(iterator position);
 140
 141 #if REALM_DEBUG
 142     struct Reflector;
 143     struct Printer;
 144     void verify() const;
 145     void print(std::ostream&) const;
 146     void print() const; // prints to std::err
 147 #endif
 148
 149     /// The version that this changeset produced. Note: This may not be the
 150     /// version produced by this changeset on the client on which this changeset
 151     /// originated, but may for instance be the version produced on the server
 152     /// after receiving and re-sending this changeset to another client.
 153     version_type version = 0;
 154
 155     /// On clients, the last integrated server version. On the server, this is
 156     /// the last integrated client version.
 157     version_type last_integrated_remote_version = 0;
 158
 159     /// Timestamp at origin when producting this changeset.
 160     timestamp_type origin_timestamp = 0;
 161
 162     /// Client file identifier that produced this changeset.
 163     file_ident_type origin_client_file_ident = 0;
 164
 165 private:
 166     struct MultiInstruction {
 167         std::vector<Instruction> instructions;
 168     };
 169
 170     // In order to achieve iterator semi-stability (just enough to be able to
 171     // run the merge algorithm while maintaining a ChangesetIndex), a Changeset
 172     // is really a list of lists. A Changeset is a vector of
 173     // `InstructionContainer`s, and each `InstructionContainer` represents 0-N
 174     // "real" instructions.
 175     //
 176     // As an optimization, there is a special case for when the
 177     // `InstructionContainer` represents exactly 1 instruction, in which case it
 178     // is represented inside the `InstructionContainer` without any additional
 179     // allocations or indirections. The `InstructionContainer` derived from
 180     // the `Instruction` struct, and co-opts the `type` field such that if the
 181     // (invalid) value of `type` is 0xff, the contents of the `Instruction` are
 182     // instead interpreted as an instance of `MultiInstruction`, which holds
 183     // a vector of `Instruction`s.
 184     //
 185     // The size of the `MultiInstruction` may also be zero, in which case it is
 186     // considered a "tombstone" - always as a result of a call to
 187     // `Changeset::erase_stable()`. The potential existence of these tombstones
 188     // is the reason that the value type of `Changeset::iterator` is
 189     // `Instruction*`, rather than `Instruction&`.
 190     //
 191     // FIXME: It would be better if `Changeset::iterator::value_type` could be
 192     // `util::Optional<Instruction&>`, but this is prevented by a bug in
 193     // `util::Optional`.
 194     struct InstructionContainer : Instruction {
 195         InstructionContainer();
 196         InstructionContainer(Instruction instr);
 197         InstructionContainer(InstructionContainer&&);
 198         InstructionContainer(const InstructionContainer&);
 199         ~InstructionContainer();
 200         InstructionContainer& operator=(InstructionContainer&&);
 201         InstructionContainer& operator=(const InstructionContainer&);
 202
 203         bool is_multi() const noexcept;
 204         void convert_to_multi();
 205         void insert(size_t position, Instruction instr);
 206         void erase(size_t position);
 207         size_t size() const noexcept;
 208
 209         Instruction& at(size_t pos) noexcept;
 210         const Instruction& at(size_t pos) const noexcept;
 211
 212         MultiInstruction& get_multi() noexcept;
 213         const MultiInstruction& get_multi() const noexcept;
 214     };
 215
 216     std::vector<InstructionContainer> m_instructions;
 217     std::shared_ptr<util::StringBuffer> m_string_buffer;
 218     std::shared_ptr<InternStrings> m_strings;
 219 };
 220
 221 /// An iterator type that hides the implementation details of the support for
 222 /// iterator stability.
 223 ///
 224 /// A `Changeset::iterator` is composed of an
 225 /// `std::vector<InstructionContainer>::iterator` and a `size_t` representing
 226 /// the index into the current `InstructionContainer`. If that container is
 227 /// empty, and the position is zero, the iterator is pointing to a tombstone.
 228 template <bool is_const>
 229 struct Changeset::IteratorImpl {
 230     using list_type = std::vector<InstructionContainer>;
 231     using inner_iterator_type = std::conditional_t<is_const, list_type::const_iterator, list_type::iterator>;
 232
 233     // reference_type is a pointer because we have no way to create a reference
 234     // to a tombstone instruction. Alternatively, it could have been
 235     // `util::Optional<Instruction&>`, but that runs into other issues.
 236     using reference_type = std::conditional_t<is_const, const Instruction*, Instruction*>;
 237
 238     using pointer_type   = std::conditional_t<is_const, const Instruction*, Instruction*>;
 239     using difference_type = std::ptrdiff_t;
 240
 241     IteratorImpl() : m_pos(0) {}
 242     IteratorImpl(const IteratorImpl& other) : m_inner(other.m_inner), m_pos(other.m_pos) {}
 243     template <bool is_const_ = is_const>
 244     IteratorImpl(const IteratorImpl<false>& other, std::enable_if_t<is_const_>* = nullptr)
 245         : m_inner(other.m_inner), m_pos(other.m_pos) {}
 246     IteratorImpl(inner_iterator_type inner) : m_inner(inner), m_pos(0) {}
 247
 248     IteratorImpl& operator++()
 249     {
 250         ++m_pos;
 251         if (m_pos >= m_inner->size()) {
 252             ++m_inner;
 253             m_pos = 0;
 254         }
 255         return *this;
 256     }
 257
 258     IteratorImpl operator++(int)
 259     {
 260         auto copy = *this;
 261         ++(*this);
 262         return copy;
 263     }
 264
 265     IteratorImpl& operator--()
 266     {
 267         if (m_pos == 0) {
 268             --m_inner;
 269             m_pos = m_inner->size();
 270             if (m_pos != 0)
 271                 --m_pos;
 272         }
 273         else {
 274             --m_pos;
 275         }
 276         return *this;
 277     }
 278
 279     IteratorImpl operator--(int)
 280     {
 281         auto copy = *this;
 282         --(*this);
 283         return copy;
 284     }
 285
 286     reference_type operator*() const
 287     {
 288         if (m_inner->size()) {
 289             return &m_inner->at(m_pos);
 290         }
 291         // It was a tombstone.
 292         return nullptr;
 293     }
 294
 295     pointer_type operator->() const
 296     {
 297         if (m_inner->size()) {
 298             return &m_inner->at(m_pos);
 299         }
 300         // It was a tombstone.
 301         return nullptr;
 302     }
 303
 304     bool operator==(const IteratorImpl& other) const
 305     {
 306         return m_inner == other.m_inner && m_pos == other.m_pos;
 307     }
 308
 309     bool operator!=(const IteratorImpl& other) const
 310     {
 311         return !(*this == other);
 312     }
 313
 314     bool operator<(const IteratorImpl& other) const
 315     {
 316         if (m_inner == other.m_inner)
 317             return m_pos < other.m_pos;
 318         return m_inner < other.m_inner;
 319     }
 320
 321     bool operator<=(const IteratorImpl& other) const
 322     {
 323         if (m_inner == other.m_inner)
 324             return m_pos <= other.m_pos;
 325         return m_inner < other.m_inner;
 326     }
 327
 328     bool operator>(const IteratorImpl& other) const
 329     {
 330         if (m_inner == other.m_inner)
 331             return m_pos > other.m_pos;
 332         return m_inner > other.m_inner;
 333     }
 334
 335     bool operator>=(const IteratorImpl& other) const
 336     {
 337         if (m_inner == other.m_inner)
 338             return m_pos >= other.m_pos;
 339         return m_inner > other.m_inner;
 340     }
 341
 342     inner_iterator_type m_inner;
 343     size_t m_pos;
 344 };
 345
 346 struct Changeset::Range {
 347     iterator begin;
 348     iterator end;
 349 };
 350
 351 #if REALM_DEBUG
 352 struct Changeset::Reflector {
 353     struct Tracer {
 354         virtual void name(StringData) = 0;
 355         virtual void field(StringData, StringData) = 0;
 356         virtual void field(StringData, ObjectID) = 0;
 357         virtual void field(StringData, int64_t) = 0;
 358         virtual void field(StringData, double) = 0;
 359         virtual void after_each() {}
 360         virtual void before_each() {}
 361     };
 362
 363     Reflector(Tracer& tracer, const Changeset& log) :
 364         m_tracer(tracer), m_log(log)
 365     {}
 366
 367     void visit_all() const;
 368 private:
 369     Tracer& m_tracer;
 370     const Changeset& m_log;
 371
 372     friend struct Instruction; // permit access for visit()
 373 #define REALM_DEFINE_REFLECTOR_VISITOR(X) void operator()(const Instruction::X&) const;
 374     REALM_FOR_EACH_INSTRUCTION_TYPE(REALM_DEFINE_REFLECTOR_VISITOR)
 375 #undef REALM_DEFINE_REFLECTOR_VISITOR
 376 };
 377
 378 struct Changeset::Printer : Changeset::Reflector::Tracer {
 379     explicit Printer(std::ostream& os) : m_out(os)
 380     {}
 381
 382     // ChangesetReflector::Tracer interface:
 383     void name(StringData) final;
 384     void field(StringData, StringData) final;
 385     void field(StringData, ObjectID) final;
 386     void field(StringData, int64_t) final;
 387     void field(StringData, double) final;
 388     void after_each() final;
 389
 390 private:
 391     std::ostream& m_out;
 392     void pad_or_ellipsis(StringData, int width) const;
 393 };
 394 #endif // REALM_DEBUG
 395
 396
 397
 398 /// Implementation:
 399
 400 inline Changeset::iterator Changeset::begin() noexcept
 401 {
 402     return m_instructions.begin();
 403 }
 404
 405 inline Changeset::iterator Changeset::end() noexcept
 406 {
 407     return m_instructions.end();
 408 }
 409
 410 inline Changeset::const_iterator Changeset::begin() const noexcept
 411 {
 412     return m_instructions.begin();
 413 }
 414
 415 inline Changeset::const_iterator Changeset::end() const noexcept
 416 {
 417     return m_instructions.end();
 418 }
 419
 420 inline Changeset::const_iterator Changeset::cbegin() const noexcept
 421 {
 422     return m_instructions.cbegin();
 423 }
 424
 425 inline Changeset::const_iterator Changeset::cend() const noexcept
 426 {
 427     return m_instructions.end();
 428 }
 429
 430 inline bool Changeset::empty() const noexcept
 431 {
 432     return size() == 0;
 433 }
 434
 435 inline size_t Changeset::size() const noexcept
 436 {
 437     size_t sum = 0;
 438     for (auto& x: m_instructions)
 439         sum += x.size();
 440     return sum;
 441 }
 442
 443 inline void Changeset::clear() noexcept
 444 {
 445     m_instructions.clear();
 446 }
 447
 448 inline util::Optional<StringBufferRange> Changeset::try_get_intern_string(InternString string) const noexcept
 449 {
 450     auto it = m_strings->find(string.value);
 451     if (it == m_strings->end())
 452         return util::none;
 453     return it->second;
 454 }
 455
 456 inline StringBufferRange Changeset::get_intern_string(InternString string) const noexcept
 457 {
 458     auto str = try_get_intern_string(string);
 459     REALM_ASSERT(str);
 460     return *str;
 461 }
 462
 463 inline InternStrings& Changeset::interned_strings() noexcept
 464 {
 465     return *m_strings;
 466 }
 467
 468 inline const InternStrings& Changeset::interned_strings() const noexcept
 469 {
 470     return *m_strings;
 471 }
 472
 473 inline util::StringBuffer& Changeset::string_buffer() noexcept
 474 {
 475     return *m_string_buffer;
 476 }
 477
 478 inline const util::StringBuffer& Changeset::string_buffer() const noexcept
 479 {
 480     return *m_string_buffer;
 481 }
 482
 483 inline util::Optional<StringData> Changeset::try_get_string(StringBufferRange range) const noexcept
 484 {
 485     if (range.offset > m_string_buffer->size())
 486         return util::none;
 487     if (range.offset + range.size > m_string_buffer->size())
 488         return util::none;
 489     return StringData{m_string_buffer->data() + range.offset, range.size};
 490 }
 491
 492 inline StringData Changeset::get_string(StringBufferRange range) const noexcept
 493 {
 494     auto string = try_get_string(range);
 495     REALM_ASSERT(string);
 496     return *string;
 497 }
 498
 499 inline StringData Changeset::get_string(InternString string) const noexcept
 500 {
 501     return get_string(get_intern_string(string));
 502 }
 503
 504 inline StringData Changeset::string_data() const noexcept
 505 {
 506     return StringData{m_string_buffer->data(), m_string_buffer->size()};
 507 }
 508
 509 inline StringBufferRange Changeset::append_string(StringData string)
 510 {
 511     m_string_buffer->reserve(1024); // we expect more strings
 512     size_t offset = m_string_buffer->size();
 513     m_string_buffer->append(string.data(), string.size());
 514     return StringBufferRange{uint32_t(offset), uint32_t(string.size())};
 515 }
 516
 517 inline Changeset::iterator Changeset::insert(iterator pos, Instruction instr)
 518 {
 519     Instruction* p = &instr;
 520     return insert(pos, p, p + 1);
 521 }
 522
 523 template <class InputIt>
 524 inline Changeset::iterator Changeset::insert(iterator pos, InputIt begin, InputIt end)
 525 {
 526     if (pos.m_pos == 0)
 527         return m_instructions.insert(pos.m_inner, begin, end);
 528     return insert_stable(pos, begin, end);
 529 }
 530
 531 inline Changeset::iterator Changeset::erase(iterator pos)
 532 {
 533     if (pos.m_inner->size() <= 1)
 534         return m_instructions.erase(pos.m_inner);
 535     return erase_stable(pos);
 536 }
 537
 538 inline Changeset::iterator Changeset::insert_stable(iterator pos, Instruction instr)
 539 {
 540     Instruction* p = &instr;
 541     return insert_stable(pos, p, p + 1);
 542 }
 543
 544 template <class InputIt>
 545 inline Changeset::iterator Changeset::insert_stable(iterator pos, InputIt begin, InputIt end)
 546 {
 547     size_t i = 0;
 548     for (auto it = begin; it != end; ++it, ++i) {
 549         pos.m_inner->insert(pos.m_pos + i, *it);
 550     }
 551     return pos;
 552 }
 553
 554 inline Changeset::iterator Changeset::erase_stable(iterator pos)
 555 {
 556     pos.m_inner->erase(pos.m_pos);
 557     ++pos;
 558     return pos;
 559 }
 560
 561 inline void Changeset::push_back(Instruction instr)
 562 {
 563     m_instructions.push_back(std::move(instr));
 564 }
 565
 566 inline Changeset::InstructionContainer::~InstructionContainer()
 567 {
 568     if (is_multi()) {
 569         get_multi().~MultiInstruction();
 570     }
 571     // Instruction subtypes are required to be POD-types (trivially
 572     // destructible), and this is checked by a static_assert in
 573     // instructions.hpp. Therefore, it is safe to do nothing if this is not a
 574     // multi-instruction.
 575 }
 576
 577 inline bool Changeset::InstructionContainer::is_multi() const noexcept
 578 {
 579     return type == Type(InstrTypeMultiInstruction);
 580 }
 581
 582 inline size_t Changeset::InstructionContainer::size() const noexcept
 583 {
 584     if (is_multi())
 585         return get_multi().instructions.size();
 586     return 1;
 587 }
 588
 589 inline Instruction& Changeset::InstructionContainer::at(size_t pos) noexcept
 590 {
 591     REALM_ASSERT(pos < size());
 592     if (is_multi())
 593         return get_multi().instructions[pos];
 594     return *this;
 595 }
 596
 597 inline const Instruction& Changeset::InstructionContainer::at(size_t pos) const noexcept
 598 {
 599     REALM_ASSERT(pos < size());
 600     if (is_multi())
 601         return get_multi().instructions[pos];
 602     return *this;
 603 }
 604
 605 inline Changeset::MultiInstruction& Changeset::InstructionContainer::get_multi() noexcept
 606 {
 607     REALM_ASSERT(is_multi());
 608     return *reinterpret_cast<MultiInstruction*>(&m_storage);
 609 }
 610
 611 inline const Changeset::MultiInstruction& Changeset::InstructionContainer::get_multi() const noexcept
 612 {
 613     REALM_ASSERT(is_multi());
 614     return *reinterpret_cast<const MultiInstruction*>(&m_storage);
 615 }
 616
 617 } // namespace sync
 618 } // namespace realm
 619
 620 namespace std {
 621
 622 template <bool is_const>
 623 struct iterator_traits<realm::sync::Changeset::IteratorImpl<is_const>> {
 624     using difference_type = std::ptrdiff_t;
 625     using iterator_category = std::bidirectional_iterator_tag;
 626 };
 627
 628 } // namespace std
 629
 630 #endif // REALM_SYNC_CHANGESET_HPP