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