/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this file,
 * You can obtain one at http://mozilla.org/MPL/2.0/. */

// This is included first to ensure it doesn't implicitly depend on anything
// else.
#include "mozilla/BufferList.h"
#include "mozilla/CheckedArithmetic.h"

// It would be nice if we could use the InfallibleAllocPolicy from mozalloc,
// but MFBT cannot use mozalloc.
class InfallibleAllocPolicy {
 public:
  template <typename T>
  T* pod_malloc(size_t aNumElems) {
    size_t size;
    if (!mozilla::SafeMul(aNumElems, sizeof(T), &size)) {
      MOZ_CRASH("TestBufferList.cpp: overflow");
    }
    T* rv = static_cast<T*>(malloc(size));
    if (!rv) {
      MOZ_CRASH("TestBufferList.cpp: out of memory");
    }
    return rv;
  }

  template <typename T>
  void free_(T* aPtr, size_t aNumElems = 0) {
    free(aPtr);
  }

  void reportAllocOverflow() const {}

  bool checkSimulatedOOM() const { return true; }
};

typedef mozilla::BufferList<InfallibleAllocPolicy> BufferList;

int main(void) {
  const size_t kInitialSize = 16;
  const size_t kInitialCapacity = 24;
  const size_t kStandardCapacity = 32;

  BufferList bl(kInitialSize, kInitialCapacity, kStandardCapacity);

  memset(bl.Start(), 0x0c, kInitialSize);
  MOZ_RELEASE_ASSERT(bl.Size() == kInitialSize);

  // Simple iteration and access.

  BufferList::IterImpl iter(bl.Iter());
  MOZ_RELEASE_ASSERT(iter.RemainingInSegment() == kInitialSize);
  MOZ_RELEASE_ASSERT(iter.HasRoomFor(kInitialSize));
  MOZ_RELEASE_ASSERT(!iter.HasRoomFor(kInitialSize + 1));
  MOZ_RELEASE_ASSERT(!iter.HasRoomFor(size_t(-1)));
  MOZ_RELEASE_ASSERT(*iter.Data() == 0x0c);
  MOZ_RELEASE_ASSERT(!iter.Done());

  iter.Advance(bl, 4);
  MOZ_RELEASE_ASSERT(iter.RemainingInSegment() == kInitialSize - 4);
  MOZ_RELEASE_ASSERT(iter.HasRoomFor(kInitialSize - 4));
  MOZ_RELEASE_ASSERT(*iter.Data() == 0x0c);
  MOZ_RELEASE_ASSERT(!iter.Done());

  iter.Advance(bl, 11);
  MOZ_RELEASE_ASSERT(iter.RemainingInSegment() == kInitialSize - 4 - 11);
  MOZ_RELEASE_ASSERT(iter.HasRoomFor(kInitialSize - 4 - 11));
  MOZ_RELEASE_ASSERT(!iter.HasRoomFor(kInitialSize - 4 - 11 + 1));
  MOZ_RELEASE_ASSERT(*iter.Data() == 0x0c);
  MOZ_RELEASE_ASSERT(!iter.Done());

  iter.Advance(bl, kInitialSize - 4 - 11);
  MOZ_RELEASE_ASSERT(iter.RemainingInSegment() == 0);
  MOZ_RELEASE_ASSERT(!iter.HasRoomFor(1));
  MOZ_RELEASE_ASSERT(iter.Done());

  // Writing to the buffer.

  const size_t kSmallWrite = 16;

  char toWrite[kSmallWrite];
  memset(toWrite, 0x0a, kSmallWrite);
  MOZ_ALWAYS_TRUE(bl.WriteBytes(toWrite, kSmallWrite));

  MOZ_RELEASE_ASSERT(bl.Size() == kInitialSize + kSmallWrite);

  iter = bl.Iter();
  iter.Advance(bl, kInitialSize);
  MOZ_RELEASE_ASSERT(!iter.Done());
  MOZ_RELEASE_ASSERT(iter.RemainingInSegment() ==
                     kInitialCapacity - kInitialSize);
  MOZ_RELEASE_ASSERT(iter.HasRoomFor(kInitialCapacity - kInitialSize));
  MOZ_RELEASE_ASSERT(*iter.Data() == 0x0a);

  // AdvanceAcrossSegments.

  iter = bl.Iter();
  MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl, kInitialCapacity - 4));
  MOZ_RELEASE_ASSERT(!iter.Done());
  MOZ_RELEASE_ASSERT(iter.RemainingInSegment() == 4);
  MOZ_RELEASE_ASSERT(iter.HasRoomFor(4));
  MOZ_RELEASE_ASSERT(*iter.Data() == 0x0a);

  iter = bl.Iter();
  MOZ_RELEASE_ASSERT(
      iter.AdvanceAcrossSegments(bl, kInitialSize + kSmallWrite - 4));
  MOZ_RELEASE_ASSERT(!iter.Done());
  MOZ_RELEASE_ASSERT(iter.RemainingInSegment() == 4);
  MOZ_RELEASE_ASSERT(iter.HasRoomFor(4));
  MOZ_RELEASE_ASSERT(*iter.Data() == 0x0a);

  MOZ_RELEASE_ASSERT(
      bl.Iter().AdvanceAcrossSegments(bl, kInitialSize + kSmallWrite - 1));
  MOZ_RELEASE_ASSERT(
      bl.Iter().AdvanceAcrossSegments(bl, kInitialSize + kSmallWrite));
  MOZ_RELEASE_ASSERT(
      !bl.Iter().AdvanceAcrossSegments(bl, kInitialSize + kSmallWrite + 1));
  MOZ_RELEASE_ASSERT(!bl.Iter().AdvanceAcrossSegments(bl, size_t(-1)));

  // Reading non-contiguous bytes.

  char toRead[kSmallWrite];
  iter = bl.Iter();
  iter.Advance(bl, kInitialSize);
  bl.ReadBytes(iter, toRead, kSmallWrite);
  MOZ_RELEASE_ASSERT(memcmp(toRead, toWrite, kSmallWrite) == 0);
  MOZ_RELEASE_ASSERT(iter.Done());

  // Make sure reading up to the end of a segment advances the iter to the next
  // segment.
  iter = bl.Iter();
  bl.ReadBytes(iter, toRead, kInitialSize);
  MOZ_RELEASE_ASSERT(!iter.Done());
  MOZ_RELEASE_ASSERT(iter.RemainingInSegment() ==
                     kInitialCapacity - kInitialSize);

  const size_t kBigWrite = 1024;

  char* toWriteBig = static_cast<char*>(malloc(kBigWrite));
  for (unsigned i = 0; i < kBigWrite; i++) {
    toWriteBig[i] = i % 37;
  }
  MOZ_ALWAYS_TRUE(bl.WriteBytes(toWriteBig, kBigWrite));

  char* toReadBig = static_cast<char*>(malloc(kBigWrite));
  iter = bl.Iter();
  MOZ_RELEASE_ASSERT(
      iter.AdvanceAcrossSegments(bl, kInitialSize + kSmallWrite));
  bl.ReadBytes(iter, toReadBig, kBigWrite);
  MOZ_RELEASE_ASSERT(memcmp(toReadBig, toWriteBig, kBigWrite) == 0);
  MOZ_RELEASE_ASSERT(iter.Done());

  free(toReadBig);
  free(toWriteBig);

  // Currently bl contains these segments:
  // #0: offset 0, [0x0c]*16 + [0x0a]*8, size 24
  // #1: offset 24, [0x0a]*8 + [i%37 for i in 0..24], size 32
  // #2: offset 56, [i%37 for i in 24..56, size 32
  // ...
  // #32: offset 1016, [i%37 for i in 984..1016], size 32
  // #33: offset 1048, [i%37 for i in 1016..1024], size 8

  static size_t kTotalSize = kInitialSize + kSmallWrite + kBigWrite;

  MOZ_RELEASE_ASSERT(bl.Size() == kTotalSize);

  static size_t kLastSegmentSize =
      (kTotalSize - kInitialCapacity) % kStandardCapacity;

  iter = bl.Iter();
  MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(
      bl, kTotalSize - kLastSegmentSize - kStandardCapacity));
  MOZ_RELEASE_ASSERT(iter.RemainingInSegment() == kStandardCapacity);
  iter.Advance(bl, kStandardCapacity);
  MOZ_RELEASE_ASSERT(iter.RemainingInSegment() == kLastSegmentSize);
  MOZ_RELEASE_ASSERT(
      unsigned(*iter.Data()) ==
      (kTotalSize - kLastSegmentSize - kInitialSize - kSmallWrite) % 37);

  // Clear.

  bl.Clear();
  MOZ_RELEASE_ASSERT(bl.Size() == 0);
  MOZ_RELEASE_ASSERT(bl.Iter().Done());

  // Move assignment.

  const size_t kSmallCapacity = 8;

  BufferList bl2(0, kSmallCapacity, kSmallCapacity);
  MOZ_ALWAYS_TRUE(bl2.WriteBytes(toWrite, kSmallWrite));
  MOZ_ALWAYS_TRUE(bl2.WriteBytes(toWrite, kSmallWrite));
  MOZ_ALWAYS_TRUE(bl2.WriteBytes(toWrite, kSmallWrite));

  bl = std::move(bl2);
  MOZ_RELEASE_ASSERT(bl2.Size() == 0);
  MOZ_RELEASE_ASSERT(bl2.Iter().Done());

  iter = bl.Iter();
  MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl, kSmallWrite * 3));
  MOZ_RELEASE_ASSERT(iter.Done());

  // MoveFallible

  bool success;
  bl2 = bl.MoveFallible<InfallibleAllocPolicy>(&success);
  MOZ_RELEASE_ASSERT(success);
  MOZ_RELEASE_ASSERT(bl.Size() == 0);
  MOZ_RELEASE_ASSERT(bl.Iter().Done());
  MOZ_RELEASE_ASSERT(bl2.Size() == kSmallWrite * 3);

  iter = bl2.Iter();
  MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl2, kSmallWrite * 3));
  MOZ_RELEASE_ASSERT(iter.Done());

  bl = bl2.MoveFallible<InfallibleAllocPolicy>(&success);

  // Borrowing.

  const size_t kBorrowStart = 4;
  const size_t kBorrowSize = 24;

  iter = bl.Iter();
  iter.Advance(bl, kBorrowStart);
  bl2 = bl.Borrow<InfallibleAllocPolicy>(iter, kBorrowSize, &success);
  MOZ_RELEASE_ASSERT(success);
  MOZ_RELEASE_ASSERT(bl2.Size() == kBorrowSize);

  MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(
      bl, kSmallWrite * 3 - kBorrowSize - kBorrowStart));
  MOZ_RELEASE_ASSERT(iter.Done());

  iter = bl2.Iter();
  MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl2, kBorrowSize));
  MOZ_RELEASE_ASSERT(iter.Done());

  BufferList::IterImpl iter1(bl.Iter()), iter2(bl2.Iter());
  iter1.Advance(bl, kBorrowStart);
  MOZ_RELEASE_ASSERT(iter1.Data() == iter2.Data());
  MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl, kBorrowSize - 5));
  MOZ_RELEASE_ASSERT(iter2.AdvanceAcrossSegments(bl2, kBorrowSize - 5));
  MOZ_RELEASE_ASSERT(iter1.Data() == iter2.Data());

  // RangeLength.

  BufferList bl12(0, 0, 8);
  MOZ_ALWAYS_TRUE(bl12.WriteBytes("abcdefgh", 8));
  MOZ_ALWAYS_TRUE(bl12.WriteBytes("12345678", 8));

  // |iter| is at position 0 (1st segment).
  iter = bl12.Iter();
  iter1 = bl12.Iter();
  MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 0);
  MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 4));
  MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 4);
  MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 4));
  MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 8);
  MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 4));
  MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 12);
  MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 3));
  MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 15);
  MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 1));
  MOZ_RELEASE_ASSERT(iter1.Done());

  // |iter| is at position 1 (1st segment).
  iter = bl12.Iter();
  iter1 = bl12.Iter();
  MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl12, 1));
  MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 1));
  MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 0);
  MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 4));
  MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 4);
  MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 4));
  MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 8);
  MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 4));
  MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 12);
  MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 2));
  MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 14);
  MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 1));
  MOZ_RELEASE_ASSERT(iter1.Done());

  // |iter| is at position 8 (2nd segment).
  iter = bl12.Iter();
  iter1 = bl12.Iter();
  MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl12, 8));
  MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 8));
  MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 0);
  MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 4));
  MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 4);
  MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 3));
  MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 7);
  MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 1));
  MOZ_RELEASE_ASSERT(iter1.Done());

  // |iter| is at position 9 (2nd segment).
  iter = bl12.Iter();
  iter1 = bl12.Iter();
  MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl12, 9));
  MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 9));
  MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 0);
  MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 4));
  MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 4);
  MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 2));
  MOZ_RELEASE_ASSERT(bl12.RangeLength(iter, iter1) == 6);
  MOZ_RELEASE_ASSERT(iter1.AdvanceAcrossSegments(bl12, 1));
  MOZ_RELEASE_ASSERT(iter1.Done());

  BufferList bl13(0, 0, 8);
  MOZ_ALWAYS_TRUE(bl13.WriteBytes("abcdefgh", 8));
  MOZ_ALWAYS_TRUE(bl13.WriteBytes("12345678", 8));
  MOZ_ALWAYS_TRUE(bl13.WriteBytes("ABCDEFGH", 8));
  MOZ_RELEASE_ASSERT(bl13.Size() == 24);

  // At segment border
  iter = bl13.Iter();
  MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl13, 8));
  MOZ_RELEASE_ASSERT(bl13.Truncate(iter) == 16);
  MOZ_RELEASE_ASSERT(iter.Done());
  MOZ_RELEASE_ASSERT(bl13.Size() == 8);

  // Restore state
  MOZ_ALWAYS_TRUE(bl13.WriteBytes("12345678", 8));
  MOZ_ALWAYS_TRUE(bl13.WriteBytes("ABCDEFGH", 8));
  MOZ_RELEASE_ASSERT(bl13.Size() == 24);

  // Before segment border
  iter = bl13.Iter();
  MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl13, 7));
  MOZ_RELEASE_ASSERT(bl13.Truncate(iter) == 17);
  MOZ_RELEASE_ASSERT(iter.Done());
  MOZ_RELEASE_ASSERT(bl13.Size() == 7);

  // Restore state
  MOZ_ALWAYS_TRUE(bl13.WriteBytes("h", 1));
  MOZ_ALWAYS_TRUE(bl13.WriteBytes("12345678", 8));
  MOZ_ALWAYS_TRUE(bl13.WriteBytes("ABCDEFGH", 8));
  MOZ_RELEASE_ASSERT(bl13.Size() == 24);

  // In last segment
  iter = bl13.Iter();
  MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl13, 20));
  MOZ_RELEASE_ASSERT(bl13.Truncate(iter) == 4);
  MOZ_RELEASE_ASSERT(iter.Done());
  MOZ_RELEASE_ASSERT(bl13.Size() == 20);

  // No-op truncate
  MOZ_RELEASE_ASSERT(bl13.Truncate(iter) == 0);
  MOZ_RELEASE_ASSERT(iter.Done());
  MOZ_RELEASE_ASSERT(bl13.Size() == 20);

  // No-op truncate with fresh iterator
  iter = bl13.Iter();
  MOZ_RELEASE_ASSERT(iter.AdvanceAcrossSegments(bl13, 20));
  MOZ_RELEASE_ASSERT(bl13.Truncate(iter) == 0);
  MOZ_RELEASE_ASSERT(iter.Done());
  MOZ_RELEASE_ASSERT(bl13.Size() == 20);

  // Truncate at start of buffer
  iter = bl13.Iter();
  MOZ_RELEASE_ASSERT(bl13.Truncate(iter) == 20);
  MOZ_RELEASE_ASSERT(iter.Done());
  MOZ_RELEASE_ASSERT(bl13.Size() == 0);

  // No-op truncate at start of buffer
  iter = bl13.Iter();
  MOZ_RELEASE_ASSERT(bl13.Truncate(iter) == 0);
  MOZ_RELEASE_ASSERT(iter.Done());
  MOZ_RELEASE_ASSERT(bl13.Size() == 0);

  return 0;
}