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