[3.13] gh-149079: Fix O(n^2) canonical ordering in unicodedata.normalize() (GH-149080) - #150780
Conversation
Sorry, something went wrong.
…normalize() (pythonGH-149080) Replace the insertion sort used for canonical ordering of combining characters with a hybrid approach: insertion sort for short runs (< 20) and counting sort for longer runs, reducing worst-case complexity from O(n^2) to O(n). This prevents denial of service via crafted Unicode strings with many combining characters in alternating CCC order. (cherry picked from commit 991224b) Co-authored-by: Seth Larson <seth@python.org> Co-authored-by: ch4n3-yoon <ch4n3.yoon@gmail.com> Co-authored-by: Seokchan Yoon <13852925+ch4n3-yoon@users.noreply.github.com> Co-authored-by: Stan Ulbrych <stan@python.org> Co-authored-by: Bénédikt Tran <10796600+picnixz@users.noreply.github.com> Co-authored-by: Petr Viktorin <encukou@gmail.com> Co-authored-by: Serhiy Storchaka <storchaka@gmail.com> Co-authored-by: Maurycy Pawłowski-Wieroński <maurycy@maurycy.com>
Documentation build overview454 files changed · ± 416 modified · - 38 deleted ± Modified
- Deleted |
Sorry, something went wrong.
|
Oh, ya' beat me to it! :-) I just wrote the same PR. |
Sorry, something went wrong.
|
Sorry! |
Sorry, something went wrong.
Oh no worries, I'm the one who's sorry! |
Sorry, something went wrong.
|
Thanks @encukou for the PR 🌮🎉.. I'm working now to backport this PR to: 3.10, 3.11, 3.12. |
Sorry, something went wrong.
|
Sorry, @encukou, I could not cleanly backport this to 3.12 due to a conflict. cherry_picker ba785b88add96acbf403d65cb157fb2743a33a32 3.12 |
Sorry, something went wrong.
|
Sorry, @encukou, I could not cleanly backport this to 3.11 due to a conflict. cherry_picker ba785b88add96acbf403d65cb157fb2743a33a32 3.11 |
Sorry, something went wrong.
|
Sorry, @encukou, I could not cleanly backport this to 3.10 due to a conflict. cherry_picker ba785b88add96acbf403d65cb157fb2743a33a32 3.10 |
Sorry, something went wrong.
Replace the insertion sort used for canonical ordering of combining
characters with a hybrid approach: insertion sort for short runs (< 20)
and counting sort for longer runs, reducing worst-case complexity from
O(n^2) to O(n). This prevents denial of service via crafted Unicode
strings with many combining characters in alternating CCC order.
(cherry picked from commit 991224b)
Co-authored-by: Seth Larson seth@python.org
Co-authored-by: ch4n3-yoon ch4n3.yoon@gmail.com
Co-authored-by: Seokchan Yoon 13852925+ch4n3-yoon@users.noreply.github.com
Co-authored-by: Stan Ulbrych stan@python.org
Co-authored-by: Bénédikt Tran 10796600+picnixz@users.noreply.github.com
Co-authored-by: Petr Viktorin encukou@gmail.com
Co-authored-by: Serhiy Storchaka storchaka@gmail.com
Co-authored-by: Maurycy Pawłowski-Wieroński maurycy@maurycy.com