New, more validating, parser for URI.

sdk/lib/core/uri.dart

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 part of dart.core;
 
 /**
  * A parsed URI, such as a URL.
  *
  * **See also:**
@@ skipping 100 matching lines @@
   List<String> _pathSegments;
 
   /**
    * Cache the computed return value of [queryParameters].
    */
   Map<String, String> _queryParameters;
 
   /**
    * Creates a new URI object by parsing a URI string.
    */
   static Uri parse(String uri) {

[kevmoo, 2014/06/10 21:29:08]

Need to update doc comment that this method will now throw with invalid values
for `uri`.

Perhaps we should reference the RFC?

[Lasse Reichstein Nielsen, 2014/06/12 08:07:31]

It threw before as well, now it just detects more invalid cases.
So, we always needed to write that.

     // This parsing will not validate percent-encoding, IPv6, etc. When done
     // it will call `new Uri(...)` which will perform these validations.
     // This is purely splitting up the URI string into components.
     //
     // Important parts of the RFC 3986 used here:
     // URI           = scheme ":" hier-part [ "?" query ] [ "#" fragment ]
     //
     // hier-part     = "//" authority path-abempty
     //               / path-absolute
     //               / path-rootless
@@ skipping 33 matching lines @@
     // segment       = *pchar
     // segment-nz    = 1*pchar
     // segment-nz-nc = 1*( unreserved / pct-encoded / sub-delims / "@" )
     //               ; non-zero-length segment without any colon ":"
     //
     // pchar         = unreserved / pct-encoded / sub-delims / ":" / "@"
     //
     // query         = *( pchar / "/" / "?" )
     //
     // fragment      = *( pchar / "/" / "?" )
-    bool isRegName(int ch) {
-      return ch < 128 && ((_regNameTable[ch >> 4] & (1 << (ch & 0x0f))) != 0);
-    }
-
-    int ipV6Address(int index) {
-      // IPv6. Skip to ']'.
-      index = uri.indexOf(']', index);
-      if (index == -1) {
-        throw new FormatException("Bad end of IPv6 host");
-      }
-      return index + 1;
-    }
-
-    int length = uri.length;
+    if (uri.isEmpty) {
+      return new Uri();
+    }
+    String scheme;
+    String userInfo = "";
+    String host = "";
+    int port = 0;
+    String path = "";
+    String query;
+    String fragment;
+    bool allowColonInPath = false;
+
+    /// Index after current char.

[Søren Gjesse, 2014/06/11 08:33:15]

Why dart-doc comments here?

[Lasse Reichstein Nielsen, 2014/06/12 08:07:31]

Because I assume the editor will display that comment if you hover over the
variable below. 

     int index = 0;
-
-    int schemeEndIndex = 0;
-
-    if (length == 0) {
-      return new Uri();
-    }
-
-    if (uri.codeUnitAt(0) != _SLASH) {
-      // Can be scheme.
-      while (index < length) {
-        // Look for ':'. If found, continue from the post of ':'. If not (end
-        // reached or invalid scheme char found) back up one char, and continue
-        // to path.
-        // Note that scheme-chars is contained in path-chars.
-        int codeUnit = uri.codeUnitAt(index++);
-        if (!_isSchemeCharacter(codeUnit)) {
-          if (codeUnit == _COLON) {
-            schemeEndIndex = index;
-          } else {
-            // Back up one char, since we met an invalid scheme char.
-            index--;
-          }
-          break;
-        }
-      }
-    }
-
-    int userInfoEndIndex = -1;
-    int portIndex = -1;
-    int authorityEndIndex = schemeEndIndex;
-    // If we see '//', there must be an authority.
-    if (authorityEndIndex == index &&
-        authorityEndIndex + 1 < length &&
-        uri.codeUnitAt(authorityEndIndex) == _SLASH &&
-        uri.codeUnitAt(authorityEndIndex + 1) == _SLASH) {
-      // Skip '//'.
-      authorityEndIndex += 2;
-      // It can both be host and userInfo.
-      while (authorityEndIndex < length) {
-        int codeUnit = uri.codeUnitAt(authorityEndIndex++);
-        if (!isRegName(codeUnit)) {
-          if (codeUnit == _LEFT_BRACKET) {
-            authorityEndIndex = ipV6Address(authorityEndIndex);
-          } else if (portIndex == -1 && codeUnit == _COLON) {
-            // First time ':'.
-            portIndex = authorityEndIndex;
-          } else if (codeUnit == _AT_SIGN || codeUnit == _COLON) {
-            // Second time ':' or first '@'. Must be userInfo.
-            userInfoEndIndex = uri.indexOf('@', authorityEndIndex - 1);
-            // Not found. Must be path then.
-            if (userInfoEndIndex == -1) {
-              authorityEndIndex = index;
-              break;
+    /// Current char.
+    int current = _EOI;
+    /// Start index of current section being parsed.
+    int start = 0;

[Anders Johnsen, 2014/06/11 10:00:03]

Start is a bit ambiguous. currentSectionStart ? 

[Lasse Reichstein Nielsen, 2014/06/12 08:07:31]

.... loooooong name.
But ok.

+    /// The position after the current character. If parsing a percent
+    /// escape, this is index + 3, otherwise index + 1.
+    int nextIndex = 0;
+
+    void advance() {
+      index = nextIndex;
+      if (index < uri.length) {
+        current = uri.codeUnitAt(index);
+        if (_MAX_VALID_CHAR >= current) {
+          if (_PERCENT != current) {
+            nextIndex = nextIndex + 1;
+            return;
+          }
+          if (index + 2 >= uri.length ||
+              !_isHexDigit(uri.codeUnitAt(index + 1)) ||
+              !_isHexDigit(uri.codeUnitAt(index + 2))) {
+            _fail(uri, index, "Incomplete percent escape");
+          }
+          // Valid escape, returns _PERCENT as current.
+          nextIndex = nextIndex + 3;
+          return;
+        }
+        _fail(uri, index, "Unexpected character");
+      }
+      current = _EOI;
+    }
+
+    // Parse authority.
+    void parseAuth() {
+      start = index;
+      void parseIpV6() {
+        assert(current == _LEFT_BRACKET);
+        assert(start == index);
+        for (int i = index + 1; i < uri.length; i++) {
+          if (uri.codeUnitAt(i) == _RIGHT_BRACKET) {
+            nextIndex = i + 1;
+            advance();
+            host = uri.substring(start, index);

[Søren Gjesse, 2014/06/11 08:33:15]

Are we doing proper IPv6 validation later, or is that not part of the spec?

[Lasse Reichstein Nielsen, 2014/06/12 08:07:31]

I believe we are doing it later.

I don't know if we allow [v47:arglebargle] syntax.

+            return;
+          }
+        }
+        _fail(uri, start, "Unmatched [ in host name");

[kevmoo, 2014/06/10 21:29:08]

quote '['

+      }
+
+      void parseHost() {
+        assert(start == index);
+        if (current == _LEFT_BRACKET) {
+          parseIpV6();
+          return;
+        }
+        while (_isRegNameChar(current)) {
+          advance();
+        }
+        host = uri.substring(start, index);
+      }
+
+      int parsePort() {
+        assert(_isDigit(current));
+        int portVal = current - _ZERO;
+        advance();
+        while (_isDigit(current)) {
+          portVal = portVal * 10 + (current - _ZERO);

[Søren Gjesse, 2014/06/11 08:33:15]

Any limitations on the port value in the spec?

+          advance();
+        }
+        return portVal;
+      }
+
+      maybeUserInfo: {
+        // Break this when we know user-info is done or not there.
+        // user-info or reg-name
+        if (current == _LEFT_BRACKET) break maybeUserInfo;
+        while (_isRegNameChar(current)) {
+          advance();
+        }
+        if (current == _SLASH) {
+          host = uri.substring(start, index);
+          return;
+        }
+        if (current == _AT_SIGN) {
+          userInfo = uri.substring(start, index);
+          advance();
+          start = index;
+          break maybeUserInfo;
+        }
+        if (current == _COLON) {
+          // First colon seen after what might be a host name.
+          // Can be either part of user-info or preceeding a port.
+          int hostEnd = index;
+          advance();
+          // user-info or port.
+          if (_isDigit(current)) {
+            int portVal = parsePort();
+            if (current == _SLASH || current == _EOI) {
+              host = uri.substring(start, hostEnd);
+              port = portVal;
+              return;
             }
-            portIndex = -1;
-            authorityEndIndex = userInfoEndIndex + 1;
-            // Now it can only be host:port.
-            while (authorityEndIndex < length) {
-              int codeUnit = uri.codeUnitAt(authorityEndIndex++);
-              if (!isRegName(codeUnit)) {
-                if (codeUnit == _LEFT_BRACKET) {
-                  authorityEndIndex = ipV6Address(authorityEndIndex);
-                } else if (codeUnit == _COLON) {
-                  if (portIndex != -1) {
-                    throw new FormatException("Double port in host");
-                  }
-                  portIndex = authorityEndIndex;
-                } else {
-                  authorityEndIndex--;
-                  break;
-                }
-              }
-            }
-            break;
-          } else {
-            authorityEndIndex--;
-            break;
-          }
-        }
-      }
-    } else {
-      authorityEndIndex = schemeEndIndex;
-    }
-
-    // At path now.
-    int pathEndIndex = authorityEndIndex;
-    while (pathEndIndex < length) {
-      int codeUnit = uri.codeUnitAt(pathEndIndex++);
-      if (codeUnit == _QUESTION || codeUnit == _NUMBER_SIGN) {
-        pathEndIndex--;
-        break;
-      }
-    }
-
-    // Maybe query.
-    int queryEndIndex = pathEndIndex;
-    if (queryEndIndex < length && uri.codeUnitAt(queryEndIndex) == _QUESTION) {
-      while (queryEndIndex < length) {
-        int codeUnit = uri.codeUnitAt(queryEndIndex++);
-        if (codeUnit == _NUMBER_SIGN) {
-          queryEndIndex--;
-          break;
-        }
-      }
-    }
-
-    var scheme = null;
-    if (schemeEndIndex > 0) {
-      scheme = uri.substring(0, schemeEndIndex - 1);
-    }
-
-    var host = "";
-    var userInfo = "";
-    var port = 0;
-    if (schemeEndIndex != authorityEndIndex) {
-      int startIndex = schemeEndIndex + 2;
-      if (userInfoEndIndex > 0) {
-        userInfo = uri.substring(startIndex, userInfoEndIndex);
-        startIndex = userInfoEndIndex + 1;
-      }
-      if (portIndex > 0) {
-        var portStr = uri.substring(portIndex, authorityEndIndex);
-        try {
-          port = int.parse(portStr);
-        } catch (_) {
-          throw new FormatException("Invalid port: '$portStr'");
-        }
-        host = uri.substring(startIndex, portIndex - 1);
-      } else {
-        host = uri.substring(startIndex, authorityEndIndex);
-      }
-    }
-
-    var path = uri.substring(authorityEndIndex, pathEndIndex);
-    var query = "";
-    if (pathEndIndex < queryEndIndex) {
-      query = uri.substring(pathEndIndex + 1, queryEndIndex);
-    }
-    var fragment = "";
-    // If queryEndIndex is not at end (length), there is a fragment.
-    if (queryEndIndex < length) {
-      fragment = uri.substring(queryEndIndex + 1, length);
+          }
+        }
+        if (current == _EOI) {
+          host = uri.substring(start, index);
+          return;
+        }
+        // A non-port character seen after a colon.
+        // This must be user-info.
+        while (_isUserInfoChar(current)) {
+          advance();
+        }
+        if (current != _AT_SIGN) {
+          _fail(uri, index, "Expected @");

[kevmoo, 2014/06/10 21:29:08]

quote '@'

+        }
+        userInfo = uri.substring(start, index);
+        advance();
+        start = index;
+      }  // end maybeUserInfo
+      parseHost();
+      if (current == _COLON) {
+        advance();
+        if (!_isDigit(current)) {
+          _fail(uri, index, "Expected port number");
+        }
+        port = parsePort();
+      }
+    }  // end parseAuth().
+
+    // Start parsing.
+    to_path: {  // Break this block to go to parsing the path.
+      advance();
+      if (_isAlpha(current)) {

[Anders Johnsen, 2014/06/11 10:00:03]

Do we need 'scheme != null' to prevent double-parsing of scheme?

[Lasse Reichstein Nielsen, 2014/06/12 08:07:31]

No, there is no parsing before this point. The code above is a helper function
which is called below.

+        // May be scheme or path.
+        do {
+          advance();
+        } while (_isSchemeCharacter(current));
+        if (current != _COLON) {
+          break to_path;
+        }
+        allowColonInPath = true;
+        scheme = uri.substring(0, index);
+        advance();
+        start = index;
+      }
+      // Path or authority.
+      if (current == _SLASH) {
+        allowColonInPath = true;
+        advance();
+        if (current == _SLASH) {
+          advance();
+          parseAuth();
+          if (current == _EOI) {
+            start = index;
+            break to_path;
+          }
+          if (current != _SLASH) {
+            _fail(uri, index, "Expected /");

[kevmoo, 2014/06/10 21:29:08]

quote '/'

+          }
+          start = index;
+          advance();
+        }
+      }
+    } // end to_path.
+    if (!allowColonInPath) {
+      while (_isPathChar(current) || current == _PERCENT) {

[Anders Johnsen, 2014/06/11 10:00:03]

Will _isPathChar return true for '/' ?

[Lasse Reichstein Nielsen, 2014/06/12 08:07:31]

No.

+        if (current == _COLON) {
+          _fail(uri, index, "Colon in path before first '/'");
+        }
+        advance();
+      }
+    }
+    // Start or continue path. May be empty.
+    while (_isPathChar(current) || current == _SLASH || current == _PERCENT) {
+      advance();
+    }
+    path = uri.substring(start, index);
+
+    if (current == _QUESTION) {
+      start = nextIndex;
+      do {
+        advance();
+      } while (_isQueryChar(current) || current == _PERCENT);
+      query = uri.substring(start, index);
+    }
+
+    if (current == _NUMBER_SIGN) {
+      // Fragment can contain same characters as query.

[Søren Gjesse, 2014/06/11 08:33:15]

No number sign in fragment?

[Lasse Reichstein Nielsen, 2014/06/12 08:07:32]

No. At most one # in any URL.

+      start = nextIndex;
+      do {
+        advance();
+      } while (_isQueryChar(current) || current == _PERCENT);
+      fragment = uri.substring(start, index);
+    }
+
+    if (current != _EOI) {
+      _fail(uri, index, "Unexpected character");
     }
 
     return new Uri(scheme: scheme,

[Anders Johnsen, 2014/06/11 10:00:03]

This constructor does some extra validation. Do we still need that, or should we
add a helper constructor that just assigns the components?

[Lasse Reichstein Nielsen, 2014/06/12 08:07:31]

As pointed out elsewhere, the validation needs to be in the constructor anyway,
so I'll drop this parser change, and move the validation to the normalize
functions used in the constructors instead.

                    userInfo: userInfo,
+                   port: port,

[kevmoo, 2014/06/10 21:29:08]

nit: might as well keep these params in the original (canonical) order, right?

[Lasse Reichstein Nielsen, 2014/06/12 08:07:31]

ACK.

                    host: host,
-                   port: port,
                    path: path,
                    query: query,
                    fragment: fragment);
   }
 
+  // Report a parse failure.
+  static void _fail(uri, index, message) {

[kevmoo, 2014/06/10 21:29:08]

Add types to parameters

+    if (index == uri.length) {
+      message += ": Unexpected end of input.";

[kevmoo, 2014/06/10 21:29:08]

Could this be changed so each message reads like a sentence?

"Unexpected character" + "at end of input." etc

+    } else {
+      message += ": Unexpected character at position $index.\n";

[kevmoo, 2014/06/10 21:29:08]

ditto for reading like a sentence from above.

+      int min = 0;
+      int max = uri.length;
+      String pre = "";
+      String post = "";

[kevmoo, 2014/06/10 21:29:08]

Code comments for what you're doing here? Is this to limit the length of the
error message?

[Lasse Reichstein Nielsen, 2014/06/12 08:07:31]

Yes, at most 78 characters of the source will be displayed.

I should move this to FormatException. It's probably useful in other cases too
(I'll have to detect newlines then, and report the line and index).

+      if (uri.length > 78) {
+        min = index - 10;
+        if (min < 0) min = 0;
+        int max = min + 72;
+        if (max > uri.length) {
+          max = uri.length;
+          min = max - 72;
+        }
+        if (min != 0) pre = "...";
+        if (max != uri.length) post = "...";
+      }
+      message = "$message$pre${uri.substring(min, max)}$post\n"
+                "${' ' * (pre.length + index - min)}^";
+    }
+    throw new FormatException(message);
+  }
+
+
   /**
    * Creates a new URI from its components.
    *
    * Each component is set through a named argument. Any number of
    * components can be provided. The default value for the components
    * not provided is the empry string, except for [port] which has a
    * default value of 0. The [path] and [query] components can be set
    * using two different named arguments.
    *
    * The scheme component is set through [scheme]. The scheme is
@@ skipping 574 matching lines @@
     if (result != null && prevIndex != index) fillResult();
     assert(index == length);
 
     return result.toString();
   }
 
   static bool _isSchemeCharacter(int ch) {
     return ch < 128 && ((_schemeTable[ch >> 4] & (1 << (ch & 0x0f))) != 0);
   }
 
+  static bool _isPathChar(int ch) {
+    return ch < 128 && ((_pathCharTable[ch >> 4] & (1 << (ch & 0x0f))) != 0);
+  }
+
+  static bool _isRegNameChar(int ch) {
+    return ch < 128 && ((_regNameTable[ch >> 4] & (1 << (ch & 0x0f))) != 0);
+  }
+
+  static bool _isUserInfoChar(int ch) {
+    return ch < 128 && (
+      ((_regNameTable[ch >> 4] & (1 << (ch & 0x0f))) != 0) || ch == _COLON);
+  }
+
+  static bool _isQueryChar(int ch) {
+    return ch < 128 && ((_queryCharTable[ch >> 4] & (1 << (ch & 0x0f))) != 0);
+  }
 
   /**
    * Returns whether the URI is absolute.
    */
   bool get isAbsolute => scheme != "" && fragment == "";
 
   String _merge(String base, String reference) {
     if (base == "") return "/$reference";
     return "${base.substring(0, base.lastIndexOf("/") + 1)}$reference";
   }
@@ skipping 597 matching lines @@
   static const int _UPPER_CASE_A = 0x41;
   static const int _UPPER_CASE_F = 0x46;
   static const int _UPPER_CASE_Z = 0x5A;
   static const int _LEFT_BRACKET = 0x5B;
   static const int _BACKSLASH = 0x5C;
   static const int _RIGHT_BRACKET = 0x5D;
   static const int _LOWER_CASE_A = 0x61;
   static const int _LOWER_CASE_F = 0x66;
   static const int _LOWER_CASE_Z = 0x7A;
   static const int _BAR = 0x7C;
+  static const int _MAX_VALID_CHAR = 0x7e;
+  static const int _EOI = 0x10000;  // Not a code unit.

[Anders Johnsen, 2014/06/11 10:00:03]

-1?

[Lasse Reichstein Nielsen, 2014/06/12 08:07:31]

Breaks the _isPathChar function (or requires an extra test) because it currently
starts with (ch < 127) && ...

+
+  static bool _isAlpha(int char) {
+    char |= 0x20;
+    return _LOWER_CASE_A <= char && _LOWER_CASE_Z >= char;
+    // TODO: Test:
+    // return ((char - _a) & 0xffff) <= (_z - _a);
+  }
+
+  static bool _isDigit(int char) {
+    return _NINE >= char && _ZERO <= char;
+  }
+
+  static bool _isHexDigit(int char) {
+    if (_NINE >= char) return _ZERO <= char;
+    char |= 0x20;
+    return _LOWER_CASE_A <= char && _LOWER_CASE_F >= char;
+  }
 
   /**
    * This is the internal implementation of JavaScript's encodeURI function.
    * It encodes all characters in the string [text] except for those
    * that appear in [canonicalTable], and returns the escaped string.
    */
   static String _uriEncode(List<int> canonicalTable,
                            String text,
                            {Encoding encoding: UTF8,
                             bool spaceToPlus: false}) {
@@ skipping 278 matching lines @@
       0xafff,   // 0x30 - 0x3f  1111111111110101
                 //              @ABCDEFGHIJKLMNO
       0xffff,   // 0x40 - 0x4f  1111111111111111
                 //              PQRSTUVWXYZ    _
       0x87ff,   // 0x50 - 0x5f  1111111111100001
                 //               abcdefghijklmno
       0xfffe,   // 0x60 - 0x6f  0111111111111111
                 //              pqrstuvwxyz   ~
       0x47ff];  // 0x70 - 0x7f  1111111111100010
 }