IPLD Selector

[jbenet]

It is ideal to have a path notation (for use in bitswap and other tools) that allows expressing ranges of objects and queries.

• Would be nice to use globbing <path>/*/**
• Would be nice to use git revs <path>~10 <path>~10:<path>~5
• Would be nice to use patterns <path>/foo*/*bar*
• Would be crazy to use regex <path>/[a-z]+ ...
• May we should just use XPath.

links:

• https://github.com/ipfs/ipfs/issues/8#issuecomment-66861007
• https://gist.github.com/jbenet/09618faa84388a58a588
• https://www.kernel.org/pub/software/scm/git/docs/gitrevisions.html
• http://en.wikipedia.org/wiki/XPath
• (WIP) records + merkledag specs specs#7 (comment)

[ion1]

It might be good to design the path traversals as an abstract syntax tree first. They are easy to create and manipulate in programming languages (without invoking a parser in runtime) and they are what binary (de)serializers input/output.

When the perfect AST structure is established, that would be a good time to specify a corresponding regexp/glob/XPath-like notation. Since the AST is already set in stone, no character that is ordinary now and does not need to be escaped in path components will become special later and silently break existing expressions.

(Alternatively, specify a “multitraversal” notation which indicates its version.)

Here’s pseudocode for the AST data types for some of the traversals that would be nice to have. This should map to actual code in any modern programming language rather trivially.

data Pattern = Pattern Reference [Traversal]

data Traversal = Glob [Glob]
               | RecursiveStar
               | Count Natural [Traversal]
               | CountMin Natural [Traversal]
               | Dereference Pattern

data Glob = Literal String
          | Star

Some pseudocode expressions using the data types defined above:

Pattern ref []

Pattern ref [Glob [Star]]

Pattern ref [RecursiveStar]

Pattern ref [Glob [Star], "bar", RecursiveStar]

Pattern ref [Glob ["foo", Star], Glob [Star, "bar", Star]]

Pattern ref [Count 10 ["parent"], "foo"]

Pattern ref ["movie.mp4", CountMin 1 ["chunks", "0"], Glob [Star]]

Pattern ref1 [Dereference (Pattern ref2 ["followers", "20", "username"])]

[jbenet]

more desired expressions:

• $ref/* - one level under $ref
• $ref/** - everything under $ref
• $ref/parent/parent/txn/10 - specific nodes
• $ref/movie.mp4/(chunks/0)+/* - selects a left-leaning subgraph
• $ref1/$($ref2/followers/20/username) - sub-expressions-- uses product of one selection in another

[jbenet]

@ion1 haha i posted these before i read your examples-- nice!

and nice AST

[jbenet]

it is looking like XPath has the wanted functionality here.

Wonder if there is an XPath subset that's way simpler.

[jbenet]

XPath pros:

• already exists
• tons of tutorials + help
• powerful + expressive
• path-oriented (css and json selectors are not path-oriented)
• the simple cases, are very straight forward and readable

XPath cons:

• it is very complex
• no clear simpler subset to run in the common case.

XPath Questions:

• are implementations in Golang and JS XML specific? or parse tree specific?
• would be easy or absurdly hard to adapt an XPath resolver module to take in a graph we give it (i.e. not built from XML)
• do we prefer css selectors instead??? they have problems too.

[jbenet]

cc @mildred thoughts? think go-ipld could support this?

[jbenet]

Or do we use JSONPath? http://goessner.net/articles/JsonPath/ https://jsonpath.curiousconcept.com/

likely JSONPath wont work with all the things we may have in ipld?

[mildred]

The problem I have with XPath is that it is designed to work on XML document semantic. Those have attributes, nodes and a few other oddities that XPath can query. Moreover, it is quite complex.

JSONPath seems better to me. It fits the data model more closely. We will probably want to extend it to be able to traverse merkle links. We could use / that doesn't seems to be used in JSONPath.

JSONPath doesn't specify a language for expressions. We might want to define a common language for all implementations.

[jbenet]

cc @nicolagreco this is the "IPLD Selector" placeholder issue. we should discuss it more here.

[jbenet]

interesting thought: graphql.org