https://habr.com/ru/post/512306/

• JavaScript

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

Задача

Дан список строк: VALID_STRINGS.
Cоздать функцию валидации test(x) которая должна вернуть true, если x — это одна из строк в этом массиве.
Область применения: x — любое значение Javascript
Ограничения: Не использовать ES6. (Цель — старый браузер)

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

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

const VALID_STRINGS = [/* VALID STRINGS */]
function test1(x) {
  for (let i = 0; i < VALID_STRINGS.length; i++) {
    if (VALID_STRINGS[i] === x) return  true
  }
  return false
}

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

Заметим, что это решение можно было бы переписать используя методы массивов(indexOf, includes, some, reduce ...). Цикл выбран для того, чтобы продемонстрировать линейную сложность алгоритма.

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

Именно это решение содержало баг, который я обнаружил.

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

const VALID_STRINGS = [/* VALID STRINGS */]
const VALID_STRINGS_DICT = {}
for (let i = 0; i < VALID_STRINGS.length; i++) {
  const validString = VALID_STRINGS[i]
  VALID_STRINGS_DICT[validString ] = 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 (let i = 0; i < VALID_STRINGS.length; i++) {
  const validString = VALID_STRINGS[i]
  VALID_STRINGS_DICT[string] = true
}
function test2(x) {
  return typeof x === 'string' && VALID_STRINGS_DICT[x] === true
}

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

Решение №4: Set

Если мы опустим ограничение на неиспользование ES6. То сможем полностью избежать подобных проблем.

const VALID_STRINGS = [/* VALID STRINGS */]
const validStringsSet = new Set(VALID_STRINGS)

function test4(x) { return validStringsSet.has(x) }

Вывод

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

FAQ:

1. Почему не Typescript: потому что данная задача решается внутри библиотеки валидации данных, предназначенной для валидации данных, которые приходят из API. А в этой ситуации typescript ничего не гарантирует.
   Сама библиотека валидации написана на Typescript. Но функции, валидации по умолчанию получают на вход значение типа unknown или any. Отсюда и появляется необходимость предполагать, что входное значение функции может быть любым значением javascript.
2. "Проблема не здесь, а там, где кидается массив там, где ожидается строка!"
   Именно для этого и нужна валидация — для раннего нахождения ошибки)
3. Почему не используется includes в медленном алгоритме? Потому что мне не нужен медленный алгоритм, а то что он медленей более явно видно при использовании цикла, чем метода.
4. Почему ограничение на использование ES6? В библиотеке валидации я хотел бы избежать использования фишек, которые не имплементированы в старые браузеры, особенно если без них можно обойтись. Решение №3 полностью решает поставленную задачу, и не имеет проблем с совместимостью. Решение №4 требует использования полифилов, и не будет работать так же производительно. Хотя читается оно в разы и разы легче.