src/librustc/middle/trans/debuginfo.rs

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