blob: 632d151c79bed640e4856dbbf46e5b901b76bdb7 [file] [log] [blame]
// 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);
}