CINXE.COM

<!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?1718759055581"> <link rel="stylesheet" href="/css/nav.css?1718759055581"> <link rel="stylesheet" href="/css/style.css?1718759055581"> <link rel="stylesheet" href="/css/prismjs@1.24-themes-prism.css"> <title>IPLD ♦ </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="/design">design</a></li> <li><a href="/design/libraries">libraries</a></li> <li><a href="/design/libraries/nodes-and-kinds/">nodes-and-kinds</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> <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/fixtures/">DAG-CBOR Test Fixtures</a><ul> <li> <a href="/specs/codecs/dag-cbor/fixtures/cross-codec/">cross-codec</a></li></ul></li> <li> <a href="/specs/codecs/dag-cbor/spec/">Spec</a></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/fixtures/">fixtures</a></li> <li> <a href="/specs/codecs/dag-jose/spec/">Spec</a></li></ul></li> <li> <a href="/specs/codecs/dag-json/">DAG-JSON</a><ul> <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> <li> <a href="/specs/codecs/dag-json/spec/">Spec</a></li></ul></li> <li> <a href="/specs/codecs/dag-pb/">DAG-PB</a><ul> <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> <li> <a href="/specs/codecs/dag-pb/spec/">Spec</a></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/fixture/">HashMap (HAMT) Test Fixtures</a><ul> <li> <a href="/specs/advanced-data-layouts/hamt/fixture/alice-words/">alice-words</a></li></ul></li> <li> <a href="/specs/advanced-data-layouts/hamt/spec/">spec</a></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/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 class="active-page"> <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>Nodes and Kinds</h1> <p><strong>Preface: purpose of this document:</strong></p> <p>This document is intended for developers of new (or renovating) IPLD libraries. It contains design suggestions based on the experience of building (and rebuilding) IPLD libraries in various languages, and reflecting on the lessons learned. It also contains both notes on practical limitations we've found for implementations, and reflections on how to express things clearly within the type systems of the host language a library is implemented in (whatever that may be).</p> <p><strong>Preface: limitations of this document:</strong></p> <p>Since this document is aimed at <em>new libraries</em>, it's also implicitly expecting that the new library might be in a <em>new language</em>. We can't presume to know precisely what that language will enable or encourage! Therefore, there will be limits to how transferable the advice in this document may be. We do expect that the best way to express IPLD concepts may vary based on the language a library is created in. We accept this and try to write this document anyway, and make it as useful as it can be.</p> <p>These guidelines are written with particular attention to the limitations that are typical to strongly typed languages. (Some of the phrasing used reflect this -- we refer to "types", "enumerations", "interfaces", "packages", etc. However, these concepts can still translate even to languages with varying amounts of compile-time type checking, and indeed even to those with none. While the concepts are certainly not identical across all languages, we hope that they're close enough to be meaningful to a thoughtful reader. If you would like some primer on these concepts, we also maintain a page on "<a href="/design/concepts/type-theory-glossary/">Type Theory Glossary</a>" which is language-agnostic.)</p> <p>We expect that common concepts for IPLD libraries will emerge across many languages, and hope that some vocabulary for these concepts is something we can share. Loosely and untyped languages may need to interpret these guidelines appropriately while extracting the key concepts; but even among languages with stricter concepts of compile-time type checking, the meaning of "interface" can vary greatly -- <em>all</em> readers will need to be ready to use their best judgement.</p> <hr> <h1>Cornerstone Types</h1> <p>Your IPLD library should have two cornerstone types:</p> <ol> <li><code>Node</code>;</li> <li><code>Kind</code>.</li> </ol> <p><code>Node</code> should be an interface -- the membership should be open (aka, it should be possible for other packages to implement it).</p> <p><code>Kind</code> should be an enumeration -- a fixed set of named members, which should not be extendable.</p> <h2 id="kind" tabindex="-1"><a class="header-anchor" href="#kind">Kind</a></h2> <p><code>Kind</code> maps very directly onto the definition of <a href="/docs/data-model/kinds/">Data Model Kinds</a>.</p> <p><code>Kind</code> does not include the Schema layer's concept of "struct", etc.</p> <p><code>Kind</code> must be an enum, <strong>and not a sum type</strong>. Attempting to implement kind as a sum type conflates it with <code>Node</code>. (This may be tempting to try to combine <code>Kind</code> and <code>Node</code> into a single sum type definition if you're only looking at the Data Model layer, but it is a mistake: both Schema types and Advanced Layouts require the ability to add more implementations of <code>Node</code>, so this conflation will cause cataclysmic problems and force a painful refactor as soon as you get to implementing those systems. See the <a href="#different-implementors-of-node">different implementors of Node</a> section, later in this document, for more information on this.)</p> <h2 id="node" tabindex="-1"><a class="header-anchor" href="#node">Node</a></h2> <p><code>Node</code> is a monomorphized interface for handling data -- in other words, we make all data look and act like a <code>Node</code>, so that we can write all of our functions against the <code>Node</code> interface, and have that work for any sort of data.</p> <p><code>Node</code> has functions for examining any of the <a href="/docs/data-model/kinds/">Data Model Kinds</a>. For example, this means <code>Node</code> must be able to do a key lookup for a map kind, provide an iterator for a list kind, or be convertible to a primitive if it's a integer kind.</p> <p><code>Node</code> is generally implemented by making an interface with the superset of all these methods needed for the various kinds of data. Some programming languages may also have a pattern-matching faculty which may make this nicer; feel free to use it (but mind the caveats issued in the <a href="#kind">Kind</a> section above, and the <a href="#different-implementors-of-node">different implementors of Node</a> section below: the membership of <code>Node</code> must remain <em>open</em>; you do <em>not</em> want to use a sum type with a closed list of concrete members here, or it will cause other roadblocks later that <em>will</em> force a redesign). For languages where this is most straightforwardly implemented by a single interface containing the superset of all necessary methods, many of the methods will error if the <code>Node</code> refers to information of the wrong kind for that method; this is fine.</p> <p><code>Node</code> should be clear about what sets of methods are valid for acting on it. Typically, this is done by a <code>Node.Kind()</code> method, which should return a member of the <a href="#kind">Kind</a> enum. This information is useful for anyone writing functions which use the <code>Node</code> interface, because it's much more pleasant (and fast) to check the Kind and know which methods can be expected to work than it is to have to probe every method individually for failure. (Again, programming languages with pattern-matching faculties may find a cleverer way for their compiler and type system to support this.)</p> <h3 id="different-implementors-of-node" tabindex="-1"><a class="header-anchor" href="#different-implementors-of-node">different implementors of Node</a></h3> <p>Though the methods on the <code>Node</code> interface are defined as those necessary for examining data of the <a href="/docs/data-model/kinds/">Data Model Kinds</a>, <strong><code>Node</code> is not only implemented by the Data Model</strong>:</p> <ul> <li>Yes, <code>Node</code> is implemented by types that just hold basic Data Model info;</li> <li><code>Node</code> is also implemented by <a href="/docs/advanced-data-layouts/">Advanced Data Layouts</a> --- <ul> <li>consider a HAMT that spans many separately-serialized chunks of data; it should still be usable as if it's a regular map.</li> </ul> </li> <li><code>Node</code> is also implemented by <a href="/docs/schemas/">Schema-typed Nodes</a> -- <ul> <li>Both if implemented by a single implementation that evaluates rules at runtime (so, finite count of implementing types and known at core library compile time)...</li> <li>or if handled by codegen/macros (unknown count / open set of implementors of <code>Node</code>; not known at core library compile time; may be created in other packages that import the core, rather than core importing them!).</li> </ul> </li> </ul> <p>Even further, some libraries may choose to make even more various implementations of <code>Node</code> for optimizing performance of specific tasks: for example, a <code>Node</code> which implements basic Data Model "map" semantics, but using some internal algorithm for memory layout which is known to be efficient for certain workloads; or for another example, a <code>Node</code> which is particularly efficient for handling data of one particular serialization codec, and keeps a lazy-loading skip-tree over the serialized bytes. Clearly, neither of these should be the default implementation a library uses, but clearly, both of them should be able to be used transparently,</p> <p>With all seven (?! indeed, <em>seven</em>) of these different stories, we can consider it conclusive that the <code>Node</code> interface should be ready to support many, many diverse implementors.</p> <h3 id="a-default-implementation-of-node" tabindex="-1"><a class="header-anchor" href="#a-default-implementation-of-node">a default implementation of Node</a></h3> <p>As an IPLD library author, you may be tempted to make a single, "default" implementation of <code>Node</code>.</p> <p>Feel free to do so; but be cautious of giving it special privileges. Try implementing it in a separate package from your core interfaces: this will be a good exercise to make sure other implementations can later do the same. (Since in the order of things you'll do when implementing a new IPLD library, creating this basic default node implementation is likely quite early, going about it in such a way that it forces design choices you'll need later anyway will save you from potentially discovering the need for some costly refactors later!)</p> <h2 id="nodes-vs-nodebuilders" tabindex="-1"><a class="header-anchor" href="#nodes-vs-nodebuilders">Nodes vs NodeBuilders</a></h2> <p>If you choose to pursue a distinction between mutable and immutable data in the design of your library, it may be useful to create two separate interfaces for each phase of the data's lifecycle. These might be called "Node" (for the immutable data) and "NodeBuilder" (for the mutating/building phase of the data's life).</p> <p>It is not necessary to have distinct interfaces for this; a library can also opt to have a mutable concept of "node". Immutable interfaces can be particularly well-suited to IPLD data, though; it's worth considering them.</p> <h2 id="higher-level-functions" tabindex="-1"><a class="header-anchor" href="#higher-level-functions">Higher level functions</a></h2> <p>Almost all features should be implemented to take <code>Node</code> arguments, and return <code>Node</code> values.</p> <p>Traversals and walks can be implemented in this way: e.g. <code>function walk(start Node, visitorFn func(visited Node))</code>.</p> <p>Selectors can be implemented in this way. (Continue with the idea above for traversals.)</p> <p>Transformations can be implemented in this way. (Continue with the idea above for traversals.)</p> <p>Codecs themselves can be implemented this way: marshalling is a traverse over nodes, so <code>func marshal(obj Node) -> bytes</code>, and unmarshalling is something like <code>func unmarshal(bytes, NodeBuilder) -> Node</code>.</p> <p>(Note that if your library has a <code>Node</code>/<code>NodeBuilder</code> split for immutability purposes, then of course any operation that builds new nodes, such as transformations or codecs during unmarshalling, will have a <code>NodeBuilder</code> parameter. If your library has a mutable <code>Node</code>, these function signatures might appear differently.)</p> <p>By defining all these functions in terms of <code>Node</code>, they can be used the same in any of the various contexts described in the <a href="#different-implementors-of-node">different implementors of Node</a> section:</p> <ul> <li>traversals/selectors/transforms/etc work over various codecs (trivially, by transitive property).</li> <li>traversals/selectors/transforms/etc work regardless of in-memory layouts that may vary per <code>Node</code> implementation</li> <li>traversals/selectors/transforms/etc work transparently over ADLs!</li> <li>traversals/selectors/transforms/etc work transparently over schemas!</li> </ul> <p>It is also useful to note that by implementing these features over the <code>Node</code> interface, rather than <em>in</em> the <code>Node</code> interface, it becomes much more possible to implement various kinds of e.g. traversal library (perhaps you'll discover two different ways to go about it, one with better ergonomics, and one with better performance?); and it also requires much less code per <code>Node</code> implementation if things like traversals are implemented from the outside.</p> </div> </main> </body> </html>