cómo se almacenan los DAGS almacenados en GIT

¿Cómo se almacenan los DAG internamente en Git? Como ejemplo, considere el DAG A-> B-> C-> D -> E-> F-> G.

Usted de alguna manera para save la siguiente información. A-> B, B-> C, C-> D, A-> E, E-> F, F-> G. Entonces, ¿cómo se almacena? Dado un nodo particular, ¿cómo se puede saber en qué twig se encuentra?

Solo para no perdernos en terminología: Un DAG en general es un gráfico G = (V, E) , compuesto por un set de vértices V y un set de bordes E , donde cada borde en el set de bordes impone una dirección ( también llamado arco ), y no hay ciclos (no hay path desde ningún vértice a sí mismo a través de los diversos arcos). Una representación típica de bordes es como pares de vértices, por ejemplo, si los nodos se representan como letras mayúsculas individuales (como en su ejemplo) podríamos tener <A, B> en el set de bordes E para indicar que el vértice A se conecta al vértice B , en esa dirección. Es decir, <A, B> significa que hay un arco de A a B.

Git no usa esta representación típica. En cambio, cada "vértice" es una confirmación, cuyo único identificador es su identificación hash (y, al less, yo tiendo a llamar a estos "nodos" en el gráfico en lugar de "vértices"). Cada commit enumera su (s) commit (s) padre (s), por sus ID hash. Por lo tanto, si el commit A (realmente a234567890123456789012345678901234567890 o algo así) es el padre del commit B (realmente b876543210... ), no hay nada en A nombrando B , pero hay un padre ID en B nombrando A

En otras palabras, los bordes en un gráfico de Git son todos al revés .

Mientras tanto, los nombres de las twigs apuntan a un único nodo de confirmación, que se designa como la confirmación de sugerencia de esa twig. Por ejemplo, el master puede resolver a 08bb3500a2a718c3c78b0547c68601cafa7a8fd9 .

El nombre HEAD contiene el nombre de la bifurcación actual o contiene la identificación hash sin formatting de la confirmación actual. Usando git rev-parse , podemos convertir cualquier nombre (incluido HEAD ) en el ID apropiado:

 $ git rev-parse HEAD 08bb3500a2a718c3c78b0547c68601cafa7a8fd9 

Ahora podemos responder estas preguntas:

Entonces, ¿cómo se almacena?

Existe un nodo de confirmación en el repository como un object de tipo commit cuyos contenidos son (después de la compression habitual expandida) simplemente text sin formatting en el formatting mostrado por git cat-file -p :

 $ git cat-file -p HEAD | sed 's/@/ /' tree a775288b86ae652ea163357939d852cdd927eed6 parent 36cafe44443fcca9eb35399ef0e9bfe289ec5dde author Junio C Hamano <gitster pobox.com> 1468959976 -0700 committer Junio C Hamano <gitster pobox.com> 1468959976 -0700 Sixth batch of topics for 2.10 Signed-off-by: Junio C Hamano <gitster pobox.com> 

Esto nos dice que hay un arco de 08bb3500a2a718c3c78b0547c68601cafa7a8fd9 a 36cafe44443fcca9eb35399ef0e9bfe289ec5dde .

Para encontrar el gráfico completo, el set de todos los bordes y vértices / nodos, comenzamos con todos los puntos de inicio adecuados (ver abajo) y leemos estos objects del repository. Para los objects de confirmación, leemos sus líneas parent , que proporcionan ID de nodo adicionales y también proporcionan un arco: desde el nodo que acabamos de leer, hasta el nodo nombrado en cada línea parent . (Una combinación de fusión tiene varias líneas parent , en lugar de una línea parent que enumera varias ID, pero por supuesto es bastante trivial. Tenga en count también que cada object de label anotado apunta a otro object, generalmente una confirmación, por lo que cuando encontramos un object de tipo tag , deberíamos leer su línea de object y repetir este process hasta que encontremos un object que no sea de label. Pero no encontraremos ningún object de este tipo si comenzamos solo por los nombres de las twigs, ver más abajo).

(En un DAG no Git normal, no se distingue especialmente un arco, pero en Git, el primer padre enumerado para cada nodo se distingue de cualquier padre adicional, y el order importa cuando se usa la syntax del sufijo- ^ . hacer un commit de fusión, el ID que solía ser HEAD se convertirá en el primer padre de la nueva confirmación de fusión).

Dado un nodo particular, ¿cómo se puede saber en qué twig se encuentra?

Esta pregunta tiene un defecto: asume que un nodo está en una twig.

Un nodo puede, de hecho, estar en ninguna twig, o en muchas twigs.

Volvamos ahora a la noción de todos los puntos de partida adecuados . ¿Qué puntos de partida hay? Si tuviéramos una representación gráfica típica, tendríamos el set completo de vértices (o nodos) enumerados en alguna parte. En Git, no tenemos esto. 1 En cambio, tenemos references , que en su mayoría son nombres que comienzan con refs/ . Las twigs y las tags son forms de reference, comenzando con refs/heads/ y refs/tags/ respectivamente. El command Git git for-each-ref te permite encontrar todas estas references.

Hay algunas references de propósitos especiales que no comienzan con refs : HEAD , MERGE_HEAD , CHERRY_PICK_HEAD , ORIG_HEAD , y así sucesivamente. Algunos commands de Git también deben mirar aquí. Para su caso particular, sin embargo, solo nos interesan los nombres de las sucursales, y todos comienzan con refs/ -de hecho, con refs/heads/ -para que podamos ejecutar git for-each-ref refs/heads para listrlos a todos . (El command for-each-ref agrega el extra / for us aquí, en la teoría de que es como una operación de list de directory).

Por lo tanto, para averiguar si el nodo X (para algunos X ) está en una o más twigs, y si es así, cuáles comenzamos a partir de la ID del nodo almacenada debajo de cada nombre de twig. Eso identifica la comisión de punta de esa twig. Seguimos a los padres de commit y padres de esos nodos, y así sucesivamente hasta que nos quedemos sin padres (usando cualquier algorithm de búsqueda que nos guste). Si nos encontramos con el nodo X en el path, el nodo X está en esa twig.

Por lo tanto, el nodo X está contenido en cada twig desde la cual podemos encontrar X a partir de la confirmación de sugerencia de esa twig. Esto es lo que la git branch --contains muestra.

(Los nombres de label generalmente apuntan directamente a nodos de confirmación (una "label de peso ligero") oa un object de label (una "label anotada"). Por lo tanto, si permitimos todas las references, debemos estar preparados para manejar las tags. señalar solo para comprometer nodos).


1 Bien, podemos hacer un recorrido exhaustivo de todo el repository para search todos los objects. Esto es lo que hace git fsck , por ejemplo, o git gc .

Cada confirmación tiene N padres, con N un integer que es igual o mayor que 0. Una confirmación raíz tiene 0 padres. Una confirmación sin fusión tiene 1 padre. Un commit de fusión tiene 2 o más padres. Un padre es otro compromiso. Cada confirmación, excepto la raíz, almacena los sha1 (s) de sus padres. Por lo tanto, los commits se organizan como un DAG. Sabiendo un compromiso, podemos decirles a todos sus antepasados. git log -1 <commit> --pretty=%P puede generar los padres del commit.

En un repository git, puede haber uno o más DAG. Una twig es un ref que señala, o un anclaje que se une a una confirmación (u otra twig). Es un poco como el puntero en C, con el compromiso como una estructura o variable de class y sha1 como su dirección. La twig se puede mover de una confirmación a otra. A veces se mueve automáticamente, mediante la introducción de un nuevo compromiso que incluye git commit , git rebase , git merge , git cherry-pick , etc. A veces se mueve a voluntad mediante git reset .

Cuando decimos que un commit está en una twig, se puede entender de otra manera, que este commit es igual a, o el antecesor de ese commit al que se refiere la twig. git branch --contains <commit> --all puede indicar en qué twigs está activada la confirmación.

    Intereting Posts