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 # Registered object identifier names
  82 REGISTERED_OID_NAMES = {
  83     'ccitt': 0,
  84     'iso': 1,
  85     'joint-iso-ccitt': 2,
  86     # ccitt
  87     'recommendation': 0,
  88     'question': 1,
  89     'administration': 2,
  90     'network-operator': 3,
  91     # iso
  92     'standard': 0,
  93     'registration-authority': 1,
  94     'member-body': 2,
  95     'identified-organization': 3,
  96     # joint-iso-ccitt
  97     'country': 16,
  98     'registration-procedures': 17
  99 }
 100
 101 """
 102 Sema nodes
 103
 104 Concepts in the ASN.1 specification are mirrored here as a simple object model.
 105
 106 Class and member names typically follow the ASN.1 terminology, but there are
 107 some concepts captured which are not expressed in the spec.
 108
 109 Most notably, we build a dependency graph of all types and values in a module,
 110 to allow code generators to build code in dependency order.
 111
 112 All nodes that may be referenced (type and value assignments) must have a
 113 method called ``reference_name``.
 114
 115 All nodes that may reference other types (e.g. assignments, component types)
 116 must have a method called ``references`` returning the names of all referenced
 117 nodes.
 118
 119 Typically, if you have a ``reference_name``, you must also have a ``references``,
 120 but not the other way around.
 121 """
 122
 123 class SemaNode(object):
 124     def children(self):
 125         raise NotImplementedError()
 126
 127
 128 class Module(object):
 129     def __init__(self, elements):
 130         self._user_types = {}
 131
 132         module_reference, _, _, _, _, module_body, _ = elements
 133         self.name = module_reference.elements[0]
 134
 135         if module_body.elements:
 136             _, assignments = module_body.elements
 137             self.assignments = [_create_sema_node(token) for token in assignments.elements]
 138         else:
 139             self.assignments = []
 140
 141     def user_types(self):
 142         if not self._user_types:
 143             # Index all type assignments by name
 144             type_assignments = [a for a in self.assignments if isinstance(a, TypeAssignment)]
 145             for user_defined in type_assignments:
 146                 self._user_types[user_defined.type_name] = user_defined.type_decl
 147
 148         return self._user_types
 149
 150     def resolve_type_decl(self, type_decl):
 151         """ Recursively resolve user-defined types to their
 152         built-in declaration.
 153         """
 154         user_types = self.user_types()
 155
 156         # Drill through Type, it acts as a container
 157         # for type + metadata like constraints.
 158         if isinstance(type_decl, Type):
 159             type_decl = type_decl.type_decl
 160
 161         if isinstance(type_decl, UserDefinedType):
 162             return self.resolve_type_decl(user_types[type_decl.type_name])
 163         else:
 164             return type_decl
 165
 166
 167     def __str__(self):
 168         return '%s DEFINITIONS ::=\n' % self.name \
 169             + 'BEGIN\n' \
 170             + '\n'.join(map(str, self.assignments)) + '\n' \
 171             + 'END\n'
 172
 173     __repr__ = __str__
 174
 175
 176 class TypeAssignment(object):
 177     def __init__(self, elements):
 178         assert(len(elements) == 3)
 179         type_name, _, type_decl = elements
 180         self.type_name = type_name
 181         self.type_decl = _create_sema_node(type_decl)
 182
 183     def reference_name(self):
 184         return self.type_name
 185
 186     def references(self):
 187         refs = self.type_decl.references()
 188
 189         # Remove any self-references
 190         refs = [ref for ref in refs if ref != self.type_name]
 191
 192         return refs
 193
 194     def __str__(self):
 195         return '%s ::= %s' % (self.type_name, self.type_decl)
 196
 197     __repr__ = __str__
 198
 199
 200 class ValueAssignment(object):
 201     def __init__(self, elements):
 202         value_name, type_name, _, value = elements
 203         self.value_name = ValueReference(value_name.elements) # First token is always a valuereference
 204         self.type_decl = _create_sema_node(type_name)
 205
 206         if isinstance(value, parser.AnnotatedToken):
 207             self.value = _create_sema_node(value)
 208         else:
 209             self.value = value
 210
 211     def reference_name(self):
 212         return self.value_name.reference_name()
 213
 214     def references(self):
 215         refs = [self.type_decl.reference_name()]
 216         if isinstance(self.value, ValueReference):
 217             refs.append(self.value.reference_name())
 218         elif isinstance(self.value, ObjectIdentifierValue):
 219             refs.extend(self.value.references())
 220         else:
 221             # It's a literal, and they don't play into declaration order.
 222             pass
 223
 224         # Remove any self-references
 225         refs = [ref for ref in refs if ref != self.value_name]
 226
 227         return refs
 228
 229     def __str__(self):
 230         return '%s %s ::= %s' % (self.value_name, self.type_decl, self.value)
 231
 232     __repr__ = __str__
 233
 234
 235 class ValueReference(object):
 236     def __init__(self, elements):
 237         self.name = elements[0]
 238
 239     def reference_name(self):
 240         return self.name
 241
 242     def references(self):
 243         return []
 244
 245     def __str__(self):
 246         return self.name
 247
 248     __repr__ = __str__
 249
 250
 251 class Type(object):
 252     """ A container for all types, contains
 253     additional metadata such as constraints.
 254     """
 255     def __init__(self, elements):
 256         self.type_decl = _create_sema_node(elements[0])
 257         if len(elements) == 2:
 258             assert elements[1].ty == 'Constraint'
 259             self.constraint = Constraint(elements[1].elements)
 260         else:
 261             self.constraint = None
 262
 263     @property
 264     def type_name(self):
 265         return self.type_decl.type_name
 266
 267     def reference_name(self):
 268         return self.type_decl.type_name
 269
 270     def references(self):
 271         if self.constraint:
 272             return self.constraint.references()
 273
 274         return []
 275
 276     def __str__(self):
 277         if self.constraint:
 278             return '%s %s' % (self.type_decl, self.constraint)
 279         else:
 280             return str(self.type_decl)
 281
 282     __repr__ = __str__
 283
 284
 285 class ConstructedType(object):
 286     """ Base type for SEQUENCE, SET and CHOICE. """
 287     def __init__(self, elements):
 288         type_name, component_tokens = elements
 289         self.type_name = type_name
 290         self.components = [_create_sema_node(token) for token in component_tokens]
 291
 292     def references(self):
 293         references = []
 294         for component in self.components:
 295             references.extend(component.references())
 296         return references
 297
 298     def __str__(self):
 299         component_type_list = ', '.join(map(str, self.components))
 300         return '%s { %s }' % (self.type_name, component_type_list)
 301
 302     __repr__ = __str__
 303
 304
 305 class ChoiceType(ConstructedType):
 306     def __init__(self, elements):
 307         super(ChoiceType, self).__init__(elements)
 308
 309
 310 class SequenceType(ConstructedType):
 311     def __init__(self, elements):
 312         super(SequenceType, self).__init__(elements)
 313
 314
 315 class SetType(ConstructedType):
 316     def __init__(self, elements):
 317         super(SetType, self).__init__(elements)
 318
 319
 320 class CollectionType(object):
 321     """ Base type for SET OF and SEQUENCE OF. """
 322     def __init__(self, kind, elements):
 323         self.kind = kind
 324         self.type_name = self.kind + ' OF'
 325
 326         if elements[0].ty == 'Type':
 327             self.size_constraint = None
 328             self.type_decl = _create_sema_node(elements[0])
 329         elif elements[0].ty == 'SizeConstraint':
 330             self.size_constraint = _create_sema_node(elements[0])
 331             self.type_decl = _create_sema_node(elements[1])
 332         else:
 333             assert False, 'Unknown form of %s OF declaration: %s' % (self.kind, elements)
 334
 335     def references(self):
 336         return self.type_decl.references()
 337
 338     def __str__(self):
 339         if self.size_constraint:
 340             return '%s %s OF %s' % (self.kind, self.size_constraint, self.type_decl)
 341         else:
 342             return '%s OF %s' % (self.kind, self.type_decl)
 343
 344     __repr__ = __str__
 345
 346
 347 class SequenceOfType(CollectionType):
 348     def __init__(self, elements):
 349         super(SequenceOfType, self).__init__('SEQUENCE', elements)
 350
 351
 352 class SetOfType(CollectionType):
 353     def __init__(self, elements):
 354         super(SetOfType, self).__init__('SET', elements)
 355
 356
 357 class TaggedType(object):
 358     def __init__(self, elements):
 359         self.class_name = None
 360         self.class_number = None
 361         self.implicit = False
 362
 363         tag_token = elements[0]
 364         if type(elements[1]) is parser.AnnotatedToken:
 365             type_token = elements[1]
 366         else:
 367             self.implicit = elements[1] == 'IMPLICIT'
 368             type_token = elements[2]
 369
 370         for tag_element in tag_token.elements:
 371             if tag_element.ty == 'TagClassNumber':
 372                 self.class_number = tag_element.elements[0]
 373             elif tag_element.ty == 'TagClass':
 374                 self.class_name = tag_element.elements[0]
 375             else:
 376                 assert False, 'Unknown tag element: %s' % tag_element
 377
 378         self.type_decl = _create_sema_node(type_token)
 379
 380     @property
 381     def type_name(self):
 382         return self.type_decl.type_name
 383
 384     def reference_name(self):
 385         return self.type_decl.type_name
 386
 387     def references(self):
 388         return self.type_decl.references()
 389
 390     def __str__(self):
 391         class_spec = []
 392         if self.class_name:
 393             class_spec.append(self.class_name)
 394         class_spec.append(self.class_number)
 395
 396         result = '[%s] ' % ' '.join(class_spec)
 397         if self.implicit:
 398             result += 'IMPLICIT '
 399
 400         result += str(self.type_decl)
 401
 402         return result
 403
 404     __repr__ = __str__
 405
 406
 407 class SimpleType(object):
 408     def __init__(self, elements):
 409         self.constraint = None
 410         self.type_name = elements[0]
 411         if len(elements) > 1 and elements[1].ty == 'Constraint':
 412             self.constraint = Constraint(elements[1].elements)
 413
 414     def reference_name(self):
 415         return self.type_name
 416
 417     def references(self):
 418         refs = [self.type_name]
 419         if self.constraint:
 420             refs.extend(self.constraint.references())
 421
 422         return refs
 423
 424     def __str__(self):
 425         if self.constraint is None:
 426             return self.type_name
 427
 428         return '%s %s' % (self.type_name, self.constraint)
 429
 430     __repr__ = __str__
 431
 432
 433 class UserDefinedType(object):
 434     def __init__(self, elements):
 435         self.type_name = elements[0]
 436
 437     def references(self):
 438         return [self.type_name]
 439
 440     def __str__(self):
 441         return self.type_name
 442
 443     __repr__ = __str__
 444
 445
 446 class Constraint(object):
 447     def __init__(self, elements):
 448         min_value, max_value = elements
 449
 450         self.min_value = _maybe_create_sema_node(min_value)
 451         self.max_value = _maybe_create_sema_node(max_value)
 452
 453     def references(self):
 454         refs = []
 455         if isinstance(self.min_value, ValueReference):
 456             refs.append(self.min_value.reference_name())
 457
 458         if isinstance(self.max_value, ValueReference):
 459             refs.append(self.max_value.reference_name())
 460
 461         return refs
 462
 463     def __str__(self):
 464         return '(%s..%s)' % (self.min_value, self.max_value)
 465
 466     __repr__ = __str__
 467
 468
 469 class SizeConstraint(Constraint):
 470     """ Size constraints have the same form as any value range constraints."""
 471     def __str__(self):
 472         return 'SIZE(%s..%s)' % (self.min_value, self.max_value)
 473
 474     __repr__ = __str__
 475
 476
 477 class ComponentType(object):
 478     def __init__(self, elements):
 479         self.identifier = None
 480         self.type_decl = None
 481         self.default_value = None
 482         self.optional = False
 483         self.components_of_type = None
 484
 485         def crack_named_type(token):
 486             named_type = NamedType(token)
 487             self.identifier = named_type.identifier
 488             self.type_decl = named_type.type_decl
 489
 490         first_token = elements[0]
 491         if first_token.ty == 'NamedType':
 492             crack_named_type(first_token.elements)
 493         elif first_token.ty == 'ComponentTypeOptional':
 494             crack_named_type(first_token.elements[0].elements)
 495             self.optional = True
 496         elif first_token.ty == 'ComponentTypeDefault':
 497             crack_named_type(first_token.elements[0].elements)
 498             self.default_value = _maybe_create_sema_node(first_token.elements[1])
 499         elif first_token.ty == 'ComponentTypeComponentsOf':
 500             self.components_of_type = _create_sema_node(first_token.elements[0])
 501         else:
 502             assert False, 'Unknown component type %s' % first_token
 503
 504     def references(self):
 505         if self.components_of_type:
 506             return [self.components_of_type.type_name]
 507
 508         refs = [self.type_decl.type_name]
 509         refs.extend(self.type_decl.references())
 510
 511         if self.default_value is not None:
 512             refs.append(str(self.default_value))
 513
 514         return refs
 515
 516     def __str__(self):
 517         if self.components_of_type:
 518             return 'COMPONENTS OF %s' % self.components_of_type
 519
 520         result = '%s %s' % (self.identifier, self.type_decl)
 521         if self.optional:
 522             result += ' OPTIONAL'
 523         elif self.default_value is not None:
 524             result += ' DEFAULT %s' % self.default_value
 525
 526         return result
 527
 528     __repr__ = __str__
 529
 530
 531 class NamedType(object):
 532     def __init__(self, elements):
 533         first_token = elements[0]
 534         if first_token.ty == 'Type':
 535             # EXT: unnamed member
 536             type_token = first_token
 537             self.identifier = _get_next_unnamed()
 538         elif first_token.ty == 'Identifier':
 539             # an identifier
 540             self.identifier = first_token.elements[0]
 541             type_token = elements[1]
 542
 543         self.type_decl = _create_sema_node(type_token)
 544
 545     def references(self):
 546         return self.type_decl.references()
 547
 548     def __str__(self):
 549         return '%s %s' % (self.identifier, self.type_decl)
 550
 551     __repr__ = __str__
 552
 553
 554 class ValueListType(object):
 555     def __init__(self, elements):
 556         self.type_name = elements[0]
 557         if len(elements) > 1:
 558             self.named_values = [_create_sema_node(token) for token in elements[1]]
 559         else:
 560             self.named_values = None
 561
 562     def references(self):
 563         # TODO: Value references
 564         return []
 565
 566     def __str__(self):
 567         if self.named_values:
 568             named_value_list = ', '.join(map(str, self.named_values))
 569             return '%s { %s }' % (self.type_name, named_value_list)
 570         else:
 571             return '%s' % self.type_name
 572
 573     __repr__ = __str__
 574
 575
 576 class BitStringType(object):
 577     def __init__(self, elements):
 578         self.type_name = elements[0]
 579         if len(elements) > 1:
 580             self.named_bits = [_create_sema_node(token) for token in elements[1]]
 581         else:
 582             self.named_bits = None
 583
 584     def references(self):
 585         # TODO: Value references
 586         return []
 587
 588     def __str__(self):
 589         if self.named_bits:
 590             named_bit_list = ', '.join(map(str, self.named_bits))
 591             return '%s { %s }' % (self.type_name, named_bit_list)
 592         else:
 593             return '%s' % self.type_name
 594
 595     __repr__ = __str__
 596
 597
 598 class NamedValue(object):
 599     def __init__(self, elements):
 600         identifier_token, value_token = elements
 601         self.identifier = identifier_token.elements[0]
 602         self.value = value_token.elements[0]
 603
 604     def references(self):
 605         # TODO: This appears to never be called. Investigate.
 606         return []
 607
 608     def __str__(self):
 609         return '%s (%s)' % (self.identifier, self.value)
 610
 611     __repr__ = __str__
 612
 613
 614 class ExtensionMarker(object):
 615     def __init__(self, elements):
 616         pass
 617
 618     def references(self):
 619         # TODO: This appears to never be called. Investigate.
 620         return []
 621
 622     def __str__(self):
 623         return '...'
 624
 625     __repr__ = __str__
 626
 627
 628 class NameForm(object):
 629     def __init__(self, elements):
 630         self.name = elements[0]
 631
 632     def references(self):
 633         return [self.name]
 634
 635     def __str__(self):
 636         return self.name
 637
 638     __repr__ = __str__
 639
 640
 641 class NumberForm(object):
 642     def __init__(self, elements):
 643         self.value = elements[0]
 644
 645     def references(self):
 646         return []
 647
 648     def __str__(self):
 649         return str(self.value)
 650
 651     __repr__ = __str__
 652
 653
 654 class NameAndNumberForm(object):
 655     def __init__(self, elements):
 656         # The first element is a NameForm containing only the
 657         # name, so unpack it into a string.
 658         self.name = elements[0].elements[0]
 659         self.number = _create_sema_node(elements[1])
 660
 661     def references(self):
 662         return [str(self.name), str(self.number)]
 663
 664     def __str__(self):
 665         return '%s(%s)' % (self.name, self.number)
 666
 667     __repr__ = __str__
 668
 669
 670 class ObjectIdentifierValue(object):
 671     def __init__(self, elements):
 672         self.components = [_create_sema_node(c) for c in elements]
 673
 674     def references(self):
 675         refs = []
 676         for component in self.components:
 677             if not isinstance(component, str):
 678                 refs.extend(component.references())
 679             else:
 680                 refs.append(component)
 681
 682         return refs
 683
 684     def __str__(self):
 685         return '{' + ' '.join(str(x) for x in self.components) + '}'
 686
 687     __repr__ = __str__
 688
 689
 690 def _maybe_create_sema_node(token):
 691     if isinstance(token, parser.AnnotatedToken):
 692         return _create_sema_node(token)
 693     else:
 694         return token
 695
 696
 697 def _create_sema_node(token):
 698     _assert_annotated_token(token)
 699
 700     if token.ty == 'ModuleDefinition':
 701         return Module(token.elements)
 702     elif token.ty == 'TypeAssignment':
 703         return TypeAssignment(token.elements)
 704     elif token.ty == 'ValueAssignment':
 705         return ValueAssignment(token.elements)
 706     elif token.ty == 'ValueReference':
 707         return ValueReference(token.elements)
 708     elif token.ty == 'ComponentType':
 709         return ComponentType(token.elements)
 710     elif token.ty == 'NamedType':
 711         return NamedType(token.elements)
 712     elif token.ty == 'ValueListType':
 713         return ValueListType(token.elements)
 714     elif token.ty == 'BitStringType':
 715         return BitStringType(token.elements)
 716     elif token.ty == 'NamedValue':
 717         return NamedValue(token.elements)
 718     elif token.ty == 'Type':
 719         return Type(token.elements)
 720     elif token.ty == 'SimpleType':
 721         return SimpleType(token.elements)
 722     elif token.ty == 'ReferencedType':
 723         return UserDefinedType(token.elements)
 724     elif token.ty == 'TaggedType':
 725         return TaggedType(token.elements)
 726     elif token.ty == 'SequenceType':
 727         return SequenceType(token.elements)
 728     elif token.ty == 'ChoiceType':
 729         return ChoiceType(token.elements)
 730     elif token.ty == 'SetType':
 731         return SetType(token.elements)
 732     elif token.ty == 'SequenceOfType':
 733         return SequenceOfType(token.elements)
 734     elif token.ty == 'SetOfType':
 735         return SetOfType(token.elements)
 736     elif token.ty == 'ExtensionMarker':
 737         return ExtensionMarker(token.elements)
 738     elif token.ty == 'SizeConstraint':
 739         return SizeConstraint(token.elements)
 740     elif token.ty == 'ObjectIdentifierValue':
 741         return ObjectIdentifierValue(token.elements)
 742     elif token.ty == 'NameForm':
 743         return NameForm(token.elements)
 744     elif token.ty == 'NumberForm':
 745         return NumberForm(token.elements)
 746     elif token.ty == 'NameAndNumberForm':
 747         return NameAndNumberForm(token.elements)
 748
 749     raise Exception('Unknown token type: %s' % token.ty)
 750
 751
 752 def _assert_annotated_token(obj):
 753     assert(type(obj) is parser.AnnotatedToken)
 754
 755
 756 # HACK: Generate unique names for unnamed members
 757 _unnamed_counter = 0
 758 def _get_next_unnamed():
 759     global _unnamed_counter
 760     _unnamed_counter += 1
 761     return 'unnamed%d' % _unnamed_counter