Implement a parser that parses the "Range" HTTP header

Parses "Range" HTTP request header so this request information
can be used in URLRequestFileJob and HttpCache.

Review URL: http://codereview.chromium.org/92006

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@14784 0039d316-1c4b-4281-b951-d872f2087c98

7 files changed, 455 insertions, 2 deletions

diff --git a/net/http/http_byte_range.cc b/net/http/http_byte_range.cc
new file mode 100644
index 0000000..8978d9a
--- /dev/null
+++ b/net/http/http_byte_range.cc
@@ -0,0 +1,76 @@
+// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <algorithm>
+
+#include "net/http/http_byte_range.h"
+
+namespace {
+
+const int64 kPositionNotSpecified = -1;
+
+}  // namespace
+
+namespace net {
+
+HttpByteRange::HttpByteRange()
+    : first_byte_position_(kPositionNotSpecified),
+      last_byte_position_(kPositionNotSpecified),
+      suffix_length_(kPositionNotSpecified),
+      has_computed_bounds_(false) {
+}
+
+bool HttpByteRange::IsSuffixByteRange() const {
+  return suffix_length_ != kPositionNotSpecified;
+}
+
+bool HttpByteRange::HasFirstBytePosition() const {
+  return first_byte_position_ != kPositionNotSpecified;
+}
+
+bool HttpByteRange::HasLastBytePosition() const {
+  return last_byte_position_ != kPositionNotSpecified;
+}
+
+bool HttpByteRange::IsValid() const {
+  if (suffix_length_ > 0)
+    return true;
+  return first_byte_position_ >= 0 &&
+         (last_byte_position_ == kPositionNotSpecified ||
+          last_byte_position_ >= first_byte_position_);
+}
+
+bool HttpByteRange::ComputeBounds(int64 size) {
+  if (size < 0)
+    return false;
+  if (has_computed_bounds_)
+    return false;
+  has_computed_bounds_ = true;
+
+  // Empty values.
+  if (!HasFirstBytePosition() &&
+      !HasLastBytePosition() &&
+      !IsSuffixByteRange()) {
+      first_byte_position_ = 0;
+      last_byte_position_ = size - 1;
+      return true;
+  }
+  if (!IsValid())
+    return false;
+  if (IsSuffixByteRange()) {
+    first_byte_position_ = size - std::min(size, suffix_length_);
+    last_byte_position_ = size - 1;
+    return true;
+  }
+  if (first_byte_position_ < size) {
+    if (HasLastBytePosition())
+      last_byte_position_ = std::min(size - 1, last_byte_position_);
+    else
+      last_byte_position_ = size - 1;
+    return true;
+  }
+  return false;
+}
+
+}  // namespace net
diff --git a/net/http/http_byte_range.h b/net/http/http_byte_range.h
new file mode 100644
index 0000000..a4f52f2
--- /dev/null
+++ b/net/http/http_byte_range.h
@@ -0,0 +1,58 @@
+// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef NET_HTTP_HTTP_BYTE_RANGE_H_
+#define NET_HTTP_HTTP_BYTE_RANGE_H_
+
+#include "base/basictypes.h"
+
+namespace net {
+
+// A container class that represents a "range" specified for range request
+// specified by RFC 2616 Section 14.35.1.
+// http://www.w3.org/Protocols/rfc2616/rfc2616-sec14.html#sec14.35.1
+class HttpByteRange {
+ public:
+  HttpByteRange();
+
+  // Since this class is POD, we use constructor, assignment operator
+  // and destructor provided by compiler.
+  int64 first_byte_position() const { return first_byte_position_; }
+  void set_first_byte_position(int64 value) { first_byte_position_ =  value; }
+
+  int64 last_byte_position() const { return last_byte_position_; }
+  void set_last_byte_position(int64 value) { last_byte_position_ = value; }
+
+  int64 suffix_length() const { return suffix_length_; }
+  void set_suffix_length(int64 value) { suffix_length_ = value; }
+
+  // Returns true if this is a suffix byte range.
+  bool IsSuffixByteRange() const;
+  // Returns true if the first byte position is specified in this request.
+  bool HasFirstBytePosition() const;
+  // Returns true if the last byte position is specified in this request.
+  bool HasLastBytePosition() const;
+
+  // Returns true if this range is valid.
+  bool IsValid() const;
+
+  // A method that when given the size in bytes of a file, adjust the internal
+  // |first_byte_position_| and |last_byte_position_| values according to the
+  // range specified by this object. If the range specified is invalid with
+  // regard to the size or |size| is negative, returns false and there will be
+  // no side effect.
+  // Returns false if this method is called more than once and there will be
+  // no side effect.
+  bool ComputeBounds(int64 size);
+
+ private:
+  int64 first_byte_position_;
+  int64 last_byte_position_;
+  int64 suffix_length_;
+  bool has_computed_bounds_;
+};
+
+}  // namespace net
+
+#endif  // NET_HTTP_HTTP_BYTE_RANGE_H_
diff --git a/net/http/http_byte_range_unittest.cc b/net/http/http_byte_range_unittest.cc
new file mode 100644
index 0000000..6629a7c
--- /dev/null
+++ b/net/http/http_byte_range_unittest.cc
@@ -0,0 +1,78 @@
+// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/http/http_byte_range.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+TEST(HttpByteRangeTest, ValidRanges) {
+  const struct {
+    int64 first_byte_position;
+    int64 last_byte_position;
+    int64 suffix_length;
+    bool valid;
+  } tests[] = {
+    {  -1, -1,  0, false },
+    {   0,  0,  0, true  },
+    { -10,  0,  0, false },
+    {  10,  0,  0, false },
+    {  10, -1,  0, true  },
+    {  -1, -1, -1, false },
+    {  -1, 50,  0, false },
+    {  10, 10000, 0, true },
+    {  -1, -1, 100000, true },
+  };
+
+  for (size_t i = 0; i < ARRAYSIZE_UNSAFE(tests); ++i) {
+    net::HttpByteRange range;
+    range.set_first_byte_position(tests[i].first_byte_position);
+    range.set_last_byte_position(tests[i].last_byte_position);
+    range.set_suffix_length(tests[i].suffix_length);
+    EXPECT_EQ(tests[i].valid, range.IsValid());
+  }
+}
+
+TEST(HttpByteRangeTest, SetInstanceSize) {
+  const struct {
+    int64 first_byte_position;
+    int64 last_byte_position;
+    int64 suffix_length;
+    int64 instance_size;
+    bool expected_return_value;
+    int64 expected_lower_bound;
+    int64 expected_upper_bound;
+  } tests[] = {
+    { -10,  0,  -1,   0, false,  -1,  -1 },
+    {  10,  0,  -1,   0, false,  -1,  -1 },
+    // Zero instance size is valid, this is the case that user has to handle.
+    {  -1, -1,  -1,   0,  true,   0,  -1 },
+    {  -1, -1, 500,   0,  true,   0,  -1 },
+    {  -1, 50,  -1,   0, false,  -1,  -1 },
+    {  -1, -1, 500, 300,  true,   0, 299 },
+    {  -1, -1,  -1, 100,  true,   0,  99 },
+    {  10, -1,  -1, 100,  true,  10,  99 },
+    {  -1, -1, 500, 1000, true, 500, 999 },
+    {  10, 10000, -1, 1000000, true, 10, 10000 },
+  };
+
+  for (size_t i = 0; i < ARRAYSIZE_UNSAFE(tests); ++i) {
+    net::HttpByteRange range;
+    range.set_first_byte_position(tests[i].first_byte_position);
+    range.set_last_byte_position(tests[i].last_byte_position);
+    range.set_suffix_length(tests[i].suffix_length);
+
+    bool return_value = range.ComputeBounds(tests[i].instance_size);
+    EXPECT_EQ(tests[i].expected_return_value, return_value);
+    if (return_value) {
+      EXPECT_EQ(tests[i].expected_lower_bound, range.first_byte_position());
+      EXPECT_EQ(tests[i].expected_upper_bound, range.last_byte_position());
+
+      // Try to call SetInstanceSize the second time.
+      EXPECT_FALSE(range.ComputeBounds(tests[i].instance_size));
+      // And expect there's no side effect.
+      EXPECT_EQ(tests[i].expected_lower_bound, range.first_byte_position());
+      EXPECT_EQ(tests[i].expected_upper_bound, range.last_byte_position());
+      EXPECT_EQ(tests[i].suffix_length, range.suffix_length());
+    }
+  }
+}
diff --git a/net/http/http_util.cc b/net/http/http_util.cc
index 500222a..f3e0835 100644
--- a/net/http/http_util.cc
+++ b/net/http/http_util.cc
@@ -195,6 +195,99 @@ void HttpUtil::ParseContentType(const string& content_type_str,
 }
 
 // static
+// Parse the Range header according to RFC 2616 14.35.1
+// ranges-specifier = byte-ranges-specifier
+// byte-ranges-specifier = bytes-unit "=" byte-range-set
+// byte-range-set  = 1#( byte-range-spec | suffix-byte-range-spec )
+// byte-range-spec = first-byte-pos "-" [last-byte-pos]
+// first-byte-pos  = 1*DIGIT
+// last-byte-pos   = 1*DIGIT
+bool HttpUtil::ParseRanges(const std::string& headers,
+                           std::vector<HttpByteRange>* ranges) {
+  std::string ranges_specifier;
+  HttpUtil::HeadersIterator it(headers.begin(), headers.end(), "\r\n");
+
+  while (it.GetNext()) {
+    // Look for "Range" header.
+    if (!LowerCaseEqualsASCII(it.name(), "range"))
+      continue;
+    ranges_specifier = it.values();
+    // We just care about the first "Range" header, so break here.
+    break;
+  }
+
+  if (ranges_specifier.empty())
+    return false;
+
+  size_t equal_char_offset = ranges_specifier.find('=');
+  if (equal_char_offset == std::string::npos)
+    return false;
+
+  // Try to extract bytes-unit part.
+  std::string::const_iterator bytes_unit_begin = ranges_specifier.begin();
+  std::string::const_iterator bytes_unit_end = bytes_unit_begin +
+                                               equal_char_offset;
+  std::string::const_iterator byte_range_set_begin = bytes_unit_end + 1;
+  std::string::const_iterator byte_range_set_end = ranges_specifier.end();
+
+  TrimLWS(&bytes_unit_begin, &bytes_unit_end);
+  // "bytes" unit identifier is not found.
+  if (!LowerCaseEqualsASCII(bytes_unit_begin, bytes_unit_end, "bytes"))
+    return false;
+
+  ValuesIterator byte_range_set_iterator(byte_range_set_begin,
+                                         byte_range_set_end, ',');
+  while (byte_range_set_iterator.GetNext()) {
+    size_t minus_char_offset = byte_range_set_iterator.value().find('-');
+    // If '-' character is not found, reports failure.
+    if (minus_char_offset == std::string::npos)
+      return false;
+
+    std::string::const_iterator first_byte_pos_begin =
+        byte_range_set_iterator.value_begin();
+    std::string::const_iterator first_byte_pos_end =
+        first_byte_pos_begin +  minus_char_offset;
+    TrimLWS(&first_byte_pos_begin, &first_byte_pos_end);
+    std::string first_byte_pos(first_byte_pos_begin, first_byte_pos_end);
+
+    HttpByteRange range;
+    // Try to obtain first-byte-pos.
+    if (!first_byte_pos.empty()) {
+        int64 first_byte_position = -1;
+        if (!StringToInt64(first_byte_pos, &first_byte_position))
+          return false;
+        range.set_first_byte_position(first_byte_position);
+      }
+
+    std::string::const_iterator last_byte_pos_begin =
+        byte_range_set_iterator.value_begin() + minus_char_offset + 1;
+    std::string::const_iterator last_byte_pos_end =
+        byte_range_set_iterator.value_end();
+    TrimLWS(&last_byte_pos_begin, &last_byte_pos_end);
+    std::string last_byte_pos(last_byte_pos_begin, last_byte_pos_end);
+
+    // We have last-byte-pos or suffix-byte-range-spec in this case.
+    if (!last_byte_pos.empty()) {
+      int64 last_byte_position;
+      if (!StringToInt64(last_byte_pos, &last_byte_position))
+        return false;
+      if (range.HasFirstBytePosition())
+        range.set_last_byte_position(last_byte_position);
+      else
+        range.set_suffix_length(last_byte_position);
+    } else if (!range.HasFirstBytePosition()) {
+      return false;
+    }
+
+    // Do a final check on the HttpByteRange object.
+    if (!range.IsValid())
+      return false;
+    ranges->push_back(range);
+  }
+  return ranges->size() > 0;
+}
+
+// static
 bool HttpUtil::HasHeader(const std::string& headers, const char* name) {
   size_t name_len = strlen(name);
   string::const_iterator it =
diff --git a/net/http/http_util.h b/net/http/http_util.h
index ade6241..ad7e671 100644
--- a/net/http/http_util.h
+++ b/net/http/http_util.h
@@ -1,12 +1,15 @@
-// Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
+// Copyright (c) 2006-2009 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef NET_HTTP_HTTP_UTIL_H_
 #define NET_HTTP_HTTP_UTIL_H_
 
+#include <vector>
+
 #include "base/string_tokenizer.h"
 #include "googleurl/src/gurl.h"
+#include "net/http/http_byte_range.h"
 
 // This is a macro to support extending this string literal at compile time.
 // Please excuse me polluting your global namespace!
@@ -42,6 +45,15 @@ class HttpUtil {
                                std::string* charset,
                                bool *had_charset);
 
+  // Scans the headers and look for the first "Range" header in |headers|,
+  // if "Range" exists and the first one of it is well formatted then returns
+  // true, |ranges| will contain a list of valid ranges. If return
+  // value is false then values in |ranges| should not be used. The format of
+  // "Range" header is defined in RFC 2616 Section 14.35.1.
+  // http://www.w3.org/Protocols/rfc2616/rfc2616-sec14.html#sec14.35.1
+  static bool ParseRanges(const std::string& headers,
+                          std::vector<HttpByteRange>* ranges);
+
   // Scans the '\r\n'-delimited headers for the given header name.  Returns
   // true if a match is found.  Input is assumed to be well-formed.
   // TODO(darin): kill this
diff --git a/net/http/http_util_unittest.cc b/net/http/http_util_unittest.cc
index 87ae3cc..11e3fa3 100644
--- a/net/http/http_util_unittest.cc
+++ b/net/http/http_util_unittest.cc
@@ -1,4 +1,4 @@
-// Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
+// Copyright (c) 2006-2009 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
@@ -513,3 +513,136 @@ TEST(HttpUtilTest, GenerateAcceptCharsetHeader) {
   EXPECT_EQ(std::string("EUC-JP,utf-8;q=0.7,*;q=0.3"),
             HttpUtil::GenerateAcceptCharsetHeader("EUC-JP"));
 }
+
+TEST(HttpUtilTest, ParseRanges) {
+  const struct {
+    const char* headers;
+    bool expected_return_value;
+    size_t expected_ranges_size;
+    const struct {
+      int64 expected_first_byte_position;
+      int64 expected_last_byte_position;
+      int64 expected_suffix_length;
+    } expected_ranges[10];
+  } tests[] = {
+    { "Range: bytes=0-10",
+      true,
+      1,
+      { {0, 10, -1}, }
+    },
+    { "Range: bytes=10-0",
+      false,
+      0,
+      {}
+    },
+    { "Range: BytES=0-10",
+      true,
+      1,
+      { {0, 10, -1}, }
+    },
+    { "Range: megabytes=0-10",
+      false,
+      0,
+      {}
+    },
+    { "Range: bytes0-10",
+      false,
+      0,
+      {}
+    },
+    { "Range: bytes=0-0,0-10,10-20,100-200,100-,-200",
+      true,
+      6,
+      { {0, 0, -1},
+        {0, 10, -1},
+        {10, 20, -1},
+        {100, 200, -1},
+        {100, -1, -1},
+        {-1, -1, 200},
+      }
+    },
+    { "Range: bytes=0-10\r\n"
+      "Range: bytes=0-10,10-20,100-200,100-,-200",
+      true,
+      1,
+      { {0, 10, -1}
+      }
+    },
+    { "Range: bytes=",
+      false,
+      0,
+      {}
+    },
+    { "Range: bytes=-",
+      false,
+      0,
+      {}
+    },
+    { "Range: bytes=0-10-",
+      false,
+      0,
+      {}
+    },
+    { "Range: bytes=-0-10",
+      false,
+      0,
+      {}
+    },
+    { "Range: bytes =0-10\r\n",
+      true,
+      1,
+      { {0, 10, -1}
+      }
+    },
+    { "Range: bytes=  0-10      \r\n",
+      true,
+      1,
+      { {0, 10, -1}
+      }
+    },
+    { "Range: bytes  =   0  -   10      \r\n",
+      true,
+      1,
+      { {0, 10, -1}
+      }
+    },
+    { "Range: bytes=   0-1   0\r\n",
+      false,
+      0,
+      {}
+    },
+    { "Range: bytes=   0-     -10\r\n",
+      false,
+      0,
+      {}
+    },
+    { "Range: bytes=   0  -  1   ,   10 -20,   100- 200 ,  100-,  -200 \r\n",
+      true,
+      5,
+      { {0, 1, -1},
+        {10, 20, -1},
+        {100, 200, -1},
+        {100, -1, -1},
+        {-1, -1, 200},
+      }
+    },
+  };
+
+  for (size_t i = 0; i < ARRAYSIZE_UNSAFE(tests); ++i) {
+    std::vector<net::HttpByteRange> ranges;
+    bool return_value = HttpUtil::ParseRanges(std::string(tests[i].headers),
+                                              &ranges);
+    EXPECT_EQ(tests[i].expected_return_value, return_value);
+    if (return_value) {
+      EXPECT_EQ(tests[i].expected_ranges_size, ranges.size());
+      for (size_t j = 0; j < ranges.size(); ++j) {
+        EXPECT_EQ(tests[i].expected_ranges[j].expected_first_byte_position,
+                  ranges[j].first_byte_position());
+        EXPECT_EQ(tests[i].expected_ranges[j].expected_last_byte_position,
+                  ranges[j].last_byte_position());
+        EXPECT_EQ(tests[i].expected_ranges[j].expected_suffix_length,
+                  ranges[j].suffix_length());
+      }
+    }
+  }
+}
diff --git a/net/net.gyp b/net/net.gyp
index a377e9c..1e25fd1 100644
--- a/net/net.gyp
+++ b/net/net.gyp
@@ -216,6 +216,8 @@
         'http/http_auth_handler_digest.h',
         'http/http_auth_handler_ntlm.cc',
         'http/http_auth_handler_ntlm.h',
+        'http/http_byte_range.cc',
+        'http/http_byte_range.h',
         'http/http_cache.cc',
         'http/http_cache.h',
         'http/http_chunked_decoder.cc',
@@ -432,6 +434,7 @@
         'http/http_auth_handler_basic_unittest.cc',
         'http/http_auth_handler_digest_unittest.cc',
         'http/http_auth_unittest.cc',
+        'http/http_byte_range_unittest.cc',
         'http/http_cache_unittest.cc',
         'http/http_chunked_decoder_unittest.cc',
         'http/http_network_layer_unittest.cc',