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   def is_entry_this_kind(self, entry, kind):
 355     """
 356     Check if input entry if of input kind
 357
 358     Args:
 359       entry: an Entry object
 360       kind: a string. Possible values are "static", "dynamic", "controls"
 361
 362     Returns:
 363       A boolean indicating whether input entry is of input kind.
 364     """
 365     if kind not in ("static", "dynamic", "controls"):
 366       assert(False), "Unknown kind value " + kind
 367
 368     return entry.name in self._entry_map[kind]
 369
 370   # After all entries/clones are inserted,
 371   # invoke this to generate the parent/child node graph all these objects
 372   def construct_graph(self):
 373     """
 374     Generate the graph recursively, after which all Entry nodes will be
 375     accessible recursively by crawling through the outer_namespaces sequence.
 376
 377     Remarks:
 378       This is safe to be called multiple times at any time. It should be done at
 379       least once or there will be no graph.
 380     """
 381     self.validate_tree()
 382     self._construct_tags()
 383     self.validate_tree()
 384     self._construct_types()
 385     self.validate_tree()
 386     self._construct_clones()
 387     self.validate_tree()
 388     self._construct_outer_namespaces()
 389     self.validate_tree()
 390
 391   def _construct_tags(self):
 392     tag_dict = self._dictionary_by_name(self.tags)
 393     for p in self._get_properties():
 394       p._tags = []
 395       for tag_id in p._tag_ids:
 396         tag = tag_dict.get(tag_id)
 397
 398         if tag not in p._tags:
 399           p._tags.append(tag)
 400
 401         if p not in tag.entries:
 402           tag._entries.append(p)
 403
 404   def _construct_types(self):
 405     type_dict = self._dictionary_by_name(self.types)
 406     for p in self._get_properties():
 407       if p._type_name:
 408         type_node = type_dict.get(p._type_name)
 409         p._typedef = type_node
 410
 411         if p not in type_node.entries:
 412           type_node._entries.append(p)
 413
 414   def _construct_clones(self):
 415     for p in self._clones:
 416       target_kind = p.target_kind
 417       target_entry = self._entry_map[target_kind].get(p.name)
 418       p._entry = target_entry
 419
 420       # should not throw if we pass validation
 421       # but can happen when importing obsolete CSV entries
 422       if target_entry is None:
 423         print >> sys.stderr, ("WARNING: Clone entry '%s' target kind '%s'" +   \
 424                               " has no corresponding entry")                   \
 425                              %(p.name, p.target_kind)
 426
 427   def _construct_outer_namespaces(self):
 428
 429     if self._outer_namespaces is None: #the first time this runs
 430       self._outer_namespaces = []
 431
 432     root = self._dictionary_by_name(self._outer_namespaces)
 433     for ons_name, ons in root.iteritems():
 434       ons._leafs = []
 435
 436     for p in self._entries_ordered:
 437       ons_name = p.get_outer_namespace()
 438       ons = root.get(ons_name, OuterNamespace(ons_name, self))
 439       root[ons_name] = ons
 440
 441       if p not in ons._leafs:
 442         ons._leafs.append(p)
 443
 444     for ons_name, ons in root.iteritems():
 445
 446       ons.validate_tree()
 447
 448       self._construct_sections(ons)
 449
 450       if ons not in self._outer_namespaces:
 451         self._outer_namespaces.append(ons)
 452
 453       ons.validate_tree()
 454
 455   def _construct_sections(self, outer_namespace):
 456
 457     sections_dict = self._dictionary_by_name(outer_namespace.sections)
 458     for sec_name, sec in sections_dict.iteritems():
 459       sec._leafs = []
 460       sec.validate_tree()
 461
 462     for p in outer_namespace._leafs:
 463       does_exist = sections_dict.get(p.get_section())
 464
 465       sec = sections_dict.get(p.get_section(), \
 466           Section(p.get_section(), outer_namespace))
 467       sections_dict[p.get_section()] = sec
 468
 469       sec.validate_tree()
 470
 471       if p not in sec._leafs:
 472         sec._leafs.append(p)
 473
 474     for sec_name, sec in sections_dict.iteritems():
 475
 476       if not sec.validate_tree():
 477         print >> sys.stderr, ("ERROR: Failed to validate tree in " +           \
 478                              "construct_sections (start), with section = '%s'")\
 479                              %(sec)
 480
 481       self._construct_kinds(sec)
 482
 483       if sec not in outer_namespace.sections:
 484         outer_namespace._sections.append(sec)
 485
 486       if not sec.validate_tree():
 487         print >> sys.stderr, ("ERROR: Failed to validate tree in " +           \
 488                               "construct_sections (end), with section = '%s'") \
 489                              %(sec)
 490
 491   # 'controls', 'static' 'dynamic'. etc
 492   def _construct_kinds(self, section):
 493     for kind in section.kinds:
 494       kind._leafs = []
 495       section.validate_tree()
 496
 497     group_entry_by_kind = itertools.groupby(section._leafs, lambda x: x.kind)
 498     leaf_it = ((k, g) for k, g in group_entry_by_kind)
 499
 500     # allow multiple kinds with the same name. merge if adjacent
 501     # e.g. dynamic,dynamic,static,static,dynamic -> dynamic,static,dynamic
 502     # this helps maintain ABI compatibility when adding an entry in a new kind
 503     for idx, (kind_name, entry_it) in enumerate(leaf_it):
 504       if idx >= len(section._kinds):
 505         kind = Kind(kind_name, section)
 506         section._kinds.append(kind)
 507         section.validate_tree()
 508
 509       kind = section._kinds[idx]
 510
 511       for p in entry_it:
 512         if p not in kind._leafs:
 513           kind._leafs.append(p)
 514
 515     for kind in section._kinds:
 516       kind.validate_tree()
 517       self._construct_inner_namespaces(kind)
 518       kind.validate_tree()
 519       self._construct_entries(kind)
 520       kind.validate_tree()
 521
 522       if not section.validate_tree():
 523         print >> sys.stderr, ("ERROR: Failed to validate tree in " +           \
 524                              "construct_kinds, with kind = '%s'") %(kind)
 525
 526       if not kind.validate_tree():
 527         print >> sys.stderr, ("ERROR: Failed to validate tree in " +           \
 528                               "construct_kinds, with kind = '%s'") %(kind)
 529
 530   def _construct_inner_namespaces(self, parent, depth=0):
 531     #parent is InnerNamespace or Kind
 532     ins_dict = self._dictionary_by_name(parent.namespaces)
 533     for name, ins in ins_dict.iteritems():
 534       ins._leafs = []
 535
 536     for p in parent._leafs:
 537       ins_list = p.get_inner_namespace_list()
 538
 539       if len(ins_list) > depth:
 540         ins_str = ins_list[depth]
 541         ins = ins_dict.get(ins_str, InnerNamespace(ins_str, parent))
 542         ins_dict[ins_str] = ins
 543
 544         if p not in ins._leafs:
 545           ins._leafs.append(p)
 546
 547     for name, ins in ins_dict.iteritems():
 548       ins.validate_tree()
 549       # construct children INS
 550       self._construct_inner_namespaces(ins, depth + 1)
 551       ins.validate_tree()
 552       # construct children entries
 553       self._construct_entries(ins, depth + 1)
 554
 555       if ins not in parent.namespaces:
 556         parent._namespaces.append(ins)
 557
 558       if not ins.validate_tree():
 559         print >> sys.stderr, ("ERROR: Failed to validate tree in " +           \
 560                               "construct_inner_namespaces, with ins = '%s'")   \
 561                              %(ins)
 562
 563   # doesnt construct the entries, so much as links them
 564   def _construct_entries(self, parent, depth=0):
 565     #parent is InnerNamespace or Kind
 566     entry_dict = self._dictionary_by_name(parent.entries)
 567     for p in parent._leafs:
 568       ins_list = p.get_inner_namespace_list()
 569
 570       if len(ins_list) == depth:
 571         entry = entry_dict.get(p.name, p)
 572         entry_dict[p.name] = entry
 573
 574     for name, entry in entry_dict.iteritems():
 575
 576       old_parent = entry.parent
 577       entry._parent = parent
 578
 579       if entry not in parent.entries:
 580         parent._entries.append(entry)
 581
 582       if old_parent is not None and old_parent != parent:
 583         print >> sys.stderr, ("ERROR: Parent changed from '%s' to '%s' for " + \
 584                               "entry '%s'")                                    \
 585                              %(old_parent.name, parent.name, entry.name)
 586
 587   def _get_children(self):
 588     if self.outer_namespaces is not None:
 589       for i in self.outer_namespaces:
 590         yield i
 591
 592     if self.tags is not None:
 593       for i in self.tags:
 594         yield i
 595
 596 class Tag(Node):
 597   """
 598   A tag Node corresponding to a top-level <tag> element.
 599
 600   Attributes (Read-Only):
 601     name: alias for id
 602     id: The name of the tag, e.g. for <tag id="BC"/> id = 'BC'
 603     description: The description of the tag, the contents of the <tag> element.
 604     parent: An edge to the parent, which is always the Metadata root node.
 605     entries: A sequence of edges to entries/clones that are using this Tag.
 606   """
 607   def __init__(self, name, parent, description=""):
 608     self._name        = name  # 'id' attribute in XML
 609     self._id          = name
 610     self._description = description
 611     self._parent      = parent
 612
 613     # all entries that have this tag, including clones
 614     self._entries     = []  # filled in by Metadata#construct_tags
 615
 616   @property
 617   def id(self):
 618     return self._id
 619
 620   @property
 621   def description(self):
 622     return self._description
 623
 624   @property
 625   def entries(self):
 626     return (i for i in self._entries)
 627
 628   def _get_children(self):
 629     return None
 630
 631 class Typedef(Node):
 632   """
 633   A typedef Node corresponding to a <typedef> element under a top-level <types>.
 634
 635   Attributes (Read-Only):
 636     name: The name of this typedef as a string.
 637     languages: A dictionary of 'language name' -> 'fully qualified class'.
 638     parent: An edge to the parent, which is always the Metadata root node.
 639     entries: An iterable over all entries which reference this typedef.
 640   """
 641   def __init__(self, name, parent, languages=None):
 642     self._name        = name
 643     self._parent      = parent
 644
 645     # all entries that have this typedef
 646     self._entries     = []  # filled in by Metadata#construct_types
 647
 648     self._languages   = languages or {}
 649
 650   @property
 651   def languages(self):
 652     return self._languages
 653
 654   @property
 655   def entries(self):
 656     return (i for i in self._entries)
 657
 658   def _get_children(self):
 659     return None
 660
 661 class OuterNamespace(Node):
 662   """
 663   A node corresponding to a <namespace> element under <metadata>
 664
 665   Attributes (Read-Only):
 666     name: The name attribute of the <namespace name="foo"> element.
 667     parent: An edge to the parent, which is always the Metadata root node.
 668     sections: A sequence of Section children.
 669   """
 670   def __init__(self, name, parent, sections=[]):
 671     self._name = name
 672     self._parent = parent # MetadataSet
 673     self._sections = sections[:]
 674     self._leafs = []
 675
 676     self._children = self._sections
 677
 678   @property
 679   def sections(self):
 680     return (i for i in self._sections)
 681
 682 class Section(Node):
 683   """
 684   A node corresponding to a <section> element under <namespace>
 685
 686   Attributes (Read-Only):
 687     name: The name attribute of the <section name="foo"> element.
 688     parent: An edge to the parent, which is always an OuterNamespace instance.
 689     description: A string description of the section, or None.
 690     kinds: A sequence of Kind children.
 691     merged_kinds: A sequence of virtual Kind children,
 692                   with each Kind's children merged by the kind.name
 693   """
 694   def __init__(self, name, parent, description=None, kinds=[]):
 695     self._name = name
 696     self._parent = parent
 697     self._description = description
 698     self._kinds = kinds[:]
 699
 700     self._leafs = []
 701
 702
 703   @property
 704   def description(self):
 705     return self._description
 706
 707   @property
 708   def kinds(self):
 709     return (i for i in self._kinds)
 710
 711   def sort_children(self):
 712     self.validate_tree()
 713     # order is always controls,static,dynamic
 714     find_child = lambda x: [i for i in self._get_children() if i.name == x]
 715     new_lst = find_child('controls') \
 716             + find_child('static')   \
 717             + find_child('dynamic')
 718     self._kinds = new_lst
 719     self.validate_tree()
 720
 721   def _get_children(self):
 722     return (i for i in self.kinds)
 723
 724   @property
 725   def merged_kinds(self):
 726
 727     def aggregate_by_name(acc, el):
 728       existing = [i for i in acc if i.name == el.name]
 729       if existing:
 730         k = existing[0]
 731       else:
 732         k = Kind(el.name, el.parent)
 733         acc.append(k)
 734
 735       k._namespaces.extend(el._namespaces)
 736       k._entries.extend(el._entries)
 737
 738       return acc
 739
 740     new_kinds_lst = reduce(aggregate_by_name, self.kinds, [])
 741
 742     for k in new_kinds_lst:
 743       yield k
 744
 745   def combine_kinds_into_single_node(self):
 746     r"""
 747     Combines the section's Kinds into a single node.
 748
 749     Combines all the children (kinds) of this section into a single
 750     virtual Kind node.
 751
 752     Returns:
 753       A new Kind node that collapses all Kind siblings into one, combining
 754       all their children together.
 755
 756       For example, given self.kinds == [ x, y ]
 757
 758         x  y               z
 759       / |  | \    -->   / | | \
 760       a b  c d          a b c d
 761
 762       a new instance z is returned in this example.
 763
 764     Remarks:
 765       The children of the kinds are the same references as before, that is
 766       their parents will point to the old parents and not to the new parent.
 767     """
 768     combined = Kind(name="combined", parent=self)
 769
 770     for k in self._get_children():
 771       combined._namespaces.extend(k.namespaces)
 772       combined._entries.extend(k.entries)
 773
 774     return combined
 775
 776 class Kind(Node):
 777   """
 778   A node corresponding to one of: <static>,<dynamic>,<controls> under a
 779   <section> element.
 780
 781   Attributes (Read-Only):
 782     name: A string which is one of 'static', 'dynamic, or 'controls'.
 783     parent: An edge to the parent, which is always a Section  instance.
 784     namespaces: A sequence of InnerNamespace children.
 785     entries: A sequence of Entry/Clone children.
 786     merged_entries: A sequence of MergedEntry virtual nodes from entries
 787   """
 788   def __init__(self, name, parent):
 789     self._name = name
 790     self._parent = parent
 791     self._namespaces = []
 792     self._entries = []
 793
 794     self._leafs = []
 795
 796   @property
 797   def namespaces(self):
 798     return self._namespaces
 799
 800   @property
 801   def entries(self):
 802     return self._entries
 803
 804   @property
 805   def merged_entries(self):
 806     for i in self.entries:
 807       yield i.merge()
 808
 809   def sort_children(self):
 810     self._namespaces.sort(key=self._get_name())
 811     self._entries.sort(key=self._get_name())
 812
 813   def _get_children(self):
 814     for i in self.namespaces:
 815       yield i
 816     for i in self.entries:
 817       yield i
 818
 819   def combine_children_by_name(self):
 820     r"""
 821     Combine multiple children with the same name into a single node.
 822
 823     Returns:
 824       A new Kind where all of the children with the same name were combined.
 825
 826       For example:
 827
 828       Given a Kind k:
 829
 830               k
 831             / | \
 832             a b c
 833             | | |
 834             d e f
 835
 836       a.name == "foo"
 837       b.name == "foo"
 838       c.name == "bar"
 839
 840       The returned Kind will look like this:
 841
 842              k'
 843             /  \
 844             a' c'
 845           / |  |
 846           d e  f
 847
 848     Remarks:
 849       This operation is not recursive. To combine the grandchildren and other
 850       ancestors, call this method on the ancestor nodes.
 851     """
 852     return Kind._combine_children_by_name(self, new_type=type(self))
 853
 854   # new_type is either Kind or InnerNamespace
 855   @staticmethod
 856   def _combine_children_by_name(self, new_type):
 857     new_ins_dict = OrderedDict()
 858     new_ent_dict = OrderedDict()
 859
 860     for ins in self.namespaces:
 861       new_ins = new_ins_dict.setdefault(ins.name,
 862                                         InnerNamespace(ins.name, parent=self))
 863       new_ins._namespaces.extend(ins.namespaces)
 864       new_ins._entries.extend(ins.entries)
 865
 866     for ent in self.entries:
 867       new_ent = new_ent_dict.setdefault(ent.name,
 868                                         ent.merge())
 869
 870     kind = new_type(self.name, self.parent)
 871     kind._namespaces = new_ins_dict.values()
 872     kind._entries = new_ent_dict.values()
 873
 874     return kind
 875
 876 class InnerNamespace(Node):
 877   """
 878   A node corresponding to a <namespace> which is an ancestor of a Kind.
 879   These namespaces may have other namespaces recursively, or entries as leafs.
 880
 881   Attributes (Read-Only):
 882     name: Name attribute from the element, e.g. <namespace name="foo"> -> 'foo'
 883     parent: An edge to the parent, which is an InnerNamespace or a Kind.
 884     namespaces: A sequence of InnerNamespace children.
 885     entries: A sequence of Entry/Clone children.
 886     merged_entries: A sequence of MergedEntry virtual nodes from entries
 887   """
 888   def __init__(self, name, parent):
 889     self._name        = name
 890     self._parent      = parent
 891     self._namespaces  = []
 892     self._entries     = []
 893     self._leafs       = []
 894
 895   @property
 896   def namespaces(self):
 897     return self._namespaces
 898
 899   @property
 900   def entries(self):
 901     return self._entries
 902
 903   @property
 904   def merged_entries(self):
 905     for i in self.entries:
 906       yield i.merge()
 907
 908   def sort_children(self):
 909     self._namespaces.sort(key=self._get_name())
 910     self._entries.sort(key=self._get_name())
 911
 912   def _get_children(self):
 913     for i in self.namespaces:
 914       yield i
 915     for i in self.entries:
 916       yield i
 917
 918   def combine_children_by_name(self):
 919     r"""
 920     Combine multiple children with the same name into a single node.
 921
 922     Returns:
 923       A new InnerNamespace where all of the children with the same name were
 924       combined.
 925
 926       For example:
 927
 928       Given an InnerNamespace i:
 929
 930               i
 931             / | \
 932             a b c
 933             | | |
 934             d e f
 935
 936       a.name == "foo"
 937       b.name == "foo"
 938       c.name == "bar"
 939
 940       The returned InnerNamespace will look like this:
 941
 942              i'
 943             /  \
 944             a' c'
 945           / |  |
 946           d e  f
 947
 948     Remarks:
 949       This operation is not recursive. To combine the grandchildren and other
 950       ancestors, call this method on the ancestor nodes.
 951     """
 952     return Kind._combine_children_by_name(self, new_type=type(self))
 953
 954 class EnumValue(Node):
 955   """
 956   A class corresponding to a <value> element within an <enum> within an <entry>.
 957
 958   Attributes (Read-Only):
 959     name: A string,                 e.g. 'ON' or 'OFF'
 960     id: An optional numeric string, e.g. '0' or '0xFF'
 961     deprecated: A boolean, True if the enum should be deprecated.
 962     optional: A boolean
 963     hidden: A boolean, True if the enum should be hidden.
 964     ndk_hidden: A boolean, True if the enum should be hidden in NDK
 965     notes: A string describing the notes, or None.
 966     parent: An edge to the parent, always an Enum instance.
 967   """
 968   def __init__(self, name, parent,
 969       id=None, deprecated=False, optional=False, hidden=False, notes=None, ndk_hidden=False):
 970     self._name = name                    # str, e.g. 'ON' or 'OFF'
 971     self._id = id                        # int, e.g. '0'
 972     self._deprecated = deprecated        # bool
 973     self._optional = optional            # bool
 974     self._hidden = hidden                # bool
 975     self._ndk_hidden = ndk_hidden        # bool
 976     self._notes = notes                  # None or str
 977     self._parent = parent
 978
 979   @property
 980   def id(self):
 981     return self._id
 982
 983   @property
 984   def deprecated(self):
 985     return self._deprecated
 986
 987   @property
 988   def optional(self):
 989     return self._optional
 990
 991   @property
 992   def hidden(self):
 993     return self._hidden
 994
 995   @property
 996   def ndk_hidden(self):
 997     return self._ndk_hidden
 998
 999   @property
1000   def notes(self):
1001     return self._notes
1002
1003   def _get_children(self):
1004     return None
1005
1006 class Enum(Node):
1007   """
1008   A class corresponding to an <enum> element within an <entry>.
1009
1010   Attributes (Read-Only):
1011     parent: An edge to the parent, always an Entry instance.
1012     values: A sequence of EnumValue children.
1013     has_values_with_id: A boolean representing if any of the children have a
1014         non-empty id property.
1015   """
1016   def __init__(self, parent, values, ids={}, deprecateds=[],
1017       optionals=[], hiddens=[], notes={}, ndk_hiddens=[]):
1018     self._values =                                                             \
1019       [ EnumValue(val, self, ids.get(val), val in deprecateds, val in optionals, val in hiddens,  \
1020                   notes.get(val), val in ndk_hiddens)                                              \
1021         for val in values ]
1022
1023     self._parent = parent
1024     self._name = None
1025
1026   @property
1027   def values(self):
1028     return (i for i in self._values)
1029
1030   @property
1031   def has_values_with_id(self):
1032     return bool(any(i for i in self.values if i.id))
1033
1034   def _get_children(self):
1035     return (i for i in self._values)
1036
1037 class Entry(Node):
1038   """
1039   A node corresponding to an <entry> element.
1040
1041   Attributes (Read-Only):
1042     parent: An edge to the parent node, which is an InnerNamespace or Kind.
1043     name: The fully qualified name string, e.g. 'android.shading.mode'
1044     name_short: The name attribute from <entry name="mode">, e.g. mode
1045     type: The type attribute from <entry type="bar">
1046     kind: A string ('static', 'dynamic', 'controls') corresponding to the
1047           ancestor Kind#name
1048     container: The container attribute from <entry container="array">, or None.
1049     container_sizes: A sequence of size strings or None if container is None.
1050     enum: An Enum instance if the enum attribute is true, None otherwise.
1051     visibility: The visibility of this entry ('system', 'hidden', 'public')
1052                 across the system. System entries are only visible in native code
1053                 headers. Hidden entries are marked @hide in managed code, while
1054                 public entries are visible in the Android SDK.
1055     applied_visibility: As visibility, but always valid, defaulting to 'system'
1056                         if no visibility is given for an entry.
1057     applied_ndk_visible: Always valid. Default is 'false'.
1058                          Set to 'true' when the visibility implied entry is visible
1059                          in NDK.
1060     synthetic: The C-level visibility of this entry ('false', 'true').
1061                Synthetic entries will not be generated into the native metadata
1062                list of entries (in C code). In general a synthetic entry is
1063                glued together at the Java layer from multiple visibiltity=hidden
1064                entries.
1065     hwlevel: The lowest hardware level at which the entry is guaranteed
1066              to be supported by the camera device. All devices with higher
1067              hwlevels will also include this entry. None means that the
1068              entry is optional on any hardware level.
1069     deprecated: Marks an entry as @Deprecated in the Java layer; if within an
1070                unreleased version this needs to be removed altogether. If applied
1071                to an entry from an older release, then this means the entry
1072                should be ignored by newer code.
1073     optional: a bool representing the optional attribute, which denotes the entry
1074               is required for hardware level full devices, but optional for other
1075               hardware levels.  None if not present.
1076     applied_optional: As optional but always valid, defaulting to False if no
1077                       optional attribute is present.
1078     tuple_values: A sequence of strings describing the tuple values,
1079                   None if container is not 'tuple'.
1080     description: A string description, or None.
1081     range: A string range, or None.
1082     units: A string units, or None.
1083     tags: A sequence of Tag nodes associated with this Entry.
1084     type_notes: A string describing notes for the type, or None.
1085     typedef: A Typedef associated with this Entry, or None.
1086
1087   Remarks:
1088     Subclass Clone can be used interchangeable with an Entry,
1089     for when we don't care about the underlying type.
1090
1091     parent and tags edges are invalid until after Metadata#construct_graph
1092     has been invoked.
1093   """
1094   def __init__(self, **kwargs):
1095     """
1096     Instantiate a new Entry node.
1097
1098     Args:
1099       name: A string with the fully qualified name, e.g. 'android.shading.mode'
1100       type: A string describing the type, e.g. 'int32'
1101       kind: A string describing the kind, e.g. 'static'
1102
1103     Args (if container):
1104       container: A string describing the container, e.g. 'array' or 'tuple'
1105       container_sizes: A list of string sizes if a container, or None otherwise
1106
1107     Args (if container is 'tuple'):
1108       tuple_values: A list of tuple values, e.g. ['width', 'height']
1109
1110     Args (if the 'enum' attribute is true):
1111       enum: A boolean, True if this is an enum, False otherwise
1112       enum_values: A list of value strings, e.g. ['ON', 'OFF']
1113       enum_optionals: A list of optional enum values, e.g. ['OFF']
1114       enum_notes: A dictionary of value->notes strings.
1115       enum_ids: A dictionary of value->id strings.
1116
1117     Args (optional):
1118       description: A string with a description of the entry.
1119       range: A string with the range of the values of the entry, e.g. '>= 0'
1120       units: A string with the units of the values, e.g. 'inches'
1121       details: A string with the detailed documentation for the entry
1122       hal_details: A string with the HAL implementation details for the entry
1123       tag_ids: A list of tag ID strings, e.g. ['BC', 'V1']
1124       type_notes: A string with the notes for the type
1125       visibility: A string describing the visibility, eg 'system', 'hidden',
1126                   'public'
1127       synthetic: A bool to mark whether this entry is visible only at the Java
1128                  layer (True), or at both layers (False = default).
1129       hwlevel: A string of the HW level (one of 'legacy', 'limited', 'full')
1130       deprecated: A bool to mark whether this is @Deprecated at the Java layer
1131                  (default = False).
1132       optional: A bool to mark whether optional for non-full hardware devices
1133       typedef: A string corresponding to a typedef's name attribute.
1134     """
1135
1136     if kwargs.get('type') is None:
1137       print >> sys.stderr, "ERROR: Missing type for entry '%s' kind  '%s'"     \
1138       %(kwargs.get('name'), kwargs.get('kind'))
1139
1140     # Attributes are Read-Only, but edges may be mutated by
1141     # Metadata, particularly during construct_graph
1142
1143     self._name = kwargs['name']
1144     self._type = kwargs['type']
1145     self._kind = kwargs['kind'] # static, dynamic, or controls
1146
1147     self._init_common(**kwargs)
1148
1149   @property
1150   def type(self):
1151     return self._type
1152
1153   @property
1154   def kind(self):
1155     return self._kind
1156
1157   @property
1158   def visibility(self):
1159     return self._visibility
1160
1161   @property
1162   def applied_visibility(self):
1163     return self._visibility or 'system'
1164
1165   @property
1166   def applied_ndk_visible(self):
1167     if self._visibility in ("public", "ndk_public"):
1168       return "true"
1169     return "false"
1170
1171   @property
1172   def synthetic(self):
1173     return self._synthetic
1174
1175   @property
1176   def hwlevel(self):
1177     return self._hwlevel
1178
1179   @property
1180   def deprecated(self):
1181     return self._deprecated
1182
1183   # TODO: optional should just return hwlevel is None
1184   @property
1185   def optional(self):
1186     return self._optional
1187
1188   @property
1189   def applied_optional(self):
1190     return self._optional or False
1191
1192   @property
1193   def name_short(self):
1194     return self.get_name_minimal()
1195
1196   @property
1197   def container(self):
1198     return self._container
1199
1200   @property
1201   def container_sizes(self):
1202     if self._container_sizes is None:
1203       return None
1204     else:
1205       return (i for i in self._container_sizes)
1206
1207   @property
1208   def tuple_values(self):
1209     if self._tuple_values is None:
1210       return None
1211     else:
1212       return (i for i in self._tuple_values)
1213
1214   @property
1215   def description(self):
1216     return self._description
1217
1218   @property
1219   def range(self):
1220     return self._range
1221
1222   @property
1223   def units(self):
1224     return self._units
1225
1226   @property
1227   def details(self):
1228     return self._details
1229
1230   @property
1231   def hal_details(self):
1232     return self._hal_details
1233
1234   @property
1235   def tags(self):
1236     if self._tags is None:
1237       return None
1238     else:
1239       return (i for i in self._tags)
1240
1241   @property
1242   def type_notes(self):
1243     return self._type_notes
1244
1245   @property
1246   def typedef(self):
1247     return self._typedef
1248
1249   @property
1250   def enum(self):
1251     return self._enum
1252
1253   def _get_children(self):
1254     if self.enum:
1255       yield self.enum
1256
1257   def sort_children(self):
1258     return None
1259
1260   def is_clone(self):
1261     """
1262     Whether or not this is a Clone instance.
1263
1264     Returns:
1265       False
1266     """
1267     return False
1268
1269   def _init_common(self, **kwargs):
1270
1271     self._parent = None # filled in by Metadata::_construct_entries
1272
1273     self._container = kwargs.get('container')
1274     self._container_sizes = kwargs.get('container_sizes')
1275
1276     # access these via the 'enum' prop
1277     enum_values = kwargs.get('enum_values')
1278     enum_deprecateds = kwargs.get('enum_deprecateds')
1279     enum_optionals = kwargs.get('enum_optionals')
1280     enum_hiddens = kwargs.get('enum_hiddens')
1281     enum_ndk_hiddens = kwargs.get('enum_ndk_hiddens')
1282     enum_notes = kwargs.get('enum_notes')  # { value => notes }
1283     enum_ids = kwargs.get('enum_ids')  # { value => notes }
1284     self._tuple_values = kwargs.get('tuple_values')
1285
1286     self._description = kwargs.get('description')
1287     self._range = kwargs.get('range')
1288     self._units = kwargs.get('units')
1289     self._details = kwargs.get('details')
1290     self._hal_details = kwargs.get('hal_details')
1291
1292     self._tag_ids = kwargs.get('tag_ids', [])
1293     self._tags = None  # Filled in by Metadata::_construct_tags
1294
1295     self._type_notes = kwargs.get('type_notes')
1296     self._type_name = kwargs.get('type_name')
1297     self._typedef = None # Filled in by Metadata::_construct_types
1298
1299     if kwargs.get('enum', False):
1300       self._enum = Enum(self, enum_values, enum_ids, enum_deprecateds, enum_optionals,
1301                         enum_hiddens, enum_notes, enum_ndk_hiddens)
1302     else:
1303       self._enum = None
1304
1305     self._visibility = kwargs.get('visibility')
1306     self._synthetic = kwargs.get('synthetic', False)
1307     self._hwlevel = kwargs.get('hwlevel')
1308     self._deprecated = kwargs.get('deprecated', False)
1309     self._optional = kwargs.get('optional')
1310     self._ndk_visible = kwargs.get('ndk_visible')
1311
1312     self._property_keys = kwargs
1313
1314   def merge(self):
1315     """
1316     Copy the attributes into a new entry, merging it with the target entry
1317     if it's a clone.
1318     """
1319     return MergedEntry(self)
1320
1321   # Helpers for accessing less than the fully qualified name
1322
1323   def get_name_as_list(self):
1324     """
1325     Returns the name as a list split by a period.
1326
1327     For example:
1328       entry.name is 'android.lens.info.shading'
1329       entry.get_name_as_list() == ['android', 'lens', 'info', 'shading']
1330     """
1331     return self.name.split(".")
1332
1333   def get_inner_namespace_list(self):
1334     """
1335     Returns the inner namespace part of the name as a list
1336
1337     For example:
1338       entry.name is 'android.lens.info.shading'
1339       entry.get_inner_namespace_list() == ['info']
1340     """
1341     return self.get_name_as_list()[2:-1]
1342
1343   def get_outer_namespace(self):
1344     """
1345     Returns the outer namespace as a string.
1346
1347     For example:
1348       entry.name is 'android.lens.info.shading'
1349       entry.get_outer_namespace() == 'android'
1350
1351     Remarks:
1352       Since outer namespaces are non-recursive,
1353       and each entry has one, this does not need to be a list.
1354     """
1355     return self.get_name_as_list()[0]
1356
1357   def get_section(self):
1358     """
1359     Returns the section as a string.
1360
1361     For example:
1362       entry.name is 'android.lens.info.shading'
1363       entry.get_section() == ''
1364
1365     Remarks:
1366       Since outer namespaces are non-recursive,
1367       and each entry has one, this does not need to be a list.
1368     """
1369     return self.get_name_as_list()[1]
1370
1371   def get_name_minimal(self):
1372     """
1373     Returns only the last component of the fully qualified name as a string.
1374
1375     For example:
1376       entry.name is 'android.lens.info.shading'
1377       entry.get_name_minimal() == 'shading'
1378
1379     Remarks:
1380       entry.name_short it an alias for this
1381     """
1382     return self.get_name_as_list()[-1]
1383
1384   def get_path_without_name(self):
1385     """
1386     Returns a string path to the entry, with the name component excluded.
1387
1388     For example:
1389       entry.name is 'android.lens.info.shading'
1390       entry.get_path_without_name() == 'android.lens.info'
1391     """
1392     return ".".join(self.get_name_as_list()[0:-1])
1393
1394
1395 class Clone(Entry):
1396   """
1397   A Node corresponding to a <clone> element. It has all the attributes of an
1398   <entry> element (Entry) plus the additions specified below.
1399
1400   Attributes (Read-Only):
1401     entry: an edge to an Entry object that this targets
1402     target_kind: A string describing the kind of the target entry.
1403     name: a string of the name, same as entry.name
1404     kind: a string of the Kind ancestor, one of 'static', 'controls', 'dynamic'
1405           for the <clone> element.
1406     type: always None, since a clone cannot override the type.
1407   """
1408   def __init__(self, entry=None, **kwargs):
1409     """
1410     Instantiate a new Clone node.
1411
1412     Args:
1413       name: A string with the fully qualified name, e.g. 'android.shading.mode'
1414       type: A string describing the type, e.g. 'int32'
1415       kind: A string describing the kind, e.g. 'static'
1416       target_kind: A string for the kind of the target entry, e.g. 'dynamic'
1417
1418     Args (if container):
1419       container: A string describing the container, e.g. 'array' or 'tuple'
1420       container_sizes: A list of string sizes if a container, or None otherwise
1421
1422     Args (if container is 'tuple'):
1423       tuple_values: A list of tuple values, e.g. ['width', 'height']
1424
1425     Args (if the 'enum' attribute is true):
1426       enum: A boolean, True if this is an enum, False otherwise
1427       enum_values: A list of value strings, e.g. ['ON', 'OFF']
1428       enum_optionals: A list of optional enum values, e.g. ['OFF']
1429       enum_notes: A dictionary of value->notes strings.
1430       enum_ids: A dictionary of value->id strings.
1431
1432     Args (optional):
1433       entry: An edge to the corresponding target Entry.
1434       description: A string with a description of the entry.
1435       range: A string with the range of the values of the entry, e.g. '>= 0'
1436       units: A string with the units of the values, e.g. 'inches'
1437       details: A string with the detailed documentation for the entry
1438       hal_details: A string with the HAL implementation details for the entry
1439       tag_ids: A list of tag ID strings, e.g. ['BC', 'V1']
1440       type_notes: A string with the notes for the type
1441
1442     Remarks:
1443       Note that type is not specified since it has to be the same as the
1444       entry.type.
1445     """
1446     self._entry = entry  # Entry object
1447     self._target_kind = kwargs['target_kind']
1448     self._name = kwargs['name']  # same as entry.name
1449     self._kind = kwargs['kind']
1450
1451     # illegal to override the type, it should be the same as the entry
1452     self._type = None
1453     # the rest of the kwargs are optional
1454     # can be used to override the regular entry data
1455     self._init_common(**kwargs)
1456
1457   @property
1458   def entry(self):
1459     return self._entry
1460
1461   @property
1462   def target_kind(self):
1463     return self._target_kind
1464
1465   def is_clone(self):
1466     """
1467     Whether or not this is a Clone instance.
1468
1469     Returns:
1470       True
1471     """
1472     return True
1473
1474 class MergedEntry(Entry):
1475   """
1476   A MergedEntry has all the attributes of a Clone and its target Entry merged
1477   together.
1478
1479   Remarks:
1480     Useful when we want to 'unfold' a clone into a real entry by copying out
1481     the target entry data. In this case we don't care about distinguishing
1482     a clone vs an entry.
1483   """
1484   def __init__(self, entry):
1485     """
1486     Create a new instance of MergedEntry.
1487
1488     Args:
1489       entry: An Entry or Clone instance
1490     """
1491     props_distinct = ['description', 'units', 'range', 'details',
1492                       'hal_details', 'tags', 'kind']
1493
1494     for p in props_distinct:
1495       p = '_' + p
1496       if entry.is_clone():
1497         setattr(self, p, getattr(entry, p) or getattr(entry.entry, p))
1498       else:
1499         setattr(self, p, getattr(entry, p))
1500
1501     props_common = ['parent', 'name', 'container',
1502                     'container_sizes', 'enum',
1503                     'tuple_values',
1504                     'type',
1505                     'type_notes',
1506                     'visibility',
1507                     'ndk_visible',
1508                     'synthetic',
1509                     'hwlevel',
1510                     'deprecated',
1511                     'optional',
1512                     'typedef'
1513                    ]
1514
1515     for p in props_common:
1516       p = '_' + p
1517       if entry.is_clone():
1518         setattr(self, p, getattr(entry.entry, p))
1519       else:
1520         setattr(self, p, getattr(entry, p))