1 #

     2 # Copyright (c) 2009 Nokia Corporation and/or its subsidiary(-ies).

     3 # All rights reserved.

     4 # This component and the accompanying materials are made available

     5 # under the terms of "Eclipse Public License v1.0"

     6 # which accompanies this distribution, and is available

     7 # at the URL "http://www.eclipse.org/legal/epl-v10.html".

     8 #

     9 # Initial Contributors:

    10 # Nokia Corporation - initial contribution.

    11 #

    12 # Contributors:

    13 #

    14 # Description: 

    15 # 

    16 

    17 import operator as ops

    18 import logging

    19 import tokenize

    20 from token import ENDMARKER, NAME, ERRORTOKEN

    21 import StringIO

    22 

    23 from cone.public import container

    24 

    25 RELATIONS = {}

    26 

    27 def abstract():

    28     import inspect

    29     caller = inspect.getouterframes(inspect.currentframe())[1][3]

    30     raise NotImplementedError(caller + ' needs to be implemented')

    31 

    32 def get_tokens(tokenstr):

    33     result = []

    34     tokens = []

    35     tokenstr = tokenstr.replace('\r', '')

    36     name_buffer = [] # Temp buffer for reading name tokens

    37     last_epos = None

    38     for toknum, tokval, spos, epos, _  in tokenize.generate_tokens(StringIO.StringIO(unicode(tokenstr)).readline):

    39         #print "toknum: %r, tokval: %r, spos: %r, epos: %r" % (toknum, tokval, spos, epos)

    40         val = tokval.strip('\r\n\t ')

    41         

    42         if toknum == ENDMARKER and name_buffer:

    43             tokens.append(''.join(name_buffer))

    44         

    45         # Ignore whitespace (this ignores also the end marker,

    46         # since its value is empty)

    47         if val == '': continue

    48         

    49         # Put NAME, and ERRORTOKEN tokens through the temp

    50         # buffer

    51         if toknum in (NAME, ERRORTOKEN):

    52             # If this and the previous token in the temp buffer are not adjacent,

    53             # they belong to separate tokens

    54             if name_buffer and spos[1] != last_epos[1]:

    55                 tokens.append(''.join(name_buffer))

    56                 name_buffer = []

    57             

    58             name_buffer.append(val)

    59             last_epos = epos

    60         # Other tokens can just go directly to the token list

    61         else:

    62             if name_buffer:

    63                 tokens.append(''.join(name_buffer))

    64                 name_buffer = []

    65             tokens.append(val)

    66     

    67     while len(tokens) > 0:

    68         val = tokens.pop(0)

    69         # Join the refs with dot in between them to make them dotted refs

    70         if val == '.':

    71             newval = ".".join([result.pop(),tokens.pop(0)])

    72             result.append( newval )

    73         else:

    74             result.append( val )

    75 

    76     return result

    77 

    78 class RelationException(Exception):

    79     pass

    80 

    81 #### The containers are here ####

    82 

    83 

    84 class RelationBase(object):

    85     """

    86     RelationBase defines a base class for all named relations that can be applied between objects. 

    87     e.g. Relation depends, that can be applied in Rule

    88     """

    89     relation_name = "RelationBase"

    90     def __init__(self, data, left, right):

    91         self.description = ""

    92         self.data = data or container.DataContainer()

    93         self.left = left

    94         self.right = right

    95 

    96     def __str__(self):

    97         """

    98         @return: A string presentation of the relation object

    99         """

   100         return "%s %s %s" % (self.left,self.relation_name,self.right)

   101     

   102     def __repr__(self):

   103         return "%s(ref=%r, lineno=%r)" % (self.__class__.__name__,

   104                                           getattr(self, 'ref', None),

   105                                           getattr(self, 'lineno', None))

   106 

   107     def get_name(self):

   108         """

   109         @return: The relation name.

   110         """

   111         return self.relation_name

   112 

   113     def get_description(self):

   114         """

   115         @return: a possible description of the relation.

   116         """

   117         return self.description

   118         

   119     def execute(self):

   120         """

   121         Execute the relation object.

   122         """

   123         pass

   124 

   125 

   126 class RelationContainer(RelationBase, list):

   127     """

   128     This class provides the RelationContainer interface for collecting

   129     relation sets into one place which can be executed through the container.

   130     """

   131     def __init__(self, data=None):

   132         super(RelationContainer, self).__init__(data, 'LContainer', 'RContainer')

   133         self.value_list = list()

   134 

   135     def append(self, value):

   136         self.value_list.append(value)

   137 

   138     def __iter__(self):

   139         return self.value_list.__iter__()

   140 

   141     def __len__(self):

   142         return len(self.value_list)

   143 

   144     def __or__(self, other):

   145         """

   146         This function adds two RelationContainers to each other and removes

   147         duplicates from the result.

   148         The modification is inplace and the returned value is called object.

   149         """

   150         self.value_list = set(self.value_list) | set(other.value_list)

   151         return self

   152 

   153     def __unicode__(self):

   154         if self:

   155             ret = ''

   156             for value in self:

   157                 ret += unicode(value)

   158         else:

   159             ret = 'No relations'

   160         return ret

   161 

   162     def find_relations(self, refs): abstract()

   163     def add_relation(self, relation): abstract()

   164     def has_errors(self): abstract()

   165 

   166 class RelationContainerImpl(RelationContainer):

   167     """ Base implementation for RelationContainer to use in ConE rules

   168     """

   169     def execute(self):

   170         ret = True

   171         i = 0

   172         for relation in self:

   173             i += 1

   174             r = relation.execute()

   175             ret = ret and r

   176         return ret

   177 

   178     def find_relations(self, refs):

   179         relations = []

   180         for ref in refs:

   181             for relation in self:

   182                 if relation.has_ref(ref):

   183                     relations.append(relation)

   184         return relations

   185 

   186     def add_relation(self, relation):

   187         self.append(relation)

   188 

   189     def has_ref(self, refs):

   190         for ref in refs:

   191             for relation in self:

   192                 if relation.has_ref(ref):

   193                     return True

   194         return False

   195 

   196     def has_errors(self):

   197         for relation in self:

   198             if relation.has_errors():

   199                 return True

   200         return False

   201             

   202     def get_errors(self):

   203         errors = []

   204         for relation in self:

   205             errors += relation.get_errors()

   206         return errors

   207 

   208 #### The relations are here ####

   209 

   210 class BaseRelation(RelationBase):

   211     """ BaseRelation implements the basic evaluation logic for relations

   212     This class abstract and should be extended for concrete implementation of

   213     relation type.

   214 

   215     Subclasses need to set their own context in their constructor before this

   216     class's constructor is called if custom context is needed. If context not

   217     set then DefaultContext is used.

   218     """

   219     KEY = 'base_relation'

   220 

   221     def __init__(self, data, left, right):

   222         # Context needs to be overridden for special purposes

   223         try:

   224             self.__getattribute__('context')

   225         except AttributeError:

   226             self.context = DefaultContext(data)

   227 

   228         left = self.expand_rule_elements(left)

   229         right = self.expand_rule_elements(right)

   230         super(BaseRelation, self).__init__(data, left, right)

   231         self.interpreter = ASTInterpreter(context=self.context)

   232 

   233     def execute(self, context=None):

   234         """

   235         @return Returns error dictionary

   236 

   237         In the client code proper way to check if the rule applies:

   238         info = relation.execute()

   239         if not info.has_errors():

   240         else: HANDLE ERRORS

   241         """

   242         # logger.debug("Interpreter context %s" % self.interpreter.context)

   243         self.interpreter.create_ast('%s %s %s' % (self.left, self.KEY, self.right))

   244         ret = self.interpreter.eval(context, relation=self)

   245         return ret

   246 

   247     def get_keys(self):

   248         """ Returns the references from this relation.

   249         """

   250         refs = ASTInterpreter.extract_refs(self.left)

   251         refs += ASTInterpreter.extract_refs(self.right)

   252         return refs

   253 

   254     def has_ref(self, ref):

   255         """ Returns if the 'ref' is included in this relation

   256         """

   257         return ref in self.get_keys()

   258 

   259     def has_errors(self):

   260         return bool(self.interpreter.errors)

   261 

   262     def get_refs(self):

   263         extracted_refs = ASTInterpreter.extract_refs(self.left)

   264         

   265         # Handle eval expressions (a somewhat ugly hack,

   266         # but this is a legacy plug-in so...)

   267         interpreter = ASTInterpreter(self.left)

   268         for expression in interpreter.parse_tree:

   269             if hasattr(expression, 'extract_refs'):

   270                 extracted_refs.extend(expression.extract_refs())

   271         

   272         # Filter out entries that evaluate successfully as Python code

   273         # e.g. True or 123

   274         result = []

   275         for item in extracted_refs:

   276             try:    eval(item)

   277             except: result.append(item)

   278             else:   pass

   279         return result

   280 

   281     def _eval_rside_value(self, value): abstract()

   282     def _compare_value(self, value): abstract()

   283 

   284     def extract_erroneus_features_with_values(self):

   285         """

   286         Extract references who have errors.

   287 

   288         Returns dictionary { 'reference' : 'value' }

   289         """

   290         data_dict = {}

   291         for ref in ASTInterpreter.extract_refs(self.right):

   292             value = self.data.get_feature(ref)

   293             if self._compare_value(value):

   294                 data_dict[ref] = value

   295             elif value == None:

   296                 data_dict[ref] = None

   297         return data_dict

   298 

   299     def get_errors(self):

   300         return self.interpreter.errors

   301 

   302     def expand_rule_elements(self, rule):

   303         """ Expans rule elements base on the reference.

   304         Context is used for fetching the child elements for parent references

   305         which uses asterisk identifier for selecting all child features: 

   306         'parent_feature.*' -> 'child_fea_1 and child_fea_2'.

   307         """

   308         tokens = get_tokens(rule) # [token for token in rule.split()]

   309 

   310         expanded_rule = ""

   311         for token in tokens:

   312             if token.endswith('.*'):

   313                 index = token.index('.*')

   314                 parent_ref = token[:index]

   315                 children = self.context.get_children_for_reference(parent_ref)

   316                 expanded_element = ' and '.join([child.reference for child in children])

   317                 if expanded_rule:

   318                     expanded_rule = '%s and %s' % (expanded_rule, expanded_element.rstrip())

   319                 else:

   320                     expanded_rule = expanded_element.rstrip()

   321             elif token.lower() in OPERATORS:

   322                 expanded_rule += ' %s ' % token

   323             else:

   324                 if expanded_rule:

   325                     expanded_rule += '%s'% token

   326                 else:

   327                     expanded_rule = token

   328         return expanded_rule.strip()

   329 

   330 class RequireRelation(BaseRelation):

   331     KEY = 'requires'

   332 RELATIONS[RequireRelation.KEY] = RequireRelation

   333 

   334 class ExcludesRelation(BaseRelation):

   335     KEY = 'excludes'

   336 

   337 RELATIONS['excludes'] = ExcludesRelation

   338 

   339 ################################

   340 # Abstract syntax tree builder #

   341 ################################

   342 

   343 def nor(expression, a, b):

   344     return not ops.or_(a, b)

   345 

   346 def nand(expression, a, b):

   347     return not ops.and_(a, b)

   348 

   349 def truth_and(expression, a, b):

   350     return ops.truth(a) and ops.truth(b)

   351 

   352 class DefaultContext(object):

   353     """ DefaultContext implements ConE specific context for handling rules

   354     """

   355     def __init__(self, data):

   356         self.data = data

   357 

   358     def eval(self, ast, expression, value):

   359         pass

   360 

   361     def get_keys(self, refs):

   362         return ASTInterpreter.extract_refs(refs)

   363 

   364     def get_children_for_reference(self, reference):

   365         # implement ConE specific children expansion

   366         pass

   367 

   368     def handle_terminal(self, expression):

   369         try:

   370             return int(expression)

   371         except:

   372             return expression

   373 

   374 PRECEDENCES = {

   375     'PREFIX_OPERATORS' : 10,

   376     'MULDIV_OPERATORS' : 8,

   377     'ADDSUB_OPERATORS' : 7,

   378     'SHIFT_OPERATORS' : 6,

   379     'BITWISE_OPERATORS' : 5,

   380     'COMPARISON_OPERATORS' : 4,

   381     'SET_OPERATORS' : 3,

   382     'BOOLEAN_OPERATORS' : 2, 

   383     'RELATION_OPERATORS' : 1,

   384     'NOT_DEFINED' : 0

   385 }

   386 

   387 class Expression(object):

   388     PRECEDENCE = PRECEDENCES['NOT_DEFINED']

   389     KEY = 'base_expression'

   390 

   391     def __init__(self, ast):

   392         self.ast = ast

   393         self.value = None

   394 

   395     def get_title(self):

   396         return self.KEY

   397 

   398     def eval(self, context, **kwargs): pass

   399 

   400 class OneParamExpression(Expression):

   401     PARAM_COUNT = 1

   402     def __init__(self, ast, expression):

   403         super(OneParamExpression, self).__init__(ast)

   404         self.expression = expression

   405 

   406     def __unicode__(self):

   407         return u'%s %s' % (self.KEY, self.expression)

   408 

   409     def eval(self, context, **kwargs):

   410         self.value = self.OP(self.expression.eval(context, **kwargs))

   411         context.eval(self.ast, self, self.value)

   412         return self.value

   413 

   414 class TwoOperatorExpression(Expression):

   415     PARAM_COUNT = 2

   416     OP = None

   417     EVAL_AS_BOOLS = True

   418 

   419     def __init__(self, ast, left, right):

   420         super(TwoOperatorExpression, self).__init__(ast)

   421         self.left = left

   422         self.right = right

   423 

   424     def __unicode__(self):

   425         return u'%s %s %s' % (self.left, self.KEY, self.right)

   426 

   427     def eval(self, context, **kwargs):

   428         self.value = self.OP(self.left.eval(context, **kwargs), self.right.eval(context, **kwargs))

   429         context.eval(self.ast, self, self.value)

   430         return self.value

   431 

   432 class TwoOperatorBooleanExpression(TwoOperatorExpression):

   433     def eval(self, context, **kwargs):

   434         self.value = self.OP(bool(self.left.eval(context, **kwargs)), bool(self.right.eval(context, **kwargs)))

   435         context.eval(self.ast, self, self.value)

   436         return self.value         

   437 

   438 class TerminalExpression(Expression):

   439     KEY = 'terminal'

   440 

   441     def __init__(self, ast, expression):

   442         super(TerminalExpression, self).__init__(ast)

   443         self.expression = expression

   444 

   445     def eval(self, context, **kwargs):

   446         """ Use context to eval the value

   447         Expression on TerminalExpression is feature reference or value

   448         context should handle the reference conversion to correct value

   449         """

   450         from cone.public import exceptions

   451         try:

   452             context.configuration.get_default_view().get_feature(self.expression)

   453             self.value = context.handle_terminal(self.expression)

   454         except exceptions.NotFound:

   455             self.value = context.convert_value(self.expression)

   456             

   457         return self.value

   458 

   459     def __unicode__(self):

   460         return self.expression

   461     

   462     def __repr__(self):

   463         return self.expression

   464 

   465     def get_ref(self):

   466         """

   467         @return: The setting reference, e.g. 'MyFeature.MySetting'

   468         """

   469         return self.expression

   470 

   471 

   472 class NegExpression(OneParamExpression):

   473     PRECEDENCE = PRECEDENCES['PREFIX_OPERATORS']

   474     KEY= '-'

   475     OP = ops.neg

   476 

   477 class AndExpression(TwoOperatorBooleanExpression):

   478     PRECEDENCE = PRECEDENCES['BOOLEAN_OPERATORS']

   479     KEY= 'and'

   480     OP = truth_and

   481 

   482 class NandExpression(TwoOperatorBooleanExpression):

   483     PRECEDENCE = PRECEDENCES['BOOLEAN_OPERATORS']

   484     KEY = 'nand'

   485     OP = nand

   486 

   487 class OrExpression(TwoOperatorBooleanExpression):

   488     PRECEDENCE = PRECEDENCES['BOOLEAN_OPERATORS']

   489     KEY = 'or'

   490     OP = ops.or_

   491 

   492 class XorExpression(TwoOperatorBooleanExpression):

   493     PRECEDENCE = PRECEDENCES['BOOLEAN_OPERATORS']

   494     KEY = 'xor'

   495     OP = ops.xor

   496 

   497 class NorExpression(TwoOperatorBooleanExpression):

   498     PRECEDENCE = PRECEDENCES['BOOLEAN_OPERATORS']

   499     KEY = 'nor'

   500     OP = nor

   501 

   502 class EqualExpression(TwoOperatorExpression):

   503     PRECEDENCE = PRECEDENCES['COMPARISON_OPERATORS']

   504     KEY = '=='

   505     OP = ops.eq

   506 

   507 class NotEqualExpression(TwoOperatorExpression):

   508     PRECEDENCE = PRECEDENCES['COMPARISON_OPERATORS']

   509     KEY = '!='

   510     OP = ops.ne

   511 

   512 class LessThanExpression(TwoOperatorExpression):

   513     PRECEDENCE = PRECEDENCES['COMPARISON_OPERATORS']

   514     KEY = '<'

   515     OP = ops.lt

   516 

   517 class GreaterThanExpression(TwoOperatorExpression):

   518     PRECEDENCE = PRECEDENCES['COMPARISON_OPERATORS']

   519     KEY = '>'

   520     OP = ops.gt

   521 

   522 class LessThanEqualExpression(TwoOperatorExpression):

   523     PRECEDENCE = PRECEDENCES['COMPARISON_OPERATORS']

   524     KEY = '<='

   525     OP = ops.le

   526 

   527 class GreaterThanEqualExpression(TwoOperatorExpression):

   528     PRECEDENCE = PRECEDENCES['COMPARISON_OPERATORS']

   529     KEY = '>='

   530     OP = ops.ge

   531 

   532 

   533 def handle_require(expression, left, right):

   534     if left and right:

   535         return True

   536     elif not left:

   537         return True

   538     return False

   539 

   540 class RequireExpression(TwoOperatorExpression):

   541     PRECEDENCE = PRECEDENCES['RELATION_OPERATORS']

   542     KEY = 'requires'

   543     OP = handle_require

   544 

   545     def eval(self, context, **kwargs):

   546         super(RequireExpression, self).eval(context, **kwargs)

   547         if not self.value:

   548             left_keys = []

   549             for ref in self.ast.extract_refs(unicode(self.left)):

   550                 for key in context.get_keys(ref):

   551                     left_keys.append(key)

   552 

   553             for key in left_keys:

   554                 self.ast.add_error(key, { 'error_string' : 'REQUIRES right side value is "False"',

   555                                           'left_key' : key,

   556                                           'rule' : self.ast.expression

   557                                           })

   558         return self.value

   559 

   560 def handle_exclude(expression, left, right):

   561     if left and not right:

   562         return True

   563     elif not left:

   564         return True

   565     return False

   566 

   567 class ExcludeExpression(TwoOperatorExpression):

   568     PRECEDENCE = PRECEDENCES['RELATION_OPERATORS']

   569     KEY = 'excludes'

   570     OP = handle_exclude

   571 

   572     def eval(self, context, **kwargs):

   573         super(ExcludeExpression, self).eval(context, **kwargs)

   574         if not self.value:

   575             left_keys = []

   576             for ref in self.ast.extract_refs(unicode(self.left)):

   577                 for key in context.get_keys(ref):

   578                     left_keys.append(key)

   579                     

   580             for key in left_keys:

   581                 self.ast.add_error(key, { 'error_string' : 'EXCLUDE right side value is "True"',

   582                                           'left_key' : key,

   583                                           'rule' : self.ast.expression

   584                                           })

   585         return self.value

   586 

   587 

   588 class NotExpression(OneParamExpression):

   589     PRECEDENCE = PRECEDENCES['PREFIX_OPERATORS']

   590     KEY = 'not'

   591     OP = ops.not_

   592 

   593 class TruthExpression(OneParamExpression):

   594     PRECEDENCE = PRECEDENCES['PREFIX_OPERATORS']

   595     KEY = 'truth'

   596     OP = ops.truth

   597 

   598 LEFT_PARENTHESIS = '('

   599 RIGHT_PARENTHESIS = ')'

   600 class SimpleCondition(EqualExpression):

   601     """

   602     A simple condition object that can refer to a model object and evaluate if the value matches  

   603     """

   604     def __init__(self, left, right):

   605         lterm = TerminalExpression(None, left)

   606         rterm = TerminalExpression(None, right)

   607         EqualExpression.__init__(self, None, lterm, rterm)

   608 

   609 

   610 # in format KEY : OPERATOR CLASS

   611 OPERATORS = {

   612     'and' : AndExpression,

   613     'nand' : NandExpression,

   614     'or' : OrExpression,

   615     'xor' : XorExpression,

   616     'nor' : NorExpression,

   617     'not' : NotExpression,

   618     'truth' : TruthExpression,

   619     '==' : EqualExpression,

   620     '!=' : NotEqualExpression,

   621     '<' : LessThanExpression,

   622     '>' : GreaterThanExpression,

   623     '<=' : LessThanEqualExpression,

   624     '>=' : GreaterThanEqualExpression,

   625     'requires' : RequireExpression,

   626     'excludes' : ExcludeExpression,

   627     '-' : NegExpression

   628     }

   629 

   630 def add_operator(key, operator_class=None, baseclass=RequireExpression):

   631     """

   632     Add new operator key and operator class.

   633     If operator class isn't provided the baseclass parameter is used as

   634     operator base. The baseclass parameter is RequireExpression by default

   635     which has success condition left_rule=True and right_rule=True

   636     

   637     """

   638     OPERATORS[key] = operator_class or create_new_class(key, baseclass)

   639 

   640 def create_new_class(key, baseclass):

   641     ns = baseclass.__dict__.copy()

   642     ns['KEY'] = key

   643     key_pieces = key.split('_')

   644     class_prefix = ''.join([key_piece.capitalize() for key_piece in key_pieces])

   645     new_class = type(class_prefix + 'Expression', (baseclass,), ns)

   646     return new_class

   647 

   648 class ParseException(Exception): pass

   649 

   650 class ASTInterpreter(object):

   651     def __init__(self, infix_expression=None, context=None):

   652         """ Takes infix expression as string """

   653         self.context = context or DefaultContext(None)

   654         # logger.debug("AST init context: %s" % self.context)

   655         self._init_locals(infix_expression)

   656         if infix_expression:

   657             self.create_ast()

   658 

   659     def _init_locals(self, infix_expression):

   660         # The result value of full eval of the parse_tree

   661         self.value = None

   662         self.warnings = {}

   663         self.errors = {}

   664         self.postfix_array = []

   665         self.parse_tree = []

   666         self.expression = infix_expression

   667 

   668     def __unicode__(self):

   669         s = ''

   670         for expr in self.parse_tree:

   671             s += unicode(expr)

   672         return s

   673 

   674     def add_error(self, key, error_dict):

   675         if self.errors.has_key(key):

   676             self.errors[key].append(error_dict)

   677         else:

   678             self.errors[key] = [error_dict]

   679 

   680     def create_ast(self, infix_expression=None):

   681         if infix_expression:

   682             self._init_locals(infix_expression)

   683         self._infix_to_postfix()

   684         self._create_parse_tree()

   685         return self.parse_tree

   686 

   687     def _infix_to_postfix(self):

   688         """

   689         Shunting yard algorithm used to convert infix presentation to postfix.

   690         """

   691         if not self.expression:

   692             raise ParseException('Expression is None')

   693         tokens = get_tokens(self.expression) # [token for token in self.expression.split()]

   694         stack = []

   695         # logger.debug('TOKENS: %s' % tokens)

   696         for token in tokens:

   697             # logger.debug('TOKEN: %s' % token)

   698             if token.lower() in OPERATORS:

   699                 op_class = OPERATORS.get(token)

   700                 if stack:

   701                     while len(stack) != 0:

   702                         top = stack[-1]

   703                         if top in OPERATORS:

   704                             top_operator = OPERATORS.get(top)

   705                             if op_class.PRECEDENCE <= top_operator.PRECEDENCE:

   706                                 self.postfix_array.append(stack.pop())

   707                             else:

   708                                 # Break from loop if top operator precedence is less.

   709                                 break

   710                         else:

   711                             # If top not operator break from loop

   712                             break

   713                 stack.append(token)

   714             elif token == LEFT_PARENTHESIS:

   715                 # logger.debug('Left parenthesis')

   716                 stack.append(token)

   717             elif token == RIGHT_PARENTHESIS:

   718                 # logger.debug('Right parenthesis')

   719                 left_par_found = False

   720                 stack_token = stack.pop()

   721                 while stack_token:

   722                     if stack_token != LEFT_PARENTHESIS:

   723                         self.postfix_array.append(stack_token)

   724                     else:

   725                         left_par_found = True

   726                         break

   727                     if stack:

   728                         stack_token = stack.pop()

   729                     else:

   730                         stack_token = None

   731                         

   732                 if not left_par_found:

   733                     raise ParseException('Mismatched parenthesis "%s".' % LEFT_PARENTHESIS)

   734             else:

   735                 # logger.debug('Adding value to output. %s' % repr((token)))

   736                 self.postfix_array.append((token))

   737             

   738         # There should be only operators left in the stack

   739         if stack:

   740             # logger.debug('Operators in stack.')

   741             operator = stack.pop()

   742             while operator:

   743                 if operator != LEFT_PARENTHESIS:

   744                     self.postfix_array.append(operator)

   745                 else:

   746                     raise ParseException('Mismatched parenthesis "%s".' % LEFT_PARENTHESIS)

   747                 if stack:

   748                     operator = stack.pop()

   749                 else:

   750                     operator = None

   751 

   752         # logger.debug('Infix to postfix conversion: %s' % self.postfix_array)

   753         return self.postfix_array

   754     

   755     def _create_parse_tree(self):

   756         self.parse_tree = []

   757         for token in self.postfix_array:

   758             if token in OPERATORS:

   759                 # logger.debug('OP: %s' % (token))

   760                 expression_class = OPERATORS[token]

   761                 params = []

   762                 for i in range(expression_class.PARAM_COUNT):

   763                     try:

   764                         params.append(self.parse_tree.pop())

   765                     except IndexError, e:

   766                         raise ParseException('Syntax error: "%s"' % self.expression)

   767                 params.reverse()

   768                 expression = expression_class(self, *params)

   769 

   770                 # logger.debug('The operation: %s' % expression)

   771                 self.parse_tree.append(expression)

   772             else:

   773                 expression = TerminalExpression(self, token)

   774                 self.parse_tree.append(expression)

   775 

   776         #logger.debug('THE STACK: %s' % self.parse_tree)

   777         #for s in self.parse_tree:

   778         #    logger.debug('Stack e: %s' % str(s))

   779 

   780         return self.parse_tree

   781 

   782     def eval(self, context=None, **kwargs):

   783         """ Evals the AST

   784         If empty expression is given, None is returned

   785         """

   786         for expression in self.parse_tree:

   787             self.value = expression.eval(context, **kwargs)

   788         return self.value

   789 

   790     @staticmethod

   791     def extract_refs(expression):

   792         tokens = get_tokens(expression)

   793         refs = []

   794         for token in tokens:

   795             if not token.lower() in OPERATORS and token != LEFT_PARENTHESIS and token != RIGHT_PARENTHESIS:

   796                 refs.append(token.strip('%s%s' % (LEFT_PARENTHESIS, RIGHT_PARENTHESIS)))

   797         return refs

   798 

   799 ##################################################################

   800 # Create and configure the main level logger

   801 logger = logging.getLogger('cone')