Merge branch 'larsmans-libcpp'

9 files changed, 122 insertions, 32 deletions

diff --git a/Cython/Compiler/ExprNodes.py b/Cython/Compiler/ExprNodes.py
index ac28d03e3..61143c9df 100644
--- a/Cython/Compiler/ExprNodes.py
+++ b/Cython/Compiler/ExprNodes.py
@@ -4738,6 +4738,9 @@ class SimpleCallNode(CallNode):
             self.is_temp = 1
             # func_type.exception_check = True
 
+        if self.is_temp and self.type.is_reference:
+            self.type = PyrexTypes.CFakeReferenceType(self.type.ref_base_type)
+
         # Called in 'nogil' context?
         self.nogil = env.nogil
         if (self.nogil and
@@ -5698,6 +5701,8 @@ class AttributeNode(ExprNode):
             self.op = "->"
         elif obj_type.is_extension_type or obj_type.is_builtin_type:
             self.op = "->"
+        elif obj_type.is_reference and obj_type.is_fake_reference:
+            self.op = "->"
         else:
             self.op = "."
         if obj_type.has_attributes:
diff --git a/Cython/Compiler/PyrexTypes.py b/Cython/Compiler/PyrexTypes.py
index bcb3ca798..393d7ab9f 100644
--- a/Cython/Compiler/PyrexTypes.py
+++ b/Cython/Compiler/PyrexTypes.py
@@ -2422,6 +2422,7 @@ class CNullPtrType(CPtrType):
 class CReferenceType(BaseType):
 
     is_reference = 1
+    is_fake_reference = 0
 
     def __init__(self, base_type):
         self.ref_base_type = base_type
@@ -2444,7 +2445,7 @@ class CReferenceType(BaseType):
         if base_type == self.ref_base_type:
             return self
         else:
-            return CReferenceType(base_type)
+            return type(self)(base_type)
 
     def deduce_template_params(self, actual):
         return self.ref_base_type.deduce_template_params(actual)
@@ -2453,6 +2454,22 @@ class CReferenceType(BaseType):
         return getattr(self.ref_base_type, name)
 
 
+class CFakeReferenceType(CReferenceType):
+
+    is_fake_reference = 1
+
+    def __repr__(self):
+        return "<CFakeReferenceType %s>" % repr(self.ref_base_type)
+
+    def __str__(self):
+        return "%s [&]" % self.ref_base_type
+
+    def declaration_code(self, entity_code,
+            for_display = 0, dll_linkage = None, pyrex = 0):
+        #print "CReferenceType.declaration_code: pointer to", self.base_type ###
+        return "__Pyx_FakeReference<%s> %s" % (self.ref_base_type.empty_declaration_code(), entity_code)
+
+
 class CFuncType(CType):
     #  return_type      CType
     #  args             [CFuncTypeArg]
diff --git a/Cython/Includes/libcpp/algorithm.pxd b/Cython/Includes/libcpp/algorithm.pxd
index bbf53eaf8..0c12bc6fe 100644
--- a/Cython/Includes/libcpp/algorithm.pxd
+++ b/Cython/Includes/libcpp/algorithm.pxd
@@ -1,4 +1,20 @@
+from libcpp cimport bool
+
+
 cdef extern from "<algorithm>" namespace "std" nogil:
+    # Sorting and searching
+    bool binary_search[Iter, T](Iter first, Iter last, const T& value)
+    bool binary_search[Iter, T, Compare](Iter first, Iter last, const T& value,
+                                         Compare comp)
+
+    void partial_sort[Iter](Iter first, Iter middle, Iter last)
+    void partial_sort[Iter, Compare](Iter first, Iter middle, Iter last,
+                                     Compare comp)
+
+    void sort[Iter](Iter first, Iter last)
+    void sort[Iter, Compare](Iter first, Iter last, Compare comp)
+
+    # Binary heaps (priority queues)
     void make_heap[Iter](Iter first, Iter last)
     void make_heap[Iter, Compare](Iter first, Iter last, Compare comp)
 
diff --git a/Cython/Includes/libcpp/map.pxd b/Cython/Includes/libcpp/map.pxd
index 3b6fe61eb..a3768d8a2 100644
--- a/Cython/Includes/libcpp/map.pxd
+++ b/Cython/Includes/libcpp/map.pxd
@@ -33,27 +33,27 @@ cdef extern from "<map>" namespace "std" nogil:
         bint operator>(map&, map&)
         bint operator<=(map&, map&)
         bint operator>=(map&, map&)
-        U& at(T&)
+        U& at(const T&) except +
         iterator begin()
         const_iterator const_begin "begin" ()
         void clear()
-        size_t count(T&)
+        size_t count(const T&)
         bint empty()
         iterator end()
         const_iterator const_end "end" ()
-        pair[iterator, iterator] equal_range(T&)
+        pair[iterator, iterator] equal_range(const T&)
         #pair[const_iterator, const_iterator] equal_range(key_type&)
         void erase(iterator)
         void erase(iterator, iterator)
-        size_t erase(T&)
-        iterator find(T&)
-        const_iterator const_find "find" (T&)
-        pair[iterator, bint] insert(pair[T, U]) # XXX pair[T,U]&
-        iterator insert(iterator, pair[T, U]) # XXX pair[T,U]&
+        size_t erase(const T&)
+        iterator find(const T&)
+        const_iterator const_find "find" (const T&)
+        pair[iterator, bint] insert(pair[T, U]) except + # XXX pair[T,U]&
+        iterator insert(iterator, pair[T, U]) except + # XXX pair[T,U]&
         #void insert(input_iterator, input_iterator)
         #key_compare key_comp()
-        iterator lower_bound(T&)
-        #const_iterator lower_bound(key_type&)
+        iterator lower_bound(const T&)
+        #const_iterator lower_bound(const key_type&)
         size_t max_size()
         reverse_iterator rbegin()
         #const_reverse_iterator rbegin()
@@ -61,6 +61,6 @@ cdef extern from "<map>" namespace "std" nogil:
         #const_reverse_iterator rend()
         size_t size()
         void swap(map&)
-        iterator upper_bound(T&)
-        #const_iterator upper_bound(key_type&)
+        iterator upper_bound(const T&)
+        #const_iterator upper_bound(const key_type&)
         #value_compare value_comp()
diff --git a/Cython/Includes/libcpp/set.pxd b/Cython/Includes/libcpp/set.pxd
index 11f2f017d..dd7437713 100644
--- a/Cython/Includes/libcpp/set.pxd
+++ b/Cython/Includes/libcpp/set.pxd
@@ -31,19 +31,19 @@ cdef extern from "<set>" namespace "std" nogil:
         iterator begin()
         #const_iterator begin()
         void clear()
-        size_t count(T&)
+        size_t count(const T&)
         bint empty()
         iterator end()
         #const_iterator end()
-        pair[iterator, iterator] equal_range(T&)
+        pair[iterator, iterator] equal_range(const T&)
         #pair[const_iterator, const_iterator] equal_range(T&)
         void erase(iterator)
         void erase(iterator, iterator)
         size_t erase(T&)
         iterator find(T&)
         #const_iterator find(T&)
-        pair[iterator, bint] insert(T&)
-        iterator insert(iterator, T&)
+        pair[iterator, bint] insert(const T&) except +
+        iterator insert(iterator, const T&) except +
         #void insert(input_iterator, input_iterator)
         #key_compare key_comp()
         iterator lower_bound(T&)
@@ -55,6 +55,6 @@ cdef extern from "<set>" namespace "std" nogil:
         #const_reverse_iterator rend()
         size_t size()
         void swap(set&)
-        iterator upper_bound(T&)
-        #const_iterator upper_bound(T&)
+        iterator upper_bound(const T&)
+        #const_iterator upper_bound(const T&)
         #value_compare value_comp()
diff --git a/Cython/Includes/libcpp/vector.pxd b/Cython/Includes/libcpp/vector.pxd
index 9d9e498a3..22db3a337 100644
--- a/Cython/Includes/libcpp/vector.pxd
+++ b/Cython/Includes/libcpp/vector.pxd
@@ -41,9 +41,9 @@ cdef extern from "<vector>" namespace "std" nogil:
         bint operator>(vector&, vector&)
         bint operator<=(vector&, vector&)
         bint operator>=(vector&, vector&)
-        void assign(size_t, T&)
-        void assign[input_iterator](input_iterator, input_iterator)
-        T& at(size_t)
+        void assign(size_t, const T&)
+        void assign[input_iterator](input_iterator, input_iterator) except +
+        T& at(size_t) except +
         T& back()
         iterator begin()
         #const_iterator begin()
@@ -55,22 +55,22 @@ cdef extern from "<vector>" namespace "std" nogil:
         iterator erase(iterator)
         iterator erase(iterator, iterator)
         T& front()
-        iterator insert(iterator, T&)
-        void insert(iterator, size_t, T&)
-        void insert(iterator, iterator, iterator)
+        iterator insert(iterator, const T&) except +
+        void insert(iterator, size_t, const T&) except +
+        void insert[Iter](iterator, Iter, Iter) except +
         size_t max_size()
         void pop_back()
-        void push_back(T&)
+        void push_back(T&) except +
         reverse_iterator rbegin()
         #const_reverse_iterator rbegin()
         reverse_iterator rend()
         #const_reverse_iterator rend()
         void reserve(size_t)
-        void resize(size_t)
-        void resize(size_t, T&)
+        void resize(size_t) except +
+        void resize(size_t, T&) except +
         size_t size()
         void swap(vector&)
         
-        #C++0x methods
+        # C++11 methods
         T* data()
         void shrink_to_fit()
diff --git a/Cython/Utility/ModuleSetupCode.c b/Cython/Utility/ModuleSetupCode.c
index 75a0343c6..6477fb2e3 100644
--- a/Cython/Utility/ModuleSetupCode.c
+++ b/Cython/Utility/ModuleSetupCode.c
@@ -217,12 +217,24 @@ static CYTHON_INLINE float __PYX_NAN() {
 
 #define __Pyx_void_to_None(void_result) (void_result, Py_INCREF(Py_None), Py_None)
 
-// Work around clang bug http://stackoverflow.com/questions/21847816/c-invoke-nested-template-class-destructor
 #ifdef __cplusplus
+// Work around clang bug http://stackoverflow.com/questions/21847816/c-invoke-nested-template-class-destructor
 template<typename T>
 void __Pyx_call_destructor(T* x) {
     x->~T();
 }
+
+// Used for temporary variables of "reference" type.
+template<typename T>
+class __Pyx_FakeReference {
+  public:
+    __Pyx_FakeReference() : ptr(NULL) { }
+    __Pyx_FakeReference(T& ref) : ptr(&ref) { }
+    T *operator->() { return ptr; }
+    operator T&() { return *ptr; }
+  private:
+    T *ptr;
+};
 #endif
 
 /////////////// UtilityFunctionPredeclarations.proto ///////////////
diff --git a/tests/run/cpp_template_ref_args.pyx b/tests/run/cpp_template_ref_args.pyx
index b65c9287b..526cef97a 100644
--- a/tests/run/cpp_template_ref_args.pyx
+++ b/tests/run/cpp_template_ref_args.pyx
@@ -5,8 +5,9 @@ cdef extern from "cpp_template_ref_args.h":
 
     cdef cppclass Bar[T]:
         Bar()
-        Bar[T] & ref()
+        # bug: Bar[T] created before class fully defined
         T value
+        Bar[T] & ref() except +
 
     cdef cppclass Foo[T]:
         Foo()
@@ -28,3 +29,12 @@ def test_template_ref_arg(int x):
     bar.value = x
 
     return foo.bar_value(bar.ref())
+
+def test_template_ref_attr(int x):
+    """
+    >>> test_template_ref_attr(4)
+    4
+    """
+    cdef Bar[int] bar
+    bar.value = x
+    return bar.ref().value
diff --git a/tests/run/libcpp_algo.pyx b/tests/run/libcpp_algo.pyx
index ec123b837..2b0a352fe 100644
--- a/tests/run/libcpp_algo.pyx
+++ b/tests/run/libcpp_algo.pyx
@@ -1,7 +1,7 @@
 # tag: cpp
 
 from libcpp cimport bool
-from libcpp.algorithm cimport make_heap, sort_heap
+from libcpp.algorithm cimport make_heap, sort_heap, sort, partial_sort
 from libcpp.vector cimport vector
 
 
@@ -27,3 +27,33 @@ def heapsort(l, bool reverse=False):
         sort_heap(v.begin(), v.end())
 
     return v
+
+
+def partialsort(l, int k, reverse=False):
+    """
+    >>> partialsort([4, 2, 3, 1, 5], k=2)[:2]
+    [1, 2]
+    >>> partialsort([4, 2, 3, 1, 5], k=2, reverse=True)[:2]
+    [5, 4]
+    """
+    cdef vector[int] v = l
+    if reverse:
+        partial_sort(v.begin(), v.begin() + k, v.end(), greater)
+    else:
+        partial_sort(v.begin(), v.begin() + k, v.end())
+    return v
+
+
+def stdsort(l, reverse=False):
+    """
+    >>> stdsort([3, 2, 1, 4, 5])
+    [1, 2, 3, 4, 5]
+    >>> stdsort([3, 2, 1, 4, 5], reverse=True)
+    [5, 4, 3, 2, 1]
+    """
+    cdef vector[int] v = l
+    if reverse:
+        sort(v.begin(), v.end(), greater)
+    else:
+        sort(v.begin(), v.end())
+    return v