Expr.java revision 793e979f25e190162eacf46d6a4efc3efc1d2f91
1/* 2 * Copyright (C) 2015 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 android.databinding.tool.expr; 18 19import org.antlr.v4.runtime.misc.Nullable; 20 21import android.databinding.tool.processing.ErrorMessages; 22import android.databinding.tool.processing.Scope; 23import android.databinding.tool.processing.scopes.LocationScopeProvider; 24import android.databinding.tool.reflection.ModelAnalyzer; 25import android.databinding.tool.reflection.ModelClass; 26import android.databinding.tool.store.Location; 27import android.databinding.tool.util.L; 28import android.databinding.tool.util.Preconditions; 29import android.databinding.tool.writer.KCode; 30import android.databinding.tool.writer.WriterPackage; 31 32import java.util.ArrayList; 33import java.util.BitSet; 34import java.util.Collections; 35import java.util.List; 36import java.util.Map; 37 38abstract public class Expr implements VersionProvider, LocationScopeProvider { 39 40 public static final int NO_ID = -1; 41 protected List<Expr> mChildren = new ArrayList<Expr>(); 42 43 // any expression that refers to this. Useful if this expr is duplicate and being replaced 44 private List<Expr> mParents = new ArrayList<Expr>(); 45 46 private Boolean mIsDynamic; 47 48 private ModelClass mResolvedType; 49 50 private String mUniqueKey; 51 52 private List<Dependency> mDependencies; 53 54 private List<Dependency> mDependants = new ArrayList<Dependency>(); 55 56 private int mId = NO_ID; 57 58 private int mRequirementId = NO_ID; 59 60 private int mVersion = 0; 61 62 // means this expression can directly be invalidated by the user 63 private boolean mCanBeInvalidated = false; 64 65 @Nullable 66 private List<Location> mLocations = new ArrayList<>(); 67 68 /** 69 * This set denotes the times when this expression is invalid. 70 * If it is an Identifier expression, it is its index 71 * If it is a composite expression, it is the union of invalid flags of its descendants 72 */ 73 private BitSet mInvalidFlags; 74 75 /** 76 * Set when this expression is registered to a model 77 */ 78 private ExprModel mModel; 79 80 /** 81 * This set denotes the times when this expression must be read. 82 * 83 * It is the union of invalidation flags of all of its non-conditional dependants. 84 */ 85 BitSet mShouldReadFlags; 86 87 BitSet mReadSoFar = new BitSet();// i've read this variable for these flags 88 89 /** 90 * calculated on initialization, assuming all conditionals are true 91 */ 92 BitSet mShouldReadWithConditionals; 93 94 private boolean mIsBindingExpression; 95 96 /** 97 * Used by generators when this expression is resolved. 98 */ 99 private boolean mRead; 100 private boolean mIsUsed = false; 101 102 Expr(Iterable<Expr> children) { 103 for (Expr expr : children) { 104 mChildren.add(expr); 105 } 106 addParents(); 107 } 108 109 Expr(Expr... children) { 110 Collections.addAll(mChildren, children); 111 addParents(); 112 } 113 114 public int getId() { 115 Preconditions.check(mId != NO_ID, "if getId is called on an expression, it should have" 116 + " an id: %s", this); 117 return mId; 118 } 119 120 public void setId(int id) { 121 Preconditions.check(mId == NO_ID, "ID is already set on %s", this); 122 mId = id; 123 } 124 125 public void addLocation(Location location) { 126 mLocations.add(location); 127 } 128 129 public List<Location> getLocations() { 130 return mLocations; 131 } 132 133 public ExprModel getModel() { 134 return mModel; 135 } 136 137 public BitSet getInvalidFlags() { 138 if (mInvalidFlags == null) { 139 mInvalidFlags = resolveInvalidFlags(); 140 } 141 return mInvalidFlags; 142 } 143 144 private BitSet resolveInvalidFlags() { 145 BitSet bitSet = (BitSet) mModel.getInvalidateAnyBitSet().clone(); 146 if (mCanBeInvalidated) { 147 bitSet.set(getId(), true); 148 } 149 for (Dependency dependency : getDependencies()) { 150 // TODO optional optimization: do not invalidate for conditional flags 151 bitSet.or(dependency.getOther().getInvalidFlags()); 152 } 153 return bitSet; 154 } 155 156 public void setBindingExpression(boolean isBindingExpression) { 157 mIsBindingExpression = isBindingExpression; 158 } 159 160 public boolean isBindingExpression() { 161 return mIsBindingExpression; 162 } 163 164 public boolean canBeEvaluatedToAVariable() { 165 return true; // anything except arg expr can be evaluated to a variable 166 } 167 168 public boolean isObservable() { 169 return getResolvedType().isObservable(); 170 } 171 172 public Expr resolveListeners(ModelClass valueType, Expr parent) { 173 for (int i = mChildren.size() - 1; i >= 0; i--) { 174 Expr child = mChildren.get(i); 175 child.resolveListeners(valueType, this); 176 } 177 resetResolvedType(); 178 return this; 179 } 180 181 protected void resetResolvedType() { 182 mResolvedType = null; 183 } 184 185 public BitSet getShouldReadFlags() { 186 if (mShouldReadFlags == null) { 187 getShouldReadFlagsWithConditionals(); 188 mShouldReadFlags = resolveShouldReadFlags(); 189 } 190 return mShouldReadFlags; 191 } 192 193 public BitSet getShouldReadFlagsWithConditionals() { 194 if (mShouldReadWithConditionals == null) { 195 mShouldReadWithConditionals = resolveShouldReadWithConditionals(); 196 } 197 return mShouldReadWithConditionals; 198 } 199 200 public void setModel(ExprModel model) { 201 mModel = model; 202 } 203 204 private BitSet resolveShouldReadWithConditionals() { 205 // ensure we have invalid flags 206 BitSet bitSet = new BitSet(); 207 // if i'm invalid, that DOES NOT mean i should be read :/. 208 if (mIsBindingExpression) { 209 bitSet.or(getInvalidFlags()); 210 } 211 212 for (Dependency dependency : getDependants()) { 213 // first traverse non-conditionals because we'll avoid adding conditionals if we are get because of these anyways 214 if (dependency.getCondition() == null) { 215 bitSet.or(dependency.getDependant().getShouldReadFlagsWithConditionals()); 216 } else { 217 bitSet.set(dependency.getDependant() 218 .getRequirementFlagIndex(dependency.getExpectedOutput())); 219 } 220 } 221 return bitSet; 222 } 223 224 private BitSet resolveShouldReadFlags() { 225 // ensure we have invalid flags 226 BitSet bitSet = new BitSet(); 227 if (isRead()) { 228 return bitSet; 229 } 230 if (mIsBindingExpression) { 231 bitSet.or(getInvalidFlags()); 232 } 233 for (Dependency dependency : getDependants()) { 234 final boolean isUnreadElevated = isUnreadElevated(dependency); 235 if (dependency.isConditional()) { 236 continue; // will be resolved later when conditional is elevated 237 } 238 if (isUnreadElevated) { 239 bitSet.set(dependency.getDependant() 240 .getRequirementFlagIndex(dependency.getExpectedOutput())); 241 } else { 242 bitSet.or(dependency.getDependant().getShouldReadFlags()); 243 } 244 } 245 bitSet.and(mShouldReadWithConditionals); 246 bitSet.andNot(mReadSoFar); 247 return bitSet; 248 } 249 250 private static boolean isUnreadElevated(Dependency input) { 251 return input.isElevated() && !input.getDependant().isRead(); 252 } 253 private void addParents() { 254 for (Expr expr : mChildren) { 255 expr.mParents.add(this); 256 } 257 } 258 259 public void onSwappedWith(Expr existing) { 260 for (Expr child : mChildren) { 261 child.onParentSwapped(this, existing); 262 } 263 } 264 265 private void onParentSwapped(Expr oldParent, Expr newParent) { 266 Preconditions.check(mParents.remove(oldParent), "trying to remove non-existent parent %s" 267 + " from %s", oldParent, mParents); 268 mParents.add(newParent); 269 } 270 271 public List<Expr> getChildren() { 272 return mChildren; 273 } 274 275 public List<Expr> getParents() { 276 return mParents; 277 } 278 279 /** 280 * Whether the result of this expression can change or not. 281 * 282 * For example, 3 + 5 can not change vs 3 + x may change. 283 * 284 * Default implementations checks children and returns true if any of them returns true 285 * 286 * @return True if the result of this expression may change due to variables 287 */ 288 public boolean isDynamic() { 289 if (mIsDynamic == null) { 290 mIsDynamic = isAnyChildDynamic(); 291 } 292 return mIsDynamic; 293 } 294 295 private boolean isAnyChildDynamic() { 296 for (Expr expr : mChildren) { 297 if (expr.isDynamic()) { 298 return true; 299 } 300 } 301 return false; 302 } 303 304 public ModelClass getResolvedType() { 305 if (mResolvedType == null) { 306 // TODO not get instance 307 try { 308 Scope.enter(this); 309 mResolvedType = resolveType(ModelAnalyzer.getInstance()); 310 if (mResolvedType == null) { 311 L.e(ErrorMessages.CANNOT_RESOLVE_TYPE, this); 312 } 313 } finally { 314 Scope.exit(); 315 } 316 } 317 return mResolvedType; 318 } 319 320 abstract protected ModelClass resolveType(ModelAnalyzer modelAnalyzer); 321 322 abstract protected List<Dependency> constructDependencies(); 323 324 /** 325 * Creates a dependency for each dynamic child. Should work for any expression besides 326 * conditionals. 327 */ 328 protected List<Dependency> constructDynamicChildrenDependencies() { 329 List<Dependency> dependencies = new ArrayList<Dependency>(); 330 for (Expr node : mChildren) { 331 if (!node.isDynamic()) { 332 continue; 333 } 334 dependencies.add(new Dependency(this, node)); 335 } 336 return dependencies; 337 } 338 339 public final List<Dependency> getDependencies() { 340 if (mDependencies == null) { 341 mDependencies = constructDependencies(); 342 } 343 return mDependencies; 344 } 345 346 void addDependant(Dependency dependency) { 347 mDependants.add(dependency); 348 } 349 350 public List<Dependency> getDependants() { 351 return mDependants; 352 } 353 354 protected static final String KEY_JOIN = "~"; 355 356 /** 357 * Returns a unique string key that can identify this expression. 358 * 359 * It must take into account any dependencies 360 * 361 * @return A unique identifier for this expression 362 */ 363 public final String getUniqueKey() { 364 if (mUniqueKey == null) { 365 mUniqueKey = computeUniqueKey(); 366 Preconditions.checkNotNull(mUniqueKey, 367 "if there are no children, you must override computeUniqueKey"); 368 Preconditions.check(!mUniqueKey.trim().equals(""), 369 "if there are no children, you must override computeUniqueKey"); 370 } 371 return mUniqueKey; 372 } 373 374 protected String computeUniqueKey() { 375 return computeChildrenKey(); 376 } 377 378 protected final String computeChildrenKey() { 379 return join(mChildren); 380 } 381 382 public void enableDirectInvalidation() { 383 mCanBeInvalidated = true; 384 } 385 386 public boolean canBeInvalidated() { 387 return mCanBeInvalidated; 388 } 389 390 public void trimShouldReadFlags(BitSet bitSet) { 391 mShouldReadFlags.andNot(bitSet); 392 } 393 394 public boolean isConditional() { 395 return false; 396 } 397 398 public int getRequirementId() { 399 return mRequirementId; 400 } 401 402 public void setRequirementId(int requirementId) { 403 mRequirementId = requirementId; 404 } 405 406 /** 407 * This is called w/ a dependency of mine. 408 * Base method should thr 409 */ 410 public int getRequirementFlagIndex(boolean expectedOutput) { 411 Preconditions.check(mRequirementId != NO_ID, "If this is an expression w/ conditional" 412 + " dependencies, it must be assigned a requirement ID"); 413 return expectedOutput ? mRequirementId + 1 : mRequirementId; 414 } 415 416 public boolean hasId() { 417 return mId != NO_ID; 418 } 419 420 public void markFlagsAsRead(BitSet flags) { 421 mReadSoFar.or(flags); 422 } 423 424 public boolean isRead() { 425 return mRead; 426 } 427 428 public boolean considerElevatingConditionals(Expr justRead) { 429 boolean elevated = false; 430 for (Dependency dependency : mDependencies) { 431 if (dependency.isConditional() && dependency.getCondition() == justRead) { 432 dependency.elevate(); 433 elevated = true; 434 } 435 } 436 return elevated; 437 } 438 439 public void invalidateReadFlags() { 440 mShouldReadFlags = null; 441 mVersion ++; 442 } 443 444 @Override 445 public int getVersion() { 446 return mVersion; 447 } 448 449 public boolean hasNestedCannotRead() { 450 if (isRead()) { 451 return false; 452 } 453 if (getShouldReadFlags().isEmpty()) { 454 return true; 455 } 456 for (Dependency dependency : getDependencies()) { 457 if (hasNestedCannotRead(dependency)) { 458 return true; 459 } 460 } 461 return false; 462 } 463 464 private static boolean hasNestedCannotRead(Dependency input) { 465 return input.isConditional() || input.getOther().hasNestedCannotRead(); 466 } 467 468 public boolean markAsReadIfDone() { 469 if (mRead) { 470 return false; 471 } 472 // TODO avoid clone, we can calculate this iteratively 473 BitSet clone = (BitSet) mShouldReadWithConditionals.clone(); 474 475 clone.andNot(mReadSoFar); 476 mRead = clone.isEmpty(); 477 if (!mRead && !mReadSoFar.isEmpty()) { 478 // check if remaining dependencies can be satisfied w/ existing values 479 // for predicate flags, this expr may already be calculated to get the predicate 480 // to detect them, traverse them later on, see which flags should be calculated to calculate 481 // them. If any of them is completely covered w/ our non-conditional flags, no reason 482 // to add them to the list since we'll already be calculated due to our non-conditional 483 // flags 484 485 for (int i = clone.nextSetBit(0); i != -1; i = clone.nextSetBit(i + 1)) { 486 final Expr expr = mModel.findFlagExpression(i); 487 if (expr == null || !expr.isConditional()) { 488 continue; 489 } 490 final BitSet readForConditional = expr.findConditionalFlags(); 491 // to calculate that conditional, i should've read /readForConditional/ flags 492 // if my read-so-far bits has any common w/ that; that means i would've already 493 // read myself 494 clone.andNot(readForConditional); 495 final BitSet invalidFlags = (BitSet) getInvalidFlags().clone(); 496 invalidFlags.xor(readForConditional); 497 mRead = invalidFlags.isEmpty() || clone.isEmpty(); 498 if (mRead) { 499 break; 500 } 501 } 502 503 } 504 if (mRead) { 505 mShouldReadFlags = null; // if we've been marked as read, clear should read flags 506 } 507 return mRead; 508 } 509 510 BitSet mConditionalFlags; 511 512 private BitSet findConditionalFlags() { 513 Preconditions.check(isConditional(), "should not call this on a non-conditional expr"); 514 if (mConditionalFlags == null) { 515 mConditionalFlags = new BitSet(); 516 resolveConditionalFlags(mConditionalFlags); 517 } 518 return mConditionalFlags; 519 } 520 521 private void resolveConditionalFlags(BitSet flags) { 522 flags.or(getPredicateInvalidFlags()); 523 // if i have only 1 dependency which is conditional, traverse it as well 524 if (getDependants().size() == 1) { 525 final Dependency dependency = getDependants().get(0); 526 if (dependency.getCondition() != null) { 527 flags.or(dependency.getDependant().findConditionalFlags()); 528 flags.set(dependency.getDependant() 529 .getRequirementFlagIndex(dependency.getExpectedOutput())); 530 } 531 } 532 } 533 534 535 @Override 536 public String toString() { 537 return getUniqueKey(); 538 } 539 540 public BitSet getReadSoFar() { 541 return mReadSoFar; 542 } 543 544 private Node mCalculationPaths = null; 545 546 protected Node getAllCalculationPaths() { 547 if (mCalculationPaths == null) { 548 Node node = new Node(); 549 // TODO distant parent w/ conditionals are still not traversed :/ 550 if (isConditional()) { 551 node.mBitSet.or(getPredicateInvalidFlags()); 552 } else { 553 node.mBitSet.or(getInvalidFlags()); 554 } 555 for (Dependency dependency : getDependants()) { 556 final Expr dependant = dependency.getDependant(); 557 if (dependency.getCondition() != null) { 558 Node cond = new Node(); 559 cond.setConditionFlag( 560 dependant.getRequirementFlagIndex(dependency.getExpectedOutput())); 561 cond.mParents.add(dependant.getAllCalculationPaths()); 562 } else { 563 node.mParents.add(dependant.getAllCalculationPaths()); 564 } 565 } 566 mCalculationPaths = node; 567 } 568 return mCalculationPaths; 569 } 570 571 public String getDefaultValue() { 572 return ModelAnalyzer.getInstance().getDefaultValue(getResolvedType().toJavaCode()); 573 } 574 575 protected BitSet getPredicateInvalidFlags() { 576 throw new IllegalStateException( 577 "must override getPredicateInvalidFlags in " + getClass().getSimpleName()); 578 } 579 580 /** 581 * Used by code generation 582 */ 583 public boolean shouldReadNow(final List<Expr> justRead) { 584 if (getShouldReadFlags().isEmpty()) { 585 return false; 586 } 587 for (Dependency input : getDependencies()) { 588 boolean dependencyReady = input.getOther().isRead() || (justRead != null && 589 justRead.contains(input.getOther())); 590 if(!dependencyReady) { 591 return false; 592 } 593 } 594 return true; 595 } 596 597 public boolean isEqualityCheck() { 598 return false; 599 } 600 601 public void setIsUsed(boolean isUsed) { 602 mIsUsed = isUsed; 603 for (Expr child : getChildren()) { 604 child.setIsUsed(isUsed); 605 } 606 } 607 608 public boolean isUsed() { 609 return mIsUsed; 610 } 611 612 public void updateExpr(ModelAnalyzer modelAnalyzer) { 613 final Map<String, Expr> exprMap = mModel.getExprMap(); 614 for (int i = mParents.size() - 1; i >= 0; i--) { 615 final Expr parent = mParents.get(i); 616 if (exprMap.get(parent.getUniqueKey()) != parent) { 617 mParents.remove(i); 618 } 619 } 620 for (Expr child : mChildren) { 621 child.updateExpr(modelAnalyzer); 622 } 623 } 624 625 protected static String join(String... items) { 626 StringBuilder result = new StringBuilder(); 627 for (int i = 0; i < items.length; i ++) { 628 if (i > 0) { 629 result.append(KEY_JOIN); 630 } 631 result.append(items[i]); 632 } 633 return result.toString(); 634 } 635 636 protected static String join(List<Expr> items) { 637 StringBuilder result = new StringBuilder(); 638 for (int i = 0; i < items.size(); i ++) { 639 if (i > 0) { 640 result.append(KEY_JOIN); 641 } 642 result.append(items.get(i).getUniqueKey()); 643 } 644 return result.toString(); 645 } 646 647 protected String asPackage() { 648 return null; 649 } 650 651 @Override 652 public List<Location> provideScopeLocation() { 653 return mLocations; 654 } 655 656 public KCode toCode() { 657 if (isDynamic()) { 658 return new KCode(WriterPackage.getExecutePendingLocalName(this)); 659 } 660 return generateCode(); 661 } 662 663 public KCode toFullCode() { 664 return generateCode(); 665 } 666 667 protected abstract KCode generateCode(); 668 669 static class Node { 670 671 BitSet mBitSet = new BitSet(); 672 List<Node> mParents = new ArrayList<Node>(); 673 int mConditionFlag = -1; 674 675 public boolean areAllPathsSatisfied(BitSet readSoFar) { 676 if (mConditionFlag != -1) { 677 return readSoFar.get(mConditionFlag) || mParents.get(0) 678 .areAllPathsSatisfied(readSoFar); 679 } else { 680 final BitSet clone = (BitSet) readSoFar.clone(); 681 clone.and(mBitSet); 682 if (!clone.isEmpty()) { 683 return true; 684 } 685 if (mParents.isEmpty()) { 686 return false; 687 } 688 for (Node parent : mParents) { 689 if (!parent.areAllPathsSatisfied(clone)) { 690 return false; 691 } 692 } 693 return true; 694 } 695 } 696 697 public void setConditionFlag(int requirementFlagIndex) { 698 mConditionFlag = requirementFlagIndex; 699 } 700 } 701} 702