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