[thirdparty/binutils-gdb.git] / gdb / dwarf2 / cooked-index.c

/* DIE indexing 

   Copyright (C) 2022-2023 Free Software Foundation, Inc.

   This file is part of GDB.

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */

#include "defs.h"
#include "dwarf2/cooked-index.h"
#include "dwarf2/read.h"
#include "cp-support.h"
#include "c-lang.h"
#include "ada-lang.h"
#include "split-name.h"
#include <algorithm>
#include "safe-ctype.h"
#include "gdbsupport/selftest.h"

/* See cooked-index.h.  */

bool
cooked_index_entry::compare (const char *stra, const char *strb,
			     bool completing)
{
  /* If we've ever matched "<" in both strings, then we disable the
     special template parameter handling.  */
  bool seen_lt = false;

  while (*stra != '\0'
	 && *strb != '\0'
	 && (TOLOWER ((unsigned char) *stra)
	     == TOLOWER ((unsigned char ) *strb)))
    {
      if (*stra == '<')
	seen_lt = true;
      ++stra;
      ++strb;
    }

  unsigned c1 = TOLOWER ((unsigned char) *stra);
  unsigned c2 = TOLOWER ((unsigned char) *strb);

  if (completing)
    {
      /* When completing, if one string ends earlier than the other,
	 consider them as equal.  Also, completion mode ignores the
	 special '<' handling.  */
      if (c1 == '\0' || c2 == '\0')
	return false;
      /* Fall through to the generic case.  */
    }
  else if (seen_lt)
    {
      /* Fall through to the generic case.  */
    }
  else if (c1 == '\0' || c1 == '<')
    {
      /* Maybe they both end at the same spot.  */
      if (c2 == '\0' || c2 == '<')
	return false;
      /* First string ended earlier.  */
      return true;
    }
  else if (c2 == '\0' || c2 == '<')
    {
      /* Second string ended earlier.  */
      return false;
    }

  return c1 < c2;
}

#if GDB_SELF_TEST

namespace {

void
test_compare ()
{
  SELF_CHECK (!cooked_index_entry::compare ("abcd", "abcd", false));
  SELF_CHECK (!cooked_index_entry::compare ("abcd", "abcd", false));
  SELF_CHECK (!cooked_index_entry::compare ("abcd", "abcd", true));
  SELF_CHECK (!cooked_index_entry::compare ("abcd", "abcd", true));

  SELF_CHECK (cooked_index_entry::compare ("abcd", "ABCDE", false));
  SELF_CHECK (!cooked_index_entry::compare ("ABCDE", "abcd", false));
  SELF_CHECK (!cooked_index_entry::compare ("abcd", "ABCDE", true));
  SELF_CHECK (!cooked_index_entry::compare ("ABCDE", "abcd", true));

  SELF_CHECK (!cooked_index_entry::compare ("name", "name<>", false));
  SELF_CHECK (!cooked_index_entry::compare ("name<>", "name", false));
  SELF_CHECK (!cooked_index_entry::compare ("name", "name<>", true));
  SELF_CHECK (!cooked_index_entry::compare ("name<>", "name", true));

  SELF_CHECK (!cooked_index_entry::compare ("name<arg>", "name<arg>", false));
  SELF_CHECK (!cooked_index_entry::compare ("name<arg>", "name<arg>", false));
  SELF_CHECK (!cooked_index_entry::compare ("name<arg>", "name<arg>", true));
  SELF_CHECK (!cooked_index_entry::compare ("name<arg>", "name<ag>", true));

  SELF_CHECK (!cooked_index_entry::compare ("name<arg<more>>",
					    "name<arg<more>>", false));

  SELF_CHECK (!cooked_index_entry::compare ("name", "name<arg<more>>", false));
  SELF_CHECK (!cooked_index_entry::compare ("name<arg<more>>", "name", false));
  SELF_CHECK (cooked_index_entry::compare ("name<arg<", "name<arg<more>>",
					   false));
  SELF_CHECK (!cooked_index_entry::compare ("name<arg<",
					    "name<arg<more>>",
					    true));
  SELF_CHECK (!cooked_index_entry::compare ("name<arg<more>>", "name<arg<",
					    false));
  SELF_CHECK (!cooked_index_entry::compare ("name<arg<more>>", "name<arg<",
					    true));

  SELF_CHECK (cooked_index_entry::compare ("", "abcd", false));
  SELF_CHECK (!cooked_index_entry::compare ("", "abcd", true));
  SELF_CHECK (!cooked_index_entry::compare ("abcd", "", false));
  SELF_CHECK (!cooked_index_entry::compare ("abcd", "", true));
}

} /* anonymous namespace */

#endif /* GDB_SELF_TEST */

/* See cooked-index.h.  */

const char *
cooked_index_entry::full_name (struct obstack *storage) const
{
  if ((flags & IS_LINKAGE) != 0 || parent_entry == nullptr)
    return canonical;

  const char *sep = nullptr;
  switch (per_cu->lang ())
    {
    case language_cplus:
    case language_rust:
      sep = "::";
      break;

    case language_go:
    case language_d:
    case language_ada:
      sep = ".";
      break;

    default:
      return canonical;
    }

  parent_entry->write_scope (storage, sep);
  obstack_grow0 (storage, canonical, strlen (canonical));
  return (const char *) obstack_finish (storage);
}

/* See cooked-index.h.  */

void
cooked_index_entry::write_scope (struct obstack *storage,
				 const char *sep) const
{
  if (parent_entry != nullptr)
    parent_entry->write_scope (storage, sep);
  obstack_grow (storage, canonical, strlen (canonical));
  obstack_grow (storage, sep, strlen (sep));
}

/* See cooked-index.h.  */

const cooked_index_entry *
cooked_index::add (sect_offset die_offset, enum dwarf_tag tag,
		   cooked_index_flag flags, const char *name,
		   const cooked_index_entry *parent_entry,
		   dwarf2_per_cu_data *per_cu)
{
  cooked_index_entry *result = create (die_offset, tag, flags, name,
				       parent_entry, per_cu);
  m_entries.push_back (result);

  /* An explicitly-tagged main program should always override the
     implicit "main" discovery.  */
  if ((flags & IS_MAIN) != 0)
    m_main = result;
  else if (per_cu->lang () != language_ada
	   && m_main == nullptr
	   && strcmp (name, "main") == 0)
    m_main = result;

  return result;
}

/* See cooked-index.h.  */

void
cooked_index::finalize ()
{
  m_future = gdb::thread_pool::g_thread_pool->post_task ([this] ()
    {
      do_finalize ();
    });
}

/* See cooked-index.h.  */

gdb::unique_xmalloc_ptr<char>
cooked_index::handle_gnat_encoded_entry (cooked_index_entry *entry,
					 htab_t gnat_entries)
{
  std::string canonical = ada_decode (entry->name, false, false);
  if (canonical.empty ())
    return {};
  std::vector<gdb::string_view> names = split_name (canonical.c_str (),
						    split_style::DOT);
  gdb::string_view tail = names.back ();
  names.pop_back ();

  const cooked_index_entry *parent = nullptr;
  for (const auto &name : names)
    {
      uint32_t hashval = dwarf5_djb_hash (name);
      void **slot = htab_find_slot_with_hash (gnat_entries, &name,
					      hashval, INSERT);
      /* CUs are processed in order, so we only need to check the most
	 recent entry.  */
      cooked_index_entry *last = (cooked_index_entry *) *slot;
      if (last == nullptr || last->per_cu != entry->per_cu)
	{
	  gdb::unique_xmalloc_ptr<char> new_name
	    = make_unique_xstrndup (name.data (), name.length ());
	  last = create (entry->die_offset, DW_TAG_namespace,
			 0, new_name.get (), parent,
			 entry->per_cu);
	  last->canonical = last->name;
	  m_names.push_back (std::move (new_name));
	  *slot = last;
	}

      parent = last;
    }

  entry->parent_entry = parent;
  return make_unique_xstrndup (tail.data (), tail.length ());
}

/* See cooked-index.h.  */

void
cooked_index::do_finalize ()
{
  auto hash_name_ptr = [] (const void *p)
    {
      const cooked_index_entry *entry = (const cooked_index_entry *) p;
      return htab_hash_pointer (entry->name);
    };

  auto eq_name_ptr = [] (const void *a, const void *b) -> int
    {
      const cooked_index_entry *ea = (const cooked_index_entry *) a;
      const cooked_index_entry *eb = (const cooked_index_entry *) b;
      return ea->name == eb->name;
    };

  /* We can use pointer equality here because names come from
     .debug_str, which will normally be unique-ified by the linker.
     Also, duplicates are relatively harmless -- they just mean a bit
     of extra memory is used.  */
  htab_up seen_names (htab_create_alloc (10, hash_name_ptr, eq_name_ptr,
					 nullptr, xcalloc, xfree));

  auto hash_entry = [] (const void *e)
    {
      const cooked_index_entry *entry = (const cooked_index_entry *) e;
      return dwarf5_djb_hash (entry->canonical);
    };

  auto eq_entry = [] (const void *a, const void *b) -> int
    {
      const cooked_index_entry *ae = (const cooked_index_entry *) a;
      const gdb::string_view *sv = (const gdb::string_view *) b;
      return (strlen (ae->canonical) == sv->length ()
	      && strncasecmp (ae->canonical, sv->data (), sv->length ()) == 0);
    };

  htab_up gnat_entries (htab_create_alloc (10, hash_entry, eq_entry,
					   nullptr, xcalloc, xfree));

  for (cooked_index_entry *entry : m_entries)
    {
      gdb_assert (entry->canonical == nullptr);
      if ((entry->flags & IS_LINKAGE) != 0)
	entry->canonical = entry->name;
      else if (entry->per_cu->lang () == language_ada)
	{
	  gdb::unique_xmalloc_ptr<char> canon_name
	    = handle_gnat_encoded_entry (entry, gnat_entries.get ());
	  if (canon_name == nullptr)
	    entry->canonical = entry->name;
	  else
	    {
	      entry->canonical = canon_name.get ();
	      m_names.push_back (std::move (canon_name));
	    }
	}
      else if (entry->per_cu->lang () == language_cplus
	       || entry->per_cu->lang () == language_c)
	{
	  void **slot = htab_find_slot (seen_names.get (), entry,
					INSERT);
	  if (*slot == nullptr)
	    {
	      gdb::unique_xmalloc_ptr<char> canon_name
		= (entry->per_cu->lang () == language_cplus
		   ? cp_canonicalize_string (entry->name)
		   : c_canonicalize_name (entry->name));
	      if (canon_name == nullptr)
		entry->canonical = entry->name;
	      else
		{
		  entry->canonical = canon_name.get ();
		  m_names.push_back (std::move (canon_name));
		}
	    }
	  else
	    {
	      const cooked_index_entry *other
		= (const cooked_index_entry *) *slot;
	      entry->canonical = other->canonical;
	    }
	}
      else
	entry->canonical = entry->name;
    }

  m_names.shrink_to_fit ();
  m_entries.shrink_to_fit ();
  std::sort (m_entries.begin (), m_entries.end (),
	     [] (const cooked_index_entry *a, const cooked_index_entry *b)
	     {
	       return *a < *b;
	     });
}

/* See cooked-index.h.  */

cooked_index::range
cooked_index::find (const std::string &name, bool completing) const
{
  wait ();

  auto lower = std::lower_bound (m_entries.cbegin (), m_entries.cend (), name,
				 [=] (const cooked_index_entry *entry,
				      const std::string &n)
  {
    return cooked_index_entry::compare (entry->canonical, n.c_str (),
					completing);
  });

  auto upper = std::upper_bound (m_entries.cbegin (), m_entries.cend (), name,
				 [=] (const std::string &n,
				      const cooked_index_entry *entry)
  {
    return cooked_index_entry::compare (n.c_str (), entry->canonical,
					completing);
  });

  return range (lower, upper);
}

cooked_index_vector::cooked_index_vector (vec_type &&vec)
  : m_vector (std::move (vec))
{
  for (auto &idx : m_vector)
    idx->finalize ();
}

/* See cooked-index.h.  */

dwarf2_per_cu_data *
cooked_index_vector::lookup (CORE_ADDR addr)
{
  for (const auto &index : m_vector)
    {
      dwarf2_per_cu_data *result = index->lookup (addr);
      if (result != nullptr)
	return result;
    }
  return nullptr;
}

/* See cooked-index.h.  */

std::vector<addrmap *>
cooked_index_vector::get_addrmaps ()
{
  std::vector<addrmap *> result;
  for (const auto &index : m_vector)
    result.push_back (index->m_addrmap);
  return result;
}

/* See cooked-index.h.  */

cooked_index_vector::range
cooked_index_vector::find (const std::string &name, bool completing) const
{
  std::vector<cooked_index::range> result_range;
  result_range.reserve (m_vector.size ());
  for (auto &entry : m_vector)
    result_range.push_back (entry->find (name, completing));
  return range (std::move (result_range));
}

/* See cooked-index.h.  */

const cooked_index_entry *
cooked_index_vector::get_main () const
{
  const cooked_index_entry *result = nullptr;

  for (const auto &index : m_vector)
    {
      const cooked_index_entry *entry = index->get_main ();
      if (result == nullptr
	  || ((result->flags & IS_MAIN) == 0
	      && entry != nullptr
	      && (entry->flags & IS_MAIN) != 0))
	result = entry;
    }

  return result;
}

void _initialize_cooked_index ();
void
_initialize_cooked_index ()
{
#if GDB_SELF_TEST
  selftests::register_test ("cooked_index_entry::compare", test_compare);
#endif
}
Commit	Line	Data
51f5a4b8 TT	1	/* DIE indexing
51f5a4b8 TT	2
213516ef	3	Copyright (C) 2022-2023 Free Software Foundation, Inc.
51f5a4b8 TT	4
	5	This file is part of GDB.
	6
	7	This program is free software; you can redistribute it and/or modify
	8	it under the terms of the GNU General Public License as published by
	9	the Free Software Foundation; either version 3 of the License, or
	10	(at your option) any later version.
	11
	12	This program is distributed in the hope that it will be useful,
	13	but WITHOUT ANY WARRANTY; without even the implied warranty of
	14	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	15	GNU General Public License for more details.
	16
	17	You should have received a copy of the GNU General Public License
	18	along with this program. If not, see <http://www.gnu.org/licenses/>. */
	19
	20	#include "defs.h"
	21	#include "dwarf2/cooked-index.h"
	22	#include "dwarf2/read.h"
	23	#include "cp-support.h"
55fc1623	24	#include "c-lang.h"
51f5a4b8 TT	25	#include "ada-lang.h"
	26	#include "split-name.h"
	27	#include <algorithm>
ac37b79c TT	28	#include "safe-ctype.h"
	29	#include "gdbsupport/selftest.h"
	30
	31	/* See cooked-index.h. */
	32
	33	bool
	34	cooked_index_entry::compare (const char stra, const char strb,
	35	bool completing)
	36	{
	37	/* If we've ever matched "<" in both strings, then we disable the
	38	special template parameter handling. */
	39	bool seen_lt = false;
	40
	41	while (*stra != '\0'
	42	&& *strb != '\0'
	43	&& (TOLOWER ((unsigned char) *stra)
	44	== TOLOWER ((unsigned char ) *strb)))
	45	{
	46	if (*stra == '<')
	47	seen_lt = true;
	48	++stra;
	49	++strb;
	50	}
	51
	52	unsigned c1 = TOLOWER ((unsigned char) *stra);
	53	unsigned c2 = TOLOWER ((unsigned char) *strb);
	54
	55	if (completing)
	56	{
	57	/* When completing, if one string ends earlier than the other,
	58	consider them as equal. Also, completion mode ignores the
	59	special '<' handling. */
	60	if (c1 == '\0' \|\| c2 == '\0')
	61	return false;
	62	/* Fall through to the generic case. */
	63	}
	64	else if (seen_lt)
	65	{
	66	/* Fall through to the generic case. */
	67	}
	68	else if (c1 == '\0' \|\| c1 == '<')
	69	{
	70	/* Maybe they both end at the same spot. */
	71	if (c2 == '\0' \|\| c2 == '<')
	72	return false;
	73	/* First string ended earlier. */
	74	return true;
	75	}
	76	else if (c2 == '\0' \|\| c2 == '<')
	77	{
	78	/* Second string ended earlier. */
	79	return false;
	80	}
	81
	82	return c1 < c2;
	83	}
	84
	85	#if GDB_SELF_TEST
	86
	87	namespace {
	88
	89	void
	90	test_compare ()
	91	{
92	SELF_CHECK (!cooked_index_entry::compare ("abcd", "abcd", false));
93	SELF_CHECK (!cooked_index_entry::compare ("abcd", "abcd", false));
94	SELF_CHECK (!cooked_index_entry::compare ("abcd", "abcd", true));
95	SELF_CHECK (!cooked_index_entry::compare ("abcd", "abcd", true));
96
97	SELF_CHECK (cooked_index_entry::compare ("abcd", "ABCDE", false));
98	SELF_CHECK (!cooked_index_entry::compare ("ABCDE", "abcd", false));
99	SELF_CHECK (!cooked_index_entry::compare ("abcd", "ABCDE", true));
100	SELF_CHECK (!cooked_index_entry::compare ("ABCDE", "abcd", true));
101
102	SELF_CHECK (!cooked_index_entry::compare ("name", "name<>", false));
103	SELF_CHECK (!cooked_index_entry::compare ("name<>", "name", false));
104	SELF_CHECK (!cooked_index_entry::compare ("name", "name<>", true));
105	SELF_CHECK (!cooked_index_entry::compare ("name<>", "name", true));
106
107	SELF_CHECK (!cooked_index_entry::compare ("name<arg>", "name<arg>", false));
108	SELF_CHECK (!cooked_index_entry::compare ("name<arg>", "name<arg>", false));
109	SELF_CHECK (!cooked_index_entry::compare ("name<arg>", "name<arg>", true));
110	SELF_CHECK (!cooked_index_entry::compare ("name<arg>", "name<ag>", true));
111
112	SELF_CHECK (!cooked_index_entry::compare ("name<arg<more>>",
113	"name<arg<more>>", false));
114
115	SELF_CHECK (!cooked_index_entry::compare ("name", "name<arg<more>>", false));
116	SELF_CHECK (!cooked_index_entry::compare ("name<arg<more>>", "name", false));
117	SELF_CHECK (cooked_index_entry::compare ("name<arg<", "name<arg<more>>",
118	false));
119	SELF_CHECK (!cooked_index_entry::compare ("name<arg<",
120	"name<arg<more>>",
121	true));
122	SELF_CHECK (!cooked_index_entry::compare ("name<arg<more>>", "name<arg<",
123	false));
124	SELF_CHECK (!cooked_index_entry::compare ("name<arg<more>>", "name<arg<",
125	true));
126
127	SELF_CHECK (cooked_index_entry::compare ("", "abcd", false));
128	SELF_CHECK (!cooked_index_entry::compare ("", "abcd", true));
129	SELF_CHECK (!cooked_index_entry::compare ("abcd", "", false));
130	SELF_CHECK (!cooked_index_entry::compare ("abcd", "", true));
131	}
132
133	} /* anonymous namespace */
134
135	#endif /* GDB_SELF_TEST */
51f5a4b8	136
51f5a4b8 TT	137	/* See cooked-index.h. */
	138
	139	const char *
	140	cooked_index_entry::full_name (struct obstack *storage) const
	141	{
72b580b8	142	if ((flags & IS_LINKAGE) != 0 \|\| parent_entry == nullptr)
51f5a4b8 TT	143	return canonical;
	144
	145	const char *sep = nullptr;
2c474c46	146	switch (per_cu->lang ())
51f5a4b8 TT	147	{
	148	case language_cplus:
	149	case language_rust:
	150	sep = "::";
	151	break;
	152
	153	case language_go:
	154	case language_d:
	155	case language_ada:
	156	sep = ".";
	157	break;
51f5a4b8	158
72b580b8 TT	159	default:
	160	return canonical;
	161	}
51f5a4b8	162
72b580b8	163	parent_entry->write_scope (storage, sep);
51f5a4b8 TT	164	obstack_grow0 (storage, canonical, strlen (canonical));
	165	return (const char *) obstack_finish (storage);
	166	}
	167
	168	/* See cooked-index.h. */
	169
	170	void
	171	cooked_index_entry::write_scope (struct obstack *storage,
	172	const char *sep) const
	173	{
	174	if (parent_entry != nullptr)
	175	parent_entry->write_scope (storage, sep);
	176	obstack_grow (storage, canonical, strlen (canonical));
	177	obstack_grow (storage, sep, strlen (sep));
	178	}
	179
	180	/* See cooked-index.h. */
	181
	182	const cooked_index_entry *
	183	cooked_index::add (sect_offset die_offset, enum dwarf_tag tag,
	184	cooked_index_flag flags, const char *name,
	185	const cooked_index_entry *parent_entry,
	186	dwarf2_per_cu_data *per_cu)
	187	{
	188	cooked_index_entry *result = create (die_offset, tag, flags, name,
	189	parent_entry, per_cu);
	190	m_entries.push_back (result);
	191
	192	/* An explicitly-tagged main program should always override the
	193	implicit "main" discovery. */
	194	if ((flags & IS_MAIN) != 0)
	195	m_main = result;
2c474c46	196	else if (per_cu->lang () != language_ada
51f5a4b8 TT	197	&& m_main == nullptr
	198	&& strcmp (name, "main") == 0)
	199	m_main = result;
	200
	201	return result;
	202	}
	203
46114cb7 TT	204	/* See cooked-index.h. */
46114cb7 TT	205
20a26f4e TT	206	void
20a26f4e TT	207	cooked_index::finalize ()
46114cb7	208	{
20a26f4e	209	m_future = gdb::thread_pool::g_thread_pool->post_task ([this] ()
46114cb7	210	{
20a26f4e TT	211	do_finalize ();
20a26f4e TT	212	});
51f5a4b8 TT	213	}
	214
	215	/* See cooked-index.h. */
	216
	217	gdb::unique_xmalloc_ptr<char>
20a26f4e TT	218	cooked_index::handle_gnat_encoded_entry (cooked_index_entry *entry,
20a26f4e TT	219	htab_t gnat_entries)
51f5a4b8 TT	220	{
	221	std::string canonical = ada_decode (entry->name, false, false);
	222	if (canonical.empty ())
	223	return {};
	224	std::vector<gdb::string_view> names = split_name (canonical.c_str (),
	225	split_style::DOT);
	226	gdb::string_view tail = names.back ();
	227	names.pop_back ();
	228
	229	const cooked_index_entry *parent = nullptr;
	230	for (const auto &name : names)
	231	{
	232	uint32_t hashval = dwarf5_djb_hash (name);
	233	void **slot = htab_find_slot_with_hash (gnat_entries, &name,
	234	hashval, INSERT);
	235	/* CUs are processed in order, so we only need to check the most
	236	recent entry. */
	237	cooked_index_entry last = (cooked_index_entry ) *slot;
	238	if (last == nullptr \|\| last->per_cu != entry->per_cu)
	239	{
	240	gdb::unique_xmalloc_ptr<char> new_name
	241	= make_unique_xstrndup (name.data (), name.length ());
20a26f4e TT	242	last = create (entry->die_offset, DW_TAG_namespace,
	243	0, new_name.get (), parent,
	244	entry->per_cu);
51f5a4b8 TT	245	last->canonical = last->name;
	246	m_names.push_back (std::move (new_name));
	247	*slot = last;
	248	}
	249
	250	parent = last;
	251	}
	252
	253	entry->parent_entry = parent;
	254	return make_unique_xstrndup (tail.data (), tail.length ());
	255	}
	256
	257	/* See cooked-index.h. */
	258
	259	void
20a26f4e	260	cooked_index::do_finalize ()
51f5a4b8 TT	261	{
	262	auto hash_name_ptr = [] (const void *p)
	263	{
	264	const cooked_index_entry entry = (const cooked_index_entry ) p;
	265	return htab_hash_pointer (entry->name);
	266	};
	267
	268	auto eq_name_ptr = [] (const void a, const void b) -> int
	269	{
	270	const cooked_index_entry ea = (const cooked_index_entry ) a;
	271	const cooked_index_entry eb = (const cooked_index_entry ) b;
	272	return ea->name == eb->name;
	273	};
	274
	275	/* We can use pointer equality here because names come from
	276	.debug_str, which will normally be unique-ified by the linker.
	277	Also, duplicates are relatively harmless -- they just mean a bit
	278	of extra memory is used. */
	279	htab_up seen_names (htab_create_alloc (10, hash_name_ptr, eq_name_ptr,
	280	nullptr, xcalloc, xfree));
	281
5a89072f TT	282	auto hash_entry = [] (const void *e)
	283	{
	284	const cooked_index_entry entry = (const cooked_index_entry ) e;
	285	return dwarf5_djb_hash (entry->canonical);
	286	};
	287
	288	auto eq_entry = [] (const void a, const void b) -> int
	289	{
	290	const cooked_index_entry ae = (const cooked_index_entry ) a;
	291	const gdb::string_view sv = (const gdb::string_view ) b;
	292	return (strlen (ae->canonical) == sv->length ()
	293	&& strncasecmp (ae->canonical, sv->data (), sv->length ()) == 0);
	294	};
	295
20a26f4e TT	296	htab_up gnat_entries (htab_create_alloc (10, hash_entry, eq_entry,
20a26f4e TT	297	nullptr, xcalloc, xfree));
46114cb7	298
20a26f4e TT	299	for (cooked_index_entry *entry : m_entries)
	300	{
	301	gdb_assert (entry->canonical == nullptr);
bed34ce7	302	if ((entry->flags & IS_LINKAGE) != 0)
20a26f4e	303	entry->canonical = entry->name;
bed34ce7	304	else if (entry->per_cu->lang () == language_ada)
51f5a4b8	305	{
bed34ce7 TT	306	gdb::unique_xmalloc_ptr<char> canon_name
	307	= handle_gnat_encoded_entry (entry, gnat_entries.get ());
	308	if (canon_name == nullptr)
	309	entry->canonical = entry->name;
	310	else
	311	{
	312	entry->canonical = canon_name.get ();
	313	m_names.push_back (std::move (canon_name));
	314	}
	315	}
55fc1623 TT	316	else if (entry->per_cu->lang () == language_cplus
55fc1623 TT	317	\|\| entry->per_cu->lang () == language_c)
bed34ce7 TT	318	{
	319	void **slot = htab_find_slot (seen_names.get (), entry,
	320	INSERT);
	321	if (*slot == nullptr)
20a26f4e TT	322	{
20a26f4e TT	323	gdb::unique_xmalloc_ptr<char> canon_name
55fc1623 TT	324	= (entry->per_cu->lang () == language_cplus
	325	? cp_canonicalize_string (entry->name)
	326	: c_canonicalize_name (entry->name));
20a26f4e TT	327	if (canon_name == nullptr)
	328	entry->canonical = entry->name;
	329	else
	330	{
	331	entry->canonical = canon_name.get ();
	332	m_names.push_back (std::move (canon_name));
	333	}
	334	}
51f5a4b8 TT	335	else
51f5a4b8 TT	336	{
bed34ce7 TT	337	const cooked_index_entry *other
	338	= (const cooked_index_entry ) slot;
	339	entry->canonical = other->canonical;
51f5a4b8 TT	340	}
51f5a4b8 TT	341	}
bed34ce7 TT	342	else
bed34ce7 TT	343	entry->canonical = entry->name;
51f5a4b8 TT	344	}
	345
	346	m_names.shrink_to_fit ();
	347	m_entries.shrink_to_fit ();
	348	std::sort (m_entries.begin (), m_entries.end (),
	349	[] (const cooked_index_entry a, const cooked_index_entry b)
	350	{
	351	return a < b;
	352	});
	353	}
20a26f4e TT	354
	355	/* See cooked-index.h. */
	356
	357	cooked_index::range
35e17631	358	cooked_index::find (const std::string &name, bool completing) const
20a26f4e TT	359	{
	360	wait ();
	361
35e17631	362	auto lower = std::lower_bound (m_entries.cbegin (), m_entries.cend (), name,
20a26f4e	363	[=] (const cooked_index_entry *entry,
ac37b79c	364	const std::string &n)
20a26f4e	365	{
ac37b79c TT	366	return cooked_index_entry::compare (entry->canonical, n.c_str (),
ac37b79c TT	367	completing);
20a26f4e TT	368	});
20a26f4e TT	369
35e17631	370	auto upper = std::upper_bound (m_entries.cbegin (), m_entries.cend (), name,
ac37b79c	371	[=] (const std::string &n,
20a26f4e TT	372	const cooked_index_entry *entry)
20a26f4e TT	373	{
ac37b79c TT	374	return cooked_index_entry::compare (n.c_str (), entry->canonical,
ac37b79c TT	375	completing);
20a26f4e TT	376	});
	377
	378	return range (lower, upper);
	379	}
	380
	381	cooked_index_vector::cooked_index_vector (vec_type &&vec)
	382	: m_vector (std::move (vec))
	383	{
	384	for (auto &idx : m_vector)
	385	idx->finalize ();
	386	}
	387
	388	/* See cooked-index.h. */
	389
	390	dwarf2_per_cu_data *
	391	cooked_index_vector::lookup (CORE_ADDR addr)
	392	{
	393	for (const auto &index : m_vector)
	394	{
	395	dwarf2_per_cu_data *result = index->lookup (addr);
	396	if (result != nullptr)
	397	return result;
	398	}
	399	return nullptr;
	400	}
	401
	402	/* See cooked-index.h. */
	403
	404	std::vector<addrmap *>
	405	cooked_index_vector::get_addrmaps ()
	406	{
	407	std::vector<addrmap *> result;
	408	for (const auto &index : m_vector)
	409	result.push_back (index->m_addrmap);
	410	return result;
	411	}
	412
	413	/* See cooked-index.h. */
	414
	415	cooked_index_vector::range
35e17631	416	cooked_index_vector::find (const std::string &name, bool completing) const
20a26f4e TT	417	{
	418	std::vector<cooked_index::range> result_range;
	419	result_range.reserve (m_vector.size ());
	420	for (auto &entry : m_vector)
	421	result_range.push_back (entry->find (name, completing));
	422	return range (std::move (result_range));
	423	}
	424
	425	/* See cooked-index.h. */
	426
	427	const cooked_index_entry *
	428	cooked_index_vector::get_main () const
	429	{
	430	const cooked_index_entry *result = nullptr;
	431
	432	for (const auto &index : m_vector)
	433	{
	434	const cooked_index_entry *entry = index->get_main ();
	435	if (result == nullptr
	436	\|\| ((result->flags & IS_MAIN) == 0
	437	&& entry != nullptr
	438	&& (entry->flags & IS_MAIN) != 0))
	439	result = entry;
	440	}
	441
	442	return result;
	443	}
ac37b79c TT	444
	445	void _initialize_cooked_index ();
	446	void
	447	_initialize_cooked_index ()
	448	{
	449	#if GDB_SELF_TEST
	450	selftests::register_test ("cooked_index_entry::compare", test_compare);
	451	#endif
	452	}