Add scope tree for variable searching

[paulherman]

Summary

The idea is to structure the scopes as a tree. A scope is either a lexical block, a function or a compile unit. Each scope is a node in the tree and is represented by the class VariableType. It has a list of variables declared in it and a list of imported variables (for example by importing a namespace). To search for a variable when evaluating an expression we go up through the tree starting from the node representing the current lexical block until we either find a variable or we encounter a NULL node (the parent of a CU is NULL).

The imported variables for each scope are parsed when the variables for the scope is parsed. This is done by the ParseNamespace method in SymbolFileDWARF which is called by ParseVariablesForContext for the compile unit and by ParseVariables for the other scopes. A special case is anonymous namespaces which should be imported to the compile unit.

[paulherman]

Add scope tree for variable searching

[paulherman]

Add scope tree for variable searching

[paulherman]

Add scope tree for variable searching

[paulherman]

Add scope tree for variable searching

[paulherman]

Add scope tree for variable searching

[paulherman]

Add scope tree for variable searching

[clayborg]

This seems to be very variable specific.

I would like to see if be able to ask a lldb_private::Block or a lldb_private::Compile and to provide a list of CompilerDeclContext objects that can be then searched by the expression parser in FindExternalVisibleDecls by searching these decl contexts starting with the block and each block's parent and then checking the compile unit. Then we don't need any variable trees as we can currently request thing (functions, globals, and other things) that have a specific CompilerDeclContext as their parents.

Basically if we implement this, I would rather not see it just be for variables. I want functions, variables, and more to work as expected.

include/lldb/Symbol/Block.h

public:
     void
     FinalizeRanges ();
 
     //------------------------------------------------------------------
     /// @copydoc SymbolContextScope::CalculateSymbolContext(SymbolContext*)
     ///
     /// @see SymbolContextScope
     //------------------------------------------------------------------
+    virtual SymbolContextScope *
+    GetParentSymbolContextScope ();
+
+    virtual lldb::VariableTreeSP
+    GetVariables ();
+
     virtual void
     CalculateSymbolContext(SymbolContext* sc);
 
     virtual lldb::ModuleSP
     CalculateSymbolContextModule ();
 
     virtual CompileUnit *
     CalculateSymbolContextCompileUnit ();
protected:
     //------------------------------------------------------------------
     // Member variables.
     //------------------------------------------------------------------
     SymbolContextScope *m_parent_scope;
     collection m_children;
     RangeList m_ranges;
     lldb::InlineFunctionInfoSP m_inlineInfoSP; ///< Inlined function information.
     lldb::VariableListSP m_variable_list_sp; ///< The variable list for all local, static and parameter variables scoped to this block.
+    lldb::VariableTreeSP m_variable_tree_sp;
     bool m_parsed_block_info:1,         ///< Set to true if this block and it's children have all been parsed
          m_parsed_block_variables:1,
          m_parsed_child_blocks:1;
 
     // A parent of child blocks can be asked to find a sibling block given
     // one of its child blocks
     Block *
     GetSiblingForChild (const Block *child_block) const;

include/lldb/Symbol/CompileUnit.h

public:
     void
     AddFunction(lldb::FunctionSP& function_sp);
 
     //------------------------------------------------------------------
     /// @copydoc SymbolContextScope::CalculateSymbolContext(SymbolContext*)
     ///
     /// @see SymbolContextScope
     //------------------------------------------------------------------
+    virtual lldb::VariableTreeSP
+    GetVariables ();
+
+    virtual SymbolContextScope *
+    GetParentSymbolContextScope ();
+
     virtual void
     CalculateSymbolContext(SymbolContext* sc);
 
     virtual lldb::ModuleSP
     CalculateSymbolContextModule ();
     
     virtual CompileUnit *
     CalculateSymbolContextCompileUnit ();
protected:
     std::vector<lldb::FunctionSP> m_functions; ///< The sparsely populated list of shared pointers to functions
                                          ///< that gets populated as functions get partially parsed.
     std::vector<ConstString> m_imported_modules; ///< All modules, including the current module, imported by this
                                                  ///< compile unit.
     FileSpecList m_support_files; ///< Files associated with this compile unit's line table and declarations.
     std::unique_ptr<LineTable> m_line_table_ap; ///< Line table that will get parsed on demand.
     lldb::VariableListSP m_variables; ///< Global and static variable list that will get parsed on demand.
     bool       m_is_optimized; /// eLazyBoolYes if this compile unit was compiled with optimization.
+    lldb::VariableTreeSP m_variable_tree_sp;
 
 private:
     enum
     {
         flagsParsedAllFunctions     = (1u << 0), ///< Have we already parsed all our functions
         flagsParsedVariables        = (1u << 1), ///< Have we already parsed globals and statics?
         flagsParsedSupportFiles     = (1u << 2), ///< Have we already parsed the support files for this compile unit?
         flagsParsedLineTable        = (1u << 3), ///< Have we parsed the line table already?

include/lldb/Symbol/Function.h

public:
     //------------------------------------------------------------------
     ~Function ();
 
     //------------------------------------------------------------------
     /// @copydoc SymbolContextScope::CalculateSymbolContext(SymbolContext*)
     ///
     /// @see SymbolContextScope
     //------------------------------------------------------------------
+    virtual SymbolContextScope *
+    GetParentSymbolContextScope ();
+
+    virtual lldb::VariableTreeSP
+    GetVariables ();
+
     virtual void
     CalculateSymbolContext(SymbolContext* sc);
 
     virtual lldb::ModuleSP
     CalculateSymbolContextModule ();
     
     virtual CompileUnit *
     CalculateSymbolContextCompileUnit ();
protected:
     lldb::user_id_t m_type_uid;     ///< The user ID of for the prototype Type for this function.
     Type * m_type;                  ///< The function prototype type for this function that include the function info (FunctionInfo), return type and parameters.
     Mangled m_mangled;              ///< The mangled function name if any, if empty, there is no mangled information.
     Block m_block;                  ///< All lexical blocks contained in this function.
     AddressRange m_range;           ///< The function address range that covers the widest range needed to contain all blocks
     DWARFExpression m_frame_base;   ///< The frame base expression for variables that are relative to the frame pointer.
     Flags m_flags;
     uint32_t m_prologue_byte_size;  ///< Compute the prologue size once and cache it
+    lldb::VariableTreeSP m_variable_tree_sp;
 private:
     DISALLOW_COPY_AND_ASSIGN(Function);
 };
 
 } // namespace lldb_private
 
 #endif  // liblldb_Function_h_

include/lldb/Symbol/Symbol.h

public:
     {
         m_contains_linker_annotations = b;
     }
     //------------------------------------------------------------------
     /// @copydoc SymbolContextScope::CalculateSymbolContext(SymbolContext*)
     ///
     /// @see SymbolContextScope
     //------------------------------------------------------------------
+    virtual lldb::VariableTreeSP
+    GetVariables ();
+
+    virtual SymbolContextScope *
+    GetParentSymbolContextScope ();
+
     virtual void
     CalculateSymbolContext (SymbolContext *sc);
 
     virtual lldb::ModuleSP
     CalculateSymbolContextModule ();
     
     virtual Symbol *
     CalculateSymbolContextSymbol ();
uint16_t        m_type_data_resolved:1, // True if the data in m_type_data has already been calculated
                     m_size_is_synthesized:1,// non-zero if this symbol's size was calculated using a delta between this symbol and the next
                     m_size_is_valid:1,
                     m_demangled_is_synthesized:1, // The demangled name was created should not be used for expressions or other lookups
                     m_contains_linker_annotations:1, // The symbol name contains linker annotations, which are optional when doing name lookups
                     m_type:7;
     Mangled         m_mangled;              // uniqued symbol name/mangled name pair
     AddressRange    m_addr_range;           // Contains the value, or the section offset address when the value is an address in a section, and the size (if any)
     uint32_t        m_flags;                // A copy of the flags from the original symbol table, the ObjectFile plug-in can interpret these
+    lldb::VariableTreeSP m_variable_tree_sp;
 };
 
 } // namespace lldb_private
 
 #endif  // liblldb_Symbol_h_

include/lldb/Symbol/SymbolContextScope.h

public:
     }
 
     virtual Symbol *
     CalculateSymbolContextSymbol ()
     {
         return NULL;
     }
 
+    virtual lldb::VariableTreeSP
+    GetVariables ()
+    {
+        return NULL;
+    }
+
+    virtual SymbolContextScope *
+    GetParentSymbolContextScope ()
+    {
+        return NULL;
+    }
+
     //------------------------------------------------------------------
     /// Dump the object's symbol context to the stream \a s.
     ///
     /// The object should dump its symbol context to the stream \a s.
     /// This function is widely used in the DumpDebug and verbose output
     /// for lldb objects.
     ///
     /// @param[in] s

include/lldb/Symbol/VariableTree.h

+//===-- VariableTree.h ------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef liblldb_VariableTree_h_
+#define liblldb_VariableTree_h_
+
+#include "lldb/lldb-private.h"
+#include "lldb/Symbol/SymbolContext.h"
+#include "lldb/Symbol/Variable.h"
+#include "lldb/Symbol/VariableList.h"
+#include <unordered_map>
+
+namespace lldb_private {
+
+class VariableTree : public std::enable_shared_from_this<VariableTree>
+{
+public:
+    VariableTree (lldb::VariableListSP &variables, SymbolContextScope *scope);
+
+    VariableTree (lldb::VariableListSP &variables, SymbolContextScope *scope, lldb::VariableListSP &imported_variables);
+    
+    ~VariableTree ();
+
+    bool
+    AddVariable (const lldb::VariableSP &var);
+
+    size_t
+    AddVariableList (const lldb::VariableListSP &vars);
+
+    size_t
+    AddImportedVariableList (const lldb::VariableListSP &imported_variables);
+
+    void
+    Clear ();
+
+    lldb::VariableSP
+    FindVariable (const ConstString &name);
+
+    lldb::VariableSP
+    FindVariable (const ConstString &name, lldb::ValueType type);
+
+    lldb::VariableTreeSP
+    GetParent ();
+
+    size_t
+    GetSize ();
+
+private:
+    lldb::VariableSP
+    FindRecVariable (const ConstString &name, std::unordered_map<SymbolContextScope *, lldb::VariableListSP> &imported_variables);
+
+    lldb::VariableSP
+    FindRecVariable (const ConstString &name, lldb::ValueType type, std::unordered_map<SymbolContextScope *, lldb::VariableListSP> &imported_variables);
+
+    lldb::VariableTreeSP m_parent;
+    lldb::VariableListSP m_variables;
+    SymbolContextScope *m_scope, *m_parent_scope;
+    lldb::VariableListSP m_imported_variables;
+};
+
+}
+
+#endif // liblldb_VariableTree_h_

include/lldb/lldb-forward.h

 class   ValueObjectChild;
 class   ValueObjectConstResult;
 class   ValueObjectConstResultChild;
 class   ValueObjectConstResultImpl;
 class   ValueObjectList;
 class   ValueObjectPrinter;
 class   Variable;
 class   VariableList;
+class   VariableTree;
 class   Watchpoint;
 class   WatchpointList;
 class   WatchpointOptions;
 struct  LineEntry;
 
 } // namespace lldb_private
 
 //----------------------------------------------------------------------
#endif
     typedef std::weak_ptr<lldb_private::UnixSignals> UnixSignalsWP;
     typedef std::shared_ptr<lldb_private::UnwindAssembly> UnwindAssemblySP;
     typedef std::shared_ptr<lldb_private::UnwindPlan> UnwindPlanSP;
     typedef lldb_private::SharingPtr<lldb_private::ValueObject> ValueObjectSP;
     typedef std::shared_ptr<lldb_private::Value> ValueSP;
     typedef std::shared_ptr<lldb_private::ValueList> ValueListSP;
     typedef std::shared_ptr<lldb_private::Variable> VariableSP;
     typedef std::shared_ptr<lldb_private::VariableList> VariableListSP;
+    typedef std::shared_ptr<lldb_private::VariableTree> VariableTreeSP;
     typedef std::shared_ptr<lldb_private::ValueObjectList> ValueObjectListSP;
     typedef std::shared_ptr<lldb_private::Watchpoint> WatchpointSP;
 
 } // namespace lldb
 
 
 #endif  // #if defined(__cplusplus)
 #endif  // LLDB_lldb_forward_h_

source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h

protected:
 
     size_t
     ParseVariables (const lldb_private::SymbolContext& sc,
                     const DWARFDIE &orig_die,
                     const lldb::addr_t func_low_pc,
                     bool parse_siblings,
                     bool parse_children,
                     lldb_private::VariableList* cc_variable_list = NULL);
     
+    void
+    ParseImportedNamespace (                                                                                             
+        const lldb_private::SymbolContext &sc,                                                                           
+        const DWARFDIE die,                                                                                  
+        const lldb::addr_t func_low_pc);
+
     bool
     ClassOrStructIsVirtual (const DWARFDIE &die);
 
     // Given a die_offset, figure out the symbol context representing that die.
     bool
     ResolveFunction (dw_offset_t offset,
                      bool include_inlines,
                      lldb_private::SymbolContextList& sc_list);

source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

 #include "lldb/Interpreter/OptionValueProperties.h"
 
 #include "lldb/Symbol/Block.h"
 #include "lldb/Symbol/CompileUnit.h"
 #include "lldb/Symbol/LineTable.h"
 #include "lldb/Symbol/ObjectFile.h"
 #include "lldb/Symbol/SymbolVendor.h"
 #include "lldb/Symbol/VariableList.h"
+#include "lldb/Symbol/VariableTree.h"
 
 #include "lldb/Target/ObjCLanguageRuntime.h"
 #include "lldb/Target/CPPLanguageRuntime.h"
 
 #include "DWARFCompileUnit.h"
 #include "DWARFDebugAbbrev.h"
 #include "DWARFDebugAranges.h"
 #include "DWARFDebugInfo.h"
if (sc.comp_unit != NULL)
             
             const dw_addr_t func_lo_pc = function_die.GetAttributeValueAsUnsigned (DW_AT_low_pc, LLDB_INVALID_ADDRESS);
             if (func_lo_pc != LLDB_INVALID_ADDRESS)
             {
                 const size_t num_variables = ParseVariables(sc, function_die.GetFirstChild(), func_lo_pc, true, true);
             
                 // Let all blocks know they have parse all their variables
                 sc.function->GetBlock (false).SetDidParseVariables (true, true);
+
+                DWARFDIE context_parent_die = GetDeclContextDIEContainingDIE(function_die);
+                if (context_parent_die && context_parent_die.Tag() == DW_TAG_namespace)
+                    sc.comp_unit->GetVariableList(true);
+                while (context_parent_die && context_parent_die.Tag() == DW_TAG_namespace)
+                {
+                    VariableListSP imported_variables(new VariableList());
+                    ParseVariables(sc, context_parent_die.GetFirstChild(), func_lo_pc, true, false, imported_variables.get());
+                    sc.function->GetVariables()->AddImportedVariableList(imported_variables);
+
+                    context_parent_die = GetDeclContextDIEContainingDIE(context_parent_die);
+                }
                 return num_variables;
             }
         }
         else if (sc.comp_unit)
         {
             DWARFCompileUnit* dwarf_cu = info->GetCompileUnit(sc.comp_unit->GetID());
 
             if (dwarf_cu == NULL)
if (sc.comp_unit != NULL)
                             if (m_using_apple_tables)
                             {
                                 GetObjectFile()->GetModule()->ReportErrorIfModifyDetected ("the DWARF debug information has been modified (.apple_names accelerator table had bad die 0x%8.8x)\n", die_offset);
                             }
                         }            
 
                     }
                 }
+                if (DWARFDIE cu_die = dwarf_cu->GetDIE(dwarf_cu->GetFirstDIEOffset()))
+                    for (auto d = cu_die.GetFirstChild(); d; d = d.GetSibling())
+                        ParseImportedNamespace(sc, d, LLDB_INVALID_ADDRESS);
             }
             return vars_added;
         }
     }
     return 0;
 }
 
+void
+SymbolFileDWARF::ParseImportedNamespace
+(
+    const SymbolContext &sc,
+    const DWARFDIE die,
+    const lldb::addr_t func_low_pc
+)
+{
+    if (die.Tag() == DW_TAG_imported_declaration || die.Tag() == DW_TAG_imported_module)
+    {
+        dw_offset_t imported_uid = die.GetAttributeValueAsReference(DW_AT_import, DW_INVALID_OFFSET);
+        if (UserIDMatches(imported_uid))
+        {
+            DWARFDebugInfo* debug_info = DebugInfo();
+            if (debug_info)
+            {
+                const DWARFDIE imported_die = debug_info->GetDIE(imported_uid);
+
+                if (imported_die)
+                {
+                    sc.comp_unit->GetVariableList(true);
+                    VariableListSP imported_variables(new VariableList());
+
+                    if (imported_die.Tag() == DW_TAG_variable)
+                    {
+                        VariableSP var = ParseVariableDIE(sc, imported_die, func_low_pc);
+                        if (var)
+                            imported_variables->AddVariable(var);
+                    }
+                    else if (imported_die.Tag() == DW_TAG_namespace)
+                        ParseVariables(sc, imported_die.GetFirstChild(), func_low_pc, true, false, imported_variables.get());
+
+                    SymbolContextScope *scope = nullptr;
+                    if (sc.block != nullptr)
+                        scope = sc.block;
+                    else if (sc.function != nullptr)
+                        scope = sc.function;
+                    else if (sc.comp_unit != nullptr)
+                        scope = sc.comp_unit;
+                    if (scope != nullptr)
+                        scope->GetVariables()->AddImportedVariableList(imported_variables);
+                }
+            }
+        }
+    }
+
+}
+
 VariableSP
 SymbolFileDWARF::ParseVariableDIE
 (
     const SymbolContext& sc,
     const DWARFDIE &die,
     const lldb::addr_t func_low_pc
 )
 {
)
     ModuleSP module = GetObjectFile()->GetModule();
     
     if ((tag == DW_TAG_variable) ||
         (tag == DW_TAG_constant) ||
         (tag == DW_TAG_formal_parameter && sc.function))
     {
         DWARFAttributes attributes;
         const size_t num_attributes = die.GetAttributes(attributes);
+        DWARFDIE spec_die;
         if (num_attributes > 0)
         {
             const char *name = NULL;
             const char *mangled = NULL;
             Declaration decl;
             uint32_t i;
             lldb::user_id_t type_uid = LLDB_INVALID_UID;
             DWARFExpression location(die.GetCU());
if ((tag == DW_TAG_variable) ||
                                     location.SetLocationListSlide (func_low_pc - attributes.CompileUnitAtIndex(i)->GetBaseAddress());
                                 }
                             }
                         }
                         break;
 
                     case DW_AT_artificial:      is_artificial = form_value.Boolean(); break;
                     case DW_AT_accessibility:   break; //accessibility = DW_ACCESS_to_AccessType(form_value.Unsigned()); break;
+                    case DW_AT_specification:
+                    {
+                        dw_offset_t spec_uid = form_value.Reference();
+                        if (UserIDMatches(spec_uid))
+                        {
+                            DWARFDebugInfo* debug_info = DebugInfo();
+                            if (debug_info)
+                                spec_die = debug_info->GetDIE(spec_uid);
+                        }
+                        break;
+                    }
                     case DW_AT_declaration:
                     case DW_AT_description:
                     case DW_AT_endianity:
                     case DW_AT_segment:
                     case DW_AT_start_scope:
                     case DW_AT_visibility:
                     default:
                     case DW_AT_abstract_origin:
                     case DW_AT_sibling:
-                    case DW_AT_specification:
                         break;
                     }
                 }
             }
 
             const DWARFDIE parent_context_die = GetDeclContextDIEContainingDIE(die);
             const dw_tag_t parent_tag = die.GetParent().Tag();
-            bool is_static_member = parent_tag == DW_TAG_compile_unit && (parent_context_die.Tag() == DW_TAG_class_type || parent_context_die.Tag() == DW_TAG_structure_type);
+            bool is_static_member = parent_tag == DW_TAG_compile_unit && (parent_context_die.Tag() == DW_TAG_class_type || parent_context_die.Tag() == DW_TAG_structure_type || (parent_context_die.Tag() == DW_TAG_namespace && parent_context_die.GetAttributeValueAsString(DW_AT_name, nullptr) != nullptr));
 
             ValueType scope = eValueTypeInvalid;
 
             const DWARFDIE sc_parent_die = GetParentSymbolContextDIE(die);
             SymbolContextScope * symbol_context_scope = NULL;
 
             if (!mangled)
             {
if ((tag == DW_TAG_variable) ||
                 return var_sp;
             }
         }
         // Cache var_sp even if NULL (the variable was just a specification or
         // was missing vital information to be able to be displayed in the debugger
         // (missing location due to optimization, etc)) so we don't re-parse
         // this DIE over and over later...
         m_die_to_variable_sp[die.GetDIE()] = var_sp;
+        if (spec_die)
+            m_die_to_variable_sp[spec_die.GetDIE()] = var_sp;
     }
     return var_sp;
 }
 
 
 DWARFDIE
 SymbolFileDWARF::FindBlockContainingSpecification (dw_offset_t func_die_offset, 
                                                    dw_offset_t spec_block_die_offset)
while (die)
                     {
                         variable_list_sp->AddVariableIfUnique (var_sp);
                         if (cc_variable_list)
                             cc_variable_list->AddVariableIfUnique (var_sp);
                         ++vars_added;
                     }
                 }
             }
-        }
+            else if (tag == DW_TAG_imported_module || tag == DW_TAG_imported_declaration)
+                ParseImportedNamespace(sc, die, func_low_pc);
+        } 
 
         bool skip_children = (sc.function == NULL && tag == DW_TAG_subprogram);
 
         if (!skip_children && parse_children && die.HasChildren())
         {
             vars_added += ParseVariables(sc, die.GetFirstChild(), func_low_pc, true, true, cc_variable_list);
         }
 

source/Symbol/Block.cpp

 
 #include "lldb/Core/Log.h"
 #include "lldb/Core/Module.h"
 #include "lldb/Core/Section.h"
 #include "lldb/Symbol/Function.h"
 #include "lldb/Symbol/SymbolFile.h"
 #include "lldb/Symbol/SymbolVendor.h"
 #include "lldb/Symbol/VariableList.h"
+#include "lldb/Symbol/VariableTree.h"
 
 using namespace lldb;
 using namespace lldb_private;
 
 Block::Block(lldb::user_id_t uid) :
     UserID(uid),
     m_parent_scope (nullptr),
     m_children (),
Block::FindBlockByID (user_id_t block_id)
     {
         matching_block = (*pos)->FindBlockByID (block_id);
         if (matching_block)
             break;
     }
     return matching_block;
 }
 
+SymbolContextScope *
+Block::GetParentSymbolContextScope ()
+{
+    SymbolContext sc;
+    CalculateSymbolContext(&sc);
+    if (m_parent_scope != nullptr)
+        return m_parent_scope;
+    else if (sc.function != nullptr)
+        return sc.function;
+    else if (sc.comp_unit != nullptr)
+        return (SymbolContextScope *)sc.comp_unit;
+    else if (sc.module_sp)
+        return sc.module_sp.get();
+    else
+        return nullptr;
+}
+
+VariableTreeSP
+Block::GetVariables ()
+{
+    if (!m_variable_tree_sp)
+    {
+        VariableListSP vars(GetBlockVariableList(true));
+        m_variable_tree_sp.reset(new VariableTree(vars, this)); 
+    }
+    return m_variable_tree_sp;
+}
+
 void
 Block::CalculateSymbolContext (SymbolContext* sc)
 {
     if (m_parent_scope)
         m_parent_scope->CalculateSymbolContext(sc);
     sc->block = this;
 }
 

source/Symbol/CMakeLists.txt

add_lldb_library(lldbSymbol
   Symtab.cpp
   Type.cpp
   TypeList.cpp
   TypeSystem.cpp
   UnwindPlan.cpp
   UnwindTable.cpp
   Variable.cpp
   VariableList.cpp
+  VariableTree.cpp
   VerifyDecl.cpp
   )

source/Symbol/CompileUnit.cpp

 //===-- CompileUnit.cpp -----------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "lldb/Symbol/CompileUnit.h"
 #include "lldb/Core/Module.h"
 #include "lldb/Symbol/LineTable.h"
 #include "lldb/Symbol/SymbolVendor.h"
 #include "lldb/Symbol/VariableList.h"
+#include "lldb/Symbol/VariableTree.h"
 #include "lldb/Target/LanguageRuntime.h"
 
 using namespace lldb;
 using namespace lldb_private;
 
 CompileUnit::CompileUnit (const lldb::ModuleSP &module_sp, void *user_data, const char *pathname, const lldb::user_id_t cu_sym_id, lldb::LanguageType language, bool is_optimized) :
     ModuleChild(module_sp),
     FileSpec (pathname, false),
if (language != eLanguageTypeUnknown)
         m_flags.Set(flagsParsedLanguage);
     assert(module_sp);
 }
 
 CompileUnit::~CompileUnit ()
 {
 }
 
+SymbolContextScope *
+CompileUnit::GetParentSymbolContextScope ()
+{
+    return GetModule().get();
+}
+
+VariableTreeSP
+CompileUnit::GetVariables ()
+{
+    if (!m_variable_tree_sp)
+    {
+        VariableListSP vars(GetVariableList(true));
+        m_variable_tree_sp.reset(new VariableTree(vars, this));
+    }
+    return m_variable_tree_sp;
+}
+
 void
 CompileUnit::CalculateSymbolContext(SymbolContext* sc)
 {
     sc->comp_unit = this;
     GetModule()->CalculateSymbolContext(sc);
 }
 
 ModuleSP

source/Symbol/Function.cpp

 #include "lldb/Core/Module.h"
 #include "lldb/Core/Section.h"
 #include "lldb/Host/Host.h"
 #include "lldb/Symbol/CompilerType.h"
 #include "lldb/Symbol/CompileUnit.h"
 #include "lldb/Symbol/LineTable.h"
 #include "lldb/Symbol/SymbolFile.h"
 #include "lldb/Symbol/SymbolVendor.h"
+#include "lldb/Symbol/SymbolContextScope.h"
+#include "lldb/Symbol/VariableList.h"
+#include "lldb/Symbol/VariableTree.h"
 #include "llvm/Support/Casting.h"
 
 using namespace lldb;
 using namespace lldb_private;
 
 //----------------------------------------------------------------------
 // Basic function information is contained in the FunctionInfo class.
 // It is designed to contain the name, linkage name, and declaration
else if (m_type_uid != LLDB_INVALID_UID)
         s->Printf(", type_uid = 0x%8.8" PRIx64, m_type_uid);
 
     s->EOL();
     // Dump the root object
     if (m_block.BlockInfoHasBeenParsed ())
         m_block.Dump(s, m_range.GetBaseAddress().GetFileAddress(), INT_MAX, show_context);
 }
 
+VariableTreeSP
+Function::GetVariables ()
+{
+    if (!m_variable_tree_sp)
+    {
+        VariableListSP vars(new VariableList());
+        m_variable_tree_sp.reset(new VariableTree(vars, this)); 
+    }
+    return m_variable_tree_sp;
+}
+
+SymbolContextScope *
+Function::GetParentSymbolContextScope ()
+{
+    return m_comp_unit;
+}
 
 void
 Function::CalculateSymbolContext(SymbolContext* sc)
 {
     sc->function = this;
     m_comp_unit->CalculateSymbolContext(sc);
 }
 

source/Symbol/Symbol.cpp

 
 #include "lldb/Core/Module.h"
 #include "lldb/Core/ModuleSpec.h"
 #include "lldb/Core/Section.h"
 #include "lldb/Core/Stream.h"
 #include "lldb/Symbol/ObjectFile.h"
 #include "lldb/Symbol/Symtab.h"
 #include "lldb/Symbol/Function.h"
+#include "lldb/Symbol/VariableTree.h"
 #include "lldb/Target/Process.h"
 #include "lldb/Target/Target.h"
 #include "lldb/Symbol/SymbolVendor.h"
 
 using namespace lldb;
 using namespace lldb_private;
 
 
Symbol::GetTypeAsString() const
     ENUM_TO_CSTRING(ObjCIVar);
     ENUM_TO_CSTRING(ReExported);
     default:
         break;
     }
     return "<unknown SymbolType>";
 }
 
+SymbolContextScope *
+Symbol::GetParentSymbolContextScope ()
+{
+    SymbolContext sc;
+    CalculateSymbolContext(&sc);
+    return sc.module_sp.get();
+}
+
+VariableTreeSP
+Symbol::GetVariables ()
+{
+    if (!m_variable_tree_sp)
+    {
+        VariableListSP vars(new VariableList());
+        m_variable_tree_sp.reset(new VariableTree(vars, this));
+    }
+    return m_variable_tree_sp;
+}
+
 void
 Symbol::CalculateSymbolContext (SymbolContext *sc)
 {
     // Symbols can reconstruct the symbol and the module in the symbol context
     sc->symbol = this;
     if (ValueIsAddress())
         sc->module_sp = GetAddressRef().GetModule();
     else

source/Symbol/VariableTree.cpp

+//===-- VariableTree.h ------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "lldb/Symbol/VariableTree.h"
+#include <sstream>
+#include <unordered_map>
+
+using namespace lldb;
+using namespace lldb_private;
+
+VariableTree::VariableTree(VariableListSP &variables, SymbolContextScope *scope) 
+    : m_variables(variables),
+    m_scope(scope),
+    m_parent_scope(scope != nullptr ? scope->GetParentSymbolContextScope() : nullptr),
+    m_imported_variables(new VariableList())
+{
+    if (!m_variables)
+        m_variables.reset(new VariableList());
+}
+
+VariableTree::VariableTree(VariableListSP &variables, SymbolContextScope *scope, VariableListSP &imported_variables)
+    : m_variables(variables),
+    m_scope(scope),
+    m_parent_scope(scope != nullptr ? scope->GetParentSymbolContextScope() : nullptr),
+    m_imported_variables(imported_variables)
+{
+    if (!m_variables)
+        m_variables.reset(new VariableList());
+    if (!m_imported_variables)
+        m_imported_variables.reset(new VariableList());
+}
+
+VariableTree::~VariableTree()
+{
+}
+
+bool
+VariableTree::AddVariable (const VariableSP &var)
+{
+    if (!m_variables->FindVariable(var->GetName()) && var->GetSymbolContextScope() == m_scope)
+    {
+        m_variables->AddVariable(var);
+        return true;
+    }
+    return false;
+}
+
+VariableTreeSP
+VariableTree::GetParent ()
+{
+    if (!m_parent && m_parent_scope != nullptr)
+        m_parent = m_parent_scope->GetVariables();
+    return m_parent;
+}
+
+size_t
+VariableTree::AddVariableList (const VariableListSP &vars)
+{
+    size_t added = 0;
+    for (size_t i = 0; i < vars->GetSize(); i++)
+        if (AddVariable(vars->GetVariableAtIndex(i)))
+            added++;
+    return added;
+}
+
+void
+VariableTree::Clear ()
+{
+    m_variables->Clear();
+}
+
+size_t
+VariableTree::GetSize ()
+{
+    return m_variables->GetSize();
+}
+
+VariableSP
+VariableTree::FindVariable (const ConstString &name)
+{
+    std::unordered_map<SymbolContextScope *, VariableListSP> imported_variables;
+    return FindRecVariable(name, imported_variables);
+}
+
+size_t
+VariableTree::AddImportedVariableList (const VariableListSP &imported_variables)
+{
+    if (!imported_variables)
+        return 0;
+
+    size_t added = 0;
+    for (size_t i = 0; i < imported_variables->GetSize(); i++)
+        if (m_imported_variables->AddVariableIfUnique(imported_variables->GetVariableAtIndex(i)))
+            added++;
+    return added;
+}
+
+VariableSP
+VariableTree::FindVariable (const ConstString &name, ValueType type)
+{
+    std::unordered_map<SymbolContextScope *, VariableListSP> imported_variables;
+    return FindRecVariable(name, type, imported_variables);
+}
+
+VariableSP
+VariableTree::FindRecVariable (const ConstString &name, std::unordered_map<SymbolContextScope *, VariableListSP> &imported_variables)
+{
+    for (size_t i = 0; i < m_imported_variables->GetSize(); i++)
+    {
+        VariableSP var = m_imported_variables->GetVariableAtIndex(i);
+        SymbolContextScope *scope = var->GetSymbolContextScope();
+
+        if (imported_variables.find(scope) == imported_variables.end())
+            imported_variables[scope] = VariableListSP(new VariableList());
+        imported_variables[scope]->AddVariable(var);
+    }
+
+    VariableSP node_result = m_variables->FindVariable(name, false);
+    VariableSP imported_result = imported_variables.find(m_scope) != imported_variables.end() ? imported_variables[m_scope]->FindVariable(name) : VariableSP();
+
+    VariableSP result;
+    if (imported_result)
+        result = imported_result;
+    else if (node_result)
+        result = node_result;
+
+    if (!result && GetParent())
+        result = GetParent()->FindRecVariable(name, imported_variables);
+
+    return result;
+}
+
+VariableSP
+VariableTree::FindRecVariable (const ConstString &name, ValueType type, std::unordered_map<SymbolContextScope *, VariableListSP> &imported_variables)
+{
+    for (size_t i = 0; i < m_imported_variables->GetSize(); i++)
+    {
+        VariableSP var = m_imported_variables->GetVariableAtIndex(i);
+        SymbolContextScope *scope = var->GetSymbolContextScope();
+
+        if (imported_variables.find(scope) == imported_variables.end())
+            imported_variables[scope] = VariableListSP(new VariableList());
+        imported_variables[scope]->AddVariable(var);
+    }
+    VariableSP node_result = m_variables->FindVariable(name, type, false);
+    VariableSP imported_result = imported_variables.find(m_scope) != imported_variables.end() ? imported_variables[m_scope]->FindVariable(name, type) : VariableSP();
+
+    VariableSP result;
+    if (imported_result)
+        result = imported_result;
+    else if (node_result)
+        result = node_result;
+
+    if (!result && GetParent())
+        result = GetParent()->FindRecVariable(name, imported_variables);
+    
+    return result;
+}
+

source/Target/StackFrame.cpp

 #include "lldb/Core/Value.h"
 #include "lldb/Core/ValueObjectVariable.h"
 #include "lldb/Core/ValueObjectConstResult.h"
 #include "lldb/Symbol/CompileUnit.h"
 #include "lldb/Symbol/Function.h"
 #include "lldb/Symbol/Symbol.h"
 #include "lldb/Symbol/SymbolContextScope.h"
 #include "lldb/Symbol/VariableList.h"
+#include "lldb/Symbol/VariableTree.h"
 #include "lldb/Target/ExecutionContext.h"
 #include "lldb/Target/Process.h"
 #include "lldb/Target/RegisterContext.h"
 #include "lldb/Target/Target.h"
 #include "lldb/Target/Thread.h"
 
 using namespace lldb;
 using namespace lldb_private;
if (m_sc.comp_unit)
         VariableListSP global_variable_list_sp (m_sc.comp_unit->GetVariableList(true));
         if (global_variable_list_sp)
             var_list_sp->AddVariables (global_variable_list_sp.get());
     }
     
     return var_list_sp;
 }
 
-
 ValueObjectSP
 StackFrame::GetValueForVariableExpressionPath (const char *var_expr_cstr,
                                                DynamicValueType use_dynamic,
                                                uint32_t options, 
                                                VariableSP &var_sp,
                                                Error &error)
 {
     // We can't fetch variable information for a history stack frame.
     if (m_is_history_frame)
         return ValueObjectSP();
 
     if (var_expr_cstr && var_expr_cstr[0])
     {
         const bool check_ptr_vs_member = (options & eExpressionPathOptionCheckPtrVsMember) != 0;
         const bool no_fragile_ivar = (options & eExpressionPathOptionsNoFragileObjcIvar) != 0;
         const bool no_synth_child = (options & eExpressionPathOptionsNoSyntheticChildren) != 0;
         //const bool no_synth_array = (options & eExpressionPathOptionsNoSyntheticArrayRange) != 0;
         error.Clear();
         bool deref = false;
         bool address_of = false;
         ValueObjectSP valobj_sp;
-        const bool get_file_globals = true;
         // When looking up a variable for an expression, we need only consider the
         // variables that are in scope.
-        VariableListSP var_list_sp (GetInScopeVariableList (get_file_globals));
-        VariableList *variable_list = var_list_sp.get();
         
-        if (variable_list)
+        VariableTreeSP vars;
+        if (m_sc.block)
+            vars = m_sc.block->GetVariables();
+        else if (m_sc.function)
+            vars = m_sc.function->GetVariables();
+        else if (m_sc.comp_unit)
+            vars = m_sc.comp_unit->GetVariables();
+        
+        if (vars)
         {
             // If first character is a '*', then show pointer contents
             const char *var_expr = var_expr_cstr;
             if (var_expr[0] == '*')
             {
                 deref = true;
                 var_expr++; // Skip the '*'
             }
             else if (var_expr[0] == '&')
             {
                 address_of = true;
                 var_expr++; // Skip the '&'
             }
 
             std::string var_path (var_expr);
             size_t separator_idx = var_path.find_first_of(".-[=+~|&^%#@!/?,<>{}");
             StreamString var_expr_path_strm;
 
             ConstString name_const_string;
             if (separator_idx == std::string::npos)
                 name_const_string.SetCString (var_path.c_str());
             else
                 name_const_string.SetCStringWithLength (var_path.c_str(), separator_idx);
 
-            var_sp = variable_list->FindVariable(name_const_string, false);
+            var_sp = vars->FindVariable(name_const_string);
             
             bool synthetically_added_instance_object = false;
 
             if (var_sp)
             {
                 var_path.erase (0, name_const_string.GetLength ());
             }
             else if (options & eExpressionPathOptionsAllowDirectIVarAccess)
             {
                 // Check for direct ivars access which helps us with implicit
                 // access to ivars with the "this->" or "self->"
                 GetSymbolContext(eSymbolContextFunction|eSymbolContextBlock);
                 lldb::LanguageType method_language = eLanguageTypeUnknown;
                 bool is_instance_method = false;
                 ConstString method_object_name;
                 if (m_sc.GetFunctionMethodInfo (method_language, is_instance_method, method_object_name))
                 {
                     if (is_instance_method && method_object_name)
                     {
-                        var_sp = variable_list->FindVariable(method_object_name);
+                        var_sp = vars->FindVariable(method_object_name);
                         if (var_sp)
                         {
                             separator_idx = 0;
                             var_path.insert(0, "->");
                             synthetically_added_instance_object = true;
                         }
                     }
                 }

test/lang/cpp/nsimport/TestCppNsImport.py

def check(self):
 
         # Load the executable
         target = self.dbg.CreateTarget(exe_path)
         self.assertTrue(target.IsValid(), VALID_TARGET)
 
         # Break on main function
         break_0 = target.BreakpointCreateBySourceRegex("// break 0", src_file_spec)
         self.assertTrue(break_0.IsValid() and break_0.GetNumLocations() >= 1, VALID_BREAKPOINT)
+        break_1 = target.BreakpointCreateBySourceRegex("// break 1", src_file_spec)
+        self.assertTrue(break_1.IsValid() and break_1.GetNumLocations() >= 1, VALID_BREAKPOINT)
 
         # Launch the process
         args = None
         env = None
         process = target.LaunchSimple(args, env, self.get_process_working_directory())
         self.assertTrue(process.IsValid(), PROCESS_IS_VALID)
 
         # Get the thread of the process
def check(self):
         self.assertTrue(test_result.IsValid() and test_result.GetValueAsSigned() == 1, "N::n = 1")
 
         test_result = frame.EvaluateExpression("nested")
         self.assertTrue(test_result.IsValid() and test_result.GetValueAsSigned() == 3, "nested = 3")
 
         test_result = frame.EvaluateExpression("anon")
         self.assertTrue(test_result.IsValid() and test_result.GetValueAsSigned() == 2, "anon = 2")
 
+        test_result = frame.EvaluateExpression("global")
+        self.assertTrue(test_result.IsValid() and test_result.GetValueAsSigned() == 4, "global = 4")
+
+        test_result = frame.EvaluateExpression("fun_var")
+        self.assertTrue(test_result.IsValid() and test_result.GetValueAsSigned() == 9, "fun_var = 9")
+
+        # Continue to second breakpoint
+        process.Continue()
+
+        # Get the thread of the process
+        self.assertTrue(process.GetState() == lldb.eStateStopped, PROCESS_STOPPED)
+        thread = lldbutil.get_stopped_thread(process, lldb.eStopReasonBreakpoint)
+
+        # Get current fream of the thread at the breakpoint
+        frame = thread.GetSelectedFrame()
+
+        # Test function inside namespace
+        test_result = frame.EvaluateExpression("fun_var")
+        self.assertTrue(test_result.IsValid() and test_result.GetValueAsSigned() == 5, "fun_var = 5")
+        
 
 if __name__ == '__main__':
     import atexit
     lldb.SBDebugger.Initialize()
     atexit.register(lambda: lldb.SBDebugger.Terminate())
     unittest2.main()

test/lang/cpp/nsimport/main.cpp

 namespace Nested
 {
     namespace
     {
         int nested;
     }
 }
 
-using namespace N;
-using namespace Nested;
+namespace Global
+{
+    int global;
+}
+
+namespace Fun
+{
+    int fun_var;
+    int fun()
+    {
+        fun_var = 5;
+        return 0; // break 1
+    }
+}
+
+using namespace Global;
+
+int fun_var = 9;
 
 int main()
 {
+    using namespace N;
+    using namespace Nested;
     n = 1;
     anon = 2;
     nested = 3;
-    return 0; // break 0
+    global = 4;
+    return Fun::fun(); // break 0
 }