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