new bt parser (kklic)

20 files changed, 4269 insertions, 0 deletions

diff --git a/lib/btparser/Makefile.am b/lib/btparser/Makefile.am
new file mode 100644
index 00000000..bb8a7f5d
--- /dev/null
+++ b/lib/btparser/Makefile.am
@@ -0,0 +1,44 @@
+lib_LTLIBRARIES = libbtparser.la
+libbtparser_la_SOURCES = \
+	backtrace.h backtrace.c \
+	frame.h frame.c \
+	location.h location.c \
+	normalize.h normalize.c \
+	normalize_dbus.c \
+	normalize_gdk.c \
+	normalize_glib.c \
+	normalize_glibc.c \
+	normalize_libstdcpp.c \
+	normalize_linux.c \
+	normalize_xorg.c \
+	thread.h thread.c \
+	utils.h utils.c
+libbtparser_la_CFLAGS = -Wall -Werror -D_GNU_SOURCE -I../Utils
+libbtparser_la_LDFLAGS = -version-info 1:1:0
+libbtparser_la_LIBADD = ../Utils/libABRTUtils.la
+
+# From http://www.seul.org/docs/autotut/
+# Version consists 3 numbers: CURRENT, REVISION, AGE.
+# CURRENT is the version of the interface the library implements.
+# Whenever a new function is added, or its name changed, or
+# the number or type of its parameters (the prototype -- in
+# libraries we call this the function signature), this number
+# goes up. And it goes up exactly by one.
+#
+# REVISION is the revision of the implementation of this
+# interface, i.e., when you change the library by only modifying
+# code inside the functions (fixing bugs, optimizing internal
+# behavior, or adding/removing/changing signatures of functions
+# that are private to the library -- used only internally) you
+# raise the revision number only.
+#
+# Age is the difference between the newest and oldest interface
+# the library currently implements. Let's say you had 8 versions
+# of your library's interface, 0 through 7. You are now on
+# the 4th revision of the 8th interface, that is, 7:3:X (remember
+# we start counting on zero). And when you had to make choices
+# for what old interfaces you would keep support -- for backward
+# compatibility purposes, you chose to keep support for
+# interfaces 5, 6 and (obviously) the current, 7. The libtool
+# version of your library would be 7:3:2 , because the Age
+# is 7-5 = 2.
diff --git a/lib/btparser/backtrace.c b/lib/btparser/backtrace.c
new file mode 100644
index 00000000..139b315d
--- /dev/null
+++ b/lib/btparser/backtrace.c
@@ -0,0 +1,445 @@
+/*
+    backtrace.c
+
+    Copyright (C) 2010  Red Hat, Inc.
+
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License along
+    with this program; if not, write to the Free Software Foundation, Inc.,
+    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+#include "backtrace.h"
+#include "thread.h"
+#include "frame.h"
+#include "utils.h"
+#include "strbuf.h"
+#include "location.h"
+#include "normalize.h"
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <assert.h>
+
+struct btp_backtrace *
+btp_backtrace_new()
+{
+    struct btp_backtrace *backtrace = btp_malloc(sizeof(struct btp_backtrace));
+    btp_backtrace_init(backtrace);
+    return backtrace;
+}
+
+void
+btp_backtrace_init(struct btp_backtrace *backtrace)
+{
+    backtrace->threads = NULL;
+    backtrace->crash = NULL;
+}
+
+void
+btp_backtrace_free(struct btp_backtrace *backtrace)
+{
+    if (!backtrace)
+        return;
+
+    while (backtrace->threads)
+    {
+        struct btp_thread *rm = backtrace->threads;
+        backtrace->threads = rm->next;
+        btp_thread_free(rm);
+    }
+
+    if (backtrace->crash)
+        btp_frame_free(backtrace->crash);
+
+    free(backtrace);
+}
+
+struct btp_backtrace *
+btp_backtrace_dup(struct btp_backtrace *backtrace)
+{
+    struct btp_backtrace *result = btp_backtrace_new();
+    memcpy(result, backtrace, sizeof(struct btp_backtrace));
+
+    if (backtrace->crash)
+        backtrace->crash = btp_frame_dup(backtrace->crash, false);
+    if (backtrace->threads)
+        backtrace->threads = btp_thread_dup(backtrace->threads, true);
+
+    return result;
+}
+
+int
+btp_backtrace_get_thread_count(struct btp_backtrace *backtrace)
+{
+    struct btp_thread *thread = backtrace->threads;
+    int count = 0;
+    while (thread)
+    {
+        thread = thread->next;
+        ++count;
+    }
+    return count;
+}
+
+void
+btp_backtrace_remove_threads_except_one(struct btp_backtrace *backtrace,
+					struct btp_thread *thread)
+{
+    while (backtrace->threads)
+    {
+        struct btp_thread *delete_thread = backtrace->threads;
+        backtrace->threads = delete_thread->next;
+        if (delete_thread != thread)
+            btp_thread_free(delete_thread);
+    }
+
+    thread->next = NULL;
+    backtrace->threads = thread;
+}
+
+/**
+ * Loop through all threads and if a single one contains the crash
+ * frame on the top, return it. Otherwise, return NULL.
+ *
+ * If require_abort is true, it is also required that the thread
+ * containing the crash frame contains some known "abort" function. In
+ * this case there can be multiple threads with the crash frame on the
+ * top, but only one of them might contain the abort function to
+ * succeed.
+ */
+static struct btp_thread *
+btp_backtrace_find_crash_thread_from_crash_frame(struct btp_backtrace *backtrace,
+                                                 bool require_abort)
+{
+    if (btp_debug_parser)
+        printf("%s(backtrace, %s)\n", __FUNCTION__, require_abort ? "true" : "false");
+
+    assert(backtrace->threads); /* checked by the caller */
+    if (!backtrace->crash || !backtrace->crash->function_name)
+        return NULL;
+
+    struct btp_thread *result = NULL;
+    struct btp_thread *thread = backtrace->threads;
+    while (thread)
+    {
+        struct btp_frame *top_frame = thread->frames;
+        bool same_name = top_frame &&
+            top_frame->function_name &&
+            0 == strcmp(top_frame->function_name, backtrace->crash->function_name);
+        bool abort_requirement_satisfied = !require_abort ||
+            btp_glibc_thread_find_exit_frame(thread);
+        if (btp_debug_parser)
+        {
+            printf(" - thread #%d: same_name %s, abort_satisfied %s\n",
+                   thread->number,
+                   same_name ? "true" : "false",
+                   abort_requirement_satisfied ? "true" : "false");
+        }
+
+        if (same_name && abort_requirement_satisfied)
+        {
+            if (NULL == result)
+                result = thread;
+            else
+            {
+                /* Second frame with the same function. Failure. */
+                return NULL;
+            }
+        }
+
+        thread = thread->next;
+    }
+
+    return result;
+}
+
+struct btp_thread *
+btp_backtrace_find_crash_thread(struct btp_backtrace *backtrace)
+{
+    /* If there is no thread, be silent and report NULL. */
+    if (!backtrace->threads)
+        return NULL;
+
+    /* If there is just one thread, it is simple. */
+    if (!backtrace->threads->next)
+        return backtrace->threads;
+
+    /* If we have a crash frame *and* there is just one thread which has
+     * this frame on the top, it is also simple.
+     */
+    struct btp_thread *thread;
+    thread = btp_backtrace_find_crash_thread_from_crash_frame(backtrace, false);
+    if (thread)
+        return thread;
+
+    /* There are multiple threads with a frame indistinguishable from
+     * the crash frame on the top of stack.
+     * Try to search for known abort functions.
+     */
+    thread = btp_backtrace_find_crash_thread_from_crash_frame(backtrace, true);
+
+    /* We might want to search a thread with known abort function, and
+     * without the crash frame here. However, it hasn't been needed so
+     * far.
+     */
+    return thread; /* result or null */
+}
+
+
+void
+btp_backtrace_limit_frame_depth(struct btp_backtrace *backtrace,
+				int depth)
+{
+    assert(depth > 0);
+    struct btp_thread *thread = backtrace->threads;
+    while (thread)
+    {
+        btp_thread_remove_frames_below_n(thread, depth);
+        thread = thread->next;
+    }
+}
+
+float
+btp_backtrace_quality_simple(struct btp_backtrace *backtrace)
+{
+    int ok_count = 0, all_count = 0;
+    struct btp_thread *thread = backtrace->threads;
+    while (thread)
+    {
+        btp_thread_quality_counts(thread, &ok_count, &all_count);
+        thread = thread->next;
+    }
+
+    if (all_count == 0)
+        return 0;
+
+    return ok_count / (float)all_count;
+}
+
+float
+btp_backtrace_quality_complex(struct btp_backtrace *backtrace)
+{
+    backtrace = btp_backtrace_dup(backtrace);
+
+    /* Find the crash thread, and then normalize the backtrace. It is
+     * not possible to find the crash thread after the backtrace has
+     * been normalized.
+     */
+    struct btp_thread *crash_thread = btp_backtrace_find_crash_thread(backtrace);
+    btp_normalize_backtrace(backtrace);
+
+    /* Get the quality q1 of the full backtrace. */
+    float q1 = btp_backtrace_quality_simple(backtrace);
+
+    if (!crash_thread)
+    {
+        btp_backtrace_free(backtrace);
+        return q1;
+    }
+
+    /* Get the quality q2 of the crash thread. */
+    float q2 = btp_thread_quality(crash_thread);
+
+    /* Get the quality q3 of the frames around the crash.  First,
+     * duplicate the crash thread so we can cut it. Then find an exit
+     * frame, and remove it and everything above it
+     * (__run_exit_handlers and such). Then remove all the redundant
+     * frames (assert calls etc.) Then limit the frame count to 5.
+     */
+    btp_thread_remove_frames_below_n(crash_thread, 5);
+    float q3 = btp_thread_quality(crash_thread);
+
+    btp_backtrace_free(backtrace);
+
+    /* Compute and return the final backtrace quality q. */
+    return 0.25f * q1 + 0.35f * q2 + 0.4f * q3;
+}
+
+char *
+btp_backtrace_to_text(struct btp_backtrace *backtrace, bool verbose)
+{
+    struct strbuf *str = strbuf_new();
+    if (verbose)
+    {
+        strbuf_append_strf(str, "Thread count: %d\n",
+                               btp_backtrace_get_thread_count(backtrace));
+    }
+
+    if (backtrace->crash && verbose)
+    {
+        strbuf_append_str(str, "Crash frame: ");
+        btp_frame_append_to_str(backtrace->crash, str, verbose);
+    }
+
+    struct btp_thread *thread = backtrace->threads;
+    while (thread)
+    {
+        btp_thread_append_to_str(thread, str, verbose);
+        thread = thread->next;
+    }
+
+    return strbuf_free_nobuf(str);
+}
+
+struct btp_frame *
+btp_backtrace_get_crash_frame(struct btp_backtrace *backtrace)
+{
+    backtrace = btp_backtrace_dup(backtrace);
+
+    struct btp_thread *crash_thread = btp_backtrace_find_crash_thread(backtrace);
+    if (!crash_thread)
+    {
+        btp_backtrace_free(backtrace);
+        return NULL;
+    }
+
+    btp_normalize_backtrace(backtrace);
+    struct btp_frame *crash_frame = crash_thread->frames;
+    crash_frame = btp_frame_dup(crash_frame, false);
+    btp_backtrace_free(backtrace);
+    return crash_frame;
+}
+
+char *
+btp_backtrace_get_duplication_hash(struct btp_backtrace *backtrace)
+{
+    backtrace = btp_backtrace_dup(backtrace);
+    struct btp_thread *crash_thread = btp_backtrace_find_crash_thread(backtrace);
+    if (crash_thread)
+        btp_backtrace_remove_threads_except_one(backtrace, crash_thread);
+
+    btp_normalize_backtrace(backtrace);
+    btp_backtrace_limit_frame_depth(backtrace, 3);
+    char *hash = btp_backtrace_to_text(backtrace, false);
+    btp_backtrace_free(backtrace);
+    return hash;
+}
+
+struct btp_backtrace *
+btp_backtrace_parse(char **input,
+                    struct btp_location *location)
+{
+    char *local_input = *input;
+    struct btp_backtrace *imbacktrace = btp_backtrace_new(); /* im - intermediate */
+
+    /* The header is mandatory, but it might contain no frame header,
+     * in some broken backtraces. In that case, backtrace.crash value
+     * is kept as NULL.
+     */
+    if (!btp_backtrace_parse_header(&local_input,
+                                    &imbacktrace->crash,
+                                    location))
+    {
+        btp_backtrace_free(imbacktrace);
+        return NULL;
+    }
+
+    struct btp_thread *thread, *prevthread = NULL;
+    while ((thread = btp_thread_parse(&local_input, location)))
+    {
+        if (prevthread)
+        {
+            btp_thread_add_sibling(prevthread, thread);
+            prevthread = thread;
+        }
+        else
+            imbacktrace->threads = prevthread = thread;
+    }
+    if (!imbacktrace->threads)
+    {
+        btp_backtrace_free(imbacktrace);
+        return NULL;
+    }
+
+    *input = local_input;
+    return imbacktrace;
+}
+
+bool
+btp_backtrace_parse_header(char **input,
+                           struct btp_frame **frame,
+                           struct btp_location *location)
+{
+    int first_thread_line, first_thread_column;
+    char *first_thread = btp_strstr_location(*input,
+                                             "\nThread ",
+                                             &first_thread_line,
+                                             &first_thread_column);
+
+    /* Skip the newline. */
+    if (first_thread)
+    {
+        ++first_thread;
+        first_thread_line += 1;
+        first_thread_column = 0;
+    }
+
+    int first_frame_line, first_frame_column;
+    char *first_frame = btp_strstr_location(*input,
+                                            "\n#",
+                                            &first_frame_line,
+                                            &first_frame_column);
+
+    /* Skip the newline. */
+    if (first_frame)
+    {
+        ++first_frame;
+        first_frame_line += 1;
+        first_frame_column = 0;
+    }
+
+    if (first_thread)
+    {
+        if (first_frame && first_frame < first_thread)
+        {
+            /* Common case. The crash frame is present in the input
+             * before the list of threads begins.
+             */
+            *input = first_frame;
+            btp_location_add(location, first_frame_line, first_frame_column);
+        }
+        else
+        {
+	    /* Uncommon case (caused by some kernel bug) where the
+             * frame is missing from the header.  The backtrace
+             * contains just threads.  We silently skip the header and
+             * return true.
+             */
+  	    *input = first_thread;
+            btp_location_add(location,
+                             first_thread_line,
+                             first_thread_column);
+            *frame = NULL;
+	    return true;
+        }
+    }
+    else if (first_frame)
+    {
+        /* Degenerate case when the backtrace contains no thread, but
+         * the frame is there.
+         */
+        *input = first_frame;
+        btp_location_add(location, first_frame_line, first_frame_column);
+    }
+    else
+    {
+        /* Degenerate case where the input is empty or completely
+         * meaningless. Report a failure.
+         */
+        location->message = "No frame and no thread found.";
+        return false;
+    }
+
+    /* Parse the frame header. */
+    *frame = btp_frame_parse(input, location);
+    return *frame;
+}
diff --git a/lib/btparser/backtrace.h b/lib/btparser/backtrace.h
new file mode 100644
index 00000000..d5de3ff3
--- /dev/null
+++ b/lib/btparser/backtrace.h
@@ -0,0 +1,269 @@
+/*
+    backtrace.h
+
+    Copyright (C) 2010  Red Hat, Inc.
+
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License along
+    with this program; if not, write to the Free Software Foundation, Inc.,
+    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+#ifndef BTPARSER_BACKTRACE_H
+#define BTPARSER_BACKTRACE_H
+
+#include <stdbool.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+struct btp_thread;
+struct btp_frame;
+struct btp_location;
+
+/**
+ * A backtrace obtained at the time of a program crash, consisting of
+ * several threads which contains frames.
+ */
+struct btp_backtrace
+{
+    struct btp_thread *threads;
+    /**
+     * The frame where the crash happened according to debugger.  It
+     * might be that we can not tell to which thread this frame
+     * belongs, because some threads end with mutually
+     * indistinguishable frames.
+     */
+    struct btp_frame *crash;
+};
+
+/**
+ * Creates and initializes a new backtrace structure.
+ * @returns
+ * It never returns NULL. The returned pointer must be released by
+ * calling the function btp_backtrace_free().
+ */
+struct btp_backtrace *
+btp_backtrace_new();
+
+/**
+ * Initializes all members of the backtrace structure to their default
+ * values.  No memory is released, members are simply overwritten.
+ * This is useful for initializing a backtrace structure placed on the
+ * stack.
+ */
+void
+btp_backtrace_init(struct btp_backtrace *backtrace);
+
+/**
+ * Releases the memory held by the backtrace, its threads and frames.
+ * @param backtrace
+ * If the backtrace is NULL, no operation is performed.
+ */
+void
+btp_backtrace_free(struct btp_backtrace *backtrace);
+
+/**
+ * Creates a duplicate of the backtrace.
+ * @param backtrace
+ * The backtrace to be copied. It's not modified by this function.
+ * @returns
+ * This function never returns NULL. If the returned duplicate is not
+ * shallow, it must be released by calling the function
+ * btp_backtrace_free().
+ */
+struct btp_backtrace *
+btp_backtrace_dup(struct btp_backtrace *backtrace);
+
+/**
+ * Returns a number of threads in the backtrace.
+ * @param backtrace
+ * It's not modified by calling this function.
+ */
+int
+btp_backtrace_get_thread_count(struct btp_backtrace *backtrace);
+
+/**
+ * Removes all threads from the backtrace and deletes them, except the
+ * one provided as a parameter.
+ * @param thread
+ * This function does not check whether the thread is a member of the backtrace.
+ * If it's not, all threads are removed from the backtrace and then deleted.
+ */
+void
+btp_backtrace_remove_threads_except_one(struct btp_backtrace *backtrace,
+					struct btp_thread *thread);
+
+/**
+ * Search all threads and tries to find the one that caused the crash.
+ * It might return NULL if the thread cannot be determined.
+ * @param backtrace
+ * It must be non-NULL pointer. It's not modified by calling this
+ * function.
+ */
+struct btp_thread *
+btp_backtrace_find_crash_thread(struct btp_backtrace *backtrace);
+
+/**
+ * Remove frames from the bottom of threads in the backtrace, until
+ * all threads have at most 'depth' frames.
+ * @param backtrace
+ * Must be non-NULL pointer.
+ */
+void
+btp_backtrace_limit_frame_depth(struct btp_backtrace *backtrace,
+				int depth);
+
+/**
+ * Evaluates the quality of the backtrace. The quality is the ratio of
+ * the number of frames with function name fully known to the number
+ * of all frames.  This function does not take into account that some
+ * frames are more important than others.
+ * @param backtrace
+ * It must be non-NULL pointer. It's not modified by calling this
+ * function.
+ * @returns
+ * A number between 0 and 1. 0 means the lowest quality, 1 means full
+ * backtrace is known.
+ */
+float
+btp_backtrace_quality_simple(struct btp_backtrace *backtrace);
+
+/**
+ * Evaluates the quality of the backtrace. The quality is determined
+ * depending on the ratio of frames with function name fully known to
+ * all frames.
+ * @param backtrace
+ * It must be non-NULL pointer. It's not modified by calling this
+ * function.
+ * @returns
+ * A number between 0 and 1. 0 means the lowest quality, 1 means full
+ * backtrace is known.  The returned value takes into account that the
+ * thread which caused the crash is more important than the other
+ * threads, and the frames around the crash frame are more important
+ * than distant frames.
+ */
+float
+btp_backtrace_quality_complex(struct btp_backtrace *backtrace);
+
+/**
+ * Returns textual representation of the backtrace.
+ * @param backtrace
+ * It must be non-NULL pointer. It's not modified by calling this
+ * function.
+ * @returns
+ * This function never returns NULL. The caller is responsible for
+ * releasing the returned memory using function free().
+ */
+char *
+btp_backtrace_to_text(struct btp_backtrace *backtrace,
+                      bool verbose);
+
+/**
+ * Analyzes the backtrace to get the frame where a crash occurred.
+ * @param backtrace
+ * It must be non-NULL pointer. It's not modified by calling this
+ * function.
+ * @returns
+ * The returned value must be released by calling btp_frame_free(),
+ * when it's no longer needed.  NULL is returned if the crash frame is
+ * not found.
+ */
+struct btp_frame *
+btp_backtrace_get_crash_frame(struct btp_backtrace *backtrace);
+
+/**
+ * Calculates the duplication hash string of the backtrace.
+ * @param backtrace
+ * It must be non-NULL pointer. It's not modified by calling this
+ * function.
+ * @returns
+ * This function never returns NULL. The caller is responsible for
+ * releasing the returned memory using function free().
+ */
+char *
+btp_backtrace_get_duplication_hash(struct btp_backtrace *backtrace);
+
+/**
+ * Parses a textual backtrace and puts it into a structure.  If
+ * parsing fails, the input parameter is not changed and NULL is
+ * returned.
+ * @code
+ * struct btp_location location;
+ * btp_location_init(&location);
+ * char *input = "...";
+ * struct btp_backtrace *backtrace = btp_backtrace_parse(input, location;
+ * if (!backtrace)
+ * {
+ *   fprintf(stderr,
+ *           "Failed to parse the backtrace.\n"
+ *           "Line %d, column %d: %s\n",
+ *           location.line,
+ *           location.column,
+ *           location.message);
+ *   exit(-1);
+ * }
+ * btp_backtrace_free(backtrace);
+ * @endcode
+ * @param input
+ * Pointer to the string with the backtrace. If this function returns
+ * true, this pointer is modified to point after the backtrace that
+ * was just parsed.
+ * @param location
+ * The caller must provide a pointer to an instance of btp_location
+ * here.  The line and column members of the location are gradually
+ * increased as the parser handles the input, so the location should
+ * be initialized before calling this function to get reasonable
+ * values.  When this function returns false (an error occurred), the
+ * structure will contain the error line, column, and message.
+ * @returns
+ * A newly allocated backtrace structure or NULL. A backtrace struct
+ * is returned when at least one thread was parsed from the input and
+ * no error occurred. The returned structure should be released by
+ * btp_backtrace_free().
+ */
+struct btp_backtrace *
+btp_backtrace_parse(char **input,
+                    struct btp_location *location);
+
+/**
+ * Parse backtrace header if it is available in the backtrace.  The
+ * header usually contains frame where the program crashed.
+ * @param input
+ * Pointer moved to point behind the header if the header is
+ * successfully detected and parsed.
+ * @param frame
+ * If this function succeeds and returns true, *frame contains the
+ * crash frame that is usually a part of the header. If no frame is
+ * detected in the header, *frame is set to NULL.
+ * @code
+ * [New Thread 11919]
+ * [New Thread 11917]
+ * Core was generated by `evince file:///tmp/Factura04-05-2010.pdf'.
+ * Program terminated with signal 8, Arithmetic exception.
+ * #0  0x000000322a2362b9 in repeat (image=<value optimized out>,
+ *     mask=<value optimized out>, mask_bits=<value optimized out>)
+ *     at pixman-bits-image.c:145
+ * 145     pixman-bits-image.c: No such file or directory.
+ *         in pixman-bits-image.c
+ * @endcode
+ */
+bool
+btp_backtrace_parse_header(char **input,
+                           struct btp_frame **frame,
+                           struct btp_location *location);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
diff --git a/lib/btparser/frame.c b/lib/btparser/frame.c
new file mode 100644
index 00000000..2bfae070
--- /dev/null
+++ b/lib/btparser/frame.c
@@ -0,0 +1,1027 @@
+/*
+    frame.c
+
+    Copyright (C) 2010  Red Hat, Inc.
+
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License along
+    with this program; if not, write to the Free Software Foundation, Inc.,
+    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+#include "frame.h"
+#include "strbuf.h"
+#include "utils.h"
+#include "location.h"
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+
+struct btp_frame *
+btp_frame_new()
+{
+    struct btp_frame *frame = btp_malloc(sizeof(struct btp_frame));
+    btp_frame_init(frame);
+    return frame;
+}
+
+void
+btp_frame_init(struct btp_frame *frame)
+{
+    frame->function_name = NULL;
+    frame->function_type = NULL;
+    frame->number = 0;
+    frame->source_file = NULL;
+    frame->source_line = -1;
+    frame->signal_handler_called = false;
+    frame->address = -1;
+    frame->next = NULL;
+}
+
+void
+btp_frame_free(struct btp_frame *frame)
+{
+    if (!frame)
+        return;
+    free(frame->function_name);
+    free(frame->function_type);
+    free(frame->source_file);
+    free(frame);
+}
+
+struct btp_frame *
+btp_frame_dup(struct btp_frame *frame, bool siblings)
+{
+    struct btp_frame *result = btp_frame_new();
+    memcpy(result, frame, sizeof(struct btp_frame));
+
+    /* Handle siblings. */
+    if (siblings)
+    {
+        if (result->next)
+            result->next = btp_frame_dup(result->next, true);
+    }
+    else
+        result->next = NULL; /* Do not copy that. */
+
+    /* Duplicate all strings if the copy is not shallow. */
+    if (result->function_name)
+        result->function_name = btp_strdup(result->function_name);
+    if (result->function_type)
+        result->function_type = btp_strdup(result->function_type);
+    if (result->source_file)
+        result->source_file = btp_strdup(result->source_file);
+
+    return result;
+}
+
+bool
+btp_frame_calls_func(struct btp_frame *frame,
+                     const char *function_name)
+{
+    return frame->function_name &&
+        0 == strcmp(frame->function_name, function_name);
+}
+
+bool
+btp_frame_calls_func_in_file(struct btp_frame *frame,
+                             const char *function_name,
+                             const char *source_file)
+{
+    return frame->function_name &&
+        0 == strcmp(frame->function_name, function_name) &&
+        frame->source_file &&
+        NULL != strstr(frame->source_file, source_file);
+}
+
+bool
+btp_frame_calls_func_in_file2(struct btp_frame *frame,
+                              const char *function_name,
+                              const char *source_file0,
+                              const char *source_file1)
+{
+    return frame->function_name &&
+        0 == strcmp(frame->function_name, function_name) &&
+        frame->source_file &&
+        (NULL != strstr(frame->source_file, source_file0) ||
+         NULL != strstr(frame->source_file, source_file1));
+}
+
+bool
+btp_frame_calls_func_in_file3(struct btp_frame *frame,
+                              const char *function_name,
+                              const char *source_file0,
+                              const char *source_file1,
+                              const char *source_file2)
+{
+    return frame->function_name &&
+        0 == strcmp(frame->function_name, function_name) &&
+        frame->source_file &&
+        (NULL != strstr(frame->source_file, source_file0) ||
+         NULL != strstr(frame->source_file, source_file1) ||
+         NULL != strstr(frame->source_file, source_file2));
+}
+
+bool
+btp_frame_calls_func_in_file4(struct btp_frame *frame,
+                              const char *function_name,
+                              const char *source_file0,
+                              const char *source_file1,
+                              const char *source_file2,
+                              const char *source_file3)
+{
+    return frame->function_name &&
+        0 == strcmp(frame->function_name, function_name) &&
+        frame->source_file &&
+        (NULL != strstr(frame->source_file, source_file0) ||
+         NULL != strstr(frame->source_file, source_file1) ||
+         NULL != strstr(frame->source_file, source_file2) ||
+         NULL != strstr(frame->source_file, source_file3));
+}
+
+int
+btp_frame_cmp(struct btp_frame *f1,
+              struct btp_frame *f2,
+              bool compare_number)
+{
+    /* Singnal handler. */
+    if (f1->signal_handler_called)
+    {
+        if (!f2->signal_handler_called)
+            return 1;
+
+        /* Both contain signal handler called. */
+        return 0;
+    }
+    else
+    {
+        if (f2->signal_handler_called)
+            return -1;
+        /* No signal handler called, continue. */
+    }
+
+    /* Function. */
+    int function_name = btp_strcmp0(f1->function_name, f2->function_name);
+    if (function_name != 0)
+        return function_name;
+    int function_type = btp_strcmp0(f1->function_type, f2->function_type);
+    if (function_type != 0)
+        return function_type;
+
+    /* Sourcefile. */
+    int source_file = btp_strcmp0(f1->source_file, f2->source_file);
+    if (source_file != 0)
+        return source_file;
+
+    /* Sourceline. */
+    int source_line = f1->source_line - f2->source_line;
+    if (source_line != 0)
+        return source_line;
+
+    /* Frame number. */
+    if (compare_number)
+    {
+        int number = f1->number - f2->number;
+        if (number != 0)
+            return number;
+    }
+
+    return 0;
+}
+
+void
+btp_frame_add_sibling(struct btp_frame *a, struct btp_frame *b)
+{
+    struct btp_frame *aa = a;
+    while (aa->next)
+        aa = aa->next;
+
+    aa->next = b;
+}
+
+void
+btp_frame_append_to_str(struct btp_frame *frame,
+                        struct strbuf *str,
+                        bool verbose)
+{
+    if (verbose)
+        strbuf_append_strf(str, " #%d", frame->number);
+    else
+        strbuf_append_str(str, " ");
+
+    if (frame->function_type)
+        strbuf_append_strf(str, " %s", frame->function_type);
+    if (frame->function_name)
+        strbuf_append_strf(str, " %s", frame->function_name);
+    if (verbose && frame->source_file)
+    {
+        if (frame->function_name)
+            strbuf_append_str(str, " at");
+        strbuf_append_strf(str, " %s", frame->source_file);
+    }
+
+    if (frame->signal_handler_called)
+        strbuf_append_str(str, " <signal handler called>");
+
+    strbuf_append_str(str, "\n");
+}
+
+/**
+ * Find string a or b in input, whatever comes first.
+ * If no string is found, return the \0 character at the end of input.
+ */
+static char *
+findfirstabnul(char *input, const char *a, const char *b)
+{
+    size_t alen = strlen(a);
+    size_t blen = strlen(b);
+    char *p = input;
+    while (*p)
+    {
+        if (strncmp(p, a, alen) == 0)
+            return p;
+        if (strncmp(p, b, blen) == 0)
+            return p;
+        ++p;
+    }
+    return p;
+}
+
+struct btp_frame *
+btp_frame_parse(char **input,
+                struct btp_location *location)
+{
+    char *local_input = *input;
+    struct btp_frame *header = btp_frame_parse_header(input, location);
+    if (!header)
+        return NULL;
+
+    /* Skip the variables section for now. */
+    /* Todo: speedup by implementing strstrnul. */
+    local_input = findfirstabnul(local_input, "\n#", "\nThread");
+    if (*local_input != '\0')
+        ++local_input; /* ++ skips the newline */
+
+    if (btp_debug_parser)
+    {
+        printf("frame #%u %s\n",
+               header->number,
+               header->function_name ? header->function_name : "signal handler called");
+    }
+
+    *input = local_input;
+    return header;
+}
+
+int
+btp_frame_parse_frame_start(char **input, unsigned *number)
+{
+    char *local_input = *input;
+
+    /* Read the hash sign. */
+    if (!btp_skip_char(&local_input, '#'))
+        return 0;
+    int count = 1;
+
+    /* Read the frame position. */
+    int digits = btp_parse_unsigned_integer(&local_input, number);
+    count += digits;
+    if (0 == digits)
+        return 0;
+
+    /* Read all the spaces after the positon. */
+    int spaces = btp_skip_char_sequence(&local_input, ' ');
+    count += spaces;
+    if (0 == spaces)
+        return 0;
+
+    *input = local_input;
+    return count;
+}
+
+int
+btp_frame_parseadd_operator(char **input, struct strbuf *target)
+{
+    char *local_input = *input;
+    if (0 == btp_skip_string(&local_input, "operator"))
+        return 0;
+
+#define OP(x) \
+    if (0 < btp_skip_string(&local_input, x))      \
+    {                                              \
+        strbuf_append_str(target, "operator"); \
+        strbuf_append_str(target, x);          \
+        int length = local_input - *input;         \
+        *input = local_input;                      \
+        return length;                             \
+    }
+
+    OP(">>=")OP(">>")OP(">=")OP(">");
+    OP("<<=")OP("<<")OP("<=")OP("<");
+    OP("->*")OP("->")OP("-");
+    OP("==")OP("=");
+    OP("&&")OP("&=")OP("&");
+    OP("||")OP("|=")OP("|");
+    OP("++")OP("+=")OP("+");
+    OP("--")OP("-=")OP("-");
+    OP("/=")OP("/");
+    OP("*=")OP("*");
+    OP("%=")OP("%");
+    OP("!=")OP("!");
+    OP("~");
+    OP("()");
+    OP("[]");
+    OP(",");
+    OP("^=")OP("^");
+    OP(" new[]")OP(" new");
+    OP(" delete[]")OP(" delete");
+    /* User defined operators are not parsed.
+       Should they be? */
+#undef OP
+    return 0;
+}
+
+#define FUNCTION_NAME_CHARS BTP_alnum "@.:=!*+-[]~&/%^|,_"
+
+int
+btp_frame_parse_function_name_chunk(char **input,
+                                    bool space_allowed,
+                                    char **target)
+{
+    char *local_input = *input;
+    struct strbuf *buf = strbuf_new();
+    while (*local_input)
+    {
+        if (0 < btp_frame_parseadd_operator(&local_input, buf))
+        {
+            /* Space is allowed after operator even when it
+               is not normally allowed. */
+            if (btp_skip_char(&local_input, ' '))
+            {
+                /* ...but if ( follows, it is not allowed. */
+                if (btp_skip_char(&local_input, '('))
+                {
+                    /* Return back both the space and (. */
+                    local_input -= 2;
+                }
+                else
+                    strbuf_append_char(buf, ' ');
+            }
+        }
+
+        if (strchr(FUNCTION_NAME_CHARS, *local_input) == NULL)
+        {
+            if (!space_allowed || strchr(" ", *local_input) == NULL)
+                break;
+        }
+
+        strbuf_append_char(buf, *local_input);
+        ++local_input;
+    }
+
+    if (buf->len == 0)
+    {
+        strbuf_free(buf);
+        return 0;
+    }
+
+    *target = strbuf_free_nobuf(buf);
+    int total_char_count = local_input - *input;
+    *input = local_input;
+    return total_char_count;
+}
+
+int
+btp_frame_parse_function_name_braces(char **input, char **target)
+{
+    char *local_input = *input;
+    if (!btp_skip_char(&local_input, '('))
+        return 0;
+
+    struct strbuf *buf = strbuf_new();
+    strbuf_append_char(buf, '(');
+    while (true)
+    {
+        char *namechunk = NULL;
+        if (0 < btp_frame_parse_function_name_chunk(&local_input, true, &namechunk) ||
+            0 < btp_frame_parse_function_name_braces(&local_input, &namechunk) ||
+            0 < btp_frame_parse_function_name_template(&local_input, &namechunk))
+        {
+            strbuf_append_str(buf, namechunk);
+            free(namechunk);
+        }
+        else
+            break;
+    }
+
+    if (!btp_skip_char(&local_input, ')'))
+    {
+        strbuf_free(buf);
+        return 0;
+    }
+
+    strbuf_append_char(buf, ')');
+    *target = strbuf_free_nobuf(buf);
+    int total_char_count = local_input - *input;
+    *input = local_input;
+    return total_char_count;
+}
+
+int
+btp_frame_parse_function_name_template(char **input, char **target)
+{
+    char *local_input = *input;
+    if (!btp_skip_char(&local_input, '<'))
+        return 0;
+
+    struct strbuf *buf = strbuf_new();
+    strbuf_append_char(buf, '<');
+    while (true)
+    {
+        char *namechunk = NULL;
+        if (0 < btp_frame_parse_function_name_chunk(&local_input, true, &namechunk) ||
+            0 < btp_frame_parse_function_name_braces(&local_input, &namechunk) ||
+            0 < btp_frame_parse_function_name_template(&local_input, &namechunk))
+        {
+            strbuf_append_str(buf, namechunk);
+            free(namechunk);
+        }
+        else
+            break;
+    }
+
+    if (!btp_skip_char(&local_input, '>'))
+    {
+        strbuf_free(buf);
+        return 0;
+    }
+
+    strbuf_append_char(buf, '>');
+    *target = strbuf_free_nobuf(buf);
+    int total_char_count = local_input - *input;
+    *input = local_input;
+    return total_char_count;
+}
+
+bool
+btp_frame_parse_function_name(char **input,
+                              char **function_name,
+                              char **function_type,
+                              struct btp_location *location)
+{
+    /* Handle unknown function name, represended by double question
+       mark. */
+    if (btp_parse_string(input, "??", function_name))
+    {
+        *function_type = NULL;
+        location->column += 2;
+        return true;
+    }
+
+    char *local_input = *input;
+    /* Up to three parts of function name. */
+    struct strbuf *buf0 = strbuf_new(), *buf1 = NULL;
+
+    /* First character:
+       '~' for destructor
+       '*' for ????
+       '_a-zA-Z' for mangled/nonmangled function name
+       '(' to start "(anonymous namespace)::" or something
+     */
+    char first;
+    char *namechunk;
+    if (btp_parse_char_limited(&local_input, "~*_" BTP_alpha, &first))
+    {
+        /* If it's a start of 'o'perator, put the 'o' back! */
+        if (first == 'o')
+            --local_input;
+        else
+        {
+            strbuf_append_char(buf0, first);
+            ++location->column;
+        }
+    }
+    else
+    {
+        int chars = btp_frame_parse_function_name_braces(&local_input,
+                                                         &namechunk);
+        if (0 < chars)
+        {
+            strbuf_append_str(buf0, namechunk);
+            free(namechunk);
+            location->column += chars;
+        }
+        else
+        {
+            location->message = "Expected function name.";
+            strbuf_free(buf0);
+            return false;
+        }
+    }
+
+    /* The rest consists of function name, braces, templates...*/
+    while (true)
+    {
+        char *namechunk = NULL;
+        int chars = btp_frame_parse_function_name_chunk(&local_input,
+                                                        false,
+                                                        &namechunk);
+
+        if (0 == chars)
+        {
+            chars = btp_frame_parse_function_name_braces(&local_input,
+                                                         &namechunk);
+        }
+
+        if (0 == chars)
+        {
+            chars = btp_frame_parse_function_name_template(&local_input,
+                                                           &namechunk);
+        }
+
+        if (0 == chars)
+            break;
+
+        strbuf_append_str(buf0, namechunk);
+        free(namechunk);
+        location->column += chars;
+    }
+
+    /* Function name MUST be ended by empty space. */
+    char space;
+    if (!btp_parse_char_limited(&local_input, BTP_space, &space))
+    {
+        strbuf_free(buf0);
+        location->message = "Space or newline expected after function name.";
+        return false;
+    }
+
+    /* Some C++ function names and function types might contain suffix
+       " const". */
+    int chars = btp_skip_string(&local_input, "const");
+    if (0 < chars)
+    {
+        strbuf_append_char(buf0, space);
+        btp_location_eat_char(location, space);
+        strbuf_append_str(buf0, "const");
+        location->column += chars;
+
+        /* Check the empty space after function name again.*/
+        if (!btp_parse_char_limited(&local_input, BTP_space, &space))
+        {
+            /* Function name MUST be ended by empty space. */
+            strbuf_free(buf0);
+            location->message = "Space or newline expected after function name.";
+            return false;
+        }
+    }
+
+    /* Maybe the first series was just a type of the function, and now
+       the real function follows. Now, we know it must not start with
+       '(', nor with '<'. */
+    chars = btp_frame_parse_function_name_chunk(&local_input,
+                                                false,
+                                                &namechunk);
+    if (0 < chars)
+    {
+        /* Eat the space separator first. */
+        btp_location_eat_char(location, space);
+
+        buf1 = strbuf_new();
+        strbuf_append_str(buf1, namechunk);
+        free(namechunk);
+        location->column += chars;
+
+        /* The rest consists of a function name parts, braces, templates...*/
+        while (true)
+        {
+            char *namechunk = NULL;
+            chars = btp_frame_parse_function_name_chunk(&local_input,
+                                                        false,
+                                                        &namechunk);
+            if (0 == chars)
+            {
+                chars = btp_frame_parse_function_name_braces(&local_input,
+                                                             &namechunk);
+            }
+            if (0 == chars)
+            {
+                chars = btp_frame_parse_function_name_template(&local_input,
+                                                               &namechunk);
+            }
+            if (0 == chars)
+                break;
+
+            strbuf_append_str(buf1, namechunk);
+            free(namechunk);
+            location->column += chars;
+        }
+
+        /* Function name MUST be ended by empty space. */
+        if (!btp_parse_char_limited(&local_input, BTP_space, &space))
+        {
+            strbuf_free(buf0);
+            strbuf_free(buf1);
+            location->message = "Space or newline expected after function name.";
+            return false;
+        }
+    }
+
+    /* Again, some C++ function names might contain suffix " const" */
+    chars = btp_skip_string(&local_input, "const");
+    if (0 < chars)
+    {
+        struct strbuf *buf = buf1 ? buf1 : buf0;
+        strbuf_append_char(buf, space);
+        btp_location_eat_char(location, space);
+        strbuf_append_str(buf, "const");
+        location->column += chars;
+
+        /* Check the empty space after function name again.*/
+        if (!btp_skip_char_limited(&local_input, BTP_space))
+        {
+            /* Function name MUST be ended by empty space. */
+            strbuf_free(buf0);
+            strbuf_free(buf1);
+            location->message = "Space or newline expected after function name.";
+            return false;
+        }
+    }
+
+    /* Return back to the empty space. */
+    --local_input;
+
+    if (buf1)
+    {
+        *function_name = strbuf_free_nobuf(buf1);
+        *function_type = strbuf_free_nobuf(buf0);
+    }
+    else
+    {
+        *function_name = strbuf_free_nobuf(buf0);
+        *function_type = NULL;
+    }
+
+    *input = local_input;
+    return true;
+}
+
+bool
+btp_frame_skip_function_args(char **input, struct btp_location *location)
+{
+    char *local_input = *input;
+    if (!btp_skip_char(&local_input, '('))
+    {
+        location->message = "Expected '(' to start function argument list.";
+        return false;
+    }
+    location->column += 1;
+
+    int depth = 0;
+    bool string = false;
+    bool escape = false;
+    do
+    {
+        if (string)
+        {
+            if (escape)
+                escape = false;
+            else if (*local_input == '\\')
+                escape = true;
+            else if (*local_input == '"')
+                string = false;
+        }
+        else
+        {
+            if (*local_input == '"')
+                string = true;
+            else if (*local_input == '(')
+                ++depth;
+            else if (*local_input == ')')
+            {
+                if (depth > 0)
+                    --depth;
+                else
+                    break;
+            }
+        }
+        btp_location_eat_char(location, *local_input);
+        ++local_input;
+    }
+    while (*local_input);
+
+    if (depth != 0 || string || escape)
+    {
+        location->message = "Unbalanced function parameter list.";
+        return false;
+    }
+
+    if (!btp_skip_char(&local_input, ')'))
+    {
+        location->message = "Expected ')' to close the function parameter list.";
+        return false;
+    }
+    location->column += 1;
+
+    *input = local_input;
+    return true;
+}
+
+bool
+btp_frame_parse_function_call(char **input,
+                              char **function_name,
+                              char **function_type,
+                              struct btp_location *location)
+{
+    char *local_input = *input;
+    char *name = NULL, *type = NULL;
+    if (!btp_frame_parse_function_name(&local_input,
+                                       &name,
+                                       &type,
+                                       location))
+    {
+        /* The location message is set by the function returning
+         * false, no need to update it here. */
+        return false;
+    }
+
+    int line, column;
+    if (0 == btp_skip_char_span_location(&local_input,
+                                         " \n",
+                                         &line,
+                                         &column))
+    {
+        free(name);
+        free(type);
+        location->message = "Expected a space or newline after the function name.";
+        return false;
+    }
+    btp_location_add(location, line, column);
+
+    if (!btp_frame_skip_function_args(&local_input, location))
+    {
+        free(name);
+        free(type);
+        /* The location message is set by the function returning
+         * false, no need to update it here. */
+        return false;
+    }
+
+    *function_name = name;
+    *function_type = type;
+    *input = local_input;
+    return true;
+}
+
+bool
+btp_frame_parse_address_in_function(char **input,
+                                    uint64_t *address,
+                                    char **function_name,
+                                    char **function_type,
+                                    struct btp_location *location)
+{
+    char *local_input = *input;
+
+    /* Read memory address in hexadecimal format. */
+    int digits = btp_parse_hexadecimal_number(&local_input, address);
+    location->column += digits;
+    if (0 == digits)
+    {
+        location->message = "Hexadecimal number representing memory address expected.";
+        return false;
+    }
+
+    /* Skip spaces. */
+    int chars = btp_skip_char_sequence(&local_input, ' ');
+    location->column += chars;
+    if (0 == chars)
+    {
+        location->message = "Space expected after memory address.";
+        return false;
+    }
+
+    /* Skip keyword "in". */
+    chars = btp_skip_string(&local_input, "in");
+    location->column += chars;
+    if (0 == chars)
+    {
+        location->message = "Keyword \"in\" expected after memory address.";
+        return false;
+    }
+
+    /* Skip spaces. */
+    chars = btp_skip_char_sequence(&local_input, ' ');
+    location->column += chars;
+    if (0 == chars)
+    {
+        location->message = "Space expected after 'in'.";
+        return false;
+    }
+
+    /* C++ specific case for "0xfafa in vtable for function ()" */
+    chars = btp_skip_string(&local_input, "vtable");
+    location->column += chars;
+    if (0 <  chars)
+    {
+        chars = btp_skip_char_sequence(&local_input, ' ');
+        location->column += chars;
+        if (0 == chars)
+        {
+            location->message = "Space expected after 'vtable'.";
+            return false;
+        }
+
+        chars = btp_skip_string(&local_input, "for");
+        location->column += chars;
+        if (0 == chars)
+        {
+            location->message = "Keyword \"for\" expected.";
+            return false;
+        }
+
+        chars = btp_skip_char_sequence(&local_input, ' ');
+        location->column += chars;
+        if (0 == chars)
+        {
+            location->message = "Space expected after 'for'.";
+            return false;
+        }
+    }
+
+    if (!btp_frame_parse_function_call(&local_input,
+                                       function_name,
+                                       function_type,
+                                       location))
+    {
+        /* Do not update location here, it has been modified by the
+           called function. */
+        return false;
+    }
+
+    *input = local_input;
+    return true;
+}
+
+bool
+btp_frame_parse_file_location(char **input,
+                              char **file,
+                              unsigned *fileline,
+                              struct btp_location *location)
+{
+    char *local_input = *input;
+    int line, column;
+    if (0 == btp_skip_char_span_location(&local_input, " \n", &line, &column))
+    {
+        location->message = "Expected a space or a newline.";
+        return false;
+    }
+    btp_location_add(location, line, column);
+
+    int chars = btp_skip_string(&local_input, "at");
+    if (0 == chars)
+    {
+        chars = btp_skip_string(&local_input, "from");
+        if (0 == chars)
+        {
+            location->message = "Expected 'at' or 'from'.";
+            return false;
+        }
+    }
+    location->column += chars;
+
+    int spaces = btp_skip_char_sequence(&local_input, ' ');
+    location->column += spaces;
+    if (0 == spaces)
+    {
+        location->message = "Expected a space before file location.";
+        return false;
+    }
+
+    char *file_name;
+    chars = btp_parse_char_span(&local_input, BTP_alnum "_/\\+.-", &file_name);
+    location->column += chars;
+    if (0 == chars)
+    {
+        location->message = "Expected a file name.";
+        return false;
+    }
+
+    if (btp_skip_char(&local_input, ':'))
+    {
+        location->column += 1;
+        int digits = btp_parse_unsigned_integer(&local_input, fileline);
+        location->column += digits;
+        if (0 == digits)
+        {
+            free(file_name);
+            location->message = "Expected a line number.";
+            return false;
+        }
+    }
+    else
+        *fileline = -1;
+
+    *file = file_name;
+    *input = local_input;
+    return true;
+}
+
+struct btp_frame *
+btp_frame_parse_header(char **input,
+                       struct btp_location *location)
+{
+    char *local_input = *input;
+    struct btp_frame *imframe = btp_frame_new(); /* im - intermediate */
+    int chars = btp_frame_parse_frame_start(&local_input,
+                                            &imframe->number);
+
+    location->column += chars;
+    if (0 == chars)
+    {
+        location->message = "Frame start sequence expected.";
+        btp_frame_free(imframe);
+        return NULL;
+    }
+
+    struct btp_location internal_location;
+    btp_location_init(&internal_location);
+    if (btp_frame_parse_address_in_function(&local_input,
+                                            &imframe->address,
+                                            &imframe->function_name,
+                                            &imframe->function_type,
+                                            &internal_location))
+    {
+        btp_location_add(location,
+                         internal_location.line,
+                         internal_location.column);
+
+        /* Optional section " from file.c:65" */
+        /* Optional section " at file.c:65" */
+        btp_location_init(&internal_location);
+        if (btp_frame_parse_file_location(&local_input,
+                                          &imframe->source_file,
+                                          &imframe->source_line,
+                                          &internal_location))
+        {
+            btp_location_add(location,
+                             internal_location.line,
+                             internal_location.column);
+        }
+    }
+    else
+    {
+        btp_location_init(&internal_location);
+        if (btp_frame_parse_function_call(&local_input,
+                                          &imframe->function_name,
+                                          &imframe->function_type,
+                                          &internal_location))
+        {
+            btp_location_add(location,
+                             internal_location.line,
+                             internal_location.column);
+
+            /* Mandatory section " at file.c:65" */
+            btp_location_init(&internal_location);
+            if (!btp_frame_parse_file_location(&local_input,
+                                               &imframe->source_file,
+                                               &imframe->source_line,
+                                               &internal_location))
+            {
+                location->message = "Function call in the frame header "
+                    "misses mandatory \"at file.c:xy\" section";
+                btp_frame_free(imframe);
+                return NULL;
+            }
+
+            btp_location_add(location,
+                             internal_location.line,
+                             internal_location.column);
+        }
+        else
+        {
+            int chars = btp_skip_string(&local_input, "<signal handler called>");
+            if (0 < chars)
+            {
+                location->column += chars;
+                imframe->signal_handler_called = true;
+            }
+            else
+            {
+                location->message = "Frame header variant not recognized.";
+                btp_frame_free(imframe);
+                return NULL;
+            }
+        }
+    }
+
+    *input = local_input;
+    return imframe;
+}
diff --git a/lib/btparser/frame.h b/lib/btparser/frame.h
new file mode 100644
index 00000000..966dd5d2
--- /dev/null
+++ b/lib/btparser/frame.h
@@ -0,0 +1,470 @@
+/*
+    frame.h
+
+    Copyright (C) 2010  Red Hat, Inc.
+
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License along
+    with this program; if not, write to the Free Software Foundation, Inc.,
+    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+#ifndef BTPARSER_FRAME_H
+#define BTPARSER_FRAME_H
+
+#include <stdbool.h>
+#include <stdint.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+struct strbuf;
+struct btp_location;
+
+/**
+ * A frame representing a function call or a signal handler on a call
+ * stack of a thread.
+ */
+struct btp_frame
+{
+    /**
+     * A function name or NULL. If it's NULL, signal_handler_called is
+     * true.
+     */
+    char *function_name;
+    /**
+     * A function type, or NULL if it isn't present.
+     */
+    char *function_type;
+    /**
+     * A frame number in a thread. It does not necessarily show the
+     * actual position in the thread, as this number is set by the
+     * parser and never updated.
+     */
+    unsigned number;
+    /**
+     * The name of the source file containing the function definition,
+     * or the name of the binary file (.so) with the binary code of
+     * the function, or NULL.
+     */
+    char *source_file;
+    /**
+     * A line number in the source file, determining the position of
+     * the function definition, or -1 when unknown.
+     */
+    unsigned source_line;
+    /**
+     * Signal handler was called on this frame.
+     */
+    bool signal_handler_called;
+    /**
+     * The function address in the computer memory, or -1 when the
+     * address is unknown.
+     */
+    uint64_t address;
+    /**
+     * A sibling frame residing below this one, or NULL if this is the
+     * last frame in the parent thread.
+     */
+    struct btp_frame *next;
+};
+
+/**
+ * Creates and initializes a new frame structure.
+ * @returns
+ * It never returns NULL. The returned pointer must be released by
+ * calling the function btp_frame_free().
+ */
+struct btp_frame *
+btp_frame_new();
+
+/**
+ * Initializes all members of the frame structure to their default
+ * values.  No memory is released, members are simply overwritten.
+ * This is useful for initializing a frame structure placed on the
+ * stack.
+ */
+void
+btp_frame_init(struct btp_frame *frame);
+
+/**
+ * Releases the memory held by the frame. The frame siblings are not
+ * released.
+ * @param frame
+ * If the frame is NULL, no operation is performed.
+ */
+void
+btp_frame_free(struct btp_frame *frame);
+
+/**
+ * Creates a duplicate of the frame.
+ * @param frame
+ * It must be non-NULL pointer. The frame is not modified by calling
+ * this function.
+ * @param siblings
+ * Whether to duplicate also siblings referenced by frame->next.  If
+ * false, frame->next is not duplicated for the new frame, but it is
+ * set to NULL.
+ * @returns
+ * This function never returns NULL. If the returned duplicate is not
+ * shallow, it must be released by calling the function
+ * btp_frame_free().
+ */
+struct btp_frame *
+btp_frame_dup(struct btp_frame *frame,
+              bool siblings);
+
+/**
+ * Checks whether the frame represents a call of function with certain
+ * function name.
+ */
+bool
+btp_frame_calls_func(struct btp_frame *frame,
+                     const char *function_name);
+
+/**
+ * Checks whether the frame represents a call of function with certain
+ * function name, which resides in a source file.
+ * @param source_file
+ * The frame's source_file is searched for the source_file as a
+ * substring.
+ */
+bool
+btp_frame_calls_func_in_file(struct btp_frame *frame,
+                             const char *function_name,
+                             const char *source_file);
+
+/**
+ * Checks whether the frame represents a call of function with certain
+ * function name, which resides in one of the source files.
+ * @param source_file0
+ * The frame's source_file is searched for the source_file0 as a
+ * substring.
+ * @returns
+ * True if the frame corresponds to a function with function_name,
+ * residing in the source_file0, or source_file1.
+ */
+bool
+btp_frame_calls_func_in_file2(struct btp_frame *frame,
+                              const char *function_name,
+                              const char *source_file0,
+                              const char *source_file1);
+
+/**
+ * Checks whether the frame represents a call of function with certain
+ * function name, which resides in one of the source files.
+ * @param source_file0
+ * The frame's source_file is searched for the source_file0 as a
+ * substring.
+ * @returns
+ * True if the frame corresponds to a function with function_name,
+ * residing in the source_file0, source_file1, or source_file2.
+ */
+bool
+btp_frame_calls_func_in_file3(struct btp_frame *frame,
+                              const char *function_name,
+                              const char *source_file0,
+                              const char *source_file1,
+                              const char *source_file2);
+
+/**
+ * Checks whether the frame represents a call of function with certain
+ * function name, which resides in one of the source files.
+ * @param source_file0
+ * The frame's source_file is searched for the source_file0 as a
+ * substring.
+ * @returns
+ * True if the frame corresponds to a function with function_name,
+ * residing in the source_file0, source_file1, source_file2, or
+ * source_file3.
+ */
+bool
+btp_frame_calls_func_in_file4(struct btp_frame *frame,
+                              const char *function_name,
+                              const char *source_file0,
+                              const char *source_file1,
+                              const char *source_file2,
+                              const char *source_file3);
+
+/**
+ * Compares two frames.
+ * @param f1
+ * It must be non-NULL pointer. It's not modified by calling this
+ * function.
+ * @param f2
+ * It must be non-NULL pointer. It's not modified by calling this
+ * function.
+ * @param compare_number
+ * Indicates whether to include the frame numbers in the
+ * comparsion. If set to false, the frame numbers are ignored.
+ * @returns
+ * Returns 0 if the frames are same.  Returns negative number if f1 is
+ * found to be 'less' than f2.  Returns positive number if f1 is found
+ * to be 'greater' than f2.
+ */
+int
+btp_frame_cmp(struct btp_frame *f1,
+              struct btp_frame *f2,
+              bool compare_number);
+
+/**
+ * Puts the frame 'b' to the bottom of the stack 'a'. In other words,
+ * it finds the last sibling of the frame 'a', and appends the frame
+ * 'b' to this last sibling.
+ */
+void
+btp_frame_add_sibling(struct btp_frame *a,
+                      struct btp_frame *b);
+
+/**
+ * Appends the textual representation of the frame to the string
+ * buffer.
+ * @param frame
+ * It must be non-NULL pointer. It's not modified by calling this
+ * function.
+ */
+void
+btp_frame_append_to_str(struct btp_frame *frame,
+                        struct strbuf *str,
+                        bool verbose);
+
+/**
+ * If the input contains a complete frame, this function parses the
+ * frame text, returns it in a structure, and moves the input pointer
+ * after the frame.  If the input does not contain proper, complete
+ * frame, the function does not modify input and returns NULL.
+ * @returns
+ * Allocated pointer with a frame structure. The pointer should be
+ * released by btp_frame_free().
+ * @param location
+ * The caller must provide a pointer to an instance of btp_location
+ * here.  When this function returns NULL, the structure will contain
+ * the error line, column, and message.  The line and column members
+ * of the location are gradually increased as the parser handles the
+ * input, so the location should be initialized before calling this
+ * function to get reasonable values.
+ */
+struct btp_frame *
+btp_frame_parse(char **input,
+                struct btp_location *location);
+
+/**
+ * If the input contains a proper frame start section, parse the frame
+ * number, and move the input pointer after this section. Otherwise do
+ * not modify input.
+ * @returns
+ * The number of characters parsed from input. 0 if the input does not
+ * contain a frame start.
+ * @code
+ * "#1 "
+ * "#255  "
+ * @endcode
+ */
+int
+btp_frame_parse_frame_start(char **input, unsigned *number);
+
+/**
+ * Parses C++ operator on input.
+ * Supports even 'operator new[]' and 'operator delete[]'.
+ * @param target
+ * The parsed operator name is appened to the string buffer provided,
+ * if an operator is found. Otherwise the string buffer is not
+ * changed.
+ * @returns
+ * The number of characters parsed from input. 0 if the input does not
+ * contain operator.
+ */
+int
+btp_frame_parseadd_operator(char **input,
+                            struct strbuf *target);
+
+/**
+ * Parses a part of function name from the input.
+ * @param target
+ * Pointer to a non-allocated pointer. This function will set
+ * the pointer to newly allocated memory containing the name chunk,
+ * if it returns positive, nonzero value.
+ * @returns
+ * The number of characters parsed from input. 0 if the input does not
+ * contain a part of function name.
+ */
+int
+btp_frame_parse_function_name_chunk(char **input,
+                                    bool space_allowed,
+                                    char **target);
+
+/**
+ * If the input buffer contains part of function name containing braces,
+ * for example "(anonymous namespace)", parse it, append the contents
+ * to target and move input after the braces.
+ * Otherwise do not modify niether the input nor the target.
+ * @returns
+ * The number of characters parsed from input. 0 if the input does not
+ * contain a braced part of function name.
+ */
+int
+btp_frame_parse_function_name_braces(char **input,
+                                     char **target);
+
+/**
+ * @returns
+ * The number of characters parsed from input. 0 if the input does not
+ * contain a template part of function name.
+ */
+int
+btp_frame_parse_function_name_template(char **input,
+                                       char **target);
+
+/**
+ * Parses the function name, which is a part of the frame header, from
+ * the input. If the frame header contains also the function type,
+ * it's also parsed.
+ * @param function_name
+ * A pointer pointing to an uninitialized pointer. This function
+ * allocates a string and sets the pointer to it if it parses the
+ * function name from the input successfully.  The memory returned
+ * this way must be released by the caller using the function free().
+ * If this function returns true, this pointer is guaranteed to be
+ * non-NULL.
+ * @param location
+ * The caller must provide a pointer to an instance of btp_location
+ * here.  The line and column members of the location are gradually
+ * increased as the parser handles the input, so the location should
+ * be initialized before calling this function to get reasonable
+ * values.  When this function returns false (an error occurred), the
+ * structure will contain the error line, column, and message.
+ * @returns
+ * True if the input stream contained a function name, which has been
+ * parsed. False otherwise.
+ */
+bool
+btp_frame_parse_function_name(char **input,
+                              char **function_name,
+                              char **function_type,
+                              struct btp_location *location);
+
+/**
+ * Skips function arguments which are a part of the frame header, in
+ * the input stream.
+ * @param location
+ * The caller must provide a pointer to an instance of btp_location
+ * here.  The line and column members of the location are gradually
+ * increased as the parser handles the input, so the location should
+ * be initialized before calling this function to get reasonable
+ * values.  When this function returns false (an error occurred), the
+ * structure will contain the error line, column, and message.
+ */
+bool
+btp_frame_skip_function_args(char **input,
+                             struct btp_location *location);
+
+/**
+ * If the input contains proper function call, parse the function
+ * name and store it to result, move the input pointer after whole
+ * function call, and return true. Otherwise do not modify the input
+ * and return false.
+ *
+ * If this function returns true, the caller is responsible to free
+ * the the function_name.
+ * @todo
+ * Parse and return the function call arguments.
+ * @param location
+ * The caller must provide a pointer to an instance of btp_location
+ * here.  The line and column members of the location are gradually
+ * increased as the parser handles the input, so the location should
+ * be initialized before calling this function to get reasonable
+ * values.  When this function returns false (an error occurred), the
+ * structure will contain the error line, column, and message.
+ */
+bool
+btp_frame_parse_function_call(char **input,
+                              char **function_name,
+                              char **function_type,
+                              struct btp_location *location);
+
+/**
+ * If the input contains address and function call, parse them, move
+ * the input pointer after this sequence, and return true.
+ * Otherwise do not modify the input and return false.
+ *
+ * If this function returns true, the caller is responsible to free
+ * the parameter function.
+ *
+ * @code
+ * 0x000000322160e7fd in fsync ()
+ * 0x000000322222987a in write_to_temp_file (
+ * filename=0x18971b0 "/home/jfclere/.recently-used.xbel",
+ * contents=<value optimized out>, length=29917, error=0x7fff3cbe4110)
+ * @endcode
+ * @param location
+ * The caller must provide a pointer to an instance of btp_location
+ * here.  The line and column members of the location are gradually
+ * increased as the parser handles the input, so the location should
+ * be initialized before calling this function to get reasonable
+ * values.  When this function returns false (an error occurred), the
+ * structure will contain the error line, column, and message.
+ */
+bool
+btp_frame_parse_address_in_function(char **input,
+                                    uint64_t *address,
+                                    char **function_name,
+                                    char **function_type,
+                                    struct btp_location *location);
+
+/**
+ * If the input contains sequence "from path/to/file:fileline" or "at
+ * path/to/file:fileline", parse it, move the input pointer after this
+ * sequence and return true. Otherwise do not modify the input and
+ * return false.
+ *
+ * The ':' followed by line number is optional. If it is not present,
+ * the fileline is set to -1.
+ * @param location
+ * The caller must provide a pointer to an instance of btp_location
+ * here.  The line and column members of the location are gradually
+ * increased as the parser handles the input, so the location should
+ * be initialized before calling this function to get reasonable
+ * values.  When this function returns false (an error occurred), the
+ * structure will contain the error line, column, and message.
+ */
+bool
+btp_frame_parse_file_location(char **input,
+                              char **file,
+                              unsigned *fileline,
+                              struct btp_location *location);
+
+/**
+ * If the input contains proper frame header, this function
+ * parses the frame header text, moves the input pointer
+ * after the frame header, and returns a frame struct.
+ * If the input does not contain proper frame header, this function
+ * returns NULL and does not modify input.
+ * @param location
+ * The caller must provide a pointer to an instance of btp_location
+ * here.  The line and column members of the location are gradually
+ * increased as the parser handles the input, so the location should
+ * be initialized before calling this function to get reasonable
+ * values.  When this function returns false (an error occurred), the
+ * structure will contain the error line, column, and message.
+ * @returns
+ * Newly created frame struct or NULL. The returned frame struct
+ * should be released by btp_frame_free().
+ */
+struct btp_frame *
+btp_frame_parse_header(char **input,
+                       struct btp_location *location);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
diff --git a/lib/btparser/location.c b/lib/btparser/location.c
new file mode 100644
index 00000000..ade706f2
--- /dev/null
+++ b/lib/btparser/location.c
@@ -0,0 +1,78 @@
+/*
+    location.c
+
+    Copyright (C) 2010  Red Hat, Inc.
+
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License along
+    with this program; if not, write to the Free Software Foundation, Inc.,
+    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+#include "location.h"
+#include <stdlib.h> /* contains NULL */
+
+void
+btp_location_init(struct btp_location *location)
+{
+    location->line = 1;
+    location->column = 0;
+    location->message = NULL;
+}
+
+void
+btp_location_add(struct btp_location *location,
+                 int add_line,
+                 int add_column)
+{
+    btp_location_add_ext(&location->line,
+                         &location->column,
+                         add_line,
+                         add_column);
+}
+
+void
+btp_location_add_ext(int *line,
+                     int *column,
+                     int add_line,
+                     int add_column)
+{
+    if (add_line > 1)
+    {
+        *line += add_line - 1;
+        *column = add_column;
+    }
+    else
+        *column += add_column;
+}
+
+void
+btp_location_eat_char(struct btp_location *location,
+                      char c)
+{
+    btp_location_eat_char_ext(&location->line,
+                              &location->column,
+                              c);
+}
+
+void
+btp_location_eat_char_ext(int *line,
+                          int *column,
+                          char c)
+{
+    if (c == '\n')
+    {
+        *line += 1;
+        *column = 0;
+    }
+    else
+        *column += 1;
+}
diff --git a/lib/btparser/location.h b/lib/btparser/location.h
new file mode 100644
index 00000000..0d620205
--- /dev/null
+++ b/lib/btparser/location.h
@@ -0,0 +1,118 @@
+/*
+    location.h
+
+    Copyright (C) 2010  Red Hat, Inc.
+
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License along
+    with this program; if not, write to the Free Software Foundation, Inc.,
+    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+#ifndef BTPARSER_LOCATION_H
+#define BTPARSER_LOCATION_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/**
+ * A location in the backtrace file with an attached message.
+ * It's used for error reporting: the line and the column points to
+ * the place where a parser error occurred, and the message explains
+ * what the parser expected and didn't find on that place.
+ */
+struct btp_location
+{
+    /** Starts from 1. */
+    int line;
+    /** Starts from 0. */
+    int column;
+    /**
+     * Error message related to the line and column.  Do not release
+     * the memory this pointer points to.
+     */
+    const char *message;
+};
+
+/**
+ * Initializes all members of the location struct to their default
+ * values.  No memory is allocated or released by this function.
+ */
+void
+btp_location_init(struct btp_location *location);
+
+/**
+ * Adds a line and a column to specific location.
+ * @note
+ * If the line is not 1 (meaning the first line), the column in the
+ * location structure is overwritten by the provided add_column value.
+ * Otherwise the add_column value is added to the column member of the
+ * location structure.
+ * @param location
+ * The structure to be modified. It must be a valid pointer.
+ * @param add_line
+ * Starts from 1. It means that if add_line is 1, the line member of the
+ * location structure is not changed.
+ * @param add_column
+ * Starts from 0.
+ */
+void
+btp_location_add(struct btp_location *location,
+                 int add_line,
+                 int add_column);
+
+/**
+ * Adds a line column pair to another line column pair.
+ * @note
+ * If the add_line is not 1 (meaning the frist line), the column is
+ * overwritten by the provided add_column value.  Otherwise the
+ * add_column value is added to the column.
+ * @param add_line
+ * Starts from 1. It means that if add_line is 1, the line is not
+ * changed.
+ * @param add_column
+ * Starts from 0.
+ */
+void
+btp_location_add_ext(int *line,
+                     int *column,
+                     int add_line,
+                     int add_column);
+
+/**
+ * Updates the line and column of the location by moving "after" the
+ * char c. If c is a newline character, the line number is increased
+ * and the column is set to 0. Otherwise the column is increased by 1.
+ */
+void
+btp_location_eat_char(struct btp_location *location,
+                      char c);
+
+/**
+ * Updates the line and the column by moving "after" the char c. If c
+ * is a newline character, the line number is increased and the column
+ * is set to 0. Otherwise the column is increased.
+ * @param line
+ * Must be a valid pointer.
+ * @param column
+ * Must be a valid pointer.
+ */
+void
+btp_location_eat_char_ext(int *line,
+                          int *column,
+                          char c);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
diff --git a/lib/btparser/normalize.c b/lib/btparser/normalize.c
new file mode 100644
index 00000000..4bbee99c
--- /dev/null
+++ b/lib/btparser/normalize.c
@@ -0,0 +1,68 @@
+/*
+    normalize.c
+
+    Copyright (C) 2010  Red Hat, Inc.
+
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License along
+    with this program; if not, write to the Free Software Foundation, Inc.,
+    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+#include "normalize.h"
+#include "frame.h"
+#include "thread.h"
+#include "backtrace.h"
+#include <string.h>
+
+void
+btp_normalize_thread(struct btp_thread *thread)
+{
+    btp_normalize_dbus_thread(thread);
+    btp_normalize_gdk_thread(thread);
+    btp_normalize_glib_thread(thread);
+    btp_normalize_glibc_thread(thread);
+    btp_normalize_libstdcpp_thread(thread);
+    btp_normalize_linux_thread(thread);
+    btp_normalize_xorg_thread(thread);
+
+    /* If the last frame has address 0x0000 and its name is '??',
+     * remove it. This frame is not really invalid, and it affects
+     * backtrace quality rating. See Red Hat Bugzilla bug #592523.
+     * @code
+     * #2  0x00007f4dcebbd62d in clone ()
+     * at ../sysdeps/unix/sysv/linux/x86_64/clone.S:112
+     * No locals.
+     * #3  0x0000000000000000 in ?? ()
+     * @endcode
+     */
+    struct btp_frame *last = thread->frames;
+    while (last && last->next)
+        last = last->next;
+    if (last &&
+        last->address == 0x0000 &&
+        last->function_name &&
+        0 == strcmp(last->function_name, "??"))
+    {
+        btp_thread_remove_frame(thread, last);
+    }
+}
+
+void
+btp_normalize_backtrace(struct btp_backtrace *backtrace)
+{
+    struct btp_thread *thread = backtrace->threads;
+    while (thread)
+    {
+        btp_normalize_thread(thread);
+        thread = thread->next;
+    }
+}
diff --git a/lib/btparser/normalize.h b/lib/btparser/normalize.h
new file mode 100644
index 00000000..35fd2836
--- /dev/null
+++ b/lib/btparser/normalize.h
@@ -0,0 +1,74 @@
+/*
+    normalize.h
+
+    Copyright (C) 2010  Red Hat, Inc.
+
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License along
+    with this program; if not, write to the Free Software Foundation, Inc.,
+    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+#ifndef BTPARSER_NORMALIZE_H
+#define BTPARSER_NORMALIZE_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+struct btp_thread;
+struct btp_backtrace;
+
+void
+btp_normalize_thread(struct btp_thread *thread);
+
+void
+btp_normalize_backtrace(struct btp_backtrace *backtrace);
+
+/**
+ */
+void
+btp_normalize_dbus_thread(struct btp_thread *thread);
+
+void
+btp_normalize_gdk_thread(struct btp_thread *thread);
+
+void
+btp_normalize_glib_thread(struct btp_thread *thread);
+
+/**
+ * Checks whether the thread it contains some function used to exit
+ * application.  If a frame with the function is found, it is
+ * returned.  If there are multiple frames with abort function, the
+ * lowest one is returned.
+ * @returns
+ * Returns NULL if such a frame is not found.
+ */
+struct btp_frame *
+btp_glibc_thread_find_exit_frame(struct btp_thread *thread);
+
+void
+btp_normalize_glibc_thread(struct btp_thread *thread);
+
+void
+btp_normalize_libstdcpp_thread(struct btp_thread *thread);
+
+void
+btp_normalize_linux_thread(struct btp_thread *thread);
+
+void
+btp_normalize_xorg_thread(struct btp_thread *thread);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
diff --git a/lib/btparser/normalize_dbus.c b/lib/btparser/normalize_dbus.c
new file mode 100644
index 00000000..d3d6a13a
--- /dev/null
+++ b/lib/btparser/normalize_dbus.c
@@ -0,0 +1,44 @@
+/*
+    normalize_dbus.c
+
+    Copyright (C) 2010  Red Hat, Inc.
+
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License along
+    with this program; if not, write to the Free Software Foundation, Inc.,
+    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+#include "normalize.h"
+#include "frame.h"
+#include "thread.h"
+#include <stdbool.h>
+
+void
+btp_normalize_dbus_thread(struct btp_thread *thread)
+{
+    struct btp_frame *frame = thread->frames;
+    while (frame)
+    {
+        struct btp_frame *next_frame = frame->next;
+
+        /* Remove frames which are not a cause of the crash. */
+        bool removable =
+            btp_frame_calls_func_in_file(frame, "gerror_to_dbus_error_message", "dbus-gobject.c") ||
+            btp_frame_calls_func_in_file(frame, "dbus_g_method_return_error", "dbus-gobject.c");
+        if (removable)
+        {
+            btp_thread_remove_frame(thread, frame);
+        }
+
+        frame = next_frame;
+    }
+}
diff --git a/lib/btparser/normalize_gdk.c b/lib/btparser/normalize_gdk.c
new file mode 100644
index 00000000..e9c4ef6a
--- /dev/null
+++ b/lib/btparser/normalize_gdk.c
@@ -0,0 +1,44 @@
+/*
+    normalize_gdk.c
+
+    Copyright (C) 2010  Red Hat, Inc.
+
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License along
+    with this program; if not, write to the Free Software Foundation, Inc.,
+    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+#include "normalize.h"
+#include "frame.h"
+#include "thread.h"
+#include <stdbool.h>
+
+void
+btp_normalize_gdk_thread(struct btp_thread *thread)
+{
+    struct btp_frame *frame = thread->frames;
+    while (frame)
+    {
+        struct btp_frame *next_frame = frame->next;
+
+        /* Remove frames which are not a cause of the crash. */
+        bool removable =
+            btp_frame_calls_func_in_file(frame, "gdk_x_error", "gdkmain-x11.c");
+
+        if (removable)
+        {
+            btp_thread_remove_frame(thread, frame);
+        }
+
+        frame = next_frame;
+    }
+}
diff --git a/lib/btparser/normalize_glib.c b/lib/btparser/normalize_glib.c
new file mode 100644
index 00000000..b5c12b60
--- /dev/null
+++ b/lib/btparser/normalize_glib.c
@@ -0,0 +1,60 @@
+/*
+    normalize_glib.c
+
+    Copyright (C) 2010  Red Hat, Inc.
+
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License along
+    with this program; if not, write to the Free Software Foundation, Inc.,
+    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+#include "normalize.h"
+#include "frame.h"
+#include "thread.h"
+#include "utils.h"
+#include <stdbool.h>
+#include <string.h>
+
+void
+btp_normalize_glib_thread(struct btp_thread *thread)
+{
+    struct btp_frame *frame = thread->frames;
+    while (frame)
+    {
+        struct btp_frame *next_frame = frame->next;
+
+        /* Normalize frame names. */
+        if (frame->function_name &&
+            0 == strncmp(frame->function_name, "IA__g_", strlen("IA__g_")))
+        {
+            /* Remove the IA__ prefix. The strcpy function cannot be
+             * used for that because the source and destination
+             * pointers overlap. */
+            char *p = frame->function_name;
+            while ((*p = p[4]) != '\0')
+                ++p;
+        }
+
+        /* Remove frames which are not a cause of the crash. */
+        bool removable =
+            btp_frame_calls_func_in_file2(frame, "g_log", "gmessages.c", "libglib") ||
+            btp_frame_calls_func_in_file2(frame, "g_logv", "gmessages.c", "libglib") ||
+            btp_frame_calls_func_in_file2(frame, "g_assertion_message", "gtestutils.c", "libglib") ||
+            btp_frame_calls_func_in_file2(frame, "g_assertion_message_expr", "gtestutils.c", "libglib");
+        if (removable)
+        {
+            btp_thread_remove_frame(thread, frame);
+        }
+
+        frame = next_frame;
+    }
+}
diff --git a/lib/btparser/normalize_glibc.c b/lib/btparser/normalize_glibc.c
new file mode 100644
index 00000000..ea40ba9d
--- /dev/null
+++ b/lib/btparser/normalize_glibc.c
@@ -0,0 +1,120 @@
+/*
+    normalize_glibc.c
+
+    Copyright (C) 2010  Red Hat, Inc.
+
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License along
+    with this program; if not, write to the Free Software Foundation, Inc.,
+    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+#include "normalize.h"
+#include "frame.h"
+#include "thread.h"
+#include "utils.h"
+#include <string.h>
+#include <stdlib.h>
+#include <assert.h>
+
+struct btp_frame *
+btp_glibc_thread_find_exit_frame(struct btp_thread *thread)
+{
+    struct btp_frame *frame = thread->frames;
+    struct btp_frame *result = NULL;
+    while (frame)
+    {
+        bool is_exit_frame =
+            btp_frame_calls_func_in_file(frame, "__run_exit_handlers", "exit.c") ||
+            btp_frame_calls_func_in_file4(frame, "raise", "pt-raise.c", "libc.so", "libc-", "libpthread.so") ||
+            btp_frame_calls_func_in_file(frame, "exit", "exit.c") ||
+            btp_frame_calls_func_in_file3(frame, "abort", "abort.c", "libc.so", "libc-") ||
+            /* Terminates a function in case of buffer overflow. */
+            btp_frame_calls_func_in_file2(frame, "__chk_fail", "chk_fail.c", "libc.so");
+
+        if (is_exit_frame)
+            result = frame;
+
+        frame = frame->next;
+    }
+
+    return result;
+}
+
+
+void
+btp_normalize_glibc_thread(struct btp_thread *thread)
+{
+    /* Find the exit frame and remove everything above it. */
+    struct btp_frame *exit_frame = btp_glibc_thread_find_exit_frame(thread);
+    if (exit_frame)
+    {
+        bool success = btp_thread_remove_frames_above(thread, exit_frame);
+        assert(success); /* if this fails, some code become broken */
+        success = btp_thread_remove_frame(thread, exit_frame);
+        assert(success); /* if this fails, some code become broken */
+    }
+
+    /* Standard function filtering loop. */
+    struct btp_frame *frame = thread->frames;
+    while (frame)
+    {
+        struct btp_frame *next_frame = frame->next;
+
+        /* Normalize frame names. */
+#define NORMALIZE_ARCH_SPECIFIC(func)                                   \
+        if (btp_frame_calls_func_in_file2(frame, "__" func "_sse2", func ".S", "libc.so") || \
+            btp_frame_calls_func_in_file2(frame, "__" func "_ssse3", func ".S", "libc.so") || \
+            btp_frame_calls_func_in_file2(frame, "__" func "_ia32", func ".S", "libc.so")) \
+        {                                                               \
+            strcpy(frame->function_name, func);                         \
+        }
+
+        NORMALIZE_ARCH_SPECIFIC("memchr");
+        NORMALIZE_ARCH_SPECIFIC("memcmp");
+        NORMALIZE_ARCH_SPECIFIC("memcpy");
+        NORMALIZE_ARCH_SPECIFIC("memset");
+        NORMALIZE_ARCH_SPECIFIC("rawmemchr");
+        NORMALIZE_ARCH_SPECIFIC("strcat");
+        NORMALIZE_ARCH_SPECIFIC("strchr");
+        NORMALIZE_ARCH_SPECIFIC("strchrnul");
+        NORMALIZE_ARCH_SPECIFIC("strcmp");
+        NORMALIZE_ARCH_SPECIFIC("strcpy");
+        NORMALIZE_ARCH_SPECIFIC("strcspn");
+        NORMALIZE_ARCH_SPECIFIC("strlen");
+        NORMALIZE_ARCH_SPECIFIC("strncmp");
+        NORMALIZE_ARCH_SPECIFIC("strpbrk");
+        NORMALIZE_ARCH_SPECIFIC("strrchr");
+        NORMALIZE_ARCH_SPECIFIC("strspn");
+        NORMALIZE_ARCH_SPECIFIC("strtok");
+
+        /* Remove frames which are not a cause of the crash. */
+        bool removable =
+            btp_frame_calls_func(frame, "__assert_fail") ||
+            btp_frame_calls_func(frame, "__strcat_chk") ||
+            btp_frame_calls_func(frame, "__strcpy_chk") ||
+            btp_frame_calls_func(frame, "__strncpy_chk") ||
+            btp_frame_calls_func(frame, "__vsnprintf_chk") ||
+            btp_frame_calls_func(frame, "___vsnprintf_chk") ||
+            btp_frame_calls_func(frame, "__snprintf_chk") ||
+            btp_frame_calls_func(frame, "___snprintf_chk") ||
+            btp_frame_calls_func(frame, "__vasprintf_chk");
+        if (removable)
+        {
+            bool success = btp_thread_remove_frames_above(thread, frame);
+            assert(success);
+            success = btp_thread_remove_frame(thread, frame);
+            assert(success);
+        }
+
+        frame = next_frame;
+    }
+}
diff --git a/lib/btparser/normalize_libstdcpp.c b/lib/btparser/normalize_libstdcpp.c
new file mode 100644
index 00000000..1f833ded
--- /dev/null
+++ b/lib/btparser/normalize_libstdcpp.c
@@ -0,0 +1,46 @@
+/*
+    normalize_libstdcpp.c
+
+    Copyright (C) 2010  Red Hat, Inc.
+
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License along
+    with this program; if not, write to the Free Software Foundation, Inc.,
+    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+#include "normalize.h"
+#include "frame.h"
+#include "thread.h"
+#include <stdbool.h>
+
+void
+btp_normalize_libstdcpp_thread(struct btp_thread *thread)
+{
+    struct btp_frame *frame = thread->frames;
+    while (frame)
+    {
+        struct btp_frame *next_frame = frame->next;
+
+        /* Remove frames which are not a cause of the crash. */
+        bool removable =
+            btp_frame_calls_func_in_file(frame, "__gnu_cxx::__verbose_terminate_handler", "vterminate.cc") ||
+            btp_frame_calls_func_in_file(frame, "__cxxabiv1::__terminate", "eh_terminate.cc") ||
+            btp_frame_calls_func_in_file(frame, "std::terminate", "eh_terminate.cc") ||
+            btp_frame_calls_func_in_file(frame, "__cxxabiv1::__cxa_throw", "eh_throw.cc");
+        if (removable)
+        {
+            btp_thread_remove_frame(thread, frame);
+        }
+
+        frame = next_frame;
+    }
+}
diff --git a/lib/btparser/normalize_linux.c b/lib/btparser/normalize_linux.c
new file mode 100644
index 00000000..8df9f9c2
--- /dev/null
+++ b/lib/btparser/normalize_linux.c
@@ -0,0 +1,41 @@
+/*
+    normalize_linux.c
+
+    Copyright (C) 2010  Red Hat, Inc.
+
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License along
+    with this program; if not, write to the Free Software Foundation, Inc.,
+    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+#include "normalize.h"
+#include "utils.h"
+#include "frame.h"
+#include "thread.h"
+#include <stdbool.h>
+
+void
+btp_normalize_linux_thread(struct btp_thread *thread)
+{
+    struct btp_frame *frame = thread->frames;
+    while (frame)
+    {
+        struct btp_frame *next_frame = frame->next;
+
+        /* Remove frames which are not a cause of the crash. */
+        bool removable = btp_frame_calls_func(frame, "__kernel_vsyscall");
+        if (removable)
+            btp_thread_remove_frame(thread, frame);
+
+        frame = next_frame;
+    }
+}
diff --git a/lib/btparser/normalize_xorg.c b/lib/btparser/normalize_xorg.c
new file mode 100644
index 00000000..11e8d624
--- /dev/null
+++ b/lib/btparser/normalize_xorg.c
@@ -0,0 +1,46 @@
+/*
+    normalize_xorg.c
+
+    Copyright (C) 2010  Red Hat, Inc.
+
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License along
+    with this program; if not, write to the Free Software Foundation, Inc.,
+    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+#include "normalize.h"
+#include "frame.h"
+#include "thread.h"
+#include <stdbool.h>
+
+void
+btp_normalize_xorg_thread(struct btp_thread *thread)
+{
+    struct btp_frame *frame = thread->frames;
+    while (frame)
+    {
+        struct btp_frame *next_frame = frame->next;
+
+        /* Remove frames which are not a cause of the crash. */
+        bool removable =
+            btp_frame_calls_func_in_file(frame, "_XReply", "xcb_io.c") ||
+            btp_frame_calls_func_in_file(frame, "_XError", "XlibInt.c") ||
+            btp_frame_calls_func_in_file(frame, "XSync", "Sync.c") ||
+            btp_frame_calls_func_in_file(frame, "process_responses", "xcb_io.c");
+        if (removable)
+        {
+            btp_thread_remove_frame(thread, frame);
+        }
+
+        frame = next_frame;
+    }
+}
diff --git a/lib/btparser/thread.c b/lib/btparser/thread.c
new file mode 100644
index 00000000..af480eb3
--- /dev/null
+++ b/lib/btparser/thread.c
@@ -0,0 +1,364 @@
+/*
+    thread.c
+
+    Copyright (C) 2010  Red Hat, Inc.
+
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License along
+    with this program; if not, write to the Free Software Foundation, Inc.,
+    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+#include "thread.h"
+#include "frame.h"
+#include "strbuf.h"
+#include "utils.h"
+#include "location.h"
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+
+struct btp_thread *
+btp_thread_new()
+{
+    struct btp_thread *thread = btp_malloc(sizeof(struct btp_thread));
+    btp_thread_init(thread);
+    return thread;
+}
+
+void
+btp_thread_init(struct btp_thread *thread)
+{
+    thread->number = -1;
+    thread->frames = NULL;
+    thread->next = NULL;
+}
+
+void
+btp_thread_free(struct btp_thread *thread)
+{
+    if (!thread)
+        return;
+
+    while (thread->frames)
+    {
+        struct btp_frame *rm = thread->frames;
+        thread->frames = rm->next;
+        btp_frame_free(rm);
+    }
+
+    free(thread);
+}
+
+struct btp_thread *
+btp_thread_dup(struct btp_thread *thread, bool siblings)
+{
+    struct btp_thread *result = btp_thread_new();
+    memcpy(result, thread, sizeof(struct btp_thread));
+
+    /* Handle siblings. */
+    if (siblings)
+    {
+        if (result->next)
+            result->next = btp_thread_dup(result->next, true);
+    }
+    else
+        result->next = NULL; /* Do not copy that. */
+
+    result->frames = btp_frame_dup(result->frames, true);
+
+    return result;
+}
+
+int
+btp_thread_cmp(struct btp_thread *t1, struct btp_thread *t2)
+{
+    int number = t1->number - t2->number;
+    if (number != 0)
+        return number;
+    struct btp_frame *f1 = t1->frames, *f2 = t2->frames;
+    do {
+        if (f1 && !f2)
+            return 1;
+        else if (f2 && !f1)
+            return -1;
+        else if (f1 && f2)
+        {
+            int frames = btp_frame_cmp(f1, f2, true);
+            if (frames != 0)
+                return frames;
+            f1 = f1->next;
+            f2 = f2->next;
+        }
+    } while (f1 || f2);
+
+    return 0;
+}
+
+struct btp_thread *
+btp_thread_add_sibling(struct btp_thread *a, struct btp_thread *b)
+{
+    struct btp_thread *aa = a;
+    while (aa->next)
+        aa = aa->next;
+
+    aa->next = b;
+    return a;
+}
+
+int
+btp_thread_get_frame_count(struct btp_thread *thread)
+{
+    struct btp_frame *frame = thread->frames;
+    int count = 0;
+    while (frame)
+    {
+        frame = frame->next;
+        ++count;
+    }
+    return count;
+}
+
+void
+btp_thread_quality_counts(struct btp_thread *thread,
+                          int *ok_count,
+                          int *all_count)
+{
+    struct btp_frame *frame = thread->frames;
+    while (frame)
+    {
+        *all_count += 1;
+        if (frame->signal_handler_called ||
+            (frame->function_name
+             && 0 != strcmp(frame->function_name, "??")))
+        {
+            *ok_count += 1;
+        }
+        frame = frame->next;
+    }
+}
+
+float
+btp_thread_quality(struct btp_thread *thread)
+{
+    int ok_count = 0, all_count = 0;
+    btp_thread_quality_counts(thread, &ok_count, &all_count);
+    if (0 == all_count)
+        return 1;
+    return ok_count/(float)all_count;
+}
+
+bool
+btp_thread_remove_frame(struct btp_thread *thread,
+                        struct btp_frame *frame)
+{
+    struct btp_frame *loop_frame = thread->frames, *prev_frame = NULL;
+    while (loop_frame)
+    {
+        if (loop_frame == frame)
+        {
+            if (prev_frame)
+                prev_frame->next = loop_frame->next;
+            else
+                thread->frames = loop_frame->next;
+
+            btp_frame_free(loop_frame);
+            return true;
+        }
+        prev_frame = loop_frame;
+        loop_frame = loop_frame->next;
+    }
+    return false;
+}
+
+bool
+btp_thread_remove_frames_above(struct btp_thread *thread,
+                               struct btp_frame *frame)
+{
+    /* Check that the frame is present in the thread. */
+    struct btp_frame *loop_frame = thread->frames;
+    while (loop_frame)
+    {
+        if (loop_frame == frame)
+            break;
+        loop_frame = loop_frame->next;
+    }
+
+    if (!loop_frame)
+        return false;
+
+    /* Delete all the frames up to the frame. */
+    while (thread->frames != frame)
+    {
+        loop_frame = thread->frames->next;
+        btp_frame_free(thread->frames);
+        thread->frames = loop_frame;
+    }
+
+    return true;
+}
+
+void
+btp_thread_remove_frames_below_n(struct btp_thread *thread,
+                                 int n)
+{
+    assert(n >= 0);
+
+    /* Skip some frames to get the required stack depth. */
+    int i = n;
+    struct btp_frame *frame = thread->frames, *last_frame = NULL;
+    while (frame && i)
+    {
+        last_frame = frame;
+        frame = frame->next;
+        --i;
+    }
+
+    /* Delete the remaining frames. */
+    if (last_frame)
+        last_frame->next = NULL;
+    else
+        thread->frames = NULL;
+
+    while (frame)
+    {
+        struct btp_frame *delete_frame = frame;
+        frame = frame->next;
+        btp_frame_free(delete_frame);
+    }
+}
+
+void
+btp_thread_append_to_str(struct btp_thread *thread,
+                         struct strbuf *str,
+                         bool verbose)
+{
+    int framecount = btp_thread_get_frame_count(thread);
+    if (verbose)
+    {
+        strbuf_append_strf(str, "Thread no. %d (%d frames)\n",
+                               thread->number, framecount);
+    }
+    else
+        strbuf_append_str(str, "Thread\n");
+
+    struct btp_frame *frame = thread->frames;
+    while (frame)
+    {
+        btp_frame_append_to_str(frame, str, verbose);
+        frame = frame->next;
+    }
+}
+
+struct btp_thread *
+btp_thread_parse(char **input,
+                 struct btp_location *location)
+{
+    char *local_input = *input;
+
+    /* Read the Thread keyword, which is mandatory. */
+    int chars = btp_skip_string(&local_input, "Thread");
+    location->column += chars;
+    if (0 == chars)
+    {
+        location->message = "\"Thread\" header expected";
+        return NULL;
+    }
+
+    /* Skip spaces, at least one space is mandatory. */
+    int spaces = btp_skip_char_sequence(&local_input, ' ');
+    location->column += spaces;
+    if (0 == spaces)
+    {
+        location->message = "Space expected after the \"Thread\" keyword.";
+        return NULL;
+    }
+
+    /* Read thread number. */
+    struct btp_thread *imthread = btp_thread_new();
+    int digits = btp_parse_unsigned_integer(&local_input, &imthread->number);
+    location->column += digits;
+    if (0 == digits)
+    {
+        location->message = "Thread number expected.";
+        btp_thread_free(imthread);
+        return NULL;
+    }
+
+    /* Skip spaces after the thread number and before the parenthesis. */
+    spaces = btp_skip_char_sequence(&local_input, ' ');
+    location->column += spaces;
+    if (0 == spaces)
+    {
+        location->message = "Space expected after the thread number.";
+        btp_thread_free(imthread);
+        return NULL;
+    }
+
+    /* Read the Thread keyword in parenthesis, which is mandatory. */
+    chars = btp_skip_string(&local_input, "(Thread ");
+    location->column += chars;
+    if (0 == chars)
+    {
+        location->message = "Thread keyword in the parenthesis expected in the form '(Thread '.";
+        btp_thread_free(imthread);
+        return NULL;
+    }
+
+    /* Read the thread identification number. */
+    digits = btp_skip_unsigned_integer(&local_input);
+    location->column += digits;
+    if (0 == digits)
+    {
+        location->message = "The thread identification number expected.";
+        btp_thread_free(imthread);
+        return NULL;
+    }
+
+    /* Read the end of the parenthesis. */
+    chars = btp_skip_string(&local_input, "):\n");
+    if (0 == chars)
+    {
+        location->message = "The end of the parenthesis expected in the form of '):\\n'.";
+        btp_thread_free(imthread);
+        return NULL;
+    }
+    /* Add the newline from the last btp_skip_string. */
+    btp_location_add(location, 2, 0);
+
+    /* Read the frames. */
+    struct btp_frame *frame, *prevframe = NULL;
+    struct btp_location frame_location;
+    btp_location_init(&frame_location);
+    while ((frame = btp_frame_parse(&local_input, &frame_location)))
+    {
+        if (prevframe)
+        {
+            btp_frame_add_sibling(prevframe, frame);
+            prevframe = frame;
+        }
+        else
+            imthread->frames = prevframe = frame;
+
+        btp_location_add(location,
+                         frame_location.line,
+                         frame_location.column);
+    }
+    if (!imthread->frames)
+    {
+        location->message = frame_location.message;
+        btp_thread_free(imthread);
+        return NULL;
+    }
+
+    *input = local_input;
+    return imthread;
+}
diff --git a/lib/btparser/thread.h b/lib/btparser/thread.h
new file mode 100644
index 00000000..f7287385
--- /dev/null
+++ b/lib/btparser/thread.h
@@ -0,0 +1,204 @@
+/*
+    thread.h
+
+    Copyright (C) 2010  Red Hat, Inc.
+
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License along
+    with this program; if not, write to the Free Software Foundation, Inc.,
+    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+#ifndef BTPARSER_THREAD_H
+#define BTPARSER_THREAD_H
+
+#include <stdbool.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+struct btp_frame;
+struct strbuf;
+struct btp_location;
+
+/**
+ * Represents a thread containing frames.
+ */
+struct btp_thread
+{
+    unsigned number;
+    /**
+     * Thread's frames, starting from the top of the stack.
+     */
+    struct btp_frame *frames;
+    /**
+     * A sibling thread, or NULL if this is the last thread in a backtrace.
+     */
+    struct btp_thread *next;
+};
+
+/**
+ * Creates and initializes a new frame structure.
+ * @returns
+ * It never returns NULL. The returned pointer must be released by
+ * calling the function btp_thread_free().
+ */
+struct btp_thread *
+btp_thread_new();
+
+/**
+ * Initializes all members of the thread to default values.
+ * No memory is released, members are simply overwritten.
+ * This is useful for initializing a thread structure placed on the
+ * stack.
+ */
+void
+btp_thread_init(struct btp_thread *thread);
+
+/**
+ * Releases the memory held by the thread. The thread siblings are not
+ * released.
+ * @param thread
+ * If thread is NULL, no operation is performed.
+ */
+void
+btp_thread_free(struct btp_thread *thread);
+
+/**
+ * Creates a duplicate of the thread.
+ * @param thread
+ * It must be non-NULL pointer. The thread is not modified by calling
+ * this function.
+ * @param siblings
+ * Whether to duplicate also siblings referenced by thread->next. If
+ * false, thread->next is not duplicated for the new frame, but it is
+ * set to NULL.
+ */
+struct btp_thread *
+btp_thread_dup(struct btp_thread *thread,
+               bool siblings);
+
+/**
+ * Compares two threads. When comparing the threads, it compares also
+ * their frames, including the frame numbers.
+ * @returns
+ * Returns 0 if the threads are same.  Returns negative number if t1
+ * is found to be 'less' than t2.  Returns positive number if t1 is
+ * found to be 'greater' than t2.
+ */
+int
+btp_thread_cmp(struct btp_thread *t1, struct btp_thread *t2);
+
+/**
+ * Puts the thread 'b' to the bottom of the stack 'a'. In other words,
+ * it finds the last sibling of the thread 'a', and appends the thread
+ * 'b' to this last sibling.
+ */
+struct btp_thread *
+btp_thread_add_sibling(struct btp_thread *a, struct btp_thread *b);
+
+/**
+ * Returns the number of frames of the thread.
+ */
+int
+btp_thread_get_frame_count(struct btp_thread *thread);
+
+/**
+ * Counts the number of 'good' frames and the number of all frames in
+ * a thread. Good means that the function name is known (so it's not
+ * just '??').
+ * @param ok_count
+ * @param all_count
+ * Not zeroed. This function just adds the numbers to ok_count and
+ * all_count.
+ */
+void
+btp_thread_quality_counts(struct btp_thread *thread,
+                          int *ok_count,
+                          int *all_count);
+
+/**
+ * Returns the quality of the thread. The quality is the ratio of the
+ * number of frames with function name fully known to the number of
+ * all frames.  This function does not take into account that some
+ * frames are more important than others.
+ * @param thread
+ * Must be a non-NULL pointer. It's not modified in this function.
+ * @returns
+ * A number between 0 and 1. 0 means the lowest quality, 1 means full
+ * thread backtrace is known. If the thread contains no frames, this
+ * function returns 1.
+ */
+float
+btp_thread_quality(struct btp_thread *thread);
+
+/**
+ * Removes the frame from the thread and then deletes it.
+ * @returns
+ * True if the frame was found in the thread and removed and deleted.
+ * False if the frame was not found in the thread.
+ */
+bool
+btp_thread_remove_frame(struct btp_thread *thread,
+                        struct btp_frame *frame);
+
+/**
+ * Removes all the frames from the thread that are above certain
+ * frame.
+ * @returns
+ * True if the frame was found, and all the frames that were above the
+ * frame in the thread were removed from the thread and then deleted.
+ * False if the frame was not found in the thread.
+ */
+bool
+btp_thread_remove_frames_above(struct btp_thread *thread,
+                               struct btp_frame *frame);
+
+/**
+ * Keeps only the top n frames in the thread.
+ */
+void
+btp_thread_remove_frames_below_n(struct btp_thread *thread,
+                                 int n);
+
+/**
+ * Appends a textual representation of 'thread' to the 'str'.
+ */
+void
+btp_thread_append_to_str(struct btp_thread *thread,
+                         struct strbuf *str,
+                         bool verbose);
+
+/**
+ * If the input contains proper thread with frames, parse the thread,
+ * move the input pointer after the thread, and return a structure
+ * representing the thread.  Otherwise to not modify the input pointer
+ * and return NULL.
+ * @param location
+ * The caller must provide a pointer to struct btp_location here.  The
+ * line and column members are gradually increased as the parser
+ * handles the input, keep this in mind to get reasonable values.
+ * When this function returns NULL (an error occurred), the structure
+ * will contain the error line, column, and message.
+ * @returns
+ * NULL or newly allocated structure, which should be released by
+ * calling btp_thread_free().
+ */
+struct btp_thread *
+btp_thread_parse(char **input,
+                 struct btp_location *location);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
diff --git a/lib/btparser/utils.c b/lib/btparser/utils.c
new file mode 100644
index 00000000..1de329a7
--- /dev/null
+++ b/lib/btparser/utils.c
@@ -0,0 +1,423 @@
+/*
+    utils.c
+
+    Copyright (C) 2010  Red Hat, Inc.
+
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License along
+    with this program; if not, write to the Free Software Foundation, Inc.,
+    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+#include "utils.h"
+#include "location.h"
+#include <stdio.h>
+#include <string.h>
+#include <errno.h>
+#include <regex.h>
+#include <limits.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <unistd.h>
+#include <fcntl.h>
+
+bool btp_debug_parser = false;
+
+void *
+btp_malloc(size_t size)
+{
+    void *ptr = malloc(size);
+    if (ptr == NULL)
+    {
+        fprintf(stderr, "btp: out of memory");
+        exit(1);
+    }
+    return ptr;
+}
+
+char *
+btp_vasprintf(const char *format, va_list p)
+{
+    int r;
+    char *string_ptr;
+
+#if 1
+    // GNU extension
+    r = vasprintf(&string_ptr, format, p);
+#else
+    // Bloat for systems that haven't got the GNU extension.
+    va_list p2;
+    va_copy(p2, p);
+    r = vsnprintf(NULL, 0, format, p);
+    string_ptr = xmalloc(r+1);
+    r = vsnprintf(string_ptr, r+1, format, p2);
+    va_end(p2);
+#endif
+
+    if (r < 0)
+    {
+        fprintf(stderr, "btp: out of memory");
+        exit(1);
+    }
+
+    return string_ptr;
+}
+
+char *
+btp_strdup(const char *s)
+{
+    return btp_strndup(s, strlen(s));
+}
+
+char *
+btp_strndup(const char *s, size_t n)
+{
+    char *result = strndup(s, n);
+    if (result == NULL)
+    {
+        fprintf(stderr, "btp: out of memory");
+        exit(1);
+    }
+    return result;
+}
+
+int
+btp_strcmp0(const char *s1, const char *s2)
+{
+    if (!s1)
+    {
+        if (s2)
+            return -1;
+        return 0;
+    }
+    else
+    {
+        if (!s2)
+            return 1;
+        /* Both are non-null. */
+        return strcmp(s1, s2);
+    }
+}
+
+char *
+btp_strchr_location(const char *s, int c, int *line, int *column)
+{
+    *line = 1;
+    *column = 0;
+
+    /* Scan s for the character.  When this loop is finished,
+       s will either point to the end of the string or the
+       character we were looking for.  */
+    while (*s != '\0' && *s != (char)c)
+    {
+        btp_location_eat_char_ext(line, column, *s);
+        ++s;
+    }
+    return ((*s == c) ? (char*)s : NULL);
+}
+
+char *
+btp_strstr_location(const char *haystack,
+                    const char *needle,
+                    int *line,
+                    int *column)
+{
+    *line = 1;
+    *column = 0;
+    size_t needlelen;
+
+    /* Check for the null needle case.  */
+    if (*needle == '\0')
+        return (char*)haystack;
+
+    needlelen = strlen(needle);
+    int chrline, chrcolumn;
+    for (;(haystack = btp_strchr_location(haystack, *needle, &chrline, &chrcolumn)) != NULL; ++haystack)
+    {
+        btp_location_add_ext(line, column, chrline, chrcolumn);
+
+        if (strncmp(haystack, needle, needlelen) == 0)
+            return (char*)haystack;
+
+        btp_location_eat_char_ext(line, column, *haystack);
+    }
+    return NULL;
+}
+
+size_t
+btp_strspn_location(const char *s,
+                    const char *accept,
+                    int *line,
+                    int *column)
+{
+    *line = 1;
+    *column = 0;
+    const char *sc;
+    for (sc = s; *sc != '\0'; ++sc)
+    {
+        if (strchr(accept, *sc) == NULL)
+            return (sc - s);
+
+        btp_location_eat_char_ext(line, column, *sc);
+    }
+    return sc - s; /* terminating nulls don't match */
+}
+
+char *
+btp_file_to_string(const char *filename)
+{
+    /* Open input file, and parse it. */
+    int fd = open(filename, O_RDONLY | O_LARGEFILE);
+    if (fd < 0)
+    {
+        fprintf(stderr, "Unable to open '%s': %s.\n",
+                filename, strerror(errno));
+        return NULL;
+    }
+
+    off_t size = lseek(fd, 0, SEEK_END);
+    if (size < 0) /* EOVERFLOW? */
+    {
+        fprintf(stderr, "Unable to seek in '%s': %s.\n",
+                filename, strerror(errno));
+    }
+
+    lseek(fd, 0, SEEK_SET); /* No reason to fail. */
+
+    static const size_t FILE_SIZE_LIMIT = 20000000; /* ~ 20 MB */
+    if (size > FILE_SIZE_LIMIT)
+    {
+        fprintf(stderr, "Input file too big (%lld). Maximum size is %zd.\n",
+                (long long)size, FILE_SIZE_LIMIT);
+        close(fd);
+        return NULL;
+    }
+
+    char *contents = btp_malloc(size + 1);
+    if (size != read(fd, contents, size))
+    {
+        fprintf(stderr, "Unable to read from '%s'.\n", filename);
+        close(fd);
+        free(contents);
+        return NULL;
+    }
+
+    /* Just reading, so no need to check the returned value. */
+    close(fd);
+
+    contents[size] = '\0';
+    return contents;
+}
+
+bool
+btp_skip_char(char **input, char c)
+{
+    if (**input != c)
+        return false;
+    ++*input;
+    return true;
+}
+
+bool
+btp_skip_char_limited(char **input, const char *allowed)
+{
+    if (strchr(allowed, **input) == NULL)
+        return false;
+    ++*input;
+    return true;
+}
+
+bool
+btp_parse_char_limited(char **input, const char *allowed, char *result)
+{
+    if (**input == '\0')
+        return false;
+    if (strchr(allowed, **input) == NULL)
+        return false;
+    *result = **input;
+    ++*input;
+    return true;
+}
+
+int
+btp_skip_char_sequence(char **input, char c)
+{
+    int count = 0;
+
+    /* Skip all the occurences of c. */
+    while (btp_skip_char(input, c))
+        ++count;
+
+    return count;
+}
+
+int
+btp_skip_char_span(char **input, const char *chars)
+{
+    size_t count = strspn(*input, chars);
+    if (0 == count)
+        return count;
+    *input += count;
+    return count;
+}
+
+int
+btp_skip_char_span_location(char **input,
+                            const char *chars,
+                            int *line,
+                            int *column)
+{
+    size_t count = btp_strspn_location(*input, chars, line, column);
+    if (0 == count)
+        return count;
+    *input += count;
+    return count;
+}
+
+int
+btp_parse_char_span(char **input, const char *accept, char **result)
+{
+    size_t count = strspn(*input, accept);
+    if (count == 0)
+        return 0;
+    *result = btp_strndup(*input, count);
+    *input += count;
+    return count;
+}
+
+bool
+btp_parse_char_cspan(char **input, const char *reject, char **result)
+{
+    size_t count = strcspn(*input, reject);
+    if (count == 0)
+        return false;
+    *result = btp_strndup(*input, count);
+    *input += count;
+    return true;
+}
+
+int
+btp_skip_string(char **input, const char *string)
+{
+    char *local_input = *input;
+    const char *local_string = string;
+    while (*local_string && *local_input && *local_input == *local_string)
+    {
+        ++local_input;
+        ++local_string;
+    }
+    if (*local_string != '\0')
+        return 0;
+    int count = local_input - *input;
+    *input = local_input;
+    return count;
+}
+
+bool
+btp_parse_string(char **input, const char *string, char **result)
+{
+    char *local_input = *input;
+    const char *local_string = string;
+    while (*local_string && *local_input && *local_input == *local_string)
+    {
+        ++local_input;
+        ++local_string;
+    }
+    if (*local_string != '\0')
+        return false;
+    *result = btp_strndup(string, local_input - *input);
+    *input = local_input;
+    return true;
+}
+
+char
+btp_parse_digit(char **input)
+{
+    char digit = **input;
+    if (digit < '0' || digit > '9')
+        return '\0';
+    ++*input;
+    return digit;
+}
+
+int
+btp_skip_unsigned_integer(char **input)
+{
+    return btp_skip_char_span(input, "0123456789");
+}
+
+int
+btp_parse_unsigned_integer(char **input, unsigned *result)
+{
+    char *local_input = *input;
+    char *numstr;
+    int length = btp_parse_char_span(&local_input,
+                                     "0123456789",
+                                     &numstr);
+    if (0 == length)
+        return 0;
+
+    char *endptr;
+    errno = 0;
+    unsigned long r = strtoul(numstr, &endptr, 10);
+    bool failure = (errno || numstr == endptr || *endptr != '\0'
+                    || r > UINT_MAX);
+    free(numstr);
+    if (failure) /* number too big or some other error */
+        return 0;
+    *result = r;
+    *input = local_input;
+    return length;
+}
+
+int
+btp_skip_hexadecimal_number(char **input)
+{
+    char *local_input = *input;
+    if (!btp_skip_char(&local_input, '0'))
+        return 0;
+    if (!btp_skip_char(&local_input, 'x'))
+        return 0;
+    int count = 2;
+    count += btp_skip_char_span(&local_input, "abcdef0123456789");
+    if (2 == count) /* btp_skip_char_span returned 0 */
+        return 0;
+    *input = local_input;
+    return count;
+}
+
+int
+btp_parse_hexadecimal_number(char **input, uint64_t *result)
+{
+    char *local_input = *input;
+    if (!btp_skip_char(&local_input, '0'))
+        return 0;
+    if (!btp_skip_char(&local_input, 'x'))
+        return 0;
+    int count = 2;
+    char *numstr;
+    count += btp_parse_char_span(&local_input,
+                                 "abcdef0123456789",
+                                 &numstr);
+
+    if (2 == count) /* btp_parse_char_span returned 0 */
+        return 0;
+    char *endptr;
+    errno = 0;
+    unsigned long long r = strtoull(numstr, &endptr, 16);
+    bool failure = (errno || numstr == endptr || *endptr != '\0');
+    free(numstr);
+    if (failure) /* number too big or some other error */
+        return 0;
+    *result = r;
+    *input = local_input;
+    return count;
+}
diff --git a/lib/btparser/utils.h b/lib/btparser/utils.h
new file mode 100644
index 00000000..680e67e0
--- /dev/null
+++ b/lib/btparser/utils.h
@@ -0,0 +1,284 @@
+/*
+    utils.h
+
+    Copyright (C) 2010  Red Hat, Inc.
+
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License along
+    with this program; if not, write to the Free Software Foundation, Inc.,
+    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+#ifndef BTPARSER_UTILS_H
+#define BTPARSER_UTILS_H
+
+#include <stdlib.h>
+#include <stdarg.h>
+#include <stdbool.h>
+#include <stdint.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#define BTP_lower "abcdefghijklmnopqrstuvwxyz"
+#define BTP_upper "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
+#define BTP_alpha BTP_lower BTP_upper
+#define BTP_space " \t\r\n\v\f"
+#define BTP_digit "0123456789"
+#define BTP_alnum BTP_alpha BTP_digit
+
+/**
+ * Debugging output to stdout while parsing.
+ * Default value is false.
+ */
+extern bool
+btp_debug_parser;
+
+/**
+ * Never returns NULL.
+ */
+void *
+btp_malloc(size_t size);
+
+/**
+ * Never returns NULL.
+ */
+char *
+btp_vasprintf(const char *format, va_list p);
+
+/**
+ * Never returns NULL.
+ */
+char *
+btp_strdup(const char *s);
+
+/**
+ * Never returns NULL.
+ */
+char *
+btp_strndup(const char *s, size_t n);
+
+/**
+ * A strcmp() variant that works also with NULL parameters.  NULL is
+ * considered to be less than a string.
+ */
+int
+btp_strcmp0(const char *s1, const char *s2);
+
+/**
+ * A strchr() variant providing line and column in the string s
+ * indicating where the char c was found.
+ * @param line
+ * Starts from 1.  Its value is valid only when this function does not
+ * return NULL.
+ * @param column
+ * Starts from 0.  Its value is valid only when this function does not
+ * return NULL.
+ */
+char *
+btp_strchr_location(const char *s, int c, int *line, int *column);
+
+/**
+ * A strstr() variant providing line and column of the haystick
+ * indicating where the needle was found.
+ * @param line
+ * Starts from 1.  Its value is valid only when this function does not
+ * return NULL.
+ * @param column
+ * Starts from 0.  Its value is valid only when this function does not
+ * return NULL.
+ */
+char *
+btp_strstr_location(const char *haystack,
+                    const char *needle,
+                    int *line,
+                    int *column);
+
+/**
+ * A strspn() variant providing line and column of the string s which
+ * corresponds to the returned length.
+ * @param line
+ * Starts from 1.
+ * @param column
+ * Starts from 0.
+ */
+size_t
+btp_strspn_location(const char *s,
+                    const char *accept,
+                    int *line,
+                    int *column);
+
+/**
+ * Loads file contents to a string.
+ * @returns
+ * File contents. If file opening/reading fails, NULL is returned.
+ */
+char *
+btp_file_to_string(const char *filename);
+
+/**
+ * If the input contains character c in the current positon, move the
+ * input pointer after the character, and return true. Otherwise do
+ * not modify the input and return false.
+ */
+bool
+btp_skip_char(char **input, char c);
+
+/**
+ * If the input contains one of allowed characters, move
+ * the input pointer after that character, and return true.
+ * Otherwise do not modify the input and return false.
+ */
+bool
+btp_skip_char_limited(char **input, const char *allowed);
+
+/**
+ * If the input contains one of allowed characters, store
+ * the character to the result, move the input pointer after
+ * that character, and return true. Otherwise do not modify
+ * the input and return false.
+ */
+bool
+btp_parse_char_limited(char **input, const char *allowed, char *result);
+
+/**
+ * If the input contains the character c one or more times, update it
+ * so that the characters are skipped. Returns the number of characters
+ * skipped, thus zero if **input does not contain c.
+ */
+int
+btp_skip_char_sequence(char **input, char c);
+
+/**
+ * If the input contains one or more characters from string chars,
+ * move the input pointer after the sequence. Otherwise do not modify
+ * the input.
+ * @returns
+ * The number of characters skipped.
+ */
+int
+btp_skip_char_span(char **input, const char *chars);
+
+/**
+ * If the input contains one or more characters from string chars,
+ * move the input pointer after the sequence. Otherwise do not modify
+ * the input.
+ * @param line
+ * Starts from 1. Corresponds to the returned number.
+ * @param column
+ * Starts from 0. Corresponds to the returned number.
+ * @returns
+ * The number of characters skipped.
+ */
+int
+btp_skip_char_span_location(char **input,
+                            const char *chars,
+                            int *line,
+                            int *column);
+
+/**
+ * If the input contains one or more characters from string accept,
+ * create a string from this sequence and store it to the result, move
+ * the input pointer after the sequence, and return the lenght of the
+ * sequence.  Otherwise do not modify the input and return 0.
+ *
+ * If this function returns nonzero value, the caller is responsible
+ * to free the result.
+ */
+int
+btp_parse_char_span(char **input, const char *accept, char **result);
+
+/**
+ * If the input contains characters which are not in string reject,
+ * create a string from this sequence and store it to the result,
+ * move the input pointer after the sequence, and return true.
+ * Otherwise do not modify the input and return false.
+ *
+ * If this function returns true, the caller is responsible to
+ * free the result.
+ */
+bool
+btp_parse_char_cspan(char **input, const char *reject, char **result);
+
+/**
+ * If the input contains the string, move the input pointer after
+ * the sequence. Otherwise do not modify the input.
+ * @returns
+ * Number of characters skipped. 0 if the input does not contain the
+ * string.
+ */
+int
+btp_skip_string(char **input, const char *string);
+
+/**
+ * If the input contains the string, copy the string to result,
+ * move the input pointer after the string, and return true.
+ * Otherwise do not modify the input and return false.
+ *
+ * If this function returns true, the caller is responsible to free
+ * the result.
+ */
+bool
+btp_parse_string(char **input, const char *string, char **result);
+
+/**
+ * If the input contains digit 0-9, return it as a character
+ * and move the input pointer after it. Otherwise return
+ * '\0' and do not modify the input.
+ */
+char
+btp_parse_digit(char **input);
+
+/**
+ * If the input contains [0-9]+, move the input pointer
+ * after the number.
+ * @returns
+ * The number of skipped characters. 0 if input does not start with a
+ * digit.
+ */
+int
+btp_skip_unsigned_integer(char **input);
+
+/**
+ * If the input contains [0-9]+, parse it, move the input pointer
+ * after the number.
+ * @returns
+ * Number of parsed characters. 0 if input does not contain a number.
+ */
+int
+btp_parse_unsigned_integer(char **input, unsigned *result);
+
+/**
+ * If the input contains 0x[0-9a-f]+, move the input pointer
+ * after that.
+ * @returns
+ * The number of characters processed from input. 0 if the input does
+ * not contain a hexadecimal number.
+ */
+int
+btp_skip_hexadecimal_number(char **input);
+
+/**
+ * If the input contains 0x[0-9a-f]+, parse the number, and move the
+ * input pointer after it.  Otherwise do not modify the input.
+ * @returns
+ * The number of characters read from input. 0 if the input does not
+ * contain a hexadecimal number.
+ */
+int
+btp_parse_hexadecimal_number(char **input, uint64_t *result);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif