eclipse/plugins/com.android.ide.eclipse.adt/src/com/android/ide/common/layout/relative/DependencyGraph.java - platform/sdk - Git at Google

 /*
  * Copyright (C) 2011 The Android Open Source Project
  *
  * Licensed under the Eclipse Public License, Version 1.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.eclipse.org/org/documents/epl-v10.php
  *
  * 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.android.ide.common.layout.relative;

 import static com.android.SdkConstants.ATTR_ID;
 import static com.android.SdkConstants.ATTR_LAYOUT_RESOURCE_PREFIX;
 import static com.android.SdkConstants.VALUE_TRUE;


 import com.android.SdkConstants;
 import static com.android.SdkConstants.ANDROID_URI;
 import com.android.ide.common.api.IDragElement;
 import com.android.ide.common.api.IDragElement.IDragAttribute;
 import com.android.ide.common.api.INode;
 import com.android.ide.common.api.INode.IAttribute;
 import com.android.ide.common.layout.BaseLayoutRule;

 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;

 /**
  * Data structure about relative layout relationships which makes it possible to:
  * <ul>
  * <li> Quickly determine not just the dependencies on other nodes, but which nodes
  *    depend on this node such that they can be visualized for the selection
  * <li> Determine if there are cyclic dependencies, and whether a potential move
  *    would result in a cycle
  * <li> Determine the "depth" of a given node (in terms of how many connections it
  *     is away from a parent edge) such that we can prioritize connections which
  *     minimizes the depth
  * </ul>
  */
 class DependencyGraph {
     /** Format to chain include cycles in: a=>b=>c=>d etc */
     static final String CHAIN_FORMAT = "%1$s=>%2$s"; //$NON-NLS-1$

     /** Format to chain constraint dependencies: button 1 above button2 etc */
     private static final String DEPENDENCY_FORMAT = "%1$s %2$s %3$s"; //$NON-NLS-1$

     private final Map<String, ViewData> mIdToView = new HashMap<String, ViewData>();
     private final Map<INode, ViewData> mNodeToView = new HashMap<INode, ViewData>();

     /** Constructs a new {@link DependencyGraph} for the given relative layout */
     DependencyGraph(INode layout) {
         INode[] nodes = layout.getChildren();

         // Parent view:
         String parentId = layout.getStringAttr(ANDROID_URI, ATTR_ID);
         if (parentId != null) {
             parentId = BaseLayoutRule.stripIdPrefix(parentId);
         } else {
             parentId = "RelativeLayout"; // For display purposes; we never reference
             // the parent id from a constraint, only via parent-relative params
             // like centerInParent
         }
         ViewData parentView = new ViewData(layout, parentId);
         mNodeToView.put(layout, parentView);
         if (parentId != null) {
             mIdToView.put(parentId, parentView);
         }

         for (INode child : nodes) {
             String id = child.getStringAttr(ANDROID_URI, ATTR_ID);
             if (id != null) {
                 id = BaseLayoutRule.stripIdPrefix(id);
             }
             ViewData view = new ViewData(child, id);
             mNodeToView.put(child, view);
             if (id != null) {
                 mIdToView.put(id, view);
             }
         }

         for (ViewData view : mNodeToView.values()) {
             for (IAttribute attribute : view.node.getLiveAttributes()) {
                 String name = attribute.getName();
                 ConstraintType type = ConstraintType.fromAttribute(name);
                 if (type != null) {
                     String value = attribute.getValue();

                     if (type.targetParent) {
                         if (value.equals(VALUE_TRUE)) {
                             Constraint constraint = new Constraint(type, view, parentView);
                             view.dependsOn.add(constraint);
                             parentView.dependedOnBy.add(constraint);
                         }
                     } else {
                         // id-based constraint.
                         // NOTE: The id could refer to some widget that is NOT a sibling!
                         String targetId = BaseLayoutRule.stripIdPrefix(value);
                         ViewData target = mIdToView.get(targetId);
                         if (target == view) {
                             // Self-reference. RelativeLayout ignores these so it's
                             // not an error like a deeper cycle (where RelativeLayout
                             // will throw an exception), but we might as well warn
                             // the user about it.
                             // TODO: Where do we emit this error?
                         } else if (target != null) {
                             Constraint constraint = new Constraint(type, view, target);
                             view.dependsOn.add(constraint);
                             target.dependedOnBy.add(constraint);
                         } else {
                             // This is valid but we might want to warn...
                             //System.out.println("Warning: no view data found for " + targetId);
                         }
                     }
                 }
             }
         }
     }

     public ViewData getView(IDragElement element) {
         IDragAttribute attribute = element.getAttribute(ANDROID_URI, ATTR_ID);
         if (attribute != null) {
             String id = attribute.getValue();
             id = BaseLayoutRule.stripIdPrefix(id);
             return getView(id);
         }

         return null;
     }

     public ViewData getView(String id) {
         return mIdToView.get(id);
     }

     public ViewData getView(INode node) {
         return mNodeToView.get(node);
     }

     /**
      * Returns the set of views that depend on the given node in either the horizontal or
      * vertical direction
      *
      * @param nodes the set of nodes that we want to compute the transitive dependencies
      *            for
      * @param vertical if true, look for vertical edge dependencies, otherwise look for
      *            horizontal edge dependencies
      * @return the set of nodes that directly or indirectly depend on the given nodes in
      *         the given direction
      */
     public Set<INode> dependsOn(Collection<? extends INode> nodes, boolean vertical) {
         List<ViewData> reachable = new ArrayList<ViewData>();

         // Traverse the graph of constraints and determine all nodes affected by
         // this node
         Set<ViewData> visiting = new HashSet<ViewData>();
         for (INode node : nodes) {
             ViewData view = mNodeToView.get(node);
             if (view != null) {
                 findBackwards(view, visiting, reachable, vertical, view);
             }
         }

         Set<INode> dependents = new HashSet<INode>(reachable.size());

         for (ViewData v : reachable) {
             dependents.add(v.node);
         }

         return dependents;
     }

     private void findBackwards(ViewData view,
             Set<ViewData> visiting, List<ViewData> reachable,
             boolean vertical, ViewData start) {
         visiting.add(view);
         reachable.add(view);

         for (Constraint constraint : view.dependedOnBy) {
             if (vertical && !constraint.type.verticalEdge) {
                 continue;
             } else  if (!vertical && !constraint.type.horizontalEdge) {
                 continue;
             }

             assert constraint.to == view;
             ViewData from = constraint.from;
             if (visiting.contains(from)) {
                 // Cycle - what do we do to highlight this?
                 List<Constraint> path = getPathTo(start.node, view.node, vertical);
                 if (path != null) {
                     // TODO: display to the user somehow. We need log access for the
                     // view rules.
                     System.out.println(Constraint.describePath(path, null, null));
                 }
             } else {
                 findBackwards(from, visiting, reachable, vertical, start);
             }
         }

         visiting.remove(view);
     }

     public List<Constraint> getPathTo(INode from, INode to, boolean vertical) {
         // Traverse the graph of constraints and determine all nodes affected by
         // this node
         Set<ViewData> visiting = new HashSet<ViewData>();
         List<Constraint> path = new ArrayList<Constraint>();
         ViewData view = mNodeToView.get(from);
         if (view != null) {
             return findForwards(view, visiting, path, vertical, to);
         }

         return null;
     }

     private List<Constraint> findForwards(ViewData view, Set<ViewData> visiting,
             List<Constraint> path, boolean vertical, INode target) {
         visiting.add(view);

         for (Constraint constraint : view.dependsOn) {
             if (vertical && !constraint.type.verticalEdge) {
                 continue;
             } else  if (!vertical && !constraint.type.horizontalEdge) {
                 continue;
             }

             try {
                 path.add(constraint);

                 if (constraint.to.node == target) {
                     return new ArrayList<Constraint>(path);
                 }

                 assert constraint.from == view;
                 ViewData to = constraint.to;
                 if (visiting.contains(to)) {
                     // CYCLE!
                     continue;
                 }

                 List<Constraint> chain = findForwards(to, visiting, path, vertical, target);
                 if (chain != null) {
                     return chain;
                 }
             } finally {
                 path.remove(constraint);
             }
         }

         visiting.remove(view);

         return null;
     }

     /**
      * Info about a specific widget child of a relative layout and its constraints. This
      * is a node in the dependency graph.
      */
     static class ViewData {
         public final INode node;
         public final String id;
         public final List<Constraint> dependsOn = new ArrayList<Constraint>(4);
         public final List<Constraint> dependedOnBy = new ArrayList<Constraint>(8);

         ViewData(INode node, String id) {
             this.node = node;
             this.id = id;
         }
     }

     /**
      * Info about a specific constraint between two widgets in a relative layout. This is
      * an edge in the dependency graph.
      */
     static class Constraint {
         public final ConstraintType type;
         public final ViewData from;
         public final ViewData to;

         // TODO: Initialize depth -- should be computed independently for top, left, etc.
         // We can use this in GuidelineHandler.MatchComparator to prefer matches that
         // are closer to a parent edge:
         //public int depth;

         Constraint(ConstraintType type, ViewData from, ViewData to) {
             this.type = type;
             this.from = from;
             this.to = to;
         }

         static String describePath(List<Constraint> path, String newName, String newId) {
             String s = "";
             for (int i = path.size() - 1; i >= 0; i--) {
                 Constraint constraint = path.get(i);
                 String suffix = (i == path.size() -1) ? constraint.to.id : s;
                 s = String.format(DEPENDENCY_FORMAT, constraint.from.id,
                         stripLayoutAttributePrefix(constraint.type.name), suffix);
             }

             if (newName != null) {
                 s = String.format(DEPENDENCY_FORMAT, s, stripLayoutAttributePrefix(newName),
                         BaseLayoutRule.stripIdPrefix(newId));
             }

             return s;
         }

         private static String stripLayoutAttributePrefix(String name) {
             if (name.startsWith(ATTR_LAYOUT_RESOURCE_PREFIX)) {
                 return name.substring(ATTR_LAYOUT_RESOURCE_PREFIX.length());
             }

             return name;
         }
     }
 }
	/*
	* Copyright (C) 2011 The Android Open Source Project
	*
	* Licensed under the Eclipse Public License, Version 1.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.eclipse.org/org/documents/epl-v10.php
	*
	* 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.android.ide.common.layout.relative;

	import static com.android.SdkConstants.ATTR_ID;
	import static com.android.SdkConstants.ATTR_LAYOUT_RESOURCE_PREFIX;
	import static com.android.SdkConstants.VALUE_TRUE;


	import com.android.SdkConstants;
	import static com.android.SdkConstants.ANDROID_URI;
	import com.android.ide.common.api.IDragElement;
	import com.android.ide.common.api.IDragElement.IDragAttribute;
	import com.android.ide.common.api.INode;
	import com.android.ide.common.api.INode.IAttribute;
	import com.android.ide.common.layout.BaseLayoutRule;

	import java.util.ArrayList;
	import java.util.Collection;
	import java.util.HashMap;
	import java.util.HashSet;
	import java.util.List;
	import java.util.Map;
	import java.util.Set;

	/**
	* Data structure about relative layout relationships which makes it possible to:
	* <ul>
	* <li> Quickly determine not just the dependencies on other nodes, but which nodes
	* depend on this node such that they can be visualized for the selection
	* <li> Determine if there are cyclic dependencies, and whether a potential move
	* would result in a cycle
	* <li> Determine the "depth" of a given node (in terms of how many connections it
	* is away from a parent edge) such that we can prioritize connections which
	* minimizes the depth
	* </ul>
	*/
	class DependencyGraph {
	/** Format to chain include cycles in: a=>b=>c=>d etc */
	static final String CHAIN_FORMAT = "%1$s=>%2$s"; //$NON-NLS-1$

	/** Format to chain constraint dependencies: button 1 above button2 etc */
	private static final String DEPENDENCY_FORMAT = "%1$s %2$s %3$s"; //$NON-NLS-1$

	private final Map<String, ViewData> mIdToView = new HashMap<String, ViewData>();
	private final Map<INode, ViewData> mNodeToView = new HashMap<INode, ViewData>();

	/** Constructs a new {@link DependencyGraph} for the given relative layout */
	DependencyGraph(INode layout) {
	INode[] nodes = layout.getChildren();

	// Parent view:
	String parentId = layout.getStringAttr(ANDROID_URI, ATTR_ID);
	if (parentId != null) {
	parentId = BaseLayoutRule.stripIdPrefix(parentId);
	} else {
	parentId = "RelativeLayout"; // For display purposes; we never reference
	// the parent id from a constraint, only via parent-relative params
	// like centerInParent
	}
	ViewData parentView = new ViewData(layout, parentId);
	mNodeToView.put(layout, parentView);
	if (parentId != null) {
	mIdToView.put(parentId, parentView);
	}

	for (INode child : nodes) {
	String id = child.getStringAttr(ANDROID_URI, ATTR_ID);
	if (id != null) {
	id = BaseLayoutRule.stripIdPrefix(id);
	}
	ViewData view = new ViewData(child, id);
	mNodeToView.put(child, view);
	if (id != null) {
	mIdToView.put(id, view);
	}
	}

	for (ViewData view : mNodeToView.values()) {
	for (IAttribute attribute : view.node.getLiveAttributes()) {
	String name = attribute.getName();
	ConstraintType type = ConstraintType.fromAttribute(name);
	if (type != null) {
	String value = attribute.getValue();

	if (type.targetParent) {
	if (value.equals(VALUE_TRUE)) {
	Constraint constraint = new Constraint(type, view, parentView);
	view.dependsOn.add(constraint);
	parentView.dependedOnBy.add(constraint);
	}
	} else {
	// id-based constraint.
	// NOTE: The id could refer to some widget that is NOT a sibling!
	String targetId = BaseLayoutRule.stripIdPrefix(value);
	ViewData target = mIdToView.get(targetId);
	if (target == view) {
	// Self-reference. RelativeLayout ignores these so it's
	// not an error like a deeper cycle (where RelativeLayout
	// will throw an exception), but we might as well warn
	// the user about it.
	// TODO: Where do we emit this error?
	} else if (target != null) {
	Constraint constraint = new Constraint(type, view, target);
	view.dependsOn.add(constraint);
	target.dependedOnBy.add(constraint);
	} else {
	// This is valid but we might want to warn...
	//System.out.println("Warning: no view data found for " + targetId);
	}
	}
	}
	}
	}
	}

	public ViewData getView(IDragElement element) {
	IDragAttribute attribute = element.getAttribute(ANDROID_URI, ATTR_ID);
	if (attribute != null) {
	String id = attribute.getValue();
	id = BaseLayoutRule.stripIdPrefix(id);
	return getView(id);
	}

	return null;
	}

	public ViewData getView(String id) {
	return mIdToView.get(id);
	}

	public ViewData getView(INode node) {
	return mNodeToView.get(node);
	}

	/**
	* Returns the set of views that depend on the given node in either the horizontal or
	* vertical direction
	*
	* @param nodes the set of nodes that we want to compute the transitive dependencies
	* for
	* @param vertical if true, look for vertical edge dependencies, otherwise look for
	* horizontal edge dependencies
	* @return the set of nodes that directly or indirectly depend on the given nodes in
	* the given direction
	*/
	public Set<INode> dependsOn(Collection<? extends INode> nodes, boolean vertical) {
	List<ViewData> reachable = new ArrayList<ViewData>();

	// Traverse the graph of constraints and determine all nodes affected by
	// this node
	Set<ViewData> visiting = new HashSet<ViewData>();
	for (INode node : nodes) {
	ViewData view = mNodeToView.get(node);
	if (view != null) {
	findBackwards(view, visiting, reachable, vertical, view);
	}
	}

	Set<INode> dependents = new HashSet<INode>(reachable.size());

	for (ViewData v : reachable) {
	dependents.add(v.node);
	}

	return dependents;
	}

	private void findBackwards(ViewData view,
	Set<ViewData> visiting, List<ViewData> reachable,
	boolean vertical, ViewData start) {
	visiting.add(view);
	reachable.add(view);

	for (Constraint constraint : view.dependedOnBy) {
	if (vertical && !constraint.type.verticalEdge) {
	continue;
	} else if (!vertical && !constraint.type.horizontalEdge) {
	continue;
	}

	assert constraint.to == view;
	ViewData from = constraint.from;
	if (visiting.contains(from)) {
	// Cycle - what do we do to highlight this?
	List<Constraint> path = getPathTo(start.node, view.node, vertical);
	if (path != null) {
	// TODO: display to the user somehow. We need log access for the
	// view rules.
	System.out.println(Constraint.describePath(path, null, null));
	}
	} else {
	findBackwards(from, visiting, reachable, vertical, start);
	}
	}

	visiting.remove(view);
	}

	public List<Constraint> getPathTo(INode from, INode to, boolean vertical) {
	// Traverse the graph of constraints and determine all nodes affected by
	// this node
	Set<ViewData> visiting = new HashSet<ViewData>();
	List<Constraint> path = new ArrayList<Constraint>();
	ViewData view = mNodeToView.get(from);
	if (view != null) {
	return findForwards(view, visiting, path, vertical, to);
	}

	return null;
	}

	private List<Constraint> findForwards(ViewData view, Set<ViewData> visiting,
	List<Constraint> path, boolean vertical, INode target) {
	visiting.add(view);

	for (Constraint constraint : view.dependsOn) {
	if (vertical && !constraint.type.verticalEdge) {
	continue;
	} else if (!vertical && !constraint.type.horizontalEdge) {
	continue;
	}

	try {
	path.add(constraint);

	if (constraint.to.node == target) {
	return new ArrayList<Constraint>(path);
	}

	assert constraint.from == view;
	ViewData to = constraint.to;
	if (visiting.contains(to)) {
	// CYCLE!
	continue;
	}

	List<Constraint> chain = findForwards(to, visiting, path, vertical, target);
	if (chain != null) {
	return chain;
	}
	} finally {
	path.remove(constraint);
	}
	}

	visiting.remove(view);

	return null;
	}

	/**
	* Info about a specific widget child of a relative layout and its constraints. This
	* is a node in the dependency graph.
	*/
	static class ViewData {
	public final INode node;
	public final String id;
	public final List<Constraint> dependsOn = new ArrayList<Constraint>(4);
	public final List<Constraint> dependedOnBy = new ArrayList<Constraint>(8);

	ViewData(INode node, String id) {
	this.node = node;
	this.id = id;
	}
	}

	/**
	* Info about a specific constraint between two widgets in a relative layout. This is
	* an edge in the dependency graph.
	*/
	static class Constraint {
	public final ConstraintType type;
	public final ViewData from;
	public final ViewData to;

	// TODO: Initialize depth -- should be computed independently for top, left, etc.
	// We can use this in GuidelineHandler.MatchComparator to prefer matches that
	// are closer to a parent edge:
	//public int depth;

	Constraint(ConstraintType type, ViewData from, ViewData to) {
	this.type = type;
	this.from = from;
	this.to = to;
	}

	static String describePath(List<Constraint> path, String newName, String newId) {
	String s = "";
	for (int i = path.size() - 1; i >= 0; i--) {
	Constraint constraint = path.get(i);
	String suffix = (i == path.size() -1) ? constraint.to.id : s;
	s = String.format(DEPENDENCY_FORMAT, constraint.from.id,
	stripLayoutAttributePrefix(constraint.type.name), suffix);
	}

	if (newName != null) {
	s = String.format(DEPENDENCY_FORMAT, s, stripLayoutAttributePrefix(newName),
	BaseLayoutRule.stripIdPrefix(newId));
	}

	return s;
	}

	private static String stripLayoutAttributePrefix(String name) {
	if (name.startsWith(ATTR_LAYOUT_RESOURCE_PREFIX)) {
	return name.substring(ATTR_LAYOUT_RESOURCE_PREFIX.length());
	}

	return name;
	}
	}
	}