Questa è una domanda sul funzionamento interno di Mercurial.
Ricordo vagamente un collega programmatore che mi spiega come funziona in modo indifferente quali changeset differiscono tra due repository e che ha una rapida soluzione al problema.
Qualcuno sa come funziona o può indirizzarmi verso un documento che descrive i dettagli?
Algorithm funziona nel modo seguente. Hai due repository: locale e remoto. Entrambi contengono un DAG di elenchi di modifiche.
L'obiettivo del protocollo di scoperta è trovare un insieme di nodi comuni , l'insieme di nodi condivisi da locale e remoto.
Uno dei problemi con il protocollo originale era la latenza, potrebbe potenzialmente richiedere molti roundtrip per scoprire che il repository locale era un sottoinsieme di remote (che è un caso molto comune, di solito si hanno poche modifiche rispetto all'upstream, mentre probabilmente l'upstream ha avuto molto sviluppo).
Il nuovo protocollo richiede solo un'interfaccia per il repository remoto: known() , che dato un insieme di liste di modifiche ti dice se sono presenti nel DAG.
L'algoritmo quindi funziona come segue:
common , missing , unknown . Originariamente tutti i nodi sono in unknown . unknown , chiama remote.known(sample)
common
missing
unknown è vuoto Ci sono un paio di ottimizzazioni, prima è invece di iniziare con un campione casuale di dispersi, iniziare inviando tutte le teste, nel caso in cui il repository locale è un sottoinsieme, hai calcolato la risposta in un round trip.
Quindi puoi fare qualcosa di simile alla strategia di bisecatura utilizzata quando trovi i changeset difettosi. Invece di campioni casuali, puoi provare a selezionare nodi che massimizzeranno il numero di nodi che verranno classificati con esso (poiché anche tutti gli antenati o discendenti saranno contrassegnati).
Il risultato finale ha funzionato piuttosto bene.
Il codice è abbastanza leggibile se sei curioso: link
Leggi altre domande sui tag mercurial algorithms