Дыры в разреженных массивах и что делает каждый метод

BotBrowser позволяет воспроизвести авторизованный фикстур того же источника под объявленным профилем и сохранить ограниченную запись того, что страница реально отправила, но он не может заставить разреженный массив вести себя как плотный, не может помешать JSON превратить дыру в null и не может заставить indexOf и includes совпасть на отсутствующем индексе. Этот разбор запускает один зонд по массиву из трёх элементов с одной дырой и фиксирует, какие методы итерации посещают дыру, какие её пропускают, чем дыра становится, когда массив копируют, заполняют, сортируют или сериализуют, и почему две проверки принадлежности на одном массиве дают противоположные ответы.

Кратко

• Дыра это отсутствующий индекс, а не сохранённый undefined: на ['a', , 'c'] зонд печатает length=3 has1=false ownKeys=0,2, тогда как плотный ['a', undefined, 'c'] печатает has1=true ownKeys=0,1,2.
• forEach, map, filter, some и every полностью пропускают дыры, поэтому map поверх дыры оставляет дыру в результате, а filter возвращает более короткий плотный массив.
• reduce без начального значения стартует с первого присутствующего элемента, поэтому сложение двух присутствующих значений даёт a+c, а тот же вызов с начальным 0 считает только два посещения.
• Spread и Array.from заполняют дыру значением undefined, поэтому копия сообщает has1=true value1=undefined, но entries() показывает дыру как 1:undefined, потому что итератор посещает каждый индекс.
• indexOf(undefined) возвращает -1 на дыре, а includes(undefined) возвращает true, потому что они используют разные сравнения и одно из них пропускает дыру.
• join и String() показывают дыру как пустое поле, поэтому ['a', , 'c'].join('-') это "a--c", тогда как slice и reverse сохраняют дыру, а sort переносит её на последний индекс.
• Оборот JSON.parse(JSON.stringify(...)) превращает дыру в null и делает её собственным ключом, поэтому массив возвращается плотнее, чем ушёл.

Содержание

• Чем дыра отличается от сохранённого undefined
• Какие методы итерации пропускают дыру
• Чем дыра становится при копировании массива
• Почему две проверки принадлежности расходятся
• Запись одного показания разреженного массива

Чем дыра отличается от сохранённого undefined

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

node=v26.9.0
shape -> length=3 has1=false ownKeys=0,2 json=["a",null,"c"]
dense -> length=3 has1=true ownKeys=0,1,2 json=["a",null,"c"]
forEach -> visits=0:"a"|2:"c"
map -> result=["0:\"a\"",null,"2:\"c\""] has1=false length=3
filter -> result=["a","c"] length=2
some -> indexesSeen=0,2
reduce-no-init -> a+c
reduce-with-init -> count=2
spread -> length=3 has1=true value1=undefined
from -> length=3 has1=true value1=undefined
entries -> 0:"a"|1:undefined|2:"c"
indexOf -> -1 includes -> true
indexOf-c -> 2
join -> "a--c"
toString -> "a,,c"
reverse -> length=3 has1=false keys=0,2
sort -> length=4 has1=true has3=false keys=0,1,2
fill -> has1=true value1="x"
slice -> length=3 has1=false
copyWithin -> has1=true value1="c"
json-roundtrip -> has1=true value1=null

Первые две строки это весь разбор в миниатюре. Оба массива имеют length=3 и оба сериализуются в ["a",null,"c"], поэтому JSON.stringify не может их различить. Разница в 1 in a и Object.keys. Массив с дырой сообщает has1=false и перечисляет только ключи 0,2; плотный массив сообщает has1=true и перечисляет 0,1,2. Дыра это не свойство со значением undefined; это отсутствие свойства, и каждый метод, который читает массив, должен решить, что делать с этим отсутствием.

Именно поэтому проверка, написанная как if (arr[i] === undefined), неверно классифицирует оба случая. На массиве с дырой чтение a[1] даёт undefined, точно как на плотном массиве, потому что отсутствующий индекс читается как undefined по правилам языка. Единственная проверка, которая их разделяет, это проверка наличия, 1 in a, или её эквивалент Object.prototype.hasOwnProperty.call(a, 1), и вторая форма нужна, когда массив мог унаследовать числовое свойство из загрязнённого прототипа.

У различия есть цена, которая проявляется в работе с размером запроса. Страница, которая строит результат присваиванием по вычисленным индексам, может оставить дыры там, где ветка не выполнилась, и сериализованная форма тогда содержит null в каждой из этих позиций. Потребитель, читающий этот JSON, не может отличить намеренно записанный null от дыры, которую никогда не заполняли, поэтому схема, которой важна разница, нуждается в соседнем поле или явном флаге наличия, потому что сам массив не несёт различие через JSON.stringify.

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

Три формы порождают дыру без того, чтобы кто-то написал запятую, и каждую легко пропустить на проверке. Первая это вычисленное присваивание, которое использует зонд: цикл, который пишет result[index] = value только для индексов, прошедших фильтр, оставляет остальные отсутствующими. Вторая это new Array(n) с последующими частичными записями, потому что конструктор задаёт length и больше ничего, поэтому каждый индекс начинается как дыра. Третья это delete arr[i], который убирает собственное свойство и оставляет length неизменным, поэтому удаление, которое выглядит как разреженное изъятие, это ровно дыра и ведёт себя как дыра в каждом методе, который измерил зонд.

Четвёртый путь тоньше и происходит от присваивания за концом массива. Запись arr[arr.length + 2] = 'x' задаёт length равным новому индексу плюс один и оставляет два промежуточных индекса как дыры, потому что язык расширяет массив и не заполняет промежуток. Страница, которая добавляет с вычисленным смещением вместо push, поэтому создаёт дыры молча, и число присутствующих элементов перестаёт равняться length.

Обнаружение через границу это то место, где всё становится операционным. Запись, которая хранит массив со страницы, может нести length и сериализованный JSON, и оба совпадают на плотном массиве с null и на разреженном массиве с дырой. Первые две строки зонда это ровно тот случай: ["a",null,"c"] для обоих. Поэтому запись, которая хочет сохранить различие, должна добавить карту наличия, например Object.keys(arr), а потребитель, который читает только сериализованную форму, уже потерял информацию до того, как начал.

Различие важно и для проверок равенства. Два массива, которые оба сериализуются в ["a",null,"c"], сравниваются как неравные под функцией глубокого равенства, которая обходит собственные ключи, потому что у одного есть индекс 1, а у другого нет, и как равные под функцией, которая сначала сериализует оба в JSON. Тест, который сравнивает вывод страницы с фикстуром, поэтому зависит от того, какой из двух стилей сравнения он использует, и фикстур, собранный вручную, молча совпадёт с плотным массивом, тогда как страница произвела разреженный.

Какие методы итерации пропускают дыру

Методы итерации массива делятся на две группы, и разделение не интуитивно. Пять, которые принимают обратный вызов, forEach, map, filter, some и every, пропускают дыру так, будто индекса нет. forEach у зонда печатает visits=0:"a"|2:"c", индекс 1 отсутствует в списке, а some печатает indexesSeen=0,2, потому что он никогда не вызывает обратный вызов для дыры.

map это тот, что удивляет, потому что его результат сохраняет дыру. Зонд печатает result=["0:\"a\"",null,"2:\"c\""] has1=false, поэтому отображённый массив имеет ту же длину, реальное значение по индексам 0 и 2 и по-прежнему ничего по индексу 1. map, который строит строки из каждого элемента, даёт результат, где дыра остаётся дырой, и последующий join на этом результате покажет её как пустое поле, а не как строку undefined.

filter противоположен, потому что он не может сохранить дыру: его результат содержит только элементы, которые принял предикат, а дыра предикату никогда не предлагается. Зонд передаёт всегда истинный предикат и получает result=["a","c"] length=2, плотный массив на одну позицию короче источника. Это делает filter(() => true) инструментом удаления дыр, и страница, которая использует его как способ скопировать массив, на самом деле уплотняет копию как побочный эффект.

reduce находится между группами, и его поведение зависит от того, задано ли начальное значение. Без начального значения reduce у зонда стартует с первого присутствующего элемента и возвращает a+c, поэтому дыра никогда не доходит до обратного вызова, а число сложений равно одному, а не двум. С начальным 0 зонд печатает count=2, потому что аккумулятор есть с самого начала и обратный вызов выполняется по одному разу для каждого присутствующего элемента. Вариант без начального значения также выбрасывает на массиве без присутствующих элементов, что является разреженным эквивалентом случая пустого массива.

some и every замыкают цепь, и дыра не считается посещением ни для одного из них. Это важно для цикла проверки, который ожидает, что every осмотрел каждый индекс: массив с дырой может пройти проверку every по диапазону, который обратный вызов никогда не видел. Предикат, который отклонил бы отсутствующее значение, никогда не выполняется, поэтому every по частично заполненному массиву слабее, чем кажется, и страница, которой нужно отвергнуть дыру, должна проверять наличие отдельно.

Сам протокол итерации дыры не пропускает. entries() у зонда печатает 0:"a"|1:undefined|2:"c", поэтому цикл for...of или spread по entries() видит каждый индекс и сообщает дыру как undefined. Последовательность, которую даёт for...of, это та же, которую упорядочивает компаратор, что сортировка массива и компараторы рассматривает со стороны порядка. Это другой способ обойти весь массив: методы с обратным вызовом пропускают дыры, а протокол итератора их заполняет, и именно поэтому страница может получить два разных счёта элементов одного массива в зависимости от того, какой цикл использует.

Чем дыра становится при копировании массива

Копирование массива не имеет одного ответа. Одни операции сохраняют дыру, другие заменяют её на undefined, третьи её переносят. Зонд упражняет пять из них и получает три разных результата из одного источника.

Spread и Array.from заполняют дыру. Зонд печатает spread -> length=3 has1=true value1=undefined и то же для from, поэтому копия плотная с явным undefined на дыре. Это самый частый способ, которым дыра исчезает без предупреждения: копия [...arr] при рефакторинге превращает разреженный массив в плотный, и любой последующий код, который рассчитывал на то, что filter сбросит дыру, теперь имеет undefined, с которым надо разбираться.

slice сохраняет дыру. Зонд печатает slice -> length=3 has1=false, поэтому нарезка всего массива воспроизводит ту же форму, потому что slice копирует собственные ключи и не изобретает отсутствующий. Ключи, которые копирует slice, это те, что сообщает обход собственных ключей, и порядок ключей объекта объясняет, почему они возвращаются отсортированными, а не в порядке вставки. Это копия, которая ведёт себя как поверхностный клон хранилища, а не значений, и это тот вариант, к которому стоит прибегать, когда дыра значима.

fill пишет на каждый индекс, который покрывает, включая дыру. Зонд заполняет индекс 1 и печатает fill -> has1=true value1="x", поэтому fill по диапазону, включающему дыру, делает её реальным элементом. copyWithin делает то же через перенос: copyWithin -> has1=true value1="c" показывает значение, скопированное поверх дыры. reverse сохраняет дыру. Зонд печатает reverse -> length=3 has1=false keys=0,2, поэтому после разворота массива из трёх элементов дыра остаётся единственным отсутствующим индексом, что логично, потому что разворот отображает индекс 1 на себя и проводит два присутствующих значения друг мимо друга.

Результат sort стоит прочитать дважды. Зонд добавляет b через concat и затем сортирует результат из четырёх элементов; шаг сортировки печатает sort -> length=4 has1=true has3=false keys=0,1,2, поэтому сортировка перенесла дыру с индекса 1 на последний индекс и заполнила индекс 1 реальным значением. Страница, которая сортирует частично заполненный массив и затем проверяет length, всё ещё получает 4, но дыра теперь в конце, а не в середине, поэтому цикл, который останавливается на первом undefined, читает другой элемент, чем до сортировки. Форма не изменилась; изменилась только её позиция, и проверка наличия по индексу 1 перешла с false на true, а по индексу 3 перевернулась в обратную сторону.

join и String() совпадают между собой и расходятся со всем остальным. Зонд печатает join -> "a--c" и toString -> "a,,c", поэтому оба показывают дыру как пустое поле, а не как слово undefined. Это тот же вывод, который дал бы плотный массив с реальной пустой строкой, что значит, что объединённую строку нельзя снова разделить на исходный массив, не зная, сколько было дыр. Оборот через join и split поэтому теряет информацию о наличии, которую нёс in.

Почему две проверки принадлежности расходятся

Самое острое следствие дыры в том, что две проверки принадлежности на одном массиве дают противоположные ответы. Зонд печатает indexOf -> -1 includes -> true для поиска undefined на массиве с дырой, и он также печатает indexOf-c -> 2, чтобы показать, что поиск присутствующего значения обычен.

Причина в том, что indexOf использует строгое равенство и пропускает дыры, а includes использует сравнение SameValueZero и трактует дыру как undefined. Дыра читается как undefined, SameValueZero говорит, что undefined совпадает с undefined, и includes возвращает true. indexOf никогда не посещает дыру, поэтому возвращает -1. Страница, которая защищает значение через if (arr.indexOf(x) === -1), и страница, которая защищает его через if (!arr.includes(x)), поэтому расходятся каждый раз, когда x равно undefined, а в массиве есть дыра, и расхождение молчаливое.

Это различие не является дефектом ни одного из методов; это документированное разделение, и оно существует потому, что includes добавили позже с мыслью о случае NaN, поэтому он должен был использовать SameValueZero, чтобы сделать истинным [NaN].includes(NaN). То же сравнение заставляет дыру совпадать с undefined, что является побочным эффектом, который язык сохранил, потому что его удаление сделало бы includes противоречивым самому себе. Страница, которой нужно знать, присутствует ли значение и заполнен ли индекс, поэтому нуждается в обеих проверках, одной для значения и одной для наличия, и два вопроса имеют разные ответы на разреженном массиве.

Оборот JSON закрывает разрыв так, что скрывает проблему. Зонд печатает json-roundtrip -> has1=true value1=null, поэтому JSON.parse(JSON.stringify(holey)) возвращает массив, где индекс 1 присутствует и его значение null. Дыра стала собственным ключом со значением null, что значит, что клон на основе JSON молча уплотняет массив и заменяет отсутствие значением, которого схема может не ожидать. Это тот же риск, что у копии через spread, но его труднее заметить, потому что код, который это делает, часто выглядит как сохранение данных.

Запись одного показания разреженного массива

Показание разреженного массива подтверждает узкое утверждение: эта среда, эта форма, эти методы дали эти результаты. Четыре поля держат его проверяемым:

1. Карта наличия, потому что length и сериализованная форма не различают дыру и сохранённый undefined.
2. Операция и то, посещает, пропускает или материализует она дыру, потому что ответ различается для каждой.
3. Собственные ключи результата, потому что map сохраняет дыру, filter её отбрасывает, а сортировка её переносит в конец.
4. Прошло ли значение через JSON, потому что оборот превращает каждую дыру в null и делает её собственным ключом.

Публичные источники

• MDN: Array
• MDN: Array.prototype.forEach()
• MDN: Array.prototype.filter()
• MDN: Array.prototype.includes()
• MDN: Array.prototype.sort()
• ECMAScript: объекты Array
• BotBrowser: справочник согласованности автоматизации

Практический вывод

Относитесь к разреженному массиву как к типу, отличному от плотного: проверяйте наличие через in или hasOwnProperty, а не чтением значения, ожидайте, что методы с обратным вызовом пропустят дыру, а spread и Array.from её заполнят, и помните, что сортировка паркует дыру на последнем индексе там, где она была в середине. Когда значение должно пережить копию, выбирайте копию по тому, что она делает с дырой: slice её сохраняет, spread уплотняет, а оборот JSON превращает её в null. Для порядка, который принимает значение заполнения, когда оно уже существует, читайте сортировка массива и компараторы; для того, что копия JSON делает с остальной структурой, читайте structuredClone против JSON.