Code Completion Design

From CodeBlocks
Revision as of 05:53, 21 February 2013 by Ollydbg (Talk | contribs) (Structure of CodeCompletion plugin: add some details.)

Jump to: navigation, search

How to build

Get the source code



Code completion source tree opened in code::blocks

Build the code completion plug-in


Code completion build target option in code::blocks


A brief description of every project files


ccoptionsprjdlg.cpp setting the additional parser search path
classbrowser.cpp viewing the symbols tree ctrl(token tree).
classbrowserbuilderthread.cpp a thread to build the class browser tree above
parser/parser.cpp Parser class was also derived from wxEvtHandler, can start batch parse... this class has member variables like :cbThreadPool m_Pool(which will create a thread from thread pool for each file need passed);TokenTree* m_pTokens(contains all the Token database);
parser/token.cpp definition of the "Token" class, and TokenTree(which means the Token dababase)
parser/searchtree.cpp implement the patricia search tree using by TokenTree
Header files no description needed

Structure of CodeCompletion plugin

Code completion plugin Structure

The above image show the main structure of our CodeCompletion plugins. The main class are:

  • CodeCompletion: this is the class for main plugin), it handle event sent from the C::B core. Toolbar handling was done in this class.
  • NativeParser: as a main member variable of the CodeCompletion class, this class is like the Parser manager class, it create/delete Parser instances when a project load/closed.
  • Parser: this class is mainly for handling Tokens. Parser class hold a TokenTree which record all the Tokens. Parser class also hold a thread pool, it can either run the parsing task in the pool(this means the parsing task will be done in a separate thread), or directly by a function call.
  • Parserthread: The class derived from the worker thread(cbThreadedTask class), it member function DoParse() is the function for parsing.

Besides that, when trying to show the suggestion list(auto completion list, or code completion list), the NativeParser need to analyze the current the current statement structure, and query the symbol(token) information from the Tokentree, this is mostly done in ResolveExpression() member function.

Some important note: when all Parserthread instances finish parsing job in the pool, the thread pool will send an event to its parent(in this case, it is the Parser class), so the Parser know that the parsing is done, or the Parser can assign another parsing jobs to the thread pool.

Low level parser(Lexical analysis, Tokenize)


for a simple c++ program like below

int main()
    return 0;

After tokenizing, it should give these 15 tokens

1 = string "int"
2 = string "main"
3 = opening parenthesis
4 = closing parenthesis
5 = opening brace
6 = string "std"
7 = namespace operator
8 = string "cout"
9 = << operator
10 = string ""hello world""
11 = string "endl"
12 = semicolon
13 = string "return"
14 = number 0
15 = closing brace

Tokenizer class


preparing the big string


Get or Peek a token


    //Get the current token string started from m_TokenIndex, 
    //After that, increase the m_Tokenindex
    wxString GetToken();
    wxString PeekToken();




Cb token cache.png

Nested Value of braces


        if (CurrentChar() == '{')
        else if (CurrentChar() == '}')

SkipUnwanted tokens


a = b + c;



// assignment statement in template arguments
template<class T = int> 
class abc {
 T m_a;
// assignment statement in function arguments
void foo( int arg1 = 60 )
    bla bla;



Return a correct token, Macro replacement


Cc std replacement.png


wxString Tokenizer::MacroReplace(const wxString str)
    wxStringHashMap::const_iterator it = s_Replacements.find(str);
    if (it != s_Replacements.end())
        // match one!
        wxString key   = it->first;
        wxString value = it->second;
        TRACE(_T("MacroReplace() : Replacing '%s' with '%s' (file='%s')."), key.wx_str(), value.wx_str(), m_Filename.wx_str());
        if (value[0]=='+' && CurrentChar()=='(')
            unsigned int start = m_TokenIndex;
            m_Buffer[start] = ' ';
            bool fillSpace = false;
            while (m_Buffer[start]!=')')
                if (m_Buffer[start]==',')
                    fillSpace = true;
                if (fillSpace==true)
                    m_Buffer[start]=' ';
            m_Buffer[start] = '{';
            return value.Remove(0,1);
        else if (value[0] == '-')
            unsigned int lenKey = key.Len();
            value = value.Remove(0,1);
            unsigned int lenValue = value.Len();
            for (unsigned int i=1; i<=lenKey; i++)
                if (i < lenValue)
                    m_Buffer[m_TokenIndex-i] = value[lenValue-i];
                    m_Buffer[m_TokenIndex-i] = ' ';
            int firstSpace = value.First(' ');
            // adjust m_TokenIndex
            m_TokenIndex = m_TokenIndex - lenValue + firstSpace;
            return value.Mid(0,firstSpace);
            return value;
    return str;

Code completion build target option in code::blocks




replacement rules

directly replacement AAAAA -> BBBBB

You can define a rule: AAAAA -> BBBBB

Which means, if the tokenizer meet a string "AAAAA", then it will returned a string "BBBBB"


For example, when

  /// See bits/stl_deque.h's _Deque_base for an explanation.
  template<typename _Tp, typename _Alloc>
    struct _Vector_base
      typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;

We should replace the string "_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)" to "namespace std {", here, we introduce two replacement rules:


In this rule, we firstly replace the "_GLIBCXX_BEGIN_NESTED_NAMESPACE" with the "namespace", then, we reserve the "std", and change the closing parenthesis to an opening brace. (See the image above), also, every token string "_GLIBCXX_END_NESTED_NAMESPACE" will be replaced by "}". CCreplacement rule.png

So, the code becomes to like below:

namespace     std   {
  /// See bits/stl_deque.h's _Deque_base for an explanation.
  template<typename _Tp, typename _Alloc>
    struct _Vector_base


For example, when


We should replace the string "_GLIBCXX_BEGIN_NAMESPACE_TR1" to "namespace tr1 {", here, we introduce two replacement rules:


In this rule, we firstly replace the "_GLIBCXX_BEGIN_NAMESPACE_TR1" with the "namespace", then, add aditional string "tr1 {"

So, the code becomes:

namespace tr1 {

AAAAA -> *

In this case, we call it a "strip the next "(" and ")" rule. for example:

The rule syntax is:


For example, In the source code below:

CVAPI(void) cvFxxxx();
CVAPI(cvMat *) cvFyyy();

will become to (if I add a replacement rule CVAPI -> *)

void cvFxxxx();
cvMat * cvFyyy();

High level parser(Syntax Analysis)

This is the main flow of a parser.

Parser Flow.gif

parser thread


    void  f1();
    int   f2(char c);
    float f3(void * p);
    int   f1;
    double f2;


Token class


class Token  : public BlockAllocated<Token, 10000>
        wxString m_Name;
        wxString m_Args;
        wxString m_AncestorsString; // all ancestors comma-separated list
        unsigned int m_File;
        unsigned int m_Line;
        unsigned int m_ImplFile;
        unsigned int m_ImplLine; // where the token was met
        TokenScope m_Scope;
        TokenKind m_TokenKind;
        bool m_IsOperator;
        bool m_IsLocal; // found in a local file?
        int m_ParentIndex;
        TokenIdxSet m_Children;
        TokenIdxSet m_Ancestors;
        TokenIdxSet m_DirectAncestors;
        TokenIdxSet m_Descendants;



Memory Pool--BlockAllocated class



Operator new overloading for fast allocate in the heap



    return result;


A simple look ahead parser


symbolA symbolB symbolC symbolD;


DoParse Examples

Handling class declaration

The main routing of handling class was in ParserThread::HandleClass function If the parserThread meet these statement

class AAA{
    int m_a;
    int m_b;
} ;

It will surely add a Token of "AAA", it's type is "class".

What about these statements

class AAA{
    int m_a;
    int m_b;
} x,y,z;

The parserThread should firstly add a Token "AAA", then it should regard "x", "y", "z" are three variables of type "AAA". This was done by "ReadVarNames()" function, it will read every comma separated variables after a class declaration.

Handling typedef statement

Sometimes, you can see these code blocks:

typedef class AAA{
    int m_a;
    int m_b;

If the parser meets the keyword "typedef", firstly it set the "m_ParsingTypedef = ture" to indicate that we are parsing a typedef statement.

Next, it meets a keyword "class", which also indicate it is a class declaration. So, the HandleClass function will do the task. A Token of "class AAA" will be added to the TokenTree. Wait a minute, how can we deal with "BBB" and "CCC", this is not the same case as previous code, we can't regard "BBB","CCC" as variables. In this case, another function "ReadClsName()" will be called. For simplicity of TokenTree, we just regard "BBB" and "CCC" as derived class of "AAA".

How does the parserThread know between these two cases. Here is the code:

                if (m_ParsingTypedef)
                    // m_ParsingTypedef = false;
                    m_Str = newToken->m_Name;

That's the whole thing I would like to write about handling class and handling typedef.


Maybe, you would ask a question: where do these Tokens store? The answer is that all the Tokens will be recorded in "TokenTree class".




For example, If you add three item to the TokenTree.



- "" (0)
      \- "p" (4)
              +- "hysi" (2)
              |          +- "cs" (1)
              |          \- "ology" (3)
              \- "sychic" (5)

Animation of Patricia tree


A better animation demo of Patricia tree can be found in Search Tree Viewer. In this page, you can select the tree type, and enter some strings, then the tree will dynamically show in the window.

SearchTree Node



Node Lable


Cb tree node lable.png


How to query a Token by a keyword

The parser collect all the Token information, and stored them in the TokenTree, the GUI function can query keywords from the database to show function tips or to build a Class Browser tree.


void ab()


Flexible Parser structure

The Parser class( in Parser.cpp and Parser.h ) has re-factored to support every project associate with a Parser object (svn revision > 6268 ). Which means: One Parser object per project, so, every project (xxx.cbp) will hold its own Token macro defines and Token trees.

Due to the new introduced conditional preprocessor handling mechanism, the same source file may give different Tokens due to the different macro defines in different project. Also, CC support parsing on the files which does not belong to any project.

  1. You open a project in CB, then all the files belong to the project( related to the project) will be parsed in CC.
  2. Now, you open another file( we call it a "separate file" later) which is not belong to the current project nor any other opened project.
  3. Then the CC will create a "temporary parser" named "NONE“ parser, and add this separate file to the "NONE" parser.
  4. So, you can still see the class tree when viewing the separate file.
  5. Once you close this separate file, the "NONE" parser will automatically be removed.

The main idea is: Now, We can let the CC do parse on some separate files and support class browsing in Symbol browser.

Automatic Code Completion

Find the search scope

CC SearchScope.png


Here are some steps to get the initial(first) search scope:

  • First, you need to correct all the "using namespace XXXX" directives at the beginning the the current source file.(labeled with "A"), this means all the child tokens of "namespace Scintilla" should be searched.

Break up the current statement




Do an AI match


CC AI Match.png

Here is the matching algorithm:



Code completion debugging support

Debug Log output


wxString name;
wxString args;
wxString m_Str;


codeblocks.exe --debug-log


Debug Log output panel

TRACE macro support

As you can see in the source file like "tokenizer.cpp" or "parserthread.cpp", there is a macro definition in the beginning of the source.

    #define TRACE(format, args...) \
        Manager::Get()->GetLogManager()->DebugLog(F(format, ##args))
    #define TRACE2(format, args...)
    #define TRACE(format, args...)                                              \
        do                                                                      \
        {                                                                       \
            if (g_EnableDebugTrace)                                             \
        }                                                                       \
        while (false)
    #define TRACE2(format, args...) \
    #define TRACE(format, args...)
    #define TRACE2(format, args...)

This is a quite complex macro definition. So, if CC_CODECOMPLETION_DEBUG_OUTPUT is defined as 0, these debugging macros were disabled. If CC_CODECOMPLETION_DEBUG_OUTPUT is defined as 1, only the TRACE macro will be defined, so you can plot some messages to the Debug log. It is always the parser will parser many files, so the debug messages will be flooding. If we only interest in the debug message when we are parsing a specific source file, the best way was define CC_CODECOMPLETION_DEBUG_OUTPUT as 2. Now, TRACE macro will plot the message only in one source file. The source file name can be specified in token.cpp

const wxString g_DebugTraceFile = _T("myfile.cpp");

This way, only the debug message when parsing "myfile.cpp" will be traced.

Code-Completion debug tool dialog

When you press shift and ctrl key and double click on any entry of the navigator tree entry, a debug tool dialog will pop up to give a more detail about the selected token. You can query its information such as its member variables, its Ancestors and so on.


Debug Smart Sense log output

When you hold theshift and ctrl key and right click on any entry of the navigator tree entry, the context menu will have a "Debug SmartSense" menu entry shown. You can click it to enable it. See the image blow. Then, all the debug log information when doing an Auto-completion will be shown in the "Debug Log" panel.

Cc debug smartsense.png

Mutexs and lockers in CC

We need lockers to avoid multiply thread issues of wxString. More detailed can be found: wxString and the locker issue in our CC code, to avoid such issue, we need lockers. There are three main kind of lockers. wxMutex s_ParserMutex; wxMutex s_TokenTreeMutex; wxMutex m_ClassBrowserBuilderThreadMutex; The first one was to protect multiply access to Parser objects, this is a static variable. The second one tries to forbid the multiply access to the TokenTree, the last one is used to build the symbol browser tree(usually show in the left docked panels of the C::B main frame)

The associated Macros are below:

// For tracking, either uncomment:
// ...or:
// ..or none of the above.
    // [1] Implementations for tracking mutexes:
    #define THREAD_LOCKER_MTX_LOCK(NAME)                                         \
        CCLogger::Get()->DebugLog(F(_T("%s.Lock() : %s(), %s, %d"),              \
                                    wxString(#NAME, wxConvUTF8).wx_str(),        \
                                    wxString(__FUNCTION__, wxConvUTF8).wx_str(), \
                                    wxString(__FILE__, wxConvUTF8).wx_str(),     \
    #define THREAD_LOCKER_MTX_LOCK_SUCCESS(NAME)                                 \
        CCLogger::Get()->DebugLog(F(_T("%s.Lock().Success() : %s(), %s, %d"),    \
                                    wxString(__FUNCTION__, wxConvUTF8).wx_str(), \
                                    wxString(__FILE__, wxConvUTF8).wx_str(),     \
    #define THREAD_LOCKER_MTX_UNLOCK(NAME)                                       \
        CCLogger::Get()->DebugLog(F(_T("%s.Unlock() : %s(), %s, %d"),            \
                                    wxString(__FUNCTION__, wxConvUTF8).wx_str(), \
                                    wxString(__FILE__, wxConvUTF8).wx_str(),     \
    #define THREAD_LOCKER_MTX_UNLOCK_SUCCESS(NAME)                               \
        CCLogger::Get()->DebugLog(F(_T("%s.Unlock().Success() : %s(), %s, %d"),  \
                                    wxString(__FUNCTION__, wxConvUTF8).wx_str(), \
                                    wxString(__FILE__, wxConvUTF8).wx_str(),     \
    #define THREAD_LOCKER_MTX_FAIL(NAME)                                         \
        CCLogger::Get()->DebugLog(F(_T("%s.Fail() : %s(), %s, %d"),              \
                                    wxString(__FUNCTION__, wxConvUTF8).wx_str(), \
                                    wxString(__FILE__, wxConvUTF8).wx_str(),     \
    // [2] Cumulative convenient macros for tracking mutexes [USE THESE!]:
    #define CC_LOCKER_TRACK_TT_MTX_LOCK(M)    \
    {                                         \
        THREAD_LOCKER_MTX_LOCK(M);            \
        if (M.Lock()==wxMUTEX_NO_ERROR)       \
        else                                  \
          THREAD_LOCKER_MTX_FAIL(M);          \
    {                                           \
        THREAD_LOCKER_MTX_UNLOCK(M);            \
        if (M.Unlock()==wxMUTEX_NO_ERROR)       \
        else                                    \
          THREAD_LOCKER_MTX_FAIL(M);            \
    // [2] Implementations for tracking critical sections:
    #define THREAD_LOCKER_CS_ENTER(NAME)                                         \
        CCLogger::Get()->DebugLog(F(_T("%s.Enter() : %s(), %s, %d"),             \
                                    wxString(__FUNCTION__, wxConvUTF8).wx_str(), \
                                    wxString(__FILE__, wxConvUTF8).wx_str(),     \
    #define THREAD_LOCKER_CS_ENTERED(NAME)                                       \
        CCLogger::Get()->DebugLog(F(_T("%s.Entered() : %s(), %s, %d"),           \
                                    wxString(__FUNCTION__, wxConvUTF8).wx_str(), \
                                    wxString(__FILE__, wxConvUTF8).wx_str(),     \
    #define THREAD_LOCKER_CS_LEAVE(NAME)                                         \
        CCLogger::Get()->DebugLog(F(_T("%s.Leave() : %s(), %s, %d"),             \
                                    wxString(__FUNCTION__, wxConvUTF8).wx_str(), \
                                    wxString(__FILE__, wxConvUTF8).wx_str(),     \
    // [2] Cumulative convenient macros for tracking critical sections [USE THESE!]:
    {                                    \
         THREAD_LOCKER_CS_ENTER(CS);     \
         CS.Enter();                     \
    {                                    \
          THREAD_LOCKER_CS_LEAVE(CS);    \
          CS.Leave();                    \
    #define CC_LOCKER_TRACK_CS_ENTER(CS)     CS.Enter();
    #define CC_LOCKER_TRACK_CS_LEAVE(CS)     CS.Leave();
    #define CC_LOCKER_TRACK_TT_MTX_LOCK(M)   cbAssert(M.Lock()==wxMUTEX_NO_ERROR);
    #define CC_LOCKER_TRACK_TT_MTX_UNLOCK(M) cbAssert(M.Unlock()==wxMUTEX_NO_ERROR);
    #define CC_LOCKER_TRACK_CS_ENTER(CS)     CS.Enter();
    #define CC_LOCKER_TRACK_CS_LEAVE(CS)     CS.Leave();
    #define CC_LOCKER_TRACK_TT_MTX_LOCK(M)   M.Lock();
    #define CC_LOCKER_TRACK_TT_MTX_UNLOCK(M) M.Unlock();

Each mutex need a Lock and Unlock macro, like for mutex for Parser, we need CC_LOCKER_TRACK_P_MTX_LOCK and CC_LOCKER_TRACK_P_MTX_UNLOCK.

Usefull Links

svn co vcfbuilder