1 /* 2 * Copyright (C) 2011 The Android Open Source Project 3 * 4 * Licensed under the Eclipse Public License, Version 1.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.eclipse.org/org/documents/epl-v10.php 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 package com.android.ide.common.layout.relative; 17 18 import static com.android.ide.common.layout.LayoutConstants.ANDROID_URI; 19 import static com.android.ide.common.layout.LayoutConstants.ATTR_ID; 20 import static com.android.ide.common.layout.LayoutConstants.ATTR_LAYOUT_PREFIX; 21 import static com.android.ide.common.layout.LayoutConstants.VALUE_TRUE; 22 23 import com.android.ide.common.api.IDragElement; 24 import com.android.ide.common.api.IDragElement.IDragAttribute; 25 import com.android.ide.common.api.INode; 26 import com.android.ide.common.api.INode.IAttribute; 27 import com.android.ide.common.layout.BaseLayoutRule; 28 29 import java.util.ArrayList; 30 import java.util.Collection; 31 import java.util.HashMap; 32 import java.util.HashSet; 33 import java.util.List; 34 import java.util.Map; 35 import java.util.Set; 36 37 /** 38 * Data structure about relative layout relationships which makes it possible to: 39 * <ul> 40 * <li> Quickly determine not just the dependencies on other nodes, but which nodes 41 * depend on this node such that they can be visualized for the selection 42 * <li> Determine if there are cyclic dependencies, and whether a potential move 43 * would result in a cycle 44 * <li> Determine the "depth" of a given node (in terms of how many connections it 45 * is away from a parent edge) such that we can prioritize connections which 46 * minimizes the depth 47 * </ul> 48 */ 49 class DependencyGraph { 50 /** Format to chain include cycles in: a=>b=>c=>d etc */ 51 static final String CHAIN_FORMAT = "%1$s=>%2$s"; //$NON-NLS-1$ 52 53 /** Format to chain constraint dependencies: button 1 above button2 etc */ 54 private static final String DEPENDENCY_FORMAT = "%1$s %2$s %3$s"; //$NON-NLS-1$ 55 56 private final Map<String, ViewData> mIdToView = new HashMap<String, ViewData>(); 57 private final Map<INode, ViewData> mNodeToView = new HashMap<INode, ViewData>(); 58 59 /** Constructs a new {@link DependencyGraph} for the given relative layout */ 60 DependencyGraph(INode layout) { 61 INode[] nodes = layout.getChildren(); 62 63 // Parent view: 64 String parentId = layout.getStringAttr(ANDROID_URI, ATTR_ID); 65 if (parentId != null) { 66 parentId = BaseLayoutRule.stripIdPrefix(parentId); 67 } else { 68 parentId = "RelativeLayout"; // For display purposes; we never reference 69 // the parent id from a constraint, only via parent-relative params 70 // like centerInParent 71 } 72 ViewData parentView = new ViewData(layout, parentId); 73 mNodeToView.put(layout, parentView); 74 if (parentId != null) { 75 mIdToView.put(parentId, parentView); 76 } 77 78 for (INode child : nodes) { 79 String id = child.getStringAttr(ANDROID_URI, ATTR_ID); 80 if (id != null) { 81 id = BaseLayoutRule.stripIdPrefix(id); 82 } 83 ViewData view = new ViewData(child, id); 84 mNodeToView.put(child, view); 85 if (id != null) { 86 mIdToView.put(id, view); 87 } 88 } 89 90 for (ViewData view : mNodeToView.values()) { 91 for (IAttribute attribute : view.node.getLiveAttributes()) { 92 String name = attribute.getName(); 93 ConstraintType type = ConstraintType.fromAttribute(name); 94 if (type != null) { 95 String value = attribute.getValue(); 96 97 if (type.targetParent) { 98 if (value.equals(VALUE_TRUE)) { 99 Constraint constraint = new Constraint(type, view, parentView); 100 view.dependsOn.add(constraint); 101 parentView.dependedOnBy.add(constraint); 102 } 103 } else { 104 // id-based constraint. 105 // NOTE: The id could refer to some widget that is NOT a sibling! 106 String targetId = BaseLayoutRule.stripIdPrefix(value); 107 ViewData target = mIdToView.get(targetId); 108 if (target == view) { 109 // Self-reference. RelativeLayout ignores these so it's 110 // not an error like a deeper cycle (where RelativeLayout 111 // will throw an exception), but we might as well warn 112 // the user about it. 113 // TODO: Where do we emit this error? 114 } else if (target != null) { 115 Constraint constraint = new Constraint(type, view, target); 116 view.dependsOn.add(constraint); 117 target.dependedOnBy.add(constraint); 118 } else { 119 // This is valid but we might want to warn... 120 //System.out.println("Warning: no view data found for " + targetId); 121 } 122 } 123 } 124 } 125 } 126 } 127 128 public ViewData getView(IDragElement element) { 129 IDragAttribute attribute = element.getAttribute(ANDROID_URI, ATTR_ID); 130 if (attribute != null) { 131 String id = attribute.getValue(); 132 id = BaseLayoutRule.stripIdPrefix(id); 133 return getView(id); 134 } 135 136 return null; 137 } 138 139 public ViewData getView(String id) { 140 return mIdToView.get(id); 141 } 142 143 public ViewData getView(INode node) { 144 return mNodeToView.get(node); 145 } 146 147 /** 148 * Returns the set of views that depend on the given node in either the horizontal or 149 * vertical direction 150 * 151 * @param nodes the set of nodes that we want to compute the transitive dependencies 152 * for 153 * @param vertical if true, look for vertical edge dependencies, otherwise look for 154 * horizontal edge dependencies 155 * @return the set of nodes that directly or indirectly depend on the given nodes in 156 * the given direction 157 */ 158 public Set<INode> dependsOn(Collection<? extends INode> nodes, boolean vertical) { 159 List<ViewData> reachable = new ArrayList<ViewData>(); 160 161 // Traverse the graph of constraints and determine all nodes affected by 162 // this node 163 Set<ViewData> visiting = new HashSet<ViewData>(); 164 for (INode node : nodes) { 165 ViewData view = mNodeToView.get(node); 166 if (view != null) { 167 findBackwards(view, visiting, reachable, vertical, view); 168 } 169 } 170 171 Set<INode> dependents = new HashSet<INode>(reachable.size()); 172 173 for (ViewData v : reachable) { 174 dependents.add(v.node); 175 } 176 177 return dependents; 178 } 179 180 private void findBackwards(ViewData view, 181 Set<ViewData> visiting, List<ViewData> reachable, 182 boolean vertical, ViewData start) { 183 visiting.add(view); 184 reachable.add(view); 185 186 for (Constraint constraint : view.dependedOnBy) { 187 if (vertical && !constraint.type.verticalEdge) { 188 continue; 189 } else if (!vertical && !constraint.type.horizontalEdge) { 190 continue; 191 } 192 193 assert constraint.to == view; 194 ViewData from = constraint.from; 195 if (visiting.contains(from)) { 196 // Cycle - what do we do to highlight this? 197 List<Constraint> path = getPathTo(start.node, view.node, vertical); 198 if (path != null) { 199 // TODO: display to the user somehow. We need log access for the 200 // view rules. 201 System.out.println(Constraint.describePath(path, null, null)); 202 } 203 } else { 204 findBackwards(from, visiting, reachable, vertical, start); 205 } 206 } 207 208 visiting.remove(view); 209 } 210 211 public List<Constraint> getPathTo(INode from, INode to, boolean vertical) { 212 // Traverse the graph of constraints and determine all nodes affected by 213 // this node 214 Set<ViewData> visiting = new HashSet<ViewData>(); 215 List<Constraint> path = new ArrayList<Constraint>(); 216 ViewData view = mNodeToView.get(from); 217 if (view != null) { 218 return findForwards(view, visiting, path, vertical, to); 219 } 220 221 return null; 222 } 223 224 private List<Constraint> findForwards(ViewData view, Set<ViewData> visiting, 225 List<Constraint> path, boolean vertical, INode target) { 226 visiting.add(view); 227 228 for (Constraint constraint : view.dependsOn) { 229 if (vertical && !constraint.type.verticalEdge) { 230 continue; 231 } else if (!vertical && !constraint.type.horizontalEdge) { 232 continue; 233 } 234 235 try { 236 path.add(constraint); 237 238 if (constraint.to.node == target) { 239 return new ArrayList<Constraint>(path); 240 } 241 242 assert constraint.from == view; 243 ViewData to = constraint.to; 244 if (visiting.contains(to)) { 245 // CYCLE! 246 continue; 247 } 248 249 List<Constraint> chain = findForwards(to, visiting, path, vertical, target); 250 if (chain != null) { 251 return chain; 252 } 253 } finally { 254 path.remove(constraint); 255 } 256 } 257 258 visiting.remove(view); 259 260 return null; 261 } 262 263 /** 264 * Info about a specific widget child of a relative layout and its constraints. This 265 * is a node in the dependency graph. 266 */ 267 static class ViewData { 268 public final INode node; 269 public final String id; 270 public final List<Constraint> dependsOn = new ArrayList<Constraint>(4); 271 public final List<Constraint> dependedOnBy = new ArrayList<Constraint>(8); 272 273 ViewData(INode node, String id) { 274 this.node = node; 275 this.id = id; 276 } 277 } 278 279 /** 280 * Info about a specific constraint between two widgets in a relative layout. This is 281 * an edge in the dependency graph. 282 */ 283 static class Constraint { 284 public final ConstraintType type; 285 public final ViewData from; 286 public final ViewData to; 287 288 // TODO: Initialize depth -- should be computed independently for top, left, etc. 289 // We can use this in GuidelineHandler.MatchComparator to prefer matches that 290 // are closer to a parent edge: 291 //public int depth; 292 293 Constraint(ConstraintType type, ViewData from, ViewData to) { 294 this.type = type; 295 this.from = from; 296 this.to = to; 297 } 298 299 static String describePath(List<Constraint> path, String newName, String newId) { 300 String s = ""; 301 for (int i = path.size() - 1; i >= 0; i--) { 302 Constraint constraint = path.get(i); 303 String suffix = (i == path.size() -1) ? constraint.to.id : s; 304 s = String.format(DEPENDENCY_FORMAT, constraint.from.id, 305 stripLayoutAttributePrefix(constraint.type.name), suffix); 306 } 307 308 if (newName != null) { 309 s = String.format(DEPENDENCY_FORMAT, s, stripLayoutAttributePrefix(newName), 310 BaseLayoutRule.stripIdPrefix(newId)); 311 } 312 313 return s; 314 } 315 316 private static String stripLayoutAttributePrefix(String name) { 317 if (name.startsWith(ATTR_LAYOUT_PREFIX)) { 318 return name.substring(ATTR_LAYOUT_PREFIX.length()); 319 } 320 321 return name; 322 } 323 } 324 } 325