Еще одна реализация регистронезависимого поиска по кириллическим символам в SQLite / Хабр

Доброго времени суток, Хабровчане!

Проблема поиска по русским символам в SQLite давно уже стала притчей во языцех, причины ее появления довольно подробно описаны здесь. Впрочем, есть довольно распространенные решения данной проблемы, самым популярным из которых является подключение ICU, библиотеки, с помощью которой можно реализовать полноценный поиск по Unicode. Но мне хотелось более короткого в плане кода решения чтобы в результате поиск был:

регистронезависимым;
по русским и английским символам;
игнорирование символа ё/Ё при поиске;
быстрым;
использовал встроенный NOCASE collation.

В результате пришла идея поковыряться в исходном коде SQLite и несколько его поправить. Инструментарий был следующий: сборка System.Data.Sqlite в которую включен исходный код SQLite Amalgamation (где весь исходный код ядра хранится в одном файле), Visual Studio 2017 и тестовая база данных.

Для сравнения строк в ядре БД есть функция patternCompare. Как известно, она реализует nocase сравнение только для первых 128 символов UTF-8, на что есть соответствующие проверки в коде. Идеей было написать ещё небольшой блок кода, выполняющей проверку на то, является ли символ кириллическим. Если заглянуть в таблицу UTF-8, то для знакомых сердцу символов выделены позиции с 0x400 по 0x45F. Теперь создадим проверку на кириллический символ и таблицы перевода в верхний и нижний регистр. Немного кода.

#define IsCyrillic(A)(A >= 0x400 && A <= 0x45F)

static const unsigned short CyrillicUpper[128] =
{
	1024, 1045, 1026, 1027, 1028, 1029, 1030, 1031, 1032, 1033, 1034, 1035, 1036, 1037, 1038, 1039,
	1040, 1041, 1042, 1043, 1044, 1045, 1046, 1047, 1048, 1049, 1050, 1051, 1052, 1053, 1054, 1055,
	1056, 1057, 1058, 1059, 1060, 1061, 1062, 1063, 1064, 1065, 1066, 1067, 1068, 1069, 1070, 1071,
	1040, 1041, 1042, 1043, 1044, 1045, 1046, 1047, 1048, 1049, 1050, 1051, 1052, 1053, 1054, 1055,
	1056, 1057, 1058, 1059, 1060, 1061, 1062, 1063, 1064, 1065, 1066, 1067, 1068, 1069, 1070, 1071,
	1104, 1045, 1106, 1107, 1108, 1109, 1110, 1111, 1112, 1113, 1114, 1115, 1116, 1117, 1118, 1119,
	1120, 1121, 1122, 1123, 1124, 1125, 1126, 1127, 1128, 1129, 1130, 1131, 1132, 1133, 1134, 1135,
	1136, 1137, 1138, 1139, 1140, 1141, 1142, 1143, 1144, 1145, 1146, 1147, 1148, 1149, 1150, 1151
};

static const unsigned short CyrillicLower[128] =
{
	1024, 1177, 1026, 1027, 1028, 1029, 1030, 1031, 1032, 1033, 1034, 1035, 1036, 1037, 1038, 1039,
	1072, 1073, 1074, 1075, 1076, 1077, 1078, 1079, 1080, 1081, 1082, 1083, 1084, 1085, 1086, 1087,
	1088, 1089, 1090, 1091, 1092, 1093, 1094, 1095, 1096, 1097, 1098, 1099, 1100, 1101, 1102, 1103,
	1072, 1073, 1074, 1075, 1076, 1077, 1078, 1079, 1080, 1081, 1082, 1083, 1084, 1085, 1086, 1087,
	1088, 1089, 1090, 1091, 1092, 1093, 1094, 1095, 1096, 1097, 1098, 1099, 1100, 1101, 1102, 1103,
	1104, 1177, 1106, 1107, 1108, 1109, 1110, 1111, 1112, 1113, 1114, 1115, 1116, 1117, 1118, 1119,
	1120, 1121, 1122, 1123, 1124, 1125, 1126, 1127, 1128, 1129, 1130, 1131, 1132, 1133, 1134, 1135,
	1136, 1137, 1138, 1139, 1140, 1141, 1142, 1143, 1144, 1145, 1146, 1147, 1148, 1149, 1150, 1151
};

#define CyrillicToUpper(ch)(CyrillicUpper[(unsigned char)(ch&~0x400)])

#define CyrillicToLower(ch)(CyrillicLower[(unsigned char)(ch&~0x400)])

Дело за малым, посмотреть все проверки на то, что символ меньше 0x80 и добавить еще одну проверку на кирилличность. Это происходит в двух местах, при проверке первого символа и всех остальных. Не буду приводить всю функцию patternCompare, лишь эти два места (уже заботливо подправленные).

Первый блок кода:

      if( c<=0x80 ){
        u32 cx;
        int bMatch;
        if( noCase ){
          cx = sqlite3Toupper(c);
          c = sqlite3Tolower(c);
        }else{
          cx = c;
        }
        while( (c2 = *(zString++))!=0 ){
          if( c2!=c && c2!=cx ) continue;
          bMatch = patternCompare(zPattern,zString,pInfo,matchOther);
          if( bMatch!=SQLITE_NOMATCH ) return bMatch;
        }
      }	  
	  else if (noCase && IsCyrillic(c))
	  {
		  u32 cx;
		  int bMatch;
		  if (noCase) {
			  cx = CyrillicToUpper(c);
			  c = CyrillicToLower(c);
		  }
		  else {
			  cx = c;
		  }
		  while ((c2 = Utf8Read(zString)) != 0) {
			  if (c2 != c && c2 != cx) continue;
			  bMatch = patternCompare(zPattern, zString, pInfo, matchOther);
			  if (bMatch != SQLITE_NOMATCH) return bMatch;
		  }
	  }

Второй блок кода:

    if( noCase  && sqlite3Tolower(c)==sqlite3Tolower(c2) && c<0x80 && c2<0x80 ){
      continue;
    }
	if (noCase && CyrillicToLower(c) == CyrillicToLower(c2) && IsCyrillic(c) && IsCyrillic(c2)) {
		continue;
	}

Регистронезависимый поиск русского и английского текста теперь исправно работает для пэттерна WHERE LIKE '%xxx%' но не будет работать для WHERE LIKE 'xxx%', если поле индексировано стандартной NOCASE функцией. Так что если вы хотите, чтобы и индексированный поиск тоже работал, придется еще немного повозиться. Заглянем поглубже в код библиотеки и увидим, что за создание индекса c collation NOCASE отвечает функция sqlite3_strnicmp. Вообще, их две, одна с параметром, отвечающим за проверку длины текста, другая без. Нам нужная первая. Но вот только текст в ней, в отличие от patternCompare не декодируется из UTF-8, так что реализуем еще одну проверку на то, что первый байт является старшим для закодированного в UTF-8 кириллического символа, а также реализуем декодирование кириллического символа из UTF-8 с преобразованием его в нижний регистр.

static unsigned char IsCyrillcByte(unsigned char b)
{
	return !((b >> 1) ^ 0x68);
}

static unsigned short ReadLowerCyrillic(const unsigned char* in)
{
	unsigned char b1, b2;
	b1 = *in;
	in++;
	b2 = *in;

	return CyrillicLower[(unsigned char)(b1 << 6) | (b2 &~ 0x80)];
}

К сожалению, функцию sqlite3_strnicmp пришлось переписать, так как она была в значительной мере оптимизирована под ASCII, теперь она выглядит вот так:

SQLITE_API int sqlite3_strnicmp(const char *zLeft, const char *zRight, int N){
  register unsigned char *a, *b;
  unsigned short cLeft, cRight;
  if( zLeft==0 ){
    return zRight ? -1 : 0;
  }else if( zRight==0 ){
    return 1;
  }
  a = (unsigned char *)zLeft;
  b = (unsigned char *)zRight;
  for(;N > 0; N--)
  { 
	  if (*a <= 0x80 && *b <= 0x80)
	  {
		  if (*a != 0 && UpperToLower[*a] == UpperToLower[*b])
		  {
				a++; b++;
		  }
		  else
		  {
			  return UpperToLower[*a] - UpperToLower[*b];
		  }
	  }
	  else if (IsCyrillcByte(*a) && IsCyrillcByte(*b))
	  {
		   cLeft = ReadLowerCyrillic(a);
		   cRight = ReadLowerCyrillic(b);

		   if (cLeft == cRight)
		   {
			   a += 2; b += 2;
		   }
		   else
		   {
			   return cLeft - cRight;
		   }

	  }
	  else if (*a == *b)
	  {
		  a++; b++;
	  }
	  else
	  {
		  return *a - *b;
	  }
  }
  return 0;
}

Все, можно ~~поливать соусом и есть~~ компилировать. Также необходимо в конце выполнить простой запрос к БД REINDEX NOCASE; для пересоздания всех регистронезависимых индексов.