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