src/librustc/middle/trans/debuginfo.rs

   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 /*!
  12 # Debug Info Module
  13
  14 This module serves the purpose of generating debug symbols. We use LLVM's
  15 [source level debugging](http://llvm.org/docs/SourceLevelDebugging.html) features for generating
  16 the debug information. The general principle is this:
  17
  18 Given the right metadata in the LLVM IR, the LLVM code generator is able to create DWARF debug
  19 symbols for the given code. The [metadata](http://llvm.org/docs/LangRef.html#metadata-type) is
  20 structured much like DWARF *debugging information entries* (DIE), representing type information
  21 such as datatype layout, function signatures, block layout, variable location and scope information,
  22 etc. It is the purpose of this module to generate correct metadata and insert it into the LLVM IR.
  23
  24 As the exact format of metadata trees may change between different LLVM versions, we now use LLVM
  25 [DIBuilder](http://llvm.org/docs/doxygen/html/classllvm_1_1DIBuilder.html) to create metadata
  26 where possible. This will hopefully ease the adaption of this module to future LLVM versions.
  27
  28 The public API of the module is a set of functions that will insert the correct metadata into the
  29 LLVM IR when called with the right parameters. The module is thus driven from an outside client with
  30 functions like `debuginfo::create_local_var_metadata(bcx: block, local: &ast::local)`.
  31
  32 Internally the module will try to reuse already created metadata by utilizing a cache. The way to
  33 get a shared metadata node when needed is thus to just call the corresponding function in this
  34 module:
  35
  36     let file_metadata = file_metadata(crate_context, path);
  37
  38 The function will take care of probing the cache for an existing node for that exact file path.
  39
  40 All private state used by the module is stored within either the CrateDebugContext struct (owned by
  41 the CrateContext) or the FunctionDebugContext (owned by the FunctionContext).
  42
  43 This file consists of three conceptual sections:
  44 1. The public interface of the module
  45 2. Module-internal metadata creation functions
  46 3. Minor utility functions
  47
  48
  49 ## Recursive Types
  50 Some kinds of types, such as structs and enums can be recursive. That means that the type definition
  51 of some type X refers to some other type which in turn (transitively) refers to X. This introduces
  52 cycles into the type referral graph. A naive algorithm doing an on-demand, depth-first traversal of
  53 this graph when describing types, can get trapped in an endless loop when it reaches such a cycle.
  54
  55 For example, the following simple type for a singly-linked list...
  56
  57 ```
  58 struct List {
  59     value: int,
  60     tail: Option<@List>,
  61 }
  62 ```
  63
  64 will generate the following callstack with a naive DFS algorithm:
  65
  66 ```
  67 describe(t = List)
  68   describe(t = int)
  69   describe(t = Option<@List>)
  70     describe(t = @List)
  71       describe(t = List) // at the beginning again...
  72       ...
  73 ```
  74
  75 To break cycles like these, we use "forward declarations". That is, when the algorithm encounters a
  76 possibly recursive type (any struct or enum), it immediately creates a type description node and
  77 inserts it into the cache *before* describing the members of the type. This type description is just
  78 a stub (as type members are not described and added to it yet) but it allows the algorithm to
  79 already refer to the type. After the stub is inserted into the cache, the algorithm continues as
  80 before. If it now encounters a recursive reference, it will hit the cache and does not try to
  81 describe the type anew.
  82
  83 This behaviour is encapsulated in the 'RecursiveTypeDescription' enum, which represents a kind of
  84 continuation, storing all state needed to continue traversal at the type members after the type has
  85 been registered with the cache. (This implementation approach might be a tad over-engineered and
  86 may change in the future)
  87
  88
  89 ## Source Locations and Line Information
  90 In addition to data type descriptions the debugging information must also allow to map machine code
  91 locations back to source code locations in order to be useful. This functionality is also handled in
  92 this module. The following functions allow to control source mappings:
  93
  94 + set_source_location()
  95 + clear_source_location()
  96 + start_emitting_source_locations()
  97
  98 `set_source_location()` allows to set the current source location. All IR instructions created after
  99 a call to this function will be linked to the given source location, until another location is
 100 specified with `set_source_location()` or the source location is cleared with
 101 `clear_source_location()`. In the later case, subsequent IR instruction will not be linked to any
 102 source location. As you can see, this is a stateful API (mimicking the one in LLVM), so be careful
 103 with source locations set by previous calls. It's probably best to not rely on any specific state
 104 being present at a given point in code.
 105
 106 One topic that deserves some extra attention is *function prologues*. At the beginning of a
 107 function's machine code there are typically a few instructions for loading argument values into
 108 allocas and checking if there's enough stack space for the function to execute. This *prologue* is
 109 not visible in the source code and LLVM puts a special PROLOGUE END marker into the line table at
 110 the first non-prologue instruction of the function. In order to find out where the prologue ends,
 111 LLVM looks for the first instruction in the function body that is linked to a source location. So,
 112 when generating prologue instructions we have to make sure that we don't emit source location
 113 information until the 'real' function body begins. For this reason, source location emission is
 114 disabled by default for any new function being translated and is only activated after a call to the
 115 third function from the list above, `start_emitting_source_locations()`. This function should be
 116 called right before regularly starting to translate the top-level block of the given function.
 117
 118 There is one exception to the above rule: `llvm.dbg.declare` instruction must be linked to the
 119 source location of the variable being declared. For function parameters these `llvm.dbg.declare`
 120 instructions typically occur in the middle of the prologue, however, they are ignored by LLVM's
 121 prologue detection. The `create_argument_metadata()` and related functions take care of linking the
 122 `llvm.dbg.declare` instructions to the correct source locations even while source location emission
 123 is still disabled, so there is no need to do anything special with source location handling here.
 124
 125 */
 126
 127
 128 use driver::session;
 129 use driver::session::{FullDebugInfo, LimitedDebugInfo, NoDebugInfo};
 130 use lib::llvm::llvm;
 131 use lib::llvm::{ModuleRef, ContextRef, ValueRef};
 132 use lib::llvm::debuginfo::*;
 133 use metadata::csearch;
 134 use middle::trans::adt;
 135 use middle::trans::common::*;
 136 use middle::trans::datum::{Datum, Lvalue};
 137 use middle::trans::machine;
 138 use middle::trans::type_of;
 139 use middle::trans::type_::Type;
 140 use middle::trans;
 141 use middle::ty;
 142 use middle::pat_util;
 143 use util::ppaux;
 144
 145 use std::c_str::{CString, ToCStr};
 146 use std::cell::{Cell, RefCell};
 147 use collections::HashMap;
 148 use collections::HashSet;
 149 use libc::{c_uint, c_ulonglong, c_longlong};
 150 use std::ptr;
 151 use std::strbuf::StrBuf;
 152 use std::sync::atomics;
 153 use syntax::codemap::{Span, Pos};
 154 use syntax::{abi, ast, codemap, ast_util, ast_map};
 155 use syntax::owned_slice::OwnedSlice;
 156 use syntax::parse::token;
 157 use syntax::parse::token::special_idents;
 158
 159 static DW_LANG_RUST: c_uint = 0x9000;
 160
 161 static DW_TAG_auto_variable: c_uint = 0x100;
 162 static DW_TAG_arg_variable: c_uint = 0x101;
 163
 164 static DW_ATE_boolean: c_uint = 0x02;
 165 static DW_ATE_float: c_uint = 0x04;
 166 static DW_ATE_signed: c_uint = 0x05;
 167 // static DW_ATE_signed_char: c_uint = 0x06;
 168 static DW_ATE_unsigned: c_uint = 0x07;
 169 static DW_ATE_unsigned_char: c_uint = 0x08;
 170
 171 //=-------------------------------------------------------------------------------------------------
 172 //  Public Interface of debuginfo module
 173 //=-------------------------------------------------------------------------------------------------
 174
 175 /// A context object for maintaining all state needed by the debuginfo module.
 176 pub struct CrateDebugContext {
 177     llcontext: ContextRef,
 178     builder: DIBuilderRef,
 179     current_debug_location: Cell<DebugLocation>,
 180     created_files: RefCell<HashMap<~str, DIFile>>,
 181     created_types: RefCell<HashMap<uint, DIType>>,
 182     created_enum_disr_types: RefCell<HashMap<ast::DefId, DIType>>,
 183     namespace_map: RefCell<HashMap<Vec<ast::Name> , @NamespaceTreeNode>>,
 184     // This collection is used to assert that composite types (structs, enums, ...) have their
 185     // members only set once:
 186     composite_types_completed: RefCell<HashSet<DIType>>,
 187 }
 188
 189 impl CrateDebugContext {
 190     pub fn new(llmod: ModuleRef) -> CrateDebugContext {
 191         debug!("CrateDebugContext::new");
 192         let builder = unsafe { llvm::LLVMDIBuilderCreate(llmod) };
 193         // DIBuilder inherits context from the module, so we'd better use the same one
 194         let llcontext = unsafe { llvm::LLVMGetModuleContext(llmod) };
 195         return CrateDebugContext {
 196             llcontext: llcontext,
 197             builder: builder,
 198             current_debug_location: Cell::new(UnknownLocation),
 199             created_files: RefCell::new(HashMap::new()),
 200             created_types: RefCell::new(HashMap::new()),
 201             created_enum_disr_types: RefCell::new(HashMap::new()),
 202             namespace_map: RefCell::new(HashMap::new()),
 203             composite_types_completed: RefCell::new(HashSet::new()),
 204         };
 205     }
 206 }
 207
 208 pub struct FunctionDebugContext {
 209     repr: FunctionDebugContextRepr,
 210 }
 211
 212 enum FunctionDebugContextRepr {
 213     FunctionDebugContext(~FunctionDebugContextData),
 214     DebugInfoDisabled,
 215     FunctionWithoutDebugInfo,
 216 }
 217
 218 impl FunctionDebugContext {
 219     fn get_ref<'a>(&'a self, cx: &CrateContext, span: Span) -> &'a FunctionDebugContextData {
 220         match self.repr {
 221             FunctionDebugContext(~ref data) => data,
 222             DebugInfoDisabled => {
 223                 cx.sess().span_bug(span, FunctionDebugContext::debuginfo_disabled_message());
 224             }
 225             FunctionWithoutDebugInfo => {
 226                 cx.sess().span_bug(span, FunctionDebugContext::should_be_ignored_message());
 227             }
 228         }
 229     }
 230
 231     fn debuginfo_disabled_message() -> &'static str {
 232         "debuginfo: Error trying to access FunctionDebugContext although debug info is disabled!"
 233     }
 234
 235     fn should_be_ignored_message() -> &'static str {
 236         "debuginfo: Error trying to access FunctionDebugContext for function that should be \
 237          ignored by debug info!"
 238     }
 239 }
 240
 241 struct FunctionDebugContextData {
 242     scope_map: RefCell<HashMap<ast::NodeId, DIScope>>,
 243     fn_metadata: DISubprogram,
 244     argument_counter: Cell<uint>,
 245     source_locations_enabled: Cell<bool>,
 246 }
 247
 248 enum VariableAccess<'a> {
 249     // The llptr given is an alloca containing the variable's value
 250     DirectVariable { alloca: ValueRef },
 251     // The llptr given is an alloca containing the start of some pointer chain leading to the
 252     // variable's content.
 253     IndirectVariable { alloca: ValueRef, address_operations: &'a [ValueRef] }
 254 }
 255
 256 enum VariableKind {
 257     ArgumentVariable(uint /*index*/),
 258     LocalVariable,
 259     CapturedVariable,
 260 }
 261
 262 /// Create any deferred debug metadata nodes
 263 pub fn finalize(cx: &CrateContext) {
 264     if cx.dbg_cx.is_none() {
 265         return;
 266     }
 267
 268     debug!("finalize");
 269     compile_unit_metadata(cx);
 270     unsafe {
 271         llvm::LLVMDIBuilderFinalize(DIB(cx));
 272         llvm::LLVMDIBuilderDispose(DIB(cx));
 273         // Debuginfo generation in LLVM by default uses a higher
 274         // version of dwarf than OS X currently understands. We can
 275         // instruct LLVM to emit an older version of dwarf, however,
 276         // for OS X to understand. For more info see #11352
 277         // This can be overridden using --llvm-opts -dwarf-version,N.
 278         if cx.sess().targ_cfg.os == abi::OsMacos {
 279             "Dwarf Version".with_c_str(
 280                 |s| llvm::LLVMRustAddModuleFlag(cx.llmod, s, 2));
 281         }
 282
 283         // Prevent bitcode readers from deleting the debug info.
 284         "Debug Info Version".with_c_str(
 285             |s| llvm::LLVMRustAddModuleFlag(cx.llmod, s,
 286                                             llvm::LLVMRustDebugMetadataVersion));
 287     };
 288 }
 289
 290 /// Creates debug information for the given global variable.
 291 ///
 292 /// Adds the created metadata nodes directly to the crate's IR.
 293 pub fn create_global_var_metadata(cx: &CrateContext,
 294                                   node_id: ast::NodeId,
 295                                   global: ValueRef) {
 296     if cx.dbg_cx.is_none() {
 297         return;
 298     }
 299
 300     // Don't create debuginfo for globals inlined from other crates. The other crate should already
 301     // contain debuginfo for it. More importantly, the global might not even exist in un-inlined
 302     // form anywhere which would lead to a linker errors.
 303     if cx.external_srcs.borrow().contains_key(&node_id) {
 304         return;
 305     }
 306
 307     let var_item = cx.tcx.map.get(node_id);
 308
 309     let (ident, span) = match var_item {
 310         ast_map::NodeItem(item) => {
 311             match item.node {
 312                 ast::ItemStatic(..) => (item.ident, item.span),
 313                 _ => cx.sess().span_bug(item.span,
 314                                         format!("debuginfo::create_global_var_metadata() -
 315                                                 Captured var-id refers to unexpected ast_item
 316                                                 variant: {:?}",
 317                                                 var_item))
 318             }
 319         },
 320         _ => cx.sess().bug(format!("debuginfo::create_global_var_metadata() - Captured var-id \
 321                                    refers to unexpected ast_map variant: {:?}",
 322                                    var_item))
 323     };
 324
 325     let filename = span_start(cx, span).file.name.clone();
 326     let file_metadata = file_metadata(cx, filename);
 327
 328     let is_local_to_unit = is_node_local_to_unit(cx, node_id);
 329     let loc = span_start(cx, span);
 330
 331     let variable_type = ty::node_id_to_type(cx.tcx(), node_id);
 332     let type_metadata = type_metadata(cx, variable_type, span);
 333
 334     let namespace_node = namespace_for_item(cx, ast_util::local_def(node_id));
 335     let var_name = token::get_ident(ident).get().to_str();
 336     let linkage_name = namespace_node.mangled_name_of_contained_item(var_name);
 337     let var_scope = namespace_node.scope;
 338
 339     var_name.with_c_str(|var_name| {
 340         linkage_name.with_c_str(|linkage_name| {
 341             unsafe {
 342                 llvm::LLVMDIBuilderCreateStaticVariable(DIB(cx),
 343                                                         var_scope,
 344                                                         var_name,
 345                                                         linkage_name,
 346                                                         file_metadata,
 347                                                         loc.line as c_uint,
 348                                                         type_metadata,
 349                                                         is_local_to_unit,
 350                                                         global,
 351                                                         ptr::null());
 352             }
 353         })
 354     });
 355 }
 356
 357 /// Creates debug information for the given local variable.
 358 ///
 359 /// Adds the created metadata nodes directly to the crate's IR.
 360 pub fn create_local_var_metadata(bcx: &Block, local: &ast::Local) {
 361     if fn_should_be_ignored(bcx.fcx) {
 362         return;
 363     }
 364
 365     let cx = bcx.ccx();
 366     let def_map = cx.tcx.def_map;
 367
 368     pat_util::pat_bindings(def_map, local.pat, |_, node_id, span, path_ref| {
 369         let var_ident = ast_util::path_to_ident(path_ref);
 370
 371         let datum = match bcx.fcx.lllocals.borrow().find_copy(&node_id) {
 372             Some(datum) => datum,
 373             None => {
 374                 bcx.sess().span_bug(span,
 375                     format!("no entry in lllocals table for {:?}",
 376                             node_id));
 377             }
 378         };
 379
 380         let scope_metadata = scope_metadata(bcx.fcx, node_id, span);
 381
 382         declare_local(bcx,
 383                       var_ident,
 384                       datum.ty,
 385                       scope_metadata,
 386                       DirectVariable { alloca: datum.val },
 387                       LocalVariable,
 388                       span);
 389     })
 390 }
 391
 392 /// Creates debug information for a variable captured in a closure.
 393 ///
 394 /// Adds the created metadata nodes directly to the crate's IR.
 395 pub fn create_captured_var_metadata(bcx: &Block,
 396                                     node_id: ast::NodeId,
 397                                     env_data_type: ty::t,
 398                                     env_pointer: ValueRef,
 399                                     env_index: uint,
 400                                     closure_store: ty::TraitStore,
 401                                     span: Span) {
 402     if fn_should_be_ignored(bcx.fcx) {
 403         return;
 404     }
 405
 406     let cx = bcx.ccx();
 407
 408     let ast_item = cx.tcx.map.find(node_id);
 409
 410     let variable_ident = match ast_item {
 411         None => {
 412             cx.sess().span_bug(span, "debuginfo::create_captured_var_metadata: node not found");
 413         }
 414         Some(ast_map::NodeLocal(pat)) | Some(ast_map::NodeArg(pat)) => {
 415             match pat.node {
 416                 ast::PatIdent(_, ref path, _) => {
 417                     ast_util::path_to_ident(path)
 418                 }
 419                 _ => {
 420                     cx.sess()
 421                       .span_bug(span,
 422                                 format!(
 423                                 "debuginfo::create_captured_var_metadata() - \
 424                                  Captured var-id refers to unexpected \
 425                                  ast_map variant: {:?}",
 426                                  ast_item));
 427                 }
 428             }
 429         }
 430         _ => {
 431             cx.sess().span_bug(span, format!("debuginfo::create_captured_var_metadata() - \
 432                 Captured var-id refers to unexpected ast_map variant: {:?}", ast_item));
 433         }
 434     };
 435
 436     let variable_type = node_id_type(bcx, node_id);
 437     let scope_metadata = bcx.fcx.debug_context.get_ref(cx, span).fn_metadata;
 438
 439     let llvm_env_data_type = type_of::type_of(cx, env_data_type);
 440     let byte_offset_of_var_in_env = machine::llelement_offset(cx, llvm_env_data_type, env_index);
 441
 442     let address_operations = unsafe {
 443         [llvm::LLVMDIBuilderCreateOpDeref(Type::i64(cx).to_ref()),
 444          llvm::LLVMDIBuilderCreateOpPlus(Type::i64(cx).to_ref()),
 445          C_i64(cx, byte_offset_of_var_in_env as i64),
 446          llvm::LLVMDIBuilderCreateOpDeref(Type::i64(cx).to_ref())]
 447     };
 448
 449     let address_op_count = match closure_store {
 450         ty::RegionTraitStore(..) => {
 451             address_operations.len()
 452         }
 453         ty::UniqTraitStore => {
 454             address_operations.len() - 1
 455         }
 456     };
 457
 458     let variable_access = IndirectVariable {
 459         alloca: env_pointer,
 460         address_operations: address_operations.slice_to(address_op_count)
 461     };
 462
 463     declare_local(bcx,
 464                   variable_ident,
 465                   variable_type,
 466                   scope_metadata,
 467                   variable_access,
 468                   CapturedVariable,
 469                   span);
 470 }
 471
 472 /// Creates debug information for a local variable introduced in the head of a match-statement arm.
 473 ///
 474 /// Adds the created metadata nodes directly to the crate's IR.
 475 pub fn create_match_binding_metadata(bcx: &Block,
 476                                      variable_ident: ast::Ident,
 477                                      node_id: ast::NodeId,
 478                                      span: Span,
 479                                      datum: Datum<Lvalue>) {
 480     if fn_should_be_ignored(bcx.fcx) {
 481         return;
 482     }
 483
 484     let scope_metadata = scope_metadata(bcx.fcx, node_id, span);
 485
 486     declare_local(bcx,
 487                   variable_ident,
 488                   datum.ty,
 489                   scope_metadata,
 490                   DirectVariable { alloca: datum.val },
 491                   LocalVariable,
 492                   span);
 493 }
 494
 495 /// Creates debug information for the given function argument.
 496 ///
 497 /// Adds the created metadata nodes directly to the crate's IR.
 498 pub fn create_argument_metadata(bcx: &Block, arg: &ast::Arg) {
 499     if fn_should_be_ignored(bcx.fcx) {
 500         return;
 501     }
 502
 503     let fcx = bcx.fcx;
 504     let cx = fcx.ccx;
 505
 506     let def_map = cx.tcx.def_map;
 507     let scope_metadata = bcx.fcx.debug_context.get_ref(cx, arg.pat.span).fn_metadata;
 508
 509     pat_util::pat_bindings(def_map, arg.pat, |_, node_id, span, path_ref| {
 510         let llarg = match bcx.fcx.llargs.borrow().find_copy(&node_id) {
 511             Some(v) => v,
 512             None => {
 513                 bcx.sess().span_bug(span,
 514                     format!("no entry in llargs table for {:?}",
 515                             node_id));
 516             }
 517         };
 518
 519         if unsafe { llvm::LLVMIsAAllocaInst(llarg.val) } == ptr::null() {
 520             cx.sess().span_bug(span, "debuginfo::create_argument_metadata() - \
 521                                     Referenced variable location is not an alloca!");
 522         }
 523
 524         let argument_ident = ast_util::path_to_ident(path_ref);
 525
 526         let argument_index = {
 527             let counter = &fcx.debug_context.get_ref(cx, span).argument_counter;
 528             let argument_index = counter.get();
 529             counter.set(argument_index + 1);
 530             argument_index
 531         };
 532
 533         declare_local(bcx,
 534                       argument_ident,
 535                       llarg.ty,
 536                       scope_metadata,
 537                       DirectVariable { alloca: llarg.val },
 538                       ArgumentVariable(argument_index),
 539                       span);
 540     })
 541 }
 542
 543 /// Sets the current debug location at the beginning of the span.
 544 ///
 545 /// Maps to a call to llvm::LLVMSetCurrentDebugLocation(...). The node_id parameter is used to
 546 /// reliably find the correct visibility scope for the code position.
 547 pub fn set_source_location(fcx: &FunctionContext,
 548                            node_id: ast::NodeId,
 549                            span: Span) {
 550     match fcx.debug_context.repr {
 551         DebugInfoDisabled => return,
 552         FunctionWithoutDebugInfo => {
 553             set_debug_location(fcx.ccx, UnknownLocation);
 554             return;
 555         }
 556         FunctionDebugContext(~ref function_debug_context) => {
 557             let cx = fcx.ccx;
 558
 559             debug!("set_source_location: {}", cx.sess().codemap().span_to_str(span));
 560
 561             if function_debug_context.source_locations_enabled.get() {
 562                 let loc = span_start(cx, span);
 563                 let scope = scope_metadata(fcx, node_id, span);
 564
 565                 set_debug_location(cx, DebugLocation::new(scope, loc.line, loc.col.to_uint()));
 566             } else {
 567                 set_debug_location(cx, UnknownLocation);
 568             }
 569         }
 570     }
 571 }
 572
 573 /// Clears the current debug location.
 574 ///
 575 /// Instructions generated hereafter won't be assigned a source location.
 576 pub fn clear_source_location(fcx: &FunctionContext) {
 577     if fn_should_be_ignored(fcx) {
 578         return;
 579     }
 580
 581     set_debug_location(fcx.ccx, UnknownLocation);
 582 }
 583
 584 /// Enables emitting source locations for the given functions.
 585 ///
 586 /// Since we don't want source locations to be emitted for the function prelude, they are disabled
 587 /// when beginning to translate a new function. This functions switches source location emitting on
 588 /// and must therefore be called before the first real statement/expression of the function is
 589 /// translated.
 590 pub fn start_emitting_source_locations(fcx: &FunctionContext) {
 591     match fcx.debug_context.repr {
 592         FunctionDebugContext(~ref data) => {
 593             data.source_locations_enabled.set(true)
 594         },
 595         _ => { /* safe to ignore */ }
 596     }
 597 }
 598
 599 /// Creates the function-specific debug context.
 600 ///
 601 /// Returns the FunctionDebugContext for the function which holds state needed for debug info
 602 /// creation. The function may also return another variant of the FunctionDebugContext enum which
 603 /// indicates why no debuginfo should be created for the function.
 604 pub fn create_function_debug_context(cx: &CrateContext,
 605                                      fn_ast_id: ast::NodeId,
 606                                      param_substs: Option<@param_substs>,
 607                                      llfn: ValueRef) -> FunctionDebugContext {
 608     if cx.sess().opts.debuginfo == NoDebugInfo {
 609         return FunctionDebugContext { repr: DebugInfoDisabled };
 610     }
 611
 612     // Clear the debug location so we don't assign them in the function prelude. Do this here
 613     // already, in case we do an early exit from this function.
 614     set_debug_location(cx, UnknownLocation);
 615
 616     if fn_ast_id == -1 {
 617         return FunctionDebugContext { repr: FunctionWithoutDebugInfo };
 618     }
 619
 620     let empty_generics = ast::Generics { lifetimes: Vec::new(), ty_params: OwnedSlice::empty() };
 621
 622     let fnitem = cx.tcx.map.get(fn_ast_id);
 623
 624     let (ident, fn_decl, generics, top_level_block, span, has_path) = match fnitem {
 625         ast_map::NodeItem(ref item) => {
 626             match item.node {
 627                 ast::ItemFn(fn_decl, _, _, ref generics, top_level_block) => {
 628                     (item.ident, fn_decl, generics, top_level_block, item.span, true)
 629                 }
 630                 _ => {
 631                     cx.sess().span_bug(item.span,
 632                         "create_function_debug_context: item bound to non-function");
 633                 }
 634             }
 635         }
 636         ast_map::NodeMethod(method) => {
 637             (method.ident,
 638              method.decl,
 639              &method.generics,
 640              method.body,
 641              method.span,
 642              true)
 643         }
 644         ast_map::NodeExpr(ref expr) => {
 645             match expr.node {
 646                 ast::ExprFnBlock(fn_decl, top_level_block) |
 647                 ast::ExprProc(fn_decl, top_level_block) => {
 648                     let name = format!("fn{}", token::gensym("fn"));
 649                     let name = token::str_to_ident(name);
 650                     (name, fn_decl,
 651                         // This is not quite right. It should actually inherit the generics of the
 652                         // enclosing function.
 653                         &empty_generics,
 654                         top_level_block,
 655                         expr.span,
 656                         // Don't try to lookup the item path:
 657                         false)
 658                 }
 659                 _ => cx.sess().span_bug(expr.span,
 660                         "create_function_debug_context: expected an expr_fn_block here")
 661             }
 662         }
 663         ast_map::NodeTraitMethod(trait_method) => {
 664             match *trait_method {
 665                 ast::Provided(method) => {
 666                     (method.ident,
 667                      method.decl,
 668                      &method.generics,
 669                      method.body,
 670                      method.span,
 671                      true)
 672                 }
 673                 _ => {
 674                     cx.sess()
 675                       .bug(format!("create_function_debug_context: \
 676                                     unexpected sort of node: {:?}",
 677                                     fnitem))
 678                 }
 679             }
 680         }
 681         ast_map::NodeForeignItem(..) |
 682         ast_map::NodeVariant(..) |
 683         ast_map::NodeStructCtor(..) => {
 684             return FunctionDebugContext { repr: FunctionWithoutDebugInfo };
 685         }
 686         _ => cx.sess().bug(format!("create_function_debug_context: \
 687                                     unexpected sort of node: {:?}", fnitem))
 688     };
 689
 690     // This can be the case for functions inlined from another crate
 691     if span == codemap::DUMMY_SP {
 692         return FunctionDebugContext { repr: FunctionWithoutDebugInfo };
 693     }
 694
 695     let loc = span_start(cx, span);
 696     let file_metadata = file_metadata(cx, loc.file.name);
 697
 698     let function_type_metadata = unsafe {
 699         let fn_signature = get_function_signature(cx, fn_ast_id, fn_decl, param_substs, span);
 700         llvm::LLVMDIBuilderCreateSubroutineType(DIB(cx), file_metadata, fn_signature)
 701     };
 702
 703     // get_template_parameters() will append a `<...>` clause to the function name if necessary.
 704     let mut function_name = StrBuf::from_str(token::get_ident(ident).get());
 705     let template_parameters = get_template_parameters(cx,
 706                                                       generics,
 707                                                       param_substs,
 708                                                       file_metadata,
 709                                                       &mut function_name);
 710
 711     // There is no ast_map::Path for ast::ExprFnBlock-type functions. For now, just don't put them
 712     // into a namespace. In the future this could be improved somehow (storing a path in the
 713     // ast_map, or construct a path using the enclosing function).
 714     let (linkage_name, containing_scope) = if has_path {
 715         let namespace_node = namespace_for_item(cx, ast_util::local_def(fn_ast_id));
 716         let linkage_name = namespace_node.mangled_name_of_contained_item(
 717             function_name.as_slice());
 718         let containing_scope = namespace_node.scope;
 719         (linkage_name, containing_scope)
 720     } else {
 721         (function_name.as_slice().to_owned(), file_metadata)
 722     };
 723
 724     // Clang sets this parameter to the opening brace of the function's block, so let's do this too.
 725     let scope_line = span_start(cx, top_level_block.span).line;
 726
 727     let is_local_to_unit = is_node_local_to_unit(cx, fn_ast_id);
 728
 729     let fn_metadata = function_name.as_slice().with_c_str(|function_name| {
 730                           linkage_name.with_c_str(|linkage_name| {
 731             unsafe {
 732                 llvm::LLVMDIBuilderCreateFunction(
 733                     DIB(cx),
 734                     containing_scope,
 735                     function_name,
 736                     linkage_name,
 737                     file_metadata,
 738                     loc.line as c_uint,
 739                     function_type_metadata,
 740                     is_local_to_unit,
 741                     true,
 742                     scope_line as c_uint,
 743                     FlagPrototyped as c_uint,
 744                     cx.sess().opts.optimize != session::No,
 745                     llfn,
 746                     template_parameters,
 747                     ptr::null())
 748             }
 749         })
 750     });
 751
 752     // Initialize fn debug context (including scope map and namespace map)
 753     let fn_debug_context = ~FunctionDebugContextData {
 754         scope_map: RefCell::new(HashMap::new()),
 755         fn_metadata: fn_metadata,
 756         argument_counter: Cell::new(1),
 757         source_locations_enabled: Cell::new(false),
 758     };
 759
 760     let arg_pats = fn_decl.inputs.iter().map(|arg_ref| arg_ref.pat).collect::<Vec<_>>();
 761     populate_scope_map(cx,
 762                        arg_pats.as_slice(),
 763                        top_level_block,
 764                        fn_metadata,
 765                        &mut *fn_debug_context.scope_map.borrow_mut());
 766
 767     return FunctionDebugContext { repr: FunctionDebugContext(fn_debug_context) };
 768
 769     fn get_function_signature(cx: &CrateContext,
 770                               fn_ast_id: ast::NodeId,
 771                               fn_decl: &ast::FnDecl,
 772                               param_substs: Option<@param_substs>,
 773                               error_span: Span) -> DIArray {
 774         if cx.sess().opts.debuginfo == LimitedDebugInfo {
 775             return create_DIArray(DIB(cx), []);
 776         }
 777
 778         let mut signature = Vec::with_capacity(fn_decl.inputs.len() + 1);
 779
 780         // Return type -- llvm::DIBuilder wants this at index 0
 781         match fn_decl.output.node {
 782             ast::TyNil => {
 783                 signature.push(ptr::null());
 784             }
 785             _ => {
 786                 assert_type_for_node_id(cx, fn_ast_id, error_span);
 787
 788                 let return_type = ty::node_id_to_type(cx.tcx(), fn_ast_id);
 789                 let return_type = match param_substs {
 790                     None => return_type,
 791                     Some(substs) => {
 792                         ty::subst_tps(cx.tcx(),
 793                                       substs.tys.as_slice(),
 794                                       substs.self_ty,
 795                                       return_type)
 796                     }
 797                 };
 798
 799                 signature.push(type_metadata(cx, return_type, codemap::DUMMY_SP));
 800             }
 801         }
 802
 803         // Arguments types
 804         for arg in fn_decl.inputs.iter() {
 805             assert_type_for_node_id(cx, arg.pat.id, arg.pat.span);
 806             let arg_type = ty::node_id_to_type(cx.tcx(), arg.pat.id);
 807             let arg_type = match param_substs {
 808                 None => arg_type,
 809                 Some(substs) => {
 810                     ty::subst_tps(cx.tcx(),
 811                                   substs.tys.as_slice(),
 812                                   substs.self_ty,
 813                                   arg_type)
 814                 }
 815             };
 816
 817             signature.push(type_metadata(cx, arg_type, codemap::DUMMY_SP));
 818         }
 819
 820         return create_DIArray(DIB(cx), signature.as_slice());
 821     }
 822
 823     fn get_template_parameters(cx: &CrateContext,
 824                                generics: &ast::Generics,
 825                                param_substs: Option<@param_substs>,
 826                                file_metadata: DIFile,
 827                                name_to_append_suffix_to: &mut StrBuf)
 828                                -> DIArray {
 829         let self_type = match param_substs {
 830             Some(param_substs) => param_substs.self_ty,
 831             _ => None
 832         };
 833
 834         // Only true for static default methods:
 835         let has_self_type = self_type.is_some();
 836
 837         if !generics.is_type_parameterized() && !has_self_type {
 838             return create_DIArray(DIB(cx), []);
 839         }
 840
 841         name_to_append_suffix_to.push_char('<');
 842
 843         // The list to be filled with template parameters:
 844         let mut template_params: Vec<DIDescriptor> =
 845             Vec::with_capacity(generics.ty_params.len() + 1);
 846
 847         // Handle self type
 848         if has_self_type {
 849             let actual_self_type = self_type.unwrap();
 850             // Add self type name to <...> clause of function name
 851             let actual_self_type_name = ppaux::ty_to_str(cx.tcx(), actual_self_type);
 852             name_to_append_suffix_to.push_str(actual_self_type_name);
 853
 854             if generics.is_type_parameterized() {
 855                 name_to_append_suffix_to.push_str(",");
 856             }
 857
 858             // Only create type information if full debuginfo is enabled
 859             if cx.sess().opts.debuginfo == FullDebugInfo {
 860                 let actual_self_type_metadata = type_metadata(cx,
 861                                                               actual_self_type,
 862                                                               codemap::DUMMY_SP);
 863
 864                 let ident = special_idents::type_self;
 865
 866                 let param_metadata = token::get_ident(ident).get()
 867                                                             .with_c_str(|name| {
 868                     unsafe {
 869                         llvm::LLVMDIBuilderCreateTemplateTypeParameter(
 870                             DIB(cx),
 871                             file_metadata,
 872                             name,
 873                             actual_self_type_metadata,
 874                             ptr::null(),
 875                             0,
 876                             0)
 877                     }
 878                 });
 879
 880                 template_params.push(param_metadata);
 881             }
 882         }
 883
 884         // Handle other generic parameters
 885         let actual_types = match param_substs {
 886             Some(param_substs) => &param_substs.tys,
 887             None => {
 888                 return create_DIArray(DIB(cx), template_params.as_slice());
 889             }
 890         };
 891
 892         for (index, &ast::TyParam{ ident: ident, .. }) in generics.ty_params.iter().enumerate() {
 893             let actual_type = *actual_types.get(index);
 894             // Add actual type name to <...> clause of function name
 895             let actual_type_name = ppaux::ty_to_str(cx.tcx(), actual_type);
 896             name_to_append_suffix_to.push_str(actual_type_name);
 897
 898             if index != generics.ty_params.len() - 1 {
 899                 name_to_append_suffix_to.push_str(",");
 900             }
 901
 902             // Again, only create type information if full debuginfo is enabled
 903             if cx.sess().opts.debuginfo == FullDebugInfo {
 904                 let actual_type_metadata = type_metadata(cx, actual_type, codemap::DUMMY_SP);
 905                 let param_metadata = token::get_ident(ident).get()
 906                                                             .with_c_str(|name| {
 907                     unsafe {
 908                         llvm::LLVMDIBuilderCreateTemplateTypeParameter(
 909                             DIB(cx),
 910                             file_metadata,
 911                             name,
 912                             actual_type_metadata,
 913                             ptr::null(),
 914                             0,
 915                             0)
 916                     }
 917                 });
 918                 template_params.push(param_metadata);
 919             }
 920         }
 921
 922         name_to_append_suffix_to.push_char('>');
 923
 924         return create_DIArray(DIB(cx), template_params.as_slice());
 925     }
 926 }
 927
 928 //=-------------------------------------------------------------------------------------------------
 929 // Module-Internal debug info creation functions
 930 //=-------------------------------------------------------------------------------------------------
 931
 932 fn is_node_local_to_unit(cx: &CrateContext, node_id: ast::NodeId) -> bool
 933 {
 934     // The is_local_to_unit flag indicates whether a function is local to the current compilation
 935     // unit (i.e. if it is *static* in the C-sense). The *reachable* set should provide a good
 936     // approximation of this, as it contains everything that might leak out of the current crate
 937     // (by being externally visible or by being inlined into something externally visible). It might
 938     // better to use the `exported_items` set from `driver::CrateAnalysis` in the future, but (atm)
 939     // this set is not available in the translation pass.
 940     !cx.reachable.contains(&node_id)
 941 }
 942
 943 fn create_DIArray(builder: DIBuilderRef, arr: &[DIDescriptor]) -> DIArray {
 944     return unsafe {
 945         llvm::LLVMDIBuilderGetOrCreateArray(builder, arr.as_ptr(), arr.len() as u32)
 946     };
 947 }
 948
 949 fn compile_unit_metadata(cx: &CrateContext) {
 950     let work_dir = &cx.sess().working_dir;
 951     let compile_unit_name = match cx.sess().local_crate_source_file {
 952         None => fallback_path(cx),
 953         Some(ref abs_path) => {
 954             if abs_path.is_relative() {
 955                 cx.sess().warn("debuginfo: Invalid path to crate's local root source file!");
 956                 fallback_path(cx)
 957             } else {
 958                 match abs_path.path_relative_from(work_dir) {
 959                     Some(ref p) if p.is_relative() => {
 960                             // prepend "./" if necessary
 961                             let dotdot = bytes!("..");
 962                             let prefix = &[dotdot[0], ::std::path::SEP_BYTE];
 963                             let mut path_bytes = Vec::from_slice(p.as_vec());
 964
 965                             if path_bytes.slice_to(2) != prefix &&
 966                                path_bytes.slice_to(2) != dotdot {
 967                                 path_bytes.insert(0, prefix[0]);
 968                                 path_bytes.insert(1, prefix[1]);
 969                             }
 970
 971                             path_bytes.as_slice().to_c_str()
 972                         }
 973                     _ => fallback_path(cx)
 974                 }
 975             }
 976         }
 977     };
 978
 979     debug!("compile_unit_metadata: {:?}", compile_unit_name);
 980     let producer = format!("rustc version {}", env!("CFG_VERSION"));
 981
 982     compile_unit_name.with_ref(|compile_unit_name| {
 983         work_dir.as_vec().with_c_str(|work_dir| {
 984             producer.with_c_str(|producer| {
 985                 "".with_c_str(|flags| {
 986                     "".with_c_str(|split_name| {
 987                         unsafe {
 988                             llvm::LLVMDIBuilderCreateCompileUnit(
 989                                 debug_context(cx).builder,
 990                                 DW_LANG_RUST,
 991                                 compile_unit_name,
 992                                 work_dir,
 993                                 producer,
 994                                 cx.sess().opts.optimize != session::No,
 995                                 flags,
 996                                 0,
 997                                 split_name);
 998                         }
 999                     })
1000                 })
1001             })
1002         })
1003     });
1004
1005     fn fallback_path(cx: &CrateContext) -> CString {
1006         cx.link_meta.crateid.name.to_c_str()
1007     }
1008 }
1009
1010 fn declare_local(bcx: &Block,
1011                  variable_ident: ast::Ident,
1012                  variable_type: ty::t,
1013                  scope_metadata: DIScope,
1014                  variable_access: VariableAccess,
1015                  variable_kind: VariableKind,
1016                  span: Span) {
1017     let cx: &CrateContext = bcx.ccx();
1018
1019     let filename = span_start(cx, span).file.name.clone();
1020     let file_metadata = file_metadata(cx, filename);
1021
1022     let name = token::get_ident(variable_ident);
1023     let loc = span_start(cx, span);
1024     let type_metadata = type_metadata(cx, variable_type, span);
1025
1026     let (argument_index, dwarf_tag) = match variable_kind {
1027         ArgumentVariable(index) => (index as c_uint, DW_TAG_arg_variable),
1028         LocalVariable    |
1029         CapturedVariable => (0, DW_TAG_auto_variable)
1030     };
1031
1032     let (var_alloca, var_metadata) = name.get().with_c_str(|name| {
1033         match variable_access {
1034             DirectVariable { alloca } => (
1035                 alloca,
1036                 unsafe {
1037                     llvm::LLVMDIBuilderCreateLocalVariable(
1038                         DIB(cx),
1039                         dwarf_tag,
1040                         scope_metadata,
1041                         name,
1042                         file_metadata,
1043                         loc.line as c_uint,
1044                         type_metadata,
1045                         cx.sess().opts.optimize != session::No,
1046                         0,
1047                         argument_index)
1048                 }
1049             ),
1050             IndirectVariable { alloca, address_operations } => (
1051                 alloca,
1052                 unsafe {
1053                     llvm::LLVMDIBuilderCreateComplexVariable(
1054                         DIB(cx),
1055                         dwarf_tag,
1056                         scope_metadata,
1057                         name,
1058                         file_metadata,
1059                         loc.line as c_uint,
1060                         type_metadata,
1061                         address_operations.as_ptr(),
1062                         address_operations.len() as c_uint,
1063                         argument_index)
1064                 }
1065             )
1066         }
1067     });
1068
1069     set_debug_location(cx, DebugLocation::new(scope_metadata, loc.line, loc.col.to_uint()));
1070     unsafe {
1071         let instr = llvm::LLVMDIBuilderInsertDeclareAtEnd(
1072             DIB(cx),
1073             var_alloca,
1074             var_metadata,
1075             bcx.llbb);
1076
1077         llvm::LLVMSetInstDebugLocation(trans::build::B(bcx).llbuilder, instr);
1078     }
1079
1080     match variable_kind {
1081         ArgumentVariable(_) | CapturedVariable => {
1082             assert!(!bcx.fcx
1083                         .debug_context
1084                         .get_ref(cx, span)
1085                         .source_locations_enabled
1086                         .get());
1087             set_debug_location(cx, UnknownLocation);
1088         }
1089         _ => { /* nothing to do */ }
1090     }
1091 }
1092
1093 fn file_metadata(cx: &CrateContext, full_path: &str) -> DIFile {
1094     match debug_context(cx).created_files.borrow().find_equiv(&full_path) {
1095         Some(file_metadata) => return *file_metadata,
1096         None => ()
1097     }
1098
1099     debug!("file_metadata: {}", full_path);
1100
1101     // FIXME (#9639): This needs to handle non-utf8 paths
1102     let work_dir = cx.sess().working_dir.as_str().unwrap();
1103     let file_name =
1104         if full_path.starts_with(work_dir) {
1105             full_path.slice(work_dir.len() + 1u, full_path.len())
1106         } else {
1107             full_path
1108         };
1109
1110     let file_metadata =
1111         file_name.with_c_str(|file_name| {
1112             work_dir.with_c_str(|work_dir| {
1113                 unsafe {
1114                     llvm::LLVMDIBuilderCreateFile(DIB(cx), file_name, work_dir)
1115                 }
1116             })
1117         });
1118
1119     let mut created_files = debug_context(cx).created_files.borrow_mut();
1120     created_files.insert(full_path.to_owned(), file_metadata);
1121     return file_metadata;
1122 }
1123
1124 /// Finds the scope metadata node for the given AST node.
1125 fn scope_metadata(fcx: &FunctionContext,
1126                   node_id: ast::NodeId,
1127                   span: Span)
1128                -> DIScope {
1129     let scope_map = &fcx.debug_context.get_ref(fcx.ccx, span).scope_map;
1130     match scope_map.borrow().find_copy(&node_id) {
1131         Some(scope_metadata) => scope_metadata,
1132         None => {
1133             let node = fcx.ccx.tcx.map.get(node_id);
1134
1135             fcx.ccx.sess().span_bug(span,
1136                 format!("debuginfo: Could not find scope info for node {:?}", node));
1137         }
1138     }
1139 }
1140
1141 fn basic_type_metadata(cx: &CrateContext, t: ty::t) -> DIType {
1142
1143     debug!("basic_type_metadata: {:?}", ty::get(t));
1144
1145     let (name, encoding) = match ty::get(t).sty {
1146         ty::ty_nil => ("()".to_owned(), DW_ATE_unsigned),
1147         ty::ty_bot => ("!".to_owned(), DW_ATE_unsigned),
1148         ty::ty_bool => ("bool".to_owned(), DW_ATE_boolean),
1149         ty::ty_char => ("char".to_owned(), DW_ATE_unsigned_char),
1150         ty::ty_int(int_ty) => match int_ty {
1151             ast::TyI => ("int".to_owned(), DW_ATE_signed),
1152             ast::TyI8 => ("i8".to_owned(), DW_ATE_signed),
1153             ast::TyI16 => ("i16".to_owned(), DW_ATE_signed),
1154             ast::TyI32 => ("i32".to_owned(), DW_ATE_signed),
1155             ast::TyI64 => ("i64".to_owned(), DW_ATE_signed)
1156         },
1157         ty::ty_uint(uint_ty) => match uint_ty {
1158             ast::TyU => ("uint".to_owned(), DW_ATE_unsigned),
1159             ast::TyU8 => ("u8".to_owned(), DW_ATE_unsigned),
1160             ast::TyU16 => ("u16".to_owned(), DW_ATE_unsigned),
1161             ast::TyU32 => ("u32".to_owned(), DW_ATE_unsigned),
1162             ast::TyU64 => ("u64".to_owned(), DW_ATE_unsigned)
1163         },
1164         ty::ty_float(float_ty) => match float_ty {
1165             ast::TyF32 => ("f32".to_owned(), DW_ATE_float),
1166             ast::TyF64 => ("f64".to_owned(), DW_ATE_float)
1167         },
1168         _ => cx.sess().bug("debuginfo::basic_type_metadata - t is invalid type")
1169     };
1170
1171     let llvm_type = type_of::type_of(cx, t);
1172     let (size, align) = size_and_align_of(cx, llvm_type);
1173     let ty_metadata = name.with_c_str(|name| {
1174         unsafe {
1175             llvm::LLVMDIBuilderCreateBasicType(
1176                 DIB(cx),
1177                 name,
1178                 bytes_to_bits(size),
1179                 bytes_to_bits(align),
1180                 encoding)
1181         }
1182     });
1183
1184     return ty_metadata;
1185 }
1186
1187 fn pointer_type_metadata(cx: &CrateContext,
1188                          pointer_type: ty::t,
1189                          pointee_type_metadata: DIType)
1190                       -> DIType {
1191     let pointer_llvm_type = type_of::type_of(cx, pointer_type);
1192     let (pointer_size, pointer_align) = size_and_align_of(cx, pointer_llvm_type);
1193     let name = ppaux::ty_to_str(cx.tcx(), pointer_type);
1194     let ptr_metadata = name.with_c_str(|name| {
1195         unsafe {
1196             llvm::LLVMDIBuilderCreatePointerType(
1197                 DIB(cx),
1198                 pointee_type_metadata,
1199                 bytes_to_bits(pointer_size),
1200                 bytes_to_bits(pointer_align),
1201                 name)
1202         }
1203     });
1204     return ptr_metadata;
1205 }
1206
1207 enum MemberDescriptionFactory {
1208     StructMD(StructMemberDescriptionFactory),
1209     TupleMD(TupleMemberDescriptionFactory),
1210     GeneralMD(GeneralMemberDescriptionFactory),
1211     EnumVariantMD(EnumVariantMemberDescriptionFactory)
1212 }
1213
1214 impl MemberDescriptionFactory {
1215     fn create_member_descriptions(&self, cx: &CrateContext)
1216                                   -> Vec<MemberDescription> {
1217         match *self {
1218             StructMD(ref this) => {
1219                 this.create_member_descriptions(cx)
1220             }
1221             TupleMD(ref this) => {
1222                 this.create_member_descriptions(cx)
1223             }
1224             GeneralMD(ref this) => {
1225                 this.create_member_descriptions(cx)
1226             }
1227             EnumVariantMD(ref this) => {
1228                 this.create_member_descriptions(cx)
1229             }
1230         }
1231     }
1232 }
1233
1234 struct StructMemberDescriptionFactory {
1235     fields: Vec<ty::field> ,
1236     span: Span,
1237 }
1238
1239 impl StructMemberDescriptionFactory {
1240     fn create_member_descriptions(&self, cx: &CrateContext)
1241                                   -> Vec<MemberDescription> {
1242         self.fields.iter().map(|field| {
1243             let name = if field.ident.name == special_idents::unnamed_field.name {
1244                 "".to_owned()
1245             } else {
1246                 token::get_ident(field.ident).get().to_str()
1247             };
1248
1249             MemberDescription {
1250                 name: name,
1251                 llvm_type: type_of::type_of(cx, field.mt.ty),
1252                 type_metadata: type_metadata(cx, field.mt.ty, self.span),
1253                 offset: ComputedMemberOffset,
1254             }
1255         }).collect()
1256     }
1257 }
1258
1259 fn prepare_struct_metadata(cx: &CrateContext,
1260                            struct_type: ty::t,
1261                            def_id: ast::DefId,
1262                            substs: &ty::substs,
1263                            span: Span)
1264                         -> RecursiveTypeDescription {
1265     let struct_name = ppaux::ty_to_str(cx.tcx(), struct_type);
1266     let struct_llvm_type = type_of::type_of(cx, struct_type);
1267
1268     let (containing_scope, definition_span) = get_namespace_and_span_for_item(cx, def_id);
1269
1270     let file_name = span_start(cx, definition_span).file.name.clone();
1271     let file_metadata = file_metadata(cx, file_name);
1272
1273     let struct_metadata_stub = create_struct_stub(cx,
1274                                                   struct_llvm_type,
1275                                                   struct_name,
1276                                                   containing_scope,
1277                                                   file_metadata,
1278                                                   definition_span);
1279
1280     let fields = ty::struct_fields(cx.tcx(), def_id, substs);
1281
1282     UnfinishedMetadata {
1283         cache_id: cache_id_for_type(struct_type),
1284         metadata_stub: struct_metadata_stub,
1285         llvm_type: struct_llvm_type,
1286         file_metadata: file_metadata,
1287         member_description_factory: StructMD(StructMemberDescriptionFactory {
1288             fields: fields,
1289             span: span,
1290         }),
1291     }
1292 }
1293
1294 enum RecursiveTypeDescription {
1295     UnfinishedMetadata {
1296         cache_id: uint,
1297         metadata_stub: DICompositeType,
1298         llvm_type: Type,
1299         file_metadata: DIFile,
1300         member_description_factory: MemberDescriptionFactory,
1301     },
1302     FinalMetadata(DICompositeType)
1303 }
1304
1305 impl RecursiveTypeDescription {
1306
1307     fn finalize(&self, cx: &CrateContext) -> DICompositeType {
1308         match *self {
1309             FinalMetadata(metadata) => metadata,
1310             UnfinishedMetadata {
1311                 cache_id,
1312                 metadata_stub,
1313                 llvm_type,
1314                 file_metadata,
1315                 ref member_description_factory
1316             } => {
1317                 // Insert the stub into the cache in order to allow recursive references ...
1318                 debug_context(cx).created_types.borrow_mut()
1319                                  .insert(cache_id, metadata_stub);
1320
1321                 // ... then create the member descriptions ...
1322                 let member_descriptions = member_description_factory.create_member_descriptions(cx);
1323
1324                 // ... and attach them to the stub to complete it.
1325                 set_members_of_composite_type(cx,
1326                                               metadata_stub,
1327                                               llvm_type,
1328                                               member_descriptions.as_slice(),
1329                                               file_metadata,
1330                                               codemap::DUMMY_SP);
1331                 return metadata_stub;
1332             }
1333         }
1334     }
1335 }
1336
1337 struct TupleMemberDescriptionFactory {
1338     component_types: Vec<ty::t> ,
1339     span: Span,
1340 }
1341
1342 impl TupleMemberDescriptionFactory {
1343     fn create_member_descriptions(&self, cx: &CrateContext)
1344                                   -> Vec<MemberDescription> {
1345         self.component_types.iter().map(|&component_type| {
1346             MemberDescription {
1347                 name: "".to_owned(),
1348                 llvm_type: type_of::type_of(cx, component_type),
1349                 type_metadata: type_metadata(cx, component_type, self.span),
1350                 offset: ComputedMemberOffset,
1351             }
1352         }).collect()
1353     }
1354 }
1355
1356 fn prepare_tuple_metadata(cx: &CrateContext,
1357                           tuple_type: ty::t,
1358                           component_types: &[ty::t],
1359                           span: Span)
1360                        -> RecursiveTypeDescription {
1361     let tuple_name = ppaux::ty_to_str(cx.tcx(), tuple_type);
1362     let tuple_llvm_type = type_of::type_of(cx, tuple_type);
1363
1364     let loc = span_start(cx, span);
1365     let file_metadata = file_metadata(cx, loc.file.name);
1366
1367     UnfinishedMetadata {
1368         cache_id: cache_id_for_type(tuple_type),
1369         metadata_stub: create_struct_stub(cx,
1370                                           tuple_llvm_type,
1371                                           tuple_name,
1372                                           file_metadata,
1373                                           file_metadata,
1374                                           span),
1375         llvm_type: tuple_llvm_type,
1376         file_metadata: file_metadata,
1377         member_description_factory: TupleMD(TupleMemberDescriptionFactory {
1378             component_types: Vec::from_slice(component_types),
1379             span: span,
1380         })
1381     }
1382 }
1383
1384 struct GeneralMemberDescriptionFactory {
1385     type_rep: @adt::Repr,
1386     variants: @Vec<@ty::VariantInfo> ,
1387     discriminant_type_metadata: ValueRef,
1388     containing_scope: DIScope,
1389     file_metadata: DIFile,
1390     span: Span,
1391 }
1392
1393 impl GeneralMemberDescriptionFactory {
1394     fn create_member_descriptions(&self, cx: &CrateContext)
1395                                   -> Vec<MemberDescription> {
1396         // Capture type_rep, so we don't have to copy the struct_defs array
1397         let struct_defs = match *self.type_rep {
1398             adt::General(_, ref struct_defs) => struct_defs,
1399             _ => cx.sess().bug("unreachable")
1400         };
1401
1402         struct_defs
1403             .iter()
1404             .enumerate()
1405             .map(|(i, struct_def)| {
1406                 let (variant_type_metadata, variant_llvm_type, member_desc_factory) =
1407                     describe_enum_variant(cx,
1408                                           struct_def,
1409                                           *self.variants.get(i),
1410                                           Some(self.discriminant_type_metadata),
1411                                           self.containing_scope,
1412                                           self.file_metadata,
1413                                           self.span);
1414
1415                 let member_descriptions =
1416                     member_desc_factory.create_member_descriptions(cx);
1417
1418                 set_members_of_composite_type(cx,
1419                                               variant_type_metadata,
1420                                               variant_llvm_type,
1421                                               member_descriptions.as_slice(),
1422                                               self.file_metadata,
1423                                               codemap::DUMMY_SP);
1424                 MemberDescription {
1425                     name: "".to_owned(),
1426                     llvm_type: variant_llvm_type,
1427                     type_metadata: variant_type_metadata,
1428                     offset: FixedMemberOffset { bytes: 0 },
1429                 }
1430         }).collect()
1431     }
1432 }
1433
1434 struct EnumVariantMemberDescriptionFactory {
1435     args: Vec<(~str, ty::t)> ,
1436     discriminant_type_metadata: Option<DIType>,
1437     span: Span,
1438 }
1439
1440 impl EnumVariantMemberDescriptionFactory {
1441     fn create_member_descriptions(&self, cx: &CrateContext)
1442                                   -> Vec<MemberDescription> {
1443         self.args.iter().enumerate().map(|(i, &(ref name, ty))| {
1444             MemberDescription {
1445                 name: name.to_str(),
1446                 llvm_type: type_of::type_of(cx, ty),
1447                 type_metadata: match self.discriminant_type_metadata {
1448                     Some(metadata) if i == 0 => metadata,
1449                     _ => type_metadata(cx, ty, self.span)
1450                 },
1451                 offset: ComputedMemberOffset,
1452             }
1453         }).collect()
1454     }
1455 }
1456
1457 fn describe_enum_variant(cx: &CrateContext,
1458                          struct_def: &adt::Struct,
1459                          variant_info: &ty::VariantInfo,
1460                          discriminant_type_metadata: Option<DIType>,
1461                          containing_scope: DIScope,
1462                          file_metadata: DIFile,
1463                          span: Span)
1464                       -> (DICompositeType, Type, MemberDescriptionFactory) {
1465     let variant_llvm_type =
1466         Type::struct_(cx, struct_def.fields
1467                                     .iter()
1468                                     .map(|&t| type_of::type_of(cx, t))
1469                                     .collect::<Vec<_>>()
1470                                     .as_slice(),
1471                       struct_def.packed);
1472     // Could some consistency checks here: size, align, field count, discr type
1473
1474     // Find the source code location of the variant's definition
1475     let variant_definition_span = if variant_info.id.krate == ast::LOCAL_CRATE {
1476         cx.tcx.map.span(variant_info.id.node)
1477     } else {
1478         // For definitions from other crates we have no location information available.
1479         codemap::DUMMY_SP
1480     };
1481
1482     let metadata_stub = create_struct_stub(cx,
1483                                            variant_llvm_type,
1484                                            token::get_ident(variant_info.name).get(),
1485                                            containing_scope,
1486                                            file_metadata,
1487                                            variant_definition_span);
1488
1489     // Get the argument names from the enum variant info
1490     let mut arg_names: Vec<_> = match variant_info.arg_names {
1491         Some(ref names) => {
1492             names.iter().map(|ident| token::get_ident(*ident).get().to_str()).collect()
1493         }
1494         None => variant_info.args.iter().map(|_| "".to_owned()).collect()
1495     };
1496
1497     // If this is not a univariant enum, there is also the (unnamed) discriminant field
1498     if discriminant_type_metadata.is_some() {
1499         arg_names.insert(0, "".to_owned());
1500     }
1501
1502     // Build an array of (field name, field type) pairs to be captured in the factory closure.
1503     let args: Vec<(~str, ty::t)> = arg_names.iter()
1504         .zip(struct_def.fields.iter())
1505         .map(|(s, &t)| (s.to_str(), t))
1506         .collect();
1507
1508     let member_description_factory =
1509         EnumVariantMD(EnumVariantMemberDescriptionFactory {
1510             args: args,
1511             discriminant_type_metadata: discriminant_type_metadata,
1512             span: span,
1513         });
1514
1515     (metadata_stub, variant_llvm_type, member_description_factory)
1516 }
1517
1518 fn prepare_enum_metadata(cx: &CrateContext,
1519                          enum_type: ty::t,
1520                          enum_def_id: ast::DefId,
1521                          span: Span)
1522                       -> RecursiveTypeDescription {
1523     let enum_name = ppaux::ty_to_str(cx.tcx(), enum_type);
1524
1525     let (containing_scope, definition_span) = get_namespace_and_span_for_item(cx, enum_def_id);
1526     let loc = span_start(cx, definition_span);
1527     let file_metadata = file_metadata(cx, loc.file.name);
1528
1529     // For empty enums there is an early exit. Just describe it as an empty struct with the
1530     // appropriate type name
1531     if ty::type_is_empty(cx.tcx(), enum_type) {
1532         let empty_type_metadata = composite_type_metadata(cx,
1533                                                           Type::nil(cx),
1534                                                           enum_name,
1535                                                           [],
1536                                                           containing_scope,
1537                                                           file_metadata,
1538                                                           definition_span);
1539
1540         return FinalMetadata(empty_type_metadata);
1541     }
1542
1543     let variants = ty::enum_variants(cx.tcx(), enum_def_id);
1544
1545     let enumerators_metadata: Vec<DIDescriptor> = variants
1546         .iter()
1547         .map(|v| {
1548             token::get_ident(v.name).get().with_c_str(|name| {
1549                 unsafe {
1550                     llvm::LLVMDIBuilderCreateEnumerator(
1551                         DIB(cx),
1552                         name,
1553                         v.disr_val as c_ulonglong)
1554                 }
1555             })
1556         })
1557         .collect();
1558
1559     let discriminant_type_metadata = |inttype| {
1560         // We can reuse the type of the discriminant for all monomorphized instances of an enum
1561         // because it doesn't depend on any type parameters. The def_id, uniquely identifying the
1562         // enum's polytype acts as key in this cache.
1563         let cached_discriminant_type_metadata = debug_context(cx).created_enum_disr_types
1564                                                                  .borrow()
1565                                                                  .find_copy(&enum_def_id);
1566         match cached_discriminant_type_metadata {
1567             Some(discriminant_type_metadata) => discriminant_type_metadata,
1568             None => {
1569                 let discriminant_llvm_type = adt::ll_inttype(cx, inttype);
1570                 let (discriminant_size, discriminant_align) =
1571                     size_and_align_of(cx, discriminant_llvm_type);
1572                 let discriminant_base_type_metadata = type_metadata(cx,
1573                                                                     adt::ty_of_inttype(inttype),
1574                                                                     codemap::DUMMY_SP);
1575                 let discriminant_name = get_enum_discriminant_name(cx, enum_def_id);
1576
1577                 let discriminant_type_metadata = discriminant_name.get().with_c_str(|name| {
1578                     unsafe {
1579                         llvm::LLVMDIBuilderCreateEnumerationType(
1580                             DIB(cx),
1581                             containing_scope,
1582                             name,
1583                             file_metadata,
1584                             loc.line as c_uint,
1585                             bytes_to_bits(discriminant_size),
1586                             bytes_to_bits(discriminant_align),
1587                             create_DIArray(DIB(cx), enumerators_metadata.as_slice()),
1588                             discriminant_base_type_metadata)
1589                     }
1590                 });
1591
1592                 debug_context(cx).created_enum_disr_types
1593                                  .borrow_mut()
1594                                  .insert(enum_def_id, discriminant_type_metadata);
1595
1596                 discriminant_type_metadata
1597             }
1598         }
1599     };
1600
1601     let type_rep = adt::represent_type(cx, enum_type);
1602
1603     return match *type_rep {
1604         adt::CEnum(inttype, _, _) => {
1605             FinalMetadata(discriminant_type_metadata(inttype))
1606         }
1607         adt::Univariant(ref struct_def, _) => {
1608             assert!(variants.len() == 1);
1609             let (metadata_stub,
1610                  variant_llvm_type,
1611                  member_description_factory) =
1612                     describe_enum_variant(cx,
1613                                           struct_def,
1614                                           *variants.get(0),
1615                                           None,
1616                                           containing_scope,
1617                                           file_metadata,
1618                                           span);
1619             UnfinishedMetadata {
1620                 cache_id: cache_id_for_type(enum_type),
1621                 metadata_stub: metadata_stub,
1622                 llvm_type: variant_llvm_type,
1623                 file_metadata: file_metadata,
1624                 member_description_factory: member_description_factory
1625             }
1626         }
1627         adt::General(inttype, _) => {
1628             let discriminant_type_metadata = discriminant_type_metadata(inttype);
1629             let enum_llvm_type = type_of::type_of(cx, enum_type);
1630             let (enum_type_size, enum_type_align) = size_and_align_of(cx, enum_llvm_type);
1631             let unique_id = generate_unique_type_id("DI_ENUM_");
1632
1633             let enum_metadata = enum_name.with_c_str(|enum_name| {
1634                 unique_id.with_c_str(|unique_id| {
1635                     unsafe {
1636                         llvm::LLVMDIBuilderCreateUnionType(
1637                         DIB(cx),
1638                         containing_scope,
1639                         enum_name,
1640                         file_metadata,
1641                         loc.line as c_uint,
1642                         bytes_to_bits(enum_type_size),
1643                         bytes_to_bits(enum_type_align),
1644                         0, // Flags
1645                         ptr::null(),
1646                         0, // RuntimeLang
1647                         unique_id)
1648                     }
1649                 })
1650             });
1651
1652             UnfinishedMetadata {
1653                 cache_id: cache_id_for_type(enum_type),
1654                 metadata_stub: enum_metadata,
1655                 llvm_type: enum_llvm_type,
1656                 file_metadata: file_metadata,
1657                 member_description_factory: GeneralMD(GeneralMemberDescriptionFactory {
1658                     type_rep: type_rep,
1659                     variants: variants,
1660                     discriminant_type_metadata: discriminant_type_metadata,
1661                     containing_scope: containing_scope,
1662                     file_metadata: file_metadata,
1663                     span: span,
1664                 }),
1665             }
1666         }
1667         adt::NullablePointer { nonnull: ref struct_def, nndiscr, .. } => {
1668             let (metadata_stub,
1669                  variant_llvm_type,
1670                  member_description_factory) =
1671                     describe_enum_variant(cx,
1672                                           struct_def,
1673                                           *variants.get(nndiscr as uint),
1674                                           None,
1675                                           containing_scope,
1676                                           file_metadata,
1677                                           span);
1678             UnfinishedMetadata {
1679                 cache_id: cache_id_for_type(enum_type),
1680                 metadata_stub: metadata_stub,
1681                 llvm_type: variant_llvm_type,
1682                 file_metadata: file_metadata,
1683                 member_description_factory: member_description_factory
1684             }
1685         }
1686     };
1687
1688     fn get_enum_discriminant_name(cx: &CrateContext, def_id: ast::DefId) -> token::InternedString {
1689         let name = if def_id.krate == ast::LOCAL_CRATE {
1690             cx.tcx.map.get_path_elem(def_id.node).name()
1691         } else {
1692             csearch::get_item_path(&cx.tcx, def_id).last().unwrap().name()
1693         };
1694
1695         token::get_name(name)
1696     }
1697 }
1698
1699 enum MemberOffset {
1700     FixedMemberOffset { bytes: uint },
1701     // For ComputedMemberOffset, the offset is read from the llvm type definition
1702     ComputedMemberOffset
1703 }
1704
1705 struct MemberDescription {
1706     name: ~str,
1707     llvm_type: Type,
1708     type_metadata: DIType,
1709     offset: MemberOffset,
1710 }
1711
1712 /// Creates debug information for a composite type, that is, anything that results in a LLVM struct.
1713 ///
1714 /// Examples of Rust types to use this are: structs, tuples, boxes, vecs, and enums.
1715 fn composite_type_metadata(cx: &CrateContext,
1716                            composite_llvm_type: Type,
1717                            composite_type_name: &str,
1718                            member_descriptions: &[MemberDescription],
1719                            containing_scope: DIScope,
1720                            file_metadata: DIFile,
1721                            definition_span: Span)
1722                         -> DICompositeType {
1723     // Create the (empty) struct metadata node ...
1724     let composite_type_metadata = create_struct_stub(cx,
1725                                                      composite_llvm_type,
1726                                                      composite_type_name,
1727                                                      containing_scope,
1728                                                      file_metadata,
1729                                                      definition_span);
1730
1731     // ... and immediately create and add the member descriptions.
1732     set_members_of_composite_type(cx,
1733                                   composite_type_metadata,
1734                                   composite_llvm_type,
1735                                   member_descriptions,
1736                                   file_metadata,
1737                                   definition_span);
1738
1739     return composite_type_metadata;
1740 }
1741
1742 fn set_members_of_composite_type(cx: &CrateContext,
1743                                  composite_type_metadata: DICompositeType,
1744                                  composite_llvm_type: Type,
1745                                  member_descriptions: &[MemberDescription],
1746                                  file_metadata: DIFile,
1747                                  definition_span: Span) {
1748     // In some rare cases LLVM metadata uniquing would lead to an existing type description being
1749     // used instead of a new one created in create_struct_stub. This would cause a hard to trace
1750     // assertion in DICompositeType::SetTypeArray(). The following check makes sure that we get a
1751     // better error message if this should happen again due to some regression.
1752     {
1753         let mut composite_types_completed =
1754             debug_context(cx).composite_types_completed.borrow_mut();
1755         if composite_types_completed.contains(&composite_type_metadata) {
1756             cx.sess().span_bug(definition_span, "debuginfo::set_members_of_composite_type() - \
1757                                                  Already completed forward declaration \
1758                                                  re-encountered.");
1759         } else {
1760             composite_types_completed.insert(composite_type_metadata);
1761         }
1762     }
1763
1764     let loc = span_start(cx, definition_span);
1765
1766     let member_metadata: Vec<DIDescriptor> = member_descriptions
1767         .iter()
1768         .enumerate()
1769         .map(|(i, member_description)| {
1770             let (member_size, member_align) = size_and_align_of(cx, member_description.llvm_type);
1771             let member_offset = match member_description.offset {
1772                 FixedMemberOffset { bytes } => bytes as u64,
1773                 ComputedMemberOffset => machine::llelement_offset(cx, composite_llvm_type, i)
1774             };
1775
1776             member_description.name.with_c_str(|member_name| {
1777                 unsafe {
1778                     llvm::LLVMDIBuilderCreateMemberType(
1779                         DIB(cx),
1780                         composite_type_metadata,
1781                         member_name,
1782                         file_metadata,
1783                         loc.line as c_uint,
1784                         bytes_to_bits(member_size),
1785                         bytes_to_bits(member_align),
1786                         bytes_to_bits(member_offset),
1787                         0,
1788                         member_description.type_metadata)
1789                 }
1790             })
1791         })
1792         .collect();
1793
1794     unsafe {
1795         let type_array = create_DIArray(DIB(cx), member_metadata.as_slice());
1796         llvm::LLVMDICompositeTypeSetTypeArray(composite_type_metadata, type_array);
1797     }
1798 }
1799
1800 // A convenience wrapper around LLVMDIBuilderCreateStructType(). Does not do any caching, does not
1801 // add any fields to the struct. This can be done later with set_members_of_composite_type().
1802 fn create_struct_stub(cx: &CrateContext,
1803                       struct_llvm_type: Type,
1804                       struct_type_name: &str,
1805                       containing_scope: DIScope,
1806                       file_metadata: DIFile,
1807                       definition_span: Span)
1808                    -> DICompositeType {
1809     let loc = span_start(cx, definition_span);
1810     let (struct_size, struct_align) = size_and_align_of(cx, struct_llvm_type);
1811
1812     // We assign unique IDs to the type stubs so LLVM metadata uniquing does not reuse instances
1813     // where we don't want it.
1814     let unique_id = generate_unique_type_id("DI_STRUCT_");
1815
1816     return unsafe {
1817         struct_type_name.with_c_str(|name| {
1818             unique_id.with_c_str(|unique_id| {
1819                 // LLVMDIBuilderCreateStructType() wants an empty array. A null pointer will lead to
1820                 // hard to trace and debug LLVM assertions later on in llvm/lib/IR/Value.cpp
1821                 let empty_array = create_DIArray(DIB(cx), []);
1822
1823                 llvm::LLVMDIBuilderCreateStructType(
1824                     DIB(cx),
1825                     containing_scope,
1826                     name,
1827                     file_metadata,
1828                     loc.line as c_uint,
1829                     bytes_to_bits(struct_size),
1830                     bytes_to_bits(struct_align),
1831                     0,
1832                     ptr::null(),
1833                     empty_array,
1834                     0,
1835                     ptr::null(),
1836                     unique_id)
1837             })
1838         })
1839     };
1840 }
1841
1842 fn boxed_type_metadata(cx: &CrateContext,
1843                        content_type_name: Option<&str>,
1844                        content_llvm_type: Type,
1845                        content_type_metadata: DIType,
1846                        span: Span)
1847                     -> DICompositeType {
1848     let box_type_name = match content_type_name {
1849         Some(content_type_name) => format!("Boxed<{}>", content_type_name),
1850         None                    => "BoxedType".to_owned()
1851     };
1852
1853     let box_llvm_type = Type::at_box(cx, content_llvm_type);
1854     let member_llvm_types = box_llvm_type.field_types();
1855     assert!(box_layout_is_correct(cx,
1856                                   member_llvm_types.as_slice(),
1857                                   content_llvm_type));
1858
1859     let int_type = ty::mk_int();
1860     let nil_pointer_type = ty::mk_nil_ptr(cx.tcx());
1861     let nil_pointer_type_metadata = type_metadata(cx, nil_pointer_type, codemap::DUMMY_SP);
1862
1863     let member_descriptions = [
1864         MemberDescription {
1865             name: "refcnt".to_owned(),
1866             llvm_type: *member_llvm_types.get(0),
1867             type_metadata: type_metadata(cx, int_type, codemap::DUMMY_SP),
1868             offset: ComputedMemberOffset,
1869         },
1870         MemberDescription {
1871             name: "drop_glue".to_owned(),
1872             llvm_type: *member_llvm_types.get(1),
1873             type_metadata: nil_pointer_type_metadata,
1874             offset: ComputedMemberOffset,
1875         },
1876         MemberDescription {
1877             name: "prev".to_owned(),
1878             llvm_type: *member_llvm_types.get(2),
1879             type_metadata: nil_pointer_type_metadata,
1880             offset: ComputedMemberOffset,
1881         },
1882         MemberDescription {
1883             name: "next".to_owned(),
1884             llvm_type: *member_llvm_types.get(3),
1885             type_metadata: nil_pointer_type_metadata,
1886             offset: ComputedMemberOffset,
1887         },
1888         MemberDescription {
1889             name: "val".to_owned(),
1890             llvm_type: *member_llvm_types.get(4),
1891             type_metadata: content_type_metadata,
1892             offset: ComputedMemberOffset,
1893         }
1894     ];
1895
1896     let loc = span_start(cx, span);
1897     let file_metadata = file_metadata(cx, loc.file.name);
1898
1899     return composite_type_metadata(
1900         cx,
1901         box_llvm_type,
1902         box_type_name,
1903         member_descriptions,
1904         file_metadata,
1905         file_metadata,
1906         span);
1907
1908     // Unfortunately, we cannot assert anything but the correct types here---and not whether the
1909     // 'next' and 'prev' pointers are in the correct order.
1910     fn box_layout_is_correct(cx: &CrateContext,
1911                              member_llvm_types: &[Type],
1912                              content_llvm_type: Type)
1913                           -> bool {
1914         member_llvm_types.len() == 5 &&
1915         member_llvm_types[0] == cx.int_type &&
1916         member_llvm_types[1] == Type::generic_glue_fn(cx).ptr_to() &&
1917         member_llvm_types[2] == Type::i8(cx).ptr_to() &&
1918         member_llvm_types[3] == Type::i8(cx).ptr_to() &&
1919         member_llvm_types[4] == content_llvm_type
1920     }
1921 }
1922
1923 fn fixed_vec_metadata(cx: &CrateContext,
1924                       element_type: ty::t,
1925                       len: uint,
1926                       span: Span)
1927                    -> DIType {
1928     let element_type_metadata = type_metadata(cx, element_type, span);
1929     let element_llvm_type = type_of::type_of(cx, element_type);
1930     let (element_type_size, element_type_align) = size_and_align_of(cx, element_llvm_type);
1931
1932     let subrange = unsafe {
1933         llvm::LLVMDIBuilderGetOrCreateSubrange(
1934         DIB(cx),
1935         0,
1936         len as c_longlong)
1937     };
1938
1939     let subscripts = create_DIArray(DIB(cx), [subrange]);
1940     return unsafe {
1941         llvm::LLVMDIBuilderCreateArrayType(
1942             DIB(cx),
1943             bytes_to_bits(element_type_size * (len as u64)),
1944             bytes_to_bits(element_type_align),
1945             element_type_metadata,
1946             subscripts)
1947     };
1948 }
1949
1950 fn vec_metadata(cx: &CrateContext,
1951                 element_type: ty::t,
1952                 span: Span)
1953              -> DICompositeType {
1954
1955     let element_type_metadata = type_metadata(cx, element_type, span);
1956     let element_llvm_type = type_of::type_of(cx, element_type);
1957     let (element_size, element_align) = size_and_align_of(cx, element_llvm_type);
1958
1959     let vec_llvm_type = Type::vec(cx, &element_llvm_type);
1960     let vec_type_name: &str = format!("[{}]", ppaux::ty_to_str(cx.tcx(), element_type));
1961
1962     let member_llvm_types = vec_llvm_type.field_types();
1963
1964     let int_type_metadata = type_metadata(cx, ty::mk_int(), span);
1965     let array_type_metadata = unsafe {
1966         llvm::LLVMDIBuilderCreateArrayType(
1967             DIB(cx),
1968             bytes_to_bits(element_size),
1969             bytes_to_bits(element_align),
1970             element_type_metadata,
1971             create_DIArray(DIB(cx), [llvm::LLVMDIBuilderGetOrCreateSubrange(DIB(cx), 0, 0)]))
1972     };
1973
1974     let member_descriptions = [
1975         MemberDescription {
1976             name: "fill".to_owned(),
1977             llvm_type: *member_llvm_types.get(0),
1978             type_metadata: int_type_metadata,
1979             offset: ComputedMemberOffset,
1980         },
1981         MemberDescription {
1982             name: "alloc".to_owned(),
1983             llvm_type: *member_llvm_types.get(1),
1984             type_metadata: int_type_metadata,
1985             offset: ComputedMemberOffset,
1986         },
1987         MemberDescription {
1988             name: "elements".to_owned(),
1989             llvm_type: *member_llvm_types.get(2),
1990             type_metadata: array_type_metadata,
1991             offset: ComputedMemberOffset,
1992         }
1993     ];
1994
1995     assert!(member_descriptions.len() == member_llvm_types.len());
1996
1997     let loc = span_start(cx, span);
1998     let file_metadata = file_metadata(cx, loc.file.name);
1999
2000     composite_type_metadata(
2001         cx,
2002         vec_llvm_type,
2003         vec_type_name,
2004         member_descriptions,
2005         file_metadata,
2006         file_metadata,
2007         span)
2008 }
2009
2010 fn vec_slice_metadata(cx: &CrateContext,
2011                       vec_type: ty::t,
2012                       element_type: ty::t,
2013                       span: Span)
2014                    -> DICompositeType {
2015
2016     debug!("vec_slice_metadata: {:?}", ty::get(vec_type));
2017
2018     let slice_llvm_type = type_of::type_of(cx, vec_type);
2019     let slice_type_name = ppaux::ty_to_str(cx.tcx(), vec_type);
2020
2021     let member_llvm_types = slice_llvm_type.field_types();
2022     assert!(slice_layout_is_correct(cx,
2023                                     member_llvm_types.as_slice(),
2024                                     element_type));
2025
2026     let data_ptr_type = ty::mk_ptr(cx.tcx(), ty::mt {
2027         ty: element_type,
2028         mutbl: ast::MutImmutable
2029     });
2030
2031     let member_descriptions = [
2032         MemberDescription {
2033             name: "data_ptr".to_owned(),
2034             llvm_type: *member_llvm_types.get(0),
2035             type_metadata: type_metadata(cx, data_ptr_type, span),
2036             offset: ComputedMemberOffset,
2037         },
2038         MemberDescription {
2039             name: "length".to_owned(),
2040             llvm_type: *member_llvm_types.get(1),
2041             type_metadata: type_metadata(cx, ty::mk_uint(), span),
2042             offset: ComputedMemberOffset,
2043         },
2044     ];
2045
2046     assert!(member_descriptions.len() == member_llvm_types.len());
2047
2048     let loc = span_start(cx, span);
2049     let file_metadata = file_metadata(cx, loc.file.name);
2050
2051     return composite_type_metadata(
2052         cx,
2053         slice_llvm_type,
2054         slice_type_name,
2055         member_descriptions,
2056         file_metadata,
2057         file_metadata,
2058         span);
2059
2060     fn slice_layout_is_correct(cx: &CrateContext,
2061                                member_llvm_types: &[Type],
2062                                element_type: ty::t)
2063                             -> bool {
2064         member_llvm_types.len() == 2 &&
2065         member_llvm_types[0] == type_of::type_of(cx, element_type).ptr_to() &&
2066         member_llvm_types[1] == cx.int_type
2067     }
2068 }
2069
2070 fn subroutine_type_metadata(cx: &CrateContext,
2071                             signature: &ty::FnSig,
2072                             span: Span)
2073                          -> DICompositeType {
2074     let loc = span_start(cx, span);
2075     let file_metadata = file_metadata(cx, loc.file.name);
2076
2077     let mut signature_metadata: Vec<DIType> =
2078         Vec::with_capacity(signature.inputs.len() + 1);
2079
2080     // return type
2081     signature_metadata.push(match ty::get(signature.output).sty {
2082         ty::ty_nil => ptr::null(),
2083         _ => type_metadata(cx, signature.output, span)
2084     });
2085
2086     // regular arguments
2087     for &argument_type in signature.inputs.iter() {
2088         signature_metadata.push(type_metadata(cx, argument_type, span));
2089     }
2090
2091     return unsafe {
2092         llvm::LLVMDIBuilderCreateSubroutineType(
2093             DIB(cx),
2094             file_metadata,
2095             create_DIArray(DIB(cx), signature_metadata.as_slice()))
2096     };
2097 }
2098
2099 fn trait_metadata(cx: &CrateContext,
2100                   def_id: ast::DefId,
2101                   trait_type: ty::t,
2102                   substs: &ty::substs,
2103                   trait_store: ty::TraitStore,
2104                   _: &ty::BuiltinBounds)
2105                -> DIType {
2106     // The implementation provided here is a stub. It makes sure that the trait type is
2107     // assigned the correct name, size, namespace, and source location. But it does not describe
2108     // the trait's methods.
2109     let last = ty::with_path(cx.tcx(), def_id, |mut path| path.last().unwrap());
2110     let ident_string = token::get_name(last.name());
2111     let name = ppaux::trait_store_to_str(cx.tcx(), trait_store) +
2112                ident_string.get();
2113     // Add type and region parameters
2114     let name = ppaux::parameterized(cx.tcx(), name, &substs.regions,
2115                                     substs.tps.as_slice(), def_id, true);
2116
2117     let (containing_scope, definition_span) = get_namespace_and_span_for_item(cx, def_id);
2118
2119     let file_name = span_start(cx, definition_span).file.name.clone();
2120     let file_metadata = file_metadata(cx, file_name);
2121
2122     let trait_llvm_type = type_of::type_of(cx, trait_type);
2123
2124     composite_type_metadata(cx,
2125                             trait_llvm_type,
2126                             name,
2127                             [],
2128                             containing_scope,
2129                             file_metadata,
2130                             definition_span)
2131 }
2132
2133 fn type_metadata(cx: &CrateContext,
2134                  t: ty::t,
2135                  usage_site_span: Span)
2136               -> DIType {
2137     let cache_id = cache_id_for_type(t);
2138
2139     match debug_context(cx).created_types.borrow().find(&cache_id) {
2140         Some(type_metadata) => return *type_metadata,
2141         None => ()
2142     }
2143
2144     fn create_pointer_to_box_metadata(cx: &CrateContext,
2145                                       pointer_type: ty::t,
2146                                       type_in_box: ty::t)
2147                                    -> DIType {
2148         let content_type_name: &str = ppaux::ty_to_str(cx.tcx(), type_in_box);
2149         let content_llvm_type = type_of::type_of(cx, type_in_box);
2150         let content_type_metadata = type_metadata(
2151             cx,
2152             type_in_box,
2153             codemap::DUMMY_SP);
2154
2155         let box_metadata = boxed_type_metadata(
2156             cx,
2157             Some(content_type_name),
2158             content_llvm_type,
2159             content_type_metadata,
2160             codemap::DUMMY_SP);
2161
2162         pointer_type_metadata(cx, pointer_type, box_metadata)
2163     }
2164
2165     debug!("type_metadata: {:?}", ty::get(t));
2166
2167     let sty = &ty::get(t).sty;
2168     let type_metadata = match *sty {
2169         ty::ty_nil      |
2170         ty::ty_bot      |
2171         ty::ty_bool     |
2172         ty::ty_char     |
2173         ty::ty_int(_)   |
2174         ty::ty_uint(_)  |
2175         ty::ty_float(_) => {
2176             basic_type_metadata(cx, t)
2177         },
2178         ty::ty_str(ref vstore) => {
2179             let i8_t = ty::mk_i8();
2180             match *vstore {
2181                 ty::VstoreFixed(len) => {
2182                     fixed_vec_metadata(cx, i8_t, len, usage_site_span)
2183                 },
2184                 ty::VstoreUniq  => {
2185                     let vec_metadata = vec_metadata(cx, i8_t, usage_site_span);
2186                     pointer_type_metadata(cx, t, vec_metadata)
2187                 }
2188                 ty::VstoreSlice(..) => {
2189                     vec_slice_metadata(cx, t, i8_t, usage_site_span)
2190                 }
2191             }
2192         },
2193         ty::ty_enum(def_id, _) => {
2194             prepare_enum_metadata(cx, t, def_id, usage_site_span).finalize(cx)
2195         },
2196         ty::ty_box(typ) => {
2197             create_pointer_to_box_metadata(cx, t, typ)
2198         },
2199         ty::ty_vec(ty, ref vstore) => {
2200             match *vstore {
2201                 ty::VstoreFixed(len) => {
2202                     fixed_vec_metadata(cx, ty, len, usage_site_span)
2203                 }
2204                 ty::VstoreUniq => {
2205                     let vec_metadata = vec_metadata(cx, ty, usage_site_span);
2206                     pointer_type_metadata(cx, t, vec_metadata)
2207                 }
2208                 ty::VstoreSlice(..) => {
2209                     vec_slice_metadata(cx, t, ty, usage_site_span)
2210                 }
2211             }
2212         },
2213         ty::ty_uniq(typ) => {
2214             let pointee = type_metadata(cx, typ, usage_site_span);
2215             pointer_type_metadata(cx, t, pointee)
2216         }
2217         ty::ty_ptr(ref mt) | ty::ty_rptr(_, ref mt) => {
2218             let pointee = type_metadata(cx, mt.ty, usage_site_span);
2219             pointer_type_metadata(cx, t, pointee)
2220         },
2221         ty::ty_bare_fn(ref barefnty) => {
2222             subroutine_type_metadata(cx, &barefnty.sig, usage_site_span)
2223         },
2224         ty::ty_closure(ref closurety) => {
2225             subroutine_type_metadata(cx, &closurety.sig, usage_site_span)
2226         },
2227         ty::ty_trait(~ty::TyTrait { def_id, ref substs, store, ref bounds }) => {
2228             trait_metadata(cx, def_id, t, substs, store, bounds)
2229         },
2230         ty::ty_struct(def_id, ref substs) => {
2231             if ty::type_is_simd(cx.tcx(), t) {
2232                 let element_type = ty::simd_type(cx.tcx(), t);
2233                 let len = ty::simd_size(cx.tcx(), t);
2234                 fixed_vec_metadata(cx, element_type, len, usage_site_span)
2235             } else {
2236                 prepare_struct_metadata(cx, t, def_id, substs, usage_site_span).finalize(cx)
2237             }
2238         },
2239         ty::ty_tup(ref elements) => {
2240             prepare_tuple_metadata(cx,
2241                                    t,
2242                                    elements.as_slice(),
2243                                    usage_site_span).finalize(cx)
2244         }
2245         _ => cx.sess().bug(format!("debuginfo: unexpected type in type_metadata: {:?}", sty))
2246     };
2247
2248     debug_context(cx).created_types.borrow_mut().insert(cache_id, type_metadata);
2249     type_metadata
2250 }
2251
2252 #[deriving(Eq)]
2253 enum DebugLocation {
2254     KnownLocation { scope: DIScope, line: uint, col: uint },
2255     UnknownLocation
2256 }
2257
2258 impl DebugLocation {
2259     fn new(scope: DIScope, line: uint, col: uint) -> DebugLocation {
2260         KnownLocation {
2261             scope: scope,
2262             line: line,
2263             col: col,
2264         }
2265     }
2266 }
2267
2268 fn set_debug_location(cx: &CrateContext, debug_location: DebugLocation) {
2269     if debug_location == debug_context(cx).current_debug_location.get() {
2270         return;
2271     }
2272
2273     let metadata_node;
2274
2275     match debug_location {
2276         KnownLocation { scope, line, .. } => {
2277             let col = 0; // Always set the column to zero like Clang and GCC
2278             debug!("setting debug location to {} {}", line, col);
2279             let elements = [C_i32(cx, line as i32), C_i32(cx, col as i32), scope, ptr::null()];
2280             unsafe {
2281                 metadata_node = llvm::LLVMMDNodeInContext(debug_context(cx).llcontext,
2282                                                           elements.as_ptr(),
2283                                                           elements.len() as c_uint);
2284             }
2285         }
2286         UnknownLocation => {
2287             debug!("clearing debug location ");
2288             metadata_node = ptr::null();
2289         }
2290     };
2291
2292     unsafe {
2293         llvm::LLVMSetCurrentDebugLocation(cx.builder.b, metadata_node);
2294     }
2295
2296     debug_context(cx).current_debug_location.set(debug_location);
2297 }
2298
2299 //=-------------------------------------------------------------------------------------------------
2300 //  Utility Functions
2301 //=-------------------------------------------------------------------------------------------------
2302
2303 fn cache_id_for_type(t: ty::t) -> uint {
2304     ty::type_id(t)
2305 }
2306
2307 // Used to avoid LLVM metadata uniquing problems. See `create_struct_stub()` and
2308 // `prepare_enum_metadata()`.
2309 fn generate_unique_type_id(prefix: &'static str) -> ~str {
2310     unsafe {
2311         static mut unique_id_counter: atomics::AtomicUint = atomics::INIT_ATOMIC_UINT;
2312         format!("{}{}", prefix, unique_id_counter.fetch_add(1, atomics::SeqCst))
2313     }
2314 }
2315
2316 /// Return codemap::Loc corresponding to the beginning of the span
2317 fn span_start(cx: &CrateContext, span: Span) -> codemap::Loc {
2318     cx.sess().codemap().lookup_char_pos(span.lo)
2319 }
2320
2321 fn size_and_align_of(cx: &CrateContext, llvm_type: Type) -> (u64, u64) {
2322     (machine::llsize_of_alloc(cx, llvm_type), machine::llalign_of_min(cx, llvm_type))
2323 }
2324
2325 fn bytes_to_bits(bytes: u64) -> c_ulonglong {
2326     (bytes * 8) as c_ulonglong
2327 }
2328
2329 #[inline]
2330 fn debug_context<'a>(cx: &'a CrateContext) -> &'a CrateDebugContext {
2331     let debug_context: &'a CrateDebugContext = cx.dbg_cx.get_ref();
2332     debug_context
2333 }
2334
2335 #[inline]
2336 fn DIB(cx: &CrateContext) -> DIBuilderRef {
2337     cx.dbg_cx.get_ref().builder
2338 }
2339
2340 fn fn_should_be_ignored(fcx: &FunctionContext) -> bool {
2341     match fcx.debug_context.repr {
2342         FunctionDebugContext(_) => false,
2343         _ => true
2344     }
2345 }
2346
2347 fn assert_type_for_node_id(cx: &CrateContext, node_id: ast::NodeId, error_span: Span) {
2348     if !cx.tcx.node_types.borrow().contains_key(&(node_id as uint)) {
2349         cx.sess().span_bug(error_span, "debuginfo: Could not find type for node id!");
2350     }
2351 }
2352
2353 fn get_namespace_and_span_for_item(cx: &CrateContext, def_id: ast::DefId)
2354                                    -> (DIScope, Span) {
2355     let containing_scope = namespace_for_item(cx, def_id).scope;
2356     let definition_span = if def_id.krate == ast::LOCAL_CRATE {
2357         cx.tcx.map.span(def_id.node)
2358     } else {
2359         // For external items there is no span information
2360         codemap::DUMMY_SP
2361     };
2362
2363     (containing_scope, definition_span)
2364 }
2365
2366 // This procedure builds the *scope map* for a given function, which maps any given ast::NodeId in
2367 // the function's AST to the correct DIScope metadata instance.
2368 //
2369 // This builder procedure walks the AST in execution order and keeps track of what belongs to which
2370 // scope, creating DIScope DIEs along the way, and introducing *artificial* lexical scope
2371 // descriptors where necessary. These artificial scopes allow GDB to correctly handle name
2372 // shadowing.
2373 fn populate_scope_map(cx: &CrateContext,
2374                       arg_pats: &[@ast::Pat],
2375                       fn_entry_block: &ast::Block,
2376                       fn_metadata: DISubprogram,
2377                       scope_map: &mut HashMap<ast::NodeId, DIScope>) {
2378     let def_map = cx.tcx.def_map;
2379
2380     struct ScopeStackEntry {
2381         scope_metadata: DIScope,
2382         ident: Option<ast::Ident>
2383     }
2384
2385     let mut scope_stack = vec!(ScopeStackEntry { scope_metadata: fn_metadata, ident: None });
2386
2387     // Push argument identifiers onto the stack so arguments integrate nicely with variable
2388     // shadowing.
2389     for &arg_pat in arg_pats.iter() {
2390         pat_util::pat_bindings(def_map, arg_pat, |_, _, _, path_ref| {
2391             let ident = ast_util::path_to_ident(path_ref);
2392             scope_stack.push(ScopeStackEntry { scope_metadata: fn_metadata, ident: Some(ident) });
2393         })
2394     }
2395
2396     // Clang creates a separate scope for function bodies, so let's do this too
2397     with_new_scope(cx,
2398                    fn_entry_block.span,
2399                    &mut scope_stack,
2400                    scope_map,
2401                    |cx, scope_stack, scope_map| {
2402         walk_block(cx, fn_entry_block, scope_stack, scope_map);
2403     });
2404
2405     // local helper functions for walking the AST.
2406     fn with_new_scope(cx: &CrateContext,
2407                       scope_span: Span,
2408                       scope_stack: &mut Vec<ScopeStackEntry> ,
2409                       scope_map: &mut HashMap<ast::NodeId, DIScope>,
2410                       inner_walk: |&CrateContext,
2411                                    &mut Vec<ScopeStackEntry> ,
2412                                    &mut HashMap<ast::NodeId, DIScope>|) {
2413         // Create a new lexical scope and push it onto the stack
2414         let loc = cx.sess().codemap().lookup_char_pos(scope_span.lo);
2415         let file_metadata = file_metadata(cx, loc.file.name);
2416         let parent_scope = scope_stack.last().unwrap().scope_metadata;
2417
2418         let scope_metadata = unsafe {
2419             llvm::LLVMDIBuilderCreateLexicalBlock(
2420                 DIB(cx),
2421                 parent_scope,
2422                 file_metadata,
2423                 loc.line as c_uint,
2424                 loc.col.to_uint() as c_uint)
2425         };
2426
2427         scope_stack.push(ScopeStackEntry { scope_metadata: scope_metadata, ident: None });
2428
2429         inner_walk(cx, scope_stack, scope_map);
2430
2431         // pop artificial scopes
2432         while scope_stack.last().unwrap().ident.is_some() {
2433             scope_stack.pop();
2434         }
2435
2436         if scope_stack.last().unwrap().scope_metadata != scope_metadata {
2437             cx.sess().span_bug(scope_span, "debuginfo: Inconsistency in scope management.");
2438         }
2439
2440         scope_stack.pop();
2441     }
2442
2443     fn walk_block(cx: &CrateContext,
2444                   block: &ast::Block,
2445                   scope_stack: &mut Vec<ScopeStackEntry> ,
2446                   scope_map: &mut HashMap<ast::NodeId, DIScope>) {
2447         scope_map.insert(block.id, scope_stack.last().unwrap().scope_metadata);
2448
2449         // The interesting things here are statements and the concluding expression.
2450         for statement in block.stmts.iter() {
2451             scope_map.insert(ast_util::stmt_id(*statement),
2452                              scope_stack.last().unwrap().scope_metadata);
2453
2454             match statement.node {
2455                 ast::StmtDecl(decl, _) => walk_decl(cx, decl, scope_stack, scope_map),
2456                 ast::StmtExpr(exp, _) |
2457                 ast::StmtSemi(exp, _) => walk_expr(cx, exp, scope_stack, scope_map),
2458                 ast::StmtMac(..) => () // ignore macros (which should be expanded anyway)
2459             }
2460         }
2461
2462         for exp in block.expr.iter() {
2463             walk_expr(cx, *exp, scope_stack, scope_map);
2464         }
2465     }
2466
2467     fn walk_decl(cx: &CrateContext,
2468                  decl: &ast::Decl,
2469                  scope_stack: &mut Vec<ScopeStackEntry> ,
2470                  scope_map: &mut HashMap<ast::NodeId, DIScope>) {
2471         match *decl {
2472             codemap::Spanned { node: ast::DeclLocal(local), .. } => {
2473                 scope_map.insert(local.id, scope_stack.last().unwrap().scope_metadata);
2474
2475                 walk_pattern(cx, local.pat, scope_stack, scope_map);
2476
2477                 for exp in local.init.iter() {
2478                     walk_expr(cx, *exp, scope_stack, scope_map);
2479                 }
2480             }
2481             _ => ()
2482         }
2483     }
2484
2485     fn walk_pattern(cx: &CrateContext,
2486                     pat: @ast::Pat,
2487                     scope_stack: &mut Vec<ScopeStackEntry> ,
2488                     scope_map: &mut HashMap<ast::NodeId, DIScope>) {
2489
2490         let def_map = cx.tcx.def_map;
2491
2492         // Unfortunately, we cannot just use pat_util::pat_bindings() or ast_util::walk_pat() here
2493         // because we have to visit *all* nodes in order to put them into the scope map. The above
2494         // functions don't do that.
2495         match pat.node {
2496             ast::PatIdent(_, ref path_ref, ref sub_pat_opt) => {
2497
2498                 // Check if this is a binding. If so we need to put it on the scope stack and maybe
2499                 // introduce an articial scope
2500                 if pat_util::pat_is_binding(def_map, pat) {
2501
2502                     let ident = ast_util::path_to_ident(path_ref);
2503
2504                     // LLVM does not properly generate 'DW_AT_start_scope' fields for variable DIEs.
2505                     // For this reason we have to introduce an artificial scope at bindings whenever
2506                     // a variable with the same name is declared in *any* parent scope.
2507                     //
2508                     // Otherwise the following error occurs:
2509                     //
2510                     // let x = 10;
2511                     //
2512                     // do_something(); // 'gdb print x' correctly prints 10
2513                     //
2514                     // {
2515                     //     do_something(); // 'gdb print x' prints 0, because it already reads the
2516                     //                     // uninitialized 'x' from the next line...
2517                     //     let x = 100;
2518                     //     do_something(); // 'gdb print x' correctly prints 100
2519                     // }
2520
2521                     // Is there already a binding with that name?
2522                     // N.B.: this comparison must be UNhygienic... because
2523                     // gdb knows nothing about the context, so any two
2524                     // variables with the same name will cause the problem.
2525                     let need_new_scope = scope_stack
2526                         .iter()
2527                         .any(|entry| entry.ident.iter().any(|i| i.name == ident.name));
2528
2529                     if need_new_scope {
2530                         // Create a new lexical scope and push it onto the stack
2531                         let loc = cx.sess().codemap().lookup_char_pos(pat.span.lo);
2532                         let file_metadata = file_metadata(cx, loc.file.name);
2533                         let parent_scope = scope_stack.last().unwrap().scope_metadata;
2534
2535                         let scope_metadata = unsafe {
2536                             llvm::LLVMDIBuilderCreateLexicalBlock(
2537                                 DIB(cx),
2538                                 parent_scope,
2539                                 file_metadata,
2540                                 loc.line as c_uint,
2541                                 loc.col.to_uint() as c_uint)
2542                         };
2543
2544                         scope_stack.push(ScopeStackEntry {
2545                             scope_metadata: scope_metadata,
2546                             ident: Some(ident)
2547                         });
2548
2549                     } else {
2550                         // Push a new entry anyway so the name can be found
2551                         let prev_metadata = scope_stack.last().unwrap().scope_metadata;
2552                         scope_stack.push(ScopeStackEntry {
2553                             scope_metadata: prev_metadata,
2554                             ident: Some(ident)
2555                         });
2556                     }
2557                 }
2558
2559                 scope_map.insert(pat.id, scope_stack.last().unwrap().scope_metadata);
2560
2561                 for &sub_pat in sub_pat_opt.iter() {
2562                     walk_pattern(cx, sub_pat, scope_stack, scope_map);
2563                 }
2564             }
2565
2566             ast::PatWild | ast::PatWildMulti => {
2567                 scope_map.insert(pat.id, scope_stack.last().unwrap().scope_metadata);
2568             }
2569
2570             ast::PatEnum(_, ref sub_pats_opt) => {
2571                 scope_map.insert(pat.id, scope_stack.last().unwrap().scope_metadata);
2572
2573                 for ref sub_pats in sub_pats_opt.iter() {
2574                     for &p in sub_pats.iter() {
2575                         walk_pattern(cx, p, scope_stack, scope_map);
2576                     }
2577                 }
2578             }
2579
2580             ast::PatStruct(_, ref field_pats, _) => {
2581                 scope_map.insert(pat.id, scope_stack.last().unwrap().scope_metadata);
2582
2583                 for &ast::FieldPat { pat: sub_pat, .. } in field_pats.iter() {
2584                     walk_pattern(cx, sub_pat, scope_stack, scope_map);
2585                 }
2586             }
2587
2588             ast::PatTup(ref sub_pats) => {
2589                 scope_map.insert(pat.id, scope_stack.last().unwrap().scope_metadata);
2590
2591                 for &sub_pat in sub_pats.iter() {
2592                     walk_pattern(cx, sub_pat, scope_stack, scope_map);
2593                 }
2594             }
2595
2596             ast::PatUniq(sub_pat) | ast::PatRegion(sub_pat) => {
2597                 scope_map.insert(pat.id, scope_stack.last().unwrap().scope_metadata);
2598                 walk_pattern(cx, sub_pat, scope_stack, scope_map);
2599             }
2600
2601             ast::PatLit(exp) => {
2602                 scope_map.insert(pat.id, scope_stack.last().unwrap().scope_metadata);
2603                 walk_expr(cx, exp, scope_stack, scope_map);
2604             }
2605
2606             ast::PatRange(exp1, exp2) => {
2607                 scope_map.insert(pat.id, scope_stack.last().unwrap().scope_metadata);
2608                 walk_expr(cx, exp1, scope_stack, scope_map);
2609                 walk_expr(cx, exp2, scope_stack, scope_map);
2610             }
2611
2612             ast::PatVec(ref front_sub_pats, ref middle_sub_pats, ref back_sub_pats) => {
2613                 scope_map.insert(pat.id, scope_stack.last().unwrap().scope_metadata);
2614
2615                 for &sub_pat in front_sub_pats.iter() {
2616                     walk_pattern(cx, sub_pat, scope_stack, scope_map);
2617                 }
2618
2619                 for &sub_pat in middle_sub_pats.iter() {
2620                     walk_pattern(cx, sub_pat, scope_stack, scope_map);
2621                 }
2622
2623                 for &sub_pat in back_sub_pats.iter() {
2624                     walk_pattern(cx, sub_pat, scope_stack, scope_map);
2625                 }
2626             }
2627         }
2628     }
2629
2630     fn walk_expr(cx: &CrateContext,
2631                  exp: &ast::Expr,
2632                  scope_stack: &mut Vec<ScopeStackEntry> ,
2633                  scope_map: &mut HashMap<ast::NodeId, DIScope>) {
2634
2635         scope_map.insert(exp.id, scope_stack.last().unwrap().scope_metadata);
2636
2637         match exp.node {
2638             ast::ExprLit(_)   |
2639             ast::ExprBreak(_) |
2640             ast::ExprAgain(_) |
2641             ast::ExprPath(_)  => {}
2642
2643             ast::ExprVstore(sub_exp, _)   |
2644             ast::ExprCast(sub_exp, _)     |
2645             ast::ExprAddrOf(_, sub_exp)  |
2646             ast::ExprField(sub_exp, _, _) |
2647             ast::ExprParen(sub_exp)       => walk_expr(cx, sub_exp, scope_stack, scope_map),
2648
2649             ast::ExprBox(place, sub_expr) => {
2650                 walk_expr(cx, place, scope_stack, scope_map);
2651                 walk_expr(cx, sub_expr, scope_stack, scope_map);
2652             }
2653
2654             ast::ExprRet(exp_opt) => match exp_opt {
2655                 Some(sub_exp) => walk_expr(cx, sub_exp, scope_stack, scope_map),
2656                 None => ()
2657             },
2658
2659             ast::ExprUnary(_, sub_exp) => {
2660                 walk_expr(cx, sub_exp, scope_stack, scope_map);
2661             }
2662
2663             ast::ExprAssignOp(_, lhs, rhs) |
2664             ast::ExprIndex(lhs, rhs)        |
2665             ast::ExprBinary(_, lhs, rhs)    => {
2666                 walk_expr(cx, lhs, scope_stack, scope_map);
2667                 walk_expr(cx, rhs, scope_stack, scope_map);
2668             }
2669
2670             ast::ExprVec(ref init_expressions) |
2671             ast::ExprTup(ref init_expressions) => {
2672                 for ie in init_expressions.iter() {
2673                     walk_expr(cx, *ie, scope_stack, scope_map);
2674                 }
2675             }
2676
2677             ast::ExprAssign(sub_exp1, sub_exp2) |
2678             ast::ExprRepeat(sub_exp1, sub_exp2) => {
2679                 walk_expr(cx, sub_exp1, scope_stack, scope_map);
2680                 walk_expr(cx, sub_exp2, scope_stack, scope_map);
2681             }
2682
2683             ast::ExprIf(cond_exp, then_block, ref opt_else_exp) => {
2684                 walk_expr(cx, cond_exp, scope_stack, scope_map);
2685
2686                 with_new_scope(cx,
2687                                then_block.span,
2688                                scope_stack,
2689                                scope_map,
2690                                |cx, scope_stack, scope_map| {
2691                     walk_block(cx, then_block, scope_stack, scope_map);
2692                 });
2693
2694                 match *opt_else_exp {
2695                     Some(else_exp) => walk_expr(cx, else_exp, scope_stack, scope_map),
2696                     _ => ()
2697                 }
2698             }
2699
2700             ast::ExprWhile(cond_exp, loop_body) => {
2701                 walk_expr(cx, cond_exp, scope_stack, scope_map);
2702
2703                 with_new_scope(cx,
2704                                loop_body.span,
2705                                scope_stack,
2706                                scope_map,
2707                                |cx, scope_stack, scope_map| {
2708                     walk_block(cx, loop_body, scope_stack, scope_map);
2709                 })
2710             }
2711
2712             ast::ExprForLoop(_, _, _, _) => {
2713                 cx.sess().span_bug(exp.span, "debuginfo::populate_scope_map() - \
2714                                               Found unexpanded for-loop.");
2715             }
2716
2717             ast::ExprMac(_) => {
2718                 cx.sess().span_bug(exp.span, "debuginfo::populate_scope_map() - \
2719                                               Found unexpanded macro.");
2720             }
2721
2722             ast::ExprLoop(block, _) |
2723             ast::ExprBlock(block)   => {
2724                 with_new_scope(cx,
2725                                block.span,
2726                                scope_stack,
2727                                scope_map,
2728                                |cx, scope_stack, scope_map| {
2729                     walk_block(cx, block, scope_stack, scope_map);
2730                 })
2731             }
2732
2733             ast::ExprFnBlock(decl, block) |
2734             ast::ExprProc(decl, block) => {
2735                 with_new_scope(cx,
2736                                block.span,
2737                                scope_stack,
2738                                scope_map,
2739                                |cx, scope_stack, scope_map| {
2740                     for &ast::Arg { pat: pattern, .. } in decl.inputs.iter() {
2741                         walk_pattern(cx, pattern, scope_stack, scope_map);
2742                     }
2743
2744                     walk_block(cx, block, scope_stack, scope_map);
2745                 })
2746             }
2747
2748             ast::ExprCall(fn_exp, ref args) => {
2749                 walk_expr(cx, fn_exp, scope_stack, scope_map);
2750
2751                 for arg_exp in args.iter() {
2752                     walk_expr(cx, *arg_exp, scope_stack, scope_map);
2753                 }
2754             }
2755
2756             ast::ExprMethodCall(_, _, ref args) => {
2757                 for arg_exp in args.iter() {
2758                     walk_expr(cx, *arg_exp, scope_stack, scope_map);
2759                 }
2760             }
2761
2762             ast::ExprMatch(discriminant_exp, ref arms) => {
2763                 walk_expr(cx, discriminant_exp, scope_stack, scope_map);
2764
2765                 // for each arm we have to first walk the pattern as these might introduce new
2766                 // artificial scopes. It should be sufficient to walk only one pattern per arm, as
2767                 // they all must contain the same binding names
2768
2769                 for arm_ref in arms.iter() {
2770                     let arm_span = arm_ref.pats.get(0).span;
2771
2772                     with_new_scope(cx,
2773                                    arm_span,
2774                                    scope_stack,
2775                                    scope_map,
2776                                    |cx, scope_stack, scope_map| {
2777                         for &pat in arm_ref.pats.iter() {
2778                             walk_pattern(cx, pat, scope_stack, scope_map);
2779                         }
2780
2781                         for guard_exp in arm_ref.guard.iter() {
2782                             walk_expr(cx, *guard_exp, scope_stack, scope_map)
2783                         }
2784
2785                         walk_expr(cx, arm_ref.body, scope_stack, scope_map);
2786                     })
2787                 }
2788             }
2789
2790             ast::ExprStruct(_, ref fields, ref base_exp) => {
2791                 for &ast::Field { expr: exp, .. } in fields.iter() {
2792                     walk_expr(cx, exp, scope_stack, scope_map);
2793                 }
2794
2795                 match *base_exp {
2796                     Some(exp) => walk_expr(cx, exp, scope_stack, scope_map),
2797                     None => ()
2798                 }
2799             }
2800
2801             ast::ExprInlineAsm(ast::InlineAsm { inputs: ref inputs,
2802                                                 outputs: ref outputs,
2803                                                 .. }) => {
2804                 // inputs, outputs: ~[(~str, @expr)]
2805                 for &(_, exp) in inputs.iter() {
2806                     walk_expr(cx, exp, scope_stack, scope_map);
2807                 }
2808
2809                 for &(_, exp) in outputs.iter() {
2810                     walk_expr(cx, exp, scope_stack, scope_map);
2811                 }
2812             }
2813         }
2814     }
2815 }
2816
2817
2818 //=-------------------------------------------------------------------------------------------------
2819 // Namespace Handling
2820 //=-------------------------------------------------------------------------------------------------
2821
2822 struct NamespaceTreeNode {
2823     name: ast::Name,
2824     scope: DIScope,
2825     parent: Option<@NamespaceTreeNode>,
2826 }
2827
2828 impl NamespaceTreeNode {
2829     fn mangled_name_of_contained_item(&self, item_name: &str) -> ~str {
2830         fn fill_nested(node: &NamespaceTreeNode, output: &mut StrBuf) {
2831             match node.parent {
2832                 Some(parent) => fill_nested(parent, output),
2833                 None => {}
2834             }
2835             let string = token::get_name(node.name);
2836             output.push_str(format!("{}", string.get().len()));
2837             output.push_str(string.get());
2838         }
2839
2840         let mut name = StrBuf::from_str("_ZN");
2841         fill_nested(self, &mut name);
2842         name.push_str(format!("{}", item_name.len()));
2843         name.push_str(item_name);
2844         name.push_char('E');
2845         name.into_owned()
2846     }
2847 }
2848
2849 fn namespace_for_item(cx: &CrateContext, def_id: ast::DefId) -> @NamespaceTreeNode {
2850     ty::with_path(cx.tcx(), def_id, |path| {
2851         // prepend crate name if not already present
2852         let krate = if def_id.krate == ast::LOCAL_CRATE {
2853             let crate_namespace_ident = token::str_to_ident(cx.link_meta.crateid.name);
2854             Some(ast_map::PathMod(crate_namespace_ident.name))
2855         } else {
2856             None
2857         };
2858         let mut path = krate.move_iter().chain(path).peekable();
2859
2860         let mut current_key = Vec::new();
2861         let mut parent_node: Option<@NamespaceTreeNode> = None;
2862
2863         // Create/Lookup namespace for each element of the path.
2864         loop {
2865             // Emulate a for loop so we can use peek below.
2866             let path_element = match path.next() {
2867                 Some(e) => e,
2868                 None => break
2869             };
2870             // Ignore the name of the item (the last path element).
2871             if path.peek().is_none() {
2872                 break;
2873             }
2874
2875             let name = path_element.name();
2876             current_key.push(name);
2877
2878             let existing_node = debug_context(cx).namespace_map.borrow()
2879                                                  .find_copy(&current_key);
2880             let current_node = match existing_node {
2881                 Some(existing_node) => existing_node,
2882                 None => {
2883                     // create and insert
2884                     let parent_scope = match parent_node {
2885                         Some(node) => node.scope,
2886                         None => ptr::null()
2887                     };
2888                     let namespace_name = token::get_name(name);
2889                     let scope = namespace_name.get().with_c_str(|namespace_name| {
2890                         unsafe {
2891                             llvm::LLVMDIBuilderCreateNameSpace(
2892                                 DIB(cx),
2893                                 parent_scope,
2894                                 namespace_name,
2895                                 // cannot reconstruct file ...
2896                                 ptr::null(),
2897                                 // ... or line information, but that's not so important.
2898                                 0)
2899                         }
2900                     });
2901
2902                     let node = @NamespaceTreeNode {
2903                         name: name,
2904                         scope: scope,
2905                         parent: parent_node,
2906                     };
2907
2908                     debug_context(cx).namespace_map.borrow_mut()
2909                                      .insert(current_key.clone(), node);
2910
2911                     node
2912                 }
2913             };
2914
2915             parent_node = Some(current_node);
2916         }
2917
2918         match parent_node {
2919             Some(node) => node,
2920             None => {
2921                 cx.sess().bug(format!("debuginfo::namespace_for_item(): \
2922                     path too short for {:?}", def_id));
2923             }
2924         }
2925     })
2926 }