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_store: ty::TraitStore,
 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_store {
 447         ty::RegionTraitStore(..) => {
 448             address_operations.len()
 449         }
 450         ty::UniqTraitStore => {
 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                   _: &ty::BuiltinBounds)
2102                -> DIType {
2103     // The implementation provided here is a stub. It makes sure that the trait type is
2104     // assigned the correct name, size, namespace, and source location. But it does not describe
2105     // the trait's methods.
2106     let last = ty::with_path(cx.tcx(), def_id, |mut path| path.last().unwrap());
2107     let ident_string = token::get_name(last.name());
2108     let name = ppaux::trait_store_to_str(cx.tcx(), trait_store) +
2109                ident_string.get();
2110     // Add type and region parameters
2111     let name = ppaux::parameterized(cx.tcx(), name, &substs.regions,
2112                                     substs.tps.as_slice(), def_id, true);
2113
2114     let (containing_scope, definition_span) = get_namespace_and_span_for_item(cx, def_id);
2115
2116     let file_name = span_start(cx, definition_span).file.name.clone();
2117     let file_metadata = file_metadata(cx, file_name);
2118
2119     let trait_llvm_type = type_of::type_of(cx, trait_type);
2120
2121     composite_type_metadata(cx,
2122                             trait_llvm_type,
2123                             name,
2124                             [],
2125                             containing_scope,
2126                             file_metadata,
2127                             definition_span)
2128 }
2129
2130 fn type_metadata(cx: &CrateContext,
2131                  t: ty::t,
2132                  usage_site_span: Span)
2133               -> DIType {
2134     let cache_id = cache_id_for_type(t);
2135
2136     match debug_context(cx).created_types.borrow().find(&cache_id) {
2137         Some(type_metadata) => return *type_metadata,
2138         None => ()
2139     }
2140
2141     fn create_pointer_to_box_metadata(cx: &CrateContext,
2142                                       pointer_type: ty::t,
2143                                       type_in_box: ty::t)
2144                                    -> DIType {
2145         let content_type_name: &str = ppaux::ty_to_str(cx.tcx(), type_in_box);
2146         let content_llvm_type = type_of::type_of(cx, type_in_box);
2147         let content_type_metadata = type_metadata(
2148             cx,
2149             type_in_box,
2150             codemap::DUMMY_SP);
2151
2152         let box_metadata = boxed_type_metadata(
2153             cx,
2154             Some(content_type_name),
2155             content_llvm_type,
2156             content_type_metadata,
2157             codemap::DUMMY_SP);
2158
2159         pointer_type_metadata(cx, pointer_type, box_metadata)
2160     }
2161
2162     debug!("type_metadata: {:?}", ty::get(t));
2163
2164     let sty = &ty::get(t).sty;
2165     let type_metadata = match *sty {
2166         ty::ty_nil      |
2167         ty::ty_bot      |
2168         ty::ty_bool     |
2169         ty::ty_char     |
2170         ty::ty_int(_)   |
2171         ty::ty_uint(_)  |
2172         ty::ty_float(_) => {
2173             basic_type_metadata(cx, t)
2174         },
2175         ty::ty_str(ref vstore) => {
2176             let i8_t = ty::mk_i8();
2177             match *vstore {
2178                 ty::VstoreFixed(len) => {
2179                     fixed_vec_metadata(cx, i8_t, len, usage_site_span)
2180                 },
2181                 ty::VstoreUniq  => {
2182                     let vec_metadata = vec_metadata(cx, i8_t, usage_site_span);
2183                     pointer_type_metadata(cx, t, vec_metadata)
2184                 }
2185                 ty::VstoreSlice(..) => {
2186                     vec_slice_metadata(cx, t, i8_t, usage_site_span)
2187                 }
2188             }
2189         },
2190         ty::ty_enum(def_id, _) => {
2191             prepare_enum_metadata(cx, t, def_id, usage_site_span).finalize(cx)
2192         },
2193         ty::ty_box(typ) => {
2194             create_pointer_to_box_metadata(cx, t, typ)
2195         },
2196         ty::ty_vec(ty, ref vstore) => {
2197             match *vstore {
2198                 ty::VstoreFixed(len) => {
2199                     fixed_vec_metadata(cx, ty, len, usage_site_span)
2200                 }
2201                 ty::VstoreUniq => {
2202                     let vec_metadata = vec_metadata(cx, ty, usage_site_span);
2203                     pointer_type_metadata(cx, t, vec_metadata)
2204                 }
2205                 ty::VstoreSlice(..) => {
2206                     vec_slice_metadata(cx, t, ty, usage_site_span)
2207                 }
2208             }
2209         },
2210         ty::ty_uniq(typ) => {
2211             let pointee = type_metadata(cx, typ, usage_site_span);
2212             pointer_type_metadata(cx, t, pointee)
2213         }
2214         ty::ty_ptr(ref mt) | ty::ty_rptr(_, ref mt) => {
2215             let pointee = type_metadata(cx, mt.ty, usage_site_span);
2216             pointer_type_metadata(cx, t, pointee)
2217         },
2218         ty::ty_bare_fn(ref barefnty) => {
2219             subroutine_type_metadata(cx, &barefnty.sig, usage_site_span)
2220         },
2221         ty::ty_closure(ref closurety) => {
2222             subroutine_type_metadata(cx, &closurety.sig, usage_site_span)
2223         },
2224         ty::ty_trait(~ty::TyTrait { def_id, ref substs, store, ref bounds }) => {
2225             trait_metadata(cx, def_id, t, substs, store, bounds)
2226         },
2227         ty::ty_struct(def_id, ref substs) => {
2228             if ty::type_is_simd(cx.tcx(), t) {
2229                 let element_type = ty::simd_type(cx.tcx(), t);
2230                 let len = ty::simd_size(cx.tcx(), t);
2231                 fixed_vec_metadata(cx, element_type, len, usage_site_span)
2232             } else {
2233                 prepare_struct_metadata(cx, t, def_id, substs, usage_site_span).finalize(cx)
2234             }
2235         },
2236         ty::ty_tup(ref elements) => {
2237             prepare_tuple_metadata(cx,
2238                                    t,
2239                                    elements.as_slice(),
2240                                    usage_site_span).finalize(cx)
2241         }
2242         _ => cx.sess().bug(format!("debuginfo: unexpected type in type_metadata: {:?}", sty))
2243     };
2244
2245     debug_context(cx).created_types.borrow_mut().insert(cache_id, type_metadata);
2246     type_metadata
2247 }
2248
2249 #[deriving(Eq)]
2250 enum DebugLocation {
2251     KnownLocation { scope: DIScope, line: uint, col: uint },
2252     UnknownLocation
2253 }
2254
2255 impl DebugLocation {
2256     fn new(scope: DIScope, line: uint, col: uint) -> DebugLocation {
2257         KnownLocation {
2258             scope: scope,
2259             line: line,
2260             col: col,
2261         }
2262     }
2263 }
2264
2265 fn set_debug_location(cx: &CrateContext, debug_location: DebugLocation) {
2266     if debug_location == debug_context(cx).current_debug_location.get() {
2267         return;
2268     }
2269
2270     let metadata_node;
2271
2272     match debug_location {
2273         KnownLocation { scope, line, .. } => {
2274             let col = 0; // Always set the column to zero like Clang and GCC
2275             debug!("setting debug location to {} {}", line, col);
2276             let elements = [C_i32(cx, line as i32), C_i32(cx, col as i32), scope, ptr::null()];
2277             unsafe {
2278                 metadata_node = llvm::LLVMMDNodeInContext(debug_context(cx).llcontext,
2279                                                           elements.as_ptr(),
2280                                                           elements.len() as c_uint);
2281             }
2282         }
2283         UnknownLocation => {
2284             debug!("clearing debug location ");
2285             metadata_node = ptr::null();
2286         }
2287     };
2288
2289     unsafe {
2290         llvm::LLVMSetCurrentDebugLocation(cx.builder.b, metadata_node);
2291     }
2292
2293     debug_context(cx).current_debug_location.set(debug_location);
2294 }
2295
2296 //=-------------------------------------------------------------------------------------------------
2297 //  Utility Functions
2298 //=-------------------------------------------------------------------------------------------------
2299
2300 fn cache_id_for_type(t: ty::t) -> uint {
2301     ty::type_id(t)
2302 }
2303
2304 // Used to avoid LLVM metadata uniquing problems. See `create_struct_stub()` and
2305 // `prepare_enum_metadata()`.
2306 fn generate_unique_type_id(prefix: &'static str) -> ~str {
2307     unsafe {
2308         static mut unique_id_counter: atomics::AtomicUint = atomics::INIT_ATOMIC_UINT;
2309         format!("{}{}", prefix, unique_id_counter.fetch_add(1, atomics::SeqCst))
2310     }
2311 }
2312
2313 /// Return codemap::Loc corresponding to the beginning of the span
2314 fn span_start(cx: &CrateContext, span: Span) -> codemap::Loc {
2315     cx.sess().codemap().lookup_char_pos(span.lo)
2316 }
2317
2318 fn size_and_align_of(cx: &CrateContext, llvm_type: Type) -> (u64, u64) {
2319     (machine::llsize_of_alloc(cx, llvm_type), machine::llalign_of_min(cx, llvm_type))
2320 }
2321
2322 fn bytes_to_bits(bytes: u64) -> c_ulonglong {
2323     (bytes * 8) as c_ulonglong
2324 }
2325
2326 #[inline]
2327 fn debug_context<'a>(cx: &'a CrateContext) -> &'a CrateDebugContext {
2328     let debug_context: &'a CrateDebugContext = cx.dbg_cx.get_ref();
2329     debug_context
2330 }
2331
2332 #[inline]
2333 fn DIB(cx: &CrateContext) -> DIBuilderRef {
2334     cx.dbg_cx.get_ref().builder
2335 }
2336
2337 fn fn_should_be_ignored(fcx: &FunctionContext) -> bool {
2338     match fcx.debug_context {
2339         FunctionDebugContext(_) => false,
2340         _ => true
2341     }
2342 }
2343
2344 fn assert_type_for_node_id(cx: &CrateContext, node_id: ast::NodeId, error_span: Span) {
2345     if !cx.tcx.node_types.borrow().contains_key(&(node_id as uint)) {
2346         cx.sess().span_bug(error_span, "debuginfo: Could not find type for node id!");
2347     }
2348 }
2349
2350 fn get_namespace_and_span_for_item(cx: &CrateContext, def_id: ast::DefId)
2351                                    -> (DIScope, Span) {
2352     let containing_scope = namespace_for_item(cx, def_id).scope;
2353     let definition_span = if def_id.krate == ast::LOCAL_CRATE {
2354         cx.tcx.map.span(def_id.node)
2355     } else {
2356         // For external items there is no span information
2357         codemap::DUMMY_SP
2358     };
2359
2360     (containing_scope, definition_span)
2361 }
2362
2363 // This procedure builds the *scope map* for a given function, which maps any given ast::NodeId in
2364 // the function's AST to the correct DIScope metadata instance.
2365 //
2366 // This builder procedure walks the AST in execution order and keeps track of what belongs to which
2367 // scope, creating DIScope DIEs along the way, and introducing *artificial* lexical scope
2368 // descriptors where necessary. These artificial scopes allow GDB to correctly handle name
2369 // shadowing.
2370 fn populate_scope_map(cx: &CrateContext,
2371                       arg_pats: &[@ast::Pat],
2372                       fn_entry_block: &ast::Block,
2373                       fn_metadata: DISubprogram,
2374                       scope_map: &mut HashMap<ast::NodeId, DIScope>) {
2375     let def_map = cx.tcx.def_map;
2376
2377     struct ScopeStackEntry {
2378         scope_metadata: DIScope,
2379         ident: Option<ast::Ident>
2380     }
2381
2382     let mut scope_stack = vec!(ScopeStackEntry { scope_metadata: fn_metadata, ident: None });
2383
2384     // Push argument identifiers onto the stack so arguments integrate nicely with variable
2385     // shadowing.
2386     for &arg_pat in arg_pats.iter() {
2387         pat_util::pat_bindings(def_map, arg_pat, |_, _, _, path_ref| {
2388             let ident = ast_util::path_to_ident(path_ref);
2389             scope_stack.push(ScopeStackEntry { scope_metadata: fn_metadata, ident: Some(ident) });
2390         })
2391     }
2392
2393     // Clang creates a separate scope for function bodies, so let's do this too
2394     with_new_scope(cx,
2395                    fn_entry_block.span,
2396                    &mut scope_stack,
2397                    scope_map,
2398                    |cx, scope_stack, scope_map| {
2399         walk_block(cx, fn_entry_block, scope_stack, scope_map);
2400     });
2401
2402     // local helper functions for walking the AST.
2403     fn with_new_scope(cx: &CrateContext,
2404                       scope_span: Span,
2405                       scope_stack: &mut Vec<ScopeStackEntry> ,
2406                       scope_map: &mut HashMap<ast::NodeId, DIScope>,
2407                       inner_walk: |&CrateContext,
2408                                    &mut Vec<ScopeStackEntry> ,
2409                                    &mut HashMap<ast::NodeId, DIScope>|) {
2410         // Create a new lexical scope and push it onto the stack
2411         let loc = cx.sess().codemap().lookup_char_pos(scope_span.lo);
2412         let file_metadata = file_metadata(cx, loc.file.name);
2413         let parent_scope = scope_stack.last().unwrap().scope_metadata;
2414
2415         let scope_metadata = unsafe {
2416             llvm::LLVMDIBuilderCreateLexicalBlock(
2417                 DIB(cx),
2418                 parent_scope,
2419                 file_metadata,
2420                 loc.line as c_uint,
2421                 loc.col.to_uint() as c_uint)
2422         };
2423
2424         scope_stack.push(ScopeStackEntry { scope_metadata: scope_metadata, ident: None });
2425
2426         inner_walk(cx, scope_stack, scope_map);
2427
2428         // pop artificial scopes
2429         while scope_stack.last().unwrap().ident.is_some() {
2430             scope_stack.pop();
2431         }
2432
2433         if scope_stack.last().unwrap().scope_metadata != scope_metadata {
2434             cx.sess().span_bug(scope_span, "debuginfo: Inconsistency in scope management.");
2435         }
2436
2437         scope_stack.pop();
2438     }
2439
2440     fn walk_block(cx: &CrateContext,
2441                   block: &ast::Block,
2442                   scope_stack: &mut Vec<ScopeStackEntry> ,
2443                   scope_map: &mut HashMap<ast::NodeId, DIScope>) {
2444         scope_map.insert(block.id, scope_stack.last().unwrap().scope_metadata);
2445
2446         // The interesting things here are statements and the concluding expression.
2447         for statement in block.stmts.iter() {
2448             scope_map.insert(ast_util::stmt_id(*statement),
2449                              scope_stack.last().unwrap().scope_metadata);
2450
2451             match statement.node {
2452                 ast::StmtDecl(decl, _) => walk_decl(cx, decl, scope_stack, scope_map),
2453                 ast::StmtExpr(exp, _) |
2454                 ast::StmtSemi(exp, _) => walk_expr(cx, exp, scope_stack, scope_map),
2455                 ast::StmtMac(..) => () // ignore macros (which should be expanded anyway)
2456             }
2457         }
2458
2459         for exp in block.expr.iter() {
2460             walk_expr(cx, *exp, scope_stack, scope_map);
2461         }
2462     }
2463
2464     fn walk_decl(cx: &CrateContext,
2465                  decl: &ast::Decl,
2466                  scope_stack: &mut Vec<ScopeStackEntry> ,
2467                  scope_map: &mut HashMap<ast::NodeId, DIScope>) {
2468         match *decl {
2469             codemap::Spanned { node: ast::DeclLocal(local), .. } => {
2470                 scope_map.insert(local.id, scope_stack.last().unwrap().scope_metadata);
2471
2472                 walk_pattern(cx, local.pat, scope_stack, scope_map);
2473
2474                 for exp in local.init.iter() {
2475                     walk_expr(cx, *exp, scope_stack, scope_map);
2476                 }
2477             }
2478             _ => ()
2479         }
2480     }
2481
2482     fn walk_pattern(cx: &CrateContext,
2483                     pat: @ast::Pat,
2484                     scope_stack: &mut Vec<ScopeStackEntry> ,
2485                     scope_map: &mut HashMap<ast::NodeId, DIScope>) {
2486
2487         let def_map = cx.tcx.def_map;
2488
2489         // Unfortunately, we cannot just use pat_util::pat_bindings() or ast_util::walk_pat() here
2490         // because we have to visit *all* nodes in order to put them into the scope map. The above
2491         // functions don't do that.
2492         match pat.node {
2493             ast::PatIdent(_, ref path_ref, ref sub_pat_opt) => {
2494
2495                 // Check if this is a binding. If so we need to put it on the scope stack and maybe
2496                 // introduce an articial scope
2497                 if pat_util::pat_is_binding(def_map, pat) {
2498
2499                     let ident = ast_util::path_to_ident(path_ref);
2500
2501                     // LLVM does not properly generate 'DW_AT_start_scope' fields for variable DIEs.
2502                     // For this reason we have to introduce an artificial scope at bindings whenever
2503                     // a variable with the same name is declared in *any* parent scope.
2504                     //
2505                     // Otherwise the following error occurs:
2506                     //
2507                     // let x = 10;
2508                     //
2509                     // do_something(); // 'gdb print x' correctly prints 10
2510                     //
2511                     // {
2512                     //     do_something(); // 'gdb print x' prints 0, because it already reads the
2513                     //                     // uninitialized 'x' from the next line...
2514                     //     let x = 100;
2515                     //     do_something(); // 'gdb print x' correctly prints 100
2516                     // }
2517
2518                     // Is there already a binding with that name?
2519                     // N.B.: this comparison must be UNhygienic... because
2520                     // gdb knows nothing about the context, so any two
2521                     // variables with the same name will cause the problem.
2522                     let need_new_scope = scope_stack
2523                         .iter()
2524                         .any(|entry| entry.ident.iter().any(|i| i.name == ident.name));
2525
2526                     if need_new_scope {
2527                         // Create a new lexical scope and push it onto the stack
2528                         let loc = cx.sess().codemap().lookup_char_pos(pat.span.lo);
2529                         let file_metadata = file_metadata(cx, loc.file.name);
2530                         let parent_scope = scope_stack.last().unwrap().scope_metadata;
2531
2532                         let scope_metadata = unsafe {
2533                             llvm::LLVMDIBuilderCreateLexicalBlock(
2534                                 DIB(cx),
2535                                 parent_scope,
2536                                 file_metadata,
2537                                 loc.line as c_uint,
2538                                 loc.col.to_uint() as c_uint)
2539                         };
2540
2541                         scope_stack.push(ScopeStackEntry {
2542                             scope_metadata: scope_metadata,
2543                             ident: Some(ident)
2544                         });
2545
2546                     } else {
2547                         // Push a new entry anyway so the name can be found
2548                         let prev_metadata = scope_stack.last().unwrap().scope_metadata;
2549                         scope_stack.push(ScopeStackEntry {
2550                             scope_metadata: prev_metadata,
2551                             ident: Some(ident)
2552                         });
2553                     }
2554                 }
2555
2556                 scope_map.insert(pat.id, scope_stack.last().unwrap().scope_metadata);
2557
2558                 for &sub_pat in sub_pat_opt.iter() {
2559                     walk_pattern(cx, sub_pat, scope_stack, scope_map);
2560                 }
2561             }
2562
2563             ast::PatWild | ast::PatWildMulti => {
2564                 scope_map.insert(pat.id, scope_stack.last().unwrap().scope_metadata);
2565             }
2566
2567             ast::PatEnum(_, ref sub_pats_opt) => {
2568                 scope_map.insert(pat.id, scope_stack.last().unwrap().scope_metadata);
2569
2570                 for ref sub_pats in sub_pats_opt.iter() {
2571                     for &p in sub_pats.iter() {
2572                         walk_pattern(cx, p, scope_stack, scope_map);
2573                     }
2574                 }
2575             }
2576
2577             ast::PatStruct(_, ref field_pats, _) => {
2578                 scope_map.insert(pat.id, scope_stack.last().unwrap().scope_metadata);
2579
2580                 for &ast::FieldPat { pat: sub_pat, .. } in field_pats.iter() {
2581                     walk_pattern(cx, sub_pat, scope_stack, scope_map);
2582                 }
2583             }
2584
2585             ast::PatTup(ref sub_pats) => {
2586                 scope_map.insert(pat.id, scope_stack.last().unwrap().scope_metadata);
2587
2588                 for &sub_pat in sub_pats.iter() {
2589                     walk_pattern(cx, sub_pat, scope_stack, scope_map);
2590                 }
2591             }
2592
2593             ast::PatUniq(sub_pat) | ast::PatRegion(sub_pat) => {
2594                 scope_map.insert(pat.id, scope_stack.last().unwrap().scope_metadata);
2595                 walk_pattern(cx, sub_pat, scope_stack, scope_map);
2596             }
2597
2598             ast::PatLit(exp) => {
2599                 scope_map.insert(pat.id, scope_stack.last().unwrap().scope_metadata);
2600                 walk_expr(cx, exp, scope_stack, scope_map);
2601             }
2602
2603             ast::PatRange(exp1, exp2) => {
2604                 scope_map.insert(pat.id, scope_stack.last().unwrap().scope_metadata);
2605                 walk_expr(cx, exp1, scope_stack, scope_map);
2606                 walk_expr(cx, exp2, scope_stack, scope_map);
2607             }
2608
2609             ast::PatVec(ref front_sub_pats, ref middle_sub_pats, ref back_sub_pats) => {
2610                 scope_map.insert(pat.id, scope_stack.last().unwrap().scope_metadata);
2611
2612                 for &sub_pat in front_sub_pats.iter() {
2613                     walk_pattern(cx, sub_pat, scope_stack, scope_map);
2614                 }
2615
2616                 for &sub_pat in middle_sub_pats.iter() {
2617                     walk_pattern(cx, sub_pat, scope_stack, scope_map);
2618                 }
2619
2620                 for &sub_pat in back_sub_pats.iter() {
2621                     walk_pattern(cx, sub_pat, scope_stack, scope_map);
2622                 }
2623             }
2624         }
2625     }
2626
2627     fn walk_expr(cx: &CrateContext,
2628                  exp: &ast::Expr,
2629                  scope_stack: &mut Vec<ScopeStackEntry> ,
2630                  scope_map: &mut HashMap<ast::NodeId, DIScope>) {
2631
2632         scope_map.insert(exp.id, scope_stack.last().unwrap().scope_metadata);
2633
2634         match exp.node {
2635             ast::ExprLit(_)   |
2636             ast::ExprBreak(_) |
2637             ast::ExprAgain(_) |
2638             ast::ExprPath(_)  => {}
2639
2640             ast::ExprVstore(sub_exp, _)   |
2641             ast::ExprCast(sub_exp, _)     |
2642             ast::ExprAddrOf(_, sub_exp)  |
2643             ast::ExprField(sub_exp, _, _) |
2644             ast::ExprParen(sub_exp)       => walk_expr(cx, sub_exp, scope_stack, scope_map),
2645
2646             ast::ExprBox(place, sub_expr) => {
2647                 walk_expr(cx, place, scope_stack, scope_map);
2648                 walk_expr(cx, sub_expr, scope_stack, scope_map);
2649             }
2650
2651             ast::ExprRet(exp_opt) => match exp_opt {
2652                 Some(sub_exp) => walk_expr(cx, sub_exp, scope_stack, scope_map),
2653                 None => ()
2654             },
2655
2656             ast::ExprUnary(_, sub_exp) => {
2657                 walk_expr(cx, sub_exp, scope_stack, scope_map);
2658             }
2659
2660             ast::ExprAssignOp(_, lhs, rhs) |
2661             ast::ExprIndex(lhs, rhs)        |
2662             ast::ExprBinary(_, lhs, rhs)    => {
2663                 walk_expr(cx, lhs, scope_stack, scope_map);
2664                 walk_expr(cx, rhs, scope_stack, scope_map);
2665             }
2666
2667             ast::ExprVec(ref init_expressions) |
2668             ast::ExprTup(ref init_expressions) => {
2669                 for ie in init_expressions.iter() {
2670                     walk_expr(cx, *ie, scope_stack, scope_map);
2671                 }
2672             }
2673
2674             ast::ExprAssign(sub_exp1, sub_exp2) |
2675             ast::ExprRepeat(sub_exp1, sub_exp2) => {
2676                 walk_expr(cx, sub_exp1, scope_stack, scope_map);
2677                 walk_expr(cx, sub_exp2, scope_stack, scope_map);
2678             }
2679
2680             ast::ExprIf(cond_exp, then_block, ref opt_else_exp) => {
2681                 walk_expr(cx, cond_exp, scope_stack, scope_map);
2682
2683                 with_new_scope(cx,
2684                                then_block.span,
2685                                scope_stack,
2686                                scope_map,
2687                                |cx, scope_stack, scope_map| {
2688                     walk_block(cx, then_block, scope_stack, scope_map);
2689                 });
2690
2691                 match *opt_else_exp {
2692                     Some(else_exp) => walk_expr(cx, else_exp, scope_stack, scope_map),
2693                     _ => ()
2694                 }
2695             }
2696
2697             ast::ExprWhile(cond_exp, loop_body) => {
2698                 walk_expr(cx, cond_exp, scope_stack, scope_map);
2699
2700                 with_new_scope(cx,
2701                                loop_body.span,
2702                                scope_stack,
2703                                scope_map,
2704                                |cx, scope_stack, scope_map| {
2705                     walk_block(cx, loop_body, scope_stack, scope_map);
2706                 })
2707             }
2708
2709             ast::ExprForLoop(_, _, _, _) => {
2710                 cx.sess().span_bug(exp.span, "debuginfo::populate_scope_map() - \
2711                                               Found unexpanded for-loop.");
2712             }
2713
2714             ast::ExprMac(_) => {
2715                 cx.sess().span_bug(exp.span, "debuginfo::populate_scope_map() - \
2716                                               Found unexpanded macro.");
2717             }
2718
2719             ast::ExprLoop(block, _) |
2720             ast::ExprBlock(block)   => {
2721                 with_new_scope(cx,
2722                                block.span,
2723                                scope_stack,
2724                                scope_map,
2725                                |cx, scope_stack, scope_map| {
2726                     walk_block(cx, block, scope_stack, scope_map);
2727                 })
2728             }
2729
2730             ast::ExprFnBlock(decl, block) |
2731             ast::ExprProc(decl, block) => {
2732                 with_new_scope(cx,
2733                                block.span,
2734                                scope_stack,
2735                                scope_map,
2736                                |cx, scope_stack, scope_map| {
2737                     for &ast::Arg { pat: pattern, .. } in decl.inputs.iter() {
2738                         walk_pattern(cx, pattern, scope_stack, scope_map);
2739                     }
2740
2741                     walk_block(cx, block, scope_stack, scope_map);
2742                 })
2743             }
2744
2745             ast::ExprCall(fn_exp, ref args) => {
2746                 walk_expr(cx, fn_exp, scope_stack, scope_map);
2747
2748                 for arg_exp in args.iter() {
2749                     walk_expr(cx, *arg_exp, scope_stack, scope_map);
2750                 }
2751             }
2752
2753             ast::ExprMethodCall(_, _, ref args) => {
2754                 for arg_exp in args.iter() {
2755                     walk_expr(cx, *arg_exp, scope_stack, scope_map);
2756                 }
2757             }
2758
2759             ast::ExprMatch(discriminant_exp, ref arms) => {
2760                 walk_expr(cx, discriminant_exp, scope_stack, scope_map);
2761
2762                 // for each arm we have to first walk the pattern as these might introduce new
2763                 // artificial scopes. It should be sufficient to walk only one pattern per arm, as
2764                 // they all must contain the same binding names
2765
2766                 for arm_ref in arms.iter() {
2767                     let arm_span = arm_ref.pats.get(0).span;
2768
2769                     with_new_scope(cx,
2770                                    arm_span,
2771                                    scope_stack,
2772                                    scope_map,
2773                                    |cx, scope_stack, scope_map| {
2774                         for &pat in arm_ref.pats.iter() {
2775                             walk_pattern(cx, pat, scope_stack, scope_map);
2776                         }
2777
2778                         for guard_exp in arm_ref.guard.iter() {
2779                             walk_expr(cx, *guard_exp, scope_stack, scope_map)
2780                         }
2781
2782                         walk_expr(cx, arm_ref.body, scope_stack, scope_map);
2783                     })
2784                 }
2785             }
2786
2787             ast::ExprStruct(_, ref fields, ref base_exp) => {
2788                 for &ast::Field { expr: exp, .. } in fields.iter() {
2789                     walk_expr(cx, exp, scope_stack, scope_map);
2790                 }
2791
2792                 match *base_exp {
2793                     Some(exp) => walk_expr(cx, exp, scope_stack, scope_map),
2794                     None => ()
2795                 }
2796             }
2797
2798             ast::ExprInlineAsm(ast::InlineAsm { inputs: ref inputs,
2799                                                 outputs: ref outputs,
2800                                                 .. }) => {
2801                 // inputs, outputs: ~[(~str, @expr)]
2802                 for &(_, exp) in inputs.iter() {
2803                     walk_expr(cx, exp, scope_stack, scope_map);
2804                 }
2805
2806                 for &(_, exp) in outputs.iter() {
2807                     walk_expr(cx, exp, scope_stack, scope_map);
2808                 }
2809             }
2810         }
2811     }
2812 }
2813
2814
2815 //=-------------------------------------------------------------------------------------------------
2816 // Namespace Handling
2817 //=-------------------------------------------------------------------------------------------------
2818
2819 struct NamespaceTreeNode {
2820     name: ast::Name,
2821     scope: DIScope,
2822     parent: Option<@NamespaceTreeNode>,
2823 }
2824
2825 impl NamespaceTreeNode {
2826     fn mangled_name_of_contained_item(&self, item_name: &str) -> ~str {
2827         fn fill_nested(node: &NamespaceTreeNode, output: &mut StrBuf) {
2828             match node.parent {
2829                 Some(parent) => fill_nested(parent, output),
2830                 None => {}
2831             }
2832             let string = token::get_name(node.name);
2833             output.push_str(format!("{}", string.get().len()));
2834             output.push_str(string.get());
2835         }
2836
2837         let mut name = StrBuf::from_str("_ZN");
2838         fill_nested(self, &mut name);
2839         name.push_str(format!("{}", item_name.len()));
2840         name.push_str(item_name);
2841         name.push_char('E');
2842         name.into_owned()
2843     }
2844 }
2845
2846 fn namespace_for_item(cx: &CrateContext, def_id: ast::DefId) -> @NamespaceTreeNode {
2847     ty::with_path(cx.tcx(), def_id, |path| {
2848         // prepend crate name if not already present
2849         let krate = if def_id.krate == ast::LOCAL_CRATE {
2850             let crate_namespace_ident = token::str_to_ident(cx.link_meta.crateid.name);
2851             Some(ast_map::PathMod(crate_namespace_ident.name))
2852         } else {
2853             None
2854         };
2855         let mut path = krate.move_iter().chain(path).peekable();
2856
2857         let mut current_key = Vec::new();
2858         let mut parent_node: Option<@NamespaceTreeNode> = None;
2859
2860         // Create/Lookup namespace for each element of the path.
2861         loop {
2862             // Emulate a for loop so we can use peek below.
2863             let path_element = match path.next() {
2864                 Some(e) => e,
2865                 None => break
2866             };
2867             // Ignore the name of the item (the last path element).
2868             if path.peek().is_none() {
2869                 break;
2870             }
2871
2872             let name = path_element.name();
2873             current_key.push(name);
2874
2875             let existing_node = debug_context(cx).namespace_map.borrow()
2876                                                  .find_copy(&current_key);
2877             let current_node = match existing_node {
2878                 Some(existing_node) => existing_node,
2879                 None => {
2880                     // create and insert
2881                     let parent_scope = match parent_node {
2882                         Some(node) => node.scope,
2883                         None => ptr::null()
2884                     };
2885                     let namespace_name = token::get_name(name);
2886                     let scope = namespace_name.get().with_c_str(|namespace_name| {
2887                         unsafe {
2888                             llvm::LLVMDIBuilderCreateNameSpace(
2889                                 DIB(cx),
2890                                 parent_scope,
2891                                 namespace_name,
2892                                 // cannot reconstruct file ...
2893                                 ptr::null(),
2894                                 // ... or line information, but that's not so important.
2895                                 0)
2896                         }
2897                     });
2898
2899                     let node = @NamespaceTreeNode {
2900                         name: name,
2901                         scope: scope,
2902                         parent: parent_node,
2903                     };
2904
2905                     debug_context(cx).namespace_map.borrow_mut()
2906                                      .insert(current_key.clone(), node);
2907
2908                     node
2909                 }
2910             };
2911
2912             parent_node = Some(current_node);
2913         }
2914
2915         match parent_node {
2916             Some(node) => node,
2917             None => {
2918                 cx.sess().bug(format!("debuginfo::namespace_for_item(): \
2919                     path too short for {:?}", def_id));
2920             }
2921         }
2922     })
2923 }