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
This document is intended as a specification for how the search feature in CDT 1.2 will work.
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.
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 fs.
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.
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.
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.
A reference to a type will be a match if that types declaration would have been a match if a search were performed using the same pattern but looking for declarations instead.
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.
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.
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 As 2 levels deep. Similarly, f(*) will search for functions with 1 parameter.
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).
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.
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 |
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