chrome/browser/profile_resetter/jtl_interpreter.cc

   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.
   4
   5 #include "chrome/browser/profile_resetter/jtl_interpreter.h"
   6
   7 #include <numeric>
   8
   9 #include "base/memory/scoped_vector.h"
  10 #include "base/strings/string_number_conversions.h"
  11 #include "base/strings/string_util.h"
  12 #include "chrome/browser/profile_resetter/jtl_foundation.h"
  13 #include "crypto/hmac.h"
  14 #include "net/base/registry_controlled_domains/registry_controlled_domain.h"
  15 #include "url/gurl.h"
  16
  17 namespace {
  18
  19 class ExecutionContext;
  20
  21 // An operation in an interpreted program.
  22 class Operation {
  23  public:
  24   virtual ~Operation() {}
  25   // Executes the operation on the specified context and instructs the context
  26   // to continue execution with the next instruction if appropriate.
  27   // Returns true if we should continue with any potential backtracking that
  28   // needs to be done.
  29   virtual bool Execute(ExecutionContext* context) = 0;
  30 };
  31
  32 // An execution context of operations.
  33 class ExecutionContext {
  34  public:
  35   // |input| is the root of a dictionary that stores the information the
  36   // sentence is evaluated on.
  37   ExecutionContext(const jtl_foundation::Hasher* hasher,
  38                    const std::vector<Operation*>& sentence,
  39                    const base::DictionaryValue* input,
  40                    base::DictionaryValue* working_memory)
  41       : hasher_(hasher),
  42         sentence_(sentence),
  43         next_instruction_index_(0u),
  44         working_memory_(working_memory),
  45         error_(false) {
  46     stack_.push_back(input);
  47   }
  48   ~ExecutionContext() {}
  49
  50   // Returns true in case of success.
  51   bool ContinueExecution() {
  52     if (error_ || stack_.empty()) {
  53       error_ = true;
  54       return false;
  55     }
  56     if (next_instruction_index_ >= sentence_.size())
  57       return true;
  58
  59     Operation* op = sentence_[next_instruction_index_];
  60     next_instruction_index_++;
  61     bool continue_traversal = op->Execute(this);
  62     next_instruction_index_--;
  63     return continue_traversal;
  64   }
  65
  66   std::string GetHash(const std::string& input) {
  67     return hasher_->GetHash(input);
  68   }
  69
  70   // Calculates the |hash| of a string, integer or double |value|, and returns
  71   // true. Returns false otherwise.
  72   bool GetValueHash(const base::Value& value, std::string* hash) {
  73     DCHECK(hash);
  74     std::string value_as_string;
  75     int tmp_int = 0;
  76     double tmp_double = 0.0;
  77     if (value.GetAsInteger(&tmp_int))
  78       value_as_string = base::IntToString(tmp_int);
  79     else if (value.GetAsDouble(&tmp_double))
  80       value_as_string = base::DoubleToString(tmp_double);
  81     else if (!value.GetAsString(&value_as_string))
  82       return false;
  83     *hash = GetHash(value_as_string);
  84     return true;
  85   }
  86
  87   const base::Value* current_node() const { return stack_.back(); }
  88   std::vector<const base::Value*>* stack() { return &stack_; }
  89   base::DictionaryValue* working_memory() { return working_memory_; }
  90   bool error() const { return error_; }
  91
  92  private:
  93   // A hasher used to hash node names in a dictionary.
  94   const jtl_foundation::Hasher* hasher_;
  95   // The sentence to be executed.
  96   const std::vector<Operation*> sentence_;
  97   // Position in |sentence_|.
  98   size_t next_instruction_index_;
  99   // A stack of Values, indicating a navigation path from the root node of
 100   // |input| (see constructor) to the current node on which the
 101   // sentence_[next_instruction_index_] is evaluated.
 102   std::vector<const base::Value*> stack_;
 103   // Memory into which values can be stored by the program.
 104   base::DictionaryValue* working_memory_;
 105   // Whether a runtime error occurred.
 106   bool error_;
 107   DISALLOW_COPY_AND_ASSIGN(ExecutionContext);
 108 };
 109
 110 class NavigateOperation : public Operation {
 111  public:
 112   explicit NavigateOperation(const std::string& hashed_key)
 113       : hashed_key_(hashed_key) {}
 114   virtual ~NavigateOperation() {}
 115   virtual bool Execute(ExecutionContext* context) OVERRIDE {
 116     const base::DictionaryValue* dict = NULL;
 117     if (!context->current_node()->GetAsDictionary(&dict)) {
 118       // Just ignore this node gracefully as this navigation is a dead end.
 119       // If this NavigateOperation occurred after a NavigateAny operation, those
 120       // may still be fulfillable, so we allow continuing the execution of the
 121       // sentence on other nodes.
 122       return true;
 123     }
 124     for (base::DictionaryValue::Iterator i(*dict); !i.IsAtEnd(); i.Advance()) {
 125       if (context->GetHash(i.key()) != hashed_key_)
 126         continue;
 127       context->stack()->push_back(&i.value());
 128       bool continue_traversal = context->ContinueExecution();
 129       context->stack()->pop_back();
 130       if (!continue_traversal)
 131         return false;
 132     }
 133     return true;
 134   }
 135
 136  private:
 137   std::string hashed_key_;
 138   DISALLOW_COPY_AND_ASSIGN(NavigateOperation);
 139 };
 140
 141 class NavigateAnyOperation : public Operation {
 142  public:
 143   NavigateAnyOperation() {}
 144   virtual ~NavigateAnyOperation() {}
 145   virtual bool Execute(ExecutionContext* context) OVERRIDE {
 146     const base::DictionaryValue* dict = NULL;
 147     const base::ListValue* list = NULL;
 148     if (context->current_node()->GetAsDictionary(&dict)) {
 149       for (base::DictionaryValue::Iterator i(*dict);
 150            !i.IsAtEnd(); i.Advance()) {
 151         context->stack()->push_back(&i.value());
 152         bool continue_traversal = context->ContinueExecution();
 153         context->stack()->pop_back();
 154         if (!continue_traversal)
 155           return false;
 156       }
 157     } else if (context->current_node()->GetAsList(&list)) {
 158       for (base::ListValue::const_iterator i = list->begin();
 159            i != list->end(); ++i) {
 160         context->stack()->push_back(*i);
 161         bool continue_traversal = context->ContinueExecution();
 162         context->stack()->pop_back();
 163         if (!continue_traversal)
 164           return false;
 165       }
 166     } else {
 167       // Do nothing, just ignore this node.
 168     }
 169     return true;
 170   }
 171
 172  private:
 173   DISALLOW_COPY_AND_ASSIGN(NavigateAnyOperation);
 174 };
 175
 176 class NavigateBackOperation : public Operation {
 177  public:
 178   NavigateBackOperation() {}
 179   virtual ~NavigateBackOperation() {}
 180   virtual bool Execute(ExecutionContext* context) OVERRIDE {
 181     const base::Value* current_node = context->current_node();
 182     context->stack()->pop_back();
 183     bool continue_traversal = context->ContinueExecution();
 184     context->stack()->push_back(current_node);
 185     return continue_traversal;
 186   }
 187
 188  private:
 189   DISALLOW_COPY_AND_ASSIGN(NavigateBackOperation);
 190 };
 191
 192 class StoreValue : public Operation {
 193  public:
 194   StoreValue(const std::string& hashed_name, scoped_ptr<base::Value> value)
 195       : hashed_name_(hashed_name),
 196         value_(value.Pass()) {
 197     DCHECK(IsStringUTF8(hashed_name));
 198     DCHECK(value_);
 199   }
 200   virtual ~StoreValue() {}
 201   virtual bool Execute(ExecutionContext* context) OVERRIDE {
 202     context->working_memory()->Set(hashed_name_, value_->DeepCopy());
 203     return context->ContinueExecution();
 204   }
 205
 206  private:
 207   std::string hashed_name_;
 208   scoped_ptr<base::Value> value_;
 209   DISALLOW_COPY_AND_ASSIGN(StoreValue);
 210 };
 211
 212 class CompareStoredValue : public Operation {
 213  public:
 214   CompareStoredValue(const std::string& hashed_name,
 215                      scoped_ptr<base::Value> value,
 216                      scoped_ptr<base::Value> default_value)
 217       : hashed_name_(hashed_name),
 218         value_(value.Pass()),
 219         default_value_(default_value.Pass()) {
 220     DCHECK(IsStringUTF8(hashed_name));
 221     DCHECK(value_);
 222     DCHECK(default_value_);
 223   }
 224   virtual ~CompareStoredValue() {}
 225   virtual bool Execute(ExecutionContext* context) OVERRIDE {
 226     const base::Value* actual_value = NULL;
 227     if (!context->working_memory()->Get(hashed_name_, &actual_value))
 228       actual_value = default_value_.get();
 229     if (!value_->Equals(actual_value))
 230       return true;
 231     return context->ContinueExecution();
 232   }
 233
 234  private:
 235   std::string hashed_name_;
 236   scoped_ptr<base::Value> value_;
 237   scoped_ptr<base::Value> default_value_;
 238   DISALLOW_COPY_AND_ASSIGN(CompareStoredValue);
 239 };
 240
 241 template<bool ExpectedTypeIsBooleanNotHashable>
 242 class StoreNodeValue : public Operation {
 243  public:
 244   explicit StoreNodeValue(const std::string& hashed_name)
 245       : hashed_name_(hashed_name) {
 246     DCHECK(IsStringUTF8(hashed_name));
 247   }
 248   virtual ~StoreNodeValue() {}
 249   virtual bool Execute(ExecutionContext* context) OVERRIDE {
 250     scoped_ptr<base::Value> value;
 251     if (ExpectedTypeIsBooleanNotHashable) {
 252       if (!context->current_node()->IsType(base::Value::TYPE_BOOLEAN))
 253         return true;
 254       value.reset(context->current_node()->DeepCopy());
 255     } else {
 256       std::string hash;
 257       if (!context->GetValueHash(*context->current_node(), &hash))
 258         return true;
 259       value.reset(new base::StringValue(hash));
 260     }
 261     context->working_memory()->Set(hashed_name_, value.release());
 262     return context->ContinueExecution();
 263   }
 264
 265  private:
 266   std::string hashed_name_;
 267   DISALLOW_COPY_AND_ASSIGN(StoreNodeValue);
 268 };
 269
 270 // Stores the hash of the registerable domain name -- as in, the portion of the
 271 // domain that is registerable, as opposed to controlled by a registrar; without
 272 // subdomains -- of the URL represented by the current node into working memory.
 273 class StoreNodeRegisterableDomain : public Operation {
 274  public:
 275   explicit StoreNodeRegisterableDomain(const std::string& hashed_name)
 276       : hashed_name_(hashed_name) {
 277     DCHECK(IsStringUTF8(hashed_name));
 278   }
 279   virtual ~StoreNodeRegisterableDomain() {}
 280   virtual bool Execute(ExecutionContext* context) OVERRIDE {
 281     std::string possibly_invalid_url;
 282     std::string domain;
 283     if (!context->current_node()->GetAsString(&possibly_invalid_url) ||
 284         !GetRegisterableDomain(possibly_invalid_url, &domain))
 285       return true;
 286     context->working_memory()->Set(
 287         hashed_name_, new base::StringValue(context->GetHash(domain)));
 288     return context->ContinueExecution();
 289   }
 290
 291  private:
 292   // If |possibly_invalid_url| is a valid URL having a registerable domain name
 293   // part, outputs that in |registerable_domain| and returns true. Otherwise,
 294   // returns false.
 295   static bool GetRegisterableDomain(const std::string& possibly_invalid_url,
 296                                     std::string* registerable_domain) {
 297     namespace domains = net::registry_controlled_domains;
 298     DCHECK(registerable_domain);
 299     GURL url(possibly_invalid_url);
 300     if (!url.is_valid())
 301       return false;
 302     std::string registry_plus_one = domains::GetDomainAndRegistry(
 303         url.host(), domains::INCLUDE_PRIVATE_REGISTRIES);
 304     size_t registry_length = domains::GetRegistryLength(
 305         url.host(),
 306         domains::INCLUDE_UNKNOWN_REGISTRIES,
 307         domains::INCLUDE_PRIVATE_REGISTRIES);
 308     // Fail unless (1.) the URL has a host part; and (2.) that host part is a
 309     // well-formed domain name consisting of at least one subcomponent; followed
 310     // by either a recognized registry identifier, or exactly one subcomponent,
 311     // which is then assumed to be the unknown registry identifier.
 312     if (registry_length == std::string::npos || registry_length == 0)
 313       return false;
 314     DCHECK_LT(registry_length, registry_plus_one.size());
 315     // Subtract one to cut off the dot separating the SLD and the registry.
 316     registerable_domain->assign(
 317         registry_plus_one, 0, registry_plus_one.size() - registry_length - 1);
 318     return true;
 319   }
 320
 321   std::string hashed_name_;
 322   DISALLOW_COPY_AND_ASSIGN(StoreNodeRegisterableDomain);
 323 };
 324
 325 class CompareNodeBool : public Operation {
 326  public:
 327   explicit CompareNodeBool(bool value) : value_(value) {}
 328   virtual ~CompareNodeBool() {}
 329   virtual bool Execute(ExecutionContext* context) OVERRIDE {
 330     bool actual_value = false;
 331     if (!context->current_node()->GetAsBoolean(&actual_value))
 332       return true;
 333     if (actual_value != value_)
 334       return true;
 335     return context->ContinueExecution();
 336   }
 337
 338  private:
 339   bool value_;
 340   DISALLOW_COPY_AND_ASSIGN(CompareNodeBool);
 341 };
 342
 343 class CompareNodeHash : public Operation {
 344  public:
 345   explicit CompareNodeHash(const std::string& hashed_value)
 346       : hashed_value_(hashed_value) {}
 347   virtual ~CompareNodeHash() {}
 348   virtual bool Execute(ExecutionContext* context) OVERRIDE {
 349     std::string actual_hash;
 350     if (!context->GetValueHash(*context->current_node(), &actual_hash) ||
 351         actual_hash != hashed_value_)
 352       return true;
 353     return context->ContinueExecution();
 354   }
 355
 356  private:
 357   std::string hashed_value_;
 358   DISALLOW_COPY_AND_ASSIGN(CompareNodeHash);
 359 };
 360
 361 class CompareNodeHashNot : public Operation {
 362  public:
 363   explicit CompareNodeHashNot(const std::string& hashed_value)
 364       : hashed_value_(hashed_value) {}
 365   virtual ~CompareNodeHashNot() {}
 366   virtual bool Execute(ExecutionContext* context) OVERRIDE {
 367     std::string actual_hash;
 368     if (context->GetValueHash(*context->current_node(), &actual_hash) &&
 369         actual_hash == hashed_value_)
 370       return true;
 371     return context->ContinueExecution();
 372   }
 373
 374  private:
 375   std::string hashed_value_;
 376   DISALLOW_COPY_AND_ASSIGN(CompareNodeHashNot);
 377 };
 378
 379 template<bool ExpectedTypeIsBooleanNotHashable>
 380 class CompareNodeToStored : public Operation {
 381  public:
 382   explicit CompareNodeToStored(const std::string& hashed_name)
 383       : hashed_name_(hashed_name) {}
 384   virtual ~CompareNodeToStored() {}
 385   virtual bool Execute(ExecutionContext* context) OVERRIDE {
 386     const base::Value* stored_value = NULL;
 387     if (!context->working_memory()->Get(hashed_name_, &stored_value))
 388       return true;
 389     if (ExpectedTypeIsBooleanNotHashable) {
 390       if (!context->current_node()->IsType(base::Value::TYPE_BOOLEAN) ||
 391           !context->current_node()->Equals(stored_value))
 392         return true;
 393     } else {
 394       std::string actual_hash;
 395       std::string stored_hash;
 396       if (!context->GetValueHash(*context->current_node(), &actual_hash) ||
 397           !stored_value->GetAsString(&stored_hash) ||
 398           actual_hash != stored_hash)
 399         return true;
 400     }
 401     return context->ContinueExecution();
 402   }
 403
 404  private:
 405   std::string hashed_name_;
 406   DISALLOW_COPY_AND_ASSIGN(CompareNodeToStored);
 407 };
 408
 409 class CompareNodeSubstring : public Operation {
 410  public:
 411   explicit CompareNodeSubstring(const std::string& hashed_pattern,
 412                                 size_t pattern_length,
 413                                 uint32 pattern_sum)
 414       : hashed_pattern_(hashed_pattern),
 415         pattern_length_(pattern_length),
 416         pattern_sum_(pattern_sum) {
 417     DCHECK(pattern_length_);
 418   }
 419   virtual ~CompareNodeSubstring() {}
 420   virtual bool Execute(ExecutionContext* context) OVERRIDE {
 421     std::string value_as_string;
 422     if (!context->current_node()->GetAsString(&value_as_string) ||
 423         !pattern_length_ || value_as_string.size() < pattern_length_)
 424       return true;
 425     // Go over the string with a sliding window. Meanwhile, maintain the sum in
 426     // an incremental fashion, and only calculate the SHA-256 hash when the sum
 427     // checks out so as to improve performance.
 428     std::string::const_iterator window_begin = value_as_string.begin();
 429     std::string::const_iterator window_end = window_begin + pattern_length_ - 1;
 430     uint32 window_sum =
 431         std::accumulate(window_begin, window_end, static_cast<uint32>(0u));
 432     while (window_end != value_as_string.end()) {
 433       window_sum += *window_end++;
 434       if (window_sum == pattern_sum_ && context->GetHash(std::string(
 435           window_begin, window_end)) == hashed_pattern_)
 436         return context->ContinueExecution();
 437       window_sum -= *window_begin++;
 438     }
 439     return true;
 440   }
 441
 442  private:
 443   std::string hashed_pattern_;
 444   size_t pattern_length_;
 445   uint32 pattern_sum_;
 446   DISALLOW_COPY_AND_ASSIGN(CompareNodeSubstring);
 447 };
 448
 449 class StopExecutingSentenceOperation : public Operation {
 450  public:
 451   StopExecutingSentenceOperation() {}
 452   virtual ~StopExecutingSentenceOperation() {}
 453   virtual bool Execute(ExecutionContext* context) OVERRIDE {
 454     return false;
 455   }
 456
 457  private:
 458   DISALLOW_COPY_AND_ASSIGN(StopExecutingSentenceOperation);
 459 };
 460
 461 class Parser {
 462  public:
 463   explicit Parser(const std::string& program)
 464       : program_(program),
 465         next_instruction_index_(0u) {}
 466   ~Parser() {}
 467   bool ParseNextSentence(ScopedVector<Operation>* output) {
 468     ScopedVector<Operation> operators;
 469     bool sentence_ended = false;
 470     while (next_instruction_index_ < program_.size() && !sentence_ended) {
 471       uint8 op_code = 0;
 472       if (!ReadOpCode(&op_code))
 473         return false;
 474       switch (static_cast<jtl_foundation::OpCodes>(op_code)) {
 475         case jtl_foundation::NAVIGATE: {
 476           std::string hashed_key;
 477           if (!ReadHash(&hashed_key))
 478             return false;
 479           operators.push_back(new NavigateOperation(hashed_key));
 480           break;
 481         }
 482         case jtl_foundation::NAVIGATE_ANY:
 483           operators.push_back(new NavigateAnyOperation);
 484           break;
 485         case jtl_foundation::NAVIGATE_BACK:
 486           operators.push_back(new NavigateBackOperation);
 487           break;
 488         case jtl_foundation::STORE_BOOL: {
 489           std::string hashed_name;
 490           if (!ReadHash(&hashed_name) || !IsStringUTF8(hashed_name))
 491             return false;
 492           bool value = false;
 493           if (!ReadBool(&value))
 494             return false;
 495           operators.push_back(new StoreValue(
 496               hashed_name,
 497               scoped_ptr<base::Value>(new base::FundamentalValue(value))));
 498           break;
 499         }
 500         case jtl_foundation::COMPARE_STORED_BOOL: {
 501           std::string hashed_name;
 502           if (!ReadHash(&hashed_name) || !IsStringUTF8(hashed_name))
 503             return false;
 504           bool value = false;
 505           if (!ReadBool(&value))
 506             return false;
 507           bool default_value = false;
 508           if (!ReadBool(&default_value))
 509             return false;
 510           operators.push_back(new CompareStoredValue(
 511               hashed_name,
 512               scoped_ptr<base::Value>(new base::FundamentalValue(value)),
 513               scoped_ptr<base::Value>(
 514                   new base::FundamentalValue(default_value))));
 515           break;
 516         }
 517         case jtl_foundation::STORE_HASH: {
 518           std::string hashed_name;
 519           if (!ReadHash(&hashed_name) || !IsStringUTF8(hashed_name))
 520             return false;
 521           std::string hashed_value;
 522           if (!ReadHash(&hashed_value))
 523             return false;
 524           operators.push_back(new StoreValue(
 525               hashed_name,
 526               scoped_ptr<base::Value>(new base::StringValue(hashed_value))));
 527           break;
 528         }
 529         case jtl_foundation::COMPARE_STORED_HASH: {
 530           std::string hashed_name;
 531           if (!ReadHash(&hashed_name) || !IsStringUTF8(hashed_name))
 532             return false;
 533           std::string hashed_value;
 534           if (!ReadHash(&hashed_value))
 535             return false;
 536           std::string hashed_default_value;
 537           if (!ReadHash(&hashed_default_value))
 538             return false;
 539           operators.push_back(new CompareStoredValue(
 540               hashed_name,
 541               scoped_ptr<base::Value>(new base::StringValue(hashed_value)),
 542               scoped_ptr<base::Value>(
 543                   new base::StringValue(hashed_default_value))));
 544           break;
 545         }
 546         case jtl_foundation::STORE_NODE_BOOL: {
 547           std::string hashed_name;
 548           if (!ReadHash(&hashed_name) || !IsStringUTF8(hashed_name))
 549             return false;
 550           operators.push_back(new StoreNodeValue<true>(hashed_name));
 551           break;
 552         }
 553         case jtl_foundation::STORE_NODE_HASH: {
 554           std::string hashed_name;
 555           if (!ReadHash(&hashed_name) || !IsStringUTF8(hashed_name))
 556             return false;
 557           operators.push_back(new StoreNodeValue<false>(hashed_name));
 558           break;
 559         }
 560         case jtl_foundation::STORE_NODE_REGISTERABLE_DOMAIN_HASH: {
 561           std::string hashed_name;
 562           if (!ReadHash(&hashed_name) || !IsStringUTF8(hashed_name))
 563             return false;
 564           operators.push_back(new StoreNodeRegisterableDomain(hashed_name));
 565           break;
 566         }
 567         case jtl_foundation::COMPARE_NODE_BOOL: {
 568           bool value = false;
 569           if (!ReadBool(&value))
 570             return false;
 571           operators.push_back(new CompareNodeBool(value));
 572           break;
 573         }
 574         case jtl_foundation::COMPARE_NODE_HASH: {
 575           std::string hashed_value;
 576           if (!ReadHash(&hashed_value))
 577             return false;
 578           operators.push_back(new CompareNodeHash(hashed_value));
 579           break;
 580         }
 581         case jtl_foundation::COMPARE_NODE_HASH_NOT: {
 582           std::string hashed_value;
 583           if (!ReadHash(&hashed_value))
 584             return false;
 585           operators.push_back(new CompareNodeHashNot(hashed_value));
 586           break;
 587         }
 588         case jtl_foundation::COMPARE_NODE_TO_STORED_BOOL: {
 589           std::string hashed_name;
 590           if (!ReadHash(&hashed_name) || !IsStringUTF8(hashed_name))
 591             return false;
 592           operators.push_back(new CompareNodeToStored<true>(hashed_name));
 593           break;
 594         }
 595         case jtl_foundation::COMPARE_NODE_TO_STORED_HASH: {
 596           std::string hashed_name;
 597           if (!ReadHash(&hashed_name) || !IsStringUTF8(hashed_name))
 598             return false;
 599           operators.push_back(new CompareNodeToStored<false>(hashed_name));
 600           break;
 601         }
 602         case jtl_foundation::COMPARE_NODE_SUBSTRING: {
 603           std::string hashed_pattern;
 604           uint32 pattern_length = 0, pattern_sum = 0;
 605           if (!ReadHash(&hashed_pattern))
 606             return false;
 607           if (!ReadUint32(&pattern_length) || pattern_length == 0)
 608             return false;
 609           if (!ReadUint32(&pattern_sum))
 610             return false;
 611           operators.push_back(new CompareNodeSubstring(
 612               hashed_pattern, pattern_length, pattern_sum));
 613           break;
 614         }
 615         case jtl_foundation::STOP_EXECUTING_SENTENCE:
 616           operators.push_back(new StopExecutingSentenceOperation);
 617           break;
 618         case jtl_foundation::END_OF_SENTENCE:
 619           sentence_ended = true;
 620           break;
 621         default:
 622           return false;
 623       }
 624     }
 625     output->swap(operators);
 626     return true;
 627   }
 628
 629   bool HasNextSentence() const {
 630     return next_instruction_index_ < program_.size();
 631   }
 632
 633  private:
 634   // Reads an uint8 and returns whether this operation was successful.
 635   bool ReadUint8(uint8* out) {
 636     DCHECK(out);
 637     if (next_instruction_index_ + 1u > program_.size())
 638       return false;
 639     *out = static_cast<uint8>(program_[next_instruction_index_]);
 640     ++next_instruction_index_;
 641     return true;
 642   }
 643
 644   // Reads an uint32 and returns whether this operation was successful.
 645   bool ReadUint32(uint32* out) {
 646     DCHECK(out);
 647     if (next_instruction_index_ + 4u > program_.size())
 648       return false;
 649     *out = 0u;
 650     for (int i = 0; i < 4; ++i) {
 651       *out >>= 8;
 652       *out |= static_cast<uint8>(program_[next_instruction_index_]) << 24;
 653       ++next_instruction_index_;
 654     }
 655     return true;
 656   }
 657
 658   // Reads an operator code and returns whether this operation was successful.
 659   bool ReadOpCode(uint8* out) { return ReadUint8(out); }
 660
 661   bool ReadHash(std::string* out) {
 662     DCHECK(out);
 663     if (next_instruction_index_ + jtl_foundation::kHashSizeInBytes >
 664         program_.size())
 665       return false;
 666     *out = program_.substr(next_instruction_index_,
 667                            jtl_foundation::kHashSizeInBytes);
 668     next_instruction_index_ += jtl_foundation::kHashSizeInBytes;
 669     DCHECK(jtl_foundation::Hasher::IsHash(*out));
 670     return true;
 671   }
 672
 673   bool ReadBool(bool* out) {
 674     DCHECK(out);
 675     uint8 value = 0;
 676     if (!ReadUint8(&value))
 677       return false;
 678     if (value == 0)
 679       *out = false;
 680     else if (value == 1)
 681       *out = true;
 682     else
 683       return false;
 684     return true;
 685   }
 686
 687   std::string program_;
 688   size_t next_instruction_index_;
 689   DISALLOW_COPY_AND_ASSIGN(Parser);
 690 };
 691
 692 }  // namespace
 693
 694 JtlInterpreter::JtlInterpreter(
 695     const std::string& hasher_seed,
 696     const std::string& program,
 697     const base::DictionaryValue* input)
 698     : hasher_seed_(hasher_seed),
 699       program_(program),
 700       input_(input),
 701       working_memory_(new base::DictionaryValue),
 702       result_(OK) {
 703   DCHECK(input->IsType(base::Value::TYPE_DICTIONARY));
 704 }
 705
 706 JtlInterpreter::~JtlInterpreter() {}
 707
 708 void JtlInterpreter::Execute() {
 709   jtl_foundation::Hasher hasher(hasher_seed_);
 710   Parser parser(program_);
 711   while (parser.HasNextSentence()) {
 712     ScopedVector<Operation> sentence;
 713     if (!parser.ParseNextSentence(&sentence)) {
 714       result_ = PARSE_ERROR;
 715       return;
 716     }
 717     ExecutionContext context(
 718         &hasher, sentence.get(), input_, working_memory_.get());
 719     context.ContinueExecution();
 720     if (context.error()) {
 721       result_ = RUNTIME_ERROR;
 722       return;
 723     }
 724   }
 725 }
 726
 727 bool JtlInterpreter::GetOutputBoolean(const std::string& unhashed_key,
 728                                       bool* output) const {
 729   std::string hashed_key =
 730       jtl_foundation::Hasher(hasher_seed_).GetHash(unhashed_key);
 731   return working_memory_->GetBoolean(hashed_key, output);
 732 }
 733
 734 bool JtlInterpreter::GetOutputString(const std::string& unhashed_key,
 735                                      std::string* output) const {
 736   std::string hashed_key =
 737       jtl_foundation::Hasher(hasher_seed_).GetHash(unhashed_key);
 738   return working_memory_->GetString(hashed_key, output);
 739 }