/*
 * Copyright 2006 The Android Open Source Project
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#include "include/core/SkPath.h"
#include "include/core/SkPathBuilder.h"
#include "include/core/SkPathTypes.h"
#include "include/core/SkRRect.h"
#include "include/core/SkSpan.h"
#include "include/private/base/SkMalloc.h"
#include "include/private/base/SkTArray.h"
#include "include/private/base/SkTo.h"
#include "src/base/SkFloatBits.h"
#include "src/core/SkEdgeClipper.h"
#include "src/core/SkGeometry.h"
#include "src/core/SkPathEnums.h"
#include "src/core/SkPathPriv.h"
#include "src/core/SkPathRawShapes.h"
#include "src/core/SkPointPriv.h"
#include "src/core/SkSpanPriv.h"

#include <algorithm>
#include <cmath>
#include <cstring>
#include <limits.h>
#include <utility>

SkPath::SkPath(sk_sp<SkPathData> pd, SkPathFillType ft, bool isVolatile)
    : fPathData(std::move(pd))
    , fFillType(ft)
    , fIsVolatile(isVolatile)
{
    SkASSERT(fPathData);
}

SkPath::SkPath(SkPathFillType ft)
    : fPathData(SkPathData::Empty())
    , fFillType(ft)
    , fIsVolatile(false)
{}

SkPath::SkPath(const SkPath&) = default;
SkPath& SkPath::operator=(const SkPath&) = default;
SkPath::SkPath(SkPath&&) = default;
SkPath& SkPath::operator=(SkPath&&) = default;

SkPath::~SkPath() {
    SkDEBUGCODE(this->validate();)
}

void SkPath::setConvexity(SkPathConvexity c) const {
    fPathData->setConvexity(c);
}

SkPathConvexity SkPath::getConvexityOrUnknown() const {
    return fPathData->getConvexityOrUnknown();
}

bool operator==(const SkPath& a, const SkPath& b) {
    return &a == &b ||
          (a.fFillType == b.fFillType && *a.fPathData == *b.fPathData);
}

void SkPath::swap(SkPath& that) {
    if (this != &that) {
        fPathData.swap(that.fPathData);
        std::swap(fFillType, that.fFillType);
        std::swap(fIsVolatile, that.fIsVolatile);
    }
}

SkPath& SkPath::reset() {
    *this = SkPath();
    return *this;
}

const SkRect& SkPath::getBounds() const {
    return fPathData->bounds();
}

uint32_t SkPath::getSegmentMasks() const {
    return fPathData->segmentMask();
}

bool SkPath::isFinite() const {
    return fPathData.get() != PeekErrorSingleton();
}

bool SkPath::isValid() const { return this->isFinite(); }

uint32_t SkPath::getGenerationID() const { return fPathData->uniqueID(); }

#ifdef SK_DEBUG
void SkPath::validate() const {}
#endif

std::optional<SkPathOvalInfo> SkPath::getOvalInfo() const { return fPathData->asOval(); }
std::optional<SkPathRRectInfo> SkPath::getRRectInfo() const { return fPathData->asRRect(); }

SkSpan<const SkPoint> SkPath::points() const { return fPathData->points(); }
SkSpan<const SkPathVerb> SkPath::verbs() const { return fPathData->verbs(); }
SkSpan<const float> SkPath::conicWeights() const { return fPathData->conics(); }

SkPath SkPath::Raw(SkSpan<const SkPoint> pts, SkSpan<const SkPathVerb> vbs,
                   SkSpan<const float> ws, SkPathFillType ft, bool isVolatile) {
    return MakeNullCheck(SkPathData::Make(pts, vbs, ws), ft, isVolatile);
}

SkPath SkPath::Rect(const SkRect& r, SkPathFillType ft, SkPathDirection dir, unsigned startIndex) {
    startIndex &= 3;    // keep it legal
    return MakeNullCheck(SkPathData::Rect(r, dir, startIndex), ft, false);
}

SkPath SkPath::Oval(const SkRect& r, SkPathDirection dir, unsigned startIndex) {
    startIndex &= 3;    // keep it legal
    return MakeNullCheck(SkPathData::Oval(r, dir, startIndex), SkPathFillType::kDefault, false);
}

SkPath SkPath::RRect(const SkRRect& rr, SkPathDirection dir, unsigned startIndex) {
    startIndex &= 7;    // keep it legal
    // To be backwards compatible with the old impl for building a rrect path, we
    // first check to see if the rrect itself can be simplified...
    const SkRect& bounds = rr.getBounds();
    auto [asType, newIndex] = SkPathPriv::SimplifyRRect(rr, startIndex);
    switch (asType) {
        case SkPathPriv::RRectAsEnum::kRect:
            return SkPath::Rect(bounds, SkPathFillType::kDefault, dir, newIndex);

        case SkPathPriv::RRectAsEnum::kOval:
            return SkPath::Oval(bounds, dir, newIndex);

        case SkPathPriv::RRectAsEnum::kRRect:
            // fall through
            break;
    }
    return MakeNullCheck(SkPathData::RRect(rr, dir, newIndex), SkPathFillType::kDefault, false);
}

SkPath SkPath::Polygon(SkSpan<const SkPoint> pts, bool isClosed,
                       SkPathFillType ft, bool isVolatile) {
    return MakeNullCheck(SkPathData::Polygon(pts, isClosed), ft, isVolatile);
}

std::optional<SkPath> SkPath::tryMakeTransform(const SkMatrix& matrix) const {
    if (auto pdata = fPathData->makeTransform(matrix)) {
        return SkPath(std::move(pdata), fFillType, fIsVolatile);
    }
    return {};
}

SkPath SkPath::makeTransform(const SkMatrix& matrix) const {
    if (!this->isFinite()) {
        return *this;
    }
    if (auto newpath = this->tryMakeTransform(matrix)) {
        return *newpath;
    }
    return SkPath(sk_ref_sp(PeekErrorSingleton()), fFillType, false);
}

std::optional<SkPathRaw> SkPath::raw(SkResolveConvexity rc) const {
    return fPathData->raw(fFillType, rc);
}

static inline bool check_edge_against_rect(const SkPoint& p0,
                                           const SkPoint& p1,
                                           const SkRect& rect,
                                           SkPathDirection dir) {
    const SkPoint* edgeBegin;
    SkVector v;
    if (SkPathDirection::kCW == dir) {
        v = p1 - p0;
        edgeBegin = &p0;
    } else {
        v = p0 - p1;
        edgeBegin = &p1;
    }
    if (v.fX || v.fY) {
        // check the cross product of v with the vec from edgeBegin to each rect corner
        SkScalar yL = v.fY * (rect.fLeft - edgeBegin->fX);
        SkScalar xT = v.fX * (rect.fTop - edgeBegin->fY);
        SkScalar yR = v.fY * (rect.fRight - edgeBegin->fX);
        SkScalar xB = v.fX * (rect.fBottom - edgeBegin->fY);
        if ((xT < yL) || (xT < yR) || (xB < yL) || (xB < yR)) {
            return false;
        }
    }
    return true;
}

bool SkPath::conservativelyContainsRect(const SkRect& rect) const {
    const SkPathConvexity convexity = this->getConvexity();
    if (!SkPathConvexity_IsConvex(convexity)) {
        return false;
    }

    const auto direction = SkPathConvexity_ToDirection(convexity);
    if (!direction) {
        return false;
    }

    SkPoint firstPt;
    SkPoint prevPt;
    int segmentCount = 0;
    SkDEBUGCODE(int moveCnt = 0;)

    for (auto [verb, pts, weight] : SkPathPriv::Iterate(*this)) {
        if (verb == SkPathVerb::kClose || (segmentCount > 0 && verb == SkPathVerb::kMove)) {
            // Closing the current contour; but since convexity is a precondition, it's the only
            // contour that matters.
            SkASSERT(moveCnt);
            segmentCount++;
            break;
        } else if (verb == SkPathVerb::kMove) {
            // A move at the start of the contour (or multiple leading moves, in which case we
            // keep the last one before a non-move verb).
            SkASSERT(!segmentCount);
            SkDEBUGCODE(++moveCnt);
            firstPt = prevPt = pts[0];
        } else {
            int pointCount = SkPathPriv::PtsInVerb((unsigned) verb);
            SkASSERT(pointCount > 0);

            if (!SkPathPriv::AllPointsEq({pts, (size_t)pointCount + 1})) {
                SkASSERT(moveCnt);
                int nextPt = pointCount;
                segmentCount++;

                if (prevPt == pts[nextPt]) {
                    // A pre-condition to getting here is that the path is convex, so if a
                    // verb's start and end points are the same, it means it's the only
                    // verb in the contour (and the only contour). While it's possible for
                    // such a single verb to be a convex curve, we do not have any non-zero
                    // length edges to conservatively test against without splitting or
                    // evaluating the curve. For simplicity, just reject the rectangle.
                    return false;
                } else if (SkPathVerb::kConic == verb) {
                    SkConic orig;
                    orig.set(pts, *weight);
                    SkPoint quadPts[5];
                    int count = orig.chopIntoQuadsPOW2(quadPts, 1);
                    SkASSERT_RELEASE(2 == count);

                    if (!check_edge_against_rect(quadPts[0], quadPts[2], rect, *direction)) {
                        return false;
                    }
                    if (!check_edge_against_rect(quadPts[2], quadPts[4], rect, *direction)) {
                        return false;
                    }
                } else {
                    if (!check_edge_against_rect(prevPt, pts[nextPt], rect, *direction)) {
                        return false;
                    }
                }
                prevPt = pts[nextPt];
            }
        }
    }

    if (segmentCount) {
        return check_edge_against_rect(prevPt, firstPt, rect, *direction);
    }
    return false;
}

bool SkPath::isLastContourClosed() const {
    SkSpan<const SkPathVerb> verbs = this->verbs();
    return !verbs.empty() && verbs.back() == SkPathVerb::kClose;
}

bool SkPath::isLine(SkPoint line[2]) const {
    SkSpan<const SkPathVerb> verbs = this->verbs();
    if (verbs.size() == 2 && verbs[1] == SkPathVerb::kLine) {
        SkASSERT(verbs[0] == SkPathVerb::kMove);
        SkSpan<const SkPoint> pts = this->points();
        SkASSERT(pts.size() == 2);
        if (line) {
            line[0] = pts[0];
            line[1] = pts[1];
        }
        return true;
    }
    return false;
}

bool SkPath::isEmpty() const {
    SkDEBUGCODE(this->validate();)
    return this->verbs().empty();
}

bool SkPath::isConvex() const {
    return SkPathConvexity_IsConvex(this->getConvexity());
}

bool SkPath::isRect(SkRect* rect, bool* isClosed, SkPathDirection* direction) const {
    SkDEBUGCODE(this->validate();)
    SkSpan<const SkPoint> pts = this->points();
    SkSpan<const SkPathVerb> vbs = this->verbs();
    if (auto rc = SkPathPriv::IsRectContour(pts, vbs, this->getSegmentMasks(), false)) {
        if (rect) {
            *rect = rc->fRect;
        }
        if (isClosed) {
            *isClosed = rc->fIsClosed;
        }
        if (direction) {
            *direction = rc->fDirection;
        }
        return true;
    }
    return false;
}

bool SkPath::isOval(SkRect* bounds) const {
    if (auto info = this->getOvalInfo()) {
        if (bounds) {
            *bounds = info->fBounds;
        }
        return true;
    }
    return false;
}

bool SkPath::isRRect(SkRRect* rrect) const {
    if (auto info = this->getRRectInfo()) {
        if (rrect) {
            *rrect = info->fRRect;
        }
        return true;
    }
    return false;
}

#ifdef SK_LEGACY_PATH_ACCESSORS
size_t SkPath::getPoints(SkSpan<SkPoint> dst) const {
    SkDEBUGCODE(this->validate();)
    SkSpan<const SkPoint> src = this->points();

    const size_t n = std::min(dst.size(), src.size());
    sk_careful_memcpy(dst.data(), src.data(), n * sizeof(SkPoint));
    return src.size();
}

SkPoint SkPath::getPoint(int index) const {
    SkSpan<const SkPoint> pts = this->points();
    if ((unsigned)index < (unsigned)pts.size()) {
        return pts[index];
    }
    return SkPoint::Make(0, 0);
}

size_t SkPath::getVerbs(SkSpan<uint8_t> dst) const {
    SkDEBUGCODE(this->validate();)
    SkSpan<const SkPathVerb> src = this->verbs();

    const size_t n = std::min(dst.size(), src.size());
    sk_careful_memcpy(dst.data(), src.data(), n);
    return src.size();
}
#endif

size_t SkPath::approximateBytesUsed() const {
    return sizeof(SkPath)
         + this->points().size_bytes()
         + this->verbs().size_bytes()
         + this->conicWeights().size_bytes();
}

std::optional<SkPoint> SkPath::getLastPt() const {
    SkDEBUGCODE(this->validate();)
    SkSpan<const SkPoint> pts = this->points();
    if (!pts.empty()) {
        return pts.back();
    }
    return {};
}

SkPathConvexity SkPath::getConvexity() const {
// Enable once we fix all the bugs
//    SkDEBUGCODE(this->isConvexityAccurate());
    SkPathConvexity convexity = this->getConvexityOrUnknown();
    if (convexity == SkPathConvexity::kUnknown) {
        convexity = this->computeConvexity();
    }
    SkASSERT(convexity != SkPathConvexity::kUnknown);
    return convexity;
}

SkPathIter SkPath::iter() const {
    return { this->points(), this->verbs(), this->conicWeights() };
}

///////////////////////////////////////////////////////////////////////////////

SkPath::Iter::Iter() {
#ifdef SK_DEBUG
    fPts = nullptr;
    fConicWeights = nullptr;
    fMoveTo.fX = fMoveTo.fY = fLastPt.fX = fLastPt.fY = 0;
    fForceClose = fCloseLine = false;
#endif
    // need to init enough to make next() harmlessly return kDone_Verb
    fVerbs = nullptr;
    fVerbStop = nullptr;
    fNeedClose = false;
}

SkPath::Iter::Iter(const SkPath& path, bool forceClose) {
    this->setPath(path, forceClose);
}

void SkPath::Iter::setPath(const SkPath& path, bool forceClose) {
    fPts = path.points().data();

    const SkSpan<const SkPathVerb> vbs = path.verbs();
    fVerbs = vbs.begin();
    fVerbStop = vbs.end();
    // For empty paths we receive an empty span, which should yield a nullptr fVerbsStop.
    SkASSERT(!!fVerbs == !!fVerbStop);

    fConicWeights = path.conicWeights().data();
    if (fConicWeights) {
      fConicWeights -= 1;  // begin one behind
    }
    fLastPt.fX = fLastPt.fY = 0;
    fMoveTo.fX = fMoveTo.fY = 0;
    fForceClose = SkToU8(forceClose);
    fNeedClose = false;
}

bool SkPath::Iter::isClosedContour() const {
    if (fVerbs == nullptr || fVerbs == fVerbStop) {
        return false;
    }
    if (fForceClose) {
        return true;
    }

    const SkPathVerb* verbs = fVerbs;
    const SkPathVerb* stop = fVerbStop;

    if (SkPathVerb::kMove == *verbs) {
        verbs += 1; // skip the initial moveto
    }

    while (verbs < stop) {
        // verbs points one beyond the current verb, decrement first.
        SkPathVerb v = *verbs++;
        if (SkPathVerb::kMove == v) {
            break;
        }
        if (SkPathVerb::kClose == v) {
            return true;
        }
    }
    return false;
}

SkPathVerb SkPath::Iter::autoClose(SkPoint pts[2]) {
    SkASSERT(pts);
    if (fLastPt != fMoveTo) {
        // A special case: if both points are NaN, SkPoint::operation== returns
        // false, but the iterator expects that they are treated as the same.
        // (consider SkPoint is a 2-dimension float point).
        if (SkIsNaN(fLastPt.fX) || SkIsNaN(fLastPt.fY) ||
            SkIsNaN(fMoveTo.fX) || SkIsNaN(fMoveTo.fY)) {
            return SkPathVerb::kClose;
        }

        pts[0] = fLastPt;
        pts[1] = fMoveTo;
        fLastPt = fMoveTo;
        fCloseLine = true;
        return SkPathVerb::kLine;
    }
    pts[0] = fMoveTo;
    return SkPathVerb::kClose;
}

SkPath::Verb SkPath::Iter::next(SkPoint ptsParam[4]) {
    SkASSERT(ptsParam);
    SkASSERT(!!fVerbs == !!fVerbStop);

    if (fVerbs == fVerbStop) {
        // Close the curve if requested and if there is some curve to close
        if (fNeedClose) {
            if (SkPathVerb::kLine == this->autoClose(ptsParam)) {
                return kLine_Verb;
            }
            fNeedClose = false;
            return kClose_Verb;
        }
        return kDone_Verb;
    }

    SkPathVerb verb = *fVerbs++;
    const SkPoint* SK_RESTRICT srcPts = fPts;
    SkPoint* SK_RESTRICT       pts = ptsParam;

    switch (verb) {
        case SkPathVerb::kMove:
            if (fNeedClose) {
                fVerbs--; // move back one verb
                verb = this->autoClose(pts);
                if (verb == SkPathVerb::kClose) {
                    fNeedClose = false;
                }
                return (Verb)verb;
            }
            if (fVerbs == fVerbStop) {    // might be a trailing moveto
                return kDone_Verb;
            }
            fMoveTo = *srcPts;
            pts[0] = *srcPts;
            srcPts += 1;
            fLastPt = fMoveTo;
            fNeedClose = fForceClose;
            break;
        case SkPathVerb::kLine:
            pts[0] = fLastPt;
            pts[1] = srcPts[0];
            fLastPt = srcPts[0];
            fCloseLine = false;
            srcPts += 1;
            break;
        case SkPathVerb::kConic:
            fConicWeights += 1;
            [[fallthrough]];
        case SkPathVerb::kQuad:
            pts[0] = fLastPt;
            memcpy(&pts[1], srcPts, 2 * sizeof(SkPoint));
            fLastPt = srcPts[1];
            srcPts += 2;
            break;
        case SkPathVerb::kCubic:
            pts[0] = fLastPt;
            memcpy(&pts[1], srcPts, 3 * sizeof(SkPoint));
            fLastPt = srcPts[2];
            srcPts += 3;
            break;
        case SkPathVerb::kClose:
            verb = this->autoClose(pts);
            if (verb == SkPathVerb::kLine) {
                fVerbs--; // move back one verb
            } else {
                fNeedClose = false;
            }
            fLastPt = fMoveTo;
            break;
    }
    fPts = srcPts;
    return (Verb)verb;
}

static inline uint8_t SkPathIterPointsPerVerb(SkPathVerb verb) {
    static const uint8_t gCounts[] = { 1, 2, 3, 3, 4, 0 };
    unsigned index = static_cast<unsigned>(verb);
    SkASSERT(index < std::size(gCounts));
    return gCounts[index];
}

std::optional<SkPath::IterRec> SkPath::Iter::next() {
    auto legacyVerb = this->next(fStorage.data());
    if (legacyVerb == kDone_Verb) {
        return {};
    }

    SkPathVerb verb = static_cast<SkPathVerb>(legacyVerb);
    return {{
        verb,
        {fStorage.data(), SkPathIterPointsPerVerb(verb)},
        verb == SkPathVerb::kConic ? *fConicWeights : 1,
    }};
}

void SkPath::RawIter::setPath(const SkPath& path) {
    SkPathPriv::Iterate iterate(path);
    fIter = iterate.begin();
    fEnd = iterate.end();
}

SkPath::Verb SkPath::RawIter::next(SkPoint pts[4]) {
    if (!(fIter != fEnd)) {
        return kDone_Verb;
    }
    auto [verb, iterPts, weights] = *fIter;
    int numPts;
    switch (verb) {
        case SkPathVerb::kMove: numPts = 1; break;
        case SkPathVerb::kLine: numPts = 2; break;
        case SkPathVerb::kQuad: numPts = 3; break;
        case SkPathVerb::kConic:
            numPts = 3;
            fConicWeight = *weights;
            break;
        case SkPathVerb::kCubic: numPts = 4; break;
        case SkPathVerb::kClose: numPts = 0; break;
    }
    memcpy(pts, iterPts, sizeof(SkPoint) * numPts);
    ++fIter;
    return (Verb) verb;
}

std::optional<SkPath::IterRec> SkPath::RawIter::next() {
    if (fIter == fEnd) {
        return {};
    }

    auto [verb, iterPts, weights] = *fIter++;
    return {{
        verb,
        {iterPts, SkPathIterPointsPerVerb(verb)},
        verb == SkPathVerb::kConic ? *weights : 1
    }};
}

///////////////////////////////////////////////////////////////////////////////

SkPath SkPath::makeFillType(SkPathFillType ft) const {
    SkPath copy = *this;
    copy.setFillType(ft);
    return copy;
}

SkPath SkPath::makeToggleInverseFillType() const {
    return this->makeFillType(SkPathFillType_ToggleInverse(fFillType));
}

SkPath SkPath::makeIsVolatile(bool v) const {
    SkPath copy = *this;
    copy.fIsVolatile = v;
    return copy;
}

SkPathConvexity SkPath::computeConvexity() const {
    if (auto c = this->getConvexityOrUnknown(); c != SkPathConvexity::kUnknown) {
        return c;
    }

    SkPathConvexity convexity = SkPathConvexity::kConcave;

    if (this->isFinite()) {
        convexity = SkPathPriv::ComputeConvexity(this->points(),
                                                 this->verbs(),
                                                 this->conicWeights());
    }

    SkASSERT(convexity != SkPathConvexity::kUnknown);
    this->setConvexity(convexity);
    return convexity;
}

bool SkPath::contains(SkPoint p) const {
    const auto raw = SkPathPriv::Raw(*this, SkResolveConvexity::kNo);
    return raw.has_value() && SkPathPriv::Contains(*raw, p);
}

int SkPath::ConvertConicToQuads(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2,
                                SkScalar w, SkPoint pts[], int pow2) {
    const SkConic conic(p0, p1, p2, w);
    return conic.chopIntoQuadsPOW2(pts, pow2);
}

///////////////////////////////////////////////////////////////////////////////////////////////////

SkRect SkPath::computeTightBounds() const {
    // If we're only lines, then our (quick) bounds is also tight.
    if (this->getSegmentMasks() == SkPath::kLine_SegmentMask) {
        return this->getBounds();
    }

    return SkPathPriv::ComputeTightBounds(this->points(),
                                          this->verbs(),
                                          this->conicWeights());
}

bool SkPath::IsLineDegenerate(const SkPoint& p1, const SkPoint& p2, bool exact) {
    return exact ? p1 == p2 : SkPointPriv::EqualsWithinTolerance(p1, p2);
}

bool SkPath::IsQuadDegenerate(const SkPoint& p1, const SkPoint& p2,
                                const SkPoint& p3, bool exact) {
    return exact ? p1 == p2 && p2 == p3 : SkPointPriv::EqualsWithinTolerance(p1, p2) &&
            SkPointPriv::EqualsWithinTolerance(p2, p3);
}

bool SkPath::IsCubicDegenerate(const SkPoint& p1, const SkPoint& p2,
                                const SkPoint& p3, const SkPoint& p4, bool exact) {
    return exact ? p1 == p2 && p2 == p3 && p3 == p4 :
            SkPointPriv::EqualsWithinTolerance(p1, p2) &&
            SkPointPriv::EqualsWithinTolerance(p2, p3) &&
            SkPointPriv::EqualsWithinTolerance(p3, p4);
}

SkPath SkPath::RRect(const SkRRect& rr, SkPathDirection dir) {
    // legacy start indices: 6 (CW) and 7 (CCW)
    return RRect(rr, dir, dir == SkPathDirection::kCW ? 6 : 7);
}

SkPath SkPath::Oval(const SkRect& r, SkPathDirection dir) {
    // legacy start index: 1
    return Oval(r, dir, 1);
}

SkPath SkPath::Circle(SkScalar x, SkScalar y, SkScalar r, SkPathDirection dir) {
    if (r >= 0) {
        return Oval(SkRect::MakeLTRB(x - r, y - r, x + r, y + r), dir);
    } else {
        return SkPath();
    }
}

SkPath SkPath::RRect(const SkRect& r, SkScalar rx, SkScalar ry, SkPathDirection dir) {
    return RRect(SkRRect::MakeRectXY(r, rx, ry), dir);
}

SkPathFirstDirection SkPathPriv::ComputeFirstDirection(const SkPath& path) {
    auto convexity = path.getConvexityOrUnknown();
    if (SkPathConvexity_IsConvex(convexity)) {
        // Note, this can return kUnknown. That is valid. If we've determined that the
        // path is convex, then we've already tried to compute its first-direction. If
        // that failed, then kUnknown is the right answer.
        return SkPathConvexity_ToFirstDirection(convexity);
    }

    // Note, this can compute a 'first' direction, even for non-convex shapes.
    if (auto raw = SkPathPriv::Raw(path, SkResolveConvexity::kNo)) {
        return ComputeFirstDirection(*raw);
    } else {
        return SkPathFirstDirection::kUnknown;
    }
}

/*
 *  This returns a singleton instance which SkPath uses to signify that its pathdata is in error:
 *  either because the inputs were invalid (e.g. bad verbs), or its coordintes were non-finite
 *  (either from the client, or after a makeTransform() call).
 */
SkPathData* SkPath::PeekErrorSingleton() {
    static SkPathData* gErrorSingleton = SkPathData::MakeNoCheck({}, {}, {}, {}, {}).release();

    // Make sure MakeNoCheck() didn't alias us to the standard Empty instance. We want our
    // pointer to be distinct from that one.
    SkASSERT(gErrorSingleton != SkPathData::Empty().get());

    return gErrorSingleton;
}

SkPath SkPath::MakeNullCheck(sk_sp<SkPathData> pdata, SkPathFillType ft, bool isVolatile) {
    if (!pdata) {
        pdata = sk_ref_sp(PeekErrorSingleton());
    }
    return SkPath(std::move(pdata), ft, isVolatile);
}

///////////////////////////////////////////////////////////////////////////////////////////////////

struct SkHalfPlane {
    SkScalar fA, fB, fC;

    SkScalar eval(SkScalar x, SkScalar y) const {
        return fA * x + fB * y + fC;
    }
    SkScalar operator()(SkScalar x, SkScalar y) const { return this->eval(x, y); }

    bool normalize() {
        double a = fA;
        double b = fB;
        double c = fC;
        double dmag = sqrt(a * a + b * b);
        // length of initial plane normal is zero
        if (dmag == 0) {
           fA = fB = 0;
           fC = SK_Scalar1;
           return true;
        }
        double dscale = sk_ieee_double_divide(1.0, dmag);
        a *= dscale;
        b *= dscale;
        c *= dscale;
        // check if we're not finite, or normal is zero-length
        if (!SkIsFinite(a, b, c) ||
            (a == 0 && b == 0)) {
            fA = fB = 0;
            fC = SK_Scalar1;
            return false;
        }
        fA = a;
        fB = b;
        fC = c;
        return true;
    }

    enum Result {
        kAllNegative,
        kAllPositive,
        kMixed
    };
    Result test(const SkRect& bounds) const {
        // check whether the diagonal aligned with the normal crosses the plane
        SkPoint diagMin, diagMax;
        if (fA >= 0) {
            diagMin.fX = bounds.fLeft;
            diagMax.fX = bounds.fRight;
        } else {
            diagMin.fX = bounds.fRight;
            diagMax.fX = bounds.fLeft;
        }
        if (fB >= 0) {
            diagMin.fY = bounds.fTop;
            diagMax.fY = bounds.fBottom;
        } else {
            diagMin.fY = bounds.fBottom;
            diagMax.fY = bounds.fTop;
        }
        SkScalar test = this->eval(diagMin.fX, diagMin.fY);
        SkScalar sign = test*this->eval(diagMax.fX, diagMax.fY);
        if (sign > 0) {
            // the path is either all on one side of the half-plane or the other
            if (test < 0) {
                return kAllNegative;
            } else {
                return kAllPositive;
            }
        }
        return kMixed;
    }
};

// assumes plane is pre-normalized
static std::optional<SkPath> clip(const SkPath& path, const SkHalfPlane& plane) {
    SkMatrix mx;
    SkPoint p0 = { -plane.fA*plane.fC, -plane.fB*plane.fC };
    mx.setAll( plane.fB, plane.fA, p0.fX,
              -plane.fA, plane.fB, p0.fY,
                      0,        0,     1);
    auto inv = mx.invert();
    if (!inv) {
        return {};
    }

    auto rotated = path.tryMakeTransform(*inv);
    if (!rotated) {
        return {};
    }
    auto raw = SkPathPriv::Raw(*rotated, SkResolveConvexity::kNo);
    if (!raw) {
        SkASSERT(false);    // if rotated was valid, so should the raw
        return {};
    }

    SkScalar big = SK_ScalarMax;
    SkRect clip = {-big, 0, big, big };

    struct Rec {
        SkPathBuilder fResult;
        SkPoint       fPrev = {0,0};
    } rec;

    SkEdgeClipper::ClipPath(*raw, clip, false,
                            [](SkEdgeClipper* clipper, bool newCtr, void* ctx) {
        Rec* rec = (Rec*)ctx;

        bool addLineTo = false;
        SkPoint      pts[4];
        while (auto verb = clipper->next(pts)) {
            if (newCtr) {
                rec->fResult.moveTo(pts[0]);
                rec->fPrev = pts[0];
                newCtr = false;
            }

            if (addLineTo || pts[0] != rec->fPrev) {
                rec->fResult.lineTo(pts[0]);
            }

            switch (*verb) {
                case SkPathVerb::kLine:
                    rec->fResult.lineTo(pts[1]);
                    rec->fPrev = pts[1];
                    break;
                case SkPathVerb::kQuad:
                    rec->fResult.quadTo(pts[1], pts[2]);
                    rec->fPrev = pts[2];
                    break;
                case SkPathVerb::kCubic:
                    rec->fResult.cubicTo(pts[1], pts[2], pts[3]);
                    rec->fPrev = pts[3];
                    break;
                default: break;
            }
            addLineTo = true;
        }
    }, &rec);

    rec.fResult.setFillType(path.getFillType());
    SkPath result = rec.fResult.detach(&mx);
    if (!result.isFinite()) {
        return {};
    }
    return result;
}

// true means we have written to clippedPath
bool SkPathPriv::PerspectiveClip(const SkPath& path, const SkMatrix& matrix, SkPath* clippedPath) {
    if (!matrix.hasPerspective()) {
        return false;
    }

    SkHalfPlane plane {
        matrix[SkMatrix::kMPersp0],
        matrix[SkMatrix::kMPersp1],
        matrix[SkMatrix::kMPersp2] - kW0PlaneDistance
    };
    if (plane.normalize()) {
        switch (plane.test(path.getBounds())) {
            case SkHalfPlane::kAllPositive:
                return false;
            case SkHalfPlane::kMixed: {
                if (auto result = clip(path, plane)) {
                    *clippedPath = *result;
                } else {
                    *clippedPath = SkPath(); // clipped out (or failed)
                }
                return true;
            }
            default: break; // handled outside of the switch
        }
    }
    // clipped out (or failed)
    *clippedPath = SkPath();
    return true;
}

std::optional<SkPathRectInfo> SkPathPriv::IsSimpleRect(const SkPath& path, bool isSimpleFill) {
    if (path.getSegmentMasks() != SkPath::kLine_SegmentMask) {
        return {};
    }
    SkPoint rectPts[5];
    int rectPtCnt = 0;
    bool needsClose = !isSimpleFill;
    for (auto [v, verbPts, w] : SkPathPriv::Iterate(path)) {
        switch (v) {
            case SkPathVerb::kMove:
                if (0 != rectPtCnt) {
                    return {};
                }
                rectPts[0] = verbPts[0];
                ++rectPtCnt;
                break;
            case SkPathVerb::kLine:
                if (5 == rectPtCnt) {
                    return {};
                }
                rectPts[rectPtCnt] = verbPts[1];
                ++rectPtCnt;
                break;
            case SkPathVerb::kClose:
                if (4 == rectPtCnt) {
                    rectPts[4] = rectPts[0];
                    rectPtCnt = 5;
                }
                needsClose = false;
                break;
            case SkPathVerb::kQuad:
            case SkPathVerb::kConic:
            case SkPathVerb::kCubic:
                return {};
        }
    }
    if (needsClose) {
        return {};
    }
    if (rectPtCnt < 5) {
        return {};
    }
    if (rectPts[0] != rectPts[4]) {
        return {};
    }
    // Check for two cases of rectangles: pts 0 and 3 form a vertical edge or a horizontal edge (
    // and pts 1 and 2 the opposite vertical or horizontal edge).
    bool vec03IsVertical;
    if (rectPts[0].fX == rectPts[3].fX && rectPts[1].fX == rectPts[2].fX &&
        rectPts[0].fY == rectPts[1].fY && rectPts[3].fY == rectPts[2].fY) {
        // Make sure it has non-zero width and height
        if (rectPts[0].fX == rectPts[1].fX || rectPts[0].fY == rectPts[3].fY) {
            return {};
        }
        vec03IsVertical = true;
    } else if (rectPts[0].fY == rectPts[3].fY && rectPts[1].fY == rectPts[2].fY &&
               rectPts[0].fX == rectPts[1].fX && rectPts[3].fX == rectPts[2].fX) {
        // Make sure it has non-zero width and height
        if (rectPts[0].fY == rectPts[1].fY || rectPts[0].fX == rectPts[3].fX) {
            return {};
        }
        vec03IsVertical = false;
    } else {
        return {};
    }

    SkPathRectInfo info;

    // Set sortFlags so that it has the low bit set if pt index 0 is on right edge and second bit
    // set if it is on the bottom edge.
    unsigned sortFlags =
            ((rectPts[0].fX < rectPts[2].fX) ? 0b00 : 0b01) |
            ((rectPts[0].fY < rectPts[2].fY) ? 0b00 : 0b10);
    switch (sortFlags) {
        case 0b00:
            info.fRect.setLTRB(rectPts[0].fX, rectPts[0].fY, rectPts[2].fX, rectPts[2].fY);
            info.fDirection = vec03IsVertical ? SkPathDirection::kCW : SkPathDirection::kCCW;
            info.fStartIndex = 0;
            break;
        case 0b01:
            info.fRect.setLTRB(rectPts[2].fX, rectPts[0].fY, rectPts[0].fX, rectPts[2].fY);
            info.fDirection = vec03IsVertical ? SkPathDirection::kCCW : SkPathDirection::kCW;
            info.fStartIndex = 1;
            break;
        case 0b10:
            info.fRect.setLTRB(rectPts[0].fX, rectPts[2].fY, rectPts[2].fX, rectPts[0].fY);
            info.fDirection = vec03IsVertical ? SkPathDirection::kCCW : SkPathDirection::kCW;
            info.fStartIndex = 3;
            break;
        case 0b11:
            info.fRect.setLTRB(rectPts[2].fX, rectPts[2].fY, rectPts[0].fX, rectPts[0].fY);
            info.fDirection = vec03IsVertical ? SkPathDirection::kCW : SkPathDirection::kCCW;
            info.fStartIndex = 2;
            break;
    }
    return info;
}

//////////////////////////////////////////////////////////////////////////////////////////////////

SkPathEdgeIter::SkPathEdgeIter(const SkPathRaw& raw) {
    fMoveToPtr = fPts = raw.fPoints.data();
    fVerbs = raw.fVerbs.data();
    fVerbsStop = fVerbs + raw.fVerbs.size();
    fConicWeights = raw.fConics.data();
    if (fConicWeights) {
        fConicWeights -= 1;  // begin one behind
    }

    fNeedsCloseLine = false;
    fNextIsNewContour = false;
    SkDEBUGCODE(fIsConic = false;)
}

SkPathEdgeIter::SkPathEdgeIter(const SkPath& path)
    : SkPathEdgeIter(SkPathPriv::Raw(path, SkResolveConvexity::kNo).value_or(SkPathRaw::Empty()))
{}