1 // Copyright 2012-2013 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 // Finds items that are externally reachable, to determine which items
12 // need to have their metadata (and possibly their AST) serialized.
13 // All items that can be referred to through an exported name are
14 // reachable, and when a reachable thing is inline or generic, it
15 // makes all other generics or inline functions that it references
16 // reachable as well.
17
18 use driver::session;
19 use middle::ty;
20 use middle::typeck;
21 use middle::privacy;
22 use util::nodemap::NodeSet;
23
24 use collections::HashSet;
25 use syntax::abi;
26 use syntax::ast;
27 use syntax::ast_map;
28 use syntax::ast_util::{def_id_of_def, is_local};
29 use syntax::attr;
30 use syntax::visit::Visitor;
31 use syntax::visit;
32
33 // Returns true if the given set of attributes contains the `#[inline]`
34 // attribute.
35 fn attributes_specify_inlining(attrs: &[ast::Attribute]) -> bool {
36 attr::contains_name(attrs, "inline")
37 }
38
39 // Returns true if the given set of generics implies that the item it's
40 // associated with must be inlined.
41 fn generics_require_inlining(generics: &ast::Generics) -> bool {
42 !generics.ty_params.is_empty()
43 }
44
45 // Returns true if the given item must be inlined because it may be
46 // monomorphized or it was marked with `#[inline]`. This will only return
47 // true for functions.
48 fn item_might_be_inlined(item: &ast::Item) -> bool {
49 if attributes_specify_inlining(item.attrs.as_slice()) {
50 return true
51 }
52
53 match item.node {
54 ast::ItemImpl(ref generics, _, _, _) |
55 ast::ItemFn(_, _, _, ref generics, _) => {
56 generics_require_inlining(generics)
57 }
58 _ => false,
59 }
60 }
61
62 fn method_might_be_inlined(tcx: &ty::ctxt, method: &ast::Method,
63 impl_src: ast::DefId) -> bool {
64 if attributes_specify_inlining(method.attrs.as_slice()) ||
65 generics_require_inlining(&method.generics) {
66 return true
67 }
68 if is_local(impl_src) {
69 {
70 match tcx.map.find(impl_src.node) {
71 Some(ast_map::NodeItem(item)) => {
72 item_might_be_inlined(item)
73 }
74 Some(..) | None => {
75 tcx.sess.span_bug(method.span, "impl did is not an item")
76 }
77 }
78 }
79 } else {
80 tcx.sess.span_bug(method.span, "found a foreign impl as a parent of a \
81 local method")
82 }
83 }
84
85 // Information needed while computing reachability.
86 struct ReachableContext<'a> {
87 // The type context.
88 tcx: &'a ty::ctxt,
89 // The set of items which must be exported in the linkage sense.
90 reachable_symbols: NodeSet,
91 // A worklist of item IDs. Each item ID in this worklist will be inlined
92 // and will be scanned for further references.
93 worklist: Vec<ast::NodeId>,
94 // Whether any output of this compilation is a library
95 any_library: bool,
96 }
97
98 impl<'a> Visitor<()> for ReachableContext<'a> {
99
100 fn visit_expr(&mut self, expr: &ast::Expr, _: ()) {
101
102 match expr.node {
103 ast::ExprPath(_) => {
104 let def = match self.tcx.def_map.borrow().find(&expr.id) {
105 Some(&def) => def,
106 None => {
107 self.tcx.sess.span_bug(expr.span,
108 "def ID not in def map?!")
109 }
110 };
111
112 let def_id = def_id_of_def(def);
113 if is_local(def_id) {
114 if self.def_id_represents_local_inlined_item(def_id) {
115 self.worklist.push(def_id.node)
116 } else {
117 match def {
118 // If this path leads to a static, then we may have
119 // to do some work to figure out whether the static
120 // is indeed reachable (address_insignificant
121 // statics are *never* reachable).
122 ast::DefStatic(..) => {
123 self.worklist.push(def_id.node);
124 }
125
126 // If this wasn't a static, then this destination is
127 // surely reachable.
128 _ => {
129 self.reachable_symbols.insert(def_id.node);
130 }
131 }
132 }
133 }
134 }
135 ast::ExprMethodCall(..) => {
136 let method_call = typeck::MethodCall::expr(expr.id);
137 match self.tcx.method_map.borrow().get(&method_call).origin {
138 typeck::MethodStatic(def_id) => {
139 if is_local(def_id) {
140 if self.def_id_represents_local_inlined_item(def_id) {
141 self.worklist.push(def_id.node)
142 }
143 self.reachable_symbols.insert(def_id.node);
144 }
145 }
146 _ => {}
147 }
148 }
149 _ => {}
150 }
151
152 visit::walk_expr(self, expr, ())
153 }
154
155 fn visit_item(&mut self, _item: &ast::Item, _: ()) {
156 // Do not recurse into items. These items will be added to the worklist
157 // and recursed into manually if necessary.
158 }
159 }
160
161 impl<'a> ReachableContext<'a> {
162 // Creates a new reachability computation context.
163 fn new(tcx: &'a ty::ctxt) -> ReachableContext<'a> {
164 let any_library = tcx.sess.crate_types.borrow().iter().any(|ty| {
165 *ty != session::CrateTypeExecutable
166 });
167 ReachableContext {
168 tcx: tcx,
169 reachable_symbols: NodeSet::new(),
170 worklist: Vec::new(),
171 any_library: any_library,
172 }
173 }
174
175 // Returns true if the given def ID represents a local item that is
176 // eligible for inlining and false otherwise.
177 fn def_id_represents_local_inlined_item(&self, def_id: ast::DefId) -> bool {
178 if def_id.krate != ast::LOCAL_CRATE {
179 return false
180 }
181
182 let node_id = def_id.node;
183 match self.tcx.map.find(node_id) {
184 Some(ast_map::NodeItem(item)) => {
185 match item.node {
186 ast::ItemFn(..) => item_might_be_inlined(item),
187 _ => false,
188 }
189 }
190 Some(ast_map::NodeTraitMethod(trait_method)) => {
191 match *trait_method {
192 ast::Required(_) => false,
193 ast::Provided(_) => true,
194 }
195 }
196 Some(ast_map::NodeMethod(method)) => {
197 if generics_require_inlining(&method.generics) ||
198 attributes_specify_inlining(method.attrs.as_slice()) {
199 true
200 } else {
201 let impl_did = self.tcx.map.get_parent_did(node_id);
202 // Check the impl. If the generics on the self type of the
203 // impl require inlining, this method does too.
204 assert!(impl_did.krate == ast::LOCAL_CRATE);
205 match self.tcx.map.expect_item(impl_did.node).node {
206 ast::ItemImpl(ref generics, _, _, _) => {
207 generics_require_inlining(generics)
208 }
209 _ => false
210 }
211 }
212 }
213 Some(_) => false,
214 None => false // This will happen for default methods.
215 }
216 }
217
218 // Step 2: Mark all symbols that the symbols on the worklist touch.
219 fn propagate(&mut self) {
220 let mut scanned = HashSet::new();
221 loop {
222 if self.worklist.len() == 0 {
223 break
224 }
225 let search_item = self.worklist.pop().unwrap();
226 if scanned.contains(&search_item) {
227 continue
228 }
229
230 scanned.insert(search_item);
231 match self.tcx.map.find(search_item) {
232 Some(ref item) => self.propagate_node(item, search_item),
233 None if search_item == ast::CRATE_NODE_ID => {}
234 None => {
235 self.tcx.sess.bug(format!("found unmapped ID in worklist: \
236 {}",
237 search_item))
238 }
239 }
240 }
241 }
242
243 fn propagate_node(&mut self, node: &ast_map::Node,
244 search_item: ast::NodeId) {
245 if !self.any_library {
246 // If we are building an executable, then there's no need to flag
247 // anything as external except for `extern fn` types. These
248 // functions may still participate in some form of native interface,
249 // but all other rust-only interfaces can be private (they will not
250 // participate in linkage after this product is produced)
251 match *node {
252 ast_map::NodeItem(item) => {
253 match item.node {
254 ast::ItemFn(_, _, abi, _, _) => {
255 if abi != abi::Rust {
256 self.reachable_symbols.insert(search_item);
257 }
258 }
259 _ => {}
260 }
261 }
262 _ => {}
263 }
264 } else {
265 // If we are building a library, then reachable symbols will
266 // continue to participate in linkage after this product is
267 // produced. In this case, we traverse the ast node, recursing on
268 // all reachable nodes from this one.
269 self.reachable_symbols.insert(search_item);
270 }
271
272 match *node {
273 ast_map::NodeItem(item) => {
274 match item.node {
275 ast::ItemFn(_, _, _, _, search_block) => {
276 if item_might_be_inlined(item) {
277 visit::walk_block(self, search_block, ())
278 }
279 }
280
281 // Statics with insignificant addresses are not reachable
282 // because they're inlined specially into all other crates.
283 ast::ItemStatic(_, _, init) => {
284 if attr::contains_name(item.attrs.as_slice(),
285 "address_insignificant") {
286 self.reachable_symbols.remove(&search_item);
287 }
288 visit::walk_expr(self, init, ());
289 }
290
291 // These are normal, nothing reachable about these
292 // inherently and their children are already in the
293 // worklist, as determined by the privacy pass
294 ast::ItemTy(..) |
295 ast::ItemMod(..) | ast::ItemForeignMod(..) |
296 ast::ItemImpl(..) | ast::ItemTrait(..) |
297 ast::ItemStruct(..) | ast::ItemEnum(..) => {}
298
299 _ => {
300 self.tcx.sess.span_bug(item.span,
301 "found non-function item \
302 in worklist?!")
303 }
304 }
305 }
306 ast_map::NodeTraitMethod(trait_method) => {
307 match *trait_method {
308 ast::Required(..) => {
309 // Keep going, nothing to get exported
310 }
311 ast::Provided(ref method) => {
312 visit::walk_block(self, method.body, ())
313 }
314 }
315 }
316 ast_map::NodeMethod(method) => {
317 let did = self.tcx.map.get_parent_did(search_item);
318 if method_might_be_inlined(self.tcx, method, did) {
319 visit::walk_block(self, method.body, ())
320 }
321 }
322 // Nothing to recurse on for these
323 ast_map::NodeForeignItem(_) |
324 ast_map::NodeVariant(_) |
325 ast_map::NodeStructCtor(_) => {}
326 _ => {
327 self.tcx.sess.bug(format!("found unexpected thingy in \
328 worklist: {}",
329 self.tcx.map.node_to_str(search_item)))
330 }
331 }
332 }
333
334 // Step 3: Mark all destructors as reachable.
335 //
336 // FIXME(pcwalton): This is a conservative overapproximation, but fixing
337 // this properly would result in the necessity of computing *type*
338 // reachability, which might result in a compile time loss.
339 fn mark_destructors_reachable(&mut self) {
340 for (_, destructor_def_id) in self.tcx.destructor_for_type.borrow().iter() {
341 if destructor_def_id.krate == ast::LOCAL_CRATE {
342 self.reachable_symbols.insert(destructor_def_id.node);
343 }
344 }
345 }
346 }
347
348 pub fn find_reachable(tcx: &ty::ctxt,
349 exported_items: &privacy::ExportedItems)
350 -> NodeSet {
351 let mut reachable_context = ReachableContext::new(tcx);
352
353 // Step 1: Seed the worklist with all nodes which were found to be public as
354 // a result of the privacy pass along with all local lang items. If
355 // other crates link to us, they're going to expect to be able to
356 // use the lang items, so we need to be sure to mark them as
357 // exported.
358 for &id in exported_items.iter() {
359 reachable_context.worklist.push(id);
360 }
361 for (_, item) in tcx.lang_items.items() {
362 match *item {
363 Some(did) if is_local(did) => {
364 reachable_context.worklist.push(did.node);
365 }
366 _ => {}
367 }
368 }
369
370 // Step 2: Mark all symbols that the symbols on the worklist touch.
371 reachable_context.propagate();
372
373 // Step 3: Mark all destructors as reachable.
374 reachable_context.mark_destructors_reachable();
375
376 // Return the set of reachable symbols.
377 reachable_context.reachable_symbols
378 }
librustc/middle/reachable.rs:47:23-47:23 -fn- definition:
// true for functions.
fn item_might_be_inlined(item: &ast::Item) -> bool {
if attributes_specify_inlining(item.attrs.as_slice()) {
references:- 3185: match item.node {
186: ast::ItemFn(..) => item_might_be_inlined(item),
187: _ => false,
--
275: ast::ItemFn(_, _, _, _, search_block) => {
276: if item_might_be_inlined(item) {
277: visit::walk_block(self, search_block, ())
librustc/middle/reachable.rs:34:14-34:14 -fn- definition:
// attribute.
fn attributes_specify_inlining(attrs: &[ast::Attribute]) -> bool {
attr::contains_name(attrs, "inline")
references:- 3197: if generics_require_inlining(&method.generics) ||
198: attributes_specify_inlining(method.attrs.as_slice()) {
199: true
librustc/middle/reachable.rs:85:52-85:52 -struct- definition:
// Information needed while computing reachability.
struct ReachableContext<'a> {
// The type context.
references:- 4166: });
167: ReachableContext {
168: tcx: tcx,
librustc/middle/reachable.rs:40:36-40:36 -fn- definition:
// associated with must be inlined.
fn generics_require_inlining(generics: &ast::Generics) -> bool {
!generics.ty_params.is_empty()
references:- 455: ast::ItemFn(_, _, _, ref generics, _) => {
56: generics_require_inlining(generics)
57: }
--
64: if attributes_specify_inlining(method.attrs.as_slice()) ||
65: generics_require_inlining(&method.generics) {
66: return true
--
196: Some(ast_map::NodeMethod(method)) => {
197: if generics_require_inlining(&method.generics) ||
198: attributes_specify_inlining(method.attrs.as_slice()) {
--
206: ast::ItemImpl(ref generics, _, _, _) => {
207: generics_require_inlining(generics)
208: }