---
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.


## Channel

Un channel est un graphe de pristine avec la liste des identifiants de patchs qui lui ont été appliqués.


## Arbre

L'arbre est une représentation des répertoires et fichiers de la copie de travail qui sont suivis par Pijul. Les éléments (fichiers/répertoires) y sont nommés et ont un identifiant local unique, attribué aléatoirement quand ils sont enregistrés dans l'arbre. Deux dépôts, même clonés depuis la même origine, ont donc des identifiants de fichiers différents. Lorsque les éléments sont aussi dans le pristine, une table fait correspondre ces identifiants locaux aux sommets du graphe.

# Remote

Chaque channel génère à sa création un identifiant global unique. Les dépôts conservent un historique des channels avec lesquels ils interagissent, afin d'accéler les synchronisations futures.

# 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"/>

Le fait que la structure soit cyclique n'aide pas vraiment à comprendre le fonctionnement général. Dans l'ordre dans lequel un utilisateur rencontre les commandes:

## Add/Rm/Mv

Add ajoute des éléments dans l'arbre, Rm les supprime et Mv les déplace.

## Record

Record parcourt les chemins du pristine qui sont $\mathrm{FOLDER}$ et calcule les changements par rapport à l'arbre. Pour chaque fichier, record appelle diff, qui travaille sur les lignes, mais conserve une correspondance entre les lignes et les nœuds du graphe.

## Apply

On applique un patch, en racommodant avec des arêtes $\mathrm{PSEUDO}$ les morceaux qui peuvent avoir été déconnectés par l'application du patch. Dans le cas d'un patch qui vient d'être produit localement, il faut mettre à jour l'*arbre* pour indiquer que tel sommet du pristine correspond à tel fichier local.

## Output

Transformer le graphe du pristine en un ensemble de fichiers que l'on peut écrire sur le disque. Il s'agit d'un mélange d'algorithmes classiques (composantes connexes de Tarjan et DFS) pour détecter les conflits.

## Unrecord

Enlever un patch d'un channel si aucun autre patch du channel ne dépend de lui. C'est presque le même algo que Apply, avec un certain nombre de subtilités liées aux conflits. Unrecord doit dans certains cas modifier le tree.

## Push/pull

Mise à jour du remote, puis comparaison depuis le dernier état global commun, trouvé par dichotomie. Notons que dans des cas très défavorables ou les patchs sont les mêmes mais dans des ordres très différents, il est possible de ne trouver aucun état commun. Dans ce cas, le calcul peut prendre du temps, mais se fait uniquement en local (pas de latence réseau).

Ensuite, on record un patch temporaire des changements en cours, on applique les nouveaux patchs, on fait un output, et on unrecord le patch temporaire.