//! This crate provides a cross-platform library and binary for translating addresses into file
//! names and line numbers. Given an address in an executable or an offset in a section of a
//! relocatable object, it uses the debugging information to figure out which file name and line
//! number are associated with it.
//!
//! When used as a library, executables are loaded using `Mapping::new`, and users can the use
//! `Mapping::locate` to find the corresponding file path and line number. If the `Mapping` was
//! created with `with_functions`, `Mapping::locate` may also return information about the function
//! containing the given address. `addr2line` avoids re-executing work where it can so that looking
//! up multiple addresses for a single file does not require re-parsing the executable's debug
//! symbols. The library makes heavy use of [gimli](https://github.com/gimli-rs/gimli), which
//! provides zero-copy access to the DWARF debugging format used by most modern compilers.
//!
//! The initial implementation of the library is heavily influenced by the original `addr2line`
//! example in gimli, which was removed in
//! [5da3e19dd4cfae30b82053868ed7ab3fdd3cf026](https://github.com/gimli-rs/gimli/commit/5da3e19dd4cfae30b82053868ed7ab3fdd3cf026) in favor of this repository.
//!
//! This crate also provides a thing CLI wrapper around the library which provides some of the
//! functionality of the `addr2line` command line tool distributed with [GNU
//! binutils](https://www.gnu.org/software/binutils/). The executable or relocatable object to use
//! is specified with the -e option. The default is the file a.out.

#![deny(missing_docs)]

extern crate gimli;
extern crate memmap;
extern crate object;
extern crate owning_ref;
extern crate fallible_iterator;
#[macro_use]
extern crate error_chain;

use object::Object;
use owning_ref::OwningHandle;
use fallible_iterator::FallibleIterator;

use std::fmt;
use std::sync;
use std::path;
use std::error;
use std::borrow::Cow;

/// An error occured while traversing the debug symbols in the provided executable.
#[derive(Debug)]
pub enum DebugInfoError {
    /// DebugLine refers to a file that does not exist
    InvalidDebugLineTarget,
    /// A unit was completely empty (i.e., did not contain a compilation unit)
    MissingComplilationUnit,
    /// The first entry in a unit is not a compilation unit
    UnitWithoutCompilationUnit,
    /// A subroutine (unit offset, routine offset) has no name
    SubroutineMissingName(usize, usize),
    /// Abstract origin points to empty entry
    DanglingAbstractOrigin,
    /// Asked to parse non-contiguous range as contiguous.
    RangeBothContiguousAndNot,
    /// A range was inverted (high > low)
    RangeInverted,
}

impl fmt::Display for DebugInfoError {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match *self {
            DebugInfoError::InvalidDebugLineTarget => {
                write!(f, "DebugLine referst to a file that does not exist")
            }
            DebugInfoError::MissingComplilationUnit => {
                write!(f,
                       "A unit was completely empty (i.e., did not contain a compilation unit)")
            }
            DebugInfoError::UnitWithoutCompilationUnit => {
                write!(f, "The first entry in a unit is not a compilation unit")
            }
            DebugInfoError::SubroutineMissingName(u, r) => {
                write!(f, "A subroutine (<{:x}><{:x}>) has no name", u, r)
            }
            DebugInfoError::DanglingAbstractOrigin => {
                write!(f, "Abstract origin points to empty entry")
            }
            DebugInfoError::RangeBothContiguousAndNot => {
                write!(f, "Asked to parse non-contiguous range as contiguous.")
            }
            DebugInfoError::RangeInverted => write!(f, "A range was inverted (high > low)"),
        }
    }
}

impl error::Error for DebugInfoError {
    fn description(&self) -> &str {
        "An error occured while traversing debug symbols"
    }
}

mod errors {
    use gimli;
    use std::io;
    use super::DebugInfoError;

    error_chain! {
        foreign_links {
            Gimli(gimli::Error) #[doc="An error given by the `gimli` library while parsing the DWARF debug symbols."];
            BadPath(io::Error) #[doc="The path given could not be used to extract debug symbols."];
            InvalidDebugSymbols(DebugInfoError) #[doc="An error occured while traversing the debug symbols in the provided executable."];
        }

        errors {
            /// A necessary debug section is missing from the provided executable.
            MissingDebugSection(s: &'static str) {
                description("missing debug section")
                display("missing debug section: '.{}'", s)
            }
        }
    }
}
pub use errors::*;

/// A `Mapping` locates and maintains the state necessary to perform address to line translation.
///
/// Constructing a `Mapping` is somewhat costly, so users should aim to re-use created `Mapping`s
/// when performing lookups for many addresses over the same executable.
pub struct Mapping {
    // we use `OwningHandle` so that we can store both the Mmap and its associated object::File.
    // the lifetime of MmapDeriver here isn't *technically* static, it's *out* lifetime, but there
    // isn't a good way to express that as far as I am aware? suggestions welcome.
    inner: OwningHandle<Box<memmap::Mmap>, Box<MmapDerived<'static>>>,
}

/// `MmapDerived` uses an `OwningHandle` to allow an `object::File` and the data structures we
/// derive from it to be co-owned.
struct MmapDerived<'mmap> {
    inner: OwningHandle<Box<object::File<'mmap>>, Box<EndianDebugInfo<'mmap>>>,
}

enum EndianDebugInfo<'object> {
    LEInfo(DebugInfo<'object, gimli::LittleEndian>),
    BEInfo(DebugInfo<'object, gimli::BigEndian>),
}

/// `DebugInfo` holds the debug information derived from a wrapping `object::File`.
struct DebugInfo<'object, Endian>
    where Endian: gimli::Endianity
{
    debug_line: gimli::DebugLine<'object, Endian>,
    units: Vec<Unit<'object, Endian>>,
}

impl Mapping {
    /// Construct a new `Mapping` from the debug symbols in the given executable.
    ///
    /// The target file will be memmap'd, and then `gimli` is used to parse out the necessary debug
    /// symbols, without copying data when possible.
    ///
    /// The returned `Mapping` will also include debug information for functions, enabling
    /// `Mapping::locate()` to also indicate what function a given address appears in. This comes
    /// at some parsing and lookup cost.
    pub fn with_functions(file_path: &path::Path) -> Result<Mapping> {
        Self::new_inner(file_path, true)
    }

    /// Construct a new `Mapping` from the debug symbols in the given executable.
    ///
    /// The target file will be memmap'd, and then `gimli` is used to parse out the necessary debug
    /// symbols, without copying data when possible.
    ///
    /// Note that this constructor will *not* include function mapping information, and thus
    /// `Mapping::locate()` will always return `None` for the function mapping of addresses.
    pub fn new(file_path: &path::Path) -> Result<Mapping> {
        Self::new_inner(file_path, false)
    }

    fn new_inner(file_path: &path::Path, with_functions: bool) -> Result<Mapping> {
        let file = memmap::Mmap::open_path(file_path, memmap::Protection::Read)
            .map_err(|e| ErrorKind::BadPath(e))?;

        OwningHandle::try_new(Box::new(file), |mmap| -> Result<_> {
                let mmap: &memmap::Mmap = unsafe { &*mmap };
                let file = object::File::parse(unsafe { mmap.as_slice() });
                OwningHandle::try_new(Box::new(file), |file| -> Result<_> {
                        let file: &object::File = unsafe { &*file };
                        Self::symbolicate(file, with_functions)
                            .chain_err(|| "failed to analyze debug information")
                            .map(|di| Box::new(di))
                    })
                    .map(|di| Box::new(MmapDerived { inner: di }))
            })
            .map(|di| Mapping { inner: di })
    }

    /// Locate the source file and line corresponding to the given virtual memory address.
    ///
    /// If the `Mapping` was constructed with `with_functions`, information about the containing
    /// function may also be returned when available.
    pub fn locate(&self,
                  addr: u64)
                  -> Result<Option<(path::PathBuf, Option<u64>, Option<Cow<str>>)>> {
        self.inner.locate(addr)
    }

    fn symbolicate<'a>(file: &'a object::File,
                       with_functions: bool)
                       -> Result<EndianDebugInfo<'a>> {
        if file.is_little_endian() {
            Ok(EndianDebugInfo::LEInfo(DebugInfo::new(file, with_functions)?))
        } else {
            Ok(EndianDebugInfo::BEInfo(DebugInfo::new(file, with_functions)?))
        }
    }
}

impl<'object> EndianDebugInfo<'object> {
    fn locate(&self, addr: u64) -> Result<Option<(path::PathBuf, Option<u64>, Option<Cow<str>>)>> {
        match *self {
            EndianDebugInfo::LEInfo(ref dbg) => dbg.locate(addr),
            EndianDebugInfo::BEInfo(ref dbg) => dbg.locate(addr),
        }
    }
}

impl<'object, Endian> DebugInfo<'object, Endian>
    where Endian: gimli::Endianity
{
    fn new<'a>(file: &'a object::File, with_functions: bool) -> Result<DebugInfo<'a, Endian>> {
        let debug_info = file.get_section(".debug_info")
            .ok_or(ErrorKind::MissingDebugSection("debug_info"))?;
        let debug_info = gimli::DebugInfo::<Endian>::new(debug_info);
        let debug_abbrev = file.get_section(".debug_abbrev")
            .ok_or(ErrorKind::MissingDebugSection("debug_abbrev"))?;
        let debug_abbrev = gimli::DebugAbbrev::<Endian>::new(debug_abbrev);
        let debug_line = file.get_section(".debug_line")
            .ok_or(ErrorKind::MissingDebugSection("debug_line"))?;
        let debug_line = gimli::DebugLine::<Endian>::new(debug_line);
        let debug_ranges = file.get_section(".debug_ranges").unwrap_or(&[]);
        let debug_ranges = gimli::DebugRanges::<Endian>::new(debug_ranges);
        let debug_str = file.get_section(".debug_str").unwrap_or(&[]);
        let debug_str = gimli::DebugStr::<Endian>::new(debug_str);

        let mut units = Vec::new();
        let mut headers = debug_info.units();
        while let Some(header) = headers.next()
            .chain_err(|| "couldn't get DIE header")? {
            let unit = Unit::parse(&debug_abbrev,
                                   &debug_ranges,
                                   &debug_line,
                                   &debug_str,
                                   &header,
                                   with_functions);
            let unit = unit.chain_err(|| "encountered invalid compilation unit")?;
            if let Some(unit) = unit {
                units.push(unit);
            }
        }

        Ok(DebugInfo {
            debug_line: debug_line,
            units: units,
        })
    }

    pub fn locate(&self,
                  addr: u64)
                  -> Result<Option<(path::PathBuf, Option<u64>, Option<Cow<str>>)>> {
        // First, find the compilation unit for the given address
        for unit in &self.units {
            if !unit.contains_address(addr) {
                continue;
            }

            let mut rowi = 0;
            let mut current = None;

            // Okay, this is the right unit. Check our DebugLine rows.
            let rows = unit.cache_every
                .and_then(|cache_every| {
                    unit.skiplist.read().ok().and_then(|skiplist| {
                        match skiplist.binary_search_by_key(&addr, |&(raddr, _, _)| raddr) {
                            Ok(i) => {
                                // we have a state machine for this address!
                                current = Some(skiplist[i].2);
                                rowi = (i + 1) * cache_every + 1;
                                Some(skiplist[i].1.clone())
                            }
                            Err(i) if i == 0 => {
                                // i is the entry in the skiplist where addr *would* appear. Thus,
                                // we don't have a state machine for *this* address, but we do know
                                // that:
                                //
                                //  - if i == 0, we have no state machine, and must from scratch
                                //  - if i == skiplist.len(), we scan from the last state machine
                                //  - otherwise, the machine from i-1 eventually encounters addr
                                None
                            }
                            Err(i) => {
                                current = Some(skiplist[i - 1].2);
                                // NOTE
                                // we need to use i * cache_every here, not (i+1) as above.
                                // this is because i is the i *after* the one we're chooseing to
                                // start from (skiplist[i-1] above).
                                rowi = i * cache_every + 1;
                                Some(skiplist[i - 1].1.clone())
                            }
                        }
                    })
                });

            let mut rows = if let Some(rows) = rows {
                rows
            } else {
                // fall back to linear scan
                unit.line_rows(&self.debug_line)
                    .map_err(|e| Error::from(ErrorKind::Gimli(e)))
                    .chain_err(|| "cannot get line rows for unit")?
            };

            // Now, find the last row before a row with a higher address than the one we seek.
            let mut praddr = 0;
            let mut skipseq = false;
            while let Ok(Some((_, &row))) = rows.next_row() {
                if row.end_sequence() {
                    current = None;
                    skipseq = false;
                    continue;
                }

                if skipseq {
                    continue;
                }

                let raddr = row.address();
                if raddr < praddr {
                    // NOTE:
                    // We currently skip these sequences, but we *should* of course handle them
                    // correctly. It's unclear how the interplay between this and the skiplist
                    // should work.
                    // unimplemented!();
                    skipseq = true;
                    continue;
                }
                praddr = raddr;

                if raddr <= addr {
                    // Might be the right row, but we won't know until we see the next one.
                    // The .clone is needed so we can keep iterating
                    current = Some(row);

                    // Add every cache_every'th non-empty row to the skiplist
                    if let Some(cache_every) = unit.cache_every {
                        if rowi != 0 && rowi % cache_every == 0 {
                            if let Ok(mut skiplist) = unit.skiplist.write() {
                                let i = rowi / cache_every - 1;
                                if i >= skiplist.len() {
                                    debug_assert!(i == skiplist.len(),
                                                  "we somehow didn't cache a StateMachine for a \
                                                   previous iteration step!");
                                    // cache this StateMachine
                                    skiplist.push((row.address(), rows.clone(), row));
                                }
                            }
                        }
                    }
                    rowi += 1;
                    continue;
                }
                break;
            }

            // The row we just last iterated to is *after* the address, to the previous row we
            // saw (stored in current) is the one we want. If there is no current, then we have to
            // give up on locating the address in this unit (and thus in the program too).
            //
            // TODO
            // Can we return partial information here by giving, say, information from the
            // compilation unit itself?
            if current.is_none() {
                return Ok(None);
            }
            let row = current.unwrap();
            let header = rows.header();

            let file = row.file(header)
                .ok_or_else(|| {
                    ErrorKind::InvalidDebugSymbols(DebugInfoError::InvalidDebugLineTarget)
                })?;

            let mut path = path::PathBuf::new();
            if let Some(directory) = file.directory(header) {
                let directory = directory.to_string_lossy();
                if !directory.starts_with('/') {
                    if let Some(comp_dir) = unit.comp_dir() {
                        path.push(&*comp_dir.to_string_lossy());
                    }
                }
                path.push(&*directory);
            }
            path.push(&*file.path_name().to_string_lossy());

            let line = row.line();
            if unit.programs.is_empty() {
                return Ok(Some((path, line, None)));
            }

            // The unit also has programs, so let's look for the function wrapping this address.
            let mut func: Option<(&Program, &gimli::Range, u64)> = None;
            for p in &unit.programs {
                if !p.contains_address(addr) {
                    continue;
                }

                // This program covers the given address -- calculate how well it matches
                let (range, dist) = p.ranges
                    .iter()
                    .filter(|range| addr >= range.begin && addr < range.end)
                    .map(|range| (range, addr - range.begin))
                    .min_by_key(|&(_, dist)| dist)
                    .expect("p.contains_address() is true, but no matching range found");

                if let Some((prev, prange, pdist)) = func.take() {
                    // are we a better match?
                    func = if dist == pdist {
                        // we're equally good -- are we tighter?
                        if range.end <= prange.end {
                            // If range.end < prange.end, then we're a tighter match.
                            //
                            // Otherwise, we found two equally good ranges for this address.
                            // This probably happened because of a function like:
                            //
                            //   fn foo() { bar() }
                            //
                            // where bar() was inlined.
                            //
                            // Currently we just take the later one, which should be the
                            // "innermost" function (because we populated `programs` in DFS order),
                            // which is what we want. In the future, we may want to expose the full
                            // call chain in this case (and the others where there is a range
                            // conflcit).
                            Some((p, range, dist))
                        } else {
                            // no
                            Some((prev, prange, pdist))
                        }
                    } else if dist < pdist {
                        // we're just better
                        Some((p, range, dist))
                    } else {
                        // current is better
                        Some((prev, prange, pdist))
                    };
                } else {
                    func = Some((p, range, dist));
                }

                // Unfortunately, we're not done even if we've already found loc, because there
                // *may* be another subprogram (specifically, one that has been inlined) that
                // matches us better. We need to keep going until we find the best one.
            }

            return Ok(Some((path, line, func.map(|u| u.0.name.to_string_lossy()))));
        }
        Ok(None)
    }
}

// TODO: most of this should be moved to the main library.
use std::marker::PhantomData;
struct Unit<'input, Endian>
    where Endian: gimli::Endianity
{
    skiplist: sync::RwLock<Vec<(u64, gimli::StateMachine<'input, Endian>, gimli::LineNumberRow)>>,

    cache_every: Option<usize>,
    address_size: u8,
    ranges: Vec<gimli::Range>,
    line_offset: gimli::DebugLineOffset,
    comp_dir: Option<&'input std::ffi::CStr>,
    comp_name: Option<&'input std::ffi::CStr>,
    programs: Vec<Program<'input>>,
    phantom: PhantomData<Endian>,
}

impl<'input, Endian> Unit<'input, Endian>
    where Endian: gimli::Endianity
{
    fn parse(debug_abbrev: &gimli::DebugAbbrev<Endian>,
             debug_ranges: &gimli::DebugRanges<Endian>,
             debug_line: &gimli::DebugLine<'input, Endian>,
             debug_str: &gimli::DebugStr<'input, Endian>,
             header: &gimli::CompilationUnitHeader<'input, Endian>,
             with_functions: bool)
             -> Result<Option<Unit<'input, Endian>>> {

        // We first want to parse out the compilation unit, and then any contained subprograms.
        let abbrev = header.abbreviations(*debug_abbrev)
            .chain_err(|| "compilation unit refers to non-existing abbreviations")?;

        let mut entries = header.entries(&abbrev);
        let mut unit = {
            // Scoped so that we can continue using entries for the loop below
            let (_, entry) = entries.next_dfs()
                .chain_err(|| "compilation unit is broken")?
                .ok_or_else(|| {
                    ErrorKind::InvalidDebugSymbols(DebugInfoError::UnitWithoutCompilationUnit)
                })?;

            if entry.tag() != gimli::DW_TAG_compile_unit {
                return Err(ErrorKind::InvalidDebugSymbols(DebugInfoError::MissingComplilationUnit)
                    .into());
            }

            // Where does our compilation unit live?
            let ranges = Self::get_ranges(entry, debug_ranges, header.address_size())
                .chain_err(|| "compilation unit has invalid ranges")?;
            if ranges.is_empty() {
                return Ok(None);
            }

            // Extract source file and line information about the compilation unit
            let line_offset = match entry.attr_value(gimli::DW_AT_stmt_list) {
                Ok(Some(gimli::AttributeValue::DebugLineRef(offset))) => offset,
                Err(e) => {
                    return Err(Error::from(ErrorKind::Gimli(e)))
                        .chain_err(|| "invalid compilation unit statement list")
                }
                _ => return Ok(None),
            };
            let comp_dir = entry.attr(gimli::DW_AT_comp_dir)
                .map_err(|e| Error::from(ErrorKind::Gimli(e)))
                .chain_err(|| "invalid compilation unit directory")?
                .and_then(|attr| attr.string_value(debug_str));
            let comp_name = entry.attr(gimli::DW_AT_name)
                .map_err(|e| Error::from(ErrorKind::Gimli(e)))
                .chain_err(|| "invalid compilation unit name")?
                .and_then(|attr| attr.string_value(debug_str));

            let lineh = debug_line.header(line_offset, header.address_size(), comp_dir, comp_name)
                .chain_err(|| "invalid compilation unit line rows")?;

            // We want to cache every sqrt(#rows).
            // Unfortunately we don't know the number of rows (and we don't want to scan all of
            // line rows to find it). However, we *do* know the number of bytes of debug line
            // information, which we can use as a proxy.
            //
            // Based on some empirical data from a couple of applications, the relationship seems
            // to be about 5.5 bytes/row for units with a decent number of rows. The values
            // vary more for smaller units, but there cache_every also matters less.
            let nrows = lineh.raw_program_buf().len() as f64 / 5.5;
            // If a unit only has a very small number of rows, we can avoid the skiplist
            // altogether (also, our estimate is more likely to be wrong).
            let cache_every = if nrows >= 100.0 {
                Some(nrows.sqrt() as usize)
            } else {
                None
            };

            Unit {
                skiplist: sync::RwLock::default(),
                cache_every: cache_every,

                address_size: header.address_size(),
                ranges: ranges,
                line_offset: line_offset,
                comp_dir: comp_dir,
                comp_name: comp_name,
                programs: vec![],
                phantom: PhantomData,
            }
        };

        // Do we also need to extract function information?
        if !with_functions {
            return Ok(Some(unit));
        }

        while let Some((_, entry)) = entries.next_dfs()
            .chain_err(|| "tree below compilation unit yielded invalid entry")? {

            // We only care about functions
            match entry.tag() {
                gimli::DW_TAG_inlined_subroutine |
                gimli::DW_TAG_subprogram => (),
                _ => continue,
            }

            // Where does this function live?
            let ranges = Self::get_ranges(entry, debug_ranges, header.address_size())
                .chain_err(|| "subroutine has invalid ranges")?;
            if ranges.is_empty() {
                continue;
            }

            if cfg!(debug_assertions) {
                // All programs should be fully contained within their compilation unit
                for r in &ranges {
                    assert!(unit.ranges
                        .iter()
                        .any(|range| range.begin <= r.begin && range.end >= r.end));
                }
            }

            let maybe_name = Self::resolve_name(entry, header, debug_str, &abbrev).chain_err(|| {
                    format!("failed to resolve name for subroutine at <{:x}><{:x}>",
                            header.offset().0,
                            entry.offset().0)
                })?;

            let name = maybe_name.ok_or_else(|| {
                    ErrorKind::InvalidDebugSymbols(DebugInfoError::SubroutineMissingName(header.offset().0, entry.offset().0))
                })?;

            unit.programs.push(Program {
                ranges: ranges,
                inlined: entry.tag() == gimli::DW_TAG_inlined_subroutine,
                name: name,
            });
        }

        Ok(Some(unit))
    }

    fn resolve_name<'a, 'b>(entry: &gimli::DebuggingInformationEntry<'input, 'a, 'b, Endian>,
                            header: &gimli::CompilationUnitHeader<'input, Endian>,
                            debug_str: &gimli::DebugStr<'input, Endian>,
                            abbrev: &gimli::Abbreviations)
                            -> Result<Option<&'input std::ffi::CStr>> {

        // For naming, we prefer the linked name, if available
        if let Some(name) = entry.attr(gimli::DW_AT_linkage_name)
            .map_err(|e| Error::from(ErrorKind::Gimli(e)))
            .chain_err(|| "invalid subprogram linkage name")?
            .and_then(|attr| attr.string_value(debug_str)) {
            return Ok(Some(name));
        }

        // Linked name is not available, so fall back to just plain old name, if that's available.
        if let Some(name) = entry.attr(gimli::DW_AT_name)
            .map_err(|e| Error::from(ErrorKind::Gimli(e)))
            .chain_err(|| "invalid subprogram name")?
            .and_then(|attr| attr.string_value(debug_str)) {
            return Ok(Some(name));
        }

        // If we don't have the link name, check if this function refers to another
        if let Some(gimli::AttributeValue::UnitRef(origin)) =
            entry.attr_value(gimli::DW_AT_abstract_origin)
                .map_err(|e| Error::from(ErrorKind::Gimli(e)))
                .chain_err(|| "invalid subprogram abstract origin")? {
            let mut entries = header.entries_at_offset(abbrev, origin)
                .chain_err(|| "illegal offset in abstract origin")?;
            let (_, parent) = entries.next_dfs()
                .chain_err(|| "abstract origin does not point to a valid entry")?
                .ok_or_else(|| {
                    ErrorKind::InvalidDebugSymbols(DebugInfoError::DanglingAbstractOrigin)
                })?;

            let name = Self::resolve_name(parent, header, debug_str, abbrev)
                .chain_err(|| "abstract origin does not resolve to a name")?;
            return Ok(name);
        }

        Ok(None)
    }

    fn get_ranges(entry: &gimli::DebuggingInformationEntry<Endian>,
                  debug_ranges: &gimli::DebugRanges<Endian>,
                  address_size: u8)
                  -> Result<Vec<gimli::Range>> {
        if let Some(range) = Self::parse_noncontiguous_ranges(entry, debug_ranges, address_size)? {
            return Ok(range);
        }
        if let Some(range) = Self::parse_contiguous_range(entry)?.map(|range| vec![range]) {
            return Ok(range);
        }
        return Ok(vec![]);
    }

    // This must be checked before `parse_contiguous_range`.
    fn parse_noncontiguous_ranges(entry: &gimli::DebuggingInformationEntry<Endian>,
                                  debug_ranges: &gimli::DebugRanges<Endian>,
                                  address_size: u8)
                                  -> Result<Option<Vec<gimli::Range>>> {
        let offset = match entry.attr_value(gimli::DW_AT_ranges) {
            Ok(Some(gimli::AttributeValue::DebugRangesRef(offset))) => offset,
            Err(e) => {
                return Err(Error::from(ErrorKind::Gimli(e)))
                    .chain_err(|| "invalid ranges attribute")
            }
            _ => return Ok(None),
        };
        let base_address = match entry.attr_value(gimli::DW_AT_low_pc) {
            Ok(Some(gimli::AttributeValue::Addr(addr))) => addr,
            Err(e) => {
                return Err(Error::from(ErrorKind::Gimli(e)))
                    .chain_err(|| "invalid low_pc attribute")
            }
            _ => 0,
        };

        let ranges = debug_ranges.ranges(offset, address_size, base_address)
            .chain_err(|| "range offsets are not valid")?;
        let ranges = ranges.collect().chain_err(|| "range could not be parsed")?;
        Ok(Some(ranges))
    }

    fn parse_contiguous_range(entry: &gimli::DebuggingInformationEntry<Endian>)
                              -> Result<Option<gimli::Range>> {

        if let Ok(Some(..)) = entry.attr_value(gimli::DW_AT_ranges) {
            return Err(ErrorKind::InvalidDebugSymbols(DebugInfoError::RangeBothContiguousAndNot)
                .into());
        }

        let low_pc = match entry.attr_value(gimli::DW_AT_low_pc) {
            Ok(Some(gimli::AttributeValue::Addr(addr))) => addr,
            Err(e) => {
                return Err(Error::from(ErrorKind::Gimli(e)))
                    .chain_err(|| "invalid low_pc attribute")
            }
            _ => return Ok(None),
        };

        let high_pc = match entry.attr_value(gimli::DW_AT_high_pc) {
            Ok(Some(gimli::AttributeValue::Addr(addr))) => addr,
            Ok(Some(gimli::AttributeValue::Udata(size))) => low_pc.wrapping_add(size),
            Err(e) => {
                return Err(Error::from(ErrorKind::Gimli(e)))
                    .chain_err(|| "invalid high_pc attribute")
            }
            Ok(None) => low_pc.wrapping_add(1),
            _ => return Ok(None),
        };

        if low_pc == 0 {
            // https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;a=blob;f=gdb/dwarf2read.c;h=ed10e03812f381ccdb5c51e1c689df8d61ab87f6;hb=HEAD#l16000
            // TODO: *technically* there could be a relocatable section placed at VA 0
            return Ok(None);
        }

        if low_pc == high_pc {
            // https://sourceware.org/ml/gdb-patches/2011-03/msg00739.html
            return Ok(None);
        }

        if low_pc > high_pc {
            return Err(ErrorKind::InvalidDebugSymbols(DebugInfoError::RangeInverted).into());
        }

        Ok(Some(gimli::Range {
            begin: low_pc,
            end: high_pc,
        }))
    }

    fn contains_address(&self, address: u64) -> bool {
        self.ranges.iter().any(|range| address >= range.begin && address < range.end)
    }

    fn line_rows(&self,
                 debug_line: &gimli::DebugLine<'input, Endian>)
                 -> gimli::Result<gimli::StateMachine<'input, Endian>> {
        debug_line.header(self.line_offset,
                    self.address_size,
                    self.comp_dir,
                    self.comp_name)
            .map(|h| h.rows())
    }

    fn comp_dir(&self) -> Option<&std::ffi::CStr> {
        self.comp_dir
    }
}

struct Program<'input> {
    ranges: Vec<gimli::Range>,
    name: &'input std::ffi::CStr,
    #[allow(dead_code)]
    inlined: bool,
}

impl<'input> Program<'input> {
    fn contains_address(&self, address: u64) -> bool {
        self.ranges.iter().any(|range| address >= range.begin && address < range.end)
    }
}

// https://github.com/Kimundi/owning-ref-rs/issues/18
use std::ops::Deref;
impl<'mmap> Deref for MmapDerived<'mmap> {
    type Target = EndianDebugInfo<'mmap>;
    fn deref(&self) -> &Self::Target {
        &*self.inner
    }
}
