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