1 // Copyright (c) 2016, the R8 project authors. Please see the AUTHORS file 2 // for details. All rights reserved. Use of this source code is governed by a 3 // BSD-style license that can be found in the LICENSE file. 4 package com.android.tools.r8.graph; 5 6 import com.android.tools.r8.dex.IndexedItemCollection; 7 import com.android.tools.r8.dex.MixedSectionCollection; 8 import java.util.Arrays; 9 10 /** 11 * Subset of dex items that are referenced by some table index. 12 */ 13 public abstract class IndexedDexItem extends CanonicalizedDexItem implements Presorted { 14 15 private static final int SORTED_INDEX_UNKNOWN = -1; 16 private int sortedIndex = SORTED_INDEX_UNKNOWN; // assigned globally after reading. 17 /** 18 * Contains the indexes assigned to this item for the various virtual output files. 19 * 20 * <p>One DexItem might be assigned to multiple virtual files. 21 * 22 * <p>For a certain virtual file this DexItem has the value: 23 * <ul> 24 * <li>{@link #UNASSOCIATED_VALUE}, when not associated with the virtual file. 25 * <li>{@link #ASSOCIATED_VALUE}, when associated with the virtual file but no index allocated. 26 * <li>A zero or greater value when this item has been associated by the virtual file 27 * and the value denotes the assigned index. 28 * </ul> 29 * <p> Note that, in case of multiple files, for a specific IndexedDexItem, we may not have 30 * as many entries in the index as there are files (we only expand when we need to). If we lookup 31 * the value of an entry that is out of bounds it is equivalent to {@link #UNASSOCIATED_VALUE} 32 * 33 * <p>This field is initialized on first write in {@link #updateVirtualFileData(int, int)}}. It 34 * is assumed that multiple files are processed concurrently and thus the allocation of the 35 * array is synchronized. However, for any a given file id, sequential access is assumed. 36 */ 37 private int[] virtualFileIndexes; 38 collectIndexedItems(IndexedItemCollection indexedItems)39 public abstract void collectIndexedItems(IndexedItemCollection indexedItems); 40 41 @Override collectMixedSectionItems(MixedSectionCollection mixedItems)42 void collectMixedSectionItems(MixedSectionCollection mixedItems) { 43 // Should never be visited. 44 assert false; 45 } 46 getOffset(ObjectToOffsetMapping mapping)47 public abstract int getOffset(ObjectToOffsetMapping mapping); 48 49 /** 50 * Constants used inside virtualFileIndexes. 51 */ 52 public static final int UNASSOCIATED_VALUE = -2; 53 public static final int ASSOCIATED_VALUE = -1; 54 public static final int MIN_VALID_VALUE = 0; 55 56 /** 57 * Returns whether this item is assigned to the given file id. 58 */ hasVirtualFileData(int virtualFileId)59 public boolean hasVirtualFileData(int virtualFileId) { 60 return getVirtualFileIndex(virtualFileId) != UNASSOCIATED_VALUE; 61 } 62 63 /** 64 * Assigns this item to the given file id if it has not been assigned previously. 65 * 66 * <p>This method returns 'true' if the item was newly assigned, i.e., it was not previously 67 * assigned to the file id. 68 */ assignToVirtualFile(int virtualFileId)69 public boolean assignToVirtualFile(int virtualFileId) { 70 // Fast lock-free check whether already assigned. 71 if (hasVirtualFileData(virtualFileId)) { 72 return false; 73 } 74 return updateVirtualFileData(virtualFileId); 75 } 76 77 /** 78 * Assigns this item to the given file id. 79 * 80 * <p>As a side effect, the {@link #virtualFileIndexes} field might be initialized or expanded. 81 * Hence this method is synchronized. Note that the field is queried without synchronization. 82 * Therefor it has to remain in a valid state at all times and must transition atomically from 83 * null to an initialized allocated value. 84 */ updateVirtualFileData(int virtualFileId)85 private synchronized boolean updateVirtualFileData(int virtualFileId) { 86 if (virtualFileIndexes == null) { 87 int[] fileIndices = new int[virtualFileId + 1]; 88 Arrays.fill(fileIndices, UNASSOCIATED_VALUE); 89 // This has to be an atomic transition from null to an initialized array. 90 virtualFileIndexes = fileIndices; 91 } 92 // We increased the number of files, increase the index size. 93 if (virtualFileId >= virtualFileIndexes.length) { 94 int oldLength = virtualFileIndexes.length; 95 int[] fileIndices = Arrays.copyOf(virtualFileIndexes, virtualFileId + 1); 96 Arrays.fill(fileIndices, oldLength, virtualFileId + 1, UNASSOCIATED_VALUE); 97 virtualFileIndexes = fileIndices; 98 } 99 assert virtualFileId < virtualFileIndexes.length; 100 boolean wasAdded = virtualFileIndexes[virtualFileId] == UNASSOCIATED_VALUE; 101 virtualFileIndexes[virtualFileId] = ASSOCIATED_VALUE; 102 return wasAdded; 103 } 104 105 /** 106 * Assigns an actual index for this item in the given file. 107 * 108 * <p>May only be used after this item has been assigned to the file using {@link 109 * #assignToVirtualFile(int, int)}. 110 */ 111 public void assignVirtualFileIndex(int virtualFileId, int index) { 112 assert virtualFileIndexes != null; 113 assert virtualFileIndexes[virtualFileId] < MIN_VALID_VALUE; 114 virtualFileIndexes[virtualFileId] = index; 115 } 116 117 /** 118 * Returns the index associated with this item for the given file id or {@link 119 * #UNASSOCIATED_VALUE} if the item is not associated to the given file id. 120 */ 121 public int getVirtualFileIndex(int virtualFileId) { 122 if (virtualFileIndexes == null) { 123 return UNASSOCIATED_VALUE; 124 } 125 // If more files were added, but this entry not associated with it, we would not have extended 126 // the size of the array. So if the {@link virtualFileId} is out of bounds, it means 127 // {@link #UNASSOCIATED_VALUE} 128 return virtualFileIndexes.length > virtualFileId 129 ? virtualFileIndexes[virtualFileId] 130 : UNASSOCIATED_VALUE; 131 } 132 133 // Partial implementation of PresortedComparable. 134 135 final public void setSortedIndex(int sortedIndex) { 136 assert sortedIndex > SORTED_INDEX_UNKNOWN; 137 assert this.sortedIndex == SORTED_INDEX_UNKNOWN; 138 this.sortedIndex = sortedIndex; 139 } 140 getSortedIndex()141 final public int getSortedIndex() { 142 return sortedIndex; 143 } 144 sortedCompareTo(int other)145 final public int sortedCompareTo(int other) { 146 assert sortedIndex > SORTED_INDEX_UNKNOWN; 147 assert other > SORTED_INDEX_UNKNOWN; 148 return Integer.compare(sortedIndex, other); 149 } 150 flushCachedValues()151 public void flushCachedValues() { 152 super.flushCachedValues(); 153 resetSortedIndex(); 154 } 155 resetSortedIndex()156 public void resetSortedIndex() { 157 sortedIndex = SORTED_INDEX_UNKNOWN; 158 } 159 } 160