Comment git détecte-t-il les fichiers similaires, pour sa détection de renommage ?

Question

Wikipedia explique la détection automatique des renommages :

En bref, étant donné un fichier dans la révision N, un fichier du même nom dans la révision N1 est son ancêtre par défaut. révision N1 est son ancêtre par défaut. Cependant, lorsqu'il n'y a pas de fichier de même nom dans la révision N1, Git recherche un fichier qui n'a existé seulement dans la révision N1 et qui est très similaire au nouveau fichier.

La détection des renommages se résume apparemment à la détection de fichiers similaires. Cet algorithme est-il documenté quelque part ? Ce serait bien de savoir quels types de transformations sont détectés automatiquement.

Answer 1

Git suit le contenu des fichiers, pas les noms de fichiers. Ainsi, renommer un fichier sans changer son contenu est facile à détecter pour git. (Git ne suit pas, mais exécute détection ; en utilisant git mv o git rm y git add est effectivement le même).

Lorsqu'un fichier est ajouté au référentiel, le nom du fichier se trouve dans l'objet arbre. Le contenu réel du fichier est ajouté sous la forme d'un objet binaire de grande taille ( blob ) dans le référentiel. Git n'ajoutera pas un autre blob pour les fichiers supplémentaires qui contiennent le même contenu. En fait, Git ne peut pas le faire car le contenu est stocké dans le système de fichiers, les deux premiers caractères du hachage étant le nom du répertoire et le reste étant le nom du fichier qui s'y trouve. Ainsi, pour détecter les renommages, il suffit de comparer les hachages.

Pour détecter les petites modifications d'un fichier renommé, Git utilise certains algorithmes et un seuil limite pour savoir s'il s'agit d'un renommage. Par exemple, regardez le -M pour git diff . Il existe également des valeurs de configuration telles que merge.renameLimit (le nombre de fichiers à prendre en compte lors de la détection des renommages pendant une fusion).

Pour comprendre comment git traite similaire (c'est-à-dire quelles transformations de fichiers sont considérées comme des renommages), explorez les options de configuration et les drapeaux disponibles, comme mentionné ci-dessus. Vous n'avez pas besoin d'être considéré avec le comment. Pour comprendre comment git accomplit réellement ces tâches, regardez les algorithmes pour trouver les différences dans le texte, et lisez le code source de git.

Les algorithmes sont appliqués uniquement à des fins de diff, de fusion et de journalisation -- ils n'affectent pas la façon dont git les stocke. Tout petit changement dans le contenu du fichier signifie qu'un nouvel objet est ajouté pour celui-ci. Il n'y a pas de delta ou de diff qui se passe à ce niveau. Bien sûr, plus tard, les objets peuvent être empaquetés où les deltas sont stockés dans les packfiles, mais cela n'est pas lié à la détection des renommages.

Answer 2

Il existe de nombreux algorithmes qui détectent les similitudes entre les textes, et les systèmes de contrôle de version les utilisent souvent déjà pour ne stocker que la différence entre deux versions. Des outils comme WinMerge sont suffisamment intelligents pour détecter les différences, même à l'intérieur des lignes, donc je ne vois pas pourquoi ces algorithmes ne seraient pas utilisés pour cette détection de renommage.

Voici une discussion sur des algorithmes pour détecter des textes similaires . Certains de ces algorithmes peuvent être optimisés pour les langues naturelles, tandis que d'autres fonctionnent mieux pour le code source, mais ils se ressemblent beaucoup par essence.