Modéliser la solution plutôt que le problème

Le but de cet exercice est d’implémenter un système "réactif", non pas dans le sens du reactive manifesto, mais dans le sens de la programmation réactive. Il s’agit d’un paradigme dans lequel on se concentre sur la façon dont interagissent des valeurs qui dépendent les unes des autres.

Pour faire simple, pensez à un tableur comme Excel.

Dans un tableur, on peut définir des cellules dont la valeur est le résultat d’une formule portant sur d’autres cellules. Pour ne pas nous mélanger les pinceaux, commençons par nommer les choses :

• Une cellule dont la valeur est renseignée à la main est appelée une InputCell;
• Une cellule dont la valeur est calculée à partir d’autres cellules est appelée une ComputeCell.

Par exemple, on peut définir:

• Une cellule A, de type InputCell,
• Une cellule B, de type InputCell,
• Une cellule C, de type ComputeCell, dont la formule est A + B,
• Une cellule D, de type ComputeCell, dont la formule est A * C.

Si l’on pose A = 2 et B = 3, on obtient automatiquement :

• C = A + B = 2 + 3 = 5,
• D = A * C = 2 * 5 = 10.

Si l’on modifie maintenant A pour qu’elle porte la valeur 3, alors instantanément, C et D sont mises à jour avec :

• C = 6,
• D = 18.

Le but de l’exercice, donc, est d’écrire un tel système en Go, dont l’interface est imposée.

package react

// Un Reactor est responsable de gérer des cellules qui dépendent les unes des autres.
type Reactor interface {
    // CreateInput crée une InputCell en fixant sa valeur initiale.
    CreateInput(int) InputCell

    // CreateCompute1 crée une ComputeCell qui dépend de la valeur d'une seule autre cellule. 
    // La fonction que l'on passe en second argument sert à mettre la ComputeCell à jour 
    // lorsque la valeur dont elle dépend est modifiée.
    CreateCompute1(Cell, func(int) int) ComputeCell

    // CreateCompute2 fait la même chose que CreateCompute1, mais avec une ComputeCell
    // qui dépend de deux autres cellules.
    CreateCompute2(Cell, Cell, func(int, int) int) ComputeCell
}

// Une Cell est conceptuellement un objet qui porte une valeur.
type Cell interface {
    // Value retourne la valeur actuelle de la cellule.
    Value() int
}

// Une InputCell est une Cell dont on peut modifier la valeur.
// Modifier la valeur d'une InputCell déclenche la mise à jour des cellules qui 
// dépendent d'elle.
type InputCell interface {
    Cell

    // SetValue modifie la valeur de la cellule.
    SetValue(int)
}

// Une ComputeCell est une Cell dont la valeur dépend d'autres cellules.
type ComputeCell interface {
    Cell

    // AddCallback permet d'ajouter une fonction de callback qui sera appelée 
    // chaque fois que la ComputeCell est appelée. 
    // Cette fonction retourne un "Canceler" que l'on peut utiliser pour supprimer
    // la fonction de callback.
    AddCallback(func(int)) Canceler
}

// Un Canceler sert à supprimer un callback.
type Canceler interface {
    // Cancel supprime le callback.
    Cancel()
}

Nous allons itérer sur l’implémentation de cette interface, en nous ajoutant des contraintes au fur et à mesure.

Je ne sais pas vous, mais en ce qui me concerne, lorsque l’on me soumet un énoncé pareil en précisant « attention, c’est un exercice difficile », la première chose que je fais; c’est réprimer deux réflexes :

• Se dire « mais non, ça n’a pas l’air bien sorcier ! » ;
• Réfléchir au code en m’imposant dès le départ toutes les contraintes possibles.

En effet, si cet exercice a été flaggé comme « difficile », a fortiori sur un site réputé et très visité comme exercism, c’est probablement parce que l’énoncé cache quelque chose qui n’est pas immédiatement visible. Ainsi, il ne sert à rien de chercher à produire une solution parfaite du premier coup : on a le temps, et rien à prouver à personne.

Pour cette raison, la première approche que j’ai suivie a été d’implémenter une version naïve, en modélisant le problème : on veut des cellules qui se mettent à jour les unes les autres. Ok, commençons donc par modéliser une cellule qui va implémenter les trois interfaces à la fois : Cell, InputCell, ComputeCell.

type cell struct {
    value int
    callbacks []func(int)
}

// Value implémente l'interface Cell
func (c *cell) Value() int {
    return c.value
}

// SetValue implémente l'interface InputCell
func (c *cell) SetValue(v int) {
    c.value = v
}

// Oulà... comment on fait cette histoire de callbacks et de Canceler ?

Étape 1 : Le système de callbacks

Bon, ça commence bien. Il y a un premier truc qui me chiffonne sur l’interface : lorsque l’on ajoute un callback à une cellule, il faut retourner un objet Canceler dont la méthode Cancel supprime le callback. Quand on a déjà fait un peu de Go, cette contorsion est un peu surprenante parce que dans la bibliothèque standard (par exemple dans le module context) on aurait plutôt tendance à retourner une fonction cancel() directement.

Soit, commençons donc par une petite pirouette qui nous permet de retourner une fonction toute bête, mais que l’utilisateur pourra appeler en appelant une méthode Cancel :

// On définit un type qui n'est rien d'autre qu'une fonction en interne.
type canceler func()

// On lui ajoute une méthode Cancel qui appelle la fonction.
// Et voilà, on respecte l'interface Canceler.
func (f canceler) Cancel() {
    f()
}

Maintenant, débarrassons-nous de AddCallback :

// AddCallback implémente l'interface ComputeCell
func (c *cell) AddCallback(cbk func(int)) Canceler {
    // Si la cellule n'a encore aucun callback, il faut allouer la slice
    if c.callbacks == nil {
        // On sait que l'on va ajouter au moins un callback dans cette slice, 
        // donc on l'alloue avec une longueur nulle, mais une capacité de 1, pour éviter 
        // que celle-ci ne se retrouve réallouée dans la foulée par l'appel à append().
        c.callbacks = make([]func(int), 0, 1)
    }
    i := len(c.callbacks)
    c.callbacks = append(c.callbacks, cbk)
    
    return canceler(func() { c.callbacks[i] = nil })
}

Ici, donc, je choisis que "supprimer un callback" consiste juste à remplacer la fonction par nil dans une slice. Ce n’est sûrement pas la façon la plus élégante de gérer ce cas (si jamais l’utilisateur ajoute et supprime des tonnes de callbacks, la slice va devenir un gigantesque gruyère), mais c’est simple et ça fonctionne, donc ça suffira pour commencer¹. On verra une solution alternative plus loin.

Une fois ceci fait, il ne nous reste plus qu’à appeler les callbacks au bon endroit, dans SetValue :

// SetValue implémente l'interface InputCell
func (c *cell) SetValue(v int) {
    c.value = v
    for _, cbk := range c.callbacks {
        if cbk != nil {
            cbk(v)
        }
    }
}

Si vous avez l’habitude du C, vous tiquerez peut-être sur le fait que l’on n’a aucune assurance que c.callbacks ne soit pas nil au moment où on itère dessus. Go s’en fiche. Itérer avec range sur une collection nulle est la même chose qu’itérer sur une collection vide.²

Étape 2 : Coder le reste du foutu Reactor

Maintenant qu’on a bien modélisé des cellules qui appellent des callbacks quand on les met à jour, on doit pouvoir coder facilement le reste du Reactor, non ? Essayons !

Alors, le Reactor doit permettre de retourner une InputCell initialisée avec la valeur choisie…

// Le type reactor va prendre 0 octet en mémoire. C'est cool ça !
// [SPOILER] Ça cache quelque chose...
type reactor struct {}

func New() Reactor {
    return reactor{}
}

func (r reactor) CreateInput(v int) InputCell {
    return &cell{value: v}
}

Passons à la suite. CreateCompute1 doit créer une ComputeCell qui se mettra à jour lorsque la cellule passée en argument est modifiée.

func (r reactor) CreateCompute1(parent Cell, update func(int) int) ComputeCell {
    // On commence par récupérer la cellule concrète derrière l'interface Cell 
    // en laissant Go paniquer si ce n'est pas le bon type (en vrai il faudrait 
    // retourner une erreur, mais la signature de la méthode ne le permet pas).
    p := parent.(*cell)
    
    // On initialise notre cellule en calculant sa valeur grâce à la fonction "update".
    c := &cell{value: update(p.Value())}
    
    // Et maintenant, on fait en sorte que la cellule soit mise à jour chaque fois 
    // que le p est modifiée, en utilisant un callback.
    p.AddCallback(func(v int) { c.SetValue(update(v)) })
    
    return c
}

Facile ! Faisons pareil avec CreateCompute2.

func (r reactor) CreateCompute2(parent1, parent2 Cell, update func(int, int) int) ComputeCell {
    p1 := parent1.(*cell)
    p2 := parent2.(*cell)
    
    c := &cell{value: update(p1.Value(), p2.Value())}
    
    p1.AddCallback(func(v int) { c.SetValue(update(v, p2.Value())) })
    p2.AddCallback(func(v int) { c.SetValue(update(p1.Value(), v)) })
    
    return c
}

Eh bien je ne vois vraiment pas ce que cet exercice avait de difficile. C’est déjà fini !

Nous n’avons plus qu’à tester notre code avant d’aller prendre un café bien mérité…

À première vue, ça marche…

Reproduisons l’exemple que j’ai donné dans l’énoncé pour nous assurer que ça fonctionne.

package main

import (
    "billet_react/react"
    "fmt"
)

func main() {
    r := react.New()
    a := r.CreateInput(2)
    b := r.CreateInput(3)
    c := r.CreateCompute2(a, b, func(a, b int) int { return a + b })
    d := r.CreateCompute2(a, c, func(a, c int) int { return a * c })
    fmt.Printf("Valeurs initiales: c = %d, d = %d\n", c.Value(), d.Value())
    a.SetValue(3)
    fmt.Printf("Nouvelles valeurs: c = %d, d = %d\n", c.Value(), d.Value())
}

Voici le résultat:

Valeurs initiales: c = 5, d = 10
Nouvelles valeurs: c = 6, d = 18

Super ! C’est exactement ce qu’on voulait.

… mais un bug sauvage apparaît !

Allez, on va se raconter ça sous la forme d’une petite histoire rigolote.

Vous faites partie du département IT d’une entreprise de distribution. L’entreprise n’a pas de stock, chaque fois qu’elle enregistre une commande, elle va acheter le produit chez son fournisseur et le revendre en se payant une marge de 33%.

Vous allez donc confier votre système au Grand Patron™ qui va s’en servir pour surveiller sa trésorerie :

    r := react.New()

    solde := r.CreateInput(0)
    coutAchat := r.CreateInput(100)
    prixVente := r.CreateInput(150)
    nbCommandes := r.CreateInput(0)

    depenses := r.CreateCompute2(
        coutAchat, nbCommandes,
        func(c, n int) int { return c * n },
    )
    recettes := r.CreateCompute2(
        prixVente, nbCommandes,
        func(p, n int) int { return p * n },
    )
    resultat := r.CreateCompute2(
        depenses, recettes,
        func(d, r int) int { return r - d },
    )
    nouveauSolde := r.CreateCompute2(
        solde, resultat,
        func(s, r int) int { return s + r },
    )

Bien ! Chaque fois qu’on va enregistrer une commande, tout ce joli monde va se mettre à jour et la cellule nouveauSolde va contenir le nouveau solde du compte en banque.

Évidemment, vous ne manquez pas de montrer au Grand Patron™ votre killer feature, le système de callback. Celui-ci va s’empresser d’ajouter une alerte par SMS :

    nouveauSolde.AddCallback(func(v int) {
        if v < 0 {
            fmt.Printf("[ALERTE] Solde négatif : %d€\n", v)
        }
    })

La nuit suivante, vers 3h du matin, le Super Commercial™ qui se trouve à Perpète, sur un autre continent, conclut le deal du siècle et enregistre 100 commandes d’un coup.

Testons ce scénario :

    fmt.Printf("Solde initial : %d€\n", nouveauSolde.Value())
    fmt.Println("On enregistre 100 commandes...")
    nbCommandes.SetValue(100)
    fmt.Printf("Solde final : %d€\n", nouveauSolde.Value())

Voici le résultat :

Solde initial : 0€
On enregistre 100 commandes...
[ALERTE] Solde négatif : -10000€
Solde final : 5000€

Ainsi, le Grand Patron™ est réveillé par un SMS au beau milieu de la nuit, lui indiquant qu’il est DANS LE ROUGE!! Il se lève en sursaut, gesticule, cherche sa robe de chambre, panique, entreprend de détruire son mobilier, se ravise, commence à fulminer, reprend son téléphone et appelle sa banque. Après avoir traité la personne au bout du fil de tous les noms, il finit par faire réveiller un superviseur qui lui assure, vingt minutes plus tard, que tout va bien. Tout ce qu’il voit, c’est un compte créditeur de 5000€.

Le lendemain matin, vous êtes viré. Ça vous apprendra à faire des blagues.

Heureusement, ce n’est qu’une histoire : il n’y a ni Grand Patron™, ni Super Commercial™. Tout ça n’est qu’un exercice, et vous venez simplement d’avoir une illustration de sa difficulté.

Caractériser le problème

Ce qui rend ce bug particulièrement vicieux, c’est que dans notre cas, il suffit d’inverser l’ordre de déclaration des deux premières ComputeCell pour le faire disparaître :

    recettes := r.CreateCompute2(
        prixVente, nbCommandes,
        func(p, n int) int { return p * n },
    )
    depenses := r.CreateCompute2(
        coutAchat, nbCommandes,
        func(c, n int) int { return c * n },
    )

Résultat:

Solde initial : 0€
On enregistre 100 commandes...
Solde final : 5000€

En fait, il est assez simple de remarquer ce qui ne va pas. Si l’on ajoute un callback sur chacune de nos cellules pour vérifier ce qui se passe, on observe ce qui suit :

Solde initial : 0€
On enregistre 100 commandes...
MàJ des dépenses : 10000
MàJ du résultat : -10000
MàJ du nouveau solde : -10000
[ALERTE] Solde négatif : -10000€
MàJ des recettes : 15000
MàJ du résultat : 5000
MàJ du nouveau solde : 5000
Solde final : 5000€

Ce qui se passe avec ce code, c’est que lors de la mise à jour, les cellules sont susceptibles de traverser des états intermédiaires instables, et donc de produire ce genre de gags qui réveillent les gens pour rien à 3h du mat'¹, avant d’être stabilisées sur le résultat final.

Hormis les problèmes de performances qui risquent de se poser dans les cas pathologiques (on risque de réaliser beaucoup plus de calculs que nécessaire…), on a un véritable problème fonctionnel : quand on met à jour une cellule, on ne peut pas savoir si l’état dans lequel on la place est stable ou non. À cela, on peut ajouter un autre problème : en l’état, si une cellule est actualisée sans changer de valeur, ses callbacks seront quand même appelés. On risque donc de spammer l’utilisateur avec des mises à jour qui n’en sont pas.

J’ai une bonne et une mauvaise nouvelle à vous annoncer :

• La bonne nouvelle, c’est que l’un de ces deux bugs se solutionne avec un bête if/else, et que pour le moment il nous arrange parce qu’il nous donne une façon simple d’observer notre algorithme en action ;
• La mauvaise nouvelle, c’est que pour l’autre bug, on va devoir faire un peu de théorie des graphes.

Avance rapide !

Vu que tout ceci n’est qu’un billet, je vais passer très rapidement sur une solution intermédiaire.

Vous aurez certainement compris que le principal défaut de notre solution naïve, c’est qu’elle utilise les callbacks de l’interface ComputeCell pour propager les nouvelles valeurs des InputCell : on ne devrait mettre à jour une cellule qu’une fois que l’on est certain que son nouvel état est définitif. Autrement dit : on ne devrait mettre à jour chaque ComputeCell qu'une seule fois grand max.

Bien, maintenant, remarquons une propriété sympa de l’interface qui nous est imposée : puisque, pour créer une ComputeCell, nous avons besoin de lui passer ses dépendances, cela veut dire qu’une cellule donnée peut dépendre que des cellules créées avant elle, et donc qu'il suffit de mettre à jour les cellules dans l’ordre dans lequel elles ont été créées pour garantir qu’elles atteindront un état stable du premier coup.

Sachant cela, notre solution intermédiaire consiste à :

• stocker dans une slice (appartenant au Reactor) des fonctions qui déclenchent la mise à jour de chaque ComputeCell, au fur et à mesure que celles-ci sont créées ;
• lorsqu’une InputCell est mise à jour, déclencher la mise à jour de toutes les ComputeCell, dans le bon ordre, en itérant sur cette slice.

Ce n’est pas très compliqué à coder :

type reactor struct {
    update []func()
}

func New() Reactor {
    return &reactor{
        update: make([]func(), 0),
    }
}

func (r *reactor) CreateInput(v int) InputCell {
    c := &cell{value: v}
    c.AddCallback(func(v int) {
        for _, up := range r.update {
            up()
        }
    })
    return c
}

func (r *reactor) CreateCompute1(parent Cell, update func(int) int) ComputeCell {
    c := &cell{value: update(parent.Value())}
    r.update = append(r.update, func() {
        c.SetValue(update(parent.Value()))
    })
    return c
}

func (r *reactor) CreateCompute2(p1, p2 Cell, update func(int, int) int) ComputeCell {
    c := &cell{value: update(p1.Value(), p2.Value())}
    r.update = append(r.update, func() {
        c.SetValue(update(p1.Value(), p2.Value()))
    })
    return c
}

On remarquera au passage que l’on n’a plus besoin de faire des casts sauvages dans les méthodes CreateCompute*. C’est un signe ! Mais surtout, on constate que tout se met à jour en une seule passe :

Solde initial : 0€
On enregistre 100 commandes...
MàJ des dépenses : 10000
MàJ des recettes : 15000
MàJ du résultat : 5000
MàJ du nouveau solde : 5000
Solde final : 5000€

Parfait, on ne réveillera plus les gens pour rien.

Cela dit, cette solution ne devrait normalement pas vous satisfaire. En effet, si le système possède un million de ComputeCell, mais que l’on met à jour une cellule dont dépend une seule ComputeCell, on se retrouve à exécuter neuf cent quatrevingt-dix-neuf mille neuf cent quatrevingt-dix-neuf (999 999) mises à jour inutiles.

On peut aisément le vérifier sur notre exemple, en mettant à jour le prix de vente et en constatant que cela déclenche une mise à jour des dépenses qui n’ont pourtant rien à faire de cette variable (et n’ont donc pas besoin d’être mises à jour).

Solde initial : 0€
On enregistre 100 Commandes...
MàJ des dépenses : 10000
MàJ des recettes : 15000
MàJ du résultat : 5000
MàJ du nouveau solde : 5000
On diminue diminue le prix de vente à 120€...
MàJ des dépenses : 10000
MàJ des recettes : 12000
MàJ du résultat : 2000
MàJ du nouveau solde : 2000
Solde final : 2000€

Cherchons un algorithme un peu plus intelligent que ça.

Fermeture transitive d’un noeud dans un graphe

Donc, soyons clairs, nous sommes en train de réfléchir sur une relation de dépendance. La meilleure façon de modéliser ça, c’est de dessiner un graphe.

  [coutAchat]  [nbCommandes]  [prixVente]
          \      /      \      /
         (depenses)    (recettes)
                 \      /
                (resultat)        [solde]
                        \          /
                       (nouveauSolde)

Légende: 
   [InputCell]
   (ComputeCell)

Ce que l’on appelle la fermeture transitive d’un noeud dans un graphe comme celui-là, c’est l’ensemble de tous les noeuds que l’on peut atteindre en suivant un chemin valide dans le graphe. Par exemple :

• la fermeture transitive de coutAchat est l’ensemble {depenses, resultat, nouveauSolde},
• la fermeture transitive de solde est l’ensemble {nouveauSolde}.

Dans notre cas, la fermeture transitive d’une InputCell, c’est l’ensemble des ComputeCell qui ont besoin d’être mises à jour chaque fois qu’elle est modifiée.

Tant que nous y sommes, définissons l’ensemble d’entrée d’une ComputeCell comme l’ensemble des InputCell dont la modification entraîne sa mise à jour. Les deux affirmations suivantes sont alors équivalentes :

• c appartient à la fermeture transitive de i,
• i appartient à l’ensemble d’entrée de c.

Notre nouvelle solution peut donc se décrire ainsi :

• À tout instant, on garde sous la main :
  • la fermeture transitive de chaque InputCell,
  • l’ensemble d’entrée de chaque ComputeCell.
• Lorsque l’on crée une nouvelle ComputeCell, on récupère son ensemble d’entrée (en fusionnant ceux de ses parents), puis on ajoute la nouvelle cellule à la fermeture transitive de chaque InputCell de son ensemble d’entrée.
• Lorsque l’on modifie la valeur d’une InputCell, on déclenche la mise à jour, dans leur ordre de création, de chaque ComputeCell de sa fermeture transitive.

Allez, on va faire ça.

Vous vous rappelez tous ces petits détails qui me faisaient tiquer dans l’implémentation naïve ? Ce sont autant de signes que les structures de données que nous avons construites sont mal conçues.

Prenons le temps d’y revenir pour rectifier le tir.

Implémenter une collection de callbacks

Jusqu’ici, nos callbacks étaient référencés dans une slice, ce qui avait le mérite de fixer l’ordre dans lequel ceux-ci sont exécutés. Cependant, ici, nous avons plutôt besoin d’un ensemble (set) de callbacks :

• On se fiche de l’ordre dans lequel les callbacks sont appelés ;
• Ce serait mieux si on n’avait pas à parsermer notre structure d’entrées nulles au fur et à mesure que l’on supprime des callbacks.

La façon la plus idiomatique de réaliser ceci en Go est d’utiliser une map (comme un dictionnaire en Python). Réglons donc le problème en implémentant une structure callbackMap supportant les méthodes Add, Remove et Trigger.

type callbackID uint64
type callbackFunc func(int)

type callbackMap struct {
    nextID    callbackID
    callbacks map[callbackID]callbackFunc
}

func (c *callbackMap) newCallbackID() callbackID {
    id := c.nextID
    c.nextID++
    return id
}

// Add ajoute un nouveau callback et retourne une clé permettant de supprimer
// celui-ci.
func (c *callbackMap) Add(cbk func(int)) callbackID {
    id := c.newCallbackID()
    if c.callbacks == nil {
        c.callbacks = make(map[callbackID]callbackFunc)
    }
    c.callbacks[id] = cbk
    return id
}

// Remove supprime un callback
func (c *callbackMap) Remove(id callbackID) {
    delete(c.callbacks, id)
}

// Trigger exécute tous les callbacks en leur passant la valeur voulue
func (c *callbackMap) Trigger(v int) {
    for _, cbk := range c.callbacks {
        cbk(v)
    }
}

Attention aux références circulaires !

Un autre détail sur lequel j’ai ouvertement tiqué dans notre première implémentation était que notre structure reactor était vide. En effet, nous avions centré notre modélisation sur les cellules, et partant de là, pratiquement toute l’intelligence se retrouvait implémentée dans la structure cell. Si l’on continue sur cette lancée, on va se heurter à un mur, car on s’apprête à maintenir une relation réciproque dans notre modèle :

• Les InputCell doivent référencer les ComputeCell de leur fermeture transitive ;
• Les ComputeCell doivent référencer les InputCell de leur ensemble d’entrée.

D’après ce que nous avons établi plus haut et sachant que dans notre modélisation, une "référence" sur une autre cellule était typiquement un pointeur sur cette cellule, nous risquons de créer des références circulaires qui rendent n’importe quel garbage collector incapable de libérer la mémoire, même lorsque nos cellules ne seront plus accessibles nulle part dans notre programme.

Le meilleur moyen de casser ces références circulaires, c’est de créer une abstraction dont vont dépendre InputCell et ComputeCell pour se référencer mutuellement. Autrement dit, les références ne doivent pas être des pointeurs, mais plutôt des "clés" comme les indices d’un tableau. Un tableau qui serait maintenu, par exemple, dans le Reactor…

Attention à la thread safety !

Dans beaucoup de langages, on pourrait se dire que la thread safety est un luxe dont on peut se passer, mais Go est un langage concurrent par nature : du moment que l’on expose une interface, on doit s’attendre à ce que quelqu’un veuille se mettre à l’utiliser dans des goroutines indépendantes. Autrement dit, si l’on fait quelque chose qui puisse servir dans la vraie vie, il vaut mieux que ce soit threadsafe.

Cette contrainte nous amène au même constat que le problème des références circulaires. En effet, si une InputCell est modifiée, alors celle-ci doit verrouiller (Mutex.Lock()) l’ensemble des ComputeCell de sa fermeture transitive avant de réaliser la moindre mise à jour. Or, dans notre implémentation naïve, toutes ces cellules sont des objets indépendants les uns des autres : ça voudrait dire que l’on les verrouille dans une boucle.

Seulement voilà : dans ce scénario, si plusieurs InputCell distinctes sont mises à jour en même temps, elles se lancent dans une course effrénée (à qui verrouillera sa fermeture transitive la première). Dans le cas de deux mises à jour simultanées, cela va encore bien se passer, mais à partir de trois, c’est susceptible d’engendrer un deadlock.¹

En revanche, si ce ne sont plus aux InputCell mais au Reactor qu’échoit la responsabilité de faire cette mise à jour, celui-ci peut verrouiller toutes ses ressources en un seul Lock(), et donc s’accomoder très facilement d’être utilisé par des dizaines de goroutines indépendantes.

Les données ET l’intelligence doit donc être implémentées dans le Reactor, et non dans les cellules.

Les cellules

Au vu de tout ce que nous venons de voir, voici ce à quoi va ressembler nos nouvelles cellules :

type cellID int

type cell struct {
    r  *reactor
    id cellID
}

func (c cell) Value() int {
    return c.r.ValueAt(c.id)
}

func (c cell) SetValue(v int) {
    c.r.SetValueAt(c.id, v)
}

func (c cell) AddCallback(cbk func(int)) Canceler {
    return c.r.AddCallbackAt(c.id, cbk)
}

Comme précédemment, notre type cell implémente les trois interfaces (Cell, InputCell, ComputeCell) à la fois, mais cette fois-ci, nos cellules sont débiles. Elles se contentent de référencer le reactor et de garder leur id. Elles ne sont d’ailleurs même pas mutables : aucune des opérations que nous pouvons exécuter dessus ne modifie leur état interne. C’est pour cette raison que nous allons pouvoir nous permettre de transmettre celles-ci par valeur plutôt que par référence : remarquez que les méthodes portent sur cell et non sur *cell.

Le reste du foutu Reactor…

Cette fois, notre reactor va être beaucoup plus costaud.

type updateFunc func([]int) int

type reactor struct {
    cells     []int
    updates   []updateFunc
    closure   [][]cellID
    callbacks map[cellID]*callbackMap
    mtx       sync.Mutex
}

func New() Reactor {
    return &reactor{
        cells:     make([]int, 0),
        updates:   make([]updateFunc, 0),
        closure:   make([][]cellID, 0),
        callbacks: make(map[cellID]*callbackMap, 0),
    }
}

Les trois premiers champs sont des slices de même longueur : le nombre de cellules gérées par le Reactor.

Les cellules sont de simples entrées dans une slice d’entiers (cells), et on se référera à elles via leur cellID. La seconde slice, updates, va contenir les fonctions de mise à jour des ComputeCells. Une cellule dont l’entrée est nil dans cette slice est une InputCell. Remarquez la signature de ces fonctions : elles prennent en entrée la totalité des cellules et retournent une valeur.

La troisième slice, closure, va contenir :

• La fermeture transitive des InputCell,
• L’ensemble d’entrée des ComputeCell.

Ensuite, nous allons stocker les ensembles de callbacks des cellules dans un map, car il est très probable que seulement une petite partie des cellules ait réellement des callbacks associés.

Pour terminer, notre structure embarque un Mutex qui nous servira à la rendre threadsafe. À ce propos, il est important de savoir dès le départ quelles méthodes on va devoir protéger avec ce mutex. En effet, certaines des méthodes que nous nous apprêtons à implémenter seront appelées de l’intérieur du reactor, et d’autres de l’extérieur : ce sont bien sûr les secondes qu’il est nécessaire de protéger, mais surtout pas les premières (au risque de créer des deadlocks). Nous allons donc, dans ce code, utiliser la convention de nommage de Go : nos méthodes privées commenceront par une minuscule, et les méthodes exposées à l’extérieur par une majuscule.

Ainsi, pour accéder à la valeur d’une cellule depuis l’intérieur du reactor, il nous suffira d’accéder à r.cells[id], mais depuis l’extérieur, nous allons devoir utiliser une méthode dédiée :

func (r *reactor) ValueAt(id cellID) int {
    r.mtx.Lock()
    defer r.mtx.Unlock()
    return r.cells[id]
}

De la même manière, pour modifier la valeur d’une cellule, nous allons définir deux méthodes, dont une seule sera publique :

• setValueAt modifie la valeur et retourne true si la valeur a bien été modifiée.
• updateAt déclenche la mise à jour d’une ComputeCell et appelle ses callbacks si celle-ci a bien été modifiée.
• SetValueAt sera appelée par le biais d’une InputCell, pour mettre à jour sa valeur et déclencher les mises à jour.

func (r *reactor) setValueAt(id cellID, v int) bool {
    if r.cells[id] == v {
        return false
    }
    r.cells[id] = v
    return true
}

func (r *reactor) updateAt(id cellID) {
    val := r.updates[id](r.cells)
    if !r.setValueAt(id, val) {
        return
    }
    callbacks := r.callbacks[id]
    if callbacks != nil {
        callbacks.Trigger(val)
    }
}

func (r *reactor) SetValueAt(id cellID, v int) {
    r.mtx.Lock()
    defer r.mtx.Unlock()
    if !r.setValueAt(id, v) {
        return
    }
    for _, i := range r.closure[id] {
        r.updateAt(i)
    }
}

Passons maintenant aux callbacks. La seule réelle subtilité, c’est de bien penser à protéger l’ajout et la suppression au moyen du mutex.

func (r *reactor) AddCallbackAt(id cellID, cbk func(int)) Canceler {
    r.mtx.Lock()
    defer r.mtx.Unlock()
    if cbk == nil {
        return canceler(func() {})
    }
    if r.callbacks[id] == nil {
        r.callbacks[id] = new(callbackMap)
    }
    key := r.callbacks[id].Add(cbk)
    return canceler(func() {
        r.removeCallbackAt(id, key)
    })
}

func (r *reactor) removeCallbackAt(id cellID, key callbackID) {
    r.mtx.Lock()
    defer r.mtx.Unlock()
    r.callbacks[id].Remove(key)
}

Les cellules

Bien, il ne nous reste "plus qu’à" gérer la création de nos cellules.

Commençons par une petite méthode utilitaire, newCell, qui va simplement se charger d’allouer un nouveau slot dans chacune des slices du reactor, et retourner le cellID de la cellule nouvellement créée :

func (r *reactor) newCell(v int) cellID {
    id := len(r.cells)
    r.cells = append(r.cells, v)
    r.updates = append(r.updates, nil)
    r.closure = append(r.closure, make([]cellID, 0, 1))
    return cellID(id)
}

Pas de difficulté particulière ici. Cette méthode rend même triviale l’implémentation de CreateInput.

func (r *reactor) CreateInput(v int) InputCell {
    r.mtx.Lock()
    defer r.mtx.Unlock()
    return cell{r, r.newCell(v)}
}

C’est maintenant que ça se corse. Lorsque l’on crée une ComputeCell nous allons avoir besoin de l’ajouter au graphe de dépendances du reactor, c’est-à-dire celui qui est décrit par son champ closure. Nous allons devoir :

• Récupérer les ensembles d’entrée de ses parents et les fusionner dans sa closure,
• Ajouter le nouveau cellID dans la closure de toutes les cellules de son ensemble d’entrée.

Petite subtilité supplémentaire : cette méthode sera appelée avec un ou deux parents. Elle doit donc être variadique.

func (r *reactor) addComputeCell(id cellID, parents ...cellID) {
    inputSet := make(map[cellID]bool)
    for _, p := range parents {
        if r.updates[p] == nil {
            // p est une InputCell
            // on l'ajoute directement à l'ensemble d'entrée
            inputSet[p] = true
            continue
        }
        for _, i := range r.closure[p] {
            // p est une ComputeCell
            // on fusionne son ensemble d'entrée à celui de la nouvelle cellule
            inputSet[i] = true
        }
    }
    // On réalloue directement l'ensemble d'entrée de la cellule avec la bonne capacité
    r.closure[id] = make([]cellID, 0, len(inputSet))
    for i := range inputSet {
        r.closure[id] = append(r.closure[id], i)
        r.closure[i] = append(r.closure[i], id)
    }
}

Et maintenant, il ne nous reste plus qu’à recoller les morceaux avec les deux méthodes CreateCompute*

func (r *reactor) CreateCompute1(parent Cell, update func(int) int) ComputeCell {
    p, ok := parent.(cell)
    if !ok || p.r != r {
        // Normalement on devrait retourner une erreur, mais la signature ne le
        // permet pas.
        panic("Parent cell doesn't belong to this reactor")
    }
    // Petite subtilité : on récupère l'ID de la cellule parente dans une
    // variable pour que seul cet ID (et pas toute la cellule parente) se 
  // trouve embarqué dans la closure de la fonction d'update.
    // En effet, puisque p possède une référence sur r, si on l'embarque dans
    // f, alors cela crée une référence circulaire r -> f -> p -> r.
    pid := p.id
    f := func(cells []int) int {
        return update(cells[pid])
    }

    r.mtx.Lock()
    defer r.mtx.Unlock()

    id := r.newCell(f(r.cells))
    r.updates[id] = f
    r.addComputeCell(id, pid)
    return cell{r, id}
}

func (r *reactor) CreateCompute2(parent1, parent2 Cell, update func(int, int) int) ComputeCell {
    p1, ok := parent1.(cell)
    if !ok || p1.r != r {
        panic("parent1 cell doesn't belong to this reactor")
    }
    p2, ok := parent2.(cell)
    if !ok || p2.r != r {
        panic("parent2 cell doesn't belong to this reactor")
    }
    pid1, pid2 := p1.id, p2.id
    f := func(cells []int) int {
        return update(cells[pid1], cells[pid2])
    }

    r.mtx.Lock()
    defer r.mtx.Unlock()

    id := r.newCell(f(r.cells))
    r.updates[id] = f
    r.addComputeCell(id, pid1, pid2)
    return cell{r, id}
}

Et voilà le travail !

Testons rapidement le dernier scénario que nous avions créé (Super Commercial™ enregistre 100 commandes, puis on modifie le prix de vente) :

Solde initial : 0€
On enregistre 100 Commandes...
MàJ des dépenses : 10000
MàJ des recettes : 15000
MàJ du résultat : 5000
MàJ du nouveau solde : 5000
On diminue diminue le prix de vente à 120€...
MàJ des recettes : 12000
MàJ du résultat : 2000
MàJ du nouveau solde : 2000
Solde final : 2000€

Tout se comporte maintenant comme prévu.