From 10e531756b972162eed402c44d0244f7f6b85131 Mon Sep 17 00:00:00 2001
From: Joakim Erdfelt <joakim.erdfelt@gmail.com>
Date: Thu, 18 Feb 2021 07:14:38 -0600
Subject: [PATCH] Merge pull request from GHSA-m394-8rww-3jr7

Use comparator based sort
Signed-off-by: Joakim Erdfelt <joakim.erdfelt@gmail.com>
Signed-off-by: gregw <gregw@webtide.com>

Co-authored-by: gregw <gregw@webtide.com>
---
 .../eclipse/jetty/http/QuotedQualityCSV.java  | 117 +++++++++++++-----
 1 file changed, 86 insertions(+), 31 deletions(-)

diff --git a/jetty-http/src/main/java/org/eclipse/jetty/http/QuotedQualityCSV.java b/jetty-http/src/main/java/org/eclipse/jetty/http/QuotedQualityCSV.java
index d148d9e..67f9981 100644
--- a/jetty-http/src/main/java/org/eclipse/jetty/http/QuotedQualityCSV.java
+++ b/jetty-http/src/main/java/org/eclipse/jetty/http/QuotedQualityCSV.java
@@ -21,12 +21,12 @@ package org.eclipse.jetty.http;
 import java.util.ArrayList;
 import java.util.Iterator;
 import java.util.List;
+import java.util.Objects;
 import java.util.function.ToIntFunction;
+import java.util.stream.Collectors;
 
 import org.eclipse.jetty.util.log.Log;
 
-import static java.lang.Integer.MIN_VALUE;
-
 /* ------------------------------------------------------------ */
 
 /**
@@ -57,7 +57,8 @@ public class QuotedQualityCSV extends QuotedCSV implements Iterable<String>
         return 3;
     };
 
-    private final List<Double> _quality = new ArrayList<>();
+    private final List<QualityValue> _qualities = new ArrayList<>();
+    private QualityValue _lastQuality;
     private boolean _sorted = false;
     private final ToIntFunction<String> _secondaryOrdering;
 
@@ -68,7 +69,7 @@ public class QuotedQualityCSV extends QuotedCSV implements Iterable<String>
      */
     public QuotedQualityCSV()
     {
-        this((ToIntFunction)null);
+        this((ToIntFunction<String>)null);
     }
 
     /* ------------------------------------------------------------ */
@@ -89,7 +90,7 @@ public class QuotedQualityCSV extends QuotedCSV implements Iterable<String>
             if ("*".equals(s))
                 return preferredOrder.length;
 
-            return MIN_VALUE;
+            return 0;
         });
     }
 
@@ -98,27 +99,43 @@ public class QuotedQualityCSV extends QuotedCSV implements Iterable<String>
     /**
      * Orders values with equal quality with the given function.
      *
-     * @param secondaryOrdering Function to apply an ordering other than specified by quality
+     * @param secondaryOrdering Function to apply an ordering other than specified by quality, highest values are sorted first.
      */
     public QuotedQualityCSV(ToIntFunction<String> secondaryOrdering)
     {
         this._secondaryOrdering = secondaryOrdering == null ? s -> 0 : secondaryOrdering;
     }
 
+    @Override
+    protected void parsedValueAndParams(StringBuffer buffer)
+    {
+        super.parsedValueAndParams(buffer);
+
+	// Collect full value with parameters
+	_lastQuality = new QualityValue(_lastQuality._quality, buffer.toString(), _lastQuality._index);
+	 _qualities.set(_lastQuality._index, _lastQuality);
+    }
+
     /* ------------------------------------------------------------ */
     @Override
     protected void parsedValue(StringBuffer buffer)
     {
         super.parsedValue(buffer);
 
+	_sorted = false;
+
+        // This is the just the value, without parameters.
         // Assume a quality of ONE
-        _quality.add(1.0D);
+	_lastQuality = new QualityValue(1.0D, buffer.toString(), _qualities.size());
+	_qualities.add(_lastQuality);
     }
 
     /* ------------------------------------------------------------ */
     @Override
     protected void parsedParam(StringBuffer buffer, int valueLength, int paramName, int paramValue)
     {
+	_sorted = false;
+
         if (paramName < 0)
         {
             if (buffer.charAt(buffer.length() - 1) == ';')
@@ -128,7 +145,7 @@ public class QuotedQualityCSV extends QuotedCSV implements Iterable<String>
                 buffer.charAt(paramName) == 'q' && paramValue > paramName &&
                 buffer.length() >= paramName && buffer.charAt(paramName + 1) == '=')
         {
-            Double q;
+            double q;
             try
             {
                 q = (_keepQuotes && buffer.charAt(paramValue) == '"')
@@ -143,8 +160,10 @@ public class QuotedQualityCSV extends QuotedCSV implements Iterable<String>
             buffer.setLength(Math.max(0, paramName - 1));
 
             if (q != 1.0D)
-                // replace assumed quality
-                _quality.set(_quality.size() - 1, q);
+            {
+                _lastQuality = new QualityValue(q, buffer.toString(), _lastQuality._index);
+                _qualities.set(_lastQuality._index, _lastQuality);
+            }
         }
     }
 
@@ -166,38 +185,74 @@ public class QuotedQualityCSV extends QuotedCSV implements Iterable<String>
 
     protected void sort()
     {
+	_values.clear();
+	_qualities.stream()
+		.filter((qv) -> qv._quality != 0.0D)
+		.sorted()
+		.map(QualityValue::getValue)
+		.collect(Collectors.toCollection(() -> _values));
         _sorted = true;
+    }
 
-        Double last = 0.0D;
-        int lastSecondaryOrder = Integer.MIN_VALUE;
+    private class QualityValue implements Comparable<QualityValue>
+    {
+        private final double _quality;
+	private final String _value;
+	private final int _index;
 
-        for (int i = _values.size(); i-- > 0; )
+	private QualityValue(double quality, String value, int index)
         {
-            String v = _values.get(i);
-            Double q = _quality.get(i);
+	    _quality = quality;
+            _value = value;
+            _index = index;
+	}
+
+	@Override
+	public int hashCode()
+	{
+	    return Double.hashCode(_quality) ^ Objects.hash(_value, _index);
+	}
+
+	@Override
+	public boolean equals(Object obj)
+	{
+	    if (!(obj instanceof QualityValue))
+		    return false;
+	    QualityValue qv = (QualityValue)obj;
+	    return _quality == qv._quality && Objects.equals(_value, qv._value) && Objects.equals(_index, qv._index);
+	}
+
+	private String getValue()
+	{
+	    return _value;
+	}
 
-            int compare = last.compareTo(q);
-            if (compare > 0 || (compare == 0 && _secondaryOrdering.applyAsInt(v) < lastSecondaryOrder))
+        @Override
+	public int compareTo(QualityValue o)
+	{
+	    // sort highest quality first
+	    int compare = Double.compare(o._quality, _quality);
+	    if (compare == 0)
             {
-                _values.set(i, _values.get(i + 1));
-                _values.set(i + 1, v);
-                _quality.set(i, _quality.get(i + 1));
-                _quality.set(i + 1, q);
-                last = 0.0D;
-                lastSecondaryOrder = 0;
-                i = _values.size();
-                continue;
+		// then sort secondary order highest first
+		compare = Integer.compare(_secondaryOrdering.applyAsInt(o._value), _secondaryOrdering.applyAsInt(_value));
+		if (compare == 0)
+		    // then sort index lowest first
+		    compare = -Integer.compare(o._index, _index);
             }
 
-            last = q;
-            lastSecondaryOrder = _secondaryOrdering.applyAsInt(v);
+	    return compare;
         }
 
-        int last_element = _quality.size();
-        while (last_element > 0 && _quality.get(--last_element).equals(0.0D))
+	@Override
+	public String toString()
         {
-            _quality.remove(last_element);
-            _values.remove(last_element);
+            return String.format("%s@%x[%s,q=%f,i=%d]",
+                getClass().getSimpleName(),
+		hashCode(),
+		_value,
+		_quality,
+		_index);
         }
     }
 }
-- 
2.23.0

