1 # Copyright (c) 2013, Schneider Electric Buildings AB
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.
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.
26 from asn1ate import parser
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.
34 for token in parse_result:
35 _assert_annotated_token(token)
36 root.append(_create_sema_node(token))
41 def topological_sort(assignments):
42 """ Algorithm adapted from:
43 http://en.wikipedia.org/wiki/Topological_sorting.
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.
50 graph = dict((a.reference_name(), set(a.references())) for a in assignments)
52 def has_predecessor(node):
53 for predecessor in graph.keys():
54 if node in graph[predecessor]:
59 # Build a topological order of reference names
60 topological_order = []
61 roots = [name for name in graph.keys() if not has_predecessor(name)]
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))
72 topological_order.insert(0, root)
75 raise Exception('Can\'t sort cyclic references: %s' % graph)
77 # Sort the actual assignments based on the topological order
78 return sorted(assignments, key=lambda a: topological_order.index(a.reference_name()))
84 Concepts in the ASN.1 specification are mirrored here as a simple object model.
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.
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.
92 All nodes that may be referenced (type and value assignments) must have a
93 method called ``reference_name``.
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
99 Typically, if you have a ``reference_name``, you must also have a ``references``,
100 but not the other way around.
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)
109 self.name = module_reference.elements[0]
110 self.assignments = [_create_sema_node(token) for token in module_body.elements]
111 self._user_types = {}
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
119 return self._user_types
121 def resolve_type_decl(self, type_decl):
122 """ Recursively resolve user-defined types to their
123 built-in declaration.
125 user_types = self.user_types()
127 if isinstance(type_decl, UserDefinedType):
128 return self.resolve_type_decl(user_types[type_decl.type_name])
134 return '%s DEFINITIONS ::=\n' % self.name \
136 + '\n'.join(map(str, self.assignments)) + '\n' \
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)
149 def reference_name(self):
150 return self.type_name
152 def references(self):
153 refs = self.type_decl.references()
155 # Remove any circular references
156 refs = [ref for ref in refs if ref != self.type_name]
161 return '%s ::= %s' % (self.type_name, self.type_decl)
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)
172 if isinstance(value, parser.AnnotatedToken):
173 self.value = _create_sema_node(value)
177 def reference_name(self):
178 return self.value_name.reference_name()
180 def references(self):
181 refs = [self.type_decl.reference_name()]
182 if isinstance(self.value, ValueReference):
183 refs.append(self.value.reference_name())
185 # It's a literal, and they don't play into declaration order.
188 # Remove any circular references
189 refs = [ref for ref in refs if ref != self.value_name]
194 return '%s %s ::= %s' % (self.value_name, self.type_decl, self.value)
199 class ValueReference(object):
200 def __init__(self, elements):
201 self.name = elements[0]
203 def reference_name(self):
206 def references(self):
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]
221 def references(self):
223 for component in self.components:
224 references.extend(component.references())
228 component_type_list = ', '.join(map(str, self.components))
229 return '%s { %s }' % (self.type_name, component_type_list)
234 class ChoiceType(ConstructedType):
235 def __init__(self, elements):
236 super(ChoiceType, self).__init__(elements)
239 class SequenceType(ConstructedType):
240 def __init__(self, elements):
241 super(SequenceType, self).__init__(elements)
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)
250 def references(self):
251 return self.type_decl.references()
254 return '%s %s' % (self.type_name, self.type_decl)
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)
265 def references(self):
266 return self.type_decl.references()
269 return '%s %s' % (self.type_name, self.type_decl)
274 class TaggedType(object):
275 def __init__(self, elements):
276 self.class_name = None
277 self.class_number = None
278 self.implicit = False
280 tag_token = elements[0]
281 if type(elements[1]) is parser.AnnotatedToken:
282 type_token = elements[1]
284 self.implicit = elements[1] == 'IMPLICIT'
285 type_token = elements[2]
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]
293 assert False, 'Unknown tag element: %s' % tag_element
295 self.type_decl = _create_sema_node(type_token)
299 return self.type_decl.type_name
301 def reference_name(self):
302 return self.type_decl.type_name
304 def references(self):
305 return self.type_decl.references()
310 class_spec.append(self.class_name)
311 class_spec.append(self.class_number)
313 result = '[%s] ' % ' '.join(class_spec)
315 result += 'IMPLICIT '
317 result += str(self.type_decl)
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)
331 def reference_name(self):
332 return self.type_name
334 def references(self):
335 refs = [self.type_name]
337 refs.extend(self.constraint.references())
342 if self.constraint is None:
343 return self.type_name
345 return '%s %s' % (self.type_name, self.constraint)
350 class UserDefinedType(object):
351 def __init__(self, elements):
352 self.type_name = elements[0]
354 def references(self):
355 return [self.type_name]
358 return self.type_name
363 class Constraint(object):
364 def __init__(self, elements):
365 min_value, max_value = elements
367 self.min_value = _maybe_create_sema_node(min_value)
368 self.max_value = _maybe_create_sema_node(max_value)
370 def references(self):
372 if isinstance(self.min_value, ValueReference):
373 refs.append(self.min_value.reference_name())
375 if isinstance(self.max_value, ValueReference):
376 refs.append(self.max_value.reference_name())
381 return '(%s..%s)' % (self.min_value, self.max_value)
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
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
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)
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])
411 assert False, 'Unknown component type %s' % first_token
413 def references(self):
414 if self.components_of_type:
415 return [self.components_of_type.type_name]
417 refs = [self.type_decl.type_name]
418 refs.extend(self.type_decl.references())
420 if self.default_value is not None:
421 refs.append(str(self.default_value))
426 if self.components_of_type:
427 return 'COMPONENTS OF %s' % self.components_of_type
429 result = '%s %s' % (self.identifier, self.type_decl)
431 result += ' OPTIONAL'
432 elif self.default_value is not None:
433 result += ' DEFAULT %s' % self.default_value
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':
449 self.identifier = first_token.elements[0]
450 type_token = elements[1]
452 self.type_decl = _create_sema_node(type_token)
454 def references(self):
455 return self.type_decl.references()
458 return '%s %s' % (self.identifier, self.type_decl)
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]]
469 self.named_values = None
471 def references(self):
472 # TODO: Value references
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)
480 return '%s' % self.type_name
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]]
491 self.named_bits = None
493 def references(self):
494 # TODO: Value references
499 named_bit_list = ', '.join(map(str, self.named_bits))
500 return '%s { %s }' % (self.type_name, named_bit_list)
502 return '%s' % self.type_name
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]
513 def references(self):
514 # TODO: This appears to never be called. Investigate.
518 return '%s (%s)' % (self.identifier, self.value)
523 def _maybe_create_sema_node(token):
524 if isinstance(token, parser.AnnotatedToken):
525 return _create_sema_node(token)
530 def _create_sema_node(token):
531 _assert_annotated_token(token)
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)
570 raise Exception('Unknown token type: %s' % token.ty)
573 def _assert_annotated_token(obj):
574 assert(type(obj) is parser.AnnotatedToken)
577 # HACK: Generate unique names for unnamed members
579 def _get_next_unnamed():
580 global _unnamed_counter
581 _unnamed_counter += 1
582 return 'unnamed%d' % _unnamed_counter