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 <numeric>
20
#include "func.h"
21

22
using namespace std::literals::string_literals;
23

24
namespace funC {
25

26
/*
27
 * 
28
 *   EXPRESSIONS
29
 * 
30
 */
31

32
Expr* Expr::copy() const {
33
  auto res = new Expr{*this};
34
  for (auto& arg : res->args) {
35
    arg = arg->copy();
36
  }
37
  return res;
38
}
39

40
Expr::Expr(int c, sym_idx_t name_idx, std::initializer_list<Expr*> _arglist) : cls(c), args(std::move(_arglist)) {
41
  sym = sym::lookup_symbol(name_idx);
42
  if (!sym) {
43
  }
44
}
45

46
void Expr::chk_rvalue(const Lexem& lem) const {
47
  if (!is_rvalue()) {
48
    lem.error_at("rvalue expected before `", "`");
49
  }
50
}
51

52
void Expr::chk_lvalue(const Lexem& lem) const {
53
  if (!is_lvalue()) {
54
    lem.error_at("lvalue expected before `", "`");
55
  }
56
}
57

58
void Expr::chk_type(const Lexem& lem) const {
59
  if (!is_type()) {
60
    lem.error_at("type expression expected before `", "`");
61
  }
62
}
63

64
bool Expr::deduce_type(const Lexem& lem) {
65
  if (e_type) {
66
    return true;
67
  }
68
  switch (cls) {
69
    case _Apply: {
70
      if (!sym) {
71
        return false;
72
      }
73
      SymVal* sym_val = dynamic_cast<SymVal*>(sym->value);
74
      if (!sym_val || !sym_val->get_type()) {
75
        return false;
76
      }
77
      std::vector<TypeExpr*> arg_types;
78
      for (const auto& arg : args) {
79
        arg_types.push_back(arg->e_type);
80
      }
81
      TypeExpr* fun_type = TypeExpr::new_map(TypeExpr::new_tensor(arg_types), TypeExpr::new_hole());
82
      try {
83
        unify(fun_type, sym_val->sym_type);
84
      } catch (UnifyError& ue) {
85
        std::ostringstream os;
86
        os << "cannot apply function " << sym->name() << " : " << sym_val->get_type() << " to arguments of type "
87
           << fun_type->args[0] << ": " << ue;
88
        lem.error(os.str());
89
      }
90
      e_type = fun_type->args[1];
91
      TypeExpr::remove_indirect(e_type);
92
      return true;
93
    }
94
    case _VarApply: {
95
      func_assert(args.size() == 2);
96
      TypeExpr* fun_type = TypeExpr::new_map(args[1]->e_type, TypeExpr::new_hole());
97
      try {
98
        unify(fun_type, args[0]->e_type);
99
      } catch (UnifyError& ue) {
100
        std::ostringstream os;
101
        os << "cannot apply expression of type " << args[0]->e_type << " to an expression of type " << args[1]->e_type
102
           << ": " << ue;
103
        lem.error(os.str());
104
      }
105
      e_type = fun_type->args[1];
106
      TypeExpr::remove_indirect(e_type);
107
      return true;
108
    }
109
    case _Letop: {
110
      func_assert(args.size() == 2);
111
      try {
112
        // std::cerr << "in assignment: " << args[0]->e_type << " from " << args[1]->e_type << std::endl;
113
        unify(args[0]->e_type, args[1]->e_type);
114
      } catch (UnifyError& ue) {
115
        std::ostringstream os;
116
        os << "cannot assign an expression of type " << args[1]->e_type << " to a variable or pattern of type "
117
           << args[0]->e_type << ": " << ue;
118
        lem.error(os.str());
119
      }
120
      e_type = args[0]->e_type;
121
      TypeExpr::remove_indirect(e_type);
122
      return true;
123
    }
124
    case _LetFirst: {
125
      func_assert(args.size() == 2);
126
      TypeExpr* rhs_type = TypeExpr::new_tensor({args[0]->e_type, TypeExpr::new_hole()});
127
      try {
128
        // std::cerr << "in implicit assignment of a modifying method: " << rhs_type << " and " << args[1]->e_type << std::endl;
129
        unify(rhs_type, args[1]->e_type);
130
      } catch (UnifyError& ue) {
131
        std::ostringstream os;
132
        os << "cannot implicitly assign an expression of type " << args[1]->e_type
133
           << " to a variable or pattern of type " << rhs_type << " in modifying method `" << sym::symbols.get_name(val)
134
           << "` : " << ue;
135
        lem.error(os.str());
136
      }
137
      e_type = rhs_type->args[1];
138
      TypeExpr::remove_indirect(e_type);
139
      // std::cerr << "result type is " << e_type << std::endl;
140
      return true;
141
    }
142
    case _CondExpr: {
143
      func_assert(args.size() == 3);
144
      auto flag_type = TypeExpr::new_atomic(_Int);
145
      try {
146
        unify(args[0]->e_type, flag_type);
147
      } catch (UnifyError& ue) {
148
        std::ostringstream os;
149
        os << "condition in a conditional expression has non-integer type " << args[0]->e_type << ": " << ue;
150
        lem.error(os.str());
151
      }
152
      try {
153
        unify(args[1]->e_type, args[2]->e_type);
154
      } catch (UnifyError& ue) {
155
        std::ostringstream os;
156
        os << "the two variants in a conditional expression have different types " << args[1]->e_type << " and "
157
           << args[2]->e_type << " : " << ue;
158
        lem.error(os.str());
159
      }
160
      e_type = args[1]->e_type;
161
      TypeExpr::remove_indirect(e_type);
162
      return true;
163
    }
164
  }
165
  return false;
166
}
167

168
int Expr::define_new_vars(CodeBlob& code) {
169
  switch (cls) {
170
    case _Tensor:
171
    case _MkTuple:
172
    case _TypeApply: {
173
      int res = 0;
174
      for (const auto& x : args) {
175
        res += x->define_new_vars(code);
176
      }
177
      return res;
178
    }
179
    case _Var:
180
      if (val < 0) {
181
        val = code.create_var(TmpVar::_Named, e_type, sym, &here);
182
        return 1;
183
      }
184
      break;
185
    case _Hole:
186
      if (val < 0) {
187
        val = code.create_var(TmpVar::_Tmp, e_type, nullptr, &here);
188
      }
189
      break;
190
  }
191
  return 0;
192
}
193

194
int Expr::predefine_vars() {
195
  switch (cls) {
196
    case _Tensor:
197
    case _MkTuple:
198
    case _TypeApply: {
199
      int res = 0;
200
      for (const auto& x : args) {
201
        res += x->predefine_vars();
202
      }
203
      return res;
204
    }
205
    case _Var:
206
      if (!sym) {
207
        func_assert(val < 0 && here.defined());
208
        if (prohibited_var_names.count(sym::symbols.get_name(~val))) {
209
          throw src::ParseError{
210
              here, PSTRING() << "symbol `" << sym::symbols.get_name(~val) << "` cannot be redefined as a variable"};
211
        }
212
        sym = sym::define_symbol(~val, false, here);
213
        // std::cerr << "predefining variable " << sym::symbols.get_name(~val) << std::endl;
214
        if (!sym) {
215
          throw src::ParseError{here, std::string{"redefined variable `"} + sym::symbols.get_name(~val) + "`"};
216
        }
217
        sym->value = new SymVal{SymVal::_Var, -1, e_type};
218
        return 1;
219
      }
220
      break;
221
  }
222
  return 0;
223
}
224

225
var_idx_t Expr::new_tmp(CodeBlob& code) const {
226
  return code.create_tmp_var(e_type, &here);
227
}
228

229
void add_set_globs(CodeBlob& code, std::vector<std::pair<SymDef*, var_idx_t>>& globs, const SrcLocation& here) {
230
  for (const auto& p : globs) {
231
    auto& op = code.emplace_back(here, Op::_SetGlob, std::vector<var_idx_t>{}, std::vector<var_idx_t>{ p.second }, p.first);
232
    op.flags |= Op::_Impure;
233
  }
234
}
235

236
std::vector<var_idx_t> Expr::pre_compile_let(CodeBlob& code, Expr* lhs, Expr* rhs, const SrcLocation& here) {
237
  while (lhs->is_type_apply()) {
238
    lhs = lhs->args.at(0);
239
  }
240
  while (rhs->is_type_apply()) {
241
    rhs = rhs->args.at(0);
242
  }
243
  if (lhs->is_mktuple()) {
244
    if (rhs->is_mktuple()) {
245
      return pre_compile_let(code, lhs->args.at(0), rhs->args.at(0), here);
246
    }
247
    auto right = rhs->pre_compile(code);
248
    TypeExpr::remove_indirect(rhs->e_type);
249
    auto unpacked_type = rhs->e_type->args.at(0);
250
    std::vector<var_idx_t> tmp{code.create_tmp_var(unpacked_type, &rhs->here)};
251
    code.emplace_back(lhs->here, Op::_UnTuple, tmp, std::move(right));
252
    auto tvar = new Expr{_Var};
253
    tvar->set_val(tmp[0]);
254
    tvar->set_location(rhs->here);
255
    tvar->e_type = unpacked_type;
256
    pre_compile_let(code, lhs->args.at(0), tvar, here);
257
    return tmp;
258
  }
259
  auto right = rhs->pre_compile(code);
260
  std::vector<std::pair<SymDef*, var_idx_t>> globs;
261
  auto left = lhs->pre_compile(code, &globs);
262
  for (var_idx_t v : left) {
263
    code.on_var_modification(v, here);
264
  }
265
  code.emplace_back(here, Op::_Let, std::move(left), right);
266
  add_set_globs(code, globs, here);
267
  return right;
268
}
269

270
std::vector<var_idx_t> pre_compile_tensor(const std::vector<Expr *> args, CodeBlob &code,
271
                                          std::vector<std::pair<SymDef*, var_idx_t>> *lval_globs,
272
                                          std::vector<int> arg_order) {
273
  if (arg_order.empty()) {
274
    arg_order.resize(args.size());
275
    std::iota(arg_order.begin(), arg_order.end(), 0);
276
  }
277
  func_assert(args.size() == arg_order.size());
278
  std::vector<std::vector<var_idx_t>> res_lists(args.size());
279

280
  struct ModifiedVar {
281
    size_t i, j;
282
    Op* op;
283
  };
284
  auto modified_vars = std::make_shared<std::vector<ModifiedVar>>();
285
  for (size_t i : arg_order) {
286
    res_lists[i] = args[i]->pre_compile(code, lval_globs);
287
    for (size_t j = 0; j < res_lists[i].size(); ++j) {
288
      TmpVar& var = code.vars.at(res_lists[i][j]);
289
      if (code.flags & CodeBlob::_AllowPostModification) {
290
        if (!lval_globs && (var.cls & TmpVar::_Named)) {
291
          Op *op = &code.emplace_back(nullptr, Op::_Let, std::vector<var_idx_t>(), std::vector<var_idx_t>());
292
          op->flags |= Op::_Disabled;
293
          var.on_modification.push_back([modified_vars, i, j, op, done = false](const SrcLocation &here) mutable {
294
            if (!done) {
295
              done = true;
296
              modified_vars->push_back({i, j, op});
297
            }
298
          });
299
        } else {
300
          var.on_modification.push_back([](const SrcLocation &) {
301
          });
302
        }
303
      } else {
304
        var.on_modification.push_back([name = var.to_string()](const SrcLocation &here) {
305
            throw src::ParseError{here, PSTRING() << "Modifying local variable " << name
306
                                                  << " after using it in the same expression"};
307
        });
308
      }
309
    }
310
  }
311
  for (const auto& list : res_lists) {
312
    for (var_idx_t v : list) {
313
      func_assert(!code.vars.at(v).on_modification.empty());
314
      code.vars.at(v).on_modification.pop_back();
315
    }
316
  }
317
  for (const ModifiedVar &m : *modified_vars) {
318
    var_idx_t& v = res_lists[m.i][m.j];
319
    var_idx_t v2 = code.create_tmp_var(code.vars[v].v_type, code.vars[v].where.get());
320
    m.op->left = {v2};
321
    m.op->right = {v};
322
    m.op->flags &= ~Op::_Disabled;
323
    v = v2;
324
  }
325
  std::vector<var_idx_t> res;
326
  for (const auto& list : res_lists) {
327
    res.insert(res.end(), list.cbegin(), list.cend());
328
  }
329
  return res;
330
}
331

332
std::vector<var_idx_t> Expr::pre_compile(CodeBlob& code, std::vector<std::pair<SymDef*, var_idx_t>>* lval_globs) const {
333
  if (lval_globs && !(cls == _Tensor || cls == _Var || cls == _Hole || cls == _TypeApply || cls == _GlobVar)) {
334
    std::cerr << "lvalue expression constructor is " << cls << std::endl;
335
    throw src::Fatal{"cannot compile lvalue expression with unknown constructor"};
336
  }
337
  switch (cls) {
338
    case _Tensor: {
339
      return pre_compile_tensor(args, code, lval_globs, {});
340
    }
341
    case _Apply: {
342
      func_assert(sym);
343
      auto func = dynamic_cast<SymValFunc*>(sym->value);
344
      std::vector<var_idx_t> res;
345
      if (func && func->arg_order.size() == args.size() && !(code.flags & CodeBlob::_ComputeAsmLtr)) {
346
        //std::cerr << "!!! reordering " << args.size() << " arguments of " << sym->name() << std::endl;
347
        res = pre_compile_tensor(args, code, lval_globs, func->arg_order);
348
      } else {
349
        res = pre_compile_tensor(args, code, lval_globs, {});
350
      }
351
      auto rvect = new_tmp_vect(code);
352
      auto& op = code.emplace_back(here, Op::_Call, rvect, std::move(res), sym);
353
      if (flags & _IsImpure) {
354
        op.flags |= Op::_Impure;
355
      }
356
      return rvect;
357
    }
358
    case _TypeApply:
359
      return args[0]->pre_compile(code, lval_globs);
360
    case _Var:
361
    case _Hole:
362
      if (val < 0) {
363
        throw src::ParseError{here, "unexpected variable definition"};
364
      }
365
      return {val};
366
    case _VarApply:
367
      if (args[0]->cls == _Glob) {
368
        auto res = args[1]->pre_compile(code);
369
        auto rvect = new_tmp_vect(code);
370
        auto& op = code.emplace_back(here, Op::_Call, rvect, std::move(res), args[0]->sym);
371
        if (args[0]->flags & _IsImpure) {
372
          op.flags |= Op::_Impure;
373
        }
374
        return rvect;
375
      } else {
376
        auto res = args[1]->pre_compile(code);
377
        auto tfunc = args[0]->pre_compile(code);
378
        if (tfunc.size() != 1) {
379
          throw src::Fatal{"stack tuple used as a function"};
380
        }
381
        res.push_back(tfunc[0]);
382
        auto rvect = new_tmp_vect(code);
383
        code.emplace_back(here, Op::_CallInd, rvect, std::move(res));
384
        return rvect;
385
      }
386
    case _Const: {
387
      auto rvect = new_tmp_vect(code);
388
      code.emplace_back(here, Op::_IntConst, rvect, intval);
389
      return rvect;
390
    }
391
    case _Glob:
392
    case _GlobVar: {
393
      auto rvect = new_tmp_vect(code);
394
      if (lval_globs) {
395
        lval_globs->push_back({ sym, rvect[0] });
396
        return rvect;
397
      } else {
398
        code.emplace_back(here, Op::_GlobVar, rvect, std::vector<var_idx_t>{}, sym);
399
        return rvect;
400
      }
401
    }
402
    case _Letop: {
403
      return pre_compile_let(code, args.at(0), args.at(1), here);
404
    }
405
    case _LetFirst: {
406
      auto rvect = new_tmp_vect(code);
407
      auto right = args[1]->pre_compile(code);
408
      std::vector<std::pair<SymDef*, var_idx_t>> local_globs;
409
      if (!lval_globs) {
410
        lval_globs = &local_globs;
411
      }
412
      auto left = args[0]->pre_compile(code, lval_globs);
413
      left.push_back(rvect[0]);
414
      for (var_idx_t v : left) {
415
        code.on_var_modification(v, here);
416
      }
417
      code.emplace_back(here, Op::_Let, std::move(left), std::move(right));
418
      add_set_globs(code, local_globs, here);
419
      return rvect;
420
    }
421
    case _MkTuple: {
422
      auto left = new_tmp_vect(code);
423
      auto right = args[0]->pre_compile(code);
424
      code.emplace_back(here, Op::_Tuple, left, std::move(right));
425
      return left;
426
    }
427
    case _CondExpr: {
428
      auto cond = args[0]->pre_compile(code);
429
      func_assert(cond.size() == 1);
430
      auto rvect = new_tmp_vect(code);
431
      Op& if_op = code.emplace_back(here, Op::_If, cond);
432
      code.push_set_cur(if_op.block0);
433
      code.emplace_back(here, Op::_Let, rvect, args[1]->pre_compile(code));
434
      code.close_pop_cur(args[1]->here);
435
      code.push_set_cur(if_op.block1);
436
      code.emplace_back(here, Op::_Let, rvect, args[2]->pre_compile(code));
437
      code.close_pop_cur(args[2]->here);
438
      return rvect;
439
    }
440
    case _SliceConst: {
441
      auto rvect = new_tmp_vect(code);
442
      code.emplace_back(here, Op::_SliceConst, rvect, strval);
443
      return rvect;
444
    }
445
    default:
446
      std::cerr << "expression constructor is " << cls << std::endl;
447
      throw src::Fatal{"cannot compile expression with unknown constructor"};
448
  }
449
}
450

451
}  // namespace funC
452