1 | // Copyright (c) 2016, the Dart project authors. Please see the AUTHORS file |
2 | // for details. All rights reserved. Use of this source code is governed by a |
3 | // BSD-style license that can be found in the LICENSE file. |
4 | |
5 | #ifndef RUNTIME_VM_TOKEN_POSITION_H_ |
6 | #define RUNTIME_VM_TOKEN_POSITION_H_ |
7 | |
8 | #include "platform/utils.h" |
9 | #include "vm/allocation.h" |
10 | |
11 | namespace dart { |
12 | |
13 | // The token space is organized as follows: |
14 | // |
15 | // Sentinel values start at -1 and move towards negative infinity: |
16 | // kNoSourcePos -> -1 |
17 | // ClassifyingTokenPositions 1 -> -1 - 1 |
18 | // ClassifyingTokenPositions N -> -1 - N |
19 | // |
20 | // Real token positions represent source offsets in some script, and are encoded |
21 | // as non-negative values which are equal to that offset. |
22 | // |
23 | // Synthetically created functions that correspond to user code are given |
24 | // starting token positions unique from other synthetic functions. The value for |
25 | // these token positions encode a unique non-negative value as a negative number |
26 | // within [kSmiMin32, -1 - N). |
27 | // |
28 | // For example: |
29 | // A synthetic token with value 0 is encoded as ((-1 - N) - (0 + 1)) = -2 - N. |
30 | // A synthetic token with value 1 is encoded as ((-1 - N) - (1 + 1)) = -3 - N. |
31 | // |
32 | // Note that the encoded value is _not_ related to any possible real token |
33 | // position, as two real token positions for different scripts can have the same |
34 | // value and thus cannot serve as a unique nonce for a synthetic node. |
35 | // |
36 | // All other nodes read from user code, such as non-synthetic functions, fields, |
37 | // etc., are given real starting token positions. All nodes coming from user |
38 | // code, both real or synthetic, with ending token positions have real ending |
39 | // token positions. |
40 | // |
41 | // This organization allows for ~1 billion token positions. |
42 | |
43 | #define SENTINEL_TOKEN_DESCRIPTORS(V) \ |
44 | V(NoSource, -1) \ |
45 | V(Box, -2) \ |
46 | V(ParallelMove, -3) \ |
47 | V(TempMove, -4) \ |
48 | V(Constant, -5) \ |
49 | V(MoveArgument, -6) \ |
50 | V(ControlFlow, -7) \ |
51 | V(Context, -8) \ |
52 | V(MethodExtractor, -9) \ |
53 | V(DeferredSlowPath, -10) \ |
54 | V(DeferredDeoptInfo, -11) \ |
55 | V(DartCodePrologue, -12) \ |
56 | V(DartCodeEpilogue, -13) \ |
57 | V(Last, -14) // Always keep this at the end. |
58 | |
59 | // A token position represents either a debug safe source (real) position, |
60 | // non-debug safe unique (synthetic) position, or a classifying value used |
61 | // by the profiler. |
62 | class TokenPosition { |
63 | public: |
64 | uword Hash() const; |
65 | |
66 | // Returns whether the token positions are equal. Defined for all token |
67 | // positions. |
68 | bool operator==(const TokenPosition& b) const { return value() == b.value(); } |
69 | |
70 | // Returns whether the token positions are not equal. Defined for all token |
71 | // positions. |
72 | bool operator!=(const TokenPosition& b) const { return !(*this == b); } |
73 | |
74 | // Returns whether the token position is less than [b]. Only defined for |
75 | // real token positions. |
76 | inline bool operator<(const TokenPosition& b) const { |
77 | return Pos() < b.Pos(); |
78 | } |
79 | |
80 | // Returns whether the token position is greater than [b]. Only defined for |
81 | // real token positions. |
82 | inline bool operator>(const TokenPosition& b) const { return b < *this; } |
83 | |
84 | // Returns whether the token position is less than or equal to [b]. Only |
85 | // defined for real token positions. |
86 | inline bool operator<=(const TokenPosition& b) const { return !(*this > b); } |
87 | |
88 | // Returns whether the token position is greater than or equal to [b]. Only |
89 | // defined for real token positions. |
90 | inline bool operator>=(const TokenPosition& b) const { return !(*this < b); } |
91 | |
92 | // For real token positions, returns whether this is between [a] and [b], |
93 | // inclusive. If [a] or [b] is non-real, they are treated as less than |
94 | // any real token position. |
95 | // |
96 | // For synthetic token positions, returns whether [a] or [b] equals this. |
97 | // |
98 | // For other token positions, always returns false. |
99 | bool IsWithin(const TokenPosition& a, const TokenPosition& b) const { |
100 | if (IsReal()) return (a.value() <= value()) && (value() <= b.value()); |
101 | if (IsSynthetic()) return (a == *this) || (b == *this); |
102 | return false; |
103 | } |
104 | |
105 | // Returns [a] if both positions are not real, the real position if only one |
106 | // of [a] and [b] is real, or the minimum position of [a] and [b]. |
107 | static const TokenPosition& Min(const TokenPosition& a, |
108 | const TokenPosition& b) { |
109 | if (!b.IsReal()) return a; |
110 | if (!a.IsReal()) return b; |
111 | return b.value() < a.value() ? b : a; |
112 | } |
113 | // Returns [a] if both positions are not real, the real position if only one |
114 | // of [a] and [b] is real, or the maximum position of [a] and [b]. |
115 | static const TokenPosition& Max(const TokenPosition& a, |
116 | const TokenPosition& b) { |
117 | if (!b.IsReal()) return a; |
118 | if (!a.IsReal()) return b; |
119 | return b.value() > a.value() ? b : a; |
120 | } |
121 | |
122 | // Compares two arbitrary source positions for use in sorting, where a |
123 | // negative return means [a] sorts before [b], a return of 0 means [a] is the |
124 | // same as [b], and a positive return means [a] sorts after [b]. |
125 | // |
126 | // Does _not_ correspond to the relational operators on token positions, as |
127 | // this also allows comparison of kNoSource, classifying, and synthetic token |
128 | // positions to each other. |
129 | static intptr_t CompareForSorting(const TokenPosition& a, |
130 | const TokenPosition& b) { |
131 | return a.value() - b.value(); |
132 | } |
133 | |
134 | static constexpr int32_t kMaxSentinelDescriptors = 64; |
135 | |
136 | #define DECLARE_VALUES(name, value) \ |
137 | static constexpr int32_t k##name##Pos = value; \ |
138 | static const TokenPosition k##name; |
139 | SENTINEL_TOKEN_DESCRIPTORS(DECLARE_VALUES); |
140 | #undef DECLARE_VALUES |
141 | // Check assumptions used in Is<X> methods below. |
142 | #define CHECK_VALUES(name, value) \ |
143 | static_assert(k##name##Pos < 0, "Non-negative sentinel descriptor"); \ |
144 | static_assert( \ |
145 | k##name##Pos == kNoSourcePos || k##name##Pos <= kBoxPos, \ |
146 | "Box sentinel descriptor is not greatest classifying sentinel value"); \ |
147 | static_assert(kLastPos <= k##name##Pos, \ |
148 | "Last sentinel descriptor is not least sentinel valu"); \ |
149 | SENTINEL_TOKEN_DESCRIPTORS(CHECK_VALUES); |
150 | #undef CHECK_VALUES |
151 | static_assert(kLastPos > -kMaxSentinelDescriptors, |
152 | "More sentinel descriptors than expected" ); |
153 | |
154 | static constexpr int32_t kMinSourcePos = 0; |
155 | static const TokenPosition kMinSource; |
156 | static constexpr int32_t kMaxSourcePos = |
157 | kSmiMax32 - kMaxSentinelDescriptors - 2; |
158 | static const TokenPosition kMaxSource; |
159 | |
160 | // Decode from a serialized form. |
161 | static TokenPosition Deserialize(int32_t value); |
162 | |
163 | // Encode into a serialized form. |
164 | int32_t Serialize() const; |
165 | |
166 | // Given a real token position, returns the next real token position. |
167 | TokenPosition Next() { |
168 | ASSERT(IsReal()); |
169 | return TokenPosition(value_ + 1); |
170 | } |
171 | |
172 | // Return the source position for real token positions. |
173 | inline intptr_t Pos() const { |
174 | ASSERT(IsReal()); |
175 | return value_; |
176 | } |
177 | |
178 | // Is |this| a classifying sentinel source position? |
179 | // Classifying positions are used by the profiler to group instructions whose |
180 | // cost isn't naturally attributable to a source location. |
181 | inline bool IsClassifying() const { |
182 | return (value_ >= kBox.value()) && (value_ <= kLast.value()); |
183 | } |
184 | |
185 | // Is |this| the no source position sentinel? |
186 | inline bool IsNoSource() const { return value_ == kNoSourcePos; } |
187 | |
188 | // Is |this| a synthetic source position? |
189 | // Synthetic source positions are used by the profiler to attribute ticks to a |
190 | // pieces of source, but ignored by the debugger as potential breakpoints. |
191 | inline bool IsSynthetic() const { return value_ < kLastPos; } |
192 | |
193 | // Is |this| a real source position? |
194 | inline bool IsReal() const { return value_ >= kMinSourcePos; } |
195 | |
196 | // Is |this| a debug pause source position? |
197 | inline bool IsDebugPause() const { return IsReal(); } |
198 | |
199 | // Creates a synthetic source position from a non-negative value. |
200 | static TokenPosition Synthetic(intptr_t value) { |
201 | ASSERT(value >= 0 && value <= kMaxSourcePos); |
202 | return TokenPosition((kLastPos - 1) - value); |
203 | } |
204 | |
205 | // Encode the token position for storage in the coverage array. |
206 | intptr_t EncodeCoveragePosition(bool is_branch_coverage); |
207 | |
208 | // Decode a token position that was stored in the coverage array. |
209 | static TokenPosition DecodeCoveragePosition(intptr_t encoded_position, |
210 | bool* is_branch_coverage); |
211 | |
212 | const char* ToCString() const; |
213 | |
214 | private: |
215 | explicit TokenPosition(intptr_t value) : value_(value) {} |
216 | |
217 | // The raw value of this TokenPosition. |
218 | intptr_t value() const { return value_; } |
219 | |
220 | int32_t value_; |
221 | |
222 | DISALLOW_ALLOCATION(); |
223 | }; |
224 | |
225 | } // namespace dart |
226 | |
227 | #endif // RUNTIME_VM_TOKEN_POSITION_H_ |
228 | |