Incorrect lftp and lftq calculation
kapone89 opened this issue · 4 comments
kapone89 commented
In some cases lftp and lftq are calculated incorrectly. To reproduce this bug you can do this:
Here's my table dump (postgresql). All values I'v changed to zero manualy. Now when I call Category.rebuild_nested_interval_tree!, lftp, lftq (and lft) are calculated incorrectly.
--
-- PostgreSQL database dump
--
SET statement_timeout = 0;
SET client_encoding = 'UTF8';
SET standard_conforming_strings = off;
SET check_function_bodies = false;
SET client_min_messages = warning;
SET escape_string_warning = off;
SET search_path = public, pg_catalog;
--
-- Name: categories_id_seq; Type: SEQUENCE SET; Schema: public; Owner: ipso-jure
--
SELECT pg_catalog.setval('categories_id_seq', 61, true);
--
-- Data for Name: categories; Type: TABLE DATA; Schema: public; Owner: ipso-jure
--
COPY categories (id, parent_id, lftp, lftq, name, active, lft) FROM stdin;
1 \N 0 0 category 0 t 0
56 40 0 0 category 22 t 0
57 40 0 0 category 23 t 0
58 41 0 0 category 24 t 0
59 58 0 0 category 25 t 0
60 1 0 0 category 26 t 0
5 1 0 0 category 1 t 0
32 1 0 0 category 2 t 0
33 32 0 0 category 3 t 0
37 1 0 0 category 4 t 0
38 1 0 0 category 5 t 0
39 38 0 0 category 6 t 0
40 1 0 0 category 7 t 0
41 1 0 0 category 8 t 0
42 1 0 0 category 9 t 0
43 1 0 0 category 10 t 0
44 1 0 0 category 11 t 0
45 1 0 0 category 12 t 0
46 1 0 0 category 13 t 0
47 1 0 0 category 14 t 0
48 1 0 0 category 15 t 0
49 1 0 0 category 16 t 0
50 49 0 0 category 17 t 0
51 38 0 0 category 18 t 0
52 40 0 0 category 19 t 0
53 52 0 0 category 20 t 0
55 40 0 0 category 21 t 0
\.
--
-- PostgreSQL database dump complete
--
clyfe commented
Can you write a test to reproduce the bug please?
kapone89 commented
I'v found this bug in this case:
FIXTURES (categories.yml)
category_1:
id: 1
parent_id:
lftp: 0
lftq: 0
name: category 0
active: true
lft: 0.0
category_2:
id: 5
parent_id: 1
lftp: 0
lftq: 0
name: category 1
active: true
lft: 0.0
category_3:
id: 32
parent_id: 1
lftp: 0
lftq: 0
name: category 2
active: true
lft: 0.0
category_4:
id: 33
parent_id: 32
lftp: 0
lftq: 0
name: category 3
active: true
lft: 0.0
category_5:
id: 37
parent_id: 1
lftp: 0
lftq: 0
name: category 4
active: true
lft: 0.0
category_6:
id: 38
parent_id: 1
lftp: 0
lftq: 0
name: category 5
active: true
lft: 0.0
category_7:
id: 39
parent_id: 38
lftp: 0
lftq: 0
name: category 6
active: true
lft: 0.0
category_8:
id: 40
parent_id: 1
lftp: 0
lftq: 0
name: category 7
active: true
lft: 0.0
category_9:
id: 41
parent_id: 1
lftp: 0
lftq: 0
name: category 8
active: true
lft: 0.0
category_10:
id: 42
parent_id: 1
lftp: 0
lftq: 0
name: category 9
active: true
lft: 0.0
category_11:
id: 43
parent_id: 1
lftp: 0
lftq: 0
name: category 10
active: true
lft: 0.0
category_12:
id: 44
parent_id: 1
lftp: 0
lftq: 0
name: category 11
active: true
lft: 0.0
category_13:
id: 45
parent_id: 1
lftp: 0
lftq: 0
name: category 12
active: true
lft: 0.0
category_14:
id: 46
parent_id: 1
lftp: 0
lftq: 0
name: category 13
active: true
lft: 0.0
category_15:
id: 47
parent_id: 1
lftp: 0
lftq: 0
name: category 14
active: true
lft: 0.0
category_16:
id: 48
parent_id: 1
lftp: 0
lftq: 0
name: category 15
active: true
lft: 0.0
category_17:
id: 49
parent_id: 1
lftp: 0
lftq: 0
name: category 16
active: true
lft: 0.0
category_18:
id: 50
parent_id: 49
lftp: 0
lftq: 0
name: category 17
active: true
lft: 0.0
category_19:
id: 51
parent_id: 38
lftp: 0
lftq: 0
name: category 18
active: true
lft: 0.0
category_20:
id: 52
parent_id: 40
lftp: 0
lftq: 0
name: category 19
active: true
lft: 0.0
category_21:
id: 53
parent_id: 52
lftp: 0
lftq: 0
name: category 20
active: true
lft: 0.0
category_22:
id: 55
parent_id: 40
lftp: 0
lftq: 0
name: category 21
active: true
lft: 0.0
category_23:
id: 56
parent_id: 40
lftp: 0
lftq: 0
name: category 22
active: true
lft: 0.0
category_24:
id: 57
parent_id: 40
lftp: 0
lftq: 0
name: category 23
active: true
lft: 0.0
category_25:
id: 58
parent_id: 41
lftp: 0
lftq: 0
name: category 24
active: true
lft: 0.0
category_26:
id: 59
parent_id: 58
lftp: 0
lftq: 0
name: category 25
active: true
lft: 0.0
category_27:
id: 60
parent_id: 1
lftp: 0
lftq: 0
name: category 26
active: true
lft: 0.0
TEST (category_test.rb):
require 'test_helper'
class CategoryTest < ActiveSupport::TestCase
test 'descendants chould be correct test 1' do
Category.rebuild_nested_interval_tree!
[10, 11, 12, 13, 14, 15, 16, 27].each do |i|
assert_equal categories(:"category_#{i}").descendants, []
end
end
end
I know that in this test lftp and lftq values are not checked but I don't fully understand the algorithm to test that. In this test incorrent lftp/lftq values causes incorrect descendants method result.
clyfe commented
It works on my machine!
Are you using the latest version? If not make sure you do and try again!
The patch with the test I used, derived from your example is here.
kapone89 commented
I'm sorry. My fault. Bug was in another place. Thank you very much for help. You're doing a great job.