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     deprecated: A boolean, True if the enum should be deprecated.
 947     optional: A boolean
 948     hidden: A boolean, True if the enum should be hidden.
 949     ndk_hidden: A boolean, True if the enum should be hidden in NDK
 950     notes: A string describing the notes, or None.
 951     parent: An edge to the parent, always an Enum instance.
 952   """
 953   def __init__(self, name, parent,
 954       id=None, deprecated=False, optional=False, hidden=False, notes=None, ndk_hidden=False):
 955     self._name = name                    # str, e.g. 'ON' or 'OFF'
 956     self._id = id                        # int, e.g. '0'
 957     self._deprecated = deprecated        # bool
 958     self._optional = optional            # bool
 959     self._hidden = hidden                # bool
 960     self._ndk_hidden = ndk_hidden        # bool
 961     self._notes = notes                  # None or str
 962     self._parent = parent
 963
 964   @property
 965   def id(self):
 966     return self._id
 967
 968   @property
 969   def deprecated(self):
 970     return self._deprecated
 971
 972   @property
 973   def optional(self):
 974     return self._optional
 975
 976   @property
 977   def hidden(self):
 978     return self._hidden
 979
 980   @property
 981   def ndk_hidden(self):
 982     return self._ndk_hidden
 983
 984   @property
 985   def notes(self):
 986     return self._notes
 987
 988   def _get_children(self):
 989     return None
 990
 991 class Enum(Node):
 992   """
 993   A class corresponding to an <enum> element within an <entry>.
 994
 995   Attributes (Read-Only):
 996     parent: An edge to the parent, always an Entry instance.
 997     values: A sequence of EnumValue children.
 998     has_values_with_id: A boolean representing if any of the children have a
 999         non-empty id property.
1000   """
1001   def __init__(self, parent, values, ids={}, deprecateds=[],
1002       optionals=[], hiddens=[], notes={}, ndk_hiddens=[]):
1003     self._values =                                                             \
1004       [ EnumValue(val, self, ids.get(val), val in deprecateds, val in optionals, val in hiddens,  \
1005                   notes.get(val), val in ndk_hiddens)                                              \
1006         for val in values ]
1007
1008     self._parent = parent
1009     self._name = None
1010
1011   @property
1012   def values(self):
1013     return (i for i in self._values)
1014
1015   @property
1016   def has_values_with_id(self):
1017     return bool(any(i for i in self.values if i.id))
1018
1019   def _get_children(self):
1020     return (i for i in self._values)
1021
1022 class Entry(Node):
1023   """
1024   A node corresponding to an <entry> element.
1025
1026   Attributes (Read-Only):
1027     parent: An edge to the parent node, which is an InnerNamespace or Kind.
1028     name: The fully qualified name string, e.g. 'android.shading.mode'
1029     name_short: The name attribute from <entry name="mode">, e.g. mode
1030     type: The type attribute from <entry type="bar">
1031     kind: A string ('static', 'dynamic', 'controls') corresponding to the
1032           ancestor Kind#name
1033     container: The container attribute from <entry container="array">, or None.
1034     container_sizes: A sequence of size strings or None if container is None.
1035     enum: An Enum instance if the enum attribute is true, None otherwise.
1036     visibility: The visibility of this entry ('system', 'hidden', 'public')
1037                 across the system. System entries are only visible in native code
1038                 headers. Hidden entries are marked @hide in managed code, while
1039                 public entries are visible in the Android SDK.
1040     applied_visibility: As visibility, but always valid, defaulting to 'system'
1041                         if no visibility is given for an entry.
1042     applied_ndk_visible: Always valid. Default is 'false'.
1043                          Set to 'true' when the visibility implied entry is visible
1044                          in NDK.
1045     synthetic: The C-level visibility of this entry ('false', 'true').
1046                Synthetic entries will not be generated into the native metadata
1047                list of entries (in C code). In general a synthetic entry is
1048                glued together at the Java layer from multiple visibiltity=hidden
1049                entries.
1050     hwlevel: The lowest hardware level at which the entry is guaranteed
1051              to be supported by the camera device. All devices with higher
1052              hwlevels will also include this entry. None means that the
1053              entry is optional on any hardware level.
1054     deprecated: Marks an entry as @Deprecated in the Java layer; if within an
1055                unreleased version this needs to be removed altogether. If applied
1056                to an entry from an older release, then this means the entry
1057                should be ignored by newer code.
1058     optional: a bool representing the optional attribute, which denotes the entry
1059               is required for hardware level full devices, but optional for other
1060               hardware levels.  None if not present.
1061     applied_optional: As optional but always valid, defaulting to False if no
1062                       optional attribute is present.
1063     tuple_values: A sequence of strings describing the tuple values,
1064                   None if container is not 'tuple'.
1065     description: A string description, or None.
1066     range: A string range, or None.
1067     units: A string units, or None.
1068     tags: A sequence of Tag nodes associated with this Entry.
1069     type_notes: A string describing notes for the type, or None.
1070     typedef: A Typedef associated with this Entry, or None.
1071
1072   Remarks:
1073     Subclass Clone can be used interchangeable with an Entry,
1074     for when we don't care about the underlying type.
1075
1076     parent and tags edges are invalid until after Metadata#construct_graph
1077     has been invoked.
1078   """
1079   def __init__(self, **kwargs):
1080     """
1081     Instantiate a new Entry node.
1082
1083     Args:
1084       name: A string with the fully qualified name, e.g. 'android.shading.mode'
1085       type: A string describing the type, e.g. 'int32'
1086       kind: A string describing the kind, e.g. 'static'
1087
1088     Args (if container):
1089       container: A string describing the container, e.g. 'array' or 'tuple'
1090       container_sizes: A list of string sizes if a container, or None otherwise
1091
1092     Args (if container is 'tuple'):
1093       tuple_values: A list of tuple values, e.g. ['width', 'height']
1094
1095     Args (if the 'enum' attribute is true):
1096       enum: A boolean, True if this is an enum, False otherwise
1097       enum_values: A list of value strings, e.g. ['ON', 'OFF']
1098       enum_optionals: A list of optional enum values, e.g. ['OFF']
1099       enum_notes: A dictionary of value->notes strings.
1100       enum_ids: A dictionary of value->id strings.
1101
1102     Args (optional):
1103       description: A string with a description of the entry.
1104       range: A string with the range of the values of the entry, e.g. '>= 0'
1105       units: A string with the units of the values, e.g. 'inches'
1106       details: A string with the detailed documentation for the entry
1107       hal_details: A string with the HAL implementation details for the entry
1108       tag_ids: A list of tag ID strings, e.g. ['BC', 'V1']
1109       type_notes: A string with the notes for the type
1110       visibility: A string describing the visibility, eg 'system', 'hidden',
1111                   'public'
1112       synthetic: A bool to mark whether this entry is visible only at the Java
1113                  layer (True), or at both layers (False = default).
1114       hwlevel: A string of the HW level (one of 'legacy', 'limited', 'full')
1115       deprecated: A bool to mark whether this is @Deprecated at the Java layer
1116                  (default = False).
1117       optional: A bool to mark whether optional for non-full hardware devices
1118       typedef: A string corresponding to a typedef's name attribute.
1119     """
1120
1121     if kwargs.get('type') is None:
1122       print >> sys.stderr, "ERROR: Missing type for entry '%s' kind  '%s'"     \
1123       %(kwargs.get('name'), kwargs.get('kind'))
1124
1125     # Attributes are Read-Only, but edges may be mutated by
1126     # Metadata, particularly during construct_graph
1127
1128     self._name = kwargs['name']
1129     self._type = kwargs['type']
1130     self._kind = kwargs['kind'] # static, dynamic, or controls
1131
1132     self._init_common(**kwargs)
1133
1134   @property
1135   def type(self):
1136     return self._type
1137
1138   @property
1139   def kind(self):
1140     return self._kind
1141
1142   @property
1143   def visibility(self):
1144     return self._visibility
1145
1146   @property
1147   def applied_visibility(self):
1148     return self._visibility or 'system'
1149
1150   @property
1151   def applied_ndk_visible(self):
1152     if self._visibility in ("public", "ndk_public"):
1153       return "true"
1154     return "false"
1155
1156   @property
1157   def synthetic(self):
1158     return self._synthetic
1159
1160   @property
1161   def hwlevel(self):
1162     return self._hwlevel
1163
1164   @property
1165   def deprecated(self):
1166     return self._deprecated
1167
1168   # TODO: optional should just return hwlevel is None
1169   @property
1170   def optional(self):
1171     return self._optional
1172
1173   @property
1174   def applied_optional(self):
1175     return self._optional or False
1176
1177   @property
1178   def name_short(self):
1179     return self.get_name_minimal()
1180
1181   @property
1182   def container(self):
1183     return self._container
1184
1185   @property
1186   def container_sizes(self):
1187     if self._container_sizes is None:
1188       return None
1189     else:
1190       return (i for i in self._container_sizes)
1191
1192   @property
1193   def tuple_values(self):
1194     if self._tuple_values is None:
1195       return None
1196     else:
1197       return (i for i in self._tuple_values)
1198
1199   @property
1200   def description(self):
1201     return self._description
1202
1203   @property
1204   def range(self):
1205     return self._range
1206
1207   @property
1208   def units(self):
1209     return self._units
1210
1211   @property
1212   def details(self):
1213     return self._details
1214
1215   @property
1216   def hal_details(self):
1217     return self._hal_details
1218
1219   @property
1220   def tags(self):
1221     if self._tags is None:
1222       return None
1223     else:
1224       return (i for i in self._tags)
1225
1226   @property
1227   def type_notes(self):
1228     return self._type_notes
1229
1230   @property
1231   def typedef(self):
1232     return self._typedef
1233
1234   @property
1235   def enum(self):
1236     return self._enum
1237
1238   def _get_children(self):
1239     if self.enum:
1240       yield self.enum
1241
1242   def sort_children(self):
1243     return None
1244
1245   def is_clone(self):
1246     """
1247     Whether or not this is a Clone instance.
1248
1249     Returns:
1250       False
1251     """
1252     return False
1253
1254   def _init_common(self, **kwargs):
1255
1256     self._parent = None # filled in by Metadata::_construct_entries
1257
1258     self._container = kwargs.get('container')
1259     self._container_sizes = kwargs.get('container_sizes')
1260
1261     # access these via the 'enum' prop
1262     enum_values = kwargs.get('enum_values')
1263     enum_deprecateds = kwargs.get('enum_deprecateds')
1264     enum_optionals = kwargs.get('enum_optionals')
1265     enum_hiddens = kwargs.get('enum_hiddens')
1266     enum_ndk_hiddens = kwargs.get('enum_ndk_hiddens')
1267     enum_notes = kwargs.get('enum_notes')  # { value => notes }
1268     enum_ids = kwargs.get('enum_ids')  # { value => notes }
1269     self._tuple_values = kwargs.get('tuple_values')
1270
1271     self._description = kwargs.get('description')
1272     self._range = kwargs.get('range')
1273     self._units = kwargs.get('units')
1274     self._details = kwargs.get('details')
1275     self._hal_details = kwargs.get('hal_details')
1276
1277     self._tag_ids = kwargs.get('tag_ids', [])
1278     self._tags = None  # Filled in by Metadata::_construct_tags
1279
1280     self._type_notes = kwargs.get('type_notes')
1281     self._type_name = kwargs.get('type_name')
1282     self._typedef = None # Filled in by Metadata::_construct_types
1283
1284     if kwargs.get('enum', False):
1285       self._enum = Enum(self, enum_values, enum_ids, enum_deprecateds, enum_optionals,
1286                         enum_hiddens, enum_notes, enum_ndk_hiddens)
1287     else:
1288       self._enum = None
1289
1290     self._visibility = kwargs.get('visibility')
1291     self._synthetic = kwargs.get('synthetic', False)
1292     self._hwlevel = kwargs.get('hwlevel')
1293     self._deprecated = kwargs.get('deprecated', False)
1294     self._optional = kwargs.get('optional')
1295     self._ndk_visible = kwargs.get('ndk_visible')
1296
1297     self._property_keys = kwargs
1298
1299   def merge(self):
1300     """
1301     Copy the attributes into a new entry, merging it with the target entry
1302     if it's a clone.
1303     """
1304     return MergedEntry(self)
1305
1306   # Helpers for accessing less than the fully qualified name
1307
1308   def get_name_as_list(self):
1309     """
1310     Returns the name as a list split by a period.
1311
1312     For example:
1313       entry.name is 'android.lens.info.shading'
1314       entry.get_name_as_list() == ['android', 'lens', 'info', 'shading']
1315     """
1316     return self.name.split(".")
1317
1318   def get_inner_namespace_list(self):
1319     """
1320     Returns the inner namespace part of the name as a list
1321
1322     For example:
1323       entry.name is 'android.lens.info.shading'
1324       entry.get_inner_namespace_list() == ['info']
1325     """
1326     return self.get_name_as_list()[2:-1]
1327
1328   def get_outer_namespace(self):
1329     """
1330     Returns the outer namespace as a string.
1331
1332     For example:
1333       entry.name is 'android.lens.info.shading'
1334       entry.get_outer_namespace() == 'android'
1335
1336     Remarks:
1337       Since outer namespaces are non-recursive,
1338       and each entry has one, this does not need to be a list.
1339     """
1340     return self.get_name_as_list()[0]
1341
1342   def get_section(self):
1343     """
1344     Returns the section as a string.
1345
1346     For example:
1347       entry.name is 'android.lens.info.shading'
1348       entry.get_section() == ''
1349
1350     Remarks:
1351       Since outer namespaces are non-recursive,
1352       and each entry has one, this does not need to be a list.
1353     """
1354     return self.get_name_as_list()[1]
1355
1356   def get_name_minimal(self):
1357     """
1358     Returns only the last component of the fully qualified name as a string.
1359
1360     For example:
1361       entry.name is 'android.lens.info.shading'
1362       entry.get_name_minimal() == 'shading'
1363
1364     Remarks:
1365       entry.name_short it an alias for this
1366     """
1367     return self.get_name_as_list()[-1]
1368
1369   def get_path_without_name(self):
1370     """
1371     Returns a string path to the entry, with the name component excluded.
1372
1373     For example:
1374       entry.name is 'android.lens.info.shading'
1375       entry.get_path_without_name() == 'android.lens.info'
1376     """
1377     return ".".join(self.get_name_as_list()[0:-1])
1378
1379
1380 class Clone(Entry):
1381   """
1382   A Node corresponding to a <clone> element. It has all the attributes of an
1383   <entry> element (Entry) plus the additions specified below.
1384
1385   Attributes (Read-Only):
1386     entry: an edge to an Entry object that this targets
1387     target_kind: A string describing the kind of the target entry.
1388     name: a string of the name, same as entry.name
1389     kind: a string of the Kind ancestor, one of 'static', 'controls', 'dynamic'
1390           for the <clone> element.
1391     type: always None, since a clone cannot override the type.
1392   """
1393   def __init__(self, entry=None, **kwargs):
1394     """
1395     Instantiate a new Clone node.
1396
1397     Args:
1398       name: A string with the fully qualified name, e.g. 'android.shading.mode'
1399       type: A string describing the type, e.g. 'int32'
1400       kind: A string describing the kind, e.g. 'static'
1401       target_kind: A string for the kind of the target entry, e.g. 'dynamic'
1402
1403     Args (if container):
1404       container: A string describing the container, e.g. 'array' or 'tuple'
1405       container_sizes: A list of string sizes if a container, or None otherwise
1406
1407     Args (if container is 'tuple'):
1408       tuple_values: A list of tuple values, e.g. ['width', 'height']
1409
1410     Args (if the 'enum' attribute is true):
1411       enum: A boolean, True if this is an enum, False otherwise
1412       enum_values: A list of value strings, e.g. ['ON', 'OFF']
1413       enum_optionals: A list of optional enum values, e.g. ['OFF']
1414       enum_notes: A dictionary of value->notes strings.
1415       enum_ids: A dictionary of value->id strings.
1416
1417     Args (optional):
1418       entry: An edge to the corresponding target Entry.
1419       description: A string with a description of the entry.
1420       range: A string with the range of the values of the entry, e.g. '>= 0'
1421       units: A string with the units of the values, e.g. 'inches'
1422       details: A string with the detailed documentation for the entry
1423       hal_details: A string with the HAL implementation details for the entry
1424       tag_ids: A list of tag ID strings, e.g. ['BC', 'V1']
1425       type_notes: A string with the notes for the type
1426
1427     Remarks:
1428       Note that type is not specified since it has to be the same as the
1429       entry.type.
1430     """
1431     self._entry = entry  # Entry object
1432     self._target_kind = kwargs['target_kind']
1433     self._name = kwargs['name']  # same as entry.name
1434     self._kind = kwargs['kind']
1435
1436     # illegal to override the type, it should be the same as the entry
1437     self._type = None
1438     # the rest of the kwargs are optional
1439     # can be used to override the regular entry data
1440     self._init_common(**kwargs)
1441
1442   @property
1443   def entry(self):
1444     return self._entry
1445
1446   @property
1447   def target_kind(self):
1448     return self._target_kind
1449
1450   def is_clone(self):
1451     """
1452     Whether or not this is a Clone instance.
1453
1454     Returns:
1455       True
1456     """
1457     return True
1458
1459 class MergedEntry(Entry):
1460   """
1461   A MergedEntry has all the attributes of a Clone and its target Entry merged
1462   together.
1463
1464   Remarks:
1465     Useful when we want to 'unfold' a clone into a real entry by copying out
1466     the target entry data. In this case we don't care about distinguishing
1467     a clone vs an entry.
1468   """
1469   def __init__(self, entry):
1470     """
1471     Create a new instance of MergedEntry.
1472
1473     Args:
1474       entry: An Entry or Clone instance
1475     """
1476     props_distinct = ['description', 'units', 'range', 'details',
1477                       'hal_details', 'tags', 'kind']
1478
1479     for p in props_distinct:
1480       p = '_' + p
1481       if entry.is_clone():
1482         setattr(self, p, getattr(entry, p) or getattr(entry.entry, p))
1483       else:
1484         setattr(self, p, getattr(entry, p))
1485
1486     props_common = ['parent', 'name', 'container',
1487                     'container_sizes', 'enum',
1488                     'tuple_values',
1489                     'type',
1490                     'type_notes',
1491                     'visibility',
1492                     'ndk_visible',
1493                     'synthetic',
1494                     'hwlevel',
1495                     'deprecated',
1496                     'optional',
1497                     'typedef'
1498                    ]
1499
1500     for p in props_common:
1501       p = '_' + p
1502       if entry.is_clone():
1503         setattr(self, p, getattr(entry.entry, p))
1504       else:
1505         setattr(self, p, getattr(entry, p))