url/url_canon_path.cc

   1 // Copyright 2013 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include <limits.h>
   6
   7 #include "base/logging.h"
   8 #include "url/url_canon.h"
   9 #include "url/url_canon_internal.h"
  10 #include "url/url_parse_internal.h"
  11
  12 namespace url {
  13
  14 namespace {
  15
  16 enum CharacterFlags {
  17   // Pass through unchanged, whether escaped or unescaped. This doesn't
  18   // actually set anything so you can't OR it to check, it's just to make the
  19   // table below more clear when neither ESCAPE or UNESCAPE is set.
  20   PASS = 0,
  21
  22   // This character requires special handling in DoPartialPath. Doing this test
  23   // first allows us to filter out the common cases of regular characters that
  24   // can be directly copied.
  25   SPECIAL = 1,
  26
  27   // This character must be escaped in the canonical output. Note that all
  28   // escaped chars also have the "special" bit set so that the code that looks
  29   // for this is triggered. Not valid with PASS or ESCAPE
  30   ESCAPE_BIT = 2,
  31   ESCAPE = ESCAPE_BIT | SPECIAL,
  32
  33   // This character must be unescaped in canonical output. Not valid with
  34   // ESCAPE or PASS. We DON'T set the SPECIAL flag since if we encounter these
  35   // characters unescaped, they should just be copied.
  36   UNESCAPE = 4,
  37
  38   // This character is disallowed in URLs. Note that the "special" bit is also
  39   // set to trigger handling.
  40   INVALID_BIT = 8,
  41   INVALID = INVALID_BIT | SPECIAL,
  42 };
  43
  44 // This table contains one of the above flag values. Note some flags are more
  45 // than one bits because they also turn on the "special" flag. Special is the
  46 // only flag that may be combined with others.
  47 //
  48 // This table is designed to match exactly what IE does with the characters.
  49 //
  50 // Dot is even more special, and the escaped version is handled specially by
  51 // IsDot. Therefore, we don't need the "escape" flag, and even the "unescape"
  52 // bit is never handled (we just need the "special") bit.
  53 const unsigned char kPathCharLookup[0x100] = {
  54 //   NULL     control chars...
  55      INVALID, ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,
  56 //   control chars...
  57      ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,
  58 //   ' '      !        "        #        $        %        &        '        (        )        *        +        ,        -        .        /
  59      ESCAPE,  PASS,    ESCAPE,  ESCAPE,  PASS,    ESCAPE,  PASS,    PASS,    PASS,    PASS,    PASS,    PASS,    PASS,    UNESCAPE,SPECIAL, PASS,
  60 //   0        1        2        3        4        5        6        7        8        9        :        ;        <        =        >        ?
  61      UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,PASS,    PASS,    ESCAPE,  PASS,    ESCAPE,  ESCAPE,
  62 //   @        A        B        C        D        E        F        G        H        I        J        K        L        M        N        O
  63      PASS,    UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,
  64 //   P        Q        R        S        T        U        V        W        X        Y        Z        [        \        ]        ^        _
  65      UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,PASS,    ESCAPE,  PASS,    ESCAPE,  UNESCAPE,
  66 //   `        a        b        c        d        e        f        g        h        i        j        k        l        m        n        o
  67      ESCAPE,  UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,
  68 //   p        q        r        s        t        u        v        w        x        y        z        {        |        }        ~        <NBSP>
  69      UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,UNESCAPE,ESCAPE,  ESCAPE,  ESCAPE,  UNESCAPE,ESCAPE,
  70 //   ...all the high-bit characters are escaped
  71      ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,
  72      ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,
  73      ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,
  74      ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,
  75      ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,
  76      ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,
  77      ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,
  78      ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE};
  79
  80 enum DotDisposition {
  81   // The given dot is just part of a filename and is not special.
  82   NOT_A_DIRECTORY,
  83
  84   // The given dot is the current directory.
  85   DIRECTORY_CUR,
  86
  87   // The given dot is the first of a double dot that should take us up one.
  88   DIRECTORY_UP
  89 };
  90
  91 // When the path resolver finds a dot, this function is called with the
  92 // character following that dot to see what it is. The return value
  93 // indicates what type this dot is (see above). This code handles the case
  94 // where the dot is at the end of the input.
  95 //
  96 // |*consumed_len| will contain the number of characters in the input that
  97 // express what we found.
  98 //
  99 // If the input is "../foo", |after_dot| = 1, |end| = 6, and
 100 // at the end, |*consumed_len| = 2 for the "./" this function consumed. The
 101 // original dot length should be handled by the caller.
 102 template<typename CHAR>
 103 DotDisposition ClassifyAfterDot(const CHAR* spec, int after_dot,
 104                                 int end, int* consumed_len) {
 105   if (after_dot == end) {
 106     // Single dot at the end.
 107     *consumed_len = 0;
 108     return DIRECTORY_CUR;
 109   }
 110   if (IsURLSlash(spec[after_dot])) {
 111     // Single dot followed by a slash.
 112     *consumed_len = 1;  // Consume the slash
 113     return DIRECTORY_CUR;
 114   }
 115
 116   int second_dot_len = IsDot(spec, after_dot, end);
 117   if (second_dot_len) {
 118     int after_second_dot = after_dot + second_dot_len;
 119     if (after_second_dot == end) {
 120       // Double dot at the end.
 121       *consumed_len = second_dot_len;
 122       return DIRECTORY_UP;
 123     }
 124     if (IsURLSlash(spec[after_second_dot])) {
 125       // Double dot followed by a slash.
 126       *consumed_len = second_dot_len + 1;
 127       return DIRECTORY_UP;
 128     }
 129   }
 130
 131   // The dots are followed by something else, not a directory.
 132   *consumed_len = 0;
 133   return NOT_A_DIRECTORY;
 134 }
 135
 136 // Rewinds the output to the previous slash. It is assumed that the output
 137 // ends with a slash and this doesn't count (we call this when we are
 138 // appending directory paths, so the previous path component has and ending
 139 // slash).
 140 //
 141 // This will stop at the first slash (assumed to be at position
 142 // |path_begin_in_output| and not go any higher than that. Some web pages
 143 // do ".." too many times, so we need to handle that brokenness.
 144 //
 145 // It searches for a literal slash rather than including a backslash as well
 146 // because it is run only on the canonical output.
 147 //
 148 // The output is guaranteed to end in a slash when this function completes.
 149 void BackUpToPreviousSlash(int path_begin_in_output,
 150                            CanonOutput* output) {
 151   DCHECK(output->length() > 0);
 152
 153   int i = output->length() - 1;
 154   DCHECK(output->at(i) == '/');
 155   if (i == path_begin_in_output)
 156     return;  // We're at the first slash, nothing to do.
 157
 158   // Now back up (skipping the trailing slash) until we find another slash.
 159   i--;
 160   while (output->at(i) != '/' && i > path_begin_in_output)
 161     i--;
 162
 163   // Now shrink the output to just include that last slash we found.
 164   output->set_length(i + 1);
 165 }
 166
 167 // Looks for problematic nested escape sequences and escapes the output as
 168 // needed to ensure they can't be misinterpreted.
 169 //
 170 // Our concern is that in input escape sequence that's invalid because it
 171 // contains nested escape sequences might look valid once those are unescaped.
 172 // For example, "%%300" is not a valid escape sequence, but after unescaping the
 173 // inner "%30" this becomes "%00" which is valid.  Leaving this in the output
 174 // string can result in callers re-canonicalizing the string and unescaping this
 175 // sequence, thus resulting in something fundamentally different than the
 176 // original input here.  This can cause a variety of problems.
 177 //
 178 // This function is called after we've just unescaped a sequence that's within
 179 // two output characters of a previous '%' that we know didn't begin a valid
 180 // escape sequence in the input string.  We look for whether the output is going
 181 // to turn into a valid escape sequence, and if so, convert the initial '%' into
 182 // an escaped "%25" so the output can't be misinterpreted.
 183 //
 184 // |spec| is the input string we're canonicalizing.
 185 // |next_input_index| is the index of the next unprocessed character in |spec|.
 186 // |input_len| is the length of |spec|.
 187 // |last_invalid_percent_index| is the index in |output| of a previously-seen
 188 // '%' character.  The caller knows this '%' character isn't followed by a valid
 189 // escape sequence in the input string.
 190 // |output| is the canonicalized output thus far.  The caller guarantees this
 191 // ends with a '%' followed by one or two characters, and the '%' is the one
 192 // pointed to by |last_invalid_percent_index|.  The last character in the string
 193 // was just unescaped.
 194 template<typename CHAR>
 195 void CheckForNestedEscapes(const CHAR* spec,
 196                            int next_input_index,
 197                            int input_len,
 198                            int last_invalid_percent_index,
 199                            CanonOutput* output) {
 200   const int length = output->length();
 201   const char last_unescaped_char = output->at(length - 1);
 202
 203   // If |output| currently looks like "%c", we need to try appending the next
 204   // input character to see if this will result in a problematic escape
 205   // sequence.  Note that this won't trigger on the first nested escape of a
 206   // two-escape sequence like "%%30%30" -- we'll allow the conversion to
 207   // "%0%30" -- but the second nested escape will be caught by this function
 208   // when it's called again in that case.
 209   const bool append_next_char = last_invalid_percent_index == length - 2;
 210   if (append_next_char) {
 211     // If the input doesn't contain a 7-bit character next, this case won't be a
 212     // problem.
 213     if ((next_input_index == input_len) || (spec[next_input_index] >= 0x80))
 214       return;
 215     output->push_back(static_cast<char>(spec[next_input_index]));
 216   }
 217
 218   // Now output ends like "%cc".  Try to unescape this.
 219   int begin = last_invalid_percent_index;
 220   unsigned char temp;
 221   if (DecodeEscaped(output->data(), &begin, output->length(), &temp)) {
 222     // New escape sequence found.  Overwrite the characters following the '%'
 223     // with "25", and push_back() the one or two characters that were following
 224     // the '%' when we were called.
 225     if (!append_next_char)
 226       output->push_back(output->at(last_invalid_percent_index + 1));
 227     output->set(last_invalid_percent_index + 1, '2');
 228     output->set(last_invalid_percent_index + 2, '5');
 229     output->push_back(last_unescaped_char);
 230   } else if (append_next_char) {
 231     // Not a valid escape sequence, but we still need to undo appending the next
 232     // source character so the caller can process it normally.
 233     output->set_length(length);
 234   }
 235 }
 236
 237 // Appends the given path to the output. It assumes that if the input path
 238 // starts with a slash, it should be copied to the output. If no path has
 239 // already been appended to the output (the case when not resolving
 240 // relative URLs), the path should begin with a slash.
 241 //
 242 // If there are already path components (this mode is used when appending
 243 // relative paths for resolving), it assumes that the output already has
 244 // a trailing slash and that if the input begins with a slash, it should be
 245 // copied to the output.
 246 //
 247 // We do not collapse multiple slashes in a row to a single slash. It seems
 248 // no web browsers do this, and we don't want incompatibilities, even though
 249 // it would be correct for most systems.
 250 template<typename CHAR, typename UCHAR>
 251 bool DoPartialPath(const CHAR* spec,
 252                    const Component& path,
 253                    int path_begin_in_output,
 254                    CanonOutput* output) {
 255   int end = path.end();
 256
 257   // We use this variable to minimize the amount of work done when unescaping --
 258   // we'll only call CheckForNestedEscapes() when this points at one of the last
 259   // couple of characters in |output|.
 260   int last_invalid_percent_index = INT_MIN;
 261
 262   bool success = true;
 263   for (int i = path.begin; i < end; i++) {
 264     UCHAR uch = static_cast<UCHAR>(spec[i]);
 265     if (sizeof(CHAR) > 1 && uch >= 0x80) {
 266       // We only need to test wide input for having non-ASCII characters. For
 267       // narrow input, we'll always just use the lookup table. We don't try to
 268       // do anything tricky with decoding/validating UTF-8. This function will
 269       // read one or two UTF-16 characters and append the output as UTF-8. This
 270       // call will be removed in 8-bit mode.
 271       success &= AppendUTF8EscapedChar(spec, &i, end, output);
 272     } else {
 273       // Normal ASCII character or 8-bit input, use the lookup table.
 274       unsigned char out_ch = static_cast<unsigned char>(uch);
 275       unsigned char flags = kPathCharLookup[out_ch];
 276       if (flags & SPECIAL) {
 277         // Needs special handling of some sort.
 278         int dotlen;
 279         if ((dotlen = IsDot(spec, i, end)) > 0) {
 280           // See if this dot was preceded by a slash in the output. We
 281           // assume that when canonicalizing paths, they will always
 282           // start with a slash and not a dot, so we don't have to
 283           // bounds check the output.
 284           //
 285           // Note that we check this in the case of dots so we don't have to
 286           // special case slashes. Since slashes are much more common than
 287           // dots, this actually increases performance measurably (though
 288           // slightly).
 289           DCHECK(output->length() > path_begin_in_output);
 290           if (output->length() > path_begin_in_output &&
 291               output->at(output->length() - 1) == '/') {
 292             // Slash followed by a dot, check to see if this is means relative
 293             int consumed_len;
 294             switch (ClassifyAfterDot<CHAR>(spec, i + dotlen, end,
 295                                            &consumed_len)) {
 296               case NOT_A_DIRECTORY:
 297                 // Copy the dot to the output, it means nothing special.
 298                 output->push_back('.');
 299                 i += dotlen - 1;
 300                 break;
 301               case DIRECTORY_CUR:  // Current directory, just skip the input.
 302                 i += dotlen + consumed_len - 1;
 303                 break;
 304               case DIRECTORY_UP:
 305                 BackUpToPreviousSlash(path_begin_in_output, output);
 306                 i += dotlen + consumed_len - 1;
 307                 break;
 308             }
 309           } else {
 310             // This dot is not preceded by a slash, it is just part of some
 311             // file name.
 312             output->push_back('.');
 313             i += dotlen - 1;
 314           }
 315
 316         } else if (out_ch == '\\') {
 317           // Convert backslashes to forward slashes
 318           output->push_back('/');
 319
 320         } else if (out_ch == '%') {
 321           // Handle escape sequences.
 322           unsigned char unescaped_value;
 323           if (DecodeEscaped(spec, &i, end, &unescaped_value)) {
 324             // Valid escape sequence, see if we keep, reject, or unescape it.
 325             // Note that at this point DecodeEscape() will have advanced |i| to
 326             // the last character of the escape sequence.
 327             char unescaped_flags = kPathCharLookup[unescaped_value];
 328
 329             if (unescaped_flags & UNESCAPE) {
 330               // This escaped value shouldn't be escaped.  Try to copy it.
 331               output->push_back(unescaped_value);
 332               // If we just unescaped a value within 2 output characters of the
 333               // '%' from a previously-detected invalid escape sequence, we
 334               // might have an input string with problematic nested escape
 335               // sequences; detect and fix them.
 336               if (last_invalid_percent_index >= (output->length() - 3)) {
 337                 CheckForNestedEscapes(spec, i + 1, end,
 338                                       last_invalid_percent_index, output);
 339               }
 340             } else {
 341               // Either this is an invalid escaped character, or it's a valid
 342               // escaped character we should keep escaped.  In the first case we
 343               // should just copy it exactly and remember the error.  In the
 344               // second we also copy exactly in case the server is sensitive to
 345               // changing the case of any hex letters.
 346               output->push_back('%');
 347               output->push_back(static_cast<char>(spec[i - 1]));
 348               output->push_back(static_cast<char>(spec[i]));
 349               if (unescaped_flags & INVALID_BIT)
 350                 success = false;
 351             }
 352           } else {
 353             // Invalid escape sequence. IE7+ rejects any URLs with such
 354             // sequences, while other browsers pass them through unchanged. We
 355             // use the permissive behavior.
 356             // TODO(brettw): Consider testing IE's strict behavior, which would
 357             // allow removing the code to handle nested escapes above.
 358             last_invalid_percent_index = output->length();
 359             output->push_back('%');
 360           }
 361
 362         } else if (flags & INVALID_BIT) {
 363           // For NULLs, etc. fail.
 364           AppendEscapedChar(out_ch, output);
 365           success = false;
 366
 367         } else if (flags & ESCAPE_BIT) {
 368           // This character should be escaped.
 369           AppendEscapedChar(out_ch, output);
 370         }
 371       } else {
 372         // Nothing special about this character, just append it.
 373         output->push_back(out_ch);
 374       }
 375     }
 376   }
 377   return success;
 378 }
 379
 380 template<typename CHAR, typename UCHAR>
 381 bool DoPath(const CHAR* spec,
 382             const Component& path,
 383             CanonOutput* output,
 384             Component* out_path) {
 385   bool success = true;
 386   out_path->begin = output->length();
 387   if (path.len > 0) {
 388     // Write out an initial slash if the input has none. If we just parse a URL
 389     // and then canonicalize it, it will of course have a slash already. This
 390     // check is for the replacement and relative URL resolving cases of file
 391     // URLs.
 392     if (!IsURLSlash(spec[path.begin]))
 393       output->push_back('/');
 394
 395     success = DoPartialPath<CHAR, UCHAR>(spec, path, out_path->begin, output);
 396   } else {
 397     // No input, canonical path is a slash.
 398     output->push_back('/');
 399   }
 400   out_path->len = output->length() - out_path->begin;
 401   return success;
 402 }
 403
 404 }  // namespace
 405
 406 bool CanonicalizePath(const char* spec,
 407                       const Component& path,
 408                       CanonOutput* output,
 409                       Component* out_path) {
 410   return DoPath<char, unsigned char>(spec, path, output, out_path);
 411 }
 412
 413 bool CanonicalizePath(const base::char16* spec,
 414                       const Component& path,
 415                       CanonOutput* output,
 416                       Component* out_path) {
 417   return DoPath<base::char16, base::char16>(spec, path, output, out_path);
 418 }
 419
 420 bool CanonicalizePartialPath(const char* spec,
 421                              const Component& path,
 422                              int path_begin_in_output,
 423                              CanonOutput* output) {
 424   return DoPartialPath<char, unsigned char>(spec, path, path_begin_in_output,
 425                                             output);
 426 }
 427
 428 bool CanonicalizePartialPath(const base::char16* spec,
 429                              const Component& path,
 430                              int path_begin_in_output,
 431                              CanonOutput* output) {
 432   return DoPartialPath<base::char16, base::char16>(spec, path,
 433                                                    path_begin_in_output,
 434                                                    output);
 435 }
 436
 437 }  // namespace url