Integrate most of GoogleURL in WTFURL
[WebKit-https.git] / Source / WTF / wtf / url / src / URLCanonPath.cpp
1 /*
2  * Copyright 2007 Google Inc. All rights reserved.
3  * Copyright 2012 Apple Inc. All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are
7  * met:
8  *
9  *     * Redistributions of source code must retain the above copyright
10  * notice, this list of conditions and the following disclaimer.
11  *     * Redistributions in binary form must reproduce the above
12  * copyright notice, this list of conditions and the following disclaimer
13  * in the documentation and/or other materials provided with the
14  * distribution.
15  *     * Neither the name of Google Inc. nor the names of its
16  * contributors may be used to endorse or promote products derived from
17  * this software without specific prior written permission.
18  *
19  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30  */
31
32 // Canonicalization functions for the paths of URLs.
33
34 #include "config.h"
35 #include "URLCanon.h"
36
37 #include "URLCanonInternal.h"
38 #include "URLParseInternal.h"
39
40 #if USE(WTFURL)
41
42 namespace WTF {
43
44 namespace URLCanonicalizer {
45
46 namespace {
47
48 enum CharacterFlags {
49     // Pass through unchanged, whether escaped or unescaped. This doesn't
50     // actually set anything so you can't OR it to check, it's just to make the
51     // table below more clear when neither ESCAPE or UNESCAPE is set.
52     PASS = 0,
53
54     // This character requires special handling in doPartialPath. Doing this test
55     // first allows us to filter out the common cases of regular characters that
56     // can be directly copied.
57     SPECIAL = 1,
58
59     // This character must be escaped in the canonical output. Note that all
60     // escaped chars also have the "special" bit set so that the code that looks
61     // for this is triggered. Not valid with PASS or ESCAPE
62     ESCAPE_BIT = 2,
63     ESCAPE = ESCAPE_BIT | SPECIAL,
64
65     // This character must be unescaped in canonical output. Not valid with
66     // ESCAPE or PASS. We DON'T set the SPECIAL flag since if we encounter these
67     // characters unescaped, they should just be copied.
68     UNESCAPE = 4,
69
70     // This character is disallowed in URLs. Note that the "special" bit is also
71     // set to trigger handling.
72     INVALID_BIT = 8,
73     INVALID = INVALID_BIT | SPECIAL,
74 };
75
76 // This table contains one of the above flag values. Note some flags are more
77 // than one bits because they also turn on the "special" flag. Special is the
78 // only flag that may be combined with others.
79 //
80 // This table is designed to match exactly what IE does with the characters.
81 //
82 // Dot is even more special, and the escaped version is handled specially by
83 // isDot. Therefore, we don't need the "escape" flag, and even the "unescape"
84 // bit is never handled (we just need the "special") bit.
85 const unsigned char kPathCharLookup[0x100] = {
86 //   null     control chars...
87      INVALID,  ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,
88 //   control chars...
89      ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,
90 //   ' '       !         "         #         $         %         &         '         (         )         *         +         ,         -         .         /
91      ESCAPE,   PASS,     ESCAPE,   ESCAPE,   PASS,     ESCAPE,   PASS,     PASS,     PASS,     PASS,     PASS,     PASS,     PASS,     UNESCAPE, SPECIAL,  PASS,
92 //   0         1         2         3         4         5         6         7         8         9         :         ;         <         =          >        ?
93      UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, PASS,     PASS,     ESCAPE,   PASS,     ESCAPE,   ESCAPE,
94 //   @         A         B         C         D         E         F         G         H         I         J         K         L         M         N         O
95      PASS,     UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE,
96 //   P         Q         R         S         T         U         V         W         X         Y         Z         [         \         ]         ^         _
97      UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, PASS,     ESCAPE,   PASS,     ESCAPE,   UNESCAPE,
98 //   `         a         b         c         d         e         f         g         h         i         j         k         l         m         n         o
99      ESCAPE,   UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE,
100 //   p         q         r         s         t         u         v         w         x         y         z         {         |         }         ~         <NBSP>
101      UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, UNESCAPE, ESCAPE,   ESCAPE,   ESCAPE,   UNESCAPE, ESCAPE,
102 //   ...all the high-bit characters are escaped
103      ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,
104      ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,
105      ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,
106      ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,
107      ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,
108      ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,
109      ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,
110      ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE,   ESCAPE};
111
112 enum DotDisposition {
113     // The given dot is just part of a filename and is not special.
114     NOT_A_DIRECTORY,
115
116     // The given dot is the current directory.
117     DIRECTORY_CUR,
118
119     // The given dot is the first of a double dot that should take us up one.
120     DIRECTORY_UP
121 };
122
123 // When the path resolver finds a dot, this function is called with the
124 // character following that dot to see what it is. The return value
125 // indicates what type this dot is (see above). This code handles the case
126 // where the dot is at the end of the input.
127 //
128 // |*consumedLength| will contain the number of characters in the input that
129 // express what we found.
130 //
131 // If the input is "../foo", |afterDot| = 1, |end| = 6, and
132 // at the end, |*consumedLength| = 2 for the "./" this function consumed. The
133 // original dot length should be handled by the caller.
134 template<typename CHAR>
135 DotDisposition ClassifyAfterDot(const CHAR* spec, int afterDot, int end, int* consumedLength)
136 {
137     if (afterDot == end) {
138         // Single dot at the end.
139         *consumedLength = 0;
140         return DIRECTORY_CUR;
141     }
142     if (URLParser::isURLSlash(spec[afterDot])) {
143         // Single dot followed by a slash.
144         *consumedLength = 1; // Consume the slash
145         return DIRECTORY_CUR;
146     }
147
148     int secondDotLength = isDot(spec, afterDot, end);
149     if (secondDotLength) {
150         int afterSecondDot = afterDot + secondDotLength;
151         if (afterSecondDot == end) {
152             // Double dot at the end.
153             *consumedLength = secondDotLength;
154             return DIRECTORY_UP;
155         }
156         if (URLParser::isURLSlash(spec[afterSecondDot])) {
157             // Double dot followed by a slash.
158             *consumedLength = secondDotLength + 1;
159             return DIRECTORY_UP;
160         }
161     }
162
163     // The dots are followed by something else, not a directory.
164     *consumedLength = 0;
165     return NOT_A_DIRECTORY;
166 }
167
168 // Rewinds the output to the previous slash. It is assumed that the output
169 // ends with a slash and this doesn't count (we call this when we are
170 // appending directory paths, so the previous path component has and ending
171 // slash).
172 //
173 // This will stop at the first slash (assumed to be at position
174 // |pathBeginInOutput| and not go any higher than that. Some web pages
175 // do ".." too many times, so we need to handle that brokenness.
176 //
177 // It searches for a literal slash rather than including a backslash as well
178 // because it is run only on the canonical output.
179 //
180 // The output is guaranteed to end in a slash when this function completes.
181 void BackUpToPreviousSlash(int pathBeginInOutput, URLBuffer<char>& output)
182 {
183     ASSERT(output.length() > 0);
184
185     int i = output.length() - 1;
186     ASSERT(output.at(i) == '/');
187     if (i == pathBeginInOutput)
188         return; // We're at the first slash, nothing to do.
189
190     // Now back up (skipping the trailing slash) until we find another slash.
191     i--;
192     while (output.at(i) != '/' && i > pathBeginInOutput)
193         i--;
194
195     // Now shrink the output to just include that last slash we found.
196     output.setLength(i + 1);
197 }
198
199 // Appends the given path to the output. It assumes that if the input path
200 // starts with a slash, it should be copied to the output. If no path has
201 // already been appended to the output (the case when not resolving
202 // relative URLs), the path should begin with a slash.
203 //
204 // If there are already path components (this mode is used when appending
205 // relative paths for resolving), it assumes that the output already has
206 // a trailing slash and that if the input begins with a slash, it should be
207 // copied to the output.
208 //
209 // We do not collapse multiple slashes in a row to a single slash. It seems
210 // no web browsers do this, and we don't want incompababilities, even though
211 // it would be correct for most systems.
212 template<typename CharacterType, typename UCHAR>
213 bool doPartialPath(const CharacterType* spec, const URLComponent& path, int pathBeginInOutput, URLBuffer<char>& output)
214 {
215     int end = path.end();
216
217     bool success = true;
218     for (int i = path.begin(); i < end; ++i) {
219         UCHAR uch = static_cast<UCHAR>(spec[i]);
220         if (sizeof(CharacterType) > sizeof(char) && uch >= 0x80) {
221             // We only need to test wide input for having non-ASCII characters. For
222             // narrow input, we'll always just use the lookup table. We don't try to
223             // do anything tricky with decoding/validating UTF-8. This function will
224             // read one or two UTF-16 characters and append the output as UTF-8. This
225             // call will be removed in 8-bit mode.
226             success &= AppendUTF8EscapedChar(spec, &i, end, output);
227         } else {
228             // Normal ASCII character or 8-bit input, use the lookup table.
229             unsigned char outCh = static_cast<unsigned char>(uch);
230             unsigned char flags = kPathCharLookup[outCh];
231             if (flags & SPECIAL) {
232                 // Needs special handling of some sort.
233                 int dotlen;
234                 if ((dotlen = isDot(spec, i, end)) > 0) {
235                     // See if this dot was preceeded by a slash in the output. We
236                     // assume that when canonicalizing paths, they will always
237                     // start with a slash and not a dot, so we don't have to
238                     // bounds check the output.
239                     //
240                     // Note that we check this in the case of dots so we don't have to
241                     // special case slashes. Since slashes are much more common than
242                     // dots, this actually increases performance measurably (though
243                     // slightly).
244                     ASSERT(output.length() > pathBeginInOutput);
245                     if (output.length() > pathBeginInOutput && output.at(output.length() - 1) == '/') {
246                         // Slash followed by a dot, check to see if this is means relative
247                         int consumedLength;
248                         switch (ClassifyAfterDot<CharacterType>(spec, i + dotlen, end, &consumedLength)) {
249                         case NOT_A_DIRECTORY:
250                             // Copy the dot to the output, it means nothing special.
251                             output.append('.');
252                             i += dotlen - 1;
253                             break;
254                         case DIRECTORY_CUR: // Current directory, just skip the input.
255                             i += dotlen + consumedLength - 1;
256                             break;
257                         case DIRECTORY_UP:
258                             BackUpToPreviousSlash(pathBeginInOutput, output);
259                             i += dotlen + consumedLength - 1;
260                             break;
261                         }
262                     } else {
263                         // This dot is not preceeded by a slash, it is just part of some
264                         // file name.
265                         output.append('.');
266                         i += dotlen - 1;
267                     }
268                 } else if (outCh == '\\') {
269                     // Convert backslashes to forward slashes
270                     output.append('/');
271                 } else if (outCh == '%') {
272                     // Handle escape sequences.
273                     unsigned char unescapedValue;
274                     if (DecodeEscaped(spec, &i, end, &unescapedValue)) {
275                         // Valid escape sequence, see if we keep, reject, or unescape it.
276                         char unescapedFlags = kPathCharLookup[unescapedValue];
277
278                         if (unescapedFlags & UNESCAPE) {
279                             // This escaped value shouldn't be escaped, copy it.
280                             output.append(unescapedValue);
281                         } else if (unescapedFlags & INVALID_BIT) {
282                             // Invalid escaped character, copy it and remember the error.
283                             output.append('%');
284                             output.append(static_cast<char>(spec[i - 1]));
285                             output.append(static_cast<char>(spec[i]));
286                             success = false;
287                         } else {
288                             // Valid escaped character but we should keep it escaped. We
289                             // don't want to change the case of any hex letters in case
290                             // the server is sensitive to that, so we just copy the two
291                             // characters without checking (DecodeEscape will have advanced
292                             // to the last character of the pair).
293                             output.append('%');
294                             output.append(static_cast<char>(spec[i - 1]));
295                             output.append(static_cast<char>(spec[i]));
296                         }
297                     } else {
298                         // Invalid escape sequence. IE7 rejects any URLs with such
299                         // sequences, while Firefox, IE6, and Safari all pass it through
300                         // unchanged. We are more permissive unlike IE7. I don't think this
301                         // can cause significant problems, if it does, we should change
302                         // to be more like IE7.
303                         output.append('%');
304                     }
305
306                 } else if (flags & INVALID_BIT) {
307                     // For NULLs, etc. fail.
308                     appendURLEscapedCharacter(outCh, output);
309                     success = false;
310
311                 } else if (flags & ESCAPE_BIT) {
312                     // This character should be escaped.
313                     appendURLEscapedCharacter(outCh, output);
314                 }
315             } else {
316                 // Nothing special about this character, just append it.
317                 output.append(outCh);
318             }
319         }
320     }
321     return success;
322 }
323
324 template<typename CharacterType, typename UCHAR>
325 bool doPath(const CharacterType* spec, const URLComponent& path, URLBuffer<char>& output, URLComponent& outputPath)
326 {
327     bool success = true;
328     outputPath.setBegin(output.length());
329     if (path.length() > 0) {
330         // Write out an initial slash if the input has none. If we just parse a URL
331         // and then canonicalize it, it will of course have a slash already. This
332         // check is for the replacement and relative URL resolving cases of file
333         // URLs.
334         if (!URLParser::isURLSlash(spec[path.begin()]))
335             output.append('/');
336
337         success = doPartialPath<CharacterType, UCHAR>(spec, path, outputPath.begin(), output);
338     } else {
339         // No input, canonical path is a slash.
340         output.append('/');
341     }
342     outputPath.setLength(output.length() - outputPath.begin());
343     return success;
344 }
345
346 } // namespace
347
348 bool CanonicalizePath(const char* spec, const URLComponent& path, URLBuffer<char>& output, URLComponent* outputPath)
349 {
350     return doPath<char, unsigned char>(spec, path, output, *outputPath);
351 }
352
353 bool CanonicalizePath(const UChar* spec, const URLComponent& path, URLBuffer<char>& output, URLComponent* outputPath)
354 {
355     return doPath<UChar, UChar>(spec, path, output, *outputPath);
356 }
357
358 bool CanonicalizePartialPath(const char* spec, const URLComponent& path, int pathBeginInOutput, URLBuffer<char>& output)
359 {
360     return doPartialPath<char, unsigned char>(spec, path, pathBeginInOutput, output);
361 }
362
363 bool CanonicalizePartialPath(const UChar* spec, const URLComponent& path, int pathBeginInOutput, URLBuffer<char>& output)
364 {
365     return doPartialPath<UChar, UChar>(spec, path, pathBeginInOutput, output);
366 }
367
368 } // namespace URLCanonicalizer
369
370 } // namespace WTF
371
372 #endif // USE(WTFURL)