search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.44k stars 480 forks source link

Rename change the hash value of some objects #8119

Closed hivert closed 12 years ago

hivert commented 14 years ago

For many objects the hash value is computed from __repr__. This is a bad idea since renaming the object change its hash value.

sage: bla = PolynomialRing(ZZ,"x")
sage: hash(bla)
-1525918542791298668
sage: bla.rename("toto")
sage: hash(bla)
2314052222105390764

Apply Only:

  1. attachment: 8119-parent-hash-final.patch

CC: @jasongrout @simon-king-jena

Component: misc

Author: Robert Bradshaw

Reviewer: Florent Hivert, Nicolas M. Thiéry, Nicolas Borie

Merged: sage-5.0.rc0

Issue created by migration from https://trac.sagemath.org/ticket/8119

robertwb commented 14 years ago
comment:1

For immutable objects, like Parents, the default __hash__ could store the value used the first time it is computed. This doesn't solve the problem of 

sage: bla = PolynomialRing(ZZ,"x")
sage: hash(bla['t'])
-1733828288
sage: bla.rename("toto")
sage: hash(bla['t'])
-1924319844
robertwb commented 14 years ago

Attachment: 8119-parent-hash.patch.gz

robertwb commented 14 years ago
comment:2

This is a partial fix (that won't work for SageObject in general, unless we enforce that mutable objects maintain their own hash, and I don't think we want to put an extra field on all Elements), but resolves the most important case. It's also a performance gain.

hivert commented 14 years ago
comment:3

Hi Robert,

I've one question related to this and I like to have the confirmation from an expert. After your patch, upon pickling/unpickling the hash value can change because it is not pickled and neither is the name, right ? As far as I manage to test this is not harmful to pickle a dict containing a renamed parent. Indeed, trying to read cPickle.c, I understood that the dict is reconstructed from it's items and thus even if the hash changed the element is inserted correctly in the dict during unpickling. Can you confirm this ?

If this is not both this patch and #8120 are broken.

Also, after this, do you still need #8506 ?

Florent

robertwb commented 14 years ago
comment:4

Replying to @hivert:

Hi Robert,

I've one question related to this and I like to have the confirmation from an expert. After your patch, upon pickling/unpickling the hash value can change because it is not pickled and neither is the name, right ? As far as I manage to test this is not harmful to pickle a dict containing a renamed parent. Indeed, trying to read cPickle.c, I understood that the dict is reconstructed from it's items and thus even if the hash changed the element is inserted correctly in the dict during unpickling. Can you confirm this ?

That is correct. Hashes in general are not guaranteed to be consistent from run to run, all that really matters is that they satisfy (to the best they can) the equality constraints.

If this is not both this patch and #8120 are broken.

Also, after this, do you still need #8506 ?

Yes, #8506 is still important--in my case I'm reducing a curve mod many, many primes, doing just a bit of stuff on each before throwing them away. I suppose eventually caching the hash value would eventually be a win, but that's a separate optimization.

jasongrout commented 14 years ago
comment:6

hivert: do you want to review this ticket?

hivert commented 13 years ago
comment:7

hivert: do you want to review this ticket?

Sure ! I completely forgot about this one. Sorry !

They are a few place where we should remove the bad implementation using __repr__ since they all inherits from CategoryObject: 

popcorn-*ge-combinat/sage $ grep "hash(self.__repr__())" **/*.py*
groups/group.pyx:        return hash(self.__repr__())
modules/module.pyx:        return hash(self.__repr__())
modules/module.pyx:        return hash(self.__repr__())
rings/polynomial/multi_polynomial_libsingular.pyx:        return hash(self.__repr__())
rings/ring.pyx:        return hash(self.__repr__())
structure/sage_object.pyx:        return hash(self.__repr__())

I don't have time to do it right now. I'll do it soon if you don't beat me.

hivert commented 13 years ago

Reviewer: Florent Hivert

hivert commented 13 years ago
comment:8

They are a few place where we should remove the bad implementation using __repr__ since they all inherits from CategoryObject:

I just added a review patch which removes the wrong hash methods.

Please review. I'm ok with the original patch, so if my review patch is ok you can put a positive review on my behalf.

hivert commented 13 years ago

Description changed:

--- 
+++ 
@@ -8,3 +8,8 @@
 sage: hash(bla)
 2314052222105390764

+ +Apply: +1. attachment: 8119-parent-hash.patch +2. attachment: 8119-parent-hash-review.patch +

nthiery commented 13 years ago
comment:9

Attachment: 8119-parent-hash-review.patch.gz

Florent's review patch looks good. However consistant* should be writtenconsistent* in the first patch. I also did not yet set a positive review because of the ongoing discussion on sage-devel. Please feel free to go ahead and set a positive review once the typo is fixed and if it is decided that the PolynomialRing issue shall be fixed in a follow up patch.

Cheers, Nicolas

nthiery commented 13 years ago

Author: Robert Bradshaw

nthiery commented 13 years ago

Changed reviewer from Florent Hivert to Florent Hivert, Nicolas M. Thiéry

robertwb commented 13 years ago
comment:10

Attachment: 8119-parent-hash.2.patch.gz

Fixed the typo, I don't think the issue with sparse PolynomialRing #11231 should hold this ticket up any longer (it's had a patch sitting on it for over a year...)

jdemeyer commented 13 years ago

Description changed:

--- 
+++ 
@@ -10,6 +10,6 @@

Apply: -1. attachment: 8119-parent-hash.patch +1. attachment: 8119-parent-hash.2.patch

  1. attachment: 8119-parent-hash-review.patch
jdemeyer commented 13 years ago
comment:11

I'm assuming the "apply" should be changed...

jdemeyer commented 13 years ago
comment:12

Please change the commit message of attachment: 8119-parent-hash.2.patch (use hg qrefresh -e for that).

hivert commented 13 years ago
comment:13

Attachment: 8119-parent-hash.3.patch.gz

I just re-uploaded roberts patch with a correct log message. I'm not sure I'm allowed to put a positive review though.

Florent

hivert commented 13 years ago

Description changed:

--- 
+++ 
@@ -10,6 +10,6 @@

Apply: -1. attachment: 8119-parent-hash.2.patch +1. attachment: 8119-parent-hash.3.patch

  1. attachment: 8119-parent-hash-review.patch
nthiery commented 13 years ago
comment:14

Bonjour Florent!

I am not sure the log message for 8119-parent-hash-review.patch is proper. While you are at it, I'd suggest to just fold it in the other patch. The review history does not bring much information here, so having a single patch will give a better overview to the future reader.

I'll set a positive review right after.

hivert commented 13 years ago

Description changed:

--- 
+++ 
@@ -9,7 +9,6 @@
 2314052222105390764

-Apply: -1. attachment: 8119-parent-hash.3.patch -2. attachment: 8119-parent-hash-review.patch +Apply Only: +1. attachment: 8119-parent-hash-final.patch

hivert commented 13 years ago
comment:15

I'd suggest to just fold it in the other patch.

Done.

nthiery commented 13 years ago
comment:17

Thanks!

It seems the buildbot is getting confused about which patch to apply though.

robertwb commented 13 years ago
comment:18

Apply 8119-parent-hash-final.patch

Granted, the patchbot doesn't bother testing positively reviewed tickets (not that anything it's concerned with changed). Thanks for getting to this for me.

jdemeyer commented 13 years ago
comment:19

Some of these doctests should be differentiated on 32-bit systems (in particular, all the results of hash()).

jdemeyer commented 13 years ago

Work Issues: fix on 32-bit

jdemeyer commented 13 years ago
comment:20

bump

0f5ae6f6-e03a-45d9-b571-4ce01615e676 commented 12 years ago

Description changed:

--- 
+++ 
@@ -10,5 +10,5 @@

Apply Only: -1. attachment: 8119-parent-hash-final.patch +1. attachment: 8119-parent-hash-final-fix32.patch

hivert commented 12 years ago

Changed work issues from fix on 32-bit to none

hivert commented 12 years ago

Changed reviewer from Florent Hivert, Nicolas M. Thiéry to Florent Hivert, Nicolas M. Thiéry, Nicolas Borie

jdemeyer commented 12 years ago
comment:23

On boxen (Linux x86_64), I get:

sage -t  -force_lib devel/sage/sage/structure/category_object.pyx
**********************************************************************
File "/padic/scratch/jdemeyer/merger/sage-5.0.beta14/devel/sage-main/sage/structure/category_object.pyx", line 757:
    sage: hash(bla)
Expected:
    -1525918542791298668
Got:
    -5279516879544852222
**********************************************************************
File "/padic/scratch/jdemeyer/merger/sage-5.0.beta14/devel/sage-main/sage/structure/category_object.pyx", line 761:
    sage: hash(bla)
Expected:
    -1525918542791298668
Got:
    -5279516879544852222
**********************************************************************
nthiery commented 12 years ago
comment:24

Attachment: 8119-parent-hash-final-fix32.patch.gz

Replying to @jdemeyer:

On boxen (Linux x86_64), I get:

sage -t  -force_lib devel/sage/sage/structure/category_object.pyx
**********************************************************************
File "/padic/scratch/jdemeyer/merger/sage-5.0.beta14/devel/sage-main/sage/structure/category_object.pyx", line 757:
    sage: hash(bla)
Expected:
    -1525918542791298668
Got:
    -5279516879544852222
**********************************************************************
File "/padic/scratch/jdemeyer/merger/sage-5.0.beta14/devel/sage-main/sage/structure/category_object.pyx", line 761:
    sage: hash(bla)
Expected:
    -1525918542791298668
Got:
    -5279516879544852222
**********************************************************************

Weird, I get here the same result as you on boxen, both with 4.8 and 5.0.beta8. I don't know how a wrong return value ended up in the patch.

Oh well, I updated the patch to expect the result obtained on boxen.

11d1fc49-71a1-44e1-869f-76be013245a0 commented 12 years ago
comment:26

Apply 8119-parent-hash-final-fix32.patch

(for patchbot)

hivert commented 12 years ago

Attachment: 8119-parent-hash-final.patch.gz

hivert commented 12 years ago

Description changed:

--- 
+++ 
@@ -10,5 +10,5 @@

Apply Only: -1. attachment: 8119-parent-hash-final-fix32.patch +1. attachment: 8119-parent-hash-final.patch

hivert commented 12 years ago
comment:28

Hi there,

I'm setting a positive review here but I uploaded a new patch removing a trailling whitespace which bothered the patchbot. The only difference between attachment: 8119-parent-hash-final-fix32.patch and attachment: 8119-parent-hash-final.patch is the trailling space (and of course Mercurials header), so I don't think a new review is needed.

Florent

nthiery commented 12 years ago
comment:29

Thanks for the final review!

jdemeyer commented 12 years ago

Merged: sage-5.0.rc0