src/librustc_back/svh.rs

   1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! Calculation and management of a Strict Version Hash for crates
  12 //!
  13 //! # Today's ABI problem
  14 //!
  15 //! In today's implementation of rustc, it is incredibly difficult to achieve
  16 //! forward binary compatibility without resorting to C-like interfaces. Within
  17 //! rust code itself, abi details such as symbol names suffer from a variety of
  18 //! unrelated factors to code changing such as the "def id drift" problem. This
  19 //! ends up yielding confusing error messages about metadata mismatches and
  20 //! such.
  21 //!
  22 //! The core of this problem is when an upstream dependency changes and
  23 //! downstream dependents are not recompiled. This causes compile errors because
  24 //! the upstream crate's metadata has changed but the downstream crates are
  25 //! still referencing the older crate's metadata.
  26 //!
  27 //! This problem exists for many reasons, the primary of which is that rust does
  28 //! not currently support forwards ABI compatibility (in place upgrades of a
  29 //! crate).
  30 //!
  31 //! # SVH and how it alleviates the problem
  32 //!
  33 //! With all of this knowledge on hand, this module contains the implementation
  34 //! of a notion of a "Strict Version Hash" for a crate. This is essentially a
  35 //! hash of all contents of a crate which can somehow be exposed to downstream
  36 //! crates.
  37 //!
  38 //! This hash is currently calculated by just hashing the AST, but this is
  39 //! obviously wrong (doc changes should not result in an incompatible ABI).
  40 //! Implementation-wise, this is required at this moment in time.
  41 //!
  42 //! By encoding this strict version hash into all crate's metadata, stale crates
  43 //! can be detected immediately and error'd about by rustc itself.
  44 //!
  45 //! # Relevant links
  46 //!
  47 //! Original issue: https://github.com/rust-lang/rust/issues/10207
  48
  49 use std::fmt;
  50 use std::hash::{Hash, SipHasher, Hasher};
  51 use std::iter::range_step;
  52 use syntax::ast;
  53 use syntax::visit;
  54
  55 #[derive(Clone, PartialEq)]
  56 pub struct Svh {
  57     hash: String,
  58 }
  59
  60 impl Svh {
  61     pub fn new(hash: &str) -> Svh {
  62         assert!(hash.len() == 16);
  63         Svh { hash: hash.to_string() }
  64     }
  65
  66     pub fn as_str<'a>(&'a self) -> &'a str {
  67         &self.hash[]
  68     }
  69
  70     pub fn calculate(metadata: &Vec<String>, krate: &ast::Crate) -> Svh {
  71         // FIXME (#14132): This is better than it used to be, but it still not
  72         // ideal. We now attempt to hash only the relevant portions of the
  73         // Crate AST as well as the top-level crate attributes. (However,
  74         // the hashing of the crate attributes should be double-checked
  75         // to ensure it is not incorporating implementation artifacts into
  76         // the hash that are not otherwise visible.)
  77
  78         // FIXME: this should use SHA1, not SipHash. SipHash is not built to
  79         //        avoid collisions.
  80         let mut state = SipHasher::new();
  81
  82         for data in metadata.iter() {
  83             data.hash(&mut state);
  84         }
  85
  86         {
  87             let mut visit = svh_visitor::make(&mut state);
  88             visit::walk_crate(&mut visit, krate);
  89         }
  90
  91         // FIXME (#14132): This hash is still sensitive to e.g. the
  92         // spans of the crate Attributes and their underlying
  93         // MetaItems; we should make ContentHashable impl for those
  94         // types and then use hash_content.  But, since all crate
  95         // attributes should appear near beginning of the file, it is
  96         // not such a big deal to be sensitive to their spans for now.
  97         //
  98         // We hash only the MetaItems instead of the entire Attribute
  99         // to avoid hashing the AttrId
 100         for attr in krate.attrs.iter() {
 101             attr.node.value.hash(&mut state);
 102         }
 103
 104         let hash = state.finish();
 105         return Svh {
 106             hash: range_step(0u, 64u, 4u).map(|i| hex(hash >> i)).collect()
 107         };
 108
 109         fn hex(b: u64) -> char {
 110             let b = (b & 0xf) as u8;
 111             let b = match b {
 112                 0 ... 9 => '0' as u8 + b,
 113                 _ => 'a' as u8 + b - 10,
 114             };
 115             b as char
 116         }
 117     }
 118 }
 119
 120 impl fmt::Show for Svh {
 121     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 122         write!(f, "Svh {{ {} }}", self.as_str())
 123     }
 124 }
 125
 126 impl fmt::String for Svh {
 127     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 128         f.pad(self.as_str())
 129     }
 130 }
 131
 132 // FIXME (#14132): Even this SVH computation still has implementation
 133 // artifacts: namely, the order of item declaration will affect the
 134 // hash computation, but for many kinds of items the order of
 135 // declaration should be irrelevant to the ABI.
 136
 137 mod svh_visitor {
 138     pub use self::SawExprComponent::*;
 139     pub use self::SawStmtComponent::*;
 140     use self::SawAbiComponent::*;
 141     use syntax::ast;
 142     use syntax::ast::*;
 143     use syntax::codemap::Span;
 144     use syntax::parse::token;
 145     use syntax::print::pprust;
 146     use syntax::visit;
 147     use syntax::visit::{Visitor, FnKind};
 148
 149     use std::hash::{Hash, SipHasher};
 150
 151     pub struct StrictVersionHashVisitor<'a> {
 152         pub st: &'a mut SipHasher,
 153     }
 154
 155     pub fn make<'a>(st: &'a mut SipHasher) -> StrictVersionHashVisitor<'a> {
 156         StrictVersionHashVisitor { st: st }
 157     }
 158
 159     // To off-load the bulk of the hash-computation on #[derive(Hash)],
 160     // we define a set of enums corresponding to the content that our
 161     // crate visitor will encounter as it traverses the ast.
 162     //
 163     // The important invariant is that all of the Saw*Component enums
 164     // do not carry any Spans, Names, or Idents.
 165     //
 166     // Not carrying any Names/Idents is the important fix for problem
 167     // noted on PR #13948: using the ident.name as the basis for a
 168     // hash leads to unstable SVH, because ident.name is just an index
 169     // into intern table (i.e. essentially a random address), not
 170     // computed from the name content.
 171     //
 172     // With the below enums, the SVH computation is not sensitive to
 173     // artifacts of how rustc was invoked nor of how the source code
 174     // was laid out.  (Or at least it is *less* sensitive.)
 175
 176     // This enum represents the different potential bits of code the
 177     // visitor could encounter that could affect the ABI for the crate,
 178     // and assigns each a distinct tag to feed into the hash computation.
 179     #[derive(Hash)]
 180     enum SawAbiComponent<'a> {
 181
 182         // FIXME (#14132): should we include (some function of)
 183         // ident.ctxt as well?
 184         SawIdent(token::InternedString),
 185         SawStructDef(token::InternedString),
 186
 187         SawLifetimeRef(token::InternedString),
 188         SawLifetimeDef(token::InternedString),
 189
 190         SawMod,
 191         SawViewItem,
 192         SawForeignItem,
 193         SawItem,
 194         SawDecl,
 195         SawTy,
 196         SawGenerics,
 197         SawFn,
 198         SawTyMethod,
 199         SawTraitMethod,
 200         SawStructField,
 201         SawVariant,
 202         SawExplicitSelf,
 203         SawPath,
 204         SawOptLifetimeRef,
 205         SawBlock,
 206         SawPat,
 207         SawLocal,
 208         SawArm,
 209         SawExpr(SawExprComponent<'a>),
 210         SawStmt(SawStmtComponent),
 211     }
 212
 213     /// SawExprComponent carries all of the information that we want
 214     /// to include in the hash that *won't* be covered by the
 215     /// subsequent recursive traversal of the expression's
 216     /// substructure by the visitor.
 217     ///
 218     /// We know every Expr_ variant is covered by a variant because
 219     /// `fn saw_expr` maps each to some case below.  Ensuring that
 220     /// each variant carries an appropriate payload has to be verified
 221     /// by hand.
 222     ///
 223     /// (However, getting that *exactly* right is not so important
 224     /// because the SVH is just a developer convenience; there is no
 225     /// guarantee of collision-freedom, hash collisions are just
 226     /// (hopefully) unlikely.)
 227     #[derive(Hash)]
 228     pub enum SawExprComponent<'a> {
 229
 230         SawExprLoop(Option<token::InternedString>),
 231         SawExprField(token::InternedString),
 232         SawExprTupField(uint),
 233         SawExprBreak(Option<token::InternedString>),
 234         SawExprAgain(Option<token::InternedString>),
 235
 236         SawExprBox,
 237         SawExprVec,
 238         SawExprCall,
 239         SawExprMethodCall,
 240         SawExprTup,
 241         SawExprBinary(ast::BinOp),
 242         SawExprUnary(ast::UnOp),
 243         SawExprLit(ast::Lit_),
 244         SawExprCast,
 245         SawExprIf,
 246         SawExprWhile,
 247         SawExprMatch,
 248         SawExprClosure,
 249         SawExprBlock,
 250         SawExprAssign,
 251         SawExprAssignOp(ast::BinOp),
 252         SawExprIndex,
 253         SawExprRange,
 254         SawExprPath,
 255         SawExprQPath,
 256         SawExprAddrOf(ast::Mutability),
 257         SawExprRet,
 258         SawExprInlineAsm(&'a ast::InlineAsm),
 259         SawExprStruct,
 260         SawExprRepeat,
 261         SawExprParen,
 262         SawExprForLoop,
 263     }
 264
 265     fn saw_expr<'a>(node: &'a Expr_) -> SawExprComponent<'a> {
 266         match *node {
 267             ExprBox(..)              => SawExprBox,
 268             ExprVec(..)              => SawExprVec,
 269             ExprCall(..)             => SawExprCall,
 270             ExprMethodCall(..)       => SawExprMethodCall,
 271             ExprTup(..)              => SawExprTup,
 272             ExprBinary(op, _, _)     => SawExprBinary(op),
 273             ExprUnary(op, _)         => SawExprUnary(op),
 274             ExprLit(ref lit)         => SawExprLit(lit.node.clone()),
 275             ExprCast(..)             => SawExprCast,
 276             ExprIf(..)               => SawExprIf,
 277             ExprWhile(..)            => SawExprWhile,
 278             ExprLoop(_, id)          => SawExprLoop(id.map(content)),
 279             ExprMatch(..)            => SawExprMatch,
 280             ExprClosure(..)          => SawExprClosure,
 281             ExprBlock(..)            => SawExprBlock,
 282             ExprAssign(..)           => SawExprAssign,
 283             ExprAssignOp(op, _, _)   => SawExprAssignOp(op),
 284             ExprField(_, id)         => SawExprField(content(id.node)),
 285             ExprTupField(_, id)      => SawExprTupField(id.node),
 286             ExprIndex(..)            => SawExprIndex,
 287             ExprRange(..)            => SawExprRange,
 288             ExprPath(..)             => SawExprPath,
 289             ExprQPath(..)            => SawExprQPath,
 290             ExprAddrOf(m, _)         => SawExprAddrOf(m),
 291             ExprBreak(id)            => SawExprBreak(id.map(content)),
 292             ExprAgain(id)            => SawExprAgain(id.map(content)),
 293             ExprRet(..)              => SawExprRet,
 294             ExprInlineAsm(ref asm)   => SawExprInlineAsm(asm),
 295             ExprStruct(..)           => SawExprStruct,
 296             ExprRepeat(..)           => SawExprRepeat,
 297             ExprParen(..)            => SawExprParen,
 298             ExprForLoop(..)          => SawExprForLoop,
 299
 300             // just syntactic artifacts, expanded away by time of SVH.
 301             ExprIfLet(..)            => unreachable!(),
 302             ExprWhileLet(..)         => unreachable!(),
 303             ExprMac(..)              => unreachable!(),
 304         }
 305     }
 306
 307     /// SawStmtComponent is analogous to SawExprComponent, but for statements.
 308     #[derive(Hash)]
 309     pub enum SawStmtComponent {
 310         SawStmtDecl,
 311         SawStmtExpr,
 312         SawStmtSemi,
 313     }
 314
 315     fn saw_stmt(node: &Stmt_) -> SawStmtComponent {
 316         match *node {
 317             StmtDecl(..) => SawStmtDecl,
 318             StmtExpr(..) => SawStmtExpr,
 319             StmtSemi(..) => SawStmtSemi,
 320             StmtMac(..)  => unreachable!(),
 321         }
 322     }
 323
 324     // Ad-hoc overloading between Ident and Name to their intern table lookups.
 325     trait InternKey { fn get_content(self) -> token::InternedString; }
 326     impl InternKey for Ident {
 327         fn get_content(self) -> token::InternedString { token::get_ident(self) }
 328     }
 329     impl InternKey for Name {
 330         fn get_content(self) -> token::InternedString { token::get_name(self) }
 331     }
 332     fn content<K:InternKey>(k: K) -> token::InternedString { k.get_content() }
 333
 334     impl<'a, 'v> Visitor<'v> for StrictVersionHashVisitor<'a> {
 335
 336         fn visit_mac(&mut self, mac: &Mac) {
 337             // macro invocations, namely macro_rules definitions,
 338             // *can* appear as items, even in the expanded crate AST.
 339
 340             if macro_name(mac).get() == "macro_rules" {
 341                 // Pretty-printing definition to a string strips out
 342                 // surface artifacts (currently), such as the span
 343                 // information, yielding a content-based hash.
 344
 345                 // FIXME (#14132): building temporary string is
 346                 // expensive; a direct content-based hash on token
 347                 // trees might be faster. Implementing this is far
 348                 // easier in short term.
 349                 let macro_defn_as_string = pprust::to_string(|pp_state| {
 350                     pp_state.print_mac(mac, token::Paren)
 351                 });
 352                 macro_defn_as_string.hash(self.st);
 353             } else {
 354                 // It is not possible to observe any kind of macro
 355                 // invocation at this stage except `macro_rules!`.
 356                 panic!("reached macro somehow: {}",
 357                       pprust::to_string(|pp_state| {
 358                           pp_state.print_mac(mac, token::Paren)
 359                       }));
 360             }
 361
 362             visit::walk_mac(self, mac);
 363
 364             fn macro_name(mac: &Mac) -> token::InternedString {
 365                 match &mac.node {
 366                     &MacInvocTT(ref path, ref _tts, ref _stx_ctxt) => {
 367                         let s = &path.segments[];
 368                         assert_eq!(s.len(), 1);
 369                         content(s[0].identifier)
 370                     }
 371                 }
 372             }
 373         }
 374
 375         fn visit_struct_def(&mut self, s: &StructDef, ident: Ident,
 376                             g: &Generics, _: NodeId) {
 377             SawStructDef(content(ident)).hash(self.st);
 378             visit::walk_generics(self, g);
 379             visit::walk_struct_def(self, s)
 380         }
 381
 382         fn visit_variant(&mut self, v: &Variant, g: &Generics) {
 383             SawVariant.hash(self.st);
 384             // walk_variant does not call walk_generics, so do it here.
 385             visit::walk_generics(self, g);
 386             visit::walk_variant(self, v, g)
 387         }
 388
 389         fn visit_opt_lifetime_ref(&mut self, _: Span, l: &Option<Lifetime>) {
 390             SawOptLifetimeRef.hash(self.st);
 391             // (This is a strange method in the visitor trait, in that
 392             // it does not expose a walk function to do the subroutine
 393             // calls.)
 394             match *l {
 395                 Some(ref l) => self.visit_lifetime_ref(l),
 396                 None => ()
 397             }
 398         }
 399
 400         // All of the remaining methods just record (in the hash
 401         // SipHasher) that the visitor saw that particular variant
 402         // (with its payload), and continue walking as the default
 403         // visitor would.
 404         //
 405         // Some of the implementations have some notes as to how one
 406         // might try to make their SVH computation less discerning
 407         // (e.g. by incorporating reachability analysis).  But
 408         // currently all of their implementations are uniform and
 409         // uninteresting.
 410         //
 411         // (If you edit a method such that it deviates from the
 412         // pattern, please move that method up above this comment.)
 413
 414         fn visit_ident(&mut self, _: Span, ident: Ident) {
 415             SawIdent(content(ident)).hash(self.st);
 416         }
 417
 418         fn visit_lifetime_ref(&mut self, l: &Lifetime) {
 419             SawLifetimeRef(content(l.name)).hash(self.st);
 420         }
 421
 422         fn visit_lifetime_def(&mut self, l: &LifetimeDef) {
 423             SawLifetimeDef(content(l.lifetime.name)).hash(self.st);
 424         }
 425
 426         // We do recursively walk the bodies of functions/methods
 427         // (rather than omitting their bodies from the hash) since
 428         // monomorphization and cross-crate inlining generally implies
 429         // that a change to a crate body will require downstream
 430         // crates to be recompiled.
 431         fn visit_expr(&mut self, ex: &Expr) {
 432             SawExpr(saw_expr(&ex.node)).hash(self.st); visit::walk_expr(self, ex)
 433         }
 434
 435         fn visit_stmt(&mut self, s: &Stmt) {
 436             SawStmt(saw_stmt(&s.node)).hash(self.st); visit::walk_stmt(self, s)
 437         }
 438
 439         fn visit_view_item(&mut self, i: &ViewItem) {
 440             // Two kinds of view items can affect the ABI for a crate:
 441             // exported `pub use` view items (since that may expose
 442             // items that downstream crates can call), and `use
 443             // foo::Trait`, since changing that may affect method
 444             // resolution.
 445             //
 446             // The simplest approach to handling both of the above is
 447             // just to adopt the same simple-minded (fine-grained)
 448             // hash that I am deploying elsewhere here.
 449             SawViewItem.hash(self.st); visit::walk_view_item(self, i)
 450         }
 451
 452         fn visit_foreign_item(&mut self, i: &ForeignItem) {
 453             // FIXME (#14132) ideally we would incorporate privacy (or
 454             // perhaps reachability) somewhere here, so foreign items
 455             // that do not leak into downstream crates would not be
 456             // part of the ABI.
 457             SawForeignItem.hash(self.st); visit::walk_foreign_item(self, i)
 458         }
 459
 460         fn visit_item(&mut self, i: &Item) {
 461             // FIXME (#14132) ideally would incorporate reachability
 462             // analysis somewhere here, so items that never leak into
 463             // downstream crates (e.g. via monomorphisation or
 464             // inlining) would not be part of the ABI.
 465             SawItem.hash(self.st); visit::walk_item(self, i)
 466         }
 467
 468         fn visit_mod(&mut self, m: &Mod, _s: Span, _n: NodeId) {
 469             SawMod.hash(self.st); visit::walk_mod(self, m)
 470         }
 471
 472         fn visit_decl(&mut self, d: &Decl) {
 473             SawDecl.hash(self.st); visit::walk_decl(self, d)
 474         }
 475
 476         fn visit_ty(&mut self, t: &Ty) {
 477             SawTy.hash(self.st); visit::walk_ty(self, t)
 478         }
 479
 480         fn visit_generics(&mut self, g: &Generics) {
 481             SawGenerics.hash(self.st); visit::walk_generics(self, g)
 482         }
 483
 484         fn visit_fn(&mut self, fk: FnKind<'v>, fd: &'v FnDecl,
 485                     b: &'v Block, s: Span, _: NodeId) {
 486             SawFn.hash(self.st); visit::walk_fn(self, fk, fd, b, s)
 487         }
 488
 489         fn visit_ty_method(&mut self, t: &TypeMethod) {
 490             SawTyMethod.hash(self.st); visit::walk_ty_method(self, t)
 491         }
 492
 493         fn visit_trait_item(&mut self, t: &TraitItem) {
 494             SawTraitMethod.hash(self.st); visit::walk_trait_item(self, t)
 495         }
 496
 497         fn visit_struct_field(&mut self, s: &StructField) {
 498             SawStructField.hash(self.st); visit::walk_struct_field(self, s)
 499         }
 500
 501         fn visit_explicit_self(&mut self, es: &ExplicitSelf) {
 502             SawExplicitSelf.hash(self.st); visit::walk_explicit_self(self, es)
 503         }
 504
 505         fn visit_path(&mut self, path: &Path, _: ast::NodeId) {
 506             SawPath.hash(self.st); visit::walk_path(self, path)
 507         }
 508
 509         fn visit_block(&mut self, b: &Block) {
 510             SawBlock.hash(self.st); visit::walk_block(self, b)
 511         }
 512
 513         fn visit_pat(&mut self, p: &Pat) {
 514             SawPat.hash(self.st); visit::walk_pat(self, p)
 515         }
 516
 517         fn visit_local(&mut self, l: &Local) {
 518             SawLocal.hash(self.st); visit::walk_local(self, l)
 519         }
 520
 521         fn visit_arm(&mut self, a: &Arm) {
 522             SawArm.hash(self.st); visit::walk_arm(self, a)
 523         }
 524     }
 525 }