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