2109

Committed 07 Mar 2024 01:56PM UTC coverage: 90.918% (+0.01%) from 90.908%

Build # 2109

Build Type

push

Evergreen

Committed by

web-flow

Commit Message

Fix querying with a path into nested collections with wildcards (#7404)

Comparing a collection with a list could fail if there was wildcards
in the path and therefore multiple collections to compare with right
hand list.

Linklist is implicitly having wildcard in the path, so if linklists is
in the path there will be a similar problem.  Do not merge values
from different objects into a common list in queries.

Run Details

93972 of 173176 branches covered (54.26%)

323 of 332 new or added lines in 6 files covered. (97.29%)

91 existing lines in 18 files now uncovered.

238503 of 262328 relevant lines covered (90.92%)

6065347.74 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

95.79

/src/realm/array_backlink.cpp

/*************************************************************************
 *
 * Copyright 2016 Realm Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 **************************************************************************/

#include <realm/array_backlink.hpp>
#include <realm/util/assert.hpp>
#include <realm/table.hpp>
#include <realm/group.hpp>
#include <realm/list.hpp>
#include <realm/set.hpp>
#include <realm/dictionary.hpp>

using namespace realm;

// nullify forward links corresponding to any backward links at index 'ndx'.
void ArrayBacklink::nullify_fwd_links(size_t ndx, CascadeState& state)
{
    uint64_t value = Array::get(ndx);
    if (value == 0) {
        return;
    }

    // Naming: Links go from source to target.
    // Backlinks go from target to source.
    // This array holds backlinks, hence it is the target.
    // The table which holds the corresponding fwd links is the source.

    // determine target table, column and key.
    REALM_ASSERT_DEBUG(dynamic_cast<Cluster*>(get_parent()));
    auto cluster = static_cast<Cluster*>(get_parent());
    const Table* target_table = cluster->get_owning_table();
    ColKey target_col_key = cluster->get_col_key(get_ndx_in_parent());
    ObjKey target_key = cluster->get_real_key(ndx);

    // determine the source table/col - which is the one holding the forward links
    TableRef source_table = target_table->get_opposite_table(target_col_key);
    ColKey src_col_key = target_table->get_opposite_column(target_col_key);

    // Now follow all backlinks to their origin and clear forward links.
    if ((value & 1) != 0) {
        // just a single one
        state.enqueue_for_nullification(*source_table, src_col_key, ObjKey(value >> 1),
                                        {target_table->get_key(), target_key});
    }
    else {
        // There is more than one backlink - Iterate through them all
        ref_type ref = to_ref(value);
        BPlusTree<int64_t> backlink_list(m_alloc);
        backlink_list.init_from_ref(ref);

        size_t sz = backlink_list.size();
        for (size_t i = 0; i < sz; i++) {
            state.enqueue_for_nullification(*source_table, src_col_key, ObjKey(backlink_list.get(i)),
                                            {target_table->get_key(), target_key});
        }
    }
}

void ArrayBacklink::add(size_t ndx, ObjKey key)
{
    uint64_t value = Array::get(ndx);

    // A backlink list of size 1 is stored as a single non-ref column value.
    if (value == 0) {
        set(ndx, key.value << 1 | 1); // Throws
        return;
    }

    // When increasing the size of the backlink list from 1 to 2, we need to
    // convert from the single non-ref column value representation, to a B+-tree
    // representation.
    BPlusTree<int64_t> backlink_list(m_alloc);
    if ((value & 1) != 0) {
        // Create new column to hold backlinks
        backlink_list.create();
        set_as_ref(ndx, backlink_list.get_ref());
        backlink_list.add(value >> 1);
    }
    else {
        backlink_list.init_from_ref(to_ref(value));
        backlink_list.set_parent(this, ndx);
        backlink_list.split_if_needed();
    }
    backlink_list.add(key.value); // Throws
}

// Return true if the last link was removed
bool ArrayBacklink::remove(size_t ndx, ObjKey key)
{
    uint64_t value = Array::get(ndx);
    REALM_ASSERT_DEBUG(value != 0);
    if (value == 0)
        return true;

    // If there is only a single backlink, it can be stored as
    // a tagged value
    if ((value & 1) != 0) {
        REALM_ASSERT_DEBUG(int64_t(value >> 1) == key.value);
        if (int64_t(value >> 1) == key.value) {
            set(ndx, 0);
            return true;
        }
        return false;
    }

    // if there is a list of backlinks we have to find
    // the right one and remove it.
    BPlusTree<int64_t> backlink_list(m_alloc);
    backlink_list.init_from_ref(ref_type(value));
    backlink_list.set_parent(this, ndx);
    backlink_list.split_if_needed();

    size_t last_ndx = backlink_list.size() - 1;
    size_t backlink_ndx = backlink_list.find_first(key.value);
    REALM_ASSERT_DEBUG(backlink_ndx != not_found);
    if (backlink_ndx != not_found) {
        if (backlink_ndx != last_ndx)
            backlink_list.set(backlink_ndx, backlink_list.get(last_ndx));
        backlink_list.erase(last_ndx); // Throws
    }

    // If there is only one backlink left we can inline it as tagged value
    if (last_ndx == 1) {
        uint64_t key_value = backlink_list.get(0);
        backlink_list.destroy();

        set(ndx, key_value << 1 | 1);
    }

    return false;
}

void ArrayBacklink::erase(size_t ndx)
{
    uint64_t value = Array::get(ndx);
    if (value && (value & 1) == 0) {
        Array::destroy_deep(ref_type(value), m_alloc);
    }
    Array::erase(ndx);
}

size_t ArrayBacklink::get_backlink_count(size_t ndx) const
{
    uint64_t value = Array::get(ndx);
    if (value == 0) {
        return 0;
    }

    // If there is only a single backlink, it can be stored as
    // a tagged value
    if ((value & 1) != 0) {
        return 1;
    }

    // return size of list
    MemRef mem(ref_type(value), m_alloc);
    return BPlusTree<int64_t>::size_from_header(mem.get_addr());
}

ObjKey ArrayBacklink::get_backlink(size_t ndx, size_t index) const
{
    uint64_t value = Array::get(ndx);
    REALM_ASSERT(value != 0);

    // If there is only a single backlink, it can be stored as
    // a tagged value
    if ((value & 1) != 0) {
        REALM_ASSERT(index == 0);
        return ObjKey(int64_t(value >> 1));
    }

    BPlusTree<int64_t> backlink_list(m_alloc);
    backlink_list.init_from_ref(ref_type(value));

    REALM_ASSERT(index < backlink_list.size());
    return ObjKey(backlink_list.get(index));
}

void ArrayBacklink::verify() const
{
#ifdef REALM_DEBUG
    Array::verify();

    REALM_ASSERT(dynamic_cast<Cluster*>(get_parent()));
    auto cluster = static_cast<Cluster*>(get_parent());
    const Table* target_table = cluster->get_owning_table();
    ColKey backlink_col_key = cluster->get_col_key(get_ndx_in_parent());

    TableRef src_table = target_table->get_opposite_table(backlink_col_key);
    ColKey src_col_key = target_table->get_opposite_column(backlink_col_key);

    // Verify that each backlink has a corresponding forward link
    for (size_t i = 0; i < size(); ++i) {
        ObjKey target_key = cluster->get_real_key(i);
        ObjLink target_link(target_table->get_key(), target_key);
        auto cnt = get_backlink_count(i);
        for (size_t j = 0; j < cnt; ++j) {
            Obj src_obj = src_table->get_object(get_backlink(i, j));
            if (src_col_key.is_dictionary()) {
                REALM_ASSERT(src_obj.get_dictionary_ptr(src_col_key)->find_any(target_link) != npos);
                continue;
            }

            if (src_col_key.get_type() == col_type_Mixed) {
                if (src_col_key.is_collection()) {
                    REALM_ASSERT(src_obj.get_collection_ptr(src_col_key)->find_any(target_link) != npos);
                }
                else {
                    REALM_ASSERT(src_obj.get<Mixed>(src_col_key).get_link() == target_link);
                }
                continue;
            }

            if (src_col_key.is_list()) {
                REALM_ASSERT(src_obj.get_list<ObjKey>(src_col_key).find_first(target_key) != npos);
            }
            else if (src_col_key.is_set()) {
                REALM_ASSERT(src_obj.get_set<ObjKey>(src_col_key).find(target_key) != npos);
            }
            else {
                REALM_ASSERT(src_obj.get_unfiltered_link(src_col_key) == target_key);
            }
        }
    }
#endif
}

bool ArrayBacklink::verify_backlink(size_t ndx, int64_t link)
{
#ifdef REALM_DEBUG
    uint64_t value = Array::get(ndx);
    if (value == 0)
        return false;

    // If there is only a single backlink, it can be stored as
    // a tagged value
    if ((value & 1) != 0) {
        return int64_t(value >> 1) == link;
    }

    BPlusTree<int64_t> backlink_list(m_alloc);
    backlink_list.init_from_ref(ref_type(value));

    return backlink_list.find_first(link) != realm::not_found;
#else
    static_cast<void>(ndx);
    static_cast<void>(link);
    return true;
#endif
}

1	/*************************************************************************
2	*
3	* Copyright 2016 Realm Inc.
4	*
5	* Licensed under the Apache License, Version 2.0 (the "License");
6	* you may not use this file except in compliance with the License.
7	* You may obtain a copy of the License at
8	*
9	* http://www.apache.org/licenses/LICENSE-2.0
10	*
11	* Unless required by applicable law or agreed to in writing, software
12	* distributed under the License is distributed on an "AS IS" BASIS,
13	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14	* See the License for the specific language governing permissions and
15	* limitations under the License.
16	*
17	**************************************************************************/
18
19	#include <realm/array_backlink.hpp>
20	#include <realm/util/assert.hpp>
21	#include <realm/table.hpp>
22	#include <realm/group.hpp>
23	#include <realm/list.hpp>
24	#include <realm/set.hpp>
25	#include <realm/dictionary.hpp>
26
27	using namespace realm;
28
29	// nullify forward links corresponding to any backward links at index 'ndx'.
30	void ArrayBacklink::nullify_fwd_links(size_t ndx, CascadeState& state)
31	{	191,904✔
32	uint64_t value = Array::get(ndx);	191,904✔
33	if (value == 0) {	191,904✔
34	return;	185,529✔
35	}	185,529✔
36		3,186✔
37	// Naming: Links go from source to target.	3,186✔
38	// Backlinks go from target to source.	3,186✔
39	// This array holds backlinks, hence it is the target.	3,186✔
40	// The table which holds the corresponding fwd links is the source.	3,186✔
41		3,186✔
42	// determine target table, column and key.	3,186✔
43	REALM_ASSERT_DEBUG(dynamic_cast<Cluster*>(get_parent()));	6,375✔
44	auto cluster = static_cast<Cluster*>(get_parent());	6,375✔
45	const Table* target_table = cluster->get_owning_table();	6,375✔
46	ColKey target_col_key = cluster->get_col_key(get_ndx_in_parent());	6,375✔
47	ObjKey target_key = cluster->get_real_key(ndx);	6,375✔
48		3,186✔
49	// determine the source table/col - which is the one holding the forward links	3,186✔
50	TableRef source_table = target_table->get_opposite_table(target_col_key);	6,375✔
51	ColKey src_col_key = target_table->get_opposite_column(target_col_key);	6,375✔
52		3,186✔
53	// Now follow all backlinks to their origin and clear forward links.	3,186✔
54	if ((value & 1) != 0) {	6,375✔
55	// just a single one	2,892✔
56	state.enqueue_for_nullification(*source_table, src_col_key, ObjKey(value >> 1),	5,787✔
57	{target_table->get_key(), target_key});	5,787✔
58	}	5,787✔
59	else {	588✔
60	// There is more than one backlink - Iterate through them all	294✔
61	ref_type ref = to_ref(value);	588✔
62	BPlusTree<int64_t> backlink_list(m_alloc);	588✔
63	backlink_list.init_from_ref(ref);	588✔
64		294✔
65	size_t sz = backlink_list.size();	588✔
66	for (size_t i = 0; i < sz; i++) {	1,776✔
67	state.enqueue_for_nullification(*source_table, src_col_key, ObjKey(backlink_list.get(i)),	1,188✔
68	{target_table->get_key(), target_key});	1,188✔
69	}	1,188✔
70	}	588✔
71	}	6,375✔
72
73	void ArrayBacklink::add(size_t ndx, ObjKey key)
74	{	6,753,522✔
75	uint64_t value = Array::get(ndx);	6,753,522✔
76		3,376,986✔
77	// A backlink list of size 1 is stored as a single non-ref column value.	3,376,986✔
78	if (value == 0) {	6,753,522✔
79	set(ndx, key.value << 1 \| 1); // Throws	615,375✔
80	return;	615,375✔
81	}	615,375✔
82		3,069,909✔
83	// When increasing the size of the backlink list from 1 to 2, we need to	3,069,909✔
84	// convert from the single non-ref column value representation, to a B+-tree	3,069,909✔
85	// representation.	3,069,909✔
86	BPlusTree<int64_t> backlink_list(m_alloc);	6,138,147✔
87	if ((value & 1) != 0) {	6,138,147✔
88	// Create new column to hold backlinks	9,984✔
89	backlink_list.create();	19,947✔
90	set_as_ref(ndx, backlink_list.get_ref());	19,947✔
91	backlink_list.add(value >> 1);	19,947✔
92	}	19,947✔
93	else {	6,118,200✔
94	backlink_list.init_from_ref(to_ref(value));	6,118,200✔
95	backlink_list.set_parent(this, ndx);	6,118,200✔
96	backlink_list.split_if_needed();	6,118,200✔
97	}	6,118,200✔
98	backlink_list.add(key.value); // Throws	6,138,147✔
99	}	6,138,147✔
100
101	// Return true if the last link was removed
102	bool ArrayBacklink::remove(size_t ndx, ObjKey key)
103	{	196,959✔
104	uint64_t value = Array::get(ndx);	196,959✔
105	REALM_ASSERT_DEBUG(value != 0);	196,959✔
106	if (value == 0)	196,959✔
107	return true;	×
108		98,475✔
109	// If there is only a single backlink, it can be stored as	98,475✔
110	// a tagged value	98,475✔
111	if ((value & 1) != 0) {	196,959✔
112	REALM_ASSERT_DEBUG(int64_t(value >> 1) == key.value);	67,737✔
113	if (int64_t(value >> 1) == key.value) {	67,737✔
114	set(ndx, 0);	67,737✔
115	return true;	67,737✔
116	}	67,737✔
UNCOV 117	return false;	×
UNCOV 118	}	×
119		64,653✔
120	// if there is a list of backlinks we have to find	64,653✔
121	// the right one and remove it.	64,653✔
122	BPlusTree<int64_t> backlink_list(m_alloc);	129,222✔
123	backlink_list.init_from_ref(ref_type(value));	129,222✔
124	backlink_list.set_parent(this, ndx);	129,222✔
125	backlink_list.split_if_needed();	129,222✔
126		64,653✔
127	size_t last_ndx = backlink_list.size() - 1;	129,222✔
128	size_t backlink_ndx = backlink_list.find_first(key.value);	129,222✔
129	REALM_ASSERT_DEBUG(backlink_ndx != not_found);	129,222✔
130	if (backlink_ndx != not_found) {	129,222✔
131	if (backlink_ndx != last_ndx)	129,222✔
132	backlink_list.set(backlink_ndx, backlink_list.get(last_ndx));	68,340✔
133	backlink_list.erase(last_ndx); // Throws	129,222✔
134	}	129,222✔
135		64,653✔
136	// If there is only one backlink left we can inline it as tagged value	64,653✔
137	if (last_ndx == 1) {	129,222✔
138	uint64_t key_value = backlink_list.get(0);	2,307✔
139	backlink_list.destroy();	2,307✔
140		1,179✔
141	set(ndx, key_value << 1 \| 1);	2,307✔
142	}	2,307✔
143		64,653✔
144	return false;	129,222✔
145	}	129,222✔
146
147	void ArrayBacklink::erase(size_t ndx)
148	{	207,033✔
149	uint64_t value = Array::get(ndx);	207,033✔
150	if (value && (value & 1) == 0) {	207,033✔
151	Array::destroy_deep(ref_type(value), m_alloc);	432✔
152	}	432✔
153	Array::erase(ndx);	207,033✔
154	}	207,033✔
155
156	size_t ArrayBacklink::get_backlink_count(size_t ndx) const
157	{	695,205✔
158	uint64_t value = Array::get(ndx);	695,205✔
159	if (value == 0) {	695,205✔
160	return 0;	352,815✔
161	}	352,815✔
162		171,075✔
163	// If there is only a single backlink, it can be stored as	171,075✔
164	// a tagged value	171,075✔
165	if ((value & 1) != 0) {	342,390✔
166	return 1;	320,100✔
167	}	320,100✔
168		11,145✔
169	// return size of list	11,145✔
170	MemRef mem(ref_type(value), m_alloc);	22,290✔
171	return BPlusTree<int64_t>::size_from_header(mem.get_addr());	22,290✔
172	}	22,290✔
173
174	ObjKey ArrayBacklink::get_backlink(size_t ndx, size_t index) const
175	{	9,381,042✔
176	uint64_t value = Array::get(ndx);	9,381,042✔
177	REALM_ASSERT(value != 0);	9,381,042✔
178		4,689,846✔
179	// If there is only a single backlink, it can be stored as	4,689,846✔
180	// a tagged value	4,689,846✔
181	if ((value & 1) != 0) {	9,381,042✔
182	REALM_ASSERT(index == 0);	175,725✔
183	return ObjKey(int64_t(value >> 1));	175,725✔
184	}	175,725✔
185		4,602,042✔
186	BPlusTree<int64_t> backlink_list(m_alloc);	9,205,317✔
187	backlink_list.init_from_ref(ref_type(value));	9,205,317✔
188		4,602,042✔
189	REALM_ASSERT(index < backlink_list.size());	9,205,317✔
190	return ObjKey(backlink_list.get(index));	9,205,317✔
191	}	9,205,317✔
192
193	void ArrayBacklink::verify() const
194	{	2,388✔
195	#ifdef REALM_DEBUG	2,388✔
196	Array::verify();	2,388✔
197		1,194✔
198	REALM_ASSERT(dynamic_cast<Cluster*>(get_parent()));	2,388✔
199	auto cluster = static_cast<Cluster*>(get_parent());	2,388✔
200	const Table* target_table = cluster->get_owning_table();	2,388✔
201	ColKey backlink_col_key = cluster->get_col_key(get_ndx_in_parent());	2,388✔
202		1,194✔
203	TableRef src_table = target_table->get_opposite_table(backlink_col_key);	2,388✔
204	ColKey src_col_key = target_table->get_opposite_column(backlink_col_key);	2,388✔
205		1,194✔
206	// Verify that each backlink has a corresponding forward link	1,194✔
207	for (size_t i = 0; i < size(); ++i) {	21,024✔
208	ObjKey target_key = cluster->get_real_key(i);	18,636✔
209	ObjLink target_link(target_table->get_key(), target_key);	18,636✔
210	auto cnt = get_backlink_count(i);	18,636✔
211	for (size_t j = 0; j < cnt; ++j) {	113,016✔
212	Obj src_obj = src_table->get_object(get_backlink(i, j));	94,380✔
213	if (src_col_key.is_dictionary()) {	94,380✔
214	REALM_ASSERT(src_obj.get_dictionary_ptr(src_col_key)->find_any(target_link) != npos);	294✔
215	continue;	294✔
216	}	294✔
217		47,043✔
218	if (src_col_key.get_type() == col_type_Mixed) {	94,086✔
219	if (src_col_key.is_collection()) {	6✔
220	REALM_ASSERT(src_obj.get_collection_ptr(src_col_key)->find_any(target_link) != npos);	6✔
221	}	6✔
222	else {	×
223	REALM_ASSERT(src_obj.get<Mixed>(src_col_key).get_link() == target_link);	×
224	}	×
225	continue;	6✔
226	}	6✔
227		47,040✔
228	if (src_col_key.is_list()) {	94,080✔
229	REALM_ASSERT(src_obj.get_list<ObjKey>(src_col_key).find_first(target_key) != npos);	27,420✔
230	}	27,420✔
231	else if (src_col_key.is_set()) {	66,660✔
232	REALM_ASSERT(src_obj.get_set<ObjKey>(src_col_key).find(target_key) != npos);	×
233	}	×
234	else {	66,660✔
235	REALM_ASSERT(src_obj.get_unfiltered_link(src_col_key) == target_key);	66,660✔
236	}	66,660✔
237	}	94,080✔
238	}	18,636✔
239	#endif	2,388✔
240	}	2,388✔
241
242	bool ArrayBacklink::verify_backlink(size_t ndx, int64_t link)
243	{	126,666✔
244	#ifdef REALM_DEBUG	126,666✔
245	uint64_t value = Array::get(ndx);	126,666✔
246	if (value == 0)	126,666✔
247	return false;	×
248		63,333✔
249	// If there is only a single backlink, it can be stored as	63,333✔
250	// a tagged value	63,333✔
251	if ((value & 1) != 0) {	126,666✔
252	return int64_t(value >> 1) == link;	552✔
253	}	552✔
254		63,057✔
255	BPlusTree<int64_t> backlink_list(m_alloc);	126,114✔
256	backlink_list.init_from_ref(ref_type(value));	126,114✔
257		63,057✔
258	return backlink_list.find_first(link) != realm::not_found;	126,114✔
259	#else
260	static_cast<void>(ndx);
261	static_cast<void>(link);
262	return true;
263	#endif
264	}	126,114✔

realm / realm-core / 2109

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous