contrib/llvm/tools/lldb/source/Symbol/TypeList.cpp

   1 //===-- TypeList.cpp --------------------------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10
  11 // C Includes
  12 // C++ Includes
  13 #include <vector>
  14
  15 // Other libraries and framework includes
  16 #include "clang/AST/ASTConsumer.h"
  17 #include "clang/AST/ASTContext.h"
  18 #include "clang/AST/Decl.h"
  19 #include "clang/AST/DeclCXX.h"
  20 #include "clang/AST/DeclGroup.h"
  21
  22 #include "clang/Basic/Builtins.h"
  23 #include "clang/Basic/IdentifierTable.h"
  24 #include "clang/Basic/LangOptions.h"
  25 #include "clang/Basic/SourceManager.h"
  26 #include "clang/Basic/TargetInfo.h"
  27
  28 #include "llvm/Support/FormattedStream.h"
  29 #include "llvm/Support/raw_ostream.h"
  30
  31 // Project includes
  32 #include "lldb/Symbol/SymbolFile.h"
  33 #include "lldb/Symbol/SymbolVendor.h"
  34 #include "lldb/Symbol/Type.h"
  35 #include "lldb/Symbol/TypeList.h"
  36
  37 using namespace lldb;
  38 using namespace lldb_private;
  39 using namespace clang;
  40
  41 TypeList::TypeList() :
  42     m_types ()
  43 {
  44 }
  45
  46 //----------------------------------------------------------------------
  47 // Destructor
  48 //----------------------------------------------------------------------
  49 TypeList::~TypeList()
  50 {
  51 }
  52
  53 void
  54 TypeList::Insert (const TypeSP& type_sp)
  55 {
  56     // Just push each type on the back for now. We will worry about uniquing later
  57     if (type_sp)
  58         m_types.insert(std::make_pair(type_sp->GetID(), type_sp));
  59 }
  60
  61
  62 bool
  63 TypeList::InsertUnique (const TypeSP& type_sp)
  64 {
  65     if (type_sp)
  66     {
  67         user_id_t type_uid = type_sp->GetID();
  68         iterator pos, end = m_types.end();
  69
  70         for (pos = m_types.find(type_uid); pos != end && pos->second->GetID() == type_uid; ++pos)
  71         {
  72             if (pos->second.get() == type_sp.get())
  73                 return false;
  74         }
  75     }
  76     Insert (type_sp);
  77     return true;
  78 }
  79
  80 //----------------------------------------------------------------------
  81 // Find a base type by its unique ID.
  82 //----------------------------------------------------------------------
  83 //TypeSP
  84 //TypeList::FindType(lldb::user_id_t uid)
  85 //{
  86 //    iterator pos = m_types.find(uid);
  87 //    if (pos != m_types.end())
  88 //        return pos->second;
  89 //    return TypeSP();
  90 //}
  91
  92 //----------------------------------------------------------------------
  93 // Find a type by name.
  94 //----------------------------------------------------------------------
  95 //TypeList
  96 //TypeList::FindTypes (const ConstString &name)
  97 //{
  98 //    // Do we ever need to make a lookup by name map? Here we are doing
  99 //    // a linear search which isn't going to be fast.
 100 //    TypeList types(m_ast.getTargetInfo()->getTriple().getTriple().c_str());
 101 //    iterator pos, end;
 102 //    for (pos = m_types.begin(), end = m_types.end(); pos != end; ++pos)
 103 //        if (pos->second->GetName() == name)
 104 //            types.Insert (pos->second);
 105 //    return types;
 106 //}
 107
 108 void
 109 TypeList::Clear()
 110 {
 111     m_types.clear();
 112 }
 113
 114 uint32_t
 115 TypeList::GetSize() const
 116 {
 117     return m_types.size();
 118 }
 119
 120 // GetTypeAtIndex isn't used a lot for large type lists, currently only for
 121 // type lists that are returned for "image dump -t TYPENAME" commands and other
 122 // simple symbol queries that grab the first result...
 123
 124 TypeSP
 125 TypeList::GetTypeAtIndex(uint32_t idx)
 126 {
 127     iterator pos, end;
 128     uint32_t i = idx;
 129     for (pos = m_types.begin(), end = m_types.end(); pos != end; ++pos)
 130     {
 131         if (i == 0)
 132             return pos->second;
 133         --i;
 134     }
 135     return TypeSP();
 136 }
 137
 138 void
 139 TypeList::ForEach (std::function <bool(const lldb::TypeSP &type_sp)> const &callback) const
 140 {
 141     for (auto pos = m_types.begin(), end = m_types.end(); pos != end; ++pos)
 142     {
 143         if (!callback(pos->second))
 144             break;
 145     }
 146 }
 147
 148 void
 149 TypeList::ForEach (std::function <bool(lldb::TypeSP &type_sp)> const &callback)
 150 {
 151     for (auto pos = m_types.begin(), end = m_types.end(); pos != end; ++pos)
 152     {
 153         if (!callback(pos->second))
 154             break;
 155     }
 156 }
 157
 158
 159 bool
 160 TypeList::RemoveTypeWithUID (user_id_t uid)
 161 {
 162     iterator pos = m_types.find(uid);
 163
 164     if (pos != m_types.end())
 165     {
 166         m_types.erase(pos);
 167         return true;
 168     }
 169     return false;
 170 }
 171
 172
 173 void
 174 TypeList::Dump(Stream *s, bool show_context)
 175 {
 176     for (iterator pos = m_types.begin(), end = m_types.end(); pos != end; ++pos)
 177     {
 178         pos->second->Dump(s, show_context);
 179     }
 180 }
 181
 182 // depending on implementation details, type lookup might fail because of
 183 // embedded spurious namespace:: prefixes. this call strips them, paying
 184 // attention to the fact that a type might have namespace'd type names as
 185 // arguments to templates, and those must not be stripped off
 186 static bool
 187 GetTypeScopeAndBasename(const char* name_cstr, std::string &scope, std::string &basename, bool *exact_ptr)
 188 {
 189     // Protect against null c string.
 190
 191     if (name_cstr && name_cstr[0])
 192     {
 193         const char *basename_cstr = name_cstr;
 194         const char* namespace_separator = ::strstr (basename_cstr, "::");
 195         if (namespace_separator)
 196         {
 197             const char* template_arg_char = ::strchr (basename_cstr, '<');
 198             while (namespace_separator != NULL)
 199             {
 200                 if (template_arg_char && namespace_separator > template_arg_char) // but namespace'd template arguments are still good to go
 201                     break;
 202                 basename_cstr = namespace_separator + 2;
 203                 namespace_separator = strstr(basename_cstr, "::");
 204             }
 205             if (basename_cstr > name_cstr)
 206             {
 207                 scope.assign (name_cstr, basename_cstr - name_cstr);
 208                 if (scope.size() >= 2 && scope[0] == ':' && scope[1] == ':')
 209                 {
 210                     // The typename passed in started with "::" so make sure we only do exact matches
 211                     if (exact_ptr)
 212                         *exact_ptr = true;
 213                     // Strip the leading "::" as this won't ever show in qualified typenames we get
 214                     // from clang.
 215                     scope.erase(0,2);
 216                 }
 217                 basename.assign (basename_cstr);
 218                 return true;
 219             }
 220         }
 221     }
 222     return false;
 223 }
 224
 225 void
 226 TypeList::RemoveMismatchedTypes (const char *qualified_typename,
 227                                  bool exact_match)
 228 {
 229     std::string type_scope;
 230     std::string type_basename;
 231     TypeClass type_class = eTypeClassAny;
 232     if (!Type::GetTypeScopeAndBasename (qualified_typename, type_scope, type_basename, type_class))
 233     {
 234         type_basename = qualified_typename;
 235         type_scope.clear();
 236     }
 237     return RemoveMismatchedTypes (type_scope, type_basename, type_class, exact_match);
 238 }
 239
 240 void
 241 TypeList::RemoveMismatchedTypes (const std::string &type_scope,
 242                                  const std::string &type_basename,
 243                                  TypeClass type_class,
 244                                  bool exact_match)
 245 {
 246     // Our "collection" type currently is a std::map which doesn't
 247     // have any good way to iterate and remove items from the map
 248     // so we currently just make a new list and add all of the matching
 249     // types to it, and then swap it into m_types at the end
 250     collection matching_types;
 251
 252     iterator pos, end = m_types.end();
 253
 254     for (pos = m_types.begin(); pos != end; ++pos)
 255     {
 256         Type* the_type = pos->second.get();
 257         bool keep_match = false;
 258         TypeClass match_type_class = eTypeClassAny;
 259
 260         if (type_class != eTypeClassAny)
 261         {
 262             match_type_class = the_type->GetClangForwardType().GetTypeClass ();
 263             if ((match_type_class & type_class) == 0)
 264                 continue;
 265         }
 266
 267         ConstString match_type_name_const_str (the_type->GetQualifiedName());
 268         if (match_type_name_const_str)
 269         {
 270             const char *match_type_name = match_type_name_const_str.GetCString();
 271             std::string match_type_scope;
 272             std::string match_type_basename;
 273             if (Type::GetTypeScopeAndBasename (match_type_name,
 274                                                match_type_scope,
 275                                                match_type_basename,
 276                                                match_type_class))
 277             {
 278                 if (match_type_basename == type_basename)
 279                 {
 280                     const size_t type_scope_size = type_scope.size();
 281                     const size_t match_type_scope_size = match_type_scope.size();
 282                     if (exact_match || (type_scope_size == match_type_scope_size))
 283                     {
 284                         keep_match = match_type_scope == type_scope;
 285                     }
 286                     else
 287                     {
 288                         if (match_type_scope_size > type_scope_size)
 289                         {
 290                             const size_t type_scope_pos = match_type_scope.rfind(type_scope);
 291                             if (type_scope_pos == match_type_scope_size - type_scope_size)
 292                             {
 293                                 if (type_scope_pos >= 2)
 294                                 {
 295                                     // Our match scope ends with the type scope we were lookikng for,
 296                                     // but we need to make sure what comes before the matching
 297                                     // type scope is a namepace boundary in case we are trying to match:
 298                                     // type_basename = "d"
 299                                     // type_scope = "b::c::"
 300                                     // We want to match:
 301                                     //  match_type_scope "a::b::c::"
 302                                     // But not:
 303                                     //  match_type_scope "a::bb::c::"
 304                                     // So below we make sure what comes before "b::c::" in match_type_scope
 305                                     // is "::", or the namespace boundary
 306                                     if (match_type_scope[type_scope_pos - 1] == ':' &&
 307                                         match_type_scope[type_scope_pos - 2] == ':')
 308                                     {
 309                                         keep_match = true;
 310                                     }
 311                                 }
 312                             }
 313                         }
 314                     }
 315                 }
 316             }
 317             else
 318             {
 319                 // The type we are currently looking at doesn't exists
 320                 // in a namespace or class, so it only matches if there
 321                 // is no type scope...
 322                 keep_match = type_scope.empty() && type_basename.compare(match_type_name) == 0;
 323             }
 324         }
 325
 326         if (keep_match)
 327         {
 328             matching_types.insert (*pos);
 329         }
 330     }
 331     m_types.swap(matching_types);
 332 }
 333
 334 void
 335 TypeList::RemoveMismatchedTypes (TypeClass type_class)
 336 {
 337     if (type_class == eTypeClassAny)
 338         return;
 339
 340     // Our "collection" type currently is a std::map which doesn't
 341     // have any good way to iterate and remove items from the map
 342     // so we currently just make a new list and add all of the matching
 343     // types to it, and then swap it into m_types at the end
 344     collection matching_types;
 345
 346     iterator pos, end = m_types.end();
 347
 348     for (pos = m_types.begin(); pos != end; ++pos)
 349     {
 350         Type* the_type = pos->second.get();
 351         TypeClass match_type_class = the_type->GetClangForwardType().GetTypeClass ();
 352         if (match_type_class & type_class)
 353             matching_types.insert (*pos);
 354     }
 355     m_types.swap(matching_types);
 356 }