Самый эффективный способ избежать XML/HTML в С++-строке?

Я не могу поверить, что этот вопрос не задавался раньше. У меня есть строка, которая должна быть вставлена в файл HTML, но может содержать специальные символы HTML. Я хочу заменить их соответствующим представлением HTML.

Код ниже работает, но довольно подробный и уродливый. Производительность не имеет решающего значения для моего приложения, но я думаю, что здесь есть проблемы с масштабируемостью. Как я могу улучшить это? Я предполагаю, что это работа для алгоритмов STL или некоторая эзотерическая функция Boost, но приведенный ниже код - лучшее, что я могу придумать сам.

void escape(std::string *data)
{
    std::string::size_type pos = 0;
    for (;;)
    {
        pos = data->find_first_of("\"&<>", pos);
        if (pos == std::string::npos) break;
        std::string replacement;
        switch ((*data)[pos])
        {
        case '\"': replacement = "&quot;"; break;   
        case '&':  replacement = "&amp;";  break;   
        case '<':  replacement = "&lt;";   break;   
        case '>':  replacement = "&gt;";   break;   
        default: ;
        }
        data->replace(pos, 1, replacement);
        pos += replacement.size();
    };
}

Ответ 1

Вместо того, чтобы просто заменять исходную строку, вы можете выполнять копирование с заменой "на лету", которая позволяет избежать перемещения символов в строке. Это будет иметь намного лучшую сложность и поведение кэша, поэтому я ожидаю огромного улучшения. Или вы можете использовать boost:: spirit:: xml encode или http://code.google.com/p/pugixml/.

void encode(std::string& data) {
    std::string buffer;
    buffer.reserve(data.size());
    for(size_t pos = 0; pos != data.size(); ++pos) {
        switch(data[pos]) {
            case '&':  buffer.append("&amp;");       break;
            case '\"': buffer.append("&quot;");      break;
            case '\'': buffer.append("&apos;");      break;
            case '<':  buffer.append("&lt;");        break;
            case '>':  buffer.append("&gt;");        break;
            default:   buffer.append(&data[pos], 1); break;
        }
    }
    data.swap(buffer);
}

EDIT: Небольшое улучшение может быть достигнуто с помощью эвристики для определения размера буфера. Замените строку buffer.reserve на data.size()*1.1 (10%) или что-то подобное в зависимости от того, сколько ожидается замена.

Ответ 2

void escape(std::string *data)
{
    using boost::algorithm::replace_all;
    replace_all(*data, "&",  "&amp;");
    replace_all(*data, "\"", "&quot;");
    replace_all(*data, "\'", "&apos;");
    replace_all(*data, "<",  "&lt;");
    replace_all(*data, ">",  "&gt;");
}

Может ли выиграть приз за наименьшее количество слов?

Ответ 3

Я бы честно пошел с более общей версией, используя итераторы, чтобы вы могли "потопить" кодировку. Рассмотрим следующую реализацию:

#include <algorithm>

namespace xml {

    // Helper for null-terminated ASCII strings (no end of string iterator).
    template<typename InIter, typename OutIter>
    OutIter copy_asciiz ( InIter begin, OutIter out )
    {
        while ( *begin != '\0' ) {
            *out++ = *begin++;
        }
        return (out);
    }

    // XML escaping in it general form.  Note that 'out' is expected
    // to an "infinite" sequence.
    template<typename InIter, typename OutIter>
    OutIter escape ( InIter begin, InIter end, OutIter out )
    {
        static const char bad[] = "&<>";
        static const char* rep[] = {"&amp;", "&lt;", "&gt;"};
        static const std::size_t n = sizeof(bad)/sizeof(bad[0]);

        for ( ; (begin != end); ++begin )
        {
            // Find which replacement to use.
            const std::size_t i =
                std::distance(bad, std::find(bad, bad+n, *begin));

            // No need for escaping.
            if ( i == n ) {
                *out++ = *begin;
            }
            // Escape the character.
            else {
                out = copy_asciiz(rep[i], out);
            }
        }
        return (out);
    }

}

Затем вы можете упростить средний случай, используя несколько перегрузок:

#include <iterator>
#include <string>

namespace xml {

    // Get escaped version of "content".
    std::string escape ( const std::string& content )
    {
        std::string result;
        result.reserve(content.size());
        escape(content.begin(), content.end(), std::back_inserter(result));
        return (result);
    }

    // Escape data on the fly, using "constant" memory.
    void escape ( std::istream& in, std::ostream& out )
    {
        escape(std::istreambuf_iterator<char>(in),
            std::istreambuf_iterator<char>(),
            std::ostreambuf_iterator<char>(out));
    }

}

Наконец, проверьте всю партию:

#include <iostream>

int main ( int, char ** )
{
    std::cout << xml::escape("<foo>bar & qux</foo>") << std::endl;
}

Ответ 4

Вот простая ~ 30-строчная программа C, которая делает трюк довольно неплохо. Здесь я предполагаю, что temp_str будет выделять достаточную память, чтобы иметь дополнительные экранированные символы.

void toExpatEscape(char *temp_str)
{
    const char cEscapeChars[6]={'&','\'','\"','>','<','\0'};
    const char * const pEscapedSeqTable[] =
    {
        "&amp;",
        "&apos;",
        "&quot;",
        "&gt;",
        "&lt;",
    };
    unsigned int i, j, k, nRef = 0, nEscapeCharsLen = strlen(cEscapeChars), str_len = strlen(temp_str);
    int nShifts = 0; 

    for (i=0; i<str_len; i++)
    {
        for(nRef=0; nRef<nEscapeCharsLen; nRef++)
        {
            if(temp_str[i] == cEscapeChars[nRef])
            {
                if((nShifts = strlen(pEscapedSeqTable[nRef]) - 1) > 0)
                {
                    memmove(temp_str+i+nShifts, temp_str+i, str_len-i+nShifts); 
                    for(j=i,k=0; j<=i+nShifts,k<=nShifts; j++,k++)
                        temp_str[j] = pEscapedSeqTable[nRef][k];
                    str_len += nShifts;
                }
            }
        }  
    }
    temp_str[str_len] = '\0';
}

Ответ 5

Мои тесты показали, что этот ответ дал наилучшую производительность из предложенных (не удивительно, что он имеет наибольшую ставку).
Я реализовал такой же алгоритм для своего проекта (я действительно хочу иметь хорошую производительность и использование памяти) - мои тесты показали, что моя реализация имеет скорость ~ 2.6-3.25. Также мне не нравится предыдущий наилучший предложенный алгоритм bcs из-за плохого использования памяти - у вас будет дополнительное использование памяти, например, при применении множителя 1,1 эвристики, как когда .append() приведет к изменению размера.
Итак, оставьте мой код здесь - может быть, кто-нибудь найдет его полезным.

HtmlPreprocess.h:

#ifndef _HTML_PREPROCESS_H_
#define _HTML_PREPROCESS_H_

#include <string>

class HtmlPreprocess
{
public:
    HtmlPreprocess();
    ~HtmlPreprocess();

    static void htmlspecialchars(
        const std::string & in,
        std::string & out
        );
};

#endif // _HTML_PREPROCESS_H_

HtmlPreprocess.cpp:

#include "HtmlPreprocess.h"


HtmlPreprocess::HtmlPreprocess()
{
}


HtmlPreprocess::~HtmlPreprocess()
{
}


const unsigned char map_char_to_final_size[] = 
{
   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,
   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,
   1,   1,   6,   1,   1,   1,   5,   6,   1,   1,   1,   1,   1,   1,   1,   1,
   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   4,   1,   4,   1,
   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,
   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,
   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,
   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,
   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,
   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,
   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,
   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,
   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,
   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,
   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,
   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1
};


const unsigned char map_char_to_index[] = 
{
   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,
   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,
   0xFF,   0xFF,   2,      0xFF,   0xFF,   0xFF,   0,      1,      0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,
   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   4,      0xFF,   3,      0xFF,
   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,
   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,
   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,
   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,
   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,
   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,
   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,
   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,
   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,
   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,
   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,
   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF,   0xFF
};


void HtmlPreprocess::htmlspecialchars(
    const std::string & in,
    std::string & out
    )
{
    const char * lp_in_stored = &in[0];
    size_t in_size = in.size();

    const char * lp_in = lp_in_stored;
    size_t final_size = 0;
    for (size_t i = 0; i < in_size; i++)
        final_size += map_char_to_final_size[*lp_in++];

    out.resize(final_size);

    lp_in = lp_in_stored;
    char * lp_out = &out[0];

    for (size_t i = 0; i < in_size; i++)
    {
        char current_char = *lp_in++;
        unsigned char next_action = map_char_to_index[current_char];

        switch (next_action){
        case 0:
            *lp_out++ = '&';
            *lp_out++ = 'a';
            *lp_out++ = 'm';
            *lp_out++ = 'p';
            *lp_out++ = ';';
            break;
        case 1:
            *lp_out++ = '&';
            *lp_out++ = 'a';
            *lp_out++ = 'p';
            *lp_out++ = 'o';
            *lp_out++ = 's';
            *lp_out++ = ';';
            break;
        case 2:
            *lp_out++ = '&';
            *lp_out++ = 'q';
            *lp_out++ = 'u';
            *lp_out++ = 'o';
            *lp_out++ = 't';
            *lp_out++ = ';';
            break;
        case 3:
            *lp_out++ = '&';
            *lp_out++ = 'g';
            *lp_out++ = 't';
            *lp_out++ = ';';
            break;
        case 4:
            *lp_out++ = '&';
            *lp_out++ = 'l';
            *lp_out++ = 't';
            *lp_out++ = ';';
            break;
        default:
            *lp_out++ = current_char;
        }
    }
}

Ответ 6

Если вы собираетесь обрабатывать скорость, то мне кажется, что лучше всего будет иметь вторую строку, которую вы создаете по ходу, копируя из первой строки во вторую строку, а затем добавляя html escape-последовательности как вы их встретите. Поскольку я предполагаю, что метод replace сначала включает перемещение памяти, а затем копию в замещенную позицию, для больших строк это будет очень медленным. Если у вас есть вторая строка для построения с использованием .append(), это позволит избежать перемещения памяти.

Насколько это было "чистотой" кода, я думаю, что так же красиво, как вы собираетесь. Вы можете создать массив символов и их замен, а затем выполнить поиск в массиве, но это, вероятно, будет медленнее и не намного чище.

Ответ 7

Вы можете использовать boost::property_tree::xml_parser::encode_char_entities, если вы не хотите писать его самостоятельно.

Для справки, здесь код в boost 1.64.0:

`` `

template<class Str>
Str encode_char_entities(const Str &s)
{
    // Don't do anything for empty strings.
    if(s.empty()) return s;

    typedef typename Str::value_type Ch;

    Str r;
    // To properly round-trip spaces and not uglify the XML beyond
    // recognition, we have to encode them IF the text contains only spaces.
    Str sp(1, Ch(' '));
    if(s.find_first_not_of(sp) == Str::npos) {
        // The first will suffice.
        r = detail::widen<Str>("&#32;");
        r += Str(s.size() - 1, Ch(' '));
    } else {
        typename Str::const_iterator end = s.end();
        for (typename Str::const_iterator it = s.begin(); it != end; ++it)
        {
            switch (*it)
            {
                case Ch('<'): r += detail::widen<Str>("&lt;"); break;
                case Ch('>'): r += detail::widen<Str>("&gt;"); break;
                case Ch('&'): r += detail::widen<Str>("&amp;"); break;
                case Ch('"'): r += detail::widen<Str>("&quot;"); break;
                case Ch('\''): r += detail::widen<Str>("&apos;"); break;
                default: r += *it; break;
            }
        }
    }
    return r;
}

`` `

Ответ 8

Я профилировал 3 решения с Visual Studio 2017. Входные данные составляли 10 000 000 строк размером 5-20 с вероятностью 9,4%, чтобы избежать char.

Решение от Джованни Фуншала
Решение HostageBrain
Решение - мое.

Результат:

требуется 1.675 секунд
требуется 0,769 секунд.
требуется 0.368 секунд

В моем решении окончательный размер предварительно вычисляется и копия строковых данных выполняется только тогда, когда это необходимо. Поэтому распределения памяти кучи должны быть минимальными.

const unsigned char calcFinalSize[] =
{
1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,
1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,
1,   1,   6,   1,   1,   1,   5,   6,   1,   1,   1,   1,   1,   1,   1,   1,
1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   4,   1,   4,   1,
1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,
1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,
1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,
1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,
1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,
1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,
1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,
1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,
1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,
1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,
1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,
1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1,   1
};

void escapeXml(std::string & in)
{
    const char* dataIn = in.data();
    size_t sizeIn = in.size();

    const char* dataInCurrent = dataIn;
    const char* dataInEnd = dataIn + sizeIn;
    size_t outSize = 0;
    while (dataInCurrent < dataInEnd)
    {
        outSize += calcFinalSize[static_cast<uint8_t>(*dataInCurrent)];
        dataInCurrent++;
    }


    if (outSize == sizeIn)
    {
        return;
    }
    std::string out;
    out.resize(outSize);

    dataInCurrent = dataIn;
    char* dataOut = &out[0];
    while (dataInCurrent < dataInEnd)
    {
        switch (*dataInCurrent) {
        case '&':
            memcpy(dataOut, "&amp;", sizeof("&amp;") - 1);
            dataOut += sizeof("&amp;") - 1;
            break;
        case '\'':
            memcpy(dataOut, "&apos;", sizeof("&apos;") - 1);
            dataOut += sizeof("&apos;") - 1;
            break;
        case '\"':
            memcpy(dataOut, "&quote;", sizeof("&quote;") - 1);
            dataOut += sizeof("&quote;") - 1;
            break;
        case '>':
            memcpy(dataOut, "&gt;", sizeof("&gt;") - 1);
            dataOut += sizeof("&gt;") - 1;
            break;
        case '<':
            memcpy(dataOut, "&lt;", sizeof("&lt;") - 1);
            dataOut += sizeof("&lt;") - 1;
            break;
        default:
            *dataOut++ = *dataInCurrent;
        }
        dataInCurrent++;
    }
    in.swap(out);
}

Ответ 9

Или с помощью только stl:

 std::string& rep(std::string &s, std::string from, std::string to)
    {
      int pos = -1;
      while ( (pos = s.find(from, pos+1) ) != string::npos)
        s.erase(pos, from.length()).insert(pos, to);

      return s;
    }

Использование:

rep(s, "&", "&quot;");
rep(s, "\"", "&quot;");

или

rep(s, "HTML","xxxx");