| <!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.26"/> | |
| <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.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 pre>code{display:block} | |
| .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 <= 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 < 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 < 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 — 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’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} |->| | | |
| +-----------------------+ +---------------------+ | |
| | | | | |
| +-----------------------+ +---------------------+ | |
| | | | | | |
| | graph-{hash1} |->| | | |
| | | | | | |
| +-----------------------+ +---------------------+ | |
| | 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><X></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><C></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> |