1 /*
2 * Copyright (C) 2008 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5 * in compliance with the License. You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software distributed under the License
10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11 * or implied. See the License for the specific language governing permissions and limitations under
12 * the License.
13 */
14
15 package com.google.common.escape;
16
17 import static com.google.common.base.Preconditions.checkNotNull;
18
19 import com.google.common.annotations.Beta;
20 import com.google.common.annotations.GwtCompatible;
21 import javax.annotation.CheckForNull;
22
23 /**
24 * An {@link Escaper} that converts literal text into a format safe for inclusion in a particular
25 * context (such as an XML document). Typically (but not always), the inverse process of
26 * "unescaping" the text is performed automatically by the relevant parser.
27 *
28 * <p>For example, an XML escaper would convert the literal string {@code "Foo<Bar>"} into {@code
29 * "Foo<Bar>"} to prevent {@code "<Bar>"} from being confused with an XML tag. When the
30 * resulting XML document is parsed, the parser API will return this text as the original literal
31 * string {@code "Foo<Bar>"}.
32 *
33 * <p><b>Note:</b> This class is similar to {@link CharEscaper} but with one very important
34 * difference. A CharEscaper can only process Java <a
35 * href="http://en.wikipedia.org/wiki/UTF-16">UTF16</a> characters in isolation and may not cope
36 * when it encounters surrogate pairs. This class facilitates the correct escaping of all Unicode
37 * characters.
38 *
39 * <p>As there are important reasons, including potential security issues, to handle Unicode
40 * correctly if you are considering implementing a new escaper you should favor using UnicodeEscaper
41 * wherever possible.
42 *
43 * <p>A {@code UnicodeEscaper} instance is required to be stateless, and safe when used concurrently
44 * by multiple threads.
45 *
46 * <p>Popular escapers are defined as constants in classes like {@link
47 * com.google.common.html.HtmlEscapers} and {@link com.google.common.xml.XmlEscapers}. To create
48 * your own escapers extend this class and implement the {@link #escape(int)} method.
49 *
50 * @author David Beaumont
51 * @since 15.0
52 */
53 @Beta
54 @GwtCompatible
55 @ElementTypesAreNonnullByDefault
56 public abstract class UnicodeEscaper extends Escaper {
57 /** The amount of padding (chars) to use when growing the escape buffer. */
58 private static final int DEST_PAD = 32;
59
60 /** Constructor for use by subclasses. */
61 protected UnicodeEscaper() {}
62
63 /**
64 * Returns the escaped form of the given Unicode code point, or {@code null} if this code point
65 * does not need to be escaped. When called as part of an escaping operation, the given code point
66 * is guaranteed to be in the range {@code 0 <= cp <= Character#MAX_CODE_POINT}.
67 *
68 * <p>If an empty array is returned, this effectively strips the input character from the
69 * resulting text.
70 *
71 * <p>If the character does not need to be escaped, this method should return {@code null}, rather
72 * than an array containing the character representation of the code point. This enables the
73 * escaping algorithm to perform more efficiently.
74 *
75 * <p>If the implementation of this method cannot correctly handle a particular code point then it
76 * should either throw an appropriate runtime exception or return a suitable replacement
77 * character. It must never silently discard invalid input as this may constitute a security risk.
78 *
79 * @param cp the Unicode code point to escape if necessary
80 * @return the replacement characters, or {@code null} if no escaping was needed
81 */
82 @CheckForNull
83 protected abstract char[] escape(int cp);
84
85 /**
86 * Returns the escaped form of a given literal string.
87 *
88 * <p>If you are escaping input in arbitrary successive chunks, then it is not generally safe to
89 * use this method. If an input string ends with an unmatched high surrogate character, then this
90 * method will throw {@link IllegalArgumentException}. You should ensure your input is valid <a
91 * href="http://en.wikipedia.org/wiki/UTF-16">UTF-16</a> before calling this method.
92 *
93 * <p><b>Note:</b> When implementing an escaper it is a good idea to override this method for
94 * efficiency by inlining the implementation of {@link #nextEscapeIndex(CharSequence, int, int)}
95 * directly. Doing this for {@link com.google.common.net.PercentEscaper} more than doubled the
96 * performance for unescaped strings (as measured by {@code CharEscapersBenchmark}).
97 *
98 * @param string the literal string to be escaped
99 * @return the escaped form of {@code string}
100 * @throws NullPointerException if {@code string} is null
101 * @throws IllegalArgumentException if invalid surrogate characters are encountered
102 */
103 @Override
104 public String escape(String string) {
105 checkNotNull(string);
106 int end = string.length();
107 int index = nextEscapeIndex(string, 0, end);
108 return index == end ? string : escapeSlow(string, index);
109 }
110
111 /**
112 * Scans a sub-sequence of characters from a given {@link CharSequence}, returning the index of
113 * the next character that requires escaping.
114 *
115 * <p><b>Note:</b> When implementing an escaper, it is a good idea to override this method for
116 * efficiency. The base class implementation determines successive Unicode code points and invokes
117 * {@link #escape(int)} for each of them. If the semantics of your escaper are such that code
118 * points in the supplementary range are either all escaped or all unescaped, this method can be
119 * implemented more efficiently using {@link CharSequence#charAt(int)}.
120 *
121 * <p>Note however that if your escaper does not escape characters in the supplementary range, you
122 * should either continue to validate the correctness of any surrogate characters encountered or
123 * provide a clear warning to users that your escaper does not validate its input.
124 *
125 * <p>See {@link com.google.common.net.PercentEscaper} for an example.
126 *
127 * @param csq a sequence of characters
128 * @param start the index of the first character to be scanned
129 * @param end the index immediately after the last character to be scanned
130 * @throws IllegalArgumentException if the scanned sub-sequence of {@code csq} contains invalid
131 * surrogate pairs
132 */
133 protected int nextEscapeIndex(CharSequence csq, int start, int end) {
134 int index = start;
135 while (index < end) {
136 int cp = codePointAt(csq, index, end);
137 if (cp < 0 || escape(cp) != null) {
138 break;
139 }
140 index += Character.isSupplementaryCodePoint(cp) ? 2 : 1;
141 }
142 return index;
143 }
144
145 /**
146 * Returns the escaped form of a given literal string, starting at the given index. This method is
147 * called by the {@link #escape(String)} method when it discovers that escaping is required. It is
148 * protected to allow subclasses to override the fastpath escaping function to inline their
149 * escaping test. See {@link CharEscaperBuilder} for an example usage.
150 *
151 * <p>This method is not reentrant and may only be invoked by the top level {@link
152 * #escape(String)} method.
153 *
154 * @param s the literal string to be escaped
155 * @param index the index to start escaping from
156 * @return the escaped form of {@code string}
157 * @throws NullPointerException if {@code string} is null
158 * @throws IllegalArgumentException if invalid surrogate characters are encountered
159 */
160 protected final String escapeSlow(String s, int index) {
161 int end = s.length();
162
163 // Get a destination buffer and setup some loop variables.
164 char[] dest = Platform.charBufferFromThreadLocal();
165 int destIndex = 0;
166 int unescapedChunkStart = 0;
167
168 while (index < end) {
169 int cp = codePointAt(s, index, end);
170 if (cp < 0) {
171 throw new IllegalArgumentException("Trailing high surrogate at end of input");
172 }
173 // It is possible for this to return null because nextEscapeIndex() may
174 // (for performance reasons) yield some false positives but it must never
175 // give false negatives.
176 char[] escaped = escape(cp);
177 int nextIndex = index + (Character.isSupplementaryCodePoint(cp) ? 2 : 1);
178 if (escaped != null) {
179 int charsSkipped = index - unescapedChunkStart;
180
181 // This is the size needed to add the replacement, not the full
182 // size needed by the string. We only regrow when we absolutely must.
183 int sizeNeeded = destIndex + charsSkipped + escaped.length;
184 if (dest.length < sizeNeeded) {
185 int destLength = sizeNeeded + (end - index) + DEST_PAD;
186 dest = growBuffer(dest, destIndex, destLength);
187 }
188 // If we have skipped any characters, we need to copy them now.
189 if (charsSkipped > 0) {
190 s.getChars(unescapedChunkStart, index, dest, destIndex);
191 destIndex += charsSkipped;
192 }
193 if (escaped.length > 0) {
194 System.arraycopy(escaped, 0, dest, destIndex, escaped.length);
195 destIndex += escaped.length;
196 }
197 // If we dealt with an escaped character, reset the unescaped range.
198 unescapedChunkStart = nextIndex;
199 }
200 index = nextEscapeIndex(s, nextIndex, end);
201 }
202
203 // Process trailing unescaped characters - no need to account for escaped
204 // length or padding the allocation.
205 int charsSkipped = end - unescapedChunkStart;
206 if (charsSkipped > 0) {
207 int endIndex = destIndex + charsSkipped;
208 if (dest.length < endIndex) {
209 dest = growBuffer(dest, destIndex, endIndex);
210 }
211 s.getChars(unescapedChunkStart, end, dest, destIndex);
212 destIndex = endIndex;
213 }
214 return new String(dest, 0, destIndex);
215 }
216
217 /**
218 * Returns the Unicode code point of the character at the given index.
219 *
220 * <p>Unlike {@link Character#codePointAt(CharSequence, int)} or {@link String#codePointAt(int)}
221 * this method will never fail silently when encountering an invalid surrogate pair.
222 *
223 * <p>The behaviour of this method is as follows:
224 *
225 * <ol>
226 * <li>If {@code index >= end}, {@link IndexOutOfBoundsException} is thrown.
227 * <li><b>If the character at the specified index is not a surrogate, it is returned.</b>
228 * <li>If the first character was a high surrogate value, then an attempt is made to read the
229 * next character.
230 * <ol>
231 * <li><b>If the end of the sequence was reached, the negated value of the trailing high
232 * surrogate is returned.</b>
233 * <li><b>If the next character was a valid low surrogate, the code point value of the
234 * high/low surrogate pair is returned.</b>
235 * <li>If the next character was not a low surrogate value, then {@link
236 * IllegalArgumentException} is thrown.
237 * </ol>
238 * <li>If the first character was a low surrogate value, {@link IllegalArgumentException} is
239 * thrown.
240 * </ol>
241 *
242 * @param seq the sequence of characters from which to decode the code point
243 * @param index the index of the first character to decode
244 * @param end the index beyond the last valid character to decode
245 * @return the Unicode code point for the given index or the negated value of the trailing high
246 * surrogate character at the end of the sequence
247 */
248 protected static int codePointAt(CharSequence seq, int index, int end) {
249 checkNotNull(seq);
250 if (index < end) {
251 char c1 = seq.charAt(index++);
252 if (c1 < Character.MIN_HIGH_SURROGATE || c1 > Character.MAX_LOW_SURROGATE) {
253 // Fast path (first test is probably all we need to do)
254 return c1;
255 } else if (c1 <= Character.MAX_HIGH_SURROGATE) {
256 // If the high surrogate was the last character, return its inverse
257 if (index == end) {
258 return -c1;
259 }
260 // Otherwise look for the low surrogate following it
261 char c2 = seq.charAt(index);
262 if (Character.isLowSurrogate(c2)) {
263 return Character.toCodePoint(c1, c2);
264 }
265 throw new IllegalArgumentException(
266 "Expected low surrogate but got char '"
267 + c2
268 + "' with value "
269 + (int) c2
270 + " at index "
271 + index
272 + " in '"
273 + seq
274 + "'");
275 } else {
276 throw new IllegalArgumentException(
277 "Unexpected low surrogate character '"
278 + c1
279 + "' with value "
280 + (int) c1
281 + " at index "
282 + (index - 1)
283 + " in '"
284 + seq
285 + "'");
286 }
287 }
288 throw new IndexOutOfBoundsException("Index exceeds specified range");
289 }
290
291 /**
292 * Helper method to grow the character buffer as needed, this only happens once in a while so it's
293 * ok if it's in a method call. If the index passed in is 0 then no copying will be done.
294 */
295 private static char[] growBuffer(char[] dest, int index, int size) {
296 if (size < 0) { // overflow - should be OutOfMemoryError but GWT/j2cl don't support it
297 throw new AssertionError("Cannot increase internal buffer any further");
298 }
299 char[] copy = new char[size];
300 if (index > 0) {
301 System.arraycopy(dest, 0, copy, 0, index);
302 }
303 return copy;
304 }
305 }