Algoritmo Git log ^

Estoy usando el command "git log ^" para asegurarme de que entre dos twigs (digamos versión actual y versión anterior) no haya compromiso en la versión anterior que no sea parte de la versión actual (utilizamos un número de logging) en el post de compromiso, que es la base para la comparación).

Básicamente me preguntaba cuál es el algorithm detrás del command. Alguien sabe como funciona?
Supongo que puedes get todas las confirmaciones de ambas twigs y compararlas una a una. Sin embargo, en caso de que la historia sea bastante larga, este puede ser un process largo.
Pero creo que hay una manera más inteligente de hacer esto. La idea sería encontrar el ancestro común, pero no estoy seguro si esto es factible y cómo podría hacerse.

Si alguien puede iluminarme, sería genial 🙂

De los comentarios, ha notado que:

Estaba hablando de la caret

y:

.. Debí haber precisado que mi propósito sería hacer este trabajo usando la API de Bitbucket más tarde (en lugar de los commands estándar de git) …

Eso hará que su trabajo sea bastante difícil, a less que la parte de la API que utiliza sea git clone . 🙂 Exactamente qué tan difícil depende de si puedes salirte con la única información sobre cada object de commit, o si necesitas el equivalente de git cherry .

El comentario de Kevin es correcto: lo que hacen git log o git rev-list , para implementar las ^branch_exclude branch_include o branch_exclude..branch_include de gitrevisions , es ejecutar una primera búsqueda de amplitud o profundidad en el gráfico de confirmación. (Basado en el código en revision.c , es principalmente el primero en amplitud).

Esto, por supuesto, requiere build el gráfico de compromiso, o al less lo suficiente.

Internamente, dentro de Git, cada commit se denomina por su ID hash. Cada confirmación consta de un pequeño object de text, que incluye las ID de hash padre del compromiso (una por padre). Esas dos partes, más un punto de partida como el ID de HEAD commit o el ID de algún nombre de twig, son todo lo que necesitamos para hacer los types más simples de recorrido, es decir, el estándar git rev-list <startpoint> gráfico caminar.

Tenga en count que la mayoría de las confirmaciones tienen solo un padre: se trata de confirmaciones ordinarias. Al less una confirmación en el gráfico no tiene padres, y es una confirmación "raíz". El primer compromiso hecho en el repository siempre es una confirmación de raíz (puede hacer más raíces con la git checkout --orphan , o usando los commands de plomería de Git). Algunas confirmaciones son fusiones : tienen dos o más padres.

Sencillos charts camina

Hay muchos algorithms de recorrido de gráfico (ver varios libros de Sedgewick, Aho y, por supuesto, Knuth), pero Git usa uno muy simple para empezar: mantener una estructura de datos en memory ( struct commit ) para cada compromiso encontrado hasta ahora, y marcar el object una vez que es "visto". Para recorrer un gráfico, dado un hash de confirmación H , ponemos a H en una queue de "commits to visit". Entonces, en no-bastante-C:

 while (there are commits in the queue) { struct commit *c = lookup_by_id(remove_first_id_from_queue()); if (c->flags & SEEN) ... we already saw this, so do nothing ... else { ... print this commit ... c->flag |= SEEN; /* now we've seen it! */ for (h in all C's "parent" hashes) append_hash_to_queue(h); } } 

La queue es lo que maneja las asignaciones de fusión, y hace de esto una primera búsqueda de amplitud. Cuando comenzamos con una queue vacía y ponemos una confirmación común en ella, visitamos esa confirmación y agregamos el padre único de la confirmación a la queue, luego retiramos inmediatamente al padre de la queue y visitamos al padre, agregando su padre a la queue, y así. Esto solo camina linealmente. El process se detiene cuando pulsamos la confirmación de la raíz. Pero cuando hacemos un commit de fusión , agregamos a ambos padres a la queue, luego comenzamos a caminar ambos lados, turnándonos visitando a "primer padre" y haciendo queue a sus padres, luego "segundo padre" y haciendo queue a sus padres, y pronto. En algún momento, pondremos en queue una confirmación que ya está en la queue o que ya se ha visto. Cuando lleguemos a esa confirmación retrasada o releída más tarde, simplemente la omitiremos.

Para implementar "commits alcanzable desde identifier include pero no desde identifier exclude ", podríamos usar este mismo algorithm, pero modificado: primero recorremos todos los commits que se pueden encontrar desde exclude , estableciendo el flag SEEN pero sin imprimir nada; luego colocamos el hash para include en la queue, volvemos a caminar e imprimimos los commits que visitamos esta vez que aún no hemos visitado a través de la exclusión.

La primera caminata, para excluir confirmaciones, es lo que podríamos llamar una "caminata negativa", y la segunda, include compromisos, es lo que podríamos llamar una "caminata positiva".

(Este algorithm es muy poco óptimo y, por lo tanto, no es lo que usa Git. Si lees el código, verás que los commits excluidos específicamente obtienen los UNINTERESTING | BOTTOM configurados, mientras que los commits excluidos a través de los walks obtienen UNINTERESTING set. Hay algunos interesantes ) código en la function relevant_commit y sus llamadores que ayuda a podar amplias franjas del gráfico durante la caminata negativa, sin tener que pasar caminando. El truco es que debemos saber si hay múltiples forms de llegar al punto que tendríamos me gusta podar en este momento. De lo contrario, es seguro marcar el compromiso único, que evitará atravesarlo y a todos sus padres durante la caminata positiva).

Cereza Git

Lo que hace git cherry (o git rev-list --cherry-mark , o cualquiera de los varios artículos similares) es más complicado que los simples paseos anteriores. Para implementar git cherry o equivalente, no solo necesitamos el gráfico de confirmación, sino también los objects restantes en el repository, porque ahora nos gustaría marcar las confirmaciones que están "en" un set pero no "en" otro set.

Antes incluso de llegar allí, necesitamos definir la diferencia simétrica , que en la syntax de Git se denota A...B (tres puntos en lugar de dos). La diferencia simétrica es, en su núcleo, "include confirmaciones que se pueden alcanzar desde el nombre del lado izquierdo o desde el nombre del lado derecho, pero no desde ambos nombres". Nuevamente, podríamos usar un algorithm de recorrido de gráfico muy simple (aunque Git no lo hace, una vez más porque este es demasiado ineficiente): realice una caminata desde A , marcando cada compromiso "visto" con una bandera "vista a la izquierda". Luego, realice una caminata desde B , marcando cada compromiso recientemente visto con una bandera "vista a la derecha", separada de las banderas "vistas a la izquierda" (de modo que marquemos todas las confirmaciones que sean accesibles desde ambos nombres, con ambas banderas).

Ahora hacemos un recorrido final de todos nuestros objects de compromiso almacenados (no de los dos nombres, justo sobre los objects internos de struct commit ), e imprimimos solo las struct commit "visto a la izquierda pero no a la derecha" como confirmaciones del lado izquierdo e imprimimos solo el "visto a la derecha pero no a la izquierda" se compromete como confirmaciones del lado derecho. Esto nos da la diferencia simétrica.

Para implementar git cherry , sin embargo, tenemos que ir un poco más allá. Para cada compromiso de padre único, obtenemos un set de cambios . (En general, ignoramos las fusiones, aunque es posible convertir una fusión en un set de cambios contra uno de sus padres). El set de cambios es básicamente el resultado de git diff <parent-id> <commit-id> .

Ahora tenemos la parte difícil: cada set de cambios se puede convertir en una ID de hash, de la misma manera que Git convierte todos los objects de Git-repository en ID de hash. Si hacemos esto con cuidado, de una manera que no sea sensible a la numeración de líneas (e ignore el post de confirmación, y el autor y la date, etc.), terminaremos con lo que Git llama una identificación de parche .

Para implementar git cherry , marcamos todas las confirmaciones ordinarias en cada "lado" con sus ID de parche. Luego podemos verificar fácilmente, mientras imprimimos cada confirmación, si cada ID de parche del lado izquierdo está en el set de todas las ID de parche del lado derecho, y viceversa. Esto nos permite encontrar commits "perdidos", incluso si el commit fue copydo (a través de git cherry-pick o git rebase o similar).

(Para ver el algorithm que Git usa realmente para las diferencias simétricas, consulte la fuente. El indicador UNINTERESTING se aumenta con otro indicador, BOTTOM y confirmaciones "de límite", aquellas en las que ambas partes se encuentran, lo que permite evitar algunas cadenas principales). con otra bandera, la bandera de BOUNDARY . Puede ver estas confirmaciones agregando --boundary a las banderas que le da a git rev-list . Encuentro que --boundary no es tan útil como podría parecer, porque primero busca ancho los puntos de partida múltiples pueden tener límites "adicionales" que no serían necesarios en las búsquedas realizadas en otros pedidos).

(Internamente, la bandera BOTTOM también se utiliza para --ancestry-path , junto con una list de "references negativas", es decir, la negación en ^X marca la confirmación a la que X refiere como reference negativa y como commit ", que luego se incluye en esta list. El código del recorrido rev-list puede excluir un commit que no tenga todos estos commits" bottom "como antepasados).

puedes usar el command cherry para encontrar los commits faltantes.

por ejemplo, digamos que su primera twig es r1 y la última es r2.

git checkout r1

git cherry r2

Esto informará todo el compromiso que no existe en la twig r2.

aquí está la documentation https://git-scm.com/docs/git-cherry