bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/parser/regexp/ROr.java

   1 package org.simantics.scl.compiler.parser.regexp;
   2
   3 import gnu.trove.set.hash.THashSet;
   4
   5 import java.util.Arrays;
   6 import java.util.Iterator;
   7
   8 import org.simantics.scl.compiler.parser.regexp.automata.NFA;
   9
  10 public class ROr extends Regexp {
  11     public final Regexp[] exps;
  12
  13     ROr(Regexp[] exps) {
  14         this.exps = exps;
  15     }
  16
  17     @Override
  18     protected void buildAutomaton(NFA aut, int inState, int outState) {
  19         for(Regexp exp : exps)
  20             exp.buildAutomaton(aut, inState, outState);
  21     }
  22
  23     @Override
  24     protected void toString(StringBuilder b, int prec) {
  25         if(prec >= 1)
  26             b.append('(');
  27         boolean first = true;
  28         for(Regexp exp : exps) {
  29             if(first)
  30                 first = false;
  31             else
  32                 b.append(" | ");
  33             exp.toString(b, 1);
  34         }
  35         if(prec >= 1)
  36             b.append(')');
  37     }
  38
  39     @Override
  40     public void toString(StringBuilder b, Namer grammar, int prec) {
  41         if(prec >= 1)
  42             b.append('(');
  43         boolean first = true;
  44         for(Regexp exp : exps) {
  45             if(first)
  46                 first = false;
  47             else
  48                 b.append(" | ");
  49             exp.toString(b, grammar, 1);
  50         }
  51         if(prec >= 1)
  52             b.append(')');
  53     }
  54
  55     @Override
  56     protected int getTypeId() {
  57         return OR;
  58     }
  59
  60     @Override
  61     public boolean equals(Object obj) {
  62         if(obj == this)
  63             return true;
  64         if(obj == null || obj.getClass() != getClass())
  65             return false;
  66         ROr other = (ROr)obj;
  67         return Arrays.equals(exps, other.exps);
  68     }
  69
  70     @Override
  71     public int hashCode() {
  72         int r = 34235;
  73         for(Regexp exp : exps) {
  74             r *= 31;
  75             r += exp.hashCode();
  76         }
  77         return r;
  78     }
  79
  80     @Override
  81     public boolean isNullable() {
  82         for(Regexp exp : exps)
  83             if(exp.isNullable())
  84                 return true;
  85         return false;
  86     }
  87
  88     private Regexp simplify(THashSet<Regexp> set) {
  89         boolean qm = set.remove(ONE);
  90
  91         Regexp exp;
  92         simpl: {
  93             if(set.size() > 1) {
  94                 frontLoop: {
  95                     Iterator<Regexp> it = set.iterator();
  96                     Regexp common = front(it.next());
  97                     while(it.hasNext()) {
  98                         Regexp temp = front(it.next());
  99                         if(!temp.equals(common))
 100                             break frontLoop;
 101                     }
 102
 103                     THashSet<Regexp> set2 = new THashSet<Regexp>();
 104                     for(Regexp e : set)
 105                         set2.add(removeFront(e));
 106
 107                     exp = seq(common, simplify(set2));
 108                     break simpl;
 109                 }
 110
 111                 backLoop: {
 112                     Iterator<Regexp> it = set.iterator();
 113                     Regexp common = back(it.next());
 114                     while(it.hasNext()) {
 115                         Regexp temp = back(it.next());
 116                         if(!temp.equals(common))
 117                             break backLoop;
 118                     }
 119
 120                     THashSet<Regexp> set2 = new THashSet<Regexp>();
 121                     for(Regexp e : set)
 122                         set2.add(removeBack(e));
 123
 124                     exp = seq(simplify(set2), common);
 125                     break simpl;
 126                 }
 127             }
 128
 129             exp = or(set);
 130         }
 131
 132         if(qm && !exp.isNullable())
 133             exp = new ROp(exp, '?');
 134         return exp;
 135     }
 136
 137     @Override
 138     public Regexp simplify() {
 139         if(exps.length == 0)
 140             return this;
 141         THashSet<Regexp> set = new THashSet<Regexp>();
 142         for(Regexp exp : exps) {
 143             exp = exp.simplify();
 144             or(set, exp);
 145         }
 146         return simplify(set);
 147     }
 148
 149     private static Regexp front(Regexp exp) {
 150         if(exp instanceof RSeq) {
 151             Regexp[] exps = ((RSeq)exp).exps;
 152             if(exps.length == 0)
 153                 return null;
 154             return exps[0];
 155         }
 156         else
 157             return exp;
 158     }
 159
 160     private static Regexp removeFront(Regexp exp) {
 161         if(exp instanceof RSeq) {
 162             Regexp[] exps = ((RSeq)exp).exps;
 163             return seq_(Arrays.asList(exps).subList(1, exps.length));
 164         }
 165         else
 166             return ONE;
 167     }
 168
 169     private static Regexp back(Regexp exp) {
 170         if(exp instanceof RSeq) {
 171             Regexp[] exps = ((RSeq)exp).exps;
 172             if(exps.length == 0)
 173                 return null;
 174             return exps[exps.length-1];
 175         }
 176         else
 177             return exp;
 178     }
 179
 180     private static Regexp removeBack(Regexp exp) {
 181         if(exp instanceof RSeq) {
 182             Regexp[] exps = ((RSeq)exp).exps;
 183             return seq_(Arrays.asList(exps).subList(0, exps.length-1));
 184         }
 185         else
 186             return ONE;
 187     }
 188 }