1 /*
2 Copyright 2015 Google Inc. All rights reserved.
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 <cassert>
18 #include <cmath>
19
20 #include <memory>
21 #include <set>
22 #include <string>
23
24 #include "desugarer.h"
25 #include "json.h"
26 #include "nlohmann/json.hpp"
27 #include "md5.h"
28 #include "parser.h"
29 #include "state.h"
30 #include "static_analysis.h"
31 #include "string_utils.h"
32 #include "vm.h"
33
34 using json = nlohmann::json;
35
36 namespace {
37
38 /** Turn a path e.g. "/a/b/c" into a dir, e.g. "/a/b/". If there is no path returns "".
39 */
dir_name(const std::string & path)40 std::string dir_name(const std::string &path)
41 {
42 size_t last_slash = path.rfind('/');
43 if (last_slash != std::string::npos) {
44 return path.substr(0, last_slash + 1);
45 }
46 return "";
47 }
48
49 /** Stack frames.
50 *
51 * Of these, FRAME_CALL is the most special, as it is the only frame the stack
52 * trace (for errors) displays.
53 */
54 enum FrameKind {
55 FRAME_APPLY_TARGET, // e in e(...)
56 FRAME_BINARY_LEFT, // a in a + b
57 FRAME_BINARY_RIGHT, // b in a + b
58 FRAME_BINARY_OP, // a + b, with a and b already calculated
59 FRAME_BUILTIN_FILTER, // When executing std.filter, used to hold intermediate state.
60 FRAME_BUILTIN_FORCE_THUNKS, // When forcing builtin args, holds intermediate state.
61 FRAME_CALL, // Used any time we have switched location in user code.
62 FRAME_ERROR, // e in error e
63 FRAME_IF, // e in if e then a else b
64 FRAME_IN_SUPER_ELEMENT, // e in 'e in super'
65 FRAME_INDEX_TARGET, // e in e[x]
66 FRAME_INDEX_INDEX, // e in x[e]
67 FRAME_INVARIANTS, // Caches the thunks that need to be executed one at a time.
68 FRAME_LOCAL, // Stores thunk bindings as we execute e in local ...; e
69 FRAME_OBJECT, // Stores intermediate state as we execute es in { [e]: ..., [e]: ... }
70 FRAME_OBJECT_COMP_ARRAY, // e in {f:a for x in e]
71 FRAME_OBJECT_COMP_ELEMENT, // Stores intermediate state when building object
72 FRAME_STRING_CONCAT, // Stores intermediate state while co-ercing objects
73 FRAME_SUPER_INDEX, // e in super[e]
74 FRAME_UNARY, // e in -e
75 FRAME_BUILTIN_JOIN_STRINGS, // When executing std.join over strings, used to hold intermediate state.
76 FRAME_BUILTIN_JOIN_ARRAYS, // When executing std.join over arrays, used to hold intermediate state.
77 FRAME_BUILTIN_DECODE_UTF8, // When executing std.decodeUTF8, used to hold intermediate state.
78 };
79
80 /** A frame on the stack.
81 *
82 * Every time a subterm is evaluated, we first push a new stack frame to
83 * store the continuation.
84 *
85 * The stack frame is a bit like a tagged union, except not as memory
86 * efficient. The set of member variables that are actually used depends on
87 * the value of the member varaible kind.
88 *
89 * If the stack frame is of kind FRAME_CALL, then it counts towards the
90 * maximum number of stack frames allowed. Other stack frames are not
91 * counted. This is because FRAME_CALL exists where there is a branch in
92 * the code, e.g. the forcing of a thunk, evaluation of a field, calling a
93 * function, etc.
94 *
95 * The stack is used to mark objects during garbage
96 * collection, so HeapObjects not referred to from the stack may be
97 * prematurely collected.
98 */
99 struct Frame {
100 /** Tag (tagged union). */
101 FrameKind kind;
102
103 /** The code we were executing before. */
104 const AST *ast;
105
106 /** The location of the code we were executing before.
107 *
108 * location == ast->location when ast != nullptr
109 */
110 LocationRange location;
111
112 /** Reuse this stack frame for the purpose of tail call optimization. */
113 bool tailCall;
114
115 /** Used for a variety of purposes. */
116 Value val;
117
118 /** Used for a variety of purposes. */
119 Value val2;
120
121 /** Used for a variety of purposes. */
122 DesugaredObject::Fields::const_iterator fit;
123
124 /** Used for a variety of purposes. */
125 std::map<const Identifier *, HeapSimpleObject::Field> objectFields;
126
127 /** Used for a variety of purposes. */
128 unsigned elementId;
129
130 /** Used for a variety of purposes. */
131 std::map<const Identifier *, HeapThunk *> elements;
132
133 /** Used for a variety of purposes. */
134 std::vector<HeapThunk *> thunks;
135
136 /** Used for accumulating a joined string. */
137 UString str;
138 bool first;
139
140 /** Used for accumulating bytes */
141 std::string bytes;
142
143 /** The context is used in error messages to attempt to find a reasonable name for the
144 * object, function, or thunk value being executed. If it is a thunk, it is filled
145 * with the value when the frame terminates.
146 */
147 HeapEntity *context;
148
149 /** The lexically nearest object we are in, or nullptr. Note
150 * that this is not the same as context, because we could be inside a function,
151 * inside an object and then context would be the function, but self would still point
152 * to the object.
153 */
154 HeapObject *self;
155
156 /** The "super" level of self. Sometimes, we look upwards in the
157 * inheritance tree, e.g. via an explicit use of super, or because a given field
158 * has been inherited. When evaluating a field from one of these super objects,
159 * we need to bind self to the concrete object (so self must point
160 * there) but uses of super should be resolved relative to the object whose
161 * field we are evaluating. Thus, we keep a second field for that. This is
162 * usually 0, unless we are evaluating a super object's field.
163 */
164 unsigned offset;
165
166 /** A set of variables introduced at this point. */
167 BindingFrame bindings;
168
Frame__anonb7e79ae60111::Frame169 Frame(const FrameKind &kind, const AST *ast)
170 : kind(kind),
171 ast(ast),
172 location(ast->location),
173 tailCall(false),
174 elementId(0),
175 context(NULL),
176 self(NULL),
177 offset(0)
178 {
179 val.t = Value::NULL_TYPE;
180 val2.t = Value::NULL_TYPE;
181 }
182
Frame__anonb7e79ae60111::Frame183 Frame(const FrameKind &kind, const LocationRange &location)
184 : kind(kind),
185 ast(nullptr),
186 location(location),
187 tailCall(false),
188 elementId(0),
189 context(NULL),
190 self(NULL),
191 offset(0)
192 {
193 val.t = Value::NULL_TYPE;
194 val2.t = Value::NULL_TYPE;
195 }
196
197 /** Mark everything visible from this frame. */
mark__anonb7e79ae60111::Frame198 void mark(Heap &heap) const
199 {
200 heap.markFrom(val);
201 heap.markFrom(val2);
202 if (context)
203 heap.markFrom(context);
204 if (self)
205 heap.markFrom(self);
206 for (const auto &bind : bindings)
207 heap.markFrom(bind.second);
208 for (const auto &el : elements)
209 heap.markFrom(el.second);
210 for (const auto &th : thunks)
211 heap.markFrom(th);
212 }
213
isCall__anonb7e79ae60111::Frame214 bool isCall(void) const
215 {
216 return kind == FRAME_CALL;
217 }
218 };
219
220 /** The stack holds all the stack frames and manages the stack frame limit. */
221 class Stack {
222 /** How many call frames are on the stack. */
223 unsigned calls;
224
225 /** How many call frames should be allowed before aborting the program. */
226 unsigned limit;
227
228 /** The stack frames. */
229 std::vector<Frame> stack;
230
231 public:
Stack(unsigned limit)232 Stack(unsigned limit) : calls(0), limit(limit) {}
233
~Stack(void)234 ~Stack(void) {}
235
size(void)236 unsigned size(void)
237 {
238 return stack.size();
239 }
240
241 /** Search for the closest variable in scope that matches the given name. */
lookUpVar(const Identifier * id)242 HeapThunk *lookUpVar(const Identifier *id)
243 {
244 for (int i = stack.size() - 1; i >= 0; --i) {
245 const auto &binds = stack[i].bindings;
246 auto it = binds.find(id);
247 if (it != binds.end()) {
248 return it->second;
249 }
250 if (stack[i].isCall())
251 break;
252 }
253 return nullptr;
254 }
255
256 /** Mark everything visible from the stack (any frame). */
mark(Heap & heap)257 void mark(Heap &heap)
258 {
259 for (const auto &f : stack) {
260 f.mark(heap);
261 }
262 }
263
top(void)264 Frame &top(void)
265 {
266 return stack.back();
267 }
268
top(void) const269 const Frame &top(void) const
270 {
271 return stack.back();
272 }
273
pop(void)274 void pop(void)
275 {
276 if (top().isCall())
277 calls--;
278 stack.pop_back();
279 }
280
281 /** Attempt to find a name for a given heap entity. This may not be possible, but we try
282 * reasonably hard. We look in the bindings for a variable in the closest scope that
283 * happens to point at the entity in question. Otherwise, the best we can do is use its
284 * type.
285 */
getName(unsigned from_here,const HeapEntity * e)286 std::string getName(unsigned from_here, const HeapEntity *e)
287 {
288 std::string name;
289 for (int i = from_here - 1; i >= 0; --i) {
290 const auto &f = stack[i];
291 for (const auto &pair : f.bindings) {
292 HeapThunk *thunk = pair.second;
293 if (!thunk->filled)
294 continue;
295 if (!thunk->content.isHeap())
296 continue;
297 if (e != thunk->content.v.h)
298 continue;
299 name = encode_utf8(pair.first->name);
300 }
301 // Do not go into the next call frame, keep local reasoning.
302 if (f.isCall())
303 break;
304 }
305
306 if (name == "")
307 name = "anonymous";
308 if (dynamic_cast<const HeapObject *>(e)) {
309 return "object <" + name + ">";
310 } else if (auto *thunk = dynamic_cast<const HeapThunk *>(e)) {
311 if (thunk->name == nullptr) {
312 return ""; // Argument of builtin, or root (since top level functions).
313 } else {
314 return "thunk <" + encode_utf8(thunk->name->name) + ">";
315 }
316 } else {
317 const auto *func = static_cast<const HeapClosure *>(e);
318 if (func->body == nullptr) {
319 return "builtin function <" + func->builtinName + ">";
320 }
321 return "function <" + name + ">";
322 }
323 }
324
325 /** Dump the stack.
326 *
327 * This is useful to help debug the VM in gdb. It is virtual to stop it
328 * being removed by the compiler.
329 */
dump(void)330 virtual void dump(void)
331 {
332 for (unsigned i = 0; i < stack.size(); ++i) {
333 std::cout << "stack[" << i << "] = " << stack[i].location << " (" << stack[i].kind
334 << ")" << std::endl;
335 }
336 std::cout << std::endl;
337 }
338
339 /** Creates the error object for throwing, and also populates it with the stack trace.
340 */
makeError(const LocationRange & loc,const std::string & msg)341 RuntimeError makeError(const LocationRange &loc, const std::string &msg)
342 {
343 std::vector<TraceFrame> stack_trace;
344 stack_trace.push_back(TraceFrame(loc));
345 for (int i = stack.size() - 1; i >= 0; --i) {
346 const auto &f = stack[i];
347 if (f.isCall()) {
348 if (f.context != nullptr) {
349 // Give the last line a name.
350 stack_trace[stack_trace.size() - 1].name = getName(i, f.context);
351 }
352 if (f.location.isSet() || f.location.file.length() > 0)
353 stack_trace.push_back(TraceFrame(f.location));
354 }
355 }
356 return RuntimeError(stack_trace, msg);
357 }
358
359 /** New (non-call) frame. */
360 template <class... Args>
newFrame(Args...args)361 void newFrame(Args... args)
362 {
363 stack.emplace_back(args...);
364 }
365
366 /** If there is a tailstrict annotated frame followed by some locals, pop them all. */
tailCallTrimStack(void)367 void tailCallTrimStack(void)
368 {
369 for (int i = stack.size() - 1; i >= 0; --i) {
370 switch (stack[i].kind) {
371 case FRAME_CALL: {
372 if (!stack[i].tailCall || stack[i].thunks.size() > 0) {
373 return;
374 }
375 // Remove all stack frames including this one.
376 while (stack.size() > unsigned(i))
377 stack.pop_back();
378 calls--;
379 return;
380 } break;
381
382 case FRAME_LOCAL: break;
383
384 default: return;
385 }
386 }
387 }
388
389 /** New call frame. */
newCall(const LocationRange & loc,HeapEntity * context,HeapObject * self,unsigned offset,const BindingFrame & up_values)390 void newCall(const LocationRange &loc, HeapEntity *context, HeapObject *self, unsigned offset,
391 const BindingFrame &up_values)
392 {
393 tailCallTrimStack();
394 if (calls >= limit) {
395 throw makeError(loc, "max stack frames exceeded.");
396 }
397 stack.emplace_back(FRAME_CALL, loc);
398 calls++;
399 top().context = context;
400 top().self = self;
401 top().offset = offset;
402 top().bindings = up_values;
403 top().tailCall = false;
404
405 #ifndef NDEBUG
406 for (const auto &bind : up_values) {
407 if (bind.second == nullptr) {
408 std::cerr << "INTERNAL ERROR: No binding for variable "
409 << encode_utf8(bind.first->name) << std::endl;
410 std::abort();
411 }
412 }
413 #endif
414 }
415
416 /** Look up the stack to find the self binding. */
getSelfBinding(HeapObject * & self,unsigned & offset)417 void getSelfBinding(HeapObject *&self, unsigned &offset)
418 {
419 self = nullptr;
420 offset = 0;
421 for (int i = stack.size() - 1; i >= 0; --i) {
422 if (stack[i].isCall()) {
423 self = stack[i].self;
424 offset = stack[i].offset;
425 return;
426 }
427 }
428 }
429
430 /** Look up the stack to see if we're running assertions for this object. */
alreadyExecutingInvariants(HeapObject * self)431 bool alreadyExecutingInvariants(HeapObject *self)
432 {
433 for (int i = stack.size() - 1; i >= 0; --i) {
434 if (stack[i].kind == FRAME_INVARIANTS) {
435 if (stack[i].self == self)
436 return true;
437 }
438 }
439 return false;
440 }
441 };
442
443 /** Typedef to save some typing. */
444 typedef std::map<std::string, VmExt> ExtMap;
445
446 /** Typedef to save some typing. */
447 typedef std::map<std::string, std::string> StrMap;
448
449 class Interpreter;
450
451 typedef const AST *(Interpreter::*BuiltinFunc)(const LocationRange &loc,
452 const std::vector<Value> &args);
453
454 /** Holds the intermediate state during execution and implements the necessary functions to
455 * implement the semantics of the language.
456 *
457 * The garbage collector used is a simple stop-the-world mark and sweep collector. It runs upon
458 * memory allocation if the heap is large enough and has grown enough since the last collection.
459 * All reachable entities have their mark field incremented. Then all entities with the old
460 * mark are removed from the heap.
461 */
462 class Interpreter {
463 /** The heap. */
464 Heap heap;
465
466 /** The value last computed. */
467 Value scratch;
468
469 /** The stack. */
470 Stack stack;
471
472 /** Used to create ASTs if needed.
473 *
474 * This is used at import time, and in a few other cases.
475 */
476 Allocator *alloc;
477
478 /** Used to "name" thunks created to cache imports. */
479 const Identifier *idImport;
480
481 /** Used to "name" thunks created on the inside of an array. */
482 const Identifier *idArrayElement;
483
484 /** Used to "name" thunks created to execute invariants. */
485 const Identifier *idInvariant;
486
487 /** Placehodler name for internal AST. */
488 const Identifier *idInternal;
489
490 /** Used to "name" thunks created to convert JSON to Jsonnet objects. */
491 const Identifier *idJsonObjVar;
492
493 const Identifier *idEmpty;
494
495 /** Used to refer to idJsonObjVar. */
496 const AST *jsonObjVar;
497
498 /* Standard Library AST */
499 const DesugaredObject *stdlibAST;
500 HeapObject *stdObject;
501
502 struct ImportCacheValue {
503 std::string foundHere;
504 std::string content;
505 /** Thunk to store cached result of execution.
506 *
507 * Null if this file was only ever successfully imported with importstr.
508 */
509 HeapThunk *thunk;
510 };
511
512 /** Cache for imported Jsonnet files. */
513 std::map<std::pair<std::string, UString>, ImportCacheValue *> cachedImports;
514
515 /** External variables for std.extVar. */
516 ExtMap externalVars;
517
518 /** The callback used for loading imported files. */
519 VmNativeCallbackMap nativeCallbacks;
520
521 /** The callback used for loading imported files. */
522 JsonnetImportCallback *importCallback;
523
524 /** User context pointer for the import callback. */
525 void *importCallbackContext;
526
527 /** Builtin functions by name. */
528 typedef std::map<std::string, BuiltinFunc> BuiltinMap;
529 BuiltinMap builtins;
530
531 /** Source values by name. Source values are values (usually functions)
532 * implemented as Jsonnet source which we use internally in the interpreter.
533 * In a sense they are the opposite of builtins. */
534 typedef std::map<std::string, HeapThunk *> SourceFuncMap;
535 SourceFuncMap sourceVals;
536 /* Just for memory management. */
537 std::vector<std::unique_ptr<Identifier>> sourceFuncIds;
538
makeError(const LocationRange & loc,const std::string & msg)539 RuntimeError makeError(const LocationRange &loc, const std::string &msg)
540 {
541 return stack.makeError(loc, msg);
542 }
543
544 /** Create an object on the heap, maybe collect garbage.
545 * \param T Something under HeapEntity
546 * \returns The new object
547 */
548 template <class T, class... Args>
549 T *makeHeap(Args &&... args)
550 {
551 T *r = heap.makeEntity<T, Args...>(std::forward<Args>(args)...);
552 if (heap.checkHeap()) { // Do a GC cycle?
553 // Avoid the object we just made being collected.
554 heap.markFrom(r);
555
556 // Mark from the stack.
557 stack.mark(heap);
558
559 // Mark from the scratch register
560 heap.markFrom(scratch);
561
562 // Mark from cached imports
563 for (const auto &pair : cachedImports) {
564 HeapThunk *thunk = pair.second->thunk;
565 if (thunk != nullptr)
566 heap.markFrom(thunk);
567 }
568
569 for (const auto &sourceVal : sourceVals) {
570 heap.markFrom(sourceVal.second);
571 }
572
573 // Delete unreachable objects.
574 heap.sweep();
575 }
576 return r;
577 }
578
makeBoolean(bool v)579 Value makeBoolean(bool v)
580 {
581 Value r;
582 r.t = Value::BOOLEAN;
583 r.v.b = v;
584 return r;
585 }
586
makeNumber(double v)587 Value makeNumber(double v)
588 {
589 Value r;
590 r.t = Value::NUMBER;
591 r.v.d = v;
592 return r;
593 }
594
makeNumberCheck(const LocationRange & loc,double v)595 Value makeNumberCheck(const LocationRange &loc, double v)
596 {
597 if (std::isnan(v)) {
598 throw makeError(loc, "not a number");
599 }
600 if (std::isinf(v)) {
601 throw makeError(loc, "overflow");
602 }
603 return makeNumber(v);
604 }
605
makeNull(void)606 Value makeNull(void)
607 {
608 Value r;
609 r.t = Value::NULL_TYPE;
610 return r;
611 }
612
makeArray(const std::vector<HeapThunk * > & v)613 Value makeArray(const std::vector<HeapThunk *> &v)
614 {
615 Value r;
616 r.t = Value::ARRAY;
617 r.v.h = makeHeap<HeapArray>(v);
618 return r;
619 }
620
makeClosure(const BindingFrame & env,HeapObject * self,unsigned offset,const HeapClosure::Params & params,AST * body)621 Value makeClosure(const BindingFrame &env, HeapObject *self, unsigned offset,
622 const HeapClosure::Params ¶ms, AST *body)
623 {
624 Value r;
625 r.t = Value::FUNCTION;
626 r.v.h = makeHeap<HeapClosure>(env, self, offset, params, body, "");
627 return r;
628 }
629
makeNativeBuiltin(const std::string & name,const std::vector<std::string> & params)630 Value makeNativeBuiltin(const std::string &name, const std::vector<std::string> ¶ms)
631 {
632 HeapClosure::Params hc_params;
633 for (const auto &p : params) {
634 hc_params.emplace_back(alloc->makeIdentifier(decode_utf8(p)), nullptr);
635 }
636 return makeBuiltin(name, hc_params);
637 }
638
makeBuiltin(const std::string & name,const HeapClosure::Params & params)639 Value makeBuiltin(const std::string &name, const HeapClosure::Params ¶ms)
640 {
641 AST *body = nullptr;
642 Value r;
643 r.t = Value::FUNCTION;
644 r.v.h = makeHeap<HeapClosure>(BindingFrame(), nullptr, 0, params, body, name);
645 return r;
646 }
647
648 template <class T, class... Args>
makeObject(Args...args)649 Value makeObject(Args... args)
650 {
651 Value r;
652 r.t = Value::OBJECT;
653 r.v.h = makeHeap<T>(args...);
654 return r;
655 }
656
makeString(const UString & v)657 Value makeString(const UString &v)
658 {
659 Value r;
660 r.t = Value::STRING;
661 r.v.h = makeHeap<HeapString>(v);
662 return r;
663 }
664
665 /** Auxiliary function of objectIndex.
666 *
667 * Traverse the object's tree from right to left, looking for an object
668 * with the given field. Call with offset initially set to 0.
669 *
670 * \param f The field we're looking for.
671 * \param start_from Step over this many leaves first.
672 * \param counter Return the level of "super" that contained the field.
673 * \returns The first object with the field, or nullptr if it could not be found.
674 */
findObject(const Identifier * f,HeapObject * curr,unsigned start_from,unsigned & counter)675 HeapLeafObject *findObject(const Identifier *f, HeapObject *curr, unsigned start_from,
676 unsigned &counter)
677 {
678 if (auto *ext = dynamic_cast<HeapExtendedObject *>(curr)) {
679 auto *r = findObject(f, ext->right, start_from, counter);
680 if (r)
681 return r;
682 auto *l = findObject(f, ext->left, start_from, counter);
683 if (l)
684 return l;
685 } else {
686 if (counter >= start_from) {
687 if (auto *simp = dynamic_cast<HeapSimpleObject *>(curr)) {
688 auto it = simp->fields.find(f);
689 if (it != simp->fields.end()) {
690 return simp;
691 }
692 } else if (auto *comp = dynamic_cast<HeapComprehensionObject *>(curr)) {
693 auto it = comp->compValues.find(f);
694 if (it != comp->compValues.end()) {
695 return comp;
696 }
697 }
698 }
699 counter++;
700 }
701 return nullptr;
702 }
703
704 typedef std::map<const Identifier *, ObjectField::Hide> IdHideMap;
705
706 /** Auxiliary function.
707 */
objectFieldsAux(const HeapObject * obj_)708 IdHideMap objectFieldsAux(const HeapObject *obj_)
709 {
710 IdHideMap r;
711 if (auto *obj = dynamic_cast<const HeapSimpleObject *>(obj_)) {
712 for (const auto &f : obj->fields) {
713 r[f.first] = f.second.hide;
714 }
715
716 } else if (auto *obj = dynamic_cast<const HeapExtendedObject *>(obj_)) {
717 r = objectFieldsAux(obj->right);
718 for (const auto &pair : objectFieldsAux(obj->left)) {
719 auto it = r.find(pair.first);
720 if (it == r.end()) {
721 // First time it is seen
722 r[pair.first] = pair.second;
723 } else if (it->second == ObjectField::INHERIT) {
724 // Seen before, but with inherited visibility so use new visibility
725 r[pair.first] = pair.second;
726 }
727 }
728
729 } else if (auto *obj = dynamic_cast<const HeapComprehensionObject *>(obj_)) {
730 for (const auto &f : obj->compValues)
731 r[f.first] = ObjectField::VISIBLE;
732 }
733 return r;
734 }
735
736 /** Auxiliary function.
737 */
objectFields(const HeapObject * obj_,bool manifesting)738 std::set<const Identifier *> objectFields(const HeapObject *obj_, bool manifesting)
739 {
740 std::set<const Identifier *> r;
741 for (const auto &pair : objectFieldsAux(obj_)) {
742 if (!manifesting || pair.second != ObjectField::HIDDEN)
743 r.insert(pair.first);
744 }
745 return r;
746 }
747
748 /** Import another Jsonnet file.
749 *
750 * If the file has already been imported, then use that version. This maintains
751 * referential transparency in the case of writes to disk during execution. The
752 * cache holds a thunk in order to cache the resulting value of execution.
753 *
754 * \param loc Location of the import statement.
755 * \param file Path to the filename.
756 */
import(const LocationRange & loc,const LiteralString * file)757 HeapThunk *import(const LocationRange &loc, const LiteralString *file)
758 {
759 ImportCacheValue *input = importString(loc, file);
760 if (input->thunk == nullptr) {
761 Tokens tokens = jsonnet_lex(input->foundHere, input->content.c_str());
762 AST *expr = jsonnet_parse(alloc, tokens);
763 jsonnet_desugar(alloc, expr, nullptr);
764 jsonnet_static_analysis(expr);
765 // If no errors then populate cache.
766 auto *thunk = makeHeap<HeapThunk>(idImport, nullptr, 0, expr);
767 input->thunk = thunk;
768 }
769 return input->thunk;
770 }
771
772 /** Import a file as a string.
773 *
774 * If the file has already been imported, then use that version. This maintains
775 * referential transparency in the case of writes to disk during execution.
776 *
777 * \param loc Location of the import statement.
778 * \param file Path to the filename.
779 * \param found_here If non-null, used to store the actual path of the file
780 */
importString(const LocationRange & loc,const LiteralString * file)781 ImportCacheValue *importString(const LocationRange &loc, const LiteralString *file)
782 {
783 std::string dir = dir_name(loc.file);
784
785 const UString &path = file->value;
786
787 std::pair<std::string, UString> key(dir, path);
788 ImportCacheValue *cached_value = cachedImports[key];
789 if (cached_value != nullptr)
790 return cached_value;
791
792 int success = 0;
793 char *found_here_cptr;
794 char *content = importCallback(importCallbackContext,
795 dir.c_str(),
796 encode_utf8(path).c_str(),
797 &found_here_cptr,
798 &success);
799
800 std::string input(content);
801 ::free(content);
802
803 if (!success) {
804 std::string epath = encode_utf8(jsonnet_string_escape(path, false));
805 std::string msg = "couldn't open import \"" + epath + "\": ";
806 msg += input;
807 throw makeError(loc, msg);
808 }
809
810 auto *input_ptr = new ImportCacheValue();
811 input_ptr->foundHere = found_here_cptr;
812 input_ptr->content = input;
813 input_ptr->thunk = nullptr; // May be filled in later by import().
814 ::free(found_here_cptr);
815 cachedImports[key] = input_ptr;
816 return input_ptr;
817 }
818
819 /** Capture the required variables from the environment. */
capture(const std::vector<const Identifier * > & free_vars)820 BindingFrame capture(const std::vector<const Identifier *> &free_vars)
821 {
822 BindingFrame env;
823 for (auto fv : free_vars) {
824 auto *th = stack.lookUpVar(fv);
825 env[fv] = th;
826 }
827 return env;
828 }
829
830 /** Count the number of leaves in the tree.
831 *
832 * \param obj The root of the tree.
833 * \returns The number of leaves.
834 */
countLeaves(HeapObject * obj)835 unsigned countLeaves(HeapObject *obj)
836 {
837 if (auto *ext = dynamic_cast<HeapExtendedObject *>(obj)) {
838 return countLeaves(ext->left) + countLeaves(ext->right);
839 } else {
840 // Must be a HeapLeafObject.
841 return 1;
842 }
843 }
844
prepareSourceValThunks()845 void prepareSourceValThunks() {
846 for (const auto &field : stdlibAST->fields) {
847 AST *nameAST = field.name;
848 if (nameAST->type != AST_LITERAL_STRING) {
849 // Skip any fields without a known name.
850 continue;
851 }
852 UString name = dynamic_cast<LiteralString *>(nameAST)->value;
853
854 sourceFuncIds.emplace_back(new Identifier(name));
855 auto *th = makeHeap<HeapThunk>(sourceFuncIds.back().get(), stdObject, 0, field.body);
856 sourceVals[encode_utf8(name)] = th;
857 }
858 }
859
860 public:
861 /** Create a new interpreter.
862 *
863 * \param loc The location range of the file to be executed.
864 */
Interpreter(Allocator * alloc,const ExtMap & ext_vars,unsigned max_stack,double gc_min_objects,double gc_growth_trigger,const VmNativeCallbackMap & native_callbacks,JsonnetImportCallback * import_callback,void * import_callback_context)865 Interpreter(Allocator *alloc, const ExtMap &ext_vars, unsigned max_stack, double gc_min_objects,
866 double gc_growth_trigger, const VmNativeCallbackMap &native_callbacks,
867 JsonnetImportCallback *import_callback, void *import_callback_context)
868
869 : heap(gc_min_objects, gc_growth_trigger),
870 stack(max_stack),
871 alloc(alloc),
872 idImport(alloc->makeIdentifier(U"import")),
873 idArrayElement(alloc->makeIdentifier(U"array_element")),
874 idInvariant(alloc->makeIdentifier(U"object_assert")),
875 idInternal(alloc->makeIdentifier(U"__internal__")),
876 idJsonObjVar(alloc->makeIdentifier(U"_")),
877 idEmpty(alloc->makeIdentifier(U"")),
878 jsonObjVar(alloc->make<Var>(LocationRange(), Fodder{}, idJsonObjVar)),
879 externalVars(ext_vars),
880 nativeCallbacks(native_callbacks),
881 importCallback(import_callback),
882 importCallbackContext(import_callback_context)
883 {
884 scratch = makeNull();
885 builtins["makeArray"] = &Interpreter::builtinMakeArray;
886 builtins["pow"] = &Interpreter::builtinPow;
887 builtins["floor"] = &Interpreter::builtinFloor;
888 builtins["ceil"] = &Interpreter::builtinCeil;
889 builtins["sqrt"] = &Interpreter::builtinSqrt;
890 builtins["sin"] = &Interpreter::builtinSin;
891 builtins["cos"] = &Interpreter::builtinCos;
892 builtins["tan"] = &Interpreter::builtinTan;
893 builtins["asin"] = &Interpreter::builtinAsin;
894 builtins["acos"] = &Interpreter::builtinAcos;
895 builtins["atan"] = &Interpreter::builtinAtan;
896 builtins["type"] = &Interpreter::builtinType;
897 builtins["filter"] = &Interpreter::builtinFilter;
898 builtins["objectHasEx"] = &Interpreter::builtinObjectHasEx;
899 builtins["length"] = &Interpreter::builtinLength;
900 builtins["objectFieldsEx"] = &Interpreter::builtinObjectFieldsEx;
901 builtins["codepoint"] = &Interpreter::builtinCodepoint;
902 builtins["char"] = &Interpreter::builtinChar;
903 builtins["log"] = &Interpreter::builtinLog;
904 builtins["exp"] = &Interpreter::builtinExp;
905 builtins["mantissa"] = &Interpreter::builtinMantissa;
906 builtins["exponent"] = &Interpreter::builtinExponent;
907 builtins["modulo"] = &Interpreter::builtinModulo;
908 builtins["extVar"] = &Interpreter::builtinExtVar;
909 builtins["primitiveEquals"] = &Interpreter::builtinPrimitiveEquals;
910 builtins["native"] = &Interpreter::builtinNative;
911 builtins["md5"] = &Interpreter::builtinMd5;
912 builtins["trace"] = &Interpreter::builtinTrace;
913 builtins["splitLimit"] = &Interpreter::builtinSplitLimit;
914 builtins["substr"] = &Interpreter::builtinSubstr;
915 builtins["range"] = &Interpreter::builtinRange;
916 builtins["strReplace"] = &Interpreter::builtinStrReplace;
917 builtins["asciiLower"] = &Interpreter::builtinAsciiLower;
918 builtins["asciiUpper"] = &Interpreter::builtinAsciiUpper;
919 builtins["join"] = &Interpreter::builtinJoin;
920 builtins["parseJson"] = &Interpreter::builtinParseJson;
921 builtins["encodeUTF8"] = &Interpreter::builtinEncodeUTF8;
922 builtins["decodeUTF8"] = &Interpreter::builtinDecodeUTF8;
923
924 DesugaredObject *stdlib = makeStdlibAST(alloc, "__internal__");
925 jsonnet_static_analysis(stdlib);
926 stdlibAST = stdlib; // stdlibAST is const, so we need to do analysis before this assignment
927 auto stdThunk = makeHeap<HeapThunk>(nullptr, nullptr, 0, static_cast<const AST*>(stdlibAST));
928 stack.newCall(stdThunk->body->location, stdThunk, stdThunk->self, stdThunk->offset, stdThunk->upValues);
929 evaluate(stdThunk->body, 0);
930 stdObject = dynamic_cast<HeapObject*>(scratch.v.h);
931 prepareSourceValThunks();
932 }
933
934
935 /** Clean up the heap, stack, stash, and builtin function ASTs. */
~Interpreter()936 ~Interpreter()
937 {
938 for (const auto &pair : cachedImports) {
939 delete pair.second;
940 }
941 }
942
getScratchRegister(void)943 const Value &getScratchRegister(void)
944 {
945 return scratch;
946 }
947
setScratchRegister(const Value & v)948 void setScratchRegister(const Value &v)
949 {
950 scratch = v;
951 }
952
953 /** Raise an error if the arguments aren't the expected types. */
validateBuiltinArgs(const LocationRange & loc,const std::string & name,const std::vector<Value> & args,const std::vector<Value::Type> params)954 void validateBuiltinArgs(const LocationRange &loc, const std::string &name,
955 const std::vector<Value> &args, const std::vector<Value::Type> params)
956 {
957 if (args.size() == params.size()) {
958 for (unsigned i = 0; i < args.size(); ++i) {
959 if (args[i].t != params[i])
960 goto bad;
961 }
962 return;
963 }
964 bad:;
965 std::stringstream ss;
966 ss << "Builtin function " + name + " expected (";
967 const char *prefix = "";
968 for (auto p : params) {
969 ss << prefix << type_str(p);
970 prefix = ", ";
971 }
972 ss << ") but got (";
973 prefix = "";
974 for (auto a : args) {
975 ss << prefix << type_str(a);
976 prefix = ", ";
977 }
978 ss << ")";
979 throw makeError(loc, ss.str());
980 }
981
builtinMakeArray(const LocationRange & loc,const std::vector<Value> & args)982 const AST *builtinMakeArray(const LocationRange &loc, const std::vector<Value> &args)
983 {
984 Frame &f = stack.top();
985 validateBuiltinArgs(loc, "makeArray", args, {Value::NUMBER, Value::FUNCTION});
986 long sz = long(args[0].v.d);
987 if (sz < 0) {
988 std::stringstream ss;
989 ss << "makeArray requires size >= 0, got " << sz;
990 throw makeError(loc, ss.str());
991 }
992 auto *func = static_cast<const HeapClosure *>(args[1].v.h);
993 std::vector<HeapThunk *> elements;
994 if (func->params.size() != 1) {
995 std::stringstream ss;
996 ss << "makeArray function must take 1 param, got: " << func->params.size();
997 throw makeError(loc, ss.str());
998 }
999 elements.resize(sz);
1000 for (long i = 0; i < sz; ++i) {
1001 auto *th = makeHeap<HeapThunk>(idArrayElement, func->self, func->offset, func->body);
1002 // The next line stops the new thunks from being GCed.
1003 f.thunks.push_back(th);
1004 th->upValues = func->upValues;
1005
1006 auto *el = makeHeap<HeapThunk>(func->params[0].id, nullptr, 0, nullptr);
1007 el->fill(makeNumber(i)); // i guaranteed not to be inf/NaN
1008 th->upValues[func->params[0].id] = el;
1009 elements[i] = th;
1010 }
1011 scratch = makeArray(elements);
1012 return nullptr;
1013 }
1014
builtinPow(const LocationRange & loc,const std::vector<Value> & args)1015 const AST *builtinPow(const LocationRange &loc, const std::vector<Value> &args)
1016 {
1017 validateBuiltinArgs(loc, "pow", args, {Value::NUMBER, Value::NUMBER});
1018 scratch = makeNumberCheck(loc, std::pow(args[0].v.d, args[1].v.d));
1019 return nullptr;
1020 }
1021
builtinFloor(const LocationRange & loc,const std::vector<Value> & args)1022 const AST *builtinFloor(const LocationRange &loc, const std::vector<Value> &args)
1023 {
1024 validateBuiltinArgs(loc, "floor", args, {Value::NUMBER});
1025 scratch = makeNumberCheck(loc, std::floor(args[0].v.d));
1026 return nullptr;
1027 }
1028
builtinCeil(const LocationRange & loc,const std::vector<Value> & args)1029 const AST *builtinCeil(const LocationRange &loc, const std::vector<Value> &args)
1030 {
1031 validateBuiltinArgs(loc, "ceil", args, {Value::NUMBER});
1032 scratch = makeNumberCheck(loc, std::ceil(args[0].v.d));
1033 return nullptr;
1034 }
1035
builtinSqrt(const LocationRange & loc,const std::vector<Value> & args)1036 const AST *builtinSqrt(const LocationRange &loc, const std::vector<Value> &args)
1037 {
1038 validateBuiltinArgs(loc, "sqrt", args, {Value::NUMBER});
1039 scratch = makeNumberCheck(loc, std::sqrt(args[0].v.d));
1040 return nullptr;
1041 }
1042
builtinSin(const LocationRange & loc,const std::vector<Value> & args)1043 const AST *builtinSin(const LocationRange &loc, const std::vector<Value> &args)
1044 {
1045 validateBuiltinArgs(loc, "sin", args, {Value::NUMBER});
1046 scratch = makeNumberCheck(loc, std::sin(args[0].v.d));
1047 return nullptr;
1048 }
1049
builtinCos(const LocationRange & loc,const std::vector<Value> & args)1050 const AST *builtinCos(const LocationRange &loc, const std::vector<Value> &args)
1051 {
1052 validateBuiltinArgs(loc, "cos", args, {Value::NUMBER});
1053 scratch = makeNumberCheck(loc, std::cos(args[0].v.d));
1054 return nullptr;
1055 }
1056
builtinTan(const LocationRange & loc,const std::vector<Value> & args)1057 const AST *builtinTan(const LocationRange &loc, const std::vector<Value> &args)
1058 {
1059 validateBuiltinArgs(loc, "tan", args, {Value::NUMBER});
1060 scratch = makeNumberCheck(loc, std::tan(args[0].v.d));
1061 return nullptr;
1062 }
1063
builtinAsin(const LocationRange & loc,const std::vector<Value> & args)1064 const AST *builtinAsin(const LocationRange &loc, const std::vector<Value> &args)
1065 {
1066 validateBuiltinArgs(loc, "asin", args, {Value::NUMBER});
1067 scratch = makeNumberCheck(loc, std::asin(args[0].v.d));
1068 return nullptr;
1069 }
1070
builtinAcos(const LocationRange & loc,const std::vector<Value> & args)1071 const AST *builtinAcos(const LocationRange &loc, const std::vector<Value> &args)
1072 {
1073 validateBuiltinArgs(loc, "acos", args, {Value::NUMBER});
1074 scratch = makeNumberCheck(loc, std::acos(args[0].v.d));
1075 return nullptr;
1076 }
1077
builtinAtan(const LocationRange & loc,const std::vector<Value> & args)1078 const AST *builtinAtan(const LocationRange &loc, const std::vector<Value> &args)
1079 {
1080 validateBuiltinArgs(loc, "atan", args, {Value::NUMBER});
1081 scratch = makeNumberCheck(loc, std::atan(args[0].v.d));
1082 return nullptr;
1083 }
1084
builtinType(const LocationRange &,const std::vector<Value> & args)1085 const AST *builtinType(const LocationRange &, const std::vector<Value> &args)
1086 {
1087 switch (args[0].t) {
1088 case Value::NULL_TYPE: scratch = makeString(U"null"); return nullptr;
1089
1090 case Value::BOOLEAN: scratch = makeString(U"boolean"); return nullptr;
1091
1092 case Value::NUMBER: scratch = makeString(U"number"); return nullptr;
1093
1094 case Value::ARRAY: scratch = makeString(U"array"); return nullptr;
1095
1096 case Value::FUNCTION: scratch = makeString(U"function"); return nullptr;
1097
1098 case Value::OBJECT: scratch = makeString(U"object"); return nullptr;
1099
1100 case Value::STRING: scratch = makeString(U"string"); return nullptr;
1101 }
1102 return nullptr; // Quiet, compiler.
1103 }
1104
builtinFilter(const LocationRange & loc,const std::vector<Value> & args)1105 const AST *builtinFilter(const LocationRange &loc, const std::vector<Value> &args)
1106 {
1107 Frame &f = stack.top();
1108 validateBuiltinArgs(loc, "filter", args, {Value::FUNCTION, Value::ARRAY});
1109 auto *func = static_cast<HeapClosure *>(args[0].v.h);
1110 auto *arr = static_cast<HeapArray *>(args[1].v.h);
1111 if (func->params.size() != 1) {
1112 throw makeError(loc, "filter function takes 1 parameter.");
1113 }
1114 if (arr->elements.size() == 0) {
1115 scratch = makeArray({});
1116 } else {
1117 f.kind = FRAME_BUILTIN_FILTER;
1118 f.val = args[0];
1119 f.val2 = args[1];
1120 f.thunks.clear();
1121 f.elementId = 0;
1122
1123 auto *thunk = arr->elements[f.elementId];
1124 BindingFrame bindings = func->upValues;
1125 bindings[func->params[0].id] = thunk;
1126 stack.newCall(loc, func, func->self, func->offset, bindings);
1127 return func->body;
1128 }
1129 return nullptr;
1130 }
1131
builtinObjectHasEx(const LocationRange & loc,const std::vector<Value> & args)1132 const AST *builtinObjectHasEx(const LocationRange &loc, const std::vector<Value> &args)
1133 {
1134 validateBuiltinArgs(
1135 loc, "objectHasEx", args, {Value::OBJECT, Value::STRING, Value::BOOLEAN});
1136 const auto *obj = static_cast<const HeapObject *>(args[0].v.h);
1137 const auto *str = static_cast<const HeapString *>(args[1].v.h);
1138 bool include_hidden = args[2].v.b;
1139 bool found = false;
1140 for (const auto &field : objectFields(obj, !include_hidden)) {
1141 if (field->name == str->value) {
1142 found = true;
1143 break;
1144 }
1145 }
1146 scratch = makeBoolean(found);
1147 return nullptr;
1148 }
1149
builtinLength(const LocationRange & loc,const std::vector<Value> & args)1150 const AST *builtinLength(const LocationRange &loc, const std::vector<Value> &args)
1151 {
1152 if (args.size() != 1) {
1153 throw makeError(loc, "length takes 1 parameter.");
1154 }
1155 HeapEntity *e = args[0].v.h;
1156 switch (args[0].t) {
1157 case Value::OBJECT: {
1158 auto fields = objectFields(static_cast<HeapObject *>(e), true);
1159 scratch = makeNumber(fields.size());
1160 } break;
1161
1162 case Value::ARRAY:
1163 scratch = makeNumber(static_cast<HeapArray *>(e)->elements.size());
1164 break;
1165
1166 case Value::STRING:
1167 scratch = makeNumber(static_cast<HeapString *>(e)->value.length());
1168 break;
1169
1170 case Value::FUNCTION:
1171 scratch = makeNumber(static_cast<HeapClosure *>(e)->params.size());
1172 break;
1173
1174 default:
1175 throw makeError(loc,
1176 "length operates on strings, objects, "
1177 "and arrays, got " +
1178 type_str(args[0]));
1179 }
1180 return nullptr;
1181 }
1182
builtinObjectFieldsEx(const LocationRange & loc,const std::vector<Value> & args)1183 const AST *builtinObjectFieldsEx(const LocationRange &loc, const std::vector<Value> &args)
1184 {
1185 validateBuiltinArgs(loc, "objectFieldsEx", args, {Value::OBJECT, Value::BOOLEAN});
1186 const auto *obj = static_cast<HeapObject *>(args[0].v.h);
1187 bool include_hidden = args[1].v.b;
1188 // Stash in a set first to sort them.
1189 std::set<UString> fields;
1190 for (const auto &field : objectFields(obj, !include_hidden)) {
1191 fields.insert(field->name);
1192 }
1193 scratch = makeArray({});
1194 auto &elements = static_cast<HeapArray *>(scratch.v.h)->elements;
1195 for (const auto &field : fields) {
1196 auto *th = makeHeap<HeapThunk>(idArrayElement, nullptr, 0, nullptr);
1197 elements.push_back(th);
1198 th->fill(makeString(field));
1199 }
1200 return nullptr;
1201 }
1202
builtinCodepoint(const LocationRange & loc,const std::vector<Value> & args)1203 const AST *builtinCodepoint(const LocationRange &loc, const std::vector<Value> &args)
1204 {
1205 validateBuiltinArgs(loc, "codepoint", args, {Value::STRING});
1206 const UString &str = static_cast<HeapString *>(args[0].v.h)->value;
1207 if (str.length() != 1) {
1208 std::stringstream ss;
1209 ss << "codepoint takes a string of length 1, got length " << str.length();
1210 throw makeError(loc, ss.str());
1211 }
1212 char32_t c = static_cast<HeapString *>(args[0].v.h)->value[0];
1213 scratch = makeNumber((unsigned long)(c));
1214 return nullptr;
1215 }
1216
builtinChar(const LocationRange & loc,const std::vector<Value> & args)1217 const AST *builtinChar(const LocationRange &loc, const std::vector<Value> &args)
1218 {
1219 validateBuiltinArgs(loc, "char", args, {Value::NUMBER});
1220 long l = long(args[0].v.d);
1221 if (l < 0) {
1222 std::stringstream ss;
1223 ss << "codepoints must be >= 0, got " << l;
1224 throw makeError(loc, ss.str());
1225 }
1226 if (l >= JSONNET_CODEPOINT_MAX) {
1227 std::stringstream ss;
1228 ss << "invalid unicode codepoint, got " << l;
1229 throw makeError(loc, ss.str());
1230 }
1231 char32_t c = l;
1232 scratch = makeString(UString(&c, 1));
1233 return nullptr;
1234 }
1235
builtinLog(const LocationRange & loc,const std::vector<Value> & args)1236 const AST *builtinLog(const LocationRange &loc, const std::vector<Value> &args)
1237 {
1238 validateBuiltinArgs(loc, "log", args, {Value::NUMBER});
1239 scratch = makeNumberCheck(loc, std::log(args[0].v.d));
1240 return nullptr;
1241 }
1242
builtinExp(const LocationRange & loc,const std::vector<Value> & args)1243 const AST *builtinExp(const LocationRange &loc, const std::vector<Value> &args)
1244 {
1245 validateBuiltinArgs(loc, "exp", args, {Value::NUMBER});
1246 scratch = makeNumberCheck(loc, std::exp(args[0].v.d));
1247 return nullptr;
1248 }
1249
builtinMantissa(const LocationRange & loc,const std::vector<Value> & args)1250 const AST *builtinMantissa(const LocationRange &loc, const std::vector<Value> &args)
1251 {
1252 validateBuiltinArgs(loc, "mantissa", args, {Value::NUMBER});
1253 int exp;
1254 double m = std::frexp(args[0].v.d, &exp);
1255 scratch = makeNumberCheck(loc, m);
1256 return nullptr;
1257 }
1258
builtinExponent(const LocationRange & loc,const std::vector<Value> & args)1259 const AST *builtinExponent(const LocationRange &loc, const std::vector<Value> &args)
1260 {
1261 validateBuiltinArgs(loc, "exponent", args, {Value::NUMBER});
1262 int exp;
1263 std::frexp(args[0].v.d, &exp);
1264 scratch = makeNumberCheck(loc, exp);
1265 return nullptr;
1266 }
1267
builtinModulo(const LocationRange & loc,const std::vector<Value> & args)1268 const AST *builtinModulo(const LocationRange &loc, const std::vector<Value> &args)
1269 {
1270 validateBuiltinArgs(loc, "modulo", args, {Value::NUMBER, Value::NUMBER});
1271 double a = args[0].v.d;
1272 double b = args[1].v.d;
1273 if (b == 0)
1274 throw makeError(loc, "division by zero.");
1275 scratch = makeNumberCheck(loc, std::fmod(a, b));
1276 return nullptr;
1277 }
1278
builtinExtVar(const LocationRange & loc,const std::vector<Value> & args)1279 const AST *builtinExtVar(const LocationRange &loc, const std::vector<Value> &args)
1280 {
1281 validateBuiltinArgs(loc, "extVar", args, {Value::STRING});
1282 const UString &var = static_cast<HeapString *>(args[0].v.h)->value;
1283 std::string var8 = encode_utf8(var);
1284 auto it = externalVars.find(var8);
1285 if (it == externalVars.end()) {
1286 std::string msg = "undefined external variable: " + var8;
1287 throw makeError(loc, msg);
1288 }
1289 const VmExt &ext = it->second;
1290 if (ext.isCode) {
1291 std::string filename = "<extvar:" + var8 + ">";
1292 Tokens tokens = jsonnet_lex(filename, ext.data.c_str());
1293 AST *expr = jsonnet_parse(alloc, tokens);
1294 jsonnet_desugar(alloc, expr, nullptr);
1295 jsonnet_static_analysis(expr);
1296 stack.pop();
1297 return expr;
1298 } else {
1299 scratch = makeString(decode_utf8(ext.data));
1300 return nullptr;
1301 }
1302 }
1303
builtinPrimitiveEquals(const LocationRange & loc,const std::vector<Value> & args)1304 const AST *builtinPrimitiveEquals(const LocationRange &loc, const std::vector<Value> &args)
1305 {
1306 if (args.size() != 2) {
1307 std::stringstream ss;
1308 ss << "primitiveEquals takes 2 parameters, got " << args.size();
1309 throw makeError(loc, ss.str());
1310 }
1311 if (args[0].t != args[1].t) {
1312 scratch = makeBoolean(false);
1313 return nullptr;
1314 }
1315 bool r;
1316 switch (args[0].t) {
1317 case Value::BOOLEAN: r = args[0].v.b == args[1].v.b; break;
1318
1319 case Value::NUMBER: r = args[0].v.d == args[1].v.d; break;
1320
1321 case Value::STRING:
1322 r = static_cast<HeapString *>(args[0].v.h)->value ==
1323 static_cast<HeapString *>(args[1].v.h)->value;
1324 break;
1325
1326 case Value::NULL_TYPE: r = true; break;
1327
1328 case Value::FUNCTION: throw makeError(loc, "cannot test equality of functions"); break;
1329
1330 default:
1331 throw makeError(loc,
1332 "primitiveEquals operates on primitive "
1333 "types, got " +
1334 type_str(args[0]));
1335 }
1336 scratch = makeBoolean(r);
1337 return nullptr;
1338 }
1339
builtinNative(const LocationRange & loc,const std::vector<Value> & args)1340 const AST *builtinNative(const LocationRange &loc, const std::vector<Value> &args)
1341 {
1342 validateBuiltinArgs(loc, "native", args, {Value::STRING});
1343
1344 std::string builtin_name = encode_utf8(static_cast<HeapString *>(args[0].v.h)->value);
1345
1346 VmNativeCallbackMap::const_iterator nit = nativeCallbacks.find(builtin_name);
1347 if (nit == nativeCallbacks.end()) {
1348 scratch = makeNull();
1349 } else {
1350 const VmNativeCallback &cb = nit->second;
1351 scratch = makeNativeBuiltin(builtin_name, cb.params);
1352 }
1353 return nullptr;
1354 }
1355
builtinMd5(const LocationRange & loc,const std::vector<Value> & args)1356 const AST *builtinMd5(const LocationRange &loc, const std::vector<Value> &args)
1357 {
1358 validateBuiltinArgs(loc, "md5", args, {Value::STRING});
1359
1360 std::string value = encode_utf8(static_cast<HeapString *>(args[0].v.h)->value);
1361
1362 scratch = makeString(decode_utf8(md5(value)));
1363 return nullptr;
1364 }
1365
builtinEncodeUTF8(const LocationRange & loc,const std::vector<Value> & args)1366 const AST *builtinEncodeUTF8(const LocationRange &loc, const std::vector<Value> &args)
1367 {
1368 validateBuiltinArgs(loc, "encodeUTF8", args, {Value::STRING});
1369
1370 std::string byteString = encode_utf8(static_cast<HeapString *>(args[0].v.h)->value);
1371
1372 scratch = makeArray({});
1373 auto &elements = static_cast<HeapArray *>(scratch.v.h)->elements;
1374 for (const auto c : byteString) {
1375 auto *th = makeHeap<HeapThunk>(idArrayElement, nullptr, 0, nullptr);
1376 elements.push_back(th);
1377 th->fill(makeNumber(uint8_t(c)));
1378 }
1379 return nullptr;
1380 }
1381
decodeUTF8(void)1382 const AST *decodeUTF8(void)
1383 {
1384 Frame &f = stack.top();
1385 const auto& elements = static_cast<HeapArray*>(f.val.v.h)->elements;
1386 while (f.elementId < elements.size()) {
1387 auto *th = elements[f.elementId];
1388 if (th->filled) {
1389 auto b = th->content;
1390 if (b.t != Value::NUMBER) {
1391 std::stringstream ss;
1392 ss << "Element " << f.elementId << " of the provided array was not a number";
1393 throw makeError(stack.top().location, ss.str());
1394 } else {
1395 double d = b.v.d;
1396 if (d < 0 || d > 255 || d != int(d)) {
1397 std::stringstream ss;
1398 ss << "Element " << f.elementId << " of the provided array was not an integer in range [0,255]";
1399 throw makeError(stack.top().location, ss.str());
1400 }
1401 f.bytes.push_back(uint8_t(d));
1402 }
1403 f.elementId++;
1404 } else {
1405 stack.newCall(f.location, th, th->self, th->offset, th->upValues);
1406 return th->body;
1407 }
1408 }
1409 scratch = makeString(decode_utf8(f.bytes));
1410 return nullptr;
1411 }
1412
builtinDecodeUTF8(const LocationRange & loc,const std::vector<Value> & args)1413 const AST *builtinDecodeUTF8(const LocationRange &loc, const std::vector<Value> &args)
1414 {
1415 validateBuiltinArgs(loc, "decodeUTF8", args, {Value::ARRAY});
1416
1417 Frame &f = stack.top();
1418 f.kind = FRAME_BUILTIN_DECODE_UTF8;
1419 f.val = args[0]; // arr
1420 f.bytes.clear();
1421 f.elementId = 0;
1422 return decodeUTF8();
1423 }
1424
builtinTrace(const LocationRange & loc,const std::vector<Value> & args)1425 const AST *builtinTrace(const LocationRange &loc, const std::vector<Value> &args)
1426 {
1427 if(args[0].t != Value::STRING) {
1428 std::stringstream ss;
1429 ss << "Builtin function trace expected string as first parameter but "
1430 << "got " << type_str(args[0].t);
1431 throw makeError(loc, ss.str());
1432 }
1433
1434 std::string str = encode_utf8(static_cast<HeapString *>(args[0].v.h)->value);
1435 std::cerr << "TRACE: " << loc.file << ":" << loc.begin.line << " " << str
1436 << std::endl;
1437
1438 scratch = args[1];
1439 return nullptr;
1440 }
1441
builtinSplitLimit(const LocationRange & loc,const std::vector<Value> & args)1442 const AST *builtinSplitLimit(const LocationRange &loc, const std::vector<Value> &args)
1443 {
1444 validateBuiltinArgs(loc, "splitLimit", args, {Value::STRING, Value::STRING, Value::NUMBER});
1445 const auto *str = static_cast<const HeapString *>(args[0].v.h);
1446 const auto *c = static_cast<const HeapString *>(args[1].v.h);
1447 long maxsplits = long(args[2].v.d);
1448 unsigned start = 0;
1449 unsigned test = 0;
1450 scratch = makeArray({});
1451 auto &elements = static_cast<HeapArray *>(scratch.v.h)->elements;
1452 while (test < str->value.size() && (maxsplits == -1 ||
1453 size_t(maxsplits) > elements.size())) {
1454 if (c->value[0] == str->value[test]) {
1455 auto *th = makeHeap<HeapThunk>(idArrayElement, nullptr, 0, nullptr);
1456 elements.push_back(th);
1457 th->fill(makeString(str->value.substr(start, test - start)));
1458 start = test + 1;
1459 test = start;
1460 } else {
1461 ++test;
1462 }
1463 }
1464 auto *th = makeHeap<HeapThunk>(idArrayElement, nullptr, 0, nullptr);
1465 elements.push_back(th);
1466 th->fill(makeString(str->value.substr(start)));
1467
1468 return nullptr;
1469 }
1470
builtinSubstr(const LocationRange & loc,const std::vector<Value> & args)1471 const AST *builtinSubstr(const LocationRange &loc, const std::vector<Value> &args)
1472 {
1473 validateBuiltinArgs(loc, "substr", args, {Value::STRING, Value::NUMBER, Value::NUMBER});
1474 const auto *str = static_cast<const HeapString *>(args[0].v.h);
1475 long from = long(args[1].v.d);
1476 long len = long(args[2].v.d);
1477 if (from < 0) {
1478 std::stringstream ss;
1479 ss << "substr second parameter should be greater than zero, got " << from;
1480 throw makeError(loc, ss.str());
1481 }
1482 if (len < 0) {
1483 std::stringstream ss;
1484 ss << "substr third parameter should be greater than zero, got " << len;
1485 throw makeError(loc, ss.str());
1486 }
1487 if (static_cast<unsigned long>(from) > str->value.size()) {
1488 scratch = makeString(UString());
1489 return nullptr;
1490 }
1491 if (size_t(len + from) > str->value.size()) {
1492 len = str->value.size() - from;
1493 }
1494 scratch = makeString(str->value.substr(from, len));
1495 return nullptr;
1496 }
1497
builtinRange(const LocationRange & loc,const std::vector<Value> & args)1498 const AST *builtinRange(const LocationRange &loc, const std::vector<Value> &args)
1499 {
1500 validateBuiltinArgs(loc, "range", args, {Value::NUMBER, Value::NUMBER});
1501 long from = long(args[0].v.d);
1502 long to = long(args[1].v.d);
1503 long len = to - from + 1;
1504 scratch = makeArray({});
1505 if (len > 0) {
1506 auto &elements = static_cast<HeapArray *>(scratch.v.h)->elements;
1507 for (int i = 0; i < len; ++i) {
1508 auto *th = makeHeap<HeapThunk>(idArrayElement, nullptr, 0, nullptr);
1509 elements.push_back(th);
1510 th->fill(makeNumber(from + i));
1511 }
1512 }
1513 return nullptr;
1514 }
1515
builtinStrReplace(const LocationRange & loc,const std::vector<Value> & args)1516 const AST *builtinStrReplace(const LocationRange &loc, const std::vector<Value> &args)
1517 {
1518 validateBuiltinArgs(loc, "strReplace", args, {Value::STRING, Value::STRING, Value::STRING});
1519 const auto *str = static_cast<const HeapString *>(args[0].v.h);
1520 const auto *from = static_cast<const HeapString *>(args[1].v.h);
1521 const auto *to = static_cast<const HeapString *>(args[2].v.h);
1522 if (from->value.empty()) {
1523 throw makeError(loc, "'from' string must not be zero length.");
1524 }
1525 UString new_str(str->value);
1526 UString::size_type pos = 0;
1527 while (pos < new_str.size()) {
1528 auto index = new_str.find(from->value, pos);
1529 if (index == new_str.npos) {
1530 break;
1531 }
1532 new_str.replace(index, from->value.size(), to->value);
1533 pos = index + to->value.size();
1534 }
1535 scratch = makeString(new_str);
1536 return nullptr;
1537 }
1538
builtinAsciiLower(const LocationRange & loc,const std::vector<Value> & args)1539 const AST *builtinAsciiLower(const LocationRange &loc, const std::vector<Value> &args)
1540 {
1541 validateBuiltinArgs(loc, "asciiLower", args, {Value::STRING});
1542 const auto *str = static_cast<const HeapString *>(args[0].v.h);
1543 UString new_str(str->value);
1544 for (size_t i = 0; i < new_str.size(); ++i) {
1545 if (new_str[i] >= 'A' && new_str[i] <= 'Z') {
1546 new_str[i] = new_str[i] - 'A' + 'a';
1547 }
1548 }
1549 scratch = makeString(new_str);
1550 return nullptr;
1551 }
1552
builtinAsciiUpper(const LocationRange & loc,const std::vector<Value> & args)1553 const AST *builtinAsciiUpper(const LocationRange &loc, const std::vector<Value> &args)
1554 {
1555 validateBuiltinArgs(loc, "asciiUpper", args, {Value::STRING});
1556 const auto *str = static_cast<const HeapString *>(args[0].v.h);
1557 UString new_str(str->value);
1558 for (size_t i = 0; i < new_str.size(); ++i) {
1559 if (new_str[i] >= 'a' && new_str[i] <= 'z') {
1560 new_str[i] = new_str[i] - 'a' + 'A';
1561 }
1562 }
1563 scratch = makeString(new_str);
1564 return nullptr;
1565 }
1566
builtinParseJson(const LocationRange & loc,const std::vector<Value> & args)1567 const AST *builtinParseJson(const LocationRange &loc, const std::vector<Value> &args)
1568 {
1569 validateBuiltinArgs(loc, "parseJson", args, {Value::STRING});
1570
1571 std::string value = encode_utf8(static_cast<HeapString *>(args[0].v.h)->value);
1572
1573 auto j = json::parse(value);
1574
1575 bool filled;
1576
1577 otherJsonToHeap(j, filled, scratch);
1578
1579 return nullptr;
1580 }
1581
otherJsonToHeap(const json & v,bool & filled,Value & attach)1582 void otherJsonToHeap(const json &v, bool &filled, Value &attach) {
1583 // In order to not anger the garbage collector, assign to attach immediately after
1584 // making the heap object.
1585 switch (v.type()) {
1586 case json::value_t::string:
1587 attach = makeString(decode_utf8(v.get<std::string>()));
1588 filled = true;
1589 break;
1590
1591 case json::value_t::boolean:
1592 attach = makeBoolean(v.get<bool>());
1593 filled = true;
1594 break;
1595
1596 case json::value_t::number_integer:
1597 case json::value_t::number_unsigned:
1598 case json::value_t::number_float:
1599 attach = makeNumber(v.get<double>());
1600 filled = true;
1601 break;
1602
1603 case json::value_t::null:
1604 attach = makeNull();
1605 filled = true;
1606 break;
1607
1608 case json::value_t::array:{
1609 attach = makeArray(std::vector<HeapThunk *>{});
1610 filled = true;
1611 auto *arr = static_cast<HeapArray *>(attach.v.h);
1612 for (size_t i = 0; i < v.size(); ++i) {
1613 arr->elements.push_back(makeHeap<HeapThunk>(idArrayElement, nullptr, 0, nullptr));
1614 otherJsonToHeap(v[i], arr->elements[i]->filled, arr->elements[i]->content);
1615 }
1616 } break;
1617
1618 case json::value_t::object: {
1619 attach = makeObject<HeapComprehensionObject>(
1620 BindingFrame{}, jsonObjVar, idJsonObjVar, BindingFrame{});
1621 filled = true;
1622 auto *obj = static_cast<HeapComprehensionObject *>(attach.v.h);
1623 for (auto it = v.begin(); it != v.end(); ++it) {
1624 auto *thunk = makeHeap<HeapThunk>(idJsonObjVar, nullptr, 0, nullptr);
1625 obj->compValues[alloc->makeIdentifier(decode_utf8(it.key()))] = thunk;
1626 otherJsonToHeap(it.value(), thunk->filled, thunk->content);
1627 }
1628 } break;
1629
1630 case json::value_t::discarded: {
1631 abort();
1632 }
1633 }
1634 }
1635
joinString(bool & first,UString & running,const Value & sep,unsigned idx,const Value & elt)1636 void joinString(bool &first, UString &running, const Value &sep, unsigned idx, const Value &elt)
1637 {
1638 if (elt.t == Value::NULL_TYPE) {
1639 return;
1640 }
1641 if (elt.t != Value::STRING) {
1642 std::stringstream ss;
1643 ss << "expected string but arr[" << idx << "] was " << type_str(elt);
1644 throw makeError(stack.top().location, ss.str());
1645 }
1646 if (!first) {
1647 running.append(static_cast<HeapString *>(sep.v.h)->value);
1648 }
1649 first = false;
1650 running.append(static_cast<HeapString *>(elt.v.h)->value);
1651 }
1652
joinStrings(void)1653 const AST *joinStrings(void)
1654 {
1655 Frame &f = stack.top();
1656 const auto& elements = static_cast<HeapArray*>(f.val2.v.h)->elements;
1657 while (f.elementId < elements.size()) {
1658 auto *th = elements[f.elementId];
1659 if (th->filled) {
1660 joinString(f.first, f.str, f.val, f.elementId, th->content);
1661 f.elementId++;
1662 } else {
1663 stack.newCall(f.location, th, th->self, th->offset, th->upValues);
1664 return th->body;
1665 }
1666 }
1667 scratch = makeString(f.str);
1668 return nullptr;
1669 }
1670
joinArray(bool & first,std::vector<HeapThunk * > & running,const Value & sep,unsigned idx,const Value & elt)1671 void joinArray(bool &first, std::vector<HeapThunk*> &running, const Value &sep, unsigned idx,
1672 const Value &elt)
1673 {
1674 if (elt.t == Value::NULL_TYPE) {
1675 return;
1676 }
1677 if (elt.t != Value::ARRAY) {
1678 std::stringstream ss;
1679 ss << "expected array but arr[" << idx << "] was " << type_str(elt);
1680 throw makeError(stack.top().location, ss.str());
1681 }
1682 if (!first) {
1683 auto& elts = static_cast<HeapArray *>(sep.v.h)->elements;
1684 running.insert(running.end(), elts.begin(), elts.end());
1685 }
1686 first = false;
1687 auto& elts = static_cast<HeapArray *>(elt.v.h)->elements;
1688 running.insert(running.end(), elts.begin(), elts.end());
1689 }
1690
joinArrays(void)1691 const AST *joinArrays(void)
1692 {
1693 Frame &f = stack.top();
1694 const auto& elements = static_cast<HeapArray*>(f.val2.v.h)->elements;
1695 while (f.elementId < elements.size()) {
1696 auto *th = elements[f.elementId];
1697 if (th->filled) {
1698 joinArray(f.first, f.thunks, f.val, f.elementId, th->content);
1699 f.elementId++;
1700 } else {
1701 stack.newCall(f.location, th, th->self, th->offset, th->upValues);
1702 return th->body;
1703 }
1704 }
1705 scratch = makeArray(f.thunks);
1706 return nullptr;
1707 }
1708
builtinJoin(const LocationRange & loc,const std::vector<Value> & args)1709 const AST *builtinJoin(const LocationRange &loc, const std::vector<Value> &args)
1710 {
1711 if (args[0].t != Value::ARRAY && args[0].t != Value::STRING) {
1712 std::stringstream ss;
1713 ss << "join first parameter should be string or array, got " << type_str(args[0]);
1714 throw makeError(loc, ss.str());
1715 }
1716 if (args[1].t != Value::ARRAY) {
1717 std::stringstream ss;
1718 ss << "join second parameter should be array, got " << type_str(args[1]);
1719 throw makeError(loc, ss.str());
1720 }
1721 Frame &f = stack.top();
1722 if (args[0].t == Value::STRING) {
1723 f.kind = FRAME_BUILTIN_JOIN_STRINGS;
1724 f.val = args[0]; // sep
1725 f.val2 = args[1]; // arr
1726 f.str.clear();
1727 f.first = true;
1728 f.elementId = 0;
1729 return joinStrings();
1730 } else {
1731 f.kind = FRAME_BUILTIN_JOIN_ARRAYS;
1732 f.val = args[0]; // sep
1733 f.val2 = args[1]; // arr
1734 f.thunks.clear();
1735 f.first = true;
1736 f.elementId = 0;
1737 return joinArrays();
1738 }
1739 }
1740
jsonToHeap(const std::unique_ptr<JsonnetJsonValue> & v,bool & filled,Value & attach)1741 void jsonToHeap(const std::unique_ptr<JsonnetJsonValue> &v, bool &filled, Value &attach)
1742 {
1743 // In order to not anger the garbage collector, assign to attach immediately after
1744 // making the heap object.
1745 switch (v->kind) {
1746 case JsonnetJsonValue::STRING:
1747 attach = makeString(decode_utf8(v->string));
1748 filled = true;
1749 break;
1750
1751 case JsonnetJsonValue::BOOL:
1752 attach = makeBoolean(v->number != 0.0);
1753 filled = true;
1754 break;
1755
1756 case JsonnetJsonValue::NUMBER:
1757 attach = makeNumber(v->number);
1758 filled = true;
1759 break;
1760
1761 case JsonnetJsonValue::NULL_KIND:
1762 attach = makeNull();
1763 filled = true;
1764 break;
1765
1766 case JsonnetJsonValue::ARRAY: {
1767 attach = makeArray(std::vector<HeapThunk *>{});
1768 filled = true;
1769 auto *arr = static_cast<HeapArray *>(attach.v.h);
1770 for (size_t i = 0; i < v->elements.size(); ++i) {
1771 arr->elements.push_back(
1772 makeHeap<HeapThunk>(idArrayElement, nullptr, 0, nullptr));
1773 jsonToHeap(v->elements[i], arr->elements[i]->filled, arr->elements[i]->content);
1774 }
1775 } break;
1776
1777 case JsonnetJsonValue::OBJECT: {
1778 attach = makeObject<HeapComprehensionObject>(
1779 BindingFrame{}, jsonObjVar, idJsonObjVar, BindingFrame{});
1780 filled = true;
1781 auto *obj = static_cast<HeapComprehensionObject *>(attach.v.h);
1782 for (const auto &pair : v->fields) {
1783 auto *thunk = makeHeap<HeapThunk>(idJsonObjVar, nullptr, 0, nullptr);
1784 obj->compValues[alloc->makeIdentifier(decode_utf8(pair.first))] = thunk;
1785 jsonToHeap(pair.second, thunk->filled, thunk->content);
1786 }
1787 } break;
1788 }
1789 }
1790
toString(const LocationRange & loc)1791 UString toString(const LocationRange &loc)
1792 {
1793 return manifestJson(loc, false, U"");
1794 }
1795
1796 /** Recursively collect an object's invariants.
1797 *
1798 * \param curr
1799 * \param self
1800 * \param offset
1801 * \param thunks
1802 */
objectInvariants(HeapObject * curr,HeapObject * self,unsigned & counter,std::vector<HeapThunk * > & thunks)1803 void objectInvariants(HeapObject *curr, HeapObject *self, unsigned &counter,
1804 std::vector<HeapThunk *> &thunks)
1805 {
1806 if (auto *ext = dynamic_cast<HeapExtendedObject *>(curr)) {
1807 objectInvariants(ext->right, self, counter, thunks);
1808 objectInvariants(ext->left, self, counter, thunks);
1809 } else {
1810 if (auto *simp = dynamic_cast<HeapSimpleObject *>(curr)) {
1811 for (AST *assert : simp->asserts) {
1812 auto *el_th = makeHeap<HeapThunk>(idInvariant, self, counter, assert);
1813 el_th->upValues = simp->upValues;
1814 thunks.push_back(el_th);
1815 }
1816 }
1817 counter++;
1818 }
1819 }
1820
1821 /** Index an object's field.
1822 *
1823 * \param loc Location where the e.f occured.
1824 * \param obj The target
1825 * \param f The field
1826 */
objectIndex(const LocationRange & loc,HeapObject * obj,const Identifier * f,unsigned offset)1827 const AST *objectIndex(const LocationRange &loc, HeapObject *obj, const Identifier *f,
1828 unsigned offset)
1829 {
1830 unsigned found_at = 0;
1831 HeapObject *self = obj;
1832 HeapLeafObject *found = findObject(f, obj, offset, found_at);
1833 if (found == nullptr) {
1834 throw makeError(loc, "field does not exist: " + encode_utf8(f->name));
1835 }
1836 if (auto *simp = dynamic_cast<HeapSimpleObject *>(found)) {
1837 auto it = simp->fields.find(f);
1838 const AST *body = it->second.body;
1839
1840 stack.newCall(loc, simp, self, found_at, simp->upValues);
1841 return body;
1842 } else {
1843 // If a HeapLeafObject is not HeapSimpleObject, it must be HeapComprehensionObject.
1844 auto *comp = static_cast<HeapComprehensionObject *>(found);
1845 auto it = comp->compValues.find(f);
1846 auto *th = it->second;
1847 BindingFrame binds = comp->upValues;
1848 binds[comp->id] = th;
1849 stack.newCall(loc, comp, self, found_at, binds);
1850 return comp->value;
1851 }
1852 }
1853
runInvariants(const LocationRange & loc,HeapObject * self)1854 void runInvariants(const LocationRange &loc, HeapObject *self)
1855 {
1856 if (stack.alreadyExecutingInvariants(self))
1857 return;
1858
1859 unsigned counter = 0;
1860 unsigned initial_stack_size = stack.size();
1861 stack.newFrame(FRAME_INVARIANTS, loc);
1862 std::vector<HeapThunk *> &thunks = stack.top().thunks;
1863 objectInvariants(self, self, counter, thunks);
1864 if (thunks.size() == 0) {
1865 stack.pop();
1866 return;
1867 }
1868 HeapThunk *thunk = thunks[0];
1869 stack.top().elementId = 1;
1870 stack.top().self = self;
1871 stack.newCall(loc, thunk, thunk->self, thunk->offset, thunk->upValues);
1872 evaluate(thunk->body, initial_stack_size);
1873 }
1874
1875 /** Call a sourceVal function with given arguments.
1876 *
1877 * This function requires all arguments to be positional. It also does not
1878 * support default arguments. This is intended to be used internally so,
1879 * error checking is also skipped.
1880 */
callSourceVal(const AST * ast,HeapThunk * sourceVal,std::vector<HeapThunk * > args)1881 const AST *callSourceVal(const AST *ast, HeapThunk *sourceVal, std::vector<HeapThunk*> args) {
1882 assert(sourceVal != nullptr);
1883 assert(sourceVal->filled);
1884 assert(sourceVal->content.t == Value::FUNCTION);
1885 auto *func = static_cast<HeapClosure *>(sourceVal->content.v.h);
1886 BindingFrame up_values = func->upValues;
1887 for (size_t i = 0; i < args.size(); ++i) {
1888 up_values.insert({func->params[i].id, args[i]});
1889 }
1890 stack.newCall(ast->location, func, func->self, func->offset, up_values);
1891 return func->body;
1892 }
1893
1894 /** Evaluate the given AST to a value.
1895 *
1896 * Rather than call itself recursively, this function maintains a separate stack of
1897 * partially-evaluated constructs. First, the AST is handled depending on its type. If
1898 * this cannot be completed without evaluating another AST (e.g. a sub expression) then a
1899 * frame is pushed onto the stack containing the partial state, and the code jumps back to
1900 * the beginning of this function. Once there are no more ASTs to evaluate, the code
1901 * executes the second part of the function to unwind the stack. If the stack cannot be
1902 * completely unwound without evaluating an AST then it jumps back to the beginning of the
1903 * function again. The process terminates when the AST has been processed and the stack is
1904 * the same size it was at the beginning of the call to evaluate.
1905 */
evaluate(const AST * ast_,unsigned initial_stack_size)1906 void evaluate(const AST *ast_, unsigned initial_stack_size)
1907 {
1908 recurse:
1909
1910 switch (ast_->type) {
1911 case AST_APPLY: {
1912 const auto &ast = *static_cast<const Apply *>(ast_);
1913 stack.newFrame(FRAME_APPLY_TARGET, ast_);
1914 ast_ = ast.target;
1915 goto recurse;
1916 } break;
1917
1918 case AST_ARRAY: {
1919 const auto &ast = *static_cast<const Array *>(ast_);
1920 HeapObject *self;
1921 unsigned offset;
1922 stack.getSelfBinding(self, offset);
1923 scratch = makeArray({});
1924 auto &elements = static_cast<HeapArray *>(scratch.v.h)->elements;
1925 for (const auto &el : ast.elements) {
1926 auto *el_th = makeHeap<HeapThunk>(idArrayElement, self, offset, el.expr);
1927 el_th->upValues = capture(el.expr->freeVariables);
1928 elements.push_back(el_th);
1929 }
1930 } break;
1931
1932 case AST_BINARY: {
1933 const auto &ast = *static_cast<const Binary *>(ast_);
1934 stack.newFrame(FRAME_BINARY_LEFT, ast_);
1935 ast_ = ast.left;
1936 goto recurse;
1937 } break;
1938
1939 case AST_BUILTIN_FUNCTION: {
1940 const auto &ast = *static_cast<const BuiltinFunction *>(ast_);
1941 HeapClosure::Params params;
1942 params.reserve(ast.params.size());
1943 for (const auto &p : ast.params) {
1944 // None of the builtins have default args.
1945 params.emplace_back(p, nullptr);
1946 }
1947 scratch = makeBuiltin(ast.name, params);
1948 } break;
1949
1950 case AST_CONDITIONAL: {
1951 const auto &ast = *static_cast<const Conditional *>(ast_);
1952 stack.newFrame(FRAME_IF, ast_);
1953 ast_ = ast.cond;
1954 goto recurse;
1955 } break;
1956
1957 case AST_ERROR: {
1958 const auto &ast = *static_cast<const Error *>(ast_);
1959 stack.newFrame(FRAME_ERROR, ast_);
1960 ast_ = ast.expr;
1961 goto recurse;
1962 } break;
1963
1964 case AST_FUNCTION: {
1965 const auto &ast = *static_cast<const Function *>(ast_);
1966 auto env = capture(ast.freeVariables);
1967 HeapObject *self;
1968 unsigned offset;
1969 stack.getSelfBinding(self, offset);
1970 HeapClosure::Params params;
1971 params.reserve(ast.params.size());
1972 for (const auto &p : ast.params) {
1973 params.emplace_back(p.id, p.expr);
1974 }
1975 scratch = makeClosure(env, self, offset, params, ast.body);
1976 } break;
1977
1978 case AST_IMPORT: {
1979 const auto &ast = *static_cast<const Import *>(ast_);
1980 HeapThunk *thunk = import(ast.location, ast.file);
1981 if (thunk->filled) {
1982 scratch = thunk->content;
1983 } else {
1984 stack.newCall(ast.location, thunk, thunk->self, thunk->offset, thunk->upValues);
1985 ast_ = thunk->body;
1986 goto recurse;
1987 }
1988 } break;
1989
1990 case AST_IMPORTSTR: {
1991 const auto &ast = *static_cast<const Importstr *>(ast_);
1992 const ImportCacheValue *value = importString(ast.location, ast.file);
1993 scratch = makeString(decode_utf8(value->content));
1994 } break;
1995
1996 case AST_IN_SUPER: {
1997 const auto &ast = *static_cast<const InSuper *>(ast_);
1998 stack.newFrame(FRAME_IN_SUPER_ELEMENT, ast_);
1999 ast_ = ast.element;
2000 goto recurse;
2001 } break;
2002
2003 case AST_INDEX: {
2004 const auto &ast = *static_cast<const Index *>(ast_);
2005 stack.newFrame(FRAME_INDEX_TARGET, ast_);
2006 ast_ = ast.target;
2007 goto recurse;
2008 } break;
2009
2010 case AST_LOCAL: {
2011 const auto &ast = *static_cast<const Local *>(ast_);
2012 stack.newFrame(FRAME_LOCAL, ast_);
2013 Frame &f = stack.top();
2014 // First build all the thunks and bind them.
2015 HeapObject *self;
2016 unsigned offset;
2017 stack.getSelfBinding(self, offset);
2018 for (const auto &bind : ast.binds) {
2019 // Note that these 2 lines must remain separate to avoid the GC running
2020 // when bindings has a nullptr for key bind.first.
2021 auto *th = makeHeap<HeapThunk>(bind.var, self, offset, bind.body);
2022 f.bindings[bind.var] = th;
2023 }
2024 // Now capture the environment (including the new thunks, to make cycles).
2025 for (const auto &bind : ast.binds) {
2026 auto *thunk = f.bindings[bind.var];
2027 thunk->upValues = capture(bind.body->freeVariables);
2028 }
2029 ast_ = ast.body;
2030 goto recurse;
2031 } break;
2032
2033 case AST_LITERAL_BOOLEAN: {
2034 const auto &ast = *static_cast<const LiteralBoolean *>(ast_);
2035 scratch = makeBoolean(ast.value);
2036 } break;
2037
2038 case AST_LITERAL_NUMBER: {
2039 const auto &ast = *static_cast<const LiteralNumber *>(ast_);
2040 scratch = makeNumberCheck(ast_->location, ast.value);
2041 } break;
2042
2043 case AST_LITERAL_STRING: {
2044 const auto &ast = *static_cast<const LiteralString *>(ast_);
2045 scratch = makeString(ast.value);
2046 } break;
2047
2048 case AST_LITERAL_NULL: {
2049 scratch = makeNull();
2050 } break;
2051
2052 case AST_DESUGARED_OBJECT: {
2053 const auto &ast = *static_cast<const DesugaredObject *>(ast_);
2054 if (ast.fields.empty()) {
2055 auto env = capture(ast.freeVariables);
2056 std::map<const Identifier *, HeapSimpleObject::Field> fields;
2057 scratch = makeObject<HeapSimpleObject>(env, fields, ast.asserts);
2058 } else {
2059 auto env = capture(ast.freeVariables);
2060 stack.newFrame(FRAME_OBJECT, ast_);
2061 auto fit = ast.fields.begin();
2062 stack.top().fit = fit;
2063 ast_ = fit->name;
2064 goto recurse;
2065 }
2066 } break;
2067
2068 case AST_OBJECT_COMPREHENSION_SIMPLE: {
2069 const auto &ast = *static_cast<const ObjectComprehensionSimple *>(ast_);
2070 stack.newFrame(FRAME_OBJECT_COMP_ARRAY, ast_);
2071 ast_ = ast.array;
2072 goto recurse;
2073 } break;
2074
2075 case AST_SELF: {
2076 scratch.t = Value::OBJECT;
2077 HeapObject *self;
2078 unsigned offset;
2079 stack.getSelfBinding(self, offset);
2080 scratch.v.h = self;
2081 } break;
2082
2083 case AST_SUPER_INDEX: {
2084 const auto &ast = *static_cast<const SuperIndex *>(ast_);
2085 stack.newFrame(FRAME_SUPER_INDEX, ast_);
2086 ast_ = ast.index;
2087 goto recurse;
2088 } break;
2089
2090 case AST_UNARY: {
2091 const auto &ast = *static_cast<const Unary *>(ast_);
2092 stack.newFrame(FRAME_UNARY, ast_);
2093 ast_ = ast.expr;
2094 goto recurse;
2095 } break;
2096
2097 case AST_VAR: {
2098 const auto &ast = *static_cast<const Var *>(ast_);
2099 auto *thunk = stack.lookUpVar(ast.id);
2100 if (thunk == nullptr) {
2101 std::cerr << "INTERNAL ERROR: Could not bind variable: "
2102 << encode_utf8(ast.id->name) << " at "
2103 << ast.location << std::endl;
2104 std::abort();
2105 }
2106 if (thunk->filled) {
2107 scratch = thunk->content;
2108 } else {
2109 stack.newCall(ast.location, thunk, thunk->self, thunk->offset, thunk->upValues);
2110 ast_ = thunk->body;
2111 goto recurse;
2112 }
2113 } break;
2114
2115 default:
2116 std::cerr << "INTERNAL ERROR: Unknown AST: " << ast_->type << std::endl;
2117 std::abort();
2118 }
2119
2120 // To evaluate another AST, set ast to it, then goto recurse.
2121 // To pop, exit the switch or goto popframe
2122 // To change the frame and re-enter the switch, goto replaceframe
2123 while (stack.size() > initial_stack_size) {
2124 Frame &f = stack.top();
2125 switch (f.kind) {
2126 case FRAME_APPLY_TARGET: {
2127 const auto &ast = *static_cast<const Apply *>(f.ast);
2128 if (scratch.t != Value::FUNCTION) {
2129 throw makeError(ast.location,
2130 "only functions can be called, got " + type_str(scratch));
2131 }
2132 auto *func = static_cast<HeapClosure *>(scratch.v.h);
2133
2134 std::set<const Identifier *> params_needed;
2135 for (const auto ¶m : func->params) {
2136 params_needed.insert(param.id);
2137 }
2138
2139 // Create thunks for arguments.
2140 std::vector<HeapThunk *> positional_args;
2141 BindingFrame args;
2142 bool got_named = false;
2143 for (unsigned i = 0; i < ast.args.size(); ++i) {
2144 const auto &arg = ast.args[i];
2145
2146 const Identifier *name;
2147 if (arg.id != nullptr) {
2148 got_named = true;
2149 name = arg.id;
2150 } else {
2151 if (got_named) {
2152 std::stringstream ss;
2153 ss << "internal error: got positional param after named at index "
2154 << i;
2155 throw makeError(ast.location, ss.str());
2156 }
2157 if (i >= func->params.size()) {
2158 std::stringstream ss;
2159 ss << "too many args, function has " << func->params.size()
2160 << " parameter(s)";
2161 throw makeError(ast.location, ss.str());
2162 }
2163 name = func->params[i].id;
2164 }
2165 // Special case for builtin functions -- leave identifier blank for
2166 // them in the thunk. This removes the thunk frame from the stacktrace.
2167 const Identifier *name_ = func->body == nullptr ? nullptr : name;
2168 HeapObject *self;
2169 unsigned offset;
2170 stack.getSelfBinding(self, offset);
2171 auto *thunk = makeHeap<HeapThunk>(name_, self, offset, arg.expr);
2172 thunk->upValues = capture(arg.expr->freeVariables);
2173 // While making the thunks, keep them in a frame to avoid premature garbage
2174 // collection.
2175 f.thunks.push_back(thunk);
2176 if (args.find(name) != args.end()) {
2177 std::stringstream ss;
2178 ss << "binding parameter a second time: " << encode_utf8(name->name);
2179 throw makeError(ast.location, ss.str());
2180 }
2181 args[name] = thunk;
2182 if (params_needed.find(name) == params_needed.end()) {
2183 std::stringstream ss;
2184 ss << "function has no parameter " << encode_utf8(name->name);
2185 throw makeError(ast.location, ss.str());
2186 }
2187 }
2188
2189 // For any func params for which there was no arg, create a thunk for those and
2190 // bind the default argument. Allow default thunks to see other params. If no
2191 // default argument than raise an error.
2192
2193 // Raise errors for unbound params, create thunks (but don't fill in upvalues).
2194 // This is a subset of f.thunks, so will not get garbage collected.
2195 std::vector<HeapThunk *> def_arg_thunks;
2196 for (const auto ¶m : func->params) {
2197 if (args.find(param.id) != args.end())
2198 continue;
2199 if (param.def == nullptr) {
2200 std::stringstream ss;
2201 ss << "function parameter " << encode_utf8(param.id->name)
2202 << " not bound in call.";
2203 throw makeError(ast.location, ss.str());
2204 }
2205
2206 // Special case for builtin functions -- leave identifier blank for
2207 // them in the thunk. This removes the thunk frame from the stacktrace.
2208 const Identifier *name_ = func->body == nullptr ? nullptr : param.id;
2209 auto *thunk =
2210 makeHeap<HeapThunk>(name_, func->self, func->offset, param.def);
2211 f.thunks.push_back(thunk);
2212 def_arg_thunks.push_back(thunk);
2213 args[param.id] = thunk;
2214 }
2215
2216 BindingFrame up_values = func->upValues;
2217 up_values.insert(args.begin(), args.end());
2218
2219 // Fill in upvalues
2220 for (HeapThunk *thunk : def_arg_thunks) {
2221 thunk->upValues = up_values;
2222 }
2223
2224 // Cache these, because pop will invalidate them.
2225 std::vector<HeapThunk *> thunks_copy = f.thunks;
2226
2227 const AST *f_ast = f.ast;
2228 stack.pop();
2229
2230 if (func->body == nullptr) {
2231 // Built-in function.
2232 // Give nullptr for self because noone looking at this frame will
2233 // attempt to bind to self (it's native code).
2234 stack.newFrame(FRAME_BUILTIN_FORCE_THUNKS, f_ast);
2235 stack.top().thunks = thunks_copy;
2236 stack.top().val = scratch;
2237 goto replaceframe;
2238 } else {
2239 // User defined function.
2240 stack.newCall(ast.location, func, func->self, func->offset, up_values);
2241 if (ast.tailstrict) {
2242 stack.top().tailCall = true;
2243 if (thunks_copy.size() == 0) {
2244 // No need to force thunks, proceed straight to body.
2245 ast_ = func->body;
2246 goto recurse;
2247 } else {
2248 // The check for args.size() > 0
2249 stack.top().thunks = thunks_copy;
2250 stack.top().val = scratch;
2251 goto replaceframe;
2252 }
2253 } else {
2254 ast_ = func->body;
2255 goto recurse;
2256 }
2257 }
2258 } break;
2259
2260 case FRAME_BINARY_LEFT: {
2261 const auto &ast = *static_cast<const Binary *>(f.ast);
2262 const Value &lhs = scratch;
2263 if (lhs.t == Value::BOOLEAN) {
2264 // Handle short-cut semantics
2265 switch (ast.op) {
2266 case BOP_AND: {
2267 if (!lhs.v.b) {
2268 scratch = makeBoolean(false);
2269 goto popframe;
2270 }
2271 } break;
2272
2273 case BOP_OR: {
2274 if (lhs.v.b) {
2275 scratch = makeBoolean(true);
2276 goto popframe;
2277 }
2278 } break;
2279
2280 default:;
2281 }
2282 }
2283 stack.top().kind = FRAME_BINARY_RIGHT;
2284 stack.top().val = lhs;
2285 ast_ = ast.right;
2286 goto recurse;
2287 } break;
2288
2289 case FRAME_BINARY_RIGHT: {
2290 stack.top().val2 = scratch;
2291 stack.top().kind = FRAME_BINARY_OP;
2292 }
2293 // Falls through.
2294 case FRAME_BINARY_OP: {
2295 const auto &ast = *static_cast<const Binary *>(f.ast);
2296 const Value &lhs = stack.top().val;
2297 const Value &rhs = stack.top().val2;
2298
2299 // Handle cases where the LHS and RHS are not the same type.
2300 if (lhs.t == Value::STRING || rhs.t == Value::STRING) {
2301 if (ast.op == BOP_PLUS) {
2302 // Handle co-ercions for string processing.
2303 stack.top().kind = FRAME_STRING_CONCAT;
2304 stack.top().val2 = rhs;
2305 goto replaceframe;
2306 }
2307 }
2308 switch (ast.op) {
2309 // Equality can be used when the types don't match.
2310 case BOP_MANIFEST_EQUAL:
2311 std::cerr << "INTERNAL ERROR: Equals not desugared" << std::endl;
2312 abort();
2313
2314 // Equality can be used when the types don't match.
2315 case BOP_MANIFEST_UNEQUAL:
2316 std::cerr << "INTERNAL ERROR: Notequals not desugared" << std::endl;
2317 abort();
2318
2319 // e in e
2320 case BOP_IN: {
2321 if (lhs.t != Value::STRING) {
2322 throw makeError(ast.location,
2323 "the left hand side of the 'in' operator should be "
2324 "a string, got " +
2325 type_str(lhs));
2326 }
2327 auto *field = static_cast<HeapString *>(lhs.v.h);
2328 switch (rhs.t) {
2329 case Value::OBJECT: {
2330 auto *obj = static_cast<HeapObject *>(rhs.v.h);
2331 auto *fid = alloc->makeIdentifier(field->value);
2332 unsigned unused_found_at = 0;
2333 bool in = findObject(fid, obj, 0, unused_found_at);
2334 scratch = makeBoolean(in);
2335 } break;
2336
2337 default:
2338 throw makeError(
2339 ast.location,
2340 "the right hand side of the 'in' operator should be"
2341 " an object, got " +
2342 type_str(rhs));
2343 }
2344 goto popframe;
2345 }
2346
2347 default:;
2348 }
2349 // Everything else requires matching types.
2350 if (lhs.t != rhs.t) {
2351 throw makeError(ast.location,
2352 "binary operator " + bop_string(ast.op) +
2353 " requires "
2354 "matching types, got " +
2355 type_str(lhs) + " and " + type_str(rhs) + ".");
2356 }
2357 switch (lhs.t) {
2358 case Value::ARRAY:
2359 if (ast.op == BOP_PLUS) {
2360 auto *arr_l = static_cast<HeapArray *>(lhs.v.h);
2361 auto *arr_r = static_cast<HeapArray *>(rhs.v.h);
2362 std::vector<HeapThunk *> elements;
2363 for (auto *el : arr_l->elements)
2364 elements.push_back(el);
2365 for (auto *el : arr_r->elements)
2366 elements.push_back(el);
2367 scratch = makeArray(elements);
2368 } else if (ast.op == BOP_LESS || ast.op == BOP_LESS_EQ || ast.op == BOP_GREATER || ast.op == BOP_GREATER_EQ) {
2369 HeapThunk *func;
2370 switch(ast.op) {
2371 case BOP_LESS:
2372 func = sourceVals["__array_less"];
2373 break;
2374 case BOP_LESS_EQ:
2375 func = sourceVals["__array_less_or_equal"];
2376 break;
2377 case BOP_GREATER:
2378 func = sourceVals["__array_greater"];
2379 break;
2380 case BOP_GREATER_EQ:
2381 func = sourceVals["__array_greater_or_equal"];
2382 break;
2383 default:
2384 assert(false && "impossible case");
2385 }
2386 if (!func->filled) {
2387 stack.newCall(ast.location, func, func->self, func->offset, func->upValues);
2388 ast_ = func->body;
2389 goto recurse;
2390 }
2391 auto *lhs_th = makeHeap<HeapThunk>(idInternal, f.self, f.offset, ast.left);
2392 lhs_th->fill(lhs);
2393 f.thunks.push_back(lhs_th);
2394 auto *rhs_th = makeHeap<HeapThunk>(idInternal, f.self, f.offset, ast.right);
2395 rhs_th->fill(rhs);
2396 f.thunks.push_back(rhs_th);
2397 const AST *orig_ast = ast_;
2398 stack.pop();
2399 ast_ = callSourceVal(orig_ast, func, {lhs_th, rhs_th});
2400 goto recurse;
2401 } else {
2402 throw makeError(ast.location,
2403 "binary operator " + bop_string(ast.op) +
2404 " does not operate on arrays.");
2405 }
2406 break;
2407
2408 case Value::BOOLEAN:
2409 switch (ast.op) {
2410 case BOP_AND: scratch = makeBoolean(lhs.v.b && rhs.v.b); break;
2411
2412 case BOP_OR: scratch = makeBoolean(lhs.v.b || rhs.v.b); break;
2413
2414 default:
2415 throw makeError(ast.location,
2416 "binary operator " + bop_string(ast.op) +
2417 " does not operate on booleans.");
2418 }
2419 break;
2420
2421 case Value::NUMBER:
2422 switch (ast.op) {
2423 case BOP_PLUS:
2424 scratch = makeNumberCheck(ast.location, lhs.v.d + rhs.v.d);
2425 break;
2426
2427 case BOP_MINUS:
2428 scratch = makeNumberCheck(ast.location, lhs.v.d - rhs.v.d);
2429 break;
2430
2431 case BOP_MULT:
2432 scratch = makeNumberCheck(ast.location, lhs.v.d * rhs.v.d);
2433 break;
2434
2435 case BOP_DIV:
2436 if (rhs.v.d == 0)
2437 throw makeError(ast.location, "division by zero.");
2438 scratch = makeNumberCheck(ast.location, lhs.v.d / rhs.v.d);
2439 break;
2440
2441 // No need to check doubles made from longs
2442
2443 case BOP_SHIFT_L: {
2444 if (rhs.v.d < 0)
2445 throw makeError(ast.location, "shift by negative exponent.");
2446 int64_t long_l = lhs.v.d;
2447 int64_t long_r = rhs.v.d;
2448 long_r = long_r % 64;
2449 scratch = makeNumber(long_l << long_r);
2450 } break;
2451
2452 case BOP_SHIFT_R: {
2453 if (rhs.v.d < 0)
2454 throw makeError(ast.location, "shift by negative exponent.");
2455 int64_t long_l = lhs.v.d;
2456 int64_t long_r = rhs.v.d;
2457 long_r = long_r % 64;
2458 scratch = makeNumber(long_l >> long_r);
2459 } break;
2460
2461 case BOP_BITWISE_AND: {
2462 int64_t long_l = lhs.v.d;
2463 int64_t long_r = rhs.v.d;
2464 scratch = makeNumber(long_l & long_r);
2465 } break;
2466
2467 case BOP_BITWISE_XOR: {
2468 int64_t long_l = lhs.v.d;
2469 int64_t long_r = rhs.v.d;
2470 scratch = makeNumber(long_l ^ long_r);
2471 } break;
2472
2473 case BOP_BITWISE_OR: {
2474 int64_t long_l = lhs.v.d;
2475 int64_t long_r = rhs.v.d;
2476 scratch = makeNumber(long_l | long_r);
2477 } break;
2478
2479 case BOP_LESS_EQ: scratch = makeBoolean(lhs.v.d <= rhs.v.d); break;
2480
2481 case BOP_GREATER_EQ:
2482 scratch = makeBoolean(lhs.v.d >= rhs.v.d);
2483 break;
2484
2485 case BOP_LESS: scratch = makeBoolean(lhs.v.d < rhs.v.d); break;
2486
2487 case BOP_GREATER: scratch = makeBoolean(lhs.v.d > rhs.v.d); break;
2488
2489 default:
2490 throw makeError(ast.location,
2491 "binary operator " + bop_string(ast.op) +
2492 " does not operate on numbers.");
2493 }
2494 break;
2495
2496 case Value::FUNCTION:
2497 throw makeError(ast.location,
2498 "binary operator " + bop_string(ast.op) +
2499 " does not operate on functions.");
2500
2501 case Value::NULL_TYPE:
2502 throw makeError(ast.location,
2503 "binary operator " + bop_string(ast.op) +
2504 " does not operate on null.");
2505
2506 case Value::OBJECT: {
2507 if (ast.op != BOP_PLUS) {
2508 throw makeError(ast.location,
2509 "binary operator " + bop_string(ast.op) +
2510 " does not operate on objects.");
2511 }
2512 auto *lhs_obj = static_cast<HeapObject *>(lhs.v.h);
2513 auto *rhs_obj = static_cast<HeapObject *>(rhs.v.h);
2514 scratch = makeObject<HeapExtendedObject>(lhs_obj, rhs_obj);
2515 } break;
2516
2517 case Value::STRING: {
2518 const UString &lhs_str = static_cast<HeapString *>(lhs.v.h)->value;
2519 const UString &rhs_str = static_cast<HeapString *>(rhs.v.h)->value;
2520 switch (ast.op) {
2521 case BOP_PLUS: scratch = makeString(lhs_str + rhs_str); break;
2522
2523 case BOP_LESS_EQ: scratch = makeBoolean(lhs_str <= rhs_str); break;
2524
2525 case BOP_GREATER_EQ:
2526 scratch = makeBoolean(lhs_str >= rhs_str);
2527 break;
2528
2529 case BOP_LESS: scratch = makeBoolean(lhs_str < rhs_str); break;
2530
2531 case BOP_GREATER: scratch = makeBoolean(lhs_str > rhs_str); break;
2532
2533 default:
2534 throw makeError(ast.location,
2535 "binary operator " + bop_string(ast.op) +
2536 " does not operate on strings.");
2537 }
2538 } break;
2539 }
2540 } break;
2541
2542 case FRAME_BUILTIN_FILTER: {
2543 const auto &ast = *static_cast<const Apply *>(f.ast);
2544 auto *func = static_cast<HeapClosure *>(f.val.v.h);
2545 auto *arr = static_cast<HeapArray *>(f.val2.v.h);
2546 if (scratch.t != Value::BOOLEAN) {
2547 throw makeError(
2548 ast.location,
2549 "filter function must return boolean, got: " + type_str(scratch));
2550 }
2551 if (scratch.v.b)
2552 f.thunks.push_back(arr->elements[f.elementId]);
2553 f.elementId++;
2554 // Iterate through arr, calling the function on each.
2555 if (f.elementId == arr->elements.size()) {
2556 scratch = makeArray(f.thunks);
2557 } else {
2558 auto *thunk = arr->elements[f.elementId];
2559 BindingFrame bindings = func->upValues;
2560 bindings[func->params[0].id] = thunk;
2561 stack.newCall(ast.location, func, func->self, func->offset, bindings);
2562 ast_ = func->body;
2563 goto recurse;
2564 }
2565 } break;
2566
2567 case FRAME_BUILTIN_FORCE_THUNKS: {
2568 const auto &ast = *static_cast<const Apply *>(f.ast);
2569 auto *func = static_cast<HeapClosure *>(f.val.v.h);
2570 if (f.elementId == f.thunks.size()) {
2571 // All thunks forced, now the builtin implementations.
2572 const LocationRange &loc = ast.location;
2573 const std::string &builtin_name = func->builtinName;
2574 std::vector<Value> args;
2575 for (auto *th : f.thunks) {
2576 args.push_back(th->content);
2577 }
2578 BuiltinMap::const_iterator bit = builtins.find(builtin_name);
2579 if (bit != builtins.end()) {
2580 const AST *new_ast = (this->*bit->second)(loc, args);
2581 if (new_ast != nullptr) {
2582 ast_ = new_ast;
2583 goto recurse;
2584 }
2585 break;
2586 }
2587 VmNativeCallbackMap::const_iterator nit =
2588 nativeCallbacks.find(builtin_name);
2589 // TODO(dcunnin): Support arrays.
2590 // TODO(dcunnin): Support objects.
2591 std::vector<JsonnetJsonValue> args2;
2592 for (const Value &arg : args) {
2593 switch (arg.t) {
2594 case Value::STRING:
2595 args2.emplace_back(
2596 JsonnetJsonValue::STRING,
2597 encode_utf8(static_cast<HeapString *>(arg.v.h)->value),
2598 0);
2599 break;
2600
2601 case Value::BOOLEAN:
2602 args2.emplace_back(
2603 JsonnetJsonValue::BOOL, "", arg.v.b ? 1.0 : 0.0);
2604 break;
2605
2606 case Value::NUMBER:
2607 args2.emplace_back(JsonnetJsonValue::NUMBER, "", arg.v.d);
2608 break;
2609
2610 case Value::NULL_TYPE:
2611 args2.emplace_back(JsonnetJsonValue::NULL_KIND, "", 0);
2612 break;
2613
2614 default:
2615 throw makeError(ast.location,
2616 "native extensions can only take primitives.");
2617 }
2618 }
2619 std::vector<const JsonnetJsonValue *> args3;
2620 for (size_t i = 0; i < args2.size(); ++i) {
2621 args3.push_back(&args2[i]);
2622 }
2623 if (nit == nativeCallbacks.end()) {
2624 throw makeError(ast.location,
2625 "unrecognized builtin name: " + builtin_name);
2626 }
2627 const VmNativeCallback &cb = nit->second;
2628
2629 int succ;
2630 std::unique_ptr<JsonnetJsonValue> r(cb.cb(cb.ctx, args3.data(), &succ));
2631
2632 if (succ) {
2633 bool unused;
2634 jsonToHeap(r, unused, scratch);
2635 } else {
2636 if (r->kind != JsonnetJsonValue::STRING) {
2637 throw makeError(
2638 ast.location,
2639 "native extension returned an error that was not a string.");
2640 }
2641 std::string rs = r->string;
2642 throw makeError(ast.location, rs);
2643 }
2644
2645 } else {
2646 // Not all arguments forced yet.
2647 HeapThunk *th = f.thunks[f.elementId++];
2648 if (!th->filled) {
2649 stack.newCall(ast.location, th, th->self, th->offset, th->upValues);
2650 ast_ = th->body;
2651 goto recurse;
2652 }
2653 }
2654 } break;
2655
2656 case FRAME_CALL: {
2657 if (auto *thunk = dynamic_cast<HeapThunk *>(f.context)) {
2658 // If we called a thunk, cache result.
2659 thunk->fill(scratch);
2660 } else if (auto *closure = dynamic_cast<HeapClosure *>(f.context)) {
2661 if (f.elementId < f.thunks.size()) {
2662 // If tailstrict, force thunks
2663 HeapThunk *th = f.thunks[f.elementId++];
2664 if (!th->filled) {
2665 stack.newCall(f.location, th, th->self, th->offset, th->upValues);
2666 ast_ = th->body;
2667 goto recurse;
2668 }
2669 } else if (f.thunks.size() == 0) {
2670 // Body has now been executed
2671 } else {
2672 // Execute the body
2673 f.thunks.clear();
2674 f.elementId = 0;
2675 ast_ = closure->body;
2676 goto recurse;
2677 }
2678 }
2679 // Result of call is in scratch, just pop.
2680 } break;
2681
2682 case FRAME_ERROR: {
2683 const auto &ast = *static_cast<const Error *>(f.ast);
2684 UString msg;
2685 if (scratch.t == Value::STRING) {
2686 msg = static_cast<HeapString *>(scratch.v.h)->value;
2687 } else {
2688 msg = toString(ast.location);
2689 }
2690 throw makeError(ast.location, encode_utf8(msg));
2691 } break;
2692
2693 case FRAME_IF: {
2694 const auto &ast = *static_cast<const Conditional *>(f.ast);
2695 if (scratch.t != Value::BOOLEAN) {
2696 throw makeError(
2697 ast.location,
2698 "condition must be boolean, got " + type_str(scratch) + ".");
2699 }
2700 ast_ = scratch.v.b ? ast.branchTrue : ast.branchFalse;
2701 stack.pop();
2702 goto recurse;
2703 } break;
2704
2705 case FRAME_SUPER_INDEX: {
2706 const auto &ast = *static_cast<const SuperIndex *>(f.ast);
2707 HeapObject *self;
2708 unsigned offset;
2709 stack.getSelfBinding(self, offset);
2710 offset++;
2711 if (offset >= countLeaves(self)) {
2712 throw makeError(ast.location,
2713 "attempt to use super when there is no super class.");
2714 }
2715 if (scratch.t != Value::STRING) {
2716 throw makeError(
2717 ast.location,
2718 "super index must be string, got " + type_str(scratch) + ".");
2719 }
2720
2721 const UString &index_name = static_cast<HeapString *>(scratch.v.h)->value;
2722 auto *fid = alloc->makeIdentifier(index_name);
2723 stack.pop();
2724 ast_ = objectIndex(ast.location, self, fid, offset);
2725 goto recurse;
2726 } break;
2727
2728 case FRAME_IN_SUPER_ELEMENT: {
2729 const auto &ast = *static_cast<const InSuper *>(f.ast);
2730 HeapObject *self;
2731 unsigned offset;
2732 stack.getSelfBinding(self, offset);
2733 offset++;
2734 if (scratch.t != Value::STRING) {
2735 throw makeError(ast.location,
2736 "left hand side of e in super must be string, got " +
2737 type_str(scratch) + ".");
2738 }
2739 if (offset >= countLeaves(self)) {
2740 // There is no super object.
2741 scratch = makeBoolean(false);
2742 } else {
2743 const UString &element_name = static_cast<HeapString *>(scratch.v.h)->value;
2744 auto *fid = alloc->makeIdentifier(element_name);
2745 unsigned unused_found_at = 0;
2746 bool in = findObject(fid, self, offset, unused_found_at);
2747 scratch = makeBoolean(in);
2748 }
2749 } break;
2750
2751 case FRAME_INDEX_INDEX: {
2752 const auto &ast = *static_cast<const Index *>(f.ast);
2753 const Value &target = f.val;
2754 if (target.t == Value::ARRAY) {
2755 const auto *array = static_cast<HeapArray *>(target.v.h);
2756 if (scratch.t == Value::STRING) {
2757 const UString &str = static_cast<HeapString *>(scratch.v.h)->value;
2758 throw makeError(
2759 ast.location,
2760 "attempted index an array with string \""
2761 + encode_utf8(jsonnet_string_escape(str, false)) + "\".");
2762 }
2763 if (scratch.t != Value::NUMBER) {
2764 throw makeError(
2765 ast.location,
2766 "array index must be number, got " + type_str(scratch) + ".");
2767 }
2768 double index = ::floor(scratch.v.d);
2769 long sz = array->elements.size();
2770 if (index < 0 || index >= sz) {
2771 std::stringstream ss;
2772 ss << "array bounds error: " << index << " not within [0, " << sz
2773 << ")";
2774 throw makeError(ast.location, ss.str());
2775 }
2776 if (scratch.v.d != index) {
2777 std::stringstream ss;
2778 ss << "array index was not integer: " << scratch.v.d;
2779 throw makeError(ast.location, ss.str());
2780 }
2781 // index < sz <= SIZE_T_MAX
2782 auto *thunk = array->elements[size_t(index)];
2783 if (thunk->filled) {
2784 scratch = thunk->content;
2785 } else {
2786 stack.pop();
2787 stack.newCall(
2788 ast.location, thunk, thunk->self, thunk->offset, thunk->upValues);
2789 ast_ = thunk->body;
2790 goto recurse;
2791 }
2792 } else if (target.t == Value::OBJECT) {
2793 auto *obj = static_cast<HeapObject *>(target.v.h);
2794 assert(obj != nullptr);
2795 if (scratch.t != Value::STRING) {
2796 throw makeError(
2797 ast.location,
2798 "object index must be string, got " + type_str(scratch) + ".");
2799 }
2800 const UString &index_name = static_cast<HeapString *>(scratch.v.h)->value;
2801 auto *fid = alloc->makeIdentifier(index_name);
2802 stack.pop();
2803 ast_ = objectIndex(ast.location, obj, fid, 0);
2804 goto recurse;
2805 } else if (target.t == Value::STRING) {
2806 auto *obj = static_cast<HeapString *>(target.v.h);
2807 assert(obj != nullptr);
2808 if (scratch.t != Value::NUMBER) {
2809 throw makeError(
2810 ast.location,
2811 "string index must be a number, got " + type_str(scratch) + ".");
2812 }
2813 long sz = obj->value.length();
2814 long i = (long)scratch.v.d;
2815 if (i < 0 || i >= sz) {
2816 std::stringstream ss;
2817 ss << "string bounds error: " << i << " not within [0, " << sz << ")";
2818 throw makeError(ast.location, ss.str());
2819 }
2820 char32_t ch[] = {obj->value[i], U'\0'};
2821 scratch = makeString(ch);
2822 } else {
2823 std::cerr << "INTERNAL ERROR: not object / array / string." << std::endl;
2824 abort();
2825 }
2826 } break;
2827
2828 case FRAME_INDEX_TARGET: {
2829 const auto &ast = *static_cast<const Index *>(f.ast);
2830 if (scratch.t != Value::ARRAY && scratch.t != Value::OBJECT &&
2831 scratch.t != Value::STRING) {
2832 throw makeError(ast.location,
2833 "can only index objects, strings, and arrays, got " +
2834 type_str(scratch) + ".");
2835 }
2836 f.val = scratch;
2837 f.kind = FRAME_INDEX_INDEX;
2838 if (scratch.t == Value::OBJECT) {
2839 auto *self = static_cast<HeapObject *>(scratch.v.h);
2840 if (!stack.alreadyExecutingInvariants(self)) {
2841 stack.newFrame(FRAME_INVARIANTS, ast.location);
2842 Frame &f2 = stack.top();
2843 f2.self = self;
2844 unsigned counter = 0;
2845 objectInvariants(self, self, counter, f2.thunks);
2846 if (f2.thunks.size() > 0) {
2847 auto *thunk = f2.thunks[0];
2848 f2.elementId = 1;
2849 stack.newCall(ast.location,
2850 thunk,
2851 thunk->self,
2852 thunk->offset,
2853 thunk->upValues);
2854 ast_ = thunk->body;
2855 goto recurse;
2856 }
2857 }
2858 }
2859 ast_ = ast.index;
2860 goto recurse;
2861 } break;
2862
2863 case FRAME_INVARIANTS: {
2864 if (f.elementId >= f.thunks.size()) {
2865 if (stack.size() == initial_stack_size + 1) {
2866 // Just pop, evaluate was invoked by runInvariants.
2867 break;
2868 }
2869 stack.pop();
2870 Frame &f2 = stack.top();
2871 const auto &ast = *static_cast<const Index *>(f2.ast);
2872 ast_ = ast.index;
2873 goto recurse;
2874 }
2875 auto *thunk = f.thunks[f.elementId++];
2876 stack.newCall(f.location, thunk, thunk->self, thunk->offset, thunk->upValues);
2877 ast_ = thunk->body;
2878 goto recurse;
2879 } break;
2880
2881 case FRAME_LOCAL: {
2882 // Result of execution is in scratch already.
2883 } break;
2884
2885 case FRAME_OBJECT: {
2886 const auto &ast = *static_cast<const DesugaredObject *>(f.ast);
2887 if (scratch.t != Value::NULL_TYPE) {
2888 if (scratch.t != Value::STRING) {
2889 throw makeError(ast.location, "field name was not a string.");
2890 }
2891 const auto &fname = static_cast<const HeapString *>(scratch.v.h)->value;
2892 const Identifier *fid = alloc->makeIdentifier(fname);
2893 if (f.objectFields.find(fid) != f.objectFields.end()) {
2894 std::string msg =
2895 "duplicate field name: \"" + encode_utf8(fname) + "\"";
2896 throw makeError(ast.location, msg);
2897 }
2898 f.objectFields[fid].hide = f.fit->hide;
2899 f.objectFields[fid].body = f.fit->body;
2900 }
2901 f.fit++;
2902 if (f.fit != ast.fields.end()) {
2903 ast_ = f.fit->name;
2904 goto recurse;
2905 } else {
2906 auto env = capture(ast.freeVariables);
2907 scratch = makeObject<HeapSimpleObject>(env, f.objectFields, ast.asserts);
2908 }
2909 } break;
2910
2911 case FRAME_OBJECT_COMP_ARRAY: {
2912 const auto &ast = *static_cast<const ObjectComprehensionSimple *>(f.ast);
2913 const Value &arr_v = scratch;
2914 if (scratch.t != Value::ARRAY) {
2915 throw makeError(ast.location,
2916 "object comprehension needs array, got " + type_str(arr_v));
2917 }
2918 const auto *arr = static_cast<const HeapArray *>(arr_v.v.h);
2919 if (arr->elements.size() == 0) {
2920 // Degenerate case. Just create the object now.
2921 scratch = makeObject<HeapComprehensionObject>(
2922 BindingFrame{}, ast.value, ast.id, BindingFrame{});
2923 } else {
2924 f.kind = FRAME_OBJECT_COMP_ELEMENT;
2925 f.val = scratch;
2926 f.bindings[ast.id] = arr->elements[0];
2927 f.elementId = 0;
2928 ast_ = ast.field;
2929 goto recurse;
2930 }
2931 } break;
2932
2933 case FRAME_OBJECT_COMP_ELEMENT: {
2934 const auto &ast = *static_cast<const ObjectComprehensionSimple *>(f.ast);
2935 const auto *arr = static_cast<const HeapArray *>(f.val.v.h);
2936 if (scratch.t != Value::NULL_TYPE) {
2937 if (scratch.t != Value::STRING) {
2938 std::stringstream ss;
2939 ss << "field must be string, got: " << type_str(scratch);
2940 throw makeError(ast.location, ss.str());
2941 }
2942 const auto &fname = static_cast<const HeapString *>(scratch.v.h)->value;
2943 const Identifier *fid = alloc->makeIdentifier(fname);
2944 if (f.elements.find(fid) != f.elements.end()) {
2945 throw makeError(ast.location,
2946 "duplicate field name: \"" + encode_utf8(fname) + "\"");
2947 }
2948 f.elements[fid] = arr->elements[f.elementId];
2949 }
2950 f.elementId++;
2951
2952 if (f.elementId == arr->elements.size()) {
2953 auto env = capture(ast.freeVariables);
2954 scratch =
2955 makeObject<HeapComprehensionObject>(env, ast.value, ast.id, f.elements);
2956 } else {
2957 f.bindings[ast.id] = arr->elements[f.elementId];
2958 ast_ = ast.field;
2959 goto recurse;
2960 }
2961 } break;
2962
2963 case FRAME_STRING_CONCAT: {
2964 const auto &ast = *static_cast<const Binary *>(f.ast);
2965 const Value &lhs = stack.top().val;
2966 const Value &rhs = stack.top().val2;
2967 UString output;
2968 if (lhs.t == Value::STRING) {
2969 output.append(static_cast<const HeapString *>(lhs.v.h)->value);
2970 } else {
2971 scratch = lhs;
2972 output.append(toString(ast.left->location));
2973 }
2974 if (rhs.t == Value::STRING) {
2975 output.append(static_cast<const HeapString *>(rhs.v.h)->value);
2976 } else {
2977 scratch = rhs;
2978 output.append(toString(ast.right->location));
2979 }
2980 scratch = makeString(output);
2981 } break;
2982
2983 case FRAME_UNARY: {
2984 const auto &ast = *static_cast<const Unary *>(f.ast);
2985 switch (scratch.t) {
2986 case Value::BOOLEAN:
2987 if (ast.op == UOP_NOT) {
2988 scratch = makeBoolean(!scratch.v.b);
2989 } else {
2990 throw makeError(ast.location,
2991 "unary operator " + uop_string(ast.op) +
2992 " does not operate on booleans.");
2993 }
2994 break;
2995
2996 case Value::NUMBER:
2997 switch (ast.op) {
2998 case UOP_PLUS: break;
2999
3000 case UOP_MINUS: scratch = makeNumber(-scratch.v.d); break;
3001
3002 case UOP_BITWISE_NOT:
3003 scratch = makeNumber(~(long)(scratch.v.d));
3004 break;
3005
3006 default:
3007 throw makeError(ast.location,
3008 "unary operator " + uop_string(ast.op) +
3009 " does not operate on numbers.");
3010 }
3011 break;
3012
3013 default:
3014 throw makeError(ast.location,
3015 "unary operator " + uop_string(ast.op) +
3016 " does not operate on type " + type_str(scratch));
3017 }
3018 } break;
3019
3020 case FRAME_BUILTIN_JOIN_STRINGS: {
3021 joinString(f.first, f.str, f.val, f.elementId, scratch);
3022 f.elementId++;
3023 auto *ast = joinStrings();
3024 if (ast != nullptr) {
3025 ast_ = ast;
3026 goto recurse;
3027 }
3028 } break;
3029
3030 case FRAME_BUILTIN_JOIN_ARRAYS: {
3031 joinArray(f.first, f.thunks, f.val, f.elementId, scratch);
3032 f.elementId++;
3033 auto *ast = joinArrays();
3034 if (ast != nullptr) {
3035 ast_ = ast;
3036 goto recurse;
3037 }
3038 } break;
3039
3040 case FRAME_BUILTIN_DECODE_UTF8: {
3041 auto *ast = decodeUTF8();
3042 if (ast != nullptr) {
3043 ast_ = ast;
3044 goto recurse;
3045 }
3046 } break;
3047
3048 default:
3049 std::cerr << "INTERNAL ERROR: Unknown FrameKind: " << f.kind << std::endl;
3050 std::abort();
3051 }
3052
3053 popframe:;
3054
3055 stack.pop();
3056
3057 replaceframe:;
3058 }
3059 }
3060
3061 /** Manifest the scratch value by evaluating any remaining fields, and then convert to JSON.
3062 *
3063 * This can trigger a garbage collection cycle. Be sure to stash any objects that aren't
3064 * reachable via the stack or heap.
3065 *
3066 * \param multiline If true, will print objects and arrays in an indented fashion.
3067 */
manifestJson(const LocationRange & loc,bool multiline,const UString & indent)3068 UString manifestJson(const LocationRange &loc, bool multiline, const UString &indent)
3069 {
3070 // Printing fields means evaluating and binding them, which can trigger
3071 // garbage collection.
3072
3073 UStringStream ss;
3074 switch (scratch.t) {
3075 case Value::ARRAY: {
3076 HeapArray *arr = static_cast<HeapArray *>(scratch.v.h);
3077 if (arr->elements.size() == 0) {
3078 ss << U"[ ]";
3079 } else {
3080 const char32_t *prefix = multiline ? U"[\n" : U"[";
3081 UString indent2 = multiline ? indent + U" " : indent;
3082 for (auto *thunk : arr->elements) {
3083 LocationRange tloc = thunk->body == nullptr ? loc : thunk->body->location;
3084 if (thunk->filled) {
3085 stack.newCall(loc, thunk, nullptr, 0, BindingFrame{});
3086 // Keep arr alive when scratch is overwritten
3087 stack.top().val = scratch;
3088 scratch = thunk->content;
3089 } else {
3090 stack.newCall(loc, thunk, thunk->self, thunk->offset, thunk->upValues);
3091 // Keep arr alive when scratch is overwritten
3092 stack.top().val = scratch;
3093 evaluate(thunk->body, stack.size());
3094 }
3095 auto element = manifestJson(tloc, multiline, indent2);
3096 // Restore scratch
3097 scratch = stack.top().val;
3098 stack.pop();
3099 ss << prefix << indent2 << element;
3100 prefix = multiline ? U",\n" : U", ";
3101 }
3102 ss << (multiline ? U"\n" : U"") << indent << U"]";
3103 }
3104 } break;
3105
3106 case Value::BOOLEAN: ss << (scratch.v.b ? U"true" : U"false"); break;
3107
3108 case Value::NUMBER: ss << decode_utf8(jsonnet_unparse_number(scratch.v.d)); break;
3109
3110 case Value::FUNCTION:
3111 throw makeError(loc, "couldn't manifest function in JSON output.");
3112
3113 case Value::NULL_TYPE: ss << U"null"; break;
3114
3115 case Value::OBJECT: {
3116 auto *obj = static_cast<HeapObject *>(scratch.v.h);
3117 runInvariants(loc, obj);
3118 // Using std::map has the useful side-effect of ordering the fields
3119 // alphabetically.
3120 std::map<UString, const Identifier *> fields;
3121 for (const auto &f : objectFields(obj, true)) {
3122 fields[f->name] = f;
3123 }
3124 if (fields.size() == 0) {
3125 ss << U"{ }";
3126 } else {
3127 UString indent2 = multiline ? indent + U" " : indent;
3128 const char32_t *prefix = multiline ? U"{\n" : U"{";
3129 for (const auto &f : fields) {
3130 // pushes FRAME_CALL
3131 const AST *body = objectIndex(loc, obj, f.second, 0);
3132 stack.top().val = scratch;
3133 evaluate(body, stack.size());
3134 auto vstr = manifestJson(body->location, multiline, indent2);
3135 // Reset scratch so that the object we're manifesting doesn't
3136 // get GC'd.
3137 scratch = stack.top().val;
3138 stack.pop();
3139 ss << prefix << indent2 << jsonnet_string_unparse(f.first, false) << U": "
3140 << vstr;
3141 prefix = multiline ? U",\n" : U", ";
3142 }
3143 ss << (multiline ? U"\n" : U"") << indent << U"}";
3144 }
3145 } break;
3146
3147 case Value::STRING: {
3148 const UString &str = static_cast<HeapString *>(scratch.v.h)->value;
3149 ss << jsonnet_string_unparse(str, false);
3150 } break;
3151 }
3152 return ss.str();
3153 }
3154
manifestString(const LocationRange & loc)3155 UString manifestString(const LocationRange &loc)
3156 {
3157 if (scratch.t != Value::STRING) {
3158 std::stringstream ss;
3159 ss << "expected string result, got: " << type_str(scratch.t);
3160 throw makeError(loc, ss.str());
3161 }
3162 return static_cast<HeapString *>(scratch.v.h)->value;
3163 }
3164
manifestMulti(bool string)3165 StrMap manifestMulti(bool string)
3166 {
3167 StrMap r;
3168 LocationRange loc("During manifestation");
3169 if (scratch.t != Value::OBJECT) {
3170 std::stringstream ss;
3171 ss << "multi mode: top-level object was a " << type_str(scratch.t) << ", "
3172 << "should be an object whose keys are filenames and values hold "
3173 << "the JSON for that file.";
3174 throw makeError(loc, ss.str());
3175 }
3176 auto *obj = static_cast<HeapObject *>(scratch.v.h);
3177 runInvariants(loc, obj);
3178 std::map<UString, const Identifier *> fields;
3179 for (const auto &f : objectFields(obj, true)) {
3180 fields[f->name] = f;
3181 }
3182 for (const auto &f : fields) {
3183 // pushes FRAME_CALL
3184 const AST *body = objectIndex(loc, obj, f.second, 0);
3185 stack.top().val = scratch;
3186 evaluate(body, stack.size());
3187 auto vstr =
3188 string ? manifestString(body->location) : manifestJson(body->location, true, U"");
3189 // Reset scratch so that the object we're manifesting doesn't
3190 // get GC'd.
3191 scratch = stack.top().val;
3192 stack.pop();
3193 r[encode_utf8(f.first)] = encode_utf8(vstr);
3194 }
3195 return r;
3196 }
3197
manifestStream(bool string)3198 std::vector<std::string> manifestStream(bool string)
3199 {
3200 std::vector<std::string> r;
3201 LocationRange loc("During manifestation");
3202 if (scratch.t != Value::ARRAY) {
3203 std::stringstream ss;
3204 ss << "stream mode: top-level object was a " << type_str(scratch.t) << ", "
3205 << "should be an array whose elements hold "
3206 << "the JSON for each document in the stream.";
3207 throw makeError(loc, ss.str());
3208 }
3209 auto *arr = static_cast<HeapArray *>(scratch.v.h);
3210 for (auto *thunk : arr->elements) {
3211 LocationRange tloc = thunk->body == nullptr ? loc : thunk->body->location;
3212 if (thunk->filled) {
3213 stack.newCall(loc, thunk, nullptr, 0, BindingFrame{});
3214 // Keep arr alive when scratch is overwritten
3215 stack.top().val = scratch;
3216 scratch = thunk->content;
3217 } else {
3218 stack.newCall(loc, thunk, thunk->self, thunk->offset, thunk->upValues);
3219 // Keep arr alive when scratch is overwritten
3220 stack.top().val = scratch;
3221 evaluate(thunk->body, stack.size());
3222 }
3223 UString element = string ? manifestString(tloc) : manifestJson(tloc, true, U"");
3224 scratch = stack.top().val;
3225 stack.pop();
3226 r.push_back(encode_utf8(element));
3227 }
3228 return r;
3229 }
3230 };
3231
3232 } // namespace
3233
jsonnet_vm_execute(Allocator * alloc,const AST * ast,const ExtMap & ext_vars,unsigned max_stack,double gc_min_objects,double gc_growth_trigger,const VmNativeCallbackMap & natives,JsonnetImportCallback * import_callback,void * ctx,bool string_output)3234 std::string jsonnet_vm_execute(Allocator *alloc, const AST *ast, const ExtMap &ext_vars,
3235 unsigned max_stack, double gc_min_objects, double gc_growth_trigger,
3236 const VmNativeCallbackMap &natives,
3237 JsonnetImportCallback *import_callback, void *ctx,
3238 bool string_output)
3239 {
3240 Interpreter vm(alloc,
3241 ext_vars,
3242 max_stack,
3243 gc_min_objects,
3244 gc_growth_trigger,
3245 natives,
3246 import_callback,
3247 ctx);
3248 vm.evaluate(ast, 0);
3249 if (string_output) {
3250 return encode_utf8(vm.manifestString(LocationRange("During manifestation")));
3251 } else {
3252 return encode_utf8(vm.manifestJson(LocationRange("During manifestation"), true, U""));
3253 }
3254 }
3255
jsonnet_vm_execute_multi(Allocator * alloc,const AST * ast,const ExtMap & ext_vars,unsigned max_stack,double gc_min_objects,double gc_growth_trigger,const VmNativeCallbackMap & natives,JsonnetImportCallback * import_callback,void * ctx,bool string_output)3256 StrMap jsonnet_vm_execute_multi(Allocator *alloc, const AST *ast, const ExtMap &ext_vars,
3257 unsigned max_stack, double gc_min_objects, double gc_growth_trigger,
3258 const VmNativeCallbackMap &natives,
3259 JsonnetImportCallback *import_callback, void *ctx,
3260 bool string_output)
3261 {
3262 Interpreter vm(alloc,
3263 ext_vars,
3264 max_stack,
3265 gc_min_objects,
3266 gc_growth_trigger,
3267 natives,
3268 import_callback,
3269 ctx);
3270 vm.evaluate(ast, 0);
3271 return vm.manifestMulti(string_output);
3272 }
3273
jsonnet_vm_execute_stream(Allocator * alloc,const AST * ast,const ExtMap & ext_vars,unsigned max_stack,double gc_min_objects,double gc_growth_trigger,const VmNativeCallbackMap & natives,JsonnetImportCallback * import_callback,void * ctx,bool string_output)3274 std::vector<std::string> jsonnet_vm_execute_stream(Allocator *alloc, const AST *ast,
3275 const ExtMap &ext_vars, unsigned max_stack,
3276 double gc_min_objects, double gc_growth_trigger,
3277 const VmNativeCallbackMap &natives,
3278 JsonnetImportCallback *import_callback,
3279 void *ctx, bool string_output)
3280 {
3281 Interpreter vm(alloc,
3282 ext_vars,
3283 max_stack,
3284 gc_min_objects,
3285 gc_growth_trigger,
3286 natives,
3287 import_callback,
3288 ctx);
3289 vm.evaluate(ast, 0);
3290 return vm.manifestStream(string_output);
3291 }
3292