Berkof commented on a change in pull request #208: URL: https://github.com/apache/ignite-3/pull/208#discussion_r671872893
########## File path: modules/configuration/src/main/java/org/apache/ignite/internal/configuration/tree/OrderedMap.java ########## @@ -0,0 +1,195 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You 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. + */ + +package org.apache.ignite.internal.configuration.tree; + +import java.util.ArrayList; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.Set; + +/** + * Simplified map class that preserves keys order. + * + * @param <V> Type of the value. + */ +class OrderedMap<V> { + /** Underlying hash map. */ + private final Map<String, V> map; + + /** Ordered keys. */ + private final List<String> orderedKeys; + + /** Default constructor. */ + OrderedMap() { + map = new HashMap<>(); + orderedKeys = new ArrayList<>(); + } + + /** + * Copy constructor. + * + * @param other Source of keys/values to copy from. + */ + OrderedMap(OrderedMap<V> other) { + map = new HashMap<>(other.map); + orderedKeys = new ArrayList<>(other.orderedKeys); + } + + /** + * Same as {@link Map#containsKey(Object)}. + * + * @param key Key to check. + * @return {@code true} if map contains the key. + */ + public boolean containsKey(String key) { + return map.containsKey(key); + } + + /** + * Same as {@link Map#get(Object)}. + * + * @param key Key to search. + * @return Value associated with the key or {@code null} is it's not found. + */ + public V get(String key) { + return map.get(key); + } + + /** + * Same as {@link Map#remove(Object)}. + * + * @param key Key to remove. + * @return Previous value associated with the key or {@code null} if the map had no such key. + */ + public V remove(String key) { + if (map.containsKey(key)) + orderedKeys.remove(key); + + return map.remove(key); + } + + /** + * Inserts a value into the map under the specified key. If the key was not present in the map, it will be ordered last. + * ordering index will be used. + * + * @param key Key to put. + * @param value Value associated with the key. + */ + public void put(String key, V value) { + if (map.put(key, value) == null) + orderedKeys.add(key); + } + + /** + * Inserts a value into the map under the specified key. The key will be positioned at the given index, shifting any + * existing values at that position to the right. Key must not be present in the map when the method is called. + * + * @param idx Ordering index for the key. Must be in {@code [0 .. size()]} range. + * @param key Key to put. + * @param value Value associated with the key. + */ + public void putByIndex(int idx, String key, V value) { + assert !map.containsKey(key) : key + " " + map; + + if (idx >= orderedKeys.size()) + orderedKeys.add(key); + else + orderedKeys.add(idx, key); + + map.put(key, value); + } + + /** + * Put value to the map at the position after the {@code precedingKey}. Key must not be present in the map when the + * method is called. + * + * @param precedingKey Previous key for the new key. Last key will be used if this one is missing from the map. Review comment: If there is no such precendingKey in the map - why do we put new value at the end? Should putAfter return flag to mark is precendingKey found? ########## File path: modules/configuration/src/test/java/org/apache/ignite/internal/configuration/tree/OrderedMapTest.java ########## @@ -0,0 +1,154 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You 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. + */ + +package org.apache.ignite.internal.configuration.tree; + +import java.util.List; +import org.junit.jupiter.api.Test; + +import static org.junit.jupiter.api.Assertions.assertEquals; +import static org.junit.jupiter.api.Assertions.assertFalse; +import static org.junit.jupiter.api.Assertions.assertNull; + +/** Test with basic {@link OrderedMap} invariants. */ +public class OrderedMapTest { + /** Map instance. */ + private final OrderedMap<String> map = new OrderedMap<>(); + + /** Tests put/get/remove consistency on a single key. */ + @Test + public void putGetRemove() { + assertNull(map.get("key1")); Review comment: put(null)? get(null)? put(< existingKey >) remove(< nonExistingKey >)? ########## File path: modules/configuration-annotation-processor/src/test/java/org/apache/ignite/internal/configuration/util/ConfigurationUtilTest.java ########## @@ -128,7 +140,7 @@ public void findSuccessfully() { var parent = newParentInstance(); Review comment: JavaDoc for test ########## File path: modules/configuration/src/main/java/org/apache/ignite/internal/configuration/tree/OrderedMap.java ########## @@ -0,0 +1,195 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You 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. + */ + +package org.apache.ignite.internal.configuration.tree; + +import java.util.ArrayList; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.Set; + +/** + * Simplified map class that preserves keys order. + * + * @param <V> Type of the value. + */ +class OrderedMap<V> { + /** Underlying hash map. */ + private final Map<String, V> map; + + /** Ordered keys. */ + private final List<String> orderedKeys; + + /** Default constructor. */ + OrderedMap() { + map = new HashMap<>(); + orderedKeys = new ArrayList<>(); + } + + /** + * Copy constructor. + * + * @param other Source of keys/values to copy from. + */ + OrderedMap(OrderedMap<V> other) { + map = new HashMap<>(other.map); + orderedKeys = new ArrayList<>(other.orderedKeys); + } + + /** + * Same as {@link Map#containsKey(Object)}. + * + * @param key Key to check. + * @return {@code true} if map contains the key. + */ + public boolean containsKey(String key) { + return map.containsKey(key); + } + + /** + * Same as {@link Map#get(Object)}. + * + * @param key Key to search. + * @return Value associated with the key or {@code null} is it's not found. + */ + public V get(String key) { + return map.get(key); + } + + /** + * Same as {@link Map#remove(Object)}. + * + * @param key Key to remove. + * @return Previous value associated with the key or {@code null} if the map had no such key. + */ + public V remove(String key) { + if (map.containsKey(key)) + orderedKeys.remove(key); + + return map.remove(key); + } + + /** + * Inserts a value into the map under the specified key. If the key was not present in the map, it will be ordered last. + * ordering index will be used. + * + * @param key Key to put. + * @param value Value associated with the key. + */ + public void put(String key, V value) { + if (map.put(key, value) == null) + orderedKeys.add(key); + } + + /** + * Inserts a value into the map under the specified key. The key will be positioned at the given index, shifting any + * existing values at that position to the right. Key must not be present in the map when the method is called. + * + * @param idx Ordering index for the key. Must be in {@code [0 .. size()]} range. + * @param key Key to put. + * @param value Value associated with the key. + */ + public void putByIndex(int idx, String key, V value) { + assert !map.containsKey(key) : key + " " + map; + + if (idx >= orderedKeys.size()) + orderedKeys.add(key); + else + orderedKeys.add(idx, key); + + map.put(key, value); + } + + /** + * Put value to the map at the position after the {@code precedingKey}. Key must not be present in the map when the + * method is called. + * + * @param precedingKey Previous key for the new key. Last key will be used if this one is missing from the map. + * @param key Key to put. + * @param value Value associated with the key. + */ + public void putAfter(String precedingKey, String key, V value) { + assert !map.containsKey(key) : key + " " + map; + + int idx = orderedKeys.indexOf(precedingKey); + + putByIndex(idx < 0 ? orderedKeys.size() : idx + 1, key, value); + } + + /** + * Re-associates the value under the {@code oldKey} to the {@code newKey}. Does nothing if the {@code oldKey} + * is not present in the map. + * was missing from the map. + * + * @param oldKey Old key. + * @param newKey New key. + * + * @throws IllegalArgumentException If both {@code oldKey} and {@code newKey} already exist in the map. + */ + public void rename(String oldKey, String newKey) { Review comment: Should map return some false result if oldKey wasn't found? Or throw an exception? ########## File path: modules/table/src/main/java/org/apache/ignite/internal/table/distributed/TableManager.java ########## @@ -575,7 +575,7 @@ else if (tblFut.complete(tbl)) try { configurationMgr.configurationRegistry() .getConfiguration(TablesConfiguration.KEY).tables().change(change -> - change.update(name, tableChange)).get(); + change.createOrUpdate(name, tableChange)).get(); Review comment: Why do we use create in alter? JavaDoc describe it as "Alter a cluster table." so we need Update semantic here. ########## File path: modules/configuration/src/main/java/org/apache/ignite/internal/configuration/util/ConfigurationUtil.java ########## @@ -277,101 +277,73 @@ else if (val instanceof Map) } } } - } - - var src = new InnerConfigurationSource(prefixMap); - - src.descend(node); - } - - /** - * Convert a traversable tree to a map of qualified keys to values. - * - * @param curRoot Current root tree. - * @param updates Tree with updates. - * @return Map of changes. - */ - public static Map<String, Serializable> nodeToFlatMap( - SuperRoot curRoot, - SuperRoot updates - ) { - Map<String, Serializable> values = new HashMap<>(); - updates.traverseChildren(new KeysTrackingConfigurationVisitor<>() { - /** Write nulls instead of actual values. Makes sense for deletions from named lists. */ - private boolean writeNulls; - - /** {@inheritDoc} */ - @Override public Map<String, Serializable> doVisitLeafNode(String key, Serializable val) { - if (val != null) - values.put(currentKey(), writeNulls ? null : val); + /** + * Specific implementation of {@link #descend(ConstructableTreeNode)} that descends into named list node and + * sets a proper ordering to named list elements. + * + * @param node Named list node under construction. + */ + private void descendToNamedListNode(NamedListNode<?> node) { + // This list must be mutable and RandomAccess. + var orderedKeys = new ArrayList<>(((NamedListView<?>)node).namedListKeys()); - return values; - } + for (Map.Entry<String, ?> entry : map.entrySet()) { + String key = entry.getKey(); + Object val = entry.getValue(); - /** {@inheritDoc} */ - @Override public Map<String, Serializable> doVisitInnerNode(String key, InnerNode node) { - if (node == null) - return null; + assert val == null || val instanceof Map || val instanceof Serializable; - node.traverseChildren(this); + if (val == null) { + // Given that this particular method is applied to modify existing trees rather than + // creating new trees, a "hack" is required in this place. "construct" is designed to create + // "change" objects, thus it would just nullify named list element instead of deleting it. + node.forceDelete(key); + } + else if (val instanceof Map) { + // For every named list entry modification we must take its index into account. + // We do this by modifying "orderedKeys" when index is explicitly passed. + Object idxObj = ((Map<?, ?>)val).get(NamedListNode.ORDER_IDX); - return values; - } + if (idxObj != null) { + assert idxObj instanceof Integer : val; - /** {@inheritDoc} */ - @Override public <N extends InnerNode> Map<String, Serializable> doVisitNamedListNode(String key, NamedListNode<N> node) { - for (String namedListKey : node.namedListKeys()) { - N namedElement = node.get(namedListKey); - - withTracking(namedListKey, true, false, () -> { - if (namedElement == null) - visitDeletedNamedListElement(); - else - namedElement.traverseChildren(this); - - return null; - }); - } + int idx = (Integer)idxObj; - return values; - } + if (idx >= orderedKeys.size()) { + // Updates can come in arbitrary order. This means that array may be too small + // during batch creation. In this case we have to insert enough nulls before + // invoking "add" method for actual key. + orderedKeys.ensureCapacity(idx + 1); - /** - * Here we must list all joined keys belonging to deleted element. The only way to do it is to traverse - * cached configuration tree and write {@code null} into all values. - */ - private void visitDeletedNamedListElement() { - // It must be impossible to delete something inside of the element that we're currently deleting. - assert !writeNulls; + while (idx != orderedKeys.size()) + orderedKeys.add(null); - Object originalNamedElement = null; + orderedKeys.add(idx, key); Review comment: orderedKeys.add(key) is enough here. ########## File path: modules/runner/src/integrationTest/java/org/apache/ignite/internal/runner/app/AbstractSchemaChangeTest.java ########## @@ -166,7 +166,7 @@ protected void renameColumn(List<Ignite> nodes, String oldName, String newName) }); tblChanger.changeColumns(listChanger -> - listChanger.update(colKey, colChanger -> colChanger.changeName(newName)) + listChanger.createOrUpdate(colKey, colChanger -> colChanger.changeName(newName)) Review comment: rename should use update? ########## File path: modules/configuration/src/main/java/org/apache/ignite/internal/configuration/tree/OrderedMap.java ########## @@ -0,0 +1,195 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You 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. + */ + +package org.apache.ignite.internal.configuration.tree; + +import java.util.ArrayList; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.Set; + +/** + * Simplified map class that preserves keys order. + * + * @param <V> Type of the value. + */ +class OrderedMap<V> { + /** Underlying hash map. */ + private final Map<String, V> map; + + /** Ordered keys. */ + private final List<String> orderedKeys; + + /** Default constructor. */ + OrderedMap() { + map = new HashMap<>(); + orderedKeys = new ArrayList<>(); + } + + /** + * Copy constructor. + * + * @param other Source of keys/values to copy from. + */ + OrderedMap(OrderedMap<V> other) { + map = new HashMap<>(other.map); + orderedKeys = new ArrayList<>(other.orderedKeys); + } + + /** + * Same as {@link Map#containsKey(Object)}. + * + * @param key Key to check. + * @return {@code true} if map contains the key. + */ + public boolean containsKey(String key) { + return map.containsKey(key); + } + + /** + * Same as {@link Map#get(Object)}. + * + * @param key Key to search. + * @return Value associated with the key or {@code null} is it's not found. + */ + public V get(String key) { + return map.get(key); + } + + /** + * Same as {@link Map#remove(Object)}. + * + * @param key Key to remove. + * @return Previous value associated with the key or {@code null} if the map had no such key. + */ + public V remove(String key) { + if (map.containsKey(key)) + orderedKeys.remove(key); + + return map.remove(key); + } + + /** + * Inserts a value into the map under the specified key. If the key was not present in the map, it will be ordered last. + * ordering index will be used. + * + * @param key Key to put. + * @param value Value associated with the key. + */ + public void put(String key, V value) { + if (map.put(key, value) == null) + orderedKeys.add(key); + } + + /** + * Inserts a value into the map under the specified key. The key will be positioned at the given index, shifting any + * existing values at that position to the right. Key must not be present in the map when the method is called. + * + * @param idx Ordering index for the key. Must be in {@code [0 .. size()]} range. + * @param key Key to put. + * @param value Value associated with the key. + */ + public void putByIndex(int idx, String key, V value) { + assert !map.containsKey(key) : key + " " + map; + + if (idx >= orderedKeys.size()) Review comment: Should have different javadoc or throw exception in case of idx > size. ########## File path: modules/configuration/src/test/java/org/apache/ignite/internal/configuration/tree/OrderedMapTest.java ########## @@ -0,0 +1,154 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You 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. + */ + +package org.apache.ignite.internal.configuration.tree; + +import java.util.List; +import org.junit.jupiter.api.Test; + +import static org.junit.jupiter.api.Assertions.assertEquals; +import static org.junit.jupiter.api.Assertions.assertFalse; +import static org.junit.jupiter.api.Assertions.assertNull; + +/** Test with basic {@link OrderedMap} invariants. */ +public class OrderedMapTest { + /** Map instance. */ + private final OrderedMap<String> map = new OrderedMap<>(); + + /** Tests put/get/remove consistency on a single key. */ + @Test + public void putGetRemove() { + assertNull(map.get("key1")); + + map.put("key", "value"); + + assertEquals(1, map.size()); + assertEquals("value", map.get("key")); + + map.remove("key"); + + assertNull(map.get("key1")); + } + + /** Tests that {@link OrderedMap#put(String, Object)} preserves order. */ + @Test + public void keysOrder() { + map.put("key1", "value1"); + map.put("key2", "value2"); + + assertEquals(2, map.size()); + assertEquals(List.of("key1", "key2"), map.keys()); + + map.clear(); + + assertEquals(0, map.size()); + assertEquals(List.of(), map.keys()); + + map.put("key2", "value2"); + map.put("key1", "value1"); + + assertEquals(2, map.size()); + assertEquals(List.of("key2", "key1"), map.keys()); + + map.put("key2", "value3"); + assertEquals(List.of("key2", "key1"), map.keys()); + } + + /** Tests that {@link OrderedMap#putByIndex(int, String, Object)} preserves order. */ + @Test + public void putByIndex() { + map.putByIndex(0, "key1", "value1"); + + map.putByIndex(0, "key2", "value2"); + + assertEquals(List.of("key2", "key1"), map.keys()); + + map.putByIndex(1, "key3", "value3"); + + assertEquals(List.of("key2", "key3", "key1"), map.keys()); + + map.putByIndex(3, "key4", "value4"); + + assertEquals(List.of("key2", "key3", "key1", "key4"), map.keys()); + + map.putByIndex(5, "key5", "value5"); + + assertEquals(List.of("key2", "key3", "key1", "key4", "key5"), map.keys()); + } + + /** Tests that {@link OrderedMap#putAfter(String, String, Object)} preserves order. */ + @Test + public void putAfter() { + map.putAfter("foo", "key1", "value1"); + + assertEquals(List.of("key1"), map.keys()); + + map.putAfter("key1", "key2", "value2"); + + assertEquals(List.of("key1", "key2"), map.keys()); + + map.putAfter("key1", "key3", "value3"); + + assertEquals(List.of("key1", "key3", "key2"), map.keys()); + + map.putAfter("key2", "key4", "value4"); + + assertEquals(List.of("key1", "key3", "key2", "key4"), map.keys()); + + map.putAfter("foo", "key5", "value5"); + + assertEquals(List.of("key1", "key3", "key2", "key4", "key5"), map.keys()); + } + + /** Tests basic invariants of {@link OrderedMap#rename(String, String)} method. */ + @Test + public void rename() { + map.put("key1", "value1"); + map.put("key2", "value2"); + map.put("key3", "value3"); + + map.rename("key2", "key4"); + + assertEquals("value2", map.get("key4")); + + assertFalse(map.containsKey("key2")); + + assertEquals(List.of("key1", "key4", "key3"), map.keys()); + } + + /** Tests that {@link OrderedMap#reorderKeys(List)} reorders keys properly. */ + @Test + public void reorderKeys() { + map.put("key1", "value1"); + map.put("key2", "value2"); + map.put("key3", "value3"); + + assertEquals(List.of("key1", "key2", "key3"), map.keys()); + + map.reorderKeys(List.of("key2", "key1", "key3")); + + assertEquals(List.of("key2", "key1", "key3"), map.keys()); + + map.reorderKeys(List.of("key2", "key3", "key1")); + + assertEquals(List.of("key2", "key3", "key1"), map.keys()); + + map.reorderKeys(List.of("key1", "key3", "key2")); + + assertEquals(List.of("key1", "key3", "key2"), map.keys()); Review comment: Reorder to: * List.of("key1", "key1", "key2")? * List.of("key1", "key1", "key2", "key3")? ########## File path: modules/configuration/src/test/java/org/apache/ignite/internal/configuration/tree/OrderedMapTest.java ########## @@ -0,0 +1,154 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You 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. + */ + +package org.apache.ignite.internal.configuration.tree; + +import java.util.List; +import org.junit.jupiter.api.Test; + +import static org.junit.jupiter.api.Assertions.assertEquals; +import static org.junit.jupiter.api.Assertions.assertFalse; +import static org.junit.jupiter.api.Assertions.assertNull; + +/** Test with basic {@link OrderedMap} invariants. */ +public class OrderedMapTest { + /** Map instance. */ + private final OrderedMap<String> map = new OrderedMap<>(); + + /** Tests put/get/remove consistency on a single key. */ + @Test + public void putGetRemove() { + assertNull(map.get("key1")); + + map.put("key", "value"); + + assertEquals(1, map.size()); + assertEquals("value", map.get("key")); + + map.remove("key"); + + assertNull(map.get("key1")); + } + + /** Tests that {@link OrderedMap#put(String, Object)} preserves order. */ + @Test + public void keysOrder() { + map.put("key1", "value1"); + map.put("key2", "value2"); + + assertEquals(2, map.size()); + assertEquals(List.of("key1", "key2"), map.keys()); + + map.clear(); + + assertEquals(0, map.size()); + assertEquals(List.of(), map.keys()); + + map.put("key2", "value2"); + map.put("key1", "value1"); + + assertEquals(2, map.size()); + assertEquals(List.of("key2", "key1"), map.keys()); + + map.put("key2", "value3"); + assertEquals(List.of("key2", "key1"), map.keys()); + } + + /** Tests that {@link OrderedMap#putByIndex(int, String, Object)} preserves order. */ + @Test + public void putByIndex() { + map.putByIndex(0, "key1", "value1"); Review comment: Let's check negative indexes. ########## File path: modules/configuration/src/test/java/org/apache/ignite/internal/configuration/tree/OrderedMapTest.java ########## @@ -0,0 +1,154 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You 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. + */ + +package org.apache.ignite.internal.configuration.tree; + +import java.util.List; +import org.junit.jupiter.api.Test; + +import static org.junit.jupiter.api.Assertions.assertEquals; +import static org.junit.jupiter.api.Assertions.assertFalse; +import static org.junit.jupiter.api.Assertions.assertNull; + +/** Test with basic {@link OrderedMap} invariants. */ +public class OrderedMapTest { + /** Map instance. */ + private final OrderedMap<String> map = new OrderedMap<>(); + + /** Tests put/get/remove consistency on a single key. */ + @Test + public void putGetRemove() { + assertNull(map.get("key1")); + + map.put("key", "value"); + + assertEquals(1, map.size()); + assertEquals("value", map.get("key")); + + map.remove("key"); + + assertNull(map.get("key1")); + } + + /** Tests that {@link OrderedMap#put(String, Object)} preserves order. */ + @Test + public void keysOrder() { + map.put("key1", "value1"); + map.put("key2", "value2"); + + assertEquals(2, map.size()); + assertEquals(List.of("key1", "key2"), map.keys()); + + map.clear(); + + assertEquals(0, map.size()); + assertEquals(List.of(), map.keys()); + + map.put("key2", "value2"); + map.put("key1", "value1"); + + assertEquals(2, map.size()); + assertEquals(List.of("key2", "key1"), map.keys()); + + map.put("key2", "value3"); + assertEquals(List.of("key2", "key1"), map.keys()); + } + + /** Tests that {@link OrderedMap#putByIndex(int, String, Object)} preserves order. */ + @Test + public void putByIndex() { + map.putByIndex(0, "key1", "value1"); + + map.putByIndex(0, "key2", "value2"); + + assertEquals(List.of("key2", "key1"), map.keys()); + + map.putByIndex(1, "key3", "value3"); + + assertEquals(List.of("key2", "key3", "key1"), map.keys()); + + map.putByIndex(3, "key4", "value4"); + + assertEquals(List.of("key2", "key3", "key1", "key4"), map.keys()); + + map.putByIndex(5, "key5", "value5"); + + assertEquals(List.of("key2", "key3", "key1", "key4", "key5"), map.keys()); + } + + /** Tests that {@link OrderedMap#putAfter(String, String, Object)} preserves order. */ + @Test + public void putAfter() { + map.putAfter("foo", "key1", "value1"); Review comment: Let's put existing value. ########## File path: modules/configuration/src/main/java/org/apache/ignite/internal/configuration/util/ConfigurationUtil.java ########## @@ -277,101 +277,73 @@ else if (val instanceof Map) } } } - } - - var src = new InnerConfigurationSource(prefixMap); - - src.descend(node); - } - - /** - * Convert a traversable tree to a map of qualified keys to values. - * - * @param curRoot Current root tree. - * @param updates Tree with updates. - * @return Map of changes. - */ - public static Map<String, Serializable> nodeToFlatMap( - SuperRoot curRoot, - SuperRoot updates - ) { - Map<String, Serializable> values = new HashMap<>(); - updates.traverseChildren(new KeysTrackingConfigurationVisitor<>() { - /** Write nulls instead of actual values. Makes sense for deletions from named lists. */ - private boolean writeNulls; - - /** {@inheritDoc} */ - @Override public Map<String, Serializable> doVisitLeafNode(String key, Serializable val) { - if (val != null) - values.put(currentKey(), writeNulls ? null : val); + /** + * Specific implementation of {@link #descend(ConstructableTreeNode)} that descends into named list node and + * sets a proper ordering to named list elements. + * + * @param node Named list node under construction. + */ + private void descendToNamedListNode(NamedListNode<?> node) { + // This list must be mutable and RandomAccess. + var orderedKeys = new ArrayList<>(((NamedListView<?>)node).namedListKeys()); - return values; - } + for (Map.Entry<String, ?> entry : map.entrySet()) { + String key = entry.getKey(); + Object val = entry.getValue(); - /** {@inheritDoc} */ - @Override public Map<String, Serializable> doVisitInnerNode(String key, InnerNode node) { - if (node == null) - return null; + assert val == null || val instanceof Map || val instanceof Serializable; - node.traverseChildren(this); + if (val == null) { + // Given that this particular method is applied to modify existing trees rather than + // creating new trees, a "hack" is required in this place. "construct" is designed to create + // "change" objects, thus it would just nullify named list element instead of deleting it. + node.forceDelete(key); + } + else if (val instanceof Map) { + // For every named list entry modification we must take its index into account. + // We do this by modifying "orderedKeys" when index is explicitly passed. + Object idxObj = ((Map<?, ?>)val).get(NamedListNode.ORDER_IDX); - return values; - } + if (idxObj != null) { + assert idxObj instanceof Integer : val; - /** {@inheritDoc} */ - @Override public <N extends InnerNode> Map<String, Serializable> doVisitNamedListNode(String key, NamedListNode<N> node) { - for (String namedListKey : node.namedListKeys()) { - N namedElement = node.get(namedListKey); - - withTracking(namedListKey, true, false, () -> { - if (namedElement == null) - visitDeletedNamedListElement(); - else - namedElement.traverseChildren(this); - - return null; - }); - } + int idx = (Integer)idxObj; - return values; - } + if (idx >= orderedKeys.size()) { + // Updates can come in arbitrary order. This means that array may be too small + // during batch creation. In this case we have to insert enough nulls before + // invoking "add" method for actual key. + orderedKeys.ensureCapacity(idx + 1); - /** - * Here we must list all joined keys belonging to deleted element. The only way to do it is to traverse - * cached configuration tree and write {@code null} into all values. - */ - private void visitDeletedNamedListElement() { - // It must be impossible to delete something inside of the element that we're currently deleting. - assert !writeNulls; + while (idx != orderedKeys.size()) + orderedKeys.add(null); - Object originalNamedElement = null; + orderedKeys.add(idx, key); + } + else + orderedKeys.set(idx, key); + } - List<String> currentPath = currentPath(); + node.construct(key, new InnerConfigurationSource((Map<String, ?>)val)); + } + else { + assert val instanceof Serializable; - try { - // This code can in fact be better optimized for deletion scenario, - // but there's no point in doing that, since the operation is so rare and it will - // complicate code even more. - originalNamedElement = find(currentPath, curRoot); - } - catch (KeyNotFoundException ignore) { - // May happen, not a big deal. This means that element never existed in the first place. + node.construct(key, new LeafConfigurationSource((Serializable)val)); Review comment: Does it mean that for primitive values we'll never keep order? ########## File path: modules/configuration/src/main/java/org/apache/ignite/internal/configuration/tree/OrderedMap.java ########## @@ -0,0 +1,195 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You 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. + */ + +package org.apache.ignite.internal.configuration.tree; + +import java.util.ArrayList; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.Set; + +/** + * Simplified map class that preserves keys order. + * + * @param <V> Type of the value. + */ +class OrderedMap<V> { + /** Underlying hash map. */ + private final Map<String, V> map; + + /** Ordered keys. */ + private final List<String> orderedKeys; + + /** Default constructor. */ + OrderedMap() { + map = new HashMap<>(); + orderedKeys = new ArrayList<>(); + } + + /** + * Copy constructor. + * + * @param other Source of keys/values to copy from. + */ + OrderedMap(OrderedMap<V> other) { + map = new HashMap<>(other.map); + orderedKeys = new ArrayList<>(other.orderedKeys); + } + + /** + * Same as {@link Map#containsKey(Object)}. + * + * @param key Key to check. + * @return {@code true} if map contains the key. + */ + public boolean containsKey(String key) { + return map.containsKey(key); + } + + /** + * Same as {@link Map#get(Object)}. + * + * @param key Key to search. + * @return Value associated with the key or {@code null} is it's not found. + */ + public V get(String key) { + return map.get(key); + } + + /** + * Same as {@link Map#remove(Object)}. + * + * @param key Key to remove. + * @return Previous value associated with the key or {@code null} if the map had no such key. + */ + public V remove(String key) { + if (map.containsKey(key)) + orderedKeys.remove(key); + + return map.remove(key); + } + + /** + * Inserts a value into the map under the specified key. If the key was not present in the map, it will be ordered last. + * ordering index will be used. + * + * @param key Key to put. + * @param value Value associated with the key. + */ + public void put(String key, V value) { + if (map.put(key, value) == null) + orderedKeys.add(key); + } + + /** + * Inserts a value into the map under the specified key. The key will be positioned at the given index, shifting any + * existing values at that position to the right. Key must not be present in the map when the method is called. + * + * @param idx Ordering index for the key. Must be in {@code [0 .. size()]} range. + * @param key Key to put. + * @param value Value associated with the key. + */ + public void putByIndex(int idx, String key, V value) { + assert !map.containsKey(key) : key + " " + map; + + if (idx >= orderedKeys.size()) + orderedKeys.add(key); + else + orderedKeys.add(idx, key); + + map.put(key, value); + } + + /** + * Put value to the map at the position after the {@code precedingKey}. Key must not be present in the map when the + * method is called. + * + * @param precedingKey Previous key for the new key. Last key will be used if this one is missing from the map. + * @param key Key to put. + * @param value Value associated with the key. + */ + public void putAfter(String precedingKey, String key, V value) { + assert !map.containsKey(key) : key + " " + map; + + int idx = orderedKeys.indexOf(precedingKey); + + putByIndex(idx < 0 ? orderedKeys.size() : idx + 1, key, value); + } + + /** + * Re-associates the value under the {@code oldKey} to the {@code newKey}. Does nothing if the {@code oldKey} + * is not present in the map. + * was missing from the map. + * + * @param oldKey Old key. + * @param newKey New key. + * + * @throws IllegalArgumentException If both {@code oldKey} and {@code newKey} already exist in the map. + */ + public void rename(String oldKey, String newKey) { + if (!map.containsKey(oldKey)) + return; + + if (map.containsKey(newKey)) + throw new IllegalArgumentException(); + + int idx = orderedKeys.indexOf(oldKey); + + orderedKeys.set(idx, newKey); + + V value = map.remove(oldKey); + + map.put(newKey, value); + } + + /** + * @return List of keys. + */ + public List<String> keys() { + return new ArrayList<>(orderedKeys); + } + + /** + * Reorders keys in the map. + * + * @param orderedKeys List of keys in new order. Must have the same set of keys in it. + */ + public void reorderKeys(List<String> orderedKeys) { + assert map.keySet().equals(Set.copyOf(orderedKeys)) : map.keySet() + " : " + orderedKeys; Review comment: Why do we check it in assertion while in other methods arguments are checked in regular code? ########## File path: modules/configuration/src/main/java/org/apache/ignite/internal/configuration/tree/OrderedMap.java ########## @@ -0,0 +1,195 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You 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. + */ + +package org.apache.ignite.internal.configuration.tree; + +import java.util.ArrayList; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.Set; + +/** + * Simplified map class that preserves keys order. + * + * @param <V> Type of the value. + */ +class OrderedMap<V> { + /** Underlying hash map. */ + private final Map<String, V> map; + + /** Ordered keys. */ + private final List<String> orderedKeys; + + /** Default constructor. */ + OrderedMap() { + map = new HashMap<>(); + orderedKeys = new ArrayList<>(); + } + + /** + * Copy constructor. + * + * @param other Source of keys/values to copy from. + */ + OrderedMap(OrderedMap<V> other) { + map = new HashMap<>(other.map); + orderedKeys = new ArrayList<>(other.orderedKeys); + } + + /** + * Same as {@link Map#containsKey(Object)}. + * + * @param key Key to check. + * @return {@code true} if map contains the key. + */ + public boolean containsKey(String key) { + return map.containsKey(key); + } + + /** + * Same as {@link Map#get(Object)}. + * + * @param key Key to search. + * @return Value associated with the key or {@code null} is it's not found. + */ + public V get(String key) { + return map.get(key); + } + + /** + * Same as {@link Map#remove(Object)}. + * + * @param key Key to remove. + * @return Previous value associated with the key or {@code null} if the map had no such key. + */ + public V remove(String key) { + if (map.containsKey(key)) + orderedKeys.remove(key); + + return map.remove(key); + } + + /** + * Inserts a value into the map under the specified key. If the key was not present in the map, it will be ordered last. + * ordering index will be used. + * + * @param key Key to put. + * @param value Value associated with the key. + */ + public void put(String key, V value) { + if (map.put(key, value) == null) Review comment: Can OrderedMap store null values? If yes - it's not correct check, if no - a few other methods can be rewritten (for example, remove: V res = map.remove() if (V != null) orderedKeys.remove(key); return res; ) ########## File path: modules/configuration/src/main/java/org/apache/ignite/internal/configuration/tree/NamedListNode.java ########## @@ -18,22 +18,22 @@ package org.apache.ignite.internal.configuration.tree; import java.util.Collections; -import java.util.HashMap; -import java.util.Map; +import java.util.List; import java.util.Objects; -import java.util.Set; import java.util.function.Consumer; import java.util.function.Supplier; import org.apache.ignite.configuration.NamedListChange; -import org.apache.ignite.configuration.NamedListView; /** */ Review comment: JavaDoc ########## File path: modules/configuration-annotation-processor/src/test/java/org/apache/ignite/internal/configuration/tree/NamedListOrderTest.java ########## @@ -0,0 +1,234 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You 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. + */ + +package org.apache.ignite.internal.configuration.tree; + +import java.util.Map; +import org.apache.ignite.configuration.NamedListChange; +import org.apache.ignite.configuration.annotation.Config; +import org.apache.ignite.configuration.annotation.ConfigurationRoot; +import org.apache.ignite.configuration.annotation.NamedConfigValue; +import org.apache.ignite.configuration.annotation.Value; +import org.apache.ignite.internal.configuration.TestConfigurationChanger; +import org.apache.ignite.internal.configuration.asm.ConfigurationAsmGenerator; +import org.apache.ignite.internal.configuration.storage.TestConfigurationStorage; +import org.junit.jupiter.api.AfterAll; +import org.junit.jupiter.api.AfterEach; +import org.junit.jupiter.api.BeforeAll; +import org.junit.jupiter.api.BeforeEach; +import org.junit.jupiter.api.Test; + +import static org.junit.jupiter.api.Assertions.assertEquals; +import static org.junit.jupiter.api.Assertions.assertThrows; + +/** Test for keys ordering in named list nodes. */ +public class NamedListOrderTest { + /** Root that has a single named list. */ + @ConfigurationRoot(rootName = "a") + public static class AConfigurationSchema { + /** */ + @NamedConfigValue + public BConfigurationSchema b; + } + + /** Named list element node that in inself contains another named list. */ + @Config + public static class BConfigurationSchema { + /** Every named list element node must have at least one configuration field that is not named list. */ + @Value(hasDefault = true) + public String c = "foo"; + + @NamedConfigValue + public BConfigurationSchema b; + } + + /** Runtime implementations generator. */ + private static ConfigurationAsmGenerator cgen; + + /** Test configuration storage. */ + private TestConfigurationStorage storage; + + /** Test configuration changer. */ + private TestConfigurationChanger changer; + + /** Instantiates {@link #cgen}. */ + @BeforeAll + public static void beforeAll() { + cgen = new ConfigurationAsmGenerator(); + } + + /** Nullifies {@link #cgen} to prevent memory leak from having runtime ClassLoader accessible from GC root. */ + @AfterAll + public static void afterAll() { + cgen = null; + } + + /** */ + @BeforeEach + public void before() { + storage = new TestConfigurationStorage(); + + changer = new TestConfigurationChanger(cgen); + changer.addRootKey(AConfiguration.KEY); + changer.register(storage); + } + + /** */ + @AfterEach + public void after() { + changer.stop(); + } + + /** + * Tests that there are no unnecessary {@code <idx>} values in the storage after all basic named list operations. + * + * @throws Exception If failed. + */ + @Test + public void storageData() throws Exception { + // Manually instantiate configuration instance. + var a = (AConfiguration)cgen.instantiateCfg(AConfiguration.KEY, changer); + + // Create values on several layers at the same time. They all shoud have <idx> = 0. Review comment: shou**l**d ########## File path: modules/configuration/src/main/java/org/apache/ignite/internal/configuration/tree/NamedListNode.java ########## @@ -18,22 +18,22 @@ package org.apache.ignite.internal.configuration.tree; import java.util.Collections; -import java.util.HashMap; -import java.util.Map; +import java.util.List; import java.util.Objects; -import java.util.Set; import java.util.function.Consumer; import java.util.function.Supplier; import org.apache.ignite.configuration.NamedListChange; -import org.apache.ignite.configuration.NamedListView; /** */ -public final class NamedListNode<N extends InnerNode> implements NamedListView<N>, NamedListChange<N>, TraversableTreeNode, ConstructableTreeNode { +public final class NamedListNode<N extends InnerNode> implements NamedListChange<N>, TraversableTreeNode, ConstructableTreeNode { + /** Name of a synthetic configuration property that describes the order of elements in a named list. */ + public static final String ORDER_IDX = "<idx>"; + /** */ Review comment: JavaDoc ########## File path: modules/configuration/src/main/java/org/apache/ignite/internal/configuration/tree/NamedListNode.java ########## @@ -18,22 +18,22 @@ package org.apache.ignite.internal.configuration.tree; import java.util.Collections; -import java.util.HashMap; -import java.util.Map; +import java.util.List; import java.util.Objects; -import java.util.Set; import java.util.function.Consumer; import java.util.function.Supplier; import org.apache.ignite.configuration.NamedListChange; -import org.apache.ignite.configuration.NamedListView; /** */ -public final class NamedListNode<N extends InnerNode> implements NamedListView<N>, NamedListChange<N>, TraversableTreeNode, ConstructableTreeNode { +public final class NamedListNode<N extends InnerNode> implements NamedListChange<N>, TraversableTreeNode, ConstructableTreeNode { + /** Name of a synthetic configuration property that describes the order of elements in a named list. */ + public static final String ORDER_IDX = "<idx>"; + /** */ - public final Supplier<N> valSupplier; + private final Supplier<N> valSupplier; /** */ Review comment: JavaDoc ########## File path: modules/configuration/src/test/java/org/apache/ignite/internal/configuration/tree/OrderedMapTest.java ########## @@ -0,0 +1,154 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You 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. + */ + +package org.apache.ignite.internal.configuration.tree; + +import java.util.List; +import org.junit.jupiter.api.Test; + +import static org.junit.jupiter.api.Assertions.assertEquals; +import static org.junit.jupiter.api.Assertions.assertFalse; +import static org.junit.jupiter.api.Assertions.assertNull; + +/** Test with basic {@link OrderedMap} invariants. */ +public class OrderedMapTest { + /** Map instance. */ + private final OrderedMap<String> map = new OrderedMap<>(); + + /** Tests put/get/remove consistency on a single key. */ + @Test + public void putGetRemove() { + assertNull(map.get("key1")); + + map.put("key", "value"); + + assertEquals(1, map.size()); + assertEquals("value", map.get("key")); + + map.remove("key"); + + assertNull(map.get("key1")); + } + + /** Tests that {@link OrderedMap#put(String, Object)} preserves order. */ + @Test + public void keysOrder() { + map.put("key1", "value1"); + map.put("key2", "value2"); + + assertEquals(2, map.size()); + assertEquals(List.of("key1", "key2"), map.keys()); + + map.clear(); + + assertEquals(0, map.size()); + assertEquals(List.of(), map.keys()); + + map.put("key2", "value2"); + map.put("key1", "value1"); + + assertEquals(2, map.size()); + assertEquals(List.of("key2", "key1"), map.keys()); + + map.put("key2", "value3"); + assertEquals(List.of("key2", "key1"), map.keys()); + } + + /** Tests that {@link OrderedMap#putByIndex(int, String, Object)} preserves order. */ + @Test + public void putByIndex() { + map.putByIndex(0, "key1", "value1"); + + map.putByIndex(0, "key2", "value2"); + + assertEquals(List.of("key2", "key1"), map.keys()); + + map.putByIndex(1, "key3", "value3"); + + assertEquals(List.of("key2", "key3", "key1"), map.keys()); + + map.putByIndex(3, "key4", "value4"); + + assertEquals(List.of("key2", "key3", "key1", "key4"), map.keys()); + + map.putByIndex(5, "key5", "value5"); + + assertEquals(List.of("key2", "key3", "key1", "key4", "key5"), map.keys()); + } + + /** Tests that {@link OrderedMap#putAfter(String, String, Object)} preserves order. */ + @Test + public void putAfter() { + map.putAfter("foo", "key1", "value1"); + + assertEquals(List.of("key1"), map.keys()); + + map.putAfter("key1", "key2", "value2"); + + assertEquals(List.of("key1", "key2"), map.keys()); + + map.putAfter("key1", "key3", "value3"); + + assertEquals(List.of("key1", "key3", "key2"), map.keys()); + + map.putAfter("key2", "key4", "value4"); + + assertEquals(List.of("key1", "key3", "key2", "key4"), map.keys()); + + map.putAfter("foo", "key5", "value5"); + + assertEquals(List.of("key1", "key3", "key2", "key4", "key5"), map.keys()); + } + + /** Tests basic invariants of {@link OrderedMap#rename(String, String)} method. */ + @Test + public void rename() { + map.put("key1", "value1"); Review comment: Rename to existing value? Rename not presented key? -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
