Code Coverage
 
Lines
Branches
Paths
Functions and Methods
Classes and Traits
Total
91.35%
169 / 185
89.43%
110 / 123
54.55%
48 / 88
74.07%
20 / 27
 CRAP
0.00%
0 / 1
SourceTree
91.35%
169 / 185
89.43%
110 / 123
54.55%
48 / 88
74.07%
20 / 27
 516.13
0.00%
0 / 1
 __construct
100.00%
2 / 2
100.00%
1 / 1
100.00%
1 / 1
100.00%
1 / 1
 1
 rebuild
100.00%
5 / 5
100.00%
1 / 1
100.00%
1 / 1
100.00%
1 / 1
 1
 getTree
100.00%
1 / 1
100.00%
1 / 1
100.00%
1 / 1
100.00%
1 / 1
 1
 getNormalizedStructure
0.00%
0 / 5
0.00%
0 / 1
0.00%
0 / 1
0.00%
0 / 1
 2
 getPathIndex
100.00%
4 / 4
100.00%
3 / 3
100.00%
2 / 2
100.00%
1 / 1
 2
 attachToRoot
100.00%
13 / 13
100.00%
1 / 1
100.00%
1 / 1
100.00%
1 / 1
 1
 attachToSlot
100.00%
17 / 17
100.00%
5 / 5
100.00%
3 / 3
100.00%
1 / 1
 3
 moveToRoot
100.00%
7 / 7
100.00%
3 / 3
100.00%
2 / 2
100.00%
1 / 1
 2
 moveToSlot
100.00%
13 / 13
100.00%
9 / 9
100.00%
5 / 5
100.00%
1 / 1
 5
 remove
100.00%
5 / 5
100.00%
3 / 3
100.00%
2 / 2
100.00%
1 / 1
 2
 hasNode
100.00%
1 / 1
100.00%
1 / 1
100.00%
1 / 1
100.00%
1 / 1
 1
 getNodeData
100.00%
1 / 1
100.00%
1 / 1
100.00%
1 / 1
100.00%
1 / 1
 1
 getNode
100.00%
3 / 3
100.00%
3 / 3
100.00%
2 / 2
100.00%
1 / 1
 2
 getParentId
100.00%
1 / 1
100.00%
1 / 1
100.00%
1 / 1
100.00%
1 / 1
 1
 setSource
100.00%
5 / 5
100.00%
3 / 3
100.00%
2 / 2
100.00%
1 / 1
 2
 setThirdPartySettings
100.00%
6 / 6
100.00%
5 / 5
66.67%
2 / 3
100.00%
1 / 1
 3.33
 generateNodeId
100.00%
1 / 1
100.00%
1 / 1
100.00%
1 / 1
100.00%
1 / 1
 1
 normalize
100.00%
21 / 21
100.00%
12 / 12
33.33%
4 / 12
100.00%
1 / 1
 12.41
 denormalize
100.00%
5 / 5
100.00%
1 / 1
100.00%
1 / 1
100.00%
1 / 1
 1
 injectChildren
100.00%
9 / 9
100.00%
10 / 10
22.22%
2 / 9
100.00%
1 / 1
 16.76
 buildPathIndex
92.86%
13 / 14
91.67%
11 / 12
37.50%
3 / 8
0.00%
0 / 1
 11.10
 removeFromCurrentParent
80.00%
16 / 20
73.33%
11 / 15
27.27%
3 / 11
0.00%
0 / 1
 32.62
 recursiveRemove
83.33%
5 / 6
88.89%
8 / 9
33.33%
2 / 6
0.00%
0 / 1
 8.74
 isDescendant
100.00%
6 / 6
100.00%
6 / 6
33.33%
1 / 3
100.00%
1 / 1
 5.67
 getSourcePlugin
50.00%
2 / 4
50.00%
3 / 6
33.33%
1 / 3
0.00%
0 / 1
 5.67
 getPluginClass
71.43%
5 / 7
66.67%
4 / 6
66.67%
2 / 3
0.00%
0 / 1
 3.33
 getSourceManager
66.67%
2 / 3
66.67%
2 / 3
50.00%
1 / 2
0.00%
0 / 1
 2.50
1<?php
2
3declare(strict_types=1);
4
5namespace Drupal\display_builder;
6
7use Drupal\Component\Plugin\PluginManagerInterface;
8use Drupal\Component\Utility\NestedArray;
9use Drupal\ui_patterns\SourceInterface;
10
11/**
12 * Manages hierarchical data with a high-performance normalized structure.
13 *
14 * This class converts nested source trees into a flat internal representation:
15 * - A 'nodes' map containing the raw configuration for each unique node.
16 * - A 'structure' map defining parent-child relationships and slot assignments.
17 *
18 * This normalization allows for O(1) or O(log N) operations when moving,
19 * updating, or retrieving specific nodes, regardless of tree depth. The
20 * tree is only denormalized back into a nested format when requested via
21 * ::getTree() for rendering or persistence.
22 */
23class SourceTree {
24
25  /**
26   * Flat map of node data keyed by node_id.
27   */
28  protected array $nodes = [];
29
30  /**
31   * Hierarchical structure of node IDs.
32   */
33  protected array $structure = [];
34
35  /**
36   * List of root node IDs.
37   */
38  protected array $root = [];
39
40  /**
41   * Cached path index.
42   */
43  protected ?array $pathIndex = NULL;
44
45  /**
46   * The source plugin manager.
47   */
48  protected ?PluginManagerInterface $sourceManager = NULL;
49
50  /**
51   * Cache of resolved plugin classes keyed by source_id.
52   */
53  protected array $pluginClassCache = [];
54
55  /**
56   * Constructor.
57   *
58   * @param array $tree
59   *   Initial nested tree data.
60   * @param \Drupal\Component\Plugin\PluginManagerInterface|null $sourceManager
61   *   The source plugin manager.
62   */
63  public function __construct(array $tree = [], ?PluginManagerInterface $sourceManager = NULL) {
64    $this->sourceManager = $sourceManager;
65    $this->rebuild($tree);
66  }
67
68  /**
69   * Rebuild the internal normalized state from a nested tree.
70   *
71   * @param array $tree
72   *   The nested tree data.
73   */
74  public function rebuild(array $tree): void {
75    $this->nodes = [];
76    $this->structure = [];
77    $this->pluginClassCache = [];
78    $this->root = $this->normalize($tree, NULL, NULL);
79    $this->pathIndex = NULL;
80  }
81
82  /**
83   * Get the nested tree data.
84   *
85   * @return array
86   *   The full nested tree data.
87   */
88  public function getTree(): array {
89    return $this->denormalize($this->root);
90  }
91
92  /**
93   * Get the raw normalized structure (nodes, structure, root).
94   *
95   * Returns the internal flat representation before denormalization, useful
96   * for debugging and dev tooling.
97   *
98   * @return array
99   *   An array with keys 'nodes', 'structure', and 'root'.
100   */
101  public function getNormalizedStructure(): array {
102    return [
103      'nodes' => $this->nodes,
104      'structure' => $this->structure,
105      'root' => $this->root,
106    ];
107  }
108
109  /**
110   * Get the path index.
111   *
112   * @return array
113   *   The path index.
114   */
115  public function getPathIndex(): array {
116    if ($this->pathIndex === NULL) {
117      $this->pathIndex = [];
118      $this->buildPathIndex($this->root, [], $this->pathIndex);
119    }
120
121    return $this->pathIndex;
122  }
123
124  /**
125   * Attach a new source to root.
126   *
127   * @param int $position
128   *   The position in the root list.
129   * @param string $source_id
130   *   The source plugin ID.
131   * @param array $source_data
132   *   The source configuration data.
133   *
134   * @return string
135   *   The new node ID.
136   */
137  public function attachToRoot(int $position, string $source_id, array $source_data): string {
138    $node_id = $this->generateNodeId();
139    $this->nodes[$node_id] = [
140      'source_id' => $source_id,
141      'source' => $source_data,
142    ];
143    $this->structure[$node_id] = [
144      'parent' => NULL,
145      'slot' => NULL,
146      'slots' => [],
147    ];
148    \array_splice($this->root, $position, 0, [$node_id]);
149    $this->pathIndex = NULL;
150
151    return $node_id;
152  }
153
154  /**
155   * Attach a new source to a slot.
156   *
157   * @param string $parent_id
158   *   The parent node ID.
159   * @param string $slot_id
160   *   The slot ID.
161   * @param int $position
162   *   The position in the slot.
163   * @param string $source_id
164   *   The source plugin ID.
165   * @param array $source_data
166   *   The source configuration data.
167   *
168   * @return string|null
169   *   The new node ID or NULL if parent not found.
170   */
171  public function attachToSlot(string $parent_id, string $slot_id, int $position, string $source_id, array $source_data): ?string {
172    if (!isset($this->structure[$parent_id])) {
173      return NULL;
174    }
175
176    $node_id = $this->generateNodeId();
177    $this->nodes[$node_id] = [
178      'source_id' => $source_id,
179      'source' => $source_data,
180    ];
181    $this->structure[$node_id] = [
182      'parent' => $parent_id,
183      'slot' => $slot_id,
184      'slots' => [],
185    ];
186
187    if (!isset($this->structure[$parent_id]['slots'][$slot_id])) {
188      $this->structure[$parent_id]['slots'][$slot_id] = [];
189    }
190    \array_splice($this->structure[$parent_id]['slots'][$slot_id], $position, 0, [$node_id]);
191    $this->pathIndex = NULL;
192
193    return $node_id;
194  }
195
196  /**
197   * Move node to root.
198   *
199   * @param string $node_id
200   *   The node ID to move.
201   * @param int $position
202   *   The new position in the root list.
203   *
204   * @return bool
205   *   TRUE if success.
206   */
207  public function moveToRoot(string $node_id, int $position): bool {
208    if (!$this->removeFromCurrentParent($node_id)) {
209      return FALSE;
210    }
211
212    $this->structure[$node_id]['parent'] = NULL;
213    $this->structure[$node_id]['slot'] = NULL;
214    \array_splice($this->root, $position, 0, [$node_id]);
215    $this->pathIndex = NULL;
216
217    return TRUE;
218  }
219
220  /**
221   * Move node to a slot.
222   *
223   * @param string $node_id
224   *   The node ID to move.
225   * @param string $parent_id
226   *   The target parent ID.
227   * @param string $slot_id
228   *   The target slot ID.
229   * @param int $position
230   *   The position in the target slot.
231   *
232   * @return bool
233   *   TRUE if success.
234   */
235  public function moveToSlot(string $node_id, string $parent_id, string $slot_id, int $position): bool {
236    if (!isset($this->structure[$parent_id])) {
237      return FALSE;
238    }
239
240    // Forbidden move: moving a parent into its own descendant.
241    if ($this->isDescendant($parent_id, $node_id)) {
242      return FALSE;
243    }
244
245    if (!$this->removeFromCurrentParent($node_id)) {
246      return FALSE;
247    }
248
249    $this->structure[$node_id]['parent'] = $parent_id;
250    $this->structure[$node_id]['slot'] = $slot_id;
251
252    if (!isset($this->structure[$parent_id]['slots'][$slot_id])) {
253      $this->structure[$parent_id]['slots'][$slot_id] = [];
254    }
255    \array_splice($this->structure[$parent_id]['slots'][$slot_id], $position, 0, [$node_id]);
256    $this->pathIndex = NULL;
257
258    return TRUE;
259  }
260
261  /**
262   * Remove a node and its descendants.
263   *
264   * @param string $node_id
265   *   The node ID to remove.
266   *
267   * @return bool
268   *   TRUE if success.
269   */
270  public function remove(string $node_id): bool {
271    if (!$this->removeFromCurrentParent($node_id)) {
272      return FALSE;
273    }
274    $this->recursiveRemove($node_id);
275    $this->pathIndex = NULL;
276
277    return TRUE;
278  }
279
280  /**
281   * Check if a node exists.
282   *
283   * @param string $node_id
284   *   The node ID.
285   *
286   * @return bool
287   *   TRUE if it exists.
288   */
289  public function hasNode(string $node_id): bool {
290    return isset($this->nodes[$node_id]);
291  }
292
293  /**
294   * Get flat node data (no children).
295   *
296   * @param string $node_id
297   *   The node ID.
298   *
299   * @return array|null
300   *   The flat node data or NULL.
301   */
302  public function getNodeData(string $node_id): ?array {
303    return $this->nodes[$node_id] ?? NULL;
304  }
305
306  /**
307   * Get a node data by ID (nested subtree).
308   *
309   * @param string $node_id
310   *   The node ID.
311   *
312   * @return array|null
313   *   The node data (nested structure for that node) or NULL.
314   */
315  public function getNode(string $node_id): ?array {
316    if (!isset($this->nodes[$node_id])) {
317      return NULL;
318    }
319
320    return $this->denormalize([$node_id])[0];
321  }
322
323  /**
324   * Get the parent ID of a node.
325   *
326   * @param string $node_id
327   *   The node ID.
328   *
329   * @return string|null
330   *   The parent ID or NULL if at root.
331   */
332  public function getParentId(string $node_id): ?string {
333    return $this->structure[$node_id]['parent'] ?? NULL;
334  }
335
336  /**
337   * Set source data for a node.
338   *
339   * @param string $node_id
340   *   The node ID.
341   * @param string $source_id
342   *   The source plugin ID.
343   * @param array $source_data
344   *   The source configuration data.
345   *
346   * @return bool
347   *   TRUE if success.
348   */
349  public function setSource(string $node_id, string $source_id, array $source_data): bool {
350    if (!isset($this->nodes[$node_id])) {
351      return FALSE;
352    }
353    $this->nodes[$node_id]['source_id'] = $source_id;
354    $this->nodes[$node_id]['source'] = $source_data;
355
356    return TRUE;
357  }
358
359  /**
360   * Set third party settings for a node.
361   *
362   * @param string $node_id
363   *   The node ID.
364   * @param string $island_id
365   *   The island (plugin) ID.
366   * @param array $data
367   *   The third party settings data.
368   *
369   * @return bool
370   *   TRUE if success.
371   */
372  public function setThirdPartySettings(string $node_id, string $island_id, array $data): bool {
373    if (!isset($this->nodes[$node_id])) {
374      return FALSE;
375    }
376
377    if (!isset($this->nodes[$node_id]['third_party_settings'])) {
378      $this->nodes[$node_id]['third_party_settings'] = [];
379    }
380    $this->nodes[$node_id]['third_party_settings'][$island_id] = $data;
381
382    return TRUE;
383  }
384
385  /**
386   * Generate a unique node ID.
387   *
388   * @return string
389   *   The generated node ID.
390   */
391  protected function generateNodeId(): string {
392    return \bin2hex(\random_bytes(8));
393  }
394
395  /**
396   * Normalize a nested tree into flat maps.
397   *
398   * @param array $items
399   *   Nested items.
400   * @param string|null $parent_id
401   *   Current parent ID.
402   * @param string|null $slot_id
403   *   Current slot ID.
404   *
405   * @return array
406   *   List of node IDs at this level.
407   */
408  protected function normalize(array $items, ?string $parent_id, ?string $slot_id): array {
409    $ids = [];
410
411    foreach ($items as $item) {
412      $node_id = $item['node_id'] ?? $this->generateNodeId();
413      $ids[] = $node_id;
414
415      $source_id = $item['source_id'] ?? '';
416      $plugin = $this->getSourcePlugin($source_id, $item['source'] ?? []);
417
418      $slots = [];
419
420      if ($plugin instanceof SourceWithSlotsInterface) {
421        foreach ($plugin->getSlotValues() as $child_slot_id => $data) {
422          $slots[$child_slot_id] = $this->normalize($data, $node_id, $child_slot_id);
423        }
424
425        foreach ($plugin->getSlotDefinitions() as $child_slot_id => $_) {
426          $path = $plugin::getSlotPath($child_slot_id);
427          NestedArray::unsetValue($item['source'], $path);
428        }
429      }
430
431      $item['node_id'] = $node_id;
432      $this->structure[$node_id] = [
433        'parent' => $parent_id,
434        'slot' => $slot_id,
435        'slots' => $slots,
436      ];
437      $this->nodes[$node_id] = $item;
438    }
439
440    return $ids;
441  }
442
443  /**
444   * Denormalize a list of node IDs into a nested tree.
445   *
446   * @param array $ids
447   *   The IDs to assemble.
448   *
449   * @return array
450   *   The nested tree.
451   */
452  protected function denormalize(array $ids): array {
453    return \array_map(function ($id) {
454      $node = $this->nodes[$id];
455      $node['node_id'] = $id;
456
457      return $this->injectChildren($node, $this->structure[$id]['slots']);
458    }, $ids);
459  }
460
461  /**
462   * Inject children IDs back into a node as nested data.
463   *
464   * @param array $node
465   *   The node data.
466   * @param array $slots
467   *   The slots with children IDs.
468   *
469   * @return array
470   *   The node data with children injected.
471   */
472  protected function injectChildren(array $node, array $slots): array {
473    if (empty($slots)) {
474      return $node;
475    }
476
477    $source_id = $node['source_id'] ?? '';
478    $class = $this->getPluginClass($source_id);
479
480    if ($class && \is_subclass_of($class, SourceWithSlotsInterface::class)) {
481      foreach ($slots as $slot_id => $child_ids) {
482        $path = $class::getSlotPath($slot_id);
483        NestedArray::setValue($node['source'], $path, $this->denormalize($child_ids));
484      }
485    }
486
487    return $node;
488  }
489
490  /**
491   * Build the path index recursively.
492   *
493   * @param array $ids
494   *   Current IDs level.
495   * @param array $current_path
496   *   Current path keys.
497   * @param array $index
498   *   The index to populate.
499   */
500  protected function buildPathIndex(array $ids, array $current_path, array &$index): void {
501    foreach ($ids as $idx => $id) {
502      $path = [...$current_path, $idx];
503      $index[$id] = [
504        'path' => $path,
505        'parent' => $this->structure[$id]['parent'],
506      ];
507
508      $struct = $this->structure[$id];
509      $source_id = $this->nodes[$id]['source_id'];
510      $class = $this->getPluginClass($source_id);
511
512      foreach ($struct['slots'] as $slot_id => $child_ids) {
513        if ($class && \is_subclass_of($class, SourceWithSlotsInterface::class)) {
514          $child_path = [...$path, 'source', ...$class::getSlotPath($slot_id)];
515        }
516        else {
517          continue;
518        }
519        $this->buildPathIndex($child_ids, $child_path, $index);
520      }
521    }
522  }
523
524  /**
525   * Remove a node from its parent's children list.
526   *
527   * @param string $node_id
528   *   The node ID.
529   *
530   * @return bool
531   *   TRUE if found and removed.
532   */
533  protected function removeFromCurrentParent(string $node_id): bool {
534    if (!isset($this->structure[$node_id])) {
535      return FALSE;
536    }
537
538    $parent_id = $this->structure[$node_id]['parent'];
539    $slot_id = $this->structure[$node_id]['slot'];
540
541    if ($parent_id === NULL) {
542      $key = \array_search($node_id, $this->root, TRUE);
543
544      if ($key === FALSE) {
545        return FALSE;
546      }
547      \array_splice($this->root, (int) $key, 1);
548
549      return TRUE;
550    }
551
552    if ($slot_id === NULL || !isset($this->structure[$parent_id]['slots'][$slot_id])) {
553      return FALSE;
554    }
555
556    $child_ids = &$this->structure[$parent_id]['slots'][$slot_id];
557
558    if (!\is_array($child_ids)) {
559      return FALSE;
560    }
561    $key = \array_search($node_id, $child_ids, TRUE);
562
563    if ($key !== FALSE) {
564      \array_splice($child_ids, (int) $key, 1);
565
566      return TRUE;
567    }
568
569    return FALSE;
570  }
571
572  /**
573   * Recursively remove node and data.
574   *
575   * @param string $node_id
576   *   The node ID.
577   */
578  protected function recursiveRemove(string $node_id): void {
579    if (!isset($this->structure[$node_id])) {
580      return;
581    }
582
583    foreach ($this->structure[$node_id]['slots'] as $child_ids) {
584      foreach ($child_ids as $child_id) {
585        $this->recursiveRemove($child_id);
586      }
587    }
588    unset($this->nodes[$node_id], $this->structure[$node_id]);
589  }
590
591  /**
592   * Check if a node is a descendant of another.
593   *
594   * @param string $node_id
595   *   The node ID to check.
596   * @param string $potential_ancestor_id
597   *   The potential ancestor ID.
598   *
599   * @return bool
600   *   TRUE if descendant.
601   */
602  protected function isDescendant(string $node_id, string $potential_ancestor_id): bool {
603    $current_parent = $this->getParentId($node_id);
604
605    while ($current_parent !== NULL) {
606      if ($current_parent === $potential_ancestor_id) {
607        return TRUE;
608      }
609      $current_parent = $this->getParentId($current_parent);
610    }
611
612    return FALSE;
613  }
614
615  /**
616   * Get source plugin instance.
617   *
618   * @param string $source_id
619   *   The source plugin ID.
620   * @param array $source_configuration
621   *   The source configuration.
622   *
623   * @return \Drupal\ui_patterns\SourceInterface|null
624   *   The source plugin instance or NULL.
625   */
626  protected function getSourcePlugin(string $source_id, array $source_configuration): ?SourceInterface {
627    try {
628      $plugin = $this->getSourceManager()->createInstance($source_id, ['settings' => $source_configuration]);
629
630      return $plugin instanceof SourceInterface ? $plugin : NULL;
631    }
632    catch (\Exception $e) {
633      return NULL;
634    }
635  }
636
637  /**
638   * Get source plugin class.
639   *
640   * @param string $source_id
641   *   The source plugin ID.
642   *
643   * @return string|null
644   *   The plugin class or NULL.
645   */
646  protected function getPluginClass(string $source_id): ?string {
647    if (\array_key_exists($source_id, $this->pluginClassCache)) {
648      return $this->pluginClassCache[$source_id];
649    }
650
651    try {
652      $definition = $this->getSourceManager()->getDefinition($source_id);
653      $this->pluginClassCache[$source_id] = $definition['class'] ?? NULL;
654    }
655    catch (\Exception $e) {
656      $this->pluginClassCache[$source_id] = NULL;
657    }
658
659    return $this->pluginClassCache[$source_id];
660  }
661
662  /**
663   * Get source plugin manager.
664   *
665   * @return \Drupal\Component\Plugin\PluginManagerInterface
666   *   The source plugin manager.
667   */
668  protected function getSourceManager(): PluginManagerInterface {
669    if ($this->sourceManager === NULL) {
670      $this->sourceManager = \Drupal::service('plugin.manager.ui_patterns_source');
671    }
672
673    return $this->sourceManager;
674  }
675
676}