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