René's URL Explorer Experiment


Title: gh-96954: use a directed acyclic word graph for storing the unicodedata codepoint names by cfbolz · Pull Request #97906 · python/cpython · GitHub

Open Graph Title: gh-96954: use a directed acyclic word graph for storing the unicodedata codepoint names by cfbolz · Pull Request #97906 · python/cpython

X Title: gh-96954: use a directed acyclic word graph for storing the unicodedata codepoint names by cfbolz · Pull Request #97906 · python/cpython

Description: gh-96954: use a directed acyclic word graph/Deterministic acyclic finite state automaton/finite state transducer for storing the unicodedata codepoint names. This is the approach that PyPy recently switched to. The names are encoded into a packed string that represents the finite state machine to recognize valid names, and also to map names to an index. The packed representation can be used to match names without decompression. The same representation can be used for the inverse operation of mapping a code point to a codepoint name. This changes reduces the size of the unicodedata shared library from 1222 KiB to 791 KiB. Relevant papers: https://www.ic.unicamp.br/~reltech/1992/92-01.pdf http://www.cs.put.poznan.pl/dweiss/site/publications/download/fsacomp.pdf (but I didn't follow the approach of not representing states explicitly, that was consistently worse in my experiments). /CC @isidentical

Open Graph Description: gh-96954: use a directed acyclic word graph/Deterministic acyclic finite state automaton/finite state transducer for storing the unicodedata codepoint names. This is the approach that PyPy recently...

X Description: gh-96954: use a directed acyclic word graph/Deterministic acyclic finite state automaton/finite state transducer for storing the unicodedata codepoint names. This is the approach that PyPy recently...

Opengraph URL: https://github.com/python/cpython/pull/97906

X: @github

direct link

Domain: github.com

react-profiling0
react-import-mapreact,react-dom,react-dom/client,react-dom/profiling,react-is,react/compiler-runtime,react/jsx-dev-runtime,react/jsx-runtime,scheduler@b8488ee2c322
route-pattern/:user_id/:repository/pull/:id/files(.:format)
route-controllerpull_requests
route-actionfiles
fetch-noncev2:e71f52d5-9d8c-8410-0cd9-39da60165222
current-catalog-service-hashae870bc5e265a340912cde392f23dad3671a0a881730ffdadd82f2f57d81641b
request-idB1B0:6AE81:2B9B7E:39EA46:6B023459
html-safe-nonce44905273697d85a4837fc2e77dad2835ee1d490d8763ce999697fd2eee96e73b
visitor-payloadeyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiJCMUIwOjZBRTgxOjJCOUI3RTozOUVBNDY6NkIwMjM0NTkiLCJ2aXNpdG9yX2lkIjoiMTI5NDkyNDQ0Njc0MTcwNTgxNyIsInJlZ2lvbl9lZGdlIjoiaWFkIiwicmVnaW9uX3JlbmRlciI6ImlhZCJ9
visitor-hmac44cb1c2ca241ded7d0df463aff3eec9e251f061143f27512145537746a608e94
hovercard-subject-tagpull_request:1077336631
github-keyboard-shortcutsrepository,pull-request-list,pull-request-conversation,pull-request-files-changed,copilot
google-site-verificationApib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I
octolytics-urlhttps://collector.github.com/github/collect
analytics-location///pull_requests/show/files
fb:app_id1401488693436528
apple-itunes-appapp-id=1477376905, app-argument=https://github.com/python/cpython/pull/97906/files
twitter:imagehttps://avatars.githubusercontent.com/u/85942?s=400&v=4
twitter:cardsummary_large_image
og:imagehttps://avatars.githubusercontent.com/u/85942?s=400&v=4
og:image:altgh-96954: use a directed acyclic word graph/Deterministic acyclic finite state automaton/finite state transducer for storing the unicodedata codepoint names. This is the approach that PyPy recently...
og:site_nameGitHub
og:typeobject
hostnamegithub.com
expected-hostnamegithub.com
None87e774ee7c6b3bee0490394e4d3e57ec9dbc956f74b87ea685dc8996c1676456
turbo-cache-controlno-preview
diff-viewunified
go-importgithub.com/python/cpython git https://github.com/python/cpython.git
octolytics-dimension-user_id1525981
octolytics-dimension-user_loginpython
octolytics-dimension-repository_id81598961
octolytics-dimension-repository_nwopython/cpython
octolytics-dimension-repository_publictrue
octolytics-dimension-repository_is_forkfalse
octolytics-dimension-repository_network_root_id81598961
octolytics-dimension-repository_network_root_nwopython/cpython
turbo-body-classeslogged-out env-production page-responsive full-width
disable-turbotrue
browser-stats-urlhttps://api.github.com/_private/browser/stats
browser-errors-urlhttps://api.github.com/_private/browser/errors
release423dbb54c5e7bfecc838eb387c1435eb3d0e760d
ui-targetfull
theme-color#1e2327
color-schemelight dark

Links:

Skip to contenthttps://github.com/python/cpython/pull/97906/files#start-of-content
https://github.com/
Sign inhttps://github.com/login?return_to=https%3A%2F%2Fgithub.com%2Fpython%2Fcpython%2Fpull%2F97906%2Ffiles
GitHubRepository hosting, code review, and collaborationhttps://github.com/platform
CopilotAI coding agent for tasks, projects, and automated workhttps://github.com/features/copilot
ActionsCI/CD and automationhttps://github.com/features/actions
Code QualityQuality analysis, fixes, and enforcementhttps://github.com/features/code-quality
CodespacesCloud development environmentshttps://github.com/features/codespaces
Code SecurityVulnerability detection and remediationhttps://github.com/security/advanced-security/code-security
Secret ProtectionSecret scanning and leak preventionhttps://github.com/security/advanced-security/secret-protection
All Featureshttps://github.com/features
Documentationhttps://docs.github.com/en
Traininghttps://learn.github.com/skills
Certificationshttps://learn.github.com/credentials
Build with Copilothttps://github.com/features/ai
Customize Copilothttps://docs.github.com/en/copilot/how-tos/copilot-on-github/customize-copilot/customize-copilot-overview
Integrationshttps://github.com/marketplace
Trending reposhttps://github.com/trending
GitHub Sponsorshttps://github.com/open-source/sponsors
Developer articleshttps://github.com/resources/articles
ChangelogYour source for the latest features, improvements, and fixes across GitHub products, all in one place.https://github.blog/changelog/
Enterpriseshttps://github.com/enterprise
Teamhttps://github.com/team
Startupshttps://github.com/enterprise/startups
Nonprofitshttps://github.com/solutions/industry/nonprofits
Healthcarehttps://github.com/solutions/industry/healthcare
Financial serviceshttps://github.com/solutions/industry/financial-services
Manufacturinghttps://github.com/solutions/industry/manufacturing
Governmenthttps://github.com/solutions/industry/government
See all industrieshttps://github.com/solutions/industry
Why GitHubhttps://github.com/why-github
Customer Storieshttps://github.com/customer-stories
Business insightshttps://github.com/solutions/executive-insights
Trust Centerhttps://github.com/trust-center
GitHub Advanced SecurityEnterprise-grade code securityhttps://github.com/security/advanced-security
Copilot for businessEnterprise-grade AI featureshttps://github.com/features/copilot/copilot-business
Premium SupportEnterprise-grade 24/7 supporthttps://github.com/enterprise/premium-support
Documentationhttps://docs.github.com/en
Resource centerhttps://github.com/resources
Bloghttps://github.blog/
Events & webinarshttps://github.com/resources/events
Community Forumhttps://github.com/orgs/community/discussions
Customer Storieshttps://github.com/customer-stories
Integrationshttps://github.com/marketplace
Customer supporthttps://help.github.com/
Traininghttps://learn.github.com/skills
GitHub Statushttps://www.githubstatus.com/
Abouthttps://github.com/about
Partnershttps://github.com/partners
Changeloghttps://github.blog/changelog/
GitHub UniverseThe event for developers, by developers — talks, workshops, and what’s next for GitHub.https://githubuniverse.com/
Pricinghttps://github.com/pricing
Sign inhttps://github.com/login?return_to=https%3A%2F%2Fgithub.com%2Fpython%2Fcpython%2Fpull%2F97906%2Ffiles
Sign uphttps://github.com/signup?ref_cta=Sign+up&ref_loc=header+logged+out&ref_page=%2F%3Cuser-name%3E%2F%3Crepo-name%3E%2Fpull_requests%2Fshow%2Ffiles&source=header-repo&source_repo=python%2Fcpython
Reloadhttps://github.com/python/cpython/pull/97906/files
Reloadhttps://github.com/python/cpython/pull/97906/files
Reloadhttps://github.com/python/cpython/pull/97906/files
pythonhttps://github.com/python
cpythonhttps://github.com/python/cpython
Codehttps://github.com/python/cpython
Issues5k+ (5k+)https://github.com/python/cpython/issues
Pull requests2.4k (2.4k)https://github.com/python/cpython/pulls
Actionshttps://github.com/python/cpython/actions
Projectshttps://github.com/python/cpython/projects
Security and qualityhttps://github.com/python/cpython/security
Insightshttps://github.com/python/cpython/insights
Sign up for GitHub https://github.com/signup?return_to=%2Fpython%2Fcpython%2Fissues%2Fnew%2Fchoose
terms of servicehttps://docs.github.com/terms
privacy statementhttps://docs.github.com/privacy
Sign inhttps://github.com/login?return_to=%2Fpython%2Fcpython%2Fissues%2Fnew%2Fchoose
ambvhttps://github.com/ambv
python:mainhttps://github.com/python/cpython/tree/main
cfbolz:unicodenames-dawghttps://github.com/cfbolz/cpython/tree/unicodenames-dawg
Conversation 70 https://github.com/python/cpython/pull/97906
Commits 42 https://github.com/python/cpython/pull/97906/commits
Checks 0 https://github.com/python/cpython/pull/97906/checks
Files changed https://github.com/python/cpython/pull/97906/files
Please reload this pagehttps://github.com/python/cpython/pull/97906/files
gh-96954: use a directed acyclic word graph for storing the unicodedata codepoint names https://github.com/python/cpython/pull/97906/files#top
Show all changes 42 commits https://github.com/python/cpython/pull/97906/files
0fb902f intermediate commit: start working on porting pypy dawg to store unic… cfbolz Sep 20, 2022 https://github.com/python/cpython/pull/97906/commits/0fb902fb8051ce2401e5cc3fd02e537592b6c174
80a8470 start porting lookup to the compact DAWG cfbolz Sep 20, 2022 https://github.com/python/cpython/pull/97906/commits/80a8470ca15bb6c995a08ce601a326c8579b70a2
8e22650 implement inverse lookup cfbolz Sep 20, 2022 https://github.com/python/cpython/pull/97906/commits/8e2265066612123fc596aee72e930155cdd7fc74
ab8ee48 cleanup script cfbolz Sep 20, 2022 https://github.com/python/cpython/pull/97906/commits/ab8ee483d5364cc9e25c2e283272313ef87bdb6c
d72faa3 refactor a bit cfbolz Sep 20, 2022 https://github.com/python/cpython/pull/97906/commits/d72faa30b512d7f5508aacdb5a46e2f654c65d24
4478542 add comments, some cleanup cfbolz Sep 21, 2022 https://github.com/python/cpython/pull/97906/commits/44785424de9da796549d05314b853a6f7b0ea262
c307224 fix inverse lookup cfbolz Sep 21, 2022 https://github.com/python/cpython/pull/97906/commits/c307224ca9eb4d4116d1b57eeb7e1ac9d958d224
2f663b2 check that names are actually shorter than NAME_MAXLEN cfbolz Sep 21, 2022 https://github.com/python/cpython/pull/97906/commits/2f663b20973872e7644d9f79d6def4d47739a885
1102b6a explain why we can't use topological sorting cfbolz Oct 4, 2022 https://github.com/python/cpython/pull/97906/commits/1102b6a2bafee86bcdde7d673ffc3a2e48f907a5
fba25e3 use topological sorting, found a way to do it cfbolz Oct 5, 2022 https://github.com/python/cpython/pull/97906/commits/fba25e3bef99b3a4884ade090607a6456addc189
330ef08 Merge remote-tracking branch 'origin/main' into unicodenames-dawg cfbolz Oct 5, 2022 https://github.com/python/cpython/pull/97906/commits/330ef08fbdd8e674d636c545d60765cf02c8448e
7bccc32 fix: make sure that looking up lower case unicode names works cfbolz Oct 5, 2022 https://github.com/python/cpython/pull/97906/commits/7bccc32a9d34f4e31e977fa4ea67ba674aa43ca5
4e4eb7a update comment cfbolz Oct 5, 2022 https://github.com/python/cpython/pull/97906/commits/4e4eb7aaa09a8c9dac9c3f32e73173dc0fe6eb56
b7ad39e 3.2.0 doesn't have aliases or named sequences cfbolz Oct 5, 2022 https://github.com/python/cpython/pull/97906/commits/b7ad39ea047fbf86be64321a506c83aaf2d8331d
a577528 move the handling of from _getcode into the two callers cfbolz Oct 5, 2022 https://github.com/python/cpython/pull/97906/commits/a57752828d352db0db40791cd0c81b298450d7fd
489b1d5 blurb cfbolz Oct 5, 2022 https://github.com/python/cpython/pull/97906/commits/489b1d59f289e950bb6c2956906ae4b6a53dc160
999c106 maybe fix ReST cfbolz Oct 5, 2022 https://github.com/python/cpython/pull/97906/commits/999c1069e6a22a31858c4c6efc036d84ab41775d
a7742e3 fix whitespace, don't know what happened here cfbolz Oct 5, 2022 https://github.com/python/cpython/pull/97906/commits/a7742e37c513c2988f9c5230a2d01c6b4f3b0aee
28102ad consistently use unsigned ints everywhere cfbolz Oct 5, 2022 https://github.com/python/cpython/pull/97906/commits/28102ade7c90479ed10eef801e83a69c09e32292
2ec1438 small simplification cfbolz Oct 5, 2022 https://github.com/python/cpython/pull/97906/commits/2ec1438cc48d2bb6ba0f1b855d6c6d9176813564
c5039c5 do a cleanup pass after Łukasz feedback cfbolz Oct 6, 2022 https://github.com/python/cpython/pull/97906/commits/c5039c57dd040acabaad8044b63070d097229c8e
bd8d80b use Py_SAFE_DOWNCAST, nicer str calls cfbolz Oct 10, 2022 https://github.com/python/cpython/pull/97906/commits/bd8d80bddfd353ba1aa27b6b96bfa19da2f0a67f
a87d561 use a cached_property for num_reachable_linear cfbolz Oct 10, 2022 https://github.com/python/cpython/pull/97906/commits/a87d561c128cf12caedeadff04c67161b9e8ad1d
d9b45ae add tests for unicodedata.lookup and .name which actually fail cfbolz Oct 10, 2022 https://github.com/python/cpython/pull/97906/commits/d9b45ae2a5db651bf03bbcb5c5af55e020bd8d5d
827100a Merge branch 'main' into unicodenames-dawg cfbolz Oct 10, 2022 https://github.com/python/cpython/pull/97906/commits/827100a1a2c39f96f83818c467ee19cd417f67aa
4443289 Merge branch 'main' into unicodenames-dawg cfbolz May 29, 2023 https://github.com/python/cpython/pull/97906/commits/4443289f5bce480a4cac29852bb2a9720480f399
75c8550 Merge branch 'main' into unicodenames-dawg ambv Oct 18, 2023 https://github.com/python/cpython/pull/97906/commits/75c8550233fa5eabfd4bd78e794daefee7a9fc84
3c3a9db Update unicodename_db.h after upgrade to Unicode 15 in GH-96809 ambv Oct 18, 2023 https://github.com/python/cpython/pull/97906/commits/3c3a9dbeb1446f19e321df93f5c808eec4d6c6ef
a627d7b update space saving numbers after unicode 15.1 cfbolz Oct 18, 2023 https://github.com/python/cpython/pull/97906/commits/a627d7b31567c2a8ff7d92fc5ffae9d7b7ec71ef
6735494 actually update Objects/unicodetype_db.h as well cfbolz Oct 18, 2023 https://github.com/python/cpython/pull/97906/commits/6735494caf1b8bc80229cd8bad8ac0522bb5d9a8
a3a8b58 no, I was wrong about the size, the effect isn't that huge cfbolz Oct 18, 2023 https://github.com/python/cpython/pull/97906/commits/a3a8b585f6cafaaafdda161f0abd41c3fa50061e
8fb106a add makefile target for regenerating the unicodedata cfbolz Oct 18, 2023 https://github.com/python/cpython/pull/97906/commits/8fb106a640d6893f311398a7962e6ad6e46ec2aa
8b52621 always check the result of dawg generation at construction time cfbolz Oct 22, 2023 https://github.com/python/cpython/pull/97906/commits/8b52621015ef34c6ee25a9e3657d0106e82fb8dd
57af105 more sensible __hash__ and __eq__ cfbolz Oct 22, 2023 https://github.com/python/cpython/pull/97906/commits/57af105a18de0bc78f8a890c41328c920c9c904d
3148c85 improve comments and docstrings cfbolz Oct 22, 2023 https://github.com/python/cpython/pull/97906/commits/3148c85651f8c3282af66056f16c7b4934590883
a6deecf rename confusingly named argument cfbolz Oct 22, 2023 https://github.com/python/cpython/pull/97906/commits/a6deecf86bfce6da33e657f1a0989b447571df4a
cc3600f add unittests for the dawg code cfbolz Oct 23, 2023 https://github.com/python/cpython/pull/97906/commits/cc3600fd65ffb5812f1977f381923b931d3dceff
cccf356 fix fixpoint bug cfbolz Oct 23, 2023 https://github.com/python/cpython/pull/97906/commits/cccf356bb94472eed61200a1c4c218f503eaa0a0
776bd1a fix comment cfbolz Oct 23, 2023 https://github.com/python/cpython/pull/97906/commits/776bd1a43b2592694a0a45bade46cedaf0b2e0f8
1cb4a69 fix typo cfbolz Nov 3, 2023 https://github.com/python/cpython/pull/97906/commits/1cb4a695afc72b34c77514bcc354af6e946ba45a
d49e871 clearer names cfbolz Nov 3, 2023 https://github.com/python/cpython/pull/97906/commits/d49e871fe71b8b9a535af6caeec5f3f8e485bd7b
dfb0580 check for empty dawg cfbolz Nov 3, 2023 https://github.com/python/cpython/pull/97906/commits/dfb0580705408e3f1daf732b203cf521ffc2af61
Clear filters https://github.com/python/cpython/pull/97906/files
Please reload this pagehttps://github.com/python/cpython/pull/97906/files
Please reload this pagehttps://github.com/python/cpython/pull/97906/files
test_makeunicodedata.py https://github.com/python/cpython/pull/97906/files#diff-1cef045fc50d1679324bded3b78b2183a980c8214c0e70d868f8532bb78eb641
test_unicodedata.py https://github.com/python/cpython/pull/97906/files#diff-c31ff7b8fca97de6b4fdaca3e14da27ab3cac411653e9c510a5378b189f909ea
Makefile.pre.in https://github.com/python/cpython/pull/97906/files#diff-1f0a8db227d22005511b0d90f5339b97db345917b863954b3b3ccb9ec308767c
2022-10-05-15-01-36.gh-issue-96954.ezwkrU.rst https://github.com/python/cpython/pull/97906/files#diff-372ed45e01f260ef615543328bba7a8af29b0ded4e8b1f4142be55bd75ed54bf
unicodedata.c https://github.com/python/cpython/pull/97906/files#diff-2cd482084cd623be20584ff84ef4b0ff781c0d955546048585a855156aedfa78
unicodename_db.h https://github.com/python/cpython/pull/97906/files#diff-72db487dcde1dbf76ffccc9e9627697dd45c2f90fd2cb2f6700e1e0192c36bdb
dawg.py https://github.com/python/cpython/pull/97906/files#diff-50fdbd5f2e89c5faf6e35f3b979591103e4abf8e3a9ed9e8c22899b381875f10
makeunicodedata.py https://github.com/python/cpython/pull/97906/files#diff-17ec60c9bf5044a66fffc2f5bd5b6c4a6df192332bd2762ddf4336a80f8f8f25
Lib/test/test_tools/test_makeunicodedata.pyhttps://github.com/python/cpython/pull/97906/files#diff-1cef045fc50d1679324bded3b78b2183a980c8214c0e70d868f8532bb78eb641
View file https://github.com/cfbolz/cpython/blob/dfb0580705408e3f1daf732b203cf521ffc2af61/Lib/test/test_tools/test_makeunicodedata.py
Open in desktop https://desktop.github.com
https://github.co/hiddenchars
https://github.com/python/cpython/pull/97906/{{ revealButtonHref }}
Lib/test/test_unicodedata.pyhttps://github.com/python/cpython/pull/97906/files#diff-c31ff7b8fca97de6b4fdaca3e14da27ab3cac411653e9c510a5378b189f909ea
View file https://github.com/cfbolz/cpython/blob/dfb0580705408e3f1daf732b203cf521ffc2af61/Lib/test/test_unicodedata.py
Open in desktop https://desktop.github.com
https://github.co/hiddenchars
https://github.com/python/cpython/pull/97906/{{ revealButtonHref }}
https://github.com/python/cpython/pull/97906/files#diff-c31ff7b8fca97de6b4fdaca3e14da27ab3cac411653e9c510a5378b189f909ea
https://github.com/python/cpython/pull/97906/files#diff-c31ff7b8fca97de6b4fdaca3e14da27ab3cac411653e9c510a5378b189f909ea
https://github.com/python/cpython/blob/main/.github/CODEOWNERS#L85
Makefile.pre.inhttps://github.com/python/cpython/pull/97906/files#diff-1f0a8db227d22005511b0d90f5339b97db345917b863954b3b3ccb9ec308767c
View file https://github.com/cfbolz/cpython/blob/dfb0580705408e3f1daf732b203cf521ffc2af61/Makefile.pre.in
Open in desktop https://desktop.github.com
https://github.co/hiddenchars
https://github.com/python/cpython/pull/97906/{{ revealButtonHref }}
https://github.com/python/cpython/pull/97906/files#diff-1f0a8db227d22005511b0d90f5339b97db345917b863954b3b3ccb9ec308767c
https://github.com/python/cpython/pull/97906/files#diff-1f0a8db227d22005511b0d90f5339b97db345917b863954b3b3ccb9ec308767c
https://github.com/python/cpython/pull/97906/files#diff-1f0a8db227d22005511b0d90f5339b97db345917b863954b3b3ccb9ec308767c
Misc/NEWS.d/next/Library/2022-10-05-15-01-36.gh-issue-96954.ezwkrU.rsthttps://github.com/python/cpython/pull/97906/files#diff-372ed45e01f260ef615543328bba7a8af29b0ded4e8b1f4142be55bd75ed54bf
View file https://github.com/cfbolz/cpython/blob/dfb0580705408e3f1daf732b203cf521ffc2af61/Misc/NEWS.d/next/Library/2022-10-05-15-01-36.gh-issue-96954.ezwkrU.rst
Open in desktop https://desktop.github.com
https://github.co/hiddenchars
https://github.com/python/cpython/pull/97906/{{ revealButtonHref }}
Please reload this pagehttps://github.com/python/cpython/pull/97906/files
https://github.com
Termshttps://docs.github.com/site-policy/github-terms/github-terms-of-service
Privacyhttps://docs.github.com/site-policy/privacy-policies/github-privacy-statement
Securityhttps://github.com/security
Statushttps://www.githubstatus.com/
Communityhttps://github.community/
Docshttps://docs.github.com/
Contacthttps://support.github.com?tags=dotcom-footer

Viewport: width=device-width


URLs of crawlers that visited me.