src/librustc/middle/trans/debuginfo.rs

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