00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00026 #include "OWBI1_config.h"
00027 #include "OW_Assertion.hpp"
00028 #include "OWBI1_WQLOperation.hpp"
00029 #include "OWBI1_WQLOperand.hpp"
00030 #include "OWBI1_WQLCompile.hpp"
00031 #include "OW_Format.hpp"
00032 #include <stack>
00033 #ifdef OWBI1_HAVE_OSTREAM
00034 #include <ostream>
00035 #else
00036 #include <iostream>
00037 #endif
00038 #include <algorithm>
00039
00040 namespace OWBI1
00041 {
00042
00043 using namespace OpenWBEM;
00044
00045
00046
00047
00048 void WQLCompile::term_el::negate()
00049 {
00050 switch (op)
00051 {
00052 case WQL_EQ: op = WQL_NE; break;
00053 case WQL_NE: op = WQL_EQ; break;
00054 case WQL_LT: op = WQL_GE; break;
00055 case WQL_LE: op = WQL_GT; break;
00056 case WQL_GT: op = WQL_LE; break;
00057 case WQL_GE: op = WQL_LT; break;
00058 default: break;
00059 }
00060 };
00061 bool operator==(const WQLCompile::term_el& x, const WQLCompile::term_el& y)
00062 {
00063 return x.op == y.op && x.opn1 == y.opn1 && x.opn2 == y.opn2;
00064 }
00065 bool operator!=(const WQLCompile::term_el& x, const WQLCompile::term_el& y)
00066 {
00067 return !(x == y);
00068 }
00069
00070
00071
00072 WQLCompile::stack_el
00073 WQLCompile::eval_el::getFirst()
00074 {
00075 return stack_el(opn1, is_terminal1);
00076 }
00077 WQLCompile::stack_el
00078 WQLCompile::eval_el::getSecond()
00079 {
00080 return stack_el(opn2, is_terminal2);
00081 }
00082 void WQLCompile::eval_el::setFirst(const WQLCompile::stack_el s)
00083 {
00084 opn1 = s.opn;
00085 is_terminal1 = s.type;
00086 }
00087 void WQLCompile::eval_el::setSecond(const WQLCompile::stack_el s)
00088 {
00089 opn2 = s.opn;
00090 is_terminal2 = s.type;
00091 }
00092 void WQLCompile::eval_el::assign_unary_to_first(const WQLCompile::eval_el & assignee)
00093 {
00094 opn1 = assignee.opn1;
00095 is_terminal1 = assignee.is_terminal1;
00096 }
00097 void WQLCompile::eval_el::assign_unary_to_second(const WQLCompile::eval_el & assignee)
00098 {
00099 opn2 = assignee.opn1;
00100 is_terminal2 = assignee.is_terminal1;
00101 }
00102
00103
00104 void WQLCompile::eval_el::order()
00105 {
00106 if ((is_terminal1 == EVAL_HEAP) && (is_terminal2 == EVAL_HEAP))
00107 {
00108 if (opn2 > opn1)
00109 {
00110 std::swap(opn1, opn2);
00111 }
00112 }
00113 else if ((is_terminal1 != EVAL_HEAP) && (is_terminal2 == EVAL_HEAP))
00114 {
00115 if (opn2 > opn1)
00116 {
00117 std::swap(opn1, opn2);
00118 std::swap(is_terminal1, is_terminal2);
00119 }
00120 }
00121 }
00122
00123
00124
00125 template<class T>
00126 inline static bool _Compare(const T& x, const T& y, WQLOperation op)
00127 {
00128 switch (op)
00129 {
00130 case WQL_EQ:
00131 return x == y;
00132 case WQL_NE:
00133 return x != y;
00134 case WQL_LT:
00135 return x < y;
00136 case WQL_LE:
00137 return x <= y;
00138 case WQL_GT:
00139 return x > y;
00140 case WQL_GE:
00141 return x >= y;
00142 default:
00143 OW_ASSERT(0);
00144 }
00145 return false;
00146 }
00147 static bool _Evaluate(
00148 const WQLOperand& lhs,
00149 const WQLOperand& rhs,
00150 WQLOperation op)
00151 {
00152 switch (lhs.getType())
00153 {
00154 case WQLOperand::NULL_VALUE:
00155 {
00156
00157
00158 return !(op == WQL_EQ) ^ (rhs.getType() == WQLOperand::NULL_VALUE);
00159 break;
00160 }
00161 case WQLOperand::INTEGER_VALUE:
00162 {
00163 return _Compare(
00164 lhs.getIntegerValue(),
00165 rhs.getIntegerValue(),
00166 op);
00167 }
00168 case WQLOperand::DOUBLE_VALUE:
00169 {
00170 return _Compare(
00171 lhs.getDoubleValue(),
00172 rhs.getDoubleValue(),
00173 op);
00174 }
00175 case WQLOperand::BOOLEAN_VALUE:
00176 {
00177 return _Compare(
00178 lhs.getBooleanValue(),
00179 rhs.getBooleanValue(),
00180 op);
00181 }
00182 case WQLOperand::STRING_VALUE:
00183 {
00184 return _Compare(
00185 lhs.getStringValue(),
00186 rhs.getStringValue(),
00187 op);
00188 }
00189 default:
00190 OW_ASSERT(0);
00191 }
00192 return false;
00193 }
00194
00195
00196
00197 WQLCompile::WQLCompile()
00198 {
00199 }
00200 WQLCompile::WQLCompile(const WQLSelectStatement & wqs)
00201 {
00202 compile(&wqs);
00203 }
00204 WQLCompile::~WQLCompile()
00205 {
00206 }
00207 void WQLCompile::compile(const WQLSelectStatement * wqs)
00208 {
00209 if (!wqs->hasWhereClause())
00210 {
00211 return;
00212 }
00213 _tableau.clear();
00214 _buildEvalHeap(wqs);
00215 _pushNOTDown();
00216 _factoring();
00217 Array<stack_el> disj;
00218 _gatherDisj(disj);
00219 if (disj.size() == 0)
00220 {
00221 if (terminal_heap.size() > 0)
00222 {
00223
00224 disj.append(stack_el(0, TERMINAL_HEAP));
00225 }
00226 }
00227
00228 for (UInt32 i=0, n =disj.size(); i< n; i++)
00229 {
00230 TableauRow tr;
00231 Array<stack_el> conj;
00232 if (disj[i].type == EVAL_HEAP)
00233 {
00234 _gatherConj(conj, disj[i]);
00235 for ( UInt32 j=0, m = conj.size(); j < m; j++)
00236 {
00237 tr.append(terminal_heap[conj[j].opn]);
00238 }
00239 }
00240 else
00241 {
00242 tr.append(terminal_heap[disj[i].opn]);
00243 }
00244 _tableau.append(tr);
00245 }
00246 eval_heap.clear();
00247
00248 _sortTableau();
00249 }
00250 bool WQLCompile::evaluate(const WQLPropertySource& source) const
00251 {
00252 bool b = false;
00253 WQLOperand lhs, rhs;
00254 UInt32 tableauSize = _tableau.size();
00255 if (tableauSize == 0)
00256 {
00257 return true;
00258 }
00259 for (UInt32 i = 0; i < tableauSize; i++)
00260 {
00261 TableauRow tr = _tableau[i];
00262 for (UInt32 j=0,m = tr.size(); j < m; j++)
00263 {
00264 if (tr[j].op == WQL_ISA)
00265 {
00266 String propertyName = tr[j].opn1.getPropertyName();
00267 String className;
00268 if (tr[j].opn2.getType() == WQLOperand::PROPERTY_NAME)
00269 {
00270 className = tr[j].opn2.getPropertyName();
00271 }
00272 else
00273 {
00274 className = tr[j].opn2.getStringValue();
00275 }
00276 b = source.evaluateISA(propertyName, className);
00277 }
00278 else
00279 {
00280 lhs = tr[j].opn1;
00281 WQLCompile::_ResolveProperty(lhs,source);
00282 rhs = tr[j].opn2;
00283 WQLCompile::_ResolveProperty(rhs,source);
00284 if (rhs.getType() != lhs.getType())
00285 {
00286 OWBI1_THROW(TypeMismatchException, Format("Type mismatch: lhs: %1 rhs: %2", lhs.toString(), rhs.toString()).c_str());
00287 }
00288 if (!_Evaluate(lhs, rhs, tr[j].op))
00289 {
00290 b = false;
00291 break;
00292 }
00293 else
00294 {
00295 b = true;
00296 }
00297 }
00298 }
00299
00300 if (b)
00301 {
00302 return true;
00303 }
00304 }
00305 return false;
00306 }
00307 void WQLCompile::print(std::ostream& ostr)
00308 {
00309 for (UInt32 i=0, n=eval_heap.size();i < n;i++)
00310 {
00311 WQLOperation wop = eval_heap[i].op;
00312 if (wop == WQL_DO_NOTHING)
00313 {
00314 continue;
00315 }
00316 ostr << "Eval element " << i << ": ";
00317 if (eval_heap[i].is_terminal1 == TERMINAL_HEAP)
00318 {
00319 ostr << "T(";
00320 }
00321 else if (eval_heap[i].is_terminal1 == EVAL_HEAP)
00322 {
00323 ostr << "E(";
00324 }
00325 else
00326 {
00327 ostr << "O(";
00328 }
00329 ostr << eval_heap[i].opn1 << ") ";
00330 ostr << WQLOperationToString(eval_heap[i].op);
00331 if (eval_heap[i].is_terminal2 == TERMINAL_HEAP)
00332 {
00333 ostr << " T(";
00334 }
00335 else if (eval_heap[i].is_terminal2 == EVAL_HEAP)
00336 {
00337 ostr << "E(";
00338 }
00339 else
00340 {
00341 ostr << "O(";
00342 }
00343 ostr << eval_heap[i].opn2 << ")" << std::endl;
00344 }
00345 for (UInt32 i=0, n=terminal_heap.size();i < n;i++)
00346 {
00347 ostr << "Terminal expression " << i << ": ";
00348 ostr << terminal_heap[i].opn1.toString() << " ";
00349 ostr << WQLOperationToString(terminal_heap[i].op) << " "
00350 << terminal_heap[i].opn2.toString() << std::endl;
00351 }
00352 }
00353 void WQLCompile::printTableau(std::ostream& ostr)
00354 {
00355 for (UInt32 i=0, n = _tableau.size(); i < n; i++)
00356 {
00357 ostr << "Tableau " << i << std::endl;
00358 TableauRow tr = _tableau[i];
00359 for (UInt32 j=0, m = tr.size(); j < m; j++)
00360 {
00361 ostr << tr[j].opn1.toString() << " ";
00362 ostr << WQLOperationToString(tr[j].op) << " "
00363 << tr[j].opn2.toString() << std::endl;
00364 }
00365 }
00366 }
00367 void WQLCompile::_buildEvalHeap(const WQLSelectStatement * wqs)
00368 {
00369 std::stack<stack_el> stack;
00370 for (UInt32 i = 0, n = wqs->_operStack.size(); i < n; i++)
00371 {
00372 const WQLSelectStatement::OperandOrOperation& curItem = wqs->_operStack[i];
00373 if (curItem.m_type == WQLSelectStatement::OperandOrOperation::OPERAND)
00374 {
00375
00376 stack.push(stack_el(i, OPERAND));
00377 }
00378 else
00379 {
00380 WQLOperation op = curItem.m_operation;
00381
00382 switch (op)
00383 {
00384
00385 case WQL_NOT:
00386 {
00387 OW_ASSERT(stack.size() >= 1);
00388
00389 stack_el op1 = stack.top();
00390
00391
00392 eval_heap.append(eval_el(false, op, op1.opn, op1.type,
00393 -1, TERMINAL_HEAP));
00394
00395 stack.top() = stack_el(eval_heap.size()-1, EVAL_HEAP);
00396
00397 break;
00398 }
00399
00400
00401 case WQL_OR:
00402 case WQL_AND:
00403 case WQL_EQ:
00404 case WQL_NE:
00405 case WQL_LT:
00406 case WQL_LE:
00407 case WQL_GT:
00408 case WQL_GE:
00409 case WQL_ISA:
00410 {
00411 OW_ASSERT(stack.size() >= 2);
00412
00413 stack_el op2 = stack.top();
00414 stack.pop();
00415
00416 stack_el op1 = stack.top();
00417 if (op1.type == OPERAND && op2.type == OPERAND)
00418 {
00419 OW_ASSERT(op1.type == OPERAND);
00420 OW_ASSERT(wqs->_operStack[op1.opn].m_type == WQLSelectStatement::OperandOrOperation::OPERAND);
00421 WQLOperand lhs = wqs->_operStack[op1.opn].m_operand;
00422 OW_ASSERT(op2.type == OPERAND);
00423 OW_ASSERT(wqs->_operStack[op2.opn].m_type == WQLSelectStatement::OperandOrOperation::OPERAND);
00424 WQLOperand rhs = wqs->_operStack[op2.opn].m_operand;
00425 terminal_heap.push_back(term_el(false, op, lhs, rhs));
00426 stack.top() = stack_el(terminal_heap.size()-1, TERMINAL_HEAP);
00427 }
00428 else
00429 {
00430
00431 eval_heap.append(eval_el(false, op, op1.opn, op1.type,
00432 op2.opn , op2.type));
00433 stack.top() = stack_el(eval_heap.size()-1, EVAL_HEAP);
00434 }
00435
00436 break;
00437 }
00438 case WQL_DO_NOTHING:
00439 {
00440 OW_ASSERT(0);
00441 break;
00442 }
00443 }
00444 }
00445 }
00446 OW_ASSERT(stack.size() == 1);
00447 }
00448 void WQLCompile::_pushNOTDown()
00449 {
00450 for (Int32 i=eval_heap.size()-1; i >= 0; i--)
00451 {
00452 bool _found = false;
00453
00454
00455 eval_heap[i].order();
00456
00457 if (eval_heap[i].op == WQL_NOT)
00458 {
00459
00460 eval_heap[i].op = WQL_DO_NOTHING;
00461
00462
00463 for (Int32 j=eval_heap.size()-1; j > i;j--)
00464 {
00465
00466 if ((eval_heap[j].is_terminal1 == EVAL_HEAP) && (eval_heap[j].opn1 == i))
00467 {
00468 eval_heap[j].assign_unary_to_first(eval_heap[i]);
00469 }
00470
00471 if ((eval_heap[j].is_terminal2 == EVAL_HEAP) && (eval_heap[j].opn2 == i))
00472 {
00473 eval_heap[j].assign_unary_to_second(eval_heap[i]);
00474 }
00475 }
00476
00477 if (eval_heap[i].mark)
00478 {
00479 eval_heap[i].mark = false;
00480 }
00481 else
00482 {
00483 _found = true;
00484 }
00485
00486 }
00487
00488 if (eval_heap[i].mark)
00489 {
00490
00491
00492 eval_heap[i].mark=false;
00493 if (eval_heap[i].op == WQL_OR)
00494 {
00495 eval_heap[i].op = WQL_AND;
00496 }
00497 else if (eval_heap[i].op == WQL_AND)
00498 {
00499 eval_heap[i].op = WQL_OR;
00500 }
00501
00502 _found = true;
00503 }
00504
00505 if (_found)
00506 {
00507
00508 int j = eval_heap[i].opn1;
00509 if (eval_heap[i].is_terminal1 == TERMINAL_HEAP)
00510 {
00511
00512 terminal_heap[j].negate();
00513 }
00514 else if (eval_heap[i].is_terminal1 == EVAL_HEAP)
00515 {
00516 eval_heap[j].mark = !(eval_heap[j].mark);
00517 }
00518
00519 if ((j = eval_heap[i].opn2) >= 0)
00520 {
00521 if (eval_heap[i].is_terminal2 == TERMINAL_HEAP)
00522 {
00523
00524 terminal_heap[j].negate();
00525 }
00526 else if (eval_heap[i].is_terminal2 == EVAL_HEAP)
00527 {
00528 eval_heap[j].mark = !(eval_heap[j].mark);
00529 }
00530 }
00531 }
00532 }
00533 }
00534 void WQLCompile::_factoring()
00535 {
00536 int i = 0,n = eval_heap.size();
00537
00538 while (i < n)
00539 {
00540 int _found = 0;
00541 int index = 0;
00542
00543 if (eval_heap[i].op == WQL_AND)
00544 {
00545 if (eval_heap[i].is_terminal1 == EVAL_HEAP)
00546 {
00547 index = eval_heap[i].opn1;
00548 if (eval_heap[index].op == WQL_OR)
00549 {
00550 _found = 1;
00551 }
00552 }
00553 if ((_found == 0) && (eval_heap[i].is_terminal2 == EVAL_HEAP))
00554 {
00555 index = eval_heap[i].opn2;
00556 if (eval_heap[index].op == WQL_OR)
00557 {
00558 _found = 2;
00559 }
00560 }
00561 if (_found != 0)
00562 {
00563 stack_el s;
00564 if (_found == 1)
00565 {
00566 s = eval_heap[i].getSecond();
00567 }
00568 else
00569 {
00570 s = eval_heap[i].getFirst();
00571 }
00572
00573 eval_el evl(false, WQL_OR, i+1, EVAL_HEAP, i, EVAL_HEAP);
00574 if (i < static_cast<int>(eval_heap.size())-1)
00575 {
00576 eval_heap.insert(i+1, evl);
00577 }
00578 else
00579 {
00580 eval_heap.append(evl);
00581 }
00582 eval_heap.insert(i+1, evl);
00583 for (int j=eval_heap.size()-1; j > i + 2; j--)
00584 {
00585
00586
00587 if ((eval_heap[j].is_terminal1 == EVAL_HEAP) &&
00588 (eval_heap[j].opn1 >= i))
00589 {
00590 eval_heap[j].opn1 += 2;
00591 }
00592 if ((eval_heap[j].is_terminal2 == EVAL_HEAP) &&
00593 (eval_heap[j].opn2 >= i))
00594 {
00595 eval_heap[j].opn2 += 2;
00596 }
00597 }
00598 n+=2;
00599
00600
00601 eval_heap[i+1].mark = false;
00602 eval_heap[i+1].op = WQL_AND;
00603 eval_heap[i+1].setFirst(s);
00604 eval_heap[i+1].setSecond( eval_heap[index].getFirst());
00605 eval_heap[i+1].order();
00606
00607 eval_heap[i].mark = false;
00608 eval_heap[i].op = WQL_AND;
00609 eval_heap[i].setFirst(s);
00610 eval_heap[i].setSecond( eval_heap[index].getSecond());
00611 eval_heap[i].order();
00612
00613
00614 i--;
00615 }
00616 }
00617 i++;
00618 }
00619 }
00620 void WQLCompile::_gatherDisj(Array<stack_el>& stk)
00621 {
00622 _gather(stk, stack_el(0, TERMINAL_HEAP), true);
00623 }
00624 void WQLCompile::_gatherConj(Array<stack_el>& stk, stack_el sel)
00625 {
00626 _gather(stk, sel, false);
00627 }
00628 void WQLCompile::_gather(Array<stack_el>& stk, stack_el sel, bool or_flag)
00629 {
00630 UInt32 i = 0;
00631 stk.empty();
00632 if ((i = eval_heap.size()) == 0)
00633 {
00634 return;
00635 }
00636 while (eval_heap[i-1].op == WQL_DO_NOTHING)
00637 {
00638 eval_heap.remove(i-1);
00639 i--;
00640 if (i == 0)
00641 {
00642 return;
00643 }
00644 }
00645 if (or_flag)
00646 {
00647 stk.append(stack_el(i-1, EVAL_HEAP));
00648 }
00649 else
00650 {
00651 if (sel.type != EVAL_HEAP)
00652 {
00653 return;
00654 }
00655 stk.append(sel);
00656 }
00657 i = 0;
00658 while (i<stk.size())
00659 {
00660 int k = stk[i].opn;
00661 if ((k < 0) || (stk[i].type != EVAL_HEAP))
00662 {
00663 i++;
00664 }
00665 else
00666 {
00667 if ( ((eval_heap[k].op != WQL_OR) && (or_flag)) ||
00668 ((eval_heap[k].op != WQL_AND) && (!or_flag)) )
00669 {
00670 i++;
00671 }
00672 else
00673 {
00674
00675 stk[i] = eval_heap[k].getSecond();
00676 stk.insert(i, eval_heap[k].getFirst());
00677 if (or_flag)
00678 {
00679 eval_heap[k].op = WQL_DO_NOTHING;
00680 }
00681 }
00682 }
00683 }
00684 }
00685 void WQLCompile::_sortTableau()
00686 {
00687
00688
00689 for (UInt32 i = 0, n = _tableau.size(); i < n; i++)
00690 {
00691 TableauRow tr = _tableau[i];
00692 WQLOperand wop;
00693 WQLOperation wopt;
00694
00695
00696 for (UInt32 j = 0, m = tr.size(); j < m; j++)
00697 {
00698 if (tr[j].opn2.getType() == WQLOperand::PROPERTY_NAME)
00699 {
00700 if (tr[j].opn1.getType() != WQLOperand::PROPERTY_NAME)
00701 {
00702 wop = tr[j].opn1;
00703 tr[j].opn1 = tr[j].opn2;
00704 tr[j].opn2 = wop;
00705
00706 switch (tr[j].op)
00707 {
00708 case WQL_LT: tr[j].op = WQL_GT; break;
00709 case WQL_GT: tr[j].op = WQL_LT; break;
00710 case WQL_LE: tr[j].op = WQL_GE; break;
00711 case WQL_GE: tr[j].op = WQL_LE; break;
00712 default: break;
00713 }
00714 }
00715 }
00716 }
00717 String key1, key2;
00718
00719 for (UInt32 j = 0, m = tr.size(); j < m; j++)
00720 {
00721 if ((tr[j].opn1.getType() == WQLOperand::PROPERTY_NAME)
00722 && (tr[j].opn2.getType() != WQLOperand::PROPERTY_NAME))
00723 {
00724 key1 = tr[j].opn1.getPropertyName();
00725 }
00726 else
00727 {
00728 key1.erase();
00729 }
00730 for (UInt32 k = j; k < m; k++)
00731 {
00732 if ((tr[k].opn1.getType() == WQLOperand::PROPERTY_NAME)
00733 && (tr[k].opn2.getType() != WQLOperand::PROPERTY_NAME))
00734 {
00735 key2 = tr[k].opn1.getPropertyName();
00736 }
00737 else
00738 {
00739 key2.erase();
00740 }
00741 if (key1 > key2)
00742 {
00743 wop = tr[j].opn1;
00744 tr[j].opn1 = tr[k].opn1;
00745 tr[k].opn1 = wop;
00746 wop = tr[j].opn2;
00747 tr[j].opn2 = tr[k].opn2;
00748 tr[k].opn2 = wop;
00749 wopt = tr[j].op;
00750 tr[j].op = tr[k].op;
00751 tr[k].op = wopt;
00752 }
00753 }
00754 }
00755
00756 tr.erase(std::unique(tr.begin(), tr.end()), tr.end());
00757
00758 _tableau[i] = tr;
00759 }
00760 }
00761
00762 }
00763