LocalsArraySet.java revision de75089fb7216d19e9c22cce4dc62a49513477d3
1/* 2 * Copyright (C) 2007 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 17package com.android.dx.cf.code; 18 19import com.android.dx.rop.code.RegisterSpec; 20import com.android.dx.rop.type.Type; 21import com.android.dx.rop.type.TypeBearer; 22import com.android.dx.util.ExceptionWithContext; 23import com.android.dx.util.Hex; 24import com.android.dx.util.MutabilityControl; 25 26import java.util.ArrayList; 27 28/** 29 * Representation of a set of local variable arrays, with Java semantics. 30 * This peculiar case is to support in-method subroutines, which can 31 * have different locals sets for each caller. 32 * 33 * <p><b>Note:</b> For the most part, the documentation for this class 34 * ignores the distinction between {@link com.android.dx.rop.type.Type} and {@link 35 * com.android.dx.rop.type.TypeBearer}.</p> 36 */ 37public class LocalsArraySet extends LocalsArray { 38 39 /** 40 * The primary LocalsArray represents the locals as seen from 41 * the subroutine itself, which is the merged representation of all the 42 * individual locals states. 43 */ 44 private final OneLocalsArray primary; 45 46 /** 47 * Indexed by label of caller block: the locals specific to each caller's 48 * invocation of the subroutine. 49 */ 50 private final ArrayList<LocalsArray> secondaries; 51 52 /** 53 * Constructs an instance. The locals array initially consists of 54 * all-uninitialized values (represented as {@code null}s). 55 * 56 * @param maxLocals {@code >= 0;} the maximum number of locals this instance 57 * can refer to 58 */ 59 public LocalsArraySet(int maxLocals) { 60 super(maxLocals != 0); 61 primary = new OneLocalsArray(maxLocals); 62 secondaries = new ArrayList(); 63 } 64 65 /** 66 * Constructs an instance with the specified primary and secondaries set. 67 * 68 * @param primary {@code non-null;} primary locals to use 69 * @param secondaries {@code non-null;} secondaries set, indexed by subroutine 70 * caller label. 71 */ 72 public LocalsArraySet(OneLocalsArray primary, 73 ArrayList<LocalsArray> secondaries) { 74 super(primary.getMaxLocals() > 0); 75 76 this.primary = primary; 77 this.secondaries = secondaries; 78 } 79 80 /** 81 * Constructs an instance which is a copy of another. 82 * 83 * @param toCopy {@code non-null;} instance to copy. 84 */ 85 private LocalsArraySet(LocalsArraySet toCopy) { 86 super(toCopy.getMaxLocals() > 0); 87 88 primary = toCopy.primary.copy(); 89 secondaries = new ArrayList(toCopy.secondaries.size()); 90 91 int sz = toCopy.secondaries.size(); 92 for (int i = 0; i < sz; i++) { 93 LocalsArray la = toCopy.secondaries.get(i); 94 95 if (la == null) { 96 secondaries.add(null); 97 } else { 98 secondaries.add(la.copy()); 99 } 100 } 101 } 102 103 104 /** @inheritDoc */ 105 @Override 106 public void setImmutable() { 107 primary.setImmutable(); 108 109 for (LocalsArray la : secondaries) { 110 if (la != null) { 111 la.setImmutable(); 112 } 113 } 114 super.setImmutable(); 115 } 116 117 /** @inheritDoc */ 118 @Override 119 public LocalsArray copy() { 120 return new LocalsArraySet(this); 121 } 122 123 /** @inheritDoc */ 124 @Override 125 public void annotate(ExceptionWithContext ex) { 126 ex.addContext("(locals array set; primary)"); 127 primary.annotate(ex); 128 129 int sz = secondaries.size(); 130 for (int label = 0; label < sz; label++) { 131 LocalsArray la = secondaries.get(label); 132 133 if (la != null) { 134 ex.addContext("(locals array set: primary for caller " 135 + Hex.u2(label) + ')'); 136 137 la.getPrimary().annotate(ex); 138 } 139 } 140 } 141 142 /** {@inheritDoc*/ 143 public String toHuman() { 144 StringBuilder sb = new StringBuilder(); 145 146 sb.append("(locals array set; primary)\n"); 147 148 sb.append(getPrimary().toHuman()); 149 sb.append('\n'); 150 151 int sz = secondaries.size(); 152 for (int label = 0; label < sz; label++) { 153 LocalsArray la = secondaries.get(label); 154 155 if (la != null) { 156 sb.append("(locals array set: primary for caller " 157 + Hex.u2(label) + ")\n"); 158 159 sb.append(la.getPrimary().toHuman()); 160 sb.append('\n'); 161 } 162 } 163 164 return sb.toString(); 165 } 166 167 /** @inheritDoc */ 168 @Override 169 public void makeInitialized(Type type) { 170 int len = primary.getMaxLocals(); 171 172 if (len == 0) { 173 // We have to check for this before checking for immutability. 174 return; 175 } 176 177 throwIfImmutable(); 178 179 primary.makeInitialized(type); 180 181 for (LocalsArray la : secondaries) { 182 if (la != null) { 183 la.makeInitialized(type); 184 } 185 } 186 } 187 188 /** @inheritDoc */ 189 @Override 190 public int getMaxLocals() { 191 return primary.getMaxLocals(); 192 } 193 194 /** @inheritDoc */ 195 @Override 196 public void set(int idx, TypeBearer type) { 197 throwIfImmutable(); 198 199 primary.set(idx, type); 200 201 for (LocalsArray la : secondaries) { 202 if (la != null) { 203 la.set(idx, type); 204 } 205 } 206 } 207 208 /** @inheritDoc */ 209 @Override 210 public void set(RegisterSpec spec) { 211 set(spec.getReg(), spec); 212 } 213 214 /** @inheritDoc */ 215 @Override 216 public void invalidate(int idx) { 217 throwIfImmutable(); 218 219 primary.invalidate(idx); 220 221 for (LocalsArray la : secondaries) { 222 if (la != null) { 223 la.invalidate(idx); 224 } 225 } 226 } 227 228 /** @inheritDoc */ 229 @Override 230 public TypeBearer getOrNull(int idx) { 231 return primary.getOrNull(idx); 232 } 233 234 /** @inheritDoc */ 235 @Override 236 public TypeBearer get(int idx) { 237 return primary.get(idx); 238 } 239 240 /** @inheritDoc */ 241 @Override 242 public TypeBearer getCategory1(int idx) { 243 return primary.getCategory1(idx); 244 } 245 246 /** @inheritDoc */ 247 @Override 248 public TypeBearer getCategory2(int idx) { 249 return primary.getCategory2(idx); 250 } 251 252 /** 253 * Merges this set with another {@code LocalsArraySet} instance. 254 * 255 * @param other {@code non-null;} to merge 256 * @return {@code non-null;} this instance if merge was a no-op, or 257 * new merged instance. 258 */ 259 private LocalsArraySet mergeWithSet(LocalsArraySet other) { 260 OneLocalsArray newPrimary; 261 ArrayList<LocalsArray> newSecondaries; 262 boolean secondariesChanged = false; 263 264 newPrimary = primary.merge(other.getPrimary()); 265 266 int sz1 = secondaries.size(); 267 int sz2 = other.secondaries.size(); 268 int sz = Math.max(sz1, sz2); 269 newSecondaries = new ArrayList(sz); 270 271 for (int i = 0; i < sz; i++) { 272 LocalsArray la1 = (i < sz1 ? secondaries.get(i) : null); 273 LocalsArray la2 = (i < sz2 ? other.secondaries.get(i) : null); 274 LocalsArray resultla = null; 275 276 if (la1 == la2) { 277 resultla = la1; 278 } else if (la1 == null) { 279 resultla = la2; 280 } else if (la2 == null) { 281 resultla = la1; 282 } else { 283 try { 284 resultla = la1.merge(la2); 285 } catch (SimException ex) { 286 ex.addContext( 287 "Merging locals set for caller block " + Hex.u2(i)); 288 } 289 } 290 291 secondariesChanged = secondariesChanged || (la1 != resultla); 292 293 newSecondaries.add(resultla); 294 } 295 296 if ((primary == newPrimary) && ! secondariesChanged ) { 297 return this; 298 } 299 300 return new LocalsArraySet(newPrimary, newSecondaries); 301 } 302 303 /** 304 * Merges this set with a {@code OneLocalsArray} instance. 305 * 306 * @param other {@code non-null;} to merge 307 * @return {@code non-null;} this instance if merge was a no-op, or 308 * new merged instance. 309 */ 310 private LocalsArraySet mergeWithOne(OneLocalsArray other) { 311 OneLocalsArray newPrimary; 312 ArrayList<LocalsArray> newSecondaries; 313 boolean secondariesChanged = false; 314 315 newPrimary = primary.merge(other.getPrimary()); 316 newSecondaries = new ArrayList(secondaries.size()); 317 318 int sz = secondaries.size(); 319 for (int i = 0; i < sz; i++) { 320 LocalsArray la = secondaries.get(i); 321 LocalsArray resultla = null; 322 323 if (la != null) { 324 try { 325 resultla = la.merge(other); 326 } catch (SimException ex) { 327 ex.addContext("Merging one locals against caller block " 328 + Hex.u2(i)); 329 } 330 } 331 332 secondariesChanged = secondariesChanged || (la != resultla); 333 334 newSecondaries.add(resultla); 335 } 336 337 if ((primary == newPrimary) && ! secondariesChanged ) { 338 return this; 339 } 340 341 return new LocalsArraySet(newPrimary, newSecondaries); 342 } 343 344 /** @inheritDoc */ 345 @Override 346 public LocalsArraySet merge(LocalsArray other) { 347 LocalsArraySet result; 348 349 try { 350 if (other instanceof LocalsArraySet) { 351 result = mergeWithSet((LocalsArraySet) other); 352 } else { 353 result = mergeWithOne((OneLocalsArray) other); 354 } 355 } catch (SimException ex) { 356 ex.addContext("underlay locals:"); 357 annotate(ex); 358 ex.addContext("overlay locals:"); 359 other.annotate(ex); 360 throw ex; 361 } 362 363 result.setImmutable(); 364 return result; 365 } 366 367 /** 368 * Gets the {@code LocalsArray} instance for a specified subroutine 369 * caller label, or null if label has no locals associated with it. 370 * 371 * @param label {@code >= 0;} subroutine caller label 372 * @return {@code null-ok;} locals if available. 373 */ 374 private LocalsArray getSecondaryForLabel(int label) { 375 if (label >= secondaries.size()) { 376 return null; 377 } 378 379 return secondaries.get(label); 380 } 381 382 /** {@inheritDoc} */ 383 @Override 384 public LocalsArraySet mergeWithSubroutineCaller 385 (LocalsArray other, int predLabel) { 386 387 LocalsArray mine = getSecondaryForLabel(predLabel); 388 LocalsArray newSecondary; 389 OneLocalsArray newPrimary; 390 391 newPrimary = primary.merge(other.getPrimary()); 392 393 if (mine == other) { 394 newSecondary = mine; 395 } else if (mine == null) { 396 newSecondary = other; 397 } else { 398 newSecondary = mine.merge(other); 399 } 400 401 if ((newSecondary == mine) && (newPrimary == primary)) { 402 return this; 403 } else { 404 /* 405 * We're going to re-build a primary as a merge of all the 406 * secondaries. 407 */ 408 newPrimary = null; 409 410 int szSecondaries = secondaries.size(); 411 int sz = Math.max(predLabel + 1, szSecondaries); 412 ArrayList<LocalsArray> newSecondaries = new ArrayList(sz); 413 for (int i = 0; i < sz; i++) { 414 LocalsArray la = null; 415 416 if (i == predLabel) { 417 /* 418 * This LocalsArray always replaces any existing one, 419 * since this is the result of a refined iteration. 420 */ 421 la = newSecondary; 422 } else if (i < szSecondaries) { 423 la = secondaries.get(i); 424 } 425 426 if (la != null) { 427 if (newPrimary == null) { 428 newPrimary = la.getPrimary(); 429 } else { 430 newPrimary = newPrimary.merge(la.getPrimary()); 431 } 432 } 433 434 newSecondaries.add(la); 435 } 436 437 LocalsArraySet result 438 = new LocalsArraySet(newPrimary, newSecondaries); 439 result.setImmutable(); 440 return result; 441 } 442 } 443 444 /** 445 * Returns a LocalsArray instance representing the locals state that should 446 * be used when returning to a subroutine caller. 447 * 448 * @param subLabel {@code >= 0;} A calling label of a subroutine 449 * @return {@code null-ok;} an instance for this subroutine, or null if subroutine 450 * is not in this set. 451 */ 452 public LocalsArray subArrayForLabel(int subLabel) { 453 LocalsArray result = getSecondaryForLabel(subLabel); 454 return result; 455 } 456 457 /**{@inheritDoc}*/ 458 @Override 459 protected OneLocalsArray getPrimary() { 460 return primary; 461 } 462} 463