Object Model for "M" Values
[This content is no longer valid. For the latest information on "M", "Quadrant", SQL Server Modeling Services, and the Repository, see the Model Citizen blog .]
Clemens Szyperski
November 3, 2009
1. Introduction
Developing and utilizing domain-specific languages (DSLs) in the SQL Server Modeling CTP typically involves authoring the grammar in “Intellipad” then using the code name “M” command-line tools to process input files against the compiled grammar. The output of this process is “M” language constructs commonly referred to as “M” values. Often, this output takes the form of an abstract syntax tree (AST) in which the highly variable structures of a DSL have been organized into a standardized graph representation. Data represented in “M” values can be checked against schema authored in “M” and can then be loaded into the SQL Server Modeling Services repository database using the mx.exe command-line tool.
Of course, a command-line tool is meant for interactive use and automation scripts. Applications and runtimes also need a means to process “M” values output programmatically, a process known as dynamic parsing. This allows a user to directly enter DSL input at runtime which the application then processes without the need to utilize intermediate command-line tools.
The Object Model (OM) described in this document is what allows this to happen. It’s the lowest-level runtime model to manage “M” values in .NET applications, that is, processing input against a grammar through .NET classes written for this purpose; and it is the same set of classes that “Intellipad” and mx.exe use themselves. Developers will utilize this object model whenever dynamic parsing is needed. Note that it replaces an older object model as described in §1.4 below.
Beyond the dynamic-parsing scenarios outlined above, the object model is a general .NET framework to manipulate arbitrary graph-shaped data. Thus, an “M” values graph is really the “data profile” of “M” with a typical instance looking like this:–
// Populate a small village with some people
Villagers => {
Jenn => Person {
Name => 'Jennifer', Age => 28, Spouse => Rich },
Rich => Person {
Name => 'Richard', Age => 26, Spouse => Jenn },
Charly => Person
{ Name => 'Charlotte', Age => 12 }
},
HaveSpouses => { Villagers.Rich, Villagers.Jenn }
All aspects of “M”, including the output structure, are still evolving and, in the November 2009 CTP, several not-yet-finalized language details appear only in “M” values. Specifically, the above example exhibits the following details:
- An “M” values instance is a sequence of optionally labeled edges. An edge is a pair (label, targetNode). In the example above, there are two such top-level edges, labeled Villagers and HaveSpouses.
- Edge labels appear to the left of the binding operator (=>). An identifier appearing to the right of the binding operator and before the value being bound is called a brand.
- “M” values supports a fairly rich set of “M” intrinsic types for leaf values. (See §2.1.3 for the supported “M” types and how they map to CLR types.)
- “M” values supports comments (//… and /*…*/ style) and verbatim text (@"…").
Caution: As a consequence of this staging of language changes, the “M” values syntax is temporarily incompatible with that used for graphs (extent initializers) in “M” and also, in different ways, from that used for graph construction in the right-hand side of “M” language rules. All this is going to be cleaned up in the future.
Architecturally, the object model comprises three main subsystems: the graph model, graph stores, and graph readers/writers. The graph model is about construction, traversal/inspection, and updating of graphs. Graph stores provide the backing implementations for different graph representations and bridges to external stores. Readers/writers support the mapping of graphs from and to streams.
This introduction comprises an overview of those three subsystems. The following sections cover each in full detail, followed by a set of fully worked examples. Some readers may prefer to skip forward to the examples sections (§2.7, §3.5, and §4.3) before delving into the details of the design.
The overall object model strikes a balance between usability and convenience on the one hand and implementation flexibility and enabling high performance on the other. Performance, both at the level of individual operations and at the level of scalability to very large graphs, is a central feature of the design. Graphs are a very general and low-level abstraction that many complex designs can be built on top of, but only if the supporting infrastructure can bear such load.
Heads-up: To meet this two-pronged goal, the design is unusual in that it relies on a family of struct types beyond what is common in the .NET framework. Readers unfamiliar with the various consequences of using structs may want to pause and pay attention to the related detail. The key property of the design is that almost all of the structs (but enumerators) are stateless; making their use convenient and straightforward without requiring constant attention to the fact that struct types are being used.
1.1. Graph Model
An “M” values instance is a directed, edge-labeled graph. Each node is either atomic, holding a single value, or non-atomic, holding a multiset of outgoing edges. Nodes carry an optional brand. Edges outgoing from a node are either unlabeled or uniquely labeled, relative to their source node. A value held by an atomic node is either of an “M” values classified type or of unclassified type (arbitrary other CLR type).
A graph allow for sharing: a single node can be reachable via more than one path (where a path is a sequence of one or more edges). A graph can contain loops: an edge can refer back to its originating node. A graph can contain cycles: a path can refer back to its originating node.
1.1.1. Labels and Brands
Edges may be associated with a nominal label, where labels are either strings or integers. The interpretation of labels is left open in the graph model, except that labels are mandated to be unique among edges outgoing from the same source node. A typical interpretation uses labels to designate roles of successor nodes.
Nodes may be associated with a nominal brand, where brands are strings. The interpretation of brands is left open in the graph model, but a typical interpretation uses brands to associate a nominal concept, such as a type or class, with a node.
1.1.2. Graph patterns
The graph model introduces no inherent ordering on successors of a node. Thus, if multiple unlabeled edges originate in a given node, then the successors (the target nodes of these edges) are distinguishable only by their content. It is valid to have any number of fully indistinguishable successors – essentially representing the elements of a multiset as unlabeled successors of a node.
A node that has only labeled outgoing edges, all of which are strings, represents a record. The successors are the members of the record; the labels are the member names.
A node that has at least two successors, all of which are the targets of labeled edges, using integer labels in the range from zero to the number of successors minus one, represents a tuple. The successors are the members of the tuple; the labels are the indices into the tuple.
A node that has only labeled outgoing edges, with exactly the two labels “Head” and “Tail”, represents a list. The successor labeled “Head” holds the first value in the list; the successor labeled “Tail” holds the remaining values in the list. This is the familiar cell-based encoding of lists.
A node with only unlabeled outgoing edges represents an unordered collection. The successors are the members of that collection.
A node with both labeled and unlabeled outgoing edges represents a composite, which is the most general pattern supported.
A node with no successors represents an empty collection, but also serves to represent an empty list, an empty record (a record with zero members), and an empty composite.
The following table summarizes the graph patterns, their corresponding notation in “M” values, and their associated labeling constraints. For tuples and lists, the expanded (and equivalent) notation that shows the representation as labeled graphs is also shown over a grey backdrop.
|
Graph Pattern |
“M” Values Notation |
Labeling Constraints |
|
Composite |
{ 42, Name => "Jack" } |
– |
|
Collection |
Primes { 1, 2, 3, 5, 7 } |
No labels |
|
Record |
Jack { Age => 42, Name => "Jack" } |
All labeled, all string labels |
|
Tuple |
|
All labeled, all integer labels, labels in range [0..count) |
|
List |
|
All labeled; exactly the labels “Head” and “Tail” |
1.1.3. Symbolic References
Normally, all relationships among nodes in a graph are expressed using edges. However, it is also possible to hold unresolved symbolic references to other nodes in a graph. Such references are captured as special atomic values (of type GraphReference). As the one exception to the branding mechanism, atomic nodes holding such symbolic references cannot be branded.
Rationale: nodes holding symbolic references are seen as place holders for the actual target node that they refer to. Reference resolution substitutes the node located by the resolution procedure for the target node that held the reference. This way, the edge label is retained and all properties of the reference target are shared, including the reference target’s brand, if any.
A symbolic reference is a pair (isGlobal, labelSequence). The isGlobal flag determines whether the reference is global or local. A global reference is resolved by starting from a separately defined global source node; if no such node is defined for a given graph, then global references are undefined.
A local reference is resolved by following the label sequence, in order, as designated by the reference, starting at the node holding the symbolic reference.
In the special case where a global source node is defined and where a local reference’s first label does not resolve from the node holding the reference, a special scope determination procedure is applied to determine the node form where the reference is to be resolved. This procedure constructs a path from the global source node to the node holding the reference. If no such path can be constructed, reference resolution fails. If multiple such paths can be constructed, then an arbitrary one of them is chosen. The node closest to the node holding the reference that has an outgoing edge labeled with the first label of the reference at hand is chosen as the scope node. Resolution proceeds from that node.
The textual syntax for symbolic references is [ label ] ('.' label)*. A global reference has no initial label, that is, it starts with a dot: .Jill or .Jack.Spouse.Age. A local reference starts with a label: Name or Spouse.Name.
In the example above, the symbolic references Spouse.Age and .Jack.Spouse can both be resolved, assuming that the shaded node is the designated global source node. Note that references can be resolved “through” other references. In the example, .Jill.Spouse.Age resolves by first resolving the encountered reference .Jill and then resolving Age relative to that node.
Global alternatives for Spouse.Age would be .Jack.Age, .Jill.Spouse.Age, and so on. Local alternatives would be Spouse.Spouse.Spouse.Age, and so on. There are no local alternatives for the global reference in the example, .Jack.Spouse.
1.2. Graph Stores
For most cases of programmatic creation, traversal, use, and modification of graphs, the types Node and Edge form the main points of access.
For implementers of custom graph “stores” (a term used broadly for all graph implementations, whether in-memory or virtualized over an external store), the type GraphStore is the center of the design. When creating graphs using Node and Edge without reference to any specific GraphSt0re, the system provides a shadow store implementation.
The architecture of the object model provides substantial flexibility for implementers of graph stores, catering for everything from very simple store implementations that just use a few CLR types to represent graphs as objects to highly sophisticated implementations that virtualize over an external store and use dense, non-object-based cache structures. The external use of such stores is the same in all cases, governed by the fixed types of the graph model.
1.3. Graph Readers and Writers
The types GraphReader and GraphWriter are used to map graphs from and to stream formats. Specific subtypes implement the reading/writing of specific stream representations; most importantly, GraphTextReader and GraphTextWriter implement the mapping from/to text streams.
1.4. Transition from Old to New Object Model
The “M” values object model covered in this document is meant to replace the older design around type IGraphBuilder, GraphBuilder, etc. This older design is to be deprecated and then removed in future releases. At the current point in time (November 2009), some of the larger design still depends on IGraphBuilder; most notably, DynamicParser does.
To enable a staged migration from the old to the new design, class NodeGraphBuilder is included in the current release. It, too, will be removed as soon as IGraphBuilder goes. NodeGraphBuilder bridges from the old IGraphBuilder API to the new GraphStore API.
In the example below, Contact, Alias, and Number are brands and Info is an edge label. Class NodeGraphBuilder maps labels in the IGraphBuilder world to brands in the new design unless an entity, in the IEntityBuilder sense, is built, in which case the entity-member label is mapped to an edge label in the new design.
string contactGrammar = @"
module M {
language Contacts
{
syntax Main =
'Contact' ':'
a:Alias => Contact { Info => Alias { a } }
| 'Contact' ':'
p:Number => Contact { Info => Number { p } };
token Alias =
('A'..'Z' | 'a'..'z')+;
token Number =
('0'..'9' | '-')+;
}
}";
CompilationResults results = Compiler.Compile(
new CompilerOptions
{
Sources = {
new TextItem {
Reader = new
StringReader(contactGrammar),
ContentType =
TextItemType.MGrammar }
}});
DynamicParser parser =
results.ParserFactories["M.Contacts"].Create();
parser.GraphBuilder = new NodeGraphBuilder();
With the parser’s graph builder set to an instance of NodeGraphBuilder, the results of DynamicParser.Parse calls are always of type Node (not just object, as in the old design). The following examples show the parsing of sample input sentences (underlined) and their interpretation using the (new) graph model.
Node contact = (Node)parser.Parse(
new
StringTextStream("Contact:gatsby"), null);
Node info = contact.Edges["Info"];
Node infoSingleValue = info.ViewAllNodes().Single();
Assert.AreEqual(contact.Brand, "Contact");
Assert.AreEqual(info.Brand, "Alias");
Assert.AreEqual(infoSingleValue.AtomicValue,
"gatsby");
contact = (Node)parser.Parse(
new
StringTextStream("Contact:555-1212"), null);
info = contact.Edges["Info"];
infoSingleValue = info.ViewAllNodes().Single();
Assert.AreEqual(contact.Brand, "Contact");
Assert.AreEqual(info.Brand, "Number");
Assert.AreEqual(infoSingleValue.AtomicValue,
"555-1212");
2. Graph Model
The type Node is the design center for almost all cases where graphs are being created, traversed, read, written, or updated. Node is a struct and leads to a family of further struct types that, together, enable allocation- and copy-free operations over graphs while providing a convenient type surface that is friendly for Linq and other modern patterns, such as initializers, as supported by C# 3.0.
Rationale: These struct types contain no implementation or representation decisions of their own and delegate all such decisions through type GraphStore to specific implementations. It is useful to think of GraphStore as a large method dispatch type that provides convenient defaults for implementers of graph stores, but that is not meant to be used directly. Access to GraphStore’s through Node and associated types is much more convenient and equally efficient. In fact, each of the struct types in this design contains exactly two reference fields: a reference to the underlying graph store and a store-specific key object. The only exceptions are the enumerator structs that hold additional enumeration state.
2.1. Node
The Node struct has a large surface area. For the purposes of documentation, it is broken up into pieces in this section and its subsections. The following shows the main surface of Node, with references to subsections for elided members.
namespace System.Dataflow {
public struct Node :
IEquatable<Node>, INotifyPropertyChanged {
public static
readonly Node Default;
// Constructors,
listed in §2.1.4
// Explicit and
implicit conversions, listed in §2.1.5
// Read/Write
methods, listed in §2.1.6
// Navigation
methods, listed in §2.1.7
public static bool
operator ==(Node left, Node right);
public static bool
operator !=(Node left, Node right);
public object
AtomicValue { get; set; }
public Identifier
Brand { get; set; }
public
EdgeCollection Edges { get; }
public bool
IsDefault { get; }
public bool
IsListOrEmptyCollection { get; }
public bool
IsReadOnly { get; }
public bool
IsRecordOrEmptyCollection { get; }
public NodeKind
NodeKind { get; }
public GraphStore
Store { get; }
public object
StoreKey { get; }
public event
PropertyChangedEventHandler PropertyChanged { add; remove; }
public static
GraphStore CreateDefaultStore();
public static Node
CreateNodeForStoreKey(GraphStore store, object key);
public override
bool Equals(object obj);
public bool
Equals(Node other);
public override
int GetHashCode();
public override
string ToString();
public
NodeCollection ViewAllNodes();
public GraphList
ViewAsList();
public
GraphDictionary ViewAsRecord();
public GraphList
ViewAsTuple();
public GraphList
ViewOrderedNodes();
public
NodeCollection ViewUnorderedNodes();
}
}
The properties of Node directly reflect the structure of the graph model; they are covered in detail in §2.1.1.
2.1.1. Node Properties
public object AtomicValue { get; set; }
public Identifier Brand { get; set; }
public EdgeCollection Edges { get; }
public bool IsDefault { get; }
public bool IsListOrEmptyCollection { get; }
public bool IsReadOnly { get; }
public bool IsRecordOrEmptyCollection { get; }
public NodeKind NodeKind { get; }
public GraphStore Store { get; }
public object StoreKey { get; }
Atomic nodes have an AtomicValue, non-atomic nodes have an atomic value of null. All nodes, but atomic nodes holding a symbolic reference, can carry a Brand (§1.1.1). The kind of a node is reflected by its NodeKind property (§2.1.2).
Non-atomic nodes have a collection of outgoing Edges; for atomic nodes, this collection is always empty. For a discussion of the rich surface provided over edge collections, see §.
Since non-atomic nodes with an empty collection of outgoing edges are reported as having a node kind of Collection, the tests IsListOrEmptyCollection and IsRecordOrEmptyCollection are provided to handle the case where a node of interest should follow the list or record pattern, but where the empty case is permissible.
If the backing store does not support updates of a node, it is marked as IsReadOnly.
A node that has been constructed using Node’s default constructor , is marked as IsDefault. A node that has been constructed using any but Node’s default constructor will have a valid store (Store) and store key (StoreKey). The details of those two concepts can be found in §3.1, but can be ignored for all but advanced scenarios.
2.1.2. NodeKind
Nodes are of one of a small number of defined kinds.
namespace System.Dataflow {
public enum NodeKind
{
Undefined, Atomic,
Composite, Collection, List, Record, Tuple
}
}
Only nodes constructed using the Node default constructor will be of kind Undefined.
2.1.3. Classified value types
Atomic nodes hold a value of a classified type: a type that is part of the profile’s set of atomic types. The following table shows how the classified CLR types map to “M” types. C# synonyms, as uses in the type excerpts in this document, are also shown.
| C# Synonym | CLR Type | “M” Type |
|---|---|---|
|
bool |
System.Boolean |
Logical |
|
byte[] |
System.Byte[] |
Binary |
|
Date |
System.Date |
Date |
|
DateTime |
System.DateTime |
DateTime |
|
DateTimeOffset |
System.DateTimeOffset |
DateTimeOffset |
|
Time |
System.Time |
Time |
|
decimal |
System.Decimal |
Decimal28 |
|
double |
System.Double |
Double |
|
GraphReference |
System.Dataflow.GraphReference |
– |
|
Guid |
System.Guid |
Guid |
|
int |
System.Int32 |
Integer32 |
|
long |
System.Int64 |
Integer64 |
|
Time |
System.Time |
Time |
Note that types System.Date and System.Time are not part of the .NET framework (yet) and found in System.Dataflow.dll.
2.1.4. Node Constructors
Type Node has a constructor overloads that fall into two groups: constructors for atomic value nodes and constructors for non-atomic nodes. These groups are covered in that order below.
Constructors for atomic nodes take value of one of the classified types (see §2.1.3) and, optionally, a brand and a store implementation to use. If the value type is not known statically, then the object-typed constructors can be used.
public Node(object constant);
public Node(Identifier brand, object constant);
public Node(GraphStore store, Identifier brand, object
constant);
When holding a strongly typed value, the following constructor overloads can be used.
Rationale: Using these constructors enables the underlying graph store to avoid boxing. Whether values get boxed depends on the specific store implementation.
public Node(bool constant);
public Node(Identifier brand, bool constant);
public Node(GraphStore store, Identifier brand, bool
constant);
public Node(Identifier brand, byte[] constant);
public Node(GraphStore store, Identifier brand, byte[]
constant);
public Node(Date constant);
public Node(Identifier brand, Date constant);
public Node(GraphStore store, Identifier brand, Date
constant);
public Node(DateTime constant);
public Node(Identifier brand, DateTime constant);
public Node(GraphStore store, Identifier brand, DateTime
constant);
public Node(DateTimeOffset constant;
public Node(Identifier brand, DateTimeOffset constant;
public Node(GraphStore store, Identifier brand,
DateTimeOffset constant);
public Node(decimal constant);
public Node(Identifier brand, decimal constant;
public Node(GraphStore store, Identifier brand, decimal
constant);
public Node(double constant);
public Node(Identifier brand, double constant);
public Node(GraphStore store, Identifier brand, double
constant);
public Node(GraphReference constant);
public Node(GraphStore store, GraphReference constant);
public Node(Guid constant);
public Node(Identifier brand, Guid constant);
public Node(GraphStore store, Identifier brand, Guid
constant);
public Node(int constant);
public Node(Identifier brand, int constant);
public Node(GraphStore store, Identifier brand, int
constant);
public Node(long constant);
public Node(Identifier brand, long constant);
public Node(GraphStore store, Identifier brand, long
constant);
public Node(string constant);
public Node(Identifier brand, string constant);
public Node(GraphStore store, Identifier brand, string
constant);
public Node(Time constant);
public Node(Identifier brand, Time constant);
public Node(GraphStore store, Identifier brand, Time
constant);
The following constructors for non-atomic nodes take a collection of outgoing edges in combination with an optional brand. These constructors are intended to support the effective cloning of non-atomic nodes.
public Node(EdgeCollection edges);
public Node(Identifier brand, EdgeCollection edges);
The following constructors supported graph patterns are composite, collection, record, tuple, and list. If left unspecified, composites are built by default. Optionally, the brand and store to use can be specified. The successors are specified as enumerables or params of edges.
public Node(IEnumerable<Edge> edges);
public Node(Identifier brand, IEnumerable<Edge>
edges);
public Node(NodeKind kind, IEnumerable<Edge> edges);
public Node(Identifier brand, NodeKind kind,
IEnumerable<Edge> edges);
public Node(GraphStore store, IEnumerable<Edge>
edges);
public Node(GraphStore store, Identifier brand,
IEnumerable<Edge> edges);
public Node(GraphStore store, NodeKind kind,
IEnumerable<Edge> edges);
public Node(GraphStore store, Identifier brand, NodeKind
kind,
IEnumerable<Edge> edges);
public Node(params Edge[] edges);
public Node(Identifier brand, params Edge[] edges);
public Node(NodeKind kind, params Edge[] edges);
public Node(Identifier brand, NodeKind kind, params Edge[]
edges);
public Node(GraphStore store, params Edge[] edges);
public Node(GraphStore store, Identifier brand, params
Edge[] edges);
public Node(GraphStore store, NodeKind kind, params Edge[]
edges);
public Node(GraphStore store, Identifier brand, NodeKind
kind,
params Edge[]
edges);
The following constructors support the graph patterns collection, tuple, and list. If left unspecified, collections are built by default. Optionally, the brand and store to use can be specified. The successors are specified as enumerables or params of nodes.
public Node(NodeKind kind);
public Node(Identifier brand, NodeKind kind);
public Node(GraphStore store, NodeKind kind);
public Node(GraphStore store, Identifier brand, NodeKind
kind);
public Node(params Node[] nodes);
public Node(Identifier brand, params Node[] nodes);
public Node(NodeKind kind, params Node[] nodes);
public Node(Identifier brand, NodeKind kind, params Node[]
nodes);
public Node(GraphStore store, params Node[] nodes);
public Node(GraphStore store, Identifier brand, params
Node[] nodes);
public Node(GraphStore store, NodeKind kind, params Node[]
nodes);
public Node(GraphStore store, Identifier brand, NodeKind
kind,
params Node[]
nodes);
2.1.5. Node Conversions
The following explicit conversions on Node support the extraction of typed values from atomic nodes. They throw if the node is non-atomic or if it holds a value of a different type.
public static
explicit operator bool(Node node);
public static
explicit operator byte[](Node node);
public static
explicit operator char(Node node);
public static explicit
operator Date(Node node);
public static
explicit operator DateTime(Node node);
public static
explicit operator DateTimeOffset(Node node);
public static
explicit operator decimal(Node node);
public static
explicit operator double(Node node);
public static
explicit operator GraphReference(Node node);
public static
explicit operator Guid(Node node);
public static
explicit operator int(Node node);
public static
explicit operator long(Node node);
public static
explicit operator string(Node node);
public static
explicit operator Time(Node node);
The following explicit conversions on Node support the extraction of nullable typed values from atomic nodes. They return null if the node is non-atomic or if it holds a value of a different type.
public static
explicit operator bool?(Node node)
public static
explicit operator char?(Node node)
public static
explicit operator Date?(Node node)
public static
explicit operator DateTime?(Node node)
public static
explicit operator DateTimeOffset?(Node node)
public static
explicit operator decimal?(Node node)
public static
explicit operator double?(Node node)
public static
explicit operator Guid?(Node node)
public static
explicit operator GraphReference?(Node node)
public static
explicit operator int?(Node node)
public static
explicit operator long?(Node node)
public static
explicit operator Time?(Node node)
The following implicit conversions on Node support the conversion of values of classified type to atomic nodes.
public static implicit operator
Node(bool value);
public static
implicit operator Node(char value);
public static
implicit operator Node(Date value);
public static
implicit operator Node(DateTime value);
public static
implicit operator Node(DateTimeOffset value);
public static
implicit operator Node(decimal value);
public static
implicit operator Node(double value);
public static
implicit operator Node(Guid value);
public static
implicit operator Node(GraphReference value);
public static
implicit operator Node(int value);
public static
implicit operator Node(long value);
public static
implicit operator Node(string value);
public static
implicit operator Node(Time value);
2.1.6. Node Read/Write Support
The following methods support the reading of a graph from a stream (yielding a sequence of edges).
Note: Reading directly from a string is mostly useful for simple scenarios such as unit tests.
public static IEnumerable<Edge> ReadFrom(GraphReader
reader);
public static IEnumerable<Edge> ReadFrom(GraphReader
reader,
Func<GraphStore> createStore);
public static IEnumerable<Edge> ReadFrom(TextReader
reader);
public static IEnumerable<Edge> ReadFrom(TextReader
reader,
Func<GraphStore> createStore);
public static IEnumerable<Edge> ReadFrom(Stream
stream);
public static IEnumerable<Edge> ReadFrom(Stream
stream,
Func<GraphStore> createStore);
public static IEnumerable<Edge> ReadFrom(Stream
stream,
Encoding
encoding);
public static IEnumerable<Edge> ReadFrom(Stream
stream,
Encoding
encoding, Func<GraphStore> createStore);
public static IEnumerable<Edge> ReadFrom(string
filePath);
public static IEnumerable<Edge> ReadFrom(string
filePath,
Func<GraphStore>
createStore);
public static IEnumerable<Edge> ReadFrom(string
filePath,
Encoding
encoding);
public static IEnumerable<Edge> ReadFrom(string
filePath,
Encoding
encoding, Func<GraphStore> createStore);
public static IEnumerable<Edge> ReadFromString(string
text);
public static IEnumerable<Edge> ReadFromString(string
text,
Func<GraphStore> createStore);
Given a node, the following methods support the writing of the graph reachable from that node to a stream.
Note: Writing directly to a string is mostly useful for simple scenarios such as unit tests.
Note: Writing to a string writes the entire reachable graph, while calling ToString returns a size-bounded string that summarizes the top structure of the reachable graph.
public void WriteTo(Stream stream);
public void WriteTo(Stream stream, Encoding encoding);
public void WriteTo(string filePath);
public void WriteTo(string filePath, Encoding encoding);
public void WriteTo(TextWriter writer);
public void WriteTo(GraphWriter writer);
public string WriteToString();
Issue: Methods to directly write a collection of edges should be added to match the model of the read methods.
2.1.7. Node Navigation Methods
Given a node, the following methods use that node as a navigation scope and attempt to resolve a given symbolic reference within that scope. If the reference is global (reference.IsGlobal), then the resolution is only supported if the underlying store maintains a set of outer edges. (See §1.1.3 for details on symbolic references and §3.2 for details on reference resolution as performed by graph stores.)
public Node NavigateFromRootTo(GraphReference reference);
public Node NavigateFromRootTo(string path);
public IAsyncResult BeginNavigateFromRootTo(GraphReference
reference,
AsyncCallback
callback, object asyncState);
public IAsyncResult BeginNavigateFromRootTo(string path,
AsyncCallback
callback, object state);
public Node EndNavigateFromRootTo(IAsyncResult asyncResult);
public Node NavigateTo(GraphReference reference);
public Node NavigateTo(string path);
public IAsyncResult BeginNavigateTo(GraphReference
reference,
AsyncCallback
callback, object asyncState);
public IAsyncResult BeginNavigateTo(string path,
AsyncCallback
callback, object state);
public Node EndNavigateTo(IAsyncResult asyncResult);
2.2. Edge
The type Edge represents a (label, target node) pair. Typically, edges belong to a source node – the edge is then a graph-theoretic labeled directed edge from the source to the target node. However, labeled edges in the object model can also stand on their own, that is, not have an associated source node. Such edges are interpreted as leading into a graph, optionally via a label, while remaining silent on the source of such an edge. In fact, edges may also be shared among multiple source nodes.
namespace System.Dataflow {
public struct Edge :
IEquatable<Edge> {
public static
readonly Edge Default = new Edge();
public Edge(Node
node);
public
Edge(KeyValuePair<Label, Node> pair);
public Edge(Label
label, Node node);
public static
explicit operator Edge(KeyValuePair<Label, Node> pair);
public static
explicit operator KeyValuePair<Label, Node>(Edge edge);
public static bool
operator ==(Edge left, Edge right);
public static bool
operator !=(Edge left, Edge right);
public bool
IsDefault { get; }
public
KeyValuePair<Label, Node> KeyValuePair { get; }
public Label Label
{ get; }
public Node Node {
get; }
public override
bool Equals(object obj);
public bool
Equals(Edge other);
public static
IEnumerable<Edge> FromKeyValuePairs(
IEnumerable<KeyValuePair<Label, Node>> pairs);
public static
IEnumerable<Edge> FromNodes(IEnumerable<Node> nodes);
public override
int GetHashCode();
public static
IEnumerable<KeyValuePair<Label, Node>> ToKeyValuePairs(
IEnumerable<Edge> edges);
public static
IEnumerable<Node> ToNodes(IEnumerable<Edge> edges);
public override
string ToString();
}
}
Besides the properties Label and Node representing the pair, property KeyValuePair (and a corresponding constructor and a couple of static helpers) are provided to easy interoperation with existing types defined in terms of KeyValuePair; most importantly, IDictionary<TKey, TValue>.
The static helper methods FromEdges and FromNodes are provided to translate between the two common cases of enumerations of edges and enumerations of (target) nodes.
2.3. Label
Labels are used to represent edge labels. Labels are either based on non-negative integers or on uninterpreted strings. Labels are atomized per AppDomain. That is, two labels are equal exactly if their object references are equal.
namespace System.Dataflow {
[Serializable]
public sealed class
Label
:
IEquatable<Label>, IComparable, IComparable<Label>
{
public static
Label Empty { get; }
public string Text
{ get; }
public int Value {
get; }
public static
implicit operator Label(string text);
public static
implicit operator Label(int value);
public static bool
operator ==(Label left, Label right);
public static bool
operator !=(Label left, Label right);
public static bool
operator <(Label id1, Label id2);
public static bool
operator <=(Label id1, Label id2);
public static bool
operator >(Label id1, Label id2);
public static bool
operator >=(Label id1, Label id2);
public int
Compare(object other);
int
IComparable.CompareTo(object obj);
int
IComparable<Label>.CompareTo(Label other);
public override
bool Equals(object obj);
bool
IEquatable<Label>.Equals(Label other)
public static
Label Get(int value);
public static
Label Get(string text);
public static
Label Get(string text, int index, int count);
public override
int GetHashCode();
public static bool
IsNullOrEmpty(Label label);
public override
string ToString();
}
}
2.4. Identifier
Identifiers are used to represent brands. Identifiers are uninterpreted strings that are atomized per AppDomain. That is, two identifiers are equal exactly if their object references are equal.
namespace System.Dataflow {
public sealed class
Identifier
:
IEquatable<Identifier>, IComparable, IComparable<Identifier>
{
public static
Identifier Empty { get; }
public string
Text { get; }
public static
implicit operator Identifier(string text);
public static
bool operator ==(Identifier left, Identifier right);
public static
bool operator !=(Identifier left, Identifier right);
public static
bool operator <(Identifier id1, Identifier id2);
public static
bool operator <=(Identifier id1, Identifier id2);
public static
bool operator >(Identifier id1, Identifier id2);
public static
bool operator >=(Identifier id1, Identifier id2);
public int
Compare(object other);
int
IComparable.CompareTo(object obj);
int
IComparable<Identifier>.CompareTo(Identifier other);
public override
bool Equals(object obj);
public static
Identifier Get(string text);
public static Identifier
Get(string text, int index, int count);
public override
int GetHashCode();
public static bool
IsNullOrEmpty(Identifier id);
public override
string ToString();
bool
IEquatable<Identifier>.Equals(Identifier other);
}
}
2.5. GraphReference
Symbolic references are held by atomic nodes as values of type GraphReference.
namespace System.Dataflow {
public struct
GraphReference : IEquatable<GraphReference> {
public static
readonly GraphReference Default = new GraphReference();
public GraphReference(string
path);
public
GraphReference(IEnumerable<Label> segments);
public
GraphReference(params Label[] segments);
public
GraphReference(IEnumerable<string> segments);
public
GraphReference(params string[] segments);
public static
explicit operator GraphReference(string path);
public static
implicit operator Node(GraphReference value);
public static bool
operator ==(GraphReference reference1,
GraphReference reference2);
public static bool
operator !=(GraphReference reference1,
GraphReference reference2);
public int Count {
get; }
public bool
IsDefault { get; }
public bool
IsGlobal { get; }
public
IEnumerable<Label> Segments { get; }
public Label
this[int index] { get; }
public override
bool Equals(object obj);
public bool
Equals(GraphReference other);
public static
string Format(GraphReference reference);
public override
int GetHashCode();
public static
Label LabelFromSegment(string segment);
public override
string ToString();
public static
Label[] Parse(string path);
}
}
A global reference (one starting with a dot in “M” notation) is flagged as IsGlobal and will have a first segment that is empty.
The Format method creates a string from a given reference that adheres to “M” syntax, including proper quoting.
The LabelFromSegment method constructs an integer label if possible and a string label otherwise.
2.6. EdgeCollection
EdgeCollection is a lightweight struct that represents the collection of outgoing edges of the corresponding source node (Source property).
namespace System.Dataflow {
public struct
EdgeCollection : ICollection<Edge> {
public int Count {
get; }
public bool
IsDefault { get; }
public bool
IsReadOnly { get; }
public Node Source
{ get; }
public Node
this[Label label] { get; set; }
public static bool
operator ==(EdgeCollection left,
EdgeCollection right);
public static bool
operator !=(EdgeCollection left,
EdgeCollection right);
public void
Add(Edge item);
public void
Add(Label label, Node node);
public void
Add(Node node);
public void
Add(params Edge[] edges);
public void
Add(params object[] nodes);
public void Clear();
public bool
Contains(Edge item);
public bool
ContainsLabel(Label label);
public void
CopyTo(Edge[] array, int arrayIndex);
public override
bool Equals(object obj);
public
EdgeCollectionEnumerator GetEnumerator();
IEnumerator<Edge>
IEnumerable<Edge>.GetEnumerator();
IEnumerator
IEnumerable.GetEnumerator();
public override
int GetHashCode();
public Node
GetLabeledEdgeOrDefault(Label label);
public
IEnumerable<Label> GetLabels();
public bool
Remove(Edge item);
public override
string ToString();
}
}
The Add overloads on EdgeCollection allow for direct contributions to the edge collection of a node. The C# collection initializer mechanism can be used for this purpose. The following example shows the direct use of Add on an existing node’s edge collection as well as the creation of a new node with a new edge collection created using a collection initializer:–
person.Edges.Add( //
Contribute new person to collection of villagers.
"Manager",
new Node(
"Person",
new EdgeCollection
{ { "Name", "John" }, { "Id", 42 } }
)
);
Rationale: Note that the primary enumerator, EdgeCollectionEnumerator, is again a struct. This enables the performance optimizations around the static enumerator pattern as supported by the C# compiler.
namespace System.Dataflow {
public struct
EdgeCollectionEnumerator : IEnumerator<Edge> {
public
EdgeCollectionEnumerator(GraphStoreEdgeCollectionAdapter adapter,
EmbeddableEnumeratorState state);
public Edge Current
{ get; }
object
IEnumerator.Current { get; }
public void
Dispose();
public bool
MoveNext();
public void
Reset();
}
}
2.7. Examples
Below is a simple scenario for using Node directly to construct a few simple things:–
var two = new Node(2);
var @true = new Node(true);
var twoAndTrue = new Node(two, @true);
var flag =
(from node in
twoAndTrue.ViewAllNodes()
where
node.AtomicValue is bool
select
(bool)node).Single();
var number =
(from node in
twoAndTrue.ViewAllNodes()
where
node.AtomicValue is int
select
(int)node).Single();
Assert.IsTrue(flag);
Assert.AreEqual(2, number);
Given the two atomic nodes constructed above, a simple tuple can be constructed:–
var pair = new Node(NodeKind.Tuple, two, @true);
var pairAsTuple = pair.ViewAsTuple();
var first = pairAsTuple[0];
var second = pairAsTuple[1];
Assert.AreEqual(2, (int)first);
Assert.IsTrue((bool)second);
Note the use of ViewAsTuple() on a node obtain a view that interprets the node’s successors using the tuple pattern. Given such a view, tuple elements can then be accessed by indexing.
The following example shows the construction of instances of the list pattern as well as the equality properties of atomic and non-atomic nodes. Specifically, atomic nodes have equality defined based on their value, while non-atomic nodes have equality defined based on their (graph-store-managed) identity.
var constants = new Node(NodeKind.List, first, two);
var structures = new Node(NodeKind.List, tuple, tuple);
var constantsAsList = constants.ViewAsList();
var structuresAsList = structures.ViewAsList();
Assert.AreEqual(constantsAsList[0],
constantsAsList[1]); // by value
Assert.AreEqual(structuresAsList[0], structuresAsList[1]);
// by identity
Graphs can be read from streamed forms:–
string villageGraph = @"
{
Villagers =>
{
Jenn =>
Person { Name => 'Jennifer', Age => 28, Spouse => Rich },
Rich =>
Person { Name => 'Richard', Age => 26, Spouse => Jenn },
Charly =>
Person { Name => 'Charlotte' }
},
HaveSpouses =>
{ Villagers.Rich, Villagers.Jenn }
}";
var village =
Node.ReadFromString(villageGraph).Single().Node;
var villagers = village.Edges["Villagers"];
New successors can be contributed to a non-atomic node:–
villagers.Add( //
Contribute new person to collection of villagers.
"Billy",
new Node(
"Person",
new EdgeCollection
{ { "Name", "William" }, { "Age", 3 } }
)
);
villagers.Add( //
Contribute age to existing person Charly.
"Charly",
new Node(new
EdgeCollection { { "Age", 12 } })
);
var charly = villagers.Edges["Charly"];
var billy = villagers.Edges["Billy"];
village.Add(
"Youth",
new Node(charly,
billy)
);
var youth = village.Edges["Youth"];
var charly2 =
(from node in youth.ViewAllNodes()
where
node.Edges["Name"] == "Charlotte"
select
node).Single();
var billy2 =
(from node in
youth.ViewAllNodes()
where
node.Edges["Age"] == 3
select
node).Single();
Assert.AreEqual(billy, billy2);
Assert.AreEqual(charly, charly2);
Assert.IsTrue(charly.Edges["Age"] == 12);
Remark: The contribution mechanics of the system respect the rules of graph merging (also referred to as graph coalescing) of “M”: if a contributed edge carries a label and the node being contributed to already has an outgoing edge with the same label, then both edges need to point to a non-atomic node. The content of the contributed edge’s target node will be merged into the content of the node that is being contributed to. This process repeats recursively. In the example above, this mechanism is used to add an Age edge to the existing node under Villagers.Charly.
3. Graph Stores
Graph stores are implementations of graph representations, including possible virtualization over external stores.
Besides the abstract type GraphStore, the system provides two concrete implementations: DefaultGraphStore and ShadowGraphStore. Graph stores have a large feature surface area that is mostly covered by defaults provided by GraphStore. This large area allows store implementations to specialize deeply and gain high-performance characteristics; the almost complete coverage by default implementations enables a low barrier to entry for custom graph-store implementations.
The DefaultGraphStore implementation uses in-memory structures to represent graphs and can be instantiated as needed to create separate graphs.
The ShadowGraphStore implementation builds on the default one, but exists in only one singleton instance per AppDomain. It is used automatically when constructing nodes using type Node without specifying a store. The shadow store is stateless, enabling thread-safe use as well as avoiding coupling among graphs independently created using the shadow store. To avoid state, the shadow store does not maintain a collection of outer edges and, therefore, has a default synthetic source node.
3.1. Stores and Store Keys
Graph stores deal in abstract nodes of externally invisible representation. Stores identify such nodes by handing out and taking back store keys: objects of unrefined type object.
A node is uniquely identified by a pair (store, store key). It is possible that a group of related stores share keys. For example, one store may represent a graph’s nodes while another, related store, may represent a particular kind of metadata associated with the nodes of the former store. By using the same keys for both stores, that association is maintained efficiently without “leaking” any particular association mechanism (such as attached properties) and without committing a store to a single metadata story.
The Node/Edge surface types all use (store, store key) pairs as their only state. Creating, copying, and destroying instances of these surface types is therefore very cheap and, in particular, creates no pressure on the garbage collector.
3.2. Reference Resolution
A graph store may provide a reference resolution service. If provided, that service can be used to perform a number of tasks: (i) resolve symbolic references, yielding the target nodes of references, (ii) substitute resolved targets for symbolic references, and (iii) compute a set of symbolic references that, if substituted in for some of a graph’s edges, yields a sharing and cycle free graph.
Most graph stores can work with the default resolver implementation provided in the GraphReferenceResolver class. The default resolver is stateless. Custom resolvers can subclass the default resolver.
namespace System.Dataflow {
public class
GraphReferenceResolver {
public virtual
bool TryBreakAllSharing(Node root,
out
Dictionary<Node, GraphReferenceTable> referenceTables);
public virtual
bool TryResolveAllReferences(Node root);
public virtual
Node ResolveReferenceInScope(Node scope,
GraphReference reference);
public virtual
IAsyncResult BeginResolveReferenceInScope(
Node scope,
GraphReference reference,
AsyncCallback callback, object asyncState);
public virtual
Node EndResolveReferenceInScope(IAsyncResult result);
}
}
BeginResolveReferenceInScope and EndResolveReferenceInScope implement the asynchronous pattern for asynchronous invocation of ResolveReferenceInScope. The default resolver is synchronous, but custom resolvers may opt to implement asynchronous resolution.
Rationale: Asynchronous reference resolution allows virtual graph stores to “page in” further parts of a graph without blocking clients that have been written to use the asynchronous version of ResolveReferenceInScope. This is the only asynchronous entry point into graph stores, keeping the overall programming model straight forward.
3.3. GraphStore
Class GraphStore is the abstract base for all graph store implementations. It provides default implementations for most parts of its (very large) surface area, allowing graph store implementations to be gradually enriched to address performance issues.
3.3.1. Graph store clients
Below is the public surface area of GraphStore; writing client code against GraphStore is for advanced scenarios – most use cases should be use the graph model types (Node, Edge, …) instead.
namespace System.Dataflow {
public abstract
class GraphStore {
public virtual
IEqualityComparer<object> KeyComparer { get; }
public virtual
ICollection<Edge> OuterEdges { get; }
public virtual
GraphReferenceResolver ReferenceResolver { get; set; }
public virtual
Node SyntheticSource { get; }
public void
AddContribution(GraphReader reader);
public void
AddContribution(Node node, IEnumerable<Edge> edges);
public virtual
void AddContribution(Node node, Edge edge);
public virtual
void AddPropertyChangedEventHandler(Node node,
PropertyChangedEventHandler eventHandler);
public Node
CreateCollection(Identifier brand, NodeKind kind);
public virtual
Node CreateCollection(Identifier brand, NodeKind kind,
IEnumerable<Node>
nodes);
public virtual
Node CreateCollection(Identifier brand, NodeKind kind,
IEnumerable<Edge> edges);
public virtual
Node CreateConstant(Identifier brand, object value);
public virtual
Node CreateConstant(Identifier brand, byte[] value);
public virtual
Node CreateConstant(Identifier brand, Date value);
public virtual
Node CreateConstant(Identifier brand, DateTime value);
public virtual
Node CreateConstant(Identifier brand,
DateTimeOffset value);
public virtual
Node CreateConstant(Identifier brand, decimal value);
public virtual
Node CreateConstant(Identifier brand, Double value);
public virtual
Node CreateConstant(Identifier brand, Guid value);
public virtual
Node CreateConstant(Identifier brand, int value);
public virtual
Node CreateConstant(Identifier brand, long value);
public virtual
Node CreateConstant(Identifier brand, bool value);
public virtual
Node CreateConstant(Identifier brand); // creates null
public virtual
Node CreateConstant(GraphReference value);
public virtual
Node CreateConstant(Identifier brand, string value);
public virtual
Node CreateConstant(Identifier brand, Time value);
public abstract
Identifier GetBrand(Node node);
public virtual
ConstantClassification GetConstantClassification(
object
value);
public static
ConstantClassification GetConstantClassification(
object
value);
public virtual
bool GetConstantBoolean(Node node);
public virtual
byte[] GetConstantBytes(Node node);
public virtual
Date GetConstantDate(Node node);
public virtual
DateTime GetConstantDateTime(Node node);
public virtual
DateTimeOffset GetConstantDateTimeOffset(Node node);
public virtual
decimal GetConstantDecimal(Node node);
public virtual
double GetConstantDouble(Node node);
public virtual
GraphReference GetConstantGraphReference(Node node);
public virtual
Guid GetConstantGuid(Node node);
public virtual int
GetConstantInt32(Node node);
public virtual
long GetConstantInt64(Node node);
public virtual
string GetConstantString(Node node);
public virtual
Time GetConstantTime(Node node);
public virtual
object GetConstantValue(Node node);
public virtual
IDictionary<Label, Node> GetLabeledEdges(Node node);
public abstract
NodeKind GetNodeKind(Node node);
public virtual
ICollection<Node> GetUnlabeledEdges(Node node);
public Node
NavigateFromRootTo(GraphReference reference);
public
IAsyncResult BeginNavigateFromRootTo(GraphReference reference,
AsyncCallback callback, object asyncState);
public Node
EndNavigateFromRootTo(IAsyncResult asyncResult);
public virtual
Node NavigateTo(Node scope, GraphReference reference);
public virtual
IAsyncResult BeginNavigateTo(Node scope,
GraphReference reference, AsyncCallback callback,
object
asyncState);
public virtual
Node EndNavigateTo(IAsyncResult asyncResult);
public virtual
bool OwnsKey(object key);
public static
GraphStore ReadFrom(TextReader reader);
public static
GraphStore ReadFrom(Func<GraphStore> createDoc,
TextReader
reader);
public static T
ReadFrom<T>(TextReader reader)
where T :
GraphStore, new();
public static
GraphStore ReadFrom(GraphReader reader);
public static
GraphStore ReadFrom(Func<GraphStore> createStore,
GraphReader
reader);
public static T
ReadFrom<T>(GraphReader reader)
where T :
GraphStore, new();
public static
GraphStore ReadFrom(string filePath);
public static
GraphStore ReadFrom(Func<GraphStore> createDoc,
string
filePath);
public static T
ReadFrom<T>(string filePath)
where T :
GraphStore, new();
public static
GraphStore ReadFrom(string filePath, Encoding encoding);
public static
GraphStore ReadFrom(Func<GraphStore> createDoc,
string
filePath, Encoding encoding);
public static T
ReadFrom<T>(string filePath, Encoding encoding)
where T :
GraphStore, new();
public static
GraphStore ReadFrom(Stream stream);
public static
GraphStore ReadFrom(Func<GraphStore> createDoc,
Stream
stream);
public static T
ReadFrom<T>(Stream stream) where T : GraphStore, new();
public static
GraphStore ReadFrom(Stream stream, Encoding encoding);
public static
GraphStore ReadFrom(Func<GraphStore> createDoc,
Stream
stream, Encoding encoding);
public static T
ReadFrom<T>(Stream stream, Encoding encoding)
where T : GraphStore, new();
public static
GraphStore ReadFromString(string text);
public static
GraphStore ReadFromString(Func<GraphStore> createDoc,
string
text);
public static T
ReadFromString<T>(string text)
where T :
GraphStore, new();
public virtual
void RemovePropertyChangedEventHandler(Node node,
PropertyChangedEventHandler eventHandler);
public virtual
void ResolveAllReferences();
public virtual
void SetBrand(Node node, Identifier brand);
public virtual
void SetConstantValue(Node node, object value);
public virtual
void SetEdge(Node node, Label label, Node value);
public virtual
void SetListValue(Node list, int index, Node element);
public virtual
void SetReferenceTarget(Action<Node> nodeVariable,
Node
target);
public virtual
string ToString(Node node);
public void
WriteTo(string filePath);
public void
WriteTo(string filePath, Encoding encoding);
public void
WriteTo(Stream stream);
public void
WriteTo(Stream stream, Encoding encoding);
public void
WriteTo(TextWriter target);
public void
WriteTo(GraphWriter writer);
public virtual
void WriteTo(GraphWriter writer, Node root,
bool
includeRootNode);
public string
WriteToString();
}
}
The SyntheticSource property provides a node that is not technically part of the graph managed by the graph store, but that synthetically gathers all outer edges of the graph. Graph stores may or may not keep track of such outer edges and even if they do, may not do so completely. That is, there may be parts of a graph that are unreachable through any of the outer edges – and thus from the synthetic source node.
Rationale: Providing outer edges enables a general model of disconnected graphs that are still globally reachable. Providing the synthetic source over the collection of outer edges is a convenience mechanism for many graph algorithms that naturally operate from a given single source node.
3.3.2. Adapters for Graph-Pattern Views
Adapters are used by graph stores to possibly provide streamlined, allocation free access and enumeration for specialized views over graph patterns. The adapter design allows for implementations that are stateless singletons – and all default adapters are such singletons.
Adapters map point functions to efficient paths in the store implementation, as available. The default adapters all map to the collection-level getters (and their collection's enumerators).
public virtual GraphStoreNodeCollectionAdapter
GetAdapterForAllNodes(
object
storeKey);
public virtual GraphStoreEdgeCollectionAdapter
GetAdapterForEdges(
object
storeKey);
public virtual GraphStoreListAdapter<Node>
GetAdapterForLists(
object
storeKey);
public virtual GraphStoreDictionaryAdapter
GetAdapterForRecords(
object
storeKey);
public virtual GraphStoreNodeCollectionAdapter
GetAdapterForRecordValues(
object
storeKey);
public virtual GraphStoreListAdapter<Node>
GetAdapterForOrderedNodes(
object storeKey);
public virtual GraphStoreNodeCollectionAdapter
GetAdapterForUnorderedNodes(
object
storeKey);
public virtual GraphStoreListAdapter<Node>
GetAdapterForTuples(
object
storeKey);
The (abstract) adapter classes referenced above provide the protocols of corresponding collection abstractions. The following table shows the correspondence:–
| Collection Type | Graph Adapter |
|---|---|
|
ICollection<Node> |
GraphStoreNodeCollectionAdapter |
|
ICollection<Edge> |
GraphStoreEdgeCollectionAdapter |
|
IList<T> |
GraphStoreListAdapter<T> |
|
IDictionary<Label, Node> |
GraphStoreDictionaryAdapter |
As an example, below is the class GraphStoreNodeCollectionAdapter:–
namespace System.Dataflow {
public abstract
class GraphStoreNodeCollectionAdapter {
public abstract void
Add(GraphStore store, object storeKey, Node item);
public abstract
void Clear(GraphStore store, object storeKey);
public abstract
bool Contains(GraphStore store, object storeKey,
Node item);
public abstract
void CopyTo(GraphStore store, object storeKey,
Node[]
array, int arrayIndex);
public abstract
void Dispose(ref EmbeddableEnumeratorState state);
public abstract
int GetCount(GraphStore store, object storeKey);
public abstract
Node GetCurrent(ref EmbeddableEnumeratorState state);
public abstract
EmbeddableEnumeratorState GetEnumerator(GraphStore store,
object
storeKey);
public abstract
bool IsReadOnly(GraphStore store, object storeKey);
public abstract bool MoveNext(ref
EmbeddableEnumeratorState state);
public abstract
void Reset(ref EmbeddableEnumeratorState state);
public abstract
bool Remove(GraphStore store, object storeKey,
Node item);
}
}
As long as specific enumeration implementations can live with the limited space to encode state afforded by the struct EmbeddableEnumeratorState, all enumeration can be kept allocation-free. However, it is equally simple to just store a reference to a standard (heap-allocated) enumerator in the object reference held by that struct and use that to connect to regular enumerable collections.
namespace System.Dataflow {
public struct
EmbeddableEnumeratorState {
public GraphStore
Store { get; set; }
public object
StoreKey { get; set; }
public object
State { get; set; }
public long Index
{ get; set; }
}
}
3.3.3. Custom graph stores
Class GraphStore implements split/merge mechanisms to enable simple custom graph store implementations while not getting in the way of sophisticated, high-performance ones.
Simple graph stores merely operate in terms of edge collections and GraphStore splits those edge collections into a collection of nodes for unlabeled edges and a dictionary from label to node for labeled edges. From there, it projects mutable views that correspond to the list and tuple graph patterns. The following method illustrates how this is achieved by revealing some of the implementation details of GraphStore:–
protected virtual IList<Node> GetTupleValues(Node
node) {
var coll = new NodeAsSplitCollection { Node =
node };
return new
TupleView(coll);
}
Here, NodeAsSplitCollection is an internal class used by GraphStore to implement a mutable view implementing ISplitCollection over an arbitrary node. This is the splitting step.
namespace System.Dataflow {
public interface
ISplitCollection : IEnumerable<Edge> {
Identifier Brand {
get; }
ICollection<Node> UnlabeledEdges { get; }
bool IsReadOnly {
get; }
IDictionary<Label, Node> LabeledEdges { get; }
}
}
The second step wraps a mutable tuple view (using the internal class TupleView) around the split view, yielding the mutable IList<Node> that represents the tuple elements.
Sophisticated graph stores operate directly in terms of specialized views with an opportunity to fine-tune the representations chosen for each of the standard graph patterns. Class DefaultGraphStore (§3.4) is an example of such a sophisticated implementation that implements the various graph patterns using separate representation classes and that hooks into the GraphStore logic directly at the ISplitCollection level.
Below is the abstract surface area of GraphStore that every graph store has to implement as well as the protected hooking surface to hook subclasses into the default implementations in the base class:–
namespace System.Dataflow {
public abstract
class GraphStore {
protected static
ICollection<Edge> EmptyEdges { get; }
// Valid if
IsNode(node) && GetKind(node) != Reference,
//
Identifier.Empty otherwise. Never returns null or throws.
public abstract
Identifier GetBrand(Node node);
protected virtual
IEnumerator<Edge> GetEdgeEnumerator(Node node);
// Valid if
IsCollection(node), empty immutable collection otherwise.
// Never returns
null or throws.
// post: non-null
collection of pairs, where pair.Key is either null
// or unique; may
be empty
protected abstract
ICollection<Edge> GetEdges(Node node);
// pre:
IsRecord(node) && HasItem(node, label)
protected virtual
Node GetLabeledEdge(Node node, Label label);
// pre:
IsRecord(node)
protected virtual
Node GetLabeledEdgeOrDefault(Node node, Label label);
// Valid if
IsNode(node), empty enumeration otherwise.
// Never returns
null or throws.
protected virtual
IEnumerable<Node> GetLabeledValues(Node node);
// Valid if
IsNode(node), empty enumeration otherwise.
// Never returns
null or throws.
protected virtual
IEnumerable<Label> GetLabels(Node node);
// Valid if
IsList(node), empty immutable list otherwise.
// Never returns
null or throws.
protected virtual
IList<Node> GetListValues(Node node);
// Valid if
IsNode(node), MNodeKind.None otherwise.
// Never returns
null or throws.
public abstract
NodeKind GetNodeKind(Node node);
// Valid if
IsList(node) or IsTuple(node),
// empty immutable
collection otherwise.
// Never returns
null or throws.
protected virtual
IList<Node> GetOrderedValues(Node node);
// Valid if
IsTuple(node), empty immutable list otherwise.
// Never returns
null or throws.
protected virtual
IList<Node> GetTupleValues(Node node);
// Default:
returns GetUnlabeledNodeCollection(node);
// override to
direct contributions to lists/tuples/...
protected virtual
ICollection<Node> GetUnlabeledContributionTarget(
Node node);
// Valid if
IsCollection(node), empty immutable collection otherwise.
// Never returns
null or throws.
protected virtual
ICollection<Node> GetValues(Node node);
// For all Has/Is
tests but IsNode:
// valid if
IsNode(node), false otherwise.
// Never returns
null or throws.
protected virtual
bool HasLabel(Node node, Label label);
// If
IsAtomic(node) then !node.IsDefault && IsNode(node)
// && !IsCollection(node)
protected virtual
bool IsAtomic(Node node);
// If
IsCollection(node) then !node.IsDefault && IsNode(node)
// && IsComposite(node)
protected virtual
bool IsCollection(Node node);
// If IsComposite(node)
then !node.IsDefault && IsNode(node)
// && !IsAtomic(node)
protected virtual
bool IsComposite(Node node);
// If IsList(node)
then !node.IsDefault && IsNode(node) && IsRecord(node)
protected virtual
bool IsList(Node node);
// If
IsRecord(node) then !node.IsDefault && IsNode(node)
// && IsComposite(node)
protected virtual
bool IsRecord(Node node);
// If
IsTuple(node) then !node.IsDefault && IsNode(node)
// && IsRecord(node)
protected virtual
bool IsTuple(Node node);
}
}
The following shows the virtual members of GraphStore, together with the default behavior exposed.
namespace System.Dataflow {
public abstract
class GraphStore {
// Default key
comparer uses object.Equals/GetHashCode
public virtual
IEqualityComparer<object> KeyComparer { get; }
// Default
returns SyntheticSource.Store.GetEdges(SyntheticSource)
public virtual
ICollection<Edge> OuterEdges { get; }
// Initialized
to direct instance of GraphReferenceResolver
public virtual
GraphReferenceResolver ReferenceResolver { get; set; }
// Default
uses ShadowGraphStore to create a composite node
// to hold
outer edges
public virtual
Node SyntheticSource { get; }
// Default coalescing logic; override to
distribute logic elsewhere
// or to
coalesce lazily.
public virtual
void AddContribution(Node node, Edge edge);
// Default:
empty
public virtual
void AddPropertyChangedEventHandler(Node node,
PropertyChangedEventHandler eventHandler);
// Override to
accelerate the case where the collection
// is known to
be constructed over unlabeled edges only
public virtual
Node CreateCollection(Identifier brand, NodeKind kind,
IEnumerable<Node> nodes);
// Override at
least this one method to support store-specific
//
construction. Default throws NotSupportedException, rendering
// the store
essentially read-only.
public virtual
Node CreateCollection(Identifier brand, NodeKind kind,
IEnumerable<Edge> edges);
// By default,
all constants (incl. null) are representing
// themselves
in a graph. Therefore, by default, only the default
// brand is
accepted; otherwise this method throws.
public virtual
Node CreateConstant(Identifier brand, object value);
// The
following methods, by default, just call through the boxing
//
CreateConstant method above. Override to avoid boxing.
public virtual
Node CreateConstant(Identifier brand, byte[] value);
public virtual
Node CreateConstant(Identifier brand, Date value);
public virtual
Node CreateConstant(Identifier brand, DateTime value);
public virtual
Node CreateConstant(Identifier brand,
DateTimeOffset value);
public virtual
Node CreateConstant(Identifier brand, decimal value);
public virtual
Node CreateConstant(Identifier brand, Double value);
public virtual
Node CreateConstant(Identifier brand, Guid value);
public virtual
Node CreateConstant(Identifier brand, int value);
public virtual
Node CreateConstant(Identifier brand, long value);
public virtual
Node CreateConstant(Identifier brand, bool value);
public virtual
Node CreateConstant(Identifier brand); // creates null
public virtual
Node CreateConstant(GraphReference value);
public virtual
Node CreateConstant(Identifier brand, string value);
public virtual
Node CreateConstant(Identifier brand, Time value);
// For adapter
retrieval methods, see §3.3.2
// Default
returns GetConstantClassification(node.StoreKey),
// assuming
that constant values represent themselves.
// Returns
ConstantClassification.Node if value cannot be classified,
// never throws.
public virtual
ConstantClassification GetConstantClassification(
Node node);
// The following
methods share the precondition:
//
IsConstant(node) && GetConstantClassification(node) == ...
// Override to
enable fast access to type-specific atom representations.
public virtual
bool GetConstantBoolean(Node node);
public virtual
byte[] GetConstantBytes(Node node);
public virtual
Date GetConstantDate(Node node);
public virtual
DateTime GetConstantDateTime(Node node);
public virtual
DateTimeOffset GetConstantDateTimeOffset(Node node);
public virtual
decimal GetConstantDecimal(Node node);
public virtual
double GetConstantDouble(Node node);
public virtual
GraphReference GetConstantGraphReference(Node node);
public virtual
Guid GetConstantGuid(Node node);
public virtual int
GetConstantInt32(Node node);
public virtual
long GetConstantInt64(Node node);
public virtual
string GetConstantString(Node node);
public virtual
Time GetConstantTime(Node node);
// Valid if
IsConstant(node), null otherwise, never throws.
public virtual
object GetConstantValue(Node node);
// Valid if
IsNode(node), empty immutable dictionary otherwise.
// Never returns
null or throws.
// Default
constructs a view over the result returned by GetEdges(node)
public virtual
IDictionary<Label, Node> GetLabeledEdges(Node node);
// Valid if
IsCollection(node), empty immutable collection otherwise.
// Never returns
null or throws.
// Default
constructs a view over the result returned by GetEdges(node)
public virtual
ICollection<Node> GetUnlabeledEdges(Node node);
// By default,
only SyntheticRoot (OuterEdges) is mutable.
public virtual
bool IsReadOnly(Node node);
// Default returns
ReferenceResolver.ResolveReferenceInScope
public virtual
Node NavigateTo(Node scope, GraphReference reference);
// Default returns
ReferenceResolver.BeginNavigateTo
public virtual
IAsyncResult BeginNavigateTo(Node scope,
GraphReference reference, AsyncCallback callback,
object asyncState);
// Default returns
ReferenceResolver.EndNavigateTo
public virtual
Node EndNavigateTo(IAsyncResult asyncResult);
// By default, it
is assumed that non-store-specific objects
// can be used as
keys. For instance, stores may represent
// atomic nodes
just by their (possibly boxed) constant value.
// OwnsKey enables
strongly key-owning stores to protect against
// foreign store
keys. However, OwnsKey cannot be used to reliably
// determine the
owner for a store key, unless it is known that
// _all_ queried
stores use strongly owned keys.
public virtual
bool OwnsKey(object key);
// Default: empty
public virtual
void RemovePropertyChangedEventHandler(Node node,
PropertyChangedEventHandler eventHandler);
// Default: calls
//
ReferenceResolver.TryResolveAllReferences(SyntheticSource)
// and throws if
some references cannot be resolved.
public virtual
void ResolveAllReferences();
// pre:
!IsReadOnly(node) && !IsReference(node)
// Default: throw
NotSupportedException
public virtual
void SetBrand(Node node, Identifier brand);
// pre:
!IsReadOnly(node) && IsAtomic(node)
// Default: throw
NotSupportedException
public virtual
void SetConstantValue(Node node, object value);
// pre:
!IsReadOnly(node) && IsCollection(node)
// Default: throw
NotSupportedException
public virtual
void SetEdge(Node node, Label label, Node value);
// pre:
!IsReadOnly(list) && IsList(list)
// Default: throw
NotSupportedException
public virtual
void SetListValue(Node list, int index, Node element);
// pre:
nodeVariable != null && IsNode(target)
// Note: Stores
that ban setting of reference targets need to also
// ban reference
resolution.
// Default: call
nodeVariable(target)
public virtual
void SetReferenceTarget(Action<Node> nodeVariable,
Node
target);
// post: if
string.Empty is returned,
// then no special string encoding is
available.
// (The caller may substitute a default string
value in such a case.)
// Default: builds
a debugger-friendly size-limited summary
// of the graph reachable from the given node.
public virtual
string ToString(Node node);
// Write the
reachable graph from the given node.
// If
includeRootNode, then include the given node, otherwise write
// a sequence of that node’s outgoing edges.
// Default: use
ReferenceResolver.TryBreakAllSharing to convert edges
// into symbolic references as needed to
eliminate sharing and cycles.
public virtual
void WriteTo(GraphWriter writer, Node root,
bool
includeRootNode)
3.4. DefaultGraphStore
The class DefaultGraphStore uses classes DefaultGraphStoreCollectionNode, DefaultGraphStoreCompositeNode, DefaultGraphStoreConstantNode, DefaultGraphStoreListNode, DefaultGraphStoreNode, DefaultGraphStoreRecordNode, and DefaultGraphStoreTupleNode to implement the object model using CLR objects in a direct way. These classes are available to ease the implementation of similar custom graph stores.
Two base classes simplify the construction of similar representation classes: DefaultGraphStoreNode and DefaultGraphStoreCollectionBase.
namespace System.Dataflow {
public abstract
class DefaultGraphStoreNode {
public GraphStore
Store { get; set; }
public bool
IsReadOnly { get; set; }
}
}
All default representations maintain a back link to their store, including the representations that hold atomic values. That is, DefaultGraphStore does not use values to represent themselves, that is, to be their own store key. The uniform back link is used to implement a strong version of GraphStore.OwnsKey in DefaultGraphStore:–
public override bool OwnsKey(object key) {
var node = key as
DefaultGraphStoreNode;
return node != null
&& node.Store == this;
}
Rationale: A strong OwnsKey implementation helps catching errors in initial multi-store graph code. However, such checking is not required and stores may opt to not pay the price to enable such checking.
namespace System.Dataflow {
public abstract
class DefaultGraphStoreCollectionBase
:
DefaultGraphStoreNode, ISplitCollection
{
public static
readonly Label HeadLabel = Label.Get("Head");
public static
readonly Label TailLabel = Label.Get("Tail");
public virtual
Identifier Brand { get; set; }
public virtual
bool IsList { get; }
public virtual
bool IsRecord { get; }
public virtual
bool IsTuple { get; }
public abstract
IDictionary<Label, Node> LabeledEdges { get; }
public abstract
ICollection<Node> UnlabeledEdges { get; }
public virtual
void Add(IEnumerable<Edge> edges);
public virtual
void Add(IEnumerable<Node> nodes);
public virtual
void Add(ILookup<Label, Node> nodesByLabel);
public virtual
IEnumerator<Edge> GetEnumerator();
IEnumerator
IEnumerable.GetEnumerator();
public virtual
ICollection<Node> ViewAllNodes();
public virtual
ICollection<Edge> ViewEdges();
public virtual
IList<Node> ViewAsList();
public virtual
IList<Node> ViewAsTuple();
}
}
Note that the above Add methods assume that coalescing (merging) has already been performed.
The default implementations of View… use the same (internal) view implementations as GraphStore, enabling pointwise implementation of some graph patterns while leaving others to default mechanisms.
3.4.1. Specialized Implementation of Tuple Graph Pattern
Most of the specialized implementations are omitted in this document as their functionality is self evident. However, below are the details of DefaultGraphStoreTupleNode to follow up on the implementation details around the default implementation of the tuple graph pattern (§3.3.3).
namespace System.Dataflow {
public class
DefaultGraphStoreTupleNode : DefaultGraphStoreCollectionBase {
public override
bool IsList { get; }
public override
bool IsRecord { get; }
public override
bool IsTuple { get; }
public override
IDictionary<Label, Node> LabeledEdges { get; }
public override
ICollection<Node> UnlabeledEdges { get; }
public override
void Add(IEnumerable<Edge> edges);
public override
void Add(IEnumerable<Node> nodes);
public override
IEnumerator<Edge> GetEnumerator();
public override
ICollection<Node> ViewAllNodes();
public override
IList<Node> ViewAsList();
public override
IList<Node> ViewAsTuple();
}
}
3.5. Examples
3.5.1. Custom CLR Objects from Graph
The following example shows a simple mapping implementation that builds a web of strongly-typed custom CLR objects, using a two-pass approach to deal with references. In a first pass, a graph is read into a default store, including reference resolution. In a second pass, a custom factory is used to traverse the graph and create a web of objects:–
string villageGraph = @"
{
Villagers =>
{
Jenn => {
Name => 'Jennifer', Age => 28, Spouse => Rich },
Rich => {
Name => 'Richard', Age => 26, Spouse => Jenn },
Charly => {
Name => 'Charlotte', Age => 12 }
},
HaveSpouses =>
{ Villagers.Rich, Villagers.Jenn }
}";
var root = Node.ReadFromString(villageGraph).Single().Node;
// With the graph store fully loaded, references are now
resolved.
// Generate custom objects from graph store, retaining no
back link
// to graph store.
var village = VillageFactory.VillageFromGraph(root);
var jenn =
(from v in
village.Villagers
where v.Name ==
"Jennifer"
select v).Single();
var jennsAge = jenn.Age;
var richsSpouse =
(from v in
village.Villagers
where v.Name ==
"Richard"
select
v.Spouse).Single();
var richsSpousesAge = richsSpouse.Age;
var jennHasSpouse = village.HaveSpouses.Contains(jenn);
var charly =
(from v in
village.Villagers
where v.Name ==
"Charlotte"
select v).Single();
var charlyHasSpouse = village.HaveSpouses.Contains(charly);
Assert.AreEqual(28, jennsAge);
Assert.AreEqual(28, richsSpousesAge);
Assert.IsTrue(jennHasSpouse);
Assert.IsFalse(charlyHasSpouse);
The simple factory used above is shown below. The factory uses a dictionary to ensure that sharing and cycles in the original graph are preserved in the generated object web.
static class VillageFactory {
public static
Village VillageFromGraph(Node root) {
var villagers =
new Dictionary<Node, Villager>();
foreach (var node
in root.Edges["Villagers"].ViewAllNodes()) {
var villager =
GetVillager(node, villagers);
}
var village = new
Village();
foreach (var node
in root.Edges["Villagers"].ViewAllNodes()) {
var villager =
GetVillager(node, villagers);
foreach (var i
in node.ViewAsRecord()) {
switch
(i.Key.Text) {
case
"Age": villager.Age = (int)i.Value; break;
case
"Name": villager.Name = (string)i.Value; break;
case
"Spouse": villager.Spouse = GetVillager(i.Value, villagers);
break;
}
}
village.Villagers.Add(villager);
}
foreach (var node
in root.Edges["HaveSpouses"].ViewAllNodes()) {
village.HaveSpouses.Add(GetVillager(node, villagers));
}
return village;
}
static Villager
GetVillager(Node node,
Dictionary<Node, Villager> villagers)
{
Villager villager;
if
(!villagers.TryGetValue(node, out villager)) {
villagers.Add(node, new Villager());
}
return villager;
}
}
3.5.2. Arbitrary CLR Objects built by Custom Graph Store
This example shows a simple custom graph store that directly builds custom-typed CLR objects.
string villageGraph = @"
Village {
Villagers => {
Jenn =>
Villager { Name => 'Jennifer', Age => 28, Spouse => Rich },
Rich =>
Villager { Name => 'Richard', Age => 26, Spouse => Jenn },
Charly =>
Villager { Name => 'Charlotte', Age => 12 }
},
HaveSpouses =>
{ Villagers.Rich, Villagers.Jenn }
}";
var typeMap = new Dictionary<Identifier, Type> {
{
typeof(Village).Name, typeof(Village) },
{
typeof(Villager).Name, typeof(Villager) }
};
Func<Identifier, Type> typeResolver =
id => {
Type t = null;
typeMap.TryGetValue(id, out t);
return t;
};
var village = ObjectGraphStore.Load<Village>(villageGraph,
typeResolver);
var jenn =
(from v in
village.Villagers
where v.Name ==
"Jennifer"
select v).Single();
var jennsAge = jenn.Age;
var richsSpouse =
(from v in
village.Villagers
where v.Name ==
"Richard"
select
v.Spouse).Single();
var richsSpousesAge = richsSpouse.Age;
var jennHasSpouse = village.HaveSpouses.Contains(jenn);
var charly =
(from v in
village.Villagers
where v.Name ==
"Charlotte"
select v).Single();
var charlyHasSpouse = village.HaveSpouses.Contains(charly);
Assert.AreEqual(28, jennsAge);
Assert.AreEqual(28, richsSpousesAge);
Assert.IsTrue(jennHasSpouse);
Assert.IsFalse(charlyHasSpouse);
The store implementation used above is shown below. It uses an externally provided mapping function (typeResolver in the code above) to map brands to .NET types.
class ObjectGraphStore : GraphStore {
static Edge[]
emptyEdges = new Edge[0];
public virtual
Func<Identifier, Type> TypeResolver { get; set; }
public override Node
CreateCollection(Identifier brand, NodeKind kind,
IEnumerable<Edge> edges)
{
var builder = new
GraphObjectBuilder();
if
(Identifier.IsNullOrEmpty(brand)) {
// All unbranded
collections are forced into lists.
builder.Type =
typeof(List<Edge>);
}
else {
// All branded
collections are forced into specific objects.
Type type =
TypeResolver(brand);
if (type ==
null) {
throw new
NotSupportedException(
"The
specified brand cannot be resovled to a type.");
}
builder.Type =
type;
}
builder.Store =
this;
if (edges != null)
{
foreach (var
edge in edges) { builder.Edges.Add(edge); }
}
return
Node.CreateNodeForStoreKey(this, builder);
}
public override
Identifier GetBrand(Node node) {
var builder =
node.StoreKey as GraphObjectBuilder;
if (builder !=
null) { return Identifier.Get(builder.Type.Name); }
return
Identifier.Empty;
}
protected override
ICollection<Edge> GetEdges(Node node) {
var builder =
node.StoreKey as GraphObjectBuilder;
if (builder ==
null) { return emptyEdges; }
return
builder.Edges;
}
public override
NodeKind GetNodeKind(Node node) {
var builder =
node.StoreKey as GraphObjectBuilder;
if (builder !=
null) { return NodeKind.Record; }
return
NodeKind.Atomic;
}
public static object
GetValue(object key) {
var builder = key
as GraphObjectBuilder;
if (builder !=
null) { return builder.GetObject(); }
return key;
}
public static T
Load<T>(string source, Func<Identifier, Type> typeResolver)
{
var sreader = new
StringReader(source);
var mreader = new
GraphTextReader(sreader);
var store =
GraphStore.ReadFrom(
() => new
ObjectGraphStore { TypeResolver = typeResolver },
mreader);
return
(T)GetValue(store.OuterEdges.Single().Node.StoreKey);
}
}
The custom store above uses the auxiliary class GraphObjectBuilder to build individual objects. Builders build their object at most once, preserving reference identity and thus sharing and cycles in the build web of objects. The builder protocol uses two phases. In the first, the custom store creates one builder per node in the graph, sets each builder’s Type property and populates each builder’s Edges collection. In the second phase, the custom store requests each builder’s object, which triggers the builder to populate those objects’ properties from the Edges collection.
class GraphObjectBuilder {
static Type
edgeCollectionType = typeof(ICollection<Edge>);
ICollection<Edge>
edges = new List<Edge>();
object target;
public
ICollection<Edge> Edges { get { return edges; } }
public Type Type {
get; set; }
public object
GetObject() {
if (target !=
null) { return target; }
target =
Activator.CreateInstance(Type);
if
(edgeCollectionType.IsAssignableFrom(Type)) {
var coll =
(ICollection<Edge>)target;
coll.Clear();
foreach (var m
in Edges) { coll.Add(m); }
}
else {
foreach (var m
in Edges) {
var property =
Type.GetProperty(m.Label.Text);
if (property
== null) {
throw new
NotSupportedException("Only properties can be set.");
}
object value =
ObjectGraphStore.GetValue(m.Node.StoreKey);
if
(edgeCollectionType.IsAssignableFrom(value.GetType())) {
var args =
(ICollection<Edge>)value;
var getter =
property.GetGetMethod();
var coll =
getter.Invoke(target, null);
var adder =
coll.GetType().GetMethod("Add");
foreach (var
a in args) {
var arg =
ObjectGraphStore.GetValue(a.Node.StoreKey);
adder.Invoke(coll, new object[] { arg });
}
}
else {
var setter =
property.GetSetMethod();
setter.Invoke(target,
new object[] { value });
}
}
}
return target;
}
}
3.5.3. Objects Built by Custom Graph Store, no References
If it is known that a graph contains no sharing or cycles, then a very simple custom graph store can be used to build custom object webs directly, in a single pass:–
string villageTree = @"
Village {
Villagers => {
Jenn =>
Villager { Name => 'Jennifer', Age => 28 },
Rich =>
Villager { Name => 'Richard', Age => 26 },
Charly =>
Villager { Name => 'Charlotte', Age => 12 }
}
}";
var village = VillageTreeStore.Load(villageTree);
var jenn =
(from v in
village.Villagers
where v.Name ==
"Jennifer"
select
v).Single();
var jennsAge = jenn.Age;
Assert.AreEqual(28, jennsAge);
The custom store VillageTreeStore used above is shown below. The main constraint that enables its simple form is that it does not support references (and thus reference resolution).
The store does implement the minimally required graph traversal methods. The web of objects can therefore be traversed/inspected as a graph as well. Besides being generally useful, this feature enables this simple store to establish sharing relationships: an already built object can be traversed while building the graph. The resulting graph cannot contain cycles, since the one-pass building approach of this store cannot build an object while deferring resolution of references to objects not yet built. In other words, the graphs buildable by this store are always directed acyclic graphs.
The store virtualizes the graph over the underlying objects in a straightforward way that does not afford updates. The graph is not exactly read-only as it supports the bottom-up addition of new nodes (and thus underlying objects) at any time. However, it does not support mutation of already constructed nodes (the edge collections returned are read-only).
If the underlying objects are directly mutated, then the store will reflect such changes in the virtualized graph’s next traversal. This works because the store itself is stateless. There is no notification mechanism for graph clients though.
class VillageTreeStore : GraphStore {
static readonly
Edge[] emptyEdges = new Edge[0];
public Village
Village {
get { return
SyntheticSource.Edges.First().Node.StoreKey as Village; }
}
public override Node
CreateCollection(Identifier brand, NodeKind kind,
IEnumerable<Edge> edges)
{
if (brand ==
typeof(Village).Name) {
return
CreateVillage(edges);
}
if (brand ==
typeof(Villager).Name) {
return
CreateVillager(edges);
}
if
(Identifier.IsNullOrEmpty(brand)) {
return
CreateEnumerableCollection(edges);
}
throw new
NotSupportedException();
}
Node
CreateEnumerableCollection(IEnumerable<Edge> edges) {
return
Node.CreateNodeForStoreKey(
this,
(edges ??
emptyEdges).Select(m => m.Node.StoreKey));
}
Node
CreateVillage(IEnumerable<Edge> edges) {
var village = new
Village();
foreach (var edge
in edges) {
switch
(edge.Label.Text) {
case
"Villagers":
var
villagers = (IEnumerable)edge.Node.StoreKey;
foreach (var
v in villagers.Cast<Villager>()) {
village.Villagers.Add(v);
}
break;
default:
throw new NotSupportedException();
}
}
return
Node.CreateNodeForStoreKey(this, village);
}
Node
CreateVillager(IEnumerable<Edge> edges) {
var villager = new
Villager();
foreach (var edge
in edges) {
switch
(edge.Label.Text) {
case
"Age":
villager.Age
= (int)edge.Node;
break;
case
"Name":
villager.Name = (string)edge.Node;
break;
default:
throw new
NotSupportedException();
}
}
return Node.CreateNodeForStoreKey(this,
villager);
}
public override
Identifier GetBrand(Node node) {
var key =
node.StoreKey;
if (key is Village
|| key is Villager) { return key.GetType().Name; }
return
Identifier.Empty;
}
protected override
ICollection<Edge> GetEdges(Node node) {
var key =
node.StoreKey;
var village = key
as Village;
if (village !=
null) {
return new
List<Edge> {
new
Edge("Villagers",
Node.CreateNodeForStoreKey(this, village.Villagers))
};
}
var villager = key
as Villager;
if (villager !=
null) {
return new
List<Edge> {
new
Edge("Age", Node.CreateNodeForStoreKey(this, villager.Age)),
new
Edge("Name", Node.CreateNodeForStoreKey(this, villager.Name))
};
}
var coll = key as
IEnumerable;
if (coll != null)
{
return
(from v in
coll.Cast<object>()
select new
Edge(Label.Empty, Node.CreateNodeForStoreKey(this, v)))
.ToList();
}
return
emptyEdges;
}
public override
NodeKind GetNodeKind(Node node) {
var key =
node.StoreKey;
if (key is Village
|| key is Villager) {
return
NodeKind.Record;
}
if (key is
IEnumerable && !(key is string)) {
return
NodeKind.Collection;
}
return NodeKind.Atomic;
}
public static
Village Load(string source) {
return
GraphStore.ReadFromString<VillageTreeStore>(source).Village;
}
}
Note: The techniques used in this example can be combined with the ones used for generic CLR object building exhibited in §3.5.2 to move beyond hard-coded knowledge of specific types. A future version of the SQL Server Modeling CTP may provide more support for such specialized graph store implementations.
4. Graph Readers and Writers
The mapping of graphs from and to serial streams is performed by GraphReader and GraphWriter, respectively. Concrete implementations of these abstract classes are provided for the important special case of text streams: GraphTextReader and GraphTextWriter.
4.1. GraphReader
The GraphReader base class has a low-level bottleneck interface, combined with a set of virtual default implementations built on top (listed separately, further below).
namespace System.Dataflow {
public abstract
class GraphReader : IDisposable {
protected
GraphReader();
// Available for
StartCollection and for
// Constant tokens
if present in the input stream;
//
Identifier.Empty if a brand is not present in the input stream
// for those
tokens; null for other tokens; never throws.
public abstract Identifier
Brand { get; }
// Available for
Constant tokens; ConstantClassification.None otherwise.
public abstract
ConstantClassification ConstantClassification { get; }
// The number of
StartCollections minus number of
// EndCollections,
both counts excluding the current token
public abstract
int Depth { get; }
// Available for
StartCollection and for
// Constant tokens
if present in the input stream;
// Label.Empty if
a label is not present in the input stream
// for those
tokens; null for other tokens; never throws.
public abstract
Label Label { get; }
// See §4.1.1
public
GraphReaderQuotas Quotas { get; }
// Current
position;
// initially
StartStream when a reader is created and no Read() calls
// have been made;
// EndStream once
reader has been advanced past the end of the stream.
public
GraphStreamTokenKind TokenKind { get; }
// Close the
reader and any underlying streams held by it.
public abstract
void Close();
protected virtual
void Dispose(bool disposing);
public void
Dispose();
// Available for
Constant tokens; may throw on parse error.
public abstract
object GetConstant();
// Throws if
current token is EndStream. Otherwise,
advance to
// the next token
and set the Label, TokenKind, TextValue
// and
ConstantKind properties according to the new token.
public abstract
bool Read();
}
}
The set of (mostly virtual) functions built on top of the reader’s bottleneck interface are listed below.
The following set of read methods can be specialized by reader implementations to avoid boxing of values. By default, these all call through ReadConstant, causing values to be boxed.
public virtual bool ReadBoolean();
public virtual byte[] ReadBytes();
public virtual Date ReadDate();
public virtual DateTime ReadDateTime();
public virtual DateTimeOffset ReadDateTimeOffset();
public virtual decimal ReadDecimal();
public virtual double ReadDouble();
public virtual GraphReference ReadGraphReference();
public virtual Guid ReadGuid();
public virtual int ReadInt32();
public virtual long ReadInt64();
public virtual object ReadNull();
public virtual string ReadText();
public virtual Time ReadTime();
The following method allows readers to skip forward over nested non-atomic nodes, while doing minimal work. The reader must be at a Start… token; after the call, the reader will be at the token that is immediately after the matching End… token.
public virtual void Skip();
4.1.1. GraphReaderQuotas
Stream reading opens up systems for potential denial of service attacks. The GraphReaderQuotas class limits the size complexity of streams to preset limits that can be used to curb such attacks.
namespace System.Dataflow {
public class
GraphReaderQuotas {
public int
MaxConstantLength { get; set; }
public int
MaxDepth { get; set; }
public int
MaxLabelLength { get; set; }
public int
MaxReferenceSegments { get; set; }
}
}
The quota setters can only be called while the reader has not yet been used; all limits must be positive values. The following table shows the quotas and their default limits:–
| Quota | Default limit | Purpose |
|---|---|---|
|
MaxConstantLength |
1024 characters |
Maximum acceptable length of serialized constants. |
|
MaxDepth |
32 |
Maximum acceptable nesting depth of non-atomic nodes. |
|
MaxLabelLength |
256 characters |
Maximum acceptable length of serialized labels and brands. |
|
MaxReferenceSegments |
32 |
Maximum acceptable number of segments in a symbolic reference. |
4.1.2. GraphTextReader
Class GraphTextReader exposes almost no new functionality beyond base class GraphReader. It has a set of constructors that support text streams from a number of sources and in a variety of encodings. The one added member is the TextValue property that exposes the source-level textual encoding of the most recently read token, as literally found in the text stream.
namespace System.Dataflow {
public class
GraphTextReader : GraphReader {
public
GraphTextReader(string filePath);
public
GraphTextReader(string filePath, Encoding encoding);
public
GraphTextReader(Stream stream);
public
GraphTextReader(Stream stream, Encoding encoding);
public
GraphTextReader(TextReader reader);
public override
Identifier Brand { get; }
public override
ConstantClassification ConstantClassification { get; }
public override
int Depth { get; }
public override
Label Label { get; }
public virtual
string TextValue { get; }
public override
void Close();
public override
object GetConstant();
public override
bool Read();
public override
void VerifyReaderPosition(
GraphStreamTokenKind requiredTokenKind, Label requiredLabel);
}
}
4.2. GraphWriter
The GraphWriter base class has a low-level bottleneck interface, combined with a set of virtual default implementations built on top (listed separately, further below).
namespace System.Dataflow {
public abstract
class GraphWriter : IDisposable {
// The number of
StartCollections written so far minus number of
// EndCollections
written so far.
public abstract
int Depth { get; }
// The last
written token. Initially, StartStream.
public abstract
GraphStreamTokenKind TokenKind { get; }
// Close the
writer and any underlying streams held by it.
// This should be
idempotent.
public abstract void Close();
protected virtual
void Dispose(bool disposing);
public void
Dispose();
// Flush the
writer and any underlying streams held by it
public abstract
void Flush();
// Write the
specified token. The label paramater may
be
// specified only
for StartCollection, Constant, and Reference
// tokens. The value paramater may be specified only for
// Constant and
Reference tokens.
public void
Write(GraphStreamTokenKind tokenKind,
Label label,
Identifier brand, object value);
protected abstract
void OnWrite(GraphStreamTokenKind tokenKind,
Label
label, Identifier brand, object value);
}
}
The following convenience functions map specific write requests to the common Write bottleneck interface.
public void WriteConstant(Label label, Identifier brand,
object value);
public void WriteEnd();
public void WriteEndCollection();
public void WriteEndComposite();
public void WriteEndRecord();
public void WriteEndList();
public void WriteEndTuple();
public void WriteStart(NodeKind kind, Label label,
Identifier brand);
public void WriteStartCollection(Label label, Identifier
brand);
public void WriteStartComposite(Label label, Identifier
brand);
public void WriteStartRecord(Label label, Identifier brand);
public void WriteStartList(Label label, Identifier brand);
public void WriteStartTuple(Label label, Identifier brand);
The following strongly typed write methods call
WriteConstant by default, causing boxing. They can be overridden to avoid
boxing.
public virtual void WriteBoolean(Label label, Identifier
brand, bool value);
public virtual void WriteBytes(Label label, Identifier
brand, byte[] value);
public virtual void WriteDate(Label label, Identifier brand,
Date value);
public virtual void WriteDateTime(Label label, Identifier
brand,
DateTime
value);
public virtual void WriteDateTimeOffset(Label label,
Identifier brand,
DateTimeOffset
value);
public virtual void WriteDecimal(Label label, Identifier
brand,
decimal value);
public virtual void WriteDouble(Label label, Identifier
brand, double value);
public virtual void WriteGraphReference(Label label,
GraphReference
reference);
public virtual void WriteGuid(Label label, Identifier brand,
Guid value);
public virtual void WriteInt32(Label label, Identifier
brand, int value);
public virtual void WriteInt64(Label label, Identifier
brand, long value);
public virtual void WriteNull(Label label, Identifier
brand);
public virtual void WriteString(Label label, Identifier
brand, string value);
public virtual void WriteTime(Label label, Identifier brand,
Time value);
The following method copies from the current reader's token to the end of the fragment, both inclusive. If the reader started on a StartXxx token, then the fragment ends with the matching EndXxx token, inclusive. Otherwise, just the current token is copied. After the call, the reader will be at the token just after the copied token.
public virtual void Write(GraphReader reader);
4.2.1. GraphTextWriter
Class GraphTextWriter mostly implements GraphWriter. It provides a set of constructors to write to a variety of stream targets, using a variety of encodings. The one added feature allows control over indentation width per nesting level: if set to 0, indentation is turned off.
namespace System.Dataflow {
public class
GraphTextWriter : GraphWriter {
public
GraphTextWriter(string filePath);
public
GraphTextWriter(string filePath, Encoding encoding);
public
GraphTextWriter(Stream stream);
public GraphTextWriter(Stream
stream, Encoding encoding);
public
GraphTextWriter(TextWriter writer);
public override
int Depth { get; }
// The set can be
called only before the first write call.
// The default is
2. A value of 0 value does no indentation.
public int
Indentation { get; set; }
public override
GraphStreamTokenKind TokenKind { get; }
public override
void Close();
public override
void Flush();
protected override
void OnWrite(GraphStreamTokenKind tokenKind,
Label
label, Identifier brand, object value);
}
}
4.3. Examples
string villageGraph = @"
{
Villagers =>
{
Jenn => {
Name => 'Jennifer', Age => 28, Spouse => Rich },
Rich => {
Name => 'Richard', Age => 26, Spouse => Jenn },
Charly => {
Name => 'Charlotte', Age => 12 }
},
HaveSpouses =>
{ Villagers.Rich, Villagers.Jenn }
}";
var input = new
StringReader(villageGraph);
var reader = new
GraphTextReader(input);
reader.Read();
while (reader.Label
!= "Rich") { reader.Read(); }
string name =
"";
int age = 0;
GraphReference
spouse = new GraphReference();
reader.Read();
while
(reader.TokenKind != GraphStreamTokenKind.EndComposite
&&
reader.TokenKind != GraphStreamTokenKind.EndStream)
{
switch
(reader.Label.Text) {
case
"Age": age = reader.ReadInt32(); break;
case
"Name": name = reader.ReadText(); break;
case
"Spouse": spouse = reader.ReadGraphReference(); break;
default: throw
new NotSupportedException("Unsupported label.");
}
}
reader.Close();
Assert.AreEqual("Richard", name);
Assert.AreEqual(26,
age);
Assert.AreEqual("Jenn", spouse.ToString());
