Page MenuHomePhabricator

Fix scope-based lookup when more than one function is found.
ClosedPublic

Authored by dawn on Dec 7 2015, 2:57 PM.

Details

Summary

When multiple functions are found by name, lldb removes duplicate entries of functions with the same type, so the first function in the symbol context list is chosen, even if it isn't in scope. This patch uses the declaration context of the execution context to select the function which is in scope.

This fixes cases like the following:

int func();
namespace ns {
    int func();
    void here() {
        // Run to BP here and eval 'p func()';
        // lldb used to find ::func(), now finds ns::func().
    }
}

Diff Detail

Repository
rL LLVM

Event Timeline

dawn updated this revision to Diff 42113.Dec 7 2015, 2:57 PM
dawn retitled this revision from to Fix scope-based lookup when more than one function is found..
dawn updated this object.
dawn set the repository for this revision to rL LLVM.
dawn added a subscriber: lldb-commits.
dawn updated this revision to Diff 42115.Dec 7 2015, 3:12 PM

Updated patch to removed change related to Pascal language - it should be part of a separate patch.

clayborg requested changes to this revision.Dec 7 2015, 4:05 PM
clayborg edited edge metadata.

So one of two things needs to happen here:

  • ClangASTContext::DeclContextCountDeclLevels() becomes a function that is on ClangASTContext only and the opaque arguments get changed into "clang::DeclContext *" args, then remove all DeclContextCountDeclLevels functions from TypeSystem.h and GoASTContext.h.
  • Change ClangASTContext::DeclContextCountDeclLevels() over to use CompilerDeclContext objects for both "void *opaque_decl_ctx" and "void *opaque_find_decl_ctx" and add any functions you need to do CompilerDeclContext that is needed to complete the functionality of this function without downcasting to clang objects.

So either make it generic, or clang specific.

I would vote for the first method since this functionality is very clang and C++ specific. It doesn't seem like a nice general purpose function any other language would use. If you do go the second route, you really need to abstract the heck out of this and add any needed methods to CompilerDeclContext.

source/Plugins/ExpressionParser/Clang/ClangExpressionDeclMap.cpp
1443 ↗(On Diff #42115)

"compiler_decl_context" should probably be named "frame_decl_ctx" for clarity

1467–1468 ↗(On Diff #42115)

Why are we pulling out class methods here?

1485 ↗(On Diff #42115)

There is no need for this lamba, inline the code at the one and only place that it is used.

1505–1509 ↗(On Diff #42115)

Seems like you actually want this to be something like:

fdi.m_func_decl_lvl = func_decl_context.Depth(compiler_decl_context);

This would be a function on CompilerDeclContext that would calculate the depth of a decl context if the first argument (compiler_decl_context) is contained within the object (func_decl_context). This would be a useful API to add to CompilerDeclContext. It can return an integer and return "-1" if the compiler_decl_context ins't contained within func_decl_context, or zero or greater if it is.

Then you would need to add more functions the CompilerDeclContext to get "fdi.m_function_name" and "fdi.m_copied_function_type".

1517 ↗(On Diff #42115)

wouldn't this be better as std::multimap<uint32_t, FuncDeclInfo> where the uint32_t is the depth? Then you can change your foo loop at 1531 to just grab the first entry in the map and iterate as long as the depth is the same...

1524 ↗(On Diff #42115)

inline the initFuncDeclInfo lambda here without needing a lambda

This revision now requires changes to proceed.Dec 7 2015, 4:05 PM
dawn added a comment.EditedDec 8 2015, 2:02 AM

Thanks Greg! To address your main point:

So either make it generic, or clang specific.

DeclContextCountDeclLevels's interface follows DeclContextFindDeclByName (authored by Paul Herman). If DeclContextCountDeclLevels is to change, then DeclContextFindDeclByName should also change for consistency.

My take on this is that the code in ClangExpressionDeclMap::FindExternalVisibleDecls which calls these scope-based lookup routines should be moved out of ClangExpressionDeclMap.cpp into CompilerExpressionDeclMap.cpp, so the interfaces to DeclContextFindDeclByName/DeclContextCountDeclLevels should remain generic while the implementations are compiler specific. That's way more than I'd like to take on as part of this patch however.

Paul, any feedback from you on this?

tberghammer added a subscriber: tberghammer.

Paul is not working on LLDB anymore so I added Siva who took over most of his work.

So one thing I don't want to propagate here is the "go parse everything inside a decl context" if we can avoid it. I believe the first CompilerDeclContext patch did this, but I don't remember the exact details so I could be wrong. But going forward I would like to see more of "find a struct named 'X' in CompilerDeclContext 'Y'" queries, instead of "parse everything in CompilerDeclContext 'Y' and then I would look for 'X'". Or if we know what we are looking for (function decl contexts and lexical block decl contexts in this case), then I would prefer to have "go parse all function and block decl contexts in CompilerDeclContext 'Y'".

I am not sure if doing all of the parsing lazily is the good approach because of speed considerations.

The problem is that if we do everything lazily then in one side we are parsing only the information what we need but on the other side it is very difficult (or impossible) to make it multi threaded. In case of a high end machine I think doing the parsing in 8-16 core (or even more) can be faster then the lazy approach if we have to parse a lot of information anyway.

I don't have any measurements but looking into the direction we are heading now we will need to parse more and more information to improve the expression evaluation (e.g. to support limit debug info) and to get it a parse a lot of thing upfront might be a better approach. In terms of the performance I expect it to be a small to medium difference (not sure about memory) but will speed up the debugging experience later. For me it is more annoying when I have to wait to evaluate an expression then to wait for the debugger to start up.

That does make sense. Lets ignore the partial parsing until we find a performance problem that needs to be fixed.

By I really do want to see the API on CompilerDeclContext and CompilerDecl get a lot more member functions that can do useful things now that we have this infrastructure.

In D15312#304652, @dawn wrote:

Thanks Greg! To address your main point:

So either make it generic, or clang specific.

DeclContextCountDeclLevels's interface follows DeclContextFindDeclByName (authored by Paul Herman). If DeclContextCountDeclLevels is to change, then DeclContextFindDeclByName should also change for consistency.

Indeed it should be. It should return a vector of CompilerDecl objects.

My take on this is that the code in ClangExpressionDeclMap::FindExternalVisibleDecls which calls these scope-based lookup routines should be moved out of ClangExpressionDeclMap.cpp into CompilerExpressionDeclMap.cpp, so the interfaces to DeclContextFindDeclByName/DeclContextCountDeclLevels should remain generic while the implementations are compiler specific. That's way more than I'd like to take on as part of this patch however.

I would still like to see your new ClangASTContext::DeclContextCountDeclLevels() broken up into one or more functions that are more useful on CompilerDeclContext. In my previous comment I mentioned a new CompilerDeclContext that could be used to get the depth:

int32_t CompilerDeclContext::GetDepth (const CompilerDeclContext &decl_ctx);

This would get the depth of one CompilerDeclContext within another CompilerDeclContext, it would return -1 if "decl_ctx" doesn't fall within the object, and zero or above it is is contained.

Not sure how to break out the other thing with the name and type, but thing about what would make a good API on CompilerDeclContext and what questions you might ask of it. The DeclContextCountDeclLevels seems to be too specific.

Paul, any feedback from you on this?

We should be using our CompilerDecl and CompilerDeclContext objects. No one should be using opaque pointers outside the API unless you are making the objects or changing the contained decl/decl context.

BTW: I fixed DeclContextFindDeclByName to return a vector of CompilerDecl objects:

% svn commit
Sending include/lldb/Symbol/ClangASTContext.h
Sending include/lldb/Symbol/GoASTContext.h
Sending include/lldb/Symbol/TypeSystem.h
Sending source/Symbol/ClangASTContext.cpp
Sending source/Symbol/CompilerDeclContext.cpp
Sending source/Symbol/TypeSystem.cpp
Transmitting file data ......
Committed revision 255038.

dawn added a comment.Dec 8 2015, 3:12 PM

Greg: But going forward I would like to see more of "find a struct named 'X'

in CompilerDeclContext 'Y'" queries, instead of ...

I think lldb should have both, a "search for anything named foo in my scope context" (for when a user does "p foo"), and a "search for a thingy (functions/types/variables/etc.) named foo in my scope context" (for when a user does "expr --type function -- foo").

tberghammer: I am not sure if doing all of the parsing lazily is the good approach because of speed considerations. ... looking into the direction we are heading now we will need to parse more and more information to improve the expression evaluation

Agreed.

Greg:

int32_t CompilerDeclContext::GetDepth (const CompilerDeclContext &decl_ctx);

This would get the depth of one CompilerDeclContext within another CompilerDeclContext, it would return -1 if "decl_ctx" doesn't fall within the object, and zero or above it is is contained.

The problem with this is that it won't work for using declarations which require information about the thing we're looking up before it can determine the proper scope levels.

BTW: I fixed DeclContextFindDeclByName to return a vector of CompilerDecl objects:

Cool, but it needs to accept an optional type to deal with function overloading. I can add that and see if I can come up with a new patch that uses the new DeclContextFindDeclByName. (In my copious spare time - heh). But...

One major performance benefit of my original implementation is that the function's name and type *only* need to be tested in the case of a using declaration, so in general it's much faster, because we only need to look for the function's parent's lookup scope. So, are you sure you want to go down this path?

In D15312#305392, @dawn wrote:

Greg: But going forward I would like to see more of "find a struct named 'X'

in CompilerDeclContext 'Y'" queries, instead of ...

I think lldb should have both, a "search for anything named foo in my scope context" (for when a user does "p foo"), and a "search for a thingy (functions/types/variables/etc.) named foo in my scope context" (for when a user does "expr --type function -- foo").

That is fine.

tberghammer: I am not sure if doing all of the parsing lazily is the good approach because of speed considerations. ... looking into the direction we are heading now we will need to parse more and more information to improve the expression evaluation

Agreed.

Greg:

int32_t CompilerDeclContext::GetDepth (const CompilerDeclContext &decl_ctx);

This would get the depth of one CompilerDeclContext within another CompilerDeclContext, it would return -1 if "decl_ctx" doesn't fall within the object, and zero or above it is is contained.

The problem with this is that it won't work for using declarations which require information about the thing we're looking up before it can determine the proper scope levels.

BTW: I fixed DeclContextFindDeclByName to return a vector of CompilerDecl objects:

Cool, but it needs to accept an optional type to deal with function overloading. I can add that and see if I can come up with a new patch that uses the new DeclContextFindDeclByName. (In my copious spare time - heh). But...

No rush for sure...

One major performance benefit of my original implementation is that the function's name and type *only* need to be tested in the case of a using declaration, so in general it's much faster, because we only need to look for the function's parent's lookup scope. So, are you sure you want to go down this path?

If you want to make this patch general then yes, but I wouldn't recommend it.

The functionality that you need is very specific to clang and your original implementation it just fine, I would say to just make a clang specific function that does exactly what you need and is only on ClangASTContext. We have discovered by our conversations above that the stuff you want to do doesn't map well onto CompilerDeclContext or CompilerDecl. Our needs are just too specific. So I vote to remove all code from TypeSystem.h and GoASTContext.h, change the version in ClangASTContext.h to be:

uint32_t
CountDeclLevels (clang::DeclContext *decl_ctx,
                             clang::DeclContext *child_decl_ctx,
                             ConstString *find_name = nullptr,
                             CompilerType *find_type = nullptr) override;

And just do what you need to do as efficiently as you need to. When you are in ClangExpressionDeclMap.cpp you know that your type system is a ClangASTContext already, so you should be able to just use your existing AST.

My whole aversion to the previous solution was you were putting very specify clang stuff into an API (TypeSystem) that is designed to be language agnostic.

dawn marked 6 inline comments as done.Dec 9 2015, 11:36 AM

Hi Greg, I'm working on a new revision to change the patch as you suggest (thanks for your review - you had some great suggestions!).

Sorry, if I'm missing something obviously here, but there's still some things I don't understand:

  1. What exactly was clang specific about the DeclContextCountDeclLevels API?
  2. How is it anymore clang specific than DeclContextFindDeclByName?

Anyway, I didn't want to drag this out any longer so am making the code clang specific. We can always generalize it in the future (I want it for Delphi).

source/Plugins/ExpressionParser/Clang/ClangExpressionDeclMap.cpp
1467–1468 ↗(On Diff #42115)

To save time - they're thrown out by the loop that actually adds the functions which follows this, so no point in spending time on them.

1505–1509 ↗(On Diff #42115)

As mentioned in prior discussions, this API is basically what you are suggesting. The name and type are not returned - they are optional inputs into the function to allow for languages which support using declarations (because using declarations need to check type and/or name). For example, in Delphi where using declarations are not supported, these would default to nullptr.

1517 ↗(On Diff #42115)

That won't work because we can have functions at more than one level that we'll want to keep in our set. Using std::multimap<type, FuncDeclInfo> might help to clean things up a little however - will give it a try.

In D15312#306201, @dawn wrote:

Hi Greg, I'm working on a new revision to change the patch as you suggest (thanks for your review - you had some great suggestions!).

Sorry, if I'm missing something obviously here, but there's still some things I don't understand:

  1. What exactly was clang specific about the DeclContextCountDeclLevels API?

CountDeclLevels doesn't really tell me what the function does. For abstract APIs I would expect an API like:

int CompilerDeclContext::GetDeclDepth (const CompilerDeclContext &child_decl_ctx);

That makes sense. It seems like you combined "find this decl instance within a decl context" with "find a decl by name in the CompilerDeclContext and optionally get the type". This is what I didn't like about API you added. It was too specialized and didn't make for good API on the CompilerDeclContext class. The class name "CountDeclLevels" didn't really say what this function would do for me. What levels? Is level 10 better than level 1? Why would I supply a name to this function if I am trying to find a specific decl (from opaque_find_decl_ctx)? Why does this function not work if I supply a type to fill in (CompilerType *find_type = <valid_ptr>) but not a name (ConstString *find_name == nullptr)? I am still unclear as to exactly what this function does even after reading it many times.

  1. How is it anymore clang specific than DeclContextFindDeclByName?

This is generic. In any CompilerDeclContext, you can find one or more decls by name. That makes sense to me:

CompilerDeclContext decl_ctx = ...;
std::vector<CompilerDecl> decls = decl_ctx.FindDeclByName("hello");

That makes sense in any language.

Anyway, I didn't want to drag this out any longer so am making the code clang specific. We can always generalize it in the future (I want it for Delphi).

You sure can, you will need to make sure the APIs make sense though. I am still unclear as to what the name and type are doing in DeclContextCountDeclLevels. I don't see how we would ever have a decl (in opaque_find_decl_ctx) that isn't unique where the same decl could have different names and different types?

Above I meant to say I don't understand what the "else if (find_name)" does. I understand the rest of it. So in the "else if (find_name)" we are looking for any decl, regardless of wether it matches "opaque_find_decl_ctx" as long as the name and type are correct? Again if I understand it correctly, these should be two different searches. One for find the depth of this within this decl context, and the other being find all decls by name within an decl context (which we already have), and then check to see if those decls match in kind and type.

dawn marked 3 inline comments as done.Dec 9 2015, 8:29 PM

It seems like you combined "find this decl instance within a decl context" with "find a decl by name in the CompilerDeclContext and optionally get the type".

It it exactly "find this decl instance within a decl context".

I am still unclear as to what the name and type are doing in DeclContextCountDeclLevels. I don't see how we would ever have a decl (in opaque_find_decl_ctx) that isn't unique where the same decl could have different names and different types?

The optional name is required by languages (like C++) to handle using declarations like:

void poo();
namespace ns {
    void foo();
    void goo();
}
void bar() {
    using ns::foo;
    // Here, 'foo' is needed so that we can match it
    // with the using declaration.
    //
    // We want the API to return 0 for 'foo',
    // -1 for 'goo', and 1 for 'poo'.
}

The optional type might be required by languages which have a using declaration-like concept where a type can be specified, like:

void foo(int, int);
namespace ns {
    void foo();
    void foo(int);
}
void bar() {
    using_like ns::foo(int);
    // Here, 'foo' and its type are both needed so that
    // we can match it with the using_like declaration.
    //
    // We want the API to return 0 for { 'foo', 'void(int)' },
    // -1 for { 'foo', 'void()' },
    // and 1 for { 'foo', 'void(int, int)' },
}

The name and type are optional (default to 0) for languages which don't have these concepts.

dawn updated this revision to Diff 42375.Dec 9 2015, 9:19 PM
dawn edited edge metadata.

This version of the patch makes the API specific to clang.

dawn updated this revision to Diff 42385.Dec 9 2015, 10:03 PM
dawn edited edge metadata.

This version of the patch is the API "generic" version of the patch. Please choose to review which ever is preferred, and I will submit another patch based on that version if needed.

BTW Greg, thanks for the suggestion of multimap - it definitely simplified things! And if you're wondering why we want to keep a set of functions for each type in FindExternalVisibleDecls, it's because overload resolution hasn't chosen a function yet, so we must keep all possible candidates in our set.

I like the clang specific patch here better. Mainly because if you add a function like this to TypeSystem.h:

virtual uint32_t
DeclContextCountDeclLevels (void *opaque_decl_ctx,
                            void *opaque_find_decl_ctx,
                            ConstString *find_name = nullptr,
                            CompilerType *find_type = nullptr) = 0;

It means that you will have a function in the CompilerDeclContext named "CountDeclLevels(...)". The "DeclContext" prefix is the convention in TypeSystem.h that says "I will add a corresponding function to CompilerDeclContext that will call through to this function.

I still like the clang specific version better because I still think it doesn't make a sensible API for CompilerDeclContext.

Greg

dawn updated this revision to Diff 42476.Dec 10 2015, 4:14 PM

Updated Clang-specific version of patch.

clayborg accepted this revision.Dec 11 2015, 9:34 AM
clayborg edited edge metadata.
This revision is now accepted and ready to land.Dec 11 2015, 9:34 AM
This revision was automatically updated to reflect the committed changes.
labath added a subscriber: labath.Dec 14 2015, 3:15 AM

Hi,

all of the new tests in TestNamespaceLookup were failing on linux, against all tested compilers (http://lab.llvm.org:8011/builders/lldb-x86_64-ubuntu-14.04-cmake/builds/9405), so I have XFAILed them. I don't know if this is something you're interested about, but I thought I'd point out that now all test in this file are marked as XFAIL on linux.