callGraphMessages doesn't order messages appropriately?

[anatoliykmetyuk]

    val executor = ScriptExecutorFactory.createScriptExecutor(true)

    def node = {
      val n = N_n_ary_op(null, false)
      n.index = scala.util.Random.nextInt(100)
      n
    }

    executor.callGraphMessages += Activation(node)
    executor.callGraphMessages += Continuation(node)
    executor.callGraphMessages += Activation(node)
    executor.callGraphMessages += Continuation(node)

    for (msg <- executor.callGraphMessages) println(msg)

If you run this code, you'll see that the messages go exactly in order they were added:

-1 Activation 29 null
-1 Continuation 20 null {} 20 null S=false nActivated=0 (=0S+0N)
-1 Activation 93 null
-1 Continuation 0 null {}  0 null S=false nActivated=0 (=0S+0N)

Expected result would be that Activation messages go prior to Continuation messages because they have higher priority. This is very strange, I have no idea why this may be the case - code in SubScript classes seems to be perfectly valid. This also may be exactly the cause of issue #22, because there the behaviour was exactly like messages were added in random order and remained in that order.

[anatoliykmetyuk]

import scala.collection.mutable._

    val ord = new Ordering[Int] {
      def compare(x: Int, y: Int): Int = x - y
    }
    val pc = PriorityQueue[Int]()(ord)

    pc += 10
    pc += 1
    pc += 8
    pc += 20
    pc += -1

    for (x <- pc) println(x)

this code runs fine and outputs

20
10
8
1
-1

that is, elements are outputed in proper order. So I assume same must hold for the case of callGraphMessages.

[anatoliykmetyuk]

In seems that Scala's native PriorityQueue has some really weird bug:

    import scala.collection.mutable.PriorityQueue
    import scala.util.Random

    // Descending ordering
    val ord = new Ordering[Int] {
      override def compare(x: Int, y: Int) = x - y
    }

    // Random queue
    def queue(n: Int, bound: Int = Int.MaxValue) = {
      val pq = PriorityQueue[Int]()(ord)
      for (i <- 1 to n) pq += Random.nextInt(bound)
      pq
    }

    // Validity test
    def valid(q: PriorityQueue[Int]): Boolean =
      q.toList.sliding(2).forall {l => ord.compare(l(0), l(1)) >= 0}

    // How to view a queue
    def queueToString(q: PriorityQueue[Int]): String = s"$q => ${valid(q)}"

    // Valid queue example
    val validQueue = PriorityQueue[Int](10, 1, 8, 20, -1)

    // Test valid queue and 100 random queues
    println(s"Valid queue: ${queueToString(validQueue)}")
    for (i <- 1 to 100) println(queueToString(queue(10, 10)))

So I think we should shift from PriorityQueue to other collections - virtually every sequence has means to order itself with Ordering.

[AndreVanDelft]

PriorityQueue works well. You should call dequeue on it, just like ScriptExecutor does. See what your first code fragment yields:

scala>     for (msg <- executor.callGraphMessages) println(msg)
-1 Activation 24 null
-1 Continuation 31 null {} 31 null S=false nActivated=0 (=0S+0N)
-1 Activation 58 null
-1 Continuation 15 null {} 15 null S=false nActivated=0 (=0S+0N)

scala> executor.callGraphMessages.dequeue
res5: subscript.vm.CallGraphMessage = -1 Activation 24 null

scala> executor.callGraphMessages.dequeue
res6: subscript.vm.CallGraphMessage = -1 Activation 58 null

scala> executor.callGraphMessages.dequeue
res7: subscript.vm.CallGraphMessage = -1 Continuation 31 null {} 31 null S=false nActivated=0 (=0S+0N)

scala> executor.callGraphMessages.dequeue
res8: subscript.vm.CallGraphMessage = -1 Continuation 15 null {} 15 null S=false nActivated=0 (=0S+0N)