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