Finite automaton

About this software

This package is a collection of the code generators, builders, helper functions (intervals, ranges, statements, branching, binary search, etc.) for creating various finite state machines.

Currently, this includes the following components:

  • Binary match generator
  • Codegen mixin
  • DFA
  • DFA to Trie converter
  • Epsilon-NFA to NFA converter
  • Expression based binary search generator
  • Interval combiner
  • NFA
  • NFA to DFA converter
  • Range helper functions
  • Sparse list
  • Statement based binary search generator
  • String escaper
  • Trie
  • Type helper functions

Note:
DFA, NFA and Trie are experimental features and are subject to change.

Examples

example_binary_match_generator.dart

import 'package:finite_automaton/binary_search_generator.dart';

import 'utils.dart';

void main(List<String> args) {
  printHeader('Example: Binary match generator');
  printText('The data is a list of ranges to check');
  printText('Output is a source code of the `predicate`');

  final lists = [
    [
      (9, 10),
      (13, 13),
      (32, 32),
    ],
    [
      (65, 90),
      (97, 122),
    ],
    [
      (48, 57),
      (65, 90),
      (97, 122),
    ],
    [
      (48, 57),
      (65, 90),
      (97, 122),
      (95, 95),
    ],
    [
      (36, 36),
      (48, 57),
      (65, 90),
      (97, 122),
      (95, 95),
    ]
  ];

  for (var list in lists) {
    final source = BinaryMatchGenerator(ranges: list, name: 'c').generate();

    printText('Data:');
    printList(list);
    printText('Generated code:');
    printCode(source);
  }
}

Output:

----------------------------------------
Example: Binary match generator
----------------------------------------

The data is a list of ranges to check

Output is a source code of the predicate

Data:

(9, 10), (13, 13), (32, 32)

Generated code:

(c < 13 ? c >= 9 && c <= 10 : !(c > 13) || c == 32)

Data:

(65, 90), (97, 122)

Generated code:

c <= 122 && (c >= 97 || c >= 65 && c <= 90)

Data:

(48, 57), (65, 90), (97, 122)

Generated code:

(c < 65 ? c >= 48 && c <= 57 : !(c > 90) || c >= 97 && c <= 122)

Data:

(48, 57), (65, 90), (97, 122), (95, 95)

Generated code:

(c < 95 ? (c < 65 ? c >= 48 && c <= 57 : c <= 90) : !(c > 95) || c >= 97 && c <= 122)

Data:

(36, 36), (48, 57), (65, 90), (97, 122), (95, 95)

Generated code:

(c < 95 ? (c < 48 ? c == 36 : !(c > 57) || c >= 65 && c <= 90) : !(c > 95) || c >= 97 && c <= 122)

example_codegen_mixin.dart

import 'package:finite_automaton/codegen_mixin.dart';

import 'utils.dart';

void main(List<String> args) {
  printHeader('Example: Codegen mixin');
  final source = _Generator().generate();
  printCode(source);
}

class _Generator with CodegenMixin {
  String generate() {
    _generate();
    return getSource();
  }

  void _generate() {
    declare('a', '0');
    declare('b', '1', isFinal: false);
    declare('c', '1', isConst: true);
    declare('c', null, type: 'String');
    openIf('c == 1');
    stmt('print(1)');
    elseIf('c != null');
    stmt("print('not null')");
    else$();
    stmt("print('null')");
    closeBlock();

    assign('c', '3');

    openFunction(
      name: 'func',
      returnType: 'int',
      positional: [
        ('int', 'x'),
      ],
      named: [
        ('int', 'y', ''),
        ('bool', 'z', 'true'),
      ],
    );
    label$('outer');
    openWhile('true');
    break$('outer');
    closeBlock();
    closeBlock();

    openBlock('switch (c) {');
    for (var i = 0; i < 3; i++) {
      openBlock('case $i:');
      assign('d', '$i');
      break$();
      closeBlock('');
    }
    closeBlock();
  }
}

Output:

----------------------------------------
Example: Codegen mixin
----------------------------------------

final a = 0;
var b = 1;
const c = 1;
final String c;
if (c == 1) {
  print(1);
} else if (c != null) {
  print('not null');
} else {
  print('null');
}
c = 3;
int func(int x, {int y, bool z = true}) {
  outer:
  while (true) {
    break outer;
  }
}
switch (c) {
  case 0:
    d = 0;
    break;
  case 1:
    d = 1;
    break;
  case 2:
    d = 2;
    break;
}

example_expression_based_binary_search_generator.dart

import 'package:finite_automaton/binary_search_generator.dart';

import 'utils.dart';

void main(List<String> args) {
  printHeader('Example: Expression based binary search generator');
  printText('Data is a map of ranges and actions');
  printText("Output is a source code of the `select` expression");

  final map = {
    (0, 9): 0,
    (10, 19): 10,
    (20, 29): 20,
    (30, 39): 30,
    (40, 49): 40,
    (50, 59): 50,
    (60, 69): 60,
  };

  printText('Data:');
  printMap(map);
  final source = TernaryBinarySearchGenerator(
    callback: (entry) => '${entry.value}',
    defaultValue: '-1',
    map: map,
    name: 'c',
  ).generate();
  printText('Generated code:');
  printCode(source);
}

Output:

----------------------------------------
Example: Expression based binary search generator
----------------------------------------

Data is a map of ranges and actions

Output is a source code of the select expression

Data:

(0, 9): 0, (10, 19): 10, (20, 29): 20, (30, 39): 30, (40, 49): 40, (50, 59): 50, (60, 69): 60

Generated code:

(c < 30 ? (c < 10 ? (c >= 0 ? 0 : -1) : (c > 19 ? 20 : 10)) : (c > 39 ? (c < 50 ? 40 : (c > 59 ? (c <= 69 ? 60 : -1) : 50)) : 30))

example_interval_combiner.dart

import 'package:finite_automaton/interval_combiner.dart';

import 'utils.dart';

void main(List<String> args) {
  printHeader('Example: Interval combiner');
  printText('Data is a list of the intervals (ranges and values)');
  printText("Output is a list of new intervals");

  final list = [
    ((0, 4), 'A'),
    ((3, 6), 'B'),
    ((5, 8), 'C'),
    ((7, 10), 'A'),
  ];

  final intervals =
      list.map((e) => Interval(e.$1.$1, e.$1.$2, {e.$2})).toList();
  var newIntervals = IntervalCombiner<String>(intervals: intervals).combine();
  printText('Intervals:');
  printList(intervals);
  printText('Combined intervals:');
  printList(newIntervals);
  newIntervals.add(Interval(9, 10, {'D'}));
  newIntervals = IntervalCombiner<String>(intervals: newIntervals).combine();
  printText('Combined intervals:');
  printList(newIntervals);
}

Output:

----------------------------------------
Example: Interval combiner
----------------------------------------

Data is a list of the intervals (ranges and values)

Output is a list of new intervals

Intervals:

(0, 4, {A}), (3, 6, {B}), (5, 8, {C}), (7, 10, {A})

Combined intervals:

(0, 2, {A}), (3, 4, {A, B}), (5, 6, {B, C}), (7, 8, {C, A}), (9, 10, {A})

Combined intervals:

(0, 2, {A}), (3, 4, {A, B}), (5, 6, {B, C}), (7, 8, {C, A}), (9, 10, {A, D})

example_sparse_list.dart

import 'package:finite_automaton/sparse_list.dart';

import 'utils.dart';

void main(List<String> args) {
  printHeader('Example: Sparse list');

  final data = [
    ((0, 4), {'A'}),
    ((3, 6), {'B'}),
    ((5, 8), {'C'}),
    ((7, 10), {'A'}),
  ];

  printText('Initial data:');
  printList(data);
  final list = SparseList<String>();
  list.addAll(data);
  _printElements(list);
  list.add((10, 11), {'Element 10-11'});
  _printElements(list);
}

void _printElements<E>(SparseList<E> list) {
  final intervals = list.intervals;
  if (intervals.isEmpty) {
    printText('No intervals');
  }

  final first = intervals.first;
  final last = intervals.last;
  final start = first.start;
  final end = last.end;
  printText('Intervals:');
  printList(list.intervals, '\n');
  final buffer = StringBuffer();
  for (var i = start - 1; i < end + 2; i++) {
    final values = list.getValues(i);
    buffer.writeln('$i: $values');
  }

  printText('Elements:');
  printCode(buffer.toString());
}

Output:

----------------------------------------
Example: Sparse list
----------------------------------------

Initial data:

((0, 4), {A}), ((3, 6), {B}), ((5, 8), {C}), ((7, 10), {A})

Intervals:

(0, 2, {A})
(3, 4, {A, B})
(5, 6, {B, C})
(7, 8, {C, A})
(9, 10, {A})

Elements:

-1: null
0: {A}
1: {A}
2: {A}
3: {A, B}
4: {A, B}
5: {B, C}
6: {B, C}
7: {C, A}
8: {C, A}
9: {A}
10: {A}
11: null

Intervals:

(0, 2, {A})
(3, 4, {A, B})
(5, 6, {B, C})
(7, 8, {C, A})
(9, 9, {A})
(10, 10, {A, Element 10-11})
(11, 11, {Element 10-11})

Elements:

-1: null
0: {A}
1: {A}
2: {A}
3: {A, B}
4: {A, B}
5: {B, C}
6: {B, C}
7: {C, A}
8: {C, A}
9: {A}
10: {A, Element 10-11}
11: {Element 10-11}
12: null

example_state_machine.dart

import 'package:finite_automaton/binary_search_generator.dart';
import 'package:finite_automaton/codegen_mixin.dart';

import 'utils.dart';

void main(List<String> args) {
  printHeader('Example: State machine');
  final map = <(State, Event), State>{
    (State.draft, Event.updateDocument): State.draft,
    (State.draft, Event.beginReview): State.review,
    (State.review, Event.submit): State.submittedToClient,
    (State.review, Event.changedNeeded): State.changesRequested,
    (State.submittedToClient, Event.accept): State.approved,
    (State.submittedToClient, Event.decline): State.declined,
    (State.declined, Event.restartReview): State.review,
    (State.changesRequested, Event.reject): State.review,
    (State.changesRequested, Event.accept): State.draft,
  };

  final source = _Generator(map: map).generate();
  printCode(source);
}

enum Event {
  accept,
  approve,
  beginReview,
  changedNeeded,
  decline,
  reject,
  restartReview,
  submit,
  updateDocument,
}

enum State {
  approved,
  changesRequested,
  declined,
  draft,
  review,
  submittedToClient,
}

class _Generator with CodegenMixin {
  static const _event = 'e';

  static const _state = 's';

  final Map<(State, Event), State> map;

  _Generator({required this.map});

  String generate() {
    _generate();
    return getSource();
  }

  void _generate() {
    writeln('/// Super fast state machine');
    openFunction(
      name: 'getNextState',
      returnType: 'State?',
      positional: [
        ('State', 'state'),
        ('Event', 'event'),
      ],
    );
    declare(_state, 'state.index');
    declare(_event, 'event.index');
    final stateMap = <(int, int), State>{};
    for (final state in State.values) {
      final index = state.index;
      stateMap[(index, index)] = state;
    }

    final source = IfElseBinarySearchGenerator(
      callback: (entry) {
        final state = entry.value;
        final code = _generateTransitions(state);
        return code;
      },
      map: stateMap,
      name: _state,
    ).generate();
    writeln(source);
  }

  String _generateTransitions(State state) {
    final code = capture(0, () {
      writeln('// $state');
      final entries = map.entries.where((e) => e.key.$1 == state);
      if (entries.isEmpty) {
        writeln('// No transitions');
        return;
      }

      final transitions = <(int, int), State>{};
      for (final entry in entries) {
        final key = entry.key;
        final next = key.$1;
        final event = key.$2;
        final index = event.index;
        transitions[(index, index)] = next;
      }
      final source = IfElseBinarySearchGenerator(
        callback: (entry) {
          final key = entry.key;
          final state = entry.value;
          final index = key.$1;
          final event = Event.values[index];
          return '''
// Handler for $event
return $state;''';
        },
        map: transitions,
        name: _event,
      ).generate();
      writeln(source);
    });

    return code;
  }
}

Output:

----------------------------------------
Example: State machine
----------------------------------------

/// Super fast state machine
State? getNextState(State state, Event event) {
  final s = state.index;
  final e = event.index;
  if (s < 3) {
    if (s < 1) {
      if (s == 0) {
        // State.approved
        // No transitions
      }
    } else if (s > 1) {
      // State.declined
      if (e == 6) {
        // Handler for Event.restartReview
        return State.declined;
      }
    } else {
      // State.changesRequested
      if (e == 0) {
        // Handler for Event.accept
        return State.changesRequested;
      } else if (e == 5) {
        // Handler for Event.reject
        return State.changesRequested;
      }
    }
  } else if (s > 3) {
    if (s < 5) {
      // State.review
      if (e == 3) {
        // Handler for Event.changedNeeded
        return State.review;
      } else if (e == 7) {
        // Handler for Event.submit
        return State.review;
      }
    } else if (s == 5) {
      // State.submittedToClient
      if (e == 0) {
        // Handler for Event.accept
        return State.submittedToClient;
      } else if (e == 4) {
        // Handler for Event.decline
        return State.submittedToClient;
      }
    }
  } else {
    // State.draft
    if (e == 2) {
      // Handler for Event.beginReview
      return State.draft;
    } else if (e == 8) {
      // Handler for Event.updateDocument
      return State.draft;
    }
  }

example_statement_based_binary_search_generator.dart

import 'package:finite_automaton/binary_search_generator.dart';

import 'utils.dart';

void main(List<String> args) {
  printHeader('Example: Statement based binary search generator');
  printText('Data is a map of ranges and actions');
  printText('Output is a source code of the `if/else if/else` statements');

  final map = {
    (0, 9): 0,
    (10, 19): 10,
    (20, 29): 20,
    (30, 39): 30,
    (40, 49): 40,
    (50, 59): 50,
    (60, 69): 60,
  };

  printText('Data:');
  printMap(map);
  final source = IfElseBinarySearchGenerator(
    callback: (entry) => '// action for ${entry.key}',
    map: map,
    name: 'c',
  ).generate();
  printText('Generated code:');
  printCode(source);
}

Output:

----------------------------------------
Example: Statement based binary search generator
----------------------------------------

Data is a map of ranges and actions

Output is a source code of the if/else if/else statements

Data:

(0, 9): 0, (10, 19): 10, (20, 29): 20, (30, 39): 30, (40, 49): 40, (50, 59): 50, (60, 69): 60

Generated code:

if (c < 30) {
  if (c < 10) {
    if (c >= 0) {
      // action for (0, 9)
    }
  } else if (c > 19) {
    // action for (20, 29)
  } else {
    // action for (10, 19)
  }
} else if (c > 39) {
  if (c < 50) {
    // action for (40, 49)
  } else if (c > 59) {
    if (c <= 69) {
      // action for (60, 69)
    }
  } else {
    // action for (50, 59)
  }
} else {
  // action for (30, 39)
}

Libraries

binary_search_generator
codegen_mixin
dfa
dfa_to_trie_converter
enfa_to_nfa_converter
interval_combiner
nfa
nfa_to_dfa_converter
range
range_helper
sparse_list
string_escaper
trie
type_helper