1// Copyright 2011 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#include "util.h"
16
17#ifdef __CYGWIN__
18#include <windows.h>
19#include <io.h>
20#elif defined( _WIN32)
21#include <windows.h>
22#include <io.h>
23#include <share.h>
24#endif
25
26#include <assert.h>
27#include <errno.h>
28#include <fcntl.h>
29#include <stdarg.h>
30#include <stdio.h>
31#include <stdlib.h>
32#include <string.h>
33#include <sys/stat.h>
34#include <sys/types.h>
35
36#ifndef _WIN32
37#include <unistd.h>
38#include <sys/time.h>
39#endif
40
41#include <vector>
42
43#if defined(__APPLE__) || defined(__FreeBSD__)
44#include <sys/sysctl.h>
45#elif defined(__SVR4) && defined(__sun)
46#include <unistd.h>
47#include <sys/loadavg.h>
48#elif defined(_AIX) && !defined(__PASE__)
49#include <libperfstat.h>
50#elif defined(linux) || defined(__GLIBC__)
51#include <sys/sysinfo.h>
52#endif
53
54#include "edit_distance.h"
55#include "metrics.h"
56
57using namespace std;
58
59void Fatal(const char* msg, ...) {
60  va_list ap;
61  fprintf(stderr, "ninja: fatal: ");
62  va_start(ap, msg);
63  vfprintf(stderr, msg, ap);
64  va_end(ap);
65  fprintf(stderr, "\n");
66#ifdef _WIN32
67  // On Windows, some tools may inject extra threads.
68  // exit() may block on locks held by those threads, so forcibly exit.
69  fflush(stderr);
70  fflush(stdout);
71  ExitProcess(1);
72#else
73  exit(1);
74#endif
75}
76
77void Warning(const char* msg, ...) {
78  va_list ap;
79  fprintf(stderr, "ninja: warning: ");
80  va_start(ap, msg);
81  vfprintf(stderr, msg, ap);
82  va_end(ap);
83  fprintf(stderr, "\n");
84}
85
86void Error(const char* msg, ...) {
87  va_list ap;
88  fprintf(stderr, "ninja: error: ");
89  va_start(ap, msg);
90  vfprintf(stderr, msg, ap);
91  va_end(ap);
92  fprintf(stderr, "\n");
93}
94
95bool CanonicalizePath(string* path, uint64_t* slash_bits, string* err) {
96  METRIC_RECORD("canonicalize str");
97  size_t len = path->size();
98  char* str = 0;
99  if (len > 0)
100    str = &(*path)[0];
101  if (!CanonicalizePath(str, &len, slash_bits, err))
102    return false;
103  path->resize(len);
104  return true;
105}
106
107static bool IsPathSeparator(char c) {
108#ifdef _WIN32
109  return c == '/' || c == '\\';
110#else
111  return c == '/';
112#endif
113}
114
115bool CanonicalizePath(char* path, size_t* len, uint64_t* slash_bits,
116                      string* err) {
117  // WARNING: this function is performance-critical; please benchmark
118  // any changes you make to it.
119  METRIC_RECORD("canonicalize path");
120  if (*len == 0) {
121    *err = "empty path";
122    return false;
123  }
124
125  const int kMaxPathComponents = 60;
126  char* components[kMaxPathComponents];
127  int component_count = 0;
128
129  char* start = path;
130  char* dst = start;
131  const char* src = start;
132  const char* end = start + *len;
133
134  if (IsPathSeparator(*src)) {
135#ifdef _WIN32
136
137    // network path starts with //
138    if (*len > 1 && IsPathSeparator(*(src + 1))) {
139      src += 2;
140      dst += 2;
141    } else {
142      ++src;
143      ++dst;
144    }
145#else
146    ++src;
147    ++dst;
148#endif
149  }
150
151  while (src < end) {
152    if (*src == '.') {
153      if (src + 1 == end || IsPathSeparator(src[1])) {
154        // '.' component; eliminate.
155        src += 2;
156        continue;
157      } else if (src[1] == '.' && (src + 2 == end || IsPathSeparator(src[2]))) {
158        // '..' component.  Back up if possible.
159        if (component_count > 0) {
160          dst = components[component_count - 1];
161          src += 3;
162          --component_count;
163        } else {
164          *dst++ = *src++;
165          *dst++ = *src++;
166          *dst++ = *src++;
167        }
168        continue;
169      }
170    }
171
172    if (IsPathSeparator(*src)) {
173      src++;
174      continue;
175    }
176
177    if (component_count == kMaxPathComponents)
178      Fatal("path has too many components : %s", path);
179    components[component_count] = dst;
180    ++component_count;
181
182    while (src != end && !IsPathSeparator(*src))
183      *dst++ = *src++;
184    *dst++ = *src++;  // Copy '/' or final \0 character as well.
185  }
186
187  if (dst == start) {
188    *dst++ = '.';
189    *dst++ = '\0';
190  }
191
192  *len = dst - start - 1;
193#ifdef _WIN32
194  uint64_t bits = 0;
195  uint64_t bits_mask = 1;
196
197  for (char* c = start; c < start + *len; ++c) {
198    switch (*c) {
199      case '\\':
200        bits |= bits_mask;
201        *c = '/';
202        NINJA_FALLTHROUGH;
203      case '/':
204        bits_mask <<= 1;
205    }
206  }
207
208  *slash_bits = bits;
209#else
210  *slash_bits = 0;
211#endif
212  return true;
213}
214
215static inline bool IsKnownShellSafeCharacter(char ch) {
216  if ('A' <= ch && ch <= 'Z') return true;
217  if ('a' <= ch && ch <= 'z') return true;
218  if ('0' <= ch && ch <= '9') return true;
219
220  switch (ch) {
221    case '_':
222    case '+':
223    case '-':
224    case '.':
225    case '/':
226      return true;
227    default:
228      return false;
229  }
230}
231
232static inline bool IsKnownWin32SafeCharacter(char ch) {
233  switch (ch) {
234    case ' ':
235    case '"':
236      return false;
237    default:
238      return true;
239  }
240}
241
242static inline bool StringNeedsShellEscaping(const string& input) {
243  for (size_t i = 0; i < input.size(); ++i) {
244    if (!IsKnownShellSafeCharacter(input[i])) return true;
245  }
246  return false;
247}
248
249static inline bool StringNeedsWin32Escaping(const string& input) {
250  for (size_t i = 0; i < input.size(); ++i) {
251    if (!IsKnownWin32SafeCharacter(input[i])) return true;
252  }
253  return false;
254}
255
256void GetShellEscapedString(const string& input, string* result) {
257  assert(result);
258
259  if (!StringNeedsShellEscaping(input)) {
260    result->append(input);
261    return;
262  }
263
264  const char kQuote = '\'';
265  const char kEscapeSequence[] = "'\\'";
266
267  result->push_back(kQuote);
268
269  string::const_iterator span_begin = input.begin();
270  for (string::const_iterator it = input.begin(), end = input.end(); it != end;
271       ++it) {
272    if (*it == kQuote) {
273      result->append(span_begin, it);
274      result->append(kEscapeSequence);
275      span_begin = it;
276    }
277  }
278  result->append(span_begin, input.end());
279  result->push_back(kQuote);
280}
281
282
283void GetWin32EscapedString(const string& input, string* result) {
284  assert(result);
285  if (!StringNeedsWin32Escaping(input)) {
286    result->append(input);
287    return;
288  }
289
290  const char kQuote = '"';
291  const char kBackslash = '\\';
292
293  result->push_back(kQuote);
294  size_t consecutive_backslash_count = 0;
295  string::const_iterator span_begin = input.begin();
296  for (string::const_iterator it = input.begin(), end = input.end(); it != end;
297       ++it) {
298    switch (*it) {
299      case kBackslash:
300        ++consecutive_backslash_count;
301        break;
302      case kQuote:
303        result->append(span_begin, it);
304        result->append(consecutive_backslash_count + 1, kBackslash);
305        span_begin = it;
306        consecutive_backslash_count = 0;
307        break;
308      default:
309        consecutive_backslash_count = 0;
310        break;
311    }
312  }
313  result->append(span_begin, input.end());
314  result->append(consecutive_backslash_count, kBackslash);
315  result->push_back(kQuote);
316}
317
318int ReadFile(const string& path, string* contents, string* err) {
319#ifdef _WIN32
320  // This makes a ninja run on a set of 1500 manifest files about 4% faster
321  // than using the generic fopen code below.
322  err->clear();
323  HANDLE f = ::CreateFileA(path.c_str(), GENERIC_READ, FILE_SHARE_READ, NULL,
324                           OPEN_EXISTING, FILE_FLAG_SEQUENTIAL_SCAN, NULL);
325  if (f == INVALID_HANDLE_VALUE) {
326    err->assign(GetLastErrorString());
327    return -ENOENT;
328  }
329
330  for (;;) {
331    DWORD len;
332    char buf[64 << 10];
333    if (!::ReadFile(f, buf, sizeof(buf), &len, NULL)) {
334      err->assign(GetLastErrorString());
335      contents->clear();
336      return -1;
337    }
338    if (len == 0)
339      break;
340    contents->append(buf, len);
341  }
342  ::CloseHandle(f);
343  return 0;
344#else
345  FILE* f = fopen(path.c_str(), "rb");
346  if (!f) {
347    err->assign(strerror(errno));
348    return -errno;
349  }
350
351  struct stat st;
352  if (fstat(fileno(f), &st) < 0) {
353    err->assign(strerror(errno));
354    fclose(f);
355    return -errno;
356  }
357
358  // +1 is for the resize in ManifestParser::Load
359  contents->reserve(st.st_size + 1);
360
361  char buf[64 << 10];
362  size_t len;
363  while (!feof(f) && (len = fread(buf, 1, sizeof(buf), f)) > 0) {
364    contents->append(buf, len);
365  }
366  if (ferror(f)) {
367    err->assign(strerror(errno));  // XXX errno?
368    contents->clear();
369    fclose(f);
370    return -errno;
371  }
372  fclose(f);
373  return 0;
374#endif
375}
376
377void SetCloseOnExec(int fd) {
378#ifndef _WIN32
379  int flags = fcntl(fd, F_GETFD);
380  if (flags < 0) {
381    perror("fcntl(F_GETFD)");
382  } else {
383    if (fcntl(fd, F_SETFD, flags | FD_CLOEXEC) < 0)
384      perror("fcntl(F_SETFD)");
385  }
386#else
387  HANDLE hd = (HANDLE) _get_osfhandle(fd);
388  if (! SetHandleInformation(hd, HANDLE_FLAG_INHERIT, 0)) {
389    fprintf(stderr, "SetHandleInformation(): %s", GetLastErrorString().c_str());
390  }
391#endif  // ! _WIN32
392}
393
394
395const char* SpellcheckStringV(const string& text,
396                              const vector<const char*>& words) {
397  const bool kAllowReplacements = true;
398  const int kMaxValidEditDistance = 3;
399
400  int min_distance = kMaxValidEditDistance + 1;
401  const char* result = NULL;
402  for (vector<const char*>::const_iterator i = words.begin();
403       i != words.end(); ++i) {
404    int distance = EditDistance(*i, text, kAllowReplacements,
405                                kMaxValidEditDistance);
406    if (distance < min_distance) {
407      min_distance = distance;
408      result = *i;
409    }
410  }
411  return result;
412}
413
414const char* SpellcheckString(const char* text, ...) {
415  // Note: This takes a const char* instead of a string& because using
416  // va_start() with a reference parameter is undefined behavior.
417  va_list ap;
418  va_start(ap, text);
419  vector<const char*> words;
420  const char* word;
421  while ((word = va_arg(ap, const char*)))
422    words.push_back(word);
423  va_end(ap);
424  return SpellcheckStringV(text, words);
425}
426
427#ifdef _WIN32
428string GetLastErrorString() {
429  DWORD err = GetLastError();
430
431  char* msg_buf;
432  FormatMessageA(
433        FORMAT_MESSAGE_ALLOCATE_BUFFER |
434        FORMAT_MESSAGE_FROM_SYSTEM |
435        FORMAT_MESSAGE_IGNORE_INSERTS,
436        NULL,
437        err,
438        MAKELANGID(LANG_NEUTRAL, SUBLANG_DEFAULT),
439        (char*)&msg_buf,
440        0,
441        NULL);
442  string msg = msg_buf;
443  LocalFree(msg_buf);
444  return msg;
445}
446
447void Win32Fatal(const char* function, const char* hint) {
448  if (hint) {
449    Fatal("%s: %s (%s)", function, GetLastErrorString().c_str(), hint);
450  } else {
451    Fatal("%s: %s", function, GetLastErrorString().c_str());
452  }
453}
454#endif
455
456bool islatinalpha(int c) {
457  // isalpha() is locale-dependent.
458  return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
459}
460
461string StripAnsiEscapeCodes(const string& in) {
462  string stripped;
463  stripped.reserve(in.size());
464
465  for (size_t i = 0; i < in.size(); ++i) {
466    if (in[i] != '\33') {
467      // Not an escape code.
468      stripped.push_back(in[i]);
469      continue;
470    }
471
472    // Only strip CSIs for now.
473    if (i + 1 >= in.size()) break;
474    if (in[i + 1] != '[') continue;  // Not a CSI.
475    i += 2;
476
477    // Skip everything up to and including the next [a-zA-Z].
478    while (i < in.size() && !islatinalpha(in[i]))
479      ++i;
480  }
481  return stripped;
482}
483
484int GetProcessorCount() {
485#ifdef _WIN32
486  return GetActiveProcessorCount(ALL_PROCESSOR_GROUPS);
487#else
488#ifdef CPU_COUNT
489  // The number of exposed processors might not represent the actual number of
490  // processors threads can run on. This happens when a CPU set limitation is
491  // active, see https://github.com/ninja-build/ninja/issues/1278
492  cpu_set_t set;
493  if (sched_getaffinity(getpid(), sizeof(set), &set) == 0) {
494    return CPU_COUNT(&set);
495  }
496#endif
497  return sysconf(_SC_NPROCESSORS_ONLN);
498#endif
499}
500
501#if defined(_WIN32) || defined(__CYGWIN__)
502static double CalculateProcessorLoad(uint64_t idle_ticks, uint64_t total_ticks)
503{
504  static uint64_t previous_idle_ticks = 0;
505  static uint64_t previous_total_ticks = 0;
506  static double previous_load = -0.0;
507
508  uint64_t idle_ticks_since_last_time = idle_ticks - previous_idle_ticks;
509  uint64_t total_ticks_since_last_time = total_ticks - previous_total_ticks;
510
511  bool first_call = (previous_total_ticks == 0);
512  bool ticks_not_updated_since_last_call = (total_ticks_since_last_time == 0);
513
514  double load;
515  if (first_call || ticks_not_updated_since_last_call) {
516    load = previous_load;
517  } else {
518    // Calculate load.
519    double idle_to_total_ratio =
520        ((double)idle_ticks_since_last_time) / total_ticks_since_last_time;
521    double load_since_last_call = 1.0 - idle_to_total_ratio;
522
523    // Filter/smooth result when possible.
524    if(previous_load > 0) {
525      load = 0.9 * previous_load + 0.1 * load_since_last_call;
526    } else {
527      load = load_since_last_call;
528    }
529  }
530
531  previous_load = load;
532  previous_total_ticks = total_ticks;
533  previous_idle_ticks = idle_ticks;
534
535  return load;
536}
537
538static uint64_t FileTimeToTickCount(const FILETIME & ft)
539{
540  uint64_t high = (((uint64_t)(ft.dwHighDateTime)) << 32);
541  uint64_t low  = ft.dwLowDateTime;
542  return (high | low);
543}
544
545double GetLoadAverage() {
546  FILETIME idle_time, kernel_time, user_time;
547  BOOL get_system_time_succeeded =
548      GetSystemTimes(&idle_time, &kernel_time, &user_time);
549
550  double posix_compatible_load;
551  if (get_system_time_succeeded) {
552    uint64_t idle_ticks = FileTimeToTickCount(idle_time);
553
554    // kernel_time from GetSystemTimes already includes idle_time.
555    uint64_t total_ticks =
556        FileTimeToTickCount(kernel_time) + FileTimeToTickCount(user_time);
557
558    double processor_load = CalculateProcessorLoad(idle_ticks, total_ticks);
559    posix_compatible_load = processor_load * GetProcessorCount();
560
561  } else {
562    posix_compatible_load = -0.0;
563  }
564
565  return posix_compatible_load;
566}
567#elif defined(__PASE__)
568double GetLoadAverage() {
569  return -0.0f;
570}
571#elif defined(_AIX)
572double GetLoadAverage() {
573  perfstat_cpu_total_t cpu_stats;
574  if (perfstat_cpu_total(NULL, &cpu_stats, sizeof(cpu_stats), 1) < 0) {
575    return -0.0f;
576  }
577
578  // Calculation taken from comment in libperfstats.h
579  return double(cpu_stats.loadavg[0]) / double(1 << SBITS);
580}
581#elif defined(__UCLIBC__) || (defined(__BIONIC__) && __ANDROID_API__ < 29)
582double GetLoadAverage() {
583  struct sysinfo si;
584  if (sysinfo(&si) != 0)
585    return -0.0f;
586  return 1.0 / (1 << SI_LOAD_SHIFT) * si.loads[0];
587}
588#else
589double GetLoadAverage() {
590  double loadavg[3] = { 0.0f, 0.0f, 0.0f };
591  if (getloadavg(loadavg, 3) < 0) {
592    // Maybe we should return an error here or the availability of
593    // getloadavg(3) should be checked when ninja is configured.
594    return -0.0f;
595  }
596  return loadavg[0];
597}
598#endif // _WIN32
599
600string ElideMiddle(const string& str, size_t width) {
601  switch (width) {
602      case 0: return "";
603      case 1: return ".";
604      case 2: return "..";
605      case 3: return "...";
606  }
607  const int kMargin = 3;  // Space for "...".
608  string result = str;
609  if (result.size() > width) {
610    size_t elide_size = (width - kMargin) / 2;
611    result = result.substr(0, elide_size)
612      + "..."
613      + result.substr(result.size() - elide_size, elide_size);
614  }
615  return result;
616}
617
618bool Truncate(const string& path, size_t size, string* err) {
619#ifdef _WIN32
620  int fh = _sopen(path.c_str(), _O_RDWR | _O_CREAT, _SH_DENYNO,
621                  _S_IREAD | _S_IWRITE);
622  int success = _chsize(fh, size);
623  _close(fh);
624#else
625  int success = truncate(path.c_str(), size);
626#endif
627  // Both truncate() and _chsize() return 0 on success and set errno and return
628  // -1 on failure.
629  if (success < 0) {
630    *err = strerror(errno);
631    return false;
632  }
633  return true;
634}
635