You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@maven.apache.org by og...@apache.org on 2009/04/23 00:57:04 UTC
svn commit: r767705 [6/31] - in /maven/mercury/trunk/mercury-core: ./ src/
src/main/ src/main/java/ src/main/java/org/ src/main/java/org/apache/
src/main/java/org/apache/maven/ src/main/java/org/apache/maven/mercury/
src/main/java/org/apache/maven/merc...
Added: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/DependencyTreeDumper.java
URL: http://svn.apache.org/viewvc/maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/DependencyTreeDumper.java?rev=767705&view=auto
==============================================================================
--- maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/DependencyTreeDumper.java (added)
+++ maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/DependencyTreeDumper.java Wed Apr 22 22:56:48 2009
@@ -0,0 +1,286 @@
+/*
+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.maven.mercury.metadata;
+
+import java.io.BufferedOutputStream;
+import java.io.BufferedWriter;
+import java.io.File;
+import java.io.FileInputStream;
+import java.io.FileOutputStream;
+import java.io.FileWriter;
+import java.io.IOException;
+import java.io.Writer;
+import java.util.List;
+import java.util.TreeSet;
+
+import org.apache.maven.mercury.artifact.ArtifactExclusionList;
+import org.apache.maven.mercury.artifact.ArtifactInclusionList;
+import org.apache.maven.mercury.artifact.ArtifactMetadata;
+import org.apache.maven.mercury.artifact.ArtifactQueryList;
+import org.apache.maven.mercury.artifact.ArtifactScopeEnum;
+import org.apache.maven.mercury.artifact.MetadataTreeNode;
+import org.apache.maven.mercury.metadata.forest.Forest;
+import org.apache.maven.mercury.metadata.forest.Node;
+import org.apache.maven.mercury.metadata.forest.Tree;
+import org.apache.maven.mercury.metadata.forest.io.xpp3.ForrestXpp3Reader;
+import org.apache.maven.mercury.metadata.forest.io.xpp3.ForrestXpp3Writer;
+import org.apache.maven.mercury.util.TimeUtil;
+
+/**
+ *
+ *
+ * @author Oleg Gusakov
+ * @version $Id$
+ *
+ */
+public class DependencyTreeDumper
+{
+ String _dumpFileName;
+ File _dumpFile;
+ Writer _wr;
+
+ public DependencyTreeDumper( String name )
+ {
+ _dumpFileName = name;
+ }
+
+ /**
+ * this one does not work because the writer runs out of stack memory on
+ * huge trees
+ *
+ * @param scope
+ * @param artifacts
+ * @param inclusions
+ * @param exclusions
+ * @param dirty
+ * @param result
+ * @throws MetadataTreeException
+ */
+ public synchronized void realDump( ArtifactScopeEnum scope
+ , ArtifactQueryList artifacts
+ , ArtifactInclusionList inclusions
+ , ArtifactExclusionList exclusions
+ , MetadataTreeNode dirty
+ , List<ArtifactMetadata> result
+ )
+ throws MetadataTreeException
+ {
+ try
+ {
+ if( artifacts == null || artifacts.getMetadataList() == null )
+ return;
+
+ Forest forest;
+ if( _dumpFile.exists() )
+ {
+ forest = new ForrestXpp3Reader().read( new FileInputStream(_dumpFile) );
+ }
+ else
+ forest = new Forest();
+
+ Tree tree = new Tree();
+
+ forest.addTree( tree );
+
+ tree.setScope( scope == null ? "null" : scope.toString() );
+
+ tree.setTimestamp( TimeUtil.getUTCTimestamp() );
+
+ for( ArtifactMetadata md : artifacts.getMetadataList() )
+ {
+ Node n = new Node();
+ n.setName( md.toString() );
+ n.setScope( md.getScope() );
+ tree.addRequest( n );
+ }
+
+ if( inclusions != null )
+ for( ArtifactMetadata md : inclusions.getMetadataList() )
+ {
+ Node n = new Node();
+ n.setName( md.toString() );
+ n.setScope( md.getScope() );
+ tree.addInclusion( n );
+
+ }
+
+ if( exclusions != null )
+ for( ArtifactMetadata md : exclusions.getMetadataList() )
+ {
+ Node n = new Node();
+ n.setName( md.toString() );
+ n.setScope( md.getScope() );
+ tree.addExclusion( n );
+
+ }
+
+ Node root = createNode( dirty, 0L );
+
+ tree.addDirtyTree( root );
+
+ if( result != null )
+ for( ArtifactMetadata md : result )
+ {
+ Node n = new Node();
+ n.setName( md.toString() );
+ n.setScope( md.getScope() );
+ tree.addResult( n );
+ }
+
+ new ForrestXpp3Writer().write( new FileWriter(_dumpFile), forest );
+ }
+ catch (Exception e)
+ {
+ throw new MetadataTreeException(e);
+ }
+ }
+
+ public synchronized void dump( ArtifactScopeEnum scope
+ , ArtifactQueryList artifacts
+ , ArtifactInclusionList inclusions
+ , ArtifactExclusionList exclusions
+ , MetadataTreeNode dirty
+ , List<ArtifactMetadata> result
+ )
+ throws MetadataTreeException
+ {
+ try
+ {
+ _dumpFile = new File(_dumpFileName+"-"+TimeUtil.getUTCTimestamp()+"-"+System.currentTimeMillis()+".xml" );
+ _wr = new FileWriter(_dumpFile);
+ _wr.write( "<tree>\n" );
+ }
+ catch ( IOException e )
+ {
+ throw new MetadataTreeException(e);
+ }
+ try
+ {
+ if( artifacts != null && artifacts.getMetadataList() != null )
+ {
+ if( scope != null )
+ _wr.write( "<scope>"+scope+"</scope>\n" );
+
+ _wr.write( "<timestamp>"+ TimeUtil.getUTCTimestamp() +"</timestamp>\n" );
+
+ _wr.write( "<request>\n" );
+ for( ArtifactMetadata md : artifacts.getMetadataList() )
+ {
+ _wr.write( " <node scope='"+md.getScope()+"'>"+md.toString()+"</node>\n" );
+ }
+ _wr.write( "</request>\n" );
+
+ if( inclusions != null )
+ {
+ _wr.write( "<inclusions>\n" );
+ for( ArtifactMetadata md : inclusions.getMetadataList() )
+ {
+ _wr.write( " <inclusion>"+md.toString()+"</inclusion>\n" );
+ }
+ _wr.write( "</inclusions>\n" );
+ }
+
+ if( exclusions != null )
+ {
+ _wr.write( "<exclusions>\n" );
+ for( ArtifactMetadata md : exclusions.getMetadataList() )
+ {
+ _wr.write( " <exclusion>"+md.toString()+"</exclusion>\n" );
+ }
+ _wr.write( "</exclusions>\n" );
+ }
+
+ _wr.write( "<source>\n" );
+ showNode( dirty, 0L );
+ _wr.write( "</source>\n" );
+
+ if( result != null )
+ {
+ TreeSet<String> ts = new TreeSet<String>();
+ for( ArtifactMetadata md : result )
+ ts.add( md.toString() );
+
+ _wr.write( "<result>\n" );
+ for( String name : ts )
+ {
+ _wr.write( " <node>"+name+"</node>\n" );
+ }
+ _wr.write( "</result>\n" );
+ }
+
+ }
+ }
+ catch (Exception e)
+ {
+ throw new MetadataTreeException(e);
+ }
+ finally
+ {
+ if( _wr != null )
+ try { _wr.write( "</tree>\n" );_wr.flush(); _wr.close(); } catch( Exception ee ) {}
+
+ _wr = null;
+ }
+ }
+
+ private void showNode( MetadataTreeNode mtn, long level )
+ throws IOException
+ {
+ if( mtn == null )
+ return;
+
+ ArtifactMetadata md = mtn.getMd();
+ for( int i=0; i<level; i++ )
+ _wr.write( " " );
+
+ _wr.write( " <node level='"+level+"'>"+md.toString()+"</node>\n" );
+
+ if( mtn.hasChildren() )
+ {
+ _wr.write( " <kids>\n" );
+ for( MetadataTreeNode kid : mtn.getChildren() )
+ showNode( kid, level+1 );
+ _wr.write( " </kids>\n" );
+ }
+ }
+
+ private static Node createNode( MetadataTreeNode mtn, long level )
+ {
+ if( mtn == null )
+ return null;
+
+ Node n = new Node();
+
+ ArtifactMetadata md = mtn.getMd();
+
+ n.setName( md.toString() );
+
+ n.setLevel( level );
+
+ if( mtn.hasChildren() )
+ {
+ for( MetadataTreeNode kid : mtn.getChildren() )
+ n.addChildren( createNode( kid, level+1 ) );
+ }
+
+ return n;
+
+ }
+}
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/DependencyTreeDumper.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/DependencyTreeDumper.java
------------------------------------------------------------------------------
svn:keywords = Author Date Id Revision
Added: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/Messages.properties
URL: http://svn.apache.org/viewvc/maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/Messages.properties?rev=767705&view=auto
==============================================================================
--- maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/Messages.properties (added)
+++ maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/Messages.properties Wed Apr 22 22:56:48 2009
@@ -0,0 +1,29 @@
+#
+# 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.
+#
+artifact.md.not.found=cannot find artifact metadata for query {0}
+dependency.model.not.implemented=the requested dependency model {0} is not yet implemented
+empty.tree=Dependency tree is not populated yet
+empty.tree.collection=Empty tree collection supplied
+empty.md.collection=Empty metadata collection supplied
+
+no.versions=cannot find any versions for {0} - exit
+
+not.optional.missing="did not find non-optional artifact for "
+
+attention.line=\n\n*************************************************************************************\n\n
\ No newline at end of file
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/Messages.properties
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/Messages.properties
------------------------------------------------------------------------------
svn:keywords = Author Date Id Revision
Added: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataRetrievalException.java
URL: http://svn.apache.org/viewvc/maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataRetrievalException.java?rev=767705&view=auto
==============================================================================
--- maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataRetrievalException.java (added)
+++ maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataRetrievalException.java Wed Apr 22 22:56:48 2009
@@ -0,0 +1,65 @@
+package org.apache.maven.mercury.metadata;
+
+import org.apache.maven.mercury.artifact.ArtifactMetadata;
+
+/*
+ * 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.
+ */
+
+/**
+ * Error while retrieving repository metadata from the repository.
+ *
+ * @author Jason van Zyl
+ * @version $Id$
+ */
+public class MetadataRetrievalException
+ extends Exception
+{
+
+ private ArtifactMetadata artifact;
+
+ public MetadataRetrievalException( String message )
+ {
+ this( message, null, null );
+ }
+
+ public MetadataRetrievalException( Throwable cause )
+ {
+ this( null, cause, null );
+ }
+
+ public MetadataRetrievalException( String message,
+ Throwable cause )
+ {
+ this( message, cause, null );
+ }
+
+ public MetadataRetrievalException( String message,
+ Throwable cause,
+ ArtifactMetadata artifact )
+ {
+ super( message, cause );
+
+ this.artifact = artifact;
+ }
+
+ public ArtifactMetadata getArtifactMetadata()
+ {
+ return artifact;
+ }
+}
\ No newline at end of file
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataRetrievalException.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataRetrievalException.java
------------------------------------------------------------------------------
svn:keywords = Author Date Id Revision
Added: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeArtifactFilter.java
URL: http://svn.apache.org/viewvc/maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeArtifactFilter.java?rev=767705&view=auto
==============================================================================
--- maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeArtifactFilter.java (added)
+++ maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeArtifactFilter.java Wed Apr 22 22:56:48 2009
@@ -0,0 +1,32 @@
+/**
+ * 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.maven.mercury.metadata;
+
+import org.apache.maven.mercury.artifact.ArtifactMetadata;
+
+/**
+ * This is a member of a chain of filters that can stop an ArtifactMetadata
+ * from reaching the resolution tree
+ *
+ * @author Oleg Gusakov
+ */
+public interface MetadataTreeArtifactFilter
+{
+ public boolean veto( ArtifactMetadata md );
+}
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeArtifactFilter.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeArtifactFilter.java
------------------------------------------------------------------------------
svn:keywords = Author Date Id Revision
Added: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeArtifactFilterMap.java
URL: http://svn.apache.org/viewvc/maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeArtifactFilterMap.java?rev=767705&view=auto
==============================================================================
--- maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeArtifactFilterMap.java (added)
+++ maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeArtifactFilterMap.java Wed Apr 22 22:56:48 2009
@@ -0,0 +1,57 @@
+/*
+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.maven.mercury.metadata;
+
+import java.util.Collection;
+import java.util.Map;
+
+import org.apache.maven.mercury.artifact.ArtifactMetadata;
+import org.apache.maven.mercury.util.Util;
+
+/**
+ *
+ *
+ * @author Oleg Gusakov
+ * @version $Id$
+ *
+ */
+public class MetadataTreeArtifactFilterMap
+ implements MetadataTreeArtifactFilter
+{
+ Map<String, Collection<String>> _vetos;
+
+ public MetadataTreeArtifactFilterMap(Map<String, Collection<String>> vetos)
+ {
+ _vetos = vetos;
+ }
+
+ public boolean veto( ArtifactMetadata md )
+ {
+ String key = md.toManagementString();
+
+ Collection<String> ver = _vetos.get( key );
+
+ if( Util.isEmpty( ver ) )
+ return false;
+
+ return ver.contains( md.getVersion() );
+ }
+
+}
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeArtifactFilterMap.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeArtifactFilterMap.java
------------------------------------------------------------------------------
svn:keywords = Author Date Id Revision
Added: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeCircularDependencyException.java
URL: http://svn.apache.org/viewvc/maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeCircularDependencyException.java?rev=767705&view=auto
==============================================================================
--- maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeCircularDependencyException.java (added)
+++ maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeCircularDependencyException.java Wed Apr 22 22:56:48 2009
@@ -0,0 +1,49 @@
+/**
+ * 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.maven.mercury.metadata;
+
+/**
+ *
+ * @author Oleg Gusakov
+ * @version $Id$
+ */
+public class MetadataTreeCircularDependencyException
+extends MetadataTreeException
+{
+
+ public MetadataTreeCircularDependencyException()
+ {
+ }
+
+ public MetadataTreeCircularDependencyException(String message)
+ {
+ super(message);
+ }
+
+ public MetadataTreeCircularDependencyException(Throwable cause)
+ {
+ super(cause);
+ }
+
+ public MetadataTreeCircularDependencyException(String message, Throwable cause)
+ {
+ super(message, cause);
+ }
+
+}
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeCircularDependencyException.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeCircularDependencyException.java
------------------------------------------------------------------------------
svn:keywords = Author Date Id Revision
Added: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeException.java
URL: http://svn.apache.org/viewvc/maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeException.java?rev=767705&view=auto
==============================================================================
--- maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeException.java (added)
+++ maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeException.java Wed Apr 22 22:56:48 2009
@@ -0,0 +1,49 @@
+/**
+ * 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.maven.mercury.metadata;
+
+/**
+ *
+ * @author Oleg Gusakov
+ * @version $Id$
+ */
+public class MetadataTreeException
+ extends Exception
+{
+
+ public MetadataTreeException()
+ {
+ }
+
+ public MetadataTreeException(String message)
+ {
+ super(message);
+ }
+
+ public MetadataTreeException(Throwable cause)
+ {
+ super(cause);
+ }
+
+ public MetadataTreeException(String message, Throwable cause)
+ {
+ super(message, cause);
+ }
+
+}
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeException.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeException.java
------------------------------------------------------------------------------
svn:keywords = Author Date Id Revision
Added: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeNodeGAComparator.java
URL: http://svn.apache.org/viewvc/maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeNodeGAComparator.java?rev=767705&view=auto
==============================================================================
--- maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeNodeGAComparator.java (added)
+++ maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeNodeGAComparator.java Wed Apr 22 22:56:48 2009
@@ -0,0 +1,40 @@
+/**
+ * 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.maven.mercury.metadata;
+
+import java.util.Comparator;
+
+import org.apache.maven.mercury.artifact.MetadataTreeNode;
+
+/**
+ * utility class for DefaultSatSolver. Assumes good data - no null's
+ *
+ * @author Oleg Gusakov
+ * @version $Id$
+ */
+public class MetadataTreeNodeGAComparator
+implements Comparator<MetadataTreeNode>
+{
+
+ public int compare(MetadataTreeNode n1, MetadataTreeNode n2)
+ {
+ return n1.getMd().getGA().compareTo( n2.getMd().getGA() );
+ }
+
+}
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeNodeGAComparator.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeNodeGAComparator.java
------------------------------------------------------------------------------
svn:keywords = Author Date Id Revision
Added: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeNodeGAVComparator.java
URL: http://svn.apache.org/viewvc/maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeNodeGAVComparator.java?rev=767705&view=auto
==============================================================================
--- maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeNodeGAVComparator.java (added)
+++ maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeNodeGAVComparator.java Wed Apr 22 22:56:48 2009
@@ -0,0 +1,40 @@
+/**
+ * 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.maven.mercury.metadata;
+
+import java.util.Comparator;
+
+import org.apache.maven.mercury.artifact.MetadataTreeNode;
+
+/**
+ * utility class for DefaultSatSolver. Assumes good data - no null's
+ *
+ * @author Oleg Gusakov
+ * @version $Id$
+ */
+public class MetadataTreeNodeGAVComparator
+implements Comparator<MetadataTreeNode>
+{
+
+ public int compare(MetadataTreeNode n1, MetadataTreeNode n2)
+ {
+ return n1.getMd().getGAV().compareTo( n2.getMd().getGAV() );
+ }
+
+}
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeNodeGAVComparator.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/MetadataTreeNodeGAVComparator.java
------------------------------------------------------------------------------
svn:keywords = Author Date Id Revision
Added: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/DefaultSatSolver.java
URL: http://svn.apache.org/viewvc/maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/DefaultSatSolver.java?rev=767705&view=auto
==============================================================================
--- maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/DefaultSatSolver.java (added)
+++ maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/DefaultSatSolver.java Wed Apr 22 22:56:48 2009
@@ -0,0 +1,664 @@
+/**
+ * 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.maven.mercury.metadata.sat;
+
+import java.math.BigInteger;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+
+import org.apache.maven.mercury.artifact.ArtifactMetadata;
+import org.apache.maven.mercury.artifact.MetadataTreeNode;
+import org.apache.maven.mercury.event.EventManager;
+import org.apache.maven.mercury.event.EventTypeEnum;
+import org.apache.maven.mercury.event.GenericEvent;
+import org.apache.maven.mercury.event.MercuryEventListener;
+import org.apache.maven.mercury.logging.IMercuryLogger;
+import org.apache.maven.mercury.logging.MercuryLoggerManager;
+import org.apache.maven.mercury.metadata.MetadataTreeNodeGAComparator;
+import org.apache.maven.mercury.metadata.MetadataTreeNodeGAVComparator;
+import org.codehaus.plexus.lang.DefaultLanguage;
+import org.codehaus.plexus.lang.Language;
+import org.sat4j.core.Vec;
+import org.sat4j.core.VecInt;
+import org.sat4j.pb.IPBSolver;
+import org.sat4j.pb.ObjectiveFunction;
+import org.sat4j.pb.SolverFactory;
+import org.sat4j.specs.ContradictionException;
+import org.sat4j.specs.IConstr;
+import org.sat4j.specs.IVec;
+import org.sat4j.specs.IVecInt;
+import org.sat4j.specs.TimeoutException;
+
+/**
+ * Default SAT4J implementation.
+ *
+ * @author Oleg Gusakov
+ * @version $Id$
+ */
+public class DefaultSatSolver
+implements SatSolver
+{
+ private static final IMercuryLogger LOG = MercuryLoggerManager.getLogger( DefaultSatSolver.class );
+ private static final Language LANG = new DefaultLanguage( DefaultSatSolver.class );
+
+ protected SatContext _context;
+ protected IPBSolver _solver = SolverFactory.newEclipseP2();
+ protected MetadataTreeNode _root;
+
+ protected EventManager _eventManager;
+
+ public static final BigInteger TWO = new BigInteger("2");
+
+ protected static final Comparator<MetadataTreeNode> gaComparator = new MetadataTreeNodeGAComparator();
+ //-----------------------------------------------------------------------
+ public static SatSolver create( MetadataTreeNode tree )
+ throws SatException
+ {
+ return new DefaultSatSolver( tree );
+ }
+ //-----------------------------------------------------------------------
+ public static SatSolver create( MetadataTreeNode tree, EventManager eventManager )
+ throws SatException
+ {
+ return new DefaultSatSolver( tree, eventManager );
+ }
+ //-----------------------------------------------------------------------
+ public DefaultSatSolver( MetadataTreeNode tree, EventManager eventManager )
+ throws SatException
+ {
+ this._eventManager = eventManager;
+ GenericEvent event = null;
+
+ if( tree == null)
+ throw new SatException( LANG.getMessage( "null.tree.arg" ) );
+
+ try
+ {
+ if( _eventManager != null )
+ event = new GenericEvent( EventTypeEnum.satSolver, EVENT_CREATE_SOLVER, tree.toString() );
+
+ if( tree.getId() == 0 )
+ MetadataTreeNode.reNumber( tree, 1 );
+
+ int nNodes = tree.countDistinctNodes();
+
+ LOG.debug( "SatContext: # of variables: "+nNodes );
+
+ _context = new SatContext( nNodes );
+ _solver.newVar( tree.countNodes() );
+ _root = tree;
+
+ try
+ {
+ addNode( tree );
+ }
+ catch (ContradictionException e)
+ {
+ throw new SatException(e);
+ }
+ }
+ finally
+ {
+ if( _eventManager != null )
+ {
+ event.stop();
+ _eventManager.fireEvent( event );
+ }
+ }
+ }
+ //-----------------------------------------------------------------------
+ public DefaultSatSolver( MetadataTreeNode tree )
+ throws SatException
+ {
+ this( tree, null );
+ }
+ //-----------------------------------------------------------------------
+ public final void applyPolicies( List<Comparator<MetadataTreeNode>> comparators )
+ throws SatException
+ {
+ if( comparators == null || comparators.size() < 1 )
+ return;
+
+ if( _root == null )
+ throw new SatException( "cannot apply policies to a null tree" );
+
+ // TODO og: assumption - around 128 GA's per tree. If more - map reallocates - slow down.
+ // TODO og: MERCURY-40
+ Map<String, List<MetadataTreeNode>> buckets = new LinkedHashMap<String, List<MetadataTreeNode>>(128);
+ fillBuckets( buckets, _root );
+ sortBuckets( buckets, comparators );
+ useBuckets( buckets );
+ }
+ //-----------------------------------------------------------------------
+ private void useBuckets( Map<String, List<MetadataTreeNode>> buckets )
+ throws SatException
+ {
+ if( buckets == null || buckets.size() < 1 )
+ return;
+
+ IVecInt vars = new VecInt( 128 );
+ IVec<BigInteger> coeffs = new Vec<BigInteger>( 128 );
+
+ int count = 0;
+
+ for( String key : buckets.keySet() )
+ {
+ List<MetadataTreeNode> bucket = buckets.get( key );
+
+// oleg: ? this is needed if optimization is "maximize"
+// Collections.reverse( bucket );
+
+ int bucketSize = bucket.size();
+
+ boolean bigBucket = bucketSize > 1;
+
+if( LOG.isDebugEnabled() )
+ LOG.debug( "\n\nBucket "+key );
+
+ IVecInt bucketVars = new VecInt( bucketSize );
+
+ for( int i=0; i<bucketSize; i++ )
+ {
+ MetadataTreeNode n = bucket.get(i);
+
+if( LOG.isDebugEnabled() )
+ LOG.debug( n.toString() );
+
+ SatVar var = _context.findOrAdd(n);
+ int varLiteral = var.getLiteral();
+
+ bucketVars.push( varLiteral );
+
+ if( bigBucket )
+ {
+ vars.push( varLiteral );
+
+ BigInteger cf = TWO.pow( count++ );
+
+ coeffs.push( cf );
+
+if( LOG.isDebugEnabled() )
+ LOG.debug( " "+cf+" x"+var.getLiteral() );
+ }
+
+ }
+
+ try
+ {
+ if( bucketVars != null && !bucketVars.isEmpty() )
+ {
+ _solver.addAtMost( bucketVars, 1 );
+ _solver.addAtLeast( bucketVars, 1 );
+ }
+ }
+ catch( ContradictionException e )
+ {
+ throw new SatException(e);
+ }
+
+if( LOG.isDebugEnabled() )
+ LOG.debug( "\n" );
+ }
+
+ if( vars.isEmpty() )
+ return;
+
+ _solver.setObjectiveFunction( new ObjectiveFunction( vars, coeffs ) );
+ }
+ //-----------------------------------------------------------------------
+ protected static final void sortBuckets(
+ Map<String, List<MetadataTreeNode>> buckets
+ , List<Comparator<MetadataTreeNode>> comparators
+ )
+ {
+ Comparator<MetadataTreeNode> lastComparator;
+ for( List<MetadataTreeNode> bucket : buckets.values() )
+ {
+ lastComparator = gaComparator;
+ for( Comparator<MetadataTreeNode> comparator : comparators )
+ {
+ sortBucket( bucket, comparator, lastComparator );
+ lastComparator = comparator;
+ }
+ // due to the nature of Comparator need to reverse the result
+ // as the best fit is now last
+ Collections.reverse( bucket );
+
+ // the best fit now first, and we don't need duplicate GAVs
+ removeDuplicateGAVs( bucket );
+
+ }
+ }
+ //-----------------------------------------------------------------------
+ // remove duplicates, preserving the order. The first one is the most fit,
+ // so need to delete from tail
+ protected static final void removeDuplicateGAVs( List<MetadataTreeNode> bucket )
+ {
+ if( bucket == null || bucket.size() < 2 )
+ return;
+
+ Comparator<MetadataTreeNode> gav = new MetadataTreeNodeGAVComparator();
+
+ int len = bucket.size();
+ int [] dups = new int[ len-1 ];
+ int cnt = 0;
+
+ for( int i=1; i<len; i++ )
+ {
+ MetadataTreeNode ti = bucket.get(i);
+
+ for( int j=0; j<i; j++ )
+ if( gav.compare( ti, bucket.get(j) ) == 0 )
+ {
+ dups[cnt++] = i;
+ break;
+ }
+ }
+
+ if( cnt > 0 )
+ for( int i=0; i<cnt; i++ )
+ bucket.remove( dups[cnt-i-1] );
+ }
+ //-----------------------------------------------------------------------
+ /**
+ * reorders the bucket's lastComparator equal subsets with comparator.
+ */
+ protected static final void sortBucket(
+ List<MetadataTreeNode> bucket
+ , Comparator<MetadataTreeNode> comparator
+ , Comparator<MetadataTreeNode> lastComparator
+ )
+ {
+ if( bucket == null || bucket.size() < 2 )
+ return;
+
+ int bLen = bucket.size();
+ MetadataTreeNode [] temp = bucket.toArray( new MetadataTreeNode[ bLen ] );
+
+ int wStart = -1;
+ int wLen = 0;
+ MetadataTreeNode [] work = new MetadataTreeNode[ bLen ];
+
+ MetadataTreeNode lastNode = null;
+ for( int i=0; i<bLen; i++ )
+ {
+ MetadataTreeNode n = temp[i];
+
+ if( lastNode == null )
+ {
+ lastNode = n;
+ continue;
+ }
+
+ if( lastComparator.compare(lastNode, n) == 0 )
+ {
+ if( wLen == 0 )
+ {
+ work[ wLen++ ] = lastNode;
+ wStart = i-1;
+ }
+
+ work[ wLen++ ] = n;
+
+ lastNode = n;
+
+ if( i < (bLen-1) )
+ continue;
+ }
+
+ if( wLen > 0 ) // eq list formed
+ {
+ reorder( work, wLen, comparator );
+ for( int j=0; j<wLen; j++ )
+ temp[ wStart+j ] = work[ j ];
+ wLen = 0;
+ wStart = -1;
+ }
+
+ lastNode = n;
+ }
+
+ bucket.clear();
+ for( int i=0; i<bLen; i++ )
+ bucket.add( temp[ i ] );
+ }
+ //-----------------------------------------------------------------------
+ private static final void reorder(
+ MetadataTreeNode[] work
+ , int wLen
+ , Comparator<MetadataTreeNode> comparator
+ )
+ {
+ MetadataTreeNode[] temp = new MetadataTreeNode[ wLen ];
+
+ for( int i=0; i< wLen; i++ )
+ temp[i] = work[i];
+
+ Arrays.sort( temp, comparator );
+
+ for( int i=0; i<wLen; i++ )
+ work[i] = temp[i];
+
+ }
+ //-----------------------------------------------------------------------
+ protected static final void fillBuckets(
+ Map<String, List<MetadataTreeNode>> buckets
+ , MetadataTreeNode node
+ )
+ {
+ String ga = node.getMd().getGA();
+ List<MetadataTreeNode> bucket = buckets.get(ga);
+ if( bucket == null )
+ {
+ // TODO og: assumption - around 32 GAVs per GA
+ bucket = new ArrayList<MetadataTreeNode>( 32 );
+ buckets.put( ga, bucket );
+ }
+
+ bucket.add( node );
+
+ if( ! node.hasChildren() )
+ return;
+
+ for( MetadataTreeNode kid : node.getChildren() )
+ {
+ fillBuckets( buckets, kid );
+ }
+ }
+ //-----------------------------------------------------------------------
+ private final void addPB( IVecInt lits, IVec<BigInteger> coeff, boolean ge, BigInteger cardinality )
+ throws ContradictionException
+ {
+ _solver.addPseudoBoolean( lits, coeff, ge, cardinality );
+
+if( LOG.isDebugEnabled() )
+ LOG.debug("PB: ");
+
+ for( int i=0; i<lits.size(); i++ )
+ {
+ int co = Integer.parseInt( ""+coeff.get(i) );
+ String sign = co < 0 ? "-" : "+";
+ int val = Math.abs(co);
+ String space = val == 1 ? "" : " ";
+
+if( LOG.isDebugEnabled() )
+ LOG.debug( " " + sign + (val==1?"":val) + space + "x"+lits.get(i) );
+ }
+if( LOG.isDebugEnabled() )
+ LOG.debug(( ge ? " >= " : " < ")+" "+cardinality );
+ }
+ //-----------------------------------------------------------------------
+ private final Map<ArtifactMetadata, List<MetadataTreeNode>> processChildren(
+ List<ArtifactMetadata> queries
+ , List<MetadataTreeNode> children
+ )
+ throws SatException
+ {
+ if( queries == null || queries.size() < 1 )
+ return null;
+
+ if( children == null || children.size() < 1 )
+ throw new SatException("there are queries, but not results. Queries: "+queries);
+
+ // TODO og: MERCURY-40
+ Map<ArtifactMetadata, List<MetadataTreeNode>> res = new LinkedHashMap<ArtifactMetadata, List<MetadataTreeNode>>( queries.size() );
+
+ for( ArtifactMetadata q : queries )
+ {
+ List<MetadataTreeNode> bucket = new ArrayList<MetadataTreeNode>(4);
+ String queryGA = q.getGA();
+
+ for( MetadataTreeNode tn : children )
+ {
+ if( tn.getMd() == null )
+ throw new SatException("resulting tree node without metadata for query "+q );
+
+ if( queryGA.equals( tn.getMd().getGA()) )
+ {
+ bucket.add(tn);
+ }
+ }
+
+ if( bucket.size() < 1 )
+ throw new SatException("No children for query "+queryGA );
+
+ res.put( q, bucket );
+ }
+
+ return res;
+ }
+ //-----------------------------------------------------------------------
+ private final void addNode( MetadataTreeNode node )
+ throws ContradictionException, SatException
+ {
+ if( node == null )
+ return;
+
+ if( node.getMd() == null )
+ throw new SatException("found a node without metadata");
+
+ SatVar nodeLit = _context.findOrAdd( node );
+
+ // this one is a must :)
+ if( node.getParent() == null )
+ addPB( SatHelper.getSmallOnes( nodeLit.getLiteral() ), SatHelper.getBigOnes(1,false), true, BigInteger.ONE );
+
+ if( ! node.hasChildren() )
+ return;
+
+ Map<ArtifactMetadata,List<MetadataTreeNode>> kids = processChildren( node.getQueries(), node.getChildren() );
+
+ // leaf node in this scope
+ if( kids == null )
+ return;
+
+ for( Map.Entry<ArtifactMetadata,List<MetadataTreeNode>> kid : kids.entrySet() )
+ {
+ ArtifactMetadata query = kid.getKey();
+
+ List<MetadataTreeNode> range = kid.getValue();
+
+ if( range.size() > 1 )
+ {
+ addRange( nodeLit.getLiteral(), range, query.isOptional() );
+ for( MetadataTreeNode tn : range )
+ {
+ addNode( tn );
+ }
+ }
+ else
+ {
+ MetadataTreeNode child = range.get(0);
+ SatVar kidLit = _context.findOrAdd( child );
+
+ addPB( SatHelper.getSmallOnes( new int [] { nodeLit.getLiteral(), kidLit.getLiteral() } )
+ , SatHelper.getBigOnes( 1, -1 )
+ , true, BigInteger.ZERO
+ );
+// addRange( nodeLit.getLiteral(), range, query.isOptional() );
+ addNode( child );
+ }
+
+ }
+ }
+ //-----------------------------------------------------------------------
+ private final int [] addRange( int parentLiteral, List<MetadataTreeNode> range, boolean optional )
+ throws ContradictionException, SatException
+ {
+ SatVar literal;
+
+ int [] literals = new int[ range.size() ];
+
+ int count = 0;
+
+ for( MetadataTreeNode tn : range )
+ {
+ literal = _context.findOrAdd( tn );
+ literals[count++] = literal.getLiteral();
+
+ // implication to parent
+ addPB( SatHelper.getSmallOnes( new int [] { parentLiteral, literal.getLiteral() } )
+ , SatHelper.getBigOnes( 1, -1 )
+ , true, BigInteger.ZERO
+ );
+ }
+
+ IVecInt rangeVector = SatHelper.getSmallOnes( literals );
+
+ if( optional ) // Sxi >= 0
+ {
+if( LOG.isDebugEnabled() )
+ LOG.debug( "optional range: atMost 1: "+ SatHelper.vectorToString( rangeVector) );
+
+ _solver.addAtMost( rangeVector, 1 );
+ }
+ else // Sxi = 1
+ {
+if( LOG.isDebugEnabled() )
+ LOG.debug( "range: " + SatHelper.vectorToString( rangeVector) );
+
+ IConstr atLeast = _solver.addAtLeast( rangeVector, 1 );
+ if( LOG.isDebugEnabled() )
+ LOG.debug( "atLeast: " + SatHelper.vectorToString( atLeast) );
+
+ IConstr atMost = _solver.addAtMost( rangeVector, 1 );
+ if( LOG.isDebugEnabled() )
+ LOG.debug( "atMost: " + SatHelper.vectorToString( atMost) );
+
+ }
+
+ return literals;
+ }
+ //-----------------------------------------------------------------------
+ public final List<ArtifactMetadata> solve()
+ throws SatException
+ {
+ List<ArtifactMetadata> res = null;
+ GenericEvent event = null;
+
+ try
+ {
+ if( _eventManager != null )
+ event = new GenericEvent( EventTypeEnum.satSolver, EVENT_SOLVE, _root.toString() );
+
+ if( _solver.isSatisfiable() )
+ {
+ res = new ArrayList<ArtifactMetadata>( _root.countNodes() );
+
+ int [] model = _solver.model();
+
+if( LOG.isDebugEnabled() )
+ if( model != null )
+ {
+ StringBuilder sb = new StringBuilder();
+ String comma = "";
+ for( int m : model )
+ {
+ sb.append( comma+m );
+ comma = ", ";
+ }
+ LOG.debug( '['+sb.toString()+']' );
+ }
+ else
+ LOG.debug( "model is null" );
+
+ for( int i : model )
+ if( i > 0 )
+ res.add( _context.getMd( i ) );
+ }
+ else // not satisfied
+ {
+ throw new SatException( LANG.getMessage( "no.solution", _root.toString() ));
+ }
+ }
+ catch (TimeoutException e)
+ {
+ throw new SatException( e );
+ }
+ finally
+ {
+ if( _eventManager != null )
+ {
+ event.stop();
+ _eventManager.fireEvent( event );
+ }
+ }
+ return res;
+ }
+ //-----------------------------------------------------------------------
+ public final MetadataTreeNode solveAsTree()
+ throws SatException
+ {
+ try
+ {
+ if( _solver.isSatisfiable() )
+ {
+ int [] model = _solver.model();
+
+if( LOG.isDebugEnabled() )
+ if( model != null )
+ {
+ StringBuilder sb = new StringBuilder();
+ String comma = "";
+ for( int m : model )
+ {
+ sb.append( comma+m );
+ comma = ", ";
+ }
+ LOG.debug( '['+sb.toString()+']' );
+ }
+ else
+ LOG.debug( "model is null" );
+
+ return _context.getSolutionSubtree( _root, model );
+ }
+ return null;
+ }
+ catch (TimeoutException e)
+ {
+ throw new SatException( e );
+ }
+
+ }
+ //-----------------------------------------------------------------------
+ public void register( MercuryEventListener listener )
+ {
+ if( _eventManager == null )
+ _eventManager = new EventManager();
+
+ _eventManager.register( listener );
+ }
+
+ public void setEventManager( EventManager eventManager )
+ {
+ _eventManager = eventManager;
+ }
+
+ public void unRegister( MercuryEventListener listener )
+ {
+ if( _eventManager != null )
+ _eventManager.unRegister( listener );
+ }
+ //-----------------------------------------------------------------------
+}
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/DefaultSatSolver.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/DefaultSatSolver.java
------------------------------------------------------------------------------
svn:keywords = Author Date Id Revision
Added: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/DependencyConflictException.java
URL: http://svn.apache.org/viewvc/maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/DependencyConflictException.java?rev=767705&view=auto
==============================================================================
--- maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/DependencyConflictException.java (added)
+++ maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/DependencyConflictException.java Wed Apr 22 22:56:48 2009
@@ -0,0 +1,69 @@
+/*
+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.maven.mercury.metadata.sat;
+
+/**
+ *
+ *
+ * @author Oleg Gusakov
+ * @version $Id$
+ *
+ */
+public class DependencyConflictException
+ extends SatException
+{
+
+ /**
+ *
+ */
+ public DependencyConflictException()
+ {
+ // TODO Auto-generated constructor stub
+ }
+
+ /**
+ * @param message
+ */
+ public DependencyConflictException( String message )
+ {
+ super( message );
+ // TODO Auto-generated constructor stub
+ }
+
+ /**
+ * @param cause
+ */
+ public DependencyConflictException( Throwable cause )
+ {
+ super( cause );
+ // TODO Auto-generated constructor stub
+ }
+
+ /**
+ * @param message
+ * @param cause
+ */
+ public DependencyConflictException( String message, Throwable cause )
+ {
+ super( message, cause );
+ // TODO Auto-generated constructor stub
+ }
+
+}
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/DependencyConflictException.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/DependencyConflictException.java
------------------------------------------------------------------------------
svn:keywords = Author Date Id Revision
Added: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/HelpingSatSolver.java
URL: http://svn.apache.org/viewvc/maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/HelpingSatSolver.java?rev=767705&view=auto
==============================================================================
--- maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/HelpingSatSolver.java (added)
+++ maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/HelpingSatSolver.java Wed Apr 22 22:56:48 2009
@@ -0,0 +1,651 @@
+/**
+ * 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.maven.mercury.metadata.sat;
+
+import java.math.BigInteger;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+
+import org.apache.maven.mercury.artifact.ArtifactMetadata;
+import org.apache.maven.mercury.artifact.MetadataTreeNode;
+import org.apache.maven.mercury.event.EventManager;
+import org.apache.maven.mercury.event.EventTypeEnum;
+import org.apache.maven.mercury.event.GenericEvent;
+import org.apache.maven.mercury.event.MercuryEventListener;
+import org.apache.maven.mercury.logging.IMercuryLogger;
+import org.apache.maven.mercury.logging.MercuryLoggerManager;
+import org.apache.maven.mercury.metadata.MetadataTreeNodeGAComparator;
+import org.apache.maven.mercury.metadata.MetadataTreeNodeGAVComparator;
+import org.codehaus.plexus.lang.DefaultLanguage;
+import org.codehaus.plexus.lang.Language;
+import org.sat4j.core.Vec;
+import org.sat4j.core.VecInt;
+import org.sat4j.pb.IPBSolver;
+import org.sat4j.pb.ObjectiveFunction;
+import org.sat4j.pb.SolverFactory;
+import org.sat4j.specs.ContradictionException;
+import org.sat4j.specs.IConstr;
+import org.sat4j.specs.IVec;
+import org.sat4j.specs.IVecInt;
+import org.sat4j.specs.TimeoutException;
+
+/**
+ * Default SAT4J implementation.
+ *
+ * @author Oleg Gusakov
+ * @version $Id$
+ */
+public class HelpingSatSolver
+{}
+//implements SatSolver
+//{
+// private static final IMercuryLogger LOG = MercuryLoggerManager.getLogger( HelpingSatSolver.class );
+// private static final Language LANG = new DefaultLanguage( HelpingSatSolver.class );
+//
+// private DependencyHelper<MetadataTreeNode,String> _helper = new DependencyHelper<MetadataTreeNode,String>( SolverFactory.newEclipseP2() );
+// protected MetadataTreeNode _root;
+//
+// protected EventManager _eventManager;
+//
+// protected static final Comparator<MetadataTreeNode> gaComparator = new MetadataTreeNodeGAComparator();
+// //-----------------------------------------------------------------------
+// public static SatSolver create( MetadataTreeNode tree )
+// throws SatException
+// {
+// return new HelpingSatSolver( tree );
+// }
+// //-----------------------------------------------------------------------
+// public static SatSolver create( MetadataTreeNode tree, EventManager eventManager )
+// throws SatException
+// {
+// return new HelpingSatSolver( tree, eventManager );
+// }
+// //-----------------------------------------------------------------------
+// public HelpingSatSolver( MetadataTreeNode tree, EventManager eventManager )
+// throws SatException
+// {
+// this._eventManager = eventManager;
+// GenericEvent event = null;
+//
+// if( tree == null)
+// throw new SatException( LANG.getMessage( "null.tree.arg" ) );
+//
+// try
+// {
+// if( _eventManager != null )
+// event = new GenericEvent( EventTypeEnum.satSolver, EVENT_CREATE_SOLVER, tree.toString() );
+//
+// if( tree.getId() == 0 )
+// MetadataTreeNode.reNumber( tree, 1 );
+//
+// int nNodes = tree.countDistinctNodes();
+//
+// LOG.debug( "SatContext: # of variables: "+nNodes );
+//
+// _root = tree;
+//
+// try
+// {
+// addNode( tree );
+// }
+// catch (ContradictionException e)
+// {
+// throw new SatException(e);
+// }
+// }
+// finally
+// {
+// if( _eventManager != null )
+// {
+// event.stop();
+// _eventManager.fireEvent( event );
+// }
+// }
+// }
+// //-----------------------------------------------------------------------
+// public HelpingSatSolver( MetadataTreeNode tree )
+// throws SatException
+// {
+// this( tree, null );
+// }
+// //-----------------------------------------------------------------------
+// public final void applyPolicies( List<Comparator<MetadataTreeNode>> comparators )
+// throws SatException
+// {
+// if( comparators == null || comparators.size() < 1 )
+// return;
+//
+// if( _root == null )
+// throw new SatException( "cannot apply policies to a null tree" );
+//
+// // TODO og: assumption - around 128 GA's per tree. If more - map reallocates - slow down.
+// // TODO og: MERCURY-40
+// Map<String, List<MetadataTreeNode>> buckets = new LinkedHashMap<String, List<MetadataTreeNode>>(128);
+// fillBuckets( buckets, _root );
+// sortBuckets( buckets, comparators );
+// useBuckets( buckets );
+// }
+// //-----------------------------------------------------------------------
+// private void useBuckets( Map<String, List<MetadataTreeNode>> buckets )
+// throws SatException
+// {
+// if( buckets == null || buckets.size() < 1 )
+// return;
+//
+// IVecInt vars = new VecInt( 128 );
+// IVec<BigInteger> coeffs = new Vec<BigInteger>( 128 );
+//
+// int count = 0;
+//
+// for( String key : buckets.keySet() )
+// {
+// List<MetadataTreeNode> bucket = buckets.get( key );
+//
+//// oleg: ? this is needed if optimization is "maximize"
+//// Collections.reverse( bucket );
+//
+// int bucketSize = bucket.size();
+//
+// boolean bigBucket = bucketSize > 1;
+//
+//if( LOG.isDebugEnabled() )
+// LOG.debug( "\n\nBucket "+key );
+//
+// IVecInt bucketVars = new VecInt( bucketSize );
+//
+// for( int i=0; i<bucketSize; i++ )
+// {
+// MetadataTreeNode n = bucket.get(i);
+//
+//if( LOG.isDebugEnabled() )
+// LOG.debug( n.toString() );
+//
+// SatVar var = _context.findOrAdd(n);
+// int varLiteral = var.getLiteral();
+//
+// bucketVars.push( varLiteral );
+//
+// if( bigBucket )
+// {
+// vars.push( varLiteral );
+//
+// long cf = (long)Math.pow( 2, count++ );
+//
+// coeffs.push( BigInteger.valueOf( cf ) );
+//
+//if( LOG.isDebugEnabled() )
+// LOG.debug( " "+cf+" x"+var.getLiteral() );
+// }
+//
+// }
+//
+// try
+// {
+// if( bucketVars != null && !bucketVars.isEmpty() )
+// {
+// _solver.addAtMost( bucketVars, 1 );
+// _solver.addAtLeast( bucketVars, 1 );
+// }
+// }
+// catch( ContradictionException e )
+// {
+// throw new SatException(e);
+// }
+//
+//if( LOG.isDebugEnabled() )
+// LOG.debug( "\n" );
+// }
+//
+// if( vars.isEmpty() )
+// return;
+//
+// _solver.setObjectiveFunction( new ObjectiveFunction( vars, coeffs ) );
+// }
+// //-----------------------------------------------------------------------
+// protected static final void sortBuckets(
+// Map<String, List<MetadataTreeNode>> buckets
+// , List<Comparator<MetadataTreeNode>> comparators
+// )
+// {
+// Comparator<MetadataTreeNode> lastComparator;
+// for( List<MetadataTreeNode> bucket : buckets.values() )
+// {
+// lastComparator = gaComparator;
+// for( Comparator<MetadataTreeNode> comparator : comparators )
+// {
+// sortBucket( bucket, comparator, lastComparator );
+// lastComparator = comparator;
+// }
+// // due to the nature of Comparator need to reverse the result
+// // as the best fit is now last
+// Collections.reverse( bucket );
+//
+// // the best fit now first, and we don't need duplicate GAVs
+// removeDuplicateGAVs( bucket );
+//
+// }
+// }
+// //-----------------------------------------------------------------------
+// // remove duplicates, preserving the order. The first one is the most fit,
+// // so need to delete from tail
+// protected static final void removeDuplicateGAVs( List<MetadataTreeNode> bucket )
+// {
+// if( bucket == null || bucket.size() < 2 )
+// return;
+//
+// Comparator<MetadataTreeNode> gav = new MetadataTreeNodeGAVComparator();
+//
+// int len = bucket.size();
+// int [] dups = new int[ len-1 ];
+// int cnt = 0;
+//
+// for( int i=1; i<len; i++ )
+// {
+// MetadataTreeNode ti = bucket.get(i);
+//
+// for( int j=0; j<i; j++ )
+// if( gav.compare( ti, bucket.get(j) ) == 0 )
+// {
+// dups[cnt++] = i;
+// break;
+// }
+// }
+//
+// if( cnt > 0 )
+// for( int i=0; i<cnt; i++ )
+// bucket.remove( dups[cnt-i-1] );
+// }
+// //-----------------------------------------------------------------------
+// /**
+// * reorders the bucket's lastComparator equal subsets with comparator.
+// */
+// protected static final void sortBucket(
+// List<MetadataTreeNode> bucket
+// , Comparator<MetadataTreeNode> comparator
+// , Comparator<MetadataTreeNode> lastComparator
+// )
+// {
+// if( bucket == null || bucket.size() < 2 )
+// return;
+//
+// int bLen = bucket.size();
+// MetadataTreeNode [] temp = bucket.toArray( new MetadataTreeNode[ bLen ] );
+//
+// int wStart = -1;
+// int wLen = 0;
+// MetadataTreeNode [] work = new MetadataTreeNode[ bLen ];
+//
+// MetadataTreeNode lastNode = null;
+// for( int i=0; i<bLen; i++ )
+// {
+// MetadataTreeNode n = temp[i];
+//
+// if( lastNode == null )
+// {
+// lastNode = n;
+// continue;
+// }
+//
+// if( lastComparator.compare(lastNode, n) == 0 )
+// {
+// if( wLen == 0 )
+// {
+// work[ wLen++ ] = lastNode;
+// wStart = i-1;
+// }
+//
+// work[ wLen++ ] = n;
+//
+// lastNode = n;
+//
+// if( i < (bLen-1) )
+// continue;
+// }
+//
+// if( wLen > 0 ) // eq list formed
+// {
+// reorder( work, wLen, comparator );
+// for( int j=0; j<wLen; j++ )
+// temp[ wStart+j ] = work[ j ];
+// wLen = 0;
+// wStart = -1;
+// }
+//
+// lastNode = n;
+// }
+//
+// bucket.clear();
+// for( int i=0; i<bLen; i++ )
+// bucket.add( temp[ i ] );
+// }
+// //-----------------------------------------------------------------------
+// private static final void reorder(
+// MetadataTreeNode[] work
+// , int wLen
+// , Comparator<MetadataTreeNode> comparator
+// )
+// {
+// MetadataTreeNode[] temp = new MetadataTreeNode[ wLen ];
+//
+// for( int i=0; i< wLen; i++ )
+// temp[i] = work[i];
+//
+// Arrays.sort( temp, comparator );
+//
+// for( int i=0; i<wLen; i++ )
+// work[i] = temp[i];
+//
+// }
+// //-----------------------------------------------------------------------
+// protected static final void fillBuckets(
+// Map<String, List<MetadataTreeNode>> buckets
+// , MetadataTreeNode node
+// )
+// {
+// String ga = node.getMd().getGA();
+// List<MetadataTreeNode> bucket = buckets.get(ga);
+// if( bucket == null )
+// {
+// // TODO og: assumption - around 32 GAVs per GA
+// bucket = new ArrayList<MetadataTreeNode>( 32 );
+// buckets.put( ga, bucket );
+// }
+//
+// bucket.add( node );
+//
+// if( ! node.hasChildren() )
+// return;
+//
+// for( MetadataTreeNode kid : node.getChildren() )
+// {
+// fillBuckets( buckets, kid );
+// }
+// }
+// //-----------------------------------------------------------------------
+// private final void addPB( IVecInt lits, IVec<BigInteger> coeff, boolean ge, BigInteger cardinality )
+// throws ContradictionException
+// {
+// _solver.addPseudoBoolean( lits, coeff, ge, cardinality );
+//
+//if( LOG.isDebugEnabled() )
+// LOG.debug("PB: ");
+//
+// for( int i=0; i<lits.size(); i++ )
+// {
+// int co = Integer.parseInt( ""+coeff.get(i) );
+// String sign = co < 0 ? "-" : "+";
+// int val = Math.abs(co);
+// String space = val == 1 ? "" : " ";
+//
+//if( LOG.isDebugEnabled() )
+// LOG.debug( " " + sign + (val==1?"":val) + space + "x"+lits.get(i) );
+// }
+//if( LOG.isDebugEnabled() )
+// LOG.debug(( ge ? " >= " : " < ")+" "+cardinality );
+// }
+// //-----------------------------------------------------------------------
+// private final Map<ArtifactMetadata, List<MetadataTreeNode>> processChildren(
+// List<ArtifactMetadata> queries
+// , List<MetadataTreeNode> children
+// )
+// throws SatException
+// {
+// if( queries == null || queries.size() < 1 )
+// return null;
+//
+// if( children == null || children.size() < 1 )
+// throw new SatException("there are queries, but not results. Queries: "+queries);
+//
+// // TODO og: MERCURY-40
+// Map<ArtifactMetadata, List<MetadataTreeNode>> res = new LinkedHashMap<ArtifactMetadata, List<MetadataTreeNode>>( queries.size() );
+//
+// for( ArtifactMetadata q : queries )
+// {
+// List<MetadataTreeNode> bucket = new ArrayList<MetadataTreeNode>(4);
+// String queryGA = q.getGA();
+//
+// for( MetadataTreeNode tn : children )
+// {
+// if( tn.getMd() == null )
+// throw new SatException("resulting tree node without metadata for query "+q );
+//
+// if( queryGA.equals( tn.getMd().getGA()) )
+// {
+// bucket.add(tn);
+// }
+// }
+//
+// if( bucket.size() < 1 )
+// throw new SatException("No children for query "+queryGA );
+//
+// res.put( q, bucket );
+// }
+//
+// return res;
+// }
+// //-----------------------------------------------------------------------
+// private final void addNode( MetadataTreeNode node )
+// throws ContradictionException, SatException
+// {
+// if( node == null )
+// return;
+//
+// if( node.getMd() == null )
+// throw new SatException("found a node without metadata");
+//
+// // this one is a must :)
+// if( node.getParent() == null )
+// _helper.setTrue( node, node.getName() );
+//
+// if( ! node.hasChildren() )
+// return;
+//
+// Map<ArtifactMetadata,List<MetadataTreeNode>> kids = processChildren( node.getQueries(), node.getChildren() );
+//
+// // leaf node in this scope
+// if( kids == null )
+// return;
+//
+// for( Map.Entry<ArtifactMetadata,List<MetadataTreeNode>> kid : kids.entrySet() )
+// {
+// ArtifactMetadata query = kid.getKey();
+//
+// List<MetadataTreeNode> range = kid.getValue();
+//
+// if( range.size() > 1 )
+// {
+// addRange( nodeLit.getLiteral(), range, query.isOptional() );
+// for( MetadataTreeNode tn : range )
+// {
+// addNode( tn );
+// }
+// }
+// else
+// {
+// MetadataTreeNode child = range.get(0);
+// SatVar kidLit = _context.findOrAdd( child );
+//
+// addPB( SatHelper.getSmallOnes( new int [] { nodeLit.getLiteral(), kidLit.getLiteral() } )
+// , SatHelper.getBigOnes( 1, -1 )
+// , true, BigInteger.ZERO
+// );
+//// addRange( nodeLit.getLiteral(), range, query.isOptional() );
+// addNode( child );
+// }
+//
+// }
+// }
+// //-----------------------------------------------------------------------
+// private final int [] addRange( int parentLiteral, List<MetadataTreeNode> range, boolean optional )
+// throws ContradictionException, SatException
+// {
+// SatVar literal;
+//
+// int [] literals = new int[ range.size() ];
+//
+// int count = 0;
+//
+// for( MetadataTreeNode tn : range )
+// {
+// literal = _context.findOrAdd( tn );
+// literals[count++] = literal.getLiteral();
+//
+// // implication to parent
+// addPB( SatHelper.getSmallOnes( new int [] { parentLiteral, literal.getLiteral() } )
+// , SatHelper.getBigOnes( 1, -1 )
+// , true, BigInteger.ZERO
+// );
+// }
+//
+// IVecInt rangeVector = SatHelper.getSmallOnes( literals );
+//
+// if( optional ) // Sxi >= 0
+// {
+//if( LOG.isDebugEnabled() )
+// LOG.debug( "optional range: atMost 1: "+ SatHelper.vectorToString( rangeVector) );
+//
+// _solver.addAtMost( rangeVector, 1 );
+// }
+// else // Sxi = 1
+// {
+//if( LOG.isDebugEnabled() )
+// LOG.debug( "range: " + SatHelper.vectorToString( rangeVector) );
+//
+// IConstr atLeast = _solver.addAtLeast( rangeVector, 1 );
+// if( LOG.isDebugEnabled() )
+// LOG.debug( "atLeast: " + SatHelper.vectorToString( atLeast) );
+//
+// IConstr atMost = _solver.addAtMost( rangeVector, 1 );
+// if( LOG.isDebugEnabled() )
+// LOG.debug( "atMost: " + SatHelper.vectorToString( atMost) );
+//
+// }
+//
+// return literals;
+// }
+// //-----------------------------------------------------------------------
+// public final List<ArtifactMetadata> solve()
+// throws SatException
+// {
+// List<ArtifactMetadata> res = null;
+// GenericEvent event = null;
+//
+// try
+// {
+// if( _eventManager != null )
+// event = new GenericEvent( EventTypeEnum.satSolver, EVENT_SOLVE, _root.toString() );
+//
+// if( _solver.isSatisfiable() )
+// {
+// res = new ArrayList<ArtifactMetadata>( _root.countNodes() );
+//
+// int [] model = _solver.model();
+//
+//if( LOG.isDebugEnabled() )
+// if( model != null )
+// {
+// StringBuilder sb = new StringBuilder();
+// String comma = "";
+// for( int m : model )
+// {
+// sb.append( comma+m );
+// comma = ", ";
+// }
+// LOG.debug( '['+sb.toString()+']' );
+// }
+// else
+// LOG.debug( "model is null" );
+//
+// for( int i : model )
+// if( i > 0 )
+// res.add( _context.getMd( i ) );
+// }
+// }
+// catch (TimeoutException e)
+// {
+// throw new SatException( e );
+// }
+// finally
+// {
+// if( _eventManager != null )
+// {
+// event.stop();
+// _eventManager.fireEvent( event );
+// }
+// }
+// return res;
+// }
+// //-----------------------------------------------------------------------
+// public final MetadataTreeNode solveAsTree()
+// throws SatException
+// {
+// try
+// {
+// if( _helper.hasASolution() )
+// {
+//
+// IVec<MetadataTreeNode> solution = _helper.getSolution();
+//
+// if( solution == null )
+// return null;
+//
+// for( Iterator<MetadataTreeNode> i = solution.iterator(); i.hasNext(); )
+// {
+// MetadataTreeNode mtn = i.next();
+//
+// if( mtn.getParent() == null )
+// return mtn;
+// }
+//
+// return null;
+// }
+// }
+// catch (TimeoutException e)
+// {
+// throw new SatException( e );
+// }
+//
+// }
+// //-----------------------------------------------------------------------
+// public void register( MercuryEventListener listener )
+// {
+// if( _eventManager == null )
+// _eventManager = new EventManager();
+//
+// _eventManager.register( listener );
+// }
+//
+// public void setEventManager( EventManager eventManager )
+// {
+// _eventManager = eventManager;
+// }
+//
+// public void unRegister( MercuryEventListener listener )
+// {
+// if( _eventManager != null )
+// _eventManager.unRegister( listener );
+// }
+// //-----------------------------------------------------------------------
+//}
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/HelpingSatSolver.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/HelpingSatSolver.java
------------------------------------------------------------------------------
svn:keywords = Author Date Id Revision
Added: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/Messages.properties
URL: http://svn.apache.org/viewvc/maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/Messages.properties?rev=767705&view=auto
==============================================================================
--- maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/Messages.properties (added)
+++ maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/Messages.properties Wed Apr 22 22:56:48 2009
@@ -0,0 +1,26 @@
+#
+# 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.
+#
+null.tree=tree root is null
+null.tree.md=tree root metadata is null
+null.model=model is null
+empty.model=model is null
+
+null.tree.arg=cannot create a solver for an empty [null] tree
+
+no.solution=no solution for the supplied tree, starting at {0}
\ No newline at end of file
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/Messages.properties
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/Messages.properties
------------------------------------------------------------------------------
svn:keywords = Author Date Id Revision
Added: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/SatContext.java
URL: http://svn.apache.org/viewvc/maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/SatContext.java?rev=767705&view=auto
==============================================================================
--- maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/SatContext.java (added)
+++ maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/SatContext.java Wed Apr 22 22:56:48 2009
@@ -0,0 +1,160 @@
+/**
+ * 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.maven.mercury.metadata.sat;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+import org.apache.maven.mercury.artifact.ArtifactMetadata;
+import org.apache.maven.mercury.artifact.MetadataTreeNode;
+import org.apache.maven.mercury.logging.IMercuryLogger;
+import org.apache.maven.mercury.logging.MercuryLoggerManager;
+import org.codehaus.plexus.lang.DefaultLanguage;
+import org.codehaus.plexus.lang.Language;
+
+ /**
+ * This class hold all variables fed to the SAT solver. Because of the
+ * tree unwinding algorithm all pivots (optional nodes) should be supplied first
+ *
+ * @author <a href="oleg@codehaus.org">Oleg Gusakov</a>
+ */
+class SatContext
+{
+ private static final Language LANG = new DefaultLanguage(SatContext.class);
+ private static final IMercuryLogger LOG = MercuryLoggerManager.getLogger( SatContext.class );
+
+ Map<MetadataTreeNode,SatVar> variables;
+ //-----------------------------------------------------------------------
+ public SatContext( int estimatedTreeSize )
+ {
+ variables = new HashMap<MetadataTreeNode,SatVar>( estimatedTreeSize );
+ }
+ //-----------------------------------------------------------------------
+ public SatVar findOrAdd( MetadataTreeNode n )
+ throws SatException
+ {
+ if( n == null )
+ throw new SatException( "cannot create a literal out of a null metadata: "+n );
+
+ SatVar var = variables.get( n );
+
+ if( var != null )
+ {
+ if( LOG.isDebugEnabled() )
+ LOG.debug( var.toString() );
+ return var;
+ }
+
+ var = new SatVar( n );
+ variables.put( n, var );
+
+ if( LOG.isDebugEnabled() )
+ LOG.debug( var.toString() );
+
+ return var;
+ }
+ //-----------------------------------------------------------------------
+ public ArtifactMetadata getMd( int literal )
+ {
+ for( SatVar v : variables.values() )
+ if( v._literal == literal )
+ return v.getMd();
+
+ return null;
+ }
+ //-----------------------------------------------------------------------
+ private static final boolean isSolution( int m, int [] model )
+ {
+ for( int mm : model )
+ if( mm == m )
+ return true;
+
+ return false;
+ }
+ //-----------------------------------------------------------------------
+ public MetadataTreeNode getSolutionSubtree( MetadataTreeNode tree, int [] model )
+ {
+ if( tree == null )
+ throw new IllegalArgumentException( LANG.getMessage( "null.tree" ) );
+
+ if( tree.getMd() == null )
+ throw new IllegalArgumentException( LANG.getMessage( "null.tree.md" ) );
+
+ if( model == null )
+ throw new IllegalArgumentException( LANG.getMessage( "null.model" ) );
+
+ if( model.length < 1 )
+ throw new IllegalArgumentException( LANG.getMessage( "empty.model" ) );
+
+ int sz = 0;
+
+ for( int m : model )
+ if( m > 0 )
+ ++sz;
+
+ if( sz == 0)
+ return null;
+
+ MetadataTreeNode res = MetadataTreeNode.deepCopy( tree );
+
+ cleanTree( res, model );
+
+ return res;
+ }
+ //-----------------------------------------------------------------------
+ private static final void cleanTree( MetadataTreeNode tn, int [] model )
+ {
+ if( ! tn.hasChildren() )
+ return;
+
+ List<MetadataTreeNode> badKids = new ArrayList<MetadataTreeNode>();
+
+ for( MetadataTreeNode kid : tn.getChildren() )
+ if( ! isSolution( kid.getId(), model ) )
+ badKids.add( kid );
+
+ tn.getChildren().removeAll( badKids );
+
+ if( ! tn.hasChildren() )
+ return;
+
+ for( MetadataTreeNode kid : tn.getChildren() )
+ cleanTree( kid, model );
+ }
+ //-----------------------------------------------------------------------
+// @Override
+// public String toString()
+// {
+// if(varCount < 1)
+// return "";
+// StringBuilder sb = new StringBuilder( 32*varCount );
+// char comma = '[';
+//
+// for( SatVar var : variables )
+// {
+// sb.append(comma+" x"+var._literal+"="+var._md.toString() );
+// comma = ',';
+// }
+// return sb.toString()+']';
+// }
+ //-----------------------------------------------------------------------
+ //-----------------------------------------------------------------------
+}
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/SatContext.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/SatContext.java
------------------------------------------------------------------------------
svn:keywords = Author Date Id Revision
Added: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/SatException.java
URL: http://svn.apache.org/viewvc/maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/SatException.java?rev=767705&view=auto
==============================================================================
--- maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/SatException.java (added)
+++ maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/SatException.java Wed Apr 22 22:56:48 2009
@@ -0,0 +1,48 @@
+/**
+ * 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.maven.mercury.metadata.sat;
+
+/**
+ * @author <a href="oleg@codehaus.org">Oleg Gusakov</a>
+ */
+public class SatException
+ extends Exception
+{
+ private static final long serialVersionUID = -2461839690564604496L;
+
+ public SatException()
+ {
+ }
+
+ public SatException(String message)
+ {
+ super(message);
+ }
+
+ public SatException(Throwable cause)
+ {
+ super(cause);
+ }
+
+ public SatException(String message, Throwable cause)
+ {
+ super(message, cause);
+ }
+
+}
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/SatException.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: maven/mercury/trunk/mercury-core/src/main/java/org/apache/maven/mercury/metadata/sat/SatException.java
------------------------------------------------------------------------------
svn:keywords = Author Date Id Revision