use StringPiece for makefile deps

Because of this, MakefileParser now returns pointers into the source
makefile string rather than allocating new strings.  Despite needing
to take the result and stuff it into a new string anyway to canonicalize
it, this takes another 50ms or so off the null Chrome build, likely
due to the vector used in MakefileParser changing to a type that doesn't
use any allocations.

(I also experimented with making the vector reserve an initial size but
didn't see any performance impact.)

5 files changed, 77 insertions, 12 deletions

diff --git a/src/graph.cc b/src/graph.cc
index c43cf70..5c37ac0 100644
--- a/src/graph.cc
+++ b/src/graph.cc
@@ -159,18 +159,20 @@ bool Edge::LoadDepFile(State* state, DiskInterface* disk_interface,
   }
 
   // Check that this depfile matches our output.
-  if (outputs_[0]->file_->path_ != makefile.out_) {
+  StringPiece opath = StringPiece(outputs_[0]->file_->path_);
+  if (opath != makefile.out_) {
     *err = "expected makefile to mention '" + outputs_[0]->file_->path_ + "', "
-           "got '" + makefile.out_ + "'";
+        "got '" + makefile.out_.AsString() + "'";
     return false;
   }
 
   // Add all its in-edges.
-  for (vector<string>::iterator i = makefile.ins_.begin();
+  for (vector<StringPiece>::iterator i = makefile.ins_.begin();
        i != makefile.ins_.end(); ++i) {
-    CanonicalizePath(&*i);
+    string path(i->str_, i->len_);
+    CanonicalizePath(&path);
 
-    Node* node = state->GetNode(*i);
+    Node* node = state->GetNode(path);
     inputs_.insert(inputs_.end() - order_only_deps_, node);
     node->out_edges_.push_back(this);
     ++implicit_deps_;
diff --git a/src/parsers.cc b/src/parsers.cc
index 849a3e1..567be6b 100644
--- a/src/parsers.cc
+++ b/src/parsers.cc
@@ -148,15 +148,24 @@ bool Tokenizer::ExpectIdent(const char* expected, string* err) {
   return true;
 }
 
-bool Tokenizer::ReadIdent(string* out) {
+bool Tokenizer::ReadIdent(StringPiece* out) {
   PeekToken();
   if (token_.type_ != Token::IDENT)
     return false;
-  out->assign(token_.pos_, token_.end_ - token_.pos_);
+  out->str_ = token_.pos_;
+  out->len_ = token_.end_ - token_.pos_;
   ConsumeToken();
   return true;
 }
 
+bool Tokenizer::ReadIdent(string* out) {
+  StringPiece token;
+  if (!ReadIdent(&token))
+    return false;
+  out->assign(token.str_, token.len_);
+  return true;
+}
+
 // A note on backslashes in Makefiles, from reading the docs:
 // Backslash-newline is the line continuation character.
 // Backslash-# escapes a # (otherwise meaningful as a comment start).
@@ -276,7 +285,7 @@ bool MakefileParser::Parse(const string& input, string* err) {
   if (!tokenizer_.ExpectToken(Token::COLON, err))
     return false;
   while (tokenizer_.PeekToken() == Token::IDENT) {
-    string in;
+    StringPiece in;
     tokenizer_.ReadIdent(&in);
     ins_.push_back(in);
   }
diff --git a/src/parsers.h b/src/parsers.h
index bdc88d2..6bdca77 100644
--- a/src/parsers.h
+++ b/src/parsers.h
@@ -21,6 +21,8 @@
 
 using namespace std;
 
+#include "string_piece.h"
+
 struct BindingEnv;
 
 /// A single parsed token in an input stream.
@@ -78,6 +80,7 @@ struct Tokenizer {
   bool Newline(string* err);
   bool ExpectToken(Token::Type expected, string* err);
   bool ExpectIdent(const char* expected, string* err);
+  bool ReadIdent(StringPiece* out);
   bool ReadIdent(string* out);
   bool ReadToNewline(string* text, string* err,
                      size_t max_length=std::numeric_limits<size_t>::max());
@@ -102,8 +105,8 @@ struct MakefileParser {
   bool Parse(const string& input, string* err);
 
   Tokenizer tokenizer_;
-  string out_;
-  vector<string> ins_;
+  StringPiece out_;
+  vector<StringPiece> ins_;
 };
 
 struct EvalString;
diff --git a/src/parsers_test.cc b/src/parsers_test.cc
index 5e2746d..c1c33a2 100644
--- a/src/parsers_test.cc
+++ b/src/parsers_test.cc
@@ -474,7 +474,7 @@ TEST(MakefileParser, Basic) {
 "build/ninja.o: ninja.cc ninja.h eval_env.h manifest_parser.h\n",
       &err));
   ASSERT_EQ("", err);
-  EXPECT_EQ("build/ninja.o", parser.out_);
+  EXPECT_EQ("build/ninja.o", parser.out_.AsString());
   EXPECT_EQ(4u, parser.ins_.size());
 }
 
@@ -496,6 +496,6 @@ TEST(MakefileParser, Continuation) {
 "  bar.h baz.h\n",
       &err));
   ASSERT_EQ("", err);
-  EXPECT_EQ("foo.o", parser.out_);
+  EXPECT_EQ("foo.o", parser.out_.AsString());
   EXPECT_EQ(2u, parser.ins_.size());
 }
diff --git a/src/string_piece.h b/src/string_piece.h
new file mode 100644
index 0000000..0e55afb
--- /dev/null
+++ b/src/string_piece.h
@@ -0,0 +1,51 @@
+// Copyright 2011 Google Inc. All Rights Reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef NINJA_STRINGPIECE_H_
+#define NINJA_STRINGPIECE_H_
+
+#include <string>
+
+using namespace std;
+
+#include <string.h>
+
+/// StringPiece represents a slice of a string whose memory is managed
+/// externally.  It is useful for reducing the number of std::strings
+/// we need to allocate.
+struct StringPiece {
+  StringPiece() : str_(NULL), len_(0) {}
+
+  /// The constructors intentionally allow for implicit conversions.
+  StringPiece(const string& str) : str_(str.data()), len_(str.size()) {}
+  StringPiece(const char* str) : str_(str), len_(strlen(str)) {}
+
+  bool operator==(const StringPiece& other) const {
+    return len_ == other.len_ && memcmp(str_, other.str_, len_) == 0;
+  }
+  bool operator!=(const StringPiece& other) const {
+    return !(*this == other);
+  }
+
+  /// Convert the slice into a full-fledged std::string, copying the
+  /// data into a new string.
+  string AsString() const {
+    return string(str_, len_);
+  }
+
+  const char* str_;
+  int len_;
+};
+
+#endif  // NINJA_BROWSE_H_