xml - 同一个多方法不同方法之间的递归

Question

我正在编写一个 Clojure 库来解析 Mac OS X 的基于 XML 的 property list files .代码工作正常，除非你给它一个大的输入文件，此时你得到 java.lang.OutOfMemoryError: Java heap space。

这是一个示例输入文件(小到可以正常工作):

<plist version="1.0">
<dict>
    <key>Integer example</key>
    <integer>5</integer>
    <key>Array example</key>
    <array>
        <integer>2</integer>
        <real>3.14159</real>
    </array>
    <key>Dictionary example</key>
    <dict>
        <key>Number</key>
        <integer>8675309</integer>
    </dict>
</dict>
</plist>

clojure.xml/parse 将它变成:

{:tag :plist, :attrs {:version "1.0"}, :content [
    {:tag :dict, :attrs nil, :content [
        {:tag :key, :attrs nil, :content ["Integer example"]}
        {:tag :integer, :attrs nil, :content ["5"]}
        {:tag :key, :attrs nil, :content ["Array example"]}
        {:tag :array, :attrs nil, :content [
            {:tag :integer, :attrs nil, :content ["2"]}
            {:tag :real, :attrs nil, :content ["3.14159"]}
        ]}
        {:tag :key, :attrs nil, :content ["Dictionary example"]}
        {:tag :dict, :attrs nil, :content [
            {:tag :key, :attrs nil, :content ["Number"]}
            {:tag :integer, :attrs nil, :content ["8675309"]}
        ]}
    ]}
]}

我的代码将其转换为 Clojure 数据结构

{"Dictionary example" {"Number" 8675309},
 "Array example" [2 3.14159],
 "Integer example" 5}

我的代码的相关部分看起来像

; extract the content contained within e.g. <integer>...</integer>
(defn- first-content
  [c]
  (first (c :content)))

; return a parsed version of the given tag
(defmulti content (fn [c] (c :tag)))

(defmethod content :array
  [c]
  (apply vector (for [item (c :content)] (content item))))

(defmethod content :dict
  [c]
  (apply hash-map (for [item (c :content)] (content item))))

(defmethod content :integer
  [c]
  (Long. (first-content c)))

(defmethod content :key
  [c]
  (first-content c))

(defmethod content :real
  [c]
  (Double. (first-content c)))

; take a java.io.File (or similar) and return the parsed version
(defn parse-plist
  [source]
  (content (first-content (clojure.xml/parse source))))

代码的核心是 content 函数，这是一种在 :tag(XML 标记的名称)上分派(dispatch)的多方法。我想知道我是否应该做一些不同的事情来使递归更好地工作。我尝试用 trampoline content 替换对 content 的所有三个调用，但这没有用。我应该做些什么来使这种相互递归更有效地工作？还是我采取了根本错误的方法？

编辑:顺便说一句，这段代码是available on GitHub , 以哪种形式可能更容易玩弄。

Answer 1

您有多个(每个 child 一个)来自单个方法的递归调用，因此您的代码不是(并且不能没有大量重组)尾递归。 trampoline 用于相互尾递归 函数。

您的大型 XML 文件有多深、多长？我问是因为您得到的是 OoM 而不是 SO。

无论如何，要解决你的递归问题(不太可能是导致异常的问题)，你必须在维护堆栈(向量或列表)表示正在构建的结果树。具有讽刺意味的是，XML 数据结构的遍历在某种程度上相当于用于构建结构的 sax 事件。