hqlcppcase.cpp 38 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151
  1. /*##############################################################################
  2. HPCC SYSTEMS software Copyright (C) 2012 HPCC Systems.
  3. Licensed under the Apache License, Version 2.0 (the "License");
  4. you may not use this file except in compliance with the License.
  5. You may obtain a copy of the License at
  6. http://www.apache.org/licenses/LICENSE-2.0
  7. Unless required by applicable law or agreed to in writing, software
  8. distributed under the License is distributed on an "AS IS" BASIS,
  9. WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  10. See the License for the specific language governing permissions and
  11. limitations under the License.
  12. ############################################################################## */
  13. #include "jliball.hpp"
  14. #include "hql.hpp"
  15. #include "platform.h"
  16. #include "jlib.hpp"
  17. #include "jexcept.hpp"
  18. #include "jmisc.hpp"
  19. #include "hql.hpp"
  20. #include "hqlfunc.hpp"
  21. #include "hqlcpp.ipp"
  22. #include "hqlwcpp.hpp"
  23. #include "hqlutil.hpp"
  24. #include "hqlcpputil.hpp"
  25. #include "hqlcatom.hpp"
  26. #include "hqlcerrors.hpp"
  27. #define INTEGER_SEARCH_THRESHOLD 30 // above this, a table search is generated.
  28. #define MAX_NUM_NOBREAK_CASE 80 // maximum number of case: without a break - compiler workaround
  29. #define INLINE_COMPARE_THRESHOLD 2 // above this, a loop is generated
  30. #define SWITCH_TABLE_DENSITY_THRESHOLD 3 // % used before use array index.
  31. #define MAX_NESTED_CASES 8 // to stop C++ compiler running out of scopes.
  32. //===========================================================================
  33. static IIdAtom * searchDataTableAtom;
  34. static IIdAtom * searchEStringTableAtom;
  35. static IIdAtom * searchQStringTableAtom;
  36. static IIdAtom * searchStringTableAtom;
  37. static IIdAtom * searchVStringTableAtom;
  38. //===========================================================================
  39. MODULE_INIT(INIT_PRIORITY_STANDARD)
  40. {
  41. searchDataTableAtom = createIdentifierAtom("searchDataTable");
  42. searchEStringTableAtom = createIdentifierAtom("searchEStringTable");
  43. searchQStringTableAtom = createIdentifierAtom("searchQStringTable");
  44. searchStringTableAtom = createIdentifierAtom("searchStringTable");
  45. searchVStringTableAtom = createIdentifierAtom("searchVStringTable");
  46. return true;
  47. }
  48. MODULE_EXIT()
  49. {
  50. }
  51. //===========================================================================
  52. //Case helper functions...
  53. void cvtChooseListToPairs(HqlExprArray & target, IHqlExpression * from, unsigned base)
  54. {
  55. unsigned max = from->numChildren();
  56. unsigned idx;
  57. target.ensure(max);
  58. for (idx = 0; idx < max; idx++)
  59. {
  60. IHqlExpression * v1 = createConstant(createIntValue(idx+base, LINK(unsignedType)));
  61. IHqlExpression * v2 = from->queryChild(idx);
  62. ITypeInfo * type = v2->queryType();
  63. target.append(* createValue(no_mapto, LINK(type), v1, LINK(v2)));
  64. }
  65. }
  66. void cvtIndexListToPairs(HqlExprArray & target, IHqlExpression * from)
  67. {
  68. unsigned max = from->numChildren();
  69. unsigned idx;
  70. target.ensure(max);
  71. for (idx = 0; idx < max; idx++)
  72. {
  73. IHqlExpression * v1 = from->queryChild(idx);
  74. IHqlExpression * v2 = createConstant(createIntValue(idx+1, LINK(unsignedType)));
  75. ITypeInfo * type = v2->queryType();
  76. target.append(* createValue(no_mapto, LINK(type), LINK(v1), v2));
  77. }
  78. }
  79. void cvtInListToPairs(HqlExprArray & target, IHqlExpression * from, bool valueIfMatch)
  80. {
  81. unsigned max = from->numChildren();
  82. unsigned idx;
  83. IHqlExpression * tValue = queryBoolExpr(valueIfMatch);
  84. ITypeInfo * type = queryBoolType();
  85. target.ensure(max);
  86. for (idx = 0; idx < max; idx++)
  87. {
  88. IHqlExpression * v1 = from->queryChild(idx);
  89. target.append(* createValue(no_mapto, LINK(type), LINK(v1), LINK(tValue)));
  90. }
  91. }
  92. IHqlExpression * createNotFoundValue()
  93. {
  94. OwnedITypeInfo int4 = makeIntType(4, true);
  95. return createConstant(int4->castFrom(true, -1));
  96. }
  97. //===========================================================================
  98. static int comparePair(IInterface * * left, IInterface * * right)
  99. {
  100. IHqlExpression * lexpr = (IHqlExpression *)*left;
  101. IHqlExpression * rexpr = (IHqlExpression *)*right;
  102. return lexpr->queryChild(0)->queryValue()->compare(rexpr->queryChild(0)->queryValue());
  103. }
  104. HqlCppCaseInfo::HqlCppCaseInfo(HqlCppTranslator & _translator) : translator(_translator)
  105. {
  106. complexCompare = false;
  107. constantCases = true;
  108. constantValues = true;
  109. indexType.setown(makeIntType(sizeof(int), true));
  110. }
  111. void HqlCppCaseInfo::addPair(IHqlExpression * expr)
  112. {
  113. pairs.append(*LINK(expr));
  114. IHqlExpression * compareValue = expr->queryChild(0);
  115. if (!compareValue->queryValue())
  116. constantCases = false;
  117. if (!expr->queryChild(1)->queryValue())
  118. constantValues = false;
  119. if (cond && !complexCompare)
  120. {
  121. ITypeInfo * valueType = compareValue->queryType();
  122. if (valueType != cond->queryType())
  123. complexCompare = isCompare3Valued(compareValue->queryType());
  124. }
  125. updateResultType(expr->queryChild(1));
  126. }
  127. void HqlCppCaseInfo::addPairs(HqlExprArray & _pairs)
  128. {
  129. pairs.ensure(_pairs.ordinality());
  130. ForEachItemIn(idx, _pairs)
  131. addPair(&_pairs.item(idx));
  132. }
  133. bool HqlCppCaseInfo::buildAssign(BuildCtx & ctx, const CHqlBoundTarget & target)
  134. {
  135. if (pairs.ordinality() == 0)
  136. {
  137. translator.buildExprAssign(ctx, target, defaultValue);
  138. }
  139. else if (cond.get() && constantCases)
  140. {
  141. processBranches();
  142. BuildCtx subctx(ctx);
  143. CHqlBoundExpr test;
  144. buildSwitchCondition(ctx, test);
  145. if (complexCompare)
  146. {
  147. if ((pairs.ordinality() > INLINE_COMPARE_THRESHOLD) || (translator.getHints() & HintSize))
  148. {
  149. if (okToAlwaysEvaluateDefault() || hasLibraryChop())
  150. buildLoopChopMap(subctx, target, test);
  151. else
  152. buildGeneralAssign(subctx, target);
  153. }
  154. else
  155. {
  156. if (okToAlwaysEvaluateDefault())
  157. buildChop3Map(subctx, target, test);
  158. else
  159. buildGeneralAssign(subctx, target);
  160. }
  161. }
  162. else
  163. {
  164. ITypeInfo * condType = test.queryType()->queryPromotedType();
  165. if (!queryBuildArrayLookup(subctx, target, test))
  166. {
  167. if (condType->getTypeCode() != type_real)
  168. {
  169. OwnedHqlExpr search = test.getTranslatedExpr();
  170. if (constantValues && (condType->getTypeCode() == type_int) && (pairs.ordinality() > INTEGER_SEARCH_THRESHOLD) && canBuildStaticList(resultType))
  171. buildIntegerSearchMap(subctx, target, search);
  172. else
  173. buildSwitchMap(subctx, &target, test.expr);
  174. }
  175. else
  176. {
  177. if (okToAlwaysEvaluateDefault() && pairs.ordinality() > 4)
  178. {
  179. translator.buildExprAssign(ctx, target, defaultValue);
  180. buildChop2Map(subctx, target, test, 0, pairs.ordinality());
  181. }
  182. else
  183. buildGeneralAssign(subctx, target);
  184. }
  185. }
  186. }
  187. }
  188. else
  189. buildGeneralAssign(ctx, target);
  190. return true;
  191. }
  192. bool HqlCppCaseInfo::buildReturn(BuildCtx & ctx)
  193. {
  194. if (pairs.ordinality() == 0)
  195. {
  196. translator.buildReturn(ctx, defaultValue);
  197. }
  198. else if (cond.get() && constantCases)
  199. {
  200. processBranches();
  201. BuildCtx subctx(ctx);
  202. CHqlBoundExpr test;
  203. buildSwitchCondition(ctx, test);
  204. if (complexCompare)
  205. {
  206. buildGeneralReturn(subctx);
  207. }
  208. else
  209. {
  210. //if canBuildArrayLookup(test)
  211. //if use a lookup table to map value->constants
  212. if (test.queryType()->getTypeCode() != type_real)
  213. buildSwitchMap(subctx, NULL, test.expr);
  214. else
  215. buildGeneralReturn(subctx);
  216. }
  217. }
  218. else
  219. buildGeneralReturn(ctx);
  220. return true;
  221. }
  222. void HqlCppCaseInfo::buildChop3Map(BuildCtx & ctx, const CHqlBoundTarget & target, CHqlBoundExpr & test, IHqlExpression * temp, unsigned start, unsigned end)
  223. {
  224. if ((end - start) <= 2)
  225. buildChop2Map(ctx, target, test, start, end);
  226. else
  227. {
  228. unsigned mid = (start + end) / 2;
  229. generateCompareVar(ctx, temp, test, queryCompare(mid));
  230. OwnedHqlExpr test1 = createValue(no_eq, LINK(temp), getZero());
  231. OwnedHqlExpr test2 = createValue(no_lt, LINK(temp), getZero());
  232. BuildCtx subctx(ctx);
  233. IHqlStmt * if1 = subctx.addFilter(test1); // if (test == 0)
  234. translator.buildExprAssign(subctx, target, queryReturn(mid)); // target = value(n)
  235. subctx.selectElse(if1); // else
  236. IHqlStmt * if2 = subctx.addFilter(test2); // if (test < 0)
  237. buildChop3Map(subctx, target, test, temp, start, mid); // repeat for start..mid
  238. subctx.selectElse(if2); // else
  239. buildChop3Map(subctx, target, test, temp, mid+1, end); // repeat for min..end
  240. }
  241. }
  242. void HqlCppCaseInfo::buildChop3Map(BuildCtx & ctx, const CHqlBoundTarget & target, CHqlBoundExpr & test)
  243. {
  244. translator.buildExprAssign(ctx, target, defaultValue);
  245. if (getNumPairs() <= 2)
  246. {
  247. buildChop2Map(ctx, target, test, 0, getNumPairs());
  248. }
  249. else
  250. {
  251. //need to hack it because there is no signed integer type
  252. OwnedHqlExpr tempVar = ctx.getTempDeclare(indexType, NULL);
  253. buildChop3Map(ctx, target, test, tempVar, 0, getNumPairs());
  254. }
  255. }
  256. void HqlCppCaseInfo::buildChop2Map(BuildCtx & ctx, const CHqlBoundTarget & target, CHqlBoundExpr & test, unsigned start, unsigned end)
  257. {
  258. BuildCtx subctx(ctx);
  259. if ((end - start) <= 3) // (1,2,3) avg(2) cf. (2,2,3) avg(2.3)
  260. {
  261. //optimize the case where they all create the same value
  262. bool same = true;
  263. unsigned index;
  264. for (index=start+1; index < end; ++index)
  265. {
  266. if (queryReturn(index-1) != queryReturn(index))
  267. {
  268. same = false;
  269. break;
  270. }
  271. }
  272. if (same)
  273. {
  274. CompoundBuilder cb(no_or);
  275. for (index=start; index < end; ++index)
  276. {
  277. IHqlExpression * compare = queryCompare(index);
  278. IHqlExpression * cond = createCompareExpr(no_eq, test.getTranslatedExpr(), LINK(compare));
  279. cb.addOperand(cond);
  280. }
  281. OwnedHqlExpr compound = cb.getCompound();
  282. translator.buildFilter(subctx, compound);
  283. translator.buildExprAssign(subctx, target, queryReturn(start));
  284. }
  285. else
  286. {
  287. IHqlStmt * stmt = NULL;
  288. for (index=start; index < end; ++index)
  289. {
  290. if (stmt)
  291. subctx.selectElse(stmt);
  292. IHqlExpression * compare = queryCompare(index);
  293. OwnedHqlExpr cond = createCompareExpr(no_eq, test.getTranslatedExpr(), LINK(compare));
  294. CHqlBoundExpr bound;
  295. translator.buildExpr(subctx, cond, bound);
  296. stmt = subctx.addFilter(bound.expr);
  297. translator.buildExprAssign(subctx, target, queryReturn(index));
  298. }
  299. }
  300. }
  301. else
  302. {
  303. unsigned mid = (start + end) / 2;
  304. IHqlExpression * compare = queryCompare(mid);
  305. OwnedHqlExpr cond = createCompareExpr(no_lt, test.getTranslatedExpr(), LINK(compare));
  306. CHqlBoundExpr bound;
  307. translator.buildExpr(subctx, cond, bound);
  308. IHqlStmt * stmt = subctx.addFilter(bound.expr);
  309. buildChop2Map(subctx, target, test, start, mid);
  310. subctx.selectElse(stmt);
  311. buildChop2Map(subctx, target, test, mid, end);
  312. }
  313. }
  314. IHqlExpression * HqlCppCaseInfo::buildIndexedMap(BuildCtx & ctx, IHqlExpression * test, unsigned lower, unsigned upper)
  315. {
  316. ITypeInfo * compareType = test->queryType()->queryPromotedType();
  317. type_t compareTypeCode = compareType->getTypeCode();
  318. HqlExprArray values;
  319. IHqlExpression * dft = queryActiveTableSelector(); // value doesn't matter as long as it will not occur
  320. unsigned num = (upper-lower+1);
  321. values.ensure(num);
  322. unsigned idx;
  323. for (idx = 0; idx < num; idx++)
  324. values.append(*LINK(dft));
  325. ForEachItemIn(idx2, pairs)
  326. {
  327. IHqlExpression & cur = pairs.item(idx2);
  328. IValue * value = cur.queryChild(0)->queryValue();
  329. unsigned replaceIndex;
  330. switch (compareTypeCode)
  331. {
  332. case type_int:
  333. replaceIndex = (int)value->getIntValue()-lower;
  334. break;
  335. case type_string:
  336. {
  337. StringBuffer temp;
  338. value->getStringValue(temp);
  339. replaceIndex = (int)(unsigned char)temp.charAt(0)-lower;
  340. break;
  341. }
  342. default:
  343. throwUnexpectedType(compareType);
  344. }
  345. IHqlExpression * mapTo = cur.queryChild(1);
  346. if (mapTo->getOperator() != no_constant)
  347. throwUnexpected();
  348. if (replaceIndex >= num)
  349. translator.reportWarning(HQLWRN_CaseCanNeverMatch, "CASE entry %d can never match the test condition", replaceIndex);
  350. else
  351. values.replace(*LINK(mapTo),replaceIndex);
  352. }
  353. //Now replace the placeholders with the default values.
  354. for (idx = 0; idx < num; idx++)
  355. {
  356. if (&values.item(idx) == dft)
  357. values.replace(*defaultValue.getLink(),idx);
  358. }
  359. // use a var string type to get better C++ generated...
  360. ITypeInfo * storeType = getArrayElementType(resultType);
  361. ITypeInfo * listType = makeArrayType(storeType, values.ordinality());
  362. OwnedHqlExpr lvalues = createValue(no_list, listType, values);
  363. CHqlBoundExpr boundTable;
  364. translator.buildExpr(ctx, lvalues, boundTable);
  365. IHqlExpression * tableIndex;
  366. switch (compareTypeCode)
  367. {
  368. case type_int:
  369. tableIndex = LINK(test);
  370. break;
  371. case type_string:
  372. tableIndex = createValue(no_index, makeCharType(), LINK(test), getZero());
  373. break;
  374. default:
  375. throwUnexpectedType(compareType);
  376. }
  377. ITypeInfo * retType = resultType;
  378. IHqlExpression * ret = createValue(no_index, LINK(retType), LINK(boundTable.expr), tableIndex);
  379. return createTranslatedOwned(ret);
  380. }
  381. void HqlCppCaseInfo::buildLoopChopMap(BuildCtx & ctx, const CHqlBoundTarget & target, CHqlBoundExpr & test)
  382. {
  383. //Declare a table that contains all the strings...
  384. ITypeInfo * compareType = queryCompareType();
  385. type_t ctc = compareType->getTypeCode();
  386. if ((ctc == type_data) && !hasLibraryChop())
  387. {
  388. buildGeneralAssign(ctx, target);
  389. return;
  390. }
  391. OwnedHqlExpr values = createCompareList();
  392. CHqlBoundExpr boundTable;
  393. translator.buildExpr(ctx, values, boundTable);
  394. OwnedHqlExpr midVar = createVariable(LINK(indexType));
  395. if (hasLibraryChop())
  396. {
  397. ITypeInfo * tableEntryType = makeReferenceModifier(LINK(compareType));
  398. ITypeInfo * tableType = makePointerType(tableEntryType);
  399. HqlExprArray args;
  400. IIdAtom * func;
  401. switch (ctc)
  402. {
  403. case type_data:
  404. func = searchDataTableAtom;
  405. break;
  406. case type_varstring:
  407. func = searchVStringTableAtom;
  408. break;
  409. case type_qstring:
  410. func = searchQStringTableAtom;
  411. break;
  412. case type_string:
  413. if (compareType->queryCharset()->queryName() == asciiAtom)
  414. func = searchStringTableAtom;
  415. else if (compareType->queryCharset()->queryName() == ebcdicAtom)
  416. func = searchEStringTableAtom;
  417. else
  418. UNIMPLEMENTED;
  419. break;
  420. case type_unicode:
  421. func = searchUnicodeTableId;
  422. break;
  423. case type_utf8:
  424. func = searchUtf8TableId;
  425. break;
  426. case type_varunicode:
  427. func = searchVUnicodeTableId;
  428. break;
  429. default:
  430. throwUnexpectedType(compareType);
  431. }
  432. args.append(*getSizetConstant(values->numChildren()));
  433. if ((ctc != type_varstring) && (ctc != type_varunicode))
  434. args.append(*getSizetConstant(values->queryChild(0)->queryType()->getStringLen()));
  435. args.append(*createValue(no_address, tableType, createValue(no_index, LINK(tableEntryType), LINK(boundTable.expr), getZero())));
  436. if ((ctc != type_varstring) && (ctc != type_varunicode))
  437. args.append(*translator.getBoundLength(test));
  438. args.append(*ensureIndexable(test.expr));
  439. if ((ctc==type_unicode) || (ctc == type_varunicode) || (ctc == type_utf8))
  440. args.append(*createConstant(compareType->queryLocale()->str()));
  441. OwnedHqlExpr call = translator.bindTranslatedFunctionCall(func, args);
  442. OwnedHqlExpr search = createTranslated(call);
  443. bool includeDefaultInResult = false;
  444. OwnedHqlExpr resultExpr = createResultsExpr(midVar, true, &includeDefaultInResult);
  445. OwnedHqlExpr simpleResult = queryCreateSimpleResultAssign(search, resultExpr);
  446. if (simpleResult)
  447. translator.buildExprAssign(ctx, target, simpleResult);
  448. else
  449. {
  450. ctx.addDeclare(midVar, NULL);
  451. translator.buildAssignToTemp(ctx, midVar, search);
  452. if (includeDefaultInResult)
  453. {
  454. translator.buildExprAssign(ctx, target, resultExpr);
  455. }
  456. else
  457. {
  458. OwnedHqlExpr compare = createBoolExpr(no_ne, LINK(midVar), createNotFoundValue());
  459. BuildCtx subctx(ctx);
  460. IHqlStmt * stmt = subctx.addFilter(compare);
  461. translator.buildExprAssign(subctx, target, resultExpr);
  462. subctx.selectElse(stmt);
  463. translator.buildExprAssign(subctx, target, defaultValue);
  464. }
  465. }
  466. }
  467. else
  468. {
  469. #if 0
  470. //Keep this as a reminder of what was needed to fix qstrings.
  471. if (ctc == type_qstring)
  472. {
  473. Linked<ITypeInfo> compareType = queryCompareType();
  474. compareType.setown(makeArrayType(compareType.getLink()));
  475. table = createValue(no_typetransfer, compareType.getLink(), table);
  476. }
  477. #endif
  478. OwnedHqlExpr resultExpr = createResultsExpr(midVar, false);
  479. //Now generate the code that performs the binary chop..
  480. ctx.addDeclare(midVar, NULL);
  481. OwnedHqlExpr compareVar = ctx.getTempDeclare(indexType, NULL);
  482. OwnedHqlExpr leftVar = ctx.getTempDeclare(indexType, NULL);
  483. OwnedHqlExpr rightVar = ctx.getTempDeclare(indexType, NULL);
  484. OwnedHqlExpr numPairs = getSizetConstant(getNumPairs());
  485. ctx.addAssign(leftVar, queryZero());
  486. ctx.addAssign(rightVar, numPairs);
  487. translator.buildExprAssign(ctx, target, defaultValue);
  488. OwnedHqlExpr loopc = createBoolExpr(no_lt, LINK(leftVar), LINK(rightVar));
  489. OwnedHqlExpr mid = createValue(no_div, createValue(no_add, LINK(leftVar), LINK(rightVar)), createConstant(indexType->castFrom(false, 2)));
  490. OwnedHqlExpr mid_p1 = createValue(no_add, LINK(indexType), LINK(midVar), createConstant(indexType->castFrom(false, 1)));
  491. OwnedHqlExpr curelem = createValue(no_index, LINK(compareType), boundTable.getTranslatedExpr(), createTranslated(mid_p1));
  492. OwnedHqlExpr test1 = createBoolExpr(no_lt, LINK(compareVar), getZero());
  493. OwnedHqlExpr test2 = createBoolExpr(no_gt, LINK(compareVar), getZero());
  494. OwnedHqlExpr order = createValue(no_order, LINK(indexType), test.getTranslatedExpr(), LINK(curelem));
  495. BuildCtx loopctx(ctx);
  496. loopctx.addLoop(loopc, NULL, true);
  497. translator.buildAssignToTemp(loopctx, midVar, mid);
  498. translator.buildAssignToTemp(loopctx, compareVar, order);
  499. BuildCtx subctx(loopctx);
  500. IHqlStmt * if1 = subctx.addFilter(test1); // if (test < 0)
  501. translator.buildAssignToTemp(subctx, rightVar, midVar); // right = mid;
  502. subctx.selectElse(if1); // else
  503. IHqlStmt * if2 = subctx.addFilter(test2); // if (test > 0)
  504. translator.buildAssignToTemp(subctx, leftVar, mid_p1); // left = mid + 1;
  505. subctx.selectElse(if2); // else
  506. //generate the default assignment...
  507. translator.buildExprAssign(subctx, target, resultExpr);
  508. subctx.addBreak();
  509. }
  510. }
  511. void HqlCppCaseInfo::buildIntegerSearchMap(BuildCtx & ctx, const CHqlBoundTarget & target, IHqlExpression * test)
  512. {
  513. ITypeInfo * compareType = queryCompareType();
  514. HqlExprArray args;
  515. args.append(*createCompareList());
  516. args.append(*LINK(test));
  517. IIdAtom * func;
  518. if (compareType->isSigned())
  519. {
  520. if (compareType->getSize() > 4)
  521. func = searchTableInteger8Id;
  522. else
  523. func = searchTableInteger4Id;
  524. }
  525. else
  526. {
  527. if (compareType->getSize() > 4)
  528. func = searchTableUInteger8Id;
  529. else
  530. func = searchTableUInteger4Id;
  531. }
  532. OwnedHqlExpr search = translator.bindFunctionCall(func, args);
  533. OwnedHqlExpr midVar = createVariable(LINK(indexType));
  534. bool includeDefaultInResult = false;
  535. OwnedHqlExpr resultExpr = createResultsExpr(midVar, true, &includeDefaultInResult);
  536. OwnedHqlExpr simpleResult = queryCreateSimpleResultAssign(search, resultExpr);
  537. if (simpleResult)
  538. translator.buildExprAssign(ctx, target, simpleResult);
  539. else
  540. {
  541. ctx.addDeclare(midVar, NULL);
  542. translator.buildAssignToTemp(ctx, midVar, search);
  543. if (includeDefaultInResult)
  544. {
  545. translator.buildExprAssign(ctx, target, resultExpr);
  546. }
  547. else
  548. {
  549. OwnedHqlExpr compare = createBoolExpr(no_ne, LINK(midVar), createNotFoundValue());
  550. BuildCtx subctx(ctx);
  551. IHqlStmt * stmt = subctx.addFilter(compare);
  552. translator.buildExprAssign(subctx, target, resultExpr);
  553. subctx.selectElse(stmt);
  554. translator.buildExprAssign(subctx, target, defaultValue);
  555. }
  556. }
  557. }
  558. void HqlCppCaseInfo::buildSwitchCondition(BuildCtx & ctx, CHqlBoundExpr & bound)
  559. {
  560. OwnedHqlExpr simpleCond = complexCompare ? getSimplifyCompareArg(cond) : LINK(cond);
  561. translator.buildCachedExpr(ctx, simpleCond, bound);
  562. }
  563. void HqlCppCaseInfo::buildSwitchMap(BuildCtx & ctx, const CHqlBoundTarget * target, IHqlExpression * test)
  564. {
  565. bool isCharCompare = (test->queryType()->getTypeCode() == type_string);
  566. Owned<ITypeInfo> unsigned1Type = makeIntType(1, false);
  567. LinkedHqlExpr cond = test;
  568. if (isCharCompare)
  569. cond.setown(createValue(no_implicitcast, LINK(unsigned1Type), createValue(no_index, makeCharType(), LINK(test), getZero())));
  570. BuildCtx subctx(ctx);
  571. IHqlStmt * stmt = subctx.addSwitch(cond);
  572. // are all the comparisons against constant values? If so we optimize it...
  573. unsigned sameCount = 0;
  574. ForEachItemIn(idx, pairs)
  575. {
  576. IHqlExpression & cur = pairs.item(idx);
  577. LinkedHqlExpr compare = cur.queryChild(0);
  578. IHqlExpression * branchValue = cur.queryChild(1);
  579. if (isCharCompare)
  580. {
  581. //Coded this way to avoid problems with ascii v ebcdic strings
  582. const byte * data = reinterpret_cast<const byte *>((char *)compare->queryValue()->queryValue());
  583. byte value = data[0];
  584. Owned<IValue> cast;
  585. if (value < 127)
  586. cast.setown(createCharValue(value, true));
  587. else
  588. cast.setown(createIntValue(data[0], LINK(unsigned1Type)));
  589. compare.setown(createConstant(cast.getClear()));
  590. }
  591. bool same = false;
  592. bool skip = false;
  593. if (idx != pairs.ordinality()-1)
  594. {
  595. IHqlExpression & next = pairs.item(idx+1);
  596. if (next.queryChild(1) == branchValue)
  597. same = true;
  598. //if save item is included twice, remove one so no error
  599. //from the case statement
  600. if (next.queryChild(0) == cur.queryChild(0))
  601. {
  602. skip = true;
  603. #ifdef _DEBUG
  604. throwUnexpected(); // should have been removed as a duplicate
  605. #endif
  606. }
  607. }
  608. if (sameCount >= MAX_NUM_NOBREAK_CASE)
  609. same = false;
  610. if (!skip)
  611. {
  612. subctx.addCase(stmt, compare);
  613. // common up case labels that produce the same result
  614. if (!same)
  615. {
  616. sameCount = 1;
  617. if (target)
  618. translator.buildExprAssign(subctx, *target, branchValue);
  619. else
  620. translator.buildReturn(subctx, branchValue);
  621. }
  622. else
  623. sameCount++;
  624. }
  625. }
  626. if (target)
  627. {
  628. subctx.addDefault(stmt);
  629. translator.buildExprAssign(subctx, *target, defaultValue);
  630. }
  631. else
  632. translator.buildReturn(ctx, defaultValue);
  633. }
  634. void HqlCppCaseInfo::buildGeneralAssign(BuildCtx & ctx, const CHqlBoundTarget & target)
  635. {
  636. unsigned max = pairs.ordinality();
  637. Owned<BuildCtx> subctx = new BuildCtx(ctx);
  638. CHqlBoundExpr pureCond;
  639. if (cond.get())
  640. translator.buildCachedExpr(*subctx, cond, pureCond);
  641. OwnedHqlExpr testMore;
  642. if (max > MAX_NESTED_CASES)
  643. {
  644. //Too many nested blocks cause the compiler indigestion...
  645. Owned<ITypeInfo> t = makeBoolType();
  646. testMore.setown(ctx.getTempDeclare(t, queryBoolExpr(false)));
  647. }
  648. for (unsigned idx = 0; idx < max; idx++)
  649. {
  650. IHqlExpression & cur = pairs.item(idx);
  651. IHqlExpression * curtest = cur.queryChild(0);
  652. IHqlExpression * curvalue = cur.queryChild(1);
  653. OwnedHqlExpr compare;
  654. if (!pureCond.expr)
  655. compare.setown(ensureExprType(curtest, queryBoolType()));
  656. else
  657. compare.setown(createBoolExpr(no_eq, pureCond.getTranslatedExpr(), LINK(curtest)));
  658. if (idx && ((idx % MAX_NESTED_CASES) == 0))
  659. {
  660. translator.buildAssignToTemp(*subctx,testMore,queryBoolExpr(true));
  661. subctx.setown(new BuildCtx(ctx));
  662. subctx->addFilter(testMore);
  663. translator.buildAssignToTemp(*subctx,testMore,queryBoolExpr(false));
  664. }
  665. IHqlStmt * test = translator.buildFilterViaExpr(*subctx, compare);
  666. translator.buildExprAssign(*subctx, target, curvalue);
  667. subctx->selectElse(test);
  668. }
  669. translator.buildExprAssign(*subctx, target, defaultValue);
  670. }
  671. void HqlCppCaseInfo::buildGeneralReturn(BuildCtx & ctx)
  672. {
  673. unsigned max = pairs.ordinality();
  674. CHqlBoundExpr pureCond;
  675. if (cond.get())
  676. translator.buildCachedExpr(ctx, cond, pureCond);
  677. for (unsigned idx = 0; idx < max; idx++)
  678. {
  679. IHqlExpression & cur = pairs.item(idx);
  680. IHqlExpression * curtest = cur.queryChild(0);
  681. IHqlExpression * curvalue = cur.queryChild(1);
  682. OwnedHqlExpr compare;
  683. if (!pureCond.expr)
  684. compare.setown(ensureExprType(curtest, queryBoolType()));
  685. else
  686. compare.setown(createBoolExpr(no_eq, pureCond.getTranslatedExpr(), LINK(curtest)));
  687. BuildCtx subctx(ctx);
  688. translator.buildFilter(subctx, compare);
  689. translator.buildReturn(subctx, curvalue);
  690. }
  691. translator.buildReturn(ctx, defaultValue);
  692. }
  693. bool HqlCppCaseInfo::okToAlwaysEvaluateDefault()
  694. {
  695. return defaultValue->isPure();
  696. }
  697. ITypeInfo * HqlCppCaseInfo::queryCompareType()
  698. {
  699. return cond->queryType()->queryPromotedType();
  700. }
  701. IHqlExpression * HqlCppCaseInfo::createCompareList()
  702. {
  703. //NB: All cases need to have the same type because they are stored in a table
  704. Linked<ITypeInfo> promoted = pairs.item(0).queryChild(0)->queryType();
  705. unsigned max = pairs.ordinality();
  706. for (unsigned idx1 = 1; idx1 < max; idx1++)
  707. {
  708. ITypeInfo * type = pairs.item(idx1).queryChild(0)->queryType();
  709. promoted.setown(getPromotedECLType(promoted, type));
  710. }
  711. HqlExprArray values;
  712. values.ensure(pairs.ordinality());
  713. ForEachItemIn(idx, pairs)
  714. {
  715. IHqlExpression & pair = pairs.item(idx);
  716. IHqlExpression * compare = pair.queryChild(0);
  717. values.append(*ensureExprType(compare, promoted));
  718. }
  719. Linked<ITypeInfo> compareType = queryCompareType();
  720. switch (compareType->getTypeCode())
  721. {
  722. case type_string:
  723. case type_data:
  724. case type_varstring:
  725. case type_qstring:
  726. case type_utf8:
  727. compareType.setown(makePointerType(makeCharType(false)));
  728. break;
  729. case type_unicode:
  730. case type_varunicode:
  731. compareType.setown(makePointerType(makeClassType("UChar")));
  732. break;
  733. }
  734. return createValue(no_list, makeArrayType(compareType.getLink()), values);
  735. }
  736. IHqlExpression * HqlCppCaseInfo::createResultsExpr(IHqlExpression * matchVar, bool canIncludeDefault, bool * includedDefault)
  737. {
  738. if (includedDefault)
  739. *includedDefault = false;
  740. //Look at all the return results and see what relation we can create
  741. //This can generate one of the following:
  742. //1. A single value.
  743. //2. A function of the result. e.g., IN...
  744. //3. A lookup in another table. [ all values are constant ]
  745. //4. A nested map statement
  746. bool areSame = true;
  747. bool areLinear = true;
  748. bool areConstant = true;
  749. __int64 linearStart = 0;
  750. __int64 linearMultiple = 1;
  751. ITypeInfo * retType = resultType;
  752. switch (retType->getTypeCode())
  753. {
  754. case type_int:
  755. case type_boolean:
  756. break;
  757. case type_string:
  758. case type_data:
  759. // areConstant = false; // a temporary hack to stop incorrect table being generated.
  760. areLinear = false;
  761. break;
  762. default:
  763. areLinear = false;
  764. break;
  765. }
  766. IHqlExpression * prevValue = NULL;
  767. HqlExprArray values;
  768. values.ensure(pairs.ordinality());
  769. ForEachItemIn(idx, pairs)
  770. {
  771. IHqlExpression & pair = pairs.item(idx);
  772. IHqlExpression * value = pair.queryChild(1);
  773. IValue * cvalue = value->queryValue();
  774. if (cvalue)
  775. {
  776. if (areLinear)
  777. {
  778. __int64 val = cvalue->getIntValue();
  779. if (idx == 0)
  780. linearStart = val;
  781. else if (idx == 1)
  782. linearMultiple = (val - linearStart);
  783. else if (val != linearStart + idx * linearMultiple)
  784. areLinear = false;
  785. }
  786. }
  787. else
  788. {
  789. areConstant = false;
  790. areLinear = false;
  791. }
  792. if (idx > 0)
  793. {
  794. if (areSame && (prevValue != value))
  795. areSame = false;
  796. }
  797. values.append(*ensureExprType(value, resultType));
  798. prevValue = value;
  799. }
  800. if (areSame)
  801. return LINK(prevValue);
  802. if (areLinear)
  803. {
  804. IHqlExpression * ret = ensureExprType(matchVar, resultType);
  805. if (linearMultiple != 1)
  806. ret = createValue(no_mul, LINK(resultType), ret, createConstant(resultType->castFrom(true, linearMultiple)));
  807. if (linearStart != 0)
  808. ret = createValue(no_add, LINK(resultType), ret, createConstant(resultType->castFrom(true, linearStart)));
  809. return ret;
  810. }
  811. unsigned firstMatchEntry = 0;
  812. if (canIncludeDefault)
  813. {
  814. //If all the values are constant, then can add the default as an extra 0th entry, because -1 will be the index for the default
  815. if (areConstant && defaultValue->isConstant() && defaultValue->queryType() == values.item(0).queryType())
  816. {
  817. firstMatchEntry = 1;
  818. values.add(*LINK(defaultValue), 0);
  819. *includedDefault = true;
  820. }
  821. }
  822. // easy way to create a value list...
  823. ITypeInfo * storeType = getArrayElementType(retType);
  824. OwnedHqlExpr newlist = createValue(no_list, makeSetType(storeType), values);
  825. if (areConstant && canBuildStaticList(resultType))
  826. {
  827. IHqlExpression * index = adjustValue(matchVar, 1+firstMatchEntry);
  828. return createValue(no_index, LINK(retType), LINK(newlist), index, createAttribute(noBoundCheckAtom));
  829. }
  830. //Need to generate a case (switch integer case 1: ..... )
  831. HqlExprArray choosePairs;
  832. cvtChooseListToPairs(choosePairs, newlist, 0);
  833. IHqlExpression * caseExpr = createOpenValue(no_case, LINK(retType));
  834. caseExpr->addOperand(LINK(matchVar));
  835. ForEachItemIn(idx2, choosePairs)
  836. caseExpr->addOperand(&choosePairs.item(idx2));
  837. choosePairs.kill(true);
  838. caseExpr->addOperand(LINK(defaultValue));
  839. return caseExpr->closeExpr();
  840. }
  841. void HqlCppCaseInfo::generateCompareVar(BuildCtx & ctx, IHqlExpression * target, CHqlBoundExpr & test, IHqlExpression * other)
  842. {
  843. OwnedHqlExpr compare = createValue(no_order, test.getTranslatedExpr(), LINK(other));
  844. translator.buildAssignToTemp(ctx, target, compare);
  845. }
  846. unsigned HqlCppCaseInfo::getNumPairs()
  847. {
  848. return pairs.ordinality();
  849. }
  850. bool HqlCppCaseInfo::hasLibraryChop()
  851. {
  852. ITypeInfo * compareType = queryCompareType();
  853. type_t ctc = compareType->getTypeCode();
  854. switch (ctc)
  855. {
  856. case type_data:
  857. return canBuildStaticList(promotedElementType);
  858. case type_string:
  859. case type_varstring:
  860. case type_qstring:
  861. case type_unicode:
  862. case type_varunicode:
  863. case type_utf8:
  864. return true;
  865. }
  866. return false;
  867. }
  868. void HqlCppCaseInfo::processBranches()
  869. {
  870. sortPairs();
  871. removeDuplicates();
  872. promoteTypes();
  873. }
  874. void HqlCppCaseInfo::promoteTypes()
  875. {
  876. Owned<ITypeInfo> promoted = pairs.item(0).queryChild(0)->getType();
  877. unsigned max = pairs.ordinality();
  878. for (unsigned idx1 = 1; idx1 < max; idx1++)
  879. {
  880. ITypeInfo * type = pairs.item(idx1).queryChild(0)->queryType();
  881. if (isStringType(promoted) && isStringType(type))
  882. {
  883. if (promoted->getStringLen() != type->getStringLen())
  884. {
  885. promoted.setown(::getPromotedECLType(promoted, type));
  886. promoted.setown(getStretchedType(UNKNOWN_LENGTH, promoted));
  887. }
  888. }
  889. promoted.setown(::getPromotedECLType(promoted, type));
  890. }
  891. promotedElementType.set(promoted);
  892. if (isStringType(promoted))
  893. promoted.setown(getStretchedType(UNKNOWN_LENGTH, promoted));
  894. ITypeInfo * testType = queryCompareType();
  895. if ((testType->queryCharset() != promoted->queryCharset()) || (testType->queryLocale() != promoted->queryLocale()))
  896. cond.setown(ensureExprType(cond, promoted));
  897. }
  898. bool HqlCppCaseInfo::canBuildArrayLookup(const CHqlBoundExpr & test)
  899. {
  900. ITypeInfo * condType = test.queryType()->queryPromotedType();
  901. //MORE: Also support this for high density tables that don't start at 0... - checking upper and lower bounds
  902. unsigned bitSize = condType->getBitSize();
  903. if (constantValues && (bitSize && (bitSize <= 8) && !condType->isSigned()))
  904. {
  905. unsigned limit = (1 << bitSize);
  906. //use case if enough items, or above a certain density...
  907. if (pairs.ordinality() * 100 >= limit * SWITCH_TABLE_DENSITY_THRESHOLD)
  908. {
  909. if ((condType->getTypeCode() == type_int) || (condType->getTypeCode() == type_string))
  910. return true;
  911. }
  912. }
  913. return false;
  914. }
  915. bool HqlCppCaseInfo::queryBuildArrayLookup(BuildCtx & ctx, const CHqlBoundTarget & target, const CHqlBoundExpr & test)
  916. {
  917. if (canBuildArrayLookup(test) && canBuildStaticList(resultType))
  918. {
  919. //MORE: Also support this for high density tables that don't start at 0... - checking upper and lower bounds
  920. ITypeInfo * condType = test.queryType()->queryPromotedType();
  921. unsigned bitSize = condType->getBitSize();
  922. unsigned limit = (1 << bitSize);
  923. BuildCtx subctx(ctx);
  924. OwnedHqlExpr ret = buildIndexedMap(subctx, test.expr, 0, limit-1);
  925. translator.buildExprAssign(ctx, target, ret);
  926. return true;
  927. }
  928. return false;
  929. }
  930. void HqlCppCaseInfo::removeDuplicates()
  931. {
  932. unsigned num = pairs.ordinality();
  933. if (num > 1)
  934. {
  935. num--;
  936. while (num--)
  937. {
  938. IHqlExpression & cur = pairs.item(num);
  939. IHqlExpression & next = pairs.item(num+1);
  940. if (cur.queryChild(0) == next.queryChild(0))
  941. {
  942. if (cur.queryChild(1) == next.queryChild(1))
  943. pairs.remove(num+1);
  944. else
  945. {
  946. // we need to keep the first in the original list.... Horrid, but it works...
  947. unsigned off1 = originalPairs.find(cur);
  948. unsigned off2 = originalPairs.find(next);
  949. assertex(off1 != NotFound && off2 != NotFound);
  950. if (off1 < off2)
  951. pairs.remove(num+1);
  952. else
  953. pairs.remove(num);
  954. }
  955. }
  956. }
  957. }
  958. }
  959. IHqlExpression * HqlCppCaseInfo::queryCreateSimpleResultAssign(IHqlExpression * search, IHqlExpression * resultExpr)
  960. {
  961. IHqlExpression * trueExpr = queryBoolExpr(true);
  962. IHqlExpression * falseExpr = queryBoolExpr(false);
  963. if (resultExpr == trueExpr && defaultValue == falseExpr)
  964. return createBoolExpr(no_ne, LINK(search), createNotFoundValue());
  965. if (resultExpr == falseExpr && defaultValue == trueExpr)
  966. return createBoolExpr(no_eq, LINK(search), createNotFoundValue());
  967. return NULL;
  968. }
  969. IHqlExpression * HqlCppCaseInfo::queryCompare(unsigned index)
  970. {
  971. return pairs.item(index).queryChild(0);
  972. }
  973. IHqlExpression * HqlCppCaseInfo::queryReturn(unsigned index)
  974. {
  975. return pairs.item(index).queryChild(1);
  976. }
  977. void HqlCppCaseInfo::setCond(IHqlExpression * expr)
  978. {
  979. cond.set(expr);
  980. if (isCompare3Valued(expr->queryType()))
  981. complexCompare = true;
  982. }
  983. void HqlCppCaseInfo::setDefault(IHqlExpression * expr)
  984. {
  985. defaultValue.set(expr);
  986. }
  987. void HqlCppCaseInfo::sortPairs()
  988. {
  989. appendArray(originalPairs, pairs);
  990. pairs.sort(comparePair);
  991. }
  992. void HqlCppCaseInfo::updateResultType(IHqlExpression * expr)
  993. {
  994. ITypeInfo * curResultType = expr->queryType();
  995. if (resultType)
  996. resultType.setown(::getPromotedECLType(resultType, curResultType));
  997. else
  998. resultType.set(curResultType);
  999. }