uri.C

/*
 * This file is part of the "Archon" framework.
 * (http://files3d.sourceforge.net)
 *
 * Copyright © 2002 by Kristian Spangsege and Brian Kristiansen.
 *
 * Permission to use, copy, modify, and distribute this software and
 * its documentation under the terms of the GNU General Public License is
 * hereby granted. No representations are made about the suitability of
 * this software for any purpose. It is provided "as is" without express
 * or implied warranty. See the GNU General Public License
 * (http://www.gnu.org/copyleft/gpl.html) for more details.
 *
 * The characters in this file are ISO8859-1 encoded.
 *
 * The documentation in this file is in "Doxygen" style
 * (http://www.doxygen.org).
 */

#include <string>

#include <archon/util/file.H>
#include <archon/util/text.H>

#include <archon/util/uri.H>

/*

NOTES:

Problem with allowed relative URI's in file:d/u



Excerpt from RFC 2396:

5.1.3. Base URI from the Retrieval URI

If no base URI is embedded and the document is not encapsulated
within some other entity (e.g., the top level of a composite entity),
then, if a URI was used to retrieve the base document, that URI shall
be considered the base URI.  Note that if the retrieval was the
result of a redirected request, the last URI used (i.e., that which
resulted in the actual retrieval of the document) is the base URI.

Note the remark about redirection!!!

*/

namespace Archon
{
  namespace Utilities
  {
    using namespace std;


    enum Scheme
    {
      scheme_file,
      scheme_http,
      scheme_ftp
    };


    string schemeName(Scheme scheme)
    {
      switch(scheme)
      {
      case scheme_file: return "FILE";
      case scheme_http: return "HTTP";
      case scheme_ftp: return "FTP";
      }
      return "<unknown>";
    }


    /*
     * mark:           ! ' ( ) * - . _ ~
     *
     * common:         $ & + ,
     *
     * user:           $ & + ,     ; =
     * userinfo:       $ & + ,   : ; =
     *
     * pchar_no_equal: $ & + ,   :       @
     * pchar:          $ & + ,   :   =   @
     * uric_no_slash:  $ & + ,   : ; = ? @
     * reserved:       $ & + , / : ; = ? @
     *
     */

    const unsigned lowalphaMask       = 1;
    const unsigned upalphaMask        = 2;
    const unsigned digitMask          = 4;
    const unsigned markMask           = 8;
    const unsigned commonMask         = 16;
    const unsigned slashMask          = 32;
    const unsigned colonMask          = 64;
    const unsigned semicolonMask      = 128;
    const unsigned equalMask          = 256;
    const unsigned questionmarkMask   = 512;
    const unsigned commercialAtMask   = 1024;
    const unsigned otherMask          = 2048;

    const unsigned alphaMask        = lowalphaMask|upalphaMask;
    const unsigned alphanumMask     = alphaMask|digitMask;
    const unsigned unreservedMask   = alphanumMask|markMask;
    const unsigned reservedMask     = commonMask|slashMask|colonMask|
    semicolonMask|equalMask|
    questionmarkMask|commercialAtMask;

    const unsigned userMask         = unreservedMask|commonMask|semicolonMask|
    equalMask;
    const unsigned userInfoMask     = userMask|colonMask;

    const unsigned pcharNoEqualMask = unreservedMask|commonMask|colonMask|
    commercialAtMask;
    const unsigned pcharMask        = pcharNoEqualMask|equalMask;
    const unsigned uricNoSlashMask  = pcharMask|semicolonMask|questionmarkMask;
    const unsigned uricMask         = uricNoSlashMask|slashMask;

    const unsigned anyMask          = uricMask|otherMask;

    unsigned charClassTable[127-32] =
    {
      /*  32    ! " #  */     2048,        8,     2048,     2048,
      /*  36  $ % & '  */       16,     2048,       16,        8,
      /*  40  ( ) * +  */        8,        8,        8,       16,
      /*  44  , - . /  */       16,        8,        8,       32,
      /*  48  0 1 2 3  */        4,        4,        4,        4,
      /*  52  4 5 6 7  */        4,        4,        4,        4,
      /*  56  8 9 : ;  */        4,        4,       64,      128,
      /*  60  < = > ?  */     2048,      256,     2048,      512,
      /*  64  @ A B C  */     1024,        2,        2,        2,
      /*  68  D E F G  */        2,        2,        2,        2,
      /*  72  H I J K  */        2,        2,        2,        2,
      /*  76  L M N O  */        2,        2,        2,        2,
      /*  80  P Q R S  */        2,        2,        2,        2,
      /*  84  T U V W  */        2,        2,        2,        2,
      /*  88  X Y Z [  */        2,        2,        2,     2048,
      /*  92  \ ] ^ _  */     2048,     2048,     2048,        8,
      /*  96  ` a b c  */     2048,        1,        1,        1,
      /* 100  d e f g  */        1,        1,        1,        1,
      /* 104  h i j k  */        1,        1,        1,        1,
      /* 108  l m n o  */        1,        1,        1,        1,
      /* 112  p q r s  */        1,        1,        1,        1,
      /* 116  t u v w  */        1,        1,        1,        1,
      /* 120  x y z {  */        1,        1,        1,     2048,
      /* 124  | } ~    */     2048,     2048,        8
    };


    static void validatePart(const string &v, const string &uri, int offset,
                             unsigned charClassMask, bool allowEscape,
                             const string &partName)
    {
      for(string::size_type i=0; i<v.size(); ++i)
      {
        unsigned char c = static_cast<unsigned char>(v[i]);
        if(allowEscape && c == '%')
        {
          if(v.size() <= i+2)
            ARCHON_THROW4(Uri::SyntaxException,
                          "Un-terminated escape sequence "
                          "within " + partName, uri, offset+i,
                          offset + v.size());
          if(!isxdigit(static_cast<unsigned char>(v[i+1])) ||
             !isxdigit(static_cast<unsigned char>(v[i+2])))
            ARCHON_THROW4(Uri::SyntaxException,
                          "Invalid escape sequence "
                          "within " + partName, uri,
                          offset+i, offset+i+3);
          i += 2;
        }
        else if(c < '\x20' || c > '\x7e' ||
                !(charClassTable[c-'\x20']&charClassMask))
          ARCHON_THROW4(Uri::SyntaxException,
                        "Illegal character within " +
                        partName, uri, offset+i, offset+i+1);
      }
    }


    static void validateUser(const string &v, const string &uri,
                             int offset, Scheme scheme)
    {
      validatePart(v, uri, offset, userMask, true, "username");
    }


    static void validatePassword(const string &v, const string &uri,
                                 int offset, Scheme scheme)
    {
      /*
       * Password is restructed to the same character class as the
       * username
       */
      validatePart(v, uri, offset, userMask, true, "password");
    }


    static void validateUserinfo(const string &v, const string &uri,
                                 int offset, Scheme scheme)
    {
      /*
       * RFC 2396 does not specify precisely how to seperate the
       * password from the username, and even advices aginst ever having
       * a password in a URI.
       *
       * The partially deprecated RFC 1738 specifies though, that the
       * only two schemes that supports a user-info part before the
       * domain name, is FTP and TELNET. In both schemes the seperator
       * is ":", and ":" is neither allowed in the username nor in the
       * password. So this is what I'll stick to.  */
      string::size_type i = v.find(':');
      if(i != string::npos)
      {
        validateUser(v.substr(0, i), uri, offset, scheme);
        validatePassword(v.substr(i+1), uri, offset+i+1, scheme);
      }
      else validateUser(v, uri, offset, scheme);
    }


    static void validateHost(const string &v, const string &uri,
                             int offset, Scheme scheme)
    {
      string::size_type i = v.rfind('.');
      if(i != string::npos && i+1 < v.size() && isdigit(static_cast<unsigned char>(v[i+1])))
      {
        // IPv4 address
        const string::size_type i1 =
          v.find('.');
        const string::size_type i2 =
          i1 == string::npos ? string::npos : v.find('.', i1+1);
        const string::size_type i3 =
          i2 == string::npos ? string::npos : v.find('.', i2+1);
        const string::size_type i4 =
          i3 == string::npos ? string::npos : v.find('.', i3+1);
        if(i4 != string::npos || i3 == string::npos)
          ARCHON_THROW4(Uri::SyntaxException,
                        "Wrong number of fields in IPv4 address",
                        uri, offset, offset+v.size());
        if(i1 == 0 || i1+1 == i2 || i2+1 == i3 || i3+1 == v.size())
          ARCHON_THROW4(Uri::SyntaxException,
                        "Empty fields in IPv4 address",
                        uri, offset, offset+v.size());
        for(i=0; i<v.size(); ++i)
          if(!isdigit(v[i]) && v[i] != '.')
            ARCHON_THROW4(Uri::SyntaxException,
                          "Illegal character within IPv4 address",
                          uri, offset+i, offset+i+1);
      }
      else
      {
        // Internet domain name

        i = 0;
        string::size_type j;
        /*
         * 'i' is position of first character of current domain label
         * 'j' is 1 + position of last character of current domain label
         */

        for(;;)
        {
          j = v.find('.', i);
          if(j == string::npos) j = v.size();

          if(j == i && j < v.size())
            ARCHON_THROW4(Uri::SyntaxException,
                          "Empty label within domain name",
                          uri, offset+i, offset+i+1);
          for(string::size_type k = i; k<j; ++k)
            if(!isalnum(v[k]) && (v[k] != '-' || k == i || k == j-1))
              ARCHON_THROW4(Uri::SyntaxException,
                            "Illegal character within domain name",
                            uri, offset+k, offset+k+1);
          if(j == v.size()) break;

          i = j+1;
        }
      }
    }


    static void validatePort(const string &v, const string &uri,
                             int offset, Scheme scheme)
    {
      validatePart(v, uri, offset, digitMask, false, "port number");
    }


    static void validateHostPort(const string &v, const string &uri,
                                 int offset, Scheme scheme)
    {
      string::size_type i = v.rfind(':');
      if(i != string::npos)
      {
        validateHost(v.substr(0, i), uri, offset, scheme);

        if(scheme == scheme_file)
          ARCHON_THROW4(Uri::SyntaxException,
                        "Port number not allowed in " +
                        schemeName(scheme) + " URI",
                        uri, offset+i, offset+v.size());

        validatePort(v.substr(i+1), uri, offset+i+1, scheme);
      }
      else validateHost(v, uri, offset, scheme);
    }


    static void validateAuthority(string v, const string &uri,
                                  int offset, Scheme scheme)
    {
      if(v.empty()) return;
      v.erase(0, 2);
      offset += 2;
      string::size_type i = v.rfind('@');
      if(i != string::npos)
      {
        if(scheme != scheme_ftp)
          ARCHON_THROW4(Uri::SyntaxException,
                        "User info not allowed in " +
                        schemeName(scheme) + " URI",
                        uri, offset, offset+i+1);

        validateUserinfo(v.substr(0, i), uri, offset, scheme);
        validateHostPort(v.substr(i+1), uri, offset+i+1, scheme);
      }
      else validateHostPort(v, uri, offset, scheme);
    }


    static void validatePathSegmentParameter(const string &v, const string &uri,
                                             int offset, Scheme scheme)
    {
      if(scheme == scheme_ftp)
      {
        if(v.size() == 0)
          ARCHON_THROW4(Uri::SyntaxException,
                        "Path segment parameter expexted",
                        uri, offset, offset+1);

        if(v.substr(0, 5) == "type=")
        {
          const string t = v.substr(5);
          if(t == "a" || t == "A" ||
             t == "i" || t == "I" ||
             t == "d" || t == "D") return;
        }
        ARCHON_THROW4(Uri::SyntaxException,
                      "A path segment parameter must "
                      "have the form 'type=[aidAID]' in the " +
                      schemeName(scheme) +
                      " URI scheme", uri, offset,
                      offset+v.size());
      }
      else
      {
        validatePart(v, uri, offset, pcharMask, true, "path segment parameter ");      
      }
    }


    static void validatePathSegment(const string &v, const string &uri,
                                    int offset, Scheme scheme,
                                    bool lastSegment)
    {
      string::size_type i = v.find(';');
      if(i != string::npos)
      {
        if(scheme == scheme_http ||
           scheme == scheme_file)
          ARCHON_THROW4(Uri::SyntaxException,
                        "Path segment parameters not "
                        "allowed in " + schemeName(scheme) +
                        " URI scheme", uri, offset+i,
                        offset+v.size());

        if(scheme == scheme_ftp && !lastSegment)
          ARCHON_THROW4(Uri::SyntaxException,
                        "Path segment parameters may "
                        "only be applied to the final path segemnt "
                        "in the " + schemeName(scheme) +
                        " URI scheme", uri, offset+i,
                        offset+v.size());

        // 'j' is position of first character of current parameter
        // 'k' is 1 + position of last character of current parameter
        string::size_type j=i+1, k;

        for(;;)
        {
          k = v.find(';', j);
          if(k == string::npos) k = v.size();

          validatePathSegmentParameter(v.substr(j, k-j), uri, offset+j,
                                       scheme);

          if(k == v.size()) break;

          if(scheme == scheme_ftp)
            ARCHON_THROW4(Uri::SyntaxException,
                          "Only one path segemnt parameter "
                          "allowed in the " + schemeName(scheme) +
                          " URI scheme", uri, offset+k,
                          offset+v.size());

          j = k+1;
        }
      }
      else i = v.size();

      /*
       * I assume here that "=" is not allowed un-escaped in the part
       * of the path segment that preceeds the path segment
       * parameters.
       *
       * In RFC 2396 it is stated that "=" is a part of the character
       * class "pchar", and thus may occur before the parameters, but
       * also that it is reserved for special purpose if occuring
       * somewhere in a path segemnt.
       *
       * For any URI scheme that I know of, "=" has no special meaning
       * whitin the part of a path segment that preceeds the
       * parameters, so I have chosen only to allow "=" in the
       * parameter section of the path segment.
       */
      validatePart(v.substr(0, i), uri, offset, uricMask, true,
                   "path segment");
    }


    static void validatePath(const string &v, const string &uri,
                             int offset, Scheme scheme)
    {
      // 'i' is position of first character of current path segemnt
      // 'j' is 1 + position of last character of current path segemnt
      string::size_type i=0, j;

      for(;;)
      {
        j = v.find('/', i);
        if(j == string::npos) j = v.size();

        validatePathSegment(v.substr(i, j-i), uri, offset+i, scheme,
                            j == v.size());

        if(j == v.size()) break;

        i = j+1;
      }
    }


    static void validateQuery(string v, const string &uri,
                              int offset, Scheme scheme)
    {
      if(v.empty()) return;
      v.erase(0, 1);
      ++offset;
      validatePart(v, uri, offset, uricMask, true, "query");      
    }


    static void validateFragmentIdentifier(string v, const string &uri,
                                           int offset)
    {
      if(v.empty()) return;
      v.erase(0, 1);
      ++offset;
      validatePart(v, uri, offset, uricMask, true, "fragment identifier");      
    }


    static string makePointerLine(int from, int to)
    {
      return string(from, ' ') + string(to-from, '^') + "\n";
    }



    void Uri::canonicalizePath()
    {
      string::size_type i = 0;
      for(;;)
      {
        i = path.find("/.", i);
        if(i == string::npos) break;
        if(i == path.size()-2 || path[i+2] == '/') path.erase(i+1, 2);
        else if(path[i+2] == '.' && (i == path.size()-3 || path[i+3] == '/') &&
                i>0)
        {
          string::size_type j = path.rfind('/', i-1)+1;
          // The slash will always be there as long as paths are absolute
          path.erase(j, i+4-j);
          i = j-1;
        }
        else i += 2;
      }
    }


    void Uri::resolveRelative(const Uri &baseUri)
    {
      scheme = baseUri.scheme;
      if(!authority.empty()) return;
      authority = baseUri.authority;
      if(!path.empty() && path[0] == '/') return;
      if(!path.empty())
      {
        // Relative path encountered
        path = (baseUri.path.empty() ? "/" :
                baseUri.path.substr(0, baseUri.path.rfind('/')+1)) + path;
        canonicalizePath();
        return;
      }
      query = baseUri.query;
    }


    Uri::Uri()
    {
      scheme = "file:";
    
      string cwd = File::getCWD();
      if(cwd[cwd.size()-1] != '/') cwd += '/';

      // 'i' is position of first character of current path segemnt
      // 'j' is 1 + position of last character of current path segemnt
      string::size_type i=0, j;

      for(;;)
      {
        j = cwd.find('/', i);
        if(j == string::npos) j = cwd.size();

        path.append(encode(cwd.substr(i, j-i), false));

        if(j == cwd.size()) break;

        path += '/';

        i = j+1;
      }
    }


    Uri::Uri(const string &uri, const Uri &baseUri)
    {
      // Decompose URI into the four main parts (all four may be empty)

      // Scheme
      string::size_type i = uri.find_first_of(":/?#");
      if(i != string::npos && uri[i] == ':') scheme = uri.substr(0, ++i);
      else i = 0;

      // Authority
      const string::size_type iAuthority = i;
      if(uri.size() >= i+2 && uri.substr(i, 2) == "//")
      {
        string::size_type j = uri.find_first_of("/?#", i+2);
        if(j == string::npos) j = uri.size();
        authority = uri.substr(i, j-i);
        i = j;
      }

      // Path
      const string::size_type iPath = i;
      {
        string::size_type j = uri.find_first_of("?#", i);
        if(j == string::npos) j = uri.size();
        path = uri.substr(i, j-i);
        i = j;
      }

      // Query
      const string::size_type iQuery = i;
      if(uri.size() >= i+1 && uri[i] == '?')
      {
        string::size_type j = uri.find('#', i+1);
        if(j == string::npos) j = uri.size();
        query = uri.substr(i, j-i);
        i = j;
      }

      if(i < uri.size())
        ARCHON_THROW4(SyntaxException,
                      "Illegal character in URI (this looks more "
                      "like a URI Reference)", uri, i, i+1);

      string effectiveScheme = scheme.empty() ? baseUri.scheme : scheme;
      effectiveScheme.erase(effectiveScheme.size()-1);
      if(Text::compareIgnoreCase(effectiveScheme, "file") == 0)
      {
        validateAuthority(authority, uri, iAuthority, scheme_file);
        validatePath(path, uri, iPath, scheme_file);

        if(!query.empty())
          ARCHON_THROW4(SyntaxException,
                        "Queries are not supported by the " +
                        schemeName(scheme_file) + " URI scheme",
                        uri, iQuery, uri.size());

        if(scheme.empty()) resolveRelative(baseUri);
      }
      else if(Text::compareIgnoreCase(effectiveScheme, "http") == 0 ||
              Text::compareIgnoreCase(effectiveScheme, "https") == 0)
      {
        validateAuthority(authority, uri, iAuthority, scheme_http);
        validatePath(path, uri, iPath, scheme_http);
        validateQuery(query, uri, iQuery, scheme_http);

        if(scheme.empty()) resolveRelative(baseUri);
        else if(authority.size() < 3)
          ARCHON_THROW4(SyntaxException,
                        "Authority (hostname) required "
                        "for absolute " + schemeName(scheme_http) +
                        " URI", uri,
                        iAuthority, iAuthority+1);
      }
      else if(Text::compareIgnoreCase(effectiveScheme, "ftp") == 0)
      {
        validateAuthority(authority, uri, iAuthority, scheme_ftp);
        validatePath(path, uri, iPath, scheme_ftp);

        if(!query.empty())
          ARCHON_THROW4(SyntaxException,
                        "Queries are not supported by the " +
                        schemeName(scheme_ftp) + " URI scheme",
                        uri, iQuery, uri.size());

        if(scheme.empty()) resolveRelative(baseUri);
        else if(authority.size() < 3)
          ARCHON_THROW4(SyntaxException,
                        "Authority (hostname) required "
                        "for absolute " + schemeName(scheme_ftp) +
                        " URI", uri,
                        iAuthority, iAuthority+1);
      }
      else
        ARCHON_THROW4(SyntaxException,
                      "Invalid or unsupported URI scheme",
                      uri, 0, iAuthority);
    }

    bool Uri::isFileScheme() const
    {
      return Text::compareIgnoreCase(scheme, "file:") == 0;
    }

    string Uri::getFile() const
    {
      const string::size_type i = path.rfind('/');
      return path.substr(i == string::npos ? 0 : i+1);
    }


    static const string hexDigits = "0123456789abcdef";

    string Uri::encode(const string &v, bool plusForSpace)
    {
      string result;
      result.reserve(string::size_type(v.size()*1.5));
      for(unsigned i=0; i<v.size(); ++i)
      {
        unsigned char c = static_cast<unsigned char>(v[i]);
        if(c == ' ' && plusForSpace) result += '+';
        else if(c < '\x20' || c > '\x7e' ||
                !(charClassTable[c-'\x20']&unreservedMask))
        {
          result += "%";
          result += hexDigits[c >> 4];
          result += hexDigits[c & 15];
        }
        else result += c;
      }

      return result;
    }


    string Uri::decode(const string &v, bool plusForSpace)
    {
      string result;
      result.reserve(v.size());
      for(unsigned i=0; i<v.size(); ++i)
      {
        unsigned char c = static_cast<unsigned char>(v[i]);
        if(c == '+' && plusForSpace) c = ' ';
        else if(c == '%')
        {
          if(v.size() <= i+2)
            ARCHON_THROW1(ArgumentException,
                          "Un-terminated escape sequence '" + v + "'");

          int p;
          c = static_cast<unsigned char>(v[++i]);
          if(c >= '0' && c <= '9') p = c - '0';
          else if(c >= 'A' && c <= 'F') p = c - 'A' + 10;
          else if(c >= 'a' && c <= 'f') p = c - 'a' + 10;
          else ARCHON_THROW1(ArgumentException,
                             "Invalid escape sequence '" + v + "'");
          p *= 16;
          c = static_cast<unsigned char>(v[++i]);
          if(c >= '0' && c <= '9') p += c - '0';
          else if(c >= 'A' && c <= 'F') p += c - 'A' + 10;
          else if(c >= 'a' && c <= 'f') p += c - 'a' + 10;
          else ARCHON_THROW1(ArgumentException,
                             "Invalid escape sequence '" + v + "'");

          c = static_cast<unsigned char>(p);
        }

        result += static_cast<char>(c);
      }

      return result;
    }


    string Uri::explain(const SyntaxException &e)
    {
      return
        "Malformed URI: " + e.getMessage() + "\n" +
        e.val + "\n" +
        makePointerLine(e.indexFrom, e.indexTo);
    }


    string Uri::toString() const
    {
      return scheme + authority + path + query;
    }

    ostream &operator<<(ostream &out, const Uri &u)
    {
      out << u.toString();
      return out;
    }


    UriReference::UriReference(const string &uriReference,
                               const UriReference &baseReference)
    {
      if(uriReference.empty())
      {
        uri = baseReference.uri;
        fragmentIdentifier = baseReference.fragmentIdentifier;
        return;
      }

      string::size_type i = uriReference.find('#');
      if(i == string::npos) uri = Uri(uriReference, baseReference.uri);
      else
      {
        uri = Uri(uriReference.substr(0, i), baseReference.uri);
        fragmentIdentifier = uriReference.substr(i);

        validateFragmentIdentifier(fragmentIdentifier, uriReference, i);
      }
    }


    string UriReference::toString() const
    {
      return uri.toString() + fragmentIdentifier;
    }


    ostream &operator<<(ostream &out, const UriReference &r)
    {
      out << r.toString();
      return out;
    }
  }
}

---