10.0.0.21 Git - asn2quickder/blob - asn1ate/sema.py

   1 # Copyright (c) 2013, Schneider Electric Buildings AB
   2 # All rights reserved.
   3 #
   4 # Redistribution and use in source and binary forms, with or without
   5 # modification, are permitted provided that the following conditions are met:
   6 #     * Redistributions of source code must retain the above copyright
   7 #       notice, this list of conditions and the following disclaimer.
   8 #     * Redistributions in binary form must reproduce the above copyright
   9 #       notice, this list of conditions and the following disclaimer in the
  10 #       documentation and/or other materials provided with the distribution.
  11 #     * Neither the name of Schneider Electric Buildings AB nor the
  12 #       names of contributors may be used to endorse or promote products
  13 #       derived from this software without specific prior written permission.
  14 #
  15 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
  16 # ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  17 # WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  18 # DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
  19 # ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  20 # (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  21 # LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  22 # ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  24 # SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25
  26 from asn1ate import parser
  27
  28
  29 def build_semantic_model(parse_result):
  30     """ Build a semantic model of the ASN.1 definition
  31     from a syntax tree generated by asn1ate.parser.
  32     """
  33     root = []
  34     for token in parse_result:
  35         _assert_annotated_token(token)
  36         root.append(_create_sema_node(token))
  37
  38     return root
  39
  40
  41 def topological_sort(assignments):
  42     """ Algorithm adapted from:
  43     http://en.wikipedia.org/wiki/Topological_sorting.
  44
  45     Assumes assignments is an iterable of items with two methods:
  46     - reference_name() -- returns the reference name of the assignment
  47     - references() -- returns an iterable of reference names
  48     upon which the assignment depends.
  49     """
  50     graph = dict((a.reference_name(), set(a.references())) for a in assignments)
  51
  52     def has_predecessor(node):
  53         for predecessor in graph.keys():
  54             if node in graph[predecessor]:
  55                 return True
  56
  57         return False
  58
  59     # Build a topological order of reference names
  60     topological_order = []
  61     roots = [name for name in graph.keys() if not has_predecessor(name)]
  62
  63     while roots:
  64         root = roots.pop()
  65
  66         # Remove the current node from the graph
  67         # and collect all new roots (the nodes that
  68         # were previously only referenced from n)
  69         successors = graph.pop(root, set())
  70         roots.extend(successor for successor in successors if not has_predecessor(successor))
  71
  72         topological_order.insert(0, root)
  73
  74     if graph:
  75         raise Exception('Can\'t sort cyclic references: %s' % graph)
  76
  77     # Sort the actual assignments based on the topological order
  78     return sorted(assignments, key=lambda a: topological_order.index(a.reference_name()))
  79
  80
  81 """
  82 Sema nodes
  83
  84 Concepts in the ASN.1 specification are mirrored here as a simple object model.
  85
  86 Class and member names typically follow the ASN.1 terminology, but there are
  87 some concepts captured which are not expressed in the spec.
  88
  89 Most notably, we build a dependency graph of all types and values in a module,
  90 to allow code generators to build code in dependency order.
  91
  92 All nodes that may be referenced (e.g. types and values) must have a
  93 method called ``reference_name``.
  94
  95 All nodes that may reference other types (e.g. assignments, component types)
  96 must have a method called ``references`` returning the names of all referenced
  97 nodes.
  98
  99 Typically, if you have a ``reference_name``, you must also have a ``references``,
 100 but not necessarily the other way around.
 101 """
 102
 103 class Module(object):
 104     def __init__(self, elements):
 105         module_reference, _, _, _, module_body, _ = elements
 106         _assert_annotated_token(module_reference)
 107         _assert_annotated_token(module_body)
 108
 109         self.name = module_reference.elements[0]
 110         self.assignments = [_create_sema_node(token) for token in module_body.elements]
 111         self._user_types = {}
 112
 113     def user_types(self):
 114         if not self._user_types:
 115             # Index all type assignments by name
 116             for user_defined in self.assignments:
 117                 self._user_types[user_defined.type_name] = user_defined.type_decl
 118
 119         return self._user_types
 120
 121     def resolve_type_decl(self, type_decl):
 122         """ Recursively resolve user-defined types to their
 123         built-in declaration.
 124         """
 125         user_types = self.user_types()
 126
 127         if isinstance(type_decl, UserDefinedType):
 128             return self.resolve_type_decl(user_types[type_decl.type_name])
 129         else:
 130             return type_decl
 131
 132
 133     def __str__(self):
 134         return '%s DEFINITIONS ::=\n' % self.name \
 135             + 'BEGIN\n' \
 136             + '\n'.join(map(str, self.assignments)) + '\n' \
 137             + 'END\n'
 138
 139     __repr__ = __str__
 140
 141
 142 class TypeAssignment(object):
 143     def __init__(self, elements):
 144         assert(len(elements) == 3)
 145         type_name, _, type_decl = elements
 146         self.type_name = type_name
 147         self.type_decl = _create_sema_node(type_decl)
 148
 149     def reference_name(self):
 150         return self.type_name
 151
 152     def references(self):
 153         refs = self.type_decl.references()
 154
 155         # Remove any circular references
 156         refs = [ref for ref in refs if ref != self.type_name]
 157
 158         return refs
 159
 160     def __str__(self):
 161         return '%s ::= %s' % (self.type_name, self.type_decl)
 162
 163     __repr__ = __str__
 164
 165
 166 class ValueAssignment(object):
 167     def __init__(self, elements):
 168         value_name, type_name, _, value = elements
 169         self.value_name = ValueReference(value_name.elements) # First token is always a valuereference
 170         self.type_decl = _create_sema_node(type_name)
 171
 172         if isinstance(value, parser.AnnotatedToken):
 173             self.value = _create_sema_node(value)
 174         else:
 175             self.value = value
 176
 177     def reference_name(self):
 178         return self.value_name.reference_name()
 179
 180     def references(self):
 181         refs = [self.type_decl.reference_name()]
 182         if isinstance(self.value, ValueReference):
 183             refs.append(self.value.reference_name())
 184         else:
 185             # It's a literal, and they don't play into declaration order.
 186             pass
 187
 188         # Remove any circular references
 189         refs = [ref for ref in refs if ref != self.value_name]
 190
 191         return refs
 192
 193     def __str__(self):
 194         return '%s %s ::= %s' % (self.value_name, self.type_decl, self.value)
 195
 196     __repr__ = __str__
 197
 198
 199 class ValueReference(object):
 200     def __init__(self, elements):
 201         self.name = elements[0]
 202
 203     def reference_name(self):
 204         return self.name
 205
 206     def references(self):
 207         return []
 208
 209     def __str__(self):
 210         return self.name
 211
 212     __repr__ = __str__
 213
 214
 215 class ConstructedType(object):
 216     def __init__(self, elements):
 217         type_name, component_tokens = elements
 218         self.type_name = type_name
 219         self.components = [_create_sema_node(token) for token in component_tokens]
 220
 221     def references(self):
 222         references = []
 223         for component in self.components:
 224             references.extend(component.references())
 225         return references
 226
 227     def __str__(self):
 228         component_type_list = ', '.join(map(str, self.components))
 229         return '%s { %s }' % (self.type_name, component_type_list)
 230
 231     __repr__ = __str__
 232
 233
 234 class ChoiceType(ConstructedType):
 235     def __init__(self, elements):
 236         super(ChoiceType, self).__init__(elements)
 237
 238
 239 class SequenceType(ConstructedType):
 240     def __init__(self, elements):
 241         super(SequenceType, self).__init__(elements)
 242
 243
 244 class SequenceOfType(object):
 245     def __init__(self, elements):
 246         type_name, type_token = elements
 247         self.type_name = type_name
 248         self.type_decl = _create_sema_node(type_token)
 249
 250     def references(self):
 251         return self.type_decl.references()
 252
 253     def __str__(self):
 254         return '%s %s' % (self.type_name, self.type_decl)
 255
 256     __repr__ = __str__
 257
 258
 259 class SetOfType(object):
 260     def __init__(self, elements):
 261         type_name, type_token = elements
 262         self.type_name = type_name
 263         self.type_decl = _create_sema_node(type_token)
 264
 265     def references(self):
 266         return self.type_decl.references()
 267
 268     def __str__(self):
 269         return '%s %s' % (self.type_name, self.type_decl)
 270
 271     __repr__ = __str__
 272
 273
 274 class TaggedType(object):
 275     def __init__(self, elements):
 276         self.class_name = None
 277         self.class_number = None
 278         self.implicit = False
 279
 280         tag_token = elements[0]
 281         if type(elements[1]) is parser.AnnotatedToken:
 282             type_token = elements[1]
 283         else:
 284             self.implicit = elements[1] == 'IMPLICIT'
 285             type_token = elements[2]
 286
 287         for tag_element in tag_token.elements:
 288             if tag_element.ty == 'TagClassNumber':
 289                 self.class_number = tag_element.elements[0]
 290             elif tag_element.ty == 'TagClass':
 291                 self.class_name = tag_element.elements[0]
 292             else:
 293                 assert False, 'Unknown tag element: %s' % tag_element
 294
 295         self.type_decl = _create_sema_node(type_token)
 296
 297     @property
 298     def type_name(self):
 299         return self.type_decl.type_name
 300
 301     def reference_name(self):
 302         return self.type_decl.type_name
 303
 304     def references(self):
 305         return self.type_decl.references()
 306
 307     def __str__(self):
 308         class_spec = []
 309         if self.class_name:
 310             class_spec.append(self.class_name)
 311         class_spec.append(self.class_number)
 312
 313         result = '[%s] ' % ' '.join(class_spec)
 314         if self.implicit:
 315             result += 'IMPLICIT '
 316
 317         result += str(self.type_decl)
 318
 319         return result
 320
 321     __repr__ = __str__
 322
 323
 324 class SimpleType(object):
 325     def __init__(self, elements):
 326         self.constraint = None
 327         self.type_name = elements[0]
 328         if len(elements) > 1 and elements[1].ty == 'Constraint':
 329             self.constraint = Constraint(elements[1].elements)
 330
 331     def reference_name(self):
 332         return self.type_name
 333
 334     def references(self):
 335         refs = [self.type_name]
 336         if self.constraint:
 337             refs.extend(self.constraint.references())
 338
 339         return refs
 340
 341     def __str__(self):
 342         if self.constraint is None:
 343             return self.type_name
 344
 345         return '%s %s' % (self.type_name, self.constraint)
 346
 347     __repr__ = __str__
 348
 349
 350 class UserDefinedType(object):
 351     def __init__(self, elements):
 352         self.type_name = elements[0]
 353
 354     def references(self):
 355         return [self.type_name]
 356
 357     def __str__(self):
 358         return self.type_name
 359
 360     __repr__ = __str__
 361
 362
 363 class Constraint(object):
 364     def __init__(self, elements):
 365         min_value, max_value = elements
 366
 367         self.min_value = _maybe_create_sema_node(min_value)
 368         self.max_value = _maybe_create_sema_node(max_value)
 369
 370     def references(self):
 371         refs = []
 372         if isinstance(self.min_value, ValueReference):
 373             refs.append(self.min_value.reference_name())
 374
 375         if isinstance(self.max_value, ValueReference):
 376             refs.append(self.max_value.reference_name())
 377
 378         return refs
 379
 380     def __str__(self):
 381         return '(%s..%s)' % (self.min_value, self.max_value)
 382
 383     __repr__ = __str__
 384
 385
 386 class ComponentType(object):
 387     def __init__(self, elements):
 388         self.identifier = None
 389         self.type_decl = None
 390         self.default_value = None
 391         self.optional = False
 392         self.components_of_type = None
 393
 394         def crack_named_type(token):
 395             named_type = NamedType(token)
 396             self.identifier = named_type.identifier
 397             self.type_decl = named_type.type_decl
 398
 399         first_token = elements[0]
 400         if first_token.ty == 'NamedType':
 401             crack_named_type(first_token.elements)
 402         elif first_token.ty == 'ComponentTypeOptional':
 403             crack_named_type(first_token.elements[0].elements)
 404             self.optional = True
 405         elif first_token.ty == 'ComponentTypeDefault':
 406             crack_named_type(first_token.elements[0].elements)
 407             self.default_value = _maybe_create_sema_node(first_token.elements[1])
 408         elif first_token.ty == 'ComponentTypeComponentsOf':
 409             self.components_of_type = _create_sema_node(first_token.elements[0])
 410         else:
 411             assert False, 'Unknown component type %s' % first_token
 412
 413     def references(self):
 414         if self.components_of_type:
 415             return [self.components_of_type.type_name]
 416
 417         refs = [self.type_decl.type_name]
 418         refs.extend(self.type_decl.references())
 419
 420         if self.default_value is not None:
 421             refs.append(str(self.default_value))
 422
 423         return refs
 424
 425     def __str__(self):
 426         if self.components_of_type:
 427             return 'COMPONENTS OF %s' % self.components_of_type
 428
 429         result = '%s %s' % (self.identifier, self.type_decl)
 430         if self.optional:
 431             result += ' OPTIONAL'
 432         elif self.default_value is not None:
 433             result += ' DEFAULT %s' % self.default_value
 434
 435         return result
 436
 437     __repr__ = __str__
 438
 439
 440 class NamedType(object):
 441     def __init__(self, elements):
 442         first_token = elements[0]
 443         if first_token.ty == 'Type':
 444             # EXT: unnamed member
 445             type_token = first_token
 446             self.identifier = _get_next_unnamed()
 447         elif first_token.ty == 'Identifier':
 448             # an identifier
 449             self.identifier = first_token.elements[0]
 450             type_token = elements[1]
 451
 452         self.type_decl = _create_sema_node(type_token)
 453
 454     def references(self):
 455         return self.type_decl.references()
 456
 457     def __str__(self):
 458         return '%s %s' % (self.identifier, self.type_decl)
 459
 460     __repr__ = __str__
 461
 462
 463 class ValueListType(object):
 464     def __init__(self, elements):
 465         self.type_name = elements[0]
 466         if len(elements) > 1:
 467             self.named_values = [_create_sema_node(token) for token in elements[1]]
 468         else:
 469             self.named_values = None
 470
 471     def references(self):
 472         # TODO: Value references
 473         return []
 474
 475     def __str__(self):
 476         if self.named_values:
 477             named_value_list = ', '.join(map(str, self.named_values))
 478             return '%s { %s }' % (self.type_name, named_value_list)
 479         else:
 480             return '%s' % self.type_name
 481
 482     __repr__ = __str__
 483
 484
 485 class BitStringType(object):
 486     def __init__(self, elements):
 487         self.type_name = elements[0]
 488         if len(elements) > 1:
 489             self.named_bits = [_create_sema_node(token) for token in elements[1]]
 490         else:
 491             self.named_bits = None
 492
 493     def references(self):
 494         # TODO: Value references
 495         return []
 496
 497     def __str__(self):
 498         if self.named_bits:
 499             named_bit_list = ', '.join(map(str, self.named_bits))
 500             return '%s { %s }' % (self.type_name, named_bit_list)
 501         else:
 502             return '%s' % self.type_name
 503
 504     __repr__ = __str__
 505
 506
 507 class NamedValue(object):
 508     def __init__(self, elements):
 509         identifier_token, value_token = elements
 510         self.identifier = identifier_token.elements[0]
 511         self.value = value_token.elements[0]
 512
 513     def references(self):
 514         # TODO: This appears to never be called. Investigate.
 515         return []
 516
 517     def __str__(self):
 518         return '%s (%s)' % (self.identifier, self.value)
 519
 520     __repr__ = __str__
 521
 522
 523 def _maybe_create_sema_node(token):
 524     if isinstance(token, parser.AnnotatedToken):
 525         return _create_sema_node(token)
 526     else:
 527         return token
 528
 529
 530 def _create_sema_node(token):
 531     _assert_annotated_token(token)
 532
 533     if token.ty == 'ModuleDefinition':
 534         return Module(token.elements)
 535     elif token.ty == 'TypeAssignment':
 536         return TypeAssignment(token.elements)
 537     elif token.ty == 'ValueAssignment':
 538         return ValueAssignment(token.elements)
 539     elif token.ty == 'ValueReference':
 540         return ValueReference(token.elements)
 541     elif token.ty == 'ComponentType':
 542         return ComponentType(token.elements)
 543     elif token.ty == 'NamedType':
 544         return NamedType(token.elements)
 545     elif token.ty == 'ValueListType':
 546         return ValueListType(token.elements)
 547     elif token.ty == 'BitStringType':
 548         return BitStringType(token.elements)
 549     elif token.ty == 'NamedValue':
 550         return NamedValue(token.elements)
 551     elif token.ty == 'Type':
 552         # Type tokens have a more specific type category
 553         # embedded as their first element
 554         return _create_sema_node(token.elements[0])
 555     elif token.ty == 'SimpleType':
 556         return SimpleType(token.elements)
 557     elif token.ty == 'ReferencedType':
 558         return UserDefinedType(token.elements)
 559     elif token.ty == 'TaggedType':
 560         return TaggedType(token.elements)
 561     elif token.ty == 'SequenceType':
 562         return SequenceType(token.elements)
 563     elif token.ty == 'ChoiceType':
 564         return ChoiceType(token.elements)
 565     elif token.ty == 'SequenceOfType':
 566         return SequenceOfType(token.elements)
 567     elif token.ty == 'SetOfType':
 568         return SetOfType(token.elements)
 569
 570     raise Exception('Unknown token type: %s' % token.ty)
 571
 572
 573 def _assert_annotated_token(obj):
 574     assert(type(obj) is parser.AnnotatedToken)
 575
 576
 577 # HACK: Generate unique names for unnamed members
 578 _unnamed_counter = 0
 579 def _get_next_unnamed():
 580     global _unnamed_counter
 581     _unnamed_counter += 1
 582     return 'unnamed%d' % _unnamed_counter