Global Search for GNOME Builder

In previous post, Indexing multiple languages source code in GNOME Builder, I wrote about how indexing of source code in a project is done in GNOME Builder. Now that we have index of all symbols in the project, this index is used to implement global search of symbols using which we can search fuzzily all symbols in the project.

These are features Global search supports now:

  • Searching for symbols which matches fuzzily to given query.
  • Filters can be added while searching. Like if we want to search only functions we need to append function@ to query. Similarly we can also search only  structs, variables, macros, enums, constants and union. This is the syntax,

<any prefix of symbol type>@<query>

This is how global search is implemented. There is fuzzy index of symbols for each directory and in each index <symbol type+unit separator+symbol name, symbol kind, symbol flags, line, column> of each symbol is stored. When a query is given in search bar all indexes will be searched for fuzzy matches and top matches from all of the indexes will be displayed. When every symbol type filter is applied in search query, internally first character of that symbol type and unit separator are preprended to search query and that is used to search fuzzy index. This prepending will automatically removes all other types of symbols from results since when indexing every symbol name is prepended with its type name and unit separator. Current implementation if these features is here GitHub.

This is a demo of these features

Indexing multiple languages source code in GNOME Builder

In previous post, Code Search for GNOME Builder: Indexing, I wrote about how indexing of source code is implemented to support searching symbols in GNOME Builder. After discussing with Christian Hergert, we changed the design of indexing to make it easier to support indexing of source code in languages other than C/C++.

This is the new design,
An interface IdeCodeIndexer is created. This interface will take a source file of a particular language and returns a list of info of symbols present in that file. Returned list of symbols are in form of GListModel. Any class that implements this interface can provide indexing support for a language.

Code Index.png

This is how indexing is done now. CodeIndex plugin will browse working directory recursively and creates index for every directory for which index is not there or index is older than files in that directory. For indexing each directory, each file in that directory will be taken and given to IdeCodeIndexer corresponding to language of that file. CodeIndex plugin will then use list of info of symbols returned by IdeCodeIndexer to create index for that directory. For finding IdeCodeIndexer corresponding to a language CodeIndex plugin will browse through all plugins and check if that plugin implements IdeCodeIndexer interface and supports that language. For checking whether a plugin supports a language or not it will check for value of “X-Ide-Code-Indexer-Languages” key in plugin info.

Adding support for indexing a new language:

If indexing a new language has to be supported then a plugin has to implement IdeCodeIndexer for that corresponding language and add a key-value pair in .plugin file like X-Ide-Code-Indexer-Languages=lang.

Support for indexing C, C++ files:

I implemented IdeCodeIndexer for C, C++ languages in clang plugin. For indexing, first this will create AST of that source file and returns a GListModel backed by this AST. On each g_list_model_get_item request this GListModel will do breadth first search till it finds declaration of a symbol and returns that symbol info. On subsequent g_list_model_get_item requests it will continue breadth first search from where it has stopped previously till it finds declaration of a symbol returns that symbol info. When all symbols are returned g_list_model_get_item will return NULL.

This repo contains code which implements CodeIndex plugin and IdeCodeIndexer in clang plugin.

Code Search for GNOME Builder: Indexing

Goal of Code Search for GNOME Builder is to provide ability to search all symbols in project fuzzily and jump to definition from reference of a symbol in GNOME Builder. For implementing these we need to have a database of declarations. So I created a plugin called ‘Indexer’ in Builder which will extract information regarding declarations and store them in a database.

What information needs to extracted from source code and how?
Since we need to search symbols by their names, names of all declarations needs to be extracted. And we also need to jump to definition of a symbol from a reference of that one, so keys of all global declarations also needs to be extracted. Note that keys of local declarations needs not to be extracted because whenever we want to jump to local definition of a symbol from its reference, that definition will be in current file and it can be easily found by AST of current file. AST is tree representation of source code in which all constructs are represents by tree nodes. We can traverse through that tree and analyse source code. For extracting names and keys of all declarations of a source file, first an AST of source code will be created, next we will traverse through that tree and extract keys and names of all declaration nodes in that tree.

How to store keys and names of declarations?
First I thought of implementing a database which will store keys and names together. After various change of plans currently I am using DzlFuzzyIndex in libdazzle for storing names. And for storing keys I implemented a database IdeSimpleTable that will store strings and an array of integers associated with it. So there will be 2 indexes one for storing names and other for storing keys of declarations.

Indexing Tool

I implemented a helper tool for indexing which will take input a set of files to index, cflags for those files and destination folder in which index files needs to be stored. This will take each file from input, extract names and declarations by traversing AST of that source file and store that in DzlFuzzyIndexand IdeSimpleTable indexes respectively. After indexing this will create 2 files one to store names and other to store keys in destination directory.

GNOME Builder - Indexer

Indexer Plugin

For indexing I implemented a plugin which will create index of source code using above tool and store that in cache folder. This will maintain a separate index for every directory. The reason behind this is if we have a single index for whole project whenever there is single change in project then entire source code needs to be reindexed. This plugin will browse through working directory and indexes a directory only if either index is not there for that directory or index is older than files in that directory. For indexing a directory, it will give list of files in that directory, cflags of those files and destination folder to store index to above tool. After indexing of project is done plugin will load all indexes and be ready for taking queries and process them.

Here is the current implementation of both indexing tool and indexer plugin. Next I will use this index to implement Global Search and Jump to definition.

Code Search for GNOME Builder : GSOC 2017

I am very happy to be part of GNOME and Google Summer of Code 2017. First of all, thank you for all GNOME members for giving me this opportunity and Christian Hergert for mentoring and helping me in this project. In this post I will introduce my project and approach for doing this project.

Goal of the project is to enhance Go to Definition and Global Search in GNOME Builder for C/C++ projects. Currently in GNOME Builder, using Go to Definition one can go from reference of a symbol to its definition if definition is there in current file or included in current file. In this project, Go to Definition will be enhanced and using that one can go from reference of a symbol to its definition which can be present in any file in the project. Global Search will also be enhanced by allowing to search all symbols in the project fuzzily right from search bar.

Approaches:

These are the approaches for implementing Go to Definition and Global Search.

Go to Definition:

In C/C++ files we will have declarations/definitions of various types of symbols like variables, functions, structs, enums, unions, classes, types and many more. Each declaration will have a name and some scope. And no two declarations of same type of symbol in same scope will have same name (with some exceptions like function overloading). Using this idea, a key can be generated for a declaration: key = scope+type+name. So we can use this key to uniquely identify a declaration. Thanks to libclang library which will generate this key for a declaration for making our lives easy.

Lets take 2 files,

1.c

int foo ()
{
  return 0;
}

2.c

int foo ();
int bar ()
{
  int a;
  a = foo ();
  return a;
}

If we want to go to definition of foo() from 2.c : line 5,  first we will go to declaration present in 2.c and generate key for that, key =File Scope+Fucntion+foo = ::F::foo. (Going from a reference to its declaration present in same file can be done by libclang library directly.) Now we will use this key and search in every file for a definition with same key. If search key matches to the key of a definition, then that is definition of our reference. If we form a database of keys of all declarations, then we can search for definition of reference very quickly. This is how Go to definition will be implemented in GNOME Builder.

Global Search:

Goal of this is to search all symbols in the project fuzzily. For doing that, names of all declarations in all files will be extracted by traversing clang AST and stored in a database. When ever we get aquery we will search this database for fuzzy matched. For storing all names, fuzzy index implementation in libdazzle library written by Christian Hergert (mentor for my project) will be used. This is the idea for implementing Global Search.

For doing above two things first an index of code needs to be created. This will be done by creating a new plugin in Builder which will do indexing process.  In conclusion implementation of project is divided into 3 tasks.

  1. Indexing: Creating a plugin which will index project and store that index into hard disk.
  2. Global Search: Implementing an interface which will searching index for a name and show fuzzy matches.
  3. Go to Definition: Implementing an interface which will search index for a key and give location of corresponding definition.

Now I am working on first part and here is the progress in implementation till now patch.  This patch does indexing but few things needs to be improved, like indexing in sub process and not in main process. By completing first part in my next post I will post about how indexing is done.