Add support for gradient opacity stops (#2062)

Fixes #2054
diff --git a/lottie/src/main/java/com/airbnb/lottie/parser/GradientColorParser.java b/lottie/src/main/java/com/airbnb/lottie/parser/GradientColorParser.java
index 6654998..4eda1fd 100644
--- a/lottie/src/main/java/com/airbnb/lottie/parser/GradientColorParser.java
+++ b/lottie/src/main/java/com/airbnb/lottie/parser/GradientColorParser.java
@@ -2,14 +2,13 @@
 
 import android.graphics.Color;
 
-import androidx.annotation.IntRange;
-
 import com.airbnb.lottie.model.content.GradientColor;
 import com.airbnb.lottie.parser.moshi.JsonReader;
 import com.airbnb.lottie.utils.MiscUtils;
 
 import java.io.IOException;
 import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.List;
 
 public class GradientColorParser implements com.airbnb.lottie.parser.ValueParser<GradientColor> {
@@ -105,7 +104,7 @@
     }
 
     GradientColor gradientColor = new GradientColor(positions, colors);
-    addOpacityStopsToGradientIfNeeded(gradientColor, array);
+    gradientColor = addOpacityStopsToGradientIfNeeded(gradientColor, array);
     return gradientColor;
   }
 
@@ -118,47 +117,108 @@
    * This should be a good approximation is nearly all cases. However, if there are many more
    * opacity stops than color stops, information will be lost.
    */
-  private void addOpacityStopsToGradientIfNeeded(GradientColor gradientColor, List<Float> array) {
+  private GradientColor addOpacityStopsToGradientIfNeeded(GradientColor gradientColor, List<Float> array) {
     int startIndex = colorPoints * 4;
     if (array.size() <= startIndex) {
-      return;
+      return gradientColor;
     }
 
+    float[] colorStopPositions = gradientColor.getPositions();
+    int[] colorStopColors = gradientColor.getColors();
+
     int opacityStops = (array.size() - startIndex) / 2;
-    double[] positions = new double[opacityStops];
-    double[] opacities = new double[opacityStops];
+    float[] opacityStopPositions = new float[opacityStops];
+    float[] opacityStopOpacities = new float[opacityStops];
 
     for (int i = startIndex, j = 0; i < array.size(); i++) {
       if (i % 2 == 0) {
-        positions[j] = array.get(i);
+        opacityStopPositions[j] = array.get(i);
       } else {
-        opacities[j] = array.get(i);
+        opacityStopOpacities[j] = array.get(i);
         j++;
       }
     }
 
-    for (int i = 0; i < gradientColor.getSize(); i++) {
-      int color = gradientColor.getColors()[i];
-      color = Color.argb(
-          getOpacityAtPosition(gradientColor.getPositions()[i], positions, opacities),
-          Color.red(color),
-          Color.green(color),
-          Color.blue(color)
-      );
-      gradientColor.getColors()[i] = color;
-    }
-  }
+    int newColorPoints = colorPoints + opacityStops;
+    float[] newPositions = new float[newColorPoints];
+    int[] newColors = new int[newColorPoints];
 
-  @IntRange(from = 0, to = 255)
-  private int getOpacityAtPosition(double position, double[] positions, double[] opacities) {
-    for (int i = 1; i < positions.length; i++) {
-      double lastPosition = positions[i - 1];
-      double thisPosition = positions[i];
-      if (positions[i] >= position) {
-        double progress = MiscUtils.clamp((position - lastPosition) / (thisPosition - lastPosition), 0, 1);
-        return (int) (255 * MiscUtils.lerp(opacities[i - 1], opacities[i], progress));
+    System.arraycopy(gradientColor.getPositions(), 0, newPositions, 0, colorPoints);
+    System.arraycopy(opacityStopPositions, 0, newPositions, colorPoints, opacityStops);
+    Arrays.sort(newPositions);
+
+    for (int i = 0; i < newColorPoints; i++) {
+      float position = newPositions[i];
+      int colorStopIndex = Arrays.binarySearch(colorStopPositions, position);
+      int opacityIndex = Arrays.binarySearch(opacityStopPositions, position);
+      if (colorStopIndex < 0 || opacityIndex > 0) {
+        // This is a stop derived from an opacity stop.
+        if (opacityIndex < 0) {
+          throw new IllegalArgumentException("Unable to find opacity stop position for " + position);
+          // TODO: use this backup instead…
+          // opacityIndex = -(opacityIndex + 1);
+        }
+        newColors[i] = getColorInBetweenColorStops(position, opacityStopOpacities[opacityIndex], colorStopPositions, colorStopColors);
+      } else {
+        // This os a step derived from a color stop.
+        newColors[i] = getColorWithOpacityStops(colorStopColors[colorStopIndex], position, opacityStopPositions, opacityStopOpacities);
       }
     }
-    return (int) (255 * opacities[opacities.length - 1]);
+    return new GradientColor(newPositions, newColors);
+  }
+
+  private int getColorInBetweenColorStops(float position, float opacity, float[] colorStopPositions, int[] colorStopColors) {
+    if (colorStopColors.length < 2 || position == colorStopPositions[0]) {
+      return colorStopColors[0];
+    }
+    for (int i = 1; i < colorStopPositions.length; i++) {
+      float colorStopPosition = colorStopPositions[i];
+      if (colorStopPosition < position && i != colorStopPositions.length - 1) {
+        continue;
+      }
+      // We found the position in which position is between i - 1 and i.
+      float distanceBetweenColors = colorStopPositions[i] - colorStopPositions[i - 1];
+      float distanceToLowerColor = position - colorStopPositions[i - 1];
+      float percentage = distanceToLowerColor / distanceBetweenColors;
+      int upperColor = colorStopColors[i];
+      int lowerColor = colorStopColors[i - 1];
+      int a = (int) (opacity * 255);
+      int r = MiscUtils.lerp(Color.red(lowerColor), Color.red(upperColor), percentage);
+      int g = MiscUtils.lerp(Color.green(lowerColor), Color.green(upperColor), percentage);
+      int b = MiscUtils.lerp(Color.blue(lowerColor), Color.blue(upperColor), percentage);
+      return Color.argb(a, r, g, b);
+    }
+    throw new IllegalArgumentException("Unreachable code.");
+  }
+
+  private int getColorWithOpacityStops(int color, float position, float[] opacityStopPositions, float[] opacityStopOpacities) {
+    if (opacityStopOpacities.length < 2 || position <= opacityStopPositions[0]) {
+      int a = (int) (opacityStopOpacities[0] * 255);
+      int r = Color.red(color);
+      int g = Color.green(color);
+      int b = Color.blue(color);
+      return Color.argb(a, r, g, b);
+    }
+    for (int i = 1; i < opacityStopPositions.length; i++) {
+      float opacityStopPosition = opacityStopPositions[i];
+      if (opacityStopPosition < position && i != opacityStopPositions.length - 1) {
+        continue;
+      }
+      final int a;
+      if (opacityStopPosition <= position) {
+        a = (int) (opacityStopOpacities[i] * 255);
+      } else {
+        // We found the position in which position in between i - 1 and i.
+        float distanceBetweenOpacities = opacityStopPositions[i] - opacityStopPositions[i - 1];
+        float distanceToLowerOpacity = position - opacityStopPositions[i - 1];
+        float percentage = distanceToLowerOpacity / distanceBetweenOpacities;
+        a = (int) (MiscUtils.lerp(opacityStopOpacities[i - 1], opacityStopOpacities[i], percentage) * 255);
+      }
+      int r = Color.red(color);
+      int g = Color.green(color);
+      int b = Color.blue(color);
+      return Color.argb(a, r, g, b);
+    }
+    throw new IllegalArgumentException("Unreachable code.");
   }
 }
\ No newline at end of file
diff --git a/snapshot-tests/src/main/assets/Tests/OpacityStops.json b/snapshot-tests/src/main/assets/Tests/OpacityStops.json
new file mode 100644
index 0000000..ef5a8f7
--- /dev/null
+++ b/snapshot-tests/src/main/assets/Tests/OpacityStops.json
@@ -0,0 +1,494 @@
+{
+  "tgs": 1,
+  "v": "5.5.2",
+  "fr": 60,
+  "ip": 0,
+  "op": 180,
+  "w": 512,
+  "h": 512,
+  "nm": "02_ricl_klass - 3:00",
+  "ddd": 0,
+  "assets": [],
+  "layers": [
+    {
+      "ddd": 0,
+      "ind": 6,
+      "ty": 4,
+      "parent": 5,
+      "sr": 1,
+      "ks": {
+        "o": {
+          "a": 1,
+          "k": [
+            {
+              "i": {
+                "x": [
+                  0.833
+                ],
+                "y": [
+                  0.833
+                ]
+              },
+              "o": {
+                "x": [
+                  0.167
+                ],
+                "y": [
+                  0.167
+                ]
+              },
+              "t": -105,
+              "s": [
+                0
+              ]
+            },
+            {
+              "i": {
+                "x": [
+                  0.833
+                ],
+                "y": [
+                  0.833
+                ]
+              },
+              "o": {
+                "x": [
+                  0.167
+                ],
+                "y": [
+                  0.167
+                ]
+              },
+              "t": -104,
+              "s": [
+                100
+              ]
+            },
+            {
+              "i": {
+                "x": [
+                  0.833
+                ],
+                "y": [
+                  0.833
+                ]
+              },
+              "o": {
+                "x": [
+                  0.167
+                ],
+                "y": [
+                  0.167
+                ]
+              },
+              "t": 34,
+              "s": [
+                100
+              ]
+            },
+            {
+              "i": {
+                "x": [
+                  0.833
+                ],
+                "y": [
+                  0.833
+                ]
+              },
+              "o": {
+                "x": [
+                  0.167
+                ],
+                "y": [
+                  0.167
+                ]
+              },
+              "t": 35,
+              "s": [
+                0
+              ]
+            },
+            {
+              "i": {
+                "x": [
+                  0.833
+                ],
+                "y": [
+                  0.833
+                ]
+              },
+              "o": {
+                "x": [
+                  0.167
+                ],
+                "y": [
+                  0.167
+                ]
+              },
+              "t": 75,
+              "s": [
+                0
+              ]
+            },
+            {
+              "i": {
+                "x": [
+                  0.833
+                ],
+                "y": [
+                  0.833
+                ]
+              },
+              "o": {
+                "x": [
+                  0.167
+                ],
+                "y": [
+                  0.167
+                ]
+              },
+              "t": 76,
+              "s": [
+                100
+              ]
+            },
+            {
+              "i": {
+                "x": [
+                  0.833
+                ],
+                "y": [
+                  0.833
+                ]
+              },
+              "o": {
+                "x": [
+                  0.167
+                ],
+                "y": [
+                  0.167
+                ]
+              },
+              "t": 214,
+              "s": [
+                100
+              ]
+            },
+            {
+              "t": 215,
+              "s": [
+                0
+              ]
+            }
+          ]
+        },
+        "p": {
+          "a": 0,
+          "k": [
+            0,
+            -0.031,
+            0
+          ]
+        },
+        "a": {
+          "a": 0,
+          "k": [
+            -87,
+            -18.182,
+            0
+          ]
+        },
+        "s": {
+          "a": 0,
+          "k": [
+            50,
+            33,
+            100
+          ]
+        }
+      },
+      "ao": 0,
+      "shapes": [
+        {
+          "ty": "gr",
+          "it": [
+            {
+              "ind": 0,
+              "ty": "sh",
+              "ks": {
+                "a": 1,
+                "k": [
+                  {
+                    "i": {
+                      "x": 0.833,
+                      "y": 0.833
+                    },
+                    "o": {
+                      "x": 0.167,
+                      "y": 0.167
+                    },
+                    "t": 213,
+                    "s": [
+                      {
+                        "i": [
+                          [
+                            0,
+                            0
+                          ],
+                          [
+                            0,
+                            0
+                          ],
+                          [
+                            0,
+                            0
+                          ],
+                          [
+                            0,
+                            0
+                          ]
+                        ],
+                        "o": [
+                          [
+                            0,
+                            0
+                          ],
+                          [
+                            0,
+                            0
+                          ],
+                          [
+                            0,
+                            0
+                          ],
+                          [
+                            0,
+                            0
+                          ]
+                        ],
+                        "v": [
+                          [
+                            571.25,
+                            -298.22
+                          ],
+                          [
+                            -192.5,
+                            -267.902
+                          ],
+                          [
+                            -182.875,
+                            510.152
+                          ],
+                          [
+                            575.125,
+                            547.848
+                          ]
+                        ],
+                        "c": true
+                      }
+                    ]
+                  },
+                  {
+                    "t": 214,
+                    "s": [
+                      {
+                        "i": [
+                          [
+                            0,
+                            0
+                          ],
+                          [
+                            0,
+                            0
+                          ],
+                          [
+                            0,
+                            0
+                          ],
+                          [
+                            0,
+                            0
+                          ]
+                        ],
+                        "o": [
+                          [
+                            0,
+                            0
+                          ],
+                          [
+                            0,
+                            0
+                          ],
+                          [
+                            0,
+                            0
+                          ],
+                          [
+                            0,
+                            0
+                          ]
+                        ],
+                        "v": [
+                          [
+                            122.25,
+                            -242.159
+                          ],
+                          [
+                            -192.5,
+                            -267.902
+                          ],
+                          [
+                            -181.875,
+                            178.333
+                          ],
+                          [
+                            175.125,
+                            141.788
+                          ]
+                        ],
+                        "c": true
+                      }
+                    ]
+                  }
+                ]
+              },
+              "hd": false
+            },
+            {
+              "ty": "gf",
+              "o": {
+                "a": 0,
+                "k": 100
+              },
+              "r": 1,
+              "bm": 0,
+              "g": {
+                "p": 5,
+                "k": {
+                  "a": 0,
+                  "k": [
+                    0.832,
+                    0.275,
+                    0.89,
+                    0.086,
+
+                    0.86,
+                    0.275,
+                    0.89,
+                    0.086,
+
+                    0.887,
+                    0.275,
+                    0.89,
+                    0.086,
+
+                    0.944,
+                    0.275,
+                    0.89,
+                    0.086,
+
+                    1,
+                    0.275,
+                    0.89,
+                    0.086,
+
+                    0.65,
+                    0,
+
+                    0.785,
+                    0.5,
+
+                    0.84,
+                    1,
+
+                    0.862,
+                    1,
+
+                    0.885,
+                    1,
+
+                    0.896,
+                    0.5,
+
+                    0.908,
+                    0
+                  ]
+                }
+              },
+              "s": {
+                "a": 0,
+                "k": [
+                  457.898,
+                  -71.143
+                ]
+              },
+              "e": {
+                "a": 0,
+                "k": [
+                  -182.411,
+                  -47.941
+                ]
+              },
+              "t": 2,
+              "h": {
+                "a": 0,
+                "k": 0
+              },
+              "a": {
+                "a": 0,
+                "k": 97.679
+              },
+              "hd": false
+            },
+            {
+              "ty": "tr",
+              "p": {
+                "a": 0,
+                "k": [
+                  0,
+                  0
+                ]
+              },
+              "a": {
+                "a": 0,
+                "k": [
+                  0,
+                  0
+                ]
+              },
+              "s": {
+                "a": 0,
+                "k": [
+                  100,
+                  100
+                ]
+              },
+              "r": {
+                "a": 0,
+                "k": 0
+              },
+              "o": {
+                "a": 0,
+                "k": 100
+              },
+              "sk": {
+                "a": 0,
+                "k": 0
+              },
+              "sa": {
+                "a": 0,
+                "k": 0
+              }
+            }
+          ],
+          "bm": 0,
+          "hd": false
+        }
+      ],
+      "ip": 0,
+      "op": 180,
+      "st": -120,
+      "bm": 0
+    }
+  ]
+}
\ No newline at end of file