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.
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.
11 //! Calculation of a Strict Version Hash for crates. For a length
12 //! comment explaining the general idea, see `librustc/middle/svh.rs`.
14 use std
::hash
::{Hash, SipHasher, Hasher}
;
15 use rustc
::hir
::def_id
::{CRATE_DEF_INDEX, DefId}
;
16 use rustc
::hir
::svh
::Svh
;
18 use rustc
::hir
::intravisit
::{self, Visitor}
;
20 use self::svh_visitor
::StrictVersionHashVisitor
;
22 pub trait SvhCalculate
{
23 /// Calculate the SVH for an entire krate.
24 fn calculate_krate_hash(&self) -> Svh
;
26 /// Calculate the SVH for a particular item.
27 fn calculate_item_hash(&self, def_id
: DefId
) -> u64;
30 impl<'tcx
> SvhCalculate
for ty
::TyCtxt
<'tcx
> {
31 fn calculate_krate_hash(&self) -> Svh
{
32 // FIXME (#14132): This is better than it used to be, but it still not
33 // ideal. We now attempt to hash only the relevant portions of the
34 // Crate AST as well as the top-level crate attributes. (However,
35 // the hashing of the crate attributes should be double-checked
36 // to ensure it is not incorporating implementation artifacts into
37 // the hash that are not otherwise visible.)
39 let crate_disambiguator
= self.sess
.crate_disambiguator
.get();
40 let krate
= self.map
.krate();
42 // FIXME: this should use SHA1, not SipHash. SipHash is not built to
44 let mut state
= SipHasher
::new();
45 debug
!("state: {:?}", state
);
47 // FIXME(#32753) -- at (*) we `to_le` for endianness, but is
48 // this enough, and does it matter anyway?
49 "crate_disambiguator".hash(&mut state
);
50 crate_disambiguator
.as_str().len().to_le().hash(&mut state
); // (*)
51 crate_disambiguator
.as_str().hash(&mut state
);
53 debug
!("crate_disambiguator: {:?}", crate_disambiguator
.as_str());
54 debug
!("state: {:?}", state
);
57 let mut visit
= StrictVersionHashVisitor
::new(&mut state
, self);
58 krate
.visit_all_items(&mut visit
);
61 // FIXME (#14132): This hash is still sensitive to e.g. the
62 // spans of the crate Attributes and their underlying
63 // MetaItems; we should make ContentHashable impl for those
64 // types and then use hash_content. But, since all crate
65 // attributes should appear near beginning of the file, it is
66 // not such a big deal to be sensitive to their spans for now.
68 // We hash only the MetaItems instead of the entire Attribute
69 // to avoid hashing the AttrId
70 for attr
in &krate
.attrs
{
71 debug
!("krate attr {:?}", attr
);
72 attr
.node
.value
.hash(&mut state
);
75 Svh
::from_hash(state
.finish())
78 fn calculate_item_hash(&self, def_id
: DefId
) -> u64 {
79 assert
!(def_id
.is_local());
81 let mut state
= SipHasher
::new();
84 let mut visit
= StrictVersionHashVisitor
::new(&mut state
, self);
85 if def_id
.index
== CRATE_DEF_INDEX
{
86 // the crate root itself is not registered in the map
87 // as an item, so we have to fetch it this way
88 let krate
= self.map
.krate();
89 intravisit
::walk_crate(&mut visit
, krate
);
91 let node_id
= self.map
.as_local_node_id(def_id
).unwrap();
92 visit
.visit_item(self.map
.expect_item(node_id
));
100 // FIXME (#14132): Even this SVH computation still has implementation
101 // artifacts: namely, the order of item declaration will affect the
102 // hash computation, but for many kinds of items the order of
103 // declaration should be irrelevant to the ABI.
106 pub use self::SawExprComponent
::*;
107 pub use self::SawStmtComponent
::*;
108 use self::SawAbiComponent
::*;
109 use syntax
::ast
::{self, Name, NodeId}
;
110 use syntax
::codemap
::Span
;
111 use syntax
::parse
::token
;
115 use rustc
::hir
::intravisit
as visit
;
116 use rustc
::hir
::intravisit
::{Visitor, FnKind}
;
118 use std
::hash
::{Hash, SipHasher}
;
120 pub struct StrictVersionHashVisitor
<'a
, 'tcx
: 'a
> {
121 pub tcx
: &'a ty
::TyCtxt
<'tcx
>,
122 pub st
: &'a
mut SipHasher
,
125 impl<'a
, 'tcx
> StrictVersionHashVisitor
<'a
, 'tcx
> {
126 pub fn new(st
: &'a
mut SipHasher
,
127 tcx
: &'a ty
::TyCtxt
<'tcx
>)
129 StrictVersionHashVisitor { st: st, tcx: tcx }
133 // To off-load the bulk of the hash-computation on #[derive(Hash)],
134 // we define a set of enums corresponding to the content that our
135 // crate visitor will encounter as it traverses the ast.
137 // The important invariant is that all of the Saw*Component enums
138 // do not carry any Spans, Names, or Idents.
140 // Not carrying any Names/Idents is the important fix for problem
141 // noted on PR #13948: using the ident.name as the basis for a
142 // hash leads to unstable SVH, because ident.name is just an index
143 // into intern table (i.e. essentially a random address), not
144 // computed from the name content.
146 // With the below enums, the SVH computation is not sensitive to
147 // artifacts of how rustc was invoked nor of how the source code
148 // was laid out. (Or at least it is *less* sensitive.)
150 // This enum represents the different potential bits of code the
151 // visitor could encounter that could affect the ABI for the crate,
152 // and assigns each a distinct tag to feed into the hash computation.
154 enum SawAbiComponent
<'a
> {
156 // FIXME (#14132): should we include (some function of)
157 // ident.ctxt as well?
158 SawIdent(token
::InternedString
),
159 SawStructDef(token
::InternedString
),
161 SawLifetime(token
::InternedString
),
162 SawLifetimeDef(token
::InternedString
),
181 SawExpr(SawExprComponent
<'a
>),
182 SawStmt(SawStmtComponent
),
185 /// SawExprComponent carries all of the information that we want
186 /// to include in the hash that *won't* be covered by the
187 /// subsequent recursive traversal of the expression's
188 /// substructure by the visitor.
190 /// We know every Expr_ variant is covered by a variant because
191 /// `fn saw_expr` maps each to some case below. Ensuring that
192 /// each variant carries an appropriate payload has to be verified
195 /// (However, getting that *exactly* right is not so important
196 /// because the SVH is just a developer convenience; there is no
197 /// guarantee of collision-freedom, hash collisions are just
198 /// (hopefully) unlikely.)
200 pub enum SawExprComponent
<'a
> {
202 SawExprLoop(Option
<token
::InternedString
>),
203 SawExprField(token
::InternedString
),
204 SawExprTupField(usize),
205 SawExprBreak(Option
<token
::InternedString
>),
206 SawExprAgain(Option
<token
::InternedString
>),
213 SawExprBinary(hir
::BinOp_
),
214 SawExprUnary(hir
::UnOp
),
215 SawExprLit(ast
::LitKind
),
224 SawExprAssignOp(hir
::BinOp_
),
226 SawExprPath(Option
<usize>),
227 SawExprAddrOf(hir
::Mutability
),
229 SawExprInlineAsm(&'a hir
::InlineAsm
),
234 fn saw_expr
<'a
>(node
: &'a Expr_
) -> SawExprComponent
<'a
> {
236 ExprBox(..) => SawExprBox
,
237 ExprVec(..) => SawExprVec
,
238 ExprCall(..) => SawExprCall
,
239 ExprMethodCall(..) => SawExprMethodCall
,
240 ExprTup(..) => SawExprTup
,
241 ExprBinary(op
, _
, _
) => SawExprBinary(op
.node
),
242 ExprUnary(op
, _
) => SawExprUnary(op
),
243 ExprLit(ref lit
) => SawExprLit(lit
.node
.clone()),
244 ExprCast(..) => SawExprCast
,
245 ExprType(..) => SawExprType
,
246 ExprIf(..) => SawExprIf
,
247 ExprWhile(..) => SawExprWhile
,
248 ExprLoop(_
, id
) => SawExprLoop(id
.map(|id
| id
.name
.as_str())),
249 ExprMatch(..) => SawExprMatch
,
250 ExprClosure(..) => SawExprClosure
,
251 ExprBlock(..) => SawExprBlock
,
252 ExprAssign(..) => SawExprAssign
,
253 ExprAssignOp(op
, _
, _
) => SawExprAssignOp(op
.node
),
254 ExprField(_
, name
) => SawExprField(name
.node
.as_str()),
255 ExprTupField(_
, id
) => SawExprTupField(id
.node
),
256 ExprIndex(..) => SawExprIndex
,
257 ExprPath(ref qself
, _
) => SawExprPath(qself
.as_ref().map(|q
| q
.position
)),
258 ExprAddrOf(m
, _
) => SawExprAddrOf(m
),
259 ExprBreak(id
) => SawExprBreak(id
.map(|id
| id
.node
.name
.as_str())),
260 ExprAgain(id
) => SawExprAgain(id
.map(|id
| id
.node
.name
.as_str())),
261 ExprRet(..) => SawExprRet
,
262 ExprInlineAsm(ref a
,_
,_
) => SawExprInlineAsm(a
),
263 ExprStruct(..) => SawExprStruct
,
264 ExprRepeat(..) => SawExprRepeat
,
268 /// SawStmtComponent is analogous to SawExprComponent, but for statements.
270 pub enum SawStmtComponent
{
276 fn saw_stmt(node
: &Stmt_
) -> SawStmtComponent
{
278 StmtDecl(..) => SawStmtDecl
,
279 StmtExpr(..) => SawStmtExpr
,
280 StmtSemi(..) => SawStmtSemi
,
284 impl<'a
, 'tcx
> Visitor
<'a
> for StrictVersionHashVisitor
<'a
, 'tcx
> {
285 fn visit_nested_item(&mut self, item
: ItemId
) {
286 debug
!("visit_nested_item: {:?} st={:?}", item
, self.st
);
287 let def_path
= self.tcx
.map
.def_path_from_id(item
.id
);
288 def_path
.hash(self.st
);
291 fn visit_variant_data(&mut self, s
: &'a VariantData
, name
: Name
,
292 g
: &'a Generics
, _
: NodeId
, _
: Span
) {
293 SawStructDef(name
.as_str()).hash(self.st
);
294 visit
::walk_generics(self, g
);
295 visit
::walk_struct_def(self, s
)
298 fn visit_variant(&mut self, v
: &'a Variant
, g
: &'a Generics
, item_id
: NodeId
) {
299 SawVariant
.hash(self.st
);
300 // walk_variant does not call walk_generics, so do it here.
301 visit
::walk_generics(self, g
);
302 visit
::walk_variant(self, v
, g
, item_id
)
305 // All of the remaining methods just record (in the hash
306 // SipHasher) that the visitor saw that particular variant
307 // (with its payload), and continue walking as the default
310 // Some of the implementations have some notes as to how one
311 // might try to make their SVH computation less discerning
312 // (e.g. by incorporating reachability analysis). But
313 // currently all of their implementations are uniform and
316 // (If you edit a method such that it deviates from the
317 // pattern, please move that method up above this comment.)
319 fn visit_name(&mut self, _
: Span
, name
: Name
) {
320 SawIdent(name
.as_str()).hash(self.st
);
323 fn visit_lifetime(&mut self, l
: &'a Lifetime
) {
324 SawLifetime(l
.name
.as_str()).hash(self.st
);
327 fn visit_lifetime_def(&mut self, l
: &'a LifetimeDef
) {
328 SawLifetimeDef(l
.lifetime
.name
.as_str()).hash(self.st
);
331 // We do recursively walk the bodies of functions/methods
332 // (rather than omitting their bodies from the hash) since
333 // monomorphization and cross-crate inlining generally implies
334 // that a change to a crate body will require downstream
335 // crates to be recompiled.
336 fn visit_expr(&mut self, ex
: &'a Expr
) {
337 SawExpr(saw_expr(&ex
.node
)).hash(self.st
); visit
::walk_expr(self, ex
)
340 fn visit_stmt(&mut self, s
: &'a Stmt
) {
341 SawStmt(saw_stmt(&s
.node
)).hash(self.st
); visit
::walk_stmt(self, s
)
344 fn visit_foreign_item(&mut self, i
: &'a ForeignItem
) {
345 // FIXME (#14132) ideally we would incorporate privacy (or
346 // perhaps reachability) somewhere here, so foreign items
347 // that do not leak into downstream crates would not be
349 SawForeignItem
.hash(self.st
); visit
::walk_foreign_item(self, i
)
352 fn visit_item(&mut self, i
: &'a Item
) {
353 debug
!("visit_item: {:?} st={:?}", i
, self.st
);
354 // FIXME (#14132) ideally would incorporate reachability
355 // analysis somewhere here, so items that never leak into
356 // downstream crates (e.g. via monomorphisation or
357 // inlining) would not be part of the ABI.
358 SawItem
.hash(self.st
); visit
::walk_item(self, i
)
361 fn visit_mod(&mut self, m
: &'a Mod
, _s
: Span
, _n
: NodeId
) {
362 SawMod
.hash(self.st
); visit
::walk_mod(self, m
)
365 fn visit_decl(&mut self, d
: &'a Decl
) {
366 SawDecl
.hash(self.st
); visit
::walk_decl(self, d
)
369 fn visit_ty(&mut self, t
: &'a Ty
) {
370 SawTy
.hash(self.st
); visit
::walk_ty(self, t
)
373 fn visit_generics(&mut self, g
: &'a Generics
) {
374 SawGenerics
.hash(self.st
); visit
::walk_generics(self, g
)
377 fn visit_fn(&mut self, fk
: FnKind
<'a
>, fd
: &'a FnDecl
,
378 b
: &'a Block
, s
: Span
, _
: NodeId
) {
379 SawFn
.hash(self.st
); visit
::walk_fn(self, fk
, fd
, b
, s
)
382 fn visit_trait_item(&mut self, ti
: &'a TraitItem
) {
383 SawTraitItem
.hash(self.st
); visit
::walk_trait_item(self, ti
)
386 fn visit_impl_item(&mut self, ii
: &'a ImplItem
) {
387 SawImplItem
.hash(self.st
); visit
::walk_impl_item(self, ii
)
390 fn visit_struct_field(&mut self, s
: &'a StructField
) {
391 SawStructField
.hash(self.st
); visit
::walk_struct_field(self, s
)
394 fn visit_explicit_self(&mut self, es
: &'a ExplicitSelf
) {
395 SawExplicitSelf
.hash(self.st
); visit
::walk_explicit_self(self, es
)
398 fn visit_path(&mut self, path
: &'a Path
, _
: ast
::NodeId
) {
399 SawPath
.hash(self.st
); visit
::walk_path(self, path
)
402 fn visit_path_list_item(&mut self, prefix
: &'a Path
, item
: &'a PathListItem
) {
403 SawPath
.hash(self.st
); visit
::walk_path_list_item(self, prefix
, item
)
406 fn visit_block(&mut self, b
: &'a Block
) {
407 SawBlock
.hash(self.st
); visit
::walk_block(self, b
)
410 fn visit_pat(&mut self, p
: &'a Pat
) {
411 SawPat
.hash(self.st
); visit
::walk_pat(self, p
)
414 fn visit_local(&mut self, l
: &'a Local
) {
415 SawLocal
.hash(self.st
); visit
::walk_local(self, l
)
418 fn visit_arm(&mut self, a
: &'a Arm
) {
419 SawArm
.hash(self.st
); visit
::walk_arm(self, a
)