strutil.cc - platform/build/kati - Gitiles

 // Copyright 2015 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.

 // +build ignore

 #include "strutil.h"

 #include <ctype.h>
 #include <limits.h>
 #include <unistd.h>

 #include <algorithm>
 #include <functional>
 #include <stack>
 #include <utility>

 #ifdef __SSE4_2__
 #include <smmintrin.h>
 #endif

 #include "log.h"

 static bool isSpace(char c) {
   return (9 <= c && c <= 13) || c == 32;
 }

 #ifdef __SSE4_2__
 static int SkipUntilSSE42(const char* s, int len,
                           const char* ranges, int ranges_size) {
   __m128i ranges16 = _mm_loadu_si128((const __m128i*)ranges);
   len &= ~15;
   int i = 0;
   while (i < len) {
     __m128i b16 = _mm_loadu_si128((const __m128i*)(s + i));
     int r = _mm_cmpestri(
         ranges16, ranges_size, b16, len - i,
         _SIDD_LEAST_SIGNIFICANT | _SIDD_CMP_RANGES | _SIDD_UBYTE_OPS);
     if (r != 16) {
       return i + r;
     }
     i += 16;
   }
   return len;
 }
 #endif

 template <typename Cond>
 static int SkipUntil(const char* s, int len,
                      const char* ranges UNUSED, int ranges_size UNUSED,
                      Cond cond) {
   int i = 0;
 #ifdef __SSE4_2__
   i += SkipUntilSSE42(s, len, ranges, ranges_size);
 #endif
   for (; i < len; i++) {
     if (cond(s[i]))
       break;
   }
   return i;
 }

 WordScanner::Iterator& WordScanner::Iterator::operator++() {
   int len = static_cast<int>(in->size());
   for (s = i + 1; s < len; s++) {
     if (!isSpace((*in)[s]))
       break;
   }
   if (s >= len) {
     in = NULL;
     s = 0;
     i = 0;
     return *this;
   }

   static const char ranges[] = "\x09\x0d  ";
   // It's intentional we are not using isSpace here. It seems with
   // lambda the compiler generates better code.
   i = s + SkipUntil(in->data() + s, len - s, ranges, 4,
                     [](char c) { return (9 <= c && c <= 13) || c == 32; });
   return *this;
 }

 StringPiece WordScanner::Iterator::operator*() const {
   return in->substr(s, i - s);
 }

 WordScanner::WordScanner(StringPiece in)
     : in_(in) {
 }

 WordScanner::Iterator WordScanner::begin() const {
   Iterator iter;
   iter.in = &in_;
   iter.s = 0;
   iter.i = -1;
   ++iter;
   return iter;
 }

 WordScanner::Iterator WordScanner::end() const {
   Iterator iter;
   iter.in = NULL;
   iter.s = 0;
   iter.i = 0;
   return iter;
 }

 void WordScanner::Split(vector<StringPiece>* o) {
   for (StringPiece t : *this)
     o->push_back(t);
 }

 WordWriter::WordWriter(string* o)
     : out_(o),
       needs_space_(false) {
 }

 void WordWriter::MaybeAddWhitespace() {
   if (needs_space_) {
     out_->push_back(' ');
   } else {
     needs_space_ = true;
   }
 }

 void WordWriter::Write(StringPiece s) {
   MaybeAddWhitespace();
   AppendString(s, out_);
 }

 ScopedTerminator::ScopedTerminator(StringPiece s)
     : s_(s), c_(s[s.size()]) {
   const_cast<char*>(s_.data())[s_.size()] = '\0';
 }

 ScopedTerminator::~ScopedTerminator() {
   const_cast<char*>(s_.data())[s_.size()] = c_;
 }

 void AppendString(StringPiece str, string* out) {
   out->append(str.begin(), str.end());
 }

 bool HasPrefix(StringPiece str, StringPiece prefix) {
   ssize_t size_diff = str.size() - prefix.size();
   return size_diff >= 0 && str.substr(0, prefix.size()) == prefix;
 }

 bool HasSuffix(StringPiece str, StringPiece suffix) {
   ssize_t size_diff = str.size() - suffix.size();
   return size_diff >= 0 && str.substr(size_diff) == suffix;
 }

 bool HasWord(StringPiece str, StringPiece w) {
   size_t found = str.find(w);
   if (found == string::npos)
     return false;
   if (found != 0 && !isSpace(str[found-1]))
     return false;
   size_t end = found + w.size();
   if (end != str.size() && !isSpace(str[end]))
     return false;
   return true;
 }

 StringPiece TrimPrefix(StringPiece str, StringPiece prefix) {
   ssize_t size_diff = str.size() - prefix.size();
   if (size_diff < 0 || str.substr(0, prefix.size()) != prefix)
     return str;
   return str.substr(prefix.size());
 }

 StringPiece TrimSuffix(StringPiece str, StringPiece suffix) {
   ssize_t size_diff = str.size() - suffix.size();
   if (size_diff < 0 || str.substr(size_diff) != suffix)
     return str;
   return str.substr(0, size_diff);
 }

 Pattern::Pattern(StringPiece pat)
     : pat_(pat), percent_index_(pat.find('%')) {
 }

 bool Pattern::Match(StringPiece str) const {
   if (percent_index_ == string::npos)
     return str == pat_;
   return MatchImpl(str);
 }

 bool Pattern::MatchImpl(StringPiece str) const {
   return (HasPrefix(str, pat_.substr(0, percent_index_)) &&
           HasSuffix(str, pat_.substr(percent_index_ + 1)));
 }

 StringPiece Pattern::Stem(StringPiece str) const {
   if (!Match(str))
     return "";
   return str.substr(percent_index_,
                     str.size() - (pat_.size() - percent_index_ - 1));
 }

 void Pattern::AppendSubst(StringPiece str, StringPiece subst,
                           string* out) const {
   if (percent_index_ == string::npos) {
     if (str == pat_) {
       AppendString(subst, out);
       return;
     } else {
       AppendString(str, out);
       return;
     }
   }

   if (MatchImpl(str)) {
     size_t subst_percent_index = subst.find('%');
     if (subst_percent_index == string::npos) {
       AppendString(subst, out);
       return;
     } else {
       AppendString(subst.substr(0, subst_percent_index), out);
       AppendString(str.substr(percent_index_,
                               str.size() - pat_.size() + 1), out);
       AppendString(subst.substr(subst_percent_index + 1), out);
       return;
     }
   }
   AppendString(str, out);
 }

 void Pattern::AppendSubstRef(StringPiece str, StringPiece subst,
                              string* out) const {
   if (percent_index_ != string::npos && subst.find('%') != string::npos) {
     AppendSubst(str, subst, out);
     return;
   }
   StringPiece s = TrimSuffix(str, pat_);
   out->append(s.begin(), s.end());
   out->append(subst.begin(), subst.end());
 }

 string NoLineBreak(const string& s) {
   size_t index = s.find('\n');
   if (index == string::npos)
     return s;
   string r = s;
   while (index != string::npos) {
     r = r.substr(0, index) + "\\n" + r.substr(index + 1);
     index = r.find('\n', index + 2);
   }
   return r;
 }

 StringPiece TrimLeftSpace(StringPiece s) {
   size_t i = 0;
   for (; i < s.size(); i++) {
     if (isSpace(s[i]))
       continue;
     char n = s.get(i+1);
     if (s[i] == '\\' && (n == '\r' || n == '\n')) {
       i++;
       continue;
     }
     break;
   }
   return s.substr(i, s.size() - i);
 }

 StringPiece TrimRightSpace(StringPiece s) {
   size_t i = 0;
   for (; i < s.size(); i++) {
     char c = s[s.size() - 1 - i];
     if (isSpace(c)) {
       if ((c == '\r' || c == '\n') && s.get(s.size() - 2 - i) == '\\')
         i++;
       continue;
     }
     break;
   }
   return s.substr(0, s.size() - i);
 }

 StringPiece TrimSpace(StringPiece s) {
   return TrimRightSpace(TrimLeftSpace(s));
 }

 StringPiece Dirname(StringPiece s) {
   size_t found = s.rfind('/');
   if (found == string::npos)
     return StringPiece(".");
   if (found == 0)
     return StringPiece("");
   return s.substr(0, found);
 }

 StringPiece Basename(StringPiece s) {
   size_t found = s.rfind('/');
   if (found == string::npos || found == 0)
     return s;
   return s.substr(found + 1);
 }

 StringPiece GetExt(StringPiece s) {
   size_t found = s.rfind('.');
   if (found == string::npos)
     return StringPiece("");
   return s.substr(found);
 }

 StringPiece StripExt(StringPiece s) {
   size_t slash_index = s.rfind('/');
   size_t found = s.rfind('.');
   if (found == string::npos ||
       (slash_index != string::npos && found < slash_index))
     return s;
   return s.substr(0, found);
 }

 void NormalizePath(string* o) {
   if (o->empty())
     return;
   size_t start_index = 0;
   if ((*o)[0] == '/')
     start_index++;
   size_t j = start_index;
   size_t prev_start = start_index;
   for (size_t i = start_index; i <= o->size(); i++) {
     char c = (*o)[i];
     if (c != '/' && c != 0) {
       (*o)[j] = c;
       j++;
       continue;
     }

     StringPiece prev_dir = StringPiece(o->data() + prev_start, j - prev_start);
     if (prev_dir == ".") {
       j--;
     } else if (prev_dir == ".." && j != 2 /* .. */) {
       if (j == 3) {
         // /..
         j = start_index;
       } else {
         size_t orig_j = j;
         j -= 4;
         j = o->rfind('/', j);
         if (j == string::npos) {
           j = start_index;
         } else {
           j++;
         }
         if (StringPiece(o->data() + j, 3) == "../") {
           j = orig_j;
           (*o)[j] = c;
           j++;
         }
       }
     } else if (!prev_dir.empty()) {
       if (c) {
         (*o)[j] = c;
         j++;
       }
     }
     prev_start = j;
   }
   if (j > 1 && (*o)[j-1] == '/')
     j--;
   o->resize(j);
 }

 void AbsPath(StringPiece s, string* o) {
   if (s.get(0) == '/') {
     o->clear();
   } else {
     char buf[PATH_MAX];
     if (!getcwd(buf, PATH_MAX)) {
       fprintf(stderr, "getcwd failed\n");
       CHECK(false);
     }

     CHECK(buf[0] == '/');
     *o = buf;
     *o += '/';
   }
   AppendString(s, o);
   NormalizePath(o);
 }

 template<typename Cond>
 size_t FindOutsideParenImpl(StringPiece s, Cond cond) {
   bool prev_backslash = false;
   stack<char> paren_stack;
   for (size_t i = 0; i < s.size(); i++) {
     char c = s[i];
     if (cond(c) && paren_stack.empty() && !prev_backslash) {
       return i;
     }
     switch (c) {
       case '(':
         paren_stack.push(')');
         break;
       case '{':
         paren_stack.push('}');
         break;

       case ')':
       case '}':
         if (!paren_stack.empty() && c == paren_stack.top()) {
           paren_stack.pop();
         }
         break;
     }
     prev_backslash = c == '\\' && !prev_backslash;
   }
   return string::npos;
 }

 size_t FindOutsideParen(StringPiece s, char c) {
   return FindOutsideParenImpl(s, [&c](char d){return c == d;});
 }

 size_t FindTwoOutsideParen(StringPiece s, char c1, char c2) {
   return FindOutsideParenImpl(s, [&c1, &c2](char d){
       return d == c1 || d == c2;
     });
 }

 size_t FindThreeOutsideParen(StringPiece s, char c1, char c2, char c3) {
   return FindOutsideParenImpl(s, [&c1, &c2, &c3](char d){
       return d == c1 || d == c2 || d == c3;
     });
 }

 size_t FindEndOfLine(StringPiece s, size_t e, size_t* lf_cnt) {
   static const char ranges[] = "\0\0\n\n\\\\";
   while (e < s.size()) {
     e += SkipUntil(s.data() + e, s.size() - e, ranges, 6,
                    [](char c) { return c == 0 || c == '\n' || c == '\\'; });
     if (e >= s.size()) {
       CHECK(s.size() == e);
       break;
     }
     char c = s[e];
     if (c == '\0')
       break;
     if (c == '\\') {
       if (s[e+1] == '\n') {
         e += 2;
         ++*lf_cnt;
       } else if (s[e+1] == '\r' && s[e+2] == '\n') {
         e += 3;
         ++*lf_cnt;
       } else if (s[e+1] == '\\') {
         e += 2;
       } else {
         e++;
       }
     } else if (c == '\n') {
       ++*lf_cnt;
       return e;
     }
   }
   return e;
 }

 StringPiece TrimLeadingCurdir(StringPiece s) {
   while (s.substr(0, 2) == "./")
     s = s.substr(2);
   return s;
 }

 void FormatForCommandSubstitution(string* s) {
   while ((*s)[s->size()-1] == '\n')
     s->pop_back();
   for (size_t i = 0; i < s->size(); i++) {
     if ((*s)[i] == '\n')
       (*s)[i] = ' ';
   }
 }

 string SortWordsInString(StringPiece s) {
   vector<string> toks;
   for (StringPiece tok : WordScanner(s)) {
     toks.push_back(tok.as_string());
   }
   sort(toks.begin(), toks.end());
   return JoinStrings(toks, " ");
 }

 string ConcatDir(StringPiece b, StringPiece n) {
   string r;
   if (!b.empty()) {
     b.AppendToString(&r);
     r += '/';
   }
   n.AppendToString(&r);
   NormalizePath(&r);
   return r;
 }

 string EchoEscape(const string &str) {
   const char *in = str.c_str();
   string buf;
   for (; *in; in++) {
     switch(*in) {
       case '\\':
         buf += "\\\\\\\\";
         break;
       case '\n':
         buf += "\\n";
         break;
       case '"':
         buf += "\\\"";
         break;
       default:
         buf += *in;
     }
   }
   return buf;
 }

 static bool NeedsShellEscape(char c) {
   return c == 0 || c == '"' || c == '$' || c == '\\' || c == '`';
 }

 void EscapeShell(string* s) {
   static const char ranges[] = "\0\0\"\"$$\\\\``";
   size_t prev = 0;
   size_t i = SkipUntil(s->c_str(), s->size(), ranges, 10, NeedsShellEscape);
   if (i == s->size())
     return;

   string r;
   for (; i < s->size();) {
     StringPiece(*s).substr(prev, i - prev).AppendToString(&r);
     char c = (*s)[i];
     r += '\\';
     if (c == '$') {
       if ((*s)[i+1] == '$') {
         r += '$';
         i++;
       }
     }
     r += c;
     i++;
     prev = i;
     i += SkipUntil(s->c_str() + i, s->size() - i, ranges, 10, NeedsShellEscape);
   }
   StringPiece(*s).substr(prev).AppendToString(&r);
   s->swap(r);
 }
	// Copyright 2015 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.

	// +build ignore

	#include "strutil.h"

	#include <ctype.h>
	#include <limits.h>
	#include <unistd.h>

	#include <algorithm>
	#include <functional>
	#include <stack>
	#include <utility>

	#ifdef __SSE4_2__
	#include <smmintrin.h>
	#endif

	#include "log.h"

	static bool isSpace(char c) {
	return (9 <= c && c <= 13) \|\| c == 32;
	}

	#ifdef __SSE4_2__
	static int SkipUntilSSE42(const char* s, int len,
	const char* ranges, int ranges_size) {
	__m128i ranges16 = _mm_loadu_si128((const __m128i*)ranges);
	len &= ~15;
	int i = 0;
	while (i < len) {
	__m128i b16 = _mm_loadu_si128((const __m128i*)(s + i));
	int r = _mm_cmpestri(
	ranges16, ranges_size, b16, len - i,
	_SIDD_LEAST_SIGNIFICANT \| _SIDD_CMP_RANGES \| _SIDD_UBYTE_OPS);
	if (r != 16) {
	return i + r;
	}
	i += 16;
	}
	return len;
	}
	#endif

	template <typename Cond>
	static int SkipUntil(const char* s, int len,
	const char* ranges UNUSED, int ranges_size UNUSED,
	Cond cond) {
	int i = 0;
	#ifdef __SSE4_2__
	i += SkipUntilSSE42(s, len, ranges, ranges_size);
	#endif
	for (; i < len; i++) {
	if (cond(s[i]))
	break;
	}
	return i;
	}

	WordScanner::Iterator& WordScanner::Iterator::operator++() {
	int len = static_cast<int>(in->size());
	for (s = i + 1; s < len; s++) {
	if (!isSpace((*in)[s]))
	break;
	}
	if (s >= len) {
	in = NULL;
	s = 0;
	i = 0;
	return *this;
	}

	static const char ranges[] = "\x09\x0d ";
	// It's intentional we are not using isSpace here. It seems with
	// lambda the compiler generates better code.
	i = s + SkipUntil(in->data() + s, len - s, ranges, 4,
	[](char c) { return (9 <= c && c <= 13) \|\| c == 32; });
	return *this;
	}

	StringPiece WordScanner::Iterator::operator*() const {
	return in->substr(s, i - s);
	}

	WordScanner::WordScanner(StringPiece in)
	: in_(in) {
	}

	WordScanner::Iterator WordScanner::begin() const {
	Iterator iter;
	iter.in = &in_;
	iter.s = 0;
	iter.i = -1;
	++iter;
	return iter;
	}

	WordScanner::Iterator WordScanner::end() const {
	Iterator iter;
	iter.in = NULL;
	iter.s = 0;
	iter.i = 0;
	return iter;
	}

	void WordScanner::Split(vector<StringPiece>* o) {
	for (StringPiece t : *this)
	o->push_back(t);
	}

	WordWriter::WordWriter(string* o)
	: out_(o),
	needs_space_(false) {
	}

	void WordWriter::MaybeAddWhitespace() {
	if (needs_space_) {
	out_->push_back(' ');
	} else {
	needs_space_ = true;
	}
	}

	void WordWriter::Write(StringPiece s) {
	MaybeAddWhitespace();
	AppendString(s, out_);
	}

	ScopedTerminator::ScopedTerminator(StringPiece s)
	: s_(s), c_(s[s.size()]) {
	const_cast<char*>(s_.data())[s_.size()] = '\0';
	}

	ScopedTerminator::~ScopedTerminator() {
	const_cast<char*>(s_.data())[s_.size()] = c_;
	}

	void AppendString(StringPiece str, string* out) {
	out->append(str.begin(), str.end());
	}

	bool HasPrefix(StringPiece str, StringPiece prefix) {
	ssize_t size_diff = str.size() - prefix.size();
	return size_diff >= 0 && str.substr(0, prefix.size()) == prefix;
	}

	bool HasSuffix(StringPiece str, StringPiece suffix) {
	ssize_t size_diff = str.size() - suffix.size();
	return size_diff >= 0 && str.substr(size_diff) == suffix;
	}

	bool HasWord(StringPiece str, StringPiece w) {
	size_t found = str.find(w);
	if (found == string::npos)
	return false;
	if (found != 0 && !isSpace(str[found-1]))
	return false;
	size_t end = found + w.size();
	if (end != str.size() && !isSpace(str[end]))
	return false;
	return true;
	}

	StringPiece TrimPrefix(StringPiece str, StringPiece prefix) {
	ssize_t size_diff = str.size() - prefix.size();
	if (size_diff < 0 \|\| str.substr(0, prefix.size()) != prefix)
	return str;
	return str.substr(prefix.size());
	}

	StringPiece TrimSuffix(StringPiece str, StringPiece suffix) {
	ssize_t size_diff = str.size() - suffix.size();
	if (size_diff < 0 \|\| str.substr(size_diff) != suffix)
	return str;
	return str.substr(0, size_diff);
	}

	Pattern::Pattern(StringPiece pat)
	: pat_(pat), percent_index_(pat.find('%')) {
	}

	bool Pattern::Match(StringPiece str) const {
	if (percent_index_ == string::npos)
	return str == pat_;
	return MatchImpl(str);
	}

	bool Pattern::MatchImpl(StringPiece str) const {
	return (HasPrefix(str, pat_.substr(0, percent_index_)) &&
	HasSuffix(str, pat_.substr(percent_index_ + 1)));
	}

	StringPiece Pattern::Stem(StringPiece str) const {
	if (!Match(str))
	return "";
	return str.substr(percent_index_,
	str.size() - (pat_.size() - percent_index_ - 1));
	}

	void Pattern::AppendSubst(StringPiece str, StringPiece subst,
	string* out) const {
	if (percent_index_ == string::npos) {
	if (str == pat_) {
	AppendString(subst, out);
	return;
	} else {
	AppendString(str, out);
	return;
	}
	}

	if (MatchImpl(str)) {
	size_t subst_percent_index = subst.find('%');
	if (subst_percent_index == string::npos) {
	AppendString(subst, out);
	return;
	} else {
	AppendString(subst.substr(0, subst_percent_index), out);
	AppendString(str.substr(percent_index_,
	str.size() - pat_.size() + 1), out);
	AppendString(subst.substr(subst_percent_index + 1), out);
	return;
	}
	}
	AppendString(str, out);
	}

	void Pattern::AppendSubstRef(StringPiece str, StringPiece subst,
	string* out) const {
	if (percent_index_ != string::npos && subst.find('%') != string::npos) {
	AppendSubst(str, subst, out);
	return;
	}
	StringPiece s = TrimSuffix(str, pat_);
	out->append(s.begin(), s.end());
	out->append(subst.begin(), subst.end());
	}

	string NoLineBreak(const string& s) {
	size_t index = s.find('\n');
	if (index == string::npos)
	return s;
	string r = s;
	while (index != string::npos) {
	r = r.substr(0, index) + "\\n" + r.substr(index + 1);
	index = r.find('\n', index + 2);
	}
	return r;
	}

	StringPiece TrimLeftSpace(StringPiece s) {
	size_t i = 0;
	for (; i < s.size(); i++) {
	if (isSpace(s[i]))
	continue;
	char n = s.get(i+1);
	if (s[i] == '\\' && (n == '\r' \|\| n == '\n')) {
	i++;
	continue;
	}
	break;
	}
	return s.substr(i, s.size() - i);
	}

	StringPiece TrimRightSpace(StringPiece s) {
	size_t i = 0;
	for (; i < s.size(); i++) {
	char c = s[s.size() - 1 - i];
	if (isSpace(c)) {
	if ((c == '\r' \|\| c == '\n') && s.get(s.size() - 2 - i) == '\\')
	i++;
	continue;
	}
	break;
	}
	return s.substr(0, s.size() - i);
	}

	StringPiece TrimSpace(StringPiece s) {
	return TrimRightSpace(TrimLeftSpace(s));
	}

	StringPiece Dirname(StringPiece s) {
	size_t found = s.rfind('/');
	if (found == string::npos)
	return StringPiece(".");
	if (found == 0)
	return StringPiece("");
	return s.substr(0, found);
	}

	StringPiece Basename(StringPiece s) {
	size_t found = s.rfind('/');
	if (found == string::npos \|\| found == 0)
	return s;
	return s.substr(found + 1);
	}

	StringPiece GetExt(StringPiece s) {
	size_t found = s.rfind('.');
	if (found == string::npos)
	return StringPiece("");
	return s.substr(found);
	}

	StringPiece StripExt(StringPiece s) {
	size_t slash_index = s.rfind('/');
	size_t found = s.rfind('.');
	if (found == string::npos \|\|
	(slash_index != string::npos && found < slash_index))
	return s;
	return s.substr(0, found);
	}

	void NormalizePath(string* o) {
	if (o->empty())
	return;
	size_t start_index = 0;
	if ((*o)[0] == '/')
	start_index++;
	size_t j = start_index;
	size_t prev_start = start_index;
	for (size_t i = start_index; i <= o->size(); i++) {
	char c = (*o)[i];
	if (c != '/' && c != 0) {
	(*o)[j] = c;
	j++;
	continue;
	}

	StringPiece prev_dir = StringPiece(o->data() + prev_start, j - prev_start);
	if (prev_dir == ".") {
	j--;
	} else if (prev_dir == ".." && j != 2 /* .. */) {
	if (j == 3) {
	// /..
	j = start_index;
	} else {
	size_t orig_j = j;
	j -= 4;
	j = o->rfind('/', j);
	if (j == string::npos) {
	j = start_index;
	} else {
	j++;
	}
	if (StringPiece(o->data() + j, 3) == "../") {
	j = orig_j;
	(*o)[j] = c;
	j++;
	}
	}
	} else if (!prev_dir.empty()) {
	if (c) {
	(*o)[j] = c;
	j++;
	}
	}
	prev_start = j;
	}
	if (j > 1 && (*o)[j-1] == '/')
	j--;
	o->resize(j);
	}

	void AbsPath(StringPiece s, string* o) {
	if (s.get(0) == '/') {
	o->clear();
	} else {
	char buf[PATH_MAX];
	if (!getcwd(buf, PATH_MAX)) {
	fprintf(stderr, "getcwd failed\n");
	CHECK(false);
	}

	CHECK(buf[0] == '/');
	*o = buf;
	*o += '/';
	}
	AppendString(s, o);
	NormalizePath(o);
	}

	template<typename Cond>
	size_t FindOutsideParenImpl(StringPiece s, Cond cond) {
	bool prev_backslash = false;
	stack<char> paren_stack;
	for (size_t i = 0; i < s.size(); i++) {
	char c = s[i];
	if (cond(c) && paren_stack.empty() && !prev_backslash) {
	return i;
	}
	switch (c) {
	case '(':
	paren_stack.push(')');
	break;
	case '{':
	paren_stack.push('}');
	break;

	case ')':
	case '}':
	if (!paren_stack.empty() && c == paren_stack.top()) {
	paren_stack.pop();
	}
	break;
	}
	prev_backslash = c == '\\' && !prev_backslash;
	}
	return string::npos;
	}

	size_t FindOutsideParen(StringPiece s, char c) {
	return FindOutsideParenImpl(s, [&c](char d){return c == d;});
	}

	size_t FindTwoOutsideParen(StringPiece s, char c1, char c2) {
	return FindOutsideParenImpl(s, [&c1, &c2](char d){
	return d == c1 \|\| d == c2;
	});
	}

	size_t FindThreeOutsideParen(StringPiece s, char c1, char c2, char c3) {
	return FindOutsideParenImpl(s, [&c1, &c2, &c3](char d){
	return d == c1 \|\| d == c2 \|\| d == c3;
	});
	}

	size_t FindEndOfLine(StringPiece s, size_t e, size_t* lf_cnt) {
	static const char ranges[] = "\0\0\n\n\\\\";
	while (e < s.size()) {
	e += SkipUntil(s.data() + e, s.size() - e, ranges, 6,
	[](char c) { return c == 0 \|\| c == '\n' \|\| c == '\\'; });
	if (e >= s.size()) {
	CHECK(s.size() == e);
	break;
	}
	char c = s[e];
	if (c == '\0')
	break;
	if (c == '\\') {
	if (s[e+1] == '\n') {
	e += 2;
	++*lf_cnt;
	} else if (s[e+1] == '\r' && s[e+2] == '\n') {
	e += 3;
	++*lf_cnt;
	} else if (s[e+1] == '\\') {
	e += 2;
	} else {
	e++;
	}
	} else if (c == '\n') {
	++*lf_cnt;
	return e;
	}
	}
	return e;
	}

	StringPiece TrimLeadingCurdir(StringPiece s) {
	while (s.substr(0, 2) == "./")
	s = s.substr(2);
	return s;
	}

	void FormatForCommandSubstitution(string* s) {
	while ((*s)[s->size()-1] == '\n')
	s->pop_back();
	for (size_t i = 0; i < s->size(); i++) {
	if ((*s)[i] == '\n')
	(*s)[i] = ' ';
	}
	}

	string SortWordsInString(StringPiece s) {
	vector<string> toks;
	for (StringPiece tok : WordScanner(s)) {
	toks.push_back(tok.as_string());
	}
	sort(toks.begin(), toks.end());
	return JoinStrings(toks, " ");
	}

	string ConcatDir(StringPiece b, StringPiece n) {
	string r;
	if (!b.empty()) {
	b.AppendToString(&r);
	r += '/';
	}
	n.AppendToString(&r);
	NormalizePath(&r);
	return r;
	}

	string EchoEscape(const string &str) {
	const char *in = str.c_str();
	string buf;
	for (; *in; in++) {
	switch(*in) {
	case '\\':
	buf += "\\\\\\\\";
	break;
	case '\n':
	buf += "\\n";
	break;
	case '"':
	buf += "\\\"";
	break;
	default:
	buf += *in;
	}
	}
	return buf;
	}

	static bool NeedsShellEscape(char c) {
	return c == 0 \|\| c == '"' \|\| c == '$' \|\| c == '\\' \|\| c == '`';
	}

	void EscapeShell(string* s) {
	static const char ranges[] = "\0\0\"\"$$\\\\``";
	size_t prev = 0;
	size_t i = SkipUntil(s->c_str(), s->size(), ranges, 10, NeedsShellEscape);
	if (i == s->size())
	return;

	string r;
	for (; i < s->size();) {
	StringPiece(*s).substr(prev, i - prev).AppendToString(&r);
	char c = (*s)[i];
	r += '\\';
	if (c == '$') {
	if ((*s)[i+1] == '$') {
	r += '$';
	i++;
	}
	}
	r += c;
	i++;
	prev = i;
	i += SkipUntil(s->c_str() + i, s->size() - i, ranges, 10, NeedsShellEscape);
	}
	StringPiece(*s).substr(prev).AppendToString(&r);
	s->swap(r);
	}