view Implab/Parsing/Scanner.cs @ 89:ce0171cacec4 v2

improved performance of a chained map operation
author cin
date Wed, 08 Oct 2014 02:19:45 +0400
parents 05e6468f066f
children 240aa6994018
line wrap: on
line source

using Implab;
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Implab.Parsing {
    /// <summary>
    /// Базовый класс для разбора потока входных символов на токены.
    /// </summary>
    /// <remarks>
    /// Сканнер имеет внутри буффер с симолами входного текста, по которому перемещаются два
    /// указателя, начала и конца токена, при перемещении искользуется ДКА для определения
    /// конца токена и допустимости текущего символа.
    /// </remarks>
    public abstract class Scanner : Disposable {
        struct ScannerConfig {
            public DFAStateDescriptior[] states;
            public int[] alphabetMap;
        }

        Stack<ScannerConfig> m_defs = new Stack<ScannerConfig>();

        DFAStateDescriptior[] m_states;
        int[] m_alphabetMap;

        protected DFAStateDescriptior m_currentState;
        int m_previewCode;

        protected int m_tokenLen = 0;
        protected int m_tokenOffset;

        protected char[] m_buffer;
        protected int m_bufferSize;
        protected int m_pointer;

        TextReader m_reader;
        bool m_disposeReader;
        int m_chunkSize = 1024; // 1k
        int m_limit = 10 * 1024 * 1024; // 10Mb

        protected Scanner(CDFADefinition definition) {
            Safe.ArgumentNotNull(definition, "definition");

            m_states = definition.States;
            m_alphabetMap = definition.Alphabet.GetTranslationMap();

            Feed(new char[0]);
        }

        /// <summary>
        /// Заполняет входными данными буффер.
        /// </summary>
        /// <param name="data">Данные для обработки.</param>
        /// <remarks>Копирование данных не происходит, переданный массив используется в
        /// качестве входного буффера.</remarks>
        public void Feed(char[] data) {
            Safe.ArgumentNotNull(data, "data");

            Feed(data, data.Length);
        }

        /// <summary>
        /// Заполняет буффур чтения входными данными.
        /// </summary>
        /// <param name="data">Данные для обработки.</param>
        /// <param name="length">Длина данных для обработки.</param>
        /// <remarks>Копирование данных не происходит, переданный массив используется в
        /// качестве входного буффера.</remarks>
        public void Feed(char[] data, int length) {
            Safe.ArgumentNotNull(data, "data");
            Safe.ArgumentInRange(length, 0, data.Length, "length");
            AssertNotDisposed();

            m_pointer = -1;
            m_buffer = data;
            m_bufferSize = length;
            Shift();
        }

        public void Feed(TextReader reader, bool dispose) {
            Safe.ArgumentNotNull(reader, "reader");
            AssertNotDisposed();

            if (m_reader != null && m_disposeReader)
                m_reader.Dispose();

            m_reader = reader;
            m_disposeReader = dispose;
            m_pointer = -1;
            m_buffer = new char[m_chunkSize];
            m_bufferSize = 0;
            Shift();
        }

        /// <summary>
        /// Получает текущий токен в виде строки.
        /// </summary>
        /// <returns></returns>
        protected string GetTokenValue() {
            return new String(m_buffer, m_tokenOffset, m_tokenLen);
        }

        /// <summary>
        /// Метки текущего токена, которые были назначены в регулярном выражении.
        /// </summary>
        protected int[] TokenTags {
            get {
                return m_currentState.tag;
            }
        }

        /// <summary>
        /// Признак конца данных
        /// </summary>
        public bool EOF {
            get {
                return m_pointer >= m_bufferSize;
            }
        }

        /// <summary>
        /// Читает следующий токен, при этом <see cref="m_tokenOffset"/> указывает на начало токена,
        /// <see cref="m_tokenLen"/> на длину токена, <see cref="m_buffer"/> - массив символов, в
        /// котором находится токен.
        /// </summary>
        /// <returns><c>false</c> - достигнут конец данных, токен не прочитан.</returns>
        protected bool ReadTokenInternal() {
            if (m_pointer >= m_bufferSize)
                return false;

            m_currentState = m_states[CDFADefinition.INITIAL_STATE];
            m_tokenLen = 0;
            m_tokenOffset = m_pointer;
            int nextState = CDFADefinition.UNREACHEBLE_STATE;
            do {
                nextState = m_currentState.transitions[m_previewCode];
                if (nextState == CDFADefinition.UNREACHEBLE_STATE) {
                    if (m_currentState.final)
                        return true;
                    else
                        throw new ParserException(
                            String.Format(
                                "Unexpected symbol '{0}', at pos {1}",
                                m_buffer[m_pointer],
                                Position
                            )
                        );
                } else {
                    m_currentState = m_states[nextState];
                    m_tokenLen++;
                }

            } while (Shift());

            // END OF DATA
            if (!m_currentState.final)
                throw new ParserException("Unexpected end of data");

            return true;
        }


        bool Shift() {
            m_pointer++;

            if (m_pointer >= m_bufferSize) {
                if (!ReadNextChunk())
                    return false;
            }

            m_previewCode = m_alphabetMap[m_buffer[m_pointer]];

            return true;
        }

        bool ReadNextChunk() {
            if (m_reader == null)
                return false;

            //  extend buffer if nesessary
            if (m_pointer + m_chunkSize > m_buffer.Length) {
                // trim unused buffer head
                var size = m_tokenLen + m_chunkSize;
                if (size >= m_limit)
                    throw new ParserException(String.Format("Input buffer {0} bytes limit exceeded", m_limit));
                var temp = new char[size];
                Array.Copy(m_buffer, m_tokenOffset, temp, 0, m_tokenLen);
                m_pointer -= m_tokenOffset;
                m_bufferSize -= m_tokenOffset;
                m_tokenOffset = 0;
                m_buffer = temp;
            }
            
            var read = m_reader.Read(m_buffer, m_tokenLen, m_chunkSize);
            if (read == 0)
                return false;

            m_bufferSize += read;

            return true;
        }

        /// <summary>
        /// Позиция сканнера во входном буфере
        /// </summary>
        public int Position {
            get {
                return m_pointer + 1;
            }
        }

        /// <summary>
        /// Преключает внутренний ДКА на указанный, позволяет реализовать подобие захватывающей
        /// группировки.
        /// </summary>
        /// <param name="states">Таблица состояний нового ДКА</param>
        /// <param name="alphabet">Таблица входных символов для нового ДКА</param>
        protected void Switch(DFAStateDescriptior[] states, int[] alphabet) {
            Safe.ArgumentNotNull(states, "dfa");

            m_defs.Push(new ScannerConfig {
                states = m_states,
                alphabetMap = m_alphabetMap
            });

            m_states = states;
            m_alphabetMap = alphabet;

            m_previewCode = m_alphabetMap[m_buffer[m_pointer]];
        }

        /// <summary>
        /// Восстанавливает предыдущей ДКА сканнера.
        /// </summary>
        protected void Restore() {
            if (m_defs.Count == 0)
                throw new InvalidOperationException();
            var prev = m_defs.Pop();
            m_states = prev.states;
            m_alphabetMap = prev.alphabetMap;
            m_previewCode = m_alphabetMap[m_buffer[m_pointer]];
        }

        protected override void Dispose(bool disposing) {
            if (disposing) {
                if (m_reader != null && m_disposeReader)
                    m_reader.Dispose();
                m_buffer = null;
                m_bufferSize = 0;
                m_pointer = 0;
                m_tokenLen = 0;
                m_tokenOffset = 0;
            }
            base.Dispose(disposing);
        }
    }
}