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