Repository: cassandra Updated Branches: refs/heads/cassandra-3.0 2da3c9db1 -> d877ba073
Eliminate the dependency on jgrapht for UDT resolution patch by Aleksey Yeschenko; reviewed by Sylvain Lebresne for CASSANDRA-10653 Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/d877ba07 Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/d877ba07 Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/d877ba07 Branch: refs/heads/cassandra-3.0 Commit: d877ba073f60b8aba9ab70a5e163cc13b232ffdd Parents: 2da3c9d Author: Aleksey Yeschenko <alek...@apache.org> Authored: Mon Nov 16 22:22:51 2015 +0000 Committer: Aleksey Yeschenko <alek...@apache.org> Committed: Fri Dec 18 15:39:33 2015 +0000 ---------------------------------------------------------------------- CHANGES.txt | 1 + NOTICE.txt | 4 - build.xml | 2 - lib/jgrapht-core-0.9.1.jar | Bin 351208 -> 0 bytes lib/licenses/jgrapht-core-0.9.1.txt | 227 ------------------- src/java/org/apache/cassandra/schema/Types.java | 64 ++++-- 6 files changed, 47 insertions(+), 251 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/cassandra/blob/d877ba07/CHANGES.txt ---------------------------------------------------------------------- diff --git a/CHANGES.txt b/CHANGES.txt index a2951a8..e6ab5dd 100644 --- a/CHANGES.txt +++ b/CHANGES.txt @@ -1,4 +1,5 @@ 3.0.3 + * Eliminate the dependency on jgrapht for UDT resolution (CASSANDRA-10653) * (Hadoop) Close Clusters and Sessions in Hadoop Input/Output classes (CASSANDRA-1837) * Fix sstableloader not working with upper case keyspace name (CASSANDRA-10806) Merged from 2.2: http://git-wip-us.apache.org/repos/asf/cassandra/blob/d877ba07/NOTICE.txt ---------------------------------------------------------------------- diff --git a/NOTICE.txt b/NOTICE.txt index b880183..a20994f 100644 --- a/NOTICE.txt +++ b/NOTICE.txt @@ -83,7 +83,3 @@ BSD 3-clause ASM (http://asm.ow2.org/) Copyright (c) 2000-2011 INRIA, France Telecom - -JGraphT -(http://jgrapht.org) -Copyright 2003-2015, by Barak Naveh and Contributors. http://git-wip-us.apache.org/repos/asf/cassandra/blob/d877ba07/build.xml ---------------------------------------------------------------------- diff --git a/build.xml b/build.xml index 0420652..cab361f 100644 --- a/build.xml +++ b/build.xml @@ -392,7 +392,6 @@ <dependency groupId="org.mindrot" artifactId="jbcrypt" version="0.3m" /> <dependency groupId="io.airlift" artifactId="airline" version="0.6" /> <dependency groupId="io.netty" artifactId="netty-all" version="4.0.23.Final" /> - <dependency groupId="org.jgrapht" artifactId="jgrapht-core" version="0.9.1" /> <dependency groupId="com.google.code.findbugs" artifactId="jsr305" version="2.0.2" /> <dependency groupId="com.clearspring.analytics" artifactId="stream" version="2.5.2" /> <!-- TODO CASSANDRA-9543 @@ -552,7 +551,6 @@ <dependency groupId="com.github.jbellis" artifactId="jamm"/> <dependency groupId="io.netty" artifactId="netty-all"/> - <dependency groupId="org.jgrapht" artifactId="jgrapht-core"/> <dependency groupId="joda-time" artifactId="joda-time"/> <dependency groupId="org.fusesource" artifactId="sigar"/> <dependency groupId="org.eclipse.jdt.core.compiler" artifactId="ecj" /> http://git-wip-us.apache.org/repos/asf/cassandra/blob/d877ba07/lib/jgrapht-core-0.9.1.jar ---------------------------------------------------------------------- diff --git a/lib/jgrapht-core-0.9.1.jar b/lib/jgrapht-core-0.9.1.jar deleted file mode 100644 index f491e25..0000000 Binary files a/lib/jgrapht-core-0.9.1.jar and /dev/null differ http://git-wip-us.apache.org/repos/asf/cassandra/blob/d877ba07/lib/licenses/jgrapht-core-0.9.1.txt ---------------------------------------------------------------------- diff --git a/lib/licenses/jgrapht-core-0.9.1.txt b/lib/licenses/jgrapht-core-0.9.1.txt deleted file mode 100644 index 5d80026..0000000 --- a/lib/licenses/jgrapht-core-0.9.1.txt +++ /dev/null @@ -1,227 +0,0 @@ -Eclipse Public License - v 1.0 - - THE ACCOMPANYING PROGRAM IS PROVIDED UNDER THE TERMS OF THIS ECLIPSE - PUBLIC LICENSE ("AGREEMENT"). ANY USE, REPRODUCTION OR DISTRIBUTION OF - THE PROGRAM CONSTITUTES RECIPIENT'S ACCEPTANCE OF THIS AGREEMENT. - - 1. DEFINITIONS - - "Contribution" means: - - a) in the case of the initial Contributor, the initial code and - documentation distributed under this Agreement, and - - b) in the case of each subsequent Contributor: - - i) changes to the Program, and - - ii) additions to the Program; - - where such changes and/or additions to the Program originate from and - are distributed by that particular Contributor. A Contribution - 'originates' from a Contributor if it was added to the Program by such - Contributor itself or anyone acting on such Contributor's behalf. - Contributions do not include additions to the Program which: (i) are - separate modules of software distributed in conjunction with the - Program under their own license agreement, and (ii) are not derivative - works of the Program. - - "Contributor" means any person or entity that distributes the Program. - - "Licensed Patents" mean patent claims licensable by a Contributor which - are necessarily infringed by the use or sale of its Contribution alone - or when combined with the Program. - - "Program" means the Contributions distributed in accordance with this - Agreement. - - "Recipient" means anyone who receives the Program under this Agreement, - including all Contributors. - - 2. GRANT OF RIGHTS - - a) Subject to the terms of this Agreement, each Contributor hereby - grants Recipient a non-exclusive, worldwide, royalty-free copyright - license to reproduce, prepare derivative works of, publicly display, - publicly perform, distribute and sublicense the Contribution of such - Contributor, if any, and such derivative works, in source code and - object code form. - - b) Subject to the terms of this Agreement, each Contributor hereby - grants Recipient a non-exclusive, worldwide, royalty-free patent - license under Licensed Patents to make, use, sell, offer to sell, - import and otherwise transfer the Contribution of such Contributor, if - any, in source code and object code form. This patent license shall - apply to the combination of the Contribution and the Program if, at the - time the Contribution is added by the Contributor, such addition of the - Contribution causes such combination to be covered by the Licensed - Patents. The patent license shall not apply to any other combinations - which include the Contribution. No hardware per se is licensed - hereunder. - - c) Recipient understands that although each Contributor grants the - licenses to its Contributions set forth herein, no assurances are - provided by any Contributor that the Program does not infringe the - patent or other intellectual property rights of any other entity. Each - Contributor disclaims any liability to Recipient for claims brought by - any other entity based on infringement of intellectual property rights - or otherwise. As a condition to exercising the rights and licenses - granted hereunder, each Recipient hereby assumes sole responsibility to - secure any other intellectual property rights needed, if any. For - example, if a third party patent license is required to allow Recipient - to distribute the Program, it is Recipient's responsibility to acquire - that license before distributing the Program. - - d) Each Contributor represents that to its knowledge it has sufficient - copyright rights in its Contribution, if any, to grant the copyright - license set forth in this Agreement. - - 3. REQUIREMENTS - - A Contributor may choose to distribute the Program in object code form - under its own license agreement, provided that: - - a) it complies with the terms and conditions of this Agreement; and - - b) its license agreement: - - i) effectively disclaims on behalf of all Contributors all warranties - and conditions, express and implied, including warranties or conditions - of title and non-infringement, and implied warranties or conditions of - merchantability and fitness for a particular purpose; - - ii) effectively excludes on behalf of all Contributors all liability - for damages, including direct, indirect, special, incidental and - consequential damages, such as lost profits; - - iii) states that any provisions which differ from this Agreement are - offered by that Contributor alone and not by any other party; and - - iv) states that source code for the Program is available from such - Contributor, and informs licensees how to obtain it in a reasonable - manner on or through a medium customarily used for software exchange. - - When the Program is made available in source code form: - - a) it must be made available under this Agreement; and - - b) a copy of this Agreement must be included with each copy of the - Program. - - Contributors may not remove or alter any copyright notices contained - within the Program. - - Each Contributor must identify itself as the originator of its - Contribution, if any, in a manner that reasonably allows subsequent - Recipients to identify the originator of the Contribution. - - 4. COMMERCIAL DISTRIBUTION - - Commercial distributors of software may accept certain responsibilities - with respect to end users, business partners and the like. While this - license is intended to facilitate the commercial use of the Program, - the Contributor who includes the Program in a commercial product - offering should do so in a manner which does not create potential - liability for other Contributors. Therefore, if a Contributor includes - the Program in a commercial product offering, such Contributor - ("Commercial Contributor") hereby agrees to defend and indemnify every - other Contributor ("Indemnified Contributor") against any losses, - damages and costs (collectively "Losses") arising from claims, lawsuits - and other legal actions brought by a third party against the - Indemnified Contributor to the extent caused by the acts or omissions - of such Commercial Contributor in connection with its distribution of - the Program in a commercial product offering. The obligations in this - section do not apply to any claims or Losses relating to any actual or - alleged intellectual property infringement. In order to qualify, an - Indemnified Contributor must: a) promptly notify the Commercial - Contributor in writing of such claim, and b) allow the Commercial - Contributor to control, and cooperate with the Commercial Contributor - in, the defense and any related settlement negotiations. The - Indemnified Contributor may participate in any such claim at its own - expense. - - For example, a Contributor might include the Program in a commercial - product offering, Product X. That Contributor is then a Commercial - Contributor. If that Commercial Contributor then makes performance - claims, or offers warranties related to Product X, those performance - claims and warranties are such Commercial Contributor's responsibility - alone. Under this section, the Commercial Contributor would have to - defend claims against the other Contributors related to those - performance claims and warranties, and if a court requires any other - Contributor to pay any damages as a result, the Commercial Contributor - must pay those damages. - - 5. NO WARRANTY - - EXCEPT AS EXPRESSLY SET FORTH IN THIS AGREEMENT, THE PROGRAM IS - PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - KIND, EITHER EXPRESS OR IMPLIED INCLUDING, WITHOUT LIMITATION, ANY - WARRANTIES OR CONDITIONS OF TITLE, NON-INFRINGEMENT, MERCHANTABILITY OR - FITNESS FOR A PARTICULAR PURPOSE. Each Recipient is solely responsible - for determining the appropriateness of using and distributing the - Program and assumes all risks associated with its exercise of rights - under this Agreement , including but not limited to the risks and costs - of program errors, compliance with applicable laws, damage to or loss - of data, programs or equipment, and unavailability or interruption of - operations. - - 6. DISCLAIMER OF LIABILITY - - EXCEPT AS EXPRESSLY SET FORTH IN THIS AGREEMENT, NEITHER RECIPIENT NOR - ANY CONTRIBUTORS SHALL HAVE ANY LIABILITY FOR ANY DIRECT, INDIRECT, - INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING - WITHOUT LIMITATION LOST PROFITS), HOWEVER CAUSED AND ON ANY THEORY OF - LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING - NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OR - DISTRIBUTION OF THE PROGRAM OR THE EXERCISE OF ANY RIGHTS GRANTED - HEREUNDER, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. - - 7. GENERAL - - If any provision of this Agreement is invalid or unenforceable under - applicable law, it shall not affect the validity or enforceability of - the remainder of the terms of this Agreement, and without further - action by the parties hereto, such provision shall be reformed to the - minimum extent necessary to make such provision valid and enforceable. - - If Recipient institutes patent litigation against any entity (including - a cross-claim or counterclaim in a lawsuit) alleging that the Program - itself (excluding combinations of the Program with other software or - hardware) infringes such Recipient's patent(s), then such Recipient's - rights granted under Section 2(b) shall terminate as of the date such - litigation is filed. - - All Recipient's rights under this Agreement shall terminate if it fails - to comply with any of the material terms or conditions of this - Agreement and does not cure such failure in a reasonable period of time - after becoming aware of such noncompliance. If all Recipient's rights - under this Agreement terminate, Recipient agrees to cease use and - distribution of the Program as soon as reasonably practicable. However, - Recipient's obligations under this Agreement and any licenses granted - by Recipient relating to the Program shall continue and survive. - - Everyone is permitted to copy and distribute copies of this Agreement, - but in order to avoid inconsistency the Agreement is copyrighted and - may only be modified in the following manner. The Agreement Steward - reserves the right to publish new versions (including revisions) of - this Agreement from time to time. No one other than the Agreement - Steward has the right to modify this Agreement. The Eclipse Foundation - is the initial Agreement Steward. The Eclipse Foundation may assign the - responsibility to serve as the Agreement Steward to a suitable separate - entity. Each new version of the Agreement will be given a - distinguishing version number. The Program (including Contributions) - may always be distributed subject to the version of the Agreement under - which it was received. In addition, after a new version of the - Agreement is published, Contributor may elect to distribute the Program - (including its Contributions) under the new version. Except as - expressly stated in Sections 2(a) and 2(b) above, Recipient receives no - rights or licenses to the intellectual property of any Contributor - under this Agreement, whether expressly, by implication, estoppel or - otherwise. All rights in the Program not expressly granted under this - Agreement are reserved. - - This Agreement is governed by the laws of the State of New York and the - intellectual property laws of the United States of America. No party to - this Agreement will bring a legal action under this Agreement more than - one year after the cause of action arose. Each party waives its rights - to a jury trial in any resulting litigation. http://git-wip-us.apache.org/repos/asf/cassandra/blob/d877ba07/src/java/org/apache/cassandra/schema/Types.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/schema/Types.java b/src/java/org/apache/cassandra/schema/Types.java index 258be9f..1b71364 100644 --- a/src/java/org/apache/cassandra/schema/Types.java +++ b/src/java/org/apache/cassandra/schema/Types.java @@ -22,18 +22,19 @@ import java.util.*; import javax.annotation.Nullable; +import com.google.common.collect.HashMultimap; import com.google.common.collect.ImmutableMap; import com.google.common.collect.MapDifference; import com.google.common.collect.Maps; +import com.google.common.collect.Multimap; import org.apache.cassandra.cql3.CQL3Type; import org.apache.cassandra.db.marshal.AbstractType; import org.apache.cassandra.db.marshal.UserType; +import org.apache.cassandra.exceptions.ConfigurationException; import org.apache.cassandra.utils.ByteBufferUtil; -import org.jgrapht.graph.DefaultDirectedGraph; -import org.jgrapht.graph.DefaultEdge; -import org.jgrapht.traverse.TopologicalOrderIterator; +import static java.lang.String.format; import static com.google.common.collect.Iterables.filter; import static java.util.stream.Collectors.toList; import static org.apache.cassandra.utils.ByteBufferUtil.bytes; @@ -114,7 +115,7 @@ public final class Types implements Iterable<UserType> public Types with(UserType type) { if (get(type.name).isPresent()) - throw new IllegalStateException(String.format("Type %s already exists", type.name)); + throw new IllegalStateException(format("Type %s already exists", type.name)); return builder().add(this).add(type).build(); } @@ -125,7 +126,7 @@ public final class Types implements Iterable<UserType> public Types without(ByteBuffer name) { UserType type = - get(name).orElseThrow(() -> new IllegalStateException(String.format("Type %s doesn't exists", name))); + get(name).orElseThrow(() -> new IllegalStateException(format("Type %s doesn't exists", name))); return builder().add(filter(this, t -> t != type)).build(); } @@ -210,27 +211,42 @@ public final class Types implements Iterable<UserType> /* * build a DAG of UDT dependencies */ - DefaultDirectedGraph<RawUDT, DefaultEdge> graph = new DefaultDirectedGraph<>(DefaultEdge.class); + Map<RawUDT, Integer> vertices = new HashMap<>(); // map values are numbers of referenced types + for (RawUDT udt : definitions) + vertices.put(udt, 0); - definitions.forEach(graph::addVertex); - - for (RawUDT udt1: definitions) + Multimap<RawUDT, RawUDT> adjacencyList = HashMultimap.create(); + for (RawUDT udt1 : definitions) for (RawUDT udt2 : definitions) - if (udt1 != udt2 && udt1.referencesUserType(udt2.name)) - graph.addEdge(udt2, udt1); + if (udt1 != udt2 && udt1.referencesUserType(udt2)) + adjacencyList.put(udt2, udt1); /* - * iterate in topological order, + * resolve dependencies in topological order, using Kahn's algorithm */ - Types types = new Types(new HashMap<>()); + adjacencyList.values().forEach(vertex -> vertices.put(vertex, vertices.get(vertex) + 1)); - TopologicalOrderIterator<RawUDT, DefaultEdge> iterator = new TopologicalOrderIterator<>(graph); - while (iterator.hasNext()) + Queue<RawUDT> resolvableTypes = new LinkedList<>(); // UDTs with 0 dependencies + for (Map.Entry<RawUDT, Integer> entry : vertices.entrySet()) + if (entry.getValue() == 0) + resolvableTypes.add(entry.getKey()); + + Types types = new Types(new HashMap<>()); + while (!resolvableTypes.isEmpty()) { - UserType udt = iterator.next().prepare(keyspace, types); // will throw InvalidRequestException if meets an unknown type + RawUDT vertex = resolvableTypes.remove(); + + for (RawUDT dependentType : adjacencyList.get(vertex)) + if (vertices.replace(dependentType, vertices.get(dependentType) - 1) == 1) + resolvableTypes.add(dependentType); + + UserType udt = vertex.prepare(keyspace, types); types.types.put(udt.name, udt); } + if (types.types.size() != definitions.size()) + throw new ConfigurationException(format("Cannot resolve UDTs for keyspace %s: some types are missing", keyspace)); + /* * return an immutable copy */ @@ -260,9 +276,9 @@ public final class Types implements Iterable<UserType> this.fieldTypes = fieldTypes; } - boolean referencesUserType(String typeName) + boolean referencesUserType(RawUDT other) { - return fieldTypes.stream().anyMatch(t -> t.referencesUserType(typeName)); + return fieldTypes.stream().anyMatch(t -> t.referencesUserType(other.name)); } UserType prepare(String keyspace, Types types) @@ -279,6 +295,18 @@ public final class Types implements Iterable<UserType> return new UserType(keyspace, bytes(name), preparedFieldNames, preparedFieldTypes); } + + @Override + public int hashCode() + { + return name.hashCode(); + } + + @Override + public boolean equals(Object other) + { + return name.equals(((RawUDT) other).name); + } } } }
