[cpp] export container types

[ftynse]

Was there any attempt to export container types like isl_*_list and isl_*_to_* ?

I can see either some conversion to std::vector and std::unordered_map, or exposing STL-style iterators from otherwise opaque classes.

[tobiasgrosser]

We were thinking of adding STL-style iterators. But nobody implemented this yet. Would be great to have. As they are random access, this might indeed not be so difficult.

[tobiasgrosser]

@Meinersbur had some ideas how to do this best.

[Meinersbur]

I was experimenting with isl_*_iterator types. To avoid having a new iterator type for each thing it could iterate (e.g. isl_map_basic_map_iterator, isl_basic_map_list_iterator), the difficulty was to support multiple internal data structures (mainly hashtables and flat arrays, but their size is stored differently everwhere).

[ftynse]

What was the problem with having multiple iterator classes? I see two category of things worthy of iterator behavior: - implicitly "iterable" objects, like a map is a collection of basic_maps and a union_map is a collection of maps; - explicitly-defined collections, isl_*_list. For the second, I was thinking about a class template isl_list_iterator which is aware of the internals of the list.

…

On 25/07/17 15:02, Michael Kruse wrote: I was experimenting with isl_*_iterator types. To avoid having a new iterator type for each thing it could iterate (e.g. isl_map_basic_map_iterator, isl_basic_map_list_iterator), the difficulty was to support multiple internal data structures (mainly hashtables and flat arrays, but their size is stored differently everwhere). — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#5 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABcTa8Fzb_h8Du9zhUhkbrq41vkpQhEfks5sRedZgaJpZM4Oiadw>.

[Meinersbur]

What was the problem with having multiple iterator classes?

• No genericity for the library's user / missing abstraction.
• Lot's and lot's of new public functions necessary.
• Library blow-up with boilerplate code.
• It is common for C++ to make a template for this, but not really C-like.
• In contrast to C++ templates, no performance advantage. Unless we declare them in the headers, they cannot be inlined. Speed will be governed by the function call overhead.

For the second, I was thinking about a class template isl_list_iterator
which is aware of the internals of the list.

IMHO the C++ binding should only use the public C interface.

[tobiasgrosser]

I agree with @ftynse, it seems discussing isl_*_list and implicitly "iterable" objects separately is a good idea.

I would expect that for list types, we automatically derive a begin(), and end() iterator. I assume we can use the functions isl_element_list_n_element, isl_element_list_get_element, and isl_element_list_get_element to make this happen to implement an iterator here.

For functions such as isl_set_foreach_point, I would just derive an iterator that calls the foreach function, adds all elements to a vector, and then uses the iterator of this vector. I doubt there will be a performance problem here (but we can fix it later). Even if we want to fix this today, having a already working iterator is a good start to see what is missing in the isl interface to make the iterator more efficient.

[tobiasgrosser]

@ftynse: Any plans to move this forward? I would be glad to see a patch we can upstream?

[ftynse]

It is in my queue, which starts to get longish.

…

On 01/08/17 19:02, Tobias Grosser wrote: @ftynse <https://github.com/ftynse>: Any plans to move this forward? I would be glad to see a patch we can upstream? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#5 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABcTawB-8Smp1ZceQzTAxCDG6PiNazZVks5sT1ongaJpZM4Oiadw>.

[tobiasgrosser]

Same here. If we all work on this together, chances are that less work needs to be done overall. Until know it seems you guys just pile up a large set of islpp hacks. ;-) I am glad to review patches. Best, Tobias

…

On Tue, Aug 1, 2017, at 19:12, ftynse wrote: It is in my queue, which starts to get longish. On 01/08/17 19:02, Tobias Grosser wrote: > > @ftynse <https://github.com/ftynse>: Any plans to move this forward? I > would be glad to see a patch we can upstream? > > — > You are receiving this because you were mentioned. > Reply to this email directly, view it on GitHub > <#5 (comment)>, or > mute the thread > <https://github.com/notifications/unsubscribe-auth/ABcTawB-8Smp1ZceQzTAxCDG6PiNazZVks5sT1ongaJpZM4Oiadw>. > -- You are receiving this because you commented. Reply to this email directly or view it on GitHub: #5 (comment)

[ftynse]

Let's proceed with lists first. We already have some public functions like union_map_to_basic_map_list, which we can expose once we have the list iterators.

The problem for me with lists is that list element type name is included in the signature, in some cases twice, like isl_id_list_get_id. If we had a set of overloaded functions %elementtype% isl::list_get(%listtype%, int) or int isl::list_n(%listtype%), we could create a template class for iterators that relies on these functions. However, I cannot immediately see how we can make a standalone begin for that. Something like

template <typename E>
class list_iterator {
  size_t pos, n;
  template <typename List>
  friend isl::list_iterator<E> begin(List);
  /*...*/
};

template <typename Elem, typename List>
isl::list_iterator<Elem> begin(List lst) {
  isl::list_iterator<Elem> it;
  it.pos = 0;
  it.n = isl::list_n_element(lst);
  return it;
}

won't be able to deduce Elem. We will need a sort of list_traits that would decay a list type into an element type, potentially through generated template specializations.

At this point, it appears reasonable to just have a template class isl::list instead, which would include the non-template iterator class and member begin/end functions. Overloaded functions are still useful unless we want to generate a bunch of specializations.

So I guess my question here is: can we get those overloads generated?

[ftynse]

@TobiG the problem with creating a vector for implicit collections is that a new vector will be created on each call to begin(), and the iterators of different vectors won't compare true. I find it reasonable to expect set.foreach_point_begin() == set.foreach_point_begin() to be true.

[tobiasgrosser]

@ftynse : I agree with the vector issue. Let's postpone it for now.

Regarding the lists, the first patch to be written is to expose some lists to the isl C++ bindings. This probably requires some minor macro hacking, as we likely do not want to expose all lists (isl_band_list e.g. should likely not be exposed).

If you want to go crazy with C++ the following might work, assuming we have list_add() always exported and already C++ types for it:

https://stackoverflow.com/questions/27879815/c11-get-type-of-first-second-etc-argument-similar-to-result-of

Realistically, I would just adapt the generator to print iterators for any type which ends with "_list".

[tobiasgrosser]

It seems even without iterators exporting isl_id_list would be useful for #11.

[tobiasgrosser]

Interestingly, isl lists also have a function:

isl_##EL##_list_foreach

It seems as if we come up with a solution for the normal foreach loop, this would also cover lists.

[tobiasgrosser]

@ftynse:

@TobiG the problem with creating a vector for implicit collections is that a new vector will be created on > each call to begin(), and the iterators of different vectors won't compare true. I find it reasonable to
expect set.foreach_point_begin() == set.foreach_point_begin() to be true.

This probably depends on the comparison function. Does anything prevent us from just comparing the position in the vector and the (pointer to the isl object) from which the vectors have been constructed? In case the iterator keeps a reference to the object we work on it cannot even be modified behind our back. let me give this a quick shot.