1    	/*
2    	 Expression writer
3    	
4    	 Copyright (C) 2014 AMPL Optimization Inc
5    	
6    	 Permission to use, copy, modify, and distribute this software and its
7    	 documentation for any purpose and without fee is hereby granted,
8    	 provided that the above copyright notice appear in all copies and that
9    	 both that the copyright notice and this permission notice and warranty
10   	 disclaimer appear in supporting documentation.
11   	
12   	 The author and AMPL Optimization Inc disclaim all warranties with
13   	 regard to this software, including all implied warranties of
14   	 merchantability and fitness.  In no event shall the author be liable
15   	 for any special, indirect or consequential damages or any damages
16   	 whatsoever resulting from loss of use, data or profits, whether in an
17   	 action of contract, negligence or other tortious action, arising out
18   	 of or in connection with the use or performance of this software.
19   	
20   	 Author: Victor Zverovich
21   	 */
22   	
23   	#ifndef MP_EXPR_WRITER_H_
24   	#define MP_EXPR_WRITER_H_
25   	
26   	#include "mp/basic-expr-visitor.h"
27   	
28   	namespace mp {
29   	
30   	namespace prec {
31   	enum Precedence {
32   	  UNKNOWN,
33   	  CONDITIONAL,       // if-then-else
34   	  IFF,               // <==>
35   	  IMPLICATION,       // ==> else
36   	  LOGICAL_OR,        // or ||
37   	  LOGICAL_AND,       // and &&
38   	  NOT,               // not !
39   	  RELATIONAL,        // < <= = == >= > != <>
40   	  ADDITIVE,          // + - less
41   	  ITERATIVE,         // sum prod min max
42   	  MULTIPLICATIVE,    // * / div mod
43   	  EXPONENTIATION,    // ^
44   	  UNARY,             // + - (unary)
45   	  CALL,              // a function call including functional forms of
46   	                     // min and max
47   	  PRIMARY            // variable, string or constant
48   	};
49   	}
50   	
51   	namespace expr {
52   	// Returns operator precedence for the specified expression kind assuming the
53   	// notation used by ExprWriter.
54   	prec::Precedence precedence(expr::Kind kind);
55   	
56   	class PrecInfo {
57   	 private:
58   	  static const prec::Precedence INFO[LAST_EXPR + 1];
59   	  friend prec::Precedence precedence(Kind kind) {
60   	    MP_ASSERT(internal::IsValid(kind), "invalid expression kind");
61   	    return INFO[kind];
62   	  }
63   	};
64   	}
65   	
66   	template <typename ExprTypes, typename NumericExpr>
67   	inline bool IsZero(NumericExpr expr) {
68   	  typedef typename ExprTypes::NumericConstant NumericConstant;
69   	  NumericConstant n = ExprTypes::template Cast<NumericConstant>(expr);
70   	  return n && n.value() == 0;
71   	}
72   	
73   	// An expression visitor that writes AMPL expressions in a textual form
74   	// to fmt::Writer. It takes into account precedence and associativity
75   	// of operators avoiding unnecessary parentheses except for potentially
76   	// confusing cases such as "!x = y" which is written as "!(x = y) instead.
77   	template <typename ExprTypes>
78   	class ExprWriter :
79   	    public BasicExprVisitor<ExprWriter<ExprTypes>, void, ExprTypes> {
80   	 private:
81   	  fmt::Writer &writer_;
82   	  int precedence_;
83   	
84   	  MP_DEFINE_EXPR_TYPES(ExprTypes);
85   	
86   	  typedef BasicExprVisitor<ExprWriter<ExprTypes>, void, ExprTypes> Base;
87   	
88   	  static int precedence(Expr e) { return expr::precedence(e.kind()); }
89   	
90   	  // Writes an argument list surrounded by parentheses.
91   	  template <typename Iter>
92   	  void WriteArgs(Iter begin, Iter end, const char *sep = ", ",
93   	      int precedence = prec::UNKNOWN);
94   	
95   	  template <typename Expr>
96   	  void WriteArgs(Expr e, const char *sep = ", ",
97   	      int precedence = prec::UNKNOWN) {
98   	    WriteArgs(e.begin(), e.end(), sep, precedence);
99   	  }
100  	
101  	  // Writes a function or an expression that has a function syntax.
102  	  template <typename Expr>
103  	  void WriteFunc(Expr e) {
104  	    writer_ << str(e.kind());
105  	    WriteArgs(e);
106  	  }
107  	
108  	  template <typename ExprType>
109  	  void WriteBinary(ExprType e);
110  	
111  	  void WriteCallArg(Expr arg);
112  	
113  	  class Parenthesizer {
114  	   private:
115  	    ExprWriter &writer_;
116  	    int saved_precedence_;
117  	    bool write_paren_;
118  	
119  	   public:
120  	    Parenthesizer(ExprWriter &w, Expr e, int precedence);
121  	    ~Parenthesizer();
122  	  };
123  	
124  	 public:
125  	  explicit ExprWriter(fmt::Writer &w)
126  	  : writer_(w), precedence_(prec::UNKNOWN) {}
127  	
128  	  void Visit(NumericExpr e, int precedence = -1) {
129  	    Parenthesizer p(*this, e, precedence);
130  	    Base::Visit(e);
131  	  }
132  	
133  	  void Visit(LogicalExpr e, int precedence = -1) {
134  	    Parenthesizer p(*this, e, precedence);
135  	    Base::Visit(e);
136  	  }
137  	
138  	  void VisitNumericConstant(NumericConstant c) { writer_ << c.value(); }
139  	
140  	  void VisitUnary(UnaryExpr e) {
141  	    writer_ << str(e.kind()) << '(';
142  	    Visit(e.arg(), prec::UNKNOWN);
143  	    writer_ << ')';
144  	  }
145  	
146  	  void VisitMinus(UnaryExpr e) {
147  	    writer_ << '-';
148  	    Visit(e.arg());
149  	  }
150  	
151  	  void VisitPow2(UnaryExpr e) {
152  	    Visit(e.arg(), prec::EXPONENTIATION + 1);
153  	    writer_ << " ^ 2";
154  	  }
155  	
156  	  void VisitBinary(BinaryExpr e) { WriteBinary(e); }
157  	  void VisitBinaryFunc(BinaryExpr e);
158  	  void VisitIf(IfExpr e);
159  	  void VisitVarArg(VarArgExpr e) { WriteFunc(e); }
160  	  void VisitSum(SumExpr e);
161  	  void VisitCount(CountExpr e) { WriteFunc(e); }
162  	  void VisitNumberOf(NumberOfExpr e);
163  	  void VisitPLTerm(PLTerm e);
164  	  void VisitCall(CallExpr e);
165  	  void VisitVariable(Variable v) { writer_ << 'x' << (v.index() + 1); }
166  	
167  	  void VisitNot(NotExpr e) {
168  	     writer_ << '!';
169  	     // Use a precedence higher then relational to print expressions
170  	     // as "!(x = y)" instead of "!x = y".
171  	     LogicalExpr arg = e.arg();
172  	     Visit(arg,
173  	           precedence(arg) == prec::RELATIONAL ? prec::RELATIONAL + 1 : -1);
174  	  }
175  	
176  	  void VisitBinaryLogical(BinaryLogicalExpr e) { WriteBinary(e); }
177  	  void VisitRelational(RelationalExpr e) { WriteBinary(e); }
178  	  void VisitLogicalCount(LogicalCountExpr e);
179  	  void VisitIteratedLogical(IteratedLogicalExpr e);
180  	  void VisitImplication(ImplicationExpr e);
181  	  void VisitAllDiff(PairwiseExpr e) { WriteFunc(e); }
182  	  void VisitLogicalConstant(LogicalConstant c) { writer_ << c.value(); }
183  	};
184  	
185  	template <typename ExprTypes>
186  	ExprWriter<ExprTypes>::Parenthesizer::Parenthesizer(
187  	    ExprWriter<ExprTypes> &w, Expr e, int prec)
188  	: writer_(w), write_paren_(false) {
189  	  saved_precedence_ = w.precedence_;
190  	  if (prec == -1)
191  	    prec = w.precedence_;
192  	  write_paren_ = precedence(e) < prec;
193  	  if (write_paren_)
194  	    w.writer_ << '(';
195  	  w.precedence_ = precedence(e);
196  	}
197  	
198  	template <typename ExprTypes>
199  	ExprWriter<ExprTypes>::Parenthesizer::~Parenthesizer() {
200  	  writer_.precedence_ = saved_precedence_;
201  	  if (write_paren_)
202  	    writer_.writer_ << ')';
203  	}
204  	
205  	template <typename ExprTypes>
206  	template <typename Iter>
207  	void ExprWriter<ExprTypes>::WriteArgs(
208  	    Iter begin, Iter end, const char *sep, int precedence) {
209  	  writer_ << '(';
210  	  if (begin != end) {
211  	    Visit(*begin, precedence);
212  	    for (++begin; begin != end; ++begin) {
213  	      writer_ << sep;
214  	      Visit(*begin, precedence);
215  	    }
216  	  }
217  	  writer_ << ')';
218  	}
219  	
220  	template <typename ExprTypes>
221  	template <typename ExprType>
222  	void ExprWriter<ExprTypes>::WriteBinary(ExprType e) {
223  	  int prec = precedence(e);
224  	  bool right_associative = prec == prec::EXPONENTIATION;
225  	  Visit(e.lhs(), prec + (right_associative ? 1 : 0));
226  	  writer_ << ' ' << str(e.kind()) << ' ';
227  	  Visit(e.rhs(), prec + (right_associative ? 0 : 1));
228  	}
229  	
230  	template <typename ExprTypes>
231  	void ExprWriter<ExprTypes>::WriteCallArg(Expr arg) {
232  	  if (NumericExpr e = ExprTypes::template Cast<NumericExpr>(arg)) {
233  	    Visit(e, prec::UNKNOWN);
234  	    return;
235  	  }
236  	  assert(arg.kind() == expr::STRING);
237  	  writer_ << "'";
238  	  const char *s = ExprTypes::template Cast<StringLiteral>(arg).value();
239  	  for ( ; *s; ++s) {
240  	    char c = *s;
241  	    switch (c) {
242  	    case '\n':
243  	      writer_ << '\\' << c;
244  	      break;
245  	    case '\'':
246  	      // Escape quote by doubling.
247  	      writer_ << c;
248  	      // Fall through.
249  	    default:
250  	      writer_ << c;
251  	    }
252  	  }
253  	  writer_ << "'";
254  	}
255  	
256  	template <typename ExprTypes>
257  	void ExprWriter<ExprTypes>::VisitBinaryFunc(BinaryExpr e) {
258  	  writer_ << str(e.kind()) << '(';
259  	  Visit(e.lhs(), prec::UNKNOWN);
260  	  writer_ << ", ";
261  	  Visit(e.rhs(), prec::UNKNOWN);
262  	  writer_ << ')';
263  	}
264  	
265  	template <typename ExprTypes>
266  	void ExprWriter<ExprTypes>::VisitIf(IfExpr e) {
267  	  writer_ << "if ";
268  	  Visit(e.condition(), prec::UNKNOWN);
269  	  writer_ << " then ";
270  	  NumericExpr else_expr = e.else_expr();
271  	  bool has_else = !IsZero<ExprTypes>(else_expr);
272  	  Visit(e.then_expr(), prec::CONDITIONAL + (has_else ? 1 : 0));
273  	  if (has_else) {
274  	    writer_ << " else ";
275  	    Visit(else_expr);
276  	  }
277  	}
278  	
279  	template <typename ExprTypes>
280  	void ExprWriter<ExprTypes>::VisitSum(SumExpr e) {
281  	  writer_ << "/* sum */ (";
282  	  typename SumExpr::iterator i = e.begin(), end = e.end();
283  	  if (i != end) {
284  	    Visit(*i);
285  	    for (++i; i != end; ++i) {
286  	      writer_ << " + ";
287  	      Visit(*i);
288  	    }
289  	  }
290  	  writer_ << ')';
291  	}
292  	
293  	template <typename ExprTypes>
294  	void ExprWriter<ExprTypes>::VisitNumberOf(NumberOfExpr e) {
295  	  writer_ << "numberof ";
296  	  typename NumberOfExpr::iterator i = e.begin();
297  	  Visit(*i++, prec::UNKNOWN);
298  	  writer_ << " in ";
299  	  WriteArgs(i, e.end());
300  	}
301  	
302  	template <typename ExprTypes>
303  	void ExprWriter<ExprTypes>::VisitPLTerm(PLTerm e) {
304  	  writer_ << "<<" << e.breakpoint(0);
305  	  for (int i = 1, n = e.num_breakpoints(); i < n; ++i)
306  	    writer_ << ", " << e.breakpoint(i);
307  	  writer_ << "; " << e.slope(0);
308  	  for (int i = 1, n = e.num_slopes(); i < n; ++i)
309  	    writer_ << ", " << e.slope(i);
310  	  writer_ << ">> ";
311  	  NumericExpr arg = e.arg();
312  	  if (Variable var = ExprTypes::template Cast<Variable>(arg))
313  	    writer_ << "x" << (var.index() + 1);
314  	  else
315  	    writer_ << "e" << ((ExprTypes::template Cast<CommonExpr>(arg)).index() + 1);
316  	}
317  	
318  	template <typename ExprTypes>
319  	void ExprWriter<ExprTypes>::VisitCall(CallExpr e) {
320  	  writer_ << e.function().name() << '(';
321  	  typename CallExpr::iterator i = e.begin(), end = e.end();
322  	  if (i != end) {
323  	    WriteCallArg(*i++);
324  	    for (; i != end; ++i) {
325  	      writer_ << ", ";
326  	      WriteCallArg(*i);
327  	    }
328  	  }
329  	  writer_ << ')';
330  	}
331  	
332  	template <typename ExprTypes>
333  	void ExprWriter<ExprTypes>::VisitLogicalCount(LogicalCountExpr e) {
334  	  writer_ << str(e.kind()) << ' ';
335  	  Visit(e.lhs());
336  	  writer_ << ' ';
337  	  WriteArgs(e.rhs());
338  	}
339  	
340  	template <typename ExprTypes>
341  	void ExprWriter<ExprTypes>::VisitIteratedLogical(IteratedLogicalExpr e) {
342  	  // There is no way to produce an AMPL forall/exists expression because
343  	  // its indexing is not available any more. So we write a count expression
344  	  // instead with a comment about the original expression.
345  	  writer_ << "/* " << str(e.kind()) << " */ ";
346  	  int prec = prec::LOGICAL_AND + 1;
347  	  const char *op = " && ";
348  	  if (e.kind() == expr::EXISTS) {
349  	    prec = prec::LOGICAL_OR + 1;
350  	    op = " || ";
351  	  }
352  	  WriteArgs(e, op, prec);
353  	}
354  	
355  	template <typename ExprTypes>
356  	void ExprWriter<ExprTypes>::VisitImplication(ImplicationExpr e) {
357  	  Visit(e.condition());
358  	  writer_ << " ==> ";
359  	  Visit(e.then_expr(), prec::IMPLICATION + 1);
360  	  LogicalExpr else_expr = e.else_expr();
361  	  LogicalConstant c = ExprTypes::template Cast<LogicalConstant>(else_expr);
362  	  if (!c || c.value() != 0) {
363  	    writer_ << " else ";
364  	    Visit(else_expr);
365  	  }
366  	}
367  	
368  	template <typename ExprTypes, typename LinearExpr, typename NumericExpr>
369  	void WriteExpr(fmt::Writer &w, const LinearExpr &linear,
370  	               NumericExpr nonlinear) {
371  	  bool have_terms = false;
372  	  typedef typename LinearExpr::iterator Iterator;
373  	  for (Iterator i = linear.begin(), e = linear.end(); i != e; ++i) {
374  	    double coef = i->coef();
375  	    if (coef != 0) {
376  	      if (have_terms)
377  	        w << " + ";
378  	      else
379  	        have_terms = true;
380  	      if (coef != 1)
381  	        w << coef << " * ";
382  	      w << "x" << (i->var_index() + 1);
383  	    }
384  	  }
385  	  if (!nonlinear || IsZero<ExprTypes>(nonlinear)) {
386  	    if (!have_terms)
387  	      w << "0";
388  	    return;
389  	  }
390  	  if (have_terms)
391  	    w << " + ";
392  	  ExprWriter<ExprTypes>(w).Visit(nonlinear);
393  	}
394  	
395  	// Writes a problem in AMPL format.
396  	template <typename Problem>
397  	void Write(fmt::Writer &w, const Problem &p) {
398  	  // Write variables.
399  	  double inf = std::numeric_limits<double>::infinity();
400  	  int num_vars = p.num_vars();
401  	  for (int i = 0; i < num_vars; ++i) {
402  	    w << "var x" << (i + 1);
403  	    typename Problem::Variable var = p.var(i);
404  	    double lb = var.lb(), ub = var.ub();
405  	    if (lb == ub) {
406  	      w << " = " << lb;
407  	    } else {
408  	      if (lb != -inf)
409  	        w << " >= " << lb;
410  	      if (ub != inf)
411  	        w << " <= " << ub;
412  	    }
413  	    w << ";\n";
414  	  }
415  	
416  	  // Write objectives.
417  	  for (int i = 0, n = p.num_objs(); i < n; ++i) {
418  	    typename Problem::Objective obj = p.obj(i);
419  	    w << (obj.type() == mp::obj::MIN ? "minimize" : "maximize") << " o: ";
420  	    WriteExpr<typename Problem::ExprTypes>(
421  	          w, obj.linear_expr(), obj.nonlinear_expr());
422  	    w << ";\n";
423  	  }
424  	
425  	  // Write algebraic constraints.
426  	  for (int i = 0, n = p.num_algebraic_cons(); i < n; ++i) {
427  	    w << "s.t. c" << (i + 1) << ": ";
428  	    typename Problem::AlgebraicCon con = p.algebraic_con(i);
429  	    double lb = con.lb(), ub = con.ub();
430  	    if (lb != ub && lb != -inf && ub != inf)
431  	      w << lb << " <= ";
432  	    WriteExpr<typename Problem::ExprTypes>(
433  	          w, con.linear_expr(), con.nonlinear_expr());
434  	    if (lb == ub)
435  	      w << " = " << lb;
436  	    else if (ub != inf)
437  	      w << " <= " << ub;
438  	    else if (lb != -inf)
439  	      w << " >= " << lb;
440  	    w << ";\n";
441  	  }
442  	}
443  	}  // namespace mp
444  	
445  	#endif  // MP_EXPR_WRITER_H_
446