src/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 "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"
  12
  13 namespace {
  14
  15 class ExecutionContext;
  16
  17 // An operation in an interpreted program.
  18 class Operation {
  19  public:
  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
  24   // needs to be done.
  25   virtual bool Execute(ExecutionContext* context) = 0;
  26 };
  27
  28 // An execution context of operations.
  29 class ExecutionContext {
  30  public:
  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)
  37       : hasher_(hasher),
  38         sentence_(sentence),
  39         next_instruction_index_(0u),
  40         working_memory_(working_memory),
  41         error_(false) {
  42     stack_.push_back(input);
  43   }
  44   ~ExecutionContext() {}
  45
  46   // Returns true in case of success.
  47   bool ContinueExecution() {
  48     if (error_ || stack_.empty()) {
  49       error_ = true;
  50       return false;
  51     }
  52     if (next_instruction_index_ >= sentence_.size())
  53       return true;
  54
  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;
  60   }
  61
  62   std::string GetHash(const std::string& input) {
  63     return hasher_->GetHash(input);
  64   }
  65
  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) {
  69     DCHECK(hash);
  70     std::string value_as_string;
  71     int tmp_int = 0;
  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))
  78       return false;
  79     *hash = GetHash(value_as_string);
  80     return true;
  81   }
  82
  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_; }
  87
  88  private:
  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.
 102   bool error_;
 103   DISALLOW_COPY_AND_ASSIGN(ExecutionContext);
 104 };
 105
 106 class NavigateOperation : public Operation {
 107  public:
 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.
 118       return true;
 119     }
 120     for (DictionaryValue::Iterator i(*dict); !i.IsAtEnd(); i.Advance()) {
 121       if (context->GetHash(i.key()) != hashed_key_)
 122         continue;
 123       context->stack()->push_back(&i.value());
 124       bool continue_traversal = context->ContinueExecution();
 125       context->stack()->pop_back();
 126       if (!continue_traversal)
 127         return false;
 128     }
 129     return true;
 130   }
 131
 132  private:
 133   std::string hashed_key_;
 134   DISALLOW_COPY_AND_ASSIGN(NavigateOperation);
 135 };
 136
 137 class NavigateAnyOperation : public Operation {
 138  public:
 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)
 150           return false;
 151       }
 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)
 158           return false;
 159       }
 160     } else {
 161       // Do nothing, just ignore this node.
 162     }
 163     return true;
 164   }
 165
 166  private:
 167   DISALLOW_COPY_AND_ASSIGN(NavigateAnyOperation);
 168 };
 169
 170 class NavigateBackOperation : public Operation {
 171  public:
 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;
 180   }
 181
 182  private:
 183   DISALLOW_COPY_AND_ASSIGN(NavigateBackOperation);
 184 };
 185
 186 class StoreValue : public Operation {
 187  public:
 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));
 192     DCHECK(value_);
 193   }
 194   virtual ~StoreValue() {}
 195   virtual bool Execute(ExecutionContext* context) OVERRIDE {
 196     context->working_memory()->Set(hashed_name_, value_->DeepCopy());
 197     return context->ContinueExecution();
 198   }
 199
 200  private:
 201   std::string hashed_name_;
 202   scoped_ptr<Value> value_;
 203   DISALLOW_COPY_AND_ASSIGN(StoreValue);
 204 };
 205
 206 class CompareStoredValue : public Operation {
 207  public:
 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));
 215     DCHECK(value_);
 216     DCHECK(default_value_);
 217   }
 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))
 224       return true;
 225     return context->ContinueExecution();
 226   }
 227
 228  private:
 229   std::string hashed_name_;
 230   scoped_ptr<Value> value_;
 231   scoped_ptr<Value> default_value_;
 232   DISALLOW_COPY_AND_ASSIGN(CompareStoredValue);
 233 };
 234
 235 template<bool ExpectedTypeIsBooleanNotHashable>
 236 class StoreNodeValue : public Operation {
 237  public:
 238   explicit StoreNodeValue(const std::string& hashed_name)
 239       : hashed_name_(hashed_name) {
 240     DCHECK(IsStringUTF8(hashed_name));
 241   }
 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))
 247         return true;
 248       value.reset(context->current_node()->DeepCopy());
 249     } else {
 250       std::string hash;
 251       if (!context->GetValueHash(*context->current_node(), &hash))
 252         return true;
 253       value.reset(new base::StringValue(hash));
 254     }
 255     context->working_memory()->Set(hashed_name_, value.release());
 256     return context->ContinueExecution();
 257   }
 258
 259  private:
 260   std::string hashed_name_;
 261   DISALLOW_COPY_AND_ASSIGN(StoreNodeValue);
 262 };
 263
 264 class CompareNodeBool : public Operation {
 265  public:
 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))
 271       return true;
 272     if (actual_value != value_)
 273       return true;
 274     return context->ContinueExecution();
 275   }
 276
 277  private:
 278   bool value_;
 279   DISALLOW_COPY_AND_ASSIGN(CompareNodeBool);
 280 };
 281
 282 class CompareNodeHash : public Operation {
 283  public:
 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_)
 291       return true;
 292     return context->ContinueExecution();
 293   }
 294
 295  private:
 296   std::string hashed_value_;
 297   DISALLOW_COPY_AND_ASSIGN(CompareNodeHash);
 298 };
 299
 300 class CompareNodeHashNot : public Operation {
 301  public:
 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_)
 309       return true;
 310     return context->ContinueExecution();
 311   }
 312
 313  private:
 314   std::string hashed_value_;
 315   DISALLOW_COPY_AND_ASSIGN(CompareNodeHashNot);
 316 };
 317
 318 template<bool ExpectedTypeIsBooleanNotHashable>
 319 class CompareNodeToStored : public Operation {
 320  public:
 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))
 327       return true;
 328     if (ExpectedTypeIsBooleanNotHashable) {
 329       if (!context->current_node()->IsType(base::Value::TYPE_BOOLEAN) ||
 330           !context->current_node()->Equals(stored_value))
 331         return true;
 332     } else {
 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)
 338         return true;
 339     }
 340     return context->ContinueExecution();
 341   }
 342
 343  private:
 344   std::string hashed_name_;
 345   DISALLOW_COPY_AND_ASSIGN(CompareNodeToStored);
 346 };
 347
 348 class StopExecutingSentenceOperation : public Operation {
 349  public:
 350   StopExecutingSentenceOperation() {}
 351   virtual ~StopExecutingSentenceOperation() {}
 352   virtual bool Execute(ExecutionContext* context) OVERRIDE {
 353     return false;
 354   }
 355
 356  private:
 357   DISALLOW_COPY_AND_ASSIGN(StopExecutingSentenceOperation);
 358 };
 359
 360 class Parser {
 361  public:
 362   explicit Parser(const std::string& program)
 363       : program_(program),
 364         next_instruction_index_(0u) {}
 365   ~Parser() {}
 366   bool ParseNextSentence(ScopedVector<Operation>* output) {
 367     ScopedVector<Operation> operators;
 368     bool sentence_ended = false;
 369     while (next_instruction_index_ < program_.size() && !sentence_ended) {
 370       uint8 op_code = 0;
 371       if (!ReadOpCode(&op_code))
 372         return false;
 373       switch (static_cast<jtl_foundation::OpCodes>(op_code)) {
 374         case jtl_foundation::NAVIGATE: {
 375           std::string hashed_key;
 376           if (!ReadHash(&hashed_key))
 377             return false;
 378           operators.push_back(new NavigateOperation(hashed_key));
 379           break;
 380         }
 381         case jtl_foundation::NAVIGATE_ANY:
 382           operators.push_back(new NavigateAnyOperation);
 383           break;
 384         case jtl_foundation::NAVIGATE_BACK:
 385           operators.push_back(new NavigateBackOperation);
 386           break;
 387         case jtl_foundation::STORE_BOOL: {
 388           std::string hashed_name;
 389           if (!ReadHash(&hashed_name) || !IsStringUTF8(hashed_name))
 390             return false;
 391           bool value = false;
 392           if (!ReadBool(&value))
 393             return false;
 394           operators.push_back(new StoreValue(
 395               hashed_name,
 396               scoped_ptr<Value>(new base::FundamentalValue(value))));
 397           break;
 398         }
 399         case jtl_foundation::COMPARE_STORED_BOOL: {
 400           std::string hashed_name;
 401           if (!ReadHash(&hashed_name) || !IsStringUTF8(hashed_name))
 402             return false;
 403           bool value = false;
 404           if (!ReadBool(&value))
 405             return false;
 406           bool default_value = false;
 407           if (!ReadBool(&default_value))
 408             return false;
 409           operators.push_back(new CompareStoredValue(
 410               hashed_name,
 411               scoped_ptr<Value>(new base::FundamentalValue(value)),
 412               scoped_ptr<Value>(new base::FundamentalValue(default_value))));
 413           break;
 414         }
 415         case jtl_foundation::STORE_HASH: {
 416           std::string hashed_name;
 417           if (!ReadHash(&hashed_name) || !IsStringUTF8(hashed_name))
 418             return false;
 419           std::string hashed_value;
 420           if (!ReadHash(&hashed_value))
 421             return false;
 422           operators.push_back(new StoreValue(
 423               hashed_name,
 424               scoped_ptr<Value>(new base::StringValue(hashed_value))));
 425           break;
 426         }
 427         case jtl_foundation::COMPARE_STORED_HASH: {
 428           std::string hashed_name;
 429           if (!ReadHash(&hashed_name) || !IsStringUTF8(hashed_name))
 430             return false;
 431           std::string hashed_value;
 432           if (!ReadHash(&hashed_value))
 433             return false;
 434           std::string hashed_default_value;
 435           if (!ReadHash(&hashed_default_value))
 436             return false;
 437           operators.push_back(new CompareStoredValue(
 438               hashed_name,
 439               scoped_ptr<Value>(new base::StringValue(hashed_value)),
 440               scoped_ptr<Value>(new base::StringValue(hashed_default_value))));
 441           break;
 442         }
 443         case jtl_foundation::STORE_NODE_BOOL: {
 444           std::string hashed_name;
 445           if (!ReadHash(&hashed_name) || !IsStringUTF8(hashed_name))
 446             return false;
 447           operators.push_back(new StoreNodeValue<true>(hashed_name));
 448           break;
 449         }
 450         case jtl_foundation::STORE_NODE_HASH: {
 451           std::string hashed_name;
 452           if (!ReadHash(&hashed_name) || !IsStringUTF8(hashed_name))
 453             return false;
 454           operators.push_back(new StoreNodeValue<false>(hashed_name));
 455           break;
 456         }
 457         case jtl_foundation::COMPARE_NODE_BOOL: {
 458           bool value = false;
 459           if (!ReadBool(&value))
 460             return false;
 461           operators.push_back(new CompareNodeBool(value));
 462           break;
 463         }
 464         case jtl_foundation::COMPARE_NODE_HASH: {
 465           std::string hashed_value;
 466           if (!ReadHash(&hashed_value))
 467             return false;
 468           operators.push_back(new CompareNodeHash(hashed_value));
 469           break;
 470         }
 471         case jtl_foundation::COMPARE_NODE_HASH_NOT: {
 472           std::string hashed_value;
 473           if (!ReadHash(&hashed_value))
 474             return false;
 475           operators.push_back(new CompareNodeHashNot(hashed_value));
 476           break;
 477         }
 478         case jtl_foundation::COMPARE_NODE_TO_STORED_BOOL: {
 479           std::string hashed_name;
 480           if (!ReadHash(&hashed_name) || !IsStringUTF8(hashed_name))
 481             return false;
 482           operators.push_back(new CompareNodeToStored<true>(hashed_name));
 483           break;
 484         }
 485         case jtl_foundation::COMPARE_NODE_TO_STORED_HASH: {
 486           std::string hashed_name;
 487           if (!ReadHash(&hashed_name) || !IsStringUTF8(hashed_name))
 488             return false;
 489           operators.push_back(new CompareNodeToStored<false>(hashed_name));
 490           break;
 491         }
 492         case jtl_foundation::STOP_EXECUTING_SENTENCE:
 493           operators.push_back(new StopExecutingSentenceOperation);
 494           break;
 495         case jtl_foundation::END_OF_SENTENCE:
 496           sentence_ended = true;
 497           break;
 498         default:
 499           return false;
 500       }
 501     }
 502     output->swap(operators);
 503     return true;
 504   }
 505
 506   bool HasNextSentence() const {
 507     return next_instruction_index_ < program_.size();
 508   }
 509
 510  private:
 511   // Reads an uint8 and returns whether this operation was successful.
 512   bool ReadUint8(uint8* out) {
 513     if (next_instruction_index_ + 1u > program_.size())
 514       return false;
 515     *out = static_cast<uint8>(program_[next_instruction_index_]);
 516     ++next_instruction_index_;
 517     return true;
 518   }
 519
 520   // Reads an operator code and returns whether this operation was successful.
 521   bool ReadOpCode(uint8* out) { return ReadUint8(out); }
 522
 523   bool ReadHash(std::string* out) {
 524     if (next_instruction_index_ + jtl_foundation::kHashSizeInBytes >
 525         program_.size())
 526       return false;
 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));
 531     return true;
 532   }
 533
 534   bool ReadBool(bool* out) {
 535     uint8 value = 0;
 536     if (!ReadUint8(&value))
 537       return false;
 538     if (value == 0)
 539       *out = false;
 540     else if (value == 1)
 541       *out = true;
 542     else
 543       return false;
 544     return true;
 545   }
 546
 547   std::string program_;
 548   size_t next_instruction_index_;
 549   DISALLOW_COPY_AND_ASSIGN(Parser);
 550 };
 551
 552 }  // namespace
 553
 554 JtlInterpreter::JtlInterpreter(
 555     const std::string& hasher_seed,
 556     const std::string& program,
 557     const DictionaryValue* input)
 558     : hasher_seed_(hasher_seed),
 559       program_(program),
 560       input_(input),
 561       working_memory_(new DictionaryValue),
 562       result_(OK) {
 563   DCHECK(input->IsType(Value::TYPE_DICTIONARY));
 564 }
 565
 566 JtlInterpreter::~JtlInterpreter() {}
 567
 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;
 575       return;
 576     }
 577     ExecutionContext context(
 578         &hasher, sentence.get(), input_, working_memory_.get());
 579     context.ContinueExecution();
 580     if (context.error()) {
 581       result_ = RUNTIME_ERROR;
 582       return;
 583     }
 584   }
 585 }
 586
 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);
 592 }
 593
 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);
 599 }