parser: Add parsing of auto traits

This adds enough handling to start parsing `auto` traits but not handle
them in the AST, lowering phase or HIR yet.

The feature is named `optin_builtin_traits` in Rust 1.49 but changes to
`auto_traits` later down the line. So we'll need to take care of this later
on.

Finally, this also changes the way the lexer detects if a string is a
keyword or not. We relied on a call to `std::lower_bound` to figure
out if a string was contained in an array or not, and this ended up
causing issues when adding new keywords. We can instead switch to a
simple hashmap and search for the key. The code *might* be less
optimized (unsure) but it is definitely simpler and easier to read.

Fixes #1814

gcc/rust/ChangeLog:

	* ast/rust-item.h (class Trait): Add `has_auto` field.
	* checks/errors/rust-feature.cc: Add handling for `feature(optin_builtin_traits)`
	* checks/errors/rust-feature.h: Likewise.
	* lex/rust-lex.cc: Fix keyword classification using hashmap.
	* lex/rust-token.h: Add `auto` keyword token.
	* parse/rust-parse-impl.h (Parser::parse_vis_item): Parse auto traits
	on `auto` keyword.

gcc/testsuite/ChangeLog:

	* rust/compile/auto_trait_invalid.rs: New test.
	* rust/compile/auto_trait_valid.rs: New test.

8 files changed, 78 insertions, 29 deletions

diff --git a/gcc/rust/ast/rust-item.h b/gcc/rust/ast/rust-item.h
index 1620961..f66a8c5 100644
--- a/gcc/rust/ast/rust-item.h
+++ b/gcc/rust/ast/rust-item.h
@@ -3399,6 +3399,7 @@ protected:
 class Trait : public VisItem
 {
   bool has_unsafe;
+  bool has_auto;
   Identifier name;
   std::vector<std::unique_ptr<GenericParam>> generic_params;
   std::vector<std::unique_ptr<TypeParamBound>> type_param_bounds;
@@ -3428,9 +3429,10 @@ public:
   Identifier get_identifier () const { return name; }
 
   bool is_unsafe () const { return has_unsafe; }
+  bool is_auto () const { return has_auto; }
 
   // Mega-constructor
-  Trait (Identifier name, bool is_unsafe,
+  Trait (Identifier name, bool is_unsafe, bool is_auto,
 	 std::vector<std::unique_ptr<GenericParam>> generic_params,
 	 std::vector<std::unique_ptr<TypeParamBound>> type_param_bounds,
 	 WhereClause where_clause,
@@ -3438,7 +3440,7 @@ public:
 	 std::vector<Attribute> outer_attrs, std::vector<Attribute> inner_attrs,
 	 Location locus)
     : VisItem (std::move (vis), std::move (outer_attrs)),
-      has_unsafe (is_unsafe), name (std::move (name)),
+      has_unsafe (is_unsafe), has_auto (is_auto), name (std::move (name)),
       generic_params (std::move (generic_params)),
       type_param_bounds (std::move (type_param_bounds)),
       where_clause (std::move (where_clause)),
@@ -3448,9 +3450,9 @@ public:
 
   // Copy constructor with vector clone
   Trait (Trait const &other)
-    : VisItem (other), has_unsafe (other.has_unsafe), name (other.name),
-      where_clause (other.where_clause), inner_attrs (other.inner_attrs),
-      locus (other.locus)
+    : VisItem (other), has_unsafe (other.has_unsafe), has_auto (other.has_auto),
+      name (other.name), where_clause (other.where_clause),
+      inner_attrs (other.inner_attrs), locus (other.locus)
   {
     generic_params.reserve (other.generic_params.size ());
     for (const auto &e : other.generic_params)
@@ -3471,6 +3473,7 @@ public:
     VisItem::operator= (other);
     name = other.name;
     has_unsafe = other.has_unsafe;
+    has_auto = other.has_auto;
     where_clause = other.where_clause;
     inner_attrs = other.inner_attrs;
     locus = other.locus;
diff --git a/gcc/rust/checks/errors/rust-feature.cc b/gcc/rust/checks/errors/rust-feature.cc
index 81689d9..ceae2aa 100644
--- a/gcc/rust/checks/errors/rust-feature.cc
+++ b/gcc/rust/checks/errors/rust-feature.cc
@@ -53,7 +53,10 @@ const std::map<std::string, Feature::Name> Feature::name_hash_map = {
   {"intrinsics", Feature::Name::INTRINSICS},
   {"rustc_attrs", Feature::Name::RUSTC_ATTRS},
   {"decl_macro", Feature::Name::DECL_MACRO},
-};
+  // TODO: Rename to "auto_traits" when supporting
+  // later Rust versions
+  {"optin_builtin_traits", Feature::Name::AUTO_TRAITS},
+}; // namespace Rust
 
 Optional<Feature::Name>
 Feature::as_name (const std::string &name)
diff --git a/gcc/rust/checks/errors/rust-feature.h b/gcc/rust/checks/errors/rust-feature.h
index 7bd76c0..1f580a0 100644
--- a/gcc/rust/checks/errors/rust-feature.h
+++ b/gcc/rust/checks/errors/rust-feature.h
@@ -41,6 +41,7 @@ public:
     INTRINSICS,
     RUSTC_ATTRS,
     DECL_MACRO,
+    AUTO_TRAITS,
   };
 
   const std::string &as_string () { return m_name_str; }
diff --git a/gcc/rust/lex/rust-lex.cc b/gcc/rust/lex/rust-lex.cc
index 9967cec..d80ce9a 100644
--- a/gcc/rust/lex/rust-lex.cc
+++ b/gcc/rust/lex/rust-lex.cc
@@ -240,23 +240,13 @@ Lexer::replace_current_token (TokenPtr replacement)
  * created with x-macros. */
 namespace {
 // TODO: make constexpr when update to c++20
-const std::string keyword_index[] = {
+const std::map<std::string, TokenId> keywords = {
 #define RS_TOKEN(x, y)
-#define RS_TOKEN_KEYWORD(name, keyword) keyword,
+#define RS_TOKEN_KEYWORD(tok, key) {key, tok},
   RS_TOKEN_LIST
 #undef RS_TOKEN_KEYWORD
 #undef RS_TOKEN
 };
-
-constexpr TokenId keyword_keys[] = {
-#define RS_TOKEN(x, y)
-#define RS_TOKEN_KEYWORD(name, keyword) name,
-  RS_TOKEN_LIST
-#undef RS_TOKEN_KEYWORD
-#undef RS_TOKEN
-};
-
-constexpr int num_keywords = sizeof (keyword_index) / sizeof (*keyword_index);
 } // namespace
 
 /* Determines whether the string passed in is a keyword or not. If it is, it
@@ -264,21 +254,18 @@ constexpr int num_keywords = sizeof (keyword_index) / sizeof (*keyword_index);
 TokenId
 Lexer::classify_keyword (const std::string &str)
 {
-  const std::string *last = keyword_index + num_keywords;
-  const std::string *idx = std::lower_bound (keyword_index, last, str);
+  auto keyword = keywords.find (str);
+  auto id = keyword->second;
 
-  if (idx == last || str != *idx)
+  if (keyword == keywords.end ())
     return IDENTIFIER;
 
-  // TODO: possibly replace this x-macro system with something like hash map?
-
   // We now have the expected token ID of the reserved keyword. However, some
   // keywords are reserved starting in certain editions. For example, `try` is
   // only a reserved keyword in editions >=2018. The language might gain new
   // reserved keywords in the future.
   //
   // https://doc.rust-lang.org/reference/keywords.html#reserved-keywords
-  auto id = keyword_keys[idx - keyword_index];
 
   // `try` is not a reserved keyword before 2018
   if (Session::get_instance ().options.get_edition ()
diff --git a/gcc/rust/lex/rust-token.h b/gcc/rust/lex/rust-token.h
index 0fc55a2..f00d9cf 100644
--- a/gcc/rust/lex/rust-token.h
+++ b/gcc/rust/lex/rust-token.h
@@ -149,7 +149,8 @@ enum PrimitiveCoreType
   /* have "weak" union and 'static keywords? */                                \
   RS_TOKEN_KEYWORD (ABSTRACT, "abstract") /* unused */                         \
   RS_TOKEN_KEYWORD (AS, "as")                                                  \
-  RS_TOKEN_KEYWORD (ASYNC, "async")   /* unused */                             \
+  RS_TOKEN_KEYWORD (ASYNC, "async") /* unused */                               \
+  RS_TOKEN_KEYWORD (AUTO, "auto")                                              \
   RS_TOKEN_KEYWORD (BECOME, "become") /* unused */                             \
   RS_TOKEN_KEYWORD (BOX, "box")	      /* unused */                             \
   RS_TOKEN_KEYWORD (BREAK, "break")                                            \
diff --git a/gcc/rust/parse/rust-parse-impl.h b/gcc/rust/parse/rust-parse-impl.h
index 2cb5e3e..0841db4 100644
--- a/gcc/rust/parse/rust-parse-impl.h
+++ b/gcc/rust/parse/rust-parse-impl.h
@@ -1057,6 +1057,7 @@ Parser<ManagedTokenSource>::parse_item (bool called_from_statement)
     case ENUM_TOK:
     case CONST:
     case STATIC_TOK:
+    case AUTO:
     case TRAIT:
     case IMPL:
     case MACRO:
@@ -1304,6 +1305,7 @@ Parser<ManagedTokenSource>::parse_vis_item (AST::AttrVec outer_attrs)
 	}
     case STATIC_TOK:
       return parse_static_item (std::move (vis), std::move (outer_attrs));
+    case AUTO:
     case TRAIT:
       return parse_trait (std::move (vis), std::move (outer_attrs));
     case IMPL:
@@ -1314,6 +1316,7 @@ Parser<ManagedTokenSource>::parse_vis_item (AST::AttrVec outer_attrs)
 
       switch (t->get_id ())
 	{
+	case AUTO:
 	case TRAIT:
 	  return parse_trait (std::move (vis), std::move (outer_attrs));
 	case EXTERN_TOK:
@@ -2034,6 +2037,7 @@ Parser<ManagedTokenSource>::parse_macro_match ()
 	  case STATIC_TOK:
 	  case STRUCT_TOK:
 	  case SUPER:
+	  case AUTO:
 	  case TRAIT:
 	  case TRUE_LITERAL:
 	  case TRY:
@@ -4753,12 +4757,20 @@ Parser<ManagedTokenSource>::parse_trait (AST::Visibility vis,
 {
   Location locus = lexer.peek_token ()->get_locus ();
   bool is_unsafe = false;
+  bool is_auto_trait = false;
+
   if (lexer.peek_token ()->get_id () == UNSAFE)
     {
       is_unsafe = true;
       lexer.skip_token ();
     }
 
+  if (lexer.peek_token ()->get_id () == AUTO)
+    {
+      is_auto_trait = true;
+      lexer.skip_token ();
+    }
+
   skip_token (TRAIT);
 
   // parse trait name
@@ -4824,12 +4836,25 @@ Parser<ManagedTokenSource>::parse_trait (AST::Visibility vis,
       return nullptr;
     }
 
+  if (is_auto_trait && !trait_items.empty ())
+    {
+      add_error (
+	Error (locus, "associated items are forbidden within auto traits"));
+
+      // FIXME: unsure if this should be done at parsing time or not
+      for (const auto &item : trait_items)
+	add_error (Error::Hint (item->get_locus (), "remove this item"));
+
+      return nullptr;
+    }
+
   trait_items.shrink_to_fit ();
   return std::unique_ptr<AST::Trait> (
-    new AST::Trait (std::move (ident), is_unsafe, std::move (generic_params),
-		    std::move (type_param_bounds), std::move (where_clause),
-		    std::move (trait_items), std::move (vis),
-		    std::move (outer_attrs), std::move (inner_attrs), locus));
+    new AST::Trait (std::move (ident), is_unsafe, is_auto_trait,
+		    std::move (generic_params), std::move (type_param_bounds),
+		    std::move (where_clause), std::move (trait_items),
+		    std::move (vis), std::move (outer_attrs),
+		    std::move (inner_attrs), locus));
 }
 
 // Parses a trait item used inside traits (not trait, the Item).
@@ -6120,6 +6145,7 @@ Parser<ManagedTokenSource>::parse_stmt (ParseRestrictions restrictions)
     case ENUM_TOK:
     case CONST:
     case STATIC_TOK:
+    case AUTO:
     case TRAIT:
     case IMPL:
     case MACRO:
@@ -11769,6 +11795,7 @@ Parser<ManagedTokenSource>::parse_stmt_or_expr_without_block ()
     case ENUM_TOK:
     case CONST:
     case STATIC_TOK:
+    case AUTO:
     case TRAIT:
       case IMPL: {
 	std::unique_ptr<AST::VisItem> item (
@@ -11790,6 +11817,7 @@ Parser<ManagedTokenSource>::parse_stmt_or_expr_without_block ()
 	      // unsafe block
 	      return parse_stmt_or_expr_with_block (std::move (outer_attrs));
 	    }
+	  case AUTO:
 	    case TRAIT: {
 	      // unsafe trait
 	      std::unique_ptr<AST::VisItem> item (
diff --git a/gcc/testsuite/rust/compile/auto_trait_invalid.rs b/gcc/testsuite/rust/compile/auto_trait_invalid.rs
new file mode 100644
index 0000000..16dca57
--- /dev/null
+++ b/gcc/testsuite/rust/compile/auto_trait_invalid.rs
@@ -0,0 +1,16 @@
+// #![feature(auto_traits)] // not present in Rust 1.49 yet
+
+#![feature(optin_builtin_traits)]
+
+unsafe auto trait Invalid { // { dg-error "associated items are forbidden within auto traits" }
+    fn foo(); // { dg-message "remove this item" }
+
+    fn bar() {} // { dg-message "remove this item" }
+
+    type Foo; // { dg-message "remove this item" }
+
+    const FOO: i32; // { dg-message "remove this item" }
+
+    const BAR: i32 = 15; // { dg-message "remove this item" }
+}
+// { dg-error "failed to parse item in crate" "" {target *-*-* } .+1 }
diff --git a/gcc/testsuite/rust/compile/auto_trait_valid.rs b/gcc/testsuite/rust/compile/auto_trait_valid.rs
new file mode 100644
index 0000000..0fdab7f
--- /dev/null
+++ b/gcc/testsuite/rust/compile/auto_trait_valid.rs
@@ -0,0 +1,10 @@
+// #![feature(auto_traits)] // not present in Rust 1.49 yet
+
+#![feature(optin_builtin_traits)]
+
+auto trait MegaSend {}
+pub auto trait MegaSync {}
+unsafe auto trait SuperSync {}
+pub unsafe auto trait SuperSend {}
+
+fn main() {}