Auto status change to "Under Review"
| @@ -0,0 +1,127 | |||
|
|
1 | using Implab.Automaton; | |
|
|
2 | using System; | |
|
|
3 | using System.Collections.Generic; | |
|
|
4 | using System.Diagnostics; | |
|
|
5 | using System.Linq; | |
|
|
6 | using System.Runtime.CompilerServices; | |
|
|
7 | using System.Text; | |
|
|
8 | using System.Threading.Tasks; | |
|
|
9 | ||
|
|
10 | namespace Implab.Formats { | |
|
|
11 | ||
|
|
12 | /// <summary> | |
|
|
13 | /// Fast input scanner for max 255 states and first 255 input chacters. | |
|
|
14 | /// </summary> | |
|
|
15 | /// <typeparam name="TTag"></typeparam> | |
|
|
16 | /// <remarks> | |
|
|
17 | /// Creates a one rank array to store automa transition table, each entry in this table is byte, to make this table fit into L1 cache. | |
|
|
18 | /// | |
|
|
19 | /// Each entry is addressed as <c>(state << 8) | input</c> which make this quite fast to get the next state. | |
|
|
20 | /// | |
|
|
21 | /// Each input symbol below 255 is treated as 255. | |
|
|
22 | /// </remarks> | |
|
|
23 | public class FastInputScanner<TTag> { | |
|
|
24 | const int StateShift = 8; | |
|
|
25 | const int StateMask = ~((1 << StateShift) - 1); | |
|
|
26 | const int AlphabetSize = 1 << StateShift; | |
|
|
27 | const int UnclassifiedInput = (1 << StateShift) - 1; | |
|
|
28 | const byte UnreachableState = byte.MaxValue; | |
|
|
29 | ||
|
|
30 | readonly TTag[] m_tags; | |
|
|
31 | readonly bool[] m_final; | |
|
|
32 | ||
|
|
33 | readonly byte m_initialState; | |
|
|
34 | readonly byte[] m_dfa; | |
|
|
35 | ||
|
|
36 | int m_position; | |
|
|
37 | byte m_state; | |
|
|
38 | ||
|
|
39 | protected FastInputScanner(byte[] table, bool[] final, TTag[] tags, byte initial) { | |
|
|
40 | m_dfa = table; | |
|
|
41 | m_final = final; | |
|
|
42 | m_tags = tags; | |
|
|
43 | m_initialState = initial; | |
|
|
44 | } | |
|
|
45 | ||
|
|
46 | public FastInputScanner(int[,] dfaTable, bool[] finalStates, TTag[] tags, int initialState, int[] inputMap) { | |
|
|
47 | var states = dfaTable.GetLength(0); | |
|
|
48 | Debug.Assert(states < byte.MaxValue); | |
|
|
49 | ||
|
|
50 | m_dfa = new byte[states << StateShift]; | |
|
|
51 | m_initialState = (byte)initialState; | |
|
|
52 | ||
|
|
53 | m_tags = tags; | |
|
|
54 | m_final = finalStates; | |
|
|
55 | ||
|
|
56 | // iterate over states | |
|
|
57 | for(int si = 0; si < states; si++) { | |
|
|
58 | // state offset for the new table | |
|
|
59 | var offset = si << StateShift; | |
|
|
60 | ||
|
|
61 | // iterate over alphabet | |
|
|
62 | for(int a = 0; a < AlphabetSize; a++) { | |
|
|
63 | var next = dfaTable[si, a < inputMap.Length ? inputMap[a] : AutomatonConst.UnclassifiedInput]; | |
|
|
64 | if (next == AutomatonConst.UnreachableState) | |
|
|
65 | next = UnreachableState; | |
|
|
66 | ||
|
|
67 | m_dfa[offset | a] = (byte)next; | |
|
|
68 | } | |
|
|
69 | } | |
|
|
70 | } | |
|
|
71 | ||
|
|
72 | public TTag Tag { | |
|
|
73 | [MethodImpl(MethodImplOptions.AggressiveInlining)] | |
|
|
74 | get { | |
|
|
75 | return m_tags[m_state]; | |
|
|
76 | } | |
|
|
77 | } | |
|
|
78 | ||
|
|
79 | public int Position { | |
|
|
80 | [MethodImpl(MethodImplOptions.AggressiveInlining)] | |
|
|
81 | get { | |
|
|
82 | return m_position; | |
|
|
83 | } | |
|
|
84 | } | |
|
|
85 | ||
|
|
86 | public bool IsFinal { | |
|
|
87 | [MethodImpl(MethodImplOptions.AggressiveInlining)] | |
|
|
88 | get { | |
|
|
89 | return m_final[m_state]; | |
|
|
90 | } | |
|
|
91 | } | |
|
|
92 | ||
|
|
93 | [MethodImpl(MethodImplOptions.AggressiveInlining)] | |
|
|
94 | public void ResetState() { | |
|
|
95 | m_state = m_initialState; | |
|
|
96 | } | |
|
|
97 | ||
|
|
98 | public FastInputScanner<TTag> Clone() { | |
|
|
99 | var clone = new FastInputScanner<TTag>(m_dfa, m_final, m_tags, m_initialState); | |
|
|
100 | clone.m_state = m_state; | |
|
|
101 | clone.m_position = m_position; | |
|
|
102 | return clone; | |
|
|
103 | } | |
|
|
104 | ||
|
|
105 | public bool Scan(char[] data, int offset, int max) { | |
|
|
106 | var next = m_state; | |
|
|
107 | ||
|
|
108 | m_position = offset; | |
|
|
109 | while (m_position < max) { | |
|
|
110 | var ch = data[m_position]; | |
|
|
111 | ||
|
|
112 | next = m_dfa[(ch >= AlphabetSize ? (next << StateShift) | UnclassifiedInput : (next << StateShift) | ch)]; | |
|
|
113 | ||
|
|
114 | if (next == UnreachableState) | |
|
|
115 | // scanner stops at the next position after the last recognized symbol | |
|
|
116 | return false; | |
|
|
117 | ||
|
|
118 | m_state = next; | |
|
|
119 | m_position++; | |
|
|
120 | } | |
|
|
121 | ||
|
|
122 | return true; | |
|
|
123 | } | |
|
|
124 | ||
|
|
125 | ||
|
|
126 | } | |
|
|
127 | } | |
| @@ -1,189 +1,189 | |||
|
|
1 | 1 | ο»Ώ<?xml version="1.0" encoding="utf-8"?> |
|
|
2 | 2 | <Project DefaultTargets="Build" ToolsVersion="12.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003"> |
|
|
3 | 3 | <PropertyGroup> |
|
|
4 | 4 | <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration> |
|
|
5 | 5 | <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform> |
|
|
6 | 6 | <ProjectGuid>{F550F1F8-8746-4AD0-9614-855F4C4B7F05}</ProjectGuid> |
|
|
7 | 7 | <OutputType>Library</OutputType> |
|
|
8 | 8 | <RootNamespace>Implab</RootNamespace> |
|
|
9 | 9 | <AssemblyName>Implab</AssemblyName> |
|
|
10 | 10 | <TargetFrameworkVersion>v4.5</TargetFrameworkVersion> |
|
|
11 | 11 | <TargetFrameworkProfile /> |
|
|
12 | 12 | </PropertyGroup> |
|
|
13 | 13 | <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' "> |
|
|
14 | 14 | <DebugSymbols>true</DebugSymbols> |
|
|
15 | 15 | <DebugType>full</DebugType> |
|
|
16 |
<Optimize> |
|
|
|
16 | <Optimize>true</Optimize> | |
|
|
17 | 17 | <OutputPath>bin\Debug</OutputPath> |
|
|
18 | 18 | <DefineConstants>TRACE;DEBUG;NET_4_5</DefineConstants> |
|
|
19 | 19 | <ErrorReport>prompt</ErrorReport> |
|
|
20 | 20 | <WarningLevel>4</WarningLevel> |
|
|
21 | 21 | <ConsolePause>false</ConsolePause> |
|
|
22 | 22 | <RunCodeAnalysis>true</RunCodeAnalysis> |
|
|
23 | 23 | </PropertyGroup> |
|
|
24 | 24 | <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' "> |
|
|
25 | 25 | <DebugType>full</DebugType> |
|
|
26 | 26 | <Optimize>true</Optimize> |
|
|
27 | 27 | <OutputPath>bin\Release</OutputPath> |
|
|
28 | 28 | <DefineConstants>NET_4_5</DefineConstants> |
|
|
29 | 29 | <ErrorReport>prompt</ErrorReport> |
|
|
30 | 30 | <WarningLevel>4</WarningLevel> |
|
|
31 | 31 | <ConsolePause>false</ConsolePause> |
|
|
32 | 32 | </PropertyGroup> |
|
|
33 | 33 | <PropertyGroup> |
|
|
34 |
<SignAssembly> |
|
|
|
34 | <SignAssembly>false</SignAssembly> | |
|
|
35 | 35 | </PropertyGroup> |
|
|
36 | 36 | <PropertyGroup> |
|
|
37 | 37 | <AssemblyOriginatorKeyFile>implab.snk</AssemblyOriginatorKeyFile> |
|
|
38 | 38 | </PropertyGroup> |
|
|
39 | 39 | <ItemGroup> |
|
|
40 | 40 | <Reference Include="System" /> |
|
|
41 | 41 | <Reference Include="System.Xml" /> |
|
|
42 | 42 | <Reference Include="mscorlib" /> |
|
|
43 | 43 | <Reference Include="System.Xml.Linq" /> |
|
|
44 | 44 | </ItemGroup> |
|
|
45 | 45 | <ItemGroup> |
|
|
46 | 46 | <Compile Include="Components\StateChangeEventArgs.cs" /> |
|
|
47 | 47 | <Compile Include="CustomEqualityComparer.cs" /> |
|
|
48 | 48 | <Compile Include="Diagnostics\ConsoleTraceListener.cs" /> |
|
|
49 | 49 | <Compile Include="Diagnostics\LogChannel.cs" /> |
|
|
50 | 50 | <Compile Include="Diagnostics\LogicalOperation.cs" /> |
|
|
51 | 51 | <Compile Include="Diagnostics\TextFileListener.cs" /> |
|
|
52 | 52 | <Compile Include="Diagnostics\Trace.cs" /> |
|
|
53 | 53 | <Compile Include="Diagnostics\TraceLog.cs" /> |
|
|
54 | 54 | <Compile Include="Diagnostics\TraceEvent.cs" /> |
|
|
55 | 55 | <Compile Include="Diagnostics\TraceEventType.cs" /> |
|
|
56 | 56 | <Compile Include="Diagnostics\TraceSourceAttribute.cs" /> |
|
|
57 | 57 | <Compile Include="Formats\CharMap.cs" /> |
|
|
58 | 58 | <Compile Include="Formats\FastInpurScanner.cs" /> |
|
|
59 | 59 | <Compile Include="Formats\InputScanner.cs" /> |
|
|
60 | 60 | <Compile Include="Formats\Json\JsonStringScanner.cs" /> |
|
|
61 | 61 | <Compile Include="Formats\Json\JsonTextScanner.cs" /> |
|
|
62 | 62 | <Compile Include="ICancellable.cs" /> |
|
|
63 | 63 | <Compile Include="IProgressHandler.cs" /> |
|
|
64 | 64 | <Compile Include="IProgressNotifier.cs" /> |
|
|
65 | 65 | <Compile Include="IPromiseT.cs" /> |
|
|
66 | 66 | <Compile Include="IPromise.cs" /> |
|
|
67 | 67 | <Compile Include="IServiceLocator.cs" /> |
|
|
68 | 68 | <Compile Include="ITaskController.cs" /> |
|
|
69 | 69 | <Compile Include="Parallels\DispatchPool.cs" /> |
|
|
70 | 70 | <Compile Include="Parallels\ArrayTraits.cs" /> |
|
|
71 | 71 | <Compile Include="Parallels\SimpleAsyncQueue.cs" /> |
|
|
72 | 72 | <Compile Include="Parallels\WorkerPool.cs" /> |
|
|
73 | 73 | <Compile Include="ProgressInitEventArgs.cs" /> |
|
|
74 | 74 | <Compile Include="Properties\AssemblyInfo.cs" /> |
|
|
75 | 75 | <Compile Include="Parallels\AsyncPool.cs" /> |
|
|
76 | 76 | <Compile Include="Safe.cs" /> |
|
|
77 | 77 | <Compile Include="SyncContextPromise.cs" /> |
|
|
78 | 78 | <Compile Include="ValueEventArgs.cs" /> |
|
|
79 | 79 | <Compile Include="PromiseExtensions.cs" /> |
|
|
80 | 80 | <Compile Include="SyncContextPromiseT.cs" /> |
|
|
81 | 81 | <Compile Include="Diagnostics\OperationContext.cs" /> |
|
|
82 | 82 | <Compile Include="Diagnostics\TraceContext.cs" /> |
|
|
83 | 83 | <Compile Include="Diagnostics\LogEventArgs.cs" /> |
|
|
84 | 84 | <Compile Include="Diagnostics\LogEventArgsT.cs" /> |
|
|
85 | 85 | <Compile Include="Diagnostics\Extensions.cs" /> |
|
|
86 | 86 | <Compile Include="PromiseEventType.cs" /> |
|
|
87 | 87 | <Compile Include="Parallels\AsyncQueue.cs" /> |
|
|
88 | 88 | <Compile Include="PromiseT.cs" /> |
|
|
89 | 89 | <Compile Include="IDeferred.cs" /> |
|
|
90 | 90 | <Compile Include="IDeferredT.cs" /> |
|
|
91 | 91 | <Compile Include="Promise.cs" /> |
|
|
92 | 92 | <Compile Include="PromiseTransientException.cs" /> |
|
|
93 | 93 | <Compile Include="Parallels\Signal.cs" /> |
|
|
94 | 94 | <Compile Include="Parallels\SharedLock.cs" /> |
|
|
95 | 95 | <Compile Include="Diagnostics\ILogWriter.cs" /> |
|
|
96 | 96 | <Compile Include="Diagnostics\ListenerBase.cs" /> |
|
|
97 | 97 | <Compile Include="Parallels\BlockingQueue.cs" /> |
|
|
98 | 98 | <Compile Include="AbstractEvent.cs" /> |
|
|
99 | 99 | <Compile Include="AbstractPromise.cs" /> |
|
|
100 | 100 | <Compile Include="AbstractPromiseT.cs" /> |
|
|
101 | 101 | <Compile Include="FuncTask.cs" /> |
|
|
102 | 102 | <Compile Include="FuncTaskBase.cs" /> |
|
|
103 | 103 | <Compile Include="FuncTaskT.cs" /> |
|
|
104 | 104 | <Compile Include="ActionChainTaskBase.cs" /> |
|
|
105 | 105 | <Compile Include="ActionChainTask.cs" /> |
|
|
106 | 106 | <Compile Include="ActionChainTaskT.cs" /> |
|
|
107 | 107 | <Compile Include="FuncChainTaskBase.cs" /> |
|
|
108 | 108 | <Compile Include="FuncChainTask.cs" /> |
|
|
109 | 109 | <Compile Include="FuncChainTaskT.cs" /> |
|
|
110 | 110 | <Compile Include="ActionTaskBase.cs" /> |
|
|
111 | 111 | <Compile Include="ActionTask.cs" /> |
|
|
112 | 112 | <Compile Include="ActionTaskT.cs" /> |
|
|
113 | 113 | <Compile Include="ICancellationToken.cs" /> |
|
|
114 | 114 | <Compile Include="SuccessPromise.cs" /> |
|
|
115 | 115 | <Compile Include="SuccessPromiseT.cs" /> |
|
|
116 | 116 | <Compile Include="PromiseAwaiterT.cs" /> |
|
|
117 | 117 | <Compile Include="PromiseAwaiter.cs" /> |
|
|
118 | 118 | <Compile Include="Components\ComponentContainer.cs" /> |
|
|
119 | 119 | <Compile Include="Components\Disposable.cs" /> |
|
|
120 | 120 | <Compile Include="Components\DisposablePool.cs" /> |
|
|
121 | 121 | <Compile Include="Components\ObjectPool.cs" /> |
|
|
122 | 122 | <Compile Include="Components\ServiceLocator.cs" /> |
|
|
123 | 123 | <Compile Include="Components\IInitializable.cs" /> |
|
|
124 | 124 | <Compile Include="TaskController.cs" /> |
|
|
125 | 125 | <Compile Include="Components\App.cs" /> |
|
|
126 | 126 | <Compile Include="Components\IRunnable.cs" /> |
|
|
127 | 127 | <Compile Include="Components\ExecutionState.cs" /> |
|
|
128 | 128 | <Compile Include="Components\RunnableComponent.cs" /> |
|
|
129 | 129 | <Compile Include="Components\IFactory.cs" /> |
|
|
130 | 130 | <Compile Include="Automaton\IAlphabet.cs" /> |
|
|
131 | 131 | <Compile Include="Automaton\ParserException.cs" /> |
|
|
132 | 132 | <Compile Include="Automaton\IndexedAlphabetBase.cs" /> |
|
|
133 | 133 | <Compile Include="Automaton\IAlphabetBuilder.cs" /> |
|
|
134 | 134 | <Compile Include="Automaton\RegularExpressions\AltToken.cs" /> |
|
|
135 | 135 | <Compile Include="Automaton\RegularExpressions\BinaryToken.cs" /> |
|
|
136 | 136 | <Compile Include="Automaton\RegularExpressions\CatToken.cs" /> |
|
|
137 | 137 | <Compile Include="Automaton\RegularExpressions\StarToken.cs" /> |
|
|
138 | 138 | <Compile Include="Automaton\RegularExpressions\SymbolToken.cs" /> |
|
|
139 | 139 | <Compile Include="Automaton\RegularExpressions\EmptyToken.cs" /> |
|
|
140 | 140 | <Compile Include="Automaton\RegularExpressions\Token.cs" /> |
|
|
141 | 141 | <Compile Include="Automaton\RegularExpressions\IVisitor.cs" /> |
|
|
142 | 142 | <Compile Include="Automaton\AutomatonTransition.cs" /> |
|
|
143 | 143 | <Compile Include="Formats\Json\JsonElementContext.cs" /> |
|
|
144 | 144 | <Compile Include="Formats\Json\JsonElementType.cs" /> |
|
|
145 | 145 | <Compile Include="Formats\Json\JsonGrammar.cs" /> |
|
|
146 | 146 | <Compile Include="Formats\Json\JsonReader.cs" /> |
|
|
147 | 147 | <Compile Include="Formats\Json\JsonScanner.cs" /> |
|
|
148 | 148 | <Compile Include="Formats\Json\JsonTokenType.cs" /> |
|
|
149 | 149 | <Compile Include="Formats\Json\JsonWriter.cs" /> |
|
|
150 | 150 | <Compile Include="Formats\Json\StringTranslator.cs" /> |
|
|
151 | 151 | <Compile Include="Automaton\MapAlphabet.cs" /> |
|
|
152 | 152 | <Compile Include="Formats\CharAlphabet.cs" /> |
|
|
153 | 153 | <Compile Include="Formats\ByteAlphabet.cs" /> |
|
|
154 | 154 | <Compile Include="Automaton\IDFATable.cs" /> |
|
|
155 | 155 | <Compile Include="Automaton\IDFATableBuilder.cs" /> |
|
|
156 | 156 | <Compile Include="Automaton\DFATable.cs" /> |
|
|
157 | 157 | <Compile Include="Automaton\RegularExpressions\RegularExpressionVisitor.cs" /> |
|
|
158 | 158 | <Compile Include="Automaton\RegularExpressions\ITaggedDFABuilder.cs" /> |
|
|
159 | 159 | <Compile Include="Formats\Grammar.cs" /> |
|
|
160 | 160 | <Compile Include="Automaton\RegularExpressions\EndTokenT.cs" /> |
|
|
161 | 161 | <Compile Include="Automaton\RegularExpressions\EndToken.cs" /> |
|
|
162 | 162 | <Compile Include="Automaton\RegularExpressions\RegularExpressionVisitorT.cs" /> |
|
|
163 | 163 | <Compile Include="Automaton\AutomatonConst.cs" /> |
|
|
164 | 164 | <Compile Include="Automaton\RegularExpressions\RegularDFA.cs" /> |
|
|
165 | 165 | <Compile Include="Components\LazyAndWeak.cs" /> |
|
|
166 | 166 | <Compile Include="AbstractTask.cs" /> |
|
|
167 | 167 | <Compile Include="AbstractTaskT.cs" /> |
|
|
168 | 168 | <Compile Include="FailedPromise.cs" /> |
|
|
169 | 169 | <Compile Include="FailedPromiseT.cs" /> |
|
|
170 | 170 | <Compile Include="Components\PollingComponent.cs" /> |
|
|
171 | 171 | <Compile Include="Xml\JsonXmlReader.cs" /> |
|
|
172 | 172 | <Compile Include="Xml\JsonXmlReaderOptions.cs" /> |
|
|
173 | 173 | <Compile Include="Xml\JsonXmlReaderPosition.cs" /> |
|
|
174 | 174 | <Compile Include="Xml\SerializationHelpers.cs" /> |
|
|
175 | 175 | <Compile Include="Xml\SerializersPool.cs" /> |
|
|
176 | 176 | <Compile Include="Xml\XmlSimpleAttribute.cs" /> |
|
|
177 | 177 | <Compile Include="Xml\XmlNameContext.cs" /> |
|
|
178 | 178 | </ItemGroup> |
|
|
179 | 179 | <Import Project="$(MSBuildBinPath)\Microsoft.CSharp.targets" /> |
|
|
180 | 180 | <ItemGroup> |
|
|
181 | 181 | <None Include="Implab.nuspec"> |
|
|
182 | 182 | <SubType>Designer</SubType> |
|
|
183 | 183 | </None> |
|
|
184 | 184 | <None Include="implab.snk" /> |
|
|
185 | 185 | </ItemGroup> |
|
|
186 | 186 | <ItemGroup> |
|
|
187 | 187 | <Content Include="license.txt" /> |
|
|
188 | 188 | </ItemGroup> |
|
|
189 | 189 | </Project> No newline at end of file |
General Comments 3
You need to be logged in to leave comments.
Login now