读paper3-Katana: Dual Slicing-Based Context for Learning Bug Fixes

提出了一种基于程序切片的方法，其不是任意地将代码作为上下文包含进来，而是分析对错误语句具有控制或数据依赖关系的语句。利用代码的上下文和修复版本的上下文来捕获相关的修复要素。这里修复版本的上下文并不是指错误代码区的代码前缀与后缀，而是指的是与错误代码直接关联的代码块，无论是控制流还是数据流。

思路上还是基于变形的AST+图神经网络，同时通过上下文的切分尽可能减少冗余信息，通过修复版本的上下文为神经网络的学习提供更多信息。

项目开源在https://github.com/saltlab/Katana

问题引入

当前最先进的基于学习的程序修复方法以各种方式利用上下文，并且其中许多方法使用基于序列和树/图的源代码表示来学习程序修复。这些方法使用包含buggy语句的包围类、包围函数、buggy子树或整个文件来捕获buggy语句的上下文。然而，所有这些方法都对处理buggy语句设置了一个界限限制。基于序列的方法使用最大标记数限制（例如，1,000个标记），在这个范围内提取buggy方法或类，以避免截断的序列。类似地，当前基于图的学习技术对程序修复使用最大节点限制（例如，500个节点）。在实践中，我们不能指望真实世界的错误总是包含在小/中型方法中，或者限制在任意数量的标记或AST节点上。因此，这种定量约束可能导致一些与bug修复相关的重要信息被截断，整体上下文甚至可能失去语义意义。

我们的思路是，对于上下文，我们可以通过程序切片的概念来限制代码，而不是仅仅限制在包围实体或标记/节点数量上的任意限制。我们假设基于切片的上下文对于学习bug修复模式的机器学习模型是有帮助的。我们的技术名为Katana，它基于静态程序切片来获得与bug和其修复相关的上下文。然后，将这个获得的切片上下文表示为增加了控制流和数据流边的AST图。然后将这个图输入到图神经网络（GNN）进行训练。

图1描绘了我们方法的概述。我们的整体方法包括五个主要步骤，即数据收集、程序切片、图表示、训练和推理。接下来，我们描述每个步骤。（宽虚线框标识的四部分）

本文样例：开发者注意到属性currentUser调用了对service的函数调用。在查看函数声明后，他们注意到service需要一个必需的user参数，并且有错误的行没有传递任何参数。开发者确定了错误的原因，并通过将在第12行声明的缺失参数user传递给函数调用来生成修复。

数据收集

爬虫，爬取思路还是挺有意思：

我们认为一个AST节点的差异就是一个bug，如果只有一个AST节点在有bug的树和修复后的树之间被添加、删除或修改，那么我们认为数据点之间存在一个节点的差异。我们通过以下步骤提取这些数据点：

• 使用SHIFT AST2解析器生成每个数据点的有bug和已修复文件的AST
• 仅选择那些两个AST之间的差异等于一个的数据点。

我们还使用SHIFT AST解析器剪枝掉任何无法解析的JavaScript数据点。如果一个JavaScript文件存在不完整的闭包，例如缺少大括号或括号，我们使用解析器来检查是否可以生成AST。

程序切片 Static Program Slicing

使用后向切片作为上下文，它是相对于切片准则 $(p,V)$ 的所有具有数据或控制依赖关系的语句的子集，其中切片准则是有问题的程序点 $p$ 处的变量集合 $V$。

我们对数据集中的每个数据点进行分析，收集必要信息进行切片分析。为了确定切片准则，我们首先对有错误和修复的行进行差异分析，以获得有错误的行号。然后，我们将该行号输入到我们的切片框架中，并提取该行中使用的变量和函数调用。为了通过静态后向切片提取上下文语句，我们结合了控制流和数据流分析，并在适用的情况下识别切片语句。

算法1概述了从给定行号 $N$ 和文件 $file$ 中提取上下文的步骤。具体来说，算法1从给定的有错误或修复的行中提取Entity实体（即变量、函数、对象）。算法1遍历所有实体，使用后向切片（backward slice）分析获取所有的 $contextLines$。$contextLines$ 是切片上下文的行号集合。在 $BackwardSlice$ 函数中，算法1遍历给定实体中的所有引用；如果引用的实体是控制流或数据依赖的，那么相应的行被添加到 $contextLines$；该过程递归地进行，以获取引用实体的后向切片。最后，算法生成从 $contextLines$ 构造的源代码语句，以返回输出。

此处，$getStatements$ 函数确保正确提取给定上下文行的所有闭包，因为在JavaScript这样的动态语言中，这是一个具有挑战性的过程。例如，与Java不同，JavaScript中的声明或表达式语句不需要分号；在这种情况下，我们将换行符视为语句的结束。有些情况下，有错误的行位于循环或条件语句中。对于这种有错误的语句，我们通过控制流分析确定闭包，以避免通过后向切片获得不完整的上下文。

我们提取的有错误和修复的文件的数据点包含了完整的JavaScript代码，只有错误和在相同错误行处的修补程序的差异。

单一切片

单一切片用于提取与错误行有关的上下文。我们首先以错误行作为切片准则，捕获后向切片（backward slice）语句作为上下文。这生成了一个只包含后向切片语句的错误文件作为上下文。然后我们将这个错误文件的上下文附加到正确的行上，并生成修复版本的错误文件。我们称之为单一切片，因为只在错误文件上应用了后向切片，并且错误文件的上下文只是简单地转移到了修复文件上。

列表3和4展示了单一切片错误和修复文件的代码片段。由于切片准则是错误行，修复文件包含与错误文件相同的切片上下文，并且不包含有关已作为修复传递的变量user的信息。

双重切片

修复后的上下文中存在一些修复成分，它们可以改善整个学习过程。双重切片分析旨在分别从错误和修复文件中提取上下文，为模型提供附加的语义信息。通过使用错误行和修复行的切片准则，我们分别从这两行中提取切片语句，生成切片的错误和修复文件。

列表3和5展示了错误和修复文件。在这种方法中，切片准则是错误行和修复行，修复文件包含了额外的行，其中包含了在第10行上对变量user的声明，这对于生成修补程序是必要的，因为函数service需要此参数。

图表示 Graph Representation

通常，程序的抽象语法树(AST)被用作程序图的主干，该图由编程语言语法的语法非终结符和终结符组成。通过不同类型的边缘，图形能够利用节点之间的句法和语义关系。它们还能够通过边缘考虑远程依赖，即使这些变量或函数位于不同的位置。

对于每个数据点，我们分别为有问题和修复后的切片文件创建图形。我们提取了每个切片文件的AST，并将其转换为图形，通过添加SuccToken边缘连接叶节点和ValueLink边缘连接附加值节点。图1展示了我们示例切片的有问题和修复后的图形。表示源代码为图形后，我们使用图神经网络（GNN）将结果图形映射为向量表示。具体而言，给定一个图形 $g=(V,E)$，其中 $V$ 是节点集合，$E$ 是边集合，我们使用函数 $f(g)\rightarrow(\mathbb R ^d,\mathbb R^{|V|\times d})$ 确定图形 $g$ 和个体节点 $v\in V$ 的 $d$ 维度表示。节点嵌入是一个向量，$\vec v=h_v^{(L)}$，其中 $L$ 表示通过消息传递在 GNN 中的总传播数。消息传递在 GNN 模型中使用，其中向量消息在图中的节点之间交换并通过聚合函数进行更新。图形表示 $\vec g$ 是节点嵌入 $h_v^l,\forall l\in 0,1,\dots,L$ 的聚合，对于每个 $l$，使用最大池化来计算平均的 $L+1$ 个向量以获得 $\vec g$。

训练

为了训练一个模型，我们采用了一个GNN架构，将图表示映射到一个固定维度的向量空间中。程序修复本质上是一系列图转换操作，从有错误的图到修复后的图，包括添加或删除节点，替换节点值或节点类型等操作。在图创建步骤中，为每个数据点生成了有错误的图 ($g_{bug}$)、修复后的图 ($g_{fix}$) 以及用于创建 $g_{fix}$ 的相应图编辑序列，即图差异。换句话说，模型通过将图编辑操作应用于有错误的行上的有错误的图（$g_{bug}$）来创建 $g_{fix}$。这个图差异包含了一系列AST修改，作为一个细粒度的监督机制来进行图转换。修改包含图编辑操作的类型、节点在图中的位置和要添加/修改的值（删除操作时不提供值）。总之，给定一个数据集 $D=\{(g_{bug}^{(i)},g_{fix}^{(i)})\}_{i=1}^{|D|}$ ，其中包含有错误的和修复过的切片代码对，模型通过学习目标 $max_\theta \mathbb E_{(g_{bug},g_{fix})\sim D}\,p(g_{bug}|g_{fix};\theta)$ 来最大化修复的可能性。最大似然估计（MLE）目标函数是在每个图编辑步骤上的交叉熵损失的总和。

对于单一切片，GNN模型的输入是有错误的图 $g_{bug}$，其中只包含与有错误行相关的切片上下文。模型的输出是应用于 $g_{bug}$ 的有错误节点上的图编辑操作，从而得到修复后的图 $g_{fix}$。

对于双重切片，模型的输入是有错误的图 $g_{bug}$，其中包含与有错误行和修复行相关的切片上下文。输出与之前的情况相同，即应用于 $g_{bug}$ 中有错误节点的图编辑操作。简而言之，使用双重切片的上下文进行训练的模型可以访问与错误和修复两者相关的额外上下文信息。

Note that, we do not differentiate the buggy or fixed graph input to the model based on any particular bug type, and feed the data as is.

结果评估

RQ1：双切片与单切片在学习修复方面有何区别？

双切片实现了更高的准确率。Top-1，3，5指的是beam size为1、3和5

RQ2：Katana与最新的基于学习的修复技术相比如何？

Katana对于所有的beam size都优于现有的技术。

RQ3：切片对于获得上下文信息有何影响？

我们对我们的切片技术进行了定量分析，以衡量所考虑的上下文的类型和数量，并将其与其他方法进行比较。我们在程序切片分析期间对我们的数据集进行了统计。我们计算了切片前后的行数以及经过控制流和数据流分析的数据点的比例。我们发现，26.96%的总数据点（113,975对有错误和修复的文件）需要同时使用控制流和数据流分析来生成切片。其余的73.04%仅通过数据流分析进行了切片。图3显示了数据点在切片前后的行数。在这里，我们将切片前的数据集称为未切片的数据集。Katana的程序切片将需要考虑的上下文的平均行数从39条减少到15条。中位数也从33条减少到9条。切片前的最大行数为1,087行，切片后减少到636行，而最小行数在两种情况下均为1。

Limitations

一个明显的问题是仅针对JS进行的训练。

Katana无法从被压缩或混淆的JavaScript代码中生成切片。压缩步骤会移除空白字符、混淆变量名，并且通常产生单行输出。因此，我们在数据集中排除了被压缩的JavaScript文件，因为它们可能会在学习过程中引入噪音。然而，在实际应用中，这些被压缩或混淆的代码在部署到生产环境之前会执行该压缩步骤，并且这些代码并不供人类阅读。因此，压缩或混淆的代码不会限制Katana的适用性。

JavaScript是一种动态类型语言，这本质上使得在程序切片期间难以跟踪控制和数据流依赖关系。在控制和数据流分析无法获得切片上下文的情况下，我们将整个文件内容视为有错误的行的上下文范围。

目前的Katana实现不支持生成多行补丁。由于我们的数据集只包含一个AST节点的差异，我们使用单行作为切片准则来提取上下文语句。然而，从概念上讲，我们可以扩展程序切片的概念来修复多行错误。

我们使用了跨程序和内部程序的后向切片分析，但限定了JavaScript文件的程序分析范围。之所以选择这种方式，是因为我们的数据收集是基于提交而不是项目；这种方法不能确保所有依赖文件都包含在提交中。此外，由于我们使用的切片框架（Understand）仅支持文件内的静态分析，因此我们的JavaScript切片器受到此限制的约束。然而，根据之前的研究，大部分修复的关键在于包含错误的文件中。正如第5.3节中讨论的那样，Katana修复错误的能力受到词汇的可用性的限制。如果修复错误需要替换一个节点或添加一个节点，则该节点值需要在词汇字典中存在。增加词汇量可能会提高Katana在修复错误时的性能。

我们使用了后向切片分析，这可能会导致在别名期间遗漏一些相关的上下文语句。别名是指多个变量引用内存中的同一位置。某些错误可能在更新变量的别名时发生，而这会改变原始变量。由于这些错误可能发生在有错误的行之后，前向切片可以帮助捕获相关的上下文语句。在未来的工作中，可以将前向切片支持纳入Katana中以处理这种错误模式。

项目复现

数据收集

data-collection文件夹下，根据readme，依次

• Run npm install
• Download JS repositories using node download_repos.js
• Install packages pip install -r requirements.txt
• Mine commits from the downloaded repositories using python commitminer.py

注意点：

• nodejs某些版本在win11下执行npm install会爆[nodegit] ERROR - finished with error code: Error: spawn EINVAL

  • 解决方案就是换个老点的版本，比如https://nodejs.org/dist/v14.17.3/

• node download_repos.js会down 39G 的仓库，准备好硬盘空间

• commitminer.py第19行会爆warning，改为如下：

match = re.findall('\\d+|\\D+', identifier)

• commitminer.py第207行会爆：

Traceback (most recent call last):
  File "path\data-collection\commitminer.py", line 216, in <module>
    createRepositoriesList()
  File "path\data-collection\commitminer.py", line 94, in createRepositoriesList
    traverseCommits(repos)
    ^^^^^^^^^^^^^^^^^^^^^^
  File "path\data-collection\commitminer.py", line 207, in traverseCommits
    f.write(m.source_code)
UnicodeEncodeError: 'gbk' codec can't encode character '\ufeff' in position 0: illegal multibyte sequence

改为utf-8并忽略无法编码的字符：

f = open(newFile, "w+",encoding='utf-8', errors='ignore')
f.write(m.source_code)
f.close()
f = open(oldFile, "w+",encoding='utf-8', errors='ignore')

• 可能存在某些仓库无法被down，导致执行python commitminer.py爆文件路径不存在，122行处修改如下：

repo_path = 'repositories/' + repo.address

if os.path.exists(repo_path):
    for commit in RepositoryMining(repo_path, only_no_merge=True, only_modifications_with_file_types=['.js']).traverse_commits():
        # code......
else:
    print(f"The path {repo_path} does not exist.")

程序切片

需要这个Understand by Scitools的api，学生貌似可以申免费，但我没申下来

破解来自：https://blog.csdn.net/weixin_48220838/article/details/131297065

understand.exe用不到，可以不用破解

1. 正常安装，设置自己的安装路径

2. 找到自己安装目录下的 bin文件夹 找到可执行程序understand.exe，复制一份到桌面

3. 打开HxD(好兄弟)软件，然后使用他打开刚刚复制的exe文件好兄弟下载链接 : Downloads | mh-nexus

4. 按下Ctrl+F 以文本方式 搜索"areYouThere" ， 用"IamNotHere!" 替代。（都不带引号）

5. 以字节序列模式搜索"45 33 FF 41 0F B6 C6 48 3B DF 44 0F 4E F8"，替换为"41 BF 01 00 00 00 90 90 90 90 90 90 90 90"

6. Ctrl+S保存退出，然后将刚刚修改的在桌面上的文件，拖到之前的bin文件替换原有的exe即可

后面用到的und，upython要破解，找到自己安装目录下的 bin文件夹 找到可执行程序，其余同上

省流步骤：

• 使用python partition.py --dir=path --num_files=10000 来划分子目录，其中path是需要划分的文件目录

• 编辑 und undCommands.txt ，将路径改为自己项目的文件夹路径，并运行 und undCommands.txt 创建 .und 数据库

  • 这个文件夹内容可能看起来很少（就两个，且很小），不必担心

• 使用脚本 python generate-file-info.py --path=<data-dir> 生成 CSV 文件

• 运行upython backward-slice.py multiple True dir1 dir2 dir3 进行切片

  • 这个过程最大内存需求可能在22G左右，可能会更多
  • 很耗时，可以同步准备后面训练的环境

• 使用脚本 node prune-unparsable-files.js <path-to-unsliced-folder> <path-to-sliced-folder> dual 剪除未完全切片的文件

---

原文如下，略有改动：

预处理

• backward-slice.py 中的切片函数需要三样东西：

  • 一个包含有错误和修复文件对的目录。
  • 该目录中的 .und 数据库。这基本上是该目录中所有文件的 Understand 数据库。请注意，understand 无法处理包含超过 10,000 对文件的文件夹，因此最好将整个数据集分割成包含 10,000 对文件的多个子目录。使用 partition.py 脚本将根目录分块为多个包含 10,000 对文件的子目录。
  • 使用python partition.py --dir=path --num_files=10000 来划分，其中path是需要划分的文件目录
  • 一个包含有错误行、修复行、有错误行号的 CSV 文件。即生成的commits.csv

• 对于这些目录中的每一个，通过编辑并运行 und undCommands.txt 创建 .und 数据库。可以在命令txt中添加更多目录块。

• 如果您使用的是 Linux，在终端中应该可以通过 upython 使用 understand 命令行。在 Mac 上，您需要将 upython 可执行文件的路径添加到应用程序文件夹中。

• 使用脚本 python generate-file-info.py --path=<data-dir> 生成 CSV 文件。确保在 --path 中传递所有在understand处理中创建的文件夹块。这将在每个子目录中创建 .csv 文件。

运行切片器

• upython backward-slice.py multiple True dir1 dir2 dir3

  • multiple 表示将对包含文件有错误和修复文件的多个目录进行切片。如果您只想在一个文件夹中执行操作，请使用 single。如果您只想测试切片器（进行健全性检查），请运行 upython backward-slice.py test True
  • 这里的 True 表示启用双重切片。False 将进行单一切片。
  • dir是所有要进行切片的文件夹
  • upython其实调用的是understand内置的python解释器

  • upython也要破解，找到自己安装目录下的 bin文件夹 找到可执行程序upython.exe，其余同上

• 运行切片器后，您需要使用脚本 node prune-unparsable-files.js <path-to-unsliced-folder> <path-to-sliced-folder> dual 剪除我们未完全切片的文件。

---

一些代码问题

generate-file-info.py

主要是一些操作系统不兼容的问题

首先，win需要将所有"/“替换为”\\"

其次，可能出现csv为空的情况，说明有报错。

• 报错module 'mmap' has no attribute 'PROT_READ'，来自函数第25行，win可改为m = mmap.mmap(f.fileno(), 0, access=mmap.ACCESS_READ)

• 报错'mmap.mmap' object has no attribute 'madvise'，win没有这个系统调用，注释掉即可

win可运行代码如下

import difflib
import datetime
import csv
import sys
from os import listdir
from os.path import isfile, join
from concurrent.futures import ThreadPoolExecutor
import mmap
import queue

def produce(i, mypath, item):
    # Data processing goes here; row goes into queue
    print('processing item {} - file prefix {}'.format(i, item[0]))
    data = generate_file(mypath, item)
    queue.put(data)
    print('submitted to queue item {}'.format(i))

def bin2str(text, encoding='utf-8'):
    return text.decode(encoding)

def mmap_io(mypath, filename):
    lines = []
    try:
        with open(mypath + '\\' + filename, "rb", buffering=0) as f:
            m = mmap.mmap(f.fileno(), 0, access=mmap.ACCESS_READ)
            # m.madvise(mmap.MADV_SEQUENTIAL)
            while True:
                line = m.readline()
                if line:
                    if len(line) > 180:
                        print('Large lines in file {} --- Skipping!!'.format(filename))
                        return []
                    lines.append(bin2str(line))
                else:
                    break
            m.close()
    except Exception as e:
        print(e)
        lines = []
    return lines

def find_diff(mypath, fileAName, fileBName):
      try:
        # fileA = open(mypath + '/' + fileAName, "rt", encoding="utf-8").readlines()
        fileA = mmap_io(mypath, fileAName)
        # fileB = open(mypath + '/' + fileBName, "rt", encoding="utf-8").readlines()
        fileB = mmap_io(mypath, fileBName)
      except Exception as e:
        print(e)
        return None, None, None

      if len(fileA) != len(fileB) or len(fileA) == 0 or len(fileB) == 0:
            return None, None, None
      d = difflib.Differ()
      diffs = d.compare(fileA, fileB)
 
      lineNum = 0

      final_line_num = None
      patch_line = None
      buggy_line = None

      for line in diffs:
            code = line[:2]
            # print(code)
            # if the  line is in both files or just b, increment the line number.
            if code in ("  ", "+ "):
                  lineNum += 1
            # if this line is only in b, print the line number and the text on the line
            if code == "- ":
                  buggy_line = line[2:].strip('\n').strip()
            if code == "+ ":
                  final_line_num = lineNum
                  patch_line = line[2:].strip('\n').strip()
            
      return final_line_num, patch_line, buggy_line


def is_whitespace_diff(buggy_line, fixed_line):
  output_list = [li for li in difflib.ndiff(fixed_line, buggy_line) if li[0] != ' ']
  if len(output_list):
    return all(f.strip() in ['+', '-'] for f in output_list)
  return False


def _get_prefix(filename):
    if filename.endswith('_babel.js'):
            return filename.split('_buggy_babel.js')[0] if '_buggy_babel.js' in filename else filename.split('_fixed_babel.js')[0]
    if filename.endswith('_buggy.js') or filename.endswith('_fixed.js'):
            return filename.split('_buggy.js')[0] if '_buggy.js' in filename else filename.split('_fixed.js')[0]

def generate_file(mypath, item):
    time_start = datetime.datetime.now()
    line_num, fixed_line, buggy_line = find_diff(mypath, item[1]['buggy_file'], item[1]['fixed_file'])
    if line_num and not is_whitespace_diff(buggy_line, fixed_line):
        time_elapsed = datetime.datetime.now() - time_start
        print('Elapsed time in seconds for file {}:'.format(item[0]), time_elapsed.seconds)
        data = [item[1]['buggy_file'], item[1]['fixed_file'], line_num, buggy_line, fixed_line]
        return data

def get_file_info(mypath):
    # blacklisted_prefixes = {}
    # with open('./bugs_info.csv', 'r', encoding="ISO-8859-1") as csv_file:
    #     csv_reader = csv.reader(csv_file, delimiter=',')
    #     for row in csv_reader:
    #         print(row)
    #         if len(row):
    #             if row[0] == 'Buggy file':
    #                 continue
    #             prefix = _get_prefix(row[0])
    #             blacklisted_prefixes[prefix] = True

    onlyfiles = [f for f in listdir(mypath) if isfile(join(mypath, f)) and f.endswith('.js')]

    file_map = {}
    for file in onlyfiles:
        prefix = _get_prefix(file)
        if 'xml' in file:
            continue

        if '_buggy' in file:
                if prefix not in file_map:
                    file_map[prefix] = {
                            'buggy_file': file
                    }
                else:
                    file_map[prefix]['buggy_file'] = file
        elif '_fixed' in file:
                if prefix in file_map:
                    file_map[prefix]['fixed_file'] = file
                else:
                    file_map[prefix] = {
                            'fixed_file': file
                }

    print('Number of datapoints', len(file_map))
    return file_map

def init_queue(queue):
    globals()['queue'] = queue

import argparse
parser = argparse.ArgumentParser()
parser.add_argument(
    '--path', help='Folder path of files', required=False)

if __name__ == '__main__':
    args = parser.parse_args()
    path = args.path

    print('start loading file info')
    file_map = get_file_info(path)
    print('done loading file_info')

    time_start = datetime.datetime.now()
    queue = queue.Queue()
    with ThreadPoolExecutor(max_workers=10,
                            initializer=init_queue,
                            initargs=(queue,)) as executor:
        print('produce items')
        for i, item in enumerate(file_map.items()):
            executor.submit(produce, i, path, item)

    print('done producing items')
    print('queue size:{}'.format(queue.qsize()))
    with open(path + '\\' + '{}_bugs_info.csv'.format(path.split('\\')[-1]), 'w', encoding='utf-8', newline='') as f:
        writer = csv.writer(f)
        while not queue.empty():
            data = queue.get()
            if data:
                writer.writerow(data)

    time_elapsed = datetime.datetime.now() - time_start
    print('Elapsed time in seconds {} to run the script:'.format(time_elapsed.seconds))

backward-slice.py

有很多文件读写时没有规定编码导致的报错，以及前文提到的不同os的路径分隔符问题

win可用代码：

import understand
import traceback
import csv
import json
import sys
import os
from difflib import get_close_matches, ndiff
import concurrent.futures

csv.field_size_limit(1000000)
REL_KIND = ['web Javascript Definein', 'web Javascript Setby', 'web Javascript Modifyby']


def safe_list_get(arr, idx):
    try:
        return arr[idx]
    except IndexError:
        return None


def get_patch_from_diff(diff):
    buggy_line = None
    fixed_line = None
    for line in diff.split('\n'):
        if line.startswith('-'):
            buggy_line = line.lstrip('-')
        elif line.startswith('+'):
            fixed_line = line.lstrip('+')
    return buggy_line, fixed_line


class BackwardSlicing(object):
    def __init__(self, db, file, buggy_line_num) -> None:
        self.file = file
        self.db = db
        self.buggy_line_num = buggy_line_num
        self.method_lines = []
        self.loops = {}
        self.conds = {}
        self.conditional_scope = {}
        self.statement_closure = {}
        self.scope = {}
        self.method_start_line_num = -1
        self.function_variables = []
        self.has_function_call = False
        self.else_lines = set()

        for lexeme in file.lexer():
            if lexeme.line_begin() == buggy_line_num:
                if lexeme.token() == 'Identifier' and lexeme.ent() and lexeme.ent().parent() and lexeme.ent().parent().kindname() in [
                    'Function', 'Class', 'File']:
                    lines = set()
                    for ref in lexeme.ent().parent().refs():
                        if not self.method_start_line_num:
                            self.method_start_line_num = ref.line()
                        if ref.kind().longname() not in ['web Javascript Callby Nondynamic', 'web Javascript Useby',
                                                         'web Javascript Useby Deref Partial']:
                            lines.add(ref.line())
                    self.method_lines = sorted(lines)
                    break

    def _get_outermost_parent(self, first_line):
        for lexeme in self.file.lexer():
            if lexeme.line_begin() == first_line and lexeme.token() not in ['Whitespace', 'Newline']:
                if lexeme.ent() and lexeme.ent().parent():
                    if lexeme.ent().parent().kindname() == 'File':
                        return None
                    elif lexeme.ent().parent().kindname() != 'File':
                        return lexeme.ent().parent().refs()[0].line()
                return None

    # For cases when the . goes to next line, for example,
    # array
    #  .find(a => a !== 2)
    #  .map(a => a + 1)
    def _get_object_beginning(self, line_number):
        for lexeme in self.file.lexer():
            if lexeme.line_begin() == line_number:
                if lexeme.token() not in ['Whitespace', 'Newline']:
                    if lexeme.text() == '.' and lexeme.previous().token() == 'Whitespace':
                        return self._get_object_beginning(line_number - 1)
                    else:
                        return line_number

                        # Find all variables in the line

    def get_variable_entities(self, line_number):
        variables = []
        for lexeme in self.file.lexer():
            if lexeme.line_begin() == line_number:
                if lexeme.token() == 'Identifier' and lexeme.ent():
                    variables.append(lexeme.ent())
                if lexeme.ent() and lexeme.ent().kindname() == 'Property':
                    variables.append(lexeme.ent().parent())

        return variables

    def is_within_loop(self, line_num):
        loop_lines = []
        for i in self.loops.items():
            if i[1].get('line_num_begin') and i[1].get('line_num_end') and line_num:
                if line_num >= int(i[1]['line_num_begin']) and line_num <= int(i[1]['line_num_end']):
                    loop_lines.append((i[1]['line_num_begin'], i[1]['line_num_end']))
        return loop_lines

    def is_within_scope(self, line_num):
        scope_lines = []
        for i in self.scope.items():
            if i[1].get('line_num_begin') and i[1].get('line_num_end') and line_num:
                if line_num >= int(i[1]['line_num_begin']) and line_num <= int(i[1]['line_num_end']):
                    scope_lines.append((i[1]['line_num_begin'], i[1]['line_num_end'], i[1]['is_variable']))
        return scope_lines

    def is_within_conditional(self, line_num):
        cond_lines = []
        for i in self.conds.items():
            if i[1].get('line_num_begin') and i[1].get('line_num_end') and line_num:
                if line_num >= int(i[1]['line_num_begin']) and line_num <= int(i[1]['line_num_end']):
                    cond_lines.append((i[1]['line_num_begin'], i[1]['line_num_end']))
                    if 'else' in i[0]:
                        self.else_lines.add(i[1]['line_num_begin'])
        return cond_lines

    def find_conditional_by_else(self, lines):
        updated_lines = lines.copy()
        common_lines_between_current_and_else_lines = self.else_lines.intersection(lines)
        for line_num in common_lines_between_current_and_else_lines:
            for cond_type_line_map in self.conditional_scope.values():
                if 'else' in cond_type_line_map:
                    last_index = len(cond_type_line_map['else']) - 1
                    for idx, val in enumerate(cond_type_line_map['else']):
                        if val['line_num_begin'] == line_num:
                            start_if = cond_type_line_map['if']['line_num_begin']
                            if start_if not in lines:
                                c = start_if
                                while c < line_num:
                                    updated_lines.add(c)
                                    c += 1
                            if idx == last_index and cond_type_line_map.get('endif'):
                                updated_lines.add(cond_type_line_map['endif']['line_num_begin'])

        return updated_lines

    def on_add_line(self, line_numbers):
        def _on_add(line_num):
            is_within_loop = self.is_within_loop(line_num)
            is_within_conditional = self.is_within_conditional(line_num)
            is_within_scope = self.is_within_scope(line_num)
            new_lines = set()

            if len(is_within_loop):  # if a line is start of the loop, add the end of the loop (curly brace)
                for l in is_within_loop:
                    new_lines.add(l[0])
                    new_lines.add(l[1])
            if len(is_within_conditional):  # if a line is start of the loop, add the end of the loop (curly brace)
                for l in is_within_conditional:
                    new_lines.add(l[0])
                    new_lines.add(l[1])
            if len(is_within_scope):  # if a line is start of the scope, add the end of the scope (curly brace)
                for l in is_within_scope:
                    new_lines.add(l[0])
                    i = l[0]
                    if l[2]:
                        while i <= l[1]:
                            new_lines.add(i)
                            i += 1
                    else:
                        new_lines.add(l[1])
            return new_lines

        if type(line_numbers) is set:
            updated_set = set()
            for l in line_numbers:
                updated_set = _on_add(l).union(updated_set)
            return updated_set
        else:
            return _on_add(line_numbers)

    def get_statements(self, lines):
        statements = []
        line_to_col_map = {}  # stores the lines where some parts of the line needs to be included (not the whole line)
        updated_lines = lines.copy()

        for line_num in lines:
            key = str(line_num)

            if self.has_function_call and line_num in self.function_variables:  # for variables that are function calls, get the whole scope of the function
                if key in self.scope and self.scope[key] is not None:
                    i = line_num
                    while i < self.scope[key].get('line_num_begin'):
                        updated_lines.add(i)
                        i += 1

            updated_lines = self.on_add_line(line_num).union(updated_lines)

            if key in self.conds and self.conds[key][
                'line_num_end']:  # if a line is start of a conditional, add the end of the loop (curly brace)
                line = self.conds[key]['line_num_end']
                updated_lines.add(line)
                if self.conds[key].get(
                        'column_num_begin') and line not in line_to_col_map:  # this takes care of the column end
                    line_to_col_map[line] = {
                        'column_num_begin': self.conds[key]['column_num_begin'],
                        'column_num_end': self.conds[key]['column_num_end']
                    }
            if key in self.scope and self.scope[key] is not None and 'line_num_end' in self.scope[
                key]:  # if a line falls within a method scope, add the end of the line to the list
                line = self.scope[key]['line_num_end']
                updated_lines.add(line)
                if self.scope[key].get('column_num_begin') and self.scope[key].get(
                        'column_num_end') and line not in line_to_col_map:  # this takes care of the column end
                    line_to_col_map[line] = {
                        'column_num_begin': self.scope[key]['column_num_begin'],
                        'column_num_end': self.scope[key]['column_num_end']
                    }
                updated_lines.add(self.scope[key]['line_num_end'])

                # check if the lines fall within an if block, then add the else blocks too
            for i in self.conds:
                block_start = int(i.split('_')[-1]) if i.startswith('else_') else int(i)
                if int(line_num) >= block_start and int(line_num) <= int(self.conds[i]['line_num_end']):
                    updated_lines.add(block_start)
                    updated_lines.add(self.conds[i]['line_num_end'])
                    if self.conds[i].get('column_num_end'):
                        if block_start in line_to_col_map:
                            del line_to_col_map[block_start]
                        else:
                            line_to_col_map[self.conds[i]['line_num_end']] = {
                                'column_num_begin': self.conds[i]['column_num_begin'],
                                'column_num_end': self.conds[i]['column_num_end']
                            }

            # this takes care of single line statement end
            for statement_continuations in self.statement_closure.values():
                if line_num in statement_continuations:
                    for s in statement_continuations:
                        updated_lines.add(s)
                        updated_lines = self.on_add_line(s).union(updated_lines)

        updated_lines = set(sorted([i for i in updated_lines if i]))
        if int(self.method_start_line_num) in updated_lines:
            updated_lines.add(self.method_lines[-1])
            updated_lines = self.on_add_line(self.method_lines[-1]).union(updated_lines)

        # this takes care of object start
        start_of_line = None
        for line_num in list(updated_lines.copy()):
            for lexeme in self.file.lexer():
                if lexeme.line_begin() == line_num:
                    if lexeme.text() == '.' and lexeme.previous().token() == 'Whitespace':
                        start_of_line = self._get_object_beginning(line_num - 1)

                        if start_of_line:
                            updated_lines.add(start_of_line)
                            updated_lines = self.on_add_line(start_of_line).union(updated_lines)
                            start_of_line = None

        parent_line = self._get_outermost_parent(min(updated_lines))
        if parent_line and self.scope.get(str(parent_line)):
            updated_lines.add(parent_line)
            end_line = self.scope[str(parent_line)].get('line_num_end')
            if end_line:
                updated_lines.add(end_line)

        lines_with_related_vars = self.get_related_var_lines(set(updated_lines), set(updated_lines), show_use_by=True)

        unified_lines = self.on_add_line(lines_with_related_vars.difference(updated_lines)).union(
            lines_with_related_vars)
        final_lines = self.find_conditional_by_else(unified_lines)
        updated_lines = sorted([i for i in final_lines if i])

        for line_num in updated_lines:
            statement = ''
            for lexeme in self.file.lexer():
                if lexeme.line_begin() == line_num:
                    if lexeme.token() not in ['Newline']:
                        if line_num in line_to_col_map:
                            if lexeme.column_end() <= line_to_col_map[line_num]['column_num_end']:
                                statement += lexeme.text()
                        else:
                            statement += lexeme.text()

            statements.append(statement.rstrip())

        return statements

    def analyze_closure(self):
        self._record_scope()
        self._record_conditional_scope()
        for line_num in self.method_lines:
            for lexeme in self.file.lexer():
                if lexeme.line_begin() == line_num:
                    if lexeme.token() not in ['Whitespace', 'Newline']:
                        if lexeme.token() == 'Keyword' and lexeme.text() in ['for', 'while']:
                            self._record_loop_closure(lexeme, line_num)
                        elif lexeme.text() == 'if':
                            self._record_if_closure(lexeme, line_num)
                            self._record_else_closure(lexeme)
                    self._record_line_closure(lexeme, line_num)

    def _record_line_closure(self, lexeme, line_num):
        line_key = str(line_num)
        if line_key not in self.statement_closure:
            self.statement_closure[line_key] = []
            while lexeme and lexeme.line_begin() < (self.method_lines[-1] + 1) and lexeme.line_begin() > \
                    self.method_lines[0]:
                if lexeme.text() in ['{', '}', 'if', 'else', 'while', 'try',
                                     'catch'] and lexeme.line_begin() == line_num:
                    del self.statement_closure[line_key]
                    break

                if lexeme.text() == ';':
                    self.statement_closure[line_key] = list(range(line_num, lexeme.line_begin() + 1))
                    break
                lexeme = lexeme.next()

    def _record_scope(self):
        brace_map = {'{': '}', '[': ']', '(': ')'}
        stack = []
        line_stack = []
        is_variable = {}
        for lexeme in self.file.lexer():
            line_key = str(lexeme.line_begin())
            if lexeme.token() == 'Keyword' and lexeme.text() == 'function':
                self.function_variables.append(lexeme.line_begin())
            if lexeme.ent() and lexeme.ent().kindname() == 'Variable' and lexeme.ent().type() in ['{}', '[{}]', '[]']:
                is_variable[line_key] = True
            if lexeme.text() in ['{', '(', '[']:
                stack.append(lexeme.text())
                line_stack.append(line_key)
                self.scope[line_key] = {
                    'is_variable': is_variable.get(line_key, False),
                    'line_num_begin': lexeme.line_begin(),
                    'column_num_begin': lexeme.column_begin(),
                }

            elif lexeme.text() in ['}', ']', ')']:
                if stack and brace_map[stack[-1]] == lexeme.text():
                    self.scope[line_stack[-1]]['line_num_end'] = lexeme.line_begin()
                    if lexeme.next() and lexeme.next().next() and lexeme.next().token() == 'Newline' and lexeme.next().next().token() != 'Indent':
                        self.scope[line_stack[-1]]['column_num_end'] = lexeme.column_end()

                    stack.pop()
                    line_stack.pop()

    def _record_loop_closure(self, lexeme, line_num):
        loop_key = str(line_num)
        self.loops[loop_key] = {
            'line_num_begin': line_num,
            'line_num_end': line_num,
            'enclosing_brace_count': 0
        }
        while lexeme and lexeme.line_begin() < self.method_lines[-1]:
            if lexeme.text() == '{':
                self.loops[loop_key]['enclosing_brace_count'] += 1
            if lexeme.text() == '}' and self.loops[loop_key]['enclosing_brace_count'] > 0:
                self.loops[loop_key]['enclosing_brace_count'] -= 1
                if self.loops[loop_key]['enclosing_brace_count'] == 0:
                    self.loops[loop_key]['line_num_end'] = lexeme.line_begin()
                    break
            lexeme = lexeme.next()

    def _record_conditional_scope(self):
        if_tracker_stack = []
        self.conditional_scope = {}
        else_if_tracker = []
        curr_if = []

        if self.parent_type == 'File':
            for entity in self.db.ents('file'):
                if str(self.file) in str(entity):
                    self.extract_control_flow(entity)

        for lexeme in self.file.lexer():
            if lexeme.token() not in ['Whitespace', 'Newline']:
                if not lexeme.ent():
                    continue
                control_flow_graph = lexeme.ent().freetext('CGraph')

                if self.parent_type == 'Function':
                    self.extract_control_flow(lexeme.ent())

                if control_flow_graph:
                    for parser in control_flow_graph.split(';'):
                        parser_nums = []
                        for x in parser.split(','):  # node_type, start_line, start_col, end_line, end_col
                            if x != '':
                                try:
                                    parser_nums.append(int(x))
                                except ValueError:
                                    parser_nums = []
                                    break
                        if not parser_nums or len(parser_nums) < 5:
                            continue
                        if parser_nums[0] == 5:
                            if parser_nums[1] not in else_if_tracker:
                                if_tracker_stack.append(parser_nums)
                                curr_if.append(parser_nums)
                                self.conditional_scope[parser_nums[1]] = {
                                    'if': {
                                        'line_num_begin': parser_nums[1],
                                        'column_num_begin': parser_nums[2],
                                        'line_num_end': parser_nums[3],
                                        'column_num_end': parser_nums[4]
                                    }
                                }
                        elif parser_nums[0] == 7 and (len(if_tracker_stack) or curr_if):  # 7 = else, 8 = endif
                            if not len(curr_if):
                                curr_if.append(if_tracker_stack[-1])
                            else_if_tracker.append(parser_nums[1])
                            current = curr_if.pop()
                            if 'else' not in self.conditional_scope[current[1]]:
                                self.conditional_scope[current[1]]['else'] = [{
                                    'line_num_begin': parser_nums[1],
                                    'column_num_begin': parser_nums[2],
                                    'line_num_end': parser_nums[3],
                                    'column_num_end': parser_nums[4]
                                }]
                            else:
                                self.conditional_scope[current[1]]['else'].append({
                                    'line_num_begin': parser_nums[1],
                                    'column_num_begin': parser_nums[2],
                                    'line_num_end': parser_nums[3],
                                    'column_num_end': parser_nums[4]
                                })
                        elif parser_nums[0] == 8 and (len(curr_if)):
                            current = curr_if.pop()
                            self.conditional_scope[current[1]]['endif'] = {
                                'line_num_begin': parser_nums[1],
                                'column_num_begin': parser_nums[2],
                                'line_num_end': parser_nums[3],
                                'column_num_end': parser_nums[4]
                            }
                            if len(if_tracker_stack):
                                if_tracker_stack.pop()

    def _lexeme_matcher(self, lexeme, string, line_num, direction='next'):
        while lexeme:
            if lexeme.line_begin() == line_num:
                if lexeme.text() == string:
                    return True
            else:
                return False

            if direction == 'next':
                lexeme = lexeme.next()
            else:
                lexeme = lexeme.previous()

    def _get_matched_lexeme(self, type, lexeme, string, line_num, direction='next'):
        matcher = lexeme.text() == string if type == 'string' else lexeme.token() == string
        while lexeme:
            if lexeme.line_begin() == line_num:
                if matcher:
                    return lexeme
            else:
                return None

            if direction == 'next':
                lexeme = lexeme.next()
            else:
                lexeme = lexeme.previous()

    def _record_if_closure(self, lexeme, line_num):
        cond_key = str(line_num)
        self.conds[cond_key] = {
            'line_num_begin': line_num,
            'line_num_end': line_num,
            'column_num_begin': lexeme.column_begin(),
            'column_num_end': lexeme.column_begin(),
            'enclosing_brace_count': 0,
        }

        if_without_braces = False
        has_braces = False
        while lexeme and lexeme.line_begin() < self.method_lines[-1]:
            if lexeme.token() == 'Newline' and self._lexeme_matcher(lexeme, ')', lexeme.line_begin(),
                                                                    'previous') and not has_braces:
                if_without_braces = True
                has_braces = False
            if if_without_braces and lexeme.text() == ';':
                self.conds[cond_key]['has_braces'] = False
                self.conds[cond_key]['line_num_end'] = lexeme.line_begin()
                self.conds[cond_key]['column_num_end'] = lexeme.column_end()
                break
            if lexeme.text() == '{' and not if_without_braces:
                has_braces = True
                self.conds[cond_key]['enclosing_brace_count'] += 1
                self.conds[cond_key]['has_braces'] = True
            if lexeme.text() == '}' and self.conds[cond_key]['enclosing_brace_count'] > 0 and not if_without_braces:
                self.conds[cond_key]['enclosing_brace_count'] -= 1
                if self.conds[cond_key]['enclosing_brace_count'] == 0:
                    self.conds[cond_key]['line_num_end'] = lexeme.line_begin()
                    self.conds[cond_key]['column_num_end'] = lexeme.column_end()
                    break

            lexeme = lexeme.next()

    def _record_else_closure(self, lexeme):
        while lexeme and lexeme.line_begin() < self.method_lines[-1]:
            if lexeme.text() == 'else':
                else_key = lexeme.text() + '_' + str(lexeme.line_begin())
                lex_it = lexeme
                self.conds[else_key] = {}
                self.conds[else_key] = {
                    'column_num_begin': lexeme.column_begin(),
                    'column_num_end': lexeme.column_end(),
                    'line_num_begin': lexeme.line_begin()
                }

                else_without_braces = False
                has_braces = False
                while lex_it and lex_it.line_begin() < self.method_lines[-1]:
                    if lex_it.token() != 'Whitespace':
                        if lex_it.text() == '{' and lex_it.previous().text() != '$':
                            has_braces = True
                            self.conds[else_key]['has_braces'] = True
                            else_without_braces = False

                        if lex_it.token() == 'Newline' and not has_braces:
                            else_without_braces = True
                            self.conds[else_key]['has_braces'] = False
                            matched_lexeme = self._get_matched_lexeme('string', lex_it.next(), ';',
                                                                      lex_it.line_end() + 1) or self._get_matched_lexeme(
                                'token', lex_it.next(), 'Newline', lex_it.line_end() + 1)
                            if matched_lexeme:
                                self.conds[else_key]['column_num_end'] = matched_lexeme.column_end()
                                self.conds[else_key]['line_num_end'] = lex_it.line_end() + 1
                                break
                            lex_it = lex_it.next()

                        if else_without_braces and (
                                lex_it.text() == ';' or (lex_it.next() and lex_it.next().token() == 'Newline')):
                            self.conds[else_key]['column_num_end'] = lex_it.column_end() + 1
                            self.conds[else_key]['line_num_end'] = lex_it.line_end()
                            else_without_braces = False
                            self.conds[else_key]['has_braces'] = False
                            break

                        if lex_it.text() == '}' and lex_it.next().text() != '`' and not else_without_braces:
                            self.conds[else_key]['column_num_end'] = lex_it.column_end()
                            self.conds[else_key]['line_num_end'] = lex_it.line_end()
                            break

                        self.conds[else_key]['column_num_end'] = lex_it.column_end()
                        self.conds[else_key]['line_num_end'] = lex_it.line_end()

                    lex_it = lex_it.next()
            lexeme = lexeme.next()

    def _record_class_scope(self, lexeme, line_stack):
        while lexeme:
            if lexeme.text() == 'class':
                line_stack.add(lexeme.line_begin())
                break
            lexeme = lexeme.previous()

    def _record_method_scope(self, lexeme, line_stack):
        builder = []
        while lexeme:
            if lexeme.text() in ['{', ')']:
                builder.append(lexeme.text())

            if (' '.join(builder) == ') {'):
                line_stack.add(lexeme.line_begin())
                break
            lexeme = lexeme.previous()

    def _record_object_scope(self, lexeme, line_stack):
        while lexeme:
            if lexeme.text() == '{':
                line_stack.add(lexeme.line_begin())
                break
            lexeme = lexeme.previous()

    def get_related_var_lines(self, line_stack, analyzed_lines, show_use_by=False):
        pointer_line = next(iter(line_stack))
        variables = self.get_variable_entities(pointer_line)

        while len(line_stack) > 0:
            for var in variables:
                for reference in var.refs():
                    current_line = reference.line()
                    if current_line <= self.buggy_line_num and current_line not in analyzed_lines and reference.kind().longname() in REL_KIND:
                        line_stack.add(current_line)

            analyzed_lines.add(pointer_line)
            line_stack.remove(pointer_line)
            if len(line_stack) > 0:
                pointer_line = next(iter(line_stack))
                variables = self.get_variable_entities(pointer_line)
        return analyzed_lines

    def run(self, file_obj=None, root_path=None, dual_slice=False, js_file_type=None):
        line_stack = set()
        analyzed_lines = set()
        variables = self.get_variable_entities(self.buggy_line_num)

        for var in variables:
            if var.kindname() == 'Function':
                self.has_function_call = True
            if var.parent() and (
                    var.parent().name() == 'constructor' or var.parent().kindname() == 'Function'):  # If its a function within a class, record the parent scope
                lexeme = var.lexer().lexeme(var.ref().line(), var.ref().column())
                self._record_class_scope(lexeme, line_stack)
                self._record_method_scope(lexeme, line_stack)
            for reference in var.refs():
                current_line = reference.line()
                if current_line < self.buggy_line_num and current_line > self.method_start_line_num and current_line not in analyzed_lines and reference.kind().longname() in REL_KIND:
                    line_stack.add(current_line)

        analyzed_lines.add(self.buggy_line_num)

        if not len(line_stack):
            return 'No lines'

        analyzed_lines = self.get_related_var_lines(line_stack, analyzed_lines)

        self.analyze_closure()
        statements = self.get_statements(set([a for a in analyzed_lines if a is not None]))

        if file_obj and file_obj['buggy_line'] and len(statements):
            if not dual_slice:
                print('Writing slice to files......')
                buggy_file = open(root_path + file_obj['buggy_file'], "w")
                fixed_file = open(root_path + file_obj['fixed_file'], "w")
                closest_match = get_close_matches(file_obj['buggy_line'], statements, n=1)
                if len(closest_match):
                    last_occurence_of_buggy_line = len(statements) - statements[::-1].index(closest_match[0]) - 1
                    if last_occurence_of_buggy_line > -1:
                        for idx, s in enumerate(statements):
                            buggy_file.write(s + '\n')
                            if s in closest_match and idx == last_occurence_of_buggy_line:
                                fixed_file.write(file_obj['fixed_line'] + '\n')
                            else:
                                fixed_file.write(s + '\n')

                        buggy_file.close()
                        fixed_file.close()
                        return statements
            else:
                print('Writing dual slice to files for file type {}......'.format(js_file_type))
                js_file = open(root_path + file_obj[js_file_type], "w")
                for s in statements:
                    js_file.write(s + '\n')
                js_file.close()
                return statements
        else:
            print('********* Sliced Statements **********')
            [print(s) for s in statements]
            print('********* End **********')
            return statements


def process_single_file(project_path):
    db = understand.open(project_path)

    buggy_line_num = 9
    file = db.lookup("test.js")[0]
    bs = BackwardSlicing(db, file, buggy_line_num)
    bs.run()


def test_backward_slice():
    db = understand.open('./test-slice-js/test-slice-js.und')
    with open('./test-slice-js/file_line_map.json') as f:
        file_line_map = json.load(f)
        for item in file_line_map:
            file = db.lookup(item['file'])[0]
            bs = BackwardSlicing(db, file, item['line_num'])
            actual_statements = bs.run()
            actual_statements = ''.join([s.strip() for s in actual_statements])

            if item['expected_output']:
                assert actual_statements == item['expected_output'], 'Failed assertion in {} {}'.format(item['file'],
                                                                                                        item[
                                                                                                            'line_num'])
                print('TEST PASSED for file/line', item['file'], item['line_num'])
            else:
                print('ACTUAL --- ', actual_statements)


def is_whitespace_diff(buggy_line, fixed_line):
    output_list = [li for li in ndiff(fixed_line, buggy_line) if li[0] != ' ']
    if len(output_list):
        return all(f.strip() in ['+', '-'] for f in output_list)
    return False


def process_split_projects(project_path, root_sliced_path, dual_slice):
    subdir = project_path.split('\\')[-1]

    udb = '{}\\{}.und'.format(project_path, subdir)
    folderpath_db_map = {}
    folderpath_db_map[udb] = project_path

    files = []
    csv_file_path = project_path + '\\' + '{}_bugs_info.csv'.format(subdir)

    with open(csv_file_path, encoding='utf-8') as csv_file:
        csv_reader = csv.reader(csv_file, delimiter=',')

        for row in csv_reader:
            files.append({
                'buggy_line_num': row[2],
                'buggy_line': row[3],
                'fixed_line': row[4],
                'buggy_file': row[0],
                'fixed_file': row[1]
            })

    def generate_slice(row):
        buggy_file = row['buggy_file']
        fixed_file = row['fixed_file']
        buggy_line_num = row['buggy_line_num']

        if os.path.exists(root_sliced_path + buggy_file):
            print('File already exists ---- Skipping...')
            return ''
        elif (os.path.exists(folderpath_db_map[udb] + '\\' + buggy_file) and os.path.exists(
                folderpath_db_map[udb] + '\\' + fixed_file)):
            print('Processing buggy file -----', buggy_file, buggy_line_num)
            file_obj = {
                'buggy_line': row['buggy_line'],
                'fixed_line': row['fixed_line'],
                'buggy_file': buggy_file,
                'fixed_file': fixed_file
            }
            try:
                db_file = db.lookup(buggy_file, 'File')
                if db_file:
                    buggy_file_slice = BackwardSlicing(db, db_file[0], int(buggy_line_num))
                    print('Doing backward slice on buggy file {}......'.format(buggy_file))
                    try:
                        buggy_file_slice.run(file_obj, root_path=root_sliced_path, dual_slice=dual_slice,
                                             js_file_type='buggy_file')
                    except Exception as err:
                        print('Error in file', buggy_file, err)
                        traceback.print_exc()
            except SystemError:
                return ''

            if dual_slice:
                try:
                    db_file = db.lookup(fixed_file, 'File')
                    if db_file:
                        fixed_file_slice = BackwardSlicing(db, db_file[0], int(buggy_line_num))
                        print('Doing backward slice on fixed file {}......'.format(fixed_file))
                        try:
                            fixed_file_slice.run(file_obj, root_path=root_sliced_path, dual_slice=dual_slice,
                                                 js_file_type='fixed_file')
                            return 'Success'
                        except Exception as err:
                            print('Error in file', fixed_file, err)
                            traceback.print_exc()
                except SystemError:
                    return ''

            return 'Success'

    db = understand.open(udb)

    with concurrent.futures.ThreadPoolExecutor(max_workers=5) as executor:
        futures = []
        print('Accessing udb.....', udb)
        for row in files:
            futures.append(executor.submit(generate_slice, row))
        for future in concurrent.futures.as_completed(futures):
            print(future.result())

    print('********** DONE **********')


if __name__ == '__main__':
    project_type = sys.argv[1] or 'test'  # choices = ['single', 'multiple', 'test']
    dual_slice = False if sys.argv[2] == 'False' else True
    project_path = sys.argv[3:]

    if project_type == 'multiple':
        for dir in project_path:
            print('Slicing for folder {}'.format(dir))
            root_sliced_path = '{}\\{}\\'.format(dir, 'sliced_dual' if dual_slice else 'sliced')
            try:
                os.mkdir(root_sliced_path)
            except FileExistsError:
                print('Folder exists..')
            process_split_projects(dir, root_sliced_path, dual_slice)
            print('Completed slicing for folder {}'.format(dir))
    elif project_type == 'single':
        process_single_file(project_path[0])
    else:
        test_backward_slice()  # For testing slicing stability

对于双重切片代码解析：

safe_list_get(arr, idx): 这个函数的作用是安全地获取列表 arr 中索引为 idx 的元素。它使用了 try-except 块来捕获可能发生的 IndexError 异常，防止程序因为索引越界而崩溃。如果索引存在，函数会返回对应的元素；否则，返回 None。

get_patch_from_diff(diff): 这个函数接受一个表示两个字符串差异的 diff 字符串作为输入，并从中提取出存在差异的行。函数首先初始化了两个变量 buggy_line 和 fixed_line，它们分别用于保存出现差异的行。随后，函数遍历 diff 字符串中的每一行，当遇到以 + 开头的行时，将这一行去掉开头的 + 加入到 fixed_line 中；当遇到以 - 开头的行时，将这一行去掉开头的 - 加入到 buggy_line 中。最后，函数返回 buggy_line 和 fixed_line。

BackwardSlicing.__init__(self, db, file, buggy_line_num): 这个类的构造函数初始化了一些属性和数据结构。它接受一个understand数据库对象db、一个文件对象file和一个有bug的行号buggy_line_num作为输入参数。这些参数分别用于初始化self.db、self.file和self.buggy_line_num属性。另外，构造函数还初始化了一些其它的属性，如self.method_lines、self.loops、self.conds等，并初始化了一些集合数据结构。构造函数的主要目的是准备数据结构以便后续的切片操作。

BackwardSlicing._get_outermost_parent(self, first_line): 这个方法用于找到 first_line 所在范围内最外层的父级行号。它通过遍历文件对象的 lexer 方法返回的结果，查找与 first_line 行号对应的词元，然后获取该词元对应的父级行号，即文件、类或函数的行号。并返回其结果。如果未找到匹配的父级行，则返回 None。

BackwardSlicing._get_object_beginning(self, line_number): 这个方法用于处理代码中可能出现的点号换行的情况，即点号后面的对象名在下一行。它通过遍历文件对象的 lexer 方法返回的结果，查找包含 line_number 行号的词元。如果找到一个包含点号的词元，且点号前面是空白字符，则递归调用该方法，传入 line_number - 1 作为参数，继续查找对象开始的行号。如果找到了对象开始的行号，则返回该行号；否则，返回 line_number。

BackwardSlicing.get_variable_entities(self, line_number): 这个方法用于获取给定行号 line_number 所在行的变量实体。它通过遍历文件对象的 lexer 方法返回的结果，查找与 line_number 行号对应的词元。当词元的类型是 Identifier 且包含实体时，将该实体添加到结果列表中。如果词元的实体是 Property 类型，则将其父实体添加到结果列表中。最后，返回结果列表。

BackwardSlicing.is_within_loop(self, line_num): 这个方法用于判断给定行号 line_num 是否在某个循环语句内部。函数会遍历存储在 self.loops 属性中的循环语句信息，判断给定行号是否在每个循环语句的起始行号和结束行号之间。如果是，则将该循环语句的起始行号和结束行号添加到结果列表中。最后，返回结果列表。

BackwardSlicing.is_within_scope(self, line_num): 这个方法用于判断给定行号 line_num 是否在某个作用域内部。函数会遍历存储在 self.scope 属性中的作用域信息，判断给定行号是否在每个作用域的起始行号和结束行号之间。如果是，则将该作用域的起始行号、结束行号和是否为变量作用域的信息添加到结果列表中。最后，返回结果列表。

BackwardSlicing.is_within_conditional(self, line_num): 这个方法用于判断给定行号 line_num 是否在某个条件语句内部。函数会遍历存储在 self.conds 属性中的条件语句信息，判断给定行号是否在每个条件语句的起始行号和结束行号之间。如果是，则将该条件语句的起始行号和结束行号添加到结果列表中。如果条件语句是一个 else 语句，则还会记录 else 语句的起始行号。最后，返回结果列表。

BackwardSlicing.find_conditional_by_else(self, lines): 这个方法用于根据else行找到相关条件语句的范围。函数遍历存储在 self.conditional_scope 属性中的条件语句信息，找到跟当前 else 行相关联的条件语句，并将相关条件语句的范围添加到结果集合中。返回最终的结果集合。

BackwardSlicing.on_add_line(self, line_numbers): 这个方法用于在切片过程中添加某个行号的相关行。它可以接受一个行号集合或单个行号作为输入。如果输入是行号集合，则会遍历集合中的每个行号，调用 _on_add 方法获取与每个行号相关的行，并将其结果合并为最终的行号集合返回。如果输入是单个行号，则直接调用 _on_add 方法返回结果。

BackwardSlicing.get_statements(self, lines): 这个方法用于根据行号集合获取与这些行号相关的语句。它遍历文件的词法分析结果，根据行号匹配词元，将匹配的词元拼接成字符串，作为一条语句，添加到结果列表中。最后，返回结果语句列表。

BackwardSlicing.analyze_closure(self): 这个方法用于分析代码的闭包信息。它通过遍历文件对象的 lexer 方法返回的结果，查找与每个行号相关的词元，然后根据词元的类型记录闭包信息，包括循环语句、条件语句和作用域信息。

BackwardSlicing.run(self, file_obj=None, root_path=None, dual_slice=False, js_file_type=None): 这个方法是类的主要方法，用于执行反向切片操作。它接受一个文件对象 file_obj、一个根目录路径 root_path、一个布尔值 dual_slice 和一个字符串 js_file_type 作为参数。在方法的实现中，它调用了类的其他私有方法和辅助函数，根据参数执行不同的切片操作，并将切片结果写入文件或打印出来。最后，返回切片结果列表。

训练

在Hoppity的GNN架构上运行的步骤如下：

• 解压./hoppity-data/目录下的sliced_data.tar.gz

如何创建一个新的Conda环境？

假设我们要创建的Conda环境的名称是model。

cd gh-crawler
npm install shift-parser fast-json-patch

cd ../hoppity-data/hoppity
conda create -n gnnEnv
conda activate gnnEnv

pip install torch
pip install -r requirements.txt

cd deps/torchext
pip install -e .

cd ../..
pip install -e .
# 报错就pip install gtrans

开始训练之前

cd hoppity-data

在开始训练之前运行：

reset_data_dirs.sh

该sh对应的bat文件：

@echo off
rmdir /s /q ml_astPKL
mkdir ml_astPKL
rmdir /s /q ml_astJSON
mkdir ml_astJSON
rmdir /s /q ml_raw
mkdir ml_raw
rmdir /s /q ml_trainingResult
mkdir ml_trainingResult
rmdir /s /q ml_patch
mkdir ml_patch
rmdir /s /q eval_dump_folder
mkdir eval_dump_folder

准备数据集的命令

cd ../gh-crawler
ast_diff/my_get_ast_diff.sh

cd hoppity/gtrans
cd data_process
rm processed.txt
./run_build_dataset.sh
./run_split.sh

my_get_ast_diff.sh对应的bat：

运行训练的命令

运行run_main.sh来触发训练。在后续阶段，我们需要在common/config.py文件中调整超参数。至少运行30个epochs的训练。之后终止脚本以结束训练。

cd hoppity-data/hoppity/gtrans/training
./run_main.sh

进行验证的命令

现在我们需要找到最佳模型。运行find_best_model.sh，并根据结果在eval.sh中相应地设置变量。

cd hoppity-data/hoppity/gtrans/eval
./find_best_model.sh

根据需要在eval.sh中设置目标模型（epoch-*.ckpt）。

./eval.sh