Autodiff Codegen Part 1: Expressions
This patch adds the 'Expression' class, which is a fundamental
building block of automatic code generation. The expressions can
be used as scalar types for cost functors as well as Jets.
Dynamic branching is not yet supported.
Change-Id: I8c61bee5c307e0eec20fd39382683ea90f720dff
diff --git a/include/ceres/internal/expression.h b/include/ceres/internal/expression.h
new file mode 100644
index 0000000..c990d93
--- /dev/null
+++ b/include/ceres/internal/expression.h
@@ -0,0 +1,203 @@
+// Ceres Solver - A fast non-linear least squares minimizer
+// Copyright 2019 Google Inc. All rights reserved.
+// http://code.google.com/p/ceres-solver/
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//
+// * Redistributions of source code must retain the above copyright notice,
+// this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above copyright notice,
+// this list of conditions and the following disclaimer in the documentation
+// and/or other materials provided with the distribution.
+// * Neither the name of Google Inc. nor the names of its contributors may be
+// used to endorse or promote products derived from this software without
+// specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+// POSSIBILITY OF SUCH DAMAGE.
+//
+// Author: darius.rueckert@fau.de (Darius Rueckert)
+//
+//
+// This file contains the basic expression type, which is used during code
+// generation. Only assignment expressions of the following form are supported:
+//
+// result = [constant|binary_expr|functioncall]
+//
+// Examples:
+// v_78 = v_28 / v_62;
+// v_97 = exp(v_20);
+// v_89 = 3.000000;
+//
+//
+#ifndef CERES_PUBLIC_EXPRESSION_H_
+#define CERES_PUBLIC_EXPRESSION_H_
+
+#include <string>
+#include <vector>
+
+namespace ceres {
+namespace internal {
+
+using ExpressionId = int;
+static constexpr ExpressionId kInvalidExpressionId = -1;
+
+enum class ExpressionType {
+ // v_0 = 3.1415;
+ COMPILE_TIME_CONSTANT,
+
+ // For example a local member of the cost-functor.
+ // v_0 = _observed_point_x;
+ RUNTIME_CONSTANT,
+
+ // Input parameter
+ // v_0 = parameters[1][5];
+ PARAMETER,
+
+ // Output Variable Assignemnt
+ // residual[0] = v_51;
+ OUTPUT_ASSIGNMENT,
+
+ // Trivial Assignment
+ // v_1 = v_0;
+ ASSIGNMENT,
+
+ // Binary Arithmetic Operations
+ // v_2 = v_0 + v_1
+ PLUS,
+ MINUS,
+ MULTIPLICATION,
+ DIVISION,
+
+ // Unary Arithmetic Operation
+ // v_1 = -(v_0);
+ // v_2 = +(v_1);
+ UNARY_MINUS,
+ UNARY_PLUS,
+
+ // Binary Comparison. (<,>,&&,...)
+ // This is the only expressions which returns a 'bool'.
+ // const bool v_2 = v_0 < v_1
+ BINARY_COMPARISON,
+
+ // The !-operator on logical expression.
+ LOGICAL_NEGATION,
+
+ // General Function Call.
+ // v_5 = f(v_0,v_1,...)
+ FUNCTION_CALL,
+
+ // The ternary ?-operator. Separated from the general function call for easier
+ // access.
+ // v_3 = ternary(v_0,v_1,v_2);
+ TERNARY,
+
+ // No Operation. A placeholder for an 'empty' expressions which will be
+ // optimized out during code generation.
+ NOP
+};
+
+// This class contains all data that is required to generate one line of code.
+// Each line has the following form:
+//
+// lhs = rhs;
+//
+// The left hand side is the variable name given by its own id. The right hand
+// side depends on the ExpressionType. For example, a COMPILE_TIME_CONSTANT
+// expressions with id 4 generates the following line:
+// v_4 = 3.1415;
+//
+// Objects of this class are created indirectly using the static CreateXX
+// methods. During creation, the Expression objects are added to the
+// ExpressionGraph (see expression_graph.h).
+class Expression {
+ public:
+ // These functions create the corresponding expression, add them to an
+ // internal vector and return a reference to them.
+ static ExpressionId CreateCompileTimeConstant(double v);
+ static ExpressionId CreateRuntimeConstant(const std::string& name);
+ static ExpressionId CreateParameter(const std::string& name);
+ static ExpressionId CreateOutputAssignment(ExpressionId v,
+ const std::string& name);
+ static ExpressionId CreateAssignment(ExpressionId v);
+ static ExpressionId CreateBinaryArithmetic(ExpressionType type,
+ ExpressionId l,
+ ExpressionId r);
+ static ExpressionId CreateUnaryArithmetic(ExpressionType type,
+ ExpressionId v);
+ static ExpressionId CreateBinaryCompare(const std::string& name,
+ ExpressionId l,
+ ExpressionId r);
+ static ExpressionId CreateLogicalNegation(ExpressionId v);
+ static ExpressionId CreateFunctionCall(
+ const std::string& name, const std::vector<ExpressionId>& params);
+ static ExpressionId CreateTernary(ExpressionId condition,
+ ExpressionId if_true,
+ ExpressionId if_false);
+
+ // Returns true if the expression type is one of the basic math-operators:
+ // +,-,*,/
+ bool IsArithmetic() const;
+
+ // If this expression is the compile time constant with the given value.
+ // Used during optimization to collapse zero/one arithmetic operations.
+ // b = a + 0; -> b = a;
+ bool IsCompileTimeConstantAndEqualTo(double constant) const;
+
+ // Checks if "other" is identical to "this" so that one of the epxressions can
+ // be replaced by a trivial assignment. Used during common subexpression
+ // elimination.
+ bool IsReplaceableBy(const Expression& other) const;
+
+ // Replace this expression by 'other'.
+ // The current id will be not replaced. That means other experssions
+ // referencing this one stay valid.
+ void Replace(const Expression& other);
+
+ // If this expression has 'other' as an argument.
+ bool DirectlyDependsOn(ExpressionId other) const;
+
+ // Converts this expression into a NOP
+ void MakeNop();
+
+ private:
+ // Only ExpressionGraph is allowed to call the constructor, because it manages
+ // the memory and ids.
+ friend class ExpressionGraph;
+
+ // Private constructor. Use the "CreateXX" functions instead.
+ Expression(ExpressionType type, ExpressionId id);
+
+ ExpressionType type_ = ExpressionType::NOP;
+ const ExpressionId id_ = kInvalidExpressionId;
+
+ // Expressions have different number of arguments. For example a binary "+"
+ // has 2 parameters and a function call to "sin" has 1 parameter. Here, a
+ // reference to these paratmers is stored. Note: The order matters!
+ std::vector<ExpressionId> arguments_;
+
+ // Depending on the type this name is one of the following:
+ // (type == FUNCTION_CALL) -> the function name
+ // (type == PARAMETER) -> the parameter name
+ // (type == OUTPUT_ASSIGN) -> the output variable name
+ // (type == BINARY_COMPARE)-> the comparison symbol "<","&&",...
+ // else -> unused
+ std::string name_;
+
+ // Only valid if type == COMPILE_TIME_CONSTANT
+ double value_ = 0;
+};
+
+} // namespace internal
+} // namespace ceres
+#endif
diff --git a/include/ceres/internal/expression_graph.h b/include/ceres/internal/expression_graph.h
new file mode 100644
index 0000000..446fddb
--- /dev/null
+++ b/include/ceres/internal/expression_graph.h
@@ -0,0 +1,92 @@
+// Ceres Solver - A fast non-linear least squares minimizer
+// Copyright 2019 Google Inc. All rights reserved.
+// http://code.google.com/p/ceres-solver/
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//
+// * Redistributions of source code must retain the above copyright notice,
+// this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above copyright notice,
+// this list of conditions and the following disclaimer in the documentation
+// and/or other materials provided with the distribution.
+// * Neither the name of Google Inc. nor the names of its contributors may be
+// used to endorse or promote products derived from this software without
+// specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+// POSSIBILITY OF SUCH DAMAGE.
+//
+// Author: darius.rueckert@fau.de (Darius Rueckert)
+
+#ifndef CERES_PUBLIC_EXPRESSION_TREE_H_
+#define CERES_PUBLIC_EXPRESSION_TREE_H_
+
+#include <vector>
+
+#include "expression.h"
+
+namespace ceres {
+namespace internal {
+
+// A directed, acyclic, unconnected graph containing all expressions of a
+// program.
+//
+// The expression graph is stored linear in the expressions_ array. The order is
+// identical to the execution order. Each expression can have multiple children
+// and multiple parents.
+// A is child of B <=> B has A as a parameter <=> B.DirectlyDependsOn(A)
+// A is parent of B <=> A has B as a parameter <=> A.DirectlyDependsOn(B)
+class ExpressionGraph {
+ public:
+ // Creates an expression and adds it to expressions_.
+ // The returned reference will be invalid after this function is called again.
+ Expression& CreateExpression(ExpressionType type);
+
+ // Checks if A depends on B.
+ // -> B is a descendant of A
+ bool DependsOn(ExpressionId A, ExpressionId B) const;
+
+ Expression& ExpressionForId(ExpressionId id) { return expressions_[id]; }
+ const Expression& ExpressionForId(ExpressionId id) const {
+ return expressions_[id];
+ }
+
+ int Size() const { return expressions_.size(); }
+
+ private:
+ // All Expressions are referenced by an ExpressionId. The ExpressionId is the
+ // index into this array. Each expression has a list of ExpressionId as
+ // arguments. These references form the graph.
+ std::vector<Expression> expressions_;
+};
+
+// After calling this method, all operations on 'ExpressionRef' objects will be
+// recorded into an ExpressionGraph. You can obtain this graph by calling
+// StopRecordingExpressions.
+//
+// Performing expression operations before calling StartRecordingExpressions or
+// calling StartRecodring. twice is an error.
+void StartRecordingExpressions();
+
+// Stops recording and returns all expressions that have been executed since the
+// call to StartRecordingExpressions. The internal ExpressionGraph will be
+// invalidated and a second consecutive call to this method results in an error.
+ExpressionGraph StopRecordingExpressions();
+
+// Returns a pointer to the active expression tree.
+// Normal users should not use this functions.
+ExpressionGraph* GetCurrentExpressionGraph();
+
+} // namespace internal
+} // namespace ceres
+#endif
diff --git a/include/ceres/internal/expression_ref.h b/include/ceres/internal/expression_ref.h
new file mode 100644
index 0000000..67ff227
--- /dev/null
+++ b/include/ceres/internal/expression_ref.h
@@ -0,0 +1,164 @@
+// Ceres Solver - A fast non-linear least squares minimizer
+// Copyright 2019 Google Inc. All rights reserved.
+// http://code.google.com/p/ceres-solver/
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//
+// * Redistributions of source code must retain the above copyright notice,
+// this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above copyright notice,
+// this list of conditions and the following disclaimer in the documentation
+// and/or other materials provided with the distribution.
+// * Neither the name of Google Inc. nor the names of its contributors may be
+// used to endorse or promote products derived from this software without
+// specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+// POSSIBILITY OF SUCH DAMAGE.
+//
+// Author: darius.rueckert@fau.de (Darius Rueckert)
+//
+// TODO: Documentation
+#ifndef CERES_PUBLIC_EXPRESSION_REF_H_
+#define CERES_PUBLIC_EXPRESSION_REF_H_
+
+#include <string>
+#include "ceres/jet.h"
+#include "expression.h"
+
+namespace ceres {
+namespace internal {
+
+// This class represents a scalar value that creates new expressions during
+// evaluation. ExpressionRef can be used as template parameter for cost functors
+// and Jets.
+//
+// ExpressionRef should be passed by value.
+struct ExpressionRef {
+ ExpressionRef() = default;
+
+ // Create a compile time constant expression directly from a double value.
+ // This is important so that we can write T(3.14) in our code and
+ // it's automatically converted to the correct expression.
+ explicit ExpressionRef(double compile_time_constant);
+
+ // Returns v_id
+ std::string ToString() const;
+
+ // Compound operators
+ ExpressionRef& operator+=(ExpressionRef x);
+ ExpressionRef& operator-=(ExpressionRef x);
+ ExpressionRef& operator*=(ExpressionRef x);
+ ExpressionRef& operator/=(ExpressionRef x);
+
+ // The index into the ExpressionGraph data array.
+ ExpressionId id = kInvalidExpressionId;
+
+ static ExpressionRef Create(ExpressionId id);
+};
+
+// Arithmetic Operators
+ExpressionRef operator-(ExpressionRef x);
+ExpressionRef operator+(ExpressionRef x);
+ExpressionRef operator+(ExpressionRef x, ExpressionRef y);
+ExpressionRef operator-(ExpressionRef x, ExpressionRef y);
+ExpressionRef operator*(ExpressionRef x, ExpressionRef y);
+ExpressionRef operator/(ExpressionRef x, ExpressionRef y);
+
+// Functions
+// TODO: Add all function supported by Jet.
+ExpressionRef sin(ExpressionRef x);
+
+// This additonal type is required, so that we can detect invalid conditions
+// during compile time. For example, the following should create a compile time
+// error:
+//
+// ExpressionRef a(5);
+// CERES_IF(a){ // Error: Invalid conversion
+// ...
+//
+// Following will work:
+//
+// ExpressionRef a(5), b(7);
+// ComparisonExpressionRef c = a < b;
+// CERES_IF(c){
+// ...
+struct ComparisonExpressionRef {
+ ExpressionId id;
+ explicit ComparisonExpressionRef(ExpressionRef ref) : id(ref.id) {}
+};
+
+ExpressionRef Ternary(ComparisonExpressionRef c,
+ ExpressionRef a,
+ ExpressionRef b);
+
+// Comparison operators
+ComparisonExpressionRef operator<(ExpressionRef a, ExpressionRef b);
+ComparisonExpressionRef operator<=(ExpressionRef a, ExpressionRef b);
+ComparisonExpressionRef operator>(ExpressionRef a, ExpressionRef b);
+ComparisonExpressionRef operator>=(ExpressionRef a, ExpressionRef b);
+ComparisonExpressionRef operator==(ExpressionRef a, ExpressionRef b);
+ComparisonExpressionRef operator!=(ExpressionRef a, ExpressionRef b);
+
+// Logical Operators
+ComparisonExpressionRef operator&&(ComparisonExpressionRef a,
+ ComparisonExpressionRef b);
+ComparisonExpressionRef operator||(ComparisonExpressionRef a,
+ ComparisonExpressionRef b);
+ComparisonExpressionRef operator!(ComparisonExpressionRef a);
+
+// This struct is used to mark numbers which are constant over
+// multiple invocations but can differ between instances.
+template <typename T>
+struct RuntimeConstant {
+ using ReturnType = T;
+ static inline ReturnType Get(double v, const char* name) { return v; }
+};
+
+template <typename G, int N>
+struct RuntimeConstant<Jet<G, N>> {
+ using ReturnType = Jet<G, N>;
+ static inline Jet<G, N> Get(double v, const char* name) {
+ return Jet<G, N>(v);
+ }
+};
+
+template <int N>
+struct RuntimeConstant<Jet<ExpressionRef, N>> {
+ using ReturnType = Jet<ExpressionRef, N>;
+ static inline ReturnType Get(double v, const char* name) {
+ // Note: The scalar value of v will be thrown away, because we don't need it
+ // during code generation.
+ (void)v;
+ return Jet<ExpressionRef, N>(Expression::CreateRuntimeConstant(name));
+ }
+};
+
+template <typename T>
+inline typename RuntimeConstant<T>::ReturnType MakeRuntimeConstant(
+ double v, const char* name) {
+ return RuntimeConstant<T>::Get(v, name);
+}
+
+#define CERES_EXPRESSION_RUNTIME_CONSTANT(_v) \
+ ceres::internal::MakeRuntimeConstant<T>(_v, #_v)
+} // namespace internal
+
+// See jet.h for more info on this type.
+template <>
+struct ComparisonReturnType<internal::ExpressionRef> {
+ using type = internal::ComparisonExpressionRef;
+};
+
+} // namespace ceres
+#endif
diff --git a/include/ceres/jet.h b/include/ceres/jet.h
index 8d83563..25d11e6 100644
--- a/include/ceres/jet.h
+++ b/include/ceres/jet.h
@@ -168,6 +168,20 @@
namespace ceres {
+// The return type of a Jet comparison, for example from <, &&, ==.
+//
+// In the context of traditional Ceres Jet operations, this would
+// always be a bool. However, in the autodiff code generation context,
+// the return is always an expression, and so a different type must be
+// used as a return from comparisons.
+//
+// In the autodiff codegen context, this function is overloaded so that 'type'
+// is one of the autodiff code generation expression types.
+template <typename T>
+struct ComparisonReturnType {
+ using type = bool;
+};
+
template <typename T, int N>
struct Jet {
enum { DIMENSION = N };
@@ -353,18 +367,21 @@
}
// Binary comparison operators for both scalars and jets.
-#define CERES_DEFINE_JET_COMPARISON_OPERATOR(op) \
- template <typename T, int N> \
- inline bool operator op(const Jet<T, N>& f, const Jet<T, N>& g) { \
- return f.a op g.a; \
- } \
- template <typename T, int N> \
- inline bool operator op(const T& s, const Jet<T, N>& g) { \
- return s op g.a; \
- } \
- template <typename T, int N> \
- inline bool operator op(const Jet<T, N>& f, const T& s) { \
- return f.a op s; \
+#define CERES_DEFINE_JET_COMPARISON_OPERATOR(op) \
+ template <typename T, int N> \
+ inline typename ComparisonReturnType<T>::type operator op( \
+ const Jet<T, N>& f, const Jet<T, N>& g) { \
+ return f.a op g.a; \
+ } \
+ template <typename T, int N> \
+ inline typename ComparisonReturnType<T>::type operator op( \
+ const T& s, const Jet<T, N>& g) { \
+ return s op g.a; \
+ } \
+ template <typename T, int N> \
+ inline typename ComparisonReturnType<T>::type operator op( \
+ const Jet<T, N>& f, const T& s) { \
+ return f.a op s; \
}
CERES_DEFINE_JET_COMPARISON_OPERATOR(<) // NOLINT
CERES_DEFINE_JET_COMPARISON_OPERATOR(<=) // NOLINT
@@ -374,6 +391,26 @@
CERES_DEFINE_JET_COMPARISON_OPERATOR(!=) // NOLINT
#undef CERES_DEFINE_JET_COMPARISON_OPERATOR
+// A function equivalent to the ternary ?-operator.
+// This function is required, because in the context of code generation a
+// comparison returns an expression type which is not convertible to bool.
+template <typename T>
+inline T Ternary(bool c, T a, T b) {
+ return c ? a : b;
+}
+
+template <typename T, int N>
+inline Jet<T, N> Ternary(typename ComparisonReturnType<T>::type c,
+ const Jet<T, N>& f,
+ const Jet<T, N>& g) {
+ Jet<T, N> r;
+ r.a = Ternary(c, f.a, g.a);
+ for (int i = 0; i < N; ++i) {
+ r.v[i] = Ternary(c, f.v[i], g.v[i]);
+ }
+ return r;
+}
+
// Pull some functions from namespace std.
//
// This is necessary because we want to use the same name (e.g. 'sqrt') for
diff --git a/internal/ceres/CMakeLists.txt b/internal/ceres/CMakeLists.txt
index e452f48..01c23ca 100644
--- a/internal/ceres/CMakeLists.txt
+++ b/internal/ceres/CMakeLists.txt
@@ -82,6 +82,9 @@
dynamic_sparse_normal_cholesky_solver.cc
evaluator.cc
eigensparse.cc
+ expression.cc
+ expression_graph.cc
+ expression_ref.cc
file.cc
float_suitesparse.cc
float_cxsparse.cc
@@ -433,6 +436,8 @@
ceres_test(dynamic_sparsity)
ceres_test(evaluation_callback)
ceres_test(evaluator)
+ ceres_test(expression)
+ ceres_test(expression_graph)
ceres_test(fixed_array)
ceres_test(gradient_checker)
ceres_test(gradient_checking_cost_function)
diff --git a/internal/ceres/expression.cc b/internal/ceres/expression.cc
new file mode 100644
index 0000000..3edcc7d
--- /dev/null
+++ b/internal/ceres/expression.cc
@@ -0,0 +1,178 @@
+// Ceres Solver - A fast non-linear least squares minimizer
+// Copyright 2019 Google Inc. All rights reserved.
+// http://code.google.com/p/ceres-solver/
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//
+// * Redistributions of source code must retain the above copyright notice,
+// this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above copyright notice,
+// this list of conditions and the following disclaimer in the documentation
+// and/or other materials provided with the distribution.
+// * Neither the name of Google Inc. nor the names of its contributors may be
+// used to endorse or promote products derived from this software without
+// specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+// POSSIBILITY OF SUCH DAMAGE.
+//
+// Author: darius.rueckert@fau.de (Darius Rueckert)
+
+#include "ceres/internal/expression.h"
+#include <algorithm>
+
+#include "ceres/internal/expression_graph.h"
+#include "glog/logging.h"
+
+namespace ceres {
+namespace internal {
+
+static Expression& MakeExpression(ExpressionType type) {
+ auto pool = GetCurrentExpressionGraph();
+ CHECK(pool)
+ << "The ExpressionGraph has to be created before using Expressions. This "
+ "is achieved by calling ceres::StartRecordingExpressions.";
+ return pool->CreateExpression(type);
+}
+
+ExpressionId Expression::CreateCompileTimeConstant(double v) {
+ auto& expr = MakeExpression(ExpressionType::COMPILE_TIME_CONSTANT);
+ expr.value_ = v;
+ return expr.id_;
+}
+
+ExpressionId Expression::CreateRuntimeConstant(const std::string& name) {
+ auto& expr = MakeExpression(ExpressionType::RUNTIME_CONSTANT);
+ expr.name_ = name;
+ return expr.id_;
+}
+
+ExpressionId Expression::CreateParameter(const std::string& name) {
+ auto& expr = MakeExpression(ExpressionType::PARAMETER);
+ expr.name_ = name;
+ return expr.id_;
+}
+
+ExpressionId Expression::CreateAssignment(ExpressionId v) {
+ auto& expr = MakeExpression(ExpressionType::ASSIGNMENT);
+ expr.arguments_.push_back(v);
+ return expr.id_;
+}
+
+ExpressionId Expression::CreateUnaryArithmetic(ExpressionType type,
+ ExpressionId v) {
+ auto& expr = MakeExpression(type);
+ expr.arguments_.push_back(v);
+ return expr.id_;
+}
+
+ExpressionId Expression::CreateOutputAssignment(ExpressionId v,
+ const std::string& name) {
+ auto& expr = MakeExpression(ExpressionType::OUTPUT_ASSIGNMENT);
+ expr.arguments_.push_back(v);
+ expr.name_ = name;
+ return expr.id_;
+}
+
+ExpressionId Expression::CreateFunctionCall(
+ const std::string& name, const std::vector<ExpressionId>& params) {
+ auto& expr = MakeExpression(ExpressionType::FUNCTION_CALL);
+ expr.arguments_ = params;
+ expr.name_ = name;
+ return expr.id_;
+}
+
+ExpressionId Expression::CreateTernary(ExpressionId condition,
+ ExpressionId if_true,
+ ExpressionId if_false) {
+ auto& expr = MakeExpression(ExpressionType::TERNARY);
+ expr.arguments_.push_back(condition);
+ expr.arguments_.push_back(if_true);
+ expr.arguments_.push_back(if_false);
+ return expr.id_;
+}
+
+ExpressionId Expression::CreateBinaryCompare(const std::string& name,
+ ExpressionId l,
+ ExpressionId r) {
+ auto& expr = MakeExpression(ExpressionType::BINARY_COMPARISON);
+ expr.arguments_.push_back(l);
+ expr.arguments_.push_back(r);
+ expr.name_ = name;
+ return expr.id_;
+}
+
+ExpressionId Expression::CreateLogicalNegation(ExpressionId v) {
+ auto& expr = MakeExpression(ExpressionType::LOGICAL_NEGATION);
+ expr.arguments_.push_back(v);
+ return expr.id_;
+}
+
+ExpressionId Expression::CreateBinaryArithmetic(ExpressionType type,
+ ExpressionId l,
+ ExpressionId r) {
+ auto& expr = MakeExpression(type);
+ expr.arguments_.push_back(l);
+ expr.arguments_.push_back(r);
+ return expr.id_;
+}
+Expression::Expression(ExpressionType type, ExpressionId id)
+ : type_(type), id_(id) {}
+
+bool Expression::IsArithmetic() const {
+ switch (type_) {
+ case ExpressionType::PLUS:
+ case ExpressionType::MULTIPLICATION:
+ case ExpressionType::DIVISION:
+ case ExpressionType::MINUS:
+ case ExpressionType::UNARY_MINUS:
+ case ExpressionType::UNARY_PLUS:
+ return true;
+ default:
+ return false;
+ }
+}
+
+bool Expression::IsReplaceableBy(const Expression& other) const {
+ // Check everything except the id.
+ return (type_ == other.type_ && name_ == other.name_ &&
+ value_ == other.value_ && arguments_ == other.arguments_);
+}
+
+void Expression::Replace(const Expression& other) {
+ if (other.id_ == id_) {
+ return;
+ }
+
+ type_ = other.type_;
+ arguments_ = other.arguments_;
+ name_ = other.name_;
+ value_ = other.value_;
+}
+
+bool Expression::DirectlyDependsOn(ExpressionId other) const {
+ return (std::find(arguments_.begin(), arguments_.end(), other) !=
+ arguments_.end());
+}
+
+bool Expression::IsCompileTimeConstantAndEqualTo(double constant) const {
+ return type_ == ExpressionType::COMPILE_TIME_CONSTANT && value_ == constant;
+}
+
+void Expression::MakeNop() {
+ type_ = ExpressionType::NOP;
+ arguments_.clear();
+}
+
+} // namespace internal
+} // namespace ceres
diff --git a/internal/ceres/expression_graph.cc b/internal/ceres/expression_graph.cc
new file mode 100644
index 0000000..0757b97
--- /dev/null
+++ b/internal/ceres/expression_graph.cc
@@ -0,0 +1,85 @@
+// Ceres Solver - A fast non-linear least squares minimizer
+// Copyright 2019 Google Inc. All rights reserved.
+// http://code.google.com/p/ceres-solver/
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//
+// * Redistributions of source code must retain the above copyright notice,
+// this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above copyright notice,
+// this list of conditions and the following disclaimer in the documentation
+// and/or other materials provided with the distribution.
+// * Neither the name of Google Inc. nor the names of its contributors may be
+// used to endorse or promote products derived from this software without
+// specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+// POSSIBILITY OF SUCH DAMAGE.
+//
+// Author: darius.rueckert@fau.de (Darius Rueckert)
+
+#include "ceres/internal/expression_graph.h"
+
+#include "glog/logging.h"
+namespace ceres {
+namespace internal {
+
+static ExpressionGraph* expression_pool = nullptr;
+
+void StartRecordingExpressions() {
+ CHECK(expression_pool == nullptr)
+ << "Expression recording must be stopped before calling "
+ "StartRecordingExpressions again.";
+ expression_pool = new ExpressionGraph;
+}
+
+ExpressionGraph StopRecordingExpressions() {
+ CHECK(expression_pool)
+ << "Expression recording hasn't started yet or you tried "
+ "to stop it twice.";
+ ExpressionGraph result = std::move(*expression_pool);
+ delete expression_pool;
+ expression_pool = nullptr;
+ return result;
+}
+
+ExpressionGraph* GetCurrentExpressionGraph() { return expression_pool; }
+
+Expression& ExpressionGraph::CreateExpression(ExpressionType type) {
+ auto id = expressions_.size();
+ Expression expr(type, id);
+ expressions_.push_back(expr);
+ return expressions_.back();
+}
+
+bool ExpressionGraph::DependsOn(ExpressionId A, ExpressionId B) const {
+ // Depth first search on the expression graph
+ // Equivalent Recursive Implementation:
+ // if (A.DirectlyDependsOn(B)) return true;
+ // for (auto p : A.params_) {
+ // if (pool[p.id].DependsOn(B, pool)) return true;
+ // }
+ std::vector<ExpressionId> stack = ExpressionForId(A).arguments_;
+ while (!stack.empty()) {
+ auto top = stack.back();
+ stack.pop_back();
+ if (top == B) {
+ return true;
+ }
+ auto& expr = ExpressionForId(top);
+ stack.insert(stack.end(), expr.arguments_.begin(), expr.arguments_.end());
+ }
+ return false;
+}
+} // namespace internal
+} // namespace ceres
diff --git a/internal/ceres/expression_graph_test.cc b/internal/ceres/expression_graph_test.cc
new file mode 100644
index 0000000..ee06f1a
--- /dev/null
+++ b/internal/ceres/expression_graph_test.cc
@@ -0,0 +1,77 @@
+// Ceres Solver - A fast non-linear least squares minimizer
+// Copyright 2019 Google Inc. All rights reserved.
+// http://code.google.com/p/ceres-solver/
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//
+// * Redistributions of source code must retain the above copyright notice,
+// this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above copyright notice,
+// this list of conditions and the following disclaimer in the documentation
+// and/or other materials provided with the distribution.
+// * Neither the name of Google Inc. nor the names of its contributors may be
+// used to endorse or promote products derived from this software without
+// specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+// POSSIBILITY OF SUCH DAMAGE.
+//
+// Author: darius.rueckert@fau.de (Darius Rueckert)
+//
+// Test expression creation and logic.
+
+#include "ceres/internal/expression_graph.h"
+#include "ceres/internal/expression_ref.h"
+
+#include "gtest/gtest.h"
+
+namespace ceres {
+namespace internal {
+
+TEST(ExpressionGraph, Creation) {
+ using T = ExpressionRef;
+ ExpressionGraph graph;
+
+ StartRecordingExpressions();
+ graph = StopRecordingExpressions();
+ EXPECT_EQ(graph.Size(), 0);
+
+ StartRecordingExpressions();
+ T a(1);
+ T b(2);
+ T c = a + b;
+ graph = StopRecordingExpressions();
+ EXPECT_EQ(graph.Size(), 3);
+}
+
+TEST(ExpressionGraph, Dependencies) {
+ using T = ExpressionRef;
+
+ StartRecordingExpressions();
+
+ T unused(6);
+ T a(2), b(3);
+ T c = a + b;
+ T d = c + a;
+
+ auto tree = StopRecordingExpressions();
+
+ // Recursive dependency check
+ ASSERT_TRUE(tree.DependsOn(d.id, c.id));
+ ASSERT_TRUE(tree.DependsOn(d.id, a.id));
+ ASSERT_TRUE(tree.DependsOn(d.id, b.id));
+ ASSERT_FALSE(tree.DependsOn(d.id, unused.id));
+}
+
+} // namespace internal
+} // namespace ceres
diff --git a/internal/ceres/expression_ref.cc b/internal/ceres/expression_ref.cc
new file mode 100644
index 0000000..75a7723
--- /dev/null
+++ b/internal/ceres/expression_ref.cc
@@ -0,0 +1,144 @@
+// Ceres Solver - A fast non-linear least squares minimizer
+// Copyright 2019 Google Inc. All rights reserved.
+// http://code.google.com/p/ceres-solver/
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//
+// * Redistributions of source code must retain the above copyright notice,
+// this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above copyright notice,
+// this list of conditions and the following disclaimer in the documentation
+// and/or other materials provided with the distribution.
+// * Neither the name of Google Inc. nor the names of its contributors may be
+// used to endorse or promote products derived from this software without
+// specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+// POSSIBILITY OF SUCH DAMAGE.
+//
+// Author: darius.rueckert@fau.de (Darius Rueckert)
+
+#include "ceres/internal/expression_ref.h"
+#include "assert.h"
+#include "ceres/internal/expression.h"
+
+namespace ceres {
+namespace internal {
+
+ExpressionRef ExpressionRef::Create(ExpressionId id) {
+ ExpressionRef ref;
+ ref.id = id;
+ return ref;
+}
+
+std::string ExpressionRef::ToString() const { return std::to_string(id); }
+
+ExpressionRef::ExpressionRef(double compile_time_constant) {
+ (*this) = ExpressionRef::Create(
+ Expression::CreateCompileTimeConstant(compile_time_constant));
+}
+
+// Compound operators
+ExpressionRef& ExpressionRef::operator+=(ExpressionRef y) {
+ *this = *this + y;
+ return *this;
+}
+
+ExpressionRef& ExpressionRef::operator-=(ExpressionRef y) {
+ *this = *this - y;
+ return *this;
+}
+
+ExpressionRef& ExpressionRef::operator*=(ExpressionRef y) {
+ *this = *this * y;
+ return *this;
+}
+
+ExpressionRef& ExpressionRef::operator/=(ExpressionRef y) {
+ *this = *this / y;
+ return *this;
+}
+
+// Arith. Operators
+ExpressionRef operator-(ExpressionRef x) {
+ return ExpressionRef::Create(
+ Expression::CreateUnaryArithmetic(ExpressionType::UNARY_MINUS, x.id));
+}
+
+ExpressionRef operator+(ExpressionRef x) {
+ return ExpressionRef::Create(
+ Expression::CreateUnaryArithmetic(ExpressionType::UNARY_PLUS, x.id));
+}
+
+ExpressionRef operator+(ExpressionRef x, ExpressionRef y) {
+ return ExpressionRef::Create(
+ Expression::CreateBinaryArithmetic(ExpressionType::PLUS, x.id, y.id));
+}
+
+ExpressionRef operator-(ExpressionRef x, ExpressionRef y) {
+ return ExpressionRef::Create(
+ Expression::CreateBinaryArithmetic(ExpressionType::MINUS, x.id, y.id));
+}
+
+ExpressionRef operator/(ExpressionRef x, ExpressionRef y) {
+ return ExpressionRef::Create(
+ Expression::CreateBinaryArithmetic(ExpressionType::DIVISION, x.id, y.id));
+}
+
+ExpressionRef operator*(ExpressionRef x, ExpressionRef y) {
+ return ExpressionRef::Create(Expression::CreateBinaryArithmetic(
+ ExpressionType::MULTIPLICATION, x.id, y.id));
+}
+
+// Functions
+ExpressionRef sin(ExpressionRef x) {
+ return ExpressionRef::Create(Expression::CreateFunctionCall("sin", {x.id}));
+}
+
+ExpressionRef Ternary(ComparisonExpressionRef c,
+ ExpressionRef a,
+ ExpressionRef b) {
+ return ExpressionRef::Create(Expression::CreateTernary(c.id, a.id, b.id));
+}
+
+#define CERES_DEFINE_EXPRESSION_COMPARISON_OPERATOR(op) \
+ ComparisonExpressionRef operator op(ExpressionRef a, ExpressionRef b) { \
+ return ComparisonExpressionRef(ExpressionRef::Create( \
+ Expression::CreateBinaryCompare(#op, a.id, b.id))); \
+ }
+
+#define CERES_DEFINE_EXPRESSION_LOGICAL_OPERATOR(op) \
+ ComparisonExpressionRef operator op(ComparisonExpressionRef a, \
+ ComparisonExpressionRef b) { \
+ return ComparisonExpressionRef(ExpressionRef::Create( \
+ Expression::CreateBinaryCompare(#op, a.id, b.id))); \
+ }
+
+CERES_DEFINE_EXPRESSION_COMPARISON_OPERATOR(<)
+CERES_DEFINE_EXPRESSION_COMPARISON_OPERATOR(<=)
+CERES_DEFINE_EXPRESSION_COMPARISON_OPERATOR(>)
+CERES_DEFINE_EXPRESSION_COMPARISON_OPERATOR(>=)
+CERES_DEFINE_EXPRESSION_COMPARISON_OPERATOR(==)
+CERES_DEFINE_EXPRESSION_COMPARISON_OPERATOR(!=)
+CERES_DEFINE_EXPRESSION_LOGICAL_OPERATOR(&&)
+CERES_DEFINE_EXPRESSION_LOGICAL_OPERATOR(||)
+#undef CERES_DEFINE_EXPRESSION_COMPARISON_OPERATOR
+#undef CERES_DEFINE_EXPRESSION_LOGICAL_OPERATOR
+
+ComparisonExpressionRef operator!(ComparisonExpressionRef a) {
+ return ComparisonExpressionRef(
+ ExpressionRef::Create(Expression::CreateLogicalNegation(a.id)));
+}
+
+} // namespace internal
+} // namespace ceres
diff --git a/internal/ceres/expression_test.cc b/internal/ceres/expression_test.cc
new file mode 100644
index 0000000..3e683c1
--- /dev/null
+++ b/internal/ceres/expression_test.cc
@@ -0,0 +1,119 @@
+// Ceres Solver - A fast non-linear least squares minimizer
+// Copyright 2019 Google Inc. All rights reserved.
+// http://code.google.com/p/ceres-solver/
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//
+// * Redistributions of source code must retain the above copyright notice,
+// this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above copyright notice,
+// this list of conditions and the following disclaimer in the documentation
+// and/or other materials provided with the distribution.
+// * Neither the name of Google Inc. nor the names of its contributors may be
+// used to endorse or promote products derived from this software without
+// specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+// POSSIBILITY OF SUCH DAMAGE.
+//
+// Author: darius.rueckert@fau.de (Darius Rueckert)
+//
+
+#include "ceres/internal/expression_graph.h"
+#include "ceres/internal/expression_ref.h"
+
+#include "gtest/gtest.h"
+
+namespace ceres {
+namespace internal {
+
+TEST(Expression, IsArithmetic) {
+ using T = ExpressionRef;
+
+ StartRecordingExpressions();
+
+ T a(2), b(3);
+ T c = a + b;
+ T d = c + a;
+
+ auto graph = StopRecordingExpressions();
+
+ ASSERT_FALSE(graph.ExpressionForId(a.id).IsArithmetic());
+ ASSERT_FALSE(graph.ExpressionForId(b.id).IsArithmetic());
+ ASSERT_TRUE(graph.ExpressionForId(c.id).IsArithmetic());
+ ASSERT_TRUE(graph.ExpressionForId(d.id).IsArithmetic());
+}
+
+TEST(Expression, IsCompileTimeConstantAndEqualTo) {
+ using T = ExpressionRef;
+
+ StartRecordingExpressions();
+
+ T a(2), b(3);
+ T c = a + b;
+
+ auto graph = StopRecordingExpressions();
+
+ ASSERT_TRUE(graph.ExpressionForId(a.id).IsCompileTimeConstantAndEqualTo(2));
+ ASSERT_FALSE(graph.ExpressionForId(a.id).IsCompileTimeConstantAndEqualTo(0));
+ ASSERT_TRUE(graph.ExpressionForId(b.id).IsCompileTimeConstantAndEqualTo(3));
+ ASSERT_FALSE(graph.ExpressionForId(c.id).IsCompileTimeConstantAndEqualTo(0));
+}
+
+TEST(Expression, IsReplaceableBy) {
+ using T = ExpressionRef;
+
+ StartRecordingExpressions();
+
+ // a2 should be replaceable by a
+ T a(2), b(3), a2(2);
+
+ // two redundant expressions
+ // -> d should be replaceable by c
+ T c = a + b;
+ T d = a + b;
+
+ auto graph = StopRecordingExpressions();
+
+ ASSERT_TRUE(graph.ExpressionForId(a2.id).IsReplaceableBy(
+ graph.ExpressionForId(a.id)));
+ ASSERT_TRUE(
+ graph.ExpressionForId(d.id).IsReplaceableBy(graph.ExpressionForId(c.id)));
+ ASSERT_FALSE(graph.ExpressionForId(d.id).IsReplaceableBy(
+ graph.ExpressionForId(a2.id)));
+}
+
+TEST(Expression, DirectlyDependsOn) {
+ using T = ExpressionRef;
+
+ StartRecordingExpressions();
+
+ T unused(6);
+ T a(2), b(3);
+ T c = a + b;
+ T d = c + a;
+
+ auto graph = StopRecordingExpressions();
+
+ ASSERT_FALSE(graph.ExpressionForId(a.id).DirectlyDependsOn(unused.id));
+ ASSERT_TRUE(graph.ExpressionForId(c.id).DirectlyDependsOn(a.id));
+ ASSERT_TRUE(graph.ExpressionForId(c.id).DirectlyDependsOn(b.id));
+ ASSERT_TRUE(graph.ExpressionForId(d.id).DirectlyDependsOn(a.id));
+ ASSERT_FALSE(graph.ExpressionForId(d.id).DirectlyDependsOn(b.id));
+ ASSERT_TRUE(graph.ExpressionForId(d.id).DirectlyDependsOn(c.id));
+}
+
+// Todo: remaining functions of Expression
+
+} // namespace internal
+} // namespace ceres
