Home | History | Annotate | Download | only in kati 
      1 // Copyright 2015 Google Inc. All rights reserved
      2 //
      3 // Licensed under the Apache License, Version 2.0 (the "License");
      4 // you may not use this file except in compliance with the License.
      5 // You may obtain a copy of the License at
      6 //
      7 //      http://www.apache.org/licenses/LICENSE-2.0
      8 //
      9 // Unless required by applicable law or agreed to in writing, software
     10 // distributed under the License is distributed on an "AS IS" BASIS,
     11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     12 // See the License for the specific language governing permissions and
     13 // limitations under the License.
     14 
     15 // +build ignore
     16 
     17 #include "strutil.h"
     18 
     19 #include <ctype.h>
     20 #include <limits.h>
     21 #include <unistd.h>
     22 
     23 #include <algorithm>
     24 #include <functional>
     25 #include <stack>
     26 #include <utility>
     27 
     28 #ifdef __SSE4_2__
     29 #include <smmintrin.h>
     30 #endif
     31 
     32 #include "log.h"
     33 
     34 static bool isSpace(char c) {
     35   return (9 <= c && c <= 13) || c == 32;
     36 }
     37 
     38 #ifdef __SSE4_2__
     39 static int SkipUntilSSE42(const char* s,
     40                           int len,
     41                           const char* ranges,
     42                           int ranges_size) {
     43   __m128i ranges16 = _mm_loadu_si128((const __m128i*)ranges);
     44   len &= ~15;
     45   int i = 0;
     46   while (i < len) {
     47     __m128i b16 = _mm_loadu_si128((const __m128i*)(s + i));
     48     int r = _mm_cmpestri(
     49         ranges16, ranges_size, b16, len - i,
     50         _SIDD_LEAST_SIGNIFICANT | _SIDD_CMP_RANGES | _SIDD_UBYTE_OPS);
     51     if (r != 16) {
     52       return i + r;
     53     }
     54     i += 16;
     55   }
     56   return len;
     57 }
     58 #endif
     59 
     60 template <typename Cond>
     61 static int SkipUntil(const char* s,
     62                      int len,
     63                      const char* ranges UNUSED,
     64                      int ranges_size UNUSED,
     65                      Cond cond) {
     66   int i = 0;
     67 #ifdef __SSE4_2__
     68   i += SkipUntilSSE42(s, len, ranges, ranges_size);
     69 #endif
     70   for (; i < len; i++) {
     71     if (cond(s[i]))
     72       break;
     73   }
     74   return i;
     75 }
     76 
     77 WordScanner::Iterator& WordScanner::Iterator::operator++() {
     78   int len = static_cast<int>(in->size());
     79   for (s = i + 1; s < len; s++) {
     80     if (!isSpace((*in)[s]))
     81       break;
     82   }
     83   if (s >= len) {
     84     in = NULL;
     85     s = 0;
     86     i = 0;
     87     return *this;
     88   }
     89 
     90   static const char ranges[] = "\x09\x0d  ";
     91   // It's intentional we are not using isSpace here. It seems with
     92   // lambda the compiler generates better code.
     93   i = s + SkipUntil(in->data() + s, len - s, ranges, 4,
     94                     [](char c) { return (9 <= c && c <= 13) || c == 32; });
     95   return *this;
     96 }
     97 
     98 StringPiece WordScanner::Iterator::operator*() const {
     99   return in->substr(s, i - s);
    100 }
    101 
    102 WordScanner::WordScanner(StringPiece in) : in_(in) {}
    103 
    104 WordScanner::Iterator WordScanner::begin() const {
    105   Iterator iter;
    106   iter.in = &in_;
    107   iter.s = 0;
    108   iter.i = -1;
    109   ++iter;
    110   return iter;
    111 }
    112 
    113 WordScanner::Iterator WordScanner::end() const {
    114   Iterator iter;
    115   iter.in = NULL;
    116   iter.s = 0;
    117   iter.i = 0;
    118   return iter;
    119 }
    120 
    121 void WordScanner::Split(vector<StringPiece>* o) {
    122   for (StringPiece t : *this)
    123     o->push_back(t);
    124 }
    125 
    126 WordWriter::WordWriter(string* o) : out_(o), needs_space_(false) {}
    127 
    128 void WordWriter::MaybeAddWhitespace() {
    129   if (needs_space_) {
    130     out_->push_back(' ');
    131   } else {
    132     needs_space_ = true;
    133   }
    134 }
    135 
    136 void WordWriter::Write(StringPiece s) {
    137   MaybeAddWhitespace();
    138   AppendString(s, out_);
    139 }
    140 
    141 ScopedTerminator::ScopedTerminator(StringPiece s) : s_(s), c_(s[s.size()]) {
    142   const_cast<char*>(s_.data())[s_.size()] = '\0';
    143 }
    144 
    145 ScopedTerminator::~ScopedTerminator() {
    146   const_cast<char*>(s_.data())[s_.size()] = c_;
    147 }
    148 
    149 void AppendString(StringPiece str, string* out) {
    150   out->append(str.begin(), str.end());
    151 }
    152 
    153 bool HasPrefix(StringPiece str, StringPiece prefix) {
    154   ssize_t size_diff = str.size() - prefix.size();
    155   return size_diff >= 0 && str.substr(0, prefix.size()) == prefix;
    156 }
    157 
    158 bool HasSuffix(StringPiece str, StringPiece suffix) {
    159   ssize_t size_diff = str.size() - suffix.size();
    160   return size_diff >= 0 && str.substr(size_diff) == suffix;
    161 }
    162 
    163 bool HasWord(StringPiece str, StringPiece w) {
    164   size_t found = str.find(w);
    165   if (found == string::npos)
    166     return false;
    167   if (found != 0 && !isSpace(str[found - 1]))
    168     return false;
    169   size_t end = found + w.size();
    170   if (end != str.size() && !isSpace(str[end]))
    171     return false;
    172   return true;
    173 }
    174 
    175 StringPiece TrimPrefix(StringPiece str, StringPiece prefix) {
    176   ssize_t size_diff = str.size() - prefix.size();
    177   if (size_diff < 0 || str.substr(0, prefix.size()) != prefix)
    178     return str;
    179   return str.substr(prefix.size());
    180 }
    181 
    182 StringPiece TrimSuffix(StringPiece str, StringPiece suffix) {
    183   ssize_t size_diff = str.size() - suffix.size();
    184   if (size_diff < 0 || str.substr(size_diff) != suffix)
    185     return str;
    186   return str.substr(0, size_diff);
    187 }
    188 
    189 Pattern::Pattern(StringPiece pat) : pat_(pat), percent_index_(pat.find('%')) {}
    190 
    191 bool Pattern::Match(StringPiece str) const {
    192   if (percent_index_ == string::npos)
    193     return str == pat_;
    194   return MatchImpl(str);
    195 }
    196 
    197 bool Pattern::MatchImpl(StringPiece str) const {
    198   return (HasPrefix(str, pat_.substr(0, percent_index_)) &&
    199           HasSuffix(str, pat_.substr(percent_index_ + 1)));
    200 }
    201 
    202 StringPiece Pattern::Stem(StringPiece str) const {
    203   if (!Match(str))
    204     return "";
    205   return str.substr(percent_index_,
    206                     str.size() - (pat_.size() - percent_index_ - 1));
    207 }
    208 
    209 void Pattern::AppendSubst(StringPiece str,
    210                           StringPiece subst,
    211                           string* out) const {
    212   if (percent_index_ == string::npos) {
    213     if (str == pat_) {
    214       AppendString(subst, out);
    215       return;
    216     } else {
    217       AppendString(str, out);
    218       return;
    219     }
    220   }
    221 
    222   if (MatchImpl(str)) {
    223     size_t subst_percent_index = subst.find('%');
    224     if (subst_percent_index == string::npos) {
    225       AppendString(subst, out);
    226       return;
    227     } else {
    228       AppendString(subst.substr(0, subst_percent_index), out);
    229       AppendString(str.substr(percent_index_, str.size() - pat_.size() + 1),
    230                    out);
    231       AppendString(subst.substr(subst_percent_index + 1), out);
    232       return;
    233     }
    234   }
    235   AppendString(str, out);
    236 }
    237 
    238 void Pattern::AppendSubstRef(StringPiece str,
    239                              StringPiece subst,
    240                              string* out) const {
    241   if (percent_index_ != string::npos && subst.find('%') != string::npos) {
    242     AppendSubst(str, subst, out);
    243     return;
    244   }
    245   StringPiece s = TrimSuffix(str, pat_);
    246   out->append(s.begin(), s.end());
    247   out->append(subst.begin(), subst.end());
    248 }
    249 
    250 string NoLineBreak(const string& s) {
    251   size_t index = s.find('\n');
    252   if (index == string::npos)
    253     return s;
    254   string r = s;
    255   while (index != string::npos) {
    256     r = r.substr(0, index) + "\\n" + r.substr(index + 1);
    257     index = r.find('\n', index + 2);
    258   }
    259   return r;
    260 }
    261 
    262 StringPiece TrimLeftSpace(StringPiece s) {
    263   size_t i = 0;
    264   for (; i < s.size(); i++) {
    265     if (isSpace(s[i]))
    266       continue;
    267     char n = s.get(i + 1);
    268     if (s[i] == '\\' && (n == '\r' || n == '\n')) {
    269       i++;
    270       continue;
    271     }
    272     break;
    273   }
    274   return s.substr(i, s.size() - i);
    275 }
    276 
    277 StringPiece TrimRightSpace(StringPiece s) {
    278   size_t i = 0;
    279   for (; i < s.size(); i++) {
    280     char c = s[s.size() - 1 - i];
    281     if (isSpace(c)) {
    282       if ((c == '\r' || c == '\n') && s.get(s.size() - 2 - i) == '\\')
    283         i++;
    284       continue;
    285     }
    286     break;
    287   }
    288   return s.substr(0, s.size() - i);
    289 }
    290 
    291 StringPiece TrimSpace(StringPiece s) {
    292   return TrimRightSpace(TrimLeftSpace(s));
    293 }
    294 
    295 StringPiece Dirname(StringPiece s) {
    296   size_t found = s.rfind('/');
    297   if (found == string::npos)
    298     return StringPiece(".");
    299   if (found == 0)
    300     return StringPiece("");
    301   return s.substr(0, found);
    302 }
    303 
    304 StringPiece Basename(StringPiece s) {
    305   size_t found = s.rfind('/');
    306   if (found == string::npos || found == 0)
    307     return s;
    308   return s.substr(found + 1);
    309 }
    310 
    311 StringPiece GetExt(StringPiece s) {
    312   size_t found = s.rfind('.');
    313   if (found == string::npos)
    314     return StringPiece("");
    315   return s.substr(found);
    316 }
    317 
    318 StringPiece StripExt(StringPiece s) {
    319   size_t slash_index = s.rfind('/');
    320   size_t found = s.rfind('.');
    321   if (found == string::npos ||
    322       (slash_index != string::npos && found < slash_index))
    323     return s;
    324   return s.substr(0, found);
    325 }
    326 
    327 void NormalizePath(string* o) {
    328   if (o->empty())
    329     return;
    330   size_t start_index = 0;
    331   if ((*o)[0] == '/')
    332     start_index++;
    333   size_t j = start_index;
    334   size_t prev_start = start_index;
    335   for (size_t i = start_index; i <= o->size(); i++) {
    336     char c = (*o)[i];
    337     if (c != '/' && c != 0) {
    338       (*o)[j] = c;
    339       j++;
    340       continue;
    341     }
    342 
    343     StringPiece prev_dir = StringPiece(o->data() + prev_start, j - prev_start);
    344     if (prev_dir == ".") {
    345       j--;
    346     } else if (prev_dir == ".." && j != 2 /* .. */) {
    347       if (j == 3) {
    348         // /..
    349         j = start_index;
    350       } else {
    351         size_t orig_j = j;
    352         j -= 4;
    353         j = o->rfind('/', j);
    354         if (j == string::npos) {
    355           j = start_index;
    356         } else {
    357           j++;
    358         }
    359         if (StringPiece(o->data() + j, 3) == "../") {
    360           j = orig_j;
    361           (*o)[j] = c;
    362           j++;
    363         }
    364       }
    365     } else if (!prev_dir.empty()) {
    366       if (c) {
    367         (*o)[j] = c;
    368         j++;
    369       }
    370     }
    371     prev_start = j;
    372   }
    373   if (j > 1 && (*o)[j - 1] == '/')
    374     j--;
    375   o->resize(j);
    376 }
    377 
    378 void AbsPath(StringPiece s, string* o) {
    379   if (s.get(0) == '/') {
    380     o->clear();
    381   } else {
    382     char buf[PATH_MAX];
    383     if (!getcwd(buf, PATH_MAX)) {
    384       fprintf(stderr, "getcwd failed\n");
    385       CHECK(false);
    386     }
    387 
    388     CHECK(buf[0] == '/');
    389     *o = buf;
    390     *o += '/';
    391   }
    392   AppendString(s, o);
    393   NormalizePath(o);
    394 }
    395 
    396 template <typename Cond>
    397 size_t FindOutsideParenImpl(StringPiece s, Cond cond) {
    398   bool prev_backslash = false;
    399   stack<char> paren_stack;
    400   for (size_t i = 0; i < s.size(); i++) {
    401     char c = s[i];
    402     if (cond(c) && paren_stack.empty() && !prev_backslash) {
    403       return i;
    404     }
    405     switch (c) {
    406       case '(':
    407         paren_stack.push(')');
    408         break;
    409       case '{':
    410         paren_stack.push('}');
    411         break;
    412 
    413       case ')':
    414       case '}':
    415         if (!paren_stack.empty() && c == paren_stack.top()) {
    416           paren_stack.pop();
    417         }
    418         break;
    419     }
    420     prev_backslash = c == '\\' && !prev_backslash;
    421   }
    422   return string::npos;
    423 }
    424 
    425 size_t FindOutsideParen(StringPiece s, char c) {
    426   return FindOutsideParenImpl(s, [&c](char d) { return c == d; });
    427 }
    428 
    429 size_t FindTwoOutsideParen(StringPiece s, char c1, char c2) {
    430   return FindOutsideParenImpl(
    431       s, [&c1, &c2](char d) { return d == c1 || d == c2; });
    432 }
    433 
    434 size_t FindThreeOutsideParen(StringPiece s, char c1, char c2, char c3) {
    435   return FindOutsideParenImpl(
    436       s, [&c1, &c2, &c3](char d) { return d == c1 || d == c2 || d == c3; });
    437 }
    438 
    439 size_t FindEndOfLine(StringPiece s, size_t e, size_t* lf_cnt) {
    440   static const char ranges[] = "\0\0\n\n\\\\";
    441   while (e < s.size()) {
    442     e += SkipUntil(s.data() + e, s.size() - e, ranges, 6,
    443                    [](char c) { return c == 0 || c == '\n' || c == '\\'; });
    444     if (e >= s.size()) {
    445       CHECK(s.size() == e);
    446       break;
    447     }
    448     char c = s[e];
    449     if (c == '\0')
    450       break;
    451     if (c == '\\') {
    452       if (s[e + 1] == '\n') {
    453         e += 2;
    454         ++*lf_cnt;
    455       } else if (s[e + 1] == '\r' && s[e + 2] == '\n') {
    456         e += 3;
    457         ++*lf_cnt;
    458       } else if (s[e + 1] == '\\') {
    459         e += 2;
    460       } else {
    461         e++;
    462       }
    463     } else if (c == '\n') {
    464       ++*lf_cnt;
    465       return e;
    466     }
    467   }
    468   return e;
    469 }
    470 
    471 StringPiece TrimLeadingCurdir(StringPiece s) {
    472   while (s.substr(0, 2) == "./")
    473     s = s.substr(2);
    474   return s;
    475 }
    476 
    477 void FormatForCommandSubstitution(string* s) {
    478   while ((*s)[s->size() - 1] == '\n')
    479     s->pop_back();
    480   for (size_t i = 0; i < s->size(); i++) {
    481     if ((*s)[i] == '\n')
    482       (*s)[i] = ' ';
    483   }
    484 }
    485 
    486 string SortWordsInString(StringPiece s) {
    487   vector<string> toks;
    488   for (StringPiece tok : WordScanner(s)) {
    489     toks.push_back(tok.as_string());
    490   }
    491   sort(toks.begin(), toks.end());
    492   return JoinStrings(toks, " ");
    493 }
    494 
    495 string ConcatDir(StringPiece b, StringPiece n) {
    496   string r;
    497   if (!b.empty()) {
    498     b.AppendToString(&r);
    499     r += '/';
    500   }
    501   n.AppendToString(&r);
    502   NormalizePath(&r);
    503   return r;
    504 }
    505 
    506 string EchoEscape(const string& str) {
    507   const char* in = str.c_str();
    508   string buf;
    509   for (; *in; in++) {
    510     switch (*in) {
    511       case '\\':
    512         buf += "\\\\\\\\";
    513         break;
    514       case '\n':
    515         buf += "\\n";
    516         break;
    517       case '"':
    518         buf += "\\\"";
    519         break;
    520       default:
    521         buf += *in;
    522     }
    523   }
    524   return buf;
    525 }
    526 
    527 static bool NeedsShellEscape(char c) {
    528   return c == 0 || c == '"' || c == '$' || c == '\\' || c == '`';
    529 }
    530 
    531 void EscapeShell(string* s) {
    532   static const char ranges[] = "\0\0\"\"$$\\\\``";
    533   size_t prev = 0;
    534   size_t i = SkipUntil(s->c_str(), s->size(), ranges, 10, NeedsShellEscape);
    535   if (i == s->size())
    536     return;
    537 
    538   string r;
    539   for (; i < s->size();) {
    540     StringPiece(*s).substr(prev, i - prev).AppendToString(&r);
    541     char c = (*s)[i];
    542     r += '\\';
    543     if (c == '$') {
    544       if ((*s)[i + 1] == '$') {
    545         r += '$';
    546         i++;
    547       }
    548     }
    549     r += c;
    550     i++;
    551     prev = i;
    552     i += SkipUntil(s->c_str() + i, s->size() - i, ranges, 10, NeedsShellEscape);
    553   }
    554   StringPiece(*s).substr(prev).AppendToString(&r);
    555   s->swap(r);
    556 }
    557