Какой алгоритм использует git для обнаружения изменений на рабочем дереве?

Это о внутренностях git.

Я читал замечательную книгу "Pro Git" и немного узнал о том, как Git работает внутри (все о SHA1, BLOB-объектах, ссылках, деревьях, коммитах и т.д. И т.д.). Кстати, довольно умная архитектура.

Итак, в контексте, git ссылается на содержимое файла как значение SHA1, чтобы он мог узнать, изменился ли конкретный контент, просто сравнивая значения хеш-функции. Но мой вопрос конкретно о том, как git проверяет, изменился ли контент в рабочем дереве или нет.

Наивный подход будет заключаться в том, что каждый раз, когда вы запускаете команду как git status или аналогичную команду, он просматривает все файлы в рабочем каталоге, вычисляет SHA1 и сравнивает его с тем, который имеет последний коммит. Но это кажется очень неэффективным для больших проектов, таких как ядро Linux.

Другая идея может заключаться в проверке даты последнего изменения файла, но я думаю, что git не хранит эту информацию (когда вы клонируете репозиторий, у всех файлов новое время)

Я уверен, что он делает это эффективно (git работает очень быстро), кто-нибудь знает, как этого добиться?

PD: Просто чтобы добавить интересную ссылку об индексе git, в частности, указав, что индекс хранит информацию о временных метках файлов, даже если объекты дерева этого не делают.

Ответ 1

Git s индекс поддерживает отметки времени, когда git последний написал каждый файл в рабочем дереве (и обновляет их всякий раз, когда файлы кэшируются из рабочего дерева или из фиксации). Метаданные можно увидеть с помощью git ls-files --debug. В дополнение к метке времени он записывает размер, индекс и другую информацию из lstat, чтобы уменьшить вероятность ложного срабатывания.

Когда вы выполняете git -status, он просто вызывает lstat для каждого файла в рабочем дереве и сравнивает метаданные в порядке чтобы быстро определить, какие файлы остались без изменений. Это описано в документации racy-git и update-index.

Ответ 2

В файловой системе unix файл-информация отслеживается и может быть подключен с помощью метода lstat. Структура stat содержит несколько временных штампов, информацию о размере и т.д.:

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 */
};

Похоже, что первоначально Git просто полагался на эту структуру stat, чтобы решить, был ли файл изменен ( см. ссылку):

При проверке, отличаются ли они, Git сначала запускает lstat(2) в файлах и сравнивает результат с этой информацией

Однако сообщалось о состоянии гонки (racy-git), который был найден, если файл был изменен следующим образом:

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

Это оставило файл в состоянии, которое было изменено, но не определено lstat.

Чтобы устранить эту проблему, теперь в таких ситуациях, когда состояние lstat неоднозначно, Git сравнивает содержимое файлов, чтобы определить, было ли оно изменено.

Примечание:

Если кто-то смущен, как и я, о st_mtime описании, в котором говорится, что он обновляется путем записи "больше нуля", это означает абсолютное изменение.

Например, в случае текстового файла с единственным символом A: если A изменено на B, то получается 0 чистое изменение общего размера байта, но st_mtime все равно будет обновляться ( пришлось попробовать сам проверить, использовать ls -l, чтобы увидеть временную метку).