Update of /cvsroot/python/python/dist/src/Objects
In directory usw-pr-cvs1:/tmp/cvs-serv30146
Modified Files:
typeobject.c
Log Message:
Use the new C3 MRO algorithm, implemented by Samuele Pedroni (SF patch
619475; also closing SF bug 618704). I tweaked his code a bit for
style.
This raises TypeError for MRO order disagreements, which is an
improvement (previously these went undetected) but also a degradation:
what if the order disagreement doesn't affect any method lookups?
I don't think I care.
Index: typeobject.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/typeobject.c,v
retrieving revision 2.185
retrieving revision 2.186
diff -C2 -d -r2.185 -r2.186
*** typeobject.c 18 Oct 2002 16:33:12 -0000 2.185
--- typeobject.c 14 Nov 2002 19:49:16 -0000 2.186
***************
*** 614,677 ****
}
- /* Method resolution order algorithm from "Putting Metaclasses to Work"
- by Forman and Danforth (Addison-Wesley 1999). */
-
- static int
- conservative_merge(PyObject *left, PyObject *right)
- {
- int left_size;
- int right_size;
- int i, j, r, ok;
- PyObject *temp, *rr;
-
- assert(PyList_Check(left));
- assert(PyList_Check(right));
-
- again:
- left_size = PyList_GET_SIZE(left);
- right_size = PyList_GET_SIZE(right);
- for (i = 0; i < left_size; i++) {
- for (j = 0; j < right_size; j++) {
- if (PyList_GET_ITEM(left, i) ==
- PyList_GET_ITEM(right, j)) {
- /* found a merge point */
- temp = PyList_New(0);
- if (temp == NULL)
- return -1;
- for (r = 0; r < j; r++) {
- rr = PyList_GET_ITEM(right, r);
- ok = PySequence_Contains(left, rr);
- if (ok < 0) {
- Py_DECREF(temp);
- return -1;
- }
- if (!ok) {
- ok = PyList_Append(temp, rr);
- if (ok < 0) {
- Py_DECREF(temp);
- return -1;
- }
- }
- }
- ok = PyList_SetSlice(left, i, i, temp);
- Py_DECREF(temp);
- if (ok < 0)
- return -1;
- ok = PyList_SetSlice(right, 0, j+1, NULL);
- if (ok < 0)
- return -1;
- goto again;
- }
- }
- }
- return PyList_SetSlice(left, left_size, left_size, right);
- }
-
- static int
- serious_order_disagreements(PyObject *left, PyObject *right)
- {
- return 0; /* XXX later -- for now, we cheat: "don't do that" */
- }
-
static int
fill_classic_mro(PyObject *mro, PyObject *cls)
--- 614,617 ----
***************
*** 715,718 ****
--- 655,733 ----
}
+ /*
+ Method resolution order algorithm C3 described in
+ "A Monotonic Superclass Linearization for Dylan",
+ by Kim Barrett, Bob Cassel, Paul Haahr,
+ David A. Moon, Keith Playford, and P. Tucker Withington.
+ (OOPSLA 1996)
+
+ */
+
+ static int
+ tail_contains(PyObject *list, int whence, PyObject *o) {
+ int j, size;
+ size = PyList_GET_SIZE(list);
+
+ for (j = whence+1; j < size; j++) {
+ if (PyList_GET_ITEM(list, j) == o)
+ return 1;
+ }
+ return 0;
+ }
+
+ static int
+ pmerge(PyObject *acc, PyObject* to_merge) {
+ int i, j, to_merge_size;
+ int *remain;
+ int ok, empty_cnt;
+
+ to_merge_size = PyList_GET_SIZE(to_merge);
+
+ remain = PyMem_MALLOC(SIZEOF_INT*to_merge_size);
+ if (remain == NULL)
+ return -1;
+ for (i = 0; i < to_merge_size; i++)
+ remain[i] = 0;
+
+ again:
+ empty_cnt = 0;
+ for (i = 0; i < to_merge_size; i++) {
+ PyObject *candidate;
+
+ PyObject *cur_list = PyList_GET_ITEM(to_merge, i);
+
+ if (remain[i] >= PyList_GET_SIZE(cur_list)) {
+ empty_cnt++;
+ continue;
+ }
+
+ candidate = PyList_GET_ITEM(cur_list, remain[i]);
+ for (j = 0; j < to_merge_size; j++) {
+ PyObject *j_lst = PyList_GET_ITEM(to_merge, j);
+ if (tail_contains(j_lst, remain[j], candidate))
+ goto skip; /* continue outer loop */
+ }
+ ok = PyList_Append(acc, candidate);
+ if (ok < 0) {
+ PyMem_Free(remain);
+ return -1;
+ }
+ for (j = 0; j < to_merge_size; j++) {
+ PyObject *j_lst = PyList_GET_ITEM(to_merge, j);
+ if (PyList_GET_ITEM(j_lst, remain[j]) == candidate) {
+ remain[j]++;
+ }
+ }
+ goto again;
+ skip:
+ }
+
+ PyMem_FREE(remain);
+ if (empty_cnt == to_merge_size)
+ return 0;
+ PyErr_SetString(PyExc_TypeError, "MRO order disagreement");
+ return -1;
+ }
+
static PyObject *
mro_implementation(PyTypeObject *type)
***************
*** 720,723 ****
--- 735,739 ----
int i, n, ok;
PyObject *bases, *result;
+ PyObject *to_merge, *bases_aslist;
if(type->tp_dict == NULL) {
***************
*** 728,734 ****
bases = type->tp_bases;
n = PyTuple_GET_SIZE(bases);
! result = Py_BuildValue("[O]", (PyObject *)type);
! if (result == NULL)
return NULL;
for (i = 0; i < n; i++) {
PyObject *base = PyTuple_GET_ITEM(bases, i);
--- 744,752 ----
bases = type->tp_bases;
n = PyTuple_GET_SIZE(bases);
!
! to_merge = PyList_New(n+1);
! if (to_merge == NULL)
return NULL;
+
for (i = 0; i < n; i++) {
PyObject *base = PyTuple_GET_ITEM(bases, i);
***************
*** 740,757 ****
parentMRO = classic_mro(base);
if (parentMRO == NULL) {
! Py_DECREF(result);
! return NULL;
! }
! if (serious_order_disagreements(result, parentMRO)) {
! Py_DECREF(result);
! return NULL;
! }
! ok = conservative_merge(result, parentMRO);
! Py_DECREF(parentMRO);
! if (ok < 0) {
! Py_DECREF(result);
return NULL;
! }
}
return result;
}
--- 758,788 ----
parentMRO = classic_mro(base);
if (parentMRO == NULL) {
! Py_DECREF(to_merge);
return NULL;
! }
!
! PyList_SET_ITEM(to_merge, i, parentMRO);
! }
!
! bases_aslist = PySequence_List(bases);
! if (bases_aslist == NULL) {
! Py_DECREF(to_merge);
! return NULL;
! }
! PyList_SET_ITEM(to_merge, n, bases_aslist);
!
! result = Py_BuildValue("[O]", (PyObject *)type);
! if (result == NULL) {
! Py_DECREF(to_merge);
! return NULL;
}
+
+ ok = pmerge(result, to_merge);
+ Py_DECREF(to_merge);
+ if (ok < 0) {
+ Py_DECREF(result);
+ return NULL;
+ }
+
return result;
}
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4