cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From alek...@apache.org
Subject [1/2] cassandra git commit: Eliminate the dependency on jgrapht for UDT resolution
Date Fri, 18 Dec 2015 15:44:01 GMT
Repository: cassandra
Updated Branches:
  refs/heads/trunk 50f7e0204 -> a0f59dce5


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/trunk
Commit: d877ba073f60b8aba9ab70a5e163cc13b232ffdd
Parents: 2da3c9d
Author: Aleksey Yeschenko <aleksey@apache.org>
Authored: Mon Nov 16 22:22:51 2015 +0000
Committer: Aleksey Yeschenko <aleksey@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);
+            }
         }
     }
 }


Mime
View raw message