Minor optimisation in `IntersectionType`

[drupol]

Hi,

I was evaluating this library today for a custom typed generator that I'm developing and I noticed something and I wanted to share what I have in mind.

Current code:

private function ensureNoDuplicateTypes(Type ...$types): void
{
  $names = [];
  
  foreach ($types as $type) {
      assert($type instanceof ObjectType);
  
      $names[] = $type->className()->qualifiedName();
  }
  
  if (count(array_unique($names)) < count($names)) {
      throw new RuntimeException(
          'An intersection type must not contain duplicate types'
      );
  }
}

The time complexity for this would be:

• foreach loop: $\mathcal{O}(n)$
• first count: $\mathcal{O}(1)$
• array_unique:
  • Worst case: $\mathcal{O}(n)$
  • Best case: $\Omega(n)$
• second count: $\mathcal{O}(1)$

What matter here in this snippet is that, no matter how many groups of duplicates $types contains, it will always traverse the full array, this is why $\mathcal{O}(n) == \Omega(n)$ in the first case. However, what we are looking for here, is to throw an exception as soon as there is a duplicate.

And here we have two scenarios:

• worst case scenario( $\mathcal{O}$ ): the last item is a duplicate
• best case scenario( $\Omega$ ): the second item is a duplicate

Here's what I propose:

private function ensureNoDuplicateTypes(Type ...$types): void
{
  $names = [];
  
  foreach ($types as $type) {
      assert($type instanceof ObjectType);
  
      $classQualifiedName = $type->className()->qualifiedName();
  
      $names[] = in_array($classQualifiedName, $names, true)
          ? throw new RuntimeException('An intersection type must not contain duplicate types')
          : $classQualifiedName;
  }
}

What I propose is to break the loop as soon as a duplicate is found.

The time complexity for this would be:

• foreach loop: $\mathcal{O}(n)$
• in_array:
  • Worst case: $\mathcal{O}(n)$
  • Best case: $\mathcal{O}(2)$
  • Between best and worst cases: $\mathcal{O}(m)$ with $(m < n)$

What do you think?
Actually I often see such things in PHP here and there and I'm wondering if introducing pull-requests for changing these kind of subtle things make sense.
Do you think it worth submitting a PR ?

Thanks in advance.

[sebastianbergmann]

Yes, please submit a PR for the 3.2 branch. Thanks!

[drupol]

Going to do this right now.