[PATCH Rust front-end v4 26/46] gccrs: Add helpers mappings canonical path and lang items

[arthur.cohen@embecosm.com]

From: Philip Herron <philip.herron@embecosm.com>

These are various helper classes used in the compiler pipeline.
---
 gcc/rust/util/rust-canonical-path.h   | 195 +++++
 gcc/rust/util/rust-common.h           |  53 ++
 gcc/rust/util/rust-hir-map.cc         | 980 ++++++++++++++++++++++++++
 gcc/rust/util/rust-hir-map.h          | 356 ++++++++++
 gcc/rust/util/rust-identifier.h       |  49 ++
 gcc/rust/util/rust-lang-item.h        | 377 ++++++++++
 gcc/rust/util/rust-mapping-common.h   |  85 +++
 gcc/rust/util/rust-stacked-contexts.h |  86 +++
 8 files changed, 2181 insertions(+)
 create mode 100644 gcc/rust/util/rust-canonical-path.h
 create mode 100644 gcc/rust/util/rust-common.h
 create mode 100644 gcc/rust/util/rust-hir-map.cc
 create mode 100644 gcc/rust/util/rust-hir-map.h
 create mode 100644 gcc/rust/util/rust-identifier.h
 create mode 100644 gcc/rust/util/rust-lang-item.h
 create mode 100644 gcc/rust/util/rust-mapping-common.h
 create mode 100644 gcc/rust/util/rust-stacked-contexts.h

diff --git a/gcc/rust/util/rust-canonical-path.h b/gcc/rust/util/rust-canonical-path.h
new file mode 100644
index 00000000000..54cc0390849
--- /dev/null
+++ b/gcc/rust/util/rust-canonical-path.h
@@ -0,0 +1,195 @@
+// Copyright (C) 2020-2022 Free Software Foundation, Inc.
+
+// This file is part of GCC.
+
+// GCC 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, or (at your option) any later
+// version.
+
+// GCC 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 GCC; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#ifndef RUST_CANONICAL_PATH
+#define RUST_CANONICAL_PATH
+
+#include "rust-system.h"
+#include "rust-mapping-common.h"
+
+namespace Rust {
+namespace Resolver {
+
+// https://doc.rust-lang.org/reference/paths.html#canonical-paths
+//
+// struct X - path X
+// impl X { fn test - path X::test }
+//
+// struct X<T> - path X
+//
+// impl X<T>   { fn test - path X::test}
+// impl X<i32> { fn test - path X<i32>::test }
+// impl X<f32> { fn test - path X<f32>::test }
+//
+// pub trait Trait { // ::a::Trait
+//   fn f(&self); // ::a::Trait::f
+// }
+//
+// impl Trait for Struct {
+//    fn f(&self) {} // <::a::Struct as ::a::Trait>::f
+// }
+class CanonicalPath
+{
+public:
+  CanonicalPath (const CanonicalPath &other) : segs (other.segs) {}
+
+  CanonicalPath &operator= (const CanonicalPath &other)
+  {
+    segs = other.segs;
+    return *this;
+  }
+
+  static CanonicalPath new_seg (NodeId id, const std::string &path)
+  {
+    rust_assert (!path.empty ());
+    return CanonicalPath ({std::pair<NodeId, std::string> (id, path)},
+			  UNKNOWN_CREATENUM);
+  }
+
+  static CanonicalPath
+  trait_impl_projection_seg (NodeId id, const CanonicalPath &trait_seg,
+			     const CanonicalPath &impl_type_seg)
+  {
+    return CanonicalPath::new_seg (id, "<" + impl_type_seg.get () + " as "
+					 + trait_seg.get () + ">");
+  }
+
+  std::string get () const
+  {
+    std::string buf;
+    for (size_t i = 0; i < segs.size (); i++)
+      {
+	bool have_more = (i + 1) < segs.size ();
+	const std::string &seg = segs.at (i).second;
+	buf += seg + (have_more ? "::" : "");
+      }
+    return buf;
+  }
+
+  static CanonicalPath get_big_self (NodeId id)
+  {
+    return CanonicalPath::new_seg (id, "Self");
+  }
+
+  static CanonicalPath create_empty ()
+  {
+    return CanonicalPath ({}, UNKNOWN_CREATENUM);
+  }
+
+  bool is_empty () const { return segs.size () == 0; }
+
+  CanonicalPath append (const CanonicalPath &other) const
+  {
+    rust_assert (!other.is_empty ());
+    if (is_empty ())
+      return CanonicalPath (other.segs, crate_num);
+
+    std::vector<std::pair<NodeId, std::string>> copy (segs);
+    for (auto &s : other.segs)
+      copy.push_back (s);
+
+    return CanonicalPath (copy, crate_num);
+  }
+
+  // if we have the path A::B::C this will give a callback for each segment
+  // including the prefix, example:
+  //
+  // path:
+  //   A::B::C
+  //
+  // iterate:
+  //   A
+  //   A::B
+  //   A::B::C
+  void iterate (std::function<bool (const CanonicalPath &)> cb) const
+  {
+    std::vector<std::pair<NodeId, std::string>> buf;
+    for (auto &seg : segs)
+      {
+	buf.push_back (seg);
+	if (!cb (CanonicalPath (buf, crate_num)))
+	  return;
+      }
+  }
+
+  // if we have the path A::B::C this will give a callback for each segment
+  // example:
+  //
+  // path:
+  //   A::B::C
+  //
+  // iterate:
+  //   A
+  //      B
+  //         C
+  void iterate_segs (std::function<bool (const CanonicalPath &)> cb) const
+  {
+    for (auto &seg : segs)
+      {
+	std::vector<std::pair<NodeId, std::string>> buf;
+	buf.push_back ({seg.first, seg.second});
+	if (!cb (CanonicalPath (buf, crate_num)))
+	  return;
+      }
+  }
+
+  size_t size () const { return segs.size (); }
+
+  NodeId get_node_id () const
+  {
+    rust_assert (!segs.empty ());
+    return segs.back ().first;
+  }
+
+  const std::pair<NodeId, std::string> &get_seg_at (size_t index) const
+  {
+    rust_assert (index < size ());
+    return segs.at (index);
+  }
+
+  bool is_equal (const CanonicalPath &b) const
+  {
+    return get ().compare (b.get ()) == 0;
+  }
+
+  void set_crate_num (CrateNum n) { crate_num = n; }
+
+  CrateNum get_crate_num () const
+  {
+    rust_assert (crate_num != UNKNOWN_CREATENUM);
+    return crate_num;
+  }
+
+  bool operator== (const CanonicalPath &b) const { return is_equal (b); }
+
+  bool operator< (const CanonicalPath &b) const { return get () < b.get (); }
+
+private:
+  explicit CanonicalPath (std::vector<std::pair<NodeId, std::string>> path,
+			  CrateNum crate_num)
+    : segs (path), crate_num (crate_num)
+  {}
+
+  std::vector<std::pair<NodeId, std::string>> segs;
+  CrateNum crate_num;
+};
+
+} // namespace Resolver
+} // namespace Rust
+
+#endif // RUST_CANONICAL_PATH
diff --git a/gcc/rust/util/rust-common.h b/gcc/rust/util/rust-common.h
new file mode 100644
index 00000000000..a3f6fb07d8d
--- /dev/null
+++ b/gcc/rust/util/rust-common.h
@@ -0,0 +1,53 @@
+// Copyright (C) 2021-2022 Free Software Foundation, Inc.
+
+// This file is part of GCC.
+
+// GCC 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, or (at your option) any later
+// version.
+
+// GCC 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 GCC; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// Common definitions useful throughout the Rust frontend.
+
+#ifndef RUST_COMMON
+#define RUST_COMMON
+
+namespace Rust {
+
+enum Mutability
+{
+  Imm,
+  Mut
+};
+
+enum Unsafety
+{
+  Unsafe,
+  Normal
+};
+
+enum Polarity
+{
+  Positive,
+  Negative
+};
+
+enum AsyncConstStatus
+{
+  NONE,
+  CONST_FN,
+  ASYNC_FN
+};
+
+} // namespace Rust
+
+#endif // RUST_COMMON
diff --git a/gcc/rust/util/rust-hir-map.cc b/gcc/rust/util/rust-hir-map.cc
new file mode 100644
index 00000000000..8705fdcf381
--- /dev/null
+++ b/gcc/rust/util/rust-hir-map.cc
@@ -0,0 +1,980 @@
+// Copyright (C) 2020-2022 Free Software Foundation, Inc.
+
+// This file is part of GCC.
+
+// GCC 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, or (at your option) any later
+// version.
+
+// GCC 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 GCC; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include "rust-hir-map.h"
+#include "rust-ast-full.h"
+#include "rust-diagnostics.h"
+#include "rust-hir-full.h"
+#include "rust-macro-builtins.h"
+#include "rust-mapping-common.h"
+
+namespace Rust {
+namespace Analysis {
+
+NodeMapping
+NodeMapping::get_error ()
+{
+  return NodeMapping (UNKNOWN_CREATENUM, UNKNOWN_NODEID, UNKNOWN_HIRID,
+		      UNKNOWN_LOCAL_DEFID);
+}
+
+CrateNum
+NodeMapping::get_crate_num () const
+{
+  return crateNum;
+}
+
+NodeId
+NodeMapping::get_nodeid () const
+{
+  return nodeId;
+}
+
+HirId
+NodeMapping::get_hirid () const
+{
+  return hirId;
+}
+
+LocalDefId
+NodeMapping::get_local_defid () const
+{
+  return localDefId;
+}
+
+DefId
+NodeMapping::get_defid () const
+{
+  return get_defid (get_crate_num (), get_local_defid ());
+}
+
+DefId
+NodeMapping::get_defid (CrateNum crate_num, LocalDefId local_defid)
+{
+  return DefId{crate_num, local_defid};
+}
+
+std::string
+NodeMapping::as_string () const
+{
+  std::ostringstream ss;
+  ss << "["
+     << "C: " << get_crate_num ();
+  if (get_nodeid () != UNKNOWN_NODEID)
+    ss << " Nid: " << get_nodeid ();
+
+  if (get_hirid () != UNKNOWN_HIRID)
+    ss << " Hid: " << get_hirid ();
+
+  if (get_local_defid () != UNKNOWN_LOCAL_DEFID)
+    ss << " Lid: " << get_local_defid ();
+
+  ss << "]";
+  return ss.str ();
+}
+
+// Mappings Class now
+static const HirId kDefaultNodeIdBegin = 1;
+static const HirId kDefaultHirIdBegin = 1;
+static const HirId kDefaultCrateNumBegin = 0;
+
+Mappings::Mappings ()
+  : crateNumItr (kDefaultCrateNumBegin), currentCrateNum (UNKNOWN_CREATENUM),
+    hirIdIter (kDefaultHirIdBegin), nodeIdIter (kDefaultNodeIdBegin)
+{}
+
+Mappings::~Mappings () {}
+
+Mappings *
+Mappings::get ()
+{
+  static std::unique_ptr<Mappings> instance;
+  if (!instance)
+    instance = std::unique_ptr<Mappings> (new Mappings ());
+
+  return instance.get ();
+}
+
+CrateNum
+Mappings::get_next_crate_num (const std::string &name)
+{
+  auto id = crateNumItr;
+  crateNumItr++;
+  set_crate_name (id, name);
+  return id;
+}
+
+void
+Mappings::set_current_crate (CrateNum crateNum)
+{
+  currentCrateNum = crateNum;
+}
+
+CrateNum
+Mappings::get_current_crate () const
+{
+  return currentCrateNum;
+}
+
+bool
+Mappings::get_crate_name (CrateNum crate_num, std::string &name) const
+{
+  auto it = crate_names.find (crate_num);
+  if (it == crate_names.end ())
+    return false;
+
+  name.assign (it->second);
+  return true;
+}
+
+void
+Mappings::set_crate_name (CrateNum crate_num, const std::string &name)
+{
+  crate_names[crate_num] = name;
+}
+
+std::string
+Mappings::get_current_crate_name () const
+{
+  std::string name;
+  bool ok = get_crate_name (get_current_crate (), name);
+  rust_assert (ok);
+  return name;
+}
+
+bool
+Mappings::lookup_crate_name (const std::string &crate_name,
+			     CrateNum &resolved_crate_num) const
+{
+  for (const auto &it : crate_names)
+    {
+      if (it.second.compare (crate_name) == 0)
+	{
+	  resolved_crate_num = it.first;
+	  return true;
+	}
+    }
+  return false;
+}
+
+bool
+Mappings::crate_num_to_nodeid (const CrateNum &crate_num, NodeId &node_id) const
+{
+  auto it = ast_crate_mappings.find (crate_num);
+  if (it == ast_crate_mappings.end ())
+    return false;
+
+  node_id = it->second->get_node_id ();
+  return true;
+}
+
+bool
+Mappings::node_is_crate (NodeId node_id) const
+{
+  for (const auto &it : ast_crate_mappings)
+    {
+      NodeId crate_node_id = it.second->get_node_id ();
+      if (crate_node_id == node_id)
+	return true;
+    }
+  return false;
+}
+
+NodeId
+Mappings::get_next_node_id ()
+{
+  auto it = nodeIdIter;
+  nodeIdIter++;
+  return it;
+}
+
+HirId
+Mappings::get_next_hir_id (CrateNum crateNum)
+{
+  auto id = hirIdIter;
+  hirIdIter++;
+
+  auto it = hirNodesWithinCrate.find (crateNum);
+  if (it == hirNodesWithinCrate.end ())
+    {
+      hirNodesWithinCrate.insert ({crateNum, {}});
+    }
+
+  hirNodesWithinCrate[crateNum].insert (id);
+  return id;
+}
+
+LocalDefId
+Mappings::get_next_localdef_id (CrateNum crateNum)
+{
+  auto it = localIdIter.find (crateNum);
+  if (it == localIdIter.end ())
+    {
+      localIdIter.insert ({crateNum, 1});
+    }
+
+  it = localIdIter.find (crateNum);
+  rust_assert (it != localIdIter.end ());
+
+  LocalDefId id = it->second;
+  localIdIter[crateNum] = id + 1;
+  return id;
+}
+
+AST::Crate &
+Mappings::get_ast_crate (CrateNum crateNum)
+{
+  auto it = ast_crate_mappings.find (crateNum);
+  rust_assert (it != ast_crate_mappings.end ());
+  return *it->second;
+}
+
+AST::Crate &
+Mappings::get_ast_crate_by_node_id (NodeId id)
+{
+  auto i = crate_node_to_crate_num.find (id);
+  rust_assert (i != crate_node_to_crate_num.end ());
+
+  CrateNum crateNum = i->second;
+  auto it = ast_crate_mappings.find (crateNum);
+  rust_assert (it != ast_crate_mappings.end ());
+  return *it->second;
+}
+
+AST::Crate &
+Mappings::insert_ast_crate (std::unique_ptr<AST::Crate> &&crate,
+			    CrateNum crate_num)
+{
+  auto it = ast_crate_mappings.find (crate_num);
+  rust_assert (it == ast_crate_mappings.end ());
+
+  // store it
+  ast_crate_mappings.insert ({crate_num, crate.release ()});
+
+  // return the reference to it
+  it = ast_crate_mappings.find (crate_num);
+  rust_assert (it != ast_crate_mappings.end ());
+  return *it->second;
+}
+
+HIR::Crate &
+Mappings::get_hir_crate (CrateNum crateNum)
+{
+  auto it = hir_crate_mappings.find (crateNum);
+  rust_assert (it != hir_crate_mappings.end ());
+  return *it->second;
+}
+
+bool
+Mappings::is_local_hirid_crate (HirId crateNum)
+{
+  for (const auto &it : hir_crate_mappings)
+    {
+      const auto &crate = it.second;
+      if (crate->get_mappings ().get_hirid () == crateNum)
+	return true;
+    }
+  return false;
+}
+
+HIR::Crate &
+Mappings::insert_hir_crate (std::unique_ptr<HIR::Crate> &&crate)
+{
+  CrateNum crateNum = crate->get_mappings ().get_crate_num ();
+  auto it = hir_crate_mappings.find (crateNum);
+  rust_assert (it == hir_crate_mappings.end ());
+
+  insert_node_to_hir (crate->get_mappings ().get_nodeid (),
+		      crate->get_mappings ().get_hirid ());
+  hir_crate_mappings.insert ({crateNum, crate.release ()});
+
+  it = hir_crate_mappings.find (crateNum);
+  rust_assert (it != hir_crate_mappings.end ());
+  return *it->second;
+}
+
+void
+Mappings::insert_defid_mapping (DefId id, HIR::Item *item)
+{
+  CrateNum crate_num = id.crateNum;
+  LocalDefId local_def_id = id.localDefId;
+
+  rust_assert (lookup_defid (id) == nullptr);
+  rust_assert (lookup_local_defid (crate_num, local_def_id) == nullptr);
+
+  defIdMappings[id] = item;
+  insert_local_defid_mapping (crate_num, local_def_id, item);
+}
+
+HIR::Item *
+Mappings::lookup_defid (DefId id)
+{
+  auto it = defIdMappings.find (id);
+  if (it == defIdMappings.end ())
+    return nullptr;
+
+  return it->second;
+}
+
+void
+Mappings::insert_hir_item (HIR::Item *item)
+{
+  auto id = item->get_mappings ().get_hirid ();
+  rust_assert (lookup_hir_item (id) == nullptr);
+
+  hirItemMappings[id] = item;
+  insert_node_to_hir (item->get_mappings ().get_nodeid (), id);
+}
+
+HIR::Item *
+Mappings::lookup_hir_item (HirId id)
+{
+  auto it = hirItemMappings.find (id);
+  if (it == hirItemMappings.end ())
+    return nullptr;
+
+  return it->second;
+}
+
+void
+Mappings::insert_hir_trait_item (HIR::TraitItem *item)
+{
+  auto id = item->get_mappings ().get_hirid ();
+  rust_assert (lookup_hir_trait_item (id) == nullptr);
+
+  hirTraitItemMappings[id] = item;
+  insert_node_to_hir (item->get_mappings ().get_nodeid (), id);
+}
+
+HIR::TraitItem *
+Mappings::lookup_hir_trait_item (HirId id)
+{
+  auto it = hirTraitItemMappings.find (id);
+  if (it == hirTraitItemMappings.end ())
+    return nullptr;
+
+  return it->second;
+}
+
+void
+Mappings::insert_hir_extern_block (HIR::ExternBlock *block)
+{
+  auto id = block->get_mappings ().get_hirid ();
+  rust_assert (lookup_hir_extern_block (id) == nullptr);
+
+  hirExternBlockMappings[id] = block;
+  insert_node_to_hir (block->get_mappings ().get_nodeid (), id);
+}
+
+HIR::ExternBlock *
+Mappings::lookup_hir_extern_block (HirId id)
+{
+  auto it = hirExternBlockMappings.find (id);
+  if (it == hirExternBlockMappings.end ())
+    return nullptr;
+
+  return it->second;
+}
+
+void
+Mappings::insert_hir_extern_item (HIR::ExternalItem *item, HirId parent_block)
+{
+  auto id = item->get_mappings ().get_hirid ();
+  rust_assert (lookup_hir_extern_item (id, nullptr) == nullptr);
+
+  hirExternItemMappings[id] = {item, parent_block};
+  insert_node_to_hir (item->get_mappings ().get_nodeid (), id);
+}
+
+HIR::ExternalItem *
+Mappings::lookup_hir_extern_item (HirId id, HirId *parent_block)
+{
+  auto it = hirExternItemMappings.find (id);
+  if (it == hirExternItemMappings.end ())
+    return nullptr;
+
+  *parent_block = it->second.second;
+
+  return it->second.first;
+}
+
+void
+Mappings::insert_hir_impl_block (HIR::ImplBlock *item)
+{
+  auto id = item->get_mappings ().get_hirid ();
+  rust_assert (lookup_hir_impl_block (id) == nullptr);
+
+  hirImplBlockMappings[id] = item;
+  insert_node_to_hir (item->get_mappings ().get_nodeid (), id);
+}
+
+HIR::ImplBlock *
+Mappings::lookup_hir_impl_block (HirId id)
+{
+  auto it = hirImplBlockMappings.find (id);
+  if (it == hirImplBlockMappings.end ())
+    return nullptr;
+
+  return it->second;
+}
+
+void
+Mappings::insert_module (HIR::Module *module)
+{
+  auto id = module->get_mappings ().get_hirid ();
+  rust_assert (lookup_module (id) == nullptr);
+
+  hirModuleMappings[id] = module;
+  insert_node_to_hir (module->get_mappings ().get_nodeid (), id);
+}
+
+HIR::Module *
+Mappings::lookup_module (HirId id)
+{
+  auto it = hirModuleMappings.find (id);
+  if (it == hirModuleMappings.end ())
+    return nullptr;
+
+  return it->second;
+}
+
+void
+Mappings::insert_hir_implitem (HirId parent_impl_id, HIR::ImplItem *item)
+{
+  auto id = item->get_impl_mappings ().get_hirid ();
+  rust_assert (lookup_hir_implitem (id, nullptr) == nullptr);
+
+  hirImplItemMappings[id]
+    = std::pair<HirId, HIR::ImplItem *> (parent_impl_id, item);
+  insert_node_to_hir (item->get_impl_mappings ().get_nodeid (), id);
+}
+
+HIR::ImplItem *
+Mappings::lookup_hir_implitem (HirId id, HirId *parent_impl_id)
+{
+  auto it = hirImplItemMappings.find (id);
+  if (it == hirImplItemMappings.end ())
+    return nullptr;
+
+  std::pair<HirId, HIR::ImplItem *> &ref = it->second;
+  if (parent_impl_id != nullptr)
+    *parent_impl_id = ref.first;
+
+  return ref.second;
+}
+
+void
+Mappings::insert_hir_expr (HIR::Expr *expr)
+{
+  auto id = expr->get_mappings ().get_hirid ();
+  hirExprMappings[id] = expr;
+
+  insert_node_to_hir (expr->get_mappings ().get_nodeid (), id);
+  insert_location (id, expr->get_locus ());
+}
+
+HIR::Expr *
+Mappings::lookup_hir_expr (HirId id)
+{
+  auto it = hirExprMappings.find (id);
+  if (it == hirExprMappings.end ())
+    return nullptr;
+
+  return it->second;
+}
+
+void
+Mappings::insert_hir_path_expr_seg (HIR::PathExprSegment *expr)
+{
+  auto id = expr->get_mappings ().get_hirid ();
+  rust_assert (lookup_hir_path_expr_seg (id) == nullptr);
+
+  hirPathSegMappings[id] = expr;
+  insert_node_to_hir (expr->get_mappings ().get_nodeid (), id);
+  insert_location (id, expr->get_locus ());
+}
+
+HIR::PathExprSegment *
+Mappings::lookup_hir_path_expr_seg (HirId id)
+{
+  auto it = hirPathSegMappings.find (id);
+  if (it == hirPathSegMappings.end ())
+    return nullptr;
+
+  return it->second;
+}
+
+void
+Mappings::insert_hir_generic_param (HIR::GenericParam *param)
+{
+  auto id = param->get_mappings ().get_hirid ();
+  rust_assert (lookup_hir_generic_param (id) == nullptr);
+
+  hirGenericParamMappings[id] = param;
+  insert_node_to_hir (param->get_mappings ().get_nodeid (), id);
+  insert_location (id, param->get_locus ());
+}
+
+HIR::GenericParam *
+Mappings::lookup_hir_generic_param (HirId id)
+{
+  auto it = hirGenericParamMappings.find (id);
+  if (it == hirGenericParamMappings.end ())
+    return nullptr;
+
+  return it->second;
+}
+
+void
+Mappings::insert_hir_type (HIR::Type *type)
+{
+  auto id = type->get_mappings ().get_hirid ();
+  rust_assert (lookup_hir_type (id) == nullptr);
+
+  hirTypeMappings[id] = type;
+  insert_node_to_hir (type->get_mappings ().get_nodeid (), id);
+}
+
+HIR::Type *
+Mappings::lookup_hir_type (HirId id)
+{
+  auto it = hirTypeMappings.find (id);
+  if (it == hirTypeMappings.end ())
+    return nullptr;
+
+  return it->second;
+}
+
+void
+Mappings::insert_hir_stmt (HIR::Stmt *stmt)
+{
+  auto id = stmt->get_mappings ().get_hirid ();
+  rust_assert (lookup_hir_stmt (id) == nullptr);
+
+  hirStmtMappings[id] = stmt;
+  insert_node_to_hir (stmt->get_mappings ().get_nodeid (), id);
+}
+
+HIR::Stmt *
+Mappings::lookup_hir_stmt (HirId id)
+{
+  auto it = hirStmtMappings.find (id);
+  if (it == hirStmtMappings.end ())
+    return nullptr;
+
+  return it->second;
+}
+
+void
+Mappings::insert_hir_param (HIR::FunctionParam *param)
+{
+  auto id = param->get_mappings ().get_hirid ();
+  rust_assert (lookup_hir_param (id) == nullptr);
+
+  hirParamMappings[id] = param;
+  insert_node_to_hir (param->get_mappings ().get_nodeid (), id);
+}
+
+HIR::FunctionParam *
+Mappings::lookup_hir_param (HirId id)
+{
+  auto it = hirParamMappings.find (id);
+  if (it == hirParamMappings.end ())
+    return nullptr;
+
+  return it->second;
+}
+
+void
+Mappings::insert_hir_self_param (HIR::SelfParam *param)
+{
+  auto id = param->get_mappings ().get_hirid ();
+  rust_assert (lookup_hir_self_param (id) == nullptr);
+
+  hirSelfParamMappings[id] = param;
+  insert_node_to_hir (param->get_mappings ().get_nodeid (), id);
+}
+
+HIR::SelfParam *
+Mappings::lookup_hir_self_param (HirId id)
+{
+  auto it = hirSelfParamMappings.find (id);
+  if (it == hirSelfParamMappings.end ())
+    return nullptr;
+
+  return it->second;
+}
+
+void
+Mappings::insert_hir_struct_field (HIR::StructExprField *field)
+{
+  auto id = field->get_mappings ().get_hirid ();
+  rust_assert (lookup_hir_struct_field (id) == nullptr);
+
+  hirStructFieldMappings[id] = field;
+  insert_node_to_hir (field->get_mappings ().get_nodeid (), id);
+}
+
+HIR::StructExprField *
+Mappings::lookup_hir_struct_field (HirId id)
+{
+  auto it = hirStructFieldMappings.find (id);
+  if (it == hirStructFieldMappings.end ())
+    return nullptr;
+
+  return it->second;
+}
+
+void
+Mappings::insert_hir_pattern (HIR::Pattern *pattern)
+{
+  auto id = pattern->get_pattern_mappings ().get_hirid ();
+  rust_assert (lookup_hir_pattern (id) == nullptr);
+
+  hirPatternMappings[id] = pattern;
+  insert_node_to_hir (pattern->get_pattern_mappings ().get_nodeid (), id);
+}
+
+HIR::Pattern *
+Mappings::lookup_hir_pattern (HirId id)
+{
+  auto it = hirPatternMappings.find (id);
+  if (it == hirPatternMappings.end ())
+    return nullptr;
+
+  return it->second;
+}
+
+void
+Mappings::insert_local_defid_mapping (CrateNum crateNum, LocalDefId id,
+				      HIR::Item *item)
+{
+  rust_assert (lookup_local_defid (crateNum, id) == nullptr);
+  localDefIdMappings[crateNum][id] = item;
+}
+
+HIR::Item *
+Mappings::lookup_local_defid (CrateNum crateNum, LocalDefId id)
+{
+  auto it = localDefIdMappings.find (crateNum);
+  if (it == localDefIdMappings.end ())
+    return nullptr;
+
+  auto iy = it->second.find (id);
+  if (iy == it->second.end ())
+    return nullptr;
+
+  return iy->second;
+}
+
+void
+Mappings::walk_local_defids_for_crate (CrateNum crateNum,
+				       std::function<bool (HIR::Item *)> cb)
+{
+  auto it = localDefIdMappings.find (crateNum);
+  if (it == localDefIdMappings.end ())
+    return;
+
+  for (auto iy = it->second.begin (); iy != it->second.end (); iy++)
+    {
+      if (!cb (iy->second))
+	return;
+    }
+}
+
+void
+Mappings::insert_node_to_hir (NodeId id, HirId ref)
+{
+  nodeIdToHirMappings[id] = ref;
+  hirIdToNodeMappings[ref] = id;
+}
+
+bool
+Mappings::lookup_node_to_hir (NodeId id, HirId *ref)
+{
+  auto it = nodeIdToHirMappings.find (id);
+  if (it == nodeIdToHirMappings.end ())
+    return false;
+
+  *ref = it->second;
+  return true;
+}
+
+bool
+Mappings::lookup_hir_to_node (HirId id, NodeId *ref)
+{
+  auto it = hirIdToNodeMappings.find (id);
+  if (it == hirIdToNodeMappings.end ())
+    return false;
+
+  *ref = it->second;
+  return true;
+}
+
+void
+Mappings::insert_location (HirId id, Location locus)
+{
+  locations[id] = locus;
+}
+
+Location
+Mappings::lookup_location (HirId id)
+{
+  auto it = locations.find (id);
+  if (it == locations.end ())
+    return Location ();
+
+  return it->second;
+}
+
+bool
+Mappings::resolve_nodeid_to_stmt (NodeId id, HIR::Stmt **stmt)
+{
+  auto it = nodeIdToHirMappings.find (id);
+  if (it == nodeIdToHirMappings.end ())
+    return false;
+
+  HirId resolved = it->second;
+  auto resolved_stmt = lookup_hir_stmt (resolved);
+  *stmt = resolved_stmt;
+  return resolved_stmt != nullptr;
+}
+
+void
+Mappings::iterate_impl_items (
+  std::function<bool (HirId, HIR::ImplItem *, HIR::ImplBlock *)> cb)
+{
+  for (auto it = hirImplItemMappings.begin (); it != hirImplItemMappings.end ();
+       it++)
+    {
+      auto id = it->first;
+      auto impl_item = it->second.second;
+      auto impl
+	= lookup_associated_impl (impl_item->get_impl_mappings ().get_hirid ());
+      if (!cb (id, impl_item, impl))
+	return;
+    }
+}
+
+void
+Mappings::iterate_impl_blocks (std::function<bool (HirId, HIR::ImplBlock *)> cb)
+{
+  for (auto it = hirImplBlockMappings.begin ();
+       it != hirImplBlockMappings.end (); it++)
+    {
+      HirId id = it->first;
+      HIR::ImplBlock *impl_block = it->second;
+      if (!cb (id, impl_block))
+	return;
+    }
+}
+
+void
+Mappings::iterate_trait_items (
+  std::function<bool (HIR::TraitItem *, HIR::Trait *)> cb)
+{
+  for (auto it = hirTraitItemMappings.begin ();
+       it != hirTraitItemMappings.end (); it++)
+    {
+      HirId trait_item_id = it->first;
+      HIR::TraitItem *trait_item = it->second;
+      HIR::Trait *trait = lookup_trait_item_mapping (trait_item_id);
+
+      if (!cb (trait_item, trait))
+	return;
+    }
+}
+
+void
+Mappings::insert_macro_def (AST::MacroRulesDefinition *macro)
+{
+  static std::map<std::string, std::function<AST::ASTFragment (
+				 Location, AST::MacroInvocData &)>>
+    builtin_macros = {
+      {"assert", MacroBuiltin::assert},
+      {"file", MacroBuiltin::file},
+      {"line", MacroBuiltin::line},
+      {"column", MacroBuiltin::column},
+      {"include_bytes", MacroBuiltin::include_bytes},
+      {"include_str", MacroBuiltin::include_str},
+      {"compile_error", MacroBuiltin::compile_error},
+      {"concat", MacroBuiltin::concat},
+      {"env", MacroBuiltin::env},
+      {"cfg", MacroBuiltin::cfg},
+      {"include", MacroBuiltin::include},
+    };
+
+  auto outer_attrs = macro->get_outer_attrs ();
+  bool should_be_builtin
+    = std::any_of (outer_attrs.begin (), outer_attrs.end (),
+		   [] (AST::Attribute attr) {
+		     return attr.get_path () == "rustc_builtin_macro";
+		   });
+  if (should_be_builtin)
+    {
+      auto builtin = builtin_macros.find (macro->get_rule_name ());
+      if (builtin != builtin_macros.end ())
+	macro->set_builtin_transcriber (builtin->second);
+      else
+	rust_error_at (macro->get_locus (),
+		       "cannot find a built-in macro with name %qs",
+		       macro->get_rule_name ().c_str ());
+    }
+
+  auto it = macroMappings.find (macro->get_node_id ());
+  rust_assert (it == macroMappings.end ());
+
+  macroMappings[macro->get_node_id ()] = macro;
+}
+
+bool
+Mappings::lookup_macro_def (NodeId id, AST::MacroRulesDefinition **def)
+{
+  auto it = macroMappings.find (id);
+  if (it == macroMappings.end ())
+    return false;
+
+  *def = it->second;
+  return true;
+}
+
+void
+Mappings::insert_visibility (NodeId id, Privacy::ModuleVisibility visibility)
+{
+  visibility_map.insert ({id, visibility});
+}
+
+bool
+Mappings::lookup_visibility (NodeId id, Privacy::ModuleVisibility &def)
+{
+  auto it = visibility_map.find (id);
+  if (it == visibility_map.end ())
+    return false;
+
+  def = it->second;
+  return true;
+}
+
+void
+Mappings::insert_module_child (NodeId module, NodeId child)
+{
+  auto it = module_child_map.find (module);
+  if (it == module_child_map.end ())
+    module_child_map.insert ({module, {child}});
+  else
+    it->second.emplace_back (child);
+}
+
+Optional<std::vector<NodeId> &>
+Mappings::lookup_module_children (NodeId module)
+{
+  auto it = module_child_map.find (module);
+  if (it == module_child_map.end ())
+    return Optional<std::vector<NodeId> &>::none ();
+
+  return Optional<std::vector<NodeId> &>::some (it->second);
+}
+
+void
+Mappings::insert_module_child_item (NodeId module,
+				    Resolver::CanonicalPath child)
+{
+  rust_assert (!child.is_empty ());
+  rust_assert (child.get_node_id () != UNKNOWN_NODEID);
+
+  auto it = module_child_items.find (module);
+  if (it == module_child_items.end ())
+    module_child_items.insert ({module, {child}});
+  else
+    it->second.emplace_back (child);
+}
+
+Optional<std::vector<Resolver::CanonicalPath> &>
+Mappings::lookup_module_chidren_items (NodeId module)
+{
+  auto it = module_child_items.find (module);
+  if (it == module_child_items.end ())
+    return Optional<std::vector<Resolver::CanonicalPath> &>::none ();
+
+  return Optional<std::vector<Resolver::CanonicalPath> &>::some (it->second);
+}
+
+Optional<Resolver::CanonicalPath &>
+Mappings::lookup_module_child (NodeId module, const std::string &item_name)
+{
+  Optional<std::vector<Resolver::CanonicalPath> &> children
+    = lookup_module_chidren_items (module);
+  if (children.is_none ())
+    return Optional<Resolver::CanonicalPath &>::none ();
+
+  // lookup the children to match the name if we can
+  for (auto &child : children.get ())
+    {
+      const std::string &raw_identifier = child.get ();
+      bool found = raw_identifier.compare (item_name) == 0;
+      if (found)
+	return Optional<Resolver::CanonicalPath &>::some (child);
+    }
+  return Optional<Resolver::CanonicalPath &>::none ();
+}
+
+void
+Mappings::insert_child_item_to_parent_module_mapping (NodeId child_item,
+						      NodeId parent_module)
+{
+  child_to_parent_module_map.insert ({child_item, parent_module});
+}
+
+Optional<NodeId>
+Mappings::lookup_parent_module (NodeId child_item)
+{
+  auto it = child_to_parent_module_map.find (child_item);
+  if (it == child_to_parent_module_map.end ())
+    return Optional<NodeId>::none ();
+
+  return Optional<NodeId>::some (it->second);
+}
+
+bool
+Mappings::node_is_module (NodeId query)
+{
+  return module_child_items.find (query) != module_child_items.end ();
+}
+
+void
+Mappings::insert_ast_item (AST::Item *item)
+{
+  auto it = ast_item_mappings.find (item->get_node_id ());
+  rust_assert (it == ast_item_mappings.end ());
+
+  ast_item_mappings[item->get_node_id ()] = item;
+}
+
+bool
+Mappings::lookup_ast_item (NodeId id, AST::Item **result)
+{
+  auto it = ast_item_mappings.find (id);
+  if (it == ast_item_mappings.end ())
+    return false;
+
+  *result = it->second;
+  return true;
+}
+
+} // namespace Analysis
+} // namespace Rust
diff --git a/gcc/rust/util/rust-hir-map.h b/gcc/rust/util/rust-hir-map.h
new file mode 100644
index 00000000000..98fcfe6a6a7
--- /dev/null
+++ b/gcc/rust/util/rust-hir-map.h
@@ -0,0 +1,356 @@
+// Copyright (C) 2020-2022 Free Software Foundation, Inc.
+
+// This file is part of GCC.
+
+// GCC 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, or (at your option) any later
+// version.
+
+// GCC 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 GCC; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#ifndef RUST_HIR_MAP_H
+#define RUST_HIR_MAP_H
+
+#include "rust-optional.h"
+#include "rust-system.h"
+#include "rust-location.h"
+#include "rust-mapping-common.h"
+#include "rust-canonical-path.h"
+#include "rust-ast-full-decls.h"
+#include "rust-hir-full-decls.h"
+#include "rust-lang-item.h"
+#include "rust-privacy-common.h"
+
+namespace Rust {
+namespace Analysis {
+
+class NodeMapping
+{
+public:
+  NodeMapping (CrateNum crateNum, NodeId nodeId, HirId hirId,
+	       LocalDefId localDefId)
+    : crateNum (crateNum), nodeId (nodeId), hirId (hirId),
+      localDefId (localDefId)
+  {}
+
+  static NodeMapping get_error ();
+
+  CrateNum get_crate_num () const;
+  NodeId get_nodeid () const;
+  HirId get_hirid () const;
+  LocalDefId get_local_defid () const;
+  DefId get_defid () const;
+
+  static DefId get_defid (CrateNum crate_num, LocalDefId local_defid);
+
+  std::string as_string () const;
+
+  bool is_equal (const NodeMapping &other) const
+  {
+    return get_crate_num () == other.get_crate_num ()
+	   && get_nodeid () == other.get_nodeid ()
+	   && get_hirid () == other.get_hirid ()
+	   && get_local_defid () == other.get_local_defid ();
+  }
+
+private:
+  CrateNum crateNum;
+  NodeId nodeId;
+  HirId hirId;
+  LocalDefId localDefId;
+};
+
+class Mappings
+{
+public:
+  static Mappings *get ();
+  ~Mappings ();
+
+  CrateNum get_next_crate_num (const std::string &name);
+  void set_current_crate (CrateNum crateNum);
+  CrateNum get_current_crate () const;
+  bool get_crate_name (CrateNum crate_num, std::string &name) const;
+  void set_crate_name (CrateNum crate_num, const std::string &name);
+  std::string get_current_crate_name () const;
+  bool lookup_crate_name (const std::string &crate_name,
+			  CrateNum &resolved_crate_num) const;
+  bool crate_num_to_nodeid (const CrateNum &crate_num, NodeId &node_id) const;
+  bool node_is_crate (NodeId node_id) const;
+
+  NodeId get_next_node_id ();
+  HirId get_next_hir_id () { return get_next_hir_id (get_current_crate ()); }
+  HirId get_next_hir_id (CrateNum crateNum);
+  LocalDefId get_next_localdef_id ()
+  {
+    return get_next_localdef_id (get_current_crate ());
+  }
+  LocalDefId get_next_localdef_id (CrateNum crateNum);
+
+  AST::Crate &get_ast_crate (CrateNum crateNum);
+  AST::Crate &get_ast_crate_by_node_id (NodeId id);
+  AST::Crate &insert_ast_crate (std::unique_ptr<AST::Crate> &&crate,
+				CrateNum crate_num);
+  HIR::Crate &insert_hir_crate (std::unique_ptr<HIR::Crate> &&crate);
+  HIR::Crate &get_hir_crate (CrateNum crateNum);
+  bool is_local_hirid_crate (HirId crateNum);
+
+  void insert_defid_mapping (DefId id, HIR::Item *item);
+  HIR::Item *lookup_defid (DefId id);
+
+  void insert_local_defid_mapping (CrateNum crateNum, LocalDefId id,
+				   HIR::Item *item);
+  HIR::Item *lookup_local_defid (CrateNum crateNum, LocalDefId id);
+
+  void insert_hir_item (HIR::Item *item);
+  HIR::Item *lookup_hir_item (HirId id);
+
+  void insert_hir_trait_item (HIR::TraitItem *item);
+  HIR::TraitItem *lookup_hir_trait_item (HirId id);
+
+  void insert_hir_extern_block (HIR::ExternBlock *block);
+  HIR::ExternBlock *lookup_hir_extern_block (HirId id);
+
+  void insert_hir_extern_item (HIR::ExternalItem *item, HirId parent_block);
+  HIR::ExternalItem *lookup_hir_extern_item (HirId id, HirId *parent_block);
+
+  void insert_hir_impl_block (HIR::ImplBlock *item);
+  HIR::ImplBlock *lookup_hir_impl_block (HirId id);
+
+  void insert_module (HIR::Module *module);
+  HIR::Module *lookup_module (HirId id);
+
+  void insert_hir_implitem (HirId parent_impl_id, HIR::ImplItem *item);
+  HIR::ImplItem *lookup_hir_implitem (HirId id, HirId *parent_impl_id);
+
+  void insert_hir_expr (HIR::Expr *expr);
+  HIR::Expr *lookup_hir_expr (HirId id);
+
+  void insert_hir_path_expr_seg (HIR::PathExprSegment *expr);
+  HIR::PathExprSegment *lookup_hir_path_expr_seg (HirId id);
+
+  void insert_hir_generic_param (HIR::GenericParam *expr);
+  HIR::GenericParam *lookup_hir_generic_param (HirId id);
+
+  void insert_hir_type (HIR::Type *type);
+  HIR::Type *lookup_hir_type (HirId id);
+
+  void insert_hir_stmt (HIR::Stmt *stmt);
+  HIR::Stmt *lookup_hir_stmt (HirId id);
+
+  void insert_hir_param (HIR::FunctionParam *type);
+  HIR::FunctionParam *lookup_hir_param (HirId id);
+
+  void insert_hir_self_param (HIR::SelfParam *type);
+  HIR::SelfParam *lookup_hir_self_param (HirId id);
+
+  void insert_hir_struct_field (HIR::StructExprField *type);
+  HIR::StructExprField *lookup_hir_struct_field (HirId id);
+
+  void insert_hir_pattern (HIR::Pattern *pattern);
+  HIR::Pattern *lookup_hir_pattern (HirId id);
+
+  void walk_local_defids_for_crate (CrateNum crateNum,
+				    std::function<bool (HIR::Item *)> cb);
+
+  void insert_node_to_hir (NodeId id, HirId ref);
+  bool lookup_node_to_hir (NodeId id, HirId *ref);
+  bool lookup_hir_to_node (HirId id, NodeId *ref);
+
+  void insert_location (HirId id, Location locus);
+  Location lookup_location (HirId id);
+
+  bool resolve_nodeid_to_stmt (NodeId id, HIR::Stmt **stmt);
+
+  std::set<HirId> &get_hirids_within_crate (CrateNum crate)
+  {
+    return hirNodesWithinCrate[crate];
+  }
+
+  void insert_impl_item_mapping (HirId impl_item_id, HIR::ImplBlock *impl)
+  {
+    rust_assert (hirImplItemsToImplMappings.find (impl_item_id)
+		 == hirImplItemsToImplMappings.end ());
+    hirImplItemsToImplMappings[impl_item_id] = impl;
+  }
+
+  HIR::ImplBlock *lookup_associated_impl (HirId impl_item_id)
+  {
+    auto lookup = hirImplItemsToImplMappings.find (impl_item_id);
+    rust_assert (lookup != hirImplItemsToImplMappings.end ());
+    return lookup->second;
+  }
+
+  void iterate_impl_items (
+    std::function<bool (HirId, HIR::ImplItem *, HIR::ImplBlock *)> cb);
+
+  void iterate_impl_blocks (std::function<bool (HirId, HIR::ImplBlock *)> cb);
+
+  void iterate_trait_items (
+    std::function<bool (HIR::TraitItem *item, HIR::Trait *)> cb);
+
+  bool is_impl_item (HirId id)
+  {
+    HirId parent_impl_block_id = UNKNOWN_HIRID;
+    return lookup_hir_implitem (id, &parent_impl_block_id) != nullptr;
+  }
+
+  void insert_trait_item_mapping (HirId trait_item_id, HIR::Trait *trait)
+  {
+    rust_assert (hirTraitItemsToTraitMappings.find (trait_item_id)
+		 == hirTraitItemsToTraitMappings.end ());
+    hirTraitItemsToTraitMappings[trait_item_id] = trait;
+  }
+
+  HIR::Trait *lookup_trait_item_mapping (HirId trait_item_id)
+  {
+    auto lookup = hirTraitItemsToTraitMappings.find (trait_item_id);
+    rust_assert (lookup != hirTraitItemsToTraitMappings.end ());
+    return lookup->second;
+  }
+
+  void insert_canonical_path (NodeId id, const Resolver::CanonicalPath path)
+  {
+    const Resolver::CanonicalPath *p = nullptr;
+    if (lookup_canonical_path (id, &p))
+      {
+	// if we have already stored a canonical path this is ok so long as
+	// this new path is equal or is smaller that the existing one but in
+	// that case we ignore it.
+	if (p->is_equal (path))
+	  return;
+	else
+	  {
+	    rust_assert (p->size () >= path.size ());
+	    return;
+	  }
+      }
+
+    paths.emplace (id, std::move (path));
+  }
+
+  bool lookup_canonical_path (NodeId id, const Resolver::CanonicalPath **path)
+  {
+    auto it = paths.find (id);
+    if (it == paths.end ())
+      return false;
+
+    *path = &it->second;
+    return true;
+  }
+
+  void insert_lang_item (RustLangItem::ItemType item_type, DefId id)
+  {
+    auto it = lang_item_mappings.find (item_type);
+    rust_assert (it == lang_item_mappings.end ());
+
+    lang_item_mappings[item_type] = id;
+  }
+
+  bool lookup_lang_item (RustLangItem::ItemType item_type, DefId *id)
+  {
+    auto it = lang_item_mappings.find (item_type);
+    if (it == lang_item_mappings.end ())
+      return false;
+
+    *id = it->second;
+    return true;
+  }
+
+  void insert_macro_def (AST::MacroRulesDefinition *macro);
+
+  bool lookup_macro_def (NodeId id, AST::MacroRulesDefinition **def);
+
+  void insert_visibility (NodeId id, Privacy::ModuleVisibility visibility);
+  bool lookup_visibility (NodeId id, Privacy::ModuleVisibility &def);
+
+  void insert_module_child (NodeId module, NodeId child);
+  Optional<std::vector<NodeId> &> lookup_module_children (NodeId module);
+
+  void insert_module_child_item (NodeId module, Resolver::CanonicalPath item);
+  Optional<std::vector<Resolver::CanonicalPath> &>
+  lookup_module_chidren_items (NodeId module);
+  Optional<Resolver::CanonicalPath &>
+  lookup_module_child (NodeId module, const std::string &item_name);
+
+  void insert_child_item_to_parent_module_mapping (NodeId child_item,
+						   NodeId parent_module);
+  Optional<NodeId> lookup_parent_module (NodeId child_item);
+  bool node_is_module (NodeId query);
+
+  void insert_ast_item (AST::Item *item);
+  bool lookup_ast_item (NodeId id, AST::Item **result);
+
+private:
+  Mappings ();
+
+  CrateNum crateNumItr;
+  CrateNum currentCrateNum;
+  HirId hirIdIter;
+  NodeId nodeIdIter;
+  std::map<CrateNum, LocalDefId> localIdIter;
+
+  std::map<NodeId, CrateNum> crate_node_to_crate_num;
+  std::map<CrateNum, AST::Crate *> ast_crate_mappings;
+  std::map<CrateNum, HIR::Crate *> hir_crate_mappings;
+  std::map<DefId, HIR::Item *> defIdMappings;
+  std::map<CrateNum, std::map<LocalDefId, HIR::Item *>> localDefIdMappings;
+
+  std::map<HirId, HIR::Module *> hirModuleMappings;
+  std::map<HirId, HIR::Item *> hirItemMappings;
+  std::map<HirId, HIR::Type *> hirTypeMappings;
+  std::map<HirId, HIR::Expr *> hirExprMappings;
+  std::map<HirId, HIR::Stmt *> hirStmtMappings;
+  std::map<HirId, HIR::FunctionParam *> hirParamMappings;
+  std::map<HirId, HIR::StructExprField *> hirStructFieldMappings;
+  std::map<HirId, std::pair<HirId, HIR::ImplItem *>> hirImplItemMappings;
+  std::map<HirId, HIR::SelfParam *> hirSelfParamMappings;
+  std::map<HirId, HIR::ImplBlock *> hirImplItemsToImplMappings;
+  std::map<HirId, HIR::ImplBlock *> hirImplBlockMappings;
+  std::map<HirId, HIR::TraitItem *> hirTraitItemMappings;
+  std::map<HirId, HIR::ExternBlock *> hirExternBlockMappings;
+  std::map<HirId, std::pair<HIR::ExternalItem *, HirId>> hirExternItemMappings;
+  std::map<HirId, HIR::PathExprSegment *> hirPathSegMappings;
+  std::map<HirId, HIR::GenericParam *> hirGenericParamMappings;
+  std::map<HirId, HIR::Trait *> hirTraitItemsToTraitMappings;
+  std::map<HirId, HIR::Pattern *> hirPatternMappings;
+  std::map<RustLangItem::ItemType, DefId> lang_item_mappings;
+  std::map<NodeId, const Resolver::CanonicalPath> paths;
+  std::map<NodeId, Location> locations;
+  std::map<NodeId, HirId> nodeIdToHirMappings;
+  std::map<HirId, NodeId> hirIdToNodeMappings;
+
+  // all hirid nodes
+  std::map<CrateNum, std::set<HirId>> hirNodesWithinCrate;
+
+  // macros
+  std::map<NodeId, AST::MacroRulesDefinition *> macroMappings;
+
+  // crate names
+  std::map<CrateNum, std::string> crate_names;
+
+  // Low level visibility map for each DefId
+  std::map<NodeId, Privacy::ModuleVisibility> visibility_map;
+
+  // Module tree maps
+
+  // Maps each module's node id to a list of its children
+  std::map<NodeId, std::vector<NodeId>> module_child_map;
+  std::map<NodeId, std::vector<Resolver::CanonicalPath>> module_child_items;
+  std::map<NodeId, NodeId> child_to_parent_module_map;
+
+  // AST mappings
+  std::map<NodeId, AST::Item *> ast_item_mappings;
+};
+
+} // namespace Analysis
+} // namespace Rust
+
+#endif // RUST_HIR_MAP_H
diff --git a/gcc/rust/util/rust-identifier.h b/gcc/rust/util/rust-identifier.h
new file mode 100644
index 00000000000..0b5cb70b373
--- /dev/null
+++ b/gcc/rust/util/rust-identifier.h
@@ -0,0 +1,49 @@
+// Copyright (C) 2020-2022 Free Software Foundation, Inc.
+
+// This file is part of GCC.
+
+// GCC 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, or (at your option) any later
+// version.
+
+// GCC 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 GCC; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#ifndef RUST_IDENTIFIER
+#define RUST_IDENTIFIER
+
+#include "rust-canonical-path.h"
+#include "rust-location.h"
+
+namespace Rust {
+
+struct RustIdent
+{
+  Resolver::CanonicalPath path;
+  Location locus;
+
+  RustIdent (const Resolver::CanonicalPath &path, Location locus)
+    : path (path), locus (locus)
+  {}
+
+  RustIdent (const RustIdent &other) : path (other.path), locus (other.locus) {}
+
+  RustIdent &operator= (const RustIdent &other)
+  {
+    path = other.path;
+    locus = other.locus;
+
+    return *this;
+  }
+};
+
+} // namespace Rust
+
+#endif // RUST_IDENTIFIER
diff --git a/gcc/rust/util/rust-lang-item.h b/gcc/rust/util/rust-lang-item.h
new file mode 100644
index 00000000000..9d1ee900aec
--- /dev/null
+++ b/gcc/rust/util/rust-lang-item.h
@@ -0,0 +1,377 @@
+// Copyright (C) 2020-2022 Free Software Foundation, Inc.
+
+// This file is part of GCC.
+
+// GCC 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, or (at your option) any later
+// version.
+
+// GCC 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 GCC; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include "rust-system.h"
+#include "operator.h"
+
+namespace Rust {
+namespace Analysis {
+
+// https://github.com/rust-lang/rust/blob/master/library/core/src/ops/arith.rs
+class RustLangItem
+{
+public:
+  enum ItemType
+  {
+    ADD,
+    SUBTRACT,
+    MULTIPLY,
+    DIVIDE,
+    REMAINDER,
+    BITAND,
+    BITOR,
+    BITXOR,
+    SHL,
+    SHR,
+
+    NEGATION,
+    NOT,
+
+    ADD_ASSIGN,
+    SUB_ASSIGN,
+    MUL_ASSIGN,
+    DIV_ASSIGN,
+    REM_ASSIGN,
+    BITAND_ASSIGN,
+    BITOR_ASSIGN,
+    BITXOR_ASSIGN,
+    SHL_ASSIGN,
+    SHR_ASSIGN,
+
+    DEREF,
+    DEREF_MUT,
+
+    // https://github.com/rust-lang/rust/blob/master/library/core/src/ops/index.rs
+    INDEX,
+    INDEX_MUT,
+
+    // https://github.com/rust-lang/rust/blob/master/library/core/src/ops/range.rs
+    RANGE_FULL,
+    RANGE,
+    RANGE_FROM,
+    RANGE_TO,
+    RANGE_INCLUSIVE,
+    RANGE_TO_INCLUSIVE,
+
+    // https://github.com/rust-lang/rust/blob/master/library/core/src/ptr/const_ptr.rs
+    CONST_PTR,
+    MUT_PTR,
+    CONST_SLICE_PTR,
+
+    UNKNOWN,
+  };
+
+  static ItemType Parse (const std::string &item)
+  {
+    if (item.compare ("add") == 0)
+      {
+	return ItemType::ADD;
+      }
+    else if (item.compare ("sub") == 0)
+      {
+	return ItemType::SUBTRACT;
+      }
+    else if (item.compare ("mul") == 0)
+      {
+	return ItemType::MULTIPLY;
+      }
+    else if (item.compare ("div") == 0)
+      {
+	return ItemType::DIVIDE;
+      }
+    else if (item.compare ("rem") == 0)
+      {
+	return ItemType::REMAINDER;
+      }
+    else if (item.compare ("bitand") == 0)
+      {
+	return ItemType::BITAND;
+      }
+    else if (item.compare ("bitor") == 0)
+      {
+	return ItemType::BITOR;
+      }
+    else if (item.compare ("bitxor") == 0)
+      {
+	return ItemType::BITXOR;
+      }
+    else if (item.compare ("shl") == 0)
+      {
+	return ItemType::SHL;
+      }
+    else if (item.compare ("shr") == 0)
+      {
+	return ItemType::SHR;
+      }
+    else if (item.compare ("neg") == 0)
+      {
+	return ItemType::NEGATION;
+      }
+    else if (item.compare ("not") == 0)
+      {
+	return ItemType::NOT;
+      }
+    else if (item.compare ("add_assign") == 0)
+      {
+	return ItemType::ADD_ASSIGN;
+      }
+    else if (item.compare ("sub_assign") == 0)
+      {
+	return ItemType::SUB_ASSIGN;
+      }
+    else if (item.compare ("mul_assign") == 0)
+      {
+	return ItemType::MUL_ASSIGN;
+      }
+    else if (item.compare ("div_assign") == 0)
+      {
+	return ItemType::DIV_ASSIGN;
+      }
+    else if (item.compare ("rem_assign") == 0)
+      {
+	return ItemType::REM_ASSIGN;
+      }
+    else if (item.compare ("bitand_assign") == 0)
+      {
+	return ItemType::BITAND_ASSIGN;
+      }
+    else if (item.compare ("bitor_assign") == 0)
+      {
+	return ItemType::BITOR_ASSIGN;
+      }
+    else if (item.compare ("bitxor_assign") == 0)
+      {
+	return ItemType::BITXOR_ASSIGN;
+      }
+    else if (item.compare ("shl_assign") == 0)
+      {
+	return ItemType::SHL_ASSIGN;
+      }
+    else if (item.compare ("shr_assign") == 0)
+      {
+	return ItemType::SHR_ASSIGN;
+      }
+    else if (item.compare ("deref") == 0)
+      {
+	return ItemType::DEREF;
+      }
+    else if (item.compare ("deref_mut") == 0)
+      {
+	return ItemType::DEREF_MUT;
+      }
+    else if (item.compare ("index") == 0)
+      {
+	return ItemType::INDEX;
+      }
+    else if (item.compare ("index_mut") == 0)
+      {
+	return ItemType::INDEX_MUT;
+      }
+    else if (item.compare ("RangeFull") == 0)
+      {
+	return ItemType::RANGE_FULL;
+      }
+    else if (item.compare ("Range") == 0)
+      {
+	return ItemType::RANGE;
+      }
+    else if (item.compare ("RangeFrom") == 0)
+      {
+	return ItemType::RANGE_FROM;
+      }
+    else if (item.compare ("RangeTo") == 0)
+      {
+	return ItemType::RANGE_TO;
+      }
+    else if (item.compare ("RangeInclusive") == 0)
+      {
+	return ItemType::RANGE_INCLUSIVE;
+      }
+    else if (item.compare ("RangeToInclusive") == 0)
+      {
+	return ItemType::RANGE_TO_INCLUSIVE;
+      }
+    else if (item.compare ("const_ptr") == 0)
+      {
+	return ItemType::CONST_PTR;
+      }
+    else if (item.compare ("mut_ptr") == 0)
+      {
+	return ItemType::MUT_PTR;
+      }
+    else if (item.compare ("const_slice_ptr") == 0)
+      {
+	return ItemType::CONST_SLICE_PTR;
+      }
+
+    return ItemType::UNKNOWN;
+  }
+
+  static std::string ToString (ItemType type)
+  {
+    switch (type)
+      {
+      case ADD:
+	return "add";
+      case SUBTRACT:
+	return "sub";
+      case MULTIPLY:
+	return "mul";
+      case DIVIDE:
+	return "div";
+      case REMAINDER:
+	return "rem";
+      case BITAND:
+	return "bitand";
+      case BITOR:
+	return "bitor";
+      case BITXOR:
+	return "bitxor";
+      case SHL:
+	return "shl";
+      case SHR:
+	return "shr";
+      case NEGATION:
+	return "neg";
+      case NOT:
+	return "not";
+      case ADD_ASSIGN:
+	return "add_assign";
+      case SUB_ASSIGN:
+	return "sub_assign";
+      case MUL_ASSIGN:
+	return "mul_assign";
+      case DIV_ASSIGN:
+	return "div_assign";
+      case REM_ASSIGN:
+	return "rem_assign";
+      case BITAND_ASSIGN:
+	return "bitand_assign";
+      case BITOR_ASSIGN:
+	return "bitor_assign";
+      case BITXOR_ASSIGN:
+	return "bitxor_assign";
+      case SHL_ASSIGN:
+	return "shl_assign";
+      case SHR_ASSIGN:
+	return "shr_assign";
+      case DEREF:
+	return "deref";
+      case DEREF_MUT:
+	return "deref_mut";
+      case INDEX:
+	return "index";
+      case INDEX_MUT:
+	return "index_mut";
+      case RANGE_FULL:
+	return "RangeFull";
+      case RANGE:
+	return "Range";
+      case RANGE_FROM:
+	return "RangeFrom";
+      case RANGE_TO:
+	return "RangeTo";
+      case RANGE_INCLUSIVE:
+	return "RangeInclusive";
+      case RANGE_TO_INCLUSIVE:
+	return "RangeToInclusive";
+      case CONST_PTR:
+	return "const_ptr";
+      case MUT_PTR:
+	return "mut_ptr";
+      case CONST_SLICE_PTR:
+	return "const_slice_ptr";
+
+      case UNKNOWN:
+	return "<UNKNOWN>";
+      }
+    return "<UNKNOWN>";
+  }
+
+  static ItemType OperatorToLangItem (ArithmeticOrLogicalOperator op)
+  {
+    switch (op)
+      {
+      case ArithmeticOrLogicalOperator::ADD:
+	return ItemType::ADD;
+      case ArithmeticOrLogicalOperator::SUBTRACT:
+	return ItemType::SUBTRACT;
+      case ArithmeticOrLogicalOperator::MULTIPLY:
+	return ItemType::MULTIPLY;
+      case ArithmeticOrLogicalOperator::DIVIDE:
+	return ItemType::DIVIDE;
+      case ArithmeticOrLogicalOperator::MODULUS:
+	return ItemType::REMAINDER;
+      case ArithmeticOrLogicalOperator::BITWISE_AND:
+	return ItemType::BITAND;
+      case ArithmeticOrLogicalOperator::BITWISE_OR:
+	return ItemType::BITOR;
+      case ArithmeticOrLogicalOperator::BITWISE_XOR:
+	return ItemType::BITXOR;
+      case ArithmeticOrLogicalOperator::LEFT_SHIFT:
+	return ItemType::SHL;
+      case ArithmeticOrLogicalOperator::RIGHT_SHIFT:
+	return ItemType::SHR;
+      }
+    return ItemType::UNKNOWN;
+  }
+
+  static ItemType
+  CompoundAssignmentOperatorToLangItem (ArithmeticOrLogicalOperator op)
+  {
+    switch (op)
+      {
+      case ArithmeticOrLogicalOperator::ADD:
+	return ItemType::ADD_ASSIGN;
+      case ArithmeticOrLogicalOperator::SUBTRACT:
+	return ItemType::SUB_ASSIGN;
+      case ArithmeticOrLogicalOperator::MULTIPLY:
+	return ItemType::MUL_ASSIGN;
+      case ArithmeticOrLogicalOperator::DIVIDE:
+	return ItemType::DIV_ASSIGN;
+      case ArithmeticOrLogicalOperator::MODULUS:
+	return ItemType::REM_ASSIGN;
+      case ArithmeticOrLogicalOperator::BITWISE_AND:
+	return ItemType::BITAND_ASSIGN;
+      case ArithmeticOrLogicalOperator::BITWISE_OR:
+	return ItemType::BITOR_ASSIGN;
+      case ArithmeticOrLogicalOperator::BITWISE_XOR:
+	return ItemType::BITXOR_ASSIGN;
+      case ArithmeticOrLogicalOperator::LEFT_SHIFT:
+	return ItemType::SHL_ASSIGN;
+      case ArithmeticOrLogicalOperator::RIGHT_SHIFT:
+	return ItemType::SHR_ASSIGN;
+      }
+    return ItemType::UNKNOWN;
+  }
+
+  static ItemType NegationOperatorToLangItem (NegationOperator op)
+  {
+    switch (op)
+      {
+      case NegationOperator::NEGATE:
+	return ItemType::NEGATION;
+      case NegationOperator::NOT:
+	return ItemType::NOT;
+      }
+    return ItemType::UNKNOWN;
+  }
+};
+
+} // namespace Analysis
+} // namespace Rust
diff --git a/gcc/rust/util/rust-mapping-common.h b/gcc/rust/util/rust-mapping-common.h
new file mode 100644
index 00000000000..c440ae98931
--- /dev/null
+++ b/gcc/rust/util/rust-mapping-common.h
@@ -0,0 +1,85 @@
+// Copyright (C) 2020-2022 Free Software Foundation, Inc.
+
+// This file is part of GCC.
+
+// GCC 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, or (at your option) any later
+// version.
+
+// GCC 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 GCC; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#ifndef RUST_MAPPING_COMMON
+#define RUST_MAPPING_COMMON
+
+#include "rust-system.h"
+
+namespace Rust {
+
+// refers to a Crate
+typedef uint32_t CrateNum;
+// refers to any node in the AST in current Crate
+typedef uint32_t NodeId;
+// refers to any node in the HIR for the current crate
+typedef uint32_t HirId;
+// refers to any top-level decl in HIR
+typedef uint32_t LocalDefId;
+
+struct DefId
+{
+  CrateNum crateNum;
+  LocalDefId localDefId;
+
+  bool operator== (const DefId &other) const
+  {
+    return this->crateNum == other.crateNum
+	   && this->localDefId == other.localDefId;
+  }
+
+  bool operator!= (const DefId &other) const { return !(*this == other); }
+
+  bool operator< (const DefId &other) const
+  {
+    return ((uint64_t) this->crateNum << 32 | this->localDefId)
+	   < ((uint64_t) other.crateNum << 32 | other.localDefId);
+  }
+
+  std::string as_string () const
+  {
+    std::string buf;
+    buf += std::to_string (crateNum);
+    buf += " "; // or anything else
+    buf += std::to_string (localDefId);
+    return buf;
+  }
+};
+
+#define UNKNOWN_CREATENUM ((uint32_t) (0))
+#define UNKNOWN_NODEID ((uint32_t) (0))
+#define UNKNOWN_HIRID ((uint32_t) (0))
+#define UNKNOWN_LOCAL_DEFID ((uint32_t) (0))
+#define UNKNOWN_DEFID (DefId{0, 0})
+
+} // namespace Rust
+
+namespace std {
+template <> struct hash<Rust::DefId>
+{
+  size_t operator() (const Rust::DefId &id) const noexcept
+  {
+    // TODO: Check if we can improve performance by having a better hash
+    // algorithm for `DefId`s
+    return hash<uint32_t> () (hash<uint32_t> () (id.crateNum)
+			      + hash<uint32_t> () (id.localDefId));
+  }
+};
+} // namespace std
+
+#endif // RUST_MAPPING_COMMON
diff --git a/gcc/rust/util/rust-stacked-contexts.h b/gcc/rust/util/rust-stacked-contexts.h
new file mode 100644
index 00000000000..c34eb907f06
--- /dev/null
+++ b/gcc/rust/util/rust-stacked-contexts.h
@@ -0,0 +1,86 @@
+// Copyright (C) 2020-2022 Free Software Foundation, Inc.
+
+// This file is part of GCC.
+
+// GCC 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, or (at your option) any later
+// version.
+
+// GCC 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 GCC; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#ifndef RUST_CONTEXT_STACK_H
+#define RUST_CONTEXT_STACK_H
+
+#include "rust-system.h"
+
+namespace Rust {
+
+/**
+ * Context stack util class. This class is useful for situations where you can
+ * enter the same kind of context multiple times. For example, when dealing with
+ * unsafe contexts, you might be tempted to simply keep a boolean value.
+ *
+ * ```rust
+ * let a = 15;
+ * unsafe { // we set the boolean to true
+ *     // Now unsafe operations are allowed!
+ *     let b = *(&a as *const i32);
+ *     let c = std::mem::transmute<i32, f32>(b); // Urgh!
+ * } // we set it to false
+ * ```
+ *
+ * However, since the language allows nested unsafe blocks, you may run into
+ * this situation:
+ *
+ * ```rust
+ * unsafe { // we set the boolean to true
+ *     unsafe { // we set the boolean to true
+ *     } // we set it to false
+ *
+ *     // Now unsafe operations are forbidden again, the boolean is false
+ *     let f = std::mem::transmute<i32, f32>(15); // Error!
+ * } // we set it to false
+ * ```
+ */
+template <typename T> class StackedContexts
+{
+public:
+  /**
+   * Enter a special context
+   */
+  void enter (T value) { stack.emplace_back (value); }
+
+  /**
+   * Exit a special context
+   */
+  T exit ()
+  {
+    rust_assert (!stack.empty ());
+
+    auto last = stack.back ();
+    stack.pop_back ();
+
+    return last;
+  }
+
+  /**
+   * Are we currently inside of a special context?
+   */
+  bool is_in_context () const { return !stack.empty (); }
+
+private:
+  /* Actual data */
+  std::vector<T> stack;
+};
+
+} // namespace Rust
+
+#endif /* !RUST_CONTEXT_STACK_H */
-- 
2.38.1