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