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