CINXE.COM
IPLD ♦ Traversal
<!doctype html> <html lang="en"> <head> <meta charset="utf-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <link rel="stylesheet" href="/css/layout.css?1738557326388"> <link rel="stylesheet" href="/css/nav.css?1738557326388"> <link rel="stylesheet" href="/css/style.css?1738557326388"> <link rel="stylesheet" href="/css/prismjs@1.24-themes-prism.css"> <title>IPLD ♦ Traversal</title> </head> <body> <header> <div class="sidebar-button" onclick="document.getElementById('sidebar').classList.toggle('sidebar-open')"> <svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"> <path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path> </svg> </div> <a href="/" class="logo">IPLD</a> <aside id=breadcrumbs> <ul> <li><a href="/docs">docs</a></li> <li><a href="/docs/data-model">data-model</a></li> <li><a href="/docs/data-model/traversal/">traversal</a></li> </ul> </aside> </header> <aside id=sidebar> <nav> <ul> <li> <a href="/docs/">Docs</a><ul> <li> <a href="/docs/intro/">Intro</a><ul> <li> <a href="/docs/intro/hello-world/">Hello, World</a></li> <li> <a href="/docs/intro/primer/">The Brief Primer</a></li> <li> <a href="/docs/intro/ecosystem/">InterPlanetary Ecosystem Overview</a></li> <li> <a href="/docs/intro/community/">Finding Community</a></li></ul></li> <li> <a href="/docs/motivation/">Motivation</a><ul> <li> <a href="/docs/motivation/benefits-of-content-addressing/">Benefits of Content Addressing</a></li> <li> <a href="/docs/motivation/data-to-data-structures/">From Data to Data Structures</a></li></ul></li> <li> <a href="/docs/codecs/">Codecs</a><ul> <li> <a href="/docs/codecs/known/">Known Codecs</a><ul> <li> <a href="/docs/codecs/known/dag-cbor/">DAG-CBOR</a></li> <li> <a href="/docs/codecs/known/dag-json/">DAG-JSON</a></li> <li> <a href="/docs/codecs/known/dag-pb/">DAG-PB</a></li></ul></li></ul></li> <li> <a href="/docs/data-model/">Data Model</a><ul> <li> <a href="/docs/data-model/node/">Nodes</a></li> <li> <a href="/docs/data-model/kinds/">Kinds</a></li> <li> <a href="/docs/data-model/pathing/">Pathing</a></li> <li class="active-page"> <a href="/docs/data-model/traversal/">Traversal</a></li></ul></li> <li> <a href="/docs/advanced-data-layouts/">Advanced Data Layouts</a><ul> <li> <a href="/docs/advanced-data-layouts/intro/">Intro to ADLs</a></li> <li> <a href="/docs/advanced-data-layouts/naming/">ADL Naming</a></li> <li> <a href="/docs/advanced-data-layouts/signalling/">Signalling ADLs</a></li> <li> <a href="/docs/advanced-data-layouts/dynamic-loading/">Dynamic Loading</a></li> <li> <a href="/docs/advanced-data-layouts/known/">Known ADLs</a></li></ul></li> <li> <a href="/docs/schemas/">Schemas</a><ul> <li> <a href="/docs/schemas/intro/">Introduction</a><ul> <li> <a href="/docs/schemas/intro/compare/">compare</a></li> <li> <a href="/docs/schemas/intro/goals/">Goals</a></li> <li> <a href="/docs/schemas/intro/feature-summary/">Feature Summary</a></li></ul></li> <li> <a href="/docs/schemas/features/">Features</a><ul> <li> <a href="/docs/schemas/features/typekinds/">Type Kinds</a></li> <li> <a href="/docs/schemas/features/representation-strategies/">Representation Strategies</a></li> <li> <a href="/docs/schemas/features/links/">Links</a></li> <li> <a href="/docs/schemas/features/indicating-adls/">Using ADLs in Schemas</a></li></ul></li> <li> <a href="/docs/schemas/using/">Using Wisely</a><ul> <li> <a href="/docs/schemas/using/authoring-guide/">Authoring Guide</a></li> <li> <a href="/docs/schemas/using/migrations/">Migrations</a></li></ul></li></ul></li> <li> <a href="/docs/synthesis/">Synthesis</a><ul> <li> <a href="/docs/synthesis/gtd/">Getting Things Done</a></li> <li> <a href="/docs/synthesis/building-in-alignment/">Building in Alignment</a></li> <li> <a href="/docs/synthesis/how-ipfs-web-gateways-work/">How IPFS Web Gateways Work</a></li> <li> <a href="/docs/synthesis/encryption/">Working With Encryption</a></li></ul></li></ul></li> <li> <a href="/specs/">Specs</a><ul> <li> <a href="/specs/about/">About the Specifications</a></li> <li> <a href="/specs/codecs/">Codecs</a><ul> <li> <a href="/specs/codecs/dag-cbor/">DAG-CBOR</a><ul> <li> <a href="/specs/codecs/dag-cbor/spec/">Spec</a></li> <li> <a href="/specs/codecs/dag-cbor/fixtures/">DAG-CBOR Test Fixtures</a><ul> <li> <a href="/specs/codecs/dag-cbor/fixtures/cross-codec/">cross-codec</a></li></ul></li></ul></li> <li> <a href="/specs/codecs/dag-cosmos/">DAG-COSMOS</a><ul> <li> <a href="/specs/codecs/dag-cosmos/basic_types/">basic_types</a></li> <li> <a href="/specs/codecs/dag-cosmos/cosmos_state/">cosmos_state</a></li> <li> <a href="/specs/codecs/dag-cosmos/crypto_types/">crypto_types</a></li> <li> <a href="/specs/codecs/dag-cosmos/tendermint_chain/">tendermint_chain</a></li> <li> <a href="/specs/codecs/dag-cosmos/typed_protobuf/">typed_protobuf</a></li></ul></li> <li> <a href="/specs/codecs/dag-eth/">DAG-ETH</a><ul> <li> <a href="/specs/codecs/dag-eth/basic_types/">basic_types</a></li> <li> <a href="/specs/codecs/dag-eth/chain/">chain</a></li> <li> <a href="/specs/codecs/dag-eth/convenience_types/">convenience_types</a></li> <li> <a href="/specs/codecs/dag-eth/state/">state</a></li></ul></li> <li> <a href="/specs/codecs/dag-jose/">DAG-JOSE</a><ul> <li> <a href="/specs/codecs/dag-jose/spec/">Spec</a></li> <li> <a href="/specs/codecs/dag-jose/fixtures/">fixtures</a></li></ul></li> <li> <a href="/specs/codecs/dag-json/">DAG-JSON</a><ul> <li> <a href="/specs/codecs/dag-json/spec/">Spec</a></li> <li> <a href="/specs/codecs/dag-json/fixtures/">DAG-JSON Test Fixtures</a><ul> <li> <a href="/specs/codecs/dag-json/fixtures/cross-codec/">cross-codec</a></li></ul></li></ul></li> <li> <a href="/specs/codecs/dag-pb/">DAG-PB</a><ul> <li> <a href="/specs/codecs/dag-pb/spec/">Spec</a></li> <li> <a href="/specs/codecs/dag-pb/fixtures/">DAG-PB Test Fixtures</a><ul> <li> <a href="/specs/codecs/dag-pb/fixtures/cross-codec/">cross-codec</a></li></ul></li></ul></li></ul></li> <li> <a href="/specs/advanced-data-layouts/">Advanced Data Layouts</a><ul> <li> <a href="/specs/advanced-data-layouts/fbl/">FBL ADL</a><ul> <li> <a href="/specs/advanced-data-layouts/fbl/spec/">spec</a></li></ul></li> <li> <a href="/specs/advanced-data-layouts/hamt/">HAMT ADL</a><ul> <li> <a href="/specs/advanced-data-layouts/hamt/spec/">spec</a></li> <li> <a href="/specs/advanced-data-layouts/hamt/fixture/">HashMap (HAMT) Test Fixtures</a><ul> <li> <a href="/specs/advanced-data-layouts/hamt/fixture/alice-words/">alice-words</a></li></ul></li></ul></li></ul></li> <li> <a href="/specs/schemas/">Schemas</a><ul> <li> <a href="/specs/schemas/prelude/">prelude</a></li></ul></li> <li> <a href="/specs/transport/">Transports</a><ul> <li> <a href="/specs/transport/car/">CAR</a><ul> <li> <a href="/specs/transport/car/carv1/">CARv1 Specification</a></li> <li> <a href="/specs/transport/car/carv2/">CARv2 Specification</a></li> <li> <a href="/specs/transport/car/fixture/">CAR Test Fixtures</a><ul> <li> <a href="/specs/transport/car/fixture/carv1-basic/">carv1-basic</a></li> <li> <a href="/specs/transport/car/fixture/carv2-basic/">carv2-basic</a></li></ul></li></ul></li> <li> <a href="/specs/transport/graphsync/">Graphsync</a><ul> <li> <a href="/specs/transport/graphsync/known_extensions/">known_extensions</a></li></ul></li> <li> <a href="/specs/transport/trustless-pathing/">Trustless Pathing</a><ul> <li> <a href="/specs/transport/trustless-pathing/fixtures/">Trustless Pathing Fixtures</a><ul> <li> <a href="/specs/transport/trustless-pathing/fixtures/unixfs_20m_variety/">unixfs_20m_variety</a></li></ul></li></ul></li></ul></li> <li> <a href="/specs/selectors/">Selectors</a><ul> <li> <a href="/specs/selectors/fixtures/">fixtures</a><ul> <li> <a href="/specs/selectors/fixtures/selector-fixtures-1/">selector-fixtures-1</a></li> <li> <a href="/specs/selectors/fixtures/selector-fixtures-adl/">selector-fixtures-adl</a></li> <li> <a href="/specs/selectors/fixtures/selector-fixtures-recursion/">selector-fixtures-recursion</a></li></ul></li></ul></li> <li> <a href="/specs/patch/">Patch</a><ul> <li> <a href="/specs/patch/fixtures/">IPLD Patch Test Fixtures</a><ul> <li> <a href="/specs/patch/fixtures/fixtures-1/">fixtures-1</a></li></ul></li></ul></li></ul></li> <li> <a href="/libraries/">Libraries</a><ul> <li> <a href="/libraries/golang/">Golang</a></li> <li> <a href="/libraries/java/">Java</a></li> <li> <a href="/libraries/javascript/">JavaScript</a></li> <li> <a href="/libraries/python/">Python</a></li> <li> <a href="/libraries/rust/">Rust</a></li></ul></li> <li> <a href="/design/">Design</a><ul> <li> <a href="/design/objectives/">Objectives</a></li> <li> <a href="/design/concepts/">Concepts</a><ul> <li> <a href="/design/concepts/type-theory-glossary/">type-theory-glossary</a></li></ul></li> <li> <a href="/design/libraries/">Libraries</a><ul> <li> <a href="/design/libraries/nodes-and-kinds/">nodes-and-kinds</a></li></ul></li> <li> <a href="/design/tricky-choices/">Tricky Choices</a><ul> <li> <a href="/design/tricky-choices/dag-pb-forms-impl-and-use/">dag-pb-forms-impl-and-use</a></li> <li> <a href="/design/tricky-choices/map-key-domain/">map-key-domain</a></li> <li> <a href="/design/tricky-choices/numeric-domain/">numeric-domain</a></li> <li> <a href="/design/tricky-choices/ordering/">ordering</a></li> <li> <a href="/design/tricky-choices/string-domain/">string-domain</a></li></ul></li> <li> <a href="/design/open-research/">Open Research</a><ul> <li> <a href="/design/open-research/ADL-autoexecution/">ADL autoexecution</a></li></ul></li></ul></li> <li> <a href="/tools/">Tools</a></li> <li> <a href="/glossary/">Glossary</a></li> <li> <a href="/media/">Media</a></li> <li> <a href="/FAQ/">FAQ</a></li></ul> </nav> </aside> <main> <div class=content> <h1>Traversal in IPLD</h1> <p>"Traversal" refers to the act of walking over IPLD data.</p> <p>Traversing a <a href="/docs/data-model/kinds/#map-kind">map</a> means iterating over its keys and values... and possibly, traversing over those values, recursively.</p> <p>Traversing a <a href="/docs/data-model/kinds/#list-kind">list</a> means iterating over its values... and possibly, traversing over those values, recursively.</p> <p>Traversing other kinds of nodes that aren't recursive just means looking at that node.</p> <p>Traversing a <a href="/docs/data-model/kinds/#link-kind">link</a> can mean either examining that link, or, <em>loading</em> it, resulting in a whole new bunch of nodes which can be traversed.</p> <h2 id="traversal-is-universal" tabindex="-1"><a class="header-anchor" href="#traversal-is-universal">Traversal is Universal</a></h2> <p>Any IPLD data can be traversed. Once data has been loaded into the <a href="..">Data Model</a> by a <a href="/glossary/#codec">codec</a>, the Data Model means we know how to look at the data. Since being in the Data Model means we know what <em><a href="/docs/data-model/kinds/">kind</a></em> of data it is, it means we know how to iterate over it... and that means we know how to traverse it, as well as all of its neighboring data.</p> <h2 id="traversal-order" tabindex="-1"><a class="header-anchor" href="#traversal-order">Traversal Order</a></h2> <p>Traversal order generally has a stable definition.</p> <p>However, exactly what that order is may vary based on what kind of traversal you're doing -- if you're using anything to direct the traversal, or if you're just walking the whole data graph plainly.</p> <p>See also the extended doc on ordering in IPLD in general: <a href="/design/tricky-choices/ordering/">Tricky Design Choices: Ordering</a></p> <h2 id="kinds-of-traversal" tabindex="-1"><a class="header-anchor" href="#kinds-of-traversal">Kinds of Traversal</a></h2> <h3 id="total-traversal" tabindex="-1"><a class="header-anchor" href="#total-traversal">Total Traversal</a></h3> <p>"Total traversal" means walking a graph of data in its natural order. Iterating over a map, in the order its iterator yields entries; iterating over lists, in the order their iterator yields entries; etc.</p> <p>A total traversal is differentiated from a <a href="#directed-traversal">Directed Traversal</a>.</p> <h3 id="directed-traversal" tabindex="-1"><a class="header-anchor" href="#directed-traversal">Directed Traversal</a></h3> <p>"Directed traversal" means walking a graph of data while holding some specific directions about how to do it. A directed traversal might visit only some of a graph, or might visit data in a specific order, based on its specific directions.</p> <p>A directed traversal is differentiated from a <a href="#total-traversal">Total Traversal</a>.</p> <p>Directed traversal is a general term and can refer to any kind of traversal one does with custom code; there are also some standardized features that many IPLD libraries will provide which perform directed traversals, such as <a href="#traversal-by-selector">Selectors</a></p> <h3 id="traversal-by-selector" tabindex="-1"><a class="header-anchor" href="#traversal-by-selector">Traversal by Selector</a></h3> <p>IPLD Selectors are a specific mechanism for declaratively describing how to traverse over an IPLD <a href="/glossary/#dag">dag</a>, as well as how to mark and select some of the nodes reached during that traversal.</p> <p>You can think of Selectors as roughly like regexps for textual data, but made for IPLD graphs.</p> <p>Selectors are a form of <a href="#directed-traversal">directed traversal</a>. Accordingly, some selectors can cause the traversal to proceed in a different order than a plain total traversal on the same data would have (as well as, of course, traversing much <em>less</em> data than a plain total traversal would have -- that's the point of them, after all).</p> <p>For an example of how the directed traversal order in selectors may differ from the norm, consider the "fields" selector: in this selector clause, the selector itself has an (ordered!) map of the fields the selector wants to focus on, and it's that ordering which will drive the selection over the map that the clause is applied on, rather than the ordering of the data in the map it's applied on. (This is important because it remains true even for arbitrarily sized maps -- remember, considering <a href="/docs/advanced-data-layouts/">ADLs</a>, the selector could be being applied on a huge map, with internal sharding... something potentially far too large to want to iterate on, if we have instructions that let us avoid it!)</p> <p>See more about Selectors in the <a href="/specs/selectors/">Selector specs</a>.</p> <h2 id="traversal-in-various-ipld-implementations" tabindex="-1"><a class="header-anchor" href="#traversal-in-various-ipld-implementations">Traversal in various IPLD implementations</a></h2> <ul> <li>in Golang: <ul> <li>in <a href="https://github.com/ipld/go-ipld-prime">go-ipld-prime</a>: <ul> <li>the entire <a href="https://godoc.org/github.com/ipld/go-ipld-prime/traversal">traversal (godoc)</a> package</li> </ul> </li> </ul> </li> </ul> <div class="callout callout-todo"> <ul> <li>Your language here, please! :D</li> </ul> </div> </div> </main> </body> </html>