Auto merge of #30652 - aturon:specialization, r=nikomatsakis

Implement RFC 1210: impl specialization

This PR implements [impl specialization](https://github.com/rust-lang/rfcs/pull/1210),
carefully following the proposal laid out in the RFC.

The implementation covers the bulk of the RFC. The remaining gaps I know of are:

- no checking for lifetime-dependent specialization (a soundness hole);
- no `default impl` yet;
- no support for `default` with associated consts;

I plan to cover these gaps in follow-up PRs, as per @nikomatsakis's preference.

The basic strategy is to build up a *specialization graph* during
coherence checking. Insertion into the graph locates the right place
to put an impl in the specialization hierarchy; if there is no right
place (due to partial overlap but no containment), you get an overlap
error. Specialization is consulted when selecting an impl (of course),
and the graph is consulted when propagating defaults down the
specialization hierarchy.

You might expect that the specialization graph would be used during
selection -- i.e., when actually performing specialization. This is
not done for two reasons:

- It's merely an optimization: given a set of candidates that apply,
  we can determine the most specialized one by comparing them directly
  for specialization, rather than consulting the graph. Given that we
  also cache the results of selection, the benefit of this
  optimization is questionable.

- To build the specialization graph in the first place, we need to use
  selection (because we need to determine whether one impl specializes
  another). Dealing with this reentrancy would require some additional
  mode switch for selection. Given that there seems to be no strong
  reason to use the graph anyway, we stick with a simpler approach in
  selection, and use the graph only for propagating default
  implementations.

Trait impl selection can succeed even when multiple impls can apply,
as long as they are part of the same specialization family. In that
case, it returns a *single* impl on success -- this is the most
specialized impl *known* to apply. However, if there are any inference
variables in play, the returned impl may not be the actual impl we
will use at trans time. Thus, we take special care to avoid projecting
associated types unless either (1) the associated type does not use
`default` and thus cannot be overridden or (2) all input types are
known concretely.

r? @nikomatsakis

7 files changed, 109 insertions, 55 deletions

diff --git a/src/libsyntax/ast.rs b/src/libsyntax/ast.rs
index f7621b0131a..c830fed5db9 100644
--- a/src/libsyntax/ast.rs
+++ b/src/libsyntax/ast.rs
@@ -1328,10 +1328,10 @@ pub struct MethodSig {
     pub explicit_self: ExplicitSelf,
 }
 
-/// Represents a method declaration in a trait declaration, possibly including
-/// a default implementation. A trait method is either required (meaning it
-/// doesn't have an implementation, just a signature) or provided (meaning it
-/// has a default implementation).
+/// Represents an item declaration within a trait declaration,
+/// possibly including a default implementation. A trait item is
+/// either required (meaning it doesn't have an implementation, just a
+/// signature) or provided (meaning it has a default implementation).
 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 pub struct TraitItem {
     pub id: NodeId,
@@ -1353,6 +1353,7 @@ pub struct ImplItem {
     pub id: NodeId,
     pub ident: Ident,
     pub vis: Visibility,
+    pub defaultness: Defaultness,
     pub attrs: Vec<Attribute>,
     pub node: ImplItemKind,
     pub span: Span,
@@ -1654,6 +1655,12 @@ pub enum Constness {
     NotConst,
 }
 
+#[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
+pub enum Defaultness {
+    Default,
+    Final,
+}
+
 impl fmt::Display for Unsafety {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         fmt::Display::fmt(match *self {
diff --git a/src/libsyntax/ext/expand.rs b/src/libsyntax/ext/expand.rs
index f5794f7219b..5bfdab791d6 100644
--- a/src/libsyntax/ext/expand.rs
+++ b/src/libsyntax/ext/expand.rs
@@ -1061,6 +1061,7 @@ fn expand_impl_item(ii: ast::ImplItem, fld: &mut MacroExpander)
             ident: ii.ident,
             attrs: ii.attrs,
             vis: ii.vis,
+            defaultness: ii.defaultness,
             node: match ii.node  {
                 ast::ImplItemKind::Method(sig, body) => {
                     let (sig, body) = expand_and_rename_method(sig, body, fld);
diff --git a/src/libsyntax/feature_gate.rs b/src/libsyntax/feature_gate.rs
index 14a3f93738a..fbaf28332c4 100644
--- a/src/libsyntax/feature_gate.rs
+++ b/src/libsyntax/feature_gate.rs
@@ -247,7 +247,10 @@ const KNOWN_FEATURES: &'static [(&'static str, &'static str, Option<u32>, Status
     ("inclusive_range_syntax", "1.7.0", Some(28237), Active),
 
     // `expr?`
-    ("question_mark", "1.9.0", Some(31436), Active)
+    ("question_mark", "1.9.0", Some(31436), Active),
+
+    // impl specialization (RFC 1210)
+    ("specialization", "1.7.0", Some(31844), Active),
 ];
 // (changing above list without updating src/doc/reference.md makes @cmr sad)
 
@@ -574,6 +577,7 @@ pub struct Features {
     pub stmt_expr_attributes: bool,
     pub deprecated: bool,
     pub question_mark: bool,
+    pub specialization: bool,
 }
 
 impl Features {
@@ -608,6 +612,7 @@ impl Features {
             stmt_expr_attributes: false,
             deprecated: false,
             question_mark: false,
+            specialization: false,
         }
     }
 }
@@ -1102,6 +1107,12 @@ impl<'a, 'v> Visitor<'v> for PostExpansionVisitor<'a> {
     }
 
     fn visit_impl_item(&mut self, ii: &'v ast::ImplItem) {
+        if ii.defaultness == ast::Defaultness::Default {
+            self.gate_feature("specialization",
+                              ii.span,
+                              "specialization is unstable");
+        }
+
         match ii.node {
             ast::ImplItemKind::Const(..) => {
                 self.gate_feature("associated_consts",
@@ -1212,6 +1223,7 @@ fn check_crate_inner<F>(cm: &CodeMap, span_handler: &Handler,
         stmt_expr_attributes: cx.has_feature("stmt_expr_attributes"),
         deprecated: cx.has_feature("deprecated"),
         question_mark: cx.has_feature("question_mark"),
+        specialization: cx.has_feature("specialization"),
     }
 }
 
diff --git a/src/libsyntax/fold.rs b/src/libsyntax/fold.rs
index 9056103d300..cd8998a211a 100644
--- a/src/libsyntax/fold.rs
+++ b/src/libsyntax/fold.rs
@@ -993,6 +993,7 @@ pub fn noop_fold_impl_item<T: Folder>(i: ImplItem, folder: &mut T)
         ident: folder.fold_ident(i.ident),
         attrs: fold_attrs(i.attrs, folder),
         vis: i.vis,
+        defaultness: i.defaultness,
         node: match i.node  {
             ast::ImplItemKind::Const(ty, expr) => {
                 ast::ImplItemKind::Const(folder.fold_ty(ty), folder.fold_expr(expr))
diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs
index 5884be40150..6839f11cd70 100644
--- a/src/libsyntax/parse/parser.rs
+++ b/src/libsyntax/parse/parser.rs
@@ -18,7 +18,7 @@ use ast::{Mod, Arg, Arm, Attribute, BindingMode, TraitItemKind};
 use ast::Block;
 use ast::{BlockCheckMode, CaptureBy};
 use ast::{Constness, Crate, CrateConfig};
-use ast::{Decl, DeclKind};
+use ast::{Decl, DeclKind, Defaultness};
 use ast::{EMPTY_CTXT, EnumDef, ExplicitSelf};
 use ast::{Expr, ExprKind, RangeLimits};
 use ast::{Field, FnDecl};
@@ -644,6 +644,25 @@ impl<'a> Parser<'a> {
         }
     }
 
+    pub fn check_contextual_keyword(&mut self, ident: Ident) -> bool {
+        let tok = token::Ident(ident, token::Plain);
+        self.expected_tokens.push(TokenType::Token(tok));
+        if let token::Ident(ref cur_ident, _) = self.token {
+            cur_ident.name == ident.name
+        } else {
+            false
+        }
+    }
+
+    pub fn eat_contextual_keyword(&mut self, ident: Ident) -> bool {
+        if self.check_contextual_keyword(ident) {
+            self.bump();
+            true
+        } else {
+            false
+        }
+    }
+
     /// If the given word is not a keyword, signal an error.
     /// If the next token is not the given word, signal an error.
     /// Otherwise, eat it.
@@ -705,7 +724,6 @@ impl<'a> Parser<'a> {
         }
     }
 
-
     /// Attempt to consume a `<`. If `<<` is seen, replace it with a single
     /// `<` and continue. If a `<` is not seen, return false.
     ///
@@ -4846,6 +4864,7 @@ impl<'a> Parser<'a> {
         let mut attrs = try!(self.parse_outer_attributes());
         let lo = self.span.lo;
         let vis = try!(self.parse_visibility());
+        let defaultness = try!(self.parse_defaultness());
         let (name, node) = if self.eat_keyword(keywords::Type) {
             let name = try!(self.parse_ident());
             try!(self.expect(&token::Eq));
@@ -4872,6 +4891,7 @@ impl<'a> Parser<'a> {
             span: mk_sp(lo, self.last_span.hi),
             ident: name,
             vis: vis,
+            defaultness: defaultness,
             attrs: attrs,
             node: node
         })
@@ -5208,6 +5228,15 @@ impl<'a> Parser<'a> {
         else { Ok(Visibility::Inherited) }
     }
 
+    /// Parse defaultness: DEFAULT or nothing
+    fn parse_defaultness(&mut self) -> PResult<'a, Defaultness> {
+        if self.eat_contextual_keyword(special_idents::DEFAULT) {
+            Ok(Defaultness::Default)
+        } else {
+            Ok(Defaultness::Final)
+        }
+    }
+
     /// Given a termination token, parse all of the items in a module
     fn parse_mod_items(&mut self, term: &token::Token, inner_lo: BytePos) -> PResult<'a, Mod> {
         let mut items = vec![];
diff --git a/src/libsyntax/parse/token.rs b/src/libsyntax/parse/token.rs
index 294cbf35895..033ac9440bc 100644
--- a/src/libsyntax/parse/token.rs
+++ b/src/libsyntax/parse/token.rs
@@ -545,66 +545,67 @@ declare_special_idents_and_keywords! {
         (9,                          __unused1,              "<__unused1>");
         (super::SELF_TYPE_KEYWORD_NAME_NUM, type_self,       "Self");
         (11,                         prelude_import,         "prelude_import");
+        (12,                         DEFAULT,                "default");
     }
 
     pub mod keywords {
         // These ones are variants of the Keyword enum
 
         'strict:
-        (12,                         As,         "as");
-        (13,                         Break,      "break");
-        (14,                         Crate,      "crate");
-        (15,                         Else,       "else");
-        (16,                         Enum,       "enum");
-        (17,                         Extern,     "extern");
-        (18,                         False,      "false");
-        (19,                         Fn,         "fn");
-        (20,                         For,        "for");
-        (21,                         If,         "if");
-        (22,                         Impl,       "impl");
-        (23,                         In,         "in");
-        (24,                         Let,        "let");
-        (25,                         Loop,       "loop");
-        (26,                         Match,      "match");
-        (27,                         Mod,        "mod");
-        (28,                         Move,       "move");
-        (29,                         Mut,        "mut");
-        (30,                         Pub,        "pub");
-        (31,                         Ref,        "ref");
-        (32,                         Return,     "return");
+        (13,                         As,         "as");
+        (14,                         Break,      "break");
+        (15,                         Crate,      "crate");
+        (16,                         Else,       "else");
+        (17,                         Enum,       "enum");
+        (18,                         Extern,     "extern");
+        (19,                         False,      "false");
+        (20,                         Fn,         "fn");
+        (21,                         For,        "for");
+        (22,                         If,         "if");
+        (23,                         Impl,       "impl");
+        (24,                         In,         "in");
+        (25,                         Let,        "let");
+        (26,                         Loop,       "loop");
+        (27,                         Match,      "match");
+        (28,                         Mod,        "mod");
+        (29,                         Move,       "move");
+        (30,                         Mut,        "mut");
+        (31,                         Pub,        "pub");
+        (32,                         Ref,        "ref");
+        (33,                         Return,     "return");
         // Static and Self are also special idents (prefill de-dupes)
         (super::STATIC_KEYWORD_NAME_NUM, Static, "static");
         (super::SELF_KEYWORD_NAME_NUM, SelfValue, "self");
         (super::SELF_TYPE_KEYWORD_NAME_NUM, SelfType, "Self");
-        (33,                         Struct,     "struct");
+        (34,                         Struct,     "struct");
         (super::SUPER_KEYWORD_NAME_NUM, Super,   "super");
-        (34,                         True,       "true");
-        (35,                         Trait,      "trait");
-        (36,                         Type,       "type");
-        (37,                         Unsafe,     "unsafe");
-        (38,                         Use,        "use");
-        (39,                         While,      "while");
-        (40,                         Continue,   "continue");
-        (41,                         Box,        "box");
-        (42,                         Const,      "const");
-        (43,                         Where,      "where");
+        (35,                         True,       "true");
+        (36,                         Trait,      "trait");
+        (37,                         Type,       "type");
+        (38,                         Unsafe,     "unsafe");
+        (39,                         Use,        "use");
+        (40,                         While,      "while");
+        (41,                         Continue,   "continue");
+        (42,                         Box,        "box");
+        (43,                         Const,      "const");
+        (44,                         Where,      "where");
         'reserved:
-        (44,                         Virtual,    "virtual");
-        (45,                         Proc,       "proc");
-        (46,                         Alignof,    "alignof");
-        (47,                         Become,     "become");
-        (48,                         Offsetof,   "offsetof");
-        (49,                         Priv,       "priv");
-        (50,                         Pure,       "pure");
-        (51,                         Sizeof,     "sizeof");
-        (52,                         Typeof,     "typeof");
-        (53,                         Unsized,    "unsized");
-        (54,                         Yield,      "yield");
-        (55,                         Do,         "do");
-        (56,                         Abstract,   "abstract");
-        (57,                         Final,      "final");
-        (58,                         Override,   "override");
-        (59,                         Macro,      "macro");
+        (45,                         Virtual,    "virtual");
+        (46,                         Proc,       "proc");
+        (47,                         Alignof,    "alignof");
+        (48,                         Become,     "become");
+        (49,                         Offsetof,   "offsetof");
+        (50,                         Priv,       "priv");
+        (51,                         Pure,       "pure");
+        (52,                         Sizeof,     "sizeof");
+        (53,                         Typeof,     "typeof");
+        (54,                         Unsized,    "unsized");
+        (55,                         Yield,      "yield");
+        (56,                         Do,         "do");
+        (57,                         Abstract,   "abstract");
+        (58,                         Final,      "final");
+        (59,                         Override,   "override");
+        (60,                         Macro,      "macro");
     }
 }
 
diff --git a/src/libsyntax/print/pprust.rs b/src/libsyntax/print/pprust.rs
index 2cfed1f82f7..533487ae1c5 100644
--- a/src/libsyntax/print/pprust.rs
+++ b/src/libsyntax/print/pprust.rs
@@ -1582,6 +1582,9 @@ impl<'a> State<'a> {
         try!(self.hardbreak_if_not_bol());
         try!(self.maybe_print_comment(ii.span.lo));
         try!(self.print_outer_attributes(&ii.attrs));
+        if let ast::Defaultness::Default = ii.defaultness {
+            try!(self.word_nbsp("default"));
+        }
         match ii.node {
             ast::ImplItemKind::Const(ref ty, ref expr) => {
                 try!(self.print_associated_const(ii.ident, &ty, Some(&expr), ii.vis));