Внимание, подводный камень

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

Задача

Дан список строк: VALID_STRINGS.
Cоздать функцию test(x) которая должна вернуть true, если x — это одна из строк в этом массиве.

Решение №1: Решение в лоб

Самым простым решением, которое может быть — это пройтись по всем строкам в этом массиве и сравнить.

const VALID_STRINGS = [/* VALID STRINGS */] function test1(x) {   for (const string of VALID_STRINGS) {     if (string === x) return  true   }   return false }

Это решение правильное, но медленное, потому что оно заставляет при каждом вызове функции пробегать по массиву в поисках совпадения. Таким образом сложность алгоритма по времени будет O(длина массива VALID_STRINGS)

Решение №2: Словарь

Массив не очень подходящая структура данных для подобной проверки. Куда лучше использовать словарь для хранения валидных строк. Ведь доступ к элементу словаря по ключу выполняется за константное время.

const VALID_STRINGS = [/* VALID STRINGS */] const VALID_STRINGS_DICT = {} for (const string of VALID_STRINGS) {   VALID_STRINGS_DICT[string] = true } function test2(x) {   return VALID_STRINGS_DICT[x] === true }

Отличное решение за константное время!

Берегись! Подводный камень!

Это хоть и быстрое решение, но не правильное. Оно не гарантирует того, что х — будет элементом массива VALID_STRINGS. И чтобы это продемонстрировать приведу контрпример:

// Предположим const VALID_STRINGS = ['somestring', 'anotherstring'] // Тогда после заполнения словаря, он будет иметь следующий вид const VALID_STRINGS_DICT = { somestring: true, anotherstring: true }  const underwaterRock = ['somestring']  test2(underwaterRock) // вернёт true

Хоть underwaterRock и не является строкой — но наша функция вернула true. А всё потому, что внутри тела функции test2(x) происходит использование x в качестве ключа.

VALID_STRINGS_DICT[x]

В этот момент — x приводится к строковому значению. И в этом и есть проблема — массив приводится к строке путем перечисления своих значений через запятую. Но когда это массив из одного строкового значения — он приводится в точности к своему первому элементу.

['somestring'].toString() === 'somestring'

Решение №3: С дополнительной проверкой

Добавим проверку типа прежде чем использовать x в качестве ключа

const VALID_STRINGS = [/* VALID STRINGS */] const VALID_STRINGS_DICT = {} for (const string of VALID_STRINGS) {   VALID_STRINGS_DICT[string] = true } function test2(x) {   return typeof x === 'string' && VALID_STRINGS_DICT[x] === true }

Дополнительная операция, но результат правильный.

Вывод

Спасибо за внимание, и будьте аккуратны, обращайте внимание на весь спектр входных значений ваших задач.

FAQ:

1. Почему не Typescript: потому что данная задача решается внутри библиотеки валидации данных, предназначенной для валидации данных, которые приходят из API. А в этой ситуации typescript ничего не гарантирует.
2. "Проблема не здесь, а там, где кидается массив там, где ожидается строка!"
   Именно для этого и нужна валидация — для раннего нахождения ошибки)
3. Почему не используется includes в медленном алгоритме? Потому что мне не нужен медленный алгоритм, а то что он медленей более явно видно при использовании цикла, чем метода.
4. Почему не юзается Set()?
   Конкретно для этой задачи я хочу избежать использования полифилов для старых браузеров, где Set отсутствует. Приведённое решение работает на очень старых версиях браузера, и выигрыша от использования Set в данном случае нет.

Прошу не рубите с плеча, и не дизлайкайте без комента)