dev/core/src/com/google/gwt/dev/cfg/PropertyCombinations.java - gwt - Git at Google

 /*
  * Copyright 2008 Google Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License"); you may not
  * use this file except in compliance with the License. You may obtain a copy of
  * the License at
  *
  * http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
  * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
  * License for the specific language governing permissions and limitations under
  * the License.
  */
 package com.google.gwt.dev.cfg;

 import com.google.gwt.core.ext.PropertyOracle;
 import com.google.gwt.core.ext.TreeLogger;
 import com.google.gwt.core.ext.UnableToCompleteException;
 import com.google.gwt.dev.util.CollapsedPropertyKey;
 import com.google.gwt.thirdparty.guava.common.base.Objects;
 import com.google.gwt.thirdparty.guava.common.collect.Lists;
 import com.google.gwt.thirdparty.guava.common.collect.Maps;
 import com.google.gwt.thirdparty.guava.common.collect.Sets;

 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
 import java.util.SortedMap;

 /**
  * Generates all possible permutations of properties in a module. Each
  * permutation consists of the list of active property values associated with
  * that permutation. That list of property values is represented as an array of
  * Strings corresponding to the list of properties returned by
  * {@link Properties#getBindingProperties()}.
  */
 public class PropertyCombinations implements Iterable<String[]> {

   /**
    * A bundle of the ordered names of binding and configuration properties and a single set value
    * for each that together uniquely identify a particular permutation.
    */
   public static class PermutationDescription {

     private List<String> bindingPropertyNames = Lists.newArrayList();
     private List<String> configurationPropertyNames = Lists.newArrayList();
     private List<String> propertyValues = Lists.newArrayList();

     @Override
     public int hashCode() {
       return Objects.hashCode(bindingPropertyNames, configurationPropertyNames, propertyValues);
     }

     @Override
     public boolean equals(Object obj) {
       if (obj instanceof PermutationDescription) {
         PermutationDescription that = (PermutationDescription) obj;
         return Objects.equal(this.bindingPropertyNames, that.bindingPropertyNames)
             && Objects.equal(this.configurationPropertyNames, that.configurationPropertyNames)
             && Objects.equal(this.propertyValues, that.propertyValues);
       }
       return false;
     }

     @Override
     public String toString() {
       return String.format(
           "PermutationDescription [bindingPropertyNames=%s, configurationPropertyNames=%s, "
           + "propertyValues=%s]", bindingPropertyNames, configurationPropertyNames, propertyValues);
     }
   }

   /**
    * Returns the list of all permutations. This method must return results in a
    * consistently sorted order over multiple invocations.
    */
   private static List<String[]> allPermutationsOf(Properties properties,
       Set<String> activeLinkerNames) {
     BindingProperty[] bindingProperties = getOrderedPropertiesOf(properties);

     List<String[]> permutations = new ArrayList<String[]>();
     if (bindingProperties.length > 0) {
       permute(bindingProperties, activeLinkerNames, null, 0, permutations);
     } else {
       permutations.add(new String[0]);
     }
     return permutations;
   }

   private static BindingProperty[] getOrderedPropertiesOf(Properties properties) {
     /*
      * We delete items from this set, but want to retain the original order as
      * much as possible.
      */
     Set<BindingProperty> bindingProperties = Sets.newLinkedHashSet(
         properties.getBindingProperties());

     // Accumulates the order in which the properties should be evaluated
     Map<String, BindingProperty> evaluationOrder = Maps.newLinkedHashMap();

     /*
      * Insert a property after all of the properties that it depends upon have
      * been inserted.
      */
     while (!bindingProperties.isEmpty()) {
       boolean changed = false;

       for (Iterator<BindingProperty> it = bindingProperties.iterator(); it.hasNext();) {
         BindingProperty prop = it.next();

         Set<String> deps = prop.getRequiredProperties();
         if (evaluationOrder.keySet().containsAll(deps)) {
           it.remove();
           evaluationOrder.put(prop.getName(), prop);
           changed = true;
         }
       }

       if (!changed) {
         throw new IllegalStateException(
             "Cycle detected within remaining property dependencies "
                 + bindingProperties.toString());
       }
     }

     return evaluationOrder.values().toArray(
         new BindingProperty[evaluationOrder.size()]);
   }

   private static void permute(BindingProperty[] properties,
       Set<String> activeLinkerNames, String[] soFar, int whichProp,
       List<String[]> permutations) {
     int lastProp = properties.length - 1;

     BindingProperty prop = properties[whichProp];

     // Find the last-one-wins Condition
     Condition winner = null;
     if (prop.getConditionalValues().size() == 1) {
       winner = prop.getRootCondition();
     } else {
       BindingProperty[] answerable = new BindingProperty[soFar.length];
       System.arraycopy(properties, 0, answerable, 0, soFar.length);
       PropertyOracle propertyOracle = new BindingProperties(answerable, soFar,
               ConfigurationProperties.EMPTY).toPropertyOracle();

       for (Condition cond : prop.getConditionalValues().keySet()) {
         try {
           if (cond.isTrue(TreeLogger.NULL, new DeferredBindingQuery(
               propertyOracle, activeLinkerNames))) {
             winner = cond;
           }
         } catch (UnableToCompleteException e) {
           throw new IllegalStateException("Should never get here for simple properties", e);
         }
       }
     }

     assert winner != null;

     String[] options = prop.getGeneratedValues(winner);
     for (int i = 0; i < options.length; i++) {
       String knownValue = options[i];

       String[] nextStep = new String[whichProp + 1];
       if (whichProp > 0) {
         System.arraycopy(soFar, 0, nextStep, 0, soFar.length);
       }
       nextStep[whichProp] = knownValue;

       if (whichProp < lastProp) {
         permute(properties, activeLinkerNames, nextStep, whichProp + 1,
             permutations);
       } else {
         // Finished this permutation.
         permutations.add(nextStep);
       }
     }
   }

   private final Properties properties;
   private final List<String[]> values;

   public PropertyCombinations(Properties properties,
       Set<String> activeLinkerNames) {
     this.properties = properties;
     this.values = allPermutationsOf(properties, activeLinkerNames);
   }

   /**
    * Copy constructor that allows the list of property values to be reset.
    */
   public PropertyCombinations(PropertyCombinations allPermutations,
       List<String[]> values) {
     this.properties = allPermutations.properties;
     this.values = values;
   }

   /**
    * Return a list of PropertyPermutations that represent the hard permutations
    * that result from collapsing the soft properties in the
    * PropertyPermutation's Properties object.
    */
   public List<PropertyCombinations> collapseProperties() {
     // Collate property values in this map
     SortedMap<CollapsedPropertyKey, List<String[]>> map = Maps.newTreeMap();

     BindingProperty[] propertyKeys = getOrderedProperties();
     // Loop over all possible property value permutations
     for (Iterator<String[]> it = iterator(); it.hasNext();) {
       String[] propertyValues = it.next();
       assert propertyValues.length == propertyKeys.length;

       BindingProperties bindingProperties =
           new BindingProperties(propertyKeys, propertyValues, ConfigurationProperties.EMPTY);
       CollapsedPropertyKey key = new CollapsedPropertyKey(bindingProperties);

       List<String[]> list = map.get(key);
       if (list == null) {
         list = Lists.newArrayList();
         map.put(key, list);
       }
       list.add(propertyValues);
     }

     // Return the collated values
     List<PropertyCombinations> toReturn = new ArrayList<PropertyCombinations>(
         map.size());
     for (List<String[]> list : map.values()) {
       toReturn.add(new PropertyCombinations(this, list));
     }

     return toReturn;
   }

   /**
    * Returns the properties used to generate permutations.
    * (Parallel to {@link #getOrderedPropertyValues}.)
    */
   public BindingProperty[] getOrderedProperties() {
     return getOrderedPropertiesOf(properties);
   }

   /**
    * Returns the value of each property used to generate the given permutation.
    * (Parallel to {@link #getOrderedProperties()}.)
    */
   public String[] getOrderedPropertyValues(int permutation) {
     return values.get(permutation);
   }

   /**
    * Returns a unique description for the given permutation.
    */
   public PermutationDescription getPermutationDescription(int permutationId) {
     PermutationDescription permutationDescription = new PermutationDescription();
     for (BindingProperty bindingProperty : properties.getBindingProperties()) {
       permutationDescription.bindingPropertyNames.add(bindingProperty.getName());
     }
     for (ConfigurationProperty configurationProperty : properties.getConfigurationProperties()) {
       permutationDescription.configurationPropertyNames.add(configurationProperty.getName());
     }
     permutationDescription.propertyValues.addAll(Arrays.asList(this.values.get(permutationId)));
     return permutationDescription;
   }

   /**
    * Enumerates each permutation as an array of strings such that the index of
    * each string in the array corresponds to the property at the same index in
    * the array returned from {@link #getOrderedProperties()}.
    */
   @Override
   public Iterator<String[]> iterator() {
     return values.iterator();
   }

   public int size() {
     return values.size();
   }
 }
	/*
	* Copyright 2008 Google Inc.
	*
	* Licensed under the Apache License, Version 2.0 (the "License"); you may not
	* use this file except in compliance with the License. You may obtain a copy of
	* the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
	* WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
	* License for the specific language governing permissions and limitations under
	* the License.
	*/
	package com.google.gwt.dev.cfg;

	import com.google.gwt.core.ext.PropertyOracle;
	import com.google.gwt.core.ext.TreeLogger;
	import com.google.gwt.core.ext.UnableToCompleteException;
	import com.google.gwt.dev.util.CollapsedPropertyKey;
	import com.google.gwt.thirdparty.guava.common.base.Objects;
	import com.google.gwt.thirdparty.guava.common.collect.Lists;
	import com.google.gwt.thirdparty.guava.common.collect.Maps;
	import com.google.gwt.thirdparty.guava.common.collect.Sets;

	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.Iterator;
	import java.util.List;
	import java.util.Map;
	import java.util.Set;
	import java.util.SortedMap;

	/**
	* Generates all possible permutations of properties in a module. Each
	* permutation consists of the list of active property values associated with
	* that permutation. That list of property values is represented as an array of
	* Strings corresponding to the list of properties returned by
	* {@link Properties#getBindingProperties()}.
	*/
	public class PropertyCombinations implements Iterable<String[]> {

	/**
	* A bundle of the ordered names of binding and configuration properties and a single set value
	* for each that together uniquely identify a particular permutation.
	*/
	public static class PermutationDescription {

	private List<String> bindingPropertyNames = Lists.newArrayList();
	private List<String> configurationPropertyNames = Lists.newArrayList();
	private List<String> propertyValues = Lists.newArrayList();

	@Override
	public int hashCode() {
	return Objects.hashCode(bindingPropertyNames, configurationPropertyNames, propertyValues);
	}

	@Override
	public boolean equals(Object obj) {
	if (obj instanceof PermutationDescription) {
	PermutationDescription that = (PermutationDescription) obj;
	return Objects.equal(this.bindingPropertyNames, that.bindingPropertyNames)
	&& Objects.equal(this.configurationPropertyNames, that.configurationPropertyNames)
	&& Objects.equal(this.propertyValues, that.propertyValues);
	}
	return false;
	}

	@Override
	public String toString() {
	return String.format(
	"PermutationDescription [bindingPropertyNames=%s, configurationPropertyNames=%s, "
	+ "propertyValues=%s]", bindingPropertyNames, configurationPropertyNames, propertyValues);
	}
	}

	/**
	* Returns the list of all permutations. This method must return results in a
	* consistently sorted order over multiple invocations.
	*/
	private static List<String[]> allPermutationsOf(Properties properties,
	Set<String> activeLinkerNames) {
	BindingProperty[] bindingProperties = getOrderedPropertiesOf(properties);

	List<String[]> permutations = new ArrayList<String[]>();
	if (bindingProperties.length > 0) {
	permute(bindingProperties, activeLinkerNames, null, 0, permutations);
	} else {
	permutations.add(new String[0]);
	}
	return permutations;
	}

	private static BindingProperty[] getOrderedPropertiesOf(Properties properties) {
	/*
	* We delete items from this set, but want to retain the original order as
	* much as possible.
	*/
	Set<BindingProperty> bindingProperties = Sets.newLinkedHashSet(
	properties.getBindingProperties());

	// Accumulates the order in which the properties should be evaluated
	Map<String, BindingProperty> evaluationOrder = Maps.newLinkedHashMap();

	/*
	* Insert a property after all of the properties that it depends upon have
	* been inserted.
	*/
	while (!bindingProperties.isEmpty()) {
	boolean changed = false;

	for (Iterator<BindingProperty> it = bindingProperties.iterator(); it.hasNext();) {
	BindingProperty prop = it.next();

	Set<String> deps = prop.getRequiredProperties();
	if (evaluationOrder.keySet().containsAll(deps)) {
	it.remove();
	evaluationOrder.put(prop.getName(), prop);
	changed = true;
	}
	}

	if (!changed) {
	throw new IllegalStateException(
	"Cycle detected within remaining property dependencies "
	+ bindingProperties.toString());
	}
	}

	return evaluationOrder.values().toArray(
	new BindingProperty[evaluationOrder.size()]);
	}

	private static void permute(BindingProperty[] properties,
	Set<String> activeLinkerNames, String[] soFar, int whichProp,
	List<String[]> permutations) {
	int lastProp = properties.length - 1;

	BindingProperty prop = properties[whichProp];

	// Find the last-one-wins Condition
	Condition winner = null;
	if (prop.getConditionalValues().size() == 1) {
	winner = prop.getRootCondition();
	} else {
	BindingProperty[] answerable = new BindingProperty[soFar.length];
	System.arraycopy(properties, 0, answerable, 0, soFar.length);
	PropertyOracle propertyOracle = new BindingProperties(answerable, soFar,
	ConfigurationProperties.EMPTY).toPropertyOracle();

	for (Condition cond : prop.getConditionalValues().keySet()) {
	try {
	if (cond.isTrue(TreeLogger.NULL, new DeferredBindingQuery(
	propertyOracle, activeLinkerNames))) {
	winner = cond;
	}
	} catch (UnableToCompleteException e) {
	throw new IllegalStateException("Should never get here for simple properties", e);
	}
	}
	}

	assert winner != null;

	String[] options = prop.getGeneratedValues(winner);
	for (int i = 0; i < options.length; i++) {
	String knownValue = options[i];

	String[] nextStep = new String[whichProp + 1];
	if (whichProp > 0) {
	System.arraycopy(soFar, 0, nextStep, 0, soFar.length);
	}
	nextStep[whichProp] = knownValue;

	if (whichProp < lastProp) {
	permute(properties, activeLinkerNames, nextStep, whichProp + 1,
	permutations);
	} else {
	// Finished this permutation.
	permutations.add(nextStep);
	}
	}
	}

	private final Properties properties;
	private final List<String[]> values;

	public PropertyCombinations(Properties properties,
	Set<String> activeLinkerNames) {
	this.properties = properties;
	this.values = allPermutationsOf(properties, activeLinkerNames);
	}

	/**
	* Copy constructor that allows the list of property values to be reset.
	*/
	public PropertyCombinations(PropertyCombinations allPermutations,
	List<String[]> values) {
	this.properties = allPermutations.properties;
	this.values = values;
	}

	/**
	* Return a list of PropertyPermutations that represent the hard permutations
	* that result from collapsing the soft properties in the
	* PropertyPermutation's Properties object.
	*/
	public List<PropertyCombinations> collapseProperties() {
	// Collate property values in this map
	SortedMap<CollapsedPropertyKey, List<String[]>> map = Maps.newTreeMap();

	BindingProperty[] propertyKeys = getOrderedProperties();
	// Loop over all possible property value permutations
	for (Iterator<String[]> it = iterator(); it.hasNext();) {
	String[] propertyValues = it.next();
	assert propertyValues.length == propertyKeys.length;

	BindingProperties bindingProperties =
	new BindingProperties(propertyKeys, propertyValues, ConfigurationProperties.EMPTY);
	CollapsedPropertyKey key = new CollapsedPropertyKey(bindingProperties);

	List<String[]> list = map.get(key);
	if (list == null) {
	list = Lists.newArrayList();
	map.put(key, list);
	}
	list.add(propertyValues);
	}

	// Return the collated values
	List<PropertyCombinations> toReturn = new ArrayList<PropertyCombinations>(
	map.size());
	for (List<String[]> list : map.values()) {
	toReturn.add(new PropertyCombinations(this, list));
	}

	return toReturn;
	}

	/**
	* Returns the properties used to generate permutations.
	* (Parallel to {@link #getOrderedPropertyValues}.)
	*/
	public BindingProperty[] getOrderedProperties() {
	return getOrderedPropertiesOf(properties);
	}

	/**
	* Returns the value of each property used to generate the given permutation.
	* (Parallel to {@link #getOrderedProperties()}.)
	*/
	public String[] getOrderedPropertyValues(int permutation) {
	return values.get(permutation);
	}

	/**
	* Returns a unique description for the given permutation.
	*/
	public PermutationDescription getPermutationDescription(int permutationId) {
	PermutationDescription permutationDescription = new PermutationDescription();
	for (BindingProperty bindingProperty : properties.getBindingProperties()) {
	permutationDescription.bindingPropertyNames.add(bindingProperty.getName());
	}
	for (ConfigurationProperty configurationProperty : properties.getConfigurationProperties()) {
	permutationDescription.configurationPropertyNames.add(configurationProperty.getName());
	}
	permutationDescription.propertyValues.addAll(Arrays.asList(this.values.get(permutationId)));
	return permutationDescription;
	}

	/**
	* Enumerates each permutation as an array of strings such that the index of
	* each string in the array corresponds to the property at the same index in
	* the array returned from {@link #getOrderedProperties()}.
	*/
	@Override
	public Iterator<String[]> iterator() {
	return values.iterator();
	}

	public int size() {
	return values.size();
	}
	}