#178 CC patch for element access functions belonging to STL containers.

[jat1]

Problem:

CC doesn't work for element access functions/operators belonging to STL containers. For example:

#include <vector>
using namespace std;


vector<string> AAA;
AAA.back().     // doesn't show string tokens
AAA[0].         // doesn't show string tokens

Patch Info:

It fixes the above issue for all STL containers, except std::array and most associative containers (set, unordered_map, etc).

I've attached some test cases. They're in cctest format, but I've not been able to get cctest to work on STL containers. I guess cctest can't handle these? Either way, I've confirmed the tests manually.

Due to the complexity of CC's template related code, I think it would be helpful to have a section on the CC design wiki explaning how it works. I'd be happy to create and add to this section if it sounds like a good idea.

[ollydbg]

Hi, thanks for the contribution, I believe you take a lot of time to debug and test the code, because our CC's source code is not very readable, especially the template related code. Sorry about that. Yes, we need to write some document on this.
The Code Completion Design I wrote was some years ago. The wiki page does not updated much recent years, I mainly add the comment and document directly into CC's source code nowadays.

One idea is to add new section. Another idea is we can write doxygen style document inside the source code, keep the document in another place is a bit hard to maintain.

What's your opinion?

About your patch, I can see that this patch solve problems which is not solved before, the test file is: cc_function_decls.cpp, note that to only test this file, I need to change the copy a file, and rename to ccc_function_decls.cpp, in this case, CCTest only test this ccc_xxxx.cpp file, not the while cc_xxxx files in the folder. (Testing a lot of files need a lot of time, this is because we log all the messages when parsing)

Here is the result:

********************************************************
  Testing in file: F:\cb_sf_git\trunk\src\plugins\codecompletion\testing\ccc_function_decls.cpp
********************************************************
-PASS:  vt[1].  GetInt
-PASS:  g_S.  i
-PASS:  g_  g_S
-PASS:  tc.Vo  Void
-PASS:  tc.St  StaticVoid
-PASS:  tc.GetC  GetClass
-PASS:  tc.GetI  GetInt
-PASS:  str.  size
-PASS:  str.  length
--------------------------------------------------------
Total 9 tests, 9 PASS, 0 FAIL
--------------------------------------------------------

100% passed now, without your patch, I see:

********************************************************
  Testing in file: F:\cb_sf_git\trunk\src\plugins\codecompletion\testing\ccc_function_decls.cpp
********************************************************
*FAIL:  vt[1].  GetInt
-PASS:  g_S.  i
-PASS:  g_  g_S
-PASS:  tc.Vo  Void
-PASS:  tc.St  StaticVoid
-PASS:  tc.GetC  GetClass
-PASS:  tc.GetI  GetInt
-PASS:  str.  size
-PASS:  str.  length
--------------------------------------------------------
Total 9 tests, 8 PASS, 1 FAIL
--------------------------------------------------------

I see a bug that the include search path are not set in the Parser object, so that the ParserThread failed to open and parse inside the #include files.

To solve this bug, I can simpily add one line in the file:

    * CCTest: add include search paths when parser initialized.

----------- src/plugins/codecompletion/cctest/nativeparser_test.cpp -----------
index 5786229..d880458 100644
@@ -208,6 +208,7 @@ void NativeParserTest::Init()
 bool NativeParserTest::ParseAndCodeCompletion(wxString filename, bool isLocalFile)
 {
     Clear();//clear the tree

+    Init();

     bool parseResult = false;
     parseResult = Parse(filename, isLocalFile);

In the Init() function, the include search paths are copied to the Parser object, so this function should be called when we start the parsing.

I have tried your sample test file (renamed it to "ccc_template_patch_2_test.cpp"), but I don't know why all the test get failed.

Again, thanks for the contribution, I think the document(comments) are very important part of a free software open source project, which help people to understand the code, otherwise, they will leave if they can't understand the source code.

[ollydbg]

I have tried your sample test file (renamed it to "ccc_template_patch_2_test.cpp"), but I don't know why all the test get failed.

Remove the last empty line of the file ccc_template_patch_2_test.cpp, so that all the test case can be run in this file, but I still get 100% failed.

About the include search path, you may need to look at the code snippet inside cctest\cctest_frame.cpp, because I need to manually locate the gcc's search paths, see:

    // TODO: Make this base folders configurable
    wxString wx_base (wxT("E:\\code\\cb\\wx\\wxWidgets-2.8.12\\"));
    wxString gcc_base(wxT("E:\\code\\gcc\\pcxmingw463\\" ));
    wxString mingwver(wxT("i686-w64-mingw32"));
    wxString gccver(wxT("4.6.3"));

    m_IncludeCtrl->SetValue(wx_base  + wxT("include")                                                                 + wxT("\n") +
                            wx_base  + wxT("lib\\gcc_dll\\mswu")                                                      + wxT("\n") +
                            gcc_base + wxT("lib\\gcc\\")+mingwver+wxT("\\")+gccver+wxT("\\include\\c++")              + wxT("\n") +
                            gcc_base + wxT("lib\\gcc\\")+mingwver+wxT("\\")+gccver+wxT("\\include\\c++\\") + mingwver + wxT("\n") +
                            gcc_base + wxT("lib\\gcc\\")+mingwver+wxT("\\")+gccver+wxT("\\include\\c++\\backward")    + wxT("\n") +
                            gcc_base + wxT("lib\\gcc\\")+mingwver+wxT("\\")+gccver+wxT("\\include")                   + wxT("\n") +
                            gcc_base + wxT("include")                                                                 + wxT("\n") +
                            gcc_base + wxT("lib\\gcc\\")+mingwver+wxT("\\")+gccver+wxT("\\include-fixed")             + wxT("\n") +
                            gcc_base + mingwver + wxT("\\include")   

In my system, I have one mingw gcc installed in "E:\code\gcc\PCXMinGW463".

[ollydbg]

Good news, I see that I find the reason why your tests fail. That's because our CCTest project does not handle the "namespace" like the one in normal CC plugins. You have some statement "using namespace std;" inside the test file, but CCTest does not even know collect them when it does the AI matches. To solve this issue, a simple way is to change the variable definition to those:

std::vector<info> vec;
std::vector<info*> vec_ptr;
std::deque<info> deq;
std::forward_list<info> frw;
std::list<info> lis;
std::stack<info> sta;
std::queue<info> que;
std::priority_queue<info, vector<info>, mycomp> pri;
std::map<info, info> mpp;

Now, I get such results:

********************************************************
  Testing in file: F:\cb_sf_git\trunk\src\plugins\codecompletion\testing\ccc_template_patch_2_test.cpp
********************************************************
-PASS: mpp[].  m_aaa
-PASS: mpp.at().  m_aaa
-PASS: pri.top().  m_aaa
-PASS: que.front().  m_aaa
-PASS: sta.top().  m_aaa
-PASS: lis.front().  m_aaa
*FAIL: frw.front().  m_aaa
-PASS: deq.front().  m_aaa
-PASS: vec_ptr[]->  m_aaa
-PASS: vec_ptr.at()->  m_aaa
-PASS: vec[].  m_aaa
-PASS: vec.at().  m_aaa
--------------------------------------------------------
Total 12 tests, 11 PASS, 1 FAIL
--------------------------------------------------------

This looks quite good.

[ollydbg]

I debugged a while, I see that you have add the function's return type name. For example, a function top() return a "const_reference", you add this function to the result. And later, the text "const_reference" is changed to a Typedef token, and finally, the actual template argument type is deduced from the Typedef token. So finally, the class info(which is the actual template argument type) are added to the results. So, it's member will be prompted. Am I right? I may need more time to debug to see what is the logic of your patch.

[ollydbg]

BTW, if with out your patch, I get the cctest result below:

********************************************************
  Testing in file: F:\cb_sf_git\trunk\src\plugins\codecompletion\testing\ccc_template_patch_2_test.cpp
********************************************************
-PASS: mpp[].  m_aaa
-PASS: mpp.at().  m_aaa
*FAIL: pri.top().  m_aaa
*FAIL: que.front().  m_aaa
*FAIL: sta.top().  m_aaa
*FAIL: lis.front().  m_aaa
*FAIL: frw.front().  m_aaa
*FAIL: deq.front().  m_aaa
*FAIL: vec_ptr[]->  m_aaa
*FAIL: vec_ptr.at()->  m_aaa
*FAIL: vec[].  m_aaa
*FAIL: vec.at().  m_aaa
--------------------------------------------------------
Total 12 tests, 2 PASS, 10 FAIL
--------------------------------------------------------

But I still don't quite understand the logic about your improvement, sorry, I need more time to debug and test the code.

[ollydbg]

I try to write some comments to describe what the logic of NativeParserBase::ResolveExpression(). Here is what I have wrote, which may help others understand the source code.

// Let's give a simple example here
// namespace AAA
// {
//     class BBB
//     {
//     public:
//         int m_aaa;
//     }
//     class CCC
//     {
//     public:
//         BBB fun();
//     }
// }
// AAA::CCC obj;
// obj.fun().|-----CC here
//
// We first split the statement "obj.fun()." into 3 components:
// component name
// 1, obj
// 2, fun
// 3, empty
//
// We do three loops here, note each loop's result will serve as the next loop's search scope
// Loop 1
// we first search the tree by the text "obj", we find a matched variable token, which has the
// type string "AAA::CCC", then the text "AAA::CCC" is resolved to a class kind token "class CCC"
// Loop 2
// we then search the tree by the text "fun", note here the search scope should be under the result
// from the previous loop, so we find that there is a function kind token under "class CCC", which
// is "function fun()" token. Then we need to see the return type of the fun() token, which is the
// name "BBB". Then we do another text search for "BBB" in the tree, and find a class kind token
// "class BBB"
// Loop 3
// Since the last search text is empty, we just return all the children of the "class BBB" token,
// so finally, we give the child variable kind token "m_aaa", then the code suggestion should prompt
// the string "m_aaa".

It terms out that all we do is searching some "text" in the Token tree under some "scope".

[jat1]

Hi ollydbg, nice work figuring out why cctest wasn't working. Testing manually was getting tedious, so it helps a lot.

As for documentation, I personally prefer to use doxygen. Then the code is directly connected to its documentation, unlike the wiki. I only proposed the wiki because the template code is spread out over multiple classes and functions, so there is no central place to describe how it all works.

However, I've looked over the code again and I can probably do some refactoring to centralize a lot of the template code. Let me create some examples of what this might look like and post them in the forums for review.

I admit my patch is difficult to understand even with my comments. I originally had paragraphs of comments describing how it worked, but the comments were in the middle of NativeParserBase::GenerateResultSet() (because of how the template code is spread out) so they looked out of place. I decided to shorten the comments to what you see in the patch and ask about documentation. I will post a full explanation of how it works below.

You're comments for NativeParserBase::ResolveExpression() look good. They give a good overview of how it works and will be a great improvement over what is currently in the header file.

[jat1]

Here is a full explanation of how the patch works. For the entire explanation, I will be referring to this example:

vector<string> AAA;
AAA.back().             // should display string tokens

Cause of problem:

The root of the problem is that CC can't parse some pieces of the C++ library. STL containers have return types like "const_reference", which users of the library can treat as typedef aliases of their template arguments.

E.g. "back()" returns "const_reference", which we can assume to 
     be a typedef alias of "const string&"

However, these return types are actually defined through a complicated chain of typedefs, templates, and inheritance. For example, the C++ library defines "const_reference" in vector as a typedef alias of "_Alloc_traits::const_reference", which is a typedef alias of
"__gnu_cxx::_alloc_traits<_Tp_alloc_type>::const_reference". This chain actually continues, but it would be too much to list here. The main thing to understand is that CC will not be able to figure out what "const_reference" is supposed to be.

Solution:

Trying get CC to understand this chain would have made the template code even more complicated and error-prone, so I used a trick. STL containers are based on the allocator class. And the allocator class contains all the simple typedefs we need. For example, in the allocator class we find the definition of const_reference:

typedef const _Tp&   const_reference

Where _Tp is a template parameter. Here's another trick - because most STL containers use the name "_Tp" for their template parameter, the above definition can be directly applied to these containers.

E.g. vector is defined as: 
        template <typename _Tp> 
        vector { ... }
So AAA's template map will connect "_Tp" to "string".

So we can look up "const_reference" in allocator, see that it returns "_Tp", look up "_Tp" in the template map and add its actual value to the search scope.

Walking through the example:

[in NativeParserBase::GenerateResultSet()]
CC sees that back() returns const_reference. It searches the TokenTree for const_reference and finds the typedef belonging to allocator:

"typedef const _Tp&   const_reference"

CC then checks that back()'s parent, AAA, is an STL container which relies on allocator. Since it is, this typedef is added to the search scope.

[in NativeParserBase::AddTemplateAlias()]
CC sees the typedef in the search scope. It searches AAA's template map for the actual type of "_Tp" and finds "string". So "string" is added to the scope.

That's the big picture. The negative of this patch is that it relies on how the C++ STL library is written. If the library is ever changed significantly, then this patch will need to be updated. But I thought that was an ok sacrifice to make for cleaner, maintainable code. Thoughts are welcome.

[ollydbg]

Hi, jat1, thanks for your detailed explanation. I understand now. My original thought was that we can create some cctest files which don't have any #include statements in the file. Which means we can put some simplified std containers in a cpp file, so that debug the parser and the codecompletion related code will becomes much easier. About the hack, I'm OK with it, parsing the whole source code is too difficult, and need a lot of semantic check, that's what GCC or clang's job, but for our CC's parser, it could be much simpler and faster.

I think most of explanation can be put into the CC's source code as comments. I also like the Doxygen style comments, the great thing is that our CC's parser can also parse doxygen style comments, and show them in suggestion list.

About the code refactoring, I think some function is too long, and has too many if conditions, such as the NativeParserBase::ResolveExpression(), and some functions are hard to understand, only if I debug the source code, and step by step to see what's done inside the function. Your work on the refactoring of the template related code are very appreciated. Thanks.

About my comments on NativeParserBase::GenerateResultSet(), I will commit them to the trunk as soon as I can, surely in doxygen format.

[ollydbg]

OK, patch, comments, test case all in SVN trunk(r10339) now. Thanks.