##// END OF EJS Templates
fixed regression: race condition in Promise...
cin -
r160:5802131432e4 v2
parent child
Show More
@@ -1,300 +1,304
1 using System;
1 using System;
2 using Implab.Parallels;
2 using Implab.Parallels;
3 using System.Threading;
3 using System.Threading;
4 using System.Reflection;
4 using System.Reflection;
5
5
6 namespace Implab {
6 namespace Implab {
7 public abstract class AbstractEvent<THandler> : ICancellationToken, ICancellable {
7 public abstract class AbstractEvent<THandler> : ICancellationToken, ICancellable {
8
8
9 const int UNRESOLVED_SATE = 0;
9 const int UNRESOLVED_SATE = 0;
10 const int TRANSITIONAL_STATE = 1;
10 const int TRANSITIONAL_STATE = 1;
11 protected const int SUCCEEDED_STATE = 2;
11 protected const int SUCCEEDED_STATE = 2;
12 protected const int REJECTED_STATE = 3;
12 protected const int REJECTED_STATE = 3;
13 protected const int CANCELLED_STATE = 4;
13 protected const int CANCELLED_STATE = 4;
14
14
15 const int CANCEL_NOT_REQUESTED = 0;
15 const int CANCEL_NOT_REQUESTED = 0;
16 const int CANCEL_REQUESTING = 1;
16 const int CANCEL_REQUESTING = 1;
17 const int CANCEL_REQUESTED = 2;
17 const int CANCEL_REQUESTED = 2;
18
18
19 const int RESERVED_HANDLERS_COUNT = 4;
19 const int RESERVED_HANDLERS_COUNT = 4;
20
20
21 int m_state;
21 int m_state;
22 Exception m_error;
22 Exception m_error;
23 int m_handlersCount;
23 int m_handlersCount;
24
24
25 //readonly THandler[] m_handlers = new THandler[RESERVED_HANDLERS_COUNT];
25 //readonly THandler[] m_handlers = new THandler[RESERVED_HANDLERS_COUNT];
26 THandler[] m_handlers;
26 THandler[] m_handlers;
27 MTQueue<THandler> m_extraHandlers;
27 MTQueue<THandler> m_extraHandlers;
28 int m_handlerPointer = -1;
28 int m_handlerPointer = -1;
29 int m_handlersCommited;
29 int m_handlersCommited;
30
30
31 int m_cancelRequest;
31 int m_cancelRequest;
32 Exception m_cancelationReason;
32 Exception m_cancelationReason;
33 MTQueue<Action<Exception>> m_cancelationHandlers;
33 MTQueue<Action<Exception>> m_cancelationHandlers;
34
34
35
35
36 #region state managment
36 #region state managment
37 bool BeginTransit() {
37 bool BeginTransit() {
38 return UNRESOLVED_SATE == Interlocked.CompareExchange(ref m_state, TRANSITIONAL_STATE, UNRESOLVED_SATE);
38 return UNRESOLVED_SATE == Interlocked.CompareExchange(ref m_state, TRANSITIONAL_STATE, UNRESOLVED_SATE);
39 }
39 }
40
40
41 void CompleteTransit(int state) {
41 void CompleteTransit(int state) {
42 if (TRANSITIONAL_STATE != Interlocked.CompareExchange(ref m_state, state, TRANSITIONAL_STATE))
42 if (TRANSITIONAL_STATE != Interlocked.CompareExchange(ref m_state, state, TRANSITIONAL_STATE))
43 throw new InvalidOperationException("Can't complete transition when the object isn't in the transitional state");
43 throw new InvalidOperationException("Can't complete transition when the object isn't in the transitional state");
44 }
44 }
45
45
46 void WaitTransition() {
46 void WaitTransition() {
47 while (m_state == TRANSITIONAL_STATE) {
47 while (m_state == TRANSITIONAL_STATE) {
48 Thread.MemoryBarrier();
48 Thread.MemoryBarrier();
49 }
49 }
50 }
50 }
51
51
52 protected bool BeginSetResult() {
52 protected bool BeginSetResult() {
53 if (!BeginTransit()) {
53 if (!BeginTransit()) {
54 WaitTransition();
54 WaitTransition();
55 if (m_state != CANCELLED_STATE)
55 if (m_state != CANCELLED_STATE)
56 throw new InvalidOperationException("The promise is already resolved");
56 throw new InvalidOperationException("The promise is already resolved");
57 return false;
57 return false;
58 }
58 }
59 return true;
59 return true;
60 }
60 }
61
61
62 protected void EndSetResult() {
62 protected void EndSetResult() {
63 CompleteTransit(SUCCEEDED_STATE);
63 CompleteTransit(SUCCEEDED_STATE);
64 Signal();
64 Signal();
65 }
65 }
66
66
67
67
68
68
69 /// <summary>
69 /// <summary>
70 /// ВыполняСт ΠΎΠ±Π΅Ρ‰Π°Π½ΠΈΠ΅, сообщая ΠΎΠ± ошибкС
70 /// ВыполняСт ΠΎΠ±Π΅Ρ‰Π°Π½ΠΈΠ΅, сообщая ΠΎΠ± ошибкС
71 /// </summary>
71 /// </summary>
72 /// <remarks>
72 /// <remarks>
73 /// ΠŸΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ ΠΎΠ±Π΅Ρ‰Π°Π½ΠΈΠ΅ Π΄ΠΎΠ»ΠΆΠ½ΠΎ Ρ€Π°Π±ΠΎΡ‚Π°Ρ‚ΡŒ Π² ΠΌΠ½ΠΎΠ³ΠΎΠΏΡ‚ΠΎΡ‡Π½ΠΎΠΉ срСдС, ΠΏΡ€ΠΈ Π΅Π³ΠΎ Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ΠΈΠΈ сразу нСсколько ΠΏΠΎΡ‚ΠΎΠΊΠΎΠ²
73 /// ΠŸΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ ΠΎΠ±Π΅Ρ‰Π°Π½ΠΈΠ΅ Π΄ΠΎΠ»ΠΆΠ½ΠΎ Ρ€Π°Π±ΠΎΡ‚Π°Ρ‚ΡŒ Π² ΠΌΠ½ΠΎΠ³ΠΎΠΏΡ‚ΠΎΡ‡Π½ΠΎΠΉ срСдС, ΠΏΡ€ΠΈ Π΅Π³ΠΎ Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ΠΈΠΈ сразу нСсколько ΠΏΠΎΡ‚ΠΎΠΊΠΎΠ²
74 /// ΠΌΠΎΠ³Ρƒ Π²Π΅Ρ€Π½ΡƒΡ‚ΡŒ ΠΎΡˆΠΈΠ±ΠΊΡƒ, ΠΏΡ€ΠΈ этом Ρ‚ΠΎΠ»ΡŒΠΊΠΎ пСрвая Π±ΡƒΠ΄Π΅Ρ‚ использована Π² качСствС Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π°, ΠΎΡΡ‚Π°Π»ΡŒΠ½Ρ‹Π΅
74 /// ΠΌΠΎΠ³Ρƒ Π²Π΅Ρ€Π½ΡƒΡ‚ΡŒ ΠΎΡˆΠΈΠ±ΠΊΡƒ, ΠΏΡ€ΠΈ этом Ρ‚ΠΎΠ»ΡŒΠΊΠΎ пСрвая Π±ΡƒΠ΄Π΅Ρ‚ использована Π² качСствС Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π°, ΠΎΡΡ‚Π°Π»ΡŒΠ½Ρ‹Π΅
75 /// Π±ΡƒΠ΄ΡƒΡ‚ ΠΏΡ€ΠΎΠΈΠ³Π½ΠΎΡ€ΠΈΡ€ΠΎΠ²Π°Π½Ρ‹.
75 /// Π±ΡƒΠ΄ΡƒΡ‚ ΠΏΡ€ΠΎΠΈΠ³Π½ΠΎΡ€ΠΈΡ€ΠΎΠ²Π°Π½Ρ‹.
76 /// </remarks>
76 /// </remarks>
77 /// <param name="error">Π˜ΡΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΠ΅ возникшСС ΠΏΡ€ΠΈ Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ΠΈΠΈ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ</param>
77 /// <param name="error">Π˜ΡΠΊΠ»ΡŽΡ‡Π΅Π½ΠΈΠ΅ возникшСС ΠΏΡ€ΠΈ Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ΠΈΠΈ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ</param>
78 /// <exception cref="InvalidOperationException">Π”Π°Π½Π½ΠΎΠ΅ ΠΎΠ±Π΅Ρ‰Π°Π½ΠΈΠ΅ ΡƒΠΆΠ΅ Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ΠΎ</exception>
78 /// <exception cref="InvalidOperationException">Π”Π°Π½Π½ΠΎΠ΅ ΠΎΠ±Π΅Ρ‰Π°Π½ΠΈΠ΅ ΡƒΠΆΠ΅ Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ΠΎ</exception>
79 protected void SetError(Exception error) {
79 protected void SetError(Exception error) {
80 if (BeginTransit()) {
80 if (BeginTransit()) {
81 if (error is OperationCanceledException) {
81 if (error is OperationCanceledException) {
82 m_error = error.InnerException;
82 m_error = error.InnerException;
83 CompleteTransit(CANCELLED_STATE);
83 CompleteTransit(CANCELLED_STATE);
84 } else {
84 } else {
85 m_error = error is PromiseTransientException ? error.InnerException : error;
85 m_error = error is PromiseTransientException ? error.InnerException : error;
86 CompleteTransit(REJECTED_STATE);
86 CompleteTransit(REJECTED_STATE);
87 }
87 }
88 Signal();
88 Signal();
89 } else {
89 } else {
90 WaitTransition();
90 WaitTransition();
91 if (m_state == SUCCEEDED_STATE)
91 if (m_state == SUCCEEDED_STATE)
92 throw new InvalidOperationException("The promise is already resolved");
92 throw new InvalidOperationException("The promise is already resolved");
93 }
93 }
94 }
94 }
95
95
96 /// <summary>
96 /// <summary>
97 /// ΠžΡ‚ΠΌΠ΅Π½ΡΠ΅Ρ‚ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΡŽ, Ссли это Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ.
97 /// ΠžΡ‚ΠΌΠ΅Π½ΡΠ΅Ρ‚ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΡŽ, Ссли это Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ.
98 /// </summary>
98 /// </summary>
99 /// <remarks>Для опрСдСлСния Π±Ρ‹Π»Π° Π»ΠΈ опСрация ΠΎΡ‚ΠΌΠ΅Π½Π΅Π½Π° слСдуСт ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ свойство <see cref="IsCancelled"/>.</remarks>
99 /// <remarks>Для опрСдСлСния Π±Ρ‹Π»Π° Π»ΠΈ опСрация ΠΎΡ‚ΠΌΠ΅Π½Π΅Π½Π° слСдуСт ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ свойство <see cref="IsCancelled"/>.</remarks>
100 protected void SetCancelled(Exception reason) {
100 protected void SetCancelled(Exception reason) {
101 if (BeginTransit()) {
101 if (BeginTransit()) {
102 m_error = reason;
102 m_error = reason;
103 CompleteTransit(CANCELLED_STATE);
103 CompleteTransit(CANCELLED_STATE);
104 Signal();
104 Signal();
105 }
105 }
106 }
106 }
107
107
108 protected abstract void SignalHandler(THandler handler, int signal);
108 protected abstract void SignalHandler(THandler handler, int signal);
109
109
110 void Signal() {
110 void Signal() {
111 var hp = m_handlerPointer;
111 var hp = m_handlerPointer;
112 var slot = hp +1 ;
112 var slot = hp +1 ;
113 while (slot < m_handlersCommited) {
113 while (slot < m_handlersCommited) {
114 if (Interlocked.CompareExchange(ref m_handlerPointer, slot, hp) == hp) {
114 if (Interlocked.CompareExchange(ref m_handlerPointer, slot, hp) == hp) {
115 SignalHandler(m_handlers[slot], m_state);
115 SignalHandler(m_handlers[slot], m_state);
116 }
116 }
117 hp = m_handlerPointer;
117 hp = m_handlerPointer;
118 slot = hp +1 ;
118 slot = hp +1 ;
119 }
119 }
120
120
121
121
122 if (m_extraHandlers != null) {
122 if (m_extraHandlers != null) {
123 THandler handler;
123 THandler handler;
124 while (m_extraHandlers.TryDequeue(out handler))
124 while (m_extraHandlers.TryDequeue(out handler))
125 SignalHandler(handler, m_state);
125 SignalHandler(handler, m_state);
126 }
126 }
127 }
127 }
128
128
129 #endregion
129 #endregion
130
130
131 protected abstract Signal GetResolveSignal();
131 protected abstract Signal GetResolveSignal();
132
132
133 #region synchronization traits
133 #region synchronization traits
134 protected void WaitResult(int timeout) {
134 protected void WaitResult(int timeout) {
135 if (!(IsResolved || GetResolveSignal().Wait(timeout)))
135 if (!(IsResolved || GetResolveSignal().Wait(timeout)))
136 throw new TimeoutException();
136 throw new TimeoutException();
137
137
138 switch (m_state) {
138 switch (m_state) {
139 case SUCCEEDED_STATE:
139 case SUCCEEDED_STATE:
140 return;
140 return;
141 case CANCELLED_STATE:
141 case CANCELLED_STATE:
142 throw new OperationCanceledException();
142 throw new OperationCanceledException();
143 case REJECTED_STATE:
143 case REJECTED_STATE:
144 throw new TargetInvocationException(m_error);
144 throw new TargetInvocationException(m_error);
145 default:
145 default:
146 throw new ApplicationException(String.Format("Invalid promise state {0}", m_state));
146 throw new ApplicationException(String.Format("Invalid promise state {0}", m_state));
147 }
147 }
148 }
148 }
149 #endregion
149 #endregion
150
150
151 #region handlers managment
151 #region handlers managment
152
152
153 protected void AddHandler(THandler handler) {
153 protected void AddHandler(THandler handler) {
154
154
155 if (m_state > 1) {
155 if (m_state > 1) {
156 // the promise is in the resolved state, just invoke the handler
156 // the promise is in the resolved state, just invoke the handler
157 SignalHandler(handler, m_state);
157 SignalHandler(handler, m_state);
158 } else {
158 } else {
159 var slot = Interlocked.Increment(ref m_handlersCount) - 1;
159 var slot = Interlocked.Increment(ref m_handlersCount) - 1;
160
160
161 if (slot < RESERVED_HANDLERS_COUNT) {
161 if (slot < RESERVED_HANDLERS_COUNT) {
162
162
163 if (slot == 0)
163 if (slot == 0) {
164 Interlocked.CompareExchange(ref m_handlers, new THandler[RESERVED_HANDLERS_COUNT], null);
164 m_handlers = new THandler[RESERVED_HANDLERS_COUNT];
165 } else {
166 while (m_handlers == null)
167 Thread.MemoryBarrier();
168 }
165
169
166 m_handlers[slot] = handler;
170 m_handlers[slot] = handler;
167
171
168 while (slot != Interlocked.CompareExchange(ref m_handlersCommited, slot + 1, slot)) {
172 while (slot != Interlocked.CompareExchange(ref m_handlersCommited, slot + 1, slot)) {
169 }
173 }
170
174
171 if (m_state > 1) {
175 if (m_state > 1) {
172 do {
176 do {
173 var hp = m_handlerPointer;
177 var hp = m_handlerPointer;
174 slot = hp + 1;
178 slot = hp + 1;
175 if (slot < m_handlersCommited) {
179 if (slot < m_handlersCommited) {
176 if (Interlocked.CompareExchange(ref m_handlerPointer, slot, hp) != hp)
180 if (Interlocked.CompareExchange(ref m_handlerPointer, slot, hp) != hp)
177 continue;
181 continue;
178 SignalHandler(m_handlers[slot], m_state);
182 SignalHandler(m_handlers[slot], m_state);
179 }
183 }
180 break;
184 break;
181 } while(true);
185 } while(true);
182 }
186 }
183 } else {
187 } else {
184 if (slot == RESERVED_HANDLERS_COUNT) {
188 if (slot == RESERVED_HANDLERS_COUNT) {
185 m_extraHandlers = new MTQueue<THandler>();
189 m_extraHandlers = new MTQueue<THandler>();
186 } else {
190 } else {
187 while (m_extraHandlers == null)
191 while (m_extraHandlers == null)
188 Thread.MemoryBarrier();
192 Thread.MemoryBarrier();
189 }
193 }
190
194
191 m_extraHandlers.Enqueue(handler);
195 m_extraHandlers.Enqueue(handler);
192
196
193 if (m_state > 1 && m_extraHandlers.TryDequeue(out handler))
197 if (m_state > 1 && m_extraHandlers.TryDequeue(out handler))
194 // if the promise have been resolved while we was adding the handler to the queue
198 // if the promise have been resolved while we was adding the handler to the queue
195 // we can't guarantee that someone is still processing it
199 // we can't guarantee that someone is still processing it
196 // therefore we need to fetch a handler from the queue and execute it
200 // therefore we need to fetch a handler from the queue and execute it
197 // note that fetched handler may be not the one that we have added
201 // note that fetched handler may be not the one that we have added
198 // even we can fetch no handlers at all :)
202 // even we can fetch no handlers at all :)
199 SignalHandler(handler, m_state);
203 SignalHandler(handler, m_state);
200 }
204 }
201 }
205 }
202 }
206 }
203
207
204 #endregion
208 #endregion
205
209
206 #region IPromise implementation
210 #region IPromise implementation
207
211
208 public bool IsResolved {
212 public bool IsResolved {
209 get {
213 get {
210 Thread.MemoryBarrier();
214 Thread.MemoryBarrier();
211 return m_state > 1;
215 return m_state > 1;
212 }
216 }
213 }
217 }
214
218
215 public bool IsCancelled {
219 public bool IsCancelled {
216 get {
220 get {
217 Thread.MemoryBarrier();
221 Thread.MemoryBarrier();
218 return m_state == CANCELLED_STATE;
222 return m_state == CANCELLED_STATE;
219 }
223 }
220 }
224 }
221
225
222 #endregion
226 #endregion
223
227
224 public Exception Error {
228 public Exception Error {
225 get {
229 get {
226 return m_error;
230 return m_error;
227 }
231 }
228 }
232 }
229
233
230 public bool CancelOperationIfRequested() {
234 public bool CancelOperationIfRequested() {
231 if (IsCancellationRequested) {
235 if (IsCancellationRequested) {
232 CancelOperation(CancellationReason);
236 CancelOperation(CancellationReason);
233 return true;
237 return true;
234 }
238 }
235 return false;
239 return false;
236 }
240 }
237
241
238 public virtual void CancelOperation(Exception reason) {
242 public virtual void CancelOperation(Exception reason) {
239 SetCancelled(reason);
243 SetCancelled(reason);
240 }
244 }
241
245
242 public void CancellationRequested(Action<Exception> handler) {
246 public void CancellationRequested(Action<Exception> handler) {
243 Safe.ArgumentNotNull(handler, "handler");
247 Safe.ArgumentNotNull(handler, "handler");
244 if (IsCancellationRequested)
248 if (IsCancellationRequested)
245 handler(CancellationReason);
249 handler(CancellationReason);
246
250
247 if (m_cancelationHandlers == null)
251 if (m_cancelationHandlers == null)
248 Interlocked.CompareExchange(ref m_cancelationHandlers, new MTQueue<Action<Exception>>(), null);
252 Interlocked.CompareExchange(ref m_cancelationHandlers, new MTQueue<Action<Exception>>(), null);
249
253
250 m_cancelationHandlers.Enqueue(handler);
254 m_cancelationHandlers.Enqueue(handler);
251
255
252 if (IsCancellationRequested && m_cancelationHandlers.TryDequeue(out handler))
256 if (IsCancellationRequested && m_cancelationHandlers.TryDequeue(out handler))
253 // TryDeque implies MemoryBarrier()
257 // TryDeque implies MemoryBarrier()
254 handler(m_cancelationReason);
258 handler(m_cancelationReason);
255 }
259 }
256
260
257 public bool IsCancellationRequested {
261 public bool IsCancellationRequested {
258 get {
262 get {
259 do {
263 do {
260 if (m_cancelRequest == CANCEL_NOT_REQUESTED)
264 if (m_cancelRequest == CANCEL_NOT_REQUESTED)
261 return false;
265 return false;
262 if (m_cancelRequest == CANCEL_REQUESTED)
266 if (m_cancelRequest == CANCEL_REQUESTED)
263 return true;
267 return true;
264 Thread.MemoryBarrier();
268 Thread.MemoryBarrier();
265 } while(true);
269 } while(true);
266 }
270 }
267 }
271 }
268
272
269 public Exception CancellationReason {
273 public Exception CancellationReason {
270 get {
274 get {
271 do {
275 do {
272 Thread.MemoryBarrier();
276 Thread.MemoryBarrier();
273 } while(m_cancelRequest == CANCEL_REQUESTING);
277 } while(m_cancelRequest == CANCEL_REQUESTING);
274
278
275 return m_cancelationReason;
279 return m_cancelationReason;
276 }
280 }
277 }
281 }
278
282
279 #region ICancellable implementation
283 #region ICancellable implementation
280
284
281 public void Cancel() {
285 public void Cancel() {
282 Cancel(null);
286 Cancel(null);
283 }
287 }
284
288
285 public void Cancel(Exception reason) {
289 public void Cancel(Exception reason) {
286 if (CANCEL_NOT_REQUESTED == Interlocked.CompareExchange(ref m_cancelRequest, CANCEL_REQUESTING, CANCEL_NOT_REQUESTED)) {
290 if (CANCEL_NOT_REQUESTED == Interlocked.CompareExchange(ref m_cancelRequest, CANCEL_REQUESTING, CANCEL_NOT_REQUESTED)) {
287 m_cancelationReason = reason;
291 m_cancelationReason = reason;
288 m_cancelRequest = CANCEL_REQUESTED;
292 m_cancelRequest = CANCEL_REQUESTED;
289 if (m_cancelationHandlers != null) {
293 if (m_cancelationHandlers != null) {
290 Action<Exception> handler;
294 Action<Exception> handler;
291 while (m_cancelationHandlers.TryDequeue(out handler))
295 while (m_cancelationHandlers.TryDequeue(out handler))
292 handler(m_cancelationReason);
296 handler(m_cancelationReason);
293 }
297 }
294 }
298 }
295 }
299 }
296
300
297 #endregion
301 #endregion
298 }
302 }
299 }
303 }
300
304
@@ -1,24 +1,22
1 namespace Implab.Parsing {
1 namespace Implab.Parsing {
2 public class CDFADefinition : DFADefinition {
2 public class CDFADefinition : DFADefinition {
3 readonly CharAlphabet m_alphabet;
3 readonly CharAlphabet m_alphabet;
4
4
5 public CharAlphabet Alphabet {
5 public CharAlphabet Alphabet {
6 get { return m_alphabet; }
6 get { return m_alphabet; }
7 }
7 }
8
8
9 public CDFADefinition(CharAlphabet alphabet): base(alphabet.Count) {
9 public CDFADefinition(CharAlphabet alphabet): base(alphabet.Count) {
10 m_alphabet = alphabet;
10 m_alphabet = alphabet;
11 }
11 }
12
12
13 public CDFADefinition Optimize() {
13 public CDFADefinition Optimize() {
14 var optimized = new CDFADefinition(new CharAlphabet());
15
14
16 Optimize(optimized, m_alphabet, optimized.Alphabet);
15 return (CDFADefinition)Optimize(alphabet => new CDFADefinition((CharAlphabet)alphabet), m_alphabet, new CharAlphabet());
17 return optimized;
18 }
16 }
19
17
20 public void PrintDFA() {
18 public void PrintDFA() {
21 PrintDFA(m_alphabet);
19 PrintDFA(m_alphabet);
22 }
20 }
23 }
21 }
24 }
22 }
@@ -1,264 +1,267
1 using Implab;
1 using Implab;
2 using System;
2 using System;
3 using System.Collections.Generic;
3 using System.Collections.Generic;
4 using System.Diagnostics;
4 using System.Diagnostics;
5 using System.Linq;
5 using System.Linq;
6
6
7 namespace Implab.Parsing {
7 namespace Implab.Parsing {
8 public class DFADefinition : IDFADefinition {
8 public class DFADefinition : IDFADefinition {
9 readonly List<DFAStateDescriptior> m_states;
9 readonly List<DFAStateDescriptior> m_states;
10
10
11 public const int INITIAL_STATE = 1;
11 public const int INITIAL_STATE = 1;
12 public const int UNREACHEBLE_STATE = 0;
12 public const int UNREACHEBLE_STATE = 0;
13
13
14 DFAStateDescriptior[] m_statesArray;
14 DFAStateDescriptior[] m_statesArray;
15 readonly int m_alpabetSize;
15 readonly int m_alpabetSize;
16
16
17 public DFADefinition(int alphabetSize) {
17 public DFADefinition(int alphabetSize) {
18 m_states = new List<DFAStateDescriptior>();
18 m_states = new List<DFAStateDescriptior>();
19 m_alpabetSize = alphabetSize;
19 m_alpabetSize = alphabetSize;
20
20
21 m_states.Add(new DFAStateDescriptior());
21 m_states.Add(new DFAStateDescriptior());
22 }
22 }
23
23
24 public DFAStateDescriptior[] States {
24 public DFAStateDescriptior[] States {
25 get {
25 get {
26 if (m_statesArray == null)
26 if (m_statesArray == null)
27 m_statesArray = m_states.ToArray();
27 m_statesArray = m_states.ToArray();
28 return m_statesArray;
28 return m_statesArray;
29 }
29 }
30 }
30 }
31
31
32 public bool InitialStateIsFinal {
32 public bool InitialStateIsFinal {
33 get {
33 get {
34 return m_states[INITIAL_STATE].final;
34 return m_states[INITIAL_STATE].final;
35 }
35 }
36 }
36 }
37
37
38 public int AddState() {
38 public int AddState() {
39 var index = m_states.Count;
39 var index = m_states.Count;
40 m_states.Add(new DFAStateDescriptior {
40 m_states.Add(new DFAStateDescriptior {
41 final = false,
41 final = false,
42 transitions = new int[AlphabetSize]
42 transitions = new int[AlphabetSize]
43 });
43 });
44 m_statesArray = null;
44 m_statesArray = null;
45
45
46 return index;
46 return index;
47 }
47 }
48
48
49 public int AddState(int[] tag) {
49 public int AddState(int[] tag) {
50 var index = m_states.Count;
50 var index = m_states.Count;
51 bool final = tag != null && tag.Length != 0;
51 bool final = tag != null && tag.Length != 0;
52 m_states.Add(new DFAStateDescriptior {
52 m_states.Add(new DFAStateDescriptior {
53 final = final,
53 final = final,
54 transitions = new int[AlphabetSize],
54 transitions = new int[AlphabetSize],
55 tag = final ? tag : null
55 tag = final ? tag : null
56 });
56 });
57 m_statesArray = null;
57 m_statesArray = null;
58 return index;
58 return index;
59 }
59 }
60
60
61 public void DefineTransition(int s1,int s2, int symbol) {
61 public void DefineTransition(int s1,int s2, int symbol) {
62 Safe.ArgumentInRange(s1, 0, m_states.Count-1, "s1");
62 Safe.ArgumentInRange(s1, 0, m_states.Count-1, "s1");
63 Safe.ArgumentInRange(s2, 0, m_states.Count-1, "s2");
63 Safe.ArgumentInRange(s2, 0, m_states.Count-1, "s2");
64 Safe.ArgumentInRange(symbol, 0, AlphabetSize-1, "symbol");
64 Safe.ArgumentInRange(symbol, 0, AlphabetSize-1, "symbol");
65
65
66 m_states[s1].transitions[symbol] = s2;
66 m_states[s1].transitions[symbol] = s2;
67 }
67 }
68
68
69 public void Optimize<TA>(IDFADefinition minimalDFA,IAlphabet<TA> sourceAlphabet, IAlphabet<TA> minimalAlphabet) {
69 protected IDFADefinition Optimize<TA>(Func<IAlphabet<TA>, IDFADefinition> dfaFactory,IAlphabet<TA> sourceAlphabet, IAlphabet<TA> minimalAlphabet) {
70 Safe.ArgumentNotNull(minimalDFA, "minimalDFA");
70 Safe.ArgumentNotNull(dfaFactory, "dfaFactory");
71 Safe.ArgumentNotNull(minimalAlphabet, "minimalAlphabet");
71 Safe.ArgumentNotNull(minimalAlphabet, "minimalAlphabet");
72
72
73 var setComparer = new CustomEqualityComparer<HashSet<int>>(
73 var setComparer = new CustomEqualityComparer<HashSet<int>>(
74 (x, y) => x.SetEquals(y),
74 (x, y) => x.SetEquals(y),
75 (s) => s.Sum(x => x.GetHashCode())
75 (s) => s.Sum(x => x.GetHashCode())
76 );
76 );
77
77
78 var arrayComparer = new CustomEqualityComparer<int[]>(
78 var arrayComparer = new CustomEqualityComparer<int[]>(
79 (x,y) => (new HashSet<int>(x)).SetEquals(new HashSet<int>(y)),
79 (x,y) => (new HashSet<int>(x)).SetEquals(new HashSet<int>(y)),
80 (a) => a.Sum(x => x.GetHashCode())
80 (a) => a.Sum(x => x.GetHashCode())
81 );
81 );
82
82
83 var optimalStates = new HashSet<HashSet<int>>(setComparer);
83 var optimalStates = new HashSet<HashSet<int>>(setComparer);
84 var queue = new HashSet<HashSet<int>>(setComparer);
84 var queue = new HashSet<HashSet<int>>(setComparer);
85
85
86 foreach (var g in Enumerable
86 foreach (var g in Enumerable
87 .Range(INITIAL_STATE, m_states.Count-1)
87 .Range(INITIAL_STATE, m_states.Count-1)
88 .Select(i => new {
88 .Select(i => new {
89 index = i,
89 index = i,
90 descriptor = m_states[i]
90 descriptor = m_states[i]
91 })
91 })
92 .Where(x => x.descriptor.final)
92 .Where(x => x.descriptor.final)
93 .GroupBy(x => x.descriptor.tag, arrayComparer)
93 .GroupBy(x => x.descriptor.tag, arrayComparer)
94 ) {
94 ) {
95 optimalStates.Add(new HashSet<int>(g.Select(x => x.index)));
95 optimalStates.Add(new HashSet<int>(g.Select(x => x.index)));
96 }
96 }
97
97
98 var state = new HashSet<int>(
98 var state = new HashSet<int>(
99 Enumerable
99 Enumerable
100 .Range(INITIAL_STATE, m_states.Count - 1)
100 .Range(INITIAL_STATE, m_states.Count - 1)
101 .Where(i => !m_states[i].final)
101 .Where(i => !m_states[i].final)
102 );
102 );
103 optimalStates.Add(state);
103 optimalStates.Add(state);
104 queue.Add(state);
104 queue.Add(state);
105
105
106 while (queue.Count > 0) {
106 while (queue.Count > 0) {
107 var stateA = queue.First();
107 var stateA = queue.First();
108 queue.Remove(stateA);
108 queue.Remove(stateA);
109
109
110 for (int c = 0; c < AlphabetSize; c++) {
110 for (int c = 0; c < AlphabetSize; c++) {
111 var stateX = new HashSet<int>();
111 var stateX = new HashSet<int>();
112
112
113 for(int s = 1; s < m_states.Count; s++) {
113 for(int s = 1; s < m_states.Count; s++) {
114 if (stateA.Contains(m_states[s].transitions[c]))
114 if (stateA.Contains(m_states[s].transitions[c]))
115 stateX.Add(s);
115 stateX.Add(s);
116 }
116 }
117
117
118 foreach (var stateY in optimalStates.ToArray()) {
118 foreach (var stateY in optimalStates.ToArray()) {
119 if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
119 if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
120 var stateR1 = new HashSet<int>(stateY);
120 var stateR1 = new HashSet<int>(stateY);
121 var stateR2 = new HashSet<int>(stateY);
121 var stateR2 = new HashSet<int>(stateY);
122
122
123 stateR1.IntersectWith(stateX);
123 stateR1.IntersectWith(stateX);
124 stateR2.ExceptWith(stateX);
124 stateR2.ExceptWith(stateX);
125
125
126 optimalStates.Remove(stateY);
126 optimalStates.Remove(stateY);
127 optimalStates.Add(stateR1);
127 optimalStates.Add(stateR1);
128 optimalStates.Add(stateR2);
128 optimalStates.Add(stateR2);
129
129
130 if (queue.Contains(stateY)) {
130 if (queue.Contains(stateY)) {
131 queue.Remove(stateY);
131 queue.Remove(stateY);
132 queue.Add(stateR1);
132 queue.Add(stateR1);
133 queue.Add(stateR2);
133 queue.Add(stateR2);
134 } else {
134 } else {
135 queue.Add(stateR1.Count <= stateR2.Count ? stateR1 : stateR2);
135 queue.Add(stateR1.Count <= stateR2.Count ? stateR1 : stateR2);
136 }
136 }
137 }
137 }
138 }
138 }
139 }
139 }
140 }
140 }
141
141
142 // строим ΠΊΠ°Ρ€Ρ‚Ρ‹ соотвСствия ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Ρ… состояний с ΠΎΡ€ΠΈΠ³ΠΈΠ½Π°Π»ΡŒΠ½Ρ‹ΠΌΠΈ
142 // строим ΠΊΠ°Ρ€Ρ‚Ρ‹ соотвСствия ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Ρ… состояний с ΠΎΡ€ΠΈΠ³ΠΈΠ½Π°Π»ΡŒΠ½Ρ‹ΠΌΠΈ
143
143
144 var initialState = optimalStates.Single(x => x.Contains(INITIAL_STATE));
144 var initialState = optimalStates.Single(x => x.Contains(INITIAL_STATE));
145
145
146 // ΠΊΠ°Ρ€Ρ‚Π° получСния ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ состояния ΠΏΠΎ ΡΠΎΠΎΡ‚Π²Π΅ΡΡ‚Π²ΡƒΡŽΡ‰Π΅ΠΌΡƒ Π΅ΠΌΡƒ простому ΡΠΎΡΡ‚ΠΎΡΠ½ΠΈΡŽ
146 // ΠΊΠ°Ρ€Ρ‚Π° получСния ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ состояния ΠΏΠΎ ΡΠΎΠΎΡ‚Π²Π΅ΡΡ‚Π²ΡƒΡŽΡ‰Π΅ΠΌΡƒ Π΅ΠΌΡƒ простому ΡΠΎΡΡ‚ΠΎΡΠ½ΠΈΡŽ
147 int[] reveseOptimalMap = new int[m_states.Count];
147 int[] reveseOptimalMap = new int[m_states.Count];
148 // ΠΊΠ°Ρ€Ρ‚Π° с индСксами ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Ρ… состояний
148 // ΠΊΠ°Ρ€Ρ‚Π° с индСксами ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Ρ… состояний
149 HashSet<int>[] optimalMap = new HashSet<int>[optimalStates.Count + 1];
149 HashSet<int>[] optimalMap = new HashSet<int>[optimalStates.Count + 1];
150 {
150 {
151 optimalMap[0] = new HashSet<int>(); // unreachable state
151 optimalMap[0] = new HashSet<int>(); // unreachable state
152 optimalMap[1] = initialState; // initial state
152 optimalMap[1] = initialState; // initial state
153 foreach (var ss in initialState)
153 foreach (var ss in initialState)
154 reveseOptimalMap[ss] = 1;
154 reveseOptimalMap[ss] = 1;
155
155
156 int i = 2;
156 int i = 2;
157 foreach (var s in optimalStates) {
157 foreach (var s in optimalStates) {
158 if (s.SetEquals(initialState))
158 if (s.SetEquals(initialState))
159 continue;
159 continue;
160 optimalMap[i] = s;
160 optimalMap[i] = s;
161 foreach (var ss in s)
161 foreach (var ss in s)
162 reveseOptimalMap[ss] = i;
162 reveseOptimalMap[ss] = i;
163 i++;
163 i++;
164 }
164 }
165 }
165 }
166
166
167 // ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ Π°Π»Ρ„Π°Π²ΠΈΡ‚
167 // ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ Π°Π»Ρ„Π°Π²ΠΈΡ‚
168
168
169 var minClasses = new HashSet<HashSet<int>>(setComparer);
169 var minClasses = new HashSet<HashSet<int>>(setComparer);
170 var alphaQueue = new Queue<HashSet<int>>();
170 var alphaQueue = new Queue<HashSet<int>>();
171 alphaQueue.Enqueue(new HashSet<int>(Enumerable.Range(0,AlphabetSize)));
171 alphaQueue.Enqueue(new HashSet<int>(Enumerable.Range(0,AlphabetSize)));
172
172
173 for (int s = 1 ; s < optimalMap.Length; s++) {
173 for (int s = 1 ; s < optimalMap.Length; s++) {
174 var newQueue = new Queue<HashSet<int>>();
174 var newQueue = new Queue<HashSet<int>>();
175
175
176 foreach (var A in alphaQueue) {
176 foreach (var A in alphaQueue) {
177 if (A.Count == 1) {
177 if (A.Count == 1) {
178 minClasses.Add(A);
178 minClasses.Add(A);
179 continue;
179 continue;
180 }
180 }
181
181
182 // Ρ€Π°Π·Π»ΠΈΡ‡Π°Π΅ΠΌ классы символов, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ пСрСводят Π² Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Π΅ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ состояния
182 // Ρ€Π°Π·Π»ΠΈΡ‡Π°Π΅ΠΌ классы символов, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ пСрСводят Π² Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Π΅ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ состояния
183 // optimalState -> alphaClass
183 // optimalState -> alphaClass
184 var classes = new Dictionary<int, HashSet<int>>();
184 var classes = new Dictionary<int, HashSet<int>>();
185
185
186 foreach (var term in A) {
186 foreach (var term in A) {
187 // ΠΈΡ‰Π΅ΠΌ всС ΠΏΠ΅Ρ€Π΅Ρ…ΠΎΠ΄Ρ‹ класса ΠΏΠΎ символу term
187 // ΠΈΡ‰Π΅ΠΌ всС ΠΏΠ΅Ρ€Π΅Ρ…ΠΎΠ΄Ρ‹ класса ΠΏΠΎ символу term
188 var s2 = reveseOptimalMap[
188 var s2 = reveseOptimalMap[
189 optimalMap[s].Select(x => m_states[x].transitions[term]).FirstOrDefault(x => x != 0) // ΠΏΠ΅Ρ€Π²ΠΎΠ΅ допустимоС элСмСнтарноС состояниС, Ссли Π΅ΡΡ‚ΡŒ
189 optimalMap[s].Select(x => m_states[x].transitions[term]).FirstOrDefault(x => x != 0) // ΠΏΠ΅Ρ€Π²ΠΎΠ΅ допустимоС элСмСнтарноС состояниС, Ссли Π΅ΡΡ‚ΡŒ
190 ];
190 ];
191
191
192 HashSet<int> A2;
192 HashSet<int> A2;
193 if (!classes.TryGetValue(s2, out A2)) {
193 if (!classes.TryGetValue(s2, out A2)) {
194 A2 = new HashSet<int>();
194 A2 = new HashSet<int>();
195 newQueue.Enqueue(A2);
195 newQueue.Enqueue(A2);
196 classes[s2] = A2;
196 classes[s2] = A2;
197 }
197 }
198 A2.Add(term);
198 A2.Add(term);
199 }
199 }
200 }
200 }
201
201
202 if (newQueue.Count == 0)
202 if (newQueue.Count == 0)
203 break;
203 break;
204 alphaQueue = newQueue;
204 alphaQueue = newQueue;
205 }
205 }
206
206
207 foreach (var A in alphaQueue)
207 foreach (var A in alphaQueue)
208 minClasses.Add(A);
208 minClasses.Add(A);
209
209
210 var alphabetMap = sourceAlphabet.Reclassify(minimalAlphabet, minClasses);
210 var alphabetMap = sourceAlphabet.Reclassify(minimalAlphabet, minClasses);
211
211
212 // построСниС Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚Π°
212 // построСниС Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚Π°
213
213
214 var minimalDFA = dfaFactory(minimalAlphabet);
215
214 var states = new int[ optimalMap.Length ];
216 var states = new int[ optimalMap.Length ];
215 states[0] = UNREACHEBLE_STATE;
217 states[0] = UNREACHEBLE_STATE;
216
218
217 for(var s = INITIAL_STATE; s < states.Length; s++) {
219 for(var s = INITIAL_STATE; s < states.Length; s++) {
218 var tags = optimalMap[s].SelectMany(x => m_states[x].tag ?? Enumerable.Empty<int>()).Distinct().ToArray();
220 var tags = optimalMap[s].SelectMany(x => m_states[x].tag ?? Enumerable.Empty<int>()).Distinct().ToArray();
219 if (tags.Length > 0)
221 if (tags.Length > 0)
220 states[s] = minimalDFA.AddState(tags);
222 states[s] = minimalDFA.AddState(tags);
221 else
223 else
222 states[s] = minimalDFA.AddState();
224 states[s] = minimalDFA.AddState();
223 }
225 }
224
226
225 Debug.Assert(states[INITIAL_STATE] == INITIAL_STATE);
227 Debug.Assert(states[INITIAL_STATE] == INITIAL_STATE);
226
228
227 for (int s1 = 1; s1 < m_states.Count; s1++) {
229 for (int s1 = 1; s1 < m_states.Count; s1++) {
228 for (int c = 0; c < AlphabetSize; c++) {
230 for (int c = 0; c < AlphabetSize; c++) {
229 var s2 = m_states[s1].transitions[c];
231 var s2 = m_states[s1].transitions[c];
230 if (s2 != UNREACHEBLE_STATE) {
232 if (s2 != UNREACHEBLE_STATE) {
231 minimalDFA.DefineTransition(
233 minimalDFA.DefineTransition(
232 reveseOptimalMap[s1],
234 reveseOptimalMap[s1],
233 reveseOptimalMap[s2],
235 reveseOptimalMap[s2],
234 alphabetMap[c]
236 alphabetMap[c]
235 );
237 );
236 }
238 }
237 }
239 }
238 }
240 }
239
241
242 return minimalDFA;
240 }
243 }
241
244
242 public void PrintDFA<TA>(IAlphabet<TA> alphabet) {
245 public void PrintDFA<TA>(IAlphabet<TA> alphabet) {
243
246
244 var reverseMap = alphabet.CreateReverseMap();
247 var reverseMap = alphabet.CreateReverseMap();
245
248
246 for (int i = 1; i < reverseMap.Length; i++) {
249 for (int i = 1; i < reverseMap.Length; i++) {
247 Console.WriteLine("C{0}: {1}", i, String.Join(",", reverseMap[i]));
250 Console.WriteLine("C{0}: {1}", i, String.Join(",", reverseMap[i]));
248 }
251 }
249
252
250 for (int i = 1; i < m_states.Count; i++) {
253 for (int i = 1; i < m_states.Count; i++) {
251 var s = m_states[i];
254 var s = m_states[i];
252 for (int c = 0; c < AlphabetSize; c++)
255 for (int c = 0; c < AlphabetSize; c++)
253 if (s.transitions[c] != UNREACHEBLE_STATE)
256 if (s.transitions[c] != UNREACHEBLE_STATE)
254 Console.WriteLine("S{0} -{1}-> S{2}{3}", i, String.Join(",", reverseMap[c]), s.transitions[c], m_states[s.transitions[c]].final ? "$" : "");
257 Console.WriteLine("S{0} -{1}-> S{2}{3}", i, String.Join(",", reverseMap[c]), s.transitions[c], m_states[s.transitions[c]].final ? "$" : "");
255 }
258 }
256 }
259 }
257
260
258 public int AlphabetSize {
261 public int AlphabetSize {
259 get {
262 get {
260 return m_alpabetSize;
263 return m_alpabetSize;
261 }
264 }
262 }
265 }
263 }
266 }
264 }
267 }
@@ -1,31 +1,29
1 using Implab;
1 using Implab;
2 using System;
2 using System;
3
3
4 namespace Implab.Parsing {
4 namespace Implab.Parsing {
5 public class EDFADefinition<T> : DFADefinition where T : struct, IConvertible {
5 public class EDFADefinition<T> : DFADefinition where T : struct, IConvertible {
6 readonly EnumAlphabet<T> m_alphabet;
6 readonly EnumAlphabet<T> m_alphabet;
7
7
8 public EnumAlphabet<T> Alphabet {
8 public EnumAlphabet<T> Alphabet {
9 get { return m_alphabet; }
9 get { return m_alphabet; }
10 }
10 }
11
11
12 public EDFADefinition(EnumAlphabet<T> alphabet) : base(alphabet.Count) {
12 public EDFADefinition(EnumAlphabet<T> alphabet) : base(alphabet.Count) {
13 m_alphabet = alphabet;
13 m_alphabet = alphabet;
14 }
14 }
15
15
16 public void DefineTransition(int s1, int s2, T input) {
16 public void DefineTransition(int s1, int s2, T input) {
17 DefineTransition(s1, s2, m_alphabet.Translate(input));
17 DefineTransition(s1, s2, m_alphabet.Translate(input));
18 }
18 }
19
19
20 public EDFADefinition<T> Optimize() {
20 public EDFADefinition<T> Optimize() {
21 var optimized = new EDFADefinition<T>(new EnumAlphabet<T>());
22 Optimize(optimized, m_alphabet, optimized.Alphabet);
23
21
24 return optimized;
22 return (EDFADefinition<T>)Optimize(alphabet => new EDFADefinition<T>((EnumAlphabet<T>)alphabet), m_alphabet, new EnumAlphabet<T>());
25 }
23 }
26
24
27 public void PrintDFA() {
25 public void PrintDFA() {
28 PrintDFA(m_alphabet);
26 PrintDFA(m_alphabet);
29 }
27 }
30 }
28 }
31 }
29 }
General Comments 0
You need to be logged in to leave comments. Login now