Support changing and insertion/deletion according to clodhopper heuristic

2 files changed, 103 insertions, 31 deletions

diff --git a/examples/change-setting.lua b/examples/change-setting.lua
index 0317bce..1c26545 100644
--- a/examples/change-setting.lua
+++ b/examples/change-setting.lua
@@ -19,9 +19,13 @@ if not conf then
    error(err)
 end
 
+-- Change name (should not move)
 conf.settings.project.name = "Clod"
+-- Change head (should not move)
 conf.settings.project.head = "refs/heads/master"
+-- Add description (should appear after head)
 conf.settings.project.description = "Demonstration of settings"
+-- Remove other.thing (will also elide trailing blank line)
 conf.settings.other.thing = nil
 
 io.stdout:write(conf:serialise())
diff --git a/lib/clod.lua b/lib/clod.lua
index 4cabbf0..2fa1d07 100644
--- a/lib/clod.lua
+++ b/lib/clod.lua
@@ -40,6 +40,38 @@ function settings_mt:__index(subkey)
    end
 end
 
+local function insert_after(entry, new_entry)
+   -- Interject new_entry after entry
+   if entry.next then
+      entry.next.prev = new_entry
+   end
+   new_entry.next = entry.next
+   new_entry.prev = entry
+   entry.next = new_entry
+   -- Now sort the line numbers out
+   local lineno = entry.lineno
+   while entry do
+      entry.lineno = lineno
+      lineno = lineno + 1
+      entry = entry.next
+   end
+end
+
+local function delete_entry(entry)
+   if entry.prev then
+      entry.prev.next = entry.next
+   end
+   if entry.next then
+      entry.next.prev = entry.prev
+   end
+   -- Shuffle all lines from here on down away
+   entry = entry.next
+   while entry do
+      entry.lineno = entry.lineno - 1
+      entry = entry.next
+   end
+end
+
 function settings_mt:__newindex(subkey, value)
    local meta = metadata[self]
    local confmeta = metadata[meta.conf]
@@ -52,40 +84,76 @@ function settings_mt:__newindex(subkey, value)
       if confmeta.settings[key] then
 	 -- Need to remove *this* entry
 	 local entry = confmeta.settings[key]
-	 if entry == confmeta.entries then
-	    -- First entry, move the head along
-	    confmeta.entries = entry.next
-	 end
-	 if entry.prev then
-	    entry.prev.next = entry.next
-	 end
-	 if entry.next then
-	    entry.next.prev = entry.prev
-	 end
-	 -- Shuffle all lines from here on down away
-	 entry = entry.next
-	 while entry do
-	    entry.lineno = entry.lineno - 1
-	    entry = entry.next
+	 local prev = entry.prev
+	 local next = entry.next
+	 delete_entry(entry)
+	 if prev and next then
+	    -- Also delete 'next' if prev is also blank
+	    if not prev.key and not next.key then
+	       delete_entry(next)
+	    end
+	 elseif prev and not next then
+	    -- Also delete prev, if it's not the zeroth sentinel
+	    -- and it's blank, since we've removed the last line
+	    if not prev.key and prev.lineno > 0 then
+	       delete_entry(prev)
+	    end
 	 end
       end
    elseif confmeta.settings[key] then
       -- Replacing extant entry
       confmeta.settings[key].value = value
    else
-      -- Inventing a new entry, we will put it at the end
-      local last = confmeta.entries
-      while last.next do
-	 last = last.next
+      -- Inventing a new entry, let's try and find a good
+      -- spot for it.
+      -- 
+      -- Search the list, looking for the longest common prefix.
+      -- Place the new element at the end of any section of that
+      -- longest common prefix, or else at the end.
+      -- If placing at the end, insert a blank line if necessary
+      -- to separate it from something without a common prefix.
+      local longest_prefix = 0
+      local longest_prefix_found_at = nil
+      local entry = confmeta.entries
+      while entry do
+	 if entry.key then
+	    local maxpos = 0
+	    for i = (#key < #entry.key and #key or #entry.key), 1, -1 do
+	       if key:sub(i,i) == entry.key:sub(i,i) then
+		  if key:sub(1,i):find("%.") then
+		     maxpos = i
+		     break
+		  end
+	       end
+	    end
+	    if maxpos > longest_prefix then
+	       longest_prefix = maxpos
+	       longest_prefix_found_at = entry
+	    end
+	 end
+	 entry = entry.next
       end
-      local new_entry = {
-	 key = key,
-	 value = value,
-	 lineno = last.lineno + 1,
-	 prev = last
-      }
-      last.next = new_entry
-      confmeta.settings[key] = new_entry
+      local insert_blank = false
+      if longest_prefix == 0 then
+	 local last = confmeta.entries
+	 while last.next do
+	    last = last.next
+	 end
+	 longest_prefix_found_at = last
+	 if last.key then
+	    insert_blank = true
+	 end
+      end
+      local before = longest_prefix_found_at
+      if insert_blank then
+	 insert_after(before, {})
+	 before = before.next
+      end
+      insert_after(before, {
+		      key = key,
+		      value = value,
+		   })
+      confmeta.settings[key] = before.next
    end
 end
 
@@ -125,7 +193,9 @@ function methods:serialise()
       retstr[#retstr+1] = line
    end
    while entries do
-      serialise_entry(entries)
+      if entries.lineno ~= 0 then
+	 serialise_entry(entries)
+      end
       entries = entries.next
    end
    serialise_entry({})
@@ -194,9 +264,7 @@ local function parse_config(conf, confname)
       return nil, err
    end
    -- Successfully loaded the settings, they're in settings and front_entry
-   -- points to line zero which we can now detach
-   front_entry.next.prev = nil
-   front_entry = front_entry.next
+   -- points to line zero which we keep, for cleanliness
    -- Construct a return object ready for magic
    local ret = setmetatable({}, clod_mt)
    metadata[ret] = {