implab/ImplabNet Commit - r160:5802131432e4

fixed regression: race condition in Promise...

cin -

r160:5802131432e4 v2

parent child

Context file:

r160:5802131432e4

Collapse all files

Implab/AbstractEvent.cs +6 -2

             using System;
             using Implab.Parallels;
             using System.Threading;
             using System.Reflection;
             namespace Implab {
                 public abstract class AbstractEvent<THandler> : ICancellationToken, ICancellable {
                     const int UNRESOLVED_SATE = 0;
                     const int TRANSITIONAL_STATE = 1;
                     protected const int SUCCEEDED_STATE = 2;
                     protected const int REJECTED_STATE = 3;
                     protected const int CANCELLED_STATE = 4;
                     const int CANCEL_NOT_REQUESTED = 0;
                     const int CANCEL_REQUESTING = 1;
                     const int CANCEL_REQUESTED = 2;
                     const int RESERVED_HANDLERS_COUNT = 4;
                     int m_state;
                     Exception m_error;
                     int m_handlersCount;
                     //readonly THandler[] m_handlers = new THandler[RESERVED_HANDLERS_COUNT];
                     THandler[] m_handlers;
                     MTQueue<THandler> m_extraHandlers;
                     int m_handlerPointer = -1;
                     int m_handlersCommited;
                     int m_cancelRequest;
                     Exception m_cancelationReason;
                     MTQueue<Action<Exception>> m_cancelationHandlers;
                     #region state managment
                     bool BeginTransit() {
                         return UNRESOLVED_SATE == Interlocked.CompareExchange(ref m_state, TRANSITIONAL_STATE, UNRESOLVED_SATE);
                     }
                     void CompleteTransit(int state) {
                         if (TRANSITIONAL_STATE != Interlocked.CompareExchange(ref m_state, state, TRANSITIONAL_STATE))
                             throw new InvalidOperationException("Can't complete transition when the object isn't in the transitional state");
                     }
                     void WaitTransition() {
                         while (m_state == TRANSITIONAL_STATE) {
                             Thread.MemoryBarrier();
                         }
                     }
                     protected bool BeginSetResult() {
                         if (!BeginTransit()) {
                             WaitTransition();
                             if (m_state != CANCELLED_STATE)
                                 throw new InvalidOperationException("The promise is already resolved");
                             return false;
                         }
                         return true;
                     }
                     protected void EndSetResult() {
                         CompleteTransit(SUCCEEDED_STATE);
                         Signal();
                     }
                     /// <summary>
                     /// Выполняет обещание, сообщая об ошибке
                     /// </summary>
                     /// <remarks>
                     /// Поскольку обещание должно работать в многопточной среде, при его выполнении сразу несколько потоков
                     /// могу вернуть ошибку, при этом только первая будет использована в качестве результата, остальные
                     /// будут проигнорированы.
                     /// </remarks>
                     /// <param name="error">Исключение возникшее при выполнении операции</param>
                     /// <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);
                             }
                             Signal();
                         } else {
                             WaitTransition();
                             if (m_state == SUCCEEDED_STATE)
                                 throw new InvalidOperationException("The promise is already resolved");
                         }
                     }
                     /// <summary>
                     /// Отменяет операцию, если это возможно.
                     /// </summary>
                     /// <remarks>Для определения была ли операция отменена следует использовать свойство <see cref="IsCancelled"/>.</remarks>
                     protected void SetCancelled(Exception reason) {
                         if (BeginTransit()) {
                             m_error = reason;
                             CompleteTransit(CANCELLED_STATE);
                             Signal();
                         }
                     }
                     protected abstract void SignalHandler(THandler handler, int signal);
                     void Signal() {
                         var hp = m_handlerPointer;
                         var slot = hp +1 ;
                         while (slot < m_handlersCommited) {
                             if (Interlocked.CompareExchange(ref m_handlerPointer, slot, hp) == hp) {
                                 SignalHandler(m_handlers[slot], m_state);
                             }
                             hp = m_handlerPointer;
                             slot = hp +1 ;
                         }
                         if (m_extraHandlers != null) {
                             THandler handler;
                             while (m_extraHandlers.TryDequeue(out handler))
                                 SignalHandler(handler, m_state);
                         }
                     }
                     #endregion
                     protected abstract Signal GetResolveSignal();
                     #region synchronization traits
                     protected void WaitResult(int timeout) {
                         if (!(IsResolved || GetResolveSignal().Wait(timeout)))
                             throw new TimeoutException();
                         switch (m_state) {
                             case SUCCEEDED_STATE:
                                 return;
                             case CANCELLED_STATE:
                                 throw new OperationCanceledException();
                             case REJECTED_STATE:
                                 throw new TargetInvocationException(m_error);
                             default:
                                 throw new ApplicationException(String.Format("Invalid promise state {0}", m_state));
                         }
                     }
                     #endregion
                     #region handlers managment
                     protected void AddHandler(THandler handler) {
                         if (m_state > 1) {
                             // the promise is in the resolved state, just invoke the handler
                             SignalHandler(handler, m_state);
                         } else {
                             var slot = Interlocked.Increment(ref m_handlersCount) - 1;
                             if (slot < RESERVED_HANDLERS_COUNT) {
-                                if (slot == 0)
+                                if (slot == 0) {
-                                    Interlocked.CompareExchange(ref m_handlers, new THandler[RESERVED_HANDLERS_COUNT], null);
+                                    m_handlers = new THandler[RESERVED_HANDLERS_COUNT];
+                                } else {
+                                    while (m_handlers == null)
+                                        Thread.MemoryBarrier();
+                                }
                                 m_handlers[slot] = handler;
                                 while (slot != Interlocked.CompareExchange(ref m_handlersCommited, slot + 1, slot)) {
                                 }
                                 if (m_state > 1) {
                                     do {
                                         var hp = m_handlerPointer;
                                         slot = hp + 1;
                                         if (slot < m_handlersCommited) {
                                             if (Interlocked.CompareExchange(ref m_handlerPointer, slot, hp) != hp)
                                                 continue;
                                             SignalHandler(m_handlers[slot], m_state);
                                         }
                                         break;
                                     } while(true);
                                 }
                             } else {
                                 if (slot == RESERVED_HANDLERS_COUNT) {
                                     m_extraHandlers = new MTQueue<THandler>();
                                 } else {
                                     while (m_extraHandlers == null)
                                         Thread.MemoryBarrier();
                                 }
                                 m_extraHandlers.Enqueue(handler);
                                 if (m_state > 1 && m_extraHandlers.TryDequeue(out handler))
                                 // if the promise have been resolved while we was adding the handler to the queue
                                 // we can't guarantee that someone is still processing it
                                 // therefore we need to fetch a handler from the queue and execute it
                                 // note that fetched handler may be not the one that we have added
                                 // even we can fetch no handlers at all :)
                                     SignalHandler(handler, m_state);
                             }
                         }
                     }
                     #endregion
                     #region IPromise implementation
                     public bool IsResolved {
                         get {
                             Thread.MemoryBarrier();
                             return m_state > 1;
                         }
                     }
                     public bool IsCancelled {
                         get {
                             Thread.MemoryBarrier();
                             return m_state == CANCELLED_STATE;
                         }
                     }
                     #endregion
                     public Exception Error {
                         get {
                             return m_error;
                         }
                     }
                     public bool CancelOperationIfRequested() {
                         if (IsCancellationRequested) {
                             CancelOperation(CancellationReason);
                             return true;
                         }
                         return false;
                     }
                     public virtual void CancelOperation(Exception reason) {
                         SetCancelled(reason);
                     }
                     public void CancellationRequested(Action<Exception> handler) {
                         Safe.ArgumentNotNull(handler, "handler");
                         if (IsCancellationRequested)
                             handler(CancellationReason);
                         if (m_cancelationHandlers == null)
                             Interlocked.CompareExchange(ref m_cancelationHandlers, new MTQueue<Action<Exception>>(), null);
                         m_cancelationHandlers.Enqueue(handler);
                         if (IsCancellationRequested && m_cancelationHandlers.TryDequeue(out handler))
                             // TryDeque implies MemoryBarrier()
                             handler(m_cancelationReason);
                     }
                     public bool IsCancellationRequested {
                         get {
                             do {
                                 if (m_cancelRequest == CANCEL_NOT_REQUESTED)
                                     return false;
                                 if (m_cancelRequest == CANCEL_REQUESTED)
                                     return true;
                                 Thread.MemoryBarrier();
                             } while(true);
                         }
                     }
                     public Exception CancellationReason {
                         get {
                             do {
                                 Thread.MemoryBarrier();
                             } while(m_cancelRequest == CANCEL_REQUESTING);
                             return m_cancelationReason;
                         }
                     }
                     #region ICancellable implementation
                     public void Cancel() {
                         Cancel(null);
                     }
                     public void Cancel(Exception reason) {
                         if (CANCEL_NOT_REQUESTED == Interlocked.CompareExchange(ref m_cancelRequest, CANCEL_REQUESTING, CANCEL_NOT_REQUESTED)) {
                             m_cancelationReason = reason;
                             m_cancelRequest = CANCEL_REQUESTED;
                             if (m_cancelationHandlers != null) {
                                 Action<Exception> handler;
                                 while (m_cancelationHandlers.TryDequeue(out handler))
                                     handler(m_cancelationReason);
                             }
                         }
                     }
                     #endregion
                 }
             }

Implab/Parsing/CDFADefinition.cs +2 -4

             namespace Implab.Parsing {
                 public class CDFADefinition : DFADefinition {
                     readonly CharAlphabet m_alphabet;
                     public CharAlphabet Alphabet {
                         get { return m_alphabet; }
                     }
                     public CDFADefinition(CharAlphabet alphabet): base(alphabet.Count) {
                         m_alphabet = alphabet;
                     }
                     public CDFADefinition Optimize() {
-                        var optimized = new CDFADefinition(new CharAlphabet());
+                        return (CDFADefinition)Optimize(alphabet => new CDFADefinition((CharAlphabet)alphabet), m_alphabet, new CharAlphabet());
-                        Optimize(optimized, m_alphabet, optimized.Alphabet);
-                        return optimized;
                     }
                     public void PrintDFA() {
                         PrintDFA(m_alphabet);
                     }
                 }
             }

Implab/Parsing/DFADefinition.cs +5 -2

             using Implab;
             using System;
             using System.Collections.Generic;
             using System.Diagnostics;
             using System.Linq;
             namespace Implab.Parsing {
                 public class DFADefinition : IDFADefinition {
                     readonly List<DFAStateDescriptior> m_states;
                     public const int INITIAL_STATE = 1;
                     public const int UNREACHEBLE_STATE = 0;
                     DFAStateDescriptior[] m_statesArray;
                     readonly int m_alpabetSize;
                     public DFADefinition(int alphabetSize) {
                         m_states = new List<DFAStateDescriptior>();
                         m_alpabetSize = alphabetSize;
                         m_states.Add(new DFAStateDescriptior());
                     }
                     public DFAStateDescriptior[] States {
                         get {
                             if (m_statesArray == null)
                                 m_statesArray = m_states.ToArray();
                             return m_statesArray;
                         }
                     }
                     public bool InitialStateIsFinal {
                         get {
                             return m_states[INITIAL_STATE].final;
                         }
                     }
                     public int AddState() {
                         var index = m_states.Count;
                         m_states.Add(new DFAStateDescriptior {
                             final = false,
                             transitions = new int[AlphabetSize]
                         });
                         m_statesArray = null;
                         return index;
                     }
                     public int AddState(int[] tag) {
                         var index = m_states.Count;
                         bool final = tag != null && tag.Length != 0;
                         m_states.Add(new DFAStateDescriptior {
                             final = final,
                             transitions = new int[AlphabetSize],
                             tag = final ? tag : null
                         });
                         m_statesArray = null;
                         return index;
                     }
                     public void DefineTransition(int s1,int s2, int symbol) {
                         Safe.ArgumentInRange(s1, 0, m_states.Count-1, "s1");
                         Safe.ArgumentInRange(s2, 0, m_states.Count-1, "s2");
                         Safe.ArgumentInRange(symbol, 0, AlphabetSize-1, "symbol");
                         m_states[s1].transitions[symbol] = s2;
                     }
-                    public void Optimize<TA>(IDFADefinition minimalDFA,IAlphabet<TA> sourceAlphabet, IAlphabet<TA> minimalAlphabet) {
+                    protected IDFADefinition Optimize<TA>(Func<IAlphabet<TA>, IDFADefinition> dfaFactory,IAlphabet<TA> sourceAlphabet, IAlphabet<TA> minimalAlphabet) {
-                        Safe.ArgumentNotNull(minimalDFA, "minimalDFA");
+                        Safe.ArgumentNotNull(dfaFactory, "dfaFactory");
                         Safe.ArgumentNotNull(minimalAlphabet, "minimalAlphabet");
                         var setComparer = new CustomEqualityComparer<HashSet<int>>(
                             (x, y) => x.SetEquals(y),
                             (s) => s.Sum(x => x.GetHashCode())
                         );
                         var arrayComparer = new CustomEqualityComparer<int[]>(
                             (x,y) => (new HashSet<int>(x)).SetEquals(new HashSet<int>(y)),
                             (a) => a.Sum(x => x.GetHashCode())
                         );
                         var optimalStates = new HashSet<HashSet<int>>(setComparer);
                         var queue = new HashSet<HashSet<int>>(setComparer);
                         foreach (var g in Enumerable
                             .Range(INITIAL_STATE, m_states.Count-1)
                             .Select(i => new {
                                 index = i,
                                 descriptor = m_states[i]
                             })
                             .Where(x => x.descriptor.final)
                             .GroupBy(x => x.descriptor.tag, arrayComparer)
                         ) {
                             optimalStates.Add(new HashSet<int>(g.Select(x => x.index)));
                         }
                         var state = new HashSet<int>(
                             Enumerable
                                 .Range(INITIAL_STATE, m_states.Count - 1)
                                 .Where(i => !m_states[i].final)
                         );
                         optimalStates.Add(state);
                         queue.Add(state);
                         while (queue.Count > 0) {
                             var stateA = queue.First();
                             queue.Remove(stateA);
                             for (int c = 0; c < AlphabetSize; c++) {
                                 var stateX = new HashSet<int>();
                                 for(int s = 1; s < m_states.Count; s++) {
                                     if (stateA.Contains(m_states[s].transitions[c]))
                                         stateX.Add(s);
                                 }
                                 foreach (var stateY in optimalStates.ToArray()) {
                                     if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
                                         var stateR1 = new HashSet<int>(stateY);
                                         var stateR2 = new HashSet<int>(stateY);
                                         stateR1.IntersectWith(stateX);
                                         stateR2.ExceptWith(stateX);
                                         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);
                                         }
                                     }
                                 }
                             }
                         }
                         // строим карты соотвествия оптимальных состояний с оригинальными
                         var initialState = optimalStates.Single(x => x.Contains(INITIAL_STATE));
                         // карта получения оптимального состояния по соотвествующему ему простому состоянию
                         int[] reveseOptimalMap = new int[m_states.Count];
                         // карта с индексами оптимальных состояний
                         HashSet<int>[] optimalMap = new HashSet<int>[optimalStates.Count + 1];
                         {
                             optimalMap[0] = new HashSet<int>(); // unreachable state
                             optimalMap[1] = initialState; // initial state
                             foreach (var ss in initialState)
                                 reveseOptimalMap[ss] = 1;
                             int i = 2;
                             foreach (var s in optimalStates) {
                                 if (s.SetEquals(initialState))
                                     continue;
                                 optimalMap[i] = s;
                                 foreach (var ss in s)
                                     reveseOptimalMap[ss] = i;
                                 i++;
                             }
                         }
                         // получаем минимальный алфавит
                         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 = 1 ; s < optimalMap.Length; 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 = reveseOptimalMap[
                                                  optimalMap[s].Select(x => m_states[x].transitions[term]).FirstOrDefault(x => x != 0) // первое допустимое элементарное состояние, если есть
                                              ];
                                     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);
                         var alphabetMap = sourceAlphabet.Reclassify(minimalAlphabet, minClasses);
                         // построение автомата
+                        var minimalDFA = dfaFactory(minimalAlphabet);
                         var states = new int[ optimalMap.Length ];
                         states[0] = UNREACHEBLE_STATE;
                         for(var s = INITIAL_STATE; s < states.Length; s++) {
                             var tags = optimalMap[s].SelectMany(x => m_states[x].tag ?? Enumerable.Empty<int>()).Distinct().ToArray();
                             if (tags.Length > 0)
                                 states[s] = minimalDFA.AddState(tags);
                             else
                                 states[s] = minimalDFA.AddState();
                         }
                         Debug.Assert(states[INITIAL_STATE] == INITIAL_STATE);
                         for (int s1 = 1; s1 < m_states.Count;  s1++) {
                             for (int c = 0; c < AlphabetSize; c++) {
                                 var s2 = m_states[s1].transitions[c];
                                 if (s2 != UNREACHEBLE_STATE) {
                                     minimalDFA.DefineTransition(
                                         reveseOptimalMap[s1],
                                         reveseOptimalMap[s2],
                                         alphabetMap[c]
                                     );
                                 }
                             }
                         }
+                        return minimalDFA;
                     }
                     public void PrintDFA<TA>(IAlphabet<TA> alphabet) {
                         var reverseMap = alphabet.CreateReverseMap();
                         for (int i = 1; i < reverseMap.Length; i++) {
                             Console.WriteLine("C{0}: {1}", i, String.Join(",", reverseMap[i]));
                         }
                         for (int i = 1; i < m_states.Count; i++) {
                             var s = m_states[i];
                             for (int c = 0; c < AlphabetSize; c++)
                                 if (s.transitions[c] != UNREACHEBLE_STATE)
                                     Console.WriteLine("S{0} -{1}-> S{2}{3}", i, String.Join(",", reverseMap[c]), s.transitions[c], m_states[s.transitions[c]].final ? "$" : "");
                         }
                     }
                     public int AlphabetSize {
                         get {
                             return m_alpabetSize;
                         }
                     }
                 }
             }

Implab/Parsing/EDFADefinition.cs +2 -4

             using Implab;
             using System;
             namespace Implab.Parsing {
                 public class EDFADefinition<T> : DFADefinition where T : struct, IConvertible {
                     readonly EnumAlphabet<T> m_alphabet;
                     public EnumAlphabet<T> Alphabet {
                         get { return m_alphabet; }
                     }
                     public EDFADefinition(EnumAlphabet<T> alphabet) : base(alphabet.Count) {
                         m_alphabet = alphabet;
                     }
                     public void DefineTransition(int s1, int s2, T input) {
                         DefineTransition(s1, s2, m_alphabet.Translate(input));
                     }
                     public EDFADefinition<T> Optimize() {
-                        var optimized = new EDFADefinition<T>(new EnumAlphabet<T>());
-                        Optimize(optimized, m_alphabet, optimized.Alphabet);
+                        return (EDFADefinition<T>)Optimize(alphabet => new EDFADefinition<T>((EnumAlphabet<T>)alphabet), m_alphabet, new EnumAlphabet<T>());
-                        return optimized;
                     }
                     public void PrintDFA() {
                         PrintDFA(m_alphabet);
                     }
                 }
             }

General Comments 0

Write
Preview

You need to be logged in to leave comments. Login now

No TODOs yet

	Site-wide shortcuts
/	Use quick search box
g h	Goto home page
g g	Goto my private gists page
g G	Goto my public gists page
g 0-9	Goto bookmarked items from 0-9
n r	New repository page
n g	New gist page

	Repositories
g s	Goto summary page
g c	Goto changelog page
g f	Goto files page
g F	Goto files page with file search activated
g p	Goto pull requests page
g o	Goto repository settings
g O	Goto repository access permissions settings
t s	Toggle sidebar on some pages