Walking AST in Lua filters

Walking AST in Lua filters

[Martin Mares]

[-- Attachment #1.1: Type: text/plain, Size: 1373 bytes --]

Hello!

I am trying to write a lua filter for automatic insertion of non-breakable 
spaces in various situations.
In my first attempt, I wanted to process all Space elements in a paragraph 
and for each of them,
look at the previous element and depending on it, either keep the Space or 
convert it to a Str
with a non-breakable space.

Therefore I need to walk through all children of the Para element 
recursively in some order,
which preserves locality (e.g., pre-order). I tried to use 
pandoc.walk_block, but the order in
which it visited children was strangely non-local.

Could you please give me a hint if there is an elegant solution?

So far, the only possibility I was able to come up with was to reimplement 
walk_block in Lua.

Have a nice day
Martin Mareš

-- 
You received this message because you are subscribed to the Google Groups "pandoc-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pandoc-discuss+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/Ez6ZCGd0@public.gmane.org
To post to this group, send email to pandoc-discuss-/JYPxA39Uh5TLH3MbocFF+G/Ez6ZCGd0@public.gmane.org
To view this discussion on the web visit https://groups.google.com/d/msgid/pandoc-discuss/7a25fa50-f6a8-4928-80a6-81a28afb5250%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[-- Attachment #1.2: Type: text/html, Size: 1929 bytes --]

Re: Walking AST in Lua filters

[John MacFarlane]

walk_block wraps functions from Text.Pandoc.Walk,
and these do a depth-first traversal, which won't
preserve order -- essentially, everything in a nested
context will be processed before the non-nested stuff.

For your purposes, writing the traversal in lua may
be necessary.  But if in the course of this you
think of ways the lua API could be improved, don't
hesitate to suggest them here.

Re: Walking AST in Lua filters

[Martin Mares]

Hello!

> walk_block wraps functions from Text.Pandoc.Walk,
> and these do a depth-first traversal, which won't
> preserve order -- essentially, everything in a nested
> context will be processed before the non-nested stuff.

Thanks for the explanation.

I expected ordinary depth-first traversal, which would recurse
on the children of a node from the left to the right, regardless of
which ones have further descendants. That would guarantee not only
that children are processed before the parent (which is already
the case), but also that the order in which the leaves are visited
corresponds to the text of the document.

It would be really nice to have an option for using this order
in the Lua API.

		Thanks
				Martin Mares

Re: Walking AST in Lua filters

[John MacFarlane]

Okay, I spoke too soon.  I just did a test, and the
functions from Text.Pandoc.Walk do the traversal in
the expected, order-preserving way.

You can verify that by trying this filter:

```
-- walktest.hs
import Text.Pandoc.Definition
import Text.Pandoc.JSON
import System.IO

main = toJSONFilter f

f :: Inline -> IO Inline
f (Str s) = do
  hPutStrLn stderr s
  return (Str s)
f (Space) = do
  hPutStrLn stderr "_"
  return Space
f x = return x
```

Demonstration:
```
% echo "This is *nested*" | pandoc -o /dev/null --filter walktest.hs
This
_
is
_
nested
```

Now compare the lua filter:
```
-- walkblock.lua
function Para(el)
    return pandoc.walk_block(el,
      { Str = function(e) print(e.text) end,
        Space = function(e) print('_') end
      })
end
```

Demonstration:
```
% echo "This is *nested*" | pandoc -o /dev/null --lua-filter walkblock.lua 
nested
This
_
is
_
```

So, I conclude that there's an issue with the
walk_block function in the pandoc module.  Let's see
if @tarleb has any ideas about how to fix this!


Martin Mares <mj-+ZI9xUNit7I@public.gmane.org> writes:

> Hello!
>
>> walk_block wraps functions from Text.Pandoc.Walk,
>> and these do a depth-first traversal, which won't
>> preserve order -- essentially, everything in a nested
>> context will be processed before the non-nested stuff.
>
> Thanks for the explanation.
>
> I expected ordinary depth-first traversal, which would recurse
> on the children of a node from the left to the right, regardless of
> which ones have further descendants. That would guarantee not only
> that children are processed before the parent (which is already
> the case), but also that the order in which the leaves are visited
> corresponds to the text of the document.
>
> It would be really nice to have an option for using this order
> in the Lua API.
>
> 		Thanks
> 				Martin Mareš

-- 
You received this message because you are subscribed to the Google Groups "pandoc-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pandoc-discuss+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/Ez6ZCGd0@public.gmane.org
To post to this group, send email to pandoc-discuss-/JYPxA39Uh5TLH3MbocFF+G/Ez6ZCGd0@public.gmane.org
To view this discussion on the web visit https://groups.google.com/d/msgid/pandoc-discuss/m2lg9379ya.fsf%40johnmacfarlane.net.
For more options, visit https://groups.google.com/d/optout.

Re: Walking AST in Lua filters

[Albert Krewinkel]

The problems seems to be with the `Walkable [Inline] [Inline]`
instance used by Lua filters. I can reproduce the Lua filter
output by changing

    main = toJSONFilter f

to

    main = toJSONFilter (mapM f :: [Inline] -> IO [Inline])

The current instance definition is

    instance OVERLAPS
             Walkable [Inline] [Inline] where
      walkM f = T.traverse (walkInlineM f) >=> f
      query f inlns = f inlns <> mconcat (map (queryInline f) inlns)

There's probably an obvious definition which preserves order, but
I fail to see it right now.


John MacFarlane writes:

> Okay, I spoke too soon.  I just did a test, and the
> functions from Text.Pandoc.Walk do the traversal in
> the expected, order-preserving way.
>
> You can verify that by trying this filter:
>
> ```
> -- walktest.hs
> import Text.Pandoc.Definition
> import Text.Pandoc.JSON
> import System.IO
>
> main = toJSONFilter f
>
> f :: Inline -> IO Inline
> f (Str s) = do
>   hPutStrLn stderr s
>   return (Str s)
> f (Space) = do
>   hPutStrLn stderr "_"
>   return Space
> f x = return x
> ```
>
> Demonstration:
> ```
> % echo "This is *nested*" | pandoc -o /dev/null --filter walktest.hs
> This
> _
> is
> _
> nested
> ```
>
> Now compare the lua filter:
> ```
> -- walkblock.lua
> function Para(el)
>     return pandoc.walk_block(el,
>       { Str = function(e) print(e.text) end,
>         Space = function(e) print('_') end
>       })
> end
> ```
>
> Demonstration:
> ```
> % echo "This is *nested*" | pandoc -o /dev/null --lua-filter walkblock.lua
> nested
> This
> _
> is
> _
> ```
>
> So, I conclude that there's an issue with the
> walk_block function in the pandoc module.  Let's see
> if @tarleb has any ideas about how to fix this!
>
>
> Martin Mares <mj-+ZI9xUNit7I@public.gmane.org> writes:
>
>> Hello!
>>
>>> walk_block wraps functions from Text.Pandoc.Walk,
>>> and these do a depth-first traversal, which won't
>>> preserve order -- essentially, everything in a nested
>>> context will be processed before the non-nested stuff.
>>
>> Thanks for the explanation.
>>
>> I expected ordinary depth-first traversal, which would recurse
>> on the children of a node from the left to the right, regardless of
>> which ones have further descendants. That would guarantee not only
>> that children are processed before the parent (which is already
>> the case), but also that the order in which the leaves are visited
>> corresponds to the text of the document.
>>
>> It would be really nice to have an option for using this order
>> in the Lua API.
>>
>> 		Thanks
>> 				Martin Mareš


--
Albert Krewinkel
GPG: 8eed e3e2 e8c5 6f18 81fe  e836 388d c0b2 1f63 1124

-- 
You received this message because you are subscribed to the Google Groups "pandoc-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pandoc-discuss+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/Ez6ZCGd0@public.gmane.org
To post to this group, send email to pandoc-discuss-/JYPxA39Uh5TLH3MbocFF+G/Ez6ZCGd0@public.gmane.org
To view this discussion on the web visit https://groups.google.com/d/msgid/pandoc-discuss/87sh3asso3.fsf%40zeitkraut.de.
For more options, visit https://groups.google.com/d/optout.

Re: Walking AST in Lua filters

[John MacFarlane]

Okay, that's good to know.  Is there any way to avoid
using the [a] -> m [a] instance in defining
walk_block, I wonder?

Albert Krewinkel <albert+pandoc-9EawChwDxG8hFhg+JK9F0w@public.gmane.org> writes:

> The problems seems to be with the `Walkable [Inline] [Inline]`
> instance used by Lua filters. I can reproduce the Lua filter
> output by changing
>
>     main = toJSONFilter f
>
> to
>
>     main = toJSONFilter (mapM f :: [Inline] -> IO [Inline])
>
> The current instance definition is
>
>     instance OVERLAPS
>              Walkable [Inline] [Inline] where
>       walkM f = T.traverse (walkInlineM f) >=> f
>       query f inlns = f inlns <> mconcat (map (queryInline f) inlns)
>
> There's probably an obvious definition which preserves order, but
> I fail to see it right now.
>
>
> John MacFarlane writes:
>
>> Okay, I spoke too soon.  I just did a test, and the
>> functions from Text.Pandoc.Walk do the traversal in
>> the expected, order-preserving way.
>>
>> You can verify that by trying this filter:
>>
>> ```
>> -- walktest.hs
>> import Text.Pandoc.Definition
>> import Text.Pandoc.JSON
>> import System.IO
>>
>> main = toJSONFilter f
>>
>> f :: Inline -> IO Inline
>> f (Str s) = do
>>   hPutStrLn stderr s
>>   return (Str s)
>> f (Space) = do
>>   hPutStrLn stderr "_"
>>   return Space
>> f x = return x
>> ```
>>
>> Demonstration:
>> ```
>> % echo "This is *nested*" | pandoc -o /dev/null --filter walktest.hs
>> This
>> _
>> is
>> _
>> nested
>> ```
>>
>> Now compare the lua filter:
>> ```
>> -- walkblock.lua
>> function Para(el)
>>     return pandoc.walk_block(el,
>>       { Str = function(e) print(e.text) end,
>>         Space = function(e) print('_') end
>>       })
>> end
>> ```
>>
>> Demonstration:
>> ```
>> % echo "This is *nested*" | pandoc -o /dev/null --lua-filter walkblock.lua
>> nested
>> This
>> _
>> is
>> _
>> ```
>>
>> So, I conclude that there's an issue with the
>> walk_block function in the pandoc module.  Let's see
>> if @tarleb has any ideas about how to fix this!
>>
>>
>> Martin Mares <mj-+ZI9xUNit7I@public.gmane.org> writes:
>>
>>> Hello!
>>>
>>>> walk_block wraps functions from Text.Pandoc.Walk,
>>>> and these do a depth-first traversal, which won't
>>>> preserve order -- essentially, everything in a nested
>>>> context will be processed before the non-nested stuff.
>>>
>>> Thanks for the explanation.
>>>
>>> I expected ordinary depth-first traversal, which would recurse
>>> on the children of a node from the left to the right, regardless of
>>> which ones have further descendants. That would guarantee not only
>>> that children are processed before the parent (which is already
>>> the case), but also that the order in which the leaves are visited
>>> corresponds to the text of the document.
>>>
>>> It would be really nice to have an option for using this order
>>> in the Lua API.
>>>
>>> 		Thanks
>>> 				Martin Mareš
>
>
> --
> Albert Krewinkel
> GPG: 8eed e3e2 e8c5 6f18 81fe  e836 388d c0b2 1f63 1124
>
> -- 
> You received this message because you are subscribed to the Google Groups "pandoc-discuss" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to pandoc-discuss+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/Ez6ZCGd0@public.gmane.org
> To post to this group, send email to pandoc-discuss-/JYPxA39Uh5TLH3MbocFF+G/Ez6ZCGd0@public.gmane.org
> To view this discussion on the web visit https://groups.google.com/d/msgid/pandoc-discuss/87sh3asso3.fsf%40zeitkraut.de.
> For more options, visit https://groups.google.com/d/optout.

-- 
You received this message because you are subscribed to the Google Groups "pandoc-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pandoc-discuss+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/Ez6ZCGd0@public.gmane.org
To post to this group, send email to pandoc-discuss-/JYPxA39Uh5TLH3MbocFF+G/Ez6ZCGd0@public.gmane.org
To view this discussion on the web visit https://groups.google.com/d/msgid/pandoc-discuss/m2600671xy.fsf%40johnmacfarlane.net.
For more options, visit https://groups.google.com/d/optout.

Re: Walking AST in Lua filters

[Albert Krewinkel]

John MacFarlane writes:

> Okay, that's good to know.  Is there any way to avoid
> using the [a] -> m [a] instance in defining
> walk_block, I wonder?

I'm not sure. We need to walk the document with functions `Inline -> m
[Inline]` and `Block -> m [Block]` to allow for splicing and element
deletion. One could use `Walkable Inline b` by mis-using `ListT`,

    walkM :: (Inline -> ListT m Inline) -> b -> ListT m b

but that seems like a bad hack, especially since `ListT IO` is, as I
understand, not a monad.

The least problematic way might be to write a specialized AST traversal
for Lua filters. The advantage of that approach is that we could switch
from the current multi-traversal filter application (i.e., one traversal
for each of Inlines → Blocks → Meta → Pandoc) to a more intuitive,
single traversal application.


> Albert Krewinkel <albert+pandoc-9EawChwDxG8hFhg+JK9F0w@public.gmane.org> writes:
>
>> The problems seems to be with the `Walkable [Inline] [Inline]`
>> instance used by Lua filters. I can reproduce the Lua filter
>> output by changing
>>
>>     main = toJSONFilter f
>>
>> to
>>
>>     main = toJSONFilter (mapM f :: [Inline] -> IO [Inline])
>>
>> The current instance definition is
>>
>>     instance OVERLAPS
>>              Walkable [Inline] [Inline] where
>>       walkM f = T.traverse (walkInlineM f) >=> f
>>       query f inlns = f inlns <> mconcat (map (queryInline f) inlns)
>>
>> There's probably an obvious definition which preserves order, but
>> I fail to see it right now.
>>
>>
>> John MacFarlane writes:
>>
>>> Okay, I spoke too soon.  I just did a test, and the
>>> functions from Text.Pandoc.Walk do the traversal in
>>> the expected, order-preserving way.
>>>
>>> You can verify that by trying this filter:
>>>
>>> ```
>>> -- walktest.hs
>>> import Text.Pandoc.Definition
>>> import Text.Pandoc.JSON
>>> import System.IO
>>>
>>> main = toJSONFilter f
>>>
>>> f :: Inline -> IO Inline
>>> f (Str s) = do
>>>   hPutStrLn stderr s
>>>   return (Str s)
>>> f (Space) = do
>>>   hPutStrLn stderr "_"
>>>   return Space
>>> f x = return x
>>> ```
>>>
>>> Demonstration:
>>> ```
>>> % echo "This is *nested*" | pandoc -o /dev/null --filter walktest.hs
>>> This
>>> _
>>> is
>>> _
>>> nested
>>> ```
>>>
>>> Now compare the lua filter:
>>> ```
>>> -- walkblock.lua
>>> function Para(el)
>>>     return pandoc.walk_block(el,
>>>       { Str = function(e) print(e.text) end,
>>>         Space = function(e) print('_') end
>>>       })
>>> end
>>> ```
>>>
>>> Demonstration:
>>> ```
>>> % echo "This is *nested*" | pandoc -o /dev/null --lua-filter walkblock.lua
>>> nested
>>> This
>>> _
>>> is
>>> _
>>> ```
>>>
>>> So, I conclude that there's an issue with the
>>> walk_block function in the pandoc module.  Let's see
>>> if @tarleb has any ideas about how to fix this!
>>>
>>>
>>> Martin Mares <mj-+ZI9xUNit7I@public.gmane.org> writes:
>>>
>>>> Hello!
>>>>
>>>>> walk_block wraps functions from Text.Pandoc.Walk,
>>>>> and these do a depth-first traversal, which won't
>>>>> preserve order -- essentially, everything in a nested
>>>>> context will be processed before the non-nested stuff.
>>>>
>>>> Thanks for the explanation.
>>>>
>>>> I expected ordinary depth-first traversal, which would recurse
>>>> on the children of a node from the left to the right, regardless of
>>>> which ones have further descendants. That would guarantee not only
>>>> that children are processed before the parent (which is already
>>>> the case), but also that the order in which the leaves are visited
>>>> corresponds to the text of the document.
>>>>
>>>> It would be really nice to have an option for using this order
>>>> in the Lua API.
>>>>
>>>> 		Thanks
>>>> 				Martin Mareš
>>
>>
>> --
>> Albert Krewinkel
>> GPG: 8eed e3e2 e8c5 6f18 81fe  e836 388d c0b2 1f63 1124
>>
>> --
>> You received this message because you are subscribed to the Google Groups "pandoc-discuss" group.
>> To unsubscribe from this group and stop receiving emails from it, send an email to pandoc-discuss+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/Ez6ZCGd0@public.gmane.org
>> To post to this group, send email to pandoc-discuss-/JYPxA39Uh5TLH3MbocFF+G/Ez6ZCGd0@public.gmane.org
>> To view this discussion on the web visit https://groups.google.com/d/msgid/pandoc-discuss/87sh3asso3.fsf%40zeitkraut.de.
>> For more options, visit https://groups.google.com/d/optout.


--
Albert Krewinkel
GPG: 8eed e3e2 e8c5 6f18 81fe  e836 388d c0b2 1f63 1124

-- 
You received this message because you are subscribed to the Google Groups "pandoc-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pandoc-discuss+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/Ez6ZCGd0@public.gmane.org
To post to this group, send email to pandoc-discuss-/JYPxA39Uh5TLH3MbocFF+G/Ez6ZCGd0@public.gmane.org
To view this discussion on the web visit https://groups.google.com/d/msgid/pandoc-discuss/87r2iurtka.fsf%40zeitkraut.de.
For more options, visit https://groups.google.com/d/optout.

Re: Walking AST in Lua filters

[John MacFarlane]

Albert Krewinkel <albert+pandoc-9EawChwDxG8hFhg+JK9F0w@public.gmane.org> writes:

> John MacFarlane writes:
>
>> Okay, that's good to know.  Is there any way to avoid
>> using the [a] -> m [a] instance in defining
>> walk_block, I wonder?
>
> I'm not sure. We need to walk the document with functions `Inline -> m
> [Inline]` and `Block -> m [Block]` to allow for splicing and element
> deletion. One could use `Walkable Inline b` by mis-using `ListT`,
>
>     walkM :: (Inline -> ListT m Inline) -> b -> ListT m b
>
> but that seems like a bad hack, especially since `ListT IO` is, as I
> understand, not a monad.

Ah yes, "this does not yield a monad unless the
argument monad is commutative." IO is definitely
not commutative.

> The least problematic way might be to write a specialized AST traversal
> for Lua filters. The advantage of that approach is that we could switch
> from the current multi-traversal filter application (i.e., one traversal
> for each of Inlines → Blocks → Meta → Pandoc) to a more intuitive,
> single traversal application.

That sounds like a good plan, especially if there's a
way to do this that doesn't require specialized
matching on particular types of nodes, which would
have to be kept in sync with changes to pandoc-types.

-- 
You received this message because you are subscribed to the Google Groups "pandoc-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pandoc-discuss+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/Ez6ZCGd0@public.gmane.org
To post to this group, send email to pandoc-discuss-/JYPxA39Uh5TLH3MbocFF+G/Ez6ZCGd0@public.gmane.org
To view this discussion on the web visit https://groups.google.com/d/msgid/pandoc-discuss/yh480kbm9w3jjj.fsf%40johnmacfarlane.net.
For more options, visit https://groups.google.com/d/optout.