synced with r21959
[mplayer/greg.git] / playtreeparser.c
blob39378281f37e6ce60feb66db92d2e3fc02fef0ab
2 /// \file
3 /// \ingroup PlaytreeParser
5 #include "config.h"
6 #include <stdlib.h>
7 #include <stdio.h>
8 #include <string.h>
9 #ifdef MP_DEBUG
10 #include <assert.h>
11 #endif
12 #include <errno.h>
13 #include <sys/types.h>
14 #include <sys/stat.h>
15 #include <fcntl.h>
16 #include <unistd.h>
17 #include <ctype.h>
18 #include "m_config.h"
19 #include "playtree.h"
20 #include "playtreeparser.h"
21 #include "stream/stream.h"
22 #include "libmpdemux/demuxer.h"
23 #include "mp_msg.h"
26 extern play_tree_t*
27 asx_parser_build_tree(char* buffer, int ref);
29 #define BUF_STEP 1024
31 #define WHITES " \n\r\t"
33 static void
34 strstrip(char* str) {
35 char* i;
37 if (str==NULL)
38 return;
39 for(i = str ; i[0] != '\0' && strchr(WHITES,i[0]) != NULL; i++)
40 /* NOTHING */;
41 if(i[0] != '\0') {
42 memmove(str,i,strlen(i) + 1);
43 for(i = str + strlen(str) - 1 ; strchr(WHITES,i[0]) != NULL; i--)
44 /* NOTHING */;
45 i[1] = '\0';
46 } else
47 str[0] = '\0';
50 static char*
51 play_tree_parser_get_line(play_tree_parser_t* p) {
52 char *end,*line_end;
53 int r,resize = 0;
55 if(p->buffer == NULL) {
56 p->buffer = malloc(BUF_STEP);
57 p->buffer_size = BUF_STEP;
58 p->iter = p->buffer;
61 if(p->stream->eof && (p->buffer_end == 0 || p->iter[0] == '\0'))
62 return NULL;
64 while(1) {
66 if(resize) {
67 r = p->iter - p->buffer;
68 p->buffer = (char*)realloc(p->buffer,p->buffer_size+BUF_STEP);
69 p->iter = p->buffer + r;
70 p->buffer_size += BUF_STEP;
71 resize = 0;
74 if(p->buffer_size - p->buffer_end > 1 && ! p->stream->eof) {
75 r = stream_read(p->stream,p->buffer + p->buffer_end,p->buffer_size - p->buffer_end - 1);
76 if(r > 0) {
77 p->buffer_end += r;
78 p->buffer[p->buffer_end] = '\0';
82 end = strchr(p->iter,'\n');
83 if(!end) {
84 if(p->stream->eof) {
85 end = p->buffer + p->buffer_end;
86 break;
88 resize = 1;
89 continue;
91 break;
94 line_end = ((*(end-1)) == '\r') ? end-1 : end;
95 if(line_end - p->iter >= 0)
96 p->line = (char*)realloc(p->line,line_end - p->iter+1);
97 else
98 return NULL;
99 if(line_end - p->iter > 0)
100 strncpy(p->line,p->iter,line_end - p->iter);
101 p->line[line_end - p->iter] = '\0';
102 if(end[0] != '\0')
103 end++;
105 if(!p->keep) {
106 if(end[0] != '\0') {
107 p->buffer_end -= end-p->iter;
108 memmove(p->buffer,end,p->buffer_end);
109 p->buffer[p->buffer_end] = '\0';
110 } else
111 p->buffer_end = 0;
112 p->iter = p->buffer;
113 } else
114 p->iter = end;
116 return p->line;
119 static void
120 play_tree_parser_reset(play_tree_parser_t* p) {
121 p->iter = p->buffer;
124 static void
125 play_tree_parser_stop_keeping(play_tree_parser_t* p) {
126 p->keep = 0;
127 if(p->iter && p->iter != p->buffer) {
128 p->buffer_end -= p->iter -p->buffer;
129 if(p->buffer_end)
130 memmove(p->buffer,p->iter,p->buffer_end);
131 p->iter = p->buffer;
136 static play_tree_t*
137 parse_asx(play_tree_parser_t* p) {
138 int comments = 0,get_line = 1;
139 char* line = NULL;
141 mp_msg(MSGT_PLAYTREE,MSGL_V,"Trying asx...\n");
143 while(1) {
144 if(get_line) {
145 line = play_tree_parser_get_line(p);
146 if(!line)
147 return NULL;
148 strstrip(line);
149 if(line[0] == '\0')
150 continue;
152 if(!comments) {
153 if(line[0] != '<') {
154 mp_msg(MSGT_PLAYTREE,MSGL_DBG2,"First char isn't '<' but '%c'\n",line[0]);
155 mp_msg(MSGT_PLAYTREE,MSGL_DBG3,"Buffer = [%s]\n",p->buffer);
156 return NULL;
157 } else if(strncmp(line,"<!--",4) == 0) { // Comments
158 comments = 1;
159 line += 4;
160 if(line[0] != '\0' && strlen(line) > 0)
161 get_line = 0;
162 } else if(strncasecmp(line,"<ASX",4) == 0) // We got an asx element
163 break;
164 else // We don't get an asx
165 return NULL;
166 } else { // Comments
167 char* c;
168 c = strchr(line,'-');
169 if(c) {
170 if (strncmp(c,"--!>",4) == 0) { // End of comments
171 comments = 0;
172 line = c+4;
173 if(line[0] != '\0') // There is some more data on this line : keep it
174 get_line = 0;
176 } else {
177 line = c+1; // Jump the -
178 if(line[0] != '\0') // Some more data
179 get_line = 0;
180 else // End of line
181 get_line = 1;
183 } else // No - on this line (or rest of line) : get next one
184 get_line = 1;
188 mp_msg(MSGT_PLAYTREE,MSGL_V,"Detected asx format\n");
190 // We have an asx : load it in memory and parse
192 while((line = play_tree_parser_get_line(p)) != NULL)
193 /* NOTHING */;
195 mp_msg(MSGT_PLAYTREE,MSGL_DBG3,"Parsing asx file: [%s]\n",p->buffer);
196 return asx_parser_build_tree(p->buffer,p->deep);
199 static char*
200 pls_entry_get_value(char* line) {
201 char* i;
203 i = strchr(line,'=');
204 if(!i || i[1] == '\0')
205 return NULL;
206 else
207 return i+1;
210 typedef struct pls_entry {
211 char* file;
212 char* title;
213 char* length;
214 } pls_entry_t;
216 static int
217 pls_read_entry(char* line,pls_entry_t** _e,int* _max_entry,char** val) {
218 int num,max_entry = (*_max_entry);
219 pls_entry_t* e = (*_e);
220 char* v;
222 v = pls_entry_get_value(line);
223 if(!v) {
224 mp_msg(MSGT_PLAYTREE,MSGL_ERR,"No value in entry %s\n",line);
225 return 0;
228 num = atoi(line);
229 if(num < 0) {
230 num = max_entry+1;
231 mp_msg(MSGT_PLAYTREE,MSGL_WARN,"No entry index in entry %s\nAssuming %d\n",line,num);
233 if(num > max_entry) {
234 e = (pls_entry_t*)realloc(e,num*sizeof(pls_entry_t));
235 memset(&e[max_entry],0,(num-max_entry)*sizeof(pls_entry_t));
236 max_entry = num;
238 (*_e) = e;
239 (*_max_entry) = max_entry;
240 (*val) = v;
242 return num;
246 static play_tree_t*
247 parse_pls(play_tree_parser_t* p) {
248 char *line,*v;
249 pls_entry_t* entries = NULL;
250 int n_entries = 0,max_entry=0,num;
251 play_tree_t *list = NULL, *entry = NULL, *last_entry = NULL;
253 mp_msg(MSGT_PLAYTREE,MSGL_V,"Trying Winamp playlist...\n");
254 while((line = play_tree_parser_get_line(p))) {
255 strstrip(line);
256 if(strlen(line))
257 break;
259 if (!line)
260 return NULL;
261 if(strcasecmp(line,"[playlist]"))
262 return NULL;
263 mp_msg(MSGT_PLAYTREE,MSGL_V,"Detected Winamp playlist format\n");
264 play_tree_parser_stop_keeping(p);
265 line = play_tree_parser_get_line(p);
266 if(!line)
267 return NULL;
268 strstrip(line);
269 if(strncasecmp(line,"NumberOfEntries",15) == 0) {
270 v = pls_entry_get_value(line);
271 n_entries = atoi(v);
272 if(n_entries < 0)
273 mp_msg(MSGT_PLAYTREE,MSGL_DBG2,"Invalid number of entries: very funny!!!\n");
274 else
275 mp_msg(MSGT_PLAYTREE,MSGL_DBG2,"Playlist claims to have %d entries. Let's see.\n",n_entries);
276 line = play_tree_parser_get_line(p);
279 while(line) {
280 strstrip(line);
281 if(line[0] == '\0') {
282 line = play_tree_parser_get_line(p);
283 continue;
285 if(strncasecmp(line,"File",4) == 0) {
286 num = pls_read_entry(line+4,&entries,&max_entry,&v);
287 if(num < 0)
288 mp_msg(MSGT_PLAYTREE,MSGL_ERR,"No value in entry %s\n",line);
289 else
290 entries[num-1].file = strdup(v);
291 } else if(strncasecmp(line,"Title",5) == 0) {
292 num = pls_read_entry(line+5,&entries,&max_entry,&v);
293 if(num < 0)
294 mp_msg(MSGT_PLAYTREE,MSGL_ERR,"No value in entry %s\n",line);
295 else
296 entries[num-1].title = strdup(v);
297 } else if(strncasecmp(line,"Length",6) == 0) {
298 num = pls_read_entry(line+6,&entries,&max_entry,&v);
299 if(num < 0)
300 mp_msg(MSGT_PLAYTREE,MSGL_ERR,"No value in entry %s\n",line);
301 else
302 entries[num-1].length = strdup(v);
303 } else
304 mp_msg(MSGT_PLAYTREE,MSGL_WARN,"Unknown entry type %s\n",line);
305 line = play_tree_parser_get_line(p);
308 for(num = 0; num < max_entry ; num++) {
309 if(entries[num].file == NULL)
310 mp_msg(MSGT_PLAYTREE,MSGL_ERR,"Entry %d don't have a file !!!!\n",num+1);
311 else {
312 mp_msg(MSGT_PLAYTREE,MSGL_DBG2,"Adding entry %s\n",entries[num].file);
313 entry = play_tree_new();
314 play_tree_add_file(entry,entries[num].file);
315 free(entries[num].file);
316 if(list)
317 play_tree_append_entry(last_entry,entry);
318 else
319 list = entry;
320 last_entry = entry;
322 if(entries[num].title) {
323 // When we have info in playtree we add this info
324 free(entries[num].title);
326 if(entries[num].length) {
327 // When we have info in playtree we add this info
328 free(entries[num].length);
332 free(entries);
334 entry = play_tree_new();
335 play_tree_set_child(entry,list);
336 return entry;
340 Reference Ini-Format: Each entry is assumed a reference
342 static play_tree_t*
343 parse_ref_ini(play_tree_parser_t* p) {
344 char *line,*v;
345 play_tree_t *list = NULL, *entry = NULL, *last_entry = NULL;
347 mp_msg(MSGT_PLAYTREE,MSGL_V,"Trying reference-ini playlist...\n");
348 if (!(line = play_tree_parser_get_line(p)))
349 return NULL;
350 strstrip(line);
351 if(strcasecmp(line,"[Reference]"))
352 return NULL;
353 mp_msg(MSGT_PLAYTREE,MSGL_V,"Detected reference-ini playlist format\n");
354 play_tree_parser_stop_keeping(p);
355 line = play_tree_parser_get_line(p);
356 if(!line)
357 return NULL;
358 while(line) {
359 strstrip(line);
360 if(strncasecmp(line,"Ref",3) == 0) {
361 v = pls_entry_get_value(line+3);
362 if(!v)
363 mp_msg(MSGT_PLAYTREE,MSGL_ERR,"No value in entry %s\n",line);
364 else
366 mp_msg(MSGT_PLAYTREE,MSGL_DBG2,"Adding entry %s\n",v);
367 entry = play_tree_new();
368 play_tree_add_file(entry,v);
369 if(list)
370 play_tree_append_entry(last_entry,entry);
371 else
372 list = entry;
373 last_entry = entry;
376 line = play_tree_parser_get_line(p);
379 if(!list) return NULL;
380 entry = play_tree_new();
381 play_tree_set_child(entry,list);
382 return entry;
385 static play_tree_t*
386 parse_m3u(play_tree_parser_t* p) {
387 char* line;
388 play_tree_t *list = NULL, *entry = NULL, *last_entry = NULL;
390 mp_msg(MSGT_PLAYTREE,MSGL_V,"Trying extended m3u playlist...\n");
391 if (!(line = play_tree_parser_get_line(p)))
392 return NULL;
393 strstrip(line);
394 if(strcasecmp(line,"#EXTM3U"))
395 return NULL;
396 mp_msg(MSGT_PLAYTREE,MSGL_V,"Detected extended m3u playlist format\n");
397 play_tree_parser_stop_keeping(p);
399 while((line = play_tree_parser_get_line(p)) != NULL) {
400 strstrip(line);
401 if(line[0] == '\0')
402 continue;
403 /* EXTM3U files contain such lines:
404 * #EXTINF:<seconds>, <title>
405 * followed by a line with the filename
406 * for now we have no place to put that
407 * so we just skip that extra-info ::atmos
409 if(line[0] == '#') {
410 #if 0 /* code functional */
411 if(strncasecmp(line,"#EXTINF:",8) == 0) {
412 mp_msg(MSGT_PLAYTREE,MSGL_INFO,"[M3U] Duration: %dsec Title: %s\n",
413 strtol(line+8,&line,10), line+2);
415 #endif
416 continue;
418 entry = play_tree_new();
419 play_tree_add_file(entry,line);
420 if(!list)
421 list = entry;
422 else
423 play_tree_append_entry(last_entry,entry);
424 last_entry = entry;
427 if(!list) return NULL;
428 entry = play_tree_new();
429 play_tree_set_child(entry,list);
430 return entry;
433 static play_tree_t*
434 parse_smil(play_tree_parser_t* p) {
435 int entrymode=0;
436 char* line,source[512],*pos,*s_start,*s_end;
437 play_tree_t *list = NULL, *entry = NULL, *last_entry = NULL;
439 mp_msg(MSGT_PLAYTREE,MSGL_V,"Trying smil playlist...\n");
441 // Check if smil
442 while((line = play_tree_parser_get_line(p)) != NULL) {
443 strstrip(line);
444 if(line[0] == '\0') // Ignore empties
445 continue;
446 if (strncasecmp(line,"<smil",5)==0 || strncasecmp(line,"<?wpl",5)==0)
447 break; // smil header found
448 else
449 return NULL; //line not smil exit
452 mp_msg(MSGT_PLAYTREE,MSGL_V,"Detected smil playlist format\n");
453 play_tree_parser_stop_keeping(p);
456 //Get entries from smil
457 while((line = play_tree_parser_get_line(p)) != NULL) {
458 strstrip(line);
459 if (line[0]=='\0')
460 continue;
461 if (!entrymode) { // all entries filled so far
462 if (strncasecmp(line,"<video",6)==0 || strncasecmp(line,"<audio",6)==0 || strncasecmp(line,"<media",6)==0) {
463 pos=strstr(line,"src="); // Is source present on this line
464 if (pos !=NULL) {
465 s_start=pos+5;
466 s_end=strchr(s_start,'"');
467 if (s_end == NULL) {
468 mp_msg(MSGT_PLAYTREE,MSGL_V,"Error parsing this source line %s\n",line);
469 continue;
471 if (s_end-s_start> 511) {
472 mp_msg(MSGT_PLAYTREE,MSGL_V,"Cannot store such a large source %s\n",line);
473 continue;
475 strncpy(source,s_start,s_end-s_start);
476 source[(s_end-s_start)]='\0'; // Null terminate
477 entry = play_tree_new();
478 play_tree_add_file(entry,source);
479 if(!list) //Insert new entry
480 list = entry;
481 else
482 play_tree_append_entry(last_entry,entry);
483 last_entry = entry;
484 } else {
485 entrymode=1;
488 } else { //Entry found but not yet filled
489 pos = strstr(line,"src="); // Is source present on this line
490 if (pos != NULL) {
491 entrymode=0;
492 s_start=pos+5;
493 s_end=strchr(s_start,'"');
494 if (s_end == NULL) {
495 mp_msg(MSGT_PLAYTREE,MSGL_V,"Error parsing this source line %s\n",line);
496 continue;
498 if (s_end-s_start> 511) {
499 mp_msg(MSGT_PLAYTREE,MSGL_V,"Cannot store such a large source %s\n",line);
500 continue;
502 strncpy(source,s_start,s_end-s_start);
503 source[(s_end-s_start)]='\0'; // Null terminate
504 entry = play_tree_new();
505 play_tree_add_file(entry,source);
506 if(!list) //Insert new entry
507 list = entry;
508 else
509 play_tree_append_entry(last_entry,entry);
510 last_entry = entry;
515 if(!list) return NULL; // Nothing found
517 entry = play_tree_new();
518 play_tree_set_child(entry,list);
519 return entry;
522 static play_tree_t*
523 embedded_playlist_parse(char *line) {
524 int f=DEMUXER_TYPE_PLAYLIST;
525 stream_t* stream;
526 play_tree_parser_t* ptp;
527 play_tree_t* entry;
529 // Get stream opened to link
530 stream=open_stream(line,0,&f);
531 if(!stream) {
532 mp_msg(MSGT_PLAYTREE,MSGL_WARN,"Can't open playlist %s\n",line);
533 return NULL;
536 //add new playtree
537 mp_msg(MSGT_PLAYTREE,MSGL_V,"Adding playlist %s to element entryref\n",line);
539 ptp = play_tree_parser_new(stream,1);
540 entry = play_tree_parser_get_play_tree(ptp, 1);
541 play_tree_parser_free(ptp);
542 free_stream(stream);
544 return entry;
547 static play_tree_t*
548 parse_textplain(play_tree_parser_t* p) {
549 char* line;
550 char *c;
551 int embedded;
552 play_tree_t *list = NULL, *entry = NULL, *last_entry = NULL;
554 mp_msg(MSGT_PLAYTREE,MSGL_V,"Trying plaintext playlist...\n");
555 play_tree_parser_stop_keeping(p);
557 while((line = play_tree_parser_get_line(p)) != NULL) {
558 strstrip(line);
559 if(line[0] == '\0' || line[0] == '#' || (line[0] == '/' && line[1] == '/'))
560 continue;
562 //Special check for embedded smil or ram reference in file
563 embedded = 0;
564 if (strlen(line) > 5)
565 for(c = line; c[0]; c++ )
566 if ( ((c[0] == '.') && //start with . and next have smil with optional ? or &
567 (tolower(c[1]) == 's') && (tolower(c[2])== 'm') &&
568 (tolower(c[3]) == 'i') && (tolower(c[4]) == 'l') &&
569 (!c[5] || c[5] == '?' || c[5] == '&')) || // or
570 ((c[0] == '.') && // start with . and next have smi or ram with optional ? or &
571 ( ((tolower(c[1]) == 's') && (tolower(c[2])== 'm') && (tolower(c[3]) == 'i')) ||
572 ((tolower(c[1]) == 'r') && (tolower(c[2])== 'a') && (tolower(c[3]) == 'm')) )
573 && (!c[4] || c[4] == '?' || c[4] == '&')) ){
574 entry=embedded_playlist_parse(line);
575 embedded = 1;
576 break;
579 if (!embedded) { //regular file link
580 entry = play_tree_new();
581 play_tree_add_file(entry,line);
584 if (entry != NULL) {
585 if(!list)
586 list = entry;
587 else
588 play_tree_append_entry(last_entry,entry);
589 last_entry = entry;
593 if(!list) return NULL;
594 entry = play_tree_new();
595 play_tree_set_child(entry,list);
596 return entry;
599 play_tree_t*
600 parse_playtree(stream_t *stream, int forced) {
601 play_tree_parser_t* p;
602 play_tree_t* ret;
604 #ifdef MP_DEBUG
605 assert(stream != NULL);
606 #endif
608 p = play_tree_parser_new(stream,0);
609 if(!p)
610 return NULL;
612 ret = play_tree_parser_get_play_tree(p, forced);
613 play_tree_parser_free(p);
615 return ret;
618 static void
619 play_tree_add_basepath(play_tree_t* pt, char* bp) {
620 int i,bl = strlen(bp),fl;
622 if(pt->child) {
623 play_tree_t* i;
624 for(i = pt->child ; i != NULL ; i = i->next)
625 play_tree_add_basepath(i,bp);
626 return;
629 if(!pt->files)
630 return;
632 for(i = 0 ; pt->files[i] != NULL ; i++) {
633 fl = strlen(pt->files[i]);
634 // if we find a full unix path, url:// or X:\ at the beginning,
635 // don't mangle it.
636 if(fl <= 0 || strstr(pt->files[i],"://") || (strstr(pt->files[i],":\\") == pt->files[i] + 1) || (pt->files[i][0] == '/') )
637 continue;
638 // if the path begins with \ then prepend drive letter to it.
639 if (pt->files[i][0] == '\\') {
640 if (pt->files[i][1] == '\\')
641 continue;
642 pt->files[i] = (char*)realloc(pt->files[i],2+fl+1);
643 memmove(pt->files[i] + 2,pt->files[i],fl+1);
644 memcpy(pt->files[i],bp,2);
645 continue;
647 pt->files[i] = (char*)realloc(pt->files[i],bl+fl+1);
648 memmove(pt->files[i] + bl,pt->files[i],fl+1);
649 memcpy(pt->files[i],bp,bl);
653 // Wrapper for play_tree_add_basepath (add base path from file)
654 void play_tree_add_bpf(play_tree_t* pt, char* filename)
656 char *ls, *file;
658 if (pt && filename)
660 file = strdup(filename);
661 if (file)
663 ls = strrchr(file,'/');
664 if(!ls) ls = strrchr(file,'\\');
665 if(ls) {
666 ls[1] = '\0';
667 play_tree_add_basepath(pt,file);
669 free(file);
674 play_tree_t*
675 parse_playlist_file(char* file) {
676 stream_t *stream;
677 play_tree_t* ret;
678 int f=DEMUXER_TYPE_PLAYLIST;
680 stream = open_stream(file,0,&f);
682 if(!stream) {
683 mp_msg(MSGT_PLAYTREE,MSGL_ERR,"Error while opening playlist file %s: %s\n",file,strerror(errno));
684 return NULL;
687 mp_msg(MSGT_PLAYTREE,MSGL_V,"Parsing playlist file %s...\n",file);
689 ret = parse_playtree(stream,1);
690 free_stream(stream);
692 play_tree_add_bpf(ret, file);
694 return ret;
699 play_tree_parser_t*
700 play_tree_parser_new(stream_t* stream,int deep) {
701 play_tree_parser_t* p;
703 p = calloc(1,sizeof(play_tree_parser_t));
704 if(!p)
705 return NULL;
706 p->stream = stream;
707 p->deep = deep;
708 p->keep = 1;
710 return p;
714 void
715 play_tree_parser_free(play_tree_parser_t* p) {
717 #ifdef MP_DEBUG
718 assert(p != NULL);
719 #endif
721 if(p->buffer) free(p->buffer);
722 if(p->line) free(p->line);
723 free(p);
726 play_tree_t*
727 play_tree_parser_get_play_tree(play_tree_parser_t* p, int forced) {
728 play_tree_t* tree = NULL;
730 #ifdef MP_DEBUG
731 assert(p != NULL);
732 #endif
735 while(play_tree_parser_get_line(p) != NULL) {
736 play_tree_parser_reset(p);
738 tree = parse_asx(p);
739 if(tree) break;
740 play_tree_parser_reset(p);
742 tree = parse_pls(p);
743 if(tree) break;
744 play_tree_parser_reset(p);
746 tree = parse_m3u(p);
747 if(tree) break;
748 play_tree_parser_reset(p);
750 tree = parse_ref_ini(p);
751 if(tree) break;
752 play_tree_parser_reset(p);
754 tree = parse_smil(p);
755 if(tree) break;
756 play_tree_parser_reset(p);
758 // Here come the others formats ( textplain must stay the last one )
759 if (forced)
761 tree = parse_textplain(p);
762 if(tree) break;
764 break;
767 if(tree)
768 mp_msg(MSGT_PLAYTREE,MSGL_V,"Playlist successfully parsed\n");
769 else
770 mp_msg(MSGT_PLAYTREE,((forced==1)?MSGL_ERR:MSGL_V),"Error while parsing playlist\n");
772 if(tree)
773 tree = play_tree_cleanup(tree);
775 if(!tree) mp_msg(MSGT_PLAYTREE,((forced==1)?MSGL_WARN:MSGL_V),"Warning: empty playlist\n");
777 return tree;