text: /** 
   * @file lluri.cpp
   * @author Phoenix
   * @date 2006-02-08
   * @brief Implementation of the LLURI class.
   *
   * $LicenseInfo:firstyear=2006&license=viewerlgpl$
   * Second Life Viewer Source Code
   * Copyright (C) 2010, Linden Research, Inc.
   * 
   * This library is free software; you can redistribute it and/or
   * modify it under the terms of the GNU Lesser General Public
   * License as published by the Free Software Foundation;
   * version 2.1 of the License only.
   * 
   * This library is distributed in the hope that it will be useful,
   * but WITHOUT ANY WARRANTY; without even the implied warranty of
   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   * Lesser General Public License for more details.
   * 
   * You should have received a copy of the GNU Lesser General Public
   * License along with this library; if not, write to the Free Software
   * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
   * 
   * Linden Research, Inc., 945 Battery Street, San Francisco, CA  94111  USA
   * $/LicenseInfo$
   */
  
  #include "linden_common.h"
  
  #include "llapp.h"
  #include "lluri.h"
  #include "llsd.h"
  #include <iomanip>
    
  #include "lluuid.h"
  
  // system includes
  #include <boost/tokenizer.hpp>
  #include <boost/algorithm/string/find_iterator.hpp>
  #include <boost/algorithm/string/finder.hpp>
  
  // static
  void LLURI::encodeCharacter(std::ostream& ostr, std::string::value_type val)
  {
  	ostr << "%"
  
  	     << std::uppercase
  	     << std::hex
  	     << std::setw(2)
  	     << std::setfill('0') 
  
  	     // VWR-4010 Cannot cast to U32 because sign-extension on 
  	     // chars > 128 will result in FFFFFFC3 instead of F3.
  	     << static_cast<S32>(static_cast<U8>(val))
  
  		// reset stream state
  	     << std::nouppercase
  	     << std::dec
  	     << std::setfill(' ');
  }
  
  // static
  std::string LLURI::escape(
  	const std::string& str,
  	const std::string& allowed,
  	bool is_allowed_sorted)
  {
  	// *NOTE: This size determination feels like a good value to
  	// me. If someone wante to come up with a more precise heuristic
  	// with some data to back up the assertion that 'sort is good'
  	// then feel free to change this test a bit.
  	if(!is_allowed_sorted && (str.size() > 2 * allowed.size()))
  	{
  		// if it's already sorted, or if the url is quite long, we
  		// want to optimize this process.
  		std::string sorted_allowed(allowed);
  		std::sort(sorted_allowed.begin(), sorted_allowed.end());
  		return escape(str, sorted_allowed, true);
  	}
  
  	std::ostringstream ostr;
  	std::string::const_iterator it = str.begin();
  	std::string::const_iterator end = str.end();
  	std::string::value_type c;
  	if(is_allowed_sorted)
  	{
  		std::string::const_iterator allowed_begin(allowed.begin());
  		std::string::const_iterator allowed_end(allowed.end());
  		for(; it != end; ++it)
  		{
  			c = *it;
  			if(std::binary_search(allowed_begin, allowed_end, c))
  			{
  				ostr << c;
  			}
  			else
  			{
  				encodeCharacter(ostr, c);
  			}
  		}
  	}
  	else
  	{
  		for(; it != end; ++it)
  		{
  			c = *it;
  			if(allowed.find(c) == std::string::npos)
  			{
  				encodeCharacter(ostr, c);
  			}
  			else
  			{
  				ostr << c;
  			}
  		}
  	}
  	return ostr.str();
  }
  
  // static
  std::string LLURI::unescape(const std::string& str)
  {
  	std::ostringstream ostr;
  	std::string::const_iterator it = str.begin();
  	std::string::const_iterator end = str.end();
  	for(; it != end; ++it)
  	{
  		if((*it) == '%')
  		{
  			++it;
  			if(it == end) break;
  
  			if(is_char_hex(*it))
  			{
  				U8 c = hex_as_nybble(*it++);
  
  				c = c << 4;
  				if (it == end) break;
  
  				if(is_char_hex(*it))
  				{
  					c |= hex_as_nybble(*it);
  					ostr.put((char)c);
  				}
  				else
  				{
  					ostr.put((char)c);
  					ostr.put(*it);
  				}
  			}
  			else
  			{
  				ostr.put('%');
  				ostr.put(*it);
  			}
  		}
  		else
  		{
  			ostr.put(*it);
  		}
  	}
  	return ostr.str();
  }
  
  namespace
  {
  	const std::string unreserved()
  	{
  		static const std::string s =   
  			"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
  			"0123456789"
  			"-._~";
  		return s;
  	}
  	const std::string path()
  	{
  		static const std::string s =
  			"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
  			"abcdefghijklmnopqrstuvwxyz"
  			"0123456789"
  			"$-_.+"
  			"!*'(),"
  			"{}|\\^~[]`"
  			"<>#%"
  			";/?:@&=";
  		return s;
  	}
  	const std::string sub_delims()
  	{
  		static const std::string s = "!$&'()*+,;=";
  		return s;
  	}
  
  	std::string escapeHostAndPort(const std::string& s)
  		{ return LLURI::escape(s, unreserved() + sub_delims() +":"); }
  	std::string escapePathComponent(const std::string& s)
  		{ return LLURI::escape(s, unreserved() + sub_delims() + ":@"); }
  	// <exodus>
  	// Removed the '+' because some servers rely on it being removed and
  	// no server relies on the contrary.
  	std::string escapeQueryVariable(const std::string& s)
  		{ return LLURI::escape(s, unreserved() + ":@!$'()*,"); }	// sub_delims - "&;+=" + ":@"
  	std::string escapeQueryValue(const std::string& s)
  		{ return LLURI::escape(s, unreserved() + ":@!$'()*,="); }	// sub_delims - "&;+" + ":@"
  	// </exodus>
  	std::string escapeUriQuery(const std::string& s)
  		{ return LLURI::escape(s, unreserved() + ":@?&$;*+=%/"); }
  	std::string escapeUriData(const std::string& s)
  		{ return LLURI::escape(s, unreserved() + "%"); }
  	std::string escapeUriPath(const std::string& s)
  		{ return LLURI::escape(s, path()); }
  }
  
  //static
  std::string LLURI::escape(const std::string& str)
  {
  	static std::string default_allowed = unreserved();
  	static bool initialized = false;
  	if(!initialized)
  	{
  		std::sort(default_allowed.begin(), default_allowed.end());
  		initialized = true;
  	}
  	return escape(str, default_allowed, true);
  }
  
  //static
  std::string LLURI::escapePathAndData(const std::string &str)
  {
      std::string result;
  
      const std::string data_marker = "data:";
      if (str.compare(0, data_marker.length(), data_marker) == 0)
      {
          // This is not url, but data, data part needs to be properly escaped
          // data part is separated by ',' from header. Minimal data uri is "data:,"
          // See "data URI scheme"
          size_t separator = str.find(',');
          if (separator != std::string::npos)
          {
              size_t header_size = separator + 1;
              std::string header = str.substr(0, header_size);
              // base64 is url-safe
              if (header.find("base64") != std::string::npos)
              {
                  // assume url-safe data
                  result = str;
              }
              else
              {
                  std::string data = str.substr(header_size, str.length() - header_size);
  
                  // Notes: File can be partially pre-escaped, that's why escaping ignores '%'
                  // It somewhat limits user from displaying strings like "%20" in text
                  // but that's how viewer worked for a while and user can double-escape it
  
  
                  // Header doesn't need escaping
                  result = header + escapeUriData(data);
              }
          }
      }
      else
      {
          // try processing it as path with query separator
          // The query component is indicated by the first question
          // mark("?") character and terminated by a number sign("#")
          size_t delim_pos = str.find('?');
          if (delim_pos == std::string::npos)
          {
              // alternate separator
              delim_pos = str.find(';');
          }
  
          if (delim_pos != std::string::npos)
          {
              size_t path_size = delim_pos + 1;
              std::string query;
              std::string fragment;
  
              size_t fragment_pos = str.find('#');
              if ((fragment_pos != std::string::npos) && (fragment_pos > delim_pos))
              {
                  query = str.substr(path_size, fragment_pos - path_size);
                  fragment = str.substr(fragment_pos);
              }
              else
              {
                  query = str.substr(path_size);
              }
  
              std::string path = str.substr(0, path_size);
  
              result = escapeUriPath(path) + escapeUriQuery(query) + escapeUriPath(fragment);
          }
      }
  
      if (result.empty())
      {
          // Not a known scheme or no data part, try just escaping as Uri path
          result = escapeUriPath(str);
      }
      return result;
  }
  
  //static
  std::string LLURI::escapeQueryValue(const std::string& s)
  {
  	return ::escapeQueryValue(s);
  }
  
  //static
  std::string LLURI::escapeQueryVariable(const std::string& s)
  {
  	return ::escapeQueryVariable(s);
  }
  
  LLURI::LLURI()
  {
  }
  
  LLURI::LLURI(const std::string& escaped_str)
  {
  	std::string::size_type delim_pos;
  	delim_pos = escaped_str.find(':');
  	std::string temp;
  	if (delim_pos == std::string::npos)
  	{
  		mScheme = "";
  		mEscapedOpaque = escaped_str;
  	}
  	else
  	{
  		mScheme = escaped_str.substr(0, delim_pos);
  		mEscapedOpaque = escaped_str.substr(delim_pos+1);
  	}
  
  	parseAuthorityAndPathUsingOpaque();
  
  	delim_pos = mEscapedPath.find('?');
  	if (delim_pos != std::string::npos)
  	{
  		mEscapedQuery = mEscapedPath.substr(delim_pos+1);
  		mEscapedPath = mEscapedPath.substr(0,delim_pos);
  	}
  }
  
  static BOOL isDefault(const std::string& scheme, U16 port)
  {
  	if (scheme == "http")
  		return port == 80;
  	if (scheme == "https")
  		return port == 443;
  	if (scheme == "ftp")
  		return port == 21;
  
  	return FALSE;
  }
  
  void LLURI::parseAuthorityAndPathUsingOpaque()
  {
  	if (mScheme == "http" || mScheme == "https" || mScheme == "hop" || 
  		mScheme == "ftp" || mScheme == "secondlife" || 
  		mScheme == "x-grid-location-info")
  	{
  		if (mEscapedOpaque.substr(0,2) != "//")
  		{
  			return;
  		}
  
  		std::string::size_type delim_pos, delim_pos2;
  		delim_pos = mEscapedOpaque.find('/', 2);
  		delim_pos2 = mEscapedOpaque.find('?', 2);
  		// no path, no query
  		if (delim_pos == std::string::npos &&
  			delim_pos2 == std::string::npos)
  		{
  			mEscapedAuthority = mEscapedOpaque.substr(2);
  			mEscapedPath = "";
  		}
  		// path exist, no query
  		else if (delim_pos2 == std::string::npos)
  		{
  			mEscapedAuthority = mEscapedOpaque.substr(2,delim_pos-2);
  			mEscapedPath = mEscapedOpaque.substr(delim_pos);
  		}
  		// no path, only query
  		else if (delim_pos == std::string::npos ||
  				 delim_pos2 < delim_pos)
  		{
  			mEscapedAuthority = mEscapedOpaque.substr(2,delim_pos2-2);
  			// query part will be broken out later
  			mEscapedPath = mEscapedOpaque.substr(delim_pos2);
  		}
  		// path and query
  		else
  		{
  			mEscapedAuthority = mEscapedOpaque.substr(2,delim_pos-2);
  			// query part will be broken out later
  			mEscapedPath = mEscapedOpaque.substr(delim_pos);
  		}
  	}
  	else if (mScheme == "about")
  	{
  		mEscapedPath = mEscapedOpaque;
  	}
  }
  
  LLURI::LLURI(const std::string& scheme,
  			 const std::string& userName,
  			 const std::string& password,
  			 const std::string& hostName,
  			 U16 port,
  			 const std::string& escapedPath,
  			 const std::string& escapedQuery)
  	: mScheme(scheme),
  	  mEscapedPath(escapedPath),
  	  mEscapedQuery(escapedQuery)
  {
  	std::ostringstream auth;
  	std::ostringstream opaque;
  
  	opaque << "//";
  	
  	if (!userName.empty())
  	{
  		auth << escape(userName);
  		if (!password.empty())
  		{
  			auth << ':' << escape(password);
  		}
  		auth << '@';
  	}
  	auth << hostName;
  	if (!isDefault(scheme, port))
  	{
  		auth << ':' << port;
  	}
  	mEscapedAuthority = auth.str();
  
  	opaque << mEscapedAuthority << escapedPath << escapedQuery;
  
  	mEscapedOpaque = opaque.str();
  }
  
  LLURI::~LLURI()
  {
  }
  
  // static
  LLURI LLURI::buildHTTP(const std::string& prefix,
  					   const LLSD& path)
  {
  	LLURI result;
  
  	// TODO: deal with '/' '?' '#' in host_port
  	if (prefix.find("://") != prefix.npos)
  	{
  		// it is a prefix
  		result = LLURI(prefix);
  	}
  	else
  	{
  		// it is just a host and optional port
  		result.mScheme = "http";
  		result.mEscapedAuthority = escapeHostAndPort(prefix);
  	}
  
  	if (path.isArray())
  	{
  		// break out and escape each path component
  		for (LLSD::array_const_iterator it = path.beginArray();
  			 it != path.endArray();
  			 ++it)
  		{
  			LL_DEBUGS() << "PATH: inserting " << it->asString() << LL_ENDL;
  			result.mEscapedPath += "/" + escapePathComponent(it->asString());
  		}
  	}
  	else if (path.isString())
  	{
  		std::string pathstr(path);
  		// Trailing slash is significant in HTTP land. If caller specified,
  		// make a point of preserving.
  		std::string last_slash;
  		std::string::size_type len(pathstr.length());
  		if (len && pathstr[len-1] == '/')
  		{
  			last_slash = "/";
  		}
  
  		// Escape every individual path component, recombining with slashes.
  		for (boost::split_iterator<std::string::const_iterator>
  				 ti(pathstr, boost::first_finder("/")), tend;
  			 ti != tend; ++ti)
  		{
  			// Eliminate a leading slash or duplicate slashes anywhere. (Extra
  			// slashes show up here as empty components.) This test also
  			// eliminates a trailing slash, hence last_slash above.
  			if (! ti->empty())
  			{
  				result.mEscapedPath
  					+= "/" + escapePathComponent(std::string(ti->begin(), ti->end()));
  			}
  		}
  
  		// Reinstate trailing slash, if any.
  		result.mEscapedPath += last_slash;
  	} 
  	else if(path.isUndefined())
  	{
  	  // do nothing
  	}
  	else
  	{
  	  LL_WARNS() << "Valid path arguments to buildHTTP are array, string, or undef, you passed type" 
  			  << path.type() << LL_ENDL;
  	}
  	result.mEscapedOpaque = "//" + result.mEscapedAuthority +
  		result.mEscapedPath;
  	return result;
  }
  
  // static
  LLURI LLURI::buildHTTP(const std::string& prefix,
  					   const LLSD& path,
  					   const LLSD& query)
  {
  	LLURI uri = buildHTTP(prefix, path);
  	// break out and escape each query component
  	uri.mEscapedQuery = mapToQueryString(query);
  	uri.mEscapedOpaque += uri.mEscapedQuery ;
  	uri.mEscapedQuery.erase(0,1); // trim the leading '?'
  	return uri;
  }
  
  // static
  LLURI LLURI::buildHTTP(const std::string& host,
  					   const U32& port,
  					   const LLSD& path)
  {
  	return LLURI::buildHTTP(llformat("%s:%u", host.c_str(), port), path);
  }
  
  // static
  LLURI LLURI::buildHTTP(const std::string& host,
  					   const U32& port,
  					   const LLSD& path,
  					   const LLSD& query)
  {
  	return LLURI::buildHTTP(llformat("%s:%u", host.c_str(), port), path, query);
  }
  
  std::string LLURI::asString() const
  {
  	if (mScheme.empty())
  	{
  		return mEscapedOpaque;
  	}
  	else
  	{
  		return mScheme + ":" + mEscapedOpaque;
  	}
  }
  
  std::string LLURI::scheme() const
  {
  	return mScheme;
  }
  
  std::string LLURI::opaque() const
  {
  	return unescape(mEscapedOpaque);
  }
  
  std::string LLURI::authority() const
  {
  	return unescape(mEscapedAuthority);
  }
  
  
  namespace {
  	void findAuthorityParts(const std::string& authority,
  							std::string& user,
  							std::string& host,
  							std::string& port)
  	{
  		std::string::size_type start_pos = authority.find('@');
  		if (start_pos == std::string::npos)
  		{
  			user = "";
  			start_pos = 0;
  		}
  		else
  		{
  			user = authority.substr(0, start_pos);
  			start_pos += 1;
  		}
  
  		std::string::size_type end_pos = authority.find(':', start_pos);
  		if (end_pos == std::string::npos)
  		{
  			host = authority.substr(start_pos);
  			port = "";
  		}
  		else
  		{
  			host = authority.substr(start_pos, end_pos - start_pos);
  			port = authority.substr(end_pos + 1);
  		}
  	}
  }
  	
  std::string LLURI::hostName() const
  {
  	std::string user, host, port;
  	findAuthorityParts(mEscapedAuthority, user, host, port);
  	return unescape(host);
  }
  
  // <AW: opensim>
  std::string LLURI::hostNameAndPort() const
  {
  	std::string user, host, port;
  	findAuthorityParts(mEscapedAuthority, user, host, port);
  	return port.empty() ? unescape(host) : unescape(host + ":" + port);
  }
  // </AW: opensim>
  
  std::string LLURI::userName() const
  {
  	std::string user, userPass, host, port;
  	findAuthorityParts(mEscapedAuthority, userPass, host, port);
  	std::string::size_type pos = userPass.find(':');
  	if (pos != std::string::npos)
  	{
  		user = userPass.substr(0, pos);
  	}
  	return unescape(user);
  }
  
  std::string LLURI::password() const
  {
  	std::string pass, userPass, host, port;
  	findAuthorityParts(mEscapedAuthority, userPass, host, port);
  	std::string::size_type pos = userPass.find(':');
  	if (pos != std::string::npos)
  	{
  		pass = userPass.substr(pos + 1);
  	}
  	return unescape(pass);
  }
  
  BOOL LLURI::defaultPort() const
  {
  	return isDefault(mScheme, hostPort());
  }
  
  U16 LLURI::hostPort() const
  {
  	std::string user, host, port;
  	findAuthorityParts(mEscapedAuthority, user, host, port);
  	if (port.empty())
  	{
  		if (mScheme == "http")
  			return 80;
  		if (mScheme == "https")
  			return 443;
  		if (mScheme == "ftp")
  			return 21;		
  		return 0;
  	}
  	return atoi(port.c_str());
  }	
  
  std::string LLURI::path() const
  {
  	return unescape(mEscapedPath);
  }
  
  LLSD LLURI::pathArray() const
  {
  	typedef boost::tokenizer<boost::char_separator<char> > tokenizer;
  	boost::char_separator<char> sep("/", "", boost::drop_empty_tokens);
  	tokenizer tokens(mEscapedPath, sep);
  	tokenizer::iterator it = tokens.begin();
  	tokenizer::iterator end = tokens.end();
  
  	LLSD params;
  	for ( ; it != end; ++it)
  	{
  		params.append(*it);
  	}
  	return params;
  }
  
  std::string LLURI::query() const
  {
  	return unescape(mEscapedQuery);
  }
  
  LLSD LLURI::queryMap() const
  {
  	return queryMap(mEscapedQuery);
  }
  
  // static
  LLSD LLURI::queryMap(std::string escaped_query_string)
  {
  	LL_DEBUGS() << "LLURI::queryMap query params: " << escaped_query_string << LL_ENDL;
  
  	LLSD result = LLSD::emptyArray();
  	while(!escaped_query_string.empty())
  	{
  		// get tuple first
  		std::string tuple;
  		std::string::size_type tuple_begin = escaped_query_string.find('&');
  		if (tuple_begin != std::string::npos)
  		{
  			tuple = escaped_query_string.substr(0, tuple_begin);
  			escaped_query_string = escaped_query_string.substr(tuple_begin+1);
  		}
  		else
  		{
  			tuple = escaped_query_string;
  			escaped_query_string = "";
  		}
  		if (tuple.empty()) continue;
  
  		// parse tuple
  		std::string::size_type key_end = tuple.find('=');
  		if (key_end != std::string::npos)
  		{
  			std::string key = unescape(tuple.substr(0,key_end));
  			std::string value = unescape(tuple.substr(key_end+1));
  			LL_DEBUGS() << "inserting key " << key << " value " << value << LL_ENDL;
  			result[key] = value;
  		}
  		else
  		{
  			LL_DEBUGS() << "inserting key " << unescape(tuple) << " value true" << LL_ENDL;
  		    result[unescape(tuple)] = true;
  		}
  	}
  	return result;
  }
  
  std::string LLURI::mapToQueryString(const LLSD& queryMap)
  {
  	std::string query_string;
  	if (queryMap.isMap())
  	{
  		bool first_element = true;
  		LLSD::map_const_iterator iter = queryMap.beginMap();
  		LLSD::map_const_iterator end = queryMap.endMap();
  		std::ostringstream ostr;
  		for (; iter != end; ++iter)
  		{
  			if(first_element)
  			{
  				ostr << "?";
  				first_element = false;
  			}
  			else
  			{
  				ostr << "&";
  			}
  			ostr << ::escapeQueryVariable(iter->first);
  			if(iter->second.isDefined())
  			{
  				ostr << "=" <<  ::escapeQueryValue(iter->second.asString());
  			}
  		}
  		query_string = ostr.str();
  	}
  	return query_string;
  }
  
  bool operator!=(const LLURI& first, const LLURI& second)
  {
  	return (first.asString() != second.asString());
  }
  