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                 let string = token::get_ident(field.ident.name);
1145                 string.get().to_str()
1146             };
1147
1148             MemberDescription {
1149                 name: name,
1150                 llvm_type: type_of::type_of(cx, field.mt.ty),
1151                 type_metadata: type_metadata(cx, field.mt.ty, self.span),
1152                 offset: ComputedMemberOffset,
1153             }
1154         })
1155     }
1156 }
1157
1158 fn prepare_struct_metadata(cx: &CrateContext,
1159                            struct_type: ty::t,
1160                            def_id: ast::DefId,
1161                            substs: &ty::substs,
1162                            span: Span)
1163                         -> RecursiveTypeDescription {
1164     let struct_name = ppaux::ty_to_str(cx.tcx, struct_type);
1165     let struct_llvm_type = type_of::type_of(cx, struct_type);
1166
1167     let (containing_scope, definition_span) = get_namespace_and_span_for_item(cx, def_id, span);
1168
1169     let file_name = span_start(cx, definition_span).file.name.clone();
1170     let file_metadata = file_metadata(cx, file_name);
1171
1172     let struct_metadata_stub = create_struct_stub(cx,
1173                                                   struct_llvm_type,
1174                                                   struct_name,
1175                                                   containing_scope,
1176                                                   file_metadata,
1177                                                   definition_span);
1178
1179     let fields = ty::struct_fields(cx.tcx, def_id, substs);
1180
1181     UnfinishedMetadata {
1182         cache_id: cache_id_for_type(struct_type),
1183         metadata_stub: struct_metadata_stub,
1184         llvm_type: struct_llvm_type,
1185         file_metadata: file_metadata,
1186         member_description_factory: @StructMemberDescriptionFactory {
1187             fields: fields,
1188             span: span,
1189         } as @MemberDescriptionFactory,
1190     }
1191 }
1192
1193 enum RecursiveTypeDescription {
1194     UnfinishedMetadata {
1195         cache_id: uint,
1196         metadata_stub: DICompositeType,
1197         llvm_type: Type,
1198         file_metadata: DIFile,
1199         member_description_factory: @MemberDescriptionFactory,
1200     },
1201     FinalMetadata(DICompositeType)
1202 }
1203
1204 impl RecursiveTypeDescription {
1205
1206     fn finalize(&self, cx: &CrateContext) -> DICompositeType {
1207         match *self {
1208             FinalMetadata(metadata) => metadata,
1209             UnfinishedMetadata {
1210                 cache_id,
1211                 metadata_stub,
1212                 llvm_type,
1213                 file_metadata,
1214                 member_description_factory
1215             } => {
1216                 // Insert the stub into the cache in order to allow recursive references ...
1217                 {
1218                     let mut created_types = debug_context(cx).created_types.borrow_mut();
1219                     created_types.get().insert(cache_id, metadata_stub);
1220                 }
1221
1222                 // ... then create the member descriptions ...
1223                 let member_descriptions = member_description_factory.create_member_descriptions(cx);
1224
1225                 // ... and attach them to the stub to complete it.
1226                 set_members_of_composite_type(cx,
1227                                               metadata_stub,
1228                                               llvm_type,
1229                                               member_descriptions,
1230                                               file_metadata,
1231                                               codemap::DUMMY_SP);
1232                 return metadata_stub;
1233             }
1234         }
1235     }
1236 }
1237
1238 struct TupleMemberDescriptionFactory {
1239     component_types: ~[ty::t],
1240     span: Span,
1241 }
1242
1243 impl MemberDescriptionFactory for TupleMemberDescriptionFactory {
1244     fn create_member_descriptions(&self, cx: &CrateContext)
1245                                   -> ~[MemberDescription] {
1246         self.component_types.map(|&component_type| {
1247             MemberDescription {
1248                 name: ~"",
1249                 llvm_type: type_of::type_of(cx, component_type),
1250                 type_metadata: type_metadata(cx, component_type, self.span),
1251                 offset: ComputedMemberOffset,
1252             }
1253         })
1254     }
1255 }
1256
1257 fn prepare_tuple_metadata(cx: &CrateContext,
1258                           tuple_type: ty::t,
1259                           component_types: &[ty::t],
1260                           span: Span)
1261                        -> RecursiveTypeDescription {
1262     let tuple_name = ppaux::ty_to_str(cx.tcx, tuple_type);
1263     let tuple_llvm_type = type_of::type_of(cx, tuple_type);
1264
1265     let loc = span_start(cx, span);
1266     let file_metadata = file_metadata(cx, loc.file.name);
1267
1268     UnfinishedMetadata {
1269         cache_id: cache_id_for_type(tuple_type),
1270         metadata_stub: create_struct_stub(cx,
1271                                           tuple_llvm_type,
1272                                           tuple_name,
1273                                           file_metadata,
1274                                           file_metadata,
1275                                           span),
1276         llvm_type: tuple_llvm_type,
1277         file_metadata: file_metadata,
1278         member_description_factory: @TupleMemberDescriptionFactory {
1279             component_types: component_types.to_owned(),
1280             span: span,
1281         } as @MemberDescriptionFactory
1282     }
1283 }
1284
1285 struct GeneralMemberDescriptionFactory {
1286     type_rep: @adt::Repr,
1287     variants: @~[@ty::VariantInfo],
1288     discriminant_type_metadata: ValueRef,
1289     containing_scope: DIScope,
1290     file_metadata: DIFile,
1291     span: Span,
1292 }
1293
1294 impl MemberDescriptionFactory for GeneralMemberDescriptionFactory {
1295     fn create_member_descriptions(&self, cx: &CrateContext)
1296                                   -> ~[MemberDescription] {
1297         // Capture type_rep, so we don't have to copy the struct_defs array
1298         let struct_defs = match *self.type_rep {
1299             adt::General(_, ref struct_defs) => struct_defs,
1300             _ => cx.sess.bug("unreachable")
1301         };
1302
1303         struct_defs
1304             .iter()
1305             .enumerate()
1306             .map(|(i, struct_def)| {
1307                 let (variant_type_metadata, variant_llvm_type, member_desc_factory) =
1308                     describe_enum_variant(cx,
1309                                           struct_def,
1310                                           self.variants[i],
1311                                           Some(self.discriminant_type_metadata),
1312                                           self.containing_scope,
1313                                           self.file_metadata,
1314                                           self.span);
1315
1316                 let member_descriptions =
1317                     member_desc_factory.create_member_descriptions(cx);
1318
1319                 set_members_of_composite_type(cx,
1320                                               variant_type_metadata,
1321                                               variant_llvm_type,
1322                                               member_descriptions,
1323                                               self.file_metadata,
1324                                               codemap::DUMMY_SP);
1325                 MemberDescription {
1326                     name: ~"",
1327                     llvm_type: variant_llvm_type,
1328                     type_metadata: variant_type_metadata,
1329                     offset: FixedMemberOffset { bytes: 0 },
1330                 }
1331         }).collect()
1332     }
1333 }
1334
1335 struct EnumVariantMemberDescriptionFactory {
1336     args: ~[(~str, ty::t)],
1337     discriminant_type_metadata: Option<DIType>,
1338     span: Span,
1339 }
1340
1341 impl MemberDescriptionFactory for EnumVariantMemberDescriptionFactory {
1342     fn create_member_descriptions(&self, cx: &CrateContext)
1343                                   -> ~[MemberDescription] {
1344         self.args.iter().enumerate().map(|(i, &(ref name, ty))| {
1345             MemberDescription {
1346                 name: name.to_str(),
1347                 llvm_type: type_of::type_of(cx, ty),
1348                 type_metadata: match self.discriminant_type_metadata {
1349                     Some(metadata) if i == 0 => metadata,
1350                     _ => type_metadata(cx, ty, self.span)
1351                 },
1352                 offset: ComputedMemberOffset,
1353             }
1354         }).collect()
1355     }
1356 }
1357
1358 fn describe_enum_variant(cx: &CrateContext,
1359                          struct_def: &adt::Struct,
1360                          variant_info: &ty::VariantInfo,
1361                          discriminant_type_metadata: Option<DIType>,
1362                          containing_scope: DIScope,
1363                          file_metadata: DIFile,
1364                          span: Span)
1365                       -> (DICompositeType, Type, @MemberDescriptionFactory) {
1366     let variant_name = token::ident_to_str(&variant_info.name);
1367     let variant_llvm_type = Type::struct_(struct_def.fields.map(|&t| type_of::type_of(cx, t)),
1368                                           struct_def.packed);
1369     // Could some consistency checks here: size, align, field count, discr type
1370
1371     // Find the source code location of the variant's definition
1372     let variant_definition_span = if variant_info.id.crate == ast::LOCAL_CRATE {
1373         {
1374             match cx.tcx.items.find(variant_info.id.node) {
1375                 Some(ast_map::NodeVariant(ref variant, _, _)) => variant.span,
1376                 ref node => {
1377                     cx.sess.span_warn(span,
1378                         format!("debuginfo::enum_metadata()::\
1379                                  adt_struct_metadata() - Unexpected node \
1380                                  type: {:?}. This is a bug.", node));
1381                     codemap::DUMMY_SP
1382                 }
1383             }
1384         }
1385     } else {
1386         // For definitions from other crates we have no location information available.
1387         codemap::DUMMY_SP
1388     };
1389
1390     let metadata_stub = create_struct_stub(cx,
1391                                            variant_llvm_type,
1392                                            variant_name,
1393                                            containing_scope,
1394                                            file_metadata,
1395                                            variant_definition_span);
1396
1397     // Get the argument names from the enum variant info
1398     let mut arg_names = match variant_info.arg_names {
1399         Some(ref names) => {
1400             names.map(|ident| {
1401                 let string = token::get_ident(ident.name);
1402                 string.get().to_str()
1403             })
1404         }
1405         None => variant_info.args.map(|_| ~"")
1406     };
1407
1408     // If this is not a univariant enum, there is also the (unnamed) discriminant field
1409     if discriminant_type_metadata.is_some() {
1410         arg_names.insert(0, ~"");
1411     }
1412
1413     // Build an array of (field name, field type) pairs to be captured in the factory closure.
1414     let args: ~[(~str, ty::t)] = arg_names.iter()
1415         .zip(struct_def.fields.iter())
1416         .map(|(s, &t)| (s.to_str(), t))
1417         .collect();
1418
1419     let member_description_factory =
1420         @EnumVariantMemberDescriptionFactory {
1421             args: args,
1422             discriminant_type_metadata: discriminant_type_metadata,
1423             span: span,
1424         } as @MemberDescriptionFactory;
1425
1426     (metadata_stub, variant_llvm_type, member_description_factory)
1427 }
1428
1429 fn prepare_enum_metadata(cx: &CrateContext,
1430                          enum_type: ty::t,
1431                          enum_def_id: ast::DefId,
1432                          span: Span)
1433                       -> RecursiveTypeDescription {
1434     let enum_name = ppaux::ty_to_str(cx.tcx, enum_type);
1435
1436     let (containing_scope, definition_span) = get_namespace_and_span_for_item(cx,
1437                                                                               enum_def_id,
1438                                                                               span);
1439     let loc = span_start(cx, definition_span);
1440     let file_metadata = file_metadata(cx, loc.file.name);
1441
1442     // For empty enums there is an early exit. Just describe it as an empty struct with the
1443     // appropriate type name
1444     if ty::type_is_empty(cx.tcx, enum_type) {
1445         let empty_type_metadata = composite_type_metadata(cx,
1446                                                           Type::nil(),
1447                                                           enum_name,
1448                                                           [],
1449                                                           containing_scope,
1450                                                           file_metadata,
1451                                                           definition_span);
1452
1453         return FinalMetadata(empty_type_metadata);
1454     }
1455
1456     let variants = ty::enum_variants(cx.tcx, enum_def_id);
1457
1458     let enumerators_metadata: ~[DIDescriptor] = variants
1459         .iter()
1460         .map(|v| {
1461             let name: &str = token::ident_to_str(&v.name);
1462             let discriminant_value = v.disr_val as c_ulonglong;
1463
1464             name.with_c_str(|name| {
1465                 unsafe {
1466                     llvm::LLVMDIBuilderCreateEnumerator(
1467                         DIB(cx),
1468                         name,
1469                         discriminant_value)
1470                 }
1471             })
1472         })
1473         .collect();
1474
1475     let discriminant_type_metadata = |inttype| {
1476         let discriminant_llvm_type = adt::ll_inttype(cx, inttype);
1477         let (discriminant_size, discriminant_align) = size_and_align_of(cx, discriminant_llvm_type);
1478         let discriminant_base_type_metadata = type_metadata(cx, adt::ty_of_inttype(inttype),
1479                                                             codemap::DUMMY_SP);
1480         enum_name.with_c_str(|enum_name| {
1481             unsafe {
1482                 llvm::LLVMDIBuilderCreateEnumerationType(
1483                     DIB(cx),
1484                     containing_scope,
1485                     enum_name,
1486                     file_metadata,
1487                     loc.line as c_uint,
1488                     bytes_to_bits(discriminant_size),
1489                     bytes_to_bits(discriminant_align),
1490                     create_DIArray(DIB(cx), enumerators_metadata),
1491                     discriminant_base_type_metadata)
1492             }
1493         })
1494     };
1495
1496     let type_rep = adt::represent_type(cx, enum_type);
1497
1498     return match *type_rep {
1499         adt::CEnum(inttype, _, _) => {
1500             FinalMetadata(discriminant_type_metadata(inttype))
1501         }
1502         adt::Univariant(ref struct_def, _) => {
1503             assert!(variants.len() == 1);
1504             let (metadata_stub,
1505                  variant_llvm_type,
1506                  member_description_factory) = describe_enum_variant(cx,
1507                                                                      struct_def,
1508                                                                      variants[0],
1509                                                                      None,
1510                                                                      containing_scope,
1511                                                                      file_metadata,
1512                                                                      span);
1513             UnfinishedMetadata {
1514                 cache_id: cache_id_for_type(enum_type),
1515                 metadata_stub: metadata_stub,
1516                 llvm_type: variant_llvm_type,
1517                 file_metadata: file_metadata,
1518                 member_description_factory: member_description_factory
1519             }
1520         }
1521         adt::General(inttype, _) => {
1522             let discriminant_type_metadata = discriminant_type_metadata(inttype);
1523             let enum_llvm_type = type_of::type_of(cx, enum_type);
1524             let (enum_type_size, enum_type_align) = size_and_align_of(cx, enum_llvm_type);
1525             let unique_id = generate_unique_type_id("DI_ENUM_");
1526
1527             let enum_metadata = enum_name.with_c_str(|enum_name| {
1528                 unique_id.with_c_str(|unique_id| {
1529                     unsafe {
1530                         llvm::LLVMDIBuilderCreateUnionType(
1531                         DIB(cx),
1532                         containing_scope,
1533                         enum_name,
1534                         file_metadata,
1535                         loc.line as c_uint,
1536                         bytes_to_bits(enum_type_size),
1537                         bytes_to_bits(enum_type_align),
1538                         0, // Flags
1539                         ptr::null(),
1540                         0, // RuntimeLang
1541                         unique_id)
1542                     }
1543                 })
1544             });
1545
1546             UnfinishedMetadata {
1547                 cache_id: cache_id_for_type(enum_type),
1548                 metadata_stub: enum_metadata,
1549                 llvm_type: enum_llvm_type,
1550                 file_metadata: file_metadata,
1551                 member_description_factory: @GeneralMemberDescriptionFactory {
1552                     type_rep: type_rep,
1553                     variants: variants,
1554                     discriminant_type_metadata: discriminant_type_metadata,
1555                     containing_scope: containing_scope,
1556                     file_metadata: file_metadata,
1557                     span: span,
1558                 } as @MemberDescriptionFactory,
1559             }
1560         }
1561         adt::NullablePointer { nonnull: ref struct_def, nndiscr, .. } => {
1562             let (metadata_stub,
1563                  variant_llvm_type,
1564                  member_description_factory) = describe_enum_variant(cx,
1565                                                                      struct_def,
1566                                                                      variants[nndiscr],
1567                                                                      None,
1568                                                                      containing_scope,
1569                                                                      file_metadata,
1570                                                                      span);
1571             UnfinishedMetadata {
1572                 cache_id: cache_id_for_type(enum_type),
1573                 metadata_stub: metadata_stub,
1574                 llvm_type: variant_llvm_type,
1575                 file_metadata: file_metadata,
1576                 member_description_factory: member_description_factory
1577             }
1578         }
1579     };
1580 }
1581
1582 enum MemberOffset {
1583     FixedMemberOffset { bytes: uint },
1584     // For ComputedMemberOffset, the offset is read from the llvm type definition
1585     ComputedMemberOffset
1586 }
1587
1588 struct MemberDescription {
1589     name: ~str,
1590     llvm_type: Type,
1591     type_metadata: DIType,
1592     offset: MemberOffset,
1593 }
1594
1595 /// Creates debug information for a composite type, that is, anything that results in a LLVM struct.
1596 ///
1597 /// Examples of Rust types to use this are: structs, tuples, boxes, vecs, and enums.
1598 fn composite_type_metadata(cx: &CrateContext,
1599                            composite_llvm_type: Type,
1600                            composite_type_name: &str,
1601                            member_descriptions: &[MemberDescription],
1602                            containing_scope: DIScope,
1603                            file_metadata: DIFile,
1604                            definition_span: Span)
1605                         -> DICompositeType {
1606     // Create the (empty) struct metadata node ...
1607     let composite_type_metadata = create_struct_stub(cx,
1608                                                      composite_llvm_type,
1609                                                      composite_type_name,
1610                                                      containing_scope,
1611                                                      file_metadata,
1612                                                      definition_span);
1613
1614     // ... and immediately create and add the member descriptions.
1615     set_members_of_composite_type(cx,
1616                                   composite_type_metadata,
1617                                   composite_llvm_type,
1618                                   member_descriptions,
1619                                   file_metadata,
1620                                   definition_span);
1621
1622     return composite_type_metadata;
1623 }
1624
1625 fn set_members_of_composite_type(cx: &CrateContext,
1626                                  composite_type_metadata: DICompositeType,
1627                                  composite_llvm_type: Type,
1628                                  member_descriptions: &[MemberDescription],
1629                                  file_metadata: DIFile,
1630                                  definition_span: Span) {
1631     // In some rare cases LLVM metadata uniquing would lead to an existing type description being
1632     // used instead of a new one created in create_struct_stub. This would cause a hard to trace
1633     // assertion in DICompositeType::SetTypeArray(). The following check makes sure that we get a
1634     // better error message if this should happen again due to some regression.
1635     {
1636         let mut composite_types_completed =
1637             debug_context(cx).composite_types_completed.borrow_mut();
1638         if composite_types_completed.get().contains(&composite_type_metadata) {
1639             cx.sess.span_bug(definition_span, "debuginfo::set_members_of_composite_type() - \
1640                                                Already completed forward declaration \
1641                                                re-encountered.");
1642         } else {
1643             composite_types_completed.get().insert(composite_type_metadata);
1644         }
1645     }
1646
1647     let loc = span_start(cx, definition_span);
1648
1649     let member_metadata: ~[DIDescriptor] = member_descriptions
1650         .iter()
1651         .enumerate()
1652         .map(|(i, member_description)| {
1653             let (member_size, member_align) = size_and_align_of(cx, member_description.llvm_type);
1654             let member_offset = match member_description.offset {
1655                 FixedMemberOffset { bytes } => bytes as u64,
1656                 ComputedMemberOffset => machine::llelement_offset(cx, composite_llvm_type, i)
1657             };
1658
1659             member_description.name.with_c_str(|member_name| {
1660                 unsafe {
1661                     llvm::LLVMDIBuilderCreateMemberType(
1662                         DIB(cx),
1663                         composite_type_metadata,
1664                         member_name,
1665                         file_metadata,
1666                         loc.line as c_uint,
1667                         bytes_to_bits(member_size),
1668                         bytes_to_bits(member_align),
1669                         bytes_to_bits(member_offset),
1670                         0,
1671                         member_description.type_metadata)
1672                 }
1673             })
1674         })
1675         .collect();
1676
1677     unsafe {
1678         let type_array = create_DIArray(DIB(cx), member_metadata);
1679         llvm::LLVMDICompositeTypeSetTypeArray(composite_type_metadata, type_array);
1680     }
1681 }
1682
1683 // A convenience wrapper around LLVMDIBuilderCreateStructType(). Does not do any caching, does not
1684 // add any fields to the struct. This can be done later with set_members_of_composite_type().
1685 fn create_struct_stub(cx: &CrateContext,
1686                       struct_llvm_type: Type,
1687                       struct_type_name: &str,
1688                       containing_scope: DIScope,
1689                       file_metadata: DIFile,
1690                       definition_span: Span)
1691                    -> DICompositeType {
1692     let loc = span_start(cx, definition_span);
1693     let (struct_size, struct_align) = size_and_align_of(cx, struct_llvm_type);
1694
1695     // We assign unique IDs to the type stubs so LLVM metadata uniquing does not reuse instances
1696     // where we don't want it.
1697     let unique_id = generate_unique_type_id("DI_STRUCT_");
1698
1699     return unsafe {
1700         struct_type_name.with_c_str(|name| {
1701             unique_id.with_c_str(|unique_id| {
1702                 // LLVMDIBuilderCreateStructType() wants an empty array. A null pointer will lead to
1703                 // hard to trace and debug LLVM assertions later on in llvm/lib/IR/Value.cpp
1704                 let empty_array = create_DIArray(DIB(cx), []);
1705
1706                 llvm::LLVMDIBuilderCreateStructType(
1707                     DIB(cx),
1708                     containing_scope,
1709                     name,
1710                     file_metadata,
1711                     loc.line as c_uint,
1712                     bytes_to_bits(struct_size),
1713                     bytes_to_bits(struct_align),
1714                     0,
1715                     ptr::null(),
1716                     empty_array,
1717                     0,
1718                     ptr::null(),
1719                     unique_id)
1720             })
1721         })
1722     };
1723 }
1724
1725 fn boxed_type_metadata(cx: &CrateContext,
1726                        content_type_name: Option<&str>,
1727                        content_llvm_type: Type,
1728                        content_type_metadata: DIType,
1729                        span: Span)
1730                     -> DICompositeType {
1731     let box_type_name = match content_type_name {
1732         Some(content_type_name) => format!("Boxed<{}>", content_type_name),
1733         None                    => ~"BoxedType"
1734     };
1735
1736     let box_llvm_type = Type::at_box(cx, content_llvm_type);
1737     let member_llvm_types = box_llvm_type.field_types();
1738     assert!(box_layout_is_correct(cx, member_llvm_types, content_llvm_type));
1739
1740     let int_type = ty::mk_int();
1741     let nil_pointer_type = ty::mk_nil_ptr(cx.tcx);
1742     let nil_pointer_type_metadata = type_metadata(cx, nil_pointer_type, codemap::DUMMY_SP);
1743
1744     let member_descriptions = [
1745         MemberDescription {
1746             name: ~"refcnt",
1747             llvm_type: member_llvm_types[0],
1748             type_metadata: type_metadata(cx, int_type, codemap::DUMMY_SP),
1749             offset: ComputedMemberOffset,
1750         },
1751         MemberDescription {
1752             name: ~"tydesc",
1753             llvm_type: member_llvm_types[1],
1754             type_metadata: nil_pointer_type_metadata,
1755             offset: ComputedMemberOffset,
1756         },
1757         MemberDescription {
1758             name: ~"prev",
1759             llvm_type: member_llvm_types[2],
1760             type_metadata: nil_pointer_type_metadata,
1761             offset: ComputedMemberOffset,
1762         },
1763         MemberDescription {
1764             name: ~"next",
1765             llvm_type: member_llvm_types[3],
1766             type_metadata: nil_pointer_type_metadata,
1767             offset: ComputedMemberOffset,
1768         },
1769         MemberDescription {
1770             name: ~"val",
1771             llvm_type: member_llvm_types[4],
1772             type_metadata: content_type_metadata,
1773             offset: ComputedMemberOffset,
1774         }
1775     ];
1776
1777     let loc = span_start(cx, span);
1778     let file_metadata = file_metadata(cx, loc.file.name);
1779
1780     return composite_type_metadata(
1781         cx,
1782         box_llvm_type,
1783         box_type_name,
1784         member_descriptions,
1785         file_metadata,
1786         file_metadata,
1787         span);
1788
1789     // Unfortunately, we cannot assert anything but the correct types here---and not whether the
1790     // 'next' and 'prev' pointers are in the correct order.
1791     fn box_layout_is_correct(cx: &CrateContext,
1792                              member_llvm_types: &[Type],
1793                              content_llvm_type: Type)
1794                           -> bool {
1795         member_llvm_types.len() == 5 &&
1796         member_llvm_types[0] == cx.int_type &&
1797         member_llvm_types[1] == cx.tydesc_type.ptr_to() &&
1798         member_llvm_types[2] == Type::i8().ptr_to() &&
1799         member_llvm_types[3] == Type::i8().ptr_to() &&
1800         member_llvm_types[4] == content_llvm_type
1801     }
1802 }
1803
1804 fn fixed_vec_metadata(cx: &CrateContext,
1805                       element_type: ty::t,
1806                       len: uint,
1807                       span: Span)
1808                    -> DIType {
1809     let element_type_metadata = type_metadata(cx, element_type, span);
1810     let element_llvm_type = type_of::type_of(cx, element_type);
1811     let (element_type_size, element_type_align) = size_and_align_of(cx, element_llvm_type);
1812
1813     let subrange = unsafe {
1814         llvm::LLVMDIBuilderGetOrCreateSubrange(
1815         DIB(cx),
1816         0,
1817         len as c_longlong)
1818     };
1819
1820     let subscripts = create_DIArray(DIB(cx), [subrange]);
1821     return unsafe {
1822         llvm::LLVMDIBuilderCreateArrayType(
1823             DIB(cx),
1824             bytes_to_bits(element_type_size * (len as u64)),
1825             bytes_to_bits(element_type_align),
1826             element_type_metadata,
1827             subscripts)
1828     };
1829 }
1830
1831 fn vec_metadata(cx: &CrateContext,
1832                 element_type: ty::t,
1833                 span: Span)
1834              -> DICompositeType {
1835
1836     let element_type_metadata = type_metadata(cx, element_type, span);
1837     let element_llvm_type = type_of::type_of(cx, element_type);
1838     let (element_size, element_align) = size_and_align_of(cx, element_llvm_type);
1839
1840     let vec_llvm_type = Type::vec(cx.sess.targ_cfg.arch, &element_llvm_type);
1841     let vec_type_name: &str = format!("[{}]", ppaux::ty_to_str(cx.tcx, element_type));
1842
1843     let member_llvm_types = vec_llvm_type.field_types();
1844
1845     let int_type_metadata = type_metadata(cx, ty::mk_int(), span);
1846     let array_type_metadata = unsafe {
1847         llvm::LLVMDIBuilderCreateArrayType(
1848             DIB(cx),
1849             bytes_to_bits(element_size),
1850             bytes_to_bits(element_align),
1851             element_type_metadata,
1852             create_DIArray(DIB(cx), [llvm::LLVMDIBuilderGetOrCreateSubrange(DIB(cx), 0, 0)]))
1853     };
1854
1855     let member_descriptions = [
1856         MemberDescription {
1857             name: ~"fill",
1858             llvm_type: member_llvm_types[0],
1859             type_metadata: int_type_metadata,
1860             offset: ComputedMemberOffset,
1861         },
1862         MemberDescription {
1863             name: ~"alloc",
1864             llvm_type: member_llvm_types[1],
1865             type_metadata: int_type_metadata,
1866             offset: ComputedMemberOffset,
1867         },
1868         MemberDescription {
1869             name: ~"elements",
1870             llvm_type: member_llvm_types[2],
1871             type_metadata: array_type_metadata,
1872             offset: ComputedMemberOffset,
1873         }
1874     ];
1875
1876     assert!(member_descriptions.len() == member_llvm_types.len());
1877
1878     let loc = span_start(cx, span);
1879     let file_metadata = file_metadata(cx, loc.file.name);
1880
1881     return composite_type_metadata(
1882         cx,
1883         vec_llvm_type,
1884         vec_type_name,
1885         member_descriptions,
1886         file_metadata,
1887         file_metadata,
1888         span);
1889 }
1890
1891 fn boxed_vec_metadata(cx: &CrateContext,
1892                       element_type: ty::t,
1893                       span: Span)
1894                    -> DICompositeType {
1895     let element_llvm_type = type_of::type_of(cx, element_type);
1896     let vec_llvm_type = Type::vec(cx.sess.targ_cfg.arch, &element_llvm_type);
1897     let vec_type_name: &str = format!("[{}]", ppaux::ty_to_str(cx.tcx, element_type));
1898     let vec_metadata = vec_metadata(cx, element_type, span);
1899
1900     return boxed_type_metadata(
1901         cx,
1902         Some(vec_type_name),
1903         vec_llvm_type,
1904         vec_metadata,
1905         span);
1906 }
1907
1908 fn vec_slice_metadata(cx: &CrateContext,
1909                       vec_type: ty::t,
1910                       element_type: ty::t,
1911                       span: Span)
1912                    -> DICompositeType {
1913
1914     debug!("vec_slice_metadata: {:?}", ty::get(vec_type));
1915
1916     let slice_llvm_type = type_of::type_of(cx, vec_type);
1917     let slice_type_name = ppaux::ty_to_str(cx.tcx, vec_type);
1918
1919     let member_llvm_types = slice_llvm_type.field_types();
1920     assert!(slice_layout_is_correct(cx, member_llvm_types, element_type));
1921
1922     let data_ptr_type = ty::mk_ptr(cx.tcx, ty::mt { ty: element_type, mutbl: ast::MutImmutable });
1923
1924     let member_descriptions = [
1925         MemberDescription {
1926             name: ~"data_ptr",
1927             llvm_type: member_llvm_types[0],
1928             type_metadata: type_metadata(cx, data_ptr_type, span),
1929             offset: ComputedMemberOffset,
1930         },
1931         MemberDescription {
1932             name: ~"length",
1933             llvm_type: member_llvm_types[1],
1934             type_metadata: type_metadata(cx, ty::mk_uint(), span),
1935             offset: ComputedMemberOffset,
1936         },
1937     ];
1938
1939     assert!(member_descriptions.len() == member_llvm_types.len());
1940
1941     let loc = span_start(cx, span);
1942     let file_metadata = file_metadata(cx, loc.file.name);
1943
1944     return composite_type_metadata(
1945         cx,
1946         slice_llvm_type,
1947         slice_type_name,
1948         member_descriptions,
1949         file_metadata,
1950         file_metadata,
1951         span);
1952
1953     fn slice_layout_is_correct(cx: &CrateContext,
1954                                member_llvm_types: &[Type],
1955                                element_type: ty::t)
1956                             -> bool {
1957         member_llvm_types.len() == 2 &&
1958         member_llvm_types[0] == type_of::type_of(cx, element_type).ptr_to() &&
1959         member_llvm_types[1] == cx.int_type
1960     }
1961 }
1962
1963 fn subroutine_type_metadata(cx: &CrateContext,
1964                             signature: &ty::FnSig,
1965                             span: Span)
1966                          -> DICompositeType {
1967     let loc = span_start(cx, span);
1968     let file_metadata = file_metadata(cx, loc.file.name);
1969
1970     let mut signature_metadata: ~[DIType] = vec::with_capacity(signature.inputs.len() + 1);
1971
1972     // return type
1973     signature_metadata.push(match ty::get(signature.output).sty {
1974         ty::ty_nil => ptr::null(),
1975         _ => type_metadata(cx, signature.output, span)
1976     });
1977
1978     // regular arguments
1979     for &argument_type in signature.inputs.iter() {
1980         signature_metadata.push(type_metadata(cx, argument_type, span));
1981     }
1982
1983     return unsafe {
1984         llvm::LLVMDIBuilderCreateSubroutineType(
1985             DIB(cx),
1986             file_metadata,
1987             create_DIArray(DIB(cx), signature_metadata))
1988     };
1989 }
1990
1991 fn trait_metadata(cx: &CrateContext,
1992                   def_id: ast::DefId,
1993                   trait_type: ty::t,
1994                   substs: &ty::substs,
1995                   trait_store: ty::TraitStore,
1996                   mutability: ast::Mutability,
1997                   _: &ty::BuiltinBounds,
1998                   usage_site_span: Span)
1999                -> DIType {
2000     // The implementation provided here is a stub. It makes sure that the trait type is
2001     // assigned the correct name, size, namespace, and source location. But it does not describe
2002     // the trait's methods.
2003     let path = ty::item_path(cx.tcx, def_id);
2004     let ident = path.last().unwrap().ident();
2005     let name = ppaux::trait_store_to_str(cx.tcx, trait_store) +
2006                ppaux::mutability_to_str(mutability) +
2007                token::ident_to_str(&ident);
2008     // Add type and region parameters
2009     let name = ppaux::parameterized(cx.tcx, name, &substs.regions,
2010                                     substs.tps, def_id, true);
2011
2012     let (containing_scope, definition_span) =
2013         get_namespace_and_span_for_item(cx, def_id, usage_site_span);
2014
2015     let file_name = span_start(cx, definition_span).file.name.clone();
2016     let file_metadata = file_metadata(cx, file_name);
2017
2018     let trait_llvm_type = type_of::type_of(cx, trait_type);
2019
2020     return composite_type_metadata(cx,
2021                                    trait_llvm_type,
2022                                    name,
2023                                    [],
2024                                    containing_scope,
2025                                    file_metadata,
2026                                    definition_span);
2027 }
2028
2029 fn type_metadata(cx: &CrateContext,
2030                  t: ty::t,
2031                  usage_site_span: Span)
2032               -> DIType {
2033     let cache_id = cache_id_for_type(t);
2034
2035     {
2036         let created_types = debug_context(cx).created_types.borrow();
2037         match created_types.get().find(&cache_id) {
2038             Some(type_metadata) => return *type_metadata,
2039             None => ()
2040         }
2041     }
2042
2043     fn create_pointer_to_box_metadata(cx: &CrateContext,
2044                                       pointer_type: ty::t,
2045                                       type_in_box: ty::t)
2046                                    -> DIType {
2047         let content_type_name: &str = ppaux::ty_to_str(cx.tcx, type_in_box);
2048         let content_llvm_type = type_of::type_of(cx, type_in_box);
2049         let content_type_metadata = type_metadata(
2050             cx,
2051             type_in_box,
2052             codemap::DUMMY_SP);
2053
2054         let box_metadata = boxed_type_metadata(
2055             cx,
2056             Some(content_type_name),
2057             content_llvm_type,
2058             content_type_metadata,
2059             codemap::DUMMY_SP);
2060
2061         pointer_type_metadata(cx, pointer_type, box_metadata)
2062     }
2063
2064     debug!("type_metadata: {:?}", ty::get(t));
2065
2066     let sty = &ty::get(t).sty;
2067     let type_metadata = match *sty {
2068         ty::ty_nil      |
2069         ty::ty_bot      |
2070         ty::ty_bool     |
2071         ty::ty_char     |
2072         ty::ty_int(_)   |
2073         ty::ty_uint(_)  |
2074         ty::ty_float(_) => {
2075             basic_type_metadata(cx, t)
2076         },
2077         ty::ty_str(ref vstore) => {
2078             let i8_t = ty::mk_i8();
2079             match *vstore {
2080                 ty::vstore_fixed(len) => {
2081                     fixed_vec_metadata(cx, i8_t, len + 1, usage_site_span)
2082                 },
2083                 ty::vstore_uniq  => {
2084                     let vec_metadata = vec_metadata(cx, i8_t, usage_site_span);
2085                     pointer_type_metadata(cx, t, vec_metadata)
2086                 }
2087                 ty::vstore_box => {
2088                     let boxed_vec_metadata = boxed_vec_metadata(cx, i8_t, usage_site_span);
2089                     pointer_type_metadata(cx, t, boxed_vec_metadata)
2090                 }
2091                 ty::vstore_slice(_region) => {
2092                     vec_slice_metadata(cx, t, i8_t, usage_site_span)
2093                 }
2094             }
2095         },
2096         ty::ty_enum(def_id, _) => {
2097             prepare_enum_metadata(cx, t, def_id, usage_site_span).finalize(cx)
2098         },
2099         ty::ty_box(typ) => {
2100             create_pointer_to_box_metadata(cx, t, typ)
2101         },
2102         ty::ty_vec(ref mt, ref vstore) => {
2103             match *vstore {
2104                 ty::vstore_fixed(len) => {
2105                     fixed_vec_metadata(cx, mt.ty, len, usage_site_span)
2106                 }
2107                 ty::vstore_uniq => {
2108                     let vec_metadata = vec_metadata(cx, mt.ty, usage_site_span);
2109                     pointer_type_metadata(cx, t, vec_metadata)
2110                 }
2111                 ty::vstore_box => {
2112                     let boxed_vec_metadata = boxed_vec_metadata(cx, mt.ty, usage_site_span);
2113                     pointer_type_metadata(cx, t, boxed_vec_metadata)
2114                 }
2115                 ty::vstore_slice(_) => {
2116                     vec_slice_metadata(cx, t, mt.ty, usage_site_span)
2117                 }
2118             }
2119         },
2120         ty::ty_uniq(typ) => {
2121             let pointee = type_metadata(cx, typ, usage_site_span);
2122             pointer_type_metadata(cx, t, pointee)
2123         }
2124         ty::ty_ptr(ref mt) | ty::ty_rptr(_, ref mt) => {
2125             let pointee = type_metadata(cx, mt.ty, usage_site_span);
2126             pointer_type_metadata(cx, t, pointee)
2127         },
2128         ty::ty_bare_fn(ref barefnty) => {
2129             subroutine_type_metadata(cx, &barefnty.sig, usage_site_span)
2130         },
2131         ty::ty_closure(ref closurety) => {
2132             subroutine_type_metadata(cx, &closurety.sig, usage_site_span)
2133         },
2134         ty::ty_trait(def_id, ref substs, trait_store, mutability, ref bounds) => {
2135             trait_metadata(cx, def_id, t, substs, trait_store, mutability, bounds, usage_site_span)
2136         },
2137         ty::ty_struct(def_id, ref substs) => {
2138             prepare_struct_metadata(cx, t, def_id, substs, usage_site_span).finalize(cx)
2139         },
2140         ty::ty_tup(ref elements) => {
2141             prepare_tuple_metadata(cx, t, *elements, usage_site_span).finalize(cx)
2142         }
2143         _ => cx.sess.bug(format!("debuginfo: unexpected type in type_metadata: {:?}", sty))
2144     };
2145
2146     let mut created_types = debug_context(cx).created_types.borrow_mut();
2147     created_types.get().insert(cache_id, type_metadata);
2148     type_metadata
2149 }
2150
2151 #[deriving(Eq)]
2152 enum DebugLocation {
2153     KnownLocation { scope: DIScope, line: uint, col: uint },
2154     UnknownLocation
2155 }
2156
2157 impl DebugLocation {
2158     fn new(scope: DIScope, line: uint, col: uint) -> DebugLocation {
2159         KnownLocation {
2160             scope: scope,
2161             line: line,
2162             col: col,
2163         }
2164     }
2165 }
2166
2167 fn set_debug_location(cx: &CrateContext, debug_location: DebugLocation) {
2168     if debug_location == debug_context(cx).current_debug_location.get() {
2169         return;
2170     }
2171
2172     let metadata_node;
2173
2174     match debug_location {
2175         KnownLocation { scope, line, .. } => {
2176             let col = 0; // Always set the column to zero like Clang and GCC
2177             debug!("setting debug location to {} {}", line, col);
2178             let elements = [C_i32(line as i32), C_i32(col as i32), scope, ptr::null()];
2179             unsafe {
2180                 metadata_node = llvm::LLVMMDNodeInContext(debug_context(cx).llcontext,
2181                                                           elements.as_ptr(),
2182                                                           elements.len() as c_uint);
2183             }
2184         }
2185         UnknownLocation => {
2186             debug!("clearing debug location ");
2187             metadata_node = ptr::null();
2188         }
2189     };
2190
2191     unsafe {
2192         llvm::LLVMSetCurrentDebugLocation(cx.builder.B, metadata_node);
2193     }
2194
2195     debug_context(cx).current_debug_location.set(debug_location);
2196 }
2197
2198 //=-------------------------------------------------------------------------------------------------
2199 //  Utility Functions
2200 //=-------------------------------------------------------------------------------------------------
2201
2202 fn cache_id_for_type(t: ty::t) -> uint {
2203     ty::type_id(t)
2204 }
2205
2206 // Used to avoid LLVM metadata uniquing problems. See `create_struct_stub()` and
2207 // `prepare_enum_metadata()`.
2208 fn generate_unique_type_id(prefix: &'static str) -> ~str {
2209     unsafe {
2210         static mut unique_id_counter: atomics::AtomicUint = atomics::INIT_ATOMIC_UINT;
2211         format!("{}{}", prefix, unique_id_counter.fetch_add(1, atomics::SeqCst))
2212     }
2213 }
2214
2215 /// Return codemap::Loc corresponding to the beginning of the span
2216 fn span_start(cx: &CrateContext, span: Span) -> codemap::Loc {
2217     cx.sess.codemap.lookup_char_pos(span.lo)
2218 }
2219
2220 fn size_and_align_of(cx: &CrateContext, llvm_type: Type) -> (u64, u64) {
2221     (machine::llsize_of_alloc(cx, llvm_type), machine::llalign_of_min(cx, llvm_type))
2222 }
2223
2224 fn bytes_to_bits(bytes: u64) -> c_ulonglong {
2225     (bytes * 8) as c_ulonglong
2226 }
2227
2228 #[inline]
2229 fn debug_context<'a>(cx: &'a CrateContext) -> &'a CrateDebugContext {
2230     let debug_context: &'a CrateDebugContext = cx.dbg_cx.get_ref();
2231     debug_context
2232 }
2233
2234 #[inline]
2235 fn DIB(cx: &CrateContext) -> DIBuilderRef {
2236     cx.dbg_cx.get_ref().builder
2237 }
2238
2239 fn fn_should_be_ignored(fcx: &FunctionContext) -> bool {
2240     match fcx.debug_context {
2241         FunctionDebugContext(_) => false,
2242         _ => true
2243     }
2244 }
2245
2246 fn assert_type_for_node_id(cx: &CrateContext, node_id: ast::NodeId, error_span: Span) {
2247     let node_types = cx.tcx.node_types.borrow();
2248     if !node_types.get().contains_key(&(node_id as uint)) {
2249         cx.sess.span_bug(error_span, "debuginfo: Could not find type for node id!");
2250     }
2251 }
2252
2253 fn get_namespace_and_span_for_item(cx: &CrateContext,
2254                                    def_id: ast::DefId,
2255                                    warning_span: Span)
2256                                 -> (DIScope, Span) {
2257     let containing_scope = namespace_for_item(cx, def_id, warning_span).scope;
2258     let definition_span = if def_id.crate == ast::LOCAL_CRATE {
2259         {
2260             let definition_span = match cx.tcx.items.find(def_id.node) {
2261                 Some(ast_map::NodeItem(item, _)) => item.span,
2262                 ref node => {
2263                     cx.sess.span_warn(warning_span,
2264                         format!("debuginfo::\
2265                                  get_namespace_and_span_for_item() \
2266                                  - Unexpected node type: {:?}", *node));
2267                     codemap::DUMMY_SP
2268                 }
2269             };
2270             definition_span
2271         }
2272     } else {
2273         // For external items there is no span information
2274         codemap::DUMMY_SP
2275     };
2276
2277     (containing_scope, definition_span)
2278 }
2279
2280 // This procedure builds the *scope map* for a given function, which maps any given ast::NodeId in
2281 // the function's AST to the correct DIScope metadata instance.
2282 //
2283 // This builder procedure walks the AST in execution order and keeps track of what belongs to which
2284 // scope, creating DIScope DIEs along the way, and introducing *artificial* lexical scope
2285 // descriptors where necessary. These artificial scopes allow GDB to correctly handle name
2286 // shadowing.
2287 fn populate_scope_map(cx: &CrateContext,
2288                       arg_pats: &[@ast::Pat],
2289                       fn_entry_block: &ast::Block,
2290                       fn_metadata: DISubprogram,
2291                       scope_map: &mut HashMap<ast::NodeId, DIScope>) {
2292     let def_map = cx.tcx.def_map;
2293
2294     struct ScopeStackEntry {
2295         scope_metadata: DIScope,
2296         ident: Option<ast::Ident>
2297     }
2298
2299     let mut scope_stack = ~[ScopeStackEntry { scope_metadata: fn_metadata, ident: None }];
2300
2301     // Push argument identifiers onto the stack so arguments integrate nicely with variable
2302     // shadowing.
2303     for &arg_pat in arg_pats.iter() {
2304         pat_util::pat_bindings(def_map, arg_pat, |_, _, _, path_ref| {
2305             let ident = ast_util::path_to_ident(path_ref);
2306             scope_stack.push(ScopeStackEntry { scope_metadata: fn_metadata, ident: Some(ident) });
2307         })
2308     }
2309
2310     // Clang creates a separate scope for function bodies, so let's do this too
2311     with_new_scope(cx,
2312                    fn_entry_block.span,
2313                    &mut scope_stack,
2314                    scope_map,
2315                    |cx, scope_stack, scope_map| {
2316         walk_block(cx, fn_entry_block, scope_stack, scope_map);
2317     });
2318
2319     // local helper functions for walking the AST.
2320     fn with_new_scope(cx: &CrateContext,
2321                       scope_span: Span,
2322                       scope_stack: &mut ~[ScopeStackEntry],
2323                       scope_map: &mut HashMap<ast::NodeId, DIScope>,
2324                       inner_walk: |&CrateContext,
2325                                    &mut ~[ScopeStackEntry],
2326                                    &mut HashMap<ast::NodeId, DIScope>|) {
2327         // Create a new lexical scope and push it onto the stack
2328         let loc = cx.sess.codemap.lookup_char_pos(scope_span.lo);
2329         let file_metadata = file_metadata(cx, loc.file.name);
2330         let parent_scope = scope_stack.last().unwrap().scope_metadata;
2331
2332         let scope_metadata = unsafe {
2333             llvm::LLVMDIBuilderCreateLexicalBlock(
2334                 DIB(cx),
2335                 parent_scope,
2336                 file_metadata,
2337                 loc.line as c_uint,
2338                 loc.col.to_uint() as c_uint)
2339         };
2340
2341         scope_stack.push(ScopeStackEntry { scope_metadata: scope_metadata, ident: None });
2342
2343         inner_walk(cx, scope_stack, scope_map);
2344
2345         // pop artificial scopes
2346         while scope_stack.last().unwrap().ident.is_some() {
2347             scope_stack.pop();
2348         }
2349
2350         if scope_stack.last().unwrap().scope_metadata != scope_metadata {
2351             cx.sess.span_bug(scope_span, "debuginfo: Inconsistency in scope management.");
2352         }
2353
2354         scope_stack.pop();
2355     }
2356
2357     fn walk_block(cx: &CrateContext,
2358                   block: &ast::Block,
2359                   scope_stack: &mut ~[ScopeStackEntry],
2360                   scope_map: &mut HashMap<ast::NodeId, DIScope>) {
2361         scope_map.insert(block.id, scope_stack.last().unwrap().scope_metadata);
2362
2363         // The interesting things here are statements and the concluding expression.
2364         for statement in block.stmts.iter() {
2365             scope_map.insert(ast_util::stmt_id(*statement),
2366                              scope_stack.last().unwrap().scope_metadata);
2367
2368             match statement.node {
2369                 ast::StmtDecl(decl, _) => walk_decl(cx, decl, scope_stack, scope_map),
2370                 ast::StmtExpr(exp, _) |
2371                 ast::StmtSemi(exp, _) => walk_expr(cx, exp, scope_stack, scope_map),
2372                 ast::StmtMac(..) => () // ignore macros (which should be expanded anyway)
2373             }
2374         }
2375
2376         for exp in block.expr.iter() {
2377             walk_expr(cx, *exp, scope_stack, scope_map);
2378         }
2379     }
2380
2381     fn walk_decl(cx: &CrateContext,
2382                  decl: &ast::Decl,
2383                  scope_stack: &mut ~[ScopeStackEntry],
2384                  scope_map: &mut HashMap<ast::NodeId, DIScope>) {
2385         match *decl {
2386             codemap::Spanned { node: ast::DeclLocal(local), .. } => {
2387                 scope_map.insert(local.id, scope_stack.last().unwrap().scope_metadata);
2388
2389                 walk_pattern(cx, local.pat, scope_stack, scope_map);
2390
2391                 for exp in local.init.iter() {
2392                     walk_expr(cx, *exp, scope_stack, scope_map);
2393                 }
2394             }
2395             _ => ()
2396         }
2397     }
2398
2399     fn walk_pattern(cx: &CrateContext,
2400                     pat: @ast::Pat,
2401                     scope_stack: &mut ~[ScopeStackEntry],
2402                     scope_map: &mut HashMap<ast::NodeId, DIScope>) {
2403
2404         let def_map = cx.tcx.def_map;
2405
2406         // Unfortunately, we cannot just use pat_util::pat_bindings() or ast_util::walk_pat() here
2407         // because we have to visit *all* nodes in order to put them into the scope map. The above
2408         // functions don't do that.
2409         match pat.node {
2410             ast::PatIdent(_, ref path_ref, ref sub_pat_opt) => {
2411
2412                 // Check if this is a binding. If so we need to put it on the scope stack and maybe
2413                 // introduce an articial scope
2414                 if pat_util::pat_is_binding(def_map, pat) {
2415
2416                     let ident = ast_util::path_to_ident(path_ref);
2417
2418                     // LLVM does not properly generate 'DW_AT_start_scope' fields for variable DIEs.
2419                     // For this reason we have to introduce an artificial scope at bindings whenever
2420                     // a variable with the same name is declared in *any* parent scope.
2421                     //
2422                     // Otherwise the following error occurs:
2423                     //
2424                     // let x = 10;
2425                     //
2426                     // do_something(); // 'gdb print x' correctly prints 10
2427                     //
2428                     // {
2429                     //     do_something(); // 'gdb print x' prints 0, because it already reads the
2430                     //                     // uninitialized 'x' from the next line...
2431                     //     let x = 100;
2432                     //     do_something(); // 'gdb print x' correctly prints 100
2433                     // }
2434
2435                     // Is there already a binding with that name?
2436                     // N.B.: this comparison must be UNhygienic... because
2437                     // gdb knows nothing about the context, so any two
2438                     // variables with the same name will cause the problem.
2439                     let need_new_scope = scope_stack
2440                         .iter()
2441                         .any(|entry| entry.ident.iter().any(|i| i.name == ident.name));
2442
2443                     if need_new_scope {
2444                         // Create a new lexical scope and push it onto the stack
2445                         let loc = cx.sess.codemap.lookup_char_pos(pat.span.lo);
2446                         let file_metadata = file_metadata(cx, loc.file.name);
2447                         let parent_scope = scope_stack.last().unwrap().scope_metadata;
2448
2449                         let scope_metadata = unsafe {
2450                             llvm::LLVMDIBuilderCreateLexicalBlock(
2451                                 DIB(cx),
2452                                 parent_scope,
2453                                 file_metadata,
2454                                 loc.line as c_uint,
2455                                 loc.col.to_uint() as c_uint)
2456                         };
2457
2458                         scope_stack.push(ScopeStackEntry {
2459                             scope_metadata: scope_metadata,
2460                             ident: Some(ident)
2461                         });
2462
2463                     } else {
2464                         // Push a new entry anyway so the name can be found
2465                         let prev_metadata = scope_stack.last().unwrap().scope_metadata;
2466                         scope_stack.push(ScopeStackEntry {
2467                             scope_metadata: prev_metadata,
2468                             ident: Some(ident)
2469                         });
2470                     }
2471                 }
2472
2473                 scope_map.insert(pat.id, scope_stack.last().unwrap().scope_metadata);
2474
2475                 for &sub_pat in sub_pat_opt.iter() {
2476                     walk_pattern(cx, sub_pat, scope_stack, scope_map);
2477                 }
2478             }
2479
2480             ast::PatWild | ast::PatWildMulti => {
2481                 scope_map.insert(pat.id, scope_stack.last().unwrap().scope_metadata);
2482             }
2483
2484             ast::PatEnum(_, ref sub_pats_opt) => {
2485                 scope_map.insert(pat.id, scope_stack.last().unwrap().scope_metadata);
2486
2487                 for ref sub_pats in sub_pats_opt.iter() {
2488                     for &p in sub_pats.iter() {
2489                         walk_pattern(cx, p, scope_stack, scope_map);
2490                     }
2491                 }
2492             }
2493
2494             ast::PatStruct(_, ref field_pats, _) => {
2495                 scope_map.insert(pat.id, scope_stack.last().unwrap().scope_metadata);
2496
2497                 for &ast::FieldPat { pat: sub_pat, .. } in field_pats.iter() {
2498                     walk_pattern(cx, sub_pat, scope_stack, scope_map);
2499                 }
2500             }
2501
2502             ast::PatTup(ref sub_pats) => {
2503                 scope_map.insert(pat.id, scope_stack.last().unwrap().scope_metadata);
2504
2505                 for &sub_pat in sub_pats.iter() {
2506                     walk_pattern(cx, sub_pat, scope_stack, scope_map);
2507                 }
2508             }
2509
2510             ast::PatUniq(sub_pat) | ast::PatRegion(sub_pat) => {
2511                 scope_map.insert(pat.id, scope_stack.last().unwrap().scope_metadata);
2512                 walk_pattern(cx, sub_pat, scope_stack, scope_map);
2513             }
2514
2515             ast::PatLit(exp) => {
2516                 scope_map.insert(pat.id, scope_stack.last().unwrap().scope_metadata);
2517                 walk_expr(cx, exp, scope_stack, scope_map);
2518             }
2519
2520             ast::PatRange(exp1, exp2) => {
2521                 scope_map.insert(pat.id, scope_stack.last().unwrap().scope_metadata);
2522                 walk_expr(cx, exp1, scope_stack, scope_map);
2523                 walk_expr(cx, exp2, scope_stack, scope_map);
2524             }
2525
2526             ast::PatVec(ref front_sub_pats, ref middle_sub_pats, ref back_sub_pats) => {
2527                 scope_map.insert(pat.id, scope_stack.last().unwrap().scope_metadata);
2528
2529                 for &sub_pat in front_sub_pats.iter() {
2530                     walk_pattern(cx, sub_pat, scope_stack, scope_map);
2531                 }
2532
2533                 for &sub_pat in middle_sub_pats.iter() {
2534                     walk_pattern(cx, sub_pat, scope_stack, scope_map);
2535                 }
2536
2537                 for &sub_pat in back_sub_pats.iter() {
2538                     walk_pattern(cx, sub_pat, scope_stack, scope_map);
2539                 }
2540             }
2541         }
2542     }
2543
2544     fn walk_expr(cx: &CrateContext,
2545                  exp: &ast::Expr,
2546                  scope_stack: &mut ~[ScopeStackEntry],
2547                  scope_map: &mut HashMap<ast::NodeId, DIScope>) {
2548
2549         scope_map.insert(exp.id, scope_stack.last().unwrap().scope_metadata);
2550
2551         match exp.node {
2552             ast::ExprLogLevel |
2553             ast::ExprLit(_)   |
2554             ast::ExprBreak(_) |
2555             ast::ExprAgain(_) |
2556             ast::ExprPath(_)  => {}
2557
2558             ast::ExprVstore(sub_exp, _)   |
2559             ast::ExprCast(sub_exp, _)     |
2560             ast::ExprAddrOf(_, sub_exp)  |
2561             ast::ExprField(sub_exp, _, _) |
2562             ast::ExprParen(sub_exp)       => walk_expr(cx, sub_exp, scope_stack, scope_map),
2563
2564             ast::ExprBox(place, sub_expr) => {
2565                 walk_expr(cx, place, scope_stack, scope_map);
2566                 walk_expr(cx, sub_expr, scope_stack, scope_map);
2567             }
2568
2569             ast::ExprRet(exp_opt) => match exp_opt {
2570                 Some(sub_exp) => walk_expr(cx, sub_exp, scope_stack, scope_map),
2571                 None => ()
2572             },
2573
2574             ast::ExprUnary(node_id, _, sub_exp) => {
2575                 scope_map.insert(node_id, scope_stack.last().unwrap().scope_metadata);
2576                 walk_expr(cx, sub_exp, scope_stack, scope_map);
2577             }
2578
2579             ast::ExprAssignOp(node_id, _, lhs, rhs) |
2580             ast::ExprIndex(node_id, lhs, rhs)        |
2581             ast::ExprBinary(node_id, _, lhs, rhs)    => {
2582                 scope_map.insert(node_id, scope_stack.last().unwrap().scope_metadata);
2583                 walk_expr(cx, lhs, scope_stack, scope_map);
2584                 walk_expr(cx, rhs, scope_stack, scope_map);
2585             }
2586
2587             ast::ExprVec(ref init_expressions, _) |
2588             ast::ExprTup(ref init_expressions)    => {
2589                 for ie in init_expressions.iter() {
2590                     walk_expr(cx, *ie, scope_stack, scope_map);
2591                 }
2592             }
2593
2594             ast::ExprAssign(sub_exp1, sub_exp2)    |
2595             ast::ExprRepeat(sub_exp1, sub_exp2, _) => {
2596                 walk_expr(cx, sub_exp1, scope_stack, scope_map);
2597                 walk_expr(cx, sub_exp2, scope_stack, scope_map);
2598             }
2599
2600             ast::ExprIf(cond_exp, then_block, ref opt_else_exp) => {
2601                 walk_expr(cx, cond_exp, scope_stack, scope_map);
2602
2603                 with_new_scope(cx,
2604                                then_block.span,
2605                                scope_stack,
2606                                scope_map,
2607                                |cx, scope_stack, scope_map| {
2608                     walk_block(cx, then_block, scope_stack, scope_map);
2609                 });
2610
2611                 match *opt_else_exp {
2612                     Some(else_exp) => walk_expr(cx, else_exp, scope_stack, scope_map),
2613                     _ => ()
2614                 }
2615             }
2616
2617             ast::ExprWhile(cond_exp, loop_body) => {
2618                 walk_expr(cx, cond_exp, scope_stack, scope_map);
2619
2620                 with_new_scope(cx,
2621                                loop_body.span,
2622                                scope_stack,
2623                                scope_map,
2624                                |cx, scope_stack, scope_map| {
2625                     walk_block(cx, loop_body, scope_stack, scope_map);
2626                 })
2627             }
2628
2629             ast::ExprForLoop(_, _, _, _) => {
2630                 cx.sess.span_bug(exp.span, "debuginfo::populate_scope_map() - \
2631                                             Found unexpanded for-loop.");
2632             }
2633
2634             ast::ExprMac(_) => {
2635                 cx.sess.span_bug(exp.span, "debuginfo::populate_scope_map() - \
2636                                             Found unexpanded macro.");
2637             }
2638
2639             ast::ExprLoop(block, _) |
2640             ast::ExprBlock(block)   => {
2641                 with_new_scope(cx,
2642                                block.span,
2643                                scope_stack,
2644                                scope_map,
2645                                |cx, scope_stack, scope_map| {
2646                     walk_block(cx, block, scope_stack, scope_map);
2647                 })
2648             }
2649
2650             ast::ExprFnBlock(decl, block) |
2651             ast::ExprProc(decl, block) => {
2652                 with_new_scope(cx,
2653                                block.span,
2654                                scope_stack,
2655                                scope_map,
2656                                |cx, scope_stack, scope_map| {
2657                     for &ast::Arg { pat: pattern, .. } in decl.inputs.iter() {
2658                         walk_pattern(cx, pattern, scope_stack, scope_map);
2659                     }
2660
2661                     walk_block(cx, block, scope_stack, scope_map);
2662                 })
2663             }
2664
2665             ast::ExprCall(fn_exp, ref args, _) => {
2666                 walk_expr(cx, fn_exp, scope_stack, scope_map);
2667
2668                 for arg_exp in args.iter() {
2669                     walk_expr(cx, *arg_exp, scope_stack, scope_map);
2670                 }
2671             }
2672
2673             ast::ExprMethodCall(node_id, _, _, ref args, _) => {
2674                 scope_map.insert(node_id, scope_stack.last().unwrap().scope_metadata);
2675
2676                 for arg_exp in args.iter() {
2677                     walk_expr(cx, *arg_exp, scope_stack, scope_map);
2678                 }
2679             }
2680
2681             ast::ExprMatch(discriminant_exp, ref arms) => {
2682                 walk_expr(cx, discriminant_exp, scope_stack, scope_map);
2683
2684                 // for each arm we have to first walk the pattern as these might introduce new
2685                 // artificial scopes. It should be sufficient to walk only one pattern per arm, as
2686                 // they all must contain the same binding names
2687
2688                 for arm_ref in arms.iter() {
2689                     let arm_span = arm_ref.pats[0].span;
2690
2691                     with_new_scope(cx,
2692                                    arm_span,
2693                                    scope_stack,
2694                                    scope_map,
2695                                    |cx, scope_stack, scope_map| {
2696                         for &pat in arm_ref.pats.iter() {
2697                             walk_pattern(cx, pat, scope_stack, scope_map);
2698                         }
2699
2700                         for guard_exp in arm_ref.guard.iter() {
2701                             walk_expr(cx, *guard_exp, scope_stack, scope_map)
2702                         }
2703
2704                         walk_block(cx, arm_ref.body, scope_stack, scope_map);
2705                     })
2706                 }
2707             }
2708
2709             ast::ExprStruct(_, ref fields, ref base_exp) => {
2710                 for &ast::Field { expr: exp, .. } in fields.iter() {
2711                     walk_expr(cx, exp, scope_stack, scope_map);
2712                 }
2713
2714                 match *base_exp {
2715                     Some(exp) => walk_expr(cx, exp, scope_stack, scope_map),
2716                     None => ()
2717                 }
2718             }
2719
2720             ast::ExprInlineAsm(ast::InlineAsm { inputs: ref inputs,
2721                                                 outputs: ref outputs,
2722                                                 .. }) => {
2723                 // inputs, outputs: ~[(~str, @expr)]
2724                 for &(_, exp) in inputs.iter() {
2725                     walk_expr(cx, exp, scope_stack, scope_map);
2726                 }
2727
2728                 for &(_, exp) in outputs.iter() {
2729                     walk_expr(cx, exp, scope_stack, scope_map);
2730                 }
2731             }
2732         }
2733     }
2734 }
2735
2736
2737 //=-------------------------------------------------------------------------------------------------
2738 // Namespace Handling
2739 //=-------------------------------------------------------------------------------------------------
2740
2741 struct NamespaceTreeNode {
2742     ident: ast::Ident,
2743     scope: DIScope,
2744     parent: Option<@NamespaceTreeNode>,
2745 }
2746
2747 impl NamespaceTreeNode {
2748     fn mangled_name_of_contained_item(&self, item_name: &str) -> ~str {
2749         let mut name = ~"_ZN";
2750         fill_nested(self, &mut name);
2751
2752         name.push_str(format!("{}{}", item_name.len(), item_name));
2753         name.push_char('E');
2754
2755         return name;
2756
2757         fn fill_nested(node: &NamespaceTreeNode, output: &mut ~str) {
2758             match node.parent {
2759                 Some(parent) => {
2760                     fill_nested(parent, output);
2761                 }
2762                 None => {}
2763             }
2764             let name = token::ident_to_str(&node.ident);
2765             output.push_str(format!("{}{}", name.len(), name));
2766         }
2767     }
2768 }
2769
2770 fn namespace_for_item(cx: &CrateContext,
2771                       def_id: ast::DefId,
2772                       warning_span: Span)
2773                    -> @NamespaceTreeNode {
2774     let namespace_path = {
2775         let mut item_path = ty::item_path(cx.tcx, def_id);
2776
2777         if (def_id.crate == ast::LOCAL_CRATE && item_path.len() < 1) ||
2778            (def_id.crate != ast::LOCAL_CRATE && item_path.len() < 2) {
2779             cx.sess.bug(format!("debuginfo::namespace_for_item() - Item path too short: {}",
2780                 ast_map::path_to_str(item_path, token::get_ident_interner())));
2781         }
2782
2783         // remove the name of the item
2784         item_path.pop();
2785
2786         if def_id.crate == ast::LOCAL_CRATE {
2787             // prepend crate name if not already present
2788             let crate_namespace_ident = token::str_to_ident(cx.link_meta.crateid.name);
2789             item_path.insert(0, ast_map::PathMod(crate_namespace_ident));
2790         }
2791
2792         item_path
2793     };
2794
2795     let mut current_key = vec::with_capacity(namespace_path.len());
2796     let mut parent_node: Option<@NamespaceTreeNode> = None;
2797     let last_index = namespace_path.len() - 1;
2798
2799     // Create/Lookup namespace for each element of the path.
2800     for (i, &path_element) in namespace_path.iter().enumerate() {
2801         let ident = path_element.ident();
2802         current_key.push(ident);
2803
2804         let existing_node = {
2805             let namespace_map = debug_context(cx).namespace_map.borrow();
2806             namespace_map.get().find_copy(&current_key)
2807         };
2808         let current_node = match existing_node {
2809             Some(existing_node) => existing_node,
2810             None => {
2811                 // create and insert
2812                 let parent_scope = match parent_node {
2813                     Some(node) => node.scope,
2814                     None => ptr::null()
2815                 };
2816                 let namespace_name = token::ident_to_str(&ident);
2817
2818                 let namespace_metadata = unsafe {
2819                     namespace_name.with_c_str(|namespace_name| {
2820                         llvm::LLVMDIBuilderCreateNameSpace(
2821                             DIB(cx),
2822                             parent_scope,
2823                             namespace_name,
2824                             ptr::null(), // cannot reconstruct file ...
2825                             0)           // ... or line information, but that's not so important.
2826                     })
2827                 };
2828
2829                 let node = @NamespaceTreeNode {
2830                     ident: ident,
2831                     scope: namespace_metadata,
2832                     parent: parent_node,
2833                 };
2834
2835                 {
2836                     let mut namespace_map = debug_context(cx).namespace_map
2837                                                              .borrow_mut();
2838                     namespace_map.get().insert(current_key.clone(), node);
2839                 }
2840
2841                 node
2842             }
2843         };
2844
2845         if i == last_index {
2846             return current_node;
2847         } else {
2848             parent_node = Some(current_node);
2849         }
2850     }
2851
2852     // Should be unreachable:
2853     let error_message = format!("debuginfo::namespace_for_item() - Code path should be \
2854                                  unreachable. namespace_path was {}",
2855                                  ast_map::path_to_str(namespace_path, token::get_ident_interner()));
2856     cx.sess.span_bug(warning_span, error_message);
2857 }