Documentation ¶
Overview ¶
Package analysis performs static program data flow analysis of an API file.
Index ¶
- type BoolValue
- func (v *BoolValue) And(o *BoolValue) *BoolValue
- func (v *BoolValue) Clone() Value
- func (v *BoolValue) Difference(o Value) Value
- func (v *BoolValue) Equals(o Value) Possibility
- func (v *BoolValue) Equivalent(o Value) bool
- func (v *BoolValue) Intersect(o Value) Value
- func (v *BoolValue) Not() *BoolValue
- func (v *BoolValue) Or(o *BoolValue) *BoolValue
- func (v *BoolValue) Print(results *Results) string
- func (v *BoolValue) String() string
- func (v *BoolValue) Type() semantic.Type
- func (v *BoolValue) Union(o Value) Value
- func (v *BoolValue) Valid() bool
- type Callstack
- type CallstackEntry
- type ClassValue
- func (v *ClassValue) Clone() Value
- func (v *ClassValue) Difference(o Value) Value
- func (v *ClassValue) Equals(o Value) Possibility
- func (v *ClassValue) Equivalent(o Value) bool
- func (v *ClassValue) Intersect(o Value) Value
- func (v *ClassValue) Print(results *Results) string
- func (v *ClassValue) Type() semantic.Type
- func (v *ClassValue) Union(o Value) Value
- func (v *ClassValue) Valid() bool
- type EnumValue
- func (v *EnumValue) Clone() Value
- func (v *EnumValue) Difference(o Value) Value
- func (v *EnumValue) Equals(o Value) Possibility
- func (v *EnumValue) Equivalent(o Value) bool
- func (v *EnumValue) GreaterEqual(o Value) Possibility
- func (v *EnumValue) GreaterThan(o Value) Possibility
- func (v *EnumValue) Intersect(o Value) Value
- func (v *EnumValue) LessEqual(o Value) Possibility
- func (v *EnumValue) LessThan(o Value) Possibility
- func (v *EnumValue) Print(results *Results) string
- func (v *EnumValue) SetGreaterEqual(o Value) Value
- func (v *EnumValue) SetGreaterThan(o Value) Value
- func (v *EnumValue) SetLessEqual(o Value) Value
- func (v *EnumValue) SetLessThan(o Value) Value
- func (v *EnumValue) String() string
- func (v *EnumValue) Type() semantic.Type
- func (v *EnumValue) Union(o Value) Value
- func (v *EnumValue) Valid() bool
- type Labels
- type MapValue
- func (v *MapValue) Clone() Value
- func (v *MapValue) ContainsKey(key Value) Possibility
- func (v *MapValue) Difference(o Value) Value
- func (v *MapValue) Equals(o Value) Possibility
- func (v *MapValue) Equivalent(o Value) bool
- func (v *MapValue) Get(s *scope, key Value) Value
- func (v *MapValue) Intersect(o Value) Value
- func (v *MapValue) Print(results *Results) string
- func (v *MapValue) Put(key, val Value) *MapValue
- func (v *MapValue) String() string
- func (v *MapValue) Type() semantic.Type
- func (v *MapValue) Union(o Value) Value
- func (v *MapValue) Valid() bool
- type Possibility
- func (a Possibility) And(b Possibility) Possibility
- func (a Possibility) Difference(b Possibility) Possibility
- func (a Possibility) Equals(b Possibility) Possibility
- func (a Possibility) Intersect(b Possibility) Possibility
- func (a Possibility) MaybeFalse() bool
- func (a Possibility) MaybeTrue() bool
- func (a Possibility) Not() Possibility
- func (a Possibility) Or(b Possibility) Possibility
- func (a Possibility) Union(b Possibility) Possibility
- type ReferenceValue
- func (v *ReferenceValue) Clone() Value
- func (v *ReferenceValue) Difference(o Value) Value
- func (v *ReferenceValue) Equals(o Value) Possibility
- func (v *ReferenceValue) Equivalent(o Value) bool
- func (v *ReferenceValue) Intersect(o Value) Value
- func (v *ReferenceValue) Print(results *Results) string
- func (v *ReferenceValue) String() string
- func (v *ReferenceValue) Type() semantic.Type
- func (v *ReferenceValue) Union(o Value) Value
- func (v *ReferenceValue) Valid() bool
- type Relational
- type Results
- type SetRelational
- type UintValue
- func (v *UintValue) Clone() Value
- func (v *UintValue) Difference(o Value) Value
- func (v *UintValue) Equals(o Value) Possibility
- func (v *UintValue) Equivalent(o Value) bool
- func (v *UintValue) GreaterEqual(o Value) Possibility
- func (v *UintValue) GreaterThan(o Value) Possibility
- func (v *UintValue) Intersect(o Value) Value
- func (v *UintValue) LessEqual(o Value) Possibility
- func (v *UintValue) LessThan(o Value) Possibility
- func (v *UintValue) Print(results *Results) string
- func (v *UintValue) SetGreaterEqual(o Value) Value
- func (v *UintValue) SetGreaterThan(o Value) Value
- func (v *UintValue) SetLessEqual(o Value) Value
- func (v *UintValue) SetLessThan(o Value) Value
- func (v *UintValue) String() string
- func (v *UintValue) Type() semantic.Type
- func (v *UintValue) Union(o Value) Value
- func (v *UintValue) Valid() bool
- type Unreachable
- type UntrackedValue
- func (v *UntrackedValue) Clone() Value
- func (v *UntrackedValue) Difference(o Value) Value
- func (v *UntrackedValue) Equals(Value) Possibility
- func (v *UntrackedValue) Equivalent(Value) bool
- func (v *UntrackedValue) Intersect(o Value) Value
- func (v *UntrackedValue) Print(*Results) string
- func (v *UntrackedValue) Type() semantic.Type
- func (v *UntrackedValue) Union(o Value) Value
- func (v *UntrackedValue) Valid() bool
- type Value
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BoolValue ¶
type BoolValue struct {
Possibility
}
BoolValue is an implementation of Value that represents all the possible values of a boolean type.
func (*BoolValue) Difference ¶
Difference returns the possibile for v that are not found in o. o must be of type BoolValue.
func (*BoolValue) Equals ¶
func (v *BoolValue) Equals(o Value) Possibility
Equals returns the possibility of v equaling o. o must be of type BoolValue.
func (*BoolValue) Equivalent ¶
Equivalent returns true iff v and o are equivalent. See Value for the definition of equivalency.
func (*BoolValue) Intersect ¶
Intersect returns the intersection of possibile values for v and o. o must be of type BoolValue.
type Callstack ¶
type Callstack []CallstackEntry
Callstack holds the callstack to a point in the API file.
type CallstackEntry ¶
type CallstackEntry struct { Location parse.Node Function *semantic.Function Parameters map[*semantic.Parameter]Value }
CallstackEntry is a single entry in a callstack.
func (CallstackEntry) String ¶
func (e CallstackEntry) String() string
type ClassValue ¶
type ClassValue struct { // The class type. Class *semantic.Class // A map of field name to possible values for that field. Fields map[string]Value }
ClassValue is an implementation of Value that represents all the possible values of a class type.
func (*ClassValue) Clone ¶
func (v *ClassValue) Clone() Value
Clone returns a copy of v with a unique pointer.
func (*ClassValue) Difference ¶
func (v *ClassValue) Difference(o Value) Value
Difference (\) returns the class value with field values that are found in v but not found in o. o must be of type *ClassValue.
func (*ClassValue) Equals ¶
func (v *ClassValue) Equals(o Value) Possibility
Equals returns the possibility of all fields of v being equal to those in o. o must be of type *ClassValue.
func (*ClassValue) Equivalent ¶
func (v *ClassValue) Equivalent(o Value) bool
Equivalent returns true iff v and o are equivalent. Unlike Equals() which returns the possibility of two values being equal, Equivalent() returns true iff the set of possible field values are exactly equal. o must be of type *ClassValue.
func (*ClassValue) Intersect ¶
func (v *ClassValue) Intersect(o Value) Value
Intersect (∩) returns the class value with field values that are found in v and o. o must be of type *ClassValue.
func (*ClassValue) Print ¶
func (v *ClassValue) Print(results *Results) string
Print returns a textual representation of the value.
func (*ClassValue) Type ¶
func (v *ClassValue) Type() semantic.Type
Type returns the semantic class type of the value.
func (*ClassValue) Union ¶
func (v *ClassValue) Union(o Value) Value
Union (∪) returns the class value with field values that are found in v or o. o must be of type *ClassValue.
func (*ClassValue) Valid ¶
func (v *ClassValue) Valid() bool
Valid returns true if there is any possibility of this value equaling any other.
type EnumValue ¶
EnumValue is an implementation of Value that represents all the possible values of an enumerator.
func (*EnumValue) Difference ¶
Difference (\) returns the values that are found in v but not found in o. o must be of type *EnumValue.
func (*EnumValue) Equals ¶
func (v *EnumValue) Equals(o Value) Possibility
Equals returns the possibility of v being equal to o. o must be of type *EnumValue.
func (*EnumValue) Equivalent ¶
Equivalent returns true iff v and o are equivalent. Unlike Equals() which returns the possibility of two values being equal, Equivalent() returns true iff the set of possible values are exactly equal. o must be of type *EnumValue.
func (*EnumValue) GreaterEqual ¶
func (v *EnumValue) GreaterEqual(o Value) Possibility
GreaterEqual returns the possibility of v being greater or equal to o. o must be of type *EnumValue.
func (*EnumValue) GreaterThan ¶
func (v *EnumValue) GreaterThan(o Value) Possibility
GreaterThan returns the possibility of v being greater than o. o must be of type *EnumValue.
func (*EnumValue) Intersect ¶
Intersect (∩) returns the values that are found in both v and o. o must be of type *EnumValue.
func (*EnumValue) LessEqual ¶
func (v *EnumValue) LessEqual(o Value) Possibility
LessEqual returns the possibility of v being less than or equal to o. o must be of type *EnumValue.
func (*EnumValue) LessThan ¶
func (v *EnumValue) LessThan(o Value) Possibility
LessThan returns the possibility of v being less than o. o must be of type *EnumValue.
func (*EnumValue) SetGreaterEqual ¶
SetGreaterEqual returns a new value that represents the range of possible values in v that are greater than or equal to the lowest in o. o must be of type *EnumValue.
func (*EnumValue) SetGreaterThan ¶
SetGreaterThan returns a new value that represents the range of possible values in v that are greater than the lowest in o. o must be of type *EnumValue.
func (*EnumValue) SetLessEqual ¶
SetLessEqual returns a new value that represents the range of possible values in v that are less than or equal to the highest in o. o must be of type *EnumValue.
func (*EnumValue) SetLessThan ¶
SetLessThan returns a new value that represents the range of possible values in v that are less than to the highest in o. o must be of type *EnumValue.
type MapValue ¶
type MapValue struct { // The map type. Map *semantic.Map // A map of keys to values. The inverse of ValueToKey. KeyToValue map[Value]Value // A map of values to keys. The inverse of KeyToValue. ValueToKey map[Value]Value }
MapValue is an implementation of Value that represents a map variable. Map entries are stored in the KeyToValue and ValueToKey fields. These two maps are always kept in sync.
MapValue attempts to reduce the number of entries stored to a minimum to maintain decent performance while also trying to keep enough information to provide useful information (avoid tending towards unbounded keys and values).
All insertions and merges use the following method when merging the key value pair (k, v) into the map:
- If m contains an equivalent key to k, then change the existing value to be a union of the existing value and v.
- If m contains an equivalent value to v, then change the existing key to be a union of the existing key and k.
- If m does not contain an equivalent key to k or an equivalent value to v then add a new entry to m.
func (*MapValue) ContainsKey ¶
func (v *MapValue) ContainsKey(key Value) Possibility
ContainsKey returns the possibility of the key existing in the map.
func (*MapValue) Difference ¶
Difference is not supported by MapValue and will panic if called.
func (*MapValue) Equals ¶
func (v *MapValue) Equals(o Value) Possibility
Equals returns False as maps do not support equality tests.
func (*MapValue) Equivalent ¶
Equivalent returns false as maps do not support equivalency tests.
type Possibility ¶
type Possibility int
Possibility is an enumerator of possibilites.
const ( // True represents a logical certanty or true. True Possibility = iota // Maybe represents the possibility of true or false. Maybe // False represents a logical certanty of false. False // Impossible represents a contradiction of certanties (for example // True ∩ False) Impossible )
func (Possibility) And ¶
func (a Possibility) And(b Possibility) Possibility
And returns the logical-and of a and b.
func (Possibility) Difference ¶
func (a Possibility) Difference(b Possibility) Possibility
Difference returns the possibile for v that are not found in o.
func (Possibility) Equals ¶
func (a Possibility) Equals(b Possibility) Possibility
Equals returns the possibility of a equaling b.
func (Possibility) Intersect ¶
func (a Possibility) Intersect(b Possibility) Possibility
Intersect returns the intersection of possibile Possibilitys for a and b.
func (Possibility) MaybeFalse ¶
func (a Possibility) MaybeFalse() bool
MaybeFalse returns true iff a is False or Maybe.
func (Possibility) MaybeTrue ¶
func (a Possibility) MaybeTrue() bool
MaybeTrue returns true iff a is True or Maybe.
func (Possibility) Not ¶
func (a Possibility) Not() Possibility
Not returns the logical negation of a.
func (Possibility) Or ¶
func (a Possibility) Or(b Possibility) Possibility
Or returns the logical-or of a and b.
func (Possibility) Union ¶
func (a Possibility) Union(b Possibility) Possibility
Union returns the union of possibile Possibilitys for a and b.
type ReferenceValue ¶
type ReferenceValue struct { // The reference type. Ty semantic.Type // Unknown is the unknown value of the referenced type. Unknown Value // Assignments is the set of all assignments made to this value. Assignments map[*semantic.Create]struct{} }
ReferenceValue is an implementation of Value that represents all the possible references of a reference value type. As references are an indirection, this value only holds the set of references not the set of referenced values. The actual referenced values are held by the scope. ReferenceValues uses *semantic.Create as the reference handles.
func (*ReferenceValue) Clone ¶
func (v *ReferenceValue) Clone() Value
Clone returns a copy of v with a unique pointer.
func (*ReferenceValue) Difference ¶
func (v *ReferenceValue) Difference(o Value) Value
Difference (\) returns the reference value with assignments that are found in v but not found in o. o must be of type *ReferenceValue.
func (*ReferenceValue) Equals ¶
func (v *ReferenceValue) Equals(o Value) Possibility
Equals returns the possibility of the reference value v being equal to o. o must be of type *ReferenceValue.
func (*ReferenceValue) Equivalent ¶
func (v *ReferenceValue) Equivalent(o Value) bool
Equivalent returns true iff v and o are equivalent. Unlike Equals() which returns the possibility of two values being equal, Equivalent() returns true iff the set of possible field values are exactly equal. o must be of type *ReferenceValue.
func (*ReferenceValue) Intersect ¶
func (v *ReferenceValue) Intersect(o Value) Value
Intersect (∩) returns the reference value the assignments that are found in both v and o. o must be of type *ReferenceValue.
func (*ReferenceValue) Print ¶
func (v *ReferenceValue) Print(results *Results) string
Print returns a textual representation of the value.
func (*ReferenceValue) String ¶
func (v *ReferenceValue) String() string
func (*ReferenceValue) Type ¶
func (v *ReferenceValue) Type() semantic.Type
Type returns the semantic reference type of the value.
func (*ReferenceValue) Union ¶
func (v *ReferenceValue) Union(o Value) Value
Union (∪) returns the reference value with all the assignments of v and o. o must be of type *ReferenceValue.
type Relational ¶
type Relational interface { // GreaterThan returns the possibility of this value being greater than v. // // Examples: // [5] > [5] -> False // [1-3] > [2-5] -> Maybe // [1-3] > [4-6] -> False // [4-6] > [1-3] -> True GreaterThan(v Value) Possibility // GreaterEqual returns the possibility of this value being greater or equal // to v. // // Examples: // [5] >= [5] -> True // [1-3] >= [2-5] -> Maybe // [1-3] >= [4-6] -> False // [4-6] >= [1-3] -> True GreaterEqual(v Value) Possibility // LessThan returns the possibility of this value being less than v. // // Examples: // [5] < [5] -> False // [1-3] < [2-5] -> Maybe // [1-3] < [4-6] -> True // [4-6] < [1-3] -> False LessThan(v Value) Possibility // LessEqual returns the possibility of this value being less than or equal // to v. // // Examples: // [5] <= [5] -> True // [1-3] <= [2-5] -> Maybe // [1-3] <= [4-6] -> True // [4-6] <= [1-3] -> False LessEqual(v Value) Possibility }
Relational is the interface implemented by values that can perform relational comparisons.
type Results ¶
type Results struct { // Unreachables is the list of unreachable blocks and statements. Unreachables []Unreachable // Globals is the map of semantic globals to their possible values. Globals map[*semantic.Global]Value // Parameters is the map of semantic parameters to their possible values. Parameters map[*semantic.Parameter]Value // Instances is the map of semantic create statements to the possible values // for those instances. Instances map[*semantic.Create]Value }
Results holds the results of the static analysis.
type SetRelational ¶
type SetRelational interface { // SetGreaterThan returns a new value that represents the range of possible // values in this value that are greater than the lowest in v. // // Examples: // [1-9] and [5] -> [6-9] // [1-9] and [2-5] -> [3-9] // [1-3] and [4-6] -> [-] // [4-6] and [1-3] -> [4-6] SetGreaterThan(v Value) Value // SetGreaterEqual returns a new value that represents the range of possible // values in this value that are greater than or equal to the lowest in v. // // Examples: // [1-9] and [5] -> [5-9] // [1-9] and [2-5] -> [2-9] // [1-3] and [4-6] -> [-] // [4-6] and [1-3] -> [4-6] SetGreaterEqual(v Value) Value // SetLessThan returns a new value that represents the range of possible // values in this value that are less than to the highest in v. // // Examples: // [1-9] and [5] -> [1-4] // [1-9] and [2-5] -> [1-4] // [1-3] and [4-6] -> [1-3] // [4-6] and [1-3] -> [-] SetLessThan(v Value) Value // SetLessEqual returns a new value that represents the range of possible // values in this value that are less than or equal to the highest in v. // // Examples: // [1-9] and [5] -> [1-5] // [1-9] and [2-5] -> [1-5] // [1-3] and [4-6] -> [1-3] // [4-6] and [1-3] -> [-] SetLessEqual(v Value) Value }
SetRelational is the interface implemented by values that produce new constrained values.
type UintValue ¶
type UintValue struct { Ty *semantic.Builtin Ranges interval.U64SpanList }
UintValue is an implementation of Value that represents all the possible values of an unsigned integer type. Although UintValue naturally represents unsigned integers, it can also be used to represent signed values by shifting the signed value into the unsigned range.
func (*UintValue) Difference ¶
Difference (\) returns the values that are found in v but not found in o. o must be of type *UintValue.
func (*UintValue) Equals ¶
func (v *UintValue) Equals(o Value) Possibility
Equals returns the possibility of v being equal to o. o must be of type *UintValue.
func (*UintValue) Equivalent ¶
Equivalent returns true iff v and o are equivalent. Unlike Equals() which returns the possibility of two values being equal, Equivalent() returns true iff the set of possible values are exactly equal. o must be of type *UintValue.
func (*UintValue) GreaterEqual ¶
func (v *UintValue) GreaterEqual(o Value) Possibility
GreaterEqual returns the possibility of v being greater or equal to o. o must be of type *UintValue.
func (*UintValue) GreaterThan ¶
func (v *UintValue) GreaterThan(o Value) Possibility
GreaterThan returns the possibility of v being greater than o. o must be of type *UintValue.
func (*UintValue) Intersect ¶
Intersect (∩) returns the values that are found in both v and o. o must be of type *UintValue.
func (*UintValue) LessEqual ¶
func (v *UintValue) LessEqual(o Value) Possibility
LessEqual returns the possibility of v being less than or equal to o. o must be of type *UintValue.
func (*UintValue) LessThan ¶
func (v *UintValue) LessThan(o Value) Possibility
LessThan returns the possibility of v being less than o. o must be of type *UintValue.
func (*UintValue) SetGreaterEqual ¶
SetGreaterEqual returns a new value that represents the range of possible values in v that are greater than or equal to the lowest in o. o must be of type *UintValue.
func (*UintValue) SetGreaterThan ¶
SetGreaterThan returns a new value that represents the range of possible values in v that are greater than the lowest in o. o must be of type *UintValue.
func (*UintValue) SetLessEqual ¶
SetLessEqual returns a new value that represents the range of possible values in v that are less than or equal to the highest in o. o must be of type *UintValue.
func (*UintValue) SetLessThan ¶
SetLessThan returns a new value that represents the range of possible values in v that are less than to the highest in o. o must be of type *UintValue.
type Unreachable ¶
Unreachable represents an unreachable block or statement.
type UntrackedValue ¶
UntrackedValue is an implementation of Value used for types that are not tracked by static analysis.
func (*UntrackedValue) Clone ¶
func (v *UntrackedValue) Clone() Value
Clone returns a new pointer to a UntrackedValue.
func (*UntrackedValue) Difference ¶
func (v *UntrackedValue) Difference(o Value) Value
Difference returns a new pointer to a UntrackedValue.
func (*UntrackedValue) Equals ¶
func (v *UntrackedValue) Equals(Value) Possibility
Equals returns Maybe.
func (*UntrackedValue) Equivalent ¶
func (v *UntrackedValue) Equivalent(Value) bool
Equivalent returns true.
func (*UntrackedValue) Intersect ¶
func (v *UntrackedValue) Intersect(o Value) Value
Intersect returns a new pointer to a UntrackedValue.
func (*UntrackedValue) Print ¶
func (v *UntrackedValue) Print(*Results) string
Print returns "<untracked>"
func (*UntrackedValue) Type ¶
func (v *UntrackedValue) Type() semantic.Type
Type returns the semantic type of the untracked value.
func (*UntrackedValue) Union ¶
func (v *UntrackedValue) Union(o Value) Value
Union returns a new pointer to a UntrackedValue.
type Value ¶
type Value interface { // Print returns a textual representation of the value. Print(results *Results) string // Type returns the semantic type of the value. Type() semantic.Type // Equivalent returns true iff this and v are equivalent. // Unlike Equals() which returns the possibility of two values being equal, // Equivalent() returns true iff the set of possible values are exactly // equal. // // Examples: // [5] and [5] are equivalent. // [1-5] and [1-5] are equivalent. // [1-3] and [1] are not equivalent. // [1] and [2] are not equivalent. Equivalent(v Value) bool // Equals returns the possibility of this value being equal to v. // If this and v have go-equality then Equals() will return True. // // Examples: // [5] and [5] returns True. // [1-5] and [1-5] returns Maybe. // [1-3] and [5-7] returns False. // [1] and [2] returns False. Equals(v Value) Possibility // Valid returns true if there is any possibility of this value equaling // any other. Valid() bool // Clone returns a copy of this value with a unique instance. // The cloned value will not have go-equality with this and so will not be // considered to have algerbraic equality. Clone() Value // Union (∪) returns the values that are found in this or v. // // Examples: // [5] ∪ [5] -> [5] // [1-3] ∪ [2-5] -> [1-5] // [1-3] ∪ [4-6] -> [1-3] [4-6] // [1] ∪ [3] -> [1] [3] Union(v Value) Value // Intersect (∩) returns the values that are found in both this and v. // // Examples: // [5] ∩ [5] -> [5] // [1-3] ∩ [2-5] -> [2-3] // [1-3] ∩ [4-6] -> [-] // [1] ∩ [3] -> [-] Intersect(v Value) Value // Difference (\) returns the values that are found in this but not found in v. // // Examples: // [5] \ [5] -> [-] // [1-3] \ [2-5] -> [1] // [1-3] \ [4-6] -> [1-3] // [1] \ [3] -> [1] Difference(v Value) Value }
Value represents the data flow analysis representation of a variable or expression. Unlike the value of a variable or expression at runtime, the static analysis representation of a value usually represents a range of possible runtime values. As such many of the value implementations are backed by some sort of set.
Values are immutable. All transformation methods on a value should return a new value.
Values that have go-equality can be considered to have algerbraic equality, even if that Value represents a wide range of possible runtime values.