Circular lists/shared structures in org-element parse-tree

Circular lists/shared structures in org-element parse-tree

[Thorsten Jolitz]

[Originally posted on the Org-mode mailing list, but I post it here too
since it is more an elisp oriented mailing list]

Hi List, 

I wonder how I can find out in a (elisp) program the points in the parse
tree (returned by org-element-parse-buffer) where shared structures are
used. 

In the read-syntax, its easy to see (especially with `print-circle' set
to non-nil):

#+begin_src emacs-lisp
  #2=(org-data nil #1=(headline (:raw-value "header 1"
   [...] :parent #2#) [...]  
#+end_src

but when processing the parse tree as a list in elisp, how can I detect the
fact that 

,------------
| :parent #2#
`------------

refers to 

,-----------------
| #2=(org-data nil
`-----------------

i.e. points back to an already existing structure?

-- 
cheers,
Thorsten

Re: Circular lists/shared structures in org-element parse-tree

[Pascal J. Bourguignon]

Thorsten Jolitz <tjolitz@gmail.com> writes:

> [Originally posted on the Org-mode mailing list, but I post it here too
> since it is more an elisp oriented mailing list]
>
> Hi List, 
>
> I wonder how I can find out in a (elisp) program the points in the parse
> tree (returned by org-element-parse-buffer) where shared structures are
> used. 
>
> In the read-syntax, its easy to see (especially with `print-circle' set
> to non-nil):
>
> #+begin_src emacs-lisp
>   #2=(org-data nil #1=(headline (:raw-value "header 1"
>    [...] :parent #2#) [...]  
> #+end_src
>
> but when processing the parse tree as a list in elisp, how can I detect the
> fact that 
>
> ,------------
> | :parent #2#
> `------------
>
> refers to 
>
> ,-----------------
> | #2=(org-data nil
> `-----------------
>
> i.e. points back to an already existing structure?


1- there is not a unique solution in general: it depends on the order in
   which you choose to walk the branches.

2- you just walk the cons tree, checking if you've not already visited
   them.


Something like this:

(let* ((counter 0)
       (objects (make-hash-table)))
   (labels ((walk (object)
              (let ((reference (gethash object objects))))
                 (if reference
                   (already-seen object reference))
                   (progn
                     (new-reference object
                                    (setf (gethash object objects) (incf counter)))
                     (cond
                       ((vector object)  
                         (dotimes (i (length vector))
                           (walk (aref vector i))))
                       ((cons object)
                        (walk (car object))
                        (walk (cdr object)))
                       ( ; you may also want to walk structures,
                         ; hashtable, etc
                        )))))
      (walk root)))

If you don't want to generate references for objects present only once,
then you can transform this in a two-pass algorithm where you first fill
the hash-table with a counter of occurence:

  (incf (gethash object objects 0))

and then only keep and renumber the entries that have a value greater
than 1.



                    
                        
-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
A bad day in () is better than a good day in {}.  
You know you've been lisping too long when you see a recent picture of George 
Lucas and think "Wait, I thought John McCarthy was dead!" -- Dalek_Baldwin

Re: Circular lists/shared structures in org-element parse-tree

[Thorsten Jolitz]

"Pascal J. Bourguignon" <pjb@informatimago.com> writes:

> Thorsten Jolitz <tjolitz@gmail.com> writes:
>
>> [Originally posted on the Org-mode mailing list, but I post it here too
>> since it is more an elisp oriented mailing list]
>>
>> Hi List, 
>>
>> I wonder how I can find out in a (elisp) program the points in the parse
>> tree (returned by org-element-parse-buffer) where shared structures are
>> used. 
>>
>> In the read-syntax, its easy to see (especially with `print-circle' set
>> to non-nil):
>>
>> #+begin_src emacs-lisp
>>   #2=(org-data nil #1=(headline (:raw-value "header 1"
>>    [...] :parent #2#) [...]  
>> #+end_src
>>
>> but when processing the parse tree as a list in elisp, how can I detect the
>> fact that 
>>
>> ,------------
>> | :parent #2#
>> `------------
>>
>> refers to 
>>
>> ,-----------------
>> | #2=(org-data nil
>> `-----------------
>>
>> i.e. points back to an already existing structure?
>
>
> 1- there is not a unique solution in general: it depends on the order in
>    which you choose to walk the branches.
>
> 2- you just walk the cons tree, checking if you've not already visited
>    them.
>
>
> Something like this:
>
> (let* ((counter 0)
>        (objects (make-hash-table)))
>    (labels ((walk (object)
>               (let ((reference (gethash object objects))))
>                  (if reference
>                    (already-seen object reference))
>                    (progn
>                      (new-reference object
>                                     (setf (gethash object objects) (incf counter)))
>                      (cond
>                        ((vector object)  
>                          (dotimes (i (length vector))
>                            (walk (aref vector i))))
>                        ((cons object)
>                         (walk (car object))
>                         (walk (cdr object)))
>                        ( ; you may also want to walk structures,
>                          ; hashtable, etc
>                         )))))
>       (walk root)))
>
> If you don't want to generate references for objects present only once,
> then you can transform this in a two-pass algorithm where you first fill
> the hash-table with a counter of occurence:
>
>   (incf (gethash object objects 0))
>
> and then only keep and renumber the entries that have a value greater
> than 1.

Thank you for the detailled instructions, very helpful indeed! I thought
Emacs might have some inbuilt functionality to deal with circular list,
but it seems to require some individual effort. 

-- 
cheers,
Thorsten

Re: Circular lists/shared structures in org-element parse-tree

[Pascal J. Bourguignon]

Thorsten Jolitz <tjolitz@gmail.com> writes:

> Thank you for the detailled instructions, very helpful indeed! I thought
> Emacs might have some inbuilt functionality to deal with circular list,
> but it seems to require some individual effort. 

But it has, to be able to print circular structures with references.

It may also have to avoid infinite recursions in compile circular code.
Let's try it:

    (defun f (x)
      #1=(if (zerop x)
             1
             (* x . #1#)))

    (byte-compile 'f) --> Error: Lisp nesting exceeds `max-lisp-eval-depth'

So, the emacs lisp compiler doesn't have any provision against circular
code per se, just the usual deep stack protection.  

Indeed, it is not expect to have circular code in general, only circular
data, which will be quoted in code, so that won't recurse while
compiling.

    (require 'cl)

    (defun* g (x)
      (dolist (e '(a . #1=(b . #1#)))
         (if (eq x e)
           (return-from g 'found))))

    (g 'a) --> found
    (g 'z) --> infinite loop.
    (byte-compile 'g) --> #[(x) … 2]

So the only part of lisp that has to deal with circular structures is
the lisp printer (and the lisp reader which must build circular
structures when it finds back references).



Otherwise, trying to generalize and parameterize the algorithm to make
it easily reusable is not so easy.  The proof is in the pudding, I mean,
often, you're interested in the walking itself more than in finding the
loops in the structure.  This loop detection is only useful to avoid
walking circles.  See for example:
https://gitorious.org/patchwork/patchwork/blobs/master/src/mclgui/circular.lisp
compare print-identified-conses/1  with print-identified-conses/2.  It's
Common Lisp code, so you will have to set lexical-binding to t using
emacs-24, and you may have some more work to port it to emacs lisp.  But
it's to illustrate the point that the interesting or complex parts is in
deciding what edge to walk, not to record the node already reached.



-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
A bad day in () is better than a good day in {}.  
You know you've been lisping too long when you see a recent picture of George 
Lucas and think "Wait, I thought John McCarthy was dead!" -- Dalek_Baldwin

Re: Circular lists/shared structures in org-element parse-tree

[Stefan Monnier]

> Thank you for the detailled instructions, very helpful indeed! I thought
> Emacs might have some inbuilt functionality to deal with circular list,
> but it seems to require some individual effort. 

The print code that generates those #N thingies uses pretty much the
same code as the one Pascal J. Bourguignon sent.

I'm not sure what other "inbuilt functionality" could look like.


        Stefan