bddbddb-checkins Mailing List for bddbddb: BDD-Based Deductive Database
Status: Beta
Brought to you by:
joewhaley
You can subscribe to this list here.
2004 |
Jan
|
Feb
|
Mar
|
Apr
|
May
|
Jun
|
Jul
(224) |
Aug
(95) |
Sep
(61) |
Oct
(131) |
Nov
(58) |
Dec
|
---|---|---|---|---|---|---|---|---|---|---|---|---|
2005 |
Jan
(30) |
Feb
(25) |
Mar
(58) |
Apr
(44) |
May
(54) |
Jun
(24) |
Jul
(6) |
Aug
(13) |
Sep
(5) |
Oct
(8) |
Nov
|
Dec
|
2006 |
Jan
(2) |
Feb
(1) |
Mar
|
Apr
|
May
(2) |
Jun
(3) |
Jul
(5) |
Aug
|
Sep
(1) |
Oct
|
Nov
(1) |
Dec
(1) |
2007 |
Jan
|
Feb
|
Mar
(1) |
Apr
|
May
|
Jun
(1) |
Jul
|
Aug
(1) |
Sep
|
Oct
|
Nov
|
Dec
|
2011 |
Jan
|
Feb
|
Mar
|
Apr
|
May
|
Jun
|
Jul
|
Aug
|
Sep
|
Oct
|
Nov
(1) |
Dec
|
From: Z <ze...@or...> - 2011-11-26 06:49:33
|
The following datalog program really deals with negated rules in a strange way. The bddbdd tells me that eveyone in the domain is "Single"... Probably I am wrong here? thank you. ************************* D 10 Married(a:D, b:D) outputtuples Single(a:D) outputtuples The output: ... Dumping tuples for Single Relation Single: 0 nodes, 16.0 elements ((none)) Single.tuples domains { D0 } = 0 nodes, 16.0 elements done. (12 ms) *********************** It should have been 14 elements instead of 16, shouldn' t it? Thank you. Zell |
From: <joe...@us...> - 2007-08-09 08:49:24
|
Revision: 654 http://bddbddb.svn.sourceforge.net/bddbddb/?rev=654&view=rev Author: joewhaley Date: 2007-08-09 01:49:27 -0700 (Thu, 09 Aug 2007) Log Message: ----------- Update homepage url. Modified Paths: -------------- trunk/bddbddb/xdocs/navigation.xml Modified: trunk/bddbddb/xdocs/navigation.xml =================================================================== --- trunk/bddbddb/xdocs/navigation.xml 2007-06-15 22:16:05 UTC (rev 653) +++ trunk/bddbddb/xdocs/navigation.xml 2007-08-09 08:49:27 UTC (rev 654) @@ -15,11 +15,11 @@ <item name="Links" href="links.html"/> <item name="NEW! PLDI'06 tutorial" - href="http://www.stanford.edu/~jwhaley/PLDITutorial.ppt"/> + href="http://suif.stanford.edu/~jwhaley/PLDITutorial.ppt"/> <item name="PLDI'04 paper" - href="http://www.stanford.edu/~jwhaley/papers/pldi04.pdf"/> + href="http://suif.stanford.edu/~jwhaley/papers/pldi04.pdf"/> <item name="PODS'05 paper" - href="http://www.stanford.edu/~jwhaley/papers/pods05.pdf"/> + href="http://suif.stanford.edu/~jwhaley/papers/pods05.pdf"/> <item name="Datalog examples" href="http://bddbddb.cvs.sourceforge.net/bddbddb/bddbddb_examples/"/> </menu> This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <joe...@us...> - 2007-06-15 22:16:09
|
Revision: 653 http://svn.sourceforge.net/bddbddb/?rev=653&view=rev Author: joewhaley Date: 2007-06-15 15:16:05 -0700 (Fri, 15 Jun 2007) Log Message: ----------- Added Google Analytics links. Modified Paths: -------------- trunk/bddbddb/xdocs/navigation.xml Modified: trunk/bddbddb/xdocs/navigation.xml =================================================================== --- trunk/bddbddb/xdocs/navigation.xml 2007-03-06 07:31:06 UTC (rev 652) +++ trunk/bddbddb/xdocs/navigation.xml 2007-06-15 22:16:05 UTC (rev 653) @@ -29,5 +29,13 @@ <item name="Download JAR file" href="http://bddbddb.sourceforge.net/bddbddb-full.jar"/> </menu> + <footer> +<script src="http://www.google-analytics.com/urchin.js" type="text/javascript"> +</script> +<script type="text/javascript"> +_uacct = "UA-72567-1"; +urchinTracker(); +</script> + </footer> </body> </project> This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <joe...@us...> - 2007-03-06 07:31:06
|
Revision: 652 http://svn.sourceforge.net/bddbddb/?rev=652&view=rev Author: joewhaley Date: 2007-03-05 23:31:06 -0800 (Mon, 05 Mar 2007) Log Message: ----------- Fixed usage of setCacheRatio Modified Paths: -------------- trunk/bddbddb/net/sf/bddbddb/BDDSolver.java Modified: trunk/bddbddb/net/sf/bddbddb/BDDSolver.java =================================================================== --- trunk/bddbddb/net/sf/bddbddb/BDDSolver.java 2006-12-06 06:02:16 UTC (rev 651) +++ trunk/bddbddb/net/sf/bddbddb/BDDSolver.java 2007-03-06 07:31:06 UTC (rev 652) @@ -299,7 +299,7 @@ } catch (OutOfMemoryError x) { out.println("Not enough memory, cannot grow node table size."); bdd.setCacheSize(bdd.getNodeTableSize()); - bdd.setCacheRatio(0.25); + bdd.setCacheRatio(4); } //bdd.setMaxIncrease(BDDNODES/2); bdd.setIncreaseFactor(2); This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <joe...@us...> - 2006-12-06 06:02:15
|
Revision: 651 http://svn.sourceforge.net/bddbddb/?rev=651&view=rev Author: joewhaley Date: 2006-12-05 22:02:16 -0800 (Tue, 05 Dec 2006) Log Message: ----------- Upgraded JavaBDD library to latest version. Modified Paths: -------------- trunk/bddbddb/Makefile trunk/bddbddb/javabdd-2.0.jar Modified: trunk/bddbddb/Makefile =================================================================== (Binary files differ) Modified: trunk/bddbddb/javabdd-2.0.jar =================================================================== (Binary files differ) This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <joe...@us...> - 2006-11-29 08:08:45
|
Revision: 650 http://svn.sourceforge.net/bddbddb/?rev=650&view=rev Author: joewhaley Date: 2006-11-29 00:08:45 -0800 (Wed, 29 Nov 2006) Log Message: ----------- Improved ZDD support. Modified Paths: -------------- trunk/bddbddb/net/sf/bddbddb/BDDInferenceRule.java trunk/bddbddb/net/sf/bddbddb/BDDRelation.java trunk/bddbddb/net/sf/bddbddb/ir/BDDOperationInterpreter.java Modified: trunk/bddbddb/net/sf/bddbddb/BDDInferenceRule.java =================================================================== --- trunk/bddbddb/net/sf/bddbddb/BDDInferenceRule.java 2006-09-16 05:51:04 UTC (rev 649) +++ trunk/bddbddb/net/sf/bddbddb/BDDInferenceRule.java 2006-11-29 08:08:45 UTC (rev 650) @@ -442,7 +442,7 @@ public BDD evalRelations(BDDFactory bdd, BDD[] relationValues, BDDVarSet[] canQuantifyAfter, long time) { long ttime = 0; - BDD result = bdd.one(); + BDD result = bdd.universe(); for (int j = 0; j < relationValues.length; ++j) { RuleTerm rt = (RuleTerm) top.get(j); BDDVarSet canNowQuantify = canQuantifyAfter[j]; @@ -488,7 +488,7 @@ if (TRACE) { solver.out.print("=" + topBdd.nodeCount()); solver.out.print(" (" + domainsOf(topBdd) + ")"); - solver.out.print(") (" + (System.currentTimeMillis() - ttime) + " ms)"); + solver.out.print(") (" + ttime + " ms)"); } result.free(); result = topBdd; @@ -834,7 +834,7 @@ } Assert._assert(!newRelationValues[i].isZero()); RuleTerm rt_new = (RuleTerm) top.get(i); - results[i] = bdd.one(); + results[i] = bdd.universe(); for (int j = 0; j < rallRelationValues.length; ++j) { RuleTerm rt = (RuleTerm) top.get(j); BDDVarSet canNowQuantify = canQuantifyAfter[j]; @@ -876,7 +876,7 @@ ftime = System.currentTimeMillis() - ftime; this.totalTime -= ftime; } - if (find_best_order && !results[i].isOne() && (System.currentTimeMillis() - ttime) >= FBO_CUTOFF) { + if (find_best_order && !results[i].isOne() && ttime >= FBO_CUTOFF) { long ftime = System.currentTimeMillis(); FindBestDomainOrder.findBestDomainOrder(solver,this, top.size() + i*j,solver.bdd, results[i], b, canNowQuantify, (RuleTerm) top.get(j-1), rt, Modified: trunk/bddbddb/net/sf/bddbddb/BDDRelation.java =================================================================== --- trunk/bddbddb/net/sf/bddbddb/BDDRelation.java 2006-09-16 05:51:04 UTC (rev 649) +++ trunk/bddbddb/net/sf/bddbddb/BDDRelation.java 2006-11-29 08:08:45 UTC (rev 650) @@ -155,7 +155,7 @@ } if (negated != null && !negated.isInitialized) { BDDRelation bddn = (BDDRelation) negated; - bddn.relation = solver.bdd.one(); + bddn.relation = solver.bdd.universe(); bddn.domains = this.domains; bddn.domainSet = this.domainSet.id(); bddn.isInitialized = true; @@ -229,7 +229,7 @@ * @return BDD that is true iff d1 < d2. */ private BDD buildLessThan(BDDDomain d1, BDDDomain d2) { - BDD leftwardBitsEqual = solver.bdd.one(); + BDD leftwardBitsEqual = solver.bdd.universe(); BDD result = solver.bdd.zero(); for (int i=d1.varNum()-1; i>=0; i--) { BDD v1 = d1.getFactory().ithVar(d1.vars()[i]); @@ -590,7 +590,7 @@ */ BDD parseTuple(String s) { StringTokenizer st = new StringTokenizer(s); - BDD b = solver.bdd.one(); + BDD b = solver.bdd.universe(); for (int i = 0; i < domains.size(); ++i) { BDDDomain d = (BDDDomain) domains.get(i); String v = st.nextToken(); @@ -718,7 +718,7 @@ if (relation.isZero()) { return; } - BDD allDomains = solver.bdd.one(); + BDD allDomains = solver.bdd.universe(); dos.write("#"); solver.out.print(fileName + " domains {"); int[] domIndices = new int[domains.size()]; @@ -966,7 +966,7 @@ * @see net.sf.bddbddb.Relation#add(java.math.BigInteger[]) */ public boolean add(BigInteger[] tuple) { - BDD val = solver.bdd.one(); + BDD val = solver.bdd.universe(); for (int i = 0; i < tuple.length; ++i) { final BDDDomain d = (BDDDomain) domains.get(i); Domain dd = getAttribute(i).getDomain(); Modified: trunk/bddbddb/net/sf/bddbddb/ir/BDDOperationInterpreter.java =================================================================== --- trunk/bddbddb/net/sf/bddbddb/ir/BDDOperationInterpreter.java 2006-09-16 05:51:04 UTC (rev 649) +++ trunk/bddbddb/net/sf/bddbddb/ir/BDDOperationInterpreter.java 2006-11-29 08:08:45 UTC (rev 650) @@ -422,7 +422,7 @@ */ public Object visit(Universe op) { BDDRelation r = (BDDRelation) op.getRelationDest(); - BDD b = factory.one(); + BDD b = factory.universe(); for (Iterator i = r.getAttributes().iterator(); i.hasNext();) { Attribute a = (Attribute) i.next(); BDDDomain d = r.getBDDDomain(a); This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <joe...@us...> - 2006-09-16 05:51:07
|
Revision: 649 http://svn.sourceforge.net/bddbddb/?rev=649&view=rev Author: joewhaley Date: 2006-09-15 22:51:04 -0700 (Fri, 15 Sep 2006) Log Message: ----------- Bug fixes from Ghassan Misherghi. Modified Paths: -------------- trunk/bddbddb/net/sf/bddbddb/BDDInferenceRule.java trunk/bddbddb/net/sf/bddbddb/DatalogParser.java trunk/bddbddb/net/sf/bddbddb/LSRelation.java Modified: trunk/bddbddb/net/sf/bddbddb/BDDInferenceRule.java =================================================================== --- trunk/bddbddb/net/sf/bddbddb/BDDInferenceRule.java 2006-07-20 06:50:33 UTC (rev 648) +++ trunk/bddbddb/net/sf/bddbddb/BDDInferenceRule.java 2006-09-16 05:51:04 UTC (rev 649) @@ -587,7 +587,7 @@ if (relationValues[i].isZero()) { if (TRACE) solver.out.println("Relation " + r + " is now empty! Stopping early."); for (int j = 0; j <= i; ++j) - relationValues[i].free(); + relationValues[j].free(); return false; } } Modified: trunk/bddbddb/net/sf/bddbddb/DatalogParser.java =================================================================== --- trunk/bddbddb/net/sf/bddbddb/DatalogParser.java 2006-07-20 06:50:33 UTC (rev 648) +++ trunk/bddbddb/net/sf/bddbddb/DatalogParser.java 2006-09-16 05:51:04 UTC (rev 649) @@ -936,7 +936,7 @@ } String varName = nextToken(st); Variable var = parseVariable(fd, nameToVar, varName); - if (vars.contains(var)) { + if (vars.contains(var) && !varName.equals("*")) { hasDuplicateVars = true; } vars.add(var); Modified: trunk/bddbddb/net/sf/bddbddb/LSRelation.java =================================================================== --- trunk/bddbddb/net/sf/bddbddb/LSRelation.java 2006-07-20 06:50:33 UTC (rev 648) +++ trunk/bddbddb/net/sf/bddbddb/LSRelation.java 2006-09-16 05:51:04 UTC (rev 649) @@ -179,12 +179,11 @@ } else { checkInfoLine(filename, s, true, true); } - for (;;) { - s = in.readLine(); - if (s == null) break; + while (s != null) { if (s.length() == 0) continue; if (s.startsWith("#")) continue; parseTuple(s); + s = in.readLine(); } } finally { if (in != null) in.close(); This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <joe...@us...> - 2006-07-20 06:50:34
|
Revision: 648 Author: joewhaley Date: 2006-07-19 23:50:33 -0700 (Wed, 19 Jul 2006) ViewCVS: http://svn.sourceforge.net/bddbddb/?rev=648&view=rev Log Message: ----------- Update path to JavaBDD library. Modified Paths: -------------- trunk/bddbddb/project.properties Modified: trunk/bddbddb/project.properties =================================================================== --- trunk/bddbddb/project.properties 2006-07-17 16:03:13 UTC (rev 647) +++ trunk/bddbddb/project.properties 2006-07-20 06:50:33 UTC (rev 648) @@ -7,7 +7,7 @@ # Tell maven where to find javabdd.jar, because it cannot build it itself. maven.jar.override = on -maven.jar.javabdd = ${basedir}/javabdd-1.0b2.jar +maven.jar.javabdd = ${basedir}/javabdd-2.0.jar maven.jar.weka = ${basedir}/weka.jar maven.jar.jwutil = ${basedir}/jwutil-1.0.jar This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <joe...@us...> - 2006-07-17 16:03:16
|
Revision: 647 Author: joewhaley Date: 2006-07-17 09:03:13 -0700 (Mon, 17 Jul 2006) ViewCVS: http://svn.sourceforge.net/bddbddb/?rev=647&view=rev Log Message: ----------- Update maven project files to JavaBDD 2.0. Modified Paths: -------------- trunk/bddbddb/project.xml Modified: trunk/bddbddb/project.xml =================================================================== --- trunk/bddbddb/project.xml 2006-07-17 05:26:09 UTC (rev 646) +++ trunk/bddbddb/project.xml 2006-07-17 16:03:13 UTC (rev 647) @@ -171,8 +171,8 @@ <dependency> <groupId>javabdd</groupId> <artifactId>javabdd</artifactId> - <version>1.0b2</version> - <jar>${basedir}/javabdd-1.0b2.jar</jar> + <version>2.0</version> + <jar>${basedir}/javabdd-2.0.jar</jar> <url>http://javabdd.sourceforge.net/</url> </dependency> <dependency> This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <joe...@us...> - 2006-07-17 05:26:12
|
Revision: 646 Author: joewhaley Date: 2006-07-16 22:26:09 -0700 (Sun, 16 Jul 2006) ViewCVS: http://svn.sourceforge.net/bddbddb/?rev=646&view=rev Log Message: ----------- Add bin directory to svn:ignore. Property Changed: ---------------- trunk/bddbddb_eclipse/ Property changes on: trunk/bddbddb_eclipse ___________________________________________________________________ Name: svn:ignore + bin This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <joe...@us...> - 2006-07-17 05:20:41
|
Revision: 645 Author: joewhaley Date: 2006-07-16 22:20:20 -0700 (Sun, 16 Jul 2006) ViewCVS: http://svn.sourceforge.net/bddbddb/?rev=645&view=rev Log Message: ----------- Upgraded to latest JavaBDD 2.0 and jwutil libraries. Modified Paths: -------------- trunk/bddbddb/.classpath trunk/bddbddb/jwutil-1.0.jar trunk/bddbddb/net/sf/bddbddb/BDDInferenceRule.java trunk/bddbddb/net/sf/bddbddb/BDDRelation.java trunk/bddbddb/net/sf/bddbddb/FindBestDomainOrder.java trunk/bddbddb/net/sf/bddbddb/TryDomainOrders.java trunk/bddbddb/net/sf/bddbddb/ir/BDDOperationInterpreter.java trunk/bddbddb/net/sf/bddbddb/ir/lowlevel/ApplyEx.java Added Paths: ----------- trunk/bddbddb/javabdd-2.0.jar Removed Paths: ------------- trunk/bddbddb/javabdd-1.0b2.jar Modified: trunk/bddbddb/.classpath =================================================================== --- trunk/bddbddb/.classpath 2006-07-17 05:20:15 UTC (rev 644) +++ trunk/bddbddb/.classpath 2006-07-17 05:20:20 UTC (rev 645) @@ -7,6 +7,6 @@ <classpathentry kind="src" path="/jwutil"/> <classpathentry kind="src" path="/JavaBDD"/> <classpathentry kind="lib" path="jwutil-1.0.jar"/> - <classpathentry kind="lib" path="javabdd-1.0b2.jar"/> + <classpathentry kind="lib" path="javabdd-2.0.jar"/> <classpathentry kind="output" path=""/> </classpath> Deleted: trunk/bddbddb/javabdd-1.0b2.jar =================================================================== (Binary files differ) Added: trunk/bddbddb/javabdd-2.0.jar =================================================================== (Binary files differ) Property changes on: trunk/bddbddb/javabdd-2.0.jar ___________________________________________________________________ Name: svn:mime-type + application/octet-stream Modified: trunk/bddbddb/jwutil-1.0.jar =================================================================== (Binary files differ) Modified: trunk/bddbddb/net/sf/bddbddb/BDDInferenceRule.java =================================================================== --- trunk/bddbddb/net/sf/bddbddb/BDDInferenceRule.java 2006-07-17 05:20:15 UTC (rev 644) +++ trunk/bddbddb/net/sf/bddbddb/BDDInferenceRule.java 2006-07-17 05:20:20 UTC (rev 645) @@ -19,6 +19,7 @@ import net.sf.javabdd.BDDDomain; import net.sf.javabdd.BDDFactory; import net.sf.javabdd.BDDPairing; +import net.sf.javabdd.BDDVarSet; /** * An implementation of InferenceRule that uses BDDs. @@ -55,7 +56,7 @@ /** * BDD variables that can be quantified away after each step. */ - BDD[] canQuantifyAfter; + BDDVarSet[] canQuantifyAfter; /** * Collection of variables that are still active after each step. @@ -211,12 +212,12 @@ void initializeQuantifySet() { if (canQuantifyAfter == null) { - canQuantifyAfter = new BDD[top.size()]; + canQuantifyAfter = new BDDVarSet[top.size()]; } for (int i = 0; i < top.size(); ++i) { RuleTerm rt = (RuleTerm) top.get(i); if (canQuantifyAfter[i] != null) canQuantifyAfter[i].free(); - canQuantifyAfter[i] = solver.bdd.one(); + canQuantifyAfter[i] = solver.bdd.emptySet(); outer : for (Iterator k = rt.variables.iterator(); k.hasNext();) { Variable v = (Variable) k.next(); if (bottom.variables.contains(v)) continue; @@ -225,7 +226,7 @@ if (rt2.variables.contains(v)) continue outer; } BDDDomain d2 = (BDDDomain) variableToBDDDomain.get(v); - canQuantifyAfter[i].andWith(d2.set()); + canQuantifyAfter[i].unionWith(d2.set()); } } } @@ -438,13 +439,13 @@ return changed; } - public BDD evalRelations(BDDFactory bdd, BDD[] relationValues, BDD[] canQuantifyAfter, long time) { + public BDD evalRelations(BDDFactory bdd, BDD[] relationValues, BDDVarSet[] canQuantifyAfter, long time) { long ttime = 0; BDD result = bdd.one(); for (int j = 0; j < relationValues.length; ++j) { RuleTerm rt = (RuleTerm) top.get(j); - BDD canNowQuantify = canQuantifyAfter[j]; + BDDVarSet canNowQuantify = canQuantifyAfter[j]; if (TRACE) solver.out.print(" x " + rt.relation); BDD b = relationValues[j]; if (TRACE) { @@ -467,7 +468,7 @@ w.close(); BDDRelation.save(solver, baseName+"_op1.bdd", result); BDDRelation.save(solver, baseName+"_op2.bdd", b); - BDDRelation.save(solver, baseName+"_op3.bdd", canNowQuantify); + BDDRelation.save(solver, baseName+"_op3.bdd", canNowQuantify.toBDD()); } catch (IOException x) { System.err.println("Error dumping BDD: "+x); } @@ -520,7 +521,7 @@ solver.out.print("Universe: for all " + d); ttime = System.currentTimeMillis(); } - BDD dset = d.set(); + BDDVarSet dset = d.set(); BDD q = relationValues[i].forAll(dset); dset.free(); if (TRACE) solver.out.println(" (" + (System.currentTimeMillis() - ttime) + " ms)"); @@ -572,7 +573,7 @@ solver.out.print(v + " is unnecessary, quantifying out " + d); ttime = System.currentTimeMillis(); } - BDD dset = d.set(); + BDDVarSet dset = d.set(); BDD q = relationValues[i].exist(dset); dset.free(); if (TRACE) { @@ -807,12 +808,12 @@ BDD limitToSingle(BDD result) { // Limit the result tuples to a single one. - BDD set = solver.bdd.one(); + BDDVarSet set = solver.bdd.emptySet(); for (Iterator k = bottom.variables.iterator(); k.hasNext(); ) { Variable v = (Variable) k.next(); if (unnecessaryVariables.contains(v)) continue; BDDDomain d2 = (BDDDomain) variableToBDDDomain.get(v); - set.andWith(d2.set()); + set.unionWith(d2.set()); } BDD singleResult = result.satOne(set, false); result.free(); @@ -823,7 +824,7 @@ return singleResult; } - public BDD[] evalRelationsIncremental(BDDFactory bdd, BDD[] newRelationValues, BDD[] rallRelationValues, BDD[] canQuantifyAfter){ + public BDD[] evalRelationsIncremental(BDDFactory bdd, BDD[] newRelationValues, BDD[] rallRelationValues, BDDVarSet[] canQuantifyAfter){ long ttime = 0; BDD[] results = new BDD[newRelationValues.length]; outer : for (int i = 0; i < newRelationValues.length; ++i) { @@ -836,7 +837,7 @@ results[i] = bdd.one(); for (int j = 0; j < rallRelationValues.length; ++j) { RuleTerm rt = (RuleTerm) top.get(j); - BDD canNowQuantify = canQuantifyAfter[j]; + BDDVarSet canNowQuantify = canQuantifyAfter[j]; if (TRACE) solver.out.print(" x " + rt.relation); BDD b; if (i != j) { @@ -847,7 +848,7 @@ } if (TRACE) { - solver.out.print(" (relprod " + b.nodeCount() + "x" + canNowQuantify.nodeCount()); + solver.out.print(" (relprod " + b.nodeCount()); } if (TRACE || find_best_order || DUMP_CUTOFF > 0) ttime = System.currentTimeMillis(); BDD topBdd = results[i].relprod(b, canNowQuantify); @@ -868,7 +869,7 @@ w.close(); BDDRelation.save(solver, baseName+"_op1.bdd", results[i]); BDDRelation.save(solver, baseName+"_op2.bdd", b); - BDDRelation.save(solver, baseName+"_op3.bdd", canNowQuantify); + BDDRelation.save(solver, baseName+"_op3.bdd", canNowQuantify.toBDD()); } catch (IOException x) { System.err.println("Error dumping BDD: "+x); } @@ -917,18 +918,23 @@ * @return string representation of the domains */ private String domainsOf(BDD b) { - BDD s = b.support(); - int[] a = s.scanSetDomains(); + BDDVarSet s = b.support(); + String result = domainsOf(s); s.free(); - if (a == null) return "(none)"; + return result; + } + + private String domainsOf(BDDVarSet s) { + BDDDomain[] a = s.getDomains(); + if (a.length == 0) return "(none)"; StringBuffer sb = new StringBuffer(); for (int i = 0; i < a.length; ++i) { - sb.append(solver.bdd.getDomain(a[i])); + sb.append(a[i]); if (i < a.length - 1) sb.append(','); } return sb.toString(); } - + /* * (non-Javadoc) * Modified: trunk/bddbddb/net/sf/bddbddb/BDDRelation.java =================================================================== --- trunk/bddbddb/net/sf/bddbddb/BDDRelation.java 2006-07-17 05:20:15 UTC (rev 644) +++ trunk/bddbddb/net/sf/bddbddb/BDDRelation.java 2006-07-17 05:20:20 UTC (rev 645) @@ -4,6 +4,7 @@ package net.sf.bddbddb; import java.util.ArrayList; +import java.util.Arrays; import java.util.Collection; import java.util.HashSet; import java.util.Iterator; @@ -21,6 +22,7 @@ import net.sf.javabdd.BDD; import net.sf.javabdd.BDDDomain; import net.sf.javabdd.BDDFactory; +import net.sf.javabdd.BDDVarSet; import net.sf.javabdd.BDD.BDDIterator; /** @@ -55,7 +57,7 @@ /** * Cache of the BDD set. */ - private BDD domainSet; + private BDDVarSet domainSet; static final byte EQ = 1; static final byte LT = 2; @@ -93,7 +95,7 @@ this.relation = solver.bdd.zero(); this.domains = new LinkedList(); if (solver.TRACE) solver.out.println("Initializing BDDRelation " + name + " with attributes " + attributes); - this.domainSet = solver.bdd.one(); + this.domainSet = solver.bdd.emptySet(); for (Iterator i = attributes.iterator(); i.hasNext();) { Attribute a = (Attribute) i.next(); Domain fd = a.attributeDomain; @@ -147,7 +149,7 @@ } if (solver.TRACE) solver.out.println("Attribute " + a + " (" + a.attributeDomain + ") assigned to BDDDomain " + d); domains.add(d); - domainSet.andWith(d.set()); + domainSet.unionWith(d.set()); } isInitialized = true; } @@ -165,19 +167,19 @@ * * @return the domain set */ - BDD calculateDomainSet() { + BDDVarSet calculateDomainSet() { if (domainSet != null) { domainSet.free(); } - this.domainSet = solver.bdd.one(); + this.domainSet = solver.bdd.emptySet(); for (Iterator i = domains.iterator(); i.hasNext();) { BDDDomain d = (BDDDomain) i.next(); - domainSet.andWith(d.set()); + domainSet.unionWith(d.set()); } return domainSet; } - public BDD getDomainSet() { + public BDDVarSet getDomainSet() { return domainSet; } @@ -298,9 +300,9 @@ */ public boolean verify(BDD r) { if (r == null) return true; /* trivially true? */ - BDD s = r.support(); + BDDVarSet s = r.support(); calculateDomainSet(); - BDD t = domainSet.and(s); + BDDVarSet t = domainSet.union(s); s.free(); //solver.out.println("Relation domains: " + domains + " BDD domains:" + activeDomains(r)); @@ -632,17 +634,13 @@ * @throws IOException */ public static void save(BDDSolver solver, String filename, BDD relation) throws IOException { - BDD s = relation.support(); - BigInteger[] a = s.scanAllVar(); - List domains = new ArrayList(a == null ? 0 : a.length); - BDD dom = solver.bdd.one(); - if (a != null) { - for (int i = 0; i < a.length; ++i) { - if (!BigInteger.ZERO.equals(a[i])) { - domains.add(solver.bdd.getDomain(i)); - dom.andWith(solver.bdd.getDomain(i).set()); - } - } + BDDVarSet s = relation.support(); + BDDDomain[] doms = s.getDomains(); + s.free(); + List domains = Arrays.asList(doms); + BDDVarSet dom = solver.bdd.emptySet(); + for (int i = 0; i < doms.length; ++i) { + dom.unionWith(doms[i].set()); } solver.out.println("Saving " + filename + ": " + relation.nodeCount() + " nodes, " + relation.satCount(dom) + " elements ("+domains+")"); @@ -776,13 +774,13 @@ */ public static String activeDomains(BDD r) { BDDFactory bdd = r.getFactory(); - BDD s = r.support(); - int[] a = s.scanSetDomains(); + BDDVarSet s = r.support(); + BDDDomain[] a = s.getDomains(); s.free(); - if (a == null) return "(none)"; + if (a.length == 0) return "(none)"; StringBuffer sb = new StringBuffer(); for (int i = 0; i < a.length; ++i) { - sb.append(bdd.getDomain(a[i])); + sb.append(a[i]); if (i < a.length - 1) sb.append(','); } return sb.toString(); @@ -842,7 +840,7 @@ */ public TupleIterator iterator(int k) { final BDDDomain d = (BDDDomain) domains.get(k); - BDD s = d.set(); + BDDVarSet s = d.set(); final BDDIterator i = relation.iterator(s); return new TupleIterator() { public BigInteger[] nextTuple() { Modified: trunk/bddbddb/net/sf/bddbddb/FindBestDomainOrder.java =================================================================== --- trunk/bddbddb/net/sf/bddbddb/FindBestDomainOrder.java 2006-07-17 05:20:15 UTC (rev 644) +++ trunk/bddbddb/net/sf/bddbddb/FindBestDomainOrder.java 2006-07-17 05:20:20 UTC (rev 645) @@ -63,6 +63,7 @@ import net.sf.bddbddb.order.WekaInterface.OrderInstance; import net.sf.javabdd.BDD; import net.sf.javabdd.BDDFactory; +import net.sf.javabdd.BDDVarSet; import net.sf.javabdd.FindBestOrder; import org.jdom.Document; import org.jdom.Element; @@ -2051,7 +2052,7 @@ * @param vars1 variables of b1 * @param vars2 variables of b2 */ - static void findBestDomainOrder(BDDSolver solver, BDDInferenceRule rule, int opNum, BDDFactory bdd, BDD b1, BDD b2, BDD b3, RuleTerm r1, RuleTerm r2, Collection vars1, Collection vars2) { + static void findBestDomainOrder(BDDSolver solver, BDDInferenceRule rule, int opNum, BDDFactory bdd, BDD b1, BDD b2, BDDVarSet b3, RuleTerm r1, RuleTerm r2, Collection vars1, Collection vars2) { Set allVarSet = new HashSet(vars1); allVarSet.addAll(vars2); allVarSet.removeAll(rule.unnecessaryVariables); Object[] a = allVarSet.toArray(); Modified: trunk/bddbddb/net/sf/bddbddb/TryDomainOrders.java =================================================================== --- trunk/bddbddb/net/sf/bddbddb/TryDomainOrders.java 2006-07-17 05:20:15 UTC (rev 644) +++ trunk/bddbddb/net/sf/bddbddb/TryDomainOrders.java 2006-07-17 05:20:20 UTC (rev 645) @@ -24,6 +24,7 @@ import net.sf.javabdd.BDD; import net.sf.javabdd.BDDDomain; import net.sf.javabdd.BDDFactory; +import net.sf.javabdd.BDDVarSet; import net.sf.javabdd.FindBestOrder; public class TryDomainOrders { @@ -179,7 +180,7 @@ solver.setVariableOrdering(); } - void doApplyEx(BDDFactory.BDDOp op, BDD b1, BDD b2, BDD b3) { + void doApplyEx(BDDFactory.BDDOp op, BDD b1, BDD b2, BDDVarSet b3) { long time = System.currentTimeMillis(); FindBestOrder fbo = new FindBestOrder(solver.BDDNODES, solver.BDDCACHE, 0, Long.MAX_VALUE, 5000); try { @@ -249,7 +250,7 @@ r1.load(rn1); r2.load(rn2); r3.load(rn3); - doApplyEx(BDDFactory.and, r1.getBDD(), r2.getBDD(), r3.getBDD()); + doApplyEx(BDDFactory.and, r1.getBDD(), r2.getBDD(), r3.getBDD().toVarSet()); return; } } else if (args[0].equals("and")) { Modified: trunk/bddbddb/net/sf/bddbddb/ir/BDDOperationInterpreter.java =================================================================== --- trunk/bddbddb/net/sf/bddbddb/ir/BDDOperationInterpreter.java 2006-07-17 05:20:15 UTC (rev 644) +++ trunk/bddbddb/net/sf/bddbddb/ir/BDDOperationInterpreter.java 2006-07-17 05:20:20 UTC (rev 645) @@ -38,6 +38,7 @@ import net.sf.javabdd.BDDDomain; import net.sf.javabdd.BDDFactory; import net.sf.javabdd.BDDPairing; +import net.sf.javabdd.BDDVarSet; import net.sf.javabdd.BDDFactory.BDDOp; /** @@ -116,24 +117,24 @@ return dd; } - BDD getProjectSet(Map m, BDDRelation r1, BDDRelation r2, BDDRelation r3) { - BDD b = factory.one(); + BDDVarSet getProjectSet(Map m, BDDRelation r1, BDDRelation r2, BDDRelation r3) { + BDDVarSet b = factory.emptySet(); for (Iterator i = r2.getAttributes().iterator(); i.hasNext();) { Attribute a = (Attribute) i.next(); if (r1.getAttributes().contains(a)) continue; BDDDomain d = (m != null)?(BDDDomain)m.get(a):r2.getBDDDomain(a); - b.andWith(d.set()); + b.unionWith(d.set()); } for (Iterator i = r3.getAttributes().iterator(); i.hasNext();) { Attribute a = (Attribute) i.next(); if (r1.getAttributes().contains(a)) continue; BDDDomain d = (m != null)?(BDDDomain)m.get(a):r3.getBDDDomain(a); - b.andWith(d.set()); + b.unionWith(d.set()); } return b; } - protected BDD makeDomainsMatch(BDD b2, BDD b3, BDDRelation r1, BDDRelation r2, BDDRelation r3) { + protected BDDVarSet makeDomainsMatch(BDD b2, BDD b3, BDDRelation r1, BDDRelation r2, BDDRelation r3) { if (CHECK) { r1.verify(); r2.verify(); @@ -227,11 +228,11 @@ BDDRelation r0 = (BDDRelation) op.getRelationDest(); BDDRelation r1 = (BDDRelation) op.getSrc(); List attributes = op.getAttributes(); - BDD b = factory.one(); + BDDVarSet b = factory.emptySet(); for (Iterator i = attributes.iterator(); i.hasNext();) { Attribute a = (Attribute) i.next(); BDDDomain d = r1.getBDDDomain(a); - b.andWith(d.set()); + b.unionWith(d.set()); if (TRACE) solver.out.println(" Projecting " + d); } if (TRACE) solver.out.println(" Exist " + r1); @@ -251,10 +252,10 @@ BDDRelation r0 = (BDDRelation) op.getRelationDest(); BDDRelation r1 = (BDDRelation) op.getSrc(); List domains = op.getDomains(); - BDD b = factory.one(); + BDDVarSet b = factory.emptySet(); for (Iterator i = domains.iterator(); i.hasNext();) { BDDDomain d = (BDDDomain) i.next(); - b.andWith(d.set()); + b.unionWith(d.set()); if (TRACE) solver.out.println(" Projecting " + d); } if (TRACE) solver.out.println(" Exist " + r1); @@ -520,7 +521,7 @@ BDD b1 = r1.getBDD().id(); BDD b2 = r2.getBDD().id(); - BDD b3 = needsDomainMatch ? makeDomainsMatch(b1, b2, r0, r1, r2) : op.getProjectSet(); + BDDVarSet b3 = needsDomainMatch ? makeDomainsMatch(b1, b2, r0, r1, r2) : op.getProjectSet(); //if (TRACE) solver.out.println(" " + op.toString()); BDD b = b1.applyEx(b2, bddop, b3); b1.free(); Modified: trunk/bddbddb/net/sf/bddbddb/ir/lowlevel/ApplyEx.java =================================================================== --- trunk/bddbddb/net/sf/bddbddb/ir/lowlevel/ApplyEx.java 2006-07-17 05:20:15 UTC (rev 644) +++ trunk/bddbddb/net/sf/bddbddb/ir/lowlevel/ApplyEx.java 2006-07-17 05:20:20 UTC (rev 645) @@ -6,16 +6,15 @@ import java.util.Iterator; import java.util.LinkedList; import java.util.List; - import jwutil.collections.Pair; import jwutil.util.Assert; import net.sf.bddbddb.Attribute; import net.sf.bddbddb.BDDRelation; import net.sf.bddbddb.Relation; import net.sf.bddbddb.ir.Operation; -import net.sf.javabdd.BDD; import net.sf.javabdd.BDDDomain; import net.sf.javabdd.BDDFactory; +import net.sf.javabdd.BDDVarSet; import net.sf.javabdd.BDDFactory.BDDOp; /** @@ -111,12 +110,12 @@ /** * @return the set to project */ - public BDD getProjectSet() { + public BDDVarSet getProjectSet() { Assert._assert(domainProjectSet != null); - BDD b = r1.getBDD().getFactory().one(); + BDDVarSet b = r1.getBDD().getFactory().emptySet(); for (Iterator i = domainProjectSet.iterator(); i.hasNext();) { BDDDomain d = (BDDDomain) i.next(); - if (d != null) b.andWith(d.set()); + if (d != null) b.unionWith(d.set()); } return b; } This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <joe...@us...> - 2006-07-17 05:20:18
|
Revision: 644 Author: joewhaley Date: 2006-07-16 22:20:15 -0700 (Sun, 16 Jul 2006) ViewCVS: http://svn.sourceforge.net/bddbddb/?rev=644&view=rev Log Message: ----------- Upgraded to latest JavaBDD 2.0 and jwutil libraries. Modified Paths: -------------- trunk/bddbddb_joeq/.classpath trunk/bddbddb_joeq/PAFly.java Modified: trunk/bddbddb_joeq/.classpath =================================================================== --- trunk/bddbddb_joeq/.classpath 2006-06-12 02:30:06 UTC (rev 643) +++ trunk/bddbddb_joeq/.classpath 2006-07-17 05:20:15 UTC (rev 644) @@ -2,6 +2,7 @@ <classpath> <classpathentry kind="src" path=""/> <classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER"/> + <classpathentry combineaccessrules="false" kind="src" path="/JavaBDD"/> <classpathentry kind="src" path="/bddbddb"/> <classpathentry kind="src" path="/joeq_core"/> <classpathentry kind="output" path=""/> Modified: trunk/bddbddb_joeq/PAFly.java =================================================================== --- trunk/bddbddb_joeq/PAFly.java 2006-06-12 02:30:06 UTC (rev 643) +++ trunk/bddbddb_joeq/PAFly.java 2006-07-17 05:20:15 UTC (rev 644) @@ -19,7 +19,6 @@ import java.io.FileWriter; import java.io.IOException; import java.io.PrintStream; -import java.lang.reflect.Array; import java.lang.reflect.Field; import java.math.BigInteger; import joeq.Class.PrimordialClassLoader; @@ -28,7 +27,6 @@ import joeq.Class.jq_FakeInstanceMethod; import joeq.Class.jq_Field; import joeq.Class.jq_Initializer; -import joeq.Class.jq_InstanceMethod; import joeq.Class.jq_Member; import joeq.Class.jq_Method; import joeq.Class.jq_NameAndDesc; @@ -67,7 +65,7 @@ import net.sf.javabdd.BDD; import net.sf.javabdd.BDDDomain; import net.sf.javabdd.BDDFactory; -import net.sf.javabdd.BDDPairing; +import net.sf.javabdd.BDDVarSet; import net.sf.javabdd.BDD.BDDIterator; /** @@ -458,7 +456,7 @@ Attribute a = r.getAttribute("heap"); BDDDomain H = r.getBDDDomain(a); - BDD Hset = H.set(); + BDDVarSet Hset = H.set(); BDD newValues; if (prevC == null) { newValues = r.getBDD().exist(Hset); @@ -468,7 +466,7 @@ } a = r.getAttribute("type"); BDDDomain T = r.getBDDDomain(a); - BDD Tset = T.set(); + BDDVarSet Tset = T.set(); List types = new LinkedList(); for (BDDIterator i = newValues.iterator(Tset); i.hasNext(); ) { BDD b = (BDD) i.next(); @@ -1354,7 +1352,7 @@ */ public Collection getAllMethods() { BDD b = roots.getBDD().id(); - BDD s = IE.getBDDDomain(0).set(); + BDDVarSet s = IE.getBDDDomain(0).set(); b.orWith(IE.getBDD().exist(s)); s.free(); BDD c = roots.getBDDDomain(0).ithVar(Mmap.get("null")); This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <joe...@us...> - 2006-06-12 02:30:10
|
Revision: 643 Author: joewhaley Date: 2006-06-11 19:30:06 -0700 (Sun, 11 Jun 2006) ViewCVS: http://svn.sourceforge.net/bddbddb/?rev=643&view=rev Log Message: ----------- Aded link to PLDI tutorial. Modified Paths: -------------- trunk/bddbddb/xdocs/navigation.xml Modified: trunk/bddbddb/xdocs/navigation.xml =================================================================== --- trunk/bddbddb/xdocs/navigation.xml 2006-06-08 02:35:35 UTC (rev 642) +++ trunk/bddbddb/xdocs/navigation.xml 2006-06-12 02:30:06 UTC (rev 643) @@ -14,6 +14,8 @@ href="index.html"/> <item name="Links" href="links.html"/> + <item name="NEW! PLDI'06 tutorial" + href="http://www.stanford.edu/~jwhaley/PLDITutorial.ppt"/> <item name="PLDI'04 paper" href="http://www.stanford.edu/~jwhaley/papers/pldi04.pdf"/> <item name="PODS'05 paper" This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <joe...@us...> - 2006-06-08 02:35:40
|
Revision: 642 Author: joewhaley Date: 2006-06-07 19:35:35 -0700 (Wed, 07 Jun 2006) ViewCVS: http://svn.sourceforge.net/bddbddb/?rev=642&view=rev Log Message: ----------- Simple modifications to reduce Eclipse warnings, mostly about unused variables. Modified Paths: -------------- trunk/bddbddb/net/sf/bddbddb/Interactive.java trunk/bddbddb/net/sf/bddbddb/Stratify.java Modified: trunk/bddbddb/net/sf/bddbddb/Interactive.java =================================================================== --- trunk/bddbddb/net/sf/bddbddb/Interactive.java 2006-06-07 00:00:59 UTC (rev 641) +++ trunk/bddbddb/net/sf/bddbddb/Interactive.java 2006-06-08 02:35:35 UTC (rev 642) @@ -188,7 +188,6 @@ log = new LinkedList(); LineNumberReader lin = new LineNumberReader(new InputStreamReader(in)); MyReader in = new MyReader(lin); - outer: for (;;) { try { out.print("> "); Modified: trunk/bddbddb/net/sf/bddbddb/Stratify.java =================================================================== --- trunk/bddbddb/net/sf/bddbddb/Stratify.java 2006-06-07 00:00:59 UTC (rev 641) +++ trunk/bddbddb/net/sf/bddbddb/Stratify.java 2006-06-08 02:35:35 UTC (rev 642) @@ -442,7 +442,6 @@ // Calculate each stratum. strata = new LinkedList(); Set visitedSccs = new HashSet(); - outer: while (!sortedSccs.isEmpty()) { List stratum = discoverStratum(sortedSccs, visitedSccs); Assert._assert(!stratum.isEmpty()); This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <joe...@us...> - 2006-06-07 00:01:03
|
Revision: 641 Author: joewhaley Date: 2006-06-06 17:00:59 -0700 (Tue, 06 Jun 2006) ViewCVS: http://svn.sourceforge.net/bddbddb/?rev=641&view=rev Log Message: ----------- Added svn:ignore properties. Property Changed: ---------------- trunk/bddbddb/net/sf/bddbddb/ trunk/bddbddb/net/sf/bddbddb/dataflow/ trunk/bddbddb/net/sf/bddbddb/ir/ trunk/bddbddb/net/sf/bddbddb/ir/dynamic/ trunk/bddbddb/net/sf/bddbddb/ir/highlevel/ trunk/bddbddb/net/sf/bddbddb/ir/lowlevel/ trunk/bddbddb/net/sf/bddbddb/order/ Property changes on: trunk/bddbddb/net/sf/bddbddb ___________________________________________________________________ Name: svn:ignore + *.class Property changes on: trunk/bddbddb/net/sf/bddbddb/dataflow ___________________________________________________________________ Name: svn:ignore + *.class Property changes on: trunk/bddbddb/net/sf/bddbddb/ir ___________________________________________________________________ Name: svn:ignore + *.class Property changes on: trunk/bddbddb/net/sf/bddbddb/ir/dynamic ___________________________________________________________________ Name: svn:ignore + *.class Property changes on: trunk/bddbddb/net/sf/bddbddb/ir/highlevel ___________________________________________________________________ Name: svn:ignore + *.class Property changes on: trunk/bddbddb/net/sf/bddbddb/ir/lowlevel ___________________________________________________________________ Name: svn:ignore + *.class Property changes on: trunk/bddbddb/net/sf/bddbddb/order ___________________________________________________________________ Name: svn:ignore + *.class This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: John W. <joe...@us...> - 2006-05-21 08:28:12
|
Update of /cvsroot/bddbddb/bddbddb/xdocs In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv20415/xdocs Modified Files: navigation.xml Log Message: Fixed broken link. Index: navigation.xml =================================================================== RCS file: /cvsroot/bddbddb/bddbddb/xdocs/navigation.xml,v retrieving revision 1.4 retrieving revision 1.5 diff -C2 -d -r1.4 -r1.5 *** navigation.xml 29 Apr 2005 05:44:06 -0000 1.4 --- navigation.xml 21 May 2006 08:28:04 -0000 1.5 *************** *** 20,24 **** href="http://www.stanford.edu/~jwhaley/papers/pods05.pdf"/> <item name="Datalog examples" ! href="http://cvs.sourceforge.net/viewcvs.py/bddbddb/bddbddb_examples/"/> </menu> <menu name="Download"> --- 20,24 ---- href="http://www.stanford.edu/~jwhaley/papers/pods05.pdf"/> <item name="Datalog examples" ! href="http://bddbddb.cvs.sourceforge.net/bddbddb/bddbddb_examples/"/> </menu> <menu name="Download"> |
From: John W. <joe...@us...> - 2006-05-21 08:00:51
|
Update of /cvsroot/bddbddb/bddbddb In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv8141 Modified Files: project.xml Log Message: Naughty sourceforge changed the CVS root. Index: project.xml =================================================================== RCS file: /cvsroot/bddbddb/bddbddb/project.xml,v retrieving revision 1.18 retrieving revision 1.19 diff -C2 -d -r1.18 -r1.19 *** project.xml 5 May 2005 21:58:40 -0000 1.18 --- project.xml 21 May 2006 08:00:46 -0000 1.19 *************** *** 82,88 **** <distributionDirectory>/home/groups/b/bd/bddbddb/</distributionDirectory> <repository> ! <connection>scm:cvs:pserver:ano...@cv...:/cvsroot/bddbddb:bddbddb</connection> ! <developerConnection>scm:cvs:ext:joe...@cv...:/cvsroot/bddbddb:bddbddb</developerConnection> ! <url>http://cvs.sourceforge.net/viewcvs.py/bddbddb/</url> </repository> <versions> --- 82,88 ---- <distributionDirectory>/home/groups/b/bd/bddbddb/</distributionDirectory> <repository> ! <connection>scm:cvs:pserver:ano...@bd...:/cvsroot/bddbddb:bddbddb</connection> ! <developerConnection>scm:cvs:ext:joe...@bd...:/cvsroot/bddbddb:bddbddb</developerConnection> ! <url>http://bddbddb.cvs.sourceforge.net/bddbddb/</url> </repository> <versions> |
From: Christopher U. <cu...@us...> - 2006-02-11 07:22:28
|
Update of /cvsroot/bddbddb/bddbddb_examples In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv3349 Added Files: pamap.datalog Log Message: initial revision. --- NEW FILE: pamap.datalog --- ### Java context-insensitive inclusion-based pointer analysis ### Handles hash map contents specially ### Author Chris Unkel ### Modified from pa.datalog ### Domains .include "fielddomains.pa" # stolen from pa.datalog; need fbo again? .bddvarorder N0_F0_I0_M1_M0_V1_V0_T0_Z0_T1_H0_H1_STR0 ### Relations vP0 (v:V0, h:H0) input vP (v:V0, h:H0) output A (dest:V0, source:V1) input hP0 (ha:H0, field:F0, hb:H1) input hP (ha:H0, field:F0, hb:H1) output S (base:V0, field:F0, src:V1) input L (base:V0, field:F0, dest:V1) input vT (var:V0, type:T0) input hT (heap:H0, type:T1) input aT (type:T0, type:T1) input vPfilter (v:V0, h:H0) actual (invoke:I0, num:Z0, actualparam:V1) input formal (method:M0, num:Z0, formalparam:V0) input Mret (method:M0, v:V1) input Mthr (method:M0, v:V1) input Iret (invoke:I0, v:V0) input Ithr (invoke:I0, v:V0) input IE0 (invoke:I0, target:M0) input IE (invoke:I0, target:M0) output ## Additional relations for special map handling stringConstant(heap:H0, string:STR0) input overridesEqualsOrHashcode(type:T0) input # Methods handled specially. Should not be hooked up via Mret as normal. handledSpecially(method:M0) # java.lang.String. stringClass(type:T0) # h0.equals(h1) might be true. mayEqual(h0:H0, h1:H1) mapContents (map:H0, key:H0, value:H0) output ### Rules vP(v,h) :- vP0(v,h). hP(h,f,h2) :- hP0(h,f,h2). IE(i,m) :- IE0(i,m). vPfilter(v,h) :- vT(v,tv), aT(tv,th), hT(h,th). vP(v1,h) :- A(v1,v2), vP(v2,h), vPfilter(v1,h). hP(h1,f,h2) :- S(v1,f,v2), vP(v1,h1), vP(v2,h2). vP(v2,h2) :- L(v1,f,v2), vP(v1,h1), hP(h1,f,h2), vPfilter(v2,h2). split A(v1,v2) :- formal(m,z,v1), IE(i,m), actual(i,z,v2). # This rule is modified from base algorithm: A(v2,v1) :- !handledSpecially(m), Mret(m,v1), IE(i,m), Iret(i,v2). A(v2,v1) :- Mthr(m,v1), IE(i,m), Ithr(i,v2). ## Additional rules for special map handling # Eclipse mangling here, ick. handledSpecially("java/util/HashMap/java/lang/Object/get(java/lang/Object)"). stringClass("java.lang.String"). mayEqual(h1, h2) :- h1=h2. mayEqual(h1, h2) :- hT(h1, t1), overridesEqualsOrHashcode(t1), !stringClass(t1), \ hT(h2, t2), overridesEqualsOrHashcode(t2), !stringClass(t2). mayEqual(h1, h2) :- stringConstant(h1, str), stringConstant(h2, str). # 0 is the special "non-constant" string constant. mayEqual(h1, h2) :- stringConstant(h1, 0), stringConstant(h2, _). mayEqual(h2, h1) :- stringConstant(h1, 0), stringConstant(h2, _). # java.util.HashMap.put handling mapContents(map, key, value) :- IE(i, "java/util/HashMap/java/lang/Object/put(java/lang/Objectjava/lang/Object)"), \ actual(i, 0, v0), vP(v0, map), \ actual(i, 1, v1), vP(v1, key), \ actual(i, 2, v2), vP(v2, value). # java.util.HashMap.get handling vP(v,value) :- IE(i, "java/util/HashMap/java/lang/Object/get(java/lang/Object)"), \ actual(i, 0, v0), vP(v0, map), \ actual(i, 0, v1), vP(v1, key), \ mayEqual(key, containedKey), \ mapContents(map, containedKey, value), \ Iret(i, v). |
From: John W. <joe...@us...> - 2006-01-22 04:03:40
|
Update of /cvsroot/bddbddb/bddbddb/net/sf/bddbddb In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv26384/net/sf/bddbddb Modified Files: TryDomainOrders.java Log Message: Support for specifying BDDs with _op?.bdd suffix. Index: TryDomainOrders.java =================================================================== RCS file: /cvsroot/bddbddb/bddbddb/net/sf/bddbddb/TryDomainOrders.java,v retrieving revision 1.4 retrieving revision 1.5 diff -C2 -d -r1.4 -r1.5 *** TryDomainOrders.java 13 Oct 2005 06:01:27 -0000 1.4 --- TryDomainOrders.java 22 Jan 2006 04:03:31 -0000 1.5 *************** *** 233,245 **** if (args.length > 1) { if (args[0].equals("relprod")) { ! if (args.length == 4) { ! BDDRelation r1 = parseRelation(args[1]); ! BDDRelation r2 = parseRelation(args[2]); ! BDDRelation r3 = parseRelation(args[3]); setVarOrder(loaded_varorder); solver.initialize(); ! r1.load(args[1]); ! r2.load(args[2]); ! r3.load(args[3]); doApplyEx(BDDFactory.and, r1.getBDD(), r2.getBDD(), r3.getBDD()); return; --- 233,253 ---- if (args.length > 1) { if (args[0].equals("relprod")) { ! if (args.length == 4 || args.length == 2) { ! String rn1, rn2, rn3; ! if (args.length == 4) { ! rn1 = args[1]; rn2 = args[2]; rn3 = args[3]; ! } else { ! rn1 = args[1]+"_op1.bdd"; ! rn2 = args[1]+"_op2.bdd"; ! rn3 = args[1]+"_op3.bdd"; ! } ! BDDRelation r1 = parseRelation(rn1); ! BDDRelation r2 = parseRelation(rn2); ! BDDRelation r3 = parseRelation(rn3); setVarOrder(loaded_varorder); solver.initialize(); ! r1.load(rn1); ! r2.load(rn2); ! r3.load(rn3); doApplyEx(BDDFactory.and, r1.getBDD(), r2.getBDD(), r3.getBDD()); return; |
From: John W. <joe...@us...> - 2006-01-22 04:03:39
|
Update of /cvsroot/bddbddb/bddbddb In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv26384 Modified Files: javabdd-1.0b2.jar Log Message: Support for specifying BDDs with _op?.bdd suffix. Index: javabdd-1.0b2.jar =================================================================== RCS file: /cvsroot/bddbddb/bddbddb/javabdd-1.0b2.jar,v retrieving revision 1.5 retrieving revision 1.6 diff -C2 -d -r1.5 -r1.6 Binary files /tmp/cvsKQjNVh and /tmp/cvslE67L0 differ |
From: John W. <joe...@us...> - 2005-10-13 06:01:37
|
Update of /cvsroot/bddbddb/bddbddb/net/sf/bddbddb In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv24803/net/sf/bddbddb Modified Files: TryDomainOrders.java Log Message: Try initial variable ordering first. Index: TryDomainOrders.java =================================================================== RCS file: /cvsroot/bddbddb/bddbddb/net/sf/bddbddb/TryDomainOrders.java,v retrieving revision 1.3 retrieving revision 1.4 diff -C2 -d -r1.3 -r1.4 *** TryDomainOrders.java 12 Oct 2005 10:41:36 -0000 1.3 --- TryDomainOrders.java 13 Oct 2005 06:01:27 -0000 1.4 *************** *** 192,197 **** solver.out.println("Time to initialize FindBestOrder: "+(System.currentTimeMillis()-time)); - OrderIterator i = new OrderIterator(domList); Map orderTimes = new HashMap(); while (i.hasNext()) { Order o = i.nextOrder(); --- 192,209 ---- solver.out.println("Time to initialize FindBestOrder: "+(System.currentTimeMillis()-time)); Map orderTimes = new HashMap(); + if (true) { + Order o = loaded_varorder.generateRandomOrder(domList); + String vOrder = o.toVarOrderString(null); + solver.out.println("Trying initial order "+vOrder); + vOrder = solver.fixVarOrder(vOrder, false); + solver.out.println("Complete order "+vOrder); + time = fbo.tryOrder(true, vOrder); + time = Math.min(time, BDDInferenceRule.LONG_TIME); + solver.out.println("Order "+o+" time: "+time+" ms"); + orderTimes.put(o, new Long(time)); + } + + OrderIterator i = new OrderIterator(domList); while (i.hasNext()) { Order o = i.nextOrder(); *************** *** 213,216 **** --- 225,229 ---- Order o = (Order) e.getKey(); Long t = (Long) e.getValue(); + if (t.longValue() >= BDDInferenceRule.LONG_TIME) break; solver.out.println("Order: "+o+" "+t+" ms"); } |
From: John W. <joe...@us...> - 2005-10-12 10:41:44
|
Update of /cvsroot/bddbddb/bddbddb/net/sf/bddbddb In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv3205/net/sf/bddbddb Modified Files: TryDomainOrders.java Log Message: Get rid of maxincrease. Index: TryDomainOrders.java =================================================================== RCS file: /cvsroot/bddbddb/bddbddb/net/sf/bddbddb/TryDomainOrders.java,v retrieving revision 1.2 retrieving revision 1.3 diff -C2 -d -r1.2 -r1.3 *** TryDomainOrders.java 12 Oct 2005 10:29:55 -0000 1.2 --- TryDomainOrders.java 12 Oct 2005 10:41:36 -0000 1.3 *************** *** 182,186 **** void doApplyEx(BDDFactory.BDDOp op, BDD b1, BDD b2, BDD b3) { long time = System.currentTimeMillis(); ! FindBestOrder fbo = new FindBestOrder(solver.BDDNODES, solver.BDDCACHE, solver.BDDNODES / 2, Long.MAX_VALUE, 5000); try { fbo.init(b1, b2, b3, op); --- 182,186 ---- void doApplyEx(BDDFactory.BDDOp op, BDD b1, BDD b2, BDD b3) { long time = System.currentTimeMillis(); ! FindBestOrder fbo = new FindBestOrder(solver.BDDNODES, solver.BDDCACHE, 0, Long.MAX_VALUE, 5000); try { fbo.init(b1, b2, b3, op); |
From: John W. <joe...@us...> - 2005-10-12 10:30:03
|
Update of /cvsroot/bddbddb/bddbddb/net/sf/bddbddb In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv1094/net/sf/bddbddb Modified Files: TryDomainOrders.java Log Message: Make it compile under older JDKs. Index: TryDomainOrders.java =================================================================== RCS file: /cvsroot/bddbddb/bddbddb/net/sf/bddbddb/TryDomainOrders.java,v retrieving revision 1.1 retrieving revision 1.2 diff -C2 -d -r1.1 -r1.2 *** TryDomainOrders.java 12 Oct 2005 10:25:21 -0000 1.1 --- TryDomainOrders.java 12 Oct 2005 10:29:55 -0000 1.2 *************** *** 203,207 **** time = Math.min(time, BDDInferenceRule.LONG_TIME); solver.out.println("Order "+o+" time: "+time+" ms"); ! orderTimes.put(o, Long.valueOf(time)); } fbo.cleanup(); --- 203,207 ---- time = Math.min(time, BDDInferenceRule.LONG_TIME); solver.out.println("Order "+o+" time: "+time+" ms"); ! orderTimes.put(o, new Long(time)); } fbo.cleanup(); |
From: John W. <joe...@us...> - 2005-10-12 10:28:59
|
Update of /cvsroot/bddbddb/bddbddb In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv832 Modified Files: jwutil-1.0.jar Log Message: Newer version. Index: jwutil-1.0.jar =================================================================== RCS file: /cvsroot/bddbddb/bddbddb/jwutil-1.0.jar,v retrieving revision 1.8 retrieving revision 1.9 diff -C2 -d -r1.8 -r1.9 Binary files /tmp/cvs2aLnQh and /tmp/cvs4t5oLv differ |
From: John W. <joe...@us...> - 2005-10-12 10:25:33
|
Update of /cvsroot/bddbddb/bddbddb/net/sf/bddbddb In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv32510/net/sf/bddbddb Added Files: TryDomainOrders.java Log Message: New simple test to try all domain orders for an operation. --- NEW FILE: TryDomainOrders.java --- // TryDomainOrders.java, created Oct 11, 2005 11:33:56 PM by joewhaley // Copyright (C) 2005 John Whaley <jw...@al...> // Licensed under the terms of the GNU LGPL; see COPYING for details. package net.sf.bddbddb; import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.Iterator; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.StringTokenizer; import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; import java.math.BigInteger; import jwutil.collections.EntryValueComparator; import jwutil.io.SystemProperties; import net.sf.bddbddb.order.Order; import net.sf.bddbddb.order.OrderConstraint; import net.sf.bddbddb.order.OrderConstraintSet; import net.sf.bddbddb.order.OrderIterator; import net.sf.javabdd.BDD; import net.sf.javabdd.BDDDomain; import net.sf.javabdd.BDDFactory; import net.sf.javabdd.FindBestOrder; public class TryDomainOrders { BDDSolver solver; List domList; String varorder; OrderConstraintSet loaded_varorder; public TryDomainOrders() { solver = new BDDSolver(); domList = new ArrayList(); varorder = solver.VARORDER; loaded_varorder = new OrderConstraintSet(); } BDDRelation parseRelation(String name, BufferedReader in) throws IOException { String s = in.readLine(); if (!s.startsWith("# ")) { // TODO: No header line! throw new IOException("no header line"); } StringTokenizer st = new StringTokenizer(s.substring(2)); List attribs = new LinkedList(); List bdddoms = new LinkedList(); while (st.hasMoreTokens()) { String msg = null; String dname = st.nextToken(": "); int dbits = Integer.parseInt(st.nextToken()); String fdname = dname; while (fdname.length() > 0 && Character.isDigit(fdname.charAt(fdname.length()-1))) { fdname = fdname.substring(0, fdname.length()-1); } Domain fd = solver.getDomain(fdname); if (fd == null) { fd = new Domain(fdname, BigInteger.ONE.shiftLeft(dbits).subtract(BigInteger.ONE)); solver.nameToDomain.put(fdname, fd); } else { if (dbits != fd.getSize().bitLength()) throw new IOException("different number of bits for "+fd+" ("+dbits+" vs "+ fd.getSize().bitLength()+")"); } BDDDomain d = solver.getBDDDomain(dname); while (d == null) { BDDDomain dom = solver.allocateBDDDomain(fd); if (dom.getName().equals(dname)) { d = dom; domList.add(dom); break; } } bdddoms.add(d); Attribute a = new Attribute(dname, fd, dname); attribs.add(a); } Relation r = solver.createRelation(name, attribs); solver.out.println("Relation "+r+": "+attribs); // Load domain lines to figure out variable order. int[][] domvars = new int[bdddoms.size()][]; int k = 0; for (Iterator i = bdddoms.iterator(); i.hasNext(); ++k) { BDDDomain d = (BDDDomain) i.next(); s = in.readLine(); if (!s.startsWith("# ")) throw new IOException("missing variable line for domain "+d); s = s.substring(2); domvars[k] = new int[d.varNum()]; st = new StringTokenizer(s); for (int j = 0; j < domvars[k].length; ++j) { if (!st.hasMoreTokens()) throw new IOException("not enough variables for domain "+d); domvars[k][j] = Integer.parseInt(st.nextToken()); } if (st.hasMoreTokens()) throw new IOException("too many variables for domain "+d); } // node num and var num s = in.readLine(); st = new StringTokenizer(s); int nNodes = Integer.parseInt(st.nextToken()); int nVars = Integer.parseInt(st.nextToken()); // variable order line s = in.readLine(); st = new StringTokenizer(s); int[] varorder = new int[nVars]; for (k = 0; k < varorder.length; ++k) { if (!st.hasMoreTokens()) throw new IOException("varorder line too short"); varorder[k] = Integer.parseInt(st.nextToken()); } if (st.hasMoreTokens()) throw new IOException("varorder line too long"); for (int a = 0; a < domvars.length; ++a) { BDDDomain adom = (BDDDomain)bdddoms.get(a); int[] a_vars = domvars[a]; int a1 = varorder[a_vars[0]]; int a2 = varorder[a_vars[a_vars.length-1]]; int a_start = Math.min(a1, a2); int a_end = Math.max(a1, a2); for (int b = a+1; b < domvars.length; ++b) { BDDDomain bdom = (BDDDomain)bdddoms.get(b); int[] b_vars = domvars[b]; int b1 = varorder[b_vars[0]]; int b2 = varorder[b_vars[b_vars.length-1]]; int b_start = Math.min(b1, b2); int b_end = Math.max(b1, b2); OrderConstraint c; if (a_start > b_end) { c = OrderConstraint.makePrecedenceConstraint(bdom, adom); } else if (b_start > a_end) { c = OrderConstraint.makePrecedenceConstraint(adom, bdom); } else { c = OrderConstraint.makeInterleaveConstraint(adom, bdom); } solver.out.println("Order constraint: "+c); boolean ok = loaded_varorder.constrain(c); if (!ok) solver.out.println("Note: order conflicts! cannot add constraint "+c); } } return (BDDRelation) r; } BDDRelation parseRelation(String filename) throws IOException { // Peek at header line to figure out relation attributes. int x = Math.max(filename.lastIndexOf('/'), filename.lastIndexOf(SystemProperties.getProperty("file.separator"))); int y = filename.lastIndexOf('.'); if (x >= y) throw new IOException("bad filename: "+filename); String relationName = filename.substring(x+1, y); String suffixName = filename.substring(y+1); BufferedReader in = null; try { in = new BufferedReader(new FileReader(filename)); // Parse BDD information. return parseRelation(relationName, in); } finally { if (in != null) try { in.close(); } catch (IOException _) { } } } void setVarOrder(OrderConstraintSet ocs) { if (varorder == null) { Order o = ocs.generateRandomOrder(domList); solver.VARORDER = o.toVarOrderString(null); } else { solver.VARORDER = varorder; } solver.setVariableOrdering(); } void doApplyEx(BDDFactory.BDDOp op, BDD b1, BDD b2, BDD b3) { long time = System.currentTimeMillis(); FindBestOrder fbo = new FindBestOrder(solver.BDDNODES, solver.BDDCACHE, solver.BDDNODES / 2, Long.MAX_VALUE, 5000); try { fbo.init(b1, b2, b3, op); } catch (IOException x) { solver.err.println("IO Exception occurred: " + x); fbo.cleanup(); return; } solver.out.println("Time to initialize FindBestOrder: "+(System.currentTimeMillis()-time)); OrderIterator i = new OrderIterator(domList); Map orderTimes = new HashMap(); while (i.hasNext()) { Order o = i.nextOrder(); String vOrder = o.toVarOrderString(null); solver.out.println("Trying order "+vOrder); vOrder = solver.fixVarOrder(vOrder, false); solver.out.println("Complete order "+vOrder); time = fbo.tryOrder(true, vOrder); time = Math.min(time, BDDInferenceRule.LONG_TIME); solver.out.println("Order "+o+" time: "+time+" ms"); orderTimes.put(o, Long.valueOf(time)); } fbo.cleanup(); List sortedEntries = new ArrayList(orderTimes.entrySet()); Collections.sort(sortedEntries, EntryValueComparator.INSTANCE); for (Iterator it = sortedEntries.iterator(); it.hasNext(); ) { Map.Entry e = (Map.Entry) it.next(); Order o = (Order) e.getKey(); Long t = (Long) e.getValue(); solver.out.println("Order: "+o+" "+t+" ms"); } } void handleCommand(String[] args) throws IOException { if (args.length > 1) { if (args[0].equals("relprod")) { if (args.length == 4) { BDDRelation r1 = parseRelation(args[1]); BDDRelation r2 = parseRelation(args[2]); BDDRelation r3 = parseRelation(args[3]); setVarOrder(loaded_varorder); solver.initialize(); r1.load(args[1]); r2.load(args[2]); r3.load(args[3]); doApplyEx(BDDFactory.and, r1.getBDD(), r2.getBDD(), r3.getBDD()); return; } } else if (args[0].equals("and")) { } else if (args[0].equals("or")) { } } solver.out.println("Usage: java "+TryDomainOrders.class.getName()+" relprod bdd1 bdd2 bdd3"); solver.out.println(" java "+TryDomainOrders.class.getName()+" and bdd1 bdd2"); solver.out.println(" java "+TryDomainOrders.class.getName()+" or bdd1 bdd2"); } /** * @param args */ public static void main(String[] args) throws IOException { TryDomainOrders dis = new TryDomainOrders(); dis.handleCommand(args); } } |