BatSchool · Data и Equal

В прошлом уроке башня научилась отвечать по тегу и не забывать варианты. Теперь Магистраль присылает каждый кадр дважды, и башня оба раза честно отвечает. Чтобы ответить один раз, башня должна узнать кадр, который уже видела. Это урок о том, что значит «тот же самый» для JavaScript и для Effect и почему ключ, по которому узнают кадр, нельзя менять.

Один кадр или два

Никто не врёт. Вот два кадра, одинаковых до буквы:

const first: Frame = { from: 'T-3', to: 'T-1', id: 7, message: { _tag: 'Ping' } };
const again: Frame = { from: 'T-3', to: 'T-1', id: 7, message: { _tag: 'Ping' } };

console.log(first === again);
console.log(new Set([first, again]).size);

false
2

Для объектов === спрашивает не «одинаковы ли они», а «это один и тот же объект». Два письма с одинаковым текстом остаются двумя письмами: их можно положить в разные ящики, порвать одно и оставить другое. Set и Map в JavaScript сравнивают ключи так же, по ссылке. Поэтому в Set оба кадра: это два объекта, разобранных из двух строк провода.

Ринцвальд это понял и склеил ключ из строк:

const stringKey = (frame: Frame): string => `${frame.from}${frame.id}`;

console.log(stringKey({ ...first, from: 'T-1', id: 12 }));
console.log(stringKey({ ...first, from: 'T-11', id: 2 }));

T-112
T-112

Строки сравниваются по значению, и дубли ушли. С ними ушёл и кадр номер 2 от башни T-11: его ключ совпал с ключом кадра 12 от T-1. Разделитель между полями это починит, но строка-ключ так и останется строкой: компилятор не знает, из чего она склеена, не заметит забытого поля и разрешит сравнить ключ кадра с чем угодно ещё.

Равенство по значению

В Effect равенство по значению устроено в модуле Equal. Equal.equals(a, b) сравнивает примитивы по значению, а массивы, простые объекты, Map, Set и даты по содержимому, вглубь. В Effect 4 так сравниваются простые объекты по умолчанию, без подготовки:

import { Equal, HashSet } from 'effect';

console.log(Equal.equals(first, again));
console.log(HashSet.size(HashSet.make(first, again)));

true
1

HashSet это неизменяемое множество из effect, которое сравнивает элементы через Equal. Чтобы не сравнивать новый элемент с каждым старым, оно сначала считает его хеш и сравнивает только с теми, у кого хеш тот же. «Неизменяемое» значит, что HashSet.add возвращает новое множество, а старое не трогает, как record из урока 19.

Осталось решить, что считать одним кадром. Целиком кадры сравнивать нельзя: у отправителя номер кадра один, и второй кадр с тем же номером это повтор, даже если по дороге в нём что-то исказилось. Значит, кадр узнают по паре «отправитель, номер».

Ключ кадра

Ключ можно было бы держать простым объектом { from, id }, раз уж Effect 4 сравнивает их по значению. Но у ключа появилось имя и правила, и для таких значений в effect есть модуль Data:

import { Data, Equal, HashSet } from 'effect';

/** Кадр узнают по отправителю и номеру; два ключа с одинаковыми полями равны. */
export class FrameKey extends Data.Class<{ readonly from: string; readonly id: number }> {}

export const keyOf = (frame: Frame): FrameKey => new FrameKey({ from: frame.from, id: frame.id });

const k1 = new FrameKey({ from: 'T-3', id: 7 });
const k2 = new FrameKey({ from: 'T-3', id: 7 });
console.log(k1 === k2, Equal.equals(k1, k2));

false true

Data.Class<Поля> даёт класс, у которого конструктор принимает объект с этими полями, а Equal.equals сравнивает экземпляры по полям. Что даёт класс сверх простого объекта:

у ключа есть имя: в сигнатуре FrameKey, а не { from: string; id: number }, и его не спутаешь с похожим объектом;
конструктор проверяет поля: забытое id не соберётся;
поля readonly, и k1.id = 8 не соберётся с ошибкой TS2540: Cannot assign to 'id' because it is a read-only property;
ключ равен только ключу: Equal.equals(k1, { from: 'T-3', id: 7 }) даёт false, потому что простой объект это другой вид значения.

Одно предупреждение: readonly здесь только в типах. В рантайме экземпляр не заморожен, и as any или код на JavaScript поменяют поле без возражений. Почему ключ нельзя менять, покажет «Где тут дыра».

С ключом выкинуть повторы можно за один проход:

export const dedupe = (frames: readonly Frame[]): readonly Frame[] => {
  let seen = HashSet.empty<FrameKey>();
  const unique: Frame[] = [];
  for (const frame of frames) {
    const key = keyOf(frame);
    if (HashSet.has(seen, key)) continue;
    seen = HashSet.add(seen, key);
    unique.push(frame);
  }
  return unique;
};

Каждый кадр даёт новый ключ. Уже видели такой ключ, кадр пропускаем; нет, запоминаем ключ в новом множестве и оставляем кадр. Порядок провода сохраняется, остаётся первый кадр с каждым ключом.

Вердикт

Башне мало выкинуть дубли, ей нужен вердикт по каждому кадру: принят, повтор или призрак, то есть подтверждение кадра, который башня не отправляла. Это объединение по тегу из урока 07, и Data умеет описывать его вместе с конструкторами:

export type Verdict = Data.TaggedEnum<{
  readonly Accepted: { readonly frame: Frame };
  readonly Duplicate: { readonly frame: Frame };
  readonly Phantom: { readonly frame: Frame; readonly of: number };
}>;
export const Verdict = Data.taggedEnum<Verdict>();

Data.TaggedEnum<{ ... }> превращает объект «тег → поля» в объединение: Verdict это { _tag: 'Accepted'; frame } | { _tag: 'Duplicate'; frame } | { _tag: 'Phantom'; frame; of }. Data.taggedEnum<Verdict>() строит для него значение с тем же именем: конструкторы Verdict.Accepted({ frame }), проверку Verdict.$is('Duplicate') и сопоставление Verdict.$match(вердикт, { Accepted: ..., Duplicate: ..., Phantom: ... }), которое, как Match.exhaustive, требует все теги. Тип и значение с одним именем живут в TypeScript в разных пространствах и не мешают друг другу.

Варианты сравниваются по значению, как ключи: два Verdict.Accepted с равными кадрами равны по Equal.equals, даже если кадры это разные объекты.

Перевод с Ук

import { Data } from 'effect';

type Frame = { readonly from: string; readonly to: string; readonly id: number };

export type Verdict = Data.TaggedEnum<{
  readonly Accepted: { readonly frame: Frame };
  readonly Duplicate: { readonly frame: Frame };
  readonly Phantom: { readonly frame: Frame; readonly of: number };
}>;
export const Verdict = Data.taggedEnum<Verdict>();

declare const frame: Frame;
export const ghost = Verdict.Phantom({ frame });

verdict.ts(13,38): error TS2345: Argument of type '{ frame: Frame; }' is not assignable to parameter of type '{ readonly frame: Frame; readonly of: number; }'.
  Property 'of' is missing in type '{ frame: Frame; }' but required in type '{ readonly frame: Frame; readonly of: number; }'.

Две строки. Нижняя говорит главное: в объекте { frame: Frame; } нет поля of, а тип { readonly frame: Frame; readonly of: number; } его требует. Верхняя называет место: строка 13, колонка 38, аргумент Verdict.Phantom. Обрати внимание, откуда компилятор взял требуемый тип: ты его не писал. Конструктор Phantom вывел его из описания вердикта: всё, что лежит в варианте, кроме _tag. Перевод: «призрак без номера подтверждённого кадра не призрак, скажи, какой кадр подтвердили». Тег конструктор ставит сам, поэтому писать _tag: 'Phantom' руками не нужно, и ошибиться в нём нельзя.

Под капотом

HashSet хранит элементы по корзинам, а корзину выбирает хеш. Чтобы проверить has(seen, key), он считает хеш ключа, идёт в его корзину и там сравнивает Equal.equals с теми немногими, кто в ней лежит. Равные значения обязаны давать равный хеш, иначе равный элемент окажется в чужой корзине и его не найдут. Data.Class считает хеш по полям, поэтому два FrameKey({ from: 'T-3', id: 7 }) попадают в одну корзину.

Посчитать хеш объекта вглубь не бесплатно, и Effect считает его один раз: результат запоминается в WeakMap, где ключом служит сам объект. Результаты Equal.equals для пар объектов запоминаются так же. Это быстро и честно, пока объект не меняется. Документация effect говорит прямо: объект, у которого уже посчитали хеш, надо считать неизменяемым. Если нужна изменяемая вещь, сравнивай её по ссылке: Equal.byReference(x) даёт такую же вещь, которую Equal.equals сравнивает как ===.

В котле мы пришли к неизменяемым данным из урока 19 ради того, чтобы старый журнал оставался правдой. Здесь та же неизменяемость нужна, чтобы отпечаток оставался правдой.

Где тут дыра

import { HashSet } from 'effect';

type Frame = { readonly from: string; readonly id: number; readonly body: string };

// Один ключ на всю ночь: зачем мусорить объектами.
const key = { from: '', id: 0 };

export const dedupe = (frames: readonly Frame[]): readonly Frame[] => {
  let seen = HashSet.empty<{ from: string; id: number }>();
  const unique: Frame[] = [];
  for (const frame of frames) {
    key.from = frame.from;
    key.id = frame.id;
    if (HashSet.has(seen, key)) continue;
    seen = HashSet.add(seen, key);
    unique.push(frame);
  }
  return unique;
};

const a = { from: 'T-3', id: 1, body: 'a' };
const b = { from: 'T-5', id: 1, body: 'b' };
console.log(dedupe([a, a]).map((frame) => frame.body));
console.log(dedupe([a, a, b]).map((frame) => frame.body));

[ 'a' ]
[ 'a' ]

На его примере, где повторяется один кадр, всё верно: остался один a. На соседнем пропал кадр b, совсем другой, от другой башни. Множество не хранит копию ключа, оно хранит тот самый объект. Ринцвальд положил в него key и следующей строкой стал его переписывать. На кадре b в key лежит { from: 'T-5', id: 1 }, и has(seen, key) находит в множестве… тот же самый key, который сравнивается сам с собой. Для множества ключ T-5 уже давно лежит внутри: он и есть та запись, что когда-то была T-3.

Если бы Ринцвальд заводил новый объект, но менял его после add, беда была бы тише. Хеш записи остался бы старым, запомненным, и запись лежала бы не в той корзине: искать её по новому значению бесполезно, по старому тоже, а положить ещё один «равный» ключ получится. Множество с двумя равными элементами это множество, которому больше нельзя верить.

Лечится тем, что ключ нельзя менять: new FrameKey(...) на каждый кадр, с readonly полями, которые компилятор не даст переписать. Сто тысяч маленьких объектов за ночь движок JavaScript переживёт; кадр, пропавший без следа, Рыдкулл не переживёт.

Башня, этап 9

Башня учится узнавать кадр по отправителю и номеру: ключ FrameKey, выкидывание повторов с сохранением порядка провода и вердикт по каждому кадру. Ключ и повторы живут в src/frame.ts, вердикт в src/tower.ts, потому что призрака видно, только зная, что башня отправляла. Сигнатуры в карточке заказа.

EF-44-1★

Не запуская, ответь true или false для каждой строки:

Equal.equals({ from: 'T-3', id: 1 }, { id: 1, from: 'T-3' });
Equal.equals(new FrameKey({ from: 'T-3', id: 1 }), { from: 'T-3', id: 1 });
new FrameKey({ from: 'T-3', id: 1 }) === new FrameKey({ from: 'T-3', id: 1 });
Equal.equals([1, 2], [1, 2]);
Equal.equals(Equal.byReference({ id: 1 }), { id: 1 });

Какие из них дали бы другой ответ, если заменить Equal.equals(a, b) на a === b?

EF-44-2★★

Ринцвальд считает, что dedupe лучше писать сравнением целых кадров: HashSet из самих Frame, без ключа, раз Effect 4 и так сравнивает объекты по значению. Придумай две строки провода, на которых его вариант и вариант с FrameKey дадут разный ответ. Какой из ответов нужен башне и почему?

Практика

Дальше

Башня отвечает на каждый кадр один раз и пишет вердикт по каждому. Пондер подключает её к настоящему проводу Магистрали и хмурится.

Как построить мост от колбэков и промисов к квитанциям и где в программе ему место, разберём в следующем уроке.