[libc++] Add caching for feature-detection Lit tests

[ldionne]

Summary

This significantly speeds up the configuration of libc++'s test suite
by making sure that we don't perform the same operations over and over
again.

[arichardson]

Thanks, this is much better than my specialized version. However, I don't think it's correct since you are passing a reference to a mutable object to the cache so c.substitutions it will always be equal.
I just tested this and the cache will still hit if we append a value to config.substitutions between checks.

[ldionne]

In D89003#2321042, @arichardson wrote:

Thanks, this is much better than my specialized version. However, I don't think it's correct since you are passing a reference to a mutable object to the cache so c.substitutions it will always be equal.
I just tested this and the cache will still hit if we append a value to config.substitutions between checks.

Excellent catch! I fixed it in ddb2baf9fbff3d574c6c2bd69c2c9569100509a4.

[arichardson]

I think copy.deepcopy() (as I used in D89109) should be a bit faster than pickle and also provide the same guarantee?

[ldionne]

In D89003#2321797, @arichardson wrote:

I think copy.deepcopy() (as I used in D89109) should be a bit faster than pickle and also provide the same guarantee?

Oops, I'm sloppy -- I had not seen your D89109 yet. Sorry about that. Does deepcopy allow us to use a dict? If not, I think I still prefer dumping to a string for simplicity. Speed isn't a huge concern here if we compare pickling to running the processes.

[arichardson]

In D89003#2321797, @arichardson wrote:

I think copy.deepcopy() (as I used in D89109) should be a bit faster than pickle and also provide the same guarantee?

However, pickle() allows storing it in a dict, so it might be better for lookups.

[arichardson]

In D89003#2321810, @ldionne wrote:

In D89003#2321797, @arichardson wrote:

I think copy.deepcopy() (as I used in D89109) should be a bit faster than pickle and also provide the same guarantee?

Oops, I'm sloppy -- I had not seen your D89109 yet. Sorry about that. Does deepcopy allow us to use a dict? If not, I think I still prefer dumping to a string for simplicity. Speed isn't a huge concern here if we compare pickling to running the processes.

My bad, I should have linked the revision in this comment. I think doing the dict lookup is better since the cache ends up holding about 60 elements in some cases.

libcxx/utils/libcxx/test/dsl.py

 import libcxx.test.format
 import lit
 import lit.LitConfig
 import lit.Test
 import lit.TestRunner
 import lit.util
 
 
-def _memoize(f):
-  cache = dict()
-  def memoized(x):
-    if x not in cache:
-      cache[x] = f(x)
-    return cache[x]
-  return memoized
+def _memoizeExpensiveOperation(extractCacheKey):
+  """
+  Allows memoizing a very expensive operation.
+
+  The caching is implemented as a list, and we search linearly for existing
+  entries. This is incredibly naive, however this allows the cache keys to
+  contain lists and other non-hashable objects. Assuming the operation we're
+  memoizing is very expensive, this is still a win anyway.
+  """
+  def decorator(function):
+    cache = []
+    def f(*args, **kwargs):
+      cacheKey = extractCacheKey(*args, **kwargs)
+      try:
+        result = next(res for (key, res) in cache if key == cacheKey)
+      except StopIteration: # This wasn't in the cache
+        result = function(*args, **kwargs)
+        cache.append((cacheKey, result))
+      return result
+    return f
+  return decorator
 
 def _executeScriptInternal(test, commands):
   """
   Returns (stdout, stderr, exitCode, timeoutInfo)
 
   TODO: This really should be easier to access from Lit itself
   """
   parsedCommands = libcxx.test.format.parseScript(test, preamble=commands)
tmp = tempfile.NamedTemporaryFile(dir=sourceRoot, delete=False, suffix='.cpp',
                                     prefix=testPrefix)
   tmp.close()
   pathInSuite = [os.path.relpath(tmp.name, sourceRoot)]
   class TestWrapper(lit.Test.Test):
     def __enter__(self):       return self
     def __exit__(self, *args): os.remove(tmp.name)
   return TestWrapper(suite, pathInSuite, config)
 
+@_memoizeExpensiveOperation(lambda c, s: (c.substitutions, c.environment, s))
 def sourceBuilds(config, source):
   """
   Return whether the program in the given string builds successfully.
 
   This is done by compiling and linking a program that consists of the given
   source with the %{cxx} substitution, and seeing whether that succeeds.
   """
   with _makeConfigTest(config) as test:
     with open(test.getSourcePath(), 'w') as sourceFile:
       sourceFile.write(source)
     out, err, exitCode, timeoutInfo = _executeScriptInternal(test, [
       "%{cxx} %s %{flags} %{compile_flags} %{link_flags} -o %t.exe"
     ])
     _executeScriptInternal(test, ['rm %t.exe'])
     return exitCode == 0
 
+@_memoizeExpensiveOperation(lambda c, p, args, testPrefix: (c.substitutions, c.environment, p, args))
 def programOutput(config, program, args=None, testPrefix=''):
   """
   Compiles a program for the test target, run it on the test target and return
   the output.
 
   If the program fails to compile or run, None is returned instead. Note that
   execution of the program is done through the %{exec} substitution, which means
   that the program may be run on a remote host depending on what %{exec} does.
try:
 
       actualOut = re.search("command output:\n(.+)\n$", out, flags=re.DOTALL)
       actualOut = actualOut.group(1) if actualOut else ""
       return actualOut
 
     finally:
       _executeScriptInternal(test, ['rm %t.exe'])
 
+@_memoizeExpensiveOperation(lambda c, f: (c.substitutions, c.environment, f))
 def hasCompileFlag(config, flag):
   """
   Return whether the compiler in the configuration supports a given compiler flag.
 
   This is done by executing the %{cxx} substitution with the given flag and
   checking whether that succeeds.
   """
   with _makeConfigTest(config) as test:
     out, err, exitCode, timeoutInfo = _executeScriptInternal(test, [
       "%{{cxx}} -xc++ {} -Werror -fsyntax-only %{{flags}} %{{compile_flags}} {}".format(os.devnull, flag)
     ])
     return exitCode == 0
 
+@_memoizeExpensiveOperation(lambda c, l: (c.substitutions, c.environment, l))
 def hasLocale(config, locale):
   """
   Return whether the runtime execution environment supports a given locale.
 
   This is done by executing a program that tries to set the given locale using
   %{exec} -- this means that the command may be executed on a remote host
   depending on the %{exec} substitution.
   """
   program = """
     #include <locale.h>
     int main(int, char** argv) {
       if (::setlocale(LC_ALL, argv[1]) != NULL) return 0;
       else                                      return 1;
     }
   """
   return programOutput(config, program, args=[pipes.quote(locale)],
                        testPrefix="check_locale_" + locale) is not None
 
+@_memoizeExpensiveOperation(lambda c, flags='': (c.substitutions, c.environment, flags))
 def compilerMacros(config, flags=''):
   """
   Return a dictionary of predefined compiler macros.
 
   The keys are strings representing macros, and the values are strings
   representing what each macro is defined to.
 
   If the optional `flags` argument (a string) is provided, these flags will