WebStrings.cc

Go to the documentation of this file.

/*
 * Copyright 2006-2009 Savarese Software Research Corporation
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     https://www.savarese.com/software/ApacheLicense-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
#include <unordered_map>
#include <algorithm>
#include <cstring>
#include <boost/algorithm/string/case_conv.hpp>
#include <boost/algorithm/string/trim.hpp>
#include <boost/regex.hpp>

#include <ssrc/wispers/utility/WebStrings.h>

// Note: we perform two passes on input, calculating the size of the
// destination buffer on the first pass and performing the
// substitutions on the second pass.  We could do this in one pass, by
// appending to a dynamic buffer or storing references to ranges of
// the input that do not have to be altered (followed by a loop over
// the ranges, writing to the output).  However, the alternatives
// would require O(N) dynamic memory allocations (either to resize the
// buffer or to record a new range), where N is the number of
// substitutions required by the input.  We assume that with today's
// large memory caches (and given that our input will almost always be
// far less than 1 MB), it is cheaper for us to do two passes (the
// first pass loads the data into the cache) and a single memory
// allocation with individual character copies than one pass with N
// memory allocations (possibly followed by a second loop to write the
// output) and N memcpy's (even though the memcpy's will be faster than
// our individual-character-copying loop).
//
// Also note that we could genercize the algorithms to share code
// between them, using functors to specialize the behavior.  We
// choose not to do so for expediency of implementation.  It
// takes more time to figure out how to properly genericize the
// code than it does to implement the utility functions independently.
//
// Regardless, performance optimizations and design refinements can
// always be made in the future.  Functionality comes first.

namespace {
  // TODO: optimize patterns.
  const boost::regex html_strip_pattern("<!--.*?-->|<[^>]*>");
  const boost::regex html_strip_amp_pattern("<!--.*?-->|<[^>]*>|&[^#&;\\d\\s<>]+;|&#\\d+;|&#[xX][a-fA-F\\d]+;");

  // begin html_title_and_body support
  const boost::regex html_title_begin("<title[^>]*>",
                                      boost::regex_constants::normal |
                                      boost::regex_constants::icase);
  const boost::regex html_title_end("</title>",
                                      boost::regex_constants::normal |
                                      boost::regex_constants::icase);
  const boost::regex html_body_begin("<body[^>]*>",
                                     boost::regex_constants::normal |
                                     boost::regex_constants::icase);
  const boost::regex html_body_end("</body>",
                                   boost::regex_constants::normal |
                                   boost::regex_constants::icase);
  // end html_title_and_body support

  const char hex_char[] = {
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
    'a', 'b', 'c', 'd', 'e', 'f'
  };

  // Sorted array of characters that are either reserved according to
  // RFC 1738 or "unsafe". 
  // This array is pre-sorted so that we can search it via a binary search.
  const char url_reserved_char[] = {
    ' ', '"', '#', '$', '%', '&', '\'', '+', ',', '/', ':', ';', '<', '=', '>',
    '?', '@', '[', '\\', ']', '^', '`', '{', '|', '}', '~'
  };

  // This array is pre-sorted so that we can search it via a binary search.
  // For such a small number of items, linear search or
  // compiler-optimized switch statement may be faster!
  const char html_escape_char[] = {
    '"', '&', '\'', '<', '>'
  };

  const char html_quot[]  = { '&', 'q', 'u', 'o', 't', ';' };
  const char html_amp[]   = { '&', 'a', 'm', 'p', ';' };
  const char html_apost[] = { '&', '#', '3', '9', ';' };
  const char html_lt[]    = { '&', 'l', 't', ';' };
  const char html_gt[]    = { '&', 'g', 't', ';' };

  struct HTMLEscapeInfo {
    const char *escape_str;
    const unsigned int size;
  };

  const HTMLEscapeInfo html_escape_info[] = {
    { 0, 1 },
    { html_quot, sizeof(html_quot) },
    { html_amp, sizeof(html_amp) },
    { html_apost, sizeof(html_apost) },
    { html_lt, sizeof(html_lt) },
    { html_gt, sizeof(html_gt) }
  };

  struct HTMLEntity {
    const char * const entity;
    const unsigned char value;
  };

  const HTMLEntity html_entity[] = {
    { "agrave", 0xe0 },
    { "aacute", 0xe1 },
    { "acirc", 0xe2 },
    { "atilde", 0xe3 },
    { "auml", 0xe4 },
    { "aring", 0xe5 },
    { "aelig", 0xe6 },
    { "amp", '&' },
    { "ccedil", 0xe7 },
    { "copy", 0xa9 },
    { "egrave", 0xe8 },
    { "eacute", 0xe9 },
    { "ecirc", 0xea },
    { "euml", 0xeb },
    { "eth", 0xf0 },
    { "igrave", 0xec },
    { "iacute", 0xed },
    { "icirc", 0xee },
    { "iuml", 0xef },
    { "gt", '>' },
    { "lt", '<' },
    { "ntilde", 0xf1 },
    { "nbsp", ' ' },
    { "ograve", 0xf2 },
    { "oacute", 0xf3 },
    { "ocirc", 0xf4 },
    { "otilde", 0xf5 },
    { "ouml", 0xf6 },
    { "oslash", 0xf8 },
    { "quot", '"' },
    { "szlig", 0xdf },
    { "thorn", 0xfe },
    { "ugrave", 0xf9 },
    { "uacute", 0xfa },
    { "ucirc", 0xfb },
    { "uuml", 0xfc },
    { "yacute", 0xfd }
  };

  const unsigned int html_entity_size = sizeof(html_entity)/sizeof(HTMLEntity);

  class HTMLEntityMap {
    typedef std::unordered_map<std::string, const unsigned char> map_type;
    map_type _map;

  public:

    HTMLEntityMap() {
      for(unsigned int i = 0; i < html_entity_size; ++i) {
        _map.insert(map_type::value_type(html_entity[i].entity,
                                         html_entity[i].value));
      }
    }

    unsigned char get(const std::string & key) const {
      map_type::const_iterator it = _map.find(key);

      return (it == _map.end() ? 0 : it->second);
    }
  };

  const HTMLEntityMap html_entity_map;

  inline bool is_reserved_url_char(const char c) {
    return
      (c < 32 || c > 122 ||
       std::binary_search(&url_reserved_char[0],
                          &url_reserved_char[sizeof(url_reserved_char)], c));
  }

  inline unsigned int html_escape_char_size(const char c) {
    switch(c) {
    case '"' : return sizeof(html_quot);
    case '&' : return sizeof(html_amp);
    case '\'': return sizeof(html_apost);
    case '<' : return sizeof(html_lt);
    case '>' : return sizeof(html_gt);
    default  : return 1;
    };
  }

  inline unsigned int html_escape_char_index(const char c) {
    switch(c) {
    case '"' : return 1;
    case '&' : return 2;
    case '\'': return 3;
    case '<' : return 4;
    case '>' : return 5;
    default  : return 0;
    };
  }

  /*
  inline bool is_html_escape_char(const char c) {
    return (html_escape_char_size(c) > 1);
  }

  inline bool is_html_escape_char(const char c) {
    return std::binary_search(&html_escape_char[0],
                              &html_escape_char[sizeof(html_escape_char)], c);
  }
  */

  inline char * escape_javascript_char(char *dest, const char c) {
    *dest++ = '\\';
    *dest++ = 'x';
    *dest++ = hex_char[((c >> 4) & 0x0f)];
    *dest++ = hex_char[(c & 0x0f)];
    return dest;
  }

  inline char * escape_url_char(char *dest, const char c) {
    *dest++ = '%';
    *dest++ = hex_char[((c >> 4) & 0x0f)];
    *dest++ = hex_char[(c & 0x0f)];
    return dest;
  }

  inline unsigned int _escaped_javascript_size(const char *src,
                                               const unsigned int src_size)
  {
    unsigned int pos = 0, escaped_size = 0;

    while(*src && pos++ < src_size) {
      if(*src >= 32) {
        switch(*src) {
        case '"':
        case '&':
        case '\'':
        case '/':
        case ';':
        case '<':
        case '>':
        case '\\': escaped_size+=4; break;
        default: ++escaped_size; break;
        };
      } else {
        escaped_size+=4;
      }

      ++src;
    }

    return escaped_size;
  }

  inline void _escape_javascript(char *dest, const char *src,
                                 const unsigned int src_size)
  {
    unsigned int pos = 0;

    while(*src && pos++ < src_size) {
      if(*src >= 32) {
        switch(*src) {
        case '"':
        case '&':
        case '\'':
        case '/':
        case ';':
        case '<':
        case '>':
        case '\\': dest = escape_javascript_char(dest, *src); break;
        default: *dest++ = *src; break;
        };
      } else {
        dest = escape_javascript_char(dest, *src);
      }

      ++src;
    }
  }


  inline unsigned int _escaped_html_size(const char *src,
                                         const unsigned int src_size)
  {
    unsigned int pos = 0, escaped_size = 0;

    while(*src && pos++ < src_size) {
      escaped_size+=html_escape_char_size(*src);
      ++src;
    }

    return escaped_size;
  }

  inline void _escape_html(char *dest, const char *src,
                           const unsigned int src_size)
  {
    unsigned int pos = 0;

    while(*src && pos++ < src_size) {
      const unsigned int index = html_escape_char_index(*src);

      if(index == 0) {
        *dest++ = *src;
      } else {
        const HTMLEscapeInfo & info = html_escape_info[index];
        std::memcpy(dest, info.escape_str, info.size);
        dest+=info.size;
      }

      ++src;
    }
  }

  inline unsigned int _escaped_url_size(const char *src,
                                        const unsigned int src_size)
  {
    unsigned int pos = 0, escaped_size = 0;

    while(*src && pos++ < src_size) {
      escaped_size += (is_reserved_url_char(*src++) ? 3 : 1);
    }

    return escaped_size;
  }

  inline void _escape_url(char *dest, const char *src,
                          const unsigned int src_size)
  {
    unsigned int pos = 0;

    while(*src && pos++ < src_size) {
      if(is_reserved_url_char(*src)) {
        dest = escape_url_char(dest, *src);
      } else {
        *dest++ = *src;
      }
      ++src;
    }
  }

  inline char * unescape_char_entity(char *dest, const char *src,
                                     const unsigned int src_size)
  {
    const char * const begin = src + 1;
    long value = 0;

    // We can't place a temporary null guard in src because it may
    // be a read-only memory-mapped region.  We trust strtol to end
    // when it encounters the terminating colon.
    if(*begin == '#') {
      if(std::tolower(*(begin + 1)) == 'x') {
        value = strtol(begin + 2, 0, 16);
      } else {
        value = strtol(begin + 1, 0, 10);
      }
    } else {
      std::string key(begin, src_size - 2);
      boost::to_lower(key);
      value = html_entity_map.get(key);
    }

    if(value > 0 && value < 256) {
      *dest = value;
      return (dest + 1);
    }

    return dest;
  }
}

__BEGIN_NS_SSRC_WSPR_UTILITY

/*
 * Escapes characters in text that could result in executing
 * JavaScript code when passed to a JavaScript interpreter.
 * In addition, all leading and trailing whitespace is removed.
 *
 * @param result Buffer in which to store escaped text.  The
 *        string will be resized to hold the text.
 * @param text The text to be escaped.
 * @param text_size The length of the unescaped text.
 */
void escape_javascript(string & result, const char *text,
                       const unsigned int text_size)
{
  result.resize(_escaped_javascript_size(text, text_size));
  _escape_javascript(&result[0], text, text_size);
  boost::algorithm::trim(result);
}

void escape_html(string & result, const char *text,
                 const unsigned int text_size)
{
  result.resize(_escaped_html_size(text, text_size));
  _escape_html(&result[0], text, text_size);
  boost::algorithm::trim(result);
}

void escape_url(string & result, const char *text,
                const unsigned int text_size)
{
  result.resize(_escaped_url_size(text, text_size));
  _escape_url(&result[0], text, text_size);
}

void unescape_url(string & url) {
  char d0, d1;
  string::iterator it = url.begin(), end = url.end(), next = it;

  for(;next != end; ++it, ++next) {
    if(*next == '+') {
      *it = ' ';
    } else if(*next == '%' && (end - next) > 2
              && std::isxdigit((d0 = *(next + 1)))
              && std::isxdigit((d1 = *(next + 2))))
    {
#define FROM_HEX(c) (((c) >= 'A') ? (((c) & 0xdf) - 'A' + 10) : ((c) - '0'))
      char num = FROM_HEX(d0);
      num*=16;
      num+=FROM_HEX(d1);
#undef FROM_HEX
      *it = num;
      next+=2;
    } else if(it != next) {
      *it = *next;
    }
  }

  if(it != next) {
    url.resize(it - url.begin());
  }
}

void strip_html(string & result, const char *text,
                const unsigned int text_size)

{
  const boost::cregex_iterator end;
  boost::cregex_iterator it(text, text + text_size, html_strip_pattern);
  const char *src = text;

  result.resize(text_size, ' ');

  char *dest = &result[0];

  while(it != end) {
    const boost::cregex_iterator::reference m = *it;
    const boost::cregex_iterator::difference_type size = m[0].first - src;

    if(size > 0) {
      std::memcpy(dest, src, size);
      dest+=size;
    }

    src = m[0].second;
    ++it;
  }

  const int tail_size = text_size - (src - text);
  if(tail_size > 0) {
    std::memcpy(dest, src, tail_size);
  }

  boost::algorithm::trim(result);
}

void strip_html_and_unescape(string & result, const char *text,
                             const unsigned int text_size)
{
  const boost::cregex_iterator end;
  boost::cregex_iterator it(text, text + text_size, html_strip_amp_pattern);
  const char *src = text;

  result.resize(text_size, ' ');

  char *dest = &result[0];

  while(it != end) {
    const boost::cregex_iterator::reference m = *it;
    const char *first = m[0].first;
    const boost::cregex_iterator::difference_type size = first - src;

    if(size > 0) {
      std::memcpy(dest, src, size);
      dest+=size;
    }

    if(*first == '&') {
      dest = unescape_char_entity(dest, first, m[0].length());
    }

    src = m[0].second;
    ++it;
  }

  const int tail_size = text_size - (src - text);
  if(tail_size > 0) {
    std::memcpy(dest, src, tail_size);
  }

  boost::algorithm::trim(result);
}

void wrap_lines(char *text, const unsigned int text_size,
                const unsigned int max_length)
{
  char * const end = text + text_size;
  char * pos = text;
  unsigned int length = 0;

  while(pos < end) {
    pos = std::strchr(text, '\n');

    if(pos == 0) {
      pos = end;
    }

    length = pos - text;

    if(length > max_length) {
      char *s = 0;
      length = 0;
      for(char *p = text; p < pos; ++p) {
        if(*p == ' ' || *p == '\n') {
          s = p;
        }
        if(++length > max_length) {
          if(s != 0) {
            *s = '\n';
            length = (p - s);
            s = 0;
          }
        }
      }
    }

    text = pos + 1;
  }
}

title_body_type html_title_and_body(const char *begin, const char *end) {
  title_body_type result(static_cast<const char *>(0), 0,
                         static_cast<const char *>(0), 0);
  boost::cmatch match;

  if(boost::regex_search(begin, end, match, html_title_begin)) {
    std::get<0>(result) = match[0].second;
    if(boost::regex_search(match[0].second, end, match, html_title_end)) {
      std::get<1>(result) = match[0].first - std::get<0>(result);;
    }
  }

  if(boost::regex_search((std::get<1>(result) == 0 ? begin :
                          std::get<0>(result) + std::get<1>(result)),
                         end, match, html_body_begin))
  {
    std::get<2>(result) = match[0].second;
    if(boost::regex_search(std::get<2>(result), end, match, html_body_end)) {
      std::get<3>(result) = match[0].first - std::get<2>(result);
    }
  }

  return result;
}

__END_NS_SSRC_WSPR_UTILITY