1 /* 2 * Copyright (C) 2011 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.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.apache.org/licenses/LICENSE-2.0 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 17 package com.android.tools.lint.checks; 18 19 import static com.android.tools.lint.detector.api.LintConstants.ANDROID_URI; 20 import static com.android.tools.lint.detector.api.LintConstants.ATTR_ID; 21 import static com.android.tools.lint.detector.api.LintConstants.ATTR_LAYOUT; 22 import static com.android.tools.lint.detector.api.LintConstants.DOT_XML; 23 import static com.android.tools.lint.detector.api.LintConstants.INCLUDE; 24 import static com.android.tools.lint.detector.api.LintConstants.LAYOUT_RESOURCE_PREFIX; 25 import static com.android.tools.lint.detector.api.LintConstants.NEW_ID_RESOURCE_PREFIX; 26 27 import com.android.resources.ResourceFolderType; 28 import com.android.tools.lint.detector.api.Category; 29 import com.android.tools.lint.detector.api.Context; 30 import com.android.tools.lint.detector.api.Issue; 31 import com.android.tools.lint.detector.api.LayoutDetector; 32 import com.android.tools.lint.detector.api.LintUtils; 33 import com.android.tools.lint.detector.api.Location; 34 import com.android.tools.lint.detector.api.Scope; 35 import com.android.tools.lint.detector.api.Severity; 36 import com.android.tools.lint.detector.api.Speed; 37 import com.android.tools.lint.detector.api.XmlContext; 38 import com.google.common.collect.ArrayListMultimap; 39 import com.google.common.collect.Multimap; 40 41 import org.w3c.dom.Attr; 42 import org.w3c.dom.Element; 43 import org.w3c.dom.Node; 44 import org.w3c.dom.NodeList; 45 46 import java.io.File; 47 import java.util.ArrayDeque; 48 import java.util.ArrayList; 49 import java.util.Collection; 50 import java.util.Collections; 51 import java.util.Deque; 52 import java.util.HashMap; 53 import java.util.HashSet; 54 import java.util.Iterator; 55 import java.util.List; 56 import java.util.Map; 57 import java.util.Set; 58 59 /** 60 * Checks for duplicate ids within a layout and within an included layout 61 */ 62 public class DuplicateIdDetector extends LayoutDetector { 63 private Set<String> mIds; 64 private Map<File, Set<String>> mFileToIds; 65 private Map<File, List<String>> mIncludes; 66 67 // Data structures used for location collection in phase 2 68 69 // Map from include files to include names to pairs of message and location 70 // Map from file defining id, to the id to be defined, to a pair of location and message 71 private Multimap<File, Multimap<String, Occurrence>> mLocations; 72 private List<Occurrence> mErrors; 73 74 /** The main issue discovered by this detector */ 75 public static final Issue WITHIN_LAYOUT = Issue.create( 76 "DuplicateIds", //$NON-NLS-1$ 77 "Checks for duplicate ids within a single layout", 78 "Within a layout, id's should be unique since otherwise findViewById() can " + 79 "return an unexpected view.", 80 Category.CORRECTNESS, 81 7, 82 Severity.WARNING, 83 DuplicateIdDetector.class, 84 Scope.RESOURCE_FILE_SCOPE); 85 86 /** The main issue discovered by this detector */ 87 public static final Issue CROSS_LAYOUT = Issue.create( 88 "DuplicateIncludedIds", //$NON-NLS-1$ 89 "Checks for duplicate ids across layouts that are combined with include tags", 90 "It's okay for two independent layouts to use the same ids. However, if " + 91 "layouts are combined with include tags, then the id's need to be unique " + 92 "within any chain of included layouts, or Activity#findViewById() can " + 93 "return an unexpected view.", 94 Category.CORRECTNESS, 95 6, 96 Severity.WARNING, 97 DuplicateIdDetector.class, 98 Scope.ALL_RESOURCES_SCOPE); 99 100 /** Constructs a duplicate id check */ 101 public DuplicateIdDetector() { 102 } 103 104 105 @Override 106 public boolean appliesTo(ResourceFolderType folderType) { 107 return folderType == ResourceFolderType.LAYOUT || folderType == ResourceFolderType.MENU; 108 } 109 110 @Override 111 public Speed getSpeed() { 112 return Speed.FAST; 113 } 114 115 @Override 116 public Collection<String> getApplicableAttributes() { 117 return Collections.singletonList(ATTR_ID); 118 } 119 120 @Override 121 public Collection<String> getApplicableElements() { 122 return Collections.singletonList(INCLUDE); 123 } 124 125 @Override 126 public void beforeCheckFile(Context context) { 127 if (context.getPhase() == 1) { 128 mIds = new HashSet<String>(); 129 } 130 } 131 132 @Override 133 public void afterCheckFile(Context context) { 134 if (context.getPhase() == 1) { 135 // Store this layout's set of ids for full project analysis in afterCheckProject 136 mFileToIds.put(context.file, mIds); 137 138 mIds = null; 139 } 140 } 141 142 @Override 143 public void beforeCheckProject(Context context) { 144 if (context.getPhase() == 1) { 145 mFileToIds = new HashMap<File, Set<String>>(); 146 mIncludes = new HashMap<File, List<String>>(); 147 } 148 } 149 150 @Override 151 public void afterCheckProject(Context context) { 152 if (context.getPhase() == 1) { 153 // Look for duplicates 154 if (mIncludes.size() > 0) { 155 // Traverse all the include chains and ensure that there are no duplicates 156 // across. 157 if (context.isEnabled(CROSS_LAYOUT) 158 && context.getScope().contains(Scope.ALL_RESOURCE_FILES)) { 159 IncludeGraph graph = new IncludeGraph(context); 160 graph.check(); 161 } 162 } 163 } else { 164 assert context.getPhase() == 2; 165 166 if (mErrors != null) { 167 for (Occurrence occurrence : mErrors) { 168 //assert location != null : occurrence; 169 Location location = occurrence.location; 170 if (location == null) { 171 location = Location.create(occurrence.file); 172 } else { 173 Object clientData = location.getClientData(); 174 if (clientData instanceof Node) { 175 Node node = (Node) clientData; 176 if (context.getDriver().isSuppressed(CROSS_LAYOUT, node)) { 177 continue; 178 } 179 } 180 } 181 182 List<Occurrence> sorted = new ArrayList<Occurrence>(); 183 Occurrence curr = occurrence.next; 184 while (curr != null) { 185 sorted.add(curr); 186 curr = curr.next; 187 } 188 Collections.sort(sorted); 189 Location prev = location; 190 for (Occurrence o : sorted) { 191 if (o.location != null) { 192 prev.setSecondary(o.location); 193 prev = o.location; 194 } 195 } 196 197 context.report(CROSS_LAYOUT, location, occurrence.message, null); 198 } 199 } 200 } 201 } 202 203 @Override 204 public void visitElement(XmlContext context, Element element) { 205 // Record include graph such that we can look for inter-layout duplicates after the 206 // project has been fully checked 207 208 String layout = element.getAttribute(ATTR_LAYOUT); // NOTE: Not in android: namespace 209 if (layout.startsWith(LAYOUT_RESOURCE_PREFIX)) { // Ignore @android:layout/ layouts 210 layout = layout.substring(LAYOUT_RESOURCE_PREFIX.length()); 211 212 if (context.getPhase() == 1) { 213 List<String> to = mIncludes.get(context.file); 214 if (to == null) { 215 to = new ArrayList<String>(); 216 mIncludes.put(context.file, to); 217 } 218 to.add(layout); 219 } else { 220 assert context.getPhase() == 2; 221 222 Collection<Multimap<String, Occurrence>> maps = mLocations.get(context.file); 223 if (maps != null && maps.size() > 0) { 224 for (Multimap<String, Occurrence> map : maps) { 225 if (maps.size() > 0) { 226 Collection<Occurrence> occurrences = map.get(layout); 227 if (occurrences != null && occurrences.size() > 0) { 228 for (Occurrence occurrence : occurrences) { 229 Location location = context.getLocation(element); 230 location.setClientData(element); 231 location.setMessage(occurrence.message); 232 location.setSecondary(occurrence.location); 233 occurrence.location = location; 234 } 235 } 236 } 237 } 238 } 239 } 240 } 241 } 242 243 @Override 244 public void visitAttribute(XmlContext context, Attr attribute) { 245 assert attribute.getName().equals(ATTR_ID) || attribute.getLocalName().equals(ATTR_ID); 246 String id = attribute.getValue(); 247 if (context.getPhase() == 1) { 248 if (mIds.contains(id)) { 249 Location location = context.getLocation(attribute); 250 251 Attr first = findIdAttribute(attribute.getOwnerDocument(), id); 252 if (first != null && first != attribute) { 253 Location secondLocation = context.getLocation(first); 254 secondLocation.setMessage(String.format("%1$s originally defined here", id)); 255 location.setSecondary(secondLocation); 256 } 257 258 context.report(WITHIN_LAYOUT, attribute, location, 259 String.format("Duplicate id %1$s, already defined earlier in this layout", 260 id), null); 261 } else if (id.startsWith(NEW_ID_RESOURCE_PREFIX)) { 262 // Skip id's on include tags 263 if (attribute.getOwnerElement().getTagName().equals(INCLUDE)) { 264 return; 265 } 266 267 mIds.add(id); 268 } 269 } else { 270 Collection<Multimap<String, Occurrence>> maps = mLocations.get(context.file); 271 if (maps != null && maps.size() > 0) { 272 for (Multimap<String, Occurrence> map : maps) { 273 if (maps.size() > 0) { 274 Collection<Occurrence> occurrences = map.get(id); 275 if (occurrences != null && occurrences.size() > 0) { 276 for (Occurrence occurrence : occurrences) { 277 if (context.getDriver().isSuppressed(CROSS_LAYOUT, attribute)) { 278 return; 279 } 280 Location location = context.getLocation(attribute); 281 location.setClientData(attribute); 282 location.setMessage(occurrence.message); 283 location.setSecondary(occurrence.location); 284 occurrence.location = location; 285 } 286 } 287 } 288 } 289 } 290 } 291 } 292 293 /** Find the first id attribute with the given value below the given node */ 294 private Attr findIdAttribute(Node node, String targetValue) { 295 if (node.getNodeType() == Node.ELEMENT_NODE) { 296 Attr attribute = ((Element) node).getAttributeNodeNS(ANDROID_URI, ATTR_ID); 297 if (attribute != null && attribute.getValue().equals(targetValue)) { 298 return attribute; 299 } 300 } 301 302 NodeList children = node.getChildNodes(); 303 for (int i = 0, n = children.getLength(); i < n; i++) { 304 Node child = children.item(i); 305 Attr result = findIdAttribute(child, targetValue); 306 if (result != null) { 307 return result; 308 } 309 } 310 311 return null; 312 } 313 314 /** Include Graph Node */ 315 private static class Layout { 316 private File mFile; 317 private List<Layout> mIncludes; 318 private List<Layout> mIncludedBy; 319 private Set<String> mIds; 320 321 Layout(File file, Set<String> ids) { 322 mFile = file; 323 mIds = ids; 324 } 325 326 Set<String> getIds() { 327 return mIds; 328 } 329 330 String getLayoutName() { 331 return LintUtils.getLayoutName(mFile); 332 } 333 334 String getDisplayName() { 335 return mFile.getParentFile().getName() + File.separator + mFile.getName(); 336 } 337 338 void include(Layout target) { 339 if (mIncludes == null) { 340 mIncludes = new ArrayList<Layout>(); 341 } 342 mIncludes.add(target); 343 344 if (target.mIncludedBy == null) { 345 target.mIncludedBy = new ArrayList<Layout>(); 346 } 347 target.mIncludedBy.add(this); 348 } 349 350 boolean isIncluded() { 351 return mIncludedBy != null && mIncludedBy.size() > 0; 352 } 353 354 File getFile() { 355 return mFile; 356 } 357 358 List<Layout> getIncludes() { 359 return mIncludes; 360 } 361 362 @Override 363 public String toString() { 364 return getDisplayName(); 365 } 366 } 367 368 private class IncludeGraph { 369 private final Context mContext; 370 private final Map<File, Layout> mFileToLayout; 371 372 public IncludeGraph(Context context) { 373 mContext = context; 374 375 // Produce a DAG of the files to be included, and compute edges to all eligible 376 // includes. 377 // Then visit the DAG and whenever you find a duplicate emit a warning about the 378 // include path which reached it. 379 mFileToLayout = new HashMap<File, Layout>(2 * mIncludes.size()); 380 for (File file : mIncludes.keySet()) { 381 if (!mFileToLayout.containsKey(file)) { 382 mFileToLayout.put(file, new Layout(file, mFileToIds.get(file))); 383 } 384 } 385 for (File file : mFileToIds.keySet()) { 386 Set<String> ids = mFileToIds.get(file); 387 if (ids != null && ids.size() > 0) { 388 if (!mFileToLayout.containsKey(file)) { 389 mFileToLayout.put(file, new Layout(file, ids)); 390 } 391 } 392 } 393 Multimap<String, Layout> nameToLayout = 394 ArrayListMultimap.create(mFileToLayout.size(), 4); 395 for (File file : mFileToLayout.keySet()) { 396 String name = LintUtils.getLayoutName(file); 397 nameToLayout.put(name, mFileToLayout.get(file)); 398 } 399 400 // Build up the DAG 401 for (File file : mIncludes.keySet()) { 402 Layout from = mFileToLayout.get(file); 403 assert from != null : file; 404 405 List<String> includedLayouts = mIncludes.get(file); 406 for (String name : includedLayouts) { 407 Collection<Layout> layouts = nameToLayout.get(name); 408 if (layouts != null && layouts.size() > 0) { 409 if (layouts.size() == 1) { 410 from.include(layouts.iterator().next()); 411 } else { 412 // See if we have an obvious match 413 File folder = from.getFile().getParentFile(); 414 File candidate = new File(folder, name + DOT_XML); 415 Layout candidateLayout = mFileToLayout.get(candidate); 416 if (candidateLayout != null) { 417 from.include(candidateLayout); 418 } else if (mFileToIds.containsKey(candidate)) { 419 // We had an entry in mFileToIds, but not a layout: this 420 // means that the file exists, but had no includes or ids. 421 // This can't be a valid match: there is a layout that we know 422 // the include will pick, but it has no includes (to other layouts) 423 // and no ids, so no need to look at it 424 continue; 425 } else { 426 for (Layout to : layouts) { 427 // Decide if the two targets are compatible 428 if (isCompatible(from, to)) { 429 from.include(to); 430 } 431 } 432 } 433 } 434 } else { 435 // The layout is including some layout which has no ids or other includes 436 // so it's not relevant for a duplicate id search 437 continue; 438 } 439 } 440 } 441 } 442 443 /** Determine whether two layouts are compatible. They are not if they (for example) 444 * specify conflicting qualifiers such as {@code -land} and {@code -port}. 445 * @param from the include from 446 * @param to the include to 447 * @return true if the two are compatible */ 448 boolean isCompatible(Layout from, Layout to) { 449 File fromFolder = from.mFile.getParentFile(); 450 File toFolder = to.mFile.getParentFile(); 451 if (fromFolder.equals(toFolder)) { 452 return true; 453 } 454 455 String[] fromQualifiers = fromFolder.getName().split("-"); //$NON-NLS-1$ 456 String[] toQualifiers = toFolder.getName().split("-"); //$NON-NLS-1$ 457 458 if (isPortrait(fromQualifiers) != isPortrait(toQualifiers)) { 459 return false; 460 } 461 462 return true; 463 } 464 465 private boolean isPortrait(String[] qualifiers) { 466 for (String qualifier : qualifiers) { 467 if (qualifier.equals("port")) { //$NON-NLS-1$ 468 return true; 469 } else if (qualifier.equals("land")) { //$NON-NLS-1$ 470 return false; 471 } 472 } 473 474 return true; // it's the default 475 } 476 477 public void check() { 478 // Visit the DAG, looking for conflicts 479 for (Layout layout : mFileToLayout.values()) { 480 if (!layout.isIncluded()) { // Only check from "root" nodes 481 Deque<Layout> stack = new ArrayDeque<Layout>(); 482 getIds(layout, stack, new HashSet<Layout>()); 483 } 484 } 485 } 486 487 /** 488 * Computes the cumulative set of ids used in a given layout. We can't 489 * just depth-first-search the graph and check the set of ids 490 * encountered along the way, because we need to detect when multiple 491 * includes contribute the same ids. For example, if a file is included 492 * more than once, that would result in duplicates. 493 */ 494 private Set<String> getIds(Layout layout, Deque<Layout> stack, Set<Layout> seen) { 495 seen.add(layout); 496 497 Set<String> layoutIds = layout.getIds(); 498 List<Layout> includes = layout.getIncludes(); 499 if (includes != null) { 500 Set<String> ids = new HashSet<String>(); 501 if (layoutIds != null) { 502 ids.addAll(layoutIds); 503 } 504 505 stack.push(layout); 506 507 Multimap<String, Set<String>> nameToIds = 508 ArrayListMultimap.create(includes.size(), 4); 509 510 for (Layout included : includes) { 511 if (seen.contains(included)) { 512 continue; 513 } 514 Set<String> includedIds = getIds(included, stack, seen); 515 if (includedIds != null) { 516 String layoutName = included.getLayoutName(); 517 518 idCheck: 519 for (String id : includedIds) { 520 if (ids.contains(id)) { 521 Collection<Set<String>> idSets = nameToIds.get(layoutName); 522 if (idSets != null) { 523 for (Set<String> siblingIds : idSets) { 524 if (siblingIds.contains(id)) { 525 // The id reference was added by a sibling, 526 // so no need to complain (again) 527 continue idCheck; 528 } 529 } 530 } 531 532 // Duplicate! Record location request for new phase. 533 if (mLocations == null) { 534 mErrors = new ArrayList<Occurrence>(); 535 mLocations = ArrayListMultimap.create(); 536 mContext.getDriver().requestRepeat(DuplicateIdDetector.this, 537 Scope.ALL_RESOURCES_SCOPE); 538 } 539 540 Map<Layout, Occurrence> occurrences = 541 new HashMap<Layout, Occurrence>(); 542 findId(layout, id, new ArrayDeque<Layout>(), occurrences, 543 new HashSet<Layout>()); 544 assert occurrences.size() >= 2; 545 546 // Stash a request to find the given include 547 Collection<Occurrence> values = occurrences.values(); 548 List<Occurrence> sorted = new ArrayList<Occurrence>(values); 549 Collections.sort(sorted); 550 String msg = String.format( 551 "Duplicate id %1$s, defined or included multiple " + 552 "times in %2$s: %3$s", 553 id, layout.getDisplayName(), 554 sorted.toString()); 555 556 // Store location request for the <include> tag 557 Occurrence primary = new Occurrence(layout.getFile(), msg, null); 558 Multimap<String, Occurrence> m = ArrayListMultimap.create(); 559 m.put(layoutName, primary); 560 mLocations.put(layout.getFile(), m); 561 mErrors.add(primary); 562 563 Occurrence prev = primary; 564 565 // Now store all the included occurrences of the id 566 for (Occurrence occurrence : values) { 567 if (occurrence.file.equals(layout.getFile())) { 568 occurrence.message = "Defined here"; 569 } else { 570 occurrence.message = String.format( 571 "Defined here, included via %1$s", 572 occurrence.includePath); 573 } 574 575 m = ArrayListMultimap.create(); 576 m.put(id, occurrence); 577 mLocations.put(occurrence.file, m); 578 579 // Link locations together 580 prev.next = occurrence; 581 prev = occurrence; 582 } 583 } 584 ids.add(id); 585 } 586 587 // Store these ids such that on a conflict, we can tell when 588 // an id was added by a single variation of this file 589 nameToIds.put(layoutName, includedIds); 590 } 591 } 592 Layout visited = stack.pop(); 593 assert visited == layout; 594 return ids; 595 } else { 596 return layoutIds; 597 } 598 } 599 600 private void findId(Layout layout, String id, Deque<Layout> stack, 601 Map<Layout, Occurrence> occurrences, Set<Layout> seen) { 602 seen.add(layout); 603 604 Set<String> layoutIds = layout.getIds(); 605 if (layoutIds != null && layoutIds.contains(id)) { 606 StringBuilder path = new StringBuilder(); 607 608 if (!stack.isEmpty()) { 609 Iterator<Layout> iterator = stack.descendingIterator(); 610 while (iterator.hasNext()) { 611 path.append(iterator.next().getDisplayName()); 612 path.append(" => "); 613 } 614 } 615 path.append(layout.getDisplayName()); 616 path.append(" defines "); 617 path.append(id); 618 619 assert occurrences.get(layout) == null : id + "," + layout; 620 occurrences.put(layout, new Occurrence(layout.getFile(), null, path.toString())); 621 } 622 623 List<Layout> includes = layout.getIncludes(); 624 if (includes != null) { 625 stack.push(layout); 626 for (Layout included : includes) { 627 if (!seen.contains(included)) { 628 findId(included, id, stack, occurrences, seen); 629 } 630 } 631 Layout visited = stack.pop(); 632 assert visited == layout; 633 } 634 } 635 } 636 637 private static class Occurrence implements Comparable<Occurrence> { 638 public Occurrence next; 639 public File file; 640 public Location location; 641 public String message; 642 public String includePath; 643 644 public Occurrence(File file, String message, String includePath) { 645 this.file = file; 646 this.message = message; 647 this.includePath = includePath; 648 } 649 650 @Override 651 public String toString() { 652 return includePath != null ? includePath : message; 653 } 654 655 @Override 656 public int compareTo(Occurrence other) { 657 // First sort by length, then sort by name 658 int delta = toString().length() - other.toString().length(); 659 if (delta != 0) { 660 return delta; 661 } 662 663 return toString().compareTo(other.toString()); 664 } 665 } 666 } 667
