* Changed all copyright messages to include 1993.

* Stubs for faster implementation of local variables (not yet finished)
* Added function name to code object.  Print it for code and function
  objects.  THIS MAKES THE .PYC FILE FORMAT INCOMPATIBLE (the version
  number has changed accordingly)
* Print address of self for built-in methods
* New internal functions getattro and setattro (getattr/setattr with
  string object arg)
* Replaced "dictobject" with more powerful "mappingobject"
* New per-type functio tp_hash to implement arbitrary object hashing,
  and hashobject() to interface to it
* Added built-in functions hash(v) and hasattr(v, 'name')
* classobject: made some functions static that accidentally weren't;
  added __hash__ special instance method to implement hash()
* Added proper comparison for built-in methods and functions

14 files changed, 273 insertions, 43 deletions

diff --git a/Objects/classobject.c b/Objects/classobject.c
index 95b85f5..823e397 100644
--- a/Objects/classobject.c
+++ b/Objects/classobject.c
@@ -261,7 +261,7 @@ instance_setattr(inst, name, v)
 		return dictinsert(inst->in_attr, name, v);
 }
 
-object *
+static object *
 instance_repr(inst)
 	instanceobject *inst;
 {
@@ -280,7 +280,7 @@ instance_repr(inst)
 	return res;
 }
 
-int
+static int
 instance_compare(inst, other)
 	instanceobject *inst, *other;
 {
@@ -311,7 +311,43 @@ instance_compare(inst, other)
 	return outcome;
 }
 
-int
+static long
+instance_hash(inst)
+	instanceobject *inst;
+{
+	object *func;
+	object *res;
+	int outcome;
+
+	func = instance_getattr(inst, "__hash__");
+	if (func == NULL) {
+		/* If there is no __cmp__ method, we hash on the address.
+		   If a __cmp__ method exists, there must be a __hash__. */
+		err_clear();
+		func = instance_getattr(inst, "__cmp__");
+		if (func == NULL)
+			return (long)inst;
+		err_setstr(TypeError, "unhashable instance");
+		return -1;
+	}
+	res = call_object(func, (object *)NULL);
+	DECREF(func);
+	if (res == NULL)
+		return -1;
+	if (is_intobject(res)) {
+		outcome = getintvalue(res);
+		if (outcome == -1)
+			outcome = -2;
+	}
+	else {
+		err_setstr(TypeError, "__hash__() should return an int");
+		outcome = -1;
+	}
+	DECREF(res);
+	return outcome;
+}
+
+static int
 instance_length(inst)
 	instanceobject *inst;
 {
@@ -339,7 +375,7 @@ instance_length(inst)
 	return outcome;
 }
 
-object *
+static object *
 instance_subscript(inst, key)
 	instanceobject *inst;
 	object *key;
@@ -362,7 +398,7 @@ instance_subscript(inst, key)
 	return res;
 }
 
-int
+static int
 instance_ass_subscript(inst, key, value)
 	instanceobject*inst;
 	object *key;
@@ -395,7 +431,7 @@ instance_ass_subscript(inst, key, value)
 	return 0;
 }
 
-mapping_methods instance_as_mapping = {
+static mapping_methods instance_as_mapping = {
 	instance_length,	/*mp_length*/
 	instance_subscript,	/*mp_subscript*/
 	instance_ass_subscript,	/*mp_ass_subscript*/
@@ -612,7 +648,7 @@ UNARY(instance_neg, "__neg__")
 UNARY(instance_pos, "__pos__")
 UNARY(instance_abs, "__abs__")
 
-int
+static int
 instance_nonzero(self)
 	instanceobject *self;
 {
@@ -739,9 +775,10 @@ typeobject Instancetype = {
 	&instance_as_number,	/*tp_as_number*/
 	&instance_as_sequence,	/*tp_as_sequence*/
 	&instance_as_mapping,	/*tp_as_mapping*/
+	instance_hash,		/*tp_hash*/
 };
 
-object *
+static object *
 instance_convert(inst, methodname)
 	object *inst;
 	char *methodname;
@@ -837,6 +874,20 @@ instancemethod_compare(a, b)
 	return cmp;
 }
 
+static long
+instancemethod_hash(a)
+	instancemethodobject *a;
+{
+	long x, y;
+	x = hashobject(a->im_self);
+	if (x == -1)
+		return -1;
+	y = hashobject(a->im_func);
+	if (y == -1)
+		return -1;
+	return x ^ y;
+}
+
 typeobject Instancemethodtype = {
 	OB_HEAD_INIT(&Typetype)
 	0,
@@ -852,4 +903,5 @@ typeobject Instancemethodtype = {
 	0,			/*tp_as_number*/
 	0,			/*tp_as_sequence*/
 	0,			/*tp_as_mapping*/
+	instancemethod_hash,	/*tp_hash*/
 };
diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index 1cfa308..fa66a9d 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -24,8 +24,13 @@ OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 
 /* Mapping object implementation; using a hash table */
 
+/* This file should really be called "dictobject.c", since "mapping"
+  is the generic name for objects with an unorderred arbitrary key
+  set (just like lists are sequences), but since it improves (and was
+  originally derived from) a file by that name I had to change its
+  name.  For the user these objects are still called "dictionaries". */
+
 #include "allobjects.h"
-#include "mappingobject.h"
 #include "modsupport.h"
 
 
@@ -593,7 +598,7 @@ mapping_getattr(mp, name)
 typeobject Mappingtype = {
 	OB_HEAD_INIT(&Typetype)
 	0,
-	"mapping",
+	"dictionary",
 	sizeof(mappingobject),
 	0,
 	mapping_dealloc,	/*tp_dealloc*/
diff --git a/Objects/floatobject.c b/Objects/floatobject.c
index e563583..8533e0e 100644
--- a/Objects/floatobject.c
+++ b/Objects/floatobject.c
@@ -145,6 +145,38 @@ float_compare(v, w)
 	return (i < j) ? -1 : (i > j) ? 1 : 0;
 }
 
+static long
+float_hash(v)
+	floatobject *v;
+{
+	double intpart, fractpart;
+	int expo;
+	long x;
+	/* This is designed so that Python numbers with the same
+	   value hash to the same value, otherwise comparisons
+	   of mapping keys will turn out weird */
+	fractpart = modf(v->ob_fval, &intpart);
+	if (fractpart == 0.0) {
+		if (intpart > 0x7fffffffL || -intpart > 0x7fffffffL) {
+			/* Convert to long int and use its hash... */
+			object *w = dnewlongobject(v->ob_fval);
+			if (w == NULL)
+				return -1;
+			x = hashobject(w);
+			DECREF(w);
+			return x;
+		}
+		x = (long)intpart;
+	}
+	else {
+		fractpart = frexp(fractpart, &expo);
+		x = (long) (intpart + fractpart) ^ expo; /* Rather arbitrary */
+	}
+	if (x == -1)
+		x = -2;
+	return x;
+}
+
 static object *
 float_add(v, w)
 	floatobject *v;
@@ -378,4 +410,5 @@ typeobject Floattype = {
 	&float_as_number,	/*tp_as_number*/
 	0,			/*tp_as_sequence*/
 	0,			/*tp_as_mapping*/
+	float_hash,		/*tp_hash */
 };
diff --git a/Objects/frameobject.c b/Objects/frameobject.c
index c7b5ddf..cec0502 100644
--- a/Objects/frameobject.c
+++ b/Objects/frameobject.c
@@ -1,6 +1,6 @@
 /***********************************************************
-Copyright 1991, 1992 by Stichting Mathematisch Centrum, Amsterdam, The
-Netherlands.
+Copyright 1991, 1992, 1993 by Stichting Mathematisch Centrum,
+Amsterdam, The Netherlands.
 
                         All Rights Reserved
 
diff --git a/Objects/funcobject.c b/Objects/funcobject.c
index a779ebb..ccf1b29 100644
--- a/Objects/funcobject.c
+++ b/Objects/funcobject.c
@@ -1,6 +1,6 @@
 /***********************************************************
-Copyright 1991, 1992 by Stichting Mathematisch Centrum, Amsterdam, The
-Netherlands.
+Copyright 1991, 1992, 1993 by Stichting Mathematisch Centrum,
+Amsterdam, The Netherlands.
 
                         All Rights Reserved
 
@@ -25,7 +25,7 @@ OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 /* Function object implementation */
 
 #include "allobjects.h"
-
+#include "compile.h"
 #include "structmember.h"
 
 typedef struct {
@@ -98,6 +98,17 @@ func_dealloc(op)
 	DEL(op);
 }
 
+static object*
+func_repr(op)
+	funcobject *op;
+{
+	char buf[140];
+	sprintf(buf, "<function %.100s at %lx>",
+		getstringvalue(((codeobject*)(op->func_code))->co_name),
+		(long)op);
+	return newstringobject(buf);
+}
+
 typeobject Functype = {
 	OB_HEAD_INIT(&Typetype)
 	0,
@@ -109,5 +120,5 @@ typeobject Functype = {
 	func_getattr,	/*tp_getattr*/
 	0,		/*tp_setattr*/
 	0,		/*tp_compare*/
-	0,		/*tp_repr*/
+	func_repr,	/*tp_repr*/
 };
diff --git a/Objects/intobject.c b/Objects/intobject.c
index 858458c..6806f0c 100644
--- a/Objects/intobject.c
+++ b/Objects/intobject.c
@@ -144,6 +144,16 @@ int_compare(v, w)
 	return (i < j) ? -1 : (i > j) ? 1 : 0;
 }
 
+static long
+int_hash(v)
+	intobject *v;
+{
+	long x = v -> ob_ival;
+	if (x == -1)
+		x = -2;
+	return x;
+}
+
 static object *
 int_add(v, w)
 	intobject *v;
@@ -413,7 +423,7 @@ int_or(v, w)
 
 static object *
 int_int(v)
-	object *v;
+	intobject *v;
 {
 	INCREF(v);
 	return v;
@@ -421,26 +431,24 @@ int_int(v)
 
 static object *
 int_long(v)
-	object *v;
+	intobject *v;
 {
-	long x = getintvalue(v);
-	return newlongobject(x);
+	return newlongobject((v -> ob_ival));
 }
 
 static object *
 int_float(v)
-	object *v;
+	intobject *v;
 {
-	long x = getintvalue(v);
-	return newfloatobject((double)x);
+	return newfloatobject((double)(v -> ob_ival));
 }
 
 static object *
 int_oct(v)
-	object *v;
+	intobject *v;
 {
 	char buf[20];
-	long x = getintvalue(v);
+	long x = v -> ob_ival;
 	if (x == 0)
 		strcpy(buf, "0");
 	else if (x > 0)
@@ -452,10 +460,10 @@ int_oct(v)
 
 static object *
 int_hex(v)
-	object *v;
+	intobject *v;
 {
 	char buf[20];
-	long x = getintvalue(v);
+	long x = v -> ob_ival;
 	if (x >= 0)
 		sprintf(buf, "0x%lx", x);
 	else
@@ -463,7 +471,6 @@ int_hex(v)
 	return newstringobject(buf);
 }
 
-
 static number_methods int_as_number = {
 	int_add,	/*nb_add*/
 	int_sub,	/*nb_subtract*/
@@ -505,4 +512,5 @@ typeobject Inttype = {
 	&int_as_number,	/*tp_as_number*/
 	0,		/*tp_as_sequence*/
 	0,		/*tp_as_mapping*/
+	&int_hash,	/*tp_hash*/
 };
diff --git a/Objects/longobject.c b/Objects/longobject.c
index 38473e2..fb82a1f 100644
--- a/Objects/longobject.c
+++ b/Objects/longobject.c
@@ -555,6 +555,7 @@ static void long_dealloc PROTO((object *));
 static int long_print PROTO((object *, FILE *, int));
 static object *long_repr PROTO((object *));
 static int long_compare PROTO((longobject *, longobject *));
+static long long_hash PROTO((longobject *));
 
 static object *long_add PROTO((longobject *, longobject *));
 static object *long_sub PROTO((longobject *, longobject *));
@@ -615,6 +616,35 @@ long_compare(a, b)
 	return sign < 0 ? -1 : sign > 0 ? 1 : 0;
 }
 
+static long
+long_hash(v)
+	longobject *v;
+{
+	long x;
+	int i, sign;
+
+	/* This is designed so that Python ints and longs with the
+	   same value hash to the same value, otherwise comparisons
+	   of mapping keys will turn out weird */
+	i = v->ob_size;
+	sign = 1;
+	x = 0;
+	if (i < 0) {
+		sign = -1;
+		i = -(i);
+	}
+	while (--i >= 0) {
+		/* Force a 32-bit circular shift */
+		x = ((x << SHIFT) & ~MASK) | ((x >> (32-SHIFT)) & MASK);
+		x += v->ob_digit[i];
+	}
+	x = x * sign;
+	if (x == -1)
+		x = -2;
+	return x;
+}
+
+
 /* Add the absolute values of two long integers. */
 
 static longobject *x_add PROTO((longobject *, longobject *));
@@ -1346,4 +1376,6 @@ typeobject Longtype = {
 	&long_as_number,/*tp_as_number*/
 	0,		/*tp_as_sequence*/
 	0,		/*tp_as_mapping*/
+	(long (*) FPROTO((object *)))
+	long_hash,	/*tp_hash*/
 };
diff --git a/Objects/mappingobject.c b/Objects/mappingobject.c
index 1cfa308..fa66a9d 100644
--- a/Objects/mappingobject.c
+++ b/Objects/mappingobject.c
@@ -24,8 +24,13 @@ OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 
 /* Mapping object implementation; using a hash table */
 
+/* This file should really be called "dictobject.c", since "mapping"
+  is the generic name for objects with an unorderred arbitrary key
+  set (just like lists are sequences), but since it improves (and was
+  originally derived from) a file by that name I had to change its
+  name.  For the user these objects are still called "dictionaries". */
+
 #include "allobjects.h"
-#include "mappingobject.h"
 #include "modsupport.h"
 
 
@@ -593,7 +598,7 @@ mapping_getattr(mp, name)
 typeobject Mappingtype = {
 	OB_HEAD_INIT(&Typetype)
 	0,
-	"mapping",
+	"dictionary",
 	sizeof(mappingobject),
 	0,
 	mapping_dealloc,	/*tp_dealloc*/
diff --git a/Objects/methodobject.c b/Objects/methodobject.c
index d0b29c7..d7ba02e 100644
--- a/Objects/methodobject.c
+++ b/Objects/methodobject.c
@@ -1,6 +1,6 @@
 /***********************************************************
-Copyright 1991, 1992 by Stichting Mathematisch Centrum, Amsterdam, The
-Netherlands.
+Copyright 1991, 1992, 1993 by Stichting Mathematisch Centrum,
+Amsterdam, The Netherlands.
 
                         All Rights Reserved
 
@@ -108,11 +108,41 @@ meth_repr(m)
 		sprintf(buf, "<built-in function '%.80s'>", m->m_name);
 	else
 		sprintf(buf,
-			"<built-in method '%.80s' of some %.80s object>",
-			m->m_name, m->m_self->ob_type->tp_name);
+			"<built-in method '%.80s' of %.80s object at %lx>",
+			m->m_name, m->m_self->ob_type->tp_name,
+			(long)m->m_self);
 	return newstringobject(buf);
 }
 
+static int
+meth_compare(a, b)
+	methodobject *a, *b;
+{
+	if (a->m_self != b->m_self)
+		return cmpobject(a->m_self, b->m_self);
+	if (a->m_meth == b->m_meth)
+		return 0;
+	if (strcmp(a->m_name, b->m_name) < 0)
+		return -1;
+	else
+		return 1;
+}
+
+static long
+meth_hash(a)
+	methodobject *a;
+{
+	long x, y;
+	if (a->m_self == NULL)
+		x = 0;
+	else {
+		x = hashobject(a->m_self);
+		if (x == -1)
+			return -1;
+	}
+	return x ^ (long) a->m_meth;
+}
+
 typeobject Methodtype = {
 	OB_HEAD_INIT(&Typetype)
 	0,
@@ -123,11 +153,12 @@ typeobject Methodtype = {
 	0,		/*tp_print*/
 	0,		/*tp_getattr*/
 	0,		/*tp_setattr*/
-	0,		/*tp_compare*/
+	meth_compare,	/*tp_compare*/
 	meth_repr,	/*tp_repr*/
 	0,		/*tp_as_number*/
 	0,		/*tp_as_sequence*/
 	0,		/*tp_as_mapping*/
+	meth_hash,	/*tp_hash*/
 };
 
 object *listmethods PROTO((struct methodlist *)); /* Forward */
diff --git a/Objects/moduleobject.c b/Objects/moduleobject.c
index 9733a77..749d872 100644
--- a/Objects/moduleobject.c
+++ b/Objects/moduleobject.c
@@ -1,6 +1,6 @@
 /***********************************************************
-Copyright 1991, 1992 by Stichting Mathematisch Centrum, Amsterdam, The
-Netherlands.
+Copyright 1991, 1992, 1993 by Stichting Mathematisch Centrum,
+Amsterdam, The Netherlands.
 
                         All Rights Reserved
 
diff --git a/Objects/object.c b/Objects/object.c
index 707dd58..9a8d4b3 100644
--- a/Objects/object.c
+++ b/Objects/object.c
@@ -1,6 +1,6 @@
 /***********************************************************
-Copyright 1991, 1992 by Stichting Mathematisch Centrum, Amsterdam, The
-Netherlands.
+Copyright 1991, 1992, 1993 by Stichting Mathematisch Centrum,
+Amsterdam, The Netherlands.
 
                         All Rights Reserved
 
@@ -165,6 +165,20 @@ cmpobject(v, w)
 	return (*tp->tp_compare)(v, w);
 }
 
+long
+hashobject(v)
+	object *v;
+{
+	typeobject *tp = v->ob_type;
+	if (tp->tp_hash != NULL)
+		return (*tp->tp_hash)(v);
+	if (tp->tp_compare == NULL)
+		return (long) v; /* Use address as hash value */
+	/* If there's a cmp but no hash defined, the object can't be hashed */
+	err_setstr(TypeError, "unhashable type");
+	return -1;
+}
+
 object *
 getattr(v, name)
 	object *v;
@@ -229,6 +243,7 @@ static typeobject Notype = {
 	0,		/*tp_as_number*/
 	0,		/*tp_as_sequence*/
 	0,		/*tp_as_mapping*/
+	0,		/*tp_hash */
 };
 
 object NoObject = {
diff --git a/Objects/stringobject.c b/Objects/stringobject.c
index 25f12fc..5c7345d 100644
--- a/Objects/stringobject.c
+++ b/Objects/stringobject.c
@@ -293,6 +293,21 @@ string_compare(a, b)
 	return (len_a < len_b) ? -1 : (len_a > len_b) ? 1 : 0;
 }
 
+static long
+string_hash(a)
+	stringobject *a;
+{
+	register int len = a->ob_size;
+	register unsigned char *p = (unsigned char *) a->ob_sval;
+	register long x = *p << 7;
+	while (--len >= 0)
+		x = (x + x + x) ^ *p++;
+	x ^= a->ob_size;
+	if (x == -1)
+		x = -2;
+	return x;
+}
+
 static sequence_methods string_as_sequence = {
 	string_length,	/*sq_length*/
 	string_concat,	/*sq_concat*/
@@ -318,6 +333,7 @@ typeobject Stringtype = {
 	0,		/*tp_as_number*/
 	&string_as_sequence,	/*tp_as_sequence*/
 	0,		/*tp_as_mapping*/
+	string_hash,	/*tp_hash*/
 };
 
 void
diff --git a/Objects/tupleobject.c b/Objects/tupleobject.c
index 0875a0c..9eb332b 100644
--- a/Objects/tupleobject.c
+++ b/Objects/tupleobject.c
@@ -1,6 +1,6 @@
 /***********************************************************
-Copyright 1991, 1992 by Stichting Mathematisch Centrum, Amsterdam, The
-Netherlands.
+Copyright 1991, 1992, 1993 by Stichting Mathematisch Centrum,
+Amsterdam, The Netherlands.
 
                         All Rights Reserved
 
@@ -179,6 +179,27 @@ tuplecompare(v, w)
 	return v->ob_size - w->ob_size;
 }
 
+static long
+tuplehash(v)
+	tupleobject *v;
+{
+	register long x, y;
+	register int len = v->ob_size;
+	register object **p;
+	x = 0x345678L;
+	p = v->ob_item;
+	while (--len >= 0) {
+		y = hashobject(*p++);
+		if (y == -1)
+			return -1;
+		x = (x + x + x) ^ y;
+	}
+	x ^= v->ob_size;
+	if (x == -1)
+		x = -2;
+	return x;
+}
+
 static int
 tuplelength(a)
 	tupleobject *a;
@@ -329,4 +350,5 @@ typeobject Tupletype = {
 	0,		/*tp_as_number*/
 	&tuple_as_sequence,	/*tp_as_sequence*/
 	0,		/*tp_as_mapping*/
+	tuplehash,	/*tp_hash*/
 };
diff --git a/Objects/typeobject.c b/Objects/typeobject.c
index f78d280..7176008 100644
--- a/Objects/typeobject.c
+++ b/Objects/typeobject.c
@@ -1,6 +1,6 @@
 /***********************************************************
-Copyright 1991, 1992 by Stichting Mathematisch Centrum, Amsterdam, The
-Netherlands.
+Copyright 1991, 1992, 1993 by Stichting Mathematisch Centrum,
+Amsterdam, The Netherlands.
 
                         All Rights Reserved