source: subversion/trunk/roundcubemail/program/include/rcube_result_thread.php @ 5561

Last change on this file since 5561 was 5561, checked in by alec, 18 months ago
  • Cleanup + perf. improvement (substr_count() is really fast!)
File size: 19.1 KB
Line 
1<?php
2
3/*
4 +-----------------------------------------------------------------------+
5 | program/include/rcube_result_thread.php                               |
6 |                                                                       |
7 | This file is part of the Roundcube Webmail client                     |
8 | Copyright (C) 2005-2011, The Roundcube Dev Team                       |
9 | Copyright (C) 2011, Kolab Systems AG                                  |
10 | Licensed under the GNU GPL                                            |
11 |                                                                       |
12 | PURPOSE:                                                              |
13 |   THREAD response handler                                             |
14 |                                                                       |
15 +-----------------------------------------------------------------------+
16 | Author: Thomas Bruederli <roundcube@gmail.com>                        |
17 | Author: Aleksander Machniak <alec@alec.pl>                            |
18 +-----------------------------------------------------------------------+
19
20 $Id: rcube_imap.php 5347 2011-10-19 06:35:29Z alec $
21
22*/
23
24
25/**
26 * Class for accessing IMAP's THREAD result
27 */
28class rcube_result_thread
29{
30    private $raw_data;
31    private $mailbox;
32    private $meta = array();
33    private $order = 'ASC';
34
35    const SEPARATOR_ELEMENT = ' ';
36    const SEPARATOR_ITEM    = '~';
37    const SEPARATOR_LEVEL   = ':';
38
39
40    /**
41     * Object constructor.
42     */
43    public function __construct($mailbox = null, $data = null)
44    {
45        $this->mailbox = $mailbox;
46        $this->init($data);
47    }
48
49
50    /**
51     * Initializes object with IMAP command response
52     *
53     * @param string $data IMAP response string
54     */
55    public function init($data = null)
56    {
57        $this->meta = array();
58
59        $data = explode('*', (string)$data);
60
61        // ...skip unilateral untagged server responses
62        for ($i=0, $len=count($data); $i<$len; $i++) {
63            if (preg_match('/^ THREAD/i', $data[$i])) {
64                $data[$i] = substr($data[$i], 7);
65                break;
66            }
67
68            unset($data[$i]);
69        }
70
71        if (empty($data)) {
72            return;
73        }
74
75        $data = array_shift($data);
76        $data = trim($data);
77        $data = preg_replace('/[\r\n]/', '', $data);
78        $data = preg_replace('/\s+/', ' ', $data);
79
80        $this->raw_data = $this->parseThread($data);
81    }
82
83
84    /**
85     * Checks the result from IMAP command
86     *
87     * @return bool True if the result is an error, False otherwise
88     */
89    public function isError()
90    {
91        return $this->raw_data === null ? true : false;
92    }
93
94
95    /**
96     * Checks if the result is empty
97     *
98     * @return bool True if the result is empty, False otherwise
99     */
100    public function isEmpty()
101    {
102        return empty($this->raw_data) ? true : false;
103    }
104
105
106    /**
107     * Returns number of elements (threads) in the result
108     *
109     * @return int Number of elements
110     */
111    public function count()
112    {
113        if ($this->meta['count'] !== null)
114            return $this->meta['count'];
115
116        if (empty($this->raw_data)) {
117            $this->meta['count'] = 0;
118        }
119        else {
120            $this->meta['count'] = 1 + substr_count($this->raw_data, self::SEPARATOR_ELEMENT);
121        }
122
123        if (!$this->meta['count'])
124            $this->meta['messages'] = 0;
125
126        return $this->meta['count'];
127    }
128
129
130    /**
131     * Returns number of all messages in the result
132     *
133     * @return int Number of elements
134     */
135    public function countMessages()
136    {
137        if ($this->meta['messages'] !== null)
138            return $this->meta['messages'];
139
140        if (empty($this->raw_data)) {
141            $this->meta['messages'] = 0;
142        }
143        else {
144            $this->meta['messages'] = 1
145                + substr_count($this->raw_data, self::SEPARATOR_ELEMENT)
146                + substr_count($this->raw_data, self::SEPARATOR_ITEM);
147        }
148
149        if ($this->meta['messages'] == 0 || $this->meta['messages'] == 1)
150            $this->meta['count'] = $this->meta['messages'];
151
152        return $this->meta['messages'];
153    }
154
155
156    /**
157     * Returns maximum message identifier in the result
158     *
159     * @return int Maximum message identifier
160     */
161    public function max()
162    {
163        if (!isset($this->meta['max'])) {
164            $this->meta['max'] = (int) @max($this->get());
165        }
166        return $this->meta['max'];
167    }
168
169
170    /**
171     * Returns minimum message identifier in the result
172     *
173     * @return int Minimum message identifier
174     */
175    public function min()
176    {
177        if (!isset($this->meta['min'])) {
178            $this->meta['min'] = (int) @min($this->get());
179        }
180        return $this->meta['min'];
181    }
182
183
184    /**
185     * Slices data set.
186     *
187     * @param $offset Offset (as for PHP's array_slice())
188     * @param $length Number of elements (as for PHP's array_slice())
189     */
190    public function slice($offset, $length)
191    {
192        $data = explode(self::SEPARATOR_ELEMENT, $this->raw_data);
193        $data = array_slice($data, $offset, $length);
194
195        $this->meta          = array();
196        $this->meta['count'] = count($data);
197        $this->raw_data      = implode(self::SEPARATOR_ELEMENT, $data);
198    }
199
200
201    /**
202     * Filters data set. Removes threads not listed in $roots list.
203     *
204     * @param array $roots List of IDs of thread roots.
205     */
206    public function filter($roots)
207    {
208        $datalen = strlen($this->raw_data);
209        $roots   = array_flip($roots);
210        $result  = '';
211        $start   = 0;
212
213        $this->meta          = array();
214        $this->meta['count'] = 0;
215
216        while (($pos = @strpos($this->raw_data, self::SEPARATOR_ELEMENT, $start))
217            || ($start < $datalen && ($pos = $datalen))
218        ) {
219            $len   = $pos - $start;
220            $elem  = substr($this->raw_data, $start, $len);
221            $start = $pos + 1;
222
223            // extract root message ID
224            if ($npos = strpos($elem, self::SEPARATOR_ITEM)) {
225                $root = (int) substr($elem, 0, $npos);
226            }
227            else {
228                $root = $elem;
229            }
230
231            if (isset($roots[$root])) {
232                $this->meta['count']++;
233                $result .= self::SEPARATOR_ELEMENT . $elem;
234            }
235        }
236
237        $this->raw_data = ltrim($result, self::SEPARATOR_ELEMENT);
238    }
239
240
241    /**
242     * Reverts order of elements in the result
243     */
244    public function revert()
245    {
246        $this->order = $this->order == 'ASC' ? 'DESC' : 'ASC';
247
248        if (empty($this->raw_data)) {
249            return;
250        }
251
252        $this->meta['pos'] = array();
253        $datalen = strlen($this->raw_data);
254        $result  = '';
255        $start   = 0;
256
257        while (($pos = @strpos($this->raw_data, self::SEPARATOR_ELEMENT, $start))
258            || ($start < $datalen && ($pos = $datalen))
259        ) {
260            $len   = $pos - $start;
261            $elem  = substr($this->raw_data, $start, $len);
262            $start = $pos + 1;
263
264            $result = $elem . self::SEPARATOR_ELEMENT . $result;
265        }
266
267        $this->raw_data = rtrim($result, self::SEPARATOR_ELEMENT);
268    }
269
270
271    /**
272     * Check if the given message ID exists in the object
273     *
274     * @param int $msgid Message ID
275     * @param bool $get_index When enabled element's index will be returned.
276     *                        Elements are indexed starting with 0
277     *
278     * @return boolean True on success, False if message ID doesn't exist
279     */
280    public function exists($msgid, $get_index = false)
281    {
282        $msgid = (int) $msgid;
283        $begin = implode('|', array(
284            '^',
285            preg_quote(self::SEPARATOR_ELEMENT, '/'),
286            preg_quote(self::SEPARATOR_LEVEL, '/'),
287        ));
288        $end = implode('|', array(
289            '$',
290            preg_quote(self::SEPARATOR_ELEMENT, '/'),
291            preg_quote(self::SEPARATOR_ITEM, '/'),
292        ));
293
294        if (preg_match("/($begin)$msgid($end)/", $this->raw_data, $m,
295            $get_index ? PREG_OFFSET_CAPTURE : null)
296        ) {
297            if ($get_index) {
298                $idx = 0;
299                if ($m[0][1]) {
300                    $idx = substr_count($this->raw_data, self::SEPARATOR_ELEMENT, 0, $m[0][1]+1)
301                        + substr_count($this->raw_data, self::SEPARATOR_ITEM, 0, $m[0][1]+1);
302                }
303                // cache position of this element, so we can use it in getElement()
304                $this->meta['pos'][$idx] = (int)$m[0][1];
305
306                return $idx;
307            }
308            return true;
309        }
310
311        return false;
312    }
313
314
315    /**
316     * Return IDs of all messages in the result. Threaded data will be flattened.
317     *
318     * @return array List of message identifiers
319     */
320    public function get()
321    {
322        if (empty($this->raw_data)) {
323            return array();
324        }
325
326        $regexp = '/(' . preg_quote(self::SEPARATOR_ELEMENT, '/')
327            . '|' . preg_quote(self::SEPARATOR_ITEM, '/') . '[0-9]+' . preg_quote(self::SEPARATOR_LEVEL, '/')
328            .')/';
329
330        return preg_split($regexp, $this->raw_data);
331    }
332
333
334    /**
335     * Return all messages in the result.
336     *
337     * @return array List of message identifiers
338     */
339    public function getCompressed()
340    {
341        if (empty($this->raw_data)) {
342            return '';
343        }
344
345        return rcube_imap_generic::compressMessageSet($this->get());
346    }
347
348
349    /**
350     * Return result element at specified index (all messages, not roots)
351     *
352     * @param int|string  $index  Element's index or "FIRST" or "LAST"
353     *
354     * @return int Element value
355     */
356    public function getElement($index)
357    {
358        $count = $this->count();
359
360        if (!$count) {
361            return null;
362        }
363
364        // first element
365        if ($index === 0 || $index === '0' || $index === 'FIRST') {
366            preg_match('/^([0-9]+)/', $this->raw_data, $m);
367            $result = (int) $m[1];
368            return $result;
369        }
370
371        // last element
372        if ($index === 'LAST' || $index == $count-1) {
373            preg_match('/([0-9]+)$/', $this->raw_data, $m);
374            $result = (int) $m[1];
375            return $result;
376        }
377
378        // do we know the position of the element or the neighbour of it?
379        if (!empty($this->meta['pos'])) {
380            $element = preg_quote(self::SEPARATOR_ELEMENT, '/');
381            $item    = preg_quote(self::SEPARATOR_ITEM, '/') . '[0-9]+' . preg_quote(self::SEPARATOR_LEVEL, '/') .'?';
382            $regexp  = '(' . $element . '|' . $item . ')';
383
384            if (isset($this->meta['pos'][$index])) {
385                if (preg_match('/([0-9]+)/', $this->raw_data, $m, null, $this->meta['pos'][$index]))
386                    $result = $m[1];
387            }
388            else if (isset($this->meta['pos'][$index-1])) {
389                // get chunk of data after previous element
390                $data = substr($this->raw_data, $this->meta['pos'][$index-1]+1, 50);
391                $data = preg_replace('/^[0-9]+/', '', $data); // remove UID at $index position
392                $data = preg_replace("/^$regexp/", '', $data); // remove separator
393                if (preg_match('/^([0-9]+)/', $data, $m))
394                    $result = $m[1];
395            }
396            else if (isset($this->meta['pos'][$index+1])) {
397                // get chunk of data before next element
398                $pos  = max(0, $this->meta['pos'][$index+1] - 50);
399                $len  = min(50, $this->meta['pos'][$index+1]);
400                $data = substr($this->raw_data, $pos, $len);
401                $data = preg_replace("/$regexp\$/", '', $data); // remove separator
402
403                if (preg_match('/([0-9]+)$/', $data, $m))
404                    $result = $m[1];
405            }
406
407            if (isset($result)) {
408                return (int) $result;
409            }
410        }
411
412        // Finally use less effective method
413        $data = $this->get();
414
415        return $data[$index];
416    }
417
418
419    /**
420     * Returns response parameters e.g. MAILBOX, ORDER
421     *
422     * @param string $param  Parameter name
423     *
424     * @return array|string Response parameters or parameter value
425     */
426    public function getParameters($param=null)
427    {
428        $params = $this->params;
429        $params['MAILBOX'] = $this->mailbox;
430        $params['ORDER']   = $this->order;
431
432        if ($param !== null) {
433            return $params[$param];
434        }
435
436        return $params;
437    }
438
439
440    /**
441     * THREAD=REFS sorting implementation (based on provided index)
442     *
443     * @param rcube_result_index $index  Sorted message identifiers
444     */
445    public function sort($index)
446    {
447        $this->sort_order = $index->getParameters('ORDER');
448
449        if (empty($this->raw_data)) {
450            return;
451        }
452
453        // when sorting search result it's good to make the index smaller
454        if ($index->count() != $this->countMessages()) {
455            $index->intersect($this->get());
456        }
457
458        $result  = array_fill_keys($index->get(), null);
459        $datalen = strlen($this->raw_data);
460        $start   = 0;
461
462        // Here we're parsing raw_data twice, we want only one big array
463        // in memory at a time
464
465        // Assign roots
466        while (($pos = @strpos($this->raw_data, self::SEPARATOR_ELEMENT, $start))
467            || ($start < $datalen && ($pos = $datalen))
468        ) {
469            $len   = $pos - $start;
470            $elem  = substr($this->raw_data, $start, $len);
471            $start = $pos + 1;
472
473            $items = explode(self::SEPARATOR_ITEM, $elem);
474            $root  = (int) array_shift($items);
475
476            $result[$elem] = $elem;
477            foreach ($items as $item) {
478                list($lv, $id) = explode(self::SEPARATOR_LEVEL, $item);
479                    $result[$id] = $root;
480            }
481        }
482
483        // get only unique roots
484        $result = array_filter($result); // make sure there are no nulls
485        $result = array_unique($result, SORT_NUMERIC);
486
487        // Re-sort raw data
488        $result = array_fill_keys($result, null);
489        $start = 0;
490
491        while (($pos = @strpos($this->raw_data, self::SEPARATOR_ELEMENT, $start))
492            || ($start < $datalen && ($pos = $datalen))
493        ) {
494            $len   = $pos - $start;
495            $elem  = substr($this->raw_data, $start, $len);
496            $start = $pos + 1;
497
498            $npos = strpos($elem, self::SEPARATOR_ITEM);
499            $root = (int) ($npos ? substr($elem, 0, $npos) : $elem);
500
501            $result[$root] = $elem;
502        }
503
504        $this->raw_data = implode(self::SEPARATOR_ELEMENT, $result);
505    }
506
507
508    /**
509     * Returns data as tree
510     *
511     * @return array Data tree
512     */
513    public function getTree()
514    {
515        $datalen = strlen($this->raw_data);
516        $result  = array();
517        $start   = 0;
518
519        while (($pos = @strpos($this->raw_data, self::SEPARATOR_ELEMENT, $start))
520            || ($start < $datalen && ($pos = $datalen))
521        ) {
522            $len   = $pos - $start;
523            $elem  = substr($this->raw_data, $start, $len);
524            $items = explode(self::SEPARATOR_ITEM, $elem);
525            $result[array_shift($items)] = $this->buildThread($items);
526            $start = $pos + 1;
527        }
528
529        return $result;
530    }
531
532
533    /**
534     * Returns thread depth and children data
535     *
536     * @return array Thread data
537     */
538    public function getThreadData()
539    {
540        $data     = $this->getTree();
541        $depth    = array();
542        $children = array();
543
544        $this->buildThreadData($data, $depth, $children);
545
546        return array($depth, $children);
547    }
548
549
550    /**
551     * Creates 'depth' and 'children' arrays from stored thread 'tree' data.
552     */
553    private function buildThreadData($data, &$depth, &$children, $level = 0)
554    {
555        foreach ((array)$data as $key => $val) {
556            $children[$key] = !empty($val);
557            $depth[$key] = $level;
558            if (!empty($val))
559                $this->buildThreadData($val, $depth, $children, $level + 1);
560        }
561    }
562
563
564    /**
565     * Converts part of the raw thread into an array
566     */
567    private function buildThread($items, $level = 1, &$pos = 0)
568    {
569        $result = array();
570
571        for ($len=count($items); $pos < $len; $pos++) {
572            list($lv, $id) = explode(self::SEPARATOR_LEVEL, $items[$pos]);
573            if ($level == $lv) {
574                $pos++;
575                $result[$id] = $this->buildThread($items, $level+1, $pos);
576            }
577            else {
578                $pos--;
579                break;
580            }
581        }
582
583        return $result;
584    }
585
586
587    /**
588     * IMAP THREAD response parser
589     */
590    private function parseThread($str, $begin = 0, $end = 0, $depth = 0)
591    {
592        // Don't be tempted to change $str to pass by reference to speed this up - it will slow it down by about
593        // 7 times instead :-) See comments on http://uk2.php.net/references and this article:
594        // http://derickrethans.nl/files/phparch-php-variables-article.pdf
595        $node = '';
596        if (!$end) {
597            $end = strlen($str);
598        }
599
600        // Let's try to store data in max. compacted stracture as a string,
601        // arrays handling is much more expensive
602        // For the following structure: THREAD (2)(3 6 (4 23)(44 7 96))
603        // -- 2
604        //
605        // -- 3
606        //     \-- 6
607        //         |-- 4
608        //         |    \-- 23
609        //         |
610        //         \-- 44
611        //              \-- 7
612        //                   \-- 96
613        //
614        // The output will be: 2,3^1:6^2:4^3:23^2:44^3:7^4:96
615
616        if ($str[$begin] != '(') {
617            $stop = $begin + strspn($str, '1234567890', $begin, $end - $begin);
618            $msg  = substr($str, $begin, $stop - $begin);
619            if (!$msg) {
620                return $node;
621            }
622
623            $this->meta['messages']++;
624
625            $node .= ($depth ? self::SEPARATOR_ITEM.$depth.self::SEPARATOR_LEVEL : '').$msg;
626
627            if ($stop + 1 < $end) {
628                $node .= $this->parseThread($str, $stop + 1, $end, $depth + 1);
629            }
630        } else {
631            $off = $begin;
632            while ($off < $end) {
633                $start = $off;
634                $off++;
635                $n = 1;
636                while ($n > 0) {
637                    $p = strpos($str, ')', $off);
638                    if ($p === false) {
639                        // error, wrong structure, mismatched brackets in IMAP THREAD response
640                        // @TODO: write error to the log or maybe set $this->raw_data = null;
641                        return $node;
642                    }
643                    $p1 = strpos($str, '(', $off);
644                    if ($p1 !== false && $p1 < $p) {
645                        $off = $p1 + 1;
646                        $n++;
647                    } else {
648                        $off = $p + 1;
649                        $n--;
650                    }
651                }
652
653                $thread = $this->parseThread($str, $start + 1, $off - 1, $depth);
654                if ($thread) {
655                    if (!$depth) {
656                        if ($node) {
657                            $node .= self::SEPARATOR_ELEMENT;
658                        }
659                    }
660                    $node .= $thread;
661                }
662            }
663        }
664
665        return $node;
666    }
667}
Note: See TracBrowser for help on using the repository browser.