◐ Shell
reader mode source ↗
Skip to content

[3.13] gh-149079: Fix O(n^2) canonical ordering in unicodedata.normalize() (GH-149080)#150780

Merged
encukou merged 1 commit into
python:3.13from
encukou:backport-991224b-3.13
Jun 2, 2026
Merged

[3.13] gh-149079: Fix O(n^2) canonical ordering in unicodedata.normalize() (GH-149080)#150780
encukou merged 1 commit into
python:3.13from
encukou:backport-991224b-3.13

Conversation

@encukou

@encukou encukou commented Jun 2, 2026 •
edited by bedevere-app Bot
Loading

Copy link
Copy Markdown
Member

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

@sethmlarson @ch4n3-yoon
@StanFromIreland @picnixz @encukou @serhiy-storchaka @maurycy
[3.13] pythongh-149079: Fix O(n^2) canonical ordering in unicodedata.… …
70304e4 
…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>
@bedevere-app bedevere-app Bot mentioned this pull request Jun 2, 2026
Open
@bedevere-app bedevere-app Bot mentioned this pull request Jun 2, 2026
Merged
@encukou encukou added needs backport to 3.10 only security fixes needs backport to 3.11 only security fixes needs backport to 3.12 only security fixes labels Jun 2, 2026
@read-the-docs-community

read-the-docs-community Bot commented Jun 2, 2026

Copy link
Copy Markdown

Documentation build overview

📚 cpython-previews | 🛠️ Build #32953331 | 📁 Comparing 70304e4 against main (025cc26)

  🔍 Preview build  

454 files changed · ± 416 modified · - 38 deleted

± Modified

- Deleted

@StanFromIreland

StanFromIreland commented Jun 2, 2026

Copy link
Copy Markdown
Member

Oh, ya' beat me to it! :-) I just wrote the same PR.

@StanFromIreland StanFromIreland mentioned this pull request Jun 2, 2026
Closed
@encukou

encukou commented Jun 2, 2026

Copy link
Copy Markdown
Member Author

Sorry!

@encukou encukou enabled auto-merge (squash) June 2, 2026 11:56
@StanFromIreland

StanFromIreland commented Jun 2, 2026

Copy link
Copy Markdown
Member

Sorry!

Oh no worries, I'm the one who's sorry!

Hide details View details @encukou encukou merged commit ba785b8 into python:3.13 Jun 2, 2026
83 of 85 checks passed
@miss-islington-app

miss-islington-app Bot commented Jun 2, 2026

Copy link
Copy Markdown

Thanks @encukou for the PR 🌮🎉.. I'm working now to backport this PR to: 3.10, 3.11, 3.12.
🐍🍒⛏🤖

@miss-islington-app

miss-islington-app Bot commented Jun 2, 2026

Copy link
Copy Markdown

Sorry, @encukou, I could not cleanly backport this to 3.12 due to a conflict.
Please backport using cherry_picker on command line.

cherry_picker ba785b88add96acbf403d65cb157fb2743a33a32 3.12

@miss-islington-app

miss-islington-app Bot commented Jun 2, 2026

Copy link
Copy Markdown

Sorry, @encukou, I could not cleanly backport this to 3.11 due to a conflict.
Please backport using cherry_picker on command line.

cherry_picker ba785b88add96acbf403d65cb157fb2743a33a32 3.11

@miss-islington-app

miss-islington-app Bot commented Jun 2, 2026

Copy link
Copy Markdown

Sorry, @encukou, I could not cleanly backport this to 3.10 due to a conflict.
Please backport using cherry_picker on command line.

cherry_picker ba785b88add96acbf403d65cb157fb2743a33a32 3.10

@encukou encukou deleted the backport-991224b-3.13 branch June 4, 2026 11:14
@StanFromIreland StanFromIreland removed needs backport to 3.10 only security fixes only security fixes needs backport to 3.12 only security fixes labels Jun 5, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@StanFromIreland StanFromIreland StanFromIreland approved these changes

Assignees

@encukou encukou

Labels

type-security A security issue

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@encukou @StanFromIreland @sethmlarson