hephaestus-compiler-project / hephaestus Goto Github PK

View Code? Open in Web Editor NEW

46.0 46.0 8.0 35.86 MB

A framework for testing compilers' type checkers

Home Page: https://hephaestus-compiler-project.github.io/

License: GNU General Public License v3.0

Python 97.90% Shell 1.40% Groovy 0.26% Java 0.45%

hephaestus's People

Contributors

Stargazers

Watchers

Forkers

alexisthedev chamitro unshorn vitekkor sainiaditya1 hephaestus-compiler-project marmac02

hephaestus's Issues

Remove type information from Parameterized Types when possible

We should remove type arguments from Parameterized Types when it's possible.

class A<T> (val x: T)
val a = A<String>("a") // Should be val a = A("a")

class A<T>
val a: A<String> = A<String>() // Should be val a: A<String> = A()

fun foo(x: A<String>) = x
foo(A<String>()) // Should be foo(A())

fun foo(): A<String> = A<String>("a") // should be fun foo(): A<String> = A("a")

To remove type arguments, all type parameters must be inferred with one of the previous ways.
To implement that, we will add a can_infer_type_args field in the ParameterizedType class.

TODO:

FieldDeclaration (Case 1) a81cb77
VariableDeclaration (Case 2) 2ce83d1
FunctionCall (Case 3) 0cf6968
FunctionReturnStmt (Case 4) 3f8d155
Add new substitution 074a9bf

Ideas for the soundness mutation

Add parent field in nodes

It is not trivial to add it, it may needs a broad refactoring.

Refactor of kotlin translator

We should not use str() and get_name in translator

Add support for parameterized functions

Improve the performance of the tool

We need to start making optimizations, because as we start adding more feature the performance of the tool drops.

Known implementation bugs

Right now, around 50 out of 1000 iterations fail.

Kotlin errors (False Positives)

error: unresolved reference: foo -- foo does not exist, we call it as a function or constructor (e.g., foo("1", 1)
error: unresolved reference: X -- For example,fun delbert(hubcaps: Sniggered<Byte, Int>, harangued: Mace<E, X, R>): Any
error: unresolved reference: g -- g does not exist (e.g., g(libraries, Gertrude()))
error: 'mayfly' overrides nothing --

class Sizzle<in I>

open abstract class Foo() {
    open abstract fun buz(p: Sizzle<Long>): Number
}

open class Bar(): Foo() {
    open override fun buz(p: Sizzle<Number>): Number = 10
}

error: expecting ')' -- Missing constructor's name

  fun diagnosis(contrasts: Assertion<Char>, troopers: Roof<Tompkins>): Roof<Tompkins> 
{
    val faculties = Flexes("tanked")
    rifle()
    return (true, Tompkins(Flexes("graving"), faculties))
  }

error: operator '===' cannot be applied to 'Int' and 'String'
error: return type of 'buz' is not a subtype of the return type of the overridden member 'public abstract fun buz(): Sizzle defined in Foo'

class Sizzle<I>(val x: I)

open abstract class Foo() {
    open abstract fun buz(): Sizzle<Number>
}

open abstract class Bar(): Foo() {
    open override fun buz() = Sizzle(4)
}

Kotlin errors (True Positives) -- Confirmed bugs that still crash frequently
- error: type mismatch: inferred type is Any but Long was expected: nested ifs in return statement of a function.
- error: type mismatch: inferred type is Any but String was expected: smart cast + function closure
Program errors

TypeError: You cannot call 'is_subtype()' in an AbstractType

  File \"check-type-system/src/transformations/parameterized.py\", line 376, in visit_field_decl
    node.field_type = self._use_type_parameter(
  File \"check-type-system/src/transformations/parameterized.py\", line 256, in _use_type_parameter
    tp.type_param = create_type_parameter(
  File \"check-type-system/src/transformations/parameterized.py\", line 48, in create_type_parameter
    bound = utils.random.choice(list(filter(
  File \"check-type-system/src/transformations/parameterized.py\", line 40, in bounds_filter
    if tparam.bound and not targ.is_subtype(tparam.bound):
  File \"check-type-system/src/ir/types.py\", line 45, in is_subtype
    raise TypeError(\"You cannot call 'is_subtype()' in an AbstractType\")
TypeError: You cannot call 'is_subtype()' in an AbstractType

TypeError: You cannot call 'is_subtype()' in an AbstractType (Known problem in which we have type parameters as type arguments of a ParameterizedType

  File \"/typesystems/check-type-system/src/transformations/substitution.py\", line 204, in visit_class_decl
    new_node = super().visit_class_decl(node)
  File \"/typesystems/check-type-system/src/ir/visitors.py\", line 145, in visit_class_decl
    return self._visit_node(node)
  File \"/typesystems/check-type-system/src/ir/visitors.py\", line 220, in _visit_node
    new_children.append(c.accept(self))
  File \"/typesystems/check-type-system/src/ir/node.py\", line 4, in accept
    return visitor.visit(self)
  File \"/typesystems/check-type-system/src/ir/visitors.py\", line 42, in visit
    return visitor(node)
  File \"/typesystems/check-type-system/src/transformations/substitution.py\", line 313, in visit_func_decl
    transform = self._type_widening(
  File \"/typesystems/check-type-system/src/transformations/substitution.py\", line 173, in _type_widening
    superclasses = tu.find_supertypes(decl.get_type(), self.types,
  File \"/typesystems/check-type-system/src/ir/type_utils.py\", line 77, in find_supertypes
    return _find_types(etype, types, get_subtypes=False,
  File \"/typesystems/check-type-system/src/ir/type_utils.py\", line 58, in _find_types
    t_set.update(_construct_related_types(etype, types, get_subtypes))
  File \"/typesystems/check-type-system/src/ir/type_utils.py\", line 14, in _construct_related_types
    t_args = _find_types(etype.type_args[i], types,
  File \"/typesystems/check-type-system/src/ir/type_utils.py\", line 58, in _find_types
    t_set.update(_construct_related_types(etype, types, get_subtypes))
  File \"/typesystems/check-type-system/src/ir/type_utils.py\", line 14, in _construct_related_types
    t_args = _find_types(etype.type_args[i], types,
  File \"/typesystems/check-type-system/src/ir/type_utils.py\", line 65, in _find_types
    t_set = {st for st in t_set if st.is_subtype(bound)}
  File \"/typesystems/check-type-system/src/ir/type_utils.py\", line 65, in <setcomp>
    t_set = {st for st in t_set if st.is_subtype(bound)}
  File \"/typesystems/check-type-system/src/ir/types.py\", line 45, in is_subtype
    raise TypeError(\"You cannot call 'is_subtype()' in an AbstractType\")
TypeError: You cannot call 'is_subtype()' in an AbstractType

AttributeError: 'SimpleClassifier' object has no attribute 'type_args'

  File \"check-type-system/src/transformations/substitution.py\", line 99, in visit_new
    return generate()
  File \"check-type-system/src/transformations/substitution.py\", line 98, in <lambda>
    generate = generators.get(sub_c, lambda: self.generate_new(sub_c))
  File \"check-type-system/src/transformations/substitution.py\", line 56, in generate_new
    return self._generate_new(class_decl, etype, params_map)
  File \"check-type-system/src/transformations/substitution.py\", line 41, in _generate_new
    args=[self.generator.generate_expr(
  File \"check-type-system/src/transformations/substitution.py\", line 41, in <listcomp>
    args=[self.generator.generate_expr(
  File \"check-type-system/src/generators/generator.py\", line 645, in generate_expr
    return ut.random.choice(gens)(expr_type)
  File \"check-type-system/src/generators/generator.py\", line 587, in <lambda>
    lambda x: self.gen_new(x, only_leaves, subtype),
  File \"check-type-system/src/generators/generator.py\", line 454, in gen_new
    args.append(self.generate_expr(
  File \"check-type-system/src/generators/generator.py\", line 645, in generate_expr
    return ut.random.choice(gens)(expr_type)
  File \"check-type-system/src/generators/generator.py\", line 587, in <lambda>
    lambda x: self.gen_new(x, only_leaves, subtype),
  File \"check-type-system/src/generators/generator.py\", line 454, in gen_new
    args.append(self.generate_expr(
  File \"check-type-system/src/generators/generator.py\", line 645, in generate_expr
    return ut.random.choice(gens)(expr_type)
  File \"check-type-system/src/generators/generator.py\", line 587, in <lambda>
    lambda x: self.gen_new(x, only_leaves, subtype),
  File \"check-type-system/src/generators/generator.py\", line 445, in gen_new
    else {t_p: etype.type_args[i]
  File \"check-type-system/src/generators/generator.py\", line 445, in <dictcomp>
    else {t_p: etype.type_args[i]
AttributeError: 'SimpleClassifier' object has no attribute 'type_args'

IndexError: list index out of range -- We must handle the case where return type is a TypeParameter

  File \"check-type-system/src/transformations/substitution.py\", line 301, in visit_func_decl
    var_decl = self.generate_variable_declaration(\"ret\",
  File \"check-type-system/src/transformations/substitution.py\", line 217, in generate_variable_declaration
    expr = self.generator.generate_expr(etype, only_leaves=True)
  File \"check-type-system/src/generators/generator.py\", line 645, in generate_expr
    return ut.random.choice(gens)(expr_type)
  File \"check-type-system/src/generators/generator.py\", line 587, in <lambda>
    lambda x: self.gen_new(x, only_leaves, subtype),
  File \"check-type-system/src/generators/generator.py\", line 439, in gen_new
    if etype2 == etype else self._get_subclass(etype))
  File \"check-type-system/src/generators/generator.py\", line 422, in _get_subclass
    return ut.random.choice(
  File \"check-type-system/src/utils.py\", line 84, in choice
    return self.r.choice(choices)
  File \"/usr/lib/python3.9/random.py\", line 346, in choice
    return seq[self._randbelow(len(seq))]
IndexError: list index out of range

IndexError: list index out of range

  File \"check-type-system/src/transformations/substitution.py\", line 99, in visit_new
    return generate()
  File \"check-type-system/src/transformations/substitution.py\", line 98, in <lambda>
    generate = generators.get(sub_c, lambda: self.generate_new(sub_c))
  File \"check-type-system/src/transformations/substitution.py\", line 65, in generate_new
    return self._generate_new(class_decl, class_type, params_map)
  File \"check-type-system/src/transformations/substitution.py\", line 41, in _generate_new
    args=[self.generator.generate_expr(
  File \"check-type-system/src/transformations/substitution.py\", line 41, in <listcomp>
    args=[self.generator.generate_expr(
  File \"check-type-system/src/generators/generator.py\", line 645, in generate_expr
    return ut.random.choice(gens)(expr_type)
  File \"check-type-system/src/generators/generator.py\", line 587, in <lambda>
    lambda x: self.gen_new(x, only_leaves, subtype),
  File \"check-type-system/src/generators/generator.py\", line 439, in gen_new
    if etype2 == etype else self._get_subclass(etype))
  File \"check-type-system/src/generators/generator.py\", line 422, in _get_subclass
    return ut.random.choice(
  File \"check-type-system/src/utils.py\", line 84, in choice
    return self.r.choice(choices)
  File \"/usr/lib/python3.9/random.py\", line 346, in choice
    return seq[self._randbelow(len(seq))]
IndexError: list index out of range

IndexError: list index out of range

  File \"check-type-system/src/transformations/type_creation.py\", line 205, in visit_program
    self._new_class = self.create_new_class(class_decl)
  File \"check-type-system/src/transformations/type_creation.py\", line 344, in create_new_class
    [self._create_super_instantiation(class_decl, class_type)],
  File \"check-type-system/src/transformations/type_creation.py\", line 286, in _create_super_instantiation
    args.append(self.generator.generate_expr(
  File \"check-type-system/src/generators/generator.py\", line 645, in generate_expr
    return ut.random.choice(gens)(expr_type)
  File \"check-type-system/src/generators/generator.py\", line 587, in <lambda>
    lambda x: self.gen_new(x, only_leaves, subtype),
  File \"check-type-system/src/generators/generator.py\", line 439, in gen_new
    if etype2 == etype else self._get_subclass(etype))
  File \"check-type-system/src/generators/generator.py\", line 422, in _get_subclass
    return ut.random.choice(
  File \"check-type-system/src/utils.py\", line 84, in choice
    return self.r.choice(choices)
  File \"/usr/lib/python3.9/random.py\", line 346, in choice
    return seq[self._randbelow(len(seq))]
IndexError: list index out of range

IndexError: list index out of range

  File \"/src/transformations/parameterized.py\", line 359, in visit_program
    node = self._analyse_selected_class(self._selected_class_decl)
  File \"/src/transformations/parameterized.py\", line 318, in _analyse_selected_class
    node = self._select_type_params(node)
  File \"/src/transformations/parameterized.py\", line 300, in _select_type_params
    node = self.visit_class_decl(node)
  File \"/src/transformations/base.py\", line 8, in inner
    new_node = visit(self, node)
  File \"/src/transformations/parameterized.py\", line 366, in visit_class_decl
    return super().visit_class_decl(node)
  File \"/src/ir/visitors.py\", line 145, in visit_class_decl
    return self._visit_node(node)
  File \"/src/ir/visitors.py\", line 220, in _visit_node
    new_children.append(c.accept(self))
  File \"/src/ir/node.py\", line 4, in accept
    return visitor.visit(self)
  File \"/src/ir/visitors.py\", line 42, in visit
    return visitor(node)
  File \"/src/transformations/base.py\", line 8, in inner
    new_node = visit(self, node)
  File \"/src/transformations/parameterized.py\", line 414, in visit_func_decl
    new_node = super().visit_func_decl(node)
  File \"/src/ir/visitors.py\", line 160, in visit_func_decl
    return self._visit_node(node)
  File \"/src/ir/visitors.py\", line 220, in _visit_node
    new_children.append(c.accept(self))
  File \"/src/ir/node.py\", line 4, in accept
    return visitor.visit(self)
  File \"/src/ir/visitors.py\", line 42, in visit
    return visitor(node)
  File \"/src/transformations/parameterized.py\", line 390, in visit_param_decl
    node.param_type = self._use_type_parameter(
  File \"/src/transformations/parameterized.py\", line 260, in _use_type_parameter
    tp.type_param = create_type_parameter(
  File \"/src/transformations/parameterized.py\", line 52, in create_type_parameter
    bound = utils.random.choice(list(filter(
  File \"/src/utils.py\", line 84, in choice
    return self.r.choice(choices)
  File \"/usr/lib/python3.9/random.py\", line 346, in choice
    return seq[self._randbelow(len(seq))]
IndexError: list index out of range

TypeError: You cannot call 'is_subtype()' in an AbstractType (Known problem in which we have type parameters as type arguments of a ParameterizedType

  File \"/src/transformations/substitution.py\", line 81, in visit_new
    subclasses = tu.find_subtypes(node.class_type, self.types)
  File \"/src/ir/type_utils.py\", line 71, in find_subtypes
    return _find_types(etype, types, get_subtypes=True,
  File \"/src/ir/type_utils.py\", line 58, in _find_types
    t_set.update(_construct_related_types(etype, types, get_subtypes))
  File \"/src/ir/type_utils.py\", line 18, in _construct_related_types
    t_args = _find_types(etype.type_args[i], types,
  File \"/src/ir/type_utils.py\", line 58, in _find_types
    t_set.update(_construct_related_types(etype, types, get_subtypes))
  File \"/src/ir/type_utils.py\", line 14, in _construct_related_types
    t_args = _find_types(etype.type_args[i], types,
  File \"/src/ir/type_utils.py\", line 65, in _find_types
    t_set = {st for st in t_set if st.is_subtype(bound)}
  File \"/src/ir/type_utils.py\", line 65, in <setcomp>
    t_set = {st for st in t_set if st.is_subtype(bound)}
  File \"/src/ir/types.py\", line 45, in is_subtype
    raise TypeError(\"You cannot call 'is_subtype()' in an AbstractType\")
TypeError: You cannot call 'is_subtype()' in an AbstractType

Implement a parser from kotlin to our AST

We can use ANTLR (https://github.com/Kotlin/kotlin-spec/tree/release/grammar/src/main/antlr)

Create deploy scripts for running experiments in workstations

enhancement: in certain cases permit smart casts for parameterized types

Example:

open class In<T>
class Child<T> : In<T>()

fun test(t: In<String>) {
    if (t is Child) {
        val child: Child<String> = t
    }
}

enhancement: Introduce type parameters in more places

We need to introduce type parameters in more places.

Examples

//Example 1
class X<T1: T2, T2> // bound

// Example 2
class X<T1: Y<T2>, T2> // bound and parameterized class

// Example3
class Y<T, Y>(val x: Y) {
   fun foo(): T {
      TODO()
   }
}
class X<T>(val x: Y<T, T>) {
  fun bar(): T {
      return x.foo()
  }
}

... and more

Add a dataset of test cases to be used as seed programs

Find tests from the kotlin repository for old bugs.
Convert them to our AST and add an option to use them as seeds instead of generating new programs.

Known Implementation Errors

This is a list of rare, known implementation errors that are difficult to be fixed.

error: type mismatch: inferred type is Int but Short was expected -- TypeArgumentErasureSubstitution

class X<T>(val x: T)

fun main () {
    val a2: X<Short> = X(X(50).x) 
}

error: type mismatch: inferred type is {Comparable<CapturedType(*)> & Number} but Short was expected -- TypeArgumentErasureSubstitution

class Paroling<N>(val burying: N)

fun buxom(warned: Paroling<Short>) {}

fun main () {
    val bizarre: Short = 10
    buxom(Paroling<Short>(if (true) bizarre else Paroling(62).burying))
}

enhancement: update_type takes too long some times

Implements transformations (mutations) to inject faults

To test them out, we will inject many faults, and we'll check how many faults the compiler reports.

Add support for higher-order functions

Including

Lambda expressions
Function types (and operations on function types)
Function references

Implementation errors related to Type Arguments Erasure

error: type mismatch: inferred type is Int but Short was expected -- TypeArgumentErasureSubstitution

class X<T>(val x: T)

fun main () {
    val a2: X<Short> = X(X(50).x) 
}

error: type mismatch: inferred type is {Comparable<CapturedType(*)> & Number} but Short was expected -- TypeArgumentErasureSubstitution

class Paroling<N>(val burying: N)

fun buxom(warned: Paroling<Short>) {}

fun main () {
    val bizarre: Short = 10
    buxom(Paroling<Short>(if (true) bizarre else Paroling(62).burying))
}

error: type mismatch: inferred type is B<C> but B<A> was expected -- ValueSubstitution

open class A
open class B<T: A>(var x: T)
class C: A()
fun foo() = B(C())

fun main () {
    val x: B<A> = B(C()) // compiles
    val y: B<A> = foo()  // error
}

FP in incorrect substitution groovy

Implementation errors

For a more comprehensive list look at #10.

unresolved reference: xxx return xxx .... (6ddf542)
unexpected tokens (use ';' to separate expressions on the same line)
unresolved reference: H open fun retracing(foo: Leathers<H>)
not enough information to infer type variable H -- Type Substitution

// shred's type changed from Huddled<Double, Double> to Tragedian
fun caterings(shred: Tragedian) =
  Syringed(Aymara(), Huddled<Any, Double>())

fun sugarier(lanky: Any): Syringed
{
  var cinches: Syringed = caterings(Huddled()) // not enough information to infer type variable H
  return cinches
}

return type of 'blackish' is not a subtype of the return type of the overridden member -- Supertype Creator (fb2dc22)

open class Ralph<in E>(open var beautify: E) {}

// Adds Picasso
open class Picasso() {
  open fun blackish(): Ralph<Number> =
    Ralph(-67)
}

class Graphic(): Picasso() {
override fun blackish() =
  Ralph(-67)
}

error: class 'Slated' is not abstract and does not implement abstract member public abstract fun heralds
error: operator '!=' cannot be applied to 'Long' and 'Boolean'
error: not enough information to infer type variable Z It happens after TypeArgumentErasureSubstitution, but it happens because we don't update the context somewhere.

Replay functionality

In order to effectively debug the programs, we need to implement a proper replay functionality.

To do so, we need to implement the following:

An option --random-seed to give a random seed to random generator.
Replay should repeat the transformations performed in the last run with exactly the same order.
The initial_program.kt must correspond to the program produced by the generator and not the previous transformation.

Boost the performance of the tool

The bottleneck of our tool is the time spent on compiler.
We can boost the performance of testing if we feed multiple files to compiler.
For example, compiling 30 programs at once takes only 15 seconds, while compiling 30 programs one at a time takes roughly 2 minutes.

This is a great improvement. So we need to adapt the tool for supporting compilation of multiple files.

Add support for Scala

Important, but basic language features

These are some basic language features that we can implement before proceeding with more advanced features such as higher-order functions and parameterized functions.

implementation bug: Parameterized transformation (return type of function)

Initial program:

class Screwing extends Harps {
    Number clicked(Integer brimful) {
        brimful
    }
}

class Harps {
    Number clicked(Integer brimful) {
        brimful
    }
}

After the transformation (when T have been selected to be used as the type of brimful):

class Screwing extends Harps<Integer> {
    Number clicked(Integer brimful) {
        brimful
    }
}

class Harps<T> {
    T clicked(T brimful) {
        brimful
    }
}

Whereas the return type of Harps.clicked shouldn't change because it has different type from brimful.

Add support for Groovy

Command line option to select language and refactoring of executor module.
Groovy Translator.
Groovy Types.
Refactoring of IR where is needed.
Refactoring of generator and transformations.

Make transformations (mutations) as permissive as possible

Parameterized (_create_parameterized_type)
Add subtype/supertype option in update_type (type_utils). For example, var_type and inferred_type of VariableDecleration can be supertypes of new_type.
substitution--smart cast

Refactoring of generator

We should apply a refactoring to the generator to use a table with possibilities instead of random.bool. Specifically, this table should include all supported features. We need that functionality for the following reasons.

For disabling features that a language cannot support in a fine-grained way.
For adding the ability for swarm testing.
It will be helpful for evaluation.
To minimise the effort of implementing a new language to (1) implementing a translator, (2) specifying this table for the new language, (3) specifying built-in types.

Compute transformation schedule based on a probabilistic function

Some transformations are not meaningful if they are applied before others. For example, it's meaningless to apply TypeArgumentErasure before ParameterizedSubstituion. Similarly, ValueSubstitution and TypeWidening are only meaningful if they are already some parent-child classes in the program.

Our tool needs to select the next transfromation to apply based on a specific probabilistic function. This function should consider the transformation that have been applied so far.

Java Bugs

https://bugs.openjdk.java.net/browse/JDK-8267220
https://bugs.openjdk.java.net/browse/JDK-8267610
https://bugs.openjdk.java.net/browse/JDK-8268159
https://bugs.openjdk.java.net/browse/JDK-8269348 -- not an issue
https://bugs.openjdk.java.net/browse/JDK-8269386 -- not an issue
https://bugs.openjdk.java.net/browse/JDK-8269586 -- Commented as not a bug
https://bugs.openjdk.java.net/browse/JDK-8269737 -- not an issue
https://bugs.openjdk.java.net/browse/JDK-8269738
https://bugs.openjdk.java.net/browse/JDK-8272077 -- not an issue
https://bugs.openjdk.java.net/browse/JDK-8274183
https://bugs.openjdk.java.net/browse/JDK-8276081

Add handler to stop testing with Ctr+C

Recommend Projects

React

A declarative, efficient, and flexible JavaScript library for building user interfaces.
Vue.js

🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript

TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
TensorFlow

An Open Source Machine Learning Framework for Everyone
Django

The Web framework for perfectionists with deadlines.
Laravel

A PHP framework for web artisans
D3

Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

javascript

JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
web

Some thing interesting about web. New door for the world.
server

A server is a program made to process requests and deliver data to clients.
Machine learning

Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Visualization

Some thing interesting about visualization, use data art
Game

Some thing interesting about game, make everyone happy.

Recommend Org

Facebook

We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft

Open source projects and samples from Microsoft.
Google

Google ❤️ Open Source for everyone.
Alibaba

Alibaba Open Source for everyone
D3

Data-Driven Documents codes.
Tencent

China tencent open source team.