auto merge of #13088 : thestinger/rust/hashmap, r=cmr

Closes #5283

7 files changed, 92 insertions, 89 deletions

diff --git a/src/libsyntax/abi.rs b/src/libsyntax/abi.rs
index b159920d929..b833eea6b56 100644
--- a/src/libsyntax/abi.rs
+++ b/src/libsyntax/abi.rs
@@ -14,7 +14,7 @@ use std::fmt::Show;
 #[deriving(Eq)]
 pub enum Os { OsWin32, OsMacos, OsLinux, OsAndroid, OsFreebsd, }
 
-#[deriving(Eq, Hash)]
+#[deriving(Eq, TotalEq, Hash)]
 pub enum Abi {
     // NB: This ordering MUST match the AbiDatas array below.
     // (This is ensured by the test indices_are_correct().)
@@ -65,7 +65,7 @@ pub enum AbiArchitecture {
     Archs(u32)  // Multiple architectures (bitset)
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct AbiSet {
     priv bits: u32   // each bit represents one of the abis below
 }
diff --git a/src/libsyntax/ast.rs b/src/libsyntax/ast.rs
index f2a256165e2..24b8a345776 100644
--- a/src/libsyntax/ast.rs
+++ b/src/libsyntax/ast.rs
@@ -113,7 +113,7 @@ impl<D:Decoder> Decodable<D> for Ident {
 /// Function name (not all functions have names)
 pub type FnIdent = Option<Ident>;
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct Lifetime {
     id: NodeId,
     span: Span,
@@ -124,7 +124,7 @@ pub struct Lifetime {
 // for instance: std::cmp::Eq  .  It's represented
 // as a sequence of identifiers, along with a bunch
 // of supporting information.
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct Path {
     span: Span,
     /// A `::foo` path, is relative to the crate root rather than current
@@ -136,7 +136,7 @@ pub struct Path {
 
 /// A segment of a path: an identifier, an optional lifetime, and a set of
 /// types.
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct PathSegment {
     /// The identifier portion of this path segment.
     identifier: Ident,
@@ -170,13 +170,13 @@ pub static DUMMY_NODE_ID: NodeId = -1;
 // typeck::collect::compute_bounds matches these against
 // the "special" built-in traits (see middle::lang_items) and
 // detects Copy, Send and Share.
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum TyParamBound {
     TraitTyParamBound(TraitRef),
     RegionTyParamBound
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct TyParam {
     ident: Ident,
     id: NodeId,
@@ -184,7 +184,7 @@ pub struct TyParam {
     default: Option<P<Ty>>
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct Generics {
     lifetimes: Vec<Lifetime>,
     ty_params: OwnedSlice<TyParam>,
@@ -202,13 +202,13 @@ impl Generics {
     }
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum MethodProvenance {
     FromTrait(DefId),
     FromImpl(DefId),
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum Def {
     DefFn(DefId, Purity),
     DefStaticMethod(/* method */ DefId, MethodProvenance, Purity),
@@ -245,7 +245,7 @@ pub enum Def {
     DefMethod(DefId /* method */, Option<DefId> /* trait */),
 }
 
-#[deriving(Clone, Eq, Hash, Encodable, Decodable, Show)]
+#[deriving(Clone, Eq, TotalEq, Hash, Encodable, Decodable, Show)]
 pub enum DefRegion {
     DefStaticRegion,
     DefEarlyBoundRegion(/* index */ uint, /* lifetime decl */ NodeId),
@@ -257,7 +257,7 @@ pub enum DefRegion {
 // used to drive conditional compilation
 pub type CrateConfig = Vec<@MetaItem> ;
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct Crate {
     module: Mod,
     attrs: Vec<Attribute> ,
@@ -267,7 +267,7 @@ pub struct Crate {
 
 pub type MetaItem = Spanned<MetaItem_>;
 
-#[deriving(Clone, Encodable, Decodable, Hash)]
+#[deriving(Clone, Encodable, Decodable, TotalEq, Hash)]
 pub enum MetaItem_ {
     MetaWord(InternedString),
     MetaList(InternedString, Vec<@MetaItem> ),
@@ -299,7 +299,7 @@ impl Eq for MetaItem_ {
     }
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct Block {
     view_items: Vec<ViewItem> ,
     stmts: Vec<@Stmt> ,
@@ -309,26 +309,26 @@ pub struct Block {
     span: Span,
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct Pat {
     id: NodeId,
     node: Pat_,
     span: Span,
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct FieldPat {
     ident: Ident,
     pat: @Pat,
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum BindingMode {
     BindByRef(Mutability),
     BindByValue(Mutability),
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum Pat_ {
     PatWild,
     PatWildMulti,
@@ -353,13 +353,13 @@ pub enum Pat_ {
     PatVec(Vec<@Pat> , Option<@Pat>, Vec<@Pat> )
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash, Show)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash, Show)]
 pub enum Mutability {
     MutMutable,
     MutImmutable,
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum Sigil {
     BorrowedSigil,
     OwnedSigil,
@@ -376,14 +376,14 @@ impl fmt::Show for Sigil {
     }
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum ExprVstore {
     ExprVstoreUniq,                 // ~[1,2,3,4]
     ExprVstoreSlice,                // &[1,2,3,4]
     ExprVstoreMutSlice,             // &mut [1,2,3,4]
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum BinOp {
     BiAdd,
     BiSub,
@@ -405,7 +405,7 @@ pub enum BinOp {
     BiGt,
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum UnOp {
     UnBox,
     UnUniq,
@@ -416,7 +416,7 @@ pub enum UnOp {
 
 pub type Stmt = Spanned<Stmt_>;
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum Stmt_ {
     // could be an item or a local (let) binding:
     StmtDecl(@Decl, NodeId),
@@ -434,7 +434,7 @@ pub enum Stmt_ {
 // FIXME (pending discussion of #1697, #2178...): local should really be
 // a refinement on pat.
 /// Local represents a `let` statement, e.g., `let <pat>:<ty> = <expr>;`
-#[deriving(Eq, Encodable, Decodable, Hash)]
+#[deriving(Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct Local {
     ty: P<Ty>,
     pat: @Pat,
@@ -445,7 +445,7 @@ pub struct Local {
 
 pub type Decl = Spanned<Decl_>;
 
-#[deriving(Eq, Encodable, Decodable, Hash)]
+#[deriving(Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum Decl_ {
     // a local (let) binding:
     DeclLocal(@Local),
@@ -453,14 +453,14 @@ pub enum Decl_ {
     DeclItem(@Item),
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct Arm {
     pats: Vec<@Pat> ,
     guard: Option<@Expr>,
     body: @Expr,
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct Field {
     ident: SpannedIdent,
     expr: @Expr,
@@ -469,26 +469,26 @@ pub struct Field {
 
 pub type SpannedIdent = Spanned<Ident>;
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum BlockCheckMode {
     DefaultBlock,
     UnsafeBlock(UnsafeSource),
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum UnsafeSource {
     CompilerGenerated,
     UserProvided,
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct Expr {
     id: NodeId,
     node: Expr_,
     span: Span,
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum Expr_ {
     ExprVstore(@Expr, ExprVstore),
     // First expr is the place; second expr is the value.
@@ -557,7 +557,7 @@ pub enum Expr_ {
 // else knows what to do with them, so you'll probably get a syntax
 // error.
 //
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 #[doc="For macro invocations; parsing is delegated to the macro"]
 pub enum TokenTree {
     // a single token
@@ -631,7 +631,7 @@ pub enum TokenTree {
 //
 pub type Matcher = Spanned<Matcher_>;
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum Matcher_ {
     // match one token
     MatchTok(::parse::token::Token),
@@ -648,12 +648,12 @@ pub type Mac = Spanned<Mac_>;
 // is being invoked, and the vector of token-trees contains the source
 // of the macro invocation.
 // There's only one flavor, now, so this could presumably be simplified.
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum Mac_ {
     MacInvocTT(Path, Vec<TokenTree> , SyntaxContext),   // new macro-invocation
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum StrStyle {
     CookedStr,
     RawStr(uint)
@@ -661,7 +661,7 @@ pub enum StrStyle {
 
 pub type Lit = Spanned<Lit_>;
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum Lit_ {
     LitStr(InternedString, StrStyle),
     LitBinary(Rc<Vec<u8> >),
@@ -677,20 +677,20 @@ pub enum Lit_ {
 
 // NB: If you change this, you'll probably want to change the corresponding
 // type structure in middle/ty.rs as well.
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct MutTy {
     ty: P<Ty>,
     mutbl: Mutability,
 }
 
-#[deriving(Eq, Encodable, Decodable, Hash)]
+#[deriving(Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct TypeField {
     ident: Ident,
     mt: MutTy,
     span: Span,
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct TypeMethod {
     ident: Ident,
     attrs: Vec<Attribute> ,
@@ -705,13 +705,13 @@ pub struct TypeMethod {
 // A trait method is either required (meaning it doesn't have an
 // implementation, just a signature) or provided (meaning it has a default
 // implementation).
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum TraitMethod {
     Required(TypeMethod),
     Provided(@Method),
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum IntTy {
     TyI,
     TyI8,
@@ -726,7 +726,7 @@ impl fmt::Show for IntTy {
     }
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum UintTy {
     TyU,
     TyU8,
@@ -741,7 +741,7 @@ impl fmt::Show for UintTy {
     }
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum FloatTy {
     TyF32,
     TyF64,
@@ -754,7 +754,7 @@ impl fmt::Show for FloatTy {
 }
 
 // NB Eq method appears below.
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct Ty {
     id: NodeId,
     node: Ty_,
@@ -762,7 +762,7 @@ pub struct Ty {
 }
 
 // Not represented directly in the AST, referred to by name through a ty_path.
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum PrimTy {
     TyInt(IntTy),
     TyUint(UintTy),
@@ -772,7 +772,7 @@ pub enum PrimTy {
     TyChar
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum Onceness {
     Once,
     Many
@@ -787,7 +787,7 @@ impl fmt::Show for Onceness {
     }
 }
 
-#[deriving(Eq, Encodable, Decodable, Hash)]
+#[deriving(Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct ClosureTy {
     sigil: Sigil,
     region: Option<Lifetime>,
@@ -802,7 +802,7 @@ pub struct ClosureTy {
     bounds: Option<OwnedSlice<TyParamBound>>,
 }
 
-#[deriving(Eq, Encodable, Decodable, Hash)]
+#[deriving(Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct BareFnTy {
     purity: Purity,
     abis: AbiSet,
@@ -810,7 +810,7 @@ pub struct BareFnTy {
     decl: P<FnDecl>
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum Ty_ {
     TyNil,
     TyBot, /* bottom type */
@@ -830,13 +830,13 @@ pub enum Ty_ {
     TyInfer,
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum AsmDialect {
     AsmAtt,
     AsmIntel
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct InlineAsm {
     asm: InternedString,
     asm_str_style: StrStyle,
@@ -848,7 +848,7 @@ pub struct InlineAsm {
     dialect: AsmDialect
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct Arg {
     ty: P<Ty>,
     pat: @Pat,
@@ -875,7 +875,7 @@ impl Arg {
     }
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct FnDecl {
     inputs: Vec<Arg> ,
     output: P<Ty>,
@@ -883,7 +883,7 @@ pub struct FnDecl {
     variadic: bool
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum Purity {
     UnsafeFn, // declared with "unsafe fn"
     ImpureFn, // declared with "fn"
@@ -900,14 +900,14 @@ impl fmt::Show for Purity {
     }
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum RetStyle {
     NoReturn, // functions with return type _|_ that always
               // raise an error or exit (i.e. never return to the caller)
     Return, // everything else
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum ExplicitSelf_ {
     SelfStatic,                                // no self
     SelfValue,                                 // `self`
@@ -917,7 +917,7 @@ pub enum ExplicitSelf_ {
 
 pub type ExplicitSelf = Spanned<ExplicitSelf_>;
 
-#[deriving(Eq, Encodable, Decodable, Hash)]
+#[deriving(Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct Method {
     ident: Ident,
     attrs: Vec<Attribute> ,
@@ -931,37 +931,37 @@ pub struct Method {
     vis: Visibility,
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct Mod {
     view_items: Vec<ViewItem> ,
     items: Vec<@Item> ,
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct ForeignMod {
     abis: AbiSet,
     view_items: Vec<ViewItem> ,
     items: Vec<@ForeignItem> ,
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct VariantArg {
     ty: P<Ty>,
     id: NodeId,
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum VariantKind {
     TupleVariantKind(Vec<VariantArg> ),
     StructVariantKind(@StructDef),
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct EnumDef {
     variants: Vec<P<Variant>> ,
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct Variant_ {
     name: Ident,
     attrs: Vec<Attribute> ,
@@ -973,7 +973,7 @@ pub struct Variant_ {
 
 pub type Variant = Spanned<Variant_>;
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct PathListIdent_ {
     name: Ident,
     id: NodeId,
@@ -983,7 +983,7 @@ pub type PathListIdent = Spanned<PathListIdent_>;
 
 pub type ViewPath = Spanned<ViewPath_>;
 
-#[deriving(Eq, Encodable, Decodable, Hash)]
+#[deriving(Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum ViewPath_ {
 
     // quux = foo::bar::baz
@@ -1000,7 +1000,7 @@ pub enum ViewPath_ {
     ViewPathList(Path, Vec<PathListIdent> , NodeId)
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct ViewItem {
     node: ViewItem_,
     attrs: Vec<Attribute> ,
@@ -1008,7 +1008,7 @@ pub struct ViewItem {
     span: Span,
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum ViewItem_ {
     // ident: name used to refer to this crate in the code
     // optional (InternedString,StrStyle): if present, this is a location
@@ -1024,14 +1024,14 @@ pub type Attribute = Spanned<Attribute_>;
 // Distinguishes between Attributes that decorate items and Attributes that
 // are contained as statements within items. These two cases need to be
 // distinguished for pretty-printing.
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum AttrStyle {
     AttrOuter,
     AttrInner,
 }
 
 // doc-comments are promoted to attributes that have is_sugared_doc = true
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct Attribute_ {
     style: AttrStyle,
     value: @MetaItem,
@@ -1045,13 +1045,13 @@ pub struct Attribute_ {
   If this impl is an ItemImpl, the impl_id is redundant (it could be the
   same as the impl's node id).
  */
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct TraitRef {
     path: Path,
     ref_id: NodeId,
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum Visibility {
     Public,
     Private,
@@ -1067,7 +1067,7 @@ impl Visibility {
     }
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct StructField_ {
     kind: StructFieldKind,
     id: NodeId,
@@ -1077,13 +1077,13 @@ pub struct StructField_ {
 
 pub type StructField = Spanned<StructField_>;
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum StructFieldKind {
     NamedField(Ident, Visibility),
     UnnamedField // element of a tuple-like struct
 }
 
-#[deriving(Eq, Encodable, Decodable, Hash)]
+#[deriving(Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct StructDef {
     fields: Vec<StructField> , /* fields, not including ctor */
     /* ID of the constructor. This is only used for tuple- or enum-like
@@ -1095,7 +1095,7 @@ pub struct StructDef {
   FIXME (#3300): Should allow items to be anonymous. Right now
   we just use dummy names for anon items.
  */
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct Item {
     ident: Ident,
     attrs: Vec<Attribute> ,
@@ -1105,7 +1105,7 @@ pub struct Item {
     span: Span,
 }
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum Item_ {
     ItemStatic(P<Ty>, Mutability, @Expr),
     ItemFn(P<FnDecl>, Purity, AbiSet, Generics, P<Block>),
@@ -1123,7 +1123,7 @@ pub enum Item_ {
     ItemMac(Mac),
 }
 
-#[deriving(Eq, Encodable, Decodable, Hash)]
+#[deriving(Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct ForeignItem {
     ident: Ident,
     attrs: Vec<Attribute> ,
@@ -1133,7 +1133,7 @@ pub struct ForeignItem {
     vis: Visibility,
 }
 
-#[deriving(Eq, Encodable, Decodable, Hash)]
+#[deriving(Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum ForeignItem_ {
     ForeignItemFn(P<FnDecl>, Generics),
     ForeignItemStatic(P<Ty>, /* is_mutbl */ bool),
@@ -1142,7 +1142,7 @@ pub enum ForeignItem_ {
 // The data we save and restore about an inlined item or method.  This is not
 // part of the AST that we parse from a file, but it becomes part of the tree
 // that we trans.
-#[deriving(Eq, Encodable, Decodable, Hash)]
+#[deriving(Eq, TotalEq, Encodable, Decodable, Hash)]
 pub enum InlinedItem {
     IIItem(@Item),
     IIMethod(DefId /* impl id */, bool /* is provided */, @Method),
diff --git a/src/libsyntax/codemap.rs b/src/libsyntax/codemap.rs
index 4ba7921c431..325df5fda60 100644
--- a/src/libsyntax/codemap.rs
+++ b/src/libsyntax/codemap.rs
@@ -22,7 +22,6 @@ source code snippets, etc.
 */
 
 use std::cell::RefCell;
-use std::cmp;
 use std::rc::Rc;
 use serialize::{Encodable, Decodable, Encoder, Decoder};
 
@@ -33,7 +32,7 @@ pub trait Pos {
 
 /// A byte offset. Keep this small (currently 32-bits), as AST contains
 /// a lot of them.
-#[deriving(Clone, Eq, Hash, Ord, Show)]
+#[deriving(Clone, Eq, TotalEq, Hash, Ord, Show)]
 pub struct BytePos(u32);
 
 /// A character offset. Because of multibyte utf8 characters, a byte offset
@@ -94,19 +93,21 @@ pub struct Span {
 
 pub static DUMMY_SP: Span = Span { lo: BytePos(0), hi: BytePos(0), expn_info: None };
 
-#[deriving(Clone, Eq, Encodable, Decodable, Hash)]
+#[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
 pub struct Spanned<T> {
     node: T,
     span: Span,
 }
 
-impl cmp::Eq for Span {
+impl Eq for Span {
     fn eq(&self, other: &Span) -> bool {
         return (*self).lo == (*other).lo && (*self).hi == (*other).hi;
     }
     fn ne(&self, other: &Span) -> bool { !(*self).eq(other) }
 }
 
+impl TotalEq for Span {}
+
 impl<S:Encoder> Encodable<S> for Span {
     /* Note #1972 -- spans are encoded but not decoded */
     fn encode(&self, s: &mut S) {
diff --git a/src/libsyntax/owned_slice.rs b/src/libsyntax/owned_slice.rs
index df38945f198..d5b90821897 100644
--- a/src/libsyntax/owned_slice.rs
+++ b/src/libsyntax/owned_slice.rs
@@ -119,6 +119,8 @@ impl<T: Eq> Eq for OwnedSlice<T> {
     }
 }
 
+impl<T: TotalEq> TotalEq for OwnedSlice<T> {}
+
 impl<T> Container for OwnedSlice<T> {
     fn len(&self) -> uint { self.len }
 }
diff --git a/src/libsyntax/parse/obsolete.rs b/src/libsyntax/parse/obsolete.rs
index 1d7bf2ef6da..63b3fb09ee3 100644
--- a/src/libsyntax/parse/obsolete.rs
+++ b/src/libsyntax/parse/obsolete.rs
@@ -23,7 +23,7 @@ use parse::parser::Parser;
 use parse::token;
 
 /// The specific types of unsupported syntax
-#[deriving(Eq, Hash)]
+#[deriving(Eq, TotalEq, Hash)]
 pub enum ObsoleteSyntax {
     ObsoleteSwap,
     ObsoleteUnsafeBlock,
diff --git a/src/libsyntax/parse/token.rs b/src/libsyntax/parse/token.rs
index eebb98294d5..15525912955 100644
--- a/src/libsyntax/parse/token.rs
+++ b/src/libsyntax/parse/token.rs
@@ -24,7 +24,7 @@ use std::local_data;
 use std::path::BytesContainer;
 
 #[allow(non_camel_case_types)]
-#[deriving(Clone, Encodable, Decodable, Eq, Hash, Show)]
+#[deriving(Clone, Encodable, Decodable, Eq, TotalEq, Hash, Show)]
 pub enum BinOp {
     PLUS,
     MINUS,
@@ -39,7 +39,7 @@ pub enum BinOp {
 }
 
 #[allow(non_camel_case_types)]
-#[deriving(Clone, Encodable, Decodable, Eq, Hash, Show)]
+#[deriving(Clone, Encodable, Decodable, Eq, TotalEq, Hash, Show)]
 pub enum Token {
     /* Expression-operator symbols. */
     EQ,
@@ -103,7 +103,7 @@ pub enum Token {
     EOF,
 }
 
-#[deriving(Clone, Encodable, Decodable, Eq, Hash)]
+#[deriving(Clone, Encodable, Decodable, Eq, TotalEq, Hash)]
 /// For interpolation during macro expansion.
 pub enum Nonterminal {
     NtItem(@ast::Item),
diff --git a/src/libsyntax/util/interner.rs b/src/libsyntax/util/interner.rs
index d6f8f1067ae..9b73cf533a7 100644
--- a/src/libsyntax/util/interner.rs
+++ b/src/libsyntax/util/interner.rs
@@ -28,7 +28,7 @@ pub struct Interner<T> {
 }
 
 // when traits can extend traits, we should extend index<Name,T> to get []
-impl<T: Eq + Hash + Clone + 'static> Interner<T> {
+impl<T: TotalEq + Hash + Clone + 'static> Interner<T> {
     pub fn new() -> Interner<T> {
         Interner {
             map: RefCell::new(HashMap::new()),