# [RFC] Normalize array's "auto-increment" value on copy on write

- Thread: https://externals.io/message/105992
- Original archive: https://news-web.php.net/php.internals/105992
- Started by netmo.php@gmail.com on 2019-06-19T23:44:36+00:00
- Messages: 7
- Reply by email to internals@lists.php.net
- More for agents: search with https://externals.io/search.md?q={query} · JSON API at https://externals.io/api · documentation at https://externals.io/llms.txt

---

## #105992 — netmo.php@gmail.com — 2019-06-19T23:44:36+00:00

URL: https://externals.io/message/105992#105992

Hello internals, I just published another RFC

https://wiki.php.net/rfc/normalize-array-auto-increment-on-copy-on-write

Please keep in mind that my intentions are good and I am proposing things
in the interest of everybody. Also, I am aware that I might be wrong. If I
am, please illustrate the reason without barking at me. Thanks <3

---

## #105994 — Nikita Popov — 2019-06-20T07:36:38+00:00

URL: https://externals.io/message/105992#105994

> Hello internals, I just published another RFC
>
> https://wiki.php.net/rfc/normalize-array-auto-increment-on-copy-on-write
>
> Please keep in mind that my intentions are good and I am proposing things
> in the interest of everybody. Also, I am aware that I might be wrong. If I
> am, please illustrate the reason without barking at me. Thanks <3
>

Looks reasonable to me.

Nikita

---

## #105995 — Niklas Keller — 2019-06-20T10:25:45+00:00

URL: https://externals.io/message/105992#105995

Hi Wes,

I don't think it'll work the way you described. I think we have to
make the auto-increment value be entirely dependent on the values in
the array for it to work.

Consider the following example combining your initial assertion in the
RFC with an example further down:

```
<?php

$array = [0, 1, 2, 3];
unset($array[3], $array[2]);

$arrayCopy = $array;

assert($array === $arrayCopy);

$arrayCopy[] = 2;
assert($arrayCopy === [0, 1, 2]); // this assertion must pass; it
doesn't currently

$array[] = 2;
assert($array === $arrayCopy); // still identical/equal
```

https://3v4l.org/vDj4c

In that case `$array` isn't reset by COW because it's not copied and
the initial assertion doesn't pass anymore.

Regards, Niklas

Am Do., 20. Juni 2019 um 09:36 Uhr schrieb Nikita Popov <nikita.ppv@gmail.com>:
>
> 
>
> > […]
>
> Looks reasonable to me.
>
> Nikita

---

## #105998 — netmo.php@gmail.com — 2019-06-20T12:11:17+00:00

URL: https://externals.io/message/105992#105998

I left that out of scope for the RFC, for reasons I don't have the
knowledge to describe properly. In the following example, `unset()` should
reset the auto increment to `1` only after the third `unset()` call

```
$array = [0, 1, 2, 3]; // auto increment is 4 because there are "holes" in
the index
unset($array[1]); // auto increment is still 4
unset($array[2]); // auto increment is still 4
unset($array[3]); // auto increment is 1, because the index sequence is
contiguous, without holes
```

I would love if it worked that way, but that must be covered separately by
someone that knows how to implement it efficiently.

For now, my RFC only makes sure that foreign references in particular will
receive arrays with normalized and predictable "auto increment" values.

Wes

---

## #106006 — Rowan Collins — 2019-06-20T17:06:34+00:00

URL: https://externals.io/message/105992#106006

> I left that out of scope for the RFC, for reasons I don't have the
> knowledge to describe properly. In the following example, `unset()` should
> reset the auto increment to `1` only after the third `unset()` call
>
> ```
> $array = [0, 1, 2, 3]; // auto increment is 4 because there are "holes" in
> the index
> unset($array[1]); // auto increment is still 4
> unset($array[2]); // auto increment is still 4
> unset($array[3]); // auto increment is 1, because the index sequence is
> contiguous, without holes
> ```
>


I wonder if it would be possible (and sufficient) to detect if the element
being removed was the highest key, and only then look for the new "next"
value.

The new value can be found either by decrementing the known value until you
hit an existing entry (optimal for large arrays with few gaps in the
sequence of keys) or by checking all the keys and finding the max (optimal
for small but sparse arrays like [12, 145, 65546]).

# pseudocode:

if ( key_being_unset == array.next_key - 1 ) {
    if ( short_or_likely_to_be_sparse(array) ) {
        new_highest_key = max(array.keys);
    } else {
        # Find highest unused number, starting from the one just deleted
        do {
            new_highest_key = key_being_unset - 1;
        } while ( not key_exists(array, new_highest_key) );
        array.next_key = new_highest_key + 1;
    }
}


I've no idea if this is plausible or not.

Regards,
-- 
Rowan Collins
[IMSoP]

---

## #106113 — Arnold Daniels — 2019-06-29T18:04:18+00:00

URL: https://externals.io/message/105992#106113

> 
>
> > […]
> should
> > […]
> in
> > […]
>
>
> I wonder if it would be possible (and sufficient) to detect if the element
> being removed was the highest key, and only then look for the new "next"
> value.
>
> The new value can be found either by decrementing the known value until you
> hit an existing entry (optimal for large arrays with few gaps in the
> sequence of keys) or by checking all the keys and finding the max (optimal
> for small but sparse arrays like [12, 145, 65546]).
>
> # pseudocode:
>
> if ( key_being_unset == array.next_key - 1 ) {
>     if ( short_or_likely_to_be_sparse(array) ) {
>         new_highest_key = max(array.keys);
>     } else {
>         # Find highest unused number, starting from the one just deleted
>         do {
>             new_highest_key = key_being_unset - 1;
>         } while ( not key_exists(array, new_highest_key) );
>         array.next_key = new_highest_key + 1;
>     }
> }
>
>
> I've no idea if this is plausible or not.
>
> Regards,
> --
> Rowan Collins
> [IMSoP]
>

As you state; this change is not BC. I'm not sure if I agree that this
should be considered a simple bugfix.

Maybe it would be good to add a secondary vote to decide if this should be
implemented in PHP 7.4 or PHP 8.

Arnold

---

## #106122 — Niklas Keller — 2019-06-30T15:16:19+00:00

URL: https://externals.io/message/105992#106122

> Maybe it would be good to add a secondary vote to decide if this should be
> implemented in PHP 7.4 or PHP 8.

Missed that, it should definitely target PHP 8, not 7.4.

Regards, Niklas