Applied message threading patch from Chris January: http://www.atomice.com/blog/?p=33

2 files changed, 451 insertions, 56 deletions

diff --git a/roundcubemail/program/include/rcmail.php b/roundcubemail/program/include/rcmail.php
index f109c16fd..96937b58a 100644
--- a/roundcubemail/program/include/rcmail.php
+++ b/roundcubemail/program/include/rcmail.php
@@ -349,6 +349,10 @@ class rcmail
     if ($this->config->get('enable_caching')) {
       $this->imap->set_caching(true);
     }
+    
+    if ($this->config->get('enable_thread_caching')) {
+      $this->imap->set_thread_caching(true);
+    }
 
     // set pagesize from config
     $this->imap->set_pagesize($this->config->get('pagesize', 50));
diff --git a/roundcubemail/program/include/rcube_imap.php b/roundcubemail/program/include/rcube_imap.php
index 637e25b92..788b0ff58 100644
--- a/roundcubemail/program/include/rcube_imap.php
+++ b/roundcubemail/program/include/rcube_imap.php
@@ -52,6 +52,7 @@ class rcube_imap
   var $sort_order = 'DESC';
   var $delimiter = NULL;
   var $caching_enabled = FALSE;
+  var $thread_caching_enabled = FALSE;
   var $default_charset = 'ISO-8859-1';
   var $default_folders = array('INBOX');
   var $default_folders_lc = array('inbox');
@@ -68,6 +69,7 @@ class rcube_imap
   var $debug_level = 1;
   var $error_code = 0;
   var $options = array('imap' => 'check');
+  var $threading = false;
 
 
   /**
@@ -472,7 +474,7 @@ class rcube_imap
       $mailbox = $this->mailbox;
       
     // count search set
-    if ($this->search_string && $mailbox == $this->mailbox && $mode == 'ALL' && !$force)
+    if ($this->search_string && $mailbox == $this->mailbox && ($mode == 'ALL' || $mode == 'THREADS') && !$force)
       return count((array)$this->search_set);
 
     $a_mailbox_cache = $this->get_cache('messagecount');
@@ -481,8 +483,12 @@ class rcube_imap
     if (!$force && is_array($a_mailbox_cache[$mailbox]) && isset($a_mailbox_cache[$mailbox][$mode]))
       return $a_mailbox_cache[$mailbox][$mode];
 
+    if ($this->get_capability('thread=references') &&
+        $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
@@ -524,6 +530,25 @@ class rcube_imap
     return (int)$count;
     }
 
+    function _threadcount($mailbox)
+    {
+        if (isset ($this->cache['__threads']['tree']))
+            return count($this->cache['__threads']['tree']);
+        if ($this->check_thread_cache_status($mailbox) > 0) {
+            $sql_result = $this->db->query("SELECT COUNT(*)
+                                            FROM " .
+                                           get_table_name('threads') . "
+                                            WHERE  user_id=? AND mailbox=?",
+                                           $_SESSION['user_id'],
+                                           $mailbox);
+
+            if ($sql_arr = $this->db->fetch_array($sql_result))
+                return $sql_arr[0];
+        }
+        list ($thread_tree, $msg_depth, $has_children) = iil_C_Thread($this->conn, $mailbox, 'REFERENCES', 'ALL');
+        $this->update_thread_cache($mailbox, $thread_tree, $msg_depth, $has_children);
+        return count($thread_tree);
+    }
 
   /**
    * Public method for listing headers
@@ -560,8 +585,9 @@ class rcube_imap
 
     $this->_set_sort_order($sort_field, $sort_order);
 
-    $max = $this->_messagecount($mailbox);
-    $start_msg = ($this->list_page-1) * $this->page_size;
+    $message_threading = $this->get_capability('thread=references') &&
+                         rcmail::get_instance()->imap->threading;
+    $max = $this->_messagecount($mailbox, $message_threading ? 'THREADS' : 'ALL');
 
     list($begin, $end) = $this->_get_message_range($max, $page);
 
@@ -573,65 +599,139 @@ class rcube_imap
     $cache_key = $mailbox.'.msg';
     $cache_status = $this->check_cache_status($mailbox, $cache_key);
 
-    // cache is OK, we can get all messages from local cache
-    if ($cache_status>0)
-      {
-      $a_msg_headers = $this->get_message_cache($cache_key, $start_msg, $start_msg+$this->page_size, $this->sort_field, $this->sort_order);
-      $headers_sorted = TRUE;
-      }
-    // cache is dirty, sync it
-    else if ($this->caching_enabled && $cache_status==-1 && !$recursive)
+    if ($cache_status <= 0 && $this->caching_enabled && $cache_status == -1 && !$recursive)
       {
       $this->sync_header_index($mailbox);
       return $this->_list_headers($mailbox, $page, $this->sort_field, $this->sort_order, TRUE);
       }
-    else
-      {
-      // retrieve headers from IMAP
-      if ($this->get_capability('sort') && ($msg_index = iil_C_Sort($this->conn, $mailbox, $this->sort_field, $this->skip_deleted ? 'UNDELETED' : '')))
-        {
-        $mymsgidx = array_slice ($msg_index, $begin, $end-$begin);
-        $msgs = join(",", $mymsgidx);
-        }
-      else
-        {
-        $msgs = sprintf("%d:%d", $begin+1, $end);
-        $msg_index = range($begin, $end);
-        }
 
+    if ($message_threading) {
+        $thread_cache_status = $this->check_thread_cache_status($mailbox);
+        if ($thread_cache_status > 0 && $cache_status > 0) {
+            // use a JOIN of the threads and messages tables to get a sorted list of roots
+            $roots = $this->get_thread_cache_roots_sorted($mailbox, $begin, $end, $this->sort_field, $this->sort_order);
+        } else {
+            if ($thread_cache_status > 0) {
+                // get a list of thread roots from the cache
+                $roots = $this->get_thread_cache_roots($mailbox);
+            } else {
+                if (isset ($this->cache['__threads']['tree'])) {
+                    $thread_tree = $this->cache['__threads']['tree'];
+                    $msg_depth = $this->cache['__threads']['depth'];
+                    $has_children = $this->cache['__threads']['has_children'];
+                } else {
+                    list ($thread_tree, $msg_depth, $has_children) = iil_C_Thread($this->conn, $mailbox, 'REFERENCES', 'ALL');
+                }
+                $this->update_thread_cache($mailbox, $thread_tree, $msg_depth, $has_children);
+                // the keys of thread_tree are the thread roots
+                $roots = array_keys($thread_tree);
+            }
+
+            if ($this->get_capability('sort') && ($sort_index = iil_C_Sort($this->conn, $mailbox, $this->sort_field, $this->skip_deleted ? 'UNDELETED' : ''))) {
+                if ($this->sort_order == 'DESC')
+                    $sort_index = array_reverse($sort_index);
+            } else {
+                if ($this->sort_order == 'DESC')
+                    $msg_index = range($max, 1);
+                else
+                    $msg_index = range(1, $max);
+            }
 
-      // fetch reuested headers from server
-      $a_msg_headers = array();
-      $deleted_count = $this->_fetch_headers($mailbox, $msgs, $a_msg_headers, $cache_key);
+            // sort the roots according to the order defined by $sort_index
+            $sorter = new rcube_thread_root_sorter();
+            $sorter->set_sequence_numbers($sort_index);
+            $sorter->sort_threads($roots);
+            
+            // get the roots for this page
+            $roots = array_slice($roots, $begin, $end - $begin);
+        }
 
-      // delete cached messages with a higher index than $max+1
-      // Changed $max to $max+1 to fix this bug : #1484295
-      $this->clear_message_cache($cache_key, $max + 1);
+        if ($thread_cache_status > 0) {
+        	// get the children of $roots from the cache
+            $threads = $this->get_thread_cache_threads($mailbox, $roots);
+            $msg_index = array ();
+            $msg_depth = array ();
+            $has_children = array ();
+            foreach ($threads as $thread) {
+                foreach ($thread as $msg) {
+                    $idx = $msg['idx'];
+                    $msg_index[] = $idx;
+                    $msg_depth[$idx] = $msg['depth'];
+                    $has_children[$idx] = $msg['has_children'];
+                }
+            }
+        } else {
+            // flatten the thread tree
+            $msg_index = array ();
+            foreach ($roots as $root) {
+                $msg_index[] = $root;
+                $msg_index = array_merge($msg_index, array_keys_recursive($thread_tree[$root]));
+            }
+        }
+    } else { // no threading
+        if ($this->get_capability('sort') && ($msg_index = iil_C_Sort($this->conn, $mailbox, $this->sort_field, $this->skip_deleted ? 'UNDELETED' : ''))) {
+            if ($this->sort_order == 'DESC')
+                 $msg_index = array_reverse($msg_index);
+            $msg_index = array_slice($msg_index, $begin, $end - $begin);
+        } else {
+            if ($this->sort_order == 'DESC')
+                $msg_index = range($end, $begin + 1);
+            else
+                $msg_index = range($begin + 1, $end);
+        }
+    }
 
-      // kick child process to sync cache
-      // ...
-      }
+    // fetch requested headers from server
+    $msgs = join(",", $msg_index);
+    // cache is OK, we can get all messages from local cache
+    if ($cache_status > 0) {
+        // if $message_threading is true then no point sorting them as they will need re-sorting later
+        $a_msg_headers = $this->get_message_cache($cache_key, $message_threading?null:$this->sort_field, $this->sort_order, $msgs);
+        // if $message_threading is true then $a_msg_headers will need re-sorting as the tree structure won't have been preserved'
+        $headers_sorted = !$message_threading;
+    } else {
+        $a_msg_headers = array();
+        $deleted_count = $this->_fetch_headers($mailbox, $msgs, $a_msg_headers, $cache_key);
+        // delete cached messages with a higher index than $max+1
+        // Changed $max to $max+1 to fix this bug : #1484295
+        $this->clear_message_cache($cache_key, $max + 1);
+    }
+
+    // kick child process to sync cache
+    // ...
 
     // return empty array if no messages found
     if (!is_array($a_msg_headers) || empty($a_msg_headers)) {
       return array();
     }
 
-    // if not already sorted
     if (!$headers_sorted)
       {
       // use this class for message sorting
       $sorter = new rcube_header_sorter();
       $sorter->set_sequence_numbers($msg_index);
       $sorter->sort_headers($a_msg_headers);
-
-      if ($this->sort_order == 'DESC')
-        $a_msg_headers = array_reverse($a_msg_headers);
       }
 
-    return array_values($a_msg_headers);
+    if ($message_threading) {
+       // Set depth, has_children and unread_children fields in headers 
+       $parents = array();
+       foreach ($a_msg_headers as $uid => $headers) {
+            $id = $headers->id;
+            $depth = $msg_depth[$id];
+            $parents = array_slice($parents, 0, $depth - 1);
+            if (!$headers->seen) {
+                foreach ($parents as $parent)
+                    $a_msg_headers[$parent]->unread_children++;
+            }
+            array_push($parents, $uid);
+            $a_msg_headers[$uid]->depth = $depth;
+            $a_msg_headers[$uid]->has_children = $has_children[$id];
+        }
     }
 
+    return array_values($a_msg_headers);
+    }
 
   /**
    * Private method for listing a set of message headers (search results)
@@ -738,11 +838,6 @@ class rcube_imap
       $begin = 0;
       $end = $max;
       }
-    else if ($this->sort_order=='DESC')
-      {
-      $begin = $max - $this->page_size - $start_msg;
-      $end =   $max - $start_msg;
-      }
     else
       {
       $begin = $start_msg;
@@ -756,8 +851,6 @@ class rcube_imap
     return array($begin, $end);
     }
     
-    
-
   /**
    * Fetches message headers
    * Used for loop
@@ -2046,6 +2139,17 @@ class rcube_imap
   /**
    * @access private
    */
+  function set_thread_caching($set)
+    {
+    if ($set && is_object($this->db))
+      $this->thread_caching_enabled = TRUE;
+    else
+      $this->thread_caching_enabled = FALSE;
+    }
+
+  /**
+   * @access private
+   */
   function get_cache($key)
     {
     // read cache
@@ -2226,6 +2330,9 @@ class rcube_imap
 
     if ($cache_count==$msg_count)
       {
+      if ($msg_count == 0)
+        return 1;
+
       // get highest index
       $header = iil_C_FetchHeader($this->conn, $mailbox, "$msg_count");
       $cache_uid = array_pop($cache_index);
@@ -2247,26 +2354,29 @@ class rcube_imap
   /**
    * @access private
    */
-  function get_message_cache($key, $from, $to, $sort_field, $sort_order)
+  function get_message_cache($key, $sort_field, $sort_order, $msgs)
     {
-    $cache_key = "$key:$from:$to:$sort_field:$sort_order";
+    $cache_key = "$key:$sort_field:$sort_order:$msgs";
     $db_header_fields = array('idx', 'uid', 'subject', 'from', 'to', 'cc', 'date', 'size');
     
-    if (!in_array($sort_field, $db_header_fields))
-      $sort_field = 'idx';
-    
     if ($this->caching_enabled && !isset($this->cache[$cache_key]))
       {
       $this->cache[$cache_key] = array();
-      $sql_result = $this->db->limitquery(
+      if (is_null($sort_field)) {
+          $sort = '';
+      } else {
+      	 if (!in_array($sort_field, $db_header_fields))
+              $sort_field = 'idx';
+          $sort = "ORDER BY ".$this->db->quoteIdentifier($sort_field)." ".
+                  strtoupper($sort_order);
+      }
+      $sql_result = $this->db->query(
         "SELECT idx, uid, headers
          FROM ".get_table_name('messages')."
          WHERE  user_id=?
          AND    cache_key=?
-         ORDER BY ".$this->db->quoteIdentifier($sort_field)." ".
-         strtoupper($sort_order),
-        $from,
-        $to-$from,
+         AND    idx IN ($msgs)
+         $sort",
         $_SESSION['user_id'],
         $key);
 
@@ -2444,8 +2554,175 @@ class rcube_imap
       $start_index);
     }
 
+    /* --------------------------------
+     *   thread caching methods
+     * --------------------------------*/
 
+    /**
+     * Checks if the thread cache is up-to-date
+     *
+     * @param string Mailbox name
+     * @return int 0 = ok, -1 = invalid, -2 = cache disabled
+     */
+    function check_thread_cache_status($mailbox)
+    {
+        if (!$this->caching_enabled)
+            return -2;
+
+        $cache_uid = $this->get_cache('thread_cache_last_uid');
+        $cache_count = $this->get_cache('thread_cache_msg_count');
+        $msg_count = $this->_messagecount($mailbox, 'ALL', TRUE);
+
+        if ($cache_count[$mailbox] == $msg_count) {
+            if ($msg_count == 0)
+                return 1;
+
+            // get highest index
+            $header = iil_C_FetchHeader($this->conn, $mailbox, "$msg_count");
+
+            // uids of highest message matches -> cache seems OK
+            if ($cache_uid[$mailbox] == $header->uid)
+                return 1;
 
+            // cache is invaid
+            return -1;
+        } else {
+            return -1;
+        }
+    }
+
+    function update_thread_cache($mailbox, $thread_tree, $msg_depth, $has_children)
+    {
+        if (empty ($mailbox))
+            return;
+
+        // add to internal (fast) cache
+        $this->cache['__threads'] = array();
+        $this->cache['__threads']['tree'] = $thread_tree;
+        $this->cache['__threads']['depth'] = $msg_depth;
+        $this->cache['__threads']['has_children'] = $has_children;
+
+        // no further caching
+        if (!$this->thread_caching_enabled || true)
+            return;
+
+        $this->db->query("DELETE FROM " .
+                         get_table_name('threads') ."
+                          WHERE user_id = ?
+                          AND mailbox = ?", $_SESSION['user_id'], $mailbox);
+        foreach ($thread_tree as $root => $subtree) {
+            $this->db->query("INSERT INTO " .
+                             get_table_name('threads') . "
+                              (user_id, mailbox, idx, has_children, is_root, root, depth)
+                              VALUES (?, ?, ?, ?, ?, ?, ?)", $_SESSION['user_id'], $mailbox, $root, $has_children[$root] ? 1 : 0, 1, $root, $msg_depth[$root]);
+            $children = array_keys_recursive($subtree);
+            foreach ($children as $idx) {
+                $this->db->query("INSERT INTO " .
+                                 get_table_name('threads') . "
+                                  (user_id, mailbox, idx, has_children, is_root, root, depth)
+                                  VALUES (?, ?, ?, ?, ?, ?, ?)", $_SESSION['user_id'], $mailbox, $idx, $has_children[$idx] ? 1 : 0, 0, $root, $msg_depth[$idx]);
+            }
+        }
+
+        $cache_uid = $this->get_cache('thread_cache_last_uid');
+        $cache_count = $this->get_cache('thread_cache_msg_count');
+        $msg_count = $this->_messagecount($mailbox);
+        if ($msg_count > 0) {
+            $header = iil_C_FetchHeader($this->conn, $mailbox, "$msg_count");
+            $cache_uid[$mailbox] = $header->uid;
+        }
+        $cache_count[$mailbox] = $msg_count;
+        $this->update_cache('thread_cache_last_uid', $cache_uid);
+        $this->update_cache('thread_cache_msg_count', $cache_count);
+    }
+
+    function get_thread_cache_roots($mailbox)
+    {
+        if (!$this->thread_caching_enabled || empty ($mailbox))
+            return array ();
+
+        $cache_key = "threads:$mailbox";
+
+        if ($this->thread_caching_enabled && !isset ($this->cache[$cache_key])) {
+            $this->cache[$cache_key] = array ();
+
+            $sql_result = $this->db->query("SELECT idx
+                                            FROM " .
+                                           get_table_name('threads') . "
+                                            WHERE  user_id=?
+                                            AND    mailbox=?
+                                            AND    is_root", $_SESSION['user_id'], $mailbox);
+
+            while ($sql_arr = $this->db->fetch_array($sql_result))
+                $this->cache[$cache_key][] = $sql_arr[0];
+        }
+
+        return $this->cache[$cache_key];
+    }
+
+    function get_thread_cache_roots_sorted($mailbox, $from, $to, $sort_field, $sort_order)
+    {
+        // empty key -> empty array
+        if (!$this->thread_caching_enabled || !$this->caching_enabled || empty ($mailbox))
+            return array ();
+
+        $cache_key = "threads:$mailbox:$from:$to:$sort_field:$sort_order";
+
+        if ($this->thread_caching_enabled && $this->caching_enabled && !isset ($this->cache[$cache_key])) {
+            $this->cache[$cache_key] = array ();
+
+            $sql_result = $this->db->limitquery("SELECT threads.idx
+                                                 FROM " .
+                                                get_table_name('threads') . "
+                                                 INNER JOIN ".
+                                                get_table_name('messages') . "
+                                                 ON threads.idx = messages.idx
+                                                 AND threads.user_id = messages.user_id
+                                                 WHERE  threads.user_id=?
+                                                 AND    mailbox=?
+                                                 AND    cache_key=?
+                                                 AND    is_root
+                                                 ORDER BY ".$this->db->quoteIdentifier($sort_field)." ".
+                                                 strtoupper($sort_order),
+                                                 $from,
+                                                 $to-$from,
+                                                 $_SESSION['user_id'], $mailbox, $mailbox.'.msg');
+
+            while ($sql_arr = $this->db->fetch_array($sql_result))
+                $this->cache[$cache_key][] = $sql_arr[0];
+        }
+
+        return $this->cache[$cache_key];
+    }
+
+    function get_thread_cache_threads($mailbox, $roots)
+    {
+        // empty key -> empty array
+        if (!$this->thread_caching_enabled || empty ($mailbox))
+            return array ();
+
+        $cache_key = "threads:$mailbox:" . join(',', $roots);
+
+        if ($this->thread_caching_enabled && !isset ($this->cache[$cache_key])) {
+            $this->cache[$cache_key] = array ();
+            // setup the key order according to $roots
+            foreach ($roots as $root)
+                $this->cache[$cache_key][$root] = array();
+
+            $sql_result = $this->db->query("SELECT idx, has_children, root, depth
+                                            FROM " .
+                                           get_table_name('threads') . "
+                                            WHERE  user_id=?
+                                            AND    mailbox=?
+                                            AND    root IN (" . join(',', $roots) .")
+                                            ORDER BY thread_id", $_SESSION['user_id'], $mailbox);
+
+            while ($sql_arr = $this->db->fetch_assoc($sql_result))
+                $this->cache[$cache_key][$sql_arr['root']][] = $sql_arr;
+        }
+
+        return $this->cache[$cache_key];
+    }
 
   /* --------------------------------
    *   encoding/decoding methods
@@ -2899,6 +3176,10 @@ class rcube_imap
     // add incremental value to messagecount
     $a_mailbox_cache[$mailbox][$mode] += $increment;
     
+    // If ALL changes then THREADS may be invalid
+    if ($mode == 'ALL')
+      unset ($a_mailbox_cache[$mailbox]['THREADS']);
+
     // there's something wrong, delete from cache
     if ($a_mailbox_cache[$mailbox][$mode] < 0)
       unset($a_mailbox_cache[$mailbox][$mode]);
@@ -3134,3 +3415,113 @@ function quoted_printable_encode($input, $line_max=76, $space_conv=false)
   }
 
 
+function array_keys_recursive($array)
+{
+    $keys = array ();
+    foreach ($array as $key => $child)
+    {
+        $keys[] = $key;
+        $keys = array_merge($keys, array_keys_recursive($child));
+    }
+    return $keys;
+}
+
+
+/**
+ * Class for sorting a thread tree in a predetermined order.
+ *
+ * @package Mail
+ * @author Chris January
+ */
+class rcube_thread_sorter
+{
+    var $sequence_numbers = array ();
+
+    /**
+     * Set the predetermined sort order.
+     *
+     * @param array Numerically indexed array of IMAP message sequence numbers
+     */
+    function set_sequence_numbers($seqnums)
+    {
+        $this->sequence_numbers = array_flip($seqnums);
+    }
+
+    /**
+     * Sort the array of header objects
+     *
+     * @param threads A thread tree
+     */
+    function sort_threads(& $threads)
+    {
+        uksort($threads, array (
+               $this,
+               "compare_seqnums"
+        ));
+        foreach (array_keys($threads) as $root)
+        {
+            $this->sort_threads($threads[$root]);
+        }
+    }
+
+    /**
+     * Sort method called by uasort()
+     */
+    function compare_seqnums($seqa, $seqb)
+    {
+        // find each sequence number in my ordered list
+        $posa = isset ($this->sequence_numbers[$seqa]) ? intval($this->sequence_numbers[$seqa]) : -1;
+        $posb = isset ($this->sequence_numbers[$seqb]) ? intval($this->sequence_numbers[$seqb]) : -1;
+
+        // return the relative position as the comparison value
+        return $posa - $posb;
+    }
+}
+
+
+/**
+ * Class for sorting thread roots in a predetermined order.
+ *
+ * @package Mail
+ * @author Chris January
+ */
+class rcube_thread_root_sorter
+{
+    var $sequence_numbers = array ();
+
+    /**
+     * Set the predetermined sort order.
+     *
+     * @param array Numerically indexed array of IMAP message sequence numbers
+     */
+    function set_sequence_numbers($seqnums)
+    {
+        $this->sequence_numbers = array_flip($seqnums);
+    }
+
+    /**
+     * Sort the array of header objects
+     *
+     * @param threads A thread tree
+     */
+    function sort_threads(& $threads)
+    {
+        usort($threads, array (
+              $this,
+              "compare_seqnums"
+        ));
+    }
+
+    /**
+     * Sort method called by uasort()
+     */
+    function compare_seqnums($seqa, $seqb)
+    {
+        // find each sequence number in my ordered list
+        $posa = isset ($this->sequence_numbers[$seqa]) ? intval($this->sequence_numbers[$seqa]) : -1;
+        $posb = isset ($this->sequence_numbers[$seqb]) ? intval($this->sequence_numbers[$seqb]) : -1;
+
+        // return the relative position as the comparison value
+        return $posa - $posb;
+    }
+}