<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="en">
<head>
<meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge"/>
<meta name="viewport" content="width=device-width, initial-scale=1.0"/>
<meta name="generator" content="Asciidoctor 2.0.23"/>
<title>Git Commit-Graph Design Notes</title>
<link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Open+Sans:300,300italic,400,400italic,600,600italic%7CNoto+Serif:400,400italic,700,700italic%7CDroid+Sans+Mono:400,700"/>
<style>
/*! Asciidoctor default stylesheet | MIT License | https://asciidoctor.org */
/* Uncomment the following line when using as a custom stylesheet */
/* @import "https://fonts.googleapis.com/css?family=Open+Sans:300,300italic,400,400italic,600,600italic%7CNoto+Serif:400,400italic,700,700italic%7CDroid+Sans+Mono:400,700"; */
html{font-family:sans-serif;-webkit-text-size-adjust:100%}
a{background:none}
a:focus{outline:thin dotted}
a:active,a:hover{outline:0}
h1{font-size:2em;margin:.67em 0}
b,strong{font-weight:bold}
abbr{font-size:.9em}
abbr[title]{cursor:help;border-bottom:1px dotted #dddddf;text-decoration:none}
dfn{font-style:italic}
hr{height:0}
mark{background:#ff0;color:#000}
code,kbd,pre,samp{font-family:monospace;font-size:1em}
pre{white-space:pre-wrap}
q{quotes:"\201C" "\201D" "\2018" "\2019"}
small{font-size:80%}
sub,sup{font-size:75%;line-height:0;position:relative;vertical-align:baseline}
sup{top:-.5em}
sub{bottom:-.25em}
img{border:0}
svg:not(:root){overflow:hidden}
figure{margin:0}
audio,video{display:inline-block}
audio:not([controls]){display:none;height:0}
fieldset{border:1px solid silver;margin:0 2px;padding:.35em .625em .75em}
legend{border:0;padding:0}
button,input,select,textarea{font-family:inherit;font-size:100%;margin:0}
button,input{line-height:normal}
button,select{text-transform:none}
button,html input[type=button],input[type=reset],input[type=submit]{-webkit-appearance:button;cursor:pointer}
button[disabled],html input[disabled]{cursor:default}
input[type=checkbox],input[type=radio]{padding:0}
button::-moz-focus-inner,input::-moz-focus-inner{border:0;padding:0}
textarea{overflow:auto;vertical-align:top}
table{border-collapse:collapse;border-spacing:0}
*,::before,::after{box-sizing:border-box}
html,body{font-size:100%}
body{background:#fff;color:rgba(0,0,0,.8);padding:0;margin:0;font-family:"Noto Serif","DejaVu Serif",serif;line-height:1;position:relative;cursor:auto;-moz-tab-size:4;-o-tab-size:4;tab-size:4;word-wrap:anywhere;-moz-osx-font-smoothing:grayscale;-webkit-font-smoothing:antialiased}
a:hover{cursor:pointer}
img,object,embed{max-width:100%;height:auto}
object,embed{height:100%}
img{-ms-interpolation-mode:bicubic}
.left{float:left!important}
.right{float:right!important}
.text-left{text-align:left!important}
.text-right{text-align:right!important}
.text-center{text-align:center!important}
.text-justify{text-align:justify!important}
.hide{display:none}
img,object,svg{display:inline-block;vertical-align:middle}
textarea{height:auto;min-height:50px}
select{width:100%}
.subheader,.admonitionblock td.content>.title,.audioblock>.title,.exampleblock>.title,.imageblock>.title,.listingblock>.title,.literalblock>.title,.stemblock>.title,.openblock>.title,.paragraph>.title,.quoteblock>.title,table.tableblock>.title,.verseblock>.title,.videoblock>.title,.dlist>.title,.olist>.title,.ulist>.title,.qlist>.title,.hdlist>.title{line-height:1.45;color:#7a2518;font-weight:400;margin-top:0;margin-bottom:.25em}
div,dl,dt,dd,ul,ol,li,h1,h2,h3,#toctitle,.sidebarblock>.content>.title,h4,h5,h6,pre,form,p,blockquote,th,td{margin:0;padding:0}
a{color:#2156a5;text-decoration:underline;line-height:inherit}
a:hover,a:focus{color:#1d4b8f}
a img{border:0}
p{line-height:1.6;margin-bottom:1.25em;text-rendering:optimizeLegibility}
p aside{font-size:.875em;line-height:1.35;font-style:italic}
h1,h2,h3,#toctitle,.sidebarblock>.content>.title,h4,h5,h6{font-family:"Open Sans","DejaVu Sans",sans-serif;font-weight:300;font-style:normal;color:#ba3925;text-rendering:optimizeLegibility;margin-top:1em;margin-bottom:.5em;line-height:1.0125em}
h1 small,h2 small,h3 small,#toctitle small,.sidebarblock>.content>.title small,h4 small,h5 small,h6 small{font-size:60%;color:#e99b8f;line-height:0}
h1{font-size:2.125em}
h2{font-size:1.6875em}
h3,#toctitle,.sidebarblock>.content>.title{font-size:1.375em}
h4,h5{font-size:1.125em}
h6{font-size:1em}
hr{border:solid #dddddf;border-width:1px 0 0;clear:both;margin:1.25em 0 1.1875em}
em,i{font-style:italic;line-height:inherit}
strong,b{font-weight:bold;line-height:inherit}
small{font-size:60%;line-height:inherit}
code{font-family:"Droid Sans Mono","DejaVu Sans Mono",monospace;font-weight:400;color:rgba(0,0,0,.9)}
ul,ol,dl{line-height:1.6;margin-bottom:1.25em;list-style-position:outside;font-family:inherit}
ul,ol{margin-left:1.5em}
ul li ul,ul li ol{margin-left:1.25em;margin-bottom:0}
ul.circle{list-style-type:circle}
ul.disc{list-style-type:disc}
ul.square{list-style-type:square}
ul.circle ul:not([class]),ul.disc ul:not([class]),ul.square ul:not([class]){list-style:inherit}
ol li ul,ol li ol{margin-left:1.25em;margin-bottom:0}
dl dt{margin-bottom:.3125em;font-weight:bold}
dl dd{margin-bottom:1.25em}
blockquote{margin:0 0 1.25em;padding:.5625em 1.25em 0 1.1875em;border-left:1px solid #ddd}
blockquote,blockquote p{line-height:1.6;color:rgba(0,0,0,.85)}
@media screen and (min-width:768px){h1,h2,h3,#toctitle,.sidebarblock>.content>.title,h4,h5,h6{line-height:1.2}
h1{font-size:2.75em}
h2{font-size:2.3125em}
h3,#toctitle,.sidebarblock>.content>.title{font-size:1.6875em}
h4{font-size:1.4375em}}
table{background:#fff;margin-bottom:1.25em;border:1px solid #dedede;word-wrap:normal}
table thead,table tfoot{background:#f7f8f7}
table thead tr th,table thead tr td,table tfoot tr th,table tfoot tr td{padding:.5em .625em .625em;font-size:inherit;color:rgba(0,0,0,.8);text-align:left}
table tr th,table tr td{padding:.5625em .625em;font-size:inherit;color:rgba(0,0,0,.8)}
table tr.even,table tr.alt{background:#f8f8f7}
table thead tr th,table tfoot tr th,table tbody tr td,table tr td,table tfoot tr td{line-height:1.6}
h1,h2,h3,#toctitle,.sidebarblock>.content>.title,h4,h5,h6{line-height:1.2;word-spacing:-.05em}
h1 strong,h2 strong,h3 strong,#toctitle strong,.sidebarblock>.content>.title strong,h4 strong,h5 strong,h6 strong{font-weight:400}
.center{margin-left:auto;margin-right:auto}
.stretch{width:100%}
.clearfix::before,.clearfix::after,.float-group::before,.float-group::after{content:" ";display:table}
.clearfix::after,.float-group::after{clear:both}
:not(pre).nobreak{word-wrap:normal}
:not(pre).nowrap{white-space:nowrap}
:not(pre).pre-wrap{white-space:pre-wrap}
:not(pre):not([class^=L])>code{font-size:.9375em;font-style:normal!important;letter-spacing:0;padding:.1em .5ex;word-spacing:-.15em;background:#f7f7f8;border-radius:4px;line-height:1.45;text-rendering:optimizeSpeed}
pre{color:rgba(0,0,0,.9);font-family:"Droid Sans Mono","DejaVu Sans Mono",monospace;line-height:1.45;text-rendering:optimizeSpeed}
pre code,pre pre{color:inherit;font-size:inherit;line-height:inherit}
pre>code{display:block}
pre.nowrap,pre.nowrap pre{white-space:pre;word-wrap:normal}
em em{font-style:normal}
strong strong{font-weight:400}
.keyseq{color:rgba(51,51,51,.8)}
kbd{font-family:"Droid Sans Mono","DejaVu Sans Mono",monospace;display:inline-block;color:rgba(0,0,0,.8);font-size:.65em;line-height:1.45;background:#f7f7f7;border:1px solid #ccc;border-radius:3px;box-shadow:0 1px 0 rgba(0,0,0,.2),inset 0 0 0 .1em #fff;margin:0 .15em;padding:.2em .5em;vertical-align:middle;position:relative;top:-.1em;white-space:nowrap}
.keyseq kbd:first-child{margin-left:0}
.keyseq kbd:last-child{margin-right:0}
.menuseq,.menuref{color:#000}
.menuseq b:not(.caret),.menuref{font-weight:inherit}
.menuseq{word-spacing:-.02em}
.menuseq b.caret{font-size:1.25em;line-height:.8}
.menuseq i.caret{font-weight:bold;text-align:center;width:.45em}
b.button::before,b.button::after{position:relative;top:-1px;font-weight:400}
b.button::before{content:"[";padding:0 3px 0 2px}
b.button::after{content:"]";padding:0 2px 0 3px}
p a>code:hover{color:rgba(0,0,0,.9)}
#header,#content,#footnotes,#footer{width:100%;margin:0 auto;max-width:62.5em;*zoom:1;position:relative;padding-left:.9375em;padding-right:.9375em}
#header::before,#header::after,#content::before,#content::after,#footnotes::before,#footnotes::after,#footer::before,#footer::after{content:" ";display:table}
#header::after,#content::after,#footnotes::after,#footer::after{clear:both}
#content{margin-top:1.25em}
#content::before{content:none}
#header>h1:first-child{color:rgba(0,0,0,.85);margin-top:2.25rem;margin-bottom:0}
#header>h1:first-child+#toc{margin-top:8px;border-top:1px solid #dddddf}
#header>h1:only-child{border-bottom:1px solid #dddddf;padding-bottom:8px}
#header .details{border-bottom:1px solid #dddddf;line-height:1.45;padding-top:.25em;padding-bottom:.25em;padding-left:.25em;color:rgba(0,0,0,.6);display:flex;flex-flow:row wrap}
#header .details span:first-child{margin-left:-.125em}
#header .details span.email a{color:rgba(0,0,0,.85)}
#header .details br{display:none}
#header .details br+span::before{content:"\00a0\2013\00a0"}
#header .details br+span.author::before{content:"\00a0\22c5\00a0";color:rgba(0,0,0,.85)}
#header .details br+span#revremark::before{content:"\00a0|\00a0"}
#header #revnumber{text-transform:capitalize}
#header #revnumber::after{content:"\00a0"}
#content>h1:first-child:not([class]){color:rgba(0,0,0,.85);border-bottom:1px solid #dddddf;padding-bottom:8px;margin-top:0;padding-top:1rem;margin-bottom:1.25rem}
#toc{border-bottom:1px solid #e7e7e9;padding-bottom:.5em}
#toc>ul{margin-left:.125em}
#toc ul.sectlevel0>li>a{font-style:italic}
#toc ul.sectlevel0 ul.sectlevel1{margin:.5em 0}
#toc ul{font-family:"Open Sans","DejaVu Sans",sans-serif;list-style-type:none}
#toc li{line-height:1.3334;margin-top:.3334em}
#toc a{text-decoration:none}
#toc a:active{text-decoration:underline}
#toctitle{color:#7a2518;font-size:1.2em}
@media screen and (min-width:768px){#toctitle{font-size:1.375em}
body.toc2{padding-left:15em;padding-right:0}
body.toc2 #header>h1:nth-last-child(2){border-bottom:1px solid #dddddf;padding-bottom:8px}
#toc.toc2{margin-top:0!important;background:#f8f8f7;position:fixed;width:15em;left:0;top:0;border-right:1px solid #e7e7e9;border-top-width:0!important;border-bottom-width:0!important;z-index:1000;padding:1.25em 1em;height:100%;overflow:auto}
#toc.toc2 #toctitle{margin-top:0;margin-bottom:.8rem;font-size:1.2em}
#toc.toc2>ul{font-size:.9em;margin-bottom:0}
#toc.toc2 ul ul{margin-left:0;padding-left:1em}
#toc.toc2 ul.sectlevel0 ul.sectlevel1{padding-left:0;margin-top:.5em;margin-bottom:.5em}
body.toc2.toc-right{padding-left:0;padding-right:15em}
body.toc2.toc-right #toc.toc2{border-right-width:0;border-left:1px solid #e7e7e9;left:auto;right:0}}
@media screen and (min-width:1280px){body.toc2{padding-left:20em;padding-right:0}
#toc.toc2{width:20em}
#toc.toc2 #toctitle{font-size:1.375em}
#toc.toc2>ul{font-size:.95em}
#toc.toc2 ul ul{padding-left:1.25em}
body.toc2.toc-right{padding-left:0;padding-right:20em}}
#content #toc{border:1px solid #e0e0dc;margin-bottom:1.25em;padding:1.25em;background:#f8f8f7;border-radius:4px}
#content #toc>:first-child{margin-top:0}
#content #toc>:last-child{margin-bottom:0}
#footer{max-width:none;background:rgba(0,0,0,.8);padding:1.25em}
#footer-text{color:hsla(0,0%,100%,.8);line-height:1.44}
#content{margin-bottom:.625em}
.sect1{padding-bottom:.625em}
@media screen and (min-width:768px){#content{margin-bottom:1.25em}
.sect1{padding-bottom:1.25em}}
.sect1:last-child{padding-bottom:0}
.sect1+.sect1{border-top:1px solid #e7e7e9}
#content h1>a.anchor,h2>a.anchor,h3>a.anchor,#toctitle>a.anchor,.sidebarblock>.content>.title>a.anchor,h4>a.anchor,h5>a.anchor,h6>a.anchor{position:absolute;z-index:1001;width:1.5ex;margin-left:-1.5ex;display:block;text-decoration:none!important;visibility:hidden;text-align:center;font-weight:400}
#content h1>a.anchor::before,h2>a.anchor::before,h3>a.anchor::before,#toctitle>a.anchor::before,.sidebarblock>.content>.title>a.anchor::before,h4>a.anchor::before,h5>a.anchor::before,h6>a.anchor::before{content:"\00A7";font-size:.85em;display:block;padding-top:.1em}
#content h1:hover>a.anchor,#content h1>a.anchor:hover,h2:hover>a.anchor,h2>a.anchor:hover,h3:hover>a.anchor,#toctitle:hover>a.anchor,.sidebarblock>.content>.title:hover>a.anchor,h3>a.anchor:hover,#toctitle>a.anchor:hover,.sidebarblock>.content>.title>a.anchor:hover,h4:hover>a.anchor,h4>a.anchor:hover,h5:hover>a.anchor,h5>a.anchor:hover,h6:hover>a.anchor,h6>a.anchor:hover{visibility:visible}
#content h1>a.link,h2>a.link,h3>a.link,#toctitle>a.link,.sidebarblock>.content>.title>a.link,h4>a.link,h5>a.link,h6>a.link{color:#ba3925;text-decoration:none}
#content h1>a.link:hover,h2>a.link:hover,h3>a.link:hover,#toctitle>a.link:hover,.sidebarblock>.content>.title>a.link:hover,h4>a.link:hover,h5>a.link:hover,h6>a.link:hover{color:#a53221}
details,.audioblock,.imageblock,.literalblock,.listingblock,.stemblock,.videoblock{margin-bottom:1.25em}
details{margin-left:1.25rem}
details>summary{cursor:pointer;display:block;position:relative;line-height:1.6;margin-bottom:.625rem;outline:none;-webkit-tap-highlight-color:transparent}
details>summary::-webkit-details-marker{display:none}
details>summary::before{content:"";border:solid transparent;border-left:solid;border-width:.3em 0 .3em .5em;position:absolute;top:.5em;left:-1.25rem;transform:translateX(15%)}
details[open]>summary::before{border:solid transparent;border-top:solid;border-width:.5em .3em 0;transform:translateY(15%)}
details>summary::after{content:"";width:1.25rem;height:1em;position:absolute;top:.3em;left:-1.25rem}
.admonitionblock td.content>.title,.audioblock>.title,.exampleblock>.title,.imageblock>.title,.listingblock>.title,.literalblock>.title,.stemblock>.title,.openblock>.title,.paragraph>.title,.quoteblock>.title,table.tableblock>.title,.verseblock>.title,.videoblock>.title,.dlist>.title,.olist>.title,.ulist>.title,.qlist>.title,.hdlist>.title{text-rendering:optimizeLegibility;text-align:left;font-family:"Noto Serif","DejaVu Serif",serif;font-size:1rem;font-style:italic}
table.tableblock.fit-content>caption.title{white-space:nowrap;width:0}
.paragraph.lead>p,#preamble>.sectionbody>[class=paragraph]:first-of-type p{font-size:1.21875em;line-height:1.6;color:rgba(0,0,0,.85)}
.admonitionblock>table{border-collapse:separate;border:0;background:none;width:100%}
.admonitionblock>table td.icon{text-align:center;width:80px}
.admonitionblock>table td.icon img{max-width:none}
.admonitionblock>table td.icon .title{font-weight:bold;font-family:"Open Sans","DejaVu Sans",sans-serif;text-transform:uppercase}
.admonitionblock>table td.content{padding-left:1.125em;padding-right:1.25em;border-left:1px solid #dddddf;color:rgba(0,0,0,.6);word-wrap:anywhere}
.admonitionblock>table td.content>:last-child>:last-child{margin-bottom:0}
.exampleblock>.content{border:1px solid #e6e6e6;margin-bottom:1.25em;padding:1.25em;background:#fff;border-radius:4px}
.sidebarblock{border:1px solid #dbdbd6;margin-bottom:1.25em;padding:1.25em;background:#f3f3f2;border-radius:4px}
.sidebarblock>.content>.title{color:#7a2518;margin-top:0;text-align:center}
.exampleblock>.content>:first-child,.sidebarblock>.content>:first-child{margin-top:0}
.exampleblock>.content>:last-child,.exampleblock>.content>:last-child>:last-child,.exampleblock>.content .olist>ol>li:last-child>:last-child,.exampleblock>.content .ulist>ul>li:last-child>:last-child,.exampleblock>.content .qlist>ol>li:last-child>:last-child,.sidebarblock>.content>:last-child,.sidebarblock>.content>:last-child>:last-child,.sidebarblock>.content .olist>ol>li:last-child>:last-child,.sidebarblock>.content .ulist>ul>li:last-child>:last-child,.sidebarblock>.content .qlist>ol>li:last-child>:last-child{margin-bottom:0}
.literalblock pre,.listingblock>.content>pre{border-radius:4px;overflow-x:auto;padding:1em;font-size:.8125em}
@media screen and (min-width:768px){.literalblock pre,.listingblock>.content>pre{font-size:.90625em}}
@media screen and (min-width:1280px){.literalblock pre,.listingblock>.content>pre{font-size:1em}}
.literalblock pre,.listingblock>.content>pre:not(.highlight),.listingblock>.content>pre[class=highlight],.listingblock>.content>pre[class^="highlight "]{background:#f7f7f8}
.literalblock.output pre{color:#f7f7f8;background:rgba(0,0,0,.9)}
.listingblock>.content{position:relative}
.listingblock code[data-lang]::before{display:none;content:attr(data-lang);position:absolute;font-size:.75em;top:.425rem;right:.5rem;line-height:1;text-transform:uppercase;color:inherit;opacity:.5}
.listingblock:hover code[data-lang]::before{display:block}
.listingblock.terminal pre .command::before{content:attr(data-prompt);padding-right:.5em;color:inherit;opacity:.5}
.listingblock.terminal pre .command:not([data-prompt])::before{content:"$"}
.listingblock pre.highlightjs{padding:0}
.listingblock pre.highlightjs>code{padding:1em;border-radius:4px}
.listingblock pre.prettyprint{border-width:0}
.prettyprint{background:#f7f7f8}
pre.prettyprint .linenums{line-height:1.45;margin-left:2em}
pre.prettyprint li{background:none;list-style-type:inherit;padding-left:0}
pre.prettyprint li code[data-lang]::before{opacity:1}
pre.prettyprint li:not(:first-child) code[data-lang]::before{display:none}
table.linenotable{border-collapse:separate;border:0;margin-bottom:0;background:none}
table.linenotable td[class]{color:inherit;vertical-align:top;padding:0;line-height:inherit;white-space:normal}
table.linenotable td.code{padding-left:.75em}
table.linenotable td.linenos,pre.pygments .linenos{border-right:1px solid;opacity:.35;padding-right:.5em;-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none}
pre.pygments span.linenos{display:inline-block;margin-right:.75em}
.quoteblock{margin:0 1em 1.25em 1.5em;display:table}
.quoteblock:not(.excerpt)>.title{margin-left:-1.5em;margin-bottom:.75em}
.quoteblock blockquote,.quoteblock p{color:rgba(0,0,0,.85);font-size:1.15rem;line-height:1.75;word-spacing:.1em;letter-spacing:0;font-style:italic;text-align:justify}
.quoteblock blockquote{margin:0;padding:0;border:0}
.quoteblock blockquote::before{content:"\201c";float:left;font-size:2.75em;font-weight:bold;line-height:.6em;margin-left:-.6em;color:#7a2518;text-shadow:0 1px 2px rgba(0,0,0,.1)}
.quoteblock blockquote>.paragraph:last-child p{margin-bottom:0}
.quoteblock .attribution{margin-top:.75em;margin-right:.5ex;text-align:right}
.verseblock{margin:0 1em 1.25em}
.verseblock pre{font-family:"Open Sans","DejaVu Sans",sans-serif;font-size:1.15rem;color:rgba(0,0,0,.85);font-weight:300;text-rendering:optimizeLegibility}
.verseblock pre strong{font-weight:400}
.verseblock .attribution{margin-top:1.25rem;margin-left:.5ex}
.quoteblock .attribution,.verseblock .attribution{font-size:.9375em;line-height:1.45;font-style:italic}
.quoteblock .attribution br,.verseblock .attribution br{display:none}
.quoteblock .attribution cite,.verseblock .attribution cite{display:block;letter-spacing:-.025em;color:rgba(0,0,0,.6)}
.quoteblock.abstract blockquote::before,.quoteblock.excerpt blockquote::before,.quoteblock .quoteblock blockquote::before{display:none}
.quoteblock.abstract blockquote,.quoteblock.abstract p,.quoteblock.excerpt blockquote,.quoteblock.excerpt p,.quoteblock .quoteblock blockquote,.quoteblock .quoteblock p{line-height:1.6;word-spacing:0}
.quoteblock.abstract{margin:0 1em 1.25em;display:block}
.quoteblock.abstract>.title{margin:0 0 .375em;font-size:1.15em;text-align:center}
.quoteblock.excerpt>blockquote,.quoteblock .quoteblock{padding:0 0 .25em 1em;border-left:.25em solid #dddddf}
.quoteblock.excerpt,.quoteblock .quoteblock{margin-left:0}
.quoteblock.excerpt blockquote,.quoteblock.excerpt p,.quoteblock .quoteblock blockquote,.quoteblock .quoteblock p{color:inherit;font-size:1.0625rem}
.quoteblock.excerpt .attribution,.quoteblock .quoteblock .attribution{color:inherit;font-size:.85rem;text-align:left;margin-right:0}
p.tableblock:last-child{margin-bottom:0}
td.tableblock>.content{margin-bottom:1.25em;word-wrap:anywhere}
td.tableblock>.content>:last-child{margin-bottom:-1.25em}
table.tableblock,th.tableblock,td.tableblock{border:0 solid #dedede}
table.grid-all>*>tr>*{border-width:1px}
table.grid-cols>*>tr>*{border-width:0 1px}
table.grid-rows>*>tr>*{border-width:1px 0}
table.frame-all{border-width:1px}
table.frame-ends{border-width:1px 0}
table.frame-sides{border-width:0 1px}
table.frame-none>colgroup+*>:first-child>*,table.frame-sides>colgroup+*>:first-child>*{border-top-width:0}
table.frame-none>:last-child>:last-child>*,table.frame-sides>:last-child>:last-child>*{border-bottom-width:0}
table.frame-none>*>tr>:first-child,table.frame-ends>*>tr>:first-child{border-left-width:0}
table.frame-none>*>tr>:last-child,table.frame-ends>*>tr>:last-child{border-right-width:0}
table.stripes-all>*>tr,table.stripes-odd>*>tr:nth-of-type(odd),table.stripes-even>*>tr:nth-of-type(even),table.stripes-hover>*>tr:hover{background:#f8f8f7}
th.halign-left,td.halign-left{text-align:left}
th.halign-right,td.halign-right{text-align:right}
th.halign-center,td.halign-center{text-align:center}
th.valign-top,td.valign-top{vertical-align:top}
th.valign-bottom,td.valign-bottom{vertical-align:bottom}
th.valign-middle,td.valign-middle{vertical-align:middle}
table thead th,table tfoot th{font-weight:bold}
tbody tr th{background:#f7f8f7}
tbody tr th,tbody tr th p,tfoot tr th,tfoot tr th p{color:rgba(0,0,0,.8);font-weight:bold}
p.tableblock>code:only-child{background:none;padding:0}
p.tableblock{font-size:1em}
ol{margin-left:1.75em}
ul li ol{margin-left:1.5em}
dl dd{margin-left:1.125em}
dl dd:last-child,dl dd:last-child>:last-child{margin-bottom:0}
li p,ul dd,ol dd,.olist .olist,.ulist .ulist,.ulist .olist,.olist .ulist{margin-bottom:.625em}
ul.checklist,ul.none,ol.none,ul.no-bullet,ol.no-bullet,ol.unnumbered,ul.unstyled,ol.unstyled{list-style-type:none}
ul.no-bullet,ol.no-bullet,ol.unnumbered{margin-left:.625em}
ul.unstyled,ol.unstyled{margin-left:0}
li>p:empty:only-child::before{content:"";display:inline-block}
ul.checklist>li>p:first-child{margin-left:-1em}
ul.checklist>li>p:first-child>.fa-square-o:first-child,ul.checklist>li>p:first-child>.fa-check-square-o:first-child{width:1.25em;font-size:.8em;position:relative;bottom:.125em}
ul.checklist>li>p:first-child>input[type=checkbox]:first-child{margin-right:.25em}
ul.inline{display:flex;flex-flow:row wrap;list-style:none;margin:0 0 .625em -1.25em}
ul.inline>li{margin-left:1.25em}
.unstyled dl dt{font-weight:400;font-style:normal}
ol.arabic{list-style-type:decimal}
ol.decimal{list-style-type:decimal-leading-zero}
ol.loweralpha{list-style-type:lower-alpha}
ol.upperalpha{list-style-type:upper-alpha}
ol.lowerroman{list-style-type:lower-roman}
ol.upperroman{list-style-type:upper-roman}
ol.lowergreek{list-style-type:lower-greek}
.hdlist>table,.colist>table{border:0;background:none}
.hdlist>table>tbody>tr,.colist>table>tbody>tr{background:none}
td.hdlist1,td.hdlist2{vertical-align:top;padding:0 .625em}
td.hdlist1{font-weight:bold;padding-bottom:1.25em}
td.hdlist2{word-wrap:anywhere}
.literalblock+.colist,.listingblock+.colist{margin-top:-.5em}
.colist td:not([class]):first-child{padding:.4em .75em 0;line-height:1;vertical-align:top}
.colist td:not([class]):first-child img{max-width:none}
.colist td:not([class]):last-child{padding:.25em 0}
.thumb,.th{line-height:0;display:inline-block;border:4px solid #fff;box-shadow:0 0 0 1px #ddd}
.imageblock.left{margin:.25em .625em 1.25em 0}
.imageblock.right{margin:.25em 0 1.25em .625em}
.imageblock>.title{margin-bottom:0}
.imageblock.thumb,.imageblock.th{border-width:6px}
.imageblock.thumb>.title,.imageblock.th>.title{padding:0 .125em}
.image.left,.image.right{margin-top:.25em;margin-bottom:.25em;display:inline-block;line-height:0}
.image.left{margin-right:.625em}
.image.right{margin-left:.625em}
a.image{text-decoration:none;display:inline-block}
a.image object{pointer-events:none}
sup.footnote,sup.footnoteref{font-size:.875em;position:static;vertical-align:super}
sup.footnote a,sup.footnoteref a{text-decoration:none}
sup.footnote a:active,sup.footnoteref a:active,#footnotes .footnote a:first-of-type:active{text-decoration:underline}
#footnotes{padding-top:.75em;padding-bottom:.75em;margin-bottom:.625em}
#footnotes hr{width:20%;min-width:6.25em;margin:-.25em 0 .75em;border-width:1px 0 0}
#footnotes .footnote{padding:0 .375em 0 .225em;line-height:1.3334;font-size:.875em;margin-left:1.2em;margin-bottom:.2em}
#footnotes .footnote a:first-of-type{font-weight:bold;text-decoration:none;margin-left:-1.05em}
#footnotes .footnote:last-of-type{margin-bottom:0}
#content #footnotes{margin-top:-.625em;margin-bottom:0;padding:.75em 0}
div.unbreakable{page-break-inside:avoid}
.big{font-size:larger}
.small{font-size:smaller}
.underline{text-decoration:underline}
.overline{text-decoration:overline}
.line-through{text-decoration:line-through}
.aqua{color:#00bfbf}
.aqua-background{background:#00fafa}
.black{color:#000}
.black-background{background:#000}
.blue{color:#0000bf}
.blue-background{background:#0000fa}
.fuchsia{color:#bf00bf}
.fuchsia-background{background:#fa00fa}
.gray{color:#606060}
.gray-background{background:#7d7d7d}
.green{color:#006000}
.green-background{background:#007d00}
.lime{color:#00bf00}
.lime-background{background:#00fa00}
.maroon{color:#600000}
.maroon-background{background:#7d0000}
.navy{color:#000060}
.navy-background{background:#00007d}
.olive{color:#606000}
.olive-background{background:#7d7d00}
.purple{color:#600060}
.purple-background{background:#7d007d}
.red{color:#bf0000}
.red-background{background:#fa0000}
.silver{color:#909090}
.silver-background{background:#bcbcbc}
.teal{color:#006060}
.teal-background{background:#007d7d}
.white{color:#bfbfbf}
.white-background{background:#fafafa}
.yellow{color:#bfbf00}
.yellow-background{background:#fafa00}
span.icon>.fa{cursor:default}
a span.icon>.fa{cursor:inherit}
.admonitionblock td.icon [class^="fa icon-"]{font-size:2.5em;text-shadow:1px 1px 2px rgba(0,0,0,.5);cursor:default}
.admonitionblock td.icon .icon-note::before{content:"\f05a";color:#19407c}
.admonitionblock td.icon .icon-tip::before{content:"\f0eb";text-shadow:1px 1px 2px rgba(155,155,0,.8);color:#111}
.admonitionblock td.icon .icon-warning::before{content:"\f071";color:#bf6900}
.admonitionblock td.icon .icon-caution::before{content:"\f06d";color:#bf3400}
.admonitionblock td.icon .icon-important::before{content:"\f06a";color:#bf0000}
.conum[data-value]{display:inline-block;color:#fff!important;background:rgba(0,0,0,.8);border-radius:50%;text-align:center;font-size:.75em;width:1.67em;height:1.67em;line-height:1.67em;font-family:"Open Sans","DejaVu Sans",sans-serif;font-style:normal;font-weight:bold}
.conum[data-value] *{color:#fff!important}
.conum[data-value]+b{display:none}
.conum[data-value]::after{content:attr(data-value)}
pre .conum[data-value]{position:relative;top:-.125em}
b.conum *{color:inherit!important}
.conum:not([data-value]):empty{display:none}
dt,th.tableblock,td.content,div.footnote{text-rendering:optimizeLegibility}
h1,h2,p,td.content,span.alt,summary{letter-spacing:-.01em}
p strong,td.content strong,div.footnote strong{letter-spacing:-.005em}
p,blockquote,dt,td.content,td.hdlist1,span.alt,summary{font-size:1.0625rem}
p{margin-bottom:1.25rem}
.sidebarblock p,.sidebarblock dt,.sidebarblock td.content,p.tableblock{font-size:1em}
.exampleblock>.content{background:#fffef7;border-color:#e0e0dc;box-shadow:0 1px 4px #e0e0dc}
.print-only{display:none!important}
@page{margin:1.25cm .75cm}
@media print{*{box-shadow:none!important;text-shadow:none!important}
html{font-size:80%}
a{color:inherit!important;text-decoration:underline!important}
a.bare,a[href^="#"],a[href^="mailto:"]{text-decoration:none!important}
a[href^="http:"]:not(.bare)::after,a[href^="https:"]:not(.bare)::after{content:"(" attr(href) ")";display:inline-block;font-size:.875em;padding-left:.25em}
abbr[title]{border-bottom:1px dotted}
abbr[title]::after{content:" (" attr(title) ")"}
pre,blockquote,tr,img,object,svg{page-break-inside:avoid}
thead{display:table-header-group}
svg{max-width:100%}
p,blockquote,dt,td.content{font-size:1em;orphans:3;widows:3}
h2,h3,#toctitle,.sidebarblock>.content>.title{page-break-after:avoid}
#header,#content,#footnotes,#footer{max-width:none}
#toc,.sidebarblock,.exampleblock>.content{background:none!important}
#toc{border-bottom:1px solid #dddddf!important;padding-bottom:0!important}
body.book #header{text-align:center}
body.book #header>h1:first-child{border:0!important;margin:2.5em 0 1em}
body.book #header .details{border:0!important;display:block;padding:0!important}
body.book #header .details span:first-child{margin-left:0!important}
body.book #header .details br{display:block}
body.book #header .details br+span::before{content:none!important}
body.book #toc{border:0!important;text-align:left!important;padding:0!important;margin:0!important}
body.book #toc,body.book #preamble,body.book h1.sect0,body.book .sect1>h2{page-break-before:always}
.listingblock code[data-lang]::before{display:block}
#footer{padding:0 .9375em}
.hide-on-print{display:none!important}
.print-only{display:block!important}
.hide-for-print{display:none!important}
.show-for-print{display:inherit!important}}
@media amzn-kf8,print{#header>h1:first-child{margin-top:1.25rem}
.sect1{padding:0!important}
.sect1+.sect1{border:0}
#footer{background:none}
#footer-text{color:rgba(0,0,0,.6);font-size:.9em}}
@media amzn-kf8{#header,#content,#footnotes,#footer{padding:0}}
</style>
</head>
<body class="article">
<div id="header">
<h1>Git Commit-Graph Design Notes</h1>
</div>
<div id="content">
<div id="preamble">
<div class="sectionbody">
<div class="paragraph">
<p>Git walks the commit graph for many reasons, including:</p>
</div>
<div class="olist arabic">
<ol class="arabic">
<li>
<p>Listing and filtering commit history.</p>
</li>
<li>
<p>Computing merge bases.</p>
</li>
</ol>
</div>
<div class="paragraph">
<p>These operations can become slow as the commit count grows. The merge
base calculation shows up in many user-facing commands, such as <em>merge-base</em>
or <em>status</em> and can take minutes to compute depending on history shape.</p>
</div>
<div class="paragraph">
<p>There are two main costs here:</p>
</div>
<div class="olist arabic">
<ol class="arabic">
<li>
<p>Decompressing and parsing commits.</p>
</li>
<li>
<p>Walking the entire graph to satisfy topological order constraints.</p>
</li>
</ol>
</div>
<div class="paragraph">
<p>The commit-graph file is a supplemental data structure that accelerates
commit graph walks. If a user downgrades or disables the <em>core.commitGraph</em>
config setting, then the existing object database is sufficient. The file is stored
as "commit-graph" either in the .git/objects/info directory or in the info
directory of an alternate.</p>
</div>
<div class="paragraph">
<p>The commit-graph file stores the commit graph structure along with some
extra metadata to speed up graph walks. By listing commit OIDs in
lexicographic order, we can identify an integer position for each commit
and refer to the parents of a commit using those integer positions. We
use binary search to find initial commits and then use the integer
positions for fast lookups during the walk.</p>
</div>
<div class="paragraph">
<p>A consumer may load the following info for a commit from the graph:</p>
</div>
<div class="olist arabic">
<ol class="arabic">
<li>
<p>The commit OID.</p>
</li>
<li>
<p>The list of parents, along with their integer position.</p>
</li>
<li>
<p>The commit date.</p>
</li>
<li>
<p>The root tree OID.</p>
</li>
<li>
<p>The generation number (see definition below).</p>
</li>
</ol>
</div>
<div class="paragraph">
<p>Values 1-4 satisfy the requirements of parse_commit_gently().</p>
</div>
<div class="paragraph">
<p>There are two definitions of generation number:</p>
</div>
<div class="olist arabic">
<ol class="arabic">
<li>
<p>Corrected committer dates (generation number v2)</p>
</li>
<li>
<p>Topological levels (generation number v1)</p>
</li>
</ol>
</div>
<div class="paragraph">
<p>Define "corrected committer date" of a commit recursively as follows:</p>
</div>
<div class="ulist">
<ul>
<li>
<p>A commit with no parents (a root commit) has corrected committer date
equal to its committer date.</p>
</li>
<li>
<p>A commit with at least one parent has corrected committer date equal to
the maximum of its committer date and one more than the largest corrected
committer date among its parents.</p>
</li>
<li>
<p>As a special case, a root commit with timestamp zero has corrected commit
date of 1, to be able to distinguish it from GENERATION_NUMBER_ZERO
(that is, an uncomputed corrected commit date).</p>
</li>
</ul>
</div>
<div class="paragraph">
<p>Define the "topological level" of a commit recursively as follows:</p>
</div>
<div class="ulist">
<ul>
<li>
<p>A commit with no parents (a root commit) has topological level of one.</p>
</li>
<li>
<p>A commit with at least one parent has topological level one more than
the largest topological level among its parents.</p>
</li>
</ul>
</div>
<div class="paragraph">
<p>Equivalently, the topological level of a commit A is one more than the
length of a longest path from A to a root commit. The recursive definition
is easier to use for computation and observing the following property:</p>
</div>
<div class="literalblock">
<div class="content">
<pre>If A and B are commits with generation numbers N and M, respectively,
and N &lt;= M, then A cannot reach B. That is, we know without searching
that B is not an ancestor of A because it is further from a root commit
than A.</pre>
</div>
</div>
<div class="literalblock">
<div class="content">
<pre>Conversely, when checking if A is an ancestor of B, then we only need
to walk commits until all commits on the walk boundary have generation
number at most N. If we walk commits using a priority queue seeded by
generation numbers, then we always expand the boundary commit with highest
generation number and can easily detect the stopping condition.</pre>
</div>
</div>
<div class="paragraph">
<p>The property applies to both versions of generation number, that is both
corrected committer dates and topological levels.</p>
</div>
<div class="paragraph">
<p>This property can be used to significantly reduce the time it takes to
walk commits and determine topological relationships. Without generation
numbers, the general heuristic is the following:</p>
</div>
<div class="literalblock">
<div class="content">
<pre>If A and B are commits with commit time X and Y, respectively, and
X &lt; Y, then A _probably_ cannot reach B.</pre>
</div>
</div>
<div class="paragraph">
<p>In absence of corrected commit dates (for example, old versions of Git or
mixed generation graph chains),
this heuristic is currently used whenever the computation is allowed to
violate topological relationships due to clock skew (such as "git log"
with default order), but is not used when the topological order is
required (such as merge base calculations, "git log --graph").</p>
</div>
<div class="paragraph">
<p>In practice, we expect some commits to be created recently and not stored
in the commit-graph. We can treat these commits as having "infinite"
generation number and walk until reaching commits with known generation
number.</p>
</div>
<div class="paragraph">
<p>We use the macro GENERATION_NUMBER_INFINITY to mark commits not
in the commit-graph file. If a commit-graph file was written by a version
of Git that did not compute generation numbers, then those commits will
have generation number represented by the macro GENERATION_NUMBER_ZERO = 0.</p>
</div>
<div class="paragraph">
<p>Since the commit-graph file is closed under reachability, we can guarantee
the following weaker condition on all commits:</p>
</div>
<div class="literalblock">
<div class="content">
<pre>If A and B are commits with generation numbers N and M, respectively,
and N &lt; M, then A cannot reach B.</pre>
</div>
</div>
<div class="paragraph">
<p>Note how the strict inequality differs from the inequality when we have
fully-computed generation numbers. Using strict inequality may result in
walking a few extra commits, but the simplicity in dealing with commits
with generation number *_INFINITY or *_ZERO is valuable.</p>
</div>
<div class="paragraph">
<p>We use the macro GENERATION_NUMBER_V1_MAX = 0x3FFFFFFF for commits whose
topological levels (generation number v1) are computed to be at least
this value. We limit at this value since it is the largest value that
can be stored in the commit-graph file using the 30 bits available
to topological levels. This presents another case where a commit can
have generation number equal to that of a parent.</p>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_design_details">Design Details</h2>
<div class="sectionbody">
<div class="ulist">
<ul>
<li>
<p>The commit-graph file is stored in a file named <em>commit-graph</em> in the
.git/objects/info directory. This could be stored in the info directory
of an alternate.</p>
</li>
<li>
<p>The core.commitGraph config setting must be on to consume graph files.</p>
</li>
<li>
<p>The file format includes parameters for the object ID hash function,
so a future change of hash algorithm does not require a change in format.</p>
</li>
<li>
<p>Commit grafts and replace objects can change the shape of the commit
history. The latter can also be enabled/disabled on the fly using
<code>--no-replace-objects</code>. This leads to difficulty storing both possible
interpretations of a commit id, especially when computing generation
numbers. The commit-graph will not be read or written when
replace-objects or grafts are present.</p>
</li>
<li>
<p>Shallow clones create grafts of commits by dropping their parents. This
leads the commit-graph to think those commits have generation number 1.
If and when those commits are made unshallow, those generation numbers
become invalid. Since shallow clones are intended to restrict the commit
history to a very small set of commits, the commit-graph feature is less
helpful for these clones, anyway. The commit-graph will not be read or
written when shallow commits are present.</p>
</li>
</ul>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_commit_graphs_chains">Commit-Graphs Chains</h2>
<div class="sectionbody">
<div class="paragraph">
<p>Typically, repos grow with near-constant velocity (commits per day). Over time,
the number of commits added by a fetch operation is much smaller than the
number of commits in the full history. By creating a "chain" of commit-graphs,
we enable fast writes of new commit data without rewriting the entire commit
history&#8201;&#8212;&#8201;at least, most of the time.</p>
</div>
<div class="sect2">
<h3 id="_file_layout">File Layout</h3>
<div class="paragraph">
<p>A commit-graph chain uses multiple files, and we use a fixed naming convention
to organize these files. Each commit-graph file has a name
<code>$OBJDIR/info/commit-graphs/graph-</code>{hash}.<code>graph</code> where {hash} is the hex-
valued hash stored in the footer of that file (which is a hash of the file&#8217;s
contents before that hash). For a chain of commit-graph files, a plain-text
file at <code>$OBJDIR/info/commit-graphs/commit-graph-chain</code> contains the
hashes for the files in order from "lowest" to "highest".</p>
</div>
<div class="paragraph">
<p>For example, if the <code>commit-graph-chain</code> file contains the lines</p>
</div>
<div class="listingblock">
<div class="content">
<pre>        {hash0}
        {hash1}
        {hash2}</pre>
</div>
</div>
<div class="paragraph">
<p>then the commit-graph chain looks like the following diagram:</p>
</div>
<div class="literalblock">
<div class="content">
<pre>+-----------------------+
|  graph-{hash2}.graph  |
+-----------------------+
  |
+-----------------------+
|                       |
|  graph-{hash1}.graph  |
|                       |
+-----------------------+
  |
+-----------------------+
|                       |
|                       |
|                       |
|  graph-{hash0}.graph  |
|                       |
|                       |
|                       |
+-----------------------+</pre>
</div>
</div>
<div class="paragraph">
<p>Let X0 be the number of commits in <code>graph-</code>{hash0}.<code>graph</code>, X1 be the number of
commits in <code>graph-</code>{hash1}.<code>graph</code>, and X2 be the number of commits in
<code>graph-</code>{hash2}.<code>graph</code>. If a commit appears in position i in <code>graph-</code>{hash2}.<code>graph</code>,
then we interpret this as being the commit in position (X0 + X1 + i), and that
will be used as its "graph position". The commits in <code>graph-</code>{hash2}.<code>graph</code> use these
positions to refer to their parents, which may be in <code>graph-</code>{hash1}.<code>graph</code> or
<code>graph-</code>{hash0}.<code>graph</code>. We can navigate to an arbitrary commit in position j by checking
its containment in the intervals [0, X0), [X0, X0 + X1), [X0 + X1, X0 + X1<br/>
X2).</p>
</div>
<div class="paragraph">
<p>Each commit-graph file (except the base, <code>graph-</code>{hash0}.<code>graph</code>) contains data
specifying the hashes of all files in the lower layers. In the above example,
<code>graph-</code>{hash1}.<code>graph</code> contains {hash0} while <code>graph-</code>{hash2}.<code>graph</code> contains
{hash0} and {hash1}.</p>
</div>
</div>
<div class="sect2">
<h3 id="_merging_commit_graph_files">Merging commit-graph files</h3>
<div class="paragraph">
<p>If we only added a new commit-graph file on every write, we would run into a
linear search problem through many commit-graph files.  Instead, we use a merge
strategy to decide when the stack should collapse some number of levels.</p>
</div>
<div class="paragraph">
<p>The diagram below shows such a collapse. As a set of new commits are added, it
is determined by the merge strategy that the files should collapse to
<code>graph-</code>{hash1}. Thus, the new commits, the commits in <code>graph-</code>{hash2} and
the commits in <code>graph-</code>{hash1} should be combined into a new <code>graph-</code>{hash3}
file.</p>
</div>
<div class="literalblock">
<div class="content">
<pre>                            +---------------------+
                            |                     |
                            |    (new commits)    |
                            |                     |
                            +---------------------+
                            |                     |
 +-----------------------+  +---------------------+
 |  graph-{hash2}        |-&gt;|                     |
 +-----------------------+  +---------------------+
          |                 |                     |
 +-----------------------+  +---------------------+
 |                       |  |                     |
 |  graph-{hash1}        |-&gt;|                     |
 |                       |  |                     |
 +-----------------------+  +---------------------+
          |                  tmp_graphXXX
 +-----------------------+
 |                       |
 |                       |
 |                       |
 |  graph-{hash0}        |
 |                       |
 |                       |
 |                       |
 +-----------------------+</pre>
</div>
</div>
<div class="paragraph">
<p>During this process, the commits to write are combined, sorted and we write the
contents to a temporary file, all while holding a <code>commit-graph-chain.lock</code>
lock-file.  When the file is flushed, we rename it to <code>graph-</code>{hash3}
according to the computed {hash3}. Finally, we write the new chain data to
<code>commit-graph-chain.lock</code>:</p>
</div>
<div class="listingblock">
<div class="content">
<pre>        {hash3}
        {hash0}</pre>
</div>
</div>
<div class="paragraph">
<p>We then close the lock-file.</p>
</div>
</div>
<div class="sect2">
<h3 id="_merge_strategy">Merge Strategy</h3>
<div class="paragraph">
<p>When writing a set of commits that do not exist in the commit-graph stack of
height N, we default to creating a new file at level N + 1. We then decide to
merge with the Nth level if one of two conditions hold:</p>
</div>
<div class="olist arabic">
<ol class="arabic">
<li>
<p><code>--size-multiple=</code><em>&lt;X&gt;</em> is specified or X = 2, and the number of commits in
level N is less than X times the number of commits in level N + 1.</p>
</li>
<li>
<p><code>--max-commits=</code><em>&lt;C&gt;</em> is specified with non-zero C and the number of commits
in level N + 1 is more than C commits.</p>
</li>
</ol>
</div>
<div class="paragraph">
<p>This decision cascades down the levels: when we merge a level we create a new
set of commits that then compares to the next level.</p>
</div>
<div class="paragraph">
<p>The first condition bounds the number of levels to be logarithmic in the total
number of commits.  The second condition bounds the total number of commits in
a <code>graph-</code>{hashN} file and not in the <code>commit-graph</code> file, preventing
significant performance issues when the stack merges and another process only
partially reads the previous stack.</p>
</div>
<div class="paragraph">
<p>The merge strategy values (2 for the size multiple, 64,000 for the maximum
number of commits) could be extracted into config settings for full
flexibility.</p>
</div>
</div>
<div class="sect2">
<h3 id="_handling_mixed_generation_number_chains">Handling Mixed Generation Number Chains</h3>
<div class="paragraph">
<p>With the introduction of generation number v2 and generation data chunk, the
following scenario is possible:</p>
</div>
<div class="olist arabic">
<ol class="arabic">
<li>
<p>"New" Git writes a commit-graph with the corrected commit dates.</p>
</li>
<li>
<p>"Old" Git writes a split commit-graph on top without corrected commit dates.</p>
</li>
</ol>
</div>
<div class="paragraph">
<p>A naive approach of using the newest available generation number from
each layer would lead to violated expectations: the lower layer would
use corrected commit dates which are much larger than the topological
levels of the higher layer. For this reason, Git inspects the topmost
layer to see if the layer is missing corrected commit dates. In such a case
Git only uses topological level for generation numbers.</p>
</div>
<div class="paragraph">
<p>When writing a new layer in split commit-graph, we write corrected commit
dates if the topmost layer has corrected commit dates written. This
guarantees that if a layer has corrected commit dates, all lower layers
must have corrected commit dates as well.</p>
</div>
<div class="paragraph">
<p>When merging layers, we do not consider whether the merged layers had corrected
commit dates. Instead, the new layer will have corrected commit dates if the
layer below the new layer has corrected commit dates.</p>
</div>
<div class="paragraph">
<p>While writing or merging layers, if the new layer is the only layer, it will
have corrected commit dates when written by compatible versions of Git. Thus,
rewriting split commit-graph as a single file (<code>--split=replace</code>) creates a
single layer with corrected commit dates.</p>
</div>
</div>
<div class="sect2">
<h3 id="_deleting_graph_hash_files">Deleting graph-{hash} files</h3>
<div class="paragraph">
<p>After a new tip file is written, some <code>graph-</code>{hash} files may no longer
be part of a chain. It is important to remove these files from disk, eventually.
The main reason to delay removal is that another process could read the
<code>commit-graph-chain</code> file before it is rewritten, but then look for the
<code>graph-</code>{hash} files after they are deleted.</p>
</div>
<div class="paragraph">
<p>To allow holding old split commit-graphs for a while after they are unreferenced,
we update the modified times of the files when they become unreferenced. Then,
we scan the <code>$OBJDIR/info/commit-graphs/</code> directory for <code>graph-</code>{hash}
files whose modified times are older than a given expiry window. This window
defaults to zero, but can be changed using command-line arguments or a config
setting.</p>
</div>
</div>
<div class="sect2">
<h3 id="_chains_across_multiple_object_directories">Chains across multiple object directories</h3>
<div class="paragraph">
<p>In a repo with alternates, we look for the <code>commit-graph-chain</code> file starting
in the local object directory and then in each alternate. The first file that
exists defines our chain. As we look for the <code>graph-</code>{hash} files for
each {hash} in the chain file, we follow the same pattern for the host
directories.</p>
</div>
<div class="paragraph">
<p>This allows commit-graphs to be split across multiple forks in a fork network.
The typical case is a large "base" repo with many smaller forks.</p>
</div>
<div class="paragraph">
<p>As the base repo advances, it will likely update and merge its commit-graph
chain more frequently than the forks. If a fork updates their commit-graph after
the base repo, then it should "reparent" the commit-graph chain onto the new
chain in the base repo. When reading each <code>graph-</code>{hash} file, we track
the object directory containing it. During a write of a new commit-graph file,
we check for any changes in the source object directory and read the
<code>commit-graph-chain</code> file for that source and create a new file based on those
files. During this "reparent" operation, we necessarily need to collapse all
levels in the fork, as all of the files are invalid against the new base file.</p>
</div>
<div class="paragraph">
<p>It is crucial to be careful when cleaning up "unreferenced" <code>graph-</code>{hash}.<code>graph</code>
files in this scenario. It falls to the user to define the proper settings for
their custom environment:</p>
</div>
<div class="olist arabic">
<ol class="arabic">
<li>
<p>When merging levels in the base repo, the unreferenced files may still be
referenced by chains from fork repos.</p>
</li>
<li>
<p>The expiry time should be set to a length of time such that every fork has
time to recompute their commit-graph chain to "reparent" onto the new base
file(s).</p>
</li>
<li>
<p>If the commit-graph chain is updated in the base, the fork will not have
access to the new chain until its chain is updated to reference those files.
(This may change in the future [5].)</p>
</li>
</ol>
</div>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_related_links">Related Links</h2>
<div class="sectionbody">
<div class="paragraph">
<p>[0] <a href="https://bugs.chromium.org/p/git/issues/detail?id=8" class="bare">https://bugs.chromium.org/p/git/issues/detail?id=8</a>
    Chromium work item for: Serialized Commit Graph</p>
</div>
<div class="paragraph">
<p>[1] <a href="https://lore.kernel.org/git/20110713070517.GC18566@sigill.intra.peff.net/" class="bare">https://lore.kernel.org/git/20110713070517.GC18566@sigill.intra.peff.net/</a>
    An abandoned patch that introduced generation numbers.</p>
</div>
<div class="paragraph">
<p>[2] <a href="https://lore.kernel.org/git/20170908033403.q7e6dj7benasrjes@sigill.intra.peff.net/" class="bare">https://lore.kernel.org/git/20170908033403.q7e6dj7benasrjes@sigill.intra.peff.net/</a>
    Discussion about generation numbers on commits and how they interact
    with fsck.</p>
</div>
<div class="paragraph">
<p>[3] <a href="https://lore.kernel.org/git/20170908034739.4op3w4f2ma5s65ku@sigill.intra.peff.net/" class="bare">https://lore.kernel.org/git/20170908034739.4op3w4f2ma5s65ku@sigill.intra.peff.net/</a>
    More discussion about generation numbers and not storing them inside
    commit objects. A valuable quote:</p>
</div>
<div class="literalblock">
<div class="content">
<pre>"I think we should be moving more in the direction of keeping
 repo-local caches for optimizations. Reachability bitmaps have been
 a big performance win. I think we should be doing the same with our
 properties of commits. Not just generation numbers, but making it
 cheap to access the graph structure without zlib-inflating whole
 commit objects (i.e., packv4 or something like the "metapacks" I
 proposed a few years ago)."</pre>
</div>
</div>
<div class="paragraph">
<p>[4] <a href="https://lore.kernel.org/git/20180108154822.54829-1-git@jeffhostetler.com/T/#u" class="bare">https://lore.kernel.org/git/20180108154822.54829-1-git@jeffhostetler.com/T/#u</a>
    A patch to remove the ahead-behind calculation from <em>status</em>.</p>
</div>
<div class="paragraph">
<p>[5] <a href="https://lore.kernel.org/git/f27db281-abad-5043-6d71-cbb083b1c877@gmail.com/" class="bare">https://lore.kernel.org/git/f27db281-abad-5043-6d71-cbb083b1c877@gmail.com/</a>
    A discussion of a "two-dimensional graph position" that can allow reading
    multiple commit-graph chains at the same time.</p>
</div>
</div>
</div>
</div>
<div id="footer">
<div id="footer-text">
Last updated 2025-10-24 14:37:25 -0700
</div>
</div>
</body>
</html>