backward.hpp

/*
 * backward.hpp
 * Copyright 2013 Google Inc. All Rights Reserved.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

#ifndef H_6B9572DA_A64B_49E6_B234_051480991C89
#define H_6B9572DA_A64B_49E6_B234_051480991C89

#ifndef __cplusplus
#	error "It's not going to compile without a C++ compiler..."
#endif

#if	  defined(BACKWARD_CXX11)
#elif defined(BACKWARD_CXX98)
#else
#	if __cplusplus >= 201103L
#		define BACKWARD_CXX11
#		define BACKWARD_ATLEAST_CXX11
#		define BACKWARD_ATLEAST_CXX98
#	else
#		define BACKWARD_CXX98
#		define BACKWARD_ATLEAST_CXX98
#	endif
#endif

// You can define one of the following (or leave it to the auto-detection):
//
// #define BACKWARD_SYSTEM_LINUX
//	- specialization for linux
//
// #define BACKWARD_SYSTEM_DARWIN
//	- specialization for Mac OS X 10.5 and later.
//
// #define BACKWARD_SYSTEM_UNKNOWN
//	- placebo implementation, does nothing.
//
#if   defined(BACKWARD_SYSTEM_LINUX)
#elif defined(BACKWARD_SYSTEM_DARWIN)
#elif defined(BACKWARD_SYSTEM_UNKNOWN)
#else
#	if defined(__linux) || defined(__linux__)
#		define BACKWARD_SYSTEM_LINUX
#	elif defined(__APPLE__)
#		define BACKWARD_SYSTEM_DARWIN
#	else
#		define BACKWARD_SYSTEM_UNKNOWN
#	endif
#endif

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <new>
#include <sstream>
#include <streambuf>
#include <string>
#include <vector>
#include <limits>

#if defined(BACKWARD_SYSTEM_LINUX)

// On linux, backtrace can back-trace or "walk" the stack using the following
// libraries:
//
// #define BACKWARD_HAS_UNWIND 1
//  - unwind comes from libgcc, but I saw an equivalent inside clang itself.
//  - with unwind, the stacktrace is as accurate as it can possibly be, since
//  this is used by the C++ runtine in gcc/clang for stack unwinding on
//  exception.
//  - normally libgcc is already linked to your program by default.
//
// #define BACKWARD_HAS_BACKTRACE == 1
//  - backtrace seems to be a little bit more portable than libunwind, but on
//  linux, it uses unwind anyway, but abstract away a tiny information that is
//  sadly really important in order to get perfectly accurate stack traces.
//  - backtrace is part of the (e)glib library.
//
// The default is:
// #define BACKWARD_HAS_UNWIND == 1
//
// Note that only one of the define should be set to 1 at a time.
//
#	if   BACKWARD_HAS_UNWIND == 1
#	elif BACKWARD_HAS_BACKTRACE == 1
#	else
#		undef  BACKWARD_HAS_UNWIND
#		define BACKWARD_HAS_UNWIND 1
#		undef  BACKWARD_HAS_BACKTRACE
#		define BACKWARD_HAS_BACKTRACE 0
#	endif

// On linux, backward can extract detailed information about a stack trace
// using one of the following libraries:
//
// #define BACKWARD_HAS_DW 1
//  - libdw gives you the most juicy details out of your stack traces:
//    - object filename
//    - function name
//    - source filename
//	  - line and column numbers
//	  - source code snippet (assuming the file is accessible)
//	  - variables name and values (if not optimized out)
//  - You need to link with the lib "dw":
//    - apt-get install libdw-dev
//    - g++/clang++ -ldw ...
//
// #define BACKWARD_HAS_BFD 1
//  - With libbfd, you get a fair amount of details:
//    - object filename
//    - function name
//    - source filename
//	  - line numbers
//	  - source code snippet (assuming the file is accessible)
//  - You need to link with the lib "bfd":
//    - apt-get install binutils-dev
//    - g++/clang++ -lbfd ...
//
// #define BACKWARD_HAS_DWARF 1
//  - libdwarf gives you the most juicy details out of your stack traces:
//    - object filename
//    - function name
//    - source filename
//    - line and column numbers
//    - source code snippet (assuming the file is accessible)
//    - variables name and values (if not optimized out)
//  - You need to link with the lib "dwarf":
//    - apt-get install libdwarf-dev
//    - g++/clang++ -ldwarf ...
//
// #define BACKWARD_HAS_BACKTRACE_SYMBOL 1
//  - backtrace provides minimal details for a stack trace:
//    - object filename
//    - function name
//  - backtrace is part of the (e)glib library.
//
// The default is:
// #define BACKWARD_HAS_BACKTRACE_SYMBOL == 1
//
// Note that only one of the define should be set to 1 at a time.
//
#	if   BACKWARD_HAS_DW == 1
#	elif BACKWARD_HAS_BFD == 1
#   elif BACKWARD_HAS_DWARF == 1
#	elif BACKWARD_HAS_BACKTRACE_SYMBOL == 1
#	else
#		undef  BACKWARD_HAS_DW
#		define BACKWARD_HAS_DW 0
#		undef  BACKWARD_HAS_BFD
#		define BACKWARD_HAS_BFD 0
#		undef  BACKWARD_HAS_DWARF
#		define BACKWARD_HAS_DWARF 0
#		undef  BACKWARD_HAS_BACKTRACE_SYMBOL
#		define BACKWARD_HAS_BACKTRACE_SYMBOL 1
#	endif

#	include <cxxabi.h>
#	include <fcntl.h>
#	ifdef __ANDROID__
//		Old Android API levels define _Unwind_Ptr in both link.h and unwind.h
//		Rename the one in link.h as we are not going to be using it
#		define _Unwind_Ptr _Unwind_Ptr_Custom
#	include <link.h>
#		undef _Unwind_Ptr
#	else
#	    include <link.h>
#	endif
#	include <sys/stat.h>
#	include <syscall.h>
#	include <unistd.h>
#	include <signal.h>

#	if BACKWARD_HAS_BFD == 1
//              NOTE: defining PACKAGE{,_VERSION} is required before including
//                    bfd.h on some platforms, see also:
//                    https://sourceware.org/bugzilla/show_bug.cgi?id=14243
#               ifndef PACKAGE
#                       define PACKAGE
#               endif
#               ifndef PACKAGE_VERSION
#                       define PACKAGE_VERSION
#               endif
#		include <bfd.h>
#		ifndef _GNU_SOURCE
#			define _GNU_SOURCE
#			include <dlfcn.h>
#			undef _GNU_SOURCE
#		else
#			include <dlfcn.h>
#		endif
#	endif

#	if BACKWARD_HAS_DW == 1
#		include <elfutils/libdw.h>
#		include <elfutils/libdwfl.h>
#		include <dwarf.h>
#	endif

#	if BACKWARD_HAS_DWARF == 1
#		include <libelf.h>
#		include <dwarf.h>
#		include <libdwarf.h>
#		include <map>
#		include <algorithm>
#		ifndef _GNU_SOURCE
#			define _GNU_SOURCE
#			include <dlfcn.h>
#			undef _GNU_SOURCE
#		else
#			include <dlfcn.h>
#		endif
#	endif

#	if (BACKWARD_HAS_BACKTRACE == 1) || (BACKWARD_HAS_BACKTRACE_SYMBOL == 1)
		// then we shall rely on backtrace
#		include <execinfo.h>
#	endif

#endif // defined(BACKWARD_SYSTEM_LINUX)

#if defined(BACKWARD_SYSTEM_DARWIN)
// On Darwin, backtrace can back-trace or "walk" the stack using the following
// libraries:
//
// #define BACKWARD_HAS_UNWIND 1
//  - unwind comes from libgcc, but I saw an equivalent inside clang itself.
//  - with unwind, the stacktrace is as accurate as it can possibly be, since
//  this is used by the C++ runtine in gcc/clang for stack unwinding on
//  exception.
//  - normally libgcc is already linked to your program by default.
//
// #define BACKWARD_HAS_BACKTRACE == 1
//  - backtrace is available by default, though it does not produce as much information
//  as another library might.
//
// The default is:
// #define BACKWARD_HAS_UNWIND == 1
//
// Note that only one of the define should be set to 1 at a time.
//
#	if   BACKWARD_HAS_UNWIND == 1
#	elif BACKWARD_HAS_BACKTRACE == 1
#	else
#		undef  BACKWARD_HAS_UNWIND
#		define BACKWARD_HAS_UNWIND 1
#		undef  BACKWARD_HAS_BACKTRACE
#		define BACKWARD_HAS_BACKTRACE 0
#	endif

// On Darwin, backward can extract detailed information about a stack trace
// using one of the following libraries:
//
// #define BACKWARD_HAS_BACKTRACE_SYMBOL 1
//  - backtrace provides minimal details for a stack trace:
//    - object filename
//    - function name
//
// The default is:
// #define BACKWARD_HAS_BACKTRACE_SYMBOL == 1
//
#	if BACKWARD_HAS_BACKTRACE_SYMBOL == 1
#	else
#		undef  BACKWARD_HAS_BACKTRACE_SYMBOL
#		define BACKWARD_HAS_BACKTRACE_SYMBOL 1
#	endif

#	include <cxxabi.h>
#	include <fcntl.h>
#	include <pthread.h>
#	include <sys/stat.h>
#	include <unistd.h>
#	include <signal.h>

#	if (BACKWARD_HAS_BACKTRACE == 1) || (BACKWARD_HAS_BACKTRACE_SYMBOL == 1)
#		include <execinfo.h>
#	endif
#endif // defined(BACKWARD_SYSTEM_DARWIN)

#if BACKWARD_HAS_UNWIND == 1

#	include <unwind.h>
// while gcc's unwind.h defines something like that:
//  extern _Unwind_Ptr _Unwind_GetIP (struct _Unwind_Context *);
//  extern _Unwind_Ptr _Unwind_GetIPInfo (struct _Unwind_Context *, int *);
//
// clang's unwind.h defines something like this:
//  uintptr_t _Unwind_GetIP(struct _Unwind_Context* __context);
//
// Even if the _Unwind_GetIPInfo can be linked to, it is not declared, worse we
// cannot just redeclare it because clang's unwind.h doesn't define _Unwind_Ptr
// anyway.
//
// Luckily we can play on the fact that the guard macros have a different name:
#ifdef __CLANG_UNWIND_H
// In fact, this function still comes from libgcc (on my different linux boxes,
// clang links against libgcc).
#	include <inttypes.h>
extern "C" uintptr_t _Unwind_GetIPInfo(_Unwind_Context*, int*);
#endif

#endif // BACKWARD_HAS_UNWIND == 1

#ifdef BACKWARD_ATLEAST_CXX11
#	include <unordered_map>
#	include <utility> // for std::swap
	namespace backward {
	namespace details {
		template <typename K, typename V>
		struct hashtable {
			typedef std::unordered_map<K, V> type;
		};
		using std::move;
	} // namespace details
	} // namespace backward
#else // NOT BACKWARD_ATLEAST_CXX11
#	define nullptr NULL
#	define override
#	include <map>
	namespace backward {
	namespace details {
		template <typename K, typename V>
		struct hashtable {
			typedef std::map<K, V> type;
		};
		template <typename T>
			const T& move(const T& v) { return v; }
		template <typename T>
			T& move(T& v) { return v; }
	} // namespace details
	} // namespace backward
#endif // BACKWARD_ATLEAST_CXX11

namespace backward {

namespace system_tag {
	struct linux_tag; // seems that I cannot call that "linux" because the name
	// is already defined... so I am adding _tag everywhere.
	struct darwin_tag;
	struct unknown_tag;

#if   defined(BACKWARD_SYSTEM_LINUX)
	typedef linux_tag current_tag;
#elif defined(BACKWARD_SYSTEM_DARWIN)
	typedef darwin_tag current_tag;
#elif defined(BACKWARD_SYSTEM_UNKNOWN)
	typedef unknown_tag current_tag;
#else
#	error "May I please get my system defines?"
#endif
} // namespace system_tag


namespace trace_resolver_tag {
#if defined(BACKWARD_SYSTEM_LINUX)
	struct libdw;
	struct libbfd;
	struct libdwarf;
	struct backtrace_symbol;

#	if   BACKWARD_HAS_DW == 1
		typedef libdw current;
#	elif BACKWARD_HAS_BFD == 1
		typedef libbfd current;
#	elif BACKWARD_HAS_DWARF == 1
		typedef libdwarf current;
#	elif BACKWARD_HAS_BACKTRACE_SYMBOL == 1
		typedef backtrace_symbol current;
#	else
#		error "You shall not pass, until you know what you want."
#	endif
#elif defined(BACKWARD_SYSTEM_DARWIN)
	struct backtrace_symbol;

#	if BACKWARD_HAS_BACKTRACE_SYMBOL == 1
		typedef backtrace_symbol current;
#	else
#		error "You shall not pass, until you know what you want."
#	endif
#endif
} // namespace trace_resolver_tag


namespace details {

template <typename T>
	struct rm_ptr { typedef T type; };

template <typename T>
	struct rm_ptr<T*> { typedef T type; };

template <typename T>
	struct rm_ptr<const T*> { typedef const T type; };

template <typename R, typename T, R (*F)(T)>
struct deleter {
	template <typename U>
		void operator()(U& ptr) const {
			(*F)(ptr);
		}
};

template <typename T>
struct default_delete {
	void operator()(T& ptr) const {
		delete ptr;
	}
};

template <typename T, typename Deleter = deleter<void, void*, &::free> >
class handle {
	struct dummy;
	T    _val;
	bool _empty;

#ifdef BACKWARD_ATLEAST_CXX11
	handle(const handle&) = delete;
	handle& operator=(const handle&) = delete;
#endif

public:
	~handle() {
		if (!_empty) {
			Deleter()(_val);
		}
	}

	explicit handle(): _val(), _empty(true) {}
	explicit handle(T val): _val(val), _empty(false) { if(!_val) _empty = true; }

#ifdef BACKWARD_ATLEAST_CXX11
	handle(handle&& from): _empty(true) {
		swap(from);
	}
	handle& operator=(handle&& from) {
		swap(from); return *this;
	}
#else
	explicit handle(const handle& from): _empty(true) {
		// some sort of poor man's move semantic.
		swap(const_cast<handle&>(from));
	}
	handle& operator=(const handle& from) {
		// some sort of poor man's move semantic.
		swap(const_cast<handle&>(from)); return *this;
	}
#endif

	void reset(T new_val) {
		handle tmp(new_val);
		swap(tmp);
	}
	operator const dummy*() const {
		if (_empty) {
			return nullptr;
		}
		return reinterpret_cast<const dummy*>(_val);
	}
	T get() {
		return _val;
	}
	T release() {
		_empty = true;
		return _val;
	}
	void swap(handle& b) {
		using std::swap;
		swap(b._val, _val); // can throw, we are safe here.
		swap(b._empty, _empty); // should not throw: if you cannot swap two
		// bools without throwing... It's a lost cause anyway!
	}

	T operator->() { return _val; }
	const T operator->() const { return _val; }

	typedef typename rm_ptr<T>::type& ref_t;
	typedef const typename rm_ptr<T>::type& const_ref_t;
	ref_t operator*() { return *_val; }
	const_ref_t operator*() const { return *_val; }
	ref_t operator[](size_t idx) { return _val[idx]; }

	// Watch out, we've got a badass over here
	T* operator&() {
		_empty = false;
		return &_val;
	}
};

// Default demangler implementation (do nothing).
template <typename TAG>
struct demangler_impl {
	static std::string demangle(const char* funcname) {
		return funcname;
	}
};

#if defined(BACKWARD_SYSTEM_LINUX) || defined(BACKWARD_SYSTEM_DARWIN)

template <>
struct demangler_impl<system_tag::current_tag> {
	demangler_impl(): _demangle_buffer_length(0) {}

	std::string demangle(const char* funcname) {
		using namespace details;
		char* result = abi::__cxa_demangle(funcname,
			_demangle_buffer.release(), &_demangle_buffer_length, nullptr);
		if(result) {
			_demangle_buffer.reset(result);
			return result;
		}
		return funcname;
	}

private:
	details::handle<char*> _demangle_buffer;
	size_t                 _demangle_buffer_length;
};

#endif // BACKWARD_SYSTEM_LINUX || BACKWARD_SYSTEM_DARWIN

struct demangler:
	public demangler_impl<system_tag::current_tag> {};

} // namespace details

/*************** A TRACE ***************/

struct Trace {
	void*    addr;
	size_t   idx;

	Trace():
		addr(nullptr), idx(0) {}

	explicit Trace(void* _addr, size_t _idx):
		addr(_addr), idx(_idx) {}
};

struct ResolvedTrace: public Trace {

	struct SourceLoc {
		std::string function;
		std::string filename;
		unsigned    line;
		unsigned    col;

		SourceLoc(): line(0), col(0) {}

		bool operator==(const SourceLoc& b) const {
			return function == b.function
				&& filename == b.filename
				&& line == b.line
				&& col == b.col;
		}

		bool operator!=(const SourceLoc& b) const {
			return !(*this == b);
		}
	};

	// In which binary object this trace is located.
	std::string                    object_filename;

	// The function in the object that contain the trace. This is not the same
	// as source.function which can be an function inlined in object_function.
	std::string                    object_function;

	// The source location of this trace. It is possible for filename to be
	// empty and for line/col to be invalid (value 0) if this information
	// couldn't be deduced, for example if there is no debug information in the
	// binary object.
	SourceLoc                      source;

	// An optionals list of "inliners". All the successive sources location
	// from where the source location of the trace (the attribute right above)
	// is inlined. It is especially useful when you compiled with optimization.
	typedef std::vector<SourceLoc> source_locs_t;
	source_locs_t                  inliners;

	ResolvedTrace():
		Trace() {}
	ResolvedTrace(const Trace& mini_trace):
		Trace(mini_trace) {}
};

/*************** STACK TRACE ***************/

// default implemention.
template <typename TAG>
class StackTraceImpl {
public:
	size_t size() const { return 0; }
	Trace operator[](size_t) { return Trace(); }
	size_t load_here(size_t=0) { return 0; }
	size_t load_from(void*, size_t=0) { return 0; }
	size_t thread_id() const { return 0; }
	void skip_n_firsts(size_t) { }
};

class StackTraceImplBase {
public:
	StackTraceImplBase(): _thread_id(0), _skip(0) {}

	size_t thread_id() const {
		return _thread_id;
	}

	void skip_n_firsts(size_t n) { _skip = n; }

protected:
	void load_thread_info() {
#ifdef BACKWARD_SYSTEM_LINUX
#ifndef __ANDROID__
		_thread_id = static_cast<size_t>(syscall(SYS_gettid));
#else
		_thread_id = static_cast<size_t>(gettid());
#endif
		if (_thread_id == static_cast<size_t>(getpid())) {
			// If the thread is the main one, let's hide that.
			// I like to keep little secret sometimes.
			_thread_id = 0;
		}
#elif defined(BACKWARD_SYSTEM_DARWIN)
		_thread_id = reinterpret_cast<size_t>(pthread_self());
		if (pthread_main_np() == 1) {
			// If the thread is the main one, let's hide that.
			_thread_id = 0;
		}
#endif
	}

	size_t skip_n_firsts() const { return _skip; }

private:
	size_t _thread_id;
	size_t _skip;
};

class StackTraceImplHolder: public StackTraceImplBase {
public:
	size_t size() const {
		return _stacktrace.size() ? _stacktrace.size() - skip_n_firsts() : 0;
	}
	Trace operator[](size_t idx) const {
		if (idx >= size()) {
			return Trace();
		}
		return Trace(_stacktrace[idx + skip_n_firsts()], idx);
	}
	void* const* begin() const {
		if (size()) {
			return &_stacktrace[skip_n_firsts()];
		}
		return nullptr;
	}

protected:
	std::vector<void*> _stacktrace;
};


#if BACKWARD_HAS_UNWIND == 1

namespace details {

template <typename F>
class Unwinder {
public:
	size_t operator()(F& f, size_t depth) {
		_f = &f;
		_index = -1;
		_depth = depth;
		_Unwind_Backtrace(&this->backtrace_trampoline, this);
		return static_cast<size_t>(_index);
	}

private:
	F*      _f;
	ssize_t _index;
	size_t  _depth;

	static _Unwind_Reason_Code backtrace_trampoline(
			_Unwind_Context* ctx, void *self) {
		return (static_cast<Unwinder*>(self))->backtrace(ctx);
	}

	_Unwind_Reason_Code backtrace(_Unwind_Context* ctx) {
		if (_index >= 0 && static_cast<size_t>(_index) >= _depth)
			return _URC_END_OF_STACK;

		int ip_before_instruction = 0;
		uintptr_t ip = _Unwind_GetIPInfo(ctx, &ip_before_instruction);

		if (!ip_before_instruction) {
			// calculating 0-1 for unsigned, looks like a possible bug to sanitiziers, so let's do it explicitly:
			if (ip==0) {
				ip = std::numeric_limits<uintptr_t>::max(); // set it to 0xffff... (as from casting 0-1)
			} else {
				ip -= 1; // else just normally decrement it (no overflow/underflow will happen)
			}
    }

		if (_index >= 0) { // ignore first frame.
			(*_f)(static_cast<size_t>(_index), reinterpret_cast<void*>(ip));
		}
		_index += 1;
		return _URC_NO_REASON;
	}
};

template <typename F>
size_t unwind(F f, size_t depth) {
	Unwinder<F> unwinder;
	return unwinder(f, depth);
}

} // namespace details


template <>
class StackTraceImpl<system_tag::current_tag>: public StackTraceImplHolder {
public:
	__attribute__ ((noinline)) // TODO use some macro
	size_t load_here(size_t depth=32) {
		load_thread_info();
		if (depth == 0) {
			return 0;
		}
		_stacktrace.resize(depth);
		size_t trace_cnt = details::unwind(callback(*this), depth);
		_stacktrace.resize(trace_cnt);
		skip_n_firsts(0);
		return size();
	}
	size_t load_from(void* addr, size_t depth=32) {
		load_here(depth + 8);

		for (size_t i = 0; i < _stacktrace.size(); ++i) {
			if (_stacktrace[i] == addr) {
				skip_n_firsts(i);
				break;
			}
		}

		_stacktrace.resize(std::min(_stacktrace.size(),
					skip_n_firsts() + depth));
		return size();
	}

private:
	struct callback {
		StackTraceImpl& self;
		callback(StackTraceImpl& _self): self(_self) {}

		void operator()(size_t idx, void* addr) {
			self._stacktrace[idx] = addr;
		}
	};
};


#else // BACKWARD_HAS_UNWIND == 0

template <>
class StackTraceImpl<system_tag::current_tag>: public StackTraceImplHolder {
public:
	__attribute__ ((noinline)) // TODO use some macro
	size_t load_here(size_t depth=32) {
		load_thread_info();
		if (depth == 0) {
			return 0;
		}
		_stacktrace.resize(depth + 1);
		size_t trace_cnt = backtrace(&_stacktrace[0], _stacktrace.size());
		_stacktrace.resize(trace_cnt);
		skip_n_firsts(1);
		return size();
	}

	size_t load_from(void* addr, size_t depth=32) {
		load_here(depth + 8);

		for (size_t i = 0; i < _stacktrace.size(); ++i) {
			if (_stacktrace[i] == addr) {
				skip_n_firsts(i);
				_stacktrace[i] = (void*)( (uintptr_t)_stacktrace[i] + 1);
				break;
			}
		}

		_stacktrace.resize(std::min(_stacktrace.size(),
					skip_n_firsts() + depth));
		return size();
	}
};

#endif // BACKWARD_HAS_UNWIND

class StackTrace:
	public StackTraceImpl<system_tag::current_tag> {};

/*************** TRACE RESOLVER ***************/

template <typename TAG>
class TraceResolverImpl;

#ifdef BACKWARD_SYSTEM_UNKNOWN

template <>
class TraceResolverImpl<system_tag::unknown_tag> {
public:
	template <class ST>
		void load_stacktrace(ST&) {}
	ResolvedTrace resolve(ResolvedTrace t) {
		return t;
	}
};

#endif

class TraceResolverImplBase {
protected:
	std::string demangle(const char* funcname) {
		return _demangler.demangle(funcname);
	}

private:
	details::demangler _demangler;
};

#ifdef BACKWARD_SYSTEM_LINUX

template <typename STACKTRACE_TAG>
class TraceResolverLinuxImpl;

#if BACKWARD_HAS_BACKTRACE_SYMBOL == 1

template <>
class TraceResolverLinuxImpl<trace_resolver_tag::backtrace_symbol>:
	public TraceResolverImplBase {
public:
	template <class ST>
		void load_stacktrace(ST& st) {
			using namespace details;
			if (st.size() == 0) {
				return;
			}
			_symbols.reset(
					backtrace_symbols(st.begin(), (int)st.size())
					);
		}

	ResolvedTrace resolve(ResolvedTrace trace) {
		char* filename = _symbols[trace.idx];
		char* funcname = filename;
		while (*funcname && *funcname != '(') {
			funcname += 1;
		}
		trace.object_filename.assign(filename, funcname); // ok even if funcname is the ending \0 (then we assign entire string)

		if (*funcname) { // if it's not end of string (e.g. from last frame ip==0)
			funcname += 1;
			char* funcname_end = funcname;
			while (*funcname_end && *funcname_end != ')' && *funcname_end != '+') {
				funcname_end += 1;
			}
			*funcname_end = '\0';
			trace.object_function = this->demangle(funcname);
			trace.source.function = trace.object_function; // we cannot do better.
		}
		return trace;
	}

private:
	details::handle<char**> _symbols;
};

#endif // BACKWARD_HAS_BACKTRACE_SYMBOL == 1

#if BACKWARD_HAS_BFD == 1

template <>
class TraceResolverLinuxImpl<trace_resolver_tag::libbfd>:
	public TraceResolverImplBase {
	static std::string read_symlink(std::string const & symlink_path) {
		std::string path;
		path.resize(100);

		while(true) {
			ssize_t len = ::readlink(symlink_path.c_str(), &*path.begin(), path.size());
			if(len < 0) {
				return "";
			}
			if (static_cast<size_t>(len) == path.size()) {
				path.resize(path.size() * 2);
			}
			else {
				path.resize(static_cast<std::string::size_type>(len));
				break;
			}
		}

		return path;
	}
public:
	TraceResolverLinuxImpl(): _bfd_loaded(false) {}

	template <class ST>
		void load_stacktrace(ST&) {}

	ResolvedTrace resolve(ResolvedTrace trace) {
		Dl_info symbol_info;

		// trace.addr is a virtual address in memory pointing to some code.
		// Let's try to find from which loaded object it comes from.
		// The loaded object can be yourself btw.
		if (!dladdr(trace.addr, &symbol_info)) {
			return trace; // dat broken trace...
		}

		std::string argv0;
		{
			std::ifstream ifs("/proc/self/cmdline");
			std::getline(ifs, argv0, '\0');
		}
		std::string tmp;
		if(symbol_info.dli_fname == argv0) {
			tmp = read_symlink("/proc/self/exe");
			symbol_info.dli_fname = tmp.c_str();
		}

		// Now we get in symbol_info:
		// .dli_fname:
		//		pathname of the shared object that contains the address.
		// .dli_fbase:
		//		where the object is loaded in memory.
		// .dli_sname:
		//		the name of the nearest symbol to trace.addr, we expect a
		//		function name.
		// .dli_saddr:
		//		the exact address corresponding to .dli_sname.

		if (symbol_info.dli_sname) {
			trace.object_function = demangle(symbol_info.dli_sname);
		}

		if (!symbol_info.dli_fname) {
			return trace;
		}

		trace.object_filename = symbol_info.dli_fname;
		bfd_fileobject& fobj = load_object_with_bfd(symbol_info.dli_fname);
		if (!fobj.handle) {
			return trace; // sad, we couldn't load the object :(
		}


		find_sym_result* details_selected; // to be filled.

		// trace.addr is the next instruction to be executed after returning
		// from the nested stack frame. In C++ this usually relate to the next
		// statement right after the function call that leaded to a new stack
		// frame. This is not usually what you want to see when printing out a
		// stacktrace...
		find_sym_result details_call_site = find_symbol_details(fobj,
				trace.addr, symbol_info.dli_fbase);
		details_selected = &details_call_site;

#if BACKWARD_HAS_UNWIND == 0
		// ...this is why we also try to resolve the symbol that is right
		// before the return address. If we are lucky enough, we will get the
		// line of the function that was called. But if the code is optimized,
		// we might get something absolutely not related since the compiler
		// can reschedule the return address with inline functions and
		// tail-call optimisation (among other things that I don't even know
		// or cannot even dream about with my tiny limited brain).
		find_sym_result details_adjusted_call_site = find_symbol_details(fobj,
				(void*) (uintptr_t(trace.addr) - 1),
				symbol_info.dli_fbase);

		// In debug mode, we should always get the right thing(TM).
		if (details_call_site.found && details_adjusted_call_site.found) {
			// Ok, we assume that details_adjusted_call_site is a better estimation.
			details_selected = &details_adjusted_call_site;
			trace.addr = (void*) (uintptr_t(trace.addr) - 1);
		}

		if (details_selected == &details_call_site && details_call_site.found) {
			// we have to re-resolve the symbol in order to reset some
			// internal state in BFD... so we can call backtrace_inliners
			// thereafter...
			details_call_site = find_symbol_details(fobj, trace.addr,
					symbol_info.dli_fbase);
		}
#endif // BACKWARD_HAS_UNWIND

		if (details_selected->found) {
			if (details_selected->filename) {
				trace.source.filename = details_selected->filename;
			}
			trace.source.line = details_selected->line;

			if (details_selected->funcname) {
				// this time we get the name of the function where the code is
				// located, instead of the function were the address is
				// located. In short, if the code was inlined, we get the
				// function correspoding to the code. Else we already got in
				// trace.function.
				trace.source.function = demangle(details_selected->funcname);

				if (!symbol_info.dli_sname) {
					// for the case dladdr failed to find the symbol name of
					// the function, we might as well try to put something
					// here.
					trace.object_function = trace.source.function;
				}
			}

			// Maybe the source of the trace got inlined inside the function
			// (trace.source.function). Let's see if we can get all the inlined
			// calls along the way up to the initial call site.
			trace.inliners = backtrace_inliners(fobj, *details_selected);

#if 0
			if (trace.inliners.size() == 0) {
				// Maybe the trace was not inlined... or maybe it was and we
				// are lacking the debug information. Let's try to make the
				// world better and see if we can get the line number of the
				// function (trace.source.function) now.
				//
				// We will get the location of where the function start (to be
				// exact: the first instruction that really start the
				// function), not where the name of the function is defined.
				// This can be quite far away from the name of the function
				// btw.
				//
				// If the source of the function is the same as the source of
				// the trace, we cannot say if the trace was really inlined or
				// not.  However, if the filename of the source is different
				// between the function and the trace... we can declare it as
				// an inliner.  This is not 100% accurate, but better than
				// nothing.

				if (symbol_info.dli_saddr) {
					find_sym_result details = find_symbol_details(fobj,
							symbol_info.dli_saddr,
							symbol_info.dli_fbase);

					if (details.found) {
						ResolvedTrace::SourceLoc diy_inliner;
						diy_inliner.line = details.line;
						if (details.filename) {
							diy_inliner.filename = details.filename;
						}
						if (details.funcname) {
							diy_inliner.function = demangle(details.funcname);
						} else {
							diy_inliner.function = trace.source.function;
						}
						if (diy_inliner != trace.source) {
							trace.inliners.push_back(diy_inliner);
						}
					}
				}
			}
#endif
		}

		return trace;
	}

private:
	bool                _bfd_loaded;

	typedef details::handle<bfd*,
			details::deleter<bfd_boolean, bfd*, &bfd_close>
				> bfd_handle_t;

	typedef details::handle<asymbol**> bfd_symtab_t;


	struct bfd_fileobject {
		bfd_handle_t handle;
		bfd_vma      base_addr;
		bfd_symtab_t symtab;
		bfd_symtab_t dynamic_symtab;
	};

	typedef details::hashtable<std::string, bfd_fileobject>::type
		fobj_bfd_map_t;
	fobj_bfd_map_t      _fobj_bfd_map;

	bfd_fileobject& load_object_with_bfd(const std::string& filename_object) {
		using namespace details;

		if (!_bfd_loaded) {
			using namespace details;
			bfd_init();
			_bfd_loaded = true;
		}

		fobj_bfd_map_t::iterator it =
			_fobj_bfd_map.find(filename_object);
		if (it != _fobj_bfd_map.end()) {
			return it->second;
		}

		// this new object is empty for now.
		bfd_fileobject& r = _fobj_bfd_map[filename_object];

		// we do the work temporary in this one;
		bfd_handle_t bfd_handle;

		int fd = open(filename_object.c_str(), O_RDONLY);
		bfd_handle.reset(
				bfd_fdopenr(filename_object.c_str(), "default", fd)
				);
		if (!bfd_handle) {
			close(fd);
			return r;
		}

		if (!bfd_check_format(bfd_handle.get(), bfd_object)) {
			return r; // not an object? You lose.
		}

		if ((bfd_get_file_flags(bfd_handle.get()) & HAS_SYMS) == 0) {
			return r; // that's what happen when you forget to compile in debug.
		}

		ssize_t symtab_storage_size =
			bfd_get_symtab_upper_bound(bfd_handle.get());

		ssize_t dyn_symtab_storage_size =
			bfd_get_dynamic_symtab_upper_bound(bfd_handle.get());

		if (symtab_storage_size <= 0 && dyn_symtab_storage_size <= 0) {
			return r; // weird, is the file is corrupted?
		}

		bfd_symtab_t symtab, dynamic_symtab;
		ssize_t symcount = 0, dyn_symcount = 0;

		if (symtab_storage_size > 0) {
			symtab.reset(
					static_cast<bfd_symbol**>(malloc(static_cast<size_t>(symtab_storage_size)))
					);
			symcount = bfd_canonicalize_symtab(
					bfd_handle.get(), symtab.get()
					);
		}

		if (dyn_symtab_storage_size > 0) {
			dynamic_symtab.reset(
					static_cast<bfd_symbol**>(malloc(static_cast<size_t>(dyn_symtab_storage_size)))
					);
			dyn_symcount = bfd_canonicalize_dynamic_symtab(
					bfd_handle.get(), dynamic_symtab.get()
					);
		}


		if (symcount <= 0 && dyn_symcount <= 0) {
			return r; // damned, that's a stripped file that you got there!
		}

		r.handle = move(bfd_handle);
		r.symtab = move(symtab);
		r.dynamic_symtab = move(dynamic_symtab);
		return r;
	}

	struct find_sym_result {
		bool found;
		const char* filename;
		const char* funcname;
		unsigned int line;
	};

	struct find_sym_context {
		TraceResolverLinuxImpl* self;
		bfd_fileobject* fobj;
		void* addr;
		void* base_addr;
		find_sym_result result;
	};

	find_sym_result find_symbol_details(bfd_fileobject& fobj, void* addr,
			void* base_addr) {
		find_sym_context context;
		context.self = this;
		context.fobj = &fobj;
		context.addr = addr;
		context.base_addr = base_addr;
		context.result.found = false;
		bfd_map_over_sections(fobj.handle.get(), &find_in_section_trampoline,
				static_cast<void*>(&context));
		return context.result;
	}

	static void find_in_section_trampoline(bfd*, asection* section,
			void* data) {
		find_sym_context* context = static_cast<find_sym_context*>(data);
		context->self->find_in_section(
				reinterpret_cast<bfd_vma>(context->addr),
				reinterpret_cast<bfd_vma>(context->base_addr),
				*context->fobj,
				section, context->result
				);
	}

	void find_in_section(bfd_vma addr, bfd_vma base_addr,
			bfd_fileobject& fobj, asection* section, find_sym_result& result)
	{
		if (result.found) return;

		if ((bfd_get_section_flags(fobj.handle.get(), section)
					& SEC_ALLOC) == 0)
			return; // a debug section is never loaded automatically.

		bfd_vma sec_addr = bfd_get_section_vma(fobj.handle.get(), section);
		bfd_size_type size = bfd_get_section_size(section);

		// are we in the boundaries of the section?
		if (addr < sec_addr || addr >= sec_addr + size) {
			addr -= base_addr; // oups, a relocated object, lets try again...
			if (addr < sec_addr || addr >= sec_addr + size) {
				return;
			}
		}

#if defined(__clang__)
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wzero-as-null-pointer-constant"
#endif
		if (!result.found && fobj.symtab) {
			result.found = bfd_find_nearest_line(fobj.handle.get(), section,
					fobj.symtab.get(), addr - sec_addr, &result.filename,
					&result.funcname, &result.line);
		}

		if (!result.found && fobj.dynamic_symtab) {
			result.found = bfd_find_nearest_line(fobj.handle.get(), section,
					fobj.dynamic_symtab.get(), addr - sec_addr,
					&result.filename, &result.funcname, &result.line);
		}
#if defined(__clang__)
#pragma clang diagnostic pop
#endif

	}

	ResolvedTrace::source_locs_t backtrace_inliners(bfd_fileobject& fobj,
			find_sym_result previous_result) {
		// This function can be called ONLY after a SUCCESSFUL call to
		// find_symbol_details. The state is global to the bfd_handle.
		ResolvedTrace::source_locs_t results;
		while (previous_result.found) {
			find_sym_result result;
			result.found = bfd_find_inliner_info(fobj.handle.get(),
					&result.filename, &result.funcname, &result.line);

			if (result.found) /* and not (
						cstrings_eq(previous_result.filename, result.filename)
						and cstrings_eq(previous_result.funcname, result.funcname)
						and result.line == previous_result.line
						)) */ {
				ResolvedTrace::SourceLoc src_loc;
				src_loc.line = result.line;
				if (result.filename) {
					src_loc.filename = result.filename;
				}
				if (result.funcname) {
					src_loc.function = demangle(result.funcname);
				}
				results.push_back(src_loc);
			}
			previous_result = result;
		}
		return results;
	}

	bool cstrings_eq(const char* a, const char* b) {
		if (!a || !b) {
			return false;
		}
		return strcmp(a, b) == 0;
	}

};
#endif // BACKWARD_HAS_BFD == 1

#if BACKWARD_HAS_DW == 1

template <>
class TraceResolverLinuxImpl<trace_resolver_tag::libdw>:
	public TraceResolverImplBase {
public:
	TraceResolverLinuxImpl(): _dwfl_handle_initialized(false) {}

	template <class ST>
		void load_stacktrace(ST&) {}

	ResolvedTrace resolve(ResolvedTrace trace) {
		using namespace details;

		Dwarf_Addr trace_addr = (Dwarf_Addr) trace.addr;

		if (!_dwfl_handle_initialized) {
			// initialize dwfl...
			_dwfl_cb.reset(new Dwfl_Callbacks);
			_dwfl_cb->find_elf = &dwfl_linux_proc_find_elf;
			_dwfl_cb->find_debuginfo = &dwfl_standard_find_debuginfo;
			_dwfl_cb->debuginfo_path = 0;

			_dwfl_handle.reset(dwfl_begin(_dwfl_cb.get()));
			_dwfl_handle_initialized = true;

			if (!_dwfl_handle) {
				return trace;
			}

			// ...from the current process.
			dwfl_report_begin(_dwfl_handle.get());
			int r = dwfl_linux_proc_report (_dwfl_handle.get(), getpid());
			dwfl_report_end(_dwfl_handle.get(), NULL, NULL);
			if (r < 0) {
				return trace;
			}
		}

		if (!_dwfl_handle) {
			return trace;
		}

		// find the module (binary object) that contains the trace's address.
		// This is not using any debug information, but the addresses ranges of
		// all the currently loaded binary object.
		Dwfl_Module* mod = dwfl_addrmodule(_dwfl_handle.get(), trace_addr);
		if (mod) {
			// now that we found it, lets get the name of it, this will be the
			// full path to the running binary or one of the loaded library.
			const char* module_name = dwfl_module_info (mod,
					0, 0, 0, 0, 0, 0, 0);
			if (module_name) {
				trace.object_filename = module_name;
			}
			// We also look after the name of the symbol, equal or before this
			// address. This is found by walking the symtab. We should get the
			// symbol corresponding to the function (mangled) containing the
			// address. If the code corresponding to the address was inlined,
			// this is the name of the out-most inliner function.
			const char* sym_name = dwfl_module_addrname(mod, trace_addr);
			if (sym_name) {
				trace.object_function = demangle(sym_name);
			}
		}

		// now let's get serious, and find out the source location (file and
		// line number) of the address.

		// This function will look in .debug_aranges for the address and map it
		// to the location of the compilation unit DIE in .debug_info and
		// return it.
		Dwarf_Addr mod_bias = 0;
		Dwarf_Die* cudie = dwfl_module_addrdie(mod, trace_addr, &mod_bias);

#if 1
		if (!cudie) {
			// Sadly clang does not generate the section .debug_aranges, thus
			// dwfl_module_addrdie will fail early. Clang doesn't either set
			// the lowpc/highpc/range info for every compilation unit.
			//
			// So in order to save the world:
			// for every compilation unit, we will iterate over every single
			// DIEs. Normally functions should have a lowpc/highpc/range, which
			// we will use to infer the compilation unit.

			// note that this is probably badly inefficient.
			while ((cudie = dwfl_module_nextcu(mod, cudie, &mod_bias))) {
				Dwarf_Die die_mem;
				Dwarf_Die* fundie = find_fundie_by_pc(cudie,
						trace_addr - mod_bias, &die_mem);
				if (fundie) {
					break;
				}
			}
		}
#endif

//#define BACKWARD_I_DO_NOT_RECOMMEND_TO_ENABLE_THIS_HORRIBLE_PIECE_OF_CODE
#ifdef BACKWARD_I_DO_NOT_RECOMMEND_TO_ENABLE_THIS_HORRIBLE_PIECE_OF_CODE
		if (!cudie) {
			// If it's still not enough, lets dive deeper in the shit, and try
			// to save the world again: for every compilation unit, we will
			// load the corresponding .debug_line section, and see if we can
			// find our address in it.

			Dwarf_Addr cfi_bias;
			Dwarf_CFI* cfi_cache = dwfl_module_eh_cfi(mod, &cfi_bias);

			Dwarf_Addr bias;
			while ((cudie = dwfl_module_nextcu(mod, cudie, &bias))) {
				if (dwarf_getsrc_die(cudie, trace_addr - bias)) {

					// ...but if we get a match, it might be a false positive
					// because our (address - bias) might as well be valid in a
					// different compilation unit. So we throw our last card on
					// the table and lookup for the address into the .eh_frame
					// section.

					handle<Dwarf_Frame*> frame;
					dwarf_cfi_addrframe(cfi_cache, trace_addr - cfi_bias, &frame);
					if (frame) {
						break;
					}
				}
			}
		}
#endif

		if (!cudie) {
			return trace; // this time we lost the game :/
		}

		// Now that we have a compilation unit DIE, this function will be able
		// to load the corresponding section in .debug_line (if not already
		// loaded) and hopefully find the source location mapped to our
		// address.
		Dwarf_Line* srcloc = dwarf_getsrc_die(cudie, trace_addr - mod_bias);

		if (srcloc) {
			const char* srcfile = dwarf_linesrc(srcloc, 0, 0);
			if (srcfile) {
				trace.source.filename = srcfile;
			}
			int line = 0, col = 0;
			dwarf_lineno(srcloc, &line);
			dwarf_linecol(srcloc, &col);
			trace.source.line = line;
			trace.source.col = col;
		}

		deep_first_search_by_pc(cudie, trace_addr - mod_bias,
				inliners_search_cb(trace));
		if (trace.source.function.size() == 0) {
			// fallback.
			trace.source.function = trace.object_function;
		}

		return trace;
	}

private:
	typedef details::handle<Dwfl*, details::deleter<void, Dwfl*, &dwfl_end> >
		dwfl_handle_t;
	details::handle<Dwfl_Callbacks*, details::default_delete<Dwfl_Callbacks*> >
		           _dwfl_cb;
	dwfl_handle_t  _dwfl_handle;
	bool           _dwfl_handle_initialized;

	// defined here because in C++98, template function cannot take locally
	// defined types... grrr.
	struct inliners_search_cb {
		void operator()(Dwarf_Die* die) {
			switch (dwarf_tag(die)) {
				const char* name;
				case DW_TAG_subprogram:
					if ((name = dwarf_diename(die))) {
						trace.source.function = name;
					}
					break;

				case DW_TAG_inlined_subroutine:
					ResolvedTrace::SourceLoc sloc;
					Dwarf_Attribute attr_mem;

					if ((name = dwarf_diename(die))) {
						sloc.function = name;
					}
					if ((name = die_call_file(die))) {
						sloc.filename = name;
					}

					Dwarf_Word line = 0, col = 0;
					dwarf_formudata(dwarf_attr(die, DW_AT_call_line,
								&attr_mem), &line);
					dwarf_formudata(dwarf_attr(die, DW_AT_call_column,
								&attr_mem), &col);
					sloc.line = (unsigned)line;
					sloc.col = (unsigned)col;

					trace.inliners.push_back(sloc);
					break;
			};
		}
		ResolvedTrace& trace;
		inliners_search_cb(ResolvedTrace& t): trace(t) {}
	};


	static bool die_has_pc(Dwarf_Die* die, Dwarf_Addr pc) {
		Dwarf_Addr low, high;

		// continuous range
		if (dwarf_hasattr(die, DW_AT_low_pc) &&
							dwarf_hasattr(die, DW_AT_high_pc)) {
			if (dwarf_lowpc(die, &low) != 0) {
				return false;
			}
			if (dwarf_highpc(die, &high) != 0) {
				Dwarf_Attribute attr_mem;
				Dwarf_Attribute* attr = dwarf_attr(die, DW_AT_high_pc, &attr_mem);
				Dwarf_Word value;
				if (dwarf_formudata(attr, &value) != 0) {
					return false;
				}
				high = low + value;
			}
			return pc >= low && pc < high;
		}

		// non-continuous range.
		Dwarf_Addr base;
		ptrdiff_t offset = 0;
		while ((offset = dwarf_ranges(die, offset, &base, &low, &high)) > 0) {
			if (pc >= low && pc < high) {
				return true;
			}
		}
		return false;
	}

	static Dwarf_Die* find_fundie_by_pc(Dwarf_Die* parent_die, Dwarf_Addr pc,
			Dwarf_Die* result) {
		if (dwarf_child(parent_die, result) != 0) {
			return 0;
		}

		Dwarf_Die* die = result;
		do {
			switch (dwarf_tag(die)) {
				case DW_TAG_subprogram:
				case DW_TAG_inlined_subroutine:
					if (die_has_pc(die, pc)) {
						return result;
					}
			};
			bool declaration = false;
			Dwarf_Attribute attr_mem;
			dwarf_formflag(dwarf_attr(die, DW_AT_declaration,
						&attr_mem), &declaration);
			if (!declaration) {
				// let's be curious and look deeper in the tree,
				// function are not necessarily at the first level, but
				// might be nested inside a namespace, structure etc.
				Dwarf_Die die_mem;
				Dwarf_Die* indie = find_fundie_by_pc(die, pc, &die_mem);
				if (indie) {
					*result = die_mem;
					return result;
				}
			}
		} while (dwarf_siblingof(die, result) == 0);
		return 0;
	}

	template <typename CB>
		static bool deep_first_search_by_pc(Dwarf_Die* parent_die,
				Dwarf_Addr pc, CB cb) {
		Dwarf_Die die_mem;
		if (dwarf_child(parent_die, &die_mem) != 0) {
			return false;
		}

		bool branch_has_pc = false;
		Dwarf_Die* die = &die_mem;
		do {
			bool declaration = false;
			Dwarf_Attribute attr_mem;
			dwarf_formflag(dwarf_attr(die, DW_AT_declaration, &attr_mem), &declaration);
			if (!declaration) {
				// let's be curious and look deeper in the tree, function are
				// not necessarily at the first level, but might be nested
				// inside a namespace, structure, a function, an inlined
				// function etc.
				branch_has_pc = deep_first_search_by_pc(die, pc, cb);
			}
			if (!branch_has_pc) {
				branch_has_pc = die_has_pc(die, pc);
			}
			if (branch_has_pc) {
				cb(die);
			}
		} while (dwarf_siblingof(die, &die_mem) == 0);
		return branch_has_pc;
	}

	static const char* die_call_file(Dwarf_Die *die) {
		Dwarf_Attribute attr_mem;
		Dwarf_Sword file_idx = 0;

		dwarf_formsdata(dwarf_attr(die, DW_AT_call_file, &attr_mem),
				&file_idx);

		if (file_idx == 0) {
			return 0;
		}

		Dwarf_Die die_mem;
		Dwarf_Die* cudie = dwarf_diecu(die, &die_mem, 0, 0);
		if (!cudie) {
			return 0;
		}

		Dwarf_Files* files = 0;
		size_t nfiles;
		dwarf_getsrcfiles(cudie, &files, &nfiles);
		if (!files) {
			return 0;
		}

		return dwarf_filesrc(files, file_idx, 0, 0);
	}

};
#endif // BACKWARD_HAS_DW == 1

#if BACKWARD_HAS_DWARF == 1

template <>
class TraceResolverLinuxImpl<trace_resolver_tag::libdwarf>:
	public TraceResolverImplBase {
	static std::string read_symlink(std::string const & symlink_path) {
		std::string path;
		path.resize(100);

		while(true) {
			ssize_t len = ::readlink(symlink_path.c_str(),
									&*path.begin(), path.size());
			if(len < 0) {
				return "";
			}
			if ((size_t)len == path.size()) {
				path.resize(path.size() * 2);
			}
			else {
				path.resize(len);
				break;
			}
		}

		return path;
	}
public:
	TraceResolverLinuxImpl(): _dwarf_loaded(false) {}

	template <class ST>
		void load_stacktrace(ST&) {}

	ResolvedTrace resolve(ResolvedTrace trace) {
		// trace.addr is a virtual address in memory pointing to some code.
		// Let's try to find from which loaded object it comes from.
		// The loaded object can be yourself btw.

		Dl_info symbol_info;
		int dladdr_result = 0;
#ifndef __ANDROID__
		link_map *link_map;
		// We request the link map so we can get information about offsets
		dladdr_result = dladdr1(trace.addr, &symbol_info,
				reinterpret_cast<void**>(&link_map), RTLD_DL_LINKMAP);
#else
		// Android doesn't have dladdr1. Don't use the linker map.
		dladdr_result = dladdr(trace.addr, &symbol_info);
#endif
		if (!dladdr_result) {
			return trace; // dat broken trace...
		}

		std::string argv0;
		{
			std::ifstream ifs("/proc/self/cmdline");
			std::getline(ifs, argv0, '\0');
		}
		std::string tmp;
		if(symbol_info.dli_fname == argv0) {
			tmp = read_symlink("/proc/self/exe");
			symbol_info.dli_fname = tmp.c_str();
		}

		// Now we get in symbol_info:
		// .dli_fname:
		//      pathname of the shared object that contains the address.
		// .dli_fbase:
		//      where the object is loaded in memory.
		// .dli_sname:
		//      the name of the nearest symbol to trace.addr, we expect a
		//      function name.
		// .dli_saddr:
		//      the exact address corresponding to .dli_sname.
		//
		// And in link_map:
		// .l_addr:
		//      difference between the address in the ELF file and the address
		//      in memory
		// l_name:
		//      absolute pathname where the object was found

		if (symbol_info.dli_sname) {
			trace.object_function = demangle(symbol_info.dli_sname);
		}

		if (!symbol_info.dli_fname) {
			return trace;
		}

		trace.object_filename = symbol_info.dli_fname;
		dwarf_fileobject& fobj = load_object_with_dwarf(symbol_info.dli_fname);
		if (!fobj.dwarf_handle) {
			return trace; // sad, we couldn't load the object :(
		}

#ifndef __ANDROID__
		// Convert the address to a module relative one by looking at
		// the module's loading address in the link map
		Dwarf_Addr address = reinterpret_cast<uintptr_t>(trace.addr) -
				reinterpret_cast<uintptr_t>(link_map->l_addr);
#else
		Dwarf_Addr address = reinterpret_cast<uintptr_t>(trace.addr);
#endif

		if (trace.object_function.empty()) {
			symbol_cache_t::iterator it =
					fobj.symbol_cache.lower_bound(address);

			if (it != fobj.symbol_cache.end()) {
				if (it->first != address) {
					if (it != fobj.symbol_cache.begin()) {
						--it;
					}
				}
				trace.object_function = demangle(it->second.c_str());
			}
		}

		// Get the Compilation Unit DIE for the address
		Dwarf_Die die = find_die(fobj, address);

		if (!die) {
			return trace; // this time we lost the game :/
		}

		// libdwarf doesn't give us direct access to its objects, it always
		// allocates a copy for the caller. We keep that copy alive in a cache
		// and we deallocate it later when it's no longer required.
		die_cache_entry& die_object = get_die_cache(fobj, die);
		if (die_object.isEmpty())
			return trace;  // We have no line section for this DIE

		die_linemap_t::iterator it =
				die_object.line_section.lower_bound(address);

		if (it != die_object.line_section.end()) {
			if (it->first != address) {
				if (it == die_object.line_section.begin()) {
					// If we are on the first item of the line section
					// but the address does not match it means that
					// the address is below the range of the DIE. Give up.
					return trace;
				} else {
					--it;
				}
			}
		} else {
			return trace; // We didn't find the address.
		}

		// Get the Dwarf_Line that the address points to and call libdwarf
		// to get source file, line and column info.
		Dwarf_Line line = die_object.line_buffer[it->second];
		Dwarf_Error error = DW_DLE_NE;

		char* filename;
		if (dwarf_linesrc(line, &filename, &error)
				== DW_DLV_OK) {
			trace.source.filename = std::string(filename);
			dwarf_dealloc(fobj.dwarf_handle.get(), filename, DW_DLA_STRING);
		}

		Dwarf_Unsigned number = 0;
		if (dwarf_lineno(line, &number, &error) == DW_DLV_OK) {
			trace.source.line = number;
		} else {
			trace.source.line = 0;
		}

		if (dwarf_lineoff_b(line, &number, &error) == DW_DLV_OK) {
			trace.source.col = number;
		} else {
			trace.source.col = 0;
		}

		std::vector<std::string> namespace_stack;
		deep_first_search_by_pc(fobj, die, address, namespace_stack,
				inliners_search_cb(trace, fobj, die));

		dwarf_dealloc(fobj.dwarf_handle.get(), die, DW_DLA_DIE);

		return trace;
	}

public:
	static int close_dwarf(Dwarf_Debug dwarf) {
		return dwarf_finish(dwarf, NULL);
	}

private:
	bool                _dwarf_loaded;

	typedef details::handle<int,
					details::deleter<int, int, &::close>
							> dwarf_file_t;

	typedef details::handle<Elf*,
					details::deleter<int, Elf*, &elf_end>
							> dwarf_elf_t;

	typedef details::handle<Dwarf_Debug,
					details::deleter<int, Dwarf_Debug, &close_dwarf>
							> dwarf_handle_t;

	typedef std::map<Dwarf_Addr, int>		die_linemap_t;

	typedef std::map<Dwarf_Off, Dwarf_Off>	die_specmap_t;

	struct die_cache_entry {
		die_specmap_t			spec_section;
		die_linemap_t			line_section;
		Dwarf_Line*				line_buffer;
		Dwarf_Signed			line_count;
		Dwarf_Line_Context		line_context;

		inline bool isEmpty() {
			return  line_buffer == NULL ||
					line_count == 0 ||
					line_context == NULL ||
					line_section.empty();
		}

		die_cache_entry() :
			line_buffer(0), line_count(0), line_context(0) {}

		~die_cache_entry()
		{
			if (line_context) {
				dwarf_srclines_dealloc_b(line_context);
			}
		}
	};

	typedef std::map<Dwarf_Off, die_cache_entry> die_cache_t;

	typedef std::map<uintptr_t, std::string>     symbol_cache_t;

	struct dwarf_fileobject {
		dwarf_file_t		file_handle;
		dwarf_elf_t			elf_handle;
		dwarf_handle_t		dwarf_handle;
		symbol_cache_t		symbol_cache;

		// Die cache
		die_cache_t     	die_cache;
		die_cache_entry*	current_cu;
	};

	typedef details::hashtable<std::string, dwarf_fileobject>::type
			fobj_dwarf_map_t;
	fobj_dwarf_map_t    _fobj_dwarf_map;

	static bool cstrings_eq(const char* a, const char* b) {
		if (!a || !b) {
			return false;
		}
		return strcmp(a, b) == 0;
	}

	dwarf_fileobject& load_object_with_dwarf(
			const std::string& filename_object) {

		if (!_dwarf_loaded) {
			// Set the ELF library operating version
			// If that fails there's nothing we can do
			_dwarf_loaded = elf_version(EV_CURRENT) != EV_NONE;
		}

		fobj_dwarf_map_t::iterator it =
				_fobj_dwarf_map.find(filename_object);
		if (it != _fobj_dwarf_map.end()) {
				return it->second;
		}

		// this new object is empty for now
		dwarf_fileobject& r = _fobj_dwarf_map[filename_object];

		dwarf_file_t file_handle;
		file_handle.reset(open(filename_object.c_str(), O_RDONLY));
		if (file_handle < 0) {
			return r;
		}

		// Try to get an ELF handle. We need to read the ELF sections
		// because we want to see if there is a .gnu_debuglink section
		// that points to a split debug file
		dwarf_elf_t elf_handle;
		elf_handle.reset(elf_begin(file_handle.get(), ELF_C_READ, NULL));
		if (!elf_handle) {
			return r;
		}

		const char* e_ident = elf_getident(elf_handle.get(), 0);
		if (!e_ident) {
			return r;
		}

		// Get the number of sections
		// We use the new APIs as elf_getshnum is deprecated
		size_t shdrnum = 0;
		if (elf_getshdrnum(elf_handle.get(), &shdrnum) == -1) {
			return r;
		}

		// Get the index to the string section
		size_t shdrstrndx = 0;
		if (elf_getshdrstrndx (elf_handle.get(), &shdrstrndx) == -1) {
			return r;
		}

		std::string debuglink;
		// Iterate through the ELF sections to try to get a gnu_debuglink
		// note and also to cache the symbol table.
		// We go the preprocessor way to avoid having to create templated
		// classes or using gelf (which might throw a compiler error if 64 bit
		// is not supported
#define ELF_GET_DATA(ARCH)                                                   \
		Elf_Scn *elf_section = 0;                                            \
		Elf_Data *elf_data = 0;                                              \
		Elf##ARCH##_Shdr* section_header = 0;                                \
		Elf_Scn *symbol_section = 0;                                         \
		size_t symbol_count = 0;                                             \
		size_t symbol_strings = 0;                                           \
		Elf##ARCH##_Sym *symbol = 0;                                         \
		const char* section_name = 0;                                        \
		                                                                     \
		while ((elf_section = elf_nextscn(elf_handle.get(), elf_section))    \
				!= NULL) {                                                   \
			section_header = elf##ARCH##_getshdr(elf_section);               \
			if (section_header == NULL) {                                    \
				return r;                                                    \
			}                                                                \
		                                                                     \
			if ((section_name = elf_strptr(                                  \
								elf_handle.get(), shdrstrndx,                \
								section_header->sh_name)) == NULL) {         \
				return r;                                                    \
			}                                                                \
		                                                                     \
			if (cstrings_eq(section_name, ".gnu_debuglink")) {               \
				elf_data = elf_getdata(elf_section, NULL);                   \
				if (elf_data && elf_data->d_size > 0) {                      \
					debuglink = std::string(                                 \
							reinterpret_cast<const char*>(elf_data->d_buf)); \
				}                                                            \
			}                                                                \
		                                                                     \
			switch(section_header->sh_type) {                                \
				case SHT_SYMTAB:                                             \
					symbol_section = elf_section;                            \
					symbol_count   = section_header->sh_size /               \
									section_header->sh_entsize;              \
					symbol_strings = section_header->sh_link;                \
					break;                                                   \
		                                                                     \
				/* We use .dynsyms as a last resort, we prefer .symtab */    \
				case SHT_DYNSYM:                                             \
					if (!symbol_section) {                                   \
						symbol_section = elf_section;                        \
						symbol_count   = section_header->sh_size /           \
										section_header->sh_entsize;          \
						symbol_strings = section_header->sh_link;            \
					}                                                        \
					break;                                                   \
			}                                                                \
		}                                                                    \
		                                                                     \
		if (symbol_section && symbol_count && symbol_strings) {              \
			elf_data = elf_getdata(symbol_section, NULL);                    \
			symbol = reinterpret_cast<Elf##ARCH##_Sym*>(elf_data->d_buf);    \
			for (size_t i = 0; i < symbol_count; ++i) {                      \
				int type = ELF##ARCH##_ST_TYPE(symbol->st_info);             \
				if (type == STT_FUNC && symbol->st_value > 0) {              \
					r.symbol_cache[symbol->st_value] = std::string(          \
							elf_strptr(elf_handle.get(),                     \
							symbol_strings, symbol->st_name));               \
				}                                                            \
				++symbol;                                                    \
			}                                                                \
		}                                                                    \


		if (e_ident[EI_CLASS] == ELFCLASS32) {
			ELF_GET_DATA(32)
		} else if (e_ident[EI_CLASS] == ELFCLASS64) {
		// libelf might have been built without 64 bit support
#if __LIBELF64
			ELF_GET_DATA(64)
#endif
		}

		if (!debuglink.empty()) {
			// We have a debuglink section! Open an elf instance on that
			// file instead. If we can't open the file, then return
			// the elf handle we had already opened.
			dwarf_file_t debuglink_file;
			debuglink_file.reset(open(debuglink.c_str(), O_RDONLY));
			if (debuglink_file.get() > 0) {
				dwarf_elf_t debuglink_elf;
				debuglink_elf.reset(
					elf_begin(debuglink_file.get(),ELF_C_READ, NULL)
				);

				// If we have a valid elf handle, return the new elf handle
				// and file handle and discard the original ones
				if (debuglink_elf) {
					elf_handle = move(debuglink_elf);
					file_handle = move(debuglink_file);
				}
			}
		}

		// Ok, we have a valid ELF handle, let's try to get debug symbols
		Dwarf_Debug dwarf_debug;
		Dwarf_Error error = DW_DLE_NE;
		dwarf_handle_t dwarf_handle;

		int dwarf_result = dwarf_elf_init(elf_handle.get(),
						DW_DLC_READ, NULL, NULL, &dwarf_debug, &error);

		// We don't do any special handling for DW_DLV_NO_ENTRY specially.
		// If we get an error, or the file doesn't have debug information
		// we just return.
		if (dwarf_result != DW_DLV_OK) {
			return r;
		}

		dwarf_handle.reset(dwarf_debug);

		r.file_handle = move(file_handle);
		r.elf_handle = move(elf_handle);
		r.dwarf_handle = move(dwarf_handle);

		return r;
	}

	die_cache_entry& get_die_cache(dwarf_fileobject& fobj, Dwarf_Die die)
	{
		Dwarf_Error error = DW_DLE_NE;

		// Get the die offset, we use it as the cache key
		Dwarf_Off die_offset;
		if (dwarf_dieoffset(die, &die_offset, &error) != DW_DLV_OK) {
			die_offset = 0;
		}

		die_cache_t::iterator it = fobj.die_cache.find(die_offset);

		if (it != fobj.die_cache.end()) {
			fobj.current_cu = &it->second;
			return it->second;
		}

		die_cache_entry& de = fobj.die_cache[die_offset];
		fobj.current_cu = &de;

		Dwarf_Addr line_addr;
		Dwarf_Small table_count;

		// The addresses in the line section are not fully sorted (they might
		// be sorted by block of code belonging to the same file), which makes
		// it necessary to do so before searching is possible.
		//
		// As libdwarf allocates a copy of everything, let's get the contents
		// of the line section and keep it around. We also create a map of
		// program counter to line table indices so we can search by address
		// and get the line buffer index.
		//
		// To make things more difficult, the same address can span more than
		// one line, so we need to keep the index pointing to the first line
		// by using insert instead of the map's [ operator.

		// Get the line context for the DIE
		if (dwarf_srclines_b(die, 0, &table_count, &de.line_context, &error)
				== DW_DLV_OK) {
			// Get the source lines for this line context, to be deallocated
			// later
			if (dwarf_srclines_from_linecontext(
					de.line_context, &de.line_buffer, &de.line_count, &error)
						== DW_DLV_OK) {

				// Add all the addresses to our map
				for (int i = 0; i < de.line_count; i++) {
					if (dwarf_lineaddr(de.line_buffer[i], &line_addr, &error)
							!= DW_DLV_OK) {
						line_addr = 0;
					}
					de.line_section.insert(
							std::pair<Dwarf_Addr, int>(line_addr, i));
				}
			}
		}

		// For each CU, cache the function DIEs that contain the
		// DW_AT_specification attribute. When building with -g3 the function
		// DIEs are separated in declaration and specification, with the
		// declaration containing only the name and parameters and the
		// specification the low/high pc and other compiler attributes.
		//
		// We cache those specifications so we don't skip over the declarations,
		// because they have no pc, and we can do namespace resolution for
		// DWARF function names.
		Dwarf_Debug dwarf = fobj.dwarf_handle.get();
		Dwarf_Die current_die = 0;
		if (dwarf_child(die, &current_die, &error) == DW_DLV_OK) {
			for(;;) {
				Dwarf_Die sibling_die = 0;

				Dwarf_Half tag_value;
				dwarf_tag(current_die, &tag_value, &error);

				if (tag_value == DW_TAG_subprogram ||
					tag_value == DW_TAG_inlined_subroutine) {

					Dwarf_Bool has_attr = 0;
					if (dwarf_hasattr(current_die, DW_AT_specification,
									  &has_attr, &error) == DW_DLV_OK) {
						if (has_attr) {
							Dwarf_Attribute attr_mem;
							if (dwarf_attr(current_die, DW_AT_specification,
											&attr_mem, &error) == DW_DLV_OK) {
								Dwarf_Off spec_offset = 0;
								if (dwarf_formref(attr_mem,
										&spec_offset, &error) == DW_DLV_OK) {
									Dwarf_Off spec_die_offset;
									if (dwarf_dieoffset(current_die,
											&spec_die_offset, &error)
											== DW_DLV_OK) {
										de.spec_section[spec_offset] =
												spec_die_offset;
									}
								}
							}
							dwarf_dealloc(dwarf, attr_mem, DW_DLA_ATTR);
						}
					}
				}

				int result = dwarf_siblingof(
						dwarf, current_die, &sibling_die, &error);
				if (result == DW_DLV_ERROR) {
					break;
				} else if (result == DW_DLV_NO_ENTRY) {
					break;
				}

				if (current_die != die) {
					dwarf_dealloc(dwarf, current_die, DW_DLA_DIE);
					current_die = 0;
				}

				current_die = sibling_die;
			}
		}
		return de;
	}

	static Dwarf_Die get_referenced_die(
			Dwarf_Debug dwarf, Dwarf_Die die, Dwarf_Half attr, bool global) {
		Dwarf_Error error = DW_DLE_NE;
		Dwarf_Attribute attr_mem;

		Dwarf_Die found_die = NULL;
		if (dwarf_attr(die, attr, &attr_mem, &error) == DW_DLV_OK) {
			Dwarf_Off offset;
			int result = 0;
			if (global) {
				result = dwarf_global_formref(attr_mem, &offset, &error);
			} else {
				result = dwarf_formref(attr_mem, &offset, &error);
			}

			if (result == DW_DLV_OK) {
				if (dwarf_offdie(dwarf, offset, &found_die, &error)
						!= DW_DLV_OK) {
					found_die = NULL;
				}
			}
			dwarf_dealloc(dwarf, attr_mem, DW_DLA_ATTR);
		}
		return found_die;
	}

	static std::string get_referenced_die_name(
			Dwarf_Debug dwarf, Dwarf_Die die, Dwarf_Half attr, bool global) {
		Dwarf_Error error = DW_DLE_NE;
		std::string value;

		Dwarf_Die found_die = get_referenced_die(dwarf, die, attr, global);

		if (found_die) {
			char *name;
			if (dwarf_diename(found_die, &name, &error) == DW_DLV_OK) {
				if (name) {
					value = std::string(name);
				}
				dwarf_dealloc(dwarf, name, DW_DLA_STRING);
			}
			dwarf_dealloc(dwarf, found_die, DW_DLA_DIE);
		}

		return value;
	}

	// Returns a spec DIE linked to the passed one. The caller should
	// deallocate the DIE
	static Dwarf_Die get_spec_die(dwarf_fileobject& fobj, Dwarf_Die die) {
		Dwarf_Debug dwarf = fobj.dwarf_handle.get();
		Dwarf_Error error = DW_DLE_NE;
		Dwarf_Off die_offset;
		if (fobj.current_cu && dwarf_die_CU_offset(die, &die_offset, &error)
				== DW_DLV_OK) {
			die_specmap_t::iterator it =
					fobj.current_cu->spec_section.find(die_offset);

			// If we have a DIE that completes the current one, check if
			// that one has the pc we are looking for
			if (it != fobj.current_cu->spec_section.end()) {
				Dwarf_Die spec_die = 0;
				if (dwarf_offdie(dwarf, it->second, &spec_die, &error)
						== DW_DLV_OK) {
					return spec_die;
				}
			}
		}

		// Maybe we have an abstract origin DIE with the function information?
		return get_referenced_die(
				fobj.dwarf_handle.get(), die, DW_AT_abstract_origin, true);

	}

	static bool die_has_pc(dwarf_fileobject& fobj, Dwarf_Die die, Dwarf_Addr pc)
	{
		Dwarf_Addr low_pc = 0, high_pc = 0;
		Dwarf_Half high_pc_form = 0;
		Dwarf_Form_Class return_class;
		Dwarf_Error error = DW_DLE_NE;
		Dwarf_Debug dwarf = fobj.dwarf_handle.get();
		bool has_lowpc = false;
		bool has_highpc = false;
		bool has_ranges = false;

		if (dwarf_lowpc(die, &low_pc, &error) == DW_DLV_OK) {
			// If we have a low_pc check if there is a high pc.
			// If we don't have a high pc this might mean we have a base
			// address for the ranges list or just an address.
			has_lowpc = true;

			if (dwarf_highpc_b(
					die, &high_pc, &high_pc_form, &return_class, &error)
					== DW_DLV_OK) {
				// We do have a high pc. In DWARF 4+ this is an offset from the
				// low pc, but in earlier versions it's an absolute address.

				has_highpc = true;
				// In DWARF 2/3 this would be a DW_FORM_CLASS_ADDRESS
				if (return_class == DW_FORM_CLASS_CONSTANT) {
					high_pc = low_pc + high_pc;
				}

				// We have low and high pc, check if our address
				// is in that range
				return pc >= low_pc && pc < high_pc;
			}
		} else {
			// Reset the low_pc, in case dwarf_lowpc failing set it to some
			// undefined value.
			low_pc = 0;
		}

		// Check if DW_AT_ranges is present and search for the PC in the
		// returned ranges list. We always add the low_pc, as it not set it will
		// be 0, in case we had a DW_AT_low_pc and DW_AT_ranges pair
		bool result = false;

		Dwarf_Attribute attr;
		if (dwarf_attr(die, DW_AT_ranges, &attr, &error) == DW_DLV_OK) {

			Dwarf_Off offset;
			if (dwarf_global_formref(attr, &offset, &error) == DW_DLV_OK) {
				Dwarf_Ranges *ranges;
				Dwarf_Signed ranges_count = 0;
				Dwarf_Unsigned byte_count = 0;

				if (dwarf_get_ranges_a(dwarf, offset, die, &ranges,
						&ranges_count, &byte_count, &error) == DW_DLV_OK) {
					has_ranges = ranges_count != 0;
					for (int i = 0; i < ranges_count; i++) {
						if (ranges[i].dwr_addr1 != 0 &&
							pc >= ranges[i].dwr_addr1 + low_pc &&
							pc < ranges[i].dwr_addr2 + low_pc) {
							result = true;
							break;
						}
					}
					dwarf_ranges_dealloc(dwarf, ranges, ranges_count);
				}
			}
		}

		// Last attempt. We might have a single address set as low_pc.
		if (!result && low_pc != 0 && pc == low_pc) {
			result = true;
		}

		// If we don't have lowpc, highpc and ranges maybe this DIE is a
		// declaration that relies on a DW_AT_specification DIE that happens
		// later. Use the specification cache we filled when we loaded this CU.
		if (!result && (!has_lowpc && !has_highpc && !has_ranges)) {
			Dwarf_Die spec_die = get_spec_die(fobj, die);
			if (spec_die) {
				result = die_has_pc(fobj, spec_die, pc);
				dwarf_dealloc(dwarf, spec_die, DW_DLA_DIE);
			}
		}

		return result;
	}

	static void get_type(Dwarf_Debug dwarf, Dwarf_Die die, std::string& type) {
		Dwarf_Error error = DW_DLE_NE;

		Dwarf_Die child = 0;
		if (dwarf_child(die, &child, &error) == DW_DLV_OK) {
			get_type(dwarf, child, type);
		}

		if (child) {
			type.insert(0, "::");
			dwarf_dealloc(dwarf, child, DW_DLA_DIE);
		}

		char *name;
		if (dwarf_diename(die, &name, &error) == DW_DLV_OK) {
			type.insert(0, std::string(name));
			dwarf_dealloc(dwarf, name, DW_DLA_STRING);
		} else {
			type.insert(0,"<unknown>");
		}
	}

	static std::string get_type_by_signature(Dwarf_Debug dwarf, Dwarf_Die die) {
		Dwarf_Error error = DW_DLE_NE;

		Dwarf_Sig8 signature;
		Dwarf_Bool has_attr = 0;
		if (dwarf_hasattr(die, DW_AT_signature,
						  &has_attr, &error) == DW_DLV_OK) {
			if (has_attr) {
				Dwarf_Attribute attr_mem;
				if (dwarf_attr(die, DW_AT_signature,
								&attr_mem, &error) == DW_DLV_OK) {
					if (dwarf_formsig8(attr_mem, &signature, &error)
							!= DW_DLV_OK) {
						return std::string("<no type signature>");
					}
				}
				dwarf_dealloc(dwarf, attr_mem, DW_DLA_ATTR);
			}
		}

		Dwarf_Unsigned next_cu_header;
		Dwarf_Sig8 tu_signature;
		std::string result;
		bool found = false;

		while (dwarf_next_cu_header_d(dwarf, 0, 0, 0, 0, 0, 0, 0, &tu_signature,
				0, &next_cu_header, 0, &error) == DW_DLV_OK) {

			if (strncmp(signature.signature, tu_signature.signature, 8) == 0) {
				Dwarf_Die type_cu_die = 0;
				if (dwarf_siblingof_b(dwarf, 0, 0, &type_cu_die, &error)
						== DW_DLV_OK) {
					Dwarf_Die child_die = 0;
					if (dwarf_child(type_cu_die, &child_die, &error)
							== DW_DLV_OK) {
						get_type(dwarf, child_die, result);
						found = !result.empty();
						dwarf_dealloc(dwarf, child_die, DW_DLA_DIE);
					}
					dwarf_dealloc(dwarf, type_cu_die, DW_DLA_DIE);
				}
			}
		}

		if (found) {
			while (dwarf_next_cu_header_d(dwarf, 0, 0, 0, 0, 0, 0, 0, 0, 0,
					&next_cu_header, 0, &error) == DW_DLV_OK) {
				// Reset the cu header state. Unfortunately, libdwarf's
				// next_cu_header API keeps its own iterator per Dwarf_Debug
				// that can't be reset. We need to keep fetching elements until
				// the end.
			}
		} else {
			// If we couldn't resolve the type just print out the signature
			std::ostringstream string_stream;
			string_stream << "<0x" <<
					std::hex << std::setfill('0');
			for (int i = 0; i < 8; ++i) {
				string_stream << std::setw(2) << std::hex
						<< (int)(unsigned char)(signature.signature[i]);
			}
			string_stream << ">";
			result = string_stream.str();
		}
		return result;
	}

	struct type_context_t {
		bool is_const;
		bool is_typedef;
		bool has_type;
		bool has_name;
		std::string text;

		type_context_t() :
			is_const(false), is_typedef(false),
			has_type(false), has_name(false) {}
	};

	// Types are resolved from right to left: we get the variable name first
	// and then all specifiers (like const or pointer) in a chain of DW_AT_type
	// DIEs. Call this function recursively until we get a complete type
	// string.
	static void set_parameter_string(
			dwarf_fileobject& fobj, Dwarf_Die die, type_context_t &context) {
		char *name;
		Dwarf_Error error = DW_DLE_NE;

		// typedefs contain also the base type, so we skip it and only
		// print the typedef name
		if (!context.is_typedef) {
			if (dwarf_diename(die, &name, &error) == DW_DLV_OK) {
				if (!context.text.empty()) {
					context.text.insert(0, " ");
				}
				context.text.insert(0, std::string(name));
				dwarf_dealloc(fobj.dwarf_handle.get(), name, DW_DLA_STRING);
			}
		} else {
			context.is_typedef = false;
			context.has_type = true;
			if (context.is_const) {
				context.text.insert(0, "const ");
				context.is_const = false;
			}
		}

		bool next_type_is_const = false;
		bool is_keyword = true;

		Dwarf_Half tag = 0;
		Dwarf_Bool has_attr = 0;
		if (dwarf_tag(die, &tag, &error) == DW_DLV_OK) {
			switch(tag) {
			case DW_TAG_structure_type:
			case DW_TAG_union_type:
			case DW_TAG_class_type:
			case DW_TAG_enumeration_type:
				context.has_type = true;
				if (dwarf_hasattr(die, DW_AT_signature,
								  &has_attr, &error) == DW_DLV_OK) {
					// If we have a signature it means the type is defined
					// in .debug_types, so we need to load the DIE pointed
					// at by the signature and resolve it
					if (has_attr) {
						std::string type =
							get_type_by_signature(fobj.dwarf_handle.get(), die);
						if (context.is_const)
							type.insert(0, "const ");

						if (!context.text.empty())
							context.text.insert(0, " ");
						context.text.insert(0, type);
					}

					// Treat enums like typedefs, and skip printing its
					// base type
					context.is_typedef = (tag == DW_TAG_enumeration_type);
				}
				break;
			case DW_TAG_const_type:
				next_type_is_const = true;
				break;
			case DW_TAG_pointer_type:
				context.text.insert(0, "*");
				break;
			case DW_TAG_reference_type:
				context.text.insert(0, "&");
				break;
			case DW_TAG_restrict_type:
				context.text.insert(0, "restrict ");
				break;
			case DW_TAG_rvalue_reference_type:
				context.text.insert(0, "&&");
				break;
			case DW_TAG_volatile_type:
				context.text.insert(0, "volatile ");
				break;
			case DW_TAG_typedef:
				// Propagate the const-ness to the next type
				// as typedefs are linked to its base type
				next_type_is_const = context.is_const;
				context.is_typedef = true;
				context.has_type = true;
				break;
			case DW_TAG_base_type:
				context.has_type = true;
				break;
			case DW_TAG_formal_parameter:
				context.has_name = true;
				break;
			default:
				is_keyword = false;
				break;
			}
		}

		if (!is_keyword && context.is_const) {
			context.text.insert(0, "const ");
		}

		context.is_const = next_type_is_const;

		Dwarf_Die ref = get_referenced_die(
				fobj.dwarf_handle.get(), die, DW_AT_type, true);
		if (ref) {
			set_parameter_string(fobj, ref, context);
			dwarf_dealloc(fobj.dwarf_handle.get(), ref, DW_DLA_DIE);
		}

		if (!context.has_type && context.has_name) {
			context.text.insert(0, "void ");
			context.has_type = true;
		}
	}

	// Resolve the function return type and parameters
	static void set_function_parameters(std::string& function_name,
										std::vector<std::string>& ns,
										dwarf_fileobject& fobj, Dwarf_Die die) {
		Dwarf_Debug dwarf = fobj.dwarf_handle.get();
		Dwarf_Error error = DW_DLE_NE;
		Dwarf_Die current_die = 0;
		std::string parameters;
		bool has_spec = true;
		// Check if we have a spec DIE. If we do we use it as it contains
		// more information, like parameter names.
		Dwarf_Die spec_die = get_spec_die(fobj, die);
		if (!spec_die) {
			has_spec = false;
			spec_die = die;
		}

		std::vector<std::string>::const_iterator it = ns.begin();
		std::string ns_name;
		for (it = ns.begin(); it < ns.end(); ++it) {
			ns_name.append(*it).append("::");
		}

		if (!ns_name.empty()) {
			function_name.insert(0, ns_name);
		}

		// See if we have a function return type. It can be either on the
		// current die or in its spec one (usually true for inlined functions)
		std::string return_type =
				get_referenced_die_name(dwarf, die, DW_AT_type, true);
		if (return_type.empty()) {
			return_type =
				get_referenced_die_name(dwarf, spec_die, DW_AT_type, true);
		}
		if (!return_type.empty()) {
			return_type.append(" ");
			function_name.insert(0, return_type);
		}

		if (dwarf_child(spec_die, &current_die, &error) == DW_DLV_OK) {
			for(;;) {
				Dwarf_Die sibling_die = 0;

				Dwarf_Half tag_value;
				dwarf_tag(current_die, &tag_value, &error);

				if (tag_value == DW_TAG_formal_parameter) {
					// Ignore artificial (ie, compiler generated) parameters
					bool is_artificial = false;
					Dwarf_Attribute attr_mem;
					if (dwarf_attr(
							current_die, DW_AT_artificial, &attr_mem, &error)
							== DW_DLV_OK) {
						Dwarf_Bool flag = 0;
						if (dwarf_formflag(attr_mem, &flag, &error)
								== DW_DLV_OK) {
							is_artificial = flag != 0;
						}
						dwarf_dealloc(dwarf, attr_mem, DW_DLA_ATTR);
					}

					if (!is_artificial) {
						type_context_t context;
						set_parameter_string(fobj, current_die, context);

						if (parameters.empty()) {
							parameters.append("(");
						} else {
							parameters.append(", ");
						}
						parameters.append(context.text);
					}
				}

				int result = dwarf_siblingof(
						dwarf, current_die, &sibling_die, &error);
				if (result == DW_DLV_ERROR) {
					break;
				} else if (result == DW_DLV_NO_ENTRY) {
					break;
				}

				if (current_die != die) {
					dwarf_dealloc(dwarf, current_die, DW_DLA_DIE);
					current_die = 0;
				}

				current_die = sibling_die;
			}
		}
		if (parameters.empty())
			parameters = "(";
		parameters.append(")");

		// If we got a spec DIE we need to deallocate it
		if (has_spec)
			dwarf_dealloc(dwarf, spec_die, DW_DLA_DIE);

		function_name.append(parameters);
	}

	// defined here because in C++98, template function cannot take locally
	// defined types... grrr.
	struct inliners_search_cb {
		void operator()(Dwarf_Die die, std::vector<std::string>& ns) {
			Dwarf_Error error = DW_DLE_NE;
			Dwarf_Half tag_value;
			Dwarf_Attribute attr_mem;
			Dwarf_Debug dwarf = fobj.dwarf_handle.get();

			dwarf_tag(die, &tag_value, &error);

			switch (tag_value) {
				char* name;
				case DW_TAG_subprogram:
					if (!trace.source.function.empty())
						break;
					if (dwarf_diename(die, &name, &error) == DW_DLV_OK) {
						trace.source.function = std::string(name);
						dwarf_dealloc(dwarf, name, DW_DLA_STRING);
					} else {
						// We don't have a function name in this DIE.
						// Check if there is a referenced non-defining
						// declaration.
						trace.source.function = get_referenced_die_name(
								dwarf, die, DW_AT_abstract_origin, true);
						if (trace.source.function.empty()) {
							trace.source.function = get_referenced_die_name(
									dwarf, die, DW_AT_specification, true);
						}
					}

					// Append the function parameters, if available
					set_function_parameters(
							trace.source.function, ns, fobj, die);

					// If the object function name is empty, it's possible that
					// there is no dynamic symbol table (maybe the executable
					// was stripped or not built with -rdynamic). See if we have
					// a DWARF linkage name to use instead. We try both
					// linkage_name and MIPS_linkage_name because the MIPS tag
					// was the unofficial one until it was adopted in DWARF4.
					// Old gcc versions generate MIPS_linkage_name
					if (trace.object_function.empty()) {
						details::demangler demangler;

						if (dwarf_attr(die, DW_AT_linkage_name,
								&attr_mem, &error) != DW_DLV_OK) {
							if (dwarf_attr(die, DW_AT_MIPS_linkage_name,
									&attr_mem, &error) != DW_DLV_OK) {
								break;
							}
						}

						char* linkage;
						if (dwarf_formstring(attr_mem, &linkage, &error)
								== DW_DLV_OK) {
							trace.object_function = demangler.demangle(linkage);
							dwarf_dealloc(dwarf, linkage, DW_DLA_STRING);
						}
						dwarf_dealloc(dwarf, name, DW_DLA_ATTR);
					}
					break;

				case DW_TAG_inlined_subroutine:
					ResolvedTrace::SourceLoc sloc;

					if (dwarf_diename(die, &name, &error) == DW_DLV_OK) {
						sloc.function = std::string(name);
						dwarf_dealloc(dwarf, name, DW_DLA_STRING);
					} else {
						// We don't have a name for this inlined DIE, it could
						// be that there is an abstract origin instead.
						// Get the DW_AT_abstract_origin value, which is a
						// reference to the source DIE and try to get its name
						sloc.function = get_referenced_die_name(
								dwarf, die, DW_AT_abstract_origin, true);
					}

					set_function_parameters(sloc.function, ns, fobj, die);

					std::string file = die_call_file(dwarf, die, cu_die);
					if (!file.empty())
						sloc.filename = file;

					Dwarf_Unsigned number = 0;
					if (dwarf_attr(die, DW_AT_call_line, &attr_mem, &error)
							== DW_DLV_OK) {
						if (dwarf_formudata(attr_mem, &number, &error)
								== DW_DLV_OK) {
							sloc.line = number;
						}
						dwarf_dealloc(dwarf, attr_mem, DW_DLA_ATTR);
					}

					if (dwarf_attr(die, DW_AT_call_column, &attr_mem, &error)
							== DW_DLV_OK) {
						if (dwarf_formudata(attr_mem, &number, &error)
								== DW_DLV_OK) {
							sloc.col = number;
						}
						dwarf_dealloc(dwarf, attr_mem, DW_DLA_ATTR);
					}

					trace.inliners.push_back(sloc);
					break;
			};
		}
		ResolvedTrace& trace;
		dwarf_fileobject& fobj;
		Dwarf_Die cu_die;
		inliners_search_cb(ResolvedTrace& t, dwarf_fileobject& f, Dwarf_Die c)
			: trace(t), fobj(f), cu_die(c) {}
	};

	static Dwarf_Die find_fundie_by_pc(dwarf_fileobject& fobj,
					Dwarf_Die parent_die, Dwarf_Addr pc, Dwarf_Die result) {
		Dwarf_Die current_die = 0;
		Dwarf_Error error = DW_DLE_NE;
		Dwarf_Debug dwarf = fobj.dwarf_handle.get();

		if (dwarf_child(parent_die, &current_die, &error) != DW_DLV_OK) {
			return NULL;
		}

		for(;;) {
			Dwarf_Die sibling_die = 0;
			Dwarf_Half tag_value;
			dwarf_tag(current_die, &tag_value, &error);

			switch (tag_value) {
				case DW_TAG_subprogram:
				case DW_TAG_inlined_subroutine:
					if (die_has_pc(fobj, current_die, pc)) {
						return current_die;
					}
			};
			bool declaration = false;
			Dwarf_Attribute attr_mem;
			if (dwarf_attr(current_die, DW_AT_declaration, &attr_mem, &error)
					== DW_DLV_OK) {
				Dwarf_Bool flag = 0;
				if (dwarf_formflag(attr_mem, &flag, &error) == DW_DLV_OK) {
					declaration = flag != 0;
				}
				dwarf_dealloc(dwarf, attr_mem, DW_DLA_ATTR);
			}

			if (!declaration) {
				// let's be curious and look deeper in the tree, functions are
				// not necessarily at the first level, but might be nested
				// inside a namespace, structure, a function, an inlined
				// function etc.
				Dwarf_Die die_mem = 0;
				Dwarf_Die indie = find_fundie_by_pc(
						fobj, current_die, pc, die_mem);
				if (indie) {
					result = die_mem;
					return result;
				}
			}

			int res = dwarf_siblingof(
					dwarf, current_die, &sibling_die, &error);
			if (res == DW_DLV_ERROR) {
				return NULL;
			} else if (res == DW_DLV_NO_ENTRY) {
				break;
			}

			if (current_die != parent_die) {
				dwarf_dealloc(dwarf, current_die, DW_DLA_DIE);
				current_die = 0;
			}

			current_die = sibling_die;
		}
		return NULL;
	}

	template <typename CB>
		static bool deep_first_search_by_pc(dwarf_fileobject& fobj,
						Dwarf_Die parent_die, Dwarf_Addr pc,
						std::vector<std::string>& ns, CB cb) {
		Dwarf_Die current_die = 0;
		Dwarf_Debug dwarf = fobj.dwarf_handle.get();
		Dwarf_Error error = DW_DLE_NE;

		if (dwarf_child(parent_die, &current_die, &error) != DW_DLV_OK) {
			return false;
		}

		bool branch_has_pc = false;
		bool has_namespace = false;
		for(;;) {
			Dwarf_Die sibling_die = 0;

			Dwarf_Half tag;
			if (dwarf_tag(current_die, &tag, &error) == DW_DLV_OK) {
				if (tag == DW_TAG_namespace || tag == DW_TAG_class_type) {
					char* ns_name = NULL;
					if (dwarf_diename(current_die, &ns_name, &error)
							== DW_DLV_OK) {
						if (ns_name) {
							ns.push_back(std::string(ns_name));
						} else {
							ns.push_back("<unknown>");
						}
						dwarf_dealloc(dwarf, ns_name,  DW_DLA_STRING);
					} else {
						ns.push_back("<unknown>");
					}
					has_namespace = true;
				}
			}

			bool declaration = false;
			Dwarf_Attribute attr_mem;
			if (tag != DW_TAG_class_type &&
				dwarf_attr(current_die, DW_AT_declaration, &attr_mem, &error)
					== DW_DLV_OK) {
				Dwarf_Bool flag = 0;
				if (dwarf_formflag(attr_mem, &flag, &error) == DW_DLV_OK) {
					declaration = flag != 0;
				}
				dwarf_dealloc(dwarf, attr_mem, DW_DLA_ATTR);
			}

			if (!declaration) {
				// let's be curious and look deeper in the tree, function are
				// not necessarily at the first level, but might be nested
				// inside a namespace, structure, a function, an inlined
				// function etc.
				branch_has_pc = deep_first_search_by_pc(
												fobj, current_die, pc, ns, cb);
			}

			if (!branch_has_pc) {
				branch_has_pc = die_has_pc(fobj, current_die, pc);
			}

			if (branch_has_pc) {
				cb(current_die, ns);
			}

			int result = dwarf_siblingof(
					dwarf, current_die, &sibling_die, &error);
			if (result == DW_DLV_ERROR) {
				return false;
			} else if (result == DW_DLV_NO_ENTRY) {
				break;
			}

			if (current_die != parent_die) {
				dwarf_dealloc(dwarf, current_die, DW_DLA_DIE);
				current_die = 0;
			}

			if (has_namespace) {
				has_namespace = false;
				ns.pop_back();
			}
			current_die = sibling_die;
		}

		if (has_namespace) {
			ns.pop_back();
		}
		return branch_has_pc;
	}

	static std::string die_call_file(
			Dwarf_Debug dwarf, Dwarf_Die die, Dwarf_Die cu_die) {
		Dwarf_Attribute attr_mem;
		Dwarf_Error error = DW_DLE_NE;
		Dwarf_Signed file_index;

		std::string file;

		if (dwarf_attr(die, DW_AT_call_file, &attr_mem, &error) == DW_DLV_OK) {
			if (dwarf_formsdata(attr_mem, &file_index, &error) != DW_DLV_OK) {
				file_index = 0;
			}
			dwarf_dealloc(dwarf, attr_mem, DW_DLA_ATTR);

			if (file_index == 0) {
				return file;
			}

			char **srcfiles = 0;
			Dwarf_Signed file_count = 0;
			if (dwarf_srcfiles(cu_die, &srcfiles, &file_count, &error)
					== DW_DLV_OK) {
				if (file_index <= file_count)
					file = std::string(srcfiles[file_index - 1]);

				// Deallocate all strings!
				for (int i = 0; i < file_count; ++i) {
					dwarf_dealloc(dwarf, srcfiles[i], DW_DLA_STRING);
				}
				dwarf_dealloc(dwarf, srcfiles, DW_DLA_LIST);
			}
		}
		return file;
	}


	Dwarf_Die find_die(dwarf_fileobject& fobj, Dwarf_Addr addr)
	{
		// Let's get to work! First see if we have a debug_aranges section so
		// we can speed up the search

		Dwarf_Debug dwarf = fobj.dwarf_handle.get();
		Dwarf_Error error = DW_DLE_NE;
		Dwarf_Arange *aranges;
		Dwarf_Signed arange_count;

		Dwarf_Die returnDie;
		bool found = false;
		if (dwarf_get_aranges(
				dwarf, &aranges, &arange_count, &error) != DW_DLV_OK) {
			aranges = NULL;
		}

		if (aranges) {
			// We have aranges. Get the one where our address is.
			Dwarf_Arange arange;
			if (dwarf_get_arange(
					aranges, arange_count, addr, &arange, &error)
						== DW_DLV_OK) {

				// We found our address. Get the compilation-unit DIE offset
				// represented by the given address range.
				Dwarf_Off cu_die_offset;
				if (dwarf_get_cu_die_offset(arange, &cu_die_offset, &error)
						== DW_DLV_OK) {
					// Get the DIE at the offset returned by the aranges search.
					// We set is_info to 1 to specify that the offset is from
					// the .debug_info section (and not .debug_types)
					int dwarf_result = dwarf_offdie_b(
							dwarf, cu_die_offset, 1, &returnDie, &error);

					found = dwarf_result == DW_DLV_OK;
				}
				dwarf_dealloc(dwarf, arange, DW_DLA_ARANGE);
			}
		}

		if (found)
			return returnDie; // The caller is responsible for freeing the die

		// The search for aranges failed. Try to find our address by scanning
		// all compilation units.
		Dwarf_Unsigned next_cu_header;
		Dwarf_Half tag = 0;
		returnDie = 0;

		while (!found && dwarf_next_cu_header_d(dwarf, 1, 0, 0, 0, 0, 0, 0, 0, 0,
				&next_cu_header, 0, &error) == DW_DLV_OK) {

			if (returnDie)
				dwarf_dealloc(dwarf, returnDie, DW_DLA_DIE);

			if (dwarf_siblingof(dwarf, 0, &returnDie, &error) == DW_DLV_OK) {
				if ((dwarf_tag(returnDie, &tag, &error) == DW_DLV_OK)
					&& tag == DW_TAG_compile_unit) {
					if (die_has_pc(fobj, returnDie, addr)) {
						found = true;
					}
                }
			}
		}

		if (found) {
			while (dwarf_next_cu_header_d(dwarf, 1, 0, 0, 0, 0, 0, 0, 0, 0,
					&next_cu_header, 0, &error) == DW_DLV_OK) {
				// Reset the cu header state. Libdwarf's next_cu_header API
				// keeps its own iterator per Dwarf_Debug that can't be reset.
				// We need to keep fetching elements until the end.
			}
		}

		if (found)
			return returnDie;

		// We couldn't find any compilation units with ranges or a high/low pc.
		// Try again by looking at all DIEs in all compilation units.
		Dwarf_Die cudie;
		while (dwarf_next_cu_header_d(dwarf, 1, 0, 0, 0, 0, 0, 0, 0, 0,
				&next_cu_header, 0, &error) == DW_DLV_OK) {
			if (dwarf_siblingof(dwarf, 0, &cudie, &error) == DW_DLV_OK) {
				Dwarf_Die die_mem = 0;
				Dwarf_Die resultDie = find_fundie_by_pc(
						fobj, cudie, addr, die_mem);

				if (resultDie) {
					found = true;
					break;
				}
			}
		}

		if (found) {
			while (dwarf_next_cu_header_d(dwarf, 1, 0, 0, 0, 0, 0, 0, 0, 0,
					&next_cu_header, 0, &error) == DW_DLV_OK) {
				// Reset the cu header state. Libdwarf's next_cu_header API
				// keeps its own iterator per Dwarf_Debug that can't be reset.
				// We need to keep fetching elements until the end.
			}
		}

		if (found)
			return cudie;

		// We failed.
		return NULL;
	}
};
#endif // BACKWARD_HAS_DWARF == 1

template<>
class TraceResolverImpl<system_tag::linux_tag>:
	public TraceResolverLinuxImpl<trace_resolver_tag::current> {};

#endif // BACKWARD_SYSTEM_LINUX

#ifdef BACKWARD_SYSTEM_DARWIN

template <typename STACKTRACE_TAG>
class TraceResolverDarwinImpl;

template <>
class TraceResolverDarwinImpl<trace_resolver_tag::backtrace_symbol>:
	public TraceResolverImplBase {
public:
	template <class ST>
		void load_stacktrace(ST& st) {
			using namespace details;
			if (st.size() == 0) {
				return;
			}
			_symbols.reset(
					backtrace_symbols(st.begin(), st.size())
					);
		}

	ResolvedTrace resolve(ResolvedTrace trace) {
		// parse:
		// <n>  <file>  <addr>  <mangled-name> + <offset>
		char* filename = _symbols[trace.idx];

		// skip "<n>  "
		while(*filename && *filename != ' ') filename++;
		while(*filename == ' ') filename++;

		// find start of <mangled-name> from end (<file> may contain a space)
		char* p = filename + strlen(filename) - 1;
		// skip to start of " + <offset>"
		while(p > filename && *p != ' ') p--;
		while(p > filename && *p == ' ') p--;
		while(p > filename && *p != ' ') p--;
		while(p > filename && *p == ' ') p--;
		char *funcname_end = p + 1;

		// skip to start of "<manged-name>"
		while(p > filename && *p != ' ') p--;
		char *funcname = p + 1;

		// skip to start of "  <addr>  "
		while(p > filename && *p == ' ') p--;
		while(p > filename && *p != ' ') p--;
		while(p > filename && *p == ' ') p--;

		// skip "<file>", handling the case where it contains a
		char* filename_end = p + 1;
		if (p == filename) {
			// something went wrong, give up
			filename_end = filename + strlen(filename);
			funcname = filename_end;
		}
		trace.object_filename.assign(filename, filename_end); // ok even if filename_end is the ending \0 (then we assign entire string)

		if (*funcname) { // if it's not end of string
			*funcname_end = '\0';

			trace.object_function = this->demangle(funcname);
			trace.object_function += " ";
			trace.object_function += (funcname_end + 1);
			trace.source.function = trace.object_function; // we cannot do better.
		}
		return trace;
	}

private:
	details::handle<char**> _symbols;
};

template<>
class TraceResolverImpl<system_tag::darwin_tag>:
	public TraceResolverDarwinImpl<trace_resolver_tag::current> {};

#endif // BACKWARD_SYSTEM_DARWIN

class TraceResolver:
	public TraceResolverImpl<system_tag::current_tag> {};

/*************** CODE SNIPPET ***************/

class SourceFile {
public:
	typedef std::vector<std::pair<unsigned, std::string> > lines_t;

	SourceFile() {}
	SourceFile(const std::string& path): _file(new std::ifstream(path.c_str())) {}
	bool is_open() const { return _file->is_open(); }

	lines_t& get_lines(unsigned line_start, unsigned line_count, lines_t& lines) {
		using namespace std;
		// This function make uses of the dumbest algo ever:
		//	1) seek(0)
		//	2) read lines one by one and discard until line_start
		//	3) read line one by one until line_start + line_count
		//
		// If you are getting snippets many time from the same file, it is
		// somewhat a waste of CPU, feel free to benchmark and propose a
		// better solution ;)

		_file->clear();
		_file->seekg(0);
		string line;
		unsigned line_idx;

		for (line_idx = 1; line_idx < line_start; ++line_idx) {
			std::getline(*_file, line);
			if (!*_file) {
				return lines;
			}
		}

		// think of it like a lambda in C++98 ;)
		// but look, I will reuse it two times!
		// What a good boy am I.
		struct isspace {
			bool operator()(char c) {
				return std::isspace(c);
			}
		};

		bool started = false;
		for (; line_idx < line_start + line_count; ++line_idx) {
			getline(*_file, line);
			if (!*_file) {
				return lines;
			}
			if (!started) {
				if (std::find_if(line.begin(), line.end(),
							not_isspace()) == line.end())
					continue;
				started = true;
			}
			lines.push_back(make_pair(line_idx, line));
		}

		lines.erase(
				std::find_if(lines.rbegin(), lines.rend(),
					not_isempty()).base(), lines.end()
				);
		return lines;
	}

	lines_t get_lines(unsigned line_start, unsigned line_count) {
		lines_t lines;
		return get_lines(line_start, line_count, lines);
	}

	// there is no find_if_not in C++98, lets do something crappy to
	// workaround.
	struct not_isspace {
		bool operator()(char c) {
			return !std::isspace(c);
		}
	};
	// and define this one here because C++98 is not happy with local defined
	// struct passed to template functions, fuuuu.
	struct not_isempty {
		bool operator()(const lines_t::value_type& p) {
			return !(std::find_if(p.second.begin(), p.second.end(),
						not_isspace()) == p.second.end());
		}
	};

	void swap(SourceFile& b) {
		_file.swap(b._file);
	}

#ifdef BACKWARD_ATLEAST_CXX11
	SourceFile(SourceFile&& from): _file(nullptr) {
		swap(from);
	}
	SourceFile& operator=(SourceFile&& from) {
		swap(from); return *this;
	}
#else
	explicit SourceFile(const SourceFile& from) {
		// some sort of poor man's move semantic.
		swap(const_cast<SourceFile&>(from));
	}
	SourceFile& operator=(const SourceFile& from) {
		// some sort of poor man's move semantic.
		swap(const_cast<SourceFile&>(from)); return *this;
	}
#endif

private:
	details::handle<std::ifstream*,
		details::default_delete<std::ifstream*>
			> _file;

#ifdef BACKWARD_ATLEAST_CXX11
	SourceFile(const SourceFile&) = delete;
	SourceFile& operator=(const SourceFile&) = delete;
#endif
};

class SnippetFactory {
public:
	typedef SourceFile::lines_t lines_t;

	lines_t get_snippet(const std::string& filename,
			unsigned line_start, unsigned context_size) {

		SourceFile& src_file = get_src_file(filename);
		unsigned start = line_start - context_size / 2;
		return src_file.get_lines(start, context_size);
	}

	lines_t get_combined_snippet(
			const std::string& filename_a, unsigned line_a,
			const std::string& filename_b, unsigned line_b,
			unsigned context_size) {
		SourceFile& src_file_a = get_src_file(filename_a);
		SourceFile& src_file_b = get_src_file(filename_b);

		lines_t lines = src_file_a.get_lines(line_a - context_size / 4,
				context_size / 2);
		src_file_b.get_lines(line_b - context_size / 4, context_size / 2,
				lines);
		return lines;
	}

	lines_t get_coalesced_snippet(const std::string& filename,
			unsigned line_a, unsigned line_b, unsigned context_size) {
		SourceFile& src_file = get_src_file(filename);

		using std::min; using std::max;
		unsigned a = min(line_a, line_b);
		unsigned b = max(line_a, line_b);

		if ((b - a) < (context_size / 3)) {
			return src_file.get_lines((a + b - context_size + 1) / 2,
					context_size);
		}

		lines_t lines = src_file.get_lines(a - context_size / 4,
				context_size / 2);
		src_file.get_lines(b - context_size / 4, context_size / 2, lines);
		return lines;
	}


private:
	typedef details::hashtable<std::string, SourceFile>::type src_files_t;
	src_files_t _src_files;

	SourceFile& get_src_file(const std::string& filename) {
		src_files_t::iterator it = _src_files.find(filename);
		if (it != _src_files.end()) {
			return it->second;
		}
		SourceFile& new_src_file = _src_files[filename];
		new_src_file = SourceFile(filename);
		return new_src_file;
	}
};

/*************** PRINTER ***************/

namespace ColorMode {
	enum type {
		automatic,
		never,
		always
	};
}

class cfile_streambuf: public std::streambuf {
public:
	cfile_streambuf(FILE *_sink): sink(_sink) {}
	int_type underflow() override { return traits_type::eof(); }
	int_type overflow(int_type ch) override {
		if (traits_type::not_eof(ch) && fwrite(&ch, sizeof ch, 1, sink) == 1) {
				return ch;
		}
		return traits_type::eof();
	}

	std::streamsize xsputn(const char_type* s, std::streamsize count) override {
		return static_cast<std::streamsize>(fwrite(s, sizeof *s, static_cast<size_t>(count), sink));
	}

#ifdef BACKWARD_ATLEAST_CXX11
public:
	cfile_streambuf(const cfile_streambuf&) = delete;
	cfile_streambuf& operator=(const cfile_streambuf&) = delete;
#else
private:
	cfile_streambuf(const cfile_streambuf &);
	cfile_streambuf &operator= (const cfile_streambuf &);
#endif

private:
	FILE *sink;
	std::vector<char> buffer;
};

#ifdef BACKWARD_SYSTEM_LINUX

namespace Color {
	enum type {
		yellow = 33,
		purple = 35,
		reset  = 39
	};
} // namespace Color

class Colorize {
public:
	Colorize(std::ostream& os):
		_os(os), _reset(false), _enabled(false) {}

	void activate(ColorMode::type mode) {
		_enabled = mode == ColorMode::always;
	}

	void activate(ColorMode::type mode, FILE* fp) {
		activate(mode, fileno(fp));
	}

	void set_color(Color::type ccode) {
		if (!_enabled) return;

		// I assume that the terminal can handle basic colors. Seriously I
		// don't want to deal with all the termcap shit.
		_os << "\033[" << static_cast<int>(ccode) << "m";
		_reset = (ccode != Color::reset);
	}

	~Colorize() {
		if (_reset) {
			set_color(Color::reset);
		}
	}

private:
	void activate(ColorMode::type mode, int fd) {
		activate(mode == ColorMode::automatic && isatty(fd) ? ColorMode::always : mode);
	}

	std::ostream& _os;
	bool          _reset;
	bool          _enabled;
};

#else // ndef BACKWARD_SYSTEM_LINUX

namespace Color {
	enum type {
		yellow = 0,
		purple = 0,
		reset  = 0
	};
} // namespace Color

class Colorize {
public:
	Colorize(std::ostream&) {}
	void activate(ColorMode::type) {}
	void activate(ColorMode::type, FILE*) {}
	void set_color(Color::type) {}
};

#endif // BACKWARD_SYSTEM_LINUX

class Printer {
public:

	bool snippet;
	ColorMode::type color_mode;
	bool address;
	bool object;
	int inliner_context_size;
	int trace_context_size;

	Printer():
		snippet(true),
		color_mode(ColorMode::automatic),
		address(false),
		object(false),
		inliner_context_size(5),
		trace_context_size(7)
		{}

	template <typename ST>
		FILE* print(ST& st, FILE* fp = stderr) {
			cfile_streambuf obuf(fp);
			std::ostream os(&obuf);
			Colorize colorize(os);
			colorize.activate(color_mode, fp);
			print_stacktrace(st, os, colorize);
			return fp;
		}

	template <typename ST>
		std::ostream& print(ST& st, std::ostream& os) {
			Colorize colorize(os);
			colorize.activate(color_mode);
			print_stacktrace(st, os, colorize);
			return os;
		}

	template <typename IT>
		FILE* print(IT begin, IT end, FILE* fp = stderr, size_t thread_id = 0) {
			cfile_streambuf obuf(fp);
			std::ostream os(&obuf);
			Colorize colorize(os);
			colorize.activate(color_mode, fp);
			print_stacktrace(begin, end, os, thread_id, colorize);
			return fp;
		}

	template <typename IT>
		std::ostream& print(IT begin, IT end, std::ostream& os, size_t thread_id = 0) {
			Colorize colorize(os);
			colorize.activate(color_mode);
			print_stacktrace(begin, end, os, thread_id, colorize);
			return os;
		}

private:
	TraceResolver  _resolver;
	SnippetFactory _snippets;

	template <typename ST>
		void print_stacktrace(ST& st, std::ostream& os, Colorize& colorize) {
			print_header(os, st.thread_id());
			_resolver.load_stacktrace(st);
			for (size_t trace_idx = st.size(); trace_idx > 0; --trace_idx) {
				print_trace(os, _resolver.resolve(st[trace_idx-1]), colorize);
			}
		}

	template <typename IT>
		void print_stacktrace(IT begin, IT end, std::ostream& os, size_t thread_id, Colorize& colorize) {
			print_header(os, thread_id);
			for (; begin != end; ++begin) {
				print_trace(os, *begin, colorize);
			}
		}

	void print_header(std::ostream& os, size_t thread_id) {
		os << "Stack trace (most recent call last)";
		if (thread_id) {
			os << " in thread " << thread_id;
		}
		os << ":\n";
	}

	void print_trace(std::ostream& os, const ResolvedTrace& trace,
			Colorize& colorize) {
		os << "#"
		   << std::left << std::setw(2) << trace.idx
		   << std::right;
		bool already_indented = true;

		if (!trace.source.filename.size() || object) {
			os << "   Object \""
			   << trace.object_filename
			   << "\", at "
			   << trace.addr
			   << ", in "
			   << trace.object_function
			   << "\n";
			already_indented = false;
		}

		for (size_t inliner_idx = trace.inliners.size();
				inliner_idx > 0; --inliner_idx) {
			if (!already_indented) {
				os << "   ";
			}
			const ResolvedTrace::SourceLoc& inliner_loc
				= trace.inliners[inliner_idx-1];
			print_source_loc(os, " | ", inliner_loc);
			if (snippet) {
				print_snippet(os, "    | ", inliner_loc,
						colorize, Color::purple, inliner_context_size);
			}
			already_indented = false;
		}

		if (trace.source.filename.size()) {
			if (!already_indented) {
				os << "   ";
			}
			print_source_loc(os, "   ", trace.source, trace.addr);
			if (snippet) {
				print_snippet(os, "      ", trace.source,
						colorize, Color::yellow, trace_context_size);
			}
		}
	}

	void print_snippet(std::ostream& os, const char* indent,
			const ResolvedTrace::SourceLoc& source_loc,
			Colorize& colorize, Color::type color_code,
			int context_size)
	{
		using namespace std;
		typedef SnippetFactory::lines_t lines_t;

		lines_t lines = _snippets.get_snippet(source_loc.filename,
				source_loc.line, static_cast<unsigned>(context_size));

		for (lines_t::const_iterator it = lines.begin();
				it != lines.end(); ++it) {
			if (it-> first == source_loc.line) {
				colorize.set_color(color_code);
				os << indent << ">";
			} else {
				os << indent << " ";
			}
			os << std::setw(4) << it->first
			   << ": "
			   << it->second
			   << "\n";
			if (it-> first == source_loc.line) {
				colorize.set_color(Color::reset);
			}
		}
	}

	void print_source_loc(std::ostream& os, const char* indent,
			const ResolvedTrace::SourceLoc& source_loc,
			void* addr=nullptr) {
		os << indent
		   << "Source \""
		   << source_loc.filename
		   << "\", line "
		   << source_loc.line
		   << ", in "
		   << source_loc.function;

		if (address && addr != nullptr) {
			os << " [" << addr << "]";
		}
		os << "\n";
	}
};

/*************** SIGNALS HANDLING ***************/

#if defined(BACKWARD_SYSTEM_LINUX) || defined(BACKWARD_SYSTEM_DARWIN)


class SignalHandling {
public:
   static std::vector<int> make_default_signals() {
       const int posix_signals[] = {
		// Signals for which the default action is "Core".
		SIGABRT,    // Abort signal from abort(3)
		SIGBUS,     // Bus error (bad memory access)
		SIGFPE,     // Floating point exception
		SIGILL,     // Illegal Instruction
		SIGIOT,     // IOT trap. A synonym for SIGABRT
		SIGQUIT,    // Quit from keyboard
		SIGSEGV,    // Invalid memory reference
		SIGSYS,     // Bad argument to routine (SVr4)
		SIGTRAP,    // Trace/breakpoint trap
		SIGXCPU,    // CPU time limit exceeded (4.2BSD)
		SIGXFSZ,    // File size limit exceeded (4.2BSD)
#if defined(BACKWARD_SYSTEM_DARWIN)
		SIGEMT,     // emulation instruction executed
#endif
	};
        return std::vector<int>(posix_signals, posix_signals + sizeof posix_signals / sizeof posix_signals[0] );
   }

  SignalHandling(const std::vector<int>& posix_signals = make_default_signals()):
	  _loaded(false) {
		bool success = true;

		const size_t stack_size = 1024 * 1024 * 8;
		_stack_content.reset(static_cast<char*>(malloc(stack_size)));
		if (_stack_content) {
			stack_t ss;
			ss.ss_sp = _stack_content.get();
			ss.ss_size = stack_size;
			ss.ss_flags = 0;
			if (sigaltstack(&ss, nullptr) < 0) {
				success = false;
			}
		} else {
			success = false;
		}

		for (size_t i = 0; i < posix_signals.size(); ++i) {
			struct sigaction action;
			memset(&action, 0, sizeof action);
			action.sa_flags = static_cast<int>(SA_SIGINFO | SA_ONSTACK | SA_NODEFER |
					SA_RESETHAND);
			sigfillset(&action.sa_mask);
			sigdelset(&action.sa_mask, posix_signals[i]);
#if defined(__clang__)
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wdisabled-macro-expansion"
#endif
			action.sa_sigaction = &sig_handler;
#if defined(__clang__)
#pragma clang diagnostic pop
#endif

			int r = sigaction(posix_signals[i], &action, nullptr);
			if (r < 0) success = false;
		}

		_loaded = success;
	}

	bool loaded() const { return _loaded; }

	static void handleSignal(int, siginfo_t* info, void* _ctx) {
		ucontext_t *uctx = static_cast<ucontext_t*>(_ctx);

		StackTrace st;
		void* error_addr = nullptr;
#ifdef REG_RIP // x86_64
		error_addr = reinterpret_cast<void*>(uctx->uc_mcontext.gregs[REG_RIP]);
#elif defined(REG_EIP) // x86_32
		error_addr = reinterpret_cast<void*>(uctx->uc_mcontext.gregs[REG_EIP]);
#elif defined(__arm__)
		error_addr = reinterpret_cast<void*>(uctx->uc_mcontext.arm_pc);
#elif defined(__aarch64__)
		error_addr = reinterpret_cast<void*>(uctx->uc_mcontext.pc);
#elif defined(__ppc__) || defined(__powerpc) || defined(__powerpc__) || defined(__POWERPC__)
		error_addr = reinterpret_cast<void*>(uctx->uc_mcontext.regs->nip);
#elif defined(__s390x__)
                error_addr = reinterpret_cast<void*>(uctx->uc_mcontext.psw.addr);
#elif defined(__APPLE__) && defined(__x86_64__)
		error_addr = reinterpret_cast<void*>(uctx->uc_mcontext->__ss.__rip);
#elif defined(__APPLE__)
		error_addr = reinterpret_cast<void*>(uctx->uc_mcontext->__ss.__eip);
#else
#	warning ":/ sorry, ain't know no nothing none not of your architecture!"
#endif
		if (error_addr) {
			st.load_from(error_addr, 32);
		} else {
			st.load_here(32);
		}

		Printer printer;
		printer.address = true;
		printer.print(st, stderr);

#if _XOPEN_SOURCE >= 700 || _POSIX_C_SOURCE >= 200809L
		psiginfo(info, nullptr);
#else
		(void)info;
#endif
	}

private:
	details::handle<char*> _stack_content;
	bool                   _loaded;

#ifdef __GNUC__
	__attribute__((noreturn))
#endif
	static void sig_handler(int signo, siginfo_t* info, void* _ctx) {
		handleSignal(signo, info, _ctx);

		// try to forward the signal.
		raise(info->si_signo);

		// terminate the process immediately.
		puts("watf? exit");
		_exit(EXIT_FAILURE);
	}
};

#endif // BACKWARD_SYSTEM_LINUX || BACKWARD_SYSTEM_DARWIN

#ifdef BACKWARD_SYSTEM_UNKNOWN

class SignalHandling {
public:
	SignalHandling(const std::vector<int>& = std::vector<int>()) {}
	bool init() { return false; }
	bool loaded() { return false; }
};

#endif // BACKWARD_SYSTEM_UNKNOWN

} // namespace backward

#endif /* H_GUARD */