dev/core/src/com/google/gwt/dev/resource/impl/PathPrefixSet.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.resource.impl;

 import com.google.gwt.dev.resource.impl.PathPrefix.Judgement;
 import com.google.gwt.dev.util.StringInterner;
 import com.google.gwt.dev.util.collect.Maps;
 import com.google.gwt.thirdparty.guava.common.collect.Lists;

 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.List;
 import java.util.Map;

 /**
  * Combines the information conveyed about a set of path prefixes to quickly
  * answer questions regarding an entire set of path prefixes.
  * <p>
  * Is effectively immutable and should not be modified after initial use.
  */
 public class PathPrefixSet {
   /*
    * (1) TODO(amitmanjhi): Improve the api of the PathPrefixSet so that with one
    * trie-traversal, it could be found out which resources rooted at a directory
    * are allowed?
    */

   private class TrieNode {
     // TODO(amitmanjhi): Consider the memory-speed tradeoff here
     private Map<String, TrieNode> children = Maps.create();
     private final String part;
     private List<PathPrefix> prefixes = Lists.newArrayList();
     private boolean hasPrefixes = false;

     public TrieNode(String part) {
       this.part = StringInterner.get().intern(part);
     }

     public TrieNode addChild(String part) {
       part = StringInterner.get().intern(part);
       TrieNode newChild = new TrieNode(part);
       assert !children.containsKey(part);
       children = Maps.put(children, part, newChild);
       return newChild;
     }

     public void addPathPrefix(PathPrefix prefix) {
       hasPrefixes = true;
       if (mergePathPrefixes) {
         if (prefixes.isEmpty()) {
           prefixes.add(prefix);
         } else {
           prefixes.get(0).merge(prefix);
         }
       } else {
         prefixes.add(prefix);
       }
     }

     public TrieNode findChild(String part) {
       return children.get(part);
     }

     public List<PathPrefix> getPathPrefixes() {
       return prefixes;
     }

     @Override
     public String toString() {
       StringBuilder sb = new StringBuilder();
       toString(sb, "");
       return sb.toString();
     }

     private void toString(StringBuilder sb, String indent) {
       if (sb.length() > 0) {
         sb.append('\n');
       }
       sb.append(indent);
       sb.append(' ');
       sb.append(part);
       for (TrieNode child : children.values()) {
         child.toString(sb, indent + "  ");
       }
     }
   }

   /**
    * Whether or not to merge prefixes that are added. Merged prefixes perform better during resource
    * scanning but at the cost of not being able to tell which module(s) are responsible for a
    * particular resource inclusion.
    */
   private boolean mergePathPrefixes = true;

   /**
    * List of all path prefixes in priority order.
    */
   private final List<PathPrefix> prefixes = new ArrayList<PathPrefix>();

   private final TrieNode rootTrieNode = new TrieNode("/");

   public PathPrefixSet() {
     this(true);
   }

   public PathPrefixSet(boolean mergePathPrefixes) {
     this.mergePathPrefixes = mergePathPrefixes;
   }

   /**
    * @param prefix the prefix to add
    * @return <code>true</code> if the prefix was not already in the set;
    *         otherwise, it merged with one having the same prefix, which has
    *         the effect of expanding the filter (the merge works as
    *         <code>union(includes - skips) - union(excludes)</code>)
    */
   public boolean add(PathPrefix prefix) {
     prefix.setPriority(prefixes.size());
     prefixes.add(prefix);

     String pathPrefix = prefix.getPrefix();

     /*
      * An empty prefix means we have no prefix requirement, but we do attach the
      * prefix to the root so that we can apply the filter.
      */
     if ("".equals(pathPrefix)) {
       rootTrieNode.addPathPrefix(prefix);
       return false;
     }

     // TODO(bruce): consider not using split for speed
     String[] parts = pathPrefix.split("/");
     TrieNode parentNode = rootTrieNode;
     boolean didAdd = false;
     for (String part : parts) {
       TrieNode childNode = parentNode.findChild(part);
       if (childNode != null) {
         // Follow existing branch.
         parentNode = childNode;
       } else {
         // Add a new branch.
         parentNode = parentNode.addChild(part);
         didAdd = true;
       }
     }
     assert (parentNode != null);
     parentNode.addPathPrefix(prefix);
     return didAdd;
   }

   public int getSize() {
     return prefixes.size();
   }

   /**
    * Determines whether or not a directory might have resources that could be
    * included. The primary purpose of this method is to allow
    * {@link ClassPathEntry} subclasses to avoid descending into directory
    * hierarchies that could not possibly contain resources that would be
    * included by {@link #includesResource(String)}
    *
    * @param dirPath must be a valid abstract directory name (must not be an
    *          empty string)
    * @return true if some PathPrefix allows the directory
    */
   public boolean includesDirectory(String dirPath) {
     assertValidAbstractDirectoryPathName(dirPath);

     /*
      * There are four cases:
      *
      * (1) The empty string was specified as a prefix, which causes everything
      * to be included.
      *
      * (2) As we walk the parts of dirPath, we see a path prefix attached to one
      * of the trie nodes we encounter. This means that there was a specified
      * prefix that this dirPath falls underneath, so it is included.
      *
      * (3) dirPath is longer than the trie, but we never encounter a path prefix
      * as we walk the trie. This indicates that this directory doesn't fall into
      * any of the specified prefixes.
      *
      * (4) dirPath is not longer than the trie and stays on the trie the whole
      * time, which means it is included (since at least some longer prefix
      * includes it).
      */

     if (rootTrieNode.hasPrefixes) {
       // Case (1).
       return true;
     }

     TrieNode parentNode = rootTrieNode;
     String[] parts = dirPath.split("/");
     for (String part : parts) {
       assert (!"".equals(part));
       TrieNode childNode = parentNode.findChild(part);
       if (childNode != null) {
         if (childNode.hasPrefixes) {
           // Case (2).
           return true;
         }

         // Haven't found a path prefix yet, so keep walking.
         parentNode = childNode;
       } else {
         // Case (3).
         return false;
       }
     }

     // Case (4).
     return true;
   }

   /**
    * Determines whether or not a given resource should be allowed by this path
    * prefix set and the corresponding filters.
    *
    * @param resourceAbstractPathName
    * @return matching <code>PathPrefix</code> if the resource matches some
    *         specified prefix and any associated filters don't exclude it.
    *         Otherwise, returns null. So it returns null if either no prefixes
    *         match or the most specific prefix excludes the resource.
    */
   public ResourceResolution includesResource(String resourceAbstractPathName) {
     String[] parts = resourceAbstractPathName.split("/");
     return includesResource(resourceAbstractPathName, parts);
   }

   /**
    * Dives down the package hierarchy looking for the most specific
    * package that applies to this resource. The filter of the most specific
    * package is the final determiner of inclusion/exclusion, such that more
    * specific subpackages can override the filter settings on less specific
    * superpackages.
    */
   public ResourceResolution includesResource(String resourceAbstractPathName,
       String[] parts) {
     assertValidAbstractResourcePathName(resourceAbstractPathName);

     ResourceResolution resourceResolution = new ResourceResolution();
     TrieNode currentNode = rootTrieNode;
     List<PathPrefix> mostSpecificPrefixes = rootTrieNode.getPathPrefixes();

     // Walk all but the last path part, which is assumed to be a file name.
     for (String part : parts) {
       assert (!"".equals(part));
       TrieNode childNode = currentNode.findChild(part);
       if (childNode == null) {
         break;
       }

       // We found a more specific node.
       if (childNode.hasPrefixes) {
         List<PathPrefix>  moreSpecificPrefixes = childNode.getPathPrefixes();
         // If PathPrefix->Module associations are accurate because PathPrefixes haven't been merged.
         if (!mergePathPrefixes) {
           // Record the module name of every PathPrefix that would allow this
           // resource. This enables detailed dependency validity checking.
           for (PathPrefix candidatePrefix : moreSpecificPrefixes) {
             if (candidatePrefix.getJudgement(
                 resourceAbstractPathName).isInclude()) {
               resourceResolution.addSourceModuleName(
                   candidatePrefix.getModuleName());
             }
           }
         }

         mostSpecificPrefixes = moreSpecificPrefixes;
       }
       currentNode = childNode;
     }

     PathPrefix chiefPrefix = null;
     Judgement chiefJudgement = null;
     for (PathPrefix candidatePrefix : mostSpecificPrefixes) {
       Judgement judgement = candidatePrefix.getJudgement(
           resourceAbstractPathName);

       // EXCLUSION_EXCLUDE > FILTER_INCLUDE > IMPLICIT_EXCLUDE
       if (chiefJudgement == null ||
           judgement.getPriority() > chiefJudgement.getPriority()) {
         chiefPrefix = candidatePrefix;
         chiefJudgement = judgement;
       }
     }

     if (chiefPrefix == null || !chiefJudgement.isInclude()) {
       return null;
     }

     resourceResolution.setPathPrefix(chiefPrefix);
     return resourceResolution;
   }

   public boolean mergePathPrefixes() {
     return mergePathPrefixes;
   }

   @Override
   public String toString() {
     return rootTrieNode.toString();
   }

   public Collection<PathPrefix> values() {
     return Collections.unmodifiableCollection(prefixes);
   }

   private void assertValidAbstractDirectoryPathName(String name) {
     assert (name != null);
     assert (!name.startsWith("/"));
   }

   private void assertValidAbstractResourcePathName(String name) {
     assert (name != null);
     assert (!"".equals(name));
     assert (!name.startsWith("/") && !name.endsWith("/"));
   }
 }
	/*
	* 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.resource.impl;

	import com.google.gwt.dev.resource.impl.PathPrefix.Judgement;
	import com.google.gwt.dev.util.StringInterner;
	import com.google.gwt.dev.util.collect.Maps;
	import com.google.gwt.thirdparty.guava.common.collect.Lists;

	import java.util.ArrayList;
	import java.util.Collection;
	import java.util.Collections;
	import java.util.List;
	import java.util.Map;

	/**
	* Combines the information conveyed about a set of path prefixes to quickly
	* answer questions regarding an entire set of path prefixes.
	* <p>
	* Is effectively immutable and should not be modified after initial use.
	*/
	public class PathPrefixSet {
	/*
	* (1) TODO(amitmanjhi): Improve the api of the PathPrefixSet so that with one
	* trie-traversal, it could be found out which resources rooted at a directory
	* are allowed?
	*/

	private class TrieNode {
	// TODO(amitmanjhi): Consider the memory-speed tradeoff here
	private Map<String, TrieNode> children = Maps.create();
	private final String part;
	private List<PathPrefix> prefixes = Lists.newArrayList();
	private boolean hasPrefixes = false;

	public TrieNode(String part) {
	this.part = StringInterner.get().intern(part);
	}

	public TrieNode addChild(String part) {
	part = StringInterner.get().intern(part);
	TrieNode newChild = new TrieNode(part);
	assert !children.containsKey(part);
	children = Maps.put(children, part, newChild);
	return newChild;
	}

	public void addPathPrefix(PathPrefix prefix) {
	hasPrefixes = true;
	if (mergePathPrefixes) {
	if (prefixes.isEmpty()) {
	prefixes.add(prefix);
	} else {
	prefixes.get(0).merge(prefix);
	}
	} else {
	prefixes.add(prefix);
	}
	}

	public TrieNode findChild(String part) {
	return children.get(part);
	}

	public List<PathPrefix> getPathPrefixes() {
	return prefixes;
	}

	@Override
	public String toString() {
	StringBuilder sb = new StringBuilder();
	toString(sb, "");
	return sb.toString();
	}

	private void toString(StringBuilder sb, String indent) {
	if (sb.length() > 0) {
	sb.append('\n');
	}
	sb.append(indent);
	sb.append(' ');
	sb.append(part);
	for (TrieNode child : children.values()) {
	child.toString(sb, indent + " ");
	}
	}
	}

	/**
	* Whether or not to merge prefixes that are added. Merged prefixes perform better during resource
	* scanning but at the cost of not being able to tell which module(s) are responsible for a
	* particular resource inclusion.
	*/
	private boolean mergePathPrefixes = true;

	/**
	* List of all path prefixes in priority order.
	*/
	private final List<PathPrefix> prefixes = new ArrayList<PathPrefix>();

	private final TrieNode rootTrieNode = new TrieNode("/");

	public PathPrefixSet() {
	this(true);
	}

	public PathPrefixSet(boolean mergePathPrefixes) {
	this.mergePathPrefixes = mergePathPrefixes;
	}

	/**
	* @param prefix the prefix to add
	* @return <code>true</code> if the prefix was not already in the set;
	* otherwise, it merged with one having the same prefix, which has
	* the effect of expanding the filter (the merge works as
	* <code>union(includes - skips) - union(excludes)</code>)
	*/
	public boolean add(PathPrefix prefix) {
	prefix.setPriority(prefixes.size());
	prefixes.add(prefix);

	String pathPrefix = prefix.getPrefix();

	/*
	* An empty prefix means we have no prefix requirement, but we do attach the
	* prefix to the root so that we can apply the filter.
	*/
	if ("".equals(pathPrefix)) {
	rootTrieNode.addPathPrefix(prefix);
	return false;
	}

	// TODO(bruce): consider not using split for speed
	String[] parts = pathPrefix.split("/");
	TrieNode parentNode = rootTrieNode;
	boolean didAdd = false;
	for (String part : parts) {
	TrieNode childNode = parentNode.findChild(part);
	if (childNode != null) {
	// Follow existing branch.
	parentNode = childNode;
	} else {
	// Add a new branch.
	parentNode = parentNode.addChild(part);
	didAdd = true;
	}
	}
	assert (parentNode != null);
	parentNode.addPathPrefix(prefix);
	return didAdd;
	}

	public int getSize() {
	return prefixes.size();
	}

	/**
	* Determines whether or not a directory might have resources that could be
	* included. The primary purpose of this method is to allow
	* {@link ClassPathEntry} subclasses to avoid descending into directory
	* hierarchies that could not possibly contain resources that would be
	* included by {@link #includesResource(String)}
	*
	* @param dirPath must be a valid abstract directory name (must not be an
	* empty string)
	* @return true if some PathPrefix allows the directory
	*/
	public boolean includesDirectory(String dirPath) {
	assertValidAbstractDirectoryPathName(dirPath);

	/*
	* There are four cases:
	*
	* (1) The empty string was specified as a prefix, which causes everything
	* to be included.
	*
	* (2) As we walk the parts of dirPath, we see a path prefix attached to one
	* of the trie nodes we encounter. This means that there was a specified
	* prefix that this dirPath falls underneath, so it is included.
	*
	* (3) dirPath is longer than the trie, but we never encounter a path prefix
	* as we walk the trie. This indicates that this directory doesn't fall into
	* any of the specified prefixes.
	*
	* (4) dirPath is not longer than the trie and stays on the trie the whole
	* time, which means it is included (since at least some longer prefix
	* includes it).
	*/

	if (rootTrieNode.hasPrefixes) {
	// Case (1).
	return true;
	}

	TrieNode parentNode = rootTrieNode;
	String[] parts = dirPath.split("/");
	for (String part : parts) {
	assert (!"".equals(part));
	TrieNode childNode = parentNode.findChild(part);
	if (childNode != null) {
	if (childNode.hasPrefixes) {
	// Case (2).
	return true;
	}

	// Haven't found a path prefix yet, so keep walking.
	parentNode = childNode;
	} else {
	// Case (3).
	return false;
	}
	}

	// Case (4).
	return true;
	}

	/**
	* Determines whether or not a given resource should be allowed by this path
	* prefix set and the corresponding filters.
	*
	* @param resourceAbstractPathName
	* @return matching <code>PathPrefix</code> if the resource matches some
	* specified prefix and any associated filters don't exclude it.
	* Otherwise, returns null. So it returns null if either no prefixes
	* match or the most specific prefix excludes the resource.
	*/
	public ResourceResolution includesResource(String resourceAbstractPathName) {
	String[] parts = resourceAbstractPathName.split("/");
	return includesResource(resourceAbstractPathName, parts);
	}

	/**
	* Dives down the package hierarchy looking for the most specific
	* package that applies to this resource. The filter of the most specific
	* package is the final determiner of inclusion/exclusion, such that more
	* specific subpackages can override the filter settings on less specific
	* superpackages.
	*/
	public ResourceResolution includesResource(String resourceAbstractPathName,
	String[] parts) {
	assertValidAbstractResourcePathName(resourceAbstractPathName);

	ResourceResolution resourceResolution = new ResourceResolution();
	TrieNode currentNode = rootTrieNode;
	List<PathPrefix> mostSpecificPrefixes = rootTrieNode.getPathPrefixes();

	// Walk all but the last path part, which is assumed to be a file name.
	for (String part : parts) {
	assert (!"".equals(part));
	TrieNode childNode = currentNode.findChild(part);
	if (childNode == null) {
	break;
	}

	// We found a more specific node.
	if (childNode.hasPrefixes) {
	List<PathPrefix> moreSpecificPrefixes = childNode.getPathPrefixes();
	// If PathPrefix->Module associations are accurate because PathPrefixes haven't been merged.
	if (!mergePathPrefixes) {
	// Record the module name of every PathPrefix that would allow this
	// resource. This enables detailed dependency validity checking.
	for (PathPrefix candidatePrefix : moreSpecificPrefixes) {
	if (candidatePrefix.getJudgement(
	resourceAbstractPathName).isInclude()) {
	resourceResolution.addSourceModuleName(
	candidatePrefix.getModuleName());
	}
	}
	}

	mostSpecificPrefixes = moreSpecificPrefixes;
	}
	currentNode = childNode;
	}

	PathPrefix chiefPrefix = null;
	Judgement chiefJudgement = null;
	for (PathPrefix candidatePrefix : mostSpecificPrefixes) {
	Judgement judgement = candidatePrefix.getJudgement(
	resourceAbstractPathName);

	// EXCLUSION_EXCLUDE > FILTER_INCLUDE > IMPLICIT_EXCLUDE
	if (chiefJudgement == null \|\|
	judgement.getPriority() > chiefJudgement.getPriority()) {
	chiefPrefix = candidatePrefix;
	chiefJudgement = judgement;
	}
	}

	if (chiefPrefix == null \|\| !chiefJudgement.isInclude()) {
	return null;
	}

	resourceResolution.setPathPrefix(chiefPrefix);
	return resourceResolution;
	}

	public boolean mergePathPrefixes() {
	return mergePathPrefixes;
	}

	@Override
	public String toString() {
	return rootTrieNode.toString();
	}

	public Collection<PathPrefix> values() {
	return Collections.unmodifiableCollection(prefixes);
	}

	private void assertValidAbstractDirectoryPathName(String name) {
	assert (name != null);
	assert (!name.startsWith("/"));
	}

	private void assertValidAbstractResourcePathName(String name) {
	assert (name != null);
	assert (!"".equals(name));
	assert (!name.startsWith("/") && !name.endsWith("/"));
	}
	}