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