1 /*
2 * Copyright (C) 2016 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
17 #include "ConstantExpression.h"
18
19 #include <stdio.h>
20 #include <string>
21 #include <android-base/parseint.h>
22 #include <android-base/logging.h>
23 #include <sstream>
24
25 #include "EnumType.h"
26
27 // The macros are really nasty here. Consider removing
28 // as many macros as possible.
29
30 #define STREQ(__x__, __y__) (strcmp((__x__), (__y__)) == 0)
31 #define OPEQ(__y__) STREQ(op, __y__)
32 #define COMPUTE_UNARY(__op__) if(OPEQ(#__op__)) return __op__ val;
33 #define COMPUTE_BINARY(__op__) if(OPEQ(#__op__)) return lval __op__ rval;
34 #define OP_IS_BIN_ARITHMETIC (OPEQ("+") || OPEQ("-") || OPEQ("*") || OPEQ("/") || OPEQ("%"))
35 #define OP_IS_BIN_BITFLIP (OPEQ("|") || OPEQ("^") || OPEQ("&"))
36 #define OP_IS_BIN_COMP (OPEQ("<") || OPEQ(">") || OPEQ("<=") || OPEQ(">=") || OPEQ("==") || OPEQ("!="))
37 #define OP_IS_BIN_SHIFT (OPEQ(">>") || OPEQ("<<"))
38 #define OP_IS_BIN_LOGICAL (OPEQ("||") || OPEQ("&&"))
39 #define SK(__x__) ScalarType::Kind::KIND_##__x__
40 #define SHOULD_NOT_REACH() CHECK(false) << __LINE__ << ": should not reach here: "
41
42 #define SWITCH_KIND(__cond__, __action__, __def__) \
43 switch(__cond__) { \
44 case SK(BOOL): __action__(bool) \
45 case SK(UINT8): __action__(uint8_t) \
46 case SK(INT8): __action__(int8_t) \
47 case SK(UINT16): __action__(uint16_t) \
48 case SK(INT16): __action__(int16_t) \
49 case SK(UINT32): __action__(uint32_t) \
50 case SK(INT32): __action__(int32_t) \
51 case SK(UINT64): __action__(uint64_t) \
52 case SK(INT64): __action__(int64_t) \
53 default: __def__ \
54 } \
55
56 namespace android {
57
isSupported(ScalarType::Kind kind)58 static inline bool isSupported(ScalarType::Kind kind) {
59 return SK(BOOL) == kind || ScalarType(kind).isValidEnumStorageType();
60 }
61
62 /* See docs at the end for details on integral promotion. */
integralPromotion(ScalarType::Kind in)63 ScalarType::Kind integralPromotion(ScalarType::Kind in) {
64 return SK(INT32) < in ? in : SK(INT32); // note that KIND_INT32 < KIND_UINT32
65 }
66
67 /* See docs at the end for details on usual arithmetic conversion. */
usualArithmeticConversion(ScalarType::Kind lft,ScalarType::Kind rgt)68 ScalarType::Kind usualArithmeticConversion(ScalarType::Kind lft,
69 ScalarType::Kind rgt) {
70 CHECK(isSupported(lft) && isSupported(rgt));
71 // Kinds in concern: bool, (u)int[8|16|32|64]
72 if(lft == rgt) return lft; // easy case
73 if(lft == SK(BOOL)) return rgt;
74 if(rgt == SK(BOOL)) return lft;
75 bool isLftSigned = (lft == SK(INT8)) || (lft == SK(INT16))
76 || (lft == SK(INT32)) || (lft == SK(INT64));
77 bool isRgtSigned = (rgt == SK(INT8)) || (rgt == SK(INT16))
78 || (rgt == SK(INT32)) || (rgt == SK(INT64));
79 if(isLftSigned == isRgtSigned) return lft < rgt ? rgt : lft;
80 ScalarType::Kind unsignedRank = isLftSigned ? rgt : lft;
81 ScalarType::Kind signedRank = isLftSigned ? lft : rgt;
82 if(unsignedRank >= signedRank) return unsignedRank;
83 if(signedRank > unsignedRank) return signedRank;
84
85 // Although there is such rule to return "the unsigned counterpart of
86 // the signed operand", it should not reach here in our HIDL grammar.
87 LOG(FATAL) << "Could not do usual arithmetic conversion for type "
88 << lft << "and" << rgt;
89 switch(signedRank) {
90 case SK(INT8): return SK(UINT8);
91 case SK(INT16): return SK(UINT16);
92 case SK(INT32): return SK(UINT32);
93 case SK(INT64): return SK(UINT64);
94 default: return SK(UINT64);
95 }
96 }
97
98 template <class T>
handleUnary(const char * op,T val)99 T handleUnary(const char *op, T val) {
100 COMPUTE_UNARY(+)
101 COMPUTE_UNARY(-)
102 COMPUTE_UNARY(!)
103 COMPUTE_UNARY(~)
104 // Should not reach here.
105 SHOULD_NOT_REACH() << "Could not handleUnary for " << op << " " << val;
106 return static_cast<T>(0xdeadbeef);
107 }
108
109 template <class T>
handleBinaryCommon(T lval,const char * op,T rval)110 T handleBinaryCommon(T lval, const char *op, T rval) {
111 COMPUTE_BINARY(+)
112 COMPUTE_BINARY(-)
113 COMPUTE_BINARY(*)
114 COMPUTE_BINARY(/)
115 COMPUTE_BINARY(%)
116 COMPUTE_BINARY(|)
117 COMPUTE_BINARY(^)
118 COMPUTE_BINARY(&)
119 // comparison operators: return 0 or 1 by nature.
120 COMPUTE_BINARY(==)
121 COMPUTE_BINARY(!=)
122 COMPUTE_BINARY(<)
123 COMPUTE_BINARY(>)
124 COMPUTE_BINARY(<=)
125 COMPUTE_BINARY(>=)
126 // Should not reach here.
127 SHOULD_NOT_REACH() << "Could not handleBinaryCommon for "
128 << lval << " " << op << " " << rval;
129 return static_cast<T>(0xdeadbeef);
130 }
131
132 template <class T>
handleShift(T lval,const char * op,int64_t rval)133 T handleShift(T lval, const char *op, int64_t rval) {
134 // just cast rval to int64_t and it should fit.
135 COMPUTE_BINARY(>>)
136 COMPUTE_BINARY(<<)
137 // Should not reach here.
138 SHOULD_NOT_REACH() << "Could not handleShift for"
139 << lval << " " << op << " " << rval;
140 return static_cast<T>(0xdeadbeef);
141 }
142
handleLogical(bool lval,const char * op,bool rval)143 bool handleLogical(bool lval, const char *op, bool rval) {
144 COMPUTE_BINARY(||);
145 COMPUTE_BINARY(&&);
146 // Should not reach here.
147 SHOULD_NOT_REACH() << "Could not handleLogical for"
148 << lval << " " << op << " " << rval;
149 return false;
150 }
151
ConstantExpression()152 ConstantExpression::ConstantExpression() {
153 }
154
Zero(ScalarType::Kind kind)155 ConstantExpression ConstantExpression::Zero(ScalarType::Kind kind) {
156 ConstantExpression ce = ValueOf(kind, 0);
157 ce.mExpr = "0";
158 return ce;
159 }
160
One(ScalarType::Kind kind)161 ConstantExpression ConstantExpression::One(ScalarType::Kind kind) {
162 ConstantExpression ce = ValueOf(kind, 1);
163 ce.mExpr = "1";
164 return ce;
165 }
166
ValueOf(ScalarType::Kind kind,uint64_t value)167 ConstantExpression ConstantExpression::ValueOf(ScalarType::Kind kind, uint64_t value) {
168 ConstantExpression ce;
169 CHECK(isSupported(kind));
170
171 ce.mExpr = "";
172 ce.mType = kConstExprLiteral;
173 ce.mValueKind = kind;
174 ce.mValue = value;
175 ce.mTrivialDescription = true;
176 return ce;
177 }
ConstantExpression(const ConstantExpression & other)178 ConstantExpression::ConstantExpression(const ConstantExpression& other) {
179 *this = other;
180 }
181
182 /* Copy constructor, with the expr overriden and treated non-trivial */
ConstantExpression(const ConstantExpression & other,std::string expr)183 ConstantExpression::ConstantExpression(const ConstantExpression& other, std::string expr) {
184 *this = other;
185 mExpr = expr;
186 mTrivialDescription = false;
187 }
188
operator =(const ConstantExpression & other)189 ConstantExpression& ConstantExpression::operator=(const ConstantExpression& other) {
190 mType = other.mType;
191 mValueKind = other.mValueKind;
192 mValue = other.mValue;
193 mExpr = other.mExpr;
194 mTrivialDescription = other.mTrivialDescription;
195 return *this;
196 }
197
198 /* Literals. */
ConstantExpression(const char * value)199 ConstantExpression::ConstantExpression(const char *value)
200 : mExpr(value), mType(kConstExprLiteral), mTrivialDescription(true) {
201 const char* head = value, *tail = head + strlen(value) - 1;
202 bool isLong = false, isUnsigned = false;
203 bool isHex = (value[0] == '0' && (value[1] == 'x' || value[1] == 'X'));
204 while(tail >= head && (*tail == 'u' || *tail == 'U' || *tail == 'l' || *tail == 'L')) {
205 isUnsigned |= (*tail == 'u' || *tail == 'U');
206 isLong |= (*tail == 'l' || *tail == 'L');
207 tail--;
208 }
209 char *newVal = strndup(value, tail - head + 1);
210 bool parseOK = base::ParseUint(newVal, &mValue);
211 free(newVal);
212 CHECK(parseOK) << "Could not parse as integer: " << value;
213
214 // guess literal type.
215 if(isLong) {
216 if(isUnsigned) // ul
217 mValueKind = SK(UINT64);
218 else // l
219 mValueKind = SK(INT64);
220 } else { // no l suffix
221 if(isUnsigned) { // u
222 if(mValue <= UINT32_MAX)
223 mValueKind = SK(UINT32);
224 else
225 mValueKind = SK(UINT64);
226 } else { // no suffix
227 if(isHex) {
228 if(mValue <= INT32_MAX) // mValue always >= 0
229 mValueKind = SK(INT32);
230 else if(mValue <= UINT32_MAX)
231 mValueKind = SK(UINT32);
232 else if(mValue <= INT64_MAX) // mValue always >= 0
233 mValueKind = SK(INT64);
234 else if(mValue <= UINT64_MAX)
235 mValueKind = SK(UINT64);
236 } else {
237 if(mValue <= INT32_MAX) // mValue always >= 0
238 mValueKind = SK(INT32);
239 else
240 mValueKind = SK(INT64);
241 }
242 }
243 }
244 }
245
246 /* Unary operations. */
ConstantExpression(const char * op,const ConstantExpression * value)247 ConstantExpression::ConstantExpression(const char *op,
248 const ConstantExpression *value)
249 : mExpr(std::string("(") + op + value->mExpr + ")"),
250 mType(kConstExprUnary),
251 mValueKind(value->mValueKind) {
252
253 #define CASE_UNARY(__type__)\
254 mValue = handleUnary(op, static_cast<__type__>(value->mValue)); return;
255
256 SWITCH_KIND(mValueKind, CASE_UNARY, SHOULD_NOT_REACH(); return;)
257 }
258
259 /* Binary operations. */
ConstantExpression(const ConstantExpression * lval,const char * op,const ConstantExpression * rval)260 ConstantExpression::ConstantExpression(const ConstantExpression *lval,
261 const char *op,
262 const ConstantExpression* rval)
263 : mExpr(std::string("(") + lval->mExpr + " " + op + " " + rval->mExpr + ")"),
264 mType(kConstExprBinary)
265 {
266
267 bool isArithmeticOrBitflip = OP_IS_BIN_ARITHMETIC || OP_IS_BIN_BITFLIP;
268
269 // CASE 1: + - * / % | ^ & < > <= >= == !=
270 if(isArithmeticOrBitflip || OP_IS_BIN_COMP) {
271 // promoted kind for both operands.
272 ScalarType::Kind promoted = usualArithmeticConversion(
273 integralPromotion(lval->mValueKind),
274 integralPromotion(rval->mValueKind));
275 // result kind.
276 mValueKind = isArithmeticOrBitflip
277 ? promoted // arithmetic or bitflip operators generates promoted type
278 : SK(BOOL); // comparison operators generates bool
279
280 #define CASE_BINARY_COMMON(__type__)\
281 mValue = handleBinaryCommon(static_cast<__type__>(lval->mValue), op, static_cast<__type__>(rval->mValue)); return;
282
283 SWITCH_KIND(promoted, CASE_BINARY_COMMON, SHOULD_NOT_REACH(); return;)
284 }
285
286 // CASE 2: << >>
287 if(OP_IS_BIN_SHIFT) {
288 mValueKind = integralPromotion(lval->mValueKind);
289 // instead of promoting rval, simply casting it to int64 should also be good.
290 int64_t numBits = rval->cast<int64_t>();
291 if(numBits < 0) {
292 // shifting with negative number of bits is undefined in C. In HIDL it
293 // is defined as shifting into the other direction.
294 op = OPEQ("<<") ? ">>" : "<<";
295 numBits = -numBits;
296 }
297
298 #define CASE_SHIFT(__type__)\
299 mValue = handleShift(static_cast<__type__>(lval->mValue), op, numBits); return;
300
301 SWITCH_KIND(mValueKind, CASE_SHIFT, SHOULD_NOT_REACH(); return;)
302 }
303
304 // CASE 3: && ||
305 if(OP_IS_BIN_LOGICAL) {
306 mValueKind = SK(BOOL);
307 // easy; everything is bool.
308 mValue = handleLogical(lval->mValue, op, rval->mValue);
309 return;
310 }
311
312 SHOULD_NOT_REACH();
313 }
314
315 /* Ternary ?: operation. */
ConstantExpression(const ConstantExpression * cond,const ConstantExpression * trueVal,const ConstantExpression * falseVal)316 ConstantExpression::ConstantExpression(const ConstantExpression *cond,
317 const ConstantExpression *trueVal,
318 const ConstantExpression *falseVal)
319 : mExpr(std::string("(") + cond->mExpr + "?" + trueVal->mExpr
320 + ":" + falseVal->mExpr + ")"),
321 mType(kConstExprTernary) {
322
323 // note: for ?:, unlike arithmetic ops, integral promotion is not necessary.
324 mValueKind = usualArithmeticConversion(trueVal->mValueKind,
325 falseVal->mValueKind);
326
327 #define CASE_TERNARY(__type__)\
328 mValue = cond->mValue ? (static_cast<__type__>(trueVal->mValue)) : (static_cast<__type__>(falseVal->mValue)); return;
329
330 SWITCH_KIND(mValueKind, CASE_TERNARY, SHOULD_NOT_REACH(); return;)
331 }
332
addOne() const333 ConstantExpression ConstantExpression::addOne() const {
334 ConstantExpression myOne = ConstantExpression::One(mValueKind);
335 return ConstantExpression(this, "+", &myOne).toLiteral();
336 }
337
toLiteral()338 ConstantExpression &ConstantExpression::toLiteral() {
339 mExpr = value();
340 mType = kConstExprLiteral;
341 return *this;
342 }
343
description() const344 const std::string &ConstantExpression::description() const {
345 return mExpr;
346 }
347
descriptionIsTrivial() const348 bool ConstantExpression::descriptionIsTrivial() const {
349 return mTrivialDescription;
350 }
351
value() const352 std::string ConstantExpression::value() const {
353 return rawValue(mValueKind);
354 }
355
value(ScalarType::Kind castKind) const356 std::string ConstantExpression::value(ScalarType::Kind castKind) const {
357 return rawValue(castKind);
358 }
359
cppValue() const360 std::string ConstantExpression::cppValue() const {
361 return cppValue(mValueKind);
362 }
363
cppValue(ScalarType::Kind castKind) const364 std::string ConstantExpression::cppValue(ScalarType::Kind castKind) const {
365 std::string literal(rawValue(castKind));
366 // this is a hack to translate
367 // enum x : int64_t { y = 1l << 63 };
368 // into
369 // enum class x : int64_t { y = (int64_t)-9223372036854775808ull };
370 // by adding the explicit cast.
371 // Because 9223372036854775808 is uint64_t, and
372 // -(uint64_t)9223372036854775808 == 9223372036854775808 could not
373 // be narrowed to int64_t.
374 if(castKind == SK(INT64) && (int64_t)mValue == INT64_MIN) {
375 return strdup(("static_cast<"
376 + ScalarType(SK(INT64)).getCppStackType() // "int64_t"
377 + ">(" + literal + "ull)").c_str());
378 }
379
380 // add suffix if necessary.
381 if(castKind == SK(UINT32) || castKind == SK(UINT64)) literal += "u";
382 if(castKind == SK(UINT64) || castKind == SK(INT64)) literal += "ll";
383 return literal;
384 }
385
javaValue() const386 std::string ConstantExpression::javaValue() const {
387 return javaValue(mValueKind);
388 }
389
javaValue(ScalarType::Kind castKind) const390 std::string ConstantExpression::javaValue(ScalarType::Kind castKind) const {
391 switch(castKind) {
392 case SK(UINT64): return rawValue(SK(INT64)) + "L";
393 case SK(INT64): return rawValue(SK(INT64)) + "L";
394 case SK(UINT32): return rawValue(SK(INT32));
395 case SK(UINT16): return rawValue(SK(INT16));
396 case SK(UINT8) : return rawValue(SK(INT8));
397 case SK(BOOL) :
398 return this->cast<bool>() ? strdup("true") : strdup("false");
399 default: break;
400 }
401 return rawValue(castKind);
402 }
403
rawValue(ScalarType::Kind castKind) const404 std::string ConstantExpression::rawValue(ScalarType::Kind castKind) const {
405
406 #define CASE_STR(__type__) return std::to_string(this->cast<__type__>());
407
408 SWITCH_KIND(castKind, CASE_STR, SHOULD_NOT_REACH(); return 0; );
409 }
410
411 template<typename T>
cast() const412 T ConstantExpression::cast() const {
413
414 #define CASE_CAST_T(__type__) return static_cast<T>(static_cast<__type__>(mValue));
415
416 SWITCH_KIND(mValueKind, CASE_CAST_T, SHOULD_NOT_REACH(); return 0; );
417 }
418
castSizeT() const419 size_t ConstantExpression::castSizeT() const {
420 return this->cast<size_t>();
421 }
422
423 /*
424
425 Evaluating expressions in HIDL language
426
427 The following rules are mostly like that in:
428 http://en.cppreference.com/w/cpp/language/operator_arithmetic
429 http://en.cppreference.com/w/cpp/language/operator_logical
430 http://en.cppreference.com/w/cpp/language/operator_comparison
431 http://en.cppreference.com/w/cpp/language/operator_other
432
433 The type of literal is the first type which the value
434 can fit from the list of types depending on the suffix and bases.
435
436 suffix decimal bases hexadecimal bases
437 no suffix int32_t int32_t
438 int64_t uint32_t
439 int64_t
440 uint64_t
441
442 u/U uint32_t (same as left)
443 uint64_t
444
445 l/L int64_t int64_t
446
447 ul/UL/uL/Ul uint64_t uint64_t
448
449
450 Note: There are no negative integer literals.
451 -1 is the unary minus applied to 1.
452
453 Unary arithmetic and bitwise operators (~ + -):
454 don't change the type of the argument.
455 (so -1u = -(1u) has type uint32_t)
456
457 Binary arithmetic and bitwise operators (except shifts) (+ - * / % & | ^):
458 1. Integral promotion is first applied on both sides.
459 2. If both operands have the same type, no promotion is necessary.
460 3. Usual arithmetic conversions.
461
462 Integral promotion: if an operand is of a type with less than 32 bits,
463 (including bool), it is promoted to int32_t.
464
465 Usual arithmetic conversions:
466 1. If operands are both signed or both unsigned, lesser conversion rank is
467 converted to greater conversion rank.
468 2. Otherwise, if unsigned's rank >= signed's rank, -> unsigned's type
469 3. Otherwise, if signed's type can hold all values in unsigned's type,
470 -> signed's type
471 4. Otherwise, both converted to the unsigned counterpart of the signed operand's
472 type.
473 rank: bool < int8_t < int16_t < int32_t < int64_t
474
475
476 Shift operators (<< >>):
477 1. Integral promotion is applied on both sides.
478 2. For unsigned a, a << b discards bits that shifts out.
479 For signed non-negative a, a << b is legal if no bits shifts out, otherwise error.
480 For signed negative a, a << b gives error.
481 3. For unsigned and signed non-negative a, a >> b discards bits that shifts out.
482 For signed negative a, a >> b discards bits that shifts out, and the signed
483 bit gets extended. ("arithmetic right shift")
484 4. Shifting with negative number of bits is undefined. (Currently, the
485 parser will shift into the other direction. This behavior may change.)
486 5. Shifting with number of bits exceeding the width of the type is undefined.
487 (Currently, 1 << 32 == 1. This behavior may change.)
488
489 Logical operators (!, &&, ||):
490 1. Convert first operand to bool. (true if non-zero, false otherwise)
491 2. If short-circuited, return the result as type bool, value 1 or 0.
492 3. Otherwise, convert second operand to bool, evaluate the result, and return
493 the result in the same fashion.
494
495 Arithmetic comparison operators (< > <= >= == !=):
496 1. Promote operands in the same way as binary arithmetic and bitwise operators.
497 (Integral promotion + Usual arithmetic conversions)
498 2. Return type bool, value 0 or 1 the same way as logical operators.
499
500 Ternary conditional operator (?:):
501 1. Evaluate the conditional and evaluate the operands.
502 2. Return type of expression is the type under usual arithmetic conversions on
503 the second and third operand. (No integral promotions necessary.)
504
505 */
506
507 } // namespace android
508
509