RegexDecomposer.java

package com.github.dakusui.jcunitx.metamodel.parameters.regex;

import com.github.dakusui.jcunitx.core.AArray;
import com.github.dakusui.jcunitx.regex.Expr;
import com.github.dakusui.jcunitx.regex.Reference;
import com.github.dakusui.jcunitx.regex.RegexTranslator;
import com.github.dakusui.jcunitx.regex.Value;
import com.github.dakusui.jcunitx.factorspace.Constraint;
import com.github.dakusui.jcunitx.factorspace.Factor;
import com.github.dakusui.jcunitx.factorspace.FactorSpace;
import com.github.dakusui.jcunitx.pipeline.stages.Generator;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

import static com.github.dakusui.jcunitx.utils.Utils.concatenate;
import static java.util.Objects.requireNonNull;

/**
 * A class to construct a factor space from a regular expression.
 *  * With the prefix and the "top level" expression given to the constructor,
 * `RegexComposer` can "decode" a row  in a generated covering array.
 * A regular expression `hello(world|WORLD)everyone{0,1}` is rendered into the following factor space.
 *
 * [source]
 * .Factors
 * ----
 * name: <REGEX:top:alt-4>:(VOID), [world], [WORLD]
 * name: <REGEX:top:rep-6>:(VOID), [(EMPTY)], [everyone]
 * name: <REGEX:top:cat-7>:[[hello], Reference:<REGEX:top:alt-4>, Reference:<REGEX:top:rep-6>]
 * ----
 *
 * A generated factor has two types of levels.
 * One is a list of values, the other is `VOID` value.
 * Each value in a list is a list of immediate values or a reference to another factor.
 * Also, this class generates a set of constructors as follows.
 *
 * [source]
 * .Constraints
 * ----
 * constraint([REGEX:top:cat-7]->REGEX:top:alt-4)
 * constraint([REGEX:top:cat-7]->REGEX:top:rep-6)
 * ----
 *
 * If there is no constraint, a covering array generation engine will give a value
 * to a factor not appearing in the final sequence.
 * This will damage the coverage of the test suite.
 * Hence, the constraints generated by this class force the engine to give the `VOID`
 * level to the factors that are not referenced.
 */
public class RegexDecomposer extends RegexTranslator {

  /**
   * Constructs a new instance of this class.
   * The `topLevel` expression is returned by the {@link com.github.dakusui.jcunitx.regex.Parser}.
   *
   * @param prefix A prefix given to factor names
   * @param topLevel The top level expression.
   * @see com.github.dakusui.jcunitx.regex.Parser
   */
  public RegexDecomposer(String prefix, Expr topLevel) {
    super(topLevel, prefix);
  }

  /**
   * Decomposes the top level expression to a factor space.
   *
   * @return The factor space
   */
  public FactorSpace decompose() {
    List<? extends Factor> factors = buildFactors();
    return FactorSpace.create(factors, buildConstraints(factors));
  }

  private List<? extends Factor> buildFactors() {
    this.topLevelExpression.accept(this);
    final List<Factor> builder = new LinkedList<>();
    for (String eachKey : this.terms.keySet()) {
      List<Object> b = new LinkedList<>();
      if (!isTopLevel(eachKey)) {
        if (isReferencedByAltDirectlyOrIndirectly(eachKey) || isAlt(eachKey)) {
          b.add(Generator.VOID);
        }
      }
      if (isAlt(eachKey)) {
        for (Value eachValue : this.terms.get(eachKey)) {
          b.add(resolveIfImmediate(eachValue));
        }
      } else /* , that is, if (isCat(eachKey)) */ {
        List<Object> work = new LinkedList<>();
        for (Value eachValue : this.terms.get(eachKey)) {
          work.addAll(this.resolve(eachValue));
        }
        b.add(work);
      }
      if (b.size() > 1 || (b.size() == 1 && isTopLevel(eachKey))) {
        builder.add(Factor.create(eachKey, b.toArray()));
      }
    }
    return Collections.unmodifiableList(builder);
  }

  private List<Constraint> buildConstraints(List<? extends Factor> factors) {
    List<Constraint> ret = new LinkedList<>();
    for (final Factor each : factors) {
      final List<String> referrers = getReferringFactors(each, factors).stream()
          .map(Factor::getName)
          .collect(Collectors.toList());
      if (referrers.isEmpty())
        continue;
      final String referee = each.getName();
      final String tag = String.format("constraint(%s->%s)", referrers, referee);
      ret.add(buildConstraint(tag, referee, referrers));
    }
    return ret;
  }

  private Constraint buildConstraint(String tag, String referee, List<String> referrers) {
    return new Constraint() {

      @Override
      public String getName() {
        return toString();
      }

      @Override
      public boolean test(AArray in) {
        for (String eachReferrer : referrers) {
          Object referrerValue = in.get(eachReferrer);
          if (!Generator.VOID.equals(referrerValue) && isReferencedBy(referrerValue)) {
            return !Generator.VOID.equals(in.get(referee));
          }
        }
        return Generator.VOID.equals(in.get(referee));
      }

      @Override
      public List<String> involvedKeys() {
        return concatenate(referrers, referee);
      }

      @Override
      public String toString() {
        return tag;
      }

      @SuppressWarnings("unchecked")
      boolean isReferencedBy(Object referrerValue) {
        return ((List<Object>) requireNonNull(referrerValue))
            .stream()
            .anyMatch((Object each) -> each instanceof Reference && ((Reference) each).key.equals(referee));
      }
    };
  }

  private List<Factor> getReferringFactors(Factor referred, List<? extends Factor> factors) {
    List<Factor> ret = new LinkedList<>();
    outer:
    for (Factor each : factors) {
      if (each == referred)
        continue;
      for (Object eachLevel : each.getLevels()) {
        if (eachLevel instanceof List) {
          for (Object eachElement : (List<?>) eachLevel) {
            if (eachElement instanceof Reference) {
              if (referred.getName().equals(((Reference) eachElement).key)) {
                ret.add(each);
                continue outer;
              }
            }
          }
        }
      }
    }
    return ret;
  }
}