Parsing $filter and $orderby using the ODataUriParser

Background and Plans

For a while now we’ve been shipping an early pre-release version of an ODataUriParser in ODataLib Contrib. The idea is to have code that converts a Uri used to interact with an OData Service into a Semantically bound Abstract Syntax Tree (AST) which represents the request in terms of the OData concepts used.

The ODataUriParser is currently an alpha at best, with many known functionality gaps and bugs. However the ASP.NET Web API OData library has a dependency on the parser and is RTMing soon, so we need to bring the quality up quickly.

Our plan is to move Uri Parser out of ODataLib Contrib into a fully supported ODataLib release.

Currently ASP.NET Web API only needs support for parsing $filter and $orderby: because today Web API doesn’t support $select and $expand, has it’s own parser for the PATH part of the Uri and all the other OData query options which are very simple to parse. This scoped set of requirements and tight time constraints means the ODataUriParser support we ship in ODataLib will initially be a subset, albeit a better tested and more complete subset, of the ODataUriParser currently in ODataLib Contrib.

So what will the API look like?

Parsing $filter

To parse a $filter you need at least two things: an IEdmModel, and an IEdmType to use as your collection element type. Optionally you can provide an IEdmEntitySet too.

For example imagine this request:

GET /Service/Customers?$filter=Name eq ‘ACME’

To parse the $filter query option, you would need an IEdmModel for the service hosted at ~/Service, and you need to provide the element type of the collection being filtered, in this case Customer.

To create the model, you can use EdmLib code directly:

var model= new EdmModel();

var customer = new EdmEntityType("TestModel", "Customer");
bool isNullable = false;
var idProperty = customer.AddStructuralProperty("Id", EdmCoreModel.Instance.GetInt32(isNullable);
customer.AddKeys(idProperty);
customer.AddStructuralProperty("Name", EdmCoreModel.Instance.GetString(isNullable));
edmModel.AddElement(customer);

var container= new EdmEntityContainer("TestModel", "DefaultContainer");
container.AddEntitySet(“Customers”, customer);
model.AddElement(container);

This code, builds a model with a single EntityType called customer (with Id and Name properties) an exposes customer instances via an EntitySet called Customers in the default container. Working with EdmLib directly like this, is however quite low-level, another simpler option is to use the ODataConventionModelBuilder from the Web API OData package, which provide a nice higher level API for building models. If you go the WebAPI route, be sure to checkout these blog posts:

In the above example working out the type of the collection is pretty simple, but of course OData paths (i.e. the bit before the ?) can be quite complicated. To help in the long run this functionality will be provided by the Uri Parser, but for now you have to work this out for the OData Uri Parser. That said, you are not alone, the WebAPI team had the same problem and has create a class called the  DefaultODataPathParser that will work out the type (and EntitySet if appropriate) of any OData path.

Once you have the IEdmModel and IEdmType you need, you can parse the $filter like this:

FilterNode filter = ODataUriParser.ParseFilter(“Name eq ‘ACME’”, model, customer);

If you start exploring this filter which is an AST, you will notice it looks like this:

QueryTree

You could easily visit this to produce some sort alternate query syntax, perhaps SQL or CLR expressions. In fact this is what the ASP.NET Web API does, to support the [Queryable] attribute, it first parses the $filter and then it converts the AST into a LINQ expression. You don’t need to do this though, you could for example convert from this AST directly to SQL, which is very useful if you don’t have a LINQ provider, because creating a LINQ provider is a significant undertaking.

Parsing $OrderBy

To parse a $orderby you again need an IEdmModel and an IEdmType for the element type of the collection you want to order. For example:

To handle this:

GET /Service/Customers?$orderby=Name desc,Id

Which orders first by Name descending and then by Id ascending, you would make this call:

OrderByNode orderby = ODataUriParser.ParseOrderBy(“Name desc, Id”, model, customer);

Again if you visit you will see something like this:

OrderByTree

If you are familiar with ASTs this will seem pretty simple.

The Node type hierarchy

The root of the type hierarchy is QueryNode. Beyond that the node hierarchy has been organized to prioritize two key pieces of information, namely:

  1. Whether the node represents a Collection or a Single value
  2. Whether the node represents an Entity or another type.

The first level down from the root of the type hierarchy indicates whether you are dealing with a Single value (SingleValueNode) or a Collection (CollectionNode). Then the second level down is used to distinguish between Entities and other types, so for example there is a node called SingleEntityNode that derives from SingleValueNode and a EntityCollectionNode that derives from CollectionNode.

Then the most derived node types distinguish between the various ways of getting to a Collection or Single instance of an Entity or Nonentity. For example the various ways you can get a single entity, one possible way is by following a navigation property with target multiplicity of 0..1 or 1 (SingleNavigationNode), and so on, each of these ways are represented as nodes that derive from SingleEntityNode.

This approach yields a hierarchy that (when simplified) looks a little like this:

NodeHierarchy

Amongst the leaf nodes, a few deserve a special mention:

  • BinaryOperatorNode which represents a Binary operator like for example:  Name eq ‘Bob’  
  • UnaryOperatorNode which represents a Unary operator like for example: not True 
  • AnyNode which represents OData any filter expression, for example: collection/any(a: a/Age gt 100)
  • AllNode which represents an OData all filter expression, for example: collection/all(a: a/Age gt 10)

From a type system perspective these all represent a boolean value, so then all derive from the natural place in the type hierarchy SingleValueNode.

To help recognize which kind of node you are dealing with at any time, all nodes have a Kind property which in the RC return one of the constants defined on the static QueryNodeKind class. For example if you given a QueryNode and you want to write a visitor, you should visit the appropriate derived nodes, first by checking the QueryNode.Kind and then casting as appropriate. For RTM we’ll convert Kind to an Enum.

All nodes are held in the Expressions held by classes like FilterClause and OrderByClause, In the future new classes will be introduced to support ODataPath, $select, $expand, etc. Then finally we’ll add a class to represent the full url once we have full coverage of OData urls.

Conclusion

The ODataUriParser is on the road to RTM quality now, but it is not happening in one big step, we will start with $filter and $orderby and overtime cover the rest of OData including paths, $expand and $select.

If you are interested in the latest code I invite you to try out the latest version of ODataLib.

-Alex