--- a/.hgignore	Fri Feb 19 18:07:17 2016 +0300
+++ b/.hgignore	Fri Apr 22 13:08:08 2016 +0300
@@ -15,3 +15,6 @@
 Implab.Diagnostics.Interactive/obj/
 MonoPlay/bin/
 MonoPlay/obj/
+Implab.Test/Implab.Format.Test/bin/
+Implab.Test/Implab.Format.Test/obj/
+*.suo

--- a/Implab.Test/Implab.Format.Test/Implab.Format.Test.csproj	Fri Feb 19 18:07:17 2016 +0300
+++ b/Implab.Test/Implab.Format.Test/Implab.Format.Test.csproj	Fri Apr 22 13:08:08 2016 +0300
@@ -10,6 +10,7 @@
     <RootNamespace>Implab.Format.Test</RootNamespace>
     <AssemblyName>Implab.Format.Test</AssemblyName>
     <TargetFrameworkVersion>v4.5</TargetFrameworkVersion>
+    <ReleaseVersion>0.2</ReleaseVersion>
   </PropertyGroup>
   <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
     <DebugSymbols>true</DebugSymbols>
@@ -32,7 +33,7 @@
   <ItemGroup>
     <Reference Include="System" />
     <Reference Include="nunit.framework">
-      <HintPath>..\..\packages\NUnit.3.0.1\lib\net45\nunit.framework.dll</HintPath>
+      <HintPath>..\..\packages\NUnit.2.6.4\lib\nunit.framework.dll</HintPath>
     </Reference>
   </ItemGroup>
   <ItemGroup>
@@ -40,6 +41,12 @@
   </ItemGroup>
   <Import Project="$(MSBuildBinPath)\Microsoft.CSharp.targets" />
   <ItemGroup>
+    <ProjectReference Include="..\..\Implab\Implab.csproj">
+      <Project>{F550F1F8-8746-4AD0-9614-855F4C4B7F05}</Project>
+      <Name>Implab</Name>
+    </ProjectReference>
+  </ItemGroup>
+  <ItemGroup>
     <None Include="packages.config" />
   </ItemGroup>
 </Project>
\ No newline at end of file

--- a/Implab.Test/Implab.Format.Test/JsonTests.cs	Fri Feb 19 18:07:17 2016 +0300
+++ b/Implab.Test/Implab.Format.Test/JsonTests.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -1,11 +1,87 @@
 using NUnit.Framework;
 using System;
+using Implab.Formats.JSON;
+using Implab.Automaton;
 
 namespace Implab.Format.Test {
-    [TestFixture()]
+    [TestFixture]
     public class JsonTests {
-        [Test()]
-        public void TestCase() {
+        [Test]
+        public void TestScannerValidTokens() {
+            using (var scanner = new JSONScanner(@"9123, -123, 0, 0.1, -0.2, -0.1e3, 1.3E-3, ""some \t\n\u0020 text"", literal []{}:")) {
+
+                Tuple<JsonTokenType,object>[] expexted = {
+                    new Tuple<JsonTokenType,object>(JsonTokenType.Number, 9123d),
+                    new Tuple<JsonTokenType,object>(JsonTokenType.ValueSeparator, ", "),
+                    new Tuple<JsonTokenType,object>(JsonTokenType.Number, -123d),
+                    new Tuple<JsonTokenType,object>(JsonTokenType.ValueSeparator, ", "),
+                    new Tuple<JsonTokenType,object>(JsonTokenType.Number, 0d),
+                    new Tuple<JsonTokenType,object>(JsonTokenType.ValueSeparator, ", "),
+                    new Tuple<JsonTokenType,object>(JsonTokenType.Number, 0.1d),
+                    new Tuple<JsonTokenType,object>(JsonTokenType.ValueSeparator, ", "),
+                    new Tuple<JsonTokenType,object>(JsonTokenType.Number, -0.2d),
+                    new Tuple<JsonTokenType,object>(JsonTokenType.ValueSeparator, ", "),
+                    new Tuple<JsonTokenType,object>(JsonTokenType.Number, -0.1e3d),
+                    new Tuple<JsonTokenType,object>(JsonTokenType.ValueSeparator, ", "),
+                    new Tuple<JsonTokenType,object>(JsonTokenType.Number, 1.3E-3d),
+                    new Tuple<JsonTokenType,object>(JsonTokenType.ValueSeparator, ", "),
+                    new Tuple<JsonTokenType,object>(JsonTokenType.String, "some \t\n  text"),
+                    new Tuple<JsonTokenType,object>(JsonTokenType.ValueSeparator, ", "),
+                    new Tuple<JsonTokenType,object>(JsonTokenType.Literal, "literal"),
+                    new Tuple<JsonTokenType,object>(JsonTokenType.BeginArray, " ["),
+                    new Tuple<JsonTokenType,object>(JsonTokenType.EndArray, "]"),
+                    new Tuple<JsonTokenType,object>(JsonTokenType.BeginObject, "{"),
+                    new Tuple<JsonTokenType,object>(JsonTokenType.EndObject, "}"),
+                    new Tuple<JsonTokenType,object>(JsonTokenType.NameSeparator, ":")
+                };
+
+                object value;
+                JsonTokenType tokenType;
+                for (var i = 0; i < expexted.Length; i++) {
+                
+                    Assert.IsTrue(scanner.ReadToken(out value, out tokenType));
+                    Assert.AreEqual(expexted[i].Item1, tokenType);
+                    Assert.AreEqual(expexted[i].Item2, value);
+                }
+
+                Assert.IsFalse(scanner.ReadToken(out value, out tokenType));
+            }
+        }
+
+        [Test]
+        public void TestScannerBadTokens() {
+            var bad = new [] {
+                " 1",
+                " literal",
+                " \"",
+                "\"unclosed string",
+                "1.bad",
+                "001", // should be read as three numbers
+                "--10",
+                "+10",
+                "1.0.0",
+                "1e1.0",
+                "l1teral0",
+                ".123",
+                "-.123"
+            };
+
+            foreach (var json in bad)
+                using (var scanner = new JSONScanner(json)) {
+                    try {
+                        object value;
+                        JsonTokenType token;
+                        scanner.ReadToken(out value, out token);
+                        if (!Object.Equals(value,json)) {
+                            Console.WriteLine("'{0}' is read as {1}", json, value is String ? String.Format("'{0}'", value) : value );
+                            continue;
+                        }
+                        Assert.Fail("Token '{0}' shouldn't pass", json);
+                    } catch (ParserException e) {
+                        Console.WriteLine(e.Message);
+                    }
+                }
+            
         }
     }
 }

--- a/Implab.Test/Implab.Format.Test/packages.config	Fri Feb 19 18:07:17 2016 +0300
+++ b/Implab.Test/Implab.Format.Test/packages.config	Fri Apr 22 13:08:08 2016 +0300
@@ -1,4 +1,4 @@
 <?xml version="1.0" encoding="utf-8"?>
 <packages>
-  <package id="NUnit" version="3.0.1" targetFramework="net45" />
+  <package id="NUnit" version="2.6.4" targetFramework="net45" />
 </packages>
\ No newline at end of file

--- a/Implab.Test/Implab.Test.csproj	Fri Feb 19 18:07:17 2016 +0300
+++ b/Implab.Test/Implab.Test.csproj	Fri Apr 22 13:08:08 2016 +0300
@@ -62,8 +62,10 @@
   </ItemGroup>
   <ItemGroup>
     <Compile Include="AsyncTests.cs" />
+    <Compile Include="CancelationTests.cs" />
     <Compile Include="PromiseHelper.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
+    <Compile Include="RunnableComponentTests.cs" />
   </ItemGroup>
   <ItemGroup>
     <ProjectReference Include="..\Implab\Implab.csproj">

--- a/Implab.Test/Implab.Test.mono.csproj	Fri Feb 19 18:07:17 2016 +0300
+++ b/Implab.Test/Implab.Test.mono.csproj	Fri Apr 22 13:08:08 2016 +0300
@@ -58,6 +58,7 @@
     <Compile Include="PromiseHelper.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
     <Compile Include="CancelationTests.cs" />
+    <Compile Include="RunnableComponentTests.cs" />
   </ItemGroup>
   <ItemGroup>
     <ProjectReference Include="..\Implab\Implab.csproj">

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab.Test/RunnableComponentTests.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,195 @@
+using System;
+using System.Reflection;
+using System.Threading;
+using Implab.Parallels;
+using Implab.Components;
+
+#if MONO
+
+using NUnit.Framework;
+using TestClassAttribute = NUnit.Framework.TestFixtureAttribute;
+using TestMethodAttribute = NUnit.Framework.TestAttribute;
+using AssertFailedException = NUnit.Framework.AssertionException;
+#else
+
+using Microsoft.VisualStudio.TestTools.UnitTesting;
+
+#endif
+
+namespace Implab.Test {
+    [TestClass]
+    public class RunnableComponentTests {
+
+        static void ShouldThrow(Action action) {
+            try {
+                action();
+                Assert.Fail();
+            } catch (AssertFailedException) {
+                throw;
+            } catch {
+            }
+        }
+
+        class Runnable : RunnableComponent {
+            public Runnable(bool initialized) : base(initialized) {
+            }
+                
+            public Action MockInit {
+                get;
+                set;
+            }
+
+            public Func<IPromise> MockStart {
+                get;
+                set;
+            }
+
+            public Func<IPromise> MockStop {
+                get;
+                set;
+            }
+
+            protected override IPromise OnStart() {
+                return MockStart != null ? MockStart() : base.OnStart();
+            }
+
+            protected override IPromise OnStop() {
+                return MockStop != null ? MockStop() : base.OnStart();
+            }
+
+            protected override void OnInitialize() {
+                if (MockInit != null)
+                    MockInit();
+            }
+        }
+
+        [TestMethod]
+        public void NormalFlowTest() {
+            var comp = new Runnable(false);
+
+            Assert.AreEqual(ExecutionState.Created, comp.State);
+
+            comp.Init();
+
+            Assert.AreEqual(ExecutionState.Ready, comp.State);
+
+            comp.Start().Join(1000);
+
+            Assert.AreEqual(ExecutionState.Running, comp.State);
+
+            comp.Stop().Join(1000);
+
+            Assert.AreEqual(ExecutionState.Disposed, comp.State);
+
+        }
+
+        [TestMethod]
+        public void InitFailTest() {
+            var comp = new Runnable(false) {
+                MockInit = () => {
+                    throw new Exception("BAD");
+                }
+            };
+
+            ShouldThrow(() => comp.Start());
+            ShouldThrow(() => comp.Stop());
+            Assert.AreEqual(ExecutionState.Created, comp.State);
+
+            ShouldThrow(comp.Init);
+
+            Assert.AreEqual(ExecutionState.Failed, comp.State);
+
+            ShouldThrow(() => comp.Start());
+            ShouldThrow(() => comp.Stop());
+            Assert.AreEqual(ExecutionState.Failed, comp.State);
+
+            comp.Dispose();
+            Assert.AreEqual(ExecutionState.Disposed, comp.State);
+        }
+
+        [TestMethod]
+        public void DisposedTest() {
+
+            var comp = new Runnable(false);
+            comp.Dispose();
+
+            ShouldThrow(() => comp.Start());
+            ShouldThrow(() => comp.Stop());
+            ShouldThrow(comp.Init);
+
+            Assert.AreEqual(ExecutionState.Disposed, comp.State);
+        }
+
+        [TestMethod]
+        public void StartCancelTest() {
+            var comp = new Runnable(true) {
+                MockStart = () => PromiseHelper.Sleep(100000, 0)
+            };
+
+            var p = comp.Start();
+            Assert.AreEqual(ExecutionState.Starting, comp.State);
+            p.Cancel();
+            ShouldThrow(() => p.Join(1000));
+            Assert.AreEqual(ExecutionState.Failed, comp.State);
+
+            Assert.IsInstanceOfType(comp.LastError, typeof(OperationCanceledException));
+
+            comp.Dispose();
+        }
+
+        [TestMethod]
+        public void StartStopTest() {
+            var stop = new Signal();
+            var comp = new Runnable(true) {
+                MockStart = () => PromiseHelper.Sleep(100000, 0),
+                MockStop = () => AsyncPool.RunThread(stop.Wait)
+            };
+
+            var p1 = comp.Start();
+            var p2 = comp.Stop();
+            // should enter stopping state
+
+            ShouldThrow(p1.Join);
+            Assert.IsTrue(p1.IsCancelled);
+            Assert.AreEqual(ExecutionState.Stopping, comp.State);
+
+            stop.Set();
+            p2.Join(1000);
+            Assert.AreEqual(ExecutionState.Disposed, comp.State);
+        }
+
+        [TestMethod]
+        public void StartStopFailTest() {
+            var comp = new Runnable(true) {
+                MockStart = () => PromiseHelper.Sleep(100000, 0).Then(null,null,x => { throw new Exception("I'm dead"); })
+            };
+
+            comp.Start();
+            var p = comp.Stop();
+            // if Start fails to cancel, should fail to stop
+            ShouldThrow(() => p.Join(1000));
+            Assert.AreEqual(ExecutionState.Failed, comp.State);
+            Assert.IsNotNull(comp.LastError);
+            Assert.AreEqual("I'm dead", comp.LastError.Message);
+        }
+
+        [TestMethod]
+        public void StopCancelTest() {
+            var comp = new Runnable(true) {
+                MockStop = () => PromiseHelper.Sleep(100000, 0)
+            };
+
+            comp.Start();
+            var p = comp.Stop();
+            Assert.AreEqual(ExecutionState.Stopping, comp.State);
+            p.Cancel();
+            ShouldThrow(() => p.Join(1000));
+            Assert.AreEqual(ExecutionState.Failed, comp.State);
+            Assert.IsInstanceOfType(comp.LastError, typeof(OperationCanceledException));
+
+            comp.Dispose();
+        }
+
+    }
+}
+

--- a/Implab/AbstractEvent.cs	Fri Feb 19 18:07:17 2016 +0300
+++ b/Implab/AbstractEvent.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -78,13 +78,9 @@
         /// <exception cref="InvalidOperationException">Данное обещание уже выполнено</exception>
         protected void SetError(Exception error) {
             if (BeginTransit()) {
-                if (error is OperationCanceledException) {
-                    m_error = error.InnerException;
-                    CompleteTransit(CANCELLED_STATE);
-                } else {
-                    m_error = error is PromiseTransientException ? error.InnerException : error;
-                    CompleteTransit(REJECTED_STATE);
-                }
+                m_error = error;
+                CompleteTransit(REJECTED_STATE);
+
                 Signal();
             } else {
                 WaitTransition();
@@ -139,11 +135,11 @@
                 case SUCCEEDED_STATE:
                     return;
                 case CANCELLED_STATE:
-                    throw new OperationCanceledException();
+                    throw new OperationCanceledException("The operation has been cancelled", m_error);
                 case REJECTED_STATE:
                     throw new TargetInvocationException(m_error);
                 default:
-                    throw new ApplicationException(String.Format("Invalid promise state {0}", m_state));
+                    throw new ApplicationException(String.Format("The promise state {0} is invalid", m_state));
             }
         }
         #endregion

--- a/Implab/AbstractPromise.cs	Fri Feb 19 18:07:17 2016 +0300
+++ b/Implab/AbstractPromise.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -134,8 +134,8 @@
         }
 
         protected void SetResult() {
-            BeginSetResult();
-            EndSetResult();
+            if(BeginSetResult())
+                EndSetResult();
         }
     }
 }

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/AbstractTask.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,45 @@
+using System;
+using System.Threading;
+
+namespace Implab {
+    /// <summary>
+    /// Базовый класс для реализации задачь. Задача представляет собой некторое
+    /// действие, которое можно иницировать и обработать результат его выполнения
+    ///  в виде обещания, для этого оно реализует интерфейс <see cref="IPromise"/>.
+    /// </summary>
+    /// <remarks>
+    /// Данный класс определяет стандартное поведение при обработки результатов, в частности
+    /// обработку <see cref="System.OperationCanceledException"/> и <see cref="PromiseTransientException"/>
+    /// </remarks>
+    public abstract class AbstractTask : AbstractPromise {
+        int m_cancelationLock;
+
+        /// <summary>
+        /// Получает эксклюзивное право отмены задания, используется для отмены задания до начала его выполнения.
+        /// </summary>
+        /// <returns><c>true</c>, if cancelation was locked, <c>false</c> otherwise.</returns>
+        protected bool LockCancelation() {
+            return 0 == Interlocked.CompareExchange(ref m_cancelationLock, 1, 0);
+        }
+
+
+
+        protected void SetErrorInternal(Exception error) {
+            // unwrap 
+            while (error is PromiseTransientException && error.InnerException != null)
+                error = error.InnerException;
+            
+            if (error is OperationCanceledException)
+                SetCancelled(error);
+            else
+                SetError(error);
+        }
+
+        protected void SetCancelledInternal(Exception reason) {
+            SetCancelled(
+                reason == null ? new OperationCanceledException() : reason is OperationCanceledException ? reason : new OperationCanceledException(null, reason)
+            );
+        }
+    }
+}
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/AbstractTaskT.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,36 @@
+using System;
+using System.Threading;
+
+namespace Implab {
+    public abstract class AbstractTask<T> : AbstractPromise<T> {
+        int m_cancelationLock;
+
+        /// <summary>
+        /// Получает эксклюзивное право отмены задания, используется для отмены задания до начала его выполнения.
+        /// </summary>
+        /// <returns><c>true</c>, if cancelation was locked, <c>false</c> otherwise.</returns>
+        protected bool LockCancelation() {
+            return 0 == Interlocked.CompareExchange(ref m_cancelationLock, 1, 0);
+        }
+
+
+
+        protected void SetErrorInternal(Exception error) {
+            // unwrap 
+            while (error is PromiseTransientException && error.InnerException != null)
+                error = error.InnerException;
+
+            if (error is OperationCanceledException)
+                SetCancelled(error);
+            else
+                SetError(error);
+        }
+
+        protected void SetCancelledInternal(Exception reason) {
+            SetCancelled(
+                reason == null ? new OperationCanceledException() : reason is OperationCanceledException ? reason : new OperationCanceledException(null, reason)
+            );
+        }
+    }
+}
+

--- a/Implab/ActionChainTask.cs	Fri Feb 19 18:07:17 2016 +0300
+++ b/Implab/ActionChainTask.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -4,6 +4,15 @@
     public class ActionChainTask : ActionChainTaskBase, IDeferred {
         readonly Func<IPromise> m_task;
 
+        /// <summary>
+        /// Initializes a new instance of the <see cref="Implab.ActionChainTask"/> class.
+        /// </summary>
+        /// <param name="task">The operation which will be performed when the <see cref="Resolve()"/> is called.</param>
+        /// <param name="error">The error handler which will invoke when the <see cref="Reject(Exception)"/> is called or when the task fails with an error.</param>
+        /// <param name="cancel">The cancellation handler.</param>
+        /// <param name="autoCancellable">If set to <c>true</c> will automatically accept
+        ///  all cancel requests before the task is started with <see cref="Resolve()"/>,
+        /// after that all requests are directed to the task.</param>
         public ActionChainTask(Func<IPromise> task, Func<Exception, IPromise> error, Func<Exception, IPromise> cancel, bool autoCancellable) : base(error,cancel, autoCancellable) {
             m_task = task;
         }
@@ -12,8 +21,10 @@
             if (m_task != null && LockCancelation()) {
                 try {
                     var p = m_task();
-                    p.On(SetResult, HandleErrorInternal, SetCancelled);
+                    p.On(SetResult, HandleErrorInternal, HandleCancelInternal);
                     CancellationRequested(p.Cancel);
+                } catch (OperationCanceledException reason){
+                    HandleCancelInternal(reason);
                 } catch(Exception err) {
                     HandleErrorInternal(err);
                 }

--- a/Implab/ActionChainTaskBase.cs	Fri Feb 19 18:07:17 2016 +0300
+++ b/Implab/ActionChainTaskBase.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -2,12 +2,10 @@
 using System.Threading;
 
 namespace Implab {
-    public class ActionChainTaskBase : AbstractPromise {
+    public class ActionChainTaskBase : AbstractTask {
         readonly Func<Exception, IPromise> m_error;
         readonly Func<Exception, IPromise> m_cancel;
 
-        int m_cancelationLock;
-
         protected ActionChainTaskBase(Func<Exception, IPromise> error, Func<Exception, IPromise> cancel, bool autoCancellable) {
             m_error = error;
             m_cancel = cancel;
@@ -20,19 +18,28 @@
                 HandleErrorInternal(error);
         }
 
-
+        public override void CancelOperation(Exception reason) {
+            if (LockCancelation())
+                // отмена вызвана до начала выполнения задачи
+                HandleCancelInternal(reason);
+        }
 
-        public override void CancelOperation(Exception reason) {
-            if (LockCancelation()) {
-                if (m_cancel != null) {
-                    try {
-                        m_cancel(reason).On(SetResult, SetError, SetCancelled);
-                    } catch (Exception err) {
-                        HandleErrorInternal(err);
-                    }
-                } else {
-                    SetCancelled(reason);
+        protected void HandleCancelInternal(Exception reason) {
+            if (m_cancel != null) {
+                try {
+                    // вызываем обработчик отмены
+                    var p = m_cancel(reason);
+                    p.On(SetResult, HandleErrorInternal, SetCancelledInternal);
+                    // сообщаем асинхронной операции, что клиент уже не хочет получать результат
+                    // т.е. если он инициировал отмену, задача отменилась, вызвался обрабочик отмены
+                    // отбработчику сообщили, что результат уже не нужен и уже сам обработчик решает
+                    // отдавать ли результат или подтвердить отмену (или вернуть ошибку).
+                    CancellationRequested(p.Cancel);
+                } catch (Exception err) {
+                    HandleErrorInternal(err);
                 }
+            } else {
+                HandleErrorInternal(reason ?? new OperationCanceledException());
             }
         }
 
@@ -40,19 +47,16 @@
             if (m_error != null) {
                 try {
                     var p = m_error(error);
-                    p.On(SetResult,SetError,SetCancelled);
+                    p.On(SetResult, SetErrorInternal, SetCancelledInternal);
                     CancellationRequested(p.Cancel);
                 } catch (Exception err) {
-                    SetError(err);
+                    SetErrorInternal(error);
                 }
             } else {
-                SetError(error);
+                SetErrorInternal(error);
             }
         }
 
-        protected bool LockCancelation() {
-            return 0 == Interlocked.CompareExchange(ref m_cancelationLock, 1, 0);
-        }
     }
 }
 

--- a/Implab/ActionChainTaskT.cs	Fri Feb 19 18:07:17 2016 +0300
+++ b/Implab/ActionChainTaskT.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -12,8 +12,10 @@
             if (m_task != null && LockCancelation()) {
                 try {
                     var p = m_task(value);
-                    p.On(SetResult, HandleErrorInternal, SetCancelled);
+                    p.On(SetResult, HandleErrorInternal, HandleCancelInternal);
                     CancellationRequested(p.Cancel);
+                } catch (OperationCanceledException reason) {
+                    HandleCancelInternal(reason);
                 } catch(Exception err) {
                     HandleErrorInternal(err);
                 }

--- a/Implab/ActionTask.cs	Fri Feb 19 18:07:17 2016 +0300
+++ b/Implab/ActionTask.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -12,6 +12,8 @@
                 try {
                     m_task();
                     SetResult();
+                } catch(OperationCanceledException reason) {
+                    HandleCancelInternal(reason);
                 } catch(Exception err) {
                     HandleErrorInternal(err);
                 }

--- a/Implab/ActionTaskBase.cs	Fri Feb 19 18:07:17 2016 +0300
+++ b/Implab/ActionTaskBase.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -1,13 +1,10 @@
 using System;
-using System.Threading;
 
 namespace Implab {
-    public class ActionTaskBase : AbstractPromise {
+    public class ActionTaskBase : AbstractTask {
         readonly Action<Exception> m_cancel;
         readonly Action<Exception> m_error;
 
-        int m_cancelationLock;
-
         protected ActionTaskBase( Action<Exception> error, Action<Exception> cancel, bool autoCancellable) {
             m_error = error;
             m_cancel = cancel;
@@ -21,37 +18,36 @@
                 HandleErrorInternal(error);
         }
 
+        public override void CancelOperation(Exception reason) {
+            if (LockCancelation())
+                HandleCancelInternal(reason);
+        }
+
         protected void HandleErrorInternal(Exception error) {
             if (m_error != null) {
                 try {
                     m_error(error);
                     SetResult();
                 } catch(Exception err) {
-                    SetError(err);
+                    SetErrorInternal(err);
                 }
             } else {
-                SetError(error);
+                SetErrorInternal(error);
             }
         }
 
-        public override void CancelOperation(Exception reason) {
-            if (LockCancelation()) {
-                if (m_cancel != null) {
-                    try {
-                        m_cancel(reason);
-                        SetResult();
-                    } catch (Exception err) {
-                        HandleErrorInternal(err);
-                    }
-                } else {
-                    SetCancelled(reason);
+        protected void HandleCancelInternal(Exception error) {
+            if (m_cancel != null) {
+                try {
+                    m_cancel(error);
+                    SetResult();
+                } catch(Exception err) {
+                    HandleErrorInternal(err);
                 }
+            } else {
+                HandleErrorInternal(error ?? new OperationCanceledException());
             }
         }
-
-        protected bool LockCancelation() {
-            return 0 == Interlocked.CompareExchange(ref m_cancelationLock, 1, 0);
-        }
     }
 }
 

--- a/Implab/ActionTaskT.cs	Fri Feb 19 18:07:17 2016 +0300
+++ b/Implab/ActionTaskT.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -12,6 +12,8 @@
                 try {
                     m_task(value);
                     SetResult();
+                } catch(OperationCanceledException reason) {
+                    HandleCancelInternal(reason);
                 } catch(Exception err) {
                     HandleErrorInternal(err);
                 }

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Automaton/AutomatonConst.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,9 @@
+
+namespace Implab.Automaton {
+    public static class AutomatonConst {
+        public const int UNREACHABLE_STATE = -1;
+
+        public const int UNCLASSIFIED_INPUT = 0;
+    }
+}
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Automaton/AutomatonTransition.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,33 @@
+using System;
+
+namespace Implab.Automaton {
+    public struct AutomatonTransition : IEquatable<AutomatonTransition> {
+        public readonly int s1;
+        public readonly int s2;
+        public readonly int edge;
+
+        public AutomatonTransition(int s1, int s2, int edge) {
+            this.s1 = s1;
+            this.s2 = s2;
+            this.edge = edge;
+        }
+
+
+        #region IEquatable implementation
+        public bool Equals(AutomatonTransition other) {
+            return other.s1 == s1 && other.s2 == s2 && other.edge == edge ;
+        }
+        #endregion
+
+        public override bool Equals(object obj) {
+            if (obj is AutomatonTransition)
+                return Equals((AutomatonTransition)obj);
+            return base.Equals(obj);
+        }
+
+        public override int GetHashCode() {
+            return s1 + s2 + edge;
+        }
+    }
+}
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Automaton/DFATable.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,348 @@
+using Implab;
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Diagnostics;
+using System.IO;
+using System.CodeDom.Compiler;
+using System.CodeDom;
+
+namespace Implab.Automaton {
+    public class DFATable : IDFATableBuilder {
+        int m_stateCount;
+        int m_symbolCount;
+        int m_initialState;
+
+        readonly HashSet<int> m_finalStates = new HashSet<int>();
+        readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>();
+
+
+        #region IDFADefinition implementation
+
+        public bool IsFinalState(int s) {
+            Safe.ArgumentInRange(s, 0, m_stateCount, "s");
+
+            return m_finalStates.Contains(s);
+        }
+
+        public IEnumerable<int> FinalStates {
+            get {
+                return m_finalStates;
+            }
+        }
+
+        public int StateCount {
+            get { return m_stateCount; }
+        }
+
+        public int AlphabetSize {
+            get { return m_symbolCount; }
+        }
+
+        public int InitialState {
+            get { return m_initialState; }
+        }
+
+        #endregion
+
+        public void SetInitialState(int s) {
+            Safe.ArgumentAssert(s >= 0, "s");
+            m_stateCount = Math.Max(m_stateCount, s + 1);
+            m_initialState = s;
+        }
+
+        public void MarkFinalState(int state) {
+            m_stateCount = Math.Max(m_stateCount, state + 1);
+            m_finalStates.Add(state);
+        }
+
+        public void Add(AutomatonTransition item) {
+            Safe.ArgumentAssert(item.s1 >= 0, "item");
+            Safe.ArgumentAssert(item.s2 >= 0, "item");
+            Safe.ArgumentAssert(item.edge >= 0, "item");
+
+            m_stateCount = Math.Max(m_stateCount, Math.Max(item.s1, item.s2) + 1);
+            m_symbolCount = Math.Max(m_symbolCount, item.edge + 1);
+
+            m_transitions.Add(item);
+        }
+
+        public void Clear() {
+            m_stateCount = 0;
+            m_symbolCount = 0;
+            m_finalStates.Clear();
+            m_transitions.Clear();
+        }
+
+        public bool Contains(AutomatonTransition item) {
+            return m_transitions.Contains(item);
+        }
+
+        public void CopyTo(AutomatonTransition[] array, int arrayIndex) {
+            m_transitions.CopyTo(array, arrayIndex);
+        }
+
+        public bool Remove(AutomatonTransition item) {
+            return m_transitions.Remove(item);
+        }
+
+        public int Count {
+            get {
+                return m_transitions.Count;
+            }
+        }
+
+        public bool IsReadOnly {
+            get {
+                return false;
+            }
+        }
+
+        public IEnumerator<AutomatonTransition> GetEnumerator() {
+            return m_transitions.GetEnumerator();
+        }
+
+        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
+            return GetEnumerator();
+        }
+
+        public void AddSymbol(int symbol) {
+            Safe.ArgumentAssert(symbol >= 0, "symbol");
+            m_symbolCount = Math.Max(symbol + 1, m_symbolCount);
+        }
+
+        public int[,] CreateTransitionTable() {
+            var table = new int[StateCount,AlphabetSize];
+
+            for (int i = 0; i < StateCount; i++)
+                for (int j = 0; j < AlphabetSize; j++)
+                    table[i, j] = AutomatonConst.UNREACHABLE_STATE;
+
+            foreach (var t in this)
+                table[t.s1,t.edge] = t.s2;
+
+            return table;
+        }
+
+        public bool[] CreateFinalStateTable() {
+            var table = new bool[StateCount];
+
+            foreach (var s in FinalStates)
+                table[s] = true;
+
+            return table;
+        }
+
+        /// <summary>Формирует множества конечных состояний перед началом работы алгоритма минимизации.</summary>
+        /// <remarks>
+        /// В процессе построения минимального автомата требуется разделить множество состояний,
+        /// на два подмножества - конечные состояния и все остальные, после чего эти подмножества
+        /// будут резделены на более мелкие. Иногда требуется гарантировать различия конечных сосотяний,
+        /// для этого необходимо переопределить даннцю фукнцию, для получения множеств конечных состояний.
+        /// </remarks>
+        /// <returns>The final states.</returns>
+        protected virtual IEnumerable<HashSet<int>> SplitFinalStates(IEnumerable<int> states) {
+            return new [] { new HashSet<int>(states) };
+        }
+
+        protected void Optimize(
+            IDFATableBuilder optimalDFA,
+            IDictionary<int,int> alphabetMap,
+            IDictionary<int,int> stateMap
+        ) {
+            Safe.ArgumentNotNull(optimalDFA, "dfa");
+            Safe.ArgumentNotNull(alphabetMap, "alphabetMap");
+            Safe.ArgumentNotNull(stateMap, "stateMap");
+
+
+            var setComparer = new CustomEqualityComparer<HashSet<int>>(
+                (x, y) => x.SetEquals(y),
+                s => s.Sum(x => x.GetHashCode())
+            );
+
+            var optimalStates = new HashSet<HashSet<int>>(setComparer);
+            var queue = new HashSet<HashSet<int>>(setComparer);
+
+            optimalStates.Add(new HashSet<int>(FinalStates));
+
+            var state = new HashSet<int>(
+                Enumerable
+                .Range(0, m_stateCount)
+                .Where(i => !m_finalStates.Contains(i))
+            );
+
+            optimalStates.Add(state);
+            queue.Add(state);
+
+            var rmap = m_transitions
+                .GroupBy(t => t.s2)
+                .ToDictionary(
+                    g => g.Key, // s2
+                    g => g.ToLookup(t => t.edge, t => t.s1)//.ToDictionary(p => p.Key)
+                );
+
+            while (queue.Count > 0) {
+                var stateA = queue.First();
+                queue.Remove(stateA);
+
+                for (int c = 0; c < m_symbolCount; c++) {
+                    var stateX = new HashSet<int>();
+                    foreach(var a in stateA.Where(rmap.ContainsKey))
+                        stateX.UnionWith(rmap[a][c]); // all states from wich the symbol 'c' leads to the state 'a'
+
+                    var tmp = optimalStates.ToArray();
+                    foreach (var stateY in tmp) {
+                        var stateR1 = new HashSet<int>(stateY);
+                        var stateR2 = new HashSet<int>(stateY);
+
+                        stateR1.IntersectWith(stateX);
+                        stateR2.ExceptWith(stateX);
+
+                        if (stateR1.Count > 0 && stateR2.Count > 0) {
+                            
+
+                            optimalStates.Remove(stateY);
+                            optimalStates.Add(stateR1);
+                            optimalStates.Add(stateR2);
+
+                            if (queue.Contains(stateY)) {
+                                queue.Remove(stateY);
+                                queue.Add(stateR1);
+                                queue.Add(stateR2);
+                            } else {
+                                queue.Add(stateR1.Count <= stateR2.Count ? stateR1 : stateR2);
+                            }
+                        }
+                    }
+                }
+            }
+
+            // дополнительно разбиваем конечные состояния
+            foreach (var final in optimalStates.Where(s => s.Overlaps(m_finalStates)).ToArray()) {
+                optimalStates.Remove(final);
+                foreach (var split in SplitFinalStates(final))
+                    optimalStates.Add(split);
+            }
+                
+
+            // карта получения оптимального состояния по соотвествующему ему простому состоянию
+            var nextState = 0;
+            foreach (var item in optimalStates) {
+                var id = nextState++;
+                foreach (var s in item)
+                    stateMap[s] = id;
+            }
+
+            // получаем минимальный алфавит
+            // входные символы не различимы, если Move(s,a1) == Move(s,a2), для любого s
+            // для этого используем алгоритм кластеризации, сначала 
+            // считаем, что все символы не различимы
+
+            var minClasses = new HashSet<HashSet<int>>(setComparer);
+            var alphaQueue = new Queue<HashSet<int>>();
+            alphaQueue.Enqueue(new HashSet<int>(Enumerable.Range(0,AlphabetSize)));
+
+            // для всех состояний, будем проверять каждый класс на различимость,
+            // т.е. символы различимы, если они приводят к разным состояниям
+            for (int s = 0 ; s < optimalStates.Count; s++) {
+                var newQueue = new Queue<HashSet<int>>();
+
+                foreach (var A in alphaQueue) {
+                    // классы из одного символа делить бесполезно, переводим их сразу в
+                    // результирующий алфавит
+                    if (A.Count == 1) {
+                        minClasses.Add(A);
+                        continue;
+                    }
+
+                    // различаем классы символов, которые переводят в различные оптимальные состояния
+                    // optimalState -> alphaClass
+                    var classes = new Dictionary<int, HashSet<int>>();
+
+                    foreach (var term in A) {
+                        // ищем все переходы класса по символу term
+                        var s2 = m_transitions.Where(t => stateMap[t.s1] == s && t.edge == term).Select(t => stateMap[t.s2]).DefaultIfEmpty(-1).First();
+
+                        HashSet<int> a2;
+                        if (!classes.TryGetValue(s2, out a2)) {
+                            a2 = new HashSet<int>();
+                            newQueue.Enqueue(a2);
+                            classes[s2] = a2;
+                        }
+                        a2.Add(term);
+                    }
+                }
+
+                if (newQueue.Count == 0)
+                    break;
+                alphaQueue = newQueue;
+            }
+
+            // после окончания работы алгоритма в очереди останутся минимальные различимые классы
+            // входных символов
+            foreach (var A in alphaQueue)
+                minClasses.Add(A);
+
+            // построение отображения алфавитов входных символов.
+            // поскольку символ DFAConst.UNCLASSIFIED_INPUT может иметь
+            // специальное значение, тогда сохраним минимальный класс,
+            // содержащий этот символ на томже месте.
+
+            var nextCls = 0;
+            foreach (var item in minClasses) {
+                if (nextCls == AutomatonConst.UNCLASSIFIED_INPUT)
+                    nextCls++;
+
+                // сохраняем DFAConst.UNCLASSIFIED_INPUT
+                var cls = item.Contains(AutomatonConst.UNCLASSIFIED_INPUT) ? AutomatonConst.UNCLASSIFIED_INPUT : nextCls++;
+                optimalDFA.AddSymbol(cls);
+
+                foreach (var a in item)
+                    alphabetMap[a] = cls;
+            }
+
+            // построение автомата
+            optimalDFA.SetInitialState(stateMap[m_initialState]);
+
+            foreach (var sf in m_finalStates.Select(s => stateMap[s]).Distinct())
+                optimalDFA.MarkFinalState(sf);
+
+            foreach (var t in m_transitions.Select(t => new AutomatonTransition(stateMap[t.s1],stateMap[t.s2],alphabetMap[t.edge])).Distinct())
+                optimalDFA.Add(t);
+        }
+
+        protected string PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
+            Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
+            Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
+
+            var data = new List<string>();
+
+            data.Add("digraph dfa {");
+
+            foreach (var final in m_finalStates)
+                data.Add(String.Format("{0} [shape=box];",String.Join("", stateAlphabet.GetSymbols(final))));
+
+            foreach (var t in m_transitions)
+                data.Add(String.Format(
+                    "{0} -> {2} [label={1}];",
+                    String.Join("", stateAlphabet.GetSymbols(t.s1)),
+                    ToLiteral(ToLiteral(String.Join("", t.edge == AutomatonConst.UNCLASSIFIED_INPUT ? new [] { "@" } : inputAlphabet.GetSymbols(t.edge).Select(x => x.ToString())))),
+                    String.Join("", stateAlphabet.GetSymbols(t.s2))
+                ));
+            data.Add("}");
+            return String.Join("\n", data);
+        }
+
+        static string ToLiteral(string input)
+        {
+            using (var writer = new StringWriter())
+            {
+                using (var provider = CodeDomProvider.CreateProvider("CSharp"))
+                {
+                    provider.GenerateCodeFromExpression(new CodePrimitiveExpression(input), writer, null);
+                    return writer.ToString();
+                }
+            }
+        }
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Automaton/EnumAlphabet.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,66 @@
+using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Globalization;
+using System.Linq;
+using System.Diagnostics.CodeAnalysis;
+
+namespace Implab.Automaton {
+    /// <summary>
+    /// Алфавит символами которого являются элементы перечислений.
+    /// </summary>
+    /// <typeparam name="T">Тип перечислений</typeparam>
+    public class EnumAlphabet<T> : IndexedAlphabetBase<T> where T : struct, IConvertible {
+        [SuppressMessage("Microsoft.Design", "CA1000:DoNotDeclareStaticMembersOnGenericTypes")]
+        static readonly Lazy<T[]> _symbols = new Lazy<T[]>(GetSymbols);
+
+        [SuppressMessage("Microsoft.Design", "CA1000:DoNotDeclareStaticMembersOnGenericTypes")]
+        static readonly Lazy<EnumAlphabet<T>> _fullAlphabet = new Lazy<EnumAlphabet<T>>(CreateEnumAlphabet);
+
+        static EnumAlphabet<T> CreateEnumAlphabet() {
+            var symbols = _symbols.Value;
+
+            if (
+                symbols[symbols.Length - 1].ToInt32(CultureInfo.InvariantCulture) >= symbols.Length
+                || symbols[0].ToInt32(CultureInfo.InvariantCulture) != 0
+            )
+                throw new InvalidOperationException("The specified enumeration must be zero-based and continuously numbered");
+
+            return new EnumAlphabet<T>(symbols.Select(x => x.ToInt32(CultureInfo.InvariantCulture)).ToArray());
+        }
+
+        static T[] GetSymbols() {
+            if (!typeof(T).IsEnum)
+                throw new InvalidOperationException("Invalid generic parameter, enumeration is required");
+
+            if (Enum.GetUnderlyingType(typeof(T)) != typeof(Int32))
+                throw new InvalidOperationException("Only enums based on Int32 are supported");
+            
+            return ((T[])Enum.GetValues(typeof(T)))
+                .OrderBy(x => x.ToInt32(CultureInfo.InvariantCulture))
+                .ToArray();
+        }
+
+        public static EnumAlphabet<T> FullAlphabet {
+            get {
+                return _fullAlphabet.Value;
+            }
+        }
+
+
+        public EnumAlphabet()
+            : base(_symbols.Value.Length) {
+        }
+
+        public EnumAlphabet(int[] map)
+            : base(map) {
+            Debug.Assert(map.Length == _symbols.Value.Length);
+        }
+
+
+        public override int GetSymbolIndex(T symbol) {
+            return symbol.ToInt32(CultureInfo.InvariantCulture);
+        }
+
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Automaton/IAlphabet.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,34 @@
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace Implab.Automaton {
+    /// <summary>
+    /// Алфавит. Множество символов, которые разбиты на классы, при этом классы имеют непрерывную нумерацию,
+    /// что позволяет использовать их в качестве индексов массивов.
+    /// </summary>
+    /// <remarks>
+    /// <para>Алфавит является сюрьективным отображением множества символов в множество индексов, это позволяет сократить размер таблицы переходов автомата
+    /// для входных символов, которые для него не различимы.</para>
+    /// </remarks>
+    /// <typeparam name="TSymbol">Тип символов.</typeparam>
+    public interface IAlphabet<TSymbol> {
+        /// <summary>
+        /// Количество классов символов в алфавите.
+        /// </summary>
+        int Count { get; }
+
+        /// <summary>
+        /// Преобразует входной символ в индекс символа из алфавита.
+        /// </summary>
+        /// <param name="symobl">Исходный символ</param>
+        /// <returns>Индекс в алфавите</returns>
+        int Translate(TSymbol symobl);
+
+        bool Contains(TSymbol symbol);
+
+        IEnumerable<TSymbol> GetSymbols(int cls);
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Automaton/IAlphabetBuilder.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,26 @@
+
+using System.Collections.Generic;
+
+namespace Implab.Automaton {
+    public interface IAlphabetBuilder<TSymbol> : IAlphabet<TSymbol> {
+        /// <summary>
+        /// Добавляет новый символ в алфавит, если символ уже был добавлен, то
+        /// возвращается ранее сопоставленный с символом класс.
+        /// </summary>
+        /// <param name="symbol">Символ для добавления.</param>
+        /// <returns>Индекс класса, который попоставлен с символом.</returns>
+        int DefineSymbol(TSymbol symbol);
+
+        int DefineSymbol(TSymbol symbol, int cls);
+        /// <summary>
+        /// Доабвляем класс символов. Множеству указанных исходных символов 
+        /// будет сопоставлен символ в алфавите.
+        /// </summary>
+        /// <param name="symbols">Множестов исходных символов</param>
+        /// <returns>Идентификатор символа алфавита.</returns>
+        int DefineClass(IEnumerable<TSymbol> symbols);
+
+        int DefineClass(IEnumerable<TSymbol> symbols, int cls);
+    }
+}
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Automaton/IDFATable.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,53 @@
+using System.Collections.Generic;
+
+
+namespace Implab.Automaton {
+    /// <summary>
+    /// Полностью описывает DFA автомат, его поведение, состояние и входные символы.
+    /// </summary>
+    /// <example>
+    /// class MyAutomaton {
+    ///     int m_current;
+    ///     readonly DFAStateDescriptor<string>[] m_automaton;
+    ///     readonly IAlphabet<MyCommands> m_commands;
+    /// 
+    ///     public MyAutomaton(IDFADefinition&lt;MyCommands,MyStates,string&gt; definition) {
+    ///         m_current = definition.StateAlphabet.Translate(MyStates.Initial);
+    ///         m_automaton = definition.GetTransitionTable();
+    ///         m_commands = definition.InputAlphabet;
+    ///     }
+    /// 
+    ///     // defined a method which will move the automaton to the next state
+    ///     public void Move(MyCommands cmd) {
+    ///         // use transition map to determine the next state
+    ///         var next = m_automaton[m_current].transitions[m_commands.Translate(cmd)];
+    /// 
+    ///         // validate that we aren't in the unreachable state
+    ///         if (next == DFAConst.UNREACHABLE_STATE)
+    ///             throw new InvalidOperationException("The specified command is invalid");
+    /// 
+    ///         // if everything is ok
+    ///         m_current = next;
+    ///     }
+    /// }
+    /// </example>
+    public interface IDFATable : IEnumerable<AutomatonTransition> {
+        int StateCount {
+            get;
+        }
+
+        int AlphabetSize {
+            get;
+        }
+
+        int InitialState {
+            get;
+        }
+
+        bool IsFinalState(int s);
+
+        IEnumerable<int> FinalStates {
+            get;
+        }
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Automaton/IDFATableBuilder.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,26 @@
+using System;
+using System.Collections.Generic;
+
+namespace Implab.Automaton {
+    public interface IDFATableBuilder : IDFATable, ICollection<AutomatonTransition> {
+        /// <summary>
+        /// Marks the state as final.
+        /// </summary>
+        /// <param name="state">State.</param>
+        void MarkFinalState(int state);
+
+        void SetInitialState(int s);
+
+        /// <summary>
+        /// Increases if needed the input alphabet size to hold the specified symbol.
+        /// </summary>
+        /// <remarks>
+        /// <code>
+        /// AlphabetSize = Math.Max(AlphabetSize, symbol + 1)
+        /// </code>
+        /// </remarks>
+        /// <param name="symbol">Symbol.</param>
+        void AddSymbol(int symbol);
+    }
+}
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Automaton/IndexedAlphabetBase.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,50 @@
+using Implab;
+using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+
+namespace Implab.Automaton {
+    /// <summary>
+    /// Indexed alphabet is the finite set of symbols where each symbol has a zero-based unique index.
+    /// </summary>
+    /// <remarks>
+    /// Indexed alphabets are usefull in bulting efficient translations from source alphabet
+    /// to the input alphabet of the automaton. It's assumed that the index to the symbol match
+    /// is well known and documented.
+    /// </remarks>
+    public abstract class IndexedAlphabetBase<T> : MapAlphabet<T> {
+
+        protected IndexedAlphabetBase() :base(true, null) {
+        }
+
+        public abstract int GetSymbolIndex(T symbol);
+
+        /// <summary>
+        /// Gets the translation map from the index of the symbol to it's class this is usefull for the optimized input symbols transtaion.
+        /// </summary>
+        /// <remarks>
+        /// The map is continous and start from the symbol with zero code. The last symbol
+        /// in the map is the last classified symbol in the alphabet, i.e. the map can be
+        /// shorter then the whole alphabet.
+        /// </remarks>
+        /// <returns>The translation map.</returns>
+        public int[] GetTranslationMap() {
+            var map = new Dictionary<int, int>();
+
+            int max = 0;
+            foreach (var p in Mappings) {
+                var index = GetSymbolIndex(p.Key);
+                max = Math.Max(max, index);
+                map[index] = p.Value;
+            }
+
+            var result = new int[max + 1];
+
+            for (int i = 0; i < result.Length; i++)
+                map.TryGetValue(i, out result[i]);
+
+            return result;
+        }
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Automaton/MapAlphabet.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,84 @@
+using System;
+using System.Collections.Generic;
+using System.Linq;
+
+namespace Implab.Automaton {
+    public class MapAlphabet<T> : IAlphabetBuilder<T> {
+        readonly Dictionary<T,int> m_map;
+        int m_nextCls;
+        readonly bool m_supportUnclassified;
+
+        public MapAlphabet(bool supportUnclassified, IEqualityComparer<T> comparer) {
+            m_map = comparer != null ? new Dictionary<T, int>(comparer) : new Dictionary<T,int>();
+            m_supportUnclassified = supportUnclassified;
+            m_nextCls = supportUnclassified ? 1 : 0;
+        }
+
+        #region IAlphabetBuilder implementation
+
+        public int DefineSymbol(T symbol) {
+            int cls;
+            return m_map.TryGetValue(symbol, out cls) ? cls : DefineSymbol(symbol, m_nextCls);
+        }
+
+        public int DefineSymbol(T symbol, int cls) {
+            Safe.ArgumentAssert(cls >= 0, "cls");
+
+            m_nextCls = Math.Max(cls + 1, m_nextCls);
+            m_map.Add(symbol, cls);
+            return cls;
+        }
+
+        public int DefineClass(IEnumerable<T> symbols) {
+            return DefineClass(symbols, m_nextCls);
+        }
+
+        public int DefineClass(IEnumerable<T> symbols, int cls) {
+            Safe.ArgumentAssert(cls >= 0, "cls");
+            Safe.ArgumentNotNull(symbols, "symbols");
+
+            m_nextCls = Math.Max(cls + 1, m_nextCls);
+
+            foreach (var symbol in symbols)
+                m_map[symbol] = cls;
+            return cls;
+        }
+
+        #endregion
+
+        #region IAlphabet implementation
+
+        public int Translate(T symbol) {
+            int cls;
+            if (m_map.TryGetValue(symbol, out cls))
+                return cls;
+            if (!m_supportUnclassified)
+                throw new ArgumentOutOfRangeException("symbol", "The specified symbol isn't in the alphabet");
+            return AutomatonConst.UNCLASSIFIED_INPUT;
+        }
+
+        public int Count {
+            get {
+                return m_nextCls;
+            }
+        }
+
+        public bool Contains(T symbol) {
+            return m_supportUnclassified || m_map.ContainsKey(symbol);
+        }
+
+
+        public IEnumerable<T> GetSymbols(int cls) {
+            Safe.ArgumentAssert(!m_supportUnclassified || cls > 0, "cls");
+            return m_map.Where(p => p.Value == cls).Select(p => p.Key);
+        }
+        #endregion
+
+        public IEnumerable<KeyValuePair<T,int>> Mappings {
+            get {
+                return m_map;
+            }
+        }
+    }
+}
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Automaton/ParserException.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,17 @@
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+
+namespace Implab.Automaton {
+    [Serializable]
+    public class ParserException : Exception {
+        public ParserException() { }
+        public ParserException(string message) : base(message) { }
+        public ParserException(string message, Exception inner) : base(message, inner) { }
+        protected ParserException(
+          System.Runtime.Serialization.SerializationInfo info,
+          System.Runtime.Serialization.StreamingContext context)
+            : base(info, context) { }
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Automaton/RegularExpressions/AltToken.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,17 @@
+using System;
+
+namespace Implab.Automaton.RegularExpressions {
+    public class AltToken: BinaryToken {
+        public AltToken(Token left, Token right)
+            : base(left, right) {
+        }
+
+        public override void Accept(IVisitor visitor) {
+            Safe.ArgumentNotNull(visitor, "visitor");
+            visitor.Visit(this);
+        }
+        public override string ToString() {
+            return String.Format(Right is BinaryToken ? "{0}|({1})" : "{0}|{1}", Left, Right);
+        }
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Automaton/RegularExpressions/BinaryToken.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,21 @@
+using Implab;
+
+namespace Implab.Automaton.RegularExpressions {
+    public abstract class BinaryToken: Token {
+        readonly Token m_left;
+        readonly Token m_right;
+
+        public Token Left {
+            get { return m_left; }
+        }
+
+        public Token Right {
+            get { return m_right; }
+        }
+
+        protected BinaryToken(Token left, Token right) {
+            Safe.ArgumentNotNull(m_left = left, "left");
+            Safe.ArgumentNotNull(m_right = right, "right");
+        }
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Automaton/RegularExpressions/CatToken.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,22 @@
+using System;
+
+namespace Implab.Automaton.RegularExpressions {
+    public class CatToken : BinaryToken {
+        public CatToken(Token left, Token right)
+            : base(left, right) {
+        }
+
+        public override void Accept(IVisitor visitor) {
+            Safe.ArgumentNotNull(visitor, "visitor");
+            visitor.Visit(this);
+        }
+
+        public override string ToString() {
+            return String.Format("{0}{1}", FormatToken(Left), FormatToken(Right));
+        }
+
+        static string FormatToken(Token token) {
+            return String.Format(token is AltToken ? "({0})" : "{0}", token);
+        }
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Automaton/RegularExpressions/EmptyToken.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,13 @@
+using Implab;
+
+namespace Implab.Automaton.RegularExpressions {
+    public class EmptyToken: Token {
+        public override void Accept(IVisitor visitor) {
+            Safe.ArgumentNotNull(visitor, "visitor");
+            visitor.Visit(this);
+        }
+        public override string ToString() {
+            return "$";
+        }
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Automaton/RegularExpressions/EndToken.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,18 @@
+using Implab;
+
+namespace Implab.Automaton.RegularExpressions {
+    /// <summary>
+    /// Конечный символ расширенного регулярного выражения, при построении ДКА
+    /// используется для определения конечных состояний.
+    /// </summary>
+    public class EndToken: Token {
+
+        public override void Accept(IVisitor visitor) {
+            Safe.ArgumentNotNull(visitor, "visitor");
+            visitor.Visit(this);
+        }
+        public override string ToString() {
+            return "#";
+        }
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Automaton/RegularExpressions/EndTokenT.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,23 @@
+namespace Implab.Automaton.RegularExpressions {
+    /// <summary>
+    /// Конечный символ расширенного регулярного выражения, при построении ДКА
+    /// используется для определения конечных состояний.
+    /// </summary>
+    public class EndToken<TTag>: EndToken {
+
+        readonly TTag m_tag;
+
+        public EndToken(TTag tag) {
+            m_tag = tag;
+        }
+
+        public EndToken()
+            : this(default(TTag)) {
+        }
+
+        public TTag Tag {
+            get { return m_tag; }
+        }
+
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Automaton/RegularExpressions/ITaggedDFABuilder.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,7 @@
+
+namespace Implab.Automaton.RegularExpressions {
+    public interface ITaggedDFABuilder<TTag> : IDFATableBuilder {
+        void SetStateTag(int s, TTag[] tags);
+    }
+}
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Automaton/RegularExpressions/IVisitor.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,13 @@
+namespace Implab.Automaton.RegularExpressions {
+    /// <summary>
+    /// Интерфейс обходчика синтаксического дерева регулярного выражения
+    /// </summary>
+    public interface IVisitor {
+        void Visit(AltToken token);
+        void Visit(StarToken token);
+        void Visit(CatToken token);
+        void Visit(EmptyToken token);
+        void Visit(EndToken token);
+        void Visit(SymbolToken token);
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Automaton/RegularExpressions/RegularDFA.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,91 @@
+using System.Collections.Generic;
+using System.Linq;
+
+namespace Implab.Automaton.RegularExpressions {
+    public class RegularDFA<TInput, TTag> : DFATable, ITaggedDFABuilder<TTag> {
+
+        readonly Dictionary<int,TTag[]> m_tags = new Dictionary<int, TTag[]>();
+        readonly IAlphabet<TInput> m_alphabet;
+
+        public RegularDFA(IAlphabet<TInput> alphabet) {
+            Safe.ArgumentNotNull(alphabet, "aplhabet");
+
+            m_alphabet = alphabet;
+        }
+
+
+        public IAlphabet<TInput> InputAlphabet {
+            get {
+                return m_alphabet;
+            }
+        }
+
+        public void MarkFinalState(int s, TTag[] tags) {
+            MarkFinalState(s);
+            SetStateTag(s, tags);
+        }
+
+        public void SetStateTag(int s, TTag[] tags) {
+            Safe.ArgumentNotNull(tags, "tags");
+            m_tags[s] = tags;
+        }
+
+        public TTag[] GetStateTag(int s) {
+            TTag[] tags;
+            return m_tags.TryGetValue(s, out tags) ? tags : new TTag[0];
+        }
+
+        public TTag[][] CreateTagTable() {
+            var table = new TTag[StateCount][];
+
+            foreach (var pair in m_tags)
+                table[pair.Key] = pair.Value;
+
+            return table;
+        }
+
+        /// <summary>
+        /// Optimize the specified alphabet.
+        /// </summary>
+        /// <param name="alphabet">Пустой алфавит, который будет зполнен в процессе оптимизации.</param>
+        public RegularDFA<TInput,TTag> Optimize(IAlphabetBuilder<TInput> alphabet) {
+            Safe.ArgumentNotNull(alphabet, "alphabet");
+
+            var dfa = new RegularDFA<TInput, TTag>(alphabet);
+
+            var alphaMap = new Dictionary<int,int>();
+            var stateMap = new Dictionary<int,int>();
+
+            Optimize(dfa, alphaMap, stateMap); 
+
+            // mark tags in the new DFA
+            foreach (var g in m_tags.Where(x => x.Key < StateCount).GroupBy(x => stateMap[x.Key], x => x.Value ))
+                dfa.SetStateTag(g.Key, g.SelectMany(x => x).ToArray());
+
+            // make the alphabet for the new DFA
+            // skip all unclassified symbols
+            foreach (var pair in alphaMap.Where(x => x.Value != 0))
+                alphabet.DefineClass(m_alphabet.GetSymbols(pair.Key), pair.Value);
+            return dfa;
+        }
+
+        protected override IEnumerable<HashSet<int>> SplitFinalStates(IEnumerable<int> states) {
+            var arrayComparer = new CustomEqualityComparer<TTag[]>(
+                (x,y) => x.Length == y.Length && x.All(it => y.Contains(it)),
+                x => x.Sum(it => x.GetHashCode())
+            );
+            return states.GroupBy(x => m_tags[x] ?? new TTag[0], arrayComparer).Select(g => new HashSet<int>(g));
+        }
+
+        public override string ToString() {
+            var states = new MapAlphabet<string>(false, null);
+
+            for (int i = 0; i < StateCount; i++)
+                states.DefineSymbol(string.Format("s{0}", i), i);
+
+            return string.Format("//[RegularDFA {1} x {2}]\n{0}", PrintDFA(InputAlphabet, states),StateCount, AlphabetSize);
+        }
+
+    }
+}
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Automaton/RegularExpressions/RegularExpressionVisitor.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,212 @@
+using Implab;
+using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+
+namespace Implab.Automaton.RegularExpressions {
+    /// <summary>
+    /// Используется для построения ДКА по регулярному выражению, сначала обходит
+    /// регулярное выражение и вычисляет followpos, затем используется метод
+    /// <see cref="BuildDFA(IDFADefinition)"/> для построения автомата.
+    /// </summary>
+    public class RegularExpressionVisitor : IVisitor {
+        int m_idx;
+        Token m_root;
+        HashSet<int> m_firstpos;
+        HashSet<int> m_lastpos;
+
+        readonly Dictionary<int, HashSet<int>> m_followpos = new Dictionary<int, HashSet<int>>();
+        readonly Dictionary<int, int> m_indexes = new Dictionary<int, int>();
+        readonly HashSet<int> m_ends = new HashSet<int>();
+
+        readonly IDFATableBuilder m_builder;
+        readonly IAlphabetBuilder<HashSet<int>> m_states = new MapAlphabet<HashSet<int>>(
+            false,
+            new CustomEqualityComparer<HashSet<int>>(
+                (x, y) => x.SetEquals(y),
+                x => x.Sum(n => n.GetHashCode())
+            )
+        );
+
+        public RegularExpressionVisitor(IDFATableBuilder builder) {
+            Safe.ArgumentNotNull(builder, "builder");
+
+            m_builder = builder;
+        }
+
+        HashSet<int> Followpos(int pos) {
+            HashSet<int> set;
+            return m_followpos.TryGetValue(pos, out set) ? set : m_followpos[pos] = new HashSet<int>();
+        }
+
+        bool Nullable(object n) {
+            if (n is EmptyToken || n is StarToken)
+                return true;
+            var altToken = n as AltToken;
+            if (altToken != null)
+                return Nullable(altToken.Left) || Nullable(altToken.Right);
+            var catToken = n as CatToken;
+            if (catToken != null)
+                return Nullable(catToken.Left) && Nullable(catToken.Right);
+            return false;
+        }
+
+        protected int Index {
+            get { return m_idx; }
+        }
+
+        public void Visit(AltToken token) {
+            if (m_root == null)
+                m_root = token;
+            var firtspos = new HashSet<int>();
+            var lastpos = new HashSet<int>();
+
+            token.Left.Accept(this);
+            firtspos.UnionWith(m_firstpos);
+            lastpos.UnionWith(m_lastpos);
+
+            token.Right.Accept(this);
+            firtspos.UnionWith(m_firstpos);
+            lastpos.UnionWith(m_lastpos);
+
+            m_firstpos = firtspos;
+            m_lastpos = lastpos;
+        }
+
+        public void Visit(StarToken token) {
+            if (m_root == null)
+                m_root = token;
+            token.Token.Accept(this);
+
+            foreach (var i in m_lastpos)
+                Followpos(i).UnionWith(m_firstpos);
+        }
+
+        public void Visit(CatToken token) {
+            if (m_root == null)
+                m_root = token;
+
+            var firtspos = new HashSet<int>();
+            var lastpos = new HashSet<int>();
+            token.Left.Accept(this);
+            firtspos.UnionWith(m_firstpos);
+            var leftLastpos = m_lastpos;
+
+            token.Right.Accept(this);
+            lastpos.UnionWith(m_lastpos);
+            var rightFirstpos = m_firstpos;
+
+            if (Nullable(token.Left))
+                firtspos.UnionWith(rightFirstpos);
+
+            if (Nullable(token.Right))
+                lastpos.UnionWith(leftLastpos);
+
+            m_firstpos = firtspos;
+            m_lastpos = lastpos;
+
+            foreach (var i in leftLastpos)
+                Followpos(i).UnionWith(rightFirstpos);
+
+        }
+
+        public void Visit(EmptyToken token) {
+            if (m_root == null)
+                m_root = token;
+        }
+
+        public void Visit(SymbolToken token) {
+            if (m_root == null)
+                m_root = token;
+            m_idx++;
+            m_indexes[m_idx] = token.Value;
+            m_firstpos = new HashSet<int>(new[] { m_idx });
+            m_lastpos = new HashSet<int>(new[] { m_idx });
+        }
+
+        public virtual void Visit(EndToken token) {
+            if (m_root == null)
+                m_root = token;
+            m_idx++;
+            m_indexes[m_idx] = AutomatonConst.UNCLASSIFIED_INPUT;
+            m_firstpos = new HashSet<int>(new[] { m_idx });
+            m_lastpos = new HashSet<int>(new[] { m_idx });
+            Followpos(m_idx);
+            m_ends.Add(m_idx);
+        }
+
+        public void BuildDFA() {
+            AddState(m_firstpos);
+            SetInitialState(m_firstpos);
+
+            if(IsFinal(m_firstpos))
+                MarkFinalState(m_firstpos);
+
+            var inputMax = m_indexes.Values.Max();
+            var queue = new Queue<HashSet<int>>();
+
+            queue.Enqueue(m_firstpos);
+
+            while (queue.Count > 0) {
+                var s1 = queue.Dequeue();
+
+                for (int a = 0; a <= inputMax; a++) {
+                    var s2 = new HashSet<int>();
+                    foreach (var p in s1) {
+                        if (m_indexes[p] == a) {
+                            s2.UnionWith(Followpos(p));
+                        }
+                    }
+                    if (s2.Count > 0) {
+                        if (!HasState(s2)) {
+                            AddState(s2);
+                            if (IsFinal(s2))
+                                MarkFinalState(s2);
+                            
+                            queue.Enqueue(s2);
+                        }
+
+                        DefineTransition(s1, s2, a);
+                    }
+
+                }
+            }
+        }
+
+        protected bool HasState(HashSet<int> state) {
+            return m_states.Contains(state);
+        }
+
+        protected void AddState(HashSet<int> state) {
+            Debug.Assert(!HasState(state));
+
+            m_states.DefineSymbol(state);
+        }
+
+        protected int Translate(HashSet<int> state) {
+            Debug.Assert(HasState(state));
+
+            return m_states.Translate(state);
+        }
+
+        protected virtual void SetInitialState(HashSet<int> state) {
+            m_builder.SetInitialState(Translate(state));
+        }
+
+        protected virtual void MarkFinalState(HashSet<int> state) {
+            m_builder.MarkFinalState(Translate(state));
+        }
+
+        protected virtual void DefineTransition(HashSet<int> s1, HashSet<int> s2, int ch) {
+            
+            m_builder.Add(new AutomatonTransition(Translate(s1), Translate(s2), ch));
+        }
+
+        bool IsFinal(IEnumerable<int> state) {
+            Debug.Assert(state != null);
+            return state.Any(m_ends.Contains);
+        }
+
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Automaton/RegularExpressions/RegularExpressionVisitorT.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,37 @@
+using Implab;
+using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+
+namespace Implab.Automaton.RegularExpressions {
+    /// <summary>
+    /// </summary>
+    public class RegularExpressionVisitor<TTag> : RegularExpressionVisitor {
+        readonly Dictionary<int, TTag> m_tags = new Dictionary<int, TTag>();
+
+        readonly ITaggedDFABuilder<TTag> m_builder;
+
+        public RegularExpressionVisitor(ITaggedDFABuilder<TTag> builder) : base(builder) {
+            m_builder = builder;
+        }
+
+        public override void Visit(EndToken token) {
+            base.Visit(token);
+            var tagged = token as EndToken<TTag>;
+            if (tagged != null)
+                m_tags.Add(Index, tagged.Tag);
+        }
+
+        protected override void MarkFinalState(HashSet<int> state) {
+            base.MarkFinalState(state);
+            m_builder.SetStateTag(Translate(state), GetStateTags(state));
+        }
+
+        TTag[] GetStateTags(IEnumerable<int> state) {
+            Debug.Assert(state != null);
+            return state.Where(m_tags.ContainsKey).Select(pos => m_tags[pos]).ToArray();
+        }
+
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Automaton/RegularExpressions/StarToken.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,31 @@
+using Implab;
+using System;
+
+
+namespace Implab.Automaton.RegularExpressions {
+    /// <summary>
+    /// Замыкание выражения с 0 и более повторов.
+    /// </summary>
+    public class StarToken: Token {
+
+        Token m_token;
+
+        public Token Token {
+            get { return m_token; }
+        }
+
+        public StarToken(Token token) {
+            Safe.ArgumentNotNull(token, "token");
+            m_token = token;
+        }
+
+        public override void Accept(IVisitor visitor) {
+            Safe.ArgumentNotNull(visitor, "visitor");
+            visitor.Visit(this);
+        }
+
+        public override string ToString() {
+            return String.Format("({0})*", Token);
+        }
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Automaton/RegularExpressions/SymbolToken.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,27 @@
+using Implab;
+
+namespace Implab.Automaton.RegularExpressions {
+    /// <summary>
+    /// Выражение, соответсвующее одному символу.
+    /// </summary>
+    public class SymbolToken: Token {
+        int m_value;
+
+        public int Value {
+            get { return m_value; }
+        }
+
+        public SymbolToken(int value) {
+            m_value = value;
+        }
+        public override void Accept(IVisitor visitor) {
+            Safe.ArgumentNotNull(visitor, "visitor");
+
+            visitor.Visit(this);
+        }
+
+        public override string ToString() {
+            return Value.ToString();
+        }
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Automaton/RegularExpressions/Token.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,63 @@
+using Implab;
+using System;
+using System.Linq;
+
+namespace Implab.Automaton.RegularExpressions {
+    public abstract class Token {
+        public abstract void Accept(IVisitor visitor);
+
+        public Token End() {
+            return Cat(new EndToken());
+        }
+
+        public Token Tag<TTag>(TTag tag) {
+            return Cat(new EndToken<TTag>(tag));
+        }
+
+        public Token Cat(Token right) {
+            return new CatToken(this, right);
+        }
+
+        public Token Or(Token right) {
+            return new AltToken(this, right);
+        }
+
+        public Token Optional() {
+            return Or(new EmptyToken());
+        }
+
+        public Token EClosure() {
+            return new StarToken(this);
+        }
+
+        public Token Closure() {
+            return Cat(new StarToken(this));
+        }
+
+        public Token Repeat(int count) {
+            Token token = null;
+
+            for (int i = 0; i < count; i++)
+                token = token != null ? token.Cat(this) : this;
+            return token ?? new EmptyToken();
+        }
+
+        public Token Repeat(int min, int max) {
+            if (min > max || min < 1)
+                throw new ArgumentOutOfRangeException();
+            var token = Repeat(min);
+
+            for (int i = min; i < max; i++)
+                token = token.Cat( Optional() );
+            return token;
+        }
+
+        public static Token New(params int[] set) {
+            Safe.ArgumentNotNull(set, "set");
+            Token token = null;
+            foreach(var c in set.Distinct())
+                token = token == null ? new SymbolToken(c) : token.Or(new SymbolToken(c));
+            return token;
+        }
+    }
+}

--- a/Implab/Components/ExecutionState.cs	Fri Feb 19 18:07:17 2016 +0300
+++ b/Implab/Components/ExecutionState.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -1,14 +1,24 @@
 namespace Implab.Components {
     
     public enum ExecutionState {
-        Reserved = 0,
-        Uninitialized,
+        Undefined = 0,
+
+        Created,
+
+        Initializing,
+
         Ready,
+
         Starting,
+
         Running,
+
         Stopping,
-        Stopped,
+
+        Failed,
+
         Disposed,
-        Failed
+
+        Last = Disposed
     }
 }
\ No newline at end of file

--- a/Implab/Components/IInitializable.cs	Fri Feb 19 18:07:17 2016 +0300
+++ b/Implab/Components/IInitializable.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -11,7 +11,7 @@
         /// Completes initialization.
         /// </summary>
         /// <remarks>
-        /// Normally virtual shouldn't be called from the constructor, due to the incomplete object state, but
+        /// Normally virtual methods shouldn't be called from the constructor, due to the incomplete object state, but
         /// they can be called from this method. This method is also usefull when we constructing a complex grpah
         /// of components where cyclic references may take place.
         /// </remarks>

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Components/LazyAndWeak.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,64 @@
+using System;
+using System.Threading;
+
+namespace Implab.Components {
+    /// <summary>
+    /// Creates an instace on-demand and allows it to be garbage collected.
+    /// </summary>
+    /// <remarks>
+    /// Usefull when dealing with memory-intensive objects which are frequently used.
+    /// This class is similar to <see cref="ObjectPool{T}"/> except it is a singleton.
+    /// </remarks>
+    public class LazyAndWeak<T> where T : class {
+
+        readonly Func<T> m_factory;
+        readonly object m_lock;
+        WeakReference m_reference;
+
+
+        public LazyAndWeak(Func<T> factory, bool useLock) {
+            Safe.ArgumentNotNull(factory, "factory");
+            m_factory = factory;
+            m_lock = useLock ? new object() : null;
+        }
+
+        public LazyAndWeak(Func<T> factory) : this(factory, false) {
+        }
+
+        public T Value {
+            get {
+                while (true) {
+                    var weak = m_reference;
+                    T value;
+                    if (weak != null) {
+                        value = weak.Target as T;
+                        if (value != null)
+                            return value;
+                    }
+
+                    if (m_lock == null) {
+                        value = m_factory();
+
+                        if (Interlocked.CompareExchange(ref m_reference, new WeakReference(value), weak) == weak)
+                            return value;
+                    } else {
+                        lock (m_lock) {
+                            // double check
+                            weak = m_reference;
+                            if (weak != null) {
+                                value = weak.Target as T;
+                                if (value != null)
+                                    return value;
+                            }
+                            // we are safe to write
+                            value = m_factory();
+                            m_reference = new WeakReference(value);
+                            return value;
+                        }
+                    }
+                }
+            }
+        }
+    }
+}
+

--- a/Implab/Components/RunnableComponent.cs	Fri Feb 19 18:07:17 2016 +0300
+++ b/Implab/Components/RunnableComponent.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -1,24 +1,164 @@
 using System;
-using Implab.Parsing;
 
 namespace Implab.Components {
-    public class RunnableComponent : Disposable, IRunnable, IInitializable {
-        
+    public abstract class RunnableComponent : IDisposable, IRunnable, IInitializable {
+        enum Commands {
+            Ok = 0,
+            Fail,
+            Init,
+            Start,
+            Stop,
+            Dispose,
+            Last = Dispose
+        }
+
+        class StateMachine {
+            static readonly ExecutionState[,] _transitions;
+
+            static StateMachine() {
+                _transitions = new ExecutionState[(int)ExecutionState.Last + 1, (int)Commands.Last + 1];
+
+                Edge(ExecutionState.Created, ExecutionState.Initializing, Commands.Init);
+                Edge(ExecutionState.Created, ExecutionState.Disposed, Commands.Dispose);
+
+                Edge(ExecutionState.Initializing, ExecutionState.Ready, Commands.Ok);
+                Edge(ExecutionState.Initializing, ExecutionState.Failed, Commands.Fail);
+
+                Edge(ExecutionState.Ready, ExecutionState.Starting, Commands.Start);
+                Edge(ExecutionState.Ready, ExecutionState.Disposed, Commands.Dispose);
+
+                Edge(ExecutionState.Starting, ExecutionState.Running, Commands.Ok);
+                Edge(ExecutionState.Starting, ExecutionState.Failed, Commands.Fail);
+                Edge(ExecutionState.Starting, ExecutionState.Stopping, Commands.Stop);
+                Edge(ExecutionState.Starting, ExecutionState.Disposed, Commands.Dispose);
 
+                Edge(ExecutionState.Running, ExecutionState.Failed, Commands.Fail);
+                Edge(ExecutionState.Running, ExecutionState.Stopping, Commands.Stop);
+                Edge(ExecutionState.Running, ExecutionState.Disposed, Commands.Dispose);
 
+                Edge(ExecutionState.Stopping, ExecutionState.Failed, Commands.Fail);
+                Edge(ExecutionState.Stopping, ExecutionState.Disposed, Commands.Ok);
+
+                Edge(ExecutionState.Failed, ExecutionState.Disposed, Commands.Dispose);
+            }
+
+            static void Edge(ExecutionState s1, ExecutionState s2, Commands cmd) {
+                _transitions[(int)s1, (int)cmd] = s2;
+            }
 
-            
+            public ExecutionState State {
+                get;
+                private set;
+            }
+
+            public StateMachine(ExecutionState initial) {
+                State = initial;
+            }
+
+            public bool Move(Commands cmd) {
+                var next = _transitions[(int)State, (int)cmd];
+                if (next == ExecutionState.Undefined)
+                    return false;
+                State = next;
+                return true;
+            }
+        }
+
         IPromise m_pending;
         Exception m_lastError;
 
+        readonly StateMachine m_stateMachine;
+
         protected RunnableComponent(bool initialized) {
+            m_stateMachine = new StateMachine(initialized ? ExecutionState.Ready : ExecutionState.Created);
+        }
+
+        protected virtual int DisposeTimeout {
+            get {
+                return 10000;
+            }
+        }
+
+        void ThrowInvalidCommand(Commands cmd) {
+            if (m_stateMachine.State == ExecutionState.Disposed)
+                throw new ObjectDisposedException(ToString());
+            
+            throw new InvalidOperationException(String.Format("Commnd {0} is not allowed in the state {1}", cmd, m_stateMachine.State));
+        }
+
+        void Move(Commands cmd) {
+            if (!m_stateMachine.Move(cmd))
+                ThrowInvalidCommand(cmd);
+        }
+
+        void Invoke(Commands cmd, Action action) {
+            lock (m_stateMachine) 
+                Move(cmd);
             
+            try {
+                action();
+                lock(m_stateMachine)
+                    Move(Commands.Ok);
+
+            } catch (Exception err) {
+                lock (m_stateMachine) {
+                    Move(Commands.Fail);
+                    m_lastError = err;
+                }
+                throw;
+            }
         }
 
+        IPromise InvokeAsync(Commands cmd, Func<IPromise> action, Action<IPromise, IDeferred> chain) {
+            IPromise promise = null;
+            IPromise prev;
+
+            var task = new ActionChainTask(action, null, null, true);
+
+            lock (m_stateMachine) {
+                Move(cmd);
+            
+                prev = m_pending;
+
+                promise = task.Then(
+                    () => {
+                        lock(m_stateMachine) {
+                            if (m_pending == promise) {
+                                Move(Commands.Ok);
+                                m_pending = null;
+                            }
+                        }
+                    }, e => {
+                        lock(m_stateMachine) {
+                            if (m_pending == promise) {
+                                Move(Commands.Fail);
+                                m_pending = null;
+                                m_lastError = e;
+                            }
+                        }
+                        throw new PromiseTransientException(e);
+                    }
+                );
+
+                m_pending = promise;
+            }
+
+            if (prev == null)
+                task.Resolve();
+            else
+                chain(prev, task);
+
+            return promise;
+        }
+
+
         #region IInitializable implementation
 
         public void Init() {
-            
+            Invoke(Commands.Init, OnInitialize);
+        }
+
+        protected virtual void OnInitialize() {
         }
 
         #endregion
@@ -26,33 +166,92 @@
         #region IRunnable implementation
 
         public IPromise Start() {
-            throw new NotImplementedException();
+            return InvokeAsync(Commands.Start, OnStart, null);
         }
 
         protected virtual IPromise OnStart() {
             return Promise.SUCCESS;
         }
 
-        protected virtual void Run() {
+        public IPromise Stop() {
+            return InvokeAsync(Commands.Stop, OnStop, StopPending).Then(Dispose);
+        }
+
+        protected virtual IPromise OnStop() {
+            return Promise.SUCCESS;
         }
 
-        public IPromise Stop() {
-            throw new NotImplementedException();
+        /// <summary>
+        /// Stops the current operation if one exists.
+        /// </summary>
+        /// <param name="current">Current.</param>
+        /// <param name="stop">Stop.</param>
+        protected virtual void StopPending(IPromise current, IDeferred stop) {
+            if (current == null) {
+                stop.Resolve();
+            } else {
+                // связваем текущую операцию с операцией остановки
+                current.On(
+                    stop.Resolve, // если текущая операция заверщилась, то можно начинать остановку
+                    stop.Reject, // если текущая операция дала ошибку - то все плохо, нельзя продолжать
+                    e => stop.Resolve() // если текущая отменилась, то можно начинать остановку
+                );
+                // посылаем текущей операции сигнал остановки
+                current.Cancel();
+            }
         }
 
         public ExecutionState State {
             get {
-                throw new NotImplementedException();
+                return m_stateMachine.State;
             }
         }
 
         public Exception LastError {
             get {
-                throw new NotImplementedException();
+                return m_lastError;
             }
         }
 
         #endregion
+
+        #region IDisposable implementation
+
+        public void Dispose() {
+            IPromise pending;
+            lock (m_stateMachine) {
+                if (m_stateMachine.State == ExecutionState.Disposed)
+                    return;
+
+                Move(Commands.Dispose);
+
+                GC.SuppressFinalize(this);
+
+                pending = m_pending;
+                m_pending = null;
+            }
+            if (pending != null) {
+                pending.Cancel();
+                pending.Timeout(DisposeTimeout).On(
+                    () => Dispose(true, null),
+                    err => Dispose(true, err),
+                    reason => Dispose(true, new OperationCanceledException("The operation is cancelled", reason))
+                );
+            } else {
+                Dispose(true, m_lastError);
+            }
+        }
+
+        ~RunnableComponent() {
+            Dispose(false, null);
+        }
+
+        #endregion
+
+        protected virtual void Dispose(bool disposing, Exception lastError) {
+
+        }
+
     }
 }
 

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Formats/ByteAlphabet.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,23 @@
+using System.Collections.Generic;
+using System.Linq;
+using Implab.Automaton;
+
+namespace Implab.Formats {
+    public class ByteAlphabet : IndexedAlphabetBase<byte> {
+
+        #region implemented abstract members of IndexedAlphabetBase
+
+        public override int GetSymbolIndex(byte symbol) {
+            return (int)symbol;
+        }
+
+        public IEnumerable<byte> InputSymbols {
+            get {
+                return Enumerable.Range(byte.MinValue, byte.MaxValue).Cast<byte>();
+            }
+        }
+
+        #endregion
+    }
+}
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Formats/CharAlphabet.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,16 @@
+using System.Collections.Generic;
+using System.Linq;
+using Implab.Automaton;
+
+namespace Implab.Formats {
+    public class CharAlphabet: IndexedAlphabetBase<char> {
+
+        public override int GetSymbolIndex(char symbol) {
+            return symbol;
+        }
+
+        public IEnumerable<char> InputSymbols {
+            get { return Enumerable.Range(char.MinValue, char.MaxValue).Cast<char>(); }
+        }
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Formats/Grammar.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,99 @@
+using Implab;
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using Implab.Automaton;
+using Implab.Automaton.RegularExpressions;
+
+namespace Implab.Formats {
+    /// <summary>
+    /// Базовый абстрактный класс. Грамматика, позволяет формулировать выражения над алфавитом типа <c>char</c>.
+    /// </summary>
+    public abstract class Grammar<TSymbol> {
+        
+        protected abstract IAlphabetBuilder<TSymbol> AlphabetBuilder {
+            get;
+        }
+
+        protected SymbolToken UnclassifiedToken() {
+            return new SymbolToken(AutomatonConst.UNCLASSIFIED_INPUT);
+        }
+
+        protected void DefineAlphabet(IEnumerable<TSymbol> alphabet) {
+            Safe.ArgumentNotNull(alphabet, "alphabet");
+
+            foreach (var ch in alphabet)
+                AlphabetBuilder.DefineSymbol(ch);
+        }
+
+        protected Token SymbolToken(TSymbol symbol) {
+            return Token.New(TranslateOrAdd(symbol));
+        }
+
+        protected Token SymbolToken(IEnumerable<TSymbol> symbols) {
+            Safe.ArgumentNotNull(symbols, "symbols");
+
+            return Token.New(TranslateOrAdd(symbols).ToArray());
+        }
+
+        protected Token SymbolSetToken(params TSymbol[] set) {
+            return SymbolToken(set);
+        }
+
+        int TranslateOrAdd(TSymbol ch) {
+            var t = AlphabetBuilder.Translate(ch);
+            if (t == AutomatonConst.UNCLASSIFIED_INPUT)
+                t = AlphabetBuilder.DefineSymbol(ch);
+            return t;
+        }
+
+        IEnumerable<int> TranslateOrAdd(IEnumerable<TSymbol> symbols) {
+            return symbols.Distinct().Select(TranslateOrAdd);
+        }
+
+        int TranslateOrDie(TSymbol ch) {
+            var t = AlphabetBuilder.Translate(ch);
+            if (t == AutomatonConst.UNCLASSIFIED_INPUT)
+                    throw new ApplicationException(String.Format("Symbol '{0}' is UNCLASSIFIED", ch));
+            return t;
+        }
+
+        IEnumerable<int> TranslateOrDie(IEnumerable<TSymbol> symbols) {
+            return symbols.Distinct().Select(TranslateOrDie);
+        }
+
+        protected Token SymbolTokenExcept(IEnumerable<TSymbol> symbols) {
+            Safe.ArgumentNotNull(symbols, "symbols");
+
+            return Token.New( Enumerable.Range(0, AlphabetBuilder.Count).Except(TranslateOrDie(symbols)).ToArray() );
+        }
+
+        protected abstract IndexedAlphabetBase<TSymbol> CreateAlphabet();
+
+        protected ScannerContext<TTag> BuildScannerContext<TTag>(Token regexp) {
+            
+            var dfa = new RegularDFA<TSymbol, TTag>(AlphabetBuilder);
+
+            var visitor = new RegularExpressionVisitor<TTag>(dfa);
+            regexp.Accept(visitor);
+            visitor.BuildDFA();
+
+            if (dfa.IsFinalState(dfa.InitialState))
+                throw new ApplicationException("The specified language contains empty token");
+
+            var ab = CreateAlphabet();
+            var optimal = dfa.Optimize(ab);
+
+            return new ScannerContext<TTag>(
+                optimal.CreateTransitionTable(),
+                optimal.CreateFinalStateTable(),
+                optimal.CreateTagTable(),
+                optimal.InitialState,
+                ab.GetTranslationMap()
+            );
+        }
+
+    }
+
+
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Formats/JSON/JSONElementContext.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,11 @@
+namespace Implab.Formats.JSON {
+    /// <summary>
+    /// internal
+    /// </summary>
+    enum JSONElementContext {
+        None,
+        Object,
+        Array,
+        Closed
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Formats/JSON/JSONElementType.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,28 @@
+namespace Implab.Formats.JSON {
+    /// <summary>
+    /// Тип элемента на котором находится парсер
+    /// </summary>
+    public enum JSONElementType {
+        None,
+        /// <summary>
+        /// Начало объекта
+        /// </summary>
+        BeginObject,
+        /// <summary>
+        /// Конец объекта
+        /// </summary>
+        EndObject,
+        /// <summary>
+        /// Начало массива
+        /// </summary>
+        BeginArray,
+        /// <summary>
+        /// Конец массива
+        /// </summary>
+        EndArray,
+        /// <summary>
+        /// Простое значение
+        /// </summary>
+        Value
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Formats/JSON/JSONGrammar.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,121 @@
+using System.Linq;
+using Implab.Automaton.RegularExpressions;
+using System;
+using Implab.Automaton;
+using Implab.Components;
+
+namespace Implab.Formats.JSON {
+    class JSONGrammar : Grammar<char> {
+        public enum TokenType {
+            None,
+            BeginObject,
+            EndObject,
+            BeginArray,
+            EndArray,
+            String,
+            Number,
+            Literal,
+            NameSeparator,
+            ValueSeparator,
+            Whitespace,
+
+            StringBound,
+            EscapedChar,
+            UnescapedChar,
+            EscapedUnicode
+        }
+
+        static LazyAndWeak<JSONGrammar> _instance = new LazyAndWeak<JSONGrammar>(() => new JSONGrammar());
+
+        public static JSONGrammar Instance {
+            get { return _instance.Value; }
+        }
+
+        readonly ScannerContext<TokenType> m_jsonExpression;
+        readonly ScannerContext<TokenType> m_stringExpression;
+        readonly CharAlphabet m_defaultAlphabet = new CharAlphabet();
+
+        public JSONGrammar() {
+            DefineAlphabet(Enumerable.Range(0, 0x20).Select(x => (char)x));
+            var hexDigit = SymbolRangeToken('a','f').Or(SymbolRangeToken('A','F')).Or(SymbolRangeToken('0','9'));
+            var digit9 = SymbolRangeToken('1', '9');
+            var zero = SymbolToken('0');
+            var digit = zero.Or(digit9);
+            var dot = SymbolToken('.');
+            var minus = SymbolToken('-');
+            var sign = SymbolSetToken('-', '+');
+            var expSign = SymbolSetToken('e', 'E');
+            var letters = SymbolRangeToken('a', 'z');
+            var integer = zero.Or(digit9.Cat(digit.EClosure()));
+            var frac = dot.Cat(digit.Closure());
+            var exp = expSign.Cat(sign.Optional()).Cat(digit.Closure());
+            var quote = SymbolToken('"');
+            var backSlash = SymbolToken('\\');
+            var specialEscapeChars = SymbolSetToken('\\', '"', '/', 'b', 'f', 't', 'n', 'r');
+            var unicodeEspace = SymbolToken('u').Cat(hexDigit.Repeat(4));
+            var whitespace = SymbolSetToken('\n', '\r', '\t', ' ').EClosure();
+            var beginObject = whitespace.Cat(SymbolToken('{')).Cat(whitespace);
+            var endObject = whitespace.Cat(SymbolToken('}')).Cat(whitespace);
+            var beginArray = whitespace.Cat(SymbolToken('[')).Cat(whitespace);
+            var endArray = whitespace.Cat(SymbolToken(']')).Cat(whitespace);
+            var nameSep = whitespace.Cat(SymbolToken(':')).Cat(whitespace);
+            var valueSep = whitespace.Cat(SymbolToken(',')).Cat(whitespace);
+            
+            var number = minus.Optional().Cat(integer).Cat(frac.Optional()).Cat(exp.Optional());
+            var literal = letters.Closure();
+            var unescaped = SymbolTokenExcept(Enumerable.Range(0, 0x20).Union(new int[] { '\\', '"' }).Select(x => (char)x));
+
+            var jsonExpression =
+                number.Tag(TokenType.Number)
+                .Or(literal.Tag(TokenType.Literal))
+                .Or(quote.Tag(TokenType.StringBound))
+                .Or(beginObject.Tag(TokenType.BeginObject))
+                .Or(endObject.Tag(TokenType.EndObject))
+                .Or(beginArray.Tag(TokenType.BeginArray))
+                .Or(endArray.Tag(TokenType.EndArray))
+                .Or(nameSep.Tag(TokenType.NameSeparator))
+                .Or(valueSep.Tag(TokenType.ValueSeparator))
+                .Or(SymbolSetToken('\n', '\r', '\t', ' ').Closure().Tag(TokenType.Whitespace));
+
+
+            var jsonStringExpression =
+                quote.Tag(TokenType.StringBound)
+                .Or(backSlash.Cat(specialEscapeChars).Tag(TokenType.EscapedChar))
+                .Or(backSlash.Cat(unicodeEspace).Tag(TokenType.EscapedUnicode))
+                .Or(unescaped.Closure().Tag(TokenType.UnescapedChar));
+                    
+
+            m_jsonExpression = BuildScannerContext<TokenType>(jsonExpression);
+            m_stringExpression = BuildScannerContext<TokenType>(jsonStringExpression);
+
+
+        }
+
+        protected override IAlphabetBuilder<char> AlphabetBuilder {
+            get {
+                return m_defaultAlphabet;
+            }
+        }
+
+        public ScannerContext<TokenType> JsonExpression {
+            get {
+                return m_jsonExpression;
+            }
+        }
+
+        public ScannerContext<TokenType> JsonStringExpression {
+            get {
+                return m_stringExpression;
+            }
+        }
+
+        Token SymbolRangeToken(char start, char stop) {
+            return SymbolToken(Enumerable.Range(start, stop - start + 1).Select(x => (char)x));
+        }
+
+        protected override IndexedAlphabetBase<char> CreateAlphabet() {
+            return new CharAlphabet();
+        }
+                
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Formats/JSON/JSONParser.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,293 @@
+using System;
+using System.Diagnostics;
+using System.IO;
+using Implab.Automaton;
+using Implab.Automaton.RegularExpressions;
+using System.Linq;
+using Implab.Components;
+using System.Collections.Generic;
+
+namespace Implab.Formats.JSON {
+    /// <summary>
+    /// Pull парсер JSON данных.
+    /// </summary>
+    /// <remarks>
+    /// Следует отметить отдельную интерпретацию свойства <see cref="Level"/>,
+    /// оно означает текущий уровень вложенности объектов, однако закрывающий
+    /// элемент объекта и массива имеет уровень меньше, чем сам объект.
+    /// <code>
+    /// { // Level = 1
+    ///     "name" : "Peter", // Level = 1
+    ///     "address" : { // Level = 2
+    ///         city : "Stern" // Level = 2
+    ///     } // Level = 1
+    /// } // Level = 0
+    /// </code>
+    /// </remarks>
+    public class JSONParser : Disposable {
+
+        enum MemberContext {
+            MemberName,
+            MemberValue
+        }
+
+        #region Parser rules
+        struct ParserContext {
+            readonly int[,] m_dfa;
+            int m_state;
+
+            readonly JSONElementContext m_elementContext;
+
+            public ParserContext(int[,] dfa, int state, JSONElementContext context) {
+                m_dfa = dfa;
+                m_state = state;
+                m_elementContext = context;
+            }
+
+            public bool Move(JsonTokenType token) {
+                var next = m_dfa[m_state, (int)token];
+                if (next == AutomatonConst.UNREACHABLE_STATE)
+                    return false;
+                m_state = next;
+                return true;
+            }
+
+            public JSONElementContext ElementContext {
+                get { return m_elementContext; }
+            }
+        }
+
+        static readonly ParserContext _jsonContext;
+        static readonly ParserContext _objectContext;
+        static readonly ParserContext _arrayContext;
+
+        static JSONParser() {
+
+            var valueExpression = MakeToken(JsonTokenType.BeginArray, JsonTokenType.BeginObject, JsonTokenType.Literal, JsonTokenType.Number, JsonTokenType.String);
+            var memberExpression = MakeToken(JsonTokenType.String).Cat(MakeToken(JsonTokenType.NameSeparator)).Cat(valueExpression);
+
+            var objectExpression = memberExpression
+                .Cat(
+                    MakeToken(JsonTokenType.ValueSeparator)
+                    .Cat(memberExpression)
+                    .EClosure()
+                )
+                .Optional()
+                .Cat(MakeToken(JsonTokenType.EndObject))
+                .End();
+            
+            var arrayExpression = valueExpression
+                .Cat(
+                    MakeToken(JsonTokenType.ValueSeparator)
+                    .Cat(valueExpression)
+                    .EClosure()
+                )
+                .Optional()
+                .Cat(MakeToken(JsonTokenType.EndArray))
+                .End();
+
+            var jsonExpression = valueExpression.End();
+
+            _jsonContext = CreateParserContext(jsonExpression, JSONElementContext.None);
+            _objectContext = CreateParserContext(objectExpression, JSONElementContext.Object);
+            _arrayContext = CreateParserContext(arrayExpression, JSONElementContext.Array);
+        }
+
+        static Token MakeToken(params JsonTokenType[] input) {
+            return Token.New( input.Select(t => (int)t).ToArray() );
+        }
+
+        static ParserContext CreateParserContext(Token expr, JSONElementContext context) {
+            
+            var dfa = new DFATable();
+            var builder = new RegularExpressionVisitor(dfa);
+            expr.Accept(builder);
+            builder.BuildDFA();
+
+            return new ParserContext(dfa.CreateTransitionTable(), dfa.InitialState, context);
+        }
+
+        #endregion
+
+        readonly JSONScanner m_scanner;
+        MemberContext m_memberContext;
+
+        JSONElementType m_elementType;
+        object m_elementValue;
+        string m_memberName = String.Empty;
+
+        Stack<ParserContext> m_stack = new Stack<ParserContext>();
+        ParserContext m_context = _jsonContext;
+
+        /// <summary>
+        /// Создает новый парсер на основе строки, содержащей JSON
+        /// </summary>
+        /// <param name="text"></param>
+        public JSONParser(string text) {
+            Safe.ArgumentNotEmpty(text, "text");
+            m_scanner = new JSONScanner(text);
+        }
+
+        /// <summary>
+        /// Создает новый экземпляр парсера, на основе текстового потока.
+        /// </summary>
+        /// <param name="reader">Текстовый поток.</param>
+        public JSONParser(TextReader reader) {
+            Safe.ArgumentNotNull(reader, "reader");
+            m_scanner = new JSONScanner(reader);
+        }
+
+        public int Level {
+            get { return m_stack.Count; }
+        }
+
+        /// <summary>
+        /// Тип текущего элемента на котором стоит парсер.
+        /// </summary>
+        public JSONElementType ElementType {
+            get { return m_elementType; }
+        }
+
+        /// <summary>
+        /// Имя элемента - имя свойства родительского контейнера. Для элементов массивов и корневого всегда
+        /// пустая строка.
+        /// </summary>
+        public string ElementName {
+            get { return m_memberName; }
+        }
+
+        /// <summary>
+        /// Значение элемента. Только для элементов типа <see cref="JSONElementType.Value"/>, для остальных <c>null</c>
+        /// </summary>
+        public object ElementValue {
+            get { return m_elementValue; }
+        }
+
+        /// <summary>
+        /// Читает слеюудущий объект из потока
+        /// </summary>
+        /// <returns><c>true</c> - операция чтения прошла успешно, <c>false</c> - конец данных</returns>
+        public bool Read() {
+            object tokenValue;
+            JsonTokenType tokenType;
+
+            m_memberName = String.Empty;
+
+            while (m_scanner.ReadToken(out tokenValue, out tokenType)) {
+                if(!m_context.Move(tokenType))
+                    UnexpectedToken(tokenValue, tokenType);
+
+                switch (tokenType) {
+                    case JsonTokenType.BeginObject:
+                        m_stack.Push(m_context);
+                        m_context = _objectContext;
+
+                        m_elementValue = null;
+                        m_memberContext = MemberContext.MemberName;
+                        m_elementType = JSONElementType.BeginObject;
+                        return true;
+                    case JsonTokenType.EndObject:
+                        if (m_stack.Count == 0)
+                            UnexpectedToken(tokenValue, tokenType);
+                        m_context = m_stack.Pop();
+
+                        m_elementValue = null;
+                        m_elementType = JSONElementType.EndObject;
+                        return true;
+                    case JsonTokenType.BeginArray:
+                        m_stack.Push(m_context);
+                        m_context = _arrayContext;
+
+                        m_elementValue = null;
+                        m_memberContext = MemberContext.MemberValue;
+                        m_elementType = JSONElementType.BeginArray;
+                        return true;
+                    case JsonTokenType.EndArray:
+                        if (m_stack.Count == 0)
+                            UnexpectedToken(tokenValue, tokenType);
+                        m_context = m_stack.Pop();
+
+                        m_elementValue = null;
+                        m_elementType = JSONElementType.EndArray;
+                        return true;
+                    case JsonTokenType.String:
+                        if (m_memberContext == MemberContext.MemberName) {
+                            m_memberName = (string)tokenValue;
+                            break;
+                        }
+                        m_elementType = JSONElementType.Value;
+                        m_elementValue = tokenValue;
+                        return true;
+                    case JsonTokenType.Number:
+                        m_elementType = JSONElementType.Value;
+                        m_elementValue = tokenValue;
+                        return true;
+                    case JsonTokenType.Literal:
+                        m_elementType = JSONElementType.Value;
+                        m_elementValue = ParseLiteral((string)tokenValue);
+                        return true;
+                    case JsonTokenType.NameSeparator:
+                        m_memberContext = MemberContext.MemberValue;
+                        break;
+                    case JsonTokenType.ValueSeparator:
+                        m_memberContext = m_context.ElementContext == JSONElementContext.Object ? MemberContext.MemberName : MemberContext.MemberValue;
+                        break;
+                    default:
+                        UnexpectedToken(tokenValue, tokenType);
+                        break;
+                }
+            }
+            if (m_context.ElementContext != JSONElementContext.None)
+                throw new ParserException("Unexpedted end of data");
+
+            EOF = true;
+
+            return false;
+        }
+
+        object ParseLiteral(string literal) {
+            switch (literal) {
+                case "null":
+                    return null;
+                case "false":
+                    return false;
+                case "true":
+                    return true;
+                default:
+                    UnexpectedToken(literal, JsonTokenType.Literal);
+                    return null; // avoid compliler error
+            }
+        }
+
+        void UnexpectedToken(object value, JsonTokenType tokenType) {
+            throw new ParserException(String.Format("Unexpected token {0}: '{1}'", tokenType, value));
+        }
+
+
+        /// <summary>
+        /// Признак конца потока
+        /// </summary>
+        public bool EOF {
+            get;
+            private set;
+        }
+
+        protected override void Dispose(bool disposing) {
+            if (disposing)
+                Safe.Dispose(m_scanner);
+        }
+
+        /// <summary>
+        /// Переходит в конец текущего объекта.
+        /// </summary>
+        public void SeekElementEnd() {
+            var level = Level - 1;
+
+            Debug.Assert(level >= 0);
+
+            while (Level != level)
+                Read();
+        }
+    }
+
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Formats/JSON/JSONScanner.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,109 @@
+using System;
+using System.Globalization;
+using Implab.Automaton;
+using System.Text;
+using Implab.Components;
+using System.IO;
+
+namespace Implab.Formats.JSON {
+    /// <summary>
+    /// Сканнер (лексер), разбивающий поток символов на токены JSON.
+    /// </summary>
+    public class JSONScanner : Disposable {
+        readonly StringBuilder m_builder = new StringBuilder();
+
+        readonly ScannerContext<JSONGrammar.TokenType> m_jsonContext = JSONGrammar.Instance.JsonExpression;
+        readonly ScannerContext<JSONGrammar.TokenType> m_stringContext = JSONGrammar.Instance.JsonStringExpression;
+
+
+        readonly TextScanner m_scanner;
+
+        /// <summary>
+        /// Создает новый экземпляр сканнера
+        /// </summary>
+        public JSONScanner(string text) {
+            Safe.ArgumentNotEmpty(text, "text");
+
+            m_scanner = new StringScanner(text);
+        }
+
+        public JSONScanner(TextReader reader, int bufferMax, int chunkSize) {
+            Safe.ArgumentNotNull(reader, "reader");
+
+            m_scanner = new ReaderScanner(reader, bufferMax, chunkSize);
+        }
+
+        public JSONScanner(TextReader reader) : this(reader, 1024*1024, 1024){
+        }
+
+        /// <summary>
+        /// Читает следующий лексический элемент из входных данных.
+        /// </summary>
+        /// <param name="tokenValue">Возвращает значение прочитанного токена.</param>
+        /// <param name="tokenType">Возвращает тип прочитанного токена.</param>
+        /// <returns><c>true</c> - чтение произведено успешно. <c>false</c> - достигнут конец входных данных</returns>
+        /// <remarks>В случе если токен не распознается, возникает исключение. Значения токенов обрабатываются, т.е.
+        /// в строках обрабатываются экранированные символы, числа становтся типа double.</remarks>
+        public bool ReadToken(out object tokenValue, out JsonTokenType tokenType) {
+            JSONGrammar.TokenType[] tag;
+            while (m_jsonContext.Execute(m_scanner, out tag)) {
+                switch (tag[0]) {
+                    case JSONGrammar.TokenType.StringBound:
+                        tokenValue = ReadString();
+                        tokenType = JsonTokenType.String;
+                        break;
+                    case JSONGrammar.TokenType.Number:
+                        tokenValue = Double.Parse(m_scanner.GetTokenValue(), CultureInfo.InvariantCulture);
+                        tokenType = JsonTokenType.Number;
+                        break;
+                    case JSONGrammar.TokenType.Whitespace:
+                        continue;
+                    default:
+                        tokenType = (JsonTokenType)tag[0];
+                        tokenValue = m_scanner.GetTokenValue();
+                        break;
+                }
+                return true;
+            }
+            tokenValue = null;
+            tokenType = JsonTokenType.None;
+            return false;
+        }
+
+        string ReadString() {
+            int pos = 0;
+            var buf = new char[6]; // the buffer for unescaping chars
+
+            JSONGrammar.TokenType[] tag;
+            m_builder.Clear();
+
+            while (m_stringContext.Execute(m_scanner, out tag)) {
+                switch (tag[0]) {
+                    case JSONGrammar.TokenType.StringBound:
+                        return m_builder.ToString();
+                    case JSONGrammar.TokenType.UnescapedChar:
+                        m_scanner.CopyTokenTo(m_builder);
+                        break;
+                    case JSONGrammar.TokenType.EscapedUnicode: // \xXXXX - unicode escape sequence
+                        m_scanner.CopyTokenTo(buf, 0); 
+                        m_builder.Append(StringTranslator.TranslateHexUnicode(buf, 2));
+                        pos++;
+                        break;
+                    case JSONGrammar.TokenType.EscapedChar:  // \t - escape sequence
+                        m_scanner.CopyTokenTo(buf, 0);
+                        m_builder.Append(StringTranslator.TranslateEscapedChar(buf[1]));
+                        break;
+                }
+
+            }
+
+            throw new ParserException("Unexpected end of data");
+        }
+
+        protected override void Dispose(bool disposing) {
+            if (disposing)
+                Safe.Dispose(m_scanner);
+            base.Dispose(disposing);
+        }
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Formats/JSON/JSONWriter.cs	Fri Apr 22 13:08:08 2016 +0300
@@ -0,0 +1,319 @@
+using System;
+using System.Collections.Generic;
+using System.IO;
+using System.Globalization;
+using System.Diagnostics;
+
+namespace Implab.Formats.JSON {
+    public class JSONWriter {
+        struct Context {
+            public bool needComma;
+            public JSONElementContext element;
+        }
+        Stack<Context> m_contextStack = new Stack<Context>();
+        Context m_context;
+
+        const int BUFFER_SIZE = 64;
+
+        TextWriter m_writer;
+        readonly bool m_indent = true;
+        readonly int m_indentSize = 4;
+        readonly char[] m_buffer = new char[BUFFER_SIZE];
+        int m_bufferPos;
+
+        static readonly char [] _hex = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };
+        static readonly char [] _escapeBKS,
+            _escapeFWD,
+            _escapeCR,
+            _escapeNL,
+            _escapeTAB,
+            _escapeBSLASH,
+            _escapeQ;
+
+        static JSONWriter() {
+            _escapeBKS = "\\b".ToCharArray();
+            _escapeFWD = "\\f".ToCharArray();
+            _escapeCR = "\\r".ToCharArray();
+            _escapeNL = "\\n".ToCharArray();
+            _escapeTAB = "\\t".ToCharArray();
+            _escapeBSLASH = "\\\\".ToCharArray();
+            _escapeQ = "\\\"".ToCharArray();
+        }
+
+        public JSONWriter(TextWriter writer) {
+            Safe.ArgumentNotNull(writer, "writer");
+            m_writer = writer;
+        }
+
+        public JSONWriter(TextWriter writer, bool indent) {
+            Safe.ArgumentNotNull(writer, "writer");
+
+            m_writer = writer;
+            m_indent = indent;
+        }
+
+        void WriteIndent() {
+            if (m_indent) {
+                var indent = new char[m_contextStack.Count * m_indentSize + 1];
+                indent[0] = '\n';
+                for (int i = 1; i < indent.Length; i++)
+                    indent[i] = ' ';
+                m_writer.Write(new String(indent));
+            } else {
+                m_writer.Write(' ');
+            }
+        }
+
+        void WriteMemberName(string name) {
+            Safe.ArgumentNotEmpty(name, "name");
+            if (m_context.element != JSONElementContext.Object)
+                OperationNotApplicable("WriteMember");
+            if (m_context.needComma)
+                m_writer.Write(",");
+
+            WriteIndent();
+            m_context.needComma = true;
+            Write(name);
+            m_writer.Write(" : ");
+        }
+
+        public void WriteValue(string name, string value) {
+            WriteMemberName(name);
+            Write(value);            
+        }
+
+        public void WriteValue(string name, bool value) {
+            WriteMemberName(name);
+            Write(value);
+        }
+
+        public void WriteValue(string name, double value) {
+            WriteMemberName(name);
+            Write(value);
+        }
+
+        public void WriteValue(string value) {
+            if (m_context.element == JSONElementContext.Array) {
+
+                if (m_context.needComma)
+                    m_writer.Write(",");
+                WriteIndent();
+                m_context.needComma = true;
+
+                Write(value);
+            } else if (m_context.element == JSONElementContext.None) {
+                Write(value);
+                m_context.element = JSONElementContext.Closed;
+            } else {
+                OperationNotApplicable("WriteValue");
+            }
+        }
+
+        public void WriteValue(bool value) {
+            if (m_context.element == JSONElementContext.Array) {
+
+                if (m_context.needComma)
+                    m_writer.Write(",");
+                WriteIndent();
+                m_context.needComma = true;
+
+                Write(value);
+            } else if (m_context.element == JSONElementContext.None) {
+                Write(value);
+                m_context.element = JSONElementContext.Closed;
+            } else {
+                OperationNotApplicable("WriteValue");
+            }
+        }
+
+        public void WriteValue(double value) {
+            if (m_context.element == JSONElementContext.Array) {
+
+                if (m_context.needComma)
+                    m_writer.Write(",");
+                WriteIndent();
+                m_context.needComma = true;
+
+                Write(value);
+            } else if (m_context.element == JSONElementContext.None) {
+                Write(value);
+                m_context.element = JSONElementContext.Closed;
+            } else {
+                OperationNotApplicable("WriteValue");
+            }
+        }
+        
+        public void BeginObject() {
+            if (m_context.element != JSONElementContext.None && m_context.element != JSONElementContext.Array)
+                OperationNotApplicable("BeginObject");
+            if (m_context.needComma)
+                m_writer.Write(",");
+
+            WriteIndent();
+
+            m_context.needComma = true;
+
+            m_contextStack.Push(m_context);
+
+            m_context = new Context { element = JSONElementContext.Object, needComma = false };
+            m_writer.Write("{");
+        }
+
+        public void BeginObject(string name) {
+            WriteMemberName(name);
+
+            m_contextStack.Push(m_context);
+
+            m_context = new Context { element = JSONElementContext.Object, needComma = false };
+            m_writer.Write("{");
+        }
+
+        public void EndObject() {
+            if (m_context.element != JSONElementContext.Object)
+                OperationNotApplicable("EndObject");
+
+            m_context = m_contextStack.Pop();
+            if (m_contextStack.Count == 0)
+                m_context.element = JSONElementContext.Closed;
+            WriteIndent();
+            m_writer.Write("}");
+        }
+
+        public void BeginArray() {
+            if (m_context.element != JSONElementContext.None && m_context.element != JSONElementContext.Array)
+                throw new InvalidOperationException();
+            if (m_context.needComma) {
+                m_writer.Write(",");
+
+            }
+            m_context.needComma = true;
+
+            WriteIndent();
+            m_contextStack.Push(m_context);
+            m_context = new Context { element = JSONElementContext.Array, needComma = false };
+            m_writer.Write("[");
+        }
+
+        public void BeginArray(string name) {
+            WriteMemberName(name);
+
+            m_contextStack.Push(m_context);
+
+            m_context = new Context { element = JSONElementContext.Array, needComma = false };
+            m_writer.Write("[");
+        }
+
+        public void EndArray() {
+            if (m_context.element != JSONElementContext.Array)
+                OperationNotApplicable("EndArray");
+
+            m_context = m_contextStack.Pop();
+            if (m_contextStack.Count == 0)
+                m_context.element = JSONElementContext.Closed;
+            WriteIndent();
+            m_writer.Write("]");
+        }
+
+        void Write(bool value) {
+            m_writer.Write(value ? "true" : "false");
+        }
+
+        void FlushBuffer() {
+            if (m_bufferPos > 0) {
+                m_writer.Write(m_buffer, 0, m_bufferPos);
+                m_bufferPos = 0;
+            }
+        }
+
+        void Write(string value) {
+            if (value == null) {
+                m_writer.Write("null");
+                return;
+            }
+
+            Debug.Assert(m_bufferPos == 0);
+
+            var chars = value.ToCharArray();
+            m_buffer[m_bufferPos++] = '"';
+
+            // Analysis disable once ForCanBeConvertedToForeach
+            for (int i = 0; i < chars.Length; i++) {
+                var ch = chars[i];
+
+                char[] escapeSeq;
+
+                switch (ch) {
+                    case '\b':
+                        escapeSeq = _escapeBKS;
+                        break;
+                    case '\f':
+                        escapeSeq = _escapeFWD;
+                        break;
+                    case '\r':
+                        escapeSeq = _escapeCR;
+                        break;
+                    case '\n':
+                        escapeSeq = _escapeNL;
+                        break;
+                    case '\t':
+                        escapeSeq = _escapeTAB;
+                        break;
+                    case '\\':
+                        escapeSeq = _escapeBSLASH;
+                        break;
+                    case '"':
+                        escapeSeq = _escapeQ;
+                        break;
+                    default:
+                        if (ch < 0x20) {
+                            if (m_bufferPos + 6 > BUFFER_SIZE)
+                                FlushBuffer();
+
+                            m_buffer[m_bufferPos++] = '\\';
+                            m_buffer[m_bufferPos++] = 'u';
+                            m_buffer[m_bufferPos++] = '0';
+                            m_buffer[m_bufferPos++] = '0';
+                            m_buffer[m_bufferPos++] = _hex[ch >> 4 & 0xf];
+                            m_buffer[m_bufferPos++] = _hex[ch & 0xf];
+
+                        } else {
+                            if (m_bufferPos >= BUFFER_SIZE)
+                                FlushBuffer();
+                            m_buffer[m_bufferPos++] = ch;
+                        }
+                        continue;
+                }
+
+                if (m_bufferPos + escapeSeq.Length > BUFFER_SIZE)
+                    FlushBuffer();
+
+                Array.Copy(escapeSeq, 0, m_buffer, m_bufferPos, escapeSeq.Length);
+                m_bufferPos += escapeSeq.Length;
+
+            }
+
+            if (m_bufferPos >= BUFFER_SIZE)
+                FlushBuffer();
+            
+            m_buffer[m_bufferPos++] = '"';
+
+            FlushBuffer();
+        }
+
+        void Write(double value) {
+            if (double.IsNaN(value))
+                Write("NaN");
+            else if (double.IsNegativeInfinity(value))
+                Write("-Infinity");
+            else if (double.IsPositiveInfinity(value))
+                Write("Infinity");
+            else
+                m_writer.Write(value.ToString(CultureInfo.InvariantCulture));
+        }
+
+        void OperationNotApplicable(string opName) {
+            throw new InvalidOperationException(String.Format("The operation '{0}' isn't applicable in the context of '{1}'", opName, m_context.element ));
+        }
+        
+    }
+}