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