Rename change the hash value of some objects

[hivert]

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]

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]

Attachment: 8119-parent-hash.patch.gz

[robertwb]

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]

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]

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]

comment:6

hivert: do you want to review this ticket?

[hivert]

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]

Reviewer: Florent Hivert

[hivert]

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.

[nthiery]

comment:9

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

Florent's review patch looks good. However consistant* should be written consistent* 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]

Author: Robert Bradshaw

[nthiery]

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

[robertwb]

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]

comment:11

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

[robertwb]

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]

comment:19

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

[jdemeyer]

Work Issues: fix on 32-bit

[jdemeyer]

comment:20

bump

[hivert]

Changed work issues from fix on 32-bit to none

[hivert]

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

[jdemeyer]

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]

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.

[loefflerd]

comment:26

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

(for patchbot)

[hivert]

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

[hivert]

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]

comment:29

Thanks for the final review!

[jdemeyer]

Merged: sage-5.0.rc0