From 27ce190366ae9efbce8c3a4b21c81cb20b10b8e3 Mon Sep 17 00:00:00 2001 From: Robert Varga Date: Thu, 18 Feb 2021 01:25:14 +0100 Subject: [PATCH] CopyHistory should be an interface We currently use some complicated machinery to keep a low number of CopyHistory instances. As it turns out, though, these objects encode only 4 bits worth of information. Turn CopyHistory into an interface and have StatementContextBase implement it directly. This allows us to use a single byte to realize its storage needs instead of having an explicit reference, while also maintaining external interface. Improvement in storage, coupled with the previous ExecutionOrder work results in reduction of InferredStatementContext and SubstatementContext by 0/8/8/16 bytes. We also have a 2-byte alignment shadow in which we can store further state. JIRA: YANGTOOLS-1255 JIRA: YANGTOOLS-1150 Change-Id: I04b8761cabc266ffc25cdeedc5a0fa1a0ffe424a Signed-off-by: Robert Varga --- .../src/main/java/module-info.java | 1 + .../reactor/AbstractResumedStatement.java | 3 +- .../reactor/InferredStatementContext.java | 4 +- .../stmt/reactor/StatementContextBase.java | 80 +++++++++- .../yang/parser/spi/meta/CopyHistory.java | 143 ++---------------- .../yang/parser/spi/meta/CopyHistoryTest.java | 71 --------- 6 files changed, 91 insertions(+), 211 deletions(-) delete mode 100644 yang/yang-parser-spi/src/test/java/org/opendaylight/yangtools/yang/parser/spi/meta/CopyHistoryTest.java diff --git a/yang/yang-parser-reactor/src/main/java/module-info.java b/yang/yang-parser-reactor/src/main/java/module-info.java index 6e18346114..9aeb3087ae 100644 --- a/yang/yang-parser-reactor/src/main/java/module-info.java +++ b/yang/yang-parser-reactor/src/main/java/module-info.java @@ -9,6 +9,7 @@ module org.opendaylight.yangtools.yang.parser.reactor { exports org.opendaylight.yangtools.yang.parser.stmt.reactor; requires transitive org.opendaylight.yangtools.yang.parser.spi; + requires com.google.common; requires org.opendaylight.yangtools.concepts; requires org.opendaylight.yangtools.yang.model.spi; requires org.slf4j; diff --git a/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/AbstractResumedStatement.java b/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/AbstractResumedStatement.java index 8699162247..20a390d1e5 100644 --- a/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/AbstractResumedStatement.java +++ b/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/AbstractResumedStatement.java @@ -20,7 +20,6 @@ import org.eclipse.jdt.annotation.Nullable; import org.opendaylight.yangtools.yang.model.api.meta.DeclaredStatement; import org.opendaylight.yangtools.yang.model.api.meta.EffectiveStatement; import org.opendaylight.yangtools.yang.model.api.meta.StatementDefinition; -import org.opendaylight.yangtools.yang.parser.spi.meta.CopyHistory; import org.opendaylight.yangtools.yang.parser.spi.meta.CopyType; import org.opendaylight.yangtools.yang.parser.spi.meta.ModelProcessingPhase; import org.opendaylight.yangtools.yang.parser.spi.meta.StatementSupport; @@ -68,7 +67,7 @@ abstract class AbstractResumedStatement, E ext AbstractResumedStatement(final StatementDefinitionContext def, final StatementSourceReference ref, final String rawArgument, final CopyType copyType) { - super(def, CopyHistory.of(copyType, CopyHistory.original())); + super(def, copyType); this.statementDeclSource = requireNonNull(ref); this.rawArgument = rawArgument; } diff --git a/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/InferredStatementContext.java b/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/InferredStatementContext.java index dc019f1e2e..6d69012b99 100644 --- a/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/InferredStatementContext.java +++ b/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/InferredStatementContext.java @@ -34,7 +34,6 @@ import org.opendaylight.yangtools.yang.model.api.meta.EffectiveStatement; import org.opendaylight.yangtools.yang.model.api.meta.StatementDefinition; import org.opendaylight.yangtools.yang.model.api.stmt.SchemaTreeEffectiveStatement; import org.opendaylight.yangtools.yang.parser.spi.SchemaTreeNamespace; -import org.opendaylight.yangtools.yang.parser.spi.meta.CopyHistory; import org.opendaylight.yangtools.yang.parser.spi.meta.CopyType; import org.opendaylight.yangtools.yang.parser.spi.meta.EffectiveStatementStateAware; import org.opendaylight.yangtools.yang.parser.spi.meta.InferenceException; @@ -89,6 +88,7 @@ final class InferredStatementContext, E extend private final @NonNull StatementContextBase prototype; private final @NonNull StatementContextBase parent; private final @NonNull StmtContext originalCtx; + // TODO: consider encoding this in StatementContextBase fields, there should be plenty of room private final @NonNull CopyType childCopyType; private final QNameModule targetModule; private final A argument; @@ -119,7 +119,7 @@ final class InferredStatementContext, E extend InferredStatementContext(final StatementContextBase parent, final StatementContextBase prototype, final CopyType myCopyType, final CopyType childCopyType, final QNameModule targetModule) { - super(prototype.definition(), CopyHistory.of(myCopyType, prototype.history())); + super(prototype, myCopyType); this.parent = requireNonNull(parent); this.prototype = requireNonNull(prototype); this.argument = targetModule == null ? prototype.argument() diff --git a/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/StatementContextBase.java b/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/StatementContextBase.java index 71fdd107bf..109ffbc537 100644 --- a/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/StatementContextBase.java +++ b/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/StatementContextBase.java @@ -14,6 +14,7 @@ import static com.google.common.base.Verify.verifyNotNull; import static java.util.Objects.requireNonNull; import com.google.common.annotations.Beta; +import com.google.common.base.VerifyException; import com.google.common.collect.ImmutableCollection; import com.google.common.collect.ImmutableList; import com.google.common.collect.ImmutableMultimap; @@ -64,7 +65,7 @@ import org.slf4j.LoggerFactory; * @param Effective Statement representation */ public abstract class StatementContextBase, E extends EffectiveStatement> - extends ReactorStmtCtx { + extends ReactorStmtCtx implements CopyHistory { /** * Event listener when an item is added to model namespace. */ @@ -95,7 +96,22 @@ public abstract class StatementContextBase, E private static final Logger LOG = LoggerFactory.getLogger(StatementContextBase.class); - private final CopyHistory copyHistory; + // + // {@link CopyHistory} encoded as a single byte. We still have 4 bits unused. + // + private static final byte COPY_LAST_TYPE_MASK = 0x03; + private static final byte COPY_ADDED_BY_USES = 0x04; + private static final byte COPY_ADDED_BY_AUGMENTATION = 0x08; + private static final byte COPY_ORIGINAL = 0x00; + + private final byte copyHistory; + + static { + final int copyTypes = CopyType.values().length; + // This implies CopyType.ordinal() is <= COPY_TYPE_MASK + verify(copyTypes == COPY_LAST_TYPE_MASK + 1, "Unexpected %s CopyType values", copyTypes); + } + // Note: this field can strictly be derived in InferredStatementContext, but it forms the basis of many of our // operations, hence we want to keep it close by. private final @NonNull StatementDefinitionContext definition; @@ -121,12 +137,41 @@ public abstract class StatementContextBase, E StatementContextBase(final StatementDefinitionContext def) { this.definition = requireNonNull(def); - this.copyHistory = CopyHistory.original(); + this.copyHistory = COPY_ORIGINAL; + } + + StatementContextBase(final StatementDefinitionContext def, final byte copyHistory) { + this.definition = requireNonNull(def); + this.copyHistory = copyHistory; } - StatementContextBase(final StatementDefinitionContext def, final CopyHistory copyHistory) { + StatementContextBase(final StatementDefinitionContext def, final CopyType copyType) { this.definition = requireNonNull(def); - this.copyHistory = requireNonNull(copyHistory); + this.copyHistory = (byte) copyFlags(copyType); + } + + StatementContextBase(final StatementContextBase prototype, final CopyType copyType) { + this.definition = prototype.definition; + this.copyHistory = (byte) (copyFlags(copyType) | prototype.copyHistory & ~COPY_LAST_TYPE_MASK); + } + + private static int copyFlags(final CopyType copyType) { + return historyFlags(copyType) | copyType.ordinal(); + } + + private static byte historyFlags(final CopyType copyType) { + switch (copyType) { + case ADDED_BY_AUGMENTATION: + return COPY_ADDED_BY_AUGMENTATION; + case ADDED_BY_USES: + return COPY_ADDED_BY_USES; + case ADDED_BY_USES_AUGMENTATION: + return COPY_ADDED_BY_AUGMENTATION | COPY_ADDED_BY_USES; + case ORIGINAL: + return COPY_ORIGINAL; + default: + throw new VerifyException("Unhandled type " + copyType); + } } @Override @@ -146,11 +191,34 @@ public abstract class StatementContextBase, E effectOfStatement.addAll(ctxs); } + // + // CopyHistory integration + // + @Override public final CopyHistory history() { - return copyHistory; + return this; } + @Override + public final boolean isAddedByUses() { + return (copyHistory & COPY_ADDED_BY_USES) != 0; + } + + @Override + public final boolean isAugmenting() { + return (copyHistory & COPY_ADDED_BY_AUGMENTATION) != 0; + } + + @Override + public final CopyType getLastOperation() { + return CopyType.values()[copyHistory & COPY_LAST_TYPE_MASK]; + } + + // + // Inference completion tracking + // + @Override final byte executionOrder() { return executionOrder; diff --git a/yang/yang-parser-spi/src/main/java/org/opendaylight/yangtools/yang/parser/spi/meta/CopyHistory.java b/yang/yang-parser-spi/src/main/java/org/opendaylight/yangtools/yang/parser/spi/meta/CopyHistory.java index 8b4e5846b5..72b77014a5 100644 --- a/yang/yang-parser-spi/src/main/java/org/opendaylight/yangtools/yang/parser/spi/meta/CopyHistory.java +++ b/yang/yang-parser-spi/src/main/java/org/opendaylight/yangtools/yang/parser/spi/meta/CopyHistory.java @@ -8,137 +8,20 @@ package org.opendaylight.yangtools.yang.parser.spi.meta; import com.google.common.annotations.Beta; -import com.google.common.annotations.VisibleForTesting; -import com.google.common.base.MoreObjects; -import com.google.common.base.Verify; -import java.util.Arrays; -import java.util.stream.Collectors; -import org.opendaylight.yangtools.concepts.Immutable; +import org.eclipse.jdt.annotation.NonNullByDefault; import org.opendaylight.yangtools.yang.model.api.CopyableNode; +/** + * Reactor's view of significant semantic history of a particular statement. + */ @Beta -public final class CopyHistory implements Immutable, CopyableNode { - private static final CopyType[] VALUES = CopyType.values(); - - private static final CopyHistory[][] CACHE = new CopyHistory[VALUES.length][]; - - static { - /* - * Cache size is dependent on number of items in CopyType, it costs N * 2^N objects. - * For 4 types that boils down to 4 * 16 = 64 objects. - * For 5 types that boils down to 5 * 32 = 160 objects. - * For 6 types that boils down to 6 * 64 = 384 objects. - * - * If we ever hit 6 types, the caching strategy needs to be revisited. - */ - Verify.verify(VALUES.length < 6); - } - - private static final CopyHistory ORIGINAL = cacheObject(CopyType.ORIGINAL, CopyType.ORIGINAL.bit()); - private static final int IS_ADDED_BY_USES_BITS = - CopyType.ADDED_BY_USES_AUGMENTATION.bit() | CopyType.ADDED_BY_USES.bit(); - private static final int IS_AUGMENTING_BITS = - CopyType.ADDED_BY_USES_AUGMENTATION.bit() | CopyType.ADDED_BY_AUGMENTATION.bit(); - - private final short operations; - private final short lastOperation; - - private CopyHistory(final int operations, final CopyType lastOperation) { - this.operations = (short) operations; - this.lastOperation = (short) lastOperation.ordinal(); - } - - public static CopyHistory original() { - return ORIGINAL; - } - - public static CopyHistory of(final CopyType copyType, final CopyHistory copyHistory) { - return ORIGINAL.append(copyType, copyHistory); - } - - private static CopyHistory[] cacheArray(final CopyType lastOperation) { - final int ordinal = lastOperation.ordinal(); - CopyHistory[] ret = CACHE[ordinal]; - if (ret == null) { - synchronized (CACHE) { - ret = CACHE[ordinal]; - if (ret == null) { - ret = new CopyHistory[1 << VALUES.length]; - CACHE[ordinal] = ret; - } - } - } - - return ret; - } - - private static CopyHistory cacheObject(final CopyType lastOperation, final int operations) { - final CopyHistory[] array = cacheArray(lastOperation); - CopyHistory ret = array[operations]; - if (ret == null) { - synchronized (array) { - ret = array[operations]; - if (ret == null) { - ret = new CopyHistory(operations, lastOperation); - array[operations] = ret; - } - } - } - - return ret; - } - - public CopyType getLastOperation() { - return VALUES[lastOperation]; - } - - @Override - public boolean isAugmenting() { - return (operations & IS_AUGMENTING_BITS) != 0; - } - - @Override - public boolean isAddedByUses() { - return (operations & IS_ADDED_BY_USES_BITS) != 0; - } - - @VisibleForTesting - boolean contains(final CopyType type) { - return (operations & type.bit()) != 0; - } - - @VisibleForTesting - CopyHistory append(final CopyType typeOfCopy, final CopyHistory toAppend) { - final int newOperations = operations | toAppend.operations | typeOfCopy.bit(); - if (newOperations == operations && typeOfCopy.ordinal() == lastOperation) { - return this; - } - - return cacheObject(typeOfCopy, newOperations); - } - - @Override - public int hashCode() { - return Integer.hashCode(operations | lastOperation << Short.SIZE); - } - - @Override - public boolean equals(final Object obj) { - if (obj == this) { - return true; - } - if (!(obj instanceof CopyHistory)) { - return false; - } - final CopyHistory other = (CopyHistory) obj; - return operations == other.operations && lastOperation == other.lastOperation; - } - - @Override - public String toString() { - return MoreObjects.toStringHelper(this).add("lastOperation", getLastOperation()) - .add("operations", Arrays.stream(VALUES).filter(value -> (value.bit() & operations) != 0) - .collect(Collectors.toList())) - .toString(); - } +@NonNullByDefault +// FIXME: YANGTOOLS-1150: this should live in yang-reactor-api +public interface CopyHistory extends CopyableNode { + /** + * Return the last copy operation in this history. + * + * @return Last {@link CopyType} + */ + CopyType getLastOperation(); } diff --git a/yang/yang-parser-spi/src/test/java/org/opendaylight/yangtools/yang/parser/spi/meta/CopyHistoryTest.java b/yang/yang-parser-spi/src/test/java/org/opendaylight/yangtools/yang/parser/spi/meta/CopyHistoryTest.java deleted file mode 100644 index 6a5c112c2a..0000000000 --- a/yang/yang-parser-spi/src/test/java/org/opendaylight/yangtools/yang/parser/spi/meta/CopyHistoryTest.java +++ /dev/null @@ -1,71 +0,0 @@ -/* - * Copyright (c) 2016 Cisco Systems, Inc. and others. All rights reserved. - * - * This program and the accompanying materials are made available under the - * terms of the Eclipse Public License v1.0 which accompanies this distribution, - * and is available at http://www.eclipse.org/legal/epl-v10.html - */ -package org.opendaylight.yangtools.yang.parser.spi.meta; - -import static org.junit.Assert.assertEquals; -import static org.junit.Assert.assertFalse; -import static org.junit.Assert.assertSame; -import static org.junit.Assert.assertTrue; - -import org.junit.Test; - -public class CopyHistoryTest { - - @Test - public void testSingleton() { - final CopyHistory original = CopyHistory.original(); - - assertEquals(CopyType.ORIGINAL, original.getLastOperation()); - assertTrue(original.contains(CopyType.ORIGINAL)); - assertFalse(original.contains(CopyType.ADDED_BY_USES)); - assertFalse(original.contains(CopyType.ADDED_BY_AUGMENTATION)); - assertFalse(original.contains(CopyType.ADDED_BY_USES_AUGMENTATION)); - - assertSame(original, CopyHistory.original()); - } - - @Test - public void testAppend() { - final CopyHistory original = CopyHistory.original(); - assertSame(original, original.append(CopyType.ORIGINAL, original)); - - final CopyHistory originalUA = original.append(CopyType.ADDED_BY_USES_AUGMENTATION, original); - assertEquals(CopyType.ADDED_BY_USES_AUGMENTATION, originalUA.getLastOperation()); - assertTrue(originalUA.contains(CopyType.ORIGINAL)); - assertFalse(originalUA.contains(CopyType.ADDED_BY_USES)); - assertFalse(originalUA.contains(CopyType.ADDED_BY_AUGMENTATION)); - assertTrue(originalUA.contains(CopyType.ADDED_BY_USES_AUGMENTATION)); - - assertSame(originalUA, original.append(CopyType.ADDED_BY_USES_AUGMENTATION, original)); - assertSame(originalUA, originalUA.append(CopyType.ADDED_BY_USES_AUGMENTATION, original)); - - final CopyHistory originalU = original.append(CopyType.ADDED_BY_USES, original); - assertEquals(CopyType.ADDED_BY_USES, originalU.getLastOperation()); - assertTrue(originalU.contains(CopyType.ORIGINAL)); - assertTrue(originalU.contains(CopyType.ADDED_BY_USES)); - assertFalse(originalU.contains(CopyType.ADDED_BY_AUGMENTATION)); - assertFalse(originalU.contains(CopyType.ADDED_BY_USES_AUGMENTATION)); - - final CopyHistory uaU = originalUA.append(CopyType.ADDED_BY_USES, original); - assertEquals(CopyType.ADDED_BY_USES, uaU.getLastOperation()); - assertTrue(uaU.contains(CopyType.ORIGINAL)); - assertTrue(uaU.contains(CopyType.ADDED_BY_USES)); - assertFalse(uaU.contains(CopyType.ADDED_BY_AUGMENTATION)); - assertTrue(uaU.contains(CopyType.ADDED_BY_USES_AUGMENTATION)); - - assertSame(uaU, originalUA.append(CopyType.ADDED_BY_USES, original)); - - final CopyHistory res = originalUA.append(CopyType.ADDED_BY_AUGMENTATION, originalU); - assertEquals(CopyType.ADDED_BY_AUGMENTATION, res.getLastOperation()); - assertTrue(res.contains(CopyType.ORIGINAL)); - assertTrue(res.contains(CopyType.ADDED_BY_USES)); - assertTrue(res.contains(CopyType.ADDED_BY_AUGMENTATION)); - assertTrue(res.contains(CopyType.ADDED_BY_USES_AUGMENTATION)); - } - -} -- 2.36.6