Checking whether some object has been already tested

Question

I have a script that is intended to check whether some value (e.g. option or function argument) matches some model. I want my script to be able to check recursive data structures. So the question is: is there more efficient way then iterating over some list that contains references to already checked Lists and Dictionaries. Example code:

function s:AlreadyChecked(arg, checkedlst)
    if type(a:arg)!=type([]) && type(a:arg)!=type({})
        return 0
    endif
    for obj in a:checkedlst
        if a:arg is obj
            return 1
        endif
    endfor
    call add(a:checkedlst, a:arg)
    return 0
endfunction

Seeking for a way to sort checkedlst (that is to compare references, but not values found by them) or even to use a hash.

Answer 1

As I'm guessing you've already discovered, Vim doesn't allow List or Dictionary variables to be used as dictionary keys. That means you can't, for example, populate a "checked" dictionary like this:

" Unless k is a String, this won't work.
:let checked[k] = 1

It also lacks a straightforward way to generate a unique String from a List or Dictionary, so this isn't reliable either:

:let checked[ string(k) ] = 1

A better approach is to mark the data structures themselves instead of trying to build a hashtable. If you don't mind temporarily making your data structures read-only, one way to do that is to use :lockvar:

:let someDict = {}
:let someDict['foo'] = [1, 2, 3]
:lockvar 1 someDict

That marks someDict as read-only. (The 1 limits the locking to the top level of the Dictionary, so nested structures aren't automatically locked.) A variable's lock state can be inspected like this:

:echo islocked('someDict')
1

:echo islocked("someDict['foo']")
0

:echo islocked("someDict['foo'][0]")
0

Unlocking is just as easy:

:unlockvar 1 someDict

So now we have a technique for marking individual levels of nested data structures as "checked", a way to query whether or not a particular level is marked, and a way to remove all the marks when we're done. Putting it all together, AlreadyChecked() can be modified like so:

function! s:AlreadyChecked(arg, checkedlst)

    if type(a:arg)!=type([]) && type(a:arg)!=type({})
        return 0
    endif

    " If this particular List or Dictionary has already been checked, just
    " return true immediately.
    "
    if islocked('a:arg')
        echo "Already checked."
        return 1
    endif

    " Lock the List or Dictionary to mark this item as already
    " checked. Note that only the top level of the List or Dictionary
    " is locked; values are not locked.
    "
    lockvar 1 a:arg

    " Remember everything we've locked, so it can be unlocked once
    " we're done.
    "
    call add(a:checkedlst, a:arg)

    return 0

endfunction

Once you're done checking, just remove all the locks:

for obj in a:checkedlst
    unlockvar 1 obj
endfor

Hope this helps. It's a hackish abuse of the locking facility, but perhaps it will do what you need.