1 #!/usr/bin/env python 2 # Copyright (c) 2012 The Chromium Authors. All rights reserved. 3 # Use of this source code is governed by a BSD-style license that can be 4 # found in the LICENSE file. 5 6 """Nodes for PPAPI IDL AST""" 7 8 # 9 # IDL Node 10 # 11 # IDL Node defines the IDLAttribute and IDLNode objects which are constructed 12 # by the parser as it processes the various 'productions'. The IDLAttribute 13 # objects are assigned to the IDLNode's property dictionary instead of being 14 # applied as children of The IDLNodes, so they do not exist in the final tree. 15 # The AST of IDLNodes is the output from the parsing state and will be used 16 # as the source data by the various generators. 17 # 18 19 import hashlib 20 import sys 21 22 from idl_log import ErrOut, InfoOut, WarnOut 23 from idl_propertynode import IDLPropertyNode 24 from idl_namespace import IDLNamespace 25 from idl_release import IDLRelease, IDLReleaseMap 26 27 28 # IDLAttribute 29 # 30 # A temporary object used by the parsing process to hold an Extended Attribute 31 # which will be passed as a child to a standard IDLNode. 32 # 33 class IDLAttribute(object): 34 def __init__(self, name, value): 35 self.cls = 'ExtAttribute' 36 self.name = name 37 self.value = value 38 39 def __str__(self): 40 return '%s=%s' % (self.name, self.value) 41 42 # 43 # IDLNode 44 # 45 # This class implements the AST tree, providing the associations between 46 # parents and children. It also contains a namepsace and propertynode to 47 # allow for look-ups. IDLNode is derived from IDLRelease, so it is 48 # version aware. 49 # 50 class IDLNode(IDLRelease): 51 52 # Set of object IDLNode types which have a name and belong in the namespace. 53 NamedSet = set(['Enum', 'EnumItem', 'File', 'Function', 'Interface', 54 'Member', 'Param', 'Struct', 'Type', 'Typedef']) 55 56 show_versions = False 57 def __init__(self, cls, filename, lineno, pos, children=None): 58 # Initialize with no starting or ending Version 59 IDLRelease.__init__(self, None, None) 60 61 self.cls = cls 62 self.lineno = lineno 63 self.pos = pos 64 self.filename = filename 65 self.filenode = None 66 self.hashes = {} 67 self.deps = {} 68 self.errors = 0 69 self.namespace = None 70 self.typelist = None 71 self.parent = None 72 self.property_node = IDLPropertyNode() 73 self.unique_releases = None 74 75 # A list of unique releases for this node 76 self.releases = None 77 78 # A map from any release, to the first unique release 79 self.first_release = None 80 81 # self.children is a list of children ordered as defined 82 self.children = [] 83 # Process the passed in list of children, placing ExtAttributes into the 84 # property dictionary, and nodes into the local child list in order. In 85 # addition, add nodes to the namespace if the class is in the NamedSet. 86 if not children: children = [] 87 for child in children: 88 if child.cls == 'ExtAttribute': 89 self.SetProperty(child.name, child.value) 90 else: 91 self.AddChild(child) 92 93 # 94 # String related functions 95 # 96 # 97 98 # Return a string representation of this node 99 def __str__(self): 100 name = self.GetName() 101 ver = IDLRelease.__str__(self) 102 if name is None: name = '' 103 if not IDLNode.show_versions: ver = '' 104 return '%s(%s%s)' % (self.cls, name, ver) 105 106 # Return file and line number for where node was defined 107 def Location(self): 108 return '%s(%d)' % (self.filename, self.lineno) 109 110 # Log an error for this object 111 def Error(self, msg): 112 self.errors += 1 113 ErrOut.LogLine(self.filename, self.lineno, 0, ' %s %s' % 114 (str(self), msg)) 115 if self.filenode: 116 errcnt = self.filenode.GetProperty('ERRORS', 0) 117 self.filenode.SetProperty('ERRORS', errcnt + 1) 118 119 # Log a warning for this object 120 def Warning(self, msg): 121 WarnOut.LogLine(self.filename, self.lineno, 0, ' %s %s' % 122 (str(self), msg)) 123 124 def GetName(self): 125 return self.GetProperty('NAME') 126 127 def GetNameVersion(self): 128 name = self.GetProperty('NAME', default='') 129 ver = IDLRelease.__str__(self) 130 return '%s%s' % (name, ver) 131 132 # Dump this object and its children 133 def Dump(self, depth=0, comments=False, out=sys.stdout): 134 if self.cls in ['Comment', 'Copyright']: 135 is_comment = True 136 else: 137 is_comment = False 138 139 # Skip this node if it's a comment, and we are not printing comments 140 if not comments and is_comment: return 141 142 tab = ''.rjust(depth * 2) 143 if is_comment: 144 out.write('%sComment\n' % tab) 145 for line in self.GetName().split('\n'): 146 out.write('%s "%s"\n' % (tab, line)) 147 else: 148 ver = IDLRelease.__str__(self) 149 if self.releases: 150 release_list = ': ' + ' '.join(self.releases) 151 else: 152 release_list = ': undefined' 153 out.write('%s%s%s%s\n' % (tab, self, ver, release_list)) 154 if self.typelist: 155 out.write('%s Typelist: %s\n' % (tab, self.typelist.GetReleases()[0])) 156 properties = self.property_node.GetPropertyList() 157 if properties: 158 out.write('%s Properties\n' % tab) 159 for p in properties: 160 if is_comment and p == 'NAME': 161 # Skip printing the name for comments, since we printed above already 162 continue 163 out.write('%s %s : %s\n' % (tab, p, self.GetProperty(p))) 164 for child in self.children: 165 child.Dump(depth+1, comments=comments, out=out) 166 167 # 168 # Search related functions 169 # 170 # Check if node is of a given type 171 def IsA(self, *typelist): 172 if self.cls in typelist: return True 173 return False 174 175 # Get a list of objects for this key 176 def GetListOf(self, *keys): 177 out = [] 178 for child in self.children: 179 if child.cls in keys: out.append(child) 180 return out 181 182 def GetOneOf(self, *keys): 183 out = self.GetListOf(*keys) 184 if out: return out[0] 185 return None 186 187 def SetParent(self, parent): 188 self.property_node.AddParent(parent) 189 self.parent = parent 190 191 def AddChild(self, node): 192 node.SetParent(self) 193 self.children.append(node) 194 195 # Get a list of all children 196 def GetChildren(self): 197 return self.children 198 199 # Get a list of all children of a given version 200 def GetChildrenVersion(self, version): 201 out = [] 202 for child in self.children: 203 if child.IsVersion(version): out.append(child) 204 return out 205 206 # Get a list of all children in a given range 207 def GetChildrenRange(self, vmin, vmax): 208 out = [] 209 for child in self.children: 210 if child.IsRange(vmin, vmax): out.append(child) 211 return out 212 213 def FindVersion(self, name, version): 214 node = self.namespace.FindNode(name, version) 215 if not node and self.parent: 216 node = self.parent.FindVersion(name, version) 217 return node 218 219 def FindRange(self, name, vmin, vmax): 220 nodes = self.namespace.FindNodes(name, vmin, vmax) 221 if not nodes and self.parent: 222 nodes = self.parent.FindVersion(name, vmin, vmax) 223 return nodes 224 225 def GetType(self, release): 226 if not self.typelist: return None 227 return self.typelist.FindRelease(release) 228 229 def GetHash(self, release): 230 hashval = self.hashes.get(release, None) 231 if hashval is None: 232 hashval = hashlib.sha1() 233 hashval.update(self.cls) 234 for key in self.property_node.GetPropertyList(): 235 val = self.GetProperty(key) 236 hashval.update('%s=%s' % (key, str(val))) 237 typeref = self.GetType(release) 238 if typeref: 239 hashval.update(typeref.GetHash(release)) 240 for child in self.GetChildren(): 241 if child.IsA('Copyright', 'Comment', 'Label'): continue 242 if not child.IsRelease(release): 243 continue 244 hashval.update( child.GetHash(release) ) 245 self.hashes[release] = hashval 246 return hashval.hexdigest() 247 248 def GetDeps(self, release, visited=None): 249 visited = visited or set() 250 251 # If this release is not valid for this object, then done. 252 if not self.IsRelease(release) or self.IsA('Comment', 'Copyright'): 253 return set([]) 254 255 # If we have cached the info for this release, return the cached value 256 deps = self.deps.get(release, None) 257 if deps is not None: 258 return deps 259 260 # If we are already visited, then return 261 if self in visited: 262 return set([self]) 263 264 # Otherwise, build the dependency list 265 visited |= set([self]) 266 deps = set([self]) 267 268 # Get child deps 269 for child in self.GetChildren(): 270 deps |= child.GetDeps(release, visited) 271 visited |= set(deps) 272 273 # Get type deps 274 typeref = self.GetType(release) 275 if typeref: 276 deps |= typeref.GetDeps(release, visited) 277 278 self.deps[release] = deps 279 return deps 280 281 def GetVersion(self, release): 282 filenode = self.GetProperty('FILE') 283 if not filenode: 284 return None 285 return filenode.release_map.GetVersion(release) 286 287 def GetUniqueReleases(self, releases): 288 """Return the unique set of first releases corresponding to input 289 290 Since we are returning the corresponding 'first' version for a 291 release, we may return a release version prior to the one in the list.""" 292 my_min, my_max = self.GetMinMax(releases) 293 if my_min > releases[-1] or my_max < releases[0]: 294 return [] 295 296 out = set() 297 for rel in releases: 298 remapped = self.first_release[rel] 299 if not remapped: continue 300 out |= set([remapped]) 301 302 # Cache the most recent set of unique_releases 303 self.unique_releases = sorted(out) 304 return self.unique_releases 305 306 def LastRelease(self, release): 307 # Get the most recent release from the most recently generated set of 308 # cached unique releases. 309 if self.unique_releases and self.unique_releases[-1] > release: 310 return False 311 return True 312 313 def GetRelease(self, version): 314 filenode = self.GetProperty('FILE') 315 if not filenode: 316 return None 317 return filenode.release_map.GetRelease(version) 318 319 def _GetReleases(self, releases): 320 if not self.releases: 321 my_min, my_max = self.GetMinMax(releases) 322 my_releases = [my_min] 323 if my_max != releases[-1]: 324 my_releases.append(my_max) 325 my_releases = set(my_releases) 326 for child in self.GetChildren(): 327 if child.IsA('Copyright', 'Comment', 'Label'): 328 continue 329 my_releases |= child.GetReleases(releases) 330 self.releases = my_releases 331 return self.releases 332 333 334 def _GetReleaseList(self, releases, visited=None): 335 visited = visited or set() 336 if not self.releases: 337 # If we are unversionable, then return first available release 338 if self.IsA('Comment', 'Copyright', 'Label'): 339 self.releases = [] 340 return self.releases 341 342 # Generate the first and if deprecated within this subset, the 343 # last release for this node 344 my_min, my_max = self.GetMinMax(releases) 345 346 if my_max != releases[-1]: 347 my_releases = set([my_min, my_max]) 348 else: 349 my_releases = set([my_min]) 350 351 # Break cycle if we reference ourselves 352 if self in visited: 353 return [my_min] 354 355 visited |= set([self]) 356 357 # Files inherit all their releases from items in the file 358 if self.IsA('AST', 'File'): 359 my_releases = set() 360 361 # Visit all children 362 child_releases = set() 363 364 # Exclude sibling results from parent visited set 365 cur_visits = visited 366 367 for child in self.children: 368 child_releases |= set(child._GetReleaseList(releases, cur_visits)) 369 visited |= set(child_releases) 370 371 # Visit my type 372 type_releases = set() 373 if self.typelist: 374 type_list = self.typelist.GetReleases() 375 for typenode in type_list: 376 type_releases |= set(typenode._GetReleaseList(releases, cur_visits)) 377 378 type_release_list = sorted(type_releases) 379 if my_min < type_release_list[0]: 380 type_node = type_list[0] 381 self.Error('requires %s in %s which is undefined at %s.' % ( 382 type_node, type_node.filename, my_min)) 383 384 for rel in child_releases | type_releases: 385 if rel >= my_min and rel <= my_max: 386 my_releases |= set([rel]) 387 388 self.releases = sorted(my_releases) 389 return self.releases 390 391 def GetReleaseList(self): 392 return self.releases 393 394 def BuildReleaseMap(self, releases): 395 unique_list = self._GetReleaseList(releases) 396 my_min, my_max = self.GetMinMax(releases) 397 398 self.first_release = {} 399 last_rel = None 400 for rel in releases: 401 if rel in unique_list: 402 last_rel = rel 403 self.first_release[rel] = last_rel 404 if rel == my_max: 405 last_rel = None 406 407 def SetProperty(self, name, val): 408 self.property_node.SetProperty(name, val) 409 410 def GetProperty(self, name, default=None): 411 return self.property_node.GetProperty(name, default) 412 413 def Traverse(self, data, func): 414 func(self, data) 415 for child in self.children: 416 child.Traverse(data, func) 417 418 419 # 420 # IDLFile 421 # 422 # A specialized version of IDLNode which tracks errors and warnings. 423 # 424 class IDLFile(IDLNode): 425 def __init__(self, name, children, errors=0): 426 attrs = [IDLAttribute('NAME', name), 427 IDLAttribute('ERRORS', errors)] 428 if not children: children = [] 429 IDLNode.__init__(self, 'File', name, 1, 0, attrs + children) 430 self.release_map = IDLReleaseMap([('M13', 1.0)]) 431 432 433 # 434 # Tests 435 # 436 def StringTest(): 437 errors = 0 438 name_str = 'MyName' 439 text_str = 'MyNode(%s)' % name_str 440 name_node = IDLAttribute('NAME', name_str) 441 node = IDLNode('MyNode', 'no file', 1, 0, [name_node]) 442 if node.GetName() != name_str: 443 ErrOut.Log('GetName returned >%s< not >%s<' % (node.GetName(), name_str)) 444 errors += 1 445 if node.GetProperty('NAME') != name_str: 446 ErrOut.Log('Failed to get name property.') 447 errors += 1 448 if str(node) != text_str: 449 ErrOut.Log('str() returned >%s< not >%s<' % (str(node), text_str)) 450 errors += 1 451 if not errors: InfoOut.Log('Passed StringTest') 452 return errors 453 454 455 def ChildTest(): 456 errors = 0 457 child = IDLNode('child', 'no file', 1, 0) 458 parent = IDLNode('parent', 'no file', 1, 0, [child]) 459 460 if child.parent != parent: 461 ErrOut.Log('Failed to connect parent.') 462 errors += 1 463 464 if [child] != parent.GetChildren(): 465 ErrOut.Log('Failed GetChildren.') 466 errors += 1 467 468 if child != parent.GetOneOf('child'): 469 ErrOut.Log('Failed GetOneOf(child)') 470 errors += 1 471 472 if parent.GetOneOf('bogus'): 473 ErrOut.Log('Failed GetOneOf(bogus)') 474 errors += 1 475 476 if not parent.IsA('parent'): 477 ErrOut.Log('Expecting parent type') 478 errors += 1 479 480 parent = IDLNode('parent', 'no file', 1, 0, [child, child]) 481 if [child, child] != parent.GetChildren(): 482 ErrOut.Log('Failed GetChildren2.') 483 errors += 1 484 485 if not errors: InfoOut.Log('Passed ChildTest') 486 return errors 487 488 489 def Main(): 490 errors = StringTest() 491 errors += ChildTest() 492 493 if errors: 494 ErrOut.Log('IDLNode failed with %d errors.' % errors) 495 return -1 496 return 0 497 498 if __name__ == '__main__': 499 sys.exit(Main()) 500 501