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         if isinstance(type_decl, UserDefinedType):
 157             return self.resolve_type_decl(user_types[type_decl.type_name])
 158         else:
 159             return type_decl
 160
 161
 162     def __str__(self):
 163         return '%s DEFINITIONS ::=\n' % self.name \
 164             + 'BEGIN\n' \
 165             + '\n'.join(map(str, self.assignments)) + '\n' \
 166             + 'END\n'
 167
 168     __repr__ = __str__
 169
 170
 171 class TypeAssignment(object):
 172     def __init__(self, elements):
 173         assert(len(elements) == 3)
 174         type_name, _, type_decl = elements
 175         self.type_name = type_name
 176         self.type_decl = _create_sema_node(type_decl)
 177
 178     def reference_name(self):
 179         return self.type_name
 180
 181     def references(self):
 182         refs = self.type_decl.references()
 183
 184         # Remove any self-references
 185         refs = [ref for ref in refs if ref != self.type_name]
 186
 187         return refs
 188
 189     def __str__(self):
 190         return '%s ::= %s' % (self.type_name, self.type_decl)
 191
 192     __repr__ = __str__
 193
 194
 195 class ValueAssignment(object):
 196     def __init__(self, elements):
 197         value_name, type_name, _, value = elements
 198         self.value_name = ValueReference(value_name.elements) # First token is always a valuereference
 199         self.type_decl = _create_sema_node(type_name)
 200
 201         if isinstance(value, parser.AnnotatedToken):
 202             self.value = _create_sema_node(value)
 203         else:
 204             self.value = value
 205
 206     def reference_name(self):
 207         return self.value_name.reference_name()
 208
 209     def references(self):
 210         refs = [self.type_decl.reference_name()]
 211         if isinstance(self.value, ValueReference):
 212             refs.append(self.value.reference_name())
 213         elif isinstance(self.value, ObjectIdentifierValue):
 214             refs.extend(self.value.references())
 215         else:
 216             # It's a literal, and they don't play into declaration order.
 217             pass
 218
 219         # Remove any self-references
 220         refs = [ref for ref in refs if ref != self.value_name]
 221
 222         return refs
 223
 224     def __str__(self):
 225         return '%s %s ::= %s' % (self.value_name, self.type_decl, self.value)
 226
 227     __repr__ = __str__
 228
 229
 230 class ValueReference(object):
 231     def __init__(self, elements):
 232         self.name = elements[0]
 233
 234     def reference_name(self):
 235         return self.name
 236
 237     def references(self):
 238         return []
 239
 240     def __str__(self):
 241         return self.name
 242
 243     __repr__ = __str__
 244
 245
 246 class ConstructedType(object):
 247     """ Base type for SEQUENCE, SET and CHOICE. """
 248     def __init__(self, elements):
 249         type_name, component_tokens = elements
 250         self.type_name = type_name
 251         self.components = [_create_sema_node(token) for token in component_tokens]
 252
 253     def references(self):
 254         references = []
 255         for component in self.components:
 256             references.extend(component.references())
 257         return references
 258
 259     def __str__(self):
 260         component_type_list = ', '.join(map(str, self.components))
 261         return '%s { %s }' % (self.type_name, component_type_list)
 262
 263     __repr__ = __str__
 264
 265
 266 class ChoiceType(ConstructedType):
 267     def __init__(self, elements):
 268         super(ChoiceType, self).__init__(elements)
 269
 270
 271 class SequenceType(ConstructedType):
 272     def __init__(self, elements):
 273         super(SequenceType, self).__init__(elements)
 274
 275
 276 class SetType(ConstructedType):
 277     def __init__(self, elements):
 278         super(SetType, self).__init__(elements)
 279
 280
 281 class CollectionType(object):
 282     """ Base type for SET OF and SEQUENCE OF. """
 283     def __init__(self, kind, elements):
 284         self.kind = kind
 285         self.type_name = self.kind + ' OF'
 286
 287         if elements[0].ty == 'Type':
 288             self.size_constraint = None
 289             self.type_decl = _create_sema_node(elements[0])
 290         elif elements[0].ty == 'SizeConstraint':
 291             self.size_constraint = _create_sema_node(elements[0])
 292             self.type_decl = _create_sema_node(elements[1])
 293         else:
 294             assert False, 'Unknown form of %s OF declaration: %s' % (self.kind, elements)
 295
 296     def references(self):
 297         return self.type_decl.references()
 298
 299     def __str__(self):
 300         if self.size_constraint:
 301             return '%s %s OF %s' % (self.kind, self.size_constraint, self.type_decl)
 302         else:
 303             return '%s OF %s' % (self.kind, self.type_decl)
 304
 305     __repr__ = __str__
 306
 307
 308 class SequenceOfType(CollectionType):
 309     def __init__(self, elements):
 310         super(SequenceOfType, self).__init__('SEQUENCE', elements)
 311
 312
 313 class SetOfType(CollectionType):
 314     def __init__(self, elements):
 315         super(SetOfType, self).__init__('SET', elements)
 316
 317
 318 class TaggedType(object):
 319     def __init__(self, elements):
 320         self.class_name = None
 321         self.class_number = None
 322         self.implicit = False
 323
 324         tag_token = elements[0]
 325         if type(elements[1]) is parser.AnnotatedToken:
 326             type_token = elements[1]
 327         else:
 328             self.implicit = elements[1] == 'IMPLICIT'
 329             type_token = elements[2]
 330
 331         for tag_element in tag_token.elements:
 332             if tag_element.ty == 'TagClassNumber':
 333                 self.class_number = tag_element.elements[0]
 334             elif tag_element.ty == 'TagClass':
 335                 self.class_name = tag_element.elements[0]
 336             else:
 337                 assert False, 'Unknown tag element: %s' % tag_element
 338
 339         self.type_decl = _create_sema_node(type_token)
 340
 341     @property
 342     def type_name(self):
 343         return self.type_decl.type_name
 344
 345     def reference_name(self):
 346         return self.type_decl.type_name
 347
 348     def references(self):
 349         return self.type_decl.references()
 350
 351     def __str__(self):
 352         class_spec = []
 353         if self.class_name:
 354             class_spec.append(self.class_name)
 355         class_spec.append(self.class_number)
 356
 357         result = '[%s] ' % ' '.join(class_spec)
 358         if self.implicit:
 359             result += 'IMPLICIT '
 360
 361         result += str(self.type_decl)
 362
 363         return result
 364
 365     __repr__ = __str__
 366
 367
 368 class SimpleType(object):
 369     def __init__(self, elements):
 370         self.constraint = None
 371         self.type_name = elements[0]
 372         if len(elements) > 1 and elements[1].ty == 'Constraint':
 373             self.constraint = Constraint(elements[1].elements)
 374
 375     def reference_name(self):
 376         return self.type_name
 377
 378     def references(self):
 379         refs = [self.type_name]
 380         if self.constraint:
 381             refs.extend(self.constraint.references())
 382
 383         return refs
 384
 385     def __str__(self):
 386         if self.constraint is None:
 387             return self.type_name
 388
 389         return '%s %s' % (self.type_name, self.constraint)
 390
 391     __repr__ = __str__
 392
 393
 394 class UserDefinedType(object):
 395     def __init__(self, elements):
 396         self.type_name = elements[0]
 397
 398     def references(self):
 399         return [self.type_name]
 400
 401     def __str__(self):
 402         return self.type_name
 403
 404     __repr__ = __str__
 405
 406
 407 class Constraint(object):
 408     def __init__(self, elements):
 409         min_value, max_value = elements
 410
 411         self.min_value = _maybe_create_sema_node(min_value)
 412         self.max_value = _maybe_create_sema_node(max_value)
 413
 414     def references(self):
 415         refs = []
 416         if isinstance(self.min_value, ValueReference):
 417             refs.append(self.min_value.reference_name())
 418
 419         if isinstance(self.max_value, ValueReference):
 420             refs.append(self.max_value.reference_name())
 421
 422         return refs
 423
 424     def __str__(self):
 425         return '(%s..%s)' % (self.min_value, self.max_value)
 426
 427     __repr__ = __str__
 428
 429
 430 class SizeConstraint(Constraint):
 431     """ Size constraints have the same form as any value range constraints."""
 432     def __str__(self):
 433         return 'SIZE(%s..%s)' % (self.min_value, self.max_value)
 434
 435     __repr__ = __str__
 436
 437
 438 class ComponentType(object):
 439     def __init__(self, elements):
 440         self.identifier = None
 441         self.type_decl = None
 442         self.default_value = None
 443         self.optional = False
 444         self.components_of_type = None
 445
 446         def crack_named_type(token):
 447             named_type = NamedType(token)
 448             self.identifier = named_type.identifier
 449             self.type_decl = named_type.type_decl
 450
 451         first_token = elements[0]
 452         if first_token.ty == 'NamedType':
 453             crack_named_type(first_token.elements)
 454         elif first_token.ty == 'ComponentTypeOptional':
 455             crack_named_type(first_token.elements[0].elements)
 456             self.optional = True
 457         elif first_token.ty == 'ComponentTypeDefault':
 458             crack_named_type(first_token.elements[0].elements)
 459             self.default_value = _maybe_create_sema_node(first_token.elements[1])
 460         elif first_token.ty == 'ComponentTypeComponentsOf':
 461             self.components_of_type = _create_sema_node(first_token.elements[0])
 462         else:
 463             assert False, 'Unknown component type %s' % first_token
 464
 465     def references(self):
 466         if self.components_of_type:
 467             return [self.components_of_type.type_name]
 468
 469         refs = [self.type_decl.type_name]
 470         refs.extend(self.type_decl.references())
 471
 472         if self.default_value is not None:
 473             refs.append(str(self.default_value))
 474
 475         return refs
 476
 477     def __str__(self):
 478         if self.components_of_type:
 479             return 'COMPONENTS OF %s' % self.components_of_type
 480
 481         result = '%s %s' % (self.identifier, self.type_decl)
 482         if self.optional:
 483             result += ' OPTIONAL'
 484         elif self.default_value is not None:
 485             result += ' DEFAULT %s' % self.default_value
 486
 487         return result
 488
 489     __repr__ = __str__
 490
 491
 492 class NamedType(object):
 493     def __init__(self, elements):
 494         first_token = elements[0]
 495         if first_token.ty == 'Type':
 496             # EXT: unnamed member
 497             type_token = first_token
 498             self.identifier = _get_next_unnamed()
 499         elif first_token.ty == 'Identifier':
 500             # an identifier
 501             self.identifier = first_token.elements[0]
 502             type_token = elements[1]
 503
 504         self.type_decl = _create_sema_node(type_token)
 505
 506     def references(self):
 507         return self.type_decl.references()
 508
 509     def __str__(self):
 510         return '%s %s' % (self.identifier, self.type_decl)
 511
 512     __repr__ = __str__
 513
 514
 515 class ValueListType(object):
 516     def __init__(self, elements):
 517         self.type_name = elements[0]
 518         if len(elements) > 1:
 519             self.named_values = [_create_sema_node(token) for token in elements[1]]
 520         else:
 521             self.named_values = None
 522
 523     def references(self):
 524         # TODO: Value references
 525         return []
 526
 527     def __str__(self):
 528         if self.named_values:
 529             named_value_list = ', '.join(map(str, self.named_values))
 530             return '%s { %s }' % (self.type_name, named_value_list)
 531         else:
 532             return '%s' % self.type_name
 533
 534     __repr__ = __str__
 535
 536
 537 class BitStringType(object):
 538     def __init__(self, elements):
 539         self.type_name = elements[0]
 540         if len(elements) > 1:
 541             self.named_bits = [_create_sema_node(token) for token in elements[1]]
 542         else:
 543             self.named_bits = None
 544
 545     def references(self):
 546         # TODO: Value references
 547         return []
 548
 549     def __str__(self):
 550         if self.named_bits:
 551             named_bit_list = ', '.join(map(str, self.named_bits))
 552             return '%s { %s }' % (self.type_name, named_bit_list)
 553         else:
 554             return '%s' % self.type_name
 555
 556     __repr__ = __str__
 557
 558
 559 class NamedValue(object):
 560     def __init__(self, elements):
 561         identifier_token, value_token = elements
 562         self.identifier = identifier_token.elements[0]
 563         self.value = value_token.elements[0]
 564
 565     def references(self):
 566         # TODO: This appears to never be called. Investigate.
 567         return []
 568
 569     def __str__(self):
 570         return '%s (%s)' % (self.identifier, self.value)
 571
 572     __repr__ = __str__
 573
 574
 575 class ExtensionMarker(object):
 576     def __init__(self, elements):
 577         pass
 578
 579     def references(self):
 580         # TODO: This appears to never be called. Investigate.
 581         return []
 582
 583     def __str__(self):
 584         return '...'
 585
 586     __repr__ = __str__
 587
 588
 589 class NameForm(object):
 590     def __init__(self, elements):
 591         self.name = elements[0]
 592
 593     def references(self):
 594         return [self.name]
 595
 596     def __str__(self):
 597         return self.name
 598
 599     __repr__ = __str__
 600
 601
 602 class NumberForm(object):
 603     def __init__(self, elements):
 604         self.value = elements[0]
 605
 606     def references(self):
 607         return []
 608
 609     def __str__(self):
 610         return str(self.value)
 611
 612     __repr__ = __str__
 613
 614
 615 class NameAndNumberForm(object):
 616     def __init__(self, elements):
 617         # The first element is a NameForm containing only the
 618         # name, so unpack it into a string.
 619         self.name = elements[0].elements[0]
 620         self.number = _create_sema_node(elements[1])
 621
 622     def references(self):
 623         return [str(self.name), str(self.number)]
 624
 625     def __str__(self):
 626         return '%s(%s)' % (self.name, self.number)
 627
 628     __repr__ = __str__
 629
 630
 631 class ObjectIdentifierValue(object):
 632     def __init__(self, elements):
 633         self.components = [_create_sema_node(c) for c in elements]
 634
 635     def references(self):
 636         refs = []
 637         for component in self.components:
 638             if not isinstance(component, str):
 639                 refs.extend(component.references())
 640             else:
 641                 refs.append(component)
 642
 643         return refs
 644
 645     def __str__(self):
 646         return '{' + ' '.join(str(x) for x in self.components) + '}'
 647
 648     __repr__ = __str__
 649
 650
 651 def _maybe_create_sema_node(token):
 652     if isinstance(token, parser.AnnotatedToken):
 653         return _create_sema_node(token)
 654     else:
 655         return token
 656
 657
 658 def _create_sema_node(token):
 659     _assert_annotated_token(token)
 660
 661     if token.ty == 'ModuleDefinition':
 662         return Module(token.elements)
 663     elif token.ty == 'TypeAssignment':
 664         return TypeAssignment(token.elements)
 665     elif token.ty == 'ValueAssignment':
 666         return ValueAssignment(token.elements)
 667     elif token.ty == 'ValueReference':
 668         return ValueReference(token.elements)
 669     elif token.ty == 'ComponentType':
 670         return ComponentType(token.elements)
 671     elif token.ty == 'NamedType':
 672         return NamedType(token.elements)
 673     elif token.ty == 'ValueListType':
 674         return ValueListType(token.elements)
 675     elif token.ty == 'BitStringType':
 676         return BitStringType(token.elements)
 677     elif token.ty == 'NamedValue':
 678         return NamedValue(token.elements)
 679     elif token.ty == 'Type':
 680         # Type tokens have a more specific type category
 681         # embedded as their first element
 682         return _create_sema_node(token.elements[0])
 683     elif token.ty == 'SimpleType':
 684         return SimpleType(token.elements)
 685     elif token.ty == 'ReferencedType':
 686         return UserDefinedType(token.elements)
 687     elif token.ty == 'TaggedType':
 688         return TaggedType(token.elements)
 689     elif token.ty == 'SequenceType':
 690         return SequenceType(token.elements)
 691     elif token.ty == 'ChoiceType':
 692         return ChoiceType(token.elements)
 693     elif token.ty == 'SetType':
 694         return SetType(token.elements)
 695     elif token.ty == 'SequenceOfType':
 696         return SequenceOfType(token.elements)
 697     elif token.ty == 'SetOfType':
 698         return SetOfType(token.elements)
 699     elif token.ty == 'ExtensionMarker':
 700         return ExtensionMarker(token.elements)
 701     elif token.ty == 'SizeConstraint':
 702         return SizeConstraint(token.elements)
 703     elif token.ty == 'ObjectIdentifierValue':
 704         return ObjectIdentifierValue(token.elements)
 705     elif token.ty == 'NameForm':
 706         return NameForm(token.elements)
 707     elif token.ty == 'NumberForm':
 708         return NumberForm(token.elements)
 709     elif token.ty == 'NameAndNumberForm':
 710         return NameAndNumberForm(token.elements)
 711
 712     raise Exception('Unknown token type: %s' % token.ty)
 713
 714
 715 def _assert_annotated_token(obj):
 716     assert(type(obj) is parser.AnnotatedToken)
 717
 718
 719 # HACK: Generate unique names for unnamed members
 720 _unnamed_counter = 0
 721 def _get_next_unnamed():
 722     global _unnamed_counter
 723     _unnamed_counter += 1
 724     return 'unnamed%d' % _unnamed_counter