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

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