View Javadoc

    1   /* Copyright (c) 2008 Google Inc.
    2    *
    3    * Licensed under the Apache License, Version 2.0 (the "License");
    4    * you may not use this file except in compliance with the License.
    5    * 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
    10   * distributed under the License is distributed on an "AS IS" BASIS,
    11   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12   * See the License for the specific language governing permissions and
    13   * limitations under the License.
    14   */
    15
    16  package org.yaml.snakeyaml.external.com.google.gdata.util.common.base;
    17
    18  import java.io.IOException;
    19
    20  /**
    21   * An {@link Escaper} that converts literal text into a format safe for
    22   * inclusion in a particular context (such as an XML document). Typically (but
    23   * not always), the inverse process of "unescaping" the text is performed
    24   * automatically by the relevant parser.
    25   *
    26   * <p>
    27   * For example, an XML escaper would convert the literal string
    28   * {@code "Foo<Bar>"} into {@code "Foo&lt;Bar&gt;"} to prevent {@code "<Bar>"}
    29   * from being confused with an XML tag. When the resulting XML document is
    30   * parsed, the parser API will return this text as the original literal string
    31   * {@code "Foo<Bar>"}.
    32   *
    33   * <p>
    34   * <b>Note:</b> This class is similar to {@link CharEscaper} but with one very
    35   * important difference. A CharEscaper can only process Java <a
    36   * href="http://en.wikipedia.org/wiki/UTF-16">UTF16</a> characters in isolation
    37   * and may not cope when it encounters surrogate pairs. This class facilitates
    38   * the correct escaping of all Unicode characters.
    39   *
    40   * <p>
    41   * As there are important reasons, including potential security issues, to
    42   * handle Unicode correctly if you are considering implementing a new escaper
    43   * you should favor using UnicodeEscaper wherever possible.
    44   *
    45   * <p>
    46   * A {@code UnicodeEscaper} instance is required to be stateless, and safe when
    47   * used concurrently by multiple threads.
    48   *
    49   * <p>
    50   * Several popular escapers are defined as constants in the class
    51   * {@link CharEscapers}. To create your own escapers extend this class and
    52   * implement the {@link #escape(int)} method.
    53   *
    54   *
    55   */
    56  public abstract class UnicodeEscaper implements Escaper {
    57      /** The amount of padding (chars) to use when growing the escape buffer. */
    58      private static final int DEST_PAD = 32;
    59
    60      /**
    61       * Returns the escaped form of the given Unicode code point, or {@code null}
    62       * if this code point does not need to be escaped. When called as part of an
    63       * escaping operation, the given code point is guaranteed to be in the range
    64       * {@code 0 <= cp <= Character#MAX_CODE_POINT}.
    65       *
    66       * <p>
    67       * If an empty array is returned, this effectively strips the input
    68       * character from the resulting text.
    69       *
    70       * <p>
    71       * If the character does not need to be escaped, this method should return
    72       * {@code null}, rather than an array containing the character
    73       * representation of the code point. This enables the escaping algorithm to
    74       * perform more efficiently.
    75       *
    76       * <p>
    77       * If the implementation of this method cannot correctly handle a particular
    78       * code point then it should either throw an appropriate runtime exception
    79       * or return a suitable replacement character. It must never silently
    80       * discard invalid input as this may constitute a security risk.
    81       *
    82       * @param cp
    83       *            the Unicode code point to escape if necessary
    84       * @return the replacement characters, or {@code null} if no escaping was
    85       *         needed
    86       */
    87      protected abstract char[] escape(int cp);
    88
    89      /**
    90       * Scans a sub-sequence of characters from a given {@link CharSequence},
    91       * returning the index of the next character that requires escaping.
    92       *
    93       * <p>
    94       * <b>Note:</b> When implementing an escaper, it is a good idea to override
    95       * this method for efficiency. The base class implementation determines
    96       * successive Unicode code points and invokes {@link #escape(int)} for each
    97       * of them. If the semantics of your escaper are such that code points in
    98       * the supplementary range are either all escaped or all unescaped, this
    99       * method can be implemented more efficiently using
    100      * {@link CharSequence#charAt(int)}.
    101      *
    102      * <p>
    103      * Note however that if your escaper does not escape characters in the
    104      * supplementary range, you should either continue to validate the
    105      * correctness of any surrogate characters encountered or provide a clear
    106      * warning to users that your escaper does not validate its input.
    107      *
    108      * <p>
    109      * See {@link PercentEscaper} for an example.
    110      *
    111      * @param csq
    112      *            a sequence of characters
    113      * @param start
    114      *            the index of the first character to be scanned
    115      * @param end
    116      *            the index immediately after the last character to be scanned
    117      * @throws IllegalArgumentException
    118      *             if the scanned sub-sequence of {@code csq} contains invalid
    119      *             surrogate pairs
    120      */
    121     protected int nextEscapeIndex(CharSequence csq, int start, int end) {
    122         int index = start;
    123         while (index < end) {
    124             int cp = codePointAt(csq, index, end);
    125             if (cp < 0 || escape(cp) != null) {
    126                 break;
    127             }
    128             index += Character.isSupplementaryCodePoint(cp) ? 2 : 1;
    129         }
    130         return index;
    131     }
    132
    133     /**
    134      * Returns the escaped form of a given literal string.
    135      *
    136      * <p>
    137      * If you are escaping input in arbitrary successive chunks, then it is not
    138      * generally safe to use this method. If an input string ends with an
    139      * unmatched high surrogate character, then this method will throw
    140      * {@link IllegalArgumentException}. You should either ensure your input is
    141      * valid <a href="http://en.wikipedia.org/wiki/UTF-16">UTF-16</a> before
    142      * calling this method or use an escaped {@link Appendable} (as returned by
    143      * {@link #escape(Appendable)}) which can cope with arbitrarily split input.
    144      *
    145      * <p>
    146      * <b>Note:</b> When implementing an escaper it is a good idea to override
    147      * this method for efficiency by inlining the implementation of
    148      * {@link #nextEscapeIndex(CharSequence, int, int)} directly. Doing this for
    149      * {@link PercentEscaper} more than doubled the performance for unescaped
    150      * strings (as measured by {@link CharEscapersBenchmark}).
    151      *
    152      * @param string
    153      *            the literal string to be escaped
    154      * @return the escaped form of {@code string}
    155      * @throws NullPointerException
    156      *             if {@code string} is null
    157      * @throws IllegalArgumentException
    158      *             if invalid surrogate characters are encountered
    159      */
    160     public String escape(String string) {
    161         int end = string.length();
    162         int index = nextEscapeIndex(string, 0, end);
    163         return index == end ? string : escapeSlow(string, index);
    164     }
    165
    166     /**
    167      * Returns the escaped form of a given literal string, starting at the given
    168      * index. This method is called by the {@link #escape(String)} method when
    169      * it discovers that escaping is required. It is protected to allow
    170      * subclasses to override the fastpath escaping function to inline their
    171      * escaping test. See {@link CharEscaperBuilder} for an example usage.
    172      *
    173      * <p>
    174      * This method is not reentrant and may only be invoked by the top level
    175      * {@link #escape(String)} method.
    176      *
    177      * @param s
    178      *            the literal string to be escaped
    179      * @param index
    180      *            the index to start escaping from
    181      * @return the escaped form of {@code string}
    182      * @throws NullPointerException
    183      *             if {@code string} is null
    184      * @throws IllegalArgumentException
    185      *             if invalid surrogate characters are encountered
    186      */
    187     protected final String escapeSlow(String s, int index) {
    188         int end = s.length();
    189
    190         // Get a destination buffer and setup some loop variables.
    191         char[] dest = DEST_TL.get();
    192         int destIndex = 0;
    193         int unescapedChunkStart = 0;
    194
    195         while (index < end) {
    196             int cp = codePointAt(s, index, end);
    197             if (cp < 0) {
    198                 throw new IllegalArgumentException("Trailing high surrogate at end of input");
    199             }
    200             char[] escaped = escape(cp);
    201             if (escaped != null) {
    202                 int charsSkipped = index - unescapedChunkStart;
    203
    204                 // This is the size needed to add the replacement, not the full
    205                 // size needed by the string. We only regrow when we absolutely
    206                 // must.
    207                 int sizeNeeded = destIndex + charsSkipped + escaped.length;
    208                 if (dest.length < sizeNeeded) {
    209                     int destLength = sizeNeeded + (end - index) + DEST_PAD;
    210                     dest = growBuffer(dest, destIndex, destLength);
    211                 }
    212                 // If we have skipped any characters, we need to copy them now.
    213                 if (charsSkipped > 0) {
    214                     s.getChars(unescapedChunkStart, index, dest, destIndex);
    215                     destIndex += charsSkipped;
    216                 }
    217                 if (escaped.length > 0) {
    218                     System.arraycopy(escaped, 0, dest, destIndex, escaped.length);
    219                     destIndex += escaped.length;
    220                 }
    221             }
    222             unescapedChunkStart = index + (Character.isSupplementaryCodePoint(cp) ? 2 : 1);
    223             index = nextEscapeIndex(s, unescapedChunkStart, end);
    224         }
    225
    226         // Process trailing unescaped characters - no need to account for
    227         // escaped
    228         // length or padding the allocation.
    229         int charsSkipped = end - unescapedChunkStart;
    230         if (charsSkipped > 0) {
    231             int endIndex = destIndex + charsSkipped;
    232             if (dest.length < endIndex) {
    233                 dest = growBuffer(dest, destIndex, endIndex);
    234             }
    235             s.getChars(unescapedChunkStart, end, dest, destIndex);
    236             destIndex = endIndex;
    237         }
    238         return new String(dest, 0, destIndex);
    239     }
    240
    241     /**
    242      * Returns an {@code Appendable} instance which automatically escapes all
    243      * text appended to it before passing the resulting text to an underlying
    244      * {@code Appendable}.
    245      *
    246      * <p>
    247      * Unlike {@link #escape(String)} it is permitted to append arbitrarily
    248      * split input to this Appendable, including input that is split over a
    249      * surrogate pair. In this case the pending high surrogate character will
    250      * not be processed until the corresponding low surrogate is appended. This
    251      * means that a trailing high surrogate character at the end of the input
    252      * cannot be detected and will be silently ignored. This is unavoidable
    253      * since the Appendable interface has no {@code close()} method, and it is
    254      * impossible to determine when the last characters have been appended.
    255      *
    256      * <p>
    257      * The methods of the returned object will propagate any exceptions thrown
    258      * by the underlying {@code Appendable}.
    259      *
    260      * <p>
    261      * For well formed <a href="http://en.wikipedia.org/wiki/UTF-16">UTF-16</a>
    262      * the escaping behavior is identical to that of {@link #escape(String)} and
    263      * the following code is equivalent to (but much slower than)
    264      * {@code escaper.escape(string)}:
    265      *
    266      * <pre>
    267      * {
    268      *     &#064;code
    269      *     StringBuilder sb = new StringBuilder();
    270      *     escaper.escape(sb).append(string);
    271      *     return sb.toString();
    272      * }
    273      * </pre>
    274      *
    275      * @param out
    276      *            the underlying {@code Appendable} to append escaped output to
    277      * @return an {@code Appendable} which passes text to {@code out} after
    278      *         escaping it
    279      * @throws NullPointerException
    280      *             if {@code out} is null
    281      * @throws IllegalArgumentException
    282      *             if invalid surrogate characters are encountered
    283      *
    284      */
    285     public Appendable escape(final Appendable out) {
    286         assert out != null;
    287
    288         return new Appendable() {
    289             int pendingHighSurrogate = -1;
    290             char[] decodedChars = new char[2];
    291
    292             public Appendable append(CharSequence csq) throws IOException {
    293                 return append(csq, 0, csq.length());
    294             }
    295
    296             public Appendable append(CharSequence csq, int start, int end) throws IOException {
    297                 int index = start;
    298                 if (index < end) {
    299                     // This is a little subtle: index must never reference the
    300                     // middle of a
    301                     // surrogate pair but unescapedChunkStart can. The first
    302                     // time we enter
    303                     // the loop below it is possible that index !=
    304                     // unescapedChunkStart.
    305                     int unescapedChunkStart = index;
    306                     if (pendingHighSurrogate != -1) {
    307                         // Our last append operation ended halfway through a
    308                         // surrogate pair
    309                         // so we have to do some extra work first.
    310                         char c = csq.charAt(index++);
    311                         if (!Character.isLowSurrogate(c)) {
    312                             throw new IllegalArgumentException(
    313                                     "Expected low surrogate character but got " + c);
    314                         }
    315                         char[] escaped = escape(Character.toCodePoint((char) pendingHighSurrogate,
    316                                 c));
    317                         if (escaped != null) {
    318                             // Emit the escaped character and adjust
    319                             // unescapedChunkStart to
    320                             // skip the low surrogate we have consumed.
    321                             outputChars(escaped, escaped.length);
    322                             unescapedChunkStart += 1;
    323                         } else {
    324                             // Emit pending high surrogate (unescaped) but do
    325                             // not modify
    326                             // unescapedChunkStart as we must still emit the low
    327                             // surrogate.
    328                             out.append((char) pendingHighSurrogate);
    329                         }
    330                         pendingHighSurrogate = -1;
    331                     }
    332                     while (true) {
    333                         // Find and append the next subsequence of unescaped
    334                         // characters.
    335                         index = nextEscapeIndex(csq, index, end);
    336                         if (index > unescapedChunkStart) {
    337                             out.append(csq, unescapedChunkStart, index);
    338                         }
    339                         if (index == end) {
    340                             break;
    341                         }
    342                         // If we are not finished, calculate the next code
    343                         // point.
    344                         int cp = codePointAt(csq, index, end);
    345                         if (cp < 0) {
    346                             // Our sequence ended half way through a surrogate
    347                             // pair so just
    348                             // record the state and exit.
    349                             pendingHighSurrogate = -cp;
    350                             break;
    351                         }
    352                         // Escape the code point and output the characters.
    353                         char[] escaped = escape(cp);
    354                         if (escaped != null) {
    355                             outputChars(escaped, escaped.length);
    356                         } else {
    357                             // This shouldn't really happen if nextEscapeIndex
    358                             // is correct but
    359                             // we should cope with false positives.
    360                             int len = Character.toChars(cp, decodedChars, 0);
    361                             outputChars(decodedChars, len);
    362                         }
    363                         // Update our index past the escaped character and
    364                         // continue.
    365                         index += (Character.isSupplementaryCodePoint(cp) ? 2 : 1);
    366                         unescapedChunkStart = index;
    367                     }
    368                 }
    369                 return this;
    370             }
    371
    372             public Appendable append(char c) throws IOException {
    373                 if (pendingHighSurrogate != -1) {
    374                     // Our last append operation ended halfway through a
    375                     // surrogate pair
    376                     // so we have to do some extra work first.
    377                     if (!Character.isLowSurrogate(c)) {
    378                         throw new IllegalArgumentException(
    379                                 "Expected low surrogate character but got '" + c + "' with value "
    380                                         + (int) c);
    381                     }
    382                     char[] escaped = escape(Character.toCodePoint((char) pendingHighSurrogate, c));
    383                     if (escaped != null) {
    384                         outputChars(escaped, escaped.length);
    385                     } else {
    386                         out.append((char) pendingHighSurrogate);
    387                         out.append(c);
    388                     }
    389                     pendingHighSurrogate = -1;
    390                 } else if (Character.isHighSurrogate(c)) {
    391                     // This is the start of a (split) surrogate pair.
    392                     pendingHighSurrogate = c;
    393                 } else {
    394                     if (Character.isLowSurrogate(c)) {
    395                         throw new IllegalArgumentException("Unexpected low surrogate character '"
    396                                 + c + "' with value " + (int) c);
    397                     }
    398                     // This is a normal (non surrogate) char.
    399                     char[] escaped = escape(c);
    400                     if (escaped != null) {
    401                         outputChars(escaped, escaped.length);
    402                     } else {
    403                         out.append(c);
    404                     }
    405                 }
    406                 return this;
    407             }
    408
    409             private void outputChars(char[] chars, int len) throws IOException {
    410                 for (int n = 0; n < len; n++) {
    411                     out.append(chars[n]);
    412                 }
    413             }
    414         };
    415     }
    416
    417     /**
    418      * Returns the Unicode code point of the character at the given index.
    419      *
    420      * <p>
    421      * Unlike {@link Character#codePointAt(CharSequence, int)} or
    422      * {@link String#codePointAt(int)} this method will never fail silently when
    423      * encountering an invalid surrogate pair.
    424      *
    425      * <p>
    426      * The behaviour of this method is as follows:
    427      * <ol>
    428      * <li>If {@code index >= end}, {@link IndexOutOfBoundsException} is thrown.
    429      * <li><b>If the character at the specified index is not a surrogate, it is
    430      * returned.</b>
    431      * <li>If the first character was a high surrogate value, then an attempt is
    432      * made to read the next character.
    433      * <ol>
    434      * <li><b>If the end of the sequence was reached, the negated value of the
    435      * trailing high surrogate is returned.</b>
    436      * <li><b>If the next character was a valid low surrogate, the code point
    437      * value of the high/low surrogate pair is returned.</b>
    438      * <li>If the next character was not a low surrogate value, then
    439      * {@link IllegalArgumentException} is thrown.
    440      * </ol>
    441      * <li>If the first character was a low surrogate value,
    442      * {@link IllegalArgumentException} is thrown.
    443      * </ol>
    444      *
    445      * @param seq
    446      *            the sequence of characters from which to decode the code point
    447      * @param index
    448      *            the index of the first character to decode
    449      * @param end
    450      *            the index beyond the last valid character to decode
    451      * @return the Unicode code point for the given index or the negated value
    452      *         of the trailing high surrogate character at the end of the
    453      *         sequence
    454      */
    455     protected static final int codePointAt(CharSequence seq, int index, int end) {
    456         if (index < end) {
    457             char c1 = seq.charAt(index++);
    458             if (c1 < Character.MIN_HIGH_SURROGATE || c1 > Character.MAX_LOW_SURROGATE) {
    459                 // Fast path (first test is probably all we need to do)
    460                 return c1;
    461             } else if (c1 <= Character.MAX_HIGH_SURROGATE) {
    462                 // If the high surrogate was the last character, return its
    463                 // inverse
    464                 if (index == end) {
    465                     return -c1;
    466                 }
    467                 // Otherwise look for the low surrogate following it
    468                 char c2 = seq.charAt(index);
    469                 if (Character.isLowSurrogate(c2)) {
    470                     return Character.toCodePoint(c1, c2);
    471                 }
    472                 throw new IllegalArgumentException("Expected low surrogate but got char '" + c2
    473                         + "' with value " + (int) c2 + " at index " + index);
    474             } else {
    475                 throw new IllegalArgumentException("Unexpected low surrogate character '" + c1
    476                         + "' with value " + (int) c1 + " at index " + (index - 1));
    477             }
    478         }
    479         throw new IndexOutOfBoundsException("Index exceeds specified range");
    480     }
    481
    482     /**
    483      * Helper method to grow the character buffer as needed, this only happens
    484      * once in a while so it's ok if it's in a method call. If the index passed
    485      * in is 0 then no copying will be done.
    486      */
    487     private static final char[] growBuffer(char[] dest, int index, int size) {
    488         char[] copy = new char[size];
    489         if (index > 0) {
    490             System.arraycopy(dest, 0, copy, 0, index);
    491         }
    492         return copy;
    493     }
    494
    495     /**
    496      * A thread-local destination buffer to keep us from creating new buffers.
    497      * The starting size is 1024 characters. If we grow past this we don't put
    498      * it back in the threadlocal, we just keep going and grow as needed.
    499      */
    500     private static final ThreadLocal<char[]> DEST_TL = new ThreadLocal<char[]>() {
    501         @Override
    502         protected char[] initialValue() {
    503             return new char[1024];
    504         }
    505     };
    506 }