Background
Microsoft's Peer-to-Peer Graphing technology provides a stable, reliable, and robust infrastructure for Windows peer-to-peer applications to communicate. Peers use Peer Name Resolution Protocol (PNRP - a serverless DNS) to register and discover other peers within the graph. Graphs are the foundation for connecting peers, services, and resources within a peer network. A peer can be a user-interactive application, service, or resource. Graphing allows data to be passed between peers efficiently and reliably.
Microsoft's entire Peer-to-Peer technology is exposed through the latest Platform SDK, as C/C++ API calls. However, the code in this article shows these APIs being used from .NET managed code using C#.
Introduction
This article describes a helper class that allows you to express a search criteria in a more SQL like manner. As we learned in the previous article, searching meta-data within peer records uses a simple XML search criteria. For example:
<peersearch>
<and>
<and>
<clause attrib="creationtime" type="date"
compare="greaterorequal">2005-07-01T00:00:00.0000000-06:00
</clause>
<clause attrib="creationtime" type="date"
compare="lessorequal">2005-09-01T00:00:00.0000000-06:00
</clause>
</and>
<clause attrib="length" type="int"
compare="greater">15000</clause>
</and>
</peersearch>
The helper class described in this article provides a method to convert from a SQL-like expression to the required XML search criteria format. The following expression converts to the XML fragment above:
creationtime between '2005-07-01' and '2005-09-01' and length > 15000
Arguably, this is much easier to read.
The Grammar
First, I'm using the GOLD (Grammar Oriented Language Development) toolkit to represent my grammar. I recommend you read the introductory article I wrote about GOLD several months ago, if you want a better understanding of this technology.
I created a simple grammar that matches the search criteria capabilities. Let's start with the rules that are needed to represent expressions in a way that's similar to the XML search criteria.
<Search List> ::= <Search List> AND <Comparison>
| <Search List> OR <Comparison>
| <Comparison>
A search consists of comparisons. It can be a single comparison like a=1, or multiple comparisons separated by AND or OR.
<Comparison> ::= Identifier LIKE StringLiteral
| Identifier BETWEEN <Value> AND <Value>
| Identifier IN '(' <Value List> ')'
| Identifier '>' <Value>
| Identifier '<' <Value>
| Identifier '<=' <Value>
| Identifier '>=' <Value>
| Identifier '=' <Value> !Equal
| Identifier '<>' <Value> !Not equal
| Identifier '!=' <Value> !Not equal
| '(' <Search List> ')'
There are several kinds of comparisons.
- LIKE compares a value against a string pattern, for example, name LIKE 'James *'.
- BETWEEN determines whether a value is within a range, for example, created BETWEEN '2005-07-01' and '2005-08-01'.
- IN compares a value to a set of literal values, for example, grade IN ('A', 'B', 'C').
- there are the typical comparisons like a=1, a>2, and b!=5.
- comparisons can also be grouped using parentheses to ensure precedence.
Next comes values. Values are literals such as strings or numbers. The numbers can be positive or negative, and either integer or floating point. Note that scientific notation (1.0e+3) is also supported.
<Unary> ::= '-' | '+' |
<Value> ::= <Unary> IntegerLiteral
| <Unary> RealLiteral
| StringLiteral
| CAST '(' <Value> AS <Type> ')'
Values can also be explicitly converted from one data type to another, using CAST. Note that dates are implicitly cast from string; so CAST('1900-01-01' as string) is never needed.
Finally, its worth mentioning that the tokens BETWEEN, IN, CAST, LIKE, AND, and OR are *not* case-sensitive.
PeerSearchCriteria Class
This class implements two, shared (static) methods called ExpressionToXML. The first method takes two parameters; the expression to parse and a boolean to indicate if the XML returned should be nicely indented. The second method takes only the expression parameter and returns un-indented XML.
Public Shared Function ExpressionToXML(ByVal _
Expression As String, ByVal Indent As Boolean) As String
If (Expression.Trim = String.Empty) Then
Return "<peersearch/>"
If _grammar Is Nothing Then
Dim exec As [Assembly] = [Assembly].GetExecutingAssembly
Dim stream As stream = _
exec.GetManifestResourceStream("RecordSearch.cgt")
_grammar = New Grammar(New BinaryReader(stream))
End If
Dim parser As SearchCriteriaParser = _
New SearchCriteriaParser(Expression, _grammar)
If parser.DoParse(New StringReader(Expression)) = _
ParseMessage.Accept Then
Dim xw As New System.Xml.XmlTextWriter(New MemoryStream, _
System.Text.Encoding.Unicode)
If Indent Then xw.Formatting = Xml.Formatting.Indented
xw.WriteStartElement("peersearch")
CType(parser.CurrentReduction.Tag, _
IASTNode).WriteToXML(xw)
xw.WriteEndElement()
xw.Flush()
xw.BaseStream.Position = 0
ExpressionToXML = New StreamReader(xw.BaseStream).ReadToEnd()
Else
Throw New SearchCritieraException(parser.Message)
End If
End Function
Public Shared Function ExpressionToXML(ByVal _
Expression As String) As String
Return ExpressionToXML(Expression, False)
End Function
The ExpressionToXML method first checks for an empty expression string. Next, if this is the first time the method has been called, it primes the rules engine with a compiled, binary version of the grammar from an embedded resource. Next, the parser is created and the expression is parsed. This creates an abstract syntax tree (AST). An AST is a tree of objects where each object (node) represents the tokens of the rules in the grammar. If any errors occur, a SearchCriteriaException is thrown. Otherwise, an XmlTextWriter is created and the AST is traversed starting with the root node. Each node in the AST contributes its XML description of the rule it represents. After traversing the whole tree, the complete XML fragment is built. The XML is extracted and returned as a string.
There are three types of nodes stored in the AST; search list, comparisons, and values. Search list and comparison nodes implement the IASTNode interface which has a single method for generating the XML fragment equivalent to the rule the node represents. For example, the SearchList class below represents the <Search List> rule of the grammar.
Class SearchList
Implements IASTNode
Friend List As New ArrayList
Public Sub New(ByVal item As SearchItem)
List.Add(item)
End Sub
Public Sub Add(ByVal item As SearchItem)
List.Add(item)
End Sub
Public Sub WriteToXML(ByVal xw As System.Xml.XmlTextWriter) _
Implements IASTNode.WriteToXML
Dim item As SearchItem = CType(List(0), SearchItem)
If List.Count = 1 Then
item.WriteToXML(xw)
Else
Dim Operation As String = CType(List(1), _
SearchItem).Operation
xw.WriteStartElement(Operation)
Dim i As Integer = 0
Do
item.WriteToXML(xw)
i += 1
item = CType(List(i), SearchItem)
Loop While i < List.Count - 1
item.WriteToXML(xw)
xw.WriteEndElement()
End If
End Sub
End Class
A search list contains a list of SearchItems. A SearchItem is a comparison plus an operation (AND, OR, or blank). The WriteXML method first checks the number of SearchItems in the list. If there is only one (for example, name = 'Bill'), it calls the SearchItem's WriteXML method. Otherwise, there is a list (for example, name = 'Bill' AND age > 50). Based on the schema rules for searching records, the <and> or <or> tag must be generated first. Within this tag, the WriteXML method loops through the SearchItems in the list. This may result in recursion, but this is handled correctly. Finally, the last item in the list is processed and the end element is written.
A comparison is much simpler. All comparisons are derived from an abstract base class called Comparison.
MustInherit Class Comparison
Implements IASTNode
Public Const EQUAL_COMPARE As String = "equal"
Public Const GREATER_COMPARE As String = "greater"
Public Const LESS_COMPARE As String = "less"
Public Const NOTEQUAL_COMPARE As String = "notequal"
Public Const GREATEROREQUAL_COMPARE As String = "greaterorequal"
Public Const LESSOREQUAL_COMPARE As String = "lessorequal"
Public MustOverride Sub WriteToXML(ByVal xw As _
System.Xml.XmlTextWriter) Implements IASTNode.WriteToXML
Protected Sub WriteClause(ByVal xw As System.Xml.XmlTextWriter, _
ByVal Attrib As String, ByVal Type As String, _
ByVal Compare As String, ByVal Value As String)
xw.WriteStartElement("clause")
xw.WriteAttributeString("attrib", Attrib)
xw.WriteAttributeString("type", Type)
xw.WriteAttributeString("compare", Compare)
xw.WriteString(Value)
xw.WriteEndElement()
End Sub
End Class
The Comparison class declares some string constants for the XML compare names. It also provides a useful method to encapsulate generating the <clause attrib="" type="" compare=""></clause> tag. The following example shows the derived class for the BETWEEN rule.
Class BetweenComparison
Inherits Comparison
Friend Identifier As String
Friend LeftBetween As Value
Friend RightBetween As Value
Public Sub New(ByVal Expr As String, _
ByVal Left As Value, ByVal Right As Value)
Identifier = Expr
LeftBetween = Left
RightBetween = Right
End Sub
Public Overrides Sub WriteToXML(ByVal xw As System.Xml.XmlTextWriter)
xw.WriteStartElement("and")
WriteClause(xw, Identifier, LeftBetween.DataType, _
GREATEROREQUAL_COMPARE, LeftBetween.Value)
WriteClause(xw, Identifier, RightBetween.DataType, _
LESSOREQUAL_COMPARE, RightBetween.Value)
xw.WriteEndElement()
End Sub
End Class
Again, information about the rule is stored; in this case, the identifier and the left and right values. Since BETWEEN implies values within a range, this translates to two comparison clauses within an <and> tag.
The Value class is the simplest. All values are derived from an abstract base class called Value.
MustInherit Class Value
Public Const INT_TYPE As String = "int"
Public Const DATE_TYPE As String = "date"
Public Const STRING_TYPE As String = "string"
Public MustOverride ReadOnly Property Value() As String
Public MustOverride ReadOnly Property DataType() As String
End Class
Constant strings are declared for the XML data types. Derived classes must override methods to indicate their value and data type. The following is the code for the class that represents a date.
Class DateValue
Inherits Value
Private Data As Date
Public Sub New(ByVal v As Date)
Data = v
End Sub
Public Overrides ReadOnly Property DataType() As String
Get
Return MyBase.DATE_TYPE
End Get
End Property
Public Overrides ReadOnly Property Value() As String
Get
Return System.Xml.XmlConvert.ToString(Data)
End Get
End Property
End Class
The DataType property returns the XML string for a date data type. The Value property returns the XML value of a date.
Using the Sample Application
The sample application lets you first create a graph (unsecured peer name 0.SearchSharedFiles) with an initial identity. The first instance should be opened with this identity. It will pause a few seconds looking for other instances, then begin to listen. Each subsequent instance of the application should open the graph with a different identity. These instances will connect to the nearest peer and synchronize. Each instance of the application is a peer.
On the Share tab, use the Add Folder button to select a folder containing files. After selecting a folder, each file in the folder is published to the graph as a record. Note that the record is set to expire after 10 minutes. The attributes of the record are set to the properties of the FileInfo class. Click on a file name in the list box to show the XML attributes associated with the record in the right text box. The lower list shows a diagnostic log of all actions and incoming events. Double-click to clear the list. Note that the windows and system32 folders provide a good set of files for searching.
On the Search tab, enter a search criteria expression. The source code and demo include a file Search Criteria Expression Examples.txt which contains some convenient search criteria expressions for you to copy and paste into the sample application. Click the Search button to issue the search. The expression is quickly converted to its XML format using the helper class and displayed in the upper-right text box. The XML fragment is then passed to the Search method.
private void Search_Click(object sender, System.EventArgs e)
{
PeerSearch search = graph.CreateSearch();
try
{
textBox5.Text =
Peer.Utility.PeerSearchCriteria.ExpressionToXML(textBox4.Text,
true);
search.Xml = textBox5.Text;
PeerRecordCollection records = search.Search();
listBox3.Items.Clear();
propertyGrid1.SelectedObject = null;
foreach (PeerRecord record in records)
{
listBox3.Items.Add(new FileItem(record.DataAsString, record.ID));
}
}
catch (Exception ex)
{
System.Windows.Forms.MessageBox.Show(ex.Message, "Search Failed");
}
}
If an error occurs, a popup dialog shows the error code. Otherwise, the bottom-left list is populated with the names of the files that match the search criteria. Click on this list to show the properties of the record in a property grid.
Points of Interest
Unit Tests
The sample code includes a project with over 40 unit tests to check all kinds of different expressions are correctly converted.
Limitations
Microsoft mentions that the performance of the underlying PeerGraphSearchRecords API is not very efficient. For simple expressions, it's not too bad. However, when you start to use more complex expressions with multiple string patterns, the performance quickly becomes unusable. For example, the following expression:
name in ('a*','b*','c*','d*','e*')
This will either use 100% CPU indefinitely or, after several minutes, result in an error. Due to other bugs, I can't determine yet, whether this has been corrected in Windows Vista.
Links to Resources
I have found the following resources to be very useful in understanding peer graphs:
Conclusion
I hope you have found this article useful. The next article will complete the graphing series by discussing how databases can be imported and exported. Stay tuned for more articles on the following topics:
- Peer Name Resolution - Windows Vista Enhancements
- Peer Graph - Importing and Exporting a Database
- Peer Groups and Identity
- Peer Collaboration - People Near Me
- Peer Collaboration - EndPoints
- Peer Collaboration - Capabilities
- Peer Collaboration - Presence
- Peer Collaboration - Invitations
If you have suggestions for other topics, please leave a comment.
History
