1<?php
2/**
3 * A class for displaying various tree-like structures.
4 *
5 * Extend the Walker class to use it, see examples below. Child classes
6 * do not need to implement all of the abstract methods in the class. The child
7 * only needs to implement the methods that are needed.
8 *
9 * @since 2.1.0
10 *
11 * @package WordPress
12 * @abstract
13 */
14class Walker {
15	/**
16	 * What the class handles.
17	 *
18	 * @since 2.1.0
19	 * @var string
20	 */
21	public $tree_type;
22
23	/**
24	 * DB fields to use.
25	 *
26	 * @since 2.1.0
27	 * @var array
28	 */
29	public $db_fields;
30
31	/**
32	 * Max number of pages walked by the paged walker
33	 *
34	 * @since 2.7.0
35	 * @var int
36	 */
37	public $max_pages = 1;
38
39	/**
40	 * Whether the current element has children or not.
41	 *
42	 * To be used in start_el().
43	 *
44	 * @since 4.0.0
45	 * @var bool
46	 */
47	public $has_children;
48
49	/**
50	 * Starts the list before the elements are added.
51	 *
52	 * The $args parameter holds additional values that may be used with the child
53	 * class methods. This method is called at the start of the output list.
54	 *
55	 * @since 2.1.0
56	 * @abstract
57	 *
58	 * @param string $output Used to append additional content (passed by reference).
59	 * @param int    $depth  Depth of the item.
60	 * @param array  $args   An array of additional arguments.
61	 */
62	public function start_lvl( &$output, $depth = 0, $args = array() ) {}
63
64	/**
65	 * Ends the list of after the elements are added.
66	 *
67	 * The $args parameter holds additional values that may be used with the child
68	 * class methods. This method finishes the list at the end of output of the elements.
69	 *
70	 * @since 2.1.0
71	 * @abstract
72	 *
73	 * @param string $output Used to append additional content (passed by reference).
74	 * @param int    $depth  Depth of the item.
75	 * @param array  $args   An array of additional arguments.
76	 */
77	public function end_lvl( &$output, $depth = 0, $args = array() ) {}
78
79	/**
80	 * Start the element output.
81	 *
82	 * The $args parameter holds additional values that may be used with the child
83	 * class methods. Includes the element output also.
84	 *
85	 * @since 2.1.0
86	 * @abstract
87	 *
88	 * @param string $output            Used to append additional content (passed by reference).
89	 * @param object $object            The data object.
90	 * @param int    $depth             Depth of the item.
91	 * @param array  $args              An array of additional arguments.
92	 * @param int    $current_object_id ID of the current item.
93	 */
94	public function start_el( &$output, $object, $depth = 0, $args = array(), $current_object_id = 0 ) {}
95
96	/**
97	 * Ends the element output, if needed.
98	 *
99	 * The $args parameter holds additional values that may be used with the child class methods.
100	 *
101	 * @since 2.1.0
102	 * @abstract
103	 *
104	 * @param string $output Used to append additional content (passed by reference).
105	 * @param object $object The data object.
106	 * @param int    $depth  Depth of the item.
107	 * @param array  $args   An array of additional arguments.
108	 */
109	public function end_el( &$output, $object, $depth = 0, $args = array() ) {}
110
111	/**
112	 * Traverse elements to create list from elements.
113	 *
114	 * Display one element if the element doesn't have any children otherwise,
115	 * display the element and its children. Will only traverse up to the max
116	 * depth and no ignore elements under that depth. It is possible to set the
117	 * max depth to include all depths, see walk() method.
118	 *
119	 * This method should not be called directly, use the walk() method instead.
120	 *
121	 * @since 2.5.0
122	 *
123	 * @param object $element           Data object.
124	 * @param array  $children_elements List of elements to continue traversing (passed by reference).
125	 * @param int    $max_depth         Max depth to traverse.
126	 * @param int    $depth             Depth of current element.
127	 * @param array  $args              An array of arguments.
128	 * @param string $output            Used to append additional content (passed by reference).
129	 */
130	public function display_element( $element, &$children_elements, $max_depth, $depth, $args, &$output ) {
131		if ( ! $element ) {
132			return;
133		}
134
135		$id_field = $this->db_fields['id'];
136		$id       = $element->$id_field;
137
138		// Display this element.
139		$this->has_children = ! empty( $children_elements[ $id ] );
140		if ( isset( $args[0] ) && is_array( $args[0] ) ) {
141			$args[0]['has_children'] = $this->has_children; // Back-compat.
142		}
143
144		$this->start_el( $output, $element, $depth, ...array_values( $args ) );
145
146		// Descend only when the depth is right and there are children for this element.
147		if ( ( 0 == $max_depth || $max_depth > $depth + 1 ) && isset( $children_elements[ $id ] ) ) {
148
149			foreach ( $children_elements[ $id ] as $child ) {
150
151				if ( ! isset( $newlevel ) ) {
152					$newlevel = true;
153					// Start the child delimiter.
154					$this->start_lvl( $output, $depth, ...array_values( $args ) );
155				}
156				$this->display_element( $child, $children_elements, $max_depth, $depth + 1, $args, $output );
157			}
158			unset( $children_elements[ $id ] );
159		}
160
161		if ( isset( $newlevel ) && $newlevel ) {
162			// End the child delimiter.
163			$this->end_lvl( $output, $depth, ...array_values( $args ) );
164		}
165
166		// End this element.
167		$this->end_el( $output, $element, $depth, ...array_values( $args ) );
168	}
169
170	/**
171	 * Display array of elements hierarchically.
172	 *
173	 * Does not assume any existing order of elements.
174	 *
175	 * $max_depth = -1 means flatly display every element.
176	 * $max_depth = 0 means display all levels.
177	 * $max_depth > 0 specifies the number of display levels.
178	 *
179	 * @since 2.1.0
180	 * @since 5.3.0 Formalized the existing `...$args` parameter by adding it
181	 *              to the function signature.
182	 *
183	 * @param array $elements  An array of elements.
184	 * @param int   $max_depth The maximum hierarchical depth.
185	 * @param mixed ...$args   Optional additional arguments.
186	 * @return string The hierarchical item output.
187	 */
188	public function walk( $elements, $max_depth, ...$args ) {
189		$output = '';
190
191		// Invalid parameter or nothing to walk.
192		if ( $max_depth < -1 || empty( $elements ) ) {
193			return $output;
194		}
195
196		$parent_field = $this->db_fields['parent'];
197
198		// Flat display.
199		if ( -1 == $max_depth ) {
200			$empty_array = array();
201			foreach ( $elements as $e ) {
202				$this->display_element( $e, $empty_array, 1, 0, $args, $output );
203			}
204			return $output;
205		}
206
207		/*
208		 * Need to display in hierarchical order.
209		 * Separate elements into two buckets: top level and children elements.
210		 * Children_elements is two dimensional array, eg.
211		 * Children_elements[10][] contains all sub-elements whose parent is 10.
212		 */
213		$top_level_elements = array();
214		$children_elements  = array();
215		foreach ( $elements as $e ) {
216			if ( empty( $e->$parent_field ) ) {
217				$top_level_elements[] = $e;
218			} else {
219				$children_elements[ $e->$parent_field ][] = $e;
220			}
221		}
222
223		/*
224		 * When none of the elements is top level.
225		 * Assume the first one must be root of the sub elements.
226		 */
227		if ( empty( $top_level_elements ) ) {
228
229			$first = array_slice( $elements, 0, 1 );
230			$root  = $first[0];
231
232			$top_level_elements = array();
233			$children_elements  = array();
234			foreach ( $elements as $e ) {
235				if ( $root->$parent_field == $e->$parent_field ) {
236					$top_level_elements[] = $e;
237				} else {
238					$children_elements[ $e->$parent_field ][] = $e;
239				}
240			}
241		}
242
243		foreach ( $top_level_elements as $e ) {
244			$this->display_element( $e, $children_elements, $max_depth, 0, $args, $output );
245		}
246
247		/*
248		 * If we are displaying all levels, and remaining children_elements is not empty,
249		 * then we got orphans, which should be displayed regardless.
250		 */
251		if ( ( 0 == $max_depth ) && count( $children_elements ) > 0 ) {
252			$empty_array = array();
253			foreach ( $children_elements as $orphans ) {
254				foreach ( $orphans as $op ) {
255					$this->display_element( $op, $empty_array, 1, 0, $args, $output );
256				}
257			}
258		}
259
260		return $output;
261	}
262
263	/**
264	 * paged_walk() - produce a page of nested elements
265	 *
266	 * Given an array of hierarchical elements, the maximum depth, a specific page number,
267	 * and number of elements per page, this function first determines all top level root elements
268	 * belonging to that page, then lists them and all of their children in hierarchical order.
269	 *
270	 * $max_depth = 0 means display all levels.
271	 * $max_depth > 0 specifies the number of display levels.
272	 *
273	 * @since 2.7.0
274	 * @since 5.3.0 Formalized the existing `...$args` parameter by adding it
275	 *              to the function signature.
276	 *
277	 * @param array $elements
278	 * @param int   $max_depth The maximum hierarchical depth.
279	 * @param int   $page_num  The specific page number, beginning with 1.
280	 * @param int   $per_page
281	 * @param mixed ...$args   Optional additional arguments.
282	 * @return string XHTML of the specified page of elements
283	 */
284	public function paged_walk( $elements, $max_depth, $page_num, $per_page, ...$args ) {
285		if ( empty( $elements ) || $max_depth < -1 ) {
286			return '';
287		}
288
289		$output = '';
290
291		$parent_field = $this->db_fields['parent'];
292
293		$count = -1;
294		if ( -1 == $max_depth ) {
295			$total_top = count( $elements );
296		}
297		if ( $page_num < 1 || $per_page < 0 ) {
298			// No paging.
299			$paging = false;
300			$start  = 0;
301			if ( -1 == $max_depth ) {
302				$end = $total_top;
303			}
304			$this->max_pages = 1;
305		} else {
306			$paging = true;
307			$start  = ( (int) $page_num - 1 ) * (int) $per_page;
308			$end    = $start + $per_page;
309			if ( -1 == $max_depth ) {
310				$this->max_pages = ceil( $total_top / $per_page );
311			}
312		}
313
314		// Flat display.
315		if ( -1 == $max_depth ) {
316			if ( ! empty( $args[0]['reverse_top_level'] ) ) {
317				$elements = array_reverse( $elements );
318				$oldstart = $start;
319				$start    = $total_top - $end;
320				$end      = $total_top - $oldstart;
321			}
322
323			$empty_array = array();
324			foreach ( $elements as $e ) {
325				$count++;
326				if ( $count < $start ) {
327					continue;
328				}
329				if ( $count >= $end ) {
330					break;
331				}
332				$this->display_element( $e, $empty_array, 1, 0, $args, $output );
333			}
334			return $output;
335		}
336
337		/*
338		 * Separate elements into two buckets: top level and children elements.
339		 * Children_elements is two dimensional array, e.g.
340		 * $children_elements[10][] contains all sub-elements whose parent is 10.
341		 */
342		$top_level_elements = array();
343		$children_elements  = array();
344		foreach ( $elements as $e ) {
345			if ( empty( $e->$parent_field ) ) {
346				$top_level_elements[] = $e;
347			} else {
348				$children_elements[ $e->$parent_field ][] = $e;
349			}
350		}
351
352		$total_top = count( $top_level_elements );
353		if ( $paging ) {
354			$this->max_pages = ceil( $total_top / $per_page );
355		} else {
356			$end = $total_top;
357		}
358
359		if ( ! empty( $args[0]['reverse_top_level'] ) ) {
360			$top_level_elements = array_reverse( $top_level_elements );
361			$oldstart           = $start;
362			$start              = $total_top - $end;
363			$end                = $total_top - $oldstart;
364		}
365		if ( ! empty( $args[0]['reverse_children'] ) ) {
366			foreach ( $children_elements as $parent => $children ) {
367				$children_elements[ $parent ] = array_reverse( $children );
368			}
369		}
370
371		foreach ( $top_level_elements as $e ) {
372			$count++;
373
374			// For the last page, need to unset earlier children in order to keep track of orphans.
375			if ( $end >= $total_top && $count < $start ) {
376					$this->unset_children( $e, $children_elements );
377			}
378
379			if ( $count < $start ) {
380				continue;
381			}
382
383			if ( $count >= $end ) {
384				break;
385			}
386
387			$this->display_element( $e, $children_elements, $max_depth, 0, $args, $output );
388		}
389
390		if ( $end >= $total_top && count( $children_elements ) > 0 ) {
391			$empty_array = array();
392			foreach ( $children_elements as $orphans ) {
393				foreach ( $orphans as $op ) {
394					$this->display_element( $op, $empty_array, 1, 0, $args, $output );
395				}
396			}
397		}
398
399		return $output;
400	}
401
402	/**
403	 * Calculates the total number of root elements.
404	 *
405	 * @since 2.7.0
406	 *
407	 * @param array $elements Elements to list.
408	 * @return int Number of root elements.
409	 */
410	public function get_number_of_root_elements( $elements ) {
411		$num          = 0;
412		$parent_field = $this->db_fields['parent'];
413
414		foreach ( $elements as $e ) {
415			if ( empty( $e->$parent_field ) ) {
416				$num++;
417			}
418		}
419		return $num;
420	}
421
422	/**
423	 * Unset all the children for a given top level element.
424	 *
425	 * @since 2.7.0
426	 *
427	 * @param object $e
428	 * @param array  $children_elements
429	 */
430	public function unset_children( $e, &$children_elements ) {
431		if ( ! $e || ! $children_elements ) {
432			return;
433		}
434
435		$id_field = $this->db_fields['id'];
436		$id       = $e->$id_field;
437
438		if ( ! empty( $children_elements[ $id ] ) && is_array( $children_elements[ $id ] ) ) {
439			foreach ( (array) $children_elements[ $id ] as $child ) {
440				$this->unset_children( $child, $children_elements );
441			}
442		}
443
444		unset( $children_elements[ $id ] );
445	}
446
447}
448