1// Copyright 2017 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#ifndef V8_PARSING_PREPARSE_DATA_H_
6#define V8_PARSING_PREPARSE_DATA_H_
7
8#include <memory>
9
10#include "src/base/vector.h"
11#include "src/common/globals.h"
12#include "src/handles/handles.h"
13#include "src/handles/maybe-handles.h"
14#include "src/utils/scoped-list.h"
15#include "src/zone/zone-chunk-list.h"
16#include "src/zone/zone-containers.h"
17
18namespace v8 {
19namespace internal {
20
21template <typename T>
22class PodArray;
23
24class Parser;
25class PreParser;
26class PreparseData;
27class ZonePreparseData;
28class AstValueFactory;
29
30/*
31
32  Skipping inner functions.
33
34  Consider the following code:
35  (function eager_outer() {
36    function lazy_inner() {
37      let a;
38      function skip_me() { a; }
39    }
40
41    return lazy_inner;
42  })();
43
44  ... lazy_inner(); ...
45
46  When parsing the code the first time, eager_outer is parsed and lazy_inner
47  (and everything inside it) is preparsed. When lazy_inner is called, we don't
48  want to parse or preparse skip_me again. Instead, we want to skip over it,
49  since it has already been preparsed once.
50
51  In order to be able to do this, we need to store the information needed for
52  allocating the variables in lazy_inner when we preparse it, and then later do
53  scope allocation based on that data.
54
55  We need the following data for each scope in lazy_inner's scope tree:
56  For each Variable:
57  - is_used
58  - maybe_assigned
59  - has_forced_context_allocation
60
61  For each Scope:
62  - inner_scope_calls_eval_.
63
64  ProducedPreparseData implements storing the above mentioned data and
65  ConsumedPreparseData implements restoring it (= setting the context
66  allocation status of the variables in a Scope (and its subscopes) based on the
67  data).
68
69 */
70
71struct PreparseByteDataConstants {
72#ifdef DEBUG
73  static constexpr int kMagicValue = 0xC0DE0DE;
74
75  static constexpr size_t kUint32Size = 5;
76  static constexpr size_t kVarint32MinSize = 3;
77  static constexpr size_t kVarint32MaxSize = 7;
78  static constexpr size_t kVarint32EndMarker = 0xF1;
79  static constexpr size_t kUint8Size = 2;
80  static constexpr size_t kQuarterMarker = 0xF2;
81  static constexpr size_t kPlaceholderSize = kUint32Size;
82#else
83  static constexpr size_t kUint32Size = 4;
84  static constexpr size_t kVarint32MinSize = 1;
85  static constexpr size_t kVarint32MaxSize = 5;
86  static constexpr size_t kUint8Size = 1;
87  static constexpr size_t kPlaceholderSize = 0;
88#endif
89
90  static const size_t kSkippableFunctionMinDataSize =
91      4 * kVarint32MinSize + 1 * kUint8Size;
92  static const size_t kSkippableFunctionMaxDataSize =
93      4 * kVarint32MaxSize + 1 * kUint8Size;
94};
95
96class V8_EXPORT_PRIVATE PreparseDataBuilder : public ZoneObject,
97                                              public PreparseByteDataConstants {
98 public:
99  // Create a PreparseDataBuilder object which will collect data as we
100  // parse.
101  explicit PreparseDataBuilder(Zone* zone, PreparseDataBuilder* parent_builder,
102                               std::vector<void*>* children_buffer);
103  ~PreparseDataBuilder() {}
104  PreparseDataBuilder(const PreparseDataBuilder&) = delete;
105  PreparseDataBuilder& operator=(const PreparseDataBuilder&) = delete;
106
107  PreparseDataBuilder* parent() const { return parent_; }
108
109  // For gathering the inner function data and splitting it up according to the
110  // laziness boundaries. Each lazy function gets its own
111  // ProducedPreparseData, and so do all lazy functions inside it.
112  class V8_NODISCARD DataGatheringScope {
113   public:
114    explicit DataGatheringScope(PreParser* preparser)
115        : preparser_(preparser), builder_(nullptr) {}
116    DataGatheringScope(const DataGatheringScope&) = delete;
117    DataGatheringScope& operator=(const DataGatheringScope&) = delete;
118
119    void Start(DeclarationScope* function_scope);
120    void SetSkippableFunction(DeclarationScope* function_scope,
121                              int function_length, int num_inner_functions);
122    inline ~DataGatheringScope() {
123      if (builder_ == nullptr) return;
124      Close();
125    }
126
127   private:
128    void Close();
129
130    PreParser* preparser_;
131    PreparseDataBuilder* builder_;
132  };
133
134  class V8_EXPORT_PRIVATE ByteData : public ZoneObject,
135                                     public PreparseByteDataConstants {
136   public:
137    ByteData()
138        : byte_data_(nullptr), index_(0), free_quarters_in_last_byte_(0) {}
139
140    void Start(std::vector<uint8_t>* buffer);
141    void Finalize(Zone* zone);
142
143    Handle<PreparseData> CopyToHeap(Isolate* isolate, int children_length);
144    Handle<PreparseData> CopyToLocalHeap(LocalIsolate* isolate,
145                                         int children_length);
146    inline ZonePreparseData* CopyToZone(Zone* zone, int children_length);
147
148    void Reserve(size_t bytes);
149    void Add(uint8_t byte);
150    int length() const;
151
152    void WriteVarint32(uint32_t data);
153    void WriteUint8(uint8_t data);
154    void WriteQuarter(uint8_t data);
155
156#ifdef DEBUG
157    void WriteUint32(uint32_t data);
158    // For overwriting previously written data at position 0.
159    void SaveCurrentSizeAtFirstUint32();
160#endif
161
162   private:
163    union {
164      struct {
165        // Only used during construction (is_finalized_ == false).
166        std::vector<uint8_t>* byte_data_;
167        int index_;
168      };
169      // Once the data is finalized, it lives in a Zone, this implies
170      // is_finalized_ == true.
171      base::Vector<uint8_t> zone_byte_data_;
172    };
173    uint8_t free_quarters_in_last_byte_;
174
175#ifdef DEBUG
176    bool is_finalized_ = false;
177#endif
178  };
179
180  // Saves the information needed for allocating the Scope's (and its
181  // subscopes') variables.
182  void SaveScopeAllocationData(DeclarationScope* scope, Parser* parser);
183
184  // In some cases, PreParser cannot produce the same Scope structure as
185  // Parser. If it happens, we're unable to produce the data that would enable
186  // skipping the inner functions of that function.
187  void Bailout() {
188    bailed_out_ = true;
189    // We don't need to call Bailout on existing / future children: the only way
190    // to try to retrieve their data is through calling Serialize on the parent,
191    // and if the parent is bailed out, it won't call Serialize on its children.
192  }
193
194  bool bailed_out() const { return bailed_out_; }
195
196#ifdef DEBUG
197  bool ThisOrParentBailedOut() const {
198    if (bailed_out_) return true;
199    if (parent_ == nullptr) return false;
200    return parent_->ThisOrParentBailedOut();
201  }
202#endif  // DEBUG
203
204  bool HasInnerFunctions() const;
205  bool HasData() const;
206  bool HasDataForParent() const;
207
208  static bool ScopeNeedsData(Scope* scope);
209
210 private:
211  friend class BuilderProducedPreparseData;
212
213  Handle<PreparseData> Serialize(Isolate* isolate);
214  Handle<PreparseData> Serialize(LocalIsolate* isolate);
215  ZonePreparseData* Serialize(Zone* zone);
216
217  void FinalizeChildren(Zone* zone);
218  void AddChild(PreparseDataBuilder* child);
219
220  void SaveDataForScope(Scope* scope);
221  void SaveDataForVariable(Variable* var);
222  void SaveDataForInnerScopes(Scope* scope);
223  bool SaveDataForSkippableFunction(PreparseDataBuilder* builder);
224
225  void CopyByteData(Zone* zone);
226
227  PreparseDataBuilder* parent_;
228  ByteData byte_data_;
229  union {
230    ScopedPtrList<PreparseDataBuilder> children_buffer_;
231    base::Vector<PreparseDataBuilder*> children_;
232  };
233
234  DeclarationScope* function_scope_;
235  int function_length_;
236  int num_inner_functions_;
237  int num_inner_with_data_;
238
239  // Whether we've given up producing the data for this function.
240  bool bailed_out_ : 1;
241  bool has_data_ : 1;
242
243#ifdef DEBUG
244  bool finalized_children_ = false;
245#endif
246};
247
248class ProducedPreparseData : public ZoneObject {
249 public:
250  // If there is data (if the Scope contains skippable inner functions), move
251  // the data into the heap and return a Handle to it; otherwise return a null
252  // MaybeHandle.
253  virtual Handle<PreparseData> Serialize(Isolate* isolate) = 0;
254
255  // If there is data (if the Scope contains skippable inner functions), move
256  // the data into the heap and return a Handle to it; otherwise return a null
257  // MaybeHandle.
258  virtual Handle<PreparseData> Serialize(LocalIsolate* isolate) = 0;
259
260  // If there is data (if the Scope contains skippable inner functions), return
261  // an off-heap ZonePreparseData representing the data; otherwise
262  // return nullptr.
263  virtual ZonePreparseData* Serialize(Zone* zone) = 0;
264
265  // Create a ProducedPreparseData which is a proxy for a previous
266  // produced PreparseData in zone.
267  static ProducedPreparseData* For(PreparseDataBuilder* builder, Zone* zone);
268
269  // Create a ProducedPreparseData which is a proxy for a previous
270  // produced PreparseData on the heap.
271  static ProducedPreparseData* For(Handle<PreparseData> data, Zone* zone);
272
273  // Create a ProducedPreparseData which is a proxy for a previous
274  // produced PreparseData in zone.
275  static ProducedPreparseData* For(ZonePreparseData* data, Zone* zone);
276};
277
278class ConsumedPreparseData {
279 public:
280  // Creates a ConsumedPreparseData representing the data of an on-heap
281  // PreparseData |data|.
282  V8_EXPORT_PRIVATE static std::unique_ptr<ConsumedPreparseData> For(
283      Isolate* isolate, Handle<PreparseData> data);
284  V8_EXPORT_PRIVATE static std::unique_ptr<ConsumedPreparseData> For(
285      LocalIsolate* isolate, Handle<PreparseData> data);
286
287  // Creates a ConsumedPreparseData representing the data of an off-heap
288  // ZonePreparseData |data|.
289  static std::unique_ptr<ConsumedPreparseData> For(Zone* zone,
290                                                   ZonePreparseData* data);
291
292  virtual ~ConsumedPreparseData() = default;
293
294  ConsumedPreparseData(const ConsumedPreparseData&) = delete;
295  ConsumedPreparseData& operator=(const ConsumedPreparseData&) = delete;
296
297  virtual ProducedPreparseData* GetDataForSkippableFunction(
298      Zone* zone, int start_position, int* end_position, int* num_parameters,
299      int* function_length, int* num_inner_functions, bool* uses_super_property,
300      LanguageMode* language_mode) = 0;
301
302  // Restores the information needed for allocating the Scope's (and its
303  // subscopes') variables.
304  virtual void RestoreScopeAllocationData(DeclarationScope* scope,
305                                          AstValueFactory* ast_value_factory,
306                                          Zone* zone) = 0;
307
308 protected:
309  ConsumedPreparseData() = default;
310};
311
312}  // namespace internal
313}  // namespace v8
314
315#endif  // V8_PARSING_PREPARSE_DATA_H_
316