cql2dnf.cpp

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

//%2006////////////////////////////////////////////////////////////////////////
//
// Copyright (c) 2000, 2001, 2002 BMC Software; Hewlett-Packard Development
// Company, L.P.; IBM Corp.; The Open Group; Tivoli Systems.
// Copyright (c) 2003 BMC Software; Hewlett-Packard Development Company, L.P.;
// IBM Corp.; EMC Corporation, The Open Group.
// Copyright (c) 2004 BMC Software; Hewlett-Packard Development Company, L.P.;
// IBM Corp.; EMC Corporation; VERITAS Software Corporation; The Open Group.
// Copyright (c) 2005 Hewlett-Packard Development Company, L.P.; IBM Corp.;
// EMC Corporation; VERITAS Software Corporation; The Open Group.
// Copyright (c) 2006 Hewlett-Packard Development Company, L.P.; IBM Corp.;
// EMC Corporation; Symantec Corporation; The Open Group.
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to
// deal in the Software without restriction, including without limitation the
// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
// sell copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
// 
// THE ABOVE COPYRIGHT NOTICE AND THIS PERMISSION NOTICE SHALL BE INCLUDED IN
// ALL COPIES OR SUBSTANTIAL PORTIONS OF THE SOFTWARE. THE SOFTWARE IS PROVIDED
// "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT
// LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
// PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
// ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//
//==============================================================================
//
// Author:      Markus Mueller ([e-mail])
//
// Modified By: Humberto Rivero ([e-mail])
//
//%/////////////////////////////////////////////////////////////////////////////


#include "Cql2Dnf.h"
#include <Pegasus/Common/Stack.h>
#include <Pegasus/Common/Tracer.h>

PEGASUS_USING_STD;
PEGASUS_NAMESPACE_BEGIN

#define PEGASUS_ARRAY_T term_el
# include <Pegasus/Common/ArrayImpl.h>
#undef PEGASUS_ARRAY_T

#define PEGASUS_ARRAY_T eval_el
# include <Pegasus/Common/ArrayImpl.h>
#undef PEGASUS_ARRAY_T

#define PEGASUS_ARRAY_T stack_el
# include <Pegasus/Common/ArrayImpl.h>
#undef PEGASUS_ARRAY_T

//
// Terminal element methods 
//

void term_el::negate()
{
   NOT = true;
};

//
// Evaluation heap element methods
//
stack_el eval_el::getFirst() 
{ 
   return stack_el(opn1, is_terminal1);
}

stack_el eval_el::getSecond()
{
   return stack_el(opn2, is_terminal2);
}

void eval_el::setFirst(const stack_el s)
{
     opn1 = s.opn;
     is_terminal1 = s.is_terminal;
}

void eval_el::setSecond(const stack_el s)
{
    opn2 = s.opn;
    is_terminal2 = s.is_terminal;
}

void eval_el::assign_unary_to_first(const eval_el & assignee)
{
    opn1 = assignee.opn1;
    is_terminal1 = assignee.is_terminal1;
}

void eval_el::assign_unary_to_second(const eval_el & assignee)
{
    opn2 = assignee.opn1;
    is_terminal2 = assignee.is_terminal1;
}

// Ordering operators, so that op1 > op2 for all non-terminals
// and terminals appear in the second operand first
void eval_el::order(void)
{
    int k;
    if ((!is_terminal1) && (!is_terminal2))
        if ((k = opn2) > opn1)
        {
            opn2 = opn1;
            opn1 =  k;
        }
    else if ((is_terminal1) && (!is_terminal2))
        if ((k = opn2) > opn1)
        {
            opn2 = opn1;
            opn1 =  k;
            is_terminal1 = false;
            is_terminal2 = true;
        }
}
/*
static bool operator==(const term_el& x, const term_el& y)
{
	return x._simplePredicate == y._simplePredicate; 
}
*/
//
// CQL Compiler methods
//
/*    
Cql2Dnf::Cql2Dnf() 
{
    eval_heap.reserveCapacity(16);
    terminal_heap.reserveCapacity(16);
}

Cql2Dnf::Cql2Dnf(CQLSelectStatement & cqs)
{
    eval_heap.reserveCapacity(16);
    terminal_heap.reserveCapacity(16);
    compile(&cqs);
}

Cql2Dnf::Cql2Dnf(CQLSelectStatement * cqs)
{
    eval_heap.reserveCapacity(16);
    terminal_heap.reserveCapacity(16);
    compile(cqs);
}
*/
Cql2Dnf::Cql2Dnf(CQLPredicate& topLevel){
    eval_heap.reserveCapacity(16);
    terminal_heap.reserveCapacity(16);
    compile(topLevel);
}

Cql2Dnf::~Cql2Dnf() {}
/*
void Cql2Dnf::compile(CQLSelectStatement * cqs){
	CQLPredicate topLevel = cqs->getPredicate();
	compile(topLevel);
}
*/
void Cql2Dnf::compile(CQLPredicate& topLevel)
{
	PEG_METHOD_ENTER(TRC_CQL, "Cql2Dnf::compile");

    _strip_ops_operands(topLevel);
    _buildEvalHeap();
    _pushNOTDown();
    _factoring();
    _construct();
    eval_heap.clear();

	PEG_METHOD_EXIT();
}

void Cql2Dnf::_buildEvalHeap()
{
	PEG_METHOD_ENTER(TRC_CQL, "Cql2Dnf::_buildEvalHeap");

    Stack<stack_el> stack;

    // Counter for Operands
    Uint32 j = 0;

    for (Uint32 i = 0, n = _operations.size(); i < n; i++)
    {
        OperationType op = _operations[i];

        switch (op)
        {
            case CQL_OR:
            case CQL_AND:
            {
                PEGASUS_ASSERT(stack.size() >= 2);

                stack_el op1 = stack.top();
                stack.pop();

                stack_el op2 = stack.top();

                // generate Eval expression
                eval_heap.append(eval_el(0, op , op1.opn, op1.is_terminal,
                                 op2.opn , op2.is_terminal));

                stack.top() = stack_el(eval_heap.size()-1, false);

                break;
            }

            case CQL_NOT:
            {
                PEGASUS_ASSERT(stack.size() >= 1);

                stack_el op1 = stack.top();

                // generate Eval expression
                eval_heap.append(eval_el(0, op , op1.opn, op1.is_terminal,
                                 -1, true));

                stack.top() = stack_el(eval_heap.size()-1, false);

                break;
            }

            case CQL_EQ: 
            case CQL_NE:
            case CQL_LT:
            case CQL_LE:
            case CQL_GT:
            case CQL_GE:
				case CQL_ISA:
				case CQL_LIKE:
            {
                PEGASUS_ASSERT(_operands.size() >= 2);

                CQLExpression lhs = _operands[j++];

                CQLExpression rhs = _operands[j++];

		CQLSimplePredicate sp(lhs,rhs,_convertOpType(op));
                terminal_heap.push(term_el(false, sp));

                stack.push(stack_el(terminal_heap.size()-1, true));

                break;
            }

            case CQL_IS_NULL:
            {
                PEGASUS_ASSERT(_operands.size() >= 1);
                CQLExpression expression = _operands[j++];
		CQLSimplePredicate dummy(expression,IS_NULL);
                terminal_heap.push(term_el(false, dummy));

                stack.push(stack_el(terminal_heap.size()-1, true));

                break;
            }

            case CQL_IS_NOT_NULL:
            {
                PEGASUS_ASSERT(_operands.size() >= 1);
                CQLExpression expression = _operands[j++];
                CQLSimplePredicate dummy(expression,IS_NOT_NULL);
                terminal_heap.push(term_el(false, dummy));

                stack.push(stack_el(terminal_heap.size()-1, true));

                break;
            }
	    case CQL_NOOP:
	    default: break;
        }
    }

    PEGASUS_ASSERT(stack.size() == 1);

    PEG_METHOD_EXIT();
}

void Cql2Dnf::_pushNOTDown()
{
    PEG_METHOD_ENTER(TRC_CQL, "Cql2Dnf::_pushNOTDown");

    for (int i=eval_heap.size()-1; i >= 0; i--)
    {
        Boolean _found = false;

        // Order all operators, so that op1 > op2 for non-terminals
        // and terminals appear as second operand

        eval_heap[i].order();

        // First solve the unary NOT operator

        if (eval_heap[i].op == CQL_NOT)
       {
            // This serves as the equivalent of an empty operator
            eval_heap[i].op = CQL_NOOP;

            // Substitute this expression in all higher order eval statements
            // so that this node becomes disconnected from the tree

            for (int j=eval_heap.size()-1; j > i;j--)
            {
               // Test first operand
               if ((!eval_heap[j].is_terminal1) && (eval_heap[j].opn1 == i))

                   eval_heap[j].assign_unary_to_first(eval_heap[i]);

               // Test second operand
               if ((!eval_heap[j].is_terminal2) && (eval_heap[j].opn2 == i))

                   eval_heap[j].assign_unary_to_second(eval_heap[i]);
            }

            // Test: Double NOT created by moving down

            if (eval_heap[i].mark)
               eval_heap[i].mark = false;
            else
               _found = true;
            // else indicate a pending NOT to be pushed down further
        }

        // Simple NOT created by moving down

        if (eval_heap[i].mark)
        {
            // Remove the mark, indicate a pending NOT to be pushed down
            // further and switch operators (AND / OR)

            eval_heap[i].mark=false;
            if (eval_heap[i].op == CQL_OR) eval_heap[i].op = CQL_AND;
            else if (eval_heap[i].op == CQL_AND) eval_heap[i].op = CQL_OR;

            // NOT operator is already ruled out
            _found = true;
        }

        // Push a pending NOT further down
        if (_found)
        {
             // First operand

             int j = eval_heap[i].opn1;
             if (eval_heap[i].is_terminal1)
                 // Flip NOT mark
                 terminal_heap[j].negate();
             else
                 eval_heap[j].mark = !(eval_heap[j].mark);

             //Second operand (if it exists)

             if ((j = eval_heap[i].opn2) >= 0)
             {
                 if (eval_heap[i].is_terminal2)
                     // Flip NOT mark
                     terminal_heap[j].negate();
                 else
                     eval_heap[j].mark = !(eval_heap[j].mark);
             }
        }
    }
	PEG_METHOD_EXIT();
}

void Cql2Dnf::_factoring(void)
{
	PEG_METHOD_ENTER(TRC_CQL, "Cql2Dnf::_factoring");

    int i = 0,n = eval_heap.size();
    //for (int i=eval_heap.size()-1; i >= 0; i--)
    while (i < n)
    {
        int _found = 0;
        int index = 0;

        // look for expressions (A | B) & C  ---> A & C | A & B
        if (eval_heap[i].op == CQL_AND)
        {
            if (!eval_heap[i].is_terminal1)
            {
                index = eval_heap[i].opn1; // remember the index
                if (eval_heap[index].op == CQL_OR) _found = 1;
            }

            if ((_found == 0) && (!eval_heap[i].is_terminal2))
            {
                index = eval_heap[i].opn2; // remember the index
                if (eval_heap[index].op == CQL_OR) _found = 2;
            }

            if (_found != 0)
            {
                 //int u1,u1_t,u2,u2_t,u3,u3_t;
                 stack_el s;

                 if (_found == 1)
                     s = eval_heap[i].getSecond();
                 else
                     s = eval_heap[i].getFirst();

                 // insert two new expression before entry i
                 eval_el evl;

                 evl = eval_el(false, CQL_OR, i+1, false, i, false);
                 if ((Uint32 )i < eval_heap.size()-1)
                     eval_heap.insert(i+1, evl);
                 else
                     eval_heap.append(evl);
                 eval_heap.insert(i+1, evl);