1 // Copyright 2013 The Chromium 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.
5 #include "chrome/browser/profile_resetter/jtl_interpreter.h"
7 #include "base/memory/scoped_vector.h"
8 #include "base/strings/string_number_conversions.h"
9 #include "base/strings/string_util.h"
10 #include "chrome/browser/profile_resetter/jtl_foundation.h"
11 #include "crypto/hmac.h"
15 class ExecutionContext;
17 // An operation in an interpreted program.
20 virtual ~Operation() {}
21 // Executes the operation on the specified context and instructs the context
22 // to continue execution with the next instruction if appropriate.
23 // Returns true if we should continue with any potential backtracking that
25 virtual bool Execute(ExecutionContext* context) = 0;
28 // An execution context of operations.
29 class ExecutionContext {
31 // |input| is the root of a dictionary that stores the information the
32 // sentence is evaluated on.
33 ExecutionContext(const jtl_foundation::Hasher* hasher,
34 const std::vector<Operation*>& sentence,
35 const DictionaryValue* input,
36 DictionaryValue* working_memory)
39 next_instruction_index_(0u),
40 working_memory_(working_memory),
42 stack_.push_back(input);
44 ~ExecutionContext() {}
46 // Returns true in case of success.
47 bool ContinueExecution() {
48 if (error_ || stack_.empty()) {
52 if (next_instruction_index_ >= sentence_.size())
55 Operation* op = sentence_[next_instruction_index_];
56 next_instruction_index_++;
57 bool continue_traversal = op->Execute(this);
58 next_instruction_index_--;
59 return continue_traversal;
62 std::string GetHash(const std::string& input) {
63 return hasher_->GetHash(input);
66 // Calculates the |hash| of a string, integer or double |value|, and returns
67 // true. Returns false otherwise.
68 bool GetValueHash(const Value& value, std::string* hash) {
70 std::string value_as_string;
72 double tmp_double = 0.0;
73 if (value.GetAsInteger(&tmp_int))
74 value_as_string = base::IntToString(tmp_int);
75 else if (value.GetAsDouble(&tmp_double))
76 value_as_string = base::DoubleToString(tmp_double);
77 else if (!value.GetAsString(&value_as_string))
79 *hash = GetHash(value_as_string);
83 const Value* current_node() const { return stack_.back(); }
84 std::vector<const Value*>* stack() { return &stack_; }
85 DictionaryValue* working_memory() { return working_memory_; }
86 bool error() const { return error_; }
89 // A hasher used to hash node names in a dictionary.
90 const jtl_foundation::Hasher* hasher_;
91 // The sentence to be executed.
92 const std::vector<Operation*> sentence_;
93 // Position in |sentence_|.
94 size_t next_instruction_index_;
95 // A stack of Values, indicating a navigation path from the root node of
96 // |input| (see constructor) to the current node on which the
97 // sentence_[next_instruction_index_] is evaluated.
98 std::vector<const Value*> stack_;
99 // Memory into which values can be stored by the program.
100 DictionaryValue* working_memory_;
101 // Whether a runtime error occurred.
103 DISALLOW_COPY_AND_ASSIGN(ExecutionContext);
106 class NavigateOperation : public Operation {
108 explicit NavigateOperation(const std::string& hashed_key)
109 : hashed_key_(hashed_key) {}
110 virtual ~NavigateOperation() {}
111 virtual bool Execute(ExecutionContext* context) OVERRIDE {
112 const DictionaryValue* dict = NULL;
113 if (!context->current_node()->GetAsDictionary(&dict)) {
114 // Just ignore this node gracefully as this navigation is a dead end.
115 // If this NavigateOperation occurred after a NavigateAny operation, those
116 // may still be fulfillable, so we allow continuing the execution of the
117 // sentence on other nodes.
120 for (DictionaryValue::Iterator i(*dict); !i.IsAtEnd(); i.Advance()) {
121 if (context->GetHash(i.key()) != hashed_key_)
123 context->stack()->push_back(&i.value());
124 bool continue_traversal = context->ContinueExecution();
125 context->stack()->pop_back();
126 if (!continue_traversal)
133 std::string hashed_key_;
134 DISALLOW_COPY_AND_ASSIGN(NavigateOperation);
137 class NavigateAnyOperation : public Operation {
139 NavigateAnyOperation() {}
140 virtual ~NavigateAnyOperation() {}
141 virtual bool Execute(ExecutionContext* context) OVERRIDE {
142 const DictionaryValue* dict = NULL;
143 const ListValue* list = NULL;
144 if (context->current_node()->GetAsDictionary(&dict)) {
145 for (DictionaryValue::Iterator i(*dict); !i.IsAtEnd(); i.Advance()) {
146 context->stack()->push_back(&i.value());
147 bool continue_traversal = context->ContinueExecution();
148 context->stack()->pop_back();
149 if (!continue_traversal)
152 } else if (context->current_node()->GetAsList(&list)) {
153 for (ListValue::const_iterator i = list->begin(); i != list->end(); ++i) {
154 context->stack()->push_back(*i);
155 bool continue_traversal = context->ContinueExecution();
156 context->stack()->pop_back();
157 if (!continue_traversal)
161 // Do nothing, just ignore this node.
167 DISALLOW_COPY_AND_ASSIGN(NavigateAnyOperation);
170 class NavigateBackOperation : public Operation {
172 NavigateBackOperation() {}
173 virtual ~NavigateBackOperation() {}
174 virtual bool Execute(ExecutionContext* context) OVERRIDE {
175 const Value* current_node = context->current_node();
176 context->stack()->pop_back();
177 bool continue_traversal = context->ContinueExecution();
178 context->stack()->push_back(current_node);
179 return continue_traversal;
183 DISALLOW_COPY_AND_ASSIGN(NavigateBackOperation);
186 class StoreValue : public Operation {
188 StoreValue(const std::string& hashed_name, scoped_ptr<Value> value)
189 : hashed_name_(hashed_name),
190 value_(value.Pass()) {
191 DCHECK(IsStringUTF8(hashed_name));
194 virtual ~StoreValue() {}
195 virtual bool Execute(ExecutionContext* context) OVERRIDE {
196 context->working_memory()->Set(hashed_name_, value_->DeepCopy());
197 return context->ContinueExecution();
201 std::string hashed_name_;
202 scoped_ptr<Value> value_;
203 DISALLOW_COPY_AND_ASSIGN(StoreValue);
206 class CompareStoredValue : public Operation {
208 CompareStoredValue(const std::string& hashed_name,
209 scoped_ptr<Value> value,
210 scoped_ptr<Value> default_value)
211 : hashed_name_(hashed_name),
212 value_(value.Pass()),
213 default_value_(default_value.Pass()) {
214 DCHECK(IsStringUTF8(hashed_name));
216 DCHECK(default_value_);
218 virtual ~CompareStoredValue() {}
219 virtual bool Execute(ExecutionContext* context) OVERRIDE {
220 const Value* actual_value = NULL;
221 if (!context->working_memory()->Get(hashed_name_, &actual_value))
222 actual_value = default_value_.get();
223 if (!value_->Equals(actual_value))
225 return context->ContinueExecution();
229 std::string hashed_name_;
230 scoped_ptr<Value> value_;
231 scoped_ptr<Value> default_value_;
232 DISALLOW_COPY_AND_ASSIGN(CompareStoredValue);
235 template<bool ExpectedTypeIsBooleanNotHashable>
236 class StoreNodeValue : public Operation {
238 explicit StoreNodeValue(const std::string& hashed_name)
239 : hashed_name_(hashed_name) {
240 DCHECK(IsStringUTF8(hashed_name));
242 virtual ~StoreNodeValue() {}
243 virtual bool Execute(ExecutionContext* context) OVERRIDE {
244 scoped_ptr<base::Value> value;
245 if (ExpectedTypeIsBooleanNotHashable) {
246 if (!context->current_node()->IsType(base::Value::TYPE_BOOLEAN))
248 value.reset(context->current_node()->DeepCopy());
251 if (!context->GetValueHash(*context->current_node(), &hash))
253 value.reset(new base::StringValue(hash));
255 context->working_memory()->Set(hashed_name_, value.release());
256 return context->ContinueExecution();
260 std::string hashed_name_;
261 DISALLOW_COPY_AND_ASSIGN(StoreNodeValue);
264 class CompareNodeBool : public Operation {
266 explicit CompareNodeBool(bool value) : value_(value) {}
267 virtual ~CompareNodeBool() {}
268 virtual bool Execute(ExecutionContext* context) OVERRIDE {
269 bool actual_value = false;
270 if (!context->current_node()->GetAsBoolean(&actual_value))
272 if (actual_value != value_)
274 return context->ContinueExecution();
279 DISALLOW_COPY_AND_ASSIGN(CompareNodeBool);
282 class CompareNodeHash : public Operation {
284 explicit CompareNodeHash(const std::string& hashed_value)
285 : hashed_value_(hashed_value) {}
286 virtual ~CompareNodeHash() {}
287 virtual bool Execute(ExecutionContext* context) OVERRIDE {
288 std::string actual_hash;
289 if (!context->GetValueHash(*context->current_node(), &actual_hash) ||
290 actual_hash != hashed_value_)
292 return context->ContinueExecution();
296 std::string hashed_value_;
297 DISALLOW_COPY_AND_ASSIGN(CompareNodeHash);
300 class CompareNodeHashNot : public Operation {
302 explicit CompareNodeHashNot(const std::string& hashed_value)
303 : hashed_value_(hashed_value) {}
304 virtual ~CompareNodeHashNot() {}
305 virtual bool Execute(ExecutionContext* context) OVERRIDE {
306 std::string actual_hash;
307 if (context->GetValueHash(*context->current_node(), &actual_hash) &&
308 actual_hash == hashed_value_)
310 return context->ContinueExecution();
314 std::string hashed_value_;
315 DISALLOW_COPY_AND_ASSIGN(CompareNodeHashNot);
318 template<bool ExpectedTypeIsBooleanNotHashable>
319 class CompareNodeToStored : public Operation {
321 explicit CompareNodeToStored(const std::string& hashed_name)
322 : hashed_name_(hashed_name) {}
323 virtual ~CompareNodeToStored() {}
324 virtual bool Execute(ExecutionContext* context) OVERRIDE {
325 const Value* stored_value = NULL;
326 if (!context->working_memory()->Get(hashed_name_, &stored_value))
328 if (ExpectedTypeIsBooleanNotHashable) {
329 if (!context->current_node()->IsType(base::Value::TYPE_BOOLEAN) ||
330 !context->current_node()->Equals(stored_value))
333 std::string actual_hash;
334 std::string stored_hash;
335 if (!context->GetValueHash(*context->current_node(), &actual_hash) ||
336 !stored_value->GetAsString(&stored_hash) ||
337 actual_hash != stored_hash)
340 return context->ContinueExecution();
344 std::string hashed_name_;
345 DISALLOW_COPY_AND_ASSIGN(CompareNodeToStored);
348 class StopExecutingSentenceOperation : public Operation {
350 StopExecutingSentenceOperation() {}
351 virtual ~StopExecutingSentenceOperation() {}
352 virtual bool Execute(ExecutionContext* context) OVERRIDE {
357 DISALLOW_COPY_AND_ASSIGN(StopExecutingSentenceOperation);
362 explicit Parser(const std::string& program)
364 next_instruction_index_(0u) {}
366 bool ParseNextSentence(ScopedVector<Operation>* output) {
367 ScopedVector<Operation> operators;
368 bool sentence_ended = false;
369 while (next_instruction_index_ < program_.size() && !sentence_ended) {
371 if (!ReadOpCode(&op_code))
373 switch (static_cast<jtl_foundation::OpCodes>(op_code)) {
374 case jtl_foundation::NAVIGATE: {
375 std::string hashed_key;
376 if (!ReadHash(&hashed_key))
378 operators.push_back(new NavigateOperation(hashed_key));
381 case jtl_foundation::NAVIGATE_ANY:
382 operators.push_back(new NavigateAnyOperation);
384 case jtl_foundation::NAVIGATE_BACK:
385 operators.push_back(new NavigateBackOperation);
387 case jtl_foundation::STORE_BOOL: {
388 std::string hashed_name;
389 if (!ReadHash(&hashed_name) || !IsStringUTF8(hashed_name))
392 if (!ReadBool(&value))
394 operators.push_back(new StoreValue(
396 scoped_ptr<Value>(new base::FundamentalValue(value))));
399 case jtl_foundation::COMPARE_STORED_BOOL: {
400 std::string hashed_name;
401 if (!ReadHash(&hashed_name) || !IsStringUTF8(hashed_name))
404 if (!ReadBool(&value))
406 bool default_value = false;
407 if (!ReadBool(&default_value))
409 operators.push_back(new CompareStoredValue(
411 scoped_ptr<Value>(new base::FundamentalValue(value)),
412 scoped_ptr<Value>(new base::FundamentalValue(default_value))));
415 case jtl_foundation::STORE_HASH: {
416 std::string hashed_name;
417 if (!ReadHash(&hashed_name) || !IsStringUTF8(hashed_name))
419 std::string hashed_value;
420 if (!ReadHash(&hashed_value))
422 operators.push_back(new StoreValue(
424 scoped_ptr<Value>(new base::StringValue(hashed_value))));
427 case jtl_foundation::COMPARE_STORED_HASH: {
428 std::string hashed_name;
429 if (!ReadHash(&hashed_name) || !IsStringUTF8(hashed_name))
431 std::string hashed_value;
432 if (!ReadHash(&hashed_value))
434 std::string hashed_default_value;
435 if (!ReadHash(&hashed_default_value))
437 operators.push_back(new CompareStoredValue(
439 scoped_ptr<Value>(new base::StringValue(hashed_value)),
440 scoped_ptr<Value>(new base::StringValue(hashed_default_value))));
443 case jtl_foundation::STORE_NODE_BOOL: {
444 std::string hashed_name;
445 if (!ReadHash(&hashed_name) || !IsStringUTF8(hashed_name))
447 operators.push_back(new StoreNodeValue<true>(hashed_name));
450 case jtl_foundation::STORE_NODE_HASH: {
451 std::string hashed_name;
452 if (!ReadHash(&hashed_name) || !IsStringUTF8(hashed_name))
454 operators.push_back(new StoreNodeValue<false>(hashed_name));
457 case jtl_foundation::COMPARE_NODE_BOOL: {
459 if (!ReadBool(&value))
461 operators.push_back(new CompareNodeBool(value));
464 case jtl_foundation::COMPARE_NODE_HASH: {
465 std::string hashed_value;
466 if (!ReadHash(&hashed_value))
468 operators.push_back(new CompareNodeHash(hashed_value));
471 case jtl_foundation::COMPARE_NODE_HASH_NOT: {
472 std::string hashed_value;
473 if (!ReadHash(&hashed_value))
475 operators.push_back(new CompareNodeHashNot(hashed_value));
478 case jtl_foundation::COMPARE_NODE_TO_STORED_BOOL: {
479 std::string hashed_name;
480 if (!ReadHash(&hashed_name) || !IsStringUTF8(hashed_name))
482 operators.push_back(new CompareNodeToStored<true>(hashed_name));
485 case jtl_foundation::COMPARE_NODE_TO_STORED_HASH: {
486 std::string hashed_name;
487 if (!ReadHash(&hashed_name) || !IsStringUTF8(hashed_name))
489 operators.push_back(new CompareNodeToStored<false>(hashed_name));
492 case jtl_foundation::STOP_EXECUTING_SENTENCE:
493 operators.push_back(new StopExecutingSentenceOperation);
495 case jtl_foundation::END_OF_SENTENCE:
496 sentence_ended = true;
502 output->swap(operators);
506 bool HasNextSentence() const {
507 return next_instruction_index_ < program_.size();
511 // Reads an uint8 and returns whether this operation was successful.
512 bool ReadUint8(uint8* out) {
513 if (next_instruction_index_ + 1u > program_.size())
515 *out = static_cast<uint8>(program_[next_instruction_index_]);
516 ++next_instruction_index_;
520 // Reads an operator code and returns whether this operation was successful.
521 bool ReadOpCode(uint8* out) { return ReadUint8(out); }
523 bool ReadHash(std::string* out) {
524 if (next_instruction_index_ + jtl_foundation::kHashSizeInBytes >
527 *out = program_.substr(next_instruction_index_,
528 jtl_foundation::kHashSizeInBytes);
529 next_instruction_index_ += jtl_foundation::kHashSizeInBytes;
530 DCHECK(jtl_foundation::Hasher::IsHash(*out));
534 bool ReadBool(bool* out) {
536 if (!ReadUint8(&value))
547 std::string program_;
548 size_t next_instruction_index_;
549 DISALLOW_COPY_AND_ASSIGN(Parser);
554 JtlInterpreter::JtlInterpreter(
555 const std::string& hasher_seed,
556 const std::string& program,
557 const DictionaryValue* input)
558 : hasher_seed_(hasher_seed),
561 working_memory_(new DictionaryValue),
563 DCHECK(input->IsType(Value::TYPE_DICTIONARY));
566 JtlInterpreter::~JtlInterpreter() {}
568 void JtlInterpreter::Execute() {
569 jtl_foundation::Hasher hasher(hasher_seed_);
570 Parser parser(program_);
571 while (parser.HasNextSentence()) {
572 ScopedVector<Operation> sentence;
573 if (!parser.ParseNextSentence(&sentence)) {
574 result_ = PARSE_ERROR;
577 ExecutionContext context(
578 &hasher, sentence.get(), input_, working_memory_.get());
579 context.ContinueExecution();
580 if (context.error()) {
581 result_ = RUNTIME_ERROR;
587 bool JtlInterpreter::GetOutputBoolean(const std::string& unhashed_key,
588 bool* output) const {
589 std::string hashed_key =
590 jtl_foundation::Hasher(hasher_seed_).GetHash(unhashed_key);
591 return working_memory_->GetBoolean(hashed_key, output);
594 bool JtlInterpreter::GetOutputString(const std::string& unhashed_key,
595 std::string* output) const {
596 std::string hashed_key =
597 jtl_foundation::Hasher(hasher_seed_).GetHash(unhashed_key);
598 return working_memory_->GetString(hashed_key, output);