12

我想确定用空格缩进的源文件中使用的制表符宽度。这对于具有特别规则缩进的文件并不难,其中前导空格仅用于缩进,始终是制表符宽度的倍数,并且缩进每次增加一级。但是许多文件会与这种常规缩进有所不同,通常是为了某种形式的垂直对齐。因此,我正在寻找一种很好的启发式方法来估计使用的标签宽度,从而允许不规则缩进的一些可能性。

这样做的动机是为 SubEthaEdit 编辑器编写扩展。不幸的是,SubEthaEdit 没有使选项卡宽度可用于脚本,所以我将根据文本猜测它。

一个合适的启发式应该:

  • 性能足够好,可以交互使用。我不认为这会是一个问题,如果需要,可以只使用部分文本。
  • 语言独立。
  • 返回最长的合适标签宽度。例如,如果每个缩进实际上是两倍的级别,则任何具有四个空格的制表符宽度的文件也可能是具有两个空格制表符的文件。显然,四个空格将是正确的选择。
  • 如果压痕完全规则,请始终正确处理。

一些简化因素:

  • 可以假设至少一行是缩进的。
  • 可以假定制表符宽度至少为两个空格。
  • 可以安全地假设缩进仅使用空格完成。并不是我对tab有什么反对——恰恰相反,我会先检查是否有用于缩进的tab,并单独处理。这确实意味着可能无法正确处理缩进混合制表符和空格,但我认为这并不重要。
  • 可以假设没有仅包含空格的行。
  • 并非所有语言都需要正确处理。例如,像 lisp 和 go 这样的语言的成功或失败将完全无关紧要,因为它们通常不是手动缩进的。
  • 不需要完美。如果偶尔需要手动调整几行,世界不会结束。

你会采取什么方法,你认为它的优点和缺点是什么?

如果您想在答案中提供工作代码,最好的方法可能是使用一个 shell 脚本来读取源文件stdin并将制表符宽度写入stdout. 伪代码或清晰的文字描述也可以。

一些结果

为了测试不同的策略,我们可以将不同的策略应用于语言分布的标准库中的文件,因为它们可能遵循语言的标准缩进。我将考虑 Python 2.7 和 Ruby 1.8 库(系统框架安装在 Mac OS X 10.7 上),它们的预期选项卡宽度分别为 4 和 2。不包括以制表符开头的行或没有以至少两个空格开头的行的文件。

Python:

                     Right  None  Wrong
Mode:                 2523     1    102
First:                2169     1    456
No-long (12):         2529     9     88
No-long (8):          2535    16     75
LR (changes):         2509     1    116
LR (indent):          1533     1   1092
Doublecheck (10):     2480    15    130
Doublecheck (20):     2509    15    101

红宝石:

                     Right  None  Wrong
Mode:                  594    29     51
First:                 578     0     54
No-long (12):          595    29     50
No-long (8):           597    29     48
LR (changes):          585     0     47
LR (indent):           496     0    136
Doublecheck (10):      610     0     22
Doublecheck (20):      609     0     23

在这些表中,“正确”应被视为确定语言标准制表符宽度,“错误”应视为非零制表符宽度不等于语言标准宽度,而“无”应视为零制表符宽度或否回答。“模式”是选择最频繁发生的缩进变化的策略;“First”是对第一行缩进进行缩进;“不长”是FastAl排除缩进大的行并采取模式的策略,数字表示允许的最大缩进变化;“LR”是Patrick87基于线性回归的策略,有基于行间缩进变化和行绝对缩进的变体;“Doublecheck”(无法抗拒双关语!)是 Mark 对 FastAl 的修改

4

7 回答 7

3

好的,因为您想要一个与语言无关的解决方案,我们将无法使用任何句法提示。尽管您说您不想要一个完美的解决方案,但这里有一个可以很好地与大多数语言一起使用的解决方案。

实际上,我必须解决密码学中的类似问题才能在多字母密码中获得正确的代码字长。这种加密是一种基本的Caesar-chiffre(字母表的每个字母移动n个字母),其中密码用于不同地移动字母(明文的第n个字母移动mod (nth,length (密码))密码的字母)。选择的武器是自相关

该算法将是这样的:

  1. 在行首的空格结束后删除所有字符 - 保持行尾标记完好无损。
  2. 删除零空格的行(因为它们只是空行)
  3. 计算每行的空白宽度并将其保存在数组长度中
  4. 自相关:循环直到最大估计数 - 可能相当高,如 32 或其他 - 当前迭代应为i对于每次迭代,计算每个条目与第i 个条目之间的距离。计算距离数 = 0(第 n 个和第(n+i) 个条目的值相同),将键i保存在数组中。
  5. 你现在有一个相同对出现的数组。计算该数组的平均值,并删除该平均值附近的所有值(留下自相关的尖峰)。尖峰将是最小值的倍数,这将是搜索到的用于缩进的空格数。

自相关是一个非常好的函数,可用于您想要检测数据流中的重复值的所有情况。它在信号处理中大量使用并且速度非常快(取决于估计的信号重复的最大距离)。

是的,当时我用自相关破解了多字母密文。;)

于 2011-08-23T14:13:25.570 回答
2
  • 对于文件中的每一行
    • 如果缩进比前一个多,将差异添加到列表中
      • 如果 > 12 则丢弃,这可能是续行
  • 生成列表中#s的频率表
  • #1 可能是您的答案。

编辑

我打开了 VB.Net(不是吗?:-) 我的意思是:

    Sub Main()
        Dim lines = IO.File.ReadAllLines("ProveGodExists.c")
        Dim previndent As Integer = 0
        Dim indent As Integer
        Dim diff As Integer
        Dim Diffs As New Dictionary(Of Integer, Integer)
        For Each line In lines
            previndent = indent
            indent = Len(line) - Len(LTrim(line))
            diff = indent - previndent
            If diff > 0 And diff < 13 Then
                If Diffs.ContainsKey(diff) Then
                    Diffs(diff) += 1
                Else
                    Diffs.Add(diff, 1)
                End If
            End If
        Next
        Dim freqtbl = From p In Diffs Order By p.Value Descending
        Console.WriteLine("Dump of frequency table:")
        For Each item In freqtbl
            Console.WriteLine(item.Key.ToString & " " & item.Value.ToString)
        Next
        Console.WriteLine("My wild guess at tab setting: " & freqtbl(0).Key.ToString)
        Console.ReadLine()
    End Sub

结果:

频率表转储:
4 748
8 22
12 12
2 2
9 2
3 1
6 1
我对标签设置的疯狂猜测:4

希望有帮助。

于 2011-08-18T20:41:01.023 回答
1

也许做一些类似...

  1. 获取文件中所有标签宽度的列表
  2. 删除 50% 最不频繁的条目
  3. 按升序对剩余条目进行排序
  4. 计算 (a, b) 对的列表,其中 b 在选项卡宽度列表中,a 给出该选项卡宽度的等级。
  5. 绘制最佳拟合线
  6. 最佳拟合线的斜率是标签宽度的猜测值。四舍五入到最接近的整数。

例子:

  1. 列表 = [4, 4, 6, 8, 8, 4, 4, 4, 8, 8, 12, 5, 11, 13, 12, 12]
  2. 列表 = [4, 4, 4, 4, 4, 8, 8, 8]
  3. 已经排序
  4. [(1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (2, 8), (2, 8), (2, 8)]
  5. 最佳拟合线是 b = 4a + 0 (R^2 = 0)
  6. 斜率为 4,所以这可能是标签宽度。
于 2011-08-09T16:31:52.433 回答
1

您的选择是(实际上)2,3,4,5,6,7,8。

我会使用@FastAl 建议的方法扫描前 50-100 行左右。我可能倾向于只是盲目地从带有文本的任何行的前面拉空格数并计算空白字符串的长度。如果您有可用的正则表达式,则左修剪线和运行长度两次似乎是一种浪费。另外,我会这样做System.Math.abs(indent - previndent),你会得到去缩进的数据。正则表达式是这样的:

row.matches('^( +)[^ ]') # grab all the spaces from line start to non-space.

一旦你得到了 7 个选项中哪一个的计数最高的统计数据,就将它作为第一个猜测值运行。对于 8、6 和 4,您应该检查是否还有 4 和 2、3 或 2 的重要计数(第二名或超过 10% 或其他一些便宜的启发式)。如果有很多 12(或 9s)可能暗示 4(或 3)也是比 8(或 6)更好的选择。一次删除或添加超过 2 个级别(通常是折叠的结束括号)非常罕见。

无关紧要的喃喃自语

我看到的一个问题是,旧的 .c 代码尤其具有这种令人讨厌的模式:

code level 0
/* Fancy comments get weird spacing because there 
 * is an extra space beyond the *
 * looks like one space!
 */
  code indent (2 spaces)
  /* Fancy comments get weird spacing because there 
   * is an extra space beyond the *
   * looks like three spaces!
   */

code level 0
  code indent (2 spaces)
  /* comment at indent level 1
     With no stars you wind up with 2 spaces + 3 spaces.
  */

呸。我不知道您如何处理这样的评论标准。对于像“c”这样的代码,您可能必须处理 2.0 版中的特殊注释......但我现在暂时忽略它。

您的最后一个问题是处理与您的假设不符的行。我的建议是将它们“标记”到深度,然后将多余的空格留在原处。如果你必须纠正我会这样做:rowtabdepth = ceiling((rowspacecount - (tabwidth/2)) / tabwidth)

于 2011-08-24T19:01:11.057 回答
0

对于您想要支持的每种语言,您需要进行一些解析:
1)排除注释(逐行或逐块,也许也嵌套?)
2)找到子块的开口({在 C-像语言,beginpascal,doshell等)

然后看看子块打开后空格数增加了多少。做一些简单的统计——找出最频繁的值、最大值和最小值、平均值。通过这种方式,您还可以查看缩进是否正常以及有多少。

于 2011-08-09T14:33:00.820 回答
0

作为基线,可以简单地计算所有缩进增加,并将最频繁的增加作为制表符宽度。作为一个 shell 脚本,编写为每个管道阶段有小动作,它可能看起来像这样:

#!/bin/sh

grep -v -E '^[[:space:]]*$' | 
  sed 's/^\([[:space:]]*\).*/\1/' | 
    awk '{ print length($0) }' | 
      awk '$1 > prev { print $1 - prev } { prev = $1 }' | 
        sort | 
          uniq -c | 
            sort -k1nr | 
              awk '{ print $2 }' | 
                head -n 1

这个实现是文件O(n log(n))n的行数,但它可以很容易地在O(n).

于 2011-08-17T18:18:16.957 回答
0

启发式:

  1. 获取从一行到下一行 > 0 的所有缩进更改的列表。
  2. 制作此列表中所有值的频率表。
  3. 取频率最高的值。

Python 脚本,采用文件名或标准输入并打印最佳缩进数:

#!/usr/bin/env python

import fileinput, collections

def leadingSpaceLen(line):
    return len(line) - len(line.lstrip())

def indentChange(line1, line2):
    return leadingSpaceLen(line2) - leadingSpaceLen(line1)

def indentChanges(lines):
    return [indentChange(line1, line2)
        for line1, line2 in zip(lines[:-1], lines[1:])]

def bestIndent(lines):
    f = collections.defaultdict(lambda: 0)
    for change in indentChanges(lines):
        if change > 0:
            f[change] += 1
    return max(f.items(), key=lambda x: x[1])[0]

if __name__ == '__main__':
    print bestIndent(tuple(fileinput.input()))
于 2011-08-24T14:29:38.163 回答