Treewalker Laravel Package

Getting Started

Minimal Setup

1. Installation:

   composer require lukascivil/treewalker
   

   Add to composer.json if not using autoloading:

   "autoload": {
       "psr-4": {
           "App\\": "app/",
           "LukasCivil\\TreeWalker\\": "vendor/lukascivil/treewalker/src/"
       }
   }
   

   Run composer dump-autoload.

2. First Use Case: Traverse a nested array (e.g., Laravel's route collection or a category tree):

   use LukasCivil\TreeWalker\TreeWalker;
   
   $tree = [
       'id' => 1,
       'name' => 'Root',
       'children' => [
           ['id' => 2, 'name' => 'Child 1'],
           ['id' => 3, 'name' => 'Child 2', 'children' => [...]]
       ]
   ];
   
   $walker = new TreeWalker($tree);
   $walker->walk(function ($node) {
       // Process each node (e.g., log, transform, or filter)
       echo $node['name'] . "\n";
   });
   

Where to Look First

• README: Covers basic usage, node structure requirements, and examples.
• TreeWalker class: Core class with methods like walk(), walkRecursive(), and filter().
• TreeNode class: Understands how nodes are structured (must have children key for recursion).

Implementation Patterns

Common Workflows

1. Flattening Trees: Convert hierarchical data to a flat array for processing (e.g., for Eloquent models):

   $flatNodes = [];
   $walker->walkRecursive(function ($node) use (&$flatNodes) {
       $flatNodes[] = $node;
   });
   

2. Filtering Nodes: Prune or select nodes based on conditions (e.g., active categories):

   $activeNodes = $walker->filter(function ($node) {
       return $node['is_active'] ?? true;
   });
   

3. Transforming Trees: Modify node data during traversal (e.g., add slugs or IDs):

   $walker->walk(function ($node) {
       $node['slug'] = Str::slug($node['name']);
   });
   

4. Integration with Laravel:

   • Eloquent Relationships: Useful for nested hasMany/belongsTo structures.

     $categories = Category::with('children')->get();
     $walker = new TreeWalker($categories->toArray());
     

   • Blade Views: Render hierarchical data (e.g., navigation menus):

     @foreach($walker->walkRecursive() as $node)
         <li>{{ $node['name'] }}</li>
     @endforeach
     

5. Bulk Operations: Update multiple nodes at once (e.g., incrementing a counter):

   $walker->walk(function ($node) {
       $node['view_count'] = ($node['view_count'] ?? 0) + 1;
   });
   

Advanced Patterns

• Custom Node Classes: Extend TreeNode to add methods or validation:

  class CategoryNode extends TreeNode {
      public function isPublished() {
          return $this->data['published_at'] !== null;
      }
  }
  

  Usage:

  $walker = new TreeWalker($categories, CategoryNode::class);
  

• Depth Tracking: Use closures to track recursion depth (e.g., for indentation):

  $walker->walkRecursive(function ($node, $depth) {
      echo str_repeat('  ', $depth) . $node['name'] . "\n";
  });
  

• Lazy Loading: Load children on-demand (e.g., for large trees):

  $walker = new TreeWalker($rootNode);
  $walker->walk(function ($node) {
      if (!isset($node['children'])) {
          $node['children'] = $this->loadChildren($node['id']);
      }
  });
  

Gotchas and Tips

Pitfalls

1. Node Structure Requirements:

   • Nodes must have a children key (even if empty []).
   • Fix: Normalize data before passing to TreeWalker:

     $tree = array_map(function ($node) {
         return array_merge($node, ['children' => []]);
     }, $rawData);
     

2. Mutable References:

   • Closures in walk() modify nodes by reference. Unexpected side effects can occur if not handled carefully.
   • Tip: Clone nodes if immutability is needed:

     $walker->walk(function ($node) {
         $node = array_merge($node); // Create a copy
         // Safe to modify
     });
     

3. Performance with Large Trees:

   • Deep recursion can hit PHP's stack limit or memory ceiling.
   • Fix: Use walkRecursive() with depth limits or iterative approaches:

     $walker->walkRecursive(function ($node, $depth) {
         if ($depth > 10) return; // Skip deep nodes
     });
     

4. Circular References:

   • Trees with circular references (e.g., parent-child loops) will cause infinite recursion.
   • Fix: Add cycle detection:

     $visited = [];
     $walker->walk(function ($node) use (&$visited) {
         if (in_array($node['id'], $visited)) return;
         $visited[] = $node['id'];
         // Process node
     });
     

Debugging Tips

• Verify Node Structure: Use var_dump($node) in closures to inspect data shape.
• Log Traversal Path: Track the path to a node for debugging:

  $path = [];
  $walker->walkRecursive(function ($node) use (&$path) {
      $path[] = $node['id'];
      // Debug $path if needed
  });
  

• Test Edge Cases:
  • Empty trees: $walker->walk(function ($node) {}) on [].
  • Single-node trees: $tree = ['id' => 1, 'children' => []].

Extension Points

1. Custom Walkers: Extend TreeWalker for domain-specific logic:

   class CategoryTreeWalker extends TreeWalker {
       public function getPublished() {
           return $this->filter(function ($node) {
               return $node['published'] ?? false;
           });
       }
   }
   

2. Event-Based Traversal: Use events (e.g., Laravel's dispatch) to trigger actions during traversal:

   $walker->walk(function ($node) {
       event(new NodeProcessed($node));
   });
   

3. Hybrid Data Structures: Combine with other libraries (e.g., spatie/array-to-object) for OOP traversal:

   use Spatie\ArrayToObject\ArrayToObject;
   
   $walker = new TreeWalker(ArrayToObject::convert($tree));
   $walker->walk(function ($node) {
       $node->slug = Str::slug($node->name);
   });
   

4. Serialization: Convert trees to/from JSON or other formats:

   $serialized = json_encode($walker->walkRecursive());
   $tree = json_decode($serialized, true);
   

Configuration Quirks

• Default Node Class: Override the default TreeNode class via constructor:

  $walker = new TreeWalker($tree, CustomNode::class);
  

• Recursion Limit: PHP's xdebug.max_nesting_level may need adjustment for deep trees:

  xdebug.max_nesting_level=500