- Parseando en Scala (1): Intro
- Parseando en Scala (2): Metasintaxis y AST
- Parseando en Scala (3): Modelo
- Parseando en Scala (4): Combinator parsing en acción
- Parseando en Scala (5): El código
- Parseando en Scala (6): Generando la salida
- Una vuelta de tuerca más a la generación del diagrama
- Superando el desafío de llevar el generador de diagramas a AppEngine
sábado, 30 de mayo de 2009
El backstage de NS-Matic: índice de posts
Ahora que NS-Matic está online gracias a Google AppEngine, les dejo un índice de los posts que podemos considerar backstage del proyecto: desde el parseo de PL/SQL, pasando por la construcción del AST, hasta la generación de diagramas en diferentes tecnologías.
Superando el desafío de llevar el generador de diagramas a AppEngine
El parseador y generador de diagramas del que hablábamos por acá ahora tiene nombre y está publicado como aplicación web en Google AppEngine: NS-Matic .
Como se sabe, desde hace poco AppEngine soporta Java, y eso significa que soporta varios lenguajes más: todos aquellos que compilan a bytecode para la JVM. Lo que yo no sabía hasta luego del primer deploy, era que las limitaciones impuestas por Google iban a frustrar el plan. Resulta que hay una lista blanca de clases estándar disponibles, entre las cuales no están las de AWT. En AppEngine no se puede instanciar ninguna clase de AWT. Google provee un API alternativo de manipulación de imágenes pero no incluye el tipo de operaciones que mi aplicación necesitaba.
Al no poder generar imágenes en el servidor, consideré usar el viejo generador de HTML. Pero no me quise conformar, e investigué la posibilidad de pasarle el fardo al cliente: ¿se puede dibujar en el navegador?
Dojo al rescate
No estaba al tanto pero resulta que sí, todo navegador que se precie hoy en día tiene capacidad de gráficos vectoriales. La mayoría con SVG, Internet Explorer con VML (cuándo no, cortándose solo). Cómo será la cosa: se está hablando de que esto le vaya ganando terreno a Flash. Para resolver las diferencias entre navegadores, podemos usar una librería cross-browser como Dojo Toolkit , y su módulo Gfx que sirve precisamente para graficar. En mis diagramas, el resultado se ve mejor que los GIF que generaba antes con AWT. Lo que se pierde es la posibilidad de guardar el diagrama como un archivo de imagen, lo que sería más práctico que guardar una página con javascript.
Antes dijimos que estábamos preparados para agregar nuevas implementaciones de generadores de diagramas porque teníamos un diseño extensible. El generador de AWT recorría el AST y daba como resultado un BufferedImage; el nuevo debería recorrer el AST y retornar un String con el script a ser ejecutado por el navegador.
Pero esto nos lleva a un nuevo replanteo: los generadores de AWT y Dojo Gfx, si bien apuntan a tecnologías diferentes (el cómo), tienen un núcleo común: el qué. Antes estábamos mezclando el qué y el cómo, ahora estamos obligados a extraer el qué, si queremos hacer las cosas bien.
El graficador abstracto
La idea sería poder definir en abstracto qué líneas hay que trazar y qué texto hay que desplegar, y en qué posición. Para esto necesitamos un modelo sencillo para generadores de tipo gráfico, que tengan la capacidad de tomar esa especificación y ejecutarla en alguna tecnología.
trait Alignment
case class AlignLeft() extends Alignment
case class AlignCenter() extends Alignment
case class Pos(x:Int, y:Int) {
def shift(dx:Int, dy:Int) = Pos(x + dx, y + dy)
}
case class Line(from:Pos, to:Pos)
case class TextLine(text:String, anchor:Pos, align:Alignment)
Pos define una posición (x,y), y con el método shift obtenemos una nueva posición con un delta horizontal y otro vertical. El concepto de posición, y la posibilidad de obtener una a partir de otra preexistente, serán de uso intensivo en esta solución. Line y TextLine definen los dos elementos básicos que sirven para armar todo.
class GraphicElement(
val pos:Pos,
val width:Int,
val elemHeight:Int,
val textLines: List[TextLine],
val lines: List[Line],
val children: List[GraphicElement])
{
lazy val height: Int = maxY - minY
lazy val nextPos = pos.shift(0, height)
private def minY = children match {
case Nil => pos.y
case _ => (children map (_.pos.y)) reduceLeft (_ min _) min pos.y
}
private def maxY:Int = children match {
case Nil => pos.y + elemHeight
case _ => ((children map (_.maxY)) reduceLeft (_ max _)) max (pos.y + elemHeight)
}
}
GraphicElement define un nodo gráfico como contenedor de objetos Line, TextLine, y nodos hijos del mismo tipo. El resultado del proceso será un árbol de nodos de éste único tipo. Para calcular en qué posición vertical se ubica cada elemento, es necesario establecer claramente cuánto espacio vertical ocupa cada uno. Al instanciar un GraphicElement, en elemHeight indicamos la altura "neta" del elemento, es decir, cuánto ocupa en vertical sin tomar en cuenta los nodos hijos. Podría ser cero en el caso de un simple contenedor de nodos. Lo que no indicamos nosotros es la altura "bruta", que incluye la de los hijos. Esa la calcula el campo height. Con el método nextPos vemos que cualquier elemento puede determinar la posición "siguiente" que se puede usar como origen del elemento que le sigue, cuando hay varios al mismo nivel. Y lo hace en términos de la posición propia, desplazada en vertical la altura propia.
Acá vemos una versión recortada del pre-generador para gráficos. El método generate retorna el GraphicElement raíz del árbol.
class GraphicGenerator(totalWidth: Int)
{
// ... codigo omitido
private def layoutText(s:String, p:Pos, w:Int,
align:Alignment):List[TextLine] = // ...etc
private def makeChildren(nodes:List[Node], prevElem:GraphicElement,
w:Int):List[GraphicElement] = // ...etc
def generate(n:Node):GraphicElement = generate(n, Pos(0,0), totalWidth)
private def generate(n:Node, p:Pos, w:Int): GraphicElement = n match
{
case s:Stmt =>
val textLines = layoutText(s.text, p.shift(5, STMT_HEIGHT - 5), w, AlignLeft())
val height = (STMT_HEIGHT - TEXT_HEIGHT) + (TEXT_HEIGHT * textLines.size)
new GraphicElement(p, w, height, textLines, Nil, Nil)
case f:Loop =>
val blockWidth = w - STMT_HEIGHT
val textLines = layoutText(f.text, p.shift(5, STMT_HEIGHT - 5), w, AlignLeft())
val height = (STMT_HEIGHT - TEXT_HEIGHT) + (TEXT_HEIGHT * textLines.size)
val blockPos = p.shift(STMT_HEIGHT, height)
val children = makeChildren(f.body, GraphicElement.nullObject(blockPos), blockWidth)
val childrenHeight = GraphicElement.sumHeights(children)
val blockLines = List(Line(p.shift(0,childrenHeight+height), p.shift(w, childrenHeight+height)),
Line(p, p.shift(w,0)),
Line(blockPos, blockPos.shift(blockWidth,0)),
Line(blockPos, blockPos.shift(0,GraphicElement.sumHeights(children))))
new GraphicElement(p, w, height, textLines, blockLines, children)
// ... y el resto de los nodos del AST
}
}
Como ejemplo vemos la resolución de los nodos Stmt (statement) y Loop. No importan mucho los detalles, pero señalaremos un par de cosas. Usamos el método layoutText cada vez que tenemos que generar texto; no podemos directamente instanciar un TextLine a partir de un String porque puede ocurrir que no nos dé el ancho disponible y haya que wrapear ese String. El método resuelve el wrapping y devuelve una lista de TextLine.
El método makeChildren procesa una lista de Node, invocando generate por cada uno, y determinando la posición de cada uno con nextPos del elemento anterior. Le pasamos como argumento un GraphicElement.nullObject, que es un GraphicElement vacío que sirve sólo para definir la posición inicial de esa secuencia de nodos.
Una vez que nos sacamos de encima todo el trabajo pesado, definamos un marco para las implementaciones gráficas. Estas ya no necesitan conocer el modelo del AST (Node y sus subtipos: Stmt, Loop, etc.) porque sólo trabajarán en términos de objetos GraphicElement.
abstract class GraphicBasedGenerator[T](width:Int) {
def generate(n:Node):T = {
val s = new GraphicGenerator(width).generate(n)
generate(s)
}
def generate(ge:GraphicElement):T
}
Esta clase ya resuelve el uso del graficador abstracto que a partir de un Node raíz obtiene un GraphicElement raíz. Queda por definir la generación de un T (tipo que depende del renderizado a usar) a partir de un GraphicElement. Entonces, implementé un graficador para Dojo Gfx como subclase de GraphicBasedGenerator, que es bastante sencillo y no incluyo en el post para no alargarlo más.
jueves, 14 de mayo de 2009
El problema del cuadrado con numeritos
Me topé con un problema irresistible, descripto en inglés en este post. No me haría ninguna gracia tener que resolverlo en una entrevista de trabajo, como fue el caso de aquel blogger: mi primer intento, en la tranquilidad de mi casa, fue lento y torpe. Pero es de esos problemas que, una vez leido el enunciado, no se pueden ignorar: si sos programador y mínimamente te gusta tu profesión, deberás resolverlo. Sugiero que lo lean allá, sin ver soluciones, y... ya sabrán que hacer.
Spoiler Alert
La solución en C del blogger me pareció inteserante por lo concisa, lo mismo la de algunos comentaristas de ese blog, que utilizaron diferentes lenguajes. Cuándo no, la mía es en Scala. Con Scala se puede apuntar a una solución concisa por su poder expresivo, pero no quise descuidar otro aspecto: que el código capture la intención. Es una solución funcional, y con objetos (uso un par de clases). Este es el resultado:
Square es un cuadrado de n celdas de lado. Pos es una posición (i, j). Definimos valores para ayudar en la claridad del código: highest es el valor más alto del cuadrado (que estaría en la celda superior izquierda). farEdge es el índice al "borde lejano"... o sea, el borde horizontal cercano es la fila 0, y el lejano la fila farEdge; igual con los bordes verticales (columnas 0 y farEdge).
Los métodos privados conceptualizan los detalles de la implementación. El método calc, en palabras se describiría así:
El método isEdge nos dice si la posición indicada cae en un borde del cuadrado, es decir, que la fila o la columna sea 0 o sea farEdge.
Lo del offset lineal surge de observar, en el planteo del problema, una característica de todos los "anillos" cuadrados que forman la grilla, desde el borde exterior hasta la celda central (o cuadrado de 2 x 2): Desde la celda superior izquierda, que contiene el máximo valor del cuadrado, podemos recorrer el borde en sentido reloj, y son todos valores decrecientes de uno en uno. Si "enderezamos" ese borde, tenemos un vector donde la primera posición es la más alta. Pero como su contenido es tan obvio, no necesitamos representarlo en memoria. Dado un índice, podemos calcular fácilmente el valor que habría en tal posición: en la 0 está highest, en la 1 está highest - 1, y así. Entonces, la única dificultad es obtener ese offset lineal, el índice al vector imaginario, a partir de una posición bidimensional. Esto lo hace el método linearOffset. Pensándolo un poco, descubrimos que hay dos fórmulas: una aplica cuando la posición está sobre el borde superior o derecho, y la otra si está sobre el inferior o izquierdo.
Cuando la posición pedida no está en el borde del cuadrado actual, procedemos con el cuadrado inmediatamente interior. Este cuadrado interior tendrá 2 celdas menos de lado que el actual. Obsérvese que nunca nos importa si empezamos desde un cuadrado más externo al actual: un cuadrado de 3 x 3 es exactamente lo mismo ya sea que hayamos partido de 3 x 3, o que hayamos partido de uno de 7 x 7 bajando hasta 3 x 3. Por eso el problema se puede resolver en términos de anillos individuales: si no me sirve el actual, me lo saco de encima y reintento con el que sigue, como quien quita las capas de una cebolla.
Lo que tenemos que tener en cuenta al bajar al cuadrado inferior es ajustar la posición, porque esta fue informada como relativa al cuadrado actual. Lo que ahora es (1, 1), para el cuadrado inferior es (0, 0). Ese ajuste lo hace la clase Pos con el método shiftIn.
Spoiler Alert
La solución en C del blogger me pareció inteserante por lo concisa, lo mismo la de algunos comentaristas de ese blog, que utilizaron diferentes lenguajes. Cuándo no, la mía es en Scala. Con Scala se puede apuntar a una solución concisa por su poder expresivo, pero no quise descuidar otro aspecto: que el código capture la intención. Es una solución funcional, y con objetos (uso un par de clases). Este es el resultado:
case class Pos(i:Int, j:Int)
{
def shiftIn = Pos(i - 1, j - 1)
}
case class Square(n:Int)
{
val highest = (n * n) - 1
val farEdge = n - 1
private def isEdge(x:Int) = x == 0 || x == farEdge
private def isEdge(p:Pos):Boolean = isEdge(p.i) || isEdge(p.j)
private def isTopOrRight(p:Pos) = p.i == 0 || p.j == farEdge
private def linearOffset(p:Pos) = if(isTopOrRight(p)) p.j + p.i else (farEdge * 2) + (farEdge - p.j) + (farEdge - p.i)
private def calc(p:Pos):Int = if(isEdge(p)) highest - linearOffset(p) else Square(n - 2).calc(p.shiftIn)
def calc(i:Int, j:Int):Int = calc(Pos(i,j))
}
Square es un cuadrado de n celdas de lado. Pos es una posición (i, j). Definimos valores para ayudar en la claridad del código: highest es el valor más alto del cuadrado (que estaría en la celda superior izquierda). farEdge es el índice al "borde lejano"... o sea, el borde horizontal cercano es la fila 0, y el lejano la fila farEdge; igual con los bordes verticales (columnas 0 y farEdge).
Los métodos privados conceptualizan los detalles de la implementación. El método calc, en palabras se describiría así:
Si la posición solicitada corresponde a un borde del cuadrado, tomar el valor más alto del cuadrado y restarle un offset lineal deesa posición respecto al contorno del cuadrado.
Si no, intentar con el cuadrado interno al actual.
El método isEdge nos dice si la posición indicada cae en un borde del cuadrado, es decir, que la fila o la columna sea 0 o sea farEdge.
Lo del offset lineal surge de observar, en el planteo del problema, una característica de todos los "anillos" cuadrados que forman la grilla, desde el borde exterior hasta la celda central (o cuadrado de 2 x 2): Desde la celda superior izquierda, que contiene el máximo valor del cuadrado, podemos recorrer el borde en sentido reloj, y son todos valores decrecientes de uno en uno. Si "enderezamos" ese borde, tenemos un vector donde la primera posición es la más alta. Pero como su contenido es tan obvio, no necesitamos representarlo en memoria. Dado un índice, podemos calcular fácilmente el valor que habría en tal posición: en la 0 está highest, en la 1 está highest - 1, y así. Entonces, la única dificultad es obtener ese offset lineal, el índice al vector imaginario, a partir de una posición bidimensional. Esto lo hace el método linearOffset. Pensándolo un poco, descubrimos que hay dos fórmulas: una aplica cuando la posición está sobre el borde superior o derecho, y la otra si está sobre el inferior o izquierdo.
Cuando la posición pedida no está en el borde del cuadrado actual, procedemos con el cuadrado inmediatamente interior. Este cuadrado interior tendrá 2 celdas menos de lado que el actual. Obsérvese que nunca nos importa si empezamos desde un cuadrado más externo al actual: un cuadrado de 3 x 3 es exactamente lo mismo ya sea que hayamos partido de 3 x 3, o que hayamos partido de uno de 7 x 7 bajando hasta 3 x 3. Por eso el problema se puede resolver en términos de anillos individuales: si no me sirve el actual, me lo saco de encima y reintento con el que sigue, como quien quita las capas de una cebolla.
Lo que tenemos que tener en cuenta al bajar al cuadrado inferior es ajustar la posición, porque esta fue informada como relativa al cuadrado actual. Lo que ahora es (1, 1), para el cuadrado inferior es (0, 0). Ese ajuste lo hace la clase Pos con el método shiftIn.
Labels:
scala
sábado, 25 de abril de 2009
Y hablando de diseño de APIs...
Hay que ver esta presentación de Joshua Bloch: How to design a good API and why it matters . Es fabulosa.
miércoles, 22 de abril de 2009
Leyendo XML en Java sin dolor
Leer XML en Java es un verdadero pain in the ass, a diferencia de Scala, que tiene soporte nativo para XML. No estoy muy al tanto de librerías que facilitan la tarea, que las debe haber, pero quiero compartir una muy elemental que hice. Las características de su diseño que, creo, la hacen interesante son:
El segundo punto se basa en el patrón Null Object: la idea es prescindir de null en el API para evitar el fatídico Null Pointer Exception. Más abajo lo vemos.
Como dije antes la librería es elemental, y sus limitaciones son:
API de XmlNode
Esta es la firma de los constructores:
Con estos métodos obtenemos el nombre (tag) y el valor (contenido) del nodo. Ambos retornarán null si es un Null Object.
Este método en cambio nunca retorna null y permite invocaciones encadenadas. El argumento debe ser un tag de un nodo hijo (inmediatamente relacionado con el actual). Veamos un ejemplo. Si creamos un XmlNode a partir de esto:
Podremos accederlo así:
Y también así:
Ahí vemos la invocación encadenada con nodos inexistentes. En nodoX nos quedó un Null Object. Para verificar si el XmlNode "está definido" o es nulo, tenemos también el siguiente método (inspirado en el homónimo de Option en Scala):
Así será más prolijo verificar si el nodo existe, en lugar de ver si getName() o getValue() retornan null.
El código
- Inmutabilidad
- Acceso a subnodos por invocaciones encadenadas, evitando NPE ante nodos inexistentes
El segundo punto se basa en el patrón Null Object: la idea es prescindir de null en el API para evitar el fatídico Null Pointer Exception. Más abajo lo vemos.
Como dije antes la librería es elemental, y sus limitaciones son:
- No sirve para "recorrer" el XML sino para obtener elementos conocidos
- No accede a los atributos de los elementos
API de XmlNode
Esta es la firma de los constructores:
public XmlNode(); public XmlNode(Node node); public XmlNode(Document doc);El primero es el Null Object, y si bien es un constructor público, lo normal será que sólo se utilice desde la misma clase y no desde afuera. El segundo toma un Node y el tercero un Document. Este último toma el nodo raiz del documento. La idea es que podamos partir de un documento o un nodo cualquiera, y olvidarnos de la diferenciación: lo que tenemos es un árbol de nodos.
public String getName();
public String getValue();
Con estos métodos obtenemos el nombre (tag) y el valor (contenido) del nodo. Ambos retornarán null si es un Null Object.
public XmlNode subNode(String tagName);
Este método en cambio nunca retorna null y permite invocaciones encadenadas. El argumento debe ser un tag de un nodo hijo (inmediatamente relacionado con el actual). Veamos un ejemplo. Si creamos un XmlNode a partir de esto:
<a> <b> <c>hola</c> <d>que tal</d> </b> </a>
Podremos accederlo así:
String nombre = nodo.getName(); // "a"
XmlNode nodoB = nodo.subNode("b"); // subnodo <b>
XmlNode nodoC = nodo.subNode("b").subNode("c"); // subnodo <c>
String valor1 = nodo.subNode("b").subNode("d").getValue(); // "que tal"
String valor2 = nodoC.getValue(); // "hola"
Y también así:
XmlNode nodoX = nodo.subNode("z").subNode("y").subNode("x");
String valor3 = nodoX.getValue(); // null
Ahí vemos la invocación encadenada con nodos inexistentes. En nodoX nos quedó un Null Object. Para verificar si el XmlNode "está definido" o es nulo, tenemos también el siguiente método (inspirado en el homónimo de Option en Scala):
public boolean isDefined();
Así será más prolijo verificar si el nodo existe, en lugar de ver si getName() o getValue() retornan null.
El código
import org.w3c.dom.Document;
import org.w3c.dom.Node;
import org.w3c.dom.NodeList;
public class XmlNode
{
protected Node node = null;
public XmlNode()
{
}
public XmlNode(Node node)
{
this.node = node;
}
public XmlNode(Document doc)
{
this.node = doc.getDocumentElement();
}
public XmlNode subNode(String tagName)
{
if(node != null)
{
NodeList nl = node.getChildNodes();
for(int i = 0; i < nl.getLength(); i++)
{
Node n = nl.item(i);
if(n.getNodeName().equals(tagName))
{
return new XmlNode(n);
}
}
}
return new XmlNode();
}
public String getName()
{
return !this.isDefined()? null : node.getNodeName();
}
public String getValue()
{
return !this.isDefined()? null : node.getFirstChild().getNodeValue();
}
public boolean isDefined()
{
return this.node != null;
}
}
sábado, 4 de abril de 2009
Una vuelta de tuerca más a la generación del diagrama
En el post anterior vimos cómo generar un diagrama Nassi-Schneiderman con tablas HTML. Hicimos un generador abstracto que nos permitiría hacer implementaciones alternativas, es decir, el diseño es modularizable.
En nuestro generador de HTML, el parámetro de tipo fue String, naturalmente, ya que generamos HTML con Strings. ¿Habrá sido una exageración parametrizar ese tipo? ¿Se les ocurre un generador que use un tipo diferente a String?
¿Y por qué no generar el diagrama como imagen? Un poco de AWT no hace mal. Mi nueva implementación usa java.awt.Image. Así es como se ve el nuevo diagrama (a partir del mismo código usado como entrada en el post anterior):
Creo que no hace falta explicar nada, el diagrama habla por sí mismo... sólo acotar que, en los IF que no tienen sección ELSE, en vez de dividir el cuadro por la mitad, hice un 90%/10% para evitar que se ocupe mucho espacio con la parte vacía. Faltan algunas mejoras, como incluir el nombre del módulo, los parámetros y la sección de declaraciones; y parametrizar el ancho de la imagen, que ahora está hardcodeado. En cuanto al alto, debería poder ser calculado según el largo del código, pero no lo resolví y por ahora también está hardcodeado. Definí las siguientes clases auxiliares inmutables, porque esto tiene uso intensivo de "puntos" y "áreas":
Los valores definidos en Area son útiles para que el código sea más claro. Si fueran funciones, el código se ejecutaría en cada invocación. Al ser val, el código se ejecuta a lo sumo una vez: el valor queda "recordado" para subsiguientes referencias. Y son lazy para que no se ejecuten hasta ser referenciados.
Con esto logramos que Area pueda ser usado como función, pasando dos áreas como argumentos. El resultado será un área que abarque completamente a esas dos. Esto fue necesario para, luego de procesar ambas secciones de un IF, obtener el área completa de la estructura (ya que cada sección tiene una altura independiente, según el código contenido). Finalmente, el generador:
El método abstracto imageWidth deberá ser implementado por quien use este trait, para indicar el ancho de imagen deseado. La altura en cambio, viene horriblemente hardcodeada de fábrica, por ahora. Obviamente esto no es todo, el trabajo sucio lo hace otra clase, a la que llamé GraphicsImageGenerator. El método generate crea la Image que vamos a retornar. Inicializa el correspondiente objeto Graphics y se lo pasa a una nueva instancia de GraphicsImageGenerator. Ésta también define un método generate pero requiere argumentos adicionales: aparte del Node, necesita saber con qué ancho cuenta para dibujarlo, y a partir de qué punto. Estos valores se calcularán para cada nodo a dibujar, aquí sólo se envían los valores iniciales que corresponden al nodo raíz del AST.
Y ahora sí, les dejo esa clase para que escudriñen si tienen ganas.
Nota: no incluyo la clase LineBreaker, que sirve para cortar un String en varios según sea necesario para que el texto entre en un ancho gráfico determinado.
trait Generator[T] {
def nullResult:T
def generate(o:Option[Node]):T = o match {
case Some(x) => generate(x)
case _ => nullResult
}
def generate(n:Node):T
}
En nuestro generador de HTML, el parámetro de tipo fue String, naturalmente, ya que generamos HTML con Strings. ¿Habrá sido una exageración parametrizar ese tipo? ¿Se les ocurre un generador que use un tipo diferente a String?
¿Y por qué no generar el diagrama como imagen? Un poco de AWT no hace mal. Mi nueva implementación usa java.awt.Image. Así es como se ve el nuevo diagrama (a partir del mismo código usado como entrada en el post anterior):
Creo que no hace falta explicar nada, el diagrama habla por sí mismo... sólo acotar que, en los IF que no tienen sección ELSE, en vez de dividir el cuadro por la mitad, hice un 90%/10% para evitar que se ocupe mucho espacio con la parte vacía. Faltan algunas mejoras, como incluir el nombre del módulo, los parámetros y la sección de declaraciones; y parametrizar el ancho de la imagen, que ahora está hardcodeado. En cuanto al alto, debería poder ser calculado según el largo del código, pero no lo resolví y por ahora también está hardcodeado. Definí las siguientes clases auxiliares inmutables, porque esto tiene uso intensivo de "puntos" y "áreas":
case class Point(x:Int, y:Int)
case class Area(start:Point, end:Point) {
lazy val width = end.x - start.x
lazy val height = end.y - start.y
lazy val middleX:Int = start.x + (width / 2)
lazy val middleTop = Point(middleX, start.y)
lazy val middleBottom = Point(middleX, end.y)
lazy val leftBottom = Point(start.x, end.y)
lazy val leftTop = start
lazy val rightTop = Point(end.x, start.y)
}
Los valores definidos en Area son útiles para que el código sea más claro. Si fueran funciones, el código se ejecutaría en cada invocación. Al ser val, el código se ejecuta a lo sumo una vez: el valor queda "recordado" para subsiguientes referencias. Y son lazy para que no se ejecuten hasta ser referenciados.
case object Area {
def apply(a1:Area, a2:Area):Area =
Area(Point(a1.start.x min a2.start.x, a1.start.y min a2.start.y),
Point(a1.end.x max a2.end.x, a1.end.y max a2.end.y))
}
Con esto logramos que Area pueda ser usado como función, pasando dos áreas como argumentos. El resultado será un área que abarque completamente a esas dos. Esto fue necesario para, luego de procesar ambas secciones de un IF, obtener el área completa de la estructura (ya que cada sección tiene una altura independiente, según el código contenido). Finalmente, el generador:
trait ImageGenerator extends Generator[Image] {
def imageWidth:Int
val totalWidth = imageWidth
val imageHeight = 800
def nullResult = null
def generate(n:Node):Image = {
val img = new BufferedImage(imageWidth, imageHeight, BufferedImage.TYPE_BYTE_BINARY)
val g = img.createGraphics
g.setPaint(Color.WHITE)
g.fillRect(0, 0, imageWidth, imageHeight)
g.setPaint(Color.BLACK)
(new GraphicsImageGenerator(g)).generate(n, totalWidth - 20, Point(10,20))
img
}
}
El método abstracto imageWidth deberá ser implementado por quien use este trait, para indicar el ancho de imagen deseado. La altura en cambio, viene horriblemente hardcodeada de fábrica, por ahora. Obviamente esto no es todo, el trabajo sucio lo hace otra clase, a la que llamé GraphicsImageGenerator. El método generate crea la Image que vamos a retornar. Inicializa el correspondiente objeto Graphics y se lo pasa a una nueva instancia de GraphicsImageGenerator. Ésta también define un método generate pero requiere argumentos adicionales: aparte del Node, necesita saber con qué ancho cuenta para dibujarlo, y a partir de qué punto. Estos valores se calcularán para cada nodo a dibujar, aquí sólo se envían los valores iniciales que corresponden al nodo raíz del AST.
Y ahora sí, les dejo esa clase para que escudriñen si tienen ganas.
class GraphicsImageGenerator(val g:Graphics2D)
{
val lineHeight = 11
val stmtSep = 3
val stmtHeight = 15
val loopThickness = 15
private def wrap(s:String, w:Int) = (new LineBreaker(s, w, g.getFontMetrics)).getSubtrings
private def widthOf(ss:List[String]) = ((ss map g.getFontMetrics.stringWidth) :\ 0)(_ max _)
private def drawRect(a:Area) = g.drawRect(a.start.x, a.start.y, a.end.x - a.start.x, a.end.y - a.start.y)
private def drawLine(p1:Point, p2:Point) = g.drawLine(p1.x, p1.y, p2.x, p2.y)
private def drawJustified(text:String, w:Int, p:Point, drawRect:Boolean)(fx:(Int, Int, Int) => Int) : Area = {
val substrings = wrap(text, w)
var y = p.y + stmtHeight
substrings foreach { s =>
g.drawString( s, fx(p.x, g.getFontMetrics.stringWidth(s), w), y)
y += lineHeight
}
Area(p, Point(p.x + w, y))
}
private def drawLeftJustified(text:String, w:Int, p:Point) = drawJustified(text, w, p, false) {
(x:Int, textWidth:Int, w:Int) => x
}
private def drawRightJustified(text:String, w:Int, p:Point) = drawJustified(text, w, p, false) {
(x:Int, textWidth:Int, w:Int) => (x + w) - textWidth
}
private def drawCentered(text:String, w:Int, p:Point) = drawJustified(text, w, p, true) {
(x:Int, textWidth:Int, w:Int) => (x + (w / 2)) - (textWidth / 2)
}
def generate(n:Node, w:Int, p:Point):Point =
n match {
case stmt:Stmt =>
drawLeftJustified(stmt.s, w, p).leftBottom
case loop:Loop =>
val areaLoop = drawLeftJustified(loop.head, w, p)
val startCode = Point(p.x + loopThickness + 2, areaLoop.end.y + 2)
val loopBodyBottom = generateCode(loop.body, (w - 4) - loopThickness, startCode)
val endPoint = Point(areaLoop.end.x, loopBodyBottom.y)
drawRect(Area(startCode, endPoint))
drawRect(Area(areaLoop.leftTop, endPoint))
Point(p.x, endPoint.y)
case cond:Cond =>
val areaCond = drawCentered(cond.c, w, p)
drawRect(areaCond)
val sepStart = if(cond.cElse.isEmpty) Point(p.x + (w * .9).asInstanceOf[Int], areaCond.end.y) else areaCond.middleBottom
val thenWidth = if(cond.cElse.isEmpty) (w * .9).asInstanceOf[Int] - 4 else (w/2) - 4
drawLine(areaCond.leftTop, sepStart)
drawLine(areaCond.rightTop, sepStart)
val pointThen = generateCode(cond.cThen, thenWidth, Point(p.x + 2, areaCond.end.y + 2))
val pointElse = generateCode(cond.cElse, (w/2) - 4, Point(p.x + 2 + (w/2), areaCond.end.y + 2))
val areaCode = Area(areaCond.leftBottom, Point(areaCond.end.x, pointThen.y max pointElse.y))
drawRect(areaCode)
drawLine(sepStart, Point(sepStart.x, areaCode.end.y))
areaCode.leftBottom
case block:Block =>
val codeEndPoint = generateCode(block.content, w - 4, Point(p.x + 2, p.y + 2))
val endPoint = block.exceps match {
case None => codeEndPoint
case Some(es) => generate(es, w - 4, codeEndPoint)
}
drawRect(Area(p, Point(p.x + w, endPoint.y)))
endPoint
case excepSection:ExcepSection =>
generateCode(excepSection.ee, w, p)
case whenExcep:WhenExcep =>
val areaWhen = drawLeftJustified(whenExcep.e, w - loopThickness, Point(p.x + loopThickness, p.y))
val endPoint = generateCode(whenExcep.body, w, Point(p.x, areaWhen.end.y))
drawLine(p, Point(p.x + w, p.y))
drawLine(Point(p.x + loopThickness, p.y), Point(p.x, p.y + loopThickness))
drawLine(Point((p.x + w) - loopThickness, p.y), Point(p.x + w, p.y + loopThickness))
endPoint
case module:Module => generate(module.body, w, p)
case _ => p
}
private def generateCode(codeList:List[Node], w:Int, p:Point):Point =
(p /: codeList) { (start:Point, c:Node) => generate(c, w, start) }
}
Nota: no incluyo la clase LineBreaker, que sirve para cortar un String en varios según sea necesario para que el texto entre en un ancho gráfico determinado.
Labels:
scala
jueves, 2 de abril de 2009
Parseando en Scala (6): Generando la salida
Nuestro propósito era parsear código PL/SQL, cosa que ya vimos en los posts anteriores, y generar como salida un diagrama estructurado.
Vamos a usar el siguiente código PL/SQL para probar el experimento. No importa lo que hace, es cualquier cosa que se me ocurrió.
Y vemos antes que nada el resultado que obtuve, tal como lo veo en el navegador. Como decíamos, es una versión HTML del diagrama Nassi-Schneidermann donde tenemos una representación visual de la estructura lógica.
Cada IF es un recuadro, con un encabezado que indica la condición (seguida de un signo de pregunta), y se divide en dos secciones: por convención, la izquierda corresponde a verdadero y la derecha a falso (THEN y ELSE respectivamente). Se puede ver cómo los IF encadenados con ELSIF quedaron resueltos como IFs anidados. Los ELSE vacíos también se dibujan, con "---". Los ciclos, como el FOR del ejemplo, son recuadros que muestran a la izquierda y en verde la cláusula correspondiente, y a la derecha el código. La sección EXCEPTION se muestra al final del recuadro del bloque debajo de una línea punteada.
Esto es generado por un módulo a partir del AST obtenido por el parseador. Pero el generador de HTML no tiene por qué ser la única opción de generación del diagrama, de hecho ya tengo un generador alternativo que comentaré más adelante. El punto es que para permitir la modularización, armamos una jerarquía de traits. El siguiente trait es el padre de los generadores.
Si recordamos, Node es el supertipo del modelo que estamos usando. El parámetro de tipo, T, es necesario porque para las posibles salidas pueden usarse diferentes tipos; de hecho esto es resultado de refactorizar mi código para permitir el generador alternativo en forma elegante. Con el método abstracto generate, requerimos que todos los generadores implementen la "transformación" de un Node cualquiera (de todos los posibles según el modelo), en algo de tipo T. Para la generación HTML ese tipo será String. Agregué una implementación default de generate que, en vez de tomar un Node toma un Option[Node]. Si se trata de un nodo definido, se deriva el control al método abstracto recién mencionado, y si no, a otro que define cómo se representa algo "vacío" para el tipo T. Esto me pareció práctico porque el modelo suele tener relaciones con opcionalidad: así puedo invocar indistintamente la generación de un nodo concreto o de un nodo que puede estar presente o no. Finalmente, el generador que hace todo el trabajo:
Definimos nullResult, para los nodos opcionales que no estén presentes, como un String vacío. Implementamos generate haciendo pattern matching sobre el nodo recibido. Contemplamos todos los tipos de nuestro modelo y generamos la representación HTML deseada para cada uno. Los detalles de la implementación puede que no sean del todo claros a primera vista, pero la idea sí, es bien simple.
El nodo Module siempre estará en la raiz del AST, por eso es el encargado de especificar el comienzo y el final del documento HTML. Entre una cosa y la otra, se producirán todas las invocaciones recursivas de generate para los nodos contenidos en el árbol. Los estilos CSS acá están hardcodeados, pero idealmente serían customizables.
Con esto finalizamos la serie, aunque me parece que habrá un bonus.
Vamos a usar el siguiente código PL/SQL para probar el experimento. No importa lo que hace, es cualquier cosa que se me ocurrió.
PROCEDURE MYPROC (Param IN NUMBER) IS
AUXVAR VARCHAR2(10) := NULL;
begin
IF Param = 1 THEN
AUXVAR = 'A';
ELSIF Param = 2 THEN
AUXVAR = 'B';
END IF;
if AUXVAR IS NOT NULL
THEN
FOR RECORD IN (SELECT * FROM MYTABLE WHERE FLD = AUXVAR)
LOOP
IF RECORD.EXPIRY <= SYSDATE
THEN
LOG_EXPIRED(RECORD.ID);
END IF;
END LOOP;
END IF;
dbms_output.put_line('END OF MYPROC WITH PARAM = ' || Param);
exception
when others then
dbms_output.put_line('OOPS!');
end;
Y vemos antes que nada el resultado que obtuve, tal como lo veo en el navegador. Como decíamos, es una versión HTML del diagrama Nassi-Schneidermann donde tenemos una representación visual de la estructura lógica.
Cada IF es un recuadro, con un encabezado que indica la condición (seguida de un signo de pregunta), y se divide en dos secciones: por convención, la izquierda corresponde a verdadero y la derecha a falso (THEN y ELSE respectivamente). Se puede ver cómo los IF encadenados con ELSIF quedaron resueltos como IFs anidados. Los ELSE vacíos también se dibujan, con "---". Los ciclos, como el FOR del ejemplo, son recuadros que muestran a la izquierda y en verde la cláusula correspondiente, y a la derecha el código. La sección EXCEPTION se muestra al final del recuadro del bloque debajo de una línea punteada.
Esto es generado por un módulo a partir del AST obtenido por el parseador. Pero el generador de HTML no tiene por qué ser la única opción de generación del diagrama, de hecho ya tengo un generador alternativo que comentaré más adelante. El punto es que para permitir la modularización, armamos una jerarquía de traits. El siguiente trait es el padre de los generadores.
trait Generator[T] {
def nullResult:T
def generate(o:Option[Node]):T = o match {
case Some(x) => generate(x)
case _ => nullResult
}
def generate(n:Node):T
}
Si recordamos, Node es el supertipo del modelo que estamos usando. El parámetro de tipo, T, es necesario porque para las posibles salidas pueden usarse diferentes tipos; de hecho esto es resultado de refactorizar mi código para permitir el generador alternativo en forma elegante. Con el método abstracto generate, requerimos que todos los generadores implementen la "transformación" de un Node cualquiera (de todos los posibles según el modelo), en algo de tipo T. Para la generación HTML ese tipo será String. Agregué una implementación default de generate que, en vez de tomar un Node toma un Option[Node]. Si se trata de un nodo definido, se deriva el control al método abstracto recién mencionado, y si no, a otro que define cómo se representa algo "vacío" para el tipo T. Esto me pareció práctico porque el modelo suele tener relaciones con opcionalidad: así puedo invocar indistintamente la generación de un nodo concreto o de un nodo que puede estar presente o no. Finalmente, el generador que hace todo el trabajo:
trait HTMLGenerator extends Generator[String] {
def nullResult = ""
def generate(n:Node):String = n match {
case Stmt(s) => s.replace("<","<") + "<br>\n"
case WhenExcep(e,body) => "<p>when " + e + " then<br>\n" +
(body map generate).mkString + "</p>\n"
case ExcepSection(s) => openCell("class=\"excsec\"") +
"<strong>exception</strong><br>\n" +
(for(w <- s) yield generate(w)).mkString +
closeCell
case Block(stmts, exceps) => "<table>" +
openCell +
(stmts map generate).mkString +
closeCell +
(if(exceps.isDefined) generate(exceps.get) else "") +
"</table><br>\n"
case Loop(h,body) => "<table><tr><td class=\"loop\">" +
h +
"</td>\n<td>" +
(body map generate).mkString +
"</td></tr></table>\n"
case Cond(c,ct,ce) => "<table>" +
openCell("colspan=\"2\" class=\"ifhead\"") +
c +
"<big><b> ?</b></big>" +
closeCell +
openCell("class=\"ifthen\"") +
(ct map generate).mkString +
"</td><td class=\"ifelse\">" +
(ce match {
case Nil => "---"
case xs => (xs map generate).mkString
}) +
closeCell +
"</table><br>\n"
case Module(t,n,p,r,v,b) => startHtml + "<h3>" + t + " " + n + "</h3>\n" +
(p match { case Some(x) => generate(x); case None => "" }) + "<br>\n" +
(if(v != Nil) "<table>" + openCell + (v map generate).mkString + closeCell + "</table>" else "") +
"<hr><br>" + generate(b) + endHtml
}
private val startHtml = "<html><head><style type=\"text/css\">\n" +
"table { width: 100%; border: solid thin }\n" +
".comment { color: darkgreen; font-style: italic }\n" +
".ifhead { background-color: moccasin; text-align: center }\n" +
".ifthen { border-top: solid thin; border-right: solid thin; }\n" +
".ifelse { border-top: solid thin; border-left: solid thin; }\n" +
".excsec { border-top: dashed thin; }\n" +
".loop { border-right: solid thin; background-color: MediumAquamarine; }\n" +
"</style></head><body>\n"
private def openCell(modif:String) = "<tr><td " + modif + ">"
private def openCell:String = openCell("")
private val closeCell = "</td></tr>"
private val endHtml = "</body></html>"
}
Definimos nullResult, para los nodos opcionales que no estén presentes, como un String vacío. Implementamos generate haciendo pattern matching sobre el nodo recibido. Contemplamos todos los tipos de nuestro modelo y generamos la representación HTML deseada para cada uno. Los detalles de la implementación puede que no sean del todo claros a primera vista, pero la idea sí, es bien simple.
El nodo Module siempre estará en la raiz del AST, por eso es el encargado de especificar el comienzo y el final del documento HTML. Entre una cosa y la otra, se producirán todas las invocaciones recursivas de generate para los nodos contenidos en el árbol. Los estilos CSS acá están hardcodeados, pero idealmente serían customizables.
Con esto finalizamos la serie, aunque me parece que habrá un bonus.
Labels:
scala
Suscribirse a:
Entradas (Atom)


