universes: lightweight ownership for jml werner dietl peter müller

Universes: Lightweight Ownership for JML

Werner DietlPeter Müller

Universe Type System

Organiza los objetos en ownership contexts.

El owner de un objeto se determina cuando se hace un new del mismo.

Un ownership context es un conjunto de objetos con el mismo owner.

El root ownership context es el conjunto de todos los objetos que no tienen owner.

Los ownership contexts conforman un árbol

Universe Type System

Propiedad owner-as-modifier: Un objeto X puede ser referenciado por

cualquier otro objeto. Todas las referencias que están fuera

del ownership context en el que está X, deben ser referencias read only.

X puede ser modificado sólo por objetos con el mismo owner o por el owner de X.

Universe Type System

Tipos de referencias: peer: referencias entre objetos con el mismo

owner. rep: referencias de un objeto X a otro objeto

cuyo owner es X. readonly: referencias entre objetos en

cualquier contexto.

Toda expresión que en runtime es una referencia debe tener declarado su respectivo modificador de ownership (por default, es peer).

Universe Type System

Tipos: Abarcan tipos primitivos de Java, Clases (e

Interfaces) y Arrays. Para Clases, son pares (modificador-ownership,

nombre de Clase). Para Arrays, dos modificadores: uno para el objeto

Array y otro para los elementos del array.

Ejemplos: rep T: tipo referencias a objetos de la clase T cuyo

owner es this. rep readonly T[]: tipo de referencias a Arrays

cuyo owner es this y sus elementos son instancias de T en contextos arbitrarios.

Universe Type System

Subtipos: Dos tipos peer, rep o readonly son subtipos si sus

correspondientes clases en Java son subtipos. También, todo tipo peer o rep es subitpo del tipo readonly de la misma clase Java.

Dos tipos de Array con el mismo modificador de ownership son subtipos si los tipos de sus elementos son subtipos.

Ejemplo: rep peer Object[] es subtipo de rep readonly Object[], dado que peer Object es subtipo de readonly Object.

Universe Type System Reglas de tipos:

Asignación: El tipo de la expresión del lado derecho tiene

que ser subtipo del tipo del lado izquierdo.

Creación: Expresión de la forma new peer T(…) o new rep T(…), donde T es el nombre de una clase.

En el caso de Arrays, hay dos modificadores. El primero puede ser peer o rep, mientras que el segundo peer o readonly.

En el caso de Arrays multidimensionales, todas las subdimensiones deben tener el mismo tipo.

Universe Type System

Reglas de tipos: Acceso a campos (x.f):

Si x y f son ambos peer, se tiene que: x y this tienen el mismo owner. x.f y x tienen el mismo owner (y que this). Luego, x.f tambien tiene el modificador peer.

Si f es rep, entonces this.f tiene el modificador rep.

Universe Type System

Reglas de tipos: Acceso a campos (x.f):

Si x es rep y f es peer se tiene que: El owner del objeto referenciado por x es this. El objeto referenciado por x.f tiene el mismo owner

que x. Luego, el owner del objeto referenciado por x.f es

this, y en consecuencia tiene el modificador rep.

En todos los casos restantes, no se puede determinar sintácticamente si el owner de x.f es this o si tiene el mismo owner que this. Por lo tanto x.f tiene el modificador readonly.

Universe Type System

Reglas de tipos: Llamado a métodos:

Análogamente al acceso a campos, los tipos de los parámetros y el resultado del método deben interpretarse respecto de la expresión que recibe la llamada.

Ejemplo: void foo(peer T p), indica que p tiene que

tener el mismo owner que el objeto sobre el cuál se ejecuta foo. Si se llama a foo sobre una expresión de tipo rep, entonces también p debe ser de tipo rep.

Universe Type System

Reglas de tipos: Llamado a métodos:

Para x.m(… ai …): El tipo del parametro ai debe ser un subtipo

de la combinación de x y la declaración del parámetro pi en la signatura del método m.

1. El tipo de la expresión de la llamada es la combinación de los tipos de x y el resultado declarado en la signatura de m.

Si algún parámetro en la signatura de m es de tipo rep, m sólo puede ser llamado desde this.

Universe Type System

Invariante: El chequeo de tipos se hace línea por línea.

Ejemplo:

public class Difference {/*@ rep @*/ Object o;public void bar() {

o = new /*@ peer @*/ Object();

o = new /*@ rep @*/ Object();}

}

13

JML (Java Modeling Language)

Lenguaje de especificación de comportamientos para Java.

Similar a la idea de contratos en Eiffel o model-based specification.

requires, ensures, invariant, etc. Combinado con universe permite

establecer relaciones de ownership entre distintos objetos.

13

14

JML - Ejemplo

public class Producer {/*@ rep readonly*/ Product[] buf;int n;/*@ peer */ Consumer cons;

public Producer() {buf= new /*@ rep readonly*/ Product[10];

}

public void produce(/*@ peer */ Product p) {buf[n]= p;n= (n+1) % buf.length;

}}

public class Consumer {...public /*@ peer */ Product consume() {

return (/*@ peer */ Product) buf[n];}}

15

JML - Ejemplo

public class Producer {/*@ rep readonly */ Product[] buf;int n;/*@ peer */ Consumer cons;

public Producer() {buf= new /*@ rep readonly */ Product[10];

}

public void produce(/*@ peer */ Product p) {buf[n]= p;n= (n+1) % buf.length;

}}

public class Consumer {...public /*@ peer */ Product consume() {

return (/*@ peer */ Product) buf[n];}}

16

JML - Ejemplo

public class Producer {/*@ rep readonly */ Product[] buf;int n;/*@ peer */ Consumer cons;

/*@ (\forall int i; 0 <= i && i < buf.length; @ buf[i] == null || buf[i].owner == this.owner @*/

public Producer() {buf= new /*@ rep readonly */ Product[10];

}

public void produce(/*@ peer */ Product p) {buf[n]= p;n= (n+1) % buf.length;

}}

17

JML - Ejemplopublic class Consumer {/*@ readonly readonly */ Product[] buf;int n;/*@ peer */ Producer pro;

/*@ invariant pro!=null && pro.con==this && @ pro.buf=buf; @*/

public Consumer(/*@ peer */ Producer p) {buf= p.buf;pro= p;p.con= this;

}

public /*@ peer */ Product consume() {n= (n+1) % buf.length;return (/*@ peer */ Product) buf[n];

}}

18

JML (ejemplo)

El downcast no arrojará excepciones en runtime: Por el invariant de Producer

pro.buf[n].owner == pro.owner Por el de Consumer

buf == pro.buf

entonces dado el tipo de pro en Consumer

pro.owner == this.owner

18

19

Otro ejemplo - Iteradorespublic class Iter { /*@ peer @*/ LinkedList list; /*@ readonly @*/ Node pos;

//@ invariant pos != null && pos.owner == list; public Iter(/*@ peer @*/ LinkedList l) { list = l; pos = l.first;}

public void setValue(/*@ readonly @*/ Object e) { list.set(pos, e); }

public void advance() {pos= pos.next;}}

20

Otro ejemplo - Iteradorespublic class LinkedList { /*@ rep @*/ Node first;

//@ requires np != null && np.owner == this; void set(/*@ readonly @*/ Node np, /*@ readonly @*/ Object e) { /*@ rep @*/ Node n = (/*@ rep @*/ Node) np; n.elem = e; } public /*@ pure @*/ boolean equals(/*@ readonly @*/ Object l) { if (!(l instanceof /*@ readonly @*/ LinkedList)) return false; /*@ readonly @*/ Node f1 = first; /*@ readonly @*/ Node f2 =((/*@ readonly @*/ LinkedList)l).first; while (f1 != null && f2 != null && f1.elem == f2.elem) { f1 = f1.next; f2 = f2.next; } return f1 == null && f2 == null; } ...}

21

Otro ejemplo - Iteradores

No puede realizarse sin interacción entre Universe y JML. Claramente, list.set(np,e) requiere

que this tenga el ownership de np. Pero no puede declararse /*@ rep */ np, porque no sería posible invocar l.set(np,e) (un parámetro rep en una función hace que la función sea invocable sólo sobre ese objeto).

21

22

Otro ejemplo - Iteradores

Solución: establecer el ownership en los requires de JML.

El constructor de Iter mantiene el invariante al hacer pos= l.first.

22

23

En resumen

Universe introduce un método de chequeo de ownership owner-as-modifier en programas Java.

Este paper presenta una extensión del método mediante JML para introducir relaciones de ownership entre objetos que no están directamente relacionados, permitiendo features tales como downcasts y shared-ownership.

23

24

En resumen

La integración con programas Java existentes es trivial (defaulting a peer). Backward-compatibility se obtiene a través de encapsulación en comentarios.

Todavía no tiene mecanismos de ownership-inference. No es trivial, especialmente por las cuestiones de pasaje de parámetros.

24

Universes: Lightweight Ownership for JML

Werner DietlPeter Müller