Fix ExpressionRef copy constructor and add a move constructor

The move constructor of ExpressionRef now implements the copy
elision, which was incorrectly done by the copy constructor.

This patch also updates the CMakeList to only add the
Expression tests for gcc. This is currently required, because
the AutoDiffCodeGen system relies on implementation defined
behaviour. (Evalution order + copy elision)

Change-Id: Ib17aeb22bd4d81de6d838b55c1b6497fb3740d0e
diff --git a/include/ceres/internal/expression_ref.h b/include/ceres/internal/expression_ref.h
index 5f293b0..b79ccb4 100644
--- a/include/ceres/internal/expression_ref.h
+++ b/include/ceres/internal/expression_ref.h
@@ -65,28 +65,44 @@
   //   T x = CERES_LOCAL_VARIABLE(local_variable_);
   ExpressionRef(double&) = delete;
 
-  // Create an ASSIGNMENT expression from other to this.
+  // Copy construction/assignment creates an ASSIGNMENT expression from
+  // 'other' to 'this'.
   //
   // For example:
   //   a = b;        // With a.id = 5 and b.id = 3
   // will generate the following assignment:
   //   v_5 = v_3;
   //
-  // If this (lhs) ExpressionRef is currently not pointing to a variable
-  // (id==invalid), then we can eliminate the assignment by just letting "this"
-  // point to the same variable as "other".
+  //  If 'this' ExpressionRef is currently not pointing to a variable
+  // (id==invalid), then an assignment to a new variable is generated. Example:
+  //    T a = 5;
+  //    T b;
+  //    b = a;  // During the assignment 'b' is invalid
   //
-  // Example:
-  //   a = b;       // With a.id = invalid and b.id = 3
-  // will generate NO expression, but after this line the following will be
-  // true:
-  //    a.id == b.id == 3
-  //
-  // If 'other' is not pointing to a variable (id==invalid), we found an
-  // uninitialized assignment, which is handled as an error.
+  // The right hand side of the assignment (= the argument 'other') must be
+  // valid in every case. The following code will result in an error.
+  //   T a;
+  //   T b = a;  // Error: Uninitialized assignment
   ExpressionRef(const ExpressionRef& other);
   ExpressionRef& operator=(const ExpressionRef& other);
 
+  // Similar to the copy assignment above, but if 'this' is uninitialized, we
+  // can remove the copy and therefore eliminate one expression in the graph.
+  // For example:
+  //   T c;
+  //   c = a + b;
+  // will generate
+  //   v_2 = v_0 + v_1
+  // instead of an additional assigment from the temporary 'a + b' to 'c'. In
+  // C++ this concept is called "Copy Elision". This is used by the compiler to
+  // eliminate copies, for example, in a function that returns an object by
+  // value. We implement it ourself here, because large parts of copy elision
+  // are implementation defined, which means that every compiler can do it
+  // differently. More information on copy elision can be found here:
+  // https://en.cppreference.com/w/cpp/language/copy_elision
+  ExpressionRef(ExpressionRef&& other);
+  ExpressionRef& operator=(ExpressionRef&& other);
+
   // Compound operators
   ExpressionRef& operator+=(const ExpressionRef& x);
   ExpressionRef& operator-=(const ExpressionRef& x);
diff --git a/internal/ceres/CMakeLists.txt b/internal/ceres/CMakeLists.txt
index a3bd8b5..7fb9336 100644
--- a/internal/ceres/CMakeLists.txt
+++ b/internal/ceres/CMakeLists.txt
@@ -417,7 +417,6 @@
   ceres_test(block_sparse_matrix)
   ceres_test(c_api)
   ceres_test(canonical_views_clustering)
-  ceres_test(code_generator)
   ceres_test(compressed_col_sparse_matrix_utils)
   ceres_test(compressed_row_sparse_matrix)
   ceres_test(concurrent_queue)
@@ -438,9 +437,6 @@
   ceres_test(dynamic_sparsity)
   ceres_test(evaluation_callback)
   ceres_test(evaluator)
-  ceres_test(expression)
-  ceres_test(conditional_expressions)
-  ceres_test(expression_graph)
   ceres_test(fixed_array)
   ceres_test(gradient_checker)
   ceres_test(gradient_checking_cost_function)
@@ -501,6 +497,34 @@
 
   add_subdirectory(generated_bundle_adjustment_tests)
 
+  # Testing the AutoDiffCodegen system is more complicated, because function- and
+  # constructor calls have side-effects. In C++ the evaluation order and
+  # the elision of copies is implementation defined. Between different compilers,
+  # some expression might be evaluated in a different order or some copies might be
+  # removed.
+  #
+  # Therefore, we run tests that expect a particular compiler behaviour only on gcc.
+  #
+  # The semantic tests, which check the correctness by executing the generated code
+  # are still run on all platforms.
+  if(CMAKE_CXX_COMPILER_ID STREQUAL "GNU")
+      set(CXX_FLAGS_OLD ${CMAKE_CXX_FLAGS})
+      # From the man page:
+      #   The C++ standard allows an implementation to omit creating a
+      #   temporary which is only used to initialize another object of the
+      #   same type.  Specifying -fno-elide-constructors disables that
+      #   optimization, and forces G++ to call the copy constructor in all cases.
+      # We use this flag to get the same results between different versions of
+      # gcc and different optimization levels. Without this flag, testing would
+      # be very painfull and might break when a new compiler version is released.
+      set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -fno-elide-constructors")
+      ceres_test(expression)
+      ceres_test(code_generator)
+      ceres_test(conditional_expressions)
+      ceres_test(expression_graph)
+      set(CMAKE_CXX_FLAGS ${CXX_FLAGS_OLD})
+  endif()
+
 endif (BUILD_TESTING AND GFLAGS)
 
 macro(add_dependencies_to_benchmark BENCHMARK_TARGET)
diff --git a/internal/ceres/code_generator_test.cc b/internal/ceres/code_generator_test.cc
index c0feb41..c8908aa 100644
--- a/internal/ceres/code_generator_test.cc
+++ b/internal/ceres/code_generator_test.cc
@@ -117,21 +117,23 @@
 
 TEST(CodeGenerator, ASSIGNMENT) {
   StartRecordingExpressions();
-  T a = T(0);
-  T b = T(1);
-  T c = a;  // < This should not generate a line!
-  a = b;
-  a = a + b;  // < Create temporary + assignment
+  T a = T(0);  // 0
+  T b = T(1);  // 1
+  T c = a;     // 2
+  a = b;       // 3
+  a = a + b;   // 4 + 5
   auto graph = StopRecordingExpressions();
   std::vector<std::string> expected_code = {"{",
                                             "  double v_0;",
                                             "  double v_1;",
-                                            "  double v_3;",
+                                            "  double v_2;",
+                                            "  double v_4;",
                                             "  v_0 = 0;",
                                             "  v_1 = 1;",
+                                            "  v_2 = v_0;",
                                             "  v_0 = v_1;",
-                                            "  v_3 = v_0 + v_1;",
-                                            "  v_0 = v_3;",
+                                            "  v_4 = v_0 + v_1;",
+                                            "  v_0 = v_4;",
                                             "}"};
   GenerateAndCheck(graph, expected_code);
 }
diff --git a/internal/ceres/conditional_expressions_test.cc b/internal/ceres/conditional_expressions_test.cc
index 5b0d8e4..c2220b5 100644
--- a/internal/ceres/conditional_expressions_test.cc
+++ b/internal/ceres/conditional_expressions_test.cc
@@ -39,73 +39,6 @@
 namespace ceres {
 namespace internal {
 
-TEST(Expression, AssignmentElimination) {
-  using T = ExpressionRef;
-
-  StartRecordingExpressions();
-  T a(2);
-  T b;
-  b = a;
-  auto graph = StopRecordingExpressions();
-
-  // b is invalid during the assignment so we expect no expression to be
-  // generated. The only expression in the graph should be the constant
-  // assignment to a.
-  EXPECT_EQ(graph.Size(), 1);
-
-  // Expected code
-  //   v_0 = 2;
-
-  ExpressionGraph reference;
-  // clang-format off
-  // Id  Type                   Lhs  Value Name  Arguments
-  reference.InsertExpression(0,  ExpressionType::COMPILE_TIME_CONSTANT, 0,   {}, "", 2);
-  // clang-format on
-  EXPECT_EQ(reference, graph);
-
-  // Variables after execution:
-  //
-  // a      <=> v_0
-  // b      <=> v_0
-  EXPECT_EQ(a.id, 0);
-  EXPECT_EQ(b.id, 0);
-}
-
-TEST(Expression, Assignment) {
-  using T = ExpressionRef;
-
-  StartRecordingExpressions();
-  T a(2);
-  T b(4);
-  b = a;
-  auto graph = StopRecordingExpressions();
-
-  // b is valid during the assignment so we expect an
-  // additional assignment expression.
-  EXPECT_EQ(graph.Size(), 3);
-
-  // Expected code
-  //   v_0 = 2;
-  //   v_1 = 4;
-  //   v_1 = v_0;
-
-  ExpressionGraph reference;
-  // clang-format off
-  // Id, Type, Lhs, Value, Name, Arguments
-  reference.InsertExpression(  0,  ExpressionType::COMPILE_TIME_CONSTANT,   0,    {}  , "",  2);
-  reference.InsertExpression(  1,  ExpressionType::COMPILE_TIME_CONSTANT,   1,     {} , "",  4);
-  reference.InsertExpression(  2,             ExpressionType::ASSIGNMENT,   1,     {0}, "",  0);
-  // clang-format on
-  EXPECT_EQ(reference, graph);
-
-  // Variables after execution:
-  //
-  // a      <=> v_0
-  // b      <=> v_1
-  EXPECT_EQ(a.id, 0);
-  EXPECT_EQ(b.id, 1);
-}
-
 TEST(Expression, ConditionalMinimal) {
   using T = ExpressionRef;
 
diff --git a/internal/ceres/expression_ref.cc b/internal/ceres/expression_ref.cc
index 23af0d1..5a330b9 100644
--- a/internal/ceres/expression_ref.cc
+++ b/internal/ceres/expression_ref.cc
@@ -49,16 +49,50 @@
 ExpressionRef& ExpressionRef::operator=(const ExpressionRef& other) {
   // Assigning an uninitialized variable to another variable is an error.
   CHECK(other.IsInitialized()) << "Uninitialized Assignment.";
+  if (IsInitialized()) {
+    // Create assignment from other -> this
+    Expression::CreateAssignment(this->id, other.id);
+  } else {
+    // Create a new variable and
+    // Create assignment from other -> this
+    // Passing kInvalidExpressionId to CreateAssignment generates a new variable
+    // name which we store in the id.
+    id = Expression::CreateAssignment(kInvalidExpressionId, other.id);
+  }
+  return *this;
+}
+
+ExpressionRef::ExpressionRef(ExpressionRef&& other) {
+  *this = std::move(other);
+}
+
+ExpressionRef& ExpressionRef::operator=(ExpressionRef&& other) {
+  // Assigning an uninitialized variable to another variable is an error.
+  CHECK(other.IsInitialized()) << "Uninitialized Assignment.";
 
   if (IsInitialized()) {
     // Create assignment from other -> this
     Expression::CreateAssignment(id, other.id);
   } else {
-    // Special case: "this" expressionref is invalid
-    //    -> Skip assignment
-    //    -> Let "this" point to the same variable as other
+    // Special case: 'this' is uninitialized and other is an rvalue.
+    //    -> Implement copy elision by only setting the reference
+    // This reduces the number of generated expressions roughly by a factor
+    // of 2. For example, in the following statement:
+    //   T c = a + b;
+    // The result of 'a + b' is an rvalue reference to ExpressionRef. Therefore,
+    // the move constructor of 'c' is called. Since 'c' is also uninitialized,
+    // this branch here is taken and the copy is removed. After this function
+    // 'c' will just point to the temporary created by the 'a + b' expression.
+    // This is valid, because we don't have any scoping information and
+    // therefore assume global scope for all temporary variables. The generated
+    // code for the single statement above, is:
+    //   v_2 = v_0 + v_1;   // With c.id = 2
+    // Without this move constructor the following two lines would be generated:
+    //   v_2 = v_0 + v_1;
+    //   v_3 = v_2;        // With c.id = 3
     id = other.id;
   }
+  other.id = kInvalidExpressionId;
   return *this;
 }
 
diff --git a/internal/ceres/expression_test.cc b/internal/ceres/expression_test.cc
index 86159d9..84d1fa4 100644
--- a/internal/ceres/expression_test.cc
+++ b/internal/ceres/expression_test.cc
@@ -147,5 +147,84 @@
   EXPECT_EQ(reference, graph);
 }
 
+TEST(Expression, Assignment) {
+  using T = ExpressionRef;
+
+  StartRecordingExpressions();
+  T a = 1;
+  T b = 2;
+  b = a;
+  auto graph = StopRecordingExpressions();
+
+  EXPECT_EQ(graph.Size(), 3);
+
+  ExpressionGraph reference;
+  // clang-format off
+  // Id, Type, Lhs, Value, Name, Arguments
+  reference.InsertExpression(  0,  ExpressionType::COMPILE_TIME_CONSTANT,   0,      {},        "",  1);
+  reference.InsertExpression(  1,  ExpressionType::COMPILE_TIME_CONSTANT,   1,      {},        "",  2);
+  reference.InsertExpression(  2,             ExpressionType::ASSIGNMENT,   1,      {0},        "",  0);
+  // clang-format on
+  EXPECT_EQ(reference, graph);
+}
+
+TEST(Expression, AssignmentCreate) {
+  using T = ExpressionRef;
+
+  StartRecordingExpressions();
+  T a = 2;
+  T b = a;
+  auto graph = StopRecordingExpressions();
+
+  EXPECT_EQ(graph.Size(), 2);
+
+  ExpressionGraph reference;
+  // clang-format off
+  // Id, Type, Lhs, Value, Name, Arguments
+  reference.InsertExpression(  0,  ExpressionType::COMPILE_TIME_CONSTANT,   0,      {},        "",  2);
+  reference.InsertExpression(  1,             ExpressionType::ASSIGNMENT,   1,      {0},        "",  0);
+  // clang-format on
+  EXPECT_EQ(reference, graph);
+}
+
+TEST(Expression, MoveAssignmentCreate) {
+  using T = ExpressionRef;
+
+  StartRecordingExpressions();
+  T a = 1;
+  T b = std::move(a);
+  auto graph = StopRecordingExpressions();
+
+  EXPECT_EQ(graph.Size(), 1);
+
+  ExpressionGraph reference;
+  // clang-format off
+  // Id, Type, Lhs, Value, Name, Arguments
+  reference.InsertExpression(  0,  ExpressionType::COMPILE_TIME_CONSTANT,   0,      {},        "",  1);
+  // clang-format on
+  EXPECT_EQ(reference, graph);
+}
+
+TEST(Expression, MoveAssignment) {
+  using T = ExpressionRef;
+
+  StartRecordingExpressions();
+  T a = 1;
+  T b = 2;
+  b = std::move(a);
+  auto graph = StopRecordingExpressions();
+
+  EXPECT_EQ(graph.Size(), 3);
+
+  ExpressionGraph reference;
+  // clang-format off
+  // Id, Type, Lhs, Value, Name, Arguments
+  reference.InsertExpression(  0,  ExpressionType::COMPILE_TIME_CONSTANT,   0,      {},        "",  1);
+  reference.InsertExpression(  1,  ExpressionType::COMPILE_TIME_CONSTANT,   1,      {},        "",  2);
+  reference.InsertExpression(  2,             ExpressionType::ASSIGNMENT,   1,      {0},        "",  0);
+  // clang-format on
+  EXPECT_EQ(reference, graph);
+}
+
 }  // namespace internal
 }  // namespace ceres