PathParser.kt

/*
 * Copyright 2019 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package androidx.compose.ui.graphics.vector

import androidx.compose.ui.graphics.Path
import androidx.compose.ui.graphics.vector.PathNode.ArcTo
import androidx.compose.ui.graphics.vector.PathNode.Close
import androidx.compose.ui.graphics.vector.PathNode.CurveTo
import androidx.compose.ui.graphics.vector.PathNode.HorizontalTo
import androidx.compose.ui.graphics.vector.PathNode.LineTo
import androidx.compose.ui.graphics.vector.PathNode.MoveTo
import androidx.compose.ui.graphics.vector.PathNode.QuadTo
import androidx.compose.ui.graphics.vector.PathNode.ReflectiveCurveTo
import androidx.compose.ui.graphics.vector.PathNode.ReflectiveQuadTo
import androidx.compose.ui.graphics.vector.PathNode.RelativeArcTo
import androidx.compose.ui.graphics.vector.PathNode.RelativeCurveTo
import androidx.compose.ui.graphics.vector.PathNode.RelativeHorizontalTo
import androidx.compose.ui.graphics.vector.PathNode.RelativeLineTo
import androidx.compose.ui.graphics.vector.PathNode.RelativeMoveTo
import androidx.compose.ui.graphics.vector.PathNode.RelativeQuadTo
import androidx.compose.ui.graphics.vector.PathNode.RelativeReflectiveCurveTo
import androidx.compose.ui.graphics.vector.PathNode.RelativeReflectiveQuadTo
import androidx.compose.ui.graphics.vector.PathNode.RelativeVerticalTo
import androidx.compose.ui.graphics.vector.PathNode.VerticalTo
import androidx.compose.ui.util.toRadians
import kotlin.math.PI
import kotlin.math.abs
import kotlin.math.atan2
import kotlin.math.ceil
import kotlin.math.cos
import kotlin.math.sin
import kotlin.math.sqrt
import kotlin.math.tan

class PathParser {

    private data class PathPoint(var x: Float = 0.0f, var y: Float = 0.0f) {
        fun reset() {
            x = 0.0f
            y = 0.0f
        }
    }

    private val nodes = mutableListOf<PathNode>()

    fun clear() {
        nodes.clear()
    }

    private val currentPoint = PathPoint()
    private val ctrlPoint = PathPoint()
    private val segmentPoint = PathPoint()
    private val reflectiveCtrlPoint = PathPoint()

    /**
     * Parses the path string to create a collection of PathNode instances with their corresponding
     * arguments
     * throws an IllegalArgumentException or NumberFormatException if the parameters are invalid
     */
    fun parsePathString(pathData: String): PathParser {
        nodes.clear()

        var start = 0
        var end = 1
        while (end < pathData.length) {
            end = nextStart(pathData, end)
            val s = pathData.substring(start, end).trim { it <= ' ' }
            if (s.isNotEmpty()) {
                val args = getFloats(s)
                addNode(s[0], args)
            }

            start = end
            end++
        }
        if (end - start == 1 && start < pathData.length) {
            addNode(pathData[start], FloatArray(0))
        }

        return this
    }

    fun addPathNodes(nodes: List<PathNode>): PathParser {
        this.nodes.addAll(nodes)
        return this
    }

    fun toNodes(): List<PathNode> = nodes

    fun toPath(target: Path = Path()): Path {
        target.reset()
        currentPoint.reset()
        ctrlPoint.reset()
        segmentPoint.reset()
        reflectiveCtrlPoint.reset()

        var previousNode: PathNode? = null
        for (node in nodes) {
            if (previousNode == null) previousNode = node
            when (node) {
                is Close -> close(target)
                is RelativeMoveTo -> node.relativeMoveTo(target)
                is MoveTo -> node.moveTo(target)
                is RelativeLineTo -> node.relativeLineTo(target)
                is LineTo -> node.lineTo(target)
                is RelativeHorizontalTo -> node.relativeHorizontalTo(target)
                is HorizontalTo -> node.horizontalTo(target)
                is RelativeVerticalTo -> node.relativeVerticalTo(target)
                is VerticalTo -> node.verticalTo(target)
                is RelativeCurveTo -> node.relativeCurveTo(target)
                is CurveTo -> node.curveTo(target)
                is RelativeReflectiveCurveTo ->
                    node.relativeReflectiveCurveTo(previousNode.isCurve, target)
                is ReflectiveCurveTo -> node.reflectiveCurveTo(previousNode.isCurve, target)
                is RelativeQuadTo -> node.relativeQuadTo(target)
                is QuadTo -> node.quadTo(target)
                is RelativeReflectiveQuadTo ->
                    node.relativeReflectiveQuadTo(previousNode.isQuad, target)
                is ReflectiveQuadTo -> node.reflectiveQuadTo(previousNode.isQuad, target)
                is RelativeArcTo -> node.relativeArcTo(target)
                is ArcTo -> node.arcTo(target)
            }
            previousNode = node
        }
        return target
    }

    private fun close(target: Path) {
        currentPoint.x = segmentPoint.x
        currentPoint.y = segmentPoint.y
        ctrlPoint.x = segmentPoint.x
        ctrlPoint.y = segmentPoint.y

        target.close()
        target.moveTo(currentPoint.x, currentPoint.y)
    }

    private fun RelativeMoveTo.relativeMoveTo(target: Path) {
        currentPoint.x += dx
        currentPoint.y += dy
        target.relativeMoveTo(dx, dy)
        segmentPoint.x = currentPoint.x
        segmentPoint.y = currentPoint.y
    }

    private fun MoveTo.moveTo(target: Path) {
        currentPoint.x = x
        currentPoint.y = y
        target.moveTo(x, y)
        segmentPoint.x = currentPoint.x
        segmentPoint.y = currentPoint.y
    }

    private fun RelativeLineTo.relativeLineTo(target: Path) {
        target.relativeLineTo(dx, dy)
        currentPoint.x += dx
        currentPoint.y += dy
    }

    private fun LineTo.lineTo(target: Path) {
        target.lineTo(x, y)
        currentPoint.x = x
        currentPoint.y = y
    }

    private fun RelativeHorizontalTo.relativeHorizontalTo(target: Path) {
        target.relativeLineTo(dx, 0.0f)
        currentPoint.x += dx
    }

    private fun HorizontalTo.horizontalTo(target: Path) {
        target.lineTo(x, currentPoint.y)
        currentPoint.x = x
    }

    private fun RelativeVerticalTo.relativeVerticalTo(target: Path) {
        target.relativeLineTo(0.0f, dy)
        currentPoint.y += dy
    }

    private fun VerticalTo.verticalTo(target: Path) {
        target.lineTo(currentPoint.x, y)
        currentPoint.y = y
    }

    private fun RelativeCurveTo.relativeCurveTo(target: Path) {
        target.relativeCubicTo(
            dx1, dy1,
            dx2, dy2,
            dx3, dy3
        )
        ctrlPoint.x = currentPoint.x + dx2
        ctrlPoint.y = currentPoint.y + dy2
        currentPoint.x += dx3
        currentPoint.y += dy3
    }

    private fun CurveTo.curveTo(target: Path) {
        target.cubicTo(
            x1, y1,
            x2, y2,
            x3, y3
        )
        ctrlPoint.x = x2
        ctrlPoint.y = y2
        currentPoint.x = x3
        currentPoint.y = y3
    }

    private fun RelativeReflectiveCurveTo.relativeReflectiveCurveTo(
        prevIsCurve: Boolean,
        target: Path
    ) {
        if (prevIsCurve) {
            reflectiveCtrlPoint.x = currentPoint.x - ctrlPoint.x
            reflectiveCtrlPoint.y = currentPoint.y - ctrlPoint.y
        } else {
            reflectiveCtrlPoint.reset()
        }

        target.relativeCubicTo(
            reflectiveCtrlPoint.x, reflectiveCtrlPoint.y,
            dx1, dy1,
            dx2, dy2
        )
        ctrlPoint.x = currentPoint.x + dx1
        ctrlPoint.y = currentPoint.y + dy1
        currentPoint.x += dx2
        currentPoint.y += dy2
    }

    private fun ReflectiveCurveTo.reflectiveCurveTo(prevIsCurve: Boolean, target: Path) {
        if (prevIsCurve) {
            reflectiveCtrlPoint.x = 2 * currentPoint.x - ctrlPoint.x
            reflectiveCtrlPoint.y = 2 * currentPoint.y - ctrlPoint.y
        } else {
            reflectiveCtrlPoint.x = currentPoint.x
            reflectiveCtrlPoint.y = currentPoint.y
        }

        target.cubicTo(
            reflectiveCtrlPoint.x, reflectiveCtrlPoint.y,
            x1, y1, x2, y2
        )
        ctrlPoint.x = x1
        ctrlPoint.y = y1
        currentPoint.x = x2
        currentPoint.y = y2
    }

    private fun RelativeQuadTo.relativeQuadTo(target: Path) {
        target.relativeQuadraticBezierTo(dx1, dy1, dx2, dy2)
        ctrlPoint.x = currentPoint.x + dx1
        ctrlPoint.y = currentPoint.y + dy1
        currentPoint.x += dx1
        currentPoint.y += dy1
    }

    private fun QuadTo.quadTo(target: Path) {
        target.quadraticBezierTo(x1, y1, x2, y2)
        ctrlPoint.x = x1
        ctrlPoint.y = y1
        currentPoint.x = x2
        currentPoint.y = y2
    }

    private fun RelativeReflectiveQuadTo.relativeReflectiveQuadTo(
        prevIsQuad: Boolean,
        target: Path
    ) {
        if (prevIsQuad) {
            reflectiveCtrlPoint.x = currentPoint.x - ctrlPoint.x
            reflectiveCtrlPoint.y = currentPoint.y - ctrlPoint.y
        } else {
            reflectiveCtrlPoint.reset()
        }

        target.relativeQuadraticBezierTo(
            reflectiveCtrlPoint.x,
            reflectiveCtrlPoint.y, dx, dy
        )
        ctrlPoint.x = currentPoint.x + reflectiveCtrlPoint.x
        ctrlPoint.y = currentPoint.y + reflectiveCtrlPoint.y
        currentPoint.x += dx
        currentPoint.y += dy
    }

    private fun ReflectiveQuadTo.reflectiveQuadTo(prevIsQuad: Boolean, target: Path) {
        if (prevIsQuad) {
            reflectiveCtrlPoint.x = 2 * currentPoint.x - ctrlPoint.x
            reflectiveCtrlPoint.y = 2 * currentPoint.y - ctrlPoint.y
        } else {
            reflectiveCtrlPoint.x = currentPoint.x
            reflectiveCtrlPoint.y = currentPoint.y
        }
        target.quadraticBezierTo(
            reflectiveCtrlPoint.x,
            reflectiveCtrlPoint.y, x, y
        )
        ctrlPoint.x = reflectiveCtrlPoint.x
        ctrlPoint.y = reflectiveCtrlPoint.y
        currentPoint.x = x
        currentPoint.y = y
    }

    private fun RelativeArcTo.relativeArcTo(target: Path) {
        val arcStartX = arcStartDx + currentPoint.x
        val arcStartY = arcStartDy + currentPoint.y

        drawArc(
            target,
            currentPoint.x.toDouble(),
            currentPoint.y.toDouble(),
            arcStartX.toDouble(),
            arcStartY.toDouble(),
            horizontalEllipseRadius.toDouble(),
            verticalEllipseRadius.toDouble(),
            theta.toDouble(),
            isMoreThanHalf,
            isPositiveArc
        )
        currentPoint.x = arcStartX
        currentPoint.y = arcStartY

        ctrlPoint.x = currentPoint.x
        ctrlPoint.y = currentPoint.y
    }

    private fun ArcTo.arcTo(target: Path) {
        drawArc(
            target,
            currentPoint.x.toDouble(),
            currentPoint.y.toDouble(),
            arcStartX.toDouble(),
            arcStartY.toDouble(),
            horizontalEllipseRadius.toDouble(),
            verticalEllipseRadius.toDouble(),
            theta.toDouble(),
            isMoreThanHalf,
            isPositiveArc
        )

        currentPoint.x = arcStartX
        currentPoint.y = arcStartY

        ctrlPoint.x = currentPoint.x
        ctrlPoint.y = currentPoint.y
    }

    private fun drawArc(
        p: Path,
        x0: Double,
        y0: Double,
        x1: Double,
        y1: Double,
        a: Double,
        b: Double,
        theta: Double,
        isMoreThanHalf: Boolean,
        isPositiveArc: Boolean
    ) {

        /* Convert rotation angle from degrees to radians */
        val thetaD = theta.toRadians()
        /* Pre-compute rotation matrix entries */
        val cosTheta = cos(thetaD)
        val sinTheta = sin(thetaD)
        /* Transform (x0, y0) and (x1, y1) into unit space */
        /* using (inverse) rotation, followed by (inverse) scale */
        val x0p = (x0 * cosTheta + y0 * sinTheta) / a
        val y0p = (-x0 * sinTheta + y0 * cosTheta) / b
        val x1p = (x1 * cosTheta + y1 * sinTheta) / a
        val y1p = (-x1 * sinTheta + y1 * cosTheta) / b

        /* Compute differences and averages */
        val dx = x0p - x1p
        val dy = y0p - y1p
        val xm = (x0p + x1p) / 2
        val ym = (y0p + y1p) / 2
        /* Solve for intersecting unit circles */
        val dsq = dx * dx + dy * dy
        if (dsq == 0.0) {
            return /* Points are coincident */
        }
        val disc = 1.0 / dsq - 1.0 / 4.0
        if (disc < 0.0) {
            val adjust = (sqrt(dsq) / 1.99999).toFloat()
            drawArc(
                p, x0, y0, x1, y1, a * adjust,
                b * adjust, theta, isMoreThanHalf, isPositiveArc
            )
            return /* Points are too far apart */
        }
        val s = sqrt(disc)
        val sdx = s * dx
        val sdy = s * dy
        var cx: Double
        var cy: Double
        if (isMoreThanHalf == isPositiveArc) {
            cx = xm - sdy
            cy = ym + sdx
        } else {
            cx = xm + sdy
            cy = ym - sdx
        }

        val eta0 = atan2(y0p - cy, x0p - cx)

        val eta1 = atan2(y1p - cy, x1p - cx)

        var sweep = eta1 - eta0
        if (isPositiveArc != (sweep >= 0)) {
            if (sweep > 0) {
                sweep -= 2 * PI
            } else {
                sweep += 2 * PI
            }
        }

        cx *= a
        cy *= b
        val tcx = cx
        cx = cx * cosTheta - cy * sinTheta
        cy = tcx * sinTheta + cy * cosTheta

        arcToBezier(
            p, cx, cy, a, b, x0, y0, thetaD,
            eta0, sweep
        )
    }

    /**
     * Converts an arc to cubic Bezier segments and records them in p.
     *
     * @param p The target for the cubic Bezier segments
     * @param cx The x coordinate center of the ellipse
     * @param cy The y coordinate center of the ellipse
     * @param a The radius of the ellipse in the horizontal direction
     * @param b The radius of the ellipse in the vertical direction
     * @param e1x E(eta1) x coordinate of the starting point of the arc
     * @param e1y E(eta2) y coordinate of the starting point of the arc
     * @param theta The angle that the ellipse bounding rectangle makes with horizontal plane
     * @param start The start angle of the arc on the ellipse
     * @param sweep The angle (positive or negative) of the sweep of the arc on the ellipse
     */
    private fun arcToBezier(
        p: Path,
        cx: Double,
        cy: Double,
        a: Double,
        b: Double,
        e1x: Double,
        e1y: Double,
        theta: Double,
        start: Double,
        sweep: Double
    ) {
        var eta1x = e1x
        var eta1y = e1y
        // Taken from equations at: http://spaceroots.org/documents/ellipse/node8.html
        // and http://www.spaceroots.org/documents/ellipse/node22.html

        // Maximum of 45 degrees per cubic Bezier segment
        val numSegments = ceil(abs(sweep * 4 / PI)).toInt()

        var eta1 = start
        val cosTheta = cos(theta)
        val sinTheta = sin(theta)
        val cosEta1 = cos(eta1)
        val sinEta1 = sin(eta1)
        var ep1x = (-a * cosTheta * sinEta1) - (b * sinTheta * cosEta1)
        var ep1y = (-a * sinTheta * sinEta1) + (b * cosTheta * cosEta1)

        val anglePerSegment = sweep / numSegments
        for (i in 0 until numSegments) {
            val eta2 = eta1 + anglePerSegment
            val sinEta2 = sin(eta2)
            val cosEta2 = cos(eta2)
            val e2x = cx + (a * cosTheta * cosEta2) - (b * sinTheta * sinEta2)
            val e2y = cy + (a * sinTheta * cosEta2) + (b * cosTheta * sinEta2)
            val ep2x = (-a * cosTheta * sinEta2) - (b * sinTheta * cosEta2)
            val ep2y = (-a * sinTheta * sinEta2) + (b * cosTheta * cosEta2)
            val tanDiff2 = tan((eta2 - eta1) / 2)
            val alpha = sin(eta2 - eta1) * (sqrt(4 + 3.0 * tanDiff2 * tanDiff2) - 1) / 3
            val q1x = eta1x + alpha * ep1x
            val q1y = eta1y + alpha * ep1y
            val q2x = e2x - alpha * ep2x
            val q2y = e2y - alpha * ep2y

            // TODO (njawad) figure out if this is still necessary?
            // Adding this no-op call to workaround a proguard related issue.
            // p.relativeLineTo(0.0, 0.0)

            p.cubicTo(
                q1x.toFloat(),
                q1y.toFloat(),
                q2x.toFloat(),
                q2y.toFloat(),
                e2x.toFloat(),
                e2y.toFloat()
            )
            eta1 = eta2
            eta1x = e2x
            eta1y = e2y
            ep1x = ep2x
            ep1y = ep2y
        }
    }

    private fun addNode(cmd: Char, args: FloatArray) {
        nodes.addAll(cmd.toPathNodes(args))
    }

    private fun nextStart(s: String, end: Int): Int {
        var index = end
        var c: Char

        while (index < s.length) {
            c = s[index]
            // Note that 'e' or 'E' are not valid path commands, but could be
            // used for floating point numbers' scientific notation.
            // Therefore, when searching for next command, we should ignore 'e'
            // and 'E'.
            if (((c - 'A') * (c - 'Z') <= 0 || (c - 'a') * (c - 'z') <= 0) &&
                c != 'e' && c != 'E'
            ) {
                return index
            }
            index++
        }
        return index
    }

    private fun getFloats(s: String): FloatArray {
        if (s[0] == 'z' || s[0] == 'Z') {
            return FloatArray(0)
        }
        val results = FloatArray(s.length)
        var count = 0
        var startPosition = 1
        var endPosition: Int

        val result = ExtractFloatResult()
        val totalLength = s.length

        // The startPosition should always be the first character of the
        // current number, and endPosition is the character after the current
        // number.
        while (startPosition < totalLength) {
            extract(s, startPosition, result)
            endPosition = result.endPosition

            if (startPosition < endPosition) {
                results[count++] =
                    s.substring(startPosition, endPosition).toFloat()
            }

            if (result.endWithNegativeOrDot) {
                // Keep the '-' or '.' sign with next number.
                startPosition = endPosition
            } else {
                startPosition = endPosition + 1
            }
        }
        return copyOfRange(results, 0, count)
    }

    private fun copyOfRange(original: FloatArray, start: Int, end: Int): FloatArray {
        if (start > end) {
            throw IllegalArgumentException()
        }
        val originalLength = original.size
        if (start < 0 || start > originalLength) {
            throw IndexOutOfBoundsException()
        }
        val resultLength = end - start
        val copyLength = minOf(resultLength, originalLength - start)
        val result = FloatArray(resultLength)
        original.copyInto(result, 0, start, start + copyLength)
        return result
    }

    private fun extract(s: String, start: Int, result: ExtractFloatResult) {
        // Now looking for ' ', ',', '.' or '-' from the start.
        var currentIndex = start
        var foundSeparator = false
        result.endWithNegativeOrDot = false
        var secondDot = false
        var isExponential = false
        while (currentIndex < s.length) {
            val isPrevExponential = isExponential
            isExponential = false
            val currentChar = s[currentIndex]
            when (currentChar) {
                ' ', ',' -> foundSeparator = true
                '-' ->
                    // The negative sign following a 'e' or 'E' is not a separator.
                    if (currentIndex != start && !isPrevExponential) {
                        foundSeparator = true
                        result.endWithNegativeOrDot = true
                    }
                '.' ->
                    if (!secondDot) {
                        secondDot = true
                    } else {
                        // This is the second dot, and it is considered as a separator.
                        foundSeparator = true
                        result.endWithNegativeOrDot = true
                    }
                'e', 'E' -> isExponential = true
            }
            if (foundSeparator) {
                break
            }
            currentIndex++
        }
        // When there is nothing found, then we put the end position to the end
        // of the string.
        result.endPosition = currentIndex
    }

    private data class ExtractFloatResult(
        // We need to return the position of the next separator and whether the
        // next float starts with a '-' or a '.'.
        var endPosition: Int = 0,
        var endWithNegativeOrDot: Boolean = false
    )
}