cql2dnf.cpp

Pegasus is an open-source implementationof the DMTF CIM and WBEM standards. It is designed to be por

                 for (int j=eval_heap.size()-1; j > i + 2; j--)
                 {
                     //eval_heap[j] = eval_heap[j-2];

                     // adjust pointers

                     if ((!eval_heap[j].is_terminal1)&&
                         (eval_heap[j].opn1 >= i))
                         eval_heap[j].opn1 += 2;
                     if ((!eval_heap[j].is_terminal2)&&
                         (eval_heap[j].opn2 >= i))
                         eval_heap[j].opn2 += 2;
                 }

                 n+=2; // increase size of array

                 // generate the new expressions : new OR expression


                 // first new AND expression
                 eval_heap[i+1].mark = false;
                 eval_heap[i+1].op = CQL_AND;
                 eval_heap[i+1].setFirst(s);
                 eval_heap[i+1].setSecond( eval_heap[index].getFirst());
                 eval_heap[i+1].order();


                 // second new AND expression
                 eval_heap[i].mark = false;
                 eval_heap[i].op = CQL_AND;
                 eval_heap[i].setFirst(s);
                 eval_heap[i].setSecond( eval_heap[index].getSecond());
                 eval_heap[i].order();

                 // mark the indexed expression as inactive
                 //eval_heap[index].op = WQL_IS_TRUE; possible disconnects
                 i--;

            } /* endif _found > 0 */

        } /* endif found AND operator */

        i++; // increase pointer
    }

	PEG_METHOD_EXIT();
}

void Cql2Dnf::_strip_ops_operands(CQLPredicate& topLevel)
{
	PEG_METHOD_ENTER(TRC_CQL, "Cql2Dnf::_strip_ops_operands");
	//
	// depth first search for all operations and operands
	// extract operations and operands and store in respective arrays for later processing
	//
	_destruct(topLevel);
	if(topLevel.getInverted()){
        	_operations.append(CQL_NOT);
        }
	PEG_METHOD_EXIT();
}

OperationType Cql2Dnf::_convertOpType(ExpressionOpType op){
	switch(op){
		case EQ: return CQL_EQ;
		case NE: return CQL_NE;
		case GT: return CQL_GT;
		case LT: return CQL_LT;
		case GE: return CQL_GE;
		case LE: return CQL_LE;
		case IS_NULL: return CQL_IS_NULL;
		case IS_NOT_NULL: return CQL_IS_NOT_NULL;
		case ISA: return CQL_ISA;
		case LIKE: return CQL_LIKE;
		default: return CQL_NOOP;
	}
}

ExpressionOpType Cql2Dnf::_convertOpType(OperationType op){
        switch(op){
                case CQL_EQ: return EQ;
                case CQL_NE: return NE;
                case CQL_GT: return GT;
                case CQL_LT: return LT;
                case CQL_GE: return GE;
                case CQL_LE: return LE;
                case CQL_IS_NULL: return IS_NULL; 
                case CQL_IS_NOT_NULL: return IS_NOT_NULL;
					 case CQL_ISA: return ISA;
					 case CQL_LIKE: return LIKE;
                default: return EQ; // should never get here
        }
	PEGASUS_UNREACHABLE(return EQ;) // should never get here
}

void Cql2Dnf::_destruct(CQLPredicate& _p){
	if(_p.isSimple()){
		CQLSimplePredicate _sp = _p.getSimplePredicate();
		_operations.append(_convertOpType(_sp.getOperation()));
		_operands.append(_sp.getLeftExpression());
		if((_operations[_operations.size()-1] != CQL_IS_NULL) && (_operations[_operations.size()-1] != CQL_IS_NOT_NULL))
			_operands.append(_sp.getRightExpression());
	}
	else{
		Array<CQLPredicate> _preds = _p.getPredicates();
		Array<BooleanOpType> _boolops = _p.getOperators();
		for(Uint32 i=0;i<_preds.size();i++){
			_destruct(_preds[i]);
			if(_preds[i].getInverted()){
				_operations.append(CQL_NOT);
			}
			if(i > 0){
				if(_boolops[i-1] == AND){
					_operations.append(CQL_AND);
				}
				if(_boolops[i-1] == OR){
                                        _operations.append(CQL_OR);
                                }
			}
		}
	}
}

void Cql2Dnf::_construct(){

	PEG_METHOD_ENTER(TRC_CQL, "Cql2Dnf::_construct");
	//
	// Each eval_el on the eval heap contains all the information needed to make a CQLPredicate.  
	// We will build a CQLPredicate for every element in the eval heap. So there is a 1 to 1 correspondence
	// between elements in the eval heap and elements in the CQLPredicate array used below.  
	// The first eval_el on the eval heap will always contain at least one terminal if the operation is a NOT
	// or two terminals if the operation is AND or OR.  We are guaranteed to build a CQLPredicate from the first
	// position in the eval_heap array. 
	//
	// The key to the algorithm is the isterminalX flag.  When set to true, we go to the 
	// term_heap and get the CQLSimplePredicate.  When set to false, we go to the _preds array below
	// and get the CQLPredicate.  Since there is a 1 - 1 correspondence, as explained above, the index
	// referred to by eval.opn1 or eval.opn2 is valid into the _preds array.
	//
	// For ANDs and ORs, we need two operands, as explained above, we get those operands
	// from either the term_heap or the _preds array.  For NOTs, we need only 1 operand, and that
	// comes from either the term_heap or the _preds array.
	//
	// When finished, the last element in the _preds array contains the top level CQLPredicate (the rebuilt tree)
	//
	// Example:  a=b^(!c=d v e=f)
	// If the current eval_heap looks like: 
	//	0,NOT,1,True,-1,True [index = 0]
	// 	0,OR,2,True,0,False  [index = 1]
	// 	0,AND,1,False,0,True [index = 2]
	//
	// And the current term_heap looks like:
	//	CQLSimplePredicate(a=b) [index = 0]
	// 	CQLSimplePredicate(c=d) [index = 1]
	//      CQLSimplePredicate(e=f) [index = 0]
	//
	// The _preds array at the end would look like:
	//	CQLPredicate(!c==d)        [index = 0]
	//	CQLPredicate(e==f v !c==d) [index = 1]
	// 	CQLPredicate((e==f v !c==d) ^ a==b) [index = 2]  (the rebuilt tree)
	//

	if(eval_heap.size() > 0){
	   Array<CQLPredicate> _preds;
	   CQLPredicate pred;
	   for(Uint32 i=0;i<eval_heap.size();i++){
		eval_el eval = eval_heap[i];
		if(eval.is_terminal1 && eval.is_terminal2){
			switch(eval.op){
				case CQL_NOT:
           	{
              	_preds.append(CQLPredicate(terminal_heap[eval.opn1]._simplePredicate,true));
					break;
            }
				case CQL_NOOP:
				{
					CQLPredicate p(terminal_heap[eval.opn1]._simplePredicate,false);
					if(terminal_heap[eval.opn1].NOT == true)
					   p.setInverted(true);
					_preds.append(p);
					break;
				}
            case CQL_AND:
            {
					CQLPredicate p;
					CQLPredicate p1(terminal_heap[eval.opn2]._simplePredicate,false);
					if(terminal_heap[eval.opn2].NOT == true)
					   p1.setInverted(true);
					p.appendPredicate(p1);
					CQLPredicate p2(terminal_heap[eval.opn1]._simplePredicate,false);
					if(terminal_heap[eval.opn1].NOT == true)
					   p2.setInverted(true);
					p.appendPredicate(p2,AND);
					_preds.append(p);
					break;
            }
            case CQL_OR:
            {
				   CQLPredicate p;
               CQLPredicate p1(terminal_heap[eval.opn2]._simplePredicate,false);
					if(terminal_heap[eval.opn2].NOT == true)
					   p1.setInverted(true);
               p.appendPredicate(p1);
               CQLPredicate p2(terminal_heap[eval.opn1]._simplePredicate,false);
					if(terminal_heap[eval.opn1].NOT == true)
                  p2.setInverted(true);
               p.appendPredicate(p2,OR);
               _preds.append(p);
               break;
            }
				case CQL_EQ:
                		case CQL_NE:
                		case CQL_GT:
                		case CQL_LT:
                		case CQL_GE: 
                		case CQL_LE:
							case CQL_ISA:
							case CQL_LIKE:
                		case CQL_IS_NULL:
                		case CQL_IS_NOT_NULL: break;
				
			}
		}else if(eval.is_terminal1 && !eval.is_terminal2){
			switch(eval.op){
				case CQL_NOT:
            {
               _preds.append(CQLPredicate(terminal_heap[eval.opn1]._simplePredicate,true));
					break;
            }
				case CQL_NOOP:
            {
               CQLPredicate p(terminal_heap[eval.opn1]._simplePredicate,false);
               if(terminal_heap[eval.opn1].NOT == true)
                  p.setInverted(true);
               _preds.append(p);
               break;
            }
            case CQL_AND:
            {
               CQLPredicate p;
               CQLPredicate p1(terminal_heap[eval.opn1]._simplePredicate,false);
			      if(terminal_heap[eval.opn1].NOT == true)
                  p1.setInverted(true);
               p = _preds[eval.opn2];
               p.appendPredicate(p1,AND);
               _preds.append(p);
               break;
            }
            case CQL_OR:
            {
              CQLPredicate p;
              CQLPredicate p1(terminal_heap[eval.opn1]._simplePredicate,false);
				  if(terminal_heap[eval.opn1].NOT == true)
                 p1.setInverted(true);
              p = _preds[eval.opn2];
              p.appendPredicate(p1,OR);
              _preds.append(p);
              break;
            }
				case CQL_EQ:
                                case CQL_NE:
                                case CQL_GT:
                                case CQL_LT:
                                case CQL_GE:
                                case CQL_LE:
										  case CQL_ISA:
							           case CQL_LIKE:
                                case CQL_IS_NULL:
                                case CQL_IS_NOT_NULL: break;
                               
			}
		}else if(!eval.is_terminal1 && eval.is_terminal2){
         switch(eval.op){
            case CQL_NOT:
            {
				   CQLPredicate p = _preds[eval.opn1];
               p.setInverted(true);
                _preds.append(p);
					break;
            }
				case CQL_NOOP:
            {
               _preds.append(_preds[eval.opn1]);
					break;
            }
            case CQL_AND:
            {
               CQLPredicate p;
               CQLPredicate p1(terminal_heap[eval.opn2]._simplePredicate,false);
				   if(terminal_heap[eval.opn2].NOT == true)
                  p1.setInverted(true);
               p = _preds[eval.opn1];
               p.appendPredicate(p1,AND);
               _preds.append(p);
               break;
            }
            case CQL_OR:
            {
               CQLPredicate p;
               CQLPredicate p1(terminal_heap[eval.opn2]._simplePredicate,false);
				   if(terminal_heap[eval.opn2].NOT == true)
                  p1.setInverted(true);
               p = _preds[eval.opn1];
               p.appendPredicate(p1,OR);
               _preds.append(p);
               break;
            }
				case CQL_EQ:
                                case CQL_NE:
                                case CQL_GT:
                                case CQL_LT:
                                case CQL_GE:
                                case CQL_LE:
										  case CQL_ISA:
										  case CQL_LIKE:
                                case CQL_IS_NULL:
                                case CQL_IS_NOT_NULL: break;
                               
                        }                                                                                                                                    
                }else{ // !eval.is_terminal1 && !eval.is_terminal2
			switch(eval.op){
            case CQL_NOT:
            {
					CQLPredicate p = _preds[eval.opn1];
					p.setInverted(true);
               _preds.append(p);
					break;
            }
			   case CQL_NOOP:
            {
               _preds.append(_preds[eval.opn1]);
					break;
            }
            case CQL_AND:
            {
					CQLPredicate p = _preds[eval.opn2];
               _flattenANDappend(p,AND,_preds[eval.opn1]);
               _preds.append(p);
               break;
            }
            case CQL_OR:
            {
					CQLPredicate p = _preds[eval.opn2];
               _flattenANDappend(p,OR,_preds[eval.opn1]);
               _preds.append(p);
               break;
            }
				case CQL_EQ:
                                case CQL_NE:
                                case CQL_GT:
                                case CQL_LT:
                                case CQL_GE:
                                case CQL_LE:
										  case CQL_ISA:
										  case CQL_LIKE:
                                case CQL_IS_NULL:
                                case CQL_IS_NOT_NULL: break;
                                
                        }

		}
	   } // end for(...)

	   _dnfPredicate = _preds[_preds.size()-1];

	} // end if
	else{ // we just have a CQLSimplePredicate on the terminal_heap
		PEGASUS_ASSERT(terminal_heap.size() == 1);
		_dnfPredicate = CQLPredicate(terminal_heap[0]._simplePredicate,false);
	}

	PEG_METHOD_EXIT();
}

CQLPredicate Cql2Dnf::getDnfPredicate(){
	return _dnfPredicate;
}

CQLPredicate Cql2Dnf::_flattenANDappend(CQLPredicate& topLevel, BooleanOpType op, CQLPredicate& p){

	PEG_METHOD_ENTER(TRC_CQL, "Cql2Dnf::_flattenANDappend");
	//
	// this is to prevent appending complex predicates to the top level predicate
	// the final DNFed predicate must only have simple predicates inside its predicate array
	//
	// example:
	// say P(top level) = A AND B
	// say P1 = C AND D
	// say we need to OR them together
	// we cant call P.appendPredicate(P1,OR) because this creates one more complex predicate layer
	// instead we would:
	// -> get P1s predicates (which should all be simple)
	// -> append its first predicate to P along with the operator passed into us
	// -> at this point we have P = A AND B OR C
	// -> then go through P1s remaining predicates and append them and P1s operators to P
	// -> when finished, we have P = A AND B OR C AND D INSTEAD of having P = A AND B OR P1 where P1 is a complex predicate
	//

	if(!p.isSimple()){
		Array<CQLPredicate> preds = p.getPredicates();
		Array<BooleanOpType> ops = p.getOperators();
		for(Uint32 i=0;i<preds.size();i++){
			if(i==0) topLevel.appendPredicate(preds[i],op);
			else topLevel.appendPredicate(preds[i],ops[i-1]);
		}
	}else{
		topLevel.appendPredicate(p,op);
	}

	PEG_METHOD_EXIT();
	return topLevel;
}

PEGASUS_NAMESPACE_END