Make only one function that needs to be implemented when searching for types.

[clayborg]

Summary

This patch started off trying to fix Module::FindFirstType() as it sometimes didn't work. The issue was the SymbolFile plug-ins didn't do any filtering of the matching types they produced, and they only looked up types using the type basename. This means if you have two types with the same basename, your type lookup can fail when only looking up a single type. We would ask the Module::FindFirstType to lookup "Foo::Bar" and it would ask the symbol file to find only 1 type matching the basename "Bar", and then we would filter out any matches that didn't match "Foo::Bar". So if the SymbolFile found "Foo::Bar" first, then it would work, but if it found "Baz::Bar" first, it would return only that type and it would be filtered out.

Discovering this issue lead me to think of the patch Alex Langford did a few months ago that was done for finding functions, where he allowed SymbolFile objects to make sure something fully matched before parsing the debug information into an AST type and other LLDB types. So this patch aimed to allow type lookups to also be much more efficient.

As LLDB has been developed over the years, we added more ways to to type lookups. These functions have lots of arguments. This patch aims to make one API that needs to be implemented that serves all previous lookups:

• Find a single type
• Find all types
• Find types in a namespace

This patch introduces a TypeMatch class that contains all of the settings and state needed for all previous type lookups. It contain a vector of CompilerContext objects that can fully or partially specify the lookup that needs to take place. This is controlled by the TypeMatch.m_exact_match boolean.

If you just want to lookup all types with a matching basename, regardless of the containing context, you can specify just a single CompilerContext entry that has a name and a CompilerContextKind mask of CompilerContextKind::AnyType.

Or you can fully specify the exact context to use when doing lookups like:
CompilerContextKind::Namespace "std"
CompilerContextKind::Class "foo"
CompilerContextKind::Typedef "size_type"

This change expands on the clang modules code that already used a vector<CompilerContext> items, but it modifies it to work with user type lookups. The clang modules type lookup is still an option that can be enabled o n the TypeMatch object.

This mirrors the most recent addition of type lookups that took a vector<CompilerContext> that allowed lookups to happen for the expression parser in certain places.

Prior to this we had the following APIs in Module:

void
Module::FindTypes(ConstString type_name, bool exact_match, size_t max_matches,
                  llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
                  TypeList &types);

void
Module::FindTypes(llvm::ArrayRef<CompilerContext> pattern, LanguageSet languages,
                  llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
                  TypeMap &types);

void Module::FindTypesInNamespace(ConstString type_name,
                                  const CompilerDeclContext &parent_decl_ctx,
                                  size_t max_matches, TypeList &type_list);

The new Module API is much simpler. It gets rid of all three above functions and replaces them with:

void Module::FindTypes(TypeMatch &match);

The TypeMatch class contains all of the needed settings:

• The vector<CompilerContext> that allow efficient lookups in the symbol file classes since they can look at basename matches only realize fully matching types. Before this any basename that matched was fully realized only to be removed later by code outside of the SymbolFile layer which could cause many types to be realized when they didn't need to.
• If the lookup is exact or not. If not exact, then the compiler context must match the bottom most items that match the compiler context, otherwise it must match exactly
• The max number of matches
• If the compiler context match is for clang modules or not. Clang modules matches include a Module compiler context kind that allows types to be matched only from certain modules and these matches are not needed when d oing user type lookups.
• An optional list of languages to use to limit the search to only certain languages
• The set of SymbolFile objects that have already been searched
• The matching type list for any matches that are found

The benefits of this approach are:

• Simpler API, and only one API to implement in SymbolFile classes
• Replaces the FindTypesInNamespace that used a CompilerDeclContext as a way to limit the search, but this only worked if the TypeSystem matched the current symbol file's type system, so you couldn't use it to lookup a type in another module
• Fixes a serious bug in our FindFirstType functions where if we were searching for "foo::bar", and we found a "baz::bar" first, the basename would match and we would only fetch 1 type using the basename, only to drop it from the matching list and returning no results

[clayborg]

Added a test case for the failing cases where there are two types in a namespace or other declaration context and only one would previously be found, and the other would fail.

[clayborg]

Remove unused local variables.

[aprantl]

Thanks for looking into this. I'm not sure I like how TypeMatch is both input and output of the type search. What do you think about making an immutable "TypeQuery" object that describes the search characteristics and have the API return a TypeMap? Apart from making it easier to reason about it would, e.g., allow caching the result of a type lookup. I'm not sure what to du about the "visited" map in that case. Maybe it could be a mutable member of the query object. Ideally the TypeQuery object would have only constructors and getters and no methods that change its state.

[clayborg]

In D137900#3925775, @aprantl wrote:

Thanks for looking into this. I'm not sure I like how TypeMatch is both input and output of the type search. What do you think about making an immutable "TypeQuery" object that describes the search characteristics and have the API return a TypeMap?

The main issue is TypeMap has outlawed copy constructors and assignment operators for some reason. And the reason to contain all of the results in the object itself is because we often call a type search on a specific module first and then fall back to other modules. Having the TypeMap be part of the TypeMatch means the TypeMatch object can make decisions on if it is done or not (found the max number of matches, etc) and we only need to pass one object into each call and avoid copying and merging TypeMap objects which will just add inefficiency. So think of an API where we have:

TypeMap Module::FindTypes(TypeMatch &match);

If we want to search a module list for a type using this API, we will need to be able to pass the existing TypeMap result into each call to the above API.

TypeMap ModuleList::FindTypes(TypeMatch &match) {
  TypeMap result;
  for (auto module: m_modules) {
    TypeMap module_result = module.FindTypes(match);
    result.InsertUnique(module_result); // Copying things from the module_result to result will be a bit inefficient here
    // And now to check if the type match is done we need to pass this TypeMap into the match object
    if (match.Done(result))
      return;
  }
}

Right now the TypeMatch object has all of the state inside of it and it doesn't allow for coding mistakes, like if above someone instead of running "match.Done(result)" accidentally did "match.Done(module_result)" (using the wrong TypeMap to check if the matching is done. This is why I ended up with a single object that doesn't allow for any mistakes when using the APIs.

Let me know if you feel strongly about modifying this.

Apart from making it easier to reason about it would, e.g., allow caching the result of a type lookup. I'm not sure what to du about the "visited" map in that case. Maybe it could be a mutable member of the query object.

Ideally the TypeQuery object would have only constructors and getters and no methods that change its state.

I will try and get rid of the SetMatchContext functions and use only constructors and see how it looks.

[clayborg]

I just got time to run a quick comparison to see how much more efficient this patch is over what we currently have when doing lookups. Since we only resolve types whose context matches now, we parse many orders of magnitude fewer types. I added the following log line into SymbolFileDWARF::ParseType(...):

LLDB_LOG(GetLog(LLDBLog::Symbols), "ParseType for die @ {0:x} {1} (\"{2}\")", die.GetOffset(), die.GetTagAsCString(), die.GetName());

And in this fixed LLDB we see we find resolve 10 types when searching a debug version of LLDB when searching for "llvm::StringRef::iterator":

(lldb) target create "../Debug/bin/lldb"
Current executable set to '/Users/gclayton/Documents/src/lldb/main/Debug/bin/lldb' (arm64).
(lldb) log enable lldb symbol
(lldb) type lookup llvm::StringRef::iterator
 ParseType for die @ 0x2265 DW_TAG_typedef ("iterator")
 ParseType for die @ 0x2187 DW_TAG_class_type ("StringRef")
 ParseType for die @ 0x12e DW_TAG_typedef ("iterator")
 ParseType for die @ 0x50 DW_TAG_class_type ("StringRef")
 ParseType for die @ 0x8fb0d DW_TAG_pointer_type ("")
 ParseType for die @ 0x8fb12 DW_TAG_const_type ("")
 ParseType for die @ 0x8fb18 DW_TAG_base_type ("char")
 ParseType for die @ 0x28efa DW_TAG_pointer_type ("")
 ParseType for die @ 0x28eff DW_TAG_const_type ("")
 ParseType for die @ 0x28f05 DW_TAG_base_type ("char")
const char *
const char *
(lldb) quit

So we parse 10 types now, where as before we parsed 2242541 types. I picked the typename "llvm::StringRef::iterator" because the previous code would have done a lookup on "iterator" and then weed out the resolved types before returning to the user. The old LLDB will every single "iterator" in any STL class, or any LLVM classes. And along the way it will resolve the containing classes and all of the types needed for the methods in the class, etc.

So this type lookup is 5 orders of magnitude better than we used to be!

[clayborg]

Make TypeMatch immutable (const) in type searches. Moves the TypeMap out and pass it in by reference to it can be populated in the FindTypes(...) methods that plug-ins override. This keeps the TypeMatch object const so it can't change, and allows results to be efficienctly populated by passing the TypeMap by reference to call sites.

[aprantl]

I still have a few more questions about the interface design here. May main goal is to eliminate as much mutable state and objects being passed by reference as makes sense (and no more :-).
In that vain I'm trying to get rid of all Set...() methods and all places where we pass a mutable reference to something. The accumulating TypeMap may be a good example where that isn't possible, though I wonder how common global exhaustive searches are and if we usually wouldn't stop in most cases after we found the first match?

I appreciate splitting it up into

FindTypes(match, results);

My hope was for match to be completely immutable and passed by value (const reference if need be), so I wonder if the m_searched_symbol_files dictionary shouldn't be part of the result object?
Are all the setters really necessary? Could we just have a bunch of static "create...()" members that instantiate an immutable search specification?

As far as the naming is concerned, what's currently called TypeMatch should maybe be called TypeQuery, since match seems to imply a result?

Why is FindFirstType a member of TypeMatch? I would have expected a function called FindFirstType to take a TypeMatch search specification as an argument?

lldb/include/lldb/Symbol/CompilerDecl.h

93

Why can't this be a return value? The context objects are tiny.

lldb/include/lldb/Symbol/CompilerDeclContext.h

66

same here

lldb/include/lldb/Symbol/Type.h

185

An ArrayRef is meant to be passed by value.

197

if?

241

Is this necessary, or could this be rolled into the constructor?

306

This sentence is missing at least one word. (I also don't quite understand the purpose of this flag)

[clayborg]

In D137900#3938759, @aprantl wrote:

I still have a few more questions about the interface design here. May main goal is to eliminate as much mutable state and objects being passed by reference as makes sense (and no more :-).
In that vain I'm trying to get rid of all Set...() methods and all places where we pass a mutable reference to something. The accumulating TypeMap may be a good example where that isn't possible, though I wonder how common global exhaustive searches are and if we usually wouldn't stop in most cases after we found the first match?

We look up many matches in the expression parser when we have a context to use for the lookup, and then we just have a base type name and we must return all of the results. Also people might want to lookup all of the types for a qualified name. So multiple matches are needed and need to span across modules so that expression lookups can get all of the information they need.

I appreciate splitting it up into

FindTypes(match, results);

My hope was for match to be completely immutable and passed by value (const reference if need be), so I wonder if the m_searched_symbol_files dictionary shouldn't be part of the result object?
Are all the setters really necessary? Could we just have a bunch of static "create...()" members that instantiate an immutable search specification?

As far as the naming is concerned, what's currently called TypeMatch should maybe be called TypeQuery, since match seems to imply a result?

I will rename TypeMatch to TypeQuery and try to see if I can put all mutable parts into a TypeQueryResults,

Why is FindFirstType a member of TypeMatch? I would have expected a function called FindFirstType to take a TypeMatch search specification as an argument?

It just sets all of the settings needed to do the TypeMatch correctly and then does the query. I avoids a bunch of duplicated code all over the place where call locations were creating a TypeMatch object with some query, then setting the max number of matches to 1 and then doing the type query. So it is a convenience function and allows us to modify anything needed when finding the first type and all locations that call this won't ever need to change if we modify the TypeMatch API.

I will try and break things up further and see if I can get rid of set accessors of TypeMatch (soon to be TypeQuery. I want to avoid having too many parameters to a constructor or create function, but it depends on how these queries are used all over. Let me do one more round of cleanup and you can let me know what you think,

[clayborg]

Renamed TypeMatch to TypeQuery and made a new TypeResults class that contains the type query results and map of which symbol files were visited. Got rid of the max number of matches in favor if a boolean that indicates if we want to just find one type.

[clayborg]

Adrian: so it doesn't seem to make sense to try and get rid of all set accessors because it really complicates the way the TypeQuery is used. We have places where a type query is being create and modified as we parse options from a command line command and we need to change the type query. I have gotten rid of most of the set accessors and mainly try to use one of 3 or 4 constructors now. There is only 1 set accessor now. Let me know what you think.

[aprantl]

I think the void FindTypes(const TypeQuery &query, TypeResults &results); API looks like a reasonable compromise. I have a bunch of smaller questions inside, but otherwise I think this can work.

lldb/include/lldb/Core/Module.h

435

Why is this not taking a TypeQuery that wraps a name?

442–444

copy&paste error?

lldb/include/lldb/Core/ModuleList.h

350–356

needs update now

372

same question — why is this not a TypeQuery?

lldb/include/lldb/Symbol/CompilerDecl.h

90

declaration

93

ping?

lldb/include/lldb/Symbol/Type.h

85

Can we get rid of this now?

231

Would you mind sorting this closer to the constructors, so it doesn't appear in the middle of the list of functions that FindTypes implementation would use?

we could even wrap the setup / match functions in a doxygen group
/ \{
/ \}

275

Could this return an ArrayRef<CompilerContext>?

[clayborg]

lldb/include/lldb/Core/Module.h

435

This function doesn't need to exist as long as the "TypeSP TypeQuery::FindFirstType(Module)" function is ok to have around.

442–444

yep!

lldb/include/lldb/Core/ModuleList.h

372

Like in Module.h we can get rid of this as long as the convenience functions in TypeQuery::FindFirstType() are ok.

lldb/include/lldb/Symbol/CompilerDecl.h

90

will fix

93

Will change!

lldb/include/lldb/Symbol/Type.h

85

I believe so! I will change "default" to "delete".

241

I will add it to the constructor.

306

I will reword

[aprantl]

lldb/include/lldb/Core/Module.h

435

It would be good to have some consistency in the interface:

• Either TypeQuery provides Find* methods that take a Module
• or Module provides Find* methods that take a TypeQuery.

Why does this interface exist instead of having a "FindFirstOnly" flag in TypeQuery? Is it because of the overhead of having to dig the type out of a TypeMap?

Otherwise we could just have one method

Module::FindTypes(const TypeQuery &query, TypeResults &results);

that can be called like this

module_sp->FindTypes(TypeQuery::createFindFirstByName("name", e_exact_match), result);
TypeSP type = result.GetTypeAtIndex(0); /// better have a special method for this too

lldb/include/lldb/Symbol/Type.h

296

/// This is the result of a \ref TypeQuery.

299

document what the bool flag does?

[clayborg]

Addressed review comments:

• remove FindFirstType from Module and ModuleList
• fix comment typos
• remove TypeQuery::SetModuleSearch(...) accessor and add bool to constructors

[clayborg]

Update headerdoc on the TypeResults class and methods.

[clayborg]

lldb/include/lldb/Core/Module.h

435

See what you think of the current code and let me know any changes you would like to see.

lldb/include/lldb/Symbol/CompilerDecl.h

93

I looked around LLVM code and there are many accessors that use this technique. Otherwise we need to enforce an exact SmallVector type as the return code and we can't use "llvm::SmallVectorImpl<lldb_private::CompilerContext>". I can change this to return a "llvm::SmallVector<CompilerContext, 4>" if needed? But that locks us into a specific small vector with a specific size of preached items.

[clayborg]

lldb/include/lldb/Symbol/CompilerDecl.h

93

change "preached" to "preset" above...

[aprantl]

I have only two concerns left:

1. IMHO it would be better if find_one (which I think of as a search *input*) would live in TypeQuery instead of TypeResult. It feels wrong to use TypeResult to pass something *in*.
2. It's inconsistent that Module has a FindTypes(TypeQuery) method and TypeQuery has a Find(First)Type(Module) method.

Could we just move find_one into TypeQuery and get rid of the Find methods in TypeQuery.
Let me know if I'm misunderstanding something.

lldb/include/lldb/Symbol/CompilerDecl.h

93

Thanks for checking — that makes sense.

lldb/source/Symbol/Type.cpp

149

IMHO it would be better if find_one (which I think of as a search *input*) would live in TypeQuery instead of TypeResult. It feels wrong to use TypeResult to pass something *in*.

[clayborg]

Address review comments:

• move "find_one" to the TypeQuery object instead of in the TypeResults
• add "find_one" to all TypqQuery constructors
• add accessors to get/set the "find_one" on a TypeQuery
• remove the TypeResults::FindFirstType(...) variants.

[aprantl]

Thanks for bearing with me. I think this is good now. One last suggestion I have is to turn the bools into an enum, so we can't accidentally mix their order up. Otherwise this LGTM!

lldb/include/lldb/Symbol/Type.h

139

Should this be an enum a la TypeQuery::e_exact_match | e_first_only?

275

We shouldn't need this if it's in the constructor?

[clayborg]

Change boolean parameters to constructors to use a bitmask enumeration for readability of code.

[clayborg]

@aprantl can you check this latest patch and accept again if you like what you see? All tests passed.

[aprantl]

lldb/include/lldb/Symbol/Type.h

101

this comment is out of date and should probably just be deleted.

270

Can we just delete this accessor?

[clayborg]

Update: There are some new failures after someone recently added new tests that involve simple template types. I need to fix my new lookup routine to do the right thing in light of these new tests. The main issue is currently if you have a "foo<int>", the accelerator tables and DWARF contain "foo" only. This causes the expression parser to be able to lookup "foo" as it is parsing an expression that has "auto a = foo<int>()" as it will actually return a specialized "foo<int>" as the result since the accelerator table will point to the "foo<int>" type. We need to outlaw these raw lookups from working. Worse yet, if there are multiple instantiations of "foo<T>", it will return all of them and cause LLDB to crash later in some AST copying code.

[clayborg]

Updated to latest sources and fixed issues from a recently added test for simple template types that showed some issues in type lookup. We previously would allow results from a lookup like "Foo" to match a type that was in the accelerator ables as "Foo", but for a type that was really "Foo<int>". This latest addition to the patch fixes these lookups from incorrectly succeeding.

lldb/include/lldb/Core/Module.h

public:
   ///     max_matches. Specify UINT32_MAX to get all possible matches.
   ///
   /// \param[in] variable_list
   ///     A list of variables that gets the matches appended to.
   ///
   void FindGlobalVariables(const RegularExpression &regex, size_t max_matches,
                            VariableList &variable_list);
 
-  /// Find types by name.
-  ///
-  /// Type lookups in modules go through the SymbolFile. The SymbolFile needs to
-  /// be able to lookup types by basename and not the fully qualified typename.
-  /// This allows the type accelerator tables to stay small, even with heavily
-  /// templatized C++. The type search will then narrow down the search
-  /// results. If "exact_match" is true, then the type search will only match
-  /// exact type name matches. If "exact_match" is false, the type will match
-  /// as long as the base typename matches and as long as any immediate
-  /// containing namespaces/class scopes that are specified match. So to
-  /// search for a type "d" in "b::c", the name "b::c::d" can be specified and
-  /// it will match any class/namespace "b" which contains a class/namespace
-  /// "c" which contains type "d". We do this to allow users to not always
-  /// have to specify complete scoping on all expressions, but it also allows
-  /// for exact matching when required.
-  ///
-  /// \param[in] type_name
-  ///     The name of the type we are looking for that is a fully
-  ///     or partially qualified type name.
-  ///
-  /// \param[in] exact_match
-  ///     If \b true, \a type_name is fully qualified and must match
-  ///     exactly. If \b false, \a type_name is a partially qualified
-  ///     name where the leading namespaces or classes can be
-  ///     omitted to make finding types that a user may type
-  ///     easier.
-  ///
-  /// \param[out] types
-  ///     A type list gets populated with any matches.
-  ///
-  void
-  FindTypes(ConstString type_name, bool exact_match, size_t max_matches,
-            llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
-            TypeList &types);
 
-  /// Find types by name.
-  ///
-  /// This behaves like the other FindTypes method but allows to
-  /// specify a DeclContext and a language for the type being searched
-  /// for.
+  /// Find the first type by qualified typename in the current module's
+  /// symbol file.
   ///
-  /// \param searched_symbol_files
-  ///     Prevents one file from being visited multiple times.
-  void
-  FindTypes(llvm::ArrayRef<CompilerContext> pattern, LanguageSet languages,
-            llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
-            TypeMap &types);
-
-  lldb::TypeSP FindFirstType(const SymbolContext &sc, ConstString type_name,
-                             bool exact_match);
-
-  /// Find types by name that are in a namespace. This function is used by the
-  /// expression parser when searches need to happen in an exact namespace
-  /// scope.
+  /// The typename can be a fully or partially qualified typename.
   ///
   /// \param[in] type_name
-  ///     The name of a type within a namespace that should not include
-  ///     any qualifying namespaces (just a type basename).
+  ///   The fully or partially specfied type name for the type to lookup.
   ///
-  /// \param[out] type_list
-  ///     A type list gets populated with any matches.
-  void FindTypesInNamespace(ConstString type_name,
-                            const CompilerDeclContext &parent_decl_ctx,
-                            size_t max_matches, TypeList &type_list);
+  /// \param[in] exact_match
+  ///   If \a exact_match is true, then the typename must a type's fully
+  ///   qualified name exactly.
+  ///   If \a exact_match is false but \a type_name starts with "::", then an
+  ///   \a exact_match will be set to true internally.
+  ///   If \a exact_match if false, but \a type_name doesn't starts with "::",
+  ///   then an a type name can be partially specfied. For example "b::a", will
+  ///   match: "b::a", "c::b::a", "d::b::a", "e::f::b::a".
+  lldb::TypeSP FindFirstType(ConstString type_name, bool exact_match);
+
+  /// Find types using a type matching object that contains all search
+  /// parameters.
+  ///
+  /// \see lldb_private::TypeMatch
+  ///
+  /// \param[in] search_first
+  ///     If non-null, this module will be searched before any other
+  ///     modules.
+  ///
+  /// \param[inout] match
+  ///     A type matching object that contains all of the details of the type
+  ///     search. Any matching types will be populated into the \a match object.
+  void FindTypes(TypeMatch &match);
 
   /// Get const accessor for the module architecture.
   ///
   /// \return
   ///     A const reference to the architecture object.
   const ArchSpec &GetArchitecture() const;
 
   /// Get const accessor for the module file specification.
protected:
 
   friend class ModuleList;
   friend class ObjectFile;
   friend class SymbolFile;
 
 private:
   Module(); // Only used internally by CreateJITModule ()
 
-  void FindTypes_Impl(
-      ConstString name, const CompilerDeclContext &parent_decl_ctx,
-      size_t max_matches,
-      llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
-      TypeMap &types);
-
   Module(const Module &) = delete;
   const Module &operator=(const Module &) = delete;
 };
 
 } // namespace lldb_private
 
 #endif // LLDB_CORE_MODULE_H

lldb/include/lldb/Core/ModuleList.h

public:
   void FindSymbolsWithNameAndType(ConstString name,
                                   lldb::SymbolType symbol_type,
                                   SymbolContextList &sc_list) const;
 
   void FindSymbolsMatchingRegExAndType(const RegularExpression &regex,
                                        lldb::SymbolType symbol_type,
                                        SymbolContextList &sc_list) const;
 
-  /// Find types by name.
+  /// Find types using a type matching object that contains all search
+  /// parameters.
   ///
   /// \param[in] search_first
   ///     If non-null, this module will be searched before any other
   ///     modules.
   ///
-  /// \param[in] name
-  ///     The name of the type we are looking for.
+  /// \param[inout] match
+  ///     A type matching object that contains all of the details of the type
+  ///     search. Any matching types will be populated into the \a match object.
+  void FindTypes(Module *search_first, TypeMatch &match) const;
+
+  /// Find the first type by qualified typename in the each module's symbol
+  /// file in the module list.
   ///
-  /// \param[in] max_matches
-  ///     Allow the number of matches to be limited to \a
-  ///     max_matches. Specify UINT32_MAX to get all possible matches.
+  /// \param[in] search_first
+  ///   If \a search_first is not NULL, then search that module first.
   ///
-  /// \param[out] types
-  ///     A type list gets populated with any matches.
+  /// \param[in] type_name
+  ///   The fully or partially specfied type name for the type to lookup.
   ///
-  void FindTypes(Module *search_first, ConstString name,
-                 bool name_is_fully_qualified, size_t max_matches,
-                 llvm::DenseSet<SymbolFile *> &searched_symbol_files,
-                 TypeList &types) const;
+  /// \param[in] exact_match
+  ///   If \a exact_match is true, then the typename must a type's fully
+  ///   qualified name exactly.
+  ///   If \a exact_match is false but \a type_name starts with "::", then an
+  ///   \a exact_match will be set to true internally.
+  ///   If \a exact_match if false, but \a type_name doesn't starts with "::",
+  ///   then an a type name can be partially specfied. For example "b::a", will
+  ///   match: "b::a", "c::b::a", "d::b::a", "e::f::b::a".
+  lldb::TypeSP FindFirstType(Module *search_first, ConstString type_name,
+                             bool exact_match) const;
 
   bool FindSourceFile(const FileSpec &orig_spec, FileSpec &new_spec) const;
 
   /// Find addresses by file/line
   ///
   /// \param[in] target_sp
   ///     The target the addresses are desired for.
   ///

lldb/include/lldb/Symbol/CompilerDecl.h

public:
   // If this decl represents a function, return the number of arguments for the
   // function
   size_t GetNumFunctionArguments() const;
 
   // If this decl represents a function, return the argument type given a zero
   // based argument index
   CompilerType GetFunctionArgumentType(size_t arg_idx) const;
 
+  /// Populate a valid compiler context from the current decl context.
+  ///
+  /// \param context A valid vector of CompilerContext entries that describes
+  /// this delcaratiion context. The first entry in the vector is the parent of
+  /// the subsequent entry, so the top most entry is the global namespace.
+  void GetCompilerContext(
+      llvm::SmallVectorImpl<lldb_private::CompilerContext> &context) const;
+
 private:
   TypeSystem *m_type_system = nullptr;
   void *m_opaque_decl = nullptr;
 };
 
 bool operator==(const CompilerDecl &lhs, const CompilerDecl &rhs);
 bool operator!=(const CompilerDecl &lhs, const CompilerDecl &rhs);
 
 } // namespace lldb_private
 
 #endif // LLDB_SYMBOL_COMPILERDECL_H

lldb/include/lldb/Symbol/CompilerDeclContext.h

 //===-- CompilerDeclContext.h -----------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLDB_SYMBOL_COMPILERDECLCONTEXT_H
 #define LLDB_SYMBOL_COMPILERDECLCONTEXT_H
 
 #include <vector>
 
+#include "lldb/Symbol/Type.h"
 #include "lldb/Utility/ConstString.h"
 #include "lldb/lldb-private.h"
 
 namespace lldb_private {
 
 /// Represents a generic declaration context in a program. A declaration context
 /// is data structure that contains declarations (e.g. namespaces).
 ///
if (m_type_system == rhs.m_type_system)
       return m_opaque_decl_ctx < rhs.m_opaque_decl_ctx;
     return m_type_system < rhs.m_type_system;
   }
 
   bool IsValid() const {
     return m_type_system != nullptr && m_opaque_decl_ctx != nullptr;
   }
 
+  /// Populate a valid compiler context from the current decl context.
+  ///
+  /// \param context A valid vector of CompilerContext entries that describes
+  /// this delcaratiion context. The first entry in the vector is the parent of
+  /// the subsequent entry, so the top most entry is the global namespace.
+  void GetCompilerContext(
+      llvm::SmallVectorImpl<lldb_private::CompilerContext> &context) const;
+
   std::vector<CompilerDecl> FindDeclByName(ConstString name,
                                            const bool ignore_using_decls);
 
   /// Checks if this decl context represents a method of a class.
   ///
   /// \param[out] language_ptr
   ///     If non NULL and \b true is returned from this function,
   ///     this will indicate if the language that respresents the method.

lldb/include/lldb/Symbol/SymbolFile.h

public:
   virtual void FindGlobalVariables(const RegularExpression &regex,
                                    uint32_t max_matches,
                                    VariableList &variables);
   virtual void FindFunctions(const Module::LookupInfo &lookup_info,
                              const CompilerDeclContext &parent_decl_ctx,
                              bool include_inlines, SymbolContextList &sc_list);
   virtual void FindFunctions(const RegularExpression &regex,
                              bool include_inlines, SymbolContextList &sc_list);
-  virtual void
-  FindTypes(ConstString name, const CompilerDeclContext &parent_decl_ctx,
-            uint32_t max_matches,
-            llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
-            TypeMap &types);
 
-  /// Find types specified by a CompilerContextPattern.
-  /// \param languages
-  ///     Only return results in these languages.
-  /// \param searched_symbol_files
-  ///     Prevents one file from being visited multiple times.
-  virtual void
-  FindTypes(llvm::ArrayRef<CompilerContext> pattern, LanguageSet languages,
-            llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
-            TypeMap &types);
+  /// Find types using a type matching object that contains all search
+  /// parameters.
+  ///
+  /// \see lldb_private::TypeMatch
+  ///
+  /// \param[in] search_first
+  ///     If non-null, this module will be searched before any other
+  ///     modules.
+  ///
+  /// \param[inout] match
+  ///     A type matching object that contains all of the details of the type
+  ///     search. Any matching types will be populated into the \a match object.
+  virtual void FindTypes(TypeMatch &match) {}
 
   virtual void
   GetMangledNamesForFunction(const std::string &scope_qualified_name,
                              std::vector<ConstString> &mangled_names);
 
   virtual void GetTypes(lldb_private::SymbolContextScope *sc_scope,
                         lldb::TypeClass type_mask,
                         lldb_private::TypeList &type_list) = 0;

lldb/include/lldb/Symbol/SymbolFileOnDemand.h

public:
   void FindFunctions(const lldb_private::RegularExpression &regex,
                      bool include_inlines,
                      lldb_private::SymbolContextList &sc_list) override;
 
   void GetMangledNamesForFunction(
       const std::string &scope_qualified_name,
       std::vector<lldb_private::ConstString> &mangled_names) override;
 
-  void
-  FindTypes(lldb_private::ConstString name,
-            const lldb_private::CompilerDeclContext &parent_decl_ctx,
-            uint32_t max_matches,
-            llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
-            lldb_private::TypeMap &types) override;
-
-  void FindTypes(llvm::ArrayRef<lldb_private::CompilerContext> pattern,
-                 lldb_private::LanguageSet languages,
-                 llvm::DenseSet<SymbolFile *> &searched_symbol_files,
-                 lldb_private::TypeMap &types) override;
+  void FindTypes(lldb_private::TypeMatch &match) override;
 
   void GetTypes(lldb_private::SymbolContextScope *sc_scope,
                 lldb::TypeClass type_mask,
                 lldb_private::TypeList &type_list) override;
 
   llvm::Expected<lldb_private::TypeSystem &>
   GetTypeSystemForLanguage(lldb::LanguageType language) override;
 

lldb/include/lldb/Symbol/Type.h

 //===-- Type.h --------------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLDB_SYMBOL_TYPE_H
 #define LLDB_SYMBOL_TYPE_H
 
 #include "lldb/Core/Declaration.h"
 #include "lldb/Symbol/CompilerDecl.h"
 #include "lldb/Symbol/CompilerType.h"
+#include "lldb/Symbol/TypeList.h"
+#include "lldb/Symbol/TypeMap.h"
+#include "lldb/Symbol/TypeSystem.h"
 #include "lldb/Utility/ConstString.h"
 #include "lldb/Utility/UserID.h"
 #include "lldb/lldb-private.h"
 
 #include "llvm/ADT/APSInt.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/Optional.h"
 
 #include <set>
 
 namespace lldb_private {
 
+/// A SmallBitVector that represents a set of source languages (\p
+/// lldb::LanguageType).  Each lldb::LanguageType is represented by
+/// the bit with the position of its enumerator. The largest
+/// LanguageType is < 64, so this is space-efficient and on 64-bit
+/// architectures a LanguageSet can be completely stack-allocated.
+struct LanguageSet {
+  llvm::SmallBitVector bitvector;
+  LanguageSet();
+
+  /// If the set contains a single language only, return it.
+  llvm::Optional<lldb::LanguageType> GetSingularLanguage();
+  void Insert(lldb::LanguageType language);
+  bool Empty() const;
+  size_t Size() const;
+  bool operator[](unsigned i) const;
+};
+
 /// CompilerContext allows an array of these items to be passed to perform
 /// detailed lookups in SymbolVendor and SymbolFile functions.
 struct CompilerContext {
   CompilerContext(CompilerContextKind t, ConstString n) : kind(t), name(n) {}
 
   bool operator==(const CompilerContext &rhs) const {
     return kind == rhs.kind && name == rhs.name;
   }
   bool operator!=(const CompilerContext &rhs) const { return !(*this == rhs); }
 
   void Dump() const;
 
   CompilerContextKind kind;
   ConstString name;
 };
 
 /// Match \p context_chain against \p pattern, which may contain "Any"
 /// kinds. The \p context_chain should *not* contain any "Any" kinds.
 bool contextMatches(llvm::ArrayRef<CompilerContext> context_chain,
                     llvm::ArrayRef<CompilerContext> pattern);
 
+/// A class that contains all state required for type lookups.
+///
+/// Using a TypeMatch class for matching types simplifies the internal APIs we
+/// need to implement type lookups in LLDB. Type lookups can fully specify the
+/// exact typename by filling out a complete or partial CompilerContext array.
+/// This allows for powerful searches and also allows the SymbolFile classes to
+/// use the m_context array to lookup types by basename, then eliminate
+/// potential matches without having to resolve types into each TypeSystem. This
+/// makes type lookups vastly more efficient and allows the SymbolFile objects
+/// to stop looking up types when the type matching is complete, like if we are
+/// looking for only a single type in our search.
+class TypeMatch {
+public:
+  /// Default constructor.
+  ///
+  /// Users will need to call one of the SetMatchContext() functions prior to
+  /// doing name lookups.
+  TypeMatch() = default;
+
+  /// Construct a type match object using a fully or partially qualified name.
+  ///
+  /// \see void SetMatchContext(llvm::StringRef name, bool exact_match);
+  TypeMatch(llvm::StringRef name, bool exact_match);
+  /// Construct a type match object that matches a type basename that exists
+  /// in the specified declaration context only.
+  ///
+  /// \see void SetMatchContext(const CompilerDeclContext &decl_ctx,
+  ///                           ConstString type_basename);
+  TypeMatch(const CompilerDeclContext &decl_ctx, ConstString type_basename);
+  /// Construct a type match object using a compiler declaration that specifies
+  /// a typename and a declaration context to use when doing exact type lookups.
+  ///
+  /// \see void SetMatchContext(const CompilerDecl &decl);
+  TypeMatch(const CompilerDecl &decl);
+
+  /// Construct a type match object that duplicates all matching criterea,
+  /// but not any searched symbol files or the type map for matches. This allows
+  /// the m_context to be modified prior to performaning another search.
+  TypeMatch(const TypeMatch &rhs);
+
+  /// Set the match context using a fully or partially qualified name.
+  ///
+  /// The specified \a type_name will be chopped up and the m_context will be
+  /// populated by separating the string by looking for "::". We do this because
+  /// symbol files have indexes that contain only the type's basename. This also
+  /// allows symbol files to efficiently not realize types that don't match the
+  /// specified context. Example of \a type_name values that can be specified
+  /// include:
+  ///   "foo": Look for any type whose basename matches "foo".
+  ///     If \a exact_match is true, then the type can't be contained in any
+  ///     declaration context like a namespace, class, or other containing
+  ///     scope.
+  ///     If \a exact match is false, then we will find all matches including
+  ///     ones that are contained in other declaration contexts, including top
+  ///     level types.
+  ///   "foo::bar": Look for any type whose basename matches "bar" but make sure
+  ///     its parent declaration context is any named declaration context
+  ///     (namespace, class, struct, etc) whose name matches "foo".
+  ///     If \a exact_match is true, then the "foo" declaration context must
+  ///     appear at the source file level or inside of a function.
+  ///     If \a exact match is false, then the "foo" declaration context can
+  ///     be contained in any other declaration contexts.
+  ///   "class foo": Only match types that are classes whose basename matches
+  ///     "foo".
+  ///   "struct foo": Only match types that are structures whose basename
+  ///     matches "foo".
+  ///   "class foo::bar": Only match types that are classes whose basename
+  ///     matches "bar" and that are contained in any named declaration context
+  ///     named "foo".
+  ///
+  /// \param[in] type_name
+  ///   A fully or partially qualified type name. This name will be parsed and
+  ///   broken up and the m_context will be populated with the various parts of
+  ///   the name. This typename can be prefixed with "struct ", "class ",
+  ///   "union", "enum " or "typedef " before the actual type name to limit the
+  ///   results of the types that match. The declaration context can be
+  ///   specified with the "::" string. like "a::b::my_type".
+  ///
+  /// \param[in] exact_match
+  ///   If \a exact_match is true, then the typename must match a type's fully
+  ///   qualified name exactly.
+  ///   If \a exact_match is false but \a type_name starts with "::", then an
+  ///   \a exact_match will be set to true internally.
+  ///   If \a exact_match if false, but \a type_name doesn't starts with "::",
+  ///   then an a type name can be partially specfied. For example "b::a", will
+  ///   match: "b::a", "c::b::a", "d::b::a", "e::f::b::a".
+  void SetMatchContext(llvm::StringRef type_name, bool exact_match);
+
+  /// Set the match context using a type basename and by specifying the required
+  /// declaration context.
+  ///
+  /// This allows the m_context to be first populated using a declaration
+  /// context to exactly identify the containing declaration context of a type.
+  /// This can be used when you have a forward declaration to a type and you
+  /// need to search for its complete type.
+  ///
+  /// \param[in] decl_ctx
+  ///   A declaration context object that comes from a TypeSystem plug-in. This
+  ///   object will be asked to full the array of CompilerContext objects
+  ///   by adding the top most declaration context first into the array and then
+  ///   adding any containing declaration contexts.
+  ///
+  /// \param[in] type_basename
+  ///   The basename of the type to lookup in the specified declaration context.
+  void SetMatchContext(const CompilerDeclContext &decl_ctx,
+                       ConstString type_basename);
+
+  /// Set the match context using a type declartion.
+  ///
+  /// This allows the m_context to be first populated using a type declaration.
+  /// The type declaration might have a declaration context and each TypeSystem
+  /// plug-in can populate the declaration context needed to perform an exact
+  /// lookup for a type.
+  /// This can be used when you have a forward declaration to a type and you
+  /// need to search for its complete type.
+  ///
+  /// \param[in] decl
+  ///   A type declaration context object that comes from a TypeSystem plug-in.
+  ///   This object will be asked to full the array of CompilerContext objects
+  ///   by adding the top most declaration context first into the array and then
+  ///   adding any containing declaration contexts, and ending with the exact
+  ///   typename and the kind of type it is (class, struct, union, enum, etc).
+  void SetMatchContext(const CompilerDecl &decl);
+
+  /// Check of a CompilerContext array from matching type from a symbol file
+  /// matches the \a m_context.
+  ///
+  /// \param[in] context
+  ///   A fully qualified CompilerContext array for a potential match that is
+  ///   created by the symbol file prior to trying to actually resolve a type.
+  ///
+  /// \returns
+  ///   True if the context matches, false if it doesn't. If \a m_exact_match
+  ///   is true, then \a context must exactly match \a m_context. If
+  ///   \a m_exact_match is false, then the bottom m_context.size() objects in
+  ///   the \a context must match. This allows SymbolFile objects the fill in a
+  ///   potential type basename match from the index into \a context, and see if
+  ///   it matches prior to having to resolve a lldb_private::Type object for
+  ///   the type from the index. This allows type parsing to be as efficient as
+  ///   possible and only realize the types that match the query.
+  bool ContextMatches(llvm::ArrayRef<lldb_private::CompilerContext> context) const;
+  /// Check if a SymbolFile object has already been searched by this type match
+  /// object.
+  ///
+  /// \param[in] sym_file
+  ///   A SymbolFile pointer that will be used to track which symbol files have
+  ///   already been searched.
+  ///
+  /// \returns
+  ///   True if the symbol file has been search already, false otherwise.
+  bool AlreadySearched(lldb_private::SymbolFile *sym_file);
+
+  /// Get the type basename to use when searching the type indexes in each
+  /// SymbolFile object.
+  ///
+  /// Debug information indexes often contain indexes that track the basename
+  /// of types only, not a fully qualified path. This allows the indexes to be
+  /// smaller and allows for efficient lookups.
+  ///
+  /// \returns
+  ///   The type basename to use when doing lookups as a constant string.
+  ConstString GetTypeBasename() const;
+
+  /// Returns true if any matching languages have been specified in this type
+  /// matching object.
+  bool HasLanguage() const { return m_languages.hasValue(); }
+
+  /// Add a language family to the list of languages that should produce a match.
+  void AddLanguage(lldb::LanguageType language);
+
+  /// Check if the language matches any languages that have been added to this
+  /// match object.
+  ///
+  /// \returns
+  ///   True if no language have been specified, or if some language have been
+  ///   added using AddLanguage(...) and they match. False otherwise.
+  bool LanguageMatches(lldb::LanguageType language) const;
+
+  /// The \a m_context can be used in two ways: normal types searching with
+  /// the context containing a stanadard declaration context for a type, or
+  /// with the context being more complete for exact matches in clang modules.
+  /// Se this to true if you wish to search for a type in clang module.
+  bool GetModuleSearch() const { return m_module_search; }
+  void SetModuleSearch(bool b) { m_module_search = b; }
+  /// Check if the type matching has found all of the matches that it needs.
+  /// This value can be checked after each call to TypeMatch::InsertUnique(...)
+  /// or TypeMatch::AppendTypes() to see if the type matching is completed and
+  /// no more matches need to be found.
+  bool Done() const;
+  /// Insert a type into the type match object.
+  ///
+  /// Only types that match should be added as results. Clients should convert
+  /// their debug information into a CompilerContext array prior to resolving
+  /// the type in the TypeSystem and make sure TypeMatch::ContextMatches(...)
+  /// returns true prior to creating and adding the type. This allows this match
+  /// object to contain only exact matches and makes type searching more
+  /// efficient by allowing fewer types to be parsed and converted into types.
+  void InsertUnique(lldb::TypeSP type_sp);
+  /// Access the type map which contains the result of the type search.
+  const TypeMap &GetTypeMap() const { return m_type_map; }
+  /// A helper function that sets all of the settings necessary to find a single
+  /// matching type in a module.
+  ///
+  /// \param module The module to find the first type in.
+  ///
+  /// \returns A valid TypeSP if a matching type was found, an empty TypeSP if
+  /// not.
+  lldb::TypeSP FindFirstType(lldb_private::Module *module);
+  /// A helper function that sets all of the settings necessary to find a single
+  /// matching type in list of modules.
+  ///
+  /// \param module_list The module list to linearly search for the first
+  ///  matching type.
+  ///
+  /// \param search_first If not NULL, search this module first, and proceed
+  /// to search the module list linearly if the result was not found in this
+  /// module.
+  ///
+  /// \returns A valid TypeSP if a matching type was found, an empty TypeSP if
+  /// not.
+  lldb::TypeSP FindFirstType(const lldb_private::ModuleList &module_list,
+                             lldb_private::Module *search_first = nullptr);
+  /// Sort the contained type map into a list and prefer matches from the
+  /// specified module first.
+  ///
+  /// \param module The module to promote types to the front of the list for.
+  ///
+  /// \param type_list The type list to populate with the results.
+  void SortTypeList(Module *module, TypeList &type_list);
+
+  /// Append all types from the from the type list to the internal type map.
+  ///
+  /// \param type_list The type list to add to the internal type map.
+  void AppendTypes(TypeList &type_list) const;
+
+  /// Access the internal compiler context array.
+  ///
+  /// Clients can use this to populate the context manually.
+  llvm::SmallVector<CompilerContext, 4> &GetContextRef() { return m_context; }
+
+  /// Access the set of searched symbol files.
+  llvm::DenseSet<lldb_private::SymbolFile *> &GetSearchedSymbolFiles() {
+    return m_searched_symbol_files;
+  }
+protected:
+  /// A full or partial compiler context array where the parent declaration
+  /// contexts appear at the top of the array starting at index zero and the
+  /// last entry is contains the type and name of the type we are looking for.
+  llvm::SmallVector<CompilerContext, 4> m_context;
+  /// If this is true, then any matching types must match m_context exactly. If
+  /// this is false, then only the bottom m_context.size() CompilerContext array
+  /// entries must match. This allows partial matching to occur.
+  bool m_exact_match = false;
+  /// Clang module searches have more entries in the compiler context and are
+  /// more complete are are used when lookup up types in a clang module's debug
+  /// information.
+  bool m_module_search = false;
+  /// If this has a value, then it specifies the max number of matches that need
+  /// to be found before the search is complete. If this has no value, then we
+  /// want all matches to be added to this object.
+  llvm::Optional<uint32_t> m_max_matches;
+  /// If this has a value, then the language family must match at least one of
+  /// the specified languages. If this has no value, then the language of the
+  /// type doesn't need to match any types that are searched.
+  llvm::Optional<LanguageSet> m_languages;
+  /// This set is used to track and make sure we only perform lookups in a
+  /// symbol file one time.
+  llvm::DenseSet<lldb_private::SymbolFile *> m_searched_symbol_files;
+  /// Only types that match the m_context, exactly if m_exact_match is true,
+  /// or partially if m_exact_match is false, should be added to this type map.
+  TypeMap m_type_map;
+};
+
 class SymbolFileType : public std::enable_shared_from_this<SymbolFileType>,
                        public UserID {
 public:
   SymbolFileType(SymbolFile &symbol_file, lldb::user_id_t uid)
       : UserID(uid), m_symbol_file(symbol_file) {}
 
   SymbolFileType(SymbolFile &symbol_file, const lldb::TypeSP &type_sp);
 

lldb/include/lldb/Symbol/TypeMap.h

public:
   // Constructors and Destructors
   TypeMap();
 
   virtual ~TypeMap();
 
   void Clear();
 
   void Dump(Stream *s, bool show_context,
-            lldb::DescriptionLevel level = lldb::eDescriptionLevelFull);
+            lldb::DescriptionLevel level = lldb::eDescriptionLevelFull) const;
 
   TypeMap FindTypes(ConstString name);
 
   void Insert(const lldb::TypeSP &type);
 
   bool Empty() const;
 
   bool InsertUnique(const lldb::TypeSP &type);
 
   uint32_t GetSize() const;
 
   lldb::TypeSP GetTypeAtIndex(uint32_t idx);
 
+  lldb::TypeSP FirstType() const;
+
   typedef std::multimap<lldb::user_id_t, lldb::TypeSP> collection;
   typedef AdaptedIterable<collection, lldb::TypeSP, map_adapter> TypeIterable;
 
-  TypeIterable Types() { return TypeIterable(m_types); }
+  TypeIterable Types() const { return TypeIterable(m_types); }
 
   void ForEach(
       std::function<bool(const lldb::TypeSP &type_sp)> const &callback) const;
 
   void ForEach(std::function<bool(lldb::TypeSP &type_sp)> const &callback);
 
   bool Remove(const lldb::TypeSP &type_sp);
 

lldb/include/lldb/Symbol/TypeSystem.h

 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/JSON.h"
 
 #include "lldb/Core/PluginInterface.h"
 #include "lldb/Expression/Expression.h"
 #include "lldb/Symbol/CompilerDecl.h"
 #include "lldb/Symbol/CompilerDeclContext.h"
+#include "lldb/Symbol/Type.h"
 #include "lldb/lldb-private.h"
 
 class DWARFDIE;
 class DWARFASTParser;
 class PDBASTParser;
 
 namespace lldb_private {
 namespace npdb {
   class PdbAstBuilder;
 } // namespace npdb
 
-/// A SmallBitVector that represents a set of source languages (\p
-/// lldb::LanguageType).  Each lldb::LanguageType is represented by
-/// the bit with the position of its enumerator. The largest
-/// LanguageType is < 64, so this is space-efficient and on 64-bit
-/// architectures a LanguageSet can be completely stack-allocated.
-struct LanguageSet {
-  llvm::SmallBitVector bitvector;
-  LanguageSet();
-
-  /// If the set contains a single language only, return it.
-  llvm::Optional<lldb::LanguageType> GetSingularLanguage();
-  void Insert(lldb::LanguageType language);
-  bool Empty() const;
-  size_t Size() const;
-  bool operator[](unsigned i) const;
-};
 
 /// Interface for representing a type system.
 ///
 /// Implemented by language plugins to define the type system for a given
 /// language.
 ///
 /// This interface extensively used opaque pointers to prevent that generic
 /// LLDB code has dependencies on language plugins. The type and semantics of
public:
   virtual CompilerDeclContext DeclGetDeclContext(void *opaque_decl);
 
   virtual CompilerType DeclGetFunctionReturnType(void *opaque_decl);
 
   virtual size_t DeclGetFunctionNumArguments(void *opaque_decl);
 
   virtual CompilerType DeclGetFunctionArgumentType(void *opaque_decl,
                                                    size_t arg_idx);
+  virtual void DeclGetCompilerContext(void *opaque_decl,
+      llvm::SmallVectorImpl<lldb_private::CompilerContext> &context);
 
   virtual CompilerType GetTypeForDecl(void *opaque_decl) = 0;
 
   // CompilerDeclContext functions
 
   virtual std::vector<CompilerDecl>
   DeclContextFindDeclByName(void *opaque_decl_ctx, ConstString name,
                             const bool ignore_imported_decls);
 
   virtual ConstString DeclContextGetName(void *opaque_decl_ctx) = 0;
 
   virtual ConstString
   DeclContextGetScopeQualifiedName(void *opaque_decl_ctx) = 0;
 
   virtual bool DeclContextIsClassMethod(
       void *opaque_decl_ctx, lldb::LanguageType *language_ptr,
       bool *is_instance_method_ptr, ConstString *language_object_name_ptr) = 0;
 
   virtual bool DeclContextIsContainedInLookup(void *opaque_decl_ctx,
                                               void *other_opaque_decl_ctx) = 0;
 
+  virtual void DeclContextGetCompilerContext(void *opaque_decl_ctx,
+      llvm::SmallVectorImpl<lldb_private::CompilerContext> &context);
   // Tests
 #ifndef NDEBUG
   /// Verify the integrity of the type to catch CompilerTypes that mix
   /// and match invalid TypeSystem/Opaque type pairs.
   virtual bool Verify(lldb::opaque_compiler_type_t type) = 0;
 #endif
 
   virtual bool IsArrayType(lldb::opaque_compiler_type_t type,

lldb/include/lldb/lldb-forward.h

 class TypeEnumMemberImpl;
 class TypeEnumMemberListImpl;
 class TypeFilterImpl;
 class TypeFormatImpl;
 class TypeImpl;
 class TypeList;
 class TypeListImpl;
 class TypeMap;
+class TypeMatch;
 class TypeMemberFunctionImpl;
 class TypeMemberImpl;
 class TypeNameSpecifierImpl;
 class TypeSummaryImpl;
 class TypeSummaryOptions;
 class TypeSystem;
 class UUID;
 class UnixSignals;

lldb/include/lldb/lldb-private-enumerations.h

enum class CompilerContextKind : uint16_t {
   Namespace = 1 << 2,
   Class = 1 << 3,
   Struct = 1 << 4,
   Union = 1 << 5,
   Function = 1 << 6,
   Variable = 1 << 7,
   Enum = 1 << 8,
   Typedef = 1 << 9,
+  Builtin = 1 << 10,
 
   Any = 1 << 15,
   /// Match 0..n nested modules.
   AnyModule = Any | Module,
   /// Match any type.
-  AnyType = Any | Class | Struct | Union | Enum | Typedef
+  AnyType = Any | Class | Struct | Union | Enum | Typedef | Builtin,
+  /// Math any declaration context.
+  AnyDeclContext = Any | Namespace | Class | Struct | Union | Enum | Function
 };
 
 // Enumerations that can be used to specify the kind of metric we're looking at
 // when collecting stats.
 enum StatisticKind {
   ExpressionSuccessful = 0,
   ExpressionFailure = 1,
   FrameVarSuccess = 2,

lldb/source/API/SBModule.cpp

 }
 
 lldb::SBType SBModule::FindFirstType(const char *name_cstr) {
   LLDB_INSTRUMENT_VA(this, name_cstr);
 
   SBType sb_type;
   ModuleSP module_sp(GetSP());
   if (name_cstr && module_sp) {
-    SymbolContext sc;
     const bool exact_match = false;
     ConstString name(name_cstr);
 
-    sb_type = SBType(module_sp->FindFirstType(sc, name, exact_match));
+    sb_type = SBType(module_sp->FindFirstType(name, exact_match));
 
     if (!sb_type.IsValid()) {
       auto type_system_or_err =
           module_sp->GetTypeSystemForLanguage(eLanguageTypeC);
       if (auto err = type_system_or_err.takeError()) {
         llvm::consumeError(std::move(err));
         return SBType();
       }

 lldb::SBTypeList SBModule::FindTypes(const char *type) {
   LLDB_INSTRUMENT_VA(this, type);
 
   SBTypeList retval;
 
   ModuleSP module_sp(GetSP());
   if (type && module_sp) {
     TypeList type_list;
-    const bool exact_match = false;
+    TypeMatch match(type, /*exact_match=*/false);
+    module_sp->FindTypes(match);
+    if (match.GetTypeMap().Empty()) {
       ConstString name(type);
-    llvm::DenseSet<SymbolFile *> searched_symbol_files;
-    module_sp->FindTypes(name, exact_match, UINT32_MAX, searched_symbol_files,
-                         type_list);
-
-    if (type_list.Empty()) {
       auto type_system_or_err =
           module_sp->GetTypeSystemForLanguage(eLanguageTypeC);
       if (auto err = type_system_or_err.takeError()) {
         llvm::consumeError(std::move(err));
       } else {
         CompilerType compiler_type =
             type_system_or_err->GetBuiltinTypeByName(name);
         if (compiler_type)
           retval.Append(SBType(compiler_type));
       }
     } else {
-      for (size_t idx = 0; idx < type_list.GetSize(); idx++) {
-        TypeSP type_sp(type_list.GetTypeAtIndex(idx));
-        if (type_sp)
-          retval.Append(SBType(type_sp));
-      }
-    }
-  }
+      for (const TypeSP &type_sp: match.GetTypeMap().Types())
   return retval;
 }
 
 lldb::SBType SBModule::GetTypeByID(lldb::user_id_t uid) {
   LLDB_INSTRUMENT_VA(this, uid);
 
   ModuleSP module_sp(GetSP());
   if (module_sp) {

lldb/source/API/SBTarget.cpp

if (target_sp) {
     ConstString const_triple(triple.c_str());
     return const_triple.GetCString();
   }
   return nullptr;
 }
 
 const char *SBTarget::GetABIName() {
   LLDB_INSTRUMENT_VA(this);
-  
   TargetSP target_sp(GetSP());
   if (target_sp) {
     std::string abi_name(target_sp->GetABIName().str());
     ConstString const_name(abi_name.c_str());
     return const_name.GetCString();
   }
   return nullptr;
 }

 }
 
 lldb::SBType SBTarget::FindFirstType(const char *typename_cstr) {
   LLDB_INSTRUMENT_VA(this, typename_cstr);
 
   TargetSP target_sp(GetSP());
   if (typename_cstr && typename_cstr[0] && target_sp) {
     ConstString const_typename(typename_cstr);
-    SymbolContext sc;
     const bool exact_match = false;
 
     const ModuleList &module_list = target_sp->GetImages();
-    size_t count = module_list.GetSize();
-    for (size_t idx = 0; idx < count; idx++) {
-      ModuleSP module_sp(module_list.GetModuleAtIndex(idx));
-      if (module_sp) {
-        TypeSP type_sp(
-            module_sp->FindFirstType(sc, const_typename, exact_match));
-        if (type_sp)
-          return SBType(type_sp);
-      }
-    }
+    TypeSP type_sp = module_list.FindFirstType(nullptr, const_typename,
+                                               exact_match);
 
     // Didn't find the type in the symbols; Try the loaded language runtimes
     if (auto process_sp = target_sp->GetProcessSP()) {
       for (auto *runtime : process_sp->GetLanguageRuntimes()) {
         if (auto vendor = runtime->GetDeclVendor()) {
           auto types = vendor->FindTypes(const_typename, /*max_matches*/ 1);
           if (!types.empty())
             return SBType(types.front());

 lldb::SBTypeList SBTarget::FindTypes(const char *typename_cstr) {
   LLDB_INSTRUMENT_VA(this, typename_cstr);
 
   SBTypeList sb_type_list;
   TargetSP target_sp(GetSP());
   if (typename_cstr && typename_cstr[0] && target_sp) {
     ModuleList &images = target_sp->GetImages();
     ConstString const_typename(typename_cstr);
-    bool exact_match = false;
-    TypeList type_list;
-    llvm::DenseSet<SymbolFile *> searched_symbol_files;
-    images.FindTypes(nullptr, const_typename, exact_match, UINT32_MAX,
-                     searched_symbol_files, type_list);
+    TypeMatch match(typename_cstr, /*exact_match=*/false);
+    images.FindTypes(nullptr, match);
 
-    for (size_t idx = 0; idx < type_list.GetSize(); idx++) {
-      TypeSP type_sp(type_list.GetTypeAtIndex(idx));
-      if (type_sp)
-        sb_type_list.Append(SBType(type_sp));
-    }
+    for (const TypeSP &type_sp: match.GetTypeMap().Types())
 
     // Try the loaded language runtimes
     if (auto process_sp = target_sp->GetProcessSP()) {
       for (auto *runtime : process_sp->GetLanguageRuntimes()) {
         if (auto *vendor = runtime->GetDeclVendor()) {
           auto types =
               vendor->FindTypes(const_typename, /*max_matches*/ UINT32_MAX);
           for (auto type : types)

lldb/source/Commands/CommandObjectMemory.cpp

bool DoExecute(Args &command, CommandReturnObject &result) override {
     Status error;
 
     const char *view_as_type_cstr =
         m_memory_options.m_view_as_type.GetCurrentValue();
     if (view_as_type_cstr && view_as_type_cstr[0]) {
       // We are viewing memory as a type
 
       const bool exact_match = false;
-      TypeList type_list;
       uint32_t reference_count = 0;
       uint32_t pointer_count = 0;
       size_t idx;
 
 #define ALL_KEYWORDS                                                           \
   KEYWORD("const")                                                             \
   KEYWORD("volatile")                                                          \
   KEYWORD("restrict")                                                          \
#undef ALL_KEYWORDS
 
           default:
             done = true;
             break;
           }
         }
       }
 
-      llvm::DenseSet<lldb_private::SymbolFile *> searched_symbol_files;
       ConstString lookup_type_name(type_str.c_str());
       StackFrame *frame = m_exe_ctx.GetFramePtr();
       ModuleSP search_first;
-      if (frame) {
+      if (frame)
         search_first = frame->GetSymbolContext(eSymbolContextModule).module_sp;
-      }
-      target->GetImages().FindTypes(search_first.get(), lookup_type_name,
-                                    exact_match, 1, searched_symbol_files,
-                                    type_list);
+      TypeSP type_sp = target->GetImages().FindFirstType(search_first.get(),
+                                                         lookup_type_name,
+                                                         exact_match);
 
-      if (type_list.GetSize() == 0 && lookup_type_name.GetCString()) {
+      if (!type_sp && lookup_type_name.GetCString()) {
         LanguageType language_for_type =
             m_memory_options.m_language_for_type.GetCurrentValue();
         std::set<LanguageType> languages_to_check;
         if (language_for_type != eLanguageTypeUnknown) {
           languages_to_check.insert(language_for_type);
         } else {
           languages_to_check = Language::GetSupportedLanguages();
         }
#undef ALL_KEYWORDS
         }
 
         if (user_defined_types.size() == 1) {
           compiler_type = *user_defined_types.begin();
         }
       }
 
       if (!compiler_type.IsValid()) {
-        if (type_list.GetSize() == 0) {
+        if (!type_sp) {
           result.AppendErrorWithFormat("unable to find any types that match "
                                        "the raw type '%s' for full type '%s'\n",
                                        lookup_type_name.GetCString(),
                                        view_as_type_cstr);
           return false;
         } else {
-          TypeSP type_sp(type_list.GetTypeAtIndex(0));
           compiler_type = type_sp->GetFullCompilerType();
         }
       }
 
       while (pointer_count > 0) {
         CompilerType pointer_type = compiler_type.GetPointerType();
         if (pointer_type.IsValid())
           compiler_type = pointer_type;

lldb/source/Commands/CommandObjectTarget.cpp

static size_t LookupFunctionInModule(CommandInterpreter &interpreter,
   }
   return 0;
 }
 
 static size_t LookupTypeInModule(Target *target,
                                  CommandInterpreter &interpreter, Stream &strm,
                                  Module *module, const char *name_cstr,
                                  bool name_is_regex) {
-  TypeList type_list;
   if (module && name_cstr && name_cstr[0]) {
-    const uint32_t max_num_matches = UINT32_MAX;
     bool name_is_fully_qualified = false;
 
-    ConstString name(name_cstr);
-    llvm::DenseSet<lldb_private::SymbolFile *> searched_symbol_files;
-    module->FindTypes(name, name_is_fully_qualified, max_num_matches,
-                      searched_symbol_files, type_list);
+    TypeMatch match(name_cstr, name_is_fully_qualified);
+    module->FindTypes(match);
 
+    TypeList type_list;
+    match.SortTypeList(module, type_list);
     if (type_list.Empty())
       return 0;
 
     const uint64_t num_matches = type_list.GetSize();
 
     strm.Indent();
     strm.Printf("%" PRIu64 " match%s found in ", num_matches,
                 num_matches > 1 ? "es" : "");
for (TypeSP type_sp : type_list.Types()) {
         typedefed_type_sp->GetFullCompilerType();
         typedefed_type_sp->GetDescription(&strm, eDescriptionLevelFull, true,
                                           target);
         typedef_type_sp = typedefed_type_sp;
         typedefed_type_sp = typedef_type_sp->GetTypedefType();
       }
       strm.EOL();
     }
-  }
     return type_list.GetSize();
   }
+  return 0;
+}
 
 static size_t LookupTypeHere(Target *target, CommandInterpreter &interpreter,
                              Stream &strm, Module &module,
                              const char *name_cstr, bool name_is_regex) {
+  TypeMatch match(name_cstr, /*exact_match=*/false);
+  module.FindTypes(match);
   TypeList type_list;
-  const uint32_t max_num_matches = UINT32_MAX;
-  bool name_is_fully_qualified = false;
-
-  ConstString name(name_cstr);
-  llvm::DenseSet<SymbolFile *> searched_symbol_files;
-  module.FindTypes(name, name_is_fully_qualified, max_num_matches,
-                   searched_symbol_files, type_list);
-
+  match.SortTypeList(&module, type_list);
   if (type_list.Empty())
     return 0;
 
   strm.Indent();
   strm.PutCString("Best match found in ");
   DumpFullpath(strm, &module.GetFileSpec(), 0);
   strm.PutCString(":\n");
 

lldb/source/Core/Module.cpp

for (size_t n = 0; n < resolver.GetNumberOfAddresses(); n++) {
     Function *f = addr.CalculateSymbolContextFunction();
     if (f && f == function)
       output_local.push_back(addr);
     else
       output_extern.push_back(addr);
   }
 }
 
-void Module::FindTypes_Impl(
-    ConstString name, const CompilerDeclContext &parent_decl_ctx,
-    size_t max_matches,
-    llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
-    TypeMap &types) {
-  if (SymbolFile *symbols = GetSymbolFile())
-    symbols->FindTypes(name, parent_decl_ctx, max_matches,
-                       searched_symbol_files, types);
-}
-
-void Module::FindTypesInNamespace(ConstString type_name,
-                                  const CompilerDeclContext &parent_decl_ctx,
-                                  size_t max_matches, TypeList &type_list) {
-  TypeMap types_map;
-  llvm::DenseSet<lldb_private::SymbolFile *> searched_symbol_files;
-  FindTypes_Impl(type_name, parent_decl_ctx, max_matches, searched_symbol_files,
-                 types_map);
-  if (types_map.GetSize()) {
-    SymbolContext sc;
-    sc.module_sp = shared_from_this();
-    sc.SortTypeList(types_map, type_list);
-  }
-}
-
-lldb::TypeSP Module::FindFirstType(const SymbolContext &sc, ConstString name,
-                                   bool exact_match) {
-  TypeList type_list;
-  llvm::DenseSet<lldb_private::SymbolFile *> searched_symbol_files;
-  FindTypes(name, exact_match, 1, searched_symbol_files, type_list);
-  if (type_list.GetSize())
-    return type_list.GetTypeAtIndex(0);
-  return TypeSP();
-}
-
-void Module::FindTypes(
-    ConstString name, bool exact_match, size_t max_matches,
-    llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
-    TypeList &types) {
-  const char *type_name_cstr = name.GetCString();
-  llvm::StringRef type_scope;
-  llvm::StringRef type_basename;
-  TypeClass type_class = eTypeClassAny;
-  TypeMap typesmap;
-
-  if (Type::GetTypeScopeAndBasename(type_name_cstr, type_scope, type_basename,
-                                    type_class)) {
-    // Check if "name" starts with "::" which means the qualified type starts
-    // from the root namespace and implies and exact match. The typenames we
-    // get back from clang do not start with "::" so we need to strip this off
-    // in order to get the qualified names to match
-    exact_match = type_scope.consume_front("::");
-
-    ConstString type_basename_const_str(type_basename);
-    FindTypes_Impl(type_basename_const_str, CompilerDeclContext(), max_matches,
-                   searched_symbol_files, typesmap);
-    if (typesmap.GetSize())
-      typesmap.RemoveMismatchedTypes(type_scope, type_basename, type_class,
-                                     exact_match);
-  } else {
-    // The type is not in a namespace/class scope, just search for it by
-    // basename
-    if (type_class != eTypeClassAny && !type_basename.empty()) {
-      // The "type_name_cstr" will have been modified if we have a valid type
-      // class prefix (like "struct", "class", "union", "typedef" etc).
-      FindTypes_Impl(ConstString(type_basename), CompilerDeclContext(),
-                     UINT_MAX, searched_symbol_files, typesmap);
-      typesmap.RemoveMismatchedTypes(type_scope, type_basename, type_class,
-                                     exact_match);
-    } else {
-      FindTypes_Impl(name, CompilerDeclContext(), UINT_MAX,
-                     searched_symbol_files, typesmap);
-      if (exact_match) {
-        typesmap.RemoveMismatchedTypes(type_scope, name.GetStringRef(),
-                                       type_class, exact_match);
-      }
-    }
-  }
-  if (typesmap.GetSize()) {
-    SymbolContext sc;
-    sc.module_sp = shared_from_this();
-    sc.SortTypeList(typesmap, types);
-  }
+lldb::TypeSP Module::FindFirstType(ConstString name, bool exact_match) {
+  TypeMatch match(name.GetStringRef(), exact_match);
+  return match.FindFirstType(this);
 }
 
-void Module::FindTypes(
-    llvm::ArrayRef<CompilerContext> pattern, LanguageSet languages,
-    llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
-    TypeMap &types) {
-  // If a scoped timer is needed, place it in a SymbolFile::FindTypes override.
-  // A timer here is too high volume for some cases, for example when calling
-  // FindTypes on each object file.
+void Module::FindTypes(TypeMatch &match) {
   if (SymbolFile *symbols = GetSymbolFile())
-    symbols->FindTypes(pattern, languages, searched_symbol_files, types);
+    symbols->FindTypes(match);
 }
 
 SymbolFile *Module::GetSymbolFile(bool can_create, Stream *feedback_strm) {
   if (!m_did_load_symfile.load()) {
     std::lock_guard<std::recursive_mutex> guard(m_mutex);
     if (!m_did_load_symfile.load() && can_create) {
       ObjectFile *obj_file = GetObjectFile();
       if (obj_file != nullptr) {

lldb/source/Core/ModuleList.cpp

for (pos = m_modules.begin(); pos != end; ++pos) {
         module_sp = (*pos);
         break;
       }
     }
   }
   return module_sp;
 }
 
-void ModuleList::FindTypes(Module *search_first, ConstString name,
-                           bool name_is_fully_qualified, size_t max_matches,
-                           llvm::DenseSet<SymbolFile *> &searched_symbol_files,
-                           TypeList &types) const {
+void ModuleList::FindTypes(Module *search_first, TypeMatch &match) const {
   std::lock_guard<std::recursive_mutex> guard(m_modules_mutex);
-
-  collection::const_iterator pos, end = m_modules.end();
   if (search_first) {
-    for (pos = m_modules.begin(); pos != end; ++pos) {
-      if (search_first == pos->get()) {
-        search_first->FindTypes(name, name_is_fully_qualified, max_matches,
-                                searched_symbol_files, types);
-
-        if (types.GetSize() >= max_matches)
-          return;
-      }
-    }
-  }
+    search_first->FindTypes(match);
+    if (match.Done())
+      return;
+  }
+  for (const auto &module_sp: m_modules) {
+    if (search_first != module_sp.get()) {
+      module_sp->FindTypes(match);
+      if (match.Done())
 
-  for (pos = m_modules.begin(); pos != end; ++pos) {
-    // Search the module if the module is not equal to the one in the symbol
-    // context "sc". If "sc" contains a empty module shared pointer, then the
-    // comparison will always be true (valid_module_ptr != nullptr).
-    if (search_first != pos->get())
-      (*pos)->FindTypes(name, name_is_fully_qualified, max_matches,
-                        searched_symbol_files, types);
-
-    if (types.GetSize() >= max_matches)
-      return;
-  }
+lldb::TypeSP ModuleList::FindFirstType(Module *search_first,
+                                       ConstString type_name,
+                                       bool exact_match) const {
+  TypeMatch match(type_name.GetStringRef(), exact_match);
+  return match.FindFirstType(*this, search_first);
 }
 
 bool ModuleList::FindSourceFile(const FileSpec &orig_spec,
                                 FileSpec &new_spec) const {
   std::lock_guard<std::recursive_mutex> guard(m_modules_mutex);
   for (const ModuleSP &module_sp : m_modules) {
     if (module_sp->FindSourceFile(orig_spec, new_spec))
       return true;

lldb/source/DataFormatters/TypeFormat.cpp

if (!valobj_key)
     return false;
   auto iter = m_types.find(valobj_key), end = m_types.end();
   CompilerType valobj_enum_type;
   if (iter == end) {
     // probably a redundant check
     if (!target_sp)
       return false;
     const ModuleList &images(target_sp->GetImages());
-    TypeList types;
-    llvm::DenseSet<lldb_private::SymbolFile *> searched_symbol_files;
-    images.FindTypes(nullptr, m_enum_type, false, UINT32_MAX,
-                     searched_symbol_files, types);
-    if (types.Empty())
+    TypeMatch match(m_enum_type.GetStringRef(), /*exact_match=*/false);
+    images.FindTypes(nullptr, match);
+    if (match.GetTypeMap().Empty())
       return false;
-    for (lldb::TypeSP type_sp : types.Types()) {
+    for (lldb::TypeSP type_sp : match.GetTypeMap().Types()) {
       if (!type_sp)
         continue;
       if ((type_sp->GetForwardCompilerType().GetTypeInfo() &
            eTypeIsEnumeration) == eTypeIsEnumeration) {
         valobj_enum_type = type_sp->GetFullCompilerType();
         m_types.emplace(valobj_key, valobj_enum_type);
         break;
       }

lldb/source/Plugins/ExpressionParser/Clang/ClangASTSource.cpp

if (const NamespaceDecl *namespace_context =
 
     LLDB_LOGV(log, "      CTD Inspecting namespace map{0} ({1} entries)",
               namespace_map.get(), namespace_map->size());
 
     for (const ClangASTImporter::NamespaceMapItem &item : *namespace_map) {
       LLDB_LOG(log, "      CTD Searching namespace {0} in module {1}",
                item.second.GetName(), item.first->GetFileSpec().GetFilename());
 
-      TypeList types;
-
       ConstString name(decl->getName());
 
-      item.first->FindTypesInNamespace(name, item.second, UINT32_MAX, types);
-
-      for (uint32_t ti = 0, te = types.GetSize(); ti != te; ++ti) {
-        lldb::TypeSP type = types.GetTypeAtIndex(ti);
-
-        if (!type)
-          continue;
+      // Create a type matcher using the CompilerDeclContext for the namespace
+      // as the context (item.second) and search for the name inside of this
+      // context.
+      TypeMatch match(item.second, name);
+      item.first->FindTypes(match);
 
-        CompilerType clang_type(type->GetFullCompilerType());
+      for (const lldb::TypeSP &type_sp: match.GetTypeMap().Types()) {
+        CompilerType clang_type(type_sp->GetFullCompilerType());
 
         if (!ClangUtil::IsClangType(clang_type))
           continue;
 
         const TagType *tag_type =
             ClangUtil::GetQualType(clang_type)->getAs<TagType>();
 
         if (!tag_type)
           continue;
 
         TagDecl *candidate_tag_decl =
             const_cast<TagDecl *>(tag_type->getDecl());
 
         if (TypeSystemClang::GetCompleteDecl(
                 &candidate_tag_decl->getASTContext(), candidate_tag_decl))
           return candidate_tag_decl;
       }
     }
   } else {
-    TypeList types;
-
-    ConstString name(decl->getName());
-
     const ModuleList &module_list = m_target->GetImages();
+    // Create a type matcher using a CompilerDecl. Each TypeSystem class knows
+    // how to fill out a CompilerContext array using a CompilerDecl.
+    TypeMatch match(CompilerDecl(m_clang_ast_context, (void *)decl));
+    module_list.FindTypes(nullptr, match);
+    for (const lldb::TypeSP &type_sp: match.GetTypeMap().Types()) {
 
-    bool exact_match = false;
-    llvm::DenseSet<SymbolFile *> searched_symbol_files;
-    module_list.FindTypes(nullptr, name, exact_match, UINT32_MAX,
-                          searched_symbol_files, types);
-
-    for (uint32_t ti = 0, te = types.GetSize(); ti != te; ++ti) {
-      lldb::TypeSP type = types.GetTypeAtIndex(ti);
-
-      if (!type)
-        continue;
-
-      CompilerType clang_type(type->GetFullCompilerType());
+      CompilerType clang_type(type_sp->GetFullCompilerType());
 
       if (!ClangUtil::IsClangType(clang_type))
         continue;
 
       const TagType *tag_type =
           ClangUtil::GetQualType(clang_type)->getAs<TagType>();
 
       if (!tag_type)
         continue;
 
       TagDecl *candidate_tag_decl = const_cast<TagDecl *>(tag_type->getDecl());
 
-      // We have found a type by basename and we need to make sure the decl
-      // contexts are the same before we can try to complete this type with
-      // another
-      if (!TypeSystemClang::DeclsAreEquivalent(const_cast<TagDecl *>(decl),
-                                               candidate_tag_decl))
-        continue;
-
       if (TypeSystemClang::GetCompleteDecl(&candidate_tag_decl->getASTContext(),
                                             candidate_tag_decl))
         return candidate_tag_decl;
     }
   }
   return nullptr;
 }
 
 void ClangASTSource::CompleteType(TagDecl *tag_decl) {
   Log *log = GetLog(LLDBLog::Expressions);
void ClangASTSource::FindExternalVisibleDecls(
   if (!m_target)
     return;
 
   FillNamespaceMap(context, module_sp, namespace_decl);
 
   if (context.m_found_type)
     return;
 
-  TypeList types;
-  const bool exact_match = true;
-  llvm::DenseSet<lldb_private::SymbolFile *> searched_symbol_files;
-  if (module_sp && namespace_decl)
-    module_sp->FindTypesInNamespace(name, namespace_decl, 1, types);
-  else {
-    m_target->GetImages().FindTypes(module_sp.get(), name, exact_match, 1,
-                                    searched_symbol_files, types);
+  lldb::TypeSP type_sp;
+  if (module_sp && namespace_decl) {
+    // Match the name in the specified decl context.
+    TypeMatch match(namespace_decl, name);
+    type_sp = match.FindFirstType(module_sp.get());
+  } else {
+    // Match the exact name of the type at the root level.
+    TypeMatch match(name.GetStringRef(), /*exact_match=*/true);
+    type_sp = match.FindFirstType(m_target->GetImages());
   }
 
-  if (size_t num_types = types.GetSize()) {
-    for (size_t ti = 0; ti < num_types; ++ti) {
-      lldb::TypeSP type_sp = types.GetTypeAtIndex(ti);
-
-      if (log) {
-        const char *name_string = type_sp->GetName().GetCString();
+  if (type_sp) {
 
-        LLDB_LOG(log, "  CAS::FEVD Matching type found for \"{0}\": {1}", name,
-                 (name_string ? name_string : "<anonymous>"));
-      }
 
-      CompilerType full_type = type_sp->GetFullCompilerType();
 
-      CompilerType copied_clang_type(GuardedCopyType(full_type));
 
-      if (!copied_clang_type) {
-        LLDB_LOG(log, "  CAS::FEVD - Couldn't export a type");
-
-        continue;
-      }
+    } else {
 
       context.AddTypeDecl(copied_clang_type);
 
       context.m_found_type = true;
-      break;
     }
   }
 
   if (!context.m_found_type) {
     // Try the modules next.
     FindDeclInModules(context, name);
   }
 

lldb/source/Plugins/LanguageRuntime/CPlusPlus/ItaniumABI/ItaniumABILanguageRuntime.cpp

if (!target.GetSectionLoadList().IsEmpty()) {
                       original_ptr, in_value.GetTypeName().GetCString(), name);
             // We are a C++ class, that's good.  Get the class name and look it
             // up:
             const char *class_name = name + strlen(vtable_demangled_prefix);
             // We know the class name is absolute, so tell FindTypes that by
             // prefixing it with the root namespace:
             std::string lookup_name("::");
             lookup_name.append(class_name);
-            
             type_info.SetName(class_name);
             const bool exact_match = true;
             TypeList class_types;
+            ConstString const_lookup_name(lookup_name);
 
             // First look in the module that the vtable symbol came from and
             // look for a single exact match.
-            llvm::DenseSet<SymbolFile *> searched_symbol_files;
-            if (sc.module_sp)
-              sc.module_sp->FindTypes(ConstString(lookup_name), exact_match, 1,
-                                      searched_symbol_files, class_types);
+            if (sc.module_sp) {
+              TypeSP type_sp = sc.module_sp->FindFirstType(const_lookup_name,
+                                                           exact_match);
+              if (type_sp)
+                class_types.Insert(type_sp);
+            }
 
             // If we didn't find a symbol, then move on to the entire module
             // list in the target and get as many unique matches as possible
-            if (class_types.Empty())
-              target.GetImages().FindTypes(nullptr, ConstString(lookup_name),
-                                           exact_match, UINT32_MAX,
-                                           searched_symbol_files, class_types);
+            if (class_types.Empty()) {
+                TypeMatch match(lookup_name, exact_match);
+                target.GetImages().FindTypes(nullptr, match);
+                match.AppendTypes(class_types);
+            }
 
             lldb::TypeSP type_sp;
             if (class_types.Empty()) {
               LLDB_LOGF(log, "0x%16.16" PRIx64 ": is not dynamic\n",
                         original_ptr);
               return TypeAndOrName();
             }
             if (class_types.GetSize() == 1) {

lldb/source/Plugins/LanguageRuntime/ObjC/ObjCLanguageRuntime.cpp

if (matching_symbols) {
 
     sc_list.GetContextAtIndex(0, sc);
 
     ModuleSP module_sp(sc.module_sp);
 
     if (!module_sp)
       return TypeSP();
 
-    const bool exact_match = true;
-    const uint32_t max_matches = UINT32_MAX;
-    TypeList types;
-
-    llvm::DenseSet<SymbolFile *> searched_symbol_files;
-    module_sp->FindTypes(name, exact_match, max_matches, searched_symbol_files,
-                         types);
-
-    for (uint32_t i = 0; i < types.GetSize(); ++i) {
-      TypeSP type_sp(types.GetTypeAtIndex(i));
-
+    TypeMatch match(name.GetStringRef(), /*exact_match=*/true);
+    module_sp->FindTypes(match);
+    for (const TypeSP &type_sp: match.GetTypeMap().Types()) {
       if (TypeSystemClang::IsObjCObjectOrInterfaceType(
               type_sp->GetForwardCompilerType())) {
         if (TypePayloadClang(type_sp->GetPayload()).IsCompleteObjCClass()) {
           m_complete_class_cache[name] = type_sp;
           return type_sp;
         }
       }
     }

lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.h

public:
 
   void FindFunctions(const Module::LookupInfo &lookup_info,
                      const CompilerDeclContext &parent_decl_ctx,
                      bool include_inlines, SymbolContextList &sc_list) override;
 
   void FindFunctions(const RegularExpression &regex, bool include_inlines,
                      SymbolContextList &sc_list) override;
 
-  void FindTypes(ConstString name, const CompilerDeclContext &parent_decl_ctx,
-                 uint32_t max_matches,
-                 llvm::DenseSet<SymbolFile *> &searched_symbol_files,
-                 TypeMap &types) override;
-
-  void FindTypes(llvm::ArrayRef<CompilerContext> pattern, LanguageSet languages,
-                 llvm::DenseSet<SymbolFile *> &searched_symbol_files,
-                 TypeMap &types) override;
-
   llvm::Expected<TypeSystem &>
   GetTypeSystemForLanguage(lldb::LanguageType language) override {
     return llvm::make_error<llvm::StringError>(
         "SymbolFileBreakpad does not support GetTypeSystemForLanguage",
         llvm::inconvertibleErrorCode());
   }
 
   CompilerDeclContext

lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp

 }
 
 void SymbolFileBreakpad::FindFunctions(const RegularExpression &regex,
                                        bool include_inlines,
                                        SymbolContextList &sc_list) {
   // TODO
 }
 
-void SymbolFileBreakpad::FindTypes(
-    ConstString name, const CompilerDeclContext &parent_decl_ctx,
-    uint32_t max_matches, llvm::DenseSet<SymbolFile *> &searched_symbol_files,
-    TypeMap &types) {}
-
-void SymbolFileBreakpad::FindTypes(
-    llvm::ArrayRef<CompilerContext> pattern, LanguageSet languages,
-    llvm::DenseSet<SymbolFile *> &searched_symbol_files, TypeMap &types) {}
-
 void SymbolFileBreakpad::AddSymbols(Symtab &symtab) {
   Log *log = GetLog(LLDBLog::Symbols);
   Module &module = *m_objfile_sp->GetModule();
   addr_t base = GetBaseFileAddress();
   if (base == LLDB_INVALID_ADDRESS) {
     LLDB_LOG(log, "Unable to fetch the base address of object file. Skipping "
                   "symtab population.");
     return;

lldb/source/Plugins/SymbolFile/DWARF/DWARFASTParserClang.cpp

TypeSP DWARFASTParserClang::ParseTypeFromClangModule(const SymbolContext &sc,
                                                      Log *log) {
   ModuleSP clang_module_sp = GetContainingClangModule(die);
   if (!clang_module_sp)
     return TypeSP();
 
   // If this type comes from a Clang module, recursively look in the
   // DWARF section of the .pcm file in the module cache. Clang
   // generates DWO skeleton units as breadcrumbs to find them.
-  llvm::SmallVector<CompilerContext, 4> decl_context;
-  die.GetDeclContext(decl_context);
-  TypeMap pcm_types;
-
+  TypeMatch match;
+  die.GetDeclContext(match.GetContextRef());
   // The type in the Clang module must have the same language as the current CU.
-  LanguageSet languages;
-  languages.Insert(SymbolFileDWARF::GetLanguageFamily(*die.GetCU()));
-  llvm::DenseSet<SymbolFile *> searched_symbol_files;
-  clang_module_sp->GetSymbolFile()->FindTypes(decl_context, languages,
-                                              searched_symbol_files, pcm_types);
-  if (pcm_types.Empty()) {
+  match.AddLanguage(SymbolFileDWARF::GetLanguageFamily(*die.GetCU()));
+  match.SetModuleSearch(true);
+  TypeSP pcm_type_sp = match.FindFirstType(clang_module_sp.get());
+  if (!pcm_type_sp) {
     // Since this type is defined in one of the Clang modules imported
     // by this symbol file, search all of them. Instead of calling
     // sym_file->FindTypes(), which would return this again, go straight
     // to the imported modules.
     auto &sym_file = die.GetCU()->GetSymbolFileDWARF();
 
     // Well-formed clang modules never form cycles; guard against corrupted
     // ones by inserting the current file.
-    searched_symbol_files.insert(&sym_file);
+    match.AlreadySearched(&sym_file);
     sym_file.ForEachExternalModule(
-        *sc.comp_unit, searched_symbol_files, [&](Module &module) {
-          module.GetSymbolFile()->FindTypes(decl_context, languages,
-                                            searched_symbol_files, pcm_types);
-          return pcm_types.GetSize();
+        *sc.comp_unit, match.GetSearchedSymbolFiles(), [&](Module &module) {
+          pcm_type_sp = match.FindFirstType(&module);
+          return !pcm_type_sp;
         });
   }
 
-  if (!pcm_types.GetSize())
+  if (!pcm_type_sp)
     return TypeSP();
 
   // We found a real definition for this type in the Clang module, so lets use
   // it and cache the fact that we found a complete type for this die.
-  TypeSP pcm_type_sp = pcm_types.GetTypeAtIndex(0);
-  if (!pcm_type_sp)
-    return TypeSP();
-
   lldb_private::CompilerType pcm_type = pcm_type_sp->GetForwardCompilerType();
   lldb_private::CompilerType type =
       GetClangASTImporter().CopyType(m_ast, pcm_type);
 
   if (!type)
     return TypeSP();
 
   // Under normal operation pcm_type is a shallow forward declaration

lldb/source/Plugins/SymbolFile/DWARF/DWARFDIE.h

public:
 
   DWARFDIE
   GetParentDeclContextDIE() const;
 
   // DeclContext related functions
   std::vector<DWARFDIE> GetDeclContextDIEs() const;
 
   /// Return this DIE's decl context as it is needed to look up types
-  /// in Clang's -gmodules debug info format.
+  /// in Clang modules. This context will include any modules or functions that
+  /// the type is declared in so an exact module match can be efficiently made.
   void GetDeclContext(
       llvm::SmallVectorImpl<lldb_private::CompilerContext> &context) const;
 
+  /// Get a context to a type so it can be looked up.
+  ///
+  /// This function uses the current DIE to fill in a CompilerContext array
+  /// that is suitable for type lookup for comparison to a TypeMatch's compiler
+  /// context (TypeMatch::GetContextRef()). If this DIE represents a named type,
+  /// it should fill out the compiler context with the type itself as the last
+  /// entry. The declaration context should be above the type and stop at an
+  /// appropriate time, like either the translation unit or at a function
+  /// context. This is designed to allow users to efficiently look for types
+  /// using a full or partial CompilerContext array.
+  void GetTypeLookupContext(
+      llvm::SmallVectorImpl<lldb_private::CompilerContext> &context) const;
+
   // Getting attribute values from the DIE.
   //
   // GetAttributeValueAsXXX() functions should only be used if you are
   // looking for one or two attributes on a DIE. If you are trying to
   // parse all attributes, use GetAttributes (...) instead
   DWARFDIE
   GetAttributeValueAsReferenceDIE(const dw_attr_t attr) const;
 

lldb/source/Plugins/SymbolFile/DWARF/DWARFDIE.cpp

void DWARFDIE::GetDeclContext(
   case DW_TAG_typedef:
     context.push_back({CompilerContextKind::Typedef, ConstString(GetName())});
     break;
   default:
     break;
   }
 }
 
+void DWARFDIE::GetTypeLookupContext(
+    llvm::SmallVectorImpl<lldb_private::CompilerContext> &context) const {
+  // If there is no name, then there is no need to look anything up for this DIE.
+  const char *name = GetName();
+  if (!name || !name[0])
+    return;
+  const dw_tag_t tag = Tag();
+  if (tag == DW_TAG_compile_unit || tag == DW_TAG_partial_unit)
+    return;
+  DWARFDIE parent = GetParent();
+  if (parent)
+    parent.GetTypeLookupContext(context);
+  switch (tag) {
+  case DW_TAG_namespace:
+    context.push_back({CompilerContextKind::Namespace, ConstString(name)});
+    break;
+  case DW_TAG_structure_type:
+    context.push_back({CompilerContextKind::Struct, ConstString(name)});
+    break;
+  case DW_TAG_union_type:
+    context.push_back({CompilerContextKind::Union, ConstString(name)});
+    break;
+  case DW_TAG_class_type:
+    context.push_back({CompilerContextKind::Class, ConstString(name)});
+    break;
+  case DW_TAG_enumeration_type:
+    context.push_back({CompilerContextKind::Enum, ConstString(name)});
+    break;
+  case DW_TAG_variable:
+    context.push_back(
+        {CompilerContextKind::Variable, ConstString(GetPubname())});
+    break;
+  case DW_TAG_typedef:
+    context.push_back({CompilerContextKind::Typedef, ConstString(name)});
+    break;
+  case DW_TAG_base_type:
+    context.push_back({CompilerContextKind::Builtin, ConstString(name)});
+    break;
+  default:
+    break;
+  }
+}
+
+
 DWARFDIE
 DWARFDIE::GetParentDeclContextDIE() const {
   if (IsValid())
     return m_die->GetParentDeclContextDIE(m_cu);
   else
     return DWARFDIE();
 }
 

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h

public:
   void FindFunctions(const lldb_private::RegularExpression &regex,
                      bool include_inlines,
                      lldb_private::SymbolContextList &sc_list) override;
 
   void GetMangledNamesForFunction(
       const std::string &scope_qualified_name,
       std::vector<lldb_private::ConstString> &mangled_names) override;
 
-  void
-  FindTypes(lldb_private::ConstString name,
-            const lldb_private::CompilerDeclContext &parent_decl_ctx,
-            uint32_t max_matches,
-            llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
-            lldb_private::TypeMap &types) override;
-
-  void FindTypes(llvm::ArrayRef<lldb_private::CompilerContext> pattern,
-                 lldb_private::LanguageSet languages,
-                 llvm::DenseSet<SymbolFile *> &searched_symbol_files,
-                 lldb_private::TypeMap &types) override;
+  void FindTypes(lldb_private::TypeMatch &match) override;
 
   void GetTypes(lldb_private::SymbolContextScope *sc_scope,
                 lldb::TypeClass type_mask,
                 lldb_private::TypeList &type_list) override;
 
   llvm::Expected<lldb_private::TypeSystem &>
   GetTypeSystemForLanguage(lldb::LanguageType language) override;
 

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.cpp

void SymbolFileDWARF::GetMangledNamesForFunction(
 
   for (DIERef die_ref :
        m_function_scope_qualified_name_map.lookup(scope_qualified_name)) {
     DWARFDIE die = GetDIE(die_ref);
     mangled_names.push_back(ConstString(die.GetMangledName()));
   }
 }
 
-void SymbolFileDWARF::FindTypes(
-    ConstString name, const CompilerDeclContext &parent_decl_ctx,
-    uint32_t max_matches,
-    llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
-    TypeMap &types) {
-  std::lock_guard<std::recursive_mutex> guard(GetModuleMutex());
-  // Make sure we haven't already searched this SymbolFile before.
-  if (!searched_symbol_files.insert(this).second)
-    return;
-
-  Log *log = GetLog(DWARFLog::Lookups);
-
-  if (log) {
-    if (parent_decl_ctx)
-      GetObjectFile()->GetModule()->LogMessage(
-          log,
-          "SymbolFileDWARF::FindTypes (sc, name=\"%s\", parent_decl_ctx = "
-          "%p (\"%s\"), max_matches=%u, type_list)",
-          name.GetCString(), static_cast<const void *>(&parent_decl_ctx),
-          parent_decl_ctx.GetName().AsCString("<NULL>"), max_matches);
-    else
-      GetObjectFile()->GetModule()->LogMessage(
-          log,
-          "SymbolFileDWARF::FindTypes (sc, name=\"%s\", parent_decl_ctx = "
-          "NULL, max_matches=%u, type_list)",
-          name.GetCString(), max_matches);
+/// Split a name up into a basename and template parameters.
+static bool SplitTemplateParams(llvm::StringRef fullname,
+                                llvm::StringRef &basename,
+                                llvm::StringRef &template_params) {
+  auto it = fullname.find('<');
+  if (it == llvm::StringRef::npos) {
+    basename = fullname;
+    template_params = llvm::StringRef();
+    return false;
   }
-
-  if (!DeclContextMatchesThisSymbolFile(parent_decl_ctx))
-    return;
-
-  m_index->GetTypes(name, [&](DWARFDIE die) {
-    if (!DIEInDeclContext(parent_decl_ctx, die))
-      return true; // The containing decl contexts don't match
-
-    Type *matching_type = ResolveType(die, true, true);
-    if (!matching_type)
-      return true;
-
-    // We found a type pointer, now find the shared pointer form our type
-    // list
-    types.InsertUnique(matching_type->shared_from_this());
-    return types.GetSize() < max_matches;
-  });
-
-  // With -gsimple-template-names, a templated type's DW_AT_name will not
-  // contain the template parameters. Try again stripping '<' and anything
-  // after, filtering out entries with template parameters that don't match.
-  if (types.GetSize() < max_matches) {
-    const llvm::StringRef name_ref = name.GetStringRef();
-    auto it = name_ref.find('<');
-    if (it != llvm::StringRef::npos) {
-      const llvm::StringRef name_no_template_params = name_ref.slice(0, it);
-      const llvm::StringRef template_params = name_ref.slice(it, name_ref.size());
-      m_index->GetTypes(ConstString(name_no_template_params), [&](DWARFDIE die) {
-        if (!DIEInDeclContext(parent_decl_ctx, die))
-          return true; // The containing decl contexts don't match
-
-        const llvm::StringRef base_name = GetTypeForDIE(die)->GetBaseName().AsCString();
-        auto it = base_name.find('<');
-        // If the candidate qualified name doesn't have '<', it doesn't have
-        // template params to compare.
-        if (it == llvm::StringRef::npos)
-          return true;
-
-        // Filter out non-matching instantiations by comparing template params.
-        const llvm::StringRef base_name_template_params =
-            base_name.slice(it, base_name.size());
-
-        if (template_params != base_name_template_params)
-          return true;
-
-        Type *matching_type = ResolveType(die, true, true);
-        if (!matching_type)
-          return true;
-
-        // We found a type pointer, now find the shared pointer form our type
-        // list.
-        types.InsertUnique(matching_type->shared_from_this());
-        return types.GetSize() < max_matches;
-      });
-    }
-  }
-
-  // Next search through the reachable Clang modules. This only applies for
-  // DWARF objects compiled with -gmodules that haven't been processed by
-  // dsymutil.
-  if (types.GetSize() < max_matches) {
-    UpdateExternalModuleListIfNeeded();
+  basename = fullname.slice(0, it);
+  template_params = fullname.slice(it, fullname.size());
 
-    for (const auto &pair : m_external_type_modules)
-      if (ModuleSP external_module_sp = pair.second)
-        if (SymbolFile *sym_file = external_module_sp->GetSymbolFile())
-          sym_file->FindTypes(name, parent_decl_ctx, max_matches,
-                              searched_symbol_files, types);
-  }
-
-  if (log && types.GetSize()) {
-    if (parent_decl_ctx) {
-      GetObjectFile()->GetModule()->LogMessage(
-          log,
-          "SymbolFileDWARF::FindTypes (sc, name=\"%s\", parent_decl_ctx "
-          "= %p (\"%s\"), max_matches=%u, type_list) => %u",
-          name.GetCString(), static_cast<const void *>(&parent_decl_ctx),
-          parent_decl_ctx.GetName().AsCString("<NULL>"), max_matches,
-          types.GetSize());
-    } else {
-      GetObjectFile()->GetModule()->LogMessage(
-          log,
-          "SymbolFileDWARF::FindTypes (sc, name=\"%s\", parent_decl_ctx "
-          "= NULL, max_matches=%u, type_list) => %u",
-          name.GetCString(), max_matches, types.GetSize());
+static bool UpdateCompilerContextForSimpleTemplateNames(TypeMatch &match) {
+  // We need to find any names in the context that have template parameters
+  // and strip them so the context can be matched when -gsimple-template-names
+  // is being used. Returns true if any of the context items were updated.
+  bool any_context_updated = false;
+  for (auto &context: match.GetContextRef()) {
+    llvm::StringRef basename, params;
+    if (SplitTemplateParams(context.name.GetStringRef(), basename, params)) {
+      context.name = ConstString(basename);
+      any_context_updated = true;
     }
   }
+  return any_context_updated;
 }
 
-void SymbolFileDWARF::FindTypes(
-    llvm::ArrayRef<CompilerContext> pattern, LanguageSet languages,
-    llvm::DenseSet<SymbolFile *> &searched_symbol_files, TypeMap &types) {
+void SymbolFileDWARF::FindTypes(TypeMatch &match) {
+
   // Make sure we haven't already searched this SymbolFile before.
-  if (!searched_symbol_files.insert(this).second)
+  if (match.AlreadySearched(this))
     return;
 
   std::lock_guard<std::recursive_mutex> guard(GetModuleMutex());
-  if (pattern.empty())
-    return;
 
-  ConstString name = pattern.back().name;
+  bool have_index_match = false;
+  m_index->GetTypes(match.GetTypeBasename(), [&](DWARFDIE die) {
 
-  if (!name)
+    // Check the language, but only if we have a language filter.
+    if (match.HasLanguage()) {
+      if (!match.LanguageMatches(GetLanguageFamily(*die.GetCU())))
+        return true; // Keep iterating over index types, language mismatch.
+    }
+
+    // Check the context matches
+    llvm::SmallVector<CompilerContext, 4> die_context;
+    if (match.GetModuleSearch())
+      die.GetDeclContext(die_context);
+    else
+      die.GetTypeLookupContext(die_context);
+    assert(!die_context.empty());
+    if (!match.ContextMatches(die_context))
+      return true; // Keep iterating over index types, context mismatch.
+
+    // Try to resolve the type.
+    if (Type *matching_type = ResolveType(die, true, true)) {
+      have_index_match = true;
+      match.InsertUnique(matching_type->shared_from_this());
+    }
+    return !match.Done(); // Keep iterating if we aren't done.
+  });
+
+  if (match.Done())
     return;
 
-  m_index->GetTypes(name, [&](DWARFDIE die) {
-    if (!languages[GetLanguageFamily(*die.GetCU())])
-      return true;
+  // With -gsimple-template-names, a templated type's DW_AT_name will not
+  // contain the template parameters. Try again stripping '<' and anything
+  // after, filtering out entries with template parameters that don't match.
+  if (!have_index_match) {
+    // Create a type matcher with a compiler context that is tuned for
+    // -gsimple-template-names. We will use this for the index lookup and the
+    // context matching, but will use the original "match" to insert matches
+    // into if things match. The "match_simple" has a compiler context with
+    // all template parameters removed to allow the names and context to match.
+    // The UpdateCompilerContextForSimpleTemplateNames(...) will return true if
+    // it trims any context items down by removing template parameter names.
+    TypeMatch match_simple(match);
+    if (UpdateCompilerContextForSimpleTemplateNames(match_simple)) {
+
+      // Copy our match's context and update the basename we are looking for
+      // so we can use this only to compare the context correctly.
+      m_index->GetTypes(match_simple.GetTypeBasename(), [&](DWARFDIE die) {
+
+        // Check the language, but only if we have a language filter.
+        if (match.HasLanguage()) {
+          if (!match.LanguageMatches(GetLanguageFamily(*die.GetCU())))
+            return true; // Keep iterating over index types, language mismatch.
+        }
 
+        // Check the context matches
         llvm::SmallVector<CompilerContext, 4> die_context;
+        if (match.GetModuleSearch())
           die.GetDeclContext(die_context);
-    if (!contextMatches(die_context, pattern))
-      return true;
+        else
+          die.GetTypeLookupContext(die_context);
+        assert(!die_context.empty());
+        if (!match_simple.ContextMatches(die_context))
+          return true; // Keep iterating over index types, context mismatch.
 
+        // Try to resolve the type.
         if (Type *matching_type = ResolveType(die, true, true)) {
-      // We found a type pointer, now find the shared pointer form our type
-      // list.
-      types.InsertUnique(matching_type->shared_from_this());
+          ConstString name = matching_type->GetQualifiedName();
+          // We have found a type that still might not match due to template
+          // parameters. If we create a new TypeMatch that uses the new type's
+          // fully qualified name, we can find out if this type matches at all
+          // context levels. We can't use just the "match_simple" context
+          // because all template parameters were stripped off. The fully
+          // qualified name of the type will have the template parameters and
+          // will allow us to make sure it matches correctly.
+          TypeMatch die_match(name.GetStringRef(), /*exact_match=*/true);
+          if (!match.ContextMatches(die_match.GetContextRef()))
+            return true; // Keep iterating over index types, context mismatch.
+
+          match.InsertUnique(matching_type->shared_from_this());
         }
-    return true;
+        return !match.Done(); // Keep iterating if we aren't done.
       });
+      if (match.Done())
+        return;
+    }
+  }
 
   // Next search through the reachable Clang modules. This only applies for
   // DWARF objects compiled with -gmodules that haven't been processed by
   // dsymutil.
   UpdateExternalModuleListIfNeeded();
 
-  for (const auto &pair : m_external_type_modules)
-    if (ModuleSP external_module_sp = pair.second)
-      external_module_sp->FindTypes(pattern, languages, searched_symbol_files,
-                                    types);
+  for (const auto &pair : m_external_type_modules) {
+    if (ModuleSP external_module_sp = pair.second) {
+      external_module_sp->FindTypes(match);
+      if (match.Done())
+        return;
+    }
+  }
 }
 
 CompilerDeclContext
 SymbolFileDWARF::FindNamespace(ConstString name,
                                const CompilerDeclContext &parent_decl_ctx) {
   std::lock_guard<std::recursive_mutex> guard(GetModuleMutex());
   Log *log = GetLog(DWARFLog::Lookups);
 

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h

void FindGlobalVariables(const lldb_private::RegularExpression &regex,
                            lldb_private::VariableList &variables) override;
   void FindFunctions(const lldb_private::Module::LookupInfo &lookup_info,
                      const lldb_private::CompilerDeclContext &parent_decl_ctx,
                      bool include_inlines,
                      lldb_private::SymbolContextList &sc_list) override;
   void FindFunctions(const lldb_private::RegularExpression &regex,
                      bool include_inlines,
                      lldb_private::SymbolContextList &sc_list) override;
-  void
-  FindTypes(lldb_private::ConstString name,
-            const lldb_private::CompilerDeclContext &parent_decl_ctx,
-            uint32_t max_matches,
-            llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
-            lldb_private::TypeMap &types) override;
-  void
-  FindTypes(llvm::ArrayRef<lldb_private::CompilerContext> context,
-            lldb_private::LanguageSet languages,
-            llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
-            lldb_private::TypeMap &types) override;
+
+  void FindTypes(lldb_private::TypeMatch &match) override;
+
   lldb_private::CompilerDeclContext FindNamespace(
       lldb_private::ConstString name,
       const lldb_private::CompilerDeclContext &parent_decl_ctx) override;
   void GetTypes(lldb_private::SymbolContextScope *sc_scope,
                 lldb::TypeClass type_mask,
                 lldb_private::TypeList &type_list) override;
   std::vector<std::unique_ptr<lldb_private::CallEdge>>
   ParseCallEdgesInFunction(lldb_private::UserID func_id) override;

lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.cpp

ForEachSymbolFile([&](SymbolFileDWARF *oso_dwarf) -> bool {
       return (bool)type_sp;
     });
 
     return type_sp;
   }
   return TypeSP();
 }
 
-void SymbolFileDWARFDebugMap::FindTypes(
-    ConstString name, const CompilerDeclContext &parent_decl_ctx,
-    uint32_t max_matches,
-    llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
-    TypeMap &types) {
+void SymbolFileDWARFDebugMap::FindTypes(TypeMatch &match) {
   std::lock_guard<std::recursive_mutex> guard(GetModuleMutex());
   ForEachSymbolFile([&](SymbolFileDWARF *oso_dwarf) -> bool {
-    oso_dwarf->FindTypes(name, parent_decl_ctx, max_matches,
-                         searched_symbol_files, types);
-    return types.GetSize() >= max_matches;
-  });
-}
-
-void SymbolFileDWARFDebugMap::FindTypes(
-    llvm::ArrayRef<CompilerContext> context, LanguageSet languages,
-    llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
-    TypeMap &types) {
-  LLDB_SCOPED_TIMER();
-  ForEachSymbolFile([&](SymbolFileDWARF *oso_dwarf) -> bool {
-    oso_dwarf->FindTypes(context, languages, searched_symbol_files, types);
-    return false;
+    oso_dwarf->FindTypes(match);
+    return !match.Done(); // Keep iterating if we aren't done finding types.
   });
 }
 
 CompilerDeclContext SymbolFileDWARFDebugMap::FindNamespace(
     lldb_private::ConstString name,
     const CompilerDeclContext &parent_decl_ctx) {
   std::lock_guard<std::recursive_mutex> guard(GetModuleMutex());
   CompilerDeclContext matching_namespace;

lldb/source/Plugins/SymbolFile/NativePDB/SymbolFileNativePDB.h

void FindFunctions(const Module::LookupInfo &lookup_info,
                      const CompilerDeclContext &parent_decl_ctx,
                      bool include_inlines, SymbolContextList &sc_list) override;
 
   void FindFunctions(const RegularExpression &regex, bool include_inlines,
                      SymbolContextList &sc_list) override;
 
   llvm::Optional<PdbCompilandSymId> FindSymbolScope(PdbCompilandSymId id);
 
-  void FindTypes(ConstString name, const CompilerDeclContext &parent_decl_ctx,
-                 uint32_t max_matches,
-                 llvm::DenseSet<SymbolFile *> &searched_symbol_files,
-                 TypeMap &types) override;
+  // void FindTypes(ConstString name, const CompilerDeclContext &parent_decl_ctx,
+  //                uint32_t max_matches,
+  //                llvm::DenseSet<SymbolFile *> &searched_symbol_files,
+  //                TypeMap &types) override;
+
+  // void FindTypes(llvm::ArrayRef<CompilerContext> pattern, LanguageSet languages,
+  //                llvm::DenseSet<SymbolFile *> &searched_symbol_files,
+  //                TypeMap &types) override;
 
-  void FindTypes(llvm::ArrayRef<CompilerContext> pattern, LanguageSet languages,
-                 llvm::DenseSet<SymbolFile *> &searched_symbol_files,
-                 TypeMap &types) override;
+  void FindTypes(lldb_private::TypeMatch &match) override;
 
   llvm::Expected<TypeSystem &>
   GetTypeSystemForLanguage(lldb::LanguageType language) override;
 
   CompilerDeclContext
   FindNamespace(ConstString name,
                 const CompilerDeclContext &parent_decl_ctx) override;
 

lldb/source/Plugins/SymbolFile/NativePDB/SymbolFileNativePDB.cpp

for (const SymbolAndOffset &match : matches) {
     sc_list.Append(sc);
   }
 }
 
 void SymbolFileNativePDB::FindFunctions(const RegularExpression &regex,
                                         bool include_inlines,
                                         SymbolContextList &sc_list) {}
 
-void SymbolFileNativePDB::FindTypes(
-    ConstString name, const CompilerDeclContext &parent_decl_ctx,
-    uint32_t max_matches, llvm::DenseSet<SymbolFile *> &searched_symbol_files,
-    TypeMap &types) {
-  std::lock_guard<std::recursive_mutex> guard(GetModuleMutex());
-  if (!name)
+void SymbolFileNativePDB::FindTypes(lldb_private::TypeMatch &match) {
+
+  // Make sure we haven't already searched this SymbolFile before.
+  if (match.AlreadySearched(this))
     return;
 
-  searched_symbol_files.clear();
-  searched_symbol_files.insert(this);
+  std::lock_guard<std::recursive_mutex> guard(GetModuleMutex());
 
-  // There is an assumption 'name' is not a regex
-  FindTypesByName(name.GetStringRef(), max_matches, types);
-}
+  std::vector<TypeIndex> matches =
+      m_index->tpi().findRecordsByName(match.GetTypeBasename().GetStringRef());
 
-void SymbolFileNativePDB::FindTypes(
-    llvm::ArrayRef<CompilerContext> pattern, LanguageSet languages,
-    llvm::DenseSet<SymbolFile *> &searched_symbol_files, TypeMap &types) {}
+  for (TypeIndex type_idx : matches) {
+    TypeSP type_sp = GetOrCreateType(type_idx);
+    if (!type_sp)
+      continue;
+
+    // We resolved a type. Get the fully qualified name to ensure it matches.
+    ConstString name = type_sp->GetQualifiedName();
+    TypeMatch type_match(name.GetStringRef(), /*exact_match=*/true);
+    if (match.ContextMatches(type_match.GetContextRef())) {
+      match.InsertUnique(type_sp);
+      if (match.Done())
+        return;
+    }
+  }
+}
 
 void SymbolFileNativePDB::FindTypesByName(llvm::StringRef name,
                                           uint32_t max_matches,
                                           TypeMap &types) {
 
   std::vector<TypeIndex> matches = m_index->tpi().findRecordsByName(name);
   if (max_matches > 0 && max_matches < matches.size())
     matches.resize(max_matches);

lldb/source/Plugins/SymbolFile/PDB/SymbolFilePDB.h

void FindFunctions(const lldb_private::RegularExpression &regex,
                      bool include_inlines,
                      lldb_private::SymbolContextList &sc_list) override;
 
   void GetMangledNamesForFunction(
       const std::string &scope_qualified_name,
       std::vector<lldb_private::ConstString> &mangled_names) override;
 
   void AddSymbols(lldb_private::Symtab &symtab) override;
-
-  void
-  FindTypes(lldb_private::ConstString name,
-            const lldb_private::CompilerDeclContext &parent_decl_ctx,
-            uint32_t max_matches,
-            llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
-            lldb_private::TypeMap &types) override;
-
-  void FindTypes(llvm::ArrayRef<lldb_private::CompilerContext> pattern,
-                 lldb_private::LanguageSet languages,
-                 llvm::DenseSet<SymbolFile *> &searched_symbol_files,
-                 lldb_private::TypeMap &types) override;
-
+  void FindTypes(lldb_private::TypeMatch &match) override;
   void FindTypesByRegex(const lldb_private::RegularExpression &regex,
                         uint32_t max_matches, lldb_private::TypeMap &types);
 
   void GetTypes(lldb_private::SymbolContextScope *sc_scope,
                 lldb::TypeClass type_mask,
                 lldb_private::TypeList &type_list) override;
 
   llvm::Expected<lldb_private::TypeSystem &>

lldb/source/Plugins/SymbolFile/PDB/SymbolFilePDB.cpp

symtab.AddSymbol(
                false,     // contains_linker_annotations
                0          // flags
                ));
   }
 
   symtab.Finalize();
 }
 
-void SymbolFilePDB::FindTypes(
-    lldb_private::ConstString name, const CompilerDeclContext &parent_decl_ctx,
-    uint32_t max_matches,
-    llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
-    lldb_private::TypeMap &types) {
-  std::lock_guard<std::recursive_mutex> guard(GetModuleMutex());
-  if (!name)
-    return;
-  if (!DeclContextMatchesThisSymbolFile(parent_decl_ctx))
-    return;
-
-  searched_symbol_files.clear();
-  searched_symbol_files.insert(this);
-
-  // There is an assumption 'name' is not a regex
-  FindTypesByName(name.GetStringRef(), parent_decl_ctx, max_matches, types);
-}
+// void SymbolFilePDB::FindTypes(
+//     lldb_private::ConstString name, const CompilerDeclContext &parent_decl_ctx,
+//     uint32_t max_matches,
+//     llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
+//     lldb_private::TypeMap &types) {
+//   std::lock_guard<std::recursive_mutex> guard(GetModuleMutex());
+//   if (!name)
+//     return;
+//   if (!DeclContextMatchesThisSymbolFile(parent_decl_ctx))
+//     return;
+
+//   searched_symbol_files.clear();
+//   searched_symbol_files.insert(this);
+
+//   // There is an assumption 'name' is not a regex
+//   FindTypesByName(name.GetStringRef(), parent_decl_ctx, max_matches, types);
+// }
 
 void SymbolFilePDB::DumpClangAST(Stream &s) {
   auto type_system_or_err =
       GetTypeSystemForLanguage(lldb::eLanguageTypeC_plus_plus);
   if (auto err = type_system_or_err.takeError()) {
     LLDB_LOG_ERROR(GetLog(LLDBLog::Symbols), std::move(err),
                    "Unable to dump ClangAST");
     return;
while (auto result = results->getNext()) {
       if (iter == m_types.end())
         continue;
       types.Insert(iter->second);
       ++matches;
     }
   }
 }
 
-void SymbolFilePDB::FindTypesByName(
-    llvm::StringRef name,
-    const lldb_private::CompilerDeclContext &parent_decl_ctx,
-    uint32_t max_matches, lldb_private::TypeMap &types) {
+void SymbolFilePDB::FindTypes(lldb_private::TypeMatch &match) {
+
+  // Make sure we haven't already searched this SymbolFile before.
+  if (match.AlreadySearched(this))
+    return;
+
+  std::lock_guard<std::recursive_mutex> guard(GetModuleMutex());
+
+
   std::unique_ptr<IPDBEnumSymbols> results;
-  if (name.empty())
+  llvm::StringRef basename = match.GetTypeBasename().GetStringRef();
+  if (basename.empty())
     return;
   results = m_global_scope_up->findAllChildren(PDB_SymType::None);
   if (!results)
     return;
 
-  uint32_t matches = 0;
-
   while (auto result = results->getNext()) {
-    if (max_matches > 0 && matches >= max_matches)
-      break;
 
     if (MSVCUndecoratedNameParser::DropScope(
-            result->getRawSymbol().getName()) != name)
+            result->getRawSymbol().getName()) != basename)
       continue;
 
     switch (result->getSymTag()) {
     case PDB_SymType::Enum:
     case PDB_SymType::UDT:
     case PDB_SymType::Typedef:
       break;
     default:
       // We're looking only for types that have names.  Skip symbols, as well
       // as unnamed types such as arrays, pointers, etc.
       continue;
     }
 
     // This should cause the type to get cached and stored in the `m_types`
     // lookup.
     if (!ResolveTypeUID(result->getSymIndexId()))
       continue;
 
-    if (parent_decl_ctx.IsValid() &&
-        GetDeclContextContainingUID(result->getSymIndexId()) != parent_decl_ctx)
-      continue;
-
     auto iter = m_types.find(result->getSymIndexId());
     if (iter == m_types.end())
       continue;
-    types.Insert(iter->second);
-    ++matches;
+    // We resolved a type. Get the fully qualified name to ensure it matches.
+    ConstString name = iter->second->GetQualifiedName();
+    TypeMatch type_match(name.GetStringRef(), /*exact_match=*/true);
+    if (match.ContextMatches(type_match.GetContextRef())) {
+      match.InsertUnique(iter->second);
+      if (match.Done())
+        return;
+    }
   }
 }
 
-void SymbolFilePDB::FindTypes(
-    llvm::ArrayRef<CompilerContext> pattern, LanguageSet languages,
-    llvm::DenseSet<SymbolFile *> &searched_symbol_files,
-    lldb_private::TypeMap &types) {}
 
 void SymbolFilePDB::GetTypesForPDBSymbol(const llvm::pdb::PDBSymbol &pdb_symbol,
                                          uint32_t type_mask,
                                          TypeCollection &type_collection) {
   bool can_parse = false;
   switch (pdb_symbol.getSymTag()) {
   case PDB_SymType::ArrayType:
     can_parse = ((type_mask & eTypeClassArray) != 0);

lldb/source/Plugins/TypeSystem/Clang/TypeSystemClang.h

public:
 
   CompilerType DeclGetFunctionReturnType(void *opaque_decl) override;
 
   size_t DeclGetFunctionNumArguments(void *opaque_decl) override;
 
   CompilerType DeclGetFunctionArgumentType(void *opaque_decl,
                                            size_t arg_idx) override;
 
+  void DeclGetCompilerContext(void *opaque_decl,
+      llvm::SmallVectorImpl<lldb_private::CompilerContext> &context) override;
+
   CompilerType GetTypeForDecl(void *opaque_decl) override;
 
   // CompilerDeclContext override functions
 
   /// Creates a CompilerDeclContext from the given DeclContext
   /// with the current TypeSystemClang instance as its typesystem.
   /// The DeclContext has to come from the ASTContext of this
   /// TypeSystemClang.
public:
   bool DeclContextIsClassMethod(void *opaque_decl_ctx,
                                 lldb::LanguageType *language_ptr,
                                 bool *is_instance_method_ptr,
                                 ConstString *language_object_name_ptr) override;
 
   bool DeclContextIsContainedInLookup(void *opaque_decl_ctx,
                                       void *other_opaque_decl_ctx) override;
 
+  void DeclContextGetCompilerContext(void *opaque_decl_ctx,
+      llvm::SmallVectorImpl<lldb_private::CompilerContext> &context) override;
+
   // Clang specific clang::DeclContext functions
 
   static clang::DeclContext *
   DeclContextGetAsDeclContext(const CompilerDeclContext &dc);
 
   static clang::ObjCMethodDecl *
   DeclContextGetAsObjCMethodDecl(const CompilerDeclContext &dc);
 

lldb/source/Plugins/TypeSystem/Clang/TypeSystemClang.cpp

if (clang::FunctionDecl *func_decl =
     return func_decl->param_size();
   if (clang::ObjCMethodDecl *objc_method =
           llvm::dyn_cast<clang::ObjCMethodDecl>((clang::Decl *)opaque_decl))
     return objc_method->param_size();
   else
     return 0;
 }
 
+static CompilerContextKind GetCompilerKind(clang::Decl::Kind clang_kind,
+                                           clang::DeclContext *decl_ctx) {
+  switch (clang_kind) {
+    case Decl::TranslationUnit:
+      return CompilerContextKind::TranslationUnit;
+    case Decl::Namespace:
+      return CompilerContextKind::Namespace;
+    case Decl::Var:
+      return CompilerContextKind::Variable;
+    case Decl::Enum:
+      return CompilerContextKind::Enum;
+    case Decl::Typedef:
+      return CompilerContextKind::Typedef;
+    default:
+      // Many other kinds have multiple values
+      if (decl_ctx) {
+        if (decl_ctx->isFunctionOrMethod())
+          return CompilerContextKind::Function;
+        else if (decl_ctx->isRecord())
+          return (CompilerContextKind)(
+              (uint16_t)CompilerContextKind::Class |
+              (uint16_t)CompilerContextKind::Struct |
+              (uint16_t)CompilerContextKind::Union);
+      }
+      break;
+  }
+  return CompilerContextKind::Any;
+}
+
+static void InsertCompilerContext(TypeSystemClang *ts,
+    clang::DeclContext *decl_ctx,
+    llvm::SmallVectorImpl<lldb_private::CompilerContext> &context) {
+  if (decl_ctx == nullptr)
+    return;
+  InsertCompilerContext(ts, decl_ctx->getParent(), context);
+  clang::Decl::Kind clang_kind = decl_ctx->getDeclKind();
+  if (clang_kind == Decl::TranslationUnit)
+    return; // Stop at the translation unit.
+  const CompilerContextKind compiler_kind = GetCompilerKind(clang_kind, decl_ctx);
+  ConstString decl_ctx_name = ts->DeclContextGetName(decl_ctx);
+  context.push_back({compiler_kind, decl_ctx_name});
+}
+
+void TypeSystemClang::DeclGetCompilerContext(void *opaque_decl,
+    llvm::SmallVectorImpl<lldb_private::CompilerContext> &context) {
+  ConstString decl_name = DeclGetName(opaque_decl);
+  if (!decl_name) {
+    // If this decl doesn't have a name, we can't make a compiler context for it.
+    context.clear();
+    return;
+  }
+  clang::Decl *decl = (clang::Decl *)opaque_decl;
+  // Add the entire decl context first
+  clang::DeclContext *decl_ctx = decl->getDeclContext();
+  InsertCompilerContext(this, decl_ctx, context);
+  // Now add the decl information
+  auto compiler_kind = GetCompilerKind(decl->getKind(),
+                                       dyn_cast<DeclContext>(decl));
+  context.push_back({compiler_kind, decl_name});
+}
+
+
 CompilerType TypeSystemClang::DeclGetFunctionArgumentType(void *opaque_decl,
                                                           size_t idx) {
   if (clang::FunctionDecl *func_decl =
           llvm::dyn_cast<clang::FunctionDecl>((clang::Decl *)opaque_decl)) {
     if (idx < func_decl->param_size()) {
       ParmVarDecl *var_decl = func_decl->getParamDecl(idx);
       if (var_decl)
         return GetType(var_decl->getOriginalType());
if (ObjCMethodDecl *objc_method =
           language_object_name_ptr->SetCString(metadata->GetObjectPtrName());
         return true;
       }
     }
   }
   return false;
 }
 
+void TypeSystemClang::DeclContextGetCompilerContext(void *opaque_decl_ctx,
+    llvm::SmallVectorImpl<lldb_private::CompilerContext> &context) {
+  auto *decl_ctx = (clang::DeclContext *)opaque_decl_ctx;
+  InsertCompilerContext(this, decl_ctx, context);
+}
+
 bool TypeSystemClang::DeclContextIsContainedInLookup(
     void *opaque_decl_ctx, void *other_opaque_decl_ctx) {
   auto *decl_ctx = (clang::DeclContext *)opaque_decl_ctx;
   auto *other = (clang::DeclContext *)other_opaque_decl_ctx;
 
   do {
     // A decl context always includes its own contents in its lookup.
     if (decl_ctx == other)

lldb/source/Symbol/CompilerDecl.cpp

return lhs.GetTypeSystem() == rhs.GetTypeSystem() &&
          lhs.GetOpaqueDecl() == rhs.GetOpaqueDecl();
 }
 
 bool lldb_private::operator!=(const lldb_private::CompilerDecl &lhs,
                               const lldb_private::CompilerDecl &rhs) {
   return lhs.GetTypeSystem() != rhs.GetTypeSystem() ||
          lhs.GetOpaqueDecl() != rhs.GetOpaqueDecl();
 }
+
+void CompilerDecl::GetCompilerContext(
+    llvm::SmallVectorImpl<lldb_private::CompilerContext> &context) const {
+  return m_type_system->DeclGetCompilerContext(m_opaque_decl, context);
+}

lldb/source/Symbol/CompilerDeclContext.cpp

bool CompilerDeclContext::IsContainedInLookup(CompilerDeclContext other) const {
   // over the type system to know that the lookup is identical.
   if (this == &other)
     return true;
 
   return m_type_system->DeclContextIsContainedInLookup(m_opaque_decl_ctx,
                                                        other.m_opaque_decl_ctx);
 }
 
+void CompilerDeclContext::GetCompilerContext(
+    llvm::SmallVectorImpl<lldb_private::CompilerContext> &context) const {
+  context.clear();
+  if (IsValid())
+    return m_type_system->DeclContextGetCompilerContext(m_opaque_decl_ctx,
+                                                        context);
+}
+
 bool lldb_private::operator==(const lldb_private::CompilerDeclContext &lhs,
                               const lldb_private::CompilerDeclContext &rhs) {
   return lhs.GetTypeSystem() == rhs.GetTypeSystem() &&
          lhs.GetOpaqueDeclContext() == rhs.GetOpaqueDeclContext();
 }
 
 bool lldb_private::operator!=(const lldb_private::CompilerDeclContext &lhs,
                               const lldb_private::CompilerDeclContext &rhs) {
   return lhs.GetTypeSystem() != rhs.GetTypeSystem() ||
          lhs.GetOpaqueDeclContext() != rhs.GetOpaqueDeclContext();
 }

lldb/source/Symbol/SymbolFile.cpp

 void SymbolFile::FindFunctions(const RegularExpression &regex,
                                bool include_inlines,
                                SymbolContextList &sc_list) {}
 
 void SymbolFile::GetMangledNamesForFunction(
     const std::string &scope_qualified_name,
     std::vector<ConstString> &mangled_names) {}
 
-void SymbolFile::FindTypes(
-    ConstString name, const CompilerDeclContext &parent_decl_ctx,
-    uint32_t max_matches,
-    llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
-    TypeMap &types) {}
-
-void SymbolFile::FindTypes(llvm::ArrayRef<CompilerContext> pattern,
-                           LanguageSet languages,
-                           llvm::DenseSet<SymbolFile *> &searched_symbol_files,
-                           TypeMap &types) {}
-
 void SymbolFile::AssertModuleLock() {
   // The code below is too expensive to leave enabled in release builds. It's
   // enabled in debug builds or when the correct macro is set.
 #if defined(LLDB_CONFIGURATION_DEBUG)
   // We assert that we have to module lock by trying to acquire the lock from a
   // different thread. Note that we must abort if the result is true to
   // guarantee correctness.
   assert(std::async(

lldb/source/Symbol/SymbolFileOnDemand.cpp

if (!m_debug_info_enabled) {
     LLDB_LOG(log, "[{0}] {1}({2}) is skipped", GetSymbolFileName(),
              __FUNCTION__, scope_qualified_name);
     return;
   }
   return m_sym_file_impl->GetMangledNamesForFunction(scope_qualified_name,
                                                      mangled_names);
 }
 
-void SymbolFileOnDemand::FindTypes(
-    ConstString name, const CompilerDeclContext &parent_decl_ctx,
-    uint32_t max_matches,
-    llvm::DenseSet<lldb_private::SymbolFile *> &searched_symbol_files,
-    TypeMap &types) {
-  if (!m_debug_info_enabled) {
-    Log *log = GetLog();
-    LLDB_LOG(log, "[{0}] {1}({2}) is skipped", GetSymbolFileName(),
-             __FUNCTION__, name);
-    return;
-  }
-  return m_sym_file_impl->FindTypes(name, parent_decl_ctx, max_matches,
-                                    searched_symbol_files, types);
-}
-
-void SymbolFileOnDemand::FindTypes(
-    llvm::ArrayRef<CompilerContext> pattern, LanguageSet languages,
-    llvm::DenseSet<SymbolFile *> &searched_symbol_files, TypeMap &types) {
+void SymbolFileOnDemand::FindTypes(TypeMatch &match) {
   if (!m_debug_info_enabled) {
     LLDB_LOG(GetLog(), "[{0}] {1} is skipped", GetSymbolFileName(),
              __FUNCTION__);
     return;
   }
-  return m_sym_file_impl->FindTypes(pattern, languages, searched_symbol_files,
-                                    types);
+  return m_sym_file_impl->FindTypes(match);
 }
 
 void SymbolFileOnDemand::GetTypes(SymbolContextScope *sc_scope,
                                   TypeClass type_mask, TypeList &type_list) {
   if (!m_debug_info_enabled) {
     LLDB_LOG(GetLog(), "[{0}] {1} is skipped", GetSymbolFileName(),
              __FUNCTION__);
     return;

lldb/source/Symbol/Type.cpp

if (*ctx != pat) {
       if (pat.kind != CompilerContextKind::AnyModule && ctx->name != pat.name)
         return false;
     }
     ++ctx;
   }
   return true;
 }
 
+static CompilerContextKind ConvertTypeClass(lldb::TypeClass type_class) {
+  if (type_class == eTypeClassAny)
+    return CompilerContextKind::AnyType;
+  uint16_t result = 0;
+  if (type_class & lldb::eTypeClassClass)
+    result |= (uint16_t)CompilerContextKind::Class;
+  if (type_class & lldb::eTypeClassStruct)
+    result |= (uint16_t)CompilerContextKind::Struct;
+  if (type_class & lldb::eTypeClassUnion)
+    result |= (uint16_t)CompilerContextKind::Union;
+  if (type_class & lldb::eTypeClassEnumeration)
+    result |= (uint16_t)CompilerContextKind::Enum;
+  if (type_class & lldb::eTypeClassFunction)
+    result |= (uint16_t)CompilerContextKind::Function;
+  if (type_class & lldb::eTypeClassTypedef)
+    result |= (uint16_t)CompilerContextKind::Typedef;
+  return (CompilerContextKind)result;
+}
+
+TypeMatch::TypeMatch(llvm::StringRef name, bool exact_match) {
+  SetMatchContext(name, exact_match);
+}
+
+void TypeMatch::SetMatchContext(llvm::StringRef name, bool exact_match) {
+  llvm::StringRef scope, basename;
+  lldb::TypeClass type_class = lldb::eTypeClassAny;
+  if (Type::GetTypeScopeAndBasename(name, scope, basename, type_class)) {
+    m_exact_match = exact_match | scope.consume_front("::");
+    if (!scope.empty()) {
+      std::pair<llvm::StringRef, llvm::StringRef> scope_pair = scope.split("::");
+      while (!scope_pair.second.empty()) {
+        m_context.push_back({CompilerContextKind::AnyDeclContext,
+                             ConstString(scope_pair.first.str())});
+        scope_pair = scope_pair.second.split("::");
+      }
+      m_context.push_back({CompilerContextKind::AnyDeclContext,
+                           ConstString(scope_pair.first.str())});
+    }
+    m_context.push_back({ConvertTypeClass(type_class),
+                         ConstString(basename.str())});
+  } else {
+    m_context.push_back({CompilerContextKind::AnyType,
+                         ConstString(name.str())});
+    m_exact_match = exact_match;
+  }
+}
+TypeMatch::TypeMatch(const CompilerDeclContext &decl_ctx,
+                     ConstString type_basename) {
+  SetMatchContext(decl_ctx, type_basename);
+}
+
+TypeMatch::TypeMatch(const TypeMatch &rhs) :
+  m_context(rhs.m_context),
+  m_exact_match(rhs.m_exact_match),
+  m_max_matches(rhs.m_max_matches),
+  m_languages(rhs.m_languages) {}
+
+TypeMatch::TypeMatch(const CompilerDecl &decl) {
+  SetMatchContext(decl);
+}
+
+void
+TypeMatch::SetMatchContext(const CompilerDeclContext &decl_ctx,
+                           ConstString type_basename) {
+  m_exact_match = true;
+  decl_ctx.GetCompilerContext(m_context);
+  m_context.push_back({CompilerContextKind::AnyType, type_basename});
+}
+
+void
+TypeMatch::SetMatchContext(const CompilerDecl &decl) {
+  m_exact_match = true;
+  decl.GetCompilerContext(m_context);
+}
+
+ConstString TypeMatch::GetTypeBasename() const {
+  if (m_context.empty())
+    return ConstString();
+  return m_context.back().name;
+}
+
+lldb::TypeSP TypeMatch::FindFirstType(lldb_private::Module *module) {
+  if (!module)
+    return TypeSP();
+  m_max_matches = 1;
+  module->FindTypes(*this);
+  if (m_type_map.Empty())
+    return TypeSP();
+  return m_type_map.FirstType();
+}
+
+lldb::TypeSP TypeMatch::FindFirstType(const lldb_private::ModuleList &module_list,
+                                      lldb_private::Module *search_first) {
+  m_max_matches = 1;
+  module_list.FindTypes(search_first, *this);
+  if (m_type_map.Empty())
+    return TypeSP();
+  return m_type_map.FirstType();
+}
+
+void TypeMatch::SortTypeList(Module *module, TypeList &type_list) {
+  if (!module)
+    return AppendTypes(type_list);
+  SymbolContext sc;
+  sc.module_sp = module->shared_from_this();
+  sc.SortTypeList(m_type_map, type_list);
+}
+
+void TypeMatch::AddLanguage(LanguageType language) {
+  if (!m_languages)
+    m_languages = LanguageSet();
+  m_languages->Insert(language);
+}
+
+void TypeMatch::AppendTypes(TypeList &type_list) const {
+  m_type_map.ForEach([&type_list](const lldb::TypeSP &type_sp) -> bool {
+    type_list.Insert(type_sp);
+    return true; // Keep iterating
+  });
+}
+
+bool TypeMatch::ContextMatches(llvm::ArrayRef<CompilerContext> context_chain) const {
+  if (m_exact_match || context_chain.size() == m_context.size())
+    return ::contextMatches(context_chain, m_context);
+
+  // We don't have an exact match, we need to bottom m_context.size() items to
+  // match for a successful lookup.
+  if (context_chain.size() < m_context.size())
+    return false; // Not enough items in context_chain to allow for a match.
+
+  size_t compare_count = context_chain.size() - m_context.size();
+  return ::contextMatches(
+      llvm::ArrayRef<CompilerContext>(context_chain.data() + compare_count,
+                                      m_context.size()),
+      m_context);
+}
+
+bool TypeMatch::AlreadySearched(lldb_private::SymbolFile *sym_file) {
+  return !m_searched_symbol_files.insert(sym_file).second;
+}
+
+bool TypeMatch::LanguageMatches(lldb::LanguageType language) const {
+  // If we have no language filterm language always matches.
+  if (!m_languages.has_value())
+    return true;
+  return (*m_languages)[language];
+}
+
+bool TypeMatch::Done() const {
+  if (!m_max_matches.has_value())
+    return false;
+  return m_type_map.GetSize() >= *m_max_matches;
+}
+
+void TypeMatch::InsertUnique(lldb::TypeSP type_sp) {
+  m_type_map.InsertUnique(type_sp);
+}
+
 void CompilerContext::Dump() const {
   switch (kind) {
   default:
     printf("Invalid");
     break;
   case CompilerContextKind::TranslationUnit:
     printf("TranslationUnit");
     break;
bool Type::GetTypeScopeAndBasename(llvm::StringRef name,
                                    llvm::StringRef &scope,
                                    llvm::StringRef &basename,
                                    TypeClass &type_class) {
   type_class = eTypeClassAny;
 
   if (name.empty())
     return false;
 
+  // Clear the scope in case we have just a type class and a basename.
+  scope = llvm::StringRef();
   basename = name;
   if (basename.consume_front("struct "))
     type_class = eTypeClassStruct;
   else if (basename.consume_front("class "))
     type_class = eTypeClassClass;
   else if (basename.consume_front("union "))
     type_class = eTypeClassUnion;
   else if (basename.consume_front("enum "))
     type_class = eTypeClassEnumeration;
   else if (basename.consume_front("typedef "))
     type_class = eTypeClassTypedef;
 
   size_t namespace_separator = basename.find("::");
-  if (namespace_separator == llvm::StringRef::npos)
-    return false;
+  if (namespace_separator == llvm::StringRef::npos) {
+    // If "name" started a type class we need to return true with no scope.
+    return type_class != eTypeClassAny;
+  }
 
   size_t template_begin = basename.find('<');
   while (namespace_separator != llvm::StringRef::npos) {
     if (template_begin != llvm::StringRef::npos &&
         namespace_separator > template_begin) {
       size_t template_depth = 1;
       llvm::StringRef template_arg =
           basename.drop_front(template_begin + 1);

lldb/source/Symbol/TypeMap.cpp

TypeSP TypeMap::GetTypeAtIndex(uint32_t idx) {
   for (pos = m_types.begin(), end = m_types.end(); pos != end; ++pos) {
     if (i == 0)
       return pos->second;
     --i;
   }
   return TypeSP();
 }
 
+lldb::TypeSP TypeMap::FirstType() const {
+  if (m_types.empty())
+    return TypeSP();
+  return m_types.begin()->second;
+}
+
 void TypeMap::ForEach(
     std::function<bool(const lldb::TypeSP &type_sp)> const &callback) const {
   for (auto pos = m_types.begin(), end = m_types.end(); pos != end; ++pos) {
     if (!callback(pos->second))
       break;
   }
 }
 
for (iterator pos = m_types.find(uid), end = m_types.end();
         m_types.erase(pos);
         return true;
       }
     }
   }
   return false;
 }
 
-void TypeMap::Dump(Stream *s, bool show_context, lldb::DescriptionLevel level) {
-  for (iterator pos = m_types.begin(), end = m_types.end(); pos != end; ++pos) {
-    pos->second->Dump(s, show_context, level);
-  }
+void TypeMap::Dump(Stream *s, bool show_context,
+                   lldb::DescriptionLevel level) const {
+  for (const auto &pair : m_types)
+    pair.second->Dump(s, show_context, level);
 }
 
 void TypeMap::RemoveMismatchedTypes(llvm::StringRef type_scope,
                                     llvm::StringRef type_basename,
                                     TypeClass type_class, bool exact_match) {
   // Our "collection" type currently is a std::map which doesn't have any good
   // way to iterate and remove items from the map so we currently just make a
   // new list and add all of the matching types to it, and then swap it into

lldb/source/Symbol/TypeSystem.cpp

 
 size_t TypeSystem::DeclGetFunctionNumArguments(void *opaque_decl) { return 0; }
 
 CompilerType TypeSystem::DeclGetFunctionArgumentType(void *opaque_decl,
                                                      size_t arg_idx) {
   return CompilerType();
 }
 
+void TypeSystem::DeclGetCompilerContext(void *opaque_decl,
+    llvm::SmallVectorImpl<lldb_private::CompilerContext> &context) {
+  context.clear();
+}
+
+ void TypeSystem::DeclContextGetCompilerContext(void *opaque_decl_ctx,
+    llvm::SmallVectorImpl<lldb_private::CompilerContext> &context) {
+  context.clear();
+}
+
 std::vector<CompilerDecl>
 TypeSystem::DeclContextFindDeclByName(void *opaque_decl_ctx, ConstString name,
                                       bool ignore_imported_decls) {
   return std::vector<CompilerDecl>();
 }
 
 std::unique_ptr<UtilityFunction>
 TypeSystem::CreateUtilityFunction(std::string text, std::string name) {

lldb/source/Target/Language.cpp

 
 bool Language::ImageListTypeScavenger::Find_Impl(
     ExecutionContextScope *exe_scope, const char *key, ResultSet &results) {
   bool result = false;
 
   Target *target = exe_scope->CalculateTarget().get();
   if (target) {
     const auto &images(target->GetImages());
-    ConstString cs_key(key);
-    llvm::DenseSet<SymbolFile *> searched_sym_files;
-    TypeList matches;
-    images.FindTypes(nullptr, cs_key, false, UINT32_MAX, searched_sym_files,
-                     matches);
-    for (const auto &match : matches.Types()) {
+    TypeMatch match(key, false);
+    images.FindTypes(nullptr, match);
+    for (const auto &match : match.GetTypeMap().Types()) {
       if (match) {
         CompilerType compiler_type(match->GetFullCompilerType());
         compiler_type = AdjustForInclusion(compiler_type);
         if (!compiler_type)
           continue;
         std::unique_ptr<Language::TypeScavenger::Result> scavengeresult(
             new Result(compiler_type));
         results.insert(std::move(scavengeresult));
         result = true;
       }
     }
   }
 
   return result;
 }
 
 bool Language::GetFormatterPrefixSuffix(ValueObject &valobj,
                                         ConstString type_hint,
                                         std::string &prefix,
                                         std::string &suffix) {
   return false;
 }
 
-bool Language::DemangledNameContainsPath(llvm::StringRef path, 
+bool Language::DemangledNameContainsPath(llvm::StringRef path,
                                          ConstString demangled) const {
   // The base implementation does a simple contains comparision:
   if (path.empty())
     return false;
-  return demangled.GetStringRef().contains(path);                                         
+  return demangled.GetStringRef().contains(path);
 }
 
 DumpValueObjectOptions::DeclPrintingHelper Language::GetDeclPrintingHelper() {
   return nullptr;
 }
 
 LazyBool Language::IsLogicalTrue(ValueObject &valobj, Status &error) {
   return eLazyBoolCalculate;

lldb/test/API/functionalities/type_find_first/Makefile

+CXX_SOURCES := main.cpp
+include Makefile.rules

lldb/test/API/functionalities/type_find_first/TestFindFirstType.py

+"""
+Test the SBModule and SBTarget type lookup APIs.
+"""
+
+import lldb
+from lldbsuite.test.lldbtest import *
+from lldbsuite.test import lldbutil
+
+
+class TypeFindFirstTestCase(TestBase):
+
+    NO_DEBUG_INFO_TESTCASE = True
+
+    def test_find_first_type(self):
+        """
+            Test SBTarget::FindFirstType() and SBModule::FindFirstType() APIs.
+
+            This function had regressed after some past modification of the type
+            lookup internal code where if we had multiple types with the same
+            basename, FindFirstType() could end up failing depending on which
+            type was found first in the debug info indexes. This test will
+            ensure this doesn't regress in the future.
+        """
+        self.build()
+        target = self.createTestTarget()
+        # Test the SBTarget APIs for FindFirstType
+        integer_type = target.FindFirstType("Integer::Point")
+        self.assertTrue(integer_type.IsValid())
+        float_type = target.FindFirstType("Float::Point")
+        self.assertTrue(float_type.IsValid())
+
+        # Test the SBModule APIs for FindFirstType
+        exe_module = target.GetModuleAtIndex(0)
+        self.assertTrue(exe_module.IsValid())
+        integer_type = exe_module.FindFirstType("Integer::Point")
+        self.assertTrue(integer_type.IsValid())
+        float_type = exe_module.FindFirstType("Float::Point")
+        self.assertTrue(float_type.IsValid())

lldb/test/API/functionalities/type_find_first/main.cpp

+namespace Integer {
+struct Point {
+  int x, y;
+};
+} // namespace Integer
+
+namespace Float {
+struct Point {
+  float x, y;
+};
+} // namespace Float
+
+int main(int argc, char const *argv[]) {
+  Integer::Point ip = {2, 3};
+  Float::Point fp = {2.0, 3.0};
+  return 0;
+}

lldb/tools/lldb-test/lldb-test.cpp

 int evaluateMemoryMapCommands(Debugger &Dbg);
 } // namespace irmemorymap
 
 namespace assert {
 int lldb_assert(Debugger &Dbg);
 } // namespace assert
 } // namespace opts
 
-std::vector<CompilerContext> parseCompilerContext() {
-  std::vector<CompilerContext> result;
+llvm::SmallVector<CompilerContext, 4> parseCompilerContext() {
+  llvm::SmallVector<CompilerContext, 4> result;
   if (opts::symbols::CompilerContext.empty())
     return result;
 
   StringRef str{opts::symbols::CompilerContext};
   SmallVector<StringRef, 8> entries_str;
   str.split(entries_str, ',', /*maxSplit*/-1, /*keepEmpty=*/false);
   for (auto entry_str : entries_str) {
     StringRef key, value;
Error opts::symbols::findNamespaces(lldb_private::Module &Module) {
   return Error::success();
 }
 
 Error opts::symbols::findTypes(lldb_private::Module &Module) {
   SymbolFile &Symfile = *Module.GetSymbolFile();
   Expected<CompilerDeclContext> ContextOr = getDeclContext(Symfile);
   if (!ContextOr)
     return ContextOr.takeError();
-  const CompilerDeclContext &ContextPtr =
-      ContextOr->IsValid() ? *ContextOr : CompilerDeclContext();
 
+  TypeMatch match;
   LanguageSet languages;
   if (!Language.empty())
-    languages.Insert(Language::GetLanguageTypeFromString(Language));
-
-  DenseSet<SymbolFile *> SearchedFiles;
-  TypeMap Map;
-  if (!Name.empty())
-    Symfile.FindTypes(ConstString(Name), ContextPtr, UINT32_MAX, SearchedFiles,
-                      Map);
-  else
-    Module.FindTypes(parseCompilerContext(), languages, SearchedFiles, Map);
+    match.AddLanguage(Language::GetLanguageTypeFromString(Language));
 
+  if (!Name.empty()) {
+    if (ContextOr->IsValid()) {
+      match.SetMatchContext(*ContextOr, ConstString(Name));
+      match.SetModuleSearch(true);
+    } else {
+      match.SetMatchContext(Name, /*exact_match=*/false);
+    }
+  } else {
+    match.GetContextRef() = parseCompilerContext();
+    match.SetModuleSearch(true);
+  }
+  Symfile.FindTypes(match);
+  const TypeMap &Map = match.GetTypeMap();
   outs() << formatv("Found {0} types:\n", Map.GetSize());
   StreamString Stream;
   // Resolve types to force-materialize typedef types.
-  Map.ForEach([&](TypeSP &type) {
-    type->GetFullCompilerType();
-    return false;
-  });
-  Map.Dump(&Stream, false, GetDescriptionLevel());
+  for (const auto &type_sp: match.GetTypeMap().Types())
+    type_sp->GetFullCompilerType();
+  match.GetTypeMap().Dump(&Stream, false, GetDescriptionLevel());
   outs() << Stream.GetData() << "\n";
   return Error::success();
 }
 
 Error opts::symbols::findVariables(lldb_private::Module &Module) {
   SymbolFile &Symfile = *Module.GetSymbolFile();
   VariableList List;
   if (Regex) {