---
title: Structure de Pijul
---
# Structures de données
## Les identifiants de patchs
Les patchs sont identifiés par un identifiant global unique, ils vivent dans un espace $P$.
## Le graphe du pristine
Un graphe $G = (V, E)$ dont les sommets $V$ sont des blocs d'octets introduits par un patch, i.e. $V = P\times \mathbb{N} \times \mathbb{N}$, et les arêtes ont une étiquette $(t, p)$ où $t$ est un sous-ensemble de $\{ \mathrm{BLOCK}, \mathrm{PSEUDO}, \mathrm{DELETED}, \mathrm{FOLDER}\}$ est le type de l'arête et $p\in P$. Dans l'implémentation, il y a aussi un flag $\mathrm{PARENT}$, qui n'a qu'une utilité pratique.
Un sommet vide est un sommet $(p, a, b)$ où $a \geq b$.
### Sémantique des arêtes
- Les arêtes sans étiquette représentent la relation d'ordre entre des blocs d'octets, à l'intérieur d'un fichier.
- Les arêtes $t = \mathrm{BLOCK}$ représentent en plus le fait que la destination est considérée comme "vivante" par le patch $p$.
- Les arêtes $t = \mathrm{DELETED}|\mathrm{BLOCK}$ représentent le fait que la destination de l'arête est considérée comme supprimée par le patch $p$. Une étiquette qui a $\mathrm{DELETED}$ sans $\mathrm{BLOCK}$ veut donc dire la même chose qu'une arête sans étiquette.
- Les arêtes où $t = \mathrm{PSEUDO}$ ne viennent pas d'un patch, mais servent de raccourci entre des morceaux du graphe, pour éviter d'avoir à traverser de grandes zones mortes.
- Les arêtes où $t = \mathrm{FOLDER}$ représentent l'arborescence des fichiers et répertoires. Un nœud ne peut pas avoir des arêtes $\mathrm{FOLDER}$ et d'autres arêtes qui pointent vers lui.
### Vie et mort des sommets
Un sommet est "vivant" si toutes ses arêtes entrantes ne sont pas $\mathrm{DELETED}$. Il est mort si toutes ses arêtes entrantes sont $\mathrm{DELETED}$, et zombie dans tous les autres cas.
### Invariants
- Le graphe a un sommet particulier, la *racine*, qui n'a pas d'arêtes entrantes.
- Les arêtes sortantes de la racine pointent (avec des arêtes $\mathrm{FOLDER}$) vers des sommets vides, les *inodes initiaux*.
- Tous les chemins $\mathrm{FOLDER}$ partant des inodes initiaux (et qui ne contiennent pas les inodes initiaux), sont de longueur paire, alternant entre des sommets "noms", dont le contenu a deux octets de méta-données suivis du nom, et des sommets "inodes" qui sont vides.
- Un sommet inode avec un parent nom dont les métadonnées indiquent que c'est un "fichier" n'a pas de descendant $\mathrm{FOLDER}$. Le sous-graphe constitué de l'ensemble des descendants d'un tel inode est un "fichier".
- Les fichiers sont des sous-graphes de $G$ disjoints les uns des autres.
- Tout sommet qui a au moins une arête vivante pointant vers lui, a au moins un chemin composé uniquement d'arêtes non-$\mathrm{DELETED}$ depuis la racine (ce qui inclut souvent des arêtes $\mathrm{PSEUDO}$).
### Conflits
Un graphe sans conflit est la conjonction des propriétés suivantes:
- le sous-graphe $S$ induit par les sommets qui ont au moins une arête entrante vivante est connexe et acyclique, et les répertoires forment un arbre.
- pour tout sommet $v \in V$, toutes les arêtes entrantes de $v$ sont $\mathrm{DELETED}$, ou aucune n'est $\mathrm{DELETED}$.
- pour chaque fichier $F$, le sous-graphe de $F$ induit par les sommets vivants est totalement ordonné.
## Patch
Un patch est un ensemble d'opérations sur le graphe du pristine. Les opérations sont de deux types:
- Ajout d'un sommet, avec des arêtes depuis d'autres sommets et des arêtes vers d'autres sommets. Les arêtes en question sont soit $\mathrm{BLOCK}$ soit $\mathrm{FOLDER}$.
- Remplacement d'une étiquette d'arêtes, appliquée à plusieurs arêtes à la fois.
Les opérations peuvent être regroupées en "hunks" pour faciliter leur lecture, mais c'est un détail d'implémentation.
# Opérations
Dans le dessin suivant, les structures sont dans des rectangles et les opérations dans des ellipses. Dans le code de Pijul, le pristine et la working copy sont génériques et représentées par des traits, ce qui permet de s'abstraire de l'implémentation. En revanche, le format de patch n'est pas générique.
<img src="structure.svg"/>

digraph G {
    Pristine[shape=box, label="Pristine (libpijul::pristine)"];
    WorkingCopy[label="Working copy (libpijul::working_copy)", shape=box];
    Tree[shape=box, label="Tree (libpijul::pristine)"];
    Patch[shape=box, label="Patch (libpijul::patch)"];
    Add[label="Add/Del/Mv (libpijul::fs)"];
    Add -> Tree;
    Output[label="Output (libpijul::output)"];
    Pristine -> Output;
    Output -> WorkingCopy;
    Output -> Tree;
    Record[label="Record (libpijul::record, libpijul::diff)"];
    Tree -> Record;
    WorkingCopy -> Record;
    Record -> Patch;
    Patch -> Apply;
    Apply[label="Apply (libpijul::apply)"];
    Apply -> Pristine;
    Apply -> Tree [style="dotted"];
    Patch -> Unrecord;
    Unrecord[label="Unrecord (libpijul::unrecord)"];
    Unrecord -> Tree [style="dotted"];
    Unrecord -> Pristine;
}