1<?php
2/**
3 * Plugin nspages : Displays nicely a list of the pages of a namespace
4 *
5 * @license GPL 2 (http://www.gnu.org/licenses/gpl.html)
6 */
7
8if(!defined('DOKU_INC')) die();
9require_once 'printer.php';
10
11class nspages_printerTree extends nspages_printer {
12    private $rootNS;
13
14    function __construct($plugin, $mode, $renderer, $data){
15        parent::__construct($plugin, $mode, $renderer, $data);
16        $this->rootNS = $data['wantedNS'] . ':';
17    }
18
19    function _print($tab, $type) {
20        $tree = $this->_groupByNs($tab);
21        $trimmedTree = $this->_getTrimmedTree($tree);
22        $orderedTree = $this->_orderTree($trimmedTree);
23        $this->_printTree($orderedTree);
24    }
25
26    /**
27     * We received the nodes all ordered together, but building the tree has probably
28     * lost the order for namespaces, we hence need to sort again each node
29     */
30    function _orderTree($tree) {
31        // We only need to sort "children". We don't need to sort "pages" because with the current
32        // workflow of the plugin nodes are provided already sorted to _print, and the way we
33        // build the tree preserves the order of the pages.
34        // An optimization could be to disable the preliminary sort and to instead sort pages here.
35        // That could save some CPU cycles because instead of sorting a big list we would sort
36        // several smaller ones. However it would require
37        // - a regression test which assert on the order of the pages when a flag is passed to
38        //   have a custom sort (eg: "-h1") to ensure we don't have the correct order just because
39        //   the DW search API returned sorted results based on the id of the pages
40        // - benchmarking (because it could be detrimental if usort has a constant overhead which
41        //   would make several small sort more costly than a single one bigger)
42        $this->_sorter->sort($tree->children);
43
44        foreach($tree->children as $subTree){
45            if (is_object($subTree)) {
46                $this->_orderTree($subTree);
47            }
48        }
49        return $tree;
50    }
51
52    private function _groupByNs($tab) {
53        $tree = new NspagesTreeNsNode(':');
54        foreach($tab as $item){
55            $this->_fillTree($tree, $this->_getNS($item), $item, '', ':');
56        }
57        return $tree;
58    }
59
60    /**
61     * Get rid of the "trunk" of the tree. ie: remove the first "empty" nodes. It prevents printing
62     * something like
63     * - A
64     *  - B
65     *    - C
66     *      - page1
67     *      - page2
68     *      - page3
69     * when the ns the user asked for is actully ns C
70     */
71    private function _getTrimmedTree($tree){
72        if ($tree->id === $this->rootNS){
73            return $tree;
74        } else {
75            if (is_null($tree->children)) {
76                // This case should never happen. But I handle it neverthelss because if I'm wrong
77                // then the recursion will never end
78                return $tree;
79            }
80            $firstAndOnlyChild = reset($tree->children);
81            return $this->_getTrimmedTree($firstAndOnlyChild);
82        }
83    }
84
85    private function _getNS($item) {
86        if($item['type'] === 'd'){
87            // If $item is itself a namespace then:
88            // - its 'id' will look like either:
89            //   1. 'a:b:c:' if the ns has no main page
90            //   2. 'a:b:c:start' or 'a:b:c:c' (if this page exists)
91            //   3. 'a:b:c' (case where there is a page a:b:c and no page a:b:c:start, see bug #120)
92            // - its 'ns' will look like 'a:b'
93            // What we want is array ['a', 'b', 'c']
94
95            // For a page at the root of the repo:
96            // - the 'id' will look like either
97            //   4. 'a:start' in most cases
98            //   5. 'a' (case where the is a page 'a' and no page 'a:start', see bug #120)
99            // - the 'ns' will be FALSE
100
101            $lastChar = substr($item['id'], -1);
102            $IdSplit = explode(':', $item['id']);
103
104            if ($item['ns'] !== false){
105                if ($lastChar === ':' // case 1
106                  || count(explode(':', $item['ns'])) === count($IdSplit) -2){ // case 2
107                    array_pop($IdSplit);
108                } else { // case 3 (nothing to do here)
109                }
110            } else {
111                if ($this->str_contains($item['id'], ':')){ // case 4
112                    array_pop($IdSplit);
113                } else { // case 5 (nothing to do here)
114                }
115            }
116
117            return $IdSplit;
118        } else {
119            // It $item is a page then:
120            // - its 'id' will look like 'a:b:page'
121            // - its 'ns' will look like 'a:b'
122            // What we want is array ['a', 'b']
123            if ($item['ns'] === false) {
124              // Special case of the pages at the root of the wiki: for them "ns" is set to boolean FALSE
125              return array();
126            } else {
127              return explode(':', $item['ns']);
128            }
129        }
130    }
131
132    /**
133     * This is similar to https://www.php.net/manual/en/function.str-contains.php, but the PHP str_contains
134     * method is available only from PHP 8 so for now we re-implement this feature
135     */
136    private function str_contains(string $haystack, string $needle){
137        return strpos($haystack, $needle) !== false;
138    }
139
140    private function _fillTree($tree, $keys, $item, $parentId, $myNs) {
141        if (empty($keys)){ // We've reach the end of the journey. We register the data of $item
142            if($item['type'] === 'd') {
143                $tree->self = $item;
144            } else {
145                if ($myNs == $item['id']) {
146                    $tree->self = $item;
147                } else {
148                    if (!isset($tree->children[$item['id']])) {
149                        if ('d' !== $item['type']) {
150                            $tree->children[$item['id']] = new NspagesTreeNsNode($item['id']);
151                            $tree->children[$item['id']]->self = $item;
152                        } else {
153                            $tree->children[$item['id']] = $item;
154                        }
155                    } else {
156                        $tree->children[$item['id']]->self = $item;
157                    }
158                }
159            }
160        } else { // We're not at the place of $item in the tree yet, we continue to go down
161            $key = $keys[0];
162            $currentId = $parentId . $key . ':';
163            $nsKey = $parentId . $key;
164            if (!array_key_exists($nsKey, $tree->children)){
165                $node = new NspagesTreeNsNode($currentId);
166                $tree->children[$nsKey] = $node;
167            }
168            array_shift($keys);
169            $this->_fillTree($tree->children[$nsKey], $keys, $item, $currentId, $item['ns']);
170        }
171    }
172
173    private function _printTree($tree) {
174        $this->renderer->listu_open();
175
176        foreach($tree->children as $subTree){
177            if (is_object($subTree)) {
178                $this->_printSubTree($subTree, 1);
179            } else {
180                $this->_printElement($subTree, 1);
181            }
182        }
183
184         $this->renderer->listu_close();
185    }
186
187    private function _printSubTree($tree, $level) {
188        $this->_printElementOpen($tree->self, $level);
189        if ( !is_null($tree->self) ){
190            $this->_printElementContent($tree->self, $level);
191        } else {
192          $this->renderer->doc .= '<div>' . $tree->id  . '</div>';
193        }
194
195        $hasInnerData = !empty($tree->children);
196        if($hasInnerData){
197            $this->renderer->listu_open();
198        }
199        foreach($tree->children as $subTree){
200            if (is_object($subTree)) {
201                $this->_printSubTree($subTree, $level+1);
202            } else {
203                $this->_printElement($subTree, $level+1);
204            }
205        }
206
207        if($hasInnerData){
208            $this->renderer->listu_close();
209        }
210        $this->_printElementClose();
211    }
212}
213
214/**
215 * Represent a namespace and its inner content
216 */
217class NspagesTreeNsNode implements ArrayAccess {
218
219    /**
220     * The list of pages and subnamespaces at level n+1 (does not include their own subnamespaces)
221     */
222    public $children = array();
223
224    /**
225     * The data about the current namespace iteslf. It may be empty in two cases:
226     * - when nspages is displaying only pages (because in that case we did not search for ns)
227     * - when this instance represents the root of the tree (because nspages doesn't display it)
228     */
229    public $self = null;
230
231    /**
232     * Used to represent the current namespace when we're in a case where we want to display it
233     * but when $self is empty.
234     * In practice it is used to represent namespace nodes when we're asked to display pages only
235     */
236    public $id = null;
237
238    function __construct($id){
239        $this->id = $id;
240    }
241
242    /**
243     * Implement ArrayAccess because instances of this class should be sortable with nspages_sorter
244     * implementations and that those implementation are performing sorts based on $item["sort"].
245     */
246    public function offsetSet($offset, $value) {
247        throw new BadMethodCallException("Not implemented by design");
248    }
249    public function offsetExists($offset) {
250        return $offset == "sort";
251    }
252    public function offsetUnset($offset) {
253        throw new BadMethodCallException("Not implemented by design");
254    }
255    public function offsetGet($offset) {
256      return is_null($this->self) ?
257            $this->id :
258            $this->self["sort"];
259    }
260}
261