• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 <android-base/logging.h>
20 #include <android-base/parseint.h>
21 #include <stdio.h>
22 #include <algorithm>
23 #include <iostream>
24 #include <sstream>
25 #include <string>
26 
27 #include "EnumType.h"
28 #include "Scope.h"  // LocalIdentifier
29 
30 // The macros are really nasty here. Consider removing
31 // as many macros as possible.
32 
33 #define OPEQ(__y__) (std::string(mOp) == std::string(__y__))
34 #define COMPUTE_UNARY(__op__)  if (op == std::string(#__op__)) return __op__ val;
35 #define COMPUTE_BINARY(__op__) if (op == std::string(#__op__)) return lval __op__ rval;
36 #define OP_IS_BIN_ARITHMETIC  (OPEQ("+") || OPEQ("-") || OPEQ("*") || OPEQ("/") || OPEQ("%"))
37 #define OP_IS_BIN_BITFLIP     (OPEQ("|") || OPEQ("^") || OPEQ("&"))
38 #define OP_IS_BIN_COMP        (OPEQ("<") || OPEQ(">") || OPEQ("<=") || OPEQ(">=") || OPEQ("==") || OPEQ("!="))
39 #define OP_IS_BIN_SHIFT       (OPEQ(">>") || OPEQ("<<"))
40 #define OP_IS_BIN_LOGICAL     (OPEQ("||") || OPEQ("&&"))
41 #define SK(__x__) ScalarType::Kind::KIND_##__x__
42 #define SHOULD_NOT_REACH() CHECK(false) << __LINE__ << ": should not reach here: "
43 
44 // NOLINT to suppress missing parentheses warnings about __def__.
45 #define SWITCH_KIND(__cond__, __action__, __def__)           \
46         switch(__cond__) {                                        \
47             case SK(BOOL): __action__(bool)                         \
48             case SK(UINT8): __action__(uint8_t)                     \
49             case SK(INT8): __action__(int8_t)                       \
50             case SK(UINT16): __action__(uint16_t)                   \
51             case SK(INT16): __action__(int16_t)                     \
52             case SK(UINT32): __action__(uint32_t)                   \
53             case SK(INT32): __action__(int32_t)                     \
54             case SK(UINT64): __action__(uint64_t)                   \
55             case SK(INT64): __action__(int64_t)                     \
56             default: __def__                        /* NOLINT */    \
57         }
58 
59 namespace android {
60 
isSupported(ScalarType::Kind kind)61 static inline bool isSupported(ScalarType::Kind kind) {
62     return SK(BOOL) == kind || ScalarType(kind, nullptr /* parent */).isValidEnumStorageType();
63 }
64 
65 /* See docs at the end for details on integral promotion. */
integralPromotion(ScalarType::Kind in)66 ScalarType::Kind integralPromotion(ScalarType::Kind in) {
67     return SK(INT32) < in ? in : SK(INT32); // note that KIND_INT32 < KIND_UINT32
68 }
69 
70 /* See docs at the end for details on usual arithmetic conversion. */
usualArithmeticConversion(ScalarType::Kind lft,ScalarType::Kind rgt)71 ScalarType::Kind usualArithmeticConversion(ScalarType::Kind lft,
72                                            ScalarType::Kind rgt) {
73     CHECK(isSupported(lft) && isSupported(rgt));
74     // Kinds in concern: bool, (u)int[8|16|32|64]
75     if(lft == rgt) return lft; // easy case
76     if(lft == SK(BOOL)) return rgt;
77     if(rgt == SK(BOOL)) return lft;
78     bool isLftSigned = (lft == SK(INT8))  || (lft == SK(INT16))
79                     || (lft == SK(INT32)) || (lft == SK(INT64));
80     bool isRgtSigned = (rgt == SK(INT8))  || (rgt == SK(INT16))
81                     || (rgt == SK(INT32)) || (rgt == SK(INT64));
82     if(isLftSigned == isRgtSigned) return lft < rgt ? rgt : lft;
83     ScalarType::Kind unsignedRank = isLftSigned ? rgt : lft;
84     ScalarType::Kind signedRank   = isLftSigned ? lft : rgt;
85     if(unsignedRank >= signedRank) return unsignedRank;
86     if(signedRank > unsignedRank)  return signedRank;
87 
88     // Although there is such rule to return "the unsigned counterpart of
89     // the signed operand", it should not reach here in our HIDL grammar.
90     CHECK(false) << "Could not do usual arithmetic conversion for type " << lft << "and" << rgt;
91     switch(signedRank) {
92         case SK(INT8):  return SK(UINT8);
93         case SK(INT16): return SK(UINT16);
94         case SK(INT32): return SK(UINT32);
95         case SK(INT64): return SK(UINT64);
96         default: return SK(UINT64);
97     }
98 }
99 
100 template <class T>
handleUnary(const std::string & op,T val)101 T handleUnary(const std::string& op, T val) {
102     COMPUTE_UNARY(+)
103     COMPUTE_UNARY(-)
104     COMPUTE_UNARY(!)
105     COMPUTE_UNARY(~)
106     // Should not reach here.
107     SHOULD_NOT_REACH() << "Could not handleUnary for " << op << " " << val;
108     return static_cast<T>(0xdeadbeef);
109 }
110 
111 template <class T>
handleBinaryCommon(T lval,const std::string & op,T rval)112 T handleBinaryCommon(T lval, const std::string& op, T rval) {
113     COMPUTE_BINARY(+)
114     COMPUTE_BINARY(-)
115     COMPUTE_BINARY(*)
116     COMPUTE_BINARY(/)
117     COMPUTE_BINARY(%)
118     COMPUTE_BINARY(|)
119     COMPUTE_BINARY(^)
120     COMPUTE_BINARY(&)
121     // comparison operators: return 0 or 1 by nature.
122     COMPUTE_BINARY(==)
123     COMPUTE_BINARY(!=)
124     COMPUTE_BINARY(<)
125     COMPUTE_BINARY(>)
126     COMPUTE_BINARY(<=)
127     COMPUTE_BINARY(>=)
128     // Should not reach here.
129     SHOULD_NOT_REACH() << "Could not handleBinaryCommon for "
130                        << lval << " " << op << " " << rval;
131     return static_cast<T>(0xdeadbeef);
132 }
133 
134 template <class T>
handleShift(T lval,const std::string & op,int64_t rval)135 T handleShift(T lval, const std::string& op, int64_t rval) {
136     // just cast rval to int64_t and it should fit.
137     COMPUTE_BINARY(>>)
138     COMPUTE_BINARY(<<)
139     // Should not reach here.
140     SHOULD_NOT_REACH() << "Could not handleShift for "
141                        << lval << " " << op << " " << rval;
142     return static_cast<T>(0xdeadbeef);
143 }
144 
handleLogical(bool lval,const std::string & op,bool rval)145 bool handleLogical(bool lval, const std::string& op, bool rval) {
146     COMPUTE_BINARY(||);
147     COMPUTE_BINARY(&&);
148     // Should not reach here.
149     SHOULD_NOT_REACH() << "Could not handleLogical for "
150                        << lval << " " << op << " " << rval;
151     return false;
152 }
153 
Zero(ScalarType::Kind kind)154 std::unique_ptr<ConstantExpression> ConstantExpression::Zero(ScalarType::Kind kind) {
155     return ValueOf(kind, 0);
156 }
157 
One(ScalarType::Kind kind)158 std::unique_ptr<ConstantExpression> ConstantExpression::One(ScalarType::Kind kind) {
159     return ValueOf(kind, 1);
160 }
161 
ValueOf(ScalarType::Kind kind,uint64_t value)162 std::unique_ptr<ConstantExpression> ConstantExpression::ValueOf(ScalarType::Kind kind,
163                                                                 uint64_t value) {
164     return std::make_unique<LiteralConstantExpression>(kind, value);
165 }
166 
isEvaluated() const167 bool ConstantExpression::isEvaluated() const {
168     return mIsEvaluated;
169 }
170 
LiteralConstantExpression(ScalarType::Kind kind,uint64_t value,const std::string & expr)171 LiteralConstantExpression::LiteralConstantExpression(
172     ScalarType::Kind kind, uint64_t value, const std::string& expr) {
173 
174     CHECK(!expr.empty());
175     CHECK(isSupported(kind));
176     mTrivialDescription = std::to_string(value) == expr;
177     mExpr = expr;
178     mValueKind = kind;
179     mValue = value;
180     mIsEvaluated = true;
181 }
182 
LiteralConstantExpression(ScalarType::Kind kind,uint64_t value)183 LiteralConstantExpression::LiteralConstantExpression(ScalarType::Kind kind, uint64_t value)
184   : LiteralConstantExpression(kind, value, std::to_string(value)) {}
185 
tryParse(const std::string & value)186 LiteralConstantExpression* LiteralConstantExpression::tryParse(const std::string& value) {
187     CHECK(!value.empty());
188 
189     bool isLong = false, isUnsigned = false;
190     bool isHex = (value[0] == '0' && value.length() > 1 && (value[1] == 'x' || value[1] == 'X'));
191 
192     auto rbegin = value.rbegin();
193     auto rend = value.rend();
194     for (; rbegin != rend && (*rbegin == 'u' || *rbegin == 'U' || *rbegin == 'l' || *rbegin == 'L');
195          ++rbegin) {
196         isUnsigned |= (*rbegin == 'u' || *rbegin == 'U');
197         isLong |= (*rbegin == 'l' || *rbegin == 'L');
198     }
199     std::string newVal(value.begin(), rbegin.base());
200     CHECK(!newVal.empty());
201 
202     uint64_t rawValue = 0;
203 
204     bool parseOK = base::ParseUint(newVal, &rawValue);
205     if (!parseOK) {
206         return nullptr;
207     }
208 
209     ScalarType::Kind kind;
210 
211     // guess literal type.
212     if(isLong) {
213         if(isUnsigned) // ul
214             kind = SK(UINT64);
215         else // l
216             kind = SK(INT64);
217     } else { // no l suffix
218         if(isUnsigned) { // u
219             if(rawValue <= UINT32_MAX)
220                 kind = SK(UINT32);
221             else
222                 kind = SK(UINT64);
223         } else { // no suffix
224             if(isHex) {
225                 if(rawValue <= INT32_MAX) // rawValue always >= 0
226                     kind = SK(INT32);
227                 else if(rawValue <= UINT32_MAX)
228                     kind = SK(UINT32);
229                 else if(rawValue <= INT64_MAX) // rawValue always >= 0
230                     kind = SK(INT64);
231                 else if(rawValue <= UINT64_MAX)
232                     kind = SK(UINT64);
233                 else
234                     return nullptr;
235             } else {
236                 if(rawValue <= INT32_MAX) // rawValue always >= 0
237                     kind = SK(INT32);
238                 else
239                     kind = SK(INT64);
240             }
241         }
242     }
243 
244     return new LiteralConstantExpression(kind, rawValue, value);
245 }
246 
evaluate()247 void LiteralConstantExpression::evaluate() {
248     // Evaluated in constructor
249     CHECK(isEvaluated());
250 }
251 
evaluate()252 void UnaryConstantExpression::evaluate() {
253     if (isEvaluated()) return;
254     CHECK(mUnary->isEvaluated());
255     mIsEvaluated = true;
256 
257     mExpr = std::string("(") + mOp + mUnary->mExpr + ")";
258     mValueKind = mUnary->mValueKind;
259 
260 #define CASE_UNARY(__type__)                                          \
261     mValue = handleUnary(mOp, static_cast<__type__>(mUnary->mValue)); \
262     return;
263 
264     SWITCH_KIND(mValueKind, CASE_UNARY, SHOULD_NOT_REACH(); return;)
265 }
266 
evaluate()267 void BinaryConstantExpression::evaluate() {
268     if (isEvaluated()) return;
269     CHECK(mLval->isEvaluated());
270     CHECK(mRval->isEvaluated());
271     mIsEvaluated = true;
272 
273     mExpr = std::string("(") + mLval->mExpr + " " + mOp + " " + mRval->mExpr + ")";
274 
275     bool isArithmeticOrBitflip = OP_IS_BIN_ARITHMETIC || OP_IS_BIN_BITFLIP;
276 
277     // CASE 1: + - *  / % | ^ & < > <= >= == !=
278     if(isArithmeticOrBitflip || OP_IS_BIN_COMP) {
279         // promoted kind for both operands.
280         ScalarType::Kind promoted = usualArithmeticConversion(integralPromotion(mLval->mValueKind),
281                                                               integralPromotion(mRval->mValueKind));
282         // result kind.
283         mValueKind = isArithmeticOrBitflip
284                     ? promoted // arithmetic or bitflip operators generates promoted type
285                     : SK(BOOL); // comparison operators generates bool
286 
287 #define CASE_BINARY_COMMON(__type__)                                       \
288     mValue = handleBinaryCommon(static_cast<__type__>(mLval->mValue), mOp, \
289                                 static_cast<__type__>(mRval->mValue));     \
290     return;
291 
292         SWITCH_KIND(promoted, CASE_BINARY_COMMON, SHOULD_NOT_REACH(); return;)
293     }
294 
295     // CASE 2: << >>
296     std::string newOp = mOp;
297     if(OP_IS_BIN_SHIFT) {
298         mValueKind = integralPromotion(mLval->mValueKind);
299         // instead of promoting rval, simply casting it to int64 should also be good.
300         int64_t numBits = mRval->cast<int64_t>();
301         if(numBits < 0) {
302             // shifting with negative number of bits is undefined in C. In HIDL it
303             // is defined as shifting into the other direction.
304             newOp = OPEQ("<<") ? std::string(">>") : std::string("<<");
305             numBits = -numBits;
306         }
307 
308 #define CASE_SHIFT(__type__)                                                    \
309     mValue = handleShift(static_cast<__type__>(mLval->mValue), newOp, numBits); \
310     return;
311 
312         SWITCH_KIND(mValueKind, CASE_SHIFT, SHOULD_NOT_REACH(); return;)
313     }
314 
315     // CASE 3: && ||
316     if(OP_IS_BIN_LOGICAL) {
317         mValueKind = SK(BOOL);
318         // easy; everything is bool.
319         mValue = handleLogical(mLval->mValue, mOp, mRval->mValue);
320         return;
321     }
322 
323     SHOULD_NOT_REACH();
324 }
325 
evaluate()326 void TernaryConstantExpression::evaluate() {
327     if (isEvaluated()) return;
328     CHECK(mCond->isEvaluated());
329     CHECK(mTrueVal->isEvaluated());
330     CHECK(mFalseVal->isEvaluated());
331     mIsEvaluated = true;
332 
333     mExpr = std::string("(") + mCond->mExpr + "?" + mTrueVal->mExpr + ":" + mFalseVal->mExpr + ")";
334 
335     // note: for ?:, unlike arithmetic ops, integral promotion is not processed.
336     mValueKind = usualArithmeticConversion(mTrueVal->mValueKind, mFalseVal->mValueKind);
337 
338 #define CASE_TERNARY(__type__)                                           \
339     mValue = mCond->mValue ? (static_cast<__type__>(mTrueVal->mValue))   \
340                            : (static_cast<__type__>(mFalseVal->mValue)); \
341     return;
342 
343     SWITCH_KIND(mValueKind, CASE_TERNARY, SHOULD_NOT_REACH(); return;)
344 }
345 
evaluate()346 void ReferenceConstantExpression::evaluate() {
347     if (isEvaluated()) return;
348     CHECK(mReference->constExpr() != nullptr);
349 
350     ConstantExpression* expr = mReference->constExpr();
351     CHECK(expr->isEvaluated());
352 
353     mValueKind = expr->mValueKind;
354     mValue = expr->mValue;
355     mIsEvaluated = true;
356 }
357 
validate() const358 status_t AttributeConstantExpression::validate() const {
359     if (mTag == "len") {
360         if (!mReference->isEnum()) {
361             std::cerr << "ERROR: " << mExpr << " refers to " << mReference->typeName()
362                       << " but should refer to an enum." << std::endl;
363             return UNKNOWN_ERROR;
364         }
365     } else {
366         std::cerr << "ERROR: " << mExpr << " is not a supported tag" << std::endl;
367         return UNKNOWN_ERROR;
368     }
369 
370     return OK;
371 }
372 
evaluate()373 void AttributeConstantExpression::evaluate() {
374     if (isEvaluated()) return;
375 
376     CHECK(mTag == "len");
377     CHECK(mReference->isEnum());
378 
379     EnumType* enumType = static_cast<EnumType*>(mReference.get());
380     mValue = enumType->numValueNames();
381 
382     if (mValue <= INT32_MAX)
383         mValueKind = SK(INT32);
384     else
385         mValueKind = SK(INT64);
386 
387     mIsEvaluated = true;
388 }
389 
addOne(ScalarType::Kind baseKind)390 std::unique_ptr<ConstantExpression> ConstantExpression::addOne(ScalarType::Kind baseKind) {
391     auto ret = std::make_unique<BinaryConstantExpression>(
392         this, "+", ConstantExpression::One(baseKind).release());
393     return ret;
394 }
395 
value() const396 std::string ConstantExpression::value() const {
397     return value(mValueKind);
398 }
399 
value(ScalarType::Kind castKind) const400 std::string ConstantExpression::value(ScalarType::Kind castKind) const {
401     CHECK(isEvaluated());
402     return rawValue(castKind) + descriptionSuffix();
403 }
404 
cppValue() const405 std::string ConstantExpression::cppValue() const {
406     return cppValue(mValueKind);
407 }
408 
cppValue(ScalarType::Kind castKind) const409 std::string ConstantExpression::cppValue(ScalarType::Kind castKind) const {
410     CHECK(isEvaluated());
411     std::string literal(rawValue(castKind));
412     // this is a hack to translate
413     //       enum x : int64_t {  y = 1l << 63 };
414     // into
415     //       enum class x : int64_t { y = (int64_t)-9223372036854775808ull };
416     // by adding the explicit cast.
417     // Because 9223372036854775808 is uint64_t, and
418     // -(uint64_t)9223372036854775808 == 9223372036854775808 could not
419     // be narrowed to int64_t.
420     if(castKind == SK(INT64) && (int64_t)mValue == INT64_MIN) {
421         literal = "static_cast<" +
422                   ScalarType(SK(INT64), nullptr /* parent */).getCppStackType()  // "int64_t"
423                   + ">(" + literal + "ull)";
424     } else {
425         // add suffix if necessary.
426         if (castKind == SK(UINT32) || castKind == SK(UINT64)) literal += "u";
427         if (castKind == SK(UINT64) || castKind == SK(INT64)) literal += "ll";
428     }
429 
430     return literal + descriptionSuffix();
431 }
432 
javaValue() const433 std::string ConstantExpression::javaValue() const {
434     return javaValue(mValueKind);
435 }
436 
javaValue(ScalarType::Kind castKind) const437 std::string ConstantExpression::javaValue(ScalarType::Kind castKind) const {
438     CHECK(isEvaluated());
439     std::string literal;
440 
441     switch(castKind) {
442         case SK(UINT64):
443             literal = rawValue(SK(INT64)) + "L";
444             break;
445         case SK(INT64):
446             literal = rawValue(SK(INT64)) + "L";
447             break;
448         case SK(UINT32):
449             literal = rawValue(SK(INT32));
450             break;
451         case SK(UINT16):
452             literal = rawValue(SK(INT16));
453             break;
454         case SK(UINT8):
455             literal = rawValue(SK(INT8));
456             break;
457         case SK(BOOL)  :
458             literal = this->cast<bool>() ? "true" : "false";
459             break;
460         default:
461             literal = rawValue(castKind);
462             break;
463     }
464 
465     return literal + descriptionSuffix();
466 }
467 
expression() const468 const std::string& ConstantExpression::expression() const {
469     CHECK(isEvaluated());
470     return mExpr;
471 }
472 
rawValue() const473 std::string ConstantExpression::rawValue() const {
474     return rawValue(mValueKind);
475 }
476 
rawValue(ScalarType::Kind castKind) const477 std::string ConstantExpression::rawValue(ScalarType::Kind castKind) const {
478     CHECK(isEvaluated());
479 
480 #define CASE_STR(__type__) return std::to_string(this->cast<__type__>());
481 
482     SWITCH_KIND(castKind, CASE_STR, SHOULD_NOT_REACH(); return nullptr; );
483 }
484 
485 template<typename T>
cast() const486 T ConstantExpression::cast() const {
487     CHECK(isEvaluated());
488 
489 #define CASE_CAST_T(__type__) return static_cast<T>(static_cast<__type__>(mValue));
490 
491     SWITCH_KIND(mValueKind, CASE_CAST_T, SHOULD_NOT_REACH(); return 0; );
492 }
493 
descriptionSuffix() const494 std::string ConstantExpression::descriptionSuffix() const {
495     CHECK(isEvaluated());
496 
497     if (!mTrivialDescription) {
498         CHECK(!mExpr.empty());
499 
500         return " /* " + mExpr + " */";
501     }
502     return "";
503 }
504 
castSizeT() const505 size_t ConstantExpression::castSizeT() const {
506     CHECK(isEvaluated());
507     return this->cast<size_t>();
508 }
509 
isReferenceConstantExpression() const510 bool ConstantExpression::isReferenceConstantExpression() const {
511     return false;
512 }
513 
validate() const514 status_t ConstantExpression::validate() const {
515     return OK;
516 }
517 
getConstantExpressions()518 std::vector<ConstantExpression*> ConstantExpression::getConstantExpressions() {
519     const auto& constRet = static_cast<const ConstantExpression*>(this)->getConstantExpressions();
520     std::vector<ConstantExpression*> ret(constRet.size());
521     std::transform(constRet.begin(), constRet.end(), ret.begin(),
522                    [](const auto* ce) { return const_cast<ConstantExpression*>(ce); });
523     return ret;
524 }
525 
getReferences()526 std::vector<Reference<LocalIdentifier>*> ConstantExpression::getReferences() {
527     const auto& constRet = static_cast<const ConstantExpression*>(this)->getReferences();
528     std::vector<Reference<LocalIdentifier>*> ret(constRet.size());
529     std::transform(constRet.begin(), constRet.end(), ret.begin(),
530                    [](const auto* ce) { return const_cast<Reference<LocalIdentifier>*>(ce); });
531     return ret;
532 }
533 
getReferences() const534 std::vector<const Reference<LocalIdentifier>*> ConstantExpression::getReferences() const {
535     return {};
536 }
537 
getTypeReferences()538 std::vector<Reference<Type>*> ConstantExpression::getTypeReferences() {
539     const auto& constRet = static_cast<const ConstantExpression*>(this)->getTypeReferences();
540     std::vector<Reference<Type>*> ret(constRet.size());
541     std::transform(constRet.begin(), constRet.end(), ret.begin(),
542                    [](const auto* ce) { return const_cast<Reference<Type>*>(ce); });
543     return ret;
544 }
545 
getTypeReferences() const546 std::vector<const Reference<Type>*> ConstantExpression::getTypeReferences() const {
547     return {};
548 }
549 
recursivePass(const std::function<status_t (ConstantExpression *)> & func,std::unordered_set<const ConstantExpression * > * visited,bool processBeforeDependencies)550 status_t ConstantExpression::recursivePass(const std::function<status_t(ConstantExpression*)>& func,
551                                            std::unordered_set<const ConstantExpression*>* visited,
552                                            bool processBeforeDependencies) {
553     if (mIsPostParseCompleted) return OK;
554 
555     if (visited->find(this) != visited->end()) return OK;
556     visited->insert(this);
557 
558     if (processBeforeDependencies) {
559         status_t err = func(this);
560         if (err != OK) return err;
561     }
562 
563     for (auto* nextCE : getConstantExpressions()) {
564         status_t err = nextCE->recursivePass(func, visited, processBeforeDependencies);
565         if (err != OK) return err;
566     }
567 
568     for (auto* nextRef : getReferences()) {
569         auto* nextCE = nextRef->shallowGet()->constExpr();
570         CHECK(nextCE != nullptr) << "Local identifier is not a constant expression";
571         status_t err = nextCE->recursivePass(func, visited, processBeforeDependencies);
572         if (err != OK) return err;
573     }
574 
575     if (!processBeforeDependencies) {
576         status_t err = func(this);
577         if (err != OK) return err;
578     }
579 
580     return OK;
581 }
582 
recursivePass(const std::function<status_t (const ConstantExpression *)> & func,std::unordered_set<const ConstantExpression * > * visited,bool processBeforeDependencies) const583 status_t ConstantExpression::recursivePass(
584     const std::function<status_t(const ConstantExpression*)>& func,
585     std::unordered_set<const ConstantExpression*>* visited, bool processBeforeDependencies) const {
586     if (mIsPostParseCompleted) return OK;
587 
588     if (visited->find(this) != visited->end()) return OK;
589     visited->insert(this);
590 
591     if (processBeforeDependencies) {
592         status_t err = func(this);
593         if (err != OK) return err;
594     }
595 
596     for (const auto* nextCE : getConstantExpressions()) {
597         status_t err = nextCE->recursivePass(func, visited, processBeforeDependencies);
598         if (err != OK) return err;
599     }
600 
601     for (const auto* nextRef : getReferences()) {
602         const auto* nextCE = nextRef->shallowGet()->constExpr();
603         CHECK(nextCE != nullptr) << "Local identifier is not a constant expression";
604         status_t err = nextCE->recursivePass(func, visited, processBeforeDependencies);
605         if (err != OK) return err;
606     }
607 
608     if (!processBeforeDependencies) {
609         status_t err = func(this);
610         if (err != OK) return err;
611     }
612 
613     return OK;
614 }
615 
CheckAcyclicStatus(status_t status,const ConstantExpression * cycleEnd,const ReferenceConstantExpression * lastReference)616 ConstantExpression::CheckAcyclicStatus::CheckAcyclicStatus(
617     status_t status, const ConstantExpression* cycleEnd,
618     const ReferenceConstantExpression* lastReference)
619     : status(status), cycleEnd(cycleEnd), lastReference(lastReference) {
620     CHECK(cycleEnd == nullptr || status != OK);
621     CHECK((cycleEnd == nullptr) == (lastReference == nullptr));
622 }
623 
checkAcyclic(std::unordered_set<const ConstantExpression * > * visited,std::unordered_set<const ConstantExpression * > * stack) const624 ConstantExpression::CheckAcyclicStatus ConstantExpression::checkAcyclic(
625     std::unordered_set<const ConstantExpression*>* visited,
626     std::unordered_set<const ConstantExpression*>* stack) const {
627     if (stack->find(this) != stack->end()) {
628         CHECK(isReferenceConstantExpression())
629             << "Only reference constant expression could be the cycle end";
630 
631         std::cerr << "ERROR: Cyclic declaration:\n";
632         return CheckAcyclicStatus(UNKNOWN_ERROR, this,
633                                   static_cast<const ReferenceConstantExpression*>(this));
634     }
635 
636     if (visited->find(this) != visited->end()) return CheckAcyclicStatus(OK);
637     visited->insert(this);
638     stack->insert(this);
639 
640     for (const auto* nextCE : getConstantExpressions()) {
641         auto err = nextCE->checkAcyclic(visited, stack);
642         if (err.status != OK) {
643             return err;
644         }
645     }
646 
647     for (const auto* nextRef : getReferences()) {
648         const auto* nextCE = nextRef->shallowGet()->constExpr();
649         CHECK(nextCE != nullptr) << "Local identifier is not a constant expression";
650         auto err = nextCE->checkAcyclic(visited, stack);
651 
652         if (err.status != OK) {
653             if (err.cycleEnd == nullptr) return err;
654 
655             // Only ReferenceConstantExpression has references,
656             CHECK(isReferenceConstantExpression())
657                 << "Only reference constant expression could have refereneces";
658 
659             // mExpr is defined explicitly before evaluation
660             std::cerr << "  '" << err.lastReference->mExpr << "' in '" << mExpr << "' at "
661                       << nextRef->location() << "\n";
662 
663             if (err.cycleEnd == this) {
664                 return CheckAcyclicStatus(err.status);
665             }
666             return CheckAcyclicStatus(err.status, err.cycleEnd,
667                                       static_cast<const ReferenceConstantExpression*>(this));
668         }
669     }
670 
671     CHECK(stack->find(this) != stack->end());
672     stack->erase(this);
673     return CheckAcyclicStatus(OK);
674 }
675 
setPostParseCompleted()676 void ConstantExpression::setPostParseCompleted() {
677     CHECK(!mIsPostParseCompleted);
678     mIsPostParseCompleted = true;
679 }
680 
getConstantExpressions() const681 std::vector<const ConstantExpression*> LiteralConstantExpression::getConstantExpressions() const {
682     return {};
683 }
684 
UnaryConstantExpression(const std::string & op,ConstantExpression * value)685 UnaryConstantExpression::UnaryConstantExpression(const std::string& op, ConstantExpression* value)
686     : mUnary(value), mOp(op) {}
687 
getConstantExpressions() const688 std::vector<const ConstantExpression*> UnaryConstantExpression::getConstantExpressions() const {
689     return {mUnary};
690 }
691 
BinaryConstantExpression(ConstantExpression * lval,const std::string & op,ConstantExpression * rval)692 BinaryConstantExpression::BinaryConstantExpression(ConstantExpression* lval, const std::string& op,
693                                                    ConstantExpression* rval)
694     : mLval(lval), mRval(rval), mOp(op) {}
695 
getConstantExpressions() const696 std::vector<const ConstantExpression*> BinaryConstantExpression::getConstantExpressions() const {
697     return {mLval, mRval};
698 }
699 
TernaryConstantExpression(ConstantExpression * cond,ConstantExpression * trueVal,ConstantExpression * falseVal)700 TernaryConstantExpression::TernaryConstantExpression(ConstantExpression* cond,
701                                                      ConstantExpression* trueVal,
702                                                      ConstantExpression* falseVal)
703     : mCond(cond), mTrueVal(trueVal), mFalseVal(falseVal) {}
704 
getConstantExpressions() const705 std::vector<const ConstantExpression*> TernaryConstantExpression::getConstantExpressions() const {
706     return {mCond, mTrueVal, mFalseVal};
707 }
708 
ReferenceConstantExpression(const Reference<LocalIdentifier> & value,const std::string & expr)709 ReferenceConstantExpression::ReferenceConstantExpression(const Reference<LocalIdentifier>& value,
710                                                          const std::string& expr)
711     : mReference(value) {
712     mExpr = expr;
713     mTrivialDescription = mExpr.empty();
714 }
715 
isReferenceConstantExpression() const716 bool ReferenceConstantExpression::isReferenceConstantExpression() const {
717     return true;
718 }
719 
getConstantExpressions() const720 std::vector<const ConstantExpression*> ReferenceConstantExpression::getConstantExpressions() const {
721     // Returns reference instead
722     return {};
723 }
724 
getReferences() const725 std::vector<const Reference<LocalIdentifier>*> ReferenceConstantExpression::getReferences() const {
726     return {&mReference};
727 }
728 
AttributeConstantExpression(const Reference<Type> & value,const std::string & fqname,const std::string & tag)729 AttributeConstantExpression::AttributeConstantExpression(const Reference<Type>& value,
730                                                          const std::string& fqname,
731                                                          const std::string& tag)
732     : mReference(value), mTag(tag) {
733     mExpr = fqname + "#" + tag;
734 }
735 
getConstantExpressions() const736 std::vector<const ConstantExpression*> AttributeConstantExpression::getConstantExpressions() const {
737     // Returns reference instead
738     return {};
739 }
740 
getTypeReferences() const741 std::vector<const Reference<Type>*> AttributeConstantExpression::getTypeReferences() const {
742     return {&mReference};
743 }
744 
745 /*
746 
747 Evaluating expressions in HIDL language
748 
749 The following rules are mostly like that in:
750 http://en.cppreference.com/w/cpp/language/operator_arithmetic
751 http://en.cppreference.com/w/cpp/language/operator_logical
752 http://en.cppreference.com/w/cpp/language/operator_comparison
753 http://en.cppreference.com/w/cpp/language/operator_other
754 
755 The type of literal is the first type which the value
756 can fit from the list of types depending on the suffix and bases.
757 
758 suffix              decimal bases           hexadecimal bases
759 no suffix           int32_t                 int32_t
760                     int64_t                 uint32_t
761                                             int64_t
762                                             uint64_t
763 
764 u/U                 uint32_t                (same as left)
765                     uint64_t
766 
767 l/L                 int64_t                 int64_t
768 
769 ul/UL/uL/Ul         uint64_t                uint64_t
770 
771 
772 Note: There are no negative integer literals.
773       -1 is the unary minus applied to 1.
774 
775 Unary arithmetic and bitwise operators (~ + -):
776   don't change the type of the argument.
777   (so -1u = -(1u) has type uint32_t)
778 
779 Binary arithmetic and bitwise operators (except shifts) (+ - * / % & | ^):
780 1. Integral promotion is first applied on both sides.
781 2. If both operands have the same type, no promotion is necessary.
782 3. Usual arithmetic conversions.
783 
784 Integral promotion: if an operand is of a type with less than 32 bits,
785 (including bool), it is promoted to int32_t.
786 
787 Usual arithmetic conversions:
788 1. If operands are both signed or both unsigned, lesser conversion rank is
789    converted to greater conversion rank.
790 2. Otherwise, if unsigned's rank >= signed's rank, -> unsigned's type
791 3. Otherwise, if signed's type can hold all values in unsigned's type,
792    -> signed's type
793 4. Otherwise, both converted to the unsigned counterpart of the signed operand's
794    type.
795 rank: bool < int8_t < int16_t < int32_t < int64_t
796 
797 
798 Shift operators (<< >>):
799 1. Integral promotion is applied on both sides.
800 2. For unsigned a, a << b discards bits that shifts out.
801    For signed non-negative a, a << b is legal if no bits shifts out, otherwise error.
802    For signed negative a, a << b gives error.
803 3. For unsigned and signed non-negative a, a >> b discards bits that shifts out.
804    For signed negative a, a >> b discards bits that shifts out, and the signed
805    bit gets extended. ("arithmetic right shift")
806 4. Shifting with negative number of bits is undefined. (Currently, the
807    parser will shift into the other direction. This behavior may change.)
808 5. Shifting with number of bits exceeding the width of the type is undefined.
809    (Currently, 1 << 32 == 1. This behavior may change.)
810 
811 Logical operators (!, &&, ||):
812 1. Convert first operand to bool. (true if non-zero, false otherwise)
813 2. If short-circuited, return the result as type bool, value 1 or 0.
814 3. Otherwise, convert second operand to bool, evaluate the result, and return
815    the result in the same fashion.
816 
817 Arithmetic comparison operators (< > <= >= == !=):
818 1. Promote operands in the same way as binary arithmetic and bitwise operators.
819    (Integral promotion + Usual arithmetic conversions)
820 2. Return type bool, value 0 or 1 the same way as logical operators.
821 
822 Ternary conditional operator (?:):
823 1. Evaluate the conditional and evaluate the operands.
824 2. Return type of expression is the type under usual arithmetic conversions on
825    the second and third operand. (No integral promotions necessary.)
826 
827 */
828 
829 }  // namespace android
830 
831