Ton

1
/*
2
    This file is part of TON Blockchain Library.
3

4
    TON Blockchain Library is free software: you can redistribute it and/or modify
5
    it under the terms of the GNU Lesser General Public License as published by
6
    the Free Software Foundation, either version 2 of the License, or
7
    (at your option) any later version.
8

9
    TON Blockchain Library is distributed in the hope that it will be useful,
10
    but WITHOUT ANY WARRANTY; without even the implied warranty of
11
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12
    GNU Lesser General Public License for more details.
13

14
    You should have received a copy of the GNU Lesser General Public License
15
    along with TON Blockchain Library.  If not, see <http://www.gnu.org/licenses/>.
16

17
    Copyright 2017-2020 Telegram Systems LLP
18
*/
19
#include "func.h"
20

21
namespace funC {
22

23
/*
24
 * 
25
 *   ABSTRACT CODE
26
 * 
27
 */
28

29
TmpVar::TmpVar(var_idx_t _idx, int _cls, TypeExpr* _type, SymDef* sym, const SrcLocation* loc)
30
    : v_type(_type), idx(_idx), cls(_cls), coord(0) {
31
  if (sym) {
32
    name = sym->sym_idx;
33
    sym->value->idx = _idx;
34
  }
35
  if (loc) {
36
    where = std::make_unique<SrcLocation>(*loc);
37
  }
38
  if (!_type) {
39
    v_type = TypeExpr::new_hole();
40
  }
41
  if (cls == _Named) {
42
    undefined = true;
43
  }
44
}
45

46
void TmpVar::set_location(const SrcLocation& loc) {
47
  if (where) {
48
    *where = loc;
49
  } else {
50
    where = std::make_unique<SrcLocation>(loc);
51
  }
52
}
53

54
void TmpVar::dump(std::ostream& os) const {
55
  show(os);
56
  os << " : " << v_type << " (width ";
57
  v_type->show_width(os);
58
  os << ")";
59
  if (coord > 0) {
60
    os << " = _" << (coord >> 8) << '.' << (coord & 255);
61
  } else if (coord < 0) {
62
    int n = (~coord >> 8), k = (~coord & 0xff);
63
    if (k) {
64
      os << " = (_" << n << ".._" << (n + k - 1) << ")";
65
    } else {
66
      os << " = ()";
67
    }
68
  }
69
  os << std::endl;
70
}
71

72
void TmpVar::show(std::ostream& os, int omit_idx) const {
73
  if (cls & _Named) {
74
    os << sym::symbols.get_name(name);
75
    if (omit_idx && (omit_idx >= 2 || (cls & _UniqueName))) {
76
      return;
77
    }
78
  }
79
  os << '_' << idx;
80
}
81

82
std::ostream& operator<<(std::ostream& os, const TmpVar& var) {
83
  var.show(os);
84
  return os;
85
}
86

87
void VarDescr::show_value(std::ostream& os) const {
88
  if (val & _Int) {
89
    os << 'i';
90
  }
91
  if (val & _Const) {
92
    os << 'c';
93
  }
94
  if (val & _Zero) {
95
    os << '0';
96
  }
97
  if (val & _NonZero) {
98
    os << '!';
99
  }
100
  if (val & _Pos) {
101
    os << '>';
102
  }
103
  if (val & _Neg) {
104
    os << '<';
105
  }
106
  if (val & _Bool) {
107
    os << 'B';
108
  }
109
  if (val & _Bit) {
110
    os << 'b';
111
  }
112
  if (val & _Even) {
113
    os << 'E';
114
  }
115
  if (val & _Odd) {
116
    os << 'O';
117
  }
118
  if (val & _Finite) {
119
    os << 'f';
120
  }
121
  if (val & _Nan) {
122
    os << 'N';
123
  }
124
  if (int_const.not_null()) {
125
    os << '=' << int_const;
126
  }
127
}
128

129
void VarDescr::show(std::ostream& os, const char* name) const {
130
  if (flags & _Last) {
131
    os << '*';
132
  }
133
  if (flags & _Unused) {
134
    os << '?';
135
  }
136
  if (name) {
137
    os << name;
138
  }
139
  os << '_' << idx;
140
  show_value(os);
141
}
142

143
void VarDescr::set_const(long long value) {
144
  return set_const(td::make_refint(value));
145
}
146

147
void VarDescr::set_const(td::RefInt256 value) {
148
  int_const = std::move(value);
149
  if (!int_const->signed_fits_bits(257)) {
150
    int_const.write().invalidate();
151
  }
152
  val = _Const | _Int;
153
  int s = sgn(int_const);
154
  if (s < -1) {
155
    val |= _Nan | _NonZero;
156
  } else if (s < 0) {
157
    val |= _NonZero | _Neg | _Finite;
158
    if (*int_const == -1) {
159
      val |= _Bool;
160
    }
161
  } else if (s > 0) {
162
    val |= _NonZero | _Pos | _Finite;
163
  } else if (!s) {
164
    //if (*int_const == 1) {
165
    //  val |= _Bit;
166
    //}
167
    val |= _Zero | _Neg | _Pos | _Finite | _Bool | _Bit;
168
  }
169
  if (val & _Finite) {
170
    val |= int_const->get_bit(0) ? _Odd : _Even;
171
  }
172
}
173

174
void VarDescr::set_const(std::string value) {
175
  str_const = value;
176
  val = _Const;
177
}
178

179
void VarDescr::set_const_nan() {
180
  set_const(td::make_refint());
181
}
182

183
void VarDescr::operator|=(const VarDescr& y) {
184
  val &= y.val;
185
  if (is_int_const() && y.is_int_const() && cmp(int_const, y.int_const) != 0) {
186
    val &= ~_Const;
187
  }
188
  if (!(val & _Const)) {
189
    int_const.clear();
190
  }
191
}
192

193
void VarDescr::operator&=(const VarDescr& y) {
194
  val |= y.val;
195
  if (y.int_const.not_null() && int_const.is_null()) {
196
    int_const = y.int_const;
197
  }
198
}
199

200
void VarDescr::set_value(const VarDescr& y) {
201
  val = y.val;
202
  int_const = y.int_const;
203
}
204

205
void VarDescr::set_value(VarDescr&& y) {
206
  val = y.val;
207
  int_const = std::move(y.int_const);
208
}
209

210
void VarDescr::clear_value() {
211
  val = 0;
212
  int_const.clear();
213
}
214

215
void VarDescrList::show(std::ostream& os) const {
216
  if (unreachable) {
217
    os << "<unreachable> ";
218
  }
219
  os << "[";
220
  for (const auto& v : list) {
221
    os << ' ' << v;
222
  }
223
  os << " ]\n";
224
}
225

226
void Op::flags_set_clear(int set, int clear) {
227
  flags = (flags | set) & ~clear;
228
  for (auto& op : block0) {
229
    op.flags_set_clear(set, clear);
230
  }
231
  for (auto& op : block1) {
232
    op.flags_set_clear(set, clear);
233
  }
234
}
235
void Op::split_vars(const std::vector<TmpVar>& vars) {
236
  split_var_list(left, vars);
237
  split_var_list(right, vars);
238
  for (auto& op : block0) {
239
    op.split_vars(vars);
240
  }
241
  for (auto& op : block1) {
242
    op.split_vars(vars);
243
  }
244
}
245

246
void Op::split_var_list(std::vector<var_idx_t>& var_list, const std::vector<TmpVar>& vars) {
247
  int new_size = 0, changes = 0;
248
  for (var_idx_t v : var_list) {
249
    int c = vars.at(v).coord;
250
    if (c < 0) {
251
      ++changes;
252
      new_size += (~c & 0xff);
253
    } else {
254
      ++new_size;
255
    }
256
  }
257
  if (!changes) {
258
    return;
259
  }
260
  std::vector<var_idx_t> new_var_list;
261
  new_var_list.reserve(new_size);
262
  for (var_idx_t v : var_list) {
263
    int c = vars.at(v).coord;
264
    if (c < 0) {
265
      int n = (~c >> 8), k = (~c & 0xff);
266
      while (k-- > 0) {
267
        new_var_list.push_back(n++);
268
      }
269
    } else {
270
      new_var_list.push_back(v);
271
    }
272
  }
273
  var_list = std::move(new_var_list);
274
}
275

276
void Op::show(std::ostream& os, const std::vector<TmpVar>& vars, std::string pfx, int mode) const {
277
  if (mode & 2) {
278
    os << pfx << " [";
279
    for (const auto& v : var_info.list) {
280
      os << ' ';
281
      if (v.flags & VarDescr::_Last) {
282
        os << '*';
283
      }
284
      if (v.flags & VarDescr::_Unused) {
285
        os << '?';
286
      }
287
      os << vars[v.idx];
288
      if (mode & 4) {
289
        os << ':';
290
        v.show_value(os);
291
      }
292
    }
293
    os << " ]\n";
294
  }
295
  std::string dis = disabled() ? "<disabled> " : "";
296
  if (noreturn()) {
297
    dis += "<noret> ";
298
  }
299
  if (!is_pure()) {
300
    dis += "<impure> ";
301
  }
302
  switch (cl) {
303
    case _Undef:
304
      os << pfx << dis << "???\n";
305
      break;
306
    case _Nop:
307
      os << pfx << dis << "NOP\n";
308
      break;
309
    case _Call:
310
      os << pfx << dis << "CALL: ";
311
      show_var_list(os, left, vars);
312
      os << " := " << (fun_ref ? fun_ref->name() : "(null)") << " ";
313
      if ((mode & 4) && args.size() == right.size()) {
314
        show_var_list(os, args, vars);
315
      } else {
316
        show_var_list(os, right, vars);
317
      }
318
      os << std::endl;
319
      break;
320
    case _CallInd:
321
      os << pfx << dis << "CALLIND: ";
322
      show_var_list(os, left, vars);
323
      os << " := EXEC ";
324
      show_var_list(os, right, vars);
325
      os << std::endl;
326
      break;
327
    case _Let:
328
      os << pfx << dis << "LET ";
329
      show_var_list(os, left, vars);
330
      os << " := ";
331
      show_var_list(os, right, vars);
332
      os << std::endl;
333
      break;
334
    case _Tuple:
335
      os << pfx << dis << "MKTUPLE ";
336
      show_var_list(os, left, vars);
337
      os << " := ";
338
      show_var_list(os, right, vars);
339
      os << std::endl;
340
      break;
341
    case _UnTuple:
342
      os << pfx << dis << "UNTUPLE ";
343
      show_var_list(os, left, vars);
344
      os << " := ";
345
      show_var_list(os, right, vars);
346
      os << std::endl;
347
      break;
348
    case _IntConst:
349
      os << pfx << dis << "CONST ";
350
      show_var_list(os, left, vars);
351
      os << " := " << int_const << std::endl;
352
      break;
353
    case _SliceConst:
354
      os << pfx << dis << "SCONST ";
355
      show_var_list(os, left, vars);
356
      os << " := " << str_const << std::endl;
357
      break;
358
    case _Import:
359
      os << pfx << dis << "IMPORT ";
360
      show_var_list(os, left, vars);
361
      os << std::endl;
362
      break;
363
    case _Return:
364
      os << pfx << dis << "RETURN ";
365
      show_var_list(os, left, vars);
366
      os << std::endl;
367
      break;
368
    case _GlobVar:
369
      os << pfx << dis << "GLOBVAR ";
370
      show_var_list(os, left, vars);
371
      os << " := " << (fun_ref ? fun_ref->name() : "(null)") << std::endl;
372
      break;
373
    case _SetGlob:
374
      os << pfx << dis << "SETGLOB ";
375
      os << (fun_ref ? fun_ref->name() : "(null)") << " := ";
376
      show_var_list(os, right, vars);
377
      os << std::endl;
378
      break;
379
    case _Repeat:
380
      os << pfx << dis << "REPEAT ";
381
      show_var_list(os, left, vars);
382
      os << ' ';
383
      show_block(os, block0.get(), vars, pfx, mode);
384
      os << std::endl;
385
      break;
386
    case _If:
387
      os << pfx << dis << "IF ";
388
      show_var_list(os, left, vars);
389
      os << ' ';
390
      show_block(os, block0.get(), vars, pfx, mode);
391
      os << " ELSE ";
392
      show_block(os, block1.get(), vars, pfx, mode);
393
      os << std::endl;
394
      break;
395
    case _While:
396
      os << pfx << dis << "WHILE ";
397
      show_var_list(os, left, vars);
398
      os << ' ';
399
      show_block(os, block0.get(), vars, pfx, mode);
400
      os << " DO ";
401
      show_block(os, block1.get(), vars, pfx, mode);
402
      os << std::endl;
403
      break;
404
    case _Until:
405
      os << pfx << dis << "UNTIL ";
406
      show_var_list(os, left, vars);
407
      os << ' ';
408
      show_block(os, block0.get(), vars, pfx, mode);
409
      os << std::endl;
410
      break;
411
    case _Again:
412
      os << pfx << dis << "AGAIN ";
413
      show_var_list(os, left, vars);
414
      os << ' ';
415
      show_block(os, block0.get(), vars, pfx, mode);
416
      os << std::endl;
417
      break;
418
    default:
419
      os << pfx << dis << "<???" << cl << "> ";
420
      show_var_list(os, left, vars);
421
      os << " -- ";
422
      show_var_list(os, right, vars);
423
      os << std::endl;
424
      break;
425
  }
426
}
427

428
void Op::show_var_list(std::ostream& os, const std::vector<var_idx_t>& idx_list,
429
                       const std::vector<TmpVar>& vars) const {
430
  if (!idx_list.size()) {
431
    os << "()";
432
  } else if (idx_list.size() == 1) {
433
    os << vars.at(idx_list[0]);
434
  } else {
435
    os << "(" << vars.at(idx_list[0]);
436
    for (std::size_t i = 1; i < idx_list.size(); i++) {
437
      os << "," << vars.at(idx_list[i]);
438
    }
439
    os << ")";
440
  }
441
}
442

443
void Op::show_var_list(std::ostream& os, const std::vector<VarDescr>& list, const std::vector<TmpVar>& vars) const {
444
  auto n = list.size();
445
  if (!n) {
446
    os << "()";
447
  } else {
448
    os << "( ";
449
    for (std::size_t i = 0; i < list.size(); i++) {
450
      if (i) {
451
        os << ", ";
452
      }
453
      if (list[i].is_unused()) {
454
        os << '?';
455
      }
456
      os << vars.at(list[i].idx) << ':';
457
      list[i].show_value(os);
458
    }
459
    os << " )";
460
  }
461
}
462

463
void Op::show_block(std::ostream& os, const Op* block, const std::vector<TmpVar>& vars, std::string pfx, int mode) {
464
  os << "{" << std::endl;
465
  std::string pfx2 = pfx + "  ";
466
  for (const Op& op : block) {
467
    op.show(os, vars, pfx2, mode);
468
  }
469
  os << pfx << "}";
470
}
471

472
void CodeBlob::flags_set_clear(int set, int clear) {
473
  for (auto& op : ops) {
474
    op.flags_set_clear(set, clear);
475
  }
476
}
477

478
std::ostream& operator<<(std::ostream& os, const CodeBlob& code) {
479
  code.print(os);
480
  return os;
481
}
482

483
// flags: +1 = show variable definition locations; +2 = show vars after each op; +4 = show var abstract value info after each op; +8 = show all variables at start
484
void CodeBlob::print(std::ostream& os, int flags) const {
485
  os << "CODE BLOB: " << var_cnt << " variables, " << in_var_cnt << " input\n";
486
  if ((flags & 8) != 0) {
487
    for (const auto& var : vars) {
488
      var.dump(os);
489
      if (var.where && (flags & 1) != 0) {
490
        var.where->show(os);
491
        os << " defined here:\n";
492
        var.where->show_context(os);
493
      }
494
    }
495
  }
496
  os << "------- BEGIN --------\n";
497
  for (const auto& op : ops) {
498
    op.show(os, vars, "", flags);
499
  }
500
  os << "-------- END ---------\n\n";
501
}
502

503
var_idx_t CodeBlob::create_var(int cls, TypeExpr* var_type, SymDef* sym, const SrcLocation* location) {
504
  vars.emplace_back(var_cnt, cls, var_type, sym, location);
505
  if (sym) {
506
    sym->value->idx = var_cnt;
507
  }
508
  return var_cnt++;
509
}
510

511
bool CodeBlob::import_params(FormalArgList arg_list) {
512
  if (var_cnt || in_var_cnt || op_cnt) {
513
    return false;
514
  }
515
  std::vector<var_idx_t> list;
516
  for (const auto& par : arg_list) {
517
    TypeExpr* arg_type;
518
    SymDef* arg_sym;
519
    SrcLocation arg_loc;
520
    std::tie(arg_type, arg_sym, arg_loc) = par;
521
    list.push_back(create_var(arg_sym ? (TmpVar::_In | TmpVar::_Named) : TmpVar::_In, arg_type, arg_sym, &arg_loc));
522
  }
523
  emplace_back(loc, Op::_Import, list);
524
  in_var_cnt = var_cnt;
525
  return true;
526
}
527

528
}  // namespace funC
529