Merged devel-threads branch (r3066:3364) back into trunk

5 files changed, 567 insertions, 110 deletions

diff --git a/program/include/html.php b/program/include/html.php
index 99132a1aa..0930f5853 100644
--- a/program/include/html.php
+++ b/program/include/html.php
@@ -5,7 +5,7 @@
  | program/include/html.php                                              |
  |                                                                       |
  | This file is part of the RoundCube Webmail client                     |
- | Copyright (C) 2005-2009, RoundCube Dev, - Switzerland                 |
+ | Copyright (C) 2005-2010, RoundCube Dev, - Switzerland                 |
  | Licensed under the GNU GPL                                            |
  |                                                                       |
  | PURPOSE:                                                              |
@@ -34,8 +34,7 @@ class html
 
     public static $lc_tags = true;
     public static $common_attrib = array('id','class','style','title','align');
-    public static $containers = array('iframe','div','span','p','h1','h2','h3',
-	'form','textarea','table','tr','th','td','style','script');
+    public static $containers = array('iframe','div','span','p','h1','h2','h3','form','textarea','table','thead','tbody','tr','th','td','style','script');
 
     /**
      * Constructor
diff --git a/program/include/rcmail.php b/program/include/rcmail.php
index 81f61379b..3ea418046 100644
--- a/program/include/rcmail.php
+++ b/program/include/rcmail.php
@@ -410,7 +410,6 @@ class rcmail
     $this->imap = new rcube_imap($this->db);
     $this->imap->debug_level = $this->config->get('debug_level');
     $this->imap->skip_deleted = $this->config->get('skip_deleted');
-    $this->imap->index_sort = $this->config->get('index_sort', true);
 
     // enable caching of imap data
     if ($this->config->get('enable_caching')) {
diff --git a/program/include/rcube_imap.php b/program/include/rcube_imap.php
index 91d36c2a3..332d53029 100644
--- a/program/include/rcube_imap.php
+++ b/program/include/rcube_imap.php
@@ -5,7 +5,7 @@
  | program/include/rcube_imap.php                                        |
  |                                                                       |
  | This file is part of the RoundCube Webmail client                     |
- | Copyright (C) 2005-2009, RoundCube Dev. - Switzerland                 |
+ | Copyright (C) 2005-2010, RoundCube Dev. - Switzerland                 |
  | Licensed under the GNU GPL                                            |
  |                                                                       |
  | PURPOSE:                                                              |
@@ -41,35 +41,40 @@ require_once('lib/tnef_decoder.inc');
  */
 class rcube_imap
 {
-  var $db;
-  var $conn;
-  var $root_dir = '';
-  var $mailbox = 'INBOX';
-  var $list_page = 1;
-  var $page_size = 10;
-  var $sort_field = 'date';
-  var $sort_order = 'DESC';
-  var $index_sort = true;
-  var $delimiter = NULL;
-  var $caching_enabled = FALSE;
-  var $default_charset = 'ISO-8859-1';
-  var $struct_charset = NULL;
-  var $default_folders = array('INBOX');
-  var $fetch_add_headers = '';
-  var $cache = array();
-  var $cache_keys = array();  
-  var $cache_changes = array();
-  var $uid_id_map = array();
-  var $msg_headers = array();
-  var $skip_deleted = FALSE;
-  var $search_set = NULL;
-  var $search_string = '';
-  var $search_charset = '';
-  var $search_sort_field = '';  
-  var $debug_level = 1;
-  var $error_code = 0;
-  var $options = array('auth_method' => 'check');
-  
+  public $debug_level = 1;
+  public $error_code = 0;
+  public $skip_deleted = false;
+  public $root_dir = '';
+  public $page_size = 10;
+  public $list_page = 1;
+  public $delimiter = NULL;
+  public $threading = false;
+  public $fetch_add_headers = '';
+  public $conn;
+
+  private $db;
+  private $root_ns = '';
+  private $mailbox = 'INBOX';
+  private $sort_field = '';
+  private $sort_order = 'DESC';
+  private $caching_enabled = false;
+  private $default_charset = 'ISO-8859-1';
+  private $struct_charset = NULL;
+  private $default_folders = array('INBOX');
+  private $default_folders_lc = array('inbox');
+  private $icache = array();
+  private $cache = array();
+  private $cache_keys = array();  
+  private $cache_changes = array();
+  private $uid_id_map = array();
+  private $msg_headers = array();
+  public  $search_set = NULL;
+  public  $search_string = '';
+  private $search_charset = '';
+  private $search_sort_field = '';
+  private $search_threads = false;
+  private $db_header_fields = array('idx', 'uid', 'subject', 'from', 'to', 'cc', 'date', 'size');
+  private $options = array('auth_method' => 'check');
   private $host, $user, $pass, $port, $ssl;
 
 
@@ -299,17 +304,18 @@ class rcube_imap
    * @param  string  Charset of search string
    * @param  string  Sorting field
    */
-  function set_search_set($str=null, $msgs=null, $charset=null, $sort_field=null)
+  function set_search_set($str=null, $msgs=null, $charset=null, $sort_field=null, $threads=false)
     {
     if (is_array($str) && $msgs == null)
-      list($str, $msgs, $charset, $sort_field) = $str;
+      list($str, $msgs, $charset, $sort_field, $threads) = $str;
     if ($msgs != null && !is_array($msgs))
       $msgs = explode(',', $msgs);
-      
+
     $this->search_string = $str;
     $this->search_set = $msgs;
     $this->search_charset = $charset;
     $this->search_sort_field = $sort_field;
+    $this->search_threads = $threads;
     }
 
 
@@ -319,7 +325,12 @@ class rcube_imap
    */
   function get_search_set()
     {
-    return array($this->search_string, $this->search_set, $this->search_charset, $this->search_sort_field);
+    return array($this->search_string,
+	$this->search_set,
+	$this->search_charset,
+	$this->search_sort_field,
+	$this->search_threads,
+	);
     }
 
 
@@ -349,6 +360,30 @@ class rcube_imap
 
 
   /**
+   * Sets threading flag to the best supported THREAD algorithm
+   *
+   * @param  boolean  TRUE to enable and FALSE
+   * @return string   Algorithm or false if THREAD is not supported
+   * @access public
+   */
+  function set_threading($enable=false)
+    {
+    $this->threading = false;
+    
+    if ($enable) {
+      if ($this->get_capability('THREAD=REFS'))
+        $this->threading = 'REFS';
+      else if ($this->get_capability('THREAD=REFERENCES'))
+        $this->threading = 'REFERENCES';
+      else if ($this->get_capability('THREAD=ORDEREDSUBJECT'))
+        $this->threading = 'ORDEREDSUBJECT';
+      }
+      
+    return $this->threading;
+    }
+
+
+  /**
    * Checks the PERMANENTFLAGS capability of the current mailbox
    * and returns true if the given flag is supported by the IMAP server
    *
@@ -480,11 +515,15 @@ class rcube_imap
 
     if (empty($mailbox))
       $mailbox = $this->mailbox;
-      
-    // count search set
-    if ($this->search_string && $mailbox == $this->mailbox && $mode == 'ALL' && !$force)
-      return count((array)$this->search_set);
 
+    // count search set
+    if ($this->search_string && $mailbox == $this->mailbox && ($mode == 'ALL' || $mode == 'THREADS') && !$force) {
+      if ($this->search_threads)
+        return $mode == 'ALL' ? count((array)$this->search_set['depth']) : count((array)$this->search_set['tree']);
+      else
+        return count((array)$this->search_set);
+      }
+    
     $a_mailbox_cache = $this->get_cache('messagecount');
     
     // return cached value
@@ -494,8 +533,11 @@ class rcube_imap
     if (!is_array($a_mailbox_cache[$mailbox]))
       $a_mailbox_cache[$mailbox] = array();
 
+    if ($mode == 'THREADS')
+      $count = $this->_threadcount($mailbox);
+
     // RECENT count is fetched a bit different
-    if ($mode == 'RECENT')
+    else if ($mode == 'RECENT')
        $count = iil_C_CheckForRecent($this->conn, $mailbox);
 
     // use SEARCH for message counting
@@ -534,6 +576,24 @@ class rcube_imap
 
 
   /**
+   * Private method for getting nr of threads
+   *
+   * @access  private
+   * @see     rcube_imap::messagecount()
+   */
+  private function _threadcount($mailbox)
+    {
+    if (!empty($this->icache['threads']))
+      return count($this->icache['threads']['tree']);
+    
+    list ($thread_tree, $msg_depth, $has_children) = $this->_fetch_threads($mailbox);
+
+//    $this->update_thread_cache($mailbox, $thread_tree, $msg_depth, $has_children);
+    return count($thread_tree);  
+    }
+
+
+  /**
    * Public method for listing headers
    * convert mailbox name with root dir first
    *
@@ -567,6 +627,9 @@ class rcube_imap
     if ($this->search_string && $mailbox == $this->mailbox)
       return $this->_list_header_set($mailbox, $page, $sort_field, $sort_order, $slice);
 
+    if ($this->threading)
+      return $this->_list_thread_headers($mailbox, $page, $sort_field, $sort_order, $recursive, $slice);
+
     $this->_set_sort_order($sort_field, $sort_order);
 
     $page = $page ? $page : $this->list_page;
@@ -593,8 +656,8 @@ class rcube_imap
     // retrieve headers from IMAP
     $a_msg_headers = array();
 
-    // use message index sort for sorting by Date (for better performance)
-    if ($this->index_sort && $this->sort_field == 'date')
+    // use message index sort as default sorting (for better performance)
+    if (!$this->sort_field)
       {
         if ($this->skip_deleted) {
           // @TODO: this could be cached
@@ -671,6 +734,140 @@ class rcube_imap
 
 
   /**
+   * Private method for listing message headers using threads
+   *
+   * @access  private
+   * @see     rcube_imap::list_headers
+   */
+  private function _list_thread_headers($mailbox, $page=NULL, $sort_field=NULL, $sort_order=NULL, $recursive=FALSE, $slice=0)
+    {
+    $this->_set_sort_order($sort_field, $sort_order);
+
+    $page = $page ? $page : $this->list_page;
+//    $cache_key = $mailbox.'.msg';
+//    $cache_status = $this->check_cache_status($mailbox, $cache_key);
+
+    // get all threads (default sort order)
+    list ($thread_tree, $msg_depth, $has_children) = $this->_fetch_threads($mailbox);
+
+    if (empty($thread_tree))
+      return array();
+
+    $msg_index = $this->_sort_threads($mailbox, $thread_tree);
+
+    return $this->_fetch_thread_headers($mailbox, $thread_tree, $msg_depth, $has_children,
+      $msg_index, $page, $slice);
+    }
+
+
+  /**
+   * Private method for fetching threads data
+   *
+   * @param   string   Mailbox/folder name
+   * @return  array    Array with thread data
+   * @access  private
+   */
+  private function _fetch_threads($mailbox)
+    {
+    if (empty($this->icache['threads'])) {
+      // get all threads
+      list ($thread_tree, $msg_depth, $has_children) = iil_C_Thread($this->conn,
+        $mailbox, $this->threading, $this->skip_deleted ? 'UNDELETED' : '');
+    
+      // add to internal (fast) cache
+      $this->icache['threads'] = array();
+      $this->icache['threads']['tree'] = $thread_tree;
+      $this->icache['threads']['depth'] = $msg_depth;
+      $this->icache['threads']['has_children'] = $has_children;
+      }
+
+    return array(
+      $this->icache['threads']['tree'],
+      $this->icache['threads']['depth'],
+      $this->icache['threads']['has_children'],
+      );
+    }
+
+
+  /**
+   * Private method for fetching threaded messages headers
+   *
+   * @access  private
+   */
+  private function _fetch_thread_headers($mailbox, $thread_tree, $msg_depth, $has_children, $msg_index, $page, $slice=0)
+    {
+    $cache_key = $mailbox.'.msg';
+    // now get IDs for current page
+    list($begin, $end) = $this->_get_message_range(count($msg_index), $page);
+    $msg_index = array_slice($msg_index, $begin, $end-$begin);
+
+    if ($slice)
+      $msg_index = array_slice($msg_index, ($this->sort_order == 'DESC' ? 0 : -$slice), $slice);
+
+    if ($this->sort_order == 'DESC')
+      $msg_index = array_reverse($msg_index);
+
+    // flatten threads array
+    // @TODO: fetch children only in expanded mode
+    $all_ids = array();
+    foreach($msg_index as $root) {
+      $all_ids[] = $root;
+      if (!empty($thread_tree[$root]))
+        $all_ids = array_merge($all_ids, array_keys_recursive($thread_tree[$root]));
+      }
+
+    // fetch reqested headers from server
+    $this->_fetch_headers($mailbox, $all_ids, $a_msg_headers, $cache_key);
+
+    // return empty array if no messages found
+    if (!is_array($a_msg_headers) || empty($a_msg_headers))
+      return array();
+    
+    // use this class for message sorting
+    $sorter = new rcube_header_sorter();
+    $sorter->set_sequence_numbers($all_ids);
+    $sorter->sort_headers($a_msg_headers);
+
+    // Set depth, has_children and unread_children fields in headers
+    $this->_set_thread_flags($a_msg_headers, $msg_depth, $has_children);
+
+    return array_values($a_msg_headers);
+    }
+
+
+  /**
+   * Private method for setting threaded messages flags:
+   * depth, has_children and unread_children
+   *
+   * @param  array   Reference to headers array indexed by message ID
+   * @param  array   Array of messages depth indexed by message ID
+   * @param  array   Array of messages children flags indexed by message ID
+   * @return array   Message headers array indexed by message ID
+   * @access private
+   */
+  private function _set_thread_flags(&$headers, $msg_depth, $msg_children)
+    {
+    $parents = array();
+
+    foreach ($headers as $idx => $header) {
+      $id = $header->id;
+      $depth = $msg_depth[$id];
+      $parents = array_slice($parents, 0, $depth);
+
+      if (!empty($parents)) {
+        $headers[$idx]->parent_uid = end($parents);
+        if (!$header->seen)
+          $headers[$parents[0]]->unread_children++;
+        }
+      array_push($parents, $header->uid);
+
+      $headers[$idx]->depth = $depth;
+      $headers[$idx]->has_children = $msg_children[$id];
+      }
+    }
+
+
+  /**
    * Private method for listing a set of message headers (search results)
    *
    * @param   string   Mailbox/folder name
@@ -687,6 +884,14 @@ class rcube_imap
     if (!strlen($mailbox) || empty($this->search_set))
       return array();
 
+    // use saved messages from searching
+    if ($this->threading)
+      return $this->_list_thread_header_set($mailbox, $page, $sort_field, $sort_order, $slice);
+
+    // search set is threaded, we need a new one
+    if ($this->search_threads)
+      $this->search('', $this->search_string, $this->search_charset, $sort_field);
+    
     $msgs = $this->search_set;
     $a_msg_headers = array();
     $page = $page ? $page : $this->list_page;
@@ -694,8 +899,8 @@ class rcube_imap
 
     $this->_set_sort_order($sort_field, $sort_order);
 
-    // quickest method
-    if ($this->index_sort && $this->search_sort_field == 'date' && $this->sort_field == 'date')
+    // quickest method (default sorting)
+    if (!$this->search_sort_field && !$this->sort_field)
       {
       if ($sort_order == 'DESC')
         $msgs = array_reverse($msgs);
@@ -716,8 +921,9 @@ class rcube_imap
 
       return array_values($a_msg_headers);
       }
+
     // sorted messages, so we can first slice array and then fetch only wanted headers
-    if ($this->get_capability('sort') && (!$this->index_sort || $this->sort_field != 'date')) // SORT searching result
+    if ($this->get_capability('sort')) // SORT searching result
       {
       // reset search set if sorting field has been changed
       if ($this->sort_field && $this->search_sort_field != $this->sort_field)
@@ -745,10 +951,10 @@ class rcube_imap
 
       return array_values($a_msg_headers);
       }
-    else { // SEARCH searching result, need sorting
+    else { // SEARCH result, need sorting
       $cnt = count($msgs);
       // 300: experimantal value for best result
-      if (($cnt > 300 && $cnt > $this->page_size) || ($this->index_sort && $this->sort_field == 'date')) {
+      if (($cnt > 300 && $cnt > $this->page_size) || !$this->sort_field) {
         // use memory less expensive (and quick) method for big result set
         $a_index = $this->message_index('', $this->sort_field, $this->sort_order);
         // get messages uids for one page...
@@ -791,6 +997,40 @@ class rcube_imap
 
 
   /**
+   * Private method for listing a set of threaded message headers (search results)
+   *
+   * @param   string   Mailbox/folder name
+   * @param   int      Current page to list
+   * @param   string   Header field to sort by
+   * @param   string   Sort order [ASC|DESC]
+   * @param   boolean  Number of slice items to extract from result array
+   * @return  array    Indexed array with message header objects
+   * @access  private
+   * @see     rcube_imap::list_header_set()
+   */
+  private function _list_thread_header_set($mailbox, $page=NULL, $sort_field=NULL, $sort_order=NULL, $slice=0)
+    {
+    // update search_set if previous data was fetched with disabled threading
+    if (!$this->search_threads)
+      $this->search('', $this->search_string, $this->search_charset, $sort_field);
+
+    $thread_tree = $this->search_set['tree'];
+    $msg_depth = $this->search_set['depth'];
+    $has_children = $this->search_set['children'];
+    $a_msg_headers = array();
+
+    $page = $page ? $page : $this->list_page;
+    $start_msg = ($page-1) * $this->page_size;
+
+    $this->_set_sort_order($sort_field, $sort_order);
+
+    $msg_index = $this->_sort_threads($mailbox, $thread_tree, array_keys($msg_depth));
+
+    return $this->_fetch_thread_headers($mailbox, $thread_tree, $msg_depth, $has_children, $msg_index, $page, $slice=0);
+    }
+
+
+  /**
    * Helper function to get first and last index of the requested set
    *
    * @param  int     message count
@@ -901,18 +1141,22 @@ class rcube_imap
    */
   function message_index($mbox_name='', $sort_field=NULL, $sort_order=NULL)
     {
+    if ($this->threading)
+      return $this->thread_index($mbox_name, $sort_field, $sort_order);
+
     $this->_set_sort_order($sort_field, $sort_order);
 
     $mailbox = $mbox_name ? $this->mod_mailbox($mbox_name) : $this->mailbox;
     $key = "{$mailbox}:{$this->sort_field}:{$this->sort_order}:{$this->search_string}.msgi";
 
     // we have a saved search result, get index from there
-    if (!isset($this->cache[$key]) && $this->search_string && $mailbox == $this->mailbox)
+    if (!isset($this->cache[$key]) && $this->search_string
+      && !$this->search_threads && $mailbox == $this->mailbox)
     {
       $this->cache[$key] = array();
       
-      // use message index sort for sorting by Date
-      if ($this->index_sort && $this->sort_field == 'date')
+      // use message index sort as default sorting
+      if (!$this->sort_field)
       {
         $msgs = $this->search_set;
 
@@ -937,7 +1181,8 @@ class rcube_imap
       }
       else
       {
-        $a_index = iil_C_FetchHeaderIndex($this->conn, $mailbox, join(',', $this->search_set), $this->sort_field, $this->skip_deleted);
+        $a_index = iil_C_FetchHeaderIndex($this->conn, $mailbox,
+	  join(',', $this->search_set), $this->sort_field, $this->skip_deleted);
 
         if ($this->sort_order=="ASC")
           asort($a_index);
@@ -963,8 +1208,8 @@ class rcube_imap
       return array_keys($a_index);
       }
 
-    // use message index sort for sorting by Date
-    if ($this->index_sort && $this->sort_field == 'date')
+    // use message index sort as default sorting
+    if (!$this->sort_field)
       {
       if ($this->skip_deleted) {
         $a_index = $this->_search_index($mailbox, 'ALL');
@@ -1002,9 +1247,90 @@ class rcube_imap
 
 
   /**
+   * Return sorted array of threaded message IDs (not UIDs)
+   *
+   * @param string Mailbox to get index from
+   * @param string Sort column
+   * @param string Sort order [ASC, DESC]
+   * @return array Indexed array with message IDs
+   */
+  function thread_index($mbox_name='', $sort_field=NULL, $sort_order=NULL)
+    {
+    $this->_set_sort_order($sort_field, $sort_order);
+
+    $mailbox = $mbox_name ? $this->mod_mailbox($mbox_name) : $this->mailbox;
+    $key = "{$mailbox}:{$this->sort_field}:{$this->sort_order}:{$this->search_string}.thi";
+
+    // we have a saved search result, get index from there
+    if (!isset($this->cache[$key]) && $this->search_string
+      && $this->search_threads && $mailbox == $this->mailbox)
+    {
+      // use message IDs for better performance
+      $ids = array_keys_recursive($this->search_set['tree']);
+      $this->cache[$key] = $this->_flatten_threads($mailbox, $this->search_set['tree'], $ids);
+    }
+
+    // have stored it in RAM
+    if (isset($this->cache[$key]))
+      return $this->cache[$key];
+/*
+    // check local cache
+    $cache_key = $mailbox.'.msg';
+    $cache_status = $this->check_cache_status($mailbox, $cache_key);
+
+    // cache is OK
+    if ($cache_status>0)
+      {
+      $a_index = $this->get_message_cache_index($cache_key, TRUE, $this->sort_field, $this->sort_order);
+      return array_keys($a_index);
+      }
+*/
+    // get all threads (default sort order)
+    list ($thread_tree) = $this->_fetch_threads($mailbox);
+
+    $this->cache[$key] = $this->_flatten_threads($mailbox, $thread_tree);
+    
+    return $this->cache[$key];
+    }
+
+
+  /**
+   * Return array of threaded messages (all, not only roots)
+   *
+   * @param string Mailbox to get index from
+   * @param array  Threaded messages array (see _fetch_threads())
+   * @param array  Message IDs if we know what we need (e.g. search result)
+   *               for better performance
+   * @return array Indexed array with message IDs
+   *
+   * @access private
+   */
+  private function _flatten_threads($mailbox, $thread_tree, $ids=null)
+    {
+    if (empty($thread_tree))
+      return array();
+
+    $msg_index = $this->_sort_threads($mailbox, $thread_tree, $ids);
+
+    if ($this->sort_order == 'DESC')
+      $msg_index = array_reverse($msg_index);
+	  
+    // flatten threads array
+    $all_ids = array();
+    foreach($msg_index as $root) {
+      $all_ids[] = $root;
+      if (!empty($thread_tree[$root]))
+        $all_ids = array_merge($all_ids, array_keys_recursive($thread_tree[$root]));
+      }
+
+    return $all_ids;
+    }
+
+
+  /**
    * @access private
    */
-  function sync_header_index($mailbox)
+  private function sync_header_index($mailbox)
     {
     $cache_key = $mailbox.'.msg';
     $cache_index = $this->get_message_cache_index($cache_key);
@@ -1102,7 +1428,7 @@ class rcube_imap
       $results = $this->search($mbox_name, $res, NULL, $sort_field);
     }
 
-    $this->set_search_set($str, $results, $charset, $sort_field);
+    $this->set_search_set($str, $results, $charset, $sort_field, (bool)$this->threading);
 
     return $results;
     }
@@ -1122,7 +1448,17 @@ class rcube_imap
     if ($this->skip_deleted && !preg_match('/UNDELETED/', $criteria))
       $criteria = 'UNDELETED '.$criteria;
 
-    if ($sort_field && $this->get_capability('sort') && (!$this->index_sort || $sort_field != 'date')) {
+    if ($this->threading) {
+      list ($thread_tree, $msg_depth, $has_children) = iil_C_Thread($this->conn,
+            $mailbox, $this->threading, $criteria, $charset);
+
+      $a_messages = array(
+        'tree' 	=> $thread_tree,
+	'depth'	=> $msg_depth,
+	'children' => $has_children
+        );
+      }
+    else if ($sort_field && $this->get_capability('sort')) {
       $charset = $charset ? $charset : $this->default_charset;
       $a_messages = iil_C_Sort($this->conn, $mailbox, $sort_field, $criteria, FALSE, $charset);
       }
@@ -1135,7 +1471,7 @@ class rcube_imap
         $a_messages = iil_C_Search($this->conn, $mailbox, ($charset ? "CHARSET $charset " : '') . $criteria);
     
         // I didn't found that SEARCH always returns sorted IDs
-        if ($this->index_sort && $this->sort_field == 'date')
+        if (!$this->sort_field)
           sort($a_messages);
         }
       }
@@ -1149,6 +1485,90 @@ class rcube_imap
     
   
   /**
+   * Sort thread
+   *
+   * @param string Mailbox name
+   * @param  array Unsorted thread tree (iil_C_Thread() result)
+   * @param  array Message IDs if we know what we need (e.g. search result)
+   * @return array Sorted roots IDs
+   * @access private
+   */
+  private function _sort_threads($mailbox, $thread_tree, $ids=NULL)
+    {
+    // THREAD=ORDEREDSUBJECT: 	sorting by sent date of root message
+    // THREAD=REFERENCES: 	sorting by sent date of root message
+    // THREAD=REFS: 		sorting by the most recent date in each thread
+    // default sorting
+    if (!$this->sort_field || ($this->sort_field == 'date' && $this->threading == 'REFS')) {
+        return array_keys($thread_tree);
+      }
+    // here we'll implement REFS sorting, for performance reason
+    else { // ($sort_field == 'date' && $this->threading != 'REFS')
+      // use SORT command
+      if ($this->get_capability('sort')) {
+        $a_index = iil_C_Sort($this->conn, $mailbox, $this->sort_field,
+	    !empty($ids) ? $ids : ($this->skip_deleted ? 'UNDELETED' : ''));
+        }
+      else {
+        // fetch specified headers for all messages and sort them
+        $a_index = iil_C_FetchHeaderIndex($this->conn, $mailbox, !empty($ids) ? $ids : "1:*",
+	    $this->sort_field, $this->skip_deleted);
+        asort($a_index); // ASC
+	$a_index = array_values($a_index);
+        }
+
+	return $this->_sort_thread_refs($thread_tree, $a_index);
+      }
+    }
+
+
+  /**
+   * THREAD=REFS sorting implementation
+   *
+   * @param  array   Thread tree array (message identifiers as keys)
+   * @param  array   Array of sorted message identifiers
+   * @return array   Array of sorted roots messages
+   * @access private
+   */
+  private function _sort_thread_refs($tree, $index)
+    {
+    if (empty($tree))
+      return array();
+    
+    $index = array_combine(array_values($index), $index);
+
+    // assign roots
+    foreach ($tree as $idx => $val) {
+      $index[$idx] = $idx;
+      if (!empty($val)) {
+        $idx_arr = array_keys_recursive($tree[$idx]);
+        foreach ($idx_arr as $subidx)
+          $index[$subidx] = $idx;
+        }
+      }
+
+    $index = array_values($index);  
+
+    // create sorted array of roots
+    $msg_index = array();
+    if ($this->sort_order != 'DESC') {
+      foreach ($index as $idx)
+        if (!isset($msg_index[$idx]))
+          $msg_index[$idx] = $idx;
+      $msg_index = array_values($msg_index);
+      }
+    else {
+      for ($x=count($index)-1; $x>=0; $x--)
+        if (!isset($msg_index[$index[$x]]))
+          $msg_index[$index[$x]] = $index[$x];
+      $msg_index = array_reverse($msg_index);
+      }
+
+    return $msg_index;
+    }
+
+
+  /**
    * Refresh saved search set
    *
    * @return array Current search set
@@ -1156,7 +1576,8 @@ class rcube_imap
   function refresh_search()
     {
     if (!empty($this->search_string))
-      $this->search_set = $this->search('', $this->search_string, $this->search_charset, $this->search_sort_field);
+      $this->search_set = $this->search('', $this->search_string, $this->search_charset,
+    	    $this->search_sort_field, $this->search_threads);
       
     return $this->get_search_set();
     }
@@ -1760,7 +2181,7 @@ class rcube_imap
    * @return boolean True on success, False on error
    */
   function move_message($uids, $to_mbox, $from_mbox='')
-    {
+  {
     $fbox = $from_mbox;
     $tbox = $to_mbox;
     $to_mbox = $this->mod_mailbox($to_mbox);
@@ -1802,25 +2223,35 @@ class rcube_imap
     }
     // moving failed
     else if ($config->get('delete_always', false) && $tbox == $config->get('trash_mbox')) {
-      return $this->delete_message($a_uids, $fbox);
+      $moved = $this->delete_message($a_uids, $fbox);
     }
 
-    // remove message ids from search set
-    if ($moved && $this->search_set && $from_mbox == $this->mailbox) {
-      foreach ($a_uids as $uid)
-        $a_mids[] = $this->_uid2id($uid, $from_mbox);
-      $this->search_set = array_diff($this->search_set, $a_mids);
-    }
+    if ($moved) {
+      // unset threads internal cache
+      unset($this->icache['threads']);
+
+      // remove message ids from search set
+      if ($this->search_set && $from_mbox == $this->mailbox) {
+        // threads are too complicated to just remove messages from set
+        if ($this->search_threads)
+          $this->refresh_search();
+        else {
+          foreach ($a_uids as $uid)
+            $a_mids[] = $this->_uid2id($uid, $from_mbox);
+          $this->search_set = array_diff($this->search_set, $a_mids);
+          }
+        }
 
-    // update cached message headers
-    $cache_key = $from_mbox.'.msg';
-    if ($moved && $start_index = $this->get_message_cache_index_min($cache_key, $a_uids)) {
-      // clear cache from the lowest index on
-      $this->clear_message_cache($cache_key, $start_index);
-      }
+      // update cached message headers
+      $cache_key = $from_mbox.'.msg';
+      if ($start_index = $this->get_message_cache_index_min($cache_key, $a_uids)) {
+        // clear cache from the lowest index on
+        $this->clear_message_cache($cache_key, $start_index);
+       }
+    }
 
     return $moved;
-    }
+  }
 
 
   /**
@@ -1831,7 +2262,7 @@ class rcube_imap
    * @return boolean True on success, False on error
    */
   function delete_message($uids, $mbox_name='')
-    {
+  {
     $mailbox = $mbox_name ? $this->mod_mailbox($mbox_name) : $this->mailbox;
 
     // convert the list of uids to array
@@ -1843,31 +2274,38 @@ class rcube_imap
 
     $deleted = iil_C_Delete($this->conn, $mailbox, join(',', $a_uids));
 
-    // send expunge command in order to have the deleted message
-    // really deleted from the mailbox
-    if ($deleted)
-      {
+    if ($deleted) {
+      // send expunge command in order to have the deleted message
+      // really deleted from the mailbox
       $this->_expunge($mailbox, FALSE, $a_uids);
       $this->_clear_messagecount($mailbox);
       unset($this->uid_id_map[$mailbox]);
-      }
 
-    // remove message ids from search set
-    if ($deleted && $this->search_set && $mailbox == $this->mailbox) {
-      foreach ($a_uids as $uid)
-        $a_mids[] = $this->_uid2id($uid, $mailbox);
-      $this->search_set = array_diff($this->search_set, $a_mids);
-    }
+      // unset threads internal cache
+      unset($this->icache['threads']);
+      
+      // remove message ids from search set
+      if ($this->search_set && $mailbox == $this->mailbox) {
+        // threads are too complicated to just remove messages from set
+        if ($this->search_threads)
+          $this->refresh_search();
+        else {
+          foreach ($a_uids as $uid)
+            $a_mids[] = $this->_uid2id($uid, $mailbox);
+          $this->search_set = array_diff($this->search_set, $a_mids);
+          }
+        }
 
-    // remove deleted messages from cache
-    $cache_key = $mailbox.'.msg';
-    if ($deleted && $start_index = $this->get_message_cache_index_min($cache_key, $a_uids)) {
-      // clear cache from the lowest index on
-      $this->clear_message_cache($cache_key, $start_index);
+      // remove deleted messages from cache
+      $cache_key = $mailbox.'.msg';
+      if ($start_index = $this->get_message_cache_index_min($cache_key, $a_uids)) {
+        // clear cache from the lowest index on
+        $this->clear_message_cache($cache_key, $start_index);
       }
+    }
 
     return $deleted;
-    }
+  }
 
 
   /**
@@ -2422,13 +2860,11 @@ class rcube_imap
   private function get_message_cache($key, $from, $to, $sort_field, $sort_order)
     {
     $cache_key = "$key:$from:$to:$sort_field:$sort_order";
-    $db_header_fields = array('idx', 'uid', 'subject', 'from', 'to', 'cc', 'date', 'size');
     
     $config = rcmail::get_instance()->config;
 
-    // use idx sort for sorting by Date with index_sort=true or for unknown field
-    if (($sort_field == 'date' && $this->index_sort)
-      || !in_array($sort_field, $db_header_fields)) {
+    // use idx sort as default sorting
+    if (!$sort_field || !in_array($sort_field, $this->db_header_fields)) {
       $sort_field = 'idx';
       }
     
@@ -2465,9 +2901,9 @@ class rcube_imap
    */
   private function &get_cached_message($key, $uid)
     {
-    $internal_key = '__single_msg';
+    $internal_key = 'message';
     
-    if ($this->caching_enabled && !isset($this->cache[$internal_key][$uid]))
+    if ($this->caching_enabled && !isset($this->icache[$internal_key][$uid]))
       {
       $sql_result = $this->db->query(
         "SELECT idx, headers, structure
@@ -2482,13 +2918,13 @@ class rcube_imap
       if ($sql_arr = $this->db->fetch_assoc($sql_result))
         {
 	$this->uid_id_map[preg_replace('/\.msg$/', '', $key)][$uid] = $sql_arr['idx'];
-        $this->cache[$internal_key][$uid] = $this->db->decode(unserialize($sql_arr['headers']));
-        if (is_object($this->cache[$internal_key][$uid]) && !empty($sql_arr['structure']))
-          $this->cache[$internal_key][$uid]->structure = $this->db->decode(unserialize($sql_arr['structure']));
+        $this->icache[$internal_key][$uid] = $this->db->decode(unserialize($sql_arr['headers']));
+        if (is_object($this->icache[$internal_key][$uid]) && !empty($sql_arr['structure']))
+          $this->icache[$internal_key][$uid]->structure = $this->db->decode(unserialize($sql_arr['structure']));
         }
       }
 
-    return $this->cache[$internal_key][$uid];
+    return $this->icache[$internal_key][$uid];
     }
 
   /**
@@ -2505,8 +2941,8 @@ class rcube_imap
     if (!empty($sa_message_index[$key]) && !$force)
       return $sa_message_index[$key];
 
-    // use idx sort for sorting by Date with index_sort=true
-    if ($sort_field == 'date' && $this->index_sort)
+    // use idx sort as default
+    if (!$sort_field || !in_array($sort_field, $this->db_header_fields))
       $sort_field = 'idx';
     
     $sa_message_index[$key] = array();
@@ -2534,8 +2970,8 @@ class rcube_imap
         return;
 
     // add to internal (fast) cache
-    $this->cache['__single_msg'][$headers->uid] = clone $headers;
-    $this->cache['__single_msg'][$headers->uid]->structure = $struct;
+    $this->icache['message'][$headers->uid] = clone $headers;
+    $this->icache['message'][$headers->uid]->structure = $struct;
 
     // no further caching
     if (!$this->caching_enabled)
diff --git a/program/include/rcube_shared.inc b/program/include/rcube_shared.inc
index f4f23a26b..a130391f7 100644
--- a/program/include/rcube_shared.inc
+++ b/program/include/rcube_shared.inc
@@ -608,6 +608,26 @@ function rcube_explode_quoted_string($delimiter, $string)
 
 
 /**
+ * Get all keys from array (recursive)
+ * 
+ * @param array Input array
+ * @return array
+ */
+function array_keys_recursive($array)
+{
+  $keys = array();
+  
+  if (!empty($array))
+    foreach ($array as $key => $child) {
+      $keys[] = $key;
+      if ($children = array_keys_recursive($child))
+        $keys = array_merge($keys, $children);
+    }
+  return $keys;
+}
+
+
+/**
  * mbstring replacement functions
  */
 
diff --git a/program/include/rcube_user.php b/program/include/rcube_user.php
index 835ffe955..6ed16dbac 100644
--- a/program/include/rcube_user.php
+++ b/program/include/rcube_user.php
@@ -111,19 +111,22 @@ class rcube_user
       if (!isset($old_prefs[$key]) && ($value == $config->get($key)))
         unset($save_prefs[$key]);
     }
-    
+
+    $save_prefs = serialize($save_prefs);
+
     $this->db->query(
       "UPDATE ".get_table_name('users')."
        SET    preferences=?,
               language=?
        WHERE  user_id=?",
-      serialize($save_prefs),
+      $save_prefs,
       $_SESSION['language'],
       $this->ID);
 
     $this->language = $_SESSION['language'];
     if ($this->db->affected_rows()) {
       $config->set_user_prefs($a_user_prefs);
+      $this->data['preferences'] = $save_prefs;
       return true;
     }