Code Coverage
 
Lines
Branches
Paths
Functions and Methods
Classes and Traits
Total
90.00%
171 / 190
88.98%
113 / 127
53.33%
48 / 90
74.07%
20 / 27
 CRAP
0.00%
0 / 1
SourceTree
90.00%
171 / 190
88.98%
113 / 127
53.33%
48 / 90
74.07%
20 / 27
 583.31
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%
15 / 15
100.00%
11 / 11
100.00%
6 / 6
100.00%
1 / 1
 6
 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
25.00%
3 / 12
100.00%
1 / 1
 15.55
 denormalize
100.00%
4 / 4
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
87.50%
14 / 16
85.71%
12 / 14
33.33%
3 / 9
0.00%
0 / 1
 16.67
 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
40.00%
2 / 5
50.00%
3 / 6
33.33%
1 / 3
0.00%
0 / 1
 5.67
 getPluginClass
62.50%
5 / 8
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 */
23final class SourceTree {
24
25  /**
26   * Flat map of node data keyed by node_id.
27   */
28  private array $nodes = [];
29
30  /**
31   * Hierarchical structure of node IDs.
32   */
33  private array $structure = [];
34
35  /**
36   * List of root node IDs.
37   */
38  private array $root = [];
39
40  /**
41   * Cached path index.
42   */
43  private ?array $pathIndex = NULL;
44
45  /**
46   * The source plugin manager.
47   */
48  private ?PluginManagerInterface $sourceManager = NULL;
49
50  /**
51   * Cache of resolved plugin classes keyed by source_id.
52   */
53  private 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 node into itself.
241    if ($node_id === $parent_id) {
242      return FALSE;
243    }
244
245    // Forbidden move: moving a parent into its own descendant.
246    if ($this->isDescendant($parent_id, $node_id)) {
247      return FALSE;
248    }
249
250    if (!$this->removeFromCurrentParent($node_id)) {
251      return FALSE;
252    }
253
254    $this->structure[$node_id]['parent'] = $parent_id;
255    $this->structure[$node_id]['slot'] = $slot_id;
256
257    if (!isset($this->structure[$parent_id]['slots'][$slot_id])) {
258      $this->structure[$parent_id]['slots'][$slot_id] = [];
259    }
260    \array_splice($this->structure[$parent_id]['slots'][$slot_id], $position, 0, [$node_id]);
261    $this->pathIndex = NULL;
262
263    return TRUE;
264  }
265
266  /**
267   * Remove a node and its descendants.
268   *
269   * @param string $node_id
270   *   The node ID to remove.
271   *
272   * @return bool
273   *   TRUE if success.
274   */
275  public function remove(string $node_id): bool {
276    if (!$this->removeFromCurrentParent($node_id)) {
277      return FALSE;
278    }
279    $this->recursiveRemove($node_id);
280    $this->pathIndex = NULL;
281
282    return TRUE;
283  }
284
285  /**
286   * Check if a node exists.
287   *
288   * @param string $node_id
289   *   The node ID.
290   *
291   * @return bool
292   *   TRUE if it exists.
293   */
294  public function hasNode(string $node_id): bool {
295    return isset($this->nodes[$node_id]);
296  }
297
298  /**
299   * Get flat node data (no children).
300   *
301   * @param string $node_id
302   *   The node ID.
303   *
304   * @return array|null
305   *   The flat node data or NULL.
306   */
307  public function getNodeData(string $node_id): ?array {
308    return $this->nodes[$node_id] ?? NULL;
309  }
310
311  /**
312   * Get a node data by ID (nested subtree).
313   *
314   * @param string $node_id
315   *   The node ID.
316   *
317   * @return array|null
318   *   The node data (nested structure for that node) or NULL.
319   */
320  public function getNode(string $node_id): ?array {
321    if (!isset($this->nodes[$node_id])) {
322      return NULL;
323    }
324
325    return $this->denormalize([$node_id])[0];
326  }
327
328  /**
329   * Get the parent ID of a node.
330   *
331   * @param string $node_id
332   *   The node ID.
333   *
334   * @return string|null
335   *   The parent ID or NULL if at root.
336   */
337  public function getParentId(string $node_id): ?string {
338    return $this->structure[$node_id]['parent'] ?? NULL;
339  }
340
341  /**
342   * Set source data for a node.
343   *
344   * @param string $node_id
345   *   The node ID.
346   * @param string $source_id
347   *   The source plugin ID.
348   * @param array $source_data
349   *   The source configuration data.
350   *
351   * @return bool
352   *   TRUE if success.
353   */
354  public function setSource(string $node_id, string $source_id, array $source_data): bool {
355    if (!isset($this->nodes[$node_id])) {
356      return FALSE;
357    }
358    $this->nodes[$node_id]['source_id'] = $source_id;
359    $this->nodes[$node_id]['source'] = $source_data;
360
361    return TRUE;
362  }
363
364  /**
365   * Set third party settings for a node.
366   *
367   * @param string $node_id
368   *   The node ID.
369   * @param string $island_id
370   *   The island (plugin) ID.
371   * @param array $data
372   *   The third party settings data.
373   *
374   * @return bool
375   *   TRUE if success.
376   */
377  public function setThirdPartySettings(string $node_id, string $island_id, array $data): bool {
378    if (!isset($this->nodes[$node_id])) {
379      return FALSE;
380    }
381
382    if (!isset($this->nodes[$node_id]['third_party_settings'])) {
383      $this->nodes[$node_id]['third_party_settings'] = [];
384    }
385    $this->nodes[$node_id]['third_party_settings'][$island_id] = $data;
386
387    return TRUE;
388  }
389
390  /**
391   * Generate a unique node ID.
392   *
393   * @return string
394   *   The generated node ID.
395   */
396  private function generateNodeId(): string {
397    return \bin2hex(\random_bytes(8));
398  }
399
400  /**
401   * Normalize a nested tree into flat maps.
402   *
403   * @param array $items
404   *   Nested items.
405   * @param string|null $parent_id
406   *   Current parent ID.
407   * @param string|null $slot_id
408   *   Current slot ID.
409   *
410   * @return array
411   *   List of node IDs at this level.
412   */
413  private function normalize(array $items, ?string $parent_id, ?string $slot_id): array {
414    $ids = [];
415
416    foreach ($items as $item) {
417      $node_id = $item['node_id'] ?? $this->generateNodeId();
418      $ids[] = $node_id;
419
420      $source_id = $item['source_id'] ?? '';
421      $plugin = $this->getSourcePlugin($source_id, $item['source'] ?? []);
422
423      $slots = [];
424
425      if ($plugin instanceof SourceWithSlotsInterface) {
426        foreach ($plugin->getSlotValues() as $child_slot_id => $data) {
427          $slots[$child_slot_id] = $this->normalize($data, $node_id, $child_slot_id);
428        }
429
430        foreach ($plugin->getSlotDefinitions() as $child_slot_id => $_) {
431          $path = $plugin::getSlotPath($child_slot_id);
432          NestedArray::unsetValue($item['source'], $path);
433        }
434      }
435
436      unset($item['node_id']);
437      $this->structure[$node_id] = [
438        'parent' => $parent_id,
439        'slot' => $slot_id,
440        'slots' => $slots,
441      ];
442      $this->nodes[$node_id] = $item;
443    }
444
445    return $ids;
446  }
447
448  /**
449   * Denormalize a list of node IDs into a nested tree.
450   *
451   * @param array $ids
452   *   The IDs to assemble.
453   *
454   * @return array
455   *   The nested tree.
456   */
457  private function denormalize(array $ids): array {
458    return \array_map(function ($id) {
459      $node = ['node_id' => $id] + $this->nodes[$id];
460
461      return $this->injectChildren($node, $this->structure[$id]['slots']);
462    }, $ids);
463  }
464
465  /**
466   * Inject children IDs back into a node as nested data.
467   *
468   * @param array $node
469   *   The node data.
470   * @param array $slots
471   *   The slots with children IDs.
472   *
473   * @return array
474   *   The node data with children injected.
475   */
476  private function injectChildren(array $node, array $slots): array {
477    if (empty($slots)) {
478      return $node;
479    }
480
481    $source_id = $node['source_id'] ?? '';
482    $class = $this->getPluginClass($source_id);
483
484    if ($class && \is_subclass_of($class, SourceWithSlotsInterface::class)) {
485      foreach ($slots as $slot_id => $child_ids) {
486        $path = $class::getSlotPath($slot_id);
487        NestedArray::setValue($node['source'], $path, $this->denormalize($child_ids));
488      }
489    }
490
491    return $node;
492  }
493
494  /**
495   * Build the path index recursively.
496   *
497   * @param array $ids
498   *   Current IDs level.
499   * @param array $current_path
500   *   Current path keys.
501   * @param array $index
502   *   The index to populate.
503   */
504  private function buildPathIndex(array $ids, array $current_path, array &$index): void {
505    foreach ($ids as $idx => $id) {
506      $path = [...$current_path, $idx];
507      $index[$id] = [
508        'path' => $path,
509        'parent' => $this->structure[$id]['parent'],
510      ];
511
512      $struct = $this->structure[$id];
513      $source_id = $this->nodes[$id]['source_id'];
514
515      if ($source_id === NULL) {
516        continue;
517      }
518      $class = $this->getPluginClass($source_id);
519
520      foreach ($struct['slots'] as $slot_id => $child_ids) {
521        if ($class && \is_subclass_of($class, SourceWithSlotsInterface::class)) {
522          $child_path = [...$path, 'source', ...$class::getSlotPath($slot_id)];
523        }
524        else {
525          continue;
526        }
527        $this->buildPathIndex($child_ids, $child_path, $index);
528      }
529    }
530  }
531
532  /**
533   * Remove a node from its parent's children list.
534   *
535   * @param string $node_id
536   *   The node ID.
537   *
538   * @return bool
539   *   TRUE if found and removed.
540   */
541  private function removeFromCurrentParent(string $node_id): bool {
542    if (!isset($this->structure[$node_id])) {
543      return FALSE;
544    }
545
546    $parent_id = $this->structure[$node_id]['parent'];
547    $slot_id = $this->structure[$node_id]['slot'];
548
549    if ($parent_id === NULL) {
550      $key = \array_search($node_id, $this->root, TRUE);
551
552      if ($key === FALSE) {
553        return FALSE;
554      }
555      \array_splice($this->root, (int) $key, 1);
556
557      return TRUE;
558    }
559
560    if ($slot_id === NULL || !isset($this->structure[$parent_id]['slots'][$slot_id])) {
561      return FALSE;
562    }
563
564    $child_ids = &$this->structure[$parent_id]['slots'][$slot_id];
565
566    if (!\is_array($child_ids)) {
567      return FALSE;
568    }
569    $key = \array_search($node_id, $child_ids, TRUE);
570
571    if ($key !== FALSE) {
572      \array_splice($child_ids, (int) $key, 1);
573
574      return TRUE;
575    }
576
577    return FALSE;
578  }
579
580  /**
581   * Recursively remove node and data.
582   *
583   * @param string $node_id
584   *   The node ID.
585   */
586  private function recursiveRemove(string $node_id): void {
587    if (!isset($this->structure[$node_id])) {
588      return;
589    }
590
591    foreach ($this->structure[$node_id]['slots'] as $child_ids) {
592      foreach ($child_ids as $child_id) {
593        $this->recursiveRemove($child_id);
594      }
595    }
596    unset($this->nodes[$node_id], $this->structure[$node_id]);
597  }
598
599  /**
600   * Check if a node is a descendant of another.
601   *
602   * @param string $node_id
603   *   The node ID to check.
604   * @param string $potential_ancestor_id
605   *   The potential ancestor ID.
606   *
607   * @return bool
608   *   TRUE if descendant.
609   */
610  private function isDescendant(string $node_id, string $potential_ancestor_id): bool {
611    $current_parent = $this->getParentId($node_id);
612
613    while ($current_parent !== NULL) {
614      if ($current_parent === $potential_ancestor_id) {
615        return TRUE;
616      }
617      $current_parent = $this->getParentId($current_parent);
618    }
619
620    return FALSE;
621  }
622
623  /**
624   * Get source plugin instance.
625   *
626   * @param string $source_id
627   *   The source plugin ID.
628   * @param array $source_configuration
629   *   The source configuration.
630   *
631   * @return \Drupal\ui_patterns\SourceInterface|null
632   *   The source plugin instance or NULL.
633   */
634  private function getSourcePlugin(string $source_id, array $source_configuration): ?SourceInterface {
635    try {
636      $plugin = $this->getSourceManager()->createInstance($source_id, ['settings' => $source_configuration]);
637
638      return $plugin instanceof SourceInterface ? $plugin : NULL;
639    }
640    catch (\Exception $e) {
641      // phpcs:ignore -- lazy-init required; see getSourceManager() docblock.
642      \Drupal::logger('display_builder')->warning('SourceTree: failed to instantiate source plugin %id: @message', ['%id' => $source_id, '@message' => $e->getMessage()]);
643
644      return NULL;
645    }
646  }
647
648  /**
649   * Get source plugin class.
650   *
651   * @param string $source_id
652   *   The source plugin ID.
653   *
654   * @return string|null
655   *   The plugin class or NULL.
656   */
657  private function getPluginClass(string $source_id): ?string {
658    if (\array_key_exists($source_id, $this->pluginClassCache)) {
659      return $this->pluginClassCache[$source_id];
660    }
661
662    try {
663      $definition = $this->getSourceManager()->getDefinition($source_id);
664      $this->pluginClassCache[$source_id] = $definition['class'] ?? NULL;
665    }
666    catch (\Exception $e) {
667      // phpcs:ignore -- lazy-init required; see getSourceManager() docblock.
668      \Drupal::logger('display_builder')->warning('SourceTree: failed to get definition for source plugin %id: @message', ['%id' => $source_id, '@message' => $e->getMessage()]);
669      $this->pluginClassCache[$source_id] = NULL;
670    }
671
672    return $this->pluginClassCache[$source_id];
673  }
674
675  /**
676   * Gets the UI Patterns source plugin manager.
677   *
678   * SourceTree is a plain value object instantiated as new SourceTree() from
679   * entity and plugin base classes where constructor injection is unavailable.
680   * The lazy-init fallback using \Drupal::service() is intentional and the
681   * only viable pattern for those call sites.
682   *
683   * @return \Drupal\Component\Plugin\PluginManagerInterface
684   *   The source plugin manager.
685   */
686  private function getSourceManager(): PluginManagerInterface {
687    if ($this->sourceManager === NULL) {
688      // phpcs:ignore -- lazy-init required; see method docblock.
689      $this->sourceManager = \Drupal::service('plugin.manager.ui_patterns_source');
690    }
691
692    return $this->sourceManager;
693  }
694
695}