gccrs: macros: Perform macro expansion in a fixed-point fashion.

This commit changes our macro expansion system from an eager and recursive
macro expansion to a fixed-point like system. Instead of, when seeing
a macro invocation, expanding it and all of the macros within it, we
now perform multiple passes of expansion on the entire crate.

This, however, leads to a problem. Rust macros are expanded lazily, but
Rust builtin macros should be expanded eagerly. Due to this, we must
work around the lazy expansion in builtin macros and perform eager
expansion for each pass of the fixed-point, before finally expanding
the builtin when there are no longer any inner macro invocations.

To perform proper macro scoping, the ENR now keeps track of the current
scope (`current_scope` member) and resolves macros accordingly.

This is done through the use of the `scoped` method, which creates a new
scope, runs a specified lambda and then exits the scope. This prevents
pushing/popping errors that we've seen happen already in similar
contexts.

We might think about generalizing it to other classes, providing a
`Scoped<EntryFn, ExitFn>` class or similar

gcc/rust/ChangeLog:

	* ast/rust-macro.cc: New file.
	* Make-lang.in: Add `rust-macro.o` object
	* ast/rust-ast-fragment.cc (Fragment::Fragment): Change API around
	the construction of AST fragments.
	(Fragment::operator=): Correct `Fragment::operator=` to take into
	account the fragment tokens.
	(Fragment::create_error): Use new constructor.
	(Fragment::complete): Remove in favor of new constructor.
	(Fragment::unexpanded): Remove as that Fragment type is no longer used
	or possible.
	(Fragment::get_tokens): Add helper to access a fragment's tokens.
	* ast/rust-ast-fragment.h (enum class): Remove `FragmentKind::Unused`
	* ast/rust-ast.cc (MacroInvocation::as_string): Display
	builtin macro invocations properly.
	* ast/rust-ast.h: Fix `DelimTokenTree` class copy constructors and
	handling of its token vector.
	* ast/rust-macro.h (class MacroMatcher): Format.
	(class MetaItemSeq): Likewise.
	(builtin_macro_from_string): Get a `BuiltinMacroKind` from a given
	string, i.e the name of the macro (`assert!`, `cfg!` and so on).
	* expand/rust-attribute-visitor.cc (AttrVisitor::visit): Do not expand
	macros recursively anymore.
	(AttrVisitor::maybe_expand_expr): Likewise.
	(AttrVisitor::maybe_expand_type): Likewise.
	* expand/rust-attribute-visitor.h: Likewise, and remove
	`expand_macro_fragment_recursively` function.
	* expand/rust-macro-builtins.cc (make_token): Add shorthand for
	returning `std::unique_ptr<AST::Token>`s.
	(make_macro_invocation): Add shorthand for returning fragments
	containing builtin macro invocations.
	(try_expand_macro_expression): Do not expand macros recursively.
	(try_expand_single_string_literal): Likewise.
	(try_expand_many_expr): Likewise.
	(parse_single_string_literal): Error out more appropriately.
	(MacroBuiltin::compile_error_handler): Add explanation for eager
	invocation
	(MacroBuiltin::file_handler): Return the proper tokens associated with
	macro invocation, and builtin macros in the case of necessary eager
	expansion.
	(MacroBuiltin::column_handler): Likewise.
	(MacroBuiltin::include_bytes_handler): Likewise.
	(MacroBuiltin::include_str_handler): Likewise.
	(MacroBuiltin::concat_handler): Likewise.
	(MacroBuiltin::env_handler): Likewise.
	(MacroBuiltin::cfg_handler): Likewise.
	(MacroBuiltin::include_handler): Likewise.
	(MacroBuiltin::line_handler): Likewise.
	* expand/rust-macro-expand.cc (MacroExpander::expand_eager_invocations):
	Add function to expand eager invocations *once* in the fixed point
	pipeline.
	(MacroExpander::expand_invoc): Call into `expand_eager_invocations` for
	builtin macro invocations.
	(MacroExpander::expand_crate): Use new `AttrVisitor` API.
	(parse_many): Return tokens in `AST::Fragment`.
	(transcribe_expression): Likewise.
	(transcribe_type): Likewise.
	* expand/rust-macro-expand.h (struct MacroExpander): Add `has_changed`
	flag for fixed point checking.
	* resolve/rust-early-name-resolver.cc (EarlyNameResolver::EarlyNameResolver):
	Keep track of the current macro scope.
	(EarlyNameResolver::go): Use `scoped` API.
	(EarlyNameResolver::visit): Likewise.
	* resolve/rust-early-name-resolver.h: Add `scoped` API.
	* rust-session-manager.cc (Session::expansion): Perform macro expansion
	in a fixed-point fashion.

gcc/testsuite/ChangeLog:

	* rust/compile/macro17.rs: Fix testsuite for new recursion errors.
	* rust/compile/macro44.rs: Fix invalid testcase assertions.
	* rust/compile/builtin_macro_recurse.rs: Fix invalid test.
	* rust/compile/builtin_macro_recurse2.rs: New test.
	* rust/compile/macro46.rs: New test.

5 files changed, 360 insertions, 141 deletions

diff --git a/gcc/rust/expand/rust-attribute-visitor.cc b/gcc/rust/expand/rust-attribute-visitor.cc
index 6bceed6..9abec92 100644
--- a/gcc/rust/expand/rust-attribute-visitor.cc
+++ b/gcc/rust/expand/rust-attribute-visitor.cc
@@ -389,8 +389,6 @@ AttrVisitor::visit (AST::ConstGenericParam &)
 void
 AttrVisitor::visit (AST::MacroInvocation &macro_invoc)
 {
-  // FIXME: Probably need to check macro_invoc.kind
-
   // initial strip test based on outer attrs
   expander.expand_cfg_attrs (macro_invoc.get_outer_attrs ());
   if (expander.fails_cfg_with_expand (macro_invoc.get_outer_attrs ()))
@@ -1124,7 +1122,7 @@ AttrVisitor::visit (AST::CallExpr &expr)
 
       stmt->accept_vis (*this);
 
-      auto final_fragment = expand_macro_fragment_recursive ();
+      auto final_fragment = expander.take_expanded_fragment ();
       if (final_fragment.should_expand ())
 	{
 	  // Remove the current expanded invocation
@@ -3423,7 +3421,7 @@ AttrVisitor::visit (AST::BareFunctionType &type)
 void
 AttrVisitor::maybe_expand_expr (std::unique_ptr<AST::Expr> &expr)
 {
-  auto final_fragment = expand_macro_fragment_recursive ();
+  auto final_fragment = expander.take_expanded_fragment ();
   if (final_fragment.should_expand ()
       && final_fragment.is_expression_fragment ())
     expr = final_fragment.take_expression_fragment ();
@@ -3432,7 +3430,7 @@ AttrVisitor::maybe_expand_expr (std::unique_ptr<AST::Expr> &expr)
 void
 AttrVisitor::maybe_expand_type (std::unique_ptr<AST::Type> &type)
 {
-  auto final_fragment = expand_macro_fragment_recursive ();
+  auto final_fragment = expander.take_expanded_fragment ();
   if (final_fragment.should_expand () && final_fragment.is_type_fragment ())
     type = final_fragment.take_type_fragment ();
 }
diff --git a/gcc/rust/expand/rust-attribute-visitor.h b/gcc/rust/expand/rust-attribute-visitor.h
index cbddc16..9b0e315 100644
--- a/gcc/rust/expand/rust-attribute-visitor.h
+++ b/gcc/rust/expand/rust-attribute-visitor.h
@@ -44,39 +44,6 @@ public:
   void expand_trait_method_decl (AST::TraitMethodDecl &decl);
 
   /**
-   * Expand The current macro fragment recursively until it could not be
-   * expanded further.
-   *
-   * The return value checking works because correctly
-   * expanded fragment can never be an error (if the fragment can not be
-   * expanded, a stand-in error fragment will be returned; for fragments that
-   * could not be further expanded: the fragment prior to the expansion failure
-   * will be returned).
-   *
-   * @return Either the expanded fragment or an empty errored-out fragment
-   * indicating an expansion failure.
-   */
-  AST::Fragment expand_macro_fragment_recursive ()
-  {
-    auto fragment = expander.take_expanded_fragment (*this);
-    unsigned int original_depth = expander.expansion_depth;
-    auto final_fragment = AST::Fragment::create_error ();
-
-    while (fragment.should_expand ())
-      {
-	final_fragment = std::move (fragment);
-	expander.expansion_depth++;
-	// further expand the previously expanded macro fragment
-	auto new_fragment = expander.take_expanded_fragment (*this);
-	if (new_fragment.is_error ())
-	  break;
-	fragment = std::move (new_fragment);
-      }
-    expander.expansion_depth = original_depth;
-    return final_fragment;
-  }
-
-  /**
    * Expand a set of values, erasing them if they are marked for strip, and
    * replacing them with expanded macro nodes if necessary.
    * This function is slightly different from `expand_pointer_allow_strip` as
@@ -101,8 +68,7 @@ public:
 	// mark for stripping if required
 	value->accept_vis (*this);
 
-	// recursively expand the children
-	auto final_fragment = expand_macro_fragment_recursive ();
+	auto final_fragment = expander.take_expanded_fragment ();
 
 	if (final_fragment.should_expand ())
 	  {
diff --git a/gcc/rust/expand/rust-macro-builtins.cc b/gcc/rust/expand/rust-macro-builtins.cc
index 1133440..e594a25 100644
--- a/gcc/rust/expand/rust-macro-builtins.cc
+++ b/gcc/rust/expand/rust-macro-builtins.cc
@@ -29,6 +29,16 @@
 
 namespace Rust {
 namespace {
+
+/**
+ * Shorthand function for creating unique_ptr tokens
+ */
+static std::unique_ptr<AST::Token>
+make_token (const TokenPtr tok)
+{
+  return std::unique_ptr<AST::Token> (new AST::Token (tok));
+}
+
 std::unique_ptr<AST::Expr>
 make_string (Location locus, std::string value)
 {
@@ -37,8 +47,64 @@ make_string (Location locus, std::string value)
 			  PrimitiveCoreType::CORETYPE_STR, {}, locus));
 }
 
-/* Match the end token of a macro given the start delimiter of the macro */
+// TODO: Is this correct?
+static AST::Fragment
+make_eager_builtin_invocation (
+  AST::BuiltinMacro kind, Location locus, AST::DelimTokenTree arguments,
+  std::vector<std::unique_ptr<AST::MacroInvocation>> &&pending_invocations)
+{
+  std::string path_str;
 
+  switch (kind)
+    {
+    // TODO: Should this be a table lookup?
+    case AST::BuiltinMacro::Assert:
+      path_str = "assert";
+      break;
+    case AST::BuiltinMacro::File:
+      path_str = "file";
+      break;
+    case AST::BuiltinMacro::Line:
+      path_str = "line";
+      break;
+    case AST::BuiltinMacro::Column:
+      path_str = "column";
+      break;
+    case AST::BuiltinMacro::IncludeBytes:
+      path_str = "include_bytes";
+      break;
+    case AST::BuiltinMacro::IncludeStr:
+      path_str = "include_str";
+      break;
+    case AST::BuiltinMacro::CompileError:
+      path_str = "compile_error";
+      break;
+    case AST::BuiltinMacro::Concat:
+      path_str = "concat";
+      break;
+    case AST::BuiltinMacro::Env:
+      path_str = "env";
+      break;
+    case AST::BuiltinMacro::Cfg:
+      path_str = "cfg";
+      break;
+    case AST::BuiltinMacro::Include:
+      path_str = "include";
+      break;
+    }
+
+  std::unique_ptr<AST::Expr> node = AST::MacroInvocation::Builtin (
+    kind,
+    AST::MacroInvocData (AST::SimplePath (
+			   {AST::SimplePathSegment (path_str, locus)}),
+			 std::move (arguments)),
+    {}, locus, std::move (pending_invocations));
+
+  return AST::Fragment ({AST::SingleASTNode (std::move (node))},
+			arguments.to_token_stream ());
+}
+
+/* Match the end token of a macro given the start delimiter of the macro */
 static inline TokenId
 macro_end_token (AST::DelimTokenTree &invoc_token_tree,
 		 Parser<MacroInvocLexer> &parser)
@@ -64,22 +130,7 @@ macro_end_token (AST::DelimTokenTree &invoc_token_tree,
   return last_token_id;
 }
 
-/* Expand and extract an expression from the macro */
-
-static inline AST::Fragment
-try_expand_macro_expression (AST::Expr *expr, MacroExpander *expander)
-{
-  rust_assert (expander);
-
-  auto attr_visitor = Rust::AttrVisitor (*expander);
-  auto early_name_resolver = Resolver::EarlyNameResolver ();
-  expr->accept_vis (early_name_resolver);
-  expr->accept_vis (attr_visitor);
-  return expander->take_expanded_fragment (attr_visitor);
-}
-
 /* Expand and then extract a string literal from the macro */
-
 static std::unique_ptr<AST::LiteralExpr>
 try_extract_string_literal_from_fragment (const Location &parent_locus,
 					  std::unique_ptr<AST::Expr> &node)
@@ -97,22 +148,6 @@ try_extract_string_literal_from_fragment (const Location &parent_locus,
     static_cast<AST::LiteralExpr *> (node->clone_expr ().release ()));
 }
 
-static std::unique_ptr<AST::LiteralExpr>
-try_expand_single_string_literal (AST::Expr *input_expr,
-				  MacroExpander *expander)
-{
-  auto nodes = try_expand_macro_expression (input_expr, expander);
-  if (nodes.is_error () || nodes.is_expression_fragment ())
-    {
-      rust_error_at (input_expr->get_locus (),
-		     "argument must be a string literal");
-      return nullptr;
-    }
-  auto expr = nodes.take_expression_fragment ();
-  return try_extract_string_literal_from_fragment (input_expr->get_locus (),
-						   expr);
-}
-
 static std::vector<std::unique_ptr<AST::Expr>>
 try_expand_many_expr (Parser<MacroInvocLexer> &parser,
 		      const TokenId last_token_id, MacroExpander *expander,
@@ -140,22 +175,7 @@ try_expand_many_expr (Parser<MacroInvocLexer> &parser,
       auto expr = parser.parse_expr (AST::AttrVec (), restrictions);
       // something must be so wrong that the expression could not be parsed
       rust_assert (expr);
-      auto nodes = try_expand_macro_expression (expr.get (), expander);
-      if (nodes.is_error ())
-	{
-	  // not macro
-	  result.push_back (std::move (expr));
-	}
-      else if (!nodes.is_expression_fragment ())
-	{
-	  rust_error_at (expr->get_locus (), "expected expression");
-	  has_error = true;
-	  return empty_expr;
-	}
-      else
-	{
-	  result.push_back (nodes.take_expression_fragment ());
-	}
+      result.push_back (std::move (expr));
 
       auto next_token = parser.peek_current_token ();
       if (!parser.skip_token (COMMA) && next_token->get_id () != last_token_id)
@@ -199,12 +219,7 @@ parse_single_string_literal (AST::DelimTokenTree &invoc_token_tree,
   else if (parser.peek_current_token ()->get_id () == last_token_id)
     rust_error_at (invoc_locus, "macro takes 1 argument");
   else
-    {
-      // when the expression does not seem to be a string literal, we then try
-      // to parse/expand it as macro to see if it expands to a string literal
-      auto expr = parser.parse_expr ();
-      lit_expr = try_expand_single_string_literal (expr.get (), expander);
-    }
+    rust_error_at (invoc_locus, "argument must be a string literal");
 
   parser.skip_token (last_token_id);
 
@@ -276,8 +291,10 @@ MacroBuiltin::file_handler (Location invoc_locus, AST::MacroInvocData &)
   auto current_file
     = Session::get_instance ().linemap->location_file (invoc_locus);
   auto file_str = AST::SingleASTNode (make_string (invoc_locus, current_file));
+  auto str_token
+    = make_token (Token::make_string (invoc_locus, std::move (current_file)));
 
-  return AST::Fragment::complete ({file_str});
+  return AST::Fragment ({file_str}, std::move (str_token));
 }
 
 AST::Fragment
@@ -286,11 +303,13 @@ MacroBuiltin::column_handler (Location invoc_locus, AST::MacroInvocData &)
   auto current_column
     = Session::get_instance ().linemap->location_to_column (invoc_locus);
 
+  auto column_tok = make_token (
+    Token::make_int (invoc_locus, std::to_string (current_column)));
   auto column_no = AST::SingleASTNode (std::unique_ptr<AST::Expr> (
     new AST::LiteralExpr (std::to_string (current_column), AST::Literal::INT,
 			  PrimitiveCoreType::CORETYPE_U32, {}, invoc_locus)));
 
-  return AST::Fragment::complete ({column_no});
+  return AST::Fragment ({column_no}, std::move (column_tok));
 }
 
 /* Expand builtin macro include_bytes!("filename"), which includes the contents
@@ -316,14 +335,25 @@ MacroBuiltin::include_bytes_handler (Location invoc_locus,
 
   /* Is there a more efficient way to do this?  */
   std::vector<std::unique_ptr<AST::Expr>> elts;
+
+  // We create the tokens for a borrow expression of a byte array, so
+  // & [ <byte0>, <byte1>, ... ]
+  std::vector<std::unique_ptr<AST::Token>> toks;
+  toks.emplace_back (make_token (Token::make (AMP, invoc_locus)));
+  toks.emplace_back (make_token (Token::make (LEFT_SQUARE, invoc_locus)));
+
   for (uint8_t b : bytes)
     {
       elts.emplace_back (
 	new AST::LiteralExpr (std::string (1, (char) b), AST::Literal::BYTE,
 			      PrimitiveCoreType::CORETYPE_U8,
 			      {} /* outer_attrs */, invoc_locus));
+      toks.emplace_back (make_token (Token::make_byte_char (invoc_locus, b)));
+      toks.emplace_back (make_token (Token::make (COMMA, invoc_locus)));
     }
 
+  toks.emplace_back (make_token (Token::make (RIGHT_SQUARE, invoc_locus)));
+
   auto elems = std::unique_ptr<AST::ArrayElems> (
     new AST::ArrayElemsValues (std::move (elts), invoc_locus));
 
@@ -334,8 +364,9 @@ MacroBuiltin::include_bytes_handler (Location invoc_locus,
     new AST::BorrowExpr (std::move (array), false, false, {}, invoc_locus));
 
   auto node = AST::SingleASTNode (std::move (borrow));
-  return AST::Fragment::complete ({node});
-}
+
+  return AST::Fragment ({node}, std::move (toks));
+} // namespace Rust
 
 /* Expand builtin macro include_str!("filename"), which includes the contents
    of the given file as a string. The file must be UTF-8 encoded. Yields an
@@ -362,7 +393,10 @@ MacroBuiltin::include_str_handler (Location invoc_locus,
   std::string str ((const char *) &bytes[0], bytes.size ());
 
   auto node = AST::SingleASTNode (make_string (invoc_locus, str));
-  return AST::Fragment::complete ({node});
+  auto str_tok = make_token (Token::make_string (invoc_locus, std::move (str)));
+
+  // FIXME: Do not return an empty token vector here
+  return AST::Fragment ({node}, std::move (str_tok));
 }
 
 /* Expand builtin macro compile_error!("error"), which forces a compile error
@@ -383,9 +417,62 @@ MacroBuiltin::compile_error_handler (Location invoc_locus,
   return AST::Fragment::create_error ();
 }
 
+static std::vector<std::unique_ptr<AST::MacroInvocation>>
+check_for_eager_invocations (
+  std::vector<std::unique_ptr<AST::Expr>> &expressions)
+{
+  std::vector<std::unique_ptr<AST::MacroInvocation>> pending;
+
+  for (auto &expr : expressions)
+    if (expr->get_ast_kind () == AST::Kind::MACRO_INVOCATION)
+      pending.emplace_back (std::unique_ptr<AST::MacroInvocation> (
+	static_cast<AST::MacroInvocation *> (expr->clone_expr ().release ())));
+
+  return pending;
+}
+
 /* Expand builtin macro concat!(), which joins all the literal parameters
    into a string with no delimiter. */
 
+// This is a weird one. We want to do something where, if something cannot be
+// expanded yet (i.e. macro invocation?) we return the whole MacroInvocation
+// node again but expanded as much as possible.
+// Is that possible? How do we do that?
+//
+// Let's take a few examples:
+//
+// 1. concat!(1, 2, true);
+// 2. concat!(a!(), 2, true);
+// 3. concat!(concat!(1, false), 2, true);
+// 4. concat!(concat!(1, a!()), 2, true);
+//
+// 1. We simply want to return the new fragment: "12true"
+// 2. We want to return `concat!(a_expanded, 2, true)` as a fragment
+// 3. We want to return `concat!(1, false, 2, true)`
+// 4. We want to return `concat!(concat!(1, a_expanded), 2, true);
+//
+// How do we do that?
+//
+// For each (un)expanded fragment: we check if it is expanded fully
+//
+// 1. What is expanded fully?
+// 2. How to check?
+//
+// If it is expanded fully and not a literal, then we error out.
+// Otherwise we simply emplace it back and keep going.
+//
+// In the second case, we must mark that this concat invocation still has some
+// expansion to do: This allows us to return a `MacroInvocation { ... }` as an
+// AST fragment, instead of a completed string.
+//
+// This means that we must change all the `try_expand_many_*` APIs and so on to
+// return some sort of index or way to signify that we might want to reuse some
+// bits and pieces of the original token tree.
+//
+// Now, before that: How do we resolve the names used in a builtin macro
+// invocation?
+// Do we split the two passes of parsing the token tree and then expanding it?
+// Can we do that easily?
 AST::Fragment
 MacroBuiltin::concat_handler (Location invoc_locus, AST::MacroInvocData &invoc)
 {
@@ -398,12 +485,25 @@ MacroBuiltin::concat_handler (Location invoc_locus, AST::MacroInvocData &invoc)
 
   auto last_token_id = macro_end_token (invoc_token_tree, parser);
 
+  auto start = lex.get_offs ();
   /* NOTE: concat! could accept no argument, so we don't have any checks here */
   auto expanded_expr = try_expand_many_expr (parser, last_token_id,
 					     invoc.get_expander (), has_error);
+  auto end = lex.get_offs ();
+
+  auto tokens = lex.get_token_slice (start, end);
+
+  auto pending_invocations = check_for_eager_invocations (expanded_expr);
+  if (!pending_invocations.empty ())
+    return make_eager_builtin_invocation (AST::BuiltinMacro::Concat,
+					  invoc_locus,
+					  invoc.get_delim_tok_tree (),
+					  std::move (pending_invocations));
+
   for (auto &expr : expanded_expr)
     {
-      if (!expr->is_literal ())
+      if (!expr->is_literal ()
+	  && expr->get_ast_kind () != AST::MACRO_INVOCATION)
 	{
 	  has_error = true;
 	  rust_error_at (expr->get_locus (), "expected a literal");
@@ -431,12 +531,13 @@ MacroBuiltin::concat_handler (Location invoc_locus, AST::MacroInvocData &invoc)
     return AST::Fragment::create_error ();
 
   auto node = AST::SingleASTNode (make_string (invoc_locus, str));
-  return AST::Fragment::complete ({node});
+  auto str_tok = make_token (Token::make_string (invoc_locus, std::move (str)));
+
+  return AST::Fragment ({node}, std::move (str_tok));
 }
 
 /* Expand builtin macro env!(), which inspects an environment variable at
    compile time. */
-
 AST::Fragment
 MacroBuiltin::env_handler (Location invoc_locus, AST::MacroInvocData &invoc)
 {
@@ -449,10 +550,22 @@ MacroBuiltin::env_handler (Location invoc_locus, AST::MacroInvocData &invoc)
   std::unique_ptr<AST::LiteralExpr> lit_expr = nullptr;
   bool has_error = false;
 
+  auto start = lex.get_offs ();
   auto expanded_expr = try_expand_many_expr (parser, last_token_id,
 					     invoc.get_expander (), has_error);
+  auto end = lex.get_offs ();
+
+  auto tokens = lex.get_token_slice (start, end);
+
   if (has_error)
     return AST::Fragment::create_error ();
+
+  auto pending = check_for_eager_invocations (expanded_expr);
+  if (!pending.empty ())
+    return make_eager_builtin_invocation (AST::BuiltinMacro::Env, invoc_locus,
+					  invoc_token_tree,
+					  std::move (pending));
+
   if (expanded_expr.size () < 1 || expanded_expr.size () > 2)
     {
       rust_error_at (invoc_locus, "env! takes 1 or 2 arguments");
@@ -492,7 +605,11 @@ MacroBuiltin::env_handler (Location invoc_locus, AST::MacroInvocData &invoc)
     }
 
   auto node = AST::SingleASTNode (make_string (invoc_locus, env_value));
-  return AST::Fragment::complete ({node});
+  auto tok
+    = make_token (Token::make_string (invoc_locus, std::move (env_value)));
+
+  // FIXME: Do not return an empty token vector here
+  return AST::Fragment ({node}, std::move (tok));
 }
 
 AST::Fragment
@@ -527,8 +644,11 @@ MacroBuiltin::cfg_handler (Location invoc_locus, AST::MacroInvocData &invoc)
   auto literal_exp = AST::SingleASTNode (std::unique_ptr<AST::Expr> (
     new AST::LiteralExpr (result ? "true" : "false", AST::Literal::BOOL,
 			  PrimitiveCoreType::CORETYPE_BOOL, {}, invoc_locus)));
+  auto tok = make_token (
+    Token::make (result ? TRUE_LITERAL : FALSE_LITERAL, invoc_locus));
 
-  return AST::Fragment::complete ({literal_exp});
+  // FIXME: Do not return an empty token vector here
+  return AST::Fragment ({literal_exp}, std::move (tok));
 }
 
 /* Expand builtin macro include!(), which includes a source file at the current
@@ -585,7 +705,8 @@ MacroBuiltin::include_handler (Location invoc_locus, AST::MacroInvocData &invoc)
       nodes.push_back (node);
     }
 
-  return AST::Fragment::complete (nodes);
+  // FIXME: Do not return an empty token vector here
+  return AST::Fragment (nodes, nullptr);
 }
 
 AST::Fragment
@@ -597,8 +718,11 @@ MacroBuiltin::line_handler (Location invoc_locus, AST::MacroInvocData &)
   auto line_no = AST::SingleASTNode (std::unique_ptr<AST::Expr> (
     new AST::LiteralExpr (std::to_string (current_line), AST::Literal::INT,
 			  PrimitiveCoreType::CORETYPE_U32, {}, invoc_locus)));
+  auto tok
+    = make_token (Token::make_int (invoc_locus, std::to_string (current_line)));
 
-  return AST::Fragment::complete ({line_no});
+  // FIXME: Do not return an empty token vector here
+  return AST::Fragment ({line_no}, std::move (tok));
 }
 
 } // namespace Rust
diff --git a/gcc/rust/expand/rust-macro-expand.cc b/gcc/rust/expand/rust-macro-expand.cc
index bf914ee..0ff849d 100644
--- a/gcc/rust/expand/rust-macro-expand.cc
+++ b/gcc/rust/expand/rust-macro-expand.cc
@@ -111,6 +111,114 @@ MacroExpander::expand_decl_macro (Location invoc_locus,
 }
 
 void
+MacroExpander::expand_eager_invocations (AST::MacroInvocation &invoc)
+{
+  if (invoc.get_pending_eager_invocations ().empty ())
+    return;
+
+  // We have to basically create a new delimited token tree which contains the
+  // result of one step of expansion. In the case of builtin macros called with
+  // other macro invocations, such as `concat!("h", 'a', a!())`, we need to
+  // expand `a!()` before expanding the concat macro.
+  // This will, ideally, give us a new token tree containing the various
+  // existing tokens + the result of the expansion of a!().
+  // To do this, we "parse" the given token tree to find anything that "looks
+  // like a macro invocation". Then, we get the corresponding macro invocation
+  // from the `pending_eager_invocations` vector and expand it.
+  // Because the `pending_eager_invocations` vector is created in the same order
+  // that the DelimTokenTree is parsed, we know that the first macro invocation
+  // within the DelimTokenTree corresponds to the first element in
+  // `pending_eager_invocations`. The idea is thus to:
+  // 1. Find a macro invocation in the token tree, noting the index of the start
+  //    token and of the end token
+  // 2. Get its associated invocation in `pending_eager_invocations`
+  // 3. Expand that element
+  // 4. Get the token tree associated with that AST fragment
+  // 5. Replace the original tokens corresponding to the invocation with the new
+  //    tokens from the fragment
+  // pseudo-code:
+  //
+  // i = 0;
+  // for tok in dtt:
+  //   if tok is identifier && tok->next() is !:
+  //     start = index(tok);
+  //     l_delim = tok->next()->next();
+  //     tok = skip_until_r_delim();
+  //     end = index(tok);
+  //
+  //     new_tt = expand_eager_invoc(eagers[i++]);
+  //     old_tt[start..end] = new_tt;
+
+  auto dtt = invoc.get_invoc_data ().get_delim_tok_tree ();
+  auto stream = dtt.to_token_stream ();
+  std::vector<std::unique_ptr<AST::TokenTree>> new_stream;
+  size_t current_pending = 0;
+
+  // we need to create a clone of the delimited token tree as the lexer
+  // expects ownership of the tokens
+  std::vector<std::unique_ptr<Rust::AST::Token>> dtt_clone;
+  for (auto &tok : stream)
+    dtt_clone.emplace_back (tok->clone_token ());
+
+  MacroInvocLexer lex (std::move (dtt_clone));
+  Parser<MacroInvocLexer> parser (lex);
+
+  // we want to build a substitution map - basically, associating a `start` and
+  // `end` index for each of the pending macro invocations
+  std::map<std::pair<size_t, size_t>, std::unique_ptr<AST::MacroInvocation> &>
+    substitution_map;
+
+  for (size_t i = 0; i < stream.size (); i++)
+    {
+      // FIXME: Can't these offsets be figure out when we actually parse the
+      // pending_eager_invocation in the first place?
+      auto invocation = parser.parse_macro_invocation ({});
+
+      // if we've managed to parse a macro invocation, we look at the current
+      // offset and store them in the substitution map. Otherwise, we skip one
+      // token and try parsing again
+      if (invocation)
+	substitution_map.insert (
+	  {{i, parser.get_token_source ().get_offs ()},
+	   invoc.get_pending_eager_invocations ()[current_pending++]});
+      else
+	parser.skip_token (stream[i]->get_id ());
+    }
+
+  size_t current_idx = 0;
+  for (auto kv : substitution_map)
+    {
+      auto &to_expand = kv.second;
+      expand_invoc (*to_expand, false);
+
+      auto fragment = take_expanded_fragment ();
+      auto &new_tokens = fragment.get_tokens ();
+
+      auto start = kv.first.first;
+      auto end = kv.first.second;
+
+      // TODO: Add doc
+      for (size_t i = current_idx; i < start; i++)
+	new_stream.emplace_back (stream[i]->clone_token ());
+
+      // TODO: Add doc
+      for (auto &tok : new_tokens)
+	new_stream.emplace_back (tok->clone_token ());
+
+      current_idx = end;
+    }
+  // TODO: Add doc
+  for (size_t i = current_idx; i < stream.size (); i++)
+    new_stream.emplace_back (stream[i]->clone_token ());
+
+  auto new_dtt
+    = AST::DelimTokenTree (dtt.get_delim_type (), std::move (new_stream));
+
+  invoc.get_pending_eager_invocations ().clear ();
+  invoc.get_invoc_data ().set_delim_tok_tree (new_dtt);
+}
+
+void
 MacroExpander::expand_invoc (AST::MacroInvocation &invoc, bool has_semicolon)
 {
   if (depth_exceeds_recursion_limit ())
@@ -119,6 +227,9 @@ MacroExpander::expand_invoc (AST::MacroInvocation &invoc, bool has_semicolon)
       return;
     }
 
+  if (invoc.get_kind () == AST::MacroInvocation::InvocKind::Builtin)
+    expand_eager_invocations (invoc);
+
   AST::MacroInvocData &invoc_data = invoc.get_invoc_data ();
 
   // ??
@@ -151,6 +262,11 @@ MacroExpander::expand_invoc (AST::MacroInvocation &invoc, bool has_semicolon)
   if (!ok)
     return;
 
+  // We store the last expanded invocation and macro definition for error
+  // reporting in case the recursion limit is reached
+  last_invoc = &invoc;
+  last_def = rules_def;
+
   if (rules_def->is_builtin ())
     fragment
       = rules_def->get_builtin_transcriber () (invoc.get_locus (), invoc_data);
@@ -292,7 +408,7 @@ MacroExpander::expand_crate ()
       // mark for stripping if required
       item->accept_vis (attr_visitor);
 
-      auto fragment = take_expanded_fragment (attr_visitor);
+      auto fragment = take_expanded_fragment ();
       if (fragment.should_expand ())
 	{
 	  // Remove the current expanded invocation
@@ -711,6 +827,9 @@ static AST::Fragment
 parse_many (Parser<MacroInvocLexer> &parser, TokenId &delimiter,
 	    std::function<AST::SingleASTNode ()> parse_fn)
 {
+  auto &lexer = parser.get_token_source ();
+  auto start = lexer.get_offs ();
+
   std::vector<AST::SingleASTNode> nodes;
   while (true)
     {
@@ -728,8 +847,9 @@ parse_many (Parser<MacroInvocLexer> &parser, TokenId &delimiter,
 
       nodes.emplace_back (std::move (node));
     }
+  auto end = lexer.get_offs ();
 
-  return AST::Fragment::complete (std::move (nodes));
+  return AST::Fragment (std::move (nodes), lexer.get_token_slice (start, end));
 }
 
 /**
@@ -838,11 +958,16 @@ transcribe_many_stmts (Parser<MacroInvocLexer> &parser, TokenId &delimiter)
 static AST::Fragment
 transcribe_expression (Parser<MacroInvocLexer> &parser)
 {
+  auto &lexer = parser.get_token_source ();
+  auto start = lexer.get_offs ();
+
   auto expr = parser.parse_expr ();
   if (expr == nullptr)
     return AST::Fragment::create_error ();
 
-  return AST::Fragment::complete ({std::move (expr)});
+  auto end = lexer.get_offs ();
+
+  return AST::Fragment ({std::move (expr)}, lexer.get_token_slice (start, end));
 }
 
 /**
@@ -853,11 +978,16 @@ transcribe_expression (Parser<MacroInvocLexer> &parser)
 static AST::Fragment
 transcribe_type (Parser<MacroInvocLexer> &parser)
 {
+  auto &lexer = parser.get_token_source ();
+  auto start = lexer.get_offs ();
+
   auto type = parser.parse_type (true);
   for (auto err : parser.get_errors ())
     err.emit_error ();
 
-  return AST::Fragment::complete ({std::move (type)});
+  auto end = lexer.get_offs ();
+
+  return AST::Fragment ({std::move (type)}, lexer.get_token_slice (start, end));
 }
 
 static AST::Fragment
diff --git a/gcc/rust/expand/rust-macro-expand.h b/gcc/rust/expand/rust-macro-expand.h
index bf761c1..9471416 100644
--- a/gcc/rust/expand/rust-macro-expand.h
+++ b/gcc/rust/expand/rust-macro-expand.h
@@ -231,7 +231,7 @@ struct MacroExpander
     : cfg (cfg), crate (crate), session (session),
       sub_stack (SubstitutionScope ()),
       expanded_fragment (AST::Fragment::create_error ()),
-      resolver (Resolver::Resolver::get ()),
+      has_changed_flag (false), resolver (Resolver::Resolver::get ()),
       mappings (Analysis::Mappings::get ())
   {}
 
@@ -240,6 +240,12 @@ struct MacroExpander
   // Expands all macros in the crate passed in.
   void expand_crate ();
 
+  /**
+   * Expand the eager invocations contained within a builtin macro invocation.
+   * Called by `expand_invoc` when expanding builtin invocations.
+   */
+  void expand_eager_invocations (AST::MacroInvocation &invoc);
+
   /* Expands a macro invocation - possibly make both
    * have similar duck-typed interface and use templates?*/
   // should this be public or private?
@@ -315,49 +321,44 @@ struct MacroExpander
 
   void set_expanded_fragment (AST::Fragment &&fragment)
   {
+    if (!fragment.is_error ())
+      has_changed_flag = true;
+
     expanded_fragment = std::move (fragment);
   }
 
-  AST::Fragment take_expanded_fragment (AST::ASTVisitor &vis)
+  AST::Fragment take_expanded_fragment ()
   {
-    AST::Fragment old_fragment = std::move (expanded_fragment);
-    auto accumulator = std::vector<AST::SingleASTNode> ();
+    auto fragment = std::move (expanded_fragment);
     expanded_fragment = AST::Fragment::create_error ();
-    auto early_name_resolver = Resolver::EarlyNameResolver ();
-
-    for (auto &node : old_fragment.get_nodes ())
-      {
-	expansion_depth++;
-
-	node.accept_vis (early_name_resolver);
-	node.accept_vis (vis);
-	// we'll decide the next move according to the outcome of the macro
-	// expansion
-	if (expanded_fragment.is_error ())
-	  accumulator.push_back (node); // if expansion fails, there might be a
-					// non-macro expression we need to keep
-	else
-	  {
-	    // if expansion succeeded, then we need to merge the fragment with
-	    // the contents in the accumulator, so that our final expansion
-	    // result will contain non-macro nodes as it should
-	    auto new_nodes = expanded_fragment.get_nodes ();
-	    std::move (new_nodes.begin (), new_nodes.end (),
-		       std::back_inserter (accumulator));
-	    expanded_fragment = AST::Fragment::complete (accumulator);
-	  }
-	expansion_depth--;
-      }
-
-    return old_fragment;
+
+    return fragment;
   }
 
+  /**
+   * Has the MacroExpander expanded a macro since its state was last reset?
+   */
+  bool has_changed () const { return has_changed_flag; }
+
+  /**
+   * Reset the expander's "changed" state. This function should be executed at
+   * each iteration in a fixed point loop
+   */
+  void reset_changed_state () { has_changed_flag = false; }
+
+  AST::MacroRulesDefinition *get_last_definition () { return last_def; }
+  AST::MacroInvocation *get_last_invocation () { return last_invoc; }
+
 private:
   AST::Crate &crate;
   Session &session;
   SubstitutionScope sub_stack;
   std::vector<ContextType> context;
   AST::Fragment expanded_fragment;
+  bool has_changed_flag;
+
+  AST::MacroRulesDefinition *last_def;
+  AST::MacroInvocation *last_invoc;
 
 public:
   Resolver::Resolver *resolver;