Click here to Skip to main content
Click here to Skip to main content
Go to top

Peer Graph - Search Criteria Helper

, 16 Jan 2006
Rate this:
Please Sign up or sign in to vote.
Expression conversion to XML search criteria for a Peer Graph, using Microsoft's Peer-to-Peer technology.

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 '(Of SearchItem)
  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
      ' operation is always the second item in the list
      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

      ' don't forget the last item
      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
  {
    // convert expression to XML search criteria fragment
    textBox5.Text = 
      Peer.Utility.PeerSearchCriteria.ExpressionToXML(textBox4.Text,
      true);
    search.Xml = textBox5.Text;

    PeerRecordCollection records = search.Search();

    listBox3.Items.Clear();
    propertyGrid1.SelectedObject = null;

    // display the results in the list box
    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:

  1. Peer Name Resolution - Windows Vista Enhancements
  1. Peer Graph - Importing and Exporting a Database
  1. Peer Groups and Identity
  1. Peer Collaboration - People Near Me
  2. Peer Collaboration - EndPoints
  3. Peer Collaboration - Capabilities
  4. Peer Collaboration - Presence
  5. Peer Collaboration - Invitations

If you have suggestions for other topics, please leave a comment.

History

  • Initial revision.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

Adrian_Moore
Web Developer
Canada Canada
Adrian Moore is the Development Manager for the SCADA Vision system developed by ABB Inc in Calgary, Alberta.
 
He has been interested in compilers, parsers, real-time database systems and peer-to-peer solutions since the early 90's. In his spare time, he is currently working on a SQL parser for querying .NET DataSets (http://www.queryadataset.com).
 
Adrian is a Microsoft MVP for Windows Networking.

Comments and Discussions

 
General:)This artles is so good Pinmemberamdk_710-Sep-06 0:51 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web04 | 2.8.140921.1 | Last Updated 16 Jan 2006
Article Copyright 2006 by Adrian_Moore
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid