00001
00002
00003 #include "osl/checkmate/analyzer/checkTableAnalyzer.h"
00004 #include "osl/checkmate/analyzer/treeWriter.h"
00005 #include "osl/checkmate/analyzer/proofTreeTraverser.h"
00006 #include "osl/checkmate/analyzer/disproofTreeTraverser.h"
00007 #include "osl/checkmate/analyzer/recordSet.h"
00008 #include "osl/checkmate/analyzer/showAllTree.h"
00009 #include "osl/checkmate/checkHashRecord.h"
00010 #include "osl/checkmate/checkMoveList.h"
00011 #include "osl/checkmate/proofDisproof.h"
00012 #include "osl/checkmate/corruptCheckTable.h"
00013 #include <boost/scoped_ptr.hpp>
00014 #include <iostream>
00015 #include <fstream>
00016
00017 namespace osl
00018 {
00019 namespace checkmate
00020 {
00021 using namespace analyzer;
00022 static void traverse(const CheckHashRecord *record, RecordSet& out)
00023 {
00024 if (! record)
00025 return;
00026 if (! out.insert(record).second)
00027 return;
00028
00029 for (CheckMoveList::const_iterator p=record->moves.begin();
00030 p!=record->moves.end(); ++p)
00031 {
00032 traverse(p->record, out);
00033 }
00034 }
00035
00036
00037 static void examineProofTree(const CheckHashRecord *record,
00038 const TwinTable& table,
00039 const HashKey& key,
00040 const PathEncoding& path,
00041 bool orNode, TreeWriter& writer,
00042 size_t& tree_size, size_t& leaf_size)
00043 {
00044 tree_size = 1;
00045 leaf_size = 1;
00046 assert(record);
00047 assert(record->proofDisproof().isCheckmateSuccess());
00048 ProofTreeTraverser traverser(writer, table);
00049 if (orNode)
00050 traverser.traverseOrNode(Move::INVALID(), record, key, path);
00051 else
00052 traverser.traverseAndNode(Move::INVALID(), record, key, path);
00053 tree_size = traverser.getVisited().size();
00054 leaf_size = traverser.getLeaves();
00055 }
00056
00057 static void examineDisproofTree(const CheckHashRecord *record,
00058 const TwinTable& table,
00059 const HashKey& key,
00060 const PathEncoding& path,
00061 bool orNode, bool isPartialStack,
00062 TreeWriter& writer,
00063 size_t& tree_size, size_t& leaf_size)
00064 {
00065 tree_size = 1;
00066 leaf_size = 1;
00067 assert(record);
00068 if (! record->proofDisproof().isCheckmateFail())
00069 {
00070 if (! record->findLoop(path, table))
00071 {
00072 assert(isPartialStack);
00073 assert(! record->twins.empty());
00074 return;
00075 }
00076 }
00077 DisproofTreeTraverser traverser(writer, table, isPartialStack);
00078 if (orNode)
00079 traverser.traverseOrNode(Move::INVALID(), record, key, path);
00080 else
00081 traverser.traverseAndNode(Move::INVALID(), record, key, path);
00082 tree_size = traverser.getVisited().size();
00083 leaf_size = traverser.getLeaves();
00084 }
00085
00086 static void examineTreeGuess(const CheckHashRecord *record,
00087 const TwinTable& table,
00088 const HashKey& key,
00089 const PathEncoding& path,
00090 bool orNode, bool isPartialStack,
00091 TreeWriter& writer,
00092 size_t& tree_size, size_t& leaf_size)
00093 {
00094 if (! record)
00095 {
00096 tree_size = 0;
00097 leaf_size = 0;
00098 return;
00099 }
00100 if ((! record->proofDisproof().isFinal())
00101 && (! record->findLoop(path, table)))
00102 {
00103 tree_size = 1;
00104 leaf_size = 1;
00105 return;
00106 }
00107 if (record->proofDisproof().isCheckmateFail()
00108 || record->findLoop(path, table))
00109 {
00110 examineDisproofTree(record, table, key, path, orNode, isPartialStack,
00111 writer, tree_size, leaf_size);
00112 }
00113 else
00114 {
00115 examineProofTree(record, table, key, path, orNode,
00116 writer, tree_size, leaf_size);
00117 }
00118 }
00119 }
00120 }
00121
00122 osl::checkmate::analyzer::
00123 CheckTableAnalyzer::CheckTableAnalyzer(const TwinTable& t, bool outline)
00124 : table(t), useOutlineFormat(outline)
00125 {
00126 }
00127
00128 osl::checkmate::analyzer::
00129 CheckTableAnalyzer::~CheckTableAnalyzer()
00130 {
00131 }
00132
00133 void osl::checkmate::analyzer::CheckTableAnalyzer::
00134 showTree(const CheckHashRecord *record, std::ostream& os,
00135 int maxDepth, bool expandFinalState, bool showTerminalMoves,
00136 size_t threshold) const
00137 {
00138 if (! record)
00139 return;
00140 ShowAllTree traverser(os, maxDepth, expandFinalState, showTerminalMoves);
00141 if (useOutlineFormat)
00142 traverser.showOutline(record);
00143 else
00144 traverser.showDot(record, threshold);
00145 }
00146
00147 size_t osl::checkmate::analyzer::
00148 CheckTableAnalyzer::treeSize(const CheckHashRecord *record) const
00149 {
00150 RecordSet nodes;
00151 traverse(record, nodes);
00152 return nodes.size();
00153 }
00154
00155 size_t osl::checkmate::analyzer::CheckTableAnalyzer::
00156 proofTreeSize(const CheckHashRecord *record, const HashKey& key,
00157 const PathEncoding& path, bool orNode) const
00158 {
00159 size_t leaf_size;
00160 return proofTreeSize(record, key, path, orNode, leaf_size);
00161 }
00162 size_t osl::checkmate::analyzer::CheckTableAnalyzer::
00163 proofTreeSize(const CheckHashRecord *record,
00164 const HashKey& key, const PathEncoding& path,
00165 bool orNode, size_t& leaf_size) const
00166 {
00167 try
00168 {
00169 TreeWriter writer;
00170 size_t tree_size;
00171 examineProofTree(record, table, key, path, orNode,
00172 writer, tree_size, leaf_size);
00173 return tree_size;
00174 }
00175 catch (CorruptCheckTable& t)
00176 {
00177 std::cerr << t.what() << ", corrupt tree was " << t.record << "\n";
00178 t.record->dump();
00179 throw;
00180 }
00181 }
00182
00183 size_t osl::checkmate::analyzer::CheckTableAnalyzer::
00184 disproofTreeSize(const CheckHashRecord *record,
00185 const HashKey& key, const PathEncoding& path,
00186 bool orNode, bool isPartialStack) const
00187 {
00188 size_t leaf_size;
00189 return disproofTreeSize(record, key, path, orNode, leaf_size,
00190 isPartialStack);
00191 }
00192
00193 size_t osl::checkmate::analyzer::CheckTableAnalyzer::
00194 disproofTreeSize(const CheckHashRecord *record,
00195 const HashKey& key, const PathEncoding& path,
00196 bool orNode, size_t& leaf_size, bool isPartialStack) const
00197 {
00198 try
00199 {
00200 TreeWriter writer;
00201 size_t tree_size;
00202 examineDisproofTree(record, table, key, path, orNode, isPartialStack,
00203 writer, tree_size, leaf_size);
00204 return tree_size;
00205 }
00206 catch (CorruptCheckTable& t)
00207 {
00208 std::cerr << t.what() << ", corrupt tree was " << t.record << "\n";
00209 t.record->dump();
00210 throw;
00211 }
00212 }
00213
00214 size_t osl::checkmate::analyzer::CheckTableAnalyzer::
00215 proofOrDisproofTreeSize(const CheckHashRecord *record,
00216 const HashKey& key,
00217 const PathEncoding& path,
00218 bool orNode, bool isPartialStack) const
00219 {
00220 size_t leaf_size;
00221 return proofOrDisproofTreeSize(record, key, path, orNode,
00222 leaf_size, isPartialStack);
00223
00224 }
00225
00226 size_t osl::checkmate::analyzer::CheckTableAnalyzer::
00227 proofOrDisproofTreeSize(const CheckHashRecord *record,
00228 const HashKey& key, const PathEncoding& path,
00229 bool orNode, size_t& leaf_size,
00230 bool isPartialStack) const
00231 {
00232 try
00233 {
00234 TreeWriter writer;
00235 size_t tree_size;
00236 examineTreeGuess(record, table, key, path, orNode, isPartialStack, writer,
00237 tree_size, leaf_size);
00238 return tree_size;
00239 }
00240 catch (CorruptCheckTable& t)
00241 {
00242 std::cerr << t.what() << ", corrupt tree was " << t.record << "\n";
00243 t.record->dump();
00244 const char *filename = "checkmate-oops.log";
00245 std::ofstream os(filename);
00246 std::cerr << "entire tree is being written in " << filename << "\n";
00247 CheckTableAnalyzer a(table);
00248 a.showTree(record, os, 100, true, true);
00249 throw;
00250 }
00251 }
00252
00253 size_t osl::checkmate::analyzer::CheckTableAnalyzer::
00254 showProofTree(const CheckHashRecord *record,
00255 const HashKey& key, const PathEncoding& path,
00256 bool orNode, std::ostream& os, bool isPartialStack) const
00257 {
00258 boost::scoped_ptr<TreeWriter> writer;
00259 if (useOutlineFormat)
00260 writer.reset(new TreeStreamWriter(&os, true));
00261 else
00262 writer.reset(new DotWriter(os));
00263 size_t tree_size, leaf_size;
00264 examineTreeGuess(record, table, key, path, orNode, isPartialStack, *writer,
00265 tree_size, leaf_size);
00266 return tree_size;
00267 }
00268
00269
00270
00271
00272
00273