1 /*
2 * JBoss, Home of Professional Open Source.
3 * Copyright 2014 Red Hat, Inc., and individual contributors
4 * as indicated by the @author tags.
5 *
6 * Licensed under the Apache License, Version 2.0 (the "License");
7 * you may not use this file except in compliance with the License.
8 * You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 */
18
19 package io.undertow.util;
20
21 import java.util.ArrayList;
22 import java.util.Collections;
23 import java.util.List;
24
25 /**
26 * Utility class for parsing headers that accept q values
27 *
28 * @author Stuart Douglas
29 */
30 public class QValueParser {
31
32 private QValueParser() {
33
34 }
35
36 /**
37 * Parses a set of headers that take q values to determine the most preferred one.
38 *
39 * It returns the result in the form of a sorted list of list, with every element in
40 * the list having the same q value. This means the highest priority items are at the
41 * front of the list. The container should use its own internal preferred ordering
42 * to determinately pick the correct item to use
43 *
44 * @param headers The headers
45 * @return The q value results
46 */
47 public static List<List<QValueResult>> parse(List<String> headers) {
48 final List<QValueResult> found = new ArrayList<>();
49 QValueResult current = null;
50 for (final String header : headers) {
51 final int l = header.length();
52 //we do not use a string builder
53 //we just keep track of where the current string starts and call substring()
54 int stringStart = 0;
55 for (int i = 0; i < l; ++i) {
56 char c = header.charAt(i);
57 switch (c) {
58 case ',': {
59 if (current != null &&
60 (i - stringStart > 2 && header.charAt(stringStart) == 'q' &&
61 header.charAt(stringStart + 1) == '=')) {
62 //if this is a valid qvalue
63 current.qvalue = header.substring(stringStart + 2, i);
64 current = null;
65 } else if (stringStart != i) {
66 current = handleNewEncoding(found, header, stringStart, i);
67 }
68 stringStart = i + 1;
69 break;
70 }
71 case ';': {
72 if (stringStart != i) {
73 current = handleNewEncoding(found, header, stringStart, i);
74 stringStart = i + 1;
75 }
76 break;
77 }
78 case ' ': {
79 if (stringStart != i) {
80 if (current != null &&
81 (i - stringStart > 2 && header.charAt(stringStart) == 'q' &&
82 header.charAt(stringStart + 1) == '=')) {
83 //if this is a valid qvalue
84 current.qvalue = header.substring(stringStart + 2, i);
85 } else {
86 current = handleNewEncoding(found, header, stringStart, i);
87 }
88 }
89 stringStart = i + 1;
90 }
91 }
92 }
93
94 if (stringStart != l) {
95 if (current != null &&
96 (l - stringStart > 2 && header.charAt(stringStart) == 'q' &&
97 header.charAt(stringStart + 1) == '=')) {
98 //if this is a valid qvalue
99 current.qvalue = header.substring(stringStart + 2, l);
100 } else {
101 current = handleNewEncoding(found, header, stringStart, l);
102 }
103 }
104 }
105 Collections.sort(found, Collections.reverseOrder());
106 String currentQValue = null;
107 List<List<QValueResult>> values = new ArrayList<>();
108 List<QValueResult> currentSet = null;
109
110 for(QValueResult val : found) {
111 if(!val.qvalue.equals(currentQValue)) {
112 currentQValue = val.qvalue;
113 currentSet = new ArrayList<>();
114 values.add(currentSet);
115 }
116 currentSet.add(val);
117 }
118 return values;
119 }
120
121 private static QValueResult handleNewEncoding(final List<QValueResult> found, final String header, final int stringStart, final int i) {
122 final QValueResult current = new QValueResult();
123 current.value = header.substring(stringStart, i);
124 found.add(current);
125 return current;
126 }
127
128 public static class QValueResult implements Comparable<QValueResult> {
129
130
131 /**
132 * The string value of the result
133 */
134 private String value;
135
136 /**
137 * we keep the qvalue as a string to avoid parsing the double.
138 * <p>
139 * This should give both performance and also possible security improvements
140 */
141 private String qvalue = "1";
142
143 public String getValue() {
144 return value;
145 }
146
147 public String getQvalue() {
148 return qvalue;
149 }
150
151 @Override
152 public boolean equals(Object o) {
153 if (this == o) return true;
154 if (!(o instanceof QValueResult)) return false;
155
156 QValueResult that = (QValueResult) o;
157
158 if (getValue() != null ? !getValue().equals(that.getValue()) : that.getValue() != null) return false;
159 return getQvalue() != null ? getQvalue().equals(that.getQvalue()) : that.getQvalue() == null;
160 }
161
162 @Override
163 public int hashCode() {
164 int result = getValue() != null ? getValue().hashCode() : 0;
165 result = 31 * result + (getQvalue() != null ? getQvalue().hashCode() : 0);
166 return result;
167 }
168
169 @Override
170 public int compareTo(final QValueResult other) {
171 //we compare the strings as if they were decimal values.
172 //we know they can only be
173
174 final String t = qvalue;
175 final String o = other.qvalue;
176 if (t == null && o == null) {
177 //neither of them has a q value
178 //we compare them via the server specified default precedence
179 //note that encoding is never null here, a * without a q value is meaningless
180 //and will be discarded before this
181 return 0;
182 }
183
184 if (o == null) {
185 return 1;
186 } else if (t == null) {
187 return -1;
188 }
189
190 final int tl = t.length();
191 final int ol = o.length();
192 //we only compare the first 5 characters as per spec
193 for (int i = 0; i < 5; ++i) {
194 if (tl == i || ol == i) {
195 return ol - tl; //longer one is higher
196 }
197 if (i == 1) continue; // this is just the decimal point
198 final int tc = t.charAt(i);
199 final int oc = o.charAt(i);
200
201 int res = tc - oc;
202 if (res != 0) {
203 return res;
204 }
205 }
206 return 0;
207 }
208
209
210 public boolean isQValueZero() {
211 //we ignore * without a qvalue
212 if (qvalue != null) {
213 int length = Math.min(5, qvalue.length());
214 //we need to find out if this is prohibiting identity
215 //encoding (q=0). Otherwise we just treat it as the identity encoding
216 boolean zero = true;
217 for (int j = 0; j < length; ++j) {
218 if (j == 1) continue;//decimal point
219 if (qvalue.charAt(j) != '0') {
220 zero = false;
221 break;
222 }
223 }
224 return zero;
225 }
226 return false;
227 }
228
229 }
230 }
231