Rework Expression creation and insertion
Objects of 'Expression' can now be freely created and copied around.
This creation does NOT add them to the active ExpressionGraph any
more. The insertion into the graph is now done by ExpressionRef,
which explicitly call graph.add(...) in each operation.
This change brings the following advantages:
1. 'Expression' is now stand-alone and side-effect free
- Remove the dependency Expression->ExpressionGraph
- Expressions can be created by the optimizer
2. Explicit graph insertion
- Previously CreateCompileTimeConstant not only created an
expression, but also inserted it into the active graph. Now
this insertion is done explicitly by ExpressionRef
3. It is now easier to insert new types and members
- Should be straight forward now, because we got rid of the
3-way dependency
- This is a preparation patch for the new return-type member in
https://ceres-solver-review.googlesource.com/c/ceres-solver/+/16224
Change-Id: Icef2fe529a4db001a10d1fb6816c9dc681b14ff2
diff --git a/include/ceres/codegen/internal/expression.h b/include/ceres/codegen/internal/expression.h
index bf07a21..7d93a4d 100644
--- a/include/ceres/codegen/internal/expression.h
+++ b/include/ceres/codegen/internal/expression.h
@@ -249,31 +249,37 @@
// 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 CreateInputAssignment(const std::string& name);
- static ExpressionId CreateOutputAssignment(ExpressionId v,
- const std::string& name);
- static ExpressionId CreateAssignment(ExpressionId dst, ExpressionId src);
- static ExpressionId CreateBinaryArithmetic(const std::string& op,
- ExpressionId l,
- ExpressionId r);
- static ExpressionId CreateUnaryArithmetic(const std::string& op,
- 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);
+ Expression() = default;
- // Conditional control expressions are inserted into the graph but can't be
- // referenced by other expressions. Therefore they don't return an
- // ExpressionId.
- static void CreateIf(ExpressionId condition);
- static void CreateElse();
- static void CreateEndIf();
+ Expression(ExpressionType type,
+ ExpressionId lhs_id = kInvalidExpressionId,
+ const std::vector<ExpressionId>& arguments = {},
+ const std::string& name = "",
+ double value = 0);
+
+ // Helper 'constructors' that create an Expression with the correct type. You
+ // can also use the actual constructor from above, but using the create
+ // functions is less prone to errors.
+ static Expression CreateCompileTimeConstant(double v);
+
+ static Expression CreateInputAssignment(const std::string& name);
+ static Expression CreateOutputAssignment(ExpressionId v,
+ const std::string& name);
+ static Expression CreateAssignment(ExpressionId dst, ExpressionId src);
+ static Expression CreateBinaryArithmetic(const std::string& op,
+ ExpressionId l,
+ ExpressionId r);
+ static Expression CreateUnaryArithmetic(const std::string& op,
+ ExpressionId v);
+ static Expression CreateBinaryCompare(const std::string& name,
+ ExpressionId l,
+ ExpressionId r);
+ static Expression CreateLogicalNegation(ExpressionId v);
+ static Expression CreateFunctionCall(const std::string& name,
+ const std::vector<ExpressionId>& params);
+ static Expression CreateIf(ExpressionId condition);
+ static Expression CreateElse();
+ static Expression CreateEndIf();
// Returns true if this is an arithmetic expression.
// Arithmetic expressions must have a valid left hand side.
@@ -309,6 +315,7 @@
// Compares all members with the == operator. If this function succeeds,
// IsSemanticallyEquivalentTo will also return true.
bool operator==(const Expression& other) const;
+ bool operator!=(const Expression& other) const { return !(*this == other); }
// Semantically equivalent expressions are similar in a way, that the type(),
// value(), name(), number of arguments is identical. The lhs_id() and the
@@ -329,14 +336,10 @@
const std::string& name() const { return name_; }
const std::vector<ExpressionId>& arguments() const { return arguments_; }
+ void set_lhs_id(ExpressionId new_lhs_id) { lhs_id_ = new_lhs_id; }
+ std::vector<ExpressionId>* mutable_arguments() { return &arguments_; }
+
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 lhs_id);
-
ExpressionType type_ = ExpressionType::NOP;
// If lhs_id_ >= 0, then this expression is assigned to v_<lhs_id>.
diff --git a/include/ceres/codegen/internal/expression_graph.h b/include/ceres/codegen/internal/expression_graph.h
index 22fbba6..30b5a78 100644
--- a/include/ceres/codegen/internal/expression_graph.h
+++ b/include/ceres/codegen/internal/expression_graph.h
@@ -48,26 +48,6 @@
// A is parent of B <=> A has B as a parameter <=> A.DirectlyDependsOn(B)
class ExpressionGraph {
public:
- // Creates an arithmetic expression of the following form:
- // <lhs> = <rhs>;
- //
- // For example:
- // CreateArithmeticExpression(PLUS, 5)
- // will generate:
- // v_5 = __ + __;
- // The place holders are then set by the CreateXX functions of Expression.
- //
- // If lhs_id == kInvalidExpressionId, then a new lhs_id will be generated and
- // assigned to the created expression.
- // Calling this function with a lhs_id that doesn't exist results in an
- // error.
- Expression& CreateArithmeticExpression(ExpressionType type,
- ExpressionId lhs_id);
-
- // Control expression don't have a left hand side.
- // Supported types: IF/ELSE/ENDIF/NOP
- Expression& CreateControlExpression(ExpressionType type);
-
// Checks if A depends on B.
// -> B is a descendant of A
bool DependsOn(ExpressionId A, ExpressionId B) const;
@@ -82,33 +62,34 @@
int Size() const { return expressions_.size(); }
// Insert a new expression at "location" into the graph. All expression
- // after "location" are moved by one element to the back. References to moved
- // expression are updated.
- void InsertExpression(ExpressionId location,
- ExpressionType type,
- ExpressionId lhs_id,
- const std::vector<ExpressionId>& arguments,
- const std::string& name,
- double value);
+ // after "location" are moved by one element to the back. References to
+ // moved expressions are updated.
+ void Insert(ExpressionId location, const Expression& expression);
+
+ // Adds an Expression to the end of the expression list and creates a new
+ // variable for the result. The id of the result variable is returned so it
+ // can be used for further operations.
+ ExpressionId InsertBack(const Expression& expression);
private:
- // All Expressions are referenced by an ExpressionId. The ExpressionId is the
- // index into this array. Each expression has a list of ExpressionId as
+ // 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
+// 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.
+// 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.
+// 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.
diff --git a/include/ceres/codegen/internal/expression_ref.h b/include/ceres/codegen/internal/expression_ref.h
index c26a4ab..c888739 100644
--- a/include/ceres/codegen/internal/expression_ref.h
+++ b/include/ceres/codegen/internal/expression_ref.h
@@ -33,9 +33,8 @@
#define CERES_PUBLIC_EXPRESSION_REF_H_
#include <string>
-#include "ceres/codegen/internal/types.h"
#include "ceres/codegen/internal/expression.h"
-
+#include "ceres/codegen/internal/types.h"
namespace ceres {
namespace internal {
@@ -117,6 +116,11 @@
static ExpressionRef Create(ExpressionId id);
};
+// A helper function which calls 'InsertBack' on the currently active graph.
+// This wrapper also checks if StartRecordingExpressions was called. See
+// ExpressionGraph::InsertBack for more information.
+ExpressionRef AddExpressionToGraph(const Expression& expression);
+
// Arithmetic Operators
ExpressionRef operator-(const ExpressionRef& x);
ExpressionRef operator+(const ExpressionRef& x);
@@ -128,12 +132,12 @@
// Functions
#define CERES_DEFINE_UNARY_FUNCTION_CALL(name) \
inline ExpressionRef name(const ExpressionRef& x) { \
- return ExpressionRef::Create( \
+ return AddExpressionToGraph( \
Expression::CreateFunctionCall(#name, {x.id})); \
}
#define CERES_DEFINE_BINARY_FUNCTION_CALL(name) \
inline ExpressionRef name(const ExpressionRef& x, const ExpressionRef& y) { \
- return ExpressionRef::Create( \
+ return AddExpressionToGraph( \
Expression::CreateFunctionCall(#name, {x.id, y.id})); \
}
CERES_DEFINE_UNARY_FUNCTION_CALL(abs);
@@ -211,7 +215,7 @@
static inline ReturnType Get(double /* unused */, const char* name) {
// Note: The scalar value of v will be thrown away, because we don't need it
// during code generation.
- return ExpressionRef::Create(Expression::CreateInputAssignment(name));
+ return AddExpressionToGraph(Expression::CreateInputAssignment(name));
}
};
@@ -222,11 +226,11 @@
}
inline ExpressionRef MakeParameter(const std::string& name) {
- return ExpressionRef::Create(Expression::CreateInputAssignment(name));
+ return AddExpressionToGraph(Expression::CreateInputAssignment(name));
}
inline ExpressionRef MakeOutput(const ExpressionRef& v,
const std::string& name) {
- return ExpressionRef::Create(Expression::CreateOutputAssignment(v.id, name));
+ return AddExpressionToGraph(Expression::CreateOutputAssignment(v.id, name));
}
} // namespace internal
diff --git a/include/ceres/codegen/macros.h b/include/ceres/codegen/macros.h
index 9750075..0efc9e2 100644
--- a/include/ceres/codegen/macros.h
+++ b/include/ceres/codegen/macros.h
@@ -109,9 +109,11 @@
ceres::internal::InputAssignment<_template_type>::Get(_local_variable, \
#_local_variable)
#define CERES_IF(condition_) \
- ceres::internal::Expression::CreateIf((condition_).id);
-#define CERES_ELSE ceres::internal::Expression::CreateElse();
-#define CERES_ENDIF ceres::internal::Expression::CreateEndIf();
+ AddExpressionToGraph(ceres::internal::Expression::CreateIf((condition_).id));
+#define CERES_ELSE \
+ AddExpressionToGraph(ceres::internal::Expression::CreateElse());
+#define CERES_ENDIF \
+ AddExpressionToGraph(ceres::internal::Expression::CreateEndIf());
#endif
#endif // CERES_PUBLIC_CODEGEN_MACROS_H_
diff --git a/internal/ceres/conditional_expressions_test.cc b/internal/ceres/conditional_expressions_test.cc
index 3fcb7a3..9c499ea 100644
--- a/internal/ceres/conditional_expressions_test.cc
+++ b/internal/ceres/conditional_expressions_test.cc
@@ -63,12 +63,12 @@
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, {} , "", 3);
- reference.InsertExpression( 2, ExpressionType::BINARY_COMPARISON, 2, {0, 1} , "<", 0);
- reference.InsertExpression( 3, ExpressionType::IF, -1, {2} , "", 0);
- reference.InsertExpression( 4, ExpressionType::ELSE, -1, {} , "", 0);
- reference.InsertExpression( 5, ExpressionType::ENDIF, -1, {} , "", 0);
+ reference.InsertBack({ExpressionType::COMPILE_TIME_CONSTANT, 0, {} , "", 2});
+ reference.InsertBack({ExpressionType::COMPILE_TIME_CONSTANT, 1, {} , "", 3});
+ reference.InsertBack({ ExpressionType::BINARY_COMPARISON, 2, {0, 1} , "<", 0});
+ reference.InsertBack({ ExpressionType::IF, -1, {2} , "", 0});
+ reference.InsertBack({ ExpressionType::ELSE, -1, {} , "", 0});
+ reference.InsertBack({ ExpressionType::ENDIF, -1, {} , "", 0});
// clang-format on
EXPECT_EQ(reference, graph);
}
@@ -104,17 +104,17 @@
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, {} , "", 3);
- reference.InsertExpression( 2, ExpressionType::BINARY_COMPARISON, 2, {0, 1}, "<", 0);
- reference.InsertExpression( 3, ExpressionType::IF, -1, {2} , "", 0);
- reference.InsertExpression( 4, ExpressionType::BINARY_ARITHMETIC, 4, {0, 1}, "+", 0);
- reference.InsertExpression( 5, ExpressionType::ELSE, -1, {} , "", 0);
- reference.InsertExpression( 6, ExpressionType::BINARY_ARITHMETIC, 6, {0, 1}, "-", 0);
- reference.InsertExpression( 7, ExpressionType::ASSIGNMENT, 4, {6} , "", 0);
- reference.InsertExpression( 8, ExpressionType::ENDIF, -1, {} , "", 0);
- reference.InsertExpression( 9, ExpressionType::BINARY_ARITHMETIC, 9, {4, 0}, "+", 0);
- reference.InsertExpression( 10, ExpressionType::ASSIGNMENT, 4, {9} , "", 0);
+ reference.InsertBack({ExpressionType::COMPILE_TIME_CONSTANT, 0, {} , "", 2});
+ reference.InsertBack({ExpressionType::COMPILE_TIME_CONSTANT, 1, {} , "", 3});
+ reference.InsertBack({ ExpressionType::BINARY_COMPARISON, 2, {0, 1}, "<", 0});
+ reference.InsertBack({ ExpressionType::IF, -1, {2} , "", 0});
+ reference.InsertBack({ ExpressionType::BINARY_ARITHMETIC, 4, {0, 1}, "+", 0});
+ reference.InsertBack({ ExpressionType::ELSE, -1, {} , "", 0});
+ reference.InsertBack({ ExpressionType::BINARY_ARITHMETIC, 6, {0, 1}, "-", 0});
+ reference.InsertBack({ ExpressionType::ASSIGNMENT, 4, {6} , "", 0});
+ reference.InsertBack({ ExpressionType::ENDIF, -1, {} , "", 0});
+ reference.InsertBack({ ExpressionType::BINARY_ARITHMETIC, 9, {4, 0}, "+", 0});
+ reference.InsertBack({ ExpressionType::ASSIGNMENT, 4, {9} , "", 0});
// clang-format on
EXPECT_EQ(reference, graph);
diff --git a/internal/ceres/expression.cc b/internal/ceres/expression.cc
index b2471e7..ca92eaf 100644
--- a/internal/ceres/expression.cc
+++ b/internal/ceres/expression.cc
@@ -30,116 +30,90 @@
#include "ceres/codegen/internal/expression.h"
#include <algorithm>
-#include "ceres/codegen/internal/expression_graph.h"
-#include "glog/logging.h"
namespace ceres {
namespace internal {
-// Wrapper for ExpressionGraph::CreateArithmeticExpression, which checks if a
-// graph is currently active. See that function for an explanation.
-static Expression& MakeArithmeticExpression(
- ExpressionType type, ExpressionId lhs_id = kInvalidExpressionId) {
- auto pool = GetCurrentExpressionGraph();
- CHECK(pool)
- << "The ExpressionGraph has to be created before using Expressions. This "
- "is achieved by calling ceres::StartRecordingExpressions.";
- return pool->CreateArithmeticExpression(type, lhs_id);
+Expression::Expression(ExpressionType type,
+ ExpressionId lhs_id,
+ const std::vector<ExpressionId>& arguments,
+ const std::string& name,
+ double value)
+ : type_(type),
+ lhs_id_(lhs_id),
+ arguments_(arguments),
+ name_(name),
+ value_(value) {}
+
+Expression Expression::CreateCompileTimeConstant(double v) {
+ return Expression(
+ ExpressionType::COMPILE_TIME_CONSTANT, kInvalidExpressionId, {}, "", v);
}
-// Wrapper for ExpressionGraph::CreateControlExpression.
-static Expression& MakeControlExpression(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->CreateControlExpression(type);
+Expression Expression::CreateInputAssignment(const std::string& name) {
+ return Expression(
+ ExpressionType::INPUT_ASSIGNMENT, kInvalidExpressionId, {}, name);
}
-ExpressionId Expression::CreateCompileTimeConstant(double v) {
- auto& expr = MakeArithmeticExpression(ExpressionType::COMPILE_TIME_CONSTANT);
- expr.value_ = v;
- return expr.lhs_id_;
+Expression Expression::CreateOutputAssignment(ExpressionId v,
+ const std::string& name) {
+ return Expression(
+ ExpressionType::OUTPUT_ASSIGNMENT, kInvalidExpressionId, {v}, name);
}
-ExpressionId Expression::CreateInputAssignment(const std::string& name) {
- auto& expr = MakeArithmeticExpression(ExpressionType::INPUT_ASSIGNMENT);
- expr.name_ = name;
- return expr.lhs_id_;
+Expression Expression::CreateAssignment(ExpressionId dst, ExpressionId src) {
+ return Expression(ExpressionType::ASSIGNMENT, dst, {src});
}
-ExpressionId Expression::CreateOutputAssignment(ExpressionId v,
- const std::string& name) {
- auto& expr = MakeArithmeticExpression(ExpressionType::OUTPUT_ASSIGNMENT);
- expr.arguments_.push_back(v);
- expr.name_ = name;
- return expr.lhs_id_;
+Expression Expression::CreateBinaryArithmetic(const std::string& op,
+ ExpressionId l,
+ ExpressionId r) {
+ return Expression(
+ ExpressionType::BINARY_ARITHMETIC, kInvalidExpressionId, {l, r}, op);
}
-ExpressionId Expression::CreateAssignment(ExpressionId dst, ExpressionId src) {
- auto& expr = MakeArithmeticExpression(ExpressionType::ASSIGNMENT, dst);
-
- expr.arguments_.push_back(src);
- return expr.lhs_id_;
+Expression Expression::CreateUnaryArithmetic(const std::string& op,
+ ExpressionId v) {
+ return Expression(
+ ExpressionType::UNARY_ARITHMETIC, kInvalidExpressionId, {v}, op);
}
-ExpressionId Expression::CreateBinaryArithmetic(const std::string& op,
- ExpressionId l,
- ExpressionId r) {
- auto& expr = MakeArithmeticExpression(ExpressionType::BINARY_ARITHMETIC);
- expr.name_ = op;
- expr.arguments_.push_back(l);
- expr.arguments_.push_back(r);
- return expr.lhs_id_;
+Expression Expression::CreateBinaryCompare(const std::string& name,
+ ExpressionId l,
+ ExpressionId r) {
+ return Expression(
+ ExpressionType::BINARY_COMPARISON, kInvalidExpressionId, {l, r}, name);
}
-ExpressionId Expression::CreateUnaryArithmetic(const std::string& op,
- ExpressionId v) {
- auto& expr = MakeArithmeticExpression(ExpressionType::UNARY_ARITHMETIC);
- expr.name_ = op;
- expr.arguments_.push_back(v);
- return expr.lhs_id_;
+Expression Expression::CreateLogicalNegation(ExpressionId v) {
+ return Expression(
+ ExpressionType::LOGICAL_NEGATION, kInvalidExpressionId, {v});
}
-ExpressionId Expression::CreateBinaryCompare(const std::string& name,
- ExpressionId l,
- ExpressionId r) {
- auto& expr = MakeArithmeticExpression(ExpressionType::BINARY_COMPARISON);
- expr.arguments_.push_back(l);
- expr.arguments_.push_back(r);
- expr.name_ = name;
- return expr.lhs_id_;
-}
-
-ExpressionId Expression::CreateLogicalNegation(ExpressionId v) {
- auto& expr = MakeArithmeticExpression(ExpressionType::LOGICAL_NEGATION);
- expr.arguments_.push_back(v);
- return expr.lhs_id_;
-}
-
-ExpressionId Expression::CreateFunctionCall(
+Expression Expression::CreateFunctionCall(
const std::string& name, const std::vector<ExpressionId>& params) {
- auto& expr = MakeArithmeticExpression(ExpressionType::FUNCTION_CALL);
- expr.arguments_ = params;
- expr.name_ = name;
- return expr.lhs_id_;
+ return Expression(
+ ExpressionType::FUNCTION_CALL, kInvalidExpressionId, params, name);
}
-void Expression::CreateIf(ExpressionId condition) {
- auto& expr = MakeControlExpression(ExpressionType::IF);
- expr.arguments_.push_back(condition);
+Expression Expression::CreateIf(ExpressionId condition) {
+ return Expression(ExpressionType::IF, kInvalidExpressionId, {condition});
}
-void Expression::CreateElse() { MakeControlExpression(ExpressionType::ELSE); }
+Expression Expression::CreateElse() { return Expression(ExpressionType::ELSE); }
-void Expression::CreateEndIf() { MakeControlExpression(ExpressionType::ENDIF); }
+Expression Expression::CreateEndIf() {
+ return Expression(ExpressionType::ENDIF);
+}
-Expression::Expression(ExpressionType type, ExpressionId id)
- : type_(type), lhs_id_(id) {}
+bool Expression::IsArithmeticExpression() const {
+ return !IsControlExpression();
+}
-bool Expression::IsArithmeticExpression() const { return HasValidLhs(); }
-
-bool Expression::IsControlExpression() const { return !HasValidLhs(); }
+bool Expression::IsControlExpression() const {
+ return type_ == ExpressionType::IF || type_ == ExpressionType::ELSE ||
+ type_ == ExpressionType::ENDIF || type_ == ExpressionType::NOP;
+}
bool Expression::IsReplaceableBy(const Expression& other) const {
// Check everything except the id.
diff --git a/internal/ceres/expression_graph.cc b/internal/ceres/expression_graph.cc
index 6d02c1c..c0761af 100644
--- a/internal/ceres/expression_graph.cc
+++ b/internal/ceres/expression_graph.cc
@@ -55,27 +55,6 @@
ExpressionGraph* GetCurrentExpressionGraph() { return expression_pool; }
-Expression& ExpressionGraph::CreateArithmeticExpression(ExpressionType type,
- ExpressionId lhs_id) {
- if (lhs_id == kInvalidExpressionId) {
- // We are creating a new temporary variable.
- // -> The new lhs_id is the index into the graph
- lhs_id = static_cast<ExpressionId>(expressions_.size());
- } else {
- // The left hand side already exists.
- }
-
- Expression expr(type, lhs_id);
- expressions_.push_back(expr);
- return expressions_.back();
-}
-
-Expression& ExpressionGraph::CreateControlExpression(ExpressionType type) {
- Expression expr(type, kInvalidExpressionId);
- 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:
@@ -83,7 +62,7 @@
// for (auto p : A.params_) {
// if (pool[p.id].DependsOn(B, pool)) return true;
// }
- std::vector<ExpressionId> stack = ExpressionForId(A).arguments_;
+ std::vector<ExpressionId> stack = ExpressionForId(A).arguments();
while (!stack.empty()) {
auto top = stack.back();
stack.pop_back();
@@ -91,7 +70,7 @@
return true;
}
auto& expr = ExpressionForId(top);
- stack.insert(stack.end(), expr.arguments_.begin(), expr.arguments_.end());
+ stack.insert(stack.end(), expr.arguments().begin(), expr.arguments().end());
}
return false;
}
@@ -108,13 +87,8 @@
return true;
}
-void ExpressionGraph::InsertExpression(
- ExpressionId location,
- ExpressionType type,
- ExpressionId lhs_id,
- const std::vector<ExpressionId>& arguments,
- const std::string& name,
- double value) {
+void ExpressionGraph::Insert(ExpressionId location,
+ const Expression& expression) {
ExpressionId last_expression_id = Size() - 1;
// Increase size by adding a dummy expression.
expressions_.push_back(Expression(ExpressionType::NOP, kInvalidExpressionId));
@@ -123,10 +97,10 @@
for (ExpressionId id = last_expression_id; id >= location; --id) {
auto& expression = expressions_[id];
// Increment reference if it points to a shifted variable.
- if (expression.lhs_id_ >= location) {
- expression.lhs_id_++;
+ if (expression.lhs_id() >= location) {
+ expression.set_lhs_id(expression.lhs_id() + 1);
}
- for (auto& arg : expression.arguments_) {
+ for (auto& arg : *expression.mutable_arguments()) {
if (arg >= location) {
arg++;
}
@@ -135,11 +109,33 @@
}
// Insert new expression at the correct place
- Expression expr(type, lhs_id);
- expr.arguments_ = arguments;
- expr.name_ = name;
- expr.value_ = value;
- expressions_[location] = expr;
+ expressions_[location] = expression;
+}
+
+ExpressionId ExpressionGraph::InsertBack(const Expression& expression) {
+ if (expression.IsControlExpression()) {
+ // Control expression are just added to the list. We do not return a
+ // reference to them.
+ CHECK(expression.lhs_id() == kInvalidExpressionId)
+ << "Control expressions must have an invalid lhs.";
+ expressions_.push_back(expression);
+ return kInvalidExpressionId;
+ }
+
+ if (expression.lhs_id() == kInvalidExpressionId) {
+ // Create a new variable name for this expression and set it as the lhs
+ Expression copy = expression;
+ copy.set_lhs_id(static_cast<ExpressionId>(expressions_.size()));
+ expressions_.push_back(copy);
+ } else {
+ // The expressions writes to a variable declared in the past
+ // -> Just add it to the list
+ CHECK_LE(expression.lhs_id(), expressions_.size())
+ << "The left hand side must reference a variable in the past.";
+ expressions_.push_back(expression);
+ }
+
+ return Size() - 1;
}
} // namespace internal
diff --git a/internal/ceres/expression_graph_test.cc b/internal/ceres/expression_graph_test.cc
index 23e68ee..65b019c 100644
--- a/internal/ceres/expression_graph_test.cc
+++ b/internal/ceres/expression_graph_test.cc
@@ -95,8 +95,7 @@
EXPECT_EQ(c_expr.arguments()[1], 1);
// We insert at the beginning, which shifts everything by one spot.
- graph.InsertExpression(
- 0, ExpressionType::COMPILE_TIME_CONSTANT, 0, {}, "", 10.2);
+ graph.Insert(0, {ExpressionType::COMPILE_TIME_CONSTANT, 0, {}, "", 10.2});
// Test if 'a' and 'c' are actually at location 1 and 3
auto& a_expr2 = graph.ExpressionForId(1);
@@ -147,9 +146,9 @@
// We manually insert the 3 missing expressions
// clang-format off
- graph1.InsertExpression(2, ExpressionType::COMPILE_TIME_CONSTANT, 2, {}, "", 5);
- graph1.InsertExpression(3, ExpressionType::BINARY_ARITHMETIC, 3, {0, 2}, "+", 0);
- graph1.InsertExpression(4, ExpressionType::ASSIGNMENT, 0, {3}, "", 0);
+ graph1.Insert(2,{ ExpressionType::COMPILE_TIME_CONSTANT, 2, {}, "", 5});
+ graph1.Insert(3,{ ExpressionType::BINARY_ARITHMETIC, 3, {0, 2}, "+", 0});
+ graph1.Insert(4,{ ExpressionType::ASSIGNMENT, 0, {3}, "", 0});
// clang-format on
// Now the graphs are identical!
diff --git a/internal/ceres/expression_ref.cc b/internal/ceres/expression_ref.cc
index bb8f920..2738b08 100644
--- a/internal/ceres/expression_ref.cc
+++ b/internal/ceres/expression_ref.cc
@@ -29,11 +29,21 @@
// Author: darius.rueckert@fau.de (Darius Rueckert)
#include "ceres/codegen/internal/expression_ref.h"
+
+#include "ceres/codegen/internal/expression_graph.h"
#include "glog/logging.h"
namespace ceres {
namespace internal {
+ExpressionRef AddExpressionToGraph(const Expression& expression) {
+ ExpressionGraph* graph = GetCurrentExpressionGraph();
+ CHECK(graph)
+ << "The ExpressionGraph has to be created before using Expressions. This "
+ "is achieved by calling ceres::StartRecordingExpressions.";
+ return ExpressionRef::Create(graph->InsertBack(expression));
+}
+
ExpressionRef ExpressionRef::Create(ExpressionId id) {
ExpressionRef ref;
ref.id = id;
@@ -41,7 +51,9 @@
}
ExpressionRef::ExpressionRef(double compile_time_constant) {
- id = Expression::CreateCompileTimeConstant(compile_time_constant);
+ id = AddExpressionToGraph(
+ Expression::CreateCompileTimeConstant(compile_time_constant))
+ .id;
}
ExpressionRef::ExpressionRef(const ExpressionRef& other) { *this = other; }
@@ -51,13 +63,15 @@
CHECK(other.IsInitialized()) << "Uninitialized Assignment.";
if (IsInitialized()) {
// Create assignment from other -> this
- Expression::CreateAssignment(this->id, other.id);
+ AddExpressionToGraph(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);
+ // Passing kInvalidExpressionId to CreateAssignment generates a new
+ // variable name which we store in the id.
+ id = AddExpressionToGraph(
+ Expression::CreateAssignment(kInvalidExpressionId, other.id))
+ .id;
}
return *this;
}
@@ -72,22 +86,23 @@
if (IsInitialized()) {
// Create assignment from other -> this
- Expression::CreateAssignment(id, other.id);
+ AddExpressionToGraph(Expression::CreateAssignment(id, other.id));
} else {
// 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:
+ // 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:
+ // 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;
@@ -119,51 +134,51 @@
// Arith. Operators
ExpressionRef operator-(const ExpressionRef& x) {
- return ExpressionRef::Create(Expression::CreateUnaryArithmetic("-", x.id));
+ return AddExpressionToGraph(Expression::CreateUnaryArithmetic("-", x.id));
}
ExpressionRef operator+(const ExpressionRef& x) {
- return ExpressionRef::Create(Expression::CreateUnaryArithmetic("+", x.id));
+ return AddExpressionToGraph(Expression::CreateUnaryArithmetic("+", x.id));
}
ExpressionRef operator+(const ExpressionRef& x, const ExpressionRef& y) {
- return ExpressionRef::Create(
+ return AddExpressionToGraph(
Expression::CreateBinaryArithmetic("+", x.id, y.id));
}
ExpressionRef operator-(const ExpressionRef& x, const ExpressionRef& y) {
- return ExpressionRef::Create(
+ return AddExpressionToGraph(
Expression::CreateBinaryArithmetic("-", x.id, y.id));
}
ExpressionRef operator/(const ExpressionRef& x, const ExpressionRef& y) {
- return ExpressionRef::Create(
+ return AddExpressionToGraph(
Expression::CreateBinaryArithmetic("/", x.id, y.id));
}
ExpressionRef operator*(const ExpressionRef& x, const ExpressionRef& y) {
- return ExpressionRef::Create(
+ return AddExpressionToGraph(
Expression::CreateBinaryArithmetic("*", x.id, y.id));
}
ExpressionRef Ternary(const ComparisonExpressionRef& c,
const ExpressionRef& x,
const ExpressionRef& y) {
- return ExpressionRef::Create(
+ return AddExpressionToGraph(
Expression::CreateFunctionCall("Ternary", {c.id, x.id, y.id}));
}
#define CERES_DEFINE_EXPRESSION_COMPARISON_OPERATOR(op) \
ComparisonExpressionRef operator op(const ExpressionRef& x, \
const ExpressionRef& y) { \
- return ComparisonExpressionRef(ExpressionRef::Create( \
+ return ComparisonExpressionRef(AddExpressionToGraph( \
Expression::CreateBinaryCompare(#op, x.id, y.id))); \
}
#define CERES_DEFINE_EXPRESSION_LOGICAL_OPERATOR(op) \
ComparisonExpressionRef operator op(const ComparisonExpressionRef& x, \
const ComparisonExpressionRef& y) { \
- return ComparisonExpressionRef(ExpressionRef::Create( \
+ return ComparisonExpressionRef(AddExpressionToGraph( \
Expression::CreateBinaryCompare(#op, x.id, y.id))); \
}
@@ -180,7 +195,7 @@
ComparisonExpressionRef operator!(const ComparisonExpressionRef& x) {
return ComparisonExpressionRef(
- ExpressionRef::Create(Expression::CreateLogicalNegation(x.id)));
+ AddExpressionToGraph(Expression::CreateLogicalNegation(x.id)));
}
} // namespace internal
diff --git a/internal/ceres/expression_test.cc b/internal/ceres/expression_test.cc
index 25fd7f6..cab196b 100644
--- a/internal/ceres/expression_test.cc
+++ b/internal/ceres/expression_test.cc
@@ -28,7 +28,6 @@
//
// Author: darius.rueckert@fau.de (Darius Rueckert)
//
-
#define CERES_CODEGEN
#include "ceres/codegen/internal/expression_graph.h"
@@ -39,60 +38,134 @@
namespace ceres {
namespace internal {
-TEST(Expression, IsArithmetic) {
- using T = ExpressionRef;
+TEST(Expression, ConstructorAndAccessors) {
+ Expression expr(ExpressionType::LOGICAL_NEGATION,
+ 12345,
+ {1, 5, 8, 10},
+ "TestConstructor",
+ 57.25);
+ EXPECT_EQ(expr.type(), ExpressionType::LOGICAL_NEGATION);
+ EXPECT_EQ(expr.lhs_id(), 12345);
+ EXPECT_EQ(expr.arguments(), std::vector<ExpressionId>({1, 5, 8, 10}));
+ EXPECT_EQ(expr.name(), "TestConstructor");
+ EXPECT_EQ(expr.value(), 57.25);
+}
- StartRecordingExpressions();
+TEST(Expression, CreateFunctions) {
+ // clang-format off
+ // The default constructor creates a NOP!
+ EXPECT_EQ(Expression(), Expression(
+ ExpressionType::NOP, kInvalidExpressionId, {}, "", 0));
- T a(2), b(3);
- T c = a + b;
- T d = c + a;
+ EXPECT_EQ(Expression::CreateCompileTimeConstant(72), Expression(
+ ExpressionType::COMPILE_TIME_CONSTANT, kInvalidExpressionId, {}, "", 72));
- auto graph = StopRecordingExpressions();
+ EXPECT_EQ(Expression::CreateInputAssignment("arguments[0][0]"), Expression(
+ ExpressionType::INPUT_ASSIGNMENT, kInvalidExpressionId, {}, "arguments[0][0]", 0));
- ASSERT_TRUE(graph.ExpressionForId(a.id).IsArithmeticExpression());
- ASSERT_TRUE(graph.ExpressionForId(b.id).IsArithmeticExpression());
- ASSERT_TRUE(graph.ExpressionForId(c.id).IsArithmeticExpression());
- ASSERT_TRUE(graph.ExpressionForId(d.id).IsArithmeticExpression());
+ EXPECT_EQ(Expression::CreateOutputAssignment(ExpressionId(5), "residuals[3]"), Expression(
+ ExpressionType::OUTPUT_ASSIGNMENT, kInvalidExpressionId, {5}, "residuals[3]", 0));
+
+ EXPECT_EQ(Expression::CreateAssignment(ExpressionId(3), ExpressionId(5)), Expression(
+ ExpressionType::ASSIGNMENT, 3, {5}, "", 0));
+
+ EXPECT_EQ(Expression::CreateBinaryArithmetic("+", ExpressionId(3),ExpressionId(5)), Expression(
+ ExpressionType::BINARY_ARITHMETIC, kInvalidExpressionId, {3,5}, "+", 0));
+
+ EXPECT_EQ(Expression::CreateUnaryArithmetic("-", ExpressionId(5)), Expression(
+ ExpressionType::UNARY_ARITHMETIC, kInvalidExpressionId, {5}, "-", 0));
+
+ EXPECT_EQ(Expression::CreateBinaryCompare("<",ExpressionId(3),ExpressionId(5)), Expression(
+ ExpressionType::BINARY_COMPARISON, kInvalidExpressionId, {3,5}, "<", 0));
+
+ EXPECT_EQ(Expression::CreateLogicalNegation(ExpressionId(5)), Expression(
+ ExpressionType::LOGICAL_NEGATION, kInvalidExpressionId, {5}, "", 0));
+
+ EXPECT_EQ(Expression::CreateFunctionCall("pow",{ExpressionId(3),ExpressionId(5)}), Expression(
+ ExpressionType::FUNCTION_CALL, kInvalidExpressionId, {3,5}, "pow", 0));
+
+ EXPECT_EQ(Expression::CreateIf(ExpressionId(5)), Expression(
+ ExpressionType::IF, kInvalidExpressionId, {5}, "", 0));
+
+ EXPECT_EQ(Expression::CreateElse(), Expression(
+ ExpressionType::ELSE, kInvalidExpressionId, {}, "", 0));
+
+ EXPECT_EQ(Expression::CreateEndIf(), Expression(
+ ExpressionType::ENDIF, kInvalidExpressionId, {}, "", 0));
+ // clang-format on
+}
+
+TEST(Expression, IsArithmeticExpression) {
+ ASSERT_TRUE(
+ Expression::CreateCompileTimeConstant(5).IsArithmeticExpression());
+ ASSERT_TRUE(
+ Expression::CreateFunctionCall("pow", {3, 5}).IsArithmeticExpression());
+ // Logical expression are also arithmetic!
+ ASSERT_TRUE(
+ Expression::CreateBinaryCompare("<", 3, 5).IsArithmeticExpression());
+ ASSERT_FALSE(Expression::CreateIf(5).IsArithmeticExpression());
+ ASSERT_FALSE(Expression::CreateEndIf().IsArithmeticExpression());
+ ASSERT_FALSE(Expression().IsArithmeticExpression());
+}
+
+TEST(Expression, IsControlExpression) {
+ // In the current implementation this is the exact opposite of
+ // IsArithmeticExpression.
+ ASSERT_FALSE(Expression::CreateCompileTimeConstant(5).IsControlExpression());
+ ASSERT_FALSE(
+ Expression::CreateFunctionCall("pow", {3, 5}).IsControlExpression());
+ ASSERT_FALSE(
+ Expression::CreateBinaryCompare("<", 3, 5).IsControlExpression());
+ ASSERT_TRUE(Expression::CreateIf(5).IsControlExpression());
+ ASSERT_TRUE(Expression::CreateEndIf().IsControlExpression());
+ ASSERT_TRUE(Expression().IsControlExpression());
}
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));
+ ASSERT_TRUE(
+ Expression::CreateCompileTimeConstant(5).IsCompileTimeConstantAndEqualTo(
+ 5));
+ ASSERT_FALSE(
+ Expression::CreateCompileTimeConstant(3).IsCompileTimeConstantAndEqualTo(
+ 5));
+ ASSERT_FALSE(Expression::CreateBinaryCompare("<", 3, 5)
+ .IsCompileTimeConstantAndEqualTo(5));
}
TEST(Expression, IsReplaceableBy) {
- using T = ExpressionRef;
+ // Create 2 identical expression
+ auto expr1 =
+ Expression::CreateBinaryArithmetic("+", ExpressionId(3), ExpressionId(5));
- StartRecordingExpressions();
+ auto expr2 =
+ Expression::CreateBinaryArithmetic("+", ExpressionId(3), ExpressionId(5));
- // a2 should be replaceable by a
- T a(2), b(3), a2(2);
+ // They are idendical and of course replaceable
+ ASSERT_EQ(expr1, expr2);
+ ASSERT_EQ(expr2, expr1);
+ ASSERT_TRUE(expr1.IsReplaceableBy(expr2));
+ ASSERT_TRUE(expr2.IsReplaceableBy(expr1));
- // two redundant expressions
- // -> d should be replaceable by c
- T c = a + b;
- T d = a + b;
+ // Give them different left hand sides
+ expr1.set_lhs_id(72);
+ expr2.set_lhs_id(42);
- auto graph = StopRecordingExpressions();
+ // v_72 = v_3 + v_5
+ // v_42 = v_3 + v_5
+ // -> They should be replaceable by each other
- 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)));
+ ASSERT_NE(expr1, expr2);
+ ASSERT_NE(expr2, expr1);
+
+ ASSERT_TRUE(expr1.IsReplaceableBy(expr2));
+ ASSERT_TRUE(expr2.IsReplaceableBy(expr1));
+
+ // A slightly differnt expression with the argument flipped
+ auto expr3 =
+ Expression::CreateBinaryArithmetic("+", ExpressionId(5), ExpressionId(3));
+
+ ASSERT_NE(expr1, expr3);
+ ASSERT_FALSE(expr1.IsReplaceableBy(expr3));
}
TEST(Expression, DirectlyDependsOn) {
@@ -138,11 +211,11 @@
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, {}, "", 3);
- reference.InsertExpression( 2, ExpressionType::BINARY_COMPARISON, 2, {0,1}, "<", 0);
- reference.InsertExpression( 3, ExpressionType::FUNCTION_CALL, 3, {2,0,1}, "Ternary", 0);
- reference.InsertExpression( 4, ExpressionType::OUTPUT_ASSIGNMENT, 4, {3}, "result", 0);
+ reference.InsertBack({ ExpressionType::COMPILE_TIME_CONSTANT, 0, {}, "", 2});
+ reference.InsertBack({ ExpressionType::COMPILE_TIME_CONSTANT, 1, {}, "", 3});
+ reference.InsertBack({ ExpressionType::BINARY_COMPARISON, 2, {0,1}, "<", 0});
+ reference.InsertBack({ ExpressionType::FUNCTION_CALL, 3, {2,0,1}, "Ternary", 0});
+ reference.InsertBack({ ExpressionType::OUTPUT_ASSIGNMENT, 4, {3}, "result", 0});
// clang-format on
EXPECT_EQ(reference, graph);
}
@@ -161,9 +234,9 @@
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);
+ reference.InsertBack({ ExpressionType::COMPILE_TIME_CONSTANT, 0, {}, "", 1});
+ reference.InsertBack({ ExpressionType::COMPILE_TIME_CONSTANT, 1, {}, "", 2});
+ reference.InsertBack({ ExpressionType::ASSIGNMENT, 1, {0}, "", 0});
// clang-format on
EXPECT_EQ(reference, graph);
}
@@ -181,8 +254,8 @@
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);
+ reference.InsertBack({ ExpressionType::COMPILE_TIME_CONSTANT, 0, {}, "", 2});
+ reference.InsertBack({ ExpressionType::ASSIGNMENT, 1, {0}, "", 0});
// clang-format on
EXPECT_EQ(reference, graph);
}
@@ -200,7 +273,7 @@
ExpressionGraph reference;
// clang-format off
// Id, Type, Lhs, Value, Name, Arguments
- reference.InsertExpression( 0, ExpressionType::COMPILE_TIME_CONSTANT, 0, {}, "", 1);
+ reference.InsertBack({ ExpressionType::COMPILE_TIME_CONSTANT, 0, {}, "", 1});
// clang-format on
EXPECT_EQ(reference, graph);
}
@@ -219,9 +292,9 @@
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);
+ reference.InsertBack({ ExpressionType::COMPILE_TIME_CONSTANT, 0, {}, "", 1});
+ reference.InsertBack({ ExpressionType::COMPILE_TIME_CONSTANT, 1, {}, "", 2});
+ reference.InsertBack({ ExpressionType::ASSIGNMENT, 1, {0}, "", 0});
// clang-format on
EXPECT_EQ(reference, graph);
}
