Add sorted and list.sort (#81)

Tim-St · corona10 · commit af17d7daed3e · 2019-09-29T17:43:24.000+09:00
* Add `sorted` and `list.sort`

Mostly finished, needs some argument parsing changes.

* Unpacking of args works now for `sorted` and `list.sort`

* add tests

* new try

* Add tests for `list.sort`

* Update list.py

* support `list.sort([], **kwargs)`

* Update list.go

* better NoneType comparison

* put tests for `sorted` in `builtin.py`
diff --git a/builtin/builtin.go b/builtin/builtin.go
@@ -60,7 +60,7 @@ func init() {
 		py.MustNewMethod("repr", builtin_repr, 0, repr_doc),
 		py.MustNewMethod("round", builtin_round, 0, round_doc),
 		py.MustNewMethod("setattr", builtin_setattr, 0, setattr_doc),
-		// py.MustNewMethod("sorted", builtin_sorted, 0, sorted_doc),
+		py.MustNewMethod("sorted", builtin_sorted, 0, sorted_doc),
 		py.MustNewMethod("sum", builtin_sum, 0, sum_doc),
 		// py.MustNewMethod("vars", builtin_vars, 0, vars_doc),
 	}
@@ -1074,3 +1074,28 @@ func builtin_sum(self py.Object, args py.Tuple) (py.Object, error) {
 	}
 	return start, nil
 }
+
+const sorted_doc = `sorted(iterable, key=None, reverse=False)
+
+Return a new list containing all items from the iterable in ascending order.
+
+A custom key function can be supplied to customize the sort order, and the
+reverse flag can be set to request the result in descending order.`
+
+func builtin_sorted(self py.Object, args py.Tuple, kwargs py.StringDict) (py.Object, error) {
+	const funcName = "sorted"
+	var iterable py.Object
+	err := py.UnpackTuple(args, nil, funcName, 1, 1, &iterable)
+	if err != nil {
+		return nil, err
+	}
+	l, err := py.SequenceList(iterable)
+	if err != nil {
+		return nil, err
+	}
+	err = py.SortInPlace(l, kwargs, funcName)
+	if err != nil {
+		return nil, err
+	}
+	return l, nil
+}
diff --git a/builtin/tests/builtin.py b/builtin/tests/builtin.py
@@ -1,4 +1,4 @@
-# Copyright 2018 The go-python Authors.  All rights reserved.
+# Copyright 2019 The go-python Authors.  All rights reserved.
 # Use of this source code is governed by a BSD-style
 # license that can be found in the LICENSE file.
 
@@ -329,6 +329,50 @@ class C: pass
 finally:
     assert ok
 
+doc="sorted"
+a = [3, 1.1, 1, 2]
+assert sorted(a) == [1, 1.1, 2, 3]
+assert sorted(sorted(a)) == [1, 1.1, 2, 3]
+assert sorted(a, reverse=True) == [3, 2, 1.1, 1]
+assert sorted(a, key=lambda l: l+1) == [1, 1.1, 2, 3]
+s = [2.0, 2, 1, 1.0]
+assert sorted(s, key=lambda l: 0) == [2.0, 2, 1, 1.0]
+assert [type(t) for t in sorted(s, key=lambda l: 0)] == [float, int, int, float]
+assert sorted(s) == [1, 1.0, 2.0, 2]
+assert [type(t) for t in sorted(s)] == [int, float, float, int]
+
+try:
+    sorted([2.0, "abc"])
+except TypeError:
+    pass
+else:
+    assert False
+
+assert sorted([]) == []
+assert sorted([0]) == [0]
+s = [0, 1]
+try:
+    # Sorting a list of len >= 2 with uncallable key must fail on all Python implementations.
+    sorted(s, key=1)
+except TypeError:
+    pass
+else:
+    assert False
+
+try:
+    sorted(1)
+except TypeError:
+    pass
+else:
+    assert False
+
+try:
+    sorted()
+except TypeError:
+    pass
+else:
+    assert False
+
 doc="sum"
 assert sum([1,2,3]) == 6
 assert sum([1,2,3], 3) == 9
diff --git a/py/list.go b/py/list.go
@@ -6,6 +6,10 @@
 
 package py
 
+import (
+	"sort"
+)
+
 var ListType = ObjectType.NewType("list", "list() -> new empty list\nlist(iterable) -> new list initialized from iterable's items", ListNew, nil)
 
 // FIXME lists are mutable so this should probably be struct { Tuple } then can use the sub methods on Tuple
@@ -14,6 +18,7 @@ type List struct {
 }
 
 func init() {
+	// FIXME: all methods should be callable using list.method([], *args, **kwargs) or [].method(*args, **kwargs)
 	ListType.Dict["append"] = MustNewMethod("append", func(self Object, args Tuple) (Object, error) {
 		listSelf := self.(*List)
 		if len(args) != 1 {
@@ -34,6 +39,36 @@ func init() {
 		return NoneType{}, nil
 	}, 0, "extend([item])")
 
+	ListType.Dict["sort"] = MustNewMethod("sort", func(self Object, args Tuple, kwargs StringDict) (Object, error) {
+		const funcName = "sort"
+		var l *List
+		if self == None {
+			// method called using `list.sort([], **kwargs)`
+			var o Object
+			err := UnpackTuple(args, nil, funcName, 1, 1, &o)
+			if err != nil {
+				return nil, err
+			}
+			var ok bool
+			l, ok = o.(*List)
+			if !ok {
+				return nil, ExceptionNewf(TypeError, "descriptor 'sort' requires a 'list' object but received a '%s'", o.Type())
+			}
+		} else {
+			// method called using `[].sort(**kargs)`
+			err := UnpackTuple(args, nil, funcName, 0, 0)
+			if err != nil {
+				return nil, err
+			}
+			l = self.(*List)
+		}
+		err := SortInPlace(l, kwargs, funcName)
+		if err != nil {
+			return nil, err
+		}
+		return NoneType{}, nil
+	}, 0, "sort(key=None, reverse=False)")
+
 }
 
 // Type of this List object
@@ -331,3 +366,122 @@ func (a *List) M__ne__(other Object) (Object, error) {
 	}
 	return False, nil
 }
+
+type sortable struct {
+	l        *List
+	keyFunc  Object
+	reverse  bool
+	firstErr error
+}
+
+type ptrSortable struct {
+	s *sortable
+}
+
+func (s ptrSortable) Len() int {
+	return s.s.l.Len()
+}
+
+func (s ptrSortable) Swap(i, j int) {
+	itemI, err := s.s.l.M__getitem__(Int(i))
+	if err != nil {
+		if s.s.firstErr == nil {
+			s.s.firstErr = err
+		}
+		return
+	}
+	itemJ, err := s.s.l.M__getitem__(Int(j))
+	if err != nil {
+		if s.s.firstErr == nil {
+			s.s.firstErr = err
+		}
+		return
+	}
+	_, err = s.s.l.M__setitem__(Int(i), itemJ)
+	if err != nil {
+		if s.s.firstErr == nil {
+			s.s.firstErr = err
+		}
+	}
+	_, err = s.s.l.M__setitem__(Int(j), itemI)
+	if err != nil {
+		if s.s.firstErr == nil {
+			s.s.firstErr = err
+		}
+	}
+}
+
+func (s ptrSortable) Less(i, j int) bool {
+	itemI, err := s.s.l.M__getitem__(Int(i))
+	if err != nil {
+		if s.s.firstErr == nil {
+			s.s.firstErr = err
+		}
+		return false
+	}
+	itemJ, err := s.s.l.M__getitem__(Int(j))
+	if err != nil {
+		if s.s.firstErr == nil {
+			s.s.firstErr = err
+		}
+		return false
+	}
+
+	if s.s.keyFunc != None {
+		itemI, err = Call(s.s.keyFunc, Tuple{itemI}, nil)
+		if err != nil {
+			if s.s.firstErr == nil {
+				s.s.firstErr = err
+			}
+			return false
+		}
+		itemJ, err = Call(s.s.keyFunc, Tuple{itemJ}, nil)
+		if err != nil {
+			if s.s.firstErr == nil {
+				s.s.firstErr = err
+			}
+			return false
+		}
+	}
+
+	var cmpResult Object
+	if s.s.reverse {
+		cmpResult, err = Lt(itemJ, itemI)
+	} else {
+		cmpResult, err = Lt(itemI, itemJ)
+	}
+
+	if err != nil {
+		if s.s.firstErr == nil {
+			s.s.firstErr = err
+		}
+		return false
+	}
+
+	if boolResult, ok := cmpResult.(Bool); ok {
+		return bool(boolResult)
+	}
+
+	return false
+}
+
+// SortInPlace sorts the given List in place using a stable sort.
+// kwargs can have the keys "key" and "reverse".
+func SortInPlace(l *List, kwargs StringDict, funcName string) error {
+	var keyFunc Object
+	var reverse Object
+	err := ParseTupleAndKeywords(nil, kwargs, "|$OO:"+funcName, []string{"key", "reverse"}, &keyFunc, &reverse)
+	if err != nil {
+		return err
+	}
+	if keyFunc == nil {
+		keyFunc = None
+	}
+	if reverse == nil {
+		reverse = False
+	}
+	// FIXME: requires the same bool-check like CPython (or better "|$Op" that doesn't panic on nil).
+	s := ptrSortable{&sortable{l, keyFunc, ObjectIsTrue(reverse), nil}}
+	sort.Stable(s)
+	return s.s.firstErr
+}
diff --git a/py/tests/list.py b/py/tests/list.py
@@ -1,4 +1,4 @@
-# Copyright 2018 The go-python Authors.  All rights reserved.
+# Copyright 2019 The go-python Authors.  All rights reserved.
 # Use of this source code is governed by a BSD-style
 # license that can be found in the LICENSE file.
 
@@ -39,4 +39,76 @@
 assert a * 0 == []
 assert a * -1 == []
 
+doc="sort"
+# [].sort
+a = [3, 1.1, 1, 2]
+s1 = list(a)
+s1.sort()
+assert s1 == [1, 1.1, 2, 3]
+s1.sort() # sort a sorted list
+assert s1 == [1, 1.1, 2, 3]
+s2 = list(a)
+s2.sort(reverse=True)
+assert s2 == [3, 2, 1.1, 1]
+s2.sort() # sort a reversed list
+assert s2 == [1, 1.1, 2, 3]
+s3 = list(a)
+s3.sort(key=lambda l: l+1) # test lambda key
+assert s3 == [1, 1.1, 2, 3]
+s4 = [2.0, 2, 1, 1.0]
+s4.sort(key=lambda l: 0) # test stability
+assert s4 == [2.0, 2, 1, 1.0]
+assert [type(t) for t in s4] == [float, int, int, float]
+s4 = [2.0, 2, 1, 1.0]
+s4.sort() # test stability
+assert s4 == [1, 1.0, 2.0, 2]
+assert [type(t) for t in s4] == [int, float, float, int]
+s5 = [2.0, "abc"]
+assertRaises(TypeError, lambda: s5.sort())
+s5 = []
+s5.sort()
+assert s5 == []
+s5 = [0]
+s5.sort()
+assert s5 == [0]
+s5 = [0, 1]
+# Sorting a list of len >= 2 with uncallable key must fail on all Python implementations.
+assertRaises(TypeError, lambda: s5.sort(key=1))
+
+# list.sort([])
+a = [3, 1.1, 1, 2]
+s1 = list(a)
+assert list.sort(s1) is None
+assert s1 == [1, 1.1, 2, 3]
+assert list.sort(s1) is None # sort a sorted list
+assert s1 == [1, 1.1, 2, 3]
+s2 = list(a)
+list.sort(s2, reverse=True)
+assert s2 == [3, 2, 1.1, 1]
+list.sort(s2) # sort a reversed list
+assert s2 == [1, 1.1, 2, 3]
+s3 = list(a)
+list.sort(s3, key=lambda l: l+1) # test lambda key
+assert s3 == [1, 1.1, 2, 3]
+s4 = [2.0, 2, 1, 1.0]
+list.sort(s4, key=lambda l: 0) # test stability
+assert s4 == [2.0, 2, 1, 1.0]
+assert [type(t) for t in s4] == [float, int, int, float]
+s4 = [2.0, 2, 1, 1.0]
+list.sort(s4) # test stability
+assert s4 == [1, 1.0, 2.0, 2]
+assert [type(t) for t in s4] == [int, float, float, int]
+s5 = [2.0, "abc"]
+assertRaises(TypeError, lambda: list.sort(s5))
+s5 = []
+list.sort(s5)
+assert s5 == []
+s5 = [0]
+list.sort(s5)
+assert s5 == [0]
+s5 = [0, 1]
+# Sorting a list of len >= 2 with uncallable key must fail on all Python implementations.
+assertRaises(TypeError, lambda: list.sort(s5, key=1))
+assertRaises(TypeError, lambda: list.sort(1))
+
 doc="finished"
