dsdl.py

# Copyright (c) 2011 by Ladislav Lhotka, CESNET <lhotka@cesnet.cz>
#                       Martin Bjorklund <mbj@tail-f.com>
#
# Translator of YANG to the hybrid DSDL schema (see RFC 6110).
#
# Permission to use, copy, modify, and/or distribute this software for any
# purpose with or without fee is hereby granted, provided that the above
# copyright notice and this permission notice appear in all copies.
# 
# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
# WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
# MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
# ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
# WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
# ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
# OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

"""Translator from YANG to hybrid DSDL schema.

It is designed as a plugin for the pyang program and defines several
new command-line options:

--dsdl-no-documentation
    No output of DTD compatibility documentation annotations

--dsdl-no-dublin-core
    No output of Dublin Core annotations

--dsdl-record-defs
    Record all top-level defs, even if they are not used

Three classes are defined in this module:

* `DSDLPlugin`: pyang plugin interface class

* `HybridDSDLSchema`: provides instance that performs the mapping
  of input YANG modules to the hybrid DSDL schema.

* `Patch`: utility class representing a patch to the YANG tree
  where augment and refine statements are recorded.
"""

__docformat__ = "reStructuredText"

import sys
import optparse
import time

import pyang
from pyang import plugin, error, xpath, util, statements, types

from schemanode import SchemaNode

def pyang_plugin_init():
    plugin.register_plugin(DSDLPlugin())

class DSDLPlugin(plugin.PyangPlugin):
    def add_output_format(self, fmts):
        self.multiple_modules = True
        fmts['dsdl'] = self
    def add_opts(self, optparser):
        optlist = [
            optparse.make_option("--dsdl-no-documentation",
                                 dest="dsdl_no_documentation",
                                 action="store_true",
                                 default=False,
                                 help="No output of DTD compatibility"
                                 " documentation annotations"),
            optparse.make_option("--dsdl-no-dublin-core",
                                 dest="dsdl_no_dublin_core",
                                 action="store_true",
                                 default=False,
                                 help="No output of Dublin Core"
                                 " metadata annotations"),
            optparse.make_option("--dsdl-record-defs",
                                 dest="dsdl_record_defs",
                                 action="store_true",
                                 default=False,
                                 help="Record all top-level defs"
                                 " (even if not used)"),
            ]
        g = optparser.add_option_group("Hybrid DSDL schema "
                                       "output specific options")
        g.add_options(optlist)

    def emit(self, ctx, modules, fd):
        if 'submodule' in [ m.keyword for m in modules ]:
            raise error.EmitError("Cannot translate submodules")
        emit_dsdl(ctx, modules, fd)

def emit_dsdl(ctx, modules, fd):
    # No errors are allowed
    for (epos, etag, eargs) in ctx.errors:
        if error.is_error(error.err_level(etag)):
            raise error.EmitError("DSDL translation needs a valid module")
    schema = HybridDSDLSchema().from_modules(modules,
                                  ctx.opts.dsdl_no_dublin_core,
                                  ctx.opts.dsdl_no_documentation,
                                  ctx.opts.dsdl_record_defs, debug=0)
    fd.write(schema.serialize())

class Patch(object):

    """Instances of this class represent a patch to the YANG tree.

    A Patch is filled with substatements of 'refine' and/or 'augment'
    that are to be applied to a single node.

    Instance variables:

    * `self.path`: list specifying the relative path to the node where
      the patch is to be applied

    * `self.plist`: list of statements to apply
    """

    def __init__(self, path, refaug):
        """Initialize the instance with `refaug` statement.

        `refaug` must be either 'refine' or 'augment'.
        """
        self.path = path
        self.plist = [refaug]

    def pop(self):
        """Pop and return the first element of `self.path`."""
        return self.path.pop(0)

    def combine(self, patch):
        """Add `patch.plist` to `self.plist`."""
        exclusive = set(["config", "default", "mandatory", "presence",
                     "min-elements", "max-elements"])
        kws = set([s.keyword for s in self.plist]) & exclusive
        add = [n for n in patch.plist if n.keyword not in kws]
        self.plist.extend(add)

class HybridDSDLSchema(object):

    """Instance of this class maps YANG to the hybrid DSDL schema.

    Typically, only a single instance is created.

    Instance variables:

    * `self.all_defs`: dictionary of all named pattern
      definitions. The keys are mangled names of the definitions.

    * `self.data`: root of the data tree.

    * `self.debug`: debugging information level (0 = no debugging).

    * `self.gg_level`: level of immersion in global groupings.

    * `self.global_defs`: dictionary of global (aka chameleon) named
      pattern definitions. The keys are mangled names of the
      definitions.

    * `self.has_anyxml`: boolean flag indicating presence of the
      'anyxml' statement in any input YANG module.

    * `self.identities`: dictionary of identity names as keys and the
      corresponding name pattern definitions as values.

    * `self.identity_deps: dictionary showing the dependences among
      identities - identity_name -> list of all identities that define
      identity_name as their base.

    * `self.local_defs`: dictionary of local named pattern
      definitions. The keys are mangled names of the definitions.

    * `self.local_grammar`: the inner <grammar> element containing the
      mapping of a single YANG module.

    * `self.module`: the module being processed.

    * `self.module_prefixes`: maps module names to (disambiguated)
      prefixes.

    * `self.namespaces`: maps used namespace URIs to (disambiguated)
      prefixes.

    * `self.notifications`: root of the subtree containing
      notifications.

    * `self.prefix_stack`: stack of active module prefixes. A new
      prefix is pushed on the stack for an augment from an external
      module.

    * `self.rpcs`: root of the subtree containing RPC signatures.

    * `self.stmt_handler`: dictionary of methods that are dispatched
      for handling individual YANG statements. Its keys are YANG
      statement keywords.

    * `self.top_grammar`: the outer (root) <grammar> element.

    * `self.type_handler`: dictionary of methods that are dispatched
      for handling individual YANG types. Its keys are the names of
      YANG built-in types.

    * `self.tree`: outer <start> pattern.

    """

    YANG_version = 1
    """Checked against the yang-version statement, if present."""

    dc_uri = "http://purl.org/dc/terms"
    """Dublin Core URI"""
    a_uri =  "http://relaxng.org/ns/compatibility/annotations/1.0"
    """DTD compatibility annotations URI"""

    datatype_map = {
        "int8": "byte",
        "int16": "short",
        "int32": "int",
        "int64": "long",
        "uint8": "unsignedByte",
        "uint16": "unsignedShort",
        "uint32": "unsignedInt",
        "uint64": "unsignedLong",
        "decimal64": "decimal",
        "binary": "base64Binary",
        "string": "string",
    }
    """Mapping of simple datatypes from YANG to W3C datatype library"""

    anyxml_def = ('<define name="__anyxml__"><zeroOrMore><choice>' +
                  '<attribute><anyName/></attribute>' +
                  '<element><anyName/><ref name="__anyxml__"/></element>' +
                  '<text/></choice></zeroOrMore></define>')
    """This definition is inserted first time 'anyxml' is found ."""

    data_nodes = ("leaf", "container", "leaf-list", "list",
                  "anyxml", "rpc", "notification")
    """Keywords of YANG data nodes."""

    schema_nodes = data_nodes + ("choice", "case")
    """Keywords of YANG schema nodes."""

    def __init__(self):
        """Initialize the dispatch dictionaries."""
        self.stmt_handler = {
            "anyxml": self.anyxml_stmt,
            "argument": self.noop,
            "augment": self.noop,
            "base": self.noop,
            "belongs-to": self.noop,
            "case": self.case_stmt,
            "choice": self.choice_stmt,
            "config": self.nma_attribute,
            "contact": self.noop,
            "container": self.container_stmt,
            "default": self.noop,
            "deviation": self.noop,
            "description": self.description_stmt,
            "enum" : self.enum_stmt,
            "feature": self.noop,
            "identity": self.noop,
            "if-feature": self.if_feature_stmt,
            "extension": self.noop,
            "import" : self.noop,
            "include" : self.include_stmt,
            "input": self.noop,
            "grouping" : self.noop,
            "key": self.noop,
            "leaf": self.leaf_stmt,
            "leaf-list": self.leaf_list_stmt,
            "list": self.list_stmt,
            "mandatory": self.noop,
            "min-elements": self.noop,
            "max-elements": self.noop,
            "must": self.must_stmt,
            "namespace": self.noop,
            "notification": self.notification_stmt,
            "ordered-by": self.nma_attribute,
            "organization": self.noop,
            "output": self.noop,
            "prefix": self.noop,
            "presence": self.noop,
            "reference": self.reference_stmt,
            "refine": self.noop,
            "revision": self.noop,
            "rpc": self.rpc_stmt,
            "min-elements": self.noop,
            "status" : self.nma_attribute,
            "type": self.type_stmt,
            "typedef" : self.noop,
            "unique" : self.unique_stmt,
            "units" : self.nma_attribute,
            "uses" : self.uses_stmt,
            "when" : self.when_stmt,
            "yang-version": self.yang_version_stmt,
        }
        self.type_handler = {
            "boolean": self.boolean_type,
            "binary": self.binary_type,
            "bits": self.bits_type,
            "decimal64": self.numeric_type,
            "enumeration": self.choice_type,
            "empty": self.empty_type,
            "identityref": self.identityref_type,
            "instance-identifier": self.instance_identifier_type,
            "int8": self.numeric_type,
            "int16": self.numeric_type,
            "int32": self.numeric_type,
            "int64": self.numeric_type,
            "leafref": self.leafref_type,
            "string" : self.string_type,
            "uint8": self.numeric_type,
            "uint16": self.numeric_type,
            "uint32": self.numeric_type,
            "uint64": self.numeric_type,
            "union": self.choice_type,
        }

    def serialize(self):
        """Return the string representation of the receiver."""
        res = '<?xml version="1.0" encoding="UTF-8"?>'
        self.top_grammar.attr["xmlns"] = \
            "http://relaxng.org/ns/structure/1.0"
        self.top_grammar.attr["datatypeLibrary"] = \
            "http://www.w3.org/2001/XMLSchema-datatypes"
        for ns in self.namespaces:
            self.top_grammar.attr["xmlns:" + self.namespaces[ns]] = ns
        res += self.top_grammar.start_tag()
        for ch in self.top_grammar.children:
            res += ch.serialize()
        res += self.tree.serialize()
        for d in self.global_defs:
            res += self.global_defs[d].serialize()
        for i in self.identities:
            res += self.identities[i].serialize()
        if self.has_anyxml:
            res += self.anyxml_def
        return res + self.top_grammar.end_tag()

    def from_modules(self, modules, no_dc=False, no_a=False,
                     record_defs=False, debug=0):
        """Return the instance representing mapped input modules."""
        self.namespaces = {
            "urn:ietf:params:xml:ns:netmod:dsdl-annotations:1" : "nma",
        }
        if not no_dc: self.namespaces[self.dc_uri] = "dc"
        if not no_a: self.namespaces[self.a_uri] = "a"
        self.global_defs = {}
        self.all_defs = {}
        self.identity_deps = {}
        self.identities = {}
        self.has_anyxml = False
        self.debug = debug
        self.module_prefixes = {}
        gpset = {}
        self.gg_level = 0
        for module in modules: self.add_namespace(module)
        for module in modules[0].i_ctx.modules.values():
            for i in module.i_identities:
                self.register_identity(module.i_identities[i])
        for module in modules:
            self.module = module
            self.prefix_stack = [self.module_prefixes[module.arg]]
            for aug in module.search("augment"):
                self.add_patch(gpset, aug)
            for sub in [ module.i_ctx.get_module(inc.arg)
                         for inc in module.search("include") ]:
                for aug in sub.search("augment"):
                    self.add_patch(gpset, aug)
        self.setup_top()
        for module in modules:
            self.module = module
            self.local_defs = {}
            if record_defs: self.preload_defs()
            self.prefix_stack = [self.module_prefixes[module.arg]]
            self.create_roots(module)
            self.lookup_expand(module, gpset.keys())
            self.handle_substmts(module, self.data, gpset)
            for d in self.local_defs.values():
                self.local_grammar.subnode(d)
            self.tree.subnode(self.local_grammar)
            self.all_defs.update(self.local_defs)
        self.all_defs.update(self.global_defs)
        self.dc_element(self.top_grammar, "date", time.strftime("%Y-%m-%d"))
        self.dc_element(self.top_grammar, "creator",
                        "Pyang %s, DSDL plugin" % pyang.__version__)
        return self

    def setup_top(self):
        """Create top-level elements of the hybrid schema."""
        self.top_grammar = SchemaNode("grammar")
        self.tree = SchemaNode("start")

    def create_roots(self, yam):
        """Create the top-level structure for module `yam`."""
        self.local_grammar = SchemaNode("grammar")
        self.local_grammar.attr["ns"] = yam.search_one("namespace").arg
        self.local_grammar.attr["nma:module"] = self.module.arg
        src_text = "YANG module '%s'" % yam.arg
        revs = yam.search("revision")
        if len(revs) > 0:
            src_text += " revision %s" % self.current_revision(revs)
        self.dc_element(self.local_grammar, "source", src_text)
        start = SchemaNode("start", self.local_grammar)
        self.data = SchemaNode("nma:data", start, interleave=True)
        self.data.occur = 2
        self.rpcs = SchemaNode("nma:rpcs", start, interleave=False)
        self.notifications = SchemaNode("nma:notifications", start,
                                        interleave=False)

    def yang_to_xpath(self, xpe):
        """Transform YANG's `xpath` to standard XPath 1.0

        Prefixes are added to unprefixed local names. Inside global
        groupings, the prefix is represented as the variable '$pref'
        which is substituted via Schematron abstract patterns.
        """
        if self.gg_level:
            pref = "$pref"
        else:
            pref = self.prefix_stack[-1]
        return xpath.add_prefix(pref, xpe)

    def add_namespace(self, module):
        """Add item uri:prefix for `module` to `self.namespaces`.

        The prefix to be actually used for `uri` is returned.  If the
        namespace is already present, the old prefix is used.  Prefix
        clashes are resolved by disambiguating `prefix`.
        """
        uri = module.search_one("namespace").arg
        prefix = module.search_one("prefix").arg
        if uri in self.namespaces: return self.namespaces[uri]
        end = 1
        new = prefix
        while new in self.namespaces.values():
            new = "%s%x" % (prefix,end)
            end += 1
        self.namespaces[uri] = new
        self.module_prefixes[module.arg] = new
        for inc in module.search("include"):
            self.module_prefixes[inc.arg] = new
        return new

    def register_identity(self, id_stmt):
        """Register identity `ident` in `self.identity_deps`.

        Fill in (recursively) all derivations from base identities.
        """
        module = self.main_module(id_stmt)
        self.add_namespace(module)
        qid = self.module_prefixes[module.arg] + ":" + id_stmt.arg
        if qid in self.identity_deps: return qid
        self.identity_deps[qid] = []
        bst = id_stmt.search_one("base")
        if not bst: return qid
        bist = bst.i_identity
        bn = self.register_identity(bist)
        self.identity_deps[bn].append(qid)
        return qid

    def add_identity(self, ident):
        """Add `id_stmt` and all derivates to `self.identities`.

        `ident` must be a fully qualified identity name.
        """
        def trname(iname): return "__" + iname.replace(":","_")
        if ident in self.identities: return
        parent = SchemaNode.define(trname(ident))
        self.identities[ident] = parent
        if self.identity_deps[ident]:
            parent = SchemaNode.choice(parent, occur=2)
        SchemaNode("value", parent, ident).attr["type"]="QName"
        for i in self.identity_deps[ident]:
            SchemaNode("ref", parent).attr["name"]=trname(i)
            self.add_identity(i)

    def preload_defs(self):
        """Preload all top-level definitions."""
        for d in (self.module.search("grouping") +
                  self.module.search("typedef")):
            uname, dic = self.unique_def_name(d)
            self.install_def(uname, d, dic)

    def add_prefix(self, name, stmt):
        """Return `name` prepended with correct prefix.

        If the name is already prefixed, the prefix may be translated
        to the value obtained from `self.module_prefixes`.  Unmodified
        `name` is returned if we are inside a global grouping.
        """
        if self.gg_level: return name
        pref, colon, local = name.partition(":")
        if colon:
            return (self.module_prefixes[stmt.i_module.i_prefixes[pref][0]]
                    + ":" + local)
        else:
            return self.prefix_stack[-1] + ":" + pref

    def qname(self, stmt):
        """Return (prefixed) node name of `stmt`.

        The result is prefixed with the local prefix unless we are
        inside a global grouping.
        """
        if self.gg_level: return stmt.arg
        return self.prefix_stack[-1] + ":" + stmt.arg

    def dc_element(self, parent, name, text):
        """Add DC element `name` containing `text` to `parent`."""
        if self.dc_uri in self.namespaces:
            dcel = SchemaNode(self.namespaces[self.dc_uri] + ":" + name,
                              text=text)
            parent.children.insert(0,dcel)

    def get_default(self, stmt, refd):
        """Return default value for `stmt` node.

        `refd` is a dictionary of applicable refinements that is
        constructed in the `process_patches` method.
        """
        if refd["default"]:
                return refd["default"]
        defst = stmt.search_one("default")
        if defst:
            return defst.arg
        return None

    def main_module(self, stmt):
        """Return the main module to which `stmt` belongs.
        """
        if stmt.i_module.keyword == "submodule":
            return stmt.i_module.i_ctx.get_module(
                stmt.i_module.i_including_modulename)
        return stmt.i_module

    def unique_def_name(self, stmt, inrpc=False):
        """Mangle the name of `stmt` (typedef or grouping).

        Return the mangled name and dictionary where the definition is
        to be installed. The `inrpc` flag indicates when we are inside
        an RPC, in which case the name gets the "__rpc" suffix.
        """
        module = self.main_module(stmt)
        if stmt.parent.keyword in ("module", "submodule"):
            name = stmt.arg
            defs = self.global_defs
        else:
            name = "__".join(stmt.full_path())
            defs = self.local_defs
        if inrpc: name += "__rpc"
        return (module.arg + "__" + name, defs)

    def add_patch(self, pset, augref):
        """Add patch corresponding to `augref` to `pset`.

        `augref` must be either 'augment' or 'refine' statement.
        """
        try:
            path = [ self.add_prefix(c, augref)
                     for c in augref.arg.split("/") if c ]
        except KeyError:
            # augment of a module that's not among input modules
            return
        car = path[0]
        patch = Patch(path[1:], augref)
        if car in pset:
            sel = [ x for x in pset[car] if patch.path == x.path ]
            if sel:
                sel[0].combine(patch)
            else:
                pset[car].append(patch)
        else:
            pset[car] = [patch]

    def apply_augments(self, auglist, p_elem, pset):
        """Handle substatements of augments from `auglist`.

        The augments are applied in the context of `p_elem`.  `pset`
        is a patch set containing patches that may be applicable to
        descendants.
        """
        for a in auglist:
            par = a.parent
            if p_elem.name == "choice" or a.search_one("when") is None:
                wel = p_elem
            else:
                if p_elem.interleave:
                    kw = "interleave"
                else:
                    kw = "group"
                wel = SchemaNode(kw, p_elem, interleave=p_elem.interleave)
                wel.occur = p_elem.occur
            if par.keyword == "uses":
                self.handle_substmts(a, wel, pset)
                continue
            if par.keyword == "submodule":
                mnam = par.i_including_modulename
            else:
                mnam = par.arg
            if self.prefix_stack[-1] == self.module_prefixes[mnam]:
                self.handle_substmts(a, wel, pset)
            else:
                self.prefix_stack.append(self.module_prefixes[mnam])
                self.handle_substmts(a, wel, pset)
                self.prefix_stack.pop()

    def current_revision(self, r_stmts):
        """Pick the most recent revision date.

        `r_stmts` is a list of 'revision' statements.
        """
        cur = max([[int(p) for p in r.arg.split("-")] for r in r_stmts])
        return "%4d-%02d-%02d" % tuple(cur)

    def insert_doc(self, p_elem, docstring):
        """Add <a:documentation> with `docstring` to `p_elem`."""
        dtag = self.namespaces[self.a_uri] + ":documentation"
        elem = SchemaNode(dtag, text=docstring)
        pos = 0
        for ch in p_elem.children:
            if ch.name == dtag: pos += 1
        p_elem.children.insert(pos, elem)

    def install_def(self, name, dstmt, def_map, interleave=False):
        """Install definition `name` into the appropriate dictionary.

        `dstmt` is the definition statement ('typedef' or 'grouping')
        that is to be mapped to a RELAX NG named pattern '<define
        name="`name`">'. `def_map` must be either `self.local_defs` or
        `self.global_defs`. `interleave` determines the interleave
        status inside the definition.
        """
        delem = SchemaNode.define(name, interleave=interleave)
        delem.attr["name"] = name
        def_map[name] = delem
        if def_map is self.global_defs: self.gg_level += 1
        self.handle_substmts(dstmt, delem)
        if def_map is self.global_defs: self.gg_level -= 1

    def handle_extension(self, stmt, p_elem):
        """Append YIN representation of extension statement `stmt`."""
        ext = stmt.i_extension
        prf, extkw = stmt.raw_keyword
        (modname,rev)=self.module.i_prefixes[prf]
        prefix = self.add_namespace(
            statements.modulename_to_module(self.module,modname,rev))
        eel = SchemaNode(prefix + ":" + extkw, p_elem)
        argst = ext.search_one("argument")
        if argst:
            if argst.search_one("yin-element", "true"):
                SchemaNode(prefix + ":" + argst.arg, eel, stmt.arg)
            else:
                eel.attr[argst.arg] = stmt.arg
        self.handle_substmts(stmt, eel)

    def propagate_occur(self, node, value):
        """Propagate occurence `value` to `node` and its ancestors.

        Occurence values are defined and explained in the SchemaNode
        class.
        """
        while node.occur < value:
            node.occur = value
            if node.name == "define":
                break
            node = node.parent

    def process_patches(self, pset, stmt, elem, altname=None):
        """Process patches for data node `name` from `pset`.

        `stmt` provides the context in YANG and `elem` is the parent
        element in the output schema. Refinements adding documentation
        and changing the config status are immediately applied. 

        The returned tuple consists of:
        - a dictionary of refinements, in which keys are the keywords
          of the refinement statements and values are the new values
          of refined parameters.
        - a list of 'augment' statements that are to be applied
          directly under `elem`.
        - a new patch set containing patches applicable to
          substatements of `stmt`.
        """
        if altname:
            name = altname
        else:
            name = stmt.arg
        new_pset = {}
        augments = []
        refine_dict = dict.fromkeys(("presence", "default", "mandatory",
                                     "min-elements", "max-elements"))
        for p in pset.pop(self.add_prefix(name, stmt), []):
            if p.path:
                head = p.pop()
                if head in new_pset:
                    new_pset[head].append(p)
                else:
                    new_pset[head] = [p]
            else:
                for refaug in p.plist:
                    if refaug.keyword == "augment":
                        augments.append(refaug)
                    else:
                        for s in refaug.substmts:
                            if s.keyword == "description":
                                self.description_stmt(s, elem, None)
                            elif s.keyword == "reference":
                                self.reference_stmt(s, elem, None)
                            elif s.keyword == "must":
                                self.must_stmt(s, elem, None)
                            elif s.keyword == "config":
                                self.nma_attribute(s, elem)
                            elif refine_dict.get(s.keyword, False) is None:
                                refine_dict[s.keyword] = s.arg
        return (refine_dict, augments, new_pset)

    def get_minmax(self, stmt, refine_dict):
        """Return pair of (min,max)-elements values for `stmt`.

        `stmt` must be a 'list' or 'leaf-list'. Applicable refinements
        from `refine_dict` are also taken into account.
        """
        minel = refine_dict["min-elements"]
        maxel = refine_dict["max-elements"]
        if minel is None:
            minst = stmt.search_one("min-elements")
            if minst:
                minel = minst.arg
            else:
                minel = "0"
        if maxel is None:
            maxst = stmt.search_one("max-elements")
            if maxst:
                maxel = maxst.arg
        return (minel, maxel)

    def lookup_expand(self, stmt, names):
        """Find schema nodes under `stmt`, also in used groupings.

        `names` is a list with qualified names of the schema nodes to
        look up. All 'uses'/'grouping' pairs between `stmt` and found
        schema nodes are marked for expansion.
        """
        if not names: return []
        todo = [stmt]
        while todo:
            pst = todo.pop()
            for sub in pst.substmts:
                if sub.keyword in self.schema_nodes:
                    qname = self.qname(sub)
                    if qname in names:
                        names.remove(qname)
                        par = sub.parent
                        while hasattr(par,"d_ref"): # par must be grouping
                            par.d_ref.d_expand = True
                            par = par.d_ref.parent
                        if not names: return [] # all found
                elif sub.keyword == "uses":
                    g = sub.i_grouping
                    g.d_ref = sub
                    todo.append(g)
        return names

    def type_with_ranges(self, tchain, p_elem, rangekw, gen_data):
        """Handle types with 'range' or 'length' restrictions.

        `tchain` is the chain of type definitions from which the
        ranges may need to be extracted. `rangekw` is the statement
        keyword determining the range type (either 'range' or
        'length'). `gen_data` is a function that generates the
        output schema node (a RELAX NG <data> pattern).
        """
        ranges = self.get_ranges(tchain, rangekw)
        if not ranges: return p_elem.subnode(gen_data())
        if len(ranges) > 1:
            p_elem = SchemaNode.choice(p_elem)
            p_elem.occur = 2
        for r in ranges:
            d_elem = gen_data()
            for p in self.range_params(r, rangekw):
                d_elem.subnode(p)
            p_elem.subnode(d_elem)

    def get_ranges(self, tchain, kw):
        """Return list of ranges defined in `tchain`.

        `kw` is the statement keyword determining the type of the
        range, i.e. 'range' or 'length'. `tchain` is the chain of type
        definitions from which the resulting range is obtained.

        The returned value is a list of tuples containing the segments
        of the resulting range.
        """
        (lo, hi) = ("min", "max")
        ran = None
        for t in tchain:
            rstmt = t.search_one(kw)
            if rstmt is None: continue
            parts = [ p.strip() for p in rstmt.arg.split("|") ]
            ran = [ [ i.strip() for i in p.split("..") ] for p in parts ]
            if ran[0][0] != 'min': lo = ran[0][0]
            if ran[-1][-1] != 'max': hi = ran[-1][-1]
        if ran is None: return None
        if len(ran) == 1:
            return [(lo, hi)]
        else:
            return [(lo, ran[0][-1])] + ran[1:-1] + [(ran[-1][0], hi)]

    def range_params(self, ran, kw):
        """Return list of <param>s corresponding to range `ran`.

        `kw` is the statement keyword determining the type of the
        range, i.e. 'range' or 'length'. `ran` is the internal
        representation of a range as constructed by the `get_ranges`
        method.
        """
        if kw == "length":
            if ran[0][0] != "m" and (len(ran) == 1 or ran[0] == ran[1]):
                elem = SchemaNode("param").set_attr("name","length")
                elem.text = ran[0]
                return [elem]
            min_ = SchemaNode("param").set_attr("name","minLength")
            max_ = SchemaNode("param").set_attr("name","maxLength")
        else:
            if len(ran) == 1: ran *= 2 # duplicating the value
            min_ = SchemaNode("param").set_attr("name","minInclusive")
            max_ = SchemaNode("param").set_attr("name","maxInclusive")
        res = []
        if ran[0][0] != "m":
            elem = min_
            elem.text = ran[0]
            res.append(elem)
        if ran[1][0] != "m":
            elem = max_
            elem.text = ran[1]
            res.append(elem)
        return res

    def handle_stmt(self, stmt, p_elem, pset={}):
        """
        Run handler method for statement `stmt`.

        `p_elem` is the parent node in the output schema. `pset` is
        the current "patch set" - a dictionary with keys being QNames
        of schema nodes at the current level of hierarchy for which
        (or descendants thereof) any pending patches exist. The values
        are instances of the Patch class.

        All handler methods are defined below and must have the same
        arguments as this method. They should create the output schema
        fragment corresponding to `stmt`, apply all patches from
        `pset` belonging to `stmt`, insert the fragment under `p_elem`
        and perform all side effects as necessary.
        """
        if self.debug > 0:
            sys.stderr.write("Handling '%s %s'\n" %
                             (util.keyword_to_str(stmt.raw_keyword), stmt.arg))
        try:
            method = self.stmt_handler[stmt.keyword]
        except KeyError:
            if isinstance(stmt.keyword, tuple): # extension
                self.handle_extension(stmt, p_elem)
                return
            else:
                raise error.EmitError(
                    "Unknown keyword %s - this should not happen.\n"
                    % stmt.keyword)

        method(stmt, p_elem, pset)

    def handle_substmts(self, stmt, p_elem, pset={}):
        """Handle all substatements of `stmt`."""
        for sub in stmt.substmts:
            self.handle_stmt(sub, p_elem, pset)

    # Handlers for YANG statements

    def noop(self, stmt, p_elem, pset=''):
        """`stmt` is not handled in the regular way."""
        pass

    def anyxml_stmt(self, stmt, p_elem, pset):
        self.has_anyxml = True
        elem = SchemaNode.element(self.qname(stmt), p_elem)
        SchemaNode("ref", elem).set_attr("name", "__anyxml__")
        refd = self.process_patches(pset, stmt, elem)[0]
        if p_elem.name == "choice":
            elem.occur = 3
        elif refd["mandatory"] or stmt.search_one("mandatory", "true"):
            elem.occur = 2
            self.propagate_occur(p_elem, 2)
        self.handle_substmts(stmt, elem)

    def nma_attribute(self, stmt, p_elem, pset=None):
        """Map `stmt` to a NETMOD-specific attribute.

        The name of the attribute is the same as the 'keyword' of
        `stmt`.
        """
        att = "nma:" + stmt.keyword
        if att not in p_elem.attr:
            p_elem.attr[att] = stmt.arg

    def case_stmt(self, stmt, p_elem, pset):
        celem = SchemaNode.case(p_elem)
        if p_elem.default_case != stmt.arg:
            celem.occur = 3
        refd, augs, new_pset = self.process_patches(pset, stmt, celem)
        left = self.lookup_expand(stmt, new_pset.keys())
        for a in augs:
            left = self.lookup_expand(a, left)
        self.handle_substmts(stmt, celem, new_pset)
        self.apply_augments(augs, celem, new_pset)

    def choice_stmt(self, stmt, p_elem, pset):
        chelem = SchemaNode.choice(p_elem)
        refd, augs, new_pset = self.process_patches(pset, stmt, chelem)
        left = self.lookup_expand(stmt, new_pset.keys())
        for a in augs:
            left = self.lookup_expand(a, left)
        if refd["mandatory"] or stmt.search_one("mandatory", "true"):
            chelem.attr["nma:mandatory"] = stmt.arg
            self.propagate_occur(chelem, 2)
        else:
            defv = self.get_default(stmt, refd)
            if defv is not None:
                chelem.default_case = defv
            else:
                chelem.occur = 3
        self.handle_substmts(stmt, chelem, new_pset)
        self.apply_augments(augs, chelem, new_pset)
        
    def container_stmt(self, stmt, p_elem, pset):
        celem = SchemaNode.element(self.qname(stmt), p_elem)
        refd, augs, new_pset = self.process_patches(pset, stmt, celem)
        left = self.lookup_expand(stmt, new_pset.keys())
        for a in augs:
            left = self.lookup_expand(a, left)
        if (p_elem.name == "choice" and p_elem.default_case != stmt.arg
            or refd["presence"] or stmt.search_one("presence")):
            celem.occur = 3
        self.handle_substmts(stmt, celem, new_pset)
        self.apply_augments(augs, celem, new_pset)
        if not celem.children: SchemaNode("empty", celem)

    def description_stmt(self, stmt, p_elem, pset):
        # ignore imported and top-level descriptions + desc. of enum
        if (self.a_uri in self.namespaces and
            stmt.i_module == self.module != stmt.parent and
            stmt.parent.keyword != "enum"):
            self.insert_doc(p_elem, stmt.arg)

    def enum_stmt(self, stmt, p_elem, pset):
        elem = SchemaNode("value", p_elem, stmt.arg)
        for sub in stmt.search("status"):
            self.handle_stmt(sub, elem)

    def if_feature_stmt(self, stmt, p_elem, pset):
        feat = stmt.i_feature
        module = self.main_module(feat)
        try:
            if feat.arg not in module.i_active_features:
                p_elem.subnode(SchemaNode("notAllowed"))
        except TypeError:  # slot i_active_features missing
            self.add_namespace(module)
            p_elem.attr["nma:if-feature"] = \
                self.module_prefixes[module.arg] + ":" + feat.arg

    def include_stmt(self, stmt, p_elem, pset):
        if stmt.parent.keyword == "module":
            subm = self.module.i_ctx.get_module(stmt.arg)
            self.handle_substmts(subm, p_elem, pset)

    def leaf_stmt(self, stmt, p_elem, pset):
        qname = self.qname(stmt)
        elem = SchemaNode.element(qname)
        if p_elem.name == "_list_" and qname in p_elem.keys:
            p_elem.keymap[qname] = elem
            elem.occur = 2
        else:
            p_elem.subnode(elem)
        refd = self.process_patches(pset, stmt, elem)[0]
        if p_elem.name == "choice":
            if p_elem.default_case != stmt.arg:
                elem.occur = 3
        elif refd["mandatory"] or stmt.search_one("mandatory", "true"):
            self.propagate_occur(elem, 2)
        if elem.occur == 0:
            defv = self.get_default(stmt, refd)
            if defv is not None:
                elem.default = defv
                self.propagate_occur(elem, 1)
        self.handle_substmts(stmt, elem)

    def leaf_list_stmt(self, stmt, p_elem, pset):
        lelem = SchemaNode.leaf_list(self.qname(stmt), p_elem)
        lelem.attr["nma:leaf-list"] = "true"
        refd = self.process_patches(pset, stmt, lelem)[0]
        lelem.minEl, lelem.maxEl = self.get_minmax(stmt, refd)
        if int(lelem.minEl) > 0: self.propagate_occur(p_elem, 2)
        self.handle_substmts(stmt, lelem)

    def list_stmt(self, stmt, p_elem, pset):
        lelem = SchemaNode.list(self.qname(stmt), p_elem)
        keyst = stmt.search_one("key")
        if keyst: lelem.keys = [self.add_prefix(k, stmt)
                                for k in keyst.arg.split()]
        refd, augs, new_pset = self.process_patches(pset, stmt, lelem)
        left = self.lookup_expand(stmt, new_pset.keys() + lelem.keys)
        for a in augs:
            left = self.lookup_expand(a, left)
        lelem.minEl, lelem.maxEl = self.get_minmax(stmt, refd)
        if int(lelem.minEl) > 0: self.propagate_occur(p_elem, 2)
        self.handle_substmts(stmt, lelem, new_pset)
        self.apply_augments(augs, lelem, new_pset)
        if not lelem.children: SchemaNode("empty", lelem)

    def must_stmt(self, stmt, p_elem, pset):
        mel = SchemaNode("nma:must", p_elem)
        mel.attr["assert"] = self.yang_to_xpath(stmt.arg)
        em = stmt.search_one("error-message")
        if em:
            SchemaNode("nma:error-message", mel, em.arg)
        eat = stmt.search_one("error-app-tag")
        if eat:
            SchemaNode("nma:error-app-tag", mel, eat.arg)

    def notification_stmt(self, stmt, p_elem, pset):
        notel = SchemaNode("nma:notification", self.notifications)
        notel.occur = 2
        elem = SchemaNode.element(self.qname(stmt), notel,
                                  interleave=True, occur=2)
        augs, new_pset = self.process_patches(pset, stmt, elem)[1:]
        self.handle_substmts(stmt, elem, new_pset)
        self.apply_augments(augs, elem, new_pset)

    def reference_stmt(self, stmt, p_elem, pset):
        # ignore imported and top-level descriptions + desc. of enum
        if (self.a_uri in self.namespaces and
            stmt.i_module == self.module != stmt.parent and
            stmt.parent.keyword != "enum"):
            self.insert_doc(p_elem, "See: " + stmt.arg)

    def rpc_stmt(self, stmt, p_elem, pset):
        rpcel = SchemaNode("nma:rpc", self.rpcs)
        r_pset = self.process_patches(pset, stmt, rpcel)[2]
        inpel = SchemaNode("nma:input", rpcel)
        elem = SchemaNode.element(self.qname(stmt), inpel, occur=2)
        augs, pset = self.process_patches(r_pset,stmt,elem,"input")[1:]
        inst = stmt.search_one("input")
        if inst:
            self.handle_substmts(inst, elem, pset)
        else:
            SchemaNode("empty", elem)
        self.apply_augments(augs, elem, pset)
        augs, pset = self.process_patches(r_pset,stmt,None,"output")[1:]
        oust = stmt.search_one("output")
        if oust or augs:
            outel = SchemaNode("nma:output", rpcel)
            outel.occur = 2
            if oust: self.handle_substmts(oust, outel, pset)
            self.apply_augments(augs, outel, pset)
        self.handle_substmts(stmt, rpcel, r_pset)

    def type_stmt(self, stmt, p_elem, pset):
        """Handle ``type`` statement.

        Built-in types are handled by one of the specific type
        callback methods defined below.
        """
        typedef = stmt.i_typedef
        if typedef and not stmt.i_is_derived: # just ref
            uname, dic = self.unique_def_name(typedef)
            if uname not in dic:
                self.install_def(uname, typedef, dic)
            SchemaNode("ref", p_elem).set_attr("name", uname)
            defst = typedef.search_one("default")
            if defst:
                dic[uname].default = defst.arg
                occur = 1
            else:
                occur = dic[uname].occur
            if occur > 0: self.propagate_occur(p_elem, occur)
            return
        chain = [stmt]
        tdefault = None
        while typedef:
            type_ = typedef.search_one("type")
            chain.insert(0, type_)
            if tdefault is None:
                tdef = typedef.search_one("default")
                if tdef:
                    tdefault = tdef.arg
            typedef = type_.i_typedef
        if tdefault and p_elem.occur == 0:
            p_elem.default = tdefault
            self.propagate_occur(p_elem, 1)
        self.type_handler[chain[0].arg](chain, p_elem)

    def unique_stmt(self, stmt, p_elem, pset):
        def addpref(nid):
            return "/".join([self.add_prefix(c, stmt)
                             for c in nid.split("/")])
        p_elem.attr["nma:unique"] = " ".join(
            [addpref(nid) for nid in stmt.arg.split()])

    def uses_stmt(self, stmt, p_elem, pset):
        expand = False
        grp = stmt.i_grouping
        for sub in stmt.substmts:
            if sub.keyword in ("refine", "augment"):
                expand = True
                self.add_patch(pset, sub)
        if expand:
            self.lookup_expand(grp, pset.keys())
        elif len(self.prefix_stack) <= 1 and not(hasattr(stmt,"d_expand")):
            uname, dic = self.unique_def_name(stmt.i_grouping,
                                              not(p_elem.interleave))
            gname = "_" + uname
            if uname not in dic:
                self.install_def(gname, stmt.i_grouping, dic,
                                 p_elem.interleave)
            elem = SchemaNode("ref", p_elem).set_attr("name", gname)
            occur = dic[gname].occur
            if occur > 0: self.propagate_occur(p_elem, occur)
            self.handle_substmts(stmt, elem)
            return
        self.handle_substmts(grp, p_elem, pset)

    def when_stmt(self, stmt, p_elem, pset=None):
        p_elem.attr["nma:when"] = self.yang_to_xpath(stmt.arg)

    def yang_version_stmt(self, stmt, p_elem, pset):
        if float(stmt.arg) != self.YANG_version:
            raise error.EmitError("Unsupported YANG version: %s" % stmt.arg)

    # Handlers for YANG types

    def binary_type(self, tchain, p_elem):
        def gen_data():
            return SchemaNode("data").set_attr("type", "base64Binary")
        self.type_with_ranges(tchain, p_elem, "length", gen_data)

    def bits_type(self, tchain, p_elem):
        elem = SchemaNode("list", p_elem)
        zom = SchemaNode("zeroOrMore", elem)
        choi = SchemaNode.choice(zom, occur=2)
        for bit in tchain[0].search("bit"):
            optel = SchemaNode("optional", choi)
            SchemaNode("value", optel, bit.arg)

    def boolean_type(self, tchain, p_elem):
        elem = SchemaNode.choice(p_elem, occur=2)
        SchemaNode("value", elem, "true")
        SchemaNode("value", elem, "false")

    def choice_type(self, tchain, p_elem):
        """Handle ``enumeration`` and ``union`` types."""
        elem = SchemaNode.choice(p_elem, occur=2)
        self.handle_substmts(tchain[0], elem)

    def empty_type(self, tchain, p_elem):
        SchemaNode("empty", p_elem)

    def identityref_type(self, tchain, p_elem):
        bid = tchain[0].search_one("base").i_identity
        module = self.main_module(bid)
        qid = self.module_prefixes[module.arg] + ":" + bid.arg
        self.add_identity(qid)
        SchemaNode("ref", p_elem).set_attr("name",
                                           "__" + qid.replace(":","_"))

    def instance_identifier_type(self, tchain, p_elem):
        SchemaNode("data", p_elem).set_attr("type", "string")
        ii = SchemaNode("nma:instance-identifier", p_elem)
        rinst = tchain[0].search_one("require-instance")
        if rinst: ii.attr["require-instance"] = rinst.arg

    def leafref_type(self, tchain, p_elem):
        typ = tchain[0]
        occur = p_elem.occur
        pathstr = typ.parent.i_leafref.i_expanded_path
        p_elem.attr["nma:leafref"] = self.yang_to_xpath(pathstr)
        while type(typ.i_type_spec) == types.PathTypeSpec:
            typ = typ.i_type_spec.i_target_node.search_one("type")
        self.handle_stmt(typ, p_elem)
        if occur == 0: p_elem.occur = 0

    def mapped_type(self, tchain, p_elem):
        """Handle types that are simply mapped to RELAX NG."""
        SchemaNode("data", p_elem).set_attr("type",
                                            self.datatype_map[tchain[0].arg])

    def numeric_type(self, tchain, p_elem):
        """Handle numeric types."""
        typ = tchain[0].arg
        def gen_data():
            elem = SchemaNode("data").set_attr("type", self.datatype_map[typ])
            if typ == "decimal64":
                fd = tchain[0].search_one("fraction-digits").arg
                SchemaNode("param",elem,"19").set_attr("name","totalDigits")
                SchemaNode("param",elem,fd).set_attr("name","fractionDigits")
            return elem
        self.type_with_ranges(tchain, p_elem, "range", gen_data)

    def string_type(self, tchain, p_elem):
        pels = []
        for t in tchain:
            for pst in t.search("pattern"):
                pels.append(SchemaNode("param",
                                       text=pst.arg).set_attr("name","pattern"))
        def get_data():
            elem = SchemaNode("data").set_attr("type", "string")
            for p in pels: elem.subnode(p)
            return elem
        self.type_with_ranges(tchain, p_elem, "length", get_data)