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::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.

1 files changed, 124 insertions, 70 deletions

diff --git a/gcc/rust/expand/rust-macro-builtins.cc b/gcc/rust/expand/rust-macro-builtins.cc
index 11b5d5f..1caba51 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)
 {
@@ -38,35 +48,60 @@ make_string (Location locus, std::string value)
 }
 
 // TODO: Is this correct?
-static std::unique_ptr<AST::Expr>
-make_macro_invocation (AST::BuiltinMacro kind, AST::DelimTokenTree arguments)
+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;
     }
 
-  return AST::MacroInvocation::builtin (
+  std::unique_ptr<AST::Expr> node = AST::MacroInvocation::Builtin (
     kind,
     AST::MacroInvocData (AST::SimplePath (
-			   {AST::SimplePathSegment (path_str, Location ())}),
+			   {AST::SimplePathSegment (path_str, locus)}),
 			 std::move (arguments)),
-    {}, Location ());
+    {}, 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 */
@@ -95,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)
@@ -128,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,
@@ -171,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)
@@ -230,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);
 
@@ -307,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
@@ -317,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
@@ -347,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));
 
@@ -365,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
@@ -393,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
@@ -414,6 +417,20 @@ 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. */
 
@@ -468,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");
@@ -501,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)
 {
@@ -519,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");
@@ -562,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
@@ -597,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
@@ -655,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
@@ -667,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