clang/utils/token-delta.py

   1 #!/usr/bin/env python
   2
   3 from __future__ import absolute_import, division, print_function
   4 import os
   5 import re
   6 import subprocess
   7 import sys
   8 import tempfile
   9
  10 ###
  11
  12
  13 class DeltaAlgorithm(object):
  14     def __init__(self):
  15         self.cache = set()
  16
  17     def test(self, changes):
  18         abstract
  19
  20     ###
  21
  22     def getTestResult(self, changes):
  23         # There is no reason to cache successful tests because we will
  24         # always reduce the changeset when we see one.
  25
  26         changeset = frozenset(changes)
  27         if changeset in self.cache:
  28             return False
  29         elif not self.test(changes):
  30             self.cache.add(changeset)
  31             return False
  32         else:
  33             return True
  34
  35     def run(self, changes, force=False):
  36         # Make sure the initial test passes, if not then (a) either
  37         # the user doesn't expect monotonicity, and we may end up
  38         # doing O(N^2) tests, or (b) the test is wrong. Avoid the
  39         # O(N^2) case unless user requests it.
  40         if not force:
  41             if not self.getTestResult(changes):
  42                 raise ValueError("Initial test passed to delta fails.")
  43
  44         # Check empty set first to quickly find poor test functions.
  45         if self.getTestResult(set()):
  46             return set()
  47         else:
  48             return self.delta(changes, self.split(changes))
  49
  50     def split(self, S):
  51         """split(set) -> [sets]
  52
  53         Partition a set into one or two pieces.
  54         """
  55
  56         # There are many ways to split, we could do a better job with more
  57         # context information (but then the API becomes grosser).
  58         L = list(S)
  59         mid = len(L) // 2
  60         if mid == 0:
  61             return (L,)
  62         else:
  63             return L[:mid], L[mid:]
  64
  65     def delta(self, c, sets):
  66         # assert(reduce(set.union, sets, set()) == c)
  67
  68         # If there is nothing left we can remove, we are done.
  69         if len(sets) <= 1:
  70             return c
  71
  72         # Look for a passing subset.
  73         res = self.search(c, sets)
  74         if res is not None:
  75             return res
  76
  77         # Otherwise, partition sets if possible; if not we are done.
  78         refined = sum(map(list, map(self.split, sets)), [])
  79         if len(refined) == len(sets):
  80             return c
  81
  82         return self.delta(c, refined)
  83
  84     def search(self, c, sets):
  85         for i, S in enumerate(sets):
  86             # If test passes on this subset alone, recurse.
  87             if self.getTestResult(S):
  88                 return self.delta(S, self.split(S))
  89
  90             # Otherwise if we have more than two sets, see if test
  91             # pases without this subset.
  92             if len(sets) > 2:
  93                 complement = sum(sets[:i] + sets[i + 1 :], [])
  94                 if self.getTestResult(complement):
  95                     return self.delta(complement, sets[:i] + sets[i + 1 :])
  96
  97
  98 ###
  99
 100
 101 class Token(object):
 102     def __init__(self, type, data, flags, file, line, column):
 103         self.type = type
 104         self.data = data
 105         self.flags = flags
 106         self.file = file
 107         self.line = line
 108         self.column = column
 109
 110
 111 kTokenRE = re.compile(
 112     r"""([a-z_]+) '(.*)'\t(.*)\tLoc=<(.*):(.*):(.*)>""", re.DOTALL | re.MULTILINE
 113 )
 114
 115
 116 def getTokens(path):
 117     p = subprocess.Popen(
 118         ["clang", "-dump-raw-tokens", path],
 119         stdin=subprocess.PIPE,
 120         stdout=subprocess.PIPE,
 121         stderr=subprocess.PIPE,
 122     )
 123     out, err = p.communicate()
 124
 125     tokens = []
 126     collect = None
 127     for ln in err.split("\n"):
 128         # Silly programmers refuse to print in simple machine readable
 129         # formats. Whatever.
 130         if collect is None:
 131             collect = ln
 132         else:
 133             collect = collect + "\n" + ln
 134         if "Loc=<" in ln and ln.endswith(">"):
 135             ln, collect = collect, None
 136             tokens.append(Token(*kTokenRE.match(ln).groups()))
 137
 138     return tokens
 139
 140
 141 ###
 142
 143
 144 class TMBDDelta(DeltaAlgorithm):
 145     def __init__(self, testProgram, tokenLists, log):
 146         def patchName(name, suffix):
 147             base, ext = os.path.splitext(name)
 148             return base + "." + suffix + ext
 149
 150         super(TMBDDelta, self).__init__()
 151         self.testProgram = testProgram
 152         self.tokenLists = tokenLists
 153         self.tempFiles = [patchName(f, "tmp") for f, _ in self.tokenLists]
 154         self.targetFiles = [patchName(f, "ok") for f, _ in self.tokenLists]
 155         self.log = log
 156         self.numTests = 0
 157
 158     def writeFiles(self, changes, fileNames):
 159         assert len(fileNames) == len(self.tokenLists)
 160         byFile = [[] for i in self.tokenLists]
 161         for i, j in changes:
 162             byFile[i].append(j)
 163
 164         for i, (file, tokens) in enumerate(self.tokenLists):
 165             f = open(fileNames[i], "w")
 166             for j in byFile[i]:
 167                 f.write(tokens[j])
 168             f.close()
 169
 170         return byFile
 171
 172     def test(self, changes):
 173         self.numTests += 1
 174
 175         byFile = self.writeFiles(changes, self.tempFiles)
 176
 177         if self.log:
 178             print("TEST - ", end=" ", file=sys.stderr)
 179             if self.log > 1:
 180                 for i, (file, _) in enumerate(self.tokenLists):
 181                     indices = byFile[i]
 182                     if i:
 183                         sys.stderr.write("\n      ")
 184                     sys.stderr.write("%s:%d tokens: [" % (file, len(byFile[i])))
 185                     prev = None
 186                     for j in byFile[i]:
 187                         if prev is None or j != prev + 1:
 188                             if prev:
 189                                 sys.stderr.write("%d][" % prev)
 190                             sys.stderr.write(str(j))
 191                             sys.stderr.write(":")
 192                         prev = j
 193                     if byFile[i]:
 194                         sys.stderr.write(str(byFile[i][-1]))
 195                     sys.stderr.write("] ")
 196             else:
 197                 print(
 198                     ", ".join(
 199                         [
 200                             "%s:%d tokens" % (file, len(byFile[i]))
 201                             for i, (file, _) in enumerate(self.tokenLists)
 202                         ]
 203                     ),
 204                     end=" ",
 205                     file=sys.stderr,
 206                 )
 207
 208         p = subprocess.Popen([self.testProgram] + self.tempFiles)
 209         res = p.wait() == 0
 210
 211         if res:
 212             self.writeFiles(changes, self.targetFiles)
 213
 214         if self.log:
 215             print("=> %s" % res, file=sys.stderr)
 216         else:
 217             if res:
 218                 print("\nSUCCESS (%d tokens)" % len(changes))
 219             else:
 220                 sys.stderr.write(".")
 221
 222         return res
 223
 224     def run(self):
 225         res = super(TMBDDelta, self).run(
 226             [
 227                 (i, j)
 228                 for i, (file, tokens) in enumerate(self.tokenLists)
 229                 for j in range(len(tokens))
 230             ]
 231         )
 232         self.writeFiles(res, self.targetFiles)
 233         if not self.log:
 234             print(file=sys.stderr)
 235         return res
 236
 237
 238 def tokenBasedMultiDelta(program, files, log):
 239     # Read in the lists of tokens.
 240     tokenLists = [(file, [t.data for t in getTokens(file)]) for file in files]
 241
 242     numTokens = sum([len(tokens) for _, tokens in tokenLists])
 243     print("Delta on %s with %d tokens." % (", ".join(files), numTokens))
 244
 245     tbmd = TMBDDelta(program, tokenLists, log)
 246
 247     res = tbmd.run()
 248
 249     print(
 250         "Finished %s with %d tokens (in %d tests)."
 251         % (", ".join(tbmd.targetFiles), len(res), tbmd.numTests)
 252     )
 253
 254
 255 def main():
 256     from optparse import OptionParser, OptionGroup
 257
 258     parser = OptionParser("%prog <test program> {files+}")
 259     parser.add_option(
 260         "",
 261         "--debug",
 262         dest="debugLevel",
 263         help="set debug level [default %default]",
 264         action="store",
 265         type=int,
 266         default=0,
 267     )
 268     (opts, args) = parser.parse_args()
 269
 270     if len(args) <= 1:
 271         parser.error("Invalid number of arguments.")
 272
 273     program, files = args[0], args[1:]
 274
 275     md = tokenBasedMultiDelta(program, files, log=opts.debugLevel)
 276
 277
 278 if __name__ == "__main__":
 279     try:
 280         main()
 281     except KeyboardInterrupt:
 282         print("Interrupted.", file=sys.stderr)
 283         os._exit(1)  # Avoid freeing our giant cache.