url/url_canon_path.cc

   1 // Copyright 2013 The Chromium Authors
   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/check.h"
   8 #include "base/check_op.h"
   9 #include "third_party/abseil-cpp/absl/types/optional.h"
  10 #include "url/url_canon.h"
  11 #include "url/url_canon_internal.h"
  12 #include "url/url_features.h"
  13 #include "url/url_parse_internal.h"
  14
  15 namespace url {
  16
  17 namespace {
  18
  19 enum CharacterFlags {
  20   // Pass through unchanged, whether escaped or not. This doesn't
  21   // actually set anything so you can't OR it to check, it's just to make the
  22   // table below more clear when any other flag is not set.
  23   PASS = 0,
  24
  25   // This character requires special handling in DoPartialPathInternal. Doing
  26   // this test
  27   // first allows us to filter out the common cases of regular characters that
  28   // can be directly copied.
  29   SPECIAL = 1,
  30
  31   // This character must be escaped in the canonical output. Note that all
  32   // escaped chars also have the "special" bit set so that the code that looks
  33   // for this is triggered. Not valid with PASS or ESCAPE
  34   ESCAPE_BIT = 2,
  35   ESCAPE = ESCAPE_BIT | SPECIAL,
  36 };
  37
  38 // This table contains one of the above flag values. Note some flags are more
  39 // than one bits because they also turn on the "special" flag. Special is the
  40 // only flag that may be combined with others.
  41 //
  42 // This table was used to be designed to match exactly what IE did with the
  43 // characters, however, which doesn't comply with the URL Standard as of Jun
  44 // 2023. See http://crbug.com/1400251 and http://crbug.com/1252531 for efforts
  45 // to comply with the URL Standard.
  46 //
  47 // Dot is even more special, and the escaped version is handled specially by
  48 // IsDot. Therefore, we don't need the "escape" flag. We just need the "special"
  49 // bit.
  50 //
  51 // clang-format off
  52 const unsigned char kPathCharLookup[0x100] = {
  53 //   NULL     control chars...
  54      ESCAPE , ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,
  55 //   control chars...
  56      ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,
  57 //   ' '      !        "        #        $        %        &        '        (        )        *        +        ,        -        .        /
  58      ESCAPE,  PASS,    ESCAPE,  ESCAPE,  PASS,    ESCAPE,  PASS,    PASS,    PASS,    PASS,    PASS,    PASS,    PASS,    PASS    ,SPECIAL, PASS,
  59 //   0        1        2        3        4        5        6        7        8        9        :        ;        <        =        >        ?
  60      PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS,    PASS,    ESCAPE,  PASS,    ESCAPE,  ESCAPE,
  61 //   @        A        B        C        D        E        F        G        H        I        J        K        L        M        N        O
  62      PASS,    PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,
  63 //   P        Q        R        S        T        U        V        W        X        Y        Z        [        \        ]        ^        _
  64      PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS,    ESCAPE,  PASS,    ESCAPE,  PASS    ,
  65 //   `        a        b        c        d        e        f        g        h        i        j        k        l        m        n        o
  66      ESCAPE,  PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,
  67 //   p        q        r        s        t        u        v        w        x        y        z        {        |        }        ~        <NBSP>
  68      PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,PASS    ,ESCAPE,  ESCAPE,  ESCAPE,  PASS    ,ESCAPE,
  69 //   ...all the high-bit characters are escaped
  70      ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,  ESCAPE,
  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 // clang-format on
  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,
 104                                 size_t after_dot,
 105                                 size_t end,
 106                                 size_t* consumed_len) {
 107   if (after_dot == end) {
 108     // Single dot at the end.
 109     *consumed_len = 0;
 110     return DIRECTORY_CUR;
 111   }
 112   if (IsURLSlash(spec[after_dot])) {
 113     // Single dot followed by a slash.
 114     *consumed_len = 1;  // Consume the slash
 115     return DIRECTORY_CUR;
 116   }
 117
 118   size_t second_dot_len = IsDot(spec, after_dot, end);
 119   if (second_dot_len) {
 120     size_t after_second_dot = after_dot + second_dot_len;
 121     if (after_second_dot == end) {
 122       // Double dot at the end.
 123       *consumed_len = second_dot_len;
 124       return DIRECTORY_UP;
 125     }
 126     if (IsURLSlash(spec[after_second_dot])) {
 127       // Double dot followed by a slash.
 128       *consumed_len = second_dot_len + 1;
 129       return DIRECTORY_UP;
 130     }
 131   }
 132
 133   // The dots are followed by something else, not a directory.
 134   *consumed_len = 0;
 135   return NOT_A_DIRECTORY;
 136 }
 137
 138 // Rewinds the output to the previous slash. It is assumed that the output
 139 // ends with a slash and this doesn't count (we call this when we are
 140 // appending directory paths, so the previous path component has and ending
 141 // slash).
 142 //
 143 // This will stop at the first slash (assumed to be at position
 144 // |path_begin_in_output| and not go any higher than that. Some web pages
 145 // do ".." too many times, so we need to handle that brokenness.
 146 //
 147 // It searches for a literal slash rather than including a backslash as well
 148 // because it is run only on the canonical output.
 149 //
 150 // The output is guaranteed to end in a slash when this function completes.
 151 void BackUpToPreviousSlash(size_t path_begin_in_output, CanonOutput* output) {
 152   CHECK(output->length() > 0);
 153   CHECK(path_begin_in_output < output->length());
 154
 155   size_t i = output->length() - 1;
 156   DCHECK(output->at(i) == '/');
 157   if (i == path_begin_in_output)
 158     return;  // We're at the first slash, nothing to do.
 159
 160   // Now back up (skipping the trailing slash) until we find another slash.
 161   do {
 162     --i;
 163   } while (output->at(i) != '/' && i > path_begin_in_output);
 164
 165   // Now shrink the output to just include that last slash we found.
 166   output->set_length(i + 1);
 167 }
 168
 169 // Canonicalizes and appends the given path to the output. It assumes that if
 170 // the input path starts with a slash, it should be copied to the output.
 171 //
 172 // If there are already path components (this mode is used when appending
 173 // relative paths for resolving), it assumes that the output already has
 174 // a trailing slash and that if the input begins with a slash, it should be
 175 // copied to the output.
 176 //
 177 // We do not collapse multiple slashes in a row to a single slash. It seems
 178 // no web browsers do this, and we don't want incompatibilities, even though
 179 // it would be correct for most systems.
 180 template <typename CHAR, typename UCHAR>
 181 bool DoPartialPathInternal(const CHAR* spec,
 182                            const Component& path,
 183                            size_t path_begin_in_output,
 184                            CanonOutput* output) {
 185   if (path.is_empty())
 186     return true;
 187
 188   size_t end = static_cast<size_t>(path.end());
 189
 190   bool success = true;
 191   for (size_t i = static_cast<size_t>(path.begin); i < end; i++) {
 192     UCHAR uch = static_cast<UCHAR>(spec[i]);
 193     if (sizeof(CHAR) > 1 && uch >= 0x80) {
 194       // We only need to test wide input for having non-ASCII characters. For
 195       // narrow input, we'll always just use the lookup table. We don't try to
 196       // do anything tricky with decoding/validating UTF-8. This function will
 197       // read one or two UTF-16 characters and append the output as UTF-8. This
 198       // call will be removed in 8-bit mode.
 199       success &= AppendUTF8EscapedChar(spec, &i, end, output);
 200     } else {
 201       // Normal ASCII character or 8-bit input, use the lookup table.
 202       unsigned char out_ch = static_cast<unsigned char>(uch);
 203       unsigned char flags = kPathCharLookup[out_ch];
 204       if (flags & SPECIAL) {
 205         // Needs special handling of some sort.
 206         size_t dotlen;
 207         if ((dotlen = IsDot(spec, i, end)) > 0) {
 208           // See if this dot was preceded by a slash in the output.
 209           //
 210           // Note that we check this in the case of dots so we don't have to
 211           // special case slashes. Since slashes are much more common than
 212           // dots, this actually increases performance measurably (though
 213           // slightly).
 214           if (output->length() > path_begin_in_output &&
 215               output->at(output->length() - 1) == '/') {
 216             // Slash followed by a dot, check to see if this is means relative
 217             size_t consumed_len;
 218             switch (ClassifyAfterDot<CHAR>(spec, i + dotlen, end,
 219                                            &consumed_len)) {
 220               case NOT_A_DIRECTORY:
 221                 // Copy the dot to the output, it means nothing special.
 222                 output->push_back('.');
 223                 i += dotlen - 1;
 224                 break;
 225               case DIRECTORY_CUR:  // Current directory, just skip the input.
 226                 i += dotlen + consumed_len - 1;
 227                 break;
 228               case DIRECTORY_UP:
 229                 BackUpToPreviousSlash(path_begin_in_output, output);
 230                 i += dotlen + consumed_len - 1;
 231                 break;
 232             }
 233           } else {
 234             // This dot is not preceded by a slash, it is just part of some
 235             // file name.
 236             output->push_back('.');
 237             i += dotlen - 1;
 238           }
 239
 240         } else if (out_ch == '\\') {
 241           // Convert backslashes to forward slashes
 242           output->push_back('/');
 243
 244         } else if (out_ch == '%') {
 245           // Handle escape sequences.
 246           unsigned char unused_unescaped_value;
 247           if (DecodeEscaped(spec, &i, end, &unused_unescaped_value)) {
 248             // Valid escape sequence. We should just copy it exactly.
 249             output->push_back('%');
 250             output->push_back(static_cast<char>(spec[i - 1]));
 251             output->push_back(static_cast<char>(spec[i]));
 252           } else {
 253             // Invalid escape sequence. IE7+ rejects any URLs with such
 254             // sequences, while other browsers pass them through unchanged. We
 255             // use the permissive behavior.
 256             // TODO(brettw): Consider testing IE's strict behavior, which would
 257             // allow removing the code to handle nested escapes above.
 258             output->push_back('%');
 259           }
 260         } else if (flags & ESCAPE_BIT) {
 261           // This character should be escaped.
 262           AppendEscapedChar(out_ch, output);
 263         }
 264       } else {
 265         // Nothing special about this character, just append it.
 266         output->push_back(out_ch);
 267       }
 268     }
 269   }
 270   return success;
 271 }
 272
 273 // Perform the same logic as in DoPartialPathInternal(), but updates the
 274 // publicly exposed CanonOutput structure similar to DoPath().  Returns
 275 // true if successful.
 276 template <typename CHAR, typename UCHAR>
 277 bool DoPartialPath(const CHAR* spec,
 278                    const Component& path,
 279                    CanonOutput* output,
 280                    Component* out_path) {
 281   out_path->begin = output->length();
 282   bool success =
 283       DoPartialPathInternal<CHAR, UCHAR>(spec, path, out_path->begin, output);
 284   out_path->len = output->length() - out_path->begin;
 285   return success;
 286 }
 287
 288 template<typename CHAR, typename UCHAR>
 289 bool DoPath(const CHAR* spec,
 290             const Component& path,
 291             CanonOutput* output,
 292             Component* out_path) {
 293   bool success = true;
 294   out_path->begin = output->length();
 295   if (path.is_nonempty()) {
 296     // Write out an initial slash if the input has none. If we just parse a URL
 297     // and then canonicalize it, it will of course have a slash already. This
 298     // check is for the replacement and relative URL resolving cases of file
 299     // URLs.
 300     if (!IsURLSlash(spec[path.begin]))
 301       output->push_back('/');
 302
 303     success =
 304         DoPartialPathInternal<CHAR, UCHAR>(spec, path, out_path->begin, output);
 305   } else {
 306     // No input, canonical path is a slash.
 307     output->push_back('/');
 308   }
 309   out_path->len = output->length() - out_path->begin;
 310   return success;
 311 }
 312
 313 }  // namespace
 314
 315 bool CanonicalizePath(const char* spec,
 316                       const Component& path,
 317                       CanonOutput* output,
 318                       Component* out_path) {
 319   return DoPath<char, unsigned char>(spec, path, output, out_path);
 320 }
 321
 322 bool CanonicalizePath(const char16_t* spec,
 323                       const Component& path,
 324                       CanonOutput* output,
 325                       Component* out_path) {
 326   return DoPath<char16_t, char16_t>(spec, path, output, out_path);
 327 }
 328
 329 bool CanonicalizePartialPath(const char* spec,
 330                              const Component& path,
 331                              CanonOutput* output,
 332                              Component* out_path) {
 333   return DoPartialPath<char, unsigned char>(spec, path, output, out_path);
 334 }
 335
 336 bool CanonicalizePartialPath(const char16_t* spec,
 337                              const Component& path,
 338                              CanonOutput* output,
 339                              Component* out_path) {
 340   return DoPartialPath<char16_t, char16_t>(spec, path, output, out_path);
 341 }
 342
 343 bool CanonicalizePartialPathInternal(const char* spec,
 344                                      const Component& path,
 345                                      size_t path_begin_in_output,
 346                                      CanonOutput* output) {
 347   return DoPartialPathInternal<char, unsigned char>(
 348       spec, path, path_begin_in_output, output);
 349 }
 350
 351 bool CanonicalizePartialPathInternal(const char16_t* spec,
 352                                      const Component& path,
 353                                      size_t path_begin_in_output,
 354                                      CanonOutput* output) {
 355   return DoPartialPathInternal<char16_t, char16_t>(
 356       spec, path, path_begin_in_output, output);
 357 }
 358
 359 }  // namespace url