» » » Изучаем и реализуем алгоритм работы правильного observer паттерна для react компонентов

 

Изучаем и реализуем алгоритм работы правильного observer паттерна для react компонентов

Автор: admin от 14-02-2018, 06:35, посмотрело: 99

Изучаем и реализуем алгоритм работы правильного observer паттерна для react компонентов

Итак продолжаем развивать observer-паттерн. В предыдущей статье от старого и очень простого паттерна "observer" маленькими шагами мы пришли к mobx и написали его мини-версию. В этой статье мы напишем полноценную версию mobx которая реализует алгоритм обновления зависимостей в правильном порядке для избежания ненужных вычислений. Надо сказать что попытки описать этот алгоритм на хабре предпринимались и раньше в статьях товарища vintage про атомы тут, тут, и тут но там не описан в полной мере последний "правильный" порядок обновления о чем и будет речь в этой статье.

https://www.youtube.com/watch?v=TfxfRkNCnmk) (забавно что автор по факту солгал потому в самом mobx реализуется не этот а более правильный алгоритм но об этом позже).



Изучаем и реализуем алгоритм работы правильного observer паттерна для react компонентов


Вкратце алгоритм состоит из способа распространения вызова функции по графу зависимостей и выявление значение "глубины" каждой зависимости через инкремент-декремент счетчика и потом вызов их в порядке увеличения глубины. Пусть при изменении имени, ячейка firstName не будет сразу вызывать подписчиков в цикле, а установит внутри каждого из слушателей значение 1 и вызовет их чтобы каждый установил значение своих подписчиков на 1 больше чем у него самого. И так рекурсивно. Ячейка fullName получит значения 1 а ячейка label получит значение 2 потому что счетчик увечили сначала ячейка firstName а потом и ячейка fullName. Теперь, после того как рекурсивный вызов закончился, ячейка fistName вызывает обратную процедуру — уменьшение счетчика рекурсивно у своих подписчиков. И теперь момент — после того как вызвался код уменьшение счетчика надо проверить если значение вернулось к нулю то только тогда следует выполнить перевычисление ячейки. Итак произойдет уменьшение счетчика label с 2 до 1 (но не вычисляется потому что не 0) потом уменьшится счетчик fullName c 1 на 0 и вычислится fullName и только потом вычислится сам label потому что fullName после вычисление вызовет уменьшение счетчика label c 1 до 0.



Таким образом мы получили вычисление label только один раз после того как все зависимые ячейки сами обновятся и будут иметь актуальное значение.



Другим вариантом (который по факту является оптимизированной версией первого) будет идея вызвать подписчиков в порядке увеличения их глубины. Под глубиной ячейки примем максимальное значение глубины своих зависимых ячеек + 1 а ячейка без формулы которая не имеет зависимостей будет иметь глубину 0. Получаем что firstName и lastName будут иметь значение 0, fullName будет иметь значение 1 а label будет иметь значение 2 потому что максимальное значение у подписчиков (fullName и firstName) равно 1, делаем +1 получаем 2.



Теперь когда ячейка fistName обновит свое значение она должна вызвать своих подписчиков в порядке увеличение глубины — сначала fullName а потом label. Массив можно сортировать каждый раз при вызове, а можно оптимизиировать и сделать вставку в отсортированный массив в момент добавления новой зависимости.



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



Таким образом мы получим вызов подписчиков в правильном порядке и избежим лишний вычислений. Почти...



В обоих вариантах есть один очень неприметный баг. Формула ячейки label не просто зависит от firstName и fullName — она зависит от них при определенных условиях. Если значение firstName.get().length <= 3 то мы выводим fullName но если значение больше 3 то мы зависим только от firstName. А теперь подумаем что происходит при когда значение firstName меняется с 4 на 3. Ячейка firstName обновит свое значение и должна вызвать подписчиков в порядке глубины — сначала будет вызов fullName который вычислит свое значение а потом вызов label который вычислит свое значение уже имея актуальное значение fullName. На первый взгляд кажется все правильно. Но если подумать то вычисление fullName на самом деле здесь не нужно — потому что значение fistName будет равно 3 а значит когда последним вызовется label ему не потребуется вызвать fullName.get() потому что ветка if просто не выполнится. Причем, в следующий раз, когда потребуется вызвать fullName его значение будет неактуально потому что между его вызовом может сколько угодно раз обновляться lastName. Вот вам и баг с лишним вычислением. В итоге наш алгоритм с вызовом подписчиков в порядке их глубины не работает в общем случае.



Итак существует тот самых "правильный" алгоритм, который ни при каких условиях и хитросплетенных зависимостях не вызовет двойного вычисления ячейки. Для начала приведу код, который по совместительству является почти полноценной версией mobx (за исключением массива и декораторов) всего в 85 строчках кода



class Cell {
  reactions = new Set();
  dependencies = new Set();
  runned = false;
  constructor(value, fn  = null, reactionFn = null, active = false) { 
    this.value = value;
    this.fn = fn;
    this.reactionFn = reactionFn;
    this.state = fn ? "dirty" : "actual";
  }
  get() {
    if (this.state !== "actual") this.actualize();
    if (CurrentObserver) {
      this.reactions.add(CurrentObserver);
      CurrentObserver.dependencies.add(this);
    }
    return this.value;
  }
  set(newValue: T) {
    if (newValue !== this.value) {
      this.value = newValue;
      for (const reaction of this.reactions) {
        reaction.mark(true);
      }
      runPendingCells()
      return true;
    } else {
      return false;
    }
  }
  mark(dirty = false) {
    this.state = dirty ? "dirty" : "check";
    for (const reaction of this.reactions) {
      if(reaction.state === "actual") reaction.mark();
    }
    if (this.active) PendingCells.push(this);
  }
  actualize() {
    if (this.state === "check") {
      for (const dep of this.dependencies) {
        dep.actualize();
      }
      if((this.state as "check" | "dirty") === "dirty"){
        this.run();
      } else {
        this.state = "actual"
      }
    } else if(this.state === "dirty"){
      this.run();
    } 
  }
  run() {
    if (!this.fn) return;
    const currentObserver = CurrentObserver;
    CurrentObserver = this;
    const oldDependencies = this.dependencies;
    this.dependencies = new Set();
    const newValue = this.fn();
    CurrentObserver = currentObserver;
    for (const dep of oldDependencies) {
      if (!this.dependencies.has(dep)) dep.reactions.delete(this);
    }
    const changed = this.set(newValue);
    this.state = "actual";
    if (changed && this.reactionFn) {
      const currentObserver = CurrentObserver;
      CurrentObserver = null;
      this.reactionFn(!this.runned);
      if(!this.runned) this.runned = true;
      CurrentObserver = currentObserver;
    }
  }
  unsubscribe() {
    for (const dep of this.dependencies) {
      dep.reactions.delete(this);
      if(dep.reactions.size === 0) dep.unsubscribe();
    }
    this.state = "dirty";
  }
}
function runPendingCells() {
  for (const cell of PendingCells) {
    cell.actualize();
  }
}


А теперь описание:

Пусть ячейка будет иметь три состояния — "actual" (которое значит что значение формулы актуально), "dirty" (которое будет значит что как только вызовется get() ячейка должна пересчитаться) и "check". Теперь как только ячейка изменит свое значение она не будет сразу вызывать вычисление подписчиков в каком-либо порядке а пометит своих подписчиков как "dirty". А те в свою очередь тоже пометят своих подписчиков но только значением "check" а те в свою очередь тоже пометят своих подписчиков значением "check", и так далее рекурсивно до конца. То есть только подписчики той ячеки которая изменилась будут иметь значение "dirty" а все остальные до конца дерева — значение "check", а чтобы при рекурсивном вызове мы не зациклились надо вызывать рекурсию только для тех ячеек которые еще не были помечены (имеют значение "actual").



Дальше при достижении конца дерева — то есть той ячейки у которой больше нет подписчиков и она является "активной" надо добавить такую ячейку в неких глобальный массив PendingCells. "Активной" является ячейка которая представляет не какую-то мемоизированную функцию (значение которой может не понадобиться прямо сейчас) а реакция (например компонент реакта) которая должна запускаться каждый раз когда любая из зависимых ячеек меняет свое значение.



В итоге, когда ячейка изменила свое значение и вызвала этот рекурсивный процесс для своих подписчиков, у нас в глобальном массиве PendingCells будут находится некие root-ячейки у которых нет зависимостей но которые прямо или косвенно могут зависеть и соотвественно либо будут пересчитываться (если вдруг все промежуточные ячейки в цепочке поменяют свое значение) либо не будут (если кто-то в этой цепочке при перевычислении не изменит свое значение)



Теперь переходим ко второму этапу. Ячейка которая изменилась и вызвала для своих подписчиков рекурсивный процесс, вызывает некую глобальную функцию flush() которая возьмет ячейки которые накопились в глобальном массиве PendingCells и вызовет у них функцию actualize(). Эта функция будет рекурсивной и будет делать вот что — если значение ячейки является "dirty" она вызовет перевычисление своей формулы (а мы помним что значение "dirty" будут иметь только ячейки которые являются прямыми подписчиками ячейки которая изменилась, а все остальные до конца дерева будут иметь значение "check"). Если же значение равно "check", то ячейка попросит свои зависимые ячейки актуализироваться (вызовет метод actualize()) и после этого снова проверит свое значение и если оно равно "check" то мы меняем значение на "actual" и не вызываем перерасчет, если же оно "dirty" то мы соответственно должны вызвать перевычисление. А теперь если произойдет обращение к ячейке чтобы получить значение формулы в методе .get() ячейка должна проверить свое значение и если оно "check" то она должна вызвать этот метод actualize() а если "dirty" то соотвественно перевычислиться. Вот и все, конец алгоритма.



Итак алгоритм на первый взгляд может показаться сложным но он достаточно простой — когда ячейка меняет свое значение у нас всего 2 этапа — первый этап это рекурсивный спуск чтобы пометить как dirty (для первого уровня) и check для всех остальных а второй этап это рекурсивный подъем при котором происходит актуализация значений.



Теперь проясню некоторые неочевидные моменты.



Первое — каким образом происходит избежание того бага с лишним перерасчетом? Это происходит потому что у нас нет жесткого условия вызывать перевычисление зависимых ячеек у ячейки которая изменились. Зависимые ячейки будут помечены как dirty и все и вычислится только когда где-то потребуется узнать ее значение. То есть, в примере с багом — ячейка fullName будет просто помечена как "dirty" а потом вычислять ее значение не потребуется так как в label выполнится условие firstName.get().length === 3 и label больше не будет зависеть от fullName.



Второе — почему такое странное действие — внутри метода actualize() — проверить — если значение равно "check" то вызвать actualize() у зависимых ячеек и после этого снова повторно проверить значение и если "dirty" то вызвать перерасчет а если "check" то сбросить на actual и ничего не делать? Все дело в том что в процессе вызова actualize() у зависимых ячеек некоторые из них могут иметь значение "dirty" и как мы знаем они должны перевычислиться. А при перевычислении есть условие — если ячейка поменяла свое значение то она должна пометить своих слушателей как "dirty". И таким образом ячейка которая до этого была "check" может после актуализации своих зависимых ячеек сама изменить значение когда изменится кто-либо из них и соотвественно нужно проверить условие снова. Но только в этом случае если никакие зависимые ячейки не изменили свое значение то значит и самой ячейки смысла вычисляться нет и мы меняем значение с "check" на "actual"



Ну а теперь мы можем проверить действие этого алгоритма на нашем примере с багом. Меняется firstName, ячейки label и fullName помечаются как "dirty" и только label попадает в глобальный массив PendingCells потому что fullName не является "активной" ячейкой как label а просто мемоизирует свое значение и обновится только в момент обращения к ней а не сразу. Дальше label поскольку имеет значение "dirty" сразу выполнит перерасчет но поскольку firstName.get().length === 3 значение fullName нам не потребуется и мы таким образом избежим лишнего перевычисления.



Честно сказать описание алгоритма занимает куда больше места чем его реализация. Этот код на typescript а также пример с реактом и тест на баг с вычислениями находится в репозитории (https://github.com/bgnx/xmob)



Источник: Хабрахабр

Категория: Операционные системы » Android

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

Добавление комментария

Имя:*
E-Mail:
Комментарий:
Полужирный Наклонный текст Подчеркнутый текст Зачеркнутый текст | Выравнивание по левому краю По центру Выравнивание по правому краю | Вставка смайликов Выбор цвета | Скрытый текст Вставка цитаты Преобразовать выбранный текст из транслитерации в кириллицу Вставка спойлера
Введите два слова, показанных на изображении: *