Add experimental tree builder classes

These classes provide mechanisms to build a traversable tree of pages
and links. Either from the existing namespace structure, or from a
control page containing (possibly a nested) set of links.

The nodes returned by the tree are deliberately sparse. No ACL checking
is taking place. Developers can enrich (or omit) nodes and influence
recursion decisions via callbacks.

The tree can optionally be sorted by comparators provided in the
TreeSort class or a custom callback.

The API provided by these classes is not considered stable yet and may
change over time. Plugin authors are encouraged to use them and provide
feedback.

14 files changed, 1435 insertions, 0 deletions

diff --git a/_test/tests/TreeBuilder/ControlPageBuilderTest.php b/_test/tests/TreeBuilder/ControlPageBuilderTest.php
new file mode 100644
index 000000000..b6bb4eb61
--- /dev/null
+++ b/_test/tests/TreeBuilder/ControlPageBuilderTest.php
@@ -0,0 +1,132 @@
+<?php
+
+namespace dokuwiki\test\Treebuilder;
+
+use dokuwiki\TreeBuilder\ControlPageBuilder;
+use DokuWikiTest;
+
+class ControlPageBuilderTest extends DokuWikiTest
+{
+    public static function setUpBeforeClass(): void
+    {
+        parent::setUpBeforeClass();
+        saveWikiText('simple', file_get_contents(__DIR__ . '/cp/simple.txt'), 'test');
+        saveWikiText('foo:complex', file_get_contents(__DIR__ . '/cp/complex.txt'), 'test');
+    }
+
+    public function testSimpleParsing()
+    {
+        $control = new ControlPageBuilder('simple');
+        $control->generate();
+        
+        $expected = [
+            '+briefs:start',
+            '+qhsr:start',
+            '++qhsr:q',
+            '++qhsr:cert',
+            '++qhsr:hse:start',
+            '++qhsr:engsystems',
+            '++qhsr:performance',
+            '++qhsr:competence',
+            '++qhsr:ashford',
+            '++qhsr:training',
+            '+tech:start',
+            '+https://homepage.company.com'
+        ];
+        
+        $result = explode("\n", (string)$control);
+        sort($expected);
+        sort($result);
+        
+        $this->assertEquals($expected, $result);
+        
+        // Additional structure tests
+        $top = $control->getTop();
+        $this->assertEquals(4, count($top->getChildren()));
+        $this->assertEquals(1, count($top->getChildren()[0]->getParents()));
+        $this->assertEquals(4, count($top->getChildren()[1]->getSiblings()));
+        $this->assertEquals(8, count($top->getChildren()[1]->getChildren()));
+
+        $this->assertEquals(12, count($control->getAll()));
+        $this->assertEquals(11, count($control->getLeaves()));
+        $this->assertEquals(1, count($control->getBranches()));
+    }
+
+    /**
+     * Parse the complex example with different flags
+     *
+     * @return array[]
+     * @see testComplexParsing
+     */
+    public function complexProvider()
+    {
+        return [
+            'No flags' => [
+                'flags' => 0,
+                'expected' => [
+                    '+content',
+                    '+foo:this',
+                    '+foo:bar',
+                    '+foo:another_link',
+                    '+https://www.google.com',
+                    '+relativeup',
+                    '+foo2:this',
+                    '++foo2:deeper:item',
+                    '+++foo2:deeper:evendeeper:item',
+                    '+foo:blarg:down',
+                    '+toplevel',
+                    '+foo:link',
+                ]
+            ],
+            'FLAG_NOEXTERNAL' => [
+                'flags' => ControlPageBuilder::FLAG_NOEXTERNAL,
+                'expected' => [
+                    '+content',
+                    '+foo:this',
+                    '+foo:bar',
+                    '+foo:another_link',
+                    '+relativeup',
+                    '+foo2:this',
+                    '++foo2:deeper:item',
+                    '+++foo2:deeper:evendeeper:item',
+                    '+foo:blarg:down',
+                    '+toplevel',
+                    '+foo:link',
+                ]
+            ],
+            'FLAG_NOINTERNAL' => [
+                'flags' => ControlPageBuilder::FLAG_NOINTERNAL,
+                'expected' => [
+                    '+https://www.google.com',
+                ]
+            ],
+        ];
+    }
+
+    /**
+     * @dataProvider complexProvider
+     * @param int $flags
+     * @param array $expected
+     * @return void
+     */
+    public function testComplexParsing(int $flags, array $expected)
+    {
+        $control = new ControlPageBuilder('foo:complex');
+        $control->addFlag($flags);
+        $control->generate();
+        
+        $result = explode("\n", (string)$control);
+        sort($expected);
+        sort($result);
+        
+        $this->assertEquals($expected, $result);
+    }
+
+    public function testNonExisting()
+    {
+        $this->expectException(\RuntimeException::class);
+        $control = new ControlPageBuilder('does:not:exist');
+        $control->generate();
+        $foo = $control->getAll();
+    }
+}
diff --git a/_test/tests/TreeBuilder/PageTreeBuilderTest.php b/_test/tests/TreeBuilder/PageTreeBuilderTest.php
new file mode 100644
index 000000000..e1c6ad9ae
--- /dev/null
+++ b/_test/tests/TreeBuilder/PageTreeBuilderTest.php
@@ -0,0 +1,200 @@
+<?php
+
+namespace dokuwiki\test\Treebuilder;
+
+use dokuwiki\TreeBuilder\PageTreeBuilder;
+use DokuWikiTest;
+
+class PageTreeBuilderTest extends DokuWikiTest
+{
+    protected $originalDataDir;
+
+    public static function setUpBeforeClass(): void
+    {
+        parent::setUpBeforeClass();
+
+        // Create a test page hierarchy
+        saveWikiText('namespace:start', 'This is the start page', 'test');
+        saveWikiText('namespace:page1', 'This is page 1', 'test');
+        saveWikiText('namespace:page2', 'This is page 2', 'test');
+        saveWikiText('namespace:subns:start', 'This is the subns start page', 'test');
+        saveWikiText('namespace:subns:page3', 'This is page 3 in subns', 'test');
+        saveWikiText('namespace:subns:deeper:start', 'This is the deeper start page', 'test');
+        saveWikiText('namespace:subns:deeper:page4', 'This is page 4 in deeper', 'test');
+    }
+
+    public function setUp(): void
+    {
+        parent::setUp();
+        global $conf;
+        $this->originalDataDir = $conf['datadir'];
+    }
+
+    public function tearDown(): void
+    {
+        global $conf;
+        $conf['datadir'] = $this->originalDataDir;
+        parent::tearDown();
+    }
+
+    public function treeConfigProvider()
+    {
+        return [
+            'Default configuration' => [
+                'namespace' => 'namespace',
+                'depth' => -1,
+                'flags' => 0,
+                'expected' => [
+                    '+namespace:start',
+                    '+namespace:page1',
+                    '+namespace:page2',
+                    '+namespace:subns',
+                    '++namespace:subns:start',
+                    '++namespace:subns:page3',
+                    '++namespace:subns:deeper',
+                    '+++namespace:subns:deeper:start',
+                    '+++namespace:subns:deeper:page4'
+                ]
+            ],
+            'Depth limit 1' => [
+                'namespace' => 'namespace',
+                'depth' => 1,
+                'flags' => 0,
+                'expected' => [
+                    '+namespace:start',
+                    '+namespace:page1',
+                    '+namespace:page2',
+                    '+namespace:subns',
+                    '++namespace:subns:start',
+                    '++namespace:subns:page3',
+                    '++namespace:subns:deeper'
+                ]
+            ],
+            'Depth limit 1 with NS_AS_STARTPAGE' => [
+                'namespace' => 'namespace',
+                'depth' => 1,
+                'flags' => PageTreeBuilder::FLAG_NS_AS_STARTPAGE,
+                'expected' => [
+                    '+namespace:page1',
+                    '+namespace:page2',
+                    '+namespace:subns:start',
+                    '++namespace:subns:page3',
+                    '++namespace:subns:deeper:start'
+                ]
+            ],
+            'FLAG_NO_NS' => [
+                'namespace' => 'namespace',
+                'depth' => -1,
+                'flags' => PageTreeBuilder::FLAG_NO_NS,
+                'expected' => [
+                    '+namespace:start',
+                    '+namespace:page1',
+                    '+namespace:page2'
+                ]
+            ],
+            'FLAG_NO_PAGES' => [
+                'namespace' => 'namespace',
+                'depth' => -1,
+                'flags' => PageTreeBuilder::FLAG_NO_PAGES,
+                'expected' => [
+                    '+namespace:subns',
+                    '++namespace:subns:deeper'
+                ]
+            ],
+            'FLAG_NS_AS_STARTPAGE' => [
+                'namespace' => 'namespace',
+                'depth' => -1,
+                'flags' => PageTreeBuilder::FLAG_NS_AS_STARTPAGE,
+                'expected' => [
+                    '+namespace:page1',
+                    '+namespace:page2',
+                    '+namespace:subns:start',
+                    '++namespace:subns:page3',
+                    '++namespace:subns:deeper:start',
+                    '+++namespace:subns:deeper:page4'
+                ]
+            ],
+            'Combined FLAG_NO_NS and FLAG_NS_AS_STARTPAGE' => [
+                'namespace' => 'namespace',
+                'depth' => -1,
+                'flags' => PageTreeBuilder::FLAG_NO_NS | PageTreeBuilder::FLAG_NS_AS_STARTPAGE,
+                'expected' => [
+                    '+namespace:page1',
+                    '+namespace:page2'
+                ]
+            ],
+            'FLAG_SELF_TOP' => [
+                'namespace' => 'namespace',
+                'depth' => -1,
+                'flags' => PageTreeBuilder::FLAG_SELF_TOP,
+                'expected' => [
+                    '+namespace',
+                    '++namespace:start',
+                    '++namespace:page1',
+                    '++namespace:page2',
+                    '++namespace:subns',
+                    '+++namespace:subns:start',
+                    '+++namespace:subns:page3',
+                    '+++namespace:subns:deeper',
+                    '++++namespace:subns:deeper:start',
+                    '++++namespace:subns:deeper:page4'
+                ]
+            ],
+        ];
+    }
+
+
+    /**
+     * @dataProvider treeConfigProvider
+     */
+    public function testPageTreeConfigurations(string $namespace, int $depth, int $flags, array $expected)
+    {
+        $tree = new PageTreeBuilder($namespace, $depth);
+        if ($flags) {
+            $tree->addFlag($flags);
+        }
+        $tree->generate();
+
+        $result = explode("\n", (string)$tree);
+        sort($expected);
+        sort($result);
+
+        $this->assertEquals($expected, $result);
+    }
+
+    /**
+     * This is the same test as above, but pretending that our data directory is in our test namespace.
+     *
+     * @dataProvider treeConfigProvider
+     */
+    public function testTopLevelTree(string $namespace, int $depth, int $flags, array $expected)
+    {
+        global $conf;
+        $conf['datadir'] .= '/namespace';
+
+        $expected = array_map(function ($item) use ($namespace) {
+            return preg_replace('/namespace:?/', '', $item);
+        }, $expected);
+
+        $namespace = '';
+        $this->testPageTreeConfigurations($namespace, $depth, $flags, $expected);
+    }
+
+
+    public function testPageTreeLeaves()
+    {
+        $tree = new PageTreeBuilder('namespace');
+        $tree->generate();
+
+        $leaves = $tree->getLeaves();
+        $branches = $tree->getBranches();
+
+        // Test that we have both leaves and branches
+        $this->assertGreaterThan(0, count($leaves), 'Should have leaf pages');
+        $this->assertGreaterThan(0, count($branches), 'Should have branch pages');
+
+        // The total should equal all pages
+        $this->assertEquals(count($tree->getAll()), count($leaves) + count($branches),
+            'Leaves + branches should equal total pages');
+    }
+}
diff --git a/_test/tests/TreeBuilder/cp/complex.txt b/_test/tests/TreeBuilder/cp/complex.txt
new file mode 100644
index 000000000..4290fddc9
--- /dev/null
+++ b/_test/tests/TreeBuilder/cp/complex.txt
@@ -0,0 +1,21 @@
+====== this is the Control ======
+
+It has all kinds of [[:content]]. But also Links.
+
+  * This is not a link
+    * [[this]] is
+    * [[foo:bar]] is also a link
+  * [[Another Link]]
+  * [[https://www.google.com|External links]] are not lessons
+
+We have two lists here
+
+  * [[foo:bar|duplicates]] will be ignored in the order
+  * [[..:relativeup]]
+  * [[foo2:this]]
+    * [[foo2:deeper:item|Deeper Item]]
+      * [[foo2:deeper:evendeeper:item|Even Deeper Item]]
+  * [[.:blarg:down]]
+  * [[:toplevel]]
+
+Here is more and another [[link]].
diff --git a/_test/tests/TreeBuilder/cp/simple.txt b/_test/tests/TreeBuilder/cp/simple.txt
new file mode 100644
index 000000000..718f03c8d
--- /dev/null
+++ b/_test/tests/TreeBuilder/cp/simple.txt
@@ -0,0 +1,12 @@
+  * [[briefs:start|Briefs]]
+  * [[qhsr:start|QHSR]]
+    * [[qhsr:q|Quality]]
+    * [[qhsr:cert|Certification]]
+    * [[qhsr:hse:start|HSE]]
+    * [[qhsr:engsystems|Eng Systems]]
+    * [[qhsr:performance|Eng Performance]]
+    * [[qhsr:competence|Eng Competence]]
+    * [[qhsr:ashford|Ashford DFO]]
+    * [[qhsr:training|Technical Training]]
+  * [[tech:start|Tech Info]]
+  * [[https://homepage.company.com|Company Homepage]]
diff --git a/inc/TreeBuilder/AbstractBuilder.php b/inc/TreeBuilder/AbstractBuilder.php
new file mode 100644
index 000000000..76758430d
--- /dev/null
+++ b/inc/TreeBuilder/AbstractBuilder.php
@@ -0,0 +1,266 @@
+<?php
+
+namespace dokuwiki\TreeBuilder;
+
+
+use dokuwiki\test\mock\Doku_Renderer;
+use dokuwiki\TreeBuilder\Node\AbstractNode;
+use dokuwiki\TreeBuilder\Node\ExternalLink;
+use dokuwiki\TreeBuilder\Node\Top;
+
+/**
+ * Abstract class to generate a tree
+ */
+abstract class AbstractBuilder
+{
+    protected bool $generated = false;
+
+    /** @var AbstractNode[] flat list of all nodes the generator found */
+    protected array $nodes = [];
+
+    /** @var Top top level element to access the tree */
+    protected Top $top;
+
+    /** @var callable|null A callback to modify or filter out nodes */
+    protected $nodeProcessor;
+
+    /** @var callable|null A callback to decide if recursion should happen */
+    protected $recursionDecision;
+
+    /**
+     * @var int configuration flags
+     */
+    protected int $flags = 0;
+
+    /**
+     * Generate the page tree. Needs to be called once the object is created.
+     *
+     * Sets the $generated flag to true.
+     *
+     * @return void
+     */
+    abstract public function generate(): void;
+
+    /**
+     * Set a callback to set additional properties on the nodes
+     *
+     * The callback receives a Node as parameter and must return a Node.
+     * If the callback returns null, the node will not be added to the tree.
+     * The callback may use the setProperty() method to set additional properties on the node.
+     * The callback can also return a completely different node, which will be added to the tree instead
+     * of the original node.
+     *
+     * @param callable|null $builder A callback to set additional properties on the nodes
+     */
+    public function setNodeProcessor(?callable $builder): void
+    {
+        if ($builder !== null && !is_callable($builder)) {
+            throw new \InvalidArgumentException('Property builder must be callable');
+        }
+        $this->nodeProcessor = $builder;
+    }
+
+    /**
+     * Set a callback to decide if recursion should happen
+     *
+     * The callback receives a Node as parameter and the current recursion depth.
+     * The node will NOT have it's children set.
+     * The callback must return true to have any children added, false to skip them.
+     *
+     * @param callable|null $filter
+     * @return void
+     */
+    public function setRecursionDecision(?callable $filter): void
+    {
+        if ($filter !== null && !is_callable($filter)) {
+            throw new \InvalidArgumentException('Recursion-filter must be callable');
+        }
+        $this->recursionDecision = $filter;
+    }
+
+    /**
+     * Add a configuration flag
+     *
+     * @param int $flag
+     * @return void
+     */
+    public function addFlag(int $flag): void
+    {
+        $this->flags |= $flag;
+    }
+
+    /**
+     * Check if a flag is set
+     *
+     * @param int $flag
+     * @return bool
+     */
+    public function hasFlag(int $flag): bool
+    {
+        return ($this->flags & $flag) === $flag;
+    }
+
+    /**
+     * Check if a flag is NOT set
+     *
+     * @param int $flag
+     * @return bool
+     */
+    public function hasNotFlag(int $flag): bool
+    {
+        return ($this->flags & $flag) !== $flag;
+    }
+
+    /**
+     * Remove a configuration flag
+     *
+     * @param int $flag
+     * @return void
+     */
+    public function removeFlag(int $flag): void
+    {
+        $this->flags &= ~$flag;
+    }
+
+    /**
+     * Access the top element
+     *
+     * Use it's children to iterate over the page hierarchy
+     *
+     * @return Top
+     */
+    public function getTop(): Top
+    {
+        if (!$this->generated) throw new \RuntimeException('need to call generate() first');
+        return $this->top;
+    }
+
+    /**
+     * Get a flat list of all nodes in the tree
+     *
+     * This is a cached version of top->getDescendants() with the ID as key of the returned array.
+     *
+     * @return AbstractNode[]
+     */
+    public function getAll(): array
+    {
+        if (!$this->generated) throw new \RuntimeException('need to call generate() first');
+        if (empty($this->nodes)) {
+            $this->nodes = [];
+            foreach ($this->top->getDescendants() as $node) {
+                $this->nodes[$node->getId()] = $node;
+            }
+        }
+
+        return $this->nodes;
+    }
+
+    /**
+     * Get a flat list of all nodes that do NOT have children
+     *
+     * @return AbstractNode[]
+     */
+    public function getLeaves(): array
+    {
+        if (!$this->generated) throw new \RuntimeException('need to call generate() first');
+        return array_filter($this->getAll(), function ($page) {
+            return !$page->getChildren();
+        });
+    }
+
+    /**
+     * Get a flat list of all nodes that DO have children
+     *
+     * @return AbstractNode[]
+     */
+    public function getBranches(): array
+    {
+        if (!$this->generated) throw new \RuntimeException('need to call generate() first');
+        return array_filter($this->getAll(), function ($page) {
+            return !!$page->getChildren();
+        });
+    }
+
+    /**
+     * Sort the tree
+     *
+     * The given comparator function will be called with two nodes as arguments and needs to
+     * return an integer less than, equal to, or greater than zero if the first argument is considered
+     * to be respectively less than, equal to, or greater than the second.
+     *
+     * Pass in one of the TreeSort comparators or your own.
+     *
+     * @param callable $comparator
+     * @return void
+     */
+    public function sort(callable $comparator): void
+    {
+        if (!$this->generated) throw new \RuntimeException('need to call generate() first');
+        $this->top->sort($comparator);
+        $this->nodes = []; // reset the cache
+    }
+
+    /**
+     * Render the tree on the given renderer
+     *
+     * This is mostly an example implementation. You probably want to implement your own.
+     *
+     * @param Doku_Renderer $R The current renderer
+     * @param AbstractNode $top The node to start from, use null to start from the top node
+     * @param int $level current nesting level, starting at 1
+     * @return void
+     */
+    public function render(Doku_Renderer $R, $top = null, $level = 1): void
+    {
+        if ($top === null) $top = $this->getTop();
+
+        $R->listu_open();
+        foreach ($top->getChildren() as $node) {
+            $R->listitem_open(1, $node->hasChildren());
+            $R->listcontent_open();
+            if (is_a($node, ExternalLink::class)) {
+                $R->externallink($node->getId(), $node->getTitle());
+            } else {
+                $R->internallink($node->getId(), $node->getTitle());
+            }
+            $R->listcontent_close();
+            if ($node->hasChildren()) {
+                $this->render($R, $node, $level + 1);
+            }
+            $R->listitem_close();
+        }
+        $R->listu_close();
+    }
+
+    /**
+     * @param AbstractNode $node
+     * @return AbstractNode|null
+     */
+    protected function applyNodeProcessor(AbstractNode $node): ?AbstractNode
+    {
+        if ($this->nodeProcessor === null) return $node;
+        $result = call_user_func($this->nodeProcessor, $node);
+        if (!$result instanceof AbstractNode) return null;
+        return $result;
+    }
+
+    /**
+     * @param AbstractNode $node
+     * @return bool should children be added?
+     */
+    protected function applyRecursionDecision(AbstractNode $node, int $depth): bool
+    {
+        if ($this->recursionDecision === null) return true;
+        return (bool)call_user_func($this->recursionDecision, $node, $depth);
+    }
+
+    /**
+     * "prints" the tree
+     *
+     * @return array
+     */
+    public function __toString(): string
+    {
+        return join("\n", $this->getAll());
+    }
+}
diff --git a/inc/TreeBuilder/ControlPageBuilder.php b/inc/TreeBuilder/ControlPageBuilder.php
new file mode 100644
index 000000000..225989868
--- /dev/null
+++ b/inc/TreeBuilder/ControlPageBuilder.php
@@ -0,0 +1,114 @@
+<?php
+
+namespace dokuwiki\TreeBuilder;
+
+use dokuwiki\File\PageResolver;
+use dokuwiki\TreeBuilder\Node\AbstractNode;
+use dokuwiki\TreeBuilder\Node\ExternalLink;
+use dokuwiki\TreeBuilder\Node\Top;
+use dokuwiki\TreeBuilder\Node\WikiPage;
+
+/**
+ * A tree builder that generates a tree from a control page
+ *
+ * A control page is a wiki page containing a nested list of external and internal links. This builder
+ * parses the control page and generates a tree of nodes representing the links.
+ */
+class ControlPageBuilder extends AbstractBuilder
+{
+    /** @var int do not include internal links */
+    const FLAG_NOINTERNAL = 1;
+    /** @var int do not include external links */
+    const FLAG_NOEXTERNAL = 2;
+
+    /** @var string */
+    protected string $controlPage;
+    /** @var int */
+    protected int $flags = 0;
+
+    /**
+     * Parse the control page
+     *
+     * Check the flag constants on how to influence the behaviour
+     *
+     * @param string $controlPage
+     * @param int $flags
+     */
+    public function __construct(string $controlPage)
+    {
+        $this->controlPage = $controlPage;
+    }
+
+    /**
+     * @inheritdoc
+     * @todo theoretically it should be possible to also take the recursionDecision into account, even though
+     *       we don't recurse here. Passing the depth would be easy, but actually aborting going deeper is difficult.
+     */
+    public function generate(): void
+    {
+        $this->top = new Top();
+        $instructions = p_cached_instructions(wikiFN($this->controlPage));
+        if (!$instructions) {
+            throw new \RuntimeException('No instructions for control page found');
+        }
+
+        $parents = [
+            0 => $this->top
+        ];
+        $level = 0;
+
+        $resolver = new PageResolver($this->controlPage);
+
+        foreach ($instructions as $instruction) {
+            switch ($instruction[0]) {
+                case 'listu_open':
+                    $level++; // new list level
+                    break;
+                case 'listu_close':
+                    // if we had a node on this level, remove it from the parents
+                    if(isset($parents[$level])) {
+                        unset($parents[$level]);
+                    }
+                    $level--; // close list level
+                    break;
+                case 'internallink':
+                case 'externallink':
+                    if ($instruction[0] == 'internallink') {
+                        if ($this->flags & self::FLAG_NOINTERNAL) break;
+
+                        $newpage = new WikiPage(
+                            $resolver->resolveId($instruction[1][0]),
+                            $instruction[1][1]
+                        );
+                    } else {
+                        if ($this->flags & self::FLAG_NOEXTERNAL) break;
+
+                        $newpage = new ExternalLink(
+                            $instruction[1][0],
+                            $instruction[1][1]
+                        );
+                    }
+
+                    if($level) {
+                        // remember this page as the parent for this level
+                        $parents[$level] = $newpage;
+                        // parent is the last page on the previous level
+                        // levels may not be evenly distributed, so we need to check the count
+                        $parent = $parents[count($parents) - 2];
+                    } else {
+                        // not in a list, so parent is always the top
+                        $parent = $this->top;
+                    }
+
+                    $newpage->setParent($parent);
+                    $newpage = $this->applyNodeProcessor($newpage);
+                    if($newpage instanceof AbstractNode) {
+                        $parent->addChild($newpage);
+                    }
+                    break;
+            }
+        }
+
+        $this->generated = true;
+    }
+}
diff --git a/inc/TreeBuilder/Node/AbstractNode.php b/inc/TreeBuilder/Node/AbstractNode.php
new file mode 100644
index 000000000..0897ec71c
--- /dev/null
+++ b/inc/TreeBuilder/Node/AbstractNode.php
@@ -0,0 +1,216 @@
+<?php
+
+namespace dokuwiki\TreeBuilder\Node;
+
+/**
+ * A node represents one entry in the tree. It can have a parent and children.
+ */
+abstract class AbstractNode
+{
+    /** @var AbstractNode|null parent node */
+    protected ?AbstractNode $parent = null;
+    /** @var string unique ID for this node, usually the page id or external URL */
+    protected string $id = '';
+    /** @var string|null title of the node, may be null */
+    protected ?string $title = null;
+
+    /** @var AbstractNode[] */
+    protected array $parents = [];
+    /** @var AbstractNode[] */
+    protected array $children = [];
+    /** @var array */
+    protected array $properties = [];
+
+    /**
+     * @param string $id The pageID or the external URL
+     * @param string|null $title The title as given in the link
+     */
+    public function __construct(string $id, ?string $title)
+    {
+        $this->id = $id;
+        $this->title = $title;
+    }
+
+    /**
+     * @return string
+     */
+    public function getId(): string
+    {
+        return $this->id;
+    }
+
+    /**
+     * Get the namespace of this node
+     *
+     * @return string
+     */
+    public function getNs(): string
+    {
+        return getNS($this->id);
+    }
+
+    /**
+     * @return string|null
+     */
+    public function getTitle(): ?string
+    {
+        return $this->title;
+    }
+
+    /**
+     * @param string|null $title
+     */
+    public function setTitle(?string $title): void
+    {
+        $this->title = $title;
+    }
+
+    /**
+     * Get all nodes on the same level
+     * @return AbstractNode[]
+     */
+    public function getSiblings(): array
+    {
+        return $this->getParent()->getChildren();
+    }
+
+    /**
+     * Get all sub nodes, may return an empty array
+     *
+     * @return AbstractNode[]
+     */
+    public function getChildren(): array
+    {
+        return $this->children;
+    }
+
+    /**
+     * Does this node have children?
+     *
+     * @return bool
+     */
+    public function hasChildren(): bool
+    {
+        return !empty($this->children);
+    }
+
+    /**
+     * Get all sub nodes and their sub nodes and so on
+     *
+     * @return AbstractNode[]
+     */
+    public function getDescendants(): array
+    {
+        $descendants = [];
+        foreach ($this->children as $child) {
+            $descendants[] = $child;
+            $descendants = array_merge($descendants, $child->getDescendants());
+        }
+        return $descendants;
+    }
+
+    /**
+     * Get all parent nodes in reverse order
+     *
+     * This list is cached, so it will only be calculated once.
+     *
+     * @return AbstractNode[]
+     */
+    public function getParents(): array
+    {
+        if (!$this->parents) {
+            $parent = $this->parent;
+            while ($parent) {
+                $this->parents[] = $parent;
+                $parent = $parent->getParent();
+            }
+        }
+
+        return $this->parents;
+    }
+
+    /**
+     * Set the direct parent node
+     */
+    public function setParent(AbstractNode $parent): void
+    {
+        $this->parent = $parent;
+    }
+
+    /**
+     * Get the direct parent node
+     *
+     * @return AbstractNode|null
+     */
+    public function getParent(): ?AbstractNode
+    {
+        return $this->parent;
+    }
+
+    /**
+     * @param AbstractNode $child
+     * @return void
+     */
+    public function addChild(AbstractNode $child): void
+    {
+        $child->setParent($this);
+        $this->children[] = $child;
+    }
+
+    /**
+     * Allows to attach an arbitrary property to the page
+     *
+     * @param string $name
+     * @param mixed $value
+     * @return void
+     */
+    public function setProperty(string $name, $value): void
+    {
+        $this->properties[$name] = $value;
+    }
+
+    /**
+     * Get the named property, default is returned when the property is not set
+     *
+     * @param string $name
+     * @param mixed $default
+     * @return mixed
+     */
+    public function getProperty(string $name, $default = null)
+    {
+        if (isset($this->properties[$name])) {
+            return $this->properties[$name];
+        }
+        return $default;
+    }
+
+    /**
+     * Sort the children of this node and all its descendants
+     *
+     * The given comparator function will be called with two nodes as arguments and needs to
+     * return an integer less than, equal to, or greater than zero if the first argument is considered
+     * to be respectively less than, equal to, or greater than the second.
+     *
+     * @param callable $comparator
+     * @return void
+     */
+    public function sort(callable $comparator): void
+    {
+        usort($this->children, $comparator);
+        foreach ($this->children as $child) {
+            $child->sort($comparator);
+        }
+    }
+
+    /**
+     * Get the string representation of the node
+     *
+     * Uses plus char to show the depth of the node in the tree
+     *
+     * @return string
+     */
+    public function __toString(): string
+    {
+        return str_pad('', count($this->getParents()), '+') . $this->id;
+    }
+}
diff --git a/inc/TreeBuilder/Node/ExternalLink.php b/inc/TreeBuilder/Node/ExternalLink.php
new file mode 100644
index 000000000..92078abc0
--- /dev/null
+++ b/inc/TreeBuilder/Node/ExternalLink.php
@@ -0,0 +1,11 @@
+<?php
+
+namespace dokuwiki\TreeBuilder\Node;
+
+/**
+ * A node representing an external link
+ */
+class ExternalLink extends AbstractNode
+{
+
+}
diff --git a/inc/TreeBuilder/Node/Top.php b/inc/TreeBuilder/Node/Top.php
new file mode 100644
index 000000000..0e6236c15
--- /dev/null
+++ b/inc/TreeBuilder/Node/Top.php
@@ -0,0 +1,40 @@
+<?php
+
+namespace dokuwiki\TreeBuilder\Node;
+
+/**
+ * A node representing the top of the tree
+ *
+ * This node has no parents or siblings. It is used to represent the root of the tree.
+ */
+class Top extends AbstractNode
+{
+    public function __construct()
+    {
+        parent::__construct('', '');
+    }
+
+    /**
+     * Always returns an empty array
+     * @inheritdoc
+     */
+    public function getSiblings(): array
+    {
+        return [];
+    }
+
+    /**
+     * Always returns an empty array
+     * @inheritdoc
+     */
+    public function getParents(): array
+    {
+        return [];
+    }
+
+    /** @inheritdoc */
+    public function getHtmlLink(): string
+    {
+        return '';
+    }
+}
diff --git a/inc/TreeBuilder/Node/WikiNamespace.php b/inc/TreeBuilder/Node/WikiNamespace.php
new file mode 100644
index 000000000..69292b793
--- /dev/null
+++ b/inc/TreeBuilder/Node/WikiNamespace.php
@@ -0,0 +1,11 @@
+<?php
+
+namespace dokuwiki\TreeBuilder\Node;
+
+/**
+ * A node representing a wiki namespace
+ */
+class WikiNamespace extends AbstractNode
+{
+
+}
diff --git a/inc/TreeBuilder/Node/WikiPage.php b/inc/TreeBuilder/Node/WikiPage.php
new file mode 100644
index 000000000..9e0996bb1
--- /dev/null
+++ b/inc/TreeBuilder/Node/WikiPage.php
@@ -0,0 +1,11 @@
+<?php
+
+namespace dokuwiki\TreeBuilder\Node;
+
+/**
+ * A node representing a wiki page
+ */
+class WikiPage extends AbstractNode
+{
+
+}
diff --git a/inc/TreeBuilder/Node/WikiStartpage.php b/inc/TreeBuilder/Node/WikiStartpage.php
new file mode 100644
index 000000000..7bb4654c2
--- /dev/null
+++ b/inc/TreeBuilder/Node/WikiStartpage.php
@@ -0,0 +1,38 @@
+<?php
+
+namespace dokuwiki\TreeBuilder\Node;
+
+/**
+ * A node representing a namespace startpage
+ */
+class WikiStartpage extends WikiNamespace
+{
+    protected string $originalNamespace;
+
+    /**
+     * Constructor
+     *
+     * @param string $id The pageID of the startpage
+     * @param string|null $title The title as given in the link
+     * @param string $originalNamespace The original namespace
+     */
+    public function __construct(string $id, ?string $title, string $originalNamespace)
+    {
+        $this->originalNamespace = $originalNamespace;
+        parent::__construct($id, $title);
+    }
+
+    /**
+     * This will return the namespace this startpage is for
+     *
+     * This might differ from the namespace of the pageID, because a startpage may be outside
+     * the namespace.
+     *
+     * @inheritdoc
+     */
+    public function getNs(): string
+    {
+        return $this->originalNamespace;
+    }
+
+}
diff --git a/inc/TreeBuilder/PageTreeBuilder.php b/inc/TreeBuilder/PageTreeBuilder.php
new file mode 100644
index 000000000..e6e9c97eb
--- /dev/null
+++ b/inc/TreeBuilder/PageTreeBuilder.php
@@ -0,0 +1,260 @@
+<?php
+
+namespace dokuwiki\TreeBuilder;
+
+use dokuwiki\File\PageResolver;
+use dokuwiki\TreeBuilder\Node\AbstractNode;
+use dokuwiki\TreeBuilder\Node\Top;
+use dokuwiki\TreeBuilder\Node\WikiNamespace;
+use dokuwiki\TreeBuilder\Node\WikiPage;
+use dokuwiki\TreeBuilder\Node\WikiStartpage;
+use dokuwiki\Utf8\PhpString;
+
+/**
+ * A tree builder for wiki pages and namespaces
+ *
+ * This replace the classic search_* functions approach and provides a way to create a traversable tree
+ * of wiki pages and namespaces.
+ *
+ * The created hierarchy can either use WikiNamespace nodes or represent namespaces as WikiPage nodes
+ * associated with the namespace's start page.
+ */
+class PageTreeBuilder extends AbstractBuilder
+{
+    /** @var array Used to remember already seen start pages */
+    protected array $startpages = [];
+
+    /** @var int Return WikiPage(startpage) instead of WikiNamespace(id) for namespaces */
+    public const FLAG_NS_AS_STARTPAGE = 1;
+
+    /** @var int Do not return Namespaces, will also disable recursion */
+    public const FLAG_NO_NS = 2;
+
+    /** @var int Do not return pages */
+    public const FLAG_NO_PAGES = 4;
+
+    /** @var int Do not filter out hidden pages */
+    public const FLAG_KEEP_HIDDEN = 8;
+
+    /** @var int The given namespace should be added as top element */
+    public const FLAG_SELF_TOP = 16;
+
+    /** @var string The top level namespace to iterate over */
+    protected string $namespace;
+
+    /** @var int The maximum depth to iterate into, -1 for infinite */
+    protected int $maxdepth;
+
+
+    /**
+     * Constructor
+     *
+     * @param string $namespace The namespace to start from
+     * @param int $maxdepth The maximum depth to iterate into, -1 for infinite
+     */
+    public function __construct(string $namespace, int $maxdepth = -1)
+    {
+        $this->namespace = $namespace;
+        $this->maxdepth = $maxdepth;
+    }
+
+    /** @inheritdoc */
+    public function generate(): void
+    {
+        $this->generated = true;
+
+        $this->top = new Top();
+
+        // add directly to top or add the namespace under the top element?
+        if ($this->hasFlag(self::FLAG_SELF_TOP)) {
+            $parent = $this->createNamespaceNode($this->namespace, noNS($this->namespace));
+            $parent->setParent($this->top);
+        } else {
+            if ($this->hasFlag(self::FLAG_NS_AS_STARTPAGE)) {
+                // do not add the namespace's own startpage in this mode
+                $this->startpages[$this->getStartpage($this->namespace)] = 1;
+            }
+
+            $parent = $this->top;
+        }
+
+        // if FLAG_SELF_TOP, we need to run a recursion decision on the parent
+        if ($parent instanceof Top || $this->applyRecursionDecision($parent, 0)) {
+            $dir = $this->namespacePath($this->namespace);
+            $this->createHierarchy($parent, $dir, $this->maxdepth);
+        }
+
+        // if FLAG_SELF_TOP, we need to add the parent to the top
+        if (!$parent instanceof Top) {
+            $this->addNodeToHierarchy($this->top, $parent);
+        }
+    }
+
+    /**
+     * Recursive function to create the page hierarchy
+     *
+     * @param AbstractNode $parent results are added as children to this element
+     * @param string $dir The directory relative to the page directory
+     * @param int $depth Current depth, recursion stops at 0
+     * @return void
+     */
+    protected function createHierarchy(AbstractNode $parent, string $dir, int $depth)
+    {
+        // Process namespaces (subdirectories)
+        if ($this->hasNotFlag(self::FLAG_NO_NS)) {
+            $this->processNamespaces($parent, $dir, $depth);
+        }
+
+        // Process pages (files)
+        if ($this->hasNotFlag(self::FLAG_NO_PAGES)) {
+            $this->processPages($parent, $dir);
+        }
+    }
+
+    /**
+     * Process namespaces (subdirectories) and add them to the hierarchy
+     *
+     * @param AbstractNode $parent Parent node to add children to
+     * @param string $dir Current directory path
+     * @param int $depth Current depth level
+     * @return void
+     */
+    protected function processNamespaces(AbstractNode $parent, string $dir, int $depth)
+    {
+        global $conf;
+        $base = $conf['datadir'] . '/';
+
+        $dirs = glob($base . $dir . '/*', GLOB_ONLYDIR);
+        foreach ($dirs as $subdir) {
+            $subdir = basename($subdir);
+            $id = pathID($dir . '/' . $subdir);
+
+            $node = $this->createNamespaceNode($id, $subdir);
+
+            // Recurse into subdirectory if depth and filter allows
+            if ($depth !== 0 && $this->applyRecursionDecision($node, $this->maxdepth - $depth)) {
+                $this->createHierarchy($node, $dir . '/' . $subdir, $depth - 1);
+            }
+
+            // Add to hierarchy
+            $this->addNodeToHierarchy($parent, $node);
+        }
+    }
+
+    /**
+     * Create a namespace node based on the flags
+     *
+     * @param string $id
+     * @param string $title
+     * @return AbstractNode
+     */
+    protected function createNamespaceNode(string $id, string $title): AbstractNode
+    {
+        if ($this->hasFlag(self::FLAG_NS_AS_STARTPAGE)) {
+            $ns = $id;
+            $id = $this->getStartpage($id); // use the start page for the namespace
+            $this->startpages[$id] = 1; // mark as seen
+            $node = new WikiStartpage($id, $title, $ns);
+        } else {
+            $node = new WikiNamespace($id, $title);
+        }
+        return $node;
+    }
+
+    /**
+     * Process pages (files) and add them to the hierarchy
+     *
+     * @param AbstractNode $parent Parent node to add children to
+     * @param string $dir Current directory path
+     * @return void
+     */
+    protected function processPages(AbstractNode $parent, string $dir)
+    {
+        global $conf;
+        $base = $conf['datadir'] . '/';
+
+        $files = glob($base . $dir . '/*.txt');
+        foreach ($files as $file) {
+            $file = basename($file);
+            $id = pathID($dir . '/' . $file);
+
+            // Skip already shown start pages
+            if (isset($this->startpages[$id])) {
+                continue;
+            }
+
+            $page = new WikiPage($id, $file);
+
+            // Add to hierarchy
+            $this->addNodeToHierarchy($parent, $page);
+        }
+    }
+
+    /**
+     * Run custom node processor and add it to the hierarchy
+     *
+     * @param AbstractNode $parent Parent node
+     * @param AbstractNode $node Node to add
+     * @return void
+     */
+    protected function addNodeToHierarchy(AbstractNode $parent, AbstractNode $node): void
+    {
+        $node->setParent($parent); // set the parent even when not added, yet
+        $node = $this->applyNodeProcessor($node);
+        if ($node instanceof AbstractNode) {
+            $parent->addChild($node);
+        }
+    }
+
+    /**
+     * Get the start page for the given namespace
+     *
+     * @param string $ns The namespace to get the start page for
+     * @return string The start page id
+     */
+    protected function getStartpage(string $ns): string
+    {
+        $id = $ns . ':';
+        return (new PageResolver(''))->resolveId($id);
+    }
+
+    /**
+     * Get the file path for the given namespace relative to the page directory
+     *
+     * @param string $namespace
+     * @return string
+     */
+    protected function namespacePath(string $namespace): string
+    {
+        global $conf;
+
+        $base = $conf['datadir'] . '/';
+        $dir = wikiFN($namespace . ':xxx');
+        $dir = substr($dir, strlen($base));
+        $dir = dirname($dir); // remove the 'xxx' part
+        if($dir === '.') $dir = ''; // dirname returns '.' for root namespace
+        return $dir;
+    }
+
+    /** @inheritdoc */
+    protected function applyRecursionDecision(AbstractNode $node, int $depth): bool
+    {
+        // automatically skip hidden elements unless disabled by flag
+        if (!$this->hasNotFlag(self::FLAG_KEEP_HIDDEN) && isHiddenPage($node->getId())) {
+            return false;
+        }
+        return parent::applyRecursionDecision($node, $depth);
+    }
+
+    /** @inheritdoc */
+    protected function applyNodeProcessor(AbstractNode $node): ?AbstractNode
+    {
+        // automatically skip hidden elements unless disabled by flag
+        if (!$this->hasNotFlag(self::FLAG_KEEP_HIDDEN) && isHiddenPage($node->getId())) {
+            return null;
+        }
+        return parent::applyNodeProcessor($node);
+    }
+
+
+}
diff --git a/inc/TreeBuilder/TreeSort.php b/inc/TreeBuilder/TreeSort.php
new file mode 100644
index 000000000..9195f3999
--- /dev/null
+++ b/inc/TreeBuilder/TreeSort.php
@@ -0,0 +1,103 @@
+<?php
+
+namespace dokuwiki\TreeBuilder;
+
+use dokuwiki\TreeBuilder\Node\AbstractNode;
+use dokuwiki\TreeBuilder\Node\WikiNamespace;
+use dokuwiki\Utf8\Sort;
+
+/**
+ * Class that provides comparators for sorting the tree nodes
+ */
+class TreeSort
+{
+    public const SORT_BY_ID = [self::class, 'sortById'];
+    public const SORT_BY_TITLE = [self::class, 'sortByTitle'];
+    public const SORT_BY_NS_FIRST_THEN_ID = [self::class, 'sortByNsFirstThenId'];
+    public const SORT_BY_NS_FIRST_THEN_TITLE = [self::class, 'sortByNsFirstThenTitle'];
+
+    /**
+     * Comparator to sort by ID
+     *
+     * @param AbstractNode $a
+     * @param AbstractNode $b
+     * @return int
+     */
+    public static function sortById(AbstractNode $a, AbstractNode $b): int
+    {
+        // we need to compare the ID segment by segment
+        $pathA = explode(':', $a->getId());
+        $pathB = explode(':', $b->getId());
+        $min = min(count($pathA), count($pathB));
+
+        for ($i = 0; $i < $min; $i++) {
+            if ($pathA[$i] !== $pathB[$i]) {
+                return $pathA[$i] <=> $pathB[$i];
+            }
+        }
+        return count($pathA) <=> count($pathB);
+    }
+
+
+    /**
+     * Comparator to sort namespace first, then by ID
+     *
+     * @param AbstractNode $a
+     * @param AbstractNode $b
+     * @return int
+     */
+    public static function sortByNsFirstThenId(AbstractNode $a, AbstractNode $b): int
+    {
+        $res = self::sortByNsFirst($a, $b);
+        if ($res === 0) $res = self::sortById($a, $b);
+        return $res;
+    }
+
+    /**
+     * Comparator to sort by title (using natural sort)
+     *
+     * @param AbstractNode $a
+     * @param AbstractNode $b
+     * @return int
+     */
+    public static function sortByTitle(AbstractNode $a, AbstractNode $b): int
+    {
+        return Sort::strcmp($a->getTitle(), $b->getTitle());
+    }
+
+    /**
+     * Comparator to sort namespace first, then by title
+     *
+     * @param AbstractNode $a
+     * @param AbstractNode $b
+     * @return int
+     */
+    public static function sortByNsFirstThenTitle(AbstractNode $a, AbstractNode $b): int
+    {
+        $res = self::sortByNsFirst($a, $b);
+        if ($res === 0) $res = self::sortByTitle($a, $b);
+        return $res;
+    }
+
+    /**
+     * Comparator to sort by namespace first
+     *
+     * @param AbstractNode $a
+     * @param AbstractNode $b
+     * @return int
+     */
+    protected static function sortByNsFirst(AbstractNode $a, AbstractNode $b): int
+    {
+        $isAaNs = ($a instanceof WikiNamespace);
+        $isBaNs = ($b instanceof WikiNamespace);
+
+        if ($isAaNs !== $isBaNs) {
+            if ($isAaNs) {
+                return -1;
+            } elseif ($isBaNs) {
+                return 1;
+            }
+        }
+        return 0;
+    }
+}