Revert "implement SkTDArray with std::vector"

This reverts commit 80e1d56e198c5fd9fe6db0c945bd558053a8dc6a.

Reason for revert: SkRTree.cpp:57 asserting, probably this?

Original change's description:
> implement SkTDArray with std::vector
> 
> It's always worth seeing if we can get away with replacing custom data
> structures with ones from the standard library.  Our array-like types
> are all good candidates to replace with std::vector, and it's especially
> easy to start with SkTDArray.  Unlike the others, it has no preallocated
> S-variant, which is tricky to make work with std::vector.
> 
> SkTDArray also has known integer overflow bugs, leading to out of range
> writes.  It'd be _very_ nice to ditch it for a better standard vector.
> 
> I removed a bunch of unused or little-used methods, and updated a couple
> call sites that used methods in unusual or dangerous ways.
> 
> I've had to tweak GrAAConvexTessellator and SkBaseShadowTessellator just
> a touch to work within the constraints of an std::vector impl.  It's not
> intended to be legal to write to the reserved-but-not-counted elements
> of an SkTDArray, but you can get away with it in our old implementation.
> This version now uses setCount() to actually reserve and count them, and
> should have the same performance and use the same amount of memory.
> 
> The PathMeasure_explosion GM I added recently to reproduce this bug now
> draws without triggering undefined behavior or ASAN errors, provided you
> have ~40GB of RAM.
> 
> Bug: skia:7674
> 
> Change-Id: I4eacae18a976cd4a6d218102f8ca5d973d4d7d0e
> Reviewed-on: https://skia-review.googlesource.com/115982
> Reviewed-by: Brian Osman <brianosman@google.com>
> Commit-Queue: Mike Klein <mtklein@chromium.org>

TBR=mtklein@chromium.org,bungeman@google.com,brianosman@google.com

Change-Id: Icffd9f22fe89746a970ff598e1a05c774960bc0e
No-Presubmit: true
No-Tree-Checks: true
No-Try: true
Bug: skia:7674
Reviewed-on: https://skia-review.googlesource.com/117901
Reviewed-by: Mike Klein <mtklein@chromium.org>
Commit-Queue: Mike Klein <mtklein@chromium.org>

6 files changed, 341 insertions, 105 deletions

diff --git a/include/private/SkTDArray.h b/include/private/SkTDArray.h
index e9660d88b7..2ba33542ca 100644
--- a/include/private/SkTDArray.h
+++ b/include/private/SkTDArray.h
@@ -1,3 +1,4 @@
+
 /*
  * Copyright 2006 The Android Open Source Project
  *
@@ -10,125 +11,362 @@
 #define SkTDArray_DEFINED
 
 #include "SkTypes.h"
-#include <vector>
-
-// SkTDArray is now a thin wrapper over std::vector.
-// Please feel free to use either.
-
-// Implementation notes:
-//   1) We take care to use SkToInt(size_t) and SkToSizeT(int) to do conversions that
-//      assert the value fits either direction.  The SkToInt(size_t) should be obvious,
-//      but even SkToSizeT(int) has caught negative values passed in where you'd expect
-//      >= 0.
-//
-//   2) We try to add yet-undefined items to the array with default initialization.
-//      This can look funny, as the only really good way to get that is to write
-//      "T v;", a T default-intialized on the stack, often meaning uninitialized.
-//      This avoids the slightly more expensive value initialization (like, floats
-//      to 0.0f) that std::vector normally provides.
-//
-//   3) See the end of the file for how we avoid std::vector<bool>.
-
-template <typename T>
-class SkTDArray {
+#include "SkMalloc.h"
+
+template <typename T> class SkTDArray {
 public:
-    SkTDArray()                            = default;
-    ~SkTDArray()                           = default;
-    SkTDArray(const SkTDArray&)            = default;
-    SkTDArray(SkTDArray&&)                 = default;
-    SkTDArray& operator=(const SkTDArray&) = default;
-    SkTDArray& operator=(SkTDArray&&)      = default;
+    SkTDArray() : fArray(nullptr), fReserve(0), fCount(0) {}
+    SkTDArray(const T src[], int count) {
+        SkASSERT(src || count == 0);
+
+        fReserve = fCount = 0;
+        fArray = nullptr;
+        if (count) {
+            fArray = (T*)sk_malloc_throw(count * sizeof(T));
+            memcpy(fArray, src, sizeof(T) * count);
+            fReserve = fCount = count;
+        }
+    }
+    SkTDArray(const SkTDArray<T>& src) : fArray(nullptr), fReserve(0), fCount(0) {
+        SkTDArray<T> tmp(src.fArray, src.fCount);
+        this->swap(tmp);
+    }
+    SkTDArray(SkTDArray<T>&& src) : fArray(nullptr), fReserve(0), fCount(0) {
+        this->swap(src);
+    }
+    ~SkTDArray() {
+        sk_free(fArray);
+    }
+
+    SkTDArray<T>& operator=(const SkTDArray<T>& src) {
+        if (this != &src) {
+            if (src.fCount > fReserve) {
+                SkTDArray<T> tmp(src.fArray, src.fCount);
+                this->swap(tmp);
+            } else {
+                sk_careful_memcpy(fArray, src.fArray, sizeof(T) * src.fCount);
+                fCount = src.fCount;
+            }
+        }
+        return *this;
+    }
+    SkTDArray<T>& operator=(SkTDArray<T>&& src) {
+        if (this != &src) {
+            this->swap(src);
+            src.reset();
+        }
+        return *this;
+    }
+
+    friend bool operator==(const SkTDArray<T>& a, const SkTDArray<T>& b) {
+        return  a.fCount == b.fCount &&
+                (a.fCount == 0 ||
+                 !memcmp(a.fArray, b.fArray, a.fCount * sizeof(T)));
+    }
+    friend bool operator!=(const SkTDArray<T>& a, const SkTDArray<T>& b) {
+        return !(a == b);
+    }
+
+    void swap(SkTDArray<T>& other) {
+        SkTSwap(fArray, other.fArray);
+        SkTSwap(fReserve, other.fReserve);
+        SkTSwap(fCount, other.fCount);
+    }
+
+    bool isEmpty() const { return fCount == 0; }
+
+    /**
+     *  Return the number of elements in the array
+     */
+    int count() const { return fCount; }
+
+    /**
+     *  Return the total number of elements allocated.
+     *  reserved() - count() gives you the number of elements you can add
+     *  without causing an allocation.
+     */
+    int reserved() const { return fReserve; }
 
-    SkTDArray(const T* src, int n) : fVec(src, src+SkToSizeT(n)) {}
+    /**
+     *  return the number of bytes in the array: count * sizeof(T)
+     */
+    size_t bytes() const { return fCount * sizeof(T); }
 
-    friend bool operator==(const SkTDArray& a, const SkTDArray& b) { return a.fVec == b.fVec; }
-    friend bool operator!=(const SkTDArray& a, const SkTDArray& b) { return a.fVec != b.fVec; }
+    T*  begin() { return fArray; }
+    const T*  begin() const { return fArray; }
+    T*  end() { return fArray ? fArray + fCount : nullptr; }
+    const T*  end() const { return fArray ? fArray + fCount : nullptr; }
 
-    void swap(SkTDArray& that) { std::swap(fVec, that.fVec); }
+    T&  operator[](int index) {
+        SkASSERT(index < fCount);
+        return fArray[index];
+    }
+    const T&  operator[](int index) const {
+        SkASSERT(index < fCount);
+        return fArray[index];
+    }
+
+    T&  getAt(int index)  {
+        return (*this)[index];
+    }
+    const T&  getAt(int index) const {
+        return (*this)[index];
+    }
+
+    void reset() {
+        if (fArray) {
+            sk_free(fArray);
+            fArray = nullptr;
+            fReserve = fCount = 0;
+        } else {
+            SkASSERT(fReserve == 0 && fCount == 0);
+        }
+    }
+
+    void rewind() {
+        // same as setCount(0)
+        fCount = 0;
+    }
+
+    /**
+     *  Sets the number of elements in the array.
+     *  If the array does not have space for count elements, it will increase
+     *  the storage allocated to some amount greater than that required.
+     *  It will never shrink the storage.
+     */
+    void setCount(int count) {
+        SkASSERT(count >= 0);
+        if (count > fReserve) {
+            this->resizeStorageToAtLeast(count);
+        }
+        fCount = count;
+    }
 
-    bool isEmpty() const { return fVec.empty(); }
-    int    count() const { return SkToInt(fVec.size()); }
-    int reserved() const { return SkToInt(fVec.capacity()); }
-    size_t bytes() const { return sizeof(T) * fVec.size(); }
+    void setReserve(int reserve) {
+        if (reserve > fReserve) {
+            this->resizeStorageToAtLeast(reserve);
+        }
+    }
 
-    const T* begin() const { return fVec.data(); }
-          T* begin()       { return fVec.data(); }
-    const T*   end() const { return this->begin() + fVec.size(); }
-          T*   end()       { return this->begin() + fVec.size(); }
+    T* prepend() {
+        this->adjustCount(1);
+        memmove(fArray + 1, fArray, (fCount - 1) * sizeof(T));
+        return fArray;
+    }
 
-    const T& operator[](int k) const { return fVec[SkToSizeT(k)]; }
-          T& operator[](int k)       { return fVec[SkToSizeT(k)]; }
-    const T&      getAt(int k) const { return fVec[SkToSizeT(k)]; }
-          T&      getAt(int k)       { return fVec[SkToSizeT(k)]; }
+    T* append() {
+        return this->append(1, nullptr);
+    }
+    T* append(int count, const T* src = nullptr) {
+        int oldCount = fCount;
+        if (count)  {
+            SkASSERT(src == nullptr || fArray == nullptr ||
+                    src + count <= fArray || fArray + oldCount <= src);
 
-    void reset() { this->~SkTDArray(); new (this) SkTDArray(); }
-    void rewind()          { fVec.clear(); }
-    void setCount  (int n) { T v; fVec.resize(SkToSizeT(n), v); }
-    void setReserve(int n) { fVec.reserve(SkToSizeT(n)); }
-    void shrinkToFit()     { fVec.shrink_to_fit(); }
+            this->adjustCount(count);
+            if (src) {
+                memcpy(fArray + oldCount, src, sizeof(T) * count);
+            }
+        }
+        return fArray + oldCount;
+    }
+
+    T* appendClear() {
+        T* result = this->append();
+        *result = 0;
+        return result;
+    }
 
-    T* append(int n = 1, const T* src = nullptr) {
-        return this->insert(this->count(), n, src);
+    T* insert(int index) {
+        return this->insert(index, 1, nullptr);
     }
-    T* insert(int ix, int n = 1, const T* src = nullptr) {
+    T* insert(int index, int count, const T* src = nullptr) {
+        SkASSERT(count);
+        SkASSERT(index <= fCount);
+        size_t oldCount = fCount;
+        this->adjustCount(count);
+        T* dst = fArray + index;
+        memmove(dst + count, dst, sizeof(T) * (oldCount - index));
         if (src) {
-            return &*fVec.insert(fVec.begin() + SkToSizeT(ix), src, src+SkToSizeT(n));
+            memcpy(dst, src, sizeof(T) * count);
         }
-        T v;
-        return &*fVec.insert(fVec.begin() + SkToSizeT(ix), SkToSizeT(n), v);
+        return dst;
     }
 
-    void remove(int ix, int n = 1) {
-        fVec.erase(fVec.begin() + SkToSizeT(ix),
-                   fVec.begin() + SkToSizeT(ix) + SkToSizeT(n));
+    void remove(int index, int count = 1) {
+        SkASSERT(index + count <= fCount);
+        fCount = fCount - count;
+        memmove(fArray + index, fArray + index + count, sizeof(T) * (fCount - index));
     }
-    void removeShuffle(int ix) {
-        std::swap(fVec[SkToSizeT(ix)], fVec.back());
-        fVec.pop_back();
+
+    void removeShuffle(int index) {
+        SkASSERT(index < fCount);
+        int newCount = fCount - 1;
+        fCount = newCount;
+        if (index != newCount) {
+            memcpy(fArray + index, fArray + newCount, sizeof(T));
+        }
+    }
+
+    template <typename S> int select(S&& selector) const {
+        const T* iter = fArray;
+        const T* stop = fArray + fCount;
+
+        for (; iter < stop; iter++) {
+            if (selector(*iter)) {
+                return SkToInt(iter - fArray);
+            }
+        }
+        return -1;
+    }
+
+    int find(const T& elem) const {
+        const T* iter = fArray;
+        const T* stop = fArray + fCount;
+
+        for (; iter < stop; iter++) {
+            if (*iter == elem) {
+                return SkToInt(iter - fArray);
+            }
+        }
+        return -1;
     }
 
-    int find(const T& value) const {
-        for (int i = 0; i < this->count(); i++) {
-            if (fVec[i] == value) {
-                return i;
+    int rfind(const T& elem) const {
+        const T* iter = fArray + fCount;
+        const T* stop = fArray;
+
+        while (iter > stop) {
+            if (*--iter == elem) {
+                return SkToInt(iter - stop);
             }
         }
         return -1;
     }
-    bool contains(const T& value) const {
-        return this->find(value) >= 0;
+
+    /**
+     * Returns true iff the array contains this element.
+     */
+    bool contains(const T& elem) const {
+        return (this->find(elem) >= 0);
+    }
+
+    /**
+     * Copies up to max elements into dst. The number of items copied is
+     * capped by count - index. The actual number copied is returned.
+     */
+    int copyRange(T* dst, int index, int max) const {
+        SkASSERT(max >= 0);
+        SkASSERT(!max || dst);
+        if (index >= fCount) {
+            return 0;
+        }
+        int count = SkMin32(max, fCount - index);
+        memcpy(dst, fArray + index, sizeof(T) * count);
+        return count;
+    }
+
+    void copy(T* dst) const {
+        this->copyRange(dst, 0, fCount);
+    }
+
+    // routines to treat the array like a stack
+    T*       push() { return this->append(); }
+    void     push(const T& elem) { *this->append() = elem; }
+    const T& top() const { return (*this)[fCount - 1]; }
+    T&       top() { return (*this)[fCount - 1]; }
+    void     pop(T* elem) { SkASSERT(fCount > 0); if (elem) *elem = (*this)[fCount - 1]; --fCount; }
+    void     pop() { SkASSERT(fCount > 0); --fCount; }
+
+    void deleteAll() {
+        T*  iter = fArray;
+        T*  stop = fArray + fCount;
+        while (iter < stop) {
+            delete *iter;
+            iter += 1;
+        }
+        this->reset();
+    }
+
+    void freeAll() {
+        T*  iter = fArray;
+        T*  stop = fArray + fCount;
+        while (iter < stop) {
+            sk_free(*iter);
+            iter += 1;
+        }
+        this->reset();
     }
 
-    void     push(const T& value)    { fVec.push_back(value); }
-    T*       push()                  { T v; fVec.push_back(v); return &fVec.back(); }
-    void     pop(T* value = nullptr) { if (value) { *value = fVec.back(); } fVec.pop_back(); }
-    const T& top() const             { return fVec.back(); }
-          T& top()                   { return fVec.back(); }
+    void unrefAll() {
+        T*  iter = fArray;
+        T*  stop = fArray + fCount;
+        while (iter < stop) {
+            (*iter)->unref();
+            iter += 1;
+        }
+        this->reset();
+    }
+
+    void safeUnrefAll() {
+        T*  iter = fArray;
+        T*  stop = fArray + fCount;
+        while (iter < stop) {
+            SkSafeUnref(*iter);
+            iter += 1;
+        }
+        this->reset();
+    }
 
-    void    deleteAll() { for (T ptr : fVec) { delete ptr;       } this->reset(); }
-    void      freeAll() { for (T ptr : fVec) { sk_free(ptr);     } this->reset(); }
-    void     unrefAll() { for (T ptr : fVec) { ptr->unref();     } this->reset(); }
-    void safeUnrefAll() { for (T ptr : fVec) { SkSafeUnref(ptr); } this->reset(); }
+    void visitAll(void visitor(T&)) {
+        T* stop = this->end();
+        for (T* curr = this->begin(); curr < stop; curr++) {
+            if (*curr) {
+                visitor(*curr);
+            }
+        }
+    }
 
-#if defined(SK_DEBUG)
-    void validate() const {}
+#ifdef SK_DEBUG
+    void validate() const {
+        SkASSERT((fReserve == 0 && fArray == nullptr) ||
+                 (fReserve > 0 && fArray != nullptr));
+        SkASSERT(fCount <= fReserve);
+    }
 #endif
 
-private:
-    std::vector<T> fVec;
-};
+    void shrinkToFit() {
+        fReserve = fCount;
+        fArray = (T*)sk_realloc_throw(fArray, fReserve * sizeof(T));
+    }
 
-// Avoid using std::vector<bool> (annoying weird bitvector specialization).
+private:
+    T*      fArray;
+    int     fReserve;
+    int     fCount;
 
-struct SkTDArray_bool {
-    bool value;
+    /**
+     *  Adjusts the number of elements in the array.
+     *  This is the same as calling setCount(count() + delta).
+     */
+    void adjustCount(int delta) {
+        this->setCount(fCount + delta);
+    }
 
-    SkTDArray_bool() = default;
-    SkTDArray_bool(bool v) : value(v) {}
-    operator bool() const { return value; }
+    /**
+     *  Increase the storage allocation such that it can hold (fCount + extra)
+     *  elements.
+     *  It never shrinks the allocation, and it may increase the allocation by
+     *  more than is strictly required, based on a private growth heuristic.
+     *
+     *  note: does NOT modify fCount
+     */
+    void resizeStorageToAtLeast(int count) {
+        SkASSERT(count > fReserve);
+        fReserve = count + 4;
+        fReserve += fReserve / 4;
+        fArray = (T*)sk_realloc_throw(fArray, fReserve * sizeof(T));
+    }
 };
 
-template <>
-class SkTDArray<bool> : public SkTDArray<SkTDArray_bool> {};
-
 #endif
diff --git a/src/core/SkPictureRecord.cpp b/src/core/SkPictureRecord.cpp
index f9d6bccc3f..6268584aa0 100644
--- a/src/core/SkPictureRecord.cpp
+++ b/src/core/SkPictureRecord.cpp
@@ -805,14 +805,14 @@ void SkPictureRecord::onDrawAnnotation(const SkRect& rect, const char key[], SkD
 ///////////////////////////////////////////////////////////////////////////////
 
 template <typename T> int find_or_append_uniqueID(SkTDArray<const T*>& array, const T* obj) {
-    for (int i = 0; i < array.count(); i++) {
-        if (array[i]->uniqueID() == obj->uniqueID()) {
-            return i;
-        }
-    }
-    int i = array.count();
-    *array.append() = SkRef(obj);
-    return i;
+    int index = array.select([&](const T* elem) {
+        return elem->uniqueID() == obj->uniqueID();
+    });
+    if (index < 0) {
+        index = array.count();
+        *array.append() = SkRef(obj);
+    }
+    return index;
 }
 
 sk_sp<SkSurface> SkPictureRecord::onNewSurface(const SkImageInfo& info, const SkSurfaceProps&) {
diff --git a/src/gpu/ops/GrAAConvexTessellator.cpp b/src/gpu/ops/GrAAConvexTessellator.cpp
index c3840ea821..9927d98b11 100644
--- a/src/gpu/ops/GrAAConvexTessellator.cpp
+++ b/src/gpu/ops/GrAAConvexTessellator.cpp
@@ -934,7 +934,7 @@ void GrAAConvexTessellator::lineTo(const SkMatrix& m, SkPoint p, CurveState curv
 
 void GrAAConvexTessellator::quadTo(const SkPoint pts[3]) {
     int maxCount = GrPathUtils::quadraticPointCount(pts, kQuadTolerance);
-    fPointBuffer.setCount(maxCount);
+    fPointBuffer.setReserve(maxCount);
     SkPoint* target = fPointBuffer.begin();
     int count = GrPathUtils::generateQuadraticPoints(pts[0], pts[1], pts[2],
                                                      kQuadTolerance, &target, maxCount);
@@ -953,7 +953,7 @@ void GrAAConvexTessellator::quadTo(const SkMatrix& m, SkPoint pts[3]) {
 void GrAAConvexTessellator::cubicTo(const SkMatrix& m, SkPoint pts[4]) {
     m.mapPoints(pts, 4);
     int maxCount = GrPathUtils::cubicPointCount(pts, kCubicTolerance);
-    fPointBuffer.setCount(maxCount);
+    fPointBuffer.setReserve(maxCount);
     SkPoint* target = fPointBuffer.begin();
     int count = GrPathUtils::generateCubicPoints(pts[0], pts[1], pts[2], pts[3],
             kCubicTolerance, &target, maxCount);
diff --git a/src/utils/SkOffsetPolygon.cpp b/src/utils/SkOffsetPolygon.cpp
index 1bef50cf01..c8ebbeb7af 100755
--- a/src/utils/SkOffsetPolygon.cpp
+++ b/src/utils/SkOffsetPolygon.cpp
@@ -274,9 +274,7 @@ bool SkInsetConvexPolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize
     static constexpr SkScalar kCleanupTolerance = 0.01f;
 
     insetPolygon->reset();
-    if (insetVertexCount >= 0) {
-        insetPolygon->setReserve(insetVertexCount);
-    }
+    insetPolygon->setReserve(insetVertexCount);
     currIndex = -1;
     for (int i = 0; i < inputPolygonSize; ++i) {
         if (edgeData[i].fValid && (currIndex == -1 ||
diff --git a/src/utils/SkShadowTessellator.cpp b/src/utils/SkShadowTessellator.cpp
index 0d3746ab79..75e4059222 100755
--- a/src/utils/SkShadowTessellator.cpp
+++ b/src/utils/SkShadowTessellator.cpp
@@ -185,7 +185,7 @@ void SkBaseShadowTessellator::handleQuad(const SkPoint pts[3]) {
     }
     // TODO: Pull PathUtils out of Ganesh?
     int maxCount = GrPathUtils::quadraticPointCount(pts, kQuadTolerance);
-    fPointBuffer.setCount(maxCount);
+    fPointBuffer.setReserve(maxCount);
     SkPoint* target = fPointBuffer.begin();
     int count = GrPathUtils::generateQuadraticPoints(pts[0], pts[1], pts[2],
                                                      kQuadTolerance, &target, maxCount);
@@ -210,7 +210,7 @@ void SkBaseShadowTessellator::handleCubic(const SkMatrix& m, SkPoint pts[4]) {
 #if SK_SUPPORT_GPU
     // TODO: Pull PathUtils out of Ganesh?
     int maxCount = GrPathUtils::cubicPointCount(pts, kCubicTolerance);
-    fPointBuffer.setCount(maxCount);
+    fPointBuffer.setReserve(maxCount);
     SkPoint* target = fPointBuffer.begin();
     int count = GrPathUtils::generateCubicPoints(pts[0], pts[1], pts[2], pts[3],
                                                  kCubicTolerance, &target, maxCount);
diff --git a/tests/SubsetPath.cpp b/tests/SubsetPath.cpp
index c1f2a62e26..6a7660e527 100644
--- a/tests/SubsetPath.cpp
+++ b/tests/SubsetPath.cpp
@@ -193,7 +193,7 @@ SkPath SubsetVerbs::getSubsetPath() const {
     bool addLineTo = false;
     while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
         bool enabled = SkPath::kLine_Verb <= verb && verb <= SkPath::kCubic_Verb
-            ? (bool)fSelected[verbIndex++] : false;
+            ? fSelected[verbIndex++] : false;
         if (enabled) {
             if (addMoveTo) {
                 result.moveTo(pts[0]);