Eclipse CDT

Search Engine Design

 

Version <1.0>

 

 

 


Revision History

Date

Version

Description

Author

08/07/03

1.0

Initial version

Andrew Niefer

 

 

 

 

 

 

 

 

 

 

 

 

 


Table of Contents

1.     Introduction                                                                                                                                                                              4

1.1      Purpose                                                                                                                                                                         4

2.     Searching using the Dialog                                                                                                                                                    4

2.1      Matching Declarations                                                                                                                                               4

2.1.1    Type                                                                                                                                                                     4

2.1.2    Method & Function                                                                                                                                          5

2.2      Matching References                                                                                                                                                  5

2.3      Matching Definitions                                                                                                                                                  5

2.4      Scopes                                                                                                                                                                           5

2.5      Wildcards                                                                                                                                                                     5

3.     Searching using the context menu                                                                                                                                        5

4.     Search Architecture                                                                                                                                                                 6

4.1      Parser Callback                                                                                                                                                             7

5.     Examples                                                                                                                                                                                    7


Search Engine Design

1.                  Introduction

1.1               Purpose

This document is intended as a specification for how the search feature in CDT 1.2 will work.

2.                  Searching using the Dialog

C++ search will be implemented using a parser callback.  Text entered into the search dialog will need to be interpreted by the search engine in a manner that allows it to decide whether or not objects returned in the parser callbacks match the given pattern.

2.1               Matching Declarations

Text entered into the search pane is scanned to extract the information needed to match a particular element.  In general, names will be either qualified or unqualified.  If the name is unqualified, then all objects matching the name will be returned regardless of their qualification.  Partial qualification can be given to match any fully qualified objects which are a superset of that qualification.

Example:

namespace NSA{

   class A{

      void f ();

   };

}

namespace NSB{

   class A{

      void f ();

   };

}

class A {

  void f();

}

 

Searching for ”f” will find all of NSA::A::f, NSB::A::f, and A::f.  Searching for “A::f” will also find all of them.  Searching for “::A::f” will only find the last A::f, similarily “NSA::A::f” or “NSB::A::f” will only find their respective f’s.

 

 The scanner will be used to tokenize the search text so that the needed information can be extracted.  Most of the items searched for can be matched simply by qualified or unqualified name.  Specific types and methods/functions are more complicated.

2.1.1          Type

The text for searching a type should be of the following form:

Type :  elaborated-type-specifieropt ::opt nested-name-specifieropt type-name

elaborated-type-specifier: class

    struct

                         enum

                         union

nested-name-specifier:  class-or-namespace-name :: nested-name-specifieropt

 

If an elaborated-type-specifier is present, only structures of that type will match, if no elaborated specifier is present, all types (class, struct, enum, union) will be matched.  If a nested-name-specifier is present, only structures whose qualified name contains the combination of nested-name-specifier and type-name will be matched.  If the type-name is given unqualified, then all structures with that name will be matched regardless of their qualification.

 

2.1.2          Method & Function

The pattern to search for a method should be of the following form:

Method: ::opt nested-name-specifieropt method-name parametersopt

parameters:  ( param-declaration-listopt )

param-declaration-list: param-declaration

                        param-declaration, param-declaration-list

The param-list is a list of parameter types that the method must match.  If the parameter list is omitted, then all methods with matching names will be returned.

Correctly interpreting a complete param-declaration without help from the parser will be difficult, so the initial implementation may only support matching type names without checking cv-qualifiers, ptr-operators, etc.

2.2               Matching References

A reference to a type will be a match if that type’s declaration would have been a match if a search were performed using the same pattern but looking for declarations instead.

2.3               Matching Definitions

A method or function definition will be a match if the declaration of that function would have been a match if the search were performed using the same pattern but looking for declarations instead.

2.4               Scopes

During a search starting from the search dialog, the user will have the option of restricting the results to a particular scope.  This scope is different from the C++ concept of scope.  The currently selected resources, the current workspace, or a given working set are all eligible scopes.  A search for an item in a particular C++ scope can be accomplished by using qualified names in the search pattern.

During a context driven search, the hierarchy of the selected element is also available as a search scope.

2.5               Wildcards

The ‘*’ and ‘?’ wildcards can be used in the search pattern.  ‘?’ represents a single letter, and ‘*’ will represent any string.  A ‘*’ will only ever match a single level of qualification, i.e., there is a difference between “::*::A” and “::*::*::A”.  The first matches all types A nested 1 level deep, the second matches A’s 2 levels deep.  Similarly, “f(*)” will search for functions with 1 parameter.

3.                  Searching using the context menu

Eventually, the search will also be able to be launched by highlighting a name in the editor and right clicking to bring up its context menu.  Once the object that has been highlighted has been determined, the search will proceed as if the user did a dialog search and specified the maximum qualifications possible (and for functions, specified all the parameters).

4.                  Search Architecture

The search itself takes place in three stages.  The first stage is to retrieve from the index manager a collection of paths in which we will find what we are searching for.  If the scope that we are searching in is a type hierarchy, then the indexer will also need to provide a list of classes that belong in that hierarchy

The second stage is to parse those files returned from the indexer and collect those items that match.

ICElement objects will be created to store the information about matched AST nodes.  We do not want to hold onto the AST nodes directly since the full AST tree will be quite large for reasonable projects.  Large portions of the AST may be able to be garbage collected before the parse is even complete if we do not keep references to the nodes.

Using ICElements enables us to use existing data structures to store the information we require.  It also helps to simplify aspects of populating the search pane.  Populating the search pane with the results of the search is the last stage.

4.1               Parser Callback

The search engine implements the parser callback ISourceElementRequestor.   Ultimately, what is found by search depends directly on the callbacks coming out of the parser.  Matches are performed during specific callbacks depending on what is being searched for.

 

Declaration

Definition

Reference

Type

enterClassSpecifier

 

acceptClassReference

Method

acceptMethodDeclaration

enterMethodBody

acceptMethodReference

Function

acceptFunctionDeclaration

enterFunctionBody

acceptFunctionReference

Namespace

enterNamespaceDefinition

 

acceptNamespaceReference

Field

acceptField

 

acceptFieldReference

Variable

acceptVariable

 

acceptVariableReference

 

 

5.                  Examples

Given the following code:

namespace NS1{

   class A2 {

      void f3( A4 ){5  };

   }

   class B6 : public A7 {

      B8() {};

   }

}

struct A9 { };

namespace NS210{

   using namespace NS11;

   B12 * b13 = new B14();

   A15::f16( (A17) b18 );

}

 

1.       Find Declaration of NS

2.       Find Declaration of “A” or “NS::A”

3.       Find Declararion of “f” or “A::f” or “NS::A::f”

4.       Find Reference to A declared in 2. ( matches “A” or “NS::A” )

5.       Find Definition of f declared in 3.

6.       Find Declaration of “B” or “NS::B”

7.       Find Reference to A declared in 2.

8.       Find Declaration of constructor B() ( “B” or “B::B” or “NS::B::B”)

9.       Find Declaration of “A” or “::A” or “struct A”

10.   Find Declaration of namespace “NS2”

11.   Find Reference to namespace NS declared in 1

12.   Find Reference to class B declared in 6.

13.   Find Declaration of variable “b”

14.   Find Reference to class B declared in 6.  Also find reference to constructor B() declared in 8.

15.   Find Reference to class A declared in 2

16.   Find Reference to function f declared in 3

17.   Find Reference to class A declared in 2

18.   Find Reference to variable b declared in 13