Войти Регистрация
Фронтенд

54. Diff корзины Яндекс Лавки: список правок между двумя деревьями

Сложная

Корзина Яндекс Лавки в веб-версии перерисовывается при каждом «+1». Перестраивать весь список из 30 товаров дорого, поэтому новое дерево сравнивают со старым и применяют только правки. Узел — строка (текст) или {tag, attrs, children}; attrs и children могут отсутствовать.

Напишите diff(a, b), верните массив правок. Путь — индексы детей от корня через точку, у корня пустая строка: "", "0", "2.1". Правила для пары узлов на одном пути:

Обе строки: если различаются — ["text", path, новая]. Строка и объект, или теги разные — ["replace", path, b], внутрь не заходим. Теги одинаковые — сначала атрибуты по алфавиту ключей из обоих узлов: новое или изменённое значение ["attr", path, key, value], исчезнувший атрибут ["attr", path, key, null]. Потом дети по индексу.

Детей сравниваем попарно до длины короче. Лишние новые — ["insert", childPath, node] по возрастанию индекса. Лишние старые — ["remove", childPath] по убыванию индекса, чтобы при применении по очереди индексы не сдвигались. Правки идут в порядке обхода: сначала правки узла, потом его детей.

В работе: Нажали «+1» у молока в корзине на 30 позиций — должна измениться одна текстовая нода, а не 30 элементов списка.

Пример 1: +1 к молоку и снята акция с сыра

Аргументы теста
{"tag": "ul", "attrs": {"class": "cart"}, "children": [{"tag": "li", "attrs": {"class": "item"}, "children": ["Молоко 3,2 % · 1 шт"]}, {"tag": "li", "attrs": {"class": "item"}, "children": ["Хлеб бородинский · 1 шт"]}, {"tag": "li", "attrs": {"class": "item promo", "data-sale": "20"}, "children": ["Сыр 200 г · 1 шт"]}]}, {"tag": "ul", "attrs": {"class": "cart"}, "children": [{"tag": "li", "attrs": {"class": "item"}, "children": ["Молоко 3,2 % · 2 шт"]}, {"tag": "li", "attrs": {"class": "item"}, "children": ["Хлеб бородинский · 1 шт"]}, {"tag": "li", "attrs": {"class": "item"}, "children": ["Сыр 200 г · 1 шт"]}]}
Ожидается
[["text", "0.0", "Молоко 3,2 % · 2 шт"], ["attr", "2", "class", "item"], ["attr", "2", "data-sale", null]]

Пример 2: одинаковые деревья

Аргументы теста
{"tag": "ul", "attrs": {"class": "cart"}, "children": [{"tag": "li", "attrs": {"class": "item"}, "children": ["Молоко 3,2 % · 1 шт"]}, {"tag": "li", "attrs": {"class": "item"}, "children": ["Хлеб бородинский · 1 шт"]}, {"tag": "li", "attrs": {"class": "item promo", "data-sale": "20"}, "children": ["Сыр 200 г · 1 шт"]}]}, {"tag": "ul", "attrs": {"class": "cart"}, "children": [{"tag": "li", "attrs": {"class": "item"}, "children": ["Молоко 3,2 % · 1 шт"]}, {"tag": "li", "attrs": {"class": "item"}, "children": ["Хлеб бородинский · 1 шт"]}, {"tag": "li", "attrs": {"class": "item promo", "data-sale": "20"}, "children": ["Сыр 200 г · 1 шт"]}]}
Ожидается
[]
Как проверяем Объявите diff — тест вызывает её сам. Таймеры и Date в тестах ненастоящие: время идёт по команде теста, поэтому setTimeout на 5 секунд проверяется мгновенно. Тестов 9: 2 открыты выше, остальные приходят после старта подхода. Лимит — 2 с на тест. 
function diff(a, b) // → Array<[type, path, ...]>
деревьяvirtual DOMdiffрекурсия

Источник: на задачах Яндекс Лавки: корзина в веб-версии. Условие пересказано своими словами.