Skip to content

Fix contextvars HAMT implementation to handle iteration over deep trees #93065

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Closed
1st1 opened this issue May 22, 2022 · 3 comments
Closed

Fix contextvars HAMT implementation to handle iteration over deep trees #93065

1st1 opened this issue May 22, 2022 · 3 comments
Assignees
@1st1
Labels
type-bug An unexpected behavior, bug, or error

Comments

@1st1
Copy link
Member

1st1 commented May 22, 2022

See MagicStack/immutables#84 for more details.
@1st1 1st1 added the type-bug An unexpected behavior, bug, or error label May 22, 2022
@1st1
Copy link
Member Author

1st1 commented May 22, 2022 •
edited
Loading

PR: #93066

@1st1 1st1 self-assigned this May 22, 2022
@molaxx
Copy link
Contributor

molaxx commented May 22, 2022

Hey @1st1 as I found the bug and fixed it, can I open the PR in cpython? i'll be honored to have a PR accepted in CPython!

1st1 added a commit to 1st1/cpython that referenced this issue May 22, 2022
@molaxx @1st1
pythongh-93065: Fix HAMT to iterate correctly over 7-level deep trees.
4216b2b 
Also while there, clarify a few things about why we reduce
the hash to 32 bits.

Co-authored-by: Yury Selivanov <yury@edgedb.com>
@vstinner vstinner mentioned this issue May 23, 2022
Merged
miss-islington pushed a commit to miss-islington/cpython that referenced this issue May 23, 2022
@1st1 @miss-islington
pythongh-93065: Fix HAMT to iterate correctly over 7-level deep trees (…
3eb4b54 
…pythonGH-93066)

Also while there, clarify a few things about why we reduce the hash to 32 bits.

Co-authored-by: Eli Libman <eli@hyro.ai>
Co-authored-by: Yury Selivanov <yury@edgedb.com>
Co-authored-by: Łukasz Langa <lukasz@langa.pl>
(cherry picked from commit c1f5c90)

Co-authored-by: Yury Selivanov <yury@edgedb.com>
miss-islington pushed a commit to miss-islington/cpython that referenced this issue May 23, 2022
@1st1 @miss-islington
pythongh-93065: Fix HAMT to iterate correctly over 7-level deep trees (…
dc2c9fe 
…pythonGH-93066)

Also while there, clarify a few things about why we reduce the hash to 32 bits.

Co-authored-by: Eli Libman <eli@hyro.ai>
Co-authored-by: Yury Selivanov <yury@edgedb.com>
Co-authored-by: Łukasz Langa <lukasz@langa.pl>
(cherry picked from commit c1f5c90)

Co-authored-by: Yury Selivanov <yury@edgedb.com>
ambv added a commit that referenced this issue May 23, 2022
@1st1 @molaxx @ambv
gh-93065: Fix HAMT to iterate correctly over 7-level deep trees (GH-9…
c1f5c90 
…3066)

Also while there, clarify a few things about why we reduce the hash to 32 bits.

Co-authored-by: Eli Libman <eli@hyro.ai>
Co-authored-by: Yury Selivanov <yury@edgedb.com>
Co-authored-by: Łukasz Langa <lukasz@langa.pl>
miss-islington pushed a commit to miss-islington/cpython that referenced this issue May 23, 2022
@1st1 @miss-islington
pythongh-93065: Fix HAMT to iterate correctly over 7-level deep trees (…
3a99e8e 
…pythonGH-93066)

Also while there, clarify a few things about why we reduce the hash to 32 bits.

Co-authored-by: Eli Libman <eli@hyro.ai>
Co-authored-by: Yury Selivanov <yury@edgedb.com>
Co-authored-by: Łukasz Langa <lukasz@langa.pl>
(cherry picked from commit c1f5c90)

Co-authored-by: Yury Selivanov <yury@edgedb.com>
ambv pushed a commit to ambv/cpython that referenced this issue May 23, 2022
@1st1 @ambv
[3.8] pythongh-93065: Fix HAMT to iterate correctly over 7-level deep…
563ad16 
… trees (pythonGH-93066)

Also while there, clarify a few things about why we reduce the hash to 32 bits.

Co-authored-by: Eli Libman <eli@hyro.ai>
Co-authored-by: Yury Selivanov <yury@edgedb.com>
Co-authored-by: Łukasz Langa <lukasz@langa.pl>
(cherry picked from commit c1f5c90)

Co-authored-by: Yury Selivanov <yury@edgedb.com>
ambv pushed a commit to ambv/cpython that referenced this issue May 23, 2022
@1st1 @ambv
[3.7] pythongh-93065: Fix HAMT to iterate correctly over 7-level deep…
df44b36 
… trees (pythonGH-93066)

Also while there, clarify a few things about why we reduce the hash to 32 bits.

Co-authored-by: Eli Libman <eli@hyro.ai>
Co-authored-by: Yury Selivanov <yury@edgedb.com>
Co-authored-by: Łukasz Langa <lukasz@langa.pl>
(cherry picked from commit c1f5c90)

Co-authored-by: Yury Selivanov <yury@edgedb.com>
ned-deily pushed a commit that referenced this issue May 23, 2022
@ambv @molaxx @1st1
[3.7] gh-93065: Fix HAMT to iterate correctly over 7-level deep trees (…
3a4ca49 
…GH-93149)

Also while there, clarify a few things about why we reduce the hash to 32 bits.

Co-authored-by: Eli Libman <eli@hyro.ai>
Co-authored-by: Yury Selivanov <yury@edgedb.com>
Co-authored-by: Łukasz Langa <lukasz@langa.pl>
(cherry picked from commit c1f5c90)
ambv pushed a commit that referenced this issue May 24, 2022
@miss-islington
gh-93065: Fix HAMT to iterate correctly over 7-level deep trees (GH-9…
a4bea26 
…3066) (GH-93146)

Also while there, clarify a few things about why we reduce the hash to 32 bits.

Co-authored-by: Eli Libman <eli@hyro.ai>
Co-authored-by: Yury Selivanov <yury@edgedb.com>
Co-authored-by: Łukasz Langa <lukasz@langa.pl>

(cherry picked from commit c1f5c90)
ambv pushed a commit that referenced this issue May 24, 2022
@miss-islington
gh-93065: Fix HAMT to iterate correctly over 7-level deep trees (GH-9…
c771cbe 
…3066) (GH-93145)

Also while there, clarify a few things about why we reduce the hash to 32 bits.

Co-authored-by: Eli Libman <eli@hyro.ai>
Co-authored-by: Yury Selivanov <yury@edgedb.com>
Co-authored-by: Łukasz Langa <lukasz@langa.pl>

(cherry picked from commit c1f5c90)
ambv pushed a commit that referenced this issue May 24, 2022
@miss-islington
gh-93065: Fix HAMT to iterate correctly over 7-level deep trees (GH-9…
95c9c2b 
…3066) (#93147)

Also while there, clarify a few things about why we reduce the hash to 32 bits.

Co-authored-by: Eli Libman <eli@hyro.ai>
Co-authored-by: Yury Selivanov <yury@edgedb.com>
Co-authored-by: Łukasz Langa <lukasz@langa.pl>

(cherry picked from commit c1f5c90)
ambv added a commit that referenced this issue May 24, 2022
@ambv
[3.8] gh-93065: Fix HAMT to iterate correctly over 7-level deep trees (…
6d4927a 
…GH-93066) (#93148)

Also while there, clarify a few things about why we reduce the hash to 32 bits.

Co-authored-by: Eli Libman <eli@hyro.ai>
Co-authored-by: Yury Selivanov <yury@edgedb.com>
Co-authored-by: Łukasz Langa <lukasz@langa.pl>

(cherry picked from commit c1f5c90)
@ambv
Copy link
Contributor

ambv commented May 24, 2022

Fixed all the way between 3.7 and 3.12. Thanks, @molaxx and @1st1!

@ambv ambv closed this as completed May 24, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@1st1 1st1

Labels
type-bug An unexpected behavior, bug, or error
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@ambv @1st1 @molaxx