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-05-16</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,
 993                              const struct config_context *ctx, void *cb)
 994 {
 995         /*
 996          * For now, we don't have any custom configuration, so fall back to
 997          * the default config.
 998          */
 999         return git_default_config(var, value, ctx, cb);
1000 }</code></pre>
1001 </div></div>
1002 <div class="paragraph"><p>Make sure to invoke <code>git_config()</code> with it in your <code>cmd_walken()</code>:</p></div>
1003 <div class="listingblock">
1004 <div class="content">
1005 <pre><code>int cmd_walken(int argc, const char **argv, const char *prefix)
1006 {
1007         ...
1008
1009         git_config(git_walken_config, NULL);
1010
1011         ...
1012 }</code></pre>
1013 </div></div>
1014 </div>
1015 <div class="sect3">
1016 <h4 id="_setting_up_code_rev_info_code">Setting Up <code>rev_info</code></h4>
1017 <div class="paragraph"><p>Now that we&#8217;ve gathered external configuration and options, it&#8217;s time to
1018 initialize the <code>rev_info</code> object which we will use to perform the walk. This is
1019 typically done by calling <code>repo_init_revisions()</code> with the repository you intend
1020 to target, as well as the <code>prefix</code> argument of <code>cmd_walken</code> and your <code>rev_info</code>
1021 struct.</p></div>
1022 <div class="paragraph"><p>Add the <code>struct rev_info</code> and the <code>repo_init_revisions()</code> call.
1023 We&#8217;ll also need to include the <code>revision.h</code> header:</p></div>
1024 <div class="listingblock">
1025 <div class="content">
1026 <pre><code>#include "revision.h"
1027
1028 ...
1029
1030 int cmd_walken(int argc, const char **argv, const char *prefix)
1031 {
1032         /* This can go wherever you like in your declarations.*/
1033         struct rev_info rev;
1034         ...
1035
1036         /* This should go after the git_config() call. */
1037         repo_init_revisions(the_repository, &amp;rev, prefix);
1038
1039         ...
1040 }</code></pre>
1041 </div></div>
1042 </div>
1043 <div class="sect3">
1044 <h4 id="_tweaking_code_rev_info_code_for_the_walk">Tweaking <code>rev_info</code> For the Walk</h4>
1045 <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
1046 initialized, we can modify it to fit our needs. This is usually done within a
1047 helper for clarity, so let&#8217;s add one:</p></div>
1048 <div class="listingblock">
1049 <div class="content">
1050 <pre><code>static void final_rev_info_setup(struct rev_info *rev)
1051 {
1052         /*
1053          * We want to mimic the appearance of `git log --oneline`, so let's
1054          * force oneline format.
1055          */
1056         get_commit_format("oneline", rev);
1057
1058         /* Start our object walk at HEAD. */
1059         add_head_to_pending(rev);
1060 }</code></pre>
1061 </div></div>
1062 <div class="admonitionblock">
1063 <table><tr>
1064 <td class="icon">
1065 <div class="title">Note</div>
1066 </td>
1067 <td class="content">
1068 <div class="paragraph"><p>Instead of using the shorthand <code>add_head_to_pending()</code>, you could do
1069 something like this:</p></div>
1070 <div class="listingblock">
1071 <div class="content">
1072 <pre><code>        struct setup_revision_opt opt;
1073
1074         memset(&amp;opt, 0, sizeof(opt));
1075         opt.def = "HEAD";
1076         opt.revarg_opt = REVARG_COMMITTISH;
1077         setup_revisions(argc, argv, rev, &amp;opt);</code></pre>
1078 </div></div>
1079 <div class="paragraph"><p>Using a <code>setup_revision_opt</code> gives you finer control over your walk&#8217;s starting
1080 point.</p></div>
1081 </td>
1082 </tr></table>
1083 </div>
1084 <div class="paragraph"><p>Then let&#8217;s invoke <code>final_rev_info_setup()</code> after the call to
1085 <code>repo_init_revisions()</code>:</p></div>
1086 <div class="listingblock">
1087 <div class="content">
1088 <pre><code>int cmd_walken(int argc, const char **argv, const char *prefix)
1089 {
1090         ...
1091
1092         final_rev_info_setup(&amp;rev);
1093
1094         ...
1095 }</code></pre>
1096 </div></div>
1097 <div class="paragraph"><p>Later, we may wish to add more arguments to <code>final_rev_info_setup()</code>. But for
1098 now, this is all we need.</p></div>
1099 </div>
1100 <div class="sect3">
1101 <h4 id="_preparing_code_rev_info_code_for_the_walk">Preparing <code>rev_info</code> For the Walk</h4>
1102 <div class="paragraph"><p>Now that <code>rev</code> is all initialized and configured, we&#8217;ve got one more setup step
1103 before we get rolling. We can do this in a helper, which will both prepare the
1104 <code>rev_info</code> for the walk, and perform the walk itself. Let&#8217;s start the helper
1105 with the call to <code>prepare_revision_walk()</code>, which can return an error without
1106 dying on its own:</p></div>
1107 <div class="listingblock">
1108 <div class="content">
1109 <pre><code>static void walken_commit_walk(struct rev_info *rev)
1110 {
1111         if (prepare_revision_walk(rev))
1112                 die(_("revision walk setup failed"));
1113 }</code></pre>
1114 </div></div>
1115 <div class="admonitionblock">
1116 <table><tr>
1117 <td class="icon">
1118 <div class="title">Note</div>
1119 </td>
1120 <td class="content"><code>die()</code> prints to <code>stderr</code> and exits the program. Since it will print to
1121 <code>stderr</code> it&#8217;s likely to be seen by a human, so we will localize it.</td>
1122 </tr></table>
1123 </div>
1124 </div>
1125 <div class="sect3">
1126 <h4 id="_performing_the_walk">Performing the Walk!</h4>
1127 <div class="paragraph"><p>Finally! We are ready to begin the walk itself. Now we can see that <code>rev_info</code>
1128 can also be used as an iterator; we move to the next item in the walk by using
1129 <code>get_revision()</code> repeatedly. Add the listed variable declarations at the top and
1130 the walk loop below the <code>prepare_revision_walk()</code> call within your
1131 <code>walken_commit_walk()</code>:</p></div>
1132 <div class="listingblock">
1133 <div class="content">
1134 <pre><code>#include "pretty.h"
1135
1136 ...
1137
1138 static void walken_commit_walk(struct rev_info *rev)
1139 {
1140         struct commit *commit;
1141         struct strbuf prettybuf = STRBUF_INIT;
1142
1143         ...
1144
1145         while ((commit = get_revision(rev))) {
1146                 strbuf_reset(&amp;prettybuf);
1147                 pp_commit_easy(CMIT_FMT_ONELINE, commit, &amp;prettybuf);
1148                 puts(prettybuf.buf);
1149         }
1150         strbuf_release(&amp;prettybuf);
1151 }</code></pre>
1152 </div></div>
1153 <div class="admonitionblock">
1154 <table><tr>
1155 <td class="icon">
1156 <div class="title">Note</div>
1157 </td>
1158 <td class="content"><code>puts()</code> prints a <code>char*</code> to <code>stdout</code>. Since this is the part of the
1159 command we expect to be machine-parsed, we&#8217;re sending it directly to stdout.</td>
1160 </tr></table>
1161 </div>
1162 <div class="paragraph"><p>Give it a shot.</p></div>
1163 <div class="listingblock">
1164 <div class="content">
1165 <pre><code>$ make
1166 $ ./bin-wrappers/git walken</code></pre>
1167 </div></div>
1168 <div class="paragraph"><p>You should see all of the subject lines of all the commits in
1169 your tree&#8217;s history, in order, ending with the initial commit, "Initial revision
1170 of "git", the information manager from hell". Congratulations! You&#8217;ve written
1171 your first revision walk. You can play with printing some additional fields
1172 from each commit if you&#8217;re curious; have a look at the functions available in
1173 <code>commit.h</code>.</p></div>
1174 </div>
1175 </div>
1176 <div class="sect2">
1177 <h3 id="_adding_a_filter">Adding a Filter</h3>
1178 <div class="paragraph"><p>Next, let&#8217;s try to filter the commits we see based on their author. This is
1179 equivalent to running <code>git log --author=&lt;pattern&gt;</code>. We can add a filter by
1180 modifying <code>rev_info.grep_filter</code>, which is a <code>struct grep_opt</code>.</p></div>
1181 <div class="paragraph"><p>First some setup. Add <code>grep_config()</code> to <code>git_walken_config()</code>:</p></div>
1182 <div class="listingblock">
1183 <div class="content">
1184 <pre><code>static int git_walken_config(const char *var, const char *value,
1185                              const struct config_context *ctx, void *cb)
1186 {
1187         grep_config(var, value, ctx, cb);
1188         return git_default_config(var, value, ctx, cb);
1189 }</code></pre>
1190 </div></div>
1191 <div class="paragraph"><p>Next, we can modify the <code>grep_filter</code>. This is done with convenience functions
1192 found in <code>grep.h</code>. For fun, we&#8217;re filtering to only commits from folks using a
1193 <code>gmail.com</code> email address - a not-very-precise guess at who may be working on
1194 Git as a hobby. Since we&#8217;re checking the author, which is a specific line in the
1195 header, we&#8217;ll use the <code>append_header_grep_pattern()</code> helper. We can use
1196 the <code>enum grep_header_field</code> to indicate which part of the commit header we want
1197 to search.</p></div>
1198 <div class="paragraph"><p>In <code>final_rev_info_setup()</code>, add your filter line:</p></div>
1199 <div class="listingblock">
1200 <div class="content">
1201 <pre><code>static void final_rev_info_setup(int argc, const char **argv,
1202                 const char *prefix, struct rev_info *rev)
1203 {
1204         ...
1205
1206         append_header_grep_pattern(&amp;rev-&gt;grep_filter, GREP_HEADER_AUTHOR,
1207                 "gmail");
1208         compile_grep_patterns(&amp;rev-&gt;grep_filter);
1209
1210         ...
1211 }</code></pre>
1212 </div></div>
1213 <div class="paragraph"><p><code>append_header_grep_pattern()</code> adds your new "gmail" pattern to <code>rev_info</code>, but
1214 it won&#8217;t work unless we compile it with <code>compile_grep_patterns()</code>.</p></div>
1215 <div class="admonitionblock">
1216 <table><tr>
1217 <td class="icon">
1218 <div class="title">Note</div>
1219 </td>
1220 <td class="content">If you are using <code>setup_revisions()</code> (for example, if you are passing a
1221 <code>setup_revision_opt</code> instead of using <code>add_head_to_pending()</code>), you don&#8217;t need
1222 to call <code>compile_grep_patterns()</code> because <code>setup_revisions()</code> calls it for you.</td>
1223 </tr></table>
1224 </div>
1225 <div class="admonitionblock">
1226 <table><tr>
1227 <td class="icon">
1228 <div class="title">Note</div>
1229 </td>
1230 <td class="content">We could add the same filter via the <code>append_grep_pattern()</code> helper if we
1231 wanted to, but <code>append_header_grep_pattern()</code> adds the <code>enum grep_context</code> and
1232 <code>enum grep_pat_token</code> for us.</td>
1233 </tr></table>
1234 </div>
1235 </div>
1236 <div class="sect2">
1237 <h3 id="_changing_the_order">Changing the Order</h3>
1238 <div class="paragraph"><p>There are a few ways that we can change the order of the commits during a
1239 revision walk. Firstly, we can use the <code>enum rev_sort_order</code> to choose from some
1240 typical orderings.</p></div>
1241 <div class="paragraph"><p><code>topo_order</code> is the same as <code>git log --topo-order</code>: we avoid showing a parent
1242 before all of its children have been shown, and we avoid mixing commits which
1243 are in different lines of history. (<code>git help log</code>'s section on <code>--topo-order</code>
1244 has a very nice diagram to illustrate this.)</p></div>
1245 <div class="paragraph"><p>Let&#8217;s see what happens when we run with <code>REV_SORT_BY_COMMIT_DATE</code> as opposed to
1246 <code>REV_SORT_BY_AUTHOR_DATE</code>. Add the following:</p></div>
1247 <div class="listingblock">
1248 <div class="content">
1249 <pre><code>static void final_rev_info_setup(int argc, const char **argv,
1250                 const char *prefix, struct rev_info *rev)
1251 {
1252         ...
1253
1254         rev-&gt;topo_order = 1;
1255         rev-&gt;sort_order = REV_SORT_BY_COMMIT_DATE;
1256
1257         ...
1258 }</code></pre>
1259 </div></div>
1260 <div class="paragraph"><p>Let&#8217;s output this into a file so we can easily diff it with the walk sorted by
1261 author date.</p></div>
1262 <div class="listingblock">
1263 <div class="content">
1264 <pre><code>$ make
1265 $ ./bin-wrappers/git walken &gt; commit-date.txt</code></pre>
1266 </div></div>
1267 <div class="paragraph"><p>Then, let&#8217;s sort by author date and run it again.</p></div>
1268 <div class="listingblock">
1269 <div class="content">
1270 <pre><code>static void final_rev_info_setup(int argc, const char **argv,
1271                 const char *prefix, struct rev_info *rev)
1272 {
1273         ...
1274
1275         rev-&gt;topo_order = 1;
1276         rev-&gt;sort_order = REV_SORT_BY_AUTHOR_DATE;
1277
1278         ...
1279 }</code></pre>
1280 </div></div>
1281 <div class="listingblock">
1282 <div class="content">
1283 <pre><code>$ make
1284 $ ./bin-wrappers/git walken &gt; author-date.txt</code></pre>
1285 </div></div>
1286 <div class="paragraph"><p>Finally, compare the two. This is a little less helpful without object names or
1287 dates, but hopefully we get the idea.</p></div>
1288 <div class="listingblock">
1289 <div class="content">
1290 <pre><code>$ diff -u commit-date.txt author-date.txt</code></pre>
1291 </div></div>
1292 <div class="paragraph"><p>This display indicates that commits can be reordered after they&#8217;re written, for
1293 example with <code>git rebase</code>.</p></div>
1294 <div class="paragraph"><p>Let&#8217;s try one more reordering of commits. <code>rev_info</code> exposes a <code>reverse</code> flag.
1295 Set that flag somewhere inside of <code>final_rev_info_setup()</code>:</p></div>
1296 <div class="listingblock">
1297 <div class="content">
1298 <pre><code>static void final_rev_info_setup(int argc, const char **argv, const char *prefix,
1299                 struct rev_info *rev)
1300 {
1301         ...
1302
1303         rev-&gt;reverse = 1;
1304
1305         ...
1306 }</code></pre>
1307 </div></div>
1308 <div class="paragraph"><p>Run your walk again and note the difference in order. (If you remove the grep
1309 pattern, you should see the last commit this call gives you as your current
1310 HEAD.)</p></div>
1311 </div>
1312 </div>
1313 </div>
1314 <div class="sect1">
1315 <h2 id="_basic_object_walk">Basic Object Walk</h2>
1316 <div class="sectionbody">
1317 <div class="paragraph"><p>So far we&#8217;ve been walking only commits. But Git has more types of objects than
1318 that! Let&#8217;s see if we can walk <em>all</em> objects, and find out some information
1319 about each one.</p></div>
1320 <div class="paragraph"><p>We can base our work on an example. <code>git pack-objects</code> prepares all kinds of
1321 objects for packing into a bitmap or packfile. The work we are interested in
1322 resides in <code>builtin/pack-objects.c:get_object_list()</code>; examination of that
1323 function shows that the all-object walk is being performed by
1324 <code>traverse_commit_list()</code> or <code>traverse_commit_list_filtered()</code>. Those two
1325 functions reside in <code>list-objects.c</code>; examining the source shows that, despite
1326 the name, these functions traverse all kinds of objects. Let&#8217;s have a look at
1327 the arguments to <code>traverse_commit_list()</code>.</p></div>
1328 <div class="ulist"><ul>
1329 <li>
1330 <p>
1331 <code>struct rev_info *revs</code>: This is the <code>rev_info</code> used for the walk. If
1332   its <code>filter</code> member is not <code>NULL</code>, then <code>filter</code> contains information for
1333   how to filter the object list.
1334 </p>
1335 </li>
1336 <li>
1337 <p>
1338 <code>show_commit_fn show_commit</code>: A callback which will be used to handle each
1339   individual commit object.
1340 </p>
1341 </li>
1342 <li>
1343 <p>
1344 <code>show_object_fn show_object</code>: A callback which will be used to handle each
1345   non-commit object (so each blob, tree, or tag).
1346 </p>
1347 </li>
1348 <li>
1349 <p>
1350 <code>void *show_data</code>: A context buffer which is passed in turn to <code>show_commit</code>
1351   and <code>show_object</code>.
1352 </p>
1353 </li>
1354 </ul></div>
1355 <div class="paragraph"><p>In addition, <code>traverse_commit_list_filtered()</code> has an additional parameter:</p></div>
1356 <div class="ulist"><ul>
1357 <li>
1358 <p>
1359 <code>struct oidset *omitted</code>: A linked-list of object IDs which the provided
1360   filter caused to be omitted.
1361 </p>
1362 </li>
1363 </ul></div>
1364 <div class="paragraph"><p>It looks like these methods use callbacks we provide instead of needing us
1365 to call it repeatedly ourselves. Cool! Let&#8217;s add the callbacks first.</p></div>
1366 <div class="paragraph"><p>For the sake of this tutorial, we&#8217;ll simply keep track of how many of each kind
1367 of object we find. At file scope in <code>builtin/walken.c</code> add the following
1368 tracking variables:</p></div>
1369 <div class="listingblock">
1370 <div class="content">
1371 <pre><code>static int commit_count;
1372 static int tag_count;
1373 static int blob_count;
1374 static int tree_count;</code></pre>
1375 </div></div>
1376 <div class="paragraph"><p>Commits are handled by a different callback than other objects; let&#8217;s do that
1377 one first:</p></div>
1378 <div class="listingblock">
1379 <div class="content">
1380 <pre><code>static void walken_show_commit(struct commit *cmt, void *buf)
1381 {
1382         commit_count++;
1383 }</code></pre>
1384 </div></div>
1385 <div class="paragraph"><p>The <code>cmt</code> argument is fairly self-explanatory. But it&#8217;s worth mentioning that
1386 the <code>buf</code> argument is actually the context buffer that we can provide to the
1387 traversal calls - <code>show_data</code>, which we mentioned a moment ago.</p></div>
1388 <div class="paragraph"><p>Since we have the <code>struct commit</code> object, we can look at all the same parts that
1389 we looked at in our earlier commit-only walk. For the sake of this tutorial,
1390 though, we&#8217;ll just increment the commit counter and move on.</p></div>
1391 <div class="paragraph"><p>The callback for non-commits is a little different, as we&#8217;ll need to check
1392 which kind of object we&#8217;re dealing with:</p></div>
1393 <div class="listingblock">
1394 <div class="content">
1395 <pre><code>static void walken_show_object(struct object *obj, const char *str, void *buf)
1396 {
1397         switch (obj-&gt;type) {
1398         case OBJ_TREE:
1399                 tree_count++;
1400                 break;
1401         case OBJ_BLOB:
1402                 blob_count++;
1403                 break;
1404         case OBJ_TAG:
1405                 tag_count++;
1406                 break;
1407         case OBJ_COMMIT:
1408                 BUG("unexpected commit object in walken_show_object\n");
1409         default:
1410                 BUG("unexpected object type %s in walken_show_object\n",
1411                         type_name(obj-&gt;type));
1412         }
1413 }</code></pre>
1414 </div></div>
1415 <div class="paragraph"><p>Again, <code>obj</code> is fairly self-explanatory, and we can guess that <code>buf</code> is the same
1416 context pointer that <code>walken_show_commit()</code> receives: the <code>show_data</code> argument
1417 to <code>traverse_commit_list()</code> and <code>traverse_commit_list_filtered()</code>. Finally,
1418 <code>str</code> contains the name of the object, which ends up being something like
1419 <code>foo.txt</code> (blob), <code>bar/baz</code> (tree), or <code>v1.2.3</code> (tag).</p></div>
1420 <div class="paragraph"><p>To help assure us that we aren&#8217;t double-counting commits, we&#8217;ll include some
1421 complaining if a commit object is routed through our non-commit callback; we&#8217;ll
1422 also complain if we see an invalid object type. Since those two cases should be
1423 unreachable, and would only change in the event of a semantic change to the Git
1424 codebase, we complain by using <code>BUG()</code> - which is a signal to a developer that
1425 the change they made caused unintended consequences, and the rest of the
1426 codebase needs to be updated to understand that change. <code>BUG()</code> is not intended
1427 to be seen by the public, so it is not localized.</p></div>
1428 <div class="paragraph"><p>Our main object walk implementation is substantially different from our commit
1429 walk implementation, so let&#8217;s make a new function to perform the object walk. We
1430 can perform setup which is applicable to all objects here, too, to keep separate
1431 from setup which is applicable to commit-only walks.</p></div>
1432 <div class="paragraph"><p>We&#8217;ll start by enabling all types of objects in the <code>struct rev_info</code>.  We&#8217;ll
1433 also turn on <code>tree_blobs_in_commit_order</code>, which means that we will walk a
1434 commit&#8217;s tree and everything it points to immediately after we find each commit,
1435 as opposed to waiting for the end and walking through all trees after the commit
1436 history has been discovered. With the appropriate settings configured, we are
1437 ready to call <code>prepare_revision_walk()</code>.</p></div>
1438 <div class="listingblock">
1439 <div class="content">
1440 <pre><code>static void walken_object_walk(struct rev_info *rev)
1441 {
1442         rev-&gt;tree_objects = 1;
1443         rev-&gt;blob_objects = 1;
1444         rev-&gt;tag_objects = 1;
1445         rev-&gt;tree_blobs_in_commit_order = 1;
1446
1447         if (prepare_revision_walk(rev))
1448                 die(_("revision walk setup failed"));
1449
1450         commit_count = 0;
1451         tag_count = 0;
1452         blob_count = 0;
1453         tree_count = 0;</code></pre>
1454 </div></div>
1455 <div class="paragraph"><p>Let&#8217;s start by calling just the unfiltered walk and reporting our counts.
1456 Complete your implementation of <code>walken_object_walk()</code>.
1457 We&#8217;ll also need to include the <code>list-objects.h</code> header.</p></div>
1458 <div class="listingblock">
1459 <div class="content">
1460 <pre><code>#include "list-objects.h"
1461
1462 ...
1463
1464         traverse_commit_list(rev, walken_show_commit, walken_show_object, NULL);
1465
1466         printf("commits %d\nblobs %d\ntags %d\ntrees %d\n", commit_count,
1467                 blob_count, tag_count, tree_count);
1468 }</code></pre>
1469 </div></div>
1470 <div class="admonitionblock">
1471 <table><tr>
1472 <td class="icon">
1473 <div class="title">Note</div>
1474 </td>
1475 <td class="content">This output is intended to be machine-parsed. Therefore, we are not
1476 sending it to <code>trace_printf()</code>, and we are not localizing it - we need scripts
1477 to be able to count on the formatting to be exactly the way it is shown here.
1478 If we were intending this output to be read by humans, we would need to localize
1479 it with <code>_()</code>.</td>
1480 </tr></table>
1481 </div>
1482 <div class="paragraph"><p>Finally, we&#8217;ll ask <code>cmd_walken()</code> to use the object walk instead. Discussing
1483 command line options is out of scope for this tutorial, so we&#8217;ll just hardcode
1484 a branch we can change at compile time. Where you call <code>final_rev_info_setup()</code>
1485 and <code>walken_commit_walk()</code>, instead branch like so:</p></div>
1486 <div class="listingblock">
1487 <div class="content">
1488 <pre><code>        if (1) {
1489                 add_head_to_pending(&amp;rev);
1490                 walken_object_walk(&amp;rev);
1491         } else {
1492                 final_rev_info_setup(argc, argv, prefix, &amp;rev);
1493                 walken_commit_walk(&amp;rev);
1494         }</code></pre>
1495 </div></div>
1496 <div class="admonitionblock">
1497 <table><tr>
1498 <td class="icon">
1499 <div class="title">Note</div>
1500 </td>
1501 <td class="content">For simplicity, we&#8217;ve avoided all the filters and sorts we applied in
1502 <code>final_rev_info_setup()</code> and simply added <code>HEAD</code> to our pending queue. If you
1503 want, you can certainly use the filters we added before by moving
1504 <code>final_rev_info_setup()</code> out of the conditional and removing the call to
1505 <code>add_head_to_pending()</code>.</td>
1506 </tr></table>
1507 </div>
1508 <div class="paragraph"><p>Now we can try to run our command! It should take noticeably longer than the
1509 commit walk, but an examination of the output will give you an idea why. Your
1510 output should look similar to this example, but with different counts:</p></div>
1511 <div class="listingblock">
1512 <div class="content">
1513 <pre><code>Object walk completed. Found 55733 commits, 100274 blobs, 0 tags, and 104210 trees.</code></pre>
1514 </div></div>
1515 <div class="paragraph"><p>This makes sense. We have more trees than commits because the Git project has
1516 lots of subdirectories which can change, plus at least one tree per commit. We
1517 have no tags because we started on a commit (<code>HEAD</code>) and while tags can point to
1518 commits, commits can&#8217;t point to tags.</p></div>
1519 <div class="admonitionblock">
1520 <table><tr>
1521 <td class="icon">
1522 <div class="title">Note</div>
1523 </td>
1524 <td class="content">You will have different counts when you run this yourself! The number of
1525 objects grows along with the Git project.</td>
1526 </tr></table>
1527 </div>
1528 <div class="sect2">
1529 <h3 id="_adding_a_filter_2">Adding a Filter</h3>
1530 <div class="paragraph"><p>There are a handful of filters that we can apply to the object walk laid out in
1531 <code>Documentation/rev-list-options.txt</code>. These filters are typically useful for
1532 operations such as creating packfiles or performing a partial clone. They are
1533 defined in <code>list-objects-filter-options.h</code>. For the purposes of this tutorial we
1534 will use the "tree:1" filter, which causes the walk to omit all trees and blobs
1535 which are not directly referenced by commits reachable from the commit in
1536 <code>pending</code> when the walk begins. (<code>pending</code> is the list of objects which need to
1537 be traversed during a walk; you can imagine a breadth-first tree traversal to
1538 help understand. In our case, that means we omit trees and blobs not directly
1539 referenced by <code>HEAD</code> or <code>HEAD</code>'s history, because we begin the walk with only
1540 <code>HEAD</code> in the <code>pending</code> list.)</p></div>
1541 <div class="paragraph"><p>For now, we are not going to track the omitted objects, so we&#8217;ll replace those
1542 parameters with <code>NULL</code>. For the sake of simplicity, we&#8217;ll add a simple
1543 build-time branch to use our filter or not. Preface the line calling
1544 <code>traverse_commit_list()</code> with the following, which will remind us which kind of
1545 walk we&#8217;ve just performed:</p></div>
1546 <div class="listingblock">
1547 <div class="content">
1548 <pre><code>        if (0) {
1549                 /* Unfiltered: */
1550                 trace_printf(_("Unfiltered object walk.\n"));
1551         } else {
1552                 trace_printf(
1553                         _("Filtered object walk with filterspec 'tree:1'.\n"));
1554
1555                 parse_list_objects_filter(&amp;rev-&gt;filter, "tree:1");
1556         }
1557         traverse_commit_list(rev, walken_show_commit,
1558                              walken_show_object, NULL);</code></pre>
1559 </div></div>
1560 <div class="paragraph"><p>The <code>rev-&gt;filter</code> member is usually built directly from a command
1561 line argument, so the module provides an easy way to build one from a string.
1562 Even though we aren&#8217;t taking user input right now, we can still build one with
1563 a hardcoded string using <code>parse_list_objects_filter()</code>.</p></div>
1564 <div class="paragraph"><p>With the filter spec "tree:1", we are expecting to see <em>only</em> the root tree for
1565 each commit; therefore, the tree object count should be less than or equal to
1566 the number of commits. (For an example of why that&#8217;s true: <code>git commit --revert</code>
1567 points to the same tree object as its grandparent.)</p></div>
1568 </div>
1569 <div class="sect2">
1570 <h3 id="_counting_omitted_objects">Counting Omitted Objects</h3>
1571 <div class="paragraph"><p>We also have the capability to enumerate all objects which were omitted by a
1572 filter, like with <code>git log --filter=&lt;spec&gt; --filter-print-omitted</code>. To do this,
1573 change <code>traverse_commit_list()</code> to <code>traverse_commit_list_filtered()</code>, which is
1574 able to populate an <code>omitted</code> list.  Asking for this list of filtered objects
1575 may cause performance degradations, however, because in this case, despite
1576 filtering objects, the possibly much larger set of all reachable objects must
1577 be processed in order to populate that list.</p></div>
1578 <div class="paragraph"><p>First, add the <code>struct oidset</code> and related items we will use to iterate it:</p></div>
1579 <div class="listingblock">
1580 <div class="content">
1581 <pre><code>#include "oidset.h"
1582
1583 ...
1584
1585 static void walken_object_walk(
1586         ...
1587
1588         struct oidset omitted;
1589         struct oidset_iter oit;
1590         struct object_id *oid = NULL;
1591         int omitted_count = 0;
1592         oidset_init(&amp;omitted, 0);
1593
1594         ...</code></pre>
1595 </div></div>
1596 <div class="paragraph"><p>Replace the call to <code>traverse_commit_list()</code> with
1597 <code>traverse_commit_list_filtered()</code> and pass a pointer to the <code>omitted</code> oidset
1598 defined and initialized above:</p></div>
1599 <div class="listingblock">
1600 <div class="content">
1601 <pre><code>        ...
1602
1603                 traverse_commit_list_filtered(rev,
1604                         walken_show_commit, walken_show_object, NULL, &amp;omitted);
1605
1606         ...</code></pre>
1607 </div></div>
1608 <div class="paragraph"><p>Then, after your traversal, the <code>oidset</code> traversal is pretty straightforward.
1609 Count all the objects within and modify the print statement:</p></div>
1610 <div class="listingblock">
1611 <div class="content">
1612 <pre><code>        /* Count the omitted objects. */
1613         oidset_iter_init(&amp;omitted, &amp;oit);
1614
1615         while ((oid = oidset_iter_next(&amp;oit)))
1616                 omitted_count++;
1617
1618         printf("commits %d\nblobs %d\ntags %d\ntrees %d\nomitted %d\n",
1619                 commit_count, blob_count, tag_count, tree_count, omitted_count);</code></pre>
1620 </div></div>
1621 <div class="paragraph"><p>By running your walk with and without the filter, you should find that the total
1622 object count in each case is identical. You can also time each invocation of
1623 the <code>walken</code> subcommand, with and without <code>omitted</code> being passed in, to confirm
1624 to yourself the runtime impact of tracking all omitted objects.</p></div>
1625 </div>
1626 <div class="sect2">
1627 <h3 id="_changing_the_order_2">Changing the Order</h3>
1628 <div class="paragraph"><p>Finally, let&#8217;s demonstrate that you can also reorder walks of all objects, not
1629 just walks of commits. First, we&#8217;ll make our handlers chattier - modify
1630 <code>walken_show_commit()</code> and <code>walken_show_object()</code> to print the object as they
1631 go:</p></div>
1632 <div class="listingblock">
1633 <div class="content">
1634 <pre><code>#include "hex.h"
1635
1636 ...
1637
1638 static void walken_show_commit(struct commit *cmt, void *buf)
1639 {
1640         trace_printf("commit: %s\n", oid_to_hex(&amp;cmt-&gt;object.oid));
1641         commit_count++;
1642 }
1643
1644 static void walken_show_object(struct object *obj, const char *str, void *buf)
1645 {
1646         trace_printf("%s: %s\n", type_name(obj-&gt;type), oid_to_hex(&amp;obj-&gt;oid));
1647
1648         ...
1649 }</code></pre>
1650 </div></div>
1651 <div class="admonitionblock">
1652 <table><tr>
1653 <td class="icon">
1654 <div class="title">Note</div>
1655 </td>
1656 <td class="content">Since we will be examining this output directly as humans, we&#8217;ll use
1657 <code>trace_printf()</code> here. Additionally, since this change introduces a significant
1658 number of printed lines, using <code>trace_printf()</code> will allow us to easily silence
1659 those lines without having to recompile.</td>
1660 </tr></table>
1661 </div>
1662 <div class="paragraph"><p>(Leave the counter increment logic in place.)</p></div>
1663 <div class="paragraph"><p>With only that change, run again (but save yourself some scrollback):</p></div>
1664 <div class="listingblock">
1665 <div class="content">
1666 <pre><code>$ GIT_TRACE=1 ./bin-wrappers/git walken 2&gt;&amp;1 | head -n 10</code></pre>
1667 </div></div>
1668 <div class="paragraph"><p>Take a look at the top commit with <code>git show</code> and the object ID you printed; it
1669 should be the same as the output of <code>git show HEAD</code>.</p></div>
1670 <div class="paragraph"><p>Next, let&#8217;s change a setting on our <code>struct rev_info</code> within
1671 <code>walken_object_walk()</code>. Find where you&#8217;re changing the other settings on <code>rev</code>,
1672 such as <code>rev-&gt;tree_objects</code> and <code>rev-&gt;tree_blobs_in_commit_order</code>, and add the
1673 <code>reverse</code> setting at the bottom:</p></div>
1674 <div class="listingblock">
1675 <div class="content">
1676 <pre><code>        ...
1677
1678         rev-&gt;tree_objects = 1;
1679         rev-&gt;blob_objects = 1;
1680         rev-&gt;tag_objects = 1;
1681         rev-&gt;tree_blobs_in_commit_order = 1;
1682         rev-&gt;reverse = 1;
1683
1684         ...</code></pre>
1685 </div></div>
1686 <div class="paragraph"><p>Now, run again, but this time, let&#8217;s grab the last handful of objects instead
1687 of the first handful:</p></div>
1688 <div class="listingblock">
1689 <div class="content">
1690 <pre><code>$ make
1691 $ GIT_TRACE=1 ./bin-wrappers/git walken 2&gt;&amp;1 | tail -n 10</code></pre>
1692 </div></div>
1693 <div class="paragraph"><p>The last commit object given should have the same OID as the one we saw at the
1694 top before, and running <code>git show &lt;oid&gt;</code> with that OID should give you again
1695 the same results as <code>git show HEAD</code>. Furthermore, if you run and examine the
1696 first ten lines again (with <code>head</code> instead of <code>tail</code> like we did before applying
1697 the <code>reverse</code> setting), you should see that now the first commit printed is the
1698 initial commit, <code>e83c5163</code>.</p></div>
1699 </div>
1700 </div>
1701 </div>
1702 <div class="sect1">
1703 <h2 id="_wrapping_up">Wrapping Up</h2>
1704 <div class="sectionbody">
1705 <div class="paragraph"><p>Let&#8217;s review. In this tutorial, we:</p></div>
1706 <div class="ulist"><ul>
1707 <li>
1708 <p>
1709 Built a commit walk from the ground up
1710 </p>
1711 </li>
1712 <li>
1713 <p>
1714 Enabled a grep filter for that commit walk
1715 </p>
1716 </li>
1717 <li>
1718 <p>
1719 Changed the sort order of that filtered commit walk
1720 </p>
1721 </li>
1722 <li>
1723 <p>
1724 Built an object walk (tags, commits, trees, and blobs) from the ground up
1725 </p>
1726 </li>
1727 <li>
1728 <p>
1729 Learned how to add a filter-spec to an object walk
1730 </p>
1731 </li>
1732 <li>
1733 <p>
1734 Changed the display order of the filtered object walk
1735 </p>
1736 </li>
1737 </ul></div>
1738 </div>
1739 </div>
1740 </div>
1741 <div id="footnotes"><hr /></div>
1742 <div id="footer">
1743 <div id="footer-text">
1744 Last updated
1745  2024-04-09 14:45:01 PDT
1746 </div>
1747 </div>
1748 </body>
1749 </html>