1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 2 3 /* This Source Code Form is subject to the terms of the Mozilla Public 4 * License, v. 2.0. If a copy of the MPL was not distributed with this 5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 6 7 #pragma once 8 9 //#include <assert.h> 10 11 #include <exception> 12 #include <iostream> 13 #include <sstream> 14 #include <string> 15 #include <utility> 16 #include <vector> 17 18 /* A NL File is composed of a header and several segments. 19 Adding items in the nl file is done through adding segment (or adding item in a segment). 20 As for the header, segment are printable. 21 Segment are identified by a prefix, which should be one of (taken from table 13 in 'writing nl 22 files'): F imported function description S suffix values V defined variable definition (must 23 precede V,C,L,O segments where used) (yes, I know, "V must preceed V"...) C algebraic constraint 24 body L logical constraint expression O objective function d dual initial guess x primal 25 initial guess r bounds on algebraic constraint bodies (“ranges”), can only appears once b bounds 26 on variable, can only appears once k Jacobian column counts (must precede all J segments) J 27 Jacobian sparsity, linear terms G Gradient sparsity, linear terms 28 */ 29 30 namespace MiniZinc { 31 32 // --- --- --- Tooling 33 34 /** Exception when translating 35 * Code mostly taken from https://www.softwariness.com/articles/assertions-in-cpp/ 36 */ 37 class NLException : public std::exception { 38 public: 39 // --- --- --- Fields 40 const char* expression; 41 const char* file; 42 int line; 43 std::string message; 44 std::string report; 45 46 /** Exception constructor. Use with the macro assert/should_not_happen. 47 * If not, WARNING: stream must be a std::ostringstream& 48 * We only use a ostreamé so we can use the standard "<<" operator, which is returning a ostream& 49 */ NLException(const char * expression,const char * file,int line,std::ostream & stream)50 NLException(const char* expression, const char* file, int line, std::ostream& stream) 51 : expression(expression), file(file), line(line) { 52 message = static_cast<std::ostringstream&>(stream).str(); 53 std::ostringstream outputStream; 54 55 if (expression == nullptr) { 56 outputStream << "Something should not have happen in file '" << file << "' line " << line 57 << ". Message:" << std::endl; 58 if (!message.empty()) { 59 outputStream << message << std::endl; 60 } else { 61 outputStream << "No message provided..." << std::endl; 62 } 63 } else { 64 std::string expressionString = expression; 65 if (expressionString == "false" || expressionString == "0" || expressionString == "FALSE") { 66 outputStream << "Unreachable code assertion"; 67 } else { 68 outputStream << "Assertion '" << expression << "'"; 69 } 70 outputStream << " failed in file '" << file << "' line " << line << std::endl; 71 } 72 outputStream << "Note: the NL component is still in development!" << std::endl; 73 report = outputStream.str(); 74 } 75 76 /** Exception interface */ what() const77 const char* what() const noexcept override { return report.c_str(); } 78 79 ~NLException() noexcept override = default; 80 }; 81 82 #ifdef assert 83 #undef assert 84 #endif 85 86 /** Should not happen macro */ 87 #define should_not_happen(MESSAGE) \ 88 do { \ 89 ostringstream oss; \ 90 oss << MESSAGE; /* NOLINT(bugprone-macro-parentheses) */ \ 91 throw NLException(NULL, __FILE__, __LINE__, oss); \ 92 } while (false) 93 94 /* CMake febug build flag: double negation... because... ? */ 95 #ifndef NDEBUG 96 #define DEBUG_MSG(STR) \ 97 do { \ 98 std::cerr << "%[NL DEBUG] " << STR << endl; /* NOLINT(bugprone-macro-parentheses) */ \ 99 } while (false) 100 #define assert(EXPRESSION) \ 101 do { \ 102 if (!(EXPRESSION)) { \ 103 ostringstream oss; \ 104 throw NLException(#EXPRESSION, __FILE__, __LINE__, oss); \ 105 } \ 106 } while (false) 107 #else 108 #define DEBUG_MSG(STR) \ 109 do { \ 110 } while (false) 111 #define assert(EXPRESSION) \ 112 do { \ 113 } while (false) 114 #endif 115 116 // --- --- --- Components 117 118 // Declaration 119 class NLFile; 120 121 /** A Bound. 122 * A bound can represent various constraint on a variable or a constraint. 123 * Because it apply to both variables and constraints, we keep it general enough. 124 * Note that the targeted variable or constraint is implicitely represented by its position in the 125 final NL File. 126 * As a result, this information does not appear here. 127 * Bounds are used in the 'b' and 'r' segments. 128 129 # Text # Starting the segment # Variable # Tag in enum NLS_Bounditem::Bound 130 0 1.1 3.4 # 1.1 =< V =< 3.4 First variable LB_UB 131 1 2.5 # V =< 2.5 Second variable UB 132 2 7 # 7 =< V etc... LB 133 3 # no constraint NONE 134 4 9.4 # V = 9.4 EQ 135 136 * Notes: - bound values are stored as 'double', even for integer variables. 137 * - we do not make that class Printable as it is better "printed" with a name for the 138 targeted variable/constraint 139 */ 140 class NLBound { 141 public: 142 /** Bound kind. Declaration matches specification above. */ 143 enum Bound { LB_UB = 0, UB = 1, LB = 2, NONE = 3, EQ = 4 }; 144 145 /** *** *** *** Fields *** *** *** **/ 146 Bound tag = NONE; 147 double lb = 0; 148 double ub = 0; 149 150 /** *** *** *** Constructors & helpers *** *** *** **/ 151 NLBound() = default; 152 NLBound(Bound tag, double lb, double ub); 153 154 static NLBound makeBounded(double lb, double ub); 155 static NLBound makeUBBounded(double ub); 156 static NLBound makeLBBounded(double lb); 157 static NLBound makeNoBound(); 158 static NLBound makeEqual(double val); 159 160 /** *** *** *** Update the lower or upper bound *** *** *** **/ 161 // Note: this method are "additive only": we cannot use them to remove a a bound. 162 void updateLB(double new_lb); 163 void updateUB(double new_ub); 164 void updateEq(double new_eq); 165 166 /** *** *** *** Printing Methods *** *** *** **/ 167 168 /** Print the bound with a comment containing the name of the variable/constraint. */ 169 std::ostream& printToStream(std::ostream& o, const std::string& vname) const; 170 171 /** Printing with 'body' as the name of the variable/constraint. */ 172 std::ostream& printToStream(std::ostream& o) const; 173 }; 174 175 /** A Declared variable. 176 * A variable is identified by its name, which is supposed to be unique in the MZN representation. 177 * In an NL file, variables are identified by their index. However, those index are dependent on 178 * the variable ordering, which can only be known once all variables are known. Hence, the 179 * computation of the index can only be achieved at a later stage. A variable is always associated 180 * to a bound, even if none are specified (See LNBound above)/ 181 */ 182 class NLVar { 183 public: 184 /** Variable name. */ 185 std::string name; 186 187 /** Is the variable an integer variable? Else is a floating point variable. */ 188 bool isInteger = false; 189 190 /** Is this variable flagged to be reported? */ 191 bool toReport = false; 192 193 /** Is the variable appearing in a nonlinear constraint (including logical constraint, L segment). 194 */ 195 bool isInNLConstraint = false; 196 197 /** Is the variable appearing non linearly in the objective? */ 198 bool isInNLObjective = false; 199 200 /** Number of occurrences in Jacobian. */ 201 unsigned int jacobianCount = 0; 202 203 /** The bound over this variable. 204 * Used when producing the unique 'b' segment of the NL file. 205 */ 206 NLBound bound; 207 208 /* *** *** *** Constructors *** *** *** */ 209 NLVar() = default; 210 211 /** Constructor with declare time information */ NLVar(std::string name,bool isInteger,bool to_report,NLBound bound)212 NLVar(std::string name, bool isInteger, bool to_report, NLBound bound) 213 : name(std::move(name)), isInteger(isInteger), toReport(to_report), bound(bound) {} 214 215 /** Copy constructor, with update on bound */ 216 NLVar copyWithBound(NLBound bound) const; 217 }; 218 219 /** A NLArray: 220 * We do not use "real" array. 221 * This type only serves when sending the result back to minizinc 222 */ 223 class NLArray { 224 public: 225 /** Array item; if the string is empty, use the value. */ 226 class Item { 227 public: 228 std::string variable; 229 double value; 230 }; 231 232 /** Array name */ 233 std::string name; 234 235 /** Dimensions part, e.g. array2d( '0..4', '0..5' [ .... ]) */ 236 std::vector<std::string> dimensions; 237 238 /** Related variables */ 239 std::vector<Item> items; 240 241 /** Is this an array or integers or floats? */ 242 bool isInteger = false; 243 }; 244 245 /** A token from an 'expression graph'. 246 * An expression graph is express in Polish Prefix Notation: operator followed by operand. 247 * A token represent an operator or an operand. 248 * See the definition of the various enum. 249 */ 250 class NLToken { 251 public: 252 /** Kind of token. */ 253 enum Kind { 254 NUMERIC, // "n42.42" a numeric constant, double 255 VARIABLE, // "v4" reference to a decision variable 0<= i < nb_vars (see header) or a 256 // defined variable for i>=nb_vars 257 STRING, // "h11:some string" Probably unused in our case. 258 FUNCALL, // "f0 3" Call a defined function (index 0, 3 args). Probably unused in 259 // our case. 260 OP, // "o5" An operation defined by its operation code 261 MOP // "o7\n3" Operator with multiple operand. The number of operands (3) is on 262 // the next line ("\n")? 263 }; 264 265 /** Opcode for operator with a fixed number of operands. */ 266 enum OpCode { 267 OPPLUS = 0, 268 OPMINUS = 1, 269 OPMULT = 2, 270 OPDIV = 3, 271 OPREM = 4, 272 OPPOW = 5, 273 OPLESS = 6, 274 FLOOR = 13, 275 CEIL = 14, 276 ABS = 15, 277 OPUMINUS = 16, 278 OPOR = 20, 279 OPAND = 21, 280 LT = 22, 281 LE = 23, 282 EQ = 24, 283 GE = 28, 284 GT = 29, 285 NE = 30, 286 OPNOT = 34, 287 OPIFnl = 35, 288 OP_tanh = 37, 289 OP_tan = 38, 290 OP_sqrt = 39, 291 OP_sinh = 40, 292 OP_sin = 41, 293 OP_log10 = 42, 294 OP_log = 43, 295 OP_exp = 44, 296 OP_cosh = 45, 297 OP_cos = 46, 298 OP_atanh = 47, 299 OP_atan2 = 48, 300 OP_atan = 49, 301 OP_asinh = 50, 302 OP_asin = 51, 303 OP_acosh = 52, 304 OP_acos = 53, 305 OPintDIV = 55, 306 OPprecision = 56, 307 OPround = 57, 308 OPtrunc = 58, 309 OPATLEAST = 62, 310 OPATMOST = 63, 311 OPPLTERM = 64, 312 OPIFSYM = 65, 313 OPEXACTLY = 66, 314 OPNOTATLEAST = 67, 315 OPNOTATMOST = 68, 316 OPNOTEXACTLY = 69, 317 OPIMPELSE = 72, 318 OP_IFF = 73, 319 OPSOMESAME = 75, 320 OP1POW = 76, 321 OP2POW = 77, 322 OPCPOW = 78, 323 OPFUNCALL = 79, 324 OPNUM = 80, 325 OPHOL = 81, 326 OPVARVAL = 82, 327 N_OPS = 83, 328 }; 329 330 /** Opcodes for operand taking multiple arguments. */ 331 enum MOpCode { 332 MINLIST = 11, 333 MAXLIST = 12, 334 OPSUMLIST = 54, 335 OPCOUNT = 59, 336 OPNUMBEROF = 60, 337 OPNUMBEROFs = 61, 338 ANDLIST = 70, 339 ORLIST = 71, 340 OPALLDIFF = 74, 341 }; 342 343 /** Obtain the name of an operator from its opcode. */ 344 static const char* getName(OpCode oc); 345 346 /** Obtain the name of an operator (with multiple operands) from its opcode. */ 347 static const char* getName(MOpCode moc); 348 349 /* *** *** *** Fields *** *** *** */ 350 351 Kind kind; 352 double numericValue; // if kind==NUMERIC 353 int argCount; // if kind==FUNCALL or kind==MOP 354 std::string 355 str; // if kind==STRING or kind=VARIABLE (variable name) or kind=FUNCALL (function name) 356 OpCode oc; // if kind==OP 357 MOpCode moc; // if kind==MOP 358 359 /* *** *** *** Constructor and helpers *** *** *** */ 360 361 NLToken() = default; 362 363 static NLToken n(double value); 364 365 static NLToken v(std::string vname); 366 367 static NLToken o(OpCode opc); 368 369 static NLToken mo(MOpCode mopc, int nb); 370 371 /* *** *** *** Query *** *** *** */ 372 bool isVariable() const; 373 374 bool isConstant() const; 375 376 /* *** *** *** Printable *** *** *** */ 377 378 std::ostream& printToStream(std::ostream& o, const NLFile& nl_file) const; 379 }; 380 381 /** A algebraic constraint. 382 * Contains both a linear and a non linear part. 383 * We do not handle network constraints. 384 */ 385 class NLAlgCons { 386 public: 387 /** Constraint name, also acts as identifier. */ 388 std::string name; 389 390 /** Bound on the algebraic constraint. 391 * Used when producing the unique r of the NL file. 392 */ 393 NLBound range; 394 395 /** Expression graph, used for the non linear part. 396 * Used to produce a new, standalone, C segment. 397 * If the expression graph is empty (linear constraint), produce the expression graph 'n0' 398 */ 399 std::vector<NLToken> expressionGraph = {}; 400 401 /** Jacobian, used for the linear part. Identify a variable by its name and associate a 402 * coefficent. Used to produce a new, standalone, J segment. 403 */ 404 std::vector<std::pair<std::string, double>> jacobian = {}; 405 406 /** Method to build the var_coeff vector. 407 * The NLFile is used to access the variables through their name in order to increase their 408 * jacobian count. 409 */ 410 void setJacobian(const std::vector<std::string>& vnames, const std::vector<double>& coeffs, 411 NLFile* nl_file); 412 413 /* *** *** *** Helpers *** *** *** */ 414 415 /** A constraint is considered linear if the expressionGraph is empty. */ 416 bool isLinear() const; 417 418 /* *** *** *** Printable *** *** *** */ 419 420 std::ostream& printToStream(std::ostream& o, const NLFile& nl_file) const; 421 }; 422 423 /** A logical constraint. 424 * Contains only a non linear part. 425 * We do not handle network constraints. 426 * Logical constraint stands on their own and do not need any identifier. 427 * However, for consistency sake, we still keep their name. 428 */ 429 class NLLogicalCons { 430 public: 431 /** Constraint name, also acts as identifier. */ 432 std::string name; 433 434 /** Index */ 435 int index = -1; 436 437 /** Expression graph, used for the non linear part. 438 * Used to produce a new, standalone, L segment. 439 * If the expression graph is empty (linear constraint), produce the expression graph 'n0' 440 */ 441 std::vector<NLToken> expressionGraph = {}; 442 443 /* *** *** *** Constructor *** *** *** */ NLLogicalCons(int idx)444 NLLogicalCons(int idx) : index(idx) {} 445 446 /* *** *** *** Printable *** *** *** */ 447 448 std::ostream& printToStream(std::ostream& o, const NLFile& nl_file) const; 449 }; 450 451 /** The header. */ 452 class NLHeader { 453 public: 454 /* *** *** *** Printable *** *** *** */ 455 456 static std::ostream& printToStream(std::ostream& o, const NLFile& nl_file); 457 }; 458 459 /** An Objective 460 * In an NL file, we can have several of those. 461 * However, in flatzinc, only one is allowed, so we only have one. 462 * Note that in NL, we do not have a "satisfy" objective, only a minimize or maximize one. 463 * We translate the "satisfy" with "minimize n0". 464 */ 465 class NLObjective { 466 public: 467 enum MinMax { 468 UNDEF = -2, 469 SATISFY = -1, 470 MINIMIZE = 0, 471 MAXIMIZE = 1, 472 }; 473 474 /* *** *** *** Fields *** *** *** */ 475 MinMax minmax = UNDEF; 476 std::vector<NLToken> expressionGraph = {}; // If empty, produce a 'n0' when printing 477 478 /* *** *** *** Gradient *** *** *** */ 479 480 /** Gradient, used for the linear part. Identify a variable by its name and associate a 481 * coefficent. Used to produce a new, standalone, G segment. 482 */ 483 std::vector<std::pair<std::string, double>> gradient = {}; 484 485 /** Method to build the var_coeff vector. */ 486 void setGradient(const std::vector<std::string>& vnames, const std::vector<double>& coeffs); 487 488 int gradientCount() const; 489 490 /* *** *** *** Helpers *** *** *** */ 491 bool isDefined() const; 492 493 bool isLinear() const; 494 495 bool isOptimisation() const; 496 497 /* *** *** *** Constructor *** *** *** */ 498 NLObjective() = default; 499 500 /* *** *** *** Printable *** *** *** */ 501 std::ostream& printToStream(std::ostream& o, const NLFile& nl_file) const; 502 }; 503 504 } // namespace MiniZinc 505