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