Move backtrace parser from src/Backtrace to lib/Utils.

Move abrt-backtrace app from src/Backtrace/main.c to src/utils/abrt-backtrace.
Move backtrace preprocessign code from abrt-backtrace to the parser.
Implemented new backtrace rating algorithm.
Added old bt rating algorithm to backtrace.c
Move strbuf to lib/Utils, and updated it to use xfuncs.
Created separate header for xfuncs.
Some functions in xfuncs marked as extern "c", so they can be used
in C code.
Merged backtrace fallback (independent_backtrace) "parser" into
backtrace.{h/c}.
Added option --rate to abrt-backtrace, to be able to use the new
backtrace rating algorithm in scripts.

8 files changed, 1975 insertions, 6 deletions

diff --git a/lib/Utils/Makefile.am b/lib/Utils/Makefile.am
index 2667b18a..d3c7a255 100644
--- a/lib/Utils/Makefile.am
+++ b/lib/Utils/Makefile.am
@@ -2,12 +2,14 @@
 # ABRTdUtils has much more. It is used by daemon and plugins only
 lib_LTLIBRARIES = libABRTUtils.la libABRTdUtils.la
 
+AM_YFLAGS = --verbose
+
 # Not used just yet:
 # time.cpp
 # xconnect.cpp
 
 libABRTUtils_la_SOURCES = \
-    xfuncs.cpp \
+    xfuncs.h xfuncs.cpp \
     encbase64.cpp \
     read_write.cpp \
     logging.cpp \
@@ -21,7 +23,10 @@ libABRTUtils_la_SOURCES = \
     DebugDump.h DebugDump.cpp \
     abrt_dbus.h abrt_dbus.cpp \
     CrashTypes.cpp \
-    ABRTException.cpp
+    ABRTException.cpp \
+    backtrace.h backtrace.c \
+    backtrace_parser.y \
+    strbuf.h strbuf.c
 libABRTUtils_la_CPPFLAGS = \
     -Wall -Werror \
     -I$(srcdir)/../../inc \
diff --git a/lib/Utils/backtrace.c b/lib/Utils/backtrace.c
new file mode 100644
index 00000000..746a1cd0
--- /dev/null
+++ b/lib/Utils/backtrace.c
@@ -0,0 +1,846 @@
+/*  -*-mode:c;c-file-style:"bsd";c-basic-offset:4;indent-tabs-mode:nil-*-
+    Copyright (C) 2009  RedHat 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 "strbuf.h"
+#include <stdlib.h>
+#include <string.h>
+#include <ctype.h>
+#include "xfuncs.h"
+
+struct frame *frame_new()
+{
+  struct frame *f = malloc(sizeof(struct frame));
+  if (!f)
+  {
+    puts("Error while allocating memory for backtrace frame.");
+    exit(5);
+  }
+
+  f->function = NULL;
+  f->number = 0;
+  f->sourcefile = NULL;
+  f->signal_handler_called = false;
+  f->next = NULL;
+  return f;
+}
+
+void frame_free(struct frame *f)
+{
+  if (f->function)
+    free(f->function);
+  if (f->sourcefile)
+    free(f->sourcefile);
+  free(f);
+}
+
+struct frame *frame_add_sibling(struct frame *a, struct frame *b)
+{
+  struct frame *aa = a;
+  while (aa->next)
+    aa = aa->next;
+
+  aa->next = b;
+  return a;
+}
+
+/* Appends a string representation of 'frame' to the 'str'. */
+static void frame_append_str(struct frame *frame, struct strbuf *str, bool verbose)
+{
+    if (verbose)
+        strbuf_append_strf(str, " #%d", frame->number);
+    else
+        strbuf_append_str(str, " ");
+
+    if (frame->function)
+        strbuf_append_strf(str, " %s", frame->function);
+    if (verbose && frame->sourcefile)
+    {
+        if (frame->function)
+            strbuf_append_str(str, " at");
+        strbuf_append_strf(str, " %s", frame->sourcefile);
+    }
+
+    if (frame->signal_handler_called)
+        strbuf_append_str(str, " <signal handler called>");
+    
+    strbuf_append_str(str, "\n");
+}
+
+static bool frame_is_exit_handler(struct frame *frame)
+{
+  return (frame->function
+	  && frame->sourcefile
+	  && 0 == strcmp(frame->function, "__run_exit_handlers")
+	  && NULL != strstr(frame->sourcefile, "exit.c"));
+}
+
+/* Checks if a frame contains abort function used
+ * by operating system to exit application.
+ * E.g. in C it's called "abort" or "raise".
+ */
+static bool frame_is_abort_frame(struct frame *frame)
+{
+  if (!frame->function || !frame->sourcefile)
+    return false;
+
+  if (0 == strcmp(frame->function, "raise") 
+      && (NULL != strstr(frame->sourcefile, "pt-raise.c")
+          || NULL != strstr(frame->sourcefile, "/libc.so.6")))
+    return true;
+  else if (0 == strcmp(frame->function, "exit")
+           && NULL != strstr(frame->sourcefile, "exit.c"))
+    return true;
+  else if (0 == strcmp(frame->function, "abort")
+           && (NULL != strstr(frame->sourcefile, "abort.c")
+               || NULL != strstr(frame->sourcefile, "/libc.so.6")))
+    return true;
+  else if (frame_is_exit_handler(frame))
+    return true;
+  
+  return false;
+}
+
+static bool frame_is_noncrash_frame(struct frame *frame)
+{
+  /* Abort frames. */
+  if (frame_is_abort_frame(frame))
+    return true;
+
+  if (!frame->function)
+    return false;
+
+  if (0 == strcmp(frame->function, "__kernel_vsyscall"))
+    return true;
+
+  if (0 == strcmp(frame->function, "__assert_fail"))
+    return true;
+
+  if (!frame->sourcefile)
+    return false;
+
+  /* GDK */
+  if (0 == strcmp(frame->function, "gdk_x_error") 
+      && 0 == strcmp(frame->sourcefile, "gdkmain-x11.c"))
+    return true;
+
+  /* X.org */
+  if (0 == strcmp(frame->function, "_XReply") 
+      && 0 == strcmp(frame->sourcefile, "xcb_io.c"))
+    return true;
+  if (0 == strcmp(frame->function, "_XError") 
+      && 0 == strcmp(frame->sourcefile, "XlibInt.c"))
+    return true;
+  if (0 == strcmp(frame->function, "XSync") 
+      && 0 == strcmp(frame->sourcefile, "Sync.c"))
+    return true;
+  if (0 == strcmp(frame->function, "process_responses") 
+      && 0 == strcmp(frame->sourcefile, "xcb_io.c"))
+    return true;
+
+  /* glib */
+  if (0 == strcmp(frame->function, "IA__g_log") 
+      && 0 == strcmp(frame->sourcefile, "gmessages.c"))
+    return true;
+  if (0 == strcmp(frame->function, "IA__g_logv") 
+      && 0 == strcmp(frame->sourcefile, "gmessages.c"))
+    return true;
+  if (0 == strcmp(frame->function, "IA__g_assertion_message") 
+      && 0 == strcmp(frame->sourcefile, "gtestutils.c"))
+    return true;
+  if (0 == strcmp(frame->function, "IA__g_assertion_message_expr") 
+      && 0 == strcmp(frame->sourcefile, "gtestutils.c"))
+    return true;
+
+  /* DBus */
+  if (0 == strcmp(frame->function, "gerror_to_dbus_error_message") 
+      && 0 == strcmp(frame->sourcefile, "dbus-gobject.c"))
+    return true;
+  if (0 == strcmp(frame->function, "dbus_g_method_return_error") 
+      && 0 == strcmp(frame->sourcefile, "dbus-gobject.c"))
+    return true;
+
+  /* libstdc++ */
+  if (0 == strcmp(frame->function, "__gnu_cxx::__verbose_terminate_handler") 
+      && NULL != strstr(frame->sourcefile, "/vterminate.cc"))
+    return true;
+  if (0 == strcmp(frame->function, "__cxxabiv1::__terminate") 
+      && NULL != strstr(frame->sourcefile, "/eh_terminate.cc"))
+    return true;
+  if (0 == strcmp(frame->function, "std::terminate") 
+      && NULL != strstr(frame->sourcefile, "/eh_terminate.cc"))
+    return true;
+  if (0 == strcmp(frame->function, "__cxxabiv1::__cxa_throw") 
+      && NULL != strstr(frame->sourcefile, "/eh_throw.cc"))
+    return true;
+
+  return false;
+}
+
+struct thread *thread_new()
+{
+  struct thread *t = malloc(sizeof(struct thread));
+  if (!t)
+  {
+    puts("Error while allocating memory for backtrace thread.");
+    exit(5);
+  }
+
+  t->number = 0;
+  t->frames = NULL;
+  t->next = NULL;
+  return t;
+}
+
+void thread_free(struct thread *t)
+{
+  while (t->frames)
+  {
+    struct frame *rm = t->frames;
+    t->frames = rm->next;
+    frame_free(rm);
+  }
+
+  free(t);
+}
+
+struct thread *thread_add_sibling(struct thread *a, struct thread *b)
+{
+  struct thread *aa = a;
+  while (aa->next)
+    aa = aa->next;
+
+  aa->next = b;
+  return a;
+}
+
+static int thread_get_frame_count(struct thread *thread)
+{
+  struct frame *f = thread->frames;
+  int count = 0;
+  while (f)
+  {
+    f = f->next;
+    ++count;
+  }
+  return count;
+}
+
+/* Appends string representation of 'thread' to the 'str'. */
+static void thread_append_str(struct thread *thread, struct strbuf *str, bool verbose)
+{
+    int framecount = 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 frame *frame = thread->frames;
+    while (frame)
+    {
+        frame_append_str(frame, str, verbose);
+        frame = frame->next;
+    }
+}
+
+/*
+ * Checks whether the thread it contains some known "abort" function.
+ * If a frame with the function is found, it is returned.
+ * If there are multiple frames with abort function, the lowest 
+ * one is returned.
+ * Nonrecursive.
+ */
+struct frame *thread_find_abort_frame(struct thread *thread)
+{
+  struct frame *frame = thread->frames;
+  struct frame *result = NULL;
+  while (frame)
+  {
+    if (frame_is_abort_frame(frame))
+      result = frame;
+  
+    frame = frame->next;
+  }
+
+  return result;
+}
+
+static void thread_remove_exit_handlers(struct thread *thread)
+{
+  struct frame *frame = thread->frames;
+  while (frame)
+  {
+    if (frame_is_exit_handler(frame))
+    {
+      /* Delete all frames from the beginning to this frame. */
+      while (thread->frames != frame)
+      {
+        struct frame *rm = thread->frames;
+        thread->frames = thread->frames->next;
+        frame_free(rm);
+      }
+      return;
+    }
+
+    frame = frame->next;
+  }
+}
+
+static void thread_remove_noncrash_frames(struct thread *thread)
+{
+  struct frame *prev = NULL;
+  struct frame *cur = thread->frames;
+  while (cur)
+  {
+    if (frame_is_noncrash_frame(cur))
+    {
+      /* This frame must be skipped, because it will 
+         be deleted. */
+      if (prev)
+	prev->next = cur->next;
+      else
+	thread->frames = cur->next;
+
+      frame_free(cur);
+
+      /* Set cur to be valid, as it will be used to 
+         advance to next item. */
+      if (prev)
+	cur = prev;
+      else
+      {
+	cur = thread->frames;
+        continue;
+      }
+    }
+
+    prev = cur;
+    cur = cur->next;
+  }
+}
+
+/* Counts the number of quality frames and the number of all frames 
+ * in a thread.
+ * @param ok_count
+ * @param all_count
+ *   Not zeroed. This function just adds the numbers to 
+ *   ok_count and all_count.
+ */
+static void thread_rating(struct thread *thread, int *ok_count, int *all_count)
+{
+    struct frame *frame = thread->frames;
+    while (frame)
+    {
+        *all_count += 1;
+        if (frame->signal_handler_called || 
+            (frame->function && 0 != strcmp(frame->function, "??")))
+        {
+            *ok_count += 1;
+        }
+        frame = frame->next;
+    }
+}
+
+struct backtrace *backtrace_new()
+{
+  struct backtrace *bt = malloc(sizeof(struct backtrace));
+  if (!bt)
+  {
+    puts("Error while allocating memory for backtrace.");
+    exit(5);
+  }
+
+  bt->threads = NULL;
+  bt->crash = NULL;
+  return bt;
+}
+
+void backtrace_free(struct backtrace *bt)
+{
+  while (bt->threads)
+  {
+    struct thread *rm = bt->threads;
+    bt->threads = rm->next;
+    thread_free(rm);
+  }
+
+  if (bt->crash)
+    frame_free(bt->crash);
+
+  free(bt);
+}
+
+static int backtrace_get_thread_count(struct backtrace *bt)
+{
+  struct thread *t = bt->threads;
+  int count = 0;
+  while (t)
+  {
+    t = t->next;
+    ++count;
+  }
+  return count;
+}
+
+void backtrace_print_tree(struct backtrace *backtrace, bool verbose)
+{
+    struct strbuf *strbuf = backtrace_tree_as_str(backtrace, verbose);
+    puts(strbuf->buf);
+    strbuf_free(strbuf);
+}
+
+struct strbuf *backtrace_tree_as_str(struct backtrace *backtrace, bool verbose)
+{
+    struct strbuf *str = strbuf_new();
+    if (verbose)
+        strbuf_append_strf(str, "Thread count: %d\n", backtrace_get_thread_count(backtrace));
+
+    if (backtrace->crash && verbose)
+    {
+        strbuf_append_str(str, "Crash frame: ");
+        frame_append_str(backtrace->crash, str, verbose);
+    }
+    
+    struct thread *thread = backtrace->threads;
+    while (thread)
+    {
+        thread_append_str(thread, str, verbose);
+        thread = thread->next;
+    }
+
+    return str;
+}
+
+void backtrace_remove_threads_except_one(struct backtrace *backtrace, 
+					 struct thread *one)
+{
+  while (backtrace->threads)
+  {
+    struct thread *rm = backtrace->threads;
+    backtrace->threads = rm->next;
+    if (rm != one)
+      thread_free(rm);
+  }
+
+  one->next = NULL;
+  backtrace->threads = one;
+}
+
+/*
+ * 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 thread *backtrace_find_crash_thread_from_crash_frame(struct backtrace *backtrace,
+								   bool require_abort)
+{
+  /*
+   * This code can be extended to compare something else when the function
+   * name is not available.
+   */
+  if (!backtrace->threads || !backtrace->crash || !backtrace->crash->function)
+    return NULL;
+
+  struct thread *result = NULL;
+  struct thread *thread = backtrace->threads;
+  while (thread)
+  {
+    if (thread->frames 
+	&& thread->frames->function
+	&& 0 == strcmp(thread->frames->function, backtrace->crash->function)
+        && (!require_abort || thread_find_abort_frame(thread)))
+    {
+      if (result == NULL)
+	result = thread;
+      else
+      {
+	/* Second frame with the same function. Failure. */
+	return NULL;
+      }
+    }
+
+    thread = thread->next;
+  }
+  
+  return result;
+}
+
+struct thread *backtrace_find_crash_thread(struct 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 thread *thread;
+  thread = 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 = backtrace_find_crash_thread_from_crash_frame(backtrace, true);
+  
+  return thread; /* result or null */
+}
+
+void backtrace_limit_frame_depth(struct backtrace *backtrace, int depth)
+{
+  if (depth <= 0)
+    return;
+
+  struct thread *thread = backtrace->threads;
+  while (thread)
+  {
+    struct frame *frame = thread_find_abort_frame(thread);
+    if (frame)
+      frame = frame->next; /* Start counting from the frame following the abort fr. */
+    else
+      frame = thread->frames; /* Start counting from the first frame. */
+
+    /* Skip some frames to get the required stack depth. */
+    int i = depth;
+    struct frame *last_frame = NULL;
+    while (frame && i)
+    {
+      last_frame = frame;
+      frame = frame->next;
+      --i;
+    }
+
+    /* Delete the remaining frames. */
+    if (last_frame)
+      last_frame->next = NULL;
+
+    while (frame)
+    {
+      struct frame *rm = frame;
+      frame = frame->next;
+      frame_free(rm);
+    }
+
+    thread = thread->next;
+  }
+}
+
+void backtrace_remove_exit_handlers(struct backtrace *backtrace)
+{
+  struct thread *thread = backtrace->threads;
+  while (thread)
+  {
+    thread_remove_exit_handlers(thread);
+    thread = thread->next;
+  }  
+}
+
+void backtrace_remove_noncrash_frames(struct backtrace *backtrace)
+{
+  struct thread *thread = backtrace->threads;
+  while (thread)
+  {
+    thread_remove_noncrash_frames(thread);
+    thread = thread->next;
+  }
+}
+
+/* Belongs to independent_backtrace(). */
+struct header
+{
+  struct strbuf *text;
+  struct header *next;
+};
+
+/* Belongs to independent_backtrace(). */
+static struct header *header_new()
+{
+  struct header *head = malloc(sizeof(struct header));
+  if (!head)
+  {
+    puts("Error while allocating memory for backtrace header.");
+    exit(5);
+  }
+  head->text = NULL;
+  head->next = NULL;
+  return head;
+}
+
+/* Recursively frees siblings. */
+/* Belongs to independent_backtrace(). */
+static void header_free(struct header *head)
+{
+  if (head->text)
+    strbuf_free(head->text);
+  if (head->next)
+    header_free(head->next);
+  free(head);
+}
+
+/* Inserts new header to array if it is not already there. */
+/* Belongs to independent_backtrace(). */
+static void header_set_insert(struct header *cur, struct strbuf *new)
+{
+  /* Duplicate found case. */
+  if (strcmp(cur->text->buf, new->buf) == 0)
+    return;
+
+  /* Last item case, insert new header here. */
+  if (cur->next == NULL)
+  {
+    cur->next = header_new();
+    cur->next->text = new;
+    return;
+  }
+
+  /* Move to next item in array case. */
+  header_set_insert(cur->next, new);
+}
+
+struct strbuf *independent_backtrace(const char *input)
+{
+  struct strbuf *header = strbuf_new();
+  bool in_bracket = false;
+  bool in_quote = false;
+  bool in_header = false;
+  bool in_digit = false;
+  bool has_at = false;
+  bool has_filename = false;
+  bool has_bracket = false;
+  struct header *headers = NULL;
+
+  const char *bk = input;
+  while (*bk)
+  {
+    if (bk[0] == '#'
+	&& bk[1] >= '0' && bk[1] <= '7'
+	&& bk[2] == ' ' /* take only #0...#7 (8 last stack frames) */
+	&& !in_quote) 
+    {
+      if (in_header && !has_filename)
+	strbuf_clear(header);
+      in_header = true;
+    }
+
+    if (!in_header)
+    {
+      ++bk;
+      continue;
+    }
+
+    if (isdigit(*bk) && !in_quote && !has_at)
+      in_digit = true;
+    else if (bk[0] == '\\' && bk[1] == '\"')
+      bk++;
+    else if (*bk == '\"')
+      in_quote = in_quote == true ? false : true;
+    else if (*bk == '(' && !in_quote)
+    {
+      in_bracket = true;
+      in_digit = false;
+      strbuf_append_char(header, '(');
+    }
+    else if (*bk == ')' && !in_quote)
+    {
+      in_bracket = false;
+      has_bracket = true;
+      in_digit = false;
+      strbuf_append_char(header, '(');
+    }
+    else if (*bk == '\n' && has_filename)
+    {
+      if (headers == NULL)
+      {
+	headers = header_new();
+	headers->text = header;
+      }
+      else
+	header_set_insert(headers, header);
+
+      header = strbuf_new();
+      in_bracket = false;
+      in_quote = false;
+      in_header = false;
+      in_digit = false;
+      has_at = false;
+      has_filename = false;
+      has_bracket = false;
+    }
+    else if (*bk == ',' && !in_quote)
+      in_digit = false;
+    else if (isspace(*bk) && !in_quote)
+      in_digit = false;
+    else if (bk[0] == 'a' && bk[1] == 't' && has_bracket && !in_quote)
+    {
+      has_at = true;
+      strbuf_append_char(header, 'a');
+    }
+    else if (bk[0] == ':' && has_at && isdigit(bk[1]) && !in_quote)
+      has_filename = true;
+    else if (in_header && !in_digit && !in_quote && !in_bracket)
+      strbuf_append_char(header, *bk);
+    
+    bk++;
+  }
+  
+  strbuf_free(header);
+
+  struct strbuf *result = strbuf_new();
+  struct header *loop = headers;
+  while (loop)
+  {
+    strbuf_append_str(result, loop->text->buf);
+    strbuf_append_char(result, '\n');
+    loop = loop->next;
+  }
+
+  if (headers)
+    header_free(headers); /* recursive */
+
+  return result;
+}
+
+/* Belongs to backtrace_rate_old(). */
+enum line_rating
+{
+    // RATING              EXAMPLE
+    MissingEverything = 0, // #0 0x0000dead in ?? ()
+    MissingFunction   = 1, // #0 0x0000dead in ?? () from /usr/lib/libfoobar.so.4
+    MissingLibrary    = 2, // #0 0x0000dead in foobar()
+    MissingSourceFile = 3, // #0 0x0000dead in FooBar::FooBar () from /usr/lib/libfoobar.so.4
+    Good              = 4, // #0 0x0000dead in FooBar::crash (this=0x0) at /home/user/foobar.cpp:204
+    BestRating = Good,
+};
+
+/* Belongs to backtrace_rate_old(). */
+static enum line_rating rate_line(const char *line)
+{
+#define FOUND(x) (strstr(line, x) != NULL)
+    /* see the comments at enum line_rating for possible combinations */
+    if (FOUND(" at "))
+        return Good;
+    const char *function = strstr(line, " in ");
+    if (function && function[4] == '?') /* " in ??" does not count */
+        function = NULL;
+    bool library = FOUND(" from ");
+    if (function && library)
+        return MissingSourceFile;
+    if (function)
+        return MissingLibrary;
+    if (library)
+        return MissingFunction;
+
+    return MissingEverything;
+#undef FOUND
+}
+
+/* just a fallback function, to be removed one day */
+int backtrace_rate_old(const char *backtrace) 
+{
+    int i, len;
+    int multiplier = 0;
+    int rating = 0;
+    int best_possible_rating = 0;
+    char last_lvl = 0;
+
+    /* We look at the frames in reversed order, since:
+     * - rate_line() checks starting from the first line of the frame
+     * (note: it may need to look at more than one line!)
+     * - we increase weight (multiplier) for every frame,
+     *   so that topmost frames end up most important
+     */
+    len = 0;
+    for (i = strlen(backtrace) - 1; i >= 0; i--)
+    {
+        if (backtrace[i] == '#'
+            && (backtrace[i+1] >= '0' && backtrace[i+1] <= '9') /* #N */
+            && (i == 0 || backtrace[i-1] == '\n')) /* it's at line start */ 
+        {
+            /* For one, "#0 xxx" always repeats, skip repeats */
+            if (backtrace[i+1] == last_lvl)
+                continue;
+            last_lvl = backtrace[i+1];
+
+            char *s = xstrndup(backtrace + i + 1, len);
+            /* Replace tabs with spaces, rate_line() does not expect tabs.
+             * Actually, even newlines may be there. Example of multiline frame
+             * where " at SRCFILE" is on 2nd line:
+             * #3  0x0040b35d in __libc_message (do_abort=<value optimized out>,
+             *     fmt=<value optimized out>) at ../sysdeps/unix/sysv/linux/libc_fatal.c:186
+             */
+            char *p;
+            for (p = s; *p; p++)
+            {
+                if (*p == '\t' || *p == '\n')
+                    *p = ' ';
+            }
+            int lrate = rate_line(s);
+            multiplier++;
+            rating += lrate * multiplier;
+            best_possible_rating += BestRating * multiplier;
+            //log("lrate:%d rating:%d best_possible_rating:%d s:'%-.40s'", 
+            //    lrate, rating, best_possible_rating, s);
+            free(s);
+            len = 0; /* starting new line */
+        }
+        else
+        {
+            len++;
+        }
+    }
+
+    /* Bogus 'backtrace' with zero frames? */
+    if (best_possible_rating == 0)
+        return 0;
+
+    /* Returning number of "stars" to show */
+    if (rating*10 >= best_possible_rating*8) /* >= 0.8 */
+        return 4;
+    if (rating*10 >= best_possible_rating*6)
+        return 3;
+    if (rating*10 >= best_possible_rating*4)
+        return 2;
+    if (rating*10 >= best_possible_rating*2)
+        return 1;
+
+    return 0;
+}
+
+float backtrace_quality(struct backtrace *backtrace)
+{
+    int ok_count = 0;
+    int all_count = 0;
+    struct thread *thread = backtrace->threads;
+    while (thread)
+    {
+        thread_rating(thread, &ok_count, &all_count);
+        thread = thread->next;
+    }
+
+    if (all_count == 0)
+        return 0;
+    return ok_count / (float)all_count;
+}
diff --git a/lib/Utils/backtrace.h b/lib/Utils/backtrace.h
new file mode 100644
index 00000000..dd6d69c2
--- /dev/null
+++ b/lib/Utils/backtrace.h
@@ -0,0 +1,152 @@
+/*
+    Backtrace parsing and processing.
+    
+    If we transform analyzer plugins to separate applications one day, 
+    this functionality should be moved to CCpp analyzer, which will 
+    then easily provide what abrt-backtrace utility provides now. Currently 
+    the code is used by abrt-backtrace, so it is shared in the utils 
+    library.
+
+    Copyright (C) 2009, 2010  RedHat 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 BACKTRACE_H
+#define BACKTRACE_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <stdio.h>
+#include <stdbool.h>
+
+struct frame
+{
+  /* Function name, or NULL. */
+  char *function;
+  /* Frame number. */
+  int number;
+  /* Name of the source file, or binary file, or NULL. */
+  char *sourcefile;
+  bool signal_handler_called;
+  /* Sibling frame, or NULL if this is the last frame in a thread. */
+  struct frame *next;
+};
+
+struct thread
+{
+  int number;
+  struct frame *frames;
+  /* Sibling thread, or NULL if this is the last thread in a backtrace. */
+  struct thread *next;
+};
+
+struct backtrace
+{
+  struct thread *threads;
+  /* 
+   * The frame where the crash happened according to GDB. 
+   * It might be that we can not tell to which thread this frame belongs,
+   * because all threads end with mutually indistinguishable frames.
+   */
+  struct frame *crash;
+};
+
+extern struct frame *frame_new();
+extern void frame_free(struct frame *f);
+extern struct frame *frame_add_sibling(struct frame *a, struct frame *b);
+
+extern struct thread *thread_new();
+extern void thread_free(struct thread *t);
+extern struct thread *thread_add_sibling(struct thread *a, struct thread *b);
+extern struct frame *thread_find_abort_frame(struct thread *thread);
+
+extern struct backtrace *backtrace_new();
+extern void backtrace_free(struct backtrace *bt);
+
+/* Prints how internal backtrace representation looks to stdout. */
+extern void backtrace_print_tree(struct backtrace *backtrace, bool verbose);
+
+/* Returns the backtrace tree string representation. */
+extern struct strbuf *backtrace_tree_as_str(struct backtrace *backtrace, bool verbose);
+
+/* 
+ * Frees all threads except the one provided as parameters. 
+ * It does not check whether one is a member of backtrace.
+ * Caller must know that.
+ */
+extern void backtrace_remove_threads_except_one(struct backtrace *backtrace, 
+						struct thread *one);
+
+/* 
+ * Search all threads and tries to find the one that caused the crash. 
+ * It might return NULL if the thread cannot be determined.
+ */
+extern struct thread *backtrace_find_crash_thread(struct backtrace *backtrace);
+
+extern void backtrace_limit_frame_depth(struct backtrace *backtrace, int depth);
+
+/*
+ * Exit handlers are all stack frames above  __run_exit_handlers()
+ */
+extern void backtrace_remove_exit_handlers(struct backtrace *backtrace);
+
+/*
+ * Removes frames known as not causing crash, but that are often 
+ * a part of a backtrace.
+ */
+extern void backtrace_remove_noncrash_frames(struct backtrace *backtrace);
+
+/* Parses the backtrace and stores it to a structure.
+ * @returns 
+ *    Returns the backtrace struct representation, or NULL if the parser failed.
+ *    Caller of this function is responsible for backtrace_free()ing the returned value.
+ * Defined in backtrace_parser.y.
+ */
+extern struct backtrace *backtrace_parse(char *input, bool debug_parser, bool debug_scanner);
+
+/* Reads the input file and calculates "independent" backtrace from it. "Independent" means 
+ * that the memory addresses that differ from run to run are removed from the backtrace, and 
+ * also variable names and values are removed.
+ * 
+ * This function can be called when backtrace_parse() call fails. It provides a shorter 
+ * version of backtrace, with a chance that hash calculated from the returned value can be used
+ * to detect duplicates. However, this kind of duplicate detection is very low-quality.
+ * @returns
+ *   The independent backtrace. Caller is responsible for calling
+ *   strbuf_free() on it.
+ */
+extern struct strbuf *independent_backtrace(const char *input);
+
+/* Get the quality of backtrace, as a number of "stars".  
+ * @returns
+ *   Value 0 to 4.
+ */
+extern int backtrace_rate_old(const char *backtrace);
+
+/* Evaluates the quality of the backtrace, meaning the ratio of frames 
+ * with function name fully known to all frames.
+ * @returns
+ *   A number between 0 and 1. 0 means the lowest quality, 
+ *   1 means full backtrace is known.
+ */
+extern float backtrace_quality(struct backtrace *backtrace);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
diff --git a/lib/Utils/backtrace_parser.y b/lib/Utils/backtrace_parser.y
new file mode 100644
index 00000000..de81a3eb
--- /dev/null
+++ b/lib/Utils/backtrace_parser.y
@@ -0,0 +1,684 @@
+%{ /* -*- mode: yacc -*-
+    Copyright (C) 2009  RedHat 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 <math.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include "backtrace.h"
+#include "strbuf.h"
+
+struct backtrace *g_backtrace;
+
+#define YYDEBUG 1
+#define YYMAXDEPTH 10000000
+void yyerror(char const *s)
+{
+  fprintf (stderr, "\nParser error: %s\n", s);
+}
+
+int yylex();
+
+%}
+     
+/* This defines the type of yylval */
+%union {
+  struct backtrace *backtrace;
+  struct thread *thread;
+  struct frame *frame;
+  char *str;
+  int num;
+  char c;
+
+  struct strbuf *strbuf;
+}
+
+/* Bison declarations.  */
+%token END 0 "end of file"
+
+%type <backtrace> backtrace
+%type <thread> threads 
+               thread
+%type <frame>  frames 
+               frame 
+               frame_head 
+               frame_head_1 
+               frame_head_2 
+               frame_head_3 
+               frame_head_4 
+               frame_head_5
+%type <strbuf> identifier 
+               hexadecimal_digit_sequence 
+               hexadecimal_number 
+               file_name 
+               file_location 
+               function_call 
+               function_name 
+               digit_sequence 
+               frame_address_in_function
+               identifier_braces
+               identifier_braces_inside
+               identifier_template
+               identifier_template_inside
+%type <c>      nondigit 
+               digit 
+               hexadecimal_digit 
+               file_name_char 
+               identifier_char 
+               identifier_char_no_templates 
+               identifier_first_char
+               identifier_braces_inside_char
+               identifier_template_inside_char
+               variables_char
+               variables_char_no_framestart
+               ws
+               ws_nonl
+               '(' ')' '+' '-' '/' '.' '_' '~' '[' ']' '\r' '?' '{' '}'
+               'a' 'b' 'c' 'd' 'e' 'f' 'g' 'h' 'i' 'j' 'k' 'l' 
+               'm' 'n' 'o' 'p' 'q' 'r' 's' 't' 'u' 'v' 'w' 'x' 'y' 'z' 
+               'A' 'B' 'C' 'D' 'E' 'F' 'G' 'H' 'I' 'J' 'K' 'L' 'M' 'N' 
+               'O' 'P' 'Q' 'R' 'S' 'T' 'U' 'V' 'W' 'X' 'Y' 'Z' 
+               '0' '1' '2' '3' '4' '5' '6' '7' '8' '9'
+               '\'' '`' ',' '#' '@' '<' '>' '=' ':' '"' ';' ' ' 
+               '\n' '\t' '\\' '!' '*' '%' '|' '^' '&' '$'
+%type <num>    frame_start
+
+%destructor { thread_free($$); } <thread>
+%destructor { frame_free($$); } <frame>
+%destructor { strbuf_free($$); } <strbuf>
+
+%start backtrace
+%glr-parser
+%error-verbose
+%locations
+
+%% /* The grammar follows.  */
+
+backtrace : /* empty */ %dprec 1 
+             { $$ = g_backtrace = backtrace_new(); }
+          | threads wsa %dprec 2
+             { 
+               $$ = g_backtrace = backtrace_new(); 
+               $$->threads = $1; 
+             }
+          |  frame_head wss threads wsa %dprec 4
+             { 
+               $$ = g_backtrace = backtrace_new(); 
+               $$->threads = $3; 
+               $$->crash = $1;
+             }
+          | frame wss threads wsa %dprec 3
+             { 
+               $$ = g_backtrace = backtrace_new(); 
+               $$->threads = $3; 
+               $$->crash = $1;
+             }
+;
+
+threads   : thread
+          | threads '\n' thread { $$ = thread_add_sibling($1, $3); }
+;
+
+thread    : keyword_thread wss digit_sequence wsa '(' keyword_thread wss digit_sequence wsa ')' ':' wsa frames 
+              { 
+                $$ = thread_new(); 
+                $$->frames = $13; 
+		
+		if (sscanf($3->buf, "%d", &$$->number) != 1)
+		{
+		  printf("Error while parsing thread number '%s'", $3->buf);
+		  exit(5);
+		}
+		strbuf_free($3);
+		strbuf_free($8);
+              }
+;
+
+frames    : frame        { $$ = $1; }
+          | frames frame { $$ = frame_add_sibling($1, $2); }
+;
+
+frame : frame_head_1 wss variables %dprec 3
+      | frame_head_2 wss variables %dprec 4
+      | frame_head_3 wss variables %dprec 5 
+      | frame_head_4 wss variables %dprec 2 
+      | frame_head_5 wss variables %dprec 1
+;
+
+frame_head : frame_head_1 %dprec 3 
+	   | frame_head_2 %dprec 4 
+	   | frame_head_3 %dprec 5 
+           | frame_head_4 %dprec 2 
+           | frame_head_5 %dprec 1
+;
+
+frame_head_1 : frame_start wss function_call wsa keyword_at wss file_location
+             { 
+               $$ = frame_new(); 
+               $$->number = $1; 
+               $$->function = $3->buf; 
+               strbuf_free_nobuf($3); 
+	       $$->sourcefile = $7->buf;
+               strbuf_free_nobuf($7); 
+             }
+;
+
+frame_head_2 : frame_start wss frame_address_in_function wss keyword_at wss file_location
+             { 
+               $$ = frame_new(); 
+               $$->number = $1; 
+               $$->function = $3->buf; 
+               strbuf_free_nobuf($3); 
+	       $$->sourcefile = $7->buf;
+               strbuf_free_nobuf($7); 
+             }
+;
+
+frame_head_3 : frame_start wss frame_address_in_function wss keyword_from wss file_location
+             { 
+               $$ = frame_new(); 
+               $$->number = $1; 
+               $$->function = $3->buf; 
+               strbuf_free_nobuf($3); 
+	       $$->sourcefile = $7->buf;
+               strbuf_free_nobuf($7); 
+             }
+;
+
+frame_head_4 : frame_start wss frame_address_in_function
+             { 
+               $$ = frame_new(); 
+               $$->number = $1; 
+               $$->function = $3->buf; 
+               strbuf_free_nobuf($3); 
+             }
+;
+
+frame_head_5 : frame_start wss keyword_sighandler
+             { 
+               $$ = frame_new(); 
+               $$->number = $1; 
+	       $$->signal_handler_called = true;
+             }
+
+frame_start: '#' digit_sequence 
+                 { 
+                   if (sscanf($2->buf, "%d", &$$) != 1)
+		   {
+		     printf("Error while parsing frame number '%s'.\n", $2->buf);
+		     exit(5);
+		   }
+		   strbuf_free($2); 
+                 }
+;
+
+frame_address_in_function : hexadecimal_number wss keyword_in wss function_call 
+                              {
+                                strbuf_free($1); 
+                                $$ = $5; 
+                              }
+                          | hexadecimal_number wss keyword_in wss keyword_vtable wss keyword_for wss function_call
+                              {
+                                strbuf_free($1); 
+                                $$ = $9; 
+                              }
+;
+
+file_location : file_name ':' digit_sequence 
+                  {
+                    $$ = $1; 
+                    strbuf_free($3); /* line number not needed for now */
+                  }
+              | file_name
+;
+
+variables : variables_line '\n'
+          | variables_line END 
+          | variables_line wss_nonl '\n' 
+          | variables_line wss_nonl END  
+          | variables variables_line '\n' 
+          | variables variables_line END  
+          | variables variables_line wss_nonl '\n' 
+          | variables variables_line wss_nonl END  
+          | variables wss_nonl variables_line '\n'
+          | variables wss_nonl variables_line END  
+          | variables wss_nonl variables_line wss_nonl '\n' 
+          | variables wss_nonl variables_line wss_nonl END  
+;
+
+variables_line : variables_char_no_framestart
+               | variables_line variables_char
+               | variables_line wss_nonl variables_char
+;
+
+variables_char : '#' | variables_char_no_framestart
+;
+
+/* Manually synchronized with function_args_char_base, except the first line. */
+variables_char_no_framestart : digit | nondigit | '"' | '(' | ')' | '\\'
+                             | '+' | '-' | '<' | '>' | '/' | '.' 
+                             | '[' | ']' | '?' | '\'' | '`' | ',' 
+                             | '=' | '{' | '}' | '^' | '&' | '$'
+                             | ':' | ';' | '!' | '@' | '*' 
+                             | '%' | '|' | '~'
+;
+
+function_call : function_name wss function_args %dprec 3
+              | return_type wss_nonl function_name wss function_args %dprec 2
+                  { $$ = $3; }
+              | function_name wss_nonl identifier_template wss function_args %dprec 1
+	      { $$ = $1; strbuf_free($3); }
+;
+
+return_type : identifier { strbuf_free($1); }
+;
+
+function_name : identifier
+              | '?' '?' 
+                { 
+                  $$ = strbuf_new(); 
+                  strbuf_append_str($$, "??"); 
+                }
+;
+
+function_args : '(' wsa ')'
+              | '(' wsa function_args_sequence wsa ')'
+;
+
+function_args_sequence : function_args_char
+                       | function_args_sequence wsa '(' wsa ')'
+                       | function_args_sequence wsa '(' wsa function_args_string wsa ')'
+                       | function_args_sequence wsa '(' wsa function_args_sequence wsa ')'
+                       | function_args_sequence wsa function_args_char
+                       | function_args_sequence wsa function_args_string
+;
+
+function_args_string : '"' wsa function_args_string_sequence wsa '"'
+                     | '"' wsa '"'
+;
+
+/* Manually synchronized with variables_char_no_framestart,
+ * except the first line. 
+ */
+function_args_char_base : digit | nondigit | '#'
+                   | '+' | '-' | '<' | '>' | '/' | '.' 
+                   | '[' | ']' | '?' | '\'' | '`' | ',' 
+                   | '=' | '{' | '}' | '^' | '&' | '$'
+                   | ':' | ';' | '!' | '@' | '*' 
+                   | '%' | '|' | '~'
+;
+function_args_escaped_char : '\\' function_args_char_base
+                           | '\\' '\\'
+                           | '\\' '"'
+;
+function_args_char : function_args_char_base
+                   | function_args_escaped_char
+;
+
+
+function_args_string_sequence : function_args_string_char
+                    | function_args_string_sequence function_args_string_char
+                    | function_args_string_sequence wss_nonl function_args_string_char
+;
+
+function_args_string_char : function_args_char | '(' | ')'
+;
+
+file_name : file_name_char { $$ = strbuf_new(); strbuf_append_char($$, $1); }
+          | file_name file_name_char { $$ = strbuf_append_char($1, $2); }
+;
+
+file_name_char : digit | nondigit | '-' | '+' | '/' | '.'
+;
+
+ /* Function name, sometimes mangled.  
+  * Example: something@GLIB_2_2
+  * CClass::operator=
+  */
+identifier : identifier_first_char %dprec 1
+              {
+		$$ = strbuf_new(); 
+		strbuf_append_char($$, $1); 
+	      }
+           | identifier_braces %dprec 1 /* e.g. (anonymous namespace)::WorkerThread */
+           | identifier identifier_char %dprec 1
+	      { $$ = strbuf_append_char($1, $2); }
+           | identifier identifier_braces %dprec 1
+              { 
+		$$ = strbuf_append_str($1, $2->buf); 
+		strbuf_free($2);
+	      }
+           | identifier identifier_template %dprec 2
+              { 
+		$$ = strbuf_append_str($1, $2->buf); 
+		strbuf_free($2);
+	      }
+;
+
+identifier_first_char: nondigit 
+                     | '~' /* destructor */
+                     | '*'
+;
+
+identifier_char_no_templates : digit | nondigit | '@' | '.' | ':' | '=' 
+	                     | '!' | '*' | '+' | '-' | '[' | ']'
+                             | '~' | '&' | '/' | '%' | '^'
+                             | '|' | ','
+;
+
+/* Most of the special characters are required to support C++ 
+ * operator overloading.
+ */
+identifier_char : identifier_char_no_templates | '<'| '>'
+;
+
+identifier_braces : '(' ')'
+                      {
+			$$ = strbuf_new();
+			strbuf_append_char($$, $1);
+			strbuf_append_char($$, $2);
+		      }
+                  | '(' identifier_braces_inside ')' 
+                      {
+			$$ = strbuf_new();
+			strbuf_append_char($$, $1);
+			strbuf_append_str($$, $2->buf);
+			strbuf_free($2);
+			strbuf_append_char($$, $3);
+                      }
+;
+
+identifier_braces_inside : identifier_braces_inside_char %dprec 1
+                            {
+	                      $$ = strbuf_new(); 
+		              strbuf_append_char($$, $1); 
+	                    }                         
+                         | identifier_braces_inside identifier_braces_inside_char %dprec 1
+			    { $$ = strbuf_append_char($1, $2); }
+                         | identifier_braces_inside '(' identifier_braces_inside ')' %dprec 1
+			    { 
+			      $$ = strbuf_append_char($1, $2); 
+			      $$ = strbuf_append_str($1, $3->buf); 
+			      strbuf_free($3);
+			      $$ = strbuf_append_char($1, $4); 
+			    }
+                         | identifier_braces_inside '(' ')' %dprec 1
+			    { 
+			      $$ = strbuf_append_char($1, $2); 
+			      $$ = strbuf_append_char($1, $3); 
+			    }
+                         | identifier_braces_inside identifier_template %dprec 2
+			    {
+			      $$ = strbuf_append_str($1, $2->buf); 
+			      strbuf_free($2);
+			    }	
+;
+
+identifier_braces_inside_char : identifier_char | ws_nonl
+;
+
+identifier_template : '<' identifier_template_inside '>'
+                      {
+			$$ = strbuf_new();
+			strbuf_append_char($$, $1);
+			strbuf_append_str($$, $2->buf);
+			strbuf_free($2);
+			strbuf_append_char($$, $3);
+		      }
+;
+
+identifier_template_inside : identifier_template_inside_char
+                              {
+	                        $$ = strbuf_new(); 
+		                strbuf_append_char($$, $1); 
+	                      }           
+                           | identifier_template_inside identifier_template_inside_char
+			      { $$ = strbuf_append_char($1, $2); }
+                           | identifier_template_inside '<' identifier_template_inside '>'
+			      { 
+				$$ = strbuf_append_char($1, $2); 
+				$$ = strbuf_append_str($1, $3->buf); 
+				strbuf_free($3);
+				$$ = strbuf_append_char($1, $4); 
+			      }
+                           | identifier_template_inside identifier_braces
+			      {
+				$$ = strbuf_append_str($1, $2->buf); 
+				strbuf_free($2);
+			      }			
+;
+
+identifier_template_inside_char : identifier_char_no_templates | ws_nonl
+;
+
+digit_sequence : digit { $$ = strbuf_new(); strbuf_append_char($$, $1); }
+               | digit_sequence digit { $$ = strbuf_append_char($1, $2); }
+;
+
+hexadecimal_number : '0' 'x' hexadecimal_digit_sequence 
+                     { 
+                       $$ = $3;
+                       strbuf_prepend_str($$, "0x"); 
+                     }
+                   | '0' 'X' hexadecimal_digit_sequence 
+                     { 
+                       $$ = $3;
+                       strbuf_prepend_str($$, "0X"); 
+                     }
+;
+
+hexadecimal_digit_sequence : hexadecimal_digit 
+                               { 
+                                 $$ = strbuf_new(); 
+                                 strbuf_append_char($$, $1); 
+                               }
+                           | hexadecimal_digit_sequence hexadecimal_digit 
+                               { $$ = strbuf_append_char($1, $2); }
+;
+
+hexadecimal_digit : digit
+                  | 'a' | 'b' | 'c' | 'd' | 'e' | 'f'
+                  | 'A' | 'B' | 'C' | 'D' | 'E' | 'F'
+;
+
+digit : '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
+;
+
+nondigit : 'a' | 'b' | 'c' | 'd' | 'e' | 'f' | 'g' | 'h' | 'i' | 'j' | 'k'
+         | 'l' | 'm' | 'n' | 'o' | 'p' | 'q' | 'r' | 's' | 't' | 'u' | 'v' | 'w'
+         | 'x' | 'y' | 'z' 
+         | 'A' | 'B' | 'C' | 'D' | 'E' | 'F' | 'G' | 'H' | 'I' | 'J' | 'K'
+         | 'L' | 'M' | 'N' | 'O' | 'P' | 'Q' | 'R' | 'S' | 'T' | 'U' | 'V' | 'W'
+         | 'X' | 'Y' | 'Z'
+         | '_'
+;
+
+ /* whitespace */
+ws : ws_nonl | '\n' | '\r'
+;
+
+ /* No newline.*/
+ws_nonl : '\t' | ' '
+;
+
+ /* whitespace sequence without a newline */
+wss_nonl : ws_nonl
+         | wss_nonl ws_nonl
+;
+
+ /* whitespace sequence */
+wss : ws
+    | wss ws
+;
+ 
+ /* whitespace sequence allowed */
+wsa : 
+    | wss
+;
+
+keyword_in : 'i' 'n'
+;
+
+keyword_at : 'a' 't'
+;
+
+keyword_for : 'f' 'o' 'r'
+;
+
+keyword_vtable : 'v' 't' 'a' 'b' 'l' 'e'
+;
+
+keyword_from : 'f' 'r' 'o' 'm'
+;
+
+keyword_thread: 'T' 'h' 'r' 'e' 'a' 'd'
+;
+
+keyword_sighandler: '<' 's' 'i' 'g' 'n' 'a' 'l' ' ' 'h' 'a' 'n' 'd' 'l' 'e' 'r' ' ' 'c' 'a' 'l' 'l' 'e' 'd' '>'
+;
+
+%%
+
+static bool scanner_echo = false;
+static char *yyin;
+
+int yylex()
+{
+  char c = *yyin;
+  if (c == '\0')
+    return END;
+  ++yyin;
+
+  /* Debug output. */
+  if (scanner_echo)
+    putchar(c);
+
+  yylval.c = c;
+
+  /* Return a single char. */
+  return c;
+}
+
+/* This is the function that is actually called from outside. 
+ * @returns
+ *   Backtrace structure. Caller is responsible for calling
+ *   backtrace_free() on this.
+ *   Returns NULL when parsing failed.
+ */
+struct backtrace *backtrace_parse(char *input, bool debug_parser, bool debug_scanner)
+{
+  /* Skip the backtrace header information. */
+  char *btnoheader_a = strstr(input, "\nThread ");
+  char *btnoheader_b = strstr(input, "\n#");
+  char *btnoheader = input;
+  if (btnoheader_a)
+  {
+    if (btnoheader_b && btnoheader_b < btnoheader_a)
+      btnoheader = btnoheader_b + 1;
+    else
+      btnoheader = btnoheader_a + 1;
+  }
+  else if (btnoheader_b)
+    btnoheader = btnoheader_b + 1;
+
+  /* Bug fixing hack for broken backtraces.
+   * Sometimes the empty line is missing before new Thread section.
+   * This is against rules, but a bug (now fixed) in Linux kernel caused
+   * this.
+   */
+  char *thread_fixer = btnoheader + 1;
+  while ((thread_fixer = strstr(thread_fixer, "\nThread")) != NULL)
+  {
+    if (thread_fixer[-1] != '\n')
+      thread_fixer[-1] = '\n';
+
+    ++thread_fixer;
+  }
+
+  /* Bug fixing hack for GDB - remove wrongly placed newlines from the backtrace.
+   * Sometimes there is a newline in the local variable section.
+   * This is caused by some GDB hooks.
+   * Example: rhbz#538440
+   * #1  0x0000000000420939 in sync_deletions (mse=0x0, mfld=0x1b85020)
+   *    at mail-stub-exchange.c:1119
+   *     status = <value optimized out>
+   *     iter = 0x1af38d0
+   *     known_messages = 0x1b5c460Traceback (most recent call last):
+   *  File "/usr/share/glib-2.0/gdb/glib.py", line 98, in next
+   *    if long (node["key_hash"]) >= 2:
+   * RuntimeError: Cannot access memory at address 0x11
+   *
+   *     __PRETTY_FUNCTION__ = "sync_deletions"
+   * #2  0x0000000000423e6b in refresh_folder (stub=0x1b77f10 [MailStubExchange], 
+   * ...
+   *
+   * The code removes every empty line (also those containing only spaces),
+   * which is not followed by a new Thread section.
+   * 
+   * rhbz#555251 contains empty lines with spaces
+   */
+  char *empty_line = btnoheader; 
+  char *c = btnoheader;
+  while (*c)
+  {
+    if (*c == '\n')
+    {
+      char *cend = c + 1;
+      while (*cend == ' ' || *cend == '\t')
+        ++cend;
+      if (*cend == '\n' && 0 != strncmp(cend, "\nThread", strlen("\nThread")))
+        memmove(c, cend, strlen(cend) + 1);
+    }
+    ++c;
+  }
+  while ((empty_line = strstr(empty_line, "\n\n")) != NULL)
+  {
+    if (0 != strncmp(empty_line, "\n\nThread", strlen("\n\nThread")))
+    {
+      /* Remove the empty line by converting the first newline to char. */
+      empty_line[0] = 'X'; 
+    }
+    ++empty_line;
+  }
+
+  /* Prepare for running parser. */
+  g_backtrace = 0;
+  yyin = btnoheader;
+#if YYDEBUG == 1
+  if (debug_parser)
+    yydebug = 1;
+#endif
+  scanner_echo = debug_scanner;
+
+  /* Parse. */
+  int failure = yyparse();
+  
+  /* Separate debugging output. */
+  if (scanner_echo)
+    putchar('\n'); 
+
+  if (failure)
+  {
+    if (g_backtrace)
+    {
+      backtrace_free(g_backtrace);
+      g_backtrace = NULL;
+    }
+    fprintf(stderr, "Error while parsing backtrace.\n");
+  }
+
+  return g_backtrace;
+}
diff --git a/lib/Utils/strbuf.c b/lib/Utils/strbuf.c
new file mode 100644
index 00000000..6153ffe1
--- /dev/null
+++ b/lib/Utils/strbuf.c
@@ -0,0 +1,130 @@
+/*  -*-mode:c;c-file-style:"bsd";c-basic-offset:4;indent-tabs-mode:nil-*-
+    String buffer implementation
+
+    Copyright (C) 2009  RedHat 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 "strbuf.h"
+#include <stdlib.h>
+#include <stdio.h>
+#include <assert.h>
+#include <string.h>
+#include <stdarg.h>
+#include "xfuncs.h"
+
+struct strbuf *strbuf_new()
+{
+    struct strbuf *buf = xmalloc(sizeof(struct strbuf));
+    buf->alloc = 8;
+    buf->len = 0;
+    buf->buf = xmalloc(buf->alloc);
+    buf->buf[buf->len] = '\0';
+    return buf;
+}
+
+void strbuf_free(struct strbuf *strbuf)
+{
+    free(strbuf->buf);
+    free(strbuf);
+}
+
+void strbuf_free_nobuf(struct strbuf *strbuf)
+{
+    free(strbuf);
+}
+
+
+void strbuf_clear(struct strbuf *strbuf)
+{
+    assert(strbuf->alloc > 0);
+    strbuf->len = 0;
+    strbuf->buf[0] = '\0';
+}
+
+/* Ensures that the buffer can be extended by num characters
+ * without touching malloc/realloc.
+ */
+static void strbuf_grow(struct strbuf *strbuf, int num)
+{
+    if (strbuf->len + num + 1 > strbuf->alloc)
+    {
+	while (strbuf->len + num + 1 > strbuf->alloc)
+	    strbuf->alloc *= 2; /* huge grow = infinite loop */
+	    
+	strbuf->buf = realloc(strbuf->buf, strbuf->alloc);
+	if (!strbuf->buf)
+	{
+	    puts("Error while allocating memory for string buffer.");
+	    exit(5);
+	}
+    }
+}
+
+struct strbuf *strbuf_append_char(struct strbuf *strbuf, char c)
+{
+    strbuf_grow(strbuf, 1);
+    strbuf->buf[strbuf->len++] = c;
+    strbuf->buf[strbuf->len] = '\0';
+    return strbuf;
+}
+
+struct strbuf *strbuf_append_str(struct strbuf *strbuf, const char *str)
+{
+    int len = strlen(str);
+    strbuf_grow(strbuf, len);
+    assert(strbuf->len + len < strbuf->alloc);
+    strcpy(strbuf->buf + strbuf->len, str);
+    strbuf->len += len;
+    return strbuf;
+}
+
+struct strbuf *strbuf_prepend_str(struct strbuf *strbuf, const char *str)
+{
+    int len = strlen(str);
+    strbuf_grow(strbuf, len);
+    assert(strbuf->len + len < strbuf->alloc);
+    memmove(strbuf->buf + len, strbuf->buf, strbuf->len + 1);
+    memcpy(strbuf->buf, str, len);
+    return strbuf;
+}
+
+struct strbuf *strbuf_append_strf(struct strbuf *strbuf, const char *format, ...)
+{
+    va_list p;
+    char *string_ptr;
+    
+    va_start(p, format);
+    string_ptr = xvasprintf(format, p);
+    va_end(p);
+    
+    strbuf_append_str(strbuf, string_ptr);
+    free(string_ptr);
+    return strbuf;
+}
+
+struct strbuf *strbuf_prepend_strf(struct strbuf *strbuf, const char *format, ...)
+{
+    va_list p;
+    char *string_ptr;
+    
+    va_start(p, format);
+    string_ptr = xvasprintf(format, p);
+    va_end(p);
+    
+    strbuf_prepend_str(strbuf, string_ptr);
+    free(string_ptr);
+    return strbuf;
+}
diff --git a/lib/Utils/strbuf.h b/lib/Utils/strbuf.h
new file mode 100644
index 00000000..d0c9c981
--- /dev/null
+++ b/lib/Utils/strbuf.h
@@ -0,0 +1,48 @@
+/*
+    strbuf.h - string buffer
+
+    Copyright (C) 2009  RedHat 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 STRBUF_H
+#define STRBUF_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+struct strbuf {
+  int alloc;
+  int len;
+  char *buf;
+};
+
+extern struct strbuf *strbuf_new();
+extern void strbuf_free(struct strbuf *strbuf);
+/* Releases strbuf, but not the internal buffer. */
+extern void strbuf_free_nobuf(struct strbuf *strbuf);
+extern void strbuf_clear(struct strbuf *strbuf);
+extern struct strbuf *strbuf_append_char(struct strbuf *strbuf, char c);
+extern struct strbuf *strbuf_append_str(struct strbuf *strbuf, const char *str);
+extern struct strbuf *strbuf_prepend_str(struct strbuf *strbuf, const char *str);
+extern struct strbuf *strbuf_append_strf(struct strbuf *strbuf, const char *format, ...);
+extern struct strbuf *strbuf_prepend_strf(struct strbuf *strbuf, const char *format, ...);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
diff --git a/lib/Utils/xfuncs.cpp b/lib/Utils/xfuncs.cpp
index 74fdac76..fd29b704 100644
--- a/lib/Utils/xfuncs.cpp
+++ b/lib/Utils/xfuncs.cpp
@@ -389,12 +389,12 @@ bool string_to_bool(const char *s)
 
 void xsetreuid(uid_t ruid, uid_t euid)
 {
-	if (setreuid(ruid, euid) != 0)
-		perror_msg_and_die("can't set %cid %lu", 'u', (long)ruid);
+    if (setreuid(ruid, euid) != 0)
+        perror_msg_and_die("can't set %cid %lu", 'u', (long)ruid);
 }
 
 void xsetregid(gid_t rgid, gid_t egid)
 {
-	if (setregid(rgid, egid) != 0)
-		perror_msg_and_die("can't set %cid %lu", 'g', (long)rgid);
+    if (setregid(rgid, egid) != 0)
+        perror_msg_and_die("can't set %cid %lu", 'g', (long)rgid);
 }
diff --git a/lib/Utils/xfuncs.h b/lib/Utils/xfuncs.h
new file mode 100644
index 00000000..327d9c9a
--- /dev/null
+++ b/lib/Utils/xfuncs.h
@@ -0,0 +1,104 @@
+/*
+    Copyright (C) 2010  ABRT team
+    Copyright (C) 2010  RedHat 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 ABRT_XFUNCS_H
+#define ABRT_XFUNCS_H
+
+#include <sys/socket.h>
+#include <sys/stat.h>
+#include <dirent.h>
+#include <stdbool.h>
+
+int ndelay_on(int fd);
+int ndelay_off(int fd);
+int close_on_exec_on(int fd);
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+void* xmalloc(size_t size);
+void* xrealloc(void *ptr, size_t size);
+void* xzalloc(size_t size);
+char* xstrdup(const char *s);
+char* xstrndup(const char *s, int n);
+
+#ifdef __cplusplus
+}
+#endif
+
+void xpipe(int filedes[2]);
+void xdup(int from);
+void xdup2(int from, int to);
+void xmove_fd(int from, int to);
+
+extern void xwrite(int fd, const void *buf, size_t count);
+extern void xwrite_str(int fd, const char *str);
+
+off_t xlseek(int fd, off_t offset, int whence);
+
+void xchdir(const char *path);
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+char* xvasprintf(const char *format, va_list p);
+char* xasprintf(const char *format, ...);
+
+#ifdef __cplusplus
+}
+#endif
+
+#ifdef __cplusplus
+std::string ssprintf(const char *format, ...);
+#endif
+
+void xsetenv(const char *key, const char *value);
+int xsocket(int domain, int type, int protocol);
+void xbind(int sockfd, struct sockaddr *my_addr, socklen_t addrlen);
+void xlisten(int s, int backlog);
+ssize_t xsendto(int s, const void *buf, size_t len, const struct sockaddr *to, socklen_t tolen);
+void xstat(const char *name, struct stat *stat_buf);
+
+#ifdef __cplusplus
+std::string get_home_dir(uid_t uid);
+#endif
+
+int xopen3(const char *pathname, int flags, int mode);
+int xopen(const char *pathname, int flags);
+void xunlink(const char *pathname);
+
+/* Just testing dent->d_type == DT_REG is wrong: some filesystems
+ * do not report the type, they report DT_UNKNOWN for every dirent
+ * (and this is not a bug in filesystem, this is allowed by standards).
+ * This function handles this case. Note: it returns 0 on symlinks
+ * even if they point to regular files.
+ */
+int is_regular_file(struct dirent *dent, const char *dirname);
+bool dot_or_dotdot(const char *filename);
+char *last_char_is(const char *s, int c);
+#ifdef __cplusplus
+std::string concat_path_file(const char *path, const char *filename);
+#endif
+bool string_to_bool(const char *s);
+
+void xsetreuid(uid_t ruid, uid_t euid);
+void xsetregid(gid_t rgid, gid_t egid);
+
+#endif