src/librustc/middle/trans/debuginfo.rs

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