23529067023

Committed 25 Mar 2026 07:03AM UTC coverage: 92.794% (-0.02%) from 92.815%

Build # 23529067023

Build Type

Pull #1660

github

Committed by

web-flow

Commit Message

Merge 529180734 into 7a4fa99d1

Pull Request Pull Request #1660: Fix SlotMap::offsetUnset() corrupting mappings when unsetting a slot in a gap

Coverage Stats

1 of 1 new or added line in 1 file covered. (100.0%)

2 existing lines in 1 file now uncovered.

8357 of 9006 relevant lines covered (92.79%)

114.13 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

95.8

/src/Cluster/SlotMap.php

<?php

/*
 * This file is part of the Predis package.
 *
 * (c) 2009-2020 Daniele Alessandri
 * (c) 2021-2026 Till Krüss
 *
 * For the full copyright and license information, please view the LICENSE
 * file that was distributed with this source code.
 */

namespace Predis\Cluster;

use ArrayAccess;
use ArrayIterator;
use Countable;
use IteratorAggregate;
use OutOfBoundsException;
use Predis\Connection\NodeConnectionInterface;
use ReturnTypeWillChange;
use Traversable;

/**
 * Compact slot map for redis-cluster.
 */
class SlotMap implements ArrayAccess, IteratorAggregate, Countable
{
    /**
     * Slot ranges list.
     *
     * @var SlotRange[]
     */
    private $slotRanges = [];

    /**
     * Checks if the given slot is valid.
     *
     * @param int $slot Slot index.
     *
     * @return bool
     */
    public static function isValid($slot)
    {
        return $slot >= 0 && $slot <= SlotRange::MAX_SLOTS;
    }

    /**
     * Checks if the given slot range is valid.
     *
     * @param int $first Initial slot of the range.
     * @param int $last  Last slot of the range.
     *
     * @return bool
     */
    public static function isValidRange($first, $last)
    {
        return SlotRange::isValidRange($first, $last);
    }

    /**
     * Resets the slot map.
     */
    public function reset()
    {
        $this->slotRanges = [];
    }

    /**
     * Checks if the slot map is empty.
     *
     * @return bool
     */
    public function isEmpty()
    {
        return empty($this->slotRanges);
    }

    /**
     * Returns the current slot map as a dictionary of $slot => $node.
     *
     * The order of the slots in the dictionary is not guaranteed.
     *
     * @return array
     */
    public function toArray()
    {
        return array_reduce(
            $this->slotRanges,
            static function ($carry, $slotRange) {
                return $carry + $slotRange->toArray();
            },
            []
        );
    }

    /**
     * Returns the list of unique nodes in the slot map.
     *
     * @return array
     */
    public function getNodes()
    {
        return array_unique(array_map(
            static function ($slotRange) {
                return $slotRange->getConnection();
            },
            $this->slotRanges
        ));
    }

    /**
     * Returns the list of slot ranges.
     *
     * @return SlotRange[]
     */
    public function getSlotRanges()
    {
        return $this->slotRanges;
    }

    /**
     * Assigns the specified slot range to a node.
     *
     * @param int                            $first      Initial slot of the range.
     * @param int                            $last       Last slot of the range.
     * @param NodeConnectionInterface|string $connection ID or connection instance.
     *
     * @throws OutOfBoundsException
     */
    public function setSlots($first, $last, $connection)
    {
        if (!static::isValidRange($first, $last)) {
            throw new OutOfBoundsException("Invalid slot range $first-$last for `$connection`");
        }

        $targetSlotRange = new SlotRange($first, $last, (string) $connection);

        // Get gaps of slot ranges list.
        $gaps = $this->getGaps($this->slotRanges);

        $results = $this->slotRanges;

        foreach ($gaps as $gap) {
            if (!$gap->hasIntersectionWith($targetSlotRange)) {
                continue;
            }

            // Get intersection of the gap and target slot range.
            $results[] = new SlotRange(
                max($gap->getStart(), $targetSlotRange->getStart()),
                min($gap->getEnd(), $targetSlotRange->getEnd()),
                $targetSlotRange->getConnection()
            );
        }

        $this->sortSlotRanges($results);

        $results = $this->compactSlotRanges($results);

        $this->slotRanges = $results;
    }

    /**
     * Returns the specified slot range.
     *
     * @param int $first Initial slot of the range.
     * @param int $last  Last slot of the range.
     *
     * @return array<int, string>
     */
    public function getSlots($first, $last)
    {
        if (!static::isValidRange($first, $last)) {
            throw new OutOfBoundsException("Invalid slot range $first-$last");
        }

        $placeHolder = new NullSlotRange($first, $last);

        $intersections = [];
        foreach ($this->slotRanges as $slotRange) {
            if (!$placeHolder->hasIntersectionWith($slotRange)) {
                continue;
            }

            $intersections[] = new SlotRange(
                max($placeHolder->getStart(), $slotRange->getStart()),
                min($placeHolder->getEnd(), $slotRange->getEnd()),
                $slotRange->getConnection()
            );
        }

        return array_reduce(
            $intersections,
            static function ($carry, $slotRange) {
                return $carry + $slotRange->toArray();
            },
            []
        );
    }

    /**
     * Checks if the specified slot is assigned.
     *
     * @param int $slot Slot index.
     *
     * @return bool
     */
    #[ReturnTypeWillChange]
    public function offsetExists($slot)
    {
        return $this->findRangeBySlot($slot) !== false;
    }

    /**
     * Returns the node assigned to the specified slot.
     *
     * @param int $slot Slot index.
     *
     * @return string|null
     */
    #[ReturnTypeWillChange]
    public function offsetGet($slot)
    {
        $found = $this->findRangeBySlot($slot);

        return $found ? $found->getConnection() : null;
    }

    /**
     * Assigns the specified slot to a node.
     *
     * @param int                            $slot       Slot index.
     * @param NodeConnectionInterface|string $connection ID or connection instance.
     *
     * @return void
     */
    #[ReturnTypeWillChange]
    public function offsetSet($slot, $connection)
    {
        if (!static::isValid($slot)) {
            throw new OutOfBoundsException("Invalid slot $slot for `$connection`");
        }

        $this->offsetUnset($slot);
        $this->setSlots($slot, $slot, $connection);
    }

    /**
     * Returns the node assigned to the specified slot.
     *
     * @param int $slot Slot index.
     *
     * @return void
     */
    #[ReturnTypeWillChange]
    public function offsetUnset($slot)
    {
        if (!static::isValid($slot)) {
            throw new OutOfBoundsException("Invalid slot $slot");
        }

        $results = [];
        foreach ($this->slotRanges as $slotRange) {
            if (!$slotRange->hasSlot($slot)) {
                $results[] = $slotRange;
                continue;
            }

            if (static::isValidRange($slotRange->getStart(), $slot - 1)) {
                $results[] = new SlotRange($slotRange->getStart(), $slot - 1, $slotRange->getConnection());
            }

            if (static::isValidRange($slot + 1, $slotRange->getEnd())) {
                $results[] = new SlotRange($slot + 1, $slotRange->getEnd(), $slotRange->getConnection());
            }
        }

        $this->slotRanges = $results;
    }

    /**
     * Returns the current number of assigned slots.
     *
     * @return int
     */
    #[ReturnTypeWillChange]
    public function count()
    {
        return array_sum(array_map(
            static function ($slotRange) {
                return $slotRange->count();
            },
            $this->slotRanges
        ));
    }

    /**
     * Returns an iterator over the slot map.
     *
     * @return Traversable<int, string>
     */
    #[ReturnTypeWillChange]
    public function getIterator()
    {
        return new ArrayIterator($this->toArray());
    }

    /**
     * Find the slot range which contains the specific slot index.
     *
     * @param int $slot Slot index.
     *
     * @return SlotRange|false The slot range object or false if not found.
     */
    protected function findRangeBySlot(int $slot)
    {
        foreach ($this->slotRanges as $slotRange) {
            if ($slotRange->hasSlot($slot)) {
                return $slotRange;
            }
        }

        return false;
    }

    /**
     * Get gaps between sorted slot ranges with NullSlotRange object.
     *
     * @param SlotRange[] $slotRanges
     *
     * @return SlotRange[]
     */
    protected function getGaps(array $slotRanges)
    {
        if (empty($slotRanges)) {
            return [
                new NullSlotRange(0, SlotRange::MAX_SLOTS),
            ];
        }
        $gaps = [];
        $count = count($slotRanges);
        $i = 0;
        foreach ($slotRanges as $key => $slotRange) {
            $start = $slotRange->getStart();
            $end = $slotRange->getEnd();
            if (static::isValidRange($i, $start - 1)) {
                $gaps[] = new NullSlotRange($i, $start - 1);
            }

            $i = $end + 1;

            if ($key === $count - 1) {
                if (static::isValidRange($i, SlotRange::MAX_SLOTS)) {
                    $gaps[] = new NullSlotRange($i, SlotRange::MAX_SLOTS);
                }
            }
        }

        return $gaps;
    }

    /**
     * Sort slot ranges by start index.
     *
     * @param SlotRange[] $slotRanges
     *
     * @return void
     */
    protected function sortSlotRanges(array &$slotRanges)
    {
        usort(
            $slotRanges,
            static function (SlotRange $a, SlotRange $b) {
                if ($a->getStart() == $b->getStart()) {
                    return 0;
                }

                return $a->getStart() < $b->getStart() ? -1 : 1;
            }
        );
    }

    /**
     * Compact adjacent slot ranges with the same connection.
     *
     * @param SlotRange[] $slotRanges
     *
     * @return SlotRange[]
     */
    protected function compactSlotRanges(array $slotRanges)
    {
        if (empty($slotRanges)) {
            return [];
        }

        $compacted = [];
        $count = count($slotRanges);
        $i = 0;
        $carry = $slotRanges[0];
        while ($i < $count) {
            $next = $slotRanges[$i + 1] ?? null;
            if (
                !is_null($next)
                && ($carry->getEnd() + 1) === $next->getStart()
                && $carry->getConnection() === $next->getConnection()
            ) {
                $carry = new SlotRange($carry->getStart(), $next->getEnd(), $carry->getConnection());
            } else {
                $compacted[] = $carry;
                $carry = $next;
            }
            $i++;
        }

        return array_values($compacted);
    }
}

1	<?php
2
3	/*
4	* This file is part of the Predis package.
5	*
6	* (c) 2009-2020 Daniele Alessandri
7	* (c) 2021-2026 Till Krüss
8	*
9	* For the full copyright and license information, please view the LICENSE
10	* file that was distributed with this source code.
11	*/
12
13	namespace Predis\Cluster;
14
15	use ArrayAccess;
16	use ArrayIterator;
17	use Countable;
18	use IteratorAggregate;
19	use OutOfBoundsException;
20	use Predis\Connection\NodeConnectionInterface;
21	use ReturnTypeWillChange;
22	use Traversable;
23
24	/**
25	* Compact slot map for redis-cluster.
26	*/
27	class SlotMap implements ArrayAccess, IteratorAggregate, Countable
28	{
29	/**
30	* Slot ranges list.
31	*
32	* @var SlotRange[]
33	*/
34	private $slotRanges = [];
35
36	/**
37	* Checks if the given slot is valid.
38	*
39	* @param int $slot Slot index.
40	*
41	* @return bool
42	*/
43	public static function isValid($slot)	64✔
44	{
45	return $slot >= 0 && $slot <= SlotRange::MAX_SLOTS;	64✔
46	}
47
48	/**
49	* Checks if the given slot range is valid.
50	*
51	* @param int $first Initial slot of the range.
52	* @param int $last Last slot of the range.
53	*
54	* @return bool
55	*/
56	public static function isValidRange($first, $last)	46✔
57	{
58	return SlotRange::isValidRange($first, $last);	46✔
59	}
60
61	/**
62	* Resets the slot map.
63	*/
64	public function reset()	76✔
65	{
66	$this->slotRanges = [];	76✔
67	}
68
69	/**
70	* Checks if the slot map is empty.
71	*
72	* @return bool
73	*/
74	public function isEmpty()	60✔
75	{
76	return empty($this->slotRanges);	60✔
77	}
78
79	/**
80	* Returns the current slot map as a dictionary of $slot => $node.
81	*
82	* The order of the slots in the dictionary is not guaranteed.
83	*
84	* @return array
85	*/
86	public function toArray()	10✔
87	{
88	return array_reduce(	10✔
89	$this->slotRanges,	10✔
90	static function ($carry, $slotRange) {	10✔
91	return $carry + $slotRange->toArray();	9✔
92	},	10✔
93	[]	10✔
94	);	10✔
95	}
96
97	/**
98	* Returns the list of unique nodes in the slot map.
99	*
100	* @return array
101	*/
102	public function getNodes()	4✔
103	{
104	return array_unique(array_map(	4✔
105	static function ($slotRange) {	4✔
106	return $slotRange->getConnection();	3✔
107	},	4✔
108	$this->slotRanges	4✔
109	));	4✔
110	}
111
112	/**
113	* Returns the list of slot ranges.
114	*
115	* @return SlotRange[]
116	*/
117	public function getSlotRanges()	×
118	{
119	return $this->slotRanges;	×
120	}
121
122	/**
123	* Assigns the specified slot range to a node.
124	*
125	* @param int $first Initial slot of the range.
126	* @param int $last Last slot of the range.
127	* @param NodeConnectionInterface\|string $connection ID or connection instance.
128	*
129	* @throws OutOfBoundsException
130	*/
131	public function setSlots($first, $last, $connection)	42✔
132	{
133	if (!static::isValidRange($first, $last)) {	42✔
134	throw new OutOfBoundsException("Invalid slot range $first-$last for `$connection`");	1✔
135	}
136
137	$targetSlotRange = new SlotRange($first, $last, (string) $connection);	41✔
138
139	// Get gaps of slot ranges list.
140	$gaps = $this->getGaps($this->slotRanges);	41✔
141
142	$results = $this->slotRanges;	41✔
143
144	foreach ($gaps as $gap) {	41✔
145	if (!$gap->hasIntersectionWith($targetSlotRange)) {	41✔
146	continue;	5✔
147	}
148
149	// Get intersection of the gap and target slot range.
150	$results[] = new SlotRange(	41✔
151	max($gap->getStart(), $targetSlotRange->getStart()),	41✔
152	min($gap->getEnd(), $targetSlotRange->getEnd()),	41✔
153	$targetSlotRange->getConnection()	41✔
154	);	41✔
155	}
156
157	$this->sortSlotRanges($results);	41✔
158
159	$results = $this->compactSlotRanges($results);	41✔
160
161	$this->slotRanges = $results;	41✔
162	}
163
164	/**
165	* Returns the specified slot range.
166	*
167	* @param int $first Initial slot of the range.
168	* @param int $last Last slot of the range.
169	*
170	* @return array<int, string>
171	*/
172	public function getSlots($first, $last)	4✔
173	{
174	if (!static::isValidRange($first, $last)) {	4✔
175	throw new OutOfBoundsException("Invalid slot range $first-$last");	1✔
176	}
177
178	$placeHolder = new NullSlotRange($first, $last);	3✔
179
180	$intersections = [];	3✔
181	foreach ($this->slotRanges as $slotRange) {	3✔
182	if (!$placeHolder->hasIntersectionWith($slotRange)) {	2✔
183	continue;	1✔
184	}
185
186	$intersections[] = new SlotRange(	1✔
187	max($placeHolder->getStart(), $slotRange->getStart()),	1✔
188	min($placeHolder->getEnd(), $slotRange->getEnd()),	1✔
189	$slotRange->getConnection()	1✔
190	);	1✔
191	}
192
193	return array_reduce(	3✔
194	$intersections,	3✔
195	static function ($carry, $slotRange) {	3✔
196	return $carry + $slotRange->toArray();	1✔
197	},	3✔
198	[]	3✔
199	);	3✔
200	}
201
202	/**
203	* Checks if the specified slot is assigned.
204	*
205	* @param int $slot Slot index.
206	*
207	* @return bool
208	*/
209	#[ReturnTypeWillChange]	6✔
210	public function offsetExists($slot)
211	{
212	return $this->findRangeBySlot($slot) !== false;	6✔
213	}
214
215	/**
216	* Returns the node assigned to the specified slot.
217	*
218	* @param int $slot Slot index.
219	*
220	* @return string\|null
221	*/
222	#[ReturnTypeWillChange]	61✔
223	public function offsetGet($slot)
224	{
225	$found = $this->findRangeBySlot($slot);	61✔
226
227	return $found ? $found->getConnection() : null;	61✔
228	}
229
230	/**
231	* Assigns the specified slot to a node.
232	*
233	* @param int $slot Slot index.
234	* @param NodeConnectionInterface\|string $connection ID or connection instance.
235	*
236	* @return void
237	*/
238	#[ReturnTypeWillChange]	9✔
239	public function offsetSet($slot, $connection)
240	{
241	if (!static::isValid($slot)) {	9✔
242	throw new OutOfBoundsException("Invalid slot $slot for `$connection`");	1✔
243	}
244
245	$this->offsetUnset($slot);	8✔
246	$this->setSlots($slot, $slot, $connection);	8✔
247	}
248
249	/**
250	* Returns the node assigned to the specified slot.
251	*
252	* @param int $slot Slot index.
253	*
254	* @return void
255	*/
256	#[ReturnTypeWillChange]	11✔
257	public function offsetUnset($slot)
258	{
259	if (!static::isValid($slot)) {	11✔
260	throw new OutOfBoundsException("Invalid slot $slot");	×
261	}
262
263	$results = [];	11✔
264	foreach ($this->slotRanges as $slotRange) {	11✔
265	if (!$slotRange->hasSlot($slot)) {	7✔
266	$results[] = $slotRange;	6✔
267	continue;	6✔
268	}
269
270	if (static::isValidRange($slotRange->getStart(), $slot - 1)) {	4✔
271	$results[] = new SlotRange($slotRange->getStart(), $slot - 1, $slotRange->getConnection());	4✔
272	}
273
274	if (static::isValidRange($slot + 1, $slotRange->getEnd())) {	4✔
275	$results[] = new SlotRange($slot + 1, $slotRange->getEnd(), $slotRange->getConnection());	4✔
276	}
277	}
278
279	$this->slotRanges = $results;	11✔
280	}
281
282	/**
283	* Returns the current number of assigned slots.
284	*
285	* @return int
286	*/
287	#[ReturnTypeWillChange]	7✔
288	public function count()
289	{
290	return array_sum(array_map(	7✔
291	static function ($slotRange) {	7✔
292	return $slotRange->count();	3✔
293	},	7✔
294	$this->slotRanges	7✔
295	));	7✔
296	}
297
298	/**
299	* Returns an iterator over the slot map.
300	*
301	* @return Traversable<int, string>
302	*/
303	#[ReturnTypeWillChange]	1✔
304	public function getIterator()
305	{
306	return new ArrayIterator($this->toArray());	1✔
307	}
308
309	/**
310	* Find the slot range which contains the specific slot index.
311	*
312	* @param int $slot Slot index.
313	*
314	* @return SlotRange\|false The slot range object or false if not found.
315	*/
316	protected function findRangeBySlot(int $slot)	66✔
317	{
318	foreach ($this->slotRanges as $slotRange) {	66✔
319	if ($slotRange->hasSlot($slot)) {	15✔
320	return $slotRange;	9✔
321	}
322	}
323
324	return false;	60✔
325	}
326
327	/**
328	* Get gaps between sorted slot ranges with NullSlotRange object.
329	*
330	* @param SlotRange[] $slotRanges
331	*
332	* @return SlotRange[]
333	*/
334	protected function getGaps(array $slotRanges)	41✔
335	{
336	if (empty($slotRanges)) {	41✔
337	return [	41✔
338	new NullSlotRange(0, SlotRange::MAX_SLOTS),	41✔
339	];	41✔
340	}
341	$gaps = [];	24✔
342	$count = count($slotRanges);	24✔
343	$i = 0;	24✔
344	foreach ($slotRanges as $key => $slotRange) {	24✔
345	$start = $slotRange->getStart();	24✔
346	$end = $slotRange->getEnd();	24✔
347	if (static::isValidRange($i, $start - 1)) {	24✔
348	$gaps[] = new NullSlotRange($i, $start - 1);	6✔
349	}
350
351	$i = $end + 1;	24✔
352
353	if ($key === $count - 1) {	24✔
354	if (static::isValidRange($i, SlotRange::MAX_SLOTS)) {	24✔
355	$gaps[] = new NullSlotRange($i, SlotRange::MAX_SLOTS);	24✔
356	}
357	}
358	}
359
360	return $gaps;	24✔
361	}
362
363	/**
364	* Sort slot ranges by start index.
365	*
366	* @param SlotRange[] $slotRanges
367	*
368	* @return void
369	*/
370	protected function sortSlotRanges(array &$slotRanges)	41✔
371	{
372	usort(	41✔
373	$slotRanges,	41✔
374	static function (SlotRange $a, SlotRange $b) {	41✔
375	if ($a->getStart() == $b->getStart()) {	23✔
UNCOV 376	return 0;	×
377	}
378
379	return $a->getStart() < $b->getStart() ? -1 : 1;	23✔
380	}	41✔
381	);	41✔
382	}
383
384	/**
385	* Compact adjacent slot ranges with the same connection.
386	*
387	* @param SlotRange[] $slotRanges
388	*
389	* @return SlotRange[]
390	*/
391	protected function compactSlotRanges(array $slotRanges)	41✔
392	{
393	if (empty($slotRanges)) {	41✔
394	return [];	×
395	}
396
397	$compacted = [];	41✔
398	$count = count($slotRanges);	41✔
399	$i = 0;	41✔
400	$carry = $slotRanges[0];	41✔
401	while ($i < $count) {	41✔
402	$next = $slotRanges[$i + 1] ?? null;	41✔
403	if (
404	!is_null($next)	41✔
405	&& ($carry->getEnd() + 1) === $next->getStart()	41✔
406	&& $carry->getConnection() === $next->getConnection()	41✔
407	) {
UNCOV 408	$carry = new SlotRange($carry->getStart(), $next->getEnd(), $carry->getConnection());	×
409	} else {
410	$compacted[] = $carry;	41✔
411	$carry = $next;	41✔
412	}
413	$i++;	41✔
414	}
415
416	return array_values($compacted);	41✔
417	}
418	}

predis / predis / 23529067023

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous