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

Итак в прошлой статье для того чтобы компоненты реакта автоматически подписывались на данные которые они рендерят и при изменении вызывался перерендер только нужных компонентов мы пришли к такой модификации observer паттерна

let CurrentObservables = null;
class Observable {
  listeners = new Set();
  constructor(value){
    this.value = value
  }
  get(){
    if(CurrentObservables) CurrentObservables.add(this);
    return this.value;
  }
  set(newValue){
    if(newValue !== this.value){
      this.notify();
    }
  }
  subscribe(listener){
    this.listeners.add(listener)
  }
  unsubscribe(listener){
    this.listeners.delete(listener)
  }
  notify(){
    for(const listener of this.listeners){
       listener();
    }
  }
}
function connect(target){
  return class extends (target instanceof React.Component ? target : React.Component) {
     stores = new Set();
     listener = ()=> this.setState({})
     render(){
        this.stores.forEach(store=>store.unsubscribe(this.listener));
        this.stores.clear();
        const prevObservables = CurrentObservables;
        CurrentObservables = this.stores;
        cosnt rendered = target instanceof React.Component ? super.render() : target(this.props);
        this.stores = CurrentObservables;
        CurrentObservables = prevObservables;
        this.stores.forEach(store=>store.subscribe(this.listener));
        return rendered;
     }
     componentWillUnmount(){
      this.stores.forEach(store=>store.unsubscribe(this.listener));
     }
  }
}

Давайте немного отрефакторим — вынесем логику установки глобального массива внутрь самого обзервера. Это можно представить как например ячейки таблицы в гугл-докс — есть ячейка которая просто хранит значение а есть ячейка которая хранит не только значение (которое будет закешировано) а и формулу(функцию) для ее пересчета. И заодно кроме формулы функции-пересчета мы добавим еще параметр функции для выполнения сайд-эффектов, как например вызов setState({}) на компоненте, когда у нас изменится значение. В итоге получим вот такой вот класс Cell

let CurrentObserver = null
class Cell {
  reactions = new Set();
  dependencies = new Set();
  tracked = false;
  constructor(value,  fn = null, reactionFn = null) {
    this.value = value;
    this.fn = fn;
    this.reactionFn = reactionFn
  }
  get() {
    if (this.fn && !this.tracked) this.run();
    if (CurrentObserver) {
      this.reactions.add(CurrentObserver);
      CurrentObserver.dependencies.add(this);
    }
    return this.value;
  }
  set(newValue) {
    if (newValue !== this.value) {
      this.value = newValue;
      for (const reaction of this.reactions) {
        reaction.run();
      }
      return true;
    } else {
      return false;
    }
  }
  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);
    if (changed && this.tracked && this.reactionFn){
      const currentObserver = CurrentObserver;
      CurrentObserver = null;
      this.reactionFn();
      CurrentObserver = currentObserver;
    }
    this.tracked = true;
  }
  unsubscribe(){
    for(const dep of this.dependencies){
      dep.reactions.delete(this);
    }
    this.tracked = false;
  }
}

function connect(target){
  return class extends (target instanceof React.Component ? target : React.Component) {
    constructor(...args){
      super(...args);
      this._cell = new Cell(null, ()=>{
        return target instanceof React.Component ? super.render() : target(this.props);
      }, ()=>{
        this.forceUpdate(); //здесь вместо setState({}) используется forceUpdate() потому что у компонента может и не быть своего состояния
      });
    }
    render(){
      return this._cell.get();
    }
    componentWillUnmount(){
      this._cell.unsubscribe();
    }
  }
} 

Теперь выясним режимы обновления нашей обcерверов. В примере выше у нас пока все обcерверы активные — после того как первый раз вызвался .get он подписался на свои dependencies и будет вызываться каждый раз когда какая-то зависимость изменит свое значение. Этот режим удобен для компонентов которые должны обновляться каждый раз когда изменились данные на которые они подписаны но есть так называемые "кешируемые" или "мемоизированные" функции для которых такое поведение нежелательно. Например есть обзервер const fullName = new Cell(()=>firstName.get() + lastName.get()) который должен вычислять полное имя когда изменится либо имя либо фамилия. Но что если после того как он вычислится к fullName в приложении при каких-то условиях обращаться не придется? Мы получим лишнее вычисление и чтобы этого избежать можно сделать так чтобы компонент вычислялся не сразу а только когда к не нему обратятся — при вызове .get().

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

Давайте рассмотрим такую ситуацию — есть четыре ячейки — firstName, lastName, fullName (которая вычисляет полное имя) и label (которая выводит либо имя если оно длинное иначе полное имя)

const firstName = new Cell("fff");
const lastName = new Cell("lll"); 
const fullName = new Cell("", ()=>firstName.get() + " " + lastName.get());
const label = new Cell("", ()=>firstName.get().length <= 3 ?  fullName.get() : firstName.get()))

Здесь самый простой вариант ромбовидных зависимостей — от firstName зависит fullName, от fullName зависит label но label также зависит и от firstName и получается как бы цикл.
Надо уточнить что в процессе нас интересует перевычисление только значения ячейки label (например нужно отрендерить в компоненте) поэтому если значение fullName для label вдруг вычислять не требуется то его вычислять и не стоит.

И вот первый баг — при измении firstName — в нашей реализацией Cell когда мы вы цикле вызываем подписчиков у нас компонент label будет вычисляться дважды — первый раз firstName вызовет label потому что он непосредственно него подписан, а второй раз label вычисляется когда fullName изменит свое значение. Первое вычисление label не нужно потому что содержит временные данные — новое имя и старое fullName. Соотвественно нам нужно избавиться от ненужных вычислений и сделать мы это можем только вызвав подписчиков в правильном порядке — сначала fullName а потом label.

Как мы это можем сделать? Если подумать то есть парочка вариантов.

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



Вкратце алгоритм состоит из способа распространения вызова функции по графу зависимостей и выявление значение "глубины" каждой зависимости через инкремент-декремент счетчика и потом вызов их в порядке увеличения глубины. Пусть при изменении имени, ячейка 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) {
    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) {
        if(this.state === "dirty") break;
        dep.actualize();
      }
      if(this.state === "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" то мы соответственно должны вызвать перевычисление. При этом, проверку на "dirty" нужно после вызова "actualize()" на каждой зависимой ячейке, потому что если ячейка приняла значение "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)