deletion of reinserted quad gives quad does not exist error, quad is returned by /api/v2/read

[3pCode]

Description

Using boltDB, and the V2 rest apis, after removing a quad, re-adding the quad, then attempting to delete the quad again results in a quad does not exist error from the api. After receiving the error, a call to /api/v2/read, does return the quad, however the /api/v2/delete api still behaves as though the quad does not exist.

Steps to reproduce the issue
(Invocation of the rest api's was performed using the swagger client v2 rest apis)

1. Init an empty bolt db, and start cayley with boltdb as backend using cayley http --db=bolt --dbpath=/tmp/someBoltDBFolder/
2. Using the api/v2/write api, add the following quads

<bob> <status> "Feeling happy" .
<sally> <status> "Feeling sad" .
<jim> <status> "Feeling happy" .
<sally> <follows> <jim> .

curl -X POST "http://localhost:64210/api/v2/write" -H "accept: application/json" -H "Content-Type: application/n-quads" -d "<bob> <status> \"Feeling happy\" .<sally> <status> \"Feeling sad\" .<jim> <status> \"Feeling happy\" .<sally> <follows> <jim> ."

2. Using the api/v2/write api, add the following quad
   <bob> <follows> <sally> .

curl -X POST "http://localhost:64210/api/v2/write" -H "accept: application/json" -H "Content-Type: application/n-quads" -d "<bob> <follows> <sally> ."

3. Using the api/v2/delete api, delete the quad
   <bob> <follows> <sally> .

curl -X POST "http://localhost:64210/api/v2/delete" -H "accept: application/json" -H "Content-Type: application/n-quads" -d "<bob> <follows> <sally> ."

4. Using the api/v2/write api, reinsert the deleted quad
   <bob> <follows> <sally> .

5.Using the api/v2/delete api, attempt to delete the quad again
<bob> <follows> <sally> .

curl -X POST "http://localhost:64210/api/v2/delete" -H "accept: application/json" -H "Content-Type: application/n-quads" -d "<bob> <follows> <sally> ."

This yields the error:
{
"error": "delete -- -> : quad does not exist"
}

6. Using the /api/v2/read api, confirm the quad actually does exist:
   curl -X GET "http://localhost:64210/api/v2/read?format=nquads" -H "accept: application/n-quads"

<bob> <status> "Feeling happy" .
<sally> <status> "Feeling sad" .
<jim> <status> "Feeling happy" .
<sally> <follows> <jim> .
<bob> <follows> <sally> .

Received results:

Step 5, should have resulted in a successful deletion, but instead reported the quad did not exist.

{
  "error": "delete <bob> -- <follows> -> <sally>: quad does not exist"
}

Expected results:
Deletion in step 5 would succeed.

Output of cayley version or commit hash:
./cayley version
Cayley version: 0.7.3
Git commit hash: 782194b
Build date: 2018-04-23T15:41:54Z

Environment details:
OSX 10.12.16

Backend database: bundled bolt version with cayley. Also reproduced with leveldb.

[3pCode]

Below is a reproducer at the native level that illustrates the issue as well:

package main

import (
	"fmt"
	"io/ioutil"
	"log"
	"os"

	"github.com/cayleygraph/cayley"
	"github.com/cayleygraph/cayley/graph"
	_ "github.com/cayleygraph/cayley/graph/kv/bolt"
	"github.com/cayleygraph/cayley/quad"
)

func main() {
	// File for your new BoltDB. Use path to regular file and not temporary in the real world
	tmpdir, err := ioutil.TempDir("", "example")
	if err != nil {
		log.Fatal(err)
	}

	defer os.RemoveAll(tmpdir) // clean up

	// Initialize the database
	err = graph.InitQuadStore("bolt", tmpdir, nil)
	if err != nil {
		log.Fatal(err)
	}

	// Open and use the database
	store, err := cayley.NewGraph("bolt", tmpdir, nil)
	if err != nil {
		log.Fatalln(err)
	}

	q1 := []string{"<bob>", "<status>", "Feeling happy", "."}
	store.AddQuad(quad.Make(q1[0], q1[1], q1[2], q1[3]))

	q2 := []string{"<sally>", "<follows>", "<jim>", "."}
	store.AddQuad(quad.Make(q2[0], q2[1], q2[2], q2[3]))

	q5 := []string{"<bob>", "<follows>", "<sally>", "."}

	for i := 0; i < 2; i++ {

		err = store.AddQuad(quad.Make(q5[0], q5[1], q5[2], q5[3]))

		if err != nil {
			fmt.Print("---> Error on addition of quad... ")
			log.Fatalln(err)
		}

		err = store.RemoveQuad(quad.Make(q5[0], q5[1], q5[2], q5[3]))
		if err != nil {
			// This is the bug, we should never land here, but we do on the second iteration
			fmt.Print("---> Error on removal of quad quad... ")
			log.Fatalln(err)
		}
	}

}

[3pCode]

The issue seems to stems from the hasPrimitive, method in indexing.go, when that method iterates over the options array, it is settling on the first matched primitive it receives, however in the case of a reinserted quad, there are multiple matches, but it still settles on the first one since it is looping from the start of the options array. Perhaps it should be iterating the options backward, the last id seen would be the one we actually want from the log, I think. Modifying the code to loop backwards resolves the issue, and the unit tests appear to pass as well as the use case of this bug using. Change is below:

cayleygraph/cayley/graph/kv/indexing.go

...
line 678:

//change to loop backwards through options..
for ix := len(options) - 1; ix >= 0; ix-- {
		//for _, x := range options {
		// TODO: batch
		//prim, err := qs.getPrimitiveFromLog(ctx, tx, x)
		prim, err := qs.getPrimitiveFromLog(ctx, tx, options[ix])

		if err != nil {
			return nil, err
		}
		if prim.IsSameLink(p) {
			return prim, nil
		}
	}
	return nil, 
```nil

[dennwc]

@3pCode Thanks for digging into this! Yes, backward iteration makes sense, since log entries will always have increasing IDs, and all the lists used to calculate options are sorted.

Feel free to PR changes - it looks like a valid fix to me. Will be happy to review it :)

[dennwc]

Fixed in #747

[cassels]

I'm experiencing a very similar issue in v0.7.5 that is likely related to this.

Add quad X, remove quad X, add quad X, remove quad X = expected behavior: quad X removed.
Add quad Y, add quad Y again, remove quad Y = unexpected behavior: quad Y can never be removed.

Noticed this by accidentally adding the same quad twice on the UI.

[dennwc]

Fixed for memstore in #860.

[iddan]

Is it supposed to reoccur in Bolt as well?

[dennwc]

Yes, I think all KVs implement it incorrectly as well. #885 may be a part of it.