Helper.py 25.8 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
    OpenGEODE - A tiny SDL Editor for TASTE

    This module provides helper functions typically used by backends:

        flatten(ast) : transform a model with nested states to a flat model
        rename_everything(ast, from_name, to_name) : rename symbols
Maxime Perrotin's avatar
Maxime Perrotin committed
11
        inner_labels_to_floating(process) : remove labels from transitions
Maxime Perrotin's avatar
Maxime Perrotin committed
12
13
        map_input_state(process) -> mapping: create a mapping
                                    input-state-transition
14
15
        sorted_fields(SEQ/CHOICE) : returns the ordered list of fields
                                    of an ASN.1 SEQUENCE or CHOICE type
Maxime Perrotin's avatar
Maxime Perrotin committed
16
        state_aggregations: enrich AST with state aggregation flags,
17
18
                            and return the list of substates of aggregations
        parallel_states: return a list of strings naming all parallel states
Maxime Perrotin's avatar
Maxime Perrotin committed
19
20
        statenames: return a list of properly-formatted state names
        rec_findstates: recursively find parallel/composite statenames
21

Maxime Perrotin's avatar
Maxime Perrotin committed
22
    Copyright (c) 2012-2015 European Space Agency
23
24
25
26
27
28

    Designed and implemented by Maxime Perrotin

    Contact: maxime.perrotin@esa.int
"""

29
import operator
30
import logging
Maxime Perrotin's avatar
Maxime Perrotin committed
31
from itertools import chain, ifilterfalse
32
from collections import defaultdict
33
34
35
36
37
38
39

from singledispatch import singledispatch

import ogAST

LOG = logging.getLogger(__name__)

Maxime Perrotin's avatar
Maxime Perrotin committed
40
__all__ = ['flatten', 'rename_everything', 'inner_labels_to_floating',
41
           'map_input_state', 'sorted_fields', 'state_aggregations',
Maxime Perrotin's avatar
Maxime Perrotin committed
42
43
44
45
46
47
48
49
50
51
           'parallel_states', 'statenames', 'rec_findstates']


def statenames(context, sep=u'\u00dc'):
    ''' Return the list of states (just the names) of a given context
    Format the output by replacing unicode separator symbol with a dot '''
    return (s.replace(sep, u'.') for s in context.mapping.viewkeys()
            if not s.endswith(u'START'))


Maxime Perrotin's avatar
Maxime Perrotin committed
52
53
54
55
56
57
58
59
60
#def non_composite_statenames(context, sep=u'\u00dc'):
#   ''' Return a list of statenames excluding parents of state compositions '''
#   composites = []
#   for each in context.composite_states:
#       if not isinstance(each, ofAST.StateAggregation):
#
#   return ifilterfalse(lambda x: , statenames(context, sep))


Maxime Perrotin's avatar
Maxime Perrotin committed
61
62
63
64
65
66
67
68
69
70
71
def rec_findstates(context, prefix=''):
    ''' In case of state compositions/aggregations, find substates '''
    for each in context.composite_states:
        if not isinstance(each, ogAST.StateAggregation):
            # Aggregations are just containers, not states
            for name in statenames(each):
                yield u'{}{}.{}'.format(prefix, each.statename, name)
        for substate in rec_findstates(each,
                                       prefix=u'{}{}.'.format(prefix,
                                                              each.statename)):
            yield substate
Maxime Perrotin's avatar
Maxime Perrotin committed
72
73
74


def state_aggregations(process):
75
76
77
78
79
    ''' Explore recursively the AST to find all state aggregations, and
        return the composite states inside them
        input: ogAST.Process element
        output: {state_aggregation: {list of ogAST.CompositeState}
    '''
80
81
    # { aggregate_name : [list of parallel states] }
    aggregates = defaultdict(list)
Maxime Perrotin's avatar
Maxime Perrotin committed
82
    def do_composite(comp, aggregate=''):
83
84
85
        ''' Recursively find all state aggregations in order to allow code
        generator backends to store the state of each parallel state '''
        pre = comp.statename if isinstance(comp, ogAST.StateAggregation) \
Maxime Perrotin's avatar
Maxime Perrotin committed
86
                    else ''
87
        for each in comp.composite_states:
Maxime Perrotin's avatar
Maxime Perrotin committed
88
89
            do_composite(each, pre)
            if isinstance(each, ogAST.StateAggregation):
90
91
                # substate of the current state is a state aggregation
                # -> set a flag in each terminator of the current state
Maxime Perrotin's avatar
Maxime Perrotin committed
92
93
                for term in comp.terminators:
                    if term.inputString.lower() == each.statename.lower():
94
                        term.next_is_aggregation = True
95
        if aggregate and not isinstance(comp, ogAST.StateAggregation):
Maxime Perrotin's avatar
Maxime Perrotin committed
96
            # Composite state inside a state aggregation
97
            aggregates[aggregate].append(comp)
Maxime Perrotin's avatar
Maxime Perrotin committed
98
99
100
101
102
103
104
105
106
107
108
            # Here, all the terminators inside the composite states must
            # be flagged with the name of the substate so that the NEXTSTATE
            # will not be using the main "context.state" variable but will
            # use the parallel substate name when generating code.
            for each in comp.terminators:
                each.substate = comp.statename
    for each in process.composite_states:
        do_composite(each)
    for each in process.terminators:
        if each.inputString.lower() in aggregates:
            each.next_is_aggregation = True
109
110
111
112
113
114
115
116
    for name, comp in aggregates.viewitems():
        # for each state aggregation. update the terminators
        # of each parallel state with the name of all sibling states
        # useful for backends to handle parallel state termination (return)
        # since they have to synchronize with the sibling states
        siblings = [sib.statename for sib in comp]
        for term in [terms for sib in comp for terms in sib.terminators]:
            term.siblings = siblings
117
    return aggregates
Maxime Perrotin's avatar
Maxime Perrotin committed
118
119


120
121
122
123
124
125
126
127
128
129
130
def parallel_states(aggregates):
    ''' Given a mapping obtained with state_aggregation(process), extract
        all parallel states and return a list of state names '''
    parallel_states = []
    for name, comp in aggregates.viewitems():
        for each in comp:
            parallel_states.extend(name for name in each.mapping.viewkeys()
                    if not name.endswith(u'START'))
    return parallel_states


Maxime Perrotin's avatar
Maxime Perrotin committed
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
def map_input_state(process):
    ''' Create a mapping dict {input1: {state1: transition, ...}, ...} '''
    mapping = defaultdict(dict)
    input_signals = [sig['name'] for sig in process.input_signals]
    # Add timers to the mapping
    input_signals.extend(process.timers)
    for input_signal in input_signals:
        for state_name, input_symbols in process.mapping.viewitems():
            if isinstance(input_symbols, list):
                # Start symbols have no list of inputs
                for i in input_symbols:
                    if input_signal.lower() in (inp.lower() for
                                               inp in i.inputlist):
                        mapping[input_signal][state_name] = i
    return mapping
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161


def inner_labels_to_floating(process):
    '''
        Transform inner labels of both floating labels and transitions
        into new floating labels, so that they can be generated in a separate
        section of code, where they are in the scope of everybody
        Works with processes, procedures and nested states
    '''
    for idx in xrange(len(process.content.floating_labels)):
        for new_floating in find_labels(
                      process.content.floating_labels[idx].transition):
            process.content.floating_labels.append(new_floating)
    for proc_tr in process.transitions:
        for new_floating in find_labels(proc_tr):
            process.content.floating_labels.append(new_floating)
Maxime Perrotin's avatar
Maxime Perrotin committed
162
163
164
    if process.content.start:
        for new_floating in find_labels(process.content.start.transition):
            process.content.floating_labels.append(new_floating)
165
166
167
168
169
    for each in process.content.named_start:
        for new_floating in find_labels(each.transition):
            process.content.floating_labels.append(new_floating)


Maxime Perrotin's avatar
Maxime Perrotin committed
170
def flatten(process, sep=u'_'):
171
    ''' In-place update of the AST: flatten a model with nested states
172
173
        Rename inner states, procedures, etc. and move them to process level
    '''
Maxime Perrotin's avatar
Maxime Perrotin committed
174
    def update_terminator(context, term, process):
175
176
177
178
        '''Set next_id, identifying the next transition to run '''
        if term.inputString.lower() in (st.statename.lower()
                                for st in context.composite_states):
            if not term.via:
Maxime Perrotin's avatar
Maxime Perrotin committed
179
                term.next_id = term.inputString.lower() + sep + u'START'
180
            else:
Maxime Perrotin's avatar
Maxime Perrotin committed
181
                term.next_id = u'{term}{sep}{entry}_START'.format(
182
                        term=term.inputString, entry=term.entrypoint, sep=sep)
183
184
        elif term.inputString.strip() == '-':
            for each in term.possible_states:
185
186
187
188
189
190
191
192
                term.candidate_id[-1].append(each)
                for comp in context.composite_states:
                    if each.lower() == comp.statename.lower():
                        if isinstance(comp, ogAST.StateAggregation):
                            term.next_is_aggregation = True
                            term.candidate_id[each + sep + u'START'] = [each]
                        else:
                            term.candidate_id[each + sep + u'START'] = \
193
194
                                       [st for st in process.mapping.viewkeys()
                                        if st.startswith(each)
Maxime Perrotin's avatar
Maxime Perrotin committed
195
                                        and not st.endswith(u'START')]
196
                        continue
197
198
199
200
201
202

    def update_composite_state(state, process):
        ''' Rename inner states, recursively, and add inner transitions
            to process, updating indexes, and update terminators
        '''
        trans_idx = len(process.transitions)
203
        prefix = state.statename + sep
204
        set_terminator_states(state, prefix)
205
206
        set_transition_states(state, prefix)

Maxime Perrotin's avatar
Maxime Perrotin committed
207
        state.mapping = {prefix + key: state.mapping.pop(key)
208
                         for key in state.mapping.keys()}
209
210
211
        # Continuous signal mappings
        state.cs_mapping = {prefix + key: state.cs_mapping.pop(key)
                            for key in state.cs_mapping.keys()}
212
213
214
215
216
217
218
219
220
        process.transitions.extend(state.transitions)

        # Add prefix to local variable names and push them at process level
        for dcl in state.variables.viewkeys():
            rename_everything(state.content, dcl, prefix + dcl)
        state.variables = {prefix + key: state.variables.pop(key)
                           for key in state.variables.keys()}
        process.variables.update(state.variables)

221
222
223
224
225
226
227
228
229
        # Update return transition indices
        for each in state.terminators:
            if each.kind == 'return':
                for idx, trans in enumerate(process.transitions):
                    if trans == each.next_trans:
                        each.next_id = idx
                        break

        values = []
230
231
232
        for key, value in state.mapping.viewitems():
            # Update transition indices
            if isinstance(value, int):
233
                # START transitions
234
235
                state.mapping[key] = value + trans_idx
            else:
236
237
                values.extend(value)

238
239
240
        for each in state.cs_mapping.viewvalues():
            # Update transition indices of continuous signals
            # XXX shouldn't we do it also for CONNECT parts?
Maxime Perrotin's avatar
Maxime Perrotin committed
241
            values.extend(each)
242

243
244
245
246
247
248
        for inp in set(values):
            # values may contain duplicate entries if an input corresponds
            # to multiple states. In that case we must update the index of the
            # input only once, thus the set().
            inp.transition_id += trans_idx

249
        process.mapping.update(state.mapping)
250
        process.cs_mapping.update(state.cs_mapping)
251
252
253
254
255
256
257

        # If composite state has entry procedures, add the call
        if state.entry_procedure:
            for each in (trans for trans in state.mapping.viewvalues()
                         if isinstance(trans, int)):
                call_entry = ogAST.ProcedureCall()
                call_entry.inputString = 'entry'
258
259
                entryproc = u'{pre}entry'.format(pre=prefix)
                call_entry.output = [{'outputName': entryproc,
260
261
262
263
264
265
266
267
268
269
                                     'params': [], 'tmpVars': []}]
                process.transitions[each].actions.insert(0, call_entry)

        # If composite state has exit procedure, add the call
        if state.exit_procedure:
            for each in chain(state.transitions, (lab.transition for lab in
                                              state.content.floating_labels)):
                if each.terminator.kind == 'return':
                    call_exit = ogAST.ProcedureCall()
                    call_exit.inputString = 'exit'
270
271
272
                    exitproc = u'{pre}exit'.format(pre=prefix)
                    call_exit.output = [{'outputName': exitproc,
                                         'params': [], 'tmpVars': []}]
273
274
275
276
277
278
                    each.actions.append(call_exit)

        for inner in state.composite_states:
            # Go recursively in inner composite states
            inner.statename = prefix + inner.statename
            update_composite_state(inner, process)
279
            # Remove: recursion is already handled within propagate_inputs
Maxime Perrotin's avatar
Maxime Perrotin committed
280
281
            #propagate_inputs(inner, process)
            #del process.mapping[inner.statename]
282
283
284
285
286
        for each in state.terminators:
            # Give prefix to terminators
            if each.label:
                each.label.inputString = prefix + each.label.inputString
            if each.kind == 'next_state':
287
288
                if each.inputString.strip() != '-':
                    each.inputString = prefix + each.inputString
289
                # Set next transition id
Maxime Perrotin's avatar
Maxime Perrotin committed
290
                update_terminator(context=state, term=each, process=process)
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
            elif each.kind == 'join':
                rename_everything(state.content,
                                  each.inputString,
                                  prefix + each.inputString)
        for each in state.labels:
            # Give prefix to labels in transitions
            rename_everything(state.content,
                              each.inputString,
                              prefix + each.inputString)
        # Add prefixed floating labels of the composite state to the process
        process.content.floating_labels.extend(state.content.floating_labels)
        # Rename inner procedures
        for each in state.content.inner_procedures:
            rename_everything(state.content, each.inputString,
                              prefix + each.inputString)
            each.inputString = prefix + each.inputString
        process.content.inner_procedures.extend(state.content.inner_procedures)

309
    def propagate_inputs(nested_state, context):
310
311
312
313
314
        ''' Nested states: Inputs at level N must be handled at level N-1
            that is, all inputs of a composite states (the ones that allow
            to exit the composite state from the outer scope) must be
            processed by each of the substates.
        '''
315
316
317
318
319
320
321
322
        if not isinstance(nested_state, ogAST.StateAggregation):
            for _, val in nested_state.mapping.viewitems():
                try:
                    inputlist = context.mapping[nested_state.statename]
                    val.extend(inputlist)
                except (AttributeError, KeyError):
                    # KeyError in case of StateAggregation
                    pass
323
324
        for each in nested_state.composite_states:
            # do the same recursively
325
            propagate_inputs(each, nested_state)
326
327
328
            #del nested_state.mapping[each.statename]
        if not isinstance(nested_state, ogAST.StateAggregation):
            del context.mapping[nested_state.statename]
329

330
331
332
333
334
335
336
337
338
    def set_terminator_states(context, prefix=''):
        ''' Associate state to terminators, needed to process properly
            a history nextstates (dash nextstate) in code generators '''
        for each in context.content.states:
            for inp in each.inputs:
                for term in inp.terminators:
                    term.possible_states.extend(prefix + name.lower()
                                                for name in each.statelist)

339
340
341
342
343
344
345
346
    def set_transition_states(context, prefix=''):
        ''' Associate state to transitions, needed to process properly
            the call to the exit procedure of a nested state '''
        for each in context.content.states:
            for inp in each.inputs:
                inp.transition.possible_states.extend(prefix + name.lower()
                                                for name in each.statelist)

347
    set_terminator_states(process)
348
    set_transition_states(process)
349

350
351
    for each in process.composite_states:
        update_composite_state(each, process)
352
        propagate_inputs(each, process)
353
        #del process.mapping[each.statename]
354
355
356
357

    # Update terminators at process level
    for each in process.terminators:
        if each.kind == 'next_state':
Maxime Perrotin's avatar
Maxime Perrotin committed
358
            update_terminator(process, each, process)
359
360
361
362
363
364
365
366
367
368
369


@singledispatch
def rename_everything(ast, from_name, to_name):
    '''
        Rename in all symbols all occurences of name_ref into new_name.
        This is used to avoid name clashes in nested diagrams when they get
        flattened. For example rename all accesses to a variable declared
        in the scope of a composite state, so that they do not overwrite
        a variable with the same name declared at a higher scope.
    '''
370
371
372
373
374
    LOG.debug ('rename_everything - ' + str(ast) + " - ")
    try:
        LOG.debug(ast.inputString)
    except:
        pass
375

376
377
    _, _, _ = ast, from_name, to_name

Maxime Perrotin's avatar
Maxime Perrotin committed
378

379
380
381
382
383
384
385
386
387
388
@rename_everything.register(ogAST.Automaton)
def _rename_automaton(ast, from_name, to_name):
    ''' Renaming at Automaton top level (content of digragrams) '''
    if ast.start:
        rename_everything(ast.start.transition, from_name, to_name)
    for each in ast.named_start:
        rename_everything(each.transition, from_name, to_name)
    for each in ast.floating_labels:
        rename_everything(each, from_name, to_name)
    for each in ast.states:
389
        for inp in chain(each.inputs, each.continuous_signals, each.connects):
390
391
392
            rename_everything(inp.transition, from_name, to_name)
            for idx, param in enumerate(inp.parameters):
                if param.lower() == from_name.lower():
393
                    inp.parameters[idx] = to_name
394
395
396
397
398
            try:
                rename_everything(inp.trigger, from_name, to_name)
            except AttributeError:
                # only for continuous signals
                pass
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
        if each.composite:
            rename_everything(each.composite.content, from_name, to_name)
    for each in ast.inner_procedures:
        # Check that from_name is not a redefined variable in the procedure
        for varname in each.variables.viewkeys():
            if varname.lower() == from_name:
                break
        else:
            rename_everything(each.content, from_name, to_name)


@rename_everything.register(ogAST.Output)
@rename_everything.register(ogAST.ProcedureCall)
def _rename_output(ast, from_name, to_name):
    ''' Rename actual parameter names in output/procedure calls
        and possibly the procedure name '''
    for each in ast.output:
        if each['outputName'].lower() == from_name.lower():
            each['outputName'] = to_name
        for param in each['params']:
            rename_everything(param, from_name, to_name)


@rename_everything.register(ogAST.Label)
def _rename_label(ast, from_name, to_name):
    ''' Rename elements in the transition following a label '''
    if ast.inputString.lower() == from_name.lower():
        ast.inputString = to_name
    rename_everything(ast.transition, from_name, to_name)

Maxime Perrotin's avatar
Maxime Perrotin committed
429

430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
@rename_everything.register(ogAST.Decision)
def _rename_decision(ast, from_name, to_name):
    ''' Rename elements in decision '''
    if ast.kind == 'question':
        rename_everything(ast.question, from_name, to_name)
    for each in ast.answers:
        rename_everything(each, from_name, to_name)


@rename_everything.register(ogAST.Answer)
def _rename_answer(ast, from_name, to_name):
    ''' Rename elements in an answer branch '''
    if ast.kind in ('constant', 'open_range'):
        rename_everything(ast.constant, from_name, to_name)
    elif ast.kind == 'closed_range':
Maxime Perrotin's avatar
Maxime Perrotin committed
445
        pass  # TODO when supported
446
447
448
449
450
451
452
453
454
455
    rename_everything(ast.transition, from_name, to_name)


@rename_everything.register(ogAST.Transition)
def _rename_transition(ast, from_name, to_name):
    ''' Rename in all symbols of a transition '''
    for each in chain(ast.actions, ast.terminators):
        # Label, output, task, decision, terminators
        rename_everything(each, from_name, to_name)

Maxime Perrotin's avatar
Maxime Perrotin committed
456

457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
@rename_everything.register(ogAST.Terminator)
def _rename_terminator(ast, from_name, to_name):
    ''' Rename terminators: join/labels, next_state '''
    if ast.inputString.lower() == from_name.lower():
        ast.inputString = to_name
    rename_everything(ast.label, from_name, to_name)
    rename_everything(ast.return_expr, from_name, to_name)


@rename_everything.register(ogAST.TaskAssign)
def _rename_task_assign(ast, from_name, to_name):
    ''' List of assignments '''
    for each in ast.elems:
        rename_everything(each, from_name, to_name)

Maxime Perrotin's avatar
Maxime Perrotin committed
472

473
474
475
476
477
@rename_everything.register(ogAST.TaskForLoop)
def _rename_forloop(ast, from_name, to_name):
    ''' List of FOR loops '''
    for each in ast.elems:
        rename_everything(each['list'], from_name, to_name)
478
479
480
481
482
        if each['range'] is not None:
            rename_everything(each['range']['start'], from_name, to_name)
            rename_everything(each['range']['stop'], from_name, to_name)
        if each['transition'] is not None:
            rename_everything(each['transition'], from_name, to_name)
483

Maxime Perrotin's avatar
Maxime Perrotin committed
484

485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
@rename_everything.register(ogAST.ExprPlus)
@rename_everything.register(ogAST.ExprMul)
@rename_everything.register(ogAST.ExprMinus)
@rename_everything.register(ogAST.ExprEq)
@rename_everything.register(ogAST.ExprNeq)
@rename_everything.register(ogAST.ExprGt)
@rename_everything.register(ogAST.ExprGe)
@rename_everything.register(ogAST.ExprLt)
@rename_everything.register(ogAST.ExprLe)
@rename_everything.register(ogAST.ExprDiv)
@rename_everything.register(ogAST.ExprMod)
@rename_everything.register(ogAST.ExprRem)
@rename_everything.register(ogAST.ExprAssign)
@rename_everything.register(ogAST.ExprOr)
@rename_everything.register(ogAST.ExprIn)
@rename_everything.register(ogAST.ExprAnd)
@rename_everything.register(ogAST.ExprXor)
@rename_everything.register(ogAST.ExprAppend)
@rename_everything.register(ogAST.ExprAssign)
def _rename_expr(ast, from_name, to_name):
    ''' Two-sided expressions '''
    rename_everything(ast.left, from_name, to_name)
    rename_everything(ast.right, from_name, to_name)
508
509


510
511
512
513
514
515
516
517
@rename_everything.register(ogAST.PrimSequenceOf)
def _rename_prim_seq_of(ast, from_name, to_name):
    ''' List of primary '''
    for each in ast.value:
        rename_everything(each, from_name, to_name)



518
519
520
@rename_everything.register(ogAST.PrimIndex)
def _rename_index(ast, from_name, to_name):
    ''' Index of an array '''
521
    rename_everything(ast.value[0], from_name, to_name)
522
523
    for each in ast.value[1]['index']:
        rename_everything(each, from_name, to_name)
524

Maxime Perrotin's avatar
Maxime Perrotin committed
525

526
527
528
529
530
531
532
533
@rename_everything.register(ogAST.PrimSubstring)
def _rename_substring(ast, from_name, to_name):
    ''' Substrings '''
    rename_everything(ast.value[0], from_name, to_name)
    for each in ast.value[1]['substring']:
        rename_everything(each, from_name, to_name)


534
535
536
537
538
539
@rename_everything.register(ogAST.PrimVariable)
def _rename_path(ast, from_name, to_name):
    ''' Ultimate seek point for the renaming: primary path/variables '''
    if ast.value[0].lower() == from_name.lower():
        ast.value[0] = to_name

Maxime Perrotin's avatar
Maxime Perrotin committed
540

541
542
543
544
545
546
547
@rename_everything.register(ogAST.PrimCall)
def _rename_primcall(ast, from_name, to_name):
    ''' PrimCall is used e.g. by function "length" (special operators) '''
    for each in ast.value[1]['procParams']:
        rename_everything(each, from_name, to_name)


548
@rename_everything.register(ogAST.PrimConditional)
549
def _rename_ifhthenelse(ast, from_name, to_name):
550
    ''' Rename expressions in Conditional expression construct '''
551
552
    for expr in ('if', 'then', 'else'):
        rename_everything(ast.value[expr], from_name, to_name)
553

Maxime Perrotin's avatar
Maxime Perrotin committed
554

555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
def find_labels(trans):
    '''
        Yield a list of transition actions whenever a label is found
        Used to transform labels into floating labels so that the gotos
        in a backend can be contained within a single scope.
    '''
    if not trans:
        return
    # Terminators can have a label - add it to the transition actions
    # (to trigger a goto at code generation)
    if trans.terminator and trans.terminator.label:
        trans.actions.append(trans.terminator.label)
        trans.terminator.label = None
    # Then for each action, check if there are labels and yield
    # a new transition with the remaining actions (following the label)
    for idx, action in enumerate(trans.actions):
        if isinstance(action, ogAST.Label):
            new_trans = ogAST.Transition()
            # Create a floating label
            flab = ogAST.Floating_label(label=action)
Maxime Perrotin's avatar
Maxime Perrotin committed
575
576
            new_trans.actions = \
                    trans.actions[slice(idx + 1, len(trans.actions))]
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
            new_trans.terminator = trans.terminator
            new_trans.terminators = trans.terminators
            flab.transition = new_trans
            # Transform the label into a JOIN in the original transition
            trans.actions[idx:] = []
            trans.terminator = ogAST.Terminator()
            trans.terminator.inputString = action.inputString
            trans.terminator.kind = 'join'
            # Recursively find labels in the new transition
            for flabel in find_labels(flab.transition):
                yield flabel
            # Then yield the new transition
            yield flab
        elif isinstance(action, ogAST.Decision):
            for answer in action.answers:
                for new_fl in find_labels(answer.transition):
                    # Append the remaining actions of the transition
                    if not new_fl.transition.terminator:
Maxime Perrotin's avatar
Maxime Perrotin committed
595
596
                        new_fl.transition.actions.extend(trans.actions
                                          [slice(idx + 1, len(trans.actions))])
597
598
                        new_fl.transition.terminator = trans.terminator
                    yield new_fl
599
600
601
602
603
604
605
606
607


def sorted_fields(atype):
    ''' Return the sorted list of a SEQUENCE or CHOICE type fields '''
    if atype.kind not in ('SequenceType', 'ChoiceType'):
        raise TypeError('Not a SEQUENCE nor a CHOICE')
    tmp = ([k, val.Line, val.CharPositionInLine]
             for k, val in atype.Children.viewitems())
    return (x[0] for x in sorted(tmp, key=operator.itemgetter(1,2)))