⚠ Je ne te demande pas de me le réexpliquer avec d'autres mots, et surtout pas des termes mathématiques! ⚠
En complément du commentaire d'Adrien Dorsaz, je vais quand même essayer. Mais ne t'inquiète pas, ce sera des mathématiques simples : de l'arithmétique élémentaire avec les nombres entiers, et un peu de graphes.
Une image que j'aime bien et qui représente des historiques possibles d'un dépôt est celle-ci :
diagramme de merge
On peut résumer le cœur d'un gestionnaire de version à cette interface rudimentaire :
type patch
type state
val commit : patch -> state -> state
val merge : state -> state -> state
Il y a deux concepts : les patchs et les états, puis deux fonctions pour appliquer un patch sur un état ou fusionner deux états. Ainsi, sur le graphe du dessus, on a par exemple :
A = commit p O
M = merge A B
Plutôt que de travailler avec des fichiers et des répertoires, commençons plus simple et travaillons avec des entiers naturels. Les états (ou sommets du graphes) sont des entiers et les patchs sont aussi des entiers où la fonction de commit est la multiplication. Le graphe relie alors deux entiers s'ils sont multiples et l'arrếte est étiquetée par le coefficient multiplicateur. La fonction de fusion (merge) calcule le plus petit commun multiple.
On peut par exemple partir de l'état initial 1 et prendre pour les trois patchs du graphes les nombres suivants : p = 2, q = 3 et r = 7. Je remets le graphe :
On aura ainsi le sommet A = 2, le sommet B = 3 et leur fusion M = 6. Ce qu'exprime le graphe, c'est que quelque soit le chemin que l'on prenne pour fusionner ces trois patchs, on tombera toujours sur Q = 42. Cela parce que la multiplication est associative et commutative.
La première propriété (associativité) n'est pas satisfaite par les autres CVS : fusionner A et N ou bien fusionner M et C ne donnera pas toujours le même résultat. C'est cela qu'illustre ces deux schémas dans la documentation de pijul :
Ensuite, à la place des nombres entiers, on peut prendre un Rubik's cube. Ici les états seraient ceux du cube, et le patchs les transformations qu'on peut lu faire subir. Avec un tel système, on aura toujours l'associativité des transformations. Que je fasse p ; (q ; r) ou (p; q) ; r cela ne change pas grand chose et l'on dit que l'on a effectué ces trois transformations à la suite p; q; r, sans mettre de parenthèses. Par contre, sur un rubik's cube, deux patchs ne peuvent pas toujours être appliqués dans n'importe quel ordre, lorsqu'ils bougent des zones communes. Dans ce cas, on dit qu'ils ne commutent pas. Il en est de même avec les CVS : des fois ça commute, des fois ça ne commute pas; mais pijul est capable de déterminer si deux patchs commutent ce qui lui permet (non de réécrire l'historique) mais de réécrire le graphe de dépendance entre les patchs pour faciliter la gestion du dépôt : on peut supprimer facilement l'effet d'un patch sans toucher aux modifications qui lui sont postérieures et indépendantes.
Il reste un point à éclaircir : la représentation interne des conflits. Revenons au cas des nombres entiers ou la fonction de merge était le calcul de plus petit commun multiple. Et regardons, ce graphe :
Ici, nos sommets sont toujours des entiers, M est le ppcm de A et B et F est un multiple quelconque de A et B, mais aussi un multiple de M. Ce que fait pijul c'est généraliser cette notion de ppcm aux fichiers. Pour cela, on considère un fichier comme une liste de lignes. Malheureusement, il n'y a pas toujours de ppcm pour deux fichiers : c'est le signe d'un conflit lors d'une fusion.
La solution est de prendre un type plus riche que les liste pour les sommets du graphe : à savoir des graphes de lignes (dont les listes sont un cas particuliers). À ce moment là, deux graphes de lignes ont toujours un « ppcm » que l'on appelle leur fusion. Si ce graphe est similaire à une liste alors il n'y a pas de conflit sinon c'est qu'il y a conflit :
If the two following conditions are both met:
the graph is acyclic, and contains a path passing through all the vertices.
for each vertex v, all incoming edges of v have the same label ("alive" vs. "deleted").
Then the task of presenting the file to the user is relatively straightforward: just go along the path and output all alive vertices. Else, we say the file has a conflict, and presenting the state of the file to the user in an intelligible way is not obvious.
Comme pijul travail avec des états qui sont ces graphes de lignes, il a une représentation interne des conflits (des graphes qui ne sont pas des listes) et peut travailler sur eux comme il le ferait avec des fichiers normaux : on peut leur appliquer des patchs, les fusionner... et les aplatir vers des fichiers (résoudre les conflits) quand on veut.
D'une manière générale, j'aime bien ce principe : Theorise first then implement is the stairway to heaven. Implement first then theorise is the highway to hell. D'autant que Jimmy page était, sans nul doute ni contestation, bien plus fin et subtil qu'Angus Young. :-P
Comme pijul a choisi la première voie, c'est plus simple et plus naturel; les autres systèmes reposant sur une mauvaise analyse de l'algèbre des patchs et des états.
Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
[^] # Re: Exemples concrets?
Posté par kantien . En réponse à la dépêche Pijul, contrôle de version et théorie des patchs, version 0.12. Évalué à 10.
En complément du commentaire d'Adrien Dorsaz, je vais quand même essayer. Mais ne t'inquiète pas, ce sera des mathématiques simples : de l'arithmétique élémentaire avec les nombres entiers, et un peu de graphes.
Une image que j'aime bien et qui représente des historiques possibles d'un dépôt est celle-ci :
diagramme de merge
On peut résumer le cœur d'un gestionnaire de version à cette interface rudimentaire :
Il y a deux concepts : les patchs et les états, puis deux fonctions pour appliquer un patch sur un état ou fusionner deux états. Ainsi, sur le graphe du dessus, on a par exemple :
Plutôt que de travailler avec des fichiers et des répertoires, commençons plus simple et travaillons avec des entiers naturels. Les états (ou sommets du graphes) sont des entiers et les patchs sont aussi des entiers où la fonction de commit est la multiplication. Le graphe relie alors deux entiers s'ils sont multiples et l'arrếte est étiquetée par le coefficient multiplicateur. La fonction de fusion (
merge) calcule le plus petit commun multiple.On peut par exemple partir de l'état initial
1et prendre pour les trois patchs du graphes les nombres suivants :p = 2,q = 3etr = 7. Je remets le graphe :On aura ainsi le sommet
A = 2, le sommetB = 3et leur fusionM = 6. Ce qu'exprime le graphe, c'est que quelque soit le chemin que l'on prenne pour fusionner ces trois patchs, on tombera toujours surQ = 42. Cela parce que la multiplication est associative et commutative.La première propriété (associativité) n'est pas satisfaite par les autres CVS : fusionner A et N ou bien fusionner M et C ne donnera pas toujours le même résultat. C'est cela qu'illustre ces deux schémas dans la documentation de pijul :
Le pire étant que ces CVS peuvent fusionner le tout, sans signaler de conflit, et faire n'importe quoi. Tel était l'exemple donné par Pierre-Étienne Meunier.
Ensuite, à la place des nombres entiers, on peut prendre un Rubik's cube. Ici les états seraient ceux du cube, et le patchs les transformations qu'on peut lu faire subir. Avec un tel système, on aura toujours l'associativité des transformations. Que je fasse
p ; (q ; r)ou(p; q) ; rcela ne change pas grand chose et l'on dit que l'on a effectué ces trois transformations à la suitep; q; r, sans mettre de parenthèses. Par contre, sur un rubik's cube, deux patchs ne peuvent pas toujours être appliqués dans n'importe quel ordre, lorsqu'ils bougent des zones communes. Dans ce cas, on dit qu'ils ne commutent pas. Il en est de même avec les CVS : des fois ça commute, des fois ça ne commute pas; mais pijul est capable de déterminer si deux patchs commutent ce qui lui permet (non de réécrire l'historique) mais de réécrire le graphe de dépendance entre les patchs pour faciliter la gestion du dépôt : on peut supprimer facilement l'effet d'un patch sans toucher aux modifications qui lui sont postérieures et indépendantes.Il reste un point à éclaircir : la représentation interne des conflits. Revenons au cas des nombres entiers ou la fonction de
mergeétait le calcul de plus petit commun multiple. Et regardons, ce graphe :Ici, nos sommets sont toujours des entiers, M est le ppcm de A et B et F est un multiple quelconque de A et B, mais aussi un multiple de M. Ce que fait pijul c'est généraliser cette notion de ppcm aux fichiers. Pour cela, on considère un fichier comme une liste de lignes. Malheureusement, il n'y a pas toujours de ppcm pour deux fichiers : c'est le signe d'un conflit lors d'une fusion.
La solution est de prendre un type plus riche que les liste pour les sommets du graphe : à savoir des graphes de lignes (dont les listes sont un cas particuliers). À ce moment là, deux graphes de lignes ont toujours un « ppcm » que l'on appelle leur fusion. Si ce graphe est similaire à une liste alors il n'y a pas de conflit sinon c'est qu'il y a conflit :
Comme pijul travail avec des états qui sont ces graphes de lignes, il a une représentation interne des conflits (des graphes qui ne sont pas des listes) et peut travailler sur eux comme il le ferait avec des fichiers normaux : on peut leur appliquer des patchs, les fusionner... et les aplatir vers des fichiers (résoudre les conflits) quand on veut.
D'une manière générale, j'aime bien ce principe : Theorise first then implement is the stairway to heaven. Implement first then theorise is the highway to hell. D'autant que Jimmy page était, sans nul doute ni contestation, bien plus fin et subtil qu'Angus Young. :-P
Comme pijul a choisi la première voie, c'est plus simple et plus naturel; les autres systèmes reposant sur une mauvaise analyse de l'algèbre des patchs et des états.
Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.