camera/docs/metadata_model.py

   1 #!/usr/bin/python
   2
   3 #
   4 # Copyright (C) 2012 The Android Open Source Project
   5 #
   6 # Licensed under the Apache License, Version 2.0 (the "License");
   7 # you may not use this file except in compliance with the License.
   8 # You may obtain a copy of the License at
   9 #
  10 #      http://www.apache.org/licenses/LICENSE-2.0
  11 #
  12 # Unless required by applicable law or agreed to in writing, software
  13 # distributed under the License is distributed on an "AS IS" BASIS,
  14 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15 # See the License for the specific language governing permissions and
  16 # limitations under the License.
  17 #
  18
  19 """
  20 A set of classes (models) each closely representing an XML node in the
  21 metadata_properties.xml file.
  22
  23   Node: Base class for most nodes.
  24   Entry: A node corresponding to <entry> elements.
  25   Clone: A node corresponding to <clone> elements.
  26   MergedEntry: A node corresponding to either <entry> or <clone> elements.
  27   Kind: A node corresponding to <dynamic>, <static>, <controls> elements.
  28   InnerNamespace: A node corresponding to a <namespace> nested under a <kind>.
  29   OuterNamespace: A node corresponding to a <namespace> with <kind> children.
  30   Section: A node corresponding to a <section> element.
  31   Enum: A class corresponding an <enum> element within an <entry>
  32   EnumValue: A class corresponding to a <value> element within an Enum
  33   Metadata: Root node that also provides tree construction functionality.
  34   Tag: A node corresponding to a top level <tag> element.
  35   Typedef: A node corresponding to a <typedef> element under <types>.
  36 """
  37
  38 import sys
  39 import itertools
  40 from collections import OrderedDict
  41
  42 class Node(object):
  43   """
  44   Base class for most nodes that are part of the Metadata graph.
  45
  46   Attributes (Read-Only):
  47     parent: An edge to a parent Node.
  48     name: A string describing the name, usually but not always the 'name'
  49           attribute of the corresponding XML node.
  50   """
  51
  52   def __init__(self):
  53     self._parent = None
  54     self._name = None
  55
  56   @property
  57   def parent(self):
  58     return self._parent
  59
  60   @property
  61   def name(self):
  62     return self._name
  63
  64   def find_all(self, pred):
  65     """
  66     Find all descendants that match the predicate.
  67
  68     Args:
  69       pred: a predicate function that acts as a filter for a Node
  70
  71     Yields:
  72       A sequence of all descendants for which pred(node) is true,
  73       in a pre-order visit order.
  74     """
  75     if pred(self):
  76       yield self
  77
  78     if self._get_children() is None:
  79       return
  80
  81     for i in self._get_children():
  82       for j in i.find_all(pred):
  83         yield j
  84
  85   def find_first(self, pred):
  86     """
  87     Find the first descendant that matches the predicate.
  88
  89     Args:
  90       pred: a predicate function that acts as a filter for a Node
  91
  92     Returns:
  93       The first Node from find_all(pred), or None if there were no results.
  94     """
  95     for i in self.find_all(pred):
  96       return i
  97
  98     return None
  99
 100   def find_parent_first(self, pred):
 101     """
 102     Find the first ancestor that matches the predicate.
 103
 104     Args:
 105       pred: A predicate function that acts as a filter for a Node
 106
 107     Returns:
 108       The first ancestor closest to the node for which pred(node) is true.
 109     """
 110     for i in self.find_parents(pred):
 111       return i
 112
 113     return None
 114
 115   def find_parents(self, pred):
 116     """
 117     Find all ancestors that match the predicate.
 118
 119     Args:
 120       pred: A predicate function that acts as a filter for a Node
 121
 122     Yields:
 123       A sequence of all ancestors (closest to furthest) from the node,
 124       where pred(node) is true.
 125     """
 126     parent = self.parent
 127
 128     while parent is not None:
 129       if pred(parent):
 130         yield parent
 131       parent = parent.parent
 132
 133   def sort_children(self):
 134     """
 135     Sorts the immediate children in-place.
 136     """
 137     self._sort_by_name(self._children)
 138
 139   def _sort_by_name(self, what):
 140     what.sort(key=lambda x: x.name)
 141
 142   def _get_name(self):
 143     return lambda x: x.name
 144
 145   # Iterate over all children nodes. None when node doesn't support children.
 146   def _get_children(self):
 147     return (i for i in self._children)
 148
 149   def _children_name_map_matching(self, match=lambda x: True):
 150     d = {}
 151     for i in self._get_children():
 152       if match(i):
 153         d[i.name] = i
 154     return d
 155
 156   @staticmethod
 157   def _dictionary_by_name(values):
 158     d = OrderedDict()
 159     for i in values:
 160       d[i.name] = i
 161
 162     return d
 163
 164   def validate_tree(self):
 165     """
 166     Sanity check the tree recursively, ensuring for a node n, all children's
 167     parents are also n.
 168
 169     Returns:
 170       True if validation succeeds, False otherwise.
 171     """
 172     succ = True
 173     children = self._get_children()
 174     if children is None:
 175       return True
 176
 177     for child in self._get_children():
 178       if child.parent != self:
 179         print >> sys.stderr, ("ERROR: Node '%s' doesn't match the parent" +    \
 180                              "(expected: %s, actual %s)")                      \
 181                              %(child, self, child.parent)
 182         succ = False
 183
 184       succ = child.validate_tree() and succ
 185
 186     return succ
 187
 188   def __str__(self):
 189     return "<%s name='%s'>" %(self.__class__, self.name)
 190
 191 class Metadata(Node):
 192   """
 193   A node corresponding to a <metadata> entry.
 194
 195   Attributes (Read-Only):
 196     parent: An edge to the parent Node. This is always None for Metadata.
 197     outer_namespaces: A sequence of immediate OuterNamespace children.
 198     tags: A sequence of all Tag instances available in the graph.
 199     types: An iterable of all Typedef instances available in the graph.
 200   """
 201
 202   def __init__(self):
 203     """
 204     Initialize with no children. Use insert_* functions and then
 205     construct_graph() to build up the Metadata from some source.
 206     """
 207 # Private
 208     self._entries = []
 209     # kind => { name => entry }
 210     self._entry_map = { 'static': {}, 'dynamic': {}, 'controls': {} }
 211     self._entries_ordered = [] # list of ordered Entry/Clone instances
 212     self._clones = []
 213
 214 # Public (Read Only)
 215     self._name = None
 216     self._parent = None
 217     self._outer_namespaces = None
 218     self._tags = []
 219     self._types = []
 220
 221   @property
 222   def outer_namespaces(self):
 223     if self._outer_namespaces is None:
 224       return None
 225     else:
 226       return (i for i in self._outer_namespaces)
 227
 228   @property
 229   def tags(self):
 230     return (i for i in self._tags)
 231
 232   @property
 233   def types(self):
 234     return (i for i in self._types)
 235
 236   def _get_properties(self):
 237
 238     for i in self._entries:
 239       yield i
 240
 241     for i in self._clones:
 242       yield i
 243
 244   def insert_tag(self, tag, description=""):
 245     """
 246     Insert a tag into the metadata.
 247
 248     Args:
 249       tag: A string identifier for a tag.
 250       description: A string description for a tag.
 251
 252     Example:
 253       metadata.insert_tag("BC", "Backwards Compatibility for old API")
 254
 255     Remarks:
 256       Subsequent calls to insert_tag with the same tag are safe (they will
 257       be ignored).
 258     """
 259     tag_ids = [tg.name for tg in self.tags if tg.name == tag]
 260     if not tag_ids:
 261       self._tags.append(Tag(tag, self, description))
 262
 263   def insert_type(self, type_name, type_selector="typedef", **kwargs):
 264     """
 265     Insert a type into the metadata.
 266
 267     Args:
 268       type_name: A type's name
 269       type_selector: The selector for the type, e.g. 'typedef'
 270
 271     Args (if type_selector == 'typedef'):
 272       languages: A map of 'language name' -> 'fully qualified class path'
 273
 274     Example:
 275       metadata.insert_type('rectangle', 'typedef',
 276                            { 'java': 'android.graphics.Rect' })
 277
 278     Remarks:
 279       Subsequent calls to insert_type with the same type name are safe (they
 280       will be ignored)
 281     """
 282
 283     if type_selector != 'typedef':
 284       raise ValueError("Unsupported type_selector given " + type_selector)
 285
 286     type_names = [tp.name for tp in self.types if tp.name == tp]
 287     if not type_names:
 288       self._types.append(Typedef(type_name, self, kwargs.get('languages')))
 289
 290   def insert_entry(self, entry):
 291     """
 292     Insert an entry into the metadata.
 293
 294     Args:
 295       entry: A key-value dictionary describing an entry. Refer to
 296              Entry#__init__ for the keys required/optional.
 297
 298     Remarks:
 299       Subsequent calls to insert_entry with the same entry+kind name are safe
 300       (they will be ignored).
 301     """
 302     e = Entry(**entry)
 303     self._entries.append(e)
 304     self._entry_map[e.kind][e.name] = e
 305     self._entries_ordered.append(e)
 306
 307   def insert_clone(self, clone):
 308     """
 309     Insert a clone into the metadata.
 310
 311     Args:
 312       clone: A key-value dictionary describing a clone. Refer to
 313             Clone#__init__ for the keys required/optional.
 314
 315     Remarks:
 316       Subsequent calls to insert_clone with the same clone+kind name are safe
 317       (they will be ignored). Also the target entry need not be inserted
 318       ahead of the clone entry.
 319     """
 320     # figure out corresponding entry later. allow clone insert, entry insert
 321     entry = None
 322     c = Clone(entry, **clone)
 323     self._entry_map[c.kind][c.name] = c
 324     self._clones.append(c)
 325     self._entries_ordered.append(c)
 326
 327   def prune_clones(self):
 328     """
 329     Remove all clones that don't point to an existing entry.
 330
 331     Remarks:
 332       This should be called after all insert_entry/insert_clone calls have
 333       finished.
 334     """
 335     remove_list = []
 336     for p in self._clones:
 337       if p.entry is None:
 338         remove_list.append(p)
 339
 340     for p in remove_list:
 341
 342       # remove from parent's entries list
 343       if p.parent is not None:
 344         p.parent._entries.remove(p)
 345       # remove from parents' _leafs list
 346       for ancestor in p.find_parents(lambda x: not isinstance(x, Metadata)):
 347         ancestor._leafs.remove(p)
 348
 349       # remove from global list
 350       self._clones.remove(p)
 351       self._entry_map[p.kind].pop(p.name)
 352       self._entries_ordered.remove(p)
 353
 354
 355   # After all entries/clones are inserted,
 356   # invoke this to generate the parent/child node graph all these objects
 357   def construct_graph(self):
 358     """
 359     Generate the graph recursively, after which all Entry nodes will be
 360     accessible recursively by crawling through the outer_namespaces sequence.
 361
 362     Remarks:
 363       This is safe to be called multiple times at any time. It should be done at
 364       least once or there will be no graph.
 365     """
 366     self.validate_tree()
 367     self._construct_tags()
 368     self.validate_tree()
 369     self._construct_types()
 370     self.validate_tree()
 371     self._construct_clones()
 372     self.validate_tree()
 373     self._construct_outer_namespaces()
 374     self.validate_tree()
 375
 376   def _construct_tags(self):
 377     tag_dict = self._dictionary_by_name(self.tags)
 378     for p in self._get_properties():
 379       p._tags = []
 380       for tag_id in p._tag_ids:
 381         tag = tag_dict.get(tag_id)
 382
 383         if tag not in p._tags:
 384           p._tags.append(tag)
 385
 386         if p not in tag.entries:
 387           tag._entries.append(p)
 388
 389   def _construct_types(self):
 390     type_dict = self._dictionary_by_name(self.types)
 391     for p in self._get_properties():
 392       if p._type_name:
 393         type_node = type_dict.get(p._type_name)
 394         p._typedef = type_node
 395
 396         if p not in type_node.entries:
 397           type_node._entries.append(p)
 398
 399   def _construct_clones(self):
 400     for p in self._clones:
 401       target_kind = p.target_kind
 402       target_entry = self._entry_map[target_kind].get(p.name)
 403       p._entry = target_entry
 404
 405       # should not throw if we pass validation
 406       # but can happen when importing obsolete CSV entries
 407       if target_entry is None:
 408         print >> sys.stderr, ("WARNING: Clone entry '%s' target kind '%s'" +   \
 409                               " has no corresponding entry")                   \
 410                              %(p.name, p.target_kind)
 411
 412   def _construct_outer_namespaces(self):
 413
 414     if self._outer_namespaces is None: #the first time this runs
 415       self._outer_namespaces = []
 416
 417     root = self._dictionary_by_name(self._outer_namespaces)
 418     for ons_name, ons in root.iteritems():
 419       ons._leafs = []
 420
 421     for p in self._entries_ordered:
 422       ons_name = p.get_outer_namespace()
 423       ons = root.get(ons_name, OuterNamespace(ons_name, self))
 424       root[ons_name] = ons
 425
 426       if p not in ons._leafs:
 427         ons._leafs.append(p)
 428
 429     for ons_name, ons in root.iteritems():
 430
 431       ons.validate_tree()
 432
 433       self._construct_sections(ons)
 434
 435       if ons not in self._outer_namespaces:
 436         self._outer_namespaces.append(ons)
 437
 438       ons.validate_tree()
 439
 440   def _construct_sections(self, outer_namespace):
 441
 442     sections_dict = self._dictionary_by_name(outer_namespace.sections)
 443     for sec_name, sec in sections_dict.iteritems():
 444       sec._leafs = []
 445       sec.validate_tree()
 446
 447     for p in outer_namespace._leafs:
 448       does_exist = sections_dict.get(p.get_section())
 449
 450       sec = sections_dict.get(p.get_section(), \
 451           Section(p.get_section(), outer_namespace))
 452       sections_dict[p.get_section()] = sec
 453
 454       sec.validate_tree()
 455
 456       if p not in sec._leafs:
 457         sec._leafs.append(p)
 458
 459     for sec_name, sec in sections_dict.iteritems():
 460
 461       if not sec.validate_tree():
 462         print >> sys.stderr, ("ERROR: Failed to validate tree in " +           \
 463                              "construct_sections (start), with section = '%s'")\
 464                              %(sec)
 465
 466       self._construct_kinds(sec)
 467
 468       if sec not in outer_namespace.sections:
 469         outer_namespace._sections.append(sec)
 470
 471       if not sec.validate_tree():
 472         print >> sys.stderr, ("ERROR: Failed to validate tree in " +           \
 473                               "construct_sections (end), with section = '%s'") \
 474                              %(sec)
 475
 476   # 'controls', 'static' 'dynamic'. etc
 477   def _construct_kinds(self, section):
 478     for kind in section.kinds:
 479       kind._leafs = []
 480       section.validate_tree()
 481
 482     group_entry_by_kind = itertools.groupby(section._leafs, lambda x: x.kind)
 483     leaf_it = ((k, g) for k, g in group_entry_by_kind)
 484
 485     # allow multiple kinds with the same name. merge if adjacent
 486     # e.g. dynamic,dynamic,static,static,dynamic -> dynamic,static,dynamic
 487     # this helps maintain ABI compatibility when adding an entry in a new kind
 488     for idx, (kind_name, entry_it) in enumerate(leaf_it):
 489       if idx >= len(section._kinds):
 490         kind = Kind(kind_name, section)
 491         section._kinds.append(kind)
 492         section.validate_tree()
 493
 494       kind = section._kinds[idx]
 495
 496       for p in entry_it:
 497         if p not in kind._leafs:
 498           kind._leafs.append(p)
 499
 500     for kind in section._kinds:
 501       kind.validate_tree()
 502       self._construct_inner_namespaces(kind)
 503       kind.validate_tree()
 504       self._construct_entries(kind)
 505       kind.validate_tree()
 506
 507       if not section.validate_tree():
 508         print >> sys.stderr, ("ERROR: Failed to validate tree in " +           \
 509                              "construct_kinds, with kind = '%s'") %(kind)
 510
 511       if not kind.validate_tree():
 512         print >> sys.stderr, ("ERROR: Failed to validate tree in " +           \
 513                               "construct_kinds, with kind = '%s'") %(kind)
 514
 515   def _construct_inner_namespaces(self, parent, depth=0):
 516     #parent is InnerNamespace or Kind
 517     ins_dict = self._dictionary_by_name(parent.namespaces)
 518     for name, ins in ins_dict.iteritems():
 519       ins._leafs = []
 520
 521     for p in parent._leafs:
 522       ins_list = p.get_inner_namespace_list()
 523
 524       if len(ins_list) > depth:
 525         ins_str = ins_list[depth]
 526         ins = ins_dict.get(ins_str, InnerNamespace(ins_str, parent))
 527         ins_dict[ins_str] = ins
 528
 529         if p not in ins._leafs:
 530           ins._leafs.append(p)
 531
 532     for name, ins in ins_dict.iteritems():
 533       ins.validate_tree()
 534       # construct children INS
 535       self._construct_inner_namespaces(ins, depth + 1)
 536       ins.validate_tree()
 537       # construct children entries
 538       self._construct_entries(ins, depth + 1)
 539
 540       if ins not in parent.namespaces:
 541         parent._namespaces.append(ins)
 542
 543       if not ins.validate_tree():
 544         print >> sys.stderr, ("ERROR: Failed to validate tree in " +           \
 545                               "construct_inner_namespaces, with ins = '%s'")   \
 546                              %(ins)
 547
 548   # doesnt construct the entries, so much as links them
 549   def _construct_entries(self, parent, depth=0):
 550     #parent is InnerNamespace or Kind
 551     entry_dict = self._dictionary_by_name(parent.entries)
 552     for p in parent._leafs:
 553       ins_list = p.get_inner_namespace_list()
 554
 555       if len(ins_list) == depth:
 556         entry = entry_dict.get(p.name, p)
 557         entry_dict[p.name] = entry
 558
 559     for name, entry in entry_dict.iteritems():
 560
 561       old_parent = entry.parent
 562       entry._parent = parent
 563
 564       if entry not in parent.entries:
 565         parent._entries.append(entry)
 566
 567       if old_parent is not None and old_parent != parent:
 568         print >> sys.stderr, ("ERROR: Parent changed from '%s' to '%s' for " + \
 569                               "entry '%s'")                                    \
 570                              %(old_parent.name, parent.name, entry.name)
 571
 572   def _get_children(self):
 573     if self.outer_namespaces is not None:
 574       for i in self.outer_namespaces:
 575         yield i
 576
 577     if self.tags is not None:
 578       for i in self.tags:
 579         yield i
 580
 581 class Tag(Node):
 582   """
 583   A tag Node corresponding to a top-level <tag> element.
 584
 585   Attributes (Read-Only):
 586     name: alias for id
 587     id: The name of the tag, e.g. for <tag id="BC"/> id = 'BC'
 588     description: The description of the tag, the contents of the <tag> element.
 589     parent: An edge to the parent, which is always the Metadata root node.
 590     entries: A sequence of edges to entries/clones that are using this Tag.
 591   """
 592   def __init__(self, name, parent, description=""):
 593     self._name        = name  # 'id' attribute in XML
 594     self._id          = name
 595     self._description = description
 596     self._parent      = parent
 597
 598     # all entries that have this tag, including clones
 599     self._entries     = []  # filled in by Metadata#construct_tags
 600
 601   @property
 602   def id(self):
 603     return self._id
 604
 605   @property
 606   def description(self):
 607     return self._description
 608
 609   @property
 610   def entries(self):
 611     return (i for i in self._entries)
 612
 613   def _get_children(self):
 614     return None
 615
 616 class Typedef(Node):
 617   """
 618   A typedef Node corresponding to a <typedef> element under a top-level <types>.
 619
 620   Attributes (Read-Only):
 621     name: The name of this typedef as a string.
 622     languages: A dictionary of 'language name' -> 'fully qualified class'.
 623     parent: An edge to the parent, which is always the Metadata root node.
 624     entries: An iterable over all entries which reference this typedef.
 625   """
 626   def __init__(self, name, parent, languages=None):
 627     self._name        = name
 628     self._parent      = parent
 629
 630     # all entries that have this typedef
 631     self._entries     = []  # filled in by Metadata#construct_types
 632
 633     self._languages   = languages or {}
 634
 635   @property
 636   def languages(self):
 637     return self._languages
 638
 639   @property
 640   def entries(self):
 641     return (i for i in self._entries)
 642
 643   def _get_children(self):
 644     return None
 645
 646 class OuterNamespace(Node):
 647   """
 648   A node corresponding to a <namespace> element under <metadata>
 649
 650   Attributes (Read-Only):
 651     name: The name attribute of the <namespace name="foo"> element.
 652     parent: An edge to the parent, which is always the Metadata root node.
 653     sections: A sequence of Section children.
 654   """
 655   def __init__(self, name, parent, sections=[]):
 656     self._name = name
 657     self._parent = parent # MetadataSet
 658     self._sections = sections[:]
 659     self._leafs = []
 660
 661     self._children = self._sections
 662
 663   @property
 664   def sections(self):
 665     return (i for i in self._sections)
 666
 667 class Section(Node):
 668   """
 669   A node corresponding to a <section> element under <namespace>
 670
 671   Attributes (Read-Only):
 672     name: The name attribute of the <section name="foo"> element.
 673     parent: An edge to the parent, which is always an OuterNamespace instance.
 674     description: A string description of the section, or None.
 675     kinds: A sequence of Kind children.
 676     merged_kinds: A sequence of virtual Kind children,
 677                   with each Kind's children merged by the kind.name
 678   """
 679   def __init__(self, name, parent, description=None, kinds=[]):
 680     self._name = name
 681     self._parent = parent
 682     self._description = description
 683     self._kinds = kinds[:]
 684
 685     self._leafs = []
 686
 687
 688   @property
 689   def description(self):
 690     return self._description
 691
 692   @property
 693   def kinds(self):
 694     return (i for i in self._kinds)
 695
 696   def sort_children(self):
 697     self.validate_tree()
 698     # order is always controls,static,dynamic
 699     find_child = lambda x: [i for i in self._get_children() if i.name == x]
 700     new_lst = find_child('controls') \
 701             + find_child('static')   \
 702             + find_child('dynamic')
 703     self._kinds = new_lst
 704     self.validate_tree()
 705
 706   def _get_children(self):
 707     return (i for i in self.kinds)
 708
 709   @property
 710   def merged_kinds(self):
 711
 712     def aggregate_by_name(acc, el):
 713       existing = [i for i in acc if i.name == el.name]
 714       if existing:
 715         k = existing[0]
 716       else:
 717         k = Kind(el.name, el.parent)
 718         acc.append(k)
 719
 720       k._namespaces.extend(el._namespaces)
 721       k._entries.extend(el._entries)
 722
 723       return acc
 724
 725     new_kinds_lst = reduce(aggregate_by_name, self.kinds, [])
 726
 727     for k in new_kinds_lst:
 728       yield k
 729
 730   def combine_kinds_into_single_node(self):
 731     r"""
 732     Combines the section's Kinds into a single node.
 733
 734     Combines all the children (kinds) of this section into a single
 735     virtual Kind node.
 736
 737     Returns:
 738       A new Kind node that collapses all Kind siblings into one, combining
 739       all their children together.
 740
 741       For example, given self.kinds == [ x, y ]
 742
 743         x  y               z
 744       / |  | \    -->   / | | \
 745       a b  c d          a b c d
 746
 747       a new instance z is returned in this example.
 748
 749     Remarks:
 750       The children of the kinds are the same references as before, that is
 751       their parents will point to the old parents and not to the new parent.
 752     """
 753     combined = Kind(name="combined", parent=self)
 754
 755     for k in self._get_children():
 756       combined._namespaces.extend(k.namespaces)
 757       combined._entries.extend(k.entries)
 758
 759     return combined
 760
 761 class Kind(Node):
 762   """
 763   A node corresponding to one of: <static>,<dynamic>,<controls> under a
 764   <section> element.
 765
 766   Attributes (Read-Only):
 767     name: A string which is one of 'static', 'dynamic, or 'controls'.
 768     parent: An edge to the parent, which is always a Section  instance.
 769     namespaces: A sequence of InnerNamespace children.
 770     entries: A sequence of Entry/Clone children.
 771     merged_entries: A sequence of MergedEntry virtual nodes from entries
 772   """
 773   def __init__(self, name, parent):
 774     self._name = name
 775     self._parent = parent
 776     self._namespaces = []
 777     self._entries = []
 778
 779     self._leafs = []
 780
 781   @property
 782   def namespaces(self):
 783     return self._namespaces
 784
 785   @property
 786   def entries(self):
 787     return self._entries
 788
 789   @property
 790   def merged_entries(self):
 791     for i in self.entries:
 792       yield i.merge()
 793
 794   def sort_children(self):
 795     self._namespaces.sort(key=self._get_name())
 796     self._entries.sort(key=self._get_name())
 797
 798   def _get_children(self):
 799     for i in self.namespaces:
 800       yield i
 801     for i in self.entries:
 802       yield i
 803
 804   def combine_children_by_name(self):
 805     r"""
 806     Combine multiple children with the same name into a single node.
 807
 808     Returns:
 809       A new Kind where all of the children with the same name were combined.
 810
 811       For example:
 812
 813       Given a Kind k:
 814
 815               k
 816             / | \
 817             a b c
 818             | | |
 819             d e f
 820
 821       a.name == "foo"
 822       b.name == "foo"
 823       c.name == "bar"
 824
 825       The returned Kind will look like this:
 826
 827              k'
 828             /  \
 829             a' c'
 830           / |  |
 831           d e  f
 832
 833     Remarks:
 834       This operation is not recursive. To combine the grandchildren and other
 835       ancestors, call this method on the ancestor nodes.
 836     """
 837     return Kind._combine_children_by_name(self, new_type=type(self))
 838
 839   # new_type is either Kind or InnerNamespace
 840   @staticmethod
 841   def _combine_children_by_name(self, new_type):
 842     new_ins_dict = OrderedDict()
 843     new_ent_dict = OrderedDict()
 844
 845     for ins in self.namespaces:
 846       new_ins = new_ins_dict.setdefault(ins.name,
 847                                         InnerNamespace(ins.name, parent=self))
 848       new_ins._namespaces.extend(ins.namespaces)
 849       new_ins._entries.extend(ins.entries)
 850
 851     for ent in self.entries:
 852       new_ent = new_ent_dict.setdefault(ent.name,
 853                                         ent.merge())
 854
 855     kind = new_type(self.name, self.parent)
 856     kind._namespaces = new_ins_dict.values()
 857     kind._entries = new_ent_dict.values()
 858
 859     return kind
 860
 861 class InnerNamespace(Node):
 862   """
 863   A node corresponding to a <namespace> which is an ancestor of a Kind.
 864   These namespaces may have other namespaces recursively, or entries as leafs.
 865
 866   Attributes (Read-Only):
 867     name: Name attribute from the element, e.g. <namespace name="foo"> -> 'foo'
 868     parent: An edge to the parent, which is an InnerNamespace or a Kind.
 869     namespaces: A sequence of InnerNamespace children.
 870     entries: A sequence of Entry/Clone children.
 871     merged_entries: A sequence of MergedEntry virtual nodes from entries
 872   """
 873   def __init__(self, name, parent):
 874     self._name        = name
 875     self._parent      = parent
 876     self._namespaces  = []
 877     self._entries     = []
 878     self._leafs       = []
 879
 880   @property
 881   def namespaces(self):
 882     return self._namespaces
 883
 884   @property
 885   def entries(self):
 886     return self._entries
 887
 888   @property
 889   def merged_entries(self):
 890     for i in self.entries:
 891       yield i.merge()
 892
 893   def sort_children(self):
 894     self._namespaces.sort(key=self._get_name())
 895     self._entries.sort(key=self._get_name())
 896
 897   def _get_children(self):
 898     for i in self.namespaces:
 899       yield i
 900     for i in self.entries:
 901       yield i
 902
 903   def combine_children_by_name(self):
 904     r"""
 905     Combine multiple children with the same name into a single node.
 906
 907     Returns:
 908       A new InnerNamespace where all of the children with the same name were
 909       combined.
 910
 911       For example:
 912
 913       Given an InnerNamespace i:
 914
 915               i
 916             / | \
 917             a b c
 918             | | |
 919             d e f
 920
 921       a.name == "foo"
 922       b.name == "foo"
 923       c.name == "bar"
 924
 925       The returned InnerNamespace will look like this:
 926
 927              i'
 928             /  \
 929             a' c'
 930           / |  |
 931           d e  f
 932
 933     Remarks:
 934       This operation is not recursive. To combine the grandchildren and other
 935       ancestors, call this method on the ancestor nodes.
 936     """
 937     return Kind._combine_children_by_name(self, new_type=type(self))
 938
 939 class EnumValue(Node):
 940   """
 941   A class corresponding to a <value> element within an <enum> within an <entry>.
 942
 943   Attributes (Read-Only):
 944     name: A string,                 e.g. 'ON' or 'OFF'
 945     id: An optional numeric string, e.g. '0' or '0xFF'
 946     optional: A boolean
 947     notes: A string describing the notes, or None.
 948     parent: An edge to the parent, always an Enum instance.
 949   """
 950   def __init__(self, name, parent, id=None, optional=False, notes=None):
 951     self._name = name                    # str, e.g. 'ON' or 'OFF'
 952     self._id = id                        # int, e.g. '0'
 953     self._optional = optional            # bool
 954     self._notes = notes                  # None or str
 955     self._parent = parent
 956
 957   @property
 958   def id(self):
 959     return self._id
 960
 961   @property
 962   def optional(self):
 963     return self._optional
 964
 965   @property
 966   def notes(self):
 967     return self._notes
 968
 969   def _get_children(self):
 970     return None
 971
 972 class Enum(Node):
 973   """
 974   A class corresponding to an <enum> element within an <entry>.
 975
 976   Attributes (Read-Only):
 977     parent: An edge to the parent, always an Entry instance.
 978     values: A sequence of EnumValue children.
 979     has_values_with_id: A boolean representing if any of the children have a
 980         non-empty id property.
 981   """
 982   def __init__(self, parent, values, ids={}, optionals=[], notes={}):
 983     self._values =                                                             \
 984       [ EnumValue(val, self, ids.get(val), val in optionals, notes.get(val))   \
 985         for val in values ]
 986
 987     self._parent = parent
 988     self._name = None
 989
 990   @property
 991   def values(self):
 992     return (i for i in self._values)
 993
 994   @property
 995   def has_values_with_id(self):
 996     return bool(any(i for i in self.values if i.id))
 997
 998   def _get_children(self):
 999     return (i for i in self._values)
1000
1001 class Entry(Node):
1002   """
1003   A node corresponding to an <entry> element.
1004
1005   Attributes (Read-Only):
1006     parent: An edge to the parent node, which is an InnerNamespace or Kind.
1007     name: The fully qualified name string, e.g. 'android.shading.mode'
1008     name_short: The name attribute from <entry name="mode">, e.g. mode
1009     type: The type attribute from <entry type="bar">
1010     kind: A string ('static', 'dynamic', 'controls') corresponding to the
1011           ancestor Kind#name
1012     container: The container attribute from <entry container="array">, or None.
1013     container_sizes: A sequence of size strings or None if container is None.
1014     enum: An Enum instance if the enum attribute is true, None otherwise.
1015     visibility: The visibility of this entry ('system', 'hidden', 'public')
1016                 across the system. System entries are only visible in native code
1017                 headers. Hidden entries are marked @hide in managed code, while
1018                 public entries are visible in the Android SDK.
1019     applied_visibility: As visibility, but always valid, defaulting to 'system'
1020                         if no visibility is given for an entry.
1021     optional: a bool representing the optional attribute, which denotes the entry
1022               is required for hardware level full devices, but optional for other
1023               hardware levels.  None if not present.
1024     applied_optional: As optional but always valid, defaulting to False if no
1025                       optional attribute is present.
1026     tuple_values: A sequence of strings describing the tuple values,
1027                   None if container is not 'tuple'.
1028     description: A string description, or None.
1029     range: A string range, or None.
1030     units: A string units, or None.
1031     tags: A sequence of Tag nodes associated with this Entry.
1032     type_notes: A string describing notes for the type, or None.
1033     typedef: A Typedef associated with this Entry, or None.
1034
1035   Remarks:
1036     Subclass Clone can be used interchangeable with an Entry,
1037     for when we don't care about the underlying type.
1038
1039     parent and tags edges are invalid until after Metadata#construct_graph
1040     has been invoked.
1041   """
1042   def __init__(self, **kwargs):
1043     """
1044     Instantiate a new Entry node.
1045
1046     Args:
1047       name: A string with the fully qualified name, e.g. 'android.shading.mode'
1048       type: A string describing the type, e.g. 'int32'
1049       kind: A string describing the kind, e.g. 'static'
1050
1051     Args (if container):
1052       container: A string describing the container, e.g. 'array' or 'tuple'
1053       container_sizes: A list of string sizes if a container, or None otherwise
1054
1055     Args (if container is 'tuple'):
1056       tuple_values: A list of tuple values, e.g. ['width', 'height']
1057
1058     Args (if the 'enum' attribute is true):
1059       enum: A boolean, True if this is an enum, False otherwise
1060       enum_values: A list of value strings, e.g. ['ON', 'OFF']
1061       enum_optionals: A list of optional enum values, e.g. ['OFF']
1062       enum_notes: A dictionary of value->notes strings.
1063       enum_ids: A dictionary of value->id strings.
1064
1065     Args (optional):
1066       description: A string with a description of the entry.
1067       range: A string with the range of the values of the entry, e.g. '>= 0'
1068       units: A string with the units of the values, e.g. 'inches'
1069       details: A string with the detailed documentation for the entry
1070       hal_details: A string with the HAL implementation details for the entry
1071       tag_ids: A list of tag ID strings, e.g. ['BC', 'V1']
1072       type_notes: A string with the notes for the type
1073       visibility: A string describing the visibility, eg 'system', 'hidden',
1074                   'public'
1075       optional: A bool to mark whether optional for non-full hardware devices
1076       typedef: A string corresponding to a typedef's name attribute.
1077     """
1078
1079     if kwargs.get('type') is None:
1080       print >> sys.stderr, "ERROR: Missing type for entry '%s' kind  '%s'"     \
1081       %(kwargs.get('name'), kwargs.get('kind'))
1082
1083     # Attributes are Read-Only, but edges may be mutated by
1084     # Metadata, particularly during construct_graph
1085
1086     self._name = kwargs['name']
1087     self._type = kwargs['type']
1088     self._kind = kwargs['kind'] # static, dynamic, or controls
1089
1090     self._init_common(**kwargs)
1091
1092   @property
1093   def type(self):
1094     return self._type
1095
1096   @property
1097   def kind(self):
1098     return self._kind
1099
1100   @property
1101   def visibility(self):
1102     return self._visibility
1103
1104   @property
1105   def applied_visibility(self):
1106     return self._visibility or 'system'
1107
1108   @property
1109   def optional(self):
1110     return self._optional
1111
1112   @property
1113   def applied_optional(self):
1114     return self._optional or False
1115
1116   @property
1117   def name_short(self):
1118     return self.get_name_minimal()
1119
1120   @property
1121   def container(self):
1122     return self._container
1123
1124   @property
1125   def container_sizes(self):
1126     if self._container_sizes is None:
1127       return None
1128     else:
1129       return (i for i in self._container_sizes)
1130
1131   @property
1132   def tuple_values(self):
1133     if self._tuple_values is None:
1134       return None
1135     else:
1136       return (i for i in self._tuple_values)
1137
1138   @property
1139   def description(self):
1140     return self._description
1141
1142   @property
1143   def range(self):
1144     return self._range
1145
1146   @property
1147   def units(self):
1148     return self._units
1149
1150   @property
1151   def details(self):
1152     return self._details
1153
1154   @property
1155   def hal_details(self):
1156     return self._hal_details
1157
1158   @property
1159   def tags(self):
1160     if self._tags is None:
1161       return None
1162     else:
1163       return (i for i in self._tags)
1164
1165   @property
1166   def type_notes(self):
1167     return self._type_notes
1168
1169   @property
1170   def typedef(self):
1171     return self._typedef
1172
1173   @property
1174   def enum(self):
1175     return self._enum
1176
1177   def _get_children(self):
1178     if self.enum:
1179       yield self.enum
1180
1181   def sort_children(self):
1182     return None
1183
1184   def is_clone(self):
1185     """
1186     Whether or not this is a Clone instance.
1187
1188     Returns:
1189       False
1190     """
1191     return False
1192
1193   def _init_common(self, **kwargs):
1194
1195     self._parent = None # filled in by Metadata::_construct_entries
1196
1197     self._container = kwargs.get('container')
1198     self._container_sizes = kwargs.get('container_sizes')
1199
1200     # access these via the 'enum' prop
1201     enum_values = kwargs.get('enum_values')
1202     enum_optionals = kwargs.get('enum_optionals')
1203     enum_notes = kwargs.get('enum_notes')  # { value => notes }
1204     enum_ids = kwargs.get('enum_ids')  # { value => notes }
1205     self._tuple_values = kwargs.get('tuple_values')
1206
1207     self._description = kwargs.get('description')
1208     self._range = kwargs.get('range')
1209     self._units = kwargs.get('units')
1210     self._details = kwargs.get('details')
1211     self._hal_details = kwargs.get('hal_details')
1212
1213     self._tag_ids = kwargs.get('tag_ids', [])
1214     self._tags = None  # Filled in by Metadata::_construct_tags
1215
1216     self._type_notes = kwargs.get('type_notes')
1217     self._type_name = kwargs.get('type_name')
1218     self._typedef = None # Filled in by Metadata::_construct_types
1219
1220     if kwargs.get('enum', False):
1221       self._enum = Enum(self, enum_values, enum_ids, enum_optionals, enum_notes)
1222     else:
1223       self._enum = None
1224
1225     self._visibility = kwargs.get('visibility')
1226     self._optional = kwargs.get('optional')
1227
1228     self._property_keys = kwargs
1229
1230   def merge(self):
1231     """
1232     Copy the attributes into a new entry, merging it with the target entry
1233     if it's a clone.
1234     """
1235     return MergedEntry(self)
1236
1237   # Helpers for accessing less than the fully qualified name
1238
1239   def get_name_as_list(self):
1240     """
1241     Returns the name as a list split by a period.
1242
1243     For example:
1244       entry.name is 'android.lens.info.shading'
1245       entry.get_name_as_list() == ['android', 'lens', 'info', 'shading']
1246     """
1247     return self.name.split(".")
1248
1249   def get_inner_namespace_list(self):
1250     """
1251     Returns the inner namespace part of the name as a list
1252
1253     For example:
1254       entry.name is 'android.lens.info.shading'
1255       entry.get_inner_namespace_list() == ['info']
1256     """
1257     return self.get_name_as_list()[2:-1]
1258
1259   def get_outer_namespace(self):
1260     """
1261     Returns the outer namespace as a string.
1262
1263     For example:
1264       entry.name is 'android.lens.info.shading'
1265       entry.get_outer_namespace() == 'android'
1266
1267     Remarks:
1268       Since outer namespaces are non-recursive,
1269       and each entry has one, this does not need to be a list.
1270     """
1271     return self.get_name_as_list()[0]
1272
1273   def get_section(self):
1274     """
1275     Returns the section as a string.
1276
1277     For example:
1278       entry.name is 'android.lens.info.shading'
1279       entry.get_section() == ''
1280
1281     Remarks:
1282       Since outer namespaces are non-recursive,
1283       and each entry has one, this does not need to be a list.
1284     """
1285     return self.get_name_as_list()[1]
1286
1287   def get_name_minimal(self):
1288     """
1289     Returns only the last component of the fully qualified name as a string.
1290
1291     For example:
1292       entry.name is 'android.lens.info.shading'
1293       entry.get_name_minimal() == 'shading'
1294
1295     Remarks:
1296       entry.name_short it an alias for this
1297     """
1298     return self.get_name_as_list()[-1]
1299
1300   def get_path_without_name(self):
1301     """
1302     Returns a string path to the entry, with the name component excluded.
1303
1304     For example:
1305       entry.name is 'android.lens.info.shading'
1306       entry.get_path_without_name() == 'android.lens.info'
1307     """
1308     return ".".join(self.get_name_as_list()[0:-1])
1309
1310
1311 class Clone(Entry):
1312   """
1313   A Node corresponding to a <clone> element. It has all the attributes of an
1314   <entry> element (Entry) plus the additions specified below.
1315
1316   Attributes (Read-Only):
1317     entry: an edge to an Entry object that this targets
1318     target_kind: A string describing the kind of the target entry.
1319     name: a string of the name, same as entry.name
1320     kind: a string of the Kind ancestor, one of 'static', 'controls', 'dynamic'
1321           for the <clone> element.
1322     type: always None, since a clone cannot override the type.
1323   """
1324   def __init__(self, entry=None, **kwargs):
1325     """
1326     Instantiate a new Clone node.
1327
1328     Args:
1329       name: A string with the fully qualified name, e.g. 'android.shading.mode'
1330       type: A string describing the type, e.g. 'int32'
1331       kind: A string describing the kind, e.g. 'static'
1332       target_kind: A string for the kind of the target entry, e.g. 'dynamic'
1333
1334     Args (if container):
1335       container: A string describing the container, e.g. 'array' or 'tuple'
1336       container_sizes: A list of string sizes if a container, or None otherwise
1337
1338     Args (if container is 'tuple'):
1339       tuple_values: A list of tuple values, e.g. ['width', 'height']
1340
1341     Args (if the 'enum' attribute is true):
1342       enum: A boolean, True if this is an enum, False otherwise
1343       enum_values: A list of value strings, e.g. ['ON', 'OFF']
1344       enum_optionals: A list of optional enum values, e.g. ['OFF']
1345       enum_notes: A dictionary of value->notes strings.
1346       enum_ids: A dictionary of value->id strings.
1347
1348     Args (optional):
1349       entry: An edge to the corresponding target Entry.
1350       description: A string with a description of the entry.
1351       range: A string with the range of the values of the entry, e.g. '>= 0'
1352       units: A string with the units of the values, e.g. 'inches'
1353       details: A string with the detailed documentation for the entry
1354       hal_details: A string with the HAL implementation details for the entry
1355       tag_ids: A list of tag ID strings, e.g. ['BC', 'V1']
1356       type_notes: A string with the notes for the type
1357
1358     Remarks:
1359       Note that type is not specified since it has to be the same as the
1360       entry.type.
1361     """
1362     self._entry = entry  # Entry object
1363     self._target_kind = kwargs['target_kind']
1364     self._name = kwargs['name']  # same as entry.name
1365     self._kind = kwargs['kind']
1366
1367     # illegal to override the type, it should be the same as the entry
1368     self._type = None
1369     # the rest of the kwargs are optional
1370     # can be used to override the regular entry data
1371     self._init_common(**kwargs)
1372
1373   @property
1374   def entry(self):
1375     return self._entry
1376
1377   @property
1378   def target_kind(self):
1379     return self._target_kind
1380
1381   def is_clone(self):
1382     """
1383     Whether or not this is a Clone instance.
1384
1385     Returns:
1386       True
1387     """
1388     return True
1389
1390 class MergedEntry(Entry):
1391   """
1392   A MergedEntry has all the attributes of a Clone and its target Entry merged
1393   together.
1394
1395   Remarks:
1396     Useful when we want to 'unfold' a clone into a real entry by copying out
1397     the target entry data. In this case we don't care about distinguishing
1398     a clone vs an entry.
1399   """
1400   def __init__(self, entry):
1401     """
1402     Create a new instance of MergedEntry.
1403
1404     Args:
1405       entry: An Entry or Clone instance
1406     """
1407     props_distinct = ['description', 'units', 'range', 'details',
1408                       'hal_details', 'tags', 'kind']
1409
1410     for p in props_distinct:
1411       p = '_' + p
1412       if entry.is_clone():
1413         setattr(self, p, getattr(entry, p) or getattr(entry.entry, p))
1414       else:
1415         setattr(self, p, getattr(entry, p))
1416
1417     props_common = ['parent', 'name', 'container',
1418                     'container_sizes', 'enum',
1419                     'tuple_values',
1420                     'type',
1421                     'type_notes',
1422                     'visibility',
1423                     'optional',
1424                     'typedef'
1425                    ]
1426
1427     for p in props_common:
1428       p = '_' + p
1429       if entry.is_clone():
1430         setattr(self, p, getattr(entry.entry, p))
1431       else:
1432         setattr(self, p, getattr(entry, p))