[PATCH 1/3] Introduce gdb::function_view

[Pedro Alves <palves at redhat dot com>]

This commit adds new function_view type.  This type holds a a
non-owning reference to a callable.  It is meant to be used as
callback type of functions, instead of using C-style pair of function
pointer and 'void *data' arguments.  function_view allows passing
references to stateful function objects / lambdas w/ captures as
callbacks efficiently, while function pointer + 'void *' does not.

See the intro in the new function-view.h header for more.

Unit tests included.  I added a new gdb/unittests/ subdir this time,
instead of putting the tests under gdb/.  If this is agreed to be a
good idea, some of the current selftests that exercise gdb/common/
things but live in gdb/ could move here (e.g., gdb/utils-selftests.c).

gdb/ChangeLog:
yyyy-mm-dd  Pedro Alves  <palves@redhat.com>

	* Makefile.in (SUBDIR_UNITTESTS_SRCS, SUBDIR_UNITTESTS_OBS): New.
	(SFILES): Add $(SUBDIR_UNITTEST_SRCS).
	(COMMON_OBS): Add $(SUBDIR_UNITTEST_OBS).
	(%.o) <unittests/%.c>: New pattern.
	(INIT_FILES): Add $(SUBDIR_UNITTESTS_SRCS).
	* common/function-view.h: New file.
	* unittests/function-view-selftests.c: New file.
---
 gdb/Makefile.in                         |  24 ++-
 gdb/common/function-view.h              | 320 ++++++++++++++++++++++++++++++++
 gdb/unittests/function-view-selftests.c | 183 ++++++++++++++++++
 3 files changed, 524 insertions(+), 3 deletions(-)
 create mode 100644 gdb/common/function-view.h
 create mode 100644 gdb/unittests/function-view-selftests.c

diff --git a/gdb/Makefile.in b/gdb/Makefile.in
index 43253d3..a4cac36 100644
--- a/gdb/Makefile.in
+++ b/gdb/Makefile.in
@@ -523,6 +523,12 @@ SUBDIR_PYTHON_DEPS =
 SUBDIR_PYTHON_LDFLAGS =
 SUBDIR_PYTHON_CFLAGS =
 
+SUBDIR_UNITTESTS_SRCS = \
+	unittests/function-view-selftests.c
+
+SUBDIR_UNITTESTS_OBS = \
+	function-view-selftests.o
+
 # Opcodes currently live in one of two places.  Either they are in the
 # opcode library, typically ../opcodes, or they are in a header file
 # in INCLUDE_DIR.
@@ -1216,7 +1222,8 @@ SFILES = \
 	common/xml-utils.c \
 	mi/mi-common.c \
 	target/waitstatus.c \
-	$(SUBDIR_GCC_COMPILE_SRCS)
+	$(SUBDIR_GCC_COMPILE_SRCS) \
+	$(SUBDIR_UNITTEST_SRCS)
 
 LINTFILES = $(SFILES) $(YYFILES) $(CONFIG_SRCS) init.c
 
@@ -1800,7 +1807,8 @@ COMMON_OBS = $(DEPFILES) $(CONFIG_OBS) $(YYOBJ) \
 	xml-syscall.o \
 	xml-tdesc.o \
 	xml-utils.o \
-	$(SUBDIR_GCC_COMPILE_OBS)
+	$(SUBDIR_GCC_COMPILE_OBS) \
+	$(SUBDIR_UNITTESTS_OBS)
 
 TSOBS = inflow.o
 
@@ -1909,6 +1917,10 @@ all: gdb$(EXEEXT) $(CONFIG_ALL)
 	$(COMPILE) $<
 	$(POSTCOMPILE)
 
+%.o: ${srcdir}/unittests/%.c
+	$(COMPILE) $<
+	$(POSTCOMPILE)
+
 # Specify an explicit rule for gdb/common/agent.c, to avoid a clash with the
 # object file generate by gdb/agent.c.
 common-agent.o: $(srcdir)/common/agent.c
@@ -2124,7 +2136,13 @@ test-cp-name-parser$(EXEEXT): test-cp-name-parser.o $(LIBIBERTY)
 # duplicates.  Files in the gdb/ directory can end up appearing in
 # COMMON_OBS (as a .o file) and CONFIG_SRCS (as a .c file).
 
-INIT_FILES = $(COMMON_OBS) $(TSOBS) $(CONFIG_SRCS) $(SUBDIR_GCC_COMPILE_SRCS)
+INIT_FILES = \
+	$(COMMON_OBS) \
+	$(TSOBS) \
+	$(CONFIG_SRCS) \
+	$(SUBDIR_GCC_COMPILE_SRCS) \
+	$(SUBDIR_UNITTESTS_SRCS)
+
 init.c: $(INIT_FILES)
 	@echo Making init.c
 	@rm -f init.c-tmp init.l-tmp
diff --git a/gdb/common/function-view.h b/gdb/common/function-view.h
new file mode 100644
index 0000000..cd455f8
--- /dev/null
+++ b/gdb/common/function-view.h
@@ -0,0 +1,320 @@
+/* Copyright (C) 2017 Free Software Foundation, Inc.
+
+   This file is part of GDB.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+#ifndef COMMON_FUNCTION_VIEW_H
+#define COMMON_FUNCTION_VIEW_H
+
+/* function_view is a polymorphic type-erasing wrapper class that
+   encapsulates a non-owning reference to arbitrary callable objects.
+
+   A way to put it is that function_view is to std::function like
+   std::string_view is to std::string.  While std::function stores a
+   type-erased callable object internally, function_view holds a
+   type-erased reference to an external callable object.
+
+   This is meant to be used as callback type of a function that:
+
+     #1 - Takes a callback as parameter.
+
+     #2 - Does not store the callback anywhere; instead if just calls
+          it or forwards it to some other function that calls it.
+
+     #3 - When we don't want, or can't make said function be a
+          template function with the callable type as template
+          parameter.  For example, when the callback is a parameter of
+          a virtual member function, or when putting the function
+          template in a header would expose too much implementation
+          detail.
+
+   For this use case, which is quite pervasive, a function_view is a
+   better choice for callback type than std::function.  It is a better
+   choice because std::function is a heavy-weight object with value
+   semantics that generally requires a heap allocation on
+   construction/assignment of the target callable, while function_view
+   is light and does not require any heap allocation.  It _is_
+   possible to use std::function in such a way that avoids most of the
+   overhead by making sure to only construct it with callables of
+   types that fit std::function's small object optimization, such as
+   function pointers and std::reference_wrapper callables, however,
+   that is quite inconvenient in practice, because restricting to
+   free-function callables would imply no state/capture (which we need
+   in most cases), and std::reference_wrapper implies remembering to
+   use std::ref/std::cref where the callable is constructed, with the
+   added inconvenience that those function have deleted rvalue-ref
+   overloads, meaning you can't use unnamed/temporary lambdas with
+   them.
+
+   Note that because function_view is a non-owning view of a callable,
+   care must be taken to ensure that the callable outlives the
+   function_view that calls it.  This is not really a problem for the
+   use case function_view is intended for, such as passing a temporary
+   function object / lambda to a function that accepts a callback,
+   because in those cases, the temporary is guaranteed to be live
+   until the called function returns.
+
+   Calling a function_view with no associated target is undefined,
+   unlike with std::function, which throws bad_function_call.  This is
+   by design, to avoid the otherwise necessary NULL check in
+   function_view::operator().
+
+   Since function_view objects are small (a pair of pointers), they
+   should generally be passed around by value.
+
+   Usage:
+
+   Given this function that accepts a callback:
+
+    void
+    iterate_over_foos (gdb::function_view<void (foo *)> callback)
+    {
+       for (auto & : foos)
+         callback (&foo);
+    }
+
+   you can call it like this, passing a lambda as callback:
+
+    iterate_over_foos ([&] (foo *f) {
+      process_one_foo (f);
+    });
+
+   or like this, passing a function object as callback:
+
+    struct function_object
+    {
+      void operator() (foo *f)
+      {
+        if (s->check ())
+          process_one_foo (f);
+      }
+
+      // some state
+      state *s;
+    };
+
+    function_object matcher (mystate);
+    iterate_over_foos (matcher);
+
+  or like this, passing a function pointer as callback:
+
+    iterate_over_foos (process_one_foo);
+
+  You can find unit tests covering the whole API in
+  unittests/function-view-selftests.c.  */
+
+namespace gdb {
+
+namespace traits
+{
+  /* A few trait helpers.  */
+  template<typename Predicate>
+  struct Not : public std::integral_constant<bool, !Predicate::value>
+  {};
+
+  template<typename...>
+  struct Or;
+
+  template<>
+  struct Or<> : public std::false_type
+  {};
+
+  template<typename B1>
+  struct Or<B1> : public B1
+  {};
+
+  template<typename B1, typename B2>
+  struct Or<B1, B2>
+    : public std::conditional<B1::value, B1, B2>::type
+  {};
+
+  template<typename B1,typename B2,typename B3, typename... Bn>
+  struct Or<B1, B2, B3, Bn...>
+    : public std::conditional<B1::value, B1, Or<B2, B3, Bn...>>::type
+  {};
+}
+
+namespace fv_detail {
+/* Bits shared by all function_view instantiations that do not depend
+   on the template parameters.  */
+
+/* Storage for the erased callable.  This is a union in order to be
+   able to save both a function object (data) pointer or a function
+   pointer without triggering undefined behavior.  */
+union erased_callable
+{
+  /* For function objects.  */
+  void *data;
+
+    /* For function pointers.  */
+  void (*fn) ();
+};
+
+} /* namespace fv_detail */
+
+/* Use partial specialization to get access to the callable's
+   signature. */
+template<class Signature>
+struct function_view;
+
+template<typename Res, typename... Args>
+class function_view<Res (Args...)>
+{
+  template<typename From, typename To>
+  using CompatibleReturnType
+    = traits::Or<std::is_void<To>,
+		 std::is_same<From, To>,
+		 std::is_convertible<From, To>>;
+
+  /* True if Func can be called with Args, and the result, and the
+     result is convertible to Res, unless Res is void.  */
+  template<typename Callable,
+	   typename Res2 = typename std::result_of<Callable &(Args...)>::type>
+  struct IsCompatibleCallable : CompatibleReturnType<Res2, Res>
+  {};
+
+  /* True if Callable is a function_view.  Used to avoid hijacking the
+     copy ctor.  */
+  template <typename Callable>
+  struct IsFunctionView
+    : std::is_same<function_view, typename std::decay<Callable>::type>
+  {};
+
+  /* Helper to make SFINAE logic easier to read.  */
+  template<typename Condition>
+  using Requires = typename std::enable_if<Condition::value, void>::type;
+
+ public:
+
+  /* NULL by default.  */
+  constexpr function_view () noexcept
+    : m_erased_callable {},
+    m_invoker {}
+  {}
+
+  /* Default copy/assignment is fine.  */
+  function_view (const function_view &) = default;
+  function_view &operator= (const function_view &) = default;
+
+  /* This is the main entry point.  Use SFINAE to avoid hijacking the
+     copy constructor and to ensure that the target type is
+     compatible.  */
+  template
+    <typename Callable,
+     typename = Requires<traits::Not<IsFunctionView<Callable>>>,
+     typename = Requires<IsCompatibleCallable<Callable>>>
+  function_view (Callable &&callable) noexcept
+  {
+    bind (callable);
+  }
+
+  /* Construct a NULL function_view.  */
+  constexpr function_view (std::nullptr_t) noexcept
+    : m_erased_callable {},
+      m_invoker {}
+  {}
+
+  /* Clear a function_view.  */
+  function_view &operator= (std::nullptr_t) noexcept
+  {
+    m_invoker = nullptr;
+    return *this;
+  }
+
+  /* Return true if the wrapper has a target, false otherwise.  Note
+     we check M_INVOKER instead of M_ERASED_CALLABLE because we don't
+     know which member of the union is active right now.  */
+  constexpr explicit operator bool () const noexcept
+  { return m_invoker != nullptr; }
+
+  /* Call the callable.  */
+  Res operator () (Args... args) const
+  { return m_invoker (m_erased_callable, std::forward<Args> (args)...); }
+
+ private:
+
+  /* Bind this function_view to a compatible function object
+     reference.  */
+  template <typename Callable>
+  void bind (Callable &callable) noexcept
+  {
+    m_erased_callable.data = (void *) std::addressof (callable);
+    m_invoker = [] (fv_detail::erased_callable ecall, Args... args)
+      noexcept (noexcept (callable (std::forward<Args> (args)...))) -> Res
+      {
+	auto &restored_callable = *static_cast<Callable *> (ecall.data);
+	/* The explicit cast to Res avoids a compile error when Res is
+	   void and the callable returns non-void.  */
+	return (Res) restored_callable (std::forward<Args> (args)...);
+      };
+  }
+
+  /* Bind this function_view to a compatible function pointer.
+
+     Making this a separate function allows avoiding one indirection,
+     by storing the function pointer directly in the storage, instead
+     of a pointer to pointer.  erased_callable is then a union in
+     order to avoid storing a function pointer as a data pointer here,
+     which would be undefined.  */
+  template<class Res2, typename... Args2>
+  void bind (Res2 (*fn) (Args2...)) noexcept
+  {
+    m_erased_callable.fn = reinterpret_cast<void (*) ()> (fn);
+    m_invoker = [] (fv_detail::erased_callable ecall, Args... args)
+      noexcept (noexcept (fn (std::forward<Args> (args)...))) -> Res
+      {
+	auto restored_fn = reinterpret_cast<Res2 (*) (Args2...)> (ecall.fn);
+	/* The explicit cast to Res avoids a compile error when Res is
+	   void and the callable returns non-void.  */
+	return (Res) restored_fn (std::forward<Args> (args)...);
+      };
+  }
+
+  /* Storage for the erased callable.  */
+  fv_detail::erased_callable m_erased_callable;
+
+  /* The invoker.  This is set to a capture-less lambda by one of the
+     'bind' overloads.  The lambda restores the right type of the
+     callable (which is passed as first argument), and forwards the
+     args.  */
+  Res (*m_invoker) (fv_detail::erased_callable, Args...);
+};
+
+/* Allow comparison with NULL.  Defer the work to the in-class
+   operator bool implementation.  */
+
+template<typename Res, typename... Args>
+constexpr inline bool
+operator== (const function_view<Res (Args...)> &f, std::nullptr_t) noexcept
+{ return !static_cast<bool> (f); }
+
+template<typename Res, typename... Args>
+constexpr inline bool
+operator== (std::nullptr_t, const function_view<Res (Args...)> &f) noexcept
+{ return !static_cast<bool> (f); }
+
+template<typename Res, typename... Args>
+constexpr inline bool
+operator!= (const function_view<Res (Args...)> &f, std::nullptr_t) noexcept
+{ return static_cast<bool> (f); }
+
+template<typename Res, typename... Args>
+constexpr inline bool
+operator!= (std::nullptr_t, const function_view<Res (Args...)> &f) noexcept
+{ return static_cast<bool> (f); }
+
+} /* namespace gdb */
+
+#endif
diff --git a/gdb/unittests/function-view-selftests.c b/gdb/unittests/function-view-selftests.c
new file mode 100644
index 0000000..8f73bc4
--- /dev/null
+++ b/gdb/unittests/function-view-selftests.c
@@ -0,0 +1,183 @@
+/* Self tests for function_view for GDB, the GNU debugger.
+
+   Copyright (C) 2017 Free Software Foundation, Inc.
+
+   This file is part of GDB.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+#include "defs.h"
+#include "selftest.h"
+#include "common/function-view.h"
+
+#if GDB_SELF_TEST
+
+namespace selftests {
+namespace function_view {
+
+static int
+add_one (int count)
+{
+  return ++count;
+}
+
+static short
+add_one_short (short count)
+{
+  return ++count;
+}
+
+static int
+call_callback (int count, gdb::function_view <int(int)> callback)
+{
+  return callback (count);
+}
+
+static void
+call_callback_void (int count, gdb::function_view <void(int)> callback)
+{
+  callback (count);
+}
+
+struct plus_one_function_object
+{
+  int operator () (int count)
+  {
+    ++calls;
+    return ++count;
+  }
+
+  int calls = 0;
+};
+
+static void
+run_tests ()
+{
+  /* A simple lambda.  */
+  auto plus_one = [] (int count) { return ++count; };
+
+  /* A function_view that references the lambda.  */
+  gdb::function_view<int (int)> plus_one_view (plus_one);
+
+  /* Check calling the lambda directly.  */
+  SELF_CHECK (plus_one (0) == 1);
+  SELF_CHECK (plus_one (1) == 2);
+
+  /* Check calling lambda via the view.  */
+  SELF_CHECK (plus_one_view (2) == 3);
+  SELF_CHECK (plus_one_view (3) == 4);
+
+  /* Check calling a function that takes a function_view as argument,
+     by value.  Pass a lambda, making sure a function_view is properly
+     constructed implicitly.  */
+  SELF_CHECK (call_callback (1, [] (int count)
+    {
+      return count + 2;
+    }) == 3);
+
+  /* Same, passing a named/lvalue lambda.  */
+  SELF_CHECK (call_callback (1, plus_one) == 2);
+  /* Same, passing named/lvalue function_view (should copy).  */
+  SELF_CHECK (call_callback (1, plus_one_view) == 2);
+
+  /* Check constructing a function view over a function-object
+     callable, and calling it.  */
+  plus_one_function_object func_obj;
+  SELF_CHECK (func_obj (0) == 1);
+  SELF_CHECK (call_callback (1, func_obj) == 2);
+  /* Check that the callable was referenced, not copied.  */
+  SELF_CHECK (func_obj.calls == 2);
+
+  /* Check constructing a function_view over free-function callable,
+     and calling it.  */
+  SELF_CHECK (call_callback (1, add_one) == 2);
+
+  /* Check calling a function with a
+     compatible-but-not-exactly-the-same prototype.  */
+  SELF_CHECK (call_callback (1, [] (short count) -> short
+    {
+      return count + 2;
+    }) == 3);
+  /* Same, but passing a function pointer.  */
+  SELF_CHECK (call_callback (1, add_one_short) == 2);
+
+  /* Like std::function, a function_view that expects a void return
+     can reference callables with non-void return type.  The result is
+     simply discarded.  Check a lambda, function object and a function
+     pointer.  */
+  call_callback_void (1, [] (int count) -> int
+    {
+      return count + 2;
+    });
+  call_callback_void (1, func_obj);
+  call_callback_void (1, add_one);
+
+  /* Check that the main ctor doesn't hijack the copy ctor.  */
+  auto plus_one_view2 (plus_one_view);
+  auto plus_one_view3 (plus_one_view2);
+  static_assert (std::is_same<decltype (plus_one_view),
+		 decltype (plus_one_view2)>::value, "");
+  static_assert (std::is_same<decltype (plus_one_view),
+		 decltype (plus_one_view3)>::value, "");
+
+  SELF_CHECK (plus_one_view3 (1) == 2);
+
+  /* Likewise, but propagate a NULL callable.  If this calls the main
+     function_view ctor instead of the copy ctor by mistake, then
+     null_func_2 ends up non-NULL (because it'd instead reference
+     null_func_1 as just another callable).  */
+  constexpr gdb::function_view<int(int)> null_func_1 = nullptr;
+  constexpr auto null_func_2 (null_func_1);
+
+  /* While at it, check whether the function_view is bound using
+     various forms, op==, op!= and op bool.  */
+
+  /* op== */
+  static_assert (null_func_2 == nullptr, "");
+  static_assert (nullptr == null_func_2, "");
+  static_assert (null_func_2 == NULL, "");
+  static_assert (NULL == null_func_2, "");
+
+  /* op!= */
+  static_assert (!(null_func_2 != nullptr), "");
+  static_assert (!(nullptr != null_func_2), "");
+  static_assert (!(null_func_2 != NULL), "");
+  static_assert (!(NULL != null_func_2), "");
+
+  /* op bool */
+  static_assert (!null_func_2, "");
+
+  /* Check the nullptr_t ctor.  */
+  constexpr gdb::function_view<int(int)> check_ctor_nullptr (nullptr);
+  static_assert (!check_ctor_nullptr, "");
+
+  /* Check the nullptr_t op= */
+  gdb::function_view<int(int)> check_op_eq_null (add_one);
+  SELF_CHECK (check_op_eq_null);
+  check_op_eq_null = nullptr;
+  SELF_CHECK (!check_op_eq_null);
+}
+
+} /* namespace function_view */
+} /* namespace selftests */
+
+#endif
+
+void
+_initialize_function_view_selftests ()
+{
+#if GDB_SELF_TEST
+  register_self_test (selftests::function_view::run_tests);
+#endif
+}
-- 
2.5.5