Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:125081
Content-Type: multipart/alternative;
 boundary="------------bumRzmUSD3bwZBn3C8Uq67m1"
Message-ID:
 <AM8P250MB017049771FC06148578B1671E28E2@AM8P250MB0170.EURP250.PROD.OUTLOOK.COM>
Date: Wed, 21 Aug 2024 03:59:24 +0200
User-Agent: Mozilla Thunderbird
Subject: Re: [PHP-DEV] State of Generics and Collections
To: Arnaud Le Blanc <arnaud.lb@gmail.com>
Cc: Derick Rethans <derick@php.net>,
 PHP Developers Mailing List <internals@lists.php.net>
References: <1b59392a-68cb-36eb-0fef-977ac7113520@php.net>
 <AM8P250MB01706B1541E1283F4065B94AE28C2@AM8P250MB0170.EURP250.PROD.OUTLOOK.COM>
 <CAP1Jc11djBvAkWgMwM-SzUQyW4AQ+TUDtLNKmyFNCmbJvKW+WA@mail.gmail.com>
Content-Language: en-US
In-Reply-To: <CAP1Jc11djBvAkWgMwM-SzUQyW4AQ+TUDtLNKmyFNCmbJvKW+WA@mail.gmail.com>
Precedence: bulk
MIME-Version: 1.0
X-MS-Exchange-MessageSentRepresentingType: 1
X-MS-PublicTrafficType: Email
X-MS-TrafficTypeDiagnostic: AM8P250MB0170:EE_|PA2P250MB1069:EE_
X-MS-Office365-Filtering-Correlation-Id: d5e866b0-5ecb-4050-99fe-08dcc184e156
X-Microsoft-Antispam:
	BCL:0;ARA:14566002|15080799003|19110799003|8060799006|12050799009|461199028|5072599009|3412199025|440099028;
X-Microsoft-Antispam-Message-Info:
	1zI9L9YBB716Zq4AbvjODATvgAzuT1bLZhvWonTn3aZ2niqGdhDMpVBkAxBanAn1CoWNVeeSM+EIO+7PuEbm8PcdtxIrqdKps0QcRBIDLUKx///xRL/RDOlcN8OnjV0Frmnz/hEJqjeRIOxy9tg1Wfq7XAiRWkF6BLqKQXtc1sfFfrMoCTs4KBo4hZzpEKUHW06KlJgDblFXVnNjP6VL/uuBYqLFI42Zg/x/K+FcKlRLeGPtjy0eTzeEvZfuYOe/qHv9+8m7/sjBZkicQhrQn/l1t/4CcehLUBuAs+EU8zHxpRh1wvKDRWXGJMF3u6khFL9ovjvrx72QRY2Oo7OcijM71PdPr24C587zkd0VgGI/3n4iyvcHZydh/C++t1+Kz24NpFclMqe+iOWOSp7HB5bXDh38sG0ARi6NJQAgt61EgUIR1J8D8t83QzEg9uJAw+X9YfNVOcbkiDQ/KJem5HMRjfMyq2hX/M0rUX5NnEUzrwRNqdvAx67/svOKy7XcyCH6L17xTMVUbJLh8aQcgiU1xZ4JyqFMGEkLOd3+3M8QZ5iibZdS28FlwERPpaZmIOYthE8S1HvcGf3iLoSStSS1L9mH83CF0f8DdzUfZN++JFqKHJ7awr/IbzDNtKPjnwgKwdR29xvciW8g6lO9jyiue0alv752kBUl85Vr7lXA67YOIXZGOZ/BvV7Vlg2gKPfZCVrx/8NdU9QajxiKdqGXCidDvZh+SV56ufpFEF59Ao/byqh7sLwKXmUu29SA
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0:
	=?utf-8?B?L3ZLQ3V0VmsySG1iOGpEUzhYclIvcGVGYzFMc05lclI4UWZ1RExXSTNoekN4?=
 =?utf-8?B?ZHd5MmE1aVNSVnB3dVNrNTQ0RWtTUEZzRHhJVWRmaFJSZWIwdVFaS1Jsb1hp?=
 =?utf-8?B?anE4cVpycGZMOHM2NjJBa0dobktZajJBS3JEYmdBM2MxZGZKK2poTStBNW1Y?=
 =?utf-8?B?THlURHhxclc0aU1wS1ozODArNjlyYWI3QkdKdmo5VDlDL29TUEh2aXZNOTVZ?=
 =?utf-8?B?RWwxaGE1bFVUdTRKOEZUbXJUT2JJRG5OR3RQK0Fxc25GeUttVEtJSzJ6ZTgr?=
 =?utf-8?B?T1dYY1QwazdpYWR1amd1U0lLSFNZamh6WnV5Q2NsMTNWVHBLUTFnL0JTbDM0?=
 =?utf-8?B?ZlBsZ3hmSkFRdVlKY0ZubnFlcklQQmVmeGJoT2JWK2JhZEdzTEJGMEVnUDFC?=
 =?utf-8?B?dTJyUU13VTF6SmFqNXI4WWhPNEhzNURGMG4vUkZ0ZkY3eW9NVTlXcVB5NlYx?=
 =?utf-8?B?bEVhRG41alNFM2xPbDlmR2l0V0VmZ0xscHgzYnQzNTVSVFpPam5NckpQMlMv?=
 =?utf-8?B?K2o3c056OW9RaEd5ZkJodEVwZVRHSVlEOEJQK0Z5TjNJenNPSEVyRGVzN0Uw?=
 =?utf-8?B?aGFhY1AyazNoY2lCUkxvV0JURGw4a0RyeWpTVFNLUnVOU1djNkExbEVvQ2RC?=
 =?utf-8?B?RUtIVFlDUHd5WDhSbDIrZytmUjI5RGFKQ2VmV2RmYlJwQmxORmMrOVdNOGt5?=
 =?utf-8?B?NHZHSGJhVlNKaVpaTUtOU0VjMVNxZkIrN2krTVFCZHB0cWoxRXhEMFRYallX?=
 =?utf-8?B?MlVSSGJKYXZsR1RsOE4rcm5PbkJ0Yys4N3pVUnZOWHpEVExkSXh5UFJJQ05v?=
 =?utf-8?B?a2srQ1kvTGNwTXVUazlwR0RPdlpkY0xyZnpqV0c1Q1VZTHI3NVIxNVRBWk9W?=
 =?utf-8?B?L2kydTFvcU1mNWVSV3hiY0FWVmlrL2QybzdiaGVWN1dzbzJSV1RjTEtzeUti?=
 =?utf-8?B?QTMyZ2E1Qk4vbWoraUJ1VnZ4aHlJbk0rNTY4eE1JWGFzUk12emUvWUlhbENz?=
 =?utf-8?B?ZHBSYnFWTnNFWTUvR1h1aHNRZHdzSGE2NGE3NFBKcFJya0JmUzVVUkhROE5N?=
 =?utf-8?B?SkQzRUdOVklnc3JDSWhnZUlRaURhOXVmRVNrK1YvSUhwUDdLTTNGc0Nza1NH?=
 =?utf-8?B?NTNrUURGQnFabkRZRDMrUkhVbEo0WHhGMTJtcjgzUmViSjVzbFZVUG9PQkRo?=
 =?utf-8?B?REdGenV0emtjc0tuU01ZU2l4cWNrVmZld0xTcU8vM3czZng1bHJIRHZNU2xZ?=
 =?utf-8?B?SjAvelBsNUpabDN1RUpMT0k0cEJ3N3V2UmZOb3h1TEJ2STZhdHBFaGI3dmd6?=
 =?utf-8?B?MmpxNDVKUCsyb01MS2M1bU1MRFc0bDF6YU4wMVlSVFhCYVY4N0M2RzZmbGdZ?=
 =?utf-8?B?b3d2ZVNLMUtIMzBQMVNPWG1Hc0k3TDJtVXM1aGF3blJTaklZcDkwNW95eXlN?=
 =?utf-8?B?bnhYMU9EamY5dGJmazNGNnVQTDRCcmcrS2grR2J1RG44MUgzNVRKTzk3ZVRN?=
 =?utf-8?B?QURLYjBZUFdsbFpTYUxLOExUVlZTb0RKeXdHRm9uVE1vZlpuc0FZQTMrMmtI?=
 =?utf-8?B?eGtUNDAvQXlmVFk0em42MmloZzR5dWo3dVFaLzQrZkJFYXpMalR6UTNRK0hB?=
 =?utf-8?B?ekorNWduM3RvV3FWN1ZKR01pcTRlMzN1d3JXY2l4aEhXb1ZuNTkvRndBanhO?=
 =?utf-8?B?bkdSSDBtd0RJVmRGYitYS2RyWUdvZUdSb25vbnlpdnZNdmZlNitIcFU0UWVV?=
 =?utf-8?Q?Qc+66sNTE0Ke0WbnkE=3D?=
X-OriginatorOrg: sct-15-20-7784-11-msonline-outlook-95b76.templateTenant
X-MS-Exchange-CrossTenant-Network-Message-Id: d5e866b0-5ecb-4050-99fe-08dcc184e156
X-MS-Exchange-CrossTenant-AuthSource: AM8P250MB0170.EURP250.PROD.OUTLOOK.COM
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 21 Aug 2024 01:59:24.3290
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 84df9e7f-e9f6-40af-b435-aaaaaaaaaaaa
X-MS-Exchange-CrossTenant-RMS-PersistedConsumerOrg:
	00000000-0000-0000-0000-000000000000
X-MS-Exchange-Transport-CrossTenantHeadersStamped: PA2P250MB1069
From: bobwei9@hotmail.com (Bob Weinand)

--------------bumRzmUSD3bwZBn3C8Uq67m1
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit

Hey Arnauld,

On 20.8.2024 15:01:28, Arnaud Le Blanc wrote:
> Hi Bob,
>
> On Tue, Aug 20, 2024 at 12:18 AM Bob Weinand<bobwei9@hotmail.com> wrote:
>> The fluid Arrays section says "A PoC has been implemented, but the performance impact is still uncertain". Where may I find that PoC for my curiosity? I'm imagining the implementation of the array types as a counted collection of types of the entries. But without the PoC I may only guess.
> I may publish the PoC at some point, but in the meantime here is a
> short description of how it's implemented:
>
> - The zend_array has a zend_type member representing the type of its elements
> - Everytime we add or update a member, we union its type with the
> array type. For simple types it's just a |= operation. For arrays with
> a single class it's also simple. For complex types it's more expensive
> currently, but it may be possible to cache transitions to make this
> cheaper.
> - Updating the array type on deletes requires to either maintain a
> counter of every type, or to re-compute the type entirely everytime.
> Both are probably too expensive. Instead, we don't update the type on
> deletes, but we re-compute the type entirely when a type check fails.
> This is based on two hypotheses: 1. A delete rarely changes an array's
> type in practice, and 2. Type checks rarely fail

That sounds like a clever way to do it. I like this approach.

> - References are treated as mixed, so adding a reference to an array
> or taking a reference to an element changes its type to mixed. Passing
> an array<mixed> to a more specific array<something> will cause a
> re-compute, which also de-refs every reference.

Classifying a reference as mixed certainly makes this work and I guess 
it's probably an acceptable overhead. References into (big) arrays are 
not that common. Short of doing a foreach by-ref, but that's anyway an 
O(n) operation generally.

> - Updating a nested element requires updating the type of every parent

Does it actually? It just requires updating the type of the parent, if 
the own type is actually changed. But types of arrays don't change all 
the time, so that's likely an amortized constant time operation with 
respect to inserts/updates.

>> It also says "Another issue is that [...] typed properties may not be possible.". Why would that be the case? Essentially a typed property would just be a static array, which you describe in the section right below.
> It becomes complicated when arrays contain references or nested
> arrays. Type constraints must be propagated to nested arrays, but also
> removed when an array is not reachable via a typed property anymore.
>
> E.g.
>
> class C {
>      public array<array<int>> $prop;
> }
>
> $a = &$c->prop[0];
> $a[] = 'string'; // must be an error
> unset($c->prop[0]);
> $a[] = 'string'; // must be accepted
In this case $a will decay from a RC=1 reference to a normal value. 
During the unreferencing operation the type restrictions can be dropped. 
That operation is only O(n) if it actually contains other references.
>
> $b = &$c->prop[1];
> $b[] = 'string'; // must be an error
> $c->prop = [];
> $a[] = 'string'; // must be accepted
>
> I don't remember all the possible cases, but I didn't find a way to
> support this that didn't involve recursively scanning an array at some
> point. IIRC, without references it's less of an issue, so a possible
> way forward would be to forbid references to members of typed
> properties. Unfortunately this breaks pass-by-reference, e.g.
> `sort($c->prop)`. out/inout parameters may be part of a solution, but
> with more array separations than pass-by-ref.

Yes, you'll have to scan the array recursively, but only if it contains 
references (which you know thanks to array<mixed> or 
array<array<mixed>>). And you also only need to descend into arrays 
which contain references.

If something contains a reference, you just slap a property type onto it 
- like "foreach entry in array { if entry is reference { 
add_type_source(inner type of entry) } }" - thus, in case of 
array<array<int>>, you slap array<int> onto it. This operation is only 
O(n) if the array type actually contains references (i.e. it will 
mismatch due to array<mixed>, and you have to iterate anyway).

So it will just work like references to property types do: these can 
also never violate the type containing them. At least in my mind.

I'd also be happy to chat more about it off-list, but possibly easier 
too once the patch is public.

> Best Regards,
> Arnaud


Overall I would not focus too much on making the case "reference into 
array" too much of a blocker. It should work, but it's fine if it comes 
with a couple rough edges regarding performance. I don't think arrays 
where you hold a reference into them are commonly passed around or big.

There are a few edge cases like state machines built with array 
references, but the solution to these is ... don't type the property 
containing it then. And if it really becomes a problem, we may still 
invest time into it after landing it.


Thanks,

Bob
--------------bumRzmUSD3bwZBn3C8Uq67m1
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: 8bit

<!DOCTYPE html><html><head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
  </head>
  <body>
    <p>Hey Arnauld,<br>
    </p>
    <div class="moz-cite-prefix">On 20.8.2024 15:01:28, Arnaud Le Blanc
      wrote:<br>
    </div>
    <blockquote type="cite" cite="mid:CAP1Jc11djBvAkWgMwM-SzUQyW4AQ+TUDtLNKmyFNCmbJvKW+WA@mail.gmail.com">
      <pre wrap="" class="moz-quote-pre">Hi Bob,

On Tue, Aug 20, 2024 at 12:18 AM Bob Weinand <a class="moz-txt-link-rfc2396E" href="mailto:bobwei9@hotmail.com">&lt;bobwei9@hotmail.com&gt;</a> wrote:
</pre>
      <blockquote type="cite">
        <pre wrap="" class="moz-quote-pre">The fluid Arrays section says &quot;A PoC has been implemented, but the performance impact is still uncertain&quot;. Where may I find that PoC for my curiosity? I'm imagining the implementation of the array types as a counted collection of types of the entries. But without the PoC I may only guess.
</pre>
      </blockquote>
      <pre wrap="" class="moz-quote-pre">
I may publish the PoC at some point, but in the meantime here is a
short description of how it's implemented:

- The zend_array has a zend_type member representing the type of its elements
- Everytime we add or update a member, we union its type with the
array type. For simple types it's just a |= operation. For arrays with
a single class it's also simple. For complex types it's more expensive
currently, but it may be possible to cache transitions to make this
cheaper.
- Updating the array type on deletes requires to either maintain a
counter of every type, or to re-compute the type entirely everytime.
Both are probably too expensive. Instead, we don't update the type on
deletes, but we re-compute the type entirely when a type check fails.
This is based on two hypotheses: 1. A delete rarely changes an array's
type in practice, and 2. Type checks rarely fail</pre>
    </blockquote>
    <p>That sounds like a clever way to do it. I like this approach.<span style="white-space: pre-wrap">
</span></p>
    <p><span style="white-space: pre-wrap">
</span></p>
    <blockquote type="cite" cite="mid:CAP1Jc11djBvAkWgMwM-SzUQyW4AQ+TUDtLNKmyFNCmbJvKW+WA@mail.gmail.com">
      <pre wrap="" class="moz-quote-pre">- References are treated as mixed, so adding a reference to an array
or taking a reference to an element changes its type to mixed. Passing
an array&lt;mixed&gt; to a more specific array&lt;something&gt; will cause a
re-compute, which also de-refs every reference.</pre>
    </blockquote>
    <p>Classifying a reference as mixed certainly makes this work and I
      guess it's probably an acceptable overhead. References into (big)
      arrays are not that common. Short of doing a foreach by-ref, but
      that's anyway an O(n) operation generally.<br>
    </p>
    <blockquote type="cite" cite="mid:CAP1Jc11djBvAkWgMwM-SzUQyW4AQ+TUDtLNKmyFNCmbJvKW+WA@mail.gmail.com">
      <pre wrap="" class="moz-quote-pre">- Updating a nested element requires updating the type of every parent</pre>
    </blockquote>
    <p>Does it actually? It just requires updating the type of the
      parent, if the own type is actually changed. But types of arrays
      don't change all the time, so that's likely an amortized constant
      time operation with respect to inserts/updates.<span style="white-space: pre-wrap">
</span></p>
    <blockquote type="cite" cite="mid:CAP1Jc11djBvAkWgMwM-SzUQyW4AQ+TUDtLNKmyFNCmbJvKW+WA@mail.gmail.com">
      <blockquote type="cite">
        <pre wrap="" class="moz-quote-pre">It also says &quot;Another issue is that [...] typed properties may not be possible.&quot;. Why would that be the case? Essentially a typed property would just be a static array, which you describe in the section right below.
</pre>
      </blockquote>
      <pre wrap="" class="moz-quote-pre">
It becomes complicated when arrays contain references or nested
arrays. Type constraints must be propagated to nested arrays, but also
removed when an array is not reachable via a typed property anymore.

E.g.

class C {
    public array&lt;array&lt;int&gt;&gt; $prop;
}

$a = &amp;$c-&gt;prop[0];
$a[] = 'string'; // must be an error
unset($c-&gt;prop[0]);
$a[] = 'string'; // must be accepted</pre>
    </blockquote>
    In this case $a will decay from a RC=1 reference to a normal value.
    During the unreferencing operation the type restrictions can be
    dropped. That operation is only O(n) if it actually contains other
    references.<br>
    <blockquote type="cite" cite="mid:CAP1Jc11djBvAkWgMwM-SzUQyW4AQ+TUDtLNKmyFNCmbJvKW+WA@mail.gmail.com">
      <pre wrap="" class="moz-quote-pre">

$b = &amp;$c-&gt;prop[1];
$b[] = 'string'; // must be an error
$c-&gt;prop = [];
$a[] = 'string'; // must be accepted

I don't remember all the possible cases, but I didn't find a way to
support this that didn't involve recursively scanning an array at some
point. IIRC, without references it's less of an issue, so a possible
way forward would be to forbid references to members of typed
properties. Unfortunately this breaks pass-by-reference, e.g.
`sort($c-&gt;prop)`. out/inout parameters may be part of a solution, but
with more array separations than pass-by-ref.</pre>
    </blockquote>
    <p><span style="white-space: pre-wrap">Yes, you'll have to scan the array recursively, but only if it contains references (which you know thanks to array&lt;mixed&gt; or array&lt;array&lt;mixed&gt;&gt;). And you also only need to descend into arrays which contain references.
</span></p>
    <p><span style="white-space: pre-wrap">
</span></p>
    <p><span style="white-space: pre-wrap">If something contains a reference, you just slap a property type onto it - like &quot;foreach entry in array { if entry is reference { add_type_source(inner type of entry) } }&quot; - thus, in case of array&lt;array&lt;int&gt;&gt;, you slap array&lt;int&gt; onto it. This operation is only O(n) if the array type actually contains references (i.e. it will mismatch due to array&lt;mixed&gt;, and you have to iterate anyway).</span></p>
    <p><span style="white-space: pre-wrap">So it will just work like references to property types do: these can also never violate the type containing them. At least in my mind.
</span></p>
    <p><span style="white-space: pre-wrap">I'd also be happy to chat more about it off-list, but possibly easier too once the patch is public.
</span></p>
    <p><span style="white-space: pre-wrap">
</span><span style="white-space: pre-wrap">
</span></p>
    <blockquote type="cite" cite="mid:CAP1Jc11djBvAkWgMwM-SzUQyW4AQ+TUDtLNKmyFNCmbJvKW+WA@mail.gmail.com">
      <pre wrap="" class="moz-quote-pre">Best Regards,
Arnaud</pre>
    </blockquote>
    <p><br>
    </p>
    <p>Overall I would not focus too much on making the case &quot;reference
      into array&quot; too much of a blocker. It should work, but it's fine
      if it comes with a couple rough edges regarding performance. I
      don't think arrays where you hold a reference into them are
      commonly passed around or big.<br>
    </p>
    <p>There are a few edge cases like state machines built with array
      references, but the solution to these is ... don't type the
      property containing it then. And if it really becomes a problem,
      we may still invest time into it after landing it.<br>
    </p>
    <p><br>
    </p>
    <p>Thanks,<br>
    </p>
    Bob<br>
  </body>
</html>

--------------bumRzmUSD3bwZBn3C8Uq67m1--