MyFirstObjectWalk.html

   1 <?xml version="1.0" encoding="UTF-8"?>
   2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
   3     "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
   4 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
   5 <head>
   6 <meta http-equiv="Content-Type" content="application/xhtml+xml; charset=UTF-8" />
   7 <meta name="generator" content="AsciiDoc 10.2.0" />
   8 <title>My First Object Walk</title>
   9 <style type="text/css">
  10 /* Shared CSS for AsciiDoc xhtml11 and html5 backends */
  11
  12 /* Default font. */
  13 body {
  14   font-family: Georgia,serif;
  15 }
  16
  17 /* Title font. */
  18 h1, h2, h3, h4, h5, h6,
  19 div.title, caption.title,
  20 thead, p.table.header,
  21 #toctitle,
  22 #author, #revnumber, #revdate, #revremark,
  23 #footer {
  24   font-family: Arial,Helvetica,sans-serif;
  25 }
  26
  27 body {
  28   margin: 1em 5% 1em 5%;
  29 }
  30
  31 a {
  32   color: blue;
  33   text-decoration: underline;
  34 }
  35 a:visited {
  36   color: fuchsia;
  37 }
  38
  39 em {
  40   font-style: italic;
  41   color: navy;
  42 }
  43
  44 strong {
  45   font-weight: bold;
  46   color: #083194;
  47 }
  48
  49 h1, h2, h3, h4, h5, h6 {
  50   color: #527bbd;
  51   margin-top: 1.2em;
  52   margin-bottom: 0.5em;
  53   line-height: 1.3;
  54 }
  55
  56 h1, h2, h3 {
  57   border-bottom: 2px solid silver;
  58 }
  59 h2 {
  60   padding-top: 0.5em;
  61 }
  62 h3 {
  63   float: left;
  64 }
  65 h3 + * {
  66   clear: left;
  67 }
  68 h5 {
  69   font-size: 1.0em;
  70 }
  71
  72 div.sectionbody {
  73   margin-left: 0;
  74 }
  75
  76 hr {
  77   border: 1px solid silver;
  78 }
  79
  80 p {
  81   margin-top: 0.5em;
  82   margin-bottom: 0.5em;
  83 }
  84
  85 ul, ol, li > p {
  86   margin-top: 0;
  87 }
  88 ul > li     { color: #aaa; }
  89 ul > li > * { color: black; }
  90
  91 .monospaced, code, pre {
  92   font-family: "Courier New", Courier, monospace;
  93   font-size: inherit;
  94   color: navy;
  95   padding: 0;
  96   margin: 0;
  97 }
  98 pre {
  99   white-space: pre-wrap;
 100 }
 101
 102 #author {
 103   color: #527bbd;
 104   font-weight: bold;
 105   font-size: 1.1em;
 106 }
 107 #email {
 108 }
 109 #revnumber, #revdate, #revremark {
 110 }
 111
 112 #footer {
 113   font-size: small;
 114   border-top: 2px solid silver;
 115   padding-top: 0.5em;
 116   margin-top: 4.0em;
 117 }
 118 #footer-text {
 119   float: left;
 120   padding-bottom: 0.5em;
 121 }
 122 #footer-badges {
 123   float: right;
 124   padding-bottom: 0.5em;
 125 }
 126
 127 #preamble {
 128   margin-top: 1.5em;
 129   margin-bottom: 1.5em;
 130 }
 131 div.imageblock, div.exampleblock, div.verseblock,
 132 div.quoteblock, div.literalblock, div.listingblock, div.sidebarblock,
 133 div.admonitionblock {
 134   margin-top: 1.0em;
 135   margin-bottom: 1.5em;
 136 }
 137 div.admonitionblock {
 138   margin-top: 2.0em;
 139   margin-bottom: 2.0em;
 140   margin-right: 10%;
 141   color: #606060;
 142 }
 143
 144 div.content { /* Block element content. */
 145   padding: 0;
 146 }
 147
 148 /* Block element titles. */
 149 div.title, caption.title {
 150   color: #527bbd;
 151   font-weight: bold;
 152   text-align: left;
 153   margin-top: 1.0em;
 154   margin-bottom: 0.5em;
 155 }
 156 div.title + * {
 157   margin-top: 0;
 158 }
 159
 160 td div.title:first-child {
 161   margin-top: 0.0em;
 162 }
 163 div.content div.title:first-child {
 164   margin-top: 0.0em;
 165 }
 166 div.content + div.title {
 167   margin-top: 0.0em;
 168 }
 169
 170 div.sidebarblock > div.content {
 171   background: #ffffee;
 172   border: 1px solid #dddddd;
 173   border-left: 4px solid #f0f0f0;
 174   padding: 0.5em;
 175 }
 176
 177 div.listingblock > div.content {
 178   border: 1px solid #dddddd;
 179   border-left: 5px solid #f0f0f0;
 180   background: #f8f8f8;
 181   padding: 0.5em;
 182 }
 183
 184 div.quoteblock, div.verseblock {
 185   padding-left: 1.0em;
 186   margin-left: 1.0em;
 187   margin-right: 10%;
 188   border-left: 5px solid #f0f0f0;
 189   color: #888;
 190 }
 191
 192 div.quoteblock > div.attribution {
 193   padding-top: 0.5em;
 194   text-align: right;
 195 }
 196
 197 div.verseblock > pre.content {
 198   font-family: inherit;
 199   font-size: inherit;
 200 }
 201 div.verseblock > div.attribution {
 202   padding-top: 0.75em;
 203   text-align: left;
 204 }
 205 /* DEPRECATED: Pre version 8.2.7 verse style literal block. */
 206 div.verseblock + div.attribution {
 207   text-align: left;
 208 }
 209
 210 div.admonitionblock .icon {
 211   vertical-align: top;
 212   font-size: 1.1em;
 213   font-weight: bold;
 214   text-decoration: underline;
 215   color: #527bbd;
 216   padding-right: 0.5em;
 217 }
 218 div.admonitionblock td.content {
 219   padding-left: 0.5em;
 220   border-left: 3px solid #dddddd;
 221 }
 222
 223 div.exampleblock > div.content {
 224   border-left: 3px solid #dddddd;
 225   padding-left: 0.5em;
 226 }
 227
 228 div.imageblock div.content { padding-left: 0; }
 229 span.image img { border-style: none; vertical-align: text-bottom; }
 230 a.image:visited { color: white; }
 231
 232 dl {
 233   margin-top: 0.8em;
 234   margin-bottom: 0.8em;
 235 }
 236 dt {
 237   margin-top: 0.5em;
 238   margin-bottom: 0;
 239   font-style: normal;
 240   color: navy;
 241 }
 242 dd > *:first-child {
 243   margin-top: 0.1em;
 244 }
 245
 246 ul, ol {
 247     list-style-position: outside;
 248 }
 249 ol.arabic {
 250   list-style-type: decimal;
 251 }
 252 ol.loweralpha {
 253   list-style-type: lower-alpha;
 254 }
 255 ol.upperalpha {
 256   list-style-type: upper-alpha;
 257 }
 258 ol.lowerroman {
 259   list-style-type: lower-roman;
 260 }
 261 ol.upperroman {
 262   list-style-type: upper-roman;
 263 }
 264
 265 div.compact ul, div.compact ol,
 266 div.compact p, div.compact p,
 267 div.compact div, div.compact div {
 268   margin-top: 0.1em;
 269   margin-bottom: 0.1em;
 270 }
 271
 272 tfoot {
 273   font-weight: bold;
 274 }
 275 td > div.verse {
 276   white-space: pre;
 277 }
 278
 279 div.hdlist {
 280   margin-top: 0.8em;
 281   margin-bottom: 0.8em;
 282 }
 283 div.hdlist tr {
 284   padding-bottom: 15px;
 285 }
 286 dt.hdlist1.strong, td.hdlist1.strong {
 287   font-weight: bold;
 288 }
 289 td.hdlist1 {
 290   vertical-align: top;
 291   font-style: normal;
 292   padding-right: 0.8em;
 293   color: navy;
 294 }
 295 td.hdlist2 {
 296   vertical-align: top;
 297 }
 298 div.hdlist.compact tr {
 299   margin: 0;
 300   padding-bottom: 0;
 301 }
 302
 303 .comment {
 304   background: yellow;
 305 }
 306
 307 .footnote, .footnoteref {
 308   font-size: 0.8em;
 309 }
 310
 311 span.footnote, span.footnoteref {
 312   vertical-align: super;
 313 }
 314
 315 #footnotes {
 316   margin: 20px 0 20px 0;
 317   padding: 7px 0 0 0;
 318 }
 319
 320 #footnotes div.footnote {
 321   margin: 0 0 5px 0;
 322 }
 323
 324 #footnotes hr {
 325   border: none;
 326   border-top: 1px solid silver;
 327   height: 1px;
 328   text-align: left;
 329   margin-left: 0;
 330   width: 20%;
 331   min-width: 100px;
 332 }
 333
 334 div.colist td {
 335   padding-right: 0.5em;
 336   padding-bottom: 0.3em;
 337   vertical-align: top;
 338 }
 339 div.colist td img {
 340   margin-top: 0.3em;
 341 }
 342
 343 @media print {
 344   #footer-badges { display: none; }
 345 }
 346
 347 #toc {
 348   margin-bottom: 2.5em;
 349 }
 350
 351 #toctitle {
 352   color: #527bbd;
 353   font-size: 1.1em;
 354   font-weight: bold;
 355   margin-top: 1.0em;
 356   margin-bottom: 0.1em;
 357 }
 358
 359 div.toclevel0, div.toclevel1, div.toclevel2, div.toclevel3, div.toclevel4 {
 360   margin-top: 0;
 361   margin-bottom: 0;
 362 }
 363 div.toclevel2 {
 364   margin-left: 2em;
 365   font-size: 0.9em;
 366 }
 367 div.toclevel3 {
 368   margin-left: 4em;
 369   font-size: 0.9em;
 370 }
 371 div.toclevel4 {
 372   margin-left: 6em;
 373   font-size: 0.9em;
 374 }
 375
 376 span.aqua { color: aqua; }
 377 span.black { color: black; }
 378 span.blue { color: blue; }
 379 span.fuchsia { color: fuchsia; }
 380 span.gray { color: gray; }
 381 span.green { color: green; }
 382 span.lime { color: lime; }
 383 span.maroon { color: maroon; }
 384 span.navy { color: navy; }
 385 span.olive { color: olive; }
 386 span.purple { color: purple; }
 387 span.red { color: red; }
 388 span.silver { color: silver; }
 389 span.teal { color: teal; }
 390 span.white { color: white; }
 391 span.yellow { color: yellow; }
 392
 393 span.aqua-background { background: aqua; }
 394 span.black-background { background: black; }
 395 span.blue-background { background: blue; }
 396 span.fuchsia-background { background: fuchsia; }
 397 span.gray-background { background: gray; }
 398 span.green-background { background: green; }
 399 span.lime-background { background: lime; }
 400 span.maroon-background { background: maroon; }
 401 span.navy-background { background: navy; }
 402 span.olive-background { background: olive; }
 403 span.purple-background { background: purple; }
 404 span.red-background { background: red; }
 405 span.silver-background { background: silver; }
 406 span.teal-background { background: teal; }
 407 span.white-background { background: white; }
 408 span.yellow-background { background: yellow; }
 409
 410 span.big { font-size: 2em; }
 411 span.small { font-size: 0.6em; }
 412
 413 span.underline { text-decoration: underline; }
 414 span.overline { text-decoration: overline; }
 415 span.line-through { text-decoration: line-through; }
 416
 417 div.unbreakable { page-break-inside: avoid; }
 418
 419
 420 /*
 421  * xhtml11 specific
 422  *
 423  * */
 424
 425 div.tableblock {
 426   margin-top: 1.0em;
 427   margin-bottom: 1.5em;
 428 }
 429 div.tableblock > table {
 430   border: 3px solid #527bbd;
 431 }
 432 thead, p.table.header {
 433   font-weight: bold;
 434   color: #527bbd;
 435 }
 436 p.table {
 437   margin-top: 0;
 438 }
 439 /* Because the table frame attribute is overridden by CSS in most browsers. */
 440 div.tableblock > table[frame="void"] {
 441   border-style: none;
 442 }
 443 div.tableblock > table[frame="hsides"] {
 444   border-left-style: none;
 445   border-right-style: none;
 446 }
 447 div.tableblock > table[frame="vsides"] {
 448   border-top-style: none;
 449   border-bottom-style: none;
 450 }
 451
 452
 453 /*
 454  * html5 specific
 455  *
 456  * */
 457
 458 table.tableblock {
 459   margin-top: 1.0em;
 460   margin-bottom: 1.5em;
 461 }
 462 thead, p.tableblock.header {
 463   font-weight: bold;
 464   color: #527bbd;
 465 }
 466 p.tableblock {
 467   margin-top: 0;
 468 }
 469 table.tableblock {
 470   border-width: 3px;
 471   border-spacing: 0px;
 472   border-style: solid;
 473   border-color: #527bbd;
 474   border-collapse: collapse;
 475 }
 476 th.tableblock, td.tableblock {
 477   border-width: 1px;
 478   padding: 4px;
 479   border-style: solid;
 480   border-color: #527bbd;
 481 }
 482
 483 table.tableblock.frame-topbot {
 484   border-left-style: hidden;
 485   border-right-style: hidden;
 486 }
 487 table.tableblock.frame-sides {
 488   border-top-style: hidden;
 489   border-bottom-style: hidden;
 490 }
 491 table.tableblock.frame-none {
 492   border-style: hidden;
 493 }
 494
 495 th.tableblock.halign-left, td.tableblock.halign-left {
 496   text-align: left;
 497 }
 498 th.tableblock.halign-center, td.tableblock.halign-center {
 499   text-align: center;
 500 }
 501 th.tableblock.halign-right, td.tableblock.halign-right {
 502   text-align: right;
 503 }
 504
 505 th.tableblock.valign-top, td.tableblock.valign-top {
 506   vertical-align: top;
 507 }
 508 th.tableblock.valign-middle, td.tableblock.valign-middle {
 509   vertical-align: middle;
 510 }
 511 th.tableblock.valign-bottom, td.tableblock.valign-bottom {
 512   vertical-align: bottom;
 513 }
 514
 515
 516 /*
 517  * manpage specific
 518  *
 519  * */
 520
 521 body.manpage h1 {
 522   padding-top: 0.5em;
 523   padding-bottom: 0.5em;
 524   border-top: 2px solid silver;
 525   border-bottom: 2px solid silver;
 526 }
 527 body.manpage h2 {
 528   border-style: none;
 529 }
 530 body.manpage div.sectionbody {
 531   margin-left: 3em;
 532 }
 533
 534 @media print {
 535   body.manpage div#toc { display: none; }
 536 }
 537
 538
 539 </style>
 540 <script type="text/javascript">
 541 /*<![CDATA[*/
 542 var asciidoc = {  // Namespace.
 543
 544 /////////////////////////////////////////////////////////////////////
 545 // Table Of Contents generator
 546 /////////////////////////////////////////////////////////////////////
 547
 548 /* Author: Mihai Bazon, September 2002
 549  * http://students.infoiasi.ro/~mishoo
 550  *
 551  * Table Of Content generator
 552  * Version: 0.4
 553  *
 554  * Feel free to use this script under the terms of the GNU General Public
 555  * License, as long as you do not remove or alter this notice.
 556  */
 557
 558  /* modified by Troy D. Hanson, September 2006. License: GPL */
 559  /* modified by Stuart Rackham, 2006, 2009. License: GPL */
 560
 561 // toclevels = 1..4.
 562 toc: function (toclevels) {
 563
 564   function getText(el) {
 565     var text = "";
 566     for (var i = el.firstChild; i != null; i = i.nextSibling) {
 567       if (i.nodeType == 3 /* Node.TEXT_NODE */) // IE doesn't speak constants.
 568         text += i.data;
 569       else if (i.firstChild != null)
 570         text += getText(i);
 571     }
 572     return text;
 573   }
 574
 575   function TocEntry(el, text, toclevel) {
 576     this.element = el;
 577     this.text = text;
 578     this.toclevel = toclevel;
 579   }
 580
 581   function tocEntries(el, toclevels) {
 582     var result = new Array;
 583     var re = new RegExp('[hH]([1-'+(toclevels+1)+'])');
 584     // Function that scans the DOM tree for header elements (the DOM2
 585     // nodeIterator API would be a better technique but not supported by all
 586     // browsers).
 587     var iterate = function (el) {
 588       for (var i = el.firstChild; i != null; i = i.nextSibling) {
 589         if (i.nodeType == 1 /* Node.ELEMENT_NODE */) {
 590           var mo = re.exec(i.tagName);
 591           if (mo && (i.getAttribute("class") || i.getAttribute("className")) != "float") {
 592             result[result.length] = new TocEntry(i, getText(i), mo[1]-1);
 593           }
 594           iterate(i);
 595         }
 596       }
 597     }
 598     iterate(el);
 599     return result;
 600   }
 601
 602   var toc = document.getElementById("toc");
 603   if (!toc) {
 604     return;
 605   }
 606
 607   // Delete existing TOC entries in case we're reloading the TOC.
 608   var tocEntriesToRemove = [];
 609   var i;
 610   for (i = 0; i < toc.childNodes.length; i++) {
 611     var entry = toc.childNodes[i];
 612     if (entry.nodeName.toLowerCase() == 'div'
 613      && entry.getAttribute("class")
 614      && entry.getAttribute("class").match(/^toclevel/))
 615       tocEntriesToRemove.push(entry);
 616   }
 617   for (i = 0; i < tocEntriesToRemove.length; i++) {
 618     toc.removeChild(tocEntriesToRemove[i]);
 619   }
 620
 621   // Rebuild TOC entries.
 622   var entries = tocEntries(document.getElementById("content"), toclevels);
 623   for (var i = 0; i < entries.length; ++i) {
 624     var entry = entries[i];
 625     if (entry.element.id == "")
 626       entry.element.id = "_toc_" + i;
 627     var a = document.createElement("a");
 628     a.href = "#" + entry.element.id;
 629     a.appendChild(document.createTextNode(entry.text));
 630     var div = document.createElement("div");
 631     div.appendChild(a);
 632     div.className = "toclevel" + entry.toclevel;
 633     toc.appendChild(div);
 634   }
 635   if (entries.length == 0)
 636     toc.parentNode.removeChild(toc);
 637 },
 638
 639
 640 /////////////////////////////////////////////////////////////////////
 641 // Footnotes generator
 642 /////////////////////////////////////////////////////////////////////
 643
 644 /* Based on footnote generation code from:
 645  * http://www.brandspankingnew.net/archive/2005/07/format_footnote.html
 646  */
 647
 648 footnotes: function () {
 649   // Delete existing footnote entries in case we're reloading the footnodes.
 650   var i;
 651   var noteholder = document.getElementById("footnotes");
 652   if (!noteholder) {
 653     return;
 654   }
 655   var entriesToRemove = [];
 656   for (i = 0; i < noteholder.childNodes.length; i++) {
 657     var entry = noteholder.childNodes[i];
 658     if (entry.nodeName.toLowerCase() == 'div' && entry.getAttribute("class") == "footnote")
 659       entriesToRemove.push(entry);
 660   }
 661   for (i = 0; i < entriesToRemove.length; i++) {
 662     noteholder.removeChild(entriesToRemove[i]);
 663   }
 664
 665   // Rebuild footnote entries.
 666   var cont = document.getElementById("content");
 667   var spans = cont.getElementsByTagName("span");
 668   var refs = {};
 669   var n = 0;
 670   for (i=0; i<spans.length; i++) {
 671     if (spans[i].className == "footnote") {
 672       n++;
 673       var note = spans[i].getAttribute("data-note");
 674       if (!note) {
 675         // Use [\s\S] in place of . so multi-line matches work.
 676         // Because JavaScript has no s (dotall) regex flag.
 677         note = spans[i].innerHTML.match(/\s*\[([\s\S]*)]\s*/)[1];
 678         spans[i].innerHTML =
 679           "[<a id='_footnoteref_" + n + "' href='#_footnote_" + n +
 680           "' title='View footnote' class='footnote'>" + n + "</a>]";
 681         spans[i].setAttribute("data-note", note);
 682       }
 683       noteholder.innerHTML +=
 684         "<div class='footnote' id='_footnote_" + n + "'>" +
 685         "<a href='#_footnoteref_" + n + "' title='Return to text'>" +
 686         n + "</a>. " + note + "</div>";
 687       var id =spans[i].getAttribute("id");
 688       if (id != null) refs["#"+id] = n;
 689     }
 690   }
 691   if (n == 0)
 692     noteholder.parentNode.removeChild(noteholder);
 693   else {
 694     // Process footnoterefs.
 695     for (i=0; i<spans.length; i++) {
 696       if (spans[i].className == "footnoteref") {
 697         var href = spans[i].getElementsByTagName("a")[0].getAttribute("href");
 698         href = href.match(/#.*/)[0];  // Because IE return full URL.
 699         n = refs[href];
 700         spans[i].innerHTML =
 701           "[<a href='#_footnote_" + n +
 702           "' title='View footnote' class='footnote'>" + n + "</a>]";
 703       }
 704     }
 705   }
 706 },
 707
 708 install: function(toclevels) {
 709   var timerId;
 710
 711   function reinstall() {
 712     asciidoc.footnotes();
 713     if (toclevels) {
 714       asciidoc.toc(toclevels);
 715     }
 716   }
 717
 718   function reinstallAndRemoveTimer() {
 719     clearInterval(timerId);
 720     reinstall();
 721   }
 722
 723   timerId = setInterval(reinstall, 500);
 724   if (document.addEventListener)
 725     document.addEventListener("DOMContentLoaded", reinstallAndRemoveTimer, false);
 726   else
 727     window.onload = reinstallAndRemoveTimer;
 728 }
 729
 730 }
 731 asciidoc.install();
 732 /*]]>*/
 733 </script>
 734 </head>
 735 <body class="article">
 736 <div id="header">
 737 <h1>My First Object Walk</h1>
 738 <span id="revdate">2024-02-02</span>
 739 </div>
 740 <div id="content">
 741 <div class="sect1">
 742 <h2 id="_what_8217_s_an_object_walk">What&#8217;s an Object Walk?</h2>
 743 <div class="sectionbody">
 744 <div class="paragraph"><p>The object walk is a key concept in Git - this is the process that underpins
 745 operations like object transfer and fsck. Beginning from a given commit, the
 746 list of objects is found by walking parent relationships between commits (commit
 747 X based on commit W) and containment relationships between objects (tree Y is
 748 contained within commit X, and blob Z is located within tree Y, giving our
 749 working tree for commit X something like <code>y/z.txt</code>).</p></div>
 750 <div class="paragraph"><p>A related concept is the revision walk, which is focused on commit objects and
 751 their parent relationships and does not delve into other object types. The
 752 revision walk is used for operations like <code>git log</code>.</p></div>
 753 <div class="sect2">
 754 <h3 id="_related_reading">Related Reading</h3>
 755 <div class="ulist"><ul>
 756 <li>
 757 <p>
 758 <code>Documentation/user-manual.txt</code> under "Hacking Git" contains some coverage of
 759   the revision walker in its various incarnations.
 760 </p>
 761 </li>
 762 <li>
 763 <p>
 764 <code>revision.h</code>
 765 </p>
 766 </li>
 767 <li>
 768 <p>
 769 <a href="https://eagain.net/articles/git-for-computer-scientists/">Git for Computer Scientists</a>
 770   gives a good overview of the types of objects in Git and what your object
 771   walk is really describing.
 772 </p>
 773 </li>
 774 </ul></div>
 775 </div>
 776 </div>
 777 </div>
 778 <div class="sect1">
 779 <h2 id="_setting_up">Setting Up</h2>
 780 <div class="sectionbody">
 781 <div class="paragraph"><p>Create a new branch from <code>master</code>.</p></div>
 782 <div class="listingblock">
 783 <div class="content">
 784 <pre><code>git checkout -b revwalk origin/master</code></pre>
 785 </div></div>
 786 <div class="paragraph"><p>We&#8217;ll put our fiddling into a new command. For fun, let&#8217;s name it <code>git walken</code>.
 787 Open up a new file <code>builtin/walken.c</code> and set up the command handler:</p></div>
 788 <div class="listingblock">
 789 <div class="content">
 790 <pre><code>/*
 791  * "git walken"
 792  *
 793  * Part of the "My First Object Walk" tutorial.
 794  */
 795
 796 #include "builtin.h"
 797 #include "trace.h"
 798
 799 int cmd_walken(int argc, const char **argv, const char *prefix)
 800 {
 801         trace_printf(_("cmd_walken incoming...\n"));
 802         return 0;
 803 }</code></pre>
 804 </div></div>
 805 <div class="admonitionblock">
 806 <table><tr>
 807 <td class="icon">
 808 <div class="title">Note</div>
 809 </td>
 810 <td class="content"><code>trace_printf()</code>, defined in <code>trace.h</code>, differs from <code>printf()</code> in
 811 that it can be turned on or off at runtime. For the purposes of this
 812 tutorial, we will write <code>walken</code> as though it is intended for use as
 813 a "plumbing" command: that is, a command which is used primarily in
 814 scripts, rather than interactively by humans (a "porcelain" command).
 815 So we will send our debug output to <code>trace_printf()</code> instead.
 816 When running, enable trace output by setting the environment variable <code>GIT_TRACE</code>.</td>
 817 </tr></table>
 818 </div>
 819 <div class="paragraph"><p>Add usage text and <code>-h</code> handling, like all subcommands should consistently do
 820 (our test suite will notice and complain if you fail to do so).
 821 We&#8217;ll need to include the <code>parse-options.h</code> header.</p></div>
 822 <div class="listingblock">
 823 <div class="content">
 824 <pre><code>#include "parse-options.h"
 825
 826 ...
 827
 828 int cmd_walken(int argc, const char **argv, const char *prefix)
 829 {
 830         const char * const walken_usage[] = {
 831                 N_("git walken"),
 832                 NULL,
 833         };
 834         struct option options[] = {
 835                 OPT_END()
 836         };
 837
 838         argc = parse_options(argc, argv, prefix, options, walken_usage, 0);
 839
 840         ...
 841 }</code></pre>
 842 </div></div>
 843 <div class="paragraph"><p>Also add the relevant line in <code>builtin.h</code> near <code>cmd_whatchanged()</code>:</p></div>
 844 <div class="listingblock">
 845 <div class="content">
 846 <pre><code>int cmd_walken(int argc, const char **argv, const char *prefix);</code></pre>
 847 </div></div>
 848 <div class="paragraph"><p>Include the command in <code>git.c</code> in <code>commands[]</code> near the entry for <code>whatchanged</code>,
 849 maintaining alphabetical ordering:</p></div>
 850 <div class="listingblock">
 851 <div class="content">
 852 <pre><code>{ "walken", cmd_walken, RUN_SETUP },</code></pre>
 853 </div></div>
 854 <div class="paragraph"><p>Add it to the <code>Makefile</code> near the line for <code>builtin/worktree.o</code>:</p></div>
 855 <div class="listingblock">
 856 <div class="content">
 857 <pre><code>BUILTIN_OBJS += builtin/walken.o</code></pre>
 858 </div></div>
 859 <div class="paragraph"><p>Build and test out your command, without forgetting to ensure the <code>DEVELOPER</code>
 860 flag is set, and with <code>GIT_TRACE</code> enabled so the debug output can be seen:</p></div>
 861 <div class="listingblock">
 862 <div class="content">
 863 <pre><code>$ echo DEVELOPER=1 &gt;&gt;config.mak
 864 $ make
 865 $ GIT_TRACE=1 ./bin-wrappers/git walken</code></pre>
 866 </div></div>
 867 <div class="admonitionblock">
 868 <table><tr>
 869 <td class="icon">
 870 <div class="title">Note</div>
 871 </td>
 872 <td class="content">For a more exhaustive overview of the new command process, take a look at
 873 <code>Documentation/MyFirstContribution.txt</code>.</td>
 874 </tr></table>
 875 </div>
 876 <div class="admonitionblock">
 877 <table><tr>
 878 <td class="icon">
 879 <div class="title">Note</div>
 880 </td>
 881 <td class="content">A reference implementation can be found at
 882 <a href="https://github.com/nasamuffin/git/tree/revwalk">https://github.com/nasamuffin/git/tree/revwalk</a>.</td>
 883 </tr></table>
 884 </div>
 885 <div class="sect2">
 886 <h3 id="_code_struct_rev_cmdline_info_code"><code>struct rev_cmdline_info</code></h3>
 887 <div class="paragraph"><p>The definition of <code>struct rev_cmdline_info</code> can be found in <code>revision.h</code>.</p></div>
 888 <div class="paragraph"><p>This struct is contained within the <code>rev_info</code> struct and is used to reflect
 889 parameters provided by the user over the CLI.</p></div>
 890 <div class="paragraph"><p><code>nr</code> represents the number of <code>rev_cmdline_entry</code> present in the array.</p></div>
 891 <div class="paragraph"><p><code>alloc</code> is used by the <code>ALLOC_GROW</code> macro. Check <code>alloc.h</code> - this variable is
 892 used to track the allocated size of the list.</p></div>
 893 <div class="paragraph"><p>Per entry, we find:</p></div>
 894 <div class="paragraph"><p><code>item</code> is the object provided upon which to base the object walk. Items in Git
 895 can be blobs, trees, commits, or tags. (See <code>Documentation/gittutorial-2.txt</code>.)</p></div>
 896 <div class="paragraph"><p><code>name</code> is the object ID (OID) of the object - a hex string you may be familiar
 897 with from using Git to organize your source in the past. Check the tutorial
 898 mentioned above towards the top for a discussion of where the OID can come
 899 from.</p></div>
 900 <div class="paragraph"><p><code>whence</code> indicates some information about what to do with the parents of the
 901 specified object. We&#8217;ll explore this flag more later on; take a look at
 902 <code>Documentation/revisions.txt</code> to get an idea of what could set the <code>whence</code>
 903 value.</p></div>
 904 <div class="paragraph"><p><code>flags</code> are used to hint the beginning of the revision walk and are the first
 905 block under the <code>#include`s in `revision.h</code>. The most likely ones to be set in
 906 the <code>rev_cmdline_info</code> are <code>UNINTERESTING</code> and <code>BOTTOM</code>, but these same flags
 907 can be used during the walk, as well.</p></div>
 908 </div>
 909 <div class="sect2">
 910 <h3 id="_code_struct_rev_info_code"><code>struct rev_info</code></h3>
 911 <div class="paragraph"><p>This one is quite a bit longer, and many fields are only used during the walk
 912 by <code>revision.c</code> - not configuration options. Most of the configurable flags in
 913 <code>struct rev_info</code> have a mirror in <code>Documentation/rev-list-options.txt</code>. It&#8217;s a
 914 good idea to take some time and read through that document.</p></div>
 915 </div>
 916 </div>
 917 </div>
 918 <div class="sect1">
 919 <h2 id="_basic_commit_walk">Basic Commit Walk</h2>
 920 <div class="sectionbody">
 921 <div class="paragraph"><p>First, let&#8217;s see if we can replicate the output of <code>git log --oneline</code>. We&#8217;ll
 922 refer back to the implementation frequently to discover norms when performing
 923 an object walk of our own.</p></div>
 924 <div class="paragraph"><p>To do so, we&#8217;ll first find all the commits, in order, which preceded the current
 925 commit. We&#8217;ll extract the name and subject of the commit from each.</p></div>
 926 <div class="paragraph"><p>Ideally, we will also be able to find out which ones are currently at the tip of
 927 various branches.</p></div>
 928 <div class="sect2">
 929 <h3 id="_setting_up_2">Setting Up</h3>
 930 <div class="paragraph"><p>Preparing for your object walk has some distinct stages.</p></div>
 931 <div class="olist arabic"><ol class="arabic">
 932 <li>
 933 <p>
 934 Perform default setup for this mode, and others which may be invoked.
 935 </p>
 936 </li>
 937 <li>
 938 <p>
 939 Check configuration files for relevant settings.
 940 </p>
 941 </li>
 942 <li>
 943 <p>
 944 Set up the <code>rev_info</code> struct.
 945 </p>
 946 </li>
 947 <li>
 948 <p>
 949 Tweak the initialized <code>rev_info</code> to suit the current walk.
 950 </p>
 951 </li>
 952 <li>
 953 <p>
 954 Prepare the <code>rev_info</code> for the walk.
 955 </p>
 956 </li>
 957 <li>
 958 <p>
 959 Iterate over the objects, processing each one.
 960 </p>
 961 </li>
 962 </ol></div>
 963 <div class="sect3">
 964 <h4 id="_default_setups">Default Setups</h4>
 965 <div class="paragraph"><p>Before examining configuration files which may modify command behavior, set up
 966 default state for switches or options your command may have. If your command
 967 utilizes other Git components, ask them to set up their default states as well.
 968 For instance, <code>git log</code> takes advantage of <code>grep</code> and <code>diff</code> functionality, so
 969 its <code>init_log_defaults()</code> sets its own state (<code>decoration_style</code>) and asks
 970 <code>grep</code> and <code>diff</code> to initialize themselves by calling each of their
 971 initialization functions.</p></div>
 972 </div>
 973 <div class="sect3">
 974 <h4 id="_configuring_from_code_gitconfig_code">Configuring From <code>.gitconfig</code></h4>
 975 <div class="paragraph"><p>Next, we should have a look at any relevant configuration settings (i.e.,
 976 settings readable and settable from <code>git config</code>). This is done by providing a
 977 callback to <code>git_config()</code>; within that callback, you can also invoke methods
 978 from other components you may need that need to intercept these options. Your
 979 callback will be invoked once per each configuration value which Git knows about
 980 (global, local, worktree, etc.).</p></div>
 981 <div class="paragraph"><p>Similarly to the default values, we don&#8217;t have anything to do here yet
 982 ourselves; however, we should call <code>git_default_config()</code> if we aren&#8217;t calling
 983 any other existing config callbacks.</p></div>
 984 <div class="paragraph"><p>Add a new function to <code>builtin/walken.c</code>.
 985 We&#8217;ll also need to include the <code>config.h</code> header:</p></div>
 986 <div class="listingblock">
 987 <div class="content">
 988 <pre><code>#include "config.h"
 989
 990 ...
 991
 992 static int git_walken_config(const char *var, const char *value, void *cb)
 993 {
 994         /*
 995          * For now, we don't have any custom configuration, so fall back to
 996          * the default config.
 997          */
 998         return git_default_config(var, value, cb);
 999 }</code></pre>
1000 </div></div>
1001 <div class="paragraph"><p>Make sure to invoke <code>git_config()</code> with it in your <code>cmd_walken()</code>:</p></div>
1002 <div class="listingblock">
1003 <div class="content">
1004 <pre><code>int cmd_walken(int argc, const char **argv, const char *prefix)
1005 {
1006         ...
1007
1008         git_config(git_walken_config, NULL);
1009
1010         ...
1011 }</code></pre>
1012 </div></div>
1013 </div>
1014 <div class="sect3">
1015 <h4 id="_setting_up_code_rev_info_code">Setting Up <code>rev_info</code></h4>
1016 <div class="paragraph"><p>Now that we&#8217;ve gathered external configuration and options, it&#8217;s time to
1017 initialize the <code>rev_info</code> object which we will use to perform the walk. This is
1018 typically done by calling <code>repo_init_revisions()</code> with the repository you intend
1019 to target, as well as the <code>prefix</code> argument of <code>cmd_walken</code> and your <code>rev_info</code>
1020 struct.</p></div>
1021 <div class="paragraph"><p>Add the <code>struct rev_info</code> and the <code>repo_init_revisions()</code> call.
1022 We&#8217;ll also need to include the <code>revision.h</code> header:</p></div>
1023 <div class="listingblock">
1024 <div class="content">
1025 <pre><code>#include "revision.h"
1026
1027 ...
1028
1029 int cmd_walken(int argc, const char **argv, const char *prefix)
1030 {
1031         /* This can go wherever you like in your declarations.*/
1032         struct rev_info rev;
1033         ...
1034
1035         /* This should go after the git_config() call. */
1036         repo_init_revisions(the_repository, &amp;rev, prefix);
1037
1038         ...
1039 }</code></pre>
1040 </div></div>
1041 </div>
1042 <div class="sect3">
1043 <h4 id="_tweaking_code_rev_info_code_for_the_walk">Tweaking <code>rev_info</code> For the Walk</h4>
1044 <div class="paragraph"><p>We&#8217;re getting close, but we&#8217;re still not quite ready to go. Now that <code>rev</code> is
1045 initialized, we can modify it to fit our needs. This is usually done within a
1046 helper for clarity, so let&#8217;s add one:</p></div>
1047 <div class="listingblock">
1048 <div class="content">
1049 <pre><code>static void final_rev_info_setup(struct rev_info *rev)
1050 {
1051         /*
1052          * We want to mimic the appearance of `git log --oneline`, so let's
1053          * force oneline format.
1054          */
1055         get_commit_format("oneline", rev);
1056
1057         /* Start our object walk at HEAD. */
1058         add_head_to_pending(rev);
1059 }</code></pre>
1060 </div></div>
1061 <div class="admonitionblock">
1062 <table><tr>
1063 <td class="icon">
1064 <div class="title">Note</div>
1065 </td>
1066 <td class="content">
1067 <div class="paragraph"><p>Instead of using the shorthand <code>add_head_to_pending()</code>, you could do
1068 something like this:</p></div>
1069 <div class="listingblock">
1070 <div class="content">
1071 <pre><code>        struct setup_revision_opt opt;
1072
1073         memset(&amp;opt, 0, sizeof(opt));
1074         opt.def = "HEAD";
1075         opt.revarg_opt = REVARG_COMMITTISH;
1076         setup_revisions(argc, argv, rev, &amp;opt);</code></pre>
1077 </div></div>
1078 <div class="paragraph"><p>Using a <code>setup_revision_opt</code> gives you finer control over your walk&#8217;s starting
1079 point.</p></div>
1080 </td>
1081 </tr></table>
1082 </div>
1083 <div class="paragraph"><p>Then let&#8217;s invoke <code>final_rev_info_setup()</code> after the call to
1084 <code>repo_init_revisions()</code>:</p></div>
1085 <div class="listingblock">
1086 <div class="content">
1087 <pre><code>int cmd_walken(int argc, const char **argv, const char *prefix)
1088 {
1089         ...
1090
1091         final_rev_info_setup(&amp;rev);
1092
1093         ...
1094 }</code></pre>
1095 </div></div>
1096 <div class="paragraph"><p>Later, we may wish to add more arguments to <code>final_rev_info_setup()</code>. But for
1097 now, this is all we need.</p></div>
1098 </div>
1099 <div class="sect3">
1100 <h4 id="_preparing_code_rev_info_code_for_the_walk">Preparing <code>rev_info</code> For the Walk</h4>
1101 <div class="paragraph"><p>Now that <code>rev</code> is all initialized and configured, we&#8217;ve got one more setup step
1102 before we get rolling. We can do this in a helper, which will both prepare the
1103 <code>rev_info</code> for the walk, and perform the walk itself. Let&#8217;s start the helper
1104 with the call to <code>prepare_revision_walk()</code>, which can return an error without
1105 dying on its own:</p></div>
1106 <div class="listingblock">
1107 <div class="content">
1108 <pre><code>static void walken_commit_walk(struct rev_info *rev)
1109 {
1110         if (prepare_revision_walk(rev))
1111                 die(_("revision walk setup failed"));
1112 }</code></pre>
1113 </div></div>
1114 <div class="admonitionblock">
1115 <table><tr>
1116 <td class="icon">
1117 <div class="title">Note</div>
1118 </td>
1119 <td class="content"><code>die()</code> prints to <code>stderr</code> and exits the program. Since it will print to
1120 <code>stderr</code> it&#8217;s likely to be seen by a human, so we will localize it.</td>
1121 </tr></table>
1122 </div>
1123 </div>
1124 <div class="sect3">
1125 <h4 id="_performing_the_walk">Performing the Walk!</h4>
1126 <div class="paragraph"><p>Finally! We are ready to begin the walk itself. Now we can see that <code>rev_info</code>
1127 can also be used as an iterator; we move to the next item in the walk by using
1128 <code>get_revision()</code> repeatedly. Add the listed variable declarations at the top and
1129 the walk loop below the <code>prepare_revision_walk()</code> call within your
1130 <code>walken_commit_walk()</code>:</p></div>
1131 <div class="listingblock">
1132 <div class="content">
1133 <pre><code>#include "pretty.h"
1134
1135 ...
1136
1137 static void walken_commit_walk(struct rev_info *rev)
1138 {
1139         struct commit *commit;
1140         struct strbuf prettybuf = STRBUF_INIT;
1141
1142         ...
1143
1144         while ((commit = get_revision(rev))) {
1145                 strbuf_reset(&amp;prettybuf);
1146                 pp_commit_easy(CMIT_FMT_ONELINE, commit, &amp;prettybuf);
1147                 puts(prettybuf.buf);
1148         }
1149         strbuf_release(&amp;prettybuf);
1150 }</code></pre>
1151 </div></div>
1152 <div class="admonitionblock">
1153 <table><tr>
1154 <td class="icon">
1155 <div class="title">Note</div>
1156 </td>
1157 <td class="content"><code>puts()</code> prints a <code>char*</code> to <code>stdout</code>. Since this is the part of the
1158 command we expect to be machine-parsed, we&#8217;re sending it directly to stdout.</td>
1159 </tr></table>
1160 </div>
1161 <div class="paragraph"><p>Give it a shot.</p></div>
1162 <div class="listingblock">
1163 <div class="content">
1164 <pre><code>$ make
1165 $ ./bin-wrappers/git walken</code></pre>
1166 </div></div>
1167 <div class="paragraph"><p>You should see all of the subject lines of all the commits in
1168 your tree&#8217;s history, in order, ending with the initial commit, "Initial revision
1169 of "git", the information manager from hell". Congratulations! You&#8217;ve written
1170 your first revision walk. You can play with printing some additional fields
1171 from each commit if you&#8217;re curious; have a look at the functions available in
1172 <code>commit.h</code>.</p></div>
1173 </div>
1174 </div>
1175 <div class="sect2">
1176 <h3 id="_adding_a_filter">Adding a Filter</h3>
1177 <div class="paragraph"><p>Next, let&#8217;s try to filter the commits we see based on their author. This is
1178 equivalent to running <code>git log --author=&lt;pattern&gt;</code>. We can add a filter by
1179 modifying <code>rev_info.grep_filter</code>, which is a <code>struct grep_opt</code>.</p></div>
1180 <div class="paragraph"><p>First some setup. Add <code>grep_config()</code> to <code>git_walken_config()</code>:</p></div>
1181 <div class="listingblock">
1182 <div class="content">
1183 <pre><code>static int git_walken_config(const char *var, const char *value, void *cb)
1184 {
1185         grep_config(var, value, cb);
1186         return git_default_config(var, value, cb);
1187 }</code></pre>
1188 </div></div>
1189 <div class="paragraph"><p>Next, we can modify the <code>grep_filter</code>. This is done with convenience functions
1190 found in <code>grep.h</code>. For fun, we&#8217;re filtering to only commits from folks using a
1191 <code>gmail.com</code> email address - a not-very-precise guess at who may be working on
1192 Git as a hobby. Since we&#8217;re checking the author, which is a specific line in the
1193 header, we&#8217;ll use the <code>append_header_grep_pattern()</code> helper. We can use
1194 the <code>enum grep_header_field</code> to indicate which part of the commit header we want
1195 to search.</p></div>
1196 <div class="paragraph"><p>In <code>final_rev_info_setup()</code>, add your filter line:</p></div>
1197 <div class="listingblock">
1198 <div class="content">
1199 <pre><code>static void final_rev_info_setup(int argc, const char **argv,
1200                 const char *prefix, struct rev_info *rev)
1201 {
1202         ...
1203
1204         append_header_grep_pattern(&amp;rev-&gt;grep_filter, GREP_HEADER_AUTHOR,
1205                 "gmail");
1206         compile_grep_patterns(&amp;rev-&gt;grep_filter);
1207
1208         ...
1209 }</code></pre>
1210 </div></div>
1211 <div class="paragraph"><p><code>append_header_grep_pattern()</code> adds your new "gmail" pattern to <code>rev_info</code>, but
1212 it won&#8217;t work unless we compile it with <code>compile_grep_patterns()</code>.</p></div>
1213 <div class="admonitionblock">
1214 <table><tr>
1215 <td class="icon">
1216 <div class="title">Note</div>
1217 </td>
1218 <td class="content">If you are using <code>setup_revisions()</code> (for example, if you are passing a
1219 <code>setup_revision_opt</code> instead of using <code>add_head_to_pending()</code>), you don&#8217;t need
1220 to call <code>compile_grep_patterns()</code> because <code>setup_revisions()</code> calls it for you.</td>
1221 </tr></table>
1222 </div>
1223 <div class="admonitionblock">
1224 <table><tr>
1225 <td class="icon">
1226 <div class="title">Note</div>
1227 </td>
1228 <td class="content">We could add the same filter via the <code>append_grep_pattern()</code> helper if we
1229 wanted to, but <code>append_header_grep_pattern()</code> adds the <code>enum grep_context</code> and
1230 <code>enum grep_pat_token</code> for us.</td>
1231 </tr></table>
1232 </div>
1233 </div>
1234 <div class="sect2">
1235 <h3 id="_changing_the_order">Changing the Order</h3>
1236 <div class="paragraph"><p>There are a few ways that we can change the order of the commits during a
1237 revision walk. Firstly, we can use the <code>enum rev_sort_order</code> to choose from some
1238 typical orderings.</p></div>
1239 <div class="paragraph"><p><code>topo_order</code> is the same as <code>git log --topo-order</code>: we avoid showing a parent
1240 before all of its children have been shown, and we avoid mixing commits which
1241 are in different lines of history. (<code>git help log</code>'s section on <code>--topo-order</code>
1242 has a very nice diagram to illustrate this.)</p></div>
1243 <div class="paragraph"><p>Let&#8217;s see what happens when we run with <code>REV_SORT_BY_COMMIT_DATE</code> as opposed to
1244 <code>REV_SORT_BY_AUTHOR_DATE</code>. Add the following:</p></div>
1245 <div class="listingblock">
1246 <div class="content">
1247 <pre><code>static void final_rev_info_setup(int argc, const char **argv,
1248                 const char *prefix, struct rev_info *rev)
1249 {
1250         ...
1251
1252         rev-&gt;topo_order = 1;
1253         rev-&gt;sort_order = REV_SORT_BY_COMMIT_DATE;
1254
1255         ...
1256 }</code></pre>
1257 </div></div>
1258 <div class="paragraph"><p>Let&#8217;s output this into a file so we can easily diff it with the walk sorted by
1259 author date.</p></div>
1260 <div class="listingblock">
1261 <div class="content">
1262 <pre><code>$ make
1263 $ ./bin-wrappers/git walken &gt; commit-date.txt</code></pre>
1264 </div></div>
1265 <div class="paragraph"><p>Then, let&#8217;s sort by author date and run it again.</p></div>
1266 <div class="listingblock">
1267 <div class="content">
1268 <pre><code>static void final_rev_info_setup(int argc, const char **argv,
1269                 const char *prefix, struct rev_info *rev)
1270 {
1271         ...
1272
1273         rev-&gt;topo_order = 1;
1274         rev-&gt;sort_order = REV_SORT_BY_AUTHOR_DATE;
1275
1276         ...
1277 }</code></pre>
1278 </div></div>
1279 <div class="listingblock">
1280 <div class="content">
1281 <pre><code>$ make
1282 $ ./bin-wrappers/git walken &gt; author-date.txt</code></pre>
1283 </div></div>
1284 <div class="paragraph"><p>Finally, compare the two. This is a little less helpful without object names or
1285 dates, but hopefully we get the idea.</p></div>
1286 <div class="listingblock">
1287 <div class="content">
1288 <pre><code>$ diff -u commit-date.txt author-date.txt</code></pre>
1289 </div></div>
1290 <div class="paragraph"><p>This display indicates that commits can be reordered after they&#8217;re written, for
1291 example with <code>git rebase</code>.</p></div>
1292 <div class="paragraph"><p>Let&#8217;s try one more reordering of commits. <code>rev_info</code> exposes a <code>reverse</code> flag.
1293 Set that flag somewhere inside of <code>final_rev_info_setup()</code>:</p></div>
1294 <div class="listingblock">
1295 <div class="content">
1296 <pre><code>static void final_rev_info_setup(int argc, const char **argv, const char *prefix,
1297                 struct rev_info *rev)
1298 {
1299         ...
1300
1301         rev-&gt;reverse = 1;
1302
1303         ...
1304 }</code></pre>
1305 </div></div>
1306 <div class="paragraph"><p>Run your walk again and note the difference in order. (If you remove the grep
1307 pattern, you should see the last commit this call gives you as your current
1308 HEAD.)</p></div>
1309 </div>
1310 </div>
1311 </div>
1312 <div class="sect1">
1313 <h2 id="_basic_object_walk">Basic Object Walk</h2>
1314 <div class="sectionbody">
1315 <div class="paragraph"><p>So far we&#8217;ve been walking only commits. But Git has more types of objects than
1316 that! Let&#8217;s see if we can walk <em>all</em> objects, and find out some information
1317 about each one.</p></div>
1318 <div class="paragraph"><p>We can base our work on an example. <code>git pack-objects</code> prepares all kinds of
1319 objects for packing into a bitmap or packfile. The work we are interested in
1320 resides in <code>builtins/pack-objects.c:get_object_list()</code>; examination of that
1321 function shows that the all-object walk is being performed by
1322 <code>traverse_commit_list()</code> or <code>traverse_commit_list_filtered()</code>. Those two
1323 functions reside in <code>list-objects.c</code>; examining the source shows that, despite
1324 the name, these functions traverse all kinds of objects. Let&#8217;s have a look at
1325 the arguments to <code>traverse_commit_list()</code>.</p></div>
1326 <div class="ulist"><ul>
1327 <li>
1328 <p>
1329 <code>struct rev_info *revs</code>: This is the <code>rev_info</code> used for the walk. If
1330   its <code>filter</code> member is not <code>NULL</code>, then <code>filter</code> contains information for
1331   how to filter the object list.
1332 </p>
1333 </li>
1334 <li>
1335 <p>
1336 <code>show_commit_fn show_commit</code>: A callback which will be used to handle each
1337   individual commit object.
1338 </p>
1339 </li>
1340 <li>
1341 <p>
1342 <code>show_object_fn show_object</code>: A callback which will be used to handle each
1343   non-commit object (so each blob, tree, or tag).
1344 </p>
1345 </li>
1346 <li>
1347 <p>
1348 <code>void *show_data</code>: A context buffer which is passed in turn to <code>show_commit</code>
1349   and <code>show_object</code>.
1350 </p>
1351 </li>
1352 </ul></div>
1353 <div class="paragraph"><p>In addition, <code>traverse_commit_list_filtered()</code> has an additional parameter:</p></div>
1354 <div class="ulist"><ul>
1355 <li>
1356 <p>
1357 <code>struct oidset *omitted</code>: A linked-list of object IDs which the provided
1358   filter caused to be omitted.
1359 </p>
1360 </li>
1361 </ul></div>
1362 <div class="paragraph"><p>It looks like these methods use callbacks we provide instead of needing us
1363 to call it repeatedly ourselves. Cool! Let&#8217;s add the callbacks first.</p></div>
1364 <div class="paragraph"><p>For the sake of this tutorial, we&#8217;ll simply keep track of how many of each kind
1365 of object we find. At file scope in <code>builtin/walken.c</code> add the following
1366 tracking variables:</p></div>
1367 <div class="listingblock">
1368 <div class="content">
1369 <pre><code>static int commit_count;
1370 static int tag_count;
1371 static int blob_count;
1372 static int tree_count;</code></pre>
1373 </div></div>
1374 <div class="paragraph"><p>Commits are handled by a different callback than other objects; let&#8217;s do that
1375 one first:</p></div>
1376 <div class="listingblock">
1377 <div class="content">
1378 <pre><code>static void walken_show_commit(struct commit *cmt, void *buf)
1379 {
1380         commit_count++;
1381 }</code></pre>
1382 </div></div>
1383 <div class="paragraph"><p>The <code>cmt</code> argument is fairly self-explanatory. But it&#8217;s worth mentioning that
1384 the <code>buf</code> argument is actually the context buffer that we can provide to the
1385 traversal calls - <code>show_data</code>, which we mentioned a moment ago.</p></div>
1386 <div class="paragraph"><p>Since we have the <code>struct commit</code> object, we can look at all the same parts that
1387 we looked at in our earlier commit-only walk. For the sake of this tutorial,
1388 though, we&#8217;ll just increment the commit counter and move on.</p></div>
1389 <div class="paragraph"><p>The callback for non-commits is a little different, as we&#8217;ll need to check
1390 which kind of object we&#8217;re dealing with:</p></div>
1391 <div class="listingblock">
1392 <div class="content">
1393 <pre><code>static void walken_show_object(struct object *obj, const char *str, void *buf)
1394 {
1395         switch (obj-&gt;type) {
1396         case OBJ_TREE:
1397                 tree_count++;
1398                 break;
1399         case OBJ_BLOB:
1400                 blob_count++;
1401                 break;
1402         case OBJ_TAG:
1403                 tag_count++;
1404                 break;
1405         case OBJ_COMMIT:
1406                 BUG("unexpected commit object in walken_show_object\n");
1407         default:
1408                 BUG("unexpected object type %s in walken_show_object\n",
1409                         type_name(obj-&gt;type));
1410         }
1411 }</code></pre>
1412 </div></div>
1413 <div class="paragraph"><p>Again, <code>obj</code> is fairly self-explanatory, and we can guess that <code>buf</code> is the same
1414 context pointer that <code>walken_show_commit()</code> receives: the <code>show_data</code> argument
1415 to <code>traverse_commit_list()</code> and <code>traverse_commit_list_filtered()</code>. Finally,
1416 <code>str</code> contains the name of the object, which ends up being something like
1417 <code>foo.txt</code> (blob), <code>bar/baz</code> (tree), or <code>v1.2.3</code> (tag).</p></div>
1418 <div class="paragraph"><p>To help assure us that we aren&#8217;t double-counting commits, we&#8217;ll include some
1419 complaining if a commit object is routed through our non-commit callback; we&#8217;ll
1420 also complain if we see an invalid object type. Since those two cases should be
1421 unreachable, and would only change in the event of a semantic change to the Git
1422 codebase, we complain by using <code>BUG()</code> - which is a signal to a developer that
1423 the change they made caused unintended consequences, and the rest of the
1424 codebase needs to be updated to understand that change. <code>BUG()</code> is not intended
1425 to be seen by the public, so it is not localized.</p></div>
1426 <div class="paragraph"><p>Our main object walk implementation is substantially different from our commit
1427 walk implementation, so let&#8217;s make a new function to perform the object walk. We
1428 can perform setup which is applicable to all objects here, too, to keep separate
1429 from setup which is applicable to commit-only walks.</p></div>
1430 <div class="paragraph"><p>We&#8217;ll start by enabling all types of objects in the <code>struct rev_info</code>.  We&#8217;ll
1431 also turn on <code>tree_blobs_in_commit_order</code>, which means that we will walk a
1432 commit&#8217;s tree and everything it points to immediately after we find each commit,
1433 as opposed to waiting for the end and walking through all trees after the commit
1434 history has been discovered. With the appropriate settings configured, we are
1435 ready to call <code>prepare_revision_walk()</code>.</p></div>
1436 <div class="listingblock">
1437 <div class="content">
1438 <pre><code>static void walken_object_walk(struct rev_info *rev)
1439 {
1440         rev-&gt;tree_objects = 1;
1441         rev-&gt;blob_objects = 1;
1442         rev-&gt;tag_objects = 1;
1443         rev-&gt;tree_blobs_in_commit_order = 1;
1444
1445         if (prepare_revision_walk(rev))
1446                 die(_("revision walk setup failed"));
1447
1448         commit_count = 0;
1449         tag_count = 0;
1450         blob_count = 0;
1451         tree_count = 0;</code></pre>
1452 </div></div>
1453 <div class="paragraph"><p>Let&#8217;s start by calling just the unfiltered walk and reporting our counts.
1454 Complete your implementation of <code>walken_object_walk()</code>.
1455 We&#8217;ll also need to include the <code>list-objects.h</code> header.</p></div>
1456 <div class="listingblock">
1457 <div class="content">
1458 <pre><code>#include "list-objects.h"
1459
1460 ...
1461
1462         traverse_commit_list(rev, walken_show_commit, walken_show_object, NULL);
1463
1464         printf("commits %d\nblobs %d\ntags %d\ntrees %d\n", commit_count,
1465                 blob_count, tag_count, tree_count);
1466 }</code></pre>
1467 </div></div>
1468 <div class="admonitionblock">
1469 <table><tr>
1470 <td class="icon">
1471 <div class="title">Note</div>
1472 </td>
1473 <td class="content">This output is intended to be machine-parsed. Therefore, we are not
1474 sending it to <code>trace_printf()</code>, and we are not localizing it - we need scripts
1475 to be able to count on the formatting to be exactly the way it is shown here.
1476 If we were intending this output to be read by humans, we would need to localize
1477 it with <code>_()</code>.</td>
1478 </tr></table>
1479 </div>
1480 <div class="paragraph"><p>Finally, we&#8217;ll ask <code>cmd_walken()</code> to use the object walk instead. Discussing
1481 command line options is out of scope for this tutorial, so we&#8217;ll just hardcode
1482 a branch we can change at compile time. Where you call <code>final_rev_info_setup()</code>
1483 and <code>walken_commit_walk()</code>, instead branch like so:</p></div>
1484 <div class="listingblock">
1485 <div class="content">
1486 <pre><code>        if (1) {
1487                 add_head_to_pending(&amp;rev);
1488                 walken_object_walk(&amp;rev);
1489         } else {
1490                 final_rev_info_setup(argc, argv, prefix, &amp;rev);
1491                 walken_commit_walk(&amp;rev);
1492         }</code></pre>
1493 </div></div>
1494 <div class="admonitionblock">
1495 <table><tr>
1496 <td class="icon">
1497 <div class="title">Note</div>
1498 </td>
1499 <td class="content">For simplicity, we&#8217;ve avoided all the filters and sorts we applied in
1500 <code>final_rev_info_setup()</code> and simply added <code>HEAD</code> to our pending queue. If you
1501 want, you can certainly use the filters we added before by moving
1502 <code>final_rev_info_setup()</code> out of the conditional and removing the call to
1503 <code>add_head_to_pending()</code>.</td>
1504 </tr></table>
1505 </div>
1506 <div class="paragraph"><p>Now we can try to run our command! It should take noticeably longer than the
1507 commit walk, but an examination of the output will give you an idea why. Your
1508 output should look similar to this example, but with different counts:</p></div>
1509 <div class="listingblock">
1510 <div class="content">
1511 <pre><code>Object walk completed. Found 55733 commits, 100274 blobs, 0 tags, and 104210 trees.</code></pre>
1512 </div></div>
1513 <div class="paragraph"><p>This makes sense. We have more trees than commits because the Git project has
1514 lots of subdirectories which can change, plus at least one tree per commit. We
1515 have no tags because we started on a commit (<code>HEAD</code>) and while tags can point to
1516 commits, commits can&#8217;t point to tags.</p></div>
1517 <div class="admonitionblock">
1518 <table><tr>
1519 <td class="icon">
1520 <div class="title">Note</div>
1521 </td>
1522 <td class="content">You will have different counts when you run this yourself! The number of
1523 objects grows along with the Git project.</td>
1524 </tr></table>
1525 </div>
1526 <div class="sect2">
1527 <h3 id="_adding_a_filter_2">Adding a Filter</h3>
1528 <div class="paragraph"><p>There are a handful of filters that we can apply to the object walk laid out in
1529 <code>Documentation/rev-list-options.txt</code>. These filters are typically useful for
1530 operations such as creating packfiles or performing a partial clone. They are
1531 defined in <code>list-objects-filter-options.h</code>. For the purposes of this tutorial we
1532 will use the "tree:1" filter, which causes the walk to omit all trees and blobs
1533 which are not directly referenced by commits reachable from the commit in
1534 <code>pending</code> when the walk begins. (<code>pending</code> is the list of objects which need to
1535 be traversed during a walk; you can imagine a breadth-first tree traversal to
1536 help understand. In our case, that means we omit trees and blobs not directly
1537 referenced by <code>HEAD</code> or <code>HEAD</code>'s history, because we begin the walk with only
1538 <code>HEAD</code> in the <code>pending</code> list.)</p></div>
1539 <div class="paragraph"><p>For now, we are not going to track the omitted objects, so we&#8217;ll replace those
1540 parameters with <code>NULL</code>. For the sake of simplicity, we&#8217;ll add a simple
1541 build-time branch to use our filter or not. Preface the line calling
1542 <code>traverse_commit_list()</code> with the following, which will remind us which kind of
1543 walk we&#8217;ve just performed:</p></div>
1544 <div class="listingblock">
1545 <div class="content">
1546 <pre><code>        if (0) {
1547                 /* Unfiltered: */
1548                 trace_printf(_("Unfiltered object walk.\n"));
1549         } else {
1550                 trace_printf(
1551                         _("Filtered object walk with filterspec 'tree:1'.\n"));
1552                 CALLOC_ARRAY(rev-&gt;filter, 1);
1553                 parse_list_objects_filter(rev-&gt;filter, "tree:1");
1554         }
1555         traverse_commit_list(rev, walken_show_commit,
1556                              walken_show_object, NULL);</code></pre>
1557 </div></div>
1558 <div class="paragraph"><p>The <code>rev-&gt;filter</code> member is usually built directly from a command
1559 line argument, so the module provides an easy way to build one from a string.
1560 Even though we aren&#8217;t taking user input right now, we can still build one with
1561 a hardcoded string using <code>parse_list_objects_filter()</code>.</p></div>
1562 <div class="paragraph"><p>With the filter spec "tree:1", we are expecting to see <em>only</em> the root tree for
1563 each commit; therefore, the tree object count should be less than or equal to
1564 the number of commits. (For an example of why that&#8217;s true: <code>git commit --revert</code>
1565 points to the same tree object as its grandparent.)</p></div>
1566 </div>
1567 <div class="sect2">
1568 <h3 id="_counting_omitted_objects">Counting Omitted Objects</h3>
1569 <div class="paragraph"><p>We also have the capability to enumerate all objects which were omitted by a
1570 filter, like with <code>git log --filter=&lt;spec&gt; --filter-print-omitted</code>. Asking
1571 <code>traverse_commit_list_filtered()</code> to populate the <code>omitted</code> list means that our
1572 object walk does not perform any better than an unfiltered object walk; all
1573 reachable objects are walked in order to populate the list.</p></div>
1574 <div class="paragraph"><p>First, add the <code>struct oidset</code> and related items we will use to iterate it:</p></div>
1575 <div class="listingblock">
1576 <div class="content">
1577 <pre><code>#include "oidset.h"
1578
1579 ...
1580
1581 static void walken_object_walk(
1582         ...
1583
1584         struct oidset omitted;
1585         struct oidset_iter oit;
1586         struct object_id *oid = NULL;
1587         int omitted_count = 0;
1588         oidset_init(&amp;omitted, 0);
1589
1590         ...</code></pre>
1591 </div></div>
1592 <div class="paragraph"><p>Modify the call to <code>traverse_commit_list_filtered()</code> to include your <code>omitted</code>
1593 object:</p></div>
1594 <div class="listingblock">
1595 <div class="content">
1596 <pre><code>        ...
1597
1598                 traverse_commit_list_filtered(rev,
1599                         walken_show_commit, walken_show_object, NULL, &amp;omitted);
1600
1601         ...</code></pre>
1602 </div></div>
1603 <div class="paragraph"><p>Then, after your traversal, the <code>oidset</code> traversal is pretty straightforward.
1604 Count all the objects within and modify the print statement:</p></div>
1605 <div class="listingblock">
1606 <div class="content">
1607 <pre><code>        /* Count the omitted objects. */
1608         oidset_iter_init(&amp;omitted, &amp;oit);
1609
1610         while ((oid = oidset_iter_next(&amp;oit)))
1611                 omitted_count++;
1612
1613         printf("commits %d\nblobs %d\ntags %d\ntrees %d\nomitted %d\n",
1614                 commit_count, blob_count, tag_count, tree_count, omitted_count);</code></pre>
1615 </div></div>
1616 <div class="paragraph"><p>By running your walk with and without the filter, you should find that the total
1617 object count in each case is identical. You can also time each invocation of
1618 the <code>walken</code> subcommand, with and without <code>omitted</code> being passed in, to confirm
1619 to yourself the runtime impact of tracking all omitted objects.</p></div>
1620 </div>
1621 <div class="sect2">
1622 <h3 id="_changing_the_order_2">Changing the Order</h3>
1623 <div class="paragraph"><p>Finally, let&#8217;s demonstrate that you can also reorder walks of all objects, not
1624 just walks of commits. First, we&#8217;ll make our handlers chattier - modify
1625 <code>walken_show_commit()</code> and <code>walken_show_object()</code> to print the object as they
1626 go:</p></div>
1627 <div class="listingblock">
1628 <div class="content">
1629 <pre><code>#include "hex.h"
1630
1631 ...
1632
1633 static void walken_show_commit(struct commit *cmt, void *buf)
1634 {
1635         trace_printf("commit: %s\n", oid_to_hex(&amp;cmt-&gt;object.oid));
1636         commit_count++;
1637 }
1638
1639 static void walken_show_object(struct object *obj, const char *str, void *buf)
1640 {
1641         trace_printf("%s: %s\n", type_name(obj-&gt;type), oid_to_hex(&amp;obj-&gt;oid));
1642
1643         ...
1644 }</code></pre>
1645 </div></div>
1646 <div class="admonitionblock">
1647 <table><tr>
1648 <td class="icon">
1649 <div class="title">Note</div>
1650 </td>
1651 <td class="content">Since we will be examining this output directly as humans, we&#8217;ll use
1652 <code>trace_printf()</code> here. Additionally, since this change introduces a significant
1653 number of printed lines, using <code>trace_printf()</code> will allow us to easily silence
1654 those lines without having to recompile.</td>
1655 </tr></table>
1656 </div>
1657 <div class="paragraph"><p>(Leave the counter increment logic in place.)</p></div>
1658 <div class="paragraph"><p>With only that change, run again (but save yourself some scrollback):</p></div>
1659 <div class="listingblock">
1660 <div class="content">
1661 <pre><code>$ GIT_TRACE=1 ./bin-wrappers/git walken | head -n 10</code></pre>
1662 </div></div>
1663 <div class="paragraph"><p>Take a look at the top commit with <code>git show</code> and the object ID you printed; it
1664 should be the same as the output of <code>git show HEAD</code>.</p></div>
1665 <div class="paragraph"><p>Next, let&#8217;s change a setting on our <code>struct rev_info</code> within
1666 <code>walken_object_walk()</code>. Find where you&#8217;re changing the other settings on <code>rev</code>,
1667 such as <code>rev-&gt;tree_objects</code> and <code>rev-&gt;tree_blobs_in_commit_order</code>, and add the
1668 <code>reverse</code> setting at the bottom:</p></div>
1669 <div class="listingblock">
1670 <div class="content">
1671 <pre><code>        ...
1672
1673         rev-&gt;tree_objects = 1;
1674         rev-&gt;blob_objects = 1;
1675         rev-&gt;tag_objects = 1;
1676         rev-&gt;tree_blobs_in_commit_order = 1;
1677         rev-&gt;reverse = 1;
1678
1679         ...</code></pre>
1680 </div></div>
1681 <div class="paragraph"><p>Now, run again, but this time, let&#8217;s grab the last handful of objects instead
1682 of the first handful:</p></div>
1683 <div class="listingblock">
1684 <div class="content">
1685 <pre><code>$ make
1686 $ GIT_TRACE=1 ./bin-wrappers git walken | tail -n 10</code></pre>
1687 </div></div>
1688 <div class="paragraph"><p>The last commit object given should have the same OID as the one we saw at the
1689 top before, and running <code>git show &lt;oid&gt;</code> with that OID should give you again
1690 the same results as <code>git show HEAD</code>. Furthermore, if you run and examine the
1691 first ten lines again (with <code>head</code> instead of <code>tail</code> like we did before applying
1692 the <code>reverse</code> setting), you should see that now the first commit printed is the
1693 initial commit, <code>e83c5163</code>.</p></div>
1694 </div>
1695 </div>
1696 </div>
1697 <div class="sect1">
1698 <h2 id="_wrapping_up">Wrapping Up</h2>
1699 <div class="sectionbody">
1700 <div class="paragraph"><p>Let&#8217;s review. In this tutorial, we:</p></div>
1701 <div class="ulist"><ul>
1702 <li>
1703 <p>
1704 Built a commit walk from the ground up
1705 </p>
1706 </li>
1707 <li>
1708 <p>
1709 Enabled a grep filter for that commit walk
1710 </p>
1711 </li>
1712 <li>
1713 <p>
1714 Changed the sort order of that filtered commit walk
1715 </p>
1716 </li>
1717 <li>
1718 <p>
1719 Built an object walk (tags, commits, trees, and blobs) from the ground up
1720 </p>
1721 </li>
1722 <li>
1723 <p>
1724 Learned how to add a filter-spec to an object walk
1725 </p>
1726 </li>
1727 <li>
1728 <p>
1729 Changed the display order of the filtered object walk
1730 </p>
1731 </li>
1732 </ul></div>
1733 </div>
1734 </div>
1735 </div>
1736 <div id="footnotes"><hr /></div>
1737 <div id="footer">
1738 <div id="footer-text">
1739 Last updated
1740  2023-07-17 11:51:48 PDT
1741 </div>
1742 </div>
1743 </body>
1744 </html>