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