Análisis de Programas de Procesamiento de Eventos Complejos

ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA INFORMÁTICA GRADO EN INGENIERÍA DEL SOFTWARE Análisis de Programas de Procesamiento de Eventos Complejos Analysis of Complex Event Processing Programs Realizado por Adrián García López Tutorizado por Antonio Vallecillo Moreno Lola Burgueño Caballero Departamento Lenguajes y Ciencias de la Computación UNIVERSIDAD DE MÁLAGA MÁLAGA, JUNIO DE 2018 Fecha defensa: El Secretario del Tribunal ii iii Resumen El procesamiento de eventos complejos (CEP, por sus siglas en inglés: Complex Event Processing), está ganando aceptación en los entornos distribuidos de tiempo real, al proporcionar una forma rápida y eficiente de correlacionar e inferir conclusiones sobre eventos que ocurren en tiempo real. Esta tecnología tiene un amplio campo de aplicación como pueden ser el Internet de las Cosas (IoT), monitorización de sistemas o alerta de situaciones de riesgo en infraestructuras sanitarias, entre otras. La característica más importante de estos tipos de programas, es la capacidad de expresar patrones de sucesos sobre los eventos, mediante la definición de reglas. La especificación de estos tipos de patrones se realiza utilizando lenguajes de procesamiento de eventos como Esper, el cual ha sido utilizado en este proyecto. Es muy importante la correcta especificación de estos patrones ya que de ellos depende el correcto funcionamiento del sistema. Con tal fin, se ha desarrollado una herramienta capaz de analizar dos propiedades que pueden comprobarse estáticamente en las especificación de los programas CEP basados en reglas: la aciclicidad de las dependencias entre reglas y las condiciones de carrera entre reglas. Ambas características tienen que lidiar con el carácter no determinista de los sistemas basados en reglas. Para el desarrollo de esta herramienta se ha utilizado un enfoque MDSE (Model-Driven Software Engineering). Más concretamente, se ha desarrollado un plug-in capaz de reconocer el lenguaje Esper y obtener como salida una representación en forma de grafo dirigido para la visualización de los resultados del análisis. Palabras clave: Procesamiento de Eventos Complejos, Esper, Ingeniería de Software Dirigida por Modelos, Xtext, Análisis Estático. iv Abstract Complex Event Processing (CEP) is having a good acceptance in distributed real-time environments since it provides a quick and efficient way to correlate and infer conclusions about events that happen in real time. This technology can be used in several areas such as Internet of Things (IoT), systems monitoring or critical situation detection in clinical environment, among others. The most important characteristic of this kind of programs is the ability to express occurrences patterns over events, by defining rules. The specification of these types of patterns is carried out by using event processing languages such as Esper. The correct specification of these patterrns is crucial because the correct behavior of the system depends on them. To this end, we have developed a tool capable of analyzing two properties that it can be checked through the static analysis of rule-based CEP programs: pattern acyclicity and pattern race conditions. They both have to deal with the non-deterministic nature of rule-based systems. For the development of this tool, a Model-Driven Software Engineering approach has been used. In particular, we have developed a plug-in capable of recognizing Esper language and obtain as output a directed graph representation for visualizing the result of the analysis. Key words: Complex Event Processing, Esper, Model-Driven Software Engineering, Xtext, Static Analysis. Índice general 1. Introducción 1 1.1. Objetivos .................................... 1 1.2. Motivación .................................... 2 1.3. Tareas a desarrollar ............................... 3 1.4. Metodología y fases de trabajo ......................... 3 1.4.1. Metodología ............................... 3 1.4.2. Fases de trabajo ............................. 4 1.5. Estructura de la memoria ........................... 5 2. Estado del arte 7 2.1. Ingeniería del Software Dirigida por Modelos ................. 7 2.1.1. Introducción ............................... 7 2.1.2. Principios Básicos ............................ 9 2.1.3. Lenguajes Específicos de Dominio (DSLs) .............. 10 2.2. Procesamiento de Eventos Complejos ..................... 11 2.2.1. Information Flow Processing (IFP) domain .............. 11 2.2.2. Sistemas de Procesamiento de Eventos Complejos .......... 13 2.2.3. Análisis estático de programas CEP .................. 14 2.3. Esper ....................................... 15 3. Tecnologías utilizadas 21 3.1. Java ....................................... 21 3.1.1. Librerías y framework utilizados .................... 21 3.2. Xtend ...................................... 22 3.3. Xtext ....................................... 23 3.3.1. Estructura de un proyecto Xtext ................... 23 3.3.2. Ejemplo de uso ............................. 24 3.3.3. Editor de texto ............................. 26 3.3.4. Generación de código .......................... 26 3.4. ANTLRWorks .................................. 28 3.5. GEF (Graphical Editing Framework) ..................... 28 v vi ÍNDICE GENERAL 3.6. Graphviz ..................................... 29 3.6.1. DOT ................................... 29 4. Estructura de la herramienta 31 4.1. Entorno ..................................... 31 4.2. Definición de la gramática ........................... 32 4.2.1. El problema de la gramática ambigua ................. 37 4.3. Generación de código .............................. 38 4.3.1. Algoritmos utilizados .......................... 40 5. Validación y pruebas 45 5.1. Depuración de la gramática .......................... 45 5.2. Pruebas de regresión .............................. 47 6. Conclusiones 51 6.1. Desarrollo de la herramienta .......................... 51 6.2. Líneas futuras de ampliación .......................... 52 A. Manual de instalación 53 A.1. Eclipse ...................................... 53 A.2. Xtext ....................................... 53 A.3. GEF (Graphical Editing Framework) ..................... 54 A.4. Graphviz ..................................... 55 B. Manual de usuario 57 C. Definición de la gramática utilizada en el lexer 61 D. Conjuntos de reglas utilizados 65 D.1. Smart House ................................... 65 D.2. MotorBike .................................... 66 D.3. Nuclear power station ............................. 67 D.4. Air Quality ................................... 68 Capítulo 1 Introducción Este capítulo servirá para contextualizar el entorno de la herramienta desarrollada, mostrando pues, su motivación, objetivos del desarrollo y, por último, se verá la estructura del presente documento. 1.1. Objetivos El objetivo fundamental del proyecto es la realización de una herramienta capaz de analizar propiedades en la especificación de los programas de Procesamiento de Eventos Complejos [Cugola and Margara, 2012], [Etzion and Niblett, 2010] basados en reglas. La herramienta se basa en un Analizador Sintáctico [Dick and Ceriel, 1990] (también conocido como parser) capaz de reconocer estas reglas y, posteriormente, generar conclusiones sobre ellas. Esta memoria describe la herramienta que hemos realizado como parte del Trabajo Fin de Grado, y que permite realizar diversos tipos de análisis estáticos sobre programas de Procesamiento de Eventos Complejos (CEP por sus siglas en inglés, Complex Event Processing). La herramienta se ha desarrollado siguiendo las técnicas de Desarrollo de Software Dirigido por Modelos [García et al., 2013,Brambilla et al., 2017] (DSDM por sus siglas) por la versatilidad que ofrece para el desarrollo de este tipo de aplicaciones. En cuanto a su funcionalidad, la herramienta es capaz de detectar ciclos en la especificación de un conjunto de reglas y alertar sobre éstos. En el caso de que no se detecten ciclos, se podrá hacer una comprobación de las prioridades asignadas a las reglas y generar el mismo conjunto de reglas con las prioridades atendiendo su orden topológico. Finalmente, al tratarse de un Trabajo Fin de Grado, los objetivos que se pretendían con este trabajo también incluyen los de conocer y familiarizarse con diversos conceptos y técnicas que no se han visto en el grado, así como poner en práctica las enseñanzas recibi1 8CAPÍTULO 2. ESTADO DEL ARTE guajes de programación. Con esto conseguimos poder razonar sobre el sistema dejando de lado detalles de implementación y, a su vez, conseguir un alto nivel de automatización al poder generar partes del sistema aplicando transformaciones sobre los modelos que lo componen. Todo lo dicho anteriormente sería los objetivos fundamentales de este paradigma para combatir el principal problema del desarrollo software, su complejidad [García et al., 2013,Vallecillo, 2018]. Actualmente nos encontramos en un momento donde la Ingeniería del Software Dirigida por Modelos se encuentra a caballo entre su adopción en la industria y su validación como paradigma de desarrollo software a través de estudios que evalúen su comportamiento frente a los métodos de desarrollo software tradicionales. Para llevar a cabo una adopción total de este paradigma en la industria, podemos ver los diferentes puntos que el autor Bran Selic nos muestra en su artículo “Manifestaciones sobre MDA” [Selic, 2008]: 1. Completar los estudios teórico y desarrollar herramientas que sean robustas y usables. 2. Hacer ver a las empresas los beneficios de la implantación de este paradigma en sus desarrollos. 3. Disponer de personal cualificado que entienda el paradigma MDSE. Para esto hay que actuar en tres ámbitos: la investigación y desarrollo de nuevas herramientas, la enseñanza de este paradigma en las universidades y la realización y transferencia de proyectos que permitan transmitir la información obtenida en las empresas. La Ingeniería de Software Dirigida por Modelos tuvo su gran auge con el nacimiento de UML (Unified Modeling Language) [OMG, 2018], una notación que nos permite especificar, visualizar y documentar los diferentes modelos de un sistema software. El problema residía en la utilización de UML para documentar al final del desarrollo, lo cual no es una acción errónea, pero haciendo esto, no se estaba sacando el máximo provecho de los modelos [García et al., 2013]. En el artículo de Grady Booch “Growing the UML” [Booch, 2002], podemos encontrar los 4 pilares fundamentales sobre el potencial de los modelos: 1. Documentar el proceso de desarrollo software. 2. Razonar sobre el propio sistema. 3. Comunicar ideas y fomentar la discusión sobre los diferentes aspectos del sistema. 4. Generar partes del sistema transformando estos modelos. La MDSE nace para facilitar la automatización del desarrollo de software en la industria pero todavía queda un largo camino hasta que su adopción sea completa. Por 2.1. INGENIERÍA DEL SOFTWARE DIRIGIDA POR MODELOS 9 un lado, hacen falta más estudios sobre la forma de enseñar este nuevo paradigma en las aulas. En el artículo de Jordi Cabot y Dimitris Kolovos “Human factors in the adoption of model-driven engineering: an educator’s perspective” [Cabot and Kolovos, 2016] podemos encontrar un análisis sobre los problemas encontrados en la enseñanza de este paradigma a estudiantes. Por otro lado, hacen falta integrar herramientas MDE en el ámbito específico de compañías para hacer ver el potencial la Ingeniería de Software Dirigida por Modelos. No obstante, estamos ante el paradigma de desarrollo de software que se asentará y será utilizado en el futuro. 2.1.2. Principios Básicos La Ingeniería de Software Dirigida por Modelos no es solo un paradigma de desarrollo de software, sino que se compone de tres grandes subconjuntos los cuales podríamos definir como “subparadigmas” enfocados en un ámbito concreto [García et al., 2013]. Figura 2.1: Paradigmas en los que se divida MDE y los cuales están relacionados con el proyecto. En la Figura 2.1 podemos observar los “subparadigmas” de interés para este proyecto. MDD (por sus siglas en inglés Model-Driven Development ) utiliza los modelos para la generación directa de artefactos [Brambilla et al., 2017]. Normalmente el resultado es fruto de la generación automática desde un modelo. Cabe destacar que existen dos “subparadigmas” más dentro de MDE (MDR y Models@runtime), los cuales, simplemente, se mencionan ya que se salen del conocimiento de este proyecto. Aunque el objetivo de estos “subparadigmas” derivados de la Ingeniería Basada en Modelos (MDE) estén claramente diferenciados, todos ellos tienen los mismo principios fundamentales [García et al., 2013]: 1. Un modelo representa total o parcialmente una característica de un sistema software. 2. Estos modelos se representan con Lenguajes Específicos de Dominio (DSL). 10 CAPÍTULO 2. ESTADO DEL ARTE 3. Un DSL es representado a través de un metamodelo 4. Normalmente, la automatización se consigue realizando transformaciones desde los modelos a código. Este proyecto reside en el ámbito de MDD ya que la el fin principal es la realización de una herramienta (aplicación). Más concretamente en el Desarrollo Específico del Dominio (DSM por sus siglas en inglés, Domain-Specific Modeling), el cual se basa en el desarrollo de DSL para intentar salvar la complejidad de un dominio específico y poder programar cercano a él. En la siguiente sección se entrará en más detalle en el campo de los Lenguajes Específicos de Dominio. 2.1.3. Lenguajes Específicos de Dominio (DSLs) Los Lenguajes Específicos de Dominio, a diferencia de los lenguajes de programación de propósito general, están desarrollados con el fin de resolver problemas y crear construcciones específicas sobre un determinado dominio. Este dominio puede ser técnico (desarrollo de un DSL para cierto framework, por ejemplo) o no (área de negocio). En cualquier caso, utilizando DSL conseguimos una mayor productividad y calidad al abstraer detalles que son específicos de un lenguaje de programación (o framework) o de áreas de negocio [García et al., 2013]. En la Figura 2.2 podemos ver las diferentes parets de un DSL y como se relacionan entre ellas: Sintaxis abstracta: define la estructura lógica, qué expresiones son correctas utilizando los conceptos del lenguaje. En pocas palabras, nos dice cuándo un modelo está bien formado. La sintaxis abstracta se define mediante un metamodelo, que no es más que el modelo de la propia sintaxis abstracta de un DSL. Sintaxis concreta: dota al DSL de notación y aspectos de visualización. Podemos diferenciar dos tipos de sintaxis concreta: textual, las cuales son más expresivas y normalmente suelen estar basadas en gramáticas (este es el caso de Xtext, herramienta centrada en el desarrollo de DSL textuales. Más adelante se entrará en detalles sobre esta herramienta) y gráficos, centrados en en la representación del DSL mediante diagramas. Un mismo DSL puede tener varias representaciones (sintaxis concreta), la separación de los tipos de sintaxis (abstracta y concreta) es una característica fundamental en la Ingeniería de Software Dirigida por Modelos. Este proyecto combina aspectos de los dos tipos de sintaxis concreta de DSL, por un lado la parte de la definición de la gramática y por otro lado la visualización gráfica del DSL. 2.2. PROCESAMIENTO DE EVENTOS COMPLEJOS 11 Semántica: define la utilidad del DLS, es decir, la transformación de los conceptos recogidos en el DSL a conceptos cuya semántica ya es conocida. Figura 2.2: Esquema de la estructura de un DSL basado en [García et al., 2013] Un ejemplo de Lenguajes Específicos de Dominio sería SQL [Microsoft, 2018], que no es más que un DSL para la gestión y manipulación de bases de datos, abstrayendo todos los detalles de bajo nivel. Otros ejemplos serían CSS (Cascading Style Sheets) [Mozilla, 2018] para dotar de estilo a las páginas webs y el propio lenguaje DOT [Graphviz, 2018b] utilizado en este proyecto para la representación de grafos (más detalles en el Capítulo 3). Para concluir este apartado hay que notar que la utilización de de los DSL nos permite un aumento de la abstracción, pero esta abstracción tiene que ser seguida por un aumento de la automatización para que el uso de los DSLs sea efectivo. Esto se consigue gracias a la semántica dotada al DSL que en la mayoría de los casos son transformaciones de modelo a texto (o código) (M2T) y de modelo a modelo (M2M). 2.2. Procesamiento de Eventos Complejos 2.2.1. Information Flow Processing (IFP) domain La forma de tratar los datos en los sistemas actuales está cambiando. Clásicamente, nos encontrábamos con sistemas en los que la información tenía que ser previamente persistida para luego ser tratada, hablamos de los Data Base Management Systems (DBMS). Estos sistemas se caracterizan por la poca tasa de actualización de los sistemas, es decir, el procesado de lo datos (una vez persistidos) se limita ha hacerse bajo demanda del usuario. 12 CAPÍTULO 2. ESTADO DEL ARTE Cuando el usuario realiza una consulta a un DBMS (por ejemplo, una aplicación web cuyo sistema de persistencia es una base de datos relacional), esta consulta produce una respuesta que es devuelta al usuario. Podemos resumir que para cada consulta se produce un único tratamiento de los datos y el resultado es devuelto a las capas exteriores del sistema. Hoy en día, debido a la evolución de los sistemas que necesitan nutrirse de información de una manera continua (inferir conclusiones sobre una gran cantidad de datos entrantes, alerta de situaciones críticas en el sistema, supervisión de sistemas, etc) nacen los sistemas IFP. Estos sistemas permiten el procesado continuo de datos procedentes de diversas fuentes externas al sistema. Una característica esencial de estos sistemas es la posibilidad de procesas flujos de datos sin tener la necesidad de hacer una persistencia previa de ellos. No obstante, podemos encontrar sistemas en los que sí se realicen persistencia de los datos. Para tal cometido, las arquitecturas de estos sistemas, así como sus mecanismos de procesado y sus modelos datos difieren de los tradicionales DBMS [Cugola and Margara, 2012]. El objetivo de estos sistemas es la realización de una serie de tratamientos o transformaciones de los datos para obtener conclusiones tan pronto como los datos entran en el sistema. Actualmente nos encontramos con dos tipos de sistemas IFP que son los predominantes en la industria: los sistemas de Data Stream Processing y los sistemas de Procesamiento de Eventos Complejos (CEP). Los sistemas de Data Stream Processing nacen a raíz de una evolución de los sistemas tradicionales DBMS para dar pie a los DSMS (por sus siglas en inglés Data Stream Management Systems). Se basan en la transformación de flujos de datos que provienen desde fuera del sistema, para producir nuevo flujos de datos que serán tratados nuevamente (dentro del sistema) o enviados fuera de sistema. La diferencia más sustancial con los DBMS es que cuando éstos para cada consulta producen una respuesta, los DSMS mantienen un conjunto de consultas (o transformaciones) que son aplicadas a cada dato que entra en el sistema, con independencia de si son persistidos o no posteriormente. Por su parte, el Procesamiento de Eventos Complejos se basa en el tratamiento de los datos como notificaciones de eventos que se introducen en el sistema o se producen dentro del mismo. Tiene sus orígenes en el modelo Publicador-Suscriptor [Eugster et al., 2003] salvando la diferencia de que en el modelo Publicador-Suscriptor, los eventos son considerados aislados unos de otros (se tratan individualmente) y en los sistemas CEP podemos inferir conclusiones cuando un determinado patrón de eventos ocurre en el sistema. 2.2. PROCESAMIENTO DE EVENTOS COMPLEJOS 13 2.2.2. Sistemas de Procesamiento de Eventos Complejos Los sistemas CEP tratan los datos como notificaciones de eventos. Para saber a qué nos referimos con el concepto de evento podemos irnos a la definición que se da en [Etzion and Niblett, 2010]: “Un evento es una ocurrencia dentro de un sistema o dominio particular; es algo que ha sucedido, o se contempla como ocurrido en ese dominio. La palabra evento también se utiliza para definir una entidad de programación que representa la ocurrencia de tal suceso en un sistema informático”. En los sistemas CEP utilizamos la segunda definición de evento, una representación informática de una ocurrencia. Necesitamos tal definición porque, como se ha comentado con anterioridad, la principal característica de CEP es la habilidad de poder reaccionar cuando una serie de eventos concretos ocurra en el sistema, y para ello, necesitamos tal representación informática para poder tratarlo. En los sistemas CEP podemos definir dos tipos de eventos: Eventos simples: normalmente estos eventos son generados mediante los productores de eventos. Éstos pueden ser: un sensor (por ejemplo de temperatura), un proceso de negocio (por ejemplo, un proceso de reserva de habitaciones de un hotel que al final del mismo emite un evento de habitación reservada), un sistema (el cual detecta una sobrecarga de tráfico en la red y lo notifica mediante el envío de un evento), etc. Los diferentes productores enviaran los eventos generados a un sistema de procesado (en este caso un motor de Procesamiento de Eventos Complejos) para su tratamiento. Eventos complejos: en un sistema CEP, para poder reaccionar a determinados patrones de eventos, tenemos que definir reglas que expresen ese patrón. Por ejemplo: si tenemos un sistema que recibe eventos de temperatura y nuestro motor tiene una regla que, cuando recibe una evento de temperatura cuya temperatura es mayor que 80º, produce un evento de encendido de los rociadores de agua, el evento resultante de ejecutar esta regla sería considerado como un evento complejo. Los eventos complejos pueden ser enviados directamente a los consumidores de eventos, que no son más que sistemas que reciben estos eventos complejos y realizan una cierta acción en consecuencia. Pueden ser desde sistemas de persistencia, actuadores o otros procesos de negocio. También, estos eventos complejos pueden ser consumidos nuevamente por otras reglas del motor de procesamiento CEP, si hay alguna regla que requiera de la presencia de algún otro evento complejo para ser ejecutada. Las reglas mencionadas anteriormente son especificadas a través de lenguajes de Procesamientos de Eventos y tienen una estructura en común en la mayoría de los sistmas CEP [Moreno et al., 2018]: 14 CAPÍTULO 2. ESTADO DEL ARTE Fase de selección: en esta fase se analiza cuáles son los eventos, tanto simple como complejos, que hacen que la regla se ejecute. Para la única regla existente en el ejemplo anterior del sensor de temperatura, en esta fase tendríamos que la regla solo se ejecutaría con eventos de tipo temperatura. En resumen, para cada regla tendremos, tras esta fase, lo que denominaremos el conjunto de dependencias, ya que en él estarán todos los eventos de los que depende la ejecución de la misma. Fase de emparejamiento: teniendo en cuanta los eventos de la fase de selección, tenemos que ver si todos ellos cumplen los requisitos para la ejecución. Volviendo al ejemplo anterior, la regla solo se ejecutaría si el evento de tipo temperatura contiene una temperatura mayor a 80º. Este es un ejemplo muy simple, pero en escenarios más complejos se podría combinar los eventos de la fase de selección con operadores lógicos (and,or,->, etc.). Fase de producción: en esta fase se definen qué tipo de datos, extraídos de los atributos de los eventos de la fase de selección, se van a producir en forma de evento en el caso de que la regla se ejecute. En el ejemplo anterior, cuando enviamos el evento de encendido de los rociadores, podríamos enviar como atributos un identificador del sensor que ha producido la alerta, para que el consumidor sepa dónde se ha producido la alerta. Figura 2.3: Grafo dirigido de las dependencias entre reglas extraído de [Moreno et al., 2018] 2.2.3. Análisis estático de programas CEP Los programas CEP son programas basados en reglas para poder inferir conclusiones mediante la definición de ciertos patrones de eventos. A raíz de lo anterior comentado, surgen dos propiedades características de estos tipos de programas: la aciclicidad y el orden 2.3. ESPER 15 entre reglas. Estas propiedades ocurren debido al carácter no determinista y confluente (el orden de ejecución de las reglas importa) de estos sistemas [Burgueño et al., 2018]. Estas dos propiedades son las que se han conseguido automatizar mediante el desarrollo de la herramienta. Aciclicidad de las reglas Supongamos que tenemos las reglas que están representadas en la Figura 2.3 como un grafo dirigido, donde los nodos con forma de rectángulos son eventos simples y los eventos con forma de óvalo son eventos complejos. Este grafo muestra sistema CEP en una Smart House y no tiene ningún ciclo entre sus eventos. Imaginemos que, por error, la regla “COHigh” tuviera en su conjunto de dependencias al evento “FireWarning”, con lo cual se estaría formando un ciclo entre ambas reglas. Esto no quiere decir que la especificación de las reglas sea incorrecta, pero puede llegar a producir situaciones de bucles infinitos (una regla que produce un tipo de evento que consume otra regla que, a su vez, produce un evento que consume la primera). Alertar de esta situación puede suponer corregir errores críticos en la especificación. Orden entre reglas Dadas dos reglas R1, R2, la primera consume eventos de tipo by produce eventos de tipo a, y la segunda consume eventos de tipo cy produce eventos de tipo b. Supongamos que recibimos un evento de tipo cy que R2se ejecuta antes que R1, con lo cual obtendrías como resultado la salida de dos eventos, uno de tipo by otro de tipo a. El problema surge cuando primero se comprueba la regla R1y, posteriormente, R2. A la llegada del evento cla regla R1no produciría nada ya que no consume eventos de este tipo, pero la regla R2sí que lo haría, con lo cual obtendríamos como resultado un evento de tipo b. Para solventar este tipo de situaciones algunos lenguajes de Procesamiento de Eventos incluyen la posibilidad de incluir prioridades a las reglas, de tal manera que, a la llegada de un evento, siempre se comprueben antes las más prioritarias. En el ejemplo anterior, R2sería más prioritaria que R1. 2.3. Esper Esper [EsperTech, 2018] es un motor de procesamiento de eventos complejos de código abierto (open-source) que pertenece a la compañía EsperTech Inc. Proporciona un lenguaje de procesamiento de eventos para especificar reglas sobre eventos simples y compuestos. 16 CAPÍTULO 2. ESTADO DEL ARTE Como se ha comentado en la sección anterior, este tipo de motores son capaces de correlacionar considerables cantidades de eventos en un tipo ínfimo. Esto es posible, gracias al cambio de en la manera de tratar los datos (o eventos). En la Figura 2.4 podemos ver en un enfoque (clásico) donde los datos son los persistidos y sobre ellos se lanzan consultas y, por otro lado, el enfoque en el cual se basan los sistemas CEP, en este caso, los patrones (reglas) son los persistidos y sobre ellos se lanzan los datos (eventos) para producir resultados. Figura 2.4: A la izquierda un enfoque estático de procesamiento de datos. A la derecha un enfoque dinámico orientado a sistemas CEP. El objetivo de la herramienta desarrollada en este TFG es el análisis en la especificación de programas Esper, con lo cual ha sido muy importante conocer cuál es la estructura de las reglas y cómo expresar el patrón deseado. A continuación, se muestra una explicación, a partir de un ejemplo, de todos los elementos que el analizador léxico implementado es capaz de reconocer. Figura 2.5: Ejemplo de la especificación de un evento simple y una regla en Esper Como se puede observar en la Figura 2.5, la sintaxis de Esper, en la especificación de reglas, es muy parecida a la de SQL (lenguaje de consultas para base de datos). Para crear un evento simple (primera línea del ejemplo), se hará utilizando las palabras reservadas create schema seguido de un nombre para ese evento simple (en este caso “Mo- 2.3. ESPER 17 torbike”). Opcionalmente, entre paréntesis, podremos especificar los atributo que tendrá este evento. En el ejemplo, este evento, que representa un evento de tipo motocicleta, tiene como atributos la presión de las dos ruedas (un número entero), la velocidad (double) y un atributo de tipo Boolean que representa si el conductor está sentado o no en el asiento. En la siguiente parte de la imagen, podemos observar la definición de una regla cuyo nombre se especifica con la anotación @Name y entre, paréntesis y comillas, el nombre (en este caso “BlowOutTire” (rueda pinchada). Un elemento muy importante a la hora de especificar las reglas, es hacerla visible a todas las demás. Es decir, expresar qué tipo de evento complejo va a generar tras su ejecución. Esto se consigue con la sentencia insert into seguida del nombre del evento complejo. Si se omitiera esta sentencia la regla no estaría visible al resto y el evento complejo generado por este patrón no estaría disponible para su uso en otro. Es posible que varias reglas produzcan el mismo tipo de evento complejo (todas ellas tendrías en mismo nombre en la sentencia insert into). La notación @Priority sirve para asignar prioridad a la regla. Si la prioridad se omite, se asocia la máxima prioridad por defecto (prioridad 0). Como se comentó en la sección anterior, es muy importante asociar prioridades correctas a las reglas en función a sus dependencias, para respetar el orden de ejecución de las mismas y no perder información (eventos) generados por otras reglas. La parte más importante en la definición de una regla, es la especificación del patrón de eventos que debe darse para que ésta se ejecute. Para ello, podemos observar en la Figura 2.5 la sección from. En esta parte de la regla encontraremos la fase de selección (donde se encuentran el conjunto de dependencias de la regla) y la fase de emparejamiento (criterios que deben ocurrir en los atributos de los evento del conjunto de dependencias de la regla para su ejecución). Esta parte es la más crítica en el herramienta y donde más se ha indagado en su desarrollo, debido a que, de ella se extrae toda la información necesaria para analizar las dos propiedades (aciclicidad y orden de ejecución) mencionadas con anterioridad. Para describir el patrón se utilizada la palabra reservada pattern y entre corchetes se expresa el patrón. Para poder expresar patrones de eventos, a continuación se explican los operadores más relevantes en Esper para su definición: 24 CAPÍTULO 3. TECNOLOGÍAS UTILIZADAS Figura 3.2: Jerarquía de directorios de un proyecto Xtext. En la Figura 3.2 se muestra la jerarquía de subproyectos generados al crear el proyecto. En el proyecto org.xtext.example.mydsl nos encontramos el fichero donde expresaremos nuestra gramática (MyDsl.xtext) y el archivo GenerateMyDsl.mwe2 donde se encuentran los flujos de tareas (workflow) que permitirán crear el editor y poder generar trazas de la gramática para su depuración. Cuando se genera la gramática a partir del archivo de flujos de tareas, se utiliza el generador ANTLR, si no se tiene previamente instalado, la herramienta solicitará la descarga. Xtext utiliza este generador para crear el parser. Cuando se genere el código del editor y del parser estos serán depositados en la carpeta src-gen de los proyectos org.xtext.example.mydsl yorg.xtext.example.mydsl.ui. En el primero se guarda el código del parser y en el segundo el código del editor, es decir, los aspectos sobre la coloración, autocompleción, y comprobación de la gramática [García et al., 2013]. 3.3.2. Ejemplo de uso En la Figura 3.3 podemos observar una definición muy simple de la gramática de un DSL. Más concretamente, la gramática es una versión muy simplificada de la gramática del lenguaje Esper. Tomándolo como punto de partida, vamos a comentar los conceptos clave que Xtext nos proporciona para definir gramáticas. 1. La definición de la gramática se basa en expresar reglas que definan la sintaxis del lenguaje que se desea diseñar. El nombre de las reglas se empieza en mayúsculas y su nombre tiene que ser único. 2. La primera regla (línea 5) se considera la regla de inicio. Esta regla indica que los programas Esper están compuestos por eventos simples o reglas. Para poder expresar 3.3. XTEXT 25 Figura 3.3: Definición de una gramática en Xtext más de una regla o evento tenemos que dotar de multiplicidad a la regla, esto se consigue utilizando los operadores de cardinalidad (+, *, ?). Para este caso, a la regla se le impuesta que puede tener cero o muchas (operador *) reglas o eventos. Esta regla hace de punto de acceso (o nodo raíz) en el árbol de sintaxis abstracta que el parser crea a partir del lexer. 3. Las reglas pueden ser asignadas mediante operadores de asignación (=, +=, ?=). Gracias a esta asignación, cuando el parser genere el AST, podremos acceder a ellas como si fueran atributos de una clase Java. En la Figura 3.3, se puede observar que en la primera regla se hace uso del operador += para asignar todas las ocurrencias de reglas al atributo rules de la regla principal. Este atributo es una lista que contiene todas las instancias de reglas del archivo. 4. Las reglas pueden contener keywords representadas como caracteres entre comillas 26 CAPÍTULO 3. TECNOLOGÍAS UTILIZADAS simples. 5. A una regla se le puede asignar un atributo name, el cual representa un identificador para la regla. Por ejemplo, para la regla Event es lo lógico que su identificador sea el nombre del evento, para ello basta con asignar al atributo name el valor deseado. 6. En la definición de una regla podemos realizar referencias cruzadas, es decir, podemos asignar a un atributo de la regla, el valor del identificador del atributo name de otra regla. Para hacerlo, simplemente hay que poner el nombre de la regla entre corchetes. Como se ve en la última regla (línea 47), al atributo simpleEvents se le asignara el valor name de la regla Event Si el lector está interesado en profundizar en todos los recursos que proporciona Xtext para la definición de la gramática, se le remite a la documentación de este framework [Xtext, 2018]. 3.3.3. Editor de texto Una vez creada la gramática podemos lanzar el editor de texto para comprobar la gramática definida en el apartado anterior. Para ello, habría que pulsar botón derecho sobre la venta donde se ha definido la gramática y pulsar sobre Run As →Generate Xtext Artifacts. Una vez hecho, podemos observar que Xtext genera para cada regla una representación de ella encapsulada en una clase Java, véase Figura 3.4. Así pues, cuando en el editor de texto detecte una regla, se devolverá una instancia de ésta al parser, y éste, generará el AST acorde al conjunto de instancias que haya en el editor. Para abrir el editor basta pulsar botón derecho sobre el primer proyecto (en este caso org.xtext.example.mydsl) y pulsar Run As →Eclipse Application. Una vez hecho esto, se abrirá una segunda instancia de Eclipse. Sobre ella tendremos que crear un proyecto haciendo File →New →Project... →Java Project y dentro del proyecto crear un archivo con la extensión del DSL que se especificó en la creación del proyecto Xtext. En la Figura 3.5 se puede observar la nueva instancia de Eclipse donde se despliega el editor de texto y donde se pueden escribir programas con la gramática diseñada. 3.3.4. Generación de código Uno de los principales potenciales del uso de DSL es la capacidad de generar código a partir de ellos. Xtext proporciona una manera simple de realizarlo a través del lenguaje Xtend. Para ello, solo ha de abrirse la clase Xtend “DslGenerator.xtend” situada en el paquete que termina con la extensión “.generator”. En esta clase nos encontremos lo que se 3.3. XTEXT 27 Figura 3.4: Clases generadas a partir de la gramática. denomina una función de “callback” llamada “doGenerate” que, cada vez que guardemos nuestro archivo en la segunda instancia de eclipse, el motor de Xtext llamará a esta función pasándole tres parámetros: 1. Resource: este parámetro pertenece a la API de EMF, y hace posible el acceso al AST creado por el parser para poder navegar, a través de sus relaciones, entre las instancias creadas de las reglas definidas en la gramática. 2. IFileSystemAccess2: este parámetro perteneciente a la propia API de Xtext nos abstrae operaciones sobre ficheros, con lo cual, podremos crear, sobrescribir y modificarlos de una manera sencilla. 3. IGeneratorContext: interfaz del contexto del generador. No se ha requerido utilizar este parámetro en la generación. En la Figura 3.6 podemos ver una simple implementación de este callback que, cada vez que guardemos el archivo de nuestro DSL en la segunda instancia de Eclipse, generará un archivo de texto plano el cual contendrá el nombre de todos los eventos simples que haya en la especificación. Se puede observar el potencial que ofrece Xtend al ofrecer un mecanismo para realizar plantillas de código (contenido del archivo a generar) mediante sentencias de escape denotadas por los símbolos «». 28 CAPÍTULO 3. TECNOLOGÍAS UTILIZADAS Figura 3.5: Segunda instancia de Eclipse donde se abre el editor de texto. 3.4. ANTLRWorks ANTLRWorks [ANTLR, 2018], es un entorno de desarrollo para gramáticas ANTLR. Su uso ha sido muy específico, se ha utilizado para comprobar el correcto funcionamiento de la gramática desarrollada. A medida que ésta se hacía más compleja, podía volverse ambigua, este tipo de problemas no son fácilmente detectables y esta herramienta nos proporciona una manera sencilla de depurar gramáticas ANTLR. Un ejemplo de su uso se verá en el Capítulo 5. 3.5. GEF (Graphical Editing Framework) GEF [Eclipse, 2018c] proporciona, de una manera integrada con el IDE Eclipse, una serie de herramientas para la visualización y desarrollo de aplicaciones gráficas. Se puede instalar como un plugin de una manera simple. Esta herramienta se ha utilizado para la visualización de grafos escritos en lenguaje DOT en una vista nativa en Eclipse (véase la Figura 3.7), ya que trae un interprete de este lenguaje. Su instalación se muestra en el Apéndice A. 3.6. GRAPHVIZ 29 Figura 3.6: callback para realizar generación de códig en Xtext. 3.6. Graphviz Graphviz [Graphviz, 2018b] es un software libre para la visualización de grafos. Esta herramienta coge descripciones de grafos en lenguajes como DOT y los representa de una manera más visual en formatos como PDF, SVG, formatos de imagen, etc. Para la herramienta desarrollada, la instalación de Graphviz no es obligatoria pero sí muy recomendable ya que, al hacerlo, nos permitirá desde Eclipse exportar el grafo en el formato que el usuario desee. Además, Graphviz permite una mejor visualización del grafo a través de la ventana gráfica de GEF, frente al uso del propio interprete DOT de GEF. Figura 3.7: Vista nativa del interprete del lenguaje DOT proporcionado por GEF. 3.6.1. DOT DOT es un lenguaje para especificar grafos de una forma sencilla. En la Figura 3.8 se puede observar un ejemplo de su definición. Para grafos dirigidos (únicos utilizados en este proyecto), la definición del grafo tiene que empezar con la palabra reservada digraph 30 CAPÍTULO 3. TECNOLOGÍAS UTILIZADAS Figura 3.8: Ejemplo de definición de un grafo mediante el lenguaje DOT. seguido de un nombre. Para definir un nodo simplemente hay que poner un identificador único, seguido (opcionalmente), de unos parámetros para modificar su estilo. Notar que no hace falta separar cada definición por “;”, pero sí que hay que realizarlas en una línea independiente. Para definir una flecha entre dos nodos, solamente hay que poner el identificador del nodo origen seguido de “->” y el identificador del nodo destino. También, se podrán añadir opciones para el estilo de cada flecha. Para una explicación en más detalle sobre el lenguaje DOT, se remite al lector a [Graphviz, 2018a] Capítulo 4 Estructura de la herramienta En este capítulo se indaga en la herramienta desarrollada, comentando los dos aspectos más importantes de ésta: la definición de la gramática y la generación de código. Para el primer aspecto se profundizará en la implementación de las reglas más importantes de la gramática (aquellas donde se definen el conjunto de dependencias de las reglas CEP). En la parte de generación de código se hablará cómo se ha conseguido pasar de un AST a un grafo dirigido y cómo se han realizado los análisis y la generación de los diferentes grafos y archivos. 4.1. Entorno La herramienta desarrollada tiene como objetivo el análisis de las dos propiedades comentada en la sección dedica a los sistemas CEP en el Capítulo 2. A partir de un fichero con la especificación de los eventos y reglas, la herramienta realizará lo que se denomina un análisis estático (análisis sin que el sistema esté en ejecución). A continuación se explica la arquitectura general de la herramienta y las tecnologías se han utilizado en cada parte, basándonos en la Figura 4.1. El fichero de eventos y reglas será creado dentro de un proyecto en el editor de texto que Xtext proporciona, y contendrá una especificación de un programa CEP escrito con el lenguaje de procesamiento de eventos Esper. En la Figura 4.1, se muestra que el fichero está fuera del entorno Xtext pero, lo hemos representado así ya que el lenguaje de procesamiento de eventos complejos no es parte de Xtext pero cabe aclarar que los programas CEP hay que crearlos en el editor. Una vez se tenga el fichero de reglas CEP, se podrá analizar las propiedades en la parte de generación de código de Xtext, para ello se ha utilizado Java yXtend indistintamente para programar los análisis, y el framework EMF para acceder al AST que nos proporciona el parser. 31 32 CAPÍTULO 4. ESTRUCTURA DE LA HERRAMIENTA El primer análisis que se hace es la comprobación de la aciclicidad en las reglas, ya que el resultado que se genera depende de si hay ciclos o no. En el caso de que haya algún ciclo, solo se generará un grafo alertando de dónde se encuentran estos ciclos, es decir, entre qué reglas. Por otro lado, si no hay ciclos se generará un grafo donde se podrán ver las dependencias entre reglas y si las prioridades asignadas antes del análisis son las correctas. Además, se generará el mismo conjunto de reglas entrante pero con una asignación de prioridades que se estiman correctas tras el análisis. Para la visualización de los grafos, en el editor de Eclipse se ha utilizado el framework GEF que proporciona una ventana gráfica donde mostrar los grafos escritos en lenguaje DOT. Figura 4.1: Workflow de la herramienta y tecnologías utilizadas en cada parte. Además, independientemente de la existencia de ciclos o no, también se generará un archivo en texto plano que mostrará los resultados obtenidos tras la realización del análisis. Este archivo será una especie de log informativo. 4.2. Definición de la gramática El primer paso para el desarrollo de la herramienta, ha sido el desarrollo de una gramática capaz de reconocer la sintaxis de Esper. Para llevar acabo tal fin, se ha utilizado el 4.2. DEFINICIÓN DE LA GRAMÁTICA 33 Figura 4.2: Representación de alto nivel del AST generado. lenguaje de desarrollo de gramática que nos proporciona Xtext. Si el lector está interesado, puede ver la definición completa en el Apéndice C. En la Figura 4.2 podemos observar la estructura (en alto nivel) del AST generado. Se ha obviado la definición de eventos simples ya que ha sido explicado en el Capítulo2en la sección dedicada al lenguaje Esper. En el desarrollo se ha profundizado con especial énfasis en la parte de la definición de los patrones (sección from de las reglas), ya que es aquí donde podemos encontrar las dependencias que tiene una regla y, a raíz de estas dependencias, poder realizar el análisis de las propiedades ya previamente mencionadas. En esta parte, se han utilizado dos operadores principales (every yfollowedBy). A continuación se muestra la definición de la regla Pattern (Figura 4.3), la cual representa la sintaxis de los patrones en Esper. Ha sido definida con una jerarquía de abstracciones, de tal modo que las regla que expresan un comportamiento de bajo nivel son envueltas por otras reglas que expresan un comportamiento general. Por motivos de claridad, a continuación se explican las reglas sobre su representación gráfica obtenida del visor de reglas de Xtext en forma de diagramas (accesible a través de Window →Show View →Other... →Xtext →Xtext Syntax Graph), las características más importantes de éstas: Pattern: la Figura 4.4 muestra la representación más abstracta de un patrón, que viene definida por la keyword pattern y entre corchetes la definición del patrón. JoinFollowBy: El siguiente paso en la jerarquía de abstracciones viene definido por la regla JoinFollowBy, y trata de definir la posibilidad de poder combinar patrones 40 CAPÍTULO 4. ESTRUCTURA DE LA HERRAMIENTA genera el archivo de reglas pero en las secciones @Priority, estará definida la prioridad según en análisis. De antemano, se puede pensar que le implementación de esta funcionalidad ha sido directa, ya que solo bastaría con recorrer el AST e ir iterando sobre todas las reglas cambiando la sección @Priority. El problema radica en que la generación de código se realiza después de que el parser genere el AST. Este, a su vez, es construido con los tokens que realiza el lexer sobre el archivo. En este proceso de tokenización se eliminan todas las keywords definidas en las reglas y se genera los atributos de cada regla con el valor que les corresponda. De este modo, con el AST se pierde el acceso a las keywords definidas. Para solventar el problema, se ha tenido que indagar en la API de EMF para obtener un método que devuelva una URI (Uniform Resource Identifier) del AST generado (está URI representaría la dirección del archivo de reglas, del cual se ha generado el AST). Esta URI obtenida es una implementación de la propia API de EMF y no una estandarizada, con lo cual se ha tenido que utilizar un método de esta API que crea un InputStream a partir de este tipo de URIs. En la Figura 4.11 se pueden ver los métodos utilizados para llevar este proceso a cabo. Una vez obtenido el acceso al archivo, simplemente se ha iterado sobre cada línea de cada regla, modificando la sección @Priority por la prioridad que le corresponde del análisis. Figura 4.11: Apertura de un InputStream a partir de la representación de URI de EMF. 4.3.1. Algoritmos utilizados Orden topológico de un grafo Dado un grafo dirigido acíclico (no contiene ningún ciclo entre sus vértices), un orden topológico es una relación de orden total (≺) entre vértices tal que: si existe un arco desde nam, entonces mes mayor que nen el orden. Para un mismo grafo dirigido puede haber diferentes ordenes topológicos, y si el grafo dirigido contienen algún ciclo, este orden no se podrá calcular. Normalmente este algoritmo es usado para tareas de planificación de 4.3. GENERACIÓN DE CÓDIGO 41 tareas con dependencias entre ellas (es decir, una tarea no se puede completar si la ejecución de otra u otras). Para explicar cómo realizar una ordenación topológica sobre un grafo dirigido, se introducen dos conceptos: Fuente: vértice que no recibe ninguna arista (su grado de entrada es 0). Sumidero: vértice del cual no salen ningún vértice (su grado de salido es 0). Tomemos de partida el grafo inicial de la Figura 4.12, cuyos vértices representan tareas a realizar y sus aristas dependencias entre ellas. De este modo, la tarea 3 solo se podrá hacer si previamente se ha hecho la tarea 1 y la tarea 2. Para calcular un orden topológico sobre este grafo basta con seleccionar una fuente y visitarla quitando todas sus aristas. Este proceso se repite hasta que se hayan visitado todos los vértices. El orden en el cual se han ido visitando los vértices, sería un posible orden topológico. Siguiendo el ejemplo, empezaríamos en la única fuente del grafo, la tarea 1. Visitamos el vértice 1y eliminamos todas sus aristas. A continuación nos quedarían dos posibles fuentes, la tarea 2 y la tarea 4. Seleccionamos la tarea 4 y repetimos el proceso, quedando el conjunto de vértices seleccionados: 1, 4. Si repetimos el proceso anterior, una vez visitados todos los nodos, obtendremos el siguiente orden topológico: 1, 4, 2, 3, 5, 6. Algoritmo de Kosaraju Dado un grafo dirigido, una componente fuertemente conexa es un subconjunto de los vértices que componen el grafo, donde hay un camino entre dos vértices cuales quiera y otro camino de vuelta, es decir, hay un ciclo en ese conjunto de vértices. El algoritmo de Kosaraju es un algoritmo que calcula todas las componentes conexas en un grafo dirigido. Su complejidad es linear ya que el algoritmo crece en proporción al numero de vértices y aristas en el grafo, es decir, su complejidad es O(V+E). Para la ejecución de este algoritmo necesitaremos un conjunto para marcar los vértices visitados y una estructura de datos LIFO (por sus sigas en inglés Last In, First Out), con una simple pila es suficiente. Los pasos a seguir serían los siguientes: 1. Comenzamos visitando un vértice, desde este se realiza una búsqueda en profundidad (DFS) visitando todos los vértices en su recorrido. Cuando un vértice no se pueda expandir más (desde él no se pueda navegar hacía otro vértice) será añadido a nuestra pila. Una vez que el vértice donde hemos empezado la búsqueda en profundidad no tiene más vértices que no hayan sido visitados, se añadirá a la pila y seleccionaremos otro vértice no visitado para repetir este proceso. 42 CAPÍTULO 4. ESTRUCTURA DE LA HERRAMIENTA Estado Inicial Paso 1 Paso 2 Paso 3 Paso 4 Paso 5 Paso 6 Figura 4.12: Elaboración de un orden topológico. 4.3. GENERACIÓN DE CÓDIGO 43 2. Una vez que todos los vértices hayan sido visitados, tenemos que invertir el grafo, es decir, construir el mismo grafo pero invirtiendo la dirección de sus aristas. Si tenemos una aristas de A hacia B, al invertirla, esta aristas irá de B hacia A. 3. Ahora, partiendo de un conjunto vacío de vértices visitados, se realiza una búsqueda en profundidad de los vértices que están en la pila. De esta manera, se empieza extrayendo un vértice de la pila, comprobando si no ha sido previamente visitado (si ha sido visitado, se descarta y se extrae el siguiente) y se realiza una búsqueda en profundidad sobre el grafo inverso. 4. En la búsqueda en profundad se irán visitando todos los vértices hasta que no se puedan visitar más (porque ya hayan sido visitados). El conjunto de vértices visitados para esta búsqueda concreta sería una componente conexa. Para encontrar el resto de componentes, bastaría repetir el paso 3 y 4 hasta que nuestra pila se quede vacía. Tomando como ejemplo el grafo situado en la parte izquierda de la Figura 4.13, un conjunto vacío de vértices visitados C1y una pila vacia P, vamos a aplicar este algoritmo. Empezando por el vértice B, aunque podríamos empezar por cualquier otro, realizamos una búsqueda en profundidad hasta llegar al vértice D, desde el cual no podemos seguir navegando ya que no tienes más sucesores. Al llegar a este nodo, el conjunto de visitados C1incluiría todos los vértices del grafo B, C, A, De incluiríamos el nodo Den la pila P=D. A continuación comenzaría el preceso de backtracking, es decir volver al vértice desde el cual hemos llegado al vértice Dy comprobar si tienes más sucesores no visitados para explorar. Una vez realizado el proceso completo, nuestra pila quedaría de la siguiente manera, P=B, C, A, D. Figura 4.13: A la izquierda un grafo dirigido. A la derecha el grafo anterior invertido. Una vez tengamos la pila con el orden de visita de los vértices, tenemos que invertir el grafo (grafo situado en la parte derecha de la Figura 4.13) y aplicar, de nuevo, una búsqueda en profundidad sobre los vértices extraídos de la pila. De esta manera, el primer vértice extraído sería el vértice By su búsqueda en profundidad daría como resultado la componente conexa hB, A, Ci. El siguiente vértice que se extraería de la pila sería el vértice Dya que los vértices CyAya han sido visitados en la búsqueda en profundidad 44 CAPÍTULO 4. ESTRUCTURA DE LA HERRAMIENTA anterior. Al hacer la búsqueda en profundidad sobre el vértice Dsus nodos adyacente ya han sido visitados con lo cual nos queda otra componente conexa formada por el vértice D, hDi. Al extraer el último elemento de la pila, está quedaría vacía, con lo cual, el algoritmo finalizaría y como resultado obtendríamos las dos componentes conexas anteriores. Capítulo 5 Validación y pruebas Este capítulo detalla la depuración de la gramática desarrollada, y cómo se ha delimitado el desarrollo de ésta. Para realizar la depuración, se introduce el uso de la herramienta ANTLRWorks para depurar gramáticas ANTLR, este tipo de gramáticas son las que utiliza Xtext internamente. Además, se propone un conjunto de reglas que han servido como test de regresión. 5.1. Depuración de la gramática En el desarrollo de la gramática, el problema más frecuente que ha surgido, es que en algún punto de su desarrollo ésta se volvía ambigua. Cuando la gramática desarrollada es pequeña, detectar este tipo de problemas puede ser relativamente sencillo a partir de las alertas que genera Xtext. Pero cuando la gramática se vuelve más extensa e incluye reglas recursivas que depende de otro tipo se reglas, detectar este problema se hace más difícil. Xtext no proporciona ningún método para depurar la gramática. Si hay errores en la definición, el workflow que genera tanto el lexer como el parser, no se ejecuta y se lanza un error. Si Xtext detecta que la gramática es ambigua, pero su definición es correcta, el workflow se ejecuta pero, internamente Xtext poda el AST cuando detecta ambigüedad. No es muy recomendable dejar a Xtext realizar este tipo de acciones porque se pierde el control de la gramática y podemos estar generando un AST que no es acorde a nuestra definición. Por este motivo se ha utilizado el entorno de desarrollo para gramáticas ANTLR ANTLRWorks [ANTLR, 2018]. Esta herramienta nos permite visualizar de una forma gráfica aquellas reglas que tienen problemas de ambigüedad, mostrando un diagrama donde se pueden ver distintas trazas de ejecución que generan el mismo AST. La herramienta se descarga como un fichero .jar, de tal modo que su ejecución es directa si se tiene instalado una JVM en la máquina pertinente. 45 46 CAPÍTULO 5. VALIDACIÓN Y PRUEBAS Lo primero que hay que hacer para utilizar esta herramienta, es configurar el workflow en Xtext para que genere un archivo con extensión .g, el cual contendrá la gramática ANTLR. No se puede utilizar la gramática ANTLR generada directamente por Xtext ya que éste, en última instancia, la modifica para incluir aspecto de autocompleción o verificación del código. En la Figura 5.1 se puede ver el contenido del workflow incluyendo la sentencia correspondiente para activar la generación de la gramática ANTLR a depurar (líneas 43-45). Figura 5.1: Workflow para la generación de la gramática. Una vez configurado el workflow, generamos la gramática como se ha explicado en la sección dedicada a Xtext del Capítulo 3. Cuando se haya generado, dentro del directorio “src-gen” del proyecto principal, en el paquete cuya terminación es “...antlr.internal”, encontraremos el archivo con extensión .g que contienen una gramática apta para ejecutarla en ANTLRWorks. 5.2. PRUEBAS DE REGRESIÓN 47 Figura 5.2: Ejemplo de depuración de gramática ANTLR en ANTLRWorks. A continuación, abrimos ANTLRWorks y cargamos el fichero .g (File →Open). Se nos desplegará en la parte izquierda un listado de todas las reglas contenidas. Si pulsamos sobre el botón para hacer la depuración (botón con icono de un insecto), se efectuará un análisis sobre todas las reglas y, al finalizar el análisis, aparecerán en rojo aquellas reglas que contengan algún tipo de problema. Si pulsamos sobre alguna de ellas, se nos abrirá un diagrama con la estructura de la regla. Sobre este diagrama podemos superponer las diferentes trazas que generan el mismo AST, pulsando en la sección “Alternatives” y seleccionando la traza o trazas que deseemos mostrar. En la Figura 5.2, se puede ver dos trazas superpuestas (verde y roja) en una regla que produce un problema de ambigüedad en la gramática. Gracias a esta herramienta se ha podido depurar la gramática al darnos los puntos exactos donde se genera la ambigüedad, para corregirlos se ha hecho uso del operador => explicado en el Capítulo 4. 5.2. Pruebas de regresión Las pruebas de regresión sirven para comprobar que una nueva funcionalidad añadida a un software, no modifica o altera una o varias funcionalidades previamente existentes 48 CAPÍTULO 5. VALIDACIÓN Y PRUEBAS en el programa. Estas pruebas se van construyendo a raíz de los casos de prueba para comprobar el correcto funcionamiento de una funcionalidad, de tal manera que cuando se desarrolle una nueva característica, contaremos con una batería de pruebas que cubrirá cada funcionalidad anterior a la nueva desarrollada. Si esta nueva funcionalidad pasa estas pruebas de regresión, se podrá afirmar, en mayor o menor medida, que no modifica las demás funcionalidades preestablecidas. Un punto de especial interés en el desarrollo del presente proyecto, ha sido decidir el nivel de detalle a incluir en nuestra gramática para reconocer programas CEP. Desarrollar desde cero un lexer capaz de reconocer el lenguaje completo Esper, no tendría mucho sentido, ya que podríamos utilizar el propio lexer que implemente Esper y ampliarlo. Además siguiendo esta vía de usar software desarrollado por terceros, se perdería el componente académico del aprendizaje de todas las tecnologías principales utilizadas mediante su desarrollo desde cero. Para delimitar el alcance del lexer, durante el desarrollo del mismo se han definido cuatro conjuntos de reglas que han servido de pruebas de regresión y de delimitadores. Debido a que en el desarrollo de la gramática hay reglas con referencias cruzadas hacia otras, jerarquías de reglas y recursividad, es muy probable que al intentar modificar alguna o intentar añadir una funcionalidad sobre reglas existentes, se acaben alterando el funcionamiento de las reglas de la gramática. Con tal motivo, para cada ampliación del lexer, se hace comprobar, a partir de estos conjuntos de reglas considerados como un conjunto de pruebas de regresión, que no se han alterado los patrones ni estructuras que ya se reconocían previamente. Por otro lado, han servido como delimitadores en el sentido de que cuando el lexer ha sido capaz de cubrir los 4 conjuntos de reglas, se ha dado por finalizado su desarrollo para poder pasar a la fase de análisis y generación de código. Cada conjunto de reglas tiene un aspecto peculiar que lo diferencia del resto, de este modo, para una versión del lexer que reconociera un conjunto determinado, no reconocería los restantes. A continuación se muestra una breve descripción de estos conjuntos de reglas: Smart House [Moreno et al., 2018]: este conjunto consta de seis reglas que modelan un sistema CEP en una “hogar inteligente”. Ese conjunto ha sido el pilar fundamental para el desarrollo de la estructura pattern. Motorbike [Burgueño et al., 2018]: en este conjunto encontramos un sistema CEP que se ejecuta sobre diferentes sensores en una motocicleta. De este conjunto de reglas se extrajo la capacidad de que el lexer fuera capaz de reconocer “joins” (patrones 5.2. PRUEBAS DE REGRESIÓN 49 de patrones). Air Quality [Burgueño et al., 2018]: conjunto de más de cuarenta reglas que modelan un sistema CEP para la detección de los diferentes componentes que hay en el aire. La característica más destacable es que la mayoría de reglas producen el mismo tipo de evento que recolecta una única regla, con lo cual, ésta dependía de todas las anteriores. Nuclear power station [Boubeta-Puig, 2018]: este conjunto de reglas modela un simple sistema de alerta en una central nuclear cuando se detecta cierto patrón de temperatura. El conjunto ha sido tomado como punto de partida para el desarrollo de la gramática al contar con pocas reglas pero conteniendo la estructura básica de éstas. En el Apéndice D se puede se encuentran estos conjuntos de reglas Esper.. 56 APÉNDICE A. MANUAL DE INSTALACIÓN Apéndice B Manual de usuario En este apéndice se mostrara un ejemplo de uso completo de la herramienta. Para ello se partirá del conjunto de reglas Smart House y del editor de texto ya desplegado en segunda instancia (ambos explicados en el Capítulo 5 y en el Capítulo 3 respectivamente). Nótese que la extensión utilizada para los archivos de reglas ha sido .esper. Una vez abierto el editor de texto y creado un proyecto para albergar el archivo de reglas, simplemente tendremos que guardar el archivo para que se realice el análisis y se genere los archivos pertinentes. Como se observa en la Figura B.1 se han generado tres archivos en el directorio src-gen: SmartHouse.dot, el cual representa el grafo que será interpretado por el visor. SmartHouseLog.txt:log del análisis. Se puede ver su estructura en la Figura B.1. SmartHousePriorities.esper: archivo con las mismas reglas entrantes pero con las asignación de prioridades acorde a un orden topológico de las reglas. Como se puede observar en la Figura B.1, tras el análisis no se han detectado ciclos pero se han detectado reglas cuyas prioridades no están acorde con el orden topológico generado. Si abrimos el archivo SmartHouse.dot y enlazamos este archivo con la vista que nos proporciona GEF (explicado en la sección sobre GEF del Apéndice A) obtendremos la representación gráfica del grafo, tal y como se puede ver en la Figura B.2. Como se observa en esta imagen, los eventos simples se han representado con una forma rectangular y los eventos complejos con una forma de óvalo. Además, hay dos vértices cuya prioridad no se corresponde con la del análisis (vértices en rojo). Abriendo el archivo SmartHousePriorities.esper nos encontrarnos el conjunto de reglas y sus prioridades acorde a este análisis. 57 58 APÉNDICE B. MANUAL DE USUARIO Partiendo del mismo conjunto de reglas vamos a provocar un ciclo sobre su especificación para mostrar como difiere la generación de los archivos según se detecten ciclos o no. Una vez insertado el ciclo en la especificación, volvemos a guardar el archivo y la herramienta nos generará dos archivos (log y la representación del grafo). Como podemos observar en la Figura B.3, en el archivo SmartHouseLog.txt, se nos muestra que se ha detectado ciclos en la especificación y, además, cuáles son las componentes conexas de cada ciclo. Como ya se ha comentado anteriormente, si se detectan ciclos, no es posible generar las prioridades de cada regla porque, para hacerlo, se necesita que no existan ciclos. Observando la Figura B.4, podemos ver el grafo que se genera pero, esta vez, se muestra aristas en color rojo, que son las componentes conexas del ciclo detectado. Figura B.1: Log generado tras el análisis. 59 Figura B.2: Grafo generado tras en análisis. Figura B.3: Log generado tras el análisis insertando un ciclo. 60 APÉNDICE B. MANUAL DE USUARIO Figura B.4: Grafo generado tras el análisis insertando un ciclo. Apéndice C Definición de la gramática utilizada en el lexer En este apéndice se muestra la definición completa de la gramática del lenguaje de procesamiento de evento complejos Esper, utilizada para el desarrollo de la herramienta: grammar org.xtext.example.mydsl.MyDsl2 with org.eclipse.xtext.common.Terminals generate myDsl2 "http://www.xtext.org/example/mydsl/MyDsl2" Domainmodel: (rules+=RuleParts | events+=Event)∗ ; //−−−−−−−−−−−−−−−−−−EVENTS−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− Event: ’create’ ’schema’ name=ID eventattributes=Attributes ’;’ ; Attributes: ’(’ attribute+=AttributesDefinition (’,’ attribute+=AttributesDefinition)∗’)’ ; AttributesDefinition : name+=ID type+=ID ; //−−−−−−−−−−−−−−−−−−−−RULES−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− RuleParts: (nameRule = Name) (insert = Insert) (priority = Priority)? (selectRule = Select) (fromRule = From) (groupBy = GroupBy)? (having = Having)?’;’; Insert : ’ insert ’ ’ into’ name=ID 61 62 APÉNDICE C. DEFINICIÓN DE LA GRAMÁTICA UTILIZADA EN EL LEXER ; Name: ’@Name’ ’(’ name=STRING ’)’ ; Priority : ’@Priority’ ’(’ priorityInt = INT ’)’ ; Select : ’ select ’ ( selectAttributes += SelectAttributesDefinition (’as’ alias +=ValidID)? )+ (’,’ selectAttributes += SelectAttributesDefinition (’as’ alias +=ValidID)?)∗ | ( asterisk?=’∗’) ; KindSelectAttributesDefinition: singleSelectDefinition = SingleSelectDefinition | defaultMethod = DefaultMethods | int = INT | string = STRING ; SelectAttributesDefinition : rightSide += (KindSelectAttributesDefinition) (operator+=Operators leftSide+= (KindSelectAttributesDefinition ))∗ ; SingleSelectDefinition : event+=[SingleDefinition] ’.’ (attribute+=ID | ’∗’ ) ; From: ’from’ ((event=[Event] (’(’ anything = Anything’)’ | ’.’ anything=Anything )) | pattern = Pattern ) ; //−−−−−−−−−−−−−−−−−−Pattern−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− Pattern: ’pattern’ ’[’ joinFollowBy=JoinFollowBy ’]’ (’.’ win=Win)? ; JoinFollowBy: followsByJoinList+=AbstractFollowBy (operator+=Operators followsByJoinList+= AbstractFollowBy)∗ 63 ; AbstractFollowBy: (=> followBy = FollowBy | ’(’ followBy = FollowBy ’)’ ) (wherePart=FollowByWhere)? ; //−−−−−−−−−−−−−−−−−−FollowBy−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− FollowBy: leftSide =TerminalExpression (=> ’−>’ rightSide+=TerminalExpression)∗ ; TerminalExpression: every?=’every’ everyExpression = FollowBy | parenthesis?=’(’ betweenParenthesis = FollowBy ’)’ | singleDefinition = SingleDefinition ; KindOfEvent: Event | Insert; SingleDefinition : (=> name=ID ’=’)? simpleEvents=[KindOfEvent] (=>’(’anything=Anything’)’)? ; //−−−−−−−−−−−−−−−−−−−−−−−−−−Win−−−−−−−−−−−−−−−−−−−−−−−−−− Win: ’win’ ’:’ defaultMethod=DefaultMethods ; //−−−−−−−−−−−−−−−−−−−−−−Where−−−−−−−−−−−−−−−−−−−−−−−−−−−−− FollowByWhere: ’(’ FollowByWhere ’)’ | ’where’ timer=Timer ; Timer: ’timer’ ’:’ defaultMethod=DefaultMethods ; //−−−−−−−−−−−−−−−−−−−GroupBy−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− GroupBy: ’group’ ’by’ anything = Anything ; //−−−−−−−−−−−−−−−−−−−Having−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− Having: ’having’ defaultMethod = DefaultMethods (operator=Operators) anything=Anything 64 APÉNDICE C. DEFINICIÓN DE LA GRAMÁTICA UTILIZADA EN EL LEXER ; //−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− DefaultMethods: name=NameMethod ’(’ anything = Anything ’)’ ; ValidID: ID | NameMethod ; NameMethod: ’avg’ | ’current_timestamp’ | ’count’ | ’max’ | ’within’ | ’time_batch’ | ’time’ ; //−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− Anything: {Anything} =>(ID | INT | STRING | ’.’ | operator += Operators | extraParenthesis += ExtraParenthesisRule | ’where’ | ANY_OTHER)∗ ; ExtraParenthesisRule: ’(’ Anything ’)’ ; //−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− enum Operators: equal = ’=’ | lessThan = ’<’ | moreThan = ’>’ | lessEqualThan = ’<=’ | moreEqualThan = ’>=’ | and = ’and’ | or = ’or’ | between = ’between’ | in = ’in’ | not = ’not’ | notIn = ’not in’ | plus = ’+’ | minus = ’−’ | multiplication = ’∗’ | isnot = ’is not’ ; Apéndice D Conjuntos de reglas utilizados D.1. Smart House create schema Home(id String, temp Int); create schema Person(name Sttring); @Name("TempIncrease") insert into TempeIncrease select h2.ts as ts , h1.id as id, h2.temp as temp, h2.temp −h1.temp as incr from pattern [(every (h1 = Home() −> h2 = Home(h2.temp −h1.temp >= 2 and h2.id = h1.id))) where timer:withhin(1 minutes)]; @Name("TempWarning") insert into TempWarning select t4.ts as ts t1.id as id, t4.temp from pattern [(every (t1 = TempIncrease(t1.temp >= 33)) −> (t2 = TempIncrease(t2.temp > t1.temp and t2.id = t1.id)) −> (t3 = TempIncrease(t3.temp > t2.temp and t3.id = t1.id)) −> (t4 = TempIncrease(t4.temp > t3.temp and t4.id = t1.id))) where timer: within(5 minutes)]; @Name("COHigh") insert into COHigh select h1.ts as ts , h1.id as id from pattern [( every (h1 = Home(h1.co >= 5000)))]; @Name("FireWarning") insert into FireWarning select tw.id as id, coh.ts as ts from pattern [(every (coh = COHigh()) −> every (tw = TempWarning(tw.id = coh.id))) where timer: within(5 seconds)]; 65