|
| 1 | +/** |
| 2 | + * Provides classes for reasoning about certain property accesses as access paths. |
| 3 | + * |
| 4 | + * Access paths represent SSA variables with zero or more property accesses applied to them. |
| 5 | + * Each property name in the access must either be constant or itself be a use of an SSA |
| 6 | + * variable. |
| 7 | + * |
| 8 | + * If `x` and `y` are SSA variables, then `x`, `x.p`, `x.p["q"]`, `x[y]` and `x[y].q` are |
| 9 | + * access paths, but `x[x.y]` is not an access path. |
| 10 | + * |
| 11 | + * Access paths can be used to identify expressions that have the same value, disregarding |
| 12 | + * any heap modifications. In general, expressions that are instances of the same access |
| 13 | + * path are not guaranteed to evaluate to the same value nor do all expressions that evaluate |
| 14 | + * to the same value have the same access paths, so access paths are neither sound nor |
| 15 | + * complete as an approximation of expression semantics. |
| 16 | + */ |
| 17 | + |
| 18 | +import javascript |
| 19 | + |
| 20 | +/** |
| 21 | + * A representation of a property name that is either statically known or is |
| 22 | + * the value of an SSA variable. |
| 23 | + */ |
| 24 | +private newtype PropertyName = |
| 25 | + StaticPropertyName(string name) { |
| 26 | + exists (PropAccess pa | name = pa.getPropertyName()) |
| 27 | + } |
| 28 | + or |
| 29 | + DynamicPropertyName(SsaVariable var) { |
| 30 | + exists (PropAccess pa | pa.getPropertyNameExpr() = var.getAUse()) |
| 31 | + } |
| 32 | + |
| 33 | +/** |
| 34 | + * Gets the representation of the property name of `pacc`, if any. |
| 35 | + */ |
| 36 | +private PropertyName getPropertyName(PropAccess pacc) { |
| 37 | + result = StaticPropertyName(pacc.getPropertyName()) |
| 38 | + or |
| 39 | + exists (SsaVariable var | |
| 40 | + pacc.getPropertyNameExpr() = var.getAUse() and |
| 41 | + result = DynamicPropertyName(var) |
| 42 | + ) |
| 43 | +} |
| 44 | + |
| 45 | +/** |
| 46 | + * A representation of a (nested) property access on an SSA variable |
| 47 | + * where each property name is either constant or itself an SSA variable. |
| 48 | + */ |
| 49 | +private newtype TAccessPath = |
| 50 | + MkRoot(SsaVariable var) |
| 51 | + or |
| 52 | + MkAccessStep(AccessPath base, PropertyName name) { |
| 53 | + exists (PropAccess pacc | |
| 54 | + pacc.getBase() = base.getAnInstance() and |
| 55 | + getPropertyName(pacc) = name |
| 56 | + ) |
| 57 | + } |
| 58 | + |
| 59 | +/** |
| 60 | + * A representation of a (nested) property access on an SSA variable |
| 61 | + * where each property name is either constant or itself an SSA variable. |
| 62 | + */ |
| 63 | +class AccessPath extends TAccessPath { |
| 64 | + /** |
| 65 | + * Gets an expression in `bb` represented by this access path. |
| 66 | + */ |
| 67 | + Expr getAnInstanceIn(BasicBlock bb) { |
| 68 | + exists (SsaVariable var | |
| 69 | + this = MkRoot(var) and |
| 70 | + result = var.getAUseIn(bb) |
| 71 | + ) |
| 72 | + or |
| 73 | + exists (PropertyName name | |
| 74 | + result = getABaseInstanceIn(bb, name) and |
| 75 | + getPropertyName(result) = name |
| 76 | + ) |
| 77 | + } |
| 78 | + |
| 79 | + /** |
| 80 | + * Gets a property access in `bb` whose base is represented by the |
| 81 | + * base of this access path, and where `name` is bound to the last |
| 82 | + * component of this access path. |
| 83 | + * |
| 84 | + * This is an auxiliary predicate that's needed to enforce a better |
| 85 | + * join order in `getAnInstanceIn` above. |
| 86 | + */ |
| 87 | + pragma[noinline] |
| 88 | + private PropAccess getABaseInstanceIn(BasicBlock bb, PropertyName name) { |
| 89 | + exists (AccessPath base | this = MkAccessStep(base, name) | |
| 90 | + result.getBase() = base.getAnInstanceIn(bb) |
| 91 | + ) |
| 92 | + } |
| 93 | + |
| 94 | + /** |
| 95 | + * Gets an expression represented by this access path. |
| 96 | + */ |
| 97 | + Expr getAnInstance() { |
| 98 | + result = getAnInstanceIn(_) |
| 99 | + } |
| 100 | + |
| 101 | + /** |
| 102 | + * Gets a textual representation of this access path. |
| 103 | + */ |
| 104 | + string toString() { |
| 105 | + exists (SsaVariable var | this = MkRoot(var) | |
| 106 | + result = var.getSourceVariable().getName() |
| 107 | + ) |
| 108 | + or |
| 109 | + exists (AccessPath base, PropertyName name, string rest | |
| 110 | + rest = "." + any(string s | name = StaticPropertyName(s)) |
| 111 | + or |
| 112 | + rest = "[" + any(SsaVariable var | name = DynamicPropertyName(var)).getSourceVariable().getName() + "]" | |
| 113 | + result = base.toString() + rest and |
| 114 | + this = MkAccessStep(base, name) |
| 115 | + ) |
| 116 | + } |
| 117 | +} |
0 commit comments