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