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