Boa: Implement the `instanceof` operator

[Razican]

ECMASCript feature
We currently don't implement the instanceof ECMAScript operator, which would be a nice addition, since it's generating many panics in the ECMAScript test suite.

The specification of the instanceof operator can be found here.

Example code
Some example code can be found in MDN. But as an example:

This code should now work and give the expected result:

let a = new String("hello");

a instanceof String;

The expected output is true.

The implementation code that needs a change is located in here.

[morrien]

Hi, I think I can take on this as my first issue. Ill be working on this if it's okay.

[morrien]

I have implemented part of the instanceof operator functionality based on given specification to the best of my knowledge and skill.

With that said, there are certain tasks, or rather points in the specification that are somehow difficult to understand and therefore interpret correctly within the project and I believe that the best course of action in this situation is to consult these with someone.

I am not sure wheter it is customary to continue a conversation like this in the issue thread, or move it elsewhere.

How should I proceed with this? Thank you.

[HalidOdat]

I am not sure wheter it is customary to continue a conversation like this in the issue thread, or move it elsewhere.

How should I proceed with this? Thank you.

We can continue the conversation here or on the PR (when created)

[morrien]

Understood, I believe a verbose comment will be most fitting considering the state of the problem.

In each step, ECMAScript spec point will be provided, with possible code solution and comments if necessary.

Spec: InstanceofOperator ( V, target ):
Structure of the call: x instanceof y (x: Value, y: Value) -> Result<Value>

Spec: 1. If Type(target) is not Object, throw a TypeError exception.

if !y.is_object() { /* throw */ }

Spec: 2. Let instOfHandler be ? GetMethod(target, @@hasInstance).

let key: RcSymbol = interpreter.well_known_symbols().has_instance_symbol();
let instance_of_handler: Option<Property> = x.get_property(key);

_Comments:_
has_instance_symbol() _call currently returns async_iterator symbol_
_Even if changed, @@hasinstance symbol seems to not be implemented whatsoever_

Spec: 3. If instOfHandler is not undefined, then
                      a. return ! ToBoolean(? Call(instOfHandler, target, « V »)).

if instance_of_handler.is_some() { ... }

_Comments:_
_Considering the previous comments this becomes an unreachable block, always None_

Spec: 4. If IsCallable(target) is false, throw a TypeError exception.

if !y.as_object().unwrap().is_callable() { /* throw */ }

_Comments:_
_I am aware of_ unwrap() _not being standard, but considering the circumstances, it seems okay_
_If this call can be rewritten in a more reasonable form, please point it out_

Spec: 5. Return ? OrdinaryHasInstance(target, V).
_Comments:_
_Since this call has to be implemented, I will continue with the ongoing structure_

Spec: OrdinaryHasInstance ( target, V )
_Comments:_
_In order to keep this clear, the spec argument names are altered_

Spec: 1. If IsCallable(target) is false, return false.

if !y.as_object().unwrap().is_callable() { /* return false */ }

Spec: 2. If target has a [[BoundTargetFunction]] internal slot, then
                      a. Let bound_target_function be target.[[BoundTargetFunction]].
                      b. Return ? InstanceofOperator(V, bound_target_function).
_Comments:_
_Since this calls InstanceofOperator() I am not sure how to proceed_

Spec: 3. If Type(V) is not Object, return false.

if !x.is_object() { /* return false */ }

Spec: 4. Let P be ? Get(target, "prototype").

let borrowed_y: GcCellRef<Object> = y.as_object().unwrap();
let prototype_of_y = borrowed_y.prototype_instance();

_Comments:_
_Split in two because of temporary value dropped while borrowed in next step_

Spec: 5. If Type(P) is not Object, throw a TypeError exception.

if !prototype_of_y.is_object() { /* throw */ }

Spec: 6. Repeat,
                      a. Set V to ? V.[[GetPrototypeOf]] ().
                      b. If V is null, return false.
                      c. If SameValue(P, V) is true, return true.
_Comments:_
_This step is messiest on my part, as its every substep raises an issue or a question;_
_a. Rewriting V as well as (possibly) declaring new variable prompts lifetime and borrow over borrow issues_
_b. V is &value::Value, should I compare it to&Value::null()?_
_c. V is an object with "constructor" property (contains a Function), P is an object containing a Function - do I compare these?_

The parts that confuse me the most are @@hasinstance symbol, recursive call of InstanceofOperator() and the prototype chain.

I understand that if these are decided to be trivial, or easily solveable by someone else, this issue will be unassigned from me.
Regardless, I will be most grateful for any explanation of parts of the specification and implementation points mentioned above.

[HalidOdat]

has_instance_symbol() _call currently returns async_iterator symbol_
_Even if changed, @@hasinstance symbol seems to not be implemented whatsoever_

Good catch! This is most definetly a bug, we should return the has_insteance, and should be changed and yes you are right the has_instence symbol is not implemented on builtin objects.

_Comments:_
_Considering the previous comments this becomes an unreachable block, always None_

Yes. but when we implement it is should work. (does not have to be in this issue/PR).

_Comments:_
_I am aware of_ unwrap() _not being standard, but considering the circumstances, it seems okay_
_If this call can be rewritten in a more reasonable form, please point it out_

Yes. if its known than it is we can use unwrap but its prefered to use .expect since it also gives a message.

---

Fist I think its best to implement the GetMethod function so we dont have to inline it, this should be implemented on GcObject it returns a result because it can throw.

fn get_method<K>(&self, context: &mut Context, key: K) -> Result<Option<GcObject>> {
    let key = key.into();
    let value = self.get(&key);

    if value.is_null_or_undefined() {
        return Ok(None);
    }

    match value.as_object() {
        Some(object) if object.is_callable() => {
            Ok(object)
        }
        _ => Err(context.construct_type_error("..."))
    }
} 

---

The OrdinaryHasInstance should also be implemented on GcObject:

fn ordinary_has_instance(&self, context: &mut Context, object: &GcObject) -> Result<bool> {
    if !self.is_callable() {
        return Ok(false);
    }

    // TODO: If C has a [[BoundTargetFunction]] internal slot, then
    //           Let BC be C.[[BoundTargetFunction]].
    //           Return ? InstanceofOperator(O, BC).

    if let Some(object) = value.as_object() {
        if let Some(prototype) = self.get("prototype".into()).as_object() {
            let mut object = object.get_prototype_of();
            while let Some(object_prototype) = o.as_object() {
                if GcObject::equals(&prototype, &object_prototype) { // the equals function is used for samevalue for objects
                    return Ok(true);
                }
                object = object_prototype.into();
            }

            Ok(false) // if its not an object its null so we return. step 6.b
        } else {
            Err(context.construct_type_error("..."))
        }
    } else {
        return Ok(false);   
    }
}

---

and the insteanceofOperator:

if let Some(object) = target.as_object() {
    let key = interpreter.well_known_symbols().has_instance_symbol();

    match object.get_method(key)? {
        Some(instance_of_handler) => {
            Ok(instance_of_handler.call(target, &[v], context)?.to_boolean().into())
        }
        None if target.is_callable() => {
            Ok(target.ordinary_has_instance(context, v)?.into())
        }
        None => {
            context.throw_type_error("...")
        } 
    }
} else {
    context.throw_type_error("...")
}

NOTE: The type errors should have proper error messages.

[morrien]

Thank you for the reply, it helped me understand the interpretation of the specification within the project much better.
With that said, I have some minor questions still, if you don't mind;

1. Based on your edit, the 'o' variable in the 'while let' line in your second code snippet should be 'object' - is that correct?
2. First 'if let' line in your second code snippet includes 'value', but there is no trace of 'value' in the function scope - are you referring to the 'object: &GcObject' argument which was maybe named differently before some refactoring took place?
3. You mentioned implementing the first two functions on GcObject, does that mean here?

[HalidOdat]

1. Based on your edit, the 'o' variable in the 'while let' line in your second code snippet should be 'object' - is that correct?

Yes. this is correct.

---

2\. First 'if let' line in your second code snippet includes 'value', but there is no trace of 'value' in the function scope - are you referring to the 'object: &GcObject' argument which was maybe named differently before some refactoring took place?

Yes. after some refactoring made some mistakes, the second should be:

fn ordinary_has_instance(&self, context: &mut Context, value: &Value) -> Result<bool> {
    if !self.is_callable() {
        return Ok(false);
    }

    // TODO: If C has a [[BoundTargetFunction]] internal slot, then
    //           Let BC be C.[[BoundTargetFunction]].
    //           Return ? InstanceofOperator(O, BC).

    if let Some(object) = value.as_object() {
        if let Some(prototype) = self.get("prototype".into()).as_object() {
            let mut object = object.get_prototype_of();
            while let Some(object_prototype) = object.as_object() {
                if GcObject::equals(&prototype, &object_prototype) { // the equals function is used for samevalue for objects
                    return Ok(true);
                }
                object = object_prototype.into();
            }

            Ok(false) // if its not an object its null so we return. step 6.b
        } else {
            Err(context.construct_type_error("..."))
        }
    } else {
        return Ok(false);   
    }
}

and also we have to change instanceofOperator too:

if let Some(object) = target.as_object() {
    let key = interpreter.well_known_symbols().has_instance_symbol();

    match object.get_method(key)? {
        Some(instance_of_handler) => {
            Ok(instance_of_handler.call(target, &[v], context)?.to_boolean().into())
        }
        None if target.is_callable() => {
            Ok(target.ordinary_has_instance(context, v)?.into())
        }
        None => {
            context.throw_type_error("...")
        } 
    }
} else {
    context.throw_type_error("...")
}

• You mentioned implementing the first two functions on GcObject, does that mean here?

Yes.

[croraf]

You can also discuss on boa's discord, and put the summary here. And you can submit a PR draft with the stuff you have :) . Perhaps the issue can be solved in a couple of PRs