001/*
002 * Copyright (C) 2008 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
005 * in compliance with the License. You may obtain a copy of the License at
006 *
007 * http://www.apache.org/licenses/LICENSE-2.0
008 *
009 * Unless required by applicable law or agreed to in writing, software distributed under the License
010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
011 * or implied. See the License for the specific language governing permissions and limitations under
012 * the License.
013 */
014
015package com.google.common.escape;
016
017import static com.google.common.base.Preconditions.checkNotNull;
018
019import com.google.common.annotations.GwtCompatible;
020import javax.annotation.CheckForNull;
021
022/**
023 * An {@link Escaper} that converts literal text into a format safe for inclusion in a particular
024 * context (such as an XML document). Typically (but not always), the inverse process of
025 * "unescaping" the text is performed automatically by the relevant parser.
026 *
027 * <p>For example, an XML escaper would convert the literal string {@code "Foo<Bar>"} into {@code
028 * "Foo&lt;Bar&gt;"} to prevent {@code "<Bar>"} from being confused with an XML tag. When the
029 * resulting XML document is parsed, the parser API will return this text as the original literal
030 * string {@code "Foo<Bar>"}.
031 *
032 * <p><b>Note:</b> This class is similar to {@link CharEscaper} but with one very important
033 * difference. A CharEscaper can only process Java <a
034 * href="http://en.wikipedia.org/wiki/UTF-16">UTF16</a> characters in isolation and may not cope
035 * when it encounters surrogate pairs. This class facilitates the correct escaping of all Unicode
036 * characters.
037 *
038 * <p>As there are important reasons, including potential security issues, to handle Unicode
039 * correctly if you are considering implementing a new escaper you should favor using UnicodeEscaper
040 * wherever possible.
041 *
042 * <p>A {@code UnicodeEscaper} instance is required to be stateless, and safe when used concurrently
043 * by multiple threads.
044 *
045 * <p>Popular escapers are defined as constants in classes like {@link
046 * com.google.common.html.HtmlEscapers} and {@link com.google.common.xml.XmlEscapers}. To create
047 * your own escapers extend this class and implement the {@link #escape(int)} method.
048 *
049 * @author David Beaumont
050 * @since 15.0
051 */
052@GwtCompatible
053@ElementTypesAreNonnullByDefault
054public abstract class UnicodeEscaper extends Escaper {
055  /** The amount of padding (chars) to use when growing the escape buffer. */
056  private static final int DEST_PAD = 32;
057
058  /** Constructor for use by subclasses. */
059  protected UnicodeEscaper() {}
060
061  /**
062   * Returns the escaped form of the given Unicode code point, or {@code null} if this code point
063   * does not need to be escaped. When called as part of an escaping operation, the given code point
064   * is guaranteed to be in the range {@code 0 <= cp <= Character#MAX_CODE_POINT}.
065   *
066   * <p>If an empty array is returned, this effectively strips the input character from the
067   * resulting text.
068   *
069   * <p>If the character does not need to be escaped, this method should return {@code null}, rather
070   * than an array containing the character representation of the code point. This enables the
071   * escaping algorithm to perform more efficiently.
072   *
073   * <p>If the implementation of this method cannot correctly handle a particular code point then it
074   * should either throw an appropriate runtime exception or return a suitable replacement
075   * character. It must never silently discard invalid input as this may constitute a security risk.
076   *
077   * @param cp the Unicode code point to escape if necessary
078   * @return the replacement characters, or {@code null} if no escaping was needed
079   */
080  @CheckForNull
081  protected abstract char[] escape(int cp);
082
083  /**
084   * Returns the escaped form of a given literal string.
085   *
086   * <p>If you are escaping input in arbitrary successive chunks, then it is not generally safe to
087   * use this method. If an input string ends with an unmatched high surrogate character, then this
088   * method will throw {@link IllegalArgumentException}. You should ensure your input is valid <a
089   * href="http://en.wikipedia.org/wiki/UTF-16">UTF-16</a> before calling this method.
090   *
091   * <p><b>Note:</b> When implementing an escaper it is a good idea to override this method for
092   * efficiency by inlining the implementation of {@link #nextEscapeIndex(CharSequence, int, int)}
093   * directly. Doing this for {@link com.google.common.net.PercentEscaper} more than doubled the
094   * performance for unescaped strings (as measured by {@code CharEscapersBenchmark}).
095   *
096   * @param string the literal string to be escaped
097   * @return the escaped form of {@code string}
098   * @throws NullPointerException if {@code string} is null
099   * @throws IllegalArgumentException if invalid surrogate characters are encountered
100   */
101  @Override
102  public String escape(String string) {
103    checkNotNull(string);
104    int end = string.length();
105    int index = nextEscapeIndex(string, 0, end);
106    return index == end ? string : escapeSlow(string, index);
107  }
108
109  /**
110   * Scans a sub-sequence of characters from a given {@link CharSequence}, returning the index of
111   * the next character that requires escaping.
112   *
113   * <p><b>Note:</b> When implementing an escaper, it is a good idea to override this method for
114   * efficiency. The base class implementation determines successive Unicode code points and invokes
115   * {@link #escape(int)} for each of them. If the semantics of your escaper are such that code
116   * points in the supplementary range are either all escaped or all unescaped, this method can be
117   * implemented more efficiently using {@link CharSequence#charAt(int)}.
118   *
119   * <p>Note however that if your escaper does not escape characters in the supplementary range, you
120   * should either continue to validate the correctness of any surrogate characters encountered or
121   * provide a clear warning to users that your escaper does not validate its input.
122   *
123   * <p>See {@link com.google.common.net.PercentEscaper} for an example.
124   *
125   * @param csq a sequence of characters
126   * @param start the index of the first character to be scanned
127   * @param end the index immediately after the last character to be scanned
128   * @throws IllegalArgumentException if the scanned sub-sequence of {@code csq} contains invalid
129   *     surrogate pairs
130   */
131  protected int nextEscapeIndex(CharSequence csq, int start, int end) {
132    int index = start;
133    while (index < end) {
134      int cp = codePointAt(csq, index, end);
135      if (cp < 0 || escape(cp) != null) {
136        break;
137      }
138      index += Character.isSupplementaryCodePoint(cp) ? 2 : 1;
139    }
140    return index;
141  }
142
143  /**
144   * Returns the escaped form of a given literal string, starting at the given index. This method is
145   * called by the {@link #escape(String)} method when it discovers that escaping is required. It is
146   * protected to allow subclasses to override the fastpath escaping function to inline their
147   * escaping test. See {@link CharEscaperBuilder} for an example usage.
148   *
149   * <p>This method is not reentrant and may only be invoked by the top level {@link
150   * #escape(String)} method.
151   *
152   * @param s the literal string to be escaped
153   * @param index the index to start escaping from
154   * @return the escaped form of {@code string}
155   * @throws NullPointerException if {@code string} is null
156   * @throws IllegalArgumentException if invalid surrogate characters are encountered
157   */
158  protected final String escapeSlow(String s, int index) {
159    int end = s.length();
160
161    // Get a destination buffer and setup some loop variables.
162    char[] dest = Platform.charBufferFromThreadLocal();
163    int destIndex = 0;
164    int unescapedChunkStart = 0;
165
166    while (index < end) {
167      int cp = codePointAt(s, index, end);
168      if (cp < 0) {
169        throw new IllegalArgumentException("Trailing high surrogate at end of input");
170      }
171      // It is possible for this to return null because nextEscapeIndex() may
172      // (for performance reasons) yield some false positives but it must never
173      // give false negatives.
174      char[] escaped = escape(cp);
175      int nextIndex = index + (Character.isSupplementaryCodePoint(cp) ? 2 : 1);
176      if (escaped != null) {
177        int charsSkipped = index - unescapedChunkStart;
178
179        // This is the size needed to add the replacement, not the full
180        // size needed by the string. We only regrow when we absolutely must.
181        int sizeNeeded = destIndex + charsSkipped + escaped.length;
182        if (dest.length < sizeNeeded) {
183          int destLength = sizeNeeded + (end - index) + DEST_PAD;
184          dest = growBuffer(dest, destIndex, destLength);
185        }
186        // If we have skipped any characters, we need to copy them now.
187        if (charsSkipped > 0) {
188          s.getChars(unescapedChunkStart, index, dest, destIndex);
189          destIndex += charsSkipped;
190        }
191        if (escaped.length > 0) {
192          System.arraycopy(escaped, 0, dest, destIndex, escaped.length);
193          destIndex += escaped.length;
194        }
195        // If we dealt with an escaped character, reset the unescaped range.
196        unescapedChunkStart = nextIndex;
197      }
198      index = nextEscapeIndex(s, nextIndex, end);
199    }
200
201    // Process trailing unescaped characters - no need to account for escaped
202    // length or padding the allocation.
203    int charsSkipped = end - unescapedChunkStart;
204    if (charsSkipped > 0) {
205      int endIndex = destIndex + charsSkipped;
206      if (dest.length < endIndex) {
207        dest = growBuffer(dest, destIndex, endIndex);
208      }
209      s.getChars(unescapedChunkStart, end, dest, destIndex);
210      destIndex = endIndex;
211    }
212    return new String(dest, 0, destIndex);
213  }
214
215  /**
216   * Returns the Unicode code point of the character at the given index.
217   *
218   * <p>Unlike {@link Character#codePointAt(CharSequence, int)} or {@link String#codePointAt(int)}
219   * this method will never fail silently when encountering an invalid surrogate pair.
220   *
221   * <p>The behaviour of this method is as follows:
222   *
223   * <ol>
224   *   <li>If {@code index >= end}, {@link IndexOutOfBoundsException} is thrown.
225   *   <li><b>If the character at the specified index is not a surrogate, it is returned.</b>
226   *   <li>If the first character was a high surrogate value, then an attempt is made to read the
227   *       next character.
228   *       <ol>
229   *         <li><b>If the end of the sequence was reached, the negated value of the trailing high
230   *             surrogate is returned.</b>
231   *         <li><b>If the next character was a valid low surrogate, the code point value of the
232   *             high/low surrogate pair is returned.</b>
233   *         <li>If the next character was not a low surrogate value, then {@link
234   *             IllegalArgumentException} is thrown.
235   *       </ol>
236   *   <li>If the first character was a low surrogate value, {@link IllegalArgumentException} is
237   *       thrown.
238   * </ol>
239   *
240   * @param seq the sequence of characters from which to decode the code point
241   * @param index the index of the first character to decode
242   * @param end the index beyond the last valid character to decode
243   * @return the Unicode code point for the given index or the negated value of the trailing high
244   *     surrogate character at the end of the sequence
245   */
246  protected static int codePointAt(CharSequence seq, int index, int end) {
247    checkNotNull(seq);
248    if (index < end) {
249      char c1 = seq.charAt(index++);
250      if (c1 < Character.MIN_HIGH_SURROGATE || c1 > Character.MAX_LOW_SURROGATE) {
251        // Fast path (first test is probably all we need to do)
252        return c1;
253      } else if (c1 <= Character.MAX_HIGH_SURROGATE) {
254        // If the high surrogate was the last character, return its inverse
255        if (index == end) {
256          return -c1;
257        }
258        // Otherwise look for the low surrogate following it
259        char c2 = seq.charAt(index);
260        if (Character.isLowSurrogate(c2)) {
261          return Character.toCodePoint(c1, c2);
262        }
263        throw new IllegalArgumentException(
264            "Expected low surrogate but got char '"
265                + c2
266                + "' with value "
267                + (int) c2
268                + " at index "
269                + index
270                + " in '"
271                + seq
272                + "'");
273      } else {
274        throw new IllegalArgumentException(
275            "Unexpected low surrogate character '"
276                + c1
277                + "' with value "
278                + (int) c1
279                + " at index "
280                + (index - 1)
281                + " in '"
282                + seq
283                + "'");
284      }
285    }
286    throw new IndexOutOfBoundsException("Index exceeds specified range");
287  }
288
289  /**
290   * Helper method to grow the character buffer as needed, this only happens once in a while so it's
291   * ok if it's in a method call. If the index passed in is 0 then no copying will be done.
292   */
293  private static char[] growBuffer(char[] dest, int index, int size) {
294    if (size < 0) { // overflow - should be OutOfMemoryError but GWT/j2cl don't support it
295      throw new AssertionError("Cannot increase internal buffer any further");
296    }
297    char[] copy = new char[size];
298    if (index > 0) {
299      System.arraycopy(dest, 0, copy, 0, index);
300    }
301    return copy;
302  }
303}