GitLab

The code for ItemizeTextToRuns is really slow on some corner cases.
This CL is fixing the performance issue (see http://crbug.com/924915).

The main issue is that each iteration of the ItemizeText loop will move
forward by the smallest amount of characters (size of the run) and then
the whole logic to find the breaking position is applied again.

As an example, the following text:
  "\n!\n!\n!\n!\n!\n!\n!\n!\n!\n!\n!\n!"

  * Computing the breaking point of "bidi direction" is O(n)
  * Computing the breaking point of "script" is O(n)

Unfortunately, most runs will be split at the \n since it's a special
character. This means the complexity of this code will be O(n^2).

The proposed code in this CL is:
  1) Splitting in block of same bidi direction
  2) Splitting in sequence of characters with compatible script
  3) Splitting for special characters / style

This way, the 1) and 2) are only executed once (e.g. O(n) ) by
character.

NOTE: This bad pattern was happening often with emoji since they
      are often isolated in a run as a special characters.

Bug: 924915, 1014119
Change-Id: I8d950e166ff01285ad0ce9796e38321ec502f368
Fixed: 2
Reviewed-on: https://chromium-review.googlesource.com/c/chromium/src/+/1865673Reviewed-by: Robert Liao <robliao@chromium.org>
Reviewed-by: Alexei Svitkine <asvitkine@chromium.org>
Commit-Queue: Etienne Bergeron <etienneb@chromium.org>
Cr-Commit-Position: refs/heads/master@{#708014}