Newer
Older
MagnetRON / src / org / ntlab / trace / Trace.java
  1. package org.ntlab.trace;
  2.  
  3. import java.io.BufferedReader;
  4. import java.io.FileReader;
  5. import java.io.IOException;
  6. import java.util.ArrayList;
  7. import java.util.HashMap;
  8. import java.util.HashSet;
  9. import java.util.Iterator;
  10. import java.util.Stack;
  11.  
  12. public class Trace {
  13. protected static final boolean EAGER_DETECTION_OF_ARRAY_SET = false; // 配列要素への代入の検出を多く見積もるか?(多く見積もるとFalse Positiveになる可能性がある)
  14. protected static Trace theTrace = null;
  15. protected HashMap<String, ThreadInstance> threads = new HashMap<String, ThreadInstance>();
  16.  
  17. protected Trace() {
  18. }
  19. /**
  20. * 指定したPlainTextのトレースファイルを解読して Trace オブジェクトを生成する
  21. * @param file トレースファイル
  22. */
  23. public Trace(BufferedReader file) {
  24. try {
  25. read(file);
  26. file.close();
  27. } catch (IOException e) {
  28. e.printStackTrace();
  29. }
  30. }
  31. /**
  32. * 指定したPlainTextのトレースファイルを解読して Trace オブジェクトを生成する
  33. * @param traceFile トレースファイルのパス
  34. */
  35. public Trace(String traceFile) {
  36. BufferedReader file;
  37. try {
  38. file = new BufferedReader(new FileReader(traceFile));
  39. read(file);
  40. file.close();
  41. } catch (IOException e) {
  42. e.printStackTrace();
  43. }
  44. }
  45.  
  46. private void read(BufferedReader file) throws IOException {
  47. // トレースファイル読み込み
  48. String line, prevLine = null;
  49. String signature;
  50. String callerSideSignature;
  51. String threadNo = null;
  52. String[] methodData;
  53. String[] argData;
  54. String[] returnData;
  55. String[] accessData;
  56. String[] updateData;
  57. String thisObjectId;
  58. String thisClassName;
  59. boolean isConstractor = false;
  60. boolean isCollectionType = false;
  61. boolean isStatic = false;
  62. long timeStamp = 0L;
  63. ThreadInstance thread = null;
  64. HashMap<String, Stack<String>> stacks = new HashMap<String, Stack<String>>();
  65. while ((line = file.readLine()) != null) {
  66. // トレースファイルの解析
  67. if (line.startsWith("Method")) {
  68. // メソッド呼び出し(コンストラクタ呼び出しも含む)
  69. methodData = line.split(":");
  70. int n = methodData[0].indexOf(',');
  71. signature = methodData[0].substring(n + 1);
  72. threadNo = getThreadNo(line);
  73. // threadNo = methodData[methodData.length - 1].split(" ")[1];
  74. if (threadNo != null) {
  75. thisObjectId = methodData[1];
  76. thisClassName = methodData[0].substring(0, n).split(" ")[1];
  77. isConstractor = false;
  78. isStatic = false;
  79. if (signature.contains("static ")) {
  80. isStatic = true;
  81. }
  82. callerSideSignature = signature;
  83. timeStamp = Long.parseLong(methodData[methodData.length - 2]);
  84. if (prevLine != null) {
  85. if (prevLine.startsWith("New")) {
  86. isConstractor = true;
  87. } else if (prevLine.startsWith("Invoke")) {
  88. callerSideSignature = prevLine.split(":")[1];
  89. }
  90. }
  91. thread = threads.get(threadNo);
  92. Stack<String> stack;
  93. if (thread == null) {
  94. thread = new ThreadInstance(threadNo);
  95. threads.put(threadNo, thread);
  96. stack = new Stack<String>();
  97. stacks.put(threadNo, stack);
  98. } else {
  99. stack = stacks.get(threadNo);
  100. }
  101. stack.push(line);
  102. thread.callMethod(signature, callerSideSignature, thisClassName, thisObjectId, isConstractor, isStatic, timeStamp);
  103. }
  104. } else if (line.startsWith("Args")) {
  105. // メソッド呼び出しの引数
  106. argData = line.split(":");
  107. threadNo = getThreadNo(line);
  108. // threadNo = argData[argData.length - 1].split(" ")[1];
  109. if (threadNo != null) {
  110. thread = threads.get(threadNo);
  111. ArrayList<ObjectReference> arguments = new ArrayList<ObjectReference>();
  112. for (int k = 1; k < argData.length - 2; k += 2) {
  113. arguments.add(new ObjectReference(argData[k+1], argData[k]));
  114. }
  115. thread.setArgments(arguments);
  116. }
  117. } else if (line.startsWith("Return")) {
  118. // メソッドからの復帰
  119. returnData = line.split(":");
  120. threadNo = getThreadNo(line);
  121. // threadNo = returnData[returnData.length - 1].split(" ")[1];
  122. if (threadNo != null) {
  123. Stack<String> stack = stacks.get(threadNo);
  124. if (!stack.isEmpty()) {
  125. String line2 = stack.peek();
  126. if (line2.split("\\(")[0].endsWith(line.split("\\(")[1])) {
  127. stack.pop();
  128. } else {
  129. do {
  130. stack.pop();
  131. thread.terminateMethod();
  132. if (!stack.isEmpty()) line2 = stack.peek();
  133. } while (!stack.isEmpty() && !line2.split("\\(")[0].endsWith(line.split("\\(")[1]));
  134. if (!stack.isEmpty()) stack.pop();
  135. }
  136. thread = threads.get(threadNo);
  137. ObjectReference returnValue = new ObjectReference(returnData[2], returnData[1]);
  138. thisObjectId = returnData[2];
  139. isCollectionType = false;
  140. String curLine = returnData[0];
  141. if(curLine.contains("Return call(List")
  142. || curLine.contains("Return call(Vector")
  143. || curLine.contains("Return call(Iterator")
  144. || curLine.contains("Return call(ListIterator")
  145. || curLine.contains("Return call(ArrayList")
  146. || curLine.contains("Return call(Stack")
  147. || curLine.contains("Return call(Hash")
  148. || curLine.contains("Return call(Map")
  149. || curLine.contains("Return call(Set")
  150. || curLine.contains("Return call(Linked")
  151. || curLine.contains("Return call(Collection")
  152. || curLine.contains("Return call(Arrays")
  153. || curLine.contains("Return call(Thread")) {
  154. isCollectionType = true;
  155. }
  156. thread.returnMethod(returnValue, thisObjectId, isCollectionType);
  157. }
  158. }
  159. } else if (line.startsWith("get")) {
  160. // フィールドアクセス
  161. accessData = line.split(":");
  162. if (accessData.length >= 9) {
  163. threadNo = getThreadNo(line);
  164. // threadNo = accessData[8].split(" ")[1];
  165. if (threadNo != null) {
  166. thread = threads.get(threadNo);
  167. timeStamp++; // 仮のタイムスタンプ(実行順を保持するため)
  168. if (thread != null) thread.fieldAccess(accessData[5], accessData[6], accessData[3], accessData[4], accessData[1], accessData[2], 0, timeStamp);
  169. }
  170. }
  171. } else if (line.startsWith("set")) {
  172. // フィールド更新
  173. updateData = line.split(":");
  174. if (updateData.length >= 7) {
  175. threadNo = getThreadNo(line);
  176. // threadNo = updateData[6].split(" ")[1];
  177. if (threadNo != null) {
  178. thread = threads.get(threadNo);
  179. timeStamp++; // 仮のタイムスタンプ(実行順を保持するため)
  180. if (thread != null) thread.fieldUpdate(updateData[3], updateData[4], updateData[1], updateData[2], 0, timeStamp);
  181. }
  182. }
  183. }
  184. prevLine = line;
  185. }
  186. }
  187. private String getThreadNo(String line) {
  188. int tidx = line.indexOf("ThreadNo ");
  189. if (tidx == -1) return null;
  190. String threadNo = line.substring(tidx + 9);
  191. try {
  192. Integer.parseInt(threadNo);
  193. } catch (NumberFormatException e) {
  194. for (int i = 1; i <= threadNo.length(); i++) {
  195. try {
  196. Integer.parseInt(threadNo.substring(0, i));
  197. } catch (NumberFormatException e2) {
  198. threadNo = threadNo.substring(0, i - 1);
  199. break;
  200. }
  201. }
  202. }
  203. return threadNo;
  204. }
  205. /**
  206. * オンライン解析用シングルトンの取得
  207. * @return オンライン解析用トレース
  208. */
  209. public static Trace getInstance() {
  210. if (theTrace == null) {
  211. theTrace = new Trace();
  212. }
  213. return theTrace;
  214. }
  215. /**
  216. * スレッドIDを指定してスレッドインスタンスを取得する(オンライン解析用)
  217. * @param threadId
  218. * @return スレッドインスタンス
  219. */
  220. public static ThreadInstance getThreadInstance(String threadId) {
  221. return getInstance().threads.get(threadId);
  222. }
  223. /**
  224. * 指定したスレッド上で現在実行中のメソッド実行を取得する(オンライン解析用)
  225. * @param thread 対象スレッド
  226. * @return thread 上で現在実行中のメソッド実行
  227. */
  228. public static MethodExecution getCurrentMethodExecution(Thread thread) {
  229. ThreadInstance t = getInstance().threads.get(String.valueOf(thread.getId()));
  230. return t.getCurrentMethodExecution();
  231. }
  232. /**
  233. * 指定したスレッド上で現在実行中のトレースポイントを取得する(オンライン解析用)
  234. * @param thread 対象スレッド
  235. * @return thread 上で現在実行中の実行文のトレースポイント
  236. */
  237. public static TracePoint getCurrentTracePoint(Thread thread) {
  238. ThreadInstance t = getInstance().threads.get(String.valueOf(thread.getId()));
  239. return t.getCurrentTracePoint();
  240. }
  241. /**
  242. * 全スレッドを取得する
  243. * @return スレッドIDからスレッドインスタンスへのマップ
  244. */
  245. public HashMap<String, ThreadInstance> getAllThreads() {
  246. return threads;
  247. }
  248.  
  249. /**
  250. * メソッド毎に全メソッド実行を全てのスレッドから取り出す
  251. * @return メソッドシグニチャからメソッド実行のリストへのHashMap
  252. */
  253. public HashMap<String, ArrayList<MethodExecution>> getAllMethodExecutions() {
  254. Iterator<String> threadsIterator = threads.keySet().iterator();
  255. final HashMap<String, ArrayList<MethodExecution>> results = new HashMap<>();
  256. for (; threadsIterator.hasNext();) {
  257. ThreadInstance thread = threads.get(threadsIterator.next());
  258. thread.traverseMethodExecutionsBackward(new IMethodExecutionVisitor() {
  259. @Override
  260. public boolean preVisitThread(ThreadInstance thread) {
  261. return false;
  262. }
  263. @Override
  264. public boolean preVisitMethodExecution(MethodExecution methodExecution) {
  265. String signature = methodExecution.getSignature();
  266. ArrayList<MethodExecution> executions = results.get(signature);
  267. if (executions == null) {
  268. executions = new ArrayList<>();
  269. results.put(signature, executions);
  270. }
  271. executions.add(methodExecution);
  272. return false;
  273. }
  274. @Override
  275. public boolean postVisitThread(ThreadInstance thread) {
  276. return false;
  277. }
  278. @Override
  279. public boolean postVisitMethodExecution(MethodExecution methodExecution, ArrayList<MethodExecution> children) {
  280. return false;
  281. }
  282. });
  283. }
  284. return results;
  285. }
  286. /**
  287. * 全メソッドのシグニチャを取得する
  288. * @return 全メソッドシグニチャ
  289. */
  290. public HashSet<String> getAllMethodSignatures() {
  291. final HashSet<String> signatures = new HashSet<String>();
  292. Iterator<String> threadsIterator = threads.keySet().iterator();
  293. for (; threadsIterator.hasNext();) {
  294. ThreadInstance thread = threads.get(threadsIterator.next());
  295. thread.traverseMethodExecutionsBackward(new IMethodExecutionVisitor() {
  296. @Override
  297. public boolean preVisitThread(ThreadInstance thread) {
  298. return false;
  299. }
  300. @Override
  301. public boolean postVisitThread(ThreadInstance thread) {
  302. return false;
  303. }
  304. @Override
  305. public boolean preVisitMethodExecution(MethodExecution methodExecution) {
  306. signatures.add(methodExecution.getSignature());
  307. return false;
  308. }
  309. @Override
  310. public boolean postVisitMethodExecution(MethodExecution methodExecution, ArrayList<MethodExecution> children) {
  311. return false;
  312. }
  313. });
  314. }
  315. return signatures;
  316. }
  317. /**
  318. * メソッド名が methodSignature に前方一致するメソッド実行を全てのスレッドから取り出す
  319. * @param methodSignature 検索文字列
  320. * @return 一致した全メソッド実行
  321. */
  322. public ArrayList<MethodExecution> getMethodExecutions(final String methodSignature) {
  323. Iterator<String> threadsIterator = threads.keySet().iterator();
  324. final ArrayList<MethodExecution> results = new ArrayList<MethodExecution>();
  325. for (; threadsIterator.hasNext();) {
  326. ThreadInstance thread = threads.get(threadsIterator.next());
  327. thread.traverseMethodExecutionsBackward(new IMethodExecutionVisitor() {
  328. @Override
  329. public boolean preVisitThread(ThreadInstance thread) {
  330. return false;
  331. }
  332. @Override
  333. public boolean preVisitMethodExecution(MethodExecution methodExecution) {
  334. if (methodExecution.getSignature().startsWith(methodSignature)) {
  335. results.add(methodExecution);
  336. }
  337. return false;
  338. }
  339. @Override
  340. public boolean postVisitThread(ThreadInstance thread) {
  341. return false;
  342. }
  343. @Override
  344. public boolean postVisitMethodExecution(MethodExecution methodExecution, ArrayList<MethodExecution> children) {
  345. return false;
  346. }
  347. });
  348. }
  349. return results;
  350. }
  351.  
  352. /**
  353. * methodSignature に前方一致するメソッド名を持つメソッドの最後の実行
  354. * @param methodSignature メソッド名(前方一致で検索する)
  355. * @return 該当する最後のメソッド実行
  356. */
  357. public MethodExecution getLastMethodExecution(final String methodSignature) {
  358. return traverseMethodEntriesInTraceBackward(new IMethodExecutionVisitor() {
  359. @Override
  360. public boolean preVisitThread(ThreadInstance thread) { return false; }
  361. @Override
  362. public boolean postVisitThread(ThreadInstance thread) { return false; }
  363. @Override
  364. public boolean preVisitMethodExecution(MethodExecution methodExecution) { return false; }
  365. @Override
  366. public boolean postVisitMethodExecution(MethodExecution methodExecution, ArrayList<MethodExecution> children) {
  367. if (methodExecution.getSignature().startsWith(methodSignature)) return true;
  368. return false;
  369. }
  370. });
  371. }
  372.  
  373. /**
  374. * methodSignature に前方一致するメソッド名を持つメソッドの before 以前の最後の実行
  375. * @param methodSignature メソッド名(前方一致で検索する)
  376. * @param before 探索開始トレースポイント(これより以前を探索)
  377. * @return 該当する最後のメソッド実行
  378. */
  379. public MethodExecution getLastMethodExecution(final String methodSignature, TracePoint before) {
  380. return traverseMethodEntriesInTraceBackward(new IMethodExecutionVisitor() {
  381. @Override
  382. public boolean preVisitThread(ThreadInstance thread) { return false; }
  383. @Override
  384. public boolean postVisitThread(ThreadInstance thread) { return false; }
  385. @Override
  386. public boolean preVisitMethodExecution(MethodExecution methodExecution) { return false; }
  387. @Override
  388. public boolean postVisitMethodExecution(MethodExecution methodExecution, ArrayList<MethodExecution> children) {
  389. if (methodExecution.getSignature().startsWith(methodSignature)) return true;
  390. return false;
  391. }
  392. }, before);
  393. }
  394. /**
  395. * マーク内で実行が開始された全メソッドのシグニチャを取得する
  396. * @param markStart マークの開始時刻
  397. * @param markEnd マークの終了時刻
  398. * @return 該当するメソッドシグニチャ
  399. */
  400. public HashSet<String> getMarkedMethodSignatures(final long markStart, final long markEnd) {
  401. final HashSet<String> signatures = new HashSet<String>();
  402. Iterator<String> threadsIterator = threads.keySet().iterator();
  403. for (; threadsIterator.hasNext();) {
  404. ThreadInstance thread = threads.get(threadsIterator.next());
  405. thread.traverseMarkedMethodExecutions(new IMethodExecutionVisitor() {
  406. @Override
  407. public boolean preVisitThread(ThreadInstance thread) {
  408. return false;
  409. }
  410. @Override
  411. public boolean postVisitThread(ThreadInstance thread) {
  412. return false;
  413. }
  414. @Override
  415. public boolean preVisitMethodExecution(MethodExecution methodExecution) {
  416. signatures.add(methodExecution.getSignature());
  417. return false;
  418. }
  419. @Override
  420. public boolean postVisitMethodExecution(MethodExecution methodExecution, ArrayList<MethodExecution> children) {
  421. return false;
  422. }
  423. }, markStart, markEnd);
  424. }
  425. return signatures;
  426. }
  427. /**
  428. * マーク内で実行が開始された全メソッド実行をメソッド毎に取得する
  429. * @param markStart マークの開始時刻
  430. * @param markEnd マークの終了時刻
  431. * @return メソッドシグニチャから該当するメソッド実行のリストへのHashMap
  432. */
  433. public HashMap<String, ArrayList<MethodExecution>> getMarkedMethodExecutions(final long markStart, final long markEnd) {
  434. final HashMap<String, ArrayList<MethodExecution>>allExecutions = new HashMap<>();
  435. Iterator<String> threadsIterator = threads.keySet().iterator();
  436. for (; threadsIterator.hasNext();) {
  437. ThreadInstance thread = threads.get(threadsIterator.next());
  438. thread.traverseMarkedMethodExecutions(new IMethodExecutionVisitor() {
  439. @Override
  440. public boolean preVisitThread(ThreadInstance thread) {
  441. return false;
  442. }
  443. @Override
  444. public boolean postVisitThread(ThreadInstance thread) {
  445. return false;
  446. }
  447. @Override
  448. public boolean preVisitMethodExecution(MethodExecution methodExecution) {
  449. ArrayList<MethodExecution> executions = allExecutions.get(methodExecution.getSignature());
  450. if (executions == null) {
  451. executions = new ArrayList<>();
  452. allExecutions.put(methodExecution.getSignature(), executions);
  453. }
  454. executions.add(methodExecution);
  455. return false;
  456. }
  457. @Override
  458. public boolean postVisitMethodExecution(MethodExecution methodExecution, ArrayList<MethodExecution> children) {
  459. return false;
  460. }
  461. }, markStart, markEnd);
  462. }
  463. return allExecutions;
  464. }
  465. /**
  466. * マーク外で実行が開始された全メソッドのシグニチャを取得する
  467. * @param markStart マークの開始時刻
  468. * @param markEnd マークの終了時刻
  469. * @return 該当するメソッドシグニチャ
  470. */
  471. public HashSet<String> getUnmarkedMethodSignatures(long markStart, long markEnd) {
  472. HashSet<String> signatures = new HashSet<String>();
  473. Iterator<String> threadsIterator = threads.keySet().iterator();
  474. for (; threadsIterator.hasNext();) {
  475. ThreadInstance thread = threads.get(threadsIterator.next());
  476. thread.getUnmarkedMethodSignatures(signatures, markStart, markEnd);
  477. }
  478. return signatures;
  479. }
  480. /**
  481. * マーク外で実行が開始された全メソッド実行を取得する
  482. * @param markStart マークの開始時刻
  483. * @param markEnd マークの終了時刻
  484. * @return メソッドシグニチャから該当するメソッド実行のリストへのHashMap
  485. */
  486. public HashMap<String, ArrayList<MethodExecution>> getUnmarkedMethodExecutions(long markStart, long markEnd) {
  487. HashMap<String, ArrayList<MethodExecution>> executions = new HashMap<>();
  488. Iterator<String> threadsIterator = threads.keySet().iterator();
  489. for (; threadsIterator.hasNext();) {
  490. ThreadInstance thread = threads.get(threadsIterator.next());
  491. thread.getUnmarkedMethodExecutions(executions, markStart, markEnd);
  492. }
  493. return executions;
  494. }
  495. protected TracePoint getLastMethodEntryInThread(ArrayList<MethodExecution> rootExecutions) {
  496. MethodExecution lastExecution = rootExecutions.remove(rootExecutions.size() - 1);
  497. return getLastMethodEntryInThread(rootExecutions, lastExecution.getExitOutPoint());
  498. }
  499.  
  500. protected TracePoint getLastMethodEntryInThread(ArrayList<MethodExecution> rootExecutions, TracePoint start) {
  501. return getLastMethodEntryInThread(rootExecutions, start, -1L);
  502. }
  503. /**
  504. *
  505. * @param rootExecutions
  506. * @param start
  507. * @param before
  508. * @return
  509. */
  510. protected TracePoint getLastMethodEntryInThread(ArrayList<MethodExecution> rootExecutions, TracePoint start, final long before) {
  511. final TracePoint cp[] = new TracePoint[1];
  512. cp[0] = start;
  513. for (;;) {
  514. if (!cp[0].isStepBackOut() && traverseMethodExecutionsInCallTreeBackward (
  515. new IMethodExecutionVisitor() {
  516. @Override
  517. public boolean preVisitThread(ThreadInstance thread) { return false; }
  518. @Override
  519. public boolean preVisitMethodExecution(MethodExecution methodExecution) { return false; }
  520. @Override
  521. public boolean postVisitThread(ThreadInstance thread) { return false; }
  522. @Override
  523. public boolean postVisitMethodExecution(MethodExecution methodExecution, ArrayList<MethodExecution> children) {
  524. if (methodExecution.getEntryTime() < before || before == -1L) {
  525. cp[0] = methodExecution.getEntryPoint();
  526. return true;
  527. }
  528. return false;
  529. }
  530. }, cp[0])) {
  531. return cp[0];
  532. }
  533. if (rootExecutions.size() == 0) break;
  534. MethodExecution lastExecution = rootExecutions.remove(rootExecutions.size() - 1);
  535. cp[0] = lastExecution.getExitOutPoint();
  536. }
  537. return null;
  538. }
  539. public boolean getLastStatementInThread(String threadId, final TracePoint[] start, final IStatementVisitor visitor) {
  540. return getLastStatementInThread((ArrayList<MethodExecution>) threads.get(threadId).getRoot().clone(), start, start[0].getStatement().getTimeStamp(), visitor);
  541. }
  542. protected boolean getLastStatementInThread(ArrayList<MethodExecution> rootExecutions, final TracePoint[] start, final long before, final IStatementVisitor visitor) {
  543. final boolean[] bArrived = new boolean[] {
  544. false
  545. };
  546. for (;;) {
  547. if (start[0].isValid() && traverseStatementsInCallTreeBackward(
  548. new IStatementVisitor() {
  549. @Override
  550. public boolean preVisitStatement(Statement statement) {
  551. if (statement instanceof MethodInvocation) {
  552. MethodExecution methodExecution = ((MethodInvocation) statement).getCalledMethodExecution();
  553. if ((!methodExecution.isTerminated() && methodExecution.getExitTime() < before) || before == -1L) {
  554. if (visitor.preVisitStatement(statement)) return true;
  555. bArrived[0] = true;
  556. return true;
  557. }
  558. } else {
  559. if (statement.getTimeStamp() < before || before == -1L) {
  560. if (visitor.preVisitStatement(statement)) return true;
  561. bArrived[0] = true;
  562. return true;
  563. }
  564. }
  565. return visitor.preVisitStatement(statement);
  566. }
  567. @Override
  568. public boolean postVisitStatement(Statement statement) {
  569. return visitor.postVisitStatement(statement);
  570. }
  571. }, start[0])) {
  572. return !bArrived[0];
  573. }
  574. if (rootExecutions.size() == 0) break;
  575. MethodExecution lastExecution = rootExecutions.remove(rootExecutions.size() - 1);
  576. start[0] = lastExecution.getExitPoint();
  577. }
  578. start[0] = null;
  579. return false;
  580. }
  581. public TracePoint getLastTracePoint() {
  582. TracePoint tp = null;
  583. for (ThreadInstance thread: threads.values()) {
  584. if (tp == null || thread.getLastTracePoint().getStatement().getTimeStamp() > tp.getStatement().getTimeStamp()) {
  585. tp = thread.getLastTracePoint();
  586. }
  587. }
  588. return tp;
  589. }
  590.  
  591. public TracePoint getCreationTracePoint(final ObjectReference newObjectId, TracePoint before) {
  592. if (before != null) before = before.duplicate();
  593. before = traverseStatementsInTraceBackward(
  594. new IStatementVisitor() {
  595. @Override
  596. public boolean preVisitStatement(Statement statement) {
  597. if (statement instanceof MethodInvocation) {
  598. MethodInvocation mi = (MethodInvocation)statement;
  599. if (mi.getCalledMethodExecution().isConstructor()
  600. && mi.getCalledMethodExecution().getReturnValue().equals(newObjectId)) {
  601. return true;
  602. }
  603. }
  604. return false;
  605. }
  606. @Override
  607. public boolean postVisitStatement(Statement statement) { return false; }
  608. }, before);
  609. if (before != null) {
  610. return before;
  611. }
  612. return null;
  613. }
  614.  
  615. public TracePoint getFieldUpdateTracePoint(final Reference ref, TracePoint before) {
  616. if (before != null) before = before.duplicate();
  617. final String srcType = ref.getSrcClassName();
  618. final String dstType = ref.getDstClassName();
  619. final String srcObjId = ref.getSrcObjectId();
  620. final String dstObjId = ref.getDstObjectId();
  621. before = traverseStatementsInTraceBackward(new IStatementVisitor() {
  622. @Override
  623. public boolean preVisitStatement(Statement statement) {
  624. if (statement instanceof FieldUpdate) {
  625. FieldUpdate fu = (FieldUpdate)statement;
  626. if (fu.getContainerObjId().equals(srcObjId)
  627. && fu.getValueObjId().equals(dstObjId)) {
  628. // オブジェクトIDが互いに一致した場合
  629. return true;
  630. } else if ((srcObjId == null || isNull(srcObjId)) && fu.getContainerClassName().equals(srcType)) {
  631. if ((dstObjId == null || isNull(dstObjId)) && fu.getValueClassName().equals(dstType)) {
  632. // ref にオブジェクトIDを指定していなかった場合
  633. ref.setSrcObjectId(fu.getContainerObjId());
  634. ref.setDstObjectId(fu.getValueObjId());
  635. return true;
  636. } else if (fu.getValueObjId().equals(dstObjId)) {
  637. // クラス変数への代入の場合
  638. ref.setSrcObjectId(srcObjId);
  639. ref.setDstClassName(dstType);
  640. return true;
  641. }
  642. }
  643. }
  644. return false;
  645. }
  646. @Override
  647. public boolean postVisitStatement(Statement statement) { return false; }
  648. }, before);
  649. if (before != null) {
  650. return before;
  651. }
  652. return null;
  653. }
  654.  
  655. public TracePoint getCollectionAddTracePoint(final Reference ref, TracePoint before) {
  656. final TracePoint[] result = new TracePoint[1];
  657. if (traverseMethodEntriesInTraceBackward(new IMethodExecutionVisitor() {
  658. @Override
  659. public boolean preVisitThread(ThreadInstance thread) {
  660. return false;
  661. }
  662. @Override
  663. public boolean postVisitThread(ThreadInstance thread) {
  664. return false;
  665. }
  666. @Override
  667. public boolean preVisitMethodExecution(MethodExecution methodExecution) {
  668. return false;
  669. }
  670. @Override
  671. public boolean postVisitMethodExecution(MethodExecution methodExecution, ArrayList<MethodExecution> children) {
  672. String srcType = ref.getSrcClassName();
  673. String dstType = ref.getDstClassName();
  674. String srcObjId = ref.getSrcObjectId();
  675. String dstObjId = ref.getDstObjectId();
  676. if (methodExecution.isCollectionType() && isCollectionAdd(methodExecution.getSignature())) {
  677. if (dstObjId != null && methodExecution.getThisObjId().equals(srcObjId)) {
  678. ArrayList<ObjectReference> args = methodExecution.getArguments();
  679. for (int i = 0; i < args.size(); i++) {
  680. ObjectReference arg = args.get(i);
  681. if (arg.getId().equals(dstObjId)) {
  682. ref.setSrcClassName(methodExecution.getThisClassName());
  683. ref.setDstClassName(arg.getActualType());
  684. result[0] = methodExecution.getCallerTracePoint();
  685. return true;
  686. }
  687. }
  688. } else if (dstObjId == null && methodExecution.getThisClassName().equals(srcType)) {
  689. ArrayList<ObjectReference> args = methodExecution.getArguments();
  690. for (int i = 0; i < args.size(); i++) {
  691. ObjectReference arg = args.get(i);
  692. if (arg.getActualType().equals(dstType)) {
  693. ref.setSrcObjectId(methodExecution.getThisObjId());
  694. ref.setDstObjectId(arg.getId());
  695. result[0] = methodExecution.getCallerTracePoint();
  696. return true;
  697. }
  698. }
  699. }
  700. }
  701. return false;
  702. }
  703. }, before) != null) {
  704. return result[0];
  705. }
  706. return null;
  707. }
  708.  
  709. public TracePoint getArraySetTracePoint(final Reference ref, TracePoint before) {
  710. final TracePoint start = (before == null) ? null : before.duplicate();
  711. before = traverseStatementsInTraceBackward(new IStatementVisitor() {
  712. @Override
  713. public boolean preVisitStatement(Statement statement) {
  714. if (statement instanceof FieldAccess) {
  715. if (isArraySet(ref, start)) {
  716. return true;
  717. }
  718. }
  719. return false;
  720. }
  721. @Override
  722. public boolean postVisitStatement(Statement statement) { return false; }
  723. }, start);
  724. if (before != null) {
  725. return before;
  726. }
  727. return null;
  728. }
  729. private boolean isCollectionAdd(String methodSignature) {
  730. return (methodSignature.contains("add(") || methodSignature.contains("set(") || methodSignature.contains("put(") || methodSignature.contains("push(") || methodSignature.contains("addElement("));
  731. }
  732. private boolean isArraySet(Reference ref, TracePoint fieldAccessPoint) {
  733. FieldAccess fieldAccess = (FieldAccess)fieldAccessPoint.getStatement();
  734. String srcObjId = ref.getSrcObjectId();
  735. String dstObjId = ref.getDstObjectId();
  736. if (fieldAccess.getValueClassName().startsWith("[L")
  737. && fieldAccess.getValueObjId().equals(srcObjId)) {
  738. // srcId は配列
  739. // メソッド実行開始から fieldAccessPoint までの間のメソッド実行中で dstId が出現したか?
  740. TracePoint p = fieldAccessPoint.duplicate();
  741. while (p.stepBackOver()) {
  742. Statement statement = p.getStatement();
  743. if (statement instanceof MethodInvocation) {
  744. MethodExecution calledMethod = ((MethodInvocation)statement).getCalledMethodExecution();
  745. if (calledMethod.getReturnValue().getId().equals(dstObjId)) {
  746. // dstId は戻り値として出現
  747. ref.setSrcClassName(fieldAccess.getValueClassName());
  748. ref.setDstClassName(calledMethod.getReturnValue().getActualType());
  749. return true;
  750. } else if (dstObjId == null || isNull(dstObjId) && calledMethod.getReturnValue().getActualType().equals(ref.getDstClassName())) {
  751. // dstClassName は戻り値の型として出現
  752. ref.setSrcObjectId(fieldAccess.getValueObjId());
  753. ref.setDstObjectId(calledMethod.getReturnValue().getId());
  754. return true;
  755. }
  756. }
  757. if (EAGER_DETECTION_OF_ARRAY_SET) {
  758. if (statement instanceof FieldAccess) {
  759. if (((FieldAccess)statement).getContainerObjId().equals(dstObjId)) {
  760. // dstId はフィールドに出現
  761. ref.setSrcClassName(fieldAccess.getValueClassName());
  762. ref.setDstClassName(((FieldAccess)statement).getContainerClassName());
  763. return true;
  764. } else if (dstObjId == null || isNull(dstObjId) && ((FieldAccess)statement).getContainerClassName().equals(ref.getDstClassName())) {
  765. // dstClassName はフィールドの型として出現
  766. ref.setSrcObjectId(fieldAccess.getValueObjId());
  767. ref.setDstObjectId(((FieldAccess)statement).getContainerObjId());
  768. return true;
  769. }
  770. }
  771. }
  772. }
  773. ArrayList<ObjectReference> args = fieldAccessPoint.getMethodExecution().getArguments();
  774. int argindex = args.indexOf(new ObjectReference(dstObjId));
  775. if (argindex != -1) {
  776. // dstId は引数に出現
  777. ref.setSrcClassName(fieldAccess.getValueClassName());
  778. ref.setDstClassName(args.get(argindex).getActualType());
  779. return true;
  780. } else if (dstObjId == null || isNull(dstObjId)) {
  781. for (int j = 0; j < args.size(); j++) {
  782. if (args.get(j).getActualType().equals(ref.getDstClassName())) {
  783. // dstClassName は引数の型に出現
  784. ref.setSrcObjectId(fieldAccess.getValueObjId());
  785. ref.setDstObjectId(args.get(j).getId());
  786. return true;
  787. }
  788. }
  789. }
  790. }
  791. return false;
  792. }
  793. /**
  794. * トレース中の全メソッド実行の開始地点を逆向きに探索する
  795. * @param visitor メソッド実行のビジター(postVisitMethodExecution()しか呼び返さないので注意)
  796. * @return 中断したメソッド実行
  797. */
  798. public MethodExecution traverseMethodEntriesInTraceBackward(IMethodExecutionVisitor visitor) {
  799. HashMap<String, ArrayList<MethodExecution>> threadRoots = new HashMap<String, ArrayList<MethodExecution>>();
  800. HashMap<String, TracePoint> threadLastPoints = new HashMap<String, TracePoint>();
  801. // 各スレッドにおいて一番最後に開始したメソッド実行を探す
  802. long traceLastTime = 0;
  803. String traceLastThread = null;
  804. long traceLastTime2 = 0;
  805. String traceLastThread2 = null;
  806. for (String threadId: threads.keySet()) {
  807. ThreadInstance thread = threads.get(threadId);
  808. ArrayList<MethodExecution> rootExecutions = (ArrayList<MethodExecution>)thread.getRoot().clone();
  809. threadRoots.put(threadId, rootExecutions);
  810. TracePoint threadLastTp = getLastMethodEntryInThread(rootExecutions);
  811. threadLastPoints.put(threadId, threadLastTp);
  812. if (threadLastTp != null) {
  813. long threadLastTime = threadLastTp.getMethodExecution().getEntryTime();
  814. if (traceLastTime < threadLastTime) {
  815. traceLastTime2 = traceLastTime;
  816. traceLastThread2 = traceLastThread;
  817. traceLastTime = threadLastTime;
  818. traceLastThread = threadId;
  819. } else if (traceLastTime2 < threadLastTime) {
  820. traceLastTime2 = threadLastTime;
  821. traceLastThread2 = threadId;
  822. }
  823. }
  824. }
  825. return traverseMethodEntriesInTraceBackwardSub(visitor, threadRoots, threadLastPoints, traceLastThread, traceLastThread2, traceLastTime2);
  826. }
  827. /**
  828. * 指定した実行時点以前に実行が開始されたメソッド実行の開始時点を逆向きに探索する
  829. * @param visitor メソッド実行のビジター(postVisitMethodExecution()しか呼び返さないので注意)
  830. * @param before 探索開始時点
  831. * @return 中断したメソッド実行
  832. */
  833. public MethodExecution traverseMethodEntriesInTraceBackward(IMethodExecutionVisitor visitor, TracePoint before) {
  834. if (before == null) {
  835. return traverseMethodEntriesInTraceBackward(visitor);
  836. }
  837. HashMap<String, ArrayList<MethodExecution>> threadRoots = new HashMap<String, ArrayList<MethodExecution>>();
  838. HashMap<String, TracePoint> threadLastPoints = new HashMap<String, TracePoint>();
  839. String traceLastThread = null;
  840. long traceLastTime2 = 0;
  841. String traceLastThread2 = null;
  842. Statement st = before.getStatement();
  843. if (st == null) {
  844. st = before.getMethodExecution().getCallerTracePoint().getStatement();
  845. }
  846. ThreadInstance thread = threads.get(st.getThreadNo());
  847. ArrayList<MethodExecution> rootExecutions = (ArrayList<MethodExecution>)thread.getRoot().clone();
  848. for (int n = rootExecutions.size() - 1; n >= 0; n--) {
  849. MethodExecution root = rootExecutions.get(n);
  850. if (root.getEntryTime() > before.getMethodExecution().getEntryTime()) {
  851. rootExecutions.remove(n);
  852. } else {
  853. break;
  854. }
  855. }
  856. if (rootExecutions.size() > 0) {
  857. rootExecutions.remove(rootExecutions.size() - 1);
  858. }
  859. before = getLastMethodEntryInThread(rootExecutions, before);
  860. for (String threadId: threads.keySet()) {
  861. ThreadInstance t = threads.get(threadId);
  862. if (t == thread) {
  863. threadRoots.put(threadId, rootExecutions);
  864. traceLastThread = threadId;
  865. threadLastPoints.put(threadId, before);
  866. } else {
  867. ArrayList<MethodExecution> rootExes = (ArrayList<MethodExecution>)t.getRoot().clone();
  868. threadRoots.put(threadId, rootExes);
  869. MethodExecution threadLastExecution = rootExes.remove(rootExes.size() - 1);
  870. TracePoint threadBeforeTp = getLastMethodEntryInThread(rootExes, threadLastExecution.getExitOutPoint(), before.getMethodExecution().getEntryTime());
  871. threadLastPoints.put(threadId, threadBeforeTp);
  872. if (threadBeforeTp != null) {
  873. long threadLastTime = threadBeforeTp.getMethodExecution().getEntryTime();
  874. if (traceLastTime2 < threadLastTime) {
  875. traceLastTime2 = threadLastTime;
  876. traceLastThread2 = threadId;
  877. }
  878. }
  879. }
  880. }
  881. return traverseMethodEntriesInTraceBackwardSub(visitor, threadRoots, threadLastPoints, traceLastThread, traceLastThread2, traceLastTime2);
  882. }
  883. private MethodExecution traverseMethodEntriesInTraceBackwardSub(
  884. final IMethodExecutionVisitor visitor,
  885. HashMap<String, ArrayList<MethodExecution>> threadRoots, HashMap<String, TracePoint> threadLastPoints,
  886. String traceLastThread, String traceLastThread2, long traceLastTime2) {
  887. // 全スレッドの同期をとりながら逆向きにメソッド実行を探索する
  888. for (;;) {
  889. // 探索対象のスレッド内の逆向き探索
  890. TracePoint threadLastTp = threadLastPoints.get(traceLastThread);
  891. MethodExecution threadLastExecution = threadLastTp.getMethodExecution();
  892. do {
  893. threadLastTp.stepBackOver();
  894. // そのスレッドの次のメソッド実行開始時点まで探索する
  895. threadLastTp = getLastMethodEntryInThread(threadRoots.get(traceLastThread), threadLastTp);
  896. if (threadLastTp == null) break;
  897. if (visitor.postVisitMethodExecution(threadLastExecution, threadLastExecution.getChildren())) {
  898. // 該当するメソッド実行を見つけた
  899. return threadLastExecution;
  900. }
  901. threadLastExecution = threadLastTp.getMethodExecution();
  902. } while (threadLastExecution.getEntryTime() > traceLastTime2);
  903. threadLastPoints.put(traceLastThread, threadLastTp);
  904. traceLastThread = traceLastThread2;
  905. // 次の次に探索すべきスレッド(未探索の領域が一番最後まで残っているスレッド)を決定する
  906. traceLastTime2 = 0;
  907. traceLastThread2 = null;
  908. boolean continueTraverse = false;
  909. for (String threadId: threadLastPoints.keySet()) {
  910. if (!threadId.equals(traceLastThread)) {
  911. TracePoint lastTp = threadLastPoints.get(threadId);
  912. if (lastTp != null) {
  913. continueTraverse = true;
  914. long threadLastTime = lastTp.getMethodExecution().getEntryTime();
  915. if (traceLastTime2 < threadLastTime) {
  916. traceLastTime2 = threadLastTime;
  917. traceLastThread2 = threadId;
  918. }
  919. }
  920. }
  921. }
  922. if (!continueTraverse && threadLastPoints.get(traceLastThread) == null) break;
  923. }
  924. return null;
  925. }
  926. /**
  927. * 呼び出し時の時刻が markStart から markEnd の間にある全スレッド中の全メソッド実行を探索する
  928. * @param visitor ビジター
  929. * @param markStart 開始時刻
  930. * @param markEnd 終了時刻
  931. */
  932. public void traverseMarkedMethodExecutions(IMethodExecutionVisitor visitor, long markStart, long markEnd) {
  933. for (String threadId: threads.keySet()) {
  934. ThreadInstance thread = threads.get(threadId);
  935. thread.traverseMarkedMethodExecutions(visitor, markStart, markEnd);
  936. }
  937. }
  938. /**
  939. * トレース内の全スレッドを同期させならが全実行文を順方向に探索する
  940. *
  941. * @param visitor 実行文のビジター
  942. * @return 中断したトレースポイント
  943. */
  944. public TracePoint traverseStatementsInTrace(IStatementVisitor visitor) {
  945. HashMap<String, ArrayList<MethodExecution>> threadRoots = new HashMap<String, ArrayList<MethodExecution>>();
  946. HashMap<String, TracePoint> threadCurPoints = new HashMap<String, TracePoint>();
  947. // 各スレッドにおいて一番最初に開始したメソッド実行を探す
  948. long traceCurTime = -1;
  949. String traceCurThread = null;
  950. long traceCurTime2 = -1;
  951. String traceCurThread2 = null;
  952. for (String threadId: threads.keySet()) {
  953. ThreadInstance thread = threads.get(threadId);
  954. ArrayList<MethodExecution> roots = (ArrayList<MethodExecution>)thread.getRoot().clone();
  955. threadRoots.put(threadId, roots);
  956. TracePoint threadCurTp;
  957. do {
  958. MethodExecution threadCurExecution = roots.remove(0);
  959. threadCurTp = threadCurExecution.getEntryPoint();
  960. } while (!threadCurTp.isValid() && roots.size() > 0);
  961. if (threadCurTp.isValid()) {
  962. threadCurPoints.put(threadId, threadCurTp);
  963. long methodEntry = threadCurTp.getMethodExecution().getEntryTime();
  964. if (traceCurTime == -1 || traceCurTime > methodEntry) {
  965. traceCurTime2 = traceCurTime;
  966. traceCurThread2 = traceCurThread;
  967. traceCurTime = methodEntry;
  968. traceCurThread = threadId;
  969. } else if (traceCurTime2 == -1 || traceCurTime2 > methodEntry) {
  970. traceCurTime2 = methodEntry;
  971. traceCurThread2 = threadId;
  972. }
  973. } else {
  974. threadCurPoints.put(threadId, null);
  975. }
  976. }
  977. return traverseStatementsInTraceSub(visitor, threadRoots, threadCurPoints, traceCurThread, traceCurThread2, traceCurTime2);
  978. }
  979. private TracePoint traverseStatementsInTraceSub(IStatementVisitor visitor,
  980. HashMap<String, ArrayList<MethodExecution>> threadRoots,
  981. HashMap<String, TracePoint> threadCurPoints,
  982. String curThreadId, String nextThreadId, long nextThreadTime) {
  983. // 全スレッドの同期をとりながら順方向に実行文を探索する
  984. for (;;) {
  985. // 探索対象のスレッド内の順方向探索
  986. TracePoint curTp = threadCurPoints.get(curThreadId);
  987. while (curTp != null
  988. && (curTp.getStatement().getTimeStamp() <= nextThreadTime || nextThreadTime == -1)) {
  989. Statement statement = curTp.getStatement();
  990. if (!(visitor instanceof AbstractTracePointVisitor)) {
  991. if (visitor.preVisitStatement(statement)) return curTp;
  992. if (!(statement instanceof MethodInvocation)) {
  993. if (visitor.postVisitStatement(statement)) return curTp;
  994. }
  995. } else {
  996. // トレースポイントの情報も必要な場合
  997. if (((AbstractTracePointVisitor) visitor).preVisitStatement(statement, curTp)) return curTp;
  998. if (!(statement instanceof MethodInvocation)) {
  999. if (((AbstractTracePointVisitor) visitor).postVisitStatement(statement, curTp)) return curTp;
  1000. }
  1001. }
  1002. curTp.stepNoReturn(); // 復帰せずに呼び出し木を潜っていく
  1003. if (!curTp.isValid()) {
  1004. // 復帰しないとこれ以上探索できない
  1005. while (!curTp.stepOver()) { // 今度は復帰はするが潜らずに探索
  1006. if (curTp.isValid()) {
  1007. // 呼び出し先探索前に一度訪問済みのメソッド呼び出し行を、探索後もう一度訪問する
  1008. if (!(visitor instanceof AbstractTracePointVisitor)) {
  1009. if (visitor.postVisitStatement(curTp.getStatement())) return curTp;
  1010. } else {
  1011. // トレースポイントの情報も必要な場合
  1012. if (((AbstractTracePointVisitor) visitor).postVisitStatement(curTp.getStatement(), curTp)) return curTp;
  1013. }
  1014. } else {
  1015. // 呼び出し木の開始時点まで探索し終えた場合
  1016. ArrayList<MethodExecution> roots = threadRoots.get(curThreadId);
  1017. while (!curTp.isValid() && roots.size() > 0) {
  1018. // 次の呼び出し木があればそれを最初から探索
  1019. MethodExecution firstExecution = roots.remove(0);
  1020. curTp = firstExecution.getEntryPoint();
  1021. }
  1022. if (curTp.isValid()) {
  1023. // 次の呼び出し木があればそれを最初から探索
  1024. threadCurPoints.put(curThreadId, curTp);
  1025. } else {
  1026. // そのスレッドの探索がすべて終了した場合
  1027. threadCurPoints.put(curThreadId, null);
  1028. curTp = null;
  1029. }
  1030. break;
  1031. }
  1032. }
  1033. }
  1034. }
  1035. curThreadId = nextThreadId;
  1036. if (curThreadId == null) break;
  1037. // 次の次に探索すべきスレッド(未探索の領域が一番最初に始まるスレッド)を決定する
  1038. nextThreadTime = -1;
  1039. nextThreadId = null;
  1040. boolean continueTraverse = false;
  1041. for (String threadId: threadCurPoints.keySet()) {
  1042. if (!threadId.equals(curThreadId)) {
  1043. TracePoint threadTp = threadCurPoints.get(threadId);
  1044. if (threadTp != null) {
  1045. continueTraverse = true;
  1046. long threadTime = threadTp.getStatement().getTimeStamp();
  1047. if (threadTime > 0 && (nextThreadTime == -1 || nextThreadTime > threadTime)) {
  1048. nextThreadTime = threadTime;
  1049. nextThreadId = threadId;
  1050. }
  1051. }
  1052. }
  1053. }
  1054. if (!continueTraverse && threadCurPoints.get(curThreadId) == null) break;
  1055. }
  1056. return null;
  1057. }
  1058. /**
  1059. * トレース内の全スレッドを同期させならが全実行文を逆方向に探索する
  1060. *
  1061. * @param visitor 実行文のビジター
  1062. * @return 中断したトレースポイント
  1063. */
  1064. public TracePoint traverseStatementsInTraceBackward(IStatementVisitor visitor) {
  1065. HashMap<String, ArrayList<MethodExecution>> threadRoots = new HashMap<String, ArrayList<MethodExecution>>();
  1066. HashMap<String, TracePoint> threadLastPoints = new HashMap<String, TracePoint>();
  1067. // 各スレッドにおいて一番最後に開始したメソッド実行を探す
  1068. long traceLastTime = 0;
  1069. String traceLastThread = null;
  1070. long traceLastTime2 = 0;
  1071. String traceLastThread2 = null;
  1072. for (String threadId: threads.keySet()) {
  1073. ThreadInstance thread = threads.get(threadId);
  1074. ArrayList<MethodExecution> root = (ArrayList<MethodExecution>)thread.getRoot().clone();
  1075. threadRoots.put(threadId, root);
  1076. TracePoint threadLastTp;
  1077. do {
  1078. MethodExecution threadLastExecution = root.remove(root.size() - 1);
  1079. threadLastTp = threadLastExecution.getExitPoint();
  1080. } while (!threadLastTp.isValid() && root.size() > 0);
  1081. if (threadLastTp.isValid()) {
  1082. threadLastPoints.put(threadId, threadLastTp);
  1083. if (traverseStatamentsInCallTreeBackwardNoReturn(visitor, threadLastTp)) return threadLastTp;
  1084. long methodEntry = threadLastTp.getMethodExecution().getEntryTime();
  1085. if (traceLastTime < methodEntry) {
  1086. traceLastTime2 = traceLastTime;
  1087. traceLastThread2 = traceLastThread;
  1088. traceLastTime = methodEntry;
  1089. traceLastThread = threadId;
  1090. } else if (traceLastTime2 < methodEntry) {
  1091. traceLastTime2 = methodEntry;
  1092. traceLastThread2 = threadId;
  1093. }
  1094. } else {
  1095. threadLastPoints.put(threadId, null);
  1096. }
  1097. }
  1098. return traverseStatementsInTraceBackwardSub(visitor, threadRoots, threadLastPoints, traceLastThread, traceLastThread2, traceLastTime2);
  1099. }
  1100. /**
  1101. *
  1102. * @param visitor
  1103. * @param before
  1104. * @return
  1105. */
  1106. public TracePoint traverseStatementsInTraceBackward(IStatementVisitor visitor, TracePoint before) {
  1107. if (before == null) {
  1108. return traverseStatementsInTraceBackward(visitor);
  1109. }
  1110. if (traverseStatamentsInCallTreeBackwardNoReturn(visitor, before)) return before;
  1111. HashMap<String, ArrayList<MethodExecution>> threadRoots = new HashMap<String, ArrayList<MethodExecution>>();
  1112. HashMap<String, TracePoint> threadLastPoints = new HashMap<String, TracePoint>();
  1113. String traceLastThread = null;
  1114. long traceLastTime2 = 0;
  1115. String traceLastThread2 = null;
  1116. Statement st = before.getStatement();
  1117. if (st == null) {
  1118. st = before.getMethodExecution().getCallerTracePoint().getStatement();
  1119. }
  1120. ThreadInstance thread = threads.get(st.getThreadNo());
  1121. for (String threadId: threads.keySet()) {
  1122. ThreadInstance t = threads.get(threadId);
  1123. ArrayList<MethodExecution> rootExecutions = (ArrayList<MethodExecution>)t.getRoot().clone();
  1124. threadRoots.put(threadId, rootExecutions);
  1125. if (t == thread) {
  1126. traceLastThread = threadId;
  1127. threadLastPoints.put(threadId, before);
  1128. for (int n = rootExecutions.size() - 1; n >= 0; n--) {
  1129. MethodExecution root = rootExecutions.get(n);
  1130. if (root.getEntryTime() > before.getMethodExecution().getEntryTime()) {
  1131. rootExecutions.remove(n);
  1132. } else {
  1133. break;
  1134. }
  1135. }
  1136. if (rootExecutions.size() > 0) {
  1137. rootExecutions.remove(rootExecutions.size() - 1);
  1138. }
  1139. } else {
  1140. MethodExecution threadLastExecution = rootExecutions.remove(rootExecutions.size() - 1);
  1141. TracePoint threadBeforeTp = getLastMethodEntryInThread(rootExecutions, threadLastExecution.getExitOutPoint(), before.getMethodExecution().getEntryTime());
  1142. threadLastPoints.put(threadId, threadBeforeTp);
  1143. if (threadBeforeTp != null) {
  1144. long threadLastTime = threadBeforeTp.getMethodExecution().getEntryTime();
  1145. if (traceLastTime2 < threadLastTime) {
  1146. traceLastTime2 = threadLastTime;
  1147. traceLastThread2 = threadId;
  1148. }
  1149. }
  1150. }
  1151. }
  1152. return traverseStatementsInTraceBackwardSub(visitor, threadRoots, threadLastPoints, traceLastThread, traceLastThread2, traceLastTime2);
  1153. }
  1154.  
  1155. private TracePoint traverseStatementsInTraceBackwardSub(IStatementVisitor visitor,
  1156. HashMap<String, ArrayList<MethodExecution>> threadRoots,
  1157. HashMap<String, TracePoint> threadLastPoints,
  1158. String traceLastThread, String traceLastThread2, long traceLastTime2) {
  1159. // 全スレッドの同期をとりながら逆向きに実行文を探索する
  1160. for (;;) {
  1161. // 探索対象のスレッド内の逆向き探索
  1162. TracePoint lastTp = threadLastPoints.get(traceLastThread);
  1163. do {
  1164. if (lastTp.stepBackOver()) {
  1165. // そのスレッドの次のメソッド実行開始時点まで探索する
  1166. if (traverseStatamentsInCallTreeBackwardNoReturn(visitor, lastTp)) return lastTp;
  1167. } else {
  1168. // 呼び出し元に戻った場合
  1169. if (lastTp.isValid()) {
  1170. if (visitor.postVisitStatement(lastTp.getStatement())) return lastTp;
  1171. } else {
  1172. // 呼び出し木の開始時点まで探索し終えた場合
  1173. ArrayList<MethodExecution> root = threadRoots.get(traceLastThread);
  1174. while (!lastTp.isValid() && root.size() > 0) {
  1175. // 次の呼び出し木があればそれを最後から探索
  1176. MethodExecution lastExecution = root.remove(root.size() - 1);
  1177. lastTp = lastExecution.getExitPoint();
  1178. }
  1179. if (lastTp.isValid()) {
  1180. // 次の呼び出し木があればそれを最後から探索
  1181. threadLastPoints.put(traceLastThread, lastTp);
  1182. if (traverseStatamentsInCallTreeBackwardNoReturn(visitor, lastTp)) return lastTp;
  1183. } else {
  1184. // そのスレッドの探索がすべて終了した場合
  1185. threadLastPoints.put(traceLastThread, null);
  1186. break;
  1187. }
  1188. }
  1189. }
  1190. } while (lastTp.getMethodExecution().getEntryTime() >= traceLastTime2);
  1191. traceLastThread = traceLastThread2;
  1192. // 次の次に探索すべきスレッド(未探索の領域が一番最後まで残っているスレッド)を決定する
  1193. traceLastTime2 = 0;
  1194. traceLastThread2 = null;
  1195. boolean continueTraverse = false;
  1196. for (String threadId: threadLastPoints.keySet()) {
  1197. if (!threadId.equals(traceLastThread)) {
  1198. TracePoint threadLastTp = threadLastPoints.get(threadId);
  1199. if (threadLastTp != null) {
  1200. continueTraverse = true;
  1201. long threadLastTime = threadLastTp.getMethodExecution().getEntryTime();
  1202. if (traceLastTime2 < threadLastTime) {
  1203. traceLastTime2 = threadLastTime;
  1204. traceLastThread2 = threadId;
  1205. }
  1206. }
  1207. }
  1208. }
  1209. if (!continueTraverse && threadLastPoints.get(traceLastThread) == null) break;
  1210. }
  1211. return null;
  1212. }
  1213. /**
  1214. * before で指定したトレースポイント以前の同一呼び出し木内の全実行文を逆向きに探索する(ただし、visitor が true を返すまで)
  1215. * @param visitor ビジター
  1216. * @param before 探索の開始点(探索対象スレッドも指定している)
  1217. * @return true -- 探索を中断した, false -- 最後まで探索した
  1218. */
  1219. public boolean traverseStatementsInCallTreeBackward(IStatementVisitor visitor, TracePoint before) {
  1220. for (;;) {
  1221. if (traverseStatamentsInCallTreeBackwardNoReturn(visitor, before)) return true;
  1222. while (!before.stepBackOver()) {
  1223. if (!before.isValid()) break;
  1224. if (visitor.postVisitStatement(before.getStatement())) return true;
  1225. }
  1226. if (!before.isValid()) break;
  1227. }
  1228. return false;
  1229. }
  1230.  
  1231. /**
  1232. * before以前の呼び出し木を呼び出し先からの復帰をせずに行けるところまで逆向きに探索する
  1233. *
  1234. * @param visitor 実行文のビジター
  1235. * @param before 探索開始実行時点
  1236. * @return true -- 探索を中断した, false -- 復帰をしない限りこれ以上進めない
  1237. */
  1238. private boolean traverseStatamentsInCallTreeBackwardNoReturn(IStatementVisitor visitor, TracePoint before) {
  1239. for (;;) {
  1240. Statement statement = before.getStatement();
  1241. if (statement instanceof MethodInvocation) {
  1242. // メソッド呼び出し文の場合は、呼び出しの前後で preVisit と postVisit を別々に実行する
  1243. if (visitor.preVisitStatement(statement)) return true;
  1244. before.stepBackNoReturn();
  1245. if (!before.isValid()) {
  1246. // 呼び出し先のメソッドで実行文が記録されていない場合
  1247. before.stepBackOver();
  1248. if (visitor.postVisitStatement(statement)) return true;
  1249. if (before.isMethodEntry()) return false;
  1250. before.stepBackOver();
  1251. }
  1252. } else {
  1253. if (visitor.preVisitStatement(statement)) return true;
  1254. if (visitor.postVisitStatement(statement)) return true;
  1255. if (before.isMethodEntry()) return false;
  1256. before.stepBackNoReturn();
  1257. }
  1258. }
  1259. }
  1260. /**
  1261. * before で指定したトレースポイント以前の同一スレッド内の全メソッド実行を呼び出し木の中で逆向きに探索する(ただし、visitor が true を返すまで)
  1262. * @param visitor ビジター
  1263. * @param before 探索の開始点(探索対象スレッドも指定している)
  1264. * @return true -- 探索を中断した, false -- 最後まで探索した
  1265. */
  1266. public boolean traverseMethodExecutionsInCallTreeBackward(IMethodExecutionVisitor visitor, TracePoint before) {
  1267. ArrayList<MethodExecution> prevMethodExecutions = before.getPreviouslyCalledMethods();
  1268. for (int i = prevMethodExecutions.size() - 1; i >= 0; i--) {
  1269. MethodExecution child = prevMethodExecutions.get(i);
  1270. if (child.traverseMethodExecutionsBackward(visitor)) return true;
  1271. }
  1272. MethodExecution methodExecution = before.getMethodExecution();
  1273. if (visitor.postVisitMethodExecution(methodExecution, null)) return true;
  1274. TracePoint caller = methodExecution.getCallerTracePoint();
  1275. if (caller != null) {
  1276. if (traverseMethodExecutionsInCallTreeBackward(visitor, caller)) return true;
  1277. }
  1278. return false;
  1279. }
  1280.  
  1281. public static String getDeclaringType(String methodSignature, boolean isConstructor) {
  1282. if (methodSignature == null) return null;
  1283. if (isConstructor) {
  1284. String[] fragments = methodSignature.split("\\(");
  1285. return fragments[0].substring(fragments[0].lastIndexOf(' ') + 1);
  1286. }
  1287. String[] fragments = methodSignature.split("\\(");
  1288. return fragments[0].substring(fragments[0].lastIndexOf(' ') + 1, fragments[0].lastIndexOf('.'));
  1289. }
  1290. public static String getMethodName(String methodSignature) {
  1291. String[] fragments = methodSignature.split("\\(");
  1292. String[] fragments2 = fragments[0].split("\\.");
  1293. return fragments2[fragments2.length - 1];
  1294. }
  1295. public static String getReturnType(String methodSignature) {
  1296. String[] fragments = methodSignature.split(" ");
  1297. for (int i = 0; i < fragments.length; i++) {
  1298. if (!fragments[i].equals("public") && !fragments[i].equals("private") && !fragments[i].equals("protected")
  1299. && !fragments[i].equals("abstract") && !fragments[i].equals("final") && !fragments[i].equals("static")
  1300. && !fragments[i].equals("synchronized") && !fragments[i].equals("native")) {
  1301. return fragments[i];
  1302. }
  1303. }
  1304. return "";
  1305. }
  1306. public static boolean isNull(String objectId) {
  1307. return objectId.equals("0");
  1308. }
  1309. public static String getNull() {
  1310. return "0";
  1311. }
  1312.  
  1313. public static boolean isPrimitive(String typeName) {
  1314. if (typeName.equals("int")
  1315. || typeName.equals("boolean")
  1316. || typeName.equals("long")
  1317. || typeName.equals("double")
  1318. || typeName.equals("float")
  1319. || typeName.equals("char")
  1320. || typeName.equals("byte")
  1321. || typeName.equals("java.lang.Integer")
  1322. || typeName.equals("java.lang.Boolean")
  1323. || typeName.equals("java.lang.Long")
  1324. || typeName.equals("java.lang.Double")
  1325. || typeName.equals("java.lang.Float")
  1326. || typeName.equals("java.lang.Character")
  1327. || typeName.equals("java.lang.Byte")) return true;
  1328. return false;
  1329. }
  1330. }