Add duplicate parameter detection to preparser.

src/preparser.cc

Index: src/preparser.cc
diff --git a/src/preparser.cc b/src/preparser.cc
index da83f96aebada421911206773fddd6c64236aa25..d0e825a9f0e0417c0cbf69f0310d90396bc5fd21 100644
--- a/src/preparser.cc
+++ b/src/preparser.cc
@@ -25,6 +25,9 @@
 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
+#include <errno.h>
+#include <math.h>
+
 #include "../include/v8stdint.h"
 #include "unicode.h"
 #include "globals.h"
@@ -32,6 +35,7 @@
 #include "allocation.h"
 #include "utils.h"
 #include "list.h"
+#include "hashmap.h"
 
 #include "scanner-base.h"
 #include "preparse-data-format.h"
@@ -68,27 +72,22 @@ void PreParser::ReportUnexpectedToken(i::Token::Value token) {
   // Four of the tokens are treated specially
   switch (token) {
   case i::Token::EOS:
-    return ReportMessageAt(source_location.beg_pos, source_location.end_pos,
-                           "unexpected_eos", NULL);
+    return ReportMessageAt(source_location, "unexpected_eos", NULL);
   case i::Token::NUMBER:
-    return ReportMessageAt(source_location.beg_pos, source_location.end_pos,
-                           "unexpected_token_number", NULL);
+    return ReportMessageAt(source_location, "unexpected_token_number", NULL);
   case i::Token::STRING:
-    return ReportMessageAt(source_location.beg_pos, source_location.end_pos,
-                           "unexpected_token_string", NULL);
+    return ReportMessageAt(source_location, "unexpected_token_string", NULL);
   case i::Token::IDENTIFIER:
-    return ReportMessageAt(source_location.beg_pos, source_location.end_pos,
+    return ReportMessageAt(source_location,
                            "unexpected_token_identifier", NULL);
   case i::Token::FUTURE_RESERVED_WORD:
-    return ReportMessageAt(source_location.beg_pos, source_location.end_pos,
-                           "unexpected_reserved", NULL);
+    return ReportMessageAt(source_location, "unexpected_reserved", NULL);
   case i::Token::FUTURE_STRICT_RESERVED_WORD:
-    return ReportMessageAt(source_location.beg_pos, source_location.end_pos,
+    return ReportMessageAt(source_location,
                            "unexpected_strict_reserved", NULL);
   default:
     const char* name = i::Token::String(token);
-    ReportMessageAt(source_location.beg_pos, source_location.end_pos,
-                    "unexpected_token", name);
+    ReportMessageAt(source_location, "unexpected_token", name);
   }
 }
 
@@ -98,7 +97,7 @@ void PreParser::ReportUnexpectedToken(i::Token::Value token) {
 void PreParser::CheckOctalLiteral(int beg_pos, int end_pos, bool* ok) {
   i::Scanner::Location octal = scanner_->octal_position();
   if (beg_pos <= octal.beg_pos && octal.end_pos <= end_pos) {
-    ReportMessageAt(octal.beg_pos, octal.end_pos, "strict_octal_literal", NULL);
+    ReportMessageAt(octal, "strict_octal_literal", NULL);
     scanner_->clear_octal_position();
     *ok = false;
   }
@@ -241,7 +240,7 @@ PreParser::Statement PreParser::ParseFunctionDeclaration(bool* ok) {
     if (identifier.IsFutureStrictReserved()) {
       type = "strict_reserved_word";
     }
-    ReportMessageAt(location.beg_pos, location.end_pos, type, NULL);
+    ReportMessageAt(location, type, NULL);
     *ok = false;
   }
   return Statement::FunctionDeclaration();
@@ -298,8 +297,7 @@ PreParser::Statement PreParser::ParseVariableDeclarations(bool accept_IN,
   } else if (peek() == i::Token::CONST) {
     if (strict_mode()) {
       i::Scanner::Location location = scanner_->peek_location();
-      ReportMessageAt(location.beg_pos, location.end_pos,
-                      "strict_const", NULL);
+      ReportMessageAt(location, "strict_const", NULL);
       *ok = false;
       return Statement::Default();
     }
@@ -448,8 +446,7 @@ PreParser::Statement PreParser::ParseWithStatement(bool* ok) {
   Expect(i::Token::WITH, CHECK_OK);
   if (strict_mode()) {
     i::Scanner::Location location = scanner_->location();
-    ReportMessageAt(location.beg_pos, location.end_pos,
-                    "strict_mode_with", NULL);
+    ReportMessageAt(location, "strict_mode_with", NULL);
     *ok = false;
     return Statement::Default();
   }
@@ -584,8 +581,7 @@ PreParser::Statement PreParser::ParseThrowStatement(bool* ok) {
   Expect(i::Token::THROW, CHECK_OK);
   if (scanner_->HasAnyLineTerminatorBeforeNext()) {
     i::JavaScriptScanner::Location pos = scanner_->location();
-    ReportMessageAt(pos.beg_pos, pos.end_pos,
-                    "newline_after_throw", NULL);
+    ReportMessageAt(pos, "newline_after_throw", NULL);
     *ok = false;
     return Statement::Default();
   }
@@ -997,8 +993,7 @@ PreParser::Expression PreParser::ParsePrimaryExpression(bool* ok) {
       if (strict_mode()) {
         Next();
         i::Scanner::Location location = scanner_->location();
-        ReportMessageAt(location.beg_pos, location.end_pos,
-                        "strict_reserved_word", NULL);
+        ReportMessageAt(location, "strict_reserved_word", NULL);
         *ok = false;
         return Expression::Default();
       }
@@ -1079,6 +1074,39 @@ PreParser::Expression PreParser::ParseArrayLiteral(bool* ok) {
   return Expression::Default();
 }
 
+void PreParser::CheckDuplicate(DuplicateFinder* finder,
+                               i::Token::Value property,
+                               int type,
+                               bool* ok) {
+  int old_value;
+  if (property == i::Token::NUMBER) {
+    old_value = finder->AddNumber(scanner_->literal_ascii_string(), type);
+  } else if (scanner_->is_literal_ascii()) {
+    old_value = finder->AddAsciiSymbol(scanner_->literal_ascii_string(),
+                                       type);
+  } else {
+    old_value = finder->AddUC16Symbol(scanner_->literal_uc16_string(), type);
+  }
+  int intersect = old_value & type;
+  if (intersect != 0) {
+    if ((intersect & kValueFlag) != 0) {
+      // Both are data properties.
+      if (!strict_mode()) return;
+      ReportMessageAt(scanner_->location(),
+                      "strict_duplicate_property", NULL);
+    } else if (((old_value ^ type) & kValueFlag) != 0) {
+      // Both a data and an accessor property with the same name.
+      ReportMessageAt(scanner_->location(),
+                      "accessor_data_property", NULL);
+    } else {
+      // Both accessors of the same type.
+      ReportMessageAt(scanner_->location(),
+                      "accessor_get_set", NULL);
+    }
+    *ok = false;
+  }
+}
+
 
 PreParser::Expression PreParser::ParseObjectLiteral(bool* ok) {
   // ObjectLiteral ::
@@ -1088,6 +1116,7 @@ PreParser::Expression PreParser::ParseObjectLiteral(bool* ok) {
   //    )*[','] '}'
 
   Expect(i::Token::LBRACE, CHECK_OK);
+  DuplicateFinder duplicate_finder;
   while (peek() != i::Token::RBRACE) {
     i::Token::Value next = peek();
     switch (next) {
@@ -1112,24 +1141,30 @@ PreParser::Expression PreParser::ParseObjectLiteral(bool* ok) {
             if (!is_keyword) {
               LogSymbol();
             }
+            int type = is_getter ? kGetterProperty : kSetterProperty;
+            CheckDuplicate(&duplicate_finder, name, type, CHECK_OK);
             ParseFunctionLiteral(CHECK_OK);
             if (peek() != i::Token::RBRACE) {
               Expect(i::Token::COMMA, CHECK_OK);
             }
             continue;  // restart the while
         }
+        CheckDuplicate(&duplicate_finder, next, kValueProperty, CHECK_OK);
         break;
       }
       case i::Token::STRING:
         Consume(next);
+        CheckDuplicate(&duplicate_finder, next, kValueProperty, CHECK_OK);
         GetStringSymbol();
         break;
       case i::Token::NUMBER:
         Consume(next);
+        CheckDuplicate(&duplicate_finder, next, kValueProperty, CHECK_OK);
         break;
       default:
         if (i::Token::IsKeyword(next)) {
           Consume(next);
+          CheckDuplicate(&duplicate_finder, next, kValueProperty, CHECK_OK);
         } else {
           // Unexpected token.
           *ok = false;
@@ -1154,9 +1189,7 @@ PreParser::Expression PreParser::ParseRegExpLiteral(bool seen_equal,
                                                     bool* ok) {
   if (!scanner_->ScanRegExpPattern(seen_equal)) {
     Next();
-    i::JavaScriptScanner::Location location = scanner_->location();
-    ReportMessageAt(location.beg_pos, location.end_pos,
-                    "unterminated_regexp", NULL);
+    ReportMessageAt(scanner_->location(), "unterminated_regexp", NULL);
     *ok = false;
     return Expression::Default();
   }
@@ -1165,9 +1198,7 @@ PreParser::Expression PreParser::ParseRegExpLiteral(bool seen_equal,
 
   if (!scanner_->ScanRegExpFlags()) {
     Next();
-    i::JavaScriptScanner::Location location = scanner_->location();
-    ReportMessageAt(location.beg_pos, location.end_pos,
-                    "invalid_regexp_flags", NULL);
+    ReportMessageAt(scanner_->location(), "invalid_regexp_flags", NULL);
     *ok = false;
     return Expression::Default();
   }
@@ -1212,6 +1243,7 @@ PreParser::Expression PreParser::ParseFunctionLiteral(bool* ok) {
   Expect(i::Token::LPAREN, CHECK_OK);
   int start_position = scanner_->location().beg_pos;
   bool done = (peek() == i::Token::RPAREN);
+  DuplicateFinder duplicate_finder;
   while (!done) {
     Identifier id = ParseIdentifier(CHECK_OK);
     if (!id.IsValidStrictVariable()) {
@@ -1220,6 +1252,20 @@ PreParser::Expression PreParser::ParseFunctionLiteral(bool* ok) {
                                     id,
                                     CHECK_OK);
     }
+    int prev_value;
+    if (scanner_->is_literal_ascii()) {
+      prev_value =
+          duplicate_finder.AddAsciiSymbol(scanner_->literal_ascii_string(), 1);
+    } else {
+      prev_value =
+          duplicate_finder.AddUC16Symbol(scanner_->literal_uc16_string(), 1);
+    }
+
+    if (prev_value != 0) {
+      SetStrictModeViolation(scanner_->location(),
+                             "strict_param_dupe",
+                             CHECK_OK);
+    }
     done = (peek() == i::Token::RPAREN);
     if (!done) {
       Expect(i::Token::COMMA, CHECK_OK);
@@ -1371,13 +1417,18 @@ void PreParser::SetStrictModeViolation(i::Scanner::Location location,
                                        const char* type,
                                        bool* ok) {
   if (strict_mode()) {
-    ReportMessageAt(location.beg_pos, location.end_pos, type, NULL);
+    ReportMessageAt(location, type, NULL);
     *ok = false;
     return;
   }
   // Delay report in case this later turns out to be strict code
   // (i.e., for function names and parameters prior to a "use strict"
   // directive).
+  // It's safe to overwrite an existing violation.
+  // It's either from a function that turned out to be non-strict,
+  // or it's in the current function (and we just need to report
+  // one error), or it's in a unclosed nesting function that wasn't
+  // strict (otherwise we would already be in strict mode).
   strict_mode_violation_location_ = location;
   strict_mode_violation_type_ = type;
 }
@@ -1389,11 +1440,9 @@ void PreParser::CheckDelayedStrictModeViolation(int beg_pos,
   i::Scanner::Location location = strict_mode_violation_location_;
   if (location.IsValid() &&
       location.beg_pos > beg_pos && location.end_pos < end_pos) {
-    ReportMessageAt(location.beg_pos, location.end_pos,
-                    strict_mode_violation_type_, NULL);
+    ReportMessageAt(location, strict_mode_violation_type_, NULL);
     *ok = false;
   }
-  strict_mode_violation_location_ = i::Scanner::Location::invalid();
 }
 
 
@@ -1408,7 +1457,7 @@ void PreParser::StrictModeIdentifierViolation(i::Scanner::Location location,
     type = "strict_reserved_word";
   }
   if (strict_mode()) {
-    ReportMessageAt(location.beg_pos, location.end_pos, type, NULL);
+    ReportMessageAt(location, type, NULL);
     *ok = false;
     return;
   }
@@ -1460,4 +1509,141 @@ bool PreParser::peek_any_identifier() {
          next == i::Token::FUTURE_RESERVED_WORD ||
          next == i::Token::FUTURE_STRICT_RESERVED_WORD;
 }
+
+
+int DuplicateFinder::AddAsciiSymbol(i::Vector<const char> key, int value) {
+  return AddSymbol(i::Vector<const byte>::cast(key), true, value);
+}
+
+int DuplicateFinder::AddUC16Symbol(i::Vector<const uint16_t> key, int value) {
+  return AddSymbol(i::Vector<const byte>::cast(key), false, value);
+}
+
+int DuplicateFinder::AddSymbol(i::Vector<const byte> key,
+                               bool is_ascii,
+                               int value) {
+  uint32_t hash = Hash(key, is_ascii);
+  byte* encoding = BackupKey(key, is_ascii);
+  i::HashMap::Entry* entry = map_->Lookup(encoding, hash, true);
+  int old_value = static_cast<int>(reinterpret_cast<intptr_t>(entry->value));
+  entry->value =
+    reinterpret_cast<void*>(static_cast<intptr_t>(value | old_value));
+  return old_value;
+}
+
+
+int DuplicateFinder::AddNumber(i::Vector<const char> key, int value) {
+  // Quick check for already being in canonical form.
+  if (IsNumberCanonical(key)) {
+    return AddAsciiSymbol(key, value);
+  }
+
+  // TODO(lrn): Use correct string->number->string conversions that
+  // generate the same string as v8's ToString(ToNumber(literal)).
+  // Current solution doesn't handle octal, and probably doesn't
+  // generate the same string in edge cases.
+  double double_value = 0.0;
+  double_value = strtod(key.start(), NULL);
+  int length;
+  if (errno == ERANGE && double_value == HUGE_VAL) {
+    // Overflow.
+    // Negative overflow (-HUGE_VAL) cannit happen as number literals
+    // don't have signs.
+    // Underflow is handled by the default code, since it returns 0.
+    length = 8;  // strlen("Infinity");
+    memcpy(number_buffer_, "Infinity", length);
+  } else {
+    length = snprintf(number_buffer_, kBufferSize, "%g", double_value);
+  }
+  return AddAsciiSymbol(i::Vector<const char>(number_buffer_, length), value);
+}
+
+
+bool DuplicateFinder::IsNumberCanonical(i::Vector<const char> number) {
+  // Test for a safe approximation of number literals that are already
+  // in canonical form: max 15 digits, no leading zeroes, except an
+  // integer part that is a single zero, and no trailing zeros below
+  // the decimal point.
+  int pos = 0;
+  int length = number.length();
+  if (number.length() > 15) return false;
+  if (number[pos] == '0') {
+    pos++;
+  } else {
+    while (pos < length &&
+           static_cast<unsigned>(number[pos] - '0') <= ('9' - '0')) pos++;
+  }
+  if (length == pos) return true;
+  if (number[pos] != '.') return false;
+  pos++;
+  bool invalid_last_digit = true;
+  while (pos < length) {
+    byte digit = number[pos] - '0';
+    if (digit > '9' - '0') return false;
+    invalid_last_digit = (digit == 0);
+    pos++;
+  }
+  return !invalid_last_digit;
+}
+
+
+uint32_t DuplicateFinder::Hash(i::Vector<const byte> key, bool is_ascii) {
+  // Primitive hash function, almost identical to the one used
+  // for strings (except that it's seeded by the length and ASCII-ness).
+  int length = key.length();
+  uint32_t hash = (length << 1) | (is_ascii ? 1 : 0) ;
+  for (int i = 0; i < length; i++) {
+    uint32_t c = key[i];
+    hash = (hash + c) * 1025;
+    hash ^= (hash >> 6);
+  }
+  return hash;
+}
+
+
+bool DuplicateFinder::Match(void* first, void* second) {
+  // Decode lengths.
+  // Length + ASCII-bit is encoded as base 128, most significant heptet first,
+  // with a 8th bit being non-zero while there are more heptets.
+  // The value encodes the number of bytes following, and whether the original
+  // was ASCII.
+  byte* s1 = reinterpret_cast<byte*>(first);
+  byte* s2 = reinterpret_cast<byte*>(second);
+  uint32_t length_ascii_field = 0;
+  byte c1;
+  do {
+    c1 = *s1;
+    if (c1 != *s2) return false;
+    length_ascii_field = (length_ascii_field << 7) | (c1 & 0x7f);
+    s1++;
+    s2++;
+  } while ((c1 & 0x80) != 0);
+  int length = static_cast<int>(length_ascii_field >> 1);
+  return memcmp(s1, s2, length) == 0;
+}
+
+
+byte* DuplicateFinder::BackupKey(i::Vector<const byte> bytes,
+                                       bool is_ascii) {
+  uint32_t ascii_length = (bytes.length() << 1) | (is_ascii ? 1 : 0);
+  backing_store_.StartSequence();
+  // Emit ascii_length as base-128 encoded number, with the 7th bit set
+  // on the byte of every heptet except the last, least significant, one.
+  if (ascii_length >= (1 << 7)) {
+    if (ascii_length >= (1 << 14)) {
+      if (ascii_length >= (1 << 21)) {
+        if (ascii_length >= (1 << 28)) {
+          backing_store_.Add(static_cast<byte>((ascii_length >> 28) | 0x80));
+        }
+        backing_store_.Add(static_cast<byte>((ascii_length >> 21) | 0x80u));
+      }
+      backing_store_.Add(static_cast<byte>((ascii_length >> 14) | 0x80u));
+    }
+    backing_store_.Add(static_cast<byte>((ascii_length >> 7) | 0x80u));
+  }
+  backing_store_.Add(static_cast<byte>(ascii_length & 0x7f));
+
+  backing_store_.AddBlock(bytes);
+  return backing_store_.EndSequence().start();
+}
 } }  // v8::preparser