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