¿Qué algoritmo usa git para detectar cambios en su árbol de trabajo?

Question

Esto es sobre las partes internas de git.

He estado leyendo el gran libro 'Pro Git' y aprendiendo un poco sobre cómo funciona git internamente (todo sobre SHA1, blobs, referencias, tress, commits, etc., etc.). Arquitectura bastante inteligente, por cierto.

Por lo tanto, para ponerlo en contexto, git hace referencia al contenido de un archivo como un valor SHA1, por lo que es capaz de saber si un contenido específico ha cambiado simplemente comparando los valores hash. Pero mi pregunta es específicamente sobre cómo git comprueba que el contenido en el árbol de trabajo ha cambiado o no.

El enfoque ingenuo será pensar que, cada vez que ejecute un comando como git status o un comando similar, buscará todos los archivos en el directorio de trabajo, calculando el SHA1 y comparándolo con el que tiene el último compromiso . Pero eso parece muy ineficiente para grandes proyectos, como el kernel de Linux.

Otra idea podría ser para comprobar la última fecha de modificación en el archivo, pero creo que git no es el almacenamiento de la información (al clonar un repositorio, todos los archivos tienen un nuevo tiempo)

Estoy seguro de que es hacerlo de manera eficiente (git es realmente rápido), ¿cómo se logra eso?

PD: Solo para agregar un interesante link sobre el índice git, indicando específicamente que el índice mantiene información sobre las marcas de tiempo de los archivos, incluso cuando los objetos del árbol no lo hacen.

Answer 1

El índice de Git mantiene las marcas de tiempo de cuando git escribió por última vez cada archivo en el árbol de trabajo (y las actualiza cuando los archivos se almacenan en caché desde el árbol de trabajo o desde una confirmación). Puede ver los metadatos con git ls-files --debug. Además de la marca de tiempo, registra el tamaño, inodo y otra información de lstat para reducir la posibilidad de un falso positivo.

Cuando realiza git-status, simplemente llama a lstat en cada archivo en el árbol de trabajo y compara los metadatos para determinar rápidamente qué archivos no han cambiado. Esto se describe en la documentación bajo racy-git y update-index.

Answer 2

En un sistema de archivos unix, la información del archivo se rastrea y se puede acceder utilizando el método lstat. El stat structure contiene múltiples marcas de tiempo, información, y más:

struct stat { 
    dev_t  st_dev;  /* ID of device containing file */ 
    ino_t  st_ino;  /* inode number */ 
    mode_t st_mode; /* protection */ 
    nlink_t st_nlink; /* number of hard links */ 
    uid_t  st_uid;  /* user ID of owner */ 
    gid_t  st_gid;  /* group ID of owner */ 
    dev_t  st_rdev; /* device ID (if special file) */ 
    off_t  st_size; /* total size, in bytes */ 
    blksize_t st_blksize; /* blocksize for file system I/O */ 
    blkcnt_t st_blocks; /* number of 512B blocks allocated */ 
    time_t st_atime; /* time of last access */ 
    time_t st_mtime; /* time of last modification */ 
    time_t st_ctime; /* time of last status change */ 
}; 

Parece que inicialmente Git simplemente se basó en este stat structure para decidir si un archivo ha sido cambiado (see reference):

Cuando comprobar si difieren, Git primera corre lstat(2) en los archivos y compara el resultado con esta información

Sin embargo, se informó de una condición de carrera (racy-git) que encontró que si un archivo fue modificado de la siguiente manera:

: modify 'foo' 
$ git update-index 'foo' 
: modify 'foo' again, in-place, without changing its size 
         (And quickly enough to not change it's timestamps) 

Esto dejó el archivo en un estado que se ha modificado pero no detectable por lstat.

Para solucionar este problema, ahora en situaciones en las que el estado de lstat es ambiguo, Git compara el contenido de los archivos para determinar si se ha modificado.

---

NOTA:

Si alguien está confundido, como si fuera, sobre st_mtime description, lo que indica que es actualizada por las escrituras "de más de cero bytes," esto significa absoluta cambio.

Por ejemplo, en el caso de un archivo de archivo de texto con un solo carácter A: si A se cambia a B hay 0 cambio neto en el tamaño total de bytes, pero el st_mtime todavía será actualizado (tenía que probar a mí mismo para verificar, use ls -l para ver la fecha y hora).