Borland string::find bug

Question

Я поддерживаю приложение C++, написанное с использованием Borland C++ Builder 5.02 (с 1997 года). Метод find() в классе строк Borland не ведет себя так, как я ожидал:

#include <cstring>
#include <iostream>

int main (int argc, char *argv[])
{
   string needle = "length == eighteen";
   string haystack = "<" + needle + ">";
   if (haystack.find(needle) != NPOS)
      cout << "Found it!" << endl;
   else
      cout << "Not found" << endl;

   return 0;
}

Эта программа выводит Not found, Если я поменяю иглу на что-то более короткое, она выдаст Found it!, Если я обменяю угловые скобки на некоторые другие символы, он находит это. Пробелы работают, но скобки тоже нет.

Обратите внимание, что я использую библиотеку строк Borland здесь: если я #include <string> и использовать std::string вместо этого он работает именно так, как я ожидал. К сожалению, изменение всего приложения для использования строк STL - неосуществимый ответ!

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

Мне очень трудно поверить, что это действительно ошибка в библиотеке строк, особенно потому, что если бы это было так, я бы ожидал, что смогу найти статью или что-то об этом. Я не могу найти такую ​​информацию.

Тем не менее, у меня закончились идеи! Это известная ошибка? Есть ли исправление?

РЕДАКТИРОВАТЬ: Посмотрев еще раз на разборки, я думаю, что он пытается сделать что-то вроде алгоритма Рабина-Карпа, где вычисляется хеш-функция мод 33554393 (наибольшее простое число < 2^25). Это может быть полиномиальная хеш-функция с основанием 32 (т.е. a_0 + 32 a_1 + 32^2 a_2 + .. + 32^n a_n), но это всего лишь догадка. Похоже на возможное переполнение, как предложил Даниэль Фишер.

Answer 1

Я нашел ссылку от 1998 года, в которой говорится, что реализация Borland поиска строк имеет ошибку:

https://groups.google.com/forum/?fromgroups=$20bug/borland.public.cpp.language/XBzjaJmCYpk/gtMPm-j8jugJ

Кроме того, похоже, что в какой-то момент истории комитет C++ решил, что строковый класс будет частью стандартного C++, а строковый класс cstring является остатком этого:

https://groups.google.com/forum/?fromgroups=$20cstring/borland.public.cpp.language/2psY2seRmS4/ywVrqwU1C2wJ

Answer 2

Если у вас есть оригинальный установочный диск BC++ 5.02, источник строкового класса находится в BC5\SOURCE\RTL\SOURCE\STRING.

Вот выдержка из кода функции string::find_case_index() (вызываемой string::find()):

const long q = 33554393L;
const long q32 = q<<5;

size_t testlength = length() - startindex;
size_t patternlength = patl = strlen(cp);
if( testlength < patternlength )
    return NPOS;
if( patternlength == 0 )
    return 0;

long patternHash = 0;
long testHash = 0;

const char _FAR *testP = c_str()+startindex;
const char _FAR *patP = cp;
long x = 1;
size_t i = patternlength-1;

while( i-- )
    x = (x<<5)%q;

for( i=0; i<patternlength; i++ )
    {
    patternHash = ( (patternHash<<5) + *patP++  ) % q;
    testHash    = ( (testHash   <<5) + *testP++ ) % q;
    }

testP = c_str()+startindex;
const char _FAR *end = testP + testlength - patternlength;

while (1)
    {

    if(testHash == patternHash)
        if( !get_paranoid_check_flag() ||
            !strncmp( testP, cp, patternlength) )
          return (size_t)(testP-c_str());

    if( testP >= end )
        break;

    // Advance & calculate the new hash value:
    testHash = ( testHash + q32 - *testP * x                 ) % q;
    testHash = ( (testHash<<5)  + *(patternlength + testP++) ) % q;
    }
return NPOS;          // Not found.

Answer 3

Вы не используете библиотеку строк Borland. String (заглавная S) - класс строк Borland. string (строчные буквы s), что точно так же, как std::string, является классом строки STL, который НЕ является реализацией Borland (STL в BCB5 был RogueWave STL). Ваше использование #include <cstring> вероятно приносит std::string в глобальное пространство имен, поэтому ваш код компилируется. Но вы действительно должны использовать #include <string> а также std::string вместо. Что касается NPOS, вы должны использовать string::npos вместо этого, поскольку это то, что string::find() на самом деле возвращается.

#include <cstring>
#include <iostream>

int main (int argc, char *argv[])
{
   string needle = "length == eighteen";
   string haystack = "<" + needle + ">";
   if (haystack.find(needle) != string::npos)
      cout << "Found it!" << endl;
   else
      cout << "Not found" << endl;

   return 0;
}

Или же:

#include <string>
#include <iostream>

int main (int argc, char *argv[])
{
   std::string needle = "length == eighteen";
   std::string haystack = "<" + needle + ">";
   if (haystack.find(needle) != std::string::npos)
      std::cout << "Found it!" << std::endl;
   else
      std::cout << "Not found" << std::endl;

   return 0;
}