Package Martel :: Module optimize
[hide private]
[frames] | no frames]

Source Code for Module Martel.optimize

  1  # Copyright 2000-2001, Dalke Scientific Software, LLC 
  2  # Distributed under the Biopython License Agreement (see the LICENSE file). 
  3   
  4  """Optimize an expression tree 
  5   
  6    - remove Group nodes with no name 
  7    - merge successive Str, single character positive Any nodes and positive 
  8          Literals 
  9  """ 
 10   
 11  import Expression 
 12   
13 -def skip_empty_group(exp):
14 while isinstance(exp, Expression.Group) and exp.name is None: 15 exp = exp.expression 16 return exp
17 18 # The only thing this does is remove Groups with no names
19 -def optimize_unnamed_groups_recursive(exp):
20 if isinstance(exp, Expression.MaxRepeat) or \ 21 isinstance(exp, Expression.Group): 22 exp.expression = skip_empty_group(exp.expression) 23 elif isinstance(exp, Expression.ExpressionList): 24 subexps = [] 25 for subexp in exp.expressions: 26 subexp = skip_empty_group(subexp) 27 subexps.append(subexp) 28 exp.expressions = subexps 29 30 if hasattr(exp, "expression"): 31 optimize_unnamed_groups_recursive(exp.expression) 32 elif hasattr(exp, "expressions"): 33 for exp in exp.expressions: 34 optimize_unnamed_groups_recursive(exp)
35
36 -def optimize_unnamed_groups(exp):
37 """return an equivalent expression tree but without unnamed groups 38 39 WARNING: has side-effect 40 """ 41 42 optimize_unnamed_groups_recursive(exp) 43 return skip_empty_group(exp)
44
45 -def is_mergeable(exp):
46 return isinstance(exp, Expression.Str) or \ 47 (isinstance(exp, Expression.Literal) and exp.invert == 0) or \ 48 (isinstance(exp, Expression.Any) and len(exp.chars) == 1 and \ 49 exp.invert == 0)
50 -def get_merge_text(exp):
51 if isinstance(exp, Expression.Str): 52 return exp.string 53 elif isinstance(exp, Expression.Literal): 54 assert exp.invert == 0 55 return exp.char 56 elif isinstance(exp, Expression.Any): 57 assert len(exp.chars) == 1 and exp.invert == 0 58 return exp.chars 59 raise AssertionError, "unknown exp: %s" % repr(exp)
60
61 -def merge_strings(exp):
62 """merge successive strings and string-like terms into a single Str 63 64 WARNING: has side-effects 65 """ 66 # Merge all of the children first - might promote a 67 # Str("A") + (Str("B") + Str("C")) into an Str("A") + Str("BC") 68 # before we do the merge into Str("ABC") 69 70 if hasattr(exp, "expression"): 71 exp.expression = merge_strings(exp.expression) 72 elif hasattr(exp, "expressions"): 73 subexps = [] 74 for subexp in exp.expressions: 75 subexps.append(merge_strings(subexp)) 76 exp.expressions = subexps 77 78 if isinstance(exp, Expression.Seq): 79 all_strings = 1 80 subexps = [] 81 for subexp in exp.expressions: 82 if not subexps: 83 subexps.append(subexp) 84 elif not is_mergeable(subexps[-1]): 85 all_strings = 0 86 subexps.append(subexp) 87 elif not is_mergeable(subexp): 88 all_strings = 0 89 subexps.append(subexp) 90 else: 91 # Previous and current are mergeable 92 subexps[-1] = Expression.Str(get_merge_text(subexps[-1]) + \ 93 get_merge_text(subexp)) 94 if all_strings and subexps: 95 assert len(subexps) == 1 96 return subexps[0] 97 98 return exp
99
100 -def optimize(exp):
101 """expression tree -> optimized expression tree 102 103 Apply various optimizations to the expression tree. 104 """ 105 106 exp = exp.copy() 107 exp = optimize_unnamed_groups(exp) 108 exp = merge_strings(exp) 109 return exp
110